1 #include "altprelookup.h"
4 extern objstr_t *prefetchcache;
5 extern pthread_mutex_t prefetchcache_mutex; //Mutex to lock Prefetch Cache
6 extern prefetchNodeInfo_t pNodeInfo;
8 prehashtable_t pflookup; //Global prefetch cache table
10 unsigned int prehashCreate(unsigned int size, float loadfactor) {
11 prehashlistnode_t *nodes;
14 // Allocate space for the hash table
15 if((nodes = calloc(size, sizeof(prehashlistnode_t))) == NULL) {
16 printf("Calloc error %s %d\n", __FILE__, __LINE__);
19 pflookup.table = nodes;
21 pflookup.mask = size -1;
22 pflookup.numelements = 0; // Initial number of elements in the hash
23 pflookup.loadfactor = loadfactor;
24 pflookup.threshold=loadfactor*size;
27 for(i=0; i<PRENUMLOCKS; i++) {
28 pflookup.larray[i].lock=RW_LOCK_BIAS;
32 //Intiliaze and set prefetch table mutex attribute
33 pthread_mutexattr_init(&pflookup.prefetchmutexattr);
34 //NOTE:PTHREAD_MUTEX_RECURSIVE is currently inside a #if_def UNIX98 in the pthread.h file
35 //Therefore use PTHREAD_MUTEX_RECURSIVE_NP instead
36 pthread_mutexattr_settype(&pflookup.prefetchmutexattr, PTHREAD_MUTEX_RECURSIVE_NP);
38 //Initialize mutex var
39 pthread_mutex_init(&pflookup.lock, &pflookup.prefetchmutexattr);
40 //pthread_mutex_init(&pflookup.lock, NULL);
41 pthread_cond_init(&pflookup.cond, NULL);
47 //Assign keys to bins inside hash table
48 unsigned int prehashFunction(unsigned int key) {
49 return ( key & pflookup.mask) >> 1;
52 //Store oids and their pointers into hash
53 void prehashInsert(unsigned int key, void *val) {
56 prehashlistnode_t *ptr, *tmp, *node;
58 if(pflookup.numelements > (pflookup.threshold)) {
60 unsigned int newsize = pflookup.size << 1;
61 prehashResize(newsize);
64 unsigned int keyindex=key>>1;
65 volatile unsigned int * lockptr=&pflookup.larray[keyindex&PRELOCKMASK].lock;
66 while(!write_trylock(lockptr)) {
70 ptr = &pflookup.table[keyindex&pflookup.mask];
72 if(ptr->key==0) { //Insert at the first bin of the table
75 atomic_inc(&pflookup.numelements);
81 tmp->val = val; //Replace value for an exsisting key
82 write_unlock(lockptr);
87 if(!isFound) { //Insert new key and value into the chain of linked list for the given bin
88 node = calloc(1, sizeof(prehashlistnode_t));
91 node->next = ptr->next;
93 atomic_inc(&pflookup.numelements);
96 write_unlock(lockptr);
100 // Search for an address for a given oid
101 void *prehashSearch(unsigned int key) {
104 unsigned int keyindex=key>>1;
105 volatile unsigned int * lockptr=&pflookup.larray[keyindex&PRELOCKMASK].lock;
106 while(!read_trylock(lockptr)) {
109 prehashlistnode_t *node = &pflookup.table[keyindex&pflookup.mask];
112 if(node->key == key) {
113 void * tmp=node->val;
114 read_unlock(lockptr);
118 } while (node!=NULL);
119 read_unlock(lockptr);
123 unsigned int prehashRemove(unsigned int key) {
124 unsigned int keyindex = key >> 1;
125 volatile unsigned int * lockptr=&pflookup.larray[keyindex&PRELOCKMASK].lock;
126 prehashlistnode_t *node, *prev;
128 while(!write_trylock(lockptr)) {
131 prehashlistnode_t *curr = &pflookup.table[keyindex&pflookup.mask];
132 // If there are no elements
133 //delete from first bin of table
134 if (curr->next == NULL && curr->key == key) {
138 atomic_dec(&(pflookup.numelements));
139 write_unlock(lockptr);
142 //delete from first bin of table but elements follow in linked list
143 if (curr->next != NULL && curr->key == key) {
144 curr->key = curr->next->key;
145 curr->val = curr->next->val;
147 curr->next = node->next;
149 atomic_dec(&(pflookup.numelements));
150 write_unlock(lockptr);
155 //delete from elements in the linked list
156 for(; curr != NULL; curr = curr->next) {
157 if (curr->key == key) {
158 prev->next = curr->next;
160 atomic_dec(&(pflookup.numelements));
161 write_unlock(lockptr);
166 write_unlock(lockptr);
170 unsigned int prehashResize(unsigned int newsize) {
171 prehashlistnode_t *node, *ptr; // curr and next keep track of the current and the next chashlistnodes in a linked list
172 unsigned int oldsize;
176 for(i=0; i<PRENUMLOCKS; i++) {
177 volatile unsigned int * lockptr=&pflookup.larray[i].lock;
179 while(!write_trylock(lockptr)) {
184 if (pflookup.numelements < pflookup.threshold) {
185 //release lock and return
186 for(i=0; i<PRENUMLOCKS; i++) {
187 volatile unsigned int * lockptr=&pflookup.larray[i].lock;
188 write_unlock(lockptr);
193 ptr = pflookup.table;
194 oldsize = pflookup.size;
196 if((node = calloc(newsize, sizeof(prehashlistnode_t))) == NULL) {
197 printf("Calloc error %s %d\n", __FILE__, __LINE__);
201 pflookup.table = node; //Update the global hashtable upon resize()
202 pflookup.size = newsize;
203 pflookup.threshold=newsize*pflookup.loadfactor;
204 mask=pflookup.mask = newsize -1;
206 for(i = 0; i < oldsize; i++) { //Outer loop for each bin in hash table
207 prehashlistnode_t * curr = &ptr[i];
208 prehashlistnode_t *tmp, *next;
212 if ((key=curr->key) == 0) { //Exit inner loop if there the first element for a given bin/index is NULL
213 break; //key = val =0 for element if not present within the hash table
216 //index = (key & mask)>>1;
217 index = (key >> 1) & mask;
218 tmp=&pflookup.table[index];
219 // Insert into the new table
226 NOTE: Add this case if you change this...
227 This case currently never happens because of the way things rehash....
229 prehashlistnode_t * newnode = calloc(1, sizeof(prehashlistnode_t));
230 newnode->key = curr->key;
231 newnode->val = curr->val;
232 newnode->next = tmp->next;
236 curr->next=tmp->next;
245 free(ptr); //Free the memory of the old hash table
246 for(i=0; i<PRENUMLOCKS; i++) {
247 volatile unsigned int * lockptr=&pflookup.larray[i].lock;
248 write_unlock(lockptr);
253 //Note: This is based on the implementation of the inserting a key in the first position of the hashtable
254 void prehashClear() {
258 prehashlistnode_t *ptr, *prev, *curr;
260 pthread_mutex_lock(&pflookup.lock);
262 ptr = pflookup.table;
263 for(i = 0; i < pflookup.size; i++) {
266 while(prev->next != NULL) {
269 prev->next = curr->next;
272 if(isFirstBin == 1) {
279 pthread_mutex_unlock(&pflookup.lock);
280 pthread_mutex_lock(&prefetchcache_mutex);
281 if (pNodeInfo.newstale==NULL) {
282 //transfer the list wholesale;
283 pNodeInfo.oldstale=pNodeInfo.oldptr;
284 pNodeInfo.newstale=pNodeInfo.newptr;
286 //merge the two lists
287 pNodeInfo.newstale->prev=pNodeInfo.oldptr;
288 pNodeInfo.newstale=pNodeInfo.newptr;
290 stale=STALL_THRESHOLD-pNodeInfo.stale_count;
292 if (stale>0&&stale>pNodeInfo.stall)
293 pNodeInfo.stall=stale;
295 pNodeInfo.stale_count+=pNodeInfo.os_count;
296 pNodeInfo.oldptr=getObjStr(DEFAULT_OBJ_STORE_SIZE);
297 pNodeInfo.newptr=pNodeInfo.oldptr;
298 pNodeInfo.os_count=1;
299 pthread_mutex_unlock(&prefetchcache_mutex);