Is it possible to write a conformant implementation of malloc in C?

Question

This is a followup to Can a char array be used with any data type?

I know about dynamic memory and common implementations of malloc, references can be found on wikipedia. I also know that the pointer returned by malloc can be cast to whatever the programmer wants, without even a warning because the standard states in 6.3.2.3 Pointers §1

A pointer to void may be converted to or from a pointer to any incomplete or object type. A pointer to any incomplete or object type may be converted to a pointer to void and back again; the result shall compare equal to the original pointer.

The question is assuming I have a freestanding environment without malloc and free, how can I build in conformant C an implementation of those two functions?

If I take some freedom regarding the standard, it is easy:

• start with a large character array
• use a reasonably large alignment (8 should be enough for many architectures)
• implement an algorithm that returns addresses from that array, at that alignment, keeping track of what has been allocated - nice examples can be found in malloc implementation?

The problem is that the effective type of the pointers returned by that implementation will still be char *

And standard says in same paragraph § 7

A pointer to an object or incomplete type may be converted to a pointer to a different object or incomplete type. If the resulting pointer is not correctly aligned for the pointed-to type, the behavior is undefined. Otherwise, when converted back again, the result shall compare equal to the original pointer.

That does not seem to allow me to pretend that what was declared as simple characters can magically contains another type, and even different types in different part of this array or at different moments in same part. Said differently dereferencing such pointers seem undefined behaviour with a strict interpretation of standard. That is why common idioms use memcpy instead of aliasing when you get a byte representation of an object in a string buffer, for example when you read it from a network stream.

So how can I build a conformant implementation of malloc in pure C???

Gyve

You can check alignment using the value of the pointer address (i.e. (ptr &7) == 0 means that you're 64 bit aligned) This means that you can safely cast the pointer to any 64bit aligned type (from char which is 1 byte aligned up to int64_t). Notice that 8 byte alignment limits you to 64bit systems (there are 128 bit systems out there). Also notice that malloc assumes ownership of the stack's break (sbrk) and some standard libraries use malloc internally - this means you shouldn't use sbrk ever. In fact, you should consider it deprecated. – Liles

Assuming C11, you don't need to guess at a "reasonably large alignment"; you can define the array with _Alignas ( max_align_t ). – Taxable

@Myst: If ptr is of pointer type, then ptr & 7 is a constraint violation. You can convert a pointer to an integer type (there may or may not be an integer type for which the conversion doesn't lose information), but there's no defined relationship between the low-order bits of the converted integer and the alignment of the pointer. sbrk is not, and never has been, part of standard C; it's an implementation detail that likely doesn't even exist on many systems. Even POSIX doesn't define it. – Taxable

@KeithThompson. Thank you for the comment. It's these inconsistencies that made me post a comment rather then an answer. As for ptr & 7, the order of bits for the 7 and the ptr should match on all systems (as the system's bit order is consistent), so that the memory alignment will match. As for casting the ptr to an integer, I believe the uintptr_t was designed exactly for this purpose. – Liles

@Myst: Yes, uintptr_t was designed for this purpose, but it's not guaranteed to exist. A system whose largest integer type isn't big enough to hold a converted pointer won't define uintptr_t. (I know of no such systems, but they could exist -- and this is a language-lawyer question.) As for the low-order bits, I've actually worked on systems where they don't behave the way you assume (Cray vector systems, where machine pointers point to 64-bit words and byte offsets are stored in the high-order 3 bits). The standard says very little about how pointers are represented. – Taxable

@KeithThompson - Thanks! I'm happy you took the time to teach me something new 👍🏻. I had no idea that some systems might store pointer data like that... 🤔 – Liles

Check the standard again but char and char* are kind of special because in the olden days char and int where often mixed (tons of function taking a char are defined as taking an int) and void* and char* where confused as well. Some implementation had malloc return char*. Or NULL being (char*)0. I'm not sure if any of that is still legal in modern C but there likely is still legacy cruft left over allowing the conversion from a memory blob declared char[] to any type. – Windproof

Answer 1

The authors of the C Standard put far more effort into specifying behaviors which weren't obviously desirable than those that were, since they expected that sensible compiler writers would support useful behaviors whether or not the Standard mandated it, and since obtuse compilers writers could produce "compliant" implementations that were fully-compliant but completely useless(*).

It was possible to write reliable and efficient malloc() equivalents on many platforms prior to the advent of C89, and I see no reason to believe that the authors intended that people writing C89 compilers for a platform which had been able to handle malloc() equivalents previously would not make those implementations just as capable as their predecessors. Unfortunately, the language which was popular in the 1990s (which was a combined superset of C89 and its predecessors) has been replaced by a poor-quality dialect which omits features that the authors of C89 would have taken for granted and expected others to do likewise.

Even beyond the question of how one acquires memory, a larger issue is that malloc() promises that newly-allocated memory will, at worst, hold Indeterminate Value; because structure types have no trap representations, reading such storage using a pointer of structure type will have defined behavior. If the memory was previously written using some other type, however, a structure-type read would have Undefined Behavior unless either the free() or malloc() physically erases all of the storage in question, thus negating the performance benefit of having malloc() rather than just calloc().

(*)Provided that there exists at least one set of source files that the implementation processes in compliant fashion without UB, an implementation may require arbitrary (perhaps impossibly large) amounts of stack space when given any other set of source files, and behave in arbitrary fashion if that space is unavailable.

Strachan

Thanks for your answer. I'm afraid it is even worse because once a memory zone has got an effective type, it can be accessed at a byte level (to be physically erased) but standard never says that it gives it again no determinated type. Only free can, but I cannot imagine how if free is written in conformant C. – Gyve

@SergeBallesta: Overwriting malloc/calloc storage can change its type, since such storage has no declared type, and the actions which set the effective type only do so until the next time the storage is accessed. A totally horribly written rule, and the "memcpy/memmove" language is IMHO insane (allows opportunities for code breakage but almost no useful optimizations), but it does allow storage to get re-purposed, sort-of. – Strachan

Accepted since it gave precious explainations. – Gyve

@SergeBallesta: Thanks. Maybe I got downvoted because I was editorializing, but I think it's important to make a distinction between the situation that existed in 1989 (where it might have been possible to have a contrived or poor-quality implementation that made a reliable malloc impossible, but no realistic good-quality implementation would do so) and that which exists today (where implementations deliberately break constructs that used to be reliable, and which are necessary for an efficient malloc/free pair). – Strachan

Answer 2

This answer is only an interpretation of the standard, because I could not find an explicit answer in C99 n1256 draft nor in C11 n1570.

The rationale comes from the C++ standard (C++14 draft n4296). 3.8 Object lifetime [basic.life] says (emphasize mine):

§ 1The lifetime of an object of type T begins when:

• storage with the proper alignment and size for type T is obtained, and
• if the object has non-vacuous initialization, its initialization is complete.

The lifetime of an object of type T ends when:

• if T is a class type with a non-trivial destructor (12.4), the destructor call starts, or
• the storage which the object occupies is reused or released.

and

§ 3 The properties ascribed to objects throughout this International Standard apply for a given object only during its lifetime.

I know that C and C++ are different languages, but they are related, and the above is only here to explain the following interpretation

The relevant part in C standard is 7.20.3 Memory management functions.

... The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object and then used to access such an object or an array of such objects in the space allocated (until the space is explicitly deallocated). The lifetime of an allocated object extends from the allocation until the deallocation. Each such allocation shall yield a pointer to an object disjoint from any other object. The pointer returned points to the start (lowest byte address) of the allocated space...

My interpretation is that provided you have a memory zone with correct size and alignement, for example a part of a large character array, but any other type of array of type could be used here you can pretend that it is a pointer to an uninitialized object or array of another type (say T) and convert a char or void pointer to the first byte of the zone to a pointer of the new type (T). But in order to not violate the strict aliasing rule, this zone must no longer be accessed through any previous value or pointer or the initial type - if the initial type was character, it will be still allowed for reading, but writing could lead to trap representation. As this object is not initialized, it can contain a trap representation and reading it before its initialization is undefined behaviour. This T object and its associated pointer will be valid until you decide to use the memory zone for any other usage and the pointer to T becomes dangling at that time.

TL/DR: The strict aliasing rule only mandates that a memory zone can only contain an object of one effective type at one single moment. But you are allowed to re-use the memory zone for an object of a different type provided:

• the size and alignment are compatible
• you initialize the new object with a correct value before using it
• you no longer access the initial object

Because that way you simply use the memory zone as allocated memory.

Per C standard, the lifetime of the initial object will not be ended (static objects last until the end of the program, and automatic ones until the end of their declaring scope), but you can no longer access it because of the strict aliasing rule

Gyve

Since you asked my opinion here : You cannot parcel of parts of an object declared as char [] into objects of other types (except character types), because they do have a declared type. However, you can declare an extern char *. Since you can have this point to an object of no declared type, the compiler must treat it as such. The definition would have to be in a linker script though, which means technically you can't implement malloc() in pure C. – Blacktop

@EOF: Storing the address of an extern char[] into a volatile char*, and then using the storage identified by that should be safe, but even if one had a block of storage with no effective type the C99 rules still wouldn't allow a conforming malloc/free pair that didn't overwrite storage before reuse. I see no basis for believing the C89 aliasing rules were ever intended to apply in cases where the only thing code ever did "directly" with an object was take its address; since that's the only thing one could do directly with a char[], there was no need to write a special rule for it. – Strachan

@EOF: Somehow, however, compiler writers have become convinced that the authors of the Standard didn't intend to say that the only optimizations that were legal were those which were unambiguously allowed by the Standard, but rather that all "optimizations" should be legal unless unambiguously forbidden. – Strachan

@Strachan I'm not following you on the "malloc/free need to overwrite the storage before reuse"-part. Of course the storage needs to be overwritten before reading from it, because the value of the object malloc() returns a pointer to is indeterminate. But I don't see how that is malloc()s business, it's the user of that pointer who has to initialize it (which sets a new effective type). – Blacktop

@EOF: Conforming code is allowed to use a structure type to copy a region of memory that is received from malloc without having first written all the fields. Any fields that weren't written before the copy operation may hold Indeterminate Values in the copy, but if code never reads those fields in the copy except as a charater type, behavior will be defined. – Strachan

@supercat: Sure. How would this necessitate malloc() writing to the storage though? – Blacktop

@EOF: If a user-written malloc didn't zero out the storage, and it had previously been used as another type, using a structure type to copy leftover parts of the storage would lead to UB even if nothing ever examined any part of the copy. – Strachan

@supercat: Reading a partially initialized struct is undefined behavior, full stop. Doesn't matter whether it's automatic or allocated storage. I don't see your point at all. – Blacktop

@EOF: Structs are forbidden from having trap representations; if a struct member has trap representations, copying the struct and then reading that member from copy would invoke UB, but the Standard was deliberately written to avoid requiring programmers to initialize unused structure members which are never going to be (individually) read. – Strachan