Merge branch 'replica_ft' of charmgit:charm into replica_ft
[charm.git] / src / conv-core / isomalloc.c
1 /**************************************************************************
2 Isomalloc:
3 A way to allocate memory at the same address on every processor.
4 This enables linked data structures, like thread stacks, to be migrated
5 to the same address range on other processors.  This is similar to an
6 explicitly managed shared memory system.
7
8 The memory is used and released via the mmap()/mumap() calls, so unused
9 memory does not take any (RAM, swap or disk) space.
10
11 The way it's implemented is that each processor claims some section 
12 of the available virtual address space, and satisfies all new allocations
13 from that space.  Migrating structures use whatever space they started with.
14
15 The b-tree implementation has two data structures that are maintained
16 simultaneously and in conjunction with each other: a b-tree of nodes
17 containing slotblocks used for quickly finding a particular slotblock;
18 and an array of doubly-linked lists containing the same slotblocks,
19 ordered according to the number of free slots in each slotblock, which
20 is used for quickly finding a block of free slots of a desired size.
21 The slotset contains pointers to both structures.
22 print_btree_top_down() and print_list_array() are very useful
23 functions for viewing the current structure of the tree and lists.
24
25 Each doubly-linked list has slotblocks containing between 2^(n-1)+1
26 and 2^n free slots, where n is the array index (i.e., bin number).
27 For example, list_array[0] points to a double-linked list of
28 slotblocks with 1 free slot, list_array[1] points to a double-linked
29 list of slotblocks with 2 free slots, list_array[2] to slotblocks with
30 3-4 free slots, list_array[3] to slotblocks with 5-8 free slots, etc.
31
32 Written for migratable threads by Milind Bhandarkar around August 2000;
33 generalized by Orion Lawlor November 2001.  B-tree implementation
34 added by Ryan Mokos in July 2008.
35  *************************************************************************/
36
37 #include "converse.h"
38 #include "memory-isomalloc.h"
39
40 #define ISOMALLOC_DEBUG 0
41
42 /* 0: use the old isomalloc implementation (array)
43 1: use the new isomalloc implementation (b-tree)  */
44 #define USE_BTREE_ISOMALLOC 1
45
46 /* b-tree definitions */
47 #define TREE_NODE_SIZE 128 /* a power of 2 is probably best  */
48 #define TREE_NODE_MID  63  /* must be cieling(TREE_NODE_SIZE / 2) - 1  */
49
50 /* linked list definitions  */
51 #define LIST_ARRAY_SIZE 64
52
53 #include <fcntl.h>
54 #include <stdio.h>
55 #include <stdlib.h>
56 #include <errno.h> /* just so I can find dynamically-linked symbols */
57 #include <unistd.h>
58
59 #if CMK_HAS_ADDR_NO_RANDOMIZE
60 #include <sys/personality.h>
61 #endif
62
63 #if CMK_USE_MEMPOOL_ISOMALLOC
64 #include "mempool.h"
65 extern int cutOffPoints[cutOffNum];
66 #endif 
67
68 static int _sync_iso = 0;
69 #if __FAULT__
70 static int _restart = 0;
71 #endif
72 static int _mmap_probe = 0;
73
74 static int read_randomflag(void)
75 {
76   FILE *fp;
77   int random_flag;
78   fp = fopen("/proc/sys/kernel/randomize_va_space", "r");
79   if (fp != NULL) {
80     fscanf(fp, "%d", &random_flag);
81     fclose(fp);
82 #if CMK_HAS_ADDR_NO_RANDOMIZE
83     if(random_flag)
84     {
85       int persona = personality(0xffffffff);
86       if(persona & ADDR_NO_RANDOMIZE)
87         random_flag = 0;
88     }
89 #endif
90   }
91   else {
92     random_flag = -1;
93   }
94   return random_flag;
95 }
96
97 struct CmiIsomallocBlock {
98   CmiInt8 slot;   /* First mapped slot */
99   CmiInt8 length; /* Length of (user portion of) mapping, in bytes*/
100 };
101 typedef struct CmiIsomallocBlock CmiIsomallocBlock;
102
103 /* Convert a heap block pointer to/from a CmiIsomallocBlock header */
104 static void *block2pointer(CmiIsomallocBlock *blockHeader) {
105   return (void *)(blockHeader+1);
106 }
107 static CmiIsomallocBlock *pointer2block(void *heapBlock) {
108   return ((CmiIsomallocBlock *)heapBlock)-1;
109 }
110
111 /* Integral type to be used for pointer arithmetic: */
112 typedef size_t memRange_t;
113
114 /* Size in bytes of a single slot */
115 static size_t slotsize;
116 static size_t regionSize;
117
118 /* Total number of slots per processor */
119 static CmiInt8 numslots=0;
120
121 /* Start and end of isomalloc-managed addresses.
122    If isomallocStart==NULL, isomalloc is disabled.
123    */
124 static char *isomallocStart=NULL;
125 static char *isomallocEnd=NULL;
126
127 /* Utility conversion functions */
128 static void *slot2addr(CmiInt8 slot) {
129   return isomallocStart+((memRange_t)slotsize)*((memRange_t)slot);
130 }
131 static int slot2pe(CmiInt8 slot) {
132   return (int)(slot/numslots);
133 }
134 static CmiInt8 pe2slot(int pe) {
135   return pe*numslots;
136 }
137 /* Return the number of slots in a block with n user data bytes */
138 #if CMK_USE_MEMPOOL_ISOMALLOC
139 static int length2slots(int nBytes) {
140   return (nBytes+slotsize-1)/slotsize;
141 }
142 #else
143 static int length2slots(int nBytes) {
144   return (sizeof(CmiIsomallocBlock)+nBytes+slotsize-1)/slotsize;
145 }
146 #endif
147 /* ======================================================================
148  * New isomalloc (b-tree-based implementation)
149  * ====================================================================== */
150
151 #if USE_BTREE_ISOMALLOC
152
153 /* doubly-linked list node */
154 struct _dllnode {
155   struct _dllnode   *previous;
156   struct _slotblock *sb;
157   struct _dllnode   *next;
158 };
159
160 /* slotblock */
161 struct _slotblock {
162   CmiInt8 startslot;
163   CmiInt8 nslots;
164   struct _dllnode *listblock;
165 };
166
167 typedef struct _dllnode   dllnode;
168 typedef struct _slotblock slotblock;
169
170 /* b-tree node */
171 struct _btreenode {
172   int num_blocks;
173   slotblock blocks[TREE_NODE_SIZE];
174   struct _btreenode *child[TREE_NODE_SIZE + 1];
175 };
176 typedef struct _btreenode btreenode;
177
178 /* slotset */
179 typedef struct _slotset {
180   btreenode *btree_root;
181   dllnode *list_array[LIST_ARRAY_SIZE];
182 } slotset;
183
184 /* return value for a b-tree insert */
185 typedef struct _insert_ret_val {
186   slotblock sb;
187   btreenode *btn;
188 } insert_ret_val;
189
190 /*****************************************************************
191  * Find and return the number of the bin (list) to which the number
192  * nslots belongs.  The range of each bin is 2^(b-1)+1 to 2^b, where b
193  * is the bin number.
194  *****************************************************************/
195
196 static int find_list_bin(CmiInt8 nslots) {
197   int list_bin     = 32;
198   CmiInt8 comp_num = 0x100000000LL;
199   int inc          = 16;
200
201   while (1) {
202     if ((nslots > (comp_num >> 1)) && (nslots <= comp_num)) {
203       /* found it */
204       return list_bin;
205     } else if (nslots < comp_num) {
206       /* look left  */
207       list_bin -= inc;
208       comp_num  = comp_num >> inc;
209       if ((inc = inc >> 1) == 0) {
210         inc = 1;
211       }
212     } else {
213       /* look right */
214       list_bin += inc;
215       comp_num  = comp_num << inc;
216       if ((inc = inc >> 1) == 0) {
217         inc = 1;
218       }
219     }
220   }
221
222 }
223
224 /*****************************************************************
225  * Creates and inserts a new dllnode into list_array (part of the
226  * slotset ss) that both points to and is pointed to by the slotblock
227  * sb.  This function also returns a pointer to that new dllnode.
228  *****************************************************************/
229
230 static dllnode *list_insert(slotset *ss, slotblock *sb) {
231
232   /* find the list bin to put the new dllnode in  */
233   int list_bin = find_list_bin(sb->nslots);
234
235   /* allocate memory for the new node */
236   dllnode *new_dlln = (dllnode *)(malloc_reentrant(sizeof(dllnode)));
237
238   /* insert the dllnode */
239   new_dlln->previous = NULL;
240   new_dlln->next     = ss->list_array[list_bin];
241   new_dlln->sb       = sb;
242   if (ss->list_array[list_bin] != NULL) {
243     ss->list_array[list_bin]->previous = new_dlln;
244   }
245   ss->list_array[list_bin] = new_dlln;
246
247   return new_dlln;
248
249 }
250
251 /*****************************************************************
252  * Deletes the dllnode from list_array (part of the slotset ss) that
253  * is pointed to by the slotblock sb.
254  *****************************************************************/
255
256 static void list_delete(slotset *ss, slotblock *sb) {
257
258   /* remove the node from the list */
259   if (sb->listblock->next != NULL) {
260     sb->listblock->next->previous = sb->listblock->previous;
261   }
262   if (sb->listblock->previous != NULL) {
263     sb->listblock->previous->next = sb->listblock->next;
264   } else {  /* first element in the list */
265     ss->list_array[find_list_bin(sb->nslots)] = sb->listblock->next;
266   }
267
268   /* free the memory from the node */
269   free_reentrant(sb->listblock);
270
271 }
272
273 /*****************************************************************
274  * Moves the dllnode dlln to the correct bin (list) of slotset ss
275  * based on the number of slots in the slotblock to which dlln points.
276  * It is assumed that the slotblock pointed to by dlln has already been
277  * updated with the new number of slots.  The integer old_nslots
278  * contains the number of slots that used to be in the slotblock.
279  *****************************************************************/
280
281 static void list_move(slotset *ss, dllnode *dlln, CmiInt8 old_nslots) {
282
283   /* determine the bin the slotblock used to be in */
284   int old_bin = find_list_bin(old_nslots);
285
286   /* determine the bin the slotblock is in now */
287   int new_bin = find_list_bin(dlln->sb->nslots);
288
289   /* if the old bin and new bin are different, move the slotblock */
290   if (new_bin != old_bin) {
291
292     /* remove from old bin */
293     if (dlln->previous == NULL) {  /* dlln is the 1st element in the list */
294       if (dlln->next != NULL) {
295         dlln->next->previous = NULL;
296       }
297       ss->list_array[old_bin] = dlln->next;
298     } else {
299       if (dlln->next != NULL) {
300         dlln->next->previous = dlln->previous;
301       }
302       dlln->previous->next = dlln->next;
303     }
304
305     /* insert at the beginning of the new bin */
306     dlln->next     = ss->list_array[new_bin];
307     dlln->previous = NULL;
308     if (dlln->next != NULL) {
309       dlln->next->previous = dlln;
310     }
311     ss->list_array[new_bin] = dlln;
312   }
313
314 }
315
316 /*****************************************************************
317  * Creates a new b-tree node
318  *****************************************************************/
319
320 static btreenode *create_btree_node() {
321   int i;
322   btreenode *btn = (btreenode *)malloc_reentrant(sizeof(btreenode));
323   btn->num_blocks = 0;
324   for (i = 0; i < TREE_NODE_SIZE; i++) {
325     btn->blocks[i].listblock = NULL;
326   }
327   for (i = 0; i < TREE_NODE_SIZE + 1; i++) {
328     btn->child[i] = NULL;
329   }
330   return btn;
331 }
332
333 /*****************************************************************
334  * Find the slotblock in the b-tree that contains startslot.  Returns
335  * NULL if such a block cannot be found.
336  *****************************************************************/
337
338 static slotblock *find_btree_slotblock(btreenode *node, CmiInt8 startslot) {
339
340   /* check if this node exists */
341   if ((node == NULL) || (startslot < 0) || (node->num_blocks == 0)) {
342     return NULL;
343   } else {
344
345     /*** Binary search on this node ***/
346     /* initialize */
347     int index = node->num_blocks >> 1;
348     int inc   = (index >> 1) + (node->num_blocks & 0x1);
349     CmiInt8 endslot;
350
351     /* loop until a node is found */
352     while (1) {
353
354       /* if startslot is in current slotblock, this is the slotblock */
355       endslot = node->blocks[index].startslot + node->blocks[index].nslots - 1;
356       if ((startslot >= node->blocks[index].startslot) &&
357           (startslot <= endslot)) {
358         return &(node->blocks[index]);
359       }
360
361       /* else, if startslot is less */
362       else if (startslot < node->blocks[index].startslot) {
363
364         /* if this is slotblock 0, take the left child */
365         if (index == 0) {
366           return find_btree_slotblock(node->child[index], startslot);
367         }
368
369         /* else check endslot of the slotblock to the left */
370         else {
371
372           /* if startslot > endslot-of-slotblock-to-the-left, take the
373              left child */
374           endslot = node->blocks[index-1].startslot + 
375             node->blocks[index-1].nslots - 1;
376           if (startslot > endslot) {
377             return find_btree_slotblock(node->child[index], startslot);
378           }
379
380           /* else continue to search this node to the left */
381           else {
382             index -= inc;
383             if ((inc = inc >> 1) == 0) {
384               inc = 1;
385             }
386           }
387         }
388       }
389
390       /* else, startslot must be greater */
391       else {
392
393         /* if this is the last slotblock, take the right child */
394         if (index == node->num_blocks - 1) {
395           return find_btree_slotblock(node->child[index+1], startslot);
396         }
397
398         /* else check startslot of the slotblock to the right */
399         else {
400
401           /* if startslot < startslot-of-slotblock-to-the-right, then
402              take the right child */
403           if (startslot < node->blocks[index+1].startslot) {
404             return find_btree_slotblock(node->child[index+1], startslot);
405           }
406
407           /* else continue to search this node to the right */
408           else {
409             index += inc;
410             if ((inc = inc >> 1) == 0) {
411               inc = 1;
412             }
413           }
414         }
415       }
416
417     }
418
419   }
420
421 }
422
423 /*****************************************************************
424  * Insert a slotblock into the b-tree starting at startslot and going
425  * for nslots slots
426  *****************************************************************/
427
428 static insert_ret_val btree_insert_int(slotset *ss, btreenode *node, 
429     CmiInt8 startslot, CmiInt8 nslots) {
430
431   insert_ret_val irv;
432
433   /*** binary search for the place to insert ***/
434
435   /* initialize */
436   int index = node->num_blocks >> 1;
437   int inc   = (index >> 1) + (node->num_blocks & 0x1);
438
439   /* loop until an insertion happens */
440   while (1) {
441     if (startslot < node->blocks[index].startslot) {  /* look to the left */
442       if ((index == 0) || 
443           (startslot > node->blocks[index-1].startslot)) {
444         if (node->child[index] != NULL) {             /* take left child */
445           irv = btree_insert_int(ss, node->child[index], startslot, nslots);
446           if (irv.btn == NULL) {
447             return irv;
448           } else {                                    /* merge return value */
449             int i, j;                                 /*   insert on left   */
450             for (i = node->num_blocks; i > index; i--) {
451               node->blocks[i].startslot     = node->blocks[i-1].startslot;
452               node->blocks[i].nslots        = node->blocks[i-1].nslots;
453               node->blocks[i].listblock     = node->blocks[i-1].listblock;
454               node->blocks[i].listblock->sb = &(node->blocks[i]);
455               node->child[i+1]              = node->child[i];
456             }
457             node->blocks[index].startslot     = irv.sb.startslot;
458             node->blocks[index].nslots        = irv.sb.nslots;
459             node->blocks[index].listblock     = irv.sb.listblock;
460             node->blocks[index].listblock->sb = &(node->blocks[index]);
461             node->child[index+1]              = irv.btn;
462             node->num_blocks++;
463             if (node->num_blocks == TREE_NODE_SIZE) {   /* split node */
464               btreenode *new_node = create_btree_node();
465               for (i = TREE_NODE_MID + 1; i < TREE_NODE_SIZE; i++) {
466                 j = i - (TREE_NODE_MID + 1);
467                 new_node->blocks[j].startslot     = node->blocks[i].startslot;
468                 new_node->blocks[j].nslots        = node->blocks[i].nslots;
469                 new_node->blocks[j].listblock     = node->blocks[i].listblock;
470                 new_node->blocks[j].listblock->sb = &(new_node->blocks[j]);
471               }
472               for (i = TREE_NODE_MID + 1; i <= TREE_NODE_SIZE; i++) {
473                 new_node->child[i-(TREE_NODE_MID+1)] = node->child[i];
474               }
475               node->num_blocks     = TREE_NODE_MID;
476               new_node->num_blocks = TREE_NODE_SIZE - TREE_NODE_MID - 1;
477
478               irv.sb.startslot = node->blocks[TREE_NODE_MID].startslot;
479               irv.sb.nslots    = node->blocks[TREE_NODE_MID].nslots;
480               irv.sb.listblock = node->blocks[TREE_NODE_MID].listblock;
481               irv.btn          = new_node;
482               return irv;
483             } else {
484               irv.btn = NULL;
485               return irv;
486             }
487           }
488         } else {                                      /* insert to the left */
489           int i, j;
490           for (i = node->num_blocks; i > index; i--) {
491             node->blocks[i].startslot     = node->blocks[i-1].startslot;
492             node->blocks[i].nslots        = node->blocks[i-1].nslots;
493             node->blocks[i].listblock     = node->blocks[i-1].listblock;
494             node->blocks[i].listblock->sb = &(node->blocks[i]);
495           }
496           node->blocks[index].startslot = startslot;
497           node->blocks[index].nslots    = nslots;
498           node->blocks[index].listblock = list_insert(ss, &(node->blocks[index]));
499           node->num_blocks++;
500           if (node->num_blocks == TREE_NODE_SIZE) {   /* split node */
501             btreenode *new_node = create_btree_node();
502             for (i = TREE_NODE_MID + 1; i < TREE_NODE_SIZE; i++) {
503               j = i - (TREE_NODE_MID + 1);
504               new_node->blocks[j].startslot     = node->blocks[i].startslot;
505               new_node->blocks[j].nslots        = node->blocks[i].nslots;
506               new_node->blocks[j].listblock     = node->blocks[i].listblock;
507               new_node->blocks[j].listblock->sb = &(new_node->blocks[j]);
508             }
509             node->num_blocks     = TREE_NODE_MID;
510             new_node->num_blocks = TREE_NODE_SIZE - TREE_NODE_MID - 1;
511
512             irv.sb.startslot = node->blocks[TREE_NODE_MID].startslot;
513             irv.sb.nslots    = node->blocks[TREE_NODE_MID].nslots;
514             irv.sb.listblock = node->blocks[TREE_NODE_MID].listblock;
515             irv.btn          = new_node;
516             return irv;
517           } else {
518             irv.btn = NULL;
519             return irv;
520           }
521         }
522       } else {                                        /* search to the left */
523         index -= inc;
524         if ((inc = inc >> 1) == 0) {
525           inc = 1;
526         }
527       }
528
529     } else {                                          /* look to the right */
530
531       if ((index == node->num_blocks - 1) || 
532           (startslot < node->blocks[index+1].startslot)) {
533         if (node->child[index+1] != NULL) {           /* take right child */
534           irv = btree_insert_int(ss, node->child[index+1], startslot, nslots);
535           if (irv.btn == NULL) {
536             return irv;
537           } else {                                    /* merge return value */
538             int i, j;                                 /*   insert on right  */
539             for (i = node->num_blocks; i > index + 1; i--) {
540               node->blocks[i].startslot     = node->blocks[i-1].startslot;
541               node->blocks[i].nslots        = node->blocks[i-1].nslots;
542               node->blocks[i].listblock     = node->blocks[i-1].listblock;
543               node->blocks[i].listblock->sb = &(node->blocks[i]);
544               node->child[i+1]              = node->child[i];
545             }
546             node->blocks[index+1].startslot     = irv.sb.startslot;
547             node->blocks[index+1].nslots        = irv.sb.nslots;
548             node->blocks[index+1].listblock     = irv.sb.listblock;
549             node->blocks[index+1].listblock->sb = &(node->blocks[index+1]);
550             node->child[index+2]                = irv.btn;
551             node->num_blocks++;
552             if (node->num_blocks == TREE_NODE_SIZE) {   /* split node */
553               btreenode *new_node = create_btree_node();
554               for (i = TREE_NODE_MID + 1; i < TREE_NODE_SIZE; i++) {
555                 j = i - (TREE_NODE_MID + 1);
556                 new_node->blocks[j].startslot     = node->blocks[i].startslot;
557                 new_node->blocks[j].nslots        = node->blocks[i].nslots;
558                 new_node->blocks[j].listblock     = node->blocks[i].listblock;
559                 new_node->blocks[j].listblock->sb = &(new_node->blocks[j]);
560               }
561               for (i = TREE_NODE_MID + 1; i <= TREE_NODE_SIZE; i++) {
562                 new_node->child[i-(TREE_NODE_MID+1)] = node->child[i];
563               }
564               node->num_blocks     = TREE_NODE_MID;
565               new_node->num_blocks = TREE_NODE_SIZE - TREE_NODE_MID - 1;
566
567               irv.sb.startslot = node->blocks[TREE_NODE_MID].startslot;
568               irv.sb.nslots    = node->blocks[TREE_NODE_MID].nslots;
569               irv.sb.listblock = node->blocks[TREE_NODE_MID].listblock;
570               irv.btn          = new_node;
571               return irv;
572             } else {
573               irv.btn = NULL;
574               return irv;
575             }
576           }
577         } else {                                      /* insert to the right */
578           int i, j;
579           for (i = node->num_blocks; i > index + 1; i--) {
580             node->blocks[i].startslot     = node->blocks[i-1].startslot;
581             node->blocks[i].nslots        = node->blocks[i-1].nslots;
582             node->blocks[i].listblock     = node->blocks[i-1].listblock;
583             node->blocks[i].listblock->sb = &(node->blocks[i]);
584           }
585           node->blocks[index+1].startslot = startslot;
586           node->blocks[index+1].nslots    = nslots;
587           node->blocks[index+1].listblock = list_insert(ss, &(node->blocks[index+1]));
588           node->num_blocks++;
589           if (node->num_blocks == TREE_NODE_SIZE) {   /* split node */
590             btreenode *new_node = create_btree_node();
591             for (i = TREE_NODE_MID + 1; i < TREE_NODE_SIZE; i++) {
592               j = i - (TREE_NODE_MID + 1);
593               new_node->blocks[j].startslot     = node->blocks[i].startslot;
594               new_node->blocks[j].nslots        = node->blocks[i].nslots;
595               new_node->blocks[j].listblock     = node->blocks[i].listblock;
596               new_node->blocks[j].listblock->sb = &(new_node->blocks[j]);
597             }
598             node->num_blocks = TREE_NODE_MID;
599             new_node->num_blocks = TREE_NODE_SIZE - TREE_NODE_MID - 1;
600
601             irv.sb.startslot = node->blocks[TREE_NODE_MID].startslot;
602             irv.sb.nslots    = node->blocks[TREE_NODE_MID].nslots;
603             irv.sb.listblock = node->blocks[TREE_NODE_MID].listblock;
604             irv.btn          = new_node;
605             return irv;
606           } else {
607             irv.btn = NULL;
608             return irv;
609           }
610         }
611       } else {                                        /* search to the right */
612         index += inc;
613         if ((inc = inc >> 1) == 0) {
614           inc = 1;
615         }
616       }
617     }
618   }
619
620 }
621
622 static btreenode *btree_insert(slotset *ss, btreenode *node, 
623     CmiInt8 startslot, CmiInt8 nslots) {
624
625   /* check the b-tree root: if it's empty, insert the element in the
626      first position */
627   if (node->num_blocks == 0) {
628
629     node->num_blocks          = 1;
630     node->blocks[0].startslot = startslot;
631     node->blocks[0].nslots    = nslots;
632     node->blocks[0].listblock = list_insert(ss, &(node->blocks[0]));
633
634   } else {
635
636     /* insert into the b-tree */
637     insert_ret_val irv = btree_insert_int(ss, node, startslot, nslots);
638
639     /* if something was returned, we need a new root */
640     if (irv.btn != NULL) {
641       btreenode *new_root  = create_btree_node();
642       new_root->num_blocks = 1;
643       new_root->blocks[0].startslot     = irv.sb.startslot;
644       new_root->blocks[0].nslots        = irv.sb.nslots;
645       new_root->blocks[0].listblock     = irv.sb.listblock;
646       new_root->blocks[0].listblock->sb = &(new_root->blocks[0]);
647       new_root->child[0] = node;
648       new_root->child[1] = irv.btn;
649       node = new_root;
650     }
651
652   }
653
654   return node;
655
656 }
657
658 /*****************************************************************
659  * Delete the slotblock from the b-tree starting at startslot
660  *****************************************************************/
661
662 static void btree_delete_int(slotset *ss, btreenode *node, 
663     CmiInt8 startslot, slotblock *sb) {
664
665   int i, index, inc;
666   int def_child;
667   int num_left, num_right, left_pos, right_pos;
668
669   /* If sb is not NULL, we're sending sb down the tree to a leaf to be
670      swapped with the next larger startslot so it can be deleted from
671      a leaf node (deletions from non-leaf nodes are not allowed
672      here).  At this point, the next larger startslot will always be
673      found by taking the leftmost child.  */
674   if (sb != NULL) {
675
676     if (node->child[0] != NULL) {
677       btree_delete_int(ss, node->child[0], startslot, sb);
678       index = 0;
679
680     } else {
681
682       /* we're now at a leaf node, so the slotblock can be deleted
683
684          first, copy slotblock 0 to the block passed down (sb) and
685          delete the list array node  */
686       list_delete(ss, sb);
687       sb->startslot     = node->blocks[0].startslot;
688       sb->nslots        = node->blocks[0].nslots;
689       sb->listblock     = node->blocks[0].listblock;
690       sb->listblock->sb = sb;
691
692       /* delete the slotblock */
693       for (i = 0; i < (node->num_blocks - 1); i++) {
694         node->blocks[i].startslot     = node->blocks[i+1].startslot;
695         node->blocks[i].nslots        = node->blocks[i+1].nslots;
696         node->blocks[i].listblock     = node->blocks[i+1].listblock;
697         node->blocks[i].listblock->sb = &(node->blocks[i]);
698       }
699       node->num_blocks--;
700
701       return;
702
703     }
704
705   } else {
706
707     /*** Binary search for the slotblock to delete ***/
708
709     /* initialize */
710     index = node->num_blocks >> 1;
711     inc = (index >> 1) + (node->num_blocks & 0x1);
712
713     /* loop until the slotblock with startslot is found */
714     while (1) {
715
716       if (startslot == node->blocks[index].startslot) {   /* found it */
717         if (node->child[index+1] != NULL) {               /* not a leaf */
718           btree_delete_int(ss, node->child[index+1], 
719               startslot, &(node->blocks[index]));
720           break;
721         } else {                                          /* is a leaf */
722           /* delete the slotblock */
723           list_delete(ss, &(node->blocks[index]));
724           for (i = index; i < (node->num_blocks - 1); i++) {
725             node->blocks[i].startslot     = node->blocks[i+1].startslot;
726             node->blocks[i].nslots        = node->blocks[i+1].nslots;
727             node->blocks[i].listblock     = node->blocks[i+1].listblock;
728             node->blocks[i].listblock->sb = &(node->blocks[i]);
729           }
730           node->num_blocks--;
731           return;
732         }
733       } else {
734         if (startslot < node->blocks[index].startslot) {  /* look left */
735           if ((index == 0) ||                             /* take left child */
736               (startslot > node->blocks[index-1].startslot)) {
737             btree_delete_int(ss, node->child[index], startslot, sb);
738             break;
739           } else {                                        /* search left */
740             index -= inc;
741             if ((inc = inc >> 1) == 0) {
742               inc = 1;
743             }
744           }
745         } else {                                          /* look right */
746           if ((index == node->num_blocks - 1) ||          /* take right child */
747               (startslot < node->blocks[index+1].startslot)) {
748             btree_delete_int(ss, node->child[index+1], startslot, sb);
749             break;
750           } else {                                        /* search right */
751             index += inc;
752             if ((inc = inc >> 1) == 0) {
753               inc = 1;
754             }
755           }
756         }
757       }
758
759     }
760
761   }
762
763   /* At this point, the desired slotblock has been removed, and we're
764      going back up the tree.  We must check for deficient nodes that
765      require the rotating or combining of elements to maintain a
766      balanced b-tree. */
767   def_child = -1;
768
769   /* check if one of the child nodes is deficient  */
770   if (node->child[index]->num_blocks < TREE_NODE_MID) {
771     def_child = index;
772   } else if (node->child[index+1]->num_blocks < TREE_NODE_MID) {
773     def_child = index + 1;
774   }
775
776   if (def_child >= 0) {
777
778     /* if there is a left sibling and it has enough elements, rotate */
779     /* to the right */
780     if ((def_child != 0) && (node->child[def_child-1] != NULL) && 
781         (node->child[def_child-1]->num_blocks > TREE_NODE_MID)) {
782
783       /* move all elements in deficient child to the right */
784       for (i = node->child[def_child]->num_blocks; i > 0; i--) {
785         node->child[def_child]->blocks[i].startslot = 
786           node->child[def_child]->blocks[i-1].startslot;
787         node->child[def_child]->blocks[i].nslots = 
788           node->child[def_child]->blocks[i-1].nslots;
789         node->child[def_child]->blocks[i].listblock = 
790           node->child[def_child]->blocks[i-1].listblock;
791         node->child[def_child]->blocks[i].listblock->sb = 
792           &(node->child[def_child]->blocks[i]);
793       }
794       for (i = node->child[def_child]->num_blocks + 1; i > 0; i--) {
795         node->child[def_child]->child[i] = 
796           node->child[def_child]->child[i-1];
797       }
798
799       /* move parent element to the deficient child */
800       node->child[def_child]->blocks[0].startslot = 
801         node->blocks[def_child-1].startslot;
802       node->child[def_child]->blocks[0].nslots = 
803         node->blocks[def_child-1].nslots;
804       node->child[def_child]->blocks[0].listblock = 
805         node->blocks[def_child-1].listblock;
806       node->child[def_child]->blocks[0].listblock->sb = 
807         &(node->child[def_child]->blocks[0]);
808       node->child[def_child]->num_blocks++;
809
810       /* move the right-most child of the parent's left child to the
811          left-most child of the formerly deficient child  */
812       i = node->child[def_child-1]->num_blocks;
813       node->child[def_child]->child[0] = 
814         node->child[def_child-1]->child[i];
815
816       /* move largest element from left child up to the parent */
817       i--;
818       node->blocks[def_child-1].startslot = 
819         node->child[def_child-1]->blocks[i].startslot;
820       node->blocks[def_child-1].nslots = 
821         node->child[def_child-1]->blocks[i].nslots;
822       node->blocks[def_child-1].listblock = 
823         node->child[def_child-1]->blocks[i].listblock;
824       node->blocks[def_child-1].listblock->sb = 
825         &(node->blocks[def_child-1]);
826       node->child[def_child-1]->num_blocks--;
827
828     }
829
830     /* otherwise, if there is a right sibling and it has enough */
831     /* elements, rotate to the left */
832     else if (((def_child + 1) <= node->num_blocks) && 
833         (node->child[def_child+1] != NULL) && 
834         (node->child[def_child+1]->num_blocks > TREE_NODE_MID)) {
835
836       /* move parent element to the deficient child */
837       i = node->child[def_child]->num_blocks;
838       node->child[def_child]->blocks[i].startslot = 
839         node->blocks[def_child].startslot;
840       node->child[def_child]->blocks[i].nslots = 
841         node->blocks[def_child].nslots;
842       node->child[def_child]->blocks[i].listblock = 
843         node->blocks[def_child].listblock;
844       node->child[def_child]->blocks[i].listblock->sb = 
845         &(node->child[def_child]->blocks[i]);
846       node->child[def_child]->num_blocks++;
847
848       /* move the left-most child of the parent's right child to the
849          right-most child of the formerly deficient child  */
850       i++;
851       node->child[def_child]->child[i] = 
852         node->child[def_child+1]->child[0];
853
854       /* move smallest element from right child up to the parent */
855       node->blocks[def_child].startslot = 
856         node->child[def_child+1]->blocks[0].startslot;
857       node->blocks[def_child].nslots = 
858         node->child[def_child+1]->blocks[0].nslots;
859       node->blocks[def_child].listblock = 
860         node->child[def_child+1]->blocks[0].listblock;
861       node->blocks[def_child].listblock->sb = 
862         &(node->blocks[def_child]);
863       node->child[def_child+1]->num_blocks--;
864
865       /* move all elements in the parent's right child to the left  */
866       for (i = 0; i < node->child[def_child+1]->num_blocks; i++) {
867         node->child[def_child+1]->blocks[i].startslot = 
868           node->child[def_child+1]->blocks[i+1].startslot;
869         node->child[def_child+1]->blocks[i].nslots = 
870           node->child[def_child+1]->blocks[i+1].nslots;
871         node->child[def_child+1]->blocks[i].listblock = 
872           node->child[def_child+1]->blocks[i+1].listblock;
873         node->child[def_child+1]->blocks[i].listblock->sb = 
874           &(node->child[def_child+1]->blocks[i]);
875       }
876       for (i = 0; i < node->child[def_child+1]->num_blocks + 1; i++) {
877         node->child[def_child+1]->child[i] = 
878           node->child[def_child+1]->child[i+1];
879       }
880     }
881
882     /* otherwise, merge the deficient node, parent, and the parent's
883        other child (one of the deficient node's siblings) by dropping
884        the parent down to the level of the children */
885     else {
886
887       /* move the parent element into the left child node */
888       i = node->child[index]->num_blocks;
889       node->child[index]->blocks[i].startslot = 
890         node->blocks[index].startslot;
891       node->child[index]->blocks[i].nslots = 
892         node->blocks[index].nslots;
893       node->child[index]->blocks[i].listblock = 
894         node->blocks[index].listblock;
895       node->child[index]->blocks[i].listblock->sb = 
896         &(node->child[index]->blocks[i]);
897       node->child[index]->num_blocks++;
898
899       /* move the elements and children of the right child node to the */
900       /* left child node */
901       num_left  = node->child[index]->num_blocks;
902       num_right = node->child[index+1]->num_blocks;
903       left_pos;
904       right_pos = 0;
905       for (left_pos = num_left; left_pos < num_left + num_right; left_pos++) {
906         node->child[index]->blocks[left_pos].startslot = 
907           node->child[index+1]->blocks[right_pos].startslot;
908         node->child[index]->blocks[left_pos].nslots = 
909           node->child[index+1]->blocks[right_pos].nslots;
910         node->child[index]->blocks[left_pos].listblock = 
911           node->child[index+1]->blocks[right_pos].listblock;
912         node->child[index]->blocks[left_pos].listblock->sb = 
913           &(node->child[index]->blocks[left_pos]);
914         right_pos++;
915       }
916       right_pos = 0;
917       for (left_pos = num_left; left_pos < num_left + num_right + 1; left_pos++) {
918         node->child[index]->child[left_pos] = 
919           node->child[index+1]->child[right_pos];
920         right_pos++;
921       }
922       node->child[index]->num_blocks = num_left + num_right;
923
924       /* delete the right child node */
925       free_reentrant(node->child[index+1]);
926       node->child[index+1] = NULL;
927
928       /* update the parent node */
929       node->num_blocks--;
930       for (i = index; i < node->num_blocks; i++) {
931         node->blocks[i].startslot     = node->blocks[i+1].startslot;
932         node->blocks[i].nslots        = node->blocks[i+1].nslots;
933         node->blocks[i].listblock     = node->blocks[i+1].listblock;
934         node->blocks[i].listblock->sb = &(node->blocks[i]);
935         node->child[i+1]              = node->child[i+2];
936       }
937
938     }
939
940   }
941
942 }
943
944 static btreenode *btree_delete(slotset *ss, btreenode *node, CmiInt8 startslot) {
945
946   /* delete element from the b-tree */
947   btree_delete_int(ss, node, startslot, NULL);
948
949   /* if the root node is empty (from a combine operation on the tree),
950      the left-most child of the root becomes the new root, unless the
951      left-most child is NULL, in which case we leave the root node
952      empty but not NULL */
953   if (node->num_blocks == 0) {
954     if (node->child[0] != NULL) {
955       btreenode *new_root = node->child[0];
956       free_reentrant(node);
957       node = new_root;
958     }
959   }
960
961   return node;
962
963 }
964
965 /*****************************************************************
966  * Creates a new slotset with nslots entries, starting with all empty
967  * slots.  The slot numbers are [startslot, startslot + nslots - 1].
968  *****************************************************************/
969
970 static slotset *new_slotset(CmiInt8 startslot, CmiInt8 nslots) {
971   int i;
972   int list_bin;
973
974   /* CmiPrintf("*** New Isomalloc ***\n"); */
975
976   /* allocate memory for the slotset */
977   slotset *ss = (slotset *)(malloc_reentrant(sizeof(slotset)));
978
979   /* allocate memory for the b-tree */
980   ss->btree_root = create_btree_node();
981
982   /* initialize the b-tree */
983   ss->btree_root->num_blocks          = 1;
984   ss->btree_root->blocks[0].startslot = startslot;
985   ss->btree_root->blocks[0].nslots    = nslots;
986
987   /* initialize the list array */
988   for (i = 0; i < LIST_ARRAY_SIZE; i++) {
989     ss->list_array[i] = NULL;
990   }
991   list_bin = find_list_bin(nslots);
992   ss->list_array[list_bin] = (dllnode *)(malloc_reentrant(sizeof(dllnode)));
993   ss->list_array[list_bin]->previous = NULL;
994   ss->list_array[list_bin]->next = NULL;
995   ss->list_array[list_bin]->sb = &(ss->btree_root->blocks[0]);
996
997   ss->btree_root->blocks[0].listblock = ss->list_array[list_bin];
998
999   return ss;
1000
1001 }
1002
1003 /*****************************************************************
1004  * Finds a slotblock containing at least nslots memory slots and
1005  * returns the startslot of that slotblock; returns -1 if no such
1006  * slotblock exists.
1007  *****************************************************************/
1008
1009 static CmiInt8 get_slots(slotset *ss, CmiInt8 nslots) {
1010
1011   /* calculate the smallest bin (list) to look in first */
1012   int start_list = find_list_bin(nslots);
1013
1014   /* search for a slotblock with enough slots */
1015   int i;
1016   dllnode *dlln;
1017   for (i = start_list; i < LIST_ARRAY_SIZE; i++) {
1018     dlln = ss->list_array[i];
1019     while (dlln != NULL) {
1020       if (dlln->sb->nslots >= nslots) {
1021         return dlln->sb->startslot;
1022       }
1023       dlln = dlln->next;
1024     }
1025   }
1026
1027   /* return -1 if no such slotblock exists */
1028   return (-1);
1029
1030 }
1031
1032 /*****************************************************************
1033  * Grab a slotblock with the specified range of blocks (nslots blocks
1034  * starting at sslot).  This is different from get_slots because
1035  * grab_slots specifies the slots to be grabbed and actually grabs
1036  * them (removes them from the set of free slots).  get_slots only
1037  * finds a set of free slots.
1038  *****************************************************************/
1039
1040 static void grab_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots) {
1041
1042   CmiInt8 endslot;
1043   slotblock *sb = find_btree_slotblock(ss->btree_root, sslot);
1044
1045   if (sb == NULL) {
1046     CmiAbort("requested a non-existent slotblock\n");
1047   } else {
1048
1049     if (sb->startslot == sslot) {
1050
1051       /* range is exact range of slotblock - delete block from tree */
1052       if (sb->nslots == nslots) {
1053         ss->btree_root = btree_delete(ss, ss->btree_root, sslot);
1054       }
1055
1056       /* range is at beginning of slotblock - update block range */
1057       else {
1058         CmiInt8 old_nslots = sb->nslots;
1059         sb->startslot     += nslots;
1060         sb->nslots        -= nslots;
1061         list_move(ss, sb->listblock, old_nslots);
1062       }
1063
1064     } else {
1065
1066       /* range is at end of slotblock - update block range */
1067       endslot = sb->startslot + sb->nslots - 1;
1068       if (endslot == (sslot + nslots - 1)) {
1069         CmiInt8 old_nslots = sb->nslots;
1070         sb->nslots        -= nslots;
1071         list_move(ss, sb->listblock, old_nslots);
1072       }
1073
1074       /* range is in middle of slotblock - update block range with the */
1075       /* new lower range and insert a block with the new upper range */
1076       else {
1077         CmiInt8 old_nslots = sb->nslots;
1078         sb->nslots         = sslot - sb->startslot;
1079         list_move(ss, sb->listblock, old_nslots);
1080         ss->btree_root = btree_insert(ss, ss->btree_root, sslot + nslots, 
1081             endslot - (sslot + nslots) + 1);
1082       }
1083
1084     }
1085
1086   }
1087
1088 }
1089
1090 /*****************************************************************
1091  * Frees nslots memory slots starting at sslot by either adding them
1092  * to one of the slotblocks that exists (if the slot ranges are
1093  * contiguous) or by creating a new slotblock
1094  *****************************************************************/
1095
1096 static void free_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots) {
1097
1098   slotblock *sb_low  = find_btree_slotblock(ss->btree_root, sslot - 1);
1099   slotblock *sb_high = find_btree_slotblock(ss->btree_root, sslot + nslots);
1100
1101   if (sb_low == NULL) {
1102     if (sb_high == NULL) {
1103
1104       /* there is no adjacent slotblock, so create a new one and */
1105       /* insert it in the b-tree */
1106       ss->btree_root = btree_insert(ss, ss->btree_root, sslot, nslots);
1107
1108     } else {
1109
1110       /* there is an adjacent slotblock to the right, so update its range */
1111       CmiInt8 old_nslots = sb_high->nslots;
1112       sb_high->startslot = sslot;
1113       sb_high->nslots   += nslots;
1114       list_move(ss, sb_high->listblock, old_nslots);
1115
1116     }
1117   } else {
1118     if (sb_high == NULL) {
1119
1120       /* there is an adjacent slotblock to the left, so update its range */
1121       CmiInt8 old_nslots  = sb_low->nslots;
1122       sb_low->nslots     += nslots;
1123       list_move(ss, sb_low->listblock, old_nslots);
1124
1125     } else {
1126
1127       /* there are adjacent slotblocks on both sides (i.e., the
1128          slots to be freed exactly span the gap between 2 slotblocks),
1129          so update the range of the lower slotblock and delete the
1130          upper one */
1131       CmiInt8 old_nslots = sb_low->nslots;
1132       sb_low->nslots     = sb_low->nslots + nslots + sb_high->nslots;
1133       list_move(ss, sb_low->listblock, old_nslots);
1134       ss->btree_root = btree_delete(ss, ss->btree_root, sb_high->startslot);
1135
1136     }
1137   }
1138
1139 }
1140
1141 /*****************************************************************
1142  * Recursively free the allocated memory of the b-tree
1143  *****************************************************************/
1144
1145 static void delete_btree(btreenode *node) {
1146   int i;
1147   for (i = 0; i <= node->num_blocks; i++) {
1148     if (node->child[i] != NULL) {
1149       delete_btree(node->child[i]);
1150       free_reentrant(node->child[i]);
1151     } else {
1152       return;
1153     }
1154   }
1155 }
1156
1157 /*****************************************************************
1158  * Free the allocated memory of the list array
1159  *****************************************************************/
1160
1161 static void delete_list_array(slotset *ss) {
1162   int i;
1163   dllnode *dlln;
1164   for (i = 0; i < LIST_ARRAY_SIZE; i++) {
1165     dlln = ss->list_array[i];
1166     if (dlln != NULL) {
1167       while (dlln->next != NULL) {
1168         dlln = dlln->next;
1169       }
1170       while (dlln->previous != NULL) {
1171         dlln = dlln->previous;
1172         free_reentrant(dlln->next);
1173       }
1174       free_reentrant(dlln);
1175     }
1176   }
1177 }
1178
1179 /*****************************************************************
1180  * Free the allocated memory of the slotset
1181  *****************************************************************/
1182
1183 static void delete_slotset(slotset *ss) {
1184   delete_btree(ss->btree_root);
1185   delete_list_array(ss);
1186   free_reentrant(ss->btree_root);
1187   free_reentrant(ss);
1188 }
1189
1190 /*****************************************************************
1191  * Print the contents of the b-tree on the screen in a top-down
1192  * fashion, starting with the root and progressing to the sub-trees
1193  *****************************************************************/
1194
1195 /* prints the elements in a single b-tree node */
1196 static void print_btree_node(btreenode *node, int node_num) {
1197   int i;
1198   CmiPrintf("Node %2d: ", node_num);
1199   for (i = 0; i < node->num_blocks; i++) {
1200     CmiPrintf("%d:[%lld,%lld] ", i, node->blocks[i].startslot, node->blocks[i].nslots);
1201   }
1202   CmiPrintf("\n");
1203 }
1204
1205 /* returns 1 if there's another level to print; 0 if not */
1206 static int print_btree_level(btreenode *node, int level, int current_level, int node_num) {
1207   int i, another_level;
1208   for (i = 0; i <= node->num_blocks; i++) {
1209     if (current_level == level) {
1210       print_btree_node(node, node_num);
1211       if (node->child[0] == NULL) {
1212         return 0;
1213       } else {
1214         return 1;
1215       }
1216     } else {
1217       another_level = print_btree_level(node->child[i], level, 
1218           current_level + 1, i);
1219     }
1220   }
1221   return another_level;
1222 }
1223
1224 static void print_btree_top_down(btreenode *node) {
1225   int level = 0;
1226   int another_level;
1227   do {
1228     CmiPrintf("B-tree Level %d\n", level);
1229     CmiPrintf("---------------\n");
1230     another_level = print_btree_level(node, level, 0, 0);
1231     level++;
1232     CmiPrintf("\n\n");
1233   } while (another_level);
1234 }
1235
1236 /*****************************************************************
1237  * Print the contents of the list arry on the screen
1238  *****************************************************************/
1239
1240 static void print_list_array(slotset *ss) {
1241   int i;
1242   dllnode *dlln;
1243   CmiPrintf("List Array\n");
1244   CmiPrintf("----------\n");
1245   for (i = 0; i < LIST_ARRAY_SIZE; i++) {
1246     CmiPrintf("List %2d: ", i);
1247     dlln = ss->list_array[i];
1248     while (dlln != NULL) {
1249       if (dlln->previous != NULL) {
1250         CmiPrintf("<->");
1251       } else {
1252         CmiPrintf(" ->");
1253       }
1254       CmiPrintf("[%lld,%lld]", dlln->sb->startslot, dlln->sb->nslots);
1255       dlln = dlln->next;
1256     }
1257     CmiPrintf("\n");
1258   }
1259 }
1260
1261 #if ISOMALLOC_DEBUG
1262 static void print_slots(slotset *ss) {
1263   print_btree_top_down(ss->btree_root);
1264   print_list_array(ss);
1265 }
1266 #else
1267 #  define print_slots(ss) /*empty*/
1268 #endif
1269
1270
1271
1272 /* ======================================================================
1273  * Old isomalloc (array-based implementation)
1274  * ====================================================================== */
1275
1276 #else
1277
1278 typedef struct _slotblock
1279 {
1280   CmiInt8 startslot;
1281   CmiInt8 nslots;
1282 } slotblock;
1283
1284 typedef struct _slotset
1285 {
1286   int maxbuf;
1287   slotblock *buf;
1288   CmiInt8 emptyslots;
1289 } slotset;
1290
1291 /*
1292  * creates a new slotset of nslots entries, starting with all
1293  * empty slots. The slot numbers are [startslot,startslot+nslot-1]
1294  */
1295
1296   static slotset *
1297 new_slotset(CmiInt8 startslot, CmiInt8 nslots)
1298 {
1299   /* CmiPrintf("*** Old isomalloc ***\n"); */
1300   int i;
1301   slotset *ss = (slotset*) malloc_reentrant(sizeof(slotset));
1302   _MEMCHECK(ss);
1303   ss->maxbuf = 16;
1304   ss->buf = (slotblock *) malloc_reentrant(sizeof(slotblock)*ss->maxbuf);
1305   _MEMCHECK(ss->buf);
1306   ss->emptyslots = nslots;
1307   ss->buf[0].startslot = startslot;
1308   ss->buf[0].nslots = nslots;
1309   for (i=1; i<ss->maxbuf; i++)
1310     ss->buf[i].nslots = 0;
1311   return ss;
1312 }
1313
1314 /*
1315  * returns new block of empty slots. if it cannot find any, returns (-1).
1316  */
1317
1318   static CmiInt8
1319 get_slots(slotset *ss, CmiInt8 nslots)
1320 {
1321   /* CmiPrintf("old get: nslots=%lld\n", nslots); */
1322   int i;
1323   if(ss->emptyslots < nslots)
1324     return (-1);
1325   for(i=0;i<(ss->maxbuf);i++)
1326     if(ss->buf[i].nslots >= nslots)
1327       return ss->buf[i].startslot;
1328   return (-1);
1329 }
1330
1331 /* just adds a slotblock to an empty position in the given slotset. */
1332
1333   static void
1334 add_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots)
1335 {
1336   int pos; 
1337   int emptypos = -1;
1338   if (nslots == 0)
1339     return;
1340   for (pos=0; pos < (ss->maxbuf); pos++) {
1341     if (ss->buf[pos].nslots == 0) {
1342       emptypos = pos;
1343       break; /* found empty slotblock */
1344     }
1345   }
1346   if (emptypos == (-1)) /*no empty slotblock found */
1347   {
1348     int i;
1349     int newsize = ss->maxbuf*2;
1350     slotblock *newbuf = (slotblock *) malloc_reentrant(sizeof(slotblock)*newsize);
1351     _MEMCHECK(newbuf);
1352     for (i=0; i<(ss->maxbuf); i++)
1353       newbuf[i] = ss->buf[i];
1354     for (i=ss->maxbuf; i<newsize; i++)
1355       newbuf[i].nslots  = 0;
1356     free_reentrant(ss->buf);
1357     ss->buf = newbuf;
1358     emptypos = ss->maxbuf;
1359     ss->maxbuf = newsize;
1360   }
1361   ss->buf[emptypos].startslot = sslot;
1362   ss->buf[emptypos].nslots = nslots;
1363   ss->emptyslots += nslots;
1364   return;
1365 }
1366
1367 /* grab a slotblock with specified range of blocks
1368  * this is different from get_slots, since it pre-specifies the
1369  * slots to be grabbed.
1370  */
1371   static void
1372 grab_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots)
1373 {
1374   /* CmiPrintf("old grab: sslot=%lld nslots=%lld\n", sslot, nslots); */
1375   CmiInt8 pos, eslot, e;
1376   eslot = sslot + nslots;
1377   for (pos=0; pos < (ss->maxbuf); pos++)
1378   {
1379     if (ss->buf[pos].nslots == 0)
1380       continue;
1381     e = ss->buf[pos].startslot + ss->buf[pos].nslots;
1382     if(sslot >= ss->buf[pos].startslot && eslot <= e)
1383     {
1384       CmiInt8 old_nslots;
1385       old_nslots = ss->buf[pos].nslots;
1386       ss->buf[pos].nslots = sslot - ss->buf[pos].startslot;
1387       ss->emptyslots -= (old_nslots - ss->buf[pos].nslots);
1388       add_slots(ss, sslot + nslots, old_nslots - ss->buf[pos].nslots - nslots);
1389       /* CmiPrintf("grab: sslot=%lld nslots=%lld pos=%lld i=%d\n", sslot, nslots, pos, i); */
1390       return;
1391     }
1392   }
1393   CmiAbort("requested a non-existent slotblock\n");
1394 }
1395
1396 /*
1397  * Frees slot by adding it to one of the blocks of empty slots.
1398  * this slotblock is one which is contiguous with the slots to be freed.
1399  * if it cannot find such a slotblock, it creates a new slotblock.
1400  * If the buffer fills up, it adds up extra buffer space.
1401  */
1402   static void
1403 free_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots)
1404 {
1405   /* CmiPrintf("old free: sslot=%lld nslots=%lld\n", sslot, nslots); */
1406   int pos;
1407   /* eslot is the ending slot of the block to be freed */
1408   CmiInt8 eslot = sslot + nslots;
1409   for (pos=0; pos < (ss->maxbuf); pos++)
1410   {
1411     CmiInt8 e = ss->buf[pos].startslot + ss->buf[pos].nslots;
1412     if (ss->buf[pos].nslots == 0)
1413       continue;
1414     /* e is the ending slot of pos'th slotblock */
1415     if (e == sslot) /* append to the current slotblock */
1416     {
1417       ss->buf[pos].nslots += nslots;
1418       ss->emptyslots += nslots;
1419       /* CmiPrintf("free:append pos=%d\n", pos); */
1420       return;
1421     }
1422     if(eslot == ss->buf[pos].startslot) /* prepend to the current slotblock */
1423     {
1424       ss->buf[pos].startslot = sslot;
1425       ss->buf[pos].nslots += nslots;
1426       ss->emptyslots += nslots;
1427       /* CmiPrintf("free:prepend pos=%d\n", pos); */
1428       return;
1429     }
1430   }
1431   /* if we are here, it means we could not find a slotblock that the */
1432   /* block to be freed was combined with. */
1433   /* CmiPrintf("free: pos=%d\n", pos); */
1434   add_slots(ss, sslot, nslots);
1435 }
1436
1437 /*
1438  * destroys slotset-- currently unused
1439  static void
1440  delete_slotset(slotset* ss)
1441  {
1442  free_reentrant(ss->buf);
1443  free_reentrant(ss);
1444  }
1445  */
1446
1447 #if ISOMALLOC_DEBUG
1448   static void
1449 print_slots(slotset *ss)
1450 {
1451   int i;
1452   CmiPrintf("[%d] maxbuf = %d\n", CmiMyPe(), ss->maxbuf);
1453   CmiPrintf("[%d] emptyslots = %d\n", CmiMyPe(), ss->emptyslots);
1454   for(i=0;i<ss->maxbuf;i++) {
1455     if(ss->buf[i].nslots)
1456       CmiPrintf("[%d] (start[%d], end[%d], num=%d) \n", CmiMyPe(), ss->buf[i].startslot, 
1457           ss->buf[i].startslot+ss->buf[i].nslots, ss->buf[i].nslots);
1458   }
1459 }
1460 #else
1461 /*#  define print_slots(ss) */ /*empty*/
1462   static void
1463 print_slots(slotset *ss)
1464 {
1465   int i;
1466   CmiPrintf("[%d] maxbuf = %d\n", CmiMyPe(), ss->maxbuf);
1467   CmiPrintf("[%d] emptyslots = %d\n", CmiMyPe(), ss->emptyslots);
1468   for(i=0;i<ss->maxbuf;i++) {
1469     if(ss->buf[i].nslots)
1470       CmiPrintf("[%d] (start[%d], end[%d], num=%d) \n", CmiMyPe(), ss->buf[i].startslot, 
1471           ss->buf[i].startslot+ss->buf[i].nslots, ss->buf[i].nslots);
1472   }
1473 }
1474
1475 #endif
1476
1477
1478 #endif
1479
1480 /* ======================= END OLD ISOMALLOC ============================ */
1481
1482
1483 /*This version of the allocate/deallocate calls are used if the 
1484   real mmap versions are disabled.*/
1485 static int disabled_map_warned=0;
1486 static void *disabled_map(int nBytes) 
1487 {
1488   if (!disabled_map_warned) {
1489     disabled_map_warned=1;
1490     if (CmiMyPe()==0)
1491       CmiError("charm isomalloc.c> Warning: since mmap() doesn't work,"
1492           " you won't be able to migrate threads\n");
1493   }
1494   return malloc(nBytes);
1495 }
1496 static void disabled_unmap(void *bk) {
1497   free(bk);
1498 }
1499
1500 /*Turn off isomalloc memory, for the given reason*/
1501 static void disable_isomalloc(const char *why)
1502 {
1503   isomallocStart=NULL;
1504   isomallocEnd=NULL;
1505   if (CmiMyPe() == 0)
1506     CmiPrintf("[%d] isomalloc.c> Disabling isomalloc because %s\n",CmiMyPe(),why);
1507 }
1508
1509 #if ! CMK_HAS_MMAP
1510 /****************** Manipulate memory map (Win32 non-version) *****************/
1511 static void *call_mmap_fixed(void *addr,size_t len) {
1512   CmiAbort("isomalloc.c: mmap_fixed should never be called here.");
1513   return NULL;
1514 }
1515 static void *call_mmap_anywhere(size_t len) {
1516   CmiAbort("isomalloc.c: mmap_anywhere should never be called here.");
1517   return NULL;
1518 }
1519 static void call_munmap(void *addr,size_t len) {
1520   CmiAbort("isomalloc.c: munmap should never be called here.");
1521 }
1522
1523   static int 
1524 init_map(char **argv)
1525 {
1526   return 0; /*Isomalloc never works without mmap*/
1527 }
1528 #else /* CMK_HAS_MMAP */
1529 /****************** Manipulate memory map (UNIX version) *****************/
1530 #include <sys/types.h>
1531 #include <sys/mman.h>
1532 #include <sys/stat.h>
1533 #include <fcntl.h>
1534
1535 #if !CMK_HAS_MMAP_ANON
1536 CpvStaticDeclare(int, zerofd); /*File descriptor for /dev/zero, for mmap*/
1537 #endif
1538
1539 /**
1540  * Maps this address with these flags.
1541  */
1542 static void *call_mmap(void *addr,size_t len, int flags) {
1543   void *ret=mmap(addr, len, PROT_READ|PROT_WRITE,
1544 #if CMK_HAS_MMAP_ANON
1545       flags|MAP_PRIVATE|MAP_ANON,-1,
1546 #else
1547       flags|MAP_PRIVATE,CpvAccess(zerofd),
1548 #endif
1549       0);
1550   if (ret==((void*)(-1))) return (void *)0; /* all-ones means failure */
1551   else return ret;
1552 }
1553 static void *call_mmap_fixed(void *addr,size_t len) {
1554   return call_mmap(addr,len,MAP_FIXED);
1555 }
1556 static void *call_mmap_anywhere(size_t len) {
1557   return call_mmap((void *)0,len,0);
1558 }
1559
1560 /* Unmaps this address range */
1561 static void call_munmap(void *addr,size_t len) {
1562   int retval;
1563   if (addr == 0) return; /* NULL address is never mapped */ 
1564   retval = munmap(addr, len);
1565   if (retval==(-1))
1566     CmiAbort("munmap call failed to deallocate requested memory.\n");
1567 }
1568
1569   static int 
1570 init_map(char **argv)
1571 {
1572 #if CMK_HAS_MMAP_ANON
1573   /*Don't need /dev/zero*/
1574 #else
1575   CpvInitialize(int, zerofd);  
1576   CpvAccess(zerofd) = open("/dev/zero", O_RDWR);
1577   if(CpvAccess(zerofd)<0)
1578     return 0; /* Cannot open /dev/zero or use MMAP_ANON, so can't mmap memory */
1579 #endif
1580   return 1;
1581 }
1582
1583 #endif /* UNIX memory map */
1584
1585 /**
1586  * maps the virtual memory associated with slot using mmap
1587  */
1588   static CmiIsomallocBlock *
1589 map_slots(CmiInt8 slot, CmiInt8 nslots)
1590 {
1591   void *pa;
1592   void *addr=slot2addr(slot);
1593   pa = call_mmap_fixed(addr, slotsize*nslots);
1594
1595   if (pa==NULL)
1596   { /*Map just failed completely*/
1597 #if ISOMALLOC_DEBUG
1598     perror("mmap failed");
1599     CmiPrintf("[%d] tried to mmap %p, but encountered error\n",CmiMyPe(),addr);
1600 #endif
1601     return NULL;
1602   }
1603   if (pa != addr)
1604   { /*Map worked, but gave us back the wrong place*/
1605 #if ISOMALLOC_DEBUG
1606     CmiPrintf("[%d] tried to mmap %p, but got %p back\n",CmiMyPe(),addr,pa);
1607 #endif
1608     call_munmap(addr,slotsize*nslots);
1609     return NULL;
1610   }
1611 #if ISOMALLOC_DEBUG
1612   CmiPrintf("[%d] mmap'd slots %ld-%ld to address %p\n",CmiMyPe(),
1613       slot,slot+nslots-1,addr);
1614 #endif
1615   return (CmiIsomallocBlock *)pa;
1616 }
1617
1618 /*
1619  * unmaps the virtual memory associated with slot using munmap
1620  */
1621   static void
1622 unmap_slots(CmiInt8 slot, CmiInt8 nslots)
1623 {
1624   void *addr=slot2addr(slot);
1625   call_munmap(addr, slotsize*nslots);
1626 #if ISOMALLOC_DEBUG
1627   CmiPrintf("[%d] munmap'd slots %ld-%ld from address %p\n",CmiMyPe(),
1628       slot,slot+nslots-1,addr);
1629 #endif
1630 }
1631
1632 static void map_failed(CmiInt8 s,CmiInt8 n)
1633 {
1634   void *addr=slot2addr(s);
1635   CmiError("charm isomalloc.c> map failed to allocate %d bytes at %p, errno:%d.\n",
1636       slotsize*n, addr, errno);
1637   CmiAbort("Exiting\n");
1638 }
1639
1640
1641
1642 /************ Address space voodoo: find free address range **********/
1643
1644 CpvStaticDeclare(slotset *, myss); /*My managed slots*/
1645
1646 #if CMK_USE_MEMPOOL_ISOMALLOC
1647 CtvDeclare(mempool_type *, threadpool); /*Thread managed pools*/
1648
1649 //alloc function to be used by mempool
1650 void * isomallocfn (size_t *size, mem_handle_t *mem_hndl, int expand_flag)
1651 {
1652   CmiInt8 s,n,i;
1653   void *newaddr;
1654   n=length2slots(*size);
1655   /*Always satisfy mallocs with local slots:*/
1656   s=get_slots(CpvAccess(myss),n);
1657   if (s==-1) {
1658     CmiError("Not enough address space left on processor %d to isomalloc %d bytes!\n",
1659               CmiMyPe(),*size);
1660     CmiAbort("Out of virtual address space for isomalloc");
1661   }
1662   grab_slots(CpvAccess(myss),s,n);
1663   for (i=0; i<5; i++) {
1664     newaddr=map_slots(s,n);
1665     if (newaddr!=NULL) break;
1666 #if CMK_HAS_USLEEP
1667     if (errno == ENOMEM) { usleep(rand()%1000); continue; }
1668     else break;
1669 #endif
1670   }
1671   if (!newaddr) map_failed(s,n);
1672   *((CmiInt8 *)mem_hndl) = s;
1673   *size = n*slotsize;
1674   return newaddr;
1675 }
1676
1677 //free function to be used by mempool
1678 void isofreefn(void *ptr, mem_handle_t mem_hndl)
1679 {
1680   call_munmap(ptr, ((block_header *)ptr)->size);
1681 }
1682 #endif
1683
1684 /*This struct describes a range of virtual addresses*/
1685 typedef struct {
1686   char *start; /*First byte of region*/
1687   memRange_t len; /*Number of bytes in region*/
1688   const char *type; /*String describing memory in region (debugging only)*/
1689 } memRegion_t;
1690
1691 /*Estimate the top of the current stack*/
1692 static void *__cur_stack_frame(void)
1693 {
1694   char __dummy;
1695   void *top_of_stack=(void *)&__dummy;
1696   return top_of_stack;
1697 }
1698 /*Estimate the location of the static data region*/
1699 static void *__static_data_loc(void)
1700 {
1701   static char __dummy;
1702   return (void *)&__dummy;
1703 }
1704
1705 /*Pointer comparison is in these subroutines, because
1706   comparing arbitrary pointers is nonportable and tricky.
1707   */
1708 static int pointer_lt(const char *a,const char *b) {
1709   return ((memRange_t)a)<((memRange_t)b);
1710 }
1711 static int pointer_ge(const char *a,const char *b) {
1712   return ((memRange_t)a)>=((memRange_t)b);
1713 }
1714
1715 static char *pmin(char *a,char *b) {return pointer_lt(a,b)?a:b;}
1716 static char *pmax(char *a,char *b) {return pointer_lt(a,b)?b:a;}
1717
1718 const static memRange_t meg=1024u*1024u; /*One megabyte*/
1719 const static memRange_t gig=1024u*1024u*1024u; /*One gigabyte*/
1720
1721 /*Check if this memory location is usable.  
1722   If not, return 1.
1723   */
1724 static int bad_location(char *loc) {
1725   void *addr;
1726   addr=call_mmap_fixed(loc,slotsize);
1727   if (addr==NULL || addr!=loc) {
1728 #if ISOMALLOC_DEBUG
1729     CmiPrintf("[%d] Skipping unmappable space at %p\n",CmiMyPe(),loc);
1730 #endif
1731     return 1; /*No good*/
1732   }
1733   call_munmap(addr,slotsize);
1734   return 0; /*This works*/
1735 }
1736
1737 /* Split this range up into n pieces, returning the size of each piece */
1738 static memRange_t divide_range(memRange_t len,int n) {
1739   return (len+1)/n;
1740 }
1741
1742 /* Return if this memory region has *any* good parts. */
1743 static int partially_good(char *start,memRange_t len,int n) {
1744   int i;
1745   memRange_t quant=divide_range(len,n);
1746   CmiAssert (quant > 0);
1747   for (i=0;i<n;i++)
1748     if (!bad_location(start+i*quant)) return 1; /* it's got some good parts */
1749   return 0; /* all locations are bad */
1750 }
1751
1752 /* Return if this memory region is usable at n samples.  
1753 */
1754 static int good_range(char *start,memRange_t len,int n) {
1755   int i;
1756   memRange_t quant=divide_range(len,n);
1757 #if ISOMALLOC_DEBUG
1758   CmiPrintf("good_range: %lld, %d\n", quant, n);
1759 #endif
1760   CmiAssert (quant > 0);
1761
1762   for (i=0;i<n;i++)
1763     if (bad_location(start+i*quant)) return 0; /* it's got some bad parts */
1764   /* It's all good: */
1765   return 1;
1766 }
1767
1768 /*Check if this entire memory range, or some subset 
1769   of the range, is usable.  If so, write it into max.
1770   */
1771 static void check_range(char *start,char *end,memRegion_t *max)
1772 {
1773   memRange_t len;
1774   CmiUInt8 tb = (CmiUInt8)gig*1024ul;   /* One terabyte */
1775   CmiUInt8 vm_limit = tb*256ul;   /* terabyte */
1776
1777   if (start>=end) return; /*Ran out of hole*/
1778   len=(memRange_t)end-(memRange_t)start;
1779
1780 #if 0
1781   /* too conservative */
1782   if (len/gig>64u) { /* This is an absurd amount of space-- cut it down, for safety */
1783     start+=16u*gig;
1784     end=start+32u*gig;
1785     len=(memRange_t)end-(memRange_t)start;  
1786   }
1787 #else
1788   /* Note: 256TB == 248 bytes.  So a 48-bit virtual-address CPU 
1789    *    can only actually address 256TB of space. */
1790   if (len/tb>10u) { /* This is an absurd amount of space-- cut it down, for safety */
1791     const memRange_t other_libs=16ul*gig; /* space for other libraries to use */
1792     start+=other_libs;
1793     end=pmin(start+vm_limit-2*other_libs, end-other_libs);
1794     len=(memRange_t)end-(memRange_t)start;
1795   }
1796 #endif
1797   if (len<=max->len) return; /*It's too short already!*/
1798 #if ISOMALLOC_DEBUG
1799   CmiPrintf("[%d] Checking at %p - %p\n",CmiMyPe(),start,end);
1800 #endif
1801
1802   /* Check the middle of the range */
1803   if (!good_range(start,len,256)) {
1804     /* Try to split into subranges: */
1805     int i,n=2;
1806 #if ISOMALLOC_DEBUG
1807     CmiPrintf("[%d] Trying to split bad address space at %p - %p...\n",CmiMyPe(),start,end);
1808 #endif
1809     len=divide_range(len,n);
1810     for (i=0;i<n;i++) {
1811       char *cur=start+i*len;
1812       if (partially_good(cur,len,16))
1813         check_range(cur,cur+len,max);
1814     }
1815     return; /* Hopefully one of the subranges will be any good */
1816   }
1817   else /* range is good */
1818   { 
1819 #if ISOMALLOC_DEBUG
1820     CmiPrintf("[%d] Address space at %p - %p is largest\n",CmiMyPe(),start,end);
1821 #endif
1822
1823     /*If we got here, we're the new largest usable range*/
1824     max->len=len;
1825     max->start=start;
1826     max->type="Unused";
1827   }
1828 }
1829
1830 /*Find the first available memory region of at least the
1831   given size not touching any data in the used list.
1832   */
1833 static memRegion_t find_free_region(memRegion_t *used,int nUsed,int atLeast) 
1834 {
1835   memRegion_t max;
1836   int i,j;  
1837
1838   max.start=0; 
1839   max.len=atLeast;
1840   /*Find the largest hole between regions*/
1841   for (i=0;i<nUsed;i++) {
1842     /*Consider a hole starting at the end of region i*/
1843     char *holeStart=used[i].start+used[i].len;
1844     char *holeEnd=(void *)(-1);
1845
1846     /*Shrink the hole by all others*/ 
1847     for (j=0;j<nUsed && pointer_lt(holeStart,holeEnd);j++) {
1848       if (pointer_lt(used[j].start,holeStart)) 
1849         holeStart=pmax(holeStart,used[j].start+used[j].len);
1850       else if (pointer_lt(used[j].start,holeEnd)) 
1851         holeEnd=pmin(holeEnd,used[j].start);
1852     } 
1853
1854     check_range(holeStart,holeEnd,&max);
1855   }
1856
1857   return max; 
1858 }
1859
1860 /*
1861    By looking at the address range carefully, try to find 
1862    the largest usable free region on the machine.
1863    */
1864 static int find_largest_free_region(memRegion_t *destRegion) {
1865   char *staticData =(char *) __static_data_loc();
1866   char *code = (char *)&find_free_region;
1867   char *threadData = (char *)&errno;
1868   char *codeDll = (char *)fprintf;
1869   char *heapLil = (char*) malloc(1);
1870   char *heapBig = (char*) malloc(6*meg);
1871   char *stack = (char *)__cur_stack_frame();
1872   size_t mmapAnyLen = 1*meg;
1873   char *mmapAny = (char*) call_mmap_anywhere(mmapAnyLen);
1874
1875   int i,nRegions=0;
1876   memRegion_t regions[10]; /*used portions of address space*/
1877   memRegion_t freeRegion; /*Largest unused block of address space*/
1878
1879   /*Mark off regions of virtual address space as ususable*/
1880   regions[nRegions].type="NULL";
1881   regions[nRegions].start=NULL; 
1882 #if CMK_POWER7 && CMK_64BIT
1883   regions[nRegions++].len=2u*gig;   /* on bluedrop, don't mess with the lower memory region */
1884 #else
1885   regions[nRegions++].len=16u*meg;
1886 #endif
1887
1888   regions[nRegions].type="Static program data";
1889   regions[nRegions].start=staticData; regions[nRegions++].len=256u*meg;
1890
1891   regions[nRegions].type="Program executable code";
1892   regions[nRegions].start=code; regions[nRegions++].len=256u*meg;
1893
1894   regions[nRegions].type="Heap (small blocks)";
1895   regions[nRegions].start=heapLil; regions[nRegions++].len=1u*gig;
1896
1897   regions[nRegions].type="Heap (large blocks)";
1898   regions[nRegions].start=heapBig; regions[nRegions++].len=1u*gig;
1899
1900   regions[nRegions].type="Stack space";
1901   regions[nRegions].start=stack; regions[nRegions++].len=256u*meg;
1902
1903   regions[nRegions].type="Program dynamically linked code";
1904   regions[nRegions].start=codeDll; regions[nRegions++].len=256u*meg; 
1905
1906   regions[nRegions].type="Result of a non-fixed call to mmap";
1907   regions[nRegions].start=mmapAny; regions[nRegions++].len=2u*gig; 
1908
1909   regions[nRegions].type="Thread private data";
1910   regions[nRegions].start=threadData; regions[nRegions++].len=256u*meg; 
1911
1912   _MEMCHECK(heapBig); free(heapBig);
1913   _MEMCHECK(heapLil); free(heapLil); 
1914   call_munmap(mmapAny,mmapAnyLen);
1915
1916   /*Align each memory region*/
1917   for (i=0;i<nRegions;i++) {
1918     memRegion_t old=regions[i];
1919     memRange_t p=(memRange_t)regions[i].start;
1920     p&=~(regions[i].len-1); /*Round start down to a len-boundary (mask off low bits)*/
1921     regions[i].start=(char *)p;
1922 #if CMK_MACOSX
1923     if (regions[i].start+regions[i].len*2>regions[i].start) regions[i].len *= 2;
1924 #endif
1925 #if ISOMALLOC_DEBUG
1926     CmiPrintf("[%d] Memory map: %p - %p (len: %lu => %lu) %s \n",CmiMyPe(),
1927         regions[i].start,regions[i].start+regions[i].len,
1928         old.len, regions[i].len, regions[i].type);
1929 #endif
1930   }
1931
1932   /*Find a large, unused region in this map: */
1933   freeRegion=find_free_region(regions,nRegions,(512u)*meg);
1934
1935   if (freeRegion.start==0) 
1936   { /*No free address space-- disable isomalloc:*/
1937     return 0;
1938   }
1939   else /* freeRegion is valid */
1940   {
1941     *destRegion=freeRegion;
1942
1943     return 1;
1944   }
1945 }
1946
1947 static int try_largest_mmap_region(memRegion_t *destRegion)
1948 {
1949   void *bad_alloc=(void*)(-1); /* mmap error return address */
1950   void *range, *good_range=NULL;
1951   double shrink = 1.5;
1952   static int count = 0;
1953   size_t size=((size_t)(-1l)), good_size=0;
1954   int retry = 0;
1955   if (sizeof(size_t) >= 8) size = size>>2;  /* 25% of machine address space! */
1956   while (1) { /* test out an allocation of this size */
1957 #if CMK_HAS_MMAP
1958     range=mmap(NULL,size,PROT_READ|PROT_WRITE,
1959         MAP_PRIVATE
1960 #if CMK_HAS_MMAP_ANON
1961         |MAP_ANON
1962 #endif
1963 #if CMK_HAS_MMAP_NORESERVE
1964         |MAP_NORESERVE
1965 #endif
1966         ,-1,0);
1967 #else
1968     range = bad_alloc;
1969 #endif
1970     if (range == bad_alloc) {  /* mmap failed */
1971 #if ISOMALLOC_DEBUG
1972       /* CmiPrintf("[%d] test failed at size: %llu error: %d\n", CmiMyPe(), size, errno);  */
1973 #endif
1974 #if CMK_HAS_USLEEP
1975       if (retry++ < 5) { usleep(rand()%10000); continue; }
1976       else retry = 0;
1977 #endif
1978       size=(double)size/shrink; /* shrink request */
1979       if (size<=0) return 0; /* mmap doesn't work */
1980     }
1981     else { /* this allocation size is available */
1982 #if ISOMALLOC_DEBUG
1983       CmiPrintf("[%d] available: %p, %lld\n", CmiMyPe(), range, size);
1984 #endif
1985       call_munmap(range,size); /* needed/wanted? */
1986       if (size > good_size) {
1987         good_range = range;
1988         good_size = size;
1989         size=((double)size)*1.1;
1990         continue;
1991       }
1992       break;
1993     }
1994   }
1995   CmiAssert(good_range!=NULL);
1996   destRegion->start=good_range; 
1997   destRegion->len=good_size;
1998 #if ISOMALLOC_DEBUG
1999   pid_t pid = getpid();
2000   {
2001     char s[128];
2002     sprintf(s, "cat /proc/%d/maps", pid);
2003     system(s);
2004   }
2005   CmiPrintf("[%d] try_largest_mmap_region: %p, %lld\n", CmiMyPe(), good_range, good_size);
2006 #endif
2007   return 1;
2008 }
2009
2010 #ifndef CMK_CPV_IS_SMP
2011 #define CMK_CPV_IS_SMP
2012 #endif
2013
2014 static void init_ranges(char **argv)
2015 {
2016   memRegion_t freeRegion;
2017   /*Largest value a signed int can hold*/
2018   memRange_t intMax=(((memRange_t)1)<<(sizeof(int)*8-1))-1;
2019   int pagesize = 0;
2020
2021   /*Round slot size up to nearest page size*/
2022 #if CMK_USE_MEMPOOL_ISOMALLOC
2023   slotsize=1024*1024;
2024 #else
2025   slotsize=16*1024;
2026 #endif 
2027 #if CMK_HAS_GETPAGESIZE
2028   pagesize = getpagesize();
2029 #endif
2030   if (pagesize < CMK_MEMORY_PAGESIZE)
2031     pagesize = CMK_MEMORY_PAGESIZE;
2032   slotsize=(slotsize+pagesize-1) & ~(pagesize-1);
2033
2034 //#if ISOMALLOC_DEBUG
2035   if (CmiMyPe() == 0)
2036     CmiPrintf("[%d] Using slotsize of %d\n", CmiMyPe(), slotsize);
2037 //#endif
2038   freeRegion.len=0u;
2039
2040   if (CmiMyRank()==0 && numslots==0)
2041   { /* Find the largest unused region of virtual address space */
2042 #ifdef CMK_MMAP_START_ADDRESS /* Hardcoded start address, for machines where automatic fails */
2043     freeRegion.start=CMK_MMAP_START_ADDRESS;
2044     freeRegion.len=CMK_MMAP_LENGTH_MEGS*meg;
2045 #endif
2046
2047     if (freeRegion.len==0u)  {
2048       if (_mmap_probe == 1) {
2049         if (try_largest_mmap_region(&freeRegion)) _sync_iso = 1;
2050       }
2051       else {
2052         if (freeRegion.len==0u) find_largest_free_region(&freeRegion);
2053       }
2054     }
2055
2056 #if 0
2057     /*Make sure our largest slot number doesn't overflow an int:*/
2058     if (freeRegion.len/slotsize>intMax)
2059       freeRegion.len=intMax*slotsize;
2060 #endif
2061
2062     if (freeRegion.len==0u) {
2063       disable_isomalloc("no free virtual address space");
2064     }
2065     else /* freeRegion.len>0, so can isomalloc */
2066     {
2067 //#if ISOMALLOC_DEBUG
2068       CmiPrintf("[%d] Isomalloc memory region: %p - %p (%d megs)\n",CmiMyPe(),
2069           freeRegion.start,freeRegion.start+freeRegion.len,
2070           freeRegion.len/meg);
2071 //#endif
2072     }
2073   }             /* end if myrank == 0 */
2074 CmiPrintf("before barrier\n");
2075 #ifdef __FAULT__
2076   CmiNodeAllBarrier();
2077 #else 
2078   CmiNodeAllBarrier();
2079 #endif
2080 CmiPrintf("after barrier\n");
2081   /*
2082      on some machines, isomalloc memory regions on different nodes 
2083      can be different. use +isomalloc_sync to calculate the
2084      intersect of all memory regions on all nodes.
2085      */
2086   if (_sync_iso == 1)
2087   {
2088 #ifdef __FAULT__
2089         if(_restart == 1){
2090             CmiUInt8 s = (CmiUInt8)freeRegion.start;
2091             CmiUInt8 e = (CmiUInt8)(freeRegion.start+freeRegion.len);
2092             CmiUInt8 ss, ee;
2093             int try_count, fd;
2094             char fname[128];
2095             sprintf(fname,".isomalloc");
2096             try_count = 0;
2097             while ((fd = open(fname, O_RDONLY)) == -1 && try_count<10000){
2098                 try_count++;
2099             }
2100             if (fd == -1) {
2101                 CmiAbort("isomalloc_sync failed during restart, make sure you have a shared file system.");
2102             }
2103             read(fd, &ss, sizeof(CmiUInt8));
2104             read(fd, &ee, sizeof(CmiUInt8));
2105             close(fd);
2106             if (ss < s || ee > e)
2107                 CmiAbort("isomalloc_sync failed during restart, virtual memory regions do not overlap.");
2108             else {
2109                 freeRegion.start = (void *)ss;
2110                 freeRegion.len = (char *)ee -(char *)ss;
2111             }
2112             CmiPrintf("[%d] consolidated Isomalloc memory region at restart: %p - %p (%d megs)\n",CmiMyPe(),freeRegion.start,freeRegion.start+freeRegion.len,freeRegion.len/meg);
2113             goto AFTER_SYNC;
2114         }
2115 #endif
2116     CmiPrintf("before cmibarrier\n");
2117         if (CmiMyRank() == 0 && freeRegion.len > 0u) {
2118         CmiPrintf("before cmibarrier test\n");
2119       if (CmiBarrier() == -1 && CmiMyPe()==0) 
2120         CmiAbort("Charm++ Error> +isomalloc_sync requires CmiBarrier() implemented.\n");
2121       else
2122           {
2123         CmiUInt8 s = (CmiUInt8)freeRegion.start;
2124         CmiUInt8 e = (CmiUInt8)(freeRegion.start+freeRegion.len);
2125         int fd, i;
2126         char fname[128];
2127
2128         if (CmiMyNode()==0) printf("Charm++> synchronizing isomalloc memory region...\n");
2129
2130         sprintf(fname,".isomalloc.%d", CmiMyNode());
2131
2132         /* remove file before writing for safe */
2133         unlink(fname);
2134 #if CMK_HAS_SYNC && ! CMK_DISABLE_SYNC
2135         system("sync");
2136 #endif
2137
2138         CmiBarrier();
2139
2140         /* write region into file */
2141         while ((fd = open(fname, O_WRONLY|O_TRUNC|O_CREAT, 0644)) == -1) 
2142 #ifndef __MINGW_H
2143           CMK_CPV_IS_SMP
2144 #endif
2145             ;
2146         write(fd, &s, sizeof(CmiUInt8));
2147         write(fd, &e, sizeof(CmiUInt8));
2148         close(fd);
2149
2150 #if CMK_HAS_SYNC && ! CMK_DISABLE_SYNC
2151         system("sync");
2152 #endif
2153
2154         CmiBarrier();
2155
2156         for (i=0; i<CmiNumNodes(); i++) {
2157           CmiUInt8 ss, ee; 
2158           int try_count;
2159           char fname[128];
2160           if (i==CmiMyNode()) continue;
2161           sprintf(fname,".isomalloc.%d", i);
2162           try_count = 0;
2163           while ((fd = open(fname, O_RDONLY)) == -1 && try_count<10000)
2164           {
2165             try_count++;
2166 #ifndef __MINGW_H
2167             CMK_CPV_IS_SMP
2168 #endif
2169               ;
2170           }
2171           if (fd == -1) {
2172             CmiAbort("isomalloc_sync failed, make sure you have a shared file system.");
2173           }
2174           read(fd, &ss, sizeof(CmiUInt8));
2175           read(fd, &ee, sizeof(CmiUInt8));
2176 //#if ISOMALLOC_DEBUG
2177           if (CmiMyPe() == 0) CmiPrintf("[%d] load node %d isomalloc region: %lx %lx. \n",
2178               CmiMyPe(), i, ss, ee);
2179 //#endif
2180           close(fd);
2181           if (ss>s) s = ss;
2182           if (ee<e) e = ee;
2183         }
2184
2185         CmiBarrier();
2186
2187         unlink(fname);
2188 #if CMK_HAS_SYNC && ! CMK_DISABLE_SYNC
2189         system("sync");
2190 #endif
2191
2192         /* update */
2193         if (s > e)  {
2194           if (CmiMyPe()==0) CmiPrintf("[%d] Invalid isomalloc region: %lx - %lx.\n", CmiMyPe(), s, e);
2195           CmiAbort("isomalloc> failed to find consolidated isomalloc region!");
2196         }
2197         freeRegion.start = (void *)s;
2198         freeRegion.len = (char *)e -(char *)s;
2199
2200         if (CmiMyPe() == 0)
2201           CmiPrintf("[%d] consolidated Isomalloc memory region: %p - %p (%d megs)\n",CmiMyPe(),
2202               freeRegion.start,freeRegion.start+freeRegion.len,
2203               freeRegion.len/meg);
2204 #if __FAULT__
2205                 if(CmiMyPe() == 0){
2206                     int fd;
2207                     char fname[128];
2208                     CmiUInt8 s = (CmiUInt8)freeRegion.start;
2209                     CmiUInt8 e = (CmiUInt8)(freeRegion.start+freeRegion.len);
2210                     sprintf(fname,".isomalloc");
2211                     while ((fd = open(fname, O_WRONLY|O_TRUNC|O_CREAT, 0644)) == -1);
2212                     write(fd, &s, sizeof(CmiUInt8));
2213                     write(fd, &e, sizeof(CmiUInt8));
2214                     close(fd);
2215                 }
2216 #endif
2217       }   /* end of barrier test */
2218           CmiPrintf("end of rank0\n");
2219     } /* end of rank 0 */
2220     else {
2221           CmiPrintf("another branch\n");
2222       CmiBarrier();
2223       CmiBarrier();
2224       CmiBarrier();
2225       CmiBarrier();
2226     }
2227   }
2228
2229 #ifdef __FAULT__
2230     AFTER_SYNC:
2231 #endif
2232
2233   if (CmiMyRank() == 0 && freeRegion.len > 0u)
2234   {
2235     /*Isomalloc covers entire unused region*/
2236     isomallocStart=freeRegion.start;
2237     isomallocEnd=freeRegion.start+freeRegion.len;
2238     numslots=(freeRegion.len/slotsize)/CmiNumPes();
2239
2240 //#if ISOMALLOC_DEBUG
2241     CmiPrintf("[%d] Can isomalloc up to %lu megs per pe\n",CmiMyPe(),
2242         ((memRange_t)numslots)*slotsize/meg);
2243 //#endif
2244   }
2245
2246   /*SMP Mode: wait here for rank 0 to initialize numslots before calculating myss*/
2247   CmiNodeAllBarrier(); 
2248
2249   CpvInitialize(slotset *, myss);
2250   CpvAccess(myss) = NULL;
2251
2252 #if CMK_USE_MEMPOOL_ISOMALLOC
2253   CtvInitialize(mempool_type *, threadpool);
2254   CtvAccess(threadpool) = NULL;
2255 #endif
2256
2257   if (isomallocStart!=NULL) {
2258     CpvAccess(myss) = new_slotset(pe2slot(CmiMyPe()), numslots);
2259   }
2260 }
2261
2262
2263 /************* Communication: for grabbing/freeing remote slots *********/
2264 typedef struct _slotmsg
2265 {
2266   char cmicore[CmiMsgHeaderSizeBytes];
2267   int pe; /*Source processor*/
2268   CmiInt8 slot; /*First requested slot*/
2269   CmiInt8 nslots; /*Number of requested slots*/
2270 } slotmsg;
2271
2272 static slotmsg *prepare_slotmsg(CmiInt8 slot,CmiInt8 nslots)
2273 {
2274   slotmsg *m=(slotmsg *)CmiAlloc(sizeof(slotmsg));
2275   m->pe=CmiMyPe();
2276   m->slot=slot;
2277   m->nslots=nslots;
2278   return m;
2279 }
2280
2281 static void grab_remote(slotmsg *msg)
2282 {
2283   grab_slots(CpvAccess(myss),msg->slot,msg->nslots);
2284   CmiFree(msg);
2285 }
2286
2287 static void free_remote(slotmsg *msg)
2288 {
2289   free_slots(CpvAccess(myss),msg->slot,msg->nslots);
2290   CmiFree(msg);
2291 }
2292 static int grab_remote_idx, free_remote_idx;
2293
2294 struct slotOP {
2295   /*Function pointer to perform local operation*/
2296   void (*local)(slotset *ss,CmiInt8 s,CmiInt8 n);
2297   /*Index to perform remote operation*/
2298   int remote;
2299 };
2300 typedef struct slotOP slotOP;
2301 static slotOP grabOP,freeOP;
2302
2303 static void init_comm(char **argv)
2304 {
2305   grab_remote_idx=CmiRegisterHandler((CmiHandler)grab_remote);
2306   free_remote_idx=CmiRegisterHandler((CmiHandler)free_remote);  
2307   grabOP.local=grab_slots;
2308   grabOP.remote=grab_remote_idx;
2309   freeOP.local=free_slots;
2310   freeOP.remote=free_remote_idx;        
2311 }
2312
2313 /*Apply the given operation to the given slots which
2314   lie on the given processor.*/
2315 static void one_slotOP(const slotOP *op,int pe,CmiInt8 s,CmiInt8 n)
2316 {
2317   /*Shrink range to only those covered by this processor*/
2318   /*First and last slot for this processor*/
2319   CmiInt8 p_s=pe2slot(pe), p_e=pe2slot(pe+1);
2320   CmiInt8 e=s+n;
2321   if (s<p_s) s=p_s;
2322   if (e>p_e) e=p_e;
2323   n=e-s;
2324
2325   /*Send off range*/
2326   if (pe==CmiMyPe()) 
2327     op->local(CpvAccess(myss),s,n);
2328   else 
2329   {/*Remote request*/
2330     slotmsg *m=prepare_slotmsg(s,n);
2331     CmiSetHandler(m, freeOP.remote);
2332     CmiSyncSendAndFree(pe,sizeof(slotmsg),m);
2333   }
2334 }
2335
2336 /*Apply the given operation to all slots in the range [s, s+n) 
2337   After a restart from checkpoint, a slotset can cross an 
2338   arbitrary set of processors.
2339   */
2340 static void all_slotOP(const slotOP *op,CmiInt8 s,CmiInt8 n)
2341 {
2342   int spe=slot2pe(s), epe=slot2pe(s+n-1);
2343   int pe;
2344   for (pe=spe; pe<=epe; pe++)
2345     one_slotOP(op,pe,s,n);
2346 }
2347
2348 /************** External interface ***************/
2349 #if CMK_USE_MEMPOOL_ISOMALLOC
2350 void *CmiIsomalloc(int size, CthThread tid)
2351 {
2352   CmiInt8 s,n,i;
2353   CmiIsomallocBlock *blk;
2354   if (isomallocStart==NULL) return disabled_map(size);
2355   if(tid != NULL) {
2356     if(CtvAccessOther(tid,threadpool) == NULL) {
2357 #if ISOMALLOC_DEBUG
2358       printf("Init Mempool in %d for %d\n",CthSelf(), tid);
2359 #endif
2360       CtvAccessOther(tid,threadpool) = mempool_init(2*(size+sizeof(CmiIsomallocBlock)+sizeof(mempool_header))+sizeof(mempool_type), isomallocfn, isofreefn,0);
2361     }
2362     blk = (CmiIsomallocBlock*)mempool_malloc(CtvAccessOther(tid,threadpool),size+sizeof(CmiIsomallocBlock),1);
2363   } else {
2364     if(CtvAccess(threadpool) == NULL) {
2365 #if ISOMALLOC_DEBUG
2366       printf("Init Mempool in %d\n",CthSelf());
2367 #endif
2368       CtvAccess(threadpool) = mempool_init(2*(size+sizeof(CmiIsomallocBlock)+sizeof(mempool_header))+sizeof(mempool_type), isomallocfn, isofreefn,0);
2369     }
2370     blk = (CmiIsomallocBlock*)mempool_malloc(CtvAccess(threadpool),size+sizeof(CmiIsomallocBlock),1);
2371   }
2372   blk->slot=(CmiInt8)blk;
2373   blk->length=size;
2374   return block2pointer(blk);
2375 }
2376 #else
2377 void *CmiIsomalloc(int size, CthThread tid)
2378 {
2379   CmiInt8 s,n,i;
2380   CmiIsomallocBlock *blk;
2381   if (isomallocStart==NULL) return disabled_map(size);
2382   n=length2slots(size);
2383   /*Always satisfy mallocs with local slots:*/
2384   s=get_slots(CpvAccess(myss),n);
2385   if (s==-1) {
2386     CmiError("Not enough address space left on processor %d to isomalloc %d bytes!\n",
2387         CmiMyPe(),size);
2388     CmiAbort("Out of virtual address space for isomalloc");
2389   }
2390   grab_slots(CpvAccess(myss),s,n);
2391   for (i=0; i<5; i++) {
2392     blk=map_slots(s,n);
2393     if (blk!=NULL) break;
2394 #if CMK_HAS_USLEEP
2395     if (errno == ENOMEM) { usleep(rand()%1000); continue; }
2396     else break;
2397 #endif
2398   }
2399   if (!blk) map_failed(s,n);
2400   blk->slot=s;
2401   blk->length=size;
2402   return block2pointer(blk);
2403 }
2404 #endif
2405
2406 #define MALLOC_ALIGNMENT           (2*sizeof(size_t))
2407 #define MINSIZE                    (sizeof(CmiIsomallocBlock))
2408
2409 /** return an aligned isomalloc memory, the alignment occurs after the
2410  *  first 'reserved' bytes.  Total requested size is (size+reserved)
2411  */
2412 static void *_isomallocAlign(size_t align, size_t size, size_t reserved, CthThread t) {
2413   void *ptr;
2414   CmiIntPtr ptr2align;
2415   CmiInt8 s;
2416
2417   if (align < MINSIZE) align = MINSIZE;
2418   /* make sure alignment is power of 2 */
2419   if ((align & (align - 1)) != 0) {
2420     size_t a = MALLOC_ALIGNMENT * 2;
2421     while ((unsigned long)a < (unsigned long)align) a <<= 1;
2422     align = a;
2423   }
2424   s = size + reserved + align;
2425   ptr = CmiIsomalloc(s,t);
2426   ptr2align = (CmiIntPtr)ptr;
2427   ptr2align += reserved;
2428   if (ptr2align % align != 0) { /* misaligned */
2429     CmiIsomallocBlock *blk = pointer2block(ptr);  /* save block */
2430     CmiIsomallocBlock savedblk = *blk;
2431     ptr2align = (ptr2align + align - 1) & -((CmiInt8) align);
2432     ptr2align -= reserved;
2433     ptr = (void*)ptr2align;
2434     blk = pointer2block(ptr);      /* restore block */
2435     *blk = savedblk;
2436   }
2437   return ptr;
2438 }
2439
2440 void *CmiIsomallocAlign(size_t align, size_t size, CthThread t)
2441 {
2442   return _isomallocAlign(align, size, 0, t);
2443 }
2444
2445 int CmiIsomallocEnabled()
2446 {
2447   return (isomallocStart!=NULL);
2448 }
2449
2450 void CmiIsomallocPup(pup_er p,void **blockPtrPtr)
2451 {
2452   CmiIsomallocBlock *blk;
2453   CmiInt8 s,length;
2454   CmiInt8 n;
2455 #if CMK_USE_MEMPOOL_ISOMALLOC
2456   CmiAbort("Incorrect pup is called\n");
2457 #endif
2458   if (isomallocStart==NULL) CmiAbort("isomalloc is disabled-- cannot use IsomallocPup");
2459
2460   if (!pup_isUnpacking(p)) 
2461   { /*We have an existing block-- unpack start slot & length*/
2462     blk=pointer2block(*blockPtrPtr);
2463     s=blk->slot;
2464     length=blk->length;
2465   }
2466
2467   pup_int8(p,&s);
2468   pup_int8(p,&length);
2469   n=length2slots(length);
2470
2471   if (pup_isUnpacking(p)) 
2472   { /*Must allocate a new block in its old location*/
2473     if (pup_isUserlevel(p) || pup_isRestarting(p))
2474     {   /*Checkpoint: must grab old slots (even remote!)*/
2475       all_slotOP(&grabOP,s,n);
2476     }
2477     blk=map_slots(s,n);
2478     if (!blk) map_failed(s,n);
2479     blk->slot=s;
2480     blk->length=length;
2481     *blockPtrPtr=block2pointer(blk);
2482   }
2483
2484   /*Pup the allocated data*/
2485   pup_bytes(p,*blockPtrPtr,length);
2486
2487   if (pup_isDeleting(p)) 
2488   { /*Unmap old slots, but do not mark as free*/
2489     unmap_slots(s,n);
2490     *blockPtrPtr=NULL; /*Zero out user's pointer*/
2491   }
2492 }
2493
2494 void CmiIsomallocFree(void *blockPtr)
2495 {
2496   if (isomallocStart==NULL) {
2497     disabled_unmap(blockPtr);
2498   }
2499   else if (blockPtr!=NULL)
2500   {
2501 #if CMK_USE_MEMPOOL_ISOMALLOC
2502     mempool_free_thread((void*)pointer2block(blockPtr)->slot);
2503 #else
2504     CmiIsomallocBlock *blk=pointer2block(blockPtr);
2505     CmiInt8 s=blk->slot; 
2506     CmiInt8 n=length2slots(blk->length);
2507     unmap_slots(s,n);
2508     /*Mark used slots as free*/
2509     all_slotOP(&freeOP,s,n);
2510 #endif
2511   }
2512 }
2513
2514 CmiInt8  CmiIsomallocLength(void *block)
2515 {
2516   return pointer2block(block)->length;
2517 }
2518
2519 /*Return true if this address is in the region managed by isomalloc*/
2520 int CmiIsomallocInRange(void *addr)
2521 {
2522   if (isomallocStart==NULL) return 0; /* There is no range we manage! */
2523   return pointer_ge((char *)addr,isomallocStart) && 
2524     pointer_lt((char*)addr,isomallocEnd);
2525 }
2526
2527 void CmiIsomallocInit(char **argv)
2528 {
2529 #if CMK_NO_ISO_MALLOC
2530   disable_isomalloc("isomalloc disabled by conv-mach");
2531 #else
2532   if (CmiGetArgFlagDesc(argv,"+noisomalloc","disable isomalloc")) {
2533     disable_isomalloc("isomalloc disabled by user.");
2534     return;
2535   }
2536 #if CMK_MMAP_PROBE
2537   _mmap_probe = 1;
2538 #elif CMK_MMAP_TEST
2539   _mmap_probe = 0;
2540 #endif
2541   if (CmiGetArgFlagDesc(argv,"+isomalloc_probe","call mmap to probe the largest available isomalloc region"))
2542     _mmap_probe = 1;
2543   if (CmiGetArgFlagDesc(argv,"+isomalloc_test","mmap test common areas for the largest available isomalloc region"))
2544     _mmap_probe = 0;
2545   if (CmiGetArgFlagDesc(argv,"+isomalloc_sync","synchronize isomalloc region globaly"))
2546     _sync_iso = 1;
2547 #if __FAULT__
2548   int resPhase;
2549   if (CmiGetArgFlagDesc(argv,"+restartisomalloc","restarting isomalloc on this processor after a crash"))
2550     _restart = 1;
2551 #endif
2552   init_comm(argv);
2553   if (!init_map(argv)) {
2554     disable_isomalloc("mmap() does not work");
2555   }
2556   else {
2557     if (CmiMyPe() == 0) {
2558       if (read_randomflag() == 1) {    /* randomization stack pointer */
2559         if (_sync_iso == 1)
2560           printf("Warning> Randomization of stack pointer is turned on in kernel.\n");
2561         else
2562           printf("Warning> Randomization of stack pointer is turned on in kernel, thread migration may not work! Run 'echo 0 > /proc/sys/kernel/randomize_va_space' as root to disable it, or try run with '+isomalloc_sync'.  \n");
2563       }
2564     }
2565     init_ranges(argv);
2566   }
2567 #endif
2568 }
2569
2570 /***************** BlockList interface *********
2571   This was moved here from memory-isomalloc.c when it 
2572   was realized that a list-of-isomalloc'd-blocks is useful for
2573   more than just isomalloc heaps.
2574   */
2575
2576 /*Convert a slot to a user address*/
2577 static char *Slot_toUser(CmiIsomallocBlockList *s) {return (char *)(s+1);}
2578 static CmiIsomallocBlockList *Slot_fmUser(void *s) {return ((CmiIsomallocBlockList *)s)-1;}
2579
2580 /*Build a new blockList.*/
2581 CmiIsomallocBlockList *CmiIsomallocBlockListNew(CthThread tid)
2582 {
2583   CmiIsomallocBlockList *ret;
2584   ret=(CmiIsomallocBlockList *)CmiIsomalloc(sizeof(*ret),tid);
2585   ret->next=ret; /*1-entry circular linked list*/
2586   ret->prev=ret;
2587   return ret;
2588 }
2589
2590 /* BIGSIM_OOC DEBUGGING */
2591 static void print_myslots();
2592
2593 /*Pup all the blocks in this list.  This amounts to two circular
2594   list traversals.  Because everything's isomalloc'd, we don't even
2595   have to restore the pointers-- they'll be restored automatically!
2596   */
2597 #if CMK_USE_MEMPOOL_ISOMALLOC
2598 void CmiIsomallocBlockListPup(pup_er p,CmiIsomallocBlockList **lp, CthThread tid)
2599 {
2600   mempool_type *mptr;
2601   block_header *current, *block_head;
2602   slot_header *currSlot;
2603   void *newblock;
2604   CmiInt8 slot;
2605   size_t size;
2606   int flags[2];
2607   int i, j;
2608   int numBlocks = 0, numSlots = 0, flag = 1;
2609
2610 #if ISOMALLOC_DEBUG
2611   printf("[%d] My rank is %lld Pupping for %lld with isUnpack %d isDelete %d \n",CmiMyPe(),CthSelf(),tid,pup_isUnpacking(p),pup_isDeleting(p));
2612 #endif
2613   flags[0] = 0; flags[1] = 1;
2614   if(!pup_isUnpacking(p)) {
2615     mptr = CtvAccessOther(tid,threadpool);
2616     current = MEMPOOL_GetBlockHead(mptr);
2617     while(current != NULL) {
2618       numBlocks++;
2619       current = MEMPOOL_GetBlockNext(current)?(block_header *)((char*)mptr+MEMPOOL_GetBlockNext(current)):NULL;
2620     }
2621 #if ISOMALLOC_DEBUG
2622     printf("Number of blocks packed %d\n",numBlocks);
2623 #endif
2624     pup_int(p,&numBlocks);
2625     current = MEMPOOL_GetBlockHead(mptr);
2626     while(current != NULL) {
2627       pup_bytes(p,&(MEMPOOL_GetBlockSize(current)),sizeof(MEMPOOL_GetBlockSize(current)));
2628       pup_bytes(p,&(MEMPOOL_GetBlockMemHndl(current)),sizeof(CmiInt8));
2629       numSlots = 0;
2630       if(flag) {
2631         pup_bytes(p,current,sizeof(mempool_type));
2632         currSlot = (slot_header*)((char*)current+sizeof(mempool_type));
2633       } else {
2634         pup_bytes(p,current,sizeof(block_header));
2635         currSlot = (slot_header*)((char*)current+sizeof(block_header));
2636       }
2637       while(currSlot != NULL) {
2638         numSlots++;
2639         currSlot = (MEMPOOL_GetSlotGNext(currSlot))?(slot_header*)((char*)mptr+MEMPOOL_GetSlotGNext(currSlot)):NULL;
2640       }
2641       pup_int(p,&numSlots);
2642       if(flag) {
2643         currSlot = (slot_header*)((char*)current+sizeof(mempool_type));
2644         flag = 0;
2645       } else {
2646         currSlot = (slot_header*)((char*)current+sizeof(block_header));
2647       }
2648       while(currSlot != NULL) {
2649         pup_int(p,&cutOffPoints[currSlot->size]);
2650         if(MEMPOOL_GetSlotStatus(currSlot)) {
2651           pup_int(p,&flags[0]);
2652           pup_bytes(p,(void*)currSlot,sizeof(slot_header));
2653         } else {
2654           pup_int(p,&flags[1]);
2655           pup_bytes(p,(void*)currSlot,MEMPOOL_GetSlotSize(currSlot));
2656         }
2657         currSlot = (MEMPOOL_GetSlotGNext(currSlot))?(slot_header*)((char*)mptr+MEMPOOL_GetSlotGNext(currSlot)):NULL;
2658       }
2659       current = (MEMPOOL_GetBlockNext(current))?(block_header *)((char*)mptr+MEMPOOL_GetBlockNext(current)):NULL;
2660     }
2661   }
2662
2663   if(pup_isUnpacking(p)) {
2664     pup_int(p,&numBlocks);
2665 #if ISOMALLOC_DEBUG
2666     printf("Number of blocks to be unpacked %d\n",numBlocks);
2667 #endif
2668     for(i = 0; i < numBlocks; i++) { 
2669       pup_bytes(p,&size,sizeof(size));
2670       pup_bytes(p,&slot,sizeof(slot));
2671       newblock = map_slots(slot,size/slotsize);
2672       if(flag) {
2673         mptr = (mempool_type*)newblock;
2674         pup_bytes(p,newblock,sizeof(mempool_type));
2675         newblock = (char*)newblock + sizeof(mempool_type);
2676         flag = 0;
2677       } else {
2678         pup_bytes(p,newblock,sizeof(block_header));
2679         newblock = (char*)newblock + sizeof(block_header);
2680       }
2681       pup_int(p,&numSlots);
2682       for(j=0; j < numSlots; j++) {
2683         pup_int(p,&flags[0]);
2684         pup_int(p,&flags[1]);
2685         if(flags[1] == 0) {
2686           pup_bytes(p,newblock,sizeof(slot_header));
2687         } else {
2688           pup_bytes(p,newblock,flags[0]);
2689         }
2690         newblock = (char*)newblock + flags[0];
2691       }
2692     }
2693 #if CMK_USE_MEMPOOL_ISOMALLOC || (CMK_SMP && CMK_CONVERSE_GEMINI_UGNI)
2694     mptr->mempoolLock = CmiCreateLock();
2695 #endif  
2696   }
2697   pup_bytes(p,lp,sizeof(int*));
2698   if(pup_isDeleting(p)) {
2699     mempool_destroy(CtvAccessOther(tid,threadpool));
2700     *lp=NULL;
2701   }
2702 }
2703 #else
2704 void CmiIsomallocBlockListPup(pup_er p,CmiIsomallocBlockList **lp, CthThread tid)
2705 {
2706   /* BIGSIM_OOC DEBUGGING */
2707   /* if(!pup_isUnpacking(p)) print_myslots(); */
2708
2709   int i,nBlocks=0;
2710   CmiIsomallocBlockList *cur=NULL, *start=*lp;
2711 #if 0 /*#ifndef CMK_OPTIMIZE*/
2712   if (CpvAccess(isomalloc_blocklist)!=NULL)
2713     CmiAbort("Called CmiIsomallocBlockListPup while a blockList is active!\n"
2714         "You should swap out the active blocklist before pupping.\n");
2715 #endif
2716   /*Count the number of blocks in the list*/
2717   if (!pup_isUnpacking(p)) {
2718     nBlocks=1; /*<- Since we have to skip the start block*/
2719     for (cur=start->next; cur!=start; cur=cur->next) 
2720       nBlocks++;
2721     /*Prepare for next trip around list:*/
2722     cur=start;
2723   }
2724   pup_int(p,&nBlocks);
2725
2726   /*Pup each block in the list*/
2727   for (i=0;i<nBlocks;i++) {
2728     void *newBlock=cur;
2729     if (!pup_isUnpacking(p)) 
2730     { /*While packing, we traverse the list to find our blocks*/
2731       cur=cur->next;
2732     }
2733     CmiIsomallocPup(p,&newBlock);
2734     if (i==0 && pup_isUnpacking(p))
2735       *lp=(CmiIsomallocBlockList *)newBlock;
2736   }
2737   if (pup_isDeleting(p))
2738     *lp=NULL;
2739
2740   /* BIGSIM_OOC DEBUGGING */
2741   /* if(pup_isUnpacking(p)) print_myslots(); */
2742 }
2743 #endif
2744
2745 /*Delete all the blocks in this list.*/
2746 void CmiIsomallocBlockListDelete(CmiIsomallocBlockList *l)
2747 {
2748   CmiIsomallocBlockList *start=l;
2749   CmiIsomallocBlockList *cur=start;
2750   if (cur==NULL) return; /*Already deleted*/
2751   do {
2752     CmiIsomallocBlockList *doomed=cur;
2753     cur=cur->next; /*Have to stash next before deleting cur*/
2754     CmiIsomallocFree(doomed);
2755   } while (cur!=start);
2756 }
2757
2758 /*Allocate a block from this blockList*/
2759 void *CmiIsomallocBlockListMalloc(CmiIsomallocBlockList *l,size_t nBytes)
2760 {
2761   CmiIsomallocBlockList *n; /*Newly created slot*/
2762   n=(CmiIsomallocBlockList *)CmiIsomalloc(sizeof(CmiIsomallocBlockList)+nBytes,NULL);
2763   /*Link the new block into the circular blocklist*/
2764   n->prev=l;
2765   n->next=l->next;
2766   l->next->prev=n;
2767   l->next=n;
2768   return Slot_toUser(n);
2769 }
2770
2771 /*Allocate a block from this blockList with alighment */
2772 void *CmiIsomallocBlockListMallocAlign(CmiIsomallocBlockList *l,size_t align,size_t nBytes)
2773 {
2774   CmiIsomallocBlockList *n; /*Newly created slot*/
2775   n=(CmiIsomallocBlockList *)_isomallocAlign(align,nBytes,sizeof(CmiIsomallocBlockList),NULL);
2776   /*Link the new block into the circular blocklist*/
2777   n->prev=l;
2778   n->next=l->next;
2779   l->next->prev=n;
2780   l->next=n;
2781   return Slot_toUser(n);
2782 }
2783
2784 /*Remove this block from its list and memory*/
2785 void CmiIsomallocBlockListFree(void *block)
2786 {
2787   CmiIsomallocBlockList *n=Slot_fmUser(block);
2788 #if DOHEAPCHECK
2789   if (n->prev->next!=n || n->next->prev!=n) 
2790     CmiAbort("Heap corruption detected in isomalloc block list header!\n"
2791         "  Run with ++debug and look for writes to negative array indices");
2792 #endif
2793   /*Link ourselves out of the blocklist*/
2794   n->prev->next=n->next;
2795   n->next->prev=n->prev;
2796   CmiIsomallocFree(n);
2797 }
2798
2799 /* BIGSIM_OOC DEBUGGING */
2800 static void print_myslots(){
2801   CmiPrintf("[%d] my slot set=%p\n", CmiMyPe(), CpvAccess(myss));
2802   print_slots(CpvAccess(myss));
2803 }
2804
2805
2806