From e9c523039054a28a5f259d3f43c4054a935e3cdd Mon Sep 17 00:00:00 2001 From: bdemsky Date: Wed, 2 Dec 2009 04:01:26 +0000 Subject: [PATCH] check in version of machine hashtable with finer grained locking... --- .../src/Runtime/DSTM/interface/altmlookup.c | 242 ++++++++++++++++++ .../src/Runtime/DSTM/interface/altmlookup.h | 45 ++++ 2 files changed, 287 insertions(+) create mode 100644 Robust/src/Runtime/DSTM/interface/altmlookup.c create mode 100644 Robust/src/Runtime/DSTM/interface/altmlookup.h diff --git a/Robust/src/Runtime/DSTM/interface/altmlookup.c b/Robust/src/Runtime/DSTM/interface/altmlookup.c new file mode 100644 index 00000000..e321e700 --- /dev/null +++ b/Robust/src/Runtime/DSTM/interface/altmlookup.c @@ -0,0 +1,242 @@ +#include "mlookup.h" +#include "dsmlock.h" +#include + +mhashtable_t mlookup; //Global hash table + +// Creates a machine lookup table with size =" size" +unsigned int mhashCreate(unsigned int size, double loadfactor) { + mhashlistnode_t *nodes; + // Allocate space for the hash table + if((nodes = calloc(size, sizeof(mhashlistnode_t))) == NULL) { + printf("Calloc error %s %d\n", __FILE__, __LINE__); + return 1; + } + + mlookup.table = nodes; + mlookup.size = size; + mlookup.threshold=size*loadfactor; + mlookup.mask = (size << 1) -1; + mlookup.numelements = 0; // Initial number of elements in the hash + mlookup.loadfactor = loadfactor; + int i; + for(i=0;i>1; +} + +// Insert value and key mapping into the hash table +void mhashInsert(unsigned int key, void *val) { + mhashlistnode_t *node; + + if (mlookup.numelements > mlookup.threshold) { + //Resize Table + unsigned int newsize = mlookup.size << 1; + mhashResize(newsize); + } + + unsigned int keyindex=(key&mlookup.mask)>>1; + volatile unsigned int * lockptr=&mlookup.lockarray[keyindex&LOCKMASK].lock; + while(!write_trylock(lockptr)) { + sched_yield(); + } + + mhashlistnode_t * ptr = &mlookup.table[keyindex]; + atomic_inc(&mlookup.numelements); + + if(ptr->key ==0) { + ptr->key=key; + ptr->val=val; + } else { // Insert in the beginning of linked list + node = calloc(1, sizeof(mhashlistnode_t)); + node->key = key; + node->val = val; + node->next = ptr->next; + ptr->next=node; + } + write_unlock(lockptr); +} + +// Return val for a given key in the hash table +void *mhashSearch(unsigned int key) { + int index; + + unsigned int keyindex=(key&mlookup.mask)>>1; + volatile unsigned int * lockptr=&mlookup.lockarray[keyindex&LOCKMASK].lock; + + while(!write_trylock(lockptr)) { + sched_yield(); + } + + mhashlistnode_t *node = &mlookup.table[keyindex]; + + do { + if(node->key == key) { + void * tmp=node->val; + write_unlock(lockptr); + return tmp; + } + node = node->next; + } while (node!=NULL); + write_unlock(lockptr); + return NULL; +} + +// Remove an entry from the hash table +unsigned int mhashRemove(unsigned int key) { + int index; + mhashlistnode_t *prev; + mhashlistnode_t *ptr, *node; + + unsigned int keyindex=(key&mlookup.mask)>>1; + volatile unsigned int * lockptr=&mlookup.lockarray[keyindex&LOCKMASK].lock; + + while(!write_trylock(lockptr)) { + sched_yield(); + } + + mhashlistnode_t *curr = &mlookup.table[keyindex]; + + for (; curr != NULL; curr = curr->next) { + if (curr->key == key) { + atomic_dec(&mlookup.numelements); + if ((curr == &ptr[index]) && (curr->next == NULL)) { + curr->key = 0; + curr->val = NULL; + } else if ((curr == &ptr[index]) && (curr->next != NULL)) { + curr->key = curr->next->key; + curr->val = curr->next->val; + node = curr->next; + curr->next = curr->next->next; + free(node); + } else { + prev->next = curr->next; + free(curr); + } + write_unlock(lockptr); + return 0; + } + prev = curr; + } + write_unlock(lockptr); + return 1; +} + +// Resize table +void int mhashResize(unsigned int newsize) { + mhashlistnode_t *node, *curr; + int isfirst; + unsigned int i,index; + unsigned int mask; + + for(i=0;ikey) == 0) { + break; + } + next = curr->next; + index = (key & mask) >>1; + tmp=&mlookup.table[index]; + + 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) { + mhashlistnode_t *newnode = calloc(1, sizeof(mhashlistnode_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); + for(i=0;ikey; + curr = curr->next; + } + } + } + + if (keyindex != *numKeys) + printf("mhashGetKeys(): WARNING: incorrect mlookup.numelements value!\n"); + + pthread_mutex_unlock(&mlookup.locktable); + return keys; + }*/ + diff --git a/Robust/src/Runtime/DSTM/interface/altmlookup.h b/Robust/src/Runtime/DSTM/interface/altmlookup.h new file mode 100644 index 00000000..49a31da9 --- /dev/null +++ b/Robust/src/Runtime/DSTM/interface/altmlookup.h @@ -0,0 +1,45 @@ +#ifndef _MLOOKUP_H_ +#define _MLOOKUP_H_ + +#include +#include +#include + +#define MLOADFACTOR 0.25 +#define MHASH_SIZE 1024 + +typedef struct mhashlistnode { + unsigned int key; + void *val; //this can be cast to another type or used to point to a larger structure + struct mhashlistnode *next; +} mhashlistnode_t; + +struct lockarray { + volatile unsigned int lock; + int buf[15]; +} + +#define NUMLOCKS 16 +#define LOCKMASK (NUMLOCKS-1) + +typedef struct mhashtable { + mhashlistnode_t *table; // points to beginning of hash table + unsigned int size; + unsigned int mask; + unsigned int numelements; + unsigned int threshold; + double loadfactor; + struct lockarray[NUMLOCKS]; +} mhashtable_t; + +unsigned int mhashCreate(unsigned int size, double loadfactor); +unsigned int mhashFunction(unsigned int key); +void mhashInsert(unsigned int key, void *val); +void *mhashSearch(unsigned int key); //returns val, NULL if not found +unsigned int mhashRemove(unsigned int key); //returns -1 if not found +unsigned int mhashResize(unsigned int newsize); +//unsigned int *mhashGetKeys(unsigned int *numKeys); +void mhashPrint(); + +#endif + -- 2.34.1