Robust/src/Runtime/memPool.h

   1 #ifndef ___MEMPOOL_H__
   2 #define ___MEMPOOL_H__
   3
   4 //////////////////////////////////////////////////////////
   5 //
   6 //  A memory pool implements POOLCREATE, POOLALLOC and
   7 //  POOLFREE to improve memory allocation by reusing records.
   8 //
   9 //  This implementation uses a lock-free singly-linked list
  10 //  to store reusable records.  The list is initialized with
  11 //  one valid record, and the list is considered empty when
  12 //  it has only one record; this allows the enqueue operation's
  13 //  CAS to assume tail can always be dereferenced.
  14 //
  15 //  poolfree adds newly freed records to the list BACK
  16 //
  17 //  poolalloc either takes records from FRONT or mallocs
  18 //
  19 //////////////////////////////////////////////////////////
  20
  21 #include <stdlib.h>
  22
  23 #ifdef MEMPOOL_DETECT_MISUSE
  24 #include <stdio.h>
  25 #include <sys/mman.h>
  26 #include <unistd.h>
  27 #include <errno.h>
  28 #include <string.h>
  29 static INTPTR pageSize;
  30 #endif
  31
  32 #include "runtime.h"
  33 #include "mem.h"
  34 #include "mlp_lock.h"
  35
  36
  37 #define CACHELINESIZE 64
  38
  39
  40
  41 typedef struct MemPoolItem_t {
  42   void* next;
  43 } MemPoolItem;
  44
  45
  46 typedef struct MemPool_t {
  47   int itemSize;
  48
  49   // only invoke this on items that are
  50   // actually new, saves time for reused
  51   // items
  52   void(*initFreshlyAllocated)(void*);
  53
  54 #ifdef MEMPOOL_DETECT_MISUSE
  55   int allocSize;
  56 #else
  57   //normal version
  58   MemPoolItem* head;
  59   // avoid cache line contention between producer/consumer...
  60   char buffer[CACHELINESIZE];
  61   MemPoolItem* tail;
  62 #endif
  63 } MemPool;
  64
  65
  66 // the memory pool must always have at least one
  67 // item in it
  68 static MemPool* poolcreate( int itemSize,
  69                             void(*initializer)(void*)
  70                             ) {
  71
  72   MemPool* p  = RUNMALLOC( sizeof( MemPool ) );
  73   p->itemSize = itemSize;
  74
  75   p->initFreshlyAllocated = initializer;
  76
  77 #ifdef MEMPOOL_DETECT_MISUSE
  78   // when detecting misuse, round the item size
  79   // up to a page and add a page, so whatever
  80   // allocated memory you get, you can use a
  81   // page-aligned subset as the record
  82   pageSize = sysconf( _SC_PAGESIZE );
  83
  84   if( itemSize % pageSize == 0 ) {
  85     // if the item size is already an exact multiple
  86     // of the page size, just increase by one page
  87     p->allocSize = itemSize + pageSize;
  88   } else {
  89     // otherwise, round down to a page size, then add two
  90     p->allocSize = (itemSize & ~(pageSize-1)) + 2*pageSize;
  91   }
  92 #else
  93
  94   // normal version
  95   p->head = RUNMALLOC( p->itemSize );
  96
  97   if( p->initFreshlyAllocated != NULL ) {
  98     p->initFreshlyAllocated( p->head );
  99   }
 100
 101   p->head->next = NULL;
 102   p->tail       = p->head;
 103 #endif
 104
 105   return p;
 106 }
 107
 108
 109
 110 #ifdef MEMPOOL_DETECT_MISUSE
 111
 112 static inline void poolfreeinto( MemPool* p, void* ptr ) {
 113   // don't actually return memory to the pool, just lock
 114   // it up tight so first code to touch it badly gets caught
 115   // also, mprotect automatically protects full pages
 116   if( mprotect( ptr, p->itemSize, PROT_NONE ) != 0 ) {
 117     printf( "mprotect failed, %s.\n", strerror( errno ) );
 118     exit( -1 );
 119   }
 120 }
 121
 122 #else
 123
 124 // normal version
 125 static inline void poolfreeinto( MemPool* p, void* ptr ) {
 126
 127   MemPoolItem* tailCurrent;
 128   MemPoolItem* tailActual;
 129
 130   // set up the now unneeded record to as the tail of the
 131   // free list by treating its first bytes as next pointer,
 132   MemPoolItem* tailNew = (MemPoolItem*) ptr;
 133   tailNew->next = NULL;
 134
 135   while( 1 ) {
 136     // make sure the null happens before the insertion,
 137     // also makes sure that we reload tailCurrent, etc..
 138     BARRIER();
 139
 140     tailCurrent = p->tail;
 141     tailActual = (MemPoolItem*)
 142       CAS( &(p->tail),         // ptr to set
 143            (INTPTR) tailCurrent, // current tail's next should be NULL
 144            (INTPTR) tailNew      // try set to our new tail
 145            );
 146     if( tailActual == tailCurrent ) {
 147       // success, update tail
 148       tailCurrent->next = tailNew;
 149       return;
 150     }
 151
 152     // if CAS failed, retry entire operation
 153   }
 154 }
 155 #endif
 156
 157
 158
 159 #ifdef MEMPOOL_DETECT_MISUSE
 160
 161 static inline void* poolalloc( MemPool* p ) {
 162   // put the memory we intend to expose to client
 163   // on a page-aligned boundary, always return
 164   // new memory
 165   INTPTR nonAligned = (INTPTR) RUNMALLOC( p->allocSize );
 166
 167   void* newRec = (void*)((nonAligned + pageSize-1) & ~(pageSize-1));
 168
 169   if( p->initFreshlyAllocated != NULL ) {
 170     p->initFreshlyAllocated( newRec );
 171   }
 172
 173   return newRec;
 174 }
 175
 176 #else
 177
 178 // normal version
 179 static inline void* poolalloc( MemPool* p ) {
 180
 181   // to protect CAS in poolfree from dereferencing
 182   // null, treat the queue as empty when there is
 183   // only one item.  The dequeue operation is only
 184   // executed by the thread that owns the pool, so
 185   // it doesn't require an atomic op
 186   MemPoolItem* headCurrent = p->head;
 187   MemPoolItem* next=headCurrent->next;
 188   int i;
 189   if(next == NULL) {
 190     // only one item, so don't take from pool
 191     void* newRec = RUNMALLOC( p->itemSize );
 192
 193     if( p->initFreshlyAllocated != NULL ) {
 194       p->initFreshlyAllocated( newRec );
 195     }
 196
 197     return newRec;
 198   }
 199
 200   p->head = next;
 201
 202   asm volatile( "prefetcht0 (%0)" :: "r" (next));
 203   next=(MemPoolItem*)(((char *)next)+CACHELINESIZE);
 204   asm volatile( "prefetcht0 (%0)" :: "r" (next));
 205
 206   return (void*)headCurrent;
 207 }
 208 #endif
 209
 210
 211
 212 static void pooldestroy( MemPool* p ) {
 213
 214 #ifndef MEMPOOL_DETECT_MISUSE
 215   MemPoolItem* i = p->head;
 216   MemPoolItem* n;
 217
 218   while( i != NULL ) {
 219     n = i->next;
 220     free( i );
 221     i = n;
 222   }
 223 #endif
 224
 225   free( p );
 226 }
 227
 228
 229 #endif // ___MEMPOOL_H__
 230
 231
 232
 233
 234
 235
 236
 237
 238
 239