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