lib/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 "lib/lib.h"
  22 #include "lib/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   return p;
  64 }
  65
  66 #ifdef TEST
  67
  68 #include <stdio.h>
  69 #include "lib/clists.h"
  70
  71 struct argh {
  72   cnode n;
  73   byte x[1];
  74 } PACKED;
  75
  76 int main(void)
  77 {
  78   struct eltpool *ep = ep_new(sizeof(struct argh), 64);
  79   clist l;
  80   clist_init(&l);
  81   for (uns i=0; i<65536; i++)
  82     {
  83       struct argh *a = ep_alloc(ep);
  84       if (i % 3)
  85         clist_add_tail(&l, &a->n);
  86       else
  87         clist_add_head(&l, &a->n);
  88       if (!(i % 5))
  89         {
  90           a = clist_head(&l);
  91           clist_remove(&a->n);
  92           ep_free(ep, a);
  93         }
  94     }
  95   ep_delete(ep);
  96   puts("OK");
  97   return 0;
  98 }
  99
 100 #endif