- CMake options:
- Public header: (included by libwebsockets.h) include/libwebsockets/lws-lwsac.h
- Implementation: lib/misc/lwsac/lwsac.c
Lwsac (“Allocated Chunks”) is a chained heap allocator that can be very useful when you know you need heap for:
- an unknown but possibly large number of objects
- objects that may be different sizes
- storage for, eg, strings pointed to by objects
- are for a related purpose
- may tend to reference each other
- share the same lifetime, when the job is done they all need to be freed
The basic trick is that in one lwsac object, you can chain together multiple
malloc type heap allocations and suballocate inside that in an automanaged
linked-list; if it happens you don’t have enough space for the next
suballocation (or “use” in lwsac language), it simply malloc’s up another chunk
for the chain that’s at least as big as you need (chunks in the lwsac can all be
different sizes without problems). The individual “uses” are contiguous blocks
without gaps, although there can’t be assumed to be any relationship between
the addresses of two different “uses” other than they’re all in the one logical
lwsac comes into its own when a) you don’t know at the start how much heap you’re going to have to use, and b) your suballocations have relationships to each other, for example, structs that live in the lwsac point to other structs also using the same lwsac… the “use” suballocations simply move forward the chunk high water mark to the next alignment boundary and are not tracked otherwise at all. You cannot free() individual uses, since nothing tracks them, but only allocate more at the head of the lwsac chunk list.
When it’s time to destroy the whole related complex of suballocations, lwsac just goes through the chunk list freeing those… it doesn’t track what’s inside just gets rid of the lwsac chunks everything was sitting on in one step. So it’s very simple to bulk-destroy the related allocations, you don’t have to walk everything to the nth degree just make one call to wrap it all up.
The user footprint is only an
lwsac_t * that is initially NULL… when it’s
used, this points to the first chunk which also has a header that describes
the lwsac itself. When it’s eventually freed, all the chunks are freed and
lwsac_t * set to NULL again. So there is no init necessary, just
make sure your
lwsac_t * starts off as NULL.
Using space inside the lwsac
The main api is
void * lwsac_use(struct lwsac **head, size_t ensure, size_t chunk_size);
You can simply point to your
lwsac_t *, ask for
ensure bytes of
contiguous memory, optionally set the size for any new chunk (0 defaults to
4KB chunk or the size of ensure if it’s bigger than that). You’ll either
NULL returned if it’s OOM, or a pointer aligned to
sizeof(void *) you
can immediately use for your use.
Because there’s no overhead except alignment, unlike malloc() where there is
considerable overhead for small sized allocations, there is basically no
overhead to “use” the lwsac for, eg, string bodies that were pointed-to by
const char * members in a struct you are instantiating the the lwsac.
It’s quite possible you only need
lwsac_free() below, but
there’s also a useful variant
void * lwsac_use_zero(struct lwsac **head, size_t ensure, size_t chunk_size);
…which does the same as
lwsac_use(), but zeroes down the memory before
handing the pointer back to the caller.
If memory is really tight, you can use another variant
void * lwsac_use_backfill(struct lwsac **head, size_t ensure, size_t chunk_size);
if a requested “use” won’t fit into the tail chunk free space, then this causes lwsac to go check in all the prior chunks if any of their free space would fit it without having to do any new allocation. If you might have a lot of chunks this is slower, but if some of your “use” sizes are small this can save you some heap if that is critical.
Freeing the whole lwsac
There is no api to free individual uses, they are only tracked with a high- water mark inside the chunk they are in, so there is no overhead.
void lwsac_free(struct lwsac **head);
lwsac_free() frees any chunks in the chain in the lwsac and sets you pointer
to NULL. Depending on what your code does, it may “use” tens of thousands of
objects in only a few dozen lwsac chunks… when it comes time to discard them
all, it means you are done after a few dozen calls to free().
You may want to pass the lwsac around for it to be processed by different
chunks of code, for that it might be convenient to reference-count who still
has things in the lwsac they don’t want deleted. You can use
lwsac_unreference() to do the free conditionally on the last reference
What did we learn this time?
Having an open-ended amount of structures or data in heap does not mean having to use
malloc()type semantics, nor having to walk what might be a very complex set of objects at
lwsacgives you a chained, chunked allocator within which you can make suballocations without taking any care about tracking or planning ahead for alloc sizes. Just ask to “use” whatever size you need next.
When you are done with the whole related allocation, you can just free the underlying chained chunks, like cleaning up a kids birthday part by gathering up the disposable tablecloth and throwing it and whatever was in it into the garbage in one step.