diff options
Diffstat (limited to 'src/common/mempool.c')
-rw-r--r-- | src/common/mempool.c | 628 |
1 files changed, 0 insertions, 628 deletions
diff --git a/src/common/mempool.c b/src/common/mempool.c deleted file mode 100644 index 4389888760..0000000000 --- a/src/common/mempool.c +++ /dev/null @@ -1,628 +0,0 @@ -/* Copyright (c) 2007-2013, The Tor Project, Inc. */ -/* See LICENSE for licensing information */ -#if 1 -/* Tor dependencies */ -#include "orconfig.h" -#endif - -#include <stdlib.h> -#include <string.h> -#include "torint.h" -#include "crypto.h" -#define MEMPOOL_PRIVATE -#include "mempool.h" - -/* OVERVIEW: - * - * This is an implementation of memory pools for Tor cells. It may be - * useful for you too. - * - * Generally, a memory pool is an allocation strategy optimized for large - * numbers of identically-sized objects. Rather than the elaborate arena - * and coalescing strategies you need to get good performance for a - * general-purpose malloc(), pools use a series of large memory "chunks", - * each of which is carved into a bunch of smaller "items" or - * "allocations". - * - * To get decent performance, you need to: - * - Minimize the number of times you hit the underlying allocator. - * - Try to keep accesses as local in memory as possible. - * - Try to keep the common case fast. - * - * Our implementation uses three lists of chunks per pool. Each chunk can - * be either "full" (no more room for items); "empty" (no items); or - * "used" (not full, not empty). There are independent doubly-linked - * lists for each state. - * - * CREDIT: - * - * I wrote this after looking at 3 or 4 other pooling allocators, but - * without copying. The strategy this most resembles (which is funny, - * since that's the one I looked at longest ago) is the pool allocator - * underlying Python's obmalloc code. Major differences from obmalloc's - * pools are: - * - We don't even try to be threadsafe. - * - We only handle objects of one size. - * - Our list of empty chunks is doubly-linked, not singly-linked. - * (This could change pretty easily; it's only doubly-linked for - * consistency.) - * - We keep a list of full chunks (so we can have a "nuke everything" - * function). Obmalloc's pools leave full chunks to float unanchored. - * - * LIMITATIONS: - * - Not even slightly threadsafe. - * - Likes to have lots of items per chunks. - * - One pointer overhead per allocated thing. (The alternative is - * something like glib's use of an RB-tree to keep track of what - * chunk any given piece of memory is in.) - * - Only aligns allocated things to void* level: redefine ALIGNMENT_TYPE - * if you need doubles. - * - Could probably be optimized a bit; the representation contains - * a bit more info than it really needs to have. - */ - -#if 1 -/* Tor dependencies */ -#include "util.h" -#include "compat.h" -#include "torlog.h" -#define ALLOC(x) tor_malloc(x) -#define FREE(x) tor_free(x) -#define ASSERT(x) tor_assert(x) -#undef ALLOC_CAN_RETURN_NULL -#define TOR -/* End Tor dependencies */ -#else -/* If you're not building this as part of Tor, you'll want to define the - * following macros. For now, these should do as defaults. - */ -#include <assert.h> -#define PREDICT_UNLIKELY(x) (x) -#define PREDICT_LIKELY(x) (x) -#define ALLOC(x) malloc(x) -#define FREE(x) free(x) -#define STRUCT_OFFSET(tp, member) \ - ((off_t) (((char*)&((tp*)0)->member)-(char*)0)) -#define ASSERT(x) assert(x) -#define ALLOC_CAN_RETURN_NULL -#endif - -/* Tuning parameters */ -/** Largest type that we need to ensure returned memory items are aligned to. - * Change this to "double" if we need to be safe for structs with doubles. */ -#define ALIGNMENT_TYPE void * -/** Increment that we need to align allocated. */ -#define ALIGNMENT sizeof(ALIGNMENT_TYPE) -/** Largest memory chunk that we should allocate. */ -#define MAX_CHUNK (8*(1L<<20)) -/** Smallest memory chunk size that we should allocate. */ -#define MIN_CHUNK 4096 - -typedef struct mp_allocated_t mp_allocated_t; -typedef struct mp_chunk_t mp_chunk_t; - -/** Holds a single allocated item, allocated as part of a chunk. */ -struct mp_allocated_t { - /** The chunk that this item is allocated in. This adds overhead to each - * allocated item, thus making this implementation inappropriate for - * very small items. */ - mp_chunk_t *in_chunk; - union { - /** If this item is free, the next item on the free list. */ - mp_allocated_t *next_free; - /** If this item is not free, the actual memory contents of this item. - * (Not actual size.) */ - char mem[1]; - /** An extra element to the union to insure correct alignment. */ - ALIGNMENT_TYPE dummy_; - } u; -}; - -/** 'Magic' value used to detect memory corruption. */ -#define MP_CHUNK_MAGIC 0x09870123 - -/** A chunk of memory. Chunks come from malloc; we use them */ -struct mp_chunk_t { - unsigned long magic; /**< Must be MP_CHUNK_MAGIC if this chunk is valid. */ - mp_chunk_t *next; /**< The next free, used, or full chunk in sequence. */ - mp_chunk_t *prev; /**< The previous free, used, or full chunk in sequence. */ - mp_pool_t *pool; /**< The pool that this chunk is part of. */ - /** First free item in the freelist for this chunk. Note that this may be - * NULL even if this chunk is not at capacity: if so, the free memory at - * next_mem has not yet been carved into items. - */ - mp_allocated_t *first_free; - int n_allocated; /**< Number of currently allocated items in this chunk. */ - int capacity; /**< Number of items that can be fit into this chunk. */ - size_t mem_size; /**< Number of usable bytes in mem. */ - char *next_mem; /**< Pointer into part of <b>mem</b> not yet carved up. */ - char mem[FLEXIBLE_ARRAY_MEMBER]; /**< Storage for this chunk. */ -}; - -/** Number of extra bytes needed beyond mem_size to allocate a chunk. */ -#define CHUNK_OVERHEAD STRUCT_OFFSET(mp_chunk_t, mem[0]) - -/** Given a pointer to a mp_allocated_t, return a pointer to the memory - * item it holds. */ -#define A2M(a) (&(a)->u.mem) -/** Given a pointer to a memory_item_t, return a pointer to its enclosing - * mp_allocated_t. */ -#define M2A(p) ( ((char*)p) - STRUCT_OFFSET(mp_allocated_t, u.mem) ) - -#ifdef ALLOC_CAN_RETURN_NULL -/** If our ALLOC() macro can return NULL, check whether <b>x</b> is NULL, - * and if so, return NULL. */ -#define CHECK_ALLOC(x) \ - if (PREDICT_UNLIKELY(!x)) { return NULL; } -#else -/** If our ALLOC() macro can't return NULL, do nothing. */ -#define CHECK_ALLOC(x) -#endif - -/** Helper: Allocate and return a new memory chunk for <b>pool</b>. Does not - * link the chunk into any list. */ -static mp_chunk_t * -mp_chunk_new(mp_pool_t *pool) -{ - size_t sz = pool->new_chunk_capacity * pool->item_alloc_size; - mp_chunk_t *chunk = ALLOC(CHUNK_OVERHEAD + sz); - -#ifdef MEMPOOL_STATS - ++pool->total_chunks_allocated; -#endif - CHECK_ALLOC(chunk); - memset(chunk, 0, sizeof(mp_chunk_t)); /* Doesn't clear the whole thing. */ - chunk->magic = MP_CHUNK_MAGIC; - chunk->capacity = pool->new_chunk_capacity; - chunk->mem_size = sz; - chunk->next_mem = chunk->mem; - chunk->pool = pool; - return chunk; -} - -/** Take a <b>chunk</b> that has just been allocated or removed from - * <b>pool</b>'s empty chunk list, and add it to the head of the used chunk - * list. */ -static INLINE void -add_newly_used_chunk_to_used_list(mp_pool_t *pool, mp_chunk_t *chunk) -{ - chunk->next = pool->used_chunks; - if (chunk->next) - chunk->next->prev = chunk; - pool->used_chunks = chunk; - ASSERT(!chunk->prev); -} - -/** Return a newly allocated item from <b>pool</b>. */ -void * -mp_pool_get(mp_pool_t *pool) -{ - mp_chunk_t *chunk; - mp_allocated_t *allocated; - - if (PREDICT_LIKELY(pool->used_chunks != NULL)) { - /* Common case: there is some chunk that is neither full nor empty. Use - * that one. (We can't use the full ones, obviously, and we should fill - * up the used ones before we start on any empty ones. */ - chunk = pool->used_chunks; - - } else if (pool->empty_chunks) { - /* We have no used chunks, but we have an empty chunk that we haven't - * freed yet: use that. (We pull from the front of the list, which should - * get us the most recently emptied chunk.) */ - chunk = pool->empty_chunks; - - /* Remove the chunk from the empty list. */ - pool->empty_chunks = chunk->next; - if (chunk->next) - chunk->next->prev = NULL; - - /* Put the chunk on the 'used' list*/ - add_newly_used_chunk_to_used_list(pool, chunk); - - ASSERT(!chunk->prev); - --pool->n_empty_chunks; - if (pool->n_empty_chunks < pool->min_empty_chunks) - pool->min_empty_chunks = pool->n_empty_chunks; - } else { - /* We have no used or empty chunks: allocate a new chunk. */ - chunk = mp_chunk_new(pool); - CHECK_ALLOC(chunk); - - /* Add the new chunk to the used list. */ - add_newly_used_chunk_to_used_list(pool, chunk); - } - - ASSERT(chunk->n_allocated < chunk->capacity); - - if (chunk->first_free) { - /* If there's anything on the chunk's freelist, unlink it and use it. */ - allocated = chunk->first_free; - chunk->first_free = allocated->u.next_free; - allocated->u.next_free = NULL; /* For debugging; not really needed. */ - ASSERT(allocated->in_chunk == chunk); - } else { - /* Otherwise, the chunk had better have some free space left on it. */ - ASSERT(chunk->next_mem + pool->item_alloc_size <= - chunk->mem + chunk->mem_size); - - /* Good, it did. Let's carve off a bit of that free space, and use - * that. */ - allocated = (void*)chunk->next_mem; - chunk->next_mem += pool->item_alloc_size; - allocated->in_chunk = chunk; - allocated->u.next_free = NULL; /* For debugging; not really needed. */ - } - - ++chunk->n_allocated; -#ifdef MEMPOOL_STATS - ++pool->total_items_allocated; -#endif - - if (PREDICT_UNLIKELY(chunk->n_allocated == chunk->capacity)) { - /* This chunk just became full. */ - ASSERT(chunk == pool->used_chunks); - ASSERT(chunk->prev == NULL); - - /* Take it off the used list. */ - pool->used_chunks = chunk->next; - if (chunk->next) - chunk->next->prev = NULL; - - /* Put it on the full list. */ - chunk->next = pool->full_chunks; - if (chunk->next) - chunk->next->prev = chunk; - pool->full_chunks = chunk; - } - /* And return the memory portion of the mp_allocated_t. */ - return A2M(allocated); -} - -/** Return an allocated memory item to its memory pool. */ -void -mp_pool_release(void *item) -{ - mp_allocated_t *allocated = (void*) M2A(item); - mp_chunk_t *chunk = allocated->in_chunk; - - ASSERT(chunk); - ASSERT(chunk->magic == MP_CHUNK_MAGIC); - ASSERT(chunk->n_allocated > 0); - - allocated->u.next_free = chunk->first_free; - chunk->first_free = allocated; - - if (PREDICT_UNLIKELY(chunk->n_allocated == chunk->capacity)) { - /* This chunk was full and is about to be used. */ - mp_pool_t *pool = chunk->pool; - /* unlink from the full list */ - if (chunk->prev) - chunk->prev->next = chunk->next; - if (chunk->next) - chunk->next->prev = chunk->prev; - if (chunk == pool->full_chunks) - pool->full_chunks = chunk->next; - - /* link to the used list. */ - chunk->next = pool->used_chunks; - chunk->prev = NULL; - if (chunk->next) - chunk->next->prev = chunk; - pool->used_chunks = chunk; - } else if (PREDICT_UNLIKELY(chunk->n_allocated == 1)) { - /* This was used and is about to be empty. */ - mp_pool_t *pool = chunk->pool; - - /* Unlink from the used list */ - if (chunk->prev) - chunk->prev->next = chunk->next; - if (chunk->next) - chunk->next->prev = chunk->prev; - if (chunk == pool->used_chunks) - pool->used_chunks = chunk->next; - - /* Link to the empty list */ - chunk->next = pool->empty_chunks; - chunk->prev = NULL; - if (chunk->next) - chunk->next->prev = chunk; - pool->empty_chunks = chunk; - - /* Reset the guts of this chunk to defragment it, in case it gets - * used again. */ - chunk->first_free = NULL; - chunk->next_mem = chunk->mem; - - ++pool->n_empty_chunks; - } - --chunk->n_allocated; -} - -/** Allocate a new memory pool to hold items of size <b>item_size</b>. We'll - * try to fit about <b>chunk_capacity</b> bytes in each chunk. */ -mp_pool_t * -mp_pool_new(size_t item_size, size_t chunk_capacity) -{ - mp_pool_t *pool; - size_t alloc_size, new_chunk_cap; - - tor_assert(item_size < SIZE_T_CEILING); - tor_assert(chunk_capacity < SIZE_T_CEILING); - tor_assert(SIZE_T_CEILING / item_size > chunk_capacity); - - pool = ALLOC(sizeof(mp_pool_t)); - CHECK_ALLOC(pool); - memset(pool, 0, sizeof(mp_pool_t)); - - /* First, we figure out how much space to allow per item. We'll want to - * use make sure we have enough for the overhead plus the item size. */ - alloc_size = (size_t)(STRUCT_OFFSET(mp_allocated_t, u.mem) + item_size); - /* If the item_size is less than sizeof(next_free), we need to make - * the allocation bigger. */ - if (alloc_size < sizeof(mp_allocated_t)) - alloc_size = sizeof(mp_allocated_t); - - /* If we're not an even multiple of ALIGNMENT, round up. */ - if (alloc_size % ALIGNMENT) { - alloc_size = alloc_size + ALIGNMENT - (alloc_size % ALIGNMENT); - } - if (alloc_size < ALIGNMENT) - alloc_size = ALIGNMENT; - ASSERT((alloc_size % ALIGNMENT) == 0); - - /* Now we figure out how many items fit in each chunk. We need to fit at - * least 2 items per chunk. No chunk can be more than MAX_CHUNK bytes long, - * or less than MIN_CHUNK. */ - if (chunk_capacity > MAX_CHUNK) - chunk_capacity = MAX_CHUNK; - /* Try to be around a power of 2 in size, since that's what allocators like - * handing out. 512K-1 byte is a lot better than 512K+1 byte. */ - chunk_capacity = (size_t) round_to_power_of_2(chunk_capacity); - while (chunk_capacity < alloc_size * 2 + CHUNK_OVERHEAD) - chunk_capacity *= 2; - if (chunk_capacity < MIN_CHUNK) - chunk_capacity = MIN_CHUNK; - - new_chunk_cap = (chunk_capacity-CHUNK_OVERHEAD) / alloc_size; - tor_assert(new_chunk_cap < INT_MAX); - pool->new_chunk_capacity = (int)new_chunk_cap; - - pool->item_alloc_size = alloc_size; - - log_debug(LD_MM, "Capacity is %lu, item size is %lu, alloc size is %lu", - (unsigned long)pool->new_chunk_capacity, - (unsigned long)pool->item_alloc_size, - (unsigned long)(pool->new_chunk_capacity*pool->item_alloc_size)); - - return pool; -} - -/** Helper function for qsort: used to sort pointers to mp_chunk_t into - * descending order of fullness. */ -static int -mp_pool_sort_used_chunks_helper(const void *_a, const void *_b) -{ - mp_chunk_t *a = *(mp_chunk_t**)_a; - mp_chunk_t *b = *(mp_chunk_t**)_b; - return b->n_allocated - a->n_allocated; -} - -/** Sort the used chunks in <b>pool</b> into descending order of fullness, - * so that we preferentially fill up mostly full chunks before we make - * nearly empty chunks less nearly empty. */ -static void -mp_pool_sort_used_chunks(mp_pool_t *pool) -{ - int i, n=0, inverted=0; - mp_chunk_t **chunks, *chunk; - for (chunk = pool->used_chunks; chunk; chunk = chunk->next) { - ++n; - if (chunk->next && chunk->next->n_allocated > chunk->n_allocated) - ++inverted; - } - if (!inverted) - return; - //printf("Sort %d/%d\n",inverted,n); - chunks = ALLOC(sizeof(mp_chunk_t *)*n); -#ifdef ALLOC_CAN_RETURN_NULL - if (PREDICT_UNLIKELY(!chunks)) return; -#endif - for (i=0,chunk = pool->used_chunks; chunk; chunk = chunk->next) - chunks[i++] = chunk; - qsort(chunks, n, sizeof(mp_chunk_t *), mp_pool_sort_used_chunks_helper); - pool->used_chunks = chunks[0]; - chunks[0]->prev = NULL; - for (i=1;i<n;++i) { - chunks[i-1]->next = chunks[i]; - chunks[i]->prev = chunks[i-1]; - } - chunks[n-1]->next = NULL; - FREE(chunks); - mp_pool_assert_ok(pool); -} - -/** If there are more than <b>n</b> empty chunks in <b>pool</b>, free the - * excess ones that have been empty for the longest. If - * <b>keep_recently_used</b> is true, do not free chunks unless they have been - * empty since the last call to this function. - **/ -void -mp_pool_clean(mp_pool_t *pool, int n_to_keep, int keep_recently_used) -{ - mp_chunk_t *chunk, **first_to_free; - - mp_pool_sort_used_chunks(pool); - ASSERT(n_to_keep >= 0); - - if (keep_recently_used) { - int n_recently_used = pool->n_empty_chunks - pool->min_empty_chunks; - if (n_to_keep < n_recently_used) - n_to_keep = n_recently_used; - } - - ASSERT(n_to_keep >= 0); - - first_to_free = &pool->empty_chunks; - while (*first_to_free && n_to_keep > 0) { - first_to_free = &(*first_to_free)->next; - --n_to_keep; - } - if (!*first_to_free) { - pool->min_empty_chunks = pool->n_empty_chunks; - return; - } - - chunk = *first_to_free; - while (chunk) { - mp_chunk_t *next = chunk->next; - chunk->magic = 0xdeadbeef; - FREE(chunk); -#ifdef MEMPOOL_STATS - ++pool->total_chunks_freed; -#endif - --pool->n_empty_chunks; - chunk = next; - } - - pool->min_empty_chunks = pool->n_empty_chunks; - *first_to_free = NULL; -} - -/** Helper: Given a list of chunks, free all the chunks in the list. */ -static void -destroy_chunks(mp_chunk_t *chunk) -{ - mp_chunk_t *next; - while (chunk) { - chunk->magic = 0xd3adb33f; - next = chunk->next; - FREE(chunk); - chunk = next; - } -} - -/** Free all space held in <b>pool</b> This makes all pointers returned from - * mp_pool_get(<b>pool</b>) invalid. */ -void -mp_pool_destroy(mp_pool_t *pool) -{ - destroy_chunks(pool->empty_chunks); - destroy_chunks(pool->used_chunks); - destroy_chunks(pool->full_chunks); - memwipe(pool, 0xe0, sizeof(mp_pool_t)); - FREE(pool); -} - -/** Helper: make sure that a given chunk list is not corrupt. */ -static int -assert_chunks_ok(mp_pool_t *pool, mp_chunk_t *chunk, int empty, int full) -{ - mp_allocated_t *allocated; - int n = 0; - if (chunk) - ASSERT(chunk->prev == NULL); - - while (chunk) { - n++; - ASSERT(chunk->magic == MP_CHUNK_MAGIC); - ASSERT(chunk->pool == pool); - for (allocated = chunk->first_free; allocated; - allocated = allocated->u.next_free) { - ASSERT(allocated->in_chunk == chunk); - } - if (empty) - ASSERT(chunk->n_allocated == 0); - else if (full) - ASSERT(chunk->n_allocated == chunk->capacity); - else - ASSERT(chunk->n_allocated > 0 && chunk->n_allocated < chunk->capacity); - - ASSERT(chunk->capacity == pool->new_chunk_capacity); - - ASSERT(chunk->mem_size == - pool->new_chunk_capacity * pool->item_alloc_size); - - ASSERT(chunk->next_mem >= chunk->mem && - chunk->next_mem <= chunk->mem + chunk->mem_size); - - if (chunk->next) - ASSERT(chunk->next->prev == chunk); - - chunk = chunk->next; - } - return n; -} - -/** Fail with an assertion if <b>pool</b> is not internally consistent. */ -void -mp_pool_assert_ok(mp_pool_t *pool) -{ - int n_empty; - - n_empty = assert_chunks_ok(pool, pool->empty_chunks, 1, 0); - assert_chunks_ok(pool, pool->full_chunks, 0, 1); - assert_chunks_ok(pool, pool->used_chunks, 0, 0); - - ASSERT(pool->n_empty_chunks == n_empty); -} - -#ifdef TOR -/** Dump information about <b>pool</b>'s memory usage to the Tor log at level - * <b>severity</b>. */ -/*FFFF uses Tor logging functions. */ -void -mp_pool_log_status(mp_pool_t *pool, int severity) -{ - uint64_t bytes_used = 0; - uint64_t bytes_allocated = 0; - uint64_t bu = 0, ba = 0; - mp_chunk_t *chunk; - int n_full = 0, n_used = 0; - - ASSERT(pool); - - for (chunk = pool->empty_chunks; chunk; chunk = chunk->next) { - bytes_allocated += chunk->mem_size; - } - log_fn(severity, LD_MM, U64_FORMAT" bytes in %d empty chunks", - U64_PRINTF_ARG(bytes_allocated), pool->n_empty_chunks); - for (chunk = pool->used_chunks; chunk; chunk = chunk->next) { - ++n_used; - bu += chunk->n_allocated * pool->item_alloc_size; - ba += chunk->mem_size; - log_fn(severity, LD_MM, " used chunk: %d items allocated", - chunk->n_allocated); - } - log_fn(severity, LD_MM, U64_FORMAT"/"U64_FORMAT - " bytes in %d partially full chunks", - U64_PRINTF_ARG(bu), U64_PRINTF_ARG(ba), n_used); - bytes_used += bu; - bytes_allocated += ba; - bu = ba = 0; - for (chunk = pool->full_chunks; chunk; chunk = chunk->next) { - ++n_full; - bu += chunk->n_allocated * pool->item_alloc_size; - ba += chunk->mem_size; - } - log_fn(severity, LD_MM, U64_FORMAT"/"U64_FORMAT - " bytes in %d full chunks", - U64_PRINTF_ARG(bu), U64_PRINTF_ARG(ba), n_full); - bytes_used += bu; - bytes_allocated += ba; - - log_fn(severity, LD_MM, "Total: "U64_FORMAT"/"U64_FORMAT" bytes allocated " - "for cell pools are full.", - U64_PRINTF_ARG(bytes_used), U64_PRINTF_ARG(bytes_allocated)); - -#ifdef MEMPOOL_STATS - log_fn(severity, LD_MM, U64_FORMAT" cell allocations ever; " - U64_FORMAT" chunk allocations ever; " - U64_FORMAT" chunk frees ever.", - U64_PRINTF_ARG(pool->total_items_allocated), - U64_PRINTF_ARG(pool->total_chunks_allocated), - U64_PRINTF_ARG(pool->total_chunks_freed)); -#endif -} -#endif - |