ucw/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 /***
  15  * [[defs]]
  16  * Definitions
  17  * -----------
  18  ***/
  19
  20 /**
  21  * Memory pool state (see @mp_push(), ...).
  22  ***/
  23 struct mempool_state {
  24   uns free[2];
  25   void *last[2];
  26   struct mempool_state *next;
  27 };
  28
  29 struct mempool { /** Memory pool. **/
  30   struct mempool_state state;
  31   void *unused, *last_big;
  32   uns chunk_size, threshold, idx;
  33 };
  34
  35 struct mempool_stats {                  /** Mempool statistics. See @mp_stats(). **/
  36   u64 total_size;                       /* Real allocated size in bytes */
  37   uns chain_count[3];                   /* Number of allocated chunks in small/big/unused chains */
  38   uns chain_size[3];                    /* Size of allocated chunks in small/big/unused chains */
  39 };
  40
  41 /***
  42  * [[basic]]
  43  * Basic manipulation
  44  * ------------------
  45  ***/
  46
  47 /**
  48  * Initialize a given mempool structure.
  49  * @chunk_size must be in the interval `[1, UINT_MAX / 2]`.
  50  * It will allocate memory by this large chunks and take
  51  * memory to satisfy requests from them.
  52  **/
  53 void mp_init(struct mempool *pool, uns chunk_size);
  54
  55 /**
  56  * Allocate and initialize a new memory pool.
  57  * See @mp_init() for @chunk_size limitations.
  58  *
  59  * The new mempool structure is allocated on the new mempool.
  60  **/
  61 struct mempool *mp_new(uns chunk_size);
  62
  63 /**
  64  * Cleanup mempool initialized by mp_init or mp_new.
  65  * Frees all the memory allocated by this mempool and,
  66  * if created by @mp_new(), the @pool itself.
  67  **/
  68 void mp_delete(struct mempool *pool);
  69
  70 /**
  71  * Free all data on a memory pool, but leaves it working.
  72  * It can keep some of the chunks allocated to serve
  73  * further allocation requests. Leaves the @pool alive,
  74  * even if it was created with @mp_new().
  75  **/
  76 void mp_flush(struct mempool *pool);
  77
  78 /**
  79  * Compute some statistics for debug purposes.
  80  * See the definition of the <<struct_mempool_stats,mempool_stats structure>>.
  81  **/
  82 void mp_stats(struct mempool *pool, struct mempool_stats *stats);
  83 u64 mp_total_size(struct mempool *pool);        /** How many bytes were allocated by the pool. **/
  84
  85
  86 /***
  87  * [[alloc]]
  88  * Allocation routines
  89  * -------------------
  90  ***/
  91
  92 /* For internal use only, do not call directly */
  93 void *mp_alloc_internal(struct mempool *pool, uns size) LIKE_MALLOC;
  94
  95 /**
  96  * The function allocates new @size bytes on a given memory pool.
  97  * If the @size is zero, the resulting pointer is undefined,
  98  * but it may be safely reallocated or used as the parameter
  99  * to other functions below.
 100  *
 101  * The resulting pointer is always aligned to a multiple of
 102  * `CPU_STRUCT_ALIGN` bytes and this condition remains true also
 103  * after future reallocations.
 104  **/
 105 void *mp_alloc(struct mempool *pool, uns size);
 106
 107 /**
 108  * The same as @mp_alloc(), but the result may be unaligned.
 109  **/
 110 void *mp_alloc_noalign(struct mempool *pool, uns size);
 111
 112 /**
 113  * The same as @mp_alloc(), but fills the newly allocated memory with zeroes.
 114  **/
 115 void *mp_alloc_zero(struct mempool *pool, uns size);
 116
 117 /**
 118  * Inlined version of @mp_alloc().
 119  **/
 120 static inline void *mp_alloc_fast(struct mempool *pool, uns size)
 121 {
 122   uns avail = pool->state.free[0] & ~(CPU_STRUCT_ALIGN - 1);
 123   if (size <= avail)
 124     {
 125       pool->state.free[0] = avail - size;
 126       return pool->state.last[0] - avail;
 127     }
 128   else
 129     return mp_alloc_internal(pool, size);
 130 }
 131
 132 /**
 133  * Inlined version of @mp_alloc_noalign().
 134  **/
 135 static inline void *mp_alloc_fast_noalign(struct mempool *pool, uns size)
 136 {
 137   if (size <= pool->state.free[0])
 138     {
 139       void *ptr = pool->state.last[0] - pool->state.free[0];
 140       pool->state.free[0] -= size;
 141       return ptr;
 142     }
 143   else
 144     return mp_alloc_internal(pool, size);
 145 }
 146
 147 /***
 148  * [[gbuf]]
 149  * Growing buffers
 150  * ---------------
 151  *
 152  * You do not need to know, how a buffer will need to be large,
 153  * you can grow it incrementally to needed size. You can grow only
 154  * one buffer at a time on a given mempool.
 155  ***/
 156
 157 /* For internal use only, do not call directly */
 158 void *mp_start_internal(struct mempool *pool, uns size) LIKE_MALLOC;
 159 void *mp_grow_internal(struct mempool *pool, uns size);
 160 void *mp_spread_internal(struct mempool *pool, void *p, uns size);
 161
 162 static inline uns
 163 mp_idx(struct mempool *pool, void *ptr)
 164 {
 165   return ptr == pool->last_big;
 166 }
 167
 168 /**
 169  * Open a new growing buffer (at least @size bytes long).
 170  * If the @size is zero, the resulting pointer is undefined,
 171  * but it may be safely reallocated or used as the parameter
 172  * to other functions below.
 173  *
 174  * The resulting pointer is always aligned to a multiple of
 175  * `CPU_STRUCT_ALIGN` bytes and this condition remains true also
 176  * after future reallocations. There is an unaligned version as well.
 177  *
 178  * Keep in mind that you can't make any other pool allocations
 179  * before you "close" the growing buffer with @mp_end().
 180  */
 181 void *mp_start(struct mempool *pool, uns size);
 182 void *mp_start_noalign(struct mempool *pool, uns size);
 183
 184 /**
 185  * Inlined version of @mp_start().
 186  **/
 187 static inline void *mp_start_fast(struct mempool *pool, uns size)
 188 {
 189   uns avail = pool->state.free[0] & ~(CPU_STRUCT_ALIGN - 1);
 190   if (size <= avail)
 191     {
 192       pool->idx = 0;
 193       pool->state.free[0] = avail;
 194       return pool->state.last[0] - avail;
 195     }
 196   else
 197     return mp_start_internal(pool, size);
 198 }
 199
 200 /**
 201  * Inlined version of @mp_start_noalign().
 202  **/
 203 static inline void *mp_start_fast_noalign(struct mempool *pool, uns size)
 204 {
 205   if (size <= pool->state.free[0])
 206     {
 207       pool->idx = 0;
 208       return pool->state.last[0] - pool->state.free[0];
 209     }
 210   else
 211     return mp_start_internal(pool, size);
 212 }
 213
 214 /**
 215  * Return start pointer of the growing buffer allocated by latest @mp_start() or a similar function.
 216  **/
 217 static inline void *mp_ptr(struct mempool *pool)
 218 {
 219   return pool->state.last[pool->idx] - pool->state.free[pool->idx];
 220 }
 221
 222 /**
 223  * Return the number of bytes available for extending the growing buffer.
 224  * (Before a reallocation will be needed).
 225  **/
 226 static inline uns mp_avail(struct mempool *pool)
 227 {
 228   return pool->state.free[pool->idx];
 229 }
 230
 231 /**
 232  * Grow the buffer allocated by @mp_start() to be at least @size bytes long
 233  * (@size may be less than @mp_avail(), even zero). Reallocated buffer may
 234  * change its starting position. The content will be unchanged to the minimum
 235  * of the old and new sizes; newly allocated memory will be uninitialized.
 236  * Multiple calls to mp_grow() have amortized linear cost wrt. the maximum value of @size. */
 237 static inline void *mp_grow(struct mempool *pool, uns size)
 238 {
 239   return (size <= mp_avail(pool)) ? mp_ptr(pool) : mp_grow_internal(pool, size);
 240 }
 241
 242 /**
 243  * Grow the buffer by at least one byte -- equivalent to <<mp_grow(),`mp_grow`>>`(@pool, @mp_avail(pool) + 1)`.
 244  **/
 245 static inline void *mp_expand(struct mempool *pool)
 246 {
 247   return mp_grow_internal(pool, mp_avail(pool) + 1);
 248 }
 249
 250 /**
 251  * Ensure that there is at least @size bytes free after @p,
 252  * if not, reallocate and adjust @p.
 253  **/
 254 static inline void *mp_spread(struct mempool *pool, void *p, uns size)
 255 {
 256   return (((uns)(pool->state.last[pool->idx] - p) >= size) ? p : mp_spread_internal(pool, p, size));
 257 }
 258
 259 /**
 260  * Close the growing buffer. The @end must point just behind the data, you want to keep
 261  * allocated (so it can be in the interval `[@mp_ptr(@pool), @mp_ptr(@pool) + @mp_avail(@pool)]`).
 262  * Returns a pointer to the beginning of the just closed block.
 263  **/
 264 static inline void *mp_end(struct mempool *pool, void *end)
 265 {
 266   void *p = mp_ptr(pool);
 267   pool->state.free[pool->idx] = pool->state.last[pool->idx] - end;
 268   return p;
 269 }
 270
 271 /**
 272  * Return size in bytes of the last allocated memory block (with @mp_alloc() or @mp_end()).
 273  **/
 274 static inline uns mp_size(struct mempool *pool, void *ptr)
 275 {
 276   uns idx = mp_idx(pool, ptr);
 277   return pool->state.last[idx] - ptr - pool->state.free[idx];
 278 }
 279
 280 /**
 281  * Open the last memory block (allocated with @mp_alloc() or @mp_end())
 282  * for growing and return its size in bytes. The contents and the start pointer
 283  * remain unchanged. Do not forget to call @mp_end() to close it.
 284  **/
 285 uns mp_open(struct mempool *pool, void *ptr);
 286
 287 /**
 288  * Inlined version of mp_open().
 289  **/
 290 static inline uns mp_open_fast(struct mempool *pool, void *ptr)
 291 {
 292   pool->idx = mp_idx(pool, ptr);
 293   uns size = pool->state.last[pool->idx] - ptr - pool->state.free[pool->idx];
 294   pool->state.free[pool->idx] += size;
 295   return size;
 296 }
 297
 298 /**
 299  * Reallocate the last memory block (allocated with @mp_alloc() or @mp_end())
 300  * to the new @size. Behavior is similar to @mp_grow(), but the resulting
 301  * block is closed.
 302  **/
 303 void *mp_realloc(struct mempool *pool, void *ptr, uns size);
 304
 305 /**
 306  * The same as @mp_realloc(), but fills the additional bytes (if any) with zeroes.
 307  **/
 308 void *mp_realloc_zero(struct mempool *pool, void *ptr, uns size);
 309
 310 /**
 311  * Inlined version of mp_realloc().
 312  **/
 313 static inline void *mp_realloc_fast(struct mempool *pool, void *ptr, uns size)
 314 {
 315   mp_open_fast(pool, ptr);
 316   ptr = mp_grow(pool, size);
 317   mp_end(pool, ptr + size);
 318   return ptr;
 319 }
 320
 321 /***
 322  * [[store]]
 323  * Storing and restoring state
 324  * ---------------------------
 325  *
 326  * Mempools can remember history of what was allocated and return back
 327  * in time.
 328  ***/
 329
 330 /**
 331  * Save the current state of a memory pool.
 332  * Do not call this function with an opened growing buffer.
 333  **/
 334 static inline void mp_save(struct mempool *pool, struct mempool_state *state)
 335 {
 336   *state = pool->state;
 337   pool->state.next = state;
 338 }
 339
 340 /**
 341  * Save the current state to a newly allocated mempool_state structure.
 342  * Do not call this function with an opened growing buffer.
 343  **/
 344 struct mempool_state *mp_push(struct mempool *pool);
 345
 346 /**
 347  * Restore the state saved by @mp_save() or @mp_push() and free all
 348  * data allocated after that point (including the state structure itself).
 349  * You can't reallocate the last memory block from the saved state.
 350  **/
 351 void mp_restore(struct mempool *pool, struct mempool_state *state);
 352
 353 /**
 354  * Restore the state saved by the last call to @mp_push().
 355  * @mp_pop() and @mp_push() works as a stack so you can push more states safely.
 356  **/
 357 void mp_pop(struct mempool *pool);
 358
 359
 360 /***
 361  * [[string]]
 362  * String operations
 363  * -----------------
 364  ***/
 365
 366 char *mp_strdup(struct mempool *, const char *) LIKE_MALLOC;            /** Makes a copy of a string on a mempool. **/
 367 void *mp_memdup(struct mempool *, const void *, uns) LIKE_MALLOC;       /** Makes a copy of a memory block on a mempool. **/
 368 /**
 369  * Concatenates all passed strings. The last parameter must be NULL.
 370  * This will concatenate two strings:
 371  *
 372  *   char *message = mp_multicat(pool, "hello ", "world", NULL);
 373  **/
 374 char *mp_multicat(struct mempool *, ...) LIKE_MALLOC SENTINEL_CHECK;
 375 /**
 376  * Concatenates two strings and stores result on @mp.
 377  */
 378 static inline char *LIKE_MALLOC mp_strcat(struct mempool *mp, const char *x, const char *y)
 379 {
 380   return mp_multicat(mp, x, y, NULL);
 381 }
 382 /**
 383  * Join strings and place @sep between each two neighboring.
 384  * @p is the mempool to provide memory, @a is array of strings and @n
 385  * tells how many there is of them.
 386  **/
 387 char *mp_strjoin(struct mempool *p, char **a, uns n, uns sep) LIKE_MALLOC;
 388
 389
 390 /***
 391  * [[format]]
 392  * Formated output
 393  * ---------------
 394  ***/
 395
 396 /**
 397  * printf() into a in-memory string, allocated on the memory pool.
 398  **/
 399 char *mp_printf(struct mempool *mp, const char *fmt, ...) FORMAT_CHECK(printf,2,3) LIKE_MALLOC;
 400 /**
 401  * Like @mp_printf(), but uses `va_list` for parameters.
 402  **/
 403 char *mp_vprintf(struct mempool *mp, const char *fmt, va_list args) LIKE_MALLOC;
 404 /**
 405  * Like @mp_printf(), but it appends the data at the end of memory
 406  * block pointed to by @ptr. The block is @mp_open()ed, so you have to
 407  * provide something that can be.
 408  *
 409  * Returns pointer to the beginning of the block (the pointer may have
 410  * changed due to reallocation).
 411  **/
 412 char *mp_printf_append(struct mempool *mp, char *ptr, const char *fmt, ...) FORMAT_CHECK(printf,3,4);
 413 /**
 414  * Like @mp_printf_append(), but uses `va_list` for parameters.
 415  **/
 416 char *mp_vprintf_append(struct mempool *mp, char *ptr, const char *fmt, va_list args);
 417
 418 #endif