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