Robust/src/Runtime/oooJava/WaitingQueue.c

   1 #include "mlp_lock.h"\r
   2 #include "WaitingQueue.h"\r
   3 //TODO check that the right path is pionted to by the below #include\r
   4 #include "RuntimeConflictResolver.h"\r
   5 \r
   6 //Note: is global to all processes\r
   7 struct BinVector * freeBinVectors = NULL;\r
   8 \r
   9 //TODO perhaps print a map of allocsites to arrayIndex?\r
  10 //Unique queue for each hashtable\r
  11 struct WaitingQueue * mallocWaitingQueue(int size) {\r
  12   //TODO perhaps in the future get rid of the WaitingQueue object all together to improve performance (but reduce clarity)\r
  13   struct WaitingQueue * q = (struct WaitingQueue *) malloc(sizeof(struct WaitingQueue));\r
  14   q->array = (struct BinElement *) malloc(sizeof(struct BinElement) * size);\r
  15   return q;\r
  16 }\r
  17 \r
  18 //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
  19 void put(int allocSiteID, struct WaitingQueue * queue, int effectType, void * resumePtr, int traverserID) {\r
  20   //lock bin\r
  21   struct BinVector * head;\r
  22   struct BinVector * currentVector;\r
  23   struct TraverserData * b;\r
  24   do {\r
  25     head = (struct BinVector *) 0x1;\r
  26     LOCKXCHG(((queue->array)[allocSiteID]).head, head);\r
  27   } while (head == (struct BinVector *) 0x1);\r
  28   //now the current bin is locked.\r
  29 \r
  30   //completely empty case\r
  31   if (queue->array[allocSiteID].tail == NULL) {\r
  32     currentVector = getUsableVector();\r
  33     head = currentVector;\r
  34     queue->array[allocSiteID].tail = currentVector; //We do not set the head here because we need lock\r
  35   }\r
  36   //Tail bin full\r
  37   else if (queue->array[allocSiteID].tail->index == NUMITEMS) {\r
  38     currentVector = getUsableVector();\r
  39     queue->array[allocSiteID].tail->next = currentVector;\r
  40     queue->array[allocSiteID].tail = currentVector;\r
  41   } else { //the bin not full case\r
  42     currentVector = queue->array[allocSiteID].tail;\r
  43   }\r
  44 \r
  45   //add item\r
  46   b = &(currentVector->array[currentVector->index++]);\r
  47 \r
  48   b->resumePtr = resumePtr;\r
  49   b->traverserID = traverserID;\r
  50   b->effectType = effectType;\r
  51 \r
  52   queue->array[allocSiteID].size++;\r
  53   queue->array[allocSiteID].head = head; // release lock\r
  54 }\r
  55 \r
  56 //!0 = no one in line.\r
  57 //=0 = someone is in line.\r
  58 int check(struct WaitingQueue * queue, int allocSiteID) {\r
  59   return ((queue->array)[allocSiteID]).size == 0;\r
  60 }\r
  61 \r
  62 //NOTE: Only the HashTable calls this function\r
  63 void resolveChain(struct WaitingQueue * queue, int allocSiteID) {\r
  64   struct BinVector * head;\r
  65   struct BinVector * next;\r
  66   struct BinVector * currentVector;\r
  67   int i;\r
  68   do {\r
  69     head = (struct BinVector *) 0x1;\r
  70     LOCKXCHG(((queue->array)[allocSiteID]).head, head);\r
  71   } while (head == (struct BinVector *) 0x1);\r
  72   //now the current bin is locked.\r
  73 \r
  74   //I don't think this case would ever happen, but just in case.\r
  75   if(head == NULL) {\r
  76     ((queue->array)[allocSiteID]).head = NULL; //release lock\r
  77     return;\r
  78   }\r
  79 \r
  80   //To prevent live lock, clear and unlock the chain and then process it on the side\r
  81   currentVector = head;\r
  82   ((queue->array)[allocSiteID]).size = 0;\r
  83   ((queue->array)[allocSiteID]).tail = NULL;\r
  84   ((queue->array)[allocSiteID]).head = NULL; //lock released\r
  85 \r
  86   //processing the chain.\r
  87   while(currentVector != NULL) {\r
  88     for(i = 0; i < currentVector->index; i++) {\r
  89       struct TraverserData * td = &(currentVector->array[i]);\r
  90       runRCRTraverse(td->resumePtr, td->traverserID);\r
  91     }\r
  92 \r
  93     //return this vector to the free-pool\r
  94     next = currentVector->next;\r
  95     returnVectorToFreePool(currentVector);\r
  96     currentVector = next;\r
  97   }\r
  98 }\r
  99 \r
 100 //NOTE: Only the traverser should be able to call this function and it clears the entire chain.\r
 101 void returnVectorToFreePool(struct BinVector *ptr) {\r
 102   struct BinVector * freeHead;\r
 103   do {\r
 104     freeHead = (struct BinVector *) 0x1;\r
 105     //TODO check if this cuts off part of the mem addr or not.\r
 106     LOCKXCHG(freeBinVectors, freeHead);\r
 107   } while (freeHead == (struct BinVector *) 0x1);\r
 108   //free bins locked\r
 109 \r
 110   if(freeHead == NULL) {\r
 111     freeBinVectors = ptr; //lock released\r
 112   }\r
 113   else {\r
 114     ptr->next = freeHead;\r
 115     freeBinVectors = ptr; //lock released\r
 116   }\r
 117 }\r
 118 \r
 119 struct BinVector * getUsableVector() {\r
 120   //Attempt to take one from the free bin first\r
 121   struct BinVector * ptr;\r
 122   do {\r
 123     ptr = (struct BinVector *) 0x1;\r
 124     LOCKXCHG(freeBinVectors, ptr);\r
 125   } while (ptr == (struct BinVector *) 0x1);\r
 126   //free bins locked\r
 127 \r
 128   if (ptr == NULL) {\r
 129     freeBinVectors = NULL; //lock released\r
 130     return mallocNewVector();\r
 131   } else {\r
 132     freeBinVectors = ptr->next; //lock released\r
 133     ptr->next = NULL;\r
 134     ptr->index = 0;\r
 135   }\r
 136 }\r
 137 \r
 138 struct BinVector * mallocNewVector() {\r
 139   struct BinVector * retval = (struct BinVector *) malloc(\r
 140       sizeof(struct BinVector));\r
 141   retval->next = NULL;\r
 142   retval->index = 0;\r
 143   return retval;\r
 144 }\r
 145 \r