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