Merge branch 'charm' of charmgit:charm into charm
[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   CmiInt8 startRegion, endRegion;
1640   CmiInt8 left, tleft;
1641   maplist **mapList = CpvAccess(mapLists);
1642   CmiInt8 ratio = regionSize/slotsize;
1643
1644   startRegion = (slot/ratio);
1645   endRegion = (slot + nslots - 1)/ratio;
1646   int whichPE = slot/numslots;
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   CmiInt8 startSlot, endSlot;
1828   startSlot = pe2slot(CmiMyPe());
1829   endSlot = startSlot + numslots - 1;
1830   if((slot < startSlot) || (slot > endSlot))
1831         return ((CmiIsomallocBlock *)remoteSlotmap(slot,nslots)); 
1832
1833   mapRegion *mapregion = CpvAccess(mapRegions);
1834   startAddr = (CmiInt8)slot2addr(slot);
1835   addr = slot2addr(slot);
1836         
1837   ratio = regionSize/slotsize;
1838   actualSlot = slot - pe2slot(CmiMyPe());
1839   left = nslots;
1840
1841   start1off = actualSlot/(1024*ratio);
1842   start2off = (actualSlot - 1024*ratio*start1off)/ratio;
1843   currentR = (1024*start1off) + start2off;  
1844
1845   end1off = (actualSlot + nslots - 1)/(1024*ratio);
1846   end2off = (actualSlot + nslots - 1 - 1024*ratio*end1off)/ratio;
1847
1848   if(!(end1off < mapregion->count))
1849   {
1850         starti = mapregion->count;
1851         endi = end1off + 11;
1852         for(i = starti; i < endi; i++)
1853         {
1854                 mapregion->counter[i] = (int *)(malloc_reentrant
1855                                         (1024 * sizeof(int)));
1856                 mapregion->marker[i] = (CmiInt8 *)(malloc_reentrant
1857                                         (1024 * sizeof(CmiInt8)));
1858                 for(j = 0; j < 1024; j++)
1859                 {
1860                         mapregion->counter[i][j] = 0;
1861                         mapregion->marker[i][j] = -1;
1862                 }
1863         }       
1864         mapregion->count = endi;
1865   } 
1866
1867   temp = mapregion->marker[start1off][start2off];
1868  
1869   if(temp != -1)
1870   {
1871         if(temp >= currentR)
1872         {
1873                 begin = currentR;
1874         }       
1875         else
1876         {
1877                 begin = temp;
1878                 temp = mapregion->marker[begin/1024][begin - ((begin/1024)*1024)];
1879         }
1880         tleft = (((temp + 1)*ratio) - actualSlot);
1881         off1 = begin/1024;
1882         off2 = begin - (off1 * 1024);
1883         if(left <= tleft)
1884         {
1885                 mapregion->counter[off1][off2] += left ;        
1886                 return (CmiIsomallocBlock *)addr;
1887         }               
1888         else
1889         {
1890                 mapregion->counter[off1][off2] += tleft ;       
1891                 left -= tleft;
1892                 off1 = (temp+1)/1024;
1893                 off2 = (temp+1) - (off1 * 1024);
1894         }
1895   }                     
1896   else
1897   {
1898         off1 = start1off;
1899         off2 = start2off;
1900   }
1901
1902   extraleft = 0;
1903   if(mapregion->marker[start1off][start2off] == -1)
1904   {
1905         extraleft = actualSlot % ratio;
1906   }
1907  
1908   temp = mapregion->marker[end1off][end2off];
1909   currentR = (1024*end1off) + end2off;  
1910   
1911   if(temp != -1)
1912   {
1913         if(temp > currentR)
1914         {
1915                 temp = currentR;
1916         }       
1917         toff1 = temp/1024;
1918         toff2 = temp - (toff1*1024);
1919         tleft = (actualSlot + nslots) - (temp * ratio);
1920         mapregion->counter[toff1][toff2] += tleft;
1921         left -= tleft;
1922         end1off = (temp - 1)/1024;
1923         end2off = (temp - 1) - (end1off * 1024);
1924   }     
1925
1926   if((end1off < off1)||((end1off == off1)&&(end2off < off2)))
1927   {
1928         return (CmiIsomallocBlock *)addr;
1929   }
1930
1931   requestSize = ((left + extraleft + (ratio-1))/ratio)*regionSize;
1932   newaddr = (void*)((CmiInt8)slot2addr(pe2slot(CmiMyPe())));
1933   newaddr = (void*)((CmiInt8)newaddr + ((1024*off1 + off2)*regionSize));
1934   pa = call_mmap_fixed(newaddr, requestSize);
1935   if (pa != newaddr)
1936   { /*Map worked, but gave us back the wrong place*/
1937 #if CMK_THREADS_DEBUG
1938     //CmiPrintf("[%d] tried to mmap %p, but got %p back\n",CmiMyPe(),newaddr,pa);
1939 #endif
1940     call_munmap(newaddr,requestSize);
1941     return NULL;
1942   }
1943
1944   if (pa==NULL)
1945   { /*Map just failed completely*/
1946
1947 #if CMK_THREADS_DEBUG
1948     perror("mmap failed");
1949     //CmiPrintf("[%d] tried to mmap %p, but encountered error\n",CmiMyPe(),addr);
1950 #endif
1951     return NULL;
1952   }
1953 #if CMK_THREADS_DEBUG
1954   //CmiPrintf("[%d] mmap'd slots %ld-%ld to address %p\n",CmiMyPe(),
1955             slot,slot+nslots-1,addr);
1956 #endif
1957
1958   mapregion->counter[off1][off2] += left;
1959   mapregion->marker[off1][off2] = 1024*end1off + end2off;
1960
1961   temp = (1024 * off1) + off2;
1962
1963   starti = off2 + 1;
1964   if(off1 == end1off)
1965         endi = end2off + 1;
1966   else
1967         endi = 1024;
1968
1969   for(i = starti; i < endi; i++)
1970   {
1971         mapregion->marker[off1][i] = temp;
1972   }
1973  
1974   starti = off1 + 1;
1975   endi = end1off;
1976   for(i = starti; i < endi; i++)
1977   {
1978         for(j = 0; j < 1024; j++)       
1979                 mapregion->marker[i][j] = temp;
1980   }
1981
1982   starti = 0;
1983   if(off1 == end1off)
1984         endi = 0;
1985   else
1986         endi = end2off + 1;
1987
1988   for(i = starti; i < endi; i++)
1989   {
1990         mapregion->marker[end1off][i] = temp;
1991   }
1992
1993   return (CmiIsomallocBlock *)addr;
1994 }
1995
1996 #else
1997
1998 /**
1999  * maps the virtual memory associated with slot using mmap
2000  */
2001 static CmiIsomallocBlock *
2002 map_slots(CmiInt8 slot, CmiInt8 nslots)
2003 {
2004   void *pa;
2005   void *addr=slot2addr(slot);
2006   pa = call_mmap_fixed(addr, slotsize*nslots);
2007
2008   if (pa==NULL)
2009   { /*Map just failed completely*/
2010 #if CMK_THREADS_DEBUG
2011     perror("mmap failed");
2012     CmiPrintf("[%d] tried to mmap %p, but encountered error\n",CmiMyPe(),addr);
2013 #endif
2014     return NULL;
2015   }
2016   if (pa != addr)
2017   { /*Map worked, but gave us back the wrong place*/
2018 #if CMK_THREADS_DEBUG
2019     CmiPrintf("[%d] tried to mmap %p, but got %p back\n",CmiMyPe(),addr,pa);
2020 #endif
2021     call_munmap(addr,slotsize*nslots);
2022     return NULL;
2023   }
2024 #if CMK_THREADS_DEBUG
2025   CmiPrintf("[%d] mmap'd slots %ld-%ld to address %p\n",CmiMyPe(),
2026             slot,slot+nslots-1,addr);
2027 #endif
2028   return (CmiIsomallocBlock *)pa;
2029 }
2030 #endif //end of else of if USE_MAPREGION 
2031
2032 #if USE_MAPREGION
2033
2034 /* method to delete a node of in a linked list */
2035 static void
2036 freelistentry(maplist *target)
2037 {
2038         maplist *prev,*next;
2039         prev = target->prev;
2040         next = target->next;
2041         if(prev != NULL)
2042                 prev->next = next;
2043         if(next != NULL)
2044                 next->prev = prev;
2045         free_reentrant(target);
2046 }
2047
2048 /* method to free an entry for VM not in range of my processor */
2049 static void 
2050 remoteSlotunmap(CmiInt8 slot, CmiInt8 nslots)
2051 {
2052   void *addr = slot2addr(slot);
2053   void *pa,*newaddr;
2054   maplist *temp,*tofree;
2055
2056   CmiInt8 left, tleft;
2057   maplist **mapList = CpvAccess(mapLists);
2058   CmiInt8 ratio = regionSize/slotsize;
2059
2060   int whichPE = slot/numslots;
2061
2062   if(mapList[whichPE] == NULL)
2063   {
2064         return;
2065   }
2066
2067   temp = mapList[whichPE];
2068
2069   while(temp != NULL)
2070   {
2071         if(slot < temp->end)
2072                 break;
2073         temp = temp->next;
2074   }
2075   if(temp == NULL)
2076   {
2077         return;
2078   }
2079
2080   left = nslots;
2081
2082   tleft = temp->end - slot;
2083   if(tleft >= nslots)
2084   {
2085         temp->count -= nslots;
2086         left -= nslots;
2087   }
2088   else
2089   {
2090         temp->count -= tleft;
2091         left -= tleft;
2092   }
2093
2094   tofree = temp;
2095   temp = temp->next;
2096   if(tofree->count <= 0)
2097   {
2098         newaddr = (void *)(slot2addr(tofree->start));
2099         call_munmap(newaddr, (tofree->end - tofree->start)*slotsize);
2100         if(tofree == mapList[whichPE])
2101         {
2102                 mapList[whichPE] = tofree->next;
2103         }
2104         freelistentry(tofree);
2105   }
2106
2107   if((temp == NULL) || (left <= 0))
2108   {
2109         return;
2110   }
2111
2112   if((slot+nslots-1) < temp->end)
2113   {
2114         tleft = slot + nslots - temp->start;
2115   }
2116   else
2117   {
2118         tleft = temp->count;
2119   }
2120
2121   temp->count -= tleft;
2122   left -= tleft;
2123
2124   tofree = temp;
2125   temp = temp->next;
2126   if(tofree->count <= 0)
2127   {
2128         newaddr = (void *)(slot2addr(tofree->start));
2129         call_munmap(newaddr, (tofree->end - tofree->start)*slotsize);
2130         if(tofree == mapList[whichPE])
2131         {
2132                 mapList[whichPE] = tofree->next;
2133         }
2134         freelistentry(tofree);
2135   }
2136
2137   if((temp == NULL) || (left <= 0))
2138   {
2139       return;
2140   }
2141
2142   tleft = slot + nslots - temp->start;
2143   temp->count -= tleft;
2144   left -= tleft;
2145
2146   tofree = temp;
2147
2148   if(tofree->count <= 0)
2149   {
2150         newaddr = (void *)(slot2addr(tofree->start));
2151         call_munmap(newaddr, (tofree->end - tofree->start)*slotsize);
2152         if(tofree == mapList[whichPE])
2153         {
2154                 mapList[whichPE] = tofree->next;
2155         }
2156         freelistentry(tofree);
2157   }
2158 }
2159 #endif
2160
2161 #if USE_MAPREGION
2162
2163 /*
2164  * unmaps the virtual memory associated with slot using munmap and in the list
2165  */
2166 static void
2167 unmap_slots(CmiInt8 slot, CmiInt8 nslots)
2168 {
2169   void *addr=slot2addr(slot);
2170
2171   mapRegion *mapregion;
2172   CmiInt8 start1off, start2off, end1off, end2off;
2173   CmiInt8 off1, off2, requestSize;
2174   CmiInt8 actualSlot, temp, left, tleft;
2175   CmiInt8 i, starti, endi, j;
2176   CmiInt8 currentR, begin;
2177   int ratio;
2178
2179   CmiInt8 startSlot, endSlot;
2180   startSlot = pe2slot(CmiMyPe());
2181   endSlot = startSlot + numslots - 1;
2182   if((slot < startSlot) || (slot > endSlot))
2183   {
2184     remoteSlotunmap(slot,nslots); 
2185     return;
2186   }
2187
2188   mapregion = CpvAccess(mapRegions);
2189
2190   ratio = regionSize/slotsize;
2191   actualSlot = slot - pe2slot(CmiMyPe());
2192   left = nslots;
2193
2194   start1off = actualSlot/(1024*ratio);
2195   start2off = (actualSlot - (start1off*1024*ratio))/ratio;
2196   currentR = (1024*start1off + start2off);  
2197
2198   end1off = (actualSlot+nslots-1)/(1024*ratio);
2199   end2off = (actualSlot+nslots-1 - (end1off*1024*ratio))/ratio;
2200
2201   temp = mapregion->marker[start1off][start2off];
2202
2203   if(temp >= currentR)
2204   {
2205         begin = currentR;
2206   }
2207   else
2208   {
2209         begin = temp;
2210         temp = mapregion->marker[begin/1024][begin - ((begin/1024)*1024)]; 
2211   }
2212
2213   tleft = (ratio*(temp+1)) - actualSlot;
2214   off1 = begin/1024;
2215   off2 = begin - (off1*1024);
2216
2217   if(tleft >= nslots)
2218   {
2219         mapregion->counter[off1][off2] -= nslots;
2220         left -= nslots;
2221   }
2222   else
2223   {
2224         mapregion->counter[off1][off2] -= tleft;
2225         left -= tleft;
2226   }
2227
2228   if(mapregion->counter[off1][off2] == 0)
2229   {
2230         addr = (void*)((CmiInt8)slot2addr(pe2slot(CmiMyPe())));
2231         addr = (void*)((CmiInt8)addr + ((1024*off1 + off2)*regionSize));
2232         call_munmap(addr,(temp+1-begin)*regionSize);
2233         for(i = begin; i <= temp; i++)
2234         {
2235                 mapregion->marker[i/1024][i - ((i/1024)*1024)] = -1;
2236         }
2237   }
2238
2239  if(left <= 0)
2240         return;
2241
2242   starti = temp + 1;
2243
2244   currentR = (1024*end1off + end2off);
2245   temp = mapregion->marker[end1off][end2off];
2246
2247   if(temp >= currentR)
2248   {
2249         begin = currentR;
2250   }
2251   else
2252   {
2253         begin = temp;
2254         temp = mapregion->marker[begin/1024][begin - ((begin/1024)*1024)]; 
2255   }
2256
2257   tleft = (actualSlot+nslots) - (ratio*begin);
2258   off1 = begin/1024;
2259   off2 = begin - (off1*1024);
2260
2261   mapregion->counter[off1][off2] -= tleft;
2262   left -= tleft;
2263
2264   if(mapregion->counter[off1][off2] == 0)
2265   {
2266         addr = (void*)((CmiInt8)slot2addr(pe2slot(CmiMyPe())));
2267         addr = (void*)((CmiInt8)addr + ((1024*off1 + off2)*regionSize));
2268         call_munmap(addr,(temp+1-begin)*regionSize);
2269         for(i = begin; i <= temp; i++)
2270         {
2271                 mapregion->marker[i/1024][i - ((i/1024)*1024)] = -1;
2272         }
2273   }
2274
2275   if(left <= 0)
2276         return;
2277
2278   endi = begin;
2279
2280   begin = starti;
2281   off1 = begin/1024;
2282   off2 = begin - (1024*off1);
2283   temp = mapregion->marker[off1][off2];
2284   mapregion->counter[off1][off2] = 0;
2285   
2286   addr = (void*)((CmiInt8)slot2addr(pe2slot(CmiMyPe())));
2287   addr = (void*)((CmiInt8)addr + ((1024*off1 + off2)*regionSize));
2288   call_munmap(addr,(temp+1-begin)*regionSize);
2289
2290   for(i = starti; i < endi; i++)
2291   {
2292         mapregion->marker[i/1024][i - ((i/1024)*1024)] = -1;
2293   }     
2294
2295
2296 #if CMK_THREADS_DEBUG
2297   CmiPrintf("[%d] munmap'd slots %ld-%ld from address %p\n",CmiMyPe(),
2298             slot,slot+nslots-1,addr);
2299 #endif
2300 }
2301 #else
2302
2303 /*
2304  * unmaps the virtual memory associated with slot using munmap
2305  */
2306 static void
2307 unmap_slots(CmiInt8 slot, CmiInt8 nslots)
2308 {
2309   void *addr=slot2addr(slot);
2310   call_munmap(addr, slotsize*nslots);
2311 #if CMK_THREADS_DEBUG
2312   CmiPrintf("[%d] munmap'd slots %ld-%ld from address %p\n",CmiMyPe(),
2313             slot,slot+nslots-1,addr);
2314 #endif
2315 }
2316 #endif 
2317
2318 static void map_failed(CmiInt8 s,CmiInt8 n)
2319 {
2320   void *addr=slot2addr(s);
2321   CmiError("charm isomalloc.c> map failed to allocate %d bytes at %p, errno:%d.\n",
2322       slotsize*n, addr, errno);
2323   CmiAbort("Exiting\n");
2324 }
2325
2326
2327
2328 /************ Address space voodoo: find free address range **********/
2329
2330 CpvStaticDeclare(slotset *, myss); /*My managed slots*/
2331
2332 /*This struct describes a range of virtual addresses*/
2333 typedef struct {
2334   char *start; /*First byte of region*/
2335   memRange_t len; /*Number of bytes in region*/
2336   const char *type; /*String describing memory in region (debugging only)*/
2337 } memRegion_t;
2338
2339 /*Estimate the top of the current stack*/
2340 static void *__cur_stack_frame(void)
2341 {
2342   char __dummy;
2343   void *top_of_stack=(void *)&__dummy;
2344   return top_of_stack;
2345 }
2346 /*Estimate the location of the static data region*/
2347 static void *__static_data_loc(void)
2348 {
2349   static char __dummy;
2350   return (void *)&__dummy;
2351 }
2352
2353 /*Pointer comparison is in these subroutines, because
2354   comparing arbitrary pointers is nonportable and tricky.
2355 */
2356 static int pointer_lt(const char *a,const char *b) {
2357         return ((memRange_t)a)<((memRange_t)b);
2358 }
2359 static int pointer_ge(const char *a,const char *b) {
2360         return ((memRange_t)a)>=((memRange_t)b);
2361 }
2362
2363 static char *pmin(char *a,char *b) {return pointer_lt(a,b)?a:b;}
2364 static char *pmax(char *a,char *b) {return pointer_lt(a,b)?b:a;}
2365
2366 const static memRange_t meg=1024u*1024u; /*One megabyte*/
2367 const static memRange_t gig=1024u*1024u*1024u; /*One gigabyte*/
2368
2369 /*Check if this memory location is usable.  
2370   If not, return 1.
2371 */
2372 static int bad_location(char *loc) {
2373   void *addr;
2374   addr=call_mmap_fixed(loc,slotsize);
2375   if (addr==NULL || addr!=loc) {
2376 #if CMK_THREADS_DEBUG
2377     CmiPrintf("[%d] Skipping unmappable space at %p\n",CmiMyPe(),loc);
2378 #endif
2379     return 1; /*No good*/
2380   }
2381   call_munmap(addr,slotsize);
2382   return 0; /*This works*/
2383 }
2384
2385 /* Split this range up into n pieces, returning the size of each piece */
2386 static memRange_t divide_range(memRange_t len,int n) {
2387         return (len+1)/n;
2388 }
2389
2390 /* Return if this memory region has *any* good parts. */
2391 static int partially_good(char *start,memRange_t len,int n) {
2392   int i;
2393   memRange_t quant=divide_range(len,n);
2394   CmiAssert (quant > 0);
2395   for (i=0;i<n;i++)
2396     if (!bad_location(start+i*quant)) return 1; /* it's got some good parts */
2397   return 0; /* all locations are bad */
2398 }
2399
2400 /* Return if this memory region is usable at n samples.  
2401 */
2402 static int good_range(char *start,memRange_t len,int n) {
2403   int i;
2404   memRange_t quant=divide_range(len,n);
2405 #if CMK_THREADS_DEBUG
2406   CmiPrintf("good_range: %lld, %d\n", quant, n);
2407 #endif
2408   CmiAssert (quant > 0);
2409
2410   for (i=0;i<n;i++)
2411     if (bad_location(start+i*quant)) return 0; /* it's got some bad parts */
2412   /* It's all good: */
2413   return 1;
2414 }
2415
2416 /*Check if this entire memory range, or some subset 
2417   of the range, is usable.  If so, write it into max.
2418 */
2419 static void check_range(char *start,char *end,memRegion_t *max)
2420 {
2421   memRange_t len;
2422   CmiUInt8 tb = (CmiUInt8)gig*1024ul;   /* One terabyte */
2423   CmiUInt8 vm_limit = tb*256ul;   /* terabyte */
2424
2425   if (start>=end) return; /*Ran out of hole*/
2426   len=(memRange_t)end-(memRange_t)start;
2427   
2428 #if 0
2429     /* too conservative */
2430   if (len/gig>64u) { /* This is an absurd amount of space-- cut it down, for safety */
2431      start+=16u*gig;
2432      end=start+32u*gig;
2433      len=(memRange_t)end-(memRange_t)start;  
2434   }
2435 #else
2436   /* Note: 256TB == 248 bytes.  So a 48-bit virtual-address CPU 
2437    *    can only actually address 256TB of space. */
2438   if (len/tb>10u) { /* This is an absurd amount of space-- cut it down, for safety */
2439     const memRange_t other_libs=16ul*gig; /* space for other libraries to use */
2440     start+=other_libs;
2441     end=pmin(start+vm_limit-2*other_libs, end-other_libs);
2442     len=(memRange_t)end-(memRange_t)start;
2443   }
2444 #endif
2445   if (len<=max->len) return; /*It's too short already!*/
2446 #if CMK_THREADS_DEBUG
2447   CmiPrintf("[%d] Checking at %p - %p\n",CmiMyPe(),start,end);
2448 #endif
2449   
2450   /* Check the middle of the range */
2451   if (!good_range(start,len,256)) {
2452     /* Try to split into subranges: */
2453     int i,n=2;
2454 #if CMK_THREADS_DEBUG
2455     CmiPrintf("[%d] Trying to split bad address space at %p - %p...\n",CmiMyPe(),start,end);
2456 #endif
2457     len=divide_range(len,n);
2458     for (i=0;i<n;i++) {
2459         char *cur=start+i*len;
2460         if (partially_good(cur,len,16))
2461            check_range(cur,cur+len,max);
2462     }
2463     return; /* Hopefully one of the subranges will be any good */
2464   }
2465   else /* range is good */
2466   { 
2467 #if CMK_THREADS_DEBUG
2468     CmiPrintf("[%d] Address space at %p - %p is largest\n",CmiMyPe(),start,end);
2469 #endif
2470
2471     /*If we got here, we're the new largest usable range*/
2472     max->len=len;
2473     max->start=start;
2474     max->type="Unused";
2475   }
2476 }
2477
2478 /*Find the first available memory region of at least the
2479   given size not touching any data in the used list.
2480  */
2481 static memRegion_t find_free_region(memRegion_t *used,int nUsed,int atLeast) 
2482 {
2483   memRegion_t max;
2484   int i,j;  
2485
2486   max.start=0; 
2487   max.len=atLeast;
2488   /*Find the largest hole between regions*/
2489   for (i=0;i<nUsed;i++) {
2490     /*Consider a hole starting at the end of region i*/
2491     char *holeStart=used[i].start+used[i].len;
2492     char *holeEnd=(void *)(-1);
2493     
2494     /*Shrink the hole by all others*/ 
2495     for (j=0;j<nUsed && pointer_lt(holeStart,holeEnd);j++) {
2496       if (pointer_lt(used[j].start,holeStart)) 
2497         holeStart=pmax(holeStart,used[j].start+used[j].len);
2498       else if (pointer_lt(used[j].start,holeEnd)) 
2499         holeEnd=pmin(holeEnd,used[j].start);
2500     } 
2501
2502     check_range(holeStart,holeEnd,&max);
2503   }
2504
2505   return max; 
2506 }
2507
2508 /*
2509 By looking at the address range carefully, try to find 
2510 the largest usable free region on the machine.
2511 */
2512 static int find_largest_free_region(memRegion_t *destRegion) {
2513     char *staticData =(char *) __static_data_loc();
2514     char *code = (char *)&find_free_region;
2515     char *threadData = (char *)&errno;
2516     char *codeDll = (char *)fprintf;
2517     char *heapLil = (char*) malloc(1);
2518     char *heapBig = (char*) malloc(6*meg);
2519     char *stack = (char *)__cur_stack_frame();
2520     size_t mmapAnyLen = 1*meg;
2521     char *mmapAny = (char*) call_mmap_anywhere(mmapAnyLen);
2522
2523     int i,nRegions=0;
2524     memRegion_t regions[10]; /*used portions of address space*/
2525     memRegion_t freeRegion; /*Largest unused block of address space*/
2526
2527 /*Mark off regions of virtual address space as ususable*/
2528     regions[nRegions].type="NULL";
2529     regions[nRegions].start=NULL; 
2530 #if CMK_POWER7 && CMK_64BIT
2531     regions[nRegions++].len=2u*gig;   /* on bluedrop, don't mess with the lower memory region */
2532 #else
2533     regions[nRegions++].len=16u*meg;
2534 #endif
2535             
2536     regions[nRegions].type="Static program data";
2537     regions[nRegions].start=staticData; regions[nRegions++].len=256u*meg;
2538
2539     regions[nRegions].type="Program executable code";
2540     regions[nRegions].start=code; regions[nRegions++].len=256u*meg;
2541
2542     regions[nRegions].type="Heap (small blocks)";
2543     regions[nRegions].start=heapLil; regions[nRegions++].len=1u*gig;
2544
2545     regions[nRegions].type="Heap (large blocks)";
2546     regions[nRegions].start=heapBig; regions[nRegions++].len=1u*gig;
2547
2548     regions[nRegions].type="Stack space";
2549     regions[nRegions].start=stack; regions[nRegions++].len=256u*meg;
2550
2551     regions[nRegions].type="Program dynamically linked code";
2552     regions[nRegions].start=codeDll; regions[nRegions++].len=256u*meg; 
2553
2554     regions[nRegions].type="Result of a non-fixed call to mmap";
2555     regions[nRegions].start=mmapAny; regions[nRegions++].len=2u*gig; 
2556
2557     regions[nRegions].type="Thread private data";
2558     regions[nRegions].start=threadData; regions[nRegions++].len=256u*meg; 
2559
2560     _MEMCHECK(heapBig); free(heapBig);
2561     _MEMCHECK(heapLil); free(heapLil); 
2562     call_munmap(mmapAny,mmapAnyLen);
2563     
2564     /*Align each memory region*/
2565     for (i=0;i<nRegions;i++) {
2566       memRegion_t old=regions[i];
2567       memRange_t p=(memRange_t)regions[i].start;
2568       p&=~(regions[i].len-1); /*Round start down to a len-boundary (mask off low bits)*/
2569       regions[i].start=(char *)p;
2570 #if CMK_MACOSX
2571       if (regions[i].start+regions[i].len*2>regions[i].start) regions[i].len *= 2;
2572 #endif
2573 #if CMK_THREADS_DEBUG
2574       CmiPrintf("[%d] Memory map: %p - %p (len: %lu => %lu) %s \n",CmiMyPe(),
2575               regions[i].start,regions[i].start+regions[i].len,
2576               old.len, regions[i].len, regions[i].type);
2577 #endif
2578     }
2579     
2580     /*Find a large, unused region in this map: */
2581     freeRegion=find_free_region(regions,nRegions,(512u)*meg);
2582     
2583     if (freeRegion.start==0) 
2584     { /*No free address space-- disable isomalloc:*/
2585       return 0;
2586     }
2587     else /* freeRegion is valid */
2588     {
2589       *destRegion=freeRegion;
2590       
2591       return 1;
2592     }
2593 }
2594
2595 static int try_largest_mmap_region(memRegion_t *destRegion)
2596 {
2597   void *bad_alloc=(void*)(-1); /* mmap error return address */
2598   void *range, *good_range=NULL;
2599   double shrink = 1.5;
2600   static int count = 0;
2601   size_t size=((size_t)(-1l)), good_size=0;
2602   int retry = 0;
2603   if (sizeof(size_t) >= 8) size = size>>2;  /* 25% of machine address space! */
2604   while (1) { /* test out an allocation of this size */
2605 #if CMK_HAS_MMAP
2606         range=mmap(NULL,size,PROT_READ|PROT_WRITE,
2607                      MAP_PRIVATE
2608 #if CMK_HAS_MMAP_ANON
2609                      |MAP_ANON
2610 #endif
2611 #if CMK_HAS_MMAP_NORESERVE
2612                      |MAP_NORESERVE
2613 #endif
2614                      ,-1,0);
2615 #else
2616         range = bad_alloc;
2617 #endif
2618         if (range == bad_alloc) {  /* mmap failed */
2619 #if CMK_THREADS_DEBUG
2620                 /* CmiPrintf("[%d] test failed at size: %llu error: %d\n", CmiMyPe(), size, errno);  */
2621 #endif
2622 #if CMK_HAS_USLEEP
2623                 if (retry++ < 5) { usleep(rand()%10000); continue; }
2624                 else retry = 0;
2625 #endif
2626                 size=(double)size/shrink; /* shrink request */
2627                 if (size<=0) return 0; /* mmap doesn't work */
2628         }
2629         else { /* this allocation size is available */
2630 #if CMK_THREADS_DEBUG
2631                CmiPrintf("[%d] available: %p, %lld\n", CmiMyPe(), range, size);
2632 #endif
2633                call_munmap(range,size); /* needed/wanted? */
2634                 if (size > good_size) {
2635                   good_range = range;
2636                   good_size = size;
2637                   size=((double)size)*1.1;
2638                   continue;
2639                 }
2640                 break;
2641         }
2642   }
2643   CmiAssert(good_range!=NULL);
2644   destRegion->start=good_range; 
2645   destRegion->len=good_size;
2646 #if CMK_THREADS_DEBUG
2647 pid_t pid = getpid();
2648 {
2649 char s[128];
2650 sprintf(s, "cat /proc/%d/maps", pid);
2651 system(s);
2652 }
2653   CmiPrintf("[%d] try_largest_mmap_region: %p, %lld\n", CmiMyPe(), good_range, good_size);
2654 #endif
2655   return 1;
2656 }
2657
2658 #ifndef CMK_CPV_IS_SMP
2659 #define CMK_CPV_IS_SMP
2660 #endif
2661
2662 static void init_ranges(char **argv)
2663 {
2664   memRegion_t freeRegion;
2665   /*Largest value a signed int can hold*/
2666   memRange_t intMax=(((memRange_t)1)<<(sizeof(int)*8-1))-1;
2667   int pagesize = 0;
2668
2669
2670 #if USE_MAPREGION
2671   /*Round regionSize size up to nearest page size*/
2672   slotsize = 128;
2673   regionSize=16*1024;
2674
2675 #if CMK_HAS_GETPAGESIZE
2676   pagesize = getpagesize();
2677 #endif
2678   if (pagesize < CMK_MEMORY_PAGESIZE)
2679     pagesize = CMK_MEMORY_PAGESIZE;
2680   regionSize=(regionSize+pagesize-1) & ~(pagesize-1);
2681 #else
2682   /*Round slot size up to nearest page size*/
2683   slotsize=16*1024;
2684 #if CMK_HAS_GETPAGESIZE
2685   pagesize = getpagesize();
2686 #endif
2687   if (pagesize < CMK_MEMORY_PAGESIZE)
2688     pagesize = CMK_MEMORY_PAGESIZE;
2689   slotsize=(slotsize+pagesize-1) & ~(pagesize-1);
2690 #endif
2691
2692 #if CMK_THREADS_DEBUG
2693   if (CmiMyPe() == 0)
2694   CmiPrintf("[%d] Using slotsize of %d\n", CmiMyPe(), slotsize);
2695 #endif
2696   freeRegion.len=0u;
2697
2698   if (CmiMyRank()==0 && numslots==0)
2699   { /* Find the largest unused region of virtual address space */
2700 #ifdef CMK_MMAP_START_ADDRESS /* Hardcoded start address, for machines where automatic fails */
2701       freeRegion.start=CMK_MMAP_START_ADDRESS;
2702       freeRegion.len=CMK_MMAP_LENGTH_MEGS*meg;
2703 #endif
2704       
2705       if (freeRegion.len==0u)  {
2706         if (_mmap_probe == 1) {
2707           if (try_largest_mmap_region(&freeRegion)) _sync_iso = 1;
2708         }
2709         else {
2710           if (freeRegion.len==0u) find_largest_free_region(&freeRegion);
2711         }
2712       }
2713
2714 #if 0
2715       /*Make sure our largest slot number doesn't overflow an int:*/
2716       if (freeRegion.len/slotsize>intMax)
2717         freeRegion.len=intMax*slotsize;
2718 #endif
2719       
2720       if (freeRegion.len==0u) {
2721         disable_isomalloc("no free virtual address space");
2722       }
2723       else /* freeRegion.len>0, so can isomalloc */
2724       {
2725 #if CMK_THREADS_DEBUG
2726         CmiPrintf("[%d] Isomalloc memory region: %p - %p (%d megs)\n",CmiMyPe(),
2727               freeRegion.start,freeRegion.start+freeRegion.len,
2728               freeRegion.len/meg);
2729 #endif
2730       }
2731   }             /* end if myrank == 0 */
2732
2733   CmiNodeAllBarrier();
2734
2735     /*
2736        on some machines, isomalloc memory regions on different nodes 
2737        can be different. use +isomalloc_sync to calculate the
2738        intersect of all memory regions on all nodes.
2739     */
2740   if (_sync_iso == 1)
2741   {
2742         if (CmiMyRank() == 0 && freeRegion.len > 0u) {
2743           if (CmiBarrier() == -1 && CmiMyPe()==0) 
2744             CmiAbort("Charm++ Error> +isomalloc_sync requires CmiBarrier() implemented.\n");
2745           else {
2746             CmiUInt8 s = (CmiUInt8)freeRegion.start;
2747             CmiUInt8 e = (CmiUInt8)(freeRegion.start+freeRegion.len);
2748             int fd, i;
2749             char fname[128];
2750
2751             if (CmiMyNode()==0) printf("Charm++> synchronizing isomalloc memory region...\n");
2752
2753             sprintf(fname,".isomalloc.%d", CmiMyNode());
2754
2755               /* remove file before writing for safe */
2756             unlink(fname);
2757 #if CMK_HAS_SYNC && ! CMK_DISABLE_SYNC
2758             system("sync");
2759 #endif
2760
2761             CmiBarrier();
2762
2763               /* write region into file */
2764             while ((fd = open(fname, O_WRONLY|O_TRUNC|O_CREAT, 0644)) == -1) 
2765 #ifndef __MINGW_H
2766               CMK_CPV_IS_SMP
2767 #endif
2768             ;
2769             write(fd, &s, sizeof(CmiUInt8));
2770             write(fd, &e, sizeof(CmiUInt8));
2771             close(fd);
2772
2773 #if CMK_HAS_SYNC && ! CMK_DISABLE_SYNC
2774             system("sync");
2775 #endif
2776
2777             CmiBarrier();
2778
2779             for (i=0; i<CmiNumNodes(); i++) {
2780               CmiUInt8 ss, ee; 
2781               int try_count;
2782               char fname[128];
2783               if (i==CmiMyNode()) continue;
2784               sprintf(fname,".isomalloc.%d", i);
2785               try_count = 0;
2786               while ((fd = open(fname, O_RDONLY)) == -1 && try_count<10000)
2787               {
2788                 try_count++;
2789 #ifndef __MINGW_H
2790                 CMK_CPV_IS_SMP
2791 #endif
2792                 ;
2793               }
2794               if (fd == -1) {
2795                 CmiAbort("isomalloc_sync failed, make sure you have a shared file system.");
2796               }
2797               read(fd, &ss, sizeof(CmiUInt8));
2798               read(fd, &ee, sizeof(CmiUInt8));
2799 #if CMK_THREADS_DEBUG
2800               if (CmiMyPe() == 0) CmiPrintf("[%d] load node %d isomalloc region: %lx %lx. \n",
2801                                CmiMyPe(), i, ss, ee);
2802 #endif
2803               close(fd);
2804               if (ss>s) s = ss;
2805               if (ee<e) e = ee;
2806             }
2807
2808             CmiBarrier();
2809
2810             unlink(fname);
2811 #if CMK_HAS_SYNC && ! CMK_DISABLE_SYNC
2812             system("sync");
2813 #endif
2814
2815               /* update */
2816             if (s > e)  {
2817               if (CmiMyPe()==0) CmiPrintf("[%d] Invalid isomalloc region: %lx - %lx.\n", CmiMyPe(), s, e);
2818               CmiAbort("isomalloc> failed to find consolidated isomalloc region!");
2819             }
2820             freeRegion.start = (void *)s;
2821             freeRegion.len = (char *)e -(char *)s;
2822
2823             if (CmiMyPe() == 0)
2824             CmiPrintf("[%d] consolidated Isomalloc memory region: %p - %p (%d megs)\n",CmiMyPe(),
2825               freeRegion.start,freeRegion.start+freeRegion.len,
2826               freeRegion.len/meg);
2827           }   /* end of barrier test */
2828         } /* end of rank 0 */
2829         else {
2830           CmiBarrier();
2831           CmiBarrier();
2832           CmiBarrier();
2833           CmiBarrier();
2834         }
2835   }
2836
2837   if (CmiMyRank() == 0 && freeRegion.len > 0u)
2838   {
2839         /*Isomalloc covers entire unused region*/
2840         isomallocStart=freeRegion.start;
2841 #if USE_MAPREGION
2842         numslots=((freeRegion.len/regionSize)/CmiNumPes())*(regionSize/slotsize);
2843         freeRegion.len = numslots*CmiNumPes()*slotsize;
2844         isomallocEnd=freeRegion.start+ freeRegion.len;
2845 #else
2846         isomallocEnd=freeRegion.start+freeRegion.len;
2847         numslots=(freeRegion.len/slotsize)/CmiNumPes();
2848 #endif 
2849
2850 #if CMK_THREADS_DEBUG
2851         CmiPrintf("[%d] Can isomalloc up to %lu megs per pe\n",CmiMyPe(),
2852               ((memRange_t)numslots)*slotsize/meg);
2853 #endif
2854   }
2855
2856   /*SMP Mode: wait here for rank 0 to initialize numslots before calculating myss*/
2857   CmiNodeAllBarrier(); 
2858  
2859   CpvInitialize(slotset *, myss);
2860   CpvAccess(myss) = NULL;
2861  
2862   if (isomallocStart!=NULL) {
2863     CpvAccess(myss) = new_slotset(pe2slot(CmiMyPe()), numslots);
2864
2865 #if USE_MAPREGION
2866     CmiInt8 i,j;
2867     CpvInitialize(maplist **, mapLists);
2868     CpvAccess(mapLists) = (maplist **)(malloc_reentrant(CmiNumPes()*sizeof(maplist *)));
2869     maplist **mapList = CpvAccess(mapLists);
2870     for(i=0; i < CmiNumPes(); i++)
2871         mapList[i] = NULL;
2872
2873     CpvInitialize(mapRegion *,mapRegions);
2874     CpvAccess(mapRegions) = (mapRegion *)(malloc_reentrant(sizeof(mapRegion)));
2875     mapRegion *mapregion = CpvAccess(mapRegions);
2876     mapregion->size = 32 * 1024;//good enough for 512 GB        
2877     mapregion->counter = (int **)(malloc_reentrant
2878                         (mapregion->size * sizeof(int*)));
2879     mapregion->marker = (CmiInt8 **)(malloc_reentrant
2880                         (mapregion->size * sizeof(CmiInt8*)));
2881     mapregion->count = 10;
2882     for(i = 0; i < mapregion->count; i++)       
2883     {
2884         mapregion->counter[i] = (int *)(malloc_reentrant
2885                                 (1024 * sizeof(int)));
2886         mapregion->marker[i] = (CmiInt8 *)(malloc_reentrant
2887                                 (1024 * sizeof(CmiInt8)));
2888         for(j = 0; j < 1024; j++)
2889         {
2890                 mapregion->counter[i][j] = 0;
2891                 mapregion->marker[i][j] = -1;
2892         }
2893     }
2894 #endif
2895   }
2896 }
2897
2898
2899 /************* Communication: for grabbing/freeing remote slots *********/
2900 typedef struct _slotmsg
2901 {
2902   char cmicore[CmiMsgHeaderSizeBytes];
2903   int pe; /*Source processor*/
2904   CmiInt8 slot; /*First requested slot*/
2905   CmiInt8 nslots; /*Number of requested slots*/
2906 } slotmsg;
2907
2908 static slotmsg *prepare_slotmsg(CmiInt8 slot,CmiInt8 nslots)
2909 {
2910         slotmsg *m=(slotmsg *)CmiAlloc(sizeof(slotmsg));
2911         m->pe=CmiMyPe();
2912         m->slot=slot;
2913         m->nslots=nslots;
2914         return m;
2915 }
2916
2917 static void grab_remote(slotmsg *msg)
2918 {
2919         grab_slots(CpvAccess(myss),msg->slot,msg->nslots);
2920         CmiFree(msg);
2921 }
2922
2923 static void free_remote(slotmsg *msg)
2924 {
2925         free_slots(CpvAccess(myss),msg->slot,msg->nslots);
2926         CmiFree(msg);
2927 }
2928 static int grab_remote_idx, free_remote_idx;
2929
2930 struct slotOP {
2931         /*Function pointer to perform local operation*/
2932         void (*local)(slotset *ss,CmiInt8 s,CmiInt8 n);
2933         /*Index to perform remote operation*/
2934         int remote;
2935 };
2936 typedef struct slotOP slotOP;
2937 static slotOP grabOP,freeOP;
2938
2939 static void init_comm(char **argv)
2940 {
2941         grab_remote_idx=CmiRegisterHandler((CmiHandler)grab_remote);
2942         free_remote_idx=CmiRegisterHandler((CmiHandler)free_remote);    
2943         grabOP.local=grab_slots;
2944         grabOP.remote=grab_remote_idx;
2945         freeOP.local=free_slots;
2946         freeOP.remote=free_remote_idx;  
2947 }
2948
2949 /*Apply the given operation to the given slots which
2950   lie on the given processor.*/
2951 static void one_slotOP(const slotOP *op,int pe,CmiInt8 s,CmiInt8 n)
2952 {
2953 /*Shrink range to only those covered by this processor*/
2954         /*First and last slot for this processor*/
2955         CmiInt8 p_s=pe2slot(pe), p_e=pe2slot(pe+1);
2956         CmiInt8 e=s+n;
2957         if (s<p_s) s=p_s;
2958         if (e>p_e) e=p_e;
2959         n=e-s;
2960
2961 /*Send off range*/
2962         if (pe==CmiMyPe()) 
2963                 op->local(CpvAccess(myss),s,n);
2964         else 
2965         {/*Remote request*/
2966                 slotmsg *m=prepare_slotmsg(s,n);
2967                 CmiSetHandler(m, freeOP.remote);
2968                 CmiSyncSendAndFree(pe,sizeof(slotmsg),m);
2969         }
2970 }
2971
2972 /*Apply the given operation to all slots in the range [s, s+n) 
2973 After a restart from checkpoint, a slotset can cross an 
2974 arbitrary set of processors.
2975 */
2976 static void all_slotOP(const slotOP *op,CmiInt8 s,CmiInt8 n)
2977 {
2978         int spe=slot2pe(s), epe=slot2pe(s+n-1);
2979         int pe;
2980         for (pe=spe; pe<=epe; pe++)
2981                 one_slotOP(op,pe,s,n);
2982 }
2983
2984 /************** External interface ***************/
2985 void *CmiIsomalloc(int size)
2986 {
2987         CmiInt8 s,n,i;
2988         CmiIsomallocBlock *blk;
2989         if (isomallocStart==NULL) return disabled_map(size);
2990         n=length2slots(size);
2991         /*Always satisfy mallocs with local slots:*/
2992         s=get_slots(CpvAccess(myss),n);
2993         if (s==-1) {
2994                 CmiError("Not enough address space left on processor %d to isomalloc %d bytes!\n",
2995                          CmiMyPe(),size);
2996                 CmiAbort("Out of virtual address space for isomalloc");
2997         }
2998         grab_slots(CpvAccess(myss),s,n);
2999         for (i=0; i<5; i++) {
3000           blk=map_slots(s,n);
3001           if (blk!=NULL) break;
3002 #if CMK_HAS_USLEEP
3003           if (errno == ENOMEM) { usleep(rand()%1000); continue; }
3004           else break;
3005 #endif
3006         }
3007         if (!blk) map_failed(s,n);
3008         blk->slot=s;
3009         blk->length=size;
3010         return block2pointer(blk);
3011 }
3012
3013 #define MALLOC_ALIGNMENT           (2*sizeof(size_t))
3014 #define MINSIZE                    (sizeof(CmiIsomallocBlock))
3015
3016 /** return an aligned isomalloc memory, the alignment occurs after the
3017  *  first 'reserved' bytes.  Total requested size is (size+reserved)
3018  */
3019 static void *_isomallocAlign(size_t align, size_t size, size_t reserved)
3020 {
3021         void *ptr;
3022         CmiIntPtr ptr2align;
3023         CmiInt8 s;
3024
3025         if (align < MINSIZE) align = MINSIZE;
3026         /* make sure alignment is power of 2 */
3027         if ((align & (align - 1)) != 0) {
3028           size_t a = MALLOC_ALIGNMENT * 2;
3029           while ((unsigned long)a < (unsigned long)align) a <<= 1;
3030           align = a;
3031         }
3032         s = size + reserved + align;
3033         ptr = CmiIsomalloc(s);
3034         ptr2align = (CmiIntPtr)ptr;
3035         ptr2align += reserved;
3036         if (ptr2align % align != 0) { /* misaligned */
3037           CmiIsomallocBlock *blk = pointer2block(ptr);  /* save block */
3038           CmiIsomallocBlock savedblk = *blk;
3039           ptr2align = (ptr2align + align - 1) & -((CmiInt8) align);
3040           ptr2align -= reserved;
3041           ptr = (void*)ptr2align;
3042           blk = pointer2block(ptr);      /* restore block */
3043           *blk = savedblk;
3044         }
3045         return ptr;
3046 }
3047
3048 void *CmiIsomallocAlign(size_t align, size_t size)
3049 {
3050   return _isomallocAlign(align, size, 0);
3051 }
3052
3053 int CmiIsomallocEnabled()
3054 {
3055   return (isomallocStart!=NULL);
3056 }
3057
3058 void CmiIsomallocPup(pup_er p,void **blockPtrPtr)
3059 {
3060         CmiIsomallocBlock *blk;
3061         CmiInt8 s,length;
3062         CmiInt8 n;
3063         if (isomallocStart==NULL) CmiAbort("isomalloc is disabled-- cannot use IsomallocPup");
3064
3065         if (!pup_isUnpacking(p)) 
3066         { /*We have an existing block-- unpack start slot & length*/
3067                 blk=pointer2block(*blockPtrPtr);
3068                 s=blk->slot;
3069                 length=blk->length;
3070         }
3071         
3072         pup_int8(p,&s);
3073         pup_int8(p,&length);
3074         n=length2slots(length);
3075         
3076         if (pup_isUnpacking(p)) 
3077         { /*Must allocate a new block in its old location*/
3078                 if (pup_isUserlevel(p) || pup_isRestarting(p))
3079                 {       /*Checkpoint: must grab old slots (even remote!)*/
3080                         all_slotOP(&grabOP,s,n);
3081                 }
3082                 blk=map_slots(s,n);
3083                 if (!blk) map_failed(s,n);
3084                 blk->slot=s;
3085                 blk->length=length;
3086                 *blockPtrPtr=block2pointer(blk);
3087         }
3088         
3089         /*Pup the allocated data*/
3090         pup_bytes(p,*blockPtrPtr,length);
3091         
3092         if (pup_isDeleting(p)) 
3093         { /*Unmap old slots, but do not mark as free*/
3094                 unmap_slots(s,n);
3095                 *blockPtrPtr=NULL; /*Zero out user's pointer*/
3096         }
3097 }
3098
3099 void CmiIsomallocFree(void *blockPtr)
3100 {
3101         if (isomallocStart==NULL) {
3102                 disabled_unmap(blockPtr);
3103         }
3104         else if (blockPtr!=NULL)
3105         {
3106                 CmiIsomallocBlock *blk=pointer2block(blockPtr);
3107                 CmiInt8 s=blk->slot; 
3108                 CmiInt8 n=length2slots(blk->length);
3109                 unmap_slots(s,n);
3110                 /*Mark used slots as free*/
3111                 all_slotOP(&freeOP,s,n);
3112         }
3113 }
3114
3115 CmiInt8   CmiIsomallocLength(void *block)
3116 {
3117         return pointer2block(block)->length;
3118 }
3119
3120 /*Return true if this address is in the region managed by isomalloc*/
3121 int CmiIsomallocInRange(void *addr)
3122 {
3123         if (isomallocStart==NULL) return 0; /* There is no range we manage! */
3124         return pointer_ge((char *)addr,isomallocStart) && 
3125                pointer_lt((char*)addr,isomallocEnd);
3126 }
3127
3128 void CmiIsomallocInit(char **argv)
3129 {
3130 #if CMK_NO_ISO_MALLOC
3131   disable_isomalloc("isomalloc disabled by conv-mach");
3132 #else
3133   if (CmiGetArgFlagDesc(argv,"+noisomalloc","disable isomalloc")) {
3134     disable_isomalloc("isomalloc disabled by user.");
3135     return;
3136   }
3137 #if CMK_MMAP_PROBE
3138   _mmap_probe = 1;
3139 #elif CMK_MMAP_TEST
3140   _mmap_probe = 0;
3141 #endif
3142   if (CmiGetArgFlagDesc(argv,"+isomalloc_probe","call mmap to probe the largest available isomalloc region"))
3143     _mmap_probe = 1;
3144   if (CmiGetArgFlagDesc(argv,"+isomalloc_test","mmap test common areas for the largest available isomalloc region"))
3145     _mmap_probe = 0;
3146   if (CmiGetArgFlagDesc(argv,"+isomalloc_sync","synchronize isomalloc region globaly"))
3147     _sync_iso = 1;
3148   init_comm(argv);
3149   if (!init_map(argv)) {
3150     disable_isomalloc("mmap() does not work");
3151   }
3152   else {
3153     if (CmiMyPe() == 0) {
3154       if (read_randomflag() == 1) {    /* randomization stack pointer */
3155         if (_sync_iso == 1)
3156           printf("Warning> Randomization of stack pointer is turned on in kernel.\n");
3157         else
3158           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");
3159       }
3160     }
3161     init_ranges(argv);
3162   }
3163 #endif
3164 }
3165
3166 /***************** BlockList interface *********
3167 This was moved here from memory-isomalloc.c when it 
3168 was realized that a list-of-isomalloc'd-blocks is useful for
3169 more than just isomalloc heaps.
3170 */
3171
3172 /*Convert a slot to a user address*/
3173 static char *Slot_toUser(CmiIsomallocBlockList *s) {return (char *)(s+1);}
3174 static CmiIsomallocBlockList *Slot_fmUser(void *s) {return ((CmiIsomallocBlockList *)s)-1;}
3175
3176
3177 /*Build a new blockList.*/
3178 CmiIsomallocBlockList *CmiIsomallocBlockListNew(void)
3179 {
3180         CmiIsomallocBlockList *ret;
3181         ret=(CmiIsomallocBlockList *)CmiIsomalloc(sizeof(*ret));
3182         ret->next=ret; /*1-entry circular linked list*/
3183         ret->prev=ret;
3184         return ret;
3185 }
3186
3187
3188 /* BIGSIM_OOC DEBUGGING */
3189 static void print_myslots();
3190
3191 /*Pup all the blocks in this list.  This amounts to two circular
3192 list traversals.  Because everything's isomalloc'd, we don't even
3193 have to restore the pointers-- they'll be restored automatically!
3194 */
3195 void CmiIsomallocBlockListPup(pup_er p,CmiIsomallocBlockList **lp)
3196 {
3197         /* BIGSIM_OOC DEBUGGING */
3198         /* if(!pup_isUnpacking(p)) print_myslots(); */
3199
3200         int i,nBlocks=0;
3201         CmiIsomallocBlockList *cur=NULL, *start=*lp;
3202 #if 0 /*#ifndef CMK_OPTIMIZE*/
3203         if (CpvAccess(isomalloc_blocklist)!=NULL)
3204                 CmiAbort("Called CmiIsomallocBlockListPup while a blockList is active!\n"
3205                         "You should swap out the active blocklist before pupping.\n");
3206 #endif
3207         /*Count the number of blocks in the list*/
3208         if (!pup_isUnpacking(p)) {
3209                 nBlocks=1; /*<- Since we have to skip the start block*/
3210                 for (cur=start->next; cur!=start; cur=cur->next) 
3211                         nBlocks++;
3212                 /*Prepare for next trip around list:*/
3213                 cur=start;
3214         }
3215         pup_int(p,&nBlocks);
3216         
3217         /*Pup each block in the list*/
3218         for (i=0;i<nBlocks;i++) {
3219                 void *newBlock=cur;
3220                 if (!pup_isUnpacking(p)) 
3221                 { /*While packing, we traverse the list to find our blocks*/
3222                         cur=cur->next;
3223                 }
3224                 CmiIsomallocPup(p,&newBlock);
3225                 if (i==0 && pup_isUnpacking(p))
3226                         *lp=(CmiIsomallocBlockList *)newBlock;
3227         }
3228         if (pup_isDeleting(p))
3229                 *lp=NULL;
3230
3231         /* BIGSIM_OOC DEBUGGING */
3232         /* if(pup_isUnpacking(p)) print_myslots(); */
3233 }
3234
3235 /*Delete all the blocks in this list.*/
3236 void CmiIsomallocBlockListDelete(CmiIsomallocBlockList *l)
3237 {
3238     CmiIsomallocBlockList *start=l;
3239     CmiIsomallocBlockList *cur=start;
3240         if (cur==NULL) return; /*Already deleted*/
3241         do {
3242           CmiIsomallocBlockList *doomed=cur;
3243                 cur=cur->next; /*Have to stash next before deleting cur*/
3244                 CmiIsomallocFree(doomed);
3245         } while (cur!=start);
3246 }
3247
3248 /*Allocate a block from this blockList*/
3249 void *CmiIsomallocBlockListMalloc(CmiIsomallocBlockList *l,size_t nBytes)
3250 {
3251     CmiIsomallocBlockList *n; /*Newly created slot*/
3252         n=(CmiIsomallocBlockList *)CmiIsomalloc(sizeof(CmiIsomallocBlockList)+nBytes);
3253         /*Link the new block into the circular blocklist*/
3254         n->prev=l;
3255         n->next=l->next;
3256         l->next->prev=n;
3257         l->next=n;
3258         return Slot_toUser(n);
3259 }
3260
3261 /*Allocate a block from this blockList with alighment */
3262 void *CmiIsomallocBlockListMallocAlign(CmiIsomallocBlockList *l,size_t align,size_t nBytes)
3263 {
3264     CmiIsomallocBlockList *n; /*Newly created slot*/
3265         n=(CmiIsomallocBlockList *)_isomallocAlign(align,nBytes,sizeof(CmiIsomallocBlockList));
3266         /*Link the new block into the circular blocklist*/
3267         n->prev=l;
3268         n->next=l->next;
3269         l->next->prev=n;
3270         l->next=n;
3271         return Slot_toUser(n);
3272 }
3273
3274 /*Remove this block from its list and memory*/
3275 void CmiIsomallocBlockListFree(void *block)
3276 {
3277     CmiIsomallocBlockList *n=Slot_fmUser(block);
3278 #if DOHEAPCHECK
3279         if (n->prev->next!=n || n->next->prev!=n) 
3280                 CmiAbort("Heap corruption detected in isomalloc block list header!\n"
3281                         "  Run with ++debug and look for writes to negative array indices");
3282 #endif
3283         /*Link ourselves out of the blocklist*/
3284         n->prev->next=n->next;
3285         n->next->prev=n->prev;
3286         CmiIsomallocFree(n);
3287 }
3288
3289
3290
3291 /* BIGSIM_OOC DEBUGGING */
3292 static void print_myslots(){
3293     CmiPrintf("[%d] my slot set=%p\n", CmiMyPe(), CpvAccess(myss));
3294     print_slots(CpvAccess(myss));
3295 }
3296
3297
3298