5 ms·

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\

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)
  - o11c 3y ago
    Alignment has to be mandatory because otherwise `free` breaks.
    - lifthrasiir 3y ago
      I think you are imagining an aligned allocator out of an unaligned allocator, where the misalignment should be stored somewhere around the actual memory block, but if the main allocator itself is aware of aligned allocations it is not necessary. I can still imagine the case where allocation bins are structured by the allocation size and alignment size and an incorrect alignment will result in an incorrect bin, but such bins are only beneficial when the alignment itself is too large compared to allocation sizes, and I'm not sure who really wants them in the first place.
- eqvinox 3y ago
  > Aside: I really hate how the nullprogram site linked seems allergic to type-safety. +∞ to this. Considering the ecosystem limitations as they are, it's paramount to use every possible thing available to catch mistakes.
- vitaminCPP 3y ago
  > Aside: I really hate how the nullprogram site linked seems allergic to type-safety. Could you give us an example, I'm not sure what you refering to.
eru 3y ago
It's a pet peeve of mine that C people seem to think that 0 isn't a number. Or that 0 (or -1) mean infinity. (Like a timeout of 0 meaning an infinite timeout, instead of failing immediately.) I guess it's mostly a consequence of C having such poor support for data types. For a low-level allocator interface this might be an acceptable compromise, but C people also tend to use this kind of mangling when it's not warranted.
- saagarjha 3y ago
  An allocation of size zero cannot be used for anything useful.
  - lifthrasiir 3y ago
    The caller may still want to distingish a successful yet useless allocation from an unsuccessful allocation, which resulted in the current situation.
    - saagarjha 3y ago
      How would you tell?
    - Nevermark 3y ago
      Zero bytes are always allocatable. Unless you need zero byte (and other) pointers to be consistently unique. But that would mean allocating and deallocating some memory for zero byte requests, to provide unique addresses. Or some reserved memory address span, outside of available (real and virtual) RAM, for zero byte pointers.
      - lifthrasiir 3y ago
        > Unless you need zero byte (and other) pointers to be consistently unique. Yes, this was the problem. People had some different ideas for contracts that `malloc` etc. should guarantee---the most lax requirement would be a "usable" pointer on success, which does almost perfectly constrain non-zero cases but leaves lots of freedom for zero cases. At the opposite side there is a "unique non-NULL" pointer requirement, as you've said, which essentially makes `malloc(0)` almost same to `malloc(1)`. Rust also has this issue because its reference, a pointer after compilation, is expected to be non-null even for zero-sized types. Rust's rule is somewhat in between: any pointer should be non-null, but it doesn't have to be unique for zero-sized types. The canonical non-null pointer for such types (as returned by `NonNull::dangling`) is the smallest non-zero pointer that satisfies the alignment.
jstarks 3y ago
I can’t agree. Combining alloc and free into one API is a false economy. You’re not really going to save any significant amount of space, and at best you’ll have an extra predictable branch or two (but probably unpredictable, I’d guess). More importantly, it’s harder to interpret the calling code’s intent in the edge cases. What does alloc(NULL, 0) mean? Did the caller try to free a null pointer, or allocate a zero-byte object? With separate functions, you can support either or both or neither, but with the combined model the only safe thing is to support neither and panic, lest you interpret an alloc as a free or vice versa.
- laserbeam 3y ago
  Depends on your goals. Lua aimed to be an incredibly tiny language with a very low footprint. The wanted you to need to implement very few functions if you needed to integrate it in your codebase. It has very few data types and function calls for that purpose. The goals of lua may not align with the goals of most projects, but it does make sense to have a single allocator function there, the same way it makes sense to have a single array/set/hash table data type (what lua calls a Table).
- laserbeam 3y ago
  Alloc(null, 0) can be implementation defined. It could be a noop in release builds and a panic in debug builds. Just how certain allocators do extra work in debug builds to detect leaks anyway. Keep in mind this is an allocator interface. Behavior is supposed to change and the allocator maker has control over that. Likewise free() doesn't always actually release memory (arena allocators for example), and that's the whole point.
wolfspaw 3y ago
Really liked that single-alloc-function strategy. Minimalist and Elegant.
eqvinox 3y ago
Hard no. Because: $ git grep -P '(X[CM]ALLOC|XREALLOC|XSTRDUP)' | wc -l 1612 $ git grep -P XFREE | wc -l 2000 $ git grep -P XREALLOC | wc -l 51 alloc and free are the most common operations, and having them be their own thing makes it much easier to reason about the code. Folding them into a common function makes the code much harder to review and maintain, both for humans as well as for tools (e.g. coccinelle).

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)
- o11c 3y ago
  Alignment has to be mandatory because otherwise `free` breaks.
  - lifthrasiir 3y ago
    I think you are imagining an aligned allocator out of an unaligned allocator, where the misalignment should be stored somewhere around the actual memory block, but if the main allocator itself is aware of aligned allocations it is not necessary. I can still imagine the case where allocation bins are structured by the allocation size and alignment size and an incorrect alignment will result in an incorrect bin, but such bins are only beneficial when the alignment itself is too large compared to allocation sizes, and I'm not sure who really wants them in the first place.
eqvinox 3y ago
> Aside: I really hate how the nullprogram site linked seems allergic to type-safety. +∞ to this. Considering the ecosystem limitations as they are, it's paramount to use every possible thing available to catch mistakes.
vitaminCPP 3y ago
> Aside: I really hate how the nullprogram site linked seems allergic to type-safety. Could you give us an example, I'm not sure what you refering to.

eru 3y ago

It's a pet peeve of mine that C people seem to think that 0 isn't a number. Or that 0 (or -1) mean infinity. (Like a timeout of 0 meaning an infinite timeout, instead of failing immediately.) I guess it's mostly a consequence of C having such poor support for data types. For a low-level allocator interface this might be an acceptable compromise, but C people also tend to use this kind of mangling when it's not warranted.

saagarjha 3y ago
An allocation of size zero cannot be used for anything useful.
- lifthrasiir 3y ago
  The caller may still want to distingish a successful yet useless allocation from an unsuccessful allocation, which resulted in the current situation.
  - saagarjha 3y ago
    How would you tell?
  - Nevermark 3y ago
    Zero bytes are always allocatable. Unless you need zero byte (and other) pointers to be consistently unique. But that would mean allocating and deallocating some memory for zero byte requests, to provide unique addresses. Or some reserved memory address span, outside of available (real and virtual) RAM, for zero byte pointers.
    - lifthrasiir 3y ago
      > Unless you need zero byte (and other) pointers to be consistently unique. Yes, this was the problem. People had some different ideas for contracts that `malloc` etc. should guarantee---the most lax requirement would be a "usable" pointer on success, which does almost perfectly constrain non-zero cases but leaves lots of freedom for zero cases. At the opposite side there is a "unique non-NULL" pointer requirement, as you've said, which essentially makes `malloc(0)` almost same to `malloc(1)`. Rust also has this issue because its reference, a pointer after compilation, is expected to be non-null even for zero-sized types. Rust's rule is somewhat in between: any pointer should be non-null, but it doesn't have to be unique for zero-sized types. The canonical non-null pointer for such types (as returned by `NonNull::dangling`) is the smallest non-zero pointer that satisfies the alignment.

jstarks 3y ago

I can’t agree. Combining alloc and free into one API is a false economy. You’re not really going to save any significant amount of space, and at best you’ll have an extra predictable branch or two (but probably unpredictable, I’d guess). More importantly, it’s harder to interpret the calling code’s intent in the edge cases. What does alloc(NULL, 0) mean? Did the caller try to free a null pointer, or allocate a zero-byte object? With separate functions, you can support either or both or neither, but with the combined model the only safe thing is to support neither and panic, lest you interpret an alloc as a free or vice versa.

laserbeam 3y ago
Depends on your goals. Lua aimed to be an incredibly tiny language with a very low footprint. The wanted you to need to implement very few functions if you needed to integrate it in your codebase. It has very few data types and function calls for that purpose. The goals of lua may not align with the goals of most projects, but it does make sense to have a single allocator function there, the same way it makes sense to have a single array/set/hash table data type (what lua calls a Table).
laserbeam 3y ago
Alloc(null, 0) can be implementation defined. It could be a noop in release builds and a panic in debug builds. Just how certain allocators do extra work in debug builds to detect leaks anyway. Keep in mind this is an allocator interface. Behavior is supposed to change and the allocator maker has control over that. Likewise free() doesn't always actually release memory (arena allocators for example), and that's the whole point.

wolfspaw 3y ago

Really liked that single-alloc-function strategy. Minimalist and Elegant.

eqvinox 3y ago

Hard no. Because: $ git grep -P '(X[CM]ALLOC|XREALLOC|XSTRDUP)' | wc -l 1612 $ git grep -P XFREE | wc -l 2000 $ git grep -P XREALLOC | wc -l 51 alloc and free are the most common operations, and having them be their own thing makes it much easier to reason about the code. Folding them into a common function makes the code much harder to review and maintain, both for humans as well as for tools (e.g. coccinelle).