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