Memory Allocators 101 – Write a simple memory allocator (2016)
arjunsreedharan.org
Memory Allocators 101 – Write a simple memory allocator (2016)
1–10 of 56 posts
Re: Memory Allocators 101 – Write a simple memory allocator (2016)
#2FreeRTOS 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://github.com/aws/amazon-freertos/tree/master/lib/FreeR...
Re: Memory Allocators 101 – Write a simple memory allocator (2016)
#3 header = (struct header_t*)block - 1;
Re: Memory Allocators 101 – Write a simple memory allocator (2016)
#4Good for didactic purposes but in the real world you may want to try an allocator like tcmalloc or jemalloc.
Re: Memory Allocators 101 – Write a simple memory allocator (2016)
#5header = (struct header_t*)block - 1; Isn't this UB?
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.
Re: Memory Allocators 101 – Write a simple memory allocator (2016)
#6I 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.
Re: Memory Allocators 101 – Write a simple memory allocator (2016)
#7header = (struct header_t*)block - 1; Isn't this UB?
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.
So I suppose that header = (struct header_t*)(block - 1); would be UB then.
Re: Memory Allocators 101 – Write a simple memory allocator (2016)
#8Earlier quoted context omitted.
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.
So I suppose that header = (struct header_t*)(block - 1); would be UB then.
Haven't read the article but if block is void *, this won't compile because sizeof(void) is not defined. And they are probably trying to subtract the sizeof(struct header) hence the expression in your original comment.
Re: Memory Allocators 101 – Write a simple memory allocator (2016)
#9header = (struct header_t*)block - 1; Isn't this UB?
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.
So UB, then? All complaint solutions I could find to this use memcpy() instead. Some use __attribute__ ((__packed__)) for structs, but that seems to have its own gotchas (https://stackoverflow.com/a/7956942), but not relevant here.
Re: Memory Allocators 101 – Write a simple memory allocator (2016)
#10Earlier quoted context omitted.
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.
So UB, then? All complaint solutions I could find to this use memcpy() instead. Some use __attribute__ ((__packed__)) for structs, but that seems to have its own gotchas ( https://stackoverflow.com/a/7956942 ), but not relevant here.
You can't use memcpy here, you have to modify the original memory to mark it as freed. You also can't allocate a new buffer to do the copy into because you are the allocator.
The C standard specifically states that a cast (T ) to and from (void ) is validly defined behavior and that you must get the original pointer back. It's also valid to go from (T ) to (U ) and back again if and only if T and U have the same alignment requirements. (void ) is required to have no alignment requirements because you can't directly de-reference it since the result would have type (void).
__attribute__((__packed__)) is a completely different topic about how the layout of the struct gets decided and what padding might be used.
What's going on here is that malloc() gives the caller a (void ) that points to one position past a (struct header_t ) and then free is casting it back from (void ) to (struct header_t ) and then going back one element in the set to get the original header with the meta-data about the allocation, this is perfectly fine because the pointer is never anything other than (void ) or (struct header_t ) as far as the language is concerned. The caller might turn the element after the (struct header_t ) into something else but the original (struct header_t *) is always the same.