21–30 of 56 posts
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 everythin…
Earlier quoted context omitted.
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 alig…
Isn't this exactly the issue with this malloc implementation? The pointer returned that points past the header by sizeof(header) may not be aligned for subsequent types.
Earlier quoted context omitted.
I’ve heard many gamedevs make specialized allocators for some of their code (the most being arena allocators)...
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.
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).
Earlier quoted context omitted.
The cast is defined by ISO/IEC 9899:1990 §6.3.2.3.1, since block is a pointer to void, and struct header_t is an object type: "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 r…
That part of the standard only covers the cast. It means that you won't mangle a pointer if you cast it to a void pointer and then back to the original pointer type. 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.
Earlier quoted context omitted.
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 alig…
You too are losing your asterisks. Maybe a bit of Unicode can help. The only thing not stripped out by Hacker News seems to be this: ⁎ e2 81 8e
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://github.com/aws/amazon-freertos/tree/master/lib/FreeR...
RTOS on Wikipedia: https://en.m.wikipedia.org/wiki/Real-time_operating_system
Earlier quoted context omitted.
That part of the standard only covers the cast. It means that you won't mangle a pointer if you cast it to a void pointer and then back to the original pointer type. 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.
There doesn't seem to be any pointer dereference on the line that paavoova quoted, so I don't see how your comment applies.
Looking at the full code on the web site, I think it is compliant but dangerous. It is decently likely to trigger gcc bugs.
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 everythin…
If I may ask, what position/designation you were interviewing for?
Earlier 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.
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 memor…
Earlier quoted context omitted.
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 memor…
Is there a way then to write compliant/non-UB/non-buggy memory allocator/GC in C/C++?
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.