diff options
| -rw-r--r-- | src/blob.c | 4 | ||||
| -rw-r--r-- | src/buffer.c | 2 | ||||
| -rw-r--r-- | src/config_file.c | 10 | ||||
| -rw-r--r-- | src/errors.c | 2 | ||||
| -rw-r--r-- | src/filter.c | 2 | ||||
| -rw-r--r-- | src/global.c | 6 | ||||
| -rw-r--r-- | src/odb.c | 2 | ||||
| -rw-r--r-- | src/pool.c | 249 | ||||
| -rw-r--r-- | src/pool.h | 108 | ||||
| -rw-r--r-- | src/refs.c | 2 | ||||
| -rw-r--r-- | src/remote.c | 2 | ||||
| -rw-r--r-- | src/repository.c | 2 | ||||
| -rw-r--r-- | tests-clar/core/pool.c | 85 |
13 files changed, 459 insertions, 17 deletions
diff --git a/src/blob.c b/src/blob.c index f553de888..36571c70a 100644 --- a/src/blob.c +++ b/src/blob.c @@ -139,12 +139,12 @@ static int write_symlink( read_len = p_readlink(path, link_data, link_size); if (read_len != (ssize_t)link_size) { giterr_set(GITERR_OS, "Failed to create blob. Can't read symlink '%s'", path); - free(link_data); + git__free(link_data); return -1; } error = git_odb_write(oid, odb, (void *)link_data, link_size, GIT_OBJ_BLOB); - free(link_data); + git__free(link_data); return error; } diff --git a/src/buffer.c b/src/buffer.c index c23803564..24a0abdbe 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -159,7 +159,7 @@ int git_buf_printf(git_buf *buf, const char *format, ...) va_end(arglist); if (len < 0) { - free(buf->ptr); + git__free(buf->ptr); buf->ptr = &git_buf__oom; return -1; } diff --git a/src/config_file.c b/src/config_file.c index 5cc15d457..fd634fbca 100644 --- a/src/config_file.c +++ b/src/config_file.c @@ -370,7 +370,7 @@ static int config_set_multivar(git_config_file *cfg, const char *name, const cha result = regcomp(&preg, regexp, REG_EXTENDED); if (result < 0) { - free(key); + git__free(key); giterr_set_regex(&preg, result); return -1; } @@ -380,7 +380,7 @@ static int config_set_multivar(git_config_file *cfg, const char *name, const cha char *tmp = git__strdup(value); GITERR_CHECK_ALLOC(tmp); - free(var->value); + git__free(var->value); var->value = tmp; replaced = 1; } @@ -409,7 +409,7 @@ static int config_set_multivar(git_config_file *cfg, const char *name, const cha result = config_write(b, key, &preg, value); - free(key); + git__free(key); regfree(&preg); return result; @@ -426,7 +426,7 @@ static int config_delete(git_config_file *cfg, const char *name) return -1; var = git_hashtable_lookup(b->values, key); - free(key); + git__free(key); if (var == NULL) return GIT_ENOTFOUND; @@ -1275,7 +1275,7 @@ static int parse_variable(diskfile_backend *cfg, char **var_name, char **var_val char *proc_line = fixup_line(value_start, 0); GITERR_CHECK_ALLOC(proc_line); git_buf_puts(&multi_value, proc_line); - free(proc_line); + git__free(proc_line); if (parse_multiline_variable(cfg, &multi_value, quote_count) < 0 || git_buf_oom(&multi_value)) { git__free(*var_name); git__free(line); diff --git a/src/errors.c b/src/errors.c index aad6c4482..7a6bbd654 100644 --- a/src/errors.c +++ b/src/errors.c @@ -173,7 +173,7 @@ void giterr_set_str(int error_class, const char *string) { git_error *error = &GIT_GLOBAL->error_t; - free(error->message); + git__free(error->message); error->message = git__strdup(string); error->klass = error_class; diff --git a/src/filter.c b/src/filter.c index f0ee1ad39..d2d113409 100644 --- a/src/filter.c +++ b/src/filter.c @@ -111,7 +111,7 @@ void git_filters_free(git_vector *filters) if (filter->do_free != NULL) filter->do_free(filter); else - free(filter); + git__free(filter); } git_vector_free(filters); diff --git a/src/global.c b/src/global.c index b10fabc61..368c6c664 100644 --- a/src/global.c +++ b/src/global.c @@ -62,7 +62,7 @@ git_global_st *git__global_state(void) if ((ptr = TlsGetValue(_tls_index)) != NULL) return ptr; - ptr = malloc(sizeof(git_global_st)); + ptr = git__malloc(sizeof(git_global_st)); if (!ptr) return NULL; @@ -78,7 +78,7 @@ static int _tls_init = 0; static void cb__free_status(void *st) { - free(st); + git__free(st); } void git_threads_init(void) @@ -103,7 +103,7 @@ git_global_st *git__global_state(void) if ((ptr = pthread_getspecific(_tls_key)) != NULL) return ptr; - ptr = malloc(sizeof(git_global_st)); + ptr = git__malloc(sizeof(git_global_st)); if (!ptr) return NULL; @@ -169,7 +169,7 @@ int git_odb__hashlink(git_oid *out, const char *path) } result = git_odb_hash(out, link_data, (size_t)size, GIT_OBJ_BLOB); - free(link_data); + git__free(link_data); } else { int fd = git_futils_open_ro(path); if (fd < 0) 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; +} + diff --git a/src/pool.h b/src/pool.h new file mode 100644 index 000000000..5f65412a0 --- /dev/null +++ b/src/pool.h @@ -0,0 +1,108 @@ +/* + * Copyright (C) 2012 the libgit2 contributors + * + * This file is part of libgit2, distributed under the GNU GPL v2 with + * a Linking Exception. For full terms see the included COPYING file. + */ +#ifndef INCLUDE_pool_h__ +#define INCLUDE_pool_h__ + +#include "common.h" + +typedef struct git_pool_page git_pool_page; + +/** + * Chunked allocator. + * + * A `git_pool` can be used when you want to cheaply allocate + * multiple items of the same type and are willing to free them + * all together with a single call. The two most common cases + * are a set of fixed size items (such as lots of OIDs) or a + * bunch of strings. + * + * Internally, a `git_pool` allocates pages of memory and then + * deals out blocks from the trailing unused portion of each page. + * The pages guarantee that the number of actual allocations done + * will be much smaller than the number of items needed. + * + * For examples of how to set up a `git_pool` see `git_pool_init`. + */ +typedef struct { + git_pool_page *open; /* pages with space left */ + git_pool_page *full; /* pages with no space left */ + void *free_list; /* optional: list of freed blocks */ + uint32_t item_size; /* size of single alloc unit in bytes */ + uint32_t page_size; /* size of page in bytes */ + unsigned has_string_alloc : 1; /* was the strdup function used */ + unsigned has_multi_item_alloc : 1; /* was items ever > 1 in malloc */ + unsigned has_large_page_alloc : 1; /* are any pages > page_size */ +} git_pool; + +/** + * Initialize a pool. + * + * To allocation strings, use like this: + * + * git_pool_init(&string_pool, 1, 0); + * my_string = git_pool_strdup(&string_pool, your_string); + * + * To allocate items of fixed size, use like this: + * + * git_pool_init(&pool, sizeof(item), 0); + * git_pool_malloc(&pool, 1, &my_item_ptr); + * + * Of course, you can use this in other ways, but those are the + * two most common patterns. + */ +extern int git_pool_init( + git_pool *pool, uint32_t item_size, uint32_t items_per_page); + +/** + * Free all items in pool + */ +extern void git_pool_clear(git_pool *pool); + +/** + * Allocate space for one or more items from a pool. + */ +extern int git_pool_malloc(git_pool *pool, uint32_t items, void **ptr); + +/** + * Allocate space and duplicate string data into it. + * + * This is allowed only for pools with item_size == sizeof(char) + */ +extern char *git_pool_strndup(git_pool *pool, const char *str, size_t n); + +/** + * Allocate space and duplicate a string into it. + * + * This is allowed only for pools with item_size == sizeof(char) + */ +extern char *git_pool_strdup(git_pool *pool, const char *str); + +/** + * Push a block back onto the free list for the pool. + * + * This is allowed only if the item_size is >= sizeof(void*). + * + * In some cases, it is helpful to "release" an allocated block + * for reuse. Pools don't support a general purpose free, but + * they will keep a simple free blocks linked list provided the + * native block size is large enough to hold a void pointer + */ +extern void git_pool_free(git_pool *pool, void *ptr); + +/* + * Misc utilities + */ + +extern uint32_t git_pool__open_pages(git_pool *pool); + +extern uint32_t git_pool__full_pages(git_pool *pool); + +extern bool git_pool__ptr_in_pool(git_pool *pool, void *ptr); + +extern uint32_t git_pool__system_page_size(void); + +#endif diff --git a/src/refs.c b/src/refs.c index bea1f1724..447f3a7b6 100644 --- a/src/refs.c +++ b/src/refs.c @@ -268,7 +268,7 @@ static int loose_lookup_to_packfile( if (loose_parse_oid(&ref->oid, &ref_file) < 0) { git_buf_free(&ref_file); - free(ref); + git__free(ref); return -1; } diff --git a/src/remote.c b/src/remote.c index b48a23339..54e1146c7 100644 --- a/src/remote.c +++ b/src/remote.c @@ -436,7 +436,7 @@ int git_remote_list(git_strarray *remotes_list, git_repository *repo) size_t i; char *elem; git_vector_foreach(&list, i, elem) { - free(elem); + git__free(elem); } git_vector_free(&list); diff --git a/src/repository.c b/src/repository.c index 88e3a182c..affc0c4c1 100644 --- a/src/repository.c +++ b/src/repository.c @@ -850,7 +850,7 @@ int git_repository_set_workdir(git_repository *repo, const char *workdir) if (git_path_prettify_dir(&path, workdir, NULL) < 0) return -1; - free(repo->workdir); + git__free(repo->workdir); repo->workdir = git_buf_detach(&path); repo->is_bare = 0; diff --git a/tests-clar/core/pool.c b/tests-clar/core/pool.c new file mode 100644 index 000000000..3f1ed8a5a --- /dev/null +++ b/tests-clar/core/pool.c @@ -0,0 +1,85 @@ +#include "clar_libgit2.h" +#include "pool.h" +#include "git2/oid.h" + +void test_core_pool__0(void) +{ + int i; + git_pool p; + void *ptr; + + cl_git_pass(git_pool_init(&p, 1, 4000)); + + for (i = 1; i < 10000; i *= 2) { + cl_git_pass(git_pool_malloc(&p, i, &ptr)); + cl_assert(ptr != NULL); + + cl_assert(git_pool__ptr_in_pool(&p, ptr)); + cl_assert(!git_pool__ptr_in_pool(&p, &i)); + } + + /* 1+2+4+8+16+32+64+128+256+512+1024 -> original block */ + /* 2048 -> 1 block */ + /* 4096 -> 1 block */ + /* 8192 -> 1 block */ + + cl_assert(git_pool__open_pages(&p) + git_pool__full_pages(&p) == 4); + + git_pool_clear(&p); +} + +void test_core_pool__1(void) +{ + int i; + git_pool p; + void *ptr; + + cl_git_pass(git_pool_init(&p, 1, 4000)); + + for (i = 2010; i > 0; i--) + cl_git_pass(git_pool_malloc(&p, i, &ptr)); + + /* with fixed page size, allocation must end up with these values */ + cl_assert(git_pool__open_pages(&p) == 1); + cl_assert(git_pool__full_pages(&p) == 505); + + git_pool_clear(&p); + + cl_git_pass(git_pool_init(&p, 1, 4100)); + + for (i = 2010; i > 0; i--) + cl_git_pass(git_pool_malloc(&p, i, &ptr)); + + /* with fixed page size, allocation must end up with these values */ + cl_assert(git_pool__open_pages(&p) == 1); + cl_assert(git_pool__full_pages(&p) == 492); + + git_pool_clear(&p); +} + +static char to_hex[] = "0123456789abcdef"; + +void test_core_pool__2(void) +{ + git_pool p; + char oid_hex[GIT_OID_HEXSZ]; + git_oid *oid; + int i, j; + + memset(oid_hex, '0', sizeof(oid_hex)); + + cl_git_pass(git_pool_init(&p, sizeof(git_oid), 100)); + + for (i = 1000; i < 10000; i++) { + cl_git_pass(git_pool_malloc(&p, 1, (void **)&oid)); + for (j = 0; j < 8; j++) + oid_hex[j] = to_hex[(i >> (4 * j)) & 0x0f]; + cl_git_pass(git_oid_fromstr(oid, oid_hex)); + } + + /* with fixed page size, allocation must end up with these values */ + cl_assert(git_pool__open_pages(&p) == 0); + cl_assert(git_pool__full_pages(&p) == 90); + + git_pool_clear(&p); +} |