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???

Answer 1

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

Answer 2

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.