
Memory Allocators 101 – Write a simple memory allocator (2016) - DonbunEf7
https://arjunsreedharan.org/post/148675821737/memory-allocators-101
======
kevin_thibedeau
FreeRTOS also has a nice collection of different heap implementations with
varying degrees of sophistication.  They are a good read for those interested
in such things. 

[https://www.freertos.org/a00111.html](https://www.freertos.org/a00111.html)

[https://github.com/aws/amazon-
freertos/tree/master/lib/FreeR...](https://github.com/aws/amazon-
freertos/tree/master/lib/FreeRTOS/portable/MemMang)

~~~
WalterGR
For the uninitiated, RTOS == Real-Time Operating System.  Real-time OSes have
constraints that don’t exist in non-real-time OSes. 

RTOS on Wikipedia: [https://en.m.wikipedia.org/wiki/Real-
time_operating_system](https://en.m.wikipedia.org/wiki/Real-
time_operating_system)

------
q3k
Please don't write custom memory allocators for production code without
seriously considering the security implications of doing so.  The glibc
allocator has benefited from years of security hardening against very creative
attack vectors. 

You don't want a simple double-free to lead to an RCE bug, do you...

------
pjc50
K&R includes an example memory allocator as well:
[https://stackoverflow.com/questions/13159564/explain-this-
im...](https://stackoverflow.com/questions/13159564/explain-this-
implementation-of-malloc-from-the-kr-book)

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. 

------
01100011
Good timing.  I literally had to do this on a whiteboard in an interview about
11 hours ago. 

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. 

~~~
sbmthakur
If I may ask, what position/designation you were interviewing for? 

~~~
dvdbloc
I was asked this as well few months ago for a New Graduate Software Engineer
position to work on embedded avionics. 

------
DivisionSol
I gotta say this is a very topical read.  Was messing around last week or so
trying to learn some x86 Assembly from scratch (Linux subsystem on Windows,)
and memory was very much a sticking point.  Seeing this is helping me grok just
what is sorta going on, which is the best way for me to learn I think. 

------
slashvar2701
While I strongly support the idea that no one should write a generic allocator
in production, writing it as an exercise is a very good idea. 

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

------
apankrat
It's worth noting that

    
    
        realloc(ptr, 0) 
    

behavior is undefined.  The vast majority of modern C libraries will implement
it as

    
    
        return free(ptr), NULL;
    

and it will be documented on man pages as such, but there _are_ systems where
this will be equivalent to

    
    
        return free(ptr), malloc(0);
    

Furthermore, in theory, this is also permitted:

    
    
        return NULL;
    

so as tempting as realloc() might be as a single override for implementing
custom allocators, there are some worms. 

~~~
tom_
Realloc's behaviour is well-defined:
[https://port70.net/~nsz/c/c11/n1570.html#7.22.3.5p3](https://port70.net/~nsz/c/c11/n1570.html#7.22.3.5p3)

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](https://port70.net/~nsz/c/c11/n1570.html#7.22.3)

~~~
richardwhiuk
Being implementation defined is hardly well defined. 

~~~
apankrat
Well, it's the return value in realloc(ptr, 0) case that is implementation-
specific, but its behavior _is_ well-defined - it is expected to "deallocate
the old object". 

My point was that in reality the behavior varies. " Undefined" in a common
tongue sense, not in the terms of the C standard. 

------
rv11
Knuth in one of his volumes ( I think vol I) has described this very nicely. 
way better than what was in K&R.

------
paavoova

      header = (struct header_t*)block - 1;
    

Isn't this UB? 

~~~
simcop2387
Not quite, (void *) is special in this regard IIRC, specifically for cases
like this.  It's a valid pointer but you're required to ensure that any
platform requirements like alignment and size will match the requirements of
what you're doing. 

~~~
burfog
No, (void⁎) is not special in this way.  It just makes things look nicer. 

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. 

~~~
tomp
Is there a way then to write compliant/non-UB/non-buggy memory allocator/GC in
C/C++? 

~~~
burfog
The moment you call sbrk or mmap, you're outside of standard C, so no. 
Treating a pointer as an integer in order to mess with the bits is also a
violation. 

Aside from that, the style used here is probably OK.  It is hard to say what
exactly would trigger the gcc bugs, but I'm pretty sure that a recent gcc
would be OK for this code. 

~~~
nemetroid
> Treating a pointer as an integer in order to mess with the bits is also a
> violation. 

Violation of what exactly?  Converting a pointer to an integer, and vice versa,
is implementation defined.  As long as you're not trying to write
implementation-independent code, it's perfectly fine. 

~~~
burfog
Sure, you can convert, but the whole point of converting is to do things that
violate the C standard.  In theory, a standard-conforming C implementation
could have the bits of a pointer be encrypted by the CPU.  There is nothing
meaningful that you could do to those bits.  Rounding pointers up or down for
alignment is impossible in standards-conforming C code. 

------
anon49124
Is there any effort to extract ORCA from Pony (which is better than Erlang's
and Azul's C4)? 

------
partycoder
Good for didactic purposes but in the real world you may want to try an
allocator like tcmalloc or jemalloc. 

~~~
lasagnaphil
I’ve heard many gamedevs make specialized allocators for some of their code
(the most being arena allocators)...

~~~
01100011
It's fairly common to avoid naked malloc()/free() in systems with real-time
requirements.  Memory pools are a great way to go if you want deterministic
behavior and better reliability. 

~~~
archi42
This.  If you're going to malloc/free equally sized objects often but randomly,
a pool allocator can be a great improvement. 

With real time requirements you often care about your response time or worst
case execution time.  In some areas of embedded, safety critical systems you're
usually prohibited from using heap at all (instead, stuff is put in global
variables or on the stack - so you're only growing in one direction).