slaballoc.h

   1 /*
   2  *  slaballoc.h
   3  *  openc2e
   4  *
   5  *  Created by Bryan Donlan on Wed 11 Jan 2006.
   6  *  Copyright (c) 2006 Bryan Donlan. All rights reserved.
   7  *
   8  *  This library is free software; you can redistribute it and/or
   9  *  modify it under the terms of the GNU Lesser General Public
  10  *  License as published by the Free Software Foundation; either
  11  *  version 2 of the License, or (at your option) any later version.
  12  *
  13  *  This library is distributed in the hope that it will be useful,
  14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  *  Lesser General Public License for more details.
  17  *
  18  */
  19 #ifndef SLABALLOC_H
  20 #define SLABALLOC_H 1
  21
  22 #include <cassert>
  23 #include <cstdlib>
  24
  25 /* Destructor callback for allocations.
  26  *
  27  * Note that this _must not_ allocate from the pool it is registered in.
  28  */
  29 typedef void (*destructor_t)(void *p);
  30
  31 class SlabAllocator {
  32         protected:
  33
  34                 size_t objsz;
  35
  36
  37                 struct slab_head {
  38                         bool reserved;
  39                         struct slab_head *next;
  40                         size_t extent;
  41                         size_t elements;
  42                         size_t objsz, tail;
  43                         SlabAllocator *owner;
  44                 };
  45
  46                 struct alloc_head {
  47                         slab_head *slab;
  48                         alloc_head *next; // Overlaps data
  49                 };
  50
  51                 size_t unitsz(size_t objsz) {
  52                         size_t sz = objsz;
  53                         // Assumption: Pointers are aligned to the same or stricter
  54                         // boundraries than all other types
  55                         //
  56                         // Otherwise with objsz == 7 and sizeof slab_head * == 8
  57                         // you'd end up with 54-byte blocks
  58                         //
  59                         // XXX: if there's padding after alloc_head.slab we explode
  60                         assert((size_t)&((alloc_head *)NULL)->next == sizeof (slab_head *));
  61                         if (sz < sizeof(slab_head *))
  62                                 sz = sizeof(slab_head *);
  63                         else if (sz % sizeof(slab_head *))
  64                                 sz += (sizeof(slab_head *)) - (sz % sizeof(slab_head *));
  65                         return sz;
  66                 }
  67
  68                 /* How much padding to add after the end of the data segment.
  69                  * Subclasses should add values to the return value of this,
  70                  * if they want to store private data there.
  71                  */
  72                 virtual size_t tail_data() const { return 0; }
  73
  74                 // Find how many unitsz fit in target - sizeof slab_head
  75                 size_t alloc_count(size_t unitsz, size_t target) {
  76                         target -= sizeof(slab_head);
  77                         return target / unitsz;
  78                 }
  79
  80                 size_t count, freect, memy_usage, memy_reserved, memy_free;
  81                 size_t block_size;
  82                 alloc_head *p_free; // A chain through free blocks
  83                 slab_head *p_head; // A chain through the beginnings of the blocks
  84                 // head is used for destructor freeing and clear()
  85                 slab_head *p_bad;  // A chain through blocks which can't be reallocated
  86                 bool autofree;
  87
  88                 void get_block() {
  89                         assert(!freect);
  90                         size_t objsz = unitsz(this->objsz);
  91                         size_t unit = objsz + tail_data();
  92                         size_t items = alloc_count(unit, block_size);
  93                         assert(items != 0);
  94                         size_t extent = unit * items;
  95                         size_t alloc = sizeof(slab_head) + extent;
  96                         void *chunk = malloc(alloc);
  97                         if (!chunk)
  98                                 throw std::bad_alloc();
  99                         slab_head *old_head = p_head;
 100                         p_head = (slab_head *)chunk;
 101                         p_head->next = old_head;
 102                         p_head->extent = extent;
 103                         p_head->elements = items;
 104                         p_head->owner = this;
 105                         p_head->reserved = false;
 106                         p_head->objsz = objsz;
 107                         p_head->tail = tail_data();
 108
 109                         unsigned char *dataspace = (unsigned char *)(p_head + 1);
 110
 111                         for (size_t i = 0; i < items; i++) {
 112                                 unsigned char *p = dataspace + i * unit;
 113                                 alloc_head *ah = (alloc_head *)p;
 114                                 ah->slab = p_head;
 115                                 ah->next = p_free;
 116                                 p_free = ah;
 117                                 freect++;
 118                                 count++;
 119                         }
 120
 121                         memy_usage += alloc;
 122                         memy_free += extent;
 123                 }
 124
 125                 static void null_destructor(void *) throw() {}
 126
 127         protected:
 128                 virtual alloc_head *_alloc(size_t sz) {
 129                         sz += sizeof(slab_head *);
 130                         if (sz < sizeof(alloc_head))
 131                                 sz = sizeof(alloc_head);
 132                         if (sz > objsz) {
 133                                 // libcpp is playing nasty tricks on us, blah
 134                                 freect = 0;
 135                                 p_free = NULL;
 136                                 objsz = sz;
 137                                 memy_reserved += memy_free;
 138                                 memy_free = 0;
 139                                 p_bad = p_head;
 140
 141                                 for (slab_head *h = p_bad; h && !h->reserved; h++)
 142                                         h->reserved = true;
 143                         }
 144                         if (!p_free) get_block();
 145                         assert(p_free);
 146
 147                         alloc_head *p = p_free;
 148                         p_free = p->next;
 149
 150                         freect--;
 151                         memy_free -= objsz;
 152
 153                         assert(p->slab->owner == this);
 154
 155                         return p;
 156                 }
 157
 158                 virtual void _release(alloc_head *p) {
 159                         if (p->slab->reserved)
 160                                 return;
 161                         p->next = p_free;
 162                         p_free = p;
 163                         freect++;
 164                         memy_free += objsz;
 165                 }
 166
 167         public:
 168                 /* Allocate sz bytes of data with the dest destructor callback,
 169                  * and return a pointer to the buffer.
 170                  *
 171                  * Note that this class does not use dest; use DestructingSlab
 172                  * if you need destruction when the slab goes away.
 173                  */
 174                 virtual void *alloc(size_t sz, destructor_t dest = null_destructor) {
 175                         (void)dest;
 176                         alloc_head *ah = _alloc(sz);
 177                         return (void *)&ah->next;
 178                 }
 179
 180                 /* Free the previously allocated data pointed to by p. */
 181                 virtual void release(void *p) {
 182                         alloc_head ahs;
 183                         unsigned char *cp = (unsigned char *)p;
 184                         cp -= ((unsigned char *)&ahs.next - (unsigned char *)&ahs);
 185                         _release((alloc_head *)cp);
 186                 }
 187
 188                 /* Arguments:
 189                  *
 190                  * size_t objsz_ - the expected size of an allocation in the slab
 191                  *   Note that, while it is not an error to allocate something
 192                  *   larger than this, if said allocation is not the first to be
 193                  *   done in the slab it will result in wasted memory until and
 194                  *   unless clear() is called.
 195                  * size_t bm
 196                  *   Indicates the target size of a slab, in bytes.
 197                  * bool af
 198                  *   Whether to free the memory of this slab on destruction
 199                  *   It's best to set this to false for globals, to prevent
 200                  *   weird order-of-destruction effects.
 201                  */
 202                 SlabAllocator(size_t objsz_ = sizeof(void **), size_t bm = 4096, bool af = true)
 203                         : objsz(objsz_), count(0), freect(0),
 204                           memy_usage(0), memy_reserved(0), memy_free(0),
 205                           block_size(bm), p_free(NULL), p_head(NULL),
 206                           autofree(af)
 207                   {
 208                           objsz += sizeof(slab_head *);
 209                   }
 210
 211                 // Note: deleting using ~SlabAllocator or clear() do _NOT_
 212                 // call destructors! Use DestructingSlab
 213
 214                 virtual ~SlabAllocator() { if (autofree) clear(); }
 215
 216                 /* Free all allocations in the slab, and release all slab memory
 217                  * to the system.
 218                  */
 219                 virtual void clear() {
 220                         while (p_head) {
 221                                 slab_head *pp = p_head;
 222                                 p_head = pp->next;
 223                                 free((void *)pp);
 224                         }
 225                         freect = count = 0;
 226                         p_free = NULL;
 227                         p_head = NULL;
 228                         memy_usage = memy_reserved = memy_free = 0;
 229                 }
 230
 231                 size_t free_elements() const { return freect; }
 232                 size_t total_elements() const { return count; }
 233                 size_t used_elements() const { return count - freect; }
 234
 235                 size_t memory_usage() const { return memy_usage; }
 236                 size_t memory_free() const { return memy_free; }
 237                 size_t memory_reserved() const { return memy_reserved; }
 238
 239                 /* Some workarounds for C++ weirdness.
 240                  *
 241                  * We stuff a pointer to the slab right before the class
 242                  * unconditionally. If the user doesn't pass us a slab, store
 243                  * NULL and use malloc. o_del detects the NULL and delegates
 244                  * to the appropriate releaser function.
 245                  *
 246                  * Note that C++ guarentees that the object destructor will
 247                  * be called before operator delete (and thus, o_del).
 248                  */
 249                 static void *o_new(size_t sz, destructor_t dest, SlabAllocator &slab) {
 250                         return (void *)slab.alloc(sz, dest);
 251                 }
 252
 253                 static void *o_new(size_t sz) {
 254                         alloc_head *ah = (alloc_head *)malloc(sizeof(&ah->slab) + sz);
 255                         ah->slab = NULL;
 256                         return (void *)&ah->next;
 257                 }
 258
 259                 static void o_del(void *p) {
 260                         alloc_head ahs;
 261                         unsigned char *cp = (unsigned char *)p;
 262                         cp -= ((unsigned char *)&ahs.next - (unsigned char *)&ahs);
 263                         alloc_head *ap = (alloc_head *)cp;
 264
 265                         if (ap->slab)
 266                                 ap->slab->owner->_release(ap);
 267                         else
 268                                 free((void *)ap);
 269                 }
 270
 271 };
 272
 273 // Subclass to destruct members on clear() or slab destruction.
 274 // Note that explicitly calling release won't destruct the objects
 275 // for you.
 276 class DestructingSlab : public SlabAllocator {
 277         protected:
 278                 struct destructor_info {
 279                         destructor_info *next;
 280                         destructor_info *prev;
 281                         destructor_t dest;
 282                         alloc_head *ah;
 283                 };
 284
 285                 virtual size_t tail_data() const {
 286                         return SlabAllocator::tail_data() + sizeof(destructor_info);
 287                 }
 288
 289                 destructor_info *p_dest;
 290         public:
 291
 292                 DestructingSlab(size_t objsz_ = sizeof(void **),
 293                                         size_t bm = 4096) : SlabAllocator(objsz_, bm) {
 294                         p_dest = NULL;
 295                 }
 296
 297                 virtual void *alloc(size_t sz, destructor_t dest = null_destructor) {
 298                         alloc_head *ah = _alloc(sz);
 299                         unsigned char *up = (unsigned char *)&ah->next;
 300                         up += ah->slab->objsz + SlabAllocator::tail_data();
 301                         destructor_info *di = (destructor_info *)up;
 302                         di->next = p_dest;
 303                         if (di->next)
 304                                 di->next->prev = di;
 305                         di->prev = NULL;
 306                         di->dest = dest;
 307                         di->ah = ah;
 308                         return (void *)&ah->next;
 309                 }
 310
 311                 virtual void release(void *p) {
 312                         unsigned char *cp = (unsigned char *)p;
 313                         cp -= sizeof (alloc_head *);
 314                         alloc_head *ah = (alloc_head *)cp;
 315
 316                         cp += ah->slab->objsz + SlabAllocator::tail_data();
 317                         destructor_info *dp = (destructor_info *)cp;
 318
 319                         if (dp->next)
 320                                 dp->next->prev = dp->prev;
 321                         if (dp->prev)
 322                                 dp->prev->next = dp->next;
 323                         else
 324                                 p_dest = dp->next;
 325                         assert(dp->ah == ah);
 326
 327                         _release(ah);
 328                 }
 329
 330                 virtual void clear() {
 331                         while (p_dest) {
 332                                 alloc_head *ah = p_dest->ah;
 333                                 unsigned char *cp = (unsigned char *)ah;
 334                                 cp += sizeof (slab_head *);
 335
 336                                 p_dest->dest((void *)cp);
 337                                 /* It'd be faster to just run all the destructors then zot the entire
 338                                  * pool, but if any destructor frees memory in the meantime this
 339                                  * *might* cause problems (needs more analysis).
 340                                  *
 341                                  * For now, release properly.
 342                                  */
 343                                 release((void *)cp);
 344                         }
 345                         SlabAllocator::clear();
 346                 }
 347 };
 348
 349 // Use in public class member section
 350 #define SLAB_CLASS(c) \
 351         static void _SLAB_destruct(void *p) { \
 352                 c *pc = (c *)p; \
 353                 pc->~c(); \
 354         } \
 355         void *operator new(size_t sz, SlabAllocator &slab) { \
 356                 return SlabAllocator::o_new(sz, _SLAB_destruct, slab); \
 357         } \
 358         void *operator new(size_t sz) { \
 359                 return SlabAllocator::o_new(sz); \
 360         } \
 361         void operator delete(void *p) { \
 362                 SlabAllocator::o_del(p); \
 363         }
 364
 365 #endif