17 ms·

So you want custom allocator support in your C library

181 points by nalgeon 3y ago

ghostpepper 3y ago
I wonder how many security-critical memory vulnerabilities would've been avoided over the decades if glibc had been designed with this API instead of the one that became the de-facto standard.
- Someone 3y ago
  Or introduced. I would think that trusting the (possibly compromised) caller to pass the correct size of a to be freed or resized object opens up new possibilities for security vulnerabilities.
  - o11c 3y ago
    Note that libc-style `free` often has to do work to walk through all possible arenas/buckets/whatever to see which one contains the given pointer. If given a size (even just a hint) it can do a much shorter walk without reducing security.
    - tom_ 3y ago
      "Even just a hint" doesn't deserve to be squirreled away in a mere paranthetical. It's what distinguishes some bullshit (the article's suggestion, whereby the allocator carefully checks that you supplied the right value that it already knows and barfs if not) from the actually potentially useful improvement to the API that you suggest. The code that frees very often does not know how much was allocated.
      - lifthrasiir 3y ago
        An allocator that fully trusts the size provided to `free` is hugely unsafe when the size turns out to be incorrect. As an extreme example, the allocator may know that every 4-byte allocation is put into the arena that is aligned to 0x1000-byte block, so it may jump straight into the arena header which won't be there if the size was incorrect. So a real-life allocator is likely to do some checking even when the size is provided, but that checking can be much more simplified in that case.
    - saagarjha 3y ago
      Most allocators can do this lookup quickly, sometimes by placing the size next to the allocation or by encoding it into the returned pointer.
      - lifthrasiir 3y ago
        > by encoding it into the returned pointer More accurately speaking though, this information is not directly available from the pointer (unless we have a universal pointer tagging support today...) and should be mapped via the allocator internal data structure. This is what o11c referred by "arenas/buckets/whatever", and having a size information does simplify this process. The metadata around the allocation is comparably expensive especially for smaller allocations anyway, so modern allocators would have at least two classes of memory depending on the size. So even when the allocator doesn't make use of any other size information, it is possible that the size information can still be helpful.
        saagarjha 3y ago
        Having the size is definitely useful, because you can skip the metadata. But since needing this information in some form or the other is very important it is generally easy to derive-no walks or anything, because that would be slow.
        jaywee 3y ago
        It can be - the allocator just needs to mmap() different bucket pools to different base addresses.
- hollimolli 3y ago
  What's wrong with the one from glib?
  - unwind 3y ago
    Please note that "glibc" is the GNU C library, which is highly distinct from "glib" which is the general-purpose utility library underlying GTK and many other GNOME-adjacent technologies.
    - hollimolli 3y ago
      Thanks, man; that was just a typo; still interested in the answer.
charcircuit 3y ago
No mention of just having the caller do allocation?
- ooterness 3y ago
  "Just"
- Someone 3y ago
  That isn’t efficient in cases where the caller cannot know the size to allocate up front. For example: To use sprintf, you’d have to guess at the buffer size to pass in, or suffer a buffer overflow. snprintf is a bit better in that you can recover from passing a buffer that’s too small, but still either requires you to be generous in sizing the buffer, or accept that you often call snprintf twice, doing double work. The way around that is to pass a pointer to an allocation routine, but that’s a simple form of the allocator interface that this article favors.
  - charcircuit 3y ago
    >That isn’t efficient in cases where the caller cannot know the size to allocate up front This can typically be avoided though. With your sprintf example you could have one function that does the first half that calculates the size and then a second function that does the second half that actually copies into the destination buffer. Alternatively if you want to use realloc you could have a function like snprintf which allows resuming from where it ran out of space.
    - lifthrasiir 3y ago
      This strategy, while is worth mentioning as another separate post, can only be applied to simple interfaces. A whole API can be much larger and can't avoid allocations inside. There are some cases where the whole API was carefully designed to avoid such allocations, but it is difficult and not always suitable for users.
    - IAmLiterallyAB 3y ago
      For the first idea: Yes, but both of those would have to interpret the format string and determine the character lengths of the arguments which is duplicated work. I'd imagine its a large portion of the work. I'm not convinced its any more efficient than snprintf. The second idea is neat though... it could return an extra argument which is a pointer to the first part of the format string that wasn't printed
deleted 3y ago
[deleted]
habibur 3y ago
The hint in OP's last line, when you are passing around function pointers to allocators, you just need only one standard function interface. allocate(void\* ptr, size_t size); ptr == NULL : alloc() size == 0 : free() both ptr and size sent : realloc() That way it's simpler on the API stage. I prefer to keep it like that in my code.
- lifthrasiir 3y ago
  Plus a context pointer and old size, as the OP pointed out.
- o11c 3y ago
  A good API can use only a single ABI-level function, but it needs more parameters than that. I imagine 4 arguments, at least 2 of which are themselves composite: auto utopia_alloc(Allocation, AlignAndSkew, Size, Flags) -> Allocation; That said, while "one function" makes interposing easy, it does mean significant branching cost compared to single functions. There's probably a way to get the best of both worlds (support several functions in the ABI, but forward them all to `utopia_alloc` if interposed). more details at https://gist.github.com/o11c/6b08643335388bbab0228db763f99219#file-memory-allocation-api-md https://gist.github.com/o11c/6b08643335388bbab0228db763f9921... Aside: I really hate how the nullprogram site linked seems allergic to type-safety.
  - lifthrasiir 3y ago
    Oh that is indeed a good list, you should submit that gist independently. That said, I believe alignments should be a suggestion and not a mandatory request, mainly because the library can fix a bad alignment by overallocation. Charles Bloom has suggested a similar thing in the past [1]. Out of possible flags the zeroing flag is probably the most used and possibly only flag needed for library uses; others are also important but only a small number of libraries will ever want them. Again, a failure to do so should ideally be somehow detected and fixed, but that detection can't be actually checking for non-zeros, so the provided function should somehow return whether the memory was actually zeroed or not. (I also share the same concern about the site, by the way.) [1] https://cbloomrants.blogspot.com/2015/09/library-writing-realizations.html https://cbloomrants.blogspot.com/2015/09/library-writing-rea... (specifically the "Simplicity is better" point)
hayley-patton 3y ago
> The standard library allocator keeps its state in global variables. This makes for a simple interface, but comes with significant performance and complexity costs Thread local allocation buffers?
- MereInterest 3y ago
  Unfortunately, because a buffer may be allocated in one thread but freed in another, you can't have purely thread-local state for the allocator.
  - hayley-patton 3y ago
    snmalloc batches up cross-thread frees, though generally any thread-local stuff is better than none.
    - kragen 3y ago
      how simple can that be and still get reasonable scaling?
      - masklinn 3y ago
        Probably depends on your work load. If you assume there’s almost no crosstalk, you can likely get away with a thread-id and an optimistic mutex per pool: the mutex will only contend if one thread tries to (de)alloc while an other thread has a cross-thread free running. If you assume there will be more contention than that, then scaling up complexity might be a good idea e.g. lock per size class / arena, or push cross-thread frees to a queue and have the owning thread check the queue once in a while. You can then make that queue lock-free or even wait-free if that is better for your workload / issues.
      - hayley-patton 3y ago
        Looks like it's 10.7 kLOC whereas mimalloc is 8.8 kLOC, so it's not much more complex at that...amount of engineering, I guess. Also spotted that the mimalloc README says > Free-ing from another thread can now be a single CAS without needing sophisticated coordination between threads which may not be the worst thing in the world; depends on what your app does.
deleted 3y ago
[deleted]
hgs3 3y ago
Good article. The caller can also pass arguments hinting whether the requested allocation will be long or short lived, zero allocated, etc... You can also go beyond the realloc/free idiom and into specialized interfaces, like a push/pop stack allocator.
matheusmoreira 3y ago
This is great!! I learned a lot from this post. I'm working on a freestanding C project and had to write my own allocator. I ended up replicating the libc design with a doubly linked list of sized blocks which get merged with free neighbors when deallocated. Never occurred to me to pass the object sizes to the deallocation and reallocation functions, even though such sizes are passed around everywhere in other parts of the code. Redesigning the whole thing would be a big effort but it might be worth it.
kccqzy 3y ago
> When an application frees an object it always has the original, requested allocation size on hand. After all, it’s a necessary condition to use the object correctly. This is quite untrue in real-world C codebases unless you have a lot of discipline. I know from reading a previous article (https://nullprogram.com/blog/2023/10/08/ https://nullprogram.com/blog/2023/10/08/) by this author that they hate null-terminated strings. But in your typical C code, you often allocate a bunch of memory to be used as a null-terminated string, return it or pass it to another function transferring ownership, and expect a different function to free() it. The length of the string is not necessarily the allocation size! The code could have allocated some predetermined max size for the buffer, build up the string gradually, and then add a null terminator. Thus, the function doing the free() can't pass the right size.
- kragen 3y ago
  if i have a function foo which calls functions bar and baz to build up a dynamically allocated string (using a custom allocator), then calls function quux to transfer ownership of the string, foo needs to store the information about how big the allocation currently is, and how to allocate more of it, in a place where functions bar and baz can access it. if it doesn't do that, bar or baz can easily overflow the buffer because they don't know how big it is. this is a particular case of 'having the requested allocation size on hand is a necessary condition to use the object correctly' but if foo is passing this data structure to bar and baz, it can pass it to quux too, so the problem as you described it just doesn't exist (unless your code is only working by the merest of chances and will have some cves later this year the first time some competent programmers look at it) 'bar or baz can easily overflow the buffer because they don't know how big it is' is a particular case of 'having the requested allocation size on hand is a necessary condition to use the object correctly'
  - comex 3y ago
    There are many reasons it might be inconvenient for foo to pass that data to quux. Perhaps it’s actually quux that called foo rather than the other way around (in other words, foo is passing ownership through its return value rather than through a function argument), in which case C makes it easier to return one value than two. Or perhaps there’s just a lot of existing logic that passes owned strings around without an accompanying size parameter, which is perfectly safe to do if you’re not planning to ever mutate them. Of course you could easily design your codebase to not have that issue, if you’re writing it from scratch. But that’s not the question.
Woodi 3y ago
Umm, C looks like nice language... Then maybe that so-so-problematic stringZ are too just bad convention ? Maybe put some intern to try other implementation ? ;)
- Woodi 3y ago
  You seriously think libc shouldn't or can't be redone ?? Without \0's this time.
Cloudef 3y ago
The fact that zig's standard library design (and general code guidelines) makes you always carry allocator with you, makes it very easy to manage memory overall. Most of time I set up arena allocator and then I don't even have to care about clean up unless it's something holding a OS resource.
- laserbeam 3y ago
  The article presents essentially the same view, for a language which doesn't have that convention, and doesn't have slices (pointers that also contain size information). Zig allocators check all three requirements illustrated here. As do most modern allocator interfaces.
- eqvinox 3y ago
  Carrying the allocator everywhere does introduce a new class of bugs — if you call into a library at a later point in time to interact with something that was previously allocated, but you pass a different allocator this time… how exactly does that work? (As opposed to: set up the allocator once, in an initialization call.)
  - flohofwoe 3y ago
    Zig stdlib "objects" like dynamic containers indeed usually only take the allocator during initialization and then store it in the instance. E.g. var list = ArrayList(u8).init(test_allocator); defer list.deinit(); try list.append('H'); try list.append('e'); ...
    - Cloudef 3y ago
      There are also often Unmanaged variants where you pass allocator to every method. In these scenarios you have to make sure you use the same allocator though. Unmanaged can be useful for short lived allocations or type that combines many standard containers, saving memory.
el_pollo_diablo 3y ago
Unless all objects allocated by the library have one of the fundamental alignment requirements, I'd add a fourth item to the checklist: 4. All functions take the alignment requirement as a parameter. The alignment requirement must be a power of 2. The reallocation and deallocation functions must be passed the same alignment requirement value as was passed to the allocation function when the block was first allocated. A common motivation for rolling out your custom allocator is dealing with extended alignment requirements. This should be reflected in the allocator's API.
- eqvinox 3y ago
  Alternatively, "the allocator should have an equivalent of posix_memalign()". Also the default alignment should be well documented, since 99% of calls won't care about a specific alignment, and then you start hunting why your math routines are slow when the CPU is doing unaligned SIMD loads…
  - el_pollo_diablo 3y ago
    C11 has aligned_alloc, which is more standard than posix_memalign, but there is no standard "aligned_realloc". There is no default alignment if all the functions of the allocator take it as a parameter, but it is reasonable for an allocator implementation to be optimized for a particular alignment requirement such as _Alignof(max_align_t).
    - eqvinox 3y ago
      > C11 has aligned_alloc, which is more standard than posix_memalign, I don't have data on this but I feel that posix_memalign might be more widely supported than aligned_alloc. Then again C11 is 12 years old now so hopefully this changed. > There is no default alignment if all the functions of the allocator take it as a parameter, I would assume you can pass 0 as the requested alignment, which makes the allocator use some default. If the allocator always requires an alignment value, it becomes a serious pain to go through all allocations and figure out a reasonable alignment value. Especially since in most cases you really don't care.
el_pollo_diablo 3y ago
If the library reallocates non-trivial objects, it may need a more sophisticated reallocation function, that does not simply bitwise copy a block to its new location. Some additional work may be needed (e.g. pointer fixup). The reallocation function could take a "move constructor" callback as parameter.
- eqvinox 3y ago
  I don't think I have ever seen something like this in an allocator API, do you have an example?
  - el_pollo_diablo 3y ago
    I don't think I have seen it in publicly available allocators either, but I once implemented it in a custom one. I suppose that this design is not very popular because it is quite fragile: you end up running arbitrary code (the move constructor) in the middle of an allocation routine, when some of the heap's invariants have not yet been restored. Consequently, you typically require that the move constructor not recursively call the allocator, which is a reasonable limitation. Alternatively, the allocator could treat reallocation as a multi-step process ( a) reserve new space, b) move data, c) free old space), with enough state tracking to allow a) and c) to be different calls to the allocator, so that b) could be performed by the caller. There is no perfect solution to this problem. I suppose that's why C++ does not have a standard reallocation counterpart to new/delete/new[]/delete[].
eqvinox 3y ago
5. The allocator must be able to mesh into debugging tools like ASAN and valgrind. Not having these tools available is a serious kneecapping yourself. C is bad enough with all the tooling you can get… I've only dealt with valgrind so far, integrating with it is pretty easy (a line or two of annotations in each function.) It just needs to be done. (To be fair this is a requirement on the allocator, not on the API a library exposes to throw in a custom allocator.)
zackoverflow 3y ago
> Note that the context pointer came after the “standard” arguments. All things being equal, “extra” arguments should go after standard ones. But don’t sweat it! In the most common calling conventions this allows stub implementations to be merely an unconditional jump. I didn't know this. Does this optimization have a name? Where can I read more about it?
- Retr0id 3y ago
  I'm not sure if there's a particular name for it, but you could consider it to be a special case of a tail call optimisation https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call
- jonathrg 3y ago
  This is because of the calling convention / ABI If you write void free_with_extra_args(int *a, int *b) { free(a); } then *a is in already in the correct slot (the RDI register) for the first argument when free_with_extra_args is being called. Whatever is put into *b is never touched. If you compile this with gcc -O2 you get free_with_extra_args: jmp free If you make the function call free(b) instead, you'll have to move b into the right place before calling free: free_with_extra_args: mov rdi, rsi jmp free This is on x86-64 as summarized here https://en.wikipedia.org/wiki/X86_calling_conventions#System_V_AMD64_ABI https://en.wikipedia.org/wiki/X86_calling_conventions#System... Wikipedia also has a nice summary of calling conventions on other platforms like ARM. All modern calling conventions are similar: pass the first args in registers and then use the stack as needed https://en.wikipedia.org/wiki/Calling_convention https://en.wikipedia.org/wiki/Calling_convention
  - flohofwoe 3y ago
    That's only one half of it though, the other interesting part is the jmp (instead of call) to hand over control to a subroutine without pushing a new return address to the stack (since there's no code after the function call, and the calling function doesn't require its own stack frame).
kazinator 3y ago
> When an application frees an object it always has the original, requested allocation size on hand. This is false in general. If it's true in your library that you have this old size on hand, then design the allocator callbacks with old-size arguments in free and realloc. If it's not convenient, then don't design those arguments in. Most of the time, the allocator implementation will the be the default one via malloc and free, where the size is not required, so you're making the caller calculate or retrieve a value that is thrown away before the allocator is called. There are situations in which a program would have to calculate the size in order to recover it. A trivial example is when a string is duplicated (as with the POSIX strdup function). If the free function required the original request size, we would have to free the string using free(str, strlen(str) + 1) rather than just free(str). Another example is when we have a header structure followed by a flexible array member. We can't just free(obj) but something like free(obj, offsetof(obj_t, array) + sizeof(obj->array[0]) * obj->nelems). The allocated size could be stored in an extra field, but that's not something required when the allocator is malloc/free.

181 points by nalgeon 3y ago

I wonder how many security-critical memory vulnerabilities would've been avoided over the decades if glibc had been designed with this API instead of the one that became the de-facto standard.

Someone 3y ago
Or introduced. I would think that trusting the (possibly compromised) caller to pass the correct size of a to be freed or resized object opens up new possibilities for security vulnerabilities.
- o11c 3y ago
  Note that libc-style `free` often has to do work to walk through all possible arenas/buckets/whatever to see which one contains the given pointer. If given a size (even just a hint) it can do a much shorter walk without reducing security.
  - tom_ 3y ago
    "Even just a hint" doesn't deserve to be squirreled away in a mere paranthetical. It's what distinguishes some bullshit (the article's suggestion, whereby the allocator carefully checks that you supplied the right value that it already knows and barfs if not) from the actually potentially useful improvement to the API that you suggest. The code that frees very often does not know how much was allocated.
    - lifthrasiir 3y ago
      An allocator that fully trusts the size provided to `free` is hugely unsafe when the size turns out to be incorrect. As an extreme example, the allocator may know that every 4-byte allocation is put into the arena that is aligned to 0x1000-byte block, so it may jump straight into the arena header which won't be there if the size was incorrect. So a real-life allocator is likely to do some checking even when the size is provided, but that checking can be much more simplified in that case.
  - saagarjha 3y ago
    Most allocators can do this lookup quickly, sometimes by placing the size next to the allocation or by encoding it into the returned pointer.
    - lifthrasiir 3y ago
      > by encoding it into the returned pointer More accurately speaking though, this information is not directly available from the pointer (unless we have a universal pointer tagging support today...) and should be mapped via the allocator internal data structure. This is what o11c referred by "arenas/buckets/whatever", and having a size information does simplify this process. The metadata around the allocation is comparably expensive especially for smaller allocations anyway, so modern allocators would have at least two classes of memory depending on the size. So even when the allocator doesn't make use of any other size information, it is possible that the size information can still be helpful.
      - saagarjha 3y ago
        Having the size is definitely useful, because you can skip the metadata. But since needing this information in some form or the other is very important it is generally easy to derive-no walks or anything, because that would be slow.
      - jaywee 3y ago
        It can be - the allocator just needs to mmap() different bucket pools to different base addresses.
hollimolli 3y ago
What's wrong with the one from glib?
- unwind 3y ago
  Please note that "glibc" is the GNU C library, which is highly distinct from "glib" which is the general-purpose utility library underlying GTK and many other GNOME-adjacent technologies.
  - hollimolli 3y ago
    Thanks, man; that was just a typo; still interested in the answer.

charcircuit 3y ago

No mention of just having the caller do allocation?

ooterness 3y ago
"Just"
Someone 3y ago
That isn’t efficient in cases where the caller cannot know the size to allocate up front. For example: To use sprintf, you’d have to guess at the buffer size to pass in, or suffer a buffer overflow. snprintf is a bit better in that you can recover from passing a buffer that’s too small, but still either requires you to be generous in sizing the buffer, or accept that you often call snprintf twice, doing double work. The way around that is to pass a pointer to an allocation routine, but that’s a simple form of the allocator interface that this article favors.
- charcircuit 3y ago
  >That isn’t efficient in cases where the caller cannot know the size to allocate up front This can typically be avoided though. With your sprintf example you could have one function that does the first half that calculates the size and then a second function that does the second half that actually copies into the destination buffer. Alternatively if you want to use realloc you could have a function like snprintf which allows resuming from where it ran out of space.
  - lifthrasiir 3y ago
    This strategy, while is worth mentioning as another separate post, can only be applied to simple interfaces. A whole API can be much larger and can't avoid allocations inside. There are some cases where the whole API was carefully designed to avoid such allocations, but it is difficult and not always suitable for users.
  - IAmLiterallyAB 3y ago
    For the first idea: Yes, but both of those would have to interpret the format string and determine the character lengths of the arguments which is duplicated work. I'd imagine its a large portion of the work. I'm not convinced its any more efficient than snprintf. The second idea is neat though... it could return an extra argument which is a pointer to the first part of the format string that wasn't printed

deleted 3y ago

[deleted]

habibur 3y ago

The hint in OP's last line, when you are passing around function pointers to allocators, you just need only one standard function interface. allocate(void\* ptr, size_t size); ptr == NULL : alloc() size == 0 : free() both ptr and size sent : realloc() That way it's simpler on the API stage. I prefer to keep it like that in my code.

lifthrasiir 3y ago
Plus a context pointer and old size, as the OP pointed out.
o11c 3y ago
A good API can use only a single ABI-level function, but it needs more parameters than that. I imagine 4 arguments, at least 2 of which are themselves composite: auto utopia_alloc(Allocation, AlignAndSkew, Size, Flags) -> Allocation; That said, while "one function" makes interposing easy, it does mean significant branching cost compared to single functions. There's probably a way to get the best of both worlds (support several functions in the ABI, but forward them all to `utopia_alloc` if interposed). more details at https://gist.github.com/o11c/6b08643335388bbab0228db763f99219#file-memory-allocation-api-md https://gist.github.com/o11c/6b08643335388bbab0228db763f9921... Aside: I really hate how the nullprogram site linked seems allergic to type-safety.
- lifthrasiir 3y ago
  Oh that is indeed a good list, you should submit that gist independently. That said, I believe alignments should be a suggestion and not a mandatory request, mainly because the library can fix a bad alignment by overallocation. Charles Bloom has suggested a similar thing in the past [1]. Out of possible flags the zeroing flag is probably the most used and possibly only flag needed for library uses; others are also important but only a small number of libraries will ever want them. Again, a failure to do so should ideally be somehow detected and fixed, but that detection can't be actually checking for non-zeros, so the provided function should somehow return whether the memory was actually zeroed or not. (I also share the same concern about the site, by the way.) [1] https://cbloomrants.blogspot.com/2015/09/library-writing-realizations.html https://cbloomrants.blogspot.com/2015/09/library-writing-rea... (specifically the "Simplicity is better" point)

hayley-patton 3y ago

> The standard library allocator keeps its state in global variables. This makes for a simple interface, but comes with significant performance and complexity costs Thread local allocation buffers?

MereInterest 3y ago
Unfortunately, because a buffer may be allocated in one thread but freed in another, you can't have purely thread-local state for the allocator.
- hayley-patton 3y ago
  snmalloc batches up cross-thread frees, though generally any thread-local stuff is better than none.
  - kragen 3y ago
    how simple can that be and still get reasonable scaling?
    - masklinn 3y ago
      Probably depends on your work load. If you assume there’s almost no crosstalk, you can likely get away with a thread-id and an optimistic mutex per pool: the mutex will only contend if one thread tries to (de)alloc while an other thread has a cross-thread free running. If you assume there will be more contention than that, then scaling up complexity might be a good idea e.g. lock per size class / arena, or push cross-thread frees to a queue and have the owning thread check the queue once in a while. You can then make that queue lock-free or even wait-free if that is better for your workload / issues.
    - hayley-patton 3y ago
      Looks like it's 10.7 kLOC whereas mimalloc is 8.8 kLOC, so it's not much more complex at that...amount of engineering, I guess. Also spotted that the mimalloc README says > Free-ing from another thread can now be a single CAS without needing sophisticated coordination between threads which may not be the worst thing in the world; depends on what your app does.

deleted 3y ago

[deleted]

hgs3 3y ago

Good article. The caller can also pass arguments hinting whether the requested allocation will be long or short lived, zero allocated, etc... You can also go beyond the realloc/free idiom and into specialized interfaces, like a push/pop stack allocator.

matheusmoreira 3y ago

This is great!! I learned a lot from this post. I'm working on a freestanding C project and had to write my own allocator. I ended up replicating the libc design with a doubly linked list of sized blocks which get merged with free neighbors when deallocated. Never occurred to me to pass the object sizes to the deallocation and reallocation functions, even though such sizes are passed around everywhere in other parts of the code. Redesigning the whole thing would be a big effort but it might be worth it.

kccqzy 3y ago

> When an application frees an object it always has the original, requested allocation size on hand. After all, it’s a necessary condition to use the object correctly. This is quite untrue in real-world C codebases unless you have a lot of discipline. I know from reading a previous article (https://nullprogram.com/blog/2023/10/08/ https://nullprogram.com/blog/2023/10/08/) by this author that they hate null-terminated strings. But in your typical C code, you often allocate a bunch of memory to be used as a null-terminated string, return it or pass it to another function transferring ownership, and expect a different function to free() it. The length of the string is not necessarily the allocation size! The code could have allocated some predetermined max size for the buffer, build up the string gradually, and then add a null terminator. Thus, the function doing the free() can't pass the right size.

kragen 3y ago
if i have a function foo which calls functions bar and baz to build up a dynamically allocated string (using a custom allocator), then calls function quux to transfer ownership of the string, foo needs to store the information about how big the allocation currently is, and how to allocate more of it, in a place where functions bar and baz can access it. if it doesn't do that, bar or baz can easily overflow the buffer because they don't know how big it is. this is a particular case of 'having the requested allocation size on hand is a necessary condition to use the object correctly' but if foo is passing this data structure to bar and baz, it can pass it to quux too, so the problem as you described it just doesn't exist (unless your code is only working by the merest of chances and will have some cves later this year the first time some competent programmers look at it) 'bar or baz can easily overflow the buffer because they don't know how big it is' is a particular case of 'having the requested allocation size on hand is a necessary condition to use the object correctly'
- comex 3y ago
  There are many reasons it might be inconvenient for foo to pass that data to quux. Perhaps it’s actually quux that called foo rather than the other way around (in other words, foo is passing ownership through its return value rather than through a function argument), in which case C makes it easier to return one value than two. Or perhaps there’s just a lot of existing logic that passes owned strings around without an accompanying size parameter, which is perfectly safe to do if you’re not planning to ever mutate them. Of course you could easily design your codebase to not have that issue, if you’re writing it from scratch. But that’s not the question.

Woodi 3y ago

Umm, C looks like nice language... Then maybe that so-so-problematic stringZ are too just bad convention ? Maybe put some intern to try other implementation ? ;)

Woodi 3y ago
You seriously think libc shouldn't or can't be redone ?? Without \0's this time.

Cloudef 3y ago

The fact that zig's standard library design (and general code guidelines) makes you always carry allocator with you, makes it very easy to manage memory overall. Most of time I set up arena allocator and then I don't even have to care about clean up unless it's something holding a OS resource.

laserbeam 3y ago
The article presents essentially the same view, for a language which doesn't have that convention, and doesn't have slices (pointers that also contain size information). Zig allocators check all three requirements illustrated here. As do most modern allocator interfaces.
eqvinox 3y ago
Carrying the allocator everywhere does introduce a new class of bugs — if you call into a library at a later point in time to interact with something that was previously allocated, but you pass a different allocator this time… how exactly does that work? (As opposed to: set up the allocator once, in an initialization call.)
- flohofwoe 3y ago
  Zig stdlib "objects" like dynamic containers indeed usually only take the allocator during initialization and then store it in the instance. E.g. var list = ArrayList(u8).init(test_allocator); defer list.deinit(); try list.append('H'); try list.append('e'); ...
  - Cloudef 3y ago
    There are also often Unmanaged variants where you pass allocator to every method. In these scenarios you have to make sure you use the same allocator though. Unmanaged can be useful for short lived allocations or type that combines many standard containers, saving memory.

el_pollo_diablo 3y ago

Unless all objects allocated by the library have one of the fundamental alignment requirements, I'd add a fourth item to the checklist: 4. All functions take the alignment requirement as a parameter. The alignment requirement must be a power of 2. The reallocation and deallocation functions must be passed the same alignment requirement value as was passed to the allocation function when the block was first allocated. A common motivation for rolling out your custom allocator is dealing with extended alignment requirements. This should be reflected in the allocator's API.

eqvinox 3y ago
Alternatively, "the allocator should have an equivalent of posix_memalign()". Also the default alignment should be well documented, since 99% of calls won't care about a specific alignment, and then you start hunting why your math routines are slow when the CPU is doing unaligned SIMD loads…
- el_pollo_diablo 3y ago
  C11 has aligned_alloc, which is more standard than posix_memalign, but there is no standard "aligned_realloc". There is no default alignment if all the functions of the allocator take it as a parameter, but it is reasonable for an allocator implementation to be optimized for a particular alignment requirement such as _Alignof(max_align_t).
  - eqvinox 3y ago
    > C11 has aligned_alloc, which is more standard than posix_memalign, I don't have data on this but I feel that posix_memalign might be more widely supported than aligned_alloc. Then again C11 is 12 years old now so hopefully this changed. > There is no default alignment if all the functions of the allocator take it as a parameter, I would assume you can pass 0 as the requested alignment, which makes the allocator use some default. If the allocator always requires an alignment value, it becomes a serious pain to go through all allocations and figure out a reasonable alignment value. Especially since in most cases you really don't care.

el_pollo_diablo 3y ago

If the library reallocates non-trivial objects, it may need a more sophisticated reallocation function, that does not simply bitwise copy a block to its new location. Some additional work may be needed (e.g. pointer fixup). The reallocation function could take a "move constructor" callback as parameter.

eqvinox 3y ago
I don't think I have ever seen something like this in an allocator API, do you have an example?
- el_pollo_diablo 3y ago
  I don't think I have seen it in publicly available allocators either, but I once implemented it in a custom one. I suppose that this design is not very popular because it is quite fragile: you end up running arbitrary code (the move constructor) in the middle of an allocation routine, when some of the heap's invariants have not yet been restored. Consequently, you typically require that the move constructor not recursively call the allocator, which is a reasonable limitation. Alternatively, the allocator could treat reallocation as a multi-step process ( a) reserve new space, b) move data, c) free old space), with enough state tracking to allow a) and c) to be different calls to the allocator, so that b) could be performed by the caller. There is no perfect solution to this problem. I suppose that's why C++ does not have a standard reallocation counterpart to new/delete/new[]/delete[].

eqvinox 3y ago

5. The allocator must be able to mesh into debugging tools like ASAN and valgrind. Not having these tools available is a serious kneecapping yourself. C is bad enough with all the tooling you can get… I've only dealt with valgrind so far, integrating with it is pretty easy (a line or two of annotations in each function.) It just needs to be done. (To be fair this is a requirement on the allocator, not on the API a library exposes to throw in a custom allocator.)

zackoverflow 3y ago

> Note that the context pointer came after the “standard” arguments. All things being equal, “extra” arguments should go after standard ones. But don’t sweat it! In the most common calling conventions this allows stub implementations to be merely an unconditional jump. I didn't know this. Does this optimization have a name? Where can I read more about it?

Retr0id 3y ago
I'm not sure if there's a particular name for it, but you could consider it to be a special case of a tail call optimisation https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call
jonathrg 3y ago
This is because of the calling convention / ABI If you write void free_with_extra_args(int *a, int *b) { free(a); } then *a is in already in the correct slot (the RDI register) for the first argument when free_with_extra_args is being called. Whatever is put into *b is never touched. If you compile this with gcc -O2 you get free_with_extra_args: jmp free If you make the function call free(b) instead, you'll have to move b into the right place before calling free: free_with_extra_args: mov rdi, rsi jmp free This is on x86-64 as summarized here https://en.wikipedia.org/wiki/X86_calling_conventions#System_V_AMD64_ABI https://en.wikipedia.org/wiki/X86_calling_conventions#System... Wikipedia also has a nice summary of calling conventions on other platforms like ARM. All modern calling conventions are similar: pass the first args in registers and then use the stack as needed https://en.wikipedia.org/wiki/Calling_convention https://en.wikipedia.org/wiki/Calling_convention
- flohofwoe 3y ago
  That's only one half of it though, the other interesting part is the jmp (instead of call) to hand over control to a subroutine without pushing a new return address to the stack (since there's no code after the function call, and the calling function doesn't require its own stack frame).

kazinator 3y ago

> When an application frees an object it always has the original, requested allocation size on hand. This is false in general. If it's true in your library that you have this old size on hand, then design the allocator callbacks with old-size arguments in free and realloc. If it's not convenient, then don't design those arguments in. Most of the time, the allocator implementation will the be the default one via malloc and free, where the size is not required, so you're making the caller calculate or retrieve a value that is thrown away before the allocator is called. There are situations in which a program would have to calculate the size in order to recover it. A trivial example is when a string is duplicated (as with the POSIX strdup function). If the free function required the original request size, we would have to free the string using free(str, strlen(str) + 1) rather than just free(str). Another example is when we have a header structure followed by a flexible array member. We can't just free(obj) but something like free(obj, offsetof(obj_t, array) + sizeof(obj->array[0]) * obj->nelems). The allocated size could be stored in an extra field, but that's not something required when the allocator is malloc/free.