diff options
Diffstat (limited to 'src/common/mempool.h')
-rw-r--r-- | src/common/mempool.h | 345 |
1 files changed, 345 insertions, 0 deletions
diff --git a/src/common/mempool.h b/src/common/mempool.h new file mode 100644 index 0000000..af457b3 --- /dev/null +++ b/src/common/mempool.h @@ -0,0 +1,345 @@ +/* + * UCW Library -- Memory Pools + * + * (c) 1997--2005 Martin Mares <mj@ucw.cz> + * (c) 2007 Pavel Charvat <pchar@ucw.cz> + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +#ifndef _UCW_POOLS_H +#define _UCW_POOLS_H + +#include <string.h> +#include <stdint.h> + +#if __GNUC__ >= 4 +#define LIKE_MALLOC __attribute__((malloc)) /** Function returns a "new" pointer **/ +#define SENTINEL_CHECK __attribute__((sentinel)) /** The last argument must be NULL **/ +#else +#define LIKE_MALLOC +#define SENTINEL_CHECK +#endif + +#define CPU_STRUCT_ALIGN (sizeof(void*)) + +/*** + * [[defs]] + * Definitions + * ----------- + ***/ + +/** + * Memory pool state (see @mp_push(), ...). + * You should use this one as an opaque handle only, the insides are internal. + **/ +struct mempool_state { + unsigned free[2]; + void *last[2]; + struct mempool_state *next; +}; + +/** + * Memory pool. + * You should use this one as an opaque handle only, the insides are internal. + **/ +struct mempool { + struct mempool_state state; + void *unused, *last_big; + unsigned chunk_size, threshold, idx; +}; + +struct mempool_stats { /** Mempool statistics. See @mp_stats(). **/ + uint64_t total_size; /* Real allocated size in bytes */ + unsigned chain_count[3]; /* Number of allocated chunks in small/big/unused chains */ + unsigned chain_size[3]; /* Size of allocated chunks in small/big/unused chains */ +}; + +/*** + * [[basic]] + * Basic manipulation + * ------------------ + ***/ + +/** + * Initialize a given mempool structure. + * @chunk_size must be in the interval `[1, UINT_MAX / 2]`. + * It will allocate memory by this large chunks and take + * memory to satisfy requests from them. + * + * Memory pools can be treated as <<trans:respools,resources>>, see <<trans:res_mempool()>>. + **/ +void mp_init(struct mempool *pool, unsigned chunk_size); + +/** + * Allocate and initialize a new memory pool. + * See @mp_init() for @chunk_size limitations. + * + * The new mempool structure is allocated on the new mempool. + * + * Memory pools can be treated as <<trans:respools,resources>>, see <<trans:res_mempool()>>. + **/ +struct mempool *mp_new(unsigned chunk_size); + +/** + * Cleanup mempool initialized by mp_init or mp_new. + * Frees all the memory allocated by this mempool and, + * if created by @mp_new(), the @pool itself. + **/ +void mp_delete(struct mempool *pool); + +/** + * Frees all data on a memory pool, but leaves it working. + * It can keep some of the chunks allocated to serve + * further allocation requests. Leaves the @pool alive, + * even if it was created with @mp_new(). + **/ +void mp_flush(struct mempool *pool); + +/** + * Compute some statistics for debug purposes. + * See the definition of the <<struct_mempool_stats,mempool_stats structure>>. + **/ +void mp_stats(struct mempool *pool, struct mempool_stats *stats); +uint64_t mp_total_size(struct mempool *pool); /** How many bytes were allocated by the pool. **/ + + +/*** + * [[alloc]] + * Allocation routines + * ------------------- + ***/ + +/* For internal use only, do not call directly */ +void *mp_alloc_internal(struct mempool *pool, unsigned size) LIKE_MALLOC; + +/** + * The function allocates new @size bytes on a given memory pool. + * If the @size is zero, the resulting pointer is undefined, + * but it may be safely reallocated or used as the parameter + * to other functions below. + * + * The resulting pointer is always aligned to a multiple of + * `CPU_STRUCT_ALIGN` bytes and this condition remains true also + * after future reallocations. + **/ +void *mp_alloc(struct mempool *pool, unsigned size); + +/** + * The same as @mp_alloc(), but the result may be unaligned. + **/ +void *mp_alloc_noalign(struct mempool *pool, unsigned size); + +/** + * The same as @mp_alloc(), but fills the newly allocated memory with zeroes. + **/ +void *mp_alloc_zero(struct mempool *pool, unsigned size); + +/** + * Inlined version of @mp_alloc(). + **/ +static inline void *mp_alloc_fast(struct mempool *pool, unsigned size) +{ + unsigned avail = pool->state.free[0] & ~(CPU_STRUCT_ALIGN - 1); + if (size <= avail) + { + pool->state.free[0] = avail - size; + return (uint8_t*)pool->state.last[0] - avail; + } + else + return mp_alloc_internal(pool, size); +} + +/** + * Inlined version of @mp_alloc_noalign(). + **/ +static inline void *mp_alloc_fast_noalign(struct mempool *pool, unsigned size) +{ + if (size <= pool->state.free[0]) + { + void *ptr = (uint8_t*)pool->state.last[0] - pool->state.free[0]; + pool->state.free[0] -= size; + return ptr; + } + else + return mp_alloc_internal(pool, size); +} + +/*** + * [[gbuf]] + * Growing buffers + * --------------- + * + * You do not need to know, how a buffer will need to be large, + * you can grow it incrementally to needed size. You can grow only + * one buffer at a time on a given mempool. + * + * Similar functionality is provided by <<growbuf:,growing buffes>> module. + ***/ + +/* For internal use only, do not call directly */ +void *mp_start_internal(struct mempool *pool, unsigned size) LIKE_MALLOC; +void *mp_grow_internal(struct mempool *pool, unsigned size); +void *mp_spread_internal(struct mempool *pool, void *p, unsigned size); + +static inline unsigned +mp_idx(struct mempool *pool, void *ptr) +{ + return ptr == pool->last_big; +} + +/** + * Open a new growing buffer (at least @size bytes long). + * If the @size is zero, the resulting pointer is undefined, + * but it may be safely reallocated or used as the parameter + * to other functions below. + * + * The resulting pointer is always aligned to a multiple of + * `CPU_STRUCT_ALIGN` bytes and this condition remains true also + * after future reallocations. There is an unaligned version as well. + * + * Keep in mind that you can't make any other pool allocations + * before you "close" the growing buffer with @mp_end(). + */ +void *mp_start(struct mempool *pool, unsigned size); +void *mp_start_noalign(struct mempool *pool, unsigned size); + +/** + * Inlined version of @mp_start(). + **/ +static inline void *mp_start_fast(struct mempool *pool, unsigned size) +{ + unsigned avail = pool->state.free[0] & ~(CPU_STRUCT_ALIGN - 1); + if (size <= avail) + { + pool->idx = 0; + pool->state.free[0] = avail; + return (uint8_t*)pool->state.last[0] - avail; + } + else + return mp_start_internal(pool, size); +} + +/** + * Inlined version of @mp_start_noalign(). + **/ +static inline void *mp_start_fast_noalign(struct mempool *pool, unsigned size) +{ + if (size <= pool->state.free[0]) + { + pool->idx = 0; + return (uint8_t*)pool->state.last[0] - pool->state.free[0]; + } + else + return mp_start_internal(pool, size); +} + +/** + * Return start pointer of the growing buffer allocated by latest @mp_start() or a similar function. + **/ +static inline void *mp_ptr(struct mempool *pool) +{ + return (uint8_t*)pool->state.last[pool->idx] - pool->state.free[pool->idx]; +} + +/** + * Return the number of bytes available for extending the growing buffer. + * (Before a reallocation will be needed). + **/ +static inline unsigned mp_avail(struct mempool *pool) +{ + return pool->state.free[pool->idx]; +} + +/** + * Grow the buffer allocated by @mp_start() to be at least @size bytes long + * (@size may be less than @mp_avail(), even zero). Reallocated buffer may + * change its starting position. The content will be unchanged to the minimum + * of the old and new sizes; newly allocated memory will be uninitialized. + * Multiple calls to mp_grow() have amortized linear cost wrt. the maximum value of @size. */ +static inline void *mp_grow(struct mempool *pool, unsigned size) +{ + return (size <= mp_avail(pool)) ? mp_ptr(pool) : mp_grow_internal(pool, size); +} + +/** + * Grow the buffer by at least one uint8_t-- equivalent to <<mp_grow(),`mp_grow`>>`(@pool, @mp_avail(pool) + 1)`. + **/ +static inline void *mp_expand(struct mempool *pool) +{ + return mp_grow_internal(pool, mp_avail(pool) + 1); +} + +/** + * Ensure that there is at least @size bytes free after @p, + * if not, reallocate and adjust @p. + **/ +static inline void *mp_spread(struct mempool *pool, void *p, unsigned size) +{ + return (((unsigned)((uint8_t*)pool->state.last[pool->idx] - (uint8_t*)p) >= size) ? p : mp_spread_internal(pool, p, size)); +} + +/** + * Close the growing buffer. The @end must point just behind the data, you want to keep + * allocated (so it can be in the interval `[@mp_ptr(@pool), @mp_ptr(@pool) + @mp_avail(@pool)]`). + * Returns a pointer to the beginning of the just closed block. + **/ +static inline void *mp_end(struct mempool *pool, void *end) +{ + void *p = mp_ptr(pool); + pool->state.free[pool->idx] = (uint8_t*)pool->state.last[pool->idx] - (uint8_t*)end; + return p; +} + +/** + * Return size in bytes of the last allocated memory block (with @mp_alloc() or @mp_end()). + **/ +static inline unsigned mp_size(struct mempool *pool, void *ptr) +{ + unsigned idx = mp_idx(pool, ptr); + return ((uint8_t*)pool->state.last[idx] - (uint8_t*)ptr) - pool->state.free[idx]; +} + +/** + * Open the last memory block (allocated with @mp_alloc() or @mp_end()) + * for growing and return its size in bytes. The contents and the start pointer + * remain unchanged. Do not forget to call @mp_end() to close it. + **/ +unsigned mp_open(struct mempool *pool, void *ptr); + +/** + * Inlined version of mp_open(). + **/ +static inline unsigned mp_open_fast(struct mempool *pool, void *ptr) +{ + pool->idx = mp_idx(pool, ptr); + unsigned size = ((uint8_t*)pool->state.last[pool->idx] - (uint8_t*)ptr) - pool->state.free[pool->idx]; + pool->state.free[pool->idx] += size; + return size; +} + +/** + * Reallocate the last memory block (allocated with @mp_alloc() or @mp_end()) + * to the new @size. Behavior is similar to @mp_grow(), but the resulting + * block is closed. + **/ +void *mp_realloc(struct mempool *pool, void *ptr, unsigned size); + +/** + * The same as @mp_realloc(), but fills the additional bytes (if any) with zeroes. + **/ +void *mp_realloc_zero(struct mempool *pool, void *ptr, unsigned size); + +/** + * Inlined version of mp_realloc(). + **/ +static inline void *mp_realloc_fast(struct mempool *pool, void *ptr, unsigned size) +{ + mp_open_fast(pool, ptr); + ptr = mp_grow(pool, size); + mp_end(pool, (uint8_t*)ptr + size); + return ptr; +} + +#endif |