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