Per-container custom allocator

[yrashk]

I have a case where allocation primitives of the underlying systems are more complex than having a single global allocator. Essentially, multiple allocation areas with a concept of a "current one."

Specifically, I am using MemoryContexts in PostgreSQL.

The way STC currently works sometimes results in hard-to-find bugs. I may have a current memory context that would go out of scope and get dropped before I dispose of an STC collection.

So, I was thinking, what if we add optional allocators to collections?

Say, something like this interface-wise:

#define i_allocator alloc_type
#define i_val int
#define i_tag obj
#include <stc/cvec.h>

When i_allocator is defined, the underlying structure will get an additional field of an "allocator type," which is something like:

typedef struct {
i_allocator allocator;
void *(*malloc)(i_allocator *, size_t);
void *(*calloc)(i_allocator *, int, size_t);
void *(*realloc)(i_allocator *, void *,size_t);
void *(*free)(i_allocator *, void *);
} i_type_allocator;
...
typedef struct {
 i_type_allocator allocator;
} i_type;

And in this case, the container will use this allocator instead of the global one.

All the initializer members of such a container will receive an additional argument of that struct type (or, perhaps, a pointer to one) so that the underlying allocator and the methods can be appropriately initialized:

cvec_obj_init(&(i_type_allocator){.allocator = ..., .malloc = ...});

Happy to try working on a PR (however, I am still not very confident with STC's codebase so it may take some time) or help to get it done if there's an agreement.

[tylov]

Hi, yes, I think there is a simpler solution to this, I will come back to you.

[tylov]

I am not keen on extending containers struct, in particular not conditionally, because it will then be very error-prone to pre-declare containers. From what I gather, in your case, only palloc() is context sensitive - repalloc() and pfree() knows which context the memory came from. In principle you can override c_malloc(), c_realloc, c_calloc() and c_free(),but you need to make sure that you have switched to the correct context before inserting new data into the containers. If you have one context per container, you can store the context in a struct along with the container.
I also noticed that repalloc() and pfree() does not accept NULL, so in principle you could do something like: (EDITED to current STC):

#define pgs_malloc(sz) palloc(sz)
#define pgs_calloc(n, sz) palloc0((n)*(sz))
#define pgs_realloc(p, sz) (p) ? repalloc(p, sz) : palloc(sz)   // palloc() only called on first insert
#define pgs_free(p, sz) (p) ? pfree(p) : (void)0

Create your container:

#define i_val int
#define i_allocator pgs
#include <stc/cvec.h> // cvec, cstack, csmap only uses realloc and free after some data is inserted. cmap and clist uses malloc. 
...
setContext();
cvec_int vec = cvec_int_with_capacity(10); // allocate with current context
// now you can insert and free vec without worry about context.

If you really need an allocator per container-instance, it gets more complicated, because then each of these functions must be given a pointer to the container, which is not always available. (e.g. an element may use dyn. allocation and be created before it is inserted into the container).

[yrashk]

I apologize for the late response. This does indeed seem to help to a degree. However, if I understand correctly, this approach would be that one has to be extremely careful when using STC API. For example, insert_entry may call reserve, which will call i_malloc and if we're not in the right context, well, too bad.

Do you think there's any chance we can further explore the idea of optional (opt-in) allocators/allocator contexts in containers? The example I gave above introduces a bit of indirection (having to go through function pointers), but what if we instead had an optional ability to define a container to have an arbitrary "context"/"payload" (a void *) that would get passed to the specified allocator. The stdlib allocators (that use malloc and friends) will ignore this payload. If the container doesn't have the payload field (because it wasn't opted in for), the implementation of the container will always supply NULL.

I'd be extremely interested in assisting in this. I love using STC, but this issue is causing me a lot of pain in the context of Postgres memory allocators, and I'd love to have a better resolution.

[yrashk]

To be less hand-wavy, I sent a limited-surface proof of concept of what I had in mind in #52

[tylov]

I think this can be done without introducing void* or function pointers to every container. And in your case, I still don't understand why you need the context other than for palloc as described here.

The issue with adding a void* in the container is that conditionally changing the data size/types of the container, makes them prone to errors if they are forward declared accidentally differently from in the implementation, in addition to be type-unsafe.

EDIT: The following actually works without any changes to STC:

// Generic code:
#include <stddef.h>
#include <stdio.h>
#include <stc/forward.h>

#define pgs_malloc(sz) \
    (printf("switch context: %d\n", c_container_of(self, _cx_memb(Pgs), pgs)->ctx), c_malloc(sz))
#define pgs_realloc(p, sz) (p ? c_realloc(p, sz) : pgs_malloc(sz))
#define pgs_free(p) (p ? c_free(p) : (void)0)

#define declare_pgs_con(C, base, ...) \
    forward_##base(C, __VA_ARGS__); \
    typedef struct { \
        int ctx; \
        C pgs; \
    } C##Pgs
// ------------------------

declare_pgs_con(IVec, cvec, int);
#define i_type IVec
#define i_val int
#define i_allocator pgs
#define i_opt c_is_forward // avoid re-type-define IVec
#include <stc/cvec.h>

int main()
{
    IVecPgs vec = {.ctx=100}; // Ok: .pgs and any container can be initialized with {0}.
    IVec_push(&vec.pgs, 42);
}

I use a similar technique in the example functor.c (this may become deprecated, as I don't think it will be much used?).

[yrashk]

@tylov thank you for such a swift response.

There are a couple of reasons why I suggested my approach with explicit context stored in the container:

1. It is error-prone to have initialization methods (like init) that do not keep track of the current memory context. This means if, by mistake, one initializes, say, a vector with init() and not with_capacity(c), then the container will "get" its memory context when the first memory reservation will be requested.
2. Some containers rely on malloc past their initialization, like clist that will malloc on pushes, not using the current context during container initialization.
3. Relying on the current context during initialization (even if it was the only place when it happened) requires at times to change the context temporarily just for the purpose of the container initialization, leading to code like oldcontext = changetocontext(ctx); container = init(); changetocontext(newcontext) which is noisy and more error-prone.
4. Relying on Postgres' ability to identify the memory context of any pointer is convenient. Still, it comes with a cost of a function call indirection and the cost of the function itself that will get the actual memory context. Storing a single pointer gets us there without the overhead at the cost of an extra pointer per container.

[tylov]

The code I showed (now updated) may be difficult to understand, but it exactly the same as having a context pointer inside each container - it is simply placed outside the container instead. The advantage is that this is typesafe, and you can place the context as a typesafe value. This will also be faster. As you see, you can place the allocator and declare_pgs_con() defines in a separate file and use it for every container.

[yrashk]

What about containers that rely on malloc interface, such as clist (point 2 in my list)?My understanding is that it'll require me to switch the current context every time I push to the list.

[tylov]

No. When you #define i_allocator pgs, i_malloc() will call pgs_malloc() which accesses ctx that is stored next to clist pgs. You can make a wrapper function which is called from the pgs_malloc macro to save/restore ctx before/after malloc, otherwise just set the current context to ctx instead of the printf and replace malloc with palloc.

NOTE: You cannot use IVec_with_capacity() / with_size(), because ctx is not initialized yet. Write you own IVecPgs constructor for that, or just use reserve() / resize() after init.

[yrashk]

Thank you. I think I may have originally not understood the example you've shown well. I am re-reading it now, and it starts making more sense.

The fact that it (as you noted) is difficult to understand is still somewhat concerning. Perhaps I should try find a way to make it less so.

[tylov]

The container_of macro is not in the standard, but is highly valuable for generic programming in C and well known as it is used in the linux kernel. The c_container_of() is in addition typesafe and portable. However, it still requires that the first arg. actually points to the member (third arg.) of the struct type given as the second argument.

[yrashk]

I am familiar with this approach. It is commonly used in libh2o which I am using heavily right now (https://github.com/h2o/h2o/blob/2ea8864c61abe6011aa6dbbb15fe4134710a31be/include/h2o/memory.h#L40) so I am up to date on this one! :)

[tylov]

The fact that it (as you noted) is difficult to understand is still somewhat concerning. Perhaps I should try find a way to make it less so.

Here is what you can do:
Edit 3: There is now an <stc/extend.h> header which allows for extending containers type-safely: Use the c_extend() macro to access the extended data in the container:

// stcpgs.h
#define pgs_malloc(sz) MemoryContextAlloc(c_extend()->memctx, sz)
#define pgs_calloc(n, sz) MemoryContextAllocZero(c_extend()->memctx, (n)*(sz))
#define pgs_realloc(p, sz) (p ? repalloc(p, sz) : pgs_malloc(sz))
#define pgs_free(p) (p ? pfree(p) : (void)0)

#define i_extend MemoryContext memctx;
#define i_allocator pgs
#define i_no_clone
#include <stc/extend.h>

Use IVec_ext and IMap_ext types as containers, and access the "real" containers with .get:

#include <stdio.h>
#define i_type IVec
#define i_key int
#define i_base cvec // base container to use
#include "stcpgs.h"

#define i_type IMap
#define i_key int
#define i_val int
#define i_base csmap
#include "stcpgs.h"

void vectest()
{
    IVec_ext vec = {.memctx=2}; 
    c_forrange (i, 1, 16)
        IVec_push(&vec.get, i*i);

    c_foreach (i, IVec, vec.get)
        printf("%d ", *i.ref);

    puts("");
    IVec_drop(&vec.get);
}

void maptest()
{
    IMap_ext map = {.memctx=1};
    c_forrange (i, 1, 16)
        IMap_insert(&map.get, i*i, i);

    c_foreach (i, IMap, map.get)
        printf("%d:%d ", i.ref->first, i.ref->second);

    puts("");
    IMap_drop(&map.get);
}