removed a debug print
[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 #if CMK_MACOSX
1837       if (regions[i].start+regions[i].len*2>regions[i].start) regions[i].len *= 2;
1838 #endif
1839 #if CMK_THREADS_DEBUG
1840       CmiPrintf("[%d] Memory map: %p - %p (len: %lu => %lu) %s \n",CmiMyPe(),
1841               regions[i].start,regions[i].start+regions[i].len,
1842               old.len, regions[i].len, regions[i].type);
1843 #endif
1844     }
1845     
1846     /*Find a large, unused region in this map: */
1847     freeRegion=find_free_region(regions,nRegions,(512u)*meg);
1848     
1849     if (freeRegion.start==0) 
1850     { /*No free address space-- disable isomalloc:*/
1851       return 0;
1852     }
1853     else /* freeRegion is valid */
1854     {
1855       *destRegion=freeRegion;
1856       
1857       return 1;
1858     }
1859 }
1860
1861 #ifndef CMK_CPV_IS_SMP
1862 #define CMK_CPV_IS_SMP
1863 #endif
1864
1865 static void init_ranges(char **argv)
1866 {
1867   memRegion_t freeRegion;
1868   /*Largest value a signed int can hold*/
1869   memRange_t intMax=(((memRange_t)1)<<(sizeof(int)*8-1))-1;
1870
1871   /*Round slot size up to nearest page size*/
1872   slotsize=16*1024;
1873   slotsize=(slotsize+CMK_MEMORY_PAGESIZE-1) & ~(CMK_MEMORY_PAGESIZE-1);
1874 #if CMK_THREADS_DEBUG
1875   CmiPrintf("[%d] Using slotsize of %d\n", CmiMyPe(), slotsize);
1876 #endif
1877
1878   freeRegion.len=0u;
1879
1880   if (CmiMyRank()==0 && numslots==0)
1881   { /* Find the largest unused region of virtual address space */
1882 #ifdef CMK_MMAP_START_ADDRESS /* Hardcoded start address, for machines where automatic fails */
1883       freeRegion.start=CMK_MMAP_START_ADDRESS;
1884       freeRegion.len=CMK_MMAP_LENGTH_MEGS*meg;
1885 #endif
1886       if (freeRegion.len==0u) find_largest_free_region(&freeRegion);
1887       
1888 #if 0
1889       /*Make sure our largest slot number doesn't overflow an int:*/
1890       if (freeRegion.len/slotsize>intMax)
1891         freeRegion.len=intMax*slotsize;
1892 #endif
1893       
1894       if (freeRegion.len==0u) {
1895         disable_isomalloc("no free virtual address space");
1896       }
1897       else /* freeRegion.len>0, so can isomalloc */
1898       {
1899 #if CMK_THREADS_DEBUG
1900         CmiPrintf("[%d] Isomalloc memory region: %p - %p (%d megs)\n",CmiMyPe(),
1901               freeRegion.start,freeRegion.start+freeRegion.len,
1902               freeRegion.len/meg);
1903 #endif
1904       }
1905   }
1906
1907     /*
1908        on some machines, isomalloc memory regions on different nodes 
1909        can be different. use +isomalloc_sync to calculate the
1910        intersect of all memory regions on all nodes.
1911     */
1912   if (_sync_iso == 1)
1913   {
1914         if (CmiMyRank() == 0 && freeRegion.len > 0u) {
1915           if (CmiBarrier() == -1) 
1916             CmiAbort("Charm++ Error> +isomalloc_sync requires CmiBarrier() implemented.\n");
1917           else {
1918             CmiUInt8 s = (CmiUInt8)freeRegion.start;
1919             CmiUInt8 e = (CmiUInt8)(freeRegion.start+freeRegion.len);
1920             int fd, i;
1921             char fname[128];
1922
1923             if (CmiMyNode()==0) printf("Charm++> synchronizing isomalloc memory region...\n");
1924
1925             sprintf(fname,".isomalloc.%d", CmiMyNode());
1926
1927               /* remove file before writing for safe */
1928             unlink(fname);
1929 #if CMK_HAS_SYNC && ! CMK_DISABLE_SYNC
1930             system("sync");
1931 #endif
1932
1933             CmiBarrier();
1934
1935               /* write region into file */
1936             while ((fd = open(fname, O_WRONLY|O_TRUNC|O_CREAT, 0644)) == -1) 
1937 #ifndef __MINGW_H
1938               CMK_CPV_IS_SMP
1939 #endif
1940             ;
1941             write(fd, &s, sizeof(CmiUInt8));
1942             write(fd, &e, sizeof(CmiUInt8));
1943             close(fd);
1944
1945 #if CMK_HAS_SYNC && ! CMK_DISABLE_SYNC
1946             system("sync");
1947 #endif
1948
1949             CmiBarrier();
1950
1951             for (i=0; i<CmiNumNodes(); i++) {
1952               CmiUInt8 ss, ee; 
1953               char fname[128];
1954               if (i==CmiMyNode()) continue;
1955               sprintf(fname,".isomalloc.%d", i);
1956               while ((fd = open(fname, O_RDONLY)) == -1)
1957 #ifndef __MINGW_H
1958               CMK_CPV_IS_SMP
1959 #endif
1960               ;
1961               read(fd, &ss, sizeof(CmiUInt8));
1962               read(fd, &ee, sizeof(CmiUInt8));
1963               close(fd);
1964               if (ss>s) s = ss;
1965               if (ee<e) e = ee;
1966             }
1967
1968             CmiBarrier();
1969
1970             unlink(fname);
1971 #if CMK_HAS_SYNC && ! CMK_DISABLE_SYNC
1972             system("sync");
1973 #endif
1974
1975               /* update */
1976             freeRegion.start = (void *)s;
1977             freeRegion.len = (char *)e -(char *)s;
1978             CmiAssert(freeRegion.len >= 0u);
1979
1980             if (CmiMyPe() == 0)
1981             CmiPrintf("[%d] consolidated Isomalloc memory region: %p - %p (%d megs)\n",CmiMyPe(),
1982               freeRegion.start,freeRegion.start+freeRegion.len,
1983               freeRegion.len/meg);
1984           }   /* end of barrier test */
1985         } /* end of rank 0 */
1986         else {
1987           CmiBarrier();
1988           CmiBarrier();
1989           CmiBarrier();
1990           CmiBarrier();
1991         }
1992   }
1993
1994   if (CmiMyRank() == 0 && freeRegion.len > 0u)
1995   {
1996         /*Isomalloc covers entire unused region*/
1997         isomallocStart=freeRegion.start;
1998         isomallocEnd=freeRegion.start+freeRegion.len;
1999         numslots=(freeRegion.len/slotsize)/CmiNumPes();
2000         
2001 #if CMK_THREADS_DEBUG
2002         CmiPrintf("[%d] Can isomalloc up to %lu megs per pe\n",CmiMyPe(),
2003               ((memRange_t)numslots)*slotsize/meg);
2004 #endif
2005   }
2006
2007   /*SMP Mode: wait here for rank 0 to initialize numslots before calculating myss*/
2008   CmiNodeAllBarrier(); 
2009   
2010   if (isomallocStart!=NULL) {
2011     CpvInitialize(slotset *, myss);
2012     CpvAccess(myss) = new_slotset(pe2slot(CmiMyPe()), numslots);
2013   }
2014 }
2015
2016
2017 /************* Communication: for grabbing/freeing remote slots *********/
2018 typedef struct _slotmsg
2019 {
2020   char cmicore[CmiMsgHeaderSizeBytes];
2021   int pe; /*Source processor*/
2022   CmiInt8 slot; /*First requested slot*/
2023   CmiInt8 nslots; /*Number of requested slots*/
2024 } slotmsg;
2025
2026 static slotmsg *prepare_slotmsg(CmiInt8 slot,CmiInt8 nslots)
2027 {
2028         slotmsg *m=(slotmsg *)CmiAlloc(sizeof(slotmsg));
2029         m->pe=CmiMyPe();
2030         m->slot=slot;
2031         m->nslots=nslots;
2032         return m;
2033 }
2034
2035 static void grab_remote(slotmsg *msg)
2036 {
2037         grab_slots(CpvAccess(myss),msg->slot,msg->nslots);
2038         CmiFree(msg);
2039 }
2040
2041 static void free_remote(slotmsg *msg)
2042 {
2043         free_slots(CpvAccess(myss),msg->slot,msg->nslots);
2044         CmiFree(msg);
2045 }
2046 static int grab_remote_idx, free_remote_idx;
2047
2048 struct slotOP {
2049         /*Function pointer to perform local operation*/
2050         void (*local)(slotset *ss,CmiInt8 s,CmiInt8 n);
2051         /*Index to perform remote operation*/
2052         int remote;
2053 };
2054 typedef struct slotOP slotOP;
2055 static slotOP grabOP,freeOP;
2056
2057 static void init_comm(char **argv)
2058 {
2059         grab_remote_idx=CmiRegisterHandler((CmiHandler)grab_remote);
2060         free_remote_idx=CmiRegisterHandler((CmiHandler)free_remote);    
2061         grabOP.local=grab_slots;
2062         grabOP.remote=grab_remote_idx;
2063         freeOP.local=free_slots;
2064         freeOP.remote=free_remote_idx;  
2065 }
2066
2067 /*Apply the given operation to the given slots which
2068   lie on the given processor.*/
2069 static void one_slotOP(const slotOP *op,int pe,CmiInt8 s,CmiInt8 n)
2070 {
2071 /*Shrink range to only those covered by this processor*/
2072         /*First and last slot for this processor*/
2073         CmiInt8 p_s=pe2slot(pe), p_e=pe2slot(pe+1);
2074         CmiInt8 e=s+n;
2075         if (s<p_s) s=p_s;
2076         if (e>p_e) e=p_e;
2077         n=e-s;
2078
2079 /*Send off range*/
2080         if (pe==CmiMyPe()) 
2081                 op->local(CpvAccess(myss),s,n);
2082         else 
2083         {/*Remote request*/
2084                 slotmsg *m=prepare_slotmsg(s,n);
2085                 CmiSetHandler(m, freeOP.remote);
2086                 CmiSyncSendAndFree(pe,sizeof(slotmsg),m);
2087         }
2088 }
2089
2090 /*Apply the given operation to all slots in the range [s, s+n) 
2091 After a restart from checkpoint, a slotset can cross an 
2092 arbitrary set of processors.
2093 */
2094 static void all_slotOP(const slotOP *op,CmiInt8 s,CmiInt8 n)
2095 {
2096         int spe=slot2pe(s), epe=slot2pe(s+n-1);
2097         int pe;
2098         for (pe=spe; pe<=epe; pe++)
2099                 one_slotOP(op,pe,s,n);
2100 }
2101
2102 /************** External interface ***************/
2103 void *CmiIsomalloc(int size)
2104 {
2105         CmiInt8 s,n;
2106         CmiIsomallocBlock *blk;
2107         if (isomallocStart==NULL) return disabled_map(size);
2108         n=length2slots(size);
2109         /*Always satisfy mallocs with local slots:*/
2110         s=get_slots(CpvAccess(myss),n);
2111         if (s==-1) {
2112                 CmiError("Not enough address space left on processor %d to isomalloc %d bytes!\n",
2113                          CmiMyPe(),size);
2114                 CmiAbort("Out of virtual address space for isomalloc");
2115         }
2116         grab_slots(CpvAccess(myss),s,n);
2117         blk=map_slots(s,n);
2118         if (!blk) map_failed(s,n);
2119         blk->slot=s;
2120         blk->length=size;
2121         return block2pointer(blk);
2122 }
2123
2124 void CmiIsomallocPup(pup_er p,void **blockPtrPtr)
2125 {
2126         CmiIsomallocBlock *blk;
2127         CmiInt8 s,length;
2128         CmiInt8 n;
2129         if (isomallocStart==NULL) CmiAbort("isomalloc is disabled-- cannot use IsomallocPup");
2130
2131         if (!pup_isUnpacking(p)) 
2132         { /*We have an existing block-- unpack start slot & length*/
2133                 blk=pointer2block(*blockPtrPtr);
2134                 s=blk->slot;
2135                 length=blk->length;
2136         }
2137         
2138         pup_int8(p,&s);
2139         pup_int8(p,&length);
2140         n=length2slots(length);
2141         
2142         if (pup_isUnpacking(p)) 
2143         { /*Must allocate a new block in its old location*/
2144                 if (pup_isUserlevel(p) || pup_isRestarting(p))
2145                         /*Checkpoint: must grab old slots (even remote!)*/
2146                         all_slotOP(&grabOP,s,n);
2147                 blk=map_slots(s,n);
2148                 if (!blk) map_failed(s,n);
2149                 blk->slot=s;
2150                 blk->length=length;
2151                 *blockPtrPtr=block2pointer(blk);
2152         }
2153         
2154         /*Pup the allocated data*/
2155         pup_bytes(p,*blockPtrPtr,length);
2156         
2157         if (pup_isDeleting(p)) 
2158         { /*Unmap old slots, but do not mark as free*/
2159                 unmap_slots(s,n);
2160                 *blockPtrPtr=NULL; /*Zero out user's pointer*/
2161         }
2162 }
2163
2164 void CmiIsomallocFree(void *blockPtr)
2165 {
2166         if (isomallocStart==NULL) {
2167                 disabled_unmap(blockPtr);
2168         }
2169         else if (blockPtr!=NULL)
2170         {
2171                 CmiIsomallocBlock *blk=pointer2block(blockPtr);
2172                 CmiInt8 s=blk->slot; 
2173                 CmiInt8 n=length2slots(blk->length);
2174                 unmap_slots(s,n);
2175                 /*Mark used slots as free*/
2176                 all_slotOP(&freeOP,s,n);
2177         }
2178 }
2179
2180 CmiInt8   CmiIsomallocLength(void *block)
2181 {
2182         return pointer2block(block)->length;
2183 }
2184
2185 /*Return true if this address is in the region managed by isomalloc*/
2186 int CmiIsomallocInRange(void *addr)
2187 {
2188         if (isomallocStart==NULL) return 0; /* There is no range we manage! */
2189         return pointer_ge((char *)addr,isomallocStart) && 
2190                pointer_lt((char*)addr,isomallocEnd);
2191 }
2192
2193 void CmiIsomallocInit(char **argv)
2194 {
2195 #if CMK_NO_ISO_MALLOC
2196   disable_isomalloc("isomalloc disabled by conv-mach");
2197 #else
2198   if (CmiGetArgFlagDesc(argv,"+isomalloc_sync","synchronize isomalloc region globaly"))
2199   _sync_iso = 1;
2200   init_comm(argv);
2201   if (!init_map(argv)) {
2202     disable_isomalloc("mmap() does not work");
2203   }
2204   else {
2205     if (read_randomflag() == 1) {    /* randomization stack pointer */
2206       if (CmiMyPe() == 0)
2207         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");
2208     }
2209     init_ranges(argv);
2210   }
2211 #endif
2212 }
2213
2214 /***************** BlockList interface *********
2215 This was moved here from memory-isomalloc.c when it 
2216 was realized that a list-of-isomalloc'd-blocks is useful for
2217 more than just isomalloc heaps.
2218 */
2219
2220 typedef CmiIsomallocBlockList Slot;
2221
2222 /*Convert a slot to a user address*/
2223 static char *Slot_toUser(Slot *s) {return (char *)(s+1);}
2224 static Slot *Slot_fmUser(void *s) {return ((Slot *)s)-1;}
2225
2226
2227 /*Build a new blockList.*/
2228 CmiIsomallocBlockList *CmiIsomallocBlockListNew(void)
2229 {
2230         CmiIsomallocBlockList *ret;
2231         ret=(CmiIsomallocBlockList *)CmiIsomalloc(sizeof(*ret));
2232         ret->next=ret; /*1-entry circular linked list*/
2233         ret->prev=ret;
2234         return ret;
2235 }
2236
2237
2238 //BIGSIM_OOC DEBUGGING
2239 static void print_myslots();
2240
2241 /*Pup all the blocks in this list.  This amounts to two circular
2242 list traversals.  Because everything's isomalloc'd, we don't even
2243 have to restore the pointers-- they'll be restored automatically!
2244 */
2245 void CmiIsomallocBlockListPup(pup_er p,CmiIsomallocBlockList **lp)
2246 {
2247         //BIGSIM_OOC DEBUGGING
2248         //if(!pup_isUnpacking(p)) print_myslots();
2249
2250         int i,nBlocks=0;
2251         Slot *cur=NULL, *start=*lp;
2252 #if 0 /*#ifndef CMK_OPTIMIZE*/
2253         if (CpvAccess(isomalloc_blocklist)!=NULL)
2254                 CmiAbort("Called CmiIsomallocBlockListPup while a blockList is active!\n"
2255                         "You should swap out the active blocklist before pupping.\n");
2256 #endif
2257         /*Count the number of blocks in the list*/
2258         if (!pup_isUnpacking(p)) {
2259                 nBlocks=1; /*<- Since we have to skip the start block*/
2260                 for (cur=start->next; cur!=start; cur=cur->next) 
2261                         nBlocks++;
2262                 /*Prepare for next trip around list:*/
2263                 cur=start;
2264         }
2265         pup_int(p,&nBlocks);
2266         
2267         /*Pup each block in the list*/
2268         for (i=0;i<nBlocks;i++) {
2269                 void *newBlock=cur;
2270                 if (!pup_isUnpacking(p)) 
2271                 { /*While packing, we traverse the list to find our blocks*/
2272                         cur=cur->next;
2273                 }
2274                 CmiIsomallocPup(p,&newBlock);
2275                 if (i==0 && pup_isUnpacking(p))
2276                         *lp=(Slot *)newBlock;
2277         }
2278         if (pup_isDeleting(p))
2279                 *lp=NULL;
2280
2281         //BIGSIM_OOC DEBUGGING
2282         //if(pup_isUnpacking(p)) print_myslots();
2283 }
2284
2285 /*Delete all the blocks in this list.*/
2286 void CmiIsomallocBlockListDelete(CmiIsomallocBlockList *l)
2287 {
2288         Slot *start=l;
2289         Slot *cur=start;
2290         if (cur==NULL) return; /*Already deleted*/
2291         do {
2292                 Slot *doomed=cur;
2293                 cur=cur->next; /*Have to stash next before deleting cur*/
2294                 CmiIsomallocFree(doomed);
2295         } while (cur!=start);
2296 }
2297
2298 /*Allocate a block from this blockList*/
2299 void *CmiIsomallocBlockListMalloc(CmiIsomallocBlockList *l,int nBytes)
2300 {
2301         Slot *n; /*Newly created slot*/
2302         n=(Slot *)CmiIsomalloc(sizeof(Slot)+nBytes);
2303         /*Link the new block into the circular blocklist*/
2304         n->prev=l;
2305         n->next=l->next;
2306         l->next->prev=n;
2307         l->next=n;
2308         return Slot_toUser(n);
2309 }
2310
2311 /*Remove this block from its list and memory*/
2312 void CmiIsomallocBlockListFree(void *block)
2313 {
2314         Slot *n=Slot_fmUser(block);
2315 #if DOHEAPCHECK
2316         if (n->prev->next!=n || n->next->prev!=n) 
2317                 CmiAbort("Heap corruption detected in isomalloc block list header!\n"
2318                         "  Run with ++debug and look for writes to negative array indices");
2319 #endif
2320         /*Link ourselves out of the blocklist*/
2321         n->prev->next=n->next;
2322         n->next->prev=n->prev;
2323         CmiIsomallocFree(n);
2324 }
2325
2326
2327
2328 //BIGSIM_OOC DEBUGGING
2329 static void print_myslots(){
2330     CmiPrintf("[%d] my slot set=%p\n", CmiMyPe(), CpvAccess(myss));
2331     print_slots(CpvAccess(myss));
2332 }
2333
2334
2335