00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #ifndef AMINO_SAFE_MEMORY_RECLAIM
00025 #define AMINO_SAFE_MEMORY_RECLAIM
00026
00027 #include <cassert>
00028 #include <algorithm>
00029 #include <iostream>
00030 #include <vector>
00031 #include <string.h>
00032 #include <stdexcept>
00033
00034 #include <amino/stdatomic.h>
00035 #include <amino/util.h>
00046 #define PTHREAD
00047
00048 #ifdef PTHREAD
00049 #include <pthread.h>
00050 #endif
00051
00052 #ifdef DEBUG
00053 #include <sys/time.h>
00054 #endif
00055
00056 namespace internal {
00057
00058 using namespace std;
00065 template<typename T> class SMRListNode {
00066 public:
00067 SMRListNode* next;
00068 T data;
00069 };
00070
00084 template<typename T, int K> class HPRecType {
00085 public:
00086 typedef T NodeType;
00087 typedef SMRListNode<NodeType*> SMR_Node;
00088
00089 volatile NodeType *hp[K];
00090 HPRecType *next;
00091
00092 atomic<bool> active;
00093
00094
00095
00096
00097
00098
00099 SMR_Node *rlist;
00100
00101
00102
00103
00104
00105 int rcount;
00106
00107
00108
00109
00110
00111 int nrThreads;
00112
00113 #ifdef FREELIST
00114 #define MAX_FREE_NODES 32
00115 SMR_Node *frListSMR;
00116 NodeType * frListData[MAX_FREE_NODES];
00117
00118 int fr_smr_count;
00119 int fr_data_count;
00120
00121 NodeType * allocDataNode() {
00122 if(fr_data_count==0) {
00123 return new NodeType();
00124 }
00125 fr_data_count--;
00126
00127 frListData[fr_data_count]->~NodeType();
00128 return new (frListData[fr_data_count]) NodeType();
00129 }
00130
00131 SMR_Node * allocSMRNode() {
00132 if(fr_smr_count==0) {
00133 return new SMR_Node();
00134 }
00135 fr_smr_count--;
00136 SMR_Node * tmp = frListSMR;
00137 frListSMR = frListSMR->next;
00138
00139 tmp->~SMR_Node();
00140 return new (tmp) SMR_Node();
00141 }
00142
00143 void freeData(NodeType * node) {
00144 if(fr_data_count<MAX_FREE_NODES) {
00145 frListData[fr_data_count] = node;
00146 fr_data_count++;
00147 }
00148 else
00149 delete node;
00150 }
00151
00152 void freeSMRNode(SMR_Node * smrNode) {
00153 if(fr_smr_count<MAX_FREE_NODES) {
00154 fr_smr_count++;
00155 smrNode->next = frListSMR;
00156 frListSMR=smrNode;
00157 }
00158 else
00159 delete smrNode;
00160 }
00161 #endif
00162
00163 HPRecType() {
00164 memset(this, 0, sizeof(HPRecType));
00165 }
00166
00167 ~HPRecType() {
00168 #ifdef FREELIST
00169 for(int i=0;i<fr_smr_count;i++) {
00170 SMR_Node * tmp = frListSMR->next;
00171 delete frListSMR;
00172 frListSMR = tmp;
00173 }
00174
00175 for(int i=0;i<fr_data_count;i++) {
00176 delete frListData[i];
00177 }
00178 #endif
00179
00180 SMRListNode<NodeType *> *tmpListNode;
00181
00182 while (rlist != NULL) {
00183 tmpListNode = rlist;
00184 rlist = rlist->next;
00185 delete tmpListNode->data;
00186 delete tmpListNode;
00187 #ifdef DEBUG
00188 rcount--;
00189 #endif
00190 }
00191 #ifdef DEBUG
00192 if(rcount)
00193 {
00194 cout<<"fatal error: rcount or freeCount not zeor"<<endl;
00195 cout<<"rcount="<<rcount<<endl;
00196 }
00197 #endif
00198 }
00199 };
00200
00205 template<typename T> class SMRThreadLocal {
00206 private:
00207 #ifdef PTHREAD
00208 pthread_key_t key;
00209 #endif
00210 public:
00211 SMRThreadLocal(void(*destroy)(void *)) {
00212 #ifdef PTHREAD
00213 int ret = pthread_key_create(&key, destroy);
00214 if(ret != 0){
00215 throw std::logic_error("Create pthread local");
00216 }
00217 #ifdef DEBUG
00218
00219 #endif
00220 #endif
00221 }
00222
00223 ~SMRThreadLocal() {
00224 #ifdef PTHREAD
00225 #ifdef DEBUG
00226
00227 #endif
00228 pthread_key_delete(key);
00229 #endif
00230 }
00231
00232 T get() {
00233 #ifdef PTHREAD
00234 return (T) pthread_getspecific(key);
00235 #endif
00236 }
00237
00238 void set(T t) {
00239 #ifdef PTHREAD
00240 int res = pthread_setspecific(key, (void *) t);
00241 if(res!=0)
00242 throw std::logic_error("Set pthread local");
00243 #endif
00244 }
00245 };
00246
00258 template<typename TT, int K> void retireHPRec(void * thr_local) {
00259 HPRecType<TT, K> *my_hprec = (HPRecType<TT, K> *) thr_local;
00260 if (my_hprec != NULL) {
00261 for (int i = 0; i < K; i++)
00262 my_hprec->hp[i] = NULL;
00263 my_hprec->active = false;
00264 }
00265 }
00266
00267 template<typename T, int K> class SMR;
00268
00277 template<typename T, int K>
00278 SMR<T, K> * getSMR() {
00279 static SMR<T, K> global_smr;
00280 return &global_smr;
00281 }
00282
00302 template<typename T, int K> class SMR {
00303 public:
00304 typedef T NodeType;
00305 typedef HPRecType<NodeType, K> HP_Rec;
00306 typedef SMRListNode<NodeType*> SMR_Node;
00307 private:
00308 SMRThreadLocal<HP_Rec *> * thread_local;
00309
00310
00311
00312
00313
00314 atomic<HP_Rec *> head_hprec;
00315
00316
00317 atomic_uint hp_count;
00318
00322 static const int MINIMAL_RLIST_LEN = 16;
00323
00330 int RH;
00331
00337 void scan(HP_Rec* head) {
00338
00339 HP_Rec *hprec = head;
00340 volatile NodeType *hptr;
00341 unsigned long pc, nrcount;
00342 SMR_Node *tmpList = NULL;
00343
00344 HP_Rec *my_hprec = thread_local->get();
00345 SMR_Node *rlist = my_hprec->rlist;
00346 unsigned int max_threads = hprec->nrThreads;
00347
00348
00349 volatile NodeType* plist[max_threads * K];
00350
00351
00352 pc = 0;
00353 for (; hprec != NULL; hprec = hprec->next) {
00354 for (int j = 0; j < K; j++) {
00355 hptr = hprec->hp[j];
00356 if (hptr != NULL)
00357 plist[pc++] = hptr;
00358 }
00359 }
00360
00361 assert(pc <= max_threads * K);
00362
00363 sort(plist, plist + pc);
00364 volatile NodeType ** newlast = unique(plist, plist + pc);
00365
00366 nrcount = 0;
00367 while (rlist != NULL) {
00368 SMR_Node *tmpListNode = rlist;
00369 rlist = rlist->next;
00370 if (binary_search(plist, newlast, tmpListNode->data)) {
00371
00372
00373 tmpListNode->next = tmpList;
00374 tmpList = tmpListNode;
00375 nrcount++;
00376 } else {
00377
00378 #ifdef FREELIST
00379 my_hprec->freeData(tmpListNode->data);
00380 my_hprec->freeSMRNode(tmpListNode);
00381 #else
00382 delete tmpListNode->data;
00383 delete tmpListNode;
00384 #endif
00385 }
00386 }
00387
00388 my_hprec->rlist = tmpList;
00389 my_hprec->rcount = nrcount;
00390 }
00391
00405 void mergeList(SMR_Node **oldList, int *countOld,
00406 SMRListNode<NodeType *> **newList, int *countNew) {
00407 SMR_Node *tmpListNode;
00408 if (oldList == NULL || *oldList == NULL)
00409 return;
00410 tmpListNode = *oldList;
00411 while (tmpListNode->next != NULL)
00412 tmpListNode = tmpListNode->next;
00413 tmpListNode->next = *newList;
00414 *newList = *oldList;
00415 *countNew += *countOld;
00416 *oldList = NULL;
00417 *countOld = 0;
00418 }
00419
00426 void helpScan(HP_Rec *head) {
00427 HP_Rec *hprec;
00428 HP_Rec *my_hprec = thread_local->get();
00429
00430 for (hprec = head; hprec != NULL; hprec = hprec->next) {
00431
00432
00433 if (hprec->active.load(memory_order_relaxed)
00434 == true) {
00435 continue;
00436 }
00437
00438
00439 bool b = false;
00440 if (hprec->active.compare_swap(b, true) == false) {
00441 continue;
00442 }
00443
00444
00445 mergeList(&hprec->rlist, &hprec->rcount, &my_hprec->rlist,
00446 &my_hprec->rcount);
00447
00448 hprec->active.store(false, memory_order_relaxed);
00449 }
00450 }
00451
00461 HP_Rec * allocHPRec() {
00462 HP_Rec *hprec;
00463 HP_Rec *oldhead;
00464
00465
00466 for (hprec = head_hprec.load(memory_order_relaxed); hprec != NULL; hprec
00467 = hprec->next) {
00468 if (hprec->active.load(memory_order_relaxed) == true) {
00469 continue;
00470 }
00471 bool b = false;
00472
00473 if (!hprec->active.compare_swap(b, true)) {
00474 continue;
00475 }
00476
00477 thread_local->set(hprec);
00478 return hprec;
00479 }
00480
00481
00482 hp_count++;
00483 if (hp_count.load(memory_order_relaxed) >= MINIMAL_RLIST_LEN / 2) {
00484 RH = hp_count.load(memory_order_relaxed) * 2;
00485 }
00486
00487
00488 hprec = new HP_Rec ();
00489
00490 hprec->active = true;
00491
00492
00493 do {
00494 oldhead = head_hprec.load(memory_order_relaxed);
00495 hprec->next = oldhead;
00496 hprec->nrThreads = hp_count.load(memory_order_relaxed);
00497 }while (head_hprec.compare_swap(oldhead, hprec) == false);
00498
00499
00500 thread_local->set(hprec);
00501 return hprec;
00502 }
00503
00504 #ifdef DEBUG
00505 public:
00506
00507 atomic_uint newAllocs;
00508 atomic_uint total_requests;
00509 atomic_long t_newNode;
00510 atomic_long t_retireNode;
00511 #endif
00512 private:
00513 SMR() {
00514 thread_local
00515 = new SMRThreadLocal<HP_Rec*> (&internal::retireHPRec<NodeType, K>);
00516 hp_count = 0;
00517 RH = MINIMAL_RLIST_LEN;
00518 head_hprec.store(NULL, memory_order_relaxed);
00519 #ifdef DEBUG
00520 newAllocs = 0;
00521 total_requests = 0;
00522 t_newNode = 0;
00523 t_retireNode = 0;
00524 #endif
00525 }
00526 public:
00527 friend SMR<NodeType, K> * getSMR<NodeType, K> ();
00528
00529 ~SMR() {
00530 HP_Rec *hprec =
00531 head_hprec.load(memory_order_relaxed);
00532 HP_Rec *tmp_hprec = NULL;
00533 while (hprec != NULL) {
00534 tmp_hprec = hprec;
00535 #ifdef DEBUG
00536 if(tmp_hprec->active.load(memory_order_relaxed)) {
00537 HP_Rec *my_hprec = thread_local->get();
00538 if(tmp_hprec!=my_hprec)
00539 cout << "Warning some HP is active" << endl;
00540 }
00541 #endif
00542 hprec = hprec->next;
00543 delete tmp_hprec;
00544 }
00545 delete thread_local;
00546 }
00547
00555 void delNode(NodeType* node) {
00556 delNode(getHPRec(), node);
00557 }
00558
00568 void delNode(HP_Rec *my_hprec, NodeType* node) {
00569
00570 compiler_barrier();
00571 #ifdef DEBUG
00572 struct timeval start, end;
00573 gettimeofday(&start, NULL);
00574 #endif
00575 #ifdef FREELIST
00576 SMR_Node *tmpListNode = my_hprec->allocSMRNode();
00577 #else
00578 SMR_Node *tmpListNode = new SMR_Node();
00579 #endif
00580
00581 tmpListNode->data = node;
00582 tmpListNode->next = my_hprec->rlist;
00583 my_hprec->rlist = tmpListNode;
00584 my_hprec->rcount++;
00585 if (my_hprec->rcount >= RH) {
00586 HP_Rec *head =
00587 head_hprec.load(memory_order_relaxed);
00588 helpScan(head);
00589 scan(head);
00590 }
00591 #ifdef DEBUG
00592 gettimeofday(&end, NULL);
00593 t_retireNode += 1000000*(end.tv_sec-start.tv_sec) + (end.tv_usec-start.tv_usec);
00594 #endif
00595
00596 compiler_barrier();
00597 }
00598
00604 HP_Rec * getHPRec() {
00605 HP_Rec *my_hprec = thread_local->get();
00606 if (my_hprec == NULL) {
00607 my_hprec = allocHPRec();
00608 }
00609 return my_hprec;
00610 }
00611
00629 void retire(HP_Rec * my_hprec, int index) {
00630 my_hprec->hp[index] = NULL;
00631 }
00632
00633 void retire(HP_Rec * my_hprec, NodeType *p) {
00634 for(int i = 0; i < K; ++i) {
00635 if(my_hprec->hp[i] == p) {
00636 my_hprec->hp[i] = NULL;
00637 }
00638 }
00639 }
00640
00655 void retire(int index) {
00656 retire(getHPRec(), index);
00657 }
00658
00659 void retire(NodeType *p) {
00660 retire(getHPRec(), p);
00661 }
00662
00667 NodeType * newNode() {
00668 return newNode(getHPRec());
00669 }
00670
00678 NodeType * newNode(HP_Rec * my_hprec) {
00679 return my_hprec->allocDataNode();
00680 }
00681
00693 void employ(int index, NodeType * pointer) {
00694 employ(getHPRec(), index, pointer);
00695 }
00696
00708 void employ(HP_Rec * my_hprec, int index, NodeType* pointer) {
00709 assert(index < K);
00710 my_hprec->hp[index] = pointer;
00711 #ifdef X86
00712
00717 NodeType * tmp;
00718 __asm__ __volatile__(
00719 "MOV %1, %0\n\t"
00720 :"=r"(tmp)
00721 :"m"(my_hprec->hp[index])
00722 );
00723 #endif
00724 }
00725 };
00726 }
00727
00728 #endif