src/mpool.c

   1 /*
   2     mpool.c - memory pool for constant sized objects
   3
   4   Copyright (C)         Lumiera.org
   5     2009,               Christian Thaeter <ct@pipapo.org>
   6
   7   This is a crippled version for nobug, the original version is maintained in lumiera
   8   (nobug debugging itself is left out here)
   9
  10   This program is free software; you can redistribute it and/or
  11   modify it under the terms of the GNU General Public License as
  12   published by the Free Software Foundation; either version 2 of the
  13   License, or (at your option) any later version.
  14
  15   This program is distributed in the hope that it will be useful,
  16   but WITHOUT ANY WARRANTY; without even the implied warranty of
  17   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18   GNU General Public License for more details.
  19
  20   You should have received a copy of the GNU General Public License
  21   along with this program; if not, write to the Free Software
  22   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  23 */
  24
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <stdio.h>
  28 #include <stdbool.h>
  29 #include <limits.h>
  30
  31 #include "mpool.h"
  32
  33 #if UINTPTR_MAX > 4294967295U   /* 64 bit */
  34 #define MPOOL_DIV_SHIFT 6
  35 #define MPOOL_C(c) c ## ULL
  36 #else                           /* 32 bit */
  37 #define MPOOL_DIV_SHIFT 5
  38 #define MPOOL_C(c) c ## UL
  39 #endif
  40
  41 /*
  42   Cluster and node structures are private
  43 */
  44
  45 typedef struct mpoolcluster_struct mpoolcluster;
  46 typedef mpoolcluster* MPoolcluster;
  47 typedef const mpoolcluster* const_MPoolcluster;
  48
  49 struct mpoolcluster_struct
  50 {
  51   llist node;           /* all clusters */
  52   char data[];          /* bitmap and elements */
  53 };
  54
  55
  56 typedef struct mpoolnode_struct mpoolnode;
  57 typedef mpoolnode* MPoolnode;
  58 typedef const mpoolnode* const_MPoolnode;
  59
  60 struct mpoolnode_struct
  61 {
  62   llist node;
  63 };
  64
  65
  66 MPool
  67 mpool_cluster_alloc_ (MPool self);
  68
  69
  70 #define MPOOL_BITMAP_SIZE(elements_per_cluster)                 \
  71   (((elements_per_cluster) + sizeof(uintptr_t)*CHAR_BIT - 1)    \
  72   / (sizeof(uintptr_t) * CHAR_BIT) * sizeof (uintptr_t))
  73
  74 MPool
  75 mpool_init (MPool self, size_t elem_size, unsigned elements_per_cluster, mpool_destroy_fn dtor)
  76 {
  77   if (self)
  78     {
  79       llist_init (&self->freelist);
  80       llist_init (&self->clusters);
  81       self->elem_size = (elem_size+sizeof(void*)-1) / sizeof(void*) * sizeof(void*);    /* void* aligned */
  82
  83       /* minimum size is the size of a llist node */
  84       if (self->elem_size < sizeof(llist))
  85         self->elem_size = sizeof(llist);
  86
  87       self->elements_per_cluster = elements_per_cluster;
  88
  89       self->cluster_size = sizeof (mpoolcluster) +              /* header */
  90         MPOOL_BITMAP_SIZE (self->elements_per_cluster) +        /* bitmap */
  91         self->elem_size * self->elements_per_cluster;           /* elements */
  92
  93       self->elements_free = 0;
  94       self->destroy = dtor;
  95       self->locality = NULL;
  96     }
  97
  98   return self;
  99 }
 100
 101
 102 static inline void*
 103 cluster_element_get (MPoolcluster cluster, MPool self, unsigned n)
 104 {
 105   return (void*)cluster +                                       /* start address */
 106     sizeof (*cluster) +                                         /* header */
 107     MPOOL_BITMAP_SIZE (self->elements_per_cluster) +            /* bitmap */
 108     self->elem_size * n;                                        /* offset*/
 109 }
 110
 111
 112 static inline bool
 113 bitmap_bit_get_nth (MPoolcluster cluster, unsigned index)
 114 {
 115   uintptr_t quot = index>>MPOOL_DIV_SHIFT;
 116   uintptr_t rem = index & ~((~MPOOL_C(0))<<MPOOL_DIV_SHIFT);
 117   uintptr_t* bitmap = (uintptr_t*)&cluster->data;
 118
 119   return bitmap[quot] & ((uintptr_t)1<<rem);
 120 }
 121
 122
 123 MPool
 124 mpool_destroy (MPool self)
 125 {
 126   if (self)
 127     {
 128       LLIST_WHILE_TAIL(&self->clusters, cluster)
 129         {
 130           if (self->destroy)
 131             for (unsigned i = 0; i < self->elements_per_cluster; ++i)
 132               {
 133                 if (bitmap_bit_get_nth ((MPoolcluster)cluster, i))
 134                   {
 135                     void* obj = cluster_element_get ((MPoolcluster)cluster, self, i);
 136                     self->destroy (obj);
 137                   }
 138               }
 139
 140           llist_unlink_fast_ (cluster);
 141           free (cluster);
 142         }
 143
 144       llist_init (&self->freelist);
 145       self->elements_free = 0;
 146       self->locality = NULL;
 147     }
 148
 149   return self;
 150 }
 151
 152
 153
 154 MPool
 155 mpool_cluster_alloc_ (MPool self)
 156 {
 157   MPoolcluster cluster = malloc (self->cluster_size);
 158
 159   if (!cluster)
 160     return NULL;
 161
 162   /* clear the bitmap */
 163   memset (&cluster->data, 0, MPOOL_BITMAP_SIZE (self->elements_per_cluster));
 164
 165   /* initialize freelist */
 166   for (unsigned i = 0; i < self->elements_per_cluster; ++i)
 167     {
 168       MPoolnode node = cluster_element_get (cluster, self, i);
 169       llist_insert_tail (&self->freelist, llist_init (&node->node));
 170     }
 171
 172   /* we insert the cluster at head because its likely be used next */
 173   llist_insert_head (&self->clusters, llist_init (&cluster->node));
 174   self->elements_free += self->elements_per_cluster;
 175
 176   return self;
 177 }
 178
 179
 180 static int
 181 cmp_cluster_contains_element (const_LList cluster, const_LList element, void* cluster_size)
 182 {
 183   if (element < cluster)
 184     return -1;
 185
 186   if ((void*)element > (void*)cluster + (uintptr_t)cluster_size)
 187     return 1;
 188
 189   return 0;
 190 }
 191
 192
 193 static inline MPoolcluster
 194 element_cluster_get (MPool self, void* element)
 195 {
 196   return (MPoolcluster) llist_ufind (&self->clusters, (const_LList) element, cmp_cluster_contains_element, (void*)self->cluster_size);
 197 }
 198
 199
 200 static inline unsigned
 201 uintptr_nearestbit (uintptr_t v, unsigned n)
 202 {
 203   unsigned r = 0;
 204   uintptr_t mask = MPOOL_C(1)<<n;
 205
 206   while (1)
 207     {
 208       if (v&mask)
 209         {
 210           if (v&mask& ~(~0ULL<<n))
 211             return n-r;
 212           else
 213             return n+r;
 214         }
 215       if (mask == ~MPOOL_C(0))
 216         return ~0U;
 217       ++r;
 218       mask |= ((mask<<1)|(mask>>1));
 219     }
 220 }
 221
 222
 223 static inline void*
 224 alloc_near (MPoolcluster cluster, MPool self, void* locality)
 225 {
 226   void* begin_of_elements =
 227     (void*)cluster +
 228     sizeof (*cluster) +                                                 /* header */
 229     MPOOL_BITMAP_SIZE (((MPool)self)->elements_per_cluster);            /* bitmap */
 230
 231   uintptr_t index = (locality - begin_of_elements) / self->elem_size;
 232   uintptr_t quot = index>>MPOOL_DIV_SHIFT;
 233   uintptr_t rem = index & ~((~MPOOL_C(0))<<MPOOL_DIV_SHIFT);
 234
 235   uintptr_t* bitmap = (uintptr_t*)&cluster->data;
 236   unsigned r = ~0U;
 237
 238   /* the bitmap word at locality */
 239   if (bitmap[quot] < UINTPTR_MAX)
 240     {
 241       r = uintptr_nearestbit (~bitmap[quot], rem);
 242     }
 243   /* the bitmap word before locality, this gives a slight bias towards the begin, keeping the pool compact */
 244   else if (quot && bitmap[quot-1] < UINTPTR_MAX)
 245     {
 246       --quot;
 247       r = uintptr_nearestbit (~bitmap[quot], sizeof(uintptr_t)*CHAR_BIT-1);
 248     }
 249
 250   if (r != ~0U && (quot*sizeof(uintptr_t)*CHAR_BIT+r) < self->elements_per_cluster)
 251     {
 252       void* ret = begin_of_elements + ((uintptr_t)(quot*sizeof(uintptr_t)*CHAR_BIT+r)*self->elem_size);
 253       return ret;
 254     }
 255   return NULL;
 256 }
 257
 258
 259 static inline void
 260 bitmap_set_element (MPoolcluster cluster, MPool self, void* element)
 261 {
 262   void* begin_of_elements =
 263     (void*)cluster +
 264     sizeof (*cluster) +                                                 /* header */
 265     MPOOL_BITMAP_SIZE (((MPool)self)->elements_per_cluster);            /* bitmap */
 266
 267   uintptr_t index = (element - begin_of_elements) / self->elem_size;
 268   uintptr_t quot = index>>MPOOL_DIV_SHIFT;
 269   uintptr_t rem = index & ~((~MPOOL_C(0))<<MPOOL_DIV_SHIFT);
 270
 271   uintptr_t* bitmap = (uintptr_t*)&cluster->data;
 272   bitmap[quot] |= ((uintptr_t)1<<rem);
 273 }
 274
 275
 276 static inline void
 277 bitmap_clear_element (MPoolcluster cluster, MPool self, void* element)
 278 {
 279   void* begin_of_elements =
 280     (void*)cluster +
 281     sizeof (*cluster) +                                                 /* header */
 282     MPOOL_BITMAP_SIZE (((MPool)self)->elements_per_cluster);            /* bitmap */
 283
 284   uintptr_t index = (element - begin_of_elements) / self->elem_size;
 285   uintptr_t quot = index>>MPOOL_DIV_SHIFT;
 286   uintptr_t rem = index & ~((~MPOOL_C(0))<<MPOOL_DIV_SHIFT);
 287
 288   uintptr_t* bitmap = (uintptr_t*)&cluster->data;
 289   bitmap[quot] &= ~((uintptr_t)1<<rem);
 290 }
 291
 292
 293 void*
 294 mpool_alloc (MPool self)
 295 {
 296   if (!self->elements_free)
 297     {
 298       if (mpool_cluster_alloc_ (self))
 299         self->locality = NULL; /* supress alloc_near() */
 300       else
 301         return NULL;
 302     }
 303
 304   void* ret = NULL;
 305
 306   if (self->locality)
 307     ret = alloc_near (element_cluster_get (self, self->locality), self, self->locality);
 308
 309   if (!ret)
 310     ret = llist_head (&self->freelist);
 311
 312   if (ret)
 313     {
 314       bitmap_set_element (element_cluster_get (self, ret), self, ret);
 315       llist_unlink_fast_ ((LList)ret);
 316     }
 317
 318   self->locality = ret;
 319   --self->elements_free;
 320
 321   return ret;
 322 }
 323
 324
 325 void*
 326 mpool_alloc_near (MPool self, void* near)
 327 {
 328   if (!self->elements_free)
 329     {
 330       if (mpool_cluster_alloc_ (self))
 331         near = NULL; /* supress alloc_near() */
 332       else
 333         return NULL;
 334     }
 335
 336   void* ret = NULL;
 337
 338   if (near)
 339     ret = alloc_near (element_cluster_get (self, near), self, near);
 340
 341   if (!ret)
 342     ret = llist_head (&self->freelist);
 343
 344   if (ret)
 345     {
 346       bitmap_set_element (element_cluster_get (self, ret), self, ret);
 347       llist_unlink_fast_ ((LList)ret);
 348     }
 349
 350   --self->elements_free;
 351
 352   return ret;
 353 }
 354
 355
 356 static inline MPoolnode
 357 find_near (MPoolcluster cluster, MPool self, void* element)
 358 {
 359   void* begin_of_elements =
 360     (void*)cluster +
 361     sizeof (*cluster) +                                                 /* header */
 362     MPOOL_BITMAP_SIZE (((MPool)self)->elements_per_cluster);            /* bitmap */
 363
 364   uintptr_t index = (element - begin_of_elements) / self->elem_size;
 365   uintptr_t quot = index>>MPOOL_DIV_SHIFT;
 366   uintptr_t rem = index & ~((~MPOOL_C(0))<<MPOOL_DIV_SHIFT);
 367
 368   uintptr_t* bitmap = (uintptr_t*)&cluster->data;
 369   unsigned r = ~0U;
 370
 371   /* the bitmap word at locality */
 372   if (bitmap[quot] < UINTPTR_MAX)
 373     {
 374       r = uintptr_nearestbit (~bitmap[quot], rem);
 375     }
 376   /* the bitmap word after element, we assume that elements after the searched element are more likely be free */
 377   else if (index < self->elements_per_cluster && bitmap[quot+1] < UINTPTR_MAX)
 378     {
 379       ++quot;
 380       r = uintptr_nearestbit (~bitmap[quot], 0);
 381     }
 382   /* finally the bitmap word before element */
 383   else if (index > 0 && bitmap[quot-1] < UINTPTR_MAX)
 384     {
 385       --quot;
 386       r = uintptr_nearestbit (~bitmap[quot], sizeof(uintptr_t)*CHAR_BIT-1);
 387     }
 388
 389   if (r != ~0U && (quot*sizeof(uintptr_t)*CHAR_BIT+r) < self->elements_per_cluster)
 390     return begin_of_elements + ((uintptr_t)(quot*sizeof(uintptr_t)*CHAR_BIT+r)*self->elem_size);
 391
 392   return NULL;
 393 }
 394
 395
 396 void
 397 mpool_free (MPool self, void* element)
 398 {
 399   if (self && element)
 400     {
 401       MPoolcluster cluster = element_cluster_get (self,element);
 402       MPoolnode near = find_near (cluster, self, element);
 403
 404       bitmap_clear_element (cluster, self, element);
 405       llist_init (&((MPoolnode)element)->node);
 406
 407       if (near)
 408         {
 409           if (near < (MPoolnode)element)
 410             llist_insert_next (&near->node, &((MPoolnode)element)->node);
 411           else
 412             llist_insert_prev (&near->node, &((MPoolnode)element)->node);
 413         }
 414       else
 415         llist_insert_tail (&self->freelist, &((MPoolnode)element)->node);
 416
 417       ++self->elements_free;
 418     }
 419 }
 420
 421
 422
 423 MPool
 424 mpool_reserve (MPool self, unsigned nelements)
 425 {
 426   if (self)
 427     while (self->elements_free < nelements)
 428       if (!mpool_cluster_alloc_ (self))
 429         return NULL;
 430
 431   return self;
 432 }
 433
 434
 435 /*
 436 //      Local Variables:
 437 //      mode: C
 438 //      c-file-style: "gnu"
 439 //      indent-tabs-mode: nil
 440 //      End:
 441 */