4af2dedb3baf84190854ba3d79617473b6687c36
[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] (%d, %d) \n", CmiMyPe(), ss->buf[i].startslot, 
1418           ss->buf[i].nslots);
1419   }
1420 }
1421 #else
1422 #  define print_slots(ss) /*empty*/
1423 #endif
1424
1425
1426 #endif
1427
1428 /* ======================= END OLD ISOMALLOC ============================ */
1429
1430
1431 /*This version of the allocate/deallocate calls are used if the 
1432 real mmap versions are disabled.*/
1433 static int disabled_map_warned=0;
1434 static void *disabled_map(int nBytes) 
1435 {
1436         if (!disabled_map_warned) {
1437                 disabled_map_warned=1;
1438                 if (CmiMyPe()==0)
1439                         CmiError("charm isomalloc.c> Warning: since mmap() doesn't work,"
1440                         " you won't be able to migrate threads\n");
1441         }
1442         return malloc(nBytes);
1443 }
1444 static void disabled_unmap(void *bk) {
1445         free(bk);
1446 }
1447
1448 /*Turn off isomalloc memory, for the given reason*/
1449 static void disable_isomalloc(const char *why)
1450 {
1451     isomallocStart=NULL;
1452     isomallocEnd=NULL;
1453 #if CMK_THREADS_DEBUG
1454     CmiPrintf("[%d] isomalloc.c> Disabling isomalloc because %s\n",CmiMyPe(),why);
1455 #endif
1456 }
1457
1458 #if ! CMK_HAS_MMAP
1459 /****************** Manipulate memory map (Win32 non-version) *****************/
1460 static void *call_mmap_fixed(void *addr,size_t len) {
1461         CmiAbort("isomalloc.c: mmap_fixed should never be called here.");
1462         return NULL;
1463 }
1464 static void *call_mmap_anywhere(size_t len) {
1465         CmiAbort("isomalloc.c: mmap_anywhere should never be called here.");
1466         return NULL;
1467 }
1468 static void call_munmap(void *addr,size_t len) {
1469         CmiAbort("isomalloc.c: munmap should never be called here.");
1470 }
1471
1472 static int 
1473 init_map(char **argv)
1474 {
1475   return 0; /*Isomalloc never works without mmap*/
1476 }
1477 #else /* CMK_HAS_MMAP */
1478 /****************** Manipulate memory map (UNIX version) *****************/
1479 #include <sys/types.h>
1480 #include <sys/mman.h>
1481 #include <sys/stat.h>
1482 #include <fcntl.h>
1483
1484 #if !CMK_HAS_MMAP_ANON
1485 CpvStaticDeclare(int, zerofd); /*File descriptor for /dev/zero, for mmap*/
1486 #endif
1487
1488 /**
1489  * Maps this address with these flags.
1490  */
1491 static void *call_mmap(void *addr,size_t len, int flags) {
1492   void *ret=mmap(addr, len, PROT_READ|PROT_WRITE,
1493 #if CMK_HAS_MMAP_ANON
1494             flags|MAP_PRIVATE|MAP_ANON,-1,
1495 #else
1496             flags|MAP_PRIVATE,CpvAccess(zerofd),
1497 #endif
1498             0);
1499   if (ret==((void*)(-1))) return (void *)0; /* all-ones means failure */
1500   else return ret;
1501 }
1502 static void *call_mmap_fixed(void *addr,size_t len) {
1503         return call_mmap(addr,len,MAP_FIXED);
1504 }
1505 static void *call_mmap_anywhere(size_t len) {
1506         return call_mmap((void *)0,len,0);
1507 }
1508
1509 /* Unmaps this address range */
1510 static void call_munmap(void *addr,size_t len) {
1511   int retval;
1512   if (addr == 0) return; /* NULL address is never mapped */ 
1513   retval = munmap(addr, len);
1514   if (retval==(-1))
1515     CmiAbort("munmap call failed to deallocate requested memory.\n");
1516 }
1517
1518 static int 
1519 init_map(char **argv)
1520 {
1521 #if CMK_HAS_MMAP_ANON
1522   /*Don't need /dev/zero*/
1523 #else
1524   CpvInitialize(int, zerofd);  
1525   CpvAccess(zerofd) = open("/dev/zero", O_RDWR);
1526   if(CpvAccess(zerofd)<0)
1527     return 0; /* Cannot open /dev/zero or use MMAP_ANON, so can't mmap memory */
1528 #endif
1529   return 1;
1530 }
1531
1532 #endif /* UNIX memory map */
1533
1534
1535 /**
1536  * maps the virtual memory associated with slot using mmap
1537  */
1538 static CmiIsomallocBlock *
1539 map_slots(CmiInt8 slot, CmiInt8 nslots)
1540 {
1541   void *pa;
1542   void *addr=slot2addr(slot);
1543   pa = call_mmap_fixed(addr, slotsize*nslots);
1544   
1545   if (pa==NULL) 
1546   { /*Map just failed completely*/
1547 #if CMK_THREADS_DEBUG
1548     perror("mmap failed");
1549     CmiPrintf("[%d] tried to mmap %p, but encountered error\n",CmiMyPe(),addr);
1550 #endif
1551     return NULL;
1552   }
1553   if (pa != addr)
1554   { /*Map worked, but gave us back the wrong place*/
1555 #if CMK_THREADS_DEBUG
1556     CmiPrintf("[%d] tried to mmap %p, but got %p back\n",CmiMyPe(),addr,pa);
1557 #endif
1558     call_munmap(addr,slotsize*nslots);
1559     return NULL;
1560   }
1561 #if CMK_THREADS_DEBUG
1562   CmiPrintf("[%d] mmap'd slots %ld-%ld to address %p\n",CmiMyPe(),
1563             slot,slot+nslots-1,addr);
1564 #endif
1565   return (CmiIsomallocBlock *)pa;
1566 }
1567
1568 /*
1569  * unmaps the virtual memory associated with slot using munmap
1570  */
1571 static void
1572 unmap_slots(CmiInt8 slot, CmiInt8 nslots)
1573 {
1574   void *addr=slot2addr(slot);
1575   call_munmap(addr, slotsize*nslots);
1576 #if CMK_THREADS_DEBUG
1577   CmiPrintf("[%d] munmap'd slots %ld-%ld from address %p\n",CmiMyPe(),
1578             slot,slot+nslots-1,addr);
1579 #endif
1580 }
1581
1582 static void map_failed(CmiInt8 s,CmiInt8 n)
1583 {
1584   void *addr=slot2addr(s);
1585   CmiError("charm isomalloc.c> map failed to allocate %d bytes at %p.\n",
1586       slotsize*n, addr);
1587   CmiAbort("Exiting\n");
1588 }
1589
1590
1591
1592 /************ Address space voodoo: find free address range **********/
1593
1594 CpvStaticDeclare(slotset *, myss); /*My managed slots*/
1595
1596 /*This struct describes a range of virtual addresses*/
1597 typedef struct {
1598   char *start; /*First byte of region*/
1599   memRange_t len; /*Number of bytes in region*/
1600   const char *type; /*String describing memory in region (debugging only)*/
1601 } memRegion_t;
1602
1603 /*Estimate the top of the current stack*/
1604 static void *__cur_stack_frame(void)
1605 {
1606   char __dummy;
1607   void *top_of_stack=(void *)&__dummy;
1608   return top_of_stack;
1609 }
1610 /*Estimate the location of the static data region*/
1611 static void *__static_data_loc(void)
1612 {
1613   static char __dummy;
1614   return (void *)&__dummy;
1615 }
1616
1617 /*Pointer comparison is in these subroutines, because
1618   comparing arbitrary pointers is nonportable and tricky.
1619 */
1620 static int pointer_lt(const char *a,const char *b) {
1621         return ((memRange_t)a)<((memRange_t)b);
1622 }
1623 static int pointer_ge(const char *a,const char *b) {
1624         return ((memRange_t)a)>=((memRange_t)b);
1625 }
1626
1627 static char *pmin(char *a,char *b) {return pointer_lt(a,b)?a:b;}
1628 static char *pmax(char *a,char *b) {return pointer_lt(a,b)?b:a;}
1629
1630 const static memRange_t meg=1024u*1024u; /*One megabyte*/
1631 const static memRange_t gig=1024u*1024u*1024u; /*One gigabyte*/
1632
1633 /*Check if this memory location is usable.  
1634   If not, return 1.
1635 */
1636 static int bad_location(char *loc) {
1637   void *addr;
1638   addr=call_mmap_fixed(loc,slotsize);
1639   if (addr==NULL) {
1640 #if CMK_THREADS_DEBUG
1641     CmiPrintf("[%d] Skipping unmappable space at %p\n",CmiMyPe(),loc);
1642 #endif
1643     return 1; /*No good*/
1644   }
1645   call_munmap(addr,slotsize);
1646   return 0; /*This works*/
1647 }
1648
1649 /* Split this range up into n pieces, returning the size of each piece */
1650 static memRange_t divide_range(memRange_t len,int n) {
1651         return (len+1)/n;
1652 }
1653
1654 /* Return if this memory region has *any* good parts. */
1655 static int partially_good(char *start,memRange_t len,int n) {
1656   int i;
1657   memRange_t quant=divide_range(len,n);
1658   for (i=0;i<n;i++)
1659     if (!bad_location(start+i*quant)) return 1; /* it's got some good parts */
1660   return 0; /* all locations are bad */
1661 }
1662
1663 /* Return if this memory region is usable at n samples.  
1664 */
1665 static int good_range(char *start,memRange_t len,int n) {
1666   int i;
1667   memRange_t quant=divide_range(len,n);
1668   for (i=0;i<n;i++)
1669     if (bad_location(start+i*quant)) return 0; /* it's got some bad parts */
1670   /* It's all good: */
1671   return 1;
1672 }
1673
1674 /*Check if this entire memory range, or some subset 
1675   of the range, is usable.  If so, write it into max.
1676 */
1677 static void check_range(char *start,char *end,memRegion_t *max)
1678 {
1679   memRange_t len;
1680   char *initialStart=start, *initialEnd=end;
1681   CmiUInt8 tb = (CmiUInt8)gig*1024ul;   /* One terabyte */
1682   CmiUInt8 vm_limit = tb*256ul;   /* terabyte */
1683
1684   if (start>=end) return; /*Ran out of hole*/
1685   len=(memRange_t)end-(memRange_t)start;
1686   
1687 #if 0
1688     /* too conservative */
1689   if (len/gig>64u) { /* This is an absurd amount of space-- cut it down, for safety */
1690      start+=16u*gig;
1691      end=start+32u*gig;
1692      len=(memRange_t)end-(memRange_t)start;  
1693   }
1694 #else
1695   /* Note: 256TB == 248 bytes.  So a 48-bit virtual-address CPU 
1696    *    can only actually address 256TB of space. */
1697   if (len/tb>10u) { /* This is an absurd amount of space-- cut it down, for safety */
1698     const memRange_t other_libs=16ul*gig; /* space for other libraries to use */
1699     start+=other_libs;
1700     end=pmin(start+vm_limit-2*other_libs, end-other_libs);
1701     len=(memRange_t)end-(memRange_t)start;
1702   }
1703 #endif
1704   if (len<=max->len) return; /*It's too short already!*/
1705 #if CMK_THREADS_DEBUG
1706   CmiPrintf("[%d] Checking at %p - %p\n",CmiMyPe(),start,end);
1707 #endif
1708   
1709   /* Check the middle of the range */
1710   if (!good_range(start,len,256)) {
1711     /* Try to split into subranges: */
1712     int i,n=2;
1713 #if CMK_THREADS_DEBUG
1714     CmiPrintf("[%d] Trying to split bad address space at %p - %p...\n",CmiMyPe(),start,end);
1715 #endif
1716     len=divide_range(len,n);
1717     for (i=0;i<n;i++) {
1718         char *cur=start+i*len;
1719         if (partially_good(cur,len,16))
1720            check_range(cur,cur+len,max);
1721     }
1722     return; /* Hopefully one of the subranges will be any good */
1723   }
1724   else /* range is good */
1725   { 
1726 #if CMK_THREADS_DEBUG
1727     CmiPrintf("[%d] Address space at %p - %p is largest\n",CmiMyPe(),start,end);
1728 #endif
1729
1730     /*If we got here, we're the new largest usable range*/
1731     max->len=len;
1732     max->start=start;
1733     max->type="Unused";
1734   }
1735 }
1736
1737 /*Find the first available memory region of at least the
1738   given size not touching any data in the used list.
1739  */
1740 static memRegion_t find_free_region(memRegion_t *used,int nUsed,int atLeast) 
1741 {
1742   memRegion_t max;
1743   int i,j;  
1744
1745   max.start=0; 
1746   max.len=atLeast;
1747   /*Find the largest hole between regions*/
1748   for (i=0;i<nUsed;i++) {
1749     /*Consider a hole starting at the end of region i*/
1750     char *holeStart=used[i].start+used[i].len;
1751     char *holeEnd=(void *)(-1);
1752     
1753     /*Shrink the hole by all others*/ 
1754     for (j=0;j<nUsed && pointer_lt(holeStart,holeEnd);j++) {
1755       if (pointer_lt(used[j].start,holeStart)) 
1756         holeStart=pmax(holeStart,used[j].start+used[j].len);
1757       else if (pointer_lt(used[j].start,holeEnd)) 
1758         holeEnd=pmin(holeEnd,used[j].start);
1759     } 
1760
1761     check_range(holeStart,holeEnd,&max);
1762   }
1763
1764   return max; 
1765 }
1766
1767 /*
1768 By looking at the address range carefully, try to find 
1769 the largest usable free region on the machine.
1770 */
1771 static int find_largest_free_region(memRegion_t *destRegion) {
1772     char *staticData =(char *) __static_data_loc();
1773     char *code = (char *)&find_free_region;
1774     char *threadData = (char *)&errno;
1775     char *codeDll = (char *)fprintf;
1776     char *heapLil = (char*) malloc(1);
1777     char *heapBig = (char*) malloc(6*meg);
1778     char *stack = (char *)__cur_stack_frame();
1779     size_t mmapAnyLen = 1*meg;
1780     char *mmapAny = (char*) call_mmap_anywhere(mmapAnyLen);
1781
1782     int i,nRegions=9;
1783     memRegion_t regions[10]; /*used portions of address space*/
1784     memRegion_t freeRegion; /*Largest unused block of address space*/
1785
1786 /*Mark off regions of virtual address space as ususable*/
1787     regions[0].type="NULL";
1788     regions[0].start=NULL; regions[0].len=16u*meg;
1789     
1790     regions[1].type="Static program data";
1791     regions[1].start=staticData; regions[1].len=256u*meg;
1792     
1793     regions[2].type="Program executable code";
1794     regions[2].start=code; regions[2].len=256u*meg;
1795     
1796     regions[3].type="Heap (small blocks)";
1797     regions[3].start=heapLil; regions[3].len=1u*gig;
1798     
1799     regions[4].type="Heap (large blocks)";
1800     regions[4].start=heapBig; regions[4].len=1u*gig;
1801     
1802     regions[5].type="Stack space";
1803     regions[5].start=stack; regions[5].len=256u*meg;
1804
1805     regions[6].type="Program dynamically linked code";
1806     regions[6].start=codeDll; regions[6].len=256u*meg; 
1807
1808     regions[7].type="Result of a non-fixed call to mmap";
1809     regions[7].start=mmapAny; regions[7].len=1u*gig; 
1810
1811     regions[8].type="Thread private data";
1812     regions[8].start=threadData; regions[8].len=256u*meg; 
1813
1814     _MEMCHECK(heapBig); free(heapBig);
1815     _MEMCHECK(heapLil); free(heapLil); 
1816     call_munmap(mmapAny,mmapAnyLen);
1817     
1818     /*Align each memory region*/
1819     for (i=0;i<nRegions;i++) {
1820       /* memRegion_t old=regions[i]; */
1821       memRange_t p=(memRange_t)regions[i].start;
1822       p&=~(regions[i].len-1); /*Round start down to a len-boundary (mask off low bits)*/
1823       regions[i].start=(char *)p;
1824 #if CMK_THREADS_DEBUG
1825       CmiPrintf("[%d] Memory map: %p - %p %s (at %p)\n",CmiMyPe(),
1826               regions[i].start,regions[i].start+regions[i].len,
1827               regions[i].type, old.start);
1828 #endif
1829     }
1830     
1831     /*Find a large, unused region in this map: */
1832     freeRegion=find_free_region(regions,nRegions,(512u)*meg);
1833     
1834     if (freeRegion.start==0) 
1835     { /*No free address space-- disable isomalloc:*/
1836       return 0;
1837     }
1838     else /* freeRegion is valid */
1839     {
1840       *destRegion=freeRegion;
1841       
1842       return 1;
1843     }
1844 }
1845
1846 #ifndef CMK_CPV_IS_SMP
1847 #define CMK_CPV_IS_SMP
1848 #endif
1849
1850 static void init_ranges(char **argv)
1851 {
1852   /*Largest value a signed int can hold*/
1853   memRange_t intMax=(((memRange_t)1)<<(sizeof(int)*8-1))-1;
1854
1855   /*Round slot size up to nearest page size*/
1856   slotsize=16*1024;
1857   slotsize=(slotsize+CMK_MEMORY_PAGESIZE-1) & ~(CMK_MEMORY_PAGESIZE-1);
1858 #if CMK_THREADS_DEBUG
1859   CmiPrintf("[%d] Using slotsize of %d\n", CmiMyPe(), slotsize);
1860 #endif
1861
1862   if (CmiMyRank()==0 && numslots==0)
1863   { /* Find the largest unused region of virtual address space */
1864       memRegion_t freeRegion;
1865       freeRegion.len=0u;
1866 #ifdef CMK_MMAP_START_ADDRESS /* Hardcoded start address, for machines where automatic fails */
1867       freeRegion.start=CMK_MMAP_START_ADDRESS;
1868       freeRegion.len=CMK_MMAP_LENGTH_MEGS*meg;
1869 #endif
1870       if (freeRegion.len==0u) find_largest_free_region(&freeRegion);
1871       
1872 #if 0
1873       /*Make sure our largest slot number doesn't overflow an int:*/
1874       if (freeRegion.len/slotsize>intMax)
1875         freeRegion.len=intMax*slotsize;
1876 #endif
1877       
1878       if (freeRegion.len==0u) {
1879         disable_isomalloc("no free virtual address space");
1880       }
1881       else /* freeRegion.len>0, so can isomalloc */
1882       {
1883 #if CMK_THREADS_DEBUG
1884         CmiPrintf("[%d] Isomalloc memory region: %p - %p (%d megs)\n",CmiMyPe(),
1885               freeRegion.start,freeRegion.start+freeRegion.len,
1886               freeRegion.len/meg);
1887 #endif
1888         
1889           /*
1890              on some machines, isomalloc memory regions on different nodes 
1891              can be different. use +isomalloc_sync to calculate the
1892              intersect of all memory regions on all nodes.
1893           */
1894         if (_sync_iso == 1) {
1895           if (CmiBarrier() == -1) 
1896             CmiAbort("Charm++ Error> +isomalloc_sync requires CmiBarrier() implemented.\n");
1897           else {
1898             CmiUInt8 s = (CmiUInt8)freeRegion.start;
1899             CmiUInt8 e = (CmiUInt8)(freeRegion.start+freeRegion.len);
1900             int fd, i;
1901             char fname[128];
1902
1903             if (CmiMyNode()==0) printf("Charm++> synchronizing isomalloc memory region...\n");
1904
1905               /* write region into file */
1906             sprintf(fname,".isomalloc.%d", CmiMyNode());
1907             while ((fd = open(fname, O_WRONLY|O_TRUNC|O_CREAT, 0644)) == -1) 
1908 #ifndef __MINGW_H
1909               CMK_CPV_IS_SMP
1910 #endif
1911             ;
1912             write(fd, &s, sizeof(CmiUInt8));
1913             write(fd, &e, sizeof(CmiUInt8));
1914             close(fd);
1915
1916             CmiBarrier();
1917
1918             for (i=0; i<CmiNumNodes(); i++) {
1919               CmiUInt8 ss, ee; 
1920               char fname[128];
1921               if (i==CmiMyNode()) continue;
1922               sprintf(fname,".isomalloc.%d", i);
1923               while ((fd = open(fname, O_RDONLY)) == -1)
1924 #ifndef __MINGW_H
1925               CMK_CPV_IS_SMP
1926 #endif
1927               ;
1928               read(fd, &ss, sizeof(CmiUInt8));
1929               read(fd, &ee, sizeof(CmiUInt8));
1930               close(fd);
1931               if (ss>s) s = ss;
1932               if (ee<e) e = ee;
1933             }
1934
1935             CmiBarrier();
1936
1937             unlink(fname);
1938
1939               /* update */
1940             freeRegion.start = (void *)s;
1941             freeRegion.len = (char *)e -(char *)s;
1942 #if CMK_THREADS_DEBUG
1943             CmiPrintf("[%d] consolidated Isomalloc memory region: %p - %p (%d megs)\n",CmiMyPe(),
1944               freeRegion.start,freeRegion.start+freeRegion.len,
1945               freeRegion.len/meg);
1946 #endif
1947           }   /* end of barrier test */
1948         }
1949
1950         /*Isomalloc covers entire unused region*/
1951         isomallocStart=freeRegion.start;
1952         isomallocEnd=freeRegion.start+freeRegion.len;
1953         numslots=(freeRegion.len/slotsize)/CmiNumPes();
1954         
1955 #if CMK_THREADS_DEBUG
1956         CmiPrintf("[%d] Can isomalloc up to %lu megs per pe\n",CmiMyPe(),
1957               ((memRange_t)numslots)*slotsize/meg);
1958 #endif
1959       }
1960   }
1961   /*SMP Mode: wait here for rank 0 to initialize numslots so we can set up myss*/
1962   CmiNodeAllBarrier(); 
1963   
1964   if (isomallocStart!=NULL) {
1965     CpvInitialize(slotset *, myss);
1966     CpvAccess(myss) = new_slotset(pe2slot(CmiMyPe()), numslots);
1967   }
1968 }
1969
1970
1971 /************* Communication: for grabbing/freeing remote slots *********/
1972 typedef struct _slotmsg
1973 {
1974   char cmicore[CmiMsgHeaderSizeBytes];
1975   int pe; /*Source processor*/
1976   CmiInt8 slot; /*First requested slot*/
1977   CmiInt8 nslots; /*Number of requested slots*/
1978 } slotmsg;
1979
1980 static slotmsg *prepare_slotmsg(CmiInt8 slot,CmiInt8 nslots)
1981 {
1982         slotmsg *m=(slotmsg *)CmiAlloc(sizeof(slotmsg));
1983         m->pe=CmiMyPe();
1984         m->slot=slot;
1985         m->nslots=nslots;
1986         return m;
1987 }
1988
1989 static void grab_remote(slotmsg *msg)
1990 {
1991         grab_slots(CpvAccess(myss),msg->slot,msg->nslots);
1992         CmiFree(msg);
1993 }
1994
1995 static void free_remote(slotmsg *msg)
1996 {
1997         free_slots(CpvAccess(myss),msg->slot,msg->nslots);
1998         CmiFree(msg);
1999 }
2000 static int grab_remote_idx, free_remote_idx;
2001
2002 struct slotOP {
2003         /*Function pointer to perform local operation*/
2004         void (*local)(slotset *ss,CmiInt8 s,CmiInt8 n);
2005         /*Index to perform remote operation*/
2006         int remote;
2007 };
2008 typedef struct slotOP slotOP;
2009 static slotOP grabOP,freeOP;
2010
2011 static void init_comm(char **argv)
2012 {
2013         grab_remote_idx=CmiRegisterHandler((CmiHandler)grab_remote);
2014         free_remote_idx=CmiRegisterHandler((CmiHandler)free_remote);    
2015         grabOP.local=grab_slots;
2016         grabOP.remote=grab_remote_idx;
2017         freeOP.local=free_slots;
2018         freeOP.remote=free_remote_idx;  
2019 }
2020
2021 /*Apply the given operation to the given slots which
2022   lie on the given processor.*/
2023 static void one_slotOP(const slotOP *op,int pe,CmiInt8 s,CmiInt8 n)
2024 {
2025 /*Shrink range to only those covered by this processor*/
2026         /*First and last slot for this processor*/
2027         CmiInt8 p_s=pe2slot(pe), p_e=pe2slot(pe+1);
2028         CmiInt8 e=s+n;
2029         if (s<p_s) s=p_s;
2030         if (e>p_e) e=p_e;
2031         n=e-s;
2032
2033 /*Send off range*/
2034         if (pe==CmiMyPe()) 
2035                 op->local(CpvAccess(myss),s,n);
2036         else 
2037         {/*Remote request*/
2038                 slotmsg *m=prepare_slotmsg(s,n);
2039                 CmiSetHandler(m, freeOP.remote);
2040                 CmiSyncSendAndFree(pe,sizeof(slotmsg),m);
2041         }
2042 }
2043
2044 /*Apply the given operation to all slots in the range [s, s+n) 
2045 After a restart from checkpoint, a slotset can cross an 
2046 arbitrary set of processors.
2047 */
2048 static void all_slotOP(const slotOP *op,CmiInt8 s,CmiInt8 n)
2049 {
2050         int spe=slot2pe(s), epe=slot2pe(s+n-1);
2051         int pe;
2052         for (pe=spe; pe<=epe; pe++)
2053                 one_slotOP(op,pe,s,n);
2054 }
2055
2056 /************** External interface ***************/
2057 void *CmiIsomalloc(int size)
2058 {
2059         CmiInt8 s,n;
2060         CmiIsomallocBlock *blk;
2061         if (isomallocStart==NULL) return disabled_map(size);
2062         n=length2slots(size);
2063         /*Always satisfy mallocs with local slots:*/
2064         s=get_slots(CpvAccess(myss),n);
2065         if (s==-1) {
2066                 CmiError("Not enough address space left on processor %d to isomalloc %d bytes!\n",
2067                          CmiMyPe(),size);
2068                 CmiAbort("Out of virtual address space for isomalloc");
2069         }
2070         grab_slots(CpvAccess(myss),s,n);
2071         blk=map_slots(s,n);
2072         if (!blk) map_failed(s,n);
2073         blk->slot=s;
2074         blk->length=size;
2075         return block2pointer(blk);
2076 }
2077
2078 void CmiIsomallocPup(pup_er p,void **blockPtrPtr)
2079 {
2080         CmiIsomallocBlock *blk;
2081         CmiInt8 s,length;
2082         CmiInt8 n;
2083         if (isomallocStart==NULL) CmiAbort("isomalloc is disabled-- cannot use IsomallocPup");
2084
2085         if (!pup_isUnpacking(p)) 
2086         { /*We have an existing block-- unpack start slot & length*/
2087                 blk=pointer2block(*blockPtrPtr);
2088                 s=blk->slot;
2089                 length=blk->length;
2090         }
2091         
2092         pup_int8(p,&s);
2093         pup_int8(p,&length);
2094         n=length2slots(length);
2095         
2096         if (pup_isUnpacking(p)) 
2097         { /*Must allocate a new block in its old location*/
2098                 if (pup_isUserlevel(p) || pup_isRestarting(p))
2099                         /*Checkpoint: must grab old slots (even remote!)*/
2100                         all_slotOP(&grabOP,s,n);
2101                 blk=map_slots(s,n);
2102                 if (!blk) map_failed(s,n);
2103                 blk->slot=s;
2104                 blk->length=length;
2105                 *blockPtrPtr=block2pointer(blk);
2106         }
2107         
2108         /*Pup the allocated data*/
2109         pup_bytes(p,*blockPtrPtr,length);
2110         
2111         if (pup_isDeleting(p)) 
2112         { /*Unmap old slots, but do not mark as free*/
2113                 unmap_slots(s,n);
2114                 *blockPtrPtr=NULL; /*Zero out user's pointer*/
2115         }
2116 }
2117
2118 void CmiIsomallocFree(void *blockPtr)
2119 {
2120         if (isomallocStart==NULL) {
2121                 disabled_unmap(blockPtr);
2122         }
2123         else if (blockPtr!=NULL)
2124         {
2125                 CmiIsomallocBlock *blk=pointer2block(blockPtr);
2126                 CmiInt8 s=blk->slot; 
2127                 CmiInt8 n=length2slots(blk->length);
2128                 unmap_slots(s,n);
2129                 /*Mark used slots as free*/
2130                 all_slotOP(&freeOP,s,n);
2131         }
2132 }
2133
2134 CmiInt8   CmiIsomallocLength(void *block)
2135 {
2136         return pointer2block(block)->length;
2137 }
2138
2139 /*Return true if this address is in the region managed by isomalloc*/
2140 int CmiIsomallocInRange(void *addr)
2141 {
2142         if (isomallocStart==NULL) return 0; /* There is no range we manage! */
2143         return pointer_ge((char *)addr,isomallocStart) && 
2144                pointer_lt((char*)addr,isomallocEnd);
2145 }
2146
2147 void CmiIsomallocInit(char **argv)
2148 {
2149 #if CMK_NO_ISO_MALLOC
2150   disable_isomalloc("isomalloc disabled by conv-mach");
2151 #else
2152   if (CmiGetArgFlagDesc(argv,"+isomalloc_sync","synchronize isomalloc region globaly"))
2153   _sync_iso = 1;
2154   init_comm(argv);
2155   if (!init_map(argv)) {
2156     disable_isomalloc("mmap() does not work");
2157   }
2158   else {
2159     if (read_randomflag() == 1) {    /* randomization stack pointer */
2160       if (CmiMyPe() == 0)
2161         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");
2162     }
2163     init_ranges(argv);
2164   }
2165 #endif
2166 }
2167
2168 /***************** BlockList interface *********
2169 This was moved here from memory-isomalloc.c when it 
2170 was realized that a list-of-isomalloc'd-blocks is useful for
2171 more than just isomalloc heaps.
2172 */
2173
2174 typedef CmiIsomallocBlockList Slot;
2175
2176 /*Convert a slot to a user address*/
2177 static char *Slot_toUser(Slot *s) {return (char *)(s+1);}
2178 static Slot *Slot_fmUser(void *s) {return ((Slot *)s)-1;}
2179
2180
2181 /*Build a new blockList.*/
2182 CmiIsomallocBlockList *CmiIsomallocBlockListNew(void)
2183 {
2184         CmiIsomallocBlockList *ret;
2185         ret=(CmiIsomallocBlockList *)CmiIsomalloc(sizeof(*ret));
2186         ret->next=ret; /*1-entry circular linked list*/
2187         ret->prev=ret;
2188         return ret;
2189 }
2190
2191 /*Pup all the blocks in this list.  This amounts to two circular
2192 list traversals.  Because everything's isomalloc'd, we don't even
2193 have to restore the pointers-- they'll be restored automatically!
2194 */
2195 void CmiIsomallocBlockListPup(pup_er p,CmiIsomallocBlockList **lp)
2196 {
2197         int i,nBlocks=0;
2198         Slot *cur=NULL, *start=*lp;
2199 #if 0 /*#ifndef CMK_OPTIMIZE*/
2200         if (CpvAccess(isomalloc_blocklist)!=NULL)
2201                 CmiAbort("Called CmiIsomallocBlockListPup while a blockList is active!\n"
2202                         "You should swap out the active blocklist before pupping.\n");
2203 #endif
2204         /*Count the number of blocks in the list*/
2205         if (!pup_isUnpacking(p)) {
2206                 nBlocks=1; /*<- Since we have to skip the start block*/
2207                 for (cur=start->next; cur!=start; cur=cur->next) 
2208                         nBlocks++;
2209                 /*Prepare for next trip around list:*/
2210                 cur=start;
2211         }
2212         pup_int(p,&nBlocks);
2213         
2214         /*Pup each block in the list*/
2215         for (i=0;i<nBlocks;i++) {
2216                 void *newBlock=cur;
2217                 if (!pup_isUnpacking(p)) 
2218                 { /*While packing, we traverse the list to find our blocks*/
2219                         cur=cur->next;
2220                 }
2221                 CmiIsomallocPup(p,&newBlock);
2222                 if (i==0 && pup_isUnpacking(p))
2223                         *lp=(Slot *)newBlock;
2224         }
2225         if (pup_isDeleting(p))
2226                 *lp=NULL;
2227 }
2228
2229 /*Delete all the blocks in this list.*/
2230 void CmiIsomallocBlockListDelete(CmiIsomallocBlockList *l)
2231 {
2232         Slot *start=l;
2233         Slot *cur=start;
2234         if (cur==NULL) return; /*Already deleted*/
2235         do {
2236                 Slot *doomed=cur;
2237                 cur=cur->next; /*Have to stash next before deleting cur*/
2238                 CmiIsomallocFree(doomed);
2239         } while (cur!=start);
2240 }
2241
2242 /*Allocate a block from this blockList*/
2243 void *CmiIsomallocBlockListMalloc(CmiIsomallocBlockList *l,int nBytes)
2244 {
2245         Slot *n; /*Newly created slot*/
2246         n=(Slot *)CmiIsomalloc(sizeof(Slot)+nBytes);
2247         /*Link the new block into the circular blocklist*/
2248         n->prev=l;
2249         n->next=l->next;
2250         l->next->prev=n;
2251         l->next=n;
2252         return Slot_toUser(n);
2253 }
2254
2255 /*Remove this block from its list and memory*/
2256 void CmiIsomallocBlockListFree(void *block)
2257 {
2258         Slot *n=Slot_fmUser(block);
2259 #if DOHEAPCHECK
2260         if (n->prev->next!=n || n->next->prev!=n) 
2261                 CmiAbort("Heap corruption detected in isomalloc block list header!\n"
2262                         "  Run with ++debug and look for writes to negative array indices");
2263 #endif
2264         /*Link ourselves out of the blocklist*/
2265         n->prev->next=n->next;
2266         n->next->prev=n->prev;
2267         CmiIsomallocFree(n);
2268 }
2269
2270
2271
2272
2273