[libgit2.git] / src / pool.c

#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];
};

struct pool_freelist {
	struct pool_freelist *next;
};

#define GIT_POOL_MIN_USABLE	4
#define GIT_POOL_MIN_PAGESZ	2 * sizeof(void*)

static void *pool_alloc_page(git_pool *pool, uint32_t size);
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)
		items_per_page = git_pool__suggest_items_per_page(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->items = 0;

	pool->has_string_alloc     = 0;
	pool->has_multi_item_alloc = 0;
	pool->has_large_page_alloc = 0;
}

void git_pool_swap(git_pool *a, git_pool *b)
{
	git_pool temp;

	if (a == b)
		return;

	memcpy(&temp, a, sizeof(temp));
	memcpy(a, b, sizeof(temp));
	memcpy(b, &temp, sizeof(temp));
}

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 void *pool_alloc_page(git_pool *pool, uint32_t size)
{
	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 NULL;

	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;
	}

	pool->items++;

	return page->data;
}

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;
}

void *git_pool_malloc(git_pool *pool, uint32_t items)
{
	git_pool_page *scan = pool->open, *prev;
	uint32_t size = items * pool->item_size;
	void *ptr = NULL;

	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 = ((struct pool_freelist *)pool->free_list)->next;
		return ptr;
	}

	/* 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);

	pool->items++;

	/* 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 ptr;
}

char *git_pool_strndup(git_pool *pool, const char *str, size_t n)
{
	char *ptr = NULL;

	assert(pool && str && pool->item_size == sizeof(char));

	if ((uint32_t)(n + 1) < n)
		return NULL;

	if ((ptr = git_pool_malloc(pool, (uint32_t)(n + 1))) != NULL) {
		memcpy(ptr, str, n);
		ptr[n] = '\0';
	}

	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));
}

char *git_pool_strdup_safe(git_pool *pool, const char *str)
{
	return str ? git_pool_strdup(pool, str) : NULL;
}

char *git_pool_strcat(git_pool *pool, const char *a, const char *b)
{
	void *ptr;
	size_t len_a, len_b;

	assert(pool && a && b && pool->item_size == sizeof(char));

	len_a = a ? strlen(a) : 0;
	len_b = b ? strlen(b) : 0;

	if ((ptr = git_pool_malloc(pool, (uint32_t)(len_a + len_b + 1))) != NULL) {
		if (len_a)
			memcpy(ptr, a, len_a);
		if (len_b)
			memcpy(((char *)ptr) + len_a, b, len_b);
		*(((char *)ptr) + len_a + len_b) = '\0';
	}
	pool->has_string_alloc = 1;

	return ptr;
}

void git_pool_free(git_pool *pool, void *ptr)
{
	struct pool_freelist *item = ptr;

	assert(pool && pool->item_size >= sizeof(void*));

	if (item) {
		item->next = pool->free_list;
		pool->free_list = item;
	}
}

void git_pool_free_array(git_pool *pool, size_t count, void **ptrs)
{
	struct pool_freelist **items = (struct pool_freelist **)ptrs;
	size_t i;

	assert(pool && ptrs && pool->item_size >= sizeof(void*));

	if (!count)
		return;

	for (i = count - 1; i > 0; --i)
		items[i]->next = items[i - 1];

	items[i]->next  = pool->free_list;
	pool->free_list = items[count - 1];
}

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 *)(((char *)scan->data) + scan->size) > ptr)
			return true;
	for (scan = pool->full; scan != NULL; scan = scan->next)
		if ((void *)scan->data <= ptr &&
			(void *)(((char *)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;
#elif defined(__amigaos4__)
		size = (uint32_t)4096; /* 4K as there is no global value we can query */
#else
		size = (uint32_t)sysconf(_SC_PAGE_SIZE);
#endif

		size -= 2 * sizeof(void *); /* allow space for malloc overhead */
	}

	return size;
}

uint32_t git_pool__suggest_items_per_page(uint32_t item_size)
{
	uint32_t page_bytes =
		git_pool__system_page_size() - sizeof(git_pool_page);
	return page_bytes / item_size;
}
Commit	Line	Data
2bc8fa02 RB	1	#include "pool.h"
	2	#ifndef GIT_WIN32
	3	#include <unistd.h>
	4	#endif
	5
	6	struct git_pool_page {
	7	git_pool_page *next;
	8	uint32_t size;
	9	uint32_t avail;
	10	char data[GIT_FLEX_ARRAY];
	11	};
	12
f16fb099 VM	13	struct pool_freelist {
f16fb099 VM	14	struct pool_freelist *next;
14bedad9 RB	15	};
14bedad9 RB	16
2bc8fa02 RB	17	#define GIT_POOL_MIN_USABLE 4
	18	#define GIT_POOL_MIN_PAGESZ 2 * sizeof(void*)
	19
19fa2bc1	20	static void pool_alloc_page(git_pool pool, uint32_t size);
2bc8fa02 RB	21	static void pool_insert_page(git_pool pool, git_pool_page page);
	22
	23	int git_pool_init(
	24	git_pool *pool, uint32_t item_size, uint32_t items_per_page)
	25	{
	26	assert(pool);
	27
	28	if (!item_size)
	29	item_size = 1;
	30	/* round up item_size for decent object alignment */
	31	if (item_size > 4)
	32	item_size = (item_size + 7) & ~7;
	33	else if (item_size == 3)
	34	item_size = 4;
	35
da3b391c RB	36	if (!items_per_page)
da3b391c RB	37	items_per_page = git_pool__suggest_items_per_page(item_size);
2bc8fa02 RB	38	if (item_size * items_per_page < GIT_POOL_MIN_PAGESZ)
	39	items_per_page = (GIT_POOL_MIN_PAGESZ + item_size - 1) / item_size;
	40
	41	memset(pool, 0, sizeof(git_pool));
	42	pool->item_size = item_size;
	43	pool->page_size = item_size * items_per_page;
	44
	45	return 0;
	46	}
	47
	48	void git_pool_clear(git_pool *pool)
	49	{
	50	git_pool_page scan, next;
	51
	52	for (scan = pool->open; scan != NULL; scan = next) {
	53	next = scan->next;
	54	git__free(scan);
	55	}
	56	pool->open = NULL;
	57
	58	for (scan = pool->full; scan != NULL; scan = next) {
	59	next = scan->next;
	60	git__free(scan);
	61	}
	62	pool->full = NULL;
	63
	64	pool->free_list = NULL;
	65
19fa2bc1 RB	66	pool->items = 0;
19fa2bc1 RB	67
2bc8fa02 RB	68	pool->has_string_alloc = 0;
	69	pool->has_multi_item_alloc = 0;
	70	pool->has_large_page_alloc = 0;
	71	}
	72
19fa2bc1 RB	73	void git_pool_swap(git_pool a, git_pool b)
	74	{
	75	git_pool temp;
	76
	77	if (a == b)
	78	return;
	79
	80	memcpy(&temp, a, sizeof(temp));
	81	memcpy(a, b, sizeof(temp));
	82	memcpy(b, &temp, sizeof(temp));
	83	}
	84
2bc8fa02 RB	85	static void pool_insert_page(git_pool pool, git_pool_page page)
	86	{
	87	git_pool_page *scan;
	88
	89	/* If there are no open pages or this page has the most open space,
	90	* insert it at the beginning of the list. This is the common case.
	91	*/
	92	if (pool->open == NULL \|\| pool->open->avail < page->avail) {
	93	page->next = pool->open;
	94	pool->open = page;
	95	return;
	96	}
	97
	98	/* Otherwise insert into sorted position. */
	99	for (scan = pool->open;
	100	scan->next && scan->next->avail > page->avail;
	101	scan = scan->next);
	102	page->next = scan->next;
	103	scan->next = page;
	104	}
	105
19fa2bc1	106	static void pool_alloc_page(git_pool pool, uint32_t size)
2bc8fa02 RB	107	{
	108	git_pool_page *page;
	109	uint32_t alloc_size;
	110
	111	if (size <= pool->page_size)
	112	alloc_size = pool->page_size;
	113	else {
	114	alloc_size = size;
	115	pool->has_large_page_alloc = 1;
	116	}
	117
	118	page = git__calloc(1, alloc_size + sizeof(git_pool_page));
	119	if (!page)
19fa2bc1	120	return NULL;
2bc8fa02 RB	121
	122	page->size = alloc_size;
	123	page->avail = alloc_size - size;
	124
	125	if (page->avail > 0)
	126	pool_insert_page(pool, page);
	127	else {
	128	page->next = pool->full;
	129	pool->full = page;
	130	}
	131
19fa2bc1	132	pool->items++;
2bc8fa02	133
19fa2bc1	134	return page->data;
2bc8fa02 RB	135	}
	136
	137	GIT_INLINE(void) pool_remove_page(
	138	git_pool pool, git_pool_page page, git_pool_page *prev)
	139	{
	140	if (prev == NULL)
	141	pool->open = page->next;
	142	else
	143	prev->next = page->next;
	144	}
	145
19fa2bc1	146	void git_pool_malloc(git_pool pool, uint32_t items)
2bc8fa02 RB	147	{
	148	git_pool_page scan = pool->open, prev;
	149	uint32_t size = items * pool->item_size;
19fa2bc1	150	void *ptr = NULL;
2bc8fa02 RB	151
	152	pool->has_string_alloc = 0;
	153	if (items > 1)
	154	pool->has_multi_item_alloc = 1;
	155	else if (pool->free_list != NULL) {
19fa2bc1	156	ptr = pool->free_list;
f16fb099	157	pool->free_list = ((struct pool_freelist *)pool->free_list)->next;
19fa2bc1	158	return ptr;
2bc8fa02 RB	159	}
	160
	161	/* just add a block if there is no open one to accomodate this */
	162	if (size >= pool->page_size \|\| !scan \|\| scan->avail < size)
19fa2bc1 RB	163	return pool_alloc_page(pool, size);
	164
	165	pool->items++;
2bc8fa02 RB	166
	167	/* find smallest block in free list with space */
	168	for (scan = pool->open, prev = NULL;
	169	scan->next && scan->next->avail >= size;
	170	prev = scan, scan = scan->next);
	171
	172	/* allocate space from the block */
19fa2bc1	173	ptr = &scan->data[scan->size - scan->avail];
2bc8fa02 RB	174	scan->avail -= size;
	175
	176	/* move to full list if there is almost no space left */
	177	if (scan->avail < pool->item_size \|\| scan->avail < GIT_POOL_MIN_USABLE) {
	178	pool_remove_page(pool, scan, prev);
	179	scan->next = pool->full;
	180	pool->full = scan;
	181	}
	182	/* reorder list if block is now smaller than the one after it */
	183	else if (scan->next != NULL && scan->next->avail > scan->avail) {
	184	pool_remove_page(pool, scan, prev);
	185	pool_insert_page(pool, scan);
	186	}
	187
19fa2bc1	188	return ptr;
2bc8fa02 RB	189	}
	190
	191	char git_pool_strndup(git_pool pool, const char *str, size_t n)
	192	{
ce33645f	193	char *ptr = NULL;
2bc8fa02 RB	194
	195	assert(pool && str && pool->item_size == sizeof(char));
	196
437f7d69 VM	197	if ((uint32_t)(n + 1) < n)
	198	return NULL;
	199
821f6bc7	200	if ((ptr = git_pool_malloc(pool, (uint32_t)(n + 1))) != NULL) {
2bc8fa02	201	memcpy(ptr, str, n);
ce33645f	202	ptr[n] = '\0';
19fa2bc1	203	}
ce33645f	204
2bc8fa02 RB	205	pool->has_string_alloc = 1;
	206
	207	return ptr;
	208	}
	209
	210	char git_pool_strdup(git_pool pool, const char *str)
	211	{
	212	assert(pool && str && pool->item_size == sizeof(char));
	213
19fa2bc1 RB	214	return git_pool_strndup(pool, str, strlen(str));
	215	}
	216
71d27358 RB	217	char git_pool_strdup_safe(git_pool pool, const char *str)
71d27358 RB	218	{
ce33645f	219	return str ? git_pool_strdup(pool, str) : NULL;
71d27358 RB	220	}
71d27358 RB	221
19fa2bc1 RB	222	char git_pool_strcat(git_pool pool, const char a, const char b)
	223	{
	224	void *ptr;
	225	size_t len_a, len_b;
	226
	227	assert(pool && a && b && pool->item_size == sizeof(char));
	228
	229	len_a = a ? strlen(a) : 0;
	230	len_b = b ? strlen(b) : 0;
	231
821f6bc7	232	if ((ptr = git_pool_malloc(pool, (uint32_t)(len_a + len_b + 1))) != NULL) {
19fa2bc1 RB	233	if (len_a)
	234	memcpy(ptr, a, len_a);
	235	if (len_b)
	236	memcpy(((char *)ptr) + len_a, b, len_b);
	237	(((char )ptr) + len_a + len_b) = '\0';
	238	}
	239	pool->has_string_alloc = 1;
	240
	241	return ptr;
2bc8fa02 RB	242	}
	243
	244	void git_pool_free(git_pool pool, void ptr)
	245	{
f16fb099	246	struct pool_freelist *item = ptr;
14bedad9	247
0c468633	248	assert(pool && pool->item_size >= sizeof(void*));
2bc8fa02	249
14bedad9 RB	250	if (item) {
	251	item->next = pool->free_list;
	252	pool->free_list = item;
0c468633 RB	253	}
	254	}
	255
	256	void git_pool_free_array(git_pool pool, size_t count, void *ptrs)
	257	{
f16fb099	258	struct pool_freelist items = (struct pool_freelist )ptrs;
0c468633 RB	259	size_t i;
	260
	261	assert(pool && ptrs && pool->item_size >= sizeof(void*));
	262
	263	if (!count)
	264	return;
	265
	266	for (i = count - 1; i > 0; --i)
14bedad9	267	items[i]->next = items[i - 1];
0c468633	268
14bedad9 RB	269	items[i]->next = pool->free_list;
14bedad9 RB	270	pool->free_list = items[count - 1];
2bc8fa02 RB	271	}
	272
	273	uint32_t git_pool__open_pages(git_pool *pool)
	274	{
	275	uint32_t ct = 0;
	276	git_pool_page *scan;
	277	for (scan = pool->open; scan != NULL; scan = scan->next) ct++;
	278	return ct;
	279	}
	280
	281	uint32_t git_pool__full_pages(git_pool *pool)
	282	{
	283	uint32_t ct = 0;
	284	git_pool_page *scan;
	285	for (scan = pool->full; scan != NULL; scan = scan->next) ct++;
	286	return ct;
	287	}
	288
	289	bool git_pool__ptr_in_pool(git_pool pool, void ptr)
	290	{
	291	git_pool_page *scan;
	292	for (scan = pool->open; scan != NULL; scan = scan->next)
821f6bc7 RB	293	if ((void *)scan->data <= ptr &&
821f6bc7 RB	294	(void )(((char )scan->data) + scan->size) > ptr)
2bc8fa02 RB	295	return true;
2bc8fa02 RB	296	for (scan = pool->full; scan != NULL; scan = scan->next)
821f6bc7 RB	297	if ((void *)scan->data <= ptr &&
821f6bc7 RB	298	(void )(((char )scan->data) + scan->size) > ptr)
2bc8fa02 RB	299	return true;
	300	return false;
	301	}
	302
	303	uint32_t git_pool__system_page_size(void)
	304	{
	305	static uint32_t size = 0;
	306
	307	if (!size) {
	308	#ifdef GIT_WIN32
	309	SYSTEM_INFO info;
	310	GetSystemInfo(&info);
	311	size = (uint32_t)info.dwPageSize;
6b5db63c	312	#elif defined(__amigaos4__)
a8df98c6	313	size = (uint32_t)4096; /* 4K as there is no global value we can query */
2bc8fa02 RB	314	#else
	315	size = (uint32_t)sysconf(_SC_PAGE_SIZE);
	316	#endif
	317
	318	size -= 2 * sizeof(void ); / allow space for malloc overhead */
	319	}
	320
	321	return size;
	322	}
	323
da3b391c RB	324	uint32_t git_pool__suggest_items_per_page(uint32_t item_size)
	325	{
	326	uint32_t page_bytes =
	327	git_pool__system_page_size() - sizeof(git_pool_page);
	328	return page_bytes / item_size;
	329	}
	330