News for hackers. Stuff that matters.
Re:Arena Allocator Tips and Tricks by matheusmoreira on Wednesday September 27, 2023 @04:30AM (#37671772)
Excellent article.

> While you could make a big, global char[] array to back your arena, it’s technically not permitted (strict aliasing).

Aren't char pointers/arrays allowed to alias everything?

I used that technique in my programming language and its allocator. It's freestanding so I couldn't use malloc. I had to get memory from somewhere so I just statically allocated a big array of bytes. It worked perfectly but I do disable strict aliasing as a matter of course since in systems programming there's aliasing everywhere.

Re:Arena Allocator Tips and Tricks by dellorter on Wednesday September 27, 2023 @04:38AM (#37671831)
If you overlay a struct in your buffer and derefrence a pointer to it you would be accessing something with a different type other than its declared type(char* as struct something *), so is strict aliasing violation

To do stay in the rules you could set up a void* to suitable region in a linkerscript

Re:Arena Allocator Tips and Tricks by matheusmoreira on Wednesday September 27, 2023 @06:07AM (#37672595)
Welp. Linus Torvalds was right about this stuff.

https://lwn.net/Articles/316126/

https://lkml.org/lkml/2003/2/26/158

Re:Arena Allocator Tips and Tricks by saagarjha on Wednesday September 27, 2023 @09:29AM (#37674374)
Wait until someone tells Linus about how processors do reordering.

(Yes, I know he understands it. Clearly he just refuses to accept that compilers can also reorder his code and he needs to accommodate that.)

Re:Arena Allocator Tips and Tricks by mtzet on Wednesday September 27, 2023 @09:48AM (#37674622)
Processors doing out-of-order execution doesn't change the semantics of the code. That's very different from the example where gcc just throws away the assignment.

The idea that he just needs to accommodate the compiler people is silly. Compilers exist to serve programmers, not the other way around. It's entirely reasonable to disagree with the compiler developers and use a flag to disable behaviour your don't want.

Re:Arena Allocator Tips and Tricks by saagarjha on Wednesday September 27, 2023 @08:06PM (#37683374)
It does when you have a weak memory model and multiple threads involved.
Re:Arena Allocator Tips and Tricks by gpderetta on Wednesday September 27, 2023 @11:26AM (#37676057)
In fairness, CPU reordering is does not visibly affect a thread view of their own loads and stores.
Re:Arena Allocator Tips and Tricks by matheusmoreira on Wednesday September 27, 2023 @08:14PM (#37683447)
> he needs to accommodate that

Clearly he doesn't. He just disabled harmful features and called it a day. Stuff like strict aliasing and undefined signed integer overflow apparently do nothing but serve as an excuse for the optimizer to screw up perfectly reasonable code.

https://cellperformance.beyond3d.com/articles/2006/06/unders...

https://stackoverflow.com/q/2958633/512904

Looks like this is a pretty good approach to fixing the C language. Take the nonsensical undefined stuff and tell the compiler to define it.

Looks like there is a may_alias type attribute to tell GCC that some types may alias:

https://gcc.gnu.org/onlinedocs/gcc/Common-Type-Attributes.ht...

I'm not sure if it's worth the effort though. Too much uncertainty.

Re:Arena Allocator Tips and Tricks by saagarjha on Wednesday September 27, 2023 @11:01PM (#37684678)
That's not how they work but I doubt getting into an argument with you about how undefined behavior works with someone who is dead-set on it being harmful is going to be productive.
Re:Arena Allocator Tips and Tricks by gpderetta on Wednesday September 27, 2023 @04:54AM (#37671966)
char can alias everything, i.e. you can deference a char pointer with impunity, even if the actual dynamic type[1] of an object is a different type. The reverse is not true: if the dynamic type of an object is char, just by using the alias rules, you can't deference it as an object of a different type.

In C++ you can just use placement new to change the dynamic type of (part of ) a char array (but beware of pointer provenance). In C is more complex: I don't claim to understand this fully, but my understanding is you can't change the type of a named object, but you should be able to change the type of anonymous memory (for example, what is allocated with malloc) by simply writing into it.

In practice at least GCC considers the full alias rules unimplementable and my understanding is that it uses a conservative model where every store can change the type of an object, and uses purely structural equivalence.

[1] of course most C implementations don't actually track dynamic types at runtime.

Re:Arena Allocator Tips and Tricks by matheusmoreira on Wednesday September 27, 2023 @05:56AM (#37672514)
> The reverse is not true: if the dynamic type of an object is char, just by using the alias rules, you can't deference it as an object of a different type.

A limitation like that simply makes no sense to me. Everything is a valid char array but I can't place structs on top of one? Oh well, nothing I can do about it. I'll just keep strict aliasing disabled. If we're writing C, it's because we want to do stuff like that without the compiler getting clever about it.

> you should be able to change the type of anonymous memory (for example, what is allocated with malloc) by simply writing into it

Well, in my case, I'm the one writing the malloc and the buffer is the anonymous memory. I remember months ago I scoured the GCC documentation for some kind of builtin that would allow me to mark the memory as such but there was nothing. I did add some malloc attributes to my allocation function just like TFA suggested but apparently its main purpose is to optimize based on aliasing nonsense which I disabled anyway.

Re:Arena Allocator Tips and Tricks by gpderetta on Wednesday September 27, 2023 @06:29AM (#37672728)
At some point you need to get the memory for your pool from somewhere, for example from malloc [1], hence you can safely set the type of the raw memory by writing into it. You can also change that type to some other type, by writing other stuff (so you can reuse the memory). You can also write metadata to it between uses. What you cannot do is having overlapping lifetimes for different types.

Making sure that you respect all the underspecified, obscure, and often contradicting rules is not easy, so if you prefer to disable strict-alias, you have my sympathy. For the most part is useful for high performance numerical code, and less advantageous for typical pointer chasing stuff.

From the practical point of view, the safest way to implement a custom allocator is to make sure that the compiler can't see through it, so separate compilation and no LTO and/or launder your pointers through appropriate inline asm.

[1] but other 'anonymous' sources, like mmap, would also work in practice.

Re:Arena Allocator Tips and Tricks by matheusmoreira on Wednesday September 27, 2023 @06:44AM (#37672814)
> For the most part is useful for high performance numerical code, and less advantageous for typical pointer chasing stuff.

Yeah. I've read that the aliasing rules and features like restrict were introduced to C because Fortran had them.

> the safest way to implement a custom allocator is to make sure that the compiler can't see through it

Makes sense.

> launder your pointers through appropriate inline asm

This is a really neat trick indeed. I learned a lot today.

Re:Arena Allocator Tips and Tricks by LoganDark on Wednesday September 27, 2023 @06:13AM (#37672632)
> Everything is a valid char array but I can't place structs on top of one? Oh well, nothing I can do about it. I'll just keep strict aliasing disabled.

Well, yeah. Strict aliasing is less about the incidental values of memory addresses and more about the actual semantics of what you're doing. Where writing a struct into the middle of a char array makes no sense because you have no guarantee in the type system that the array is properly sized or aligned to contain that struct.

Re:Arena Allocator Tips and Tricks by matheusmoreira on Wednesday September 27, 2023 @06:29AM (#37672731)
The compiler knows the size of statically allocated buffers and can be told about alignments with:

  __attribute__((aligned(N)))
  __builtin_assume_aligned(P, N)
Is this information sufficient for correct code generation?
Re:Arena Allocator Tips and Tricks by LoganDark on Wednesday September 27, 2023 @09:24AM (#37674321)
No, because strict aliasing doesn't allow the compiler to magically decide that someplace you are writing happens to be in a statically allocated buffer. Strict aliasing says you have a pointer of some type and what you do with it has to agree with the type of that pointer. That's the "strict" in it.
Re:Arena Allocator Tips and Tricks by variadix on Thursday September 28, 2023 @11:29AM (#37691029)
I feel like there should be a builtin that takes a void* and returns a void* which basically marks the input as aliased by the returned pointer regardless of the TBAA rules.
Re:Arena Allocator Tips and Tricks by variadix on Thursday September 28, 2023 @09:40PM (#37698305)
Turns out there is! __builtin_launder seems mostly equivalent to what the author proposes but probably more reliable. Facebook’s folly library appears to use both, preferring the builtin.