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