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