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