Adding optional support for critical path detection(currently disabled by default...
[charm.git] / src / ck-core / cklocation.C
1 /**
2 \file
3 \addtogroup CkArrayImpl
4
5 The location manager keeps track of an indexed set of migratable
6 objects.  It is used by the array manager to locate array elements,
7 interact with the load balancer, and perform migrations.
8
9 Orion Sky Lawlor, olawlor@acm.org 9/29/2001
10 */
11 #include "charm++.h"
12 #include "register.h"
13 #include "ck.h"
14 #include "trace.h"
15
16 #if CMK_LBDB_ON
17 #include "LBDatabase.h"
18 #endif // CMK_LBDB_ON
19
20 #if CMK_GRID_QUEUE_AVAILABLE
21 CpvExtern(void *, CkGridObject);
22 #endif
23
24 /************************** Debugging Utilities **************/
25 //For debugging: convert given index to a string
26 static const char *idx2str(const CkArrayIndex &ind)
27 {
28         static char retBuf[80];
29         retBuf[0]=0;
30         for (int i=0;i<ind.nInts;i++)
31         {
32                 if (i>0) strcat(retBuf,";");
33                 sprintf(&retBuf[strlen(retBuf)],"%d",ind.data()[i]);
34         }
35         return retBuf;
36 }
37
38 static const char *idx2str(const CkArrayMessage *m)
39 {
40         return idx2str(((CkArrayMessage *)m)->array_index());
41 }
42
43 #define ARRAY_DEBUG_OUTPUT 0
44
45 #if ARRAY_DEBUG_OUTPUT 
46 #   define DEB(x) CkPrintf x  //General debug messages
47 #   define DEBI(x) CkPrintf x  //Index debug messages
48 #   define DEBC(x) CkPrintf x  //Construction debug messages
49 #   define DEBS(x) CkPrintf x  //Send/recv/broadcast debug messages
50 #   define DEBM(x) CkPrintf x  //Migration debug messages
51 #   define DEBL(x) CkPrintf x  //Load balancing debug messages
52 #   define DEBK(x) //CkPrintf x  //Spring Cleaning debug messages
53 #   define DEBB(x) CkPrintf x  //Broadcast debug messages
54 #   define AA "LocMgr on %d: "
55 #   define AB ,CkMyPe()
56 #else
57 #   define DEB(X) /*CkPrintf x*/
58 #   define DEBI(X) /*CkPrintf x*/
59 #   define DEBC(X) /*CkPrintf x*/
60 #   define DEBS(x) /*CkPrintf x*/
61 #   define DEBM(X) /*CkPrintf x*/
62 #   define DEBL(X) /*CkPrintf x*/
63 #   define DEBK(x) /*CkPrintf x*/
64 #   define DEBB(x) /*CkPrintf x*/
65 #   define str(x) /**/
66 #endif
67
68
69
70 #if CMK_LBDB_ON
71 /*LBDB object handles are fixed-sized, and not necc.
72 the same size as ArrayIndices.
73 */
74 LDObjid idx2LDObjid(const CkArrayIndex &idx)
75 {
76   LDObjid r;
77   int i;
78   const int *data=idx.data();
79   if (OBJ_ID_SZ>=idx.nInts) {
80     for (i=0;i<idx.nInts;i++)
81       r.id[i]=data[i];
82     for (i=idx.nInts;i<OBJ_ID_SZ;i++)
83       r.id[i]=0;
84   } else {
85     //Must hash array index into LBObjid
86     int j;
87     for (j=0;j<OBJ_ID_SZ;j++)
88         r.id[j]=data[j];
89     for (i=0;i<idx.nInts;i++)
90       for (j=0;j<OBJ_ID_SZ;j++)
91         r.id[j]+=circleShift(data[i],22+11*i*(j+1))+
92           circleShift(data[i],21-9*i*(j+1));
93   }
94   return r;
95 }
96 #endif
97
98 /************************* Array Index *********************
99 Array Index class.  An array index is just a 
100 a run of bytes used to look up an object in a hash table.
101 */
102 typedef unsigned char uc;
103
104 CkHashCode CkArrayIndex::staticHash(const void *v,size_t)
105         {return ((const CkArrayIndex *)v)->hash();}
106
107 int CkArrayIndex::staticCompare(const void *k1,const void *k2,size_t /*len*/)
108 {
109         return ((const CkArrayIndex *)k1)->
110                 compare(*(const CkArrayIndex *)k2);
111 }
112
113 void CkArrayIndex::pup(PUP::er &p) 
114 {
115         p(nInts);
116         p(data(),nInts);
117 }
118
119 /*********************** Array Messages ************************/
120 inline CkArrayIndexMax &CkArrayMessage::array_index(void)
121 {
122         return UsrToEnv((void *)this)->getsetArrayIndex();
123 }
124 unsigned short &CkArrayMessage::array_ep(void)
125 {
126         return UsrToEnv((void *)this)->getsetArrayEp();
127 }
128 unsigned short &CkArrayMessage::array_ep_bcast(void)
129 {
130         return UsrToEnv((void *)this)->getsetArrayBcastEp();
131 }
132 unsigned char &CkArrayMessage::array_hops(void)
133 {
134         return UsrToEnv((void *)this)->getsetArrayHops();
135 }
136 unsigned int CkArrayMessage::array_getSrcPe(void)
137 {
138         return UsrToEnv((void *)this)->getsetArraySrcPe();
139 }
140 unsigned int CkArrayMessage::array_ifNotThere(void)
141 {
142         return UsrToEnv((void *)this)->getArrayIfNotThere();
143 }
144 void CkArrayMessage::array_setIfNotThere(unsigned int i)
145 {
146         UsrToEnv((void *)this)->setArrayIfNotThere(i);
147 }
148
149 /*********************** Array Map ******************
150 Given an array element index, an array map tells us 
151 the index's "home" Pe.  This is the Pe the element will
152 be created on, and also where messages to this element will
153 be forwarded by default.
154 */
155
156 CkArrayMap::CkArrayMap(void) { }
157 CkArrayMap::~CkArrayMap() { }
158 int CkArrayMap::registerArray(CkArrayIndexMax& numElements,CkArrayID aid)
159 {return 0;}
160
161 #define CKARRAYMAP_POPULATE_INITIAL(POPULATE_CONDITION) \
162         int i; \
163         for (int i1=0; i1<numElements.data()[0]; i1++) { \
164           if (numElements.nInts == 1) { \
165             /* Make 1D indices */ \
166             i = i1; \
167             CkArrayIndex1D idx(i1); \
168             if (POPULATE_CONDITION) \
169               mgr->insertInitial(idx,CkCopyMsg(&ctorMsg)); \
170           } else { \
171             /* higher dimensionality */ \
172             for (int i2=0; i2<numElements.data()[1]; i2++) { \
173               if (numElements.nInts == 2) { \
174                 /* Make 2D indices */ \
175                 i = i1 * numElements.data()[1] + i2; \
176                 CkArrayIndex2D idx(i1, i2); \
177                 if (POPULATE_CONDITION) \
178                   mgr->insertInitial(idx,CkCopyMsg(&ctorMsg)); \
179               } else { \
180                 /* higher dimensionality */ \
181                 CkAssert(numElements.nInts == 3); \
182                 for (int i3=0; i3<numElements.data()[2]; i3++) { \
183                   /* Make 3D indices */ \
184                   i = (i1 * numElements.data()[1] + i2) * numElements.data()[2] + i3; \
185                   CkArrayIndex3D idx(i1, i2, i3 ); \
186                   if (POPULATE_CONDITION) \
187                     mgr->insertInitial(idx,CkCopyMsg(&ctorMsg)); \
188                 } \
189               } \
190             } \
191           } \
192         }
193
194 void CkArrayMap::populateInitial(int arrayHdl,CkArrayIndexMax& numElements,void *ctorMsg,CkArrMgr *mgr)
195 {
196         if (numElements.nInts==0) {
197           CkFreeMsg(ctorMsg);
198           return;
199         }
200         int thisPe=CkMyPe();
201         /* The CkArrayIndexMax is supposed to have at most 3 dimensions, which
202            means that all the fields are ints, and numElements.nInts represents
203            how many of them are used */
204         CKARRAYMAP_POPULATE_INITIAL(procNum(arrayHdl,idx)==thisPe);
205
206 #if CMK_BLUEGENE_CHARM
207         BgEntrySplit("split-array-new-end");
208 #endif
209
210         mgr->doneInserting();
211         CkFreeMsg(ctorMsg);
212 }
213
214 CkGroupID _RRMapID;
215 /**
216  *The default map object-- round-robin homes.  This is 
217  * almost always what you want.
218  */
219 class RRMap : public CkArrayMap
220 {
221 public:
222   RRMap(void)
223   {
224           DEBC((AA"Creating RRMap\n"AB));
225   }
226   RRMap(CkMigrateMessage *m):CkArrayMap(m){}
227   int procNum(int /*arrayHdl*/, const CkArrayIndex &i)
228   {
229 #if 1
230     if (i.nInts==1) {
231       //Map 1D integer indices in simple round-robin fashion
232       int ans= (i.data()[0])%CkNumPes();
233       while(!CmiNodeAlive(ans) || (ans == CkMyPe() && CpvAccess(startedEvac))){
234         ans = (ans +1 )%CkNumPes();
235       }
236       return ans;
237     }
238     else 
239 #endif
240       {
241         //Map other indices based on their hash code, mod a big prime.
242         unsigned int hash=(i.hash()+739)%1280107;
243         int ans = (hash % CkNumPes());
244         while(!CmiNodeAlive(ans)){
245                 ans = (ans +1 )%CkNumPes();
246         }
247         return ans;
248
249       }
250   }
251 };
252
253 class BlockMap : public RRMap
254 {
255 public:
256   BlockMap(void){
257         DEBC((AA"Creating BlockMap\n"AB));
258   }
259   BlockMap(CkMigrateMessage *m):RRMap(m){ }
260   void populateInitial(int arrayHdl,CkArrayIndexMax& numElements,void *ctorMsg,CkArrMgr *mgr){
261         if (numElements.nInts==0) {
262           CkFreeMsg(ctorMsg);
263           return;
264         }
265         int thisPe=CkMyPe();
266         int numPes=CkNumPes();
267         int binSize;
268         if (numElements.nInts == 1) {
269           binSize = (int)ceil((double)numElements.data()[0]/(double)numPes);
270         } else if (numElements.nInts == 2) {
271           binSize = (int)ceil((double)(numElements.data()[0]*numElements.data()[1])/(double)numPes);
272         } else if (numElements.nInts == 3) {
273           binSize = (int)ceil((double)(numElements.data()[0]*numElements.data()[1]*numElements.data()[2])/(double)numPes);
274         } else {
275           CkAbort("CkArrayIndex has dimension greater than 3!");
276         }
277         CKARRAYMAP_POPULATE_INITIAL(i/binSize==thisPe);
278
279         /*
280         CkArrayIndexMax idx;
281         for (idx=numElements.begin(); idx<numElements; idx.getNext(numElements)) {
282           //for (int i=0;i<numElements;i++) {
283                 int binSize = (int)ceil((double)numElements.getCombinedCount()/(double)numPes);
284                 if (i/binSize==thisPe)
285                         mgr->insertInitial(idx,CkCopyMsg(&ctorMsg));
286         }*/
287         mgr->doneInserting();
288         CkFreeMsg(ctorMsg);
289   }
290 };
291
292 /**
293  * map object-- use seed load balancer.  
294  */
295 class CldMap : public CkArrayMap
296 {
297 public:
298   CldMap(void)
299   {
300           DEBC((AA"Creating CldMap\n"AB));
301   }
302   CldMap(CkMigrateMessage *m):CkArrayMap(m){}
303   int homePe(int /*arrayHdl*/, const CkArrayIndex &i)
304   {
305     if (i.nInts==1) {
306       //Map 1D integer indices in simple round-robin fashion
307       return (i.data()[0])%CkNumPes();
308     }
309     else 
310       {
311         //Map other indices based on their hash code, mod a big prime.
312         unsigned int hash=(i.hash()+739)%1280107;
313         return (hash % CkNumPes());
314       }
315   }
316   int procNum(int arrayHdl, const CkArrayIndex &i)
317   {
318      return CLD_ANYWHERE;   // -1
319   }
320   void populateInitial(int arrayHdl,CkArrayIndexMax& numElements,void *ctorMsg,CkArrMgr *mgr)  {
321         if (numElements.nInts==0) {
322           CkFreeMsg(ctorMsg);
323           return;
324         }
325         int thisPe=CkMyPe();
326         int numPes=CkNumPes();
327         //CkArrayIndexMax idx;
328
329         CKARRAYMAP_POPULATE_INITIAL(i%numPes==thisPe);
330         /*for (idx=numElements.begin(); idx<numElements; idx.getNext(numElements)) {
331           //for (int i=0;i<numElements;i++)
332                         if((idx.getRank(numElements))%numPes==thisPe)
333                                 mgr->insertInitial(CkArrayIndex1D(i),CkCopyMsg(&ctorMsg),0);
334         }*/
335         mgr->doneInserting();
336         CkFreeMsg(ctorMsg);
337   }
338
339 };
340
341 CkpvStaticDeclare(double*, rem);
342
343 class arrInfo {
344  private:
345    CkArrayIndexMax _nelems;
346    int *_map;
347    void distrib(int *speeds);
348  public:
349    arrInfo(void):_map(NULL){}
350    arrInfo(CkArrayIndexMax& n, int *speeds)
351    {
352      _nelems = n;
353      _map = new int[_nelems.getCombinedCount()];
354      distrib(speeds);
355    }
356    ~arrInfo() { delete[] _map; }
357    int getMap(const CkArrayIndex &i);
358    void pup(PUP::er& p){
359      p|_nelems;
360      int totalElements = _nelems.getCombinedCount();
361      if(p.isUnpacking()){
362        _map = new int[totalElements];
363      }
364      p(_map,totalElements);
365    }
366 };
367
368 static int cmp(const void *first, const void *second)
369 {
370   int fi = *((const int *)first);
371   int si = *((const int *)second);
372   return ((CkpvAccess(rem)[fi]==CkpvAccess(rem)[si]) ?
373           0 :
374           ((CkpvAccess(rem)[fi]<CkpvAccess(rem)[si]) ?
375           1 : (-1)));
376 }
377
378 void
379 arrInfo::distrib(int *speeds)
380 {
381   int _nelemsCount = _nelems.getCombinedCount();
382   double total = 0.0;
383   int npes = CkNumPes();
384   int i,j,k;
385   for(i=0;i<npes;i++)
386     total += (double) speeds[i];
387   double *nspeeds = new double[npes];
388   for(i=0;i<npes;i++)
389     nspeeds[i] = (double) speeds[i] / total;
390   int *cp = new int[npes];
391   for(i=0;i<npes;i++)
392     cp[i] = (int) (nspeeds[i]*_nelemsCount);
393   int nr = 0;
394   for(i=0;i<npes;i++)
395     nr += cp[i];
396   nr = _nelemsCount - nr;
397   if(nr != 0)
398   {
399     CkpvAccess(rem) = new double[npes];
400     for(i=0;i<npes;i++)
401       CkpvAccess(rem)[i] = (double)_nelemsCount*nspeeds[i] - cp[i];
402     int *pes = new int[npes];
403     for(i=0;i<npes;i++)
404       pes[i] = i;
405     qsort(pes, npes, sizeof(int), cmp);
406     for(i=0;i<nr;i++)
407       cp[pes[i]]++;
408     delete[] CkpvAccess(rem);
409     delete[] pes;
410   }
411   k = 0;
412   for(i=0;i<npes;i++)
413   {
414     for(j=0;j<cp[i];j++)
415       _map[k++] = i;
416   }
417   delete[] nspeeds;
418   delete[] cp;
419 }
420
421 int
422 arrInfo::getMap(const CkArrayIndex &i)
423 {
424   if(i.nInts==1)
425     return _map[i.data()[0]];
426   else
427     return _map[((i.hash()+739)%1280107)%_nelems.getCombinedCount()];
428 }
429
430 //Speeds maps processor number to "speed" (some sort of iterations per second counter)
431 // It is initialized by processor 0.
432 static int* speeds;
433
434 #if CMK_USE_PROP_MAP
435 typedef struct _speedmsg
436 {
437   char hdr[CmiMsgHeaderSizeBytes];
438   int node;
439   int speed;
440 } speedMsg;
441
442 static void _speedHdlr(void *m)
443 {
444   speedMsg *msg=(speedMsg *)m;
445   if (CmiMyRank()==0)
446     for (int pe=0;pe<CmiNodeSize(msg->node);pe++)
447       speeds[CmiNodeFirst(msg->node)+pe] = msg->speed;  
448   CmiFree(m);
449 }
450
451 void _propMapInit(void)
452 {
453   speeds = new int[CkNumPes()];
454   int hdlr = CkRegisterHandler((CmiHandler)_speedHdlr);
455   CmiPrintf("[%d]Measuring processor speed for prop. mapping...\n", CkMyPe());
456   int s = LDProcessorSpeed();
457   speedMsg msg;
458   CmiSetHandler(&msg, hdlr);
459   msg.node = CkMyNode();
460   msg.speed = s;
461   CmiSyncBroadcastAllAndFree(sizeof(msg), &msg);
462   for(int i=0;i<CkNumNodes();i++)
463     CmiDeliverSpecificMsg(hdlr);
464 }
465 #else
466 void _propMapInit(void)
467 {
468   speeds = new int[CkNumPes()];
469   int i;
470   for(i=0;i<CkNumPes();i++)
471     speeds[i] = 1;
472 }
473 #endif
474 /**
475  * A proportional map object-- tries to map more objects to
476  * faster processors and fewer to slower processors.  Also
477  * attempts to ensure good locality by mapping nearby elements
478  * together.
479  */
480 class PropMap : public CkArrayMap
481 {
482 private:
483   CkPupPtrVec<arrInfo> arrs;
484 public:
485   PropMap(void)
486   {
487     CkpvInitialize(double*, rem);
488     DEBC((AA"Creating PropMap\n"AB));
489   }
490   PropMap(CkMigrateMessage *m) {}
491   int registerArray(CkArrayIndexMax& numElements,CkArrayID aid)
492   {
493     int idx = arrs.size();
494     arrs.resize(idx+1);
495     arrs[idx] = new arrInfo(numElements, speeds);
496     return idx;
497   }
498   int procNum(int arrayHdl, const CkArrayIndex &i)
499   {
500     return arrs[arrayHdl]->getMap(i);
501   }
502   void pup(PUP::er& p){
503     p|arrs;
504   }
505 };
506
507 class CkMapsInit : public Chare
508 {
509 public:
510   CkMapsInit(CkArgMsg *msg) {
511     _RRMapID = CProxy_RRMap::ckNew();
512     delete msg;
513   }
514   CkMapsInit(CkMigrateMessage *m) {}
515 };
516
517 // given an envelope of a Charm msg, find the recipient object pointer
518 CkMigratable * CkArrayMessageObjectPtr(envelope *env) {
519   if (env->getMsgtype()!=ForArrayEltMsg) return NULL;   // not an array msg
520
521   CkArrayID aid = env->getsetArrayMgr();
522   CkArray *mgr=(CkArray *)_localBranch(aid);
523   if (mgr) {
524     CkLocMgr *locMgr = mgr->getLocMgr();
525     if (locMgr) {
526       return locMgr->lookup(env->getsetArrayIndex(),aid);
527     }
528   }
529   return NULL;
530 }
531
532 /****************************** Out-of-Core support ********************/
533
534 #if CMK_OUT_OF_CORE
535 CooPrefetchManager CkArrayElementPrefetcher;
536 CkpvDeclare(int,CkSaveRestorePrefetch);
537
538 /**
539  * Return the out-of-core objid (from CooRegisterObject)
540  * that this Converse message will access.  If the message
541  * will not access an object, return -1.
542  */
543 int CkArrayPrefetch_msg2ObjId(void *msg) {
544   envelope *env=(envelope *)msg;
545   CkMigratable *elt = CkArrayMessageObjectPtr(env);
546   return elt?elt->prefetchObjID:-1;
547 }
548
549 /**
550  * Write this object (registered with RegisterObject)
551  * to this writable file.
552  */
553 void CkArrayPrefetch_writeToSwap(FILE *swapfile,void *objptr) {
554   CkMigratable *elt=(CkMigratable *)objptr;
555
556   //Save the element's data to disk:
557   PUP::toDisk p(swapfile);
558   elt->pup(p);
559
560   //Call the element's destructor in-place (so pointer doesn't change)
561   CkpvAccess(CkSaveRestorePrefetch)=1;
562   elt->~CkMigratable(); //< because destuctor is virtual, destroys user class too.
563   CkpvAccess(CkSaveRestorePrefetch)=0;
564 }
565         
566 /**
567  * Read this object (registered with RegisterObject)
568  * from this readable file.
569  */
570 void CkArrayPrefetch_readFromSwap(FILE *swapfile,void *objptr) {
571   CkMigratable *elt=(CkMigratable *)objptr;
572   //Call the element's migration constructor in-place
573   CkpvAccess(CkSaveRestorePrefetch)=1;
574   int ctorIdx=_chareTable[elt->thisChareType]->migCtor;
575   elt->myRec->invokeEntry(elt,(CkMigrateMessage *)0,ctorIdx,CmiTrue);
576   CkpvAccess(CkSaveRestorePrefetch)=0;
577   
578   //Restore the element's data from disk:
579   PUP::fromDisk p(swapfile);
580   elt->pup(p);
581 }
582
583 static void _CkMigratable_prefetchInit(void) 
584 {
585   CkpvExtern(int,CkSaveRestorePrefetch);
586   CkpvAccess(CkSaveRestorePrefetch)=0;
587   CkArrayElementPrefetcher.msg2ObjId=CkArrayPrefetch_msg2ObjId;
588   CkArrayElementPrefetcher.writeToSwap=CkArrayPrefetch_writeToSwap;
589   CkArrayElementPrefetcher.readFromSwap=CkArrayPrefetch_readFromSwap;
590   CooRegisterManager(&CkArrayElementPrefetcher, _charmHandlerIdx);
591 }
592 #endif
593
594 /****************************** CkMigratable ***************************/
595 /**
596  * This tiny class is used to convey information to the 
597  * newly created CkMigratable object when its constructor is called.
598  */
599 class CkMigratable_initInfo {
600 public:
601         CkLocRec_local *locRec;
602         int chareType;
603         CmiBool forPrefetch; /* If true, this creation is only a prefetch restore-from-disk.*/
604 };
605
606 CkpvStaticDeclare(CkMigratable_initInfo,mig_initInfo);
607
608
609 void _CkMigratable_initInfoInit(void) {
610   CkpvInitialize(CkMigratable_initInfo,mig_initInfo);
611 #if CMK_OUT_OF_CORE
612   _CkMigratable_prefetchInit();
613 #endif
614 }
615
616 void CkMigratable::commonInit(void) {
617         CkMigratable_initInfo &i=CkpvAccess(mig_initInfo);
618 #if CMK_OUT_OF_CORE
619         isInCore=CmiTrue;
620         if (CkpvAccess(CkSaveRestorePrefetch))
621                 return; /* Just restoring from disk--don't touch object */
622         prefetchObjID=-1; //Unregistered
623 #endif
624         myRec=i.locRec;
625         thisIndexMax=myRec->getIndex();
626         thisChareType=i.chareType;
627         usesAtSync=CmiFalse;
628         usesAutoMeasure=CmiTrue;
629         barrierRegistered=CmiFalse;
630         /*
631         FAULT_EVAC
632         */
633         AsyncEvacuate(CmiTrue);
634 }
635
636 CkMigratable::CkMigratable(void) {
637         DEBC((AA"In CkMigratable constructor\n"AB));
638         commonInit();
639 }
640 CkMigratable::CkMigratable(CkMigrateMessage *m) {
641         commonInit();
642 }
643
644 int CkMigratable::ckGetChareType(void) const {return thisChareType;}
645
646 void CkMigratable::pup(PUP::er &p) {
647         DEBM((AA"In CkMigratable::pup %s\n"AB,idx2str(thisIndexMax)));
648         Chare::pup(p);
649         p|thisIndexMax;
650         p(usesAtSync);
651         p(usesAutoMeasure);
652 #if CMK_LBDB_ON 
653         int readyMigrate;
654         if (p.isPacking()) readyMigrate = myRec->isReadyMigrate();
655         p|readyMigrate;
656         if (p.isUnpacking()) myRec->ReadyMigrate(readyMigrate);
657 #endif
658         if(p.isUnpacking()) barrierRegistered=CmiFalse;
659         /*
660                 FAULT_EVAC
661         */
662         p | asyncEvacuate;
663         if(p.isUnpacking()){myRec->AsyncEvacuate(asyncEvacuate);}
664         
665         ckFinishConstruction();
666 }
667
668 void CkMigratable::ckDestroy(void) {
669         DEBC((AA"In CkMigratable::ckDestroy %s\n"AB,idx2str(thisIndexMax)));
670         myRec->destroy();
671 }
672
673 void CkMigratable::ckAboutToMigrate(void) { }
674 void CkMigratable::ckJustMigrated(void) { }
675
676 CkMigratable::~CkMigratable() {
677         DEBC((AA"In CkMigratable::~CkMigratable %s\n"AB,idx2str(thisIndexMax)));
678 #if CMK_OUT_OF_CORE
679         isInCore=CmiFalse;
680         if (CkpvAccess(CkSaveRestorePrefetch)) 
681                 return; /* Just saving to disk--don't deregister anything. */
682         /* We're really leaving or dying-- unregister from the ooc system*/
683         if (prefetchObjID!=-1) {
684                 CooDeregisterObject(prefetchObjID);
685                 prefetchObjID=-1;
686         }
687 #endif
688         /*Might want to tell myRec about our doom here--
689         it's difficult to avoid some kind of circular-delete, though.
690         */
691 #if CMK_LBDB_ON 
692         if (barrierRegistered) {
693           DEBL((AA"Removing barrier for element %s\n"AB,idx2str(thisIndexMax)));
694           if (usesAtSync)
695                 myRec->getLBDB()->RemoveLocalBarrierClient(ldBarrierHandle);
696           else
697                 myRec->getLBDB()->RemoveLocalBarrierReceiver(ldBarrierRecvHandle);
698         }
699 #endif
700         //To detect use-after-delete
701         thisIndexMax.nInts=-123456;
702 }
703
704 void CkMigratable::CkAbort(const char *why) const {
705         CkError("CkMigratable '%s' aborting:\n",_chareTable[thisChareType]->name);
706         ::CkAbort(why);
707 }
708
709 void CkMigratable::ResumeFromSync(void)
710 {
711 //      CkAbort("::ResumeFromSync() not defined for this array element!\n");
712 }
713
714 void CkMigratable::UserSetLBLoad() {
715         CkAbort("::UserSetLBLoad() not defined for this array element!\n");
716 }
717
718 #if CMK_LBDB_ON  //For load balancing:
719 // user can call this helper function to set obj load (for model-based lb)
720 void CkMigratable::setObjTiming(double cputime) {
721         myRec->setObjTiming(cputime);
722 }
723
724 void CkMigratable::ckFinishConstruction(void)
725 {
726 //      if ((!usesAtSync) || barrierRegistered) return;
727         myRec->setMeasure(usesAutoMeasure);
728         if (barrierRegistered) return;
729         DEBL((AA"Registering barrier client for %s\n"AB,idx2str(thisIndexMax)));
730         if (usesAtSync)
731           ldBarrierHandle = myRec->getLBDB()->AddLocalBarrierClient(
732                 (LDBarrierFn)staticResumeFromSync,(void*)(this));
733         else
734           ldBarrierRecvHandle = myRec->getLBDB()->AddLocalBarrierReceiver(
735                 (LDBarrierFn)staticResumeFromSync,(void*)(this));
736         barrierRegistered=CmiTrue;
737 }
738 void CkMigratable::AtSync(int waitForMigration)
739 {
740         if (!usesAtSync)
741                 CkAbort("You must set usesAtSync=CmiTrue in your array element constructor to use AtSync!\n");
742         myRec->AsyncMigrate(!waitForMigration);
743         if (waitForMigration) ReadyMigrate(CmiTrue);
744         ckFinishConstruction();
745         DEBL((AA"Element %s going to sync\n"AB,idx2str(thisIndexMax)));
746           // model-based load balancing, ask user to provide cpu load
747         if (usesAutoMeasure == CmiFalse) UserSetLBLoad();
748         myRec->getLBDB()->AtLocalBarrier(ldBarrierHandle);
749 }
750 void CkMigratable::ReadyMigrate(CmiBool ready)
751 {
752         myRec->ReadyMigrate(ready);
753 }
754 void CkMigratable::staticResumeFromSync(void* data)
755 {
756         CkMigratable *el=(CkMigratable *)data;
757         DEBL((AA"Element %s resuming from sync\n"AB,idx2str(el->thisIndexMax)));
758         el->ResumeFromSync();
759 }
760 void CkMigratable::setMigratable(int migratable) 
761 {
762         myRec->setMigratable(migratable);
763 }
764
765 struct CkArrayThreadListener {
766         struct CthThreadListener base;
767         CkMigratable *mig;
768 };
769
770 extern "C"
771 void CkArrayThreadListener_suspend(struct CthThreadListener *l)
772 {
773         CkArrayThreadListener *a=(CkArrayThreadListener *)l;
774         a->mig->ckStopTiming();
775 }
776
777 extern "C"
778 void CkArrayThreadListener_resume(struct CthThreadListener *l)
779 {
780         CkArrayThreadListener *a=(CkArrayThreadListener *)l;
781         a->mig->ckStartTiming();
782 }
783
784 extern "C"
785 void CkArrayThreadListener_free(struct CthThreadListener *l)
786 {
787         CkArrayThreadListener *a=(CkArrayThreadListener *)l;
788         delete a;
789 }
790
791 void CkMigratable::CkAddThreadListeners(CthThread tid, void *msg)
792 {
793         Chare::CkAddThreadListeners(tid, msg);   // for trace
794         CthSetThreadID(tid, thisIndexMax.data()[0], thisIndexMax.data()[1], 
795                        thisIndexMax.data()[2]);
796         CkArrayThreadListener *a=new CkArrayThreadListener;
797         a->base.suspend=CkArrayThreadListener_suspend;
798         a->base.resume=CkArrayThreadListener_resume;
799         a->base.free=CkArrayThreadListener_free;
800         a->mig=this;
801         CthAddListener(tid,(struct CthThreadListener *)a);
802 }
803 #else
804 void CkMigratable::setObjTiming(double cputime) {}
805
806 /* no load balancer: need dummy implementations to prevent link error */
807 void CkMigratable::CkAddThreadListeners(CthThread tid, void *msg)
808 {
809 }
810 #endif
811
812
813 /*CkMigratableList*/
814 CkMigratableList::CkMigratableList() {}
815 CkMigratableList::~CkMigratableList() {}
816
817 void CkMigratableList::setSize(int s) {
818         el.resize(s);
819 }
820
821 void CkMigratableList::put(CkMigratable *v,int atIdx) {
822 #ifndef CMK_OPTIMIZE
823         if (atIdx>=length())
824                 CkAbort("Internal array manager error (CkMigrableList::put index out of bounds)");
825 #endif
826         el[atIdx]=v;
827 }
828
829
830 /************************** Location Records: *********************************/
831
832 //---------------- Base type:
833 void CkLocRec::weAreObsolete(const CkArrayIndex &idx) {}
834 CkLocRec::~CkLocRec() { }
835 void CkLocRec::beenReplaced(void)
836     {/*Default: ignore replacement*/}
837
838 //Return the represented array element; or NULL if there is none
839 CkMigratable *CkLocRec::lookupElement(CkArrayID aid) {return NULL;}
840
841 //Return the last known processor; or -1 if none
842 int CkLocRec::lookupProcessor(void) {return -1;}
843
844
845 /*----------------- Local:
846 Matches up the array index with the local index, an
847 interfaces with the load balancer on behalf of the
848 represented array elements.
849 */
850 CkLocRec_local::CkLocRec_local(CkLocMgr *mgr,CmiBool fromMigration,
851   CmiBool ignoreArrival, const CkArrayIndex &idx_,int localIdx_)
852         :CkLocRec(mgr),idx(idx_),localIdx(localIdx_),
853          running(CmiFalse),deletedMarker(NULL)
854 {
855 #if CMK_LBDB_ON
856         DEBL((AA"Registering element %s with load balancer\n"AB,idx2str(idx)));
857         nextPe = -1;
858         asyncMigrate = CmiFalse;
859         readyMigrate = CmiTrue;
860         enable_measure = CmiTrue;
861         bounced  = CmiFalse;
862         the_lbdb=mgr->getLBDB();
863         ldHandle=the_lbdb->RegisterObj(mgr->getOMHandle(),
864                 idx2LDObjid(idx),(void *)this,1);
865         if (fromMigration) {
866                 DEBL((AA"Element %s migrated in\n"AB,idx2str(idx)));
867                 if (!ignoreArrival)  {
868                         the_lbdb->Migrated(ldHandle, CmiTrue);
869                   // load balancer should ignore this objects movement
870                 //  AsyncMigrate(CmiTrue);
871                 }
872         }
873 #endif
874         /*
875                 FAULT_EVAC
876         */
877         asyncEvacuate = CmiTrue;
878 }
879 CkLocRec_local::~CkLocRec_local()
880 {
881         if (deletedMarker!=NULL) *deletedMarker=CmiTrue;
882         myLocMgr->reclaim(idx,localIdx);
883 #if CMK_LBDB_ON
884         stopTiming();
885         DEBL((AA"Unregistering element %s from load balancer\n"AB,idx2str(idx)));
886         the_lbdb->UnregisterObj(ldHandle);
887 #endif
888 }
889 void CkLocRec_local::migrateMe(int toPe) //Leaving this processor
890 {
891         //This will pack us up, send us off, and delete us
892 //      printf("[%d] migrating migrateMe to %d \n",CkMyPe(),toPe);
893         myLocMgr->emigrate(this,toPe);
894 }
895
896 #if CMK_LBDB_ON
897 void CkLocRec_local::startTiming(void) {
898         running=CmiTrue;
899         DEBL((AA"Start timing for %s at %.3fs {\n"AB,idx2str(idx),CkWallTimer()));
900         if (enable_measure) the_lbdb->ObjectStart(ldHandle);
901 }
902 void CkLocRec_local::stopTiming(void) {
903         DEBL((AA"} Stop timing for %s at %.3fs\n"AB,idx2str(idx),CkWallTimer()));
904         if (running && enable_measure) the_lbdb->ObjectStop(ldHandle);
905         running=CmiFalse;
906 }
907 void CkLocRec_local::setObjTiming(double cputime) {
908         the_lbdb->EstObjLoad(ldHandle, cputime);
909 }
910 #endif
911
912 void CkLocRec_local::destroy(void) //User called destructor
913 {
914         //Our destructor does all the needed work
915         delete this;
916 }
917 //Return the represented array element; or NULL if there is none
918 CkMigratable *CkLocRec_local::lookupElement(CkArrayID aid) {
919         return myLocMgr->lookupLocal(localIdx,aid);
920 }
921
922 //Return the last known processor; or -1 if none
923 int CkLocRec_local::lookupProcessor(void) {
924         return CkMyPe();
925 }
926
927 CkLocRec::RecType CkLocRec_local::type(void)
928 {
929         return local;
930 }
931
932 void CkLocRec_local::addedElement(void) 
933 {
934         //Push everything in the half-created queue into the system--
935         // anything not ready yet will be put back in.
936         while (!halfCreated.isEmpty()) 
937                 CkArrayManagerDeliver(CkMyPe(),halfCreated.deq());
938 }
939
940 CmiBool CkLocRec_local::isObsolete(int nSprings,const CkArrayIndex &idx_)
941
942         int len=halfCreated.length();
943         if (len!=0) {
944                 /* This is suspicious-- the halfCreated queue should be extremely
945                  transient.  It's possible we just looked at the wrong time, though;
946                  so this is only a warning. 
947                 */
948                 CkPrintf("CkLoc WARNING> %d messages still around for uncreated element %s!\n",
949                          len,idx2str(idx));
950         }
951         //A local element never expires
952         return CmiFalse;
953 }
954
955 /**********Added for cosmology (inline function handling without parameter marshalling)***********/
956
957 LDObjHandle CkMigratable::timingBeforeCall(int* objstopped){
958
959         LDObjHandle objHandle;
960 #if CMK_LBDB_ON
961         if (getLBDB()->RunningObject(&objHandle)) {
962                 *objstopped = 1;
963                 getLBDB()->ObjectStop(objHandle);
964   }
965 #endif
966
967   //DEBS((AA"   Invoking entry %d on element %s\n"AB,epIdx,idx2str(idx)));
968         //CmiBool isDeleted=CmiFalse; //Enables us to detect deletion during processing
969         //deletedMarker=&isDeleted;
970         myRec->startTiming();
971 /*#ifndef CMK_OPTIMIZE
972         if (msg) {  Tracing: 
973                 envelope *env=UsrToEnv(msg);
974         //      CkPrintf("ckLocation.C beginExecuteDetailed %d %d \n",env->getEvent(),env->getsetArraySrcPe());
975                 if (_entryTable[epIdx]->traceEnabled)
976                         _TRACE_BEGIN_EXECUTE_DETAILED(env->getEvent(),
977                                  ForChareMsg,epIdx,env->getsetArraySrcPe(), env->getTotalsize(), idx.getProjectionID(((CkGroupID)env->getsetArrayMgr())).idx);
978         }
979 #endif*/
980
981   return objHandle;
982 }
983
984 void CkMigratable::timingAfterCall(LDObjHandle objHandle,int *objstopped){
985   
986 /*#ifndef CMK_OPTIMIZE
987         if (msg) {  Tracing: 
988                 if (_entryTable[epIdx]->traceEnabled)
989                         _TRACE_END_EXECUTE();
990         }
991 #endif*/
992 //#if CMK_LBDB_ON
993 //        if (!isDeleted) checkBufferedMigration();   // check if should migrate
994 //#endif
995 //      if (isDeleted) return CmiFalse;//We were deleted
996 //      deletedMarker=NULL;
997         ckStopTiming();
998 //      return CmiTrue;
999 #if CMK_LBDB_ON
1000         if (*objstopped) getLBDB()->ObjectStart(objHandle);
1001 #endif
1002
1003  return;
1004 }
1005 /****************************************************************************/
1006
1007
1008 CmiBool CkLocRec_local::invokeEntry(CkMigratable *obj,void *msg,
1009         int epIdx,CmiBool doFree) 
1010 {
1011
1012         DEBS((AA"   Invoking entry %d on element %s\n"AB,epIdx,idx2str(idx)));
1013         CmiBool isDeleted=CmiFalse; //Enables us to detect deletion during processing
1014         deletedMarker=&isDeleted;
1015         startTiming();
1016
1017
1018 #ifndef CMK_OPTIMIZE
1019         if (msg) { /* Tracing: */
1020                 envelope *env=UsrToEnv(msg);
1021         //      CkPrintf("ckLocation.C beginExecuteDetailed %d %d \n",env->getEvent(),env->getsetArraySrcPe());
1022                 if (_entryTable[epIdx]->traceEnabled)
1023                         _TRACE_BEGIN_EXECUTE_DETAILED(env->getEvent(),
1024                                  ForChareMsg,epIdx,env->getsetArraySrcPe(), env->getTotalsize(), idx.getProjectionID((((CkGroupID)env->getsetArrayMgr())).idx));
1025         }
1026 #endif
1027         if (doFree) 
1028            CkDeliverMessageFree(epIdx,msg,obj);
1029         else /* !doFree */
1030            CkDeliverMessageReadonly(epIdx,msg,obj);
1031
1032
1033 #ifndef CMK_OPTIMIZE
1034         if (msg) { /* Tracing: */
1035                 if (_entryTable[epIdx]->traceEnabled)
1036                         _TRACE_END_EXECUTE();
1037         }
1038 #endif
1039 #if CMK_LBDB_ON
1040         if (!isDeleted) checkBufferedMigration();   // check if should migrate
1041 #endif
1042         if (isDeleted) return CmiFalse;//We were deleted
1043         deletedMarker=NULL;
1044         stopTiming();
1045         return CmiTrue;
1046 }
1047
1048 CmiBool CkLocRec_local::deliver(CkArrayMessage *msg,CkDeliver_t type,int opts)
1049 {
1050
1051         if (type==CkDeliver_queue) { /*Send via the message queue */
1052                 if (opts & CK_MSG_KEEP)
1053                         msg = (CkArrayMessage *)CkCopyMsg((void **)&msg);
1054                 CkArrayManagerDeliver(CkMyPe(),msg,opts);
1055                 return CmiTrue;
1056         }
1057         else
1058         {
1059                 CkMigratable *obj=myLocMgr->lookupLocal(localIdx,
1060                         UsrToEnv(msg)->getsetArrayMgr());
1061                 if (obj==NULL) {//That sibling of this object isn't created yet!
1062                         if (opts & CK_MSG_KEEP)
1063                                 msg = (CkArrayMessage *)CkCopyMsg((void **)&msg);
1064                         if (msg->array_ifNotThere()!=CkArray_IfNotThere_buffer) {
1065                                 return myLocMgr->demandCreateElement(msg,CkMyPe(),type);
1066                         }
1067                         else {
1068                                 DEBS((AA"   BUFFERING message for nonexistent element %s!\n"AB,idx2str(this->idx)));
1069                                 halfCreated.enq(msg);
1070                                 return CmiTrue;
1071                         }
1072                 }
1073                         
1074                 if (msg->array_hops()>1)
1075                         myLocMgr->multiHop(msg);
1076                 CmiBool doFree = (CmiBool)!(opts & CK_MSG_KEEP);
1077 #if CMK_LBDB_ON
1078                 // if there is a running obj being measured, stop it temporarily
1079                 LDObjHandle objHandle;
1080                 int objstopped = 0;
1081                 if (the_lbdb->RunningObject(&objHandle)) {
1082                         objstopped = 1;
1083                         the_lbdb->ObjectStop(objHandle);
1084                 }
1085 #endif
1086 #if CMK_GRID_QUEUE_AVAILABLE
1087                 // retain a pointer to the sending object (needed later)
1088                 CpvAccess(CkGridObject) = obj;
1089 #endif
1090
1091
1092
1093
1094
1095 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
1096         // store the pointer to the currently executing msg
1097         envelope *env = UsrToEnv(msg);
1098         currentlyExecutingMsg = env; 
1099         thisMethodSentAMessage = false;
1100
1101         // Increase the counts for the entry that we are about to execute
1102         env->updateCounts();
1103         
1104         // Increase the reference count for the message so the user won't delete it
1105         CmiReference(env);
1106
1107         // Store the current time
1108         timeEntryMethodStarted = CmiWallTimer();
1109 #endif
1110
1111         CmiBool status = invokeEntry(obj,(void *)msg,msg->array_ep(),doFree);
1112         
1113
1114 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
1115   double timeEntryMethodEnded = CmiWallTimer();
1116   env->pathHistory.incrementTotalTime(timeEntryMethodEnded-timeEntryMethodStarted);
1117   if(!thisMethodSentAMessage){
1118     registerTerminalEntryMethod();
1119   }
1120
1121   CmiFree(env); // free the message, because we incremented its reference count above
1122
1123   // set to NULL the pointer to the currently executing msg
1124   currentlyExecutingMsg = NULL;
1125   //  CkPrintf("This entry method is %s\n", (int)thisMethodSentAMessage?"non-terminal":"terminal");
1126 #endif
1127
1128
1129
1130
1131
1132
1133 #if CMK_GRID_QUEUE_AVAILABLE
1134                 CpvAccess(CkGridObject) = NULL;
1135 #endif
1136 #if CMK_LBDB_ON
1137                 if (objstopped) the_lbdb->ObjectStart(objHandle);
1138 #endif
1139                 return status;
1140         }
1141
1142
1143
1144 }
1145
1146 #if CMK_LBDB_ON
1147 void CkLocRec_local::staticMigrate(LDObjHandle h, int dest)
1148 {
1149         CkLocRec_local *el=(CkLocRec_local *)LDObjUserData(h);
1150         DEBL((AA"Load balancer wants to migrate %s to %d\n"AB,idx2str(el->idx),dest));
1151         el->recvMigrate(dest);
1152 }
1153
1154 void CkLocRec_local::recvMigrate(int toPe)
1155 {
1156         // we are in the mode of delaying actual migration
1157         // till readyMigrate()
1158         if (readyMigrate) { migrateMe(toPe); }
1159         else nextPe = toPe;
1160 }
1161
1162 void CkLocRec_local::AsyncMigrate(CmiBool use)  
1163 {
1164         asyncMigrate = use; 
1165         the_lbdb->UseAsyncMigrate(ldHandle, use);
1166 }
1167
1168 CmiBool CkLocRec_local::checkBufferedMigration()
1169 {
1170         // we don't migrate in user's code when calling ReadyMigrate(true)
1171         // we postphone the action to here until we exit from the user code.
1172         if (readyMigrate && nextPe != -1) {
1173             int toPe = nextPe;
1174             nextPe = -1;
1175             // don't migrate inside the object call
1176             migrateMe(toPe);
1177             // don't do anything
1178             return CmiTrue;
1179         }
1180         return CmiFalse;
1181 }
1182
1183 int CkLocRec_local::MigrateToPe()
1184 {
1185         int pe = nextPe;
1186         nextPe = -1;
1187         return pe;
1188 }
1189
1190 void CkLocRec_local::setMigratable(int migratable)
1191 {
1192         if (migratable)
1193           the_lbdb->Migratable(ldHandle);
1194         else
1195           the_lbdb->NonMigratable(ldHandle);
1196 }
1197 #endif
1198
1199 /**
1200  * Represents a deleted array element (and prevents re-use).
1201  * These are a debugging aid, usable only by uncommenting a line in
1202  * the element destruction code.
1203  */
1204 class CkLocRec_dead:public CkLocRec {
1205 public:
1206         CkLocRec_dead(CkLocMgr *Narr):CkLocRec(Narr) {}
1207   
1208         virtual RecType type(void) {return dead;}
1209   
1210         virtual CmiBool deliver(CkArrayMessage *msg,CkDeliver_t type,int opts=0) {
1211                 CkPrintf("Dead array element is %s.\n",idx2str(msg->array_index()));
1212                 CkAbort("Send to dead array element!\n");
1213                 return CmiFalse;
1214         }
1215         virtual void beenReplaced(void) 
1216                 {CkAbort("Can't re-use dead array element!\n");}
1217   
1218         //Return if this element is now obsolete (it isn't)
1219         virtual CmiBool isObsolete(int nSprings,const CkArrayIndex &idx) {return CmiFalse;}     
1220 };
1221
1222 /**
1223  * This is the abstract superclass of arrayRecs that keep track of their age,
1224  * and eventually expire. Its kids are remote and buffering.
1225  */
1226 class CkLocRec_aging:public CkLocRec {
1227 private:
1228         int lastAccess;//Age when last accessed
1229 protected:
1230         //Update our access time
1231         inline void access(void) {
1232                 lastAccess=myLocMgr->getSpringCount();
1233         }
1234         //Return if we are "stale"-- we were last accessed a while ago
1235         CmiBool isStale(void) {
1236                 if (myLocMgr->getSpringCount()-lastAccess>3) return CmiTrue;
1237                 else return CmiFalse;
1238         }
1239 public:
1240         CkLocRec_aging(CkLocMgr *Narr):CkLocRec(Narr) {
1241                 lastAccess=myLocMgr->getSpringCount();
1242         }
1243         //Return if this element is now obsolete
1244         virtual CmiBool isObsolete(int nSprings,const CkArrayIndex &idx)=0;
1245         //virtual void pup(PUP::er &p) { CkLocRec::pup(p); p(lastAccess); }
1246 };
1247
1248
1249 /**
1250  * Represents a remote array element.  This is just a PE number.
1251  */
1252 class CkLocRec_remote:public CkLocRec_aging {
1253 private:
1254         int onPe;//The last known Pe for this element
1255 public:
1256         CkLocRec_remote(CkLocMgr *Narr,int NonPe)
1257                 :CkLocRec_aging(Narr)
1258                 {
1259                         onPe=NonPe;
1260 #ifndef CMK_OPTIMIZE
1261                         if (onPe==CkMyPe())
1262                                 CkAbort("ERROR!  'remote' array element on this Pe!\n");
1263 #endif
1264                 }
1265         //Return the last known processor for this element
1266         int lookupProcessor(void) {
1267                 return onPe;
1268         }  
1269         virtual RecType type(void) {return remote;}
1270   
1271         //Send a message for this element.
1272         virtual CmiBool deliver(CkArrayMessage *msg,CkDeliver_t type,int opts=0) {
1273                 /*FAULT_EVAC*/
1274                 int destPE = onPe;
1275                 if((!CmiNodeAlive(onPe) && onPe != allowMessagesOnly)){
1276 //                      printf("Delivery failed because process %d is invalid\n",onPe);
1277                         /*
1278                                 Send it to its home processor instead
1279                         */
1280                         const CkArrayIndex &idx=msg->array_index();
1281                         destPE = getNextPE(idx);
1282                 }
1283                 access();//Update our modification date
1284                 msg->array_hops()++;
1285                 DEBS((AA"   Forwarding message for element %s to %d (REMOTE)\n"AB,
1286                       idx2str(msg->array_index()),destPE));
1287                 if (opts & CK_MSG_KEEP)
1288                         msg = (CkArrayMessage *)CkCopyMsg((void **)&msg);
1289                 CkArrayManagerDeliver(destPE,msg,opts);
1290                 return CmiTrue;
1291         }
1292         //Return if this element is now obsolete
1293         virtual CmiBool isObsolete(int nSprings,const CkArrayIndex &idx) {
1294                 if (myLocMgr->isHome(idx)) 
1295                         //Home elements never become obsolete
1296                         // if they did, we couldn't deliver messages to that element.
1297                         return CmiFalse;
1298                 else if (isStale())
1299                         return CmiTrue;//We haven't been used in a long time
1300                 else
1301                         return CmiFalse;//We're fairly recent
1302         }
1303         //virtual void pup(PUP::er &p) { CkLocRec_aging::pup(p); p(onPe); }
1304 };
1305
1306
1307 /**
1308  * Buffers messages until record is replaced in the hash table, 
1309  * then delivers all messages to the replacing record.  This is 
1310  * used when a message arrives for a local element that has not
1311  * yet been created, buffering messages until the new element finally
1312  * checks in.
1313  *
1314  * It's silly to send a message to an element you won't ever create,
1315  * so this kind of record causes an abort "Stale array manager message!"
1316  * if it's left undelivered too long.
1317  */
1318 class CkLocRec_buffering:public CkLocRec_aging {
1319 private:
1320         CkQ<CkArrayMessage *> buffer;//Buffered messages.
1321 public:
1322         CkLocRec_buffering(CkLocMgr *Narr):CkLocRec_aging(Narr) {}
1323         virtual ~CkLocRec_buffering() {
1324                 if (0!=buffer.length())
1325                         CkPrintf("[%d] Warning: Messages abandoned in array manager buffer!\n", CkMyPe());
1326         }
1327   
1328         virtual RecType type(void) {return buffering;}
1329   
1330         //Buffer a message for this element.
1331         virtual CmiBool deliver(CkArrayMessage *msg,CkDeliver_t type,int opts=0) {
1332                 DEBS((AA" Queued message for %s\n"AB,idx2str(msg->array_index())));
1333                 if (opts & CK_MSG_KEEP)
1334                         msg = (CkArrayMessage *)CkCopyMsg((void **)&msg);
1335                 buffer.enq(msg);
1336                 return CmiTrue;
1337         }
1338  
1339         //This is called when this ArrayRec is about to be replaced.
1340         // We dump all our buffered messages off on the next guy,
1341         // who should know what to do with them.
1342         virtual void beenReplaced(void) {
1343                 DEBS((AA" Delivering queued messages:\n"AB));
1344                 CkArrayMessage *m;
1345                 while (NULL!=(m=buffer.deq())) {
1346                         DEBS((AA"Sending buffered message to %s\n"AB,idx2str(m->array_index())));
1347                         myLocMgr->deliverViaQueue(m);
1348                 }
1349         }
1350   
1351         //Return if this element is now obsolete
1352         virtual CmiBool isObsolete(int nSprings,const CkArrayIndex &idx) {
1353                 if (isStale()) {
1354                         /*This indicates something is seriously wrong--
1355                           buffers should be short-lived.*/
1356                         CkPrintf("WARNING: %d stale array message(s) found!\n",buffer.length());
1357                         CkArrayMessage *msg=buffer.deq();
1358                         CkPrintf("Addressed to: ");
1359                         CkPrintEntryMethod(msg->array_ep());
1360                         CkPrintf(" index %s\n",idx2str(idx));
1361                         if (myLocMgr->isHome(idx)) 
1362                                 CkPrintf("is this an out-of-bounds array index, or was it never created?\n");
1363                         else //Idx is a remote-home index
1364                                 CkPrintf("why weren't they forwarded?\n");
1365                         
1366                         // CkAbort("Stale array manager message(s)!\n");
1367                 }
1368                 return CmiFalse;
1369         }
1370   
1371 /*  virtual void pup(PUP::er &p) {
1372     CkLocRec_aging::pup(p);
1373     CkArray::pupArrayMsgQ(buffer, p);
1374     }*/
1375 };
1376
1377 /*********************** Spring Cleaning *****************/
1378 /**
1379  * Used to periodically flush out unused remote element pointers.
1380  *
1381  * Cleaning often will free up memory quickly, but slow things
1382  * down because the cleaning takes time and some not-recently-referenced
1383  * remote element pointers might be valid and used some time in 
1384  * the future.
1385  *
1386  * Also used to determine if buffered messages have become stale.
1387  */
1388 inline void CkLocMgr::springCleaning(void)
1389 {
1390   nSprings++;
1391
1392   //Poke through the hash table for old ArrayRecs.
1393   void *objp;
1394   void *keyp;
1395   
1396   CkHashtableIterator *it=hash.iterator();
1397   CmiImmediateLock(hashImmLock);
1398   while (NULL!=(objp=it->next(&keyp))) {
1399     CkLocRec *rec=*(CkLocRec **)objp;
1400     CkArrayIndex &idx=*(CkArrayIndex *)keyp;
1401     if (rec->isObsolete(nSprings,idx)) {
1402       //This record is obsolete-- remove it from the table
1403       DEBK((AA"Cleaning out old record %s\n"AB,idx2str(idx)));
1404       hash.remove(*(CkArrayIndexMax *)&idx);
1405       delete rec;
1406       it->seek(-1);//retry this hash slot
1407     }
1408   }
1409   CmiImmediateUnlock(hashImmLock);
1410   delete it;
1411 }
1412 void CkLocMgr::staticSpringCleaning(void *forWhom,double curWallTime) {
1413         DEBK((AA"Starting spring cleaning at %.2f\n"AB,CkWallTimer()));
1414         ((CkLocMgr *)forWhom)->springCleaning();
1415 }
1416
1417 // clean all buffer'ed messages and also free local objects
1418 void CkLocMgr::flushAllRecs(void)
1419 {
1420   void *objp;
1421   void *keyp;
1422     
1423   CkHashtableIterator *it=hash.iterator();
1424   CmiImmediateLock(hashImmLock);
1425   while (NULL!=(objp=it->next(&keyp))) {
1426     CkLocRec *rec=*(CkLocRec **)objp;
1427     CkArrayIndex &idx=*(CkArrayIndex *)keyp;
1428     if (rec->type() != CkLocRec::local) {
1429       hash.remove(*(CkArrayIndexMax *)&idx);
1430       delete rec;
1431       it->seek(-1);//retry this hash slot
1432     }
1433     else {
1434         callMethod((CkLocRec_local*)rec, &CkMigratable::ckDestroy);
1435         it->seek(-1);//retry this hash slot
1436     }
1437   }
1438   delete it;
1439   CmiImmediateUnlock(hashImmLock);
1440 }
1441
1442 /*************************** LocMgr: CREATION *****************************/
1443 CkLocMgr::CkLocMgr(CkGroupID mapID_,CkGroupID lbdbID_,CkArrayIndexMax& numInitial)
1444         :thisProxy(thisgroup),thislocalproxy(thisgroup,CkMyPe()),
1445          hash(17,0.3)
1446 {
1447         DEBC((AA"Creating new location manager %d\n"AB,thisgroup));
1448 // moved to _CkMigratable_initInfoInit()
1449 //      CkpvInitialize(CkMigratable_initInfo,mig_initInfo);
1450
1451         managers.init();
1452         nManagers=0;
1453         firstManager=NULL;
1454         firstFree=localLen=0;
1455         duringMigration=CmiFalse;
1456         nSprings=0;
1457         CcdCallOnConditionKeepOnPE(CcdPERIODIC_1minute,staticSpringCleaning,(void *)this, CkMyPe());
1458
1459 //Register with the map object
1460         mapID=mapID_;
1461         map=(CkArrayMap *)CkLocalBranch(mapID);
1462         if (map==NULL) CkAbort("ERROR!  Local branch of array map is NULL!");
1463         mapHandle=map->registerArray(numInitial,thisgroup);
1464
1465 //Find and register with the load balancer
1466         lbdbID = lbdbID_;
1467         initLB(lbdbID_);
1468         hashImmLock = CmiCreateImmediateLock();
1469 }
1470
1471 CkLocMgr::CkLocMgr(CkMigrateMessage* m)
1472         :IrrGroup(m),thisProxy(thisgroup),thislocalproxy(thisgroup,CkMyPe()),hash(17,0.3)
1473 {
1474         managers.init();
1475         nManagers=0;
1476         firstManager=NULL;
1477         firstFree=localLen=0;
1478         duringMigration=CmiFalse;
1479         nSprings=0;
1480         CcdCallOnConditionKeepOnPE(CcdPERIODIC_1minute,staticSpringCleaning,(void *)this, CkMyPe());
1481         hashImmLock = CmiCreateImmediateLock();
1482 }
1483
1484 void CkLocMgr::pup(PUP::er &p){
1485         IrrGroup::pup(p);
1486         p|mapID;
1487         p|lbdbID;
1488         mapID = _RRMapID;
1489         if(p.isUnpacking()){
1490                 thisProxy=thisgroup;
1491                 CProxyElement_CkLocMgr newlocalproxy(thisgroup,CkMyPe());
1492                 thislocalproxy=newlocalproxy;
1493                 //Register with the map object
1494                 map=(CkArrayMap *)CkLocalBranch(mapID);
1495                 if (map==NULL) CkAbort("ERROR!  Local branch of array map is NULL!");
1496                 CkArrayIndexMax emptyIndex;
1497                 mapHandle=map->registerArray(emptyIndex,thisgroup);
1498                 // _lbdb is the fixed global groupID
1499                 initLB(lbdbID);
1500                 // delay doneInserting when it is unpacking during restart.
1501                 // to prevent load balancing kicking in
1502                 if (!CkInRestarting()) 
1503                         doneInserting();
1504         }
1505 }
1506
1507 void _CkLocMgrInit(void) {
1508   /* Don't trace our deliver method--it does its own tracing */
1509   CkDisableTracing(CkIndex_CkLocMgr::deliverInline(0));
1510 }
1511
1512 /// Add a new local array manager to our list.
1513 /// Returns a new CkMigratableList for the manager to store his
1514 /// elements in.
1515 CkMigratableList *CkLocMgr::addManager(CkArrayID id,CkArrMgr *mgr)
1516 {
1517         CK_MAGICNUMBER_CHECK
1518         DEBC((AA"Adding new array manager\n"AB));
1519         //Link new manager into list
1520         ManagerRec *n=new ManagerRec;
1521         managers.find(id)=n;
1522         n->next=firstManager;
1523         n->mgr=mgr;
1524         n->elts.setSize(localLen);
1525         nManagers++;
1526         firstManager=n;
1527         return &n->elts;
1528 }
1529
1530 /// Return the next unused local element index.
1531 int CkLocMgr::nextFree(void) {
1532         if (firstFree>=localLen)
1533         {//Need more space in the local index arrays-- enlarge them
1534                 int oldLen=localLen;
1535                 localLen=localLen*2+8;
1536                 DEBC((AA"Growing the local list from %d to %d...\n"AB,oldLen,localLen));
1537                 for (ManagerRec *m=firstManager;m!=NULL;m=m->next)
1538                         m->elts.setSize(localLen);
1539                 //Update the free list
1540                 freeList.resize(localLen);
1541                 for (int i=oldLen;i<localLen;i++)
1542                         freeList[i]=i+1;
1543         }
1544         int localIdx=firstFree;
1545         if (localIdx==-1) CkAbort("CkLocMgr free list corrupted!");
1546         firstFree=freeList[localIdx];
1547         freeList[localIdx]=-1; //Mark as used
1548         return localIdx;
1549 }
1550
1551 CkLocRec_remote *CkLocMgr::insertRemote(const CkArrayIndex &idx,int nowOnPe)
1552 {
1553         DEBS((AA"Remote element %s lives on %d\n"AB,idx2str(idx),nowOnPe));
1554         CkLocRec_remote *rem=new CkLocRec_remote(this,nowOnPe);
1555         insertRec(rem,idx);
1556         return rem;
1557 }
1558
1559 //This element now lives on the given Pe
1560 void CkLocMgr::inform(const CkArrayIndex &idx,int nowOnPe)
1561 {
1562         if (nowOnPe==CkMyPe())
1563                 return; //Never insert a "remote" record pointing here
1564         CkLocRec *rec=elementNrec(idx);
1565         if (rec!=NULL && rec->type()==CkLocRec::local)
1566                 return; //Never replace a local element's record!
1567         insertRemote(idx,nowOnPe);
1568 }
1569
1570 //Tell this element's home processor it now lives "there"
1571 void CkLocMgr::informHome(const CkArrayIndex &idx,int nowOnPe)
1572 {
1573         int home=homePe(idx);
1574         if (home!=CkMyPe() && home!=nowOnPe) {
1575                 //Let this element's home Pe know it lives here now
1576                 DEBC((AA"  Telling %s's home %d that it lives on %d.\n"AB,idx2str(idx),home,nowOnPe));
1577                 thisProxy[home].updateLocation(idx,nowOnPe);
1578         }
1579 }
1580
1581 CkLocRec_local *CkLocMgr::createLocal(const CkArrayIndex &idx, 
1582                 CmiBool forMigration, CmiBool ignoreArrival,
1583                 CmiBool notifyHome)
1584 {
1585         int localIdx=nextFree();
1586         DEBC((AA"Adding new record for element %s at local index %d\n"AB,idx2str(idx),localIdx));
1587         CkLocRec_local *rec=new CkLocRec_local(this,forMigration,ignoreArrival,idx,localIdx);
1588         insertRec(rec,idx); //Add to global hashtable
1589         if (notifyHome) informHome(idx,CkMyPe());
1590         return rec;
1591 }
1592
1593 //Add a new local array element, calling element's constructor
1594 CmiBool CkLocMgr::addElement(CkArrayID id,const CkArrayIndex &idx,
1595                 CkMigratable *elt,int ctorIdx,void *ctorMsg)
1596 {
1597         CK_MAGICNUMBER_CHECK
1598         CkLocRec *oldRec=elementNrec(idx);
1599         CkLocRec_local *rec;
1600         if (oldRec==NULL||oldRec->type()!=CkLocRec::local) 
1601         { //This is the first we've heard of that element-- add new local record
1602                 rec=createLocal(idx,CmiFalse,CmiFalse,CmiTrue);
1603         } else 
1604         { //rec is *already* local-- must not be the first insertion    
1605                 rec=((CkLocRec_local *)oldRec);
1606                 rec->addedElement();
1607         }
1608         if (!addElementToRec(rec,managers.find(id),elt,ctorIdx,ctorMsg)) return CmiFalse;
1609         elt->ckFinishConstruction();
1610         return CmiTrue;
1611 }
1612
1613 //As above, but shared with the migration code
1614 CmiBool CkLocMgr::addElementToRec(CkLocRec_local *rec,ManagerRec *m,
1615                 CkMigratable *elt,int ctorIdx,void *ctorMsg)
1616 {//Insert the new element into its manager's local list
1617         int localIdx=rec->getLocalIndex();
1618         if (m->elts.get(localIdx)!=NULL) CkAbort("Cannot insert array element twice!");
1619         m->elts.put(elt,localIdx); //Local element table
1620
1621 //Call the element's constructor
1622         DEBC((AA"Constructing element %s of array\n"AB,idx2str(rec->getIndex())));
1623         CkMigratable_initInfo &i=CkpvAccess(mig_initInfo);
1624         i.locRec=rec;
1625         i.chareType=_entryTable[ctorIdx]->chareIdx;
1626         if (!rec->invokeEntry(elt,ctorMsg,ctorIdx,CmiTrue)) return CmiFalse;
1627
1628 #if CMK_OUT_OF_CORE
1629         /* Register new element with out-of-core */
1630         PUP::sizer p_getSize; elt->pup(p_getSize);
1631         elt->prefetchObjID=CooRegisterObject(&CkArrayElementPrefetcher,p_getSize.size(),elt);
1632 #endif
1633         
1634         return CmiTrue;
1635 }
1636 void CkLocMgr::updateLocation(const CkArrayIndexMax &idx,int nowOnPe) {
1637         inform(idx,nowOnPe);
1638 }
1639
1640 /*************************** LocMgr: DELETION *****************************/
1641 /// This index will no longer be used-- delete the associated elements
1642 void CkLocMgr::reclaim(const CkArrayIndex &idx,int localIdx) {
1643         CK_MAGICNUMBER_CHECK
1644         DEBC((AA"Destroying element %s (local %d)\n"AB,idx2str(idx),localIdx));
1645         //Delete, and mark as empty, each array element
1646         for (ManagerRec *m=firstManager;m!=NULL;m=m->next) {
1647                 delete m->elts.get(localIdx);
1648                 m->elts.empty(localIdx);
1649         }
1650         
1651         removeFromTable(idx);
1652         
1653         //Link local index into free list
1654         freeList[localIdx]=firstFree;
1655         firstFree=localIdx;
1656         if (!duringMigration) 
1657         { //This is a local element dying a natural death
1658                 int home=homePe(idx);
1659                 if (home!=CkMyPe())
1660                         thisProxy[home].reclaimRemote(idx,CkMyPe());
1661         /*      //Install a zombie to keep the living from re-using this index.
1662                 insertRecN(new CkLocRec_dead(this),idx); */
1663         }
1664 }
1665
1666 void CkLocMgr::reclaimRemote(const CkArrayIndexMax &idx,int deletedOnPe) {
1667         DEBC((AA"Our element %s died on PE %d\n"AB,idx2str(idx),deletedOnPe));
1668         CkLocRec *rec=elementNrec(idx);
1669         if (rec==NULL) return; //We never knew him
1670         if (rec->type()==CkLocRec::local) return; //He's already been reborn
1671         removeFromTable(idx);
1672         delete rec;
1673 }
1674 void CkLocMgr::removeFromTable(const CkArrayIndex &idx) {
1675 #ifndef CMK_OPTIMIZE
1676         //Make sure it's actually in the table before we delete it
1677         if (NULL==elementNrec(idx))
1678                 CkAbort("CkLocMgr::removeFromTable called on invalid index!");
1679 #endif
1680         CmiImmediateLock(hashImmLock);
1681         hash.remove(*(CkArrayIndexMax *)&idx);
1682         CmiImmediateUnlock(hashImmLock);
1683 #ifndef CMK_OPTIMIZE
1684         //Make sure it's really gone
1685         if (NULL!=elementNrec(idx))
1686                 CkAbort("CkLocMgr::removeFromTable called, but element still there!");
1687 #endif
1688 }
1689
1690 /************************** LocMgr: MESSAGING *************************/
1691 /// Deliver message to this element, going via the scheduler if local
1692 void CkLocMgr::deliver(CkMessage *m,CkDeliver_t type,int opts) {
1693         DEBS((AA"deliver \n"AB));
1694         CK_MAGICNUMBER_CHECK
1695         CkArrayMessage *msg=(CkArrayMessage *)m;
1696
1697
1698         const CkArrayIndex &idx=msg->array_index();
1699         DEBS((AA"deliver %s\n"AB,idx2str(idx)));
1700         if (type==CkDeliver_queue)
1701                 _TRACE_CREATION_DETAILED(UsrToEnv(m),msg->array_ep());
1702         CkLocRec *rec=elementNrec(idx);
1703         if(rec != NULL){
1704                 DEBS((AA"deliver %s of type %d \n"AB,idx2str(idx),rec->type()));
1705         }else{
1706                 DEBS((AA"deliver %s rec is null\n"AB,idx2str(idx)));
1707         }
1708 #if CMK_LBDB_ON
1709         if (type==CkDeliver_queue) {
1710                 if (!(opts & CK_MSG_LB_NOTRACE)) {
1711                 if(rec!=NULL) the_lbdb->Send(myLBHandle,idx2LDObjid(idx),UsrToEnv(msg)->getTotalsize(), rec->lookupProcessor());
1712                 else /*rec==NULL*/ the_lbdb->Send(myLBHandle,idx2LDObjid(idx),UsrToEnv(msg)->getTotalsize(),homePe(msg->array_index()));
1713                 }
1714         }
1715 #endif
1716 #if CMK_GRID_QUEUE_AVAILABLE
1717         int gridSrcPE;
1718         int gridSrcCluster;
1719         int gridDestPE;
1720         int gridDestCluster;
1721         CkMigratable *obj;
1722         ArrayElement *obj2;
1723         CkGroupID gid;
1724         int *data;
1725
1726         obj = (CkMigratable *) CpvAccess(CkGridObject);   // CkGridObject is a pointer to the sending object (retained earlier)
1727         if (obj != NULL) {
1728           obj2 = dynamic_cast<ArrayElement *> (obj);
1729           if (obj2 > 0) {
1730             // Get the sending object's array gid and indexes.
1731             // These are guaranteed to exist due to the succeeding dynamic cast above.
1732             gid = obj2->ckGetArrayID ();
1733             data = obj2->thisIndexMax.data ();
1734
1735             // Get the source PE and destination PE.
1736             gridSrcPE = CkMyPe ();
1737             if (rec != NULL) {
1738               gridDestPE = rec->lookupProcessor ();
1739             } else {
1740               gridDestPE = homePe (msg->array_index ());
1741             }
1742
1743             // Get the source cluster and destination cluster.
1744             gridSrcCluster = CmiGetCluster (gridSrcPE);
1745             gridDestCluster = CmiGetCluster (gridDestPE);
1746
1747             // If the Grid queue interval is greater than zero, it means that the more complicated
1748             // technique for registering border objects that exceed a specified threshold of
1749             // cross-cluster messages within a specified interval (and deregistering border objects
1750             // that do not meet this threshold) is used.  Otherwise a much simpler technique is used
1751             // where a border object is registered immediately upon sending a single cross-cluster
1752             // message (and deregistered when load balancing takes place).
1753             if (obj2->grid_queue_interval > 0) {
1754               // Increment the sending object's count of all messages.
1755               obj2->msg_count += 1;
1756
1757               // If the source cluster and destination cluster differ, this is a Grid message.
1758               // (Increment the count of all Grid messages.)
1759               if (gridSrcCluster != gridDestCluster) {
1760                 obj2->msg_count_grid += 1;
1761               }
1762
1763               // If the number of messages exceeds the interval, check to see if the object has
1764               // sent enough cross-cluster messages to qualify as a border object.
1765               if (obj2->msg_count >= obj2->grid_queue_interval) {
1766                 if (obj2->msg_count_grid >= obj2->grid_queue_threshold) {
1767                   // The object is a border object; if it is not already registered, register it.
1768                   if (!obj2->border_flag) {
1769                     CmiGridQueueRegister (gid.idx, obj2->thisIndexMax.nInts, data[0], data[1], data[2]);
1770                   }
1771                   obj2->border_flag = 1;
1772                 } else {
1773                   // The object is not a border object; if it is registered, deregister it.
1774                   if (obj2->border_flag) {
1775                     CmiGridQueueDeregister (gid.idx, obj2->thisIndexMax.nInts, data[0], data[1], data[2]);
1776                   }
1777                   obj2->border_flag = 0;
1778                 }
1779                 // Reset the counts.
1780                 obj2->msg_count = 0;
1781                 obj2->msg_count_grid = 0;
1782               }
1783             } else {
1784               if (gridSrcCluster != gridDestCluster) {
1785                 CmiGridQueueRegister (gid.idx, obj2->thisIndexMax.nInts, data[0], data[1], data[2]);
1786               }
1787             }
1788           }
1789
1790           // Reset the CkGridObject pointer.
1791           CpvAccess(CkGridObject) = NULL;
1792         }
1793 #endif
1794         /**FAULT_EVAC*/
1795         if (rec!=NULL){
1796                 CmiBool result = rec->deliver(msg,type,opts);
1797                 if(!result){
1798                 /*      //DEBS((AA"deliver %s failed type %d \n"AB,idx2str(idx),rec->type()));
1799                         DEBS((AA"deliver %s failed \n"AB,idx2str(idx)));
1800                         if(rec->type() == CkLocRec::remote){
1801                                 if (opts & CK_MSG_KEEP)
1802                                         msg = (CkArrayMessage *)CkCopyMsg((void **)&msg);
1803                                 deliverUnknown(msg,type);
1804                         }*/
1805                 }
1806         }else /* rec==NULL*/ {
1807                 if (opts & CK_MSG_KEEP)
1808                         msg = (CkArrayMessage *)CkCopyMsg((void **)&msg);
1809                 deliverUnknown(msg,type,opts);
1810         }
1811
1812 }
1813
1814 /// This index is not hashed-- somehow figure out what to do.
1815 CmiBool CkLocMgr::deliverUnknown(CkArrayMessage *msg,CkDeliver_t type,int opts)
1816 {
1817         CK_MAGICNUMBER_CHECK
1818         const CkArrayIndex &idx=msg->array_index();
1819         int onPe=homePe(idx);
1820         if (onPe!=CkMyPe()) 
1821         {// Forward the message to its home processor
1822                 DEBM((AA"Forwarding message for unknown %s to home %d \n"AB,idx2str(idx),onPe));
1823                 msg->array_hops()++;
1824                 CkArrayManagerDeliver(onPe,msg,opts);
1825                 return CmiTrue;
1826         }
1827         else
1828         { // We *are* the home processor:
1829         //Check if the element's array manager has been registered yet:
1830           CkArrMgr *mgr=managers.find(UsrToEnv((void *)msg)->getsetArrayMgr())->mgr;
1831           if (!mgr) { //No manager yet-- postpone the message (stupidly)
1832             if (CkInRestarting()) {
1833               // during restarting, this message should be ignored
1834               delete msg;
1835             }
1836             else {
1837               CkArrayManagerDeliver(CkMyPe(),msg); 
1838             }
1839           }
1840           else { // Has a manager-- must buffer the message
1841             DEBC((AA"Adding buffer for unknown element %s\n"AB,idx2str(idx)));
1842             CkLocRec *rec=new CkLocRec_buffering(this);
1843             insertRecN(rec,idx);
1844             rec->deliver(msg,type);
1845           
1846             if (msg->array_ifNotThere()!=CkArray_IfNotThere_buffer) 
1847             { //Demand-create the element:
1848               return demandCreateElement(msg,-1,type);
1849             }
1850           }
1851           return CmiTrue;
1852         }
1853 }
1854
1855 CmiBool CkLocMgr::demandCreateElement(CkArrayMessage *msg,int onPe,CkDeliver_t type)
1856 {
1857         CK_MAGICNUMBER_CHECK
1858         const CkArrayIndex &idx=msg->array_index();
1859         int chareType=_entryTable[msg->array_ep()]->chareIdx;
1860         int ctor=_chareTable[chareType]->getDefaultCtor();
1861         if (ctor==-1) CkAbort("Can't create array element to handle message--\n"
1862                               "The element has no default constructor in the .ci file!\n");
1863         if (onPe==-1) 
1864         { //Decide where element needs to live
1865                 if (msg->array_ifNotThere()==CkArray_IfNotThere_createhere) 
1866                         onPe=UsrToEnv(msg)->getsetArraySrcPe();
1867                 else //Createhome
1868                         onPe=homePe(idx);
1869         }
1870         
1871         //Find the manager and build the element
1872         DEBC((AA"Demand-creating element %s on pe %d\n"AB,idx2str(idx),onPe));
1873         CkArrMgr *mgr=managers.find(UsrToEnv((void *)msg)->getsetArrayMgr())->mgr;
1874         if (!mgr) CkAbort("Tried to demand-create for nonexistent arrMgr");
1875         return mgr->demandCreateElement(idx,onPe,ctor,type);
1876 }
1877
1878 //This message took several hops to reach us-- fix it
1879 void CkLocMgr::multiHop(CkArrayMessage *msg)
1880 {
1881         CK_MAGICNUMBER_CHECK
1882         int srcPe=msg->array_getSrcPe();
1883         if (srcPe==CkMyPe())
1884                 DEB((AA"Odd routing: local element %s is %d hops away!\n"AB,idx2str(msg),msg->array_hops()));
1885         else
1886         {//Send a routing message letting original sender know new element location
1887                 DEBS((AA"Sending update back to %d for element\n"AB,srcPe,idx2str(msg)));
1888                 thisProxy[srcPe].updateLocation(msg->array_index(),CkMyPe());
1889         }
1890 }
1891
1892 /************************** LocMgr: ITERATOR *************************/
1893 CkLocation::CkLocation(CkLocMgr *mgr_, CkLocRec_local *rec_)
1894         :mgr(mgr_), rec(rec_) {}
1895         
1896 const CkArrayIndex &CkLocation::getIndex(void) const {
1897         return rec->getIndex();
1898 }
1899
1900 void CkLocation::destroyAll() {
1901         mgr->callMethod(rec, &CkMigratable::ckDestroy);
1902 }
1903
1904 void CkLocation::pup(PUP::er &p) {
1905         mgr->pupElementsFor(p,rec,CkElementCreation_migrate);
1906 }
1907
1908 CkLocIterator::~CkLocIterator() {}
1909
1910 /// Iterate over our local elements:
1911 void CkLocMgr::iterate(CkLocIterator &dest) {
1912   //Poke through the hash table for local ArrayRecs.
1913   void *objp;
1914   CkHashtableIterator *it=hash.iterator();
1915   CmiImmediateLock(hashImmLock);
1916   while (NULL!=(objp=it->next())) {
1917     CkLocRec *rec=*(CkLocRec **)objp;
1918     if (rec->type()==CkLocRec::local) {
1919       CkLocation loc(this,(CkLocRec_local *)rec);
1920       dest.addLocation(loc);
1921     }
1922   }
1923   CmiImmediateUnlock(hashImmLock);
1924   delete it;
1925 }
1926
1927
1928
1929
1930 /************************** LocMgr: MIGRATION *************************/
1931
1932 void CkLocMgr::pupElementsFor(PUP::er &p,CkLocRec_local *rec,
1933                 CkElementCreation_t type)
1934 {
1935         p.comment("-------- Array Location --------");
1936         register ManagerRec *m;
1937         int localIdx=rec->getLocalIndex();
1938
1939         //First pup the element types
1940         // (A separate loop so ckLocal works even in element pup routines)
1941         for (m=firstManager;m!=NULL;m=m->next) {
1942                 int elCType;
1943                 if (!p.isUnpacking())
1944                 { //Need to find the element's existing type
1945                         CkMigratable *elt=m->element(localIdx);
1946                         if (elt) elCType=elt->ckGetChareType();
1947                         else elCType=-1; //Element hasn't been created
1948                 }
1949                 p(elCType);
1950                 if (p.isUnpacking() && elCType!=-1) {
1951                         //Create the element
1952                         CkMigratable *elt=m->mgr->allocateMigrated(elCType,rec->getIndex(),type);
1953                         int migCtorIdx=_chareTable[elCType]->getMigCtor();
1954                         //Insert into our tables and call migration constructor
1955                         if (!addElementToRec(rec,m,elt,migCtorIdx,NULL)) return;
1956                 }
1957         }
1958         //Next pup the element data
1959         for (m=firstManager;m!=NULL;m=m->next) {
1960                 CkMigratable *elt=m->element(localIdx);
1961                 if (elt!=NULL) 
1962                 {
1963                        elt->pup(p);
1964                 }
1965         }
1966 }
1967
1968 /// Call this member function on each element of this location:
1969 void CkLocMgr::callMethod(CkLocRec_local *rec,CkMigratable_voidfn_t fn)
1970 {
1971         int localIdx=rec->getLocalIndex();
1972         for (ManagerRec *m=firstManager;m!=NULL;m=m->next) {
1973                 CkMigratable *el=m->element(localIdx);
1974                 if (el) (el->* fn)();
1975         }
1976 }
1977
1978 /// return a list of migratables in this local record
1979 void CkLocMgr::migratableList(CkLocRec_local *rec, CkVec<CkMigratable *> &list)
1980 {
1981         register ManagerRec *m;
1982         int localIdx=rec->getLocalIndex();
1983
1984         for (m=firstManager;m!=NULL;m=m->next) {
1985                 CkMigratable *elt=m->element(localIdx);
1986                 if (elt) list.push_back(elt);
1987         }
1988 }
1989
1990 /// Migrate this local element away to another processor.
1991 void CkLocMgr::emigrate(CkLocRec_local *rec,int toPe)
1992 {
1993         CK_MAGICNUMBER_CHECK
1994         if (toPe==CkMyPe()) return; //You're already there!
1995         /*
1996                 FAULT_EVAC
1997                 if the toProcessor is already marked as invalid, dont emigrate
1998                 Shouldn't happen but might
1999         */
2000         if(!CmiNodeAlive(toPe)){
2001                 return;
2002         }
2003
2004         int localIdx=rec->getLocalIndex();
2005         CkArrayIndexMax idx=rec->getIndex();
2006
2007 #if CMK_OUT_OF_CORE
2008         /* Load in any elements that are out-of-core */
2009         for (ManagerRec *m=firstManager;m!=NULL;m=m->next) {
2010                 CkMigratable *el=m->element(localIdx);
2011                 if (el) if (!el->isInCore) CooBringIn(el->prefetchObjID);
2012         }
2013 #endif
2014
2015         //Let all the elements know we're leaving
2016         callMethod(rec,&CkMigratable::ckAboutToMigrate);
2017         /*EVAC*/
2018
2019 //First pass: find size of migration message
2020         int bufSize;
2021         {
2022                 PUP::sizer p;
2023                 p(nManagers);
2024                 pupElementsFor(p,rec,CkElementCreation_migrate);
2025                 bufSize=p.size(); 
2026         }
2027
2028 //Allocate and pack into message
2029         int doubleSize=bufSize/sizeof(double)+1;
2030         CkArrayElementMigrateMessage *msg = 
2031                 new (doubleSize, 0) CkArrayElementMigrateMessage;
2032         msg->idx=idx;
2033         msg->length=bufSize;
2034 #if CMK_LBDB_ON
2035         msg->ignoreArrival = rec->isAsyncMigrate()?1:0;
2036 #endif
2037         /*
2038                 FAULT_EVAC
2039         */
2040         msg->bounced = rec->isBounced();
2041         {
2042                 PUP::toMem p(msg->packData); 
2043                 p.becomeDeleting(); 
2044                 p(nManagers);
2045                 pupElementsFor(p,rec,CkElementCreation_migrate);
2046                 if (p.size()!=bufSize) {
2047                         CkError("ERROR! Array element claimed it was %d bytes to a"
2048                                 "sizing PUP::er, but copied %d bytes into the packing PUP::er!\n",
2049                                 bufSize,p.size());
2050                         CkAbort("Array element's pup routine has a direction mismatch.\n");
2051                 }
2052         }
2053
2054         DEBM((AA"Migrated index size %s to %d \n"AB,idx2str(idx),toPe));        
2055
2056 //Send off message and delete old copy
2057         thisProxy[toPe].immigrate(msg);
2058         duringMigration=CmiTrue;
2059         delete rec; //Removes elements, hashtable entries, local index
2060         
2061         
2062         duringMigration=CmiFalse;
2063         //The element now lives on another processor-- tell ourselves and its home
2064         inform(idx,toPe);
2065         informHome(idx,toPe);
2066         CK_MAGICNUMBER_CHECK
2067 }
2068
2069 /**
2070   Migrating array element is arriving on this processor.
2071 */
2072 void CkLocMgr::immigrate(CkArrayElementMigrateMessage *msg)
2073 {
2074         CkArrayMessage *amsg=(CkArrayMessage *)msg;
2075         const CkArrayIndex &idx=msg->idx;
2076                 
2077         PUP::fromMem p(msg->packData); 
2078         
2079         int nMsgMan;
2080         p(nMsgMan);
2081         if (nMsgMan<nManagers)
2082                 CkAbort("Array element arrived from location with fewer managers!\n");
2083         if (nMsgMan>nManagers) {
2084                 //Some array managers haven't registered yet-- throw it back
2085                 DEBM((AA"Busy-waiting for array registration on migrating %s\n"AB,idx2str(idx)));
2086                 thisProxy[CkMyPe()].immigrate(msg);
2087                 return;
2088         }
2089
2090         //Create a record for this element
2091         CkLocRec_local *rec=createLocal(idx,CmiTrue,msg->ignoreArrival,CmiFalse /* home told on departure */ );
2092         
2093         //Create the new elements as we unpack the message
2094         pupElementsFor(p,rec,CkElementCreation_migrate);
2095         if (p.size()!=msg->length) {
2096                 CkError("ERROR! Array element claimed it was %d bytes to a"
2097                         "packing PUP::er, but %d bytes in the unpacking PUP::er!\n",
2098                         msg->length,p.size());
2099                 CkError("(I have %d managers; he claims %d managers)\n",
2100                         nManagers,nMsgMan);
2101                 
2102                 CkAbort("Array element's pup routine has a direction mismatch.\n");
2103         }
2104         /*
2105                 FAULT_EVAC
2106                         if this element came in as a result of being bounced off some other process,
2107                         then it needs to be resumed. It is assumed that it was bounced because load 
2108                         balancing caused it to move into a processor which later crashed
2109         */
2110         if(msg->bounced){
2111                 callMethod(rec,&CkMigratable::ResumeFromSync);
2112         }
2113         
2114         //Let all the elements know we've arrived
2115         callMethod(rec,&CkMigratable::ckJustMigrated);
2116         /*FAULT_EVAC
2117                 If this processor has started evacuating array elements on it 
2118                 dont let new immigrants in. If they arrive send them to what
2119                 would be their correct homePE.
2120                 Leave a record here mentioning the processor where it got sent
2121         */
2122         
2123         if(CpvAccess(startedEvac)){
2124                 int newhomePE = getNextPE(idx);
2125                 DEBM((AA"Migrated into failed processor index size %s resent to %d \n"AB,idx2str(idx),newhomePE));      
2126                 CkLocMgr *mgr = rec->getLocMgr();
2127                 int targetPE=getNextPE(idx);
2128                 //set this flag so that load balancer is not informed when
2129                 //this element migrates
2130                 rec->AsyncMigrate(CmiTrue);
2131                 rec->Bounced(CmiTrue);
2132                 mgr->emigrate(rec,targetPE);
2133                 
2134         }
2135
2136         delete msg;
2137 }
2138
2139 void CkLocMgr::restore(const CkArrayIndex &idx, PUP::er &p)
2140 {
2141         CkLocRec_local *rec=createLocal(idx,CmiFalse,CmiFalse,CmiTrue /* home doesn't know yet */ );
2142
2143         //Create the new elements as we unpack the message
2144         pupElementsFor(p,rec,CkElementCreation_restore);
2145 }
2146
2147
2148 /// Insert and unpack this array element from this checkpoint (e.g., from CkLocation::pup)
2149 void CkLocMgr::resume(const CkArrayIndex &idx, PUP::er &p)
2150 {
2151         CkLocRec_local *rec=createLocal(idx,CmiFalse,CmiFalse,CmiTrue /* home doesn't know yet */ );
2152
2153         //Create the new elements as we unpack the message
2154         pupElementsFor(p,rec,CkElementCreation_resume);
2155
2156         callMethod(rec,&CkMigratable::ckJustMigrated);
2157 }
2158
2159 /********************* LocMgr: UTILITY ****************/
2160 void CkMagicNumber_impl::badMagicNumber(
2161         int expected,const char *file,int line,void *obj) const
2162 {
2163         CkError("FAILURE on pe %d, %s:%d> Expected %p's magic number "
2164                 "to be 0x%08x; but found 0x%08x!\n", CkMyPe(),file,line,obj,
2165                 expected, magic);
2166         CkAbort("Bad magic number detected!  This implies either\n"
2167                 "the heap or a message was corrupted!\n");
2168 }
2169 CkMagicNumber_impl::CkMagicNumber_impl(int m) :magic(m) { }
2170
2171 //Look up the object with this array index, or return NULL
2172 CkMigratable *CkLocMgr::lookup(const CkArrayIndex &idx,CkArrayID aid) {
2173         CkLocRec *rec=elementNrec(idx);
2174         if (rec==NULL) return NULL;
2175         else return rec->lookupElement(aid);
2176 }
2177 //"Last-known" location (returns a processor number)
2178 int CkLocMgr::lastKnown(const CkArrayIndex &idx) {
2179         CkLocMgr *vthis=(CkLocMgr *)this;//Cast away "const"
2180         CkLocRec *rec=vthis->elementNrec(idx);
2181         int pe=-1;
2182         if (rec!=NULL) pe=rec->lookupProcessor();
2183         if (pe==-1) return homePe(idx);
2184         else{
2185                 /*
2186                         FAULT_EVAC
2187                         if the lastKnownPE is invalid return homePE and delete this record
2188                 */
2189                 if(!CmiNodeAlive(pe)){
2190                         removeFromTable(idx);
2191                         return homePe(idx);
2192                 }
2193                 return pe;
2194         }       
2195 }
2196 /// Return true if this array element lives on another processor
2197 bool CkLocMgr::isRemote(const CkArrayIndex &idx,int *onPe) const
2198 {
2199         CkLocMgr *vthis=(CkLocMgr *)this;//Cast away "const"
2200         CkLocRec *rec=vthis->elementNrec(idx);
2201         if (rec==NULL || rec->type()!=CkLocRec::remote) 
2202                 return false; /* not definitely a remote element */
2203         else /* element is indeed remote */
2204         {
2205                 *onPe=rec->lookupProcessor();
2206                 return true;
2207         }
2208 }
2209
2210 static const char *rec2str[]={
2211     "base (INVALID)",//Base class (invalid type)
2212     "local",//Array element that lives on this Pe
2213     "remote",//Array element that lives on some other Pe
2214     "buffering",//Array element that was just created
2215     "dead"//Deleted element (for debugging)
2216 };
2217
2218 //Add given element array record at idx, replacing the existing record
2219 void CkLocMgr::insertRec(CkLocRec *rec,const CkArrayIndex &idx) {
2220         CkLocRec *old=elementNrec(idx);
2221         insertRecN(rec,idx);
2222         if (old!=NULL) {
2223                 DEBC((AA"  replaces old rec(%s) for %s\n"AB,rec2str[old->type()],idx2str(idx)));
2224                 //There was an old element at this location
2225                 if (old->type()==CkLocRec::local && rec->type()==CkLocRec::local) {
2226                     if (!CkInRestarting()) {    // ok if it is restarting
2227                         CkPrintf("ERROR! Duplicate array index: %s\n",idx2str(idx));
2228                         CkAbort("Duplicate array index used");
2229                     }
2230                 }
2231                 old->beenReplaced();
2232                 delete old;
2233         }
2234 }
2235
2236 //Add given record, when there is guarenteed to be no prior record
2237 void CkLocMgr::insertRecN(CkLocRec *rec,const CkArrayIndex &idx) {
2238         DEBC((AA"  adding new rec(%s) for %s\n"AB,rec2str[rec->type()],idx2str(idx)));
2239         CmiImmediateLock(hashImmLock);
2240         hash.put(*(CkArrayIndexMax *)&idx)=rec;
2241         CmiImmediateUnlock(hashImmLock);
2242 }
2243
2244 //Call this on an unrecognized array index
2245 static void abort_out_of_bounds(const CkArrayIndex &idx)
2246 {
2247   CkPrintf("ERROR! Unknown array index: %s\n",idx2str(idx));
2248   CkAbort("Array index out of bounds\n");
2249 }
2250
2251 //Look up array element in hash table.  Index out-of-bounds if not found.
2252 CkLocRec *CkLocMgr::elementRec(const CkArrayIndex &idx) {
2253 #ifdef CMK_OPTIMIZE
2254 //Assume the element will be found
2255         return hash.getRef(*(CkArrayIndexMax *)&idx);
2256 #else
2257 //Include an out-of-bounds check if the element isn't found
2258         CkLocRec *rec=elementNrec(idx);
2259         if (rec==NULL) abort_out_of_bounds(idx);
2260         return rec;
2261 #endif
2262 }
2263
2264 //Look up array element in hash table.  Return NULL if not there.
2265 CkLocRec *CkLocMgr::elementNrec(const CkArrayIndex &idx) {
2266         return hash.get(*(CkArrayIndexMax *)&idx);
2267 }
2268
2269 /********************* LocMgr: LOAD BALANCE ****************/
2270
2271 #if !CMK_LBDB_ON
2272 //Empty versions of all load balancer calls
2273 void CkLocMgr::initLB(CkGroupID lbdbID_) {}
2274 void CkLocMgr::startInserting(void) {}
2275 void CkLocMgr::doneInserting(void) {}
2276 void CkLocMgr::dummyAtSync(void) {}
2277 #endif
2278
2279
2280 #if CMK_LBDB_ON
2281 void CkLocMgr::initLB(CkGroupID lbdbID_)
2282 { //Find and register with the load balancer
2283         the_lbdb = (LBDatabase *)CkLocalBranch(lbdbID_);
2284         if (the_lbdb == 0)
2285                 CkAbort("LBDatabase not yet created?\n");
2286         DEBL((AA"Connected to load balancer %p\n"AB,the_lbdb));
2287
2288         // Register myself as an object manager
2289         LDOMid myId;
2290         myId.id = thisgroup;
2291         LDCallbacks myCallbacks;
2292         myCallbacks.migrate = (LDMigrateFn)CkLocRec_local::staticMigrate;
2293         myCallbacks.setStats = NULL;
2294         myCallbacks.queryEstLoad = NULL;
2295         myLBHandle = the_lbdb->RegisterOM(myId,this,myCallbacks);
2296
2297         // Tell the lbdb that I'm registering objects
2298         the_lbdb->RegisteringObjects(myLBHandle);
2299
2300         /*Set up the dummy barrier-- the load balancer needs
2301           us to call Registering/DoneRegistering during each AtSync,
2302           and this is the only way to do so.
2303         */
2304         the_lbdb->AddLocalBarrierReceiver(
2305                 (LDBarrierFn)staticRecvAtSync,(void*)(this));
2306         dummyBarrierHandle = the_lbdb->AddLocalBarrierClient(
2307                 (LDResumeFn)staticDummyResumeFromSync,(void*)(this));
2308         dummyAtSync();
2309 }
2310 void CkLocMgr::dummyAtSync(void)
2311 {
2312         DEBL((AA"dummyAtSync called\n"AB));
2313         the_lbdb->AtLocalBarrier(dummyBarrierHandle);
2314 }
2315
2316 void CkLocMgr::staticDummyResumeFromSync(void* data)
2317 {      ((CkLocMgr*)data)->dummyResumeFromSync(); }
2318 void CkLocMgr::dummyResumeFromSync()
2319 {
2320         DEBL((AA"DummyResumeFromSync called\n"AB));
2321         the_lbdb->DoneRegisteringObjects(myLBHandle);
2322         dummyAtSync();
2323 }
2324 void CkLocMgr::staticRecvAtSync(void* data)
2325 {      ((CkLocMgr*)data)->recvAtSync(); }
2326 void CkLocMgr::recvAtSync()
2327 {
2328         DEBL((AA"recvAtSync called\n"AB));
2329         the_lbdb->RegisteringObjects(myLBHandle);
2330 }
2331
2332 void CkLocMgr::startInserting(void)
2333 {
2334         the_lbdb->RegisteringObjects(myLBHandle);
2335 }
2336 void CkLocMgr::doneInserting(void)
2337 {
2338         the_lbdb->DoneRegisteringObjects(myLBHandle);
2339 }
2340 #endif
2341
2342 #include "CkLocation.def.h"
2343
2344