fix for migration
[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   CmiNodeAllBarrier();
2075   /*
2076      on some machines, isomalloc memory regions on different nodes 
2077      can be different. use +isomalloc_sync to calculate the
2078      intersect of all memory regions on all nodes.
2079      */
2080   if (_sync_iso == 1)
2081   {
2082 #ifdef __FAULT__
2083     if(_restart == 1){
2084       CmiUInt8 s = (CmiUInt8)freeRegion.start;
2085       CmiUInt8 e = (CmiUInt8)(freeRegion.start+freeRegion.len);
2086       CmiUInt8 ss, ee;
2087       int try_count, fd;
2088       char fname[128];
2089       sprintf(fname,".isomalloc");
2090       try_count = 0;
2091       while ((fd = open(fname, O_RDONLY)) == -1 && try_count<10000){
2092         try_count++;
2093       }
2094       if (fd == -1) {
2095         CmiAbort("isomalloc_sync failed during restart, make sure you have a shared file system.");
2096       }
2097       read(fd, &ss, sizeof(CmiUInt8));
2098       read(fd, &ee, sizeof(CmiUInt8));
2099       close(fd);
2100       if (ss < s || ee > e)
2101         CmiAbort("isomalloc_sync failed during restart, virtual memory regions do not overlap.");
2102       else {
2103         freeRegion.start = (void *)ss;
2104         freeRegion.len = (char *)ee -(char *)ss;
2105       }
2106       CmiPrintf("[%d] consolidated Isomalloc memory region at restart: %p - %p (%d megs)\n",CmiMyPe(),freeRegion.start,freeRegion.start+freeRegion.len,freeRegion.len/meg);
2107       goto AFTER_SYNC;
2108     }
2109 #endif
2110     if (CmiMyRank() == 0 && freeRegion.len > 0u) {
2111       if (CmiBarrier() == -1 && CmiMyPe()==0) 
2112         CmiAbort("Charm++ Error> +isomalloc_sync requires CmiBarrier() implemented.\n");
2113       else
2114       {
2115         CmiUInt8 s = (CmiUInt8)freeRegion.start;
2116         CmiUInt8 e = (CmiUInt8)(freeRegion.start+freeRegion.len);
2117         int fd, i,j;
2118         char fname[128];
2119
2120         if (CmiMyNode()==0) printf("Charm++> synchronizing isomalloc memory region...\n");
2121
2122         sprintf(fname,".isomalloc.%d.%d", CmiMyPartition(),CmiMyNode());
2123
2124         /* remove file before writing for safe */
2125         unlink(fname);
2126 #if CMK_HAS_SYNC && ! CMK_DISABLE_SYNC
2127         system("sync");
2128 #endif
2129
2130         CmiBarrier();
2131
2132         /* write region into file */
2133         while ((fd = open(fname, O_WRONLY|O_TRUNC|O_CREAT, 0644)) == -1) 
2134 #ifndef __MINGW_H
2135           CMK_CPV_IS_SMP
2136 #endif
2137             ;
2138         write(fd, &s, sizeof(CmiUInt8));
2139         write(fd, &e, sizeof(CmiUInt8));
2140         close(fd);
2141
2142 #if CMK_HAS_SYNC && ! CMK_DISABLE_SYNC
2143         system("sync");
2144 #endif
2145
2146         CmiBarrier();
2147         for(j=0;j<CmiNumPartition();j++){
2148           for (i=0; i<CmiNumNodes(); i++) {
2149             CmiUInt8 ss, ee; 
2150             int try_count;
2151             char fname[128];
2152             //if (i==CmiMyNode()) continue;
2153             sprintf(fname,".isomalloc.%d.%d",j, i);
2154             try_count = 0;
2155             while ((fd = open(fname, O_RDONLY)) == -1 && try_count<10000)
2156             {
2157               try_count++;
2158 #ifndef __MINGW_H
2159               CMK_CPV_IS_SMP
2160 #endif
2161                 ;
2162             }
2163             if (fd == -1) {
2164               CmiAbort("isomalloc_sync failed, make sure you have a shared file system.");
2165             }
2166             read(fd, &ss, sizeof(CmiUInt8));
2167             read(fd, &ee, sizeof(CmiUInt8));
2168 #if ISOMALLOC_DEBUG
2169             if (CmiMyPe() == 0) CmiPrintf("[%d] load node %d isomalloc region: %lx %lx. \n",
2170                 CmiMyPe(), i, ss, ee);
2171 #endif
2172             close(fd);
2173             if (ss>s) s = ss;
2174             if (ee<e) e = ee;
2175           }
2176         }
2177
2178         CmiBarrier();
2179
2180         unlink(fname);
2181 #if CMK_HAS_SYNC && ! CMK_DISABLE_SYNC
2182         system("sync");
2183 #endif
2184
2185         /* update */
2186         if (s > e)  {
2187           if (CmiMyPe()==0) CmiPrintf("[%d] Invalid isomalloc region: %lx - %lx.\n", CmiMyPe(), s, e);
2188           CmiAbort("isomalloc> failed to find consolidated isomalloc region!");
2189         }
2190         freeRegion.start = (void *)s;
2191         freeRegion.len = (char *)e -(char *)s;
2192
2193         if (CmiMyPe() == 0)
2194           CmiPrintf("[%d] consolidated Isomalloc memory region: %p - %p (%d megs)\n",CmiMyPe(),
2195               freeRegion.start,freeRegion.start+freeRegion.len,
2196               freeRegion.len/meg);
2197 #if __FAULT__
2198         if(CmiMyPe() == 0 && CmiMyPartition() == 0){
2199           int fd;
2200           char fname[128];
2201           CmiUInt8 s = (CmiUInt8)freeRegion.start;
2202           CmiUInt8 e = (CmiUInt8)(freeRegion.start+freeRegion.len);
2203           sprintf(fname,".isomalloc");
2204           while ((fd = open(fname, O_WRONLY|O_TRUNC|O_CREAT, 0644)) == -1);
2205           write(fd, &s, sizeof(CmiUInt8));
2206           write(fd, &e, sizeof(CmiUInt8));
2207           close(fd);
2208         }
2209 #endif
2210       }   /* end of barrier test */
2211     } /* end of rank 0 */
2212     else {
2213       CmiBarrier();
2214       CmiBarrier();
2215       CmiBarrier();
2216       CmiBarrier();
2217     }
2218   }
2219
2220 #ifdef __FAULT__
2221 AFTER_SYNC:
2222 #endif
2223
2224   if (CmiMyRank() == 0 && freeRegion.len > 0u)
2225   {
2226     /*Isomalloc covers entire unused region*/
2227     isomallocStart=freeRegion.start;
2228     isomallocEnd=freeRegion.start+freeRegion.len;
2229     numslots=(freeRegion.len/slotsize)/CmiNumPes();
2230
2231 #if ISOMALLOC_DEBUG
2232     CmiPrintf("[%d] Can isomalloc up to %lu megs per pe\n",CmiMyPe(),
2233         ((memRange_t)numslots)*slotsize/meg);
2234 #endif
2235   }
2236
2237   /*SMP Mode: wait here for rank 0 to initialize numslots before calculating myss*/
2238   CmiNodeAllBarrier(); 
2239
2240   CpvInitialize(slotset *, myss);
2241   CpvAccess(myss) = NULL;
2242
2243 #if CMK_USE_MEMPOOL_ISOMALLOC
2244   CtvInitialize(mempool_type *, threadpool);
2245   CtvAccess(threadpool) = NULL;
2246 #endif
2247
2248   if (isomallocStart!=NULL) {
2249     CpvAccess(myss) = new_slotset(pe2slot(CmiMyPe()), numslots);
2250   }
2251 }
2252
2253
2254 /************* Communication: for grabbing/freeing remote slots *********/
2255 typedef struct _slotmsg
2256 {
2257   char cmicore[CmiMsgHeaderSizeBytes];
2258   int pe; /*Source processor*/
2259   CmiInt8 slot; /*First requested slot*/
2260   CmiInt8 nslots; /*Number of requested slots*/
2261 } slotmsg;
2262
2263 static slotmsg *prepare_slotmsg(CmiInt8 slot,CmiInt8 nslots)
2264 {
2265   slotmsg *m=(slotmsg *)CmiAlloc(sizeof(slotmsg));
2266   m->pe=CmiMyPe();
2267   m->slot=slot;
2268   m->nslots=nslots;
2269   return m;
2270 }
2271
2272 static void grab_remote(slotmsg *msg)
2273 {
2274   grab_slots(CpvAccess(myss),msg->slot,msg->nslots);
2275   CmiFree(msg);
2276 }
2277
2278 static void free_remote(slotmsg *msg)
2279 {
2280   free_slots(CpvAccess(myss),msg->slot,msg->nslots);
2281   CmiFree(msg);
2282 }
2283 static int grab_remote_idx, free_remote_idx;
2284
2285 struct slotOP {
2286   /*Function pointer to perform local operation*/
2287   void (*local)(slotset *ss,CmiInt8 s,CmiInt8 n);
2288   /*Index to perform remote operation*/
2289   int remote;
2290 };
2291 typedef struct slotOP slotOP;
2292 static slotOP grabOP,freeOP;
2293
2294 static void init_comm(char **argv)
2295 {
2296   grab_remote_idx=CmiRegisterHandler((CmiHandler)grab_remote);
2297   free_remote_idx=CmiRegisterHandler((CmiHandler)free_remote);  
2298   grabOP.local=grab_slots;
2299   grabOP.remote=grab_remote_idx;
2300   freeOP.local=free_slots;
2301   freeOP.remote=free_remote_idx;        
2302 }
2303
2304 /*Apply the given operation to the given slots which
2305   lie on the given processor.*/
2306 static void one_slotOP(const slotOP *op,int pe,CmiInt8 s,CmiInt8 n)
2307 {
2308   /*Shrink range to only those covered by this processor*/
2309   /*First and last slot for this processor*/
2310   CmiInt8 p_s=pe2slot(pe), p_e=pe2slot(pe+1);
2311   CmiInt8 e=s+n;
2312   if (s<p_s) s=p_s;
2313   if (e>p_e) e=p_e;
2314   n=e-s;
2315
2316   /*Send off range*/
2317   if (pe==CmiMyPe()) 
2318     op->local(CpvAccess(myss),s,n);
2319   else 
2320   {/*Remote request*/
2321     slotmsg *m=prepare_slotmsg(s,n);
2322     CmiSetHandler(m, freeOP.remote);
2323     CmiSyncSendAndFree(pe,sizeof(slotmsg),m);
2324   }
2325 }
2326
2327 /*Apply the given operation to all slots in the range [s, s+n) 
2328   After a restart from checkpoint, a slotset can cross an 
2329   arbitrary set of processors.
2330   */
2331 static void all_slotOP(const slotOP *op,CmiInt8 s,CmiInt8 n)
2332 {
2333   int spe=slot2pe(s), epe=slot2pe(s+n-1);
2334   int pe;
2335   for (pe=spe; pe<=epe; pe++)
2336     one_slotOP(op,pe,s,n);
2337 }
2338
2339 /************** External interface ***************/
2340 #if CMK_USE_MEMPOOL_ISOMALLOC
2341 void *CmiIsomalloc(int size, CthThread tid)
2342 {
2343   CmiInt8 s,n,i;
2344   CmiIsomallocBlock *blk;
2345   if (isomallocStart==NULL) return disabled_map(size);
2346   if(tid != NULL) {
2347     if(CtvAccessOther(tid,threadpool) == NULL) {
2348 #if ISOMALLOC_DEBUG
2349       printf("Init Mempool in %d for %d\n",CthSelf(), tid);
2350 #endif
2351       CtvAccessOther(tid,threadpool) = mempool_init(2*(size+sizeof(CmiIsomallocBlock)+sizeof(mempool_header))+sizeof(mempool_type), isomallocfn, isofreefn,0);
2352     }
2353     blk = (CmiIsomallocBlock*)mempool_malloc(CtvAccessOther(tid,threadpool),size+sizeof(CmiIsomallocBlock),1);
2354   } else {
2355     if(CtvAccess(threadpool) == NULL) {
2356 #if ISOMALLOC_DEBUG
2357       printf("Init Mempool in %d\n",CthSelf());
2358 #endif
2359       CtvAccess(threadpool) = mempool_init(2*(size+sizeof(CmiIsomallocBlock)+sizeof(mempool_header))+sizeof(mempool_type), isomallocfn, isofreefn,0);
2360     }
2361     blk = (CmiIsomallocBlock*)mempool_malloc(CtvAccess(threadpool),size+sizeof(CmiIsomallocBlock),1);
2362   }
2363   blk->slot=(CmiInt8)blk;
2364   blk->length=size;
2365   return block2pointer(blk);
2366 }
2367 #else
2368 void *CmiIsomalloc(int size, CthThread tid)
2369 {
2370   CmiInt8 s,n,i;
2371   CmiIsomallocBlock *blk;
2372   if (isomallocStart==NULL) return disabled_map(size);
2373   n=length2slots(size);
2374   /*Always satisfy mallocs with local slots:*/
2375   s=get_slots(CpvAccess(myss),n);
2376   if (s==-1) {
2377     CmiError("Not enough address space left on processor %d to isomalloc %d bytes!\n",
2378         CmiMyPe(),size);
2379     CmiAbort("Out of virtual address space for isomalloc");
2380   }
2381   grab_slots(CpvAccess(myss),s,n);
2382   for (i=0; i<5; i++) {
2383     blk=map_slots(s,n);
2384     if (blk!=NULL) break;
2385 #if CMK_HAS_USLEEP
2386     if (errno == ENOMEM) { usleep(rand()%1000); continue; }
2387     else break;
2388 #endif
2389   }
2390   if (!blk) map_failed(s,n);
2391   blk->slot=s;
2392   blk->length=size;
2393   return block2pointer(blk);
2394 }
2395 #endif
2396
2397 #define MALLOC_ALIGNMENT           (2*sizeof(size_t))
2398 #define MINSIZE                    (sizeof(CmiIsomallocBlock))
2399
2400 /** return an aligned isomalloc memory, the alignment occurs after the
2401  *  first 'reserved' bytes.  Total requested size is (size+reserved)
2402  */
2403 static void *_isomallocAlign(size_t align, size_t size, size_t reserved, CthThread t) {
2404   void *ptr;
2405   CmiIntPtr ptr2align;
2406   CmiInt8 s;
2407
2408   if (align < MINSIZE) align = MINSIZE;
2409   /* make sure alignment is power of 2 */
2410   if ((align & (align - 1)) != 0) {
2411     size_t a = MALLOC_ALIGNMENT * 2;
2412     while ((unsigned long)a < (unsigned long)align) a <<= 1;
2413     align = a;
2414   }
2415   s = size + reserved + align;
2416   ptr = CmiIsomalloc(s,t);
2417   ptr2align = (CmiIntPtr)ptr;
2418   ptr2align += reserved;
2419   if (ptr2align % align != 0) { /* misaligned */
2420     CmiIsomallocBlock *blk = pointer2block(ptr);  /* save block */
2421     CmiIsomallocBlock savedblk = *blk;
2422     ptr2align = (ptr2align + align - 1) & -((CmiInt8) align);
2423     ptr2align -= reserved;
2424     ptr = (void*)ptr2align;
2425     blk = pointer2block(ptr);      /* restore block */
2426     *blk = savedblk;
2427   }
2428   return ptr;
2429 }
2430
2431 void *CmiIsomallocAlign(size_t align, size_t size, CthThread t)
2432 {
2433   return _isomallocAlign(align, size, 0, t);
2434 }
2435
2436 int CmiIsomallocEnabled()
2437 {
2438   return (isomallocStart!=NULL);
2439 }
2440
2441 void CmiIsomallocPup(pup_er p,void **blockPtrPtr)
2442 {
2443   CmiIsomallocBlock *blk;
2444   CmiInt8 s,length;
2445   CmiInt8 n;
2446 #if CMK_USE_MEMPOOL_ISOMALLOC
2447   CmiAbort("Incorrect pup is called\n");
2448 #endif
2449   if (isomallocStart==NULL) CmiAbort("isomalloc is disabled-- cannot use IsomallocPup");
2450
2451   if (!pup_isUnpacking(p)) 
2452   { /*We have an existing block-- unpack start slot & length*/
2453     blk=pointer2block(*blockPtrPtr);
2454     s=blk->slot;
2455     length=blk->length;
2456   }
2457
2458   pup_int8(p,&s);
2459   pup_int8(p,&length);
2460   n=length2slots(length);
2461
2462   if (pup_isUnpacking(p)) 
2463   { /*Must allocate a new block in its old location*/
2464     if (pup_isUserlevel(p) || pup_isRestarting(p))
2465     {   /*Checkpoint: must grab old slots (even remote!)*/
2466       all_slotOP(&grabOP,s,n);
2467     }
2468     blk=map_slots(s,n);
2469     if (!blk) map_failed(s,n);
2470     blk->slot=s;
2471     blk->length=length;
2472     *blockPtrPtr=block2pointer(blk);
2473   }
2474
2475   /*Pup the allocated data*/
2476   pup_bytes(p,*blockPtrPtr,length);
2477
2478   if (pup_isDeleting(p)) 
2479   { /*Unmap old slots, but do not mark as free*/
2480     unmap_slots(s,n);
2481     *blockPtrPtr=NULL; /*Zero out user's pointer*/
2482   }
2483 }
2484
2485 void CmiIsomallocFree(void *blockPtr)
2486 {
2487   if (isomallocStart==NULL) {
2488     disabled_unmap(blockPtr);
2489   }
2490   else if (blockPtr!=NULL)
2491   {
2492 #if CMK_USE_MEMPOOL_ISOMALLOC
2493     mempool_free_thread((void*)pointer2block(blockPtr)->slot);
2494 #else
2495     CmiIsomallocBlock *blk=pointer2block(blockPtr);
2496     CmiInt8 s=blk->slot; 
2497     CmiInt8 n=length2slots(blk->length);
2498     unmap_slots(s,n);
2499     /*Mark used slots as free*/
2500     all_slotOP(&freeOP,s,n);
2501 #endif
2502   }
2503 }
2504
2505 CmiInt8  CmiIsomallocLength(void *block)
2506 {
2507   return pointer2block(block)->length;
2508 }
2509
2510 /*Return true if this address is in the region managed by isomalloc*/
2511 int CmiIsomallocInRange(void *addr)
2512 {
2513   if (isomallocStart==NULL) return 0; /* There is no range we manage! */
2514   return pointer_ge((char *)addr,isomallocStart) && 
2515     pointer_lt((char*)addr,isomallocEnd);
2516 }
2517
2518 void CmiIsomallocInit(char **argv)
2519 {
2520 #if CMK_NO_ISO_MALLOC
2521   disable_isomalloc("isomalloc disabled by conv-mach");
2522 #else
2523   if (CmiGetArgFlagDesc(argv,"+noisomalloc","disable isomalloc")) {
2524     disable_isomalloc("isomalloc disabled by user.");
2525     return;
2526   }
2527 #if CMK_MMAP_PROBE
2528   _mmap_probe = 1;
2529 #elif CMK_MMAP_TEST
2530   _mmap_probe = 0;
2531 #endif
2532   if (CmiGetArgFlagDesc(argv,"+isomalloc_probe","call mmap to probe the largest available isomalloc region"))
2533     _mmap_probe = 1;
2534   if (CmiGetArgFlagDesc(argv,"+isomalloc_test","mmap test common areas for the largest available isomalloc region"))
2535     _mmap_probe = 0;
2536   if (CmiGetArgFlagDesc(argv,"+isomalloc_sync","synchronize isomalloc region globaly"))
2537     _sync_iso = 1;
2538 #if __FAULT__
2539   int resPhase;
2540   if (CmiGetArgFlagDesc(argv,"+restartisomalloc","restarting isomalloc on this processor after a crash"))
2541     _restart = 1;
2542 #endif
2543   init_comm(argv);
2544   if (!init_map(argv)) {
2545     disable_isomalloc("mmap() does not work");
2546   }
2547   else {
2548     if (CmiMyPe() == 0) {
2549       if (read_randomflag() == 1) {    /* randomization stack pointer */
2550         if (_sync_iso == 1)
2551           printf("Warning> Randomization of stack pointer is turned on in kernel.\n");
2552         else
2553           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");
2554       }
2555     }
2556     init_ranges(argv);
2557   }
2558 #endif
2559 }
2560
2561 /***************** BlockList interface *********
2562   This was moved here from memory-isomalloc.c when it 
2563   was realized that a list-of-isomalloc'd-blocks is useful for
2564   more than just isomalloc heaps.
2565   */
2566
2567 /*Convert a slot to a user address*/
2568 static char *Slot_toUser(CmiIsomallocBlockList *s) {return (char *)(s+1);}
2569 static CmiIsomallocBlockList *Slot_fmUser(void *s) {return ((CmiIsomallocBlockList *)s)-1;}
2570
2571 /*Build a new blockList.*/
2572 CmiIsomallocBlockList *CmiIsomallocBlockListNew(CthThread tid)
2573 {
2574   CmiIsomallocBlockList *ret;
2575   ret=(CmiIsomallocBlockList *)CmiIsomalloc(sizeof(*ret),tid);
2576   ret->next=ret; /*1-entry circular linked list*/
2577   ret->prev=ret;
2578   return ret;
2579 }
2580
2581 /* BIGSIM_OOC DEBUGGING */
2582 static void print_myslots();
2583
2584 /*Pup all the blocks in this list.  This amounts to two circular
2585   list traversals.  Because everything's isomalloc'd, we don't even
2586   have to restore the pointers-- they'll be restored automatically!
2587   */
2588 #if CMK_USE_MEMPOOL_ISOMALLOC
2589 void CmiIsomallocBlockListPup(pup_er p,CmiIsomallocBlockList **lp, CthThread tid)
2590 {
2591   mempool_type *mptr;
2592   block_header *current, *block_head;
2593   slot_header *currSlot;
2594   void *newblock;
2595   CmiInt8 slot;
2596   size_t size;
2597   int flags[2];
2598   int i, j;
2599   int numBlocks = 0, numSlots = 0, flag = 1;
2600
2601 #if ISOMALLOC_DEBUG
2602   printf("[%d] My rank is %lld Pupping for %lld with isUnpack %d isDelete %d \n",CmiMyPe(),CthSelf(),tid,pup_isUnpacking(p),pup_isDeleting(p));
2603 #endif
2604   flags[0] = 0; flags[1] = 1;
2605   //  if(!pup_isUnpacking(p)&& !pup_isChecking(p)) {
2606   int first = 1;
2607   i = 0; j = 0;
2608   //if(!pup_isUnpacking(p)) {
2609   if(!pup_isUnpacking(p)&&!(pup_isChecking(p)&&!pup_isCalChecking(p))) {
2610     mptr = CtvAccessOther(tid,threadpool);
2611     current = MEMPOOL_GetBlockHead(mptr);
2612     while(current != NULL) {
2613       numBlocks++;
2614       current = MEMPOOL_GetBlockNext(current)?(block_header *)((char*)mptr+MEMPOOL_GetBlockNext(current)):NULL;
2615     }
2616 #if ISOMALLOC_DEBUG
2617     printf("Number of blocks packed %d\n",numBlocks);
2618 #endif
2619     pup_int(p,&numBlocks);
2620     current = MEMPOOL_GetBlockHead(mptr);
2621     while(current != NULL) {
2622       j=0;
2623       pup_bytes(p,&(MEMPOOL_GetBlockSize(current)),sizeof(MEMPOOL_GetBlockSize(current)));
2624       pup_bytes(p,&(MEMPOOL_GetBlockMemHndl(current)),sizeof(CmiInt8));
2625       numSlots = 0;
2626       if(flag) {
2627         pup_bytes(p,current,sizeof(mempool_type));
2628         currSlot = (slot_header*)((char*)current+sizeof(mempool_type));
2629       } else {
2630         pup_bytes(p,current,sizeof(block_header));
2631         currSlot = (slot_header*)((char*)current+sizeof(block_header));
2632       }
2633       while(currSlot != NULL) {
2634         numSlots++;
2635         currSlot = (MEMPOOL_GetSlotGNext(currSlot))?(slot_header*)((char*)mptr+MEMPOOL_GetSlotGNext(currSlot)):NULL;
2636       }
2637       pup_int(p,&numSlots);
2638       if(flag) {
2639         currSlot = (slot_header*)((char*)current+sizeof(mempool_type));
2640         flag = 0;
2641       } else {
2642         currSlot = (slot_header*)((char*)current+sizeof(block_header));
2643       }
2644       while(currSlot != NULL) {
2645         pup_int(p,&cutOffPoints[currSlot->size]);
2646         if(MEMPOOL_GetSlotStatus(currSlot)) {
2647           pup_int(p,&flags[0]);
2648           pup_bytes(p,(void*)currSlot,sizeof(slot_header));
2649         } else {
2650           pup_int(p,&flags[1]);
2651           //pup_bytes(p,(void*)currSlot,sizeof(slot_header));
2652           if(pup_isChecking(p)){
2653             if(first == 0){
2654               pup_resumeChecking(p);
2655             }else{
2656               first = 0;
2657             }
2658             //      printf("[%d][%d]checking block %d slot %d check isomalloc header %d\n",CmiMyPartition(),CmiMyPe(),i,j,MEMPOOL_GetSlotSize(currSlot));
2659           }
2660           //         else
2661           //         printf("[%d][%d]block %d slot %d check isomalloc header %d\n",CmiMyPartition(),CmiMyPe(),i,j,MEMPOOL_GetSlotSize(currSlot));
2662           //pup_bytes(p,(void*)currSlot+sizeof(slot_header),MEMPOOL_GetSlotSize(currSlot)-sizeof(slot_header));
2663           pup_bytes(p,(void*)currSlot,MEMPOOL_GetSlotSize(currSlot));
2664           if(pup_isChecking(p)){
2665             pup_skipChecking(p);
2666           }
2667         }
2668         currSlot = (MEMPOOL_GetSlotGNext(currSlot))?(slot_header*)((char*)mptr+MEMPOOL_GetSlotGNext(currSlot)):NULL;
2669         j++;
2670       }
2671       current = (MEMPOOL_GetBlockNext(current))?(block_header *)((char*)mptr+MEMPOOL_GetBlockNext(current)):NULL;
2672       i++;
2673     }
2674   }
2675
2676   if(pup_isUnpacking(p)||(pup_isChecking(p)&&!pup_isCalChecking(p))) {
2677     //if(pup_isUnpacking(p)) {
2678     pup_int(p,&numBlocks);
2679 #if ISOMALLOC_DEBUG
2680     printf("Number of blocks to be unpacked %d\n",numBlocks);
2681 #endif
2682     //printf("[%d][%d]Number of blocks to be unpacked %d\n",CmiMyPartition(),CmiMyPe(),numBlocks);
2683     for(i = 0; i < numBlocks; i++) { 
2684       pup_bytes(p,&size,sizeof(size));
2685       pup_bytes(p,&slot,sizeof(slot));
2686       newblock = map_slots(slot,size/slotsize);
2687       if(flag) {
2688         mptr = (mempool_type*)newblock;
2689         pup_bytes(p,newblock,sizeof(mempool_type));
2690         newblock = (char*)newblock + sizeof(mempool_type);
2691         flag = 0;
2692       } else {
2693         pup_bytes(p,newblock,sizeof(block_header));
2694         newblock = (char*)newblock + sizeof(block_header);
2695       }
2696       pup_int(p,&numSlots);
2697       //printf("[%d][%d]Number of slots to be unpacked %d\n",CmiMyPartition(),CmiMyPe(),numSlots);
2698       for(j=0; j < numSlots; j++) {
2699         pup_int(p,&flags[0]);
2700         pup_int(p,&flags[1]);
2701         if(flags[1] == 0) {
2702           pup_bytes(p,newblock,sizeof(slot_header));
2703         } else {
2704           //pup_bytes(p,newblock,sizeof(slot_header));
2705           if(pup_isChecking(p)){
2706             if(first == 0){
2707               pup_resumeChecking(p);
2708             }else{
2709               first = 0;
2710             }
2711             //       printf("[%d][%d]unpack block %d slot %d check isomalloc header %d\n",CmiMyPartition(),CmiMyPe(),i,j,flags[0]);
2712           }
2713           pup_bytes(p,newblock,flags[0]);
2714           if(pup_isChecking(p)){
2715             pup_skipChecking(p);
2716           }
2717         }
2718         newblock = (char*)newblock + flags[0];
2719       }
2720     }
2721 #if CMK_USE_MEMPOOL_ISOMALLOC || (CMK_SMP && CMK_CONVERSE_GEMINI_UGNI)
2722     mptr->mempoolLock = CmiCreateLock();
2723 #endif  
2724   }
2725   pup_bytes(p,lp,sizeof(int*));
2726   if(pup_isDeleting(p)) {
2727     mempool_destroy(CtvAccessOther(tid,threadpool));
2728     *lp=NULL;
2729   }
2730   }
2731 #else
2732   void CmiIsomallocBlockListPup(pup_er p,CmiIsomallocBlockList **lp, CthThread tid)
2733   {
2734     /* BIGSIM_OOC DEBUGGING */
2735     /* if(!pup_isUnpacking(p)) print_myslots(); */
2736
2737     int i,nBlocks=0;
2738     CmiIsomallocBlockList *cur=NULL, *start=*lp;
2739 #if 0 /*#ifndef CMK_OPTIMIZE*/
2740     if (CpvAccess(isomalloc_blocklist)!=NULL)
2741       CmiAbort("Called CmiIsomallocBlockListPup while a blockList is active!\n"
2742           "You should swap out the active blocklist before pupping.\n");
2743 #endif
2744     /*Count the number of blocks in the list*/
2745     if (!pup_isUnpacking(p)) {
2746       nBlocks=1; /*<- Since we have to skip the start block*/
2747       for (cur=start->next; cur!=start; cur=cur->next) 
2748         nBlocks++;
2749       /*Prepare for next trip around list:*/
2750       cur=start;
2751     }
2752     pup_int(p,&nBlocks);
2753
2754     /*Pup each block in the list*/
2755     for (i=0;i<nBlocks;i++) {
2756       void *newBlock=cur;
2757       if (!pup_isUnpacking(p)) 
2758       { /*While packing, we traverse the list to find our blocks*/
2759         cur=cur->next;
2760       }
2761       CmiIsomallocPup(p,&newBlock);
2762       if (i==0 && pup_isUnpacking(p))
2763         *lp=(CmiIsomallocBlockList *)newBlock;
2764     }
2765     if (pup_isDeleting(p))
2766       *lp=NULL;
2767
2768     /* BIGSIM_OOC DEBUGGING */
2769     /* if(pup_isUnpacking(p)) print_myslots(); */
2770   }
2771 #endif
2772
2773   /*Delete all the blocks in this list.*/
2774   void CmiIsomallocBlockListDelete(CmiIsomallocBlockList *l)
2775   {
2776     CmiIsomallocBlockList *start=l;
2777     CmiIsomallocBlockList *cur=start;
2778     if (cur==NULL) return; /*Already deleted*/
2779     do {
2780       CmiIsomallocBlockList *doomed=cur;
2781       cur=cur->next; /*Have to stash next before deleting cur*/
2782       CmiIsomallocFree(doomed);
2783     } while (cur!=start);
2784   }
2785
2786   /*Allocate a block from this blockList*/
2787   void *CmiIsomallocBlockListMalloc(CmiIsomallocBlockList *l,size_t nBytes)
2788   {
2789     CmiIsomallocBlockList *n; /*Newly created slot*/
2790     n=(CmiIsomallocBlockList *)CmiIsomalloc(sizeof(CmiIsomallocBlockList)+nBytes,NULL);
2791     /*Link the new block into the circular blocklist*/
2792     n->prev=l;
2793     n->next=l->next;
2794     l->next->prev=n;
2795     l->next=n;
2796     return Slot_toUser(n);
2797   }
2798
2799   /*Allocate a block from this blockList with alighment */
2800   void *CmiIsomallocBlockListMallocAlign(CmiIsomallocBlockList *l,size_t align,size_t nBytes)
2801   {
2802     CmiIsomallocBlockList *n; /*Newly created slot*/
2803     n=(CmiIsomallocBlockList *)_isomallocAlign(align,nBytes,sizeof(CmiIsomallocBlockList),NULL);
2804     /*Link the new block into the circular blocklist*/
2805     n->prev=l;
2806     n->next=l->next;
2807     l->next->prev=n;
2808     l->next=n;
2809     return Slot_toUser(n);
2810   }
2811
2812   /*Remove this block from its list and memory*/
2813   void CmiIsomallocBlockListFree(void *block)
2814   {
2815     CmiIsomallocBlockList *n=Slot_fmUser(block);
2816 #if DOHEAPCHECK
2817     if (n->prev->next!=n || n->next->prev!=n) 
2818       CmiAbort("Heap corruption detected in isomalloc block list header!\n"
2819           "  Run with ++debug and look for writes to negative array indices");
2820 #endif
2821     /*Link ourselves out of the blocklist*/
2822     n->prev->next=n->next;
2823     n->next->prev=n->prev;
2824     CmiIsomallocFree(n);
2825   }
2826
2827   /* BIGSIM_OOC DEBUGGING */
2828   static void print_myslots(){
2829     CmiPrintf("[%d] my slot set=%p\n", CmiMyPe(), CpvAccess(myss));
2830     print_slots(CpvAccess(myss));
2831   }
2832
2833
2834