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