From 0d1805f3310b8f2a82678b6e168cf78131bc22c9 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Mon, 13 Apr 2009 22:58:08 +0000 Subject: [PATCH] fix bugs, speedup --- Robust/src/Runtime/STM/stm.c | 91 ++++++++++- Robust/src/Runtime/STM/stmlookup.c | 239 +++++------------------------ Robust/src/Runtime/STM/stmlookup.h | 11 +- Robust/src/Runtime/STM/tm.h | 1 + Robust/src/Runtime/garbage.c | 17 +- Robust/src/Runtime/garbage.h | 3 +- 6 files changed, 144 insertions(+), 218 deletions(-) diff --git a/Robust/src/Runtime/STM/stm.c b/Robust/src/Runtime/STM/stm.c index 1c3a0147..84a0ab64 100644 --- a/Robust/src/Runtime/STM/stm.c +++ b/Robust/src/Runtime/STM/stm.c @@ -220,7 +220,11 @@ int transCommit() { #endif do { /* Look through all the objects in the transaction hash table */ - int finalResponse = traverseCache(); + int finalResponse; + if (c_numelements<(c_size>>3)) + finalResponse= alttraverseCache(); + else + finalResponse= traverseCache(); if(finalResponse == TRANS_ABORT) { #ifdef TRANSSTATS numTransAbort++; @@ -351,6 +355,91 @@ int traverseCache() { } } +/* ================================================== + * traverseCache + * - goes through the transaction cache and + * - decides if a transaction should commit or abort + * ================================================== + */ +int alttraverseCache() { + /* Create info to keep track of objects that can be locked */ + int numoidrdlocked=0; + int numoidwrlocked=0; + void * rdlocked[200]; + void * wrlocked[200]; + int softabort=0; + int i; + void ** oidrdlocked; + void ** oidwrlocked; + if (c_numelements<200) { + oidrdlocked=rdlocked; + oidwrlocked=wrlocked; + } else { + int size=c_numelements*sizeof(void*); + oidrdlocked=malloc(size); + oidwrlocked=malloc(size); + } + chashlistnode_t *curr = c_list; + /* Inner loop to traverse the linked list of the cache lookupTable */ + while(curr != NULL) { + //if the first bin in hash table is empty + objheader_t * headeraddr=&((objheader_t *) curr->val)[-1]; + + unsigned int version = headeraddr->version; + objheader_t *header=(objheader_t *) (((char *)curr->key)-sizeof(objheader_t)); + + if(STATUS(headeraddr) & DIRTY) { + /* Read from the main heap and compare versions */ + if(write_trylock(&header->lock)) { //can aquire write lock + if (version == header->version) {/* versions match */ + /* Keep track of objects locked */ + oidwrlocked[numoidwrlocked++] = OID(header); + } else { + oidwrlocked[numoidwrlocked++] = OID(header); + transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked); + return TRANS_ABORT; + } + } else { /* cannot aquire lock */ + if(version == header->version) /* versions match */ + softabort=1; + else { + transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked); + return TRANS_ABORT; + } + } + } else { + /* Read from the main heap and compare versions */ + if(read_trylock(&header->lock)) { //can further aquire read locks + if(version == header->version) {/* versions match */ + oidrdlocked[numoidrdlocked++] = OID(header); + } else { + oidrdlocked[numoidrdlocked++] = OID(header); + transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked); + return TRANS_ABORT; + } + } else { /* cannot aquire lock */ + if(version == header->version) + softabort=1; + else { + transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked); + return TRANS_ABORT; + } + } + } + + curr = curr->lnext; + } + + /* Decide the final response */ + if (softabort) { + transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked); + return TRANS_SOFT_ABORT; + } else { + transCommitProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked); + return TRANS_COMMIT; + } +} + /* ================================== * transAbortProcess diff --git a/Robust/src/Runtime/STM/stmlookup.c b/Robust/src/Runtime/STM/stmlookup.c index f9537c53..26da7e5b 100644 --- a/Robust/src/Runtime/STM/stmlookup.c +++ b/Robust/src/Runtime/STM/stmlookup.c @@ -2,6 +2,7 @@ #include "strings.h" __thread chashlistnode_t *c_table; +__thread chashlistnode_t *c_list; __thread unsigned int c_size; __thread unsigned INTPTR c_mask; __thread unsigned int c_numelements; @@ -22,94 +23,39 @@ void t_chashCreate(unsigned int size, double loadfactor) { c_threshold=size*loadfactor; c_mask = (size << 3)-1; c_numelements = 0; // Initial number of elements in the hash + c_list=NULL; } void t_chashreset() { chashlistnode_t *ptr = c_table; int i; - for(i=0 ; inext; - free(curr); - curr=next; + if (c_numelements<(c_size>>3)) { + chashlistnode_t *top=&ptr[c_size]; + chashlistnode_t *tmpptr=c_list; + while(tmpptr!=NULL) { + chashlistnode_t *next=tmpptr->lnext; + if (tmpptr>=ptr&&tmpptrkey=0; + tmpptr->next=NULL; + } else { + free(tmpptr); + } + tmpptr=next; + } + } else { + for(i=0 ; inext; + free(curr); + curr=next; + } } + bzero(c_table, sizeof(chashlistnode_t)*c_size); } c_numelements = 0; - bzero(c_table, sizeof(chashlistnode_t)*c_size); -} - -chashtable_t *chashCreate(unsigned int size, double loadfactor) { - chashtable_t *ctable; - chashlistnode_t *nodes; - int i; - - if((ctable = calloc(1, sizeof(chashtable_t))) == NULL) { - printf("Calloc error %s %d\n", __FILE__, __LINE__); - return NULL; - } - - // Allocate space for the hash table - if((nodes = calloc(size, sizeof(chashlistnode_t))) == NULL) { - printf("Calloc error %s %d\n", __FILE__, __LINE__); - free(ctable); - return NULL; - } - - ctable->table = nodes; - ctable->loadfactor = loadfactor; - ctable->size = size; - ctable->threshold=size*loadfactor; - ctable->mask = (size << 3)-1; - ctable->numelements = 0; // Initial number of elements in the hash - - - return ctable; -} - -//Finds the right bin in the hash table -static INLINE unsigned int chashFunction(chashtable_t *table, void * key) { - return (((unsigned INTPTR) key) & (table->mask))>>3; //throw away low order bit -} - -//Store objects and their pointers into hash -void chashInsert(chashtable_t *table, void * key, void *val) { - chashlistnode_t *ptr; - - if(table->numelements > (table->threshold)) { - //Resize - unsigned int newsize = table->size << 1; - chashResize(table,newsize); - } - - ptr = &table->table[(((unsigned INTPTR)key)&table->mask)>>3]; - table->numelements++; - - if(ptr->key==0) { - ptr->key=key; - ptr->val=val; - } else { // Insert in the beginning of linked list - chashlistnode_t * node = calloc(1, sizeof(chashlistnode_t)); - node->key = key; - node->val = val; - node->next = ptr->next; - ptr->next=node; - } -} - -// Search for an address for a given oid -INLINE void * chashSearch(chashtable_t *table, void * key) { - //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE - chashlistnode_t *node = &table->table[(((unsigned INTPTR)key) & table->mask)>>3]; - - do { - if(node->key == key) { - return node->val; - } - node = node->next; - } while(node != NULL); - - return NULL; + c_list=NULL; } //Store objects and their pointers into hash @@ -129,12 +75,16 @@ void t_chashInsert(void * key, void *val) { if(ptr->key==0) { ptr->key=key; ptr->val=val; + ptr->lnext=c_list; + c_list=ptr; } else { // Insert in the beginning of linked list chashlistnode_t * node = calloc(1, sizeof(chashlistnode_t)); node->key = key; node->val = val; node->next = ptr->next; ptr->next=node; + node->lnext=c_list; + c_list=node; } } @@ -152,112 +102,6 @@ INLINE void * t_chashSearch(void * key) { return NULL; } - -unsigned int chashRemove(chashtable_t *table, void * key) { - return chashRemove2(table, key)==NULL; - -} - -void * chashRemove2(chashtable_t *table, void * key) { - int index; - chashlistnode_t *curr, *prev; - chashlistnode_t *ptr, *node; - void *value; - - ptr = table->table; - index = chashFunction(table,key); - curr = &ptr[index]; - - for (; curr != NULL; curr = curr->next) { - if (curr->key == key) { // Find a match in the hash table - table->numelements--; // Decrement the number of elements in the global hashtable - if ((curr == &ptr[index]) && (curr->next == NULL)) { // Delete the first item inside the hashtable with no linked list of chashlistnode_t - curr->key = 0; - value=curr->val; - curr->val = NULL; - } else if ((curr == &ptr[index]) && (curr->next != NULL)) { //Delete the first item with a linked list of chashlistnode_t connected - curr->key = curr->next->key; - value=curr->val; - curr->val = curr->next->val; - node = curr->next; - curr->next = curr->next->next; - free(node); - } else { // Regular delete from linked listed - prev->next = curr->next; - value=curr->val; - free(curr); - } - return value; - } - prev = curr; - } - return NULL; -} - -unsigned int chashResize(chashtable_t *table, unsigned int newsize) { - chashlistnode_t *node, *ptr, *curr; // curr and next keep track of the current and the next chashlistnodes in a linked list - unsigned int oldsize; - int isfirst; // Keeps track of the first element in the chashlistnode_t for each bin in hashtable - unsigned int i,index; - unsigned int mask; - - ptr = table->table; - oldsize = table->size; - - if((node = calloc(newsize, sizeof(chashlistnode_t))) == NULL) { - printf("Calloc error %s %d\n", __FILE__, __LINE__); - return 1; - } - - table->table = node; //Update the global hashtable upon resize() - table->size = newsize; - table->threshold = newsize * table->loadfactor; - mask=table->mask = (newsize << 3)-1; - - for(i = 0; i < oldsize; i++) { //Outer loop for each bin in hash table - curr = &ptr[i]; - isfirst = 1; - do { //Inner loop to go through linked lists - void * key; - chashlistnode_t *tmp,*next; - - if ((key=curr->key) == 0) { //Exit inner loop if there the first element is 0 - break; //key = val =0 for element if not present within the hash table - } - next = curr->next; - index = (((unsigned INTPTR)key) & mask) >>3; - tmp=&node[index]; - // Insert into the new table - if(tmp->key == 0) { - tmp->key = curr->key; - tmp->val = curr->val; - if (!isfirst) { - free(curr); - } - }/* - NOTE: Add this case if you change this... - This case currently never happens because of the way things rehash.... - else if (isfirst) { - chashlistnode_t *newnode= calloc(1, sizeof(chashlistnode_t)); - newnode->key = curr->key; - newnode->val = curr->val; - newnode->next = tmp->next; - tmp->next=newnode; - } */ - else { - curr->next=tmp->next; - tmp->next=curr; - } - - isfirst = 0; - curr = next; - } while(curr!=NULL); - } - - free(ptr); //Free the memory of the old hash table - return 0; -} - unsigned int t_chashResize(unsigned int newsize) { chashlistnode_t *node, *ptr, *curr; // curr and next keep track of the current and the next chashlistnodes in a linked list unsigned int oldsize; @@ -267,6 +111,7 @@ unsigned int t_chashResize(unsigned int newsize) { ptr = c_table; oldsize = c_size; + c_list=NULL; if((node = calloc(newsize, sizeof(chashlistnode_t))) == NULL) { printf("Calloc error %s %d\n", __FILE__, __LINE__); @@ -295,6 +140,8 @@ unsigned int t_chashResize(unsigned int newsize) { if(tmp->key == 0) { tmp->key = curr->key; tmp->val = curr->val; + tmp->lnext=c_list; + c_list=tmp; if (!isfirst) { free(curr); } @@ -311,6 +158,8 @@ unsigned int t_chashResize(unsigned int newsize) { else { curr->next=tmp->next; tmp->next=curr; + curr->lnext=c_list; + c_list=curr; } isfirst = 0; @@ -322,23 +171,6 @@ unsigned int t_chashResize(unsigned int newsize) { return 0; } -//Delete the entire hash table -void chashDelete(chashtable_t *ctable) { - int i; - chashlistnode_t *ptr = ctable->table; - - for(i=0 ; isize ; i++) { - chashlistnode_t * curr = ptr[i].next; - while(curr!=NULL) { - chashlistnode_t * next = curr->next; - free(curr); - curr=next; - } - } - free(ptr); - free(ctable); -} - //Delete the entire hash table void t_chashDelete() { int i; @@ -354,4 +186,5 @@ void t_chashDelete() { } free(ptr); c_table=NULL; + c_list=NULL; } diff --git a/Robust/src/Runtime/STM/stmlookup.h b/Robust/src/Runtime/STM/stmlookup.h index e7544748..476716e1 100644 --- a/Robust/src/Runtime/STM/stmlookup.h +++ b/Robust/src/Runtime/STM/stmlookup.h @@ -22,6 +22,7 @@ typedef struct chashlistnode { void * key; void * val; //this can be cast to another type or used to point to a larger structure struct chashlistnode *next; + struct chashlistnode *lnext; } chashlistnode_t; typedef struct chashtable { @@ -41,17 +42,9 @@ unsigned int t_chashResize(unsigned int newsize); void t_chashDelete(); void t_chashreset(); -/* Prototypes for hash*/ -chashtable_t *chashCreate(unsigned int size, double loadfactor); -void chashInsert(chashtable_t *table, void * key, void *val); -void *chashSearch(chashtable_t *table, void * key); //returns val, NULL if not found -unsigned int chashRemove(chashtable_t *table, void * key); //returns -1 if not found -void * chashRemove2(chashtable_t *table, void * key); //returns -1 if not found -unsigned int chashResize(chashtable_t *table, unsigned int newsize); -void chashDelete(chashtable_t *table); -/* end hash */ extern __thread chashlistnode_t *c_table; +extern __thread chashlistnode_t *c_list; extern __thread unsigned int c_size; extern __thread unsigned INTPTR c_mask; extern __thread unsigned int c_numelements; diff --git a/Robust/src/Runtime/STM/tm.h b/Robust/src/Runtime/STM/tm.h index 3227d511..6910348b 100644 --- a/Robust/src/Runtime/STM/tm.h +++ b/Robust/src/Runtime/STM/tm.h @@ -145,6 +145,7 @@ void *objstrAlloc(unsigned int size); __attribute__((pure)) void *transRead(void * oid); int transCommit(); int traverseCache(); +int alttraverseCache(); int transAbortProcess(void **, int *, void **, int *); int transCommmitProcess(void **, int *, void **, int *); void randomdelay(); diff --git a/Robust/src/Runtime/garbage.c b/Robust/src/Runtime/garbage.c index fb6c161f..3fadff44 100644 --- a/Robust/src/Runtime/garbage.c +++ b/Robust/src/Runtime/garbage.c @@ -147,7 +147,7 @@ void fixobjlist(struct objlist * ptr) { } } -void fixtable(chashlistnode_t ** tc_table, unsigned int tc_size) { +void fixtable(chashlistnode_t ** tc_table, chashlistnode_t **tc_list, unsigned int tc_size) { unsigned int mask=(tc_size<<3)-1; chashlistnode_t *node=calloc(tc_size, sizeof(chashlistnode_t)); chashlistnode_t *ptr=*tc_table; @@ -155,6 +155,7 @@ void fixtable(chashlistnode_t ** tc_table, unsigned int tc_size) { unsigned int i; unsigned int index; int isfirst; + chashlistnode_t *newlist=NULL; for(i=0;ikey == 0) { tmp->key = curr->key; tmp->val = curr->val; + tmp->lnext=newlist; + newlist=tmp; if (!isfirst) { free(curr); } @@ -215,8 +218,12 @@ void fixtable(chashlistnode_t ** tc_table, unsigned int tc_size) { newnode->key = curr->key; newnode->val = curr->val; newnode->next = tmp->next; + newnode->lnext=newlist; + newlist=newnode; tmp->next=newnode; } else { + curr->lnext=newlist; + newlist=curr; curr->next=tmp->next; tmp->next=curr; } @@ -226,6 +233,7 @@ void fixtable(chashlistnode_t ** tc_table, unsigned int tc_size) { } free(ptr); (*tc_table)=node; + (*tc_list)=newlist; } #endif @@ -284,8 +292,8 @@ void collect(struct garbagelist * stackptr) { #ifdef STM if (c_table!=NULL) { - fixtable(&c_table, c_size); - fixobjlist(newobjs); + fixtable(&c_table, &c_list, c_size); + fixobjlist(newobjs); } memorybase=NULL; #endif @@ -314,7 +322,7 @@ void collect(struct garbagelist * stackptr) { #endif #ifdef STM if ((*listptr->tc_table)!=NULL) { - fixtable(listptr->tc_table, listptr->tc_size); + fixtable(listptr->tc_table, listptr->tc_list, listptr->tc_size); fixobjlist(listptr->objlist); } *(listptr->base)=NULL; @@ -585,6 +593,7 @@ struct listitem * stopforgc(struct garbagelist * ptr) { #ifdef STM litem->tc_size=c_size; litem->tc_table=&c_table; + litem->tc_list=&c_list; litem->objlist=newobjs; litem->base=&memorybase; #endif diff --git a/Robust/src/Runtime/garbage.h b/Robust/src/Runtime/garbage.h index 7a9dc9c7..597734ed 100644 --- a/Robust/src/Runtime/garbage.h +++ b/Robust/src/Runtime/garbage.h @@ -19,6 +19,7 @@ struct listitem { #ifdef STM unsigned int tc_size; chashlistnode_t **tc_table; + chashlistnode_t **tc_list; struct objlist * objlist; char **base; #endif @@ -40,5 +41,5 @@ int gc_createcopy(void * orig, void **); void * mygcmalloc(struct garbagelist * ptr, int size); #endif #ifdef STM -void fixtable(chashlistnode_t **, unsigned int); +void fixtable(chashlistnode_t **, chashlistnode_t **, unsigned int); #endif -- 2.34.1