lib/mempool.h

   1 /*
   2  *      UCW Library -- Memory Pools
   3  *
   4  *      (c) 1997--2005 Martin Mares <mj@ucw.cz>
   5  *      (c) 2007 Pavel Charvat <pchar@ucw.cz>
   6  *
   7  *      This software may be freely distributed and used according to the terms
   8  *      of the GNU Lesser General Public License.
   9  */
  10
  11 #ifndef _UCW_POOLS_H
  12 #define _UCW_POOLS_H
  13
  14 /* Memory pool state (see mp_push(), ...) */
  15 struct mempool_state {
  16   uns free[2];
  17   void *last[2];
  18   struct mempool_state *next;
  19 };
  20
  21 /* Memory pool */
  22 struct mempool {
  23   struct mempool_state state;
  24   void *unused, *last_big;
  25   uns chunk_size, threshold, idx;
  26 };
  27
  28 /* Statistics (see mp_stats()) */
  29 struct mempool_stats {
  30   u64 total_size;                       /* Real allocated size in bytes */
  31   uns chain_count[3];                   /* Number of allocated chunks in small/big/unused chains */
  32   uns chain_size[3];                    /* Size of allocated chunks in small/big/unused chains */
  33 };
  34
  35 /* Initialize a given mempool structure. Chunk size must be in the interval [1, UINT_MAX / 2] */
  36 void mp_init(struct mempool *pool, uns chunk_size);
  37
  38 /* Allocate and initialize a new memory pool. See mp_init for chunk size limitations. */
  39 struct mempool *mp_new(uns chunk_size);
  40
  41 /* Cleanup mempool initialized by mp_init or mp_new */
  42 void mp_delete(struct mempool *pool);
  43
  44 /* Free all data on a memory pool (saves some empty chunks for later allocations) */
  45 void mp_flush(struct mempool *pool);
  46
  47 /* Compute some statistics for debug purposes. See the definition of the mempool_stats structure. */
  48 void mp_stats(struct mempool *pool, struct mempool_stats *stats);
  49 u64 mp_total_size(struct mempool *pool);
  50
  51
  52 /*** Allocation routines ***/
  53
  54 /* For internal use only, do not call directly */
  55 void *mp_alloc_internal(struct mempool *pool, uns size) LIKE_MALLOC;
  56
  57 /* The function allocates new <size> bytes on a given memory pool.
  58  * If the <size> is zero, the resulting pointer is undefined,
  59  * but it may be safely reallocated or used as the parameter
  60  * to other functions below.
  61  *
  62  * The resulting pointer is always aligned to a multiple of
  63  * CPU_STRUCT_ALIGN bytes and this condition remains true also
  64  * after future reallocations.
  65  */
  66 void *mp_alloc(struct mempool *pool, uns size);
  67
  68 /* The same as mp_alloc, but the result may not be aligned */
  69 void *mp_alloc_noalign(struct mempool *pool, uns size);
  70
  71 /* The same as mp_alloc, but fills the newly allocated data with zeroes */
  72 void *mp_alloc_zero(struct mempool *pool, uns size);
  73
  74 /* Inlined version of mp_alloc() */
  75 static inline void *
  76 mp_alloc_fast(struct mempool *pool, uns size)
  77 {
  78   uns avail = pool->state.free[0] & ~(CPU_STRUCT_ALIGN - 1);
  79   if (size <= avail)
  80     {
  81       pool->state.free[0] = avail - size;
  82       return pool->state.last[0] - avail;
  83     }
  84   else
  85     return mp_alloc_internal(pool, size);
  86 }
  87
  88 /* Inlined version of mp_alloc_noalign() */
  89 static inline void *
  90 mp_alloc_fast_noalign(struct mempool *pool, uns size)
  91 {
  92   if (size <= pool->state.free[0])
  93     {
  94       void *ptr = pool->state.last[0] - pool->state.free[0];
  95       pool->state.free[0] -= size;
  96       return ptr;
  97     }
  98   else
  99     return mp_alloc_internal(pool, size);
 100 }
 101
 102
 103 /*** Usage as a growing buffer ***/
 104
 105 /* For internal use only, do not call directly */
 106 void *mp_start_internal(struct mempool *pool, uns size) LIKE_MALLOC;
 107 void *mp_grow_internal(struct mempool *pool, uns size);
 108 void *mp_spread_internal(struct mempool *pool, void *p, uns size);
 109
 110 static inline uns
 111 mp_idx(struct mempool *pool, void *ptr)
 112 {
 113   return ptr == pool->last_big;
 114 }
 115
 116 /* Open a new growing buffer (at least <size> bytes long).
 117  * If the <size> is zero, the resulting pointer is undefined,
 118  * but it may be safely reallocated or used as the parameter
 119  * to other functions below.
 120  *
 121  * The resulting pointer is always aligned to a multiple of
 122  * CPU_STRUCT_ALIGN bytes and this condition remains true also
 123  * after future reallocations. There is an unaligned version as well.
 124  *
 125  * Keep in mind that you can't make any other <pool> allocations
 126  * before you "close" the growing buffer with mp_end().
 127  */
 128 void *mp_start(struct mempool *pool, uns size);
 129 void *mp_start_noalign(struct mempool *pool, uns size);
 130
 131 /* Inlined version of mp_start() */
 132 static inline void *
 133 mp_start_fast(struct mempool *pool, uns size)
 134 {
 135   uns avail = pool->state.free[0] & ~(CPU_STRUCT_ALIGN - 1);
 136   if (size <= avail)
 137     {
 138       pool->idx = 0;
 139       pool->state.free[0] = avail;
 140       return pool->state.last[0] - avail;
 141     }
 142   else
 143     return mp_start_internal(pool, size);
 144 }
 145
 146 /* Inlined version of mp_start_noalign() */
 147 static inline void *
 148 mp_start_fast_noalign(struct mempool *pool, uns size)
 149 {
 150   if (size <= pool->state.free[0])
 151     {
 152       pool->idx = 0;
 153       return pool->state.last[0] - pool->state.free[0];
 154     }
 155   else
 156     return mp_start_internal(pool, size);
 157 }
 158
 159 /* Return start pointer of the growing buffer allocated by mp_start() or a similar function */
 160 static inline void *
 161 mp_ptr(struct mempool *pool)
 162 {
 163   return pool->state.last[pool->idx] - pool->state.free[pool->idx];
 164 }
 165
 166 /* Return the number of bytes available for extending the growing buffer */
 167 static inline uns
 168 mp_avail(struct mempool *pool)
 169 {
 170   return pool->state.free[pool->idx];
 171 }
 172
 173 /* Grow the buffer allocated by mp_start() to be at least <size> bytes long
 174  * (<size> may be less than mp_avail(), even zero). Reallocated buffer may
 175  * change its starting position. The content will be unchanged to the minimum
 176  * of the old and new sizes; newly allocated memory will be uninitialized.
 177  * Multiple calls to mp_grow have amortized linear cost wrt. the maximum value of <size>. */
 178 static inline void *
 179 mp_grow(struct mempool *pool, uns size)
 180 {
 181   return (size <= mp_avail(pool)) ? mp_ptr(pool) : mp_grow_internal(pool, size);
 182 }
 183
 184 /* Grow the buffer by at least one byte -- equivalent to mp_grow(pool, mp_avail(pool) + 1) */
 185 static inline void *
 186 mp_expand(struct mempool *pool)
 187 {
 188   return mp_grow_internal(pool, mp_avail(pool) + 1);
 189 }
 190
 191 /* Ensure that there is at least <size> bytes free after <p>, if not, reallocate and adjust <p>. */
 192 static inline void *
 193 mp_spread(struct mempool *pool, void *p, uns size)
 194 {
 195   return (((uns)(pool->state.last[pool->idx] - p) >= size) ? p : mp_spread_internal(pool, p, size));
 196 }
 197
 198 /* Close the growing buffer. The <end> must point just behind the data, you want to keep
 199  * allocated (so it can be in the interval [mp_ptr(pool), mp_ptr(pool) + mp_avail(pool)]).
 200  * Returns a pointer to the beginning of the just closed block. */
 201 static inline void *
 202 mp_end(struct mempool *pool, void *end)
 203 {
 204   void *p = mp_ptr(pool);
 205   pool->state.free[pool->idx] = pool->state.last[pool->idx] - end;
 206   return p;
 207 }
 208
 209 /* Return size in bytes of the last allocated memory block (with mp_alloc*() or mp_end()). */
 210 static inline uns
 211 mp_size(struct mempool *pool, void *ptr)
 212 {
 213   uns idx = mp_idx(pool, ptr);
 214   return pool->state.last[idx] - ptr - pool->state.free[idx];
 215 }
 216
 217 /* Open the last memory block (allocated with mp_alloc*() or mp_end())
 218  * for growing and return its size in bytes. The contents and the start pointer
 219  * remain unchanged. Do not forget to call mp_end() to close it. */
 220 uns mp_open(struct mempool *pool, void *ptr);
 221
 222 /* Inlined version of mp_open() */
 223 static inline uns
 224 mp_open_fast(struct mempool *pool, void *ptr)
 225 {
 226   pool->idx = mp_idx(pool, ptr);
 227   uns size = pool->state.last[pool->idx] - ptr - pool->state.free[pool->idx];
 228   pool->state.free[pool->idx] += size;
 229   return size;
 230 }
 231
 232 /* Reallocate the last memory block (allocated with mp_alloc*() or mp_end())
 233  * to the new <size>. Behavior is similar to mp_grow(), but the resulting
 234  * block is closed. */
 235 void *mp_realloc(struct mempool *pool, void *ptr, uns size);
 236
 237 /* The same as mp_realloc(), but fills the additional bytes (if any) with zeroes */
 238 void *mp_realloc_zero(struct mempool *pool, void *ptr, uns size);
 239
 240 /* Inlined version of mp_realloc() */
 241 static inline void *
 242 mp_realloc_fast(struct mempool *pool, void *ptr, uns size)
 243 {
 244   mp_open_fast(pool, ptr);
 245   ptr = mp_grow(pool, size);
 246   mp_end(pool, ptr + size);
 247   return ptr;
 248 }
 249
 250
 251 /*** Usage as a stack ***/
 252
 253 /* Save the current state of a memory pool.
 254  * Do not call this function with an opened growing buffer. */
 255 static inline void
 256 mp_save(struct mempool *pool, struct mempool_state *state)
 257 {
 258   *state = pool->state;
 259   pool->state.next = state;
 260 }
 261
 262 /* Save the current state to a newly allocated mempool_state structure.
 263  * Do not call this function with an opened growing buffer. */
 264 struct mempool_state *mp_push(struct mempool *pool);
 265
 266 /* Restore the state saved by mp_save() or mp_push() and free all
 267  * data allocated after that point (including the state structure itself).
 268  * You can't reallocate the last memory block from the saved state. */
 269 void mp_restore(struct mempool *pool, struct mempool_state *state);
 270
 271 /* Restore the state saved by the last call to mp_push().
 272  * mp_pop() and mp_push() works as a stack so you can push more states safely. */
 273 void mp_pop(struct mempool *pool);
 274
 275
 276 /*** mempool-str.c ***/
 277
 278 char *mp_strdup(struct mempool *, const char *) LIKE_MALLOC;
 279 void *mp_memdup(struct mempool *, const void *, uns) LIKE_MALLOC;
 280 char *mp_multicat(struct mempool *, ...) LIKE_MALLOC SENTINEL_CHECK;
 281 static inline char * LIKE_MALLOC
 282 mp_strcat(struct mempool *mp, const char *x, const char *y)
 283 {
 284   return mp_multicat(mp, x, y, NULL);
 285 }
 286 char *mp_strjoin(struct mempool *p, char **a, uns n, uns sep) LIKE_MALLOC;
 287
 288
 289 /*** mempool-fmt.c ***/
 290
 291 char *mp_printf(struct mempool *mp, const char *fmt, ...) FORMAT_CHECK(printf,2,3) LIKE_MALLOC;
 292 char *mp_vprintf(struct mempool *mp, const char *fmt, va_list args) LIKE_MALLOC;
 293 char *mp_printf_append(struct mempool *mp, char *ptr, const char *fmt, ...) FORMAT_CHECK(printf,3,4);
 294 char *mp_vprintf_append(struct mempool *mp, char *ptr, const char *fmt, va_list args);
 295
 296 #endif