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