[RFC] A Framework for Allocator Partitioning Hints

[melver]

@waffles_the_dog

[..] if different TUs are seeing different sets of types I don’t know how you determine the number of partitions. [..] Similarly for the directly indexed partitions, without knowing ahead of time how many and which slots are used I’m not sure how that works?

The !alloc_partition_hint metadata carries the necessary information to deterministically calculate a partition ID, and currently that’s the type name (as string) and if it contains a pointer. Then with the type name, we just hash that, and as long as the hash function is stable, the result will always be the partition ID modulo max partitions.

Of course if a user does:

// foo.c
struct Something { int a; };
// bar.c
struct Something { std::string a; };

… in the same namespace, we consider it UB.

@waffles_the_dog

I think having a general interface to register replacement functions is the right approach?

There are 2 aspects, one is if the user wants to register some special replacement functions where some source code can’t be changed. That could be a separate file, the format could just be function:replacement:arg, but I’m not a big fan of custom file formats. I don’t think this is at all needed for the baseline initial version, and I’m weary of YAGNI, so I’d postpone that until after the initial version is landed.

Then there’s communicating replacements and the arg position from Clang to an LLVM IR pass, such as what you will need for TMO if you choose the IR pass based design. This needs to be part of the LLVM IR generated, and the canonical way to do this would be to design an MD node that the IR pass interprets to pick the replacement function and where the arg is placed. Currently AllocPartition knows about !alloc_partition_hint <type-as-str> <contains-bool>, but that can be extended with additional optional parameters (... <token> <token-pos>).

@waffles_the_dog

We could hypothetically have a pair of builtins: __builtin_infer_type_names(expr) and __builtin_infer_type_token(expr).

I prefer simplicity, and currently don’t see how I’d want to use such a builtin. I think existing facilities like typeof()/typeid()/decltype() likely cover uses where code can afford to use such builtins. The real value that the proposed features provide is transparency and some degree of type-introspection to construct a token to make allocation decisions. __builtin_infer_type_token could be useful, if anything, to get the inference logic sorted out.

But I think we really need to charter an incremental path, before designing new features, esp. to keep things managable and simple.

Planning - Given you’re currently investigating how to move TMO to an IR pass, I could imagine something like this to work out and provide a coherent overall feature (but not sure that’s what you were imagining):

1. I can rename AllocPartition to AllocToken (also shorter name, which I like). AllocToken will give us the shared LLVM IR infrastructure we need.
2. I introduce Clang -fsanitize=alloc-token which behaves more or less like the current prototype, and constructs a sensible “token ID” as a default token (currently: TypeHashPointerSplit).
3. With that baseline infrastructure, TMO can be built on top - you could figure out the extra MD info passed on via !alloc_token_hint (probably “semantic token + target fn + argpos”).
4. We can teach AllocToken about the more advanced !alloc_token_hint.
5. You introduce attribute typed_memory_operation (shorter: alloc_typed(F, N)?), and replace the less advanced type-inference logic with your more advanced one. Such functions will be passed the “semantic token”.
6. At this point AllocToken will take care of -fsanitize=alloc-token and the attribute – by design they will not conflict (the pass knows about both), as those with the attribute will use TMO semantics, and the rest may only be covered if -fsanitize=alloc-partition is enabled.
7. [Future] Other LLVM-based languages can insert the AllocToken pass into their pipeline.

Naming: As always a hard thing - I think “token” should capture most use cases (incl. e.g. per-allocation-site tokens etc.). typed_memory_operation → “memory operation” can also be understood as a “load”, “store”, etc. and is generally ambigious.
I’d propose something that mirrors alloc_size, e.g. alloc_typed.

Questions for TMO via IR-pass (should you decide to do so):

1. Does it have to work without additional compiler flags? If yes, we just need to unconditionally insert the IR pass. Performance-wise I’d prefer an explicit flag for more complex features, but we can probably make the pass return fast if we know the function has no TMO-attributed calls.

This plan could be executed incrementally and I also don’t think we’d need the __builtins, if you are comfortable with ripping out my type-inference code – if you upstream first, then I can rebase (but my reading was you need more time, and I don’t see a point in rushing if the incremental plan works).

Thoughts?