ucw/eltpool.c

   1 /*
   2  *      UCW Library -- Fast Allocator for Fixed-Size Elements
   3  *
   4  *      (c) 2007 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 /*
  11  *  This allocator is optimized for intensive allocation and freeing of small
  12  *  blocks of identical sizes. System memory is allocated by multiples of the
  13  *  page size and it is returned back only when the whole eltpool is deleted.
  14  *
  15  *  In the future, we can add returning of memory to the system and also cache
  16  *  coloring like in the SLAB allocator used in the Linux kernel.
  17  */
  18
  19 #undef LOCAL_DEBUG
  20
  21 #include "ucw/lib.h"
  22 #include "ucw/eltpool.h"
  23
  24 struct eltpool *
  25 ep_new(uns elt_size, uns elts_per_chunk)
  26 {
  27   struct eltpool *pool = xmalloc_zero(sizeof(*pool));
  28   pool->elt_size = ALIGN_TO(MAX(elt_size, sizeof(struct eltpool_free)), CPU_STRUCT_ALIGN);
  29   pool->chunk_size = CPU_PAGE_SIZE;
  30   while (pool->elt_size * elts_per_chunk + sizeof(struct eltpool_chunk) > pool->chunk_size)
  31     pool->chunk_size *= 2;
  32   pool->elts_per_chunk = (pool->chunk_size - sizeof(struct eltpool_chunk)) / pool->elt_size;
  33   DBG("ep_new(): got elt_size=%d, epc=%d; used chunk_size=%d, epc=%d", elt_size, elts_per_chunk, pool->chunk_size, pool->elts_per_chunk);
  34   return pool;
  35 }
  36
  37 void
  38 ep_delete(struct eltpool *pool)
  39 {
  40   struct eltpool_chunk *ch;
  41   while (ch = pool->first_chunk)
  42     {
  43       pool->first_chunk = ch->next;
  44       page_free(ch, pool->chunk_size);
  45     }
  46   xfree(pool);
  47 }
  48
  49 void *
  50 ep_alloc_slow(struct eltpool *pool)
  51 {
  52   struct eltpool_chunk *ch = page_alloc(pool->chunk_size);
  53   void *p = (void *)(ch+1);
  54   for (uns i=1; i<pool->elts_per_chunk; i++)
  55     {
  56       struct eltpool_free *f = p;
  57       f->next = pool->first_free;
  58       pool->first_free = f;
  59       p += pool->elt_size;
  60     }
  61   ch->next = pool->first_chunk;
  62   pool->first_chunk = ch;
  63   pool->num_chunks++;
  64   return p;
  65 }
  66
  67 u64
  68 ep_total_size(struct eltpool *pool)
  69 {
  70   return (u64)pool->num_chunks * pool->chunk_size + sizeof(*pool);
  71 }
  72
  73 #ifdef TEST
  74
  75 #include <stdio.h>
  76 #include "ucw/clists.h"
  77
  78 struct argh {
  79   cnode n;
  80   byte x[1];
  81 } PACKED;
  82
  83 int main(void)
  84 {
  85   struct eltpool *ep = ep_new(sizeof(struct argh), 64);
  86   clist l;
  87   clist_init(&l);
  88   for (uns i=0; i<65536; i++)
  89     {
  90       struct argh *a = ep_alloc(ep);
  91       if (i % 3)
  92         clist_add_tail(&l, &a->n);
  93       else
  94         clist_add_head(&l, &a->n);
  95       if (!(i % 5))
  96         {
  97           a = clist_head(&l);
  98           clist_remove(&a->n);
  99           ep_free(ep, a);
 100         }
 101     }
 102   ep_delete(ep);
 103   puts("OK");
 104   return 0;
 105 }
 106
 107 #endif