sparkler: introduce a particle system

A while ago I made this particle system on SDL, and had the beginnings of
an octree implemented within it, but never finished actually using the
octree to accelerate the proximity searches.

This now has the octree completed and of course more particle interactions now
that neighbors could be found more quickly.

The simulation somewhat resembles a fireworks display.  Every particle is drawn
as a single pixel.  The visual effect is dominated by spontaneously spawned
rockets which explode into thousands of particles accompanied by bursts that
thrust particles away from the explosion radially in an expanding sphere
resembling a shock wave.  When the shock wave happens to strike another rocket,
it explodes, resulting in another shock wave.  This can produce spectacular
chain reactions, so it's worth running for some time and seeing what transpires.

1 files changed, 225 insertions, 0 deletions

diff --git a/modules/sparkler/chunker.c b/modules/sparkler/chunker.c
new file mode 100644
index 0000000..ca072eb
--- /dev/null
+++ b/modules/sparkler/chunker.c
@@ -0,0 +1,225 @@
+#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.
+ */