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