[RFC/PATCH 2/3] small-alloc: add allocator for small objects

[David Barr <davidbarr@google.com>]

This allocator assigns an integer handle to each allocation which
can be used to retrieve the pointer to the start of the allocation
and its length.
On average, the per-allocation memory overhead is twice the length
of the variable-length-encoding of the allocation size. For objects
less than 128 bytes in size, this equates to 2 bytes of overhead.

Signed-off-by: David Barr <davidbarr@google.com>
---

 This is the second in a series of patches to enable libfastimport.
 The theme of series is memory-effective, fast, scalable data structures.

 small-alloc.c |   82 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 small-alloc.h |   18 ++++++++++++
 2 files changed, 100 insertions(+), 0 deletions(-)
 create mode 100644 small-alloc.c
 create mode 100644 small-alloc.h

diff --git a/small-alloc.c b/small-alloc.c
new file mode 100644
index 0000000..936884e
--- /dev/null
+++ b/small-alloc.c
@@ -0,0 +1,82 @@
+#include "git-compat-util.h"
+#include "cache.h"
+#include "varint.h"
+#include "small-alloc.h"
+
+static const size_t chunk_size = 2 * 1024 * 1024;
+
+void *pool_alloc(struct mem_pool *pool, size_t len, size_t *id_out)
+{
+	static size_t id = 1;
+	size_t n;
+	void *r;
+
+	if ((pool->end - pool->next_free >= len) &&
+	    (pool->len_free >= sizeof_varint(len)))
+		n = pool->nr - 1;
+	else {
+		if ((pool->end - pool->next_free < len)) {
+			size_t pool_size = chunk_size;
+			if (len >= (chunk_size/2))
+				pool_size = len;
+			pool->total_allocd += pool_size;
+			pool->next_free = malloc(pool_size);
+			pool->end = pool->next_free + pool_size;
+		}
+		pool->total_allocd += sizeof(*pool->first_id) +
+				sizeof(*pool->space) +
+				sizeof(*pool->len);
+		ALLOC_GROW(pool->first_id, pool->nr + 1, pool->f_alloc);
+		ALLOC_GROW(pool->len, pool->nr + 1, pool->l_alloc);
+		ALLOC_GROW(pool->space, pool->nr + 1, pool->s_alloc);
+		pool->first_id[pool->nr] = id;
+		pool->len_free = sizeof(*pool->len);
+		bzero(pool->len[pool->nr], sizeof(*pool->len));
+		pool->space[pool->nr] = pool->next_free;
+		n = pool->nr++;
+	}
+
+	if (id_out)
+		*id_out = id;
+	id++;
+
+	char *t = &pool->len[n][sizeof(*pool->len) - pool->len_free];
+	if (encode_varint(&t, pool->len[n] + sizeof(*pool->len), len))
+		return NULL;
+	pool->len_free = pool->len[n] + sizeof(*pool->len) - t;
+
+	r = pool->next_free;
+	pool->next_free += len;
+	return r;
+}
+
+void *pool_ptr(struct mem_pool *pool, size_t id, size_t *len_out)
+{
+	char *r;
+	const char *t;
+	uint64_t len = 0, cur;
+
+	if (!id || !pool->nr)
+		return NULL;
+
+	size_t n = pool->nr * id / pool->first_id[pool->nr - 1];
+	if (n >= pool->nr - 1)
+		n = pool->nr - 1;
+	while (n && pool->first_id[n] > id)
+		n--;
+	while (n + 1 < pool->nr && pool->first_id[n + 1] <= id)
+		n++;
+	if (pool->first_id[n] > id)
+		return NULL;
+
+	cur = pool->first_id[n];
+	for (r = pool->space[n], t = (const char*) pool->len[n];
+	     !decode_varint(&t, pool->len[n] + sizeof(*pool->len), &len);
+	     r += len, cur++)
+		if (cur == id) {
+			if (len_out)
+				*len_out = len;
+			return r;
+		}
+	return NULL;
+}
diff --git a/small-alloc.h b/small-alloc.h
new file mode 100644
index 0000000..eb77491
--- /dev/null
+++ b/small-alloc.h
@@ -0,0 +1,18 @@
+#ifndef SMALL_ALLOC_H_
+#define SMALL_ALLOC_H_
+
+struct mem_pool {
+	size_t *first_id;
+	char **space;
+	char (*len)[sizeof(size_t) + sizeof(char*)];
+	size_t f_alloc, s_alloc, l_alloc, nr;
+	char *next_free;
+	char *end;
+	int len_free;
+	size_t total_allocd;
+};
+
+void *pool_alloc(struct mem_pool *pool, size_t len, size_t *id_out);
+void *pool_ptr(struct mem_pool *pool, size_t id, size_t *len_out);
+
+#endif
-- 
1.7.5.1