Changes for out-of-core emulation in BigSim. Details could be referred to Chao Mei...
[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 void CkMigratable::ckJustRestored(void) { }
676
677 CkMigratable::~CkMigratable() {
678         DEBC((AA"In CkMigratable::~CkMigratable %s\n"AB,idx2str(thisIndexMax)));
679 #if CMK_OUT_OF_CORE
680         isInCore=CmiFalse;
681         if (CkpvAccess(CkSaveRestorePrefetch)) 
682                 return; /* Just saving to disk--don't deregister anything. */
683         /* We're really leaving or dying-- unregister from the ooc system*/
684         if (prefetchObjID!=-1) {
685                 CooDeregisterObject(prefetchObjID);
686                 prefetchObjID=-1;
687         }
688 #endif
689         /*Might want to tell myRec about our doom here--
690         it's difficult to avoid some kind of circular-delete, though.
691         */
692 #if CMK_LBDB_ON 
693         if (barrierRegistered) {
694           DEBL((AA"Removing barrier for element %s\n"AB,idx2str(thisIndexMax)));
695           if (usesAtSync)
696                 myRec->getLBDB()->RemoveLocalBarrierClient(ldBarrierHandle);
697           else
698                 myRec->getLBDB()->RemoveLocalBarrierReceiver(ldBarrierRecvHandle);
699         }
700 #endif
701         //To detect use-after-delete
702         thisIndexMax.nInts=-123456;
703 }
704
705 void CkMigratable::CkAbort(const char *why) const {
706         CkError("CkMigratable '%s' aborting:\n",_chareTable[thisChareType]->name);
707         ::CkAbort(why);
708 }
709
710 void CkMigratable::ResumeFromSync(void)
711 {
712 //      CkAbort("::ResumeFromSync() not defined for this array element!\n");
713 }
714
715 void CkMigratable::UserSetLBLoad() {
716         CkAbort("::UserSetLBLoad() not defined for this array element!\n");
717 }
718
719 #if CMK_LBDB_ON  //For load balancing:
720 // user can call this helper function to set obj load (for model-based lb)
721 void CkMigratable::setObjTiming(double cputime) {
722         myRec->setObjTiming(cputime);
723 }
724
725 void CkMigratable::ckFinishConstruction(void)
726 {
727 //      if ((!usesAtSync) || barrierRegistered) return;
728         myRec->setMeasure(usesAutoMeasure);
729         if (barrierRegistered) return;
730         DEBL((AA"Registering barrier client for %s\n"AB,idx2str(thisIndexMax)));
731         if (usesAtSync)
732           ldBarrierHandle = myRec->getLBDB()->AddLocalBarrierClient(
733                 (LDBarrierFn)staticResumeFromSync,(void*)(this));
734         else
735           ldBarrierRecvHandle = myRec->getLBDB()->AddLocalBarrierReceiver(
736                 (LDBarrierFn)staticResumeFromSync,(void*)(this));
737         barrierRegistered=CmiTrue;
738 }
739 void CkMigratable::AtSync(int waitForMigration)
740 {
741         if (!usesAtSync)
742                 CkAbort("You must set usesAtSync=CmiTrue in your array element constructor to use AtSync!\n");
743         myRec->AsyncMigrate(!waitForMigration);
744         if (waitForMigration) ReadyMigrate(CmiTrue);
745         ckFinishConstruction();
746         DEBL((AA"Element %s going to sync\n"AB,idx2str(thisIndexMax)));
747           // model-based load balancing, ask user to provide cpu load
748         if (usesAutoMeasure == CmiFalse) UserSetLBLoad();
749         myRec->getLBDB()->AtLocalBarrier(ldBarrierHandle);
750 }
751 void CkMigratable::ReadyMigrate(CmiBool ready)
752 {
753         myRec->ReadyMigrate(ready);
754 }
755 void CkMigratable::staticResumeFromSync(void* data)
756 {
757         CkMigratable *el=(CkMigratable *)data;
758         DEBL((AA"Element %s resuming from sync\n"AB,idx2str(el->thisIndexMax)));
759         el->ResumeFromSync();
760 }
761 void CkMigratable::setMigratable(int migratable) 
762 {
763         myRec->setMigratable(migratable);
764 }
765
766 struct CkArrayThreadListener {
767         struct CthThreadListener base;
768         CkMigratable *mig;
769 };
770
771 extern "C"
772 void CkArrayThreadListener_suspend(struct CthThreadListener *l)
773 {
774         CkArrayThreadListener *a=(CkArrayThreadListener *)l;
775         a->mig->ckStopTiming();
776 }
777
778 extern "C"
779 void CkArrayThreadListener_resume(struct CthThreadListener *l)
780 {
781         CkArrayThreadListener *a=(CkArrayThreadListener *)l;
782         a->mig->ckStartTiming();
783 }
784
785 extern "C"
786 void CkArrayThreadListener_free(struct CthThreadListener *l)
787 {
788         CkArrayThreadListener *a=(CkArrayThreadListener *)l;
789         delete a;
790 }
791
792 void CkMigratable::CkAddThreadListeners(CthThread tid, void *msg)
793 {
794         Chare::CkAddThreadListeners(tid, msg);   // for trace
795         CthSetThreadID(tid, thisIndexMax.data()[0], thisIndexMax.data()[1], 
796                        thisIndexMax.data()[2]);
797         CkArrayThreadListener *a=new CkArrayThreadListener;
798         a->base.suspend=CkArrayThreadListener_suspend;
799         a->base.resume=CkArrayThreadListener_resume;
800         a->base.free=CkArrayThreadListener_free;
801         a->mig=this;
802         CthAddListener(tid,(struct CthThreadListener *)a);
803 }
804 #else
805 void CkMigratable::setObjTiming(double cputime) {}
806
807 /* no load balancer: need dummy implementations to prevent link error */
808 void CkMigratable::CkAddThreadListeners(CthThread tid, void *msg)
809 {
810 }
811 #endif
812
813
814 /*CkMigratableList*/
815 CkMigratableList::CkMigratableList() {}
816 CkMigratableList::~CkMigratableList() {}
817
818 void CkMigratableList::setSize(int s) {
819         el.resize(s);
820 }
821
822 void CkMigratableList::put(CkMigratable *v,int atIdx) {
823 #ifndef CMK_OPTIMIZE
824         if (atIdx>=length())
825                 CkAbort("Internal array manager error (CkMigrableList::put index out of bounds)");
826 #endif
827         el[atIdx]=v;
828 }
829
830
831 /************************** Location Records: *********************************/
832
833 //---------------- Base type:
834 void CkLocRec::weAreObsolete(const CkArrayIndex &idx) {}
835 CkLocRec::~CkLocRec() { }
836 void CkLocRec::beenReplaced(void)
837     {/*Default: ignore replacement*/}
838
839 //Return the represented array element; or NULL if there is none
840 CkMigratable *CkLocRec::lookupElement(CkArrayID aid) {return NULL;}
841
842 //Return the last known processor; or -1 if none
843 int CkLocRec::lookupProcessor(void) {return -1;}
844
845
846 /*----------------- Local:
847 Matches up the array index with the local index, an
848 interfaces with the load balancer on behalf of the
849 represented array elements.
850 */
851 CkLocRec_local::CkLocRec_local(CkLocMgr *mgr,CmiBool fromMigration,
852   CmiBool ignoreArrival, const CkArrayIndex &idx_,int localIdx_)
853         :CkLocRec(mgr),idx(idx_),localIdx(localIdx_),
854          running(CmiFalse),deletedMarker(NULL)
855 {
856 #if CMK_LBDB_ON
857         DEBL((AA"Registering element %s with load balancer\n"AB,idx2str(idx)));
858         //BIGSIM_OOC DEBUGGING
859         //CkPrintf("LocMgr on %d: Registering element %s with load balancer\n", CkMyPe(), idx2str(idx));
860         nextPe = -1;
861         asyncMigrate = CmiFalse;
862         readyMigrate = CmiTrue;
863         enable_measure = CmiTrue;
864         bounced  = CmiFalse;
865         the_lbdb=mgr->getLBDB();
866         ldHandle=the_lbdb->RegisterObj(mgr->getOMHandle(),
867                 idx2LDObjid(idx),(void *)this,1);
868         if (fromMigration) {
869                 DEBL((AA"Element %s migrated in\n"AB,idx2str(idx)));
870                 if (!ignoreArrival)  {
871                         the_lbdb->Migrated(ldHandle, CmiTrue);
872                   // load balancer should ignore this objects movement
873                 //  AsyncMigrate(CmiTrue);
874                 }
875         }
876 #endif
877         /*
878                 FAULT_EVAC
879         */
880         asyncEvacuate = CmiTrue;
881 }
882 CkLocRec_local::~CkLocRec_local()
883 {
884         if (deletedMarker!=NULL) *deletedMarker=CmiTrue;
885         myLocMgr->reclaim(idx,localIdx);
886 #if CMK_LBDB_ON
887         stopTiming();
888         DEBL((AA"Unregistering element %s from load balancer\n"AB,idx2str(idx)));
889         the_lbdb->UnregisterObj(ldHandle);
890 #endif
891 }
892 void CkLocRec_local::migrateMe(int toPe) //Leaving this processor
893 {
894         //This will pack us up, send us off, and delete us
895 //      printf("[%d] migrating migrateMe to %d \n",CkMyPe(),toPe);
896         myLocMgr->emigrate(this,toPe);
897 }
898
899 #if CMK_LBDB_ON
900 void CkLocRec_local::startTiming(void) {
901         running=CmiTrue;
902         DEBL((AA"Start timing for %s at %.3fs {\n"AB,idx2str(idx),CkWallTimer()));
903         if (enable_measure) the_lbdb->ObjectStart(ldHandle);
904 }
905 void CkLocRec_local::stopTiming(void) {
906         DEBL((AA"} Stop timing for %s at %.3fs\n"AB,idx2str(idx),CkWallTimer()));
907         if (running && enable_measure) the_lbdb->ObjectStop(ldHandle);
908         running=CmiFalse;
909 }
910 void CkLocRec_local::setObjTiming(double cputime) {
911         the_lbdb->EstObjLoad(ldHandle, cputime);
912 }
913 #endif
914
915 void CkLocRec_local::destroy(void) //User called destructor
916 {
917         //Our destructor does all the needed work
918         delete this;
919 }
920 //Return the represented array element; or NULL if there is none
921 CkMigratable *CkLocRec_local::lookupElement(CkArrayID aid) {
922         return myLocMgr->lookupLocal(localIdx,aid);
923 }
924
925 //Return the last known processor; or -1 if none
926 int CkLocRec_local::lookupProcessor(void) {
927         return CkMyPe();
928 }
929
930 CkLocRec::RecType CkLocRec_local::type(void)
931 {
932         return local;
933 }
934
935 void CkLocRec_local::addedElement(void) 
936 {
937         //Push everything in the half-created queue into the system--
938         // anything not ready yet will be put back in.
939         while (!halfCreated.isEmpty()) 
940                 CkArrayManagerDeliver(CkMyPe(),halfCreated.deq());
941 }
942
943 CmiBool CkLocRec_local::isObsolete(int nSprings,const CkArrayIndex &idx_)
944
945         int len=halfCreated.length();
946         if (len!=0) {
947                 /* This is suspicious-- the halfCreated queue should be extremely
948                  transient.  It's possible we just looked at the wrong time, though;
949                  so this is only a warning. 
950                 */
951                 CkPrintf("CkLoc WARNING> %d messages still around for uncreated element %s!\n",
952                          len,idx2str(idx));
953         }
954         //A local element never expires
955         return CmiFalse;
956 }
957
958 /**********Added for cosmology (inline function handling without parameter marshalling)***********/
959
960 LDObjHandle CkMigratable::timingBeforeCall(int* objstopped){
961
962         LDObjHandle objHandle;
963 #if CMK_LBDB_ON
964         if (getLBDB()->RunningObject(&objHandle)) {
965                 *objstopped = 1;
966                 getLBDB()->ObjectStop(objHandle);
967   }
968 #endif
969
970   //DEBS((AA"   Invoking entry %d on element %s\n"AB,epIdx,idx2str(idx)));
971         //CmiBool isDeleted=CmiFalse; //Enables us to detect deletion during processing
972         //deletedMarker=&isDeleted;
973         myRec->startTiming();
974 /*#ifndef CMK_OPTIMIZE
975         if (msg) {  Tracing: 
976                 envelope *env=UsrToEnv(msg);
977         //      CkPrintf("ckLocation.C beginExecuteDetailed %d %d \n",env->getEvent(),env->getsetArraySrcPe());
978                 if (_entryTable[epIdx]->traceEnabled)
979                         _TRACE_BEGIN_EXECUTE_DETAILED(env->getEvent(),
980                                  ForChareMsg,epIdx,env->getsetArraySrcPe(), env->getTotalsize(), idx.getProjectionID(((CkGroupID)env->getsetArrayMgr())).idx);
981         }
982 #endif*/
983
984   return objHandle;
985 }
986
987 void CkMigratable::timingAfterCall(LDObjHandle objHandle,int *objstopped){
988   
989 /*#ifndef CMK_OPTIMIZE
990         if (msg) {  Tracing: 
991                 if (_entryTable[epIdx]->traceEnabled)
992                         _TRACE_END_EXECUTE();
993         }
994 #endif*/
995 //#if CMK_LBDB_ON
996 //        if (!isDeleted) checkBufferedMigration();   // check if should migrate
997 //#endif
998 //      if (isDeleted) return CmiFalse;//We were deleted
999 //      deletedMarker=NULL;
1000         ckStopTiming();
1001 //      return CmiTrue;
1002 #if CMK_LBDB_ON
1003         if (*objstopped) getLBDB()->ObjectStart(objHandle);
1004 #endif
1005
1006  return;
1007 }
1008 /****************************************************************************/
1009
1010
1011 CmiBool CkLocRec_local::invokeEntry(CkMigratable *obj,void *msg,
1012         int epIdx,CmiBool doFree) 
1013 {
1014
1015         DEBS((AA"   Invoking entry %d on element %s\n"AB,epIdx,idx2str(idx)));
1016         CmiBool isDeleted=CmiFalse; //Enables us to detect deletion during processing
1017         deletedMarker=&isDeleted;
1018         startTiming();
1019
1020
1021 #ifndef CMK_OPTIMIZE
1022         if (msg) { /* Tracing: */
1023                 envelope *env=UsrToEnv(msg);
1024         //      CkPrintf("ckLocation.C beginExecuteDetailed %d %d \n",env->getEvent(),env->getsetArraySrcPe());
1025                 if (_entryTable[epIdx]->traceEnabled)
1026                         _TRACE_BEGIN_EXECUTE_DETAILED(env->getEvent(),
1027                                  ForChareMsg,epIdx,env->getsetArraySrcPe(), env->getTotalsize(), idx.getProjectionID((((CkGroupID)env->getsetArrayMgr())).idx));
1028         }
1029 #endif
1030
1031         if (doFree) 
1032            CkDeliverMessageFree(epIdx,msg,obj);
1033         else /* !doFree */
1034            CkDeliverMessageReadonly(epIdx,msg,obj);
1035
1036
1037 #ifndef CMK_OPTIMIZE
1038         if (msg) { /* Tracing: */
1039                 if (_entryTable[epIdx]->traceEnabled)
1040                         _TRACE_END_EXECUTE();
1041         }
1042 #endif
1043 #if CMK_LBDB_ON
1044         if (!isDeleted) checkBufferedMigration();   // check if should migrate
1045 #endif
1046         if (isDeleted) return CmiFalse;//We were deleted
1047         deletedMarker=NULL;
1048         stopTiming();
1049         return CmiTrue;
1050 }
1051
1052 CmiBool CkLocRec_local::deliver(CkArrayMessage *msg,CkDeliver_t type,int opts)
1053 {
1054
1055         if (type==CkDeliver_queue) { /*Send via the message queue */
1056                 if (opts & CK_MSG_KEEP)
1057                         msg = (CkArrayMessage *)CkCopyMsg((void **)&msg);
1058                 CkArrayManagerDeliver(CkMyPe(),msg,opts);
1059                 return CmiTrue;
1060         }
1061         else
1062         {
1063                 CkMigratable *obj=myLocMgr->lookupLocal(localIdx,
1064                         UsrToEnv(msg)->getsetArrayMgr());
1065                 if (obj==NULL) {//That sibling of this object isn't created yet!
1066                         if (opts & CK_MSG_KEEP)
1067                                 msg = (CkArrayMessage *)CkCopyMsg((void **)&msg);
1068                         if (msg->array_ifNotThere()!=CkArray_IfNotThere_buffer) {
1069                                 return myLocMgr->demandCreateElement(msg,CkMyPe(),type);
1070                         }
1071                         else {
1072                                 DEBS((AA"   BUFFERING message for nonexistent element %s!\n"AB,idx2str(this->idx)));
1073                                 halfCreated.enq(msg);
1074                                 return CmiTrue;
1075                         }
1076                 }
1077                         
1078                 if (msg->array_hops()>1)
1079                         myLocMgr->multiHop(msg);
1080                 CmiBool doFree = (CmiBool)!(opts & CK_MSG_KEEP);
1081 #if CMK_LBDB_ON
1082                 // if there is a running obj being measured, stop it temporarily
1083                 LDObjHandle objHandle;
1084                 int objstopped = 0;
1085                 if (the_lbdb->RunningObject(&objHandle)) {
1086                         objstopped = 1;
1087                         the_lbdb->ObjectStop(objHandle);
1088                 }
1089 #endif
1090 #if CMK_GRID_QUEUE_AVAILABLE
1091                 // retain a pointer to the sending object (needed later)
1092                 CpvAccess(CkGridObject) = obj;
1093 #endif
1094
1095         CmiBool status = invokeEntry(obj,(void *)msg,msg->array_ep(),doFree);
1096         
1097 #if CMK_GRID_QUEUE_AVAILABLE
1098                 CpvAccess(CkGridObject) = NULL;
1099 #endif
1100 #if CMK_LBDB_ON
1101                 if (objstopped) the_lbdb->ObjectStart(objHandle);
1102 #endif
1103                 return status;
1104         }
1105
1106
1107 }
1108
1109 #if CMK_LBDB_ON
1110 void CkLocRec_local::staticMigrate(LDObjHandle h, int dest)
1111 {
1112         CkLocRec_local *el=(CkLocRec_local *)LDObjUserData(h);
1113         DEBL((AA"Load balancer wants to migrate %s to %d\n"AB,idx2str(el->idx),dest));
1114         el->recvMigrate(dest);
1115 }
1116
1117 void CkLocRec_local::recvMigrate(int toPe)
1118 {
1119         // we are in the mode of delaying actual migration
1120         // till readyMigrate()
1121         if (readyMigrate) { migrateMe(toPe); }
1122         else nextPe = toPe;
1123 }
1124
1125 void CkLocRec_local::AsyncMigrate(CmiBool use)  
1126 {
1127         asyncMigrate = use; 
1128         the_lbdb->UseAsyncMigrate(ldHandle, use);
1129 }
1130
1131 CmiBool CkLocRec_local::checkBufferedMigration()
1132 {
1133         // we don't migrate in user's code when calling ReadyMigrate(true)
1134         // we postphone the action to here until we exit from the user code.
1135         if (readyMigrate && nextPe != -1) {
1136             int toPe = nextPe;
1137             nextPe = -1;
1138             // don't migrate inside the object call
1139             migrateMe(toPe);
1140             // don't do anything
1141             return CmiTrue;
1142         }
1143         return CmiFalse;
1144 }
1145
1146 int CkLocRec_local::MigrateToPe()
1147 {
1148         int pe = nextPe;
1149         nextPe = -1;
1150         return pe;
1151 }
1152
1153 void CkLocRec_local::setMigratable(int migratable)
1154 {
1155         if (migratable)
1156           the_lbdb->Migratable(ldHandle);
1157         else
1158           the_lbdb->NonMigratable(ldHandle);
1159 }
1160 #endif
1161
1162 /**
1163  * Represents a deleted array element (and prevents re-use).
1164  * These are a debugging aid, usable only by uncommenting a line in
1165  * the element destruction code.
1166  */
1167 class CkLocRec_dead:public CkLocRec {
1168 public:
1169         CkLocRec_dead(CkLocMgr *Narr):CkLocRec(Narr) {}
1170   
1171         virtual RecType type(void) {return dead;}
1172   
1173         virtual CmiBool deliver(CkArrayMessage *msg,CkDeliver_t type,int opts=0) {
1174                 CkPrintf("Dead array element is %s.\n",idx2str(msg->array_index()));
1175                 CkAbort("Send to dead array element!\n");
1176                 return CmiFalse;
1177         }
1178         virtual void beenReplaced(void) 
1179                 {CkAbort("Can't re-use dead array element!\n");}
1180   
1181         //Return if this element is now obsolete (it isn't)
1182         virtual CmiBool isObsolete(int nSprings,const CkArrayIndex &idx) {return CmiFalse;}     
1183 };
1184
1185 /**
1186  * This is the abstract superclass of arrayRecs that keep track of their age,
1187  * and eventually expire. Its kids are remote and buffering.
1188  */
1189 class CkLocRec_aging:public CkLocRec {
1190 private:
1191         int lastAccess;//Age when last accessed
1192 protected:
1193         //Update our access time
1194         inline void access(void) {
1195                 lastAccess=myLocMgr->getSpringCount();
1196         }
1197         //Return if we are "stale"-- we were last accessed a while ago
1198         CmiBool isStale(void) {
1199                 if (myLocMgr->getSpringCount()-lastAccess>3) return CmiTrue;
1200                 else return CmiFalse;
1201         }
1202 public:
1203         CkLocRec_aging(CkLocMgr *Narr):CkLocRec(Narr) {
1204                 lastAccess=myLocMgr->getSpringCount();
1205         }
1206         //Return if this element is now obsolete
1207         virtual CmiBool isObsolete(int nSprings,const CkArrayIndex &idx)=0;
1208         //virtual void pup(PUP::er &p) { CkLocRec::pup(p); p(lastAccess); }
1209 };
1210
1211
1212 /**
1213  * Represents a remote array element.  This is just a PE number.
1214  */
1215 class CkLocRec_remote:public CkLocRec_aging {
1216 private:
1217         int onPe;//The last known Pe for this element
1218 public:
1219         CkLocRec_remote(CkLocMgr *Narr,int NonPe)
1220                 :CkLocRec_aging(Narr)
1221                 {
1222                         onPe=NonPe;
1223 #ifndef CMK_OPTIMIZE
1224                         if (onPe==CkMyPe())
1225                                 CkAbort("ERROR!  'remote' array element on this Pe!\n");
1226 #endif
1227                 }
1228         //Return the last known processor for this element
1229         int lookupProcessor(void) {
1230                 return onPe;
1231         }  
1232         virtual RecType type(void) {return remote;}
1233   
1234         //Send a message for this element.
1235         virtual CmiBool deliver(CkArrayMessage *msg,CkDeliver_t type,int opts=0) {
1236                 /*FAULT_EVAC*/
1237                 int destPE = onPe;
1238                 if((!CmiNodeAlive(onPe) && onPe != allowMessagesOnly)){
1239 //                      printf("Delivery failed because process %d is invalid\n",onPe);
1240                         /*
1241                                 Send it to its home processor instead
1242                         */
1243                         const CkArrayIndex &idx=msg->array_index();
1244                         destPE = getNextPE(idx);
1245                 }
1246                 access();//Update our modification date
1247                 msg->array_hops()++;
1248                 DEBS((AA"   Forwarding message for element %s to %d (REMOTE)\n"AB,
1249                       idx2str(msg->array_index()),destPE));
1250                 if (opts & CK_MSG_KEEP)
1251                         msg = (CkArrayMessage *)CkCopyMsg((void **)&msg);
1252                 CkArrayManagerDeliver(destPE,msg,opts);
1253                 return CmiTrue;
1254         }
1255         //Return if this element is now obsolete
1256         virtual CmiBool isObsolete(int nSprings,const CkArrayIndex &idx) {
1257                 if (myLocMgr->isHome(idx)) 
1258                         //Home elements never become obsolete
1259                         // if they did, we couldn't deliver messages to that element.
1260                         return CmiFalse;
1261                 else if (isStale())
1262                         return CmiTrue;//We haven't been used in a long time
1263                 else
1264                         return CmiFalse;//We're fairly recent
1265         }
1266         //virtual void pup(PUP::er &p) { CkLocRec_aging::pup(p); p(onPe); }
1267 };
1268
1269
1270 /**
1271  * Buffers messages until record is replaced in the hash table, 
1272  * then delivers all messages to the replacing record.  This is 
1273  * used when a message arrives for a local element that has not
1274  * yet been created, buffering messages until the new element finally
1275  * checks in.
1276  *
1277  * It's silly to send a message to an element you won't ever create,
1278  * so this kind of record causes an abort "Stale array manager message!"
1279  * if it's left undelivered too long.
1280  */
1281 class CkLocRec_buffering:public CkLocRec_aging {
1282 private:
1283         CkQ<CkArrayMessage *> buffer;//Buffered messages.
1284 public:
1285         CkLocRec_buffering(CkLocMgr *Narr):CkLocRec_aging(Narr) {}
1286         virtual ~CkLocRec_buffering() {
1287                 if (0!=buffer.length())
1288                         CkPrintf("[%d] Warning: Messages abandoned in array manager buffer!\n", CkMyPe());
1289         }
1290   
1291         virtual RecType type(void) {return buffering;}
1292   
1293         //Buffer a message for this element.
1294         virtual CmiBool deliver(CkArrayMessage *msg,CkDeliver_t type,int opts=0) {
1295                 DEBS((AA" Queued message for %s\n"AB,idx2str(msg->array_index())));
1296                 if (opts & CK_MSG_KEEP)
1297                         msg = (CkArrayMessage *)CkCopyMsg((void **)&msg);
1298                 buffer.enq(msg);
1299                 return CmiTrue;
1300         }
1301  
1302         //This is called when this ArrayRec is about to be replaced.
1303         // We dump all our buffered messages off on the next guy,
1304         // who should know what to do with them.
1305         virtual void beenReplaced(void) {
1306                 DEBS((AA" Delivering queued messages:\n"AB));
1307                 CkArrayMessage *m;
1308                 while (NULL!=(m=buffer.deq())) {
1309                         DEBS((AA"Sending buffered message to %s\n"AB,idx2str(m->array_index())));
1310                         myLocMgr->deliverViaQueue(m);
1311                 }
1312         }
1313   
1314         //Return if this element is now obsolete
1315         virtual CmiBool isObsolete(int nSprings,const CkArrayIndex &idx) {
1316                 if (isStale()) {
1317                         /*This indicates something is seriously wrong--
1318                           buffers should be short-lived.*/
1319                         CkPrintf("WARNING: %d stale array message(s) found!\n",buffer.length());
1320                         CkArrayMessage *msg=buffer.deq();
1321                         CkPrintf("Addressed to: ");
1322                         CkPrintEntryMethod(msg->array_ep());
1323                         CkPrintf(" index %s\n",idx2str(idx));
1324                         if (myLocMgr->isHome(idx)) 
1325                                 CkPrintf("is this an out-of-bounds array index, or was it never created?\n");
1326                         else //Idx is a remote-home index
1327                                 CkPrintf("why weren't they forwarded?\n");
1328                         
1329                         // CkAbort("Stale array manager message(s)!\n");
1330                 }
1331                 return CmiFalse;
1332         }
1333   
1334 /*  virtual void pup(PUP::er &p) {
1335     CkLocRec_aging::pup(p);
1336     CkArray::pupArrayMsgQ(buffer, p);
1337     }*/
1338 };
1339
1340 /*********************** Spring Cleaning *****************/
1341 /**
1342  * Used to periodically flush out unused remote element pointers.
1343  *
1344  * Cleaning often will free up memory quickly, but slow things
1345  * down because the cleaning takes time and some not-recently-referenced
1346  * remote element pointers might be valid and used some time in 
1347  * the future.
1348  *
1349  * Also used to determine if buffered messages have become stale.
1350  */
1351 inline void CkLocMgr::springCleaning(void)
1352 {
1353   nSprings++;
1354
1355   //Poke through the hash table for old ArrayRecs.
1356   void *objp;
1357   void *keyp;
1358   
1359   CkHashtableIterator *it=hash.iterator();
1360   CmiImmediateLock(hashImmLock);
1361   while (NULL!=(objp=it->next(&keyp))) {
1362     CkLocRec *rec=*(CkLocRec **)objp;
1363     CkArrayIndex &idx=*(CkArrayIndex *)keyp;
1364     if (rec->isObsolete(nSprings,idx)) {
1365       //This record is obsolete-- remove it from the table
1366       DEBK((AA"Cleaning out old record %s\n"AB,idx2str(idx)));
1367       hash.remove(*(CkArrayIndexMax *)&idx);
1368       delete rec;
1369       it->seek(-1);//retry this hash slot
1370     }
1371   }
1372   CmiImmediateUnlock(hashImmLock);
1373   delete it;
1374 }
1375 void CkLocMgr::staticSpringCleaning(void *forWhom,double curWallTime) {
1376         DEBK((AA"Starting spring cleaning at %.2f\n"AB,CkWallTimer()));
1377         ((CkLocMgr *)forWhom)->springCleaning();
1378 }
1379
1380 // clean all buffer'ed messages and also free local objects
1381 void CkLocMgr::flushAllRecs(void)
1382 {
1383   void *objp;
1384   void *keyp;
1385     
1386   CkHashtableIterator *it=hash.iterator();
1387   CmiImmediateLock(hashImmLock);
1388   while (NULL!=(objp=it->next(&keyp))) {
1389     CkLocRec *rec=*(CkLocRec **)objp;
1390     CkArrayIndex &idx=*(CkArrayIndex *)keyp;
1391     if (rec->type() != CkLocRec::local) {
1392       //In the case of taking core out of memory (in BigSim's emulation)
1393       //the meta data in the location manager are not deleted so we need
1394       //this condition
1395       if(BgOutOfCoreFlag!=1){
1396         hash.remove(*(CkArrayIndexMax *)&idx);
1397         delete rec;
1398         it->seek(-1);//retry this hash slot
1399       }
1400     }
1401     else {
1402         callMethod((CkLocRec_local*)rec, &CkMigratable::ckDestroy);
1403         it->seek(-1);//retry this hash slot
1404     }
1405   }
1406   delete it;
1407   CmiImmediateUnlock(hashImmLock);
1408 }
1409
1410 /*************************** LocMgr: CREATION *****************************/
1411 CkLocMgr::CkLocMgr(CkGroupID mapID_,CkGroupID lbdbID_,CkArrayIndexMax& numInitial)
1412         :thisProxy(thisgroup),thislocalproxy(thisgroup,CkMyPe()),
1413          hash(17,0.3)
1414 {
1415         DEBC((AA"Creating new location manager %d\n"AB,thisgroup));
1416 // moved to _CkMigratable_initInfoInit()
1417 //      CkpvInitialize(CkMigratable_initInfo,mig_initInfo);
1418
1419         managers.init();
1420         nManagers=0;
1421         firstManager=NULL;
1422         firstFree=localLen=0;
1423         duringMigration=CmiFalse;
1424         nSprings=0;
1425         CcdCallOnConditionKeepOnPE(CcdPERIODIC_1minute,staticSpringCleaning,(void *)this, CkMyPe());
1426
1427 //Register with the map object
1428         mapID=mapID_;
1429         map=(CkArrayMap *)CkLocalBranch(mapID);
1430         if (map==NULL) CkAbort("ERROR!  Local branch of array map is NULL!");
1431         mapHandle=map->registerArray(numInitial,thisgroup);
1432
1433 //Find and register with the load balancer
1434         lbdbID = lbdbID_;
1435         initLB(lbdbID_);
1436         hashImmLock = CmiCreateImmediateLock();
1437 }
1438
1439 CkLocMgr::CkLocMgr(CkMigrateMessage* m)
1440         :IrrGroup(m),thisProxy(thisgroup),thislocalproxy(thisgroup,CkMyPe()),hash(17,0.3)
1441 {
1442         managers.init();
1443         nManagers=0;
1444         firstManager=NULL;
1445         firstFree=localLen=0;
1446         duringMigration=CmiFalse;
1447         nSprings=0;
1448         CcdCallOnConditionKeepOnPE(CcdPERIODIC_1minute,staticSpringCleaning,(void *)this, CkMyPe());
1449         hashImmLock = CmiCreateImmediateLock();
1450 }
1451
1452 void CkLocMgr::pup(PUP::er &p){
1453         IrrGroup::pup(p);
1454         p|mapID;
1455         p|lbdbID;
1456         mapID = _RRMapID;
1457         if(p.isUnpacking()){
1458                 thisProxy=thisgroup;
1459                 CProxyElement_CkLocMgr newlocalproxy(thisgroup,CkMyPe());
1460                 thislocalproxy=newlocalproxy;
1461                 //Register with the map object
1462                 map=(CkArrayMap *)CkLocalBranch(mapID);
1463                 if (map==NULL) CkAbort("ERROR!  Local branch of array map is NULL!");
1464                 CkArrayIndexMax emptyIndex;
1465                 mapHandle=map->registerArray(emptyIndex,thisgroup);
1466                 // _lbdb is the fixed global groupID
1467                 initLB(lbdbID);
1468                 // delay doneInserting when it is unpacking during restart.
1469                 // to prevent load balancing kicking in
1470                 if (!CkInRestarting()) 
1471                         doneInserting();
1472         }
1473 }
1474
1475 void _CkLocMgrInit(void) {
1476   /* Don't trace our deliver method--it does its own tracing */
1477   CkDisableTracing(CkIndex_CkLocMgr::deliverInline(0));
1478 }
1479
1480 /// Add a new local array manager to our list.
1481 /// Returns a new CkMigratableList for the manager to store his
1482 /// elements in.
1483 CkMigratableList *CkLocMgr::addManager(CkArrayID id,CkArrMgr *mgr)
1484 {
1485         CK_MAGICNUMBER_CHECK
1486         DEBC((AA"Adding new array manager\n"AB));
1487         //Link new manager into list
1488         ManagerRec *n=new ManagerRec;
1489         managers.find(id)=n;
1490         n->next=firstManager;
1491         n->mgr=mgr;
1492         n->elts.setSize(localLen);
1493         nManagers++;
1494         firstManager=n;
1495         return &n->elts;
1496 }
1497
1498 /// Return the next unused local element index.
1499 int CkLocMgr::nextFree(void) {
1500         if (firstFree>=localLen)
1501         {//Need more space in the local index arrays-- enlarge them
1502                 int oldLen=localLen;
1503                 localLen=localLen*2+8;
1504                 DEBC((AA"Growing the local list from %d to %d...\n"AB,oldLen,localLen));
1505                 for (ManagerRec *m=firstManager;m!=NULL;m=m->next)
1506                         m->elts.setSize(localLen);
1507                 //Update the free list
1508                 freeList.resize(localLen);
1509                 for (int i=oldLen;i<localLen;i++)
1510                         freeList[i]=i+1;
1511         }
1512         int localIdx=firstFree;
1513         if (localIdx==-1) CkAbort("CkLocMgr free list corrupted!");
1514         firstFree=freeList[localIdx];
1515         freeList[localIdx]=-1; //Mark as used
1516         return localIdx;
1517 }
1518
1519 CkLocRec_remote *CkLocMgr::insertRemote(const CkArrayIndex &idx,int nowOnPe)
1520 {
1521         DEBS((AA"Remote element %s lives on %d\n"AB,idx2str(idx),nowOnPe));
1522         CkLocRec_remote *rem=new CkLocRec_remote(this,nowOnPe);
1523         insertRec(rem,idx);
1524         return rem;
1525 }
1526
1527 //This element now lives on the given Pe
1528 void CkLocMgr::inform(const CkArrayIndex &idx,int nowOnPe)
1529 {
1530         if (nowOnPe==CkMyPe())
1531                 return; //Never insert a "remote" record pointing here
1532         CkLocRec *rec=elementNrec(idx);
1533         if (rec!=NULL && rec->type()==CkLocRec::local)
1534                 return; //Never replace a local element's record!
1535         insertRemote(idx,nowOnPe);
1536 }
1537
1538 //Tell this element's home processor it now lives "there"
1539 void CkLocMgr::informHome(const CkArrayIndex &idx,int nowOnPe)
1540 {
1541         int home=homePe(idx);
1542         if (home!=CkMyPe() && home!=nowOnPe) {
1543                 //Let this element's home Pe know it lives here now
1544                 DEBC((AA"  Telling %s's home %d that it lives on %d.\n"AB,idx2str(idx),home,nowOnPe));
1545                 thisProxy[home].updateLocation(idx,nowOnPe);
1546         }
1547 }
1548
1549 CkLocRec_local *CkLocMgr::createLocal(const CkArrayIndex &idx, 
1550                 CmiBool forMigration, CmiBool ignoreArrival,
1551                 CmiBool notifyHome)
1552 {
1553         int localIdx=nextFree();
1554         DEBC((AA"Adding new record for element %s at local index %d\n"AB,idx2str(idx),localIdx));
1555         CkLocRec_local *rec=new CkLocRec_local(this,forMigration,ignoreArrival,idx,localIdx);
1556         insertRec(rec,idx); //Add to global hashtable
1557
1558
1559         if (notifyHome) informHome(idx,CkMyPe());
1560         return rec;
1561 }
1562
1563 //Add a new local array element, calling element's constructor
1564 CmiBool CkLocMgr::addElement(CkArrayID id,const CkArrayIndex &idx,
1565                 CkMigratable *elt,int ctorIdx,void *ctorMsg)
1566 {
1567         CK_MAGICNUMBER_CHECK
1568         CkLocRec *oldRec=elementNrec(idx);
1569         CkLocRec_local *rec;
1570         if (oldRec==NULL||oldRec->type()!=CkLocRec::local) 
1571         { //This is the first we've heard of that element-- add new local record
1572                 rec=createLocal(idx,CmiFalse,CmiFalse,CmiTrue);
1573         } else 
1574         { //rec is *already* local-- must not be the first insertion    
1575                 rec=((CkLocRec_local *)oldRec);
1576                 rec->addedElement();
1577         }
1578         if (!addElementToRec(rec,managers.find(id),elt,ctorIdx,ctorMsg)) return CmiFalse;
1579         elt->ckFinishConstruction();
1580         return CmiTrue;
1581 }
1582
1583 //As above, but shared with the migration code
1584 CmiBool CkLocMgr::addElementToRec(CkLocRec_local *rec,ManagerRec *m,
1585                 CkMigratable *elt,int ctorIdx,void *ctorMsg)
1586 {//Insert the new element into its manager's local list
1587         int localIdx=rec->getLocalIndex();
1588         if (m->elts.get(localIdx)!=NULL) CkAbort("Cannot insert array element twice!");
1589         m->elts.put(elt,localIdx); //Local element table
1590
1591 //Call the element's constructor
1592         DEBC((AA"Constructing element %s of array\n"AB,idx2str(rec->getIndex())));
1593         CkMigratable_initInfo &i=CkpvAccess(mig_initInfo);
1594         i.locRec=rec;
1595         i.chareType=_entryTable[ctorIdx]->chareIdx;
1596         if (!rec->invokeEntry(elt,ctorMsg,ctorIdx,CmiTrue)) return CmiFalse;
1597
1598 #if CMK_OUT_OF_CORE
1599         /* Register new element with out-of-core */
1600         PUP::sizer p_getSize; elt->pup(p_getSize);
1601         elt->prefetchObjID=CooRegisterObject(&CkArrayElementPrefetcher,p_getSize.size(),elt);
1602 #endif
1603         
1604         return CmiTrue;
1605 }
1606 void CkLocMgr::updateLocation(const CkArrayIndexMax &idx,int nowOnPe) {
1607         inform(idx,nowOnPe);
1608 }
1609
1610 /*************************** LocMgr: DELETION *****************************/
1611 /// This index will no longer be used-- delete the associated elements
1612 void CkLocMgr::reclaim(const CkArrayIndex &idx,int localIdx) {
1613         CK_MAGICNUMBER_CHECK
1614         DEBC((AA"Destroying element %s (local %d)\n"AB,idx2str(idx),localIdx));
1615         //Delete, and mark as empty, each array element
1616         for (ManagerRec *m=firstManager;m!=NULL;m=m->next) {
1617                 delete m->elts.get(localIdx);
1618                 m->elts.empty(localIdx);
1619         }
1620         
1621         removeFromTable(idx);
1622         
1623         //Link local index into free list
1624         freeList[localIdx]=firstFree;
1625         firstFree=localIdx;
1626         
1627                 
1628         if (!duringMigration) 
1629         { //This is a local element dying a natural death
1630             #if CMK_BLUEGENE_CHARM
1631                 //After migration, reclaimRemote will be called through 
1632                 //the CkRemoveArrayElement in the pupping routines for those 
1633                 //objects that are not on the home processors. However,
1634                 //those remote records should not be deleted since the corresponding
1635                 //objects are not actually deleted but on disk. If deleted, msgs
1636                 //that seeking where is the object will be accumulated (a circular
1637                 //msg chain) and causes the program no progress
1638                 if(BgOutOfCoreFlag==1) return; 
1639             #endif
1640                 int home=homePe(idx);
1641                 if (home!=CkMyPe())
1642                         thisProxy[home].reclaimRemote(idx,CkMyPe());
1643         /*      //Install a zombie to keep the living from re-using this index.
1644                 insertRecN(new CkLocRec_dead(this),idx); */
1645         }
1646 }
1647
1648 void CkLocMgr::reclaimRemote(const CkArrayIndexMax &idx,int deletedOnPe) {
1649         DEBC((AA"Our element %s died on PE %d\n"AB,idx2str(idx),deletedOnPe));
1650         CkLocRec *rec=elementNrec(idx);
1651         if (rec==NULL) return; //We never knew him
1652         if (rec->type()==CkLocRec::local) return; //He's already been reborn
1653         removeFromTable(idx);
1654         delete rec;
1655 }
1656 void CkLocMgr::removeFromTable(const CkArrayIndex &idx) {
1657 #ifndef CMK_OPTIMIZE
1658         //Make sure it's actually in the table before we delete it
1659         if (NULL==elementNrec(idx))
1660                 CkAbort("CkLocMgr::removeFromTable called on invalid index!");
1661 #endif
1662         CmiImmediateLock(hashImmLock);
1663         hash.remove(*(CkArrayIndexMax *)&idx);
1664         CmiImmediateUnlock(hashImmLock);
1665 #ifndef CMK_OPTIMIZE
1666         //Make sure it's really gone
1667         if (NULL!=elementNrec(idx))
1668                 CkAbort("CkLocMgr::removeFromTable called, but element still there!");
1669 #endif
1670 }
1671
1672 /************************** LocMgr: MESSAGING *************************/
1673 /// Deliver message to this element, going via the scheduler if local
1674 void CkLocMgr::deliver(CkMessage *m,CkDeliver_t type,int opts) {
1675         DEBS((AA"deliver \n"AB));
1676         CK_MAGICNUMBER_CHECK
1677         CkArrayMessage *msg=(CkArrayMessage *)m;
1678
1679
1680         const CkArrayIndex &idx=msg->array_index();
1681         DEBS((AA"deliver %s\n"AB,idx2str(idx)));
1682         if (type==CkDeliver_queue)
1683                 _TRACE_CREATION_DETAILED(UsrToEnv(m),msg->array_ep());
1684         CkLocRec *rec=elementNrec(idx);
1685         if(rec != NULL){
1686                 DEBS((AA"deliver %s of type %d \n"AB,idx2str(idx),rec->type()));
1687         }else{
1688                 DEBS((AA"deliver %s rec is null\n"AB,idx2str(idx)));
1689         }
1690 #if CMK_LBDB_ON
1691         if (type==CkDeliver_queue) {
1692                 if (!(opts & CK_MSG_LB_NOTRACE)) {
1693                 if(rec!=NULL) the_lbdb->Send(myLBHandle,idx2LDObjid(idx),UsrToEnv(msg)->getTotalsize(), rec->lookupProcessor());
1694                 else /*rec==NULL*/ the_lbdb->Send(myLBHandle,idx2LDObjid(idx),UsrToEnv(msg)->getTotalsize(),homePe(msg->array_index()));
1695                 }
1696         }
1697 #endif
1698 #if CMK_GRID_QUEUE_AVAILABLE
1699         int gridSrcPE;
1700         int gridSrcCluster;
1701         int gridDestPE;
1702         int gridDestCluster;
1703         CkMigratable *obj;
1704         ArrayElement *obj2;
1705         CkGroupID gid;
1706         int *data;
1707
1708         obj = (CkMigratable *) CpvAccess(CkGridObject);   // CkGridObject is a pointer to the sending object (retained earlier)
1709         if (obj != NULL) {
1710           obj2 = dynamic_cast<ArrayElement *> (obj);
1711           if (obj2 > 0) {
1712             // Get the sending object's array gid and indexes.
1713             // These are guaranteed to exist due to the succeeding dynamic cast above.
1714             gid = obj2->ckGetArrayID ();
1715             data = obj2->thisIndexMax.data ();
1716
1717             // Get the source PE and destination PE.
1718             gridSrcPE = CkMyPe ();
1719             if (rec != NULL) {
1720               gridDestPE = rec->lookupProcessor ();
1721             } else {
1722               gridDestPE = homePe (msg->array_index ());
1723             }
1724
1725             // Get the source cluster and destination cluster.
1726             gridSrcCluster = CmiGetCluster (gridSrcPE);
1727             gridDestCluster = CmiGetCluster (gridDestPE);
1728
1729             // If the Grid queue interval is greater than zero, it means that the more complicated
1730             // technique for registering border objects that exceed a specified threshold of
1731             // cross-cluster messages within a specified interval (and deregistering border objects
1732             // that do not meet this threshold) is used.  Otherwise a much simpler technique is used
1733             // where a border object is registered immediately upon sending a single cross-cluster
1734             // message (and deregistered when load balancing takes place).
1735             if (obj2->grid_queue_interval > 0) {
1736               // Increment the sending object's count of all messages.
1737               obj2->msg_count += 1;
1738
1739               // If the source cluster and destination cluster differ, this is a Grid message.
1740               // (Increment the count of all Grid messages.)
1741               if (gridSrcCluster != gridDestCluster) {
1742                 obj2->msg_count_grid += 1;
1743               }
1744
1745               // If the number of messages exceeds the interval, check to see if the object has
1746               // sent enough cross-cluster messages to qualify as a border object.
1747               if (obj2->msg_count >= obj2->grid_queue_interval) {
1748                 if (obj2->msg_count_grid >= obj2->grid_queue_threshold) {
1749                   // The object is a border object; if it is not already registered, register it.
1750                   if (!obj2->border_flag) {
1751                     CmiGridQueueRegister (gid.idx, obj2->thisIndexMax.nInts, data[0], data[1], data[2]);
1752                   }
1753                   obj2->border_flag = 1;
1754                 } else {
1755                   // The object is not a border object; if it is registered, deregister it.
1756                   if (obj2->border_flag) {
1757                     CmiGridQueueDeregister (gid.idx, obj2->thisIndexMax.nInts, data[0], data[1], data[2]);
1758                   }
1759                   obj2->border_flag = 0;
1760                 }
1761                 // Reset the counts.
1762                 obj2->msg_count = 0;
1763                 obj2->msg_count_grid = 0;
1764               }
1765             } else {
1766               if (gridSrcCluster != gridDestCluster) {
1767                 CmiGridQueueRegister (gid.idx, obj2->thisIndexMax.nInts, data[0], data[1], data[2]);
1768               }
1769             }
1770           }
1771
1772           // Reset the CkGridObject pointer.
1773           CpvAccess(CkGridObject) = NULL;
1774         }
1775 #endif
1776         /**FAULT_EVAC*/
1777         if (rec!=NULL){
1778                 CmiBool result = rec->deliver(msg,type,opts);
1779                 if(!result){
1780                 /*      //DEBS((AA"deliver %s failed type %d \n"AB,idx2str(idx),rec->type()));
1781                         DEBS((AA"deliver %s failed \n"AB,idx2str(idx)));
1782                         if(rec->type() == CkLocRec::remote){
1783                                 if (opts & CK_MSG_KEEP)
1784                                         msg = (CkArrayMessage *)CkCopyMsg((void **)&msg);
1785                                 deliverUnknown(msg,type);
1786                         }*/
1787                 }
1788         }else /* rec==NULL*/ {
1789                 if (opts & CK_MSG_KEEP)
1790                         msg = (CkArrayMessage *)CkCopyMsg((void **)&msg);
1791                 deliverUnknown(msg,type,opts);
1792         }
1793
1794 }
1795
1796 /// This index is not hashed-- somehow figure out what to do.
1797 CmiBool CkLocMgr::deliverUnknown(CkArrayMessage *msg,CkDeliver_t type,int opts)
1798 {
1799         CK_MAGICNUMBER_CHECK
1800         const CkArrayIndex &idx=msg->array_index();
1801         int onPe=homePe(idx);
1802         if (onPe!=CkMyPe()) 
1803         {// Forward the message to its home processor
1804                 DEBM((AA"Forwarding message for unknown %s to home %d \n"AB,idx2str(idx),onPe));
1805                 msg->array_hops()++;
1806                 CkArrayManagerDeliver(onPe,msg,opts);
1807                 return CmiTrue;
1808         }
1809         else
1810         { // We *are* the home processor:
1811         //Check if the element's array manager has been registered yet:
1812           CkArrMgr *mgr=managers.find(UsrToEnv((void *)msg)->getsetArrayMgr())->mgr;
1813           if (!mgr) { //No manager yet-- postpone the message (stupidly)
1814             if (CkInRestarting()) {
1815               // during restarting, this message should be ignored
1816               delete msg;
1817             }
1818             else {
1819               CkArrayManagerDeliver(CkMyPe(),msg); 
1820             }
1821           }
1822           else { // Has a manager-- must buffer the message
1823             DEBC((AA"Adding buffer for unknown element %s\n"AB,idx2str(idx)));
1824             CkLocRec *rec=new CkLocRec_buffering(this);
1825             insertRecN(rec,idx);
1826             rec->deliver(msg,type);
1827           
1828             if (msg->array_ifNotThere()!=CkArray_IfNotThere_buffer) 
1829             { //Demand-create the element:
1830               return demandCreateElement(msg,-1,type);
1831             }
1832           }
1833           return CmiTrue;
1834         }
1835 }
1836
1837 CmiBool CkLocMgr::demandCreateElement(CkArrayMessage *msg,int onPe,CkDeliver_t type)
1838 {
1839         CK_MAGICNUMBER_CHECK
1840         const CkArrayIndex &idx=msg->array_index();
1841         int chareType=_entryTable[msg->array_ep()]->chareIdx;
1842         int ctor=_chareTable[chareType]->getDefaultCtor();
1843         if (ctor==-1) CkAbort("Can't create array element to handle message--\n"
1844                               "The element has no default constructor in the .ci file!\n");
1845         if (onPe==-1) 
1846         { //Decide where element needs to live
1847                 if (msg->array_ifNotThere()==CkArray_IfNotThere_createhere) 
1848                         onPe=UsrToEnv(msg)->getsetArraySrcPe();
1849                 else //Createhome
1850                         onPe=homePe(idx);
1851         }
1852         
1853         //Find the manager and build the element
1854         DEBC((AA"Demand-creating element %s on pe %d\n"AB,idx2str(idx),onPe));
1855         CkArrMgr *mgr=managers.find(UsrToEnv((void *)msg)->getsetArrayMgr())->mgr;
1856         if (!mgr) CkAbort("Tried to demand-create for nonexistent arrMgr");
1857         return mgr->demandCreateElement(idx,onPe,ctor,type);
1858 }
1859
1860 //This message took several hops to reach us-- fix it
1861 void CkLocMgr::multiHop(CkArrayMessage *msg)
1862 {
1863         CK_MAGICNUMBER_CHECK
1864         int srcPe=msg->array_getSrcPe();
1865         if (srcPe==CkMyPe())
1866                 DEB((AA"Odd routing: local element %s is %d hops away!\n"AB,idx2str(msg),msg->array_hops()));
1867         else
1868         {//Send a routing message letting original sender know new element location
1869                 DEBS((AA"Sending update back to %d for element\n"AB,srcPe,idx2str(msg)));
1870                 thisProxy[srcPe].updateLocation(msg->array_index(),CkMyPe());
1871         }
1872 }
1873
1874 /************************** LocMgr: ITERATOR *************************/
1875 CkLocation::CkLocation(CkLocMgr *mgr_, CkLocRec_local *rec_)
1876         :mgr(mgr_), rec(rec_) {}
1877         
1878 const CkArrayIndex &CkLocation::getIndex(void) const {
1879         return rec->getIndex();
1880 }
1881
1882 void CkLocation::destroyAll() {
1883         mgr->callMethod(rec, &CkMigratable::ckDestroy);
1884 }
1885
1886 void CkLocation::pup(PUP::er &p) {
1887         mgr->pupElementsFor(p,rec,CkElementCreation_migrate);
1888 }
1889
1890 CkLocIterator::~CkLocIterator() {}
1891
1892 /// Iterate over our local elements:
1893 void CkLocMgr::iterate(CkLocIterator &dest) {
1894   //Poke through the hash table for local ArrayRecs.
1895   void *objp;
1896   CkHashtableIterator *it=hash.iterator();
1897   CmiImmediateLock(hashImmLock);
1898
1899   while (NULL!=(objp=it->next())) {
1900     CkLocRec *rec=*(CkLocRec **)objp;
1901     if (rec->type()==CkLocRec::local) {
1902       CkLocation loc(this,(CkLocRec_local *)rec);
1903       dest.addLocation(loc);
1904     }
1905   }
1906   CmiImmediateUnlock(hashImmLock);
1907   delete it;
1908 }
1909
1910
1911
1912
1913 /************************** LocMgr: MIGRATION *************************/
1914
1915 void CkLocMgr::pupElementsFor(PUP::er &p,CkLocRec_local *rec,
1916                 CkElementCreation_t type)
1917 {
1918         p.comment("-------- Array Location --------");
1919         register ManagerRec *m;
1920         int localIdx=rec->getLocalIndex();
1921
1922         //First pup the element types
1923         // (A separate loop so ckLocal works even in element pup routines)
1924         for (m=firstManager;m!=NULL;m=m->next) {
1925                 int elCType;
1926                 if (!p.isUnpacking())
1927                 { //Need to find the element's existing type
1928                         CkMigratable *elt=m->element(localIdx);
1929                         if (elt) elCType=elt->ckGetChareType();
1930                         else elCType=-1; //Element hasn't been created
1931                 }
1932                 p(elCType);
1933                 if (p.isUnpacking() && elCType!=-1) {
1934                         //Create the element
1935                         CkMigratable *elt=m->mgr->allocateMigrated(elCType,rec->getIndex(),type);
1936                         int migCtorIdx=_chareTable[elCType]->getMigCtor();
1937                         //Insert into our tables and call migration constructor
1938                         if (!addElementToRec(rec,m,elt,migCtorIdx,NULL)) return;
1939                 }
1940         }
1941         //Next pup the element data
1942         for (m=firstManager;m!=NULL;m=m->next) {
1943                 CkMigratable *elt=m->element(localIdx);
1944                 if (elt!=NULL) 
1945                 {       
1946                        elt->pup(p);
1947                 }
1948         }
1949 }
1950
1951 /// Call this member function on each element of this location:
1952 void CkLocMgr::callMethod(CkLocRec_local *rec,CkMigratable_voidfn_t fn)
1953 {
1954         int localIdx=rec->getLocalIndex();
1955         for (ManagerRec *m=firstManager;m!=NULL;m=m->next) {
1956                 CkMigratable *el=m->element(localIdx);
1957                 if (el) (el->* fn)();
1958         }
1959 }
1960
1961 /// return a list of migratables in this local record
1962 void CkLocMgr::migratableList(CkLocRec_local *rec, CkVec<CkMigratable *> &list)
1963 {
1964         register ManagerRec *m;
1965         int localIdx=rec->getLocalIndex();
1966
1967         for (m=firstManager;m!=NULL;m=m->next) {
1968                 CkMigratable *elt=m->element(localIdx);
1969                 if (elt) list.push_back(elt);
1970         }
1971 }
1972
1973 /// Migrate this local element away to another processor.
1974 void CkLocMgr::emigrate(CkLocRec_local *rec,int toPe)
1975 {
1976         CK_MAGICNUMBER_CHECK
1977         if (toPe==CkMyPe()) return; //You're already there!
1978         /*
1979                 FAULT_EVAC
1980                 if the toProcessor is already marked as invalid, dont emigrate
1981                 Shouldn't happen but might
1982         */
1983         if(!CmiNodeAlive(toPe)){
1984                 return;
1985         }
1986
1987         int localIdx=rec->getLocalIndex();
1988         CkArrayIndexMax idx=rec->getIndex();
1989
1990 #if CMK_OUT_OF_CORE
1991         /* Load in any elements that are out-of-core */
1992         for (ManagerRec *m=firstManager;m!=NULL;m=m->next) {
1993                 CkMigratable *el=m->element(localIdx);
1994                 if (el) if (!el->isInCore) CooBringIn(el->prefetchObjID);
1995         }
1996 #endif
1997
1998         //Let all the elements know we're leaving
1999         callMethod(rec,&CkMigratable::ckAboutToMigrate);
2000         /*EVAC*/
2001
2002 //First pass: find size of migration message
2003         int bufSize;
2004         {
2005                 PUP::sizer p;
2006                 p(nManagers);
2007                 pupElementsFor(p,rec,CkElementCreation_migrate);
2008                 bufSize=p.size(); 
2009         }
2010
2011 //Allocate and pack into message
2012         int doubleSize=bufSize/sizeof(double)+1;
2013         CkArrayElementMigrateMessage *msg = 
2014                 new (doubleSize, 0) CkArrayElementMigrateMessage;
2015         msg->idx=idx;
2016         msg->length=bufSize;
2017 #if CMK_LBDB_ON
2018         msg->ignoreArrival = rec->isAsyncMigrate()?1:0;
2019 #endif
2020         /*
2021                 FAULT_EVAC
2022         */
2023         msg->bounced = rec->isBounced();
2024         {
2025                 PUP::toMem p(msg->packData); 
2026                 p.becomeDeleting(); 
2027                 p(nManagers);
2028                 pupElementsFor(p,rec,CkElementCreation_migrate);
2029                 if (p.size()!=bufSize) {
2030                         CkError("ERROR! Array element claimed it was %d bytes to a"
2031                                 "sizing PUP::er, but copied %d bytes into the packing PUP::er!\n",
2032                                 bufSize,p.size());
2033                         CkAbort("Array element's pup routine has a direction mismatch.\n");
2034                 }
2035         }
2036
2037         DEBM((AA"Migrated index size %s to %d \n"AB,idx2str(idx),toPe));        
2038
2039 //Send off message and delete old copy
2040         thisProxy[toPe].immigrate(msg);
2041         duringMigration=CmiTrue;
2042         delete rec; //Removes elements, hashtable entries, local index
2043         
2044         
2045         duringMigration=CmiFalse;
2046         //The element now lives on another processor-- tell ourselves and its home
2047         inform(idx,toPe);
2048         informHome(idx,toPe);
2049         CK_MAGICNUMBER_CHECK
2050 }
2051
2052 /**
2053   Migrating array element is arriving on this processor.
2054 */
2055 void CkLocMgr::immigrate(CkArrayElementMigrateMessage *msg)
2056 {
2057         CkArrayMessage *amsg=(CkArrayMessage *)msg;
2058         const CkArrayIndex &idx=msg->idx;
2059                 
2060         PUP::fromMem p(msg->packData); 
2061         
2062         int nMsgMan;
2063         p(nMsgMan);
2064         if (nMsgMan<nManagers)
2065                 CkAbort("Array element arrived from location with fewer managers!\n");
2066         if (nMsgMan>nManagers) {
2067                 //Some array managers haven't registered yet-- throw it back
2068                 DEBM((AA"Busy-waiting for array registration on migrating %s\n"AB,idx2str(idx)));
2069                 thisProxy[CkMyPe()].immigrate(msg);
2070                 return;
2071         }
2072
2073         //Create a record for this element
2074         CkLocRec_local *rec=createLocal(idx,CmiTrue,msg->ignoreArrival,CmiFalse /* home told on departure */ );
2075         
2076         //Create the new elements as we unpack the message
2077         pupElementsFor(p,rec,CkElementCreation_migrate);
2078         if (p.size()!=msg->length) {
2079                 CkError("ERROR! Array element claimed it was %d bytes to a"
2080                         "packing PUP::er, but %d bytes in the unpacking PUP::er!\n",
2081                         msg->length,p.size());
2082                 CkError("(I have %d managers; he claims %d managers)\n",
2083                         nManagers,nMsgMan);
2084                 
2085                 CkAbort("Array element's pup routine has a direction mismatch.\n");
2086         }
2087         /*
2088                 FAULT_EVAC
2089                         if this element came in as a result of being bounced off some other process,
2090                         then it needs to be resumed. It is assumed that it was bounced because load 
2091                         balancing caused it to move into a processor which later crashed
2092         */
2093         if(msg->bounced){
2094                 callMethod(rec,&CkMigratable::ResumeFromSync);
2095         }
2096         
2097         //Let all the elements know we've arrived
2098         callMethod(rec,&CkMigratable::ckJustMigrated);
2099         /*FAULT_EVAC
2100                 If this processor has started evacuating array elements on it 
2101                 dont let new immigrants in. If they arrive send them to what
2102                 would be their correct homePE.
2103                 Leave a record here mentioning the processor where it got sent
2104         */
2105         
2106         if(CpvAccess(startedEvac)){
2107                 int newhomePE = getNextPE(idx);
2108                 DEBM((AA"Migrated into failed processor index size %s resent to %d \n"AB,idx2str(idx),newhomePE));      
2109                 CkLocMgr *mgr = rec->getLocMgr();
2110                 int targetPE=getNextPE(idx);
2111                 //set this flag so that load balancer is not informed when
2112                 //this element migrates
2113                 rec->AsyncMigrate(CmiTrue);
2114                 rec->Bounced(CmiTrue);
2115                 mgr->emigrate(rec,targetPE);
2116                 
2117         }
2118
2119         delete msg;
2120 }
2121
2122 void CkLocMgr::restore(const CkArrayIndex &idx, PUP::er &p)
2123 {
2124         //This is in broughtIntoMem during out-of-core emulation in BigSim,
2125         //informHome should not be called since such information is already
2126         //immediately updated real migration
2127 #ifndef CMK_OPTIMIZE
2128         if(BgOutOfCoreFlag!=2)
2129             CmiAbort("CkLocMgr::restore should only be used in out-of-core emulation for BigSim and be called when object is brought into memory!\n");
2130 #endif
2131         CkLocRec_local *rec=createLocal(idx,CmiFalse,CmiFalse,CmiFalse);
2132         
2133         //BIGSIM_OOC DEBUGGING
2134         //CkPrintf("Proc[%d]: Registering element %s with LDB\n", CkMyPe(), idx2str(idx));
2135
2136         //Create the new elements as we unpack the message
2137         pupElementsFor(p,rec,CkElementCreation_restore);
2138
2139         callMethod(rec,&CkMigratable::ckJustRestored);
2140 }
2141
2142
2143 /// Insert and unpack this array element from this checkpoint (e.g., from CkLocation::pup)
2144 void CkLocMgr::resume(const CkArrayIndex &idx, PUP::er &p)
2145 {
2146         CkLocRec_local *rec=createLocal(idx,CmiFalse,CmiFalse,CmiTrue /* home doesn't know yet */ );
2147
2148         //Create the new elements as we unpack the message
2149         pupElementsFor(p,rec,CkElementCreation_resume);
2150
2151         callMethod(rec,&CkMigratable::ckJustMigrated);
2152 }
2153
2154 /********************* LocMgr: UTILITY ****************/
2155 void CkMagicNumber_impl::badMagicNumber(
2156         int expected,const char *file,int line,void *obj) const
2157 {
2158         CkError("FAILURE on pe %d, %s:%d> Expected %p's magic number "
2159                 "to be 0x%08x; but found 0x%08x!\n", CkMyPe(),file,line,obj,
2160                 expected, magic);
2161         CkAbort("Bad magic number detected!  This implies either\n"
2162                 "the heap or a message was corrupted!\n");
2163 }
2164 CkMagicNumber_impl::CkMagicNumber_impl(int m) :magic(m) { }
2165
2166 //Look up the object with this array index, or return NULL
2167 CkMigratable *CkLocMgr::lookup(const CkArrayIndex &idx,CkArrayID aid) {
2168         CkLocRec *rec=elementNrec(idx);
2169         if (rec==NULL) return NULL;
2170         else return rec->lookupElement(aid);
2171 }
2172 //"Last-known" location (returns a processor number)
2173 int CkLocMgr::lastKnown(const CkArrayIndex &idx) {
2174         CkLocMgr *vthis=(CkLocMgr *)this;//Cast away "const"
2175         CkLocRec *rec=vthis->elementNrec(idx);
2176         int pe=-1;
2177         if (rec!=NULL) pe=rec->lookupProcessor();
2178         if (pe==-1) return homePe(idx);
2179         else{
2180                 /*
2181                         FAULT_EVAC
2182                         if the lastKnownPE is invalid return homePE and delete this record
2183                 */
2184                 if(!CmiNodeAlive(pe)){
2185                         removeFromTable(idx);
2186                         return homePe(idx);
2187                 }
2188                 return pe;
2189         }       
2190 }
2191 /// Return true if this array element lives on another processor
2192 bool CkLocMgr::isRemote(const CkArrayIndex &idx,int *onPe) const
2193 {
2194         CkLocMgr *vthis=(CkLocMgr *)this;//Cast away "const"
2195         CkLocRec *rec=vthis->elementNrec(idx);
2196         if (rec==NULL || rec->type()!=CkLocRec::remote) 
2197                 return false; /* not definitely a remote element */
2198         else /* element is indeed remote */
2199         {
2200                 *onPe=rec->lookupProcessor();
2201                 return true;
2202         }
2203 }
2204
2205 static const char *rec2str[]={
2206     "base (INVALID)",//Base class (invalid type)
2207     "local",//Array element that lives on this Pe
2208     "remote",//Array element that lives on some other Pe
2209     "buffering",//Array element that was just created
2210     "dead"//Deleted element (for debugging)
2211 };
2212
2213 //Add given element array record at idx, replacing the existing record
2214 void CkLocMgr::insertRec(CkLocRec *rec,const CkArrayIndex &idx) {
2215         CkLocRec *old=elementNrec(idx);
2216         insertRecN(rec,idx);
2217         if (old!=NULL) {
2218                 DEBC((AA"  replaces old rec(%s) for %s\n"AB,rec2str[old->type()],idx2str(idx)));
2219                 //There was an old element at this location
2220                 if (old->type()==CkLocRec::local && rec->type()==CkLocRec::local) {
2221                     if (!CkInRestarting()) {    // ok if it is restarting
2222                         CkPrintf("ERROR! Duplicate array index: %s\n",idx2str(idx));
2223                         CkAbort("Duplicate array index used");
2224                     }
2225                 }
2226                 old->beenReplaced();
2227                 delete old;
2228         }
2229 }
2230
2231 //Add given record, when there is guarenteed to be no prior record
2232 void CkLocMgr::insertRecN(CkLocRec *rec,const CkArrayIndex &idx) {
2233         DEBC((AA"  adding new rec(%s) for %s\n"AB,rec2str[rec->type()],idx2str(idx)));
2234         CmiImmediateLock(hashImmLock);
2235         hash.put(*(CkArrayIndexMax *)&idx)=rec;
2236         CmiImmediateUnlock(hashImmLock);
2237 }
2238
2239 //Call this on an unrecognized array index
2240 static void abort_out_of_bounds(const CkArrayIndex &idx)
2241 {
2242   CkPrintf("ERROR! Unknown array index: %s\n",idx2str(idx));
2243   CkAbort("Array index out of bounds\n");
2244 }
2245
2246 //Look up array element in hash table.  Index out-of-bounds if not found.
2247 CkLocRec *CkLocMgr::elementRec(const CkArrayIndex &idx) {
2248 #ifdef CMK_OPTIMIZE
2249 //Assume the element will be found
2250         return hash.getRef(*(CkArrayIndexMax *)&idx);
2251 #else
2252 //Include an out-of-bounds check if the element isn't found
2253         CkLocRec *rec=elementNrec(idx);
2254         if (rec==NULL) abort_out_of_bounds(idx);
2255         return rec;
2256 #endif
2257 }
2258
2259 //Look up array element in hash table.  Return NULL if not there.
2260 CkLocRec *CkLocMgr::elementNrec(const CkArrayIndex &idx) {
2261         return hash.get(*(CkArrayIndexMax *)&idx);
2262 }
2263
2264 /********************* LocMgr: LOAD BALANCE ****************/
2265
2266 #if !CMK_LBDB_ON
2267 //Empty versions of all load balancer calls
2268 void CkLocMgr::initLB(CkGroupID lbdbID_) {}
2269 void CkLocMgr::startInserting(void) {}
2270 void CkLocMgr::doneInserting(void) {}
2271 void CkLocMgr::dummyAtSync(void) {}
2272 #endif
2273
2274
2275 #if CMK_LBDB_ON
2276 void CkLocMgr::initLB(CkGroupID lbdbID_)
2277 { //Find and register with the load balancer
2278         the_lbdb = (LBDatabase *)CkLocalBranch(lbdbID_);
2279         if (the_lbdb == 0)
2280                 CkAbort("LBDatabase not yet created?\n");
2281         DEBL((AA"Connected to load balancer %p\n"AB,the_lbdb));
2282
2283         // Register myself as an object manager
2284         LDOMid myId;
2285         myId.id = thisgroup;
2286         LDCallbacks myCallbacks;
2287         myCallbacks.migrate = (LDMigrateFn)CkLocRec_local::staticMigrate;
2288         myCallbacks.setStats = NULL;
2289         myCallbacks.queryEstLoad = NULL;
2290         myLBHandle = the_lbdb->RegisterOM(myId,this,myCallbacks);
2291
2292         // Tell the lbdb that I'm registering objects
2293         the_lbdb->RegisteringObjects(myLBHandle);
2294
2295         /*Set up the dummy barrier-- the load balancer needs
2296           us to call Registering/DoneRegistering during each AtSync,
2297           and this is the only way to do so.
2298         */
2299         the_lbdb->AddLocalBarrierReceiver(
2300                 (LDBarrierFn)staticRecvAtSync,(void*)(this));
2301         dummyBarrierHandle = the_lbdb->AddLocalBarrierClient(
2302                 (LDResumeFn)staticDummyResumeFromSync,(void*)(this));
2303         dummyAtSync();
2304 }
2305 void CkLocMgr::dummyAtSync(void)
2306 {
2307         DEBL((AA"dummyAtSync called\n"AB));
2308         the_lbdb->AtLocalBarrier(dummyBarrierHandle);
2309 }
2310
2311 void CkLocMgr::staticDummyResumeFromSync(void* data)
2312 {      ((CkLocMgr*)data)->dummyResumeFromSync(); }
2313 void CkLocMgr::dummyResumeFromSync()
2314 {
2315         DEBL((AA"DummyResumeFromSync called\n"AB));
2316         the_lbdb->DoneRegisteringObjects(myLBHandle);
2317         dummyAtSync();
2318 }
2319 void CkLocMgr::staticRecvAtSync(void* data)
2320 {      ((CkLocMgr*)data)->recvAtSync(); }
2321 void CkLocMgr::recvAtSync()
2322 {
2323         DEBL((AA"recvAtSync called\n"AB));
2324         the_lbdb->RegisteringObjects(myLBHandle);
2325 }
2326
2327 void CkLocMgr::startInserting(void)
2328 {
2329         the_lbdb->RegisteringObjects(myLBHandle);
2330 }
2331 void CkLocMgr::doneInserting(void)
2332 {
2333         the_lbdb->DoneRegisteringObjects(myLBHandle);
2334 }
2335 #endif
2336
2337 #include "CkLocation.def.h"
2338
2339