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