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   int protectSize;
  57 #else
  58   //normal version
  59   MemPoolItem* head;
  60   // avoid cache line contention between producer/consumer...
  61   char buffer[CACHELINESIZE];
  62   MemPoolItem* tail;
  63 #endif
  64 } MemPool;
  65
  66
  67 // the memory pool must always have at least one
  68 // item in it
  69 static MemPool* poolcreate( int itemSize,
  70                             void(*initializer)(void*)
  71                             ) {
  72
  73   MemPool* p  = RUNMALLOC( sizeof( MemPool ) );
  74   p->itemSize = itemSize;
  75
  76   p->initFreshlyAllocated = initializer;
  77
  78 #ifdef MEMPOOL_DETECT_MISUSE
  79   // when detecting misuse, round the item size
  80   // up to a page and add a page, so whatever
  81   // allocated memory you get, you can use a
  82   // page-aligned subset as the record
  83   pageSize = sysconf( _SC_PAGESIZE );
  84
  85   if( itemSize % pageSize == 0 ) {
  86     // if the item size is already an exact multiple
  87     // of the page size, just increase alloc by one page
  88     p->allocSize = itemSize + pageSize;
  89
  90     // and size for mprotect should be exact page multiple
  91     p->protectSize = itemSize;
  92   } else {
  93     // otherwise, round down to a page size, then add two
  94     p->allocSize = (itemSize & ~(pageSize-1)) + 2*pageSize;
  95
  96     // and size for mprotect should be exact page multiple
  97     // so round down, add one
  98     p->protectSize = (itemSize & ~(pageSize-1)) + pageSize;
  99   }
 100 #else
 101
 102   // normal version
 103   p->head = RUNMALLOC( p->itemSize );
 104
 105   if( p->initFreshlyAllocated != NULL ) {
 106     p->initFreshlyAllocated( p->head );
 107   }
 108
 109   p->head->next = NULL;
 110   p->tail       = p->head;
 111 #endif
 112
 113   return p;
 114 }
 115
 116
 117
 118 #ifdef MEMPOOL_DETECT_MISUSE
 119
 120 static inline void poolfreeinto( MemPool* p, void* ptr ) {
 121   // don't actually return memory to the pool, just lock
 122   // it up tight so first code to touch it badly gets caught
 123   // also, mprotect automatically protects full pages
 124   if( mprotect( ptr, p->protectSize, PROT_NONE ) != 0 ) {
 125
 126     switch( errno ) {
 127
 128     case ENOMEM: {
 129       printf( "mprotect failed, ENOMEM.\n" );
 130     } break;
 131
 132     default:
 133       printf( "mprotect failed, errno=%d.\n", errno );
 134     }
 135
 136     exit( -1 );
 137   }
 138 }
 139
 140 #else
 141
 142 // normal version
 143 static inline void poolfreeinto( MemPool* p, void* ptr ) {
 144
 145   MemPoolItem* tailCurrent;
 146   MemPoolItem* tailActual;
 147
 148   // set up the now unneeded record to as the tail of the
 149   // free list by treating its first bytes as next pointer,
 150   MemPoolItem* tailNew = (MemPoolItem*) ptr;
 151   tailNew->next = NULL;
 152
 153   while( 1 ) {
 154     // make sure the null happens before the insertion,
 155     // also makes sure that we reload tailCurrent, etc..
 156     BARRIER();
 157
 158     tailCurrent = p->tail;
 159     tailActual = (MemPoolItem*)
 160       CAS( &(p->tail),         // ptr to set
 161            (INTPTR) tailCurrent, // current tail's next should be NULL
 162            (INTPTR) tailNew      // try set to our new tail
 163            );
 164     if( tailActual == tailCurrent ) {
 165       // success, update tail
 166       tailCurrent->next = tailNew;
 167       return;
 168     }
 169
 170     // if CAS failed, retry entire operation
 171   }
 172 }
 173 #endif
 174
 175
 176
 177 #ifdef MEMPOOL_DETECT_MISUSE
 178
 179 static inline void* poolalloc( MemPool* p ) {
 180   // put the memory we intend to expose to client
 181   // on a page-aligned boundary, always return
 182   // new memory
 183   INTPTR nonAligned = (INTPTR) RUNMALLOC( p->allocSize );
 184
 185   void* newRec = (void*)((nonAligned + pageSize-1) & ~(pageSize-1));
 186
 187   //printf( "PageSize is %d or 0x%x.\n", (INTPTR)pageSize, (INTPTR)pageSize );
 188   //printf( "itemSize is 0x%x and allocSize is 0x%x.\n", (INTPTR)p->itemSize, (INTPTR)p->allocSize );
 189   //printf( "Allocation returned 0x%x to 0x%x,\n",   (INTPTR)nonAligned, (INTPTR)nonAligned + (INTPTR)(p->allocSize) );
 190   //printf( "Intend to use       0x%x to 0x%x,\n\n", (INTPTR)newRec,     (INTPTR)newRec     + (INTPTR)(p->itemSize)  );
 191
 192   // intentionally touch the top of the new, aligned record in terms of the
 193   // pages that will be locked when it eventually is free'd
 194   INTPTR topOfRec = (INTPTR)newRec;
 195   topOfRec += p->protectSize - 1;
 196   ((char*)topOfRec)[0] = 0x1;
 197
 198
 199
 200   if( p->initFreshlyAllocated != NULL ) {
 201     p->initFreshlyAllocated( newRec );
 202   }
 203
 204   return newRec;
 205 }
 206
 207 #else
 208
 209 // normal version
 210 static inline void* poolalloc( MemPool* p ) {
 211
 212   // to protect CAS in poolfree from dereferencing
 213   // null, treat the queue as empty when there is
 214   // only one item.  The dequeue operation is only
 215   // executed by the thread that owns the pool, so
 216   // it doesn't require an atomic op
 217   MemPoolItem* headCurrent = p->head;
 218   MemPoolItem* next=headCurrent->next;
 219   int i;
 220   if(next == NULL) {
 221     // only one item, so don't take from pool
 222     void* newRec = RUNMALLOC( p->itemSize );
 223
 224     if( p->initFreshlyAllocated != NULL ) {
 225       p->initFreshlyAllocated( newRec );
 226     }
 227
 228     return newRec;
 229   }
 230
 231   p->head = next;
 232
 233   asm volatile( "prefetcht0 (%0)" :: "r" (next));
 234   next=(MemPoolItem*)(((char *)next)+CACHELINESIZE);
 235   asm volatile( "prefetcht0 (%0)" :: "r" (next));
 236
 237   return (void*)headCurrent;
 238 }
 239 #endif
 240
 241
 242
 243 static void pooldestroy( MemPool* p ) {
 244
 245 #ifndef MEMPOOL_DETECT_MISUSE
 246   MemPoolItem* i = p->head;
 247   MemPoolItem* n;
 248
 249   while( i != NULL ) {
 250     n = i->next;
 251     free( i );
 252     i = n;
 253   }
 254 #endif
 255
 256   free( p );
 257 }
 258
 259
 260 #endif // ___MEMPOOL_H__
 261
 262
 263
 264
 265
 266
 267
 268
 269
 270