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