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