Overview

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.

lwsac overview

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.

lwsac initialization

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 the user 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 get 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_use() and 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_reference() and lwsac_unreference() to do the free conditionally on the last reference becoming unreferenced.

What did we learn this time?

  • Having an open-ended amount of structures or data in heap does not mean having to use strdup() and individual malloc() type semantics, nor having to walk what might be a very complex set of objects at free()-time.

  • lwsac gives 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.