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