pool.c 7.16 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12
#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];
};

13 14
struct pool_freelist {
	struct pool_freelist *next;
15 16
};

17 18 19
#define GIT_POOL_MIN_USABLE	4
#define GIT_POOL_MIN_PAGESZ	2 * sizeof(void*)

20
static void *pool_alloc_page(git_pool *pool, uint32_t size);
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
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;

36 37
	if (!items_per_page)
		items_per_page = git_pool__suggest_items_per_page(item_size);
38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
	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;

66 67
	pool->items = 0;

68 69 70 71 72
	pool->has_string_alloc     = 0;
	pool->has_multi_item_alloc = 0;
	pool->has_large_page_alloc = 0;
}

73 74 75 76 77 78 79 80 81 82 83 84
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));
}

85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
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;
}

106
static void *pool_alloc_page(git_pool *pool, uint32_t size)
107 108 109 110 111 112 113 114 115 116 117 118 119
{
	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)
120
		return NULL;
121 122 123 124 125 126 127 128 129 130 131

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

132
	pool->items++;
133

134
	return page->data;
135 136 137 138 139 140 141 142 143 144 145
}

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

146
void *git_pool_malloc(git_pool *pool, uint32_t items)
147 148 149
{
	git_pool_page *scan = pool->open, *prev;
	uint32_t size = items * pool->item_size;
150
	void *ptr = NULL;
151 152 153 154 155

	pool->has_string_alloc = 0;
	if (items > 1)
		pool->has_multi_item_alloc = 1;
	else if (pool->free_list != NULL) {
156
		ptr = pool->free_list;
157
		pool->free_list = ((struct pool_freelist *)pool->free_list)->next;
158
		return ptr;
159 160 161 162
	}

	/* just add a block if there is no open one to accomodate this */
	if (size >= pool->page_size || !scan || scan->avail < size)
163 164 165
		return pool_alloc_page(pool, size);

	pool->items++;
166 167 168 169 170 171 172

	/* 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 */
173
	ptr = &scan->data[scan->size - scan->avail];
174 175 176 177 178 179 180 181 182 183 184 185 186 187
	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);
	}

188
	return ptr;
189 190 191 192
}

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

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

197 198 199
	if ((uint32_t)(n + 1) < n)
		return NULL;

Russell Belfer committed
200
	if ((ptr = git_pool_malloc(pool, (uint32_t)(n + 1))) != NULL) {
201
		memcpy(ptr, str, n);
202
		ptr[n] = '\0';
203
	}
204

205 206 207 208 209 210 211 212 213
	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));

214 215 216
	return git_pool_strndup(pool, str, strlen(str));
}

217 218
char *git_pool_strdup_safe(git_pool *pool, const char *str)
{
219
	return str ? git_pool_strdup(pool, str) : NULL;
220 221
}

222 223 224 225 226 227 228 229 230 231
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;

Russell Belfer committed
232
	if ((ptr = git_pool_malloc(pool, (uint32_t)(len_a + len_b + 1))) != NULL) {
233 234 235 236 237 238 239 240 241
		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;
242 243 244 245
}

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

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

250 251 252
	if (item) {
		item->next = pool->free_list;
		pool->free_list = item;
253 254 255 256 257
	}
}

void git_pool_free_array(git_pool *pool, size_t count, void **ptrs)
{
258
	struct pool_freelist **items = (struct pool_freelist **)ptrs;
259 260 261 262 263 264 265 266
	size_t i;

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

	if (!count)
		return;

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

269 270
	items[i]->next  = pool->free_list;
	pool->free_list = items[count - 1];
271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292
}

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)
Russell Belfer committed
293 294
		if ((void *)scan->data <= ptr &&
			(void *)(((char *)scan->data) + scan->size) > ptr)
295 296
			return true;
	for (scan = pool->full; scan != NULL; scan = scan->next)
Russell Belfer committed
297 298
		if ((void *)scan->data <= ptr &&
			(void *)(((char *)scan->data) + scan->size) > ptr)
299 300 301 302 303 304 305 306 307 308 309 310 311
			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;
Chris Young committed
312
#elif defined(__amigaos4__)
313
		size = (uint32_t)4096; /* 4K as there is no global value we can query */
314 315 316 317 318 319 320 321 322 323
#else
		size = (uint32_t)sysconf(_SC_PAGE_SIZE);
#endif

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

	return size;
}

324 325 326 327 328 329 330
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;
}