4 //////////////////////////////////////////////////////////
6 // A memory pool implements POOLCREATE, POOLALLOC and
7 // POOLFREE to improve memory allocation by reusing records.
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.
15 // poolfree adds newly freed records to the list BACK
17 // poolalloc either takes records from FRONT or mallocs
19 //////////////////////////////////////////////////////////
27 #define CACHELINESIZE 64
28 #define DQ_POP_EMPTY NULL
29 #define DQ_POP_ABORT NULL
32 typedef struct sqMemPoolItem_t {
36 typedef struct sqMemPool_t {
40 // avoid cache line contention between producer/consumer...
41 char buffer[CACHELINESIZE];
47 typedef struct dequeItem_t {
49 struct dequeItem_t * next;
53 typedef struct deque_t {
55 // avoid cache line contention between producer/consumer...
56 char buffer[CACHELINESIZE - sizeof(void*)];
61 #define EXTRACTPTR(x) (x&0x0000ffffffffffff)
62 #define INCREMENTTAG 0x0001000000000000
64 // the memory pool must always have at least one
66 static void dqInit(deque *q) {
67 q->head = calloc(1, sizeof(dequeItem) );
70 q->objret.itemSize=sizeof(dequeItem);
71 q->objret.head=calloc(1, sizeof(dequeItem));
72 q->objret.head->next=NULL;
73 q->objret.tail=q->objret.head;
76 static inline void tagpoolfreeinto(sqMemPool* p, void* ptr, void *realptr) {
77 // set up the now unneeded record to as the tail of the
78 // free list by treating its first bytes as next pointer,
79 sqMemPoolItem* tailNew = (sqMemPoolItem*) realptr;
82 sqMemPoolItem* tailCurrent=(sqMemPoolItem *)LOCKXCHG((INTPTR *) &p->tail, (INTPTR) realptr);
83 tailCurrent->next=(sqMemPoolItem *) ptr;
86 static inline void* tagpoolalloc(sqMemPool* p) {
87 // to protect CAS in poolfree from dereferencing
88 // null, treat the queue as empty when there is
89 // only one item. The dequeue operation is only
90 // executed by the thread that owns the pool, so
91 // it doesn't require an atomic op
92 sqMemPoolItem* headCurrent = p->head;
93 sqMemPoolItem* realHead=(sqMemPoolItem *) EXTRACTPTR((INTPTR)headCurrent);
94 sqMemPoolItem* next=realHead->next;
97 // only one item, so don't take from pool
98 sqMemPoolItem * newitem=(sqMemPoolItem *) RUNMALLOC(p->itemSize);
99 ((dequeItem *)newitem)->next=NULL;
104 sqMemPoolItem* realNext=(sqMemPoolItem *) EXTRACTPTR((INTPTR)next);
105 asm volatile ( "prefetcht0 (%0)" :: "r" (realNext));
106 realNext=(sqMemPoolItem*)(((char *)realNext)+CACHELINESIZE);
107 asm volatile ( "prefetcht0 (%0)" :: "r" (realNext));
109 return (void*)headCurrent;
115 // in: a ptr, expected old, desired new
116 // return: actual old
118 // Pass in a ptr, what you expect the old value is and
119 // what you want the new value to be.
120 // The CAS returns what the value is actually: if it matches
121 // your proposed old value then you assume the update was successful,
122 // otherwise someone did CAS before you, so try again (the return
123 // value is the old value you will pass next time.)
125 static inline void dqPushBottom(deque* p, void* work) {
126 dequeItem *ptr=(dequeItem *) tagpoolalloc(&p->objret);
127 dequeItem *realptr=(dequeItem *) EXTRACTPTR((unsigned INTPTR)ptr);
128 ptr=(dequeItem *) (((unsigned INTPTR)ptr)+INCREMENTTAG);
131 //thread unsafe enqueue...only works if one thread enqueue to a queue
136 static inline void* dqPopTopSelf(deque *p) {
139 dequeItem *ptr=p->head;
140 dequeItem *realptr=(dequeItem *) EXTRACTPTR((INTPTR)ptr);
141 dequeItem *next=realptr->next;
142 //remove if we can..steal work no matter what
143 if (likely(next!=NULL)) {
144 if (((dequeItem *)CAS(&(p->head),(INTPTR)ptr, (INTPTR)next))!=ptr)
147 item=(void *)LOCKXCHG((unsigned INTPTR*) &(realptr->work), (unsigned INTPTR) item);
150 tagpoolfreeinto(&p->objret,ptr, realptr);
151 if (item==NULL&&tryagain) {
158 if (realptr->work!=NULL)
159 item=(void *) LOCKXCHG((unsigned INTPTR*) &(realptr->work), (unsigned INTPTR) item);
165 static inline void* dqPopTop(deque *p) {
166 dequeItem *ptr=p->head;
167 dequeItem *realptr=(dequeItem *) EXTRACTPTR((INTPTR)ptr);
168 dequeItem *next=realptr->next;
169 //remove if we can..steal work no matter what
170 if (likely(next!=NULL)) {
171 if (((dequeItem *)CAS(&(p->head),(INTPTR)ptr, (INTPTR)next))!=ptr)
174 item=(void *)LOCKXCHG((unsigned INTPTR*) &(realptr->work), (unsigned INTPTR) item);
177 tagpoolfreeinto(&p->objret,ptr, realptr);
181 if (realptr->work!=NULL)
182 item=(void *) LOCKXCHG((unsigned INTPTR*) &(realptr->work), (unsigned INTPTR) item);
187 #define dqPopBottom dqPopTopSelf
189 #endif // ___MEMPOOL_H__