summaryrefslogtreecommitdiff
path: root/src/common/mempool.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/common/mempool.h')
-rw-r--r--src/common/mempool.h345
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