From ad44b775e30b2740d25bb8330c9e8879f1ec5533 Mon Sep 17 00:00:00 2001 From: Marek Olšák Date: Mon, 19 Jul 2010 11:04:30 +0200 Subject: util: add a memory pool for equally sized memory allocations malloc/free are in O(1). --- src/gallium/auxiliary/util/u_mempool.c | 173 +++++++++++++++++++++++++++++++++ 1 file changed, 173 insertions(+) create mode 100644 src/gallium/auxiliary/util/u_mempool.c (limited to 'src/gallium/auxiliary/util/u_mempool.c') diff --git a/src/gallium/auxiliary/util/u_mempool.c b/src/gallium/auxiliary/util/u_mempool.c new file mode 100644 index 0000000000..da1cc702ec --- /dev/null +++ b/src/gallium/auxiliary/util/u_mempool.c @@ -0,0 +1,173 @@ +/* + * Copyright 2010 Marek Olšák + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * on the rights to use, copy, modify, merge, publish, distribute, sub + * license, and/or sell copies of the Software, and to permit persons to whom + * the Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL + * THE AUTHOR(S) AND/OR THEIR SUPPLIERS BE LIABLE FOR ANY CLAIM, + * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR + * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE + * USE OR OTHER DEALINGS IN THE SOFTWARE. */ + +#include "util/u_mempool.h" + +#include "util/u_math.h" +#include "util/u_memory.h" +#include "util/u_simple_list.h" + +#include + +#define UTIL_MEMPOOL_MAGIC 0xcafe4321 + +struct util_mempool_block_body {}; + +/* The block is either allocated memory or free space. */ +struct util_mempool_block { + /* The header. */ + /* The first next free block. */ + struct util_mempool_block *next_free; + + intptr_t magic; + + /* The block begins here. */ + struct util_mempool_block_body body; + + /* Memory after the last member is dedicated to the block itself. + * The allocated size is always larger than this structure. */ +}; + +static struct util_mempool_block * +util_mempool_get_block(struct util_mempool *pool, + struct util_mempool_page *page, unsigned index) +{ + return (struct util_mempool_block*) + ((uint8_t*)&page->body + (pool->block_size * index)); +} + +static void util_mempool_add_new_page(struct util_mempool *pool) +{ + struct util_mempool_page *page; + struct util_mempool_block *block; + int i; + + page = MALLOC(pool->page_size); + insert_at_tail(&pool->list, page); + + /* Mark all blocks as free. */ + for (i = 0; i < pool->num_blocks-1; i++) { + block = util_mempool_get_block(pool, page, i); + block->next_free = util_mempool_get_block(pool, page, i+1); + block->magic = UTIL_MEMPOOL_MAGIC; + } + + block = util_mempool_get_block(pool, page, pool->num_blocks-1); + block->next_free = pool->first_free; + pool->first_free = util_mempool_get_block(pool, page, 0); + pool->num_pages++; + +#if 0 + fprintf(stderr, "New page! Num of pages: %i\n", pool->num_pages); +#endif +} + +static void *util_mempool_malloc_st(struct util_mempool *pool) +{ + struct util_mempool_block *block; + + if (!pool->first_free) + util_mempool_add_new_page(pool); + + block = pool->first_free; + assert(block->magic == UTIL_MEMPOOL_MAGIC); + pool->first_free = block->next_free; + + return &block->body; +} + +static void util_mempool_free_st(struct util_mempool *pool, void *ptr) +{ + struct util_mempool_block dummy; + struct util_mempool_block *block = + (struct util_mempool_block*) + ((uint8_t*)ptr - ((uint8_t*)&dummy.body - (uint8_t*)&dummy)); + + assert(block->magic == UTIL_MEMPOOL_MAGIC); + block->next_free = pool->first_free; + pool->first_free = block; +} + +static void *util_mempool_malloc_mt(struct util_mempool *pool) +{ + void *mem; + + pipe_mutex_lock(pool->mutex); + mem = util_mempool_malloc_st(pool); + pipe_mutex_unlock(pool->mutex); + return mem; +} + +static void util_mempool_free_mt(struct util_mempool *pool, void *ptr) +{ + pipe_mutex_lock(pool->mutex); + util_mempool_free_st(pool, ptr); + pipe_mutex_unlock(pool->mutex); +} + +void util_mempool_set_thread_safety(struct util_mempool *pool, + enum util_mempool_threading threading) +{ + pool->threading = threading; + + if (threading) { + pipe_mutex_init(pool->mutex); + pool->malloc = util_mempool_malloc_mt; + pool->free = util_mempool_free_mt; + } else { + pool->malloc = util_mempool_malloc_st; + pool->free = util_mempool_free_st; + } +} + +void util_mempool_create(struct util_mempool *pool, + unsigned item_size, + unsigned num_blocks, + enum util_mempool_threading threading) +{ + item_size = align(item_size, sizeof(intptr_t)); + + pool->num_pages = 0; + pool->num_blocks = num_blocks; + pool->block_size = sizeof(struct util_mempool_block) + item_size; + pool->block_size = align(pool->block_size, sizeof(intptr_t)); + pool->page_size = sizeof(struct util_mempool_page) + + num_blocks * pool->block_size; + pool->first_free = NULL; + + make_empty_list(&pool->list); + + util_mempool_set_thread_safety(pool, threading); +} + +void util_mempool_destroy(struct util_mempool *pool) +{ + struct util_mempool_page *page, *temp; + + foreach_s(page, temp, &pool->list) { + remove_from_list(page); + FREE(page); + } + + if (pool->threading) + pipe_mutex_destroy(pool->mutex); +} -- cgit v1.2.3 From 369e9272def1d41bec56213512c1966071f54f93 Mon Sep 17 00:00:00 2001 From: Brian Paul Date: Mon, 19 Jul 2010 10:50:08 -0600 Subject: util: add dummy field to empty structure types Empty structure types aren't allowed with MSVC. I haven't tested this change. Hope I haven't broken it... --- src/gallium/auxiliary/util/u_mempool.c | 2 +- src/gallium/auxiliary/util/u_mempool.h | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) (limited to 'src/gallium/auxiliary/util/u_mempool.c') diff --git a/src/gallium/auxiliary/util/u_mempool.c b/src/gallium/auxiliary/util/u_mempool.c index da1cc702ec..c4bb2658f2 100644 --- a/src/gallium/auxiliary/util/u_mempool.c +++ b/src/gallium/auxiliary/util/u_mempool.c @@ -30,7 +30,7 @@ #define UTIL_MEMPOOL_MAGIC 0xcafe4321 -struct util_mempool_block_body {}; +struct util_mempool_block_body { char dummy; }; /* The block is either allocated memory or free space. */ struct util_mempool_block { diff --git a/src/gallium/auxiliary/util/u_mempool.h b/src/gallium/auxiliary/util/u_mempool.h index b8d2aaefb6..c96f9b696b 100644 --- a/src/gallium/auxiliary/util/u_mempool.h +++ b/src/gallium/auxiliary/util/u_mempool.h @@ -43,7 +43,7 @@ enum util_mempool_threading { UTIL_MEMPOOL_MULTITHREADED = TRUE }; -struct util_mempool_page_body {}; +struct util_mempool_page_body { char dummy; }; /* The page is an array of blocks (allocations). */ struct util_mempool_page { -- cgit v1.2.3 From fd03dd203f19301520d16de58552cc2fec5e6115 Mon Sep 17 00:00:00 2001 From: Marek Olšák Date: Mon, 19 Jul 2010 18:08:53 +0200 Subject: util: remove the dummy field in mempool It should allocate less memory now. --- src/gallium/auxiliary/util/u_mempool.c | 13 ++++--------- src/gallium/auxiliary/util/u_mempool.h | 5 ----- 2 files changed, 4 insertions(+), 14 deletions(-) (limited to 'src/gallium/auxiliary/util/u_mempool.c') diff --git a/src/gallium/auxiliary/util/u_mempool.c b/src/gallium/auxiliary/util/u_mempool.c index c4bb2658f2..0ce4b6cf1a 100644 --- a/src/gallium/auxiliary/util/u_mempool.c +++ b/src/gallium/auxiliary/util/u_mempool.c @@ -30,8 +30,6 @@ #define UTIL_MEMPOOL_MAGIC 0xcafe4321 -struct util_mempool_block_body { char dummy; }; - /* The block is either allocated memory or free space. */ struct util_mempool_block { /* The header. */ @@ -40,9 +38,6 @@ struct util_mempool_block { intptr_t magic; - /* The block begins here. */ - struct util_mempool_block_body body; - /* Memory after the last member is dedicated to the block itself. * The allocated size is always larger than this structure. */ }; @@ -52,7 +47,8 @@ util_mempool_get_block(struct util_mempool *pool, struct util_mempool_page *page, unsigned index) { return (struct util_mempool_block*) - ((uint8_t*)&page->body + (pool->block_size * index)); + ((uint8_t*)page + sizeof(struct util_mempool_page) + + (pool->block_size * index)); } static void util_mempool_add_new_page(struct util_mempool *pool) @@ -92,15 +88,14 @@ static void *util_mempool_malloc_st(struct util_mempool *pool) assert(block->magic == UTIL_MEMPOOL_MAGIC); pool->first_free = block->next_free; - return &block->body; + return (uint8_t*)block + sizeof(struct util_mempool_block); } static void util_mempool_free_st(struct util_mempool *pool, void *ptr) { - struct util_mempool_block dummy; struct util_mempool_block *block = (struct util_mempool_block*) - ((uint8_t*)ptr - ((uint8_t*)&dummy.body - (uint8_t*)&dummy)); + ((uint8_t*)ptr - sizeof(struct util_mempool_block)); assert(block->magic == UTIL_MEMPOOL_MAGIC); block->next_free = pool->first_free; diff --git a/src/gallium/auxiliary/util/u_mempool.h b/src/gallium/auxiliary/util/u_mempool.h index c96f9b696b..a5b5d6a9b7 100644 --- a/src/gallium/auxiliary/util/u_mempool.h +++ b/src/gallium/auxiliary/util/u_mempool.h @@ -43,16 +43,11 @@ enum util_mempool_threading { UTIL_MEMPOOL_MULTITHREADED = TRUE }; -struct util_mempool_page_body { char dummy; }; - /* The page is an array of blocks (allocations). */ struct util_mempool_page { /* The header (linked-list pointers). */ struct util_mempool_page *prev, *next; - /* The page begins here. */ - struct util_mempool_page_body body; - /* Memory after the last member is dedicated to the page itself. * The allocated size is always larger than this structure. */ }; -- cgit v1.2.3 From bdde9d2fcead2e49985f4cd1c73ad4aae5b2878f Mon Sep 17 00:00:00 2001 From: Marek Olšák Date: Mon, 19 Jul 2010 23:26:17 +0200 Subject: util: mempool: initialize last block's magic number in a page --- src/gallium/auxiliary/util/u_mempool.c | 1 + 1 file changed, 1 insertion(+) (limited to 'src/gallium/auxiliary/util/u_mempool.c') diff --git a/src/gallium/auxiliary/util/u_mempool.c b/src/gallium/auxiliary/util/u_mempool.c index 0ce4b6cf1a..84e2a34acc 100644 --- a/src/gallium/auxiliary/util/u_mempool.c +++ b/src/gallium/auxiliary/util/u_mempool.c @@ -69,6 +69,7 @@ static void util_mempool_add_new_page(struct util_mempool *pool) block = util_mempool_get_block(pool, page, pool->num_blocks-1); block->next_free = pool->first_free; + block->magic = UTIL_MEMPOOL_MAGIC; pool->first_free = util_mempool_get_block(pool, page, 0); pool->num_pages++; -- cgit v1.2.3 From d26fb6916931f10e029429ecbf46e86484e7e956 Mon Sep 17 00:00:00 2001 From: Marek Olšák Date: Mon, 26 Jul 2010 14:53:06 +0200 Subject: util: fix mutex leaks in mempool --- src/gallium/auxiliary/util/u_mempool.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'src/gallium/auxiliary/util/u_mempool.c') diff --git a/src/gallium/auxiliary/util/u_mempool.c b/src/gallium/auxiliary/util/u_mempool.c index 84e2a34acc..6b1a72a7f6 100644 --- a/src/gallium/auxiliary/util/u_mempool.c +++ b/src/gallium/auxiliary/util/u_mempool.c @@ -126,7 +126,6 @@ void util_mempool_set_thread_safety(struct util_mempool *pool, pool->threading = threading; if (threading) { - pipe_mutex_init(pool->mutex); pool->malloc = util_mempool_malloc_mt; pool->free = util_mempool_free_mt; } else { @@ -152,6 +151,8 @@ void util_mempool_create(struct util_mempool *pool, make_empty_list(&pool->list); + pipe_mutex_init(pool->mutex); + util_mempool_set_thread_safety(pool, threading); } -- cgit v1.2.3 From a3a42e46965221b8f8249f0f1076fc3544b68d0e Mon Sep 17 00:00:00 2001 From: Marek Olšák Date: Mon, 26 Jul 2010 14:56:48 +0200 Subject: util: fix another mutex leak in mempool By fixing one, I introduced another. Crap. --- src/gallium/auxiliary/util/u_mempool.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'src/gallium/auxiliary/util/u_mempool.c') diff --git a/src/gallium/auxiliary/util/u_mempool.c b/src/gallium/auxiliary/util/u_mempool.c index 6b1a72a7f6..1f336b39a1 100644 --- a/src/gallium/auxiliary/util/u_mempool.c +++ b/src/gallium/auxiliary/util/u_mempool.c @@ -165,6 +165,5 @@ void util_mempool_destroy(struct util_mempool *pool) FREE(page); } - if (pool->threading) - pipe_mutex_destroy(pool->mutex); + pipe_mutex_destroy(pool->mutex); } -- cgit v1.2.3