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