From 524db0cf19648e3c7c78d3e73103b7a0bdcd6bfc Mon Sep 17 00:00:00 2001 From: Vito Caputo Date: Wed, 18 Jan 2017 17:14:52 -0800 Subject: *: move source into src/ subdir Restoring some organizational sanity since adopting autotools. --- src/modules/sparkler/chunker.c | 225 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 225 insertions(+) create mode 100644 src/modules/sparkler/chunker.c (limited to 'src/modules/sparkler/chunker.c') diff --git a/src/modules/sparkler/chunker.c b/src/modules/sparkler/chunker.c new file mode 100644 index 0000000..ca072eb --- /dev/null +++ b/src/modules/sparkler/chunker.c @@ -0,0 +1,225 @@ +#include +#include +#include +#include +#include + +#include "chunker.h" +#include "container.h" +#include "list.h" + +/* Everything associated with the particles tends to be short-lived. + * + * They come and go frequently in large numbers. This implements a very basic + * chunked allocator which prioritizes efficient allocation and freeing over + * low waste of memory. We malloc chunks at a time, doling out elements from + * the chunk sequentially as requested until the chunk is cannot fulfill an + * allocation, then we just retire the chunk, add a new chunk and continue. + * + * When allocations are freed, we simply decrement the refcount for its chunk, + * leaving the chunk pinned with holes accumulating until its refcount reaches + * zero, at which point the chunk is made available for allocations again. + * + * This requires a reference to the chunk be returned with every allocation. + * It may be possible to reduce the footprint of this by using a relative + * offset to the chunk start instead, but that would probably be more harmful + * to the alignment. + * + * This has some similarities to a slab allocator... + */ + +#define CHUNK_ALIGNMENT 8192 /* XXX: this may be unnecessary, callers should be able to ideally size their chunkers */ +#define ALLOC_ALIGNMENT 8 /* allocations within the chunk need to be aligned since their size affects subsequent allocation offsets */ +#define ALIGN(_size, _alignment) (((_size) + _alignment - 1) & ~(_alignment - 1)) + +typedef struct chunk_t { + chunker_t *chunker; /* chunker chunk belongs to */ + list_head_t chunks; /* node on free/pinned list */ + uint32_t n_refs; /* number of references (allocations) to this chunk */ + unsigned next_offset; /* next available offset for allocation */ + uint8_t mem[]; /* usable memory from this chunk */ +} chunk_t; + +typedef struct allocation_t { + chunk_t *chunk; /* chunk this allocation came from */ + uint8_t mem[]; /* usable memory from this allocation */ +} allocation_t; + +struct chunker_t { + chunk_t *chunk; /* current chunk allocations come from */ + unsigned chunk_size; /* size chunks are allocated in */ + list_head_t free_chunks; /* list of completely free chunks */ + list_head_t pinned_chunks; /* list of chunks pinned because they have an outstanding allocation */ +}; + + +/* Add a reference to a chunk. */ +static inline void chunk_ref(chunk_t *chunk) +{ + assert(chunk); + assert(chunk->chunker); + + chunk->n_refs++; + + assert(chunk->n_refs != 0); +} + + +/* Remove reference from a chunk, move to free list when no references remain. */ +static inline void chunk_unref(chunk_t *chunk) +{ + assert(chunk); + assert(chunk->chunker); + assert(chunk->n_refs > 0); + + chunk->n_refs--; + if (chunk->n_refs == 0) { + list_move(&chunk->chunks, &chunk->chunker->free_chunks); + } +} + + +/* Return allocated size of the chunk */ +static inline unsigned chunk_alloc_size(chunker_t *chunker) +{ + assert(chunker); + + return (sizeof(chunk_t) + chunker->chunk_size); +} + + +/* Get a new working chunk, retiring and replacing chunker->chunk. */ +static void chunker_new_chunk(chunker_t *chunker) +{ + chunk_t *chunk; + + assert(chunker); + + if (chunker->chunk) { + chunk_unref(chunker->chunk); + chunker->chunk = NULL; + } + + if (!list_empty(&chunker->free_chunks)) { + chunk = list_entry(chunker->free_chunks.next, chunk_t, chunks); + list_del(&chunk->chunks); + } else { + /* No free chunks, must ask libc for memory */ + chunk = malloc(chunk_alloc_size(chunker)); + } + + /* Note a chunk is pinned from the moment it's created, and a reference + * is added to represent chunker->chunk, even though no allocations + * occurred yet. + */ + chunk->n_refs = 1; + chunk->next_offset = 0; + chunk->chunker = chunker; + chunker->chunk = chunk; + list_add(&chunk->chunks, &chunker->pinned_chunks); +} + + +/* Create a new chunker. */ +chunker_t * chunker_new(unsigned chunk_size) +{ + chunker_t *chunker; + + chunker = calloc(1, sizeof(chunker_t)); + if (!chunker) { + return NULL; + } + + INIT_LIST_HEAD(&chunker->free_chunks); + INIT_LIST_HEAD(&chunker->pinned_chunks); + + /* XXX: chunker->chunk_size does not include the size of the chunk_t container */ + chunker->chunk_size = ALIGN(chunk_size, CHUNK_ALIGNMENT); + + return chunker; +} + + +/* Allocate non-zeroed memory from a chunker. */ +void * chunker_alloc(chunker_t *chunker, unsigned size) +{ + allocation_t *allocation; + + assert(chunker); + assert(size <= chunker->chunk_size); + + size = ALIGN(sizeof(allocation_t) + size, ALLOC_ALIGNMENT); + + if (!chunker->chunk || size + chunker->chunk->next_offset > chunker->chunk_size) { + /* Retire this chunk, time for a new one */ + chunker_new_chunk(chunker); + } + + if (!chunker->chunk) { + return NULL; + } + + chunk_ref(chunker->chunk); + allocation = (allocation_t *)&chunker->chunk->mem[chunker->chunk->next_offset]; + chunker->chunk->next_offset += size; + allocation->chunk = chunker->chunk; + + assert(chunker->chunk->next_offset <= chunker->chunk_size); + + return allocation->mem; +} + + +/* Free memory allocated from a chunker. */ +void chunker_free(void *ptr) +{ + allocation_t *allocation = container_of(ptr, allocation_t, mem); + + assert(ptr); + + chunk_unref(allocation->chunk); +} + + +/* Free a chunker and it's associated allocations. */ +void chunker_free_chunker(chunker_t *chunker) +{ + chunk_t *chunk, *_chunk; + + assert(chunker); + + if (chunker->chunk) { + chunk_unref(chunker->chunk); + } + + assert(list_empty(&chunker->pinned_chunks)); + + list_for_each_entry_safe(chunk, _chunk, &chunker->free_chunks, chunks) { + free(chunk); + } + + free(chunker); +} + +/* TODO: add pinned chunk iterator interface for cache-friendly iterating across + * chunk contents. + * The idea is that at times when the performance is really important, the + * chunks will be full of active particles, because it's the large numbers + * which slows us down. At those times, it's beneficial to not walk linked + * lists of structs to process them, instead we just process all the elements + * of the chunk as an array and assume everything is active. The type of + * processing being done in this fashion is benign to perform on an unused + * element, as long as there's no dangling pointers being dereferenced. If + * there's references, a status field could be maintained in the entry to say + * if it's active, then simply skip processing of the inactive elements. This + * tends to be more cache-friendly than chasing pointers. A linked list + * heirarchy of particles is still maintained for the parent:child + * relationships under the assumption that some particles will make use of the + * tracked descendants, though nothing has been done with it yet. + * + * The current implementation of the _particle_t is variable length, which precludes + * this optimization. However, breaking out the particle_props_t into a separate + * chunker would allow running particles_age() across the props alone directly + * within the pinned chunks. The other passes are still done heirarchically, + * and require the full particle context. + */ -- cgit v1.2.3