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 #include "runtime.h"
  32 #include "mem.h"
  33 #include "mlp_lock.h"
  34
  35
  36 #define CACHELINESIZE 64
  37
  38
  39
  40 typedef struct MemPoolItem_t {
  41   struct MemPoolItem_t* next;
  42 } MemPoolItem;
  43
  44
  45 typedef struct MemPool_t {
  46   int itemSize;
  47
  48   // only invoke this on items that are
  49   // actually new, saves time for reused
  50   // items
  51   void (*initFreshlyAllocated)(void*);
  52
  53 #ifdef MEMPOOL_DETECT_MISUSE
  54   int allocSize;
  55   int protectSize;
  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 alloc by one page
  87     p->allocSize = itemSize + pageSize;
  88
  89     // and size for mprotect should be exact page multiple
  90     p->protectSize = itemSize;
  91   } else {
  92     // otherwise, round down to a page size, then add two
  93     p->allocSize = (itemSize & ~(pageSize-1)) + 2*pageSize;
  94
  95     // and size for mprotect should be exact page multiple
  96     // so round down, add one
  97     p->protectSize = (itemSize & ~(pageSize-1)) + pageSize;
  98   }
  99 #else
 100
 101   // normal version
 102   p->head = RUNMALLOC(p->itemSize);
 103
 104   if( p->initFreshlyAllocated != NULL ) {
 105     p->initFreshlyAllocated(p->head);
 106   }
 107
 108   p->head->next = NULL;
 109   p->tail       = p->head;
 110 #endif
 111
 112   return p;
 113 }
 114
 115
 116
 117 #ifdef MEMPOOL_DETECT_MISUSE
 118
 119 static inline void poolfreeinto(MemPool* p, void* ptr) {
 120   // don't actually return memory to the pool, just lock
 121   // it up tight so first code to touch it badly gets caught
 122   // also, mprotect automatically protects full pages
 123   if( mprotect(ptr, p->protectSize, PROT_NONE) != 0 ) {
 124
 125     switch( errno ) {
 126
 127     case ENOMEM: {
 128       printf("mprotect failed, ENOMEM.\n");
 129     } break;
 130
 131     default:
 132       printf("mprotect failed, errno=%d.\n", errno);
 133     }
 134
 135     printf("itemSize is 0x%x, allocSize is 0x%x, protectSize is 0x%x.\n", (INTPTR)p->itemSize, (INTPTR)p->allocSize, (INTPTR)p->protectSize);
 136     printf("Intended to protect 0x%x to 0x%x,\n\n", (INTPTR)ptr, (INTPTR)ptr + (INTPTR)(p->protectSize) );
 137
 138     exit(-1);
 139   }
 140 }
 141
 142 #else
 143
 144
 145 // normal version
 146 static inline void poolfreeinto(MemPool* p, void* ptr) {
 147   MemPoolItem* tailNew = (MemPoolItem*) ptr;
 148   tailNew->next = NULL;
 149   CFENCE;
 150   MemPoolItem *tailCurrent=(MemPoolItem *) LOCKXCHG((INTPTR *) &p->tail, (INTPTR) tailNew);
 151   tailCurrent->next=tailNew;
 152 }
 153 #endif
 154
 155
 156
 157 #ifdef MEMPOOL_DETECT_MISUSE
 158
 159 static inline void* poolalloc(MemPool* p) {
 160   // put the memory we intend to expose to client
 161   // on a page-aligned boundary, always return
 162   // new memory
 163
 164   INTPTR nonAligned = (INTPTR) RUNMALLOC(p->allocSize);
 165
 166   void* newRec = (void*)((nonAligned + pageSize-1) & ~(pageSize-1));
 167
 168   //printf( "PageSize is %d or 0x%x.\n", (INTPTR)pageSize, (INTPTR)pageSize );
 169   //printf( "itemSize is 0x%x, allocSize is 0x%x, protectSize is 0x%x.\n", (INTPTR)p->itemSize, (INTPTR)p->allocSize, (INTPTR)p->protectSize );
 170   //printf( "Allocation returned 0x%x to 0x%x,\n",   (INTPTR)nonAligned, (INTPTR)nonAligned + (INTPTR)(p->allocSize) );
 171   //printf( "Intend to use       0x%x to 0x%x,\n\n", (INTPTR)newRec,     (INTPTR)newRec     + (INTPTR)(p->itemSize)  );
 172
 173   // intentionally touch the top of the new, aligned record in terms of the
 174   // pages that will be locked when it eventually is free'd
 175   INTPTR topOfRec = (INTPTR)newRec;
 176   topOfRec += p->protectSize - 1;
 177   ((char*)topOfRec)[0] = 0x1;
 178
 179   if( p->initFreshlyAllocated != NULL ) {
 180     p->initFreshlyAllocated(newRec);
 181   }
 182
 183   return newRec;
 184 }
 185
 186 #else
 187
 188 // normal version
 189 static inline void* poolalloc(MemPool* p) {
 190
 191   // to protect CAS in poolfree from dereferencing
 192   // null, treat the queue as empty when there is
 193   // only one item.  The dequeue operation is only
 194   // executed by the thread that owns the pool, so
 195   // it doesn't require an atomic op
 196   MemPoolItem* headCurrent = p->head;
 197   MemPoolItem* next=headCurrent->next;
 198   int i;
 199
 200
 201   if(next == NULL) {
 202     // only one item, so don't take from pool
 203     void *newRec=RUNMALLOC(p->itemSize);
 204     if( p->initFreshlyAllocated != NULL ) {
 205       p->initFreshlyAllocated(newRec);
 206     }
 207     return newRec;
 208   }
 209
 210   p->head = next;
 211
 212   asm volatile ( "prefetcht0 (%0)" :: "r" (next));
 213   next=(MemPoolItem*)(((char *)next)+CACHELINESIZE);
 214   asm volatile ( "prefetcht0 (%0)" :: "r" (next));
 215
 216   return (void*)headCurrent;
 217 }
 218 #endif
 219
 220
 221
 222 static void pooldestroy(MemPool* p) {
 223
 224 #ifndef MEMPOOL_DETECT_MISUSE
 225   MemPoolItem* i = p->head;
 226   MemPoolItem* n;
 227
 228   while( i != NULL ) {
 229     n = i->next;
 230     free(i);
 231     i = n;
 232   }
 233 #endif
 234
 235   free(p);
 236 }
 237
 238
 239 #endif // ___MEMPOOL_H__