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