Contains first sketch of waiting queue logic. The WaitingQueue struct will be removed...

diff --git a/Robust/src/Runtime/oooJava/WaitingQueue.c b/Robust/src/Runtime/oooJava/WaitingQueue.c
new file mode 100644 (file)
index 0000000..e05a253
--- /dev/null
+++ b/Robust/src/Runtime/oooJava/WaitingQueue.c
@@ -0,0 +1,145 @@
+#include "mlp_lock.h"\r
+#include "WaitingQueue.h"\r
+//TODO check that the right path is pionted to by the below #include\r
+#include "RuntimeConflictResolver.h"\r
+\r
+//Note: is global to all processes\r
+struct BinVector * freeBinVectors = NULL;\r
+\r
+//TODO perhaps print a map of allocsites to arrayIndex?\r
+//Unique queue for each hashtable\r
+struct WaitingQueue * mallocWaitingQueue(int size) {\r
+  //TODO perhaps in the future get rid of the WaitingQueue object all together to improve performance (but reduce clarity)\r
+  struct WaitingQueue * q = (struct WaitingQueue *) malloc(sizeof(struct WaitingQueue));\r
+  q->array = (struct BinElement *) malloc(sizeof(struct BinElement) * size);\r
+  return q;\r
+}\r
+\r
+//NOTE: allocSiteID is NOT the same as allocsite, rather it's an ID generated by the traverser for an alloc site for a traversal.\r
+void put(int allocSiteID, struct WaitingQueue * queue, int effectType, void * resumePtr, int traverserID) {\r
+  //lock bin\r
+  struct BinVector * head;\r
+  struct BinVector * currentVector;\r
+  struct TraverserData * b;\r
+  do {\r
+    head = (struct BinVector *) 0x1;\r
+    LOCKXCHG(((queue->array)[allocSiteID]).head, head);\r
+  } while (head == (struct BinVector *) 0x1);\r
+  //now the current bin is locked.\r
+\r
+  //completely empty case\r
+  if (queue->array[allocSiteID].tail == NULL) {\r
+    currentVector = getUsableVector();\r
+    head = currentVector;\r
+    queue->array[allocSiteID].tail = currentVector; //We do not set the head here because we need lock\r
+  }\r
+  //Tail bin full\r
+  else if (queue->array[allocSiteID].tail->index == NUMITEMS) {\r
+    currentVector = getUsableVector();\r
+    queue->array[allocSiteID].tail->next = currentVector;\r
+    queue->array[allocSiteID].tail = currentVector;\r
+  } else { //the bin not full case\r
+    currentVector = queue->array[allocSiteID].tail;\r
+  }\r
+\r
+  //add item\r
+  b = &(currentVector->array[currentVector->index++]);\r
+\r
+  b->resumePtr = resumePtr;\r
+  b->traverserID = traverserID;\r
+  b->effectType = effectType;\r
+\r
+  queue->array[allocSiteID].size++;\r
+  queue->array[allocSiteID].head = head; // release lock\r
+}\r
+\r
+//!0 = no one in line.\r
+//=0 = someone is in line.\r
+int check(struct WaitingQueue * queue, int allocSiteID) {\r
+  return ((queue->array)[allocSiteID]).size == 0;\r
+}\r
+\r
+//NOTE: Only the HashTable calls this function\r
+void resolveChain(struct WaitingQueue * queue, int allocSiteID) {\r
+  struct BinVector * head;\r
+  struct BinVector * next;\r
+  struct BinVector * currentVector;\r
+  int i;\r
+  do {\r
+    head = (struct BinVector *) 0x1;\r
+    LOCKXCHG(((queue->array)[allocSiteID]).head, head);\r
+  } while (head == (struct BinVector *) 0x1);\r
+  //now the current bin is locked.\r
+\r
+  //I don't think this case would ever happen, but just in case.\r
+  if(head == NULL) {\r
+    ((queue->array)[allocSiteID]).head = NULL; //release lock\r
+    return;\r
+  }\r
+\r
+  //To prevent live lock, clear and unlock the chain and then process it on the side\r
+  currentVector = head;\r
+  ((queue->array)[allocSiteID]).size = 0;\r
+  ((queue->array)[allocSiteID]).tail = NULL;\r
+  ((queue->array)[allocSiteID]).head = NULL; //lock released\r
+\r
+  //processing the chain.\r
+  while(currentVector != NULL) {\r
+    for(i = 0; i < currentVector->index; i++) {\r
+      struct TraverserData * td = &(currentVector->array[i]);\r
+      runRCRTraverse(td->resumePtr, td->traverserID);\r
+    }\r
+\r
+    //return this vector to the free-pool\r
+    next = currentVector->next;\r
+    returnVectorToFreePool(currentVector);\r
+    currentVector = next;\r
+  }\r
+}\r
+\r
+//NOTE: Only the traverser should be able to call this function and it clears the entire chain.\r
+void returnVectorToFreePool(struct BinVector *ptr) {\r
+  struct BinVector * freeHead;\r
+  do {\r
+    freeHead = (struct BinVector *) 0x1;\r
+    //TODO check if this cuts off part of the mem addr or not.\r
+    LOCKXCHG(freeBinVectors, freeHead);\r
+  } while (freeHead == (struct BinVector *) 0x1);\r
+  //free bins locked\r
+\r
+  if(freeHead == NULL) {\r
+    freeBinVectors = ptr; //lock released\r
+  }\r
+  else {\r
+    ptr->next = freeHead;\r
+    freeBinVectors = ptr; //lock released\r
+  }\r
+}\r
+\r
+struct BinVector * getUsableVector() {\r
+  //Attempt to take one from the free bin first\r
+  struct BinVector * ptr;\r
+  do {\r
+    ptr = (struct BinVector *) 0x1;\r
+    LOCKXCHG(freeBinVectors, ptr);\r
+  } while (ptr == (struct BinVector *) 0x1);\r
+  //free bins locked\r
+\r
+  if (ptr == NULL) {\r
+    freeBinVectors = NULL; //lock released\r
+    return mallocNewVector();\r
+  } else {\r
+    freeBinVectors = ptr->next; //lock released\r
+    ptr->next = NULL;\r
+    ptr->index = 0;\r
+  }\r
+}\r
+\r
+struct BinVector * mallocNewVector() {\r
+  struct BinVector * retval = (struct BinVector *) malloc(\r
+      sizeof(struct BinVector));\r
+  retval->next = NULL;\r
+  retval->index = 0;\r
+  return retval;\r
+}\r
+\r

diff --git a/Robust/src/Runtime/oooJava/WaitingQueue.h b/Robust/src/Runtime/oooJava/WaitingQueue.h
new file mode 100644 (file)
index 0000000..786d910
--- /dev/null
+++ b/Robust/src/Runtime/oooJava/WaitingQueue.h
@@ -0,0 +1,46 @@
+/*
+ * waitingQueue.h
+ *
+ *  Created on: Sep 1, 2010
+ *      Author: stephey
+ */
+#ifndef WAITINGQUEUE_H_
+#define WAITINGQUEUE_H_
+
+#define NUMITEMS 20
+
+/* print header */
+struct TraverserData {
+  void * resumePtr;
+  int traverserID;
+  int effectType;
+};
+
+struct BinVector {
+  struct TraverserData array[NUMITEMS];
+  struct BinVector * next;
+  int index;
+};
+
+struct BinElement {
+  struct BinVector * head;
+  struct BinVector * tail;
+  int size;
+};
+
+
+//TODO in the future, remove this struct all together
+struct WaitingQueue {
+  struct BinElement * array;
+};
+
+void put(int allocSiteID, struct WaitingQueue * queue, int effectType, void * resumePtr, int traverserID);
+int check(struct WaitingQueue * queue, int allocSiteID);
+struct WaitingQueue * mallocWaitingQueue(int size);
+void returnVectorToFreePool(struct BinVector *ptr);
+void resolveChain(struct WaitingQueue * queue, int allocSiteID);
+struct BinVector * mallocNewVector();
+struct BinVector * getUsableVector();
+struct BinVector * getUsableVector();
+
+#endif /* WAITINGQUEUE_H_ */