turned off the new isomalloc map region feature until it is properly tested.
[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   The b-tree implementation has two data structures that are maintained
23 simultaneously and in conjunction with each other: a b-tree of nodes
24 containing slotblocks used for quickly finding a particular slotblock;
25 and an array of doubly-linked lists containing the same slotblocks,
26 ordered according to the number of free slots in each slotblock, which
27 is used for quickly finding a block of free slots of a desired size.
28 The slotset contains pointers to both structures.
29 print_btree_top_down() and print_list_array() are very useful
30 functions for viewing the current structure of the tree and lists.
31
32   Each doubly-linked list has slotblocks containing between 2^(n-1)+1
33 and 2^n free slots, where n is the array index (i.e., bin number).
34 For example, list_array[0] points to a double-linked list of
35 slotblocks with 1 free slot, list_array[1] points to a double-linked
36 list of slotblocks with 2 free slots, list_array[2] to slotblocks with
37 3-4 free slots, list_array[3] to slotblocks with 5-8 free slots, etc.
38
39 Written for migratable threads by Milind Bhandarkar around August 2000;
40 generalized by Orion Lawlor November 2001.  B-tree implementation
41 added by Ryan Mokos in July 2008.
42 *************************************************************************/
43
44 #include "converse.h"
45 #include "memory-isomalloc.h"
46
47 #define CMK_THREADS_DEBUG 0
48
49 /* 0: do not use the intermediate mapregion management
50    1: use the intermediate mapregion management  */
51 #ifndef USE_MAPREGION
52 #define USE_MAPREGION      0
53 #endif
54
55 /* 0: use the old isomalloc implementation (array)
56    1: use the new isomalloc implementation (b-tree)  */
57 #define USE_BTREE_ISOMALLOC 1
58
59 /* b-tree definitions */
60 #define TREE_NODE_SIZE 128 /* a power of 2 is probably best  */
61 #define TREE_NODE_MID  63  /* must be cieling(TREE_NODE_SIZE / 2) - 1  */
62
63 /* linked list definitions  */
64 #define LIST_ARRAY_SIZE 64
65
66 #include <fcntl.h>
67 #include <stdio.h>
68 #include <stdlib.h>
69 #include <errno.h> /* just so I can find dynamically-linked symbols */
70 #include <unistd.h>
71
72 #if CMK_HAS_ADDR_NO_RANDOMIZE
73 #include <sys/personality.h>
74 #endif
75
76 static int _sync_iso = 0;
77 static int _mmap_probe = 0;
78
79 static int read_randomflag(void)
80 {
81   FILE *fp;
82   int random_flag;
83   fp = fopen("/proc/sys/kernel/randomize_va_space", "r");
84   if (fp != NULL) {
85     fscanf(fp, "%d", &random_flag);
86     fclose(fp);
87 #if CMK_HAS_ADDR_NO_RANDOMIZE
88     if(random_flag)
89     {
90         int persona = personality(0xffffffff);
91         if(persona & ADDR_NO_RANDOMIZE)
92             random_flag = 0;
93     }
94 #endif
95   }
96   else {
97     random_flag = -1;
98   }
99   return random_flag;
100 }
101
102 struct CmiIsomallocBlock {
103       CmiInt8 slot;   /* First mapped slot */
104       CmiInt8 length; /* Length of (user portion of) mapping, in bytes*/
105 };
106 typedef struct CmiIsomallocBlock CmiIsomallocBlock;
107
108 /* Convert a heap block pointer to/from a CmiIsomallocBlock header */
109 static void *block2pointer(CmiIsomallocBlock *blockHeader) {
110         return (void *)(blockHeader+1);
111 }
112 static CmiIsomallocBlock *pointer2block(void *heapBlock) {
113         return ((CmiIsomallocBlock *)heapBlock)-1;
114 }
115
116 /* Integral type to be used for pointer arithmetic: */
117 typedef size_t memRange_t;
118
119 /* Size in bytes of a single slot */
120 static size_t slotsize;
121 static size_t regionSize;
122
123 /* Total number of slots per processor */
124 static CmiInt8 numslots=0;
125
126 /* Start and end of isomalloc-managed addresses.
127    If isomallocStart==NULL, isomalloc is disabled.
128 */
129 static char *isomallocStart=NULL;
130 static char *isomallocEnd=NULL;
131
132 /* Utility conversion functions */
133 static void *slot2addr(CmiInt8 slot) {
134         return isomallocStart+((memRange_t)slotsize)*((memRange_t)slot);
135 }
136 static int slot2pe(CmiInt8 slot) {
137         return (int)(slot/numslots);
138 }
139 static CmiInt8 pe2slot(int pe) {
140         return pe*numslots;
141 }
142 /* Return the number of slots in a block with n user data bytes */
143 static int length2slots(int nBytes) {
144         return (sizeof(CmiIsomallocBlock)+nBytes+slotsize-1)/slotsize;
145 }
146
147 typedef struct
148 {
149         CmiInt8 size;
150         CmiInt8 count;
151         int **counter;
152         CmiInt8 **marker;
153 }mapRegion;
154
155 CpvStaticDeclare(mapRegion *, mapRegions); 
156
157 struct _maplist
158 {
159         struct _maplist *prev;
160         CmiInt8 start,end,count; 
161         struct _maplist *next;
162 };
163
164 typedef struct _maplist maplist;
165 CpvStaticDeclare(maplist **, mapLists); 
166
167 /* ======================================================================
168  * New isomalloc (b-tree-based implementation)
169  * ====================================================================== */
170
171 #if USE_BTREE_ISOMALLOC
172
173 /* doubly-linked list node */
174 struct _dllnode {
175   struct _dllnode   *previous;
176   struct _slotblock *sb;
177   struct _dllnode   *next;
178 };
179
180 /* slotblock */
181 struct _slotblock {
182   CmiInt8 startslot;
183   CmiInt8 nslots;
184   struct _dllnode *listblock;
185 };
186
187 typedef struct _dllnode   dllnode;
188 typedef struct _slotblock slotblock;
189
190 /* b-tree node */
191 struct _btreenode {
192   int num_blocks;
193   slotblock blocks[TREE_NODE_SIZE];
194   struct _btreenode *child[TREE_NODE_SIZE + 1];
195 };
196 typedef struct _btreenode btreenode;
197
198 /* slotset */
199 typedef struct _slotset {
200   btreenode *btree_root;
201   dllnode *list_array[LIST_ARRAY_SIZE];
202 } slotset;
203
204 /* return value for a b-tree insert */
205 typedef struct _insert_ret_val {
206   slotblock sb;
207   btreenode *btn;
208 } insert_ret_val;
209
210 /*****************************************************************
211  * Find and return the number of the bin (list) to which the number
212  * nslots belongs.  The range of each bin is 2^(b-1)+1 to 2^b, where b
213  * is the bin number.
214  *****************************************************************/
215
216 static int find_list_bin(CmiInt8 nslots) {
217   int list_bin     = 32;
218   CmiInt8 comp_num = 0x100000000LL;
219   int inc          = 16;
220
221   while (1) {
222     if ((nslots > (comp_num >> 1)) && (nslots <= comp_num)) {
223       /* found it */
224       return list_bin;
225     } else if (nslots < comp_num) {
226       /* look left  */
227       list_bin -= inc;
228       comp_num  = comp_num >> inc;
229       if ((inc = inc >> 1) == 0) {
230         inc = 1;
231       }
232     } else {
233       /* look right */
234       list_bin += inc;
235       comp_num  = comp_num << inc;
236       if ((inc = inc >> 1) == 0) {
237         inc = 1;
238       }
239     }
240   }
241
242 }
243
244 /*****************************************************************
245  * Creates and inserts a new dllnode into list_array (part of the
246  * slotset ss) that both points to and is pointed to by the slotblock
247  * sb.  This function also returns a pointer to that new dllnode.
248  *****************************************************************/
249
250 static dllnode *list_insert(slotset *ss, slotblock *sb) {
251
252   /* find the list bin to put the new dllnode in  */
253   int list_bin = find_list_bin(sb->nslots);
254
255   /* allocate memory for the new node */
256   dllnode *new_dlln = (dllnode *)(malloc_reentrant(sizeof(dllnode)));
257
258   /* insert the dllnode */
259   new_dlln->previous = NULL;
260   new_dlln->next     = ss->list_array[list_bin];
261   new_dlln->sb       = sb;
262   if (ss->list_array[list_bin] != NULL) {
263     ss->list_array[list_bin]->previous = new_dlln;
264   }
265   ss->list_array[list_bin] = new_dlln;
266
267   return new_dlln;
268
269 }
270
271 /*****************************************************************
272  * Deletes the dllnode from list_array (part of the slotset ss) that
273  * is pointed to by the slotblock sb.
274  *****************************************************************/
275
276 static void list_delete(slotset *ss, slotblock *sb) {
277
278   /* remove the node from the list */
279   if (sb->listblock->next != NULL) {
280     sb->listblock->next->previous = sb->listblock->previous;
281   }
282   if (sb->listblock->previous != NULL) {
283     sb->listblock->previous->next = sb->listblock->next;
284   } else {  /* first element in the list */
285     ss->list_array[find_list_bin(sb->nslots)] = sb->listblock->next;
286   }
287
288   /* free the memory from the node */
289   free_reentrant(sb->listblock);
290
291 }
292
293 /*****************************************************************
294  * Moves the dllnode dlln to the correct bin (list) of slotset ss
295  * based on the number of slots in the slotblock to which dlln points.
296  * It is assumed that the slotblock pointed to by dlln has already been
297  * updated with the new number of slots.  The integer old_nslots
298  * contains the number of slots that used to be in the slotblock.
299  *****************************************************************/
300
301 static void list_move(slotset *ss, dllnode *dlln, CmiInt8 old_nslots) {
302
303   /* determine the bin the slotblock used to be in */
304   int old_bin = find_list_bin(old_nslots);
305
306   /* determine the bin the slotblock is in now */
307   int new_bin = find_list_bin(dlln->sb->nslots);
308
309   /* if the old bin and new bin are different, move the slotblock */
310   if (new_bin != old_bin) {
311
312     /* remove from old bin */
313     if (dlln->previous == NULL) {  /* dlln is the 1st element in the list */
314       if (dlln->next != NULL) {
315         dlln->next->previous = NULL;
316       }
317       ss->list_array[old_bin] = dlln->next;
318     } else {
319       if (dlln->next != NULL) {
320         dlln->next->previous = dlln->previous;
321       }
322       dlln->previous->next = dlln->next;
323     }
324
325     /* insert at the beginning of the new bin */
326     dlln->next     = ss->list_array[new_bin];
327     dlln->previous = NULL;
328     if (dlln->next != NULL) {
329       dlln->next->previous = dlln;
330     }
331     ss->list_array[new_bin] = dlln;
332   }
333
334 }
335
336 /*****************************************************************
337  * Creates a new b-tree node
338  *****************************************************************/
339
340 static btreenode *create_btree_node() {
341   int i;
342   btreenode *btn = (btreenode *)malloc_reentrant(sizeof(btreenode));
343   btn->num_blocks = 0;
344   for (i = 0; i < TREE_NODE_SIZE; i++) {
345     btn->blocks[i].listblock = NULL;
346   }
347   for (i = 0; i < TREE_NODE_SIZE + 1; i++) {
348     btn->child[i] = NULL;
349   }
350   return btn;
351 }
352
353 /*****************************************************************
354  * Find the slotblock in the b-tree that contains startslot.  Returns
355  * NULL if such a block cannot be found.
356  *****************************************************************/
357
358 static slotblock *find_btree_slotblock(btreenode *node, CmiInt8 startslot) {
359
360   /* check if this node exists */
361   if ((node == NULL) || (startslot < 0) || (node->num_blocks == 0)) {
362     return NULL;
363   } else {
364
365     /*** Binary search on this node ***/
366     /* initialize */
367     int index = node->num_blocks >> 1;
368     int inc   = (index >> 1) + (node->num_blocks & 0x1);
369     CmiInt8 endslot;
370
371     /* loop until a node is found */
372     while (1) {
373
374       /* if startslot is in current slotblock, this is the slotblock */
375       endslot = node->blocks[index].startslot + node->blocks[index].nslots - 1;
376       if ((startslot >= node->blocks[index].startslot) &&
377           (startslot <= endslot)) {
378         return &(node->blocks[index]);
379       }
380
381       /* else, if startslot is less */
382       else if (startslot < node->blocks[index].startslot) {
383
384         /* if this is slotblock 0, take the left child */
385         if (index == 0) {
386           return find_btree_slotblock(node->child[index], startslot);
387         }
388
389         /* else check endslot of the slotblock to the left */
390         else {
391
392           /* if startslot > endslot-of-slotblock-to-the-left, take the
393              left child */
394           endslot = node->blocks[index-1].startslot + 
395             node->blocks[index-1].nslots - 1;
396           if (startslot > endslot) {
397             return find_btree_slotblock(node->child[index], startslot);
398           }
399
400           /* else continue to search this node to the left */
401           else {
402             index -= inc;
403             if ((inc = inc >> 1) == 0) {
404               inc = 1;
405             }
406           }
407         }
408       }
409
410       /* else, startslot must be greater */
411       else {
412
413         /* if this is the last slotblock, take the right child */
414         if (index == node->num_blocks - 1) {
415           return find_btree_slotblock(node->child[index+1], startslot);
416         }
417
418         /* else check startslot of the slotblock to the right */
419         else {
420
421           /* if startslot < startslot-of-slotblock-to-the-right, then
422              take the right child */
423           if (startslot < node->blocks[index+1].startslot) {
424             return find_btree_slotblock(node->child[index+1], startslot);
425           }
426
427           /* else continue to search this node to the right */
428           else {
429             index += inc;
430             if ((inc = inc >> 1) == 0) {
431               inc = 1;
432             }
433           }
434         }
435       }
436       
437     }
438
439   }
440
441 }
442
443 /*****************************************************************
444  * Insert a slotblock into the b-tree starting at startslot and going
445  * for nslots slots
446  *****************************************************************/
447
448 static insert_ret_val btree_insert_int(slotset *ss, btreenode *node, 
449                                        CmiInt8 startslot, CmiInt8 nslots) {
450
451   insert_ret_val irv;
452
453   /*** binary search for the place to insert ***/
454
455   /* initialize */
456   int index = node->num_blocks >> 1;
457   int inc   = (index >> 1) + (node->num_blocks & 0x1);
458
459   /* loop until an insertion happens */
460   while (1) {
461     if (startslot < node->blocks[index].startslot) {  /* look to the left */
462       if ((index == 0) || 
463           (startslot > node->blocks[index-1].startslot)) {
464         if (node->child[index] != NULL) {             /* take left child */
465           irv = btree_insert_int(ss, node->child[index], startslot, nslots);
466           if (irv.btn == NULL) {
467             return irv;
468           } else {                                    /* merge return value */
469             int i, j;                                 /*   insert on left   */
470             for (i = node->num_blocks; i > index; i--) {
471               node->blocks[i].startslot     = node->blocks[i-1].startslot;
472               node->blocks[i].nslots        = node->blocks[i-1].nslots;
473               node->blocks[i].listblock     = node->blocks[i-1].listblock;
474               node->blocks[i].listblock->sb = &(node->blocks[i]);
475               node->child[i+1]              = node->child[i];
476             }
477             node->blocks[index].startslot     = irv.sb.startslot;
478             node->blocks[index].nslots        = irv.sb.nslots;
479             node->blocks[index].listblock     = irv.sb.listblock;
480             node->blocks[index].listblock->sb = &(node->blocks[index]);
481             node->child[index+1]              = irv.btn;
482             node->num_blocks++;
483             if (node->num_blocks == TREE_NODE_SIZE) {   /* split node */
484               btreenode *new_node = create_btree_node();
485               for (i = TREE_NODE_MID + 1; i < TREE_NODE_SIZE; i++) {
486                 j = i - (TREE_NODE_MID + 1);
487                 new_node->blocks[j].startslot     = node->blocks[i].startslot;
488                 new_node->blocks[j].nslots        = node->blocks[i].nslots;
489                 new_node->blocks[j].listblock     = node->blocks[i].listblock;
490                 new_node->blocks[j].listblock->sb = &(new_node->blocks[j]);
491               }
492               for (i = TREE_NODE_MID + 1; i <= TREE_NODE_SIZE; i++) {
493                 new_node->child[i-(TREE_NODE_MID+1)] = node->child[i];
494               }
495               node->num_blocks     = TREE_NODE_MID;
496               new_node->num_blocks = TREE_NODE_SIZE - TREE_NODE_MID - 1;
497
498               irv.sb.startslot = node->blocks[TREE_NODE_MID].startslot;
499               irv.sb.nslots    = node->blocks[TREE_NODE_MID].nslots;
500               irv.sb.listblock = node->blocks[TREE_NODE_MID].listblock;
501               irv.btn          = new_node;
502               return irv;
503             } else {
504               irv.btn = NULL;
505               return irv;
506             }
507           }
508         } else {                                      /* insert to the left */
509           int i, j;
510           for (i = node->num_blocks; i > index; i--) {
511             node->blocks[i].startslot     = node->blocks[i-1].startslot;
512             node->blocks[i].nslots        = node->blocks[i-1].nslots;
513             node->blocks[i].listblock     = node->blocks[i-1].listblock;
514             node->blocks[i].listblock->sb = &(node->blocks[i]);
515           }
516           node->blocks[index].startslot = startslot;
517           node->blocks[index].nslots    = nslots;
518           node->blocks[index].listblock = list_insert(ss, &(node->blocks[index]));
519           node->num_blocks++;
520           if (node->num_blocks == TREE_NODE_SIZE) {   /* split node */
521             btreenode *new_node = create_btree_node();
522             for (i = TREE_NODE_MID + 1; i < TREE_NODE_SIZE; i++) {
523               j = i - (TREE_NODE_MID + 1);
524               new_node->blocks[j].startslot     = node->blocks[i].startslot;
525               new_node->blocks[j].nslots        = node->blocks[i].nslots;
526               new_node->blocks[j].listblock     = node->blocks[i].listblock;
527               new_node->blocks[j].listblock->sb = &(new_node->blocks[j]);
528             }
529             node->num_blocks     = TREE_NODE_MID;
530             new_node->num_blocks = TREE_NODE_SIZE - TREE_NODE_MID - 1;
531
532             irv.sb.startslot = node->blocks[TREE_NODE_MID].startslot;
533             irv.sb.nslots    = node->blocks[TREE_NODE_MID].nslots;
534             irv.sb.listblock = node->blocks[TREE_NODE_MID].listblock;
535             irv.btn          = new_node;
536             return irv;
537           } else {
538             irv.btn = NULL;
539             return irv;
540           }
541         }
542       } else {                                        /* search to the left */
543         index -= inc;
544         if ((inc = inc >> 1) == 0) {
545           inc = 1;
546         }
547       }
548
549     } else {                                          /* look to the right */
550
551       if ((index == node->num_blocks - 1) || 
552           (startslot < node->blocks[index+1].startslot)) {
553         if (node->child[index+1] != NULL) {           /* take right child */
554           irv = btree_insert_int(ss, node->child[index+1], startslot, nslots);
555           if (irv.btn == NULL) {
556             return irv;
557           } else {                                    /* merge return value */
558             int i, j;                                 /*   insert on right  */
559             for (i = node->num_blocks; i > index + 1; i--) {
560               node->blocks[i].startslot     = node->blocks[i-1].startslot;
561               node->blocks[i].nslots        = node->blocks[i-1].nslots;
562               node->blocks[i].listblock     = node->blocks[i-1].listblock;
563               node->blocks[i].listblock->sb = &(node->blocks[i]);
564               node->child[i+1]              = node->child[i];
565             }
566             node->blocks[index+1].startslot     = irv.sb.startslot;
567             node->blocks[index+1].nslots        = irv.sb.nslots;
568             node->blocks[index+1].listblock     = irv.sb.listblock;
569             node->blocks[index+1].listblock->sb = &(node->blocks[index+1]);
570             node->child[index+2]                = irv.btn;
571             node->num_blocks++;
572             if (node->num_blocks == TREE_NODE_SIZE) {   /* split node */
573               btreenode *new_node = create_btree_node();
574               for (i = TREE_NODE_MID + 1; i < TREE_NODE_SIZE; i++) {
575                 j = i - (TREE_NODE_MID + 1);
576                 new_node->blocks[j].startslot     = node->blocks[i].startslot;
577                 new_node->blocks[j].nslots        = node->blocks[i].nslots;
578                 new_node->blocks[j].listblock     = node->blocks[i].listblock;
579                 new_node->blocks[j].listblock->sb = &(new_node->blocks[j]);
580               }
581               for (i = TREE_NODE_MID + 1; i <= TREE_NODE_SIZE; i++) {
582                 new_node->child[i-(TREE_NODE_MID+1)] = node->child[i];
583               }
584               node->num_blocks     = TREE_NODE_MID;
585               new_node->num_blocks = TREE_NODE_SIZE - TREE_NODE_MID - 1;
586
587               irv.sb.startslot = node->blocks[TREE_NODE_MID].startslot;
588               irv.sb.nslots    = node->blocks[TREE_NODE_MID].nslots;
589               irv.sb.listblock = node->blocks[TREE_NODE_MID].listblock;
590               irv.btn          = new_node;
591               return irv;
592             } else {
593               irv.btn = NULL;
594               return irv;
595             }
596           }
597         } else {                                      /* insert to the right */
598           int i, j;
599           for (i = node->num_blocks; i > index + 1; i--) {
600             node->blocks[i].startslot     = node->blocks[i-1].startslot;
601             node->blocks[i].nslots        = node->blocks[i-1].nslots;
602             node->blocks[i].listblock     = node->blocks[i-1].listblock;
603             node->blocks[i].listblock->sb = &(node->blocks[i]);
604           }
605           node->blocks[index+1].startslot = startslot;
606           node->blocks[index+1].nslots    = nslots;
607           node->blocks[index+1].listblock = list_insert(ss, &(node->blocks[index+1]));
608           node->num_blocks++;
609           if (node->num_blocks == TREE_NODE_SIZE) {   /* split node */
610             btreenode *new_node = create_btree_node();
611             for (i = TREE_NODE_MID + 1; i < TREE_NODE_SIZE; i++) {
612               j = i - (TREE_NODE_MID + 1);
613               new_node->blocks[j].startslot     = node->blocks[i].startslot;
614               new_node->blocks[j].nslots        = node->blocks[i].nslots;
615               new_node->blocks[j].listblock     = node->blocks[i].listblock;
616               new_node->blocks[j].listblock->sb = &(new_node->blocks[j]);
617             }
618             node->num_blocks = TREE_NODE_MID;
619             new_node->num_blocks = TREE_NODE_SIZE - TREE_NODE_MID - 1;
620
621             irv.sb.startslot = node->blocks[TREE_NODE_MID].startslot;
622             irv.sb.nslots    = node->blocks[TREE_NODE_MID].nslots;
623             irv.sb.listblock = node->blocks[TREE_NODE_MID].listblock;
624             irv.btn          = new_node;
625             return irv;
626           } else {
627             irv.btn = NULL;
628             return irv;
629           }
630         }
631       } else {                                        /* search to the right */
632         index += inc;
633         if ((inc = inc >> 1) == 0) {
634           inc = 1;
635         }
636       }
637     }
638   }
639
640 }
641
642 static btreenode *btree_insert(slotset *ss, btreenode *node, 
643                                CmiInt8 startslot, CmiInt8 nslots) {
644
645   /* check the b-tree root: if it's empty, insert the element in the
646      first position */
647   if (node->num_blocks == 0) {
648
649     node->num_blocks          = 1;
650     node->blocks[0].startslot = startslot;
651     node->blocks[0].nslots    = nslots;
652     node->blocks[0].listblock = list_insert(ss, &(node->blocks[0]));
653
654   } else {
655
656     /* insert into the b-tree */
657     insert_ret_val irv = btree_insert_int(ss, node, startslot, nslots);
658
659     /* if something was returned, we need a new root */
660     if (irv.btn != NULL) {
661       btreenode *new_root  = create_btree_node();
662       new_root->num_blocks = 1;
663       new_root->blocks[0].startslot     = irv.sb.startslot;
664       new_root->blocks[0].nslots        = irv.sb.nslots;
665       new_root->blocks[0].listblock     = irv.sb.listblock;
666       new_root->blocks[0].listblock->sb = &(new_root->blocks[0]);
667       new_root->child[0] = node;
668       new_root->child[1] = irv.btn;
669       node = new_root;
670     }
671
672   }
673
674   return node;
675
676 }
677
678 /*****************************************************************
679  * Delete the slotblock from the b-tree starting at startslot
680  *****************************************************************/
681
682 static void btree_delete_int(slotset *ss, btreenode *node, 
683                              CmiInt8 startslot, slotblock *sb) {
684
685   int i, index, inc;
686   int def_child;
687   int num_left, num_right, left_pos, right_pos;
688
689   /* If sb is not NULL, we're sending sb down the tree to a leaf to be
690      swapped with the next larger startslot so it can be deleted from
691      a leaf node (deletions from non-leaf nodes are not allowed
692      here).  At this point, the next larger startslot will always be
693      found by taking the leftmost child.  */
694   if (sb != NULL) {
695
696     if (node->child[0] != NULL) {
697       btree_delete_int(ss, node->child[0], startslot, sb);
698       index = 0;
699
700     } else {
701
702       /* we're now at a leaf node, so the slotblock can be deleted
703
704          first, copy slotblock 0 to the block passed down (sb) and
705          delete the list array node  */
706       list_delete(ss, sb);
707       sb->startslot     = node->blocks[0].startslot;
708       sb->nslots        = node->blocks[0].nslots;
709       sb->listblock     = node->blocks[0].listblock;
710       sb->listblock->sb = sb;
711
712       /* delete the slotblock */
713       for (i = 0; i < (node->num_blocks - 1); i++) {
714         node->blocks[i].startslot     = node->blocks[i+1].startslot;
715         node->blocks[i].nslots        = node->blocks[i+1].nslots;
716         node->blocks[i].listblock     = node->blocks[i+1].listblock;
717         node->blocks[i].listblock->sb = &(node->blocks[i]);
718       }
719       node->num_blocks--;
720
721       return;
722
723     }
724
725   } else {
726
727     /*** Binary search for the slotblock to delete ***/
728
729     /* initialize */
730     index = node->num_blocks >> 1;
731     inc = (index >> 1) + (node->num_blocks & 0x1);
732
733     /* loop until the slotblock with startslot is found */
734     while (1) {
735
736       if (startslot == node->blocks[index].startslot) {   /* found it */
737         if (node->child[index+1] != NULL) {               /* not a leaf */
738           btree_delete_int(ss, node->child[index+1], 
739                            startslot, &(node->blocks[index]));
740           break;
741         } else {                                          /* is a leaf */
742           /* delete the slotblock */
743           list_delete(ss, &(node->blocks[index]));
744           for (i = index; i < (node->num_blocks - 1); i++) {
745             node->blocks[i].startslot     = node->blocks[i+1].startslot;
746             node->blocks[i].nslots        = node->blocks[i+1].nslots;
747             node->blocks[i].listblock     = node->blocks[i+1].listblock;
748             node->blocks[i].listblock->sb = &(node->blocks[i]);
749           }
750           node->num_blocks--;
751           return;
752         }
753       } else {
754         if (startslot < node->blocks[index].startslot) {  /* look left */
755           if ((index == 0) ||                             /* take left child */
756               (startslot > node->blocks[index-1].startslot)) {
757             btree_delete_int(ss, node->child[index], startslot, sb);
758             break;
759           } else {                                        /* search left */
760             index -= inc;
761             if ((inc = inc >> 1) == 0) {
762               inc = 1;
763             }
764           }
765         } else {                                          /* look right */
766           if ((index == node->num_blocks - 1) ||          /* take right child */
767               (startslot < node->blocks[index+1].startslot)) {
768             btree_delete_int(ss, node->child[index+1], startslot, sb);
769             break;
770           } else {                                        /* search right */
771             index += inc;
772             if ((inc = inc >> 1) == 0) {
773               inc = 1;
774             }
775           }
776         }
777       }
778
779     }
780
781   }
782
783   /* At this point, the desired slotblock has been removed, and we're
784      going back up the tree.  We must check for deficient nodes that
785      require the rotating or combining of elements to maintain a
786      balanced b-tree. */
787   def_child = -1;
788
789   /* check if one of the child nodes is deficient  */
790   if (node->child[index]->num_blocks < TREE_NODE_MID) {
791     def_child = index;
792   } else if (node->child[index+1]->num_blocks < TREE_NODE_MID) {
793     def_child = index + 1;
794   }
795
796   if (def_child >= 0) {
797
798     /* if there is a left sibling and it has enough elements, rotate */
799     /* to the right */
800     if ((def_child != 0) && (node->child[def_child-1] != NULL) && 
801         (node->child[def_child-1]->num_blocks > TREE_NODE_MID)) {
802
803       /* move all elements in deficient child to the right */
804       for (i = node->child[def_child]->num_blocks; i > 0; i--) {
805         node->child[def_child]->blocks[i].startslot = 
806           node->child[def_child]->blocks[i-1].startslot;
807         node->child[def_child]->blocks[i].nslots = 
808           node->child[def_child]->blocks[i-1].nslots;
809         node->child[def_child]->blocks[i].listblock = 
810           node->child[def_child]->blocks[i-1].listblock;
811         node->child[def_child]->blocks[i].listblock->sb = 
812           &(node->child[def_child]->blocks[i]);
813       }
814       for (i = node->child[def_child]->num_blocks + 1; i > 0; i--) {
815         node->child[def_child]->child[i] = 
816           node->child[def_child]->child[i-1];
817       }
818
819       /* move parent element to the deficient child */
820       node->child[def_child]->blocks[0].startslot = 
821         node->blocks[def_child-1].startslot;
822       node->child[def_child]->blocks[0].nslots = 
823         node->blocks[def_child-1].nslots;
824       node->child[def_child]->blocks[0].listblock = 
825         node->blocks[def_child-1].listblock;
826       node->child[def_child]->blocks[0].listblock->sb = 
827         &(node->child[def_child]->blocks[0]);
828       node->child[def_child]->num_blocks++;
829
830       /* move the right-most child of the parent's left child to the
831          left-most child of the formerly deficient child  */
832       i = node->child[def_child-1]->num_blocks;
833       node->child[def_child]->child[0] = 
834         node->child[def_child-1]->child[i];
835
836       /* move largest element from left child up to the parent */
837       i--;
838       node->blocks[def_child-1].startslot = 
839         node->child[def_child-1]->blocks[i].startslot;
840       node->blocks[def_child-1].nslots = 
841         node->child[def_child-1]->blocks[i].nslots;
842       node->blocks[def_child-1].listblock = 
843         node->child[def_child-1]->blocks[i].listblock;
844       node->blocks[def_child-1].listblock->sb = 
845         &(node->blocks[def_child-1]);
846       node->child[def_child-1]->num_blocks--;
847
848     }
849
850     /* otherwise, if there is a right sibling and it has enough */
851     /* elements, rotate to the left */
852     else if (((def_child + 1) <= node->num_blocks) && 
853              (node->child[def_child+1] != NULL) && 
854              (node->child[def_child+1]->num_blocks > TREE_NODE_MID)) {
855
856       /* move parent element to the deficient child */
857       i = node->child[def_child]->num_blocks;
858       node->child[def_child]->blocks[i].startslot = 
859         node->blocks[def_child].startslot;
860       node->child[def_child]->blocks[i].nslots = 
861         node->blocks[def_child].nslots;
862       node->child[def_child]->blocks[i].listblock = 
863         node->blocks[def_child].listblock;
864       node->child[def_child]->blocks[i].listblock->sb = 
865         &(node->child[def_child]->blocks[i]);
866       node->child[def_child]->num_blocks++;
867
868       /* move the left-most child of the parent's right child to the
869          right-most child of the formerly deficient child  */
870       i++;
871       node->child[def_child]->child[i] = 
872         node->child[def_child+1]->child[0];
873
874       /* move smallest element from right child up to the parent */
875       node->blocks[def_child].startslot = 
876         node->child[def_child+1]->blocks[0].startslot;
877       node->blocks[def_child].nslots = 
878         node->child[def_child+1]->blocks[0].nslots;
879       node->blocks[def_child].listblock = 
880         node->child[def_child+1]->blocks[0].listblock;
881       node->blocks[def_child].listblock->sb = 
882         &(node->blocks[def_child]);
883       node->child[def_child+1]->num_blocks--;
884
885       /* move all elements in the parent's right child to the left  */
886       for (i = 0; i < node->child[def_child+1]->num_blocks; i++) {
887         node->child[def_child+1]->blocks[i].startslot = 
888           node->child[def_child+1]->blocks[i+1].startslot;
889         node->child[def_child+1]->blocks[i].nslots = 
890           node->child[def_child+1]->blocks[i+1].nslots;
891         node->child[def_child+1]->blocks[i].listblock = 
892           node->child[def_child+1]->blocks[i+1].listblock;
893         node->child[def_child+1]->blocks[i].listblock->sb = 
894           &(node->child[def_child+1]->blocks[i]);
895       }
896       for (i = 0; i < node->child[def_child+1]->num_blocks + 1; i++) {
897         node->child[def_child+1]->child[i] = 
898           node->child[def_child+1]->child[i+1];
899       }
900     }
901
902     /* otherwise, merge the deficient node, parent, and the parent's
903        other child (one of the deficient node's siblings) by dropping
904        the parent down to the level of the children */
905     else {
906
907       /* move the parent element into the left child node */
908       i = node->child[index]->num_blocks;
909       node->child[index]->blocks[i].startslot = 
910         node->blocks[index].startslot;
911       node->child[index]->blocks[i].nslots = 
912         node->blocks[index].nslots;
913       node->child[index]->blocks[i].listblock = 
914         node->blocks[index].listblock;
915       node->child[index]->blocks[i].listblock->sb = 
916         &(node->child[index]->blocks[i]);
917       node->child[index]->num_blocks++;
918
919       /* move the elements and children of the right child node to the */
920       /* left child node */
921       num_left  = node->child[index]->num_blocks;
922       num_right = node->child[index+1]->num_blocks;
923       left_pos;
924       right_pos = 0;
925       for (left_pos = num_left; left_pos < num_left + num_right; left_pos++) {
926         node->child[index]->blocks[left_pos].startslot = 
927           node->child[index+1]->blocks[right_pos].startslot;
928         node->child[index]->blocks[left_pos].nslots = 
929           node->child[index+1]->blocks[right_pos].nslots;
930         node->child[index]->blocks[left_pos].listblock = 
931           node->child[index+1]->blocks[right_pos].listblock;
932         node->child[index]->blocks[left_pos].listblock->sb = 
933           &(node->child[index]->blocks[left_pos]);
934         right_pos++;
935       }
936       right_pos = 0;
937       for (left_pos = num_left; left_pos < num_left + num_right + 1; left_pos++) {
938         node->child[index]->child[left_pos] = 
939           node->child[index+1]->child[right_pos];
940         right_pos++;
941       }
942       node->child[index]->num_blocks = num_left + num_right;
943
944       /* delete the right child node */
945       free_reentrant(node->child[index+1]);
946       node->child[index+1] = NULL;
947
948       /* update the parent node */
949       node->num_blocks--;
950       for (i = index; i < node->num_blocks; i++) {
951         node->blocks[i].startslot     = node->blocks[i+1].startslot;
952         node->blocks[i].nslots        = node->blocks[i+1].nslots;
953         node->blocks[i].listblock     = node->blocks[i+1].listblock;
954         node->blocks[i].listblock->sb = &(node->blocks[i]);
955         node->child[i+1]              = node->child[i+2];
956       }
957
958     }
959
960   }
961
962 }
963
964 static btreenode *btree_delete(slotset *ss, btreenode *node, CmiInt8 startslot) {
965
966   /* delete element from the b-tree */
967   btree_delete_int(ss, node, startslot, NULL);
968
969   /* if the root node is empty (from a combine operation on the tree),
970      the left-most child of the root becomes the new root, unless the
971      left-most child is NULL, in which case we leave the root node
972      empty but not NULL */
973   if (node->num_blocks == 0) {
974     if (node->child[0] != NULL) {
975       btreenode *new_root = node->child[0];
976       free_reentrant(node);
977       node = new_root;
978     }
979   }
980
981   return node;
982
983 }
984
985 /*****************************************************************
986  * Creates a new slotset with nslots entries, starting with all empty
987  * slots.  The slot numbers are [startslot, startslot + nslots - 1].
988  *****************************************************************/
989
990 static slotset *new_slotset(CmiInt8 startslot, CmiInt8 nslots) {
991   int i;
992   int list_bin;
993
994   /* CmiPrintf("*** New Isomalloc ***\n"); */
995
996   /* allocate memory for the slotset */
997   slotset *ss = (slotset *)(malloc_reentrant(sizeof(slotset)));
998
999   /* allocate memory for the b-tree */
1000   ss->btree_root = create_btree_node();
1001
1002   /* initialize the b-tree */
1003   ss->btree_root->num_blocks          = 1;
1004   ss->btree_root->blocks[0].startslot = startslot;
1005   ss->btree_root->blocks[0].nslots    = nslots;
1006
1007   /* initialize the list array */
1008   for (i = 0; i < LIST_ARRAY_SIZE; i++) {
1009     ss->list_array[i] = NULL;
1010   }
1011   list_bin = find_list_bin(nslots);
1012   ss->list_array[list_bin] = (dllnode *)(malloc_reentrant(sizeof(dllnode)));
1013   ss->list_array[list_bin]->previous = NULL;
1014   ss->list_array[list_bin]->next = NULL;
1015   ss->list_array[list_bin]->sb = &(ss->btree_root->blocks[0]);
1016
1017   ss->btree_root->blocks[0].listblock = ss->list_array[list_bin];
1018
1019   return ss;
1020
1021 }
1022
1023 /*****************************************************************
1024  * Finds a slotblock containing at least nslots memory slots and
1025  * returns the startslot of that slotblock; returns -1 if no such
1026  * slotblock exists.
1027  *****************************************************************/
1028
1029 static CmiInt8 get_slots(slotset *ss, CmiInt8 nslots) {
1030
1031   /* calculate the smallest bin (list) to look in first */
1032   int start_list = find_list_bin(nslots);
1033
1034   /* search for a slotblock with enough slots */
1035   int i;
1036   dllnode *dlln;
1037   for (i = start_list; i < LIST_ARRAY_SIZE; i++) {
1038     dlln = ss->list_array[i];
1039     while (dlln != NULL) {
1040       if (dlln->sb->nslots >= nslots) {
1041         return dlln->sb->startslot;
1042       }
1043       dlln = dlln->next;
1044     }
1045   }
1046
1047   /* return -1 if no such slotblock exists */
1048   return (-1);
1049
1050 }
1051
1052 /*****************************************************************
1053  * Grab a slotblock with the specified range of blocks (nslots blocks
1054  * starting at sslot).  This is different from get_slots because
1055  * grab_slots specifies the slots to be grabbed and actually grabs
1056  * them (removes them from the set of free slots).  get_slots only
1057  * finds a set of free slots.
1058  *****************************************************************/
1059
1060 static void grab_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots) {
1061
1062   CmiInt8 endslot;
1063   slotblock *sb = find_btree_slotblock(ss->btree_root, sslot);
1064
1065   if (sb == NULL) {
1066     CmiAbort("requested a non-existent slotblock\n");
1067   } else {
1068     
1069     if (sb->startslot == sslot) {
1070
1071       /* range is exact range of slotblock - delete block from tree */
1072       if (sb->nslots == nslots) {
1073         ss->btree_root = btree_delete(ss, ss->btree_root, sslot);
1074       }
1075
1076       /* range is at beginning of slotblock - update block range */
1077       else {
1078         CmiInt8 old_nslots = sb->nslots;
1079         sb->startslot     += nslots;
1080         sb->nslots        -= nslots;
1081         list_move(ss, sb->listblock, old_nslots);
1082       }
1083
1084     } else {
1085
1086       /* range is at end of slotblock - update block range */
1087       endslot = sb->startslot + sb->nslots - 1;
1088       if (endslot == (sslot + nslots - 1)) {
1089         CmiInt8 old_nslots = sb->nslots;
1090         sb->nslots        -= nslots;
1091         list_move(ss, sb->listblock, old_nslots);
1092       }
1093
1094       /* range is in middle of slotblock - update block range with the */
1095       /* new lower range and insert a block with the new upper range */
1096       else {
1097         CmiInt8 old_nslots = sb->nslots;
1098         sb->nslots         = sslot - sb->startslot;
1099         list_move(ss, sb->listblock, old_nslots);
1100         ss->btree_root = btree_insert(ss, ss->btree_root, sslot + nslots, 
1101                                       endslot - (sslot + nslots) + 1);
1102       }
1103
1104     }
1105
1106   }
1107
1108 }
1109
1110 /*****************************************************************
1111  * Frees nslots memory slots starting at sslot by either adding them
1112  * to one of the slotblocks that exists (if the slot ranges are
1113  * contiguous) or by creating a new slotblock
1114  *****************************************************************/
1115
1116 static void free_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots) {
1117
1118   slotblock *sb_low  = find_btree_slotblock(ss->btree_root, sslot - 1);
1119   slotblock *sb_high = find_btree_slotblock(ss->btree_root, sslot + nslots);
1120
1121   if (sb_low == NULL) {
1122     if (sb_high == NULL) {
1123
1124       /* there is no adjacent slotblock, so create a new one and */
1125       /* insert it in the b-tree */
1126       ss->btree_root = btree_insert(ss, ss->btree_root, sslot, nslots);
1127
1128     } else {
1129
1130       /* there is an adjacent slotblock to the right, so update its range */
1131       CmiInt8 old_nslots = sb_high->nslots;
1132       sb_high->startslot = sslot;
1133       sb_high->nslots   += nslots;
1134       list_move(ss, sb_high->listblock, old_nslots);
1135
1136     }
1137   } else {
1138     if (sb_high == NULL) {
1139
1140       /* there is an adjacent slotblock to the left, so update its range */
1141       CmiInt8 old_nslots  = sb_low->nslots;
1142       sb_low->nslots     += nslots;
1143       list_move(ss, sb_low->listblock, old_nslots);
1144
1145     } else {
1146
1147       /* there are adjacent slotblocks on both sides (i.e., the
1148          slots to be freed exactly span the gap between 2 slotblocks),
1149          so update the range of the lower slotblock and delete the
1150          upper one */
1151       CmiInt8 old_nslots = sb_low->nslots;
1152       sb_low->nslots     = sb_low->nslots + nslots + sb_high->nslots;
1153       list_move(ss, sb_low->listblock, old_nslots);
1154       ss->btree_root = btree_delete(ss, ss->btree_root, sb_high->startslot);
1155
1156     }
1157   }
1158
1159 }
1160
1161 /*****************************************************************
1162  * Recursively free the allocated memory of the b-tree
1163  *****************************************************************/
1164
1165 static void delete_btree(btreenode *node) {
1166   int i;
1167   for (i = 0; i <= node->num_blocks; i++) {
1168     if (node->child[i] != NULL) {
1169       delete_btree(node->child[i]);
1170       free_reentrant(node->child[i]);
1171     } else {
1172       return;
1173     }
1174   }
1175 }
1176
1177 /*****************************************************************
1178  * Free the allocated memory of the list array
1179  *****************************************************************/
1180
1181 static void delete_list_array(slotset *ss) {
1182   int i;
1183   dllnode *dlln;
1184   for (i = 0; i < LIST_ARRAY_SIZE; i++) {
1185     dlln = ss->list_array[i];
1186     if (dlln != NULL) {
1187       while (dlln->next != NULL) {
1188         dlln = dlln->next;
1189       }
1190       while (dlln->previous != NULL) {
1191         dlln = dlln->previous;
1192         free_reentrant(dlln->next);
1193       }
1194       free_reentrant(dlln);
1195     }
1196   }
1197 }
1198
1199 /*****************************************************************
1200  * Free the allocated memory of the slotset
1201  *****************************************************************/
1202
1203 static void delete_slotset(slotset *ss) {
1204   delete_btree(ss->btree_root);
1205   delete_list_array(ss);
1206   free_reentrant(ss->btree_root);
1207   free_reentrant(ss);
1208 }
1209
1210 /*****************************************************************
1211  * Print the contents of the b-tree on the screen in a top-down
1212  * fashion, starting with the root and progressing to the sub-trees
1213  *****************************************************************/
1214
1215 /* prints the elements in a single b-tree node */
1216 static void print_btree_node(btreenode *node, int node_num) {
1217   int i;
1218   CmiPrintf("Node %2d: ", node_num);
1219   for (i = 0; i < node->num_blocks; i++) {
1220     CmiPrintf("%d:[%lld,%lld] ", i, node->blocks[i].startslot, node->blocks[i].nslots);
1221   }
1222   CmiPrintf("\n");
1223 }
1224
1225 /* returns 1 if there's another level to print; 0 if not */
1226 static int print_btree_level(btreenode *node, int level, int current_level, int node_num) {
1227   int i, another_level;
1228   for (i = 0; i <= node->num_blocks; i++) {
1229     if (current_level == level) {
1230       print_btree_node(node, node_num);
1231       if (node->child[0] == NULL) {
1232         return 0;
1233       } else {
1234         return 1;
1235       }
1236     } else {
1237       another_level = print_btree_level(node->child[i], level, 
1238                                         current_level + 1, i);
1239     }
1240   }
1241   return another_level;
1242 }
1243
1244 static void print_btree_top_down(btreenode *node) {
1245   int level = 0;
1246   int another_level;
1247   do {
1248     CmiPrintf("B-tree Level %d\n", level);
1249     CmiPrintf("---------------\n");
1250     another_level = print_btree_level(node, level, 0, 0);
1251     level++;
1252     CmiPrintf("\n\n");
1253   } while (another_level);
1254 }
1255
1256 /*****************************************************************
1257  * Print the contents of the list arry on the screen
1258  *****************************************************************/
1259
1260 static void print_list_array(slotset *ss) {
1261   int i;
1262   dllnode *dlln;
1263   CmiPrintf("List Array\n");
1264   CmiPrintf("----------\n");
1265   for (i = 0; i < LIST_ARRAY_SIZE; i++) {
1266     CmiPrintf("List %2d: ", i);
1267     dlln = ss->list_array[i];
1268     while (dlln != NULL) {
1269       if (dlln->previous != NULL) {
1270         CmiPrintf("<->");
1271       } else {
1272         CmiPrintf(" ->");
1273       }
1274       CmiPrintf("[%lld,%lld]", dlln->sb->startslot, dlln->sb->nslots);
1275       dlln = dlln->next;
1276     }
1277     CmiPrintf("\n");
1278   }
1279 }
1280
1281 #if CMK_THREADS_DEBUG
1282 static void print_slots(slotset *ss) {
1283   print_btree_top_down(ss->btree_root);
1284   print_list_array(ss);
1285 }
1286 #else
1287 #  define print_slots(ss) /*empty*/
1288 #endif
1289
1290
1291
1292 /* ======================================================================
1293  * Old isomalloc (array-based implementation)
1294  * ====================================================================== */
1295
1296 #else
1297
1298 typedef struct _slotblock
1299 {
1300   CmiInt8 startslot;
1301   CmiInt8 nslots;
1302 } slotblock;
1303
1304 typedef struct _slotset
1305 {
1306   int maxbuf;
1307   slotblock *buf;
1308   CmiInt8 emptyslots;
1309 } slotset;
1310
1311 /*
1312  * creates a new slotset of nslots entries, starting with all
1313  * empty slots. The slot numbers are [startslot,startslot+nslot-1]
1314  */
1315
1316 static slotset *
1317 new_slotset(CmiInt8 startslot, CmiInt8 nslots)
1318 {
1319   /* CmiPrintf("*** Old isomalloc ***\n"); */
1320   int i;
1321   slotset *ss = (slotset*) malloc_reentrant(sizeof(slotset));
1322   _MEMCHECK(ss);
1323   ss->maxbuf = 16;
1324   ss->buf = (slotblock *) malloc_reentrant(sizeof(slotblock)*ss->maxbuf);
1325   _MEMCHECK(ss->buf);
1326   ss->emptyslots = nslots;
1327   ss->buf[0].startslot = startslot;
1328   ss->buf[0].nslots = nslots;
1329   for (i=1; i<ss->maxbuf; i++)
1330     ss->buf[i].nslots = 0;
1331   return ss;
1332 }
1333
1334 /*
1335  * returns new block of empty slots. if it cannot find any, returns (-1).
1336  */
1337
1338 static CmiInt8
1339 get_slots(slotset *ss, CmiInt8 nslots)
1340 {
1341   /* CmiPrintf("old get: nslots=%lld\n", nslots); */
1342   int i;
1343   if(ss->emptyslots < nslots)
1344     return (-1);
1345   for(i=0;i<(ss->maxbuf);i++)
1346     if(ss->buf[i].nslots >= nslots)
1347       return ss->buf[i].startslot;
1348   return (-1);
1349 }
1350
1351 /* just adds a slotblock to an empty position in the given slotset. */
1352
1353 static void
1354 add_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots)
1355 {
1356   int pos; 
1357   int emptypos = -1;
1358   if (nslots == 0)
1359     return;
1360   for (pos=0; pos < (ss->maxbuf); pos++) {
1361     if (ss->buf[pos].nslots == 0) {
1362       emptypos = pos;
1363       break; /* found empty slotblock */
1364     }
1365   }
1366   if (emptypos == (-1)) /*no empty slotblock found */
1367   {
1368     int i;
1369     int newsize = ss->maxbuf*2;
1370     slotblock *newbuf = (slotblock *) malloc_reentrant(sizeof(slotblock)*newsize);
1371     _MEMCHECK(newbuf);
1372     for (i=0; i<(ss->maxbuf); i++)
1373       newbuf[i] = ss->buf[i];
1374     for (i=ss->maxbuf; i<newsize; i++)
1375       newbuf[i].nslots  = 0;
1376     free_reentrant(ss->buf);
1377     ss->buf = newbuf;
1378     emptypos = ss->maxbuf;
1379     ss->maxbuf = newsize;
1380   }
1381   ss->buf[emptypos].startslot = sslot;
1382   ss->buf[emptypos].nslots = nslots;
1383   ss->emptyslots += nslots;
1384   return;
1385 }
1386
1387 /* grab a slotblock with specified range of blocks
1388  * this is different from get_slots, since it pre-specifies the
1389  * slots to be grabbed.
1390  */
1391 static void
1392 grab_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots)
1393 {
1394   /* CmiPrintf("old grab: sslot=%lld nslots=%lld\n", sslot, nslots); */
1395   CmiInt8 pos, eslot, e;
1396   eslot = sslot + nslots;
1397   for (pos=0; pos < (ss->maxbuf); pos++)
1398   {
1399     if (ss->buf[pos].nslots == 0)
1400       continue;
1401     e = ss->buf[pos].startslot + ss->buf[pos].nslots;
1402     if(sslot >= ss->buf[pos].startslot && eslot <= e)
1403     {
1404       CmiInt8 old_nslots;
1405       old_nslots = ss->buf[pos].nslots;
1406       ss->buf[pos].nslots = sslot - ss->buf[pos].startslot;
1407       ss->emptyslots -= (old_nslots - ss->buf[pos].nslots);
1408       add_slots(ss, sslot + nslots, old_nslots - ss->buf[pos].nslots - nslots);
1409       /* CmiPrintf("grab: sslot=%lld nslots=%lld pos=%lld i=%d\n", sslot, nslots, pos, i); */
1410       return;
1411     }
1412   }
1413   CmiAbort("requested a non-existent slotblock\n");
1414 }
1415
1416 /*
1417  * Frees slot by adding it to one of the blocks of empty slots.
1418  * this slotblock is one which is contiguous with the slots to be freed.
1419  * if it cannot find such a slotblock, it creates a new slotblock.
1420  * If the buffer fills up, it adds up extra buffer space.
1421  */
1422 static void
1423 free_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots)
1424 {
1425   /* CmiPrintf("old free: sslot=%lld nslots=%lld\n", sslot, nslots); */
1426   int pos;
1427   /* eslot is the ending slot of the block to be freed */
1428   CmiInt8 eslot = sslot + nslots;
1429   for (pos=0; pos < (ss->maxbuf); pos++)
1430   {
1431     CmiInt8 e = ss->buf[pos].startslot + ss->buf[pos].nslots;
1432     if (ss->buf[pos].nslots == 0)
1433       continue;
1434     /* e is the ending slot of pos'th slotblock */
1435     if (e == sslot) /* append to the current slotblock */
1436     {
1437             ss->buf[pos].nslots += nslots;
1438             ss->emptyslots += nslots;
1439             /* CmiPrintf("free:append pos=%d\n", pos); */
1440             return;
1441     }
1442     if(eslot == ss->buf[pos].startslot) /* prepend to the current slotblock */
1443     {
1444             ss->buf[pos].startslot = sslot;
1445             ss->buf[pos].nslots += nslots;
1446             ss->emptyslots += nslots;
1447             /* CmiPrintf("free:prepend pos=%d\n", pos); */
1448             return;
1449     }
1450   }
1451   /* if we are here, it means we could not find a slotblock that the */
1452   /* block to be freed was combined with. */
1453   /* CmiPrintf("free: pos=%d\n", pos); */
1454   add_slots(ss, sslot, nslots);
1455 }
1456
1457 /*
1458  * destroys slotset-- currently unused
1459 static void
1460 delete_slotset(slotset* ss)
1461 {
1462   free_reentrant(ss->buf);
1463   free_reentrant(ss);
1464 }
1465 */
1466
1467 #if CMK_THREADS_DEBUG
1468 static void
1469 print_slots(slotset *ss)
1470 {
1471   int i;
1472   CmiPrintf("[%d] maxbuf = %d\n", CmiMyPe(), ss->maxbuf);
1473   CmiPrintf("[%d] emptyslots = %d\n", CmiMyPe(), ss->emptyslots);
1474   for(i=0;i<ss->maxbuf;i++) {
1475     if(ss->buf[i].nslots)
1476       CmiPrintf("[%d] (start[%d], end[%d], num=%d) \n", CmiMyPe(), ss->buf[i].startslot, 
1477           ss->buf[i].startslot+ss->buf[i].nslots, ss->buf[i].nslots);
1478   }
1479 }
1480 #else
1481 /*#  define print_slots(ss) */ /*empty*/
1482 static void
1483 print_slots(slotset *ss)
1484 {
1485   int i;
1486   CmiPrintf("[%d] maxbuf = %d\n", CmiMyPe(), ss->maxbuf);
1487   CmiPrintf("[%d] emptyslots = %d\n", CmiMyPe(), ss->emptyslots);
1488   for(i=0;i<ss->maxbuf;i++) {
1489     if(ss->buf[i].nslots)
1490       CmiPrintf("[%d] (start[%d], end[%d], num=%d) \n", CmiMyPe(), ss->buf[i].startslot, 
1491           ss->buf[i].startslot+ss->buf[i].nslots, ss->buf[i].nslots);
1492   }
1493 }
1494
1495 #endif
1496
1497
1498 #endif
1499
1500 /* ======================= END OLD ISOMALLOC ============================ */
1501
1502
1503 /*This version of the allocate/deallocate calls are used if the 
1504 real mmap versions are disabled.*/
1505 static int disabled_map_warned=0;
1506 static void *disabled_map(int nBytes) 
1507 {
1508         if (!disabled_map_warned) {
1509                 disabled_map_warned=1;
1510                 if (CmiMyPe()==0)
1511                         CmiError("charm isomalloc.c> Warning: since mmap() doesn't work,"
1512                         " you won't be able to migrate threads\n");
1513         }
1514         return malloc(nBytes);
1515 }
1516 static void disabled_unmap(void *bk) {
1517         free(bk);
1518 }
1519
1520 /*Turn off isomalloc memory, for the given reason*/
1521 static void disable_isomalloc(const char *why)
1522 {
1523     isomallocStart=NULL;
1524     isomallocEnd=NULL;
1525     if (CmiMyPe() == 0)
1526     CmiPrintf("[%d] isomalloc.c> Disabling isomalloc because %s\n",CmiMyPe(),why);
1527 }
1528
1529 #if ! CMK_HAS_MMAP
1530 /****************** Manipulate memory map (Win32 non-version) *****************/
1531 static void *call_mmap_fixed(void *addr,size_t len) {
1532         CmiAbort("isomalloc.c: mmap_fixed should never be called here.");
1533         return NULL;
1534 }
1535 static void *call_mmap_anywhere(size_t len) {
1536         CmiAbort("isomalloc.c: mmap_anywhere should never be called here.");
1537         return NULL;
1538 }
1539 static void call_munmap(void *addr,size_t len) {
1540         CmiAbort("isomalloc.c: munmap should never be called here.");
1541 }
1542
1543 static int 
1544 init_map(char **argv)
1545 {
1546   return 0; /*Isomalloc never works without mmap*/
1547 }
1548 #else /* CMK_HAS_MMAP */
1549 /****************** Manipulate memory map (UNIX version) *****************/
1550 #include <sys/types.h>
1551 #include <sys/mman.h>
1552 #include <sys/stat.h>
1553 #include <fcntl.h>
1554
1555 #if !CMK_HAS_MMAP_ANON
1556 CpvStaticDeclare(int, zerofd); /*File descriptor for /dev/zero, for mmap*/
1557 #endif
1558
1559 /**
1560  * Maps this address with these flags.
1561  */
1562 static void *call_mmap(void *addr,size_t len, int flags) {
1563   void *ret=mmap(addr, len, PROT_READ|PROT_WRITE,
1564 #if CMK_HAS_MMAP_ANON
1565             flags|MAP_PRIVATE|MAP_ANON,-1,
1566 #else
1567             flags|MAP_PRIVATE,CpvAccess(zerofd),
1568 #endif
1569             0);
1570   if (ret==((void*)(-1))) return (void *)0; /* all-ones means failure */
1571   else return ret;
1572 }
1573 static void *call_mmap_fixed(void *addr,size_t len) {
1574         return call_mmap(addr,len,MAP_FIXED);
1575 }
1576 static void *call_mmap_anywhere(size_t len) {
1577         return call_mmap((void *)0,len,0);
1578 }
1579
1580 /* Unmaps this address range */
1581 static void call_munmap(void *addr,size_t len) {
1582   int retval;
1583   if (addr == 0) return; /* NULL address is never mapped */ 
1584   retval = munmap(addr, len);
1585   if (retval==(-1))
1586     CmiAbort("munmap call failed to deallocate requested memory.\n");
1587 }
1588
1589 static int 
1590 init_map(char **argv)
1591 {
1592 #if CMK_HAS_MMAP_ANON
1593   /*Don't need /dev/zero*/
1594 #else
1595   CpvInitialize(int, zerofd);  
1596   CpvAccess(zerofd) = open("/dev/zero", O_RDWR);
1597   if(CpvAccess(zerofd)<0)
1598     return 0; /* Cannot open /dev/zero or use MMAP_ANON, so can't mmap memory */
1599 #endif
1600   return 1;
1601 }
1602
1603 #endif /* UNIX memory map */
1604
1605 #if USE_MAPREGION
1606
1607 /* method to check if mmap behaved as was desired*/
1608 static int 
1609 check_map(void *pa, void *addr, CmiInt8 requestSize)
1610 {
1611   if (pa != addr)
1612   { /*Map worked, but gave us back the wrong place*/
1613 #if CMK_THREADS_DEBUG
1614     //CmiPrintf("[%d] tried to mmap %p, but got %p back\n",CmiMyPe(),addr,pa);
1615 #endif
1616     call_munmap(pa,requestSize);
1617     return 1;
1618   }
1619
1620   if (pa==NULL)
1621   { /*Map just failed completely*/
1622
1623 #if CMK_THREADS_DEBUG
1624     perror("mmap failed");
1625     //CmiPrintf("[%d] tried to mmap %p, but encountered error\n",CmiMyPe(),addr);
1626 #endif
1627     return 1;
1628   }
1629   return 0;
1630 }
1631
1632 /* method to handle mmap of VM spots beyong processor's local range - uses linked lists,
1633    one for each processor  */
1634 static CmiIsomallocBlock *
1635 remoteSlotmap(CmiInt8 slot, CmiInt8 nslots)
1636 {
1637   void *addr = slot2addr(slot);
1638   void *pa,*newaddr;
1639   maplist *newentry,*temp,*prev,*next;
1640
1641   int whichPE = slot/numslots;
1642   CmiInt8 startRegion, endRegion;
1643   CmiInt8 left, tleft;
1644   maplist **mapList = CpvAccess(mapLists);
1645   CmiInt8 ratio = regionSize/slotsize;
1646
1647   startRegion = (slot/ratio);
1648   endRegion = (slot + nslots - 1)/ratio;
1649
1650   /* new linked list for memory in this range*/
1651   if(mapList[whichPE] == NULL)
1652   {
1653         newentry = (maplist *)(malloc_reentrant(sizeof(maplist)));
1654         newentry->prev = newentry->next = NULL;
1655         newaddr = (void *)(slot2addr(startRegion*ratio));
1656         pa = call_mmap_fixed(newaddr, (endRegion-startRegion+1)*regionSize);
1657         if(check_map(pa,newaddr,(endRegion-startRegion+1)*regionSize))
1658           return NULL;
1659         newentry->start = (startRegion * ratio);
1660         newentry->end = ((endRegion+1) * ratio);
1661         newentry->count = nslots;
1662         mapList[whichPE] = newentry;
1663         return (CmiIsomallocBlock *)addr;
1664   }     
1665
1666   temp = mapList[whichPE];
1667
1668   /* VM region needed should be head of this linked list*/
1669   if((slot + nslots - 1) < temp->start) 
1670   {
1671         newentry = (maplist *)(malloc_reentrant(sizeof(maplist)));
1672         newentry->prev = NULL;
1673         newentry->next = temp;
1674         temp->prev = newentry;
1675         newaddr = (void *)(slot2addr(startRegion*ratio));
1676         pa = call_mmap_fixed(newaddr, (endRegion-startRegion+1)*regionSize);
1677         if(check_map(pa,newaddr,(endRegion-startRegion+1)*regionSize))
1678           return NULL;
1679         newentry->start = (startRegion * ratio);
1680         newentry->end = ((endRegion+1) * ratio);
1681         newentry->count = nslots;
1682         mapList[whichPE] = newentry;
1683         return (CmiIsomallocBlock *)addr;
1684   }
1685
1686   prev = NULL;
1687   while(temp != NULL)
1688   {
1689         if(slot < temp->end)
1690                 break; 
1691         prev = temp;
1692         temp = temp->next;
1693   }
1694
1695   /* VM region needed should be at the end of linked list */ 
1696   if(temp == NULL)
1697   {
1698         newentry = (maplist *)(malloc_reentrant(sizeof(maplist)));
1699         newentry->prev = prev;
1700         prev->next = newentry; 
1701         newentry->next = NULL;
1702         newaddr = (void *)(slot2addr(startRegion*ratio));
1703         pa = call_mmap_fixed(newaddr, (endRegion-startRegion+1)*regionSize);
1704         if(check_map(pa,newaddr,(endRegion-startRegion+1)*regionSize))
1705           return NULL;
1706         newentry->start = (startRegion * ratio);
1707         newentry->end = ((endRegion+1) * ratio);
1708         newentry->count = nslots;
1709         return (CmiIsomallocBlock *)addr;
1710   }
1711
1712   left = nslots;
1713
1714   /* VM region needed should be added before temp region */
1715   if((slot + nslots - 1) < temp->start)
1716   {
1717         newentry = (maplist *)(malloc_reentrant(sizeof(maplist)));
1718         newentry->prev = prev;
1719         prev->next = newentry; 
1720         newentry->next = temp;
1721         temp->prev = newentry;
1722         newaddr = (void *)(slot2addr(startRegion*ratio));
1723         pa = call_mmap_fixed(newaddr, (endRegion-startRegion+1)*regionSize);
1724         if(check_map(pa,newaddr,(endRegion-startRegion+1)*regionSize))
1725           return NULL;
1726         newentry->start = (startRegion * ratio);
1727         newentry->end = ((endRegion+1) * ratio);
1728         newentry->count = nslots;
1729         return (CmiIsomallocBlock *)addr;
1730   }
1731
1732   /* VM region needed starts before temp but overlaps with it */
1733   if((slot < temp->start))
1734   {
1735         tleft = (slot + nslots - temp->start);
1736         temp->count += tleft;
1737         left -= tleft;
1738         endRegion = (temp->start/ratio) - 1;
1739
1740         newentry = (maplist *)(malloc_reentrant(sizeof(maplist)));
1741         if(mapList[whichPE] == temp)
1742         {
1743                 mapList[whichPE] = newentry;
1744                 newentry->prev = NULL;
1745         }
1746         else
1747         {
1748                 newentry->prev = prev;
1749                 prev->next = newentry;
1750         }
1751         temp->prev = newentry;
1752         newentry->next = temp;
1753         newaddr = (void *)(slot2addr(startRegion*ratio));
1754         pa = call_mmap_fixed(newaddr, (endRegion-startRegion+1)*regionSize);
1755         if(check_map(pa,newaddr,(endRegion-startRegion+1)*regionSize))
1756           return NULL;
1757         newentry->start = (startRegion * ratio);
1758         newentry->end = ((endRegion+1) * ratio);
1759         newentry->count = left;
1760         return (CmiIsomallocBlock *)addr;
1761   }
1762  
1763   tleft = temp->end - slot;
1764   if(tleft >= nslots)
1765   {
1766         temp->count += nslots;
1767         return (CmiIsomallocBlock *)addr;
1768   }
1769   else
1770   {
1771         temp->count += tleft;
1772         left -= tleft;
1773         startRegion = temp->end/ratio;
1774   }
1775          
1776   next = temp->next;
1777
1778   if(next != NULL)
1779   {
1780           if((slot + nslots) > next->start)
1781           {
1782                 tleft = (slot + nslots - next->start);
1783                 next->count += tleft;
1784                 left -= tleft;
1785                 if(left <= 0)
1786                 {
1787                         return (CmiIsomallocBlock *)addr;
1788                 }
1789                 endRegion = (next->start/ratio)-1;
1790           }
1791   }
1792
1793   /* add a new region in between 2 existing region */    
1794   newentry = (maplist *)(malloc_reentrant(sizeof(maplist)));
1795   newentry->prev = temp;
1796   temp->next = newentry;
1797   newentry->next = next;
1798   if(next != NULL)
1799         next->prev = newentry;
1800   newaddr = (void *)(slot2addr(startRegion*ratio));
1801   pa = call_mmap_fixed(newaddr, (endRegion-startRegion+1)*regionSize);
1802   if(check_map(pa,newaddr,(endRegion-startRegion+1)*regionSize))
1803     return NULL;
1804   newentry->start = (startRegion * ratio);
1805   newentry->end = ((endRegion+1) * ratio);
1806   newentry->count = left;
1807   return (CmiIsomallocBlock *)addr;
1808   
1809 }
1810 #endif
1811
1812 #if USE_MAPREGION
1813 /**
1814  * maps the virtual memory associated with slot using mmap
1815    using list based mmap slot maintenance
1816  */
1817 static CmiIsomallocBlock *
1818 map_slots(CmiInt8 slot, CmiInt8 nslots)
1819 {
1820   void *pa;
1821   void *addr,*newaddr;
1822   int ratio, checkmap;
1823   CmiInt8 i, starti, endi, j;
1824   CmiInt8 start1off, start2off, end1off, end2off;
1825   CmiInt8 off1, off2, temp, toff1, toff2;
1826   CmiInt8 actualSlot, requestSize, begin, currentR;
1827   CmiInt8 startAddr, left, tleft, extraleft;
1828
1829   mapRegion *mapregion = CpvAccess(mapRegions);
1830   CmiInt8 startSlot, endSlot;
1831
1832   startSlot = pe2slot(CmiMyPe());
1833   endSlot = startSlot + numslots - 1;
1834   if((slot < startSlot) || (slot > endSlot))
1835         return ((CmiIsomallocBlock *)remoteSlotmap(slot,nslots)); 
1836
1837   startAddr = (CmiInt8)slot2addr(slot);
1838   addr = slot2addr(slot);
1839         
1840   ratio = regionSize/slotsize;
1841   actualSlot = slot - pe2slot(CmiMyPe());
1842   left = nslots;
1843
1844   start1off = actualSlot/(1024*ratio);
1845   start2off = (actualSlot - 1024*ratio*start1off)/ratio;
1846   currentR = (1024*start1off) + start2off;  
1847
1848   end1off = (actualSlot + nslots - 1)/(1024*ratio);
1849   end2off = (actualSlot + nslots - 1 - 1024*ratio*end1off)/ratio;
1850
1851   if(!(end1off < mapregion->count))
1852   {
1853         starti = mapregion->count;
1854         endi = end1off + 11;
1855         for(i = starti; i < endi; i++)
1856         {
1857                 mapregion->counter[i] = (int *)(malloc_reentrant
1858                                         (1024 * sizeof(int)));
1859                 mapregion->marker[i] = (CmiInt8 *)(malloc_reentrant
1860                                         (1024 * sizeof(CmiInt8)));
1861                 for(j = 0; j < 1024; j++)
1862                 {
1863                         mapregion->counter[i][j] = 0;
1864                         mapregion->marker[i][j] = -1;
1865                 }
1866         }       
1867         mapregion->count = endi;
1868   } 
1869
1870   temp = mapregion->marker[start1off][start2off];
1871  
1872   if(temp != -1)
1873   {
1874         if(temp >= currentR)
1875         {
1876                 begin = currentR;
1877         }       
1878         else
1879         {
1880                 begin = temp;
1881                 temp = mapregion->marker[begin/1024][begin - ((begin/1024)*1024)];
1882         }
1883         tleft = (((temp + 1)*ratio) - actualSlot);
1884         off1 = begin/1024;
1885         off2 = begin - (off1 * 1024);
1886         if(left <= tleft)
1887         {
1888                 mapregion->counter[off1][off2] += left ;        
1889                 return (CmiIsomallocBlock *)addr;
1890         }               
1891         else
1892         {
1893                 mapregion->counter[off1][off2] += tleft ;       
1894                 left -= tleft;
1895                 off1 = (temp+1)/1024;
1896                 off2 = (temp+1) - (off1 * 1024);
1897         }
1898   }                     
1899   else
1900   {
1901         off1 = start1off;
1902         off2 = start2off;
1903   }
1904
1905   extraleft = 0;
1906   if(mapregion->marker[start1off][start2off] == -1)
1907   {
1908         extraleft = actualSlot % ratio;
1909   }
1910  
1911   temp = mapregion->marker[end1off][end2off];
1912   currentR = (1024*end1off) + end2off;  
1913   
1914   if(temp != -1)
1915   {
1916         if(temp > currentR)
1917         {
1918                 temp = currentR;
1919         }       
1920         toff1 = temp/1024;
1921         toff2 = temp - (toff1*1024);
1922         tleft = (actualSlot + nslots) - (temp * ratio);
1923         mapregion->counter[toff1][toff2] += tleft;
1924         left -= tleft;
1925         end1off = (temp - 1)/1024;
1926         end2off = (temp - 1) - (end1off * 1024);
1927   }     
1928
1929   if((end1off < off1)||((end1off == off1)&&(end2off < off2)))
1930   {
1931         return (CmiIsomallocBlock *)addr;
1932   }
1933
1934   requestSize = ((left + extraleft + (ratio-1))/ratio)*regionSize;
1935   newaddr = (void*)((CmiInt8)slot2addr(pe2slot(CmiMyPe())));
1936   newaddr = (void*)((CmiInt8)newaddr + ((1024*off1 + off2)*regionSize));
1937   pa = call_mmap_fixed(newaddr, requestSize);
1938   if (pa != newaddr)
1939   { /*Map worked, but gave us back the wrong place*/
1940 #if CMK_THREADS_DEBUG
1941     //CmiPrintf("[%d] tried to mmap %p, but got %p back\n",CmiMyPe(),newaddr,pa);
1942 #endif
1943     call_munmap(newaddr,requestSize);
1944     return NULL;
1945   }
1946
1947   if (pa==NULL)
1948   { /*Map just failed completely*/
1949
1950 #if CMK_THREADS_DEBUG
1951     perror("mmap failed");
1952     //CmiPrintf("[%d] tried to mmap %p, but encountered error\n",CmiMyPe(),addr);
1953 #endif
1954     return NULL;
1955   }
1956 #if CMK_THREADS_DEBUG
1957   //CmiPrintf("[%d] mmap'd slots %ld-%ld to address %p\n",CmiMyPe(),
1958             slot,slot+nslots-1,addr);
1959 #endif
1960
1961   mapregion->counter[off1][off2] += left;
1962   mapregion->marker[off1][off2] = 1024*end1off + end2off;
1963
1964   temp = (1024 * off1) + off2;
1965
1966   starti = off2 + 1;
1967   if(off1 == end1off)
1968         endi = end2off + 1;
1969   else
1970         endi = 1024;
1971
1972   for(i = starti; i < endi; i++)
1973   {
1974         mapregion->marker[off1][i] = temp;
1975   }
1976  
1977   starti = off1 + 1;
1978   endi = end1off;
1979   for(i = starti; i < endi; i++)
1980   {
1981         for(j = 0; j < 1024; j++)       
1982                 mapregion->marker[i][j] = temp;
1983   }
1984
1985   starti = 0;
1986   if(off1 == end1off)
1987         endi = 0;
1988   else
1989         endi = end2off + 1;
1990
1991   for(i = starti; i < endi; i++)
1992   {
1993         mapregion->marker[end1off][i] = temp;
1994   }
1995
1996   return (CmiIsomallocBlock *)addr;
1997 }
1998
1999 #else
2000
2001 /**
2002  * maps the virtual memory associated with slot using mmap
2003  */
2004 static CmiIsomallocBlock *
2005 map_slots(CmiInt8 slot, CmiInt8 nslots)
2006 {
2007   void *pa;
2008   void *addr=slot2addr(slot);
2009   pa = call_mmap_fixed(addr, slotsize*nslots);
2010
2011   if (pa==NULL)
2012   { /*Map just failed completely*/
2013 #if CMK_THREADS_DEBUG
2014     perror("mmap failed");
2015     CmiPrintf("[%d] tried to mmap %p, but encountered error\n",CmiMyPe(),addr);
2016 #endif
2017     return NULL;
2018   }
2019   if (pa != addr)
2020   { /*Map worked, but gave us back the wrong place*/
2021 #if CMK_THREADS_DEBUG
2022     CmiPrintf("[%d] tried to mmap %p, but got %p back\n",CmiMyPe(),addr,pa);
2023 #endif
2024     call_munmap(addr,slotsize*nslots);
2025     return NULL;
2026   }
2027 #if CMK_THREADS_DEBUG
2028   CmiPrintf("[%d] mmap'd slots %ld-%ld to address %p\n",CmiMyPe(),
2029             slot,slot+nslots-1,addr);
2030 #endif
2031   return (CmiIsomallocBlock *)pa;
2032 }
2033 #endif //end of else of if USE_MAPREGION 
2034
2035 #if USE_MAPREGION
2036
2037 /* method to delete a node of in a linked list */
2038 static void
2039 freelistentry(maplist *target)
2040 {
2041         maplist *prev,*next;
2042         prev = target->prev;
2043         next = target->next;
2044         if(prev != NULL)
2045                 prev->next = next;
2046         if(next != NULL)
2047                 next->prev = prev;
2048         free_reentrant(target);
2049 }
2050
2051 /* method to free an entry for VM not in range of my processor */
2052 static void 
2053 remoteSlotunmap(CmiInt8 slot, CmiInt8 nslots)
2054 {
2055   void *addr = slot2addr(slot);
2056   void *pa,*newaddr;
2057   maplist *temp,*tofree;
2058
2059   CmiInt8 left, tleft;
2060   maplist **mapList = CpvAccess(mapLists);
2061   CmiInt8 ratio = regionSize/slotsize;
2062
2063   int whichPE = slot/numslots;
2064
2065   if(mapList[whichPE] == NULL)
2066   {
2067         return;
2068   }
2069
2070   temp = mapList[whichPE];
2071
2072   while(temp != NULL)
2073   {
2074         if(slot < temp->end)
2075                 break;
2076         temp = temp->next;
2077   }
2078   if(temp == NULL)
2079   {
2080         return;
2081   }
2082
2083   left = nslots;
2084
2085   tleft = temp->end - slot;
2086   if(tleft >= nslots)
2087   {
2088         temp->count -= nslots;
2089         left -= nslots;
2090   }
2091   else
2092   {
2093         temp->count -= tleft;
2094         left -= tleft;
2095   }
2096
2097   tofree = temp;
2098   temp = temp->next;
2099   if(tofree->count <= 0)
2100   {
2101         newaddr = (void *)(slot2addr(tofree->start));
2102         call_munmap(newaddr, (tofree->end - tofree->start)*slotsize);
2103         if(tofree == mapList[whichPE])
2104         {
2105                 mapList[whichPE] = tofree->next;
2106         }
2107         freelistentry(tofree);
2108   }
2109
2110   if((temp == NULL) || (left <= 0))
2111   {
2112         return;
2113   }
2114
2115   if((slot+nslots-1) < temp->end)
2116   {
2117         tleft = slot + nslots - temp->start;
2118   }
2119   else
2120   {
2121         tleft = temp->count;
2122   }
2123
2124   temp->count -= tleft;
2125   left -= tleft;
2126
2127   tofree = temp;
2128   temp = temp->next;
2129   if(tofree->count <= 0)
2130   {
2131         newaddr = (void *)(slot2addr(tofree->start));
2132         call_munmap(newaddr, (tofree->end - tofree->start)*slotsize);
2133         if(tofree == mapList[whichPE])
2134         {
2135                 mapList[whichPE] = tofree->next;
2136         }
2137         freelistentry(tofree);
2138   }
2139
2140   if((temp == NULL) || (left <= 0))
2141   {
2142       return;
2143   }
2144
2145   tleft = slot + nslots - temp->start;
2146   temp->count -= tleft;
2147   left -= tleft;
2148
2149   tofree = temp;
2150
2151   if(tofree->count <= 0)
2152   {
2153         newaddr = (void *)(slot2addr(tofree->start));
2154         call_munmap(newaddr, (tofree->end - tofree->start)*slotsize);
2155         if(tofree == mapList[whichPE])
2156         {
2157                 mapList[whichPE] = tofree->next;
2158         }
2159         freelistentry(tofree);
2160   }
2161 }
2162 #endif
2163
2164 #if USE_MAPREGION
2165
2166 /*
2167  * unmaps the virtual memory associated with slot using munmap and in the list
2168  */
2169 static void
2170 unmap_slots(CmiInt8 slot, CmiInt8 nslots)
2171 {
2172   void *addr=slot2addr(slot);
2173
2174   mapRegion *mapregion;
2175   CmiInt8 start1off, start2off, end1off, end2off;
2176   CmiInt8 off1, off2, requestSize;
2177   CmiInt8 actualSlot, temp, left, tleft;
2178   CmiInt8 i, starti, endi, j;
2179   CmiInt8 currentR, begin;
2180   int ratio;
2181
2182   CmiInt8 startSlot, endSlot;
2183   startSlot = pe2slot(CmiMyPe());
2184   endSlot = startSlot + numslots - 1;
2185   if((slot < startSlot) || (slot > endSlot))
2186   {
2187     remoteSlotunmap(slot,nslots); 
2188     return;
2189   }
2190
2191   mapregion = CpvAccess(mapRegions);
2192
2193   ratio = regionSize/slotsize;
2194   actualSlot = slot - pe2slot(CmiMyPe());
2195   left = nslots;
2196
2197   start1off = actualSlot/(1024*ratio);
2198   start2off = (actualSlot - (start1off*1024*ratio))/ratio;
2199   currentR = (1024*start1off + start2off);  
2200
2201   end1off = (actualSlot+nslots-1)/(1024*ratio);
2202   end2off = (actualSlot+nslots-1 - (end1off*1024*ratio))/ratio;
2203
2204   temp = mapregion->marker[start1off][start2off];
2205
2206   if(temp >= currentR)
2207   {
2208         begin = currentR;
2209   }
2210   else
2211   {
2212         begin = temp;
2213         temp = mapregion->marker[begin/1024][begin - ((begin/1024)*1024)]; 
2214   }
2215
2216   tleft = (ratio*(temp+1)) - actualSlot;
2217   off1 = begin/1024;
2218   off2 = begin - (off1*1024);
2219
2220   if(tleft >= nslots)
2221   {
2222         mapregion->counter[off1][off2] -= nslots;
2223         left -= nslots;
2224   }
2225   else
2226   {
2227         mapregion->counter[off1][off2] -= tleft;
2228         left -= tleft;
2229   }
2230
2231   if(mapregion->counter[off1][off2] == 0)
2232   {
2233         addr = (void*)((CmiInt8)slot2addr(pe2slot(CmiMyPe())));
2234         addr = (void*)((CmiInt8)addr + ((1024*off1 + off2)*regionSize));
2235         call_munmap(addr,(temp+1-begin)*regionSize);
2236         for(i = begin; i <= temp; i++)
2237         {
2238                 mapregion->marker[i/1024][i - ((i/1024)*1024)] = -1;
2239         }
2240   }
2241
2242  if(left <= 0)
2243         return;
2244
2245   starti = temp + 1;
2246
2247   currentR = (1024*end1off + end2off);
2248   temp = mapregion->marker[end1off][end2off];
2249
2250   if(temp >= currentR)
2251   {
2252         begin = currentR;
2253   }
2254   else
2255   {
2256         begin = temp;
2257         temp = mapregion->marker[begin/1024][begin - ((begin/1024)*1024)]; 
2258   }
2259
2260   tleft = (actualSlot+nslots) - (ratio*begin);
2261   off1 = begin/1024;
2262   off2 = begin - (off1*1024);
2263
2264   mapregion->counter[off1][off2] -= tleft;
2265   left -= tleft;
2266
2267   if(mapregion->counter[off1][off2] == 0)
2268   {
2269         addr = (void*)((CmiInt8)slot2addr(pe2slot(CmiMyPe())));
2270         addr = (void*)((CmiInt8)addr + ((1024*off1 + off2)*regionSize));
2271         call_munmap(addr,(temp+1-begin)*regionSize);
2272         for(i = begin; i <= temp; i++)
2273         {
2274                 mapregion->marker[i/1024][i - ((i/1024)*1024)] = -1;
2275         }
2276   }
2277
2278   if(left <= 0)
2279         return;
2280
2281   endi = begin;
2282
2283   begin = starti;
2284   off1 = begin/1024;
2285   off2 = begin - (1024*off1);
2286   temp = mapregion->marker[off1][off2];
2287   mapregion->counter[off1][off2] = 0;
2288   
2289   addr = (void*)((CmiInt8)slot2addr(pe2slot(CmiMyPe())));
2290   addr = (void*)((CmiInt8)addr + ((1024*off1 + off2)*regionSize));
2291   call_munmap(addr,(temp+1-begin)*regionSize);
2292
2293   for(i = starti; i < endi; i++)
2294   {
2295         mapregion->marker[i/1024][i - ((i/1024)*1024)] = -1;
2296   }     
2297
2298
2299 #if CMK_THREADS_DEBUG
2300   CmiPrintf("[%d] munmap'd slots %ld-%ld from address %p\n",CmiMyPe(),
2301             slot,slot+nslots-1,addr);
2302 #endif
2303 }
2304 #else
2305
2306 /*
2307  * unmaps the virtual memory associated with slot using munmap
2308  */
2309 static void
2310 unmap_slots(CmiInt8 slot, CmiInt8 nslots)
2311 {
2312   void *addr=slot2addr(slot);
2313   call_munmap(addr, slotsize*nslots);
2314 #if CMK_THREADS_DEBUG
2315   CmiPrintf("[%d] munmap'd slots %ld-%ld from address %p\n",CmiMyPe(),
2316             slot,slot+nslots-1,addr);
2317 #endif
2318 }
2319 #endif 
2320
2321 static void map_failed(CmiInt8 s,CmiInt8 n)
2322 {
2323   void *addr=slot2addr(s);
2324   CmiError("charm isomalloc.c> map failed to allocate %d bytes at %p, errno:%d.\n",
2325       slotsize*n, addr, errno);
2326   CmiAbort("Exiting\n");
2327 }
2328
2329
2330
2331 /************ Address space voodoo: find free address range **********/
2332
2333 CpvStaticDeclare(slotset *, myss); /*My managed slots*/
2334
2335 /*This struct describes a range of virtual addresses*/
2336 typedef struct {
2337   char *start; /*First byte of region*/
2338   memRange_t len; /*Number of bytes in region*/
2339   const char *type; /*String describing memory in region (debugging only)*/
2340 } memRegion_t;
2341
2342 /*Estimate the top of the current stack*/
2343 static void *__cur_stack_frame(void)
2344 {
2345   char __dummy;
2346   void *top_of_stack=(void *)&__dummy;
2347   return top_of_stack;
2348 }
2349 /*Estimate the location of the static data region*/
2350 static void *__static_data_loc(void)
2351 {
2352   static char __dummy;
2353   return (void *)&__dummy;
2354 }
2355
2356 /*Pointer comparison is in these subroutines, because
2357   comparing arbitrary pointers is nonportable and tricky.
2358 */
2359 static int pointer_lt(const char *a,const char *b) {
2360         return ((memRange_t)a)<((memRange_t)b);
2361 }
2362 static int pointer_ge(const char *a,const char *b) {
2363         return ((memRange_t)a)>=((memRange_t)b);
2364 }
2365
2366 static char *pmin(char *a,char *b) {return pointer_lt(a,b)?a:b;}
2367 static char *pmax(char *a,char *b) {return pointer_lt(a,b)?b:a;}
2368
2369 const static memRange_t meg=1024u*1024u; /*One megabyte*/
2370 const static memRange_t gig=1024u*1024u*1024u; /*One gigabyte*/
2371
2372 /*Check if this memory location is usable.  
2373   If not, return 1.
2374 */
2375 static int bad_location(char *loc) {
2376   void *addr;
2377   addr=call_mmap_fixed(loc,slotsize);
2378   if (addr==NULL || addr!=loc) {
2379 #if CMK_THREADS_DEBUG
2380     CmiPrintf("[%d] Skipping unmappable space at %p\n",CmiMyPe(),loc);
2381 #endif
2382     return 1; /*No good*/
2383   }
2384   call_munmap(addr,slotsize);
2385   return 0; /*This works*/
2386 }
2387
2388 /* Split this range up into n pieces, returning the size of each piece */
2389 static memRange_t divide_range(memRange_t len,int n) {
2390         return (len+1)/n;
2391 }
2392
2393 /* Return if this memory region has *any* good parts. */
2394 static int partially_good(char *start,memRange_t len,int n) {
2395   int i;
2396   memRange_t quant=divide_range(len,n);
2397   CmiAssert (quant > 0);
2398   for (i=0;i<n;i++)
2399     if (!bad_location(start+i*quant)) return 1; /* it's got some good parts */
2400   return 0; /* all locations are bad */
2401 }
2402
2403 /* Return if this memory region is usable at n samples.  
2404 */
2405 static int good_range(char *start,memRange_t len,int n) {
2406   int i;
2407   memRange_t quant=divide_range(len,n);
2408 #if CMK_THREADS_DEBUG
2409   CmiPrintf("good_range: %lld, %d\n", quant, n);
2410 #endif
2411   CmiAssert (quant > 0);
2412
2413   for (i=0;i<n;i++)
2414     if (bad_location(start+i*quant)) return 0; /* it's got some bad parts */
2415   /* It's all good: */
2416   return 1;
2417 }
2418
2419 /*Check if this entire memory range, or some subset 
2420   of the range, is usable.  If so, write it into max.
2421 */
2422 static void check_range(char *start,char *end,memRegion_t *max)
2423 {
2424   memRange_t len;
2425   CmiUInt8 tb = (CmiUInt8)gig*1024ul;   /* One terabyte */
2426   CmiUInt8 vm_limit = tb*256ul;   /* terabyte */
2427
2428   if (start>=end) return; /*Ran out of hole*/
2429   len=(memRange_t)end-(memRange_t)start;
2430   
2431 #if 0
2432     /* too conservative */
2433   if (len/gig>64u) { /* This is an absurd amount of space-- cut it down, for safety */
2434      start+=16u*gig;
2435      end=start+32u*gig;
2436      len=(memRange_t)end-(memRange_t)start;  
2437   }
2438 #else
2439   /* Note: 256TB == 248 bytes.  So a 48-bit virtual-address CPU 
2440    *    can only actually address 256TB of space. */
2441   if (len/tb>10u) { /* This is an absurd amount of space-- cut it down, for safety */
2442     const memRange_t other_libs=16ul*gig; /* space for other libraries to use */
2443     start+=other_libs;
2444     end=pmin(start+vm_limit-2*other_libs, end-other_libs);
2445     len=(memRange_t)end-(memRange_t)start;
2446   }
2447 #endif
2448   if (len<=max->len) return; /*It's too short already!*/
2449 #if CMK_THREADS_DEBUG
2450   CmiPrintf("[%d] Checking at %p - %p\n",CmiMyPe(),start,end);
2451 #endif
2452   
2453   /* Check the middle of the range */
2454   if (!good_range(start,len,256)) {
2455     /* Try to split into subranges: */
2456     int i,n=2;
2457 #if CMK_THREADS_DEBUG
2458     CmiPrintf("[%d] Trying to split bad address space at %p - %p...\n",CmiMyPe(),start,end);
2459 #endif
2460     len=divide_range(len,n);
2461     for (i=0;i<n;i++) {
2462         char *cur=start+i*len;
2463         if (partially_good(cur,len,16))
2464            check_range(cur,cur+len,max);
2465     }
2466     return; /* Hopefully one of the subranges will be any good */
2467   }
2468   else /* range is good */
2469   { 
2470 #if CMK_THREADS_DEBUG
2471     CmiPrintf("[%d] Address space at %p - %p is largest\n",CmiMyPe(),start,end);
2472 #endif
2473
2474     /*If we got here, we're the new largest usable range*/
2475     max->len=len;
2476     max->start=start;
2477     max->type="Unused";
2478   }
2479 }
2480
2481 /*Find the first available memory region of at least the
2482   given size not touching any data in the used list.
2483  */
2484 static memRegion_t find_free_region(memRegion_t *used,int nUsed,int atLeast) 
2485 {
2486   memRegion_t max;
2487   int i,j;  
2488
2489   max.start=0; 
2490   max.len=atLeast;
2491   /*Find the largest hole between regions*/
2492   for (i=0;i<nUsed;i++) {
2493     /*Consider a hole starting at the end of region i*/
2494     char *holeStart=used[i].start+used[i].len;
2495     char *holeEnd=(void *)(-1);
2496     
2497     /*Shrink the hole by all others*/ 
2498     for (j=0;j<nUsed && pointer_lt(holeStart,holeEnd);j++) {
2499       if (pointer_lt(used[j].start,holeStart)) 
2500         holeStart=pmax(holeStart,used[j].start+used[j].len);
2501       else if (pointer_lt(used[j].start,holeEnd)) 
2502         holeEnd=pmin(holeEnd,used[j].start);
2503     } 
2504
2505     check_range(holeStart,holeEnd,&max);
2506   }
2507
2508   return max; 
2509 }
2510
2511 /*
2512 By looking at the address range carefully, try to find 
2513 the largest usable free region on the machine.
2514 */
2515 static int find_largest_free_region(memRegion_t *destRegion) {
2516     char *staticData =(char *) __static_data_loc();
2517     char *code = (char *)&find_free_region;
2518     char *threadData = (char *)&errno;
2519     char *codeDll = (char *)fprintf;
2520     char *heapLil = (char*) malloc(1);
2521     char *heapBig = (char*) malloc(6*meg);
2522     char *stack = (char *)__cur_stack_frame();
2523     size_t mmapAnyLen = 1*meg;
2524     char *mmapAny = (char*) call_mmap_anywhere(mmapAnyLen);
2525
2526     int i,nRegions=0;
2527     memRegion_t regions[10]; /*used portions of address space*/
2528     memRegion_t freeRegion; /*Largest unused block of address space*/
2529
2530 /*Mark off regions of virtual address space as ususable*/
2531     regions[nRegions].type="NULL";
2532     regions[nRegions].start=NULL; 
2533 #if CMK_POWER7 && CMK_64BIT
2534     regions[nRegions++].len=2u*gig;   /* on bluedrop, don't mess with the lower memory region */
2535 #else
2536     regions[nRegions++].len=16u*meg;
2537 #endif
2538             
2539     regions[nRegions].type="Static program data";
2540     regions[nRegions].start=staticData; regions[nRegions++].len=256u*meg;
2541
2542     regions[nRegions].type="Program executable code";
2543     regions[nRegions].start=code; regions[nRegions++].len=256u*meg;
2544
2545     regions[nRegions].type="Heap (small blocks)";
2546     regions[nRegions].start=heapLil; regions[nRegions++].len=1u*gig;
2547
2548     regions[nRegions].type="Heap (large blocks)";
2549     regions[nRegions].start=heapBig; regions[nRegions++].len=1u*gig;
2550
2551     regions[nRegions].type="Stack space";
2552     regions[nRegions].start=stack; regions[nRegions++].len=256u*meg;
2553
2554     regions[nRegions].type="Program dynamically linked code";
2555     regions[nRegions].start=codeDll; regions[nRegions++].len=256u*meg; 
2556
2557     regions[nRegions].type="Result of a non-fixed call to mmap";
2558     regions[nRegions].start=mmapAny; regions[nRegions++].len=2u*gig; 
2559
2560     regions[nRegions].type="Thread private data";
2561     regions[nRegions].start=threadData; regions[nRegions++].len=256u*meg; 
2562
2563     _MEMCHECK(heapBig); free(heapBig);
2564     _MEMCHECK(heapLil); free(heapLil); 
2565     call_munmap(mmapAny,mmapAnyLen);
2566     
2567     /*Align each memory region*/
2568     for (i=0;i<nRegions;i++) {
2569       memRegion_t old=regions[i];
2570       memRange_t p=(memRange_t)regions[i].start;
2571       p&=~(regions[i].len-1); /*Round start down to a len-boundary (mask off low bits)*/
2572       regions[i].start=(char *)p;
2573 #if CMK_MACOSX
2574       if (regions[i].start+regions[i].len*2>regions[i].start) regions[i].len *= 2;
2575 #endif
2576 #if CMK_THREADS_DEBUG
2577       CmiPrintf("[%d] Memory map: %p - %p (len: %lu => %lu) %s \n",CmiMyPe(),
2578               regions[i].start,regions[i].start+regions[i].len,
2579               old.len, regions[i].len, regions[i].type);
2580 #endif
2581     }
2582     
2583     /*Find a large, unused region in this map: */
2584     freeRegion=find_free_region(regions,nRegions,(512u)*meg);
2585     
2586     if (freeRegion.start==0) 
2587     { /*No free address space-- disable isomalloc:*/
2588       return 0;
2589     }
2590     else /* freeRegion is valid */
2591     {
2592       *destRegion=freeRegion;
2593       
2594       return 1;
2595     }
2596 }
2597
2598 static int try_largest_mmap_region(memRegion_t *destRegion)
2599 {
2600   void *bad_alloc=(void*)(-1); /* mmap error return address */
2601   void *range, *good_range=NULL;
2602   double shrink = 1.5;
2603   static int count = 0;
2604   size_t size=((size_t)(-1l)), good_size=0;
2605   int retry = 0;
2606   if (sizeof(size_t) >= 8) size = size>>2;  /* 25% of machine address space! */
2607   while (1) { /* test out an allocation of this size */
2608 #if CMK_HAS_MMAP
2609         range=mmap(NULL,size,PROT_READ|PROT_WRITE,
2610                      MAP_PRIVATE
2611 #if CMK_HAS_MMAP_ANON
2612                      |MAP_ANON
2613 #endif
2614 #if CMK_HAS_MMAP_NORESERVE
2615                      |MAP_NORESERVE
2616 #endif
2617                      ,-1,0);
2618 #else
2619         range = bad_alloc;
2620 #endif
2621         if (range == bad_alloc) {  /* mmap failed */
2622 #if CMK_THREADS_DEBUG
2623                 /* CmiPrintf("[%d] test failed at size: %llu error: %d\n", CmiMyPe(), size, errno);  */
2624 #endif
2625 #if CMK_HAS_USLEEP
2626                 if (retry++ < 5) { usleep(rand()%10000); continue; }
2627                 else retry = 0;
2628 #endif
2629                 size=(double)size/shrink; /* shrink request */
2630                 if (size<=0) return 0; /* mmap doesn't work */
2631         }
2632         else { /* this allocation size is available */
2633 #if CMK_THREADS_DEBUG
2634                CmiPrintf("[%d] available: %p, %lld\n", CmiMyPe(), range, size);
2635 #endif
2636                call_munmap(range,size); /* needed/wanted? */
2637                 if (size > good_size) {
2638                   good_range = range;
2639                   good_size = size;
2640                   size=((double)size)*1.1;
2641                   continue;
2642                 }
2643                 break;
2644         }
2645   }
2646   CmiAssert(good_range!=NULL);
2647   destRegion->start=good_range; 
2648   destRegion->len=good_size;
2649 #if CMK_THREADS_DEBUG
2650 pid_t pid = getpid();
2651 {
2652 char s[128];
2653 sprintf(s, "cat /proc/%d/maps", pid);
2654 system(s);
2655 }
2656   CmiPrintf("[%d] try_largest_mmap_region: %p, %lld\n", CmiMyPe(), good_range, good_size);
2657 #endif
2658   return 1;
2659 }
2660
2661 #ifndef CMK_CPV_IS_SMP
2662 #define CMK_CPV_IS_SMP
2663 #endif
2664
2665 static void init_ranges(char **argv)
2666 {
2667   memRegion_t freeRegion;
2668   /*Largest value a signed int can hold*/
2669   memRange_t intMax=(((memRange_t)1)<<(sizeof(int)*8-1))-1;
2670   int pagesize = 0;
2671
2672
2673 #if USE_MAPREGION
2674   /*Round regionSize size up to nearest page size*/
2675   CmiInt8 i,j;
2676   maplist **mapList;
2677   mapRegion *mapregion;
2678   slotsize = 128;
2679   regionSize=16*1024;
2680
2681 #if CMK_HAS_GETPAGESIZE
2682   pagesize = getpagesize();
2683 #endif
2684   if (pagesize < CMK_MEMORY_PAGESIZE)
2685     pagesize = CMK_MEMORY_PAGESIZE;
2686   regionSize=(regionSize+pagesize-1) & ~(pagesize-1);
2687 #else
2688   /*Round slot size up to nearest page size*/
2689   slotsize=16*1024;
2690 #if CMK_HAS_GETPAGESIZE
2691   pagesize = getpagesize();
2692 #endif
2693   if (pagesize < CMK_MEMORY_PAGESIZE)
2694     pagesize = CMK_MEMORY_PAGESIZE;
2695   slotsize=(slotsize+pagesize-1) & ~(pagesize-1);
2696 #endif
2697
2698 #if CMK_THREADS_DEBUG
2699   if (CmiMyPe() == 0)
2700   CmiPrintf("[%d] Using slotsize of %d\n", CmiMyPe(), slotsize);
2701 #endif
2702   freeRegion.len=0u;
2703
2704   if (CmiMyRank()==0 && numslots==0)
2705   { /* Find the largest unused region of virtual address space */
2706 #ifdef CMK_MMAP_START_ADDRESS /* Hardcoded start address, for machines where automatic fails */
2707       freeRegion.start=CMK_MMAP_START_ADDRESS;
2708       freeRegion.len=CMK_MMAP_LENGTH_MEGS*meg;
2709 #endif
2710       
2711       if (freeRegion.len==0u)  {
2712         if (_mmap_probe == 1) {
2713           if (try_largest_mmap_region(&freeRegion)) _sync_iso = 1;
2714         }
2715         else {
2716           if (freeRegion.len==0u) find_largest_free_region(&freeRegion);
2717         }
2718       }
2719
2720 #if 0
2721       /*Make sure our largest slot number doesn't overflow an int:*/
2722       if (freeRegion.len/slotsize>intMax)
2723         freeRegion.len=intMax*slotsize;
2724 #endif
2725       
2726       if (freeRegion.len==0u) {
2727         disable_isomalloc("no free virtual address space");
2728       }
2729       else /* freeRegion.len>0, so can isomalloc */
2730       {
2731 #if CMK_THREADS_DEBUG
2732         CmiPrintf("[%d] Isomalloc memory region: %p - %p (%d megs)\n",CmiMyPe(),
2733               freeRegion.start,freeRegion.start+freeRegion.len,
2734               freeRegion.len/meg);
2735 #endif
2736       }
2737   }             /* end if myrank == 0 */
2738
2739   CmiNodeAllBarrier();
2740
2741     /*
2742        on some machines, isomalloc memory regions on different nodes 
2743        can be different. use +isomalloc_sync to calculate the
2744        intersect of all memory regions on all nodes.
2745     */
2746   if (_sync_iso == 1)
2747   {
2748         if (CmiMyRank() == 0 && freeRegion.len > 0u) {
2749           if (CmiBarrier() == -1 && CmiMyPe()==0) 
2750             CmiAbort("Charm++ Error> +isomalloc_sync requires CmiBarrier() implemented.\n");
2751           else {
2752             CmiUInt8 s = (CmiUInt8)freeRegion.start;
2753             CmiUInt8 e = (CmiUInt8)(freeRegion.start+freeRegion.len);
2754             int fd, i;
2755             char fname[128];
2756
2757             if (CmiMyNode()==0) printf("Charm++> synchronizing isomalloc memory region...\n");
2758
2759             sprintf(fname,".isomalloc.%d", CmiMyNode());
2760
2761               /* remove file before writing for safe */
2762             unlink(fname);
2763 #if CMK_HAS_SYNC && ! CMK_DISABLE_SYNC
2764             system("sync");
2765 #endif
2766
2767             CmiBarrier();
2768
2769               /* write region into file */
2770             while ((fd = open(fname, O_WRONLY|O_TRUNC|O_CREAT, 0644)) == -1) 
2771 #ifndef __MINGW_H
2772               CMK_CPV_IS_SMP
2773 #endif
2774             ;
2775             write(fd, &s, sizeof(CmiUInt8));
2776             write(fd, &e, sizeof(CmiUInt8));
2777             close(fd);
2778
2779 #if CMK_HAS_SYNC && ! CMK_DISABLE_SYNC
2780             system("sync");
2781 #endif
2782
2783             CmiBarrier();
2784
2785             for (i=0; i<CmiNumNodes(); i++) {
2786               CmiUInt8 ss, ee; 
2787               int try_count;
2788               char fname[128];
2789               if (i==CmiMyNode()) continue;
2790               sprintf(fname,".isomalloc.%d", i);
2791               try_count = 0;
2792               while ((fd = open(fname, O_RDONLY)) == -1 && try_count<10000)
2793               {
2794                 try_count++;
2795 #ifndef __MINGW_H
2796                 CMK_CPV_IS_SMP
2797 #endif
2798                 ;
2799               }
2800               if (fd == -1) {
2801                 CmiAbort("isomalloc_sync failed, make sure you have a shared file system.");
2802               }
2803               read(fd, &ss, sizeof(CmiUInt8));
2804               read(fd, &ee, sizeof(CmiUInt8));
2805 #if CMK_THREADS_DEBUG
2806               if (CmiMyPe() == 0) CmiPrintf("[%d] load node %d isomalloc region: %lx %lx. \n",
2807                                CmiMyPe(), i, ss, ee);
2808 #endif
2809               close(fd);
2810               if (ss>s) s = ss;
2811               if (ee<e) e = ee;
2812             }
2813
2814             CmiBarrier();
2815
2816             unlink(fname);
2817 #if CMK_HAS_SYNC && ! CMK_DISABLE_SYNC
2818             system("sync");
2819 #endif
2820
2821               /* update */
2822             if (s > e)  {
2823               if (CmiMyPe()==0) CmiPrintf("[%d] Invalid isomalloc region: %lx - %lx.\n", CmiMyPe(), s, e);
2824               CmiAbort("isomalloc> failed to find consolidated isomalloc region!");
2825             }
2826             freeRegion.start = (void *)s;
2827             freeRegion.len = (char *)e -(char *)s;
2828
2829             if (CmiMyPe() == 0)
2830             CmiPrintf("[%d] consolidated Isomalloc memory region: %p - %p (%d megs)\n",CmiMyPe(),
2831               freeRegion.start,freeRegion.start+freeRegion.len,
2832               freeRegion.len/meg);
2833           }   /* end of barrier test */
2834         } /* end of rank 0 */
2835         else {
2836           CmiBarrier();
2837           CmiBarrier();
2838           CmiBarrier();
2839           CmiBarrier();
2840         }
2841   }
2842
2843   if (CmiMyRank() == 0 && freeRegion.len > 0u)
2844   {
2845         /*Isomalloc covers entire unused region*/
2846         isomallocStart=freeRegion.start;
2847 #if USE_MAPREGION
2848         numslots=((freeRegion.len/regionSize)/CmiNumPes())*(regionSize/slotsize);
2849         freeRegion.len = numslots*CmiNumPes()*slotsize;
2850         isomallocEnd=freeRegion.start+ freeRegion.len;
2851 #else
2852         isomallocEnd=freeRegion.start+freeRegion.len;
2853         numslots=(freeRegion.len/slotsize)/CmiNumPes();
2854 #endif 
2855
2856 #if CMK_THREADS_DEBUG
2857         CmiPrintf("[%d] Can isomalloc up to %lu megs per pe\n",CmiMyPe(),
2858               ((memRange_t)numslots)*slotsize/meg);
2859 #endif
2860   }
2861
2862   /*SMP Mode: wait here for rank 0 to initialize numslots before calculating myss*/
2863   CmiNodeAllBarrier(); 
2864  
2865   CpvInitialize(slotset *, myss);
2866   CpvAccess(myss) = NULL;
2867  
2868   if (isomallocStart!=NULL) {
2869     CpvAccess(myss) = new_slotset(pe2slot(CmiMyPe()), numslots);
2870
2871 #if USE_MAPREGION
2872     CpvInitialize(maplist **, mapLists);
2873     CpvAccess(mapLists) = (maplist **)(malloc_reentrant(CmiNumPes()*sizeof(maplist *)));
2874     mapList = CpvAccess(mapLists);
2875     for(i=0; i < CmiNumPes(); i++)
2876         mapList[i] = NULL;
2877
2878     CpvInitialize(mapRegion *,mapRegions);
2879     CpvAccess(mapRegions) = (mapRegion *)(malloc_reentrant(sizeof(mapRegion)));
2880     mapregion = CpvAccess(mapRegions);
2881     mapregion->size = 32 * 1024;//good enough for 512 GB        
2882     mapregion->counter = (int **)(malloc_reentrant
2883                         (mapregion->size * sizeof(int*)));
2884     mapregion->marker = (CmiInt8 **)(malloc_reentrant
2885                         (mapregion->size * sizeof(CmiInt8*)));
2886     mapregion->count = 10;
2887     for(i = 0; i < mapregion->count; i++)       
2888     {
2889         mapregion->counter[i] = (int *)(malloc_reentrant
2890                                 (1024 * sizeof(int)));
2891         mapregion->marker[i] = (CmiInt8 *)(malloc_reentrant
2892                                 (1024 * sizeof(CmiInt8)));
2893         for(j = 0; j < 1024; j++)
2894         {
2895                 mapregion->counter[i][j] = 0;
2896                 mapregion->marker[i][j] = -1;
2897         }
2898     }
2899 #endif
2900   }
2901 }
2902
2903
2904 /************* Communication: for grabbing/freeing remote slots *********/
2905 typedef struct _slotmsg
2906 {
2907   char cmicore[CmiMsgHeaderSizeBytes];
2908   int pe; /*Source processor*/
2909   CmiInt8 slot; /*First requested slot*/
2910   CmiInt8 nslots; /*Number of requested slots*/
2911 } slotmsg;
2912
2913 static slotmsg *prepare_slotmsg(CmiInt8 slot,CmiInt8 nslots)
2914 {
2915         slotmsg *m=(slotmsg *)CmiAlloc(sizeof(slotmsg));
2916         m->pe=CmiMyPe();
2917         m->slot=slot;
2918         m->nslots=nslots;
2919         return m;
2920 }
2921
2922 static void grab_remote(slotmsg *msg)
2923 {
2924         grab_slots(CpvAccess(myss),msg->slot,msg->nslots);
2925         CmiFree(msg);
2926 }
2927
2928 static void free_remote(slotmsg *msg)
2929 {
2930         free_slots(CpvAccess(myss),msg->slot,msg->nslots);
2931         CmiFree(msg);
2932 }
2933 static int grab_remote_idx, free_remote_idx;
2934
2935 struct slotOP {
2936         /*Function pointer to perform local operation*/
2937         void (*local)(slotset *ss,CmiInt8 s,CmiInt8 n);
2938         /*Index to perform remote operation*/
2939         int remote;
2940 };
2941 typedef struct slotOP slotOP;
2942 static slotOP grabOP,freeOP;
2943
2944 static void init_comm(char **argv)
2945 {
2946         grab_remote_idx=CmiRegisterHandler((CmiHandler)grab_remote);
2947         free_remote_idx=CmiRegisterHandler((CmiHandler)free_remote);    
2948         grabOP.local=grab_slots;
2949         grabOP.remote=grab_remote_idx;
2950         freeOP.local=free_slots;
2951         freeOP.remote=free_remote_idx;  
2952 }
2953
2954 /*Apply the given operation to the given slots which
2955   lie on the given processor.*/
2956 static void one_slotOP(const slotOP *op,int pe,CmiInt8 s,CmiInt8 n)
2957 {
2958 /*Shrink range to only those covered by this processor*/
2959         /*First and last slot for this processor*/
2960         CmiInt8 p_s=pe2slot(pe), p_e=pe2slot(pe+1);
2961         CmiInt8 e=s+n;
2962         if (s<p_s) s=p_s;
2963         if (e>p_e) e=p_e;
2964         n=e-s;
2965
2966 /*Send off range*/
2967         if (pe==CmiMyPe()) 
2968                 op->local(CpvAccess(myss),s,n);
2969         else 
2970         {/*Remote request*/
2971                 slotmsg *m=prepare_slotmsg(s,n);
2972                 CmiSetHandler(m, freeOP.remote);
2973                 CmiSyncSendAndFree(pe,sizeof(slotmsg),m);
2974         }
2975 }
2976
2977 /*Apply the given operation to all slots in the range [s, s+n) 
2978 After a restart from checkpoint, a slotset can cross an 
2979 arbitrary set of processors.
2980 */
2981 static void all_slotOP(const slotOP *op,CmiInt8 s,CmiInt8 n)
2982 {
2983         int spe=slot2pe(s), epe=slot2pe(s+n-1);
2984         int pe;
2985         for (pe=spe; pe<=epe; pe++)
2986                 one_slotOP(op,pe,s,n);
2987 }
2988
2989 /************** External interface ***************/
2990 void *CmiIsomalloc(int size)
2991 {
2992         CmiInt8 s,n,i;
2993         CmiIsomallocBlock *blk;
2994         if (isomallocStart==NULL) return disabled_map(size);
2995         n=length2slots(size);
2996         /*Always satisfy mallocs with local slots:*/
2997         s=get_slots(CpvAccess(myss),n);
2998         if (s==-1) {
2999                 CmiError("Not enough address space left on processor %d to isomalloc %d bytes!\n",
3000                          CmiMyPe(),size);
3001                 CmiAbort("Out of virtual address space for isomalloc");
3002         }
3003         grab_slots(CpvAccess(myss),s,n);
3004         for (i=0; i<5; i++) {
3005           blk=map_slots(s,n);
3006           if (blk!=NULL) break;
3007 #if CMK_HAS_USLEEP
3008           if (errno == ENOMEM) { usleep(rand()%1000); continue; }
3009           else break;
3010 #endif
3011         }
3012         if (!blk) map_failed(s,n);
3013         blk->slot=s;
3014         blk->length=size;
3015         return block2pointer(blk);
3016 }
3017
3018 #define MALLOC_ALIGNMENT           (2*sizeof(size_t))
3019 #define MINSIZE                    (sizeof(CmiIsomallocBlock))
3020
3021 /** return an aligned isomalloc memory, the alignment occurs after the
3022  *  first 'reserved' bytes.  Total requested size is (size+reserved)
3023  */
3024 static void *_isomallocAlign(size_t align, size_t size, size_t reserved)
3025 {
3026         void *ptr;
3027         CmiIntPtr ptr2align;
3028         CmiInt8 s;
3029
3030         if (align < MINSIZE) align = MINSIZE;
3031         /* make sure alignment is power of 2 */
3032         if ((align & (align - 1)) != 0) {
3033           size_t a = MALLOC_ALIGNMENT * 2;
3034           while ((unsigned long)a < (unsigned long)align) a <<= 1;
3035           align = a;
3036         }
3037         s = size + reserved + align;
3038         ptr = CmiIsomalloc(s);
3039         ptr2align = (CmiIntPtr)ptr;
3040         ptr2align += reserved;
3041         if (ptr2align % align != 0) { /* misaligned */
3042           CmiIsomallocBlock *blk = pointer2block(ptr);  /* save block */
3043           CmiIsomallocBlock savedblk = *blk;
3044           ptr2align = (ptr2align + align - 1) & -((CmiInt8) align);
3045           ptr2align -= reserved;
3046           ptr = (void*)ptr2align;
3047           blk = pointer2block(ptr);      /* restore block */
3048           *blk = savedblk;
3049         }
3050         return ptr;
3051 }
3052
3053 void *CmiIsomallocAlign(size_t align, size_t size)
3054 {
3055   return _isomallocAlign(align, size, 0);
3056 }
3057
3058 int CmiIsomallocEnabled()
3059 {
3060   return (isomallocStart!=NULL);
3061 }
3062
3063 void CmiIsomallocPup(pup_er p,void **blockPtrPtr)
3064 {
3065         CmiIsomallocBlock *blk;
3066         CmiInt8 s,length;
3067         CmiInt8 n;
3068         if (isomallocStart==NULL) CmiAbort("isomalloc is disabled-- cannot use IsomallocPup");
3069
3070         if (!pup_isUnpacking(p)) 
3071         { /*We have an existing block-- unpack start slot & length*/
3072                 blk=pointer2block(*blockPtrPtr);
3073                 s=blk->slot;
3074                 length=blk->length;
3075         }
3076         
3077         pup_int8(p,&s);
3078         pup_int8(p,&length);
3079         n=length2slots(length);
3080         
3081         if (pup_isUnpacking(p)) 
3082         { /*Must allocate a new block in its old location*/
3083                 if (pup_isUserlevel(p) || pup_isRestarting(p))
3084                 {       /*Checkpoint: must grab old slots (even remote!)*/
3085                         all_slotOP(&grabOP,s,n);
3086                 }
3087                 blk=map_slots(s,n);
3088                 if (!blk) map_failed(s,n);
3089                 blk->slot=s;
3090                 blk->length=length;
3091                 *blockPtrPtr=block2pointer(blk);
3092         }
3093         
3094         /*Pup the allocated data*/
3095         pup_bytes(p,*blockPtrPtr,length);
3096         
3097         if (pup_isDeleting(p)) 
3098         { /*Unmap old slots, but do not mark as free*/
3099                 unmap_slots(s,n);
3100                 *blockPtrPtr=NULL; /*Zero out user's pointer*/
3101         }
3102 }
3103
3104 void CmiIsomallocFree(void *blockPtr)
3105 {
3106         if (isomallocStart==NULL) {
3107                 disabled_unmap(blockPtr);
3108         }
3109         else if (blockPtr!=NULL)
3110         {
3111                 CmiIsomallocBlock *blk=pointer2block(blockPtr);
3112                 CmiInt8 s=blk->slot; 
3113                 CmiInt8 n=length2slots(blk->length);
3114                 unmap_slots(s,n);
3115                 /*Mark used slots as free*/
3116                 all_slotOP(&freeOP,s,n);
3117         }
3118 }
3119
3120 CmiInt8   CmiIsomallocLength(void *block)
3121 {
3122         return pointer2block(block)->length;
3123 }
3124
3125 /*Return true if this address is in the region managed by isomalloc*/
3126 int CmiIsomallocInRange(void *addr)
3127 {
3128         if (isomallocStart==NULL) return 0; /* There is no range we manage! */
3129         return pointer_ge((char *)addr,isomallocStart) && 
3130                pointer_lt((char*)addr,isomallocEnd);
3131 }
3132
3133 void CmiIsomallocInit(char **argv)
3134 {
3135 #if CMK_NO_ISO_MALLOC
3136   disable_isomalloc("isomalloc disabled by conv-mach");
3137 #else
3138   if (CmiGetArgFlagDesc(argv,"+noisomalloc","disable isomalloc")) {
3139     disable_isomalloc("isomalloc disabled by user.");
3140     return;
3141   }
3142 #if CMK_MMAP_PROBE
3143   _mmap_probe = 1;
3144 #elif CMK_MMAP_TEST
3145   _mmap_probe = 0;
3146 #endif
3147   if (CmiGetArgFlagDesc(argv,"+isomalloc_probe","call mmap to probe the largest available isomalloc region"))
3148     _mmap_probe = 1;
3149   if (CmiGetArgFlagDesc(argv,"+isomalloc_test","mmap test common areas for the largest available isomalloc region"))
3150     _mmap_probe = 0;
3151   if (CmiGetArgFlagDesc(argv,"+isomalloc_sync","synchronize isomalloc region globaly"))
3152     _sync_iso = 1;
3153   init_comm(argv);
3154   if (!init_map(argv)) {
3155     disable_isomalloc("mmap() does not work");
3156   }
3157   else {
3158     if (CmiMyPe() == 0) {
3159       if (read_randomflag() == 1) {    /* randomization stack pointer */
3160         if (_sync_iso == 1)
3161           printf("Warning> Randomization of stack pointer is turned on in kernel.\n");
3162         else
3163           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");
3164       }
3165     }
3166     init_ranges(argv);
3167   }
3168 #endif
3169 }
3170
3171 /***************** BlockList interface *********
3172 This was moved here from memory-isomalloc.c when it 
3173 was realized that a list-of-isomalloc'd-blocks is useful for
3174 more than just isomalloc heaps.
3175 */
3176
3177 /*Convert a slot to a user address*/
3178 static char *Slot_toUser(CmiIsomallocBlockList *s) {return (char *)(s+1);}
3179 static CmiIsomallocBlockList *Slot_fmUser(void *s) {return ((CmiIsomallocBlockList *)s)-1;}
3180
3181
3182 /*Build a new blockList.*/
3183 CmiIsomallocBlockList *CmiIsomallocBlockListNew(void)
3184 {
3185         CmiIsomallocBlockList *ret;
3186         ret=(CmiIsomallocBlockList *)CmiIsomalloc(sizeof(*ret));
3187         ret->next=ret; /*1-entry circular linked list*/
3188         ret->prev=ret;
3189         return ret;
3190 }
3191
3192
3193 /* BIGSIM_OOC DEBUGGING */
3194 static void print_myslots();
3195
3196 /*Pup all the blocks in this list.  This amounts to two circular
3197 list traversals.  Because everything's isomalloc'd, we don't even
3198 have to restore the pointers-- they'll be restored automatically!
3199 */
3200 void CmiIsomallocBlockListPup(pup_er p,CmiIsomallocBlockList **lp)
3201 {
3202         /* BIGSIM_OOC DEBUGGING */
3203         /* if(!pup_isUnpacking(p)) print_myslots(); */
3204
3205         int i,nBlocks=0;
3206         CmiIsomallocBlockList *cur=NULL, *start=*lp;
3207 #if 0 /*#ifndef CMK_OPTIMIZE*/
3208         if (CpvAccess(isomalloc_blocklist)!=NULL)
3209                 CmiAbort("Called CmiIsomallocBlockListPup while a blockList is active!\n"
3210                         "You should swap out the active blocklist before pupping.\n");
3211 #endif
3212         /*Count the number of blocks in the list*/
3213         if (!pup_isUnpacking(p)) {
3214                 nBlocks=1; /*<- Since we have to skip the start block*/
3215                 for (cur=start->next; cur!=start; cur=cur->next) 
3216                         nBlocks++;
3217                 /*Prepare for next trip around list:*/
3218                 cur=start;
3219         }
3220         pup_int(p,&nBlocks);
3221         
3222         /*Pup each block in the list*/
3223         for (i=0;i<nBlocks;i++) {
3224                 void *newBlock=cur;
3225                 if (!pup_isUnpacking(p)) 
3226                 { /*While packing, we traverse the list to find our blocks*/
3227                         cur=cur->next;
3228                 }
3229                 CmiIsomallocPup(p,&newBlock);
3230                 if (i==0 && pup_isUnpacking(p))
3231                         *lp=(CmiIsomallocBlockList *)newBlock;
3232         }
3233         if (pup_isDeleting(p))
3234                 *lp=NULL;
3235
3236         /* BIGSIM_OOC DEBUGGING */
3237         /* if(pup_isUnpacking(p)) print_myslots(); */
3238 }
3239
3240 /*Delete all the blocks in this list.*/
3241 void CmiIsomallocBlockListDelete(CmiIsomallocBlockList *l)
3242 {
3243     CmiIsomallocBlockList *start=l;
3244     CmiIsomallocBlockList *cur=start;
3245         if (cur==NULL) return; /*Already deleted*/
3246         do {
3247           CmiIsomallocBlockList *doomed=cur;
3248                 cur=cur->next; /*Have to stash next before deleting cur*/
3249                 CmiIsomallocFree(doomed);
3250         } while (cur!=start);
3251 }
3252
3253 /*Allocate a block from this blockList*/
3254 void *CmiIsomallocBlockListMalloc(CmiIsomallocBlockList *l,size_t nBytes)
3255 {
3256     CmiIsomallocBlockList *n; /*Newly created slot*/
3257         n=(CmiIsomallocBlockList *)CmiIsomalloc(sizeof(CmiIsomallocBlockList)+nBytes);
3258         /*Link the new block into the circular blocklist*/
3259         n->prev=l;
3260         n->next=l->next;
3261         l->next->prev=n;
3262         l->next=n;
3263         return Slot_toUser(n);
3264 }
3265
3266 /*Allocate a block from this blockList with alighment */
3267 void *CmiIsomallocBlockListMallocAlign(CmiIsomallocBlockList *l,size_t align,size_t nBytes)
3268 {
3269     CmiIsomallocBlockList *n; /*Newly created slot*/
3270         n=(CmiIsomallocBlockList *)_isomallocAlign(align,nBytes,sizeof(CmiIsomallocBlockList));
3271         /*Link the new block into the circular blocklist*/
3272         n->prev=l;
3273         n->next=l->next;
3274         l->next->prev=n;
3275         l->next=n;
3276         return Slot_toUser(n);
3277 }
3278
3279 /*Remove this block from its list and memory*/
3280 void CmiIsomallocBlockListFree(void *block)
3281 {
3282     CmiIsomallocBlockList *n=Slot_fmUser(block);
3283 #if DOHEAPCHECK
3284         if (n->prev->next!=n || n->next->prev!=n) 
3285                 CmiAbort("Heap corruption detected in isomalloc block list header!\n"
3286                         "  Run with ++debug and look for writes to negative array indices");
3287 #endif
3288         /*Link ourselves out of the blocklist*/
3289         n->prev->next=n->next;
3290         n->next->prev=n->prev;
3291         CmiIsomallocFree(n);
3292 }
3293
3294
3295
3296 /* BIGSIM_OOC DEBUGGING */
3297 static void print_myslots(){
3298     CmiPrintf("[%d] my slot set=%p\n", CmiMyPe(), CpvAccess(myss));
3299     print_slots(CpvAccess(myss));
3300 }
3301
3302
3303