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 #include "mlp_lock.h"
  23
  24
  25 // The cache line size is set for the AMD Opteron 6168 (dc-10)
  26 // that has L1 and L2 cache line sizes of 64 bytes.  Source:
  27 // http://www.cs.virginia.edu/~skadron/cs451/opteron/opteron.ppt
  28 #define CACHELINESIZE 64
  29
  30
  31 typedef struct MemPoolItem_t {
  32   void* next;
  33 } MemPoolItem;
  34
  35
  36 typedef struct MemPool_t {
  37   int itemSize;
  38   MemPoolItem* head;
  39
  40   // avoid cache line contention between producer/consumer...
  41   char buffer[CACHELINESIZE - sizeof(void*)];
  42
  43   MemPoolItem* tail;
  44 } MemPool;
  45
  46
  47 // the memory pool must always have at least one
  48 // item in it
  49 static MemPool* poolcreate( int itemSize ) {
  50   MemPool* p    = calloc( 1, sizeof( MemPool ) );
  51   p->itemSize   = itemSize;
  52   p->head       = calloc( 1, itemSize );
  53   p->head->next = NULL;
  54   p->tail       = p->head;
  55 }
  56
  57
  58 // CAS
  59 // in: a ptr, expected old, desired new
  60 // return: actual old
  61 //
  62 // Pass in a ptr, what you expect the old value is and
  63 // what you want the new value to be.
  64 // The CAS returns what the value is actually: if it matches
  65 // your proposed old value then you assume the update was successful,
  66 // otherwise someone did CAS before you, so try again (the return
  67 // value is the old value you will pass next time.)
  68
  69 static inline void poolfreeinto( MemPool* p, void* ptr ) {
  70
  71   MemPoolItem* tailCurrent;
  72   MemPoolItem* tailActual;
  73
  74   // set up the now unneeded record to as the tail of the
  75   // free list by treating its first bytes as next pointer,
  76   MemPoolItem* tailNew = (MemPoolItem*) ptr;
  77   tailNew->next = NULL;
  78
  79   while( 1 ) {
  80     // make sure the null happens before the insertion,
  81     // also makes sure that we reload tailCurrent, etc..
  82     BARRIER();
  83
  84     tailCurrent = p->tail;
  85     tailActual = (MemPoolItem*)
  86       CAS( &(p->tail),         // ptr to set
  87            (long) tailCurrent, // current tail's next should be NULL
  88            (long) tailNew      // try set to our new tail
  89            );
  90     if( tailActual == tailCurrent ) {
  91       // success, update tail
  92       tailCurrent->next = tailNew;
  93       return;
  94     }
  95
  96     // if CAS failed, retry entire operation
  97   }
  98 }
  99
 100
 101 static inline void* poolalloc( MemPool* p ) {
 102
 103   // to protect CAS in poolfree from dereferencing
 104   // null, treat the queue as empty when there is
 105   // only one item.  The dequeue operation is only
 106   // executed by the thread that owns the pool, so
 107   // it doesn't require an atomic op
 108   MemPoolItem* headCurrent = p->head;
 109
 110   if( headCurrent->next == NULL ) {
 111     // only one item, so don't take from pool
 112     return calloc( 1, p->itemSize );
 113   }
 114
 115   p->head = headCurrent->next;
 116   return headCurrent;
 117 }
 118
 119
 120 static void pooldestroy( MemPool* p ) {
 121   MemPoolItem* i = p->head;
 122   MemPoolItem* n;
 123
 124   while( i != NULL ) {
 125     n = i->next;
 126     free( i );
 127     i = n;
 128   }
 129
 130   free( p );
 131 }
 132
 133
 134 #endif // ___MEMPOOL_H__
 135
 136
 137
 138
 139
 140
 141
 142
 143
 144