Hacker News Reader

Comment by habibur | Hacker News Reader

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.

View on HN

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/6b08643335388bbab0228db763f9921...

Aside: I really hate how the nullprogram site linked seems allergic to type-safety.

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-rea... (specifically the "Simplicity is better" point)

Alignment has to be mandatory because otherwise `free` breaks.

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.

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

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

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.

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

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.

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.

An allocation of size zero cannot be used for anything useful.

The caller may still want to distingish a successful yet useless allocation from an unsuccessful allocation, which resulted in the current situation.

How would you tell?

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.

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

You could definitely use it for something useful; you can't store anything through it, but if an allocator supports allocations of size 0 with the same semantics of non-zero allocations, you get a "unique" ptr from the allocator dynamically.

Anywhere you need a dynamic list identifier this would suit (yes, a counter could do this too, this would be effectively a globally unique token)

One example is a non-null sentinel/oracle allocation. Often you see this in lockless data structures where you don't want to do a null check.

It should still work. Just like adding 0 to a number should still work, or multiplying by 1. The computer should just happily do nothing.

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

It's not just C people :D - Zero may or may not be a natural number depending on who you ask, and negative numbers definitely are not.

And since in low-level programming, which is kind of C's kingdom, every bit might count and you'd rather use that useless sign bit for something else. -1 being particularly liked by compilers because it is "all bits set" in the dominant two's complement sign encoding, which sometimes allows optimization tricks.

> I guess it's mostly a consequence of C having such poor support for data types.

Technically nothing prevents anyone from returning a small two fields structure - one for a tag and one for the value - to have "tagged unions" or "optional types" almost like your favorite language. But in the eyes of a low-level C programmer, that's one field too much (omg that doesn't fit in a register, you will be held responsible for global warming if you publish this etc.).

So, it's not that we think that anything non-positive is not a "true number", it's more like we've been using these conventions sometimes since assembly programming days (OR AX,AX to test if register AX is zero in old x86 assembly, because the OR instruction sets the CPU's Z flag) in order to get maximum performance.

You are right about cramming things into bits. But it often makes code more complicated.

Eg if you have two operations you do one after another and they have time-outs of t1 and t2, then normally, you know that after t1+t2, either both will have succeeded, or they will have failed.

But that breaks down with the 'C-conventions' when either t1 or t2 equals 0. Thus you need extra logic to deal with these.

As an aside: OCaml uses tagged pointers to cram more information into machine words. That's an implementation technique, and (mostly) hidden from users of the language. (Apart from integers having 63 bits, instead of 64 bits size by default.) So that's an example where the language is 'clean', but the implementation is still efficient and uses all the low level tricks.

And my pet peeve is more that many people always do this trickery, even when not every bit counts.

> It's not just C people :D - Zero may or may not be a natural number depending on who you ask, and negative numbers definitely are not.

Yes, but I never mentioned any restriction to Natural numbers. Btw, in the context of computers 0 is definitely a number that comes natural, even if it's not a Natural number by some people's definition.

The number 0 is interesting in the sense that it is actually a comparatively late and abstract invention. The natural numbers are also mathematically defined as either including or excluding 0 depending on the author.

That said the issue is really in-band signaling. “I already have this data type which I don’t fully use, let’s use one of the unused values to represent something completely unrelated..”

Yes, in-band signalling is error-prone.

If you want to do it properly, you better have good language support for it. (Eg dependent types might help?)

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

Plus a context pointer and old size, as the OP pointed out.

Really liked that single-alloc-function strategy.

Minimalist and Elegant.

Reply on news.ycombinator.com