Implement git_pool paged memory allocator

This adds a `git_pool` object that can do simple paged memory
allocation with free for the entire pool at once.  Using this,
you can replace many small allocations with large blocks that
can then cheaply be doled out in small pieces.  This is best
used when you plan to free the small blocks all at once - for
example, if they represent the parsed state from a file or data
stream that are either all kept or all discarded.

There are two real patterns of usage for `git_pools`: either
for "string" allocation, where the item size is a single byte
and you end up just packing the allocations in together, or for
"fixed size" allocation where you are allocating a large object
(e.g. a `git_oid`) and you generally just allocation single
objects that can be tightly packed.  Of course, you can use it
for other things, but those two cases are the easiest.

1 files changed, 249 insertions, 0 deletions

diff --git a/src/pool.c b/src/pool.c
new file mode 100644
index 000000000..8a611a2dc
--- /dev/null
+++ b/src/pool.c
@@ -0,0 +1,249 @@
+#include "pool.h"
+#ifndef GIT_WIN32
+#include <unistd.h>
+#endif
+
+struct git_pool_page {
+	git_pool_page *next;
+	uint32_t size;
+	uint32_t avail;
+	char data[GIT_FLEX_ARRAY];
+};
+
+#define GIT_POOL_MIN_USABLE	4
+#define GIT_POOL_MIN_PAGESZ	2 * sizeof(void*)
+
+static int pool_alloc_page(git_pool *pool, uint32_t size, void **ptr);
+static void pool_insert_page(git_pool *pool, git_pool_page *page);
+
+int git_pool_init(
+	git_pool *pool, uint32_t item_size, uint32_t items_per_page)
+{
+	assert(pool);
+
+	if (!item_size)
+		item_size = 1;
+	/* round up item_size for decent object alignment */
+	if (item_size > 4)
+		item_size = (item_size + 7) & ~7;
+	else if (item_size == 3)
+		item_size = 4;
+
+	if (!items_per_page) {
+		uint32_t page_bytes =
+			git_pool__system_page_size() - sizeof(git_pool_page);
+		items_per_page = page_bytes / item_size;
+	}
+	if (item_size * items_per_page < GIT_POOL_MIN_PAGESZ)
+		items_per_page = (GIT_POOL_MIN_PAGESZ + item_size - 1) / item_size;
+
+	memset(pool, 0, sizeof(git_pool));
+	pool->item_size = item_size;
+	pool->page_size = item_size * items_per_page;
+
+	return 0;
+}
+
+void git_pool_clear(git_pool *pool)
+{
+	git_pool_page *scan, *next;
+
+	for (scan = pool->open; scan != NULL; scan = next) {
+		next = scan->next;
+		git__free(scan);
+	}
+	pool->open = NULL;
+
+	for (scan = pool->full; scan != NULL; scan = next) {
+		next = scan->next;
+		git__free(scan);
+	}
+	pool->full = NULL;
+
+	pool->free_list = NULL;
+
+	pool->has_string_alloc     = 0;
+	pool->has_multi_item_alloc = 0;
+	pool->has_large_page_alloc = 0;
+}
+
+static void pool_insert_page(git_pool *pool, git_pool_page *page)
+{
+	git_pool_page *scan;
+
+	/* If there are no open pages or this page has the most open space,
+	 * insert it at the beginning of the list.  This is the common case.
+	 */
+	if (pool->open == NULL || pool->open->avail < page->avail) {
+		page->next = pool->open;
+		pool->open = page;
+		return;
+	}
+
+	/* Otherwise insert into sorted position. */
+	for (scan = pool->open;
+		 scan->next && scan->next->avail > page->avail;
+		 scan = scan->next);
+	page->next = scan->next;
+	scan->next = page;
+}
+
+static int pool_alloc_page(
+	git_pool *pool, uint32_t size, void **ptr)
+{
+	git_pool_page *page;
+	uint32_t alloc_size;
+
+	if (size <= pool->page_size)
+		alloc_size = pool->page_size;
+	else {
+		alloc_size = size;
+		pool->has_large_page_alloc = 1;
+	}
+
+	page = git__calloc(1, alloc_size + sizeof(git_pool_page));
+	if (!page)
+		return -1;
+
+	page->size  = alloc_size;
+	page->avail = alloc_size - size;
+
+	if (page->avail > 0)
+		pool_insert_page(pool, page);
+	else {
+		page->next = pool->full;
+		pool->full = page;
+	}
+
+	*ptr = page->data;
+
+	return 0;
+}
+
+GIT_INLINE(void) pool_remove_page(
+	git_pool *pool, git_pool_page *page, git_pool_page *prev)
+{
+	if (prev == NULL)
+		pool->open = page->next;
+	else
+		prev->next = page->next;
+}
+
+int git_pool_malloc(git_pool *pool, uint32_t items, void **ptr)
+{
+	git_pool_page *scan = pool->open, *prev;
+	uint32_t size = items * pool->item_size;
+
+	pool->has_string_alloc = 0;
+	if (items > 1)
+		pool->has_multi_item_alloc = 1;
+	else if (pool->free_list != NULL) {
+		*ptr = pool->free_list;
+		pool->free_list = *((void **)pool->free_list);
+	}
+
+	/* just add a block if there is no open one to accomodate this */
+	if (size >= pool->page_size || !scan || scan->avail < size)
+		return pool_alloc_page(pool, size, ptr);
+
+	/* find smallest block in free list with space */
+	for (scan = pool->open, prev = NULL;
+		 scan->next && scan->next->avail >= size;
+		 prev = scan, scan = scan->next);
+
+	/* allocate space from the block */
+	*ptr = &scan->data[scan->size - scan->avail];
+	scan->avail -= size;
+
+	/* move to full list if there is almost no space left */
+	if (scan->avail < pool->item_size || scan->avail < GIT_POOL_MIN_USABLE) {
+		pool_remove_page(pool, scan, prev);
+		scan->next = pool->full;
+		pool->full = scan;
+	}
+	/* reorder list if block is now smaller than the one after it */
+	else if (scan->next != NULL && scan->next->avail > scan->avail) {
+		pool_remove_page(pool, scan, prev);
+		pool_insert_page(pool, scan);
+	}
+
+	return 0;
+}
+
+char *git_pool_strndup(git_pool *pool, const char *str, size_t n)
+{
+	void *ptr = NULL;
+
+	assert(pool && str && pool->item_size == sizeof(char));
+
+	if (!git_pool_malloc(pool, n, &ptr))
+		memcpy(ptr, str, n);
+	pool->has_string_alloc = 1;
+
+	return ptr;
+}
+
+char *git_pool_strdup(git_pool *pool, const char *str)
+{
+	assert(pool && str && pool->item_size == sizeof(char));
+
+	return git_pool_strndup(pool, str, strlen(str) + 1);
+}
+
+void git_pool_free(git_pool *pool, void *ptr)
+{
+	assert(pool && ptr && pool->item_size >= sizeof(void*));
+
+	*((void **)ptr) = pool->free_list;
+	pool->free_list = ptr;
+}
+
+uint32_t git_pool__open_pages(git_pool *pool)
+{
+	uint32_t ct = 0;
+	git_pool_page *scan;
+	for (scan = pool->open; scan != NULL; scan = scan->next) ct++;
+	return ct;
+}
+
+uint32_t git_pool__full_pages(git_pool *pool)
+{
+	uint32_t ct = 0;
+	git_pool_page *scan;
+	for (scan = pool->full; scan != NULL; scan = scan->next) ct++;
+	return ct;
+}
+
+bool git_pool__ptr_in_pool(git_pool *pool, void *ptr)
+{
+	git_pool_page *scan;
+	for (scan = pool->open; scan != NULL; scan = scan->next)
+		if ( ((void *)scan->data) <= ptr &&
+			(((void *)scan->data) + scan->size) > ptr)
+			return true;
+	for (scan = pool->full; scan != NULL; scan = scan->next)
+		if ( ((void *)scan->data) <= ptr &&
+			(((void *)scan->data) + scan->size) > ptr)
+			return true;
+	return false;
+}
+
+uint32_t git_pool__system_page_size(void)
+{
+	static uint32_t size = 0;
+
+	if (!size) {
+#ifdef GIT_WIN32
+		SYSTEM_INFO info;
+		GetSystemInfo(&info);
+		size = (uint32_t)info.dwPageSize;
+#else
+		size = (uint32_t)sysconf(_SC_PAGE_SIZE);
+#endif
+
+		size -= 2 * sizeof(void *); /* allow space for malloc overhead */
+	}
+
+	return size;
+}
+