Robust/src/Tests/memPool/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 //  EACH THREAD should have one local pool.
  10 //
  11 //
  12 //
  13 //  This implementation uses a lock-free singly-linked list
  14 //  to store reusable records.  The algorithm is a much-
  15 //  simplified version of the list described in Valois '95
  16 //  because it supports less features.
  17 //
  18 //  poolfree adds newly freed records to the list FRONT
  19 //
  20 //  poolalloc either takes records from BACK or mallocs
  21 //
  22 //  Note the use of dummy nodes between every valid list
  23 //  element.  This is a crucial aspect in allowing the
  24 //  implementation to have simple CAS logic.
  25 //
  26 //  Empty list:
  27 //  dummyItem -->     1stPTR --> NULL
  28 //  head --> tail --> 2ndPTR --> 1stPTR
  29 //
  30 //  Prepare a new record to add at head:
  31 //  Record --> 1stPTR --> currentHead
  32 //             2ndPTR --> 1stPTR
  33 //  CAS( &head,
  34 //       head,
  35 //       2ndPtr )
  36 //
  37 //  Remove a record from tail:
  38 //
  39 //
  40 //
  41 //
  42 //
  43 //////////////////////////////////////////////////////////
  44
  45 #include <stdlib.h>
  46 #include "mlp_lock.h"
  47
  48
  49 typedef struct MemPoolItem_t {
  50   void* next;
  51 } MemPoolItem;
  52
  53
  54 typedef struct MemPool_t {
  55   int itemSize;
  56   MemPoolItem* head;
  57
  58   // avoid cache line contention between producer/consumer...
  59   char buffer[CACHELINESIZE - sizeof(void*)];
  60
  61   MemPoolItem* tail;
  62 } MemPool;
  63
  64
  65 // the memory pool must always have at least one
  66 // item in it
  67 MemPool* poolcreate( int itemSize ) {
  68   MemPool* p    = malloc( sizeof( MemPool ) );
  69   p->itemSize   = itemSize;
  70   p->head       = malloc( itemSize );
  71   p->head->next = NULL;
  72   p->tail       = p->head;
  73 }
  74
  75
  76 // CAS
  77 // in: a ptr, expected old, desired new
  78 // return: actual old
  79 //
  80 // Pass in a ptr, what you expect the old value is and
  81 // what you want the new value to be.
  82 // The CAS returns what the value is actually: if it matches
  83 // your proposed old value then you assume the update was successful,
  84 // otherwise someone did CAS before you, so try again (the return
  85 // value is the old value you will pass next time.)
  86
  87 static inline void poolfree( MemPool* p, void* ptr ) {
  88
  89   MemPoolItem* tailCurrent;
  90   MemPoolItem* tailActual;
  91
  92   // set up the now unneeded record to as the tail of the
  93   // free list by treating its first bytes as next pointer,
  94   MemPoolItem* tailNew = (MemPoolItem*) ptr;
  95   newTail->next = NULL;
  96
  97   while( 1 ) {
  98     // make sure the null happens before the insertion,
  99     // also makes sure that we reload tailCurrent, etc..
 100     BARRIER();
 101
 102     tailCurrent = p->tail;
 103     tailActual  = CAS( &(p->tail),  // ptr to set
 104                        tailCurrent, // current tail's next should be NULL
 105                        tailNew );   // try set to our new tail
 106     if( tailActual == tailCurrent ) {
 107       // success, update tail
 108       tailCurrent->next = newTail;
 109       return;
 110     }
 111
 112     // if CAS failed, retry entire operation
 113   }
 114 }
 115
 116
 117 static inline void* poolalloc( MemPool* p ) {
 118
 119   // to protect CAS in poolfree from dereferencing
 120   // null, treat the queue as empty when there is
 121   // only one item.  The dequeue operation is only
 122   // executed by the thread that owns the pool, so
 123   // it doesn't require an atomic op
 124   MemPoolItem* headCurrent = p->head;
 125
 126   if( headCurrent->next == NULL ) {
 127     // only one item, so don't take from pool
 128     return calloc( 1, p->itemSize );
 129   }
 130
 131   p->head = headCurrent->next;
 132   return headCurrent;
 133 }
 134
 135
 136 #endif // ___MEMPOOL_H__
 137
 138
 139
 140
 141
 142
 143
 144
 145
 146