diff options
Diffstat (limited to 'modules/sparkler/chunker.c')
| -rw-r--r-- | modules/sparkler/chunker.c | 225 |
1 files changed, 0 insertions, 225 deletions
diff --git a/modules/sparkler/chunker.c b/modules/sparkler/chunker.c deleted file mode 100644 index ca072eb..0000000 --- a/modules/sparkler/chunker.c +++ /dev/null @@ -1,225 +0,0 @@ -#include <assert.h> -#include <stddef.h> -#include <stdlib.h> -#include <stdint.h> -#include <string.h> - -#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. - */ |