Both allocators and wrappers should have run-time identity

[stephenrkell]

Currently there is some confusion about what an "allocator" is, owing to the presence of struct allocator instances that actually cover more than one allocator, such as __generic_malloc_allocator. All these struct allocator objects are statically defined -- we never generate them. If we could generate these and related structures, we could maintain a richer run-time model of allocators, allocator wrappers and allocation call sites. This would be useful for automating some meta-level policy, such as deleting an allocation when it's no longer needed. Currently the per-allocator free call is too stupid to allow this, as it can't identify which is the right free function to call when there are many alternatives (in cases where freeing and finalisation are baked into the same operation, for example).

Currently, link-time code generation (using the macros in tools/stubgen.h) is used to wrap each allocator wrapper (yes, two levels of wrapping) and also to wrap any linked-in definitions of malloc (all in allocscompilerwrapper.py). All this is a big mess that needs rationalising.

• Each allocator instance should get its own struct allocator instance, which should be generated and linked into the object defining its "first" entry point (f.s.v.o. "first"... what I'm envisaging is rather like C++, where the translation unit defining the first virtual function is the one that gets the vtable).

• Consequently, we no longer have a ___generic_malloc_allocator -- rather, each instance of malloc should have its own struct allocator. For example, if we link an executable that defines malloc, we generate a fresh struct allocator including implementations of its operations (which can call into the indexing code currently used by __generic_malloc_allocator, but acting on a separate index instance, which will have to be declared and statically constructed, also in the generated code).

• At the same time as generating the struct allocator instance, we also link in any wrapper that are necessary to observe the allocator. For example, if we have a malloc definition, we link in wrappers that do the indexing. (See the mention of 'callee' wrappers in tools/stubgen.h and tools/allocscompilerwrapper.py.) This already happens, and probably needs to be maintained and generalised to other allocators besides malloc.

• The libc is handled slightly specially, since it's preload-interposable and we don't expect the libc to be liballocs-compiled. So we have a struct allocator instance called __libc_malloc_allocator which is static, rather like the current __generic_malloc_allocator. And the libc malloc does not have 'callee wrappers' -- we use the preload mechanism instead. Since malloc and libc are special, there is probably not much to change here.

• The proposed change assumes we have some way to identify when a link job contains an allocator definition. The simplest way is to match symbols by name -- e.g. we consider an allocator to be defined by a set of symbols such as {malloc, free, calloc, realloc}, and pick the first of these (malloc) as the one that triggers generation of the struct allocator instance. (The other may still require callee-side wrapping, though.) Optional symbols that map closely to one of the liballocs meta-operations, like malloc_usable_size, probably need to be recognised too. Currently, we effectively have hard-coded one such set of symbols.

• As well as allocators themselves, each declared allocator wrapper should also (somehow) have a run-time identity. We could perhaps define a simple structure, and generate these at the same time as we generate the struct allocator instances (at link time). Currently we don't know which allocator is wrapped by a given wrapper; we might want to infer this dynamically by observation, and fill it in.

• Similarly, allocator call sites should have a run-time identity. The new static metadata handling (when it's ready) will have a notion of call sites encompassing allocator calls, system calls and perhaps others. We may want to remember call chains; each node in a call chain, if it is a call from a particular site, should be able to link to the structure describing that site (e.g. the allocator wrapper call site's allocation type record) rather than just to the raw address.

[stephenrkell]

It may be possible to eliminate the wrapping of allocator wrappers, as discussed in #20 .

[stephenrkell]

Pithy summary of how malloc should be callee-instrumented: a global, preload-interposable malloc should not be callee-wrapped (because we will preload-interpose it to do the same thing). Others should be. Ditto for other malloc-family functions.

What about a malloc that has both global-interposable alias and another alias? We should callee-wrap the local alias. This will mean that the two are no longer aliased. That is fine.

I think all this should be driven from one big config file or very specialised/hackable script, rather than hard-coded logic buried somewhere in our Python compile/link-wrapper scripts as at present. Then, it can be given a clean semantics, and addition of custom allocators or allocator wrappers can be explained uniformly in terms of addition to that file/scripts.

[stephenrkell]

Another way to think about the 'config file' idea is to put the built-in allocators and LIBALLOCS_* environment variables on the same level.

Roughly the level at which this needs to work is the link map... from a pooled description of what needs callee-wrapping, we should be able to explain the difference between the actual link map (including stubs linked in) and the vanilla no-liballocs link map.

We can perhaps turn the env vars into a config file that is merged with the 'built-in' config, then use the config file to produce linker options. The logic for all this belongs in the gold plugin.

[stephenrkell]

What do we do when final-linking a DSO that contains a 'malloc'? It's preemptible but may or may not be the global malloc, so may or may not need the callee wrappers. Probably it's necessary to create a local alias, then ensure any locally-bound reference (maybe from protected visibility, maybe from -Bsymbolic) actually goes to the alias, which does get the callee wrapper. So the global 'malloc' (and friends) are not used internally by the object, and will only be used externally if it does indeed 'win' the contention for that global symbol.

[difcsi]

This is useful for lifetime policies as well.

Currently, a lifetime policy is tied to the life of an allocation. Whenever the allocation event occurs, it is necessary to attach at least one lifetime policy to the newly allocated chunk. Currently, this is the responsibility of the allocator or the wrapper. This is a bit error-prone and would ideally not be left to the client to do.

I think that ideally, at least one lifetime policy should be applied by virtue of the allocation itself. The question arises: which one? Within a language VM for example, VM internals would rely on the "default" manual lifetime policy, whilst objects allocated for use within the language might exclusively rely on the GC policy. As both of these events are presumably delegated to malloc and friends at some point, this required that an allocation wrappers have their own identity and can be distinguished at run-time. Each allocator can have a set of lifetime policies it applies to allocated chunks by default.

struct allocator {
    ...
    struct {
        void *call_size;
        unsigned initial_policies:4;
    } known_facades[]; // see docs for facade definition
   //it is the indexing code's responsibility to collect "seen" call sites? Maybe?
  // maybe it is also responsible for setting initial policies? 
  // if so, why not just require each wrapper to have specialised indexing code? Many wrappers share it
}

[stephenrkell]

We considered adding to struct allocator (or possibly an inheriting struct allocator_with_lifetimes)

struct
{
        void *call_site;
        unsigned initial_policies:4;
} *known_facades; // <--- this gets built how?
unsigned n_known_facades;  /* use realloc / qsort */

and/or

struct lifetime_policy *lifetime_policy_map[4];

How (and for what) would the above be used?

Maybe: the indexing code also is responsible for setting the initial policy bits?

Many wrappers/allocators share generic indexing code (e.g. generic_malloc), so and that code can maintain these extra fields. It's generated from macros in stubgen.h.

Then, we could simply provide a way for a facade wrapper to specialise the setting for the initial policy bits (e.g. CPython's facade over malloc)?

We declare facades and bona fide allocation functions using a mini-language:

LIBALLOCS_ALLOC_FNS="myalloc(Z)p"

and that language lets us associate free functions with their allocation functions:

LIBALLOCS_FREE_FNS="myfree(p)->mymalloc"

so maybe these languages could also specify the initial policies?

We also considered whether each free function is a distinct policy, i.e. "free with myfree". So LIBALLOCS_FREE_FNS="myfree(p)->mymalloc" is saying "there exists a manual policy 'free by calling myfree(p)', which works for p issued by mymalloc".

And we noted that "requesting to free" and "actually performing a free" are separate operations in our approach (even though in C they are both combined in a single free() call).

Does this align with the distinction of facade vs "proper free function" (base-level allocator operation)? i.e. a facade is requesting a free, the allocator operation performs it? Direct calls to free() are a degenerate case. Hmm. This does not feel right.

[stephenrkell]

I think refactoring the little language is a good idea. We have the idea of an allocation function group, within which the functions have different roles and may have different semantics. We currently specify the signature, but we could also specify what lifetime policies apply, which are proper allocation functions vs facades, etc. And there is also the question of which indexing to apply... currently we always do generic-malloc and there is a separate set of env vars, e.g. LIBALLOCS_SUBALLOC_FNS, for generic-small. That is not general enough.

It might be best to wait until we have eliminated the allocscompilerwrapper.py Python script before refactoring all this. That's because there are two implementations of the existing environment variable mini-languages: one in the linker plugin, one in the Python script. Once we eliminate the Python script, things will be simpler.