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