https://www.freertos.org/a00111.html
https://github.com/aws/amazon-freertos/tree/master/lib/FreeR...
RTOS on Wikipedia: https://en.m.wikipedia.org/wiki/Real-time_operating_system
You don't want a simple double-free to lead to an RCE bug, do you...
To me, the K&R one seems much less readable and also doesn't include the global malloc lock, since even the updated edition of K&R predates standardised threading.
I note it also does the "bp = (Header *)ap - 1;" trick, so if that's undefined behaviour then it's a good example of how hard it is to write C without relying on UB.
Interesting things to consider: Fragmentation prevention, real-time performance, minimizing locking(lock-free techniques, or per-thread free lists), and reusing the freed memory to contain the free list structure. I basically started out whiteboarding what the article lays out and by the end of the interview realized everything wrong with it. It's a good starting point though.
The article looks at lot like the tutorial I wrote a long time ago ... (Every now and then, I see my old PDF in post about implementing allocators, which is disturbing since I wrote it in a hurry as a quick support for a lecture and I found it very poorly written ... )
I think it's interesting to note that using sbrk(2) is a bit deprecated, it's way easier to implement malloc(3) using mmap(2) ...
There's also better ways to handle pointers arithmetic and list management. Someday I'll put only cleaner version only ... Someday ...
realloc(ptr, 0)
return free(ptr), NULL;
return free(ptr), malloc(0);
return NULL;
If the size of the space requested is zero, the behavior is implementation-defined: https://port70.net/~nsz/c/c11/n1570.html#7.22.3
header = (struct header_t*)block - 1;
"A pointer to void may be converted to or from a pointer to any incomplete or object type."
The subtraction is defined by §6.5.6.8, provided that block points to an element of a large enough array object:
"When an expression that has integer type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integer expression."
(There's similar text in other versions of the C standard.)
Accessing the data that is being pointed at is another matter entirely. You must satisfy alignment constraints. You also must not read any memory as a type other than what it was written as, aside from a very limited exception for type char.
The code also isn't undefined behavior... but you are really asking to hit compiler bugs! This is an easy way to confuse gcc into wrongly determining that the code has undefined behavior, and if gcc gets confused then it may determine that a code path can't be taken. Code paths that can't be taken may be deleted.
The main rule here is that memory has a type which is determined by what was last written into it, and you may only read or examine the memory using that type. (for the type, we ignore attributes like the distinction between signed and unsigned) There is a minor exception that is just enough to implement something like memcpy by using a (char⁎) to read and then write as a char. You still aren't supposed to look at that char. These rules apply to memory accessed via pointers, no matter how you cast them, and to memory accessed via union members.
Real compilers differ from that:
Every compiler I'm aware of will not enforce the rules for unions. The gcc compiler promises not to enforce the rules in this case.
Every compiler I'm aware of will let you look at any data that has been read as a char, so the memcpy trick works and you can do things like determine endianness at runtime.
It is legit to initialize a type X variable, take the address of it, cast it from (X⁎) to (Y⁎), pass it through arbitrary data structures and functions to hide the origin from the compiler, cast the (Y⁎) back to (X⁎), and then access the type X variable. If you do this, gcc may generate bad code.
I think he also forgot to implement memalign(3) and posix_memalign(3).
The simplest case is if you know that you will free everything at once, or nothing at all. This allows you to eliminate most bookkeeping and allows a completely lock-free architecture. But there are also more complex cases where you can still get big benefits from exploiting known invariants.
jemalloc allows you to query these invariants if you don't know them, and to use the information to re-configure the allocator to match them :/
I'm pretty sure most modern allocators allow you to do this as well.
> The simplest case is if you know that you will free everything at once, or nothing at all.
That's pretty much a one liner with jemalloc.