added two command line options:
[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_THREADS_DEBUG 0
31
32 /* 0: use the old isomalloc implementation (array)
33    1: use the new isomalloc implementation (b-tree)  */
34 #define USE_BTREE_ISOMALLOC 1
35
36 /* b-tree definitions */
37 #define TREE_NODE_SIZE 128 /* a power of 2 is probably best  */
38 #define TREE_NODE_MID  63  /* must be cieling(TREE_NODE_SIZE / 2) - 1  */
39
40 /* linked list definitions  */
41 #define LIST_ARRAY_SIZE 64
42
43 #include <fcntl.h>
44 #include <stdio.h>
45 #include <stdlib.h>
46 #include <errno.h> /* just so I can find dynamically-linked symbols */
47 #include <unistd.h>
48
49 #if CMK_HAS_ADDR_NO_RANDOMIZE
50 #include <sys/personality.h>
51 #endif
52
53 static int _sync_iso = 0;
54 static int _mmap_probe = 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 #if CMK_THREADS_DEBUG
1702   CmiPrintf("good_range: %lld, %d\n", quant, n);
1703 #endif
1704   CmiAssert (quant > 0);
1705   for (i=0;i<n;i++)
1706     if (bad_location(start+i*quant)) return 0; /* it's got some bad parts */
1707   /* It's all good: */
1708   return 1;
1709 }
1710
1711 /*Check if this entire memory range, or some subset 
1712   of the range, is usable.  If so, write it into max.
1713 */
1714 static void check_range(char *start,char *end,memRegion_t *max)
1715 {
1716   memRange_t len;
1717   CmiUInt8 tb = (CmiUInt8)gig*1024ul;   /* One terabyte */
1718   CmiUInt8 vm_limit = tb*256ul;   /* terabyte */
1719
1720   if (start>=end) return; /*Ran out of hole*/
1721   len=(memRange_t)end-(memRange_t)start;
1722   
1723 #if 0
1724     /* too conservative */
1725   if (len/gig>64u) { /* This is an absurd amount of space-- cut it down, for safety */
1726      start+=16u*gig;
1727      end=start+32u*gig;
1728      len=(memRange_t)end-(memRange_t)start;  
1729   }
1730 #else
1731   /* Note: 256TB == 248 bytes.  So a 48-bit virtual-address CPU 
1732    *    can only actually address 256TB of space. */
1733   if (len/tb>10u) { /* This is an absurd amount of space-- cut it down, for safety */
1734     const memRange_t other_libs=16ul*gig; /* space for other libraries to use */
1735     start+=other_libs;
1736     end=pmin(start+vm_limit-2*other_libs, end-other_libs);
1737     len=(memRange_t)end-(memRange_t)start;
1738   }
1739 #endif
1740   if (len<=max->len) return; /*It's too short already!*/
1741 #if CMK_THREADS_DEBUG
1742   CmiPrintf("[%d] Checking at %p - %p\n",CmiMyPe(),start,end);
1743 #endif
1744   
1745   /* Check the middle of the range */
1746   if (!good_range(start,len,256)) {
1747     /* Try to split into subranges: */
1748     int i,n=2;
1749 #if CMK_THREADS_DEBUG
1750     CmiPrintf("[%d] Trying to split bad address space at %p - %p...\n",CmiMyPe(),start,end);
1751 #endif
1752     len=divide_range(len,n);
1753     for (i=0;i<n;i++) {
1754         char *cur=start+i*len;
1755         if (partially_good(cur,len,16))
1756            check_range(cur,cur+len,max);
1757     }
1758     return; /* Hopefully one of the subranges will be any good */
1759   }
1760   else /* range is good */
1761   { 
1762 #if CMK_THREADS_DEBUG
1763     CmiPrintf("[%d] Address space at %p - %p is largest\n",CmiMyPe(),start,end);
1764 #endif
1765
1766     /*If we got here, we're the new largest usable range*/
1767     max->len=len;
1768     max->start=start;
1769     max->type="Unused";
1770   }
1771 }
1772
1773 /*Find the first available memory region of at least the
1774   given size not touching any data in the used list.
1775  */
1776 static memRegion_t find_free_region(memRegion_t *used,int nUsed,int atLeast) 
1777 {
1778   memRegion_t max;
1779   int i,j;  
1780
1781   max.start=0; 
1782   max.len=atLeast;
1783   /*Find the largest hole between regions*/
1784   for (i=0;i<nUsed;i++) {
1785     /*Consider a hole starting at the end of region i*/
1786     char *holeStart=used[i].start+used[i].len;
1787     char *holeEnd=(void *)(-1);
1788     
1789     /*Shrink the hole by all others*/ 
1790     for (j=0;j<nUsed && pointer_lt(holeStart,holeEnd);j++) {
1791       if (pointer_lt(used[j].start,holeStart)) 
1792         holeStart=pmax(holeStart,used[j].start+used[j].len);
1793       else if (pointer_lt(used[j].start,holeEnd)) 
1794         holeEnd=pmin(holeEnd,used[j].start);
1795     } 
1796
1797     check_range(holeStart,holeEnd,&max);
1798   }
1799
1800   return max; 
1801 }
1802
1803 /*
1804 By looking at the address range carefully, try to find 
1805 the largest usable free region on the machine.
1806 */
1807 static int find_largest_free_region(memRegion_t *destRegion) {
1808     char *staticData =(char *) __static_data_loc();
1809     char *code = (char *)&find_free_region;
1810     char *threadData = (char *)&errno;
1811     char *codeDll = (char *)fprintf;
1812     char *heapLil = (char*) malloc(1);
1813     char *heapBig = (char*) malloc(6*meg);
1814     char *stack = (char *)__cur_stack_frame();
1815     size_t mmapAnyLen = 1*meg;
1816     char *mmapAny = (char*) call_mmap_anywhere(mmapAnyLen);
1817
1818     int i,nRegions=0;
1819     memRegion_t regions[10]; /*used portions of address space*/
1820     memRegion_t freeRegion; /*Largest unused block of address space*/
1821
1822     /* printf("%p %p %p %p %p %p %p %p \n", staticData, code, threadData, codeDll, heapLil, heapBig, stack, mmapAny); */
1823
1824 /*Mark off regions of virtual address space as ususable*/
1825     regions[nRegions].type="NULL";
1826     regions[nRegions].start=NULL; 
1827 #if CMK_POWER7 && CMK_64BIT
1828     regions[nRegions++].len=2u*gig;   /* on bluedrop, don't mess with the lower memory region */
1829 #else
1830     regions[nRegions++].len=16u*meg;
1831 #endif
1832     
1833     regions[nRegions].type="Static program data";
1834     regions[nRegions].start=staticData; regions[nRegions++].len=256u*meg;
1835     
1836     regions[nRegions].type="Program executable code";
1837     regions[nRegions].start=code; regions[nRegions++].len=256u*meg;
1838     
1839     regions[nRegions].type="Heap (small blocks)";
1840     regions[nRegions].start=heapLil; regions[nRegions++].len=1u*gig;
1841     
1842     regions[nRegions].type="Heap (large blocks)";
1843     regions[nRegions].start=heapBig; regions[nRegions++].len=1u*gig;
1844     
1845     regions[nRegions].type="Stack space";
1846     regions[nRegions].start=stack; regions[nRegions++].len=256u*meg;
1847
1848     regions[nRegions].type="Program dynamically linked code";
1849     regions[nRegions].start=codeDll; regions[nRegions++].len=256u*meg; 
1850
1851     regions[nRegions].type="Result of a non-fixed call to mmap";
1852     regions[nRegions].start=mmapAny; regions[nRegions++].len=2u*gig; 
1853
1854     regions[nRegions].type="Thread private data";
1855     regions[nRegions].start=threadData; regions[nRegions++].len=256u*meg; 
1856
1857     _MEMCHECK(heapBig); free(heapBig);
1858     _MEMCHECK(heapLil); free(heapLil); 
1859     call_munmap(mmapAny,mmapAnyLen);
1860     
1861     /*Align each memory region*/
1862     for (i=0;i<nRegions;i++) {
1863       memRegion_t old=regions[i];
1864       memRange_t p=(memRange_t)regions[i].start;
1865       p&=~(regions[i].len-1); /*Round start down to a len-boundary (mask off low bits)*/
1866       regions[i].start=(char *)p;
1867 #if CMK_MACOSX
1868       if (regions[i].start+regions[i].len*2>regions[i].start) regions[i].len *= 2;
1869 #endif
1870 #if CMK_THREADS_DEBUG
1871       CmiPrintf("[%d] Memory map: %p - %p (len: %lu => %lu) %s \n",CmiMyPe(),
1872               regions[i].start,regions[i].start+regions[i].len,
1873               old.len, regions[i].len, regions[i].type);
1874 #endif
1875     }
1876     
1877     /*Find a large, unused region in this map: */
1878     freeRegion=find_free_region(regions,nRegions,(512u)*meg);
1879     
1880     if (freeRegion.start==0) 
1881     { /*No free address space-- disable isomalloc:*/
1882       return 0;
1883     }
1884     else /* freeRegion is valid */
1885     {
1886       *destRegion=freeRegion;
1887       
1888       return 1;
1889     }
1890 }
1891
1892 /* probe method */
1893 static int try_largest_mmap_region(memRegion_t *destRegion)
1894 {
1895   void *bad_alloc=(void*)(-1); /* mmap error return address */
1896   void *range, *good_range=NULL;
1897   double shrink = 1.5;
1898   static int count = 0;
1899   size_t size=((size_t)(-1l)), good_size=0;
1900   int retry = 0;
1901   if (sizeof(size_t) >= 8) size = size>>2;  /* 25% of machine address space! */
1902   while (1) { /* test out an allocation of this size */
1903         range=mmap(NULL,size,PROT_READ|PROT_WRITE,
1904                      MAP_PRIVATE
1905 #if CMK_HAS_MMAP_ANON
1906                      |MAP_ANON
1907 #endif
1908 #if CMK_HAS_MMAP_NORESERVE
1909                      |MAP_NORESERVE
1910 #endif
1911                      ,-1,0);
1912         if (range==bad_alloc) { /* mmap failed */
1913 #if CMK_THREADS_DEBUG
1914                 /* CmiPrintf("[%d] test failed at size: %llu error: %d\n", CmiMyPe(), size, errno);  */
1915 #endif
1916                 if (retry++ < 5) { usleep(rand()%10000); continue; }
1917                 else retry = 0;
1918                 size=(double)size/shrink; /* shrink request */
1919                 if (size<=0) return 0; /* mmap doesn't work */
1920         }
1921         else { /* this allocation size is available */
1922 #if CMK_THREADS_DEBUG
1923                CmiPrintf("[%d] available: %p, %lld\n", CmiMyPe(), range, size);
1924 #endif
1925                 munmap(range,size); /* needed/wanted? */
1926                 if (size > good_size) {
1927                   good_range = range;
1928                   good_size = size;
1929                   size=((double)size)*1.1;
1930                   continue;
1931                 }
1932                 break;
1933         }
1934   }
1935   CmiAssert(good_range!=NULL);
1936   destRegion->start=good_range; 
1937   destRegion->len=good_size;
1938 #if CMK_THREADS_DEBUG
1939 pid_t pid = getpid();
1940 {
1941 char s[128];
1942 sprintf(s, "cat /proc/%d/maps", pid);
1943 system(s);
1944 }
1945   CmiPrintf("[%d] try_largest_mmap_region: %p, %lld\n", CmiMyPe(), good_range, good_size);
1946 #endif
1947   return 1;
1948 }
1949
1950 #ifndef CMK_CPV_IS_SMP
1951 #define CMK_CPV_IS_SMP
1952 #endif
1953
1954 static void init_ranges(char **argv)
1955 {
1956   memRegion_t freeRegion;
1957   /*Largest value a signed int can hold*/
1958   memRange_t intMax=(((memRange_t)1)<<(sizeof(int)*8-1))-1;
1959   int pagesize = 0;
1960
1961   /*Round slot size up to nearest page size*/
1962   slotsize=16*1024;
1963 #if CMK_HAS_GETPAGESIZE
1964   pagesize = getpagesize();
1965 #endif
1966   if (pagesize < CMK_MEMORY_PAGESIZE)
1967     pagesize = CMK_MEMORY_PAGESIZE;
1968   slotsize=(slotsize+pagesize-1) & ~(pagesize-1);
1969 #if CMK_THREADS_DEBUG
1970   if (CmiMyPe() == 0)
1971   CmiPrintf("[%d] Using slotsize of %d\n", CmiMyPe(), slotsize);
1972 #endif
1973
1974   freeRegion.len=0u;
1975
1976   if (CmiMyRank()==0 && numslots==0)
1977   { /* Find the largest unused region of virtual address space */
1978 #ifdef CMK_MMAP_START_ADDRESS /* Hardcoded start address, for machines where automatic fails */
1979       freeRegion.start=CMK_MMAP_START_ADDRESS;
1980       freeRegion.len=CMK_MMAP_LENGTH_MEGS*meg;
1981 #endif
1982
1983       if (freeRegion.len==0u)  {
1984         if (_mmap_probe == 1) {
1985           if (try_largest_mmap_region(&freeRegion)) _sync_iso = 1;
1986         }
1987         else {
1988           if (freeRegion.len==0u) find_largest_free_region(&freeRegion);
1989         }
1990       }
1991       
1992 #if 0
1993       /*Make sure our largest slot number doesn't overflow an int:*/
1994       if (freeRegion.len/slotsize>intMax)
1995         freeRegion.len=intMax*slotsize;
1996 #endif
1997       
1998       if (freeRegion.len==0u) {
1999         disable_isomalloc("no free virtual address space");
2000       }
2001       else /* freeRegion.len>0, so can isomalloc */
2002       {
2003 #if CMK_THREADS_DEBUG
2004         CmiPrintf("[%d] Isomalloc memory region: %p - %p (%d megs)\n",CmiMyPe(),
2005               freeRegion.start,freeRegion.start+freeRegion.len,
2006               freeRegion.len/meg);
2007 #endif
2008       }
2009   }             /* end if myrank == 0 */
2010
2011   CmiNodeAllBarrier();
2012
2013     /*
2014        on some machines, isomalloc memory regions on different nodes 
2015        can be different. use +isomalloc_sync to calculate the
2016        intersect of all memory regions on all nodes.
2017     */
2018   if (_sync_iso == 1)
2019   {
2020         if (CmiMyRank() == 0 && freeRegion.len > 0u) {
2021           if (CmiBarrier() == -1 && CmiMyPe()==0) 
2022             CmiAbort("Charm++ Error> +isomalloc_sync requires CmiBarrier() implemented.\n");
2023           else {
2024             CmiUInt8 s = (CmiUInt8)freeRegion.start;
2025             CmiUInt8 e = (CmiUInt8)(freeRegion.start+freeRegion.len);
2026             int fd, i;
2027             char fname[128];
2028
2029             if (CmiMyNode()==0) printf("Charm++> synchronizing isomalloc memory region...\n");
2030
2031             sprintf(fname,"/tmp/.isomalloc.%d.%d", getpid(), CmiMyNode());
2032
2033               /* remove file before writing for safe */
2034             unlink(fname);
2035 #if CMK_HAS_SYNC && ! CMK_DISABLE_SYNC
2036             system("sync");
2037 #endif
2038
2039             CmiBarrier();
2040
2041               /* write region into file */
2042             while ((fd = open(fname, O_WRONLY|O_TRUNC|O_CREAT, 0644)) == -1) 
2043 #ifndef __MINGW_H
2044               CMK_CPV_IS_SMP
2045 #endif
2046             ;
2047             write(fd, &s, sizeof(CmiUInt8));
2048             write(fd, &e, sizeof(CmiUInt8));
2049             close(fd);
2050
2051 #if CMK_HAS_SYNC && ! CMK_DISABLE_SYNC
2052             system("sync");
2053 #endif
2054
2055             CmiBarrier();
2056
2057             for (i=0; i<CmiNumNodes(); i++) {
2058               CmiUInt8 ss, ee; 
2059               int try_count;
2060               char fname[128];
2061               if (i==CmiMyNode()) continue;
2062               sprintf(fname,".isomalloc.%d", i);
2063               try_count = 0;
2064               while ((fd = open(fname, O_RDONLY)) == -1 && try_count<10000)
2065               {
2066                 try_count++;
2067 #ifndef __MINGW_H
2068                 CMK_CPV_IS_SMP
2069 #endif
2070                 ;
2071               }
2072               if (fd == -1) {
2073                 CmiAbort("isomalloc_sync failed, make sure you have a shared file system.");
2074               }
2075               read(fd, &ss, sizeof(CmiUInt8));
2076               read(fd, &ee, sizeof(CmiUInt8));
2077 #if CMK_THREADS_DEBUG
2078               if (CmiMyPe() == 0) CmiPrintf("[%d] load node %d isomalloc region: %lx %lx. \n",
2079                                CmiMyPe(), i, ss, ee);
2080 #endif
2081               close(fd);
2082               if (ss>s) s = ss;
2083               if (ee<e) e = ee;
2084             }
2085
2086             CmiBarrier();
2087
2088             unlink(fname);
2089 #if CMK_HAS_SYNC && ! CMK_DISABLE_SYNC
2090             system("sync");
2091 #endif
2092
2093               /* update */
2094             if (s > e)  {
2095               if (CmiMyPe()==0) CmiPrintf("[%d] Invalid isomalloc region: %lx - %lx.\n", CmiMyPe(), s, e);
2096               CmiAbort("isomalloc> failed to find consolidated isomalloc region!");
2097             }
2098             freeRegion.start = (void *)s;
2099             freeRegion.len = (char *)e -(char *)s;
2100
2101             if (CmiMyPe() == 0)
2102             CmiPrintf("[%d] consolidated Isomalloc memory region: %p - %p (%d megs)\n",CmiMyPe(),
2103               freeRegion.start,freeRegion.start+freeRegion.len,
2104               freeRegion.len/meg);
2105           }   /* end of barrier test */
2106         } /* end of rank 0 */
2107         else {
2108           CmiBarrier();
2109           CmiBarrier();
2110           CmiBarrier();
2111           CmiBarrier();
2112         }
2113   }
2114
2115   if (CmiMyRank() == 0 && freeRegion.len > 0u)
2116   {
2117         /*Isomalloc covers entire unused region*/
2118         isomallocStart=freeRegion.start;
2119         isomallocEnd=freeRegion.start+freeRegion.len;
2120         numslots=(freeRegion.len/slotsize)/CmiNumPes();
2121         
2122 #if CMK_THREADS_DEBUG
2123         CmiPrintf("[%d] Can isomalloc up to %lu megs per pe\n",CmiMyPe(),
2124               ((memRange_t)numslots)*slotsize/meg);
2125 #endif
2126   }
2127
2128   /*SMP Mode: wait here for rank 0 to initialize numslots before calculating myss*/
2129   CmiNodeAllBarrier(); 
2130   
2131   CpvInitialize(slotset *, myss);
2132   CpvAccess(myss) = NULL;
2133   if (isomallocStart!=NULL) {
2134     CpvAccess(myss) = new_slotset(pe2slot(CmiMyPe()), numslots);
2135   }
2136 }
2137
2138
2139 /************* Communication: for grabbing/freeing remote slots *********/
2140 typedef struct _slotmsg
2141 {
2142   char cmicore[CmiMsgHeaderSizeBytes];
2143   int pe; /*Source processor*/
2144   CmiInt8 slot; /*First requested slot*/
2145   CmiInt8 nslots; /*Number of requested slots*/
2146 } slotmsg;
2147
2148 static slotmsg *prepare_slotmsg(CmiInt8 slot,CmiInt8 nslots)
2149 {
2150         slotmsg *m=(slotmsg *)CmiAlloc(sizeof(slotmsg));
2151         m->pe=CmiMyPe();
2152         m->slot=slot;
2153         m->nslots=nslots;
2154         return m;
2155 }
2156
2157 static void grab_remote(slotmsg *msg)
2158 {
2159         grab_slots(CpvAccess(myss),msg->slot,msg->nslots);
2160         CmiFree(msg);
2161 }
2162
2163 static void free_remote(slotmsg *msg)
2164 {
2165         free_slots(CpvAccess(myss),msg->slot,msg->nslots);
2166         CmiFree(msg);
2167 }
2168 static int grab_remote_idx, free_remote_idx;
2169
2170 struct slotOP {
2171         /*Function pointer to perform local operation*/
2172         void (*local)(slotset *ss,CmiInt8 s,CmiInt8 n);
2173         /*Index to perform remote operation*/
2174         int remote;
2175 };
2176 typedef struct slotOP slotOP;
2177 static slotOP grabOP,freeOP;
2178
2179 static void init_comm(char **argv)
2180 {
2181         grab_remote_idx=CmiRegisterHandler((CmiHandler)grab_remote);
2182         free_remote_idx=CmiRegisterHandler((CmiHandler)free_remote);    
2183         grabOP.local=grab_slots;
2184         grabOP.remote=grab_remote_idx;
2185         freeOP.local=free_slots;
2186         freeOP.remote=free_remote_idx;  
2187 }
2188
2189 /*Apply the given operation to the given slots which
2190   lie on the given processor.*/
2191 static void one_slotOP(const slotOP *op,int pe,CmiInt8 s,CmiInt8 n)
2192 {
2193 /*Shrink range to only those covered by this processor*/
2194         /*First and last slot for this processor*/
2195         CmiInt8 p_s=pe2slot(pe), p_e=pe2slot(pe+1);
2196         CmiInt8 e=s+n;
2197         if (s<p_s) s=p_s;
2198         if (e>p_e) e=p_e;
2199         n=e-s;
2200
2201 /*Send off range*/
2202         if (pe==CmiMyPe()) 
2203                 op->local(CpvAccess(myss),s,n);
2204         else 
2205         {/*Remote request*/
2206                 slotmsg *m=prepare_slotmsg(s,n);
2207                 CmiSetHandler(m, freeOP.remote);
2208                 CmiSyncSendAndFree(pe,sizeof(slotmsg),m);
2209         }
2210 }
2211
2212 /*Apply the given operation to all slots in the range [s, s+n) 
2213 After a restart from checkpoint, a slotset can cross an 
2214 arbitrary set of processors.
2215 */
2216 static void all_slotOP(const slotOP *op,CmiInt8 s,CmiInt8 n)
2217 {
2218         int spe=slot2pe(s), epe=slot2pe(s+n-1);
2219         int pe;
2220         for (pe=spe; pe<=epe; pe++)
2221                 one_slotOP(op,pe,s,n);
2222 }
2223
2224 /************** External interface ***************/
2225 void *CmiIsomalloc(int size)
2226 {
2227         CmiInt8 s,n,i;
2228         CmiIsomallocBlock *blk;
2229         if (isomallocStart==NULL) return disabled_map(size);
2230         n=length2slots(size);
2231         /*Always satisfy mallocs with local slots:*/
2232         s=get_slots(CpvAccess(myss),n);
2233         if (s==-1) {
2234                 CmiError("Not enough address space left on processor %d to isomalloc %d bytes!\n",
2235                          CmiMyPe(),size);
2236                 CmiAbort("Out of virtual address space for isomalloc");
2237         }
2238         grab_slots(CpvAccess(myss),s,n);
2239         for (i=0; i<5; i++) {
2240           blk=map_slots(s,n);
2241           if (blk!=NULL) break;
2242 #if CMK_HAS_USLEEP
2243           if (errno == ENOMEM) { usleep(rand()%1000); continue; }
2244           else break;
2245 #endif
2246         }
2247         if (!blk) map_failed(s,n);
2248         blk->slot=s;
2249         blk->length=size;
2250         return block2pointer(blk);
2251 }
2252
2253 #define MALLOC_ALIGNMENT           (2*sizeof(size_t))
2254 #define MINSIZE                    (sizeof(CmiIsomallocBlock))
2255
2256 /** return an aligned isomalloc memory, the alignment occurs after the
2257  *  first 'reserved' bytes.  Total requested size is (size+reserved)
2258  */
2259 static void *_isomallocAlign(size_t align, size_t size, size_t reserved)
2260 {
2261         void *ptr;
2262         CmiIntPtr ptr2align;
2263         CmiInt8 s;
2264
2265         if (align < MINSIZE) align = MINSIZE;
2266         /* make sure alignment is power of 2 */
2267         if ((align & (align - 1)) != 0) {
2268           size_t a = MALLOC_ALIGNMENT * 2;
2269           while ((unsigned long)a < (unsigned long)align) a <<= 1;
2270           align = a;
2271         }
2272         s = size + reserved + align;
2273         ptr = CmiIsomalloc(s);
2274         ptr2align = (CmiIntPtr)ptr;
2275         ptr2align += reserved;
2276         if (ptr2align % align != 0) { /* misaligned */
2277           CmiIsomallocBlock *blk = pointer2block(ptr);  /* save block */
2278           CmiIsomallocBlock savedblk = *blk;
2279           ptr2align = (ptr2align + align - 1) & -((CmiInt8) align);
2280           ptr2align -= reserved;
2281           ptr = (void*)ptr2align;
2282           blk = pointer2block(ptr);      /* restore block */
2283           *blk = savedblk;
2284         }
2285         return ptr;
2286 }
2287
2288 void *CmiIsomallocAlign(size_t align, size_t size)
2289 {
2290   return _isomallocAlign(align, size, 0);
2291 }
2292
2293 int CmiIsomallocEnabled()
2294 {
2295   return (isomallocStart!=NULL);
2296 }
2297
2298 void CmiIsomallocPup(pup_er p,void **blockPtrPtr)
2299 {
2300         CmiIsomallocBlock *blk;
2301         CmiInt8 s,length;
2302         CmiInt8 n;
2303         if (isomallocStart==NULL) CmiAbort("isomalloc is disabled-- cannot use IsomallocPup");
2304
2305         if (!pup_isUnpacking(p)) 
2306         { /*We have an existing block-- unpack start slot & length*/
2307                 blk=pointer2block(*blockPtrPtr);
2308                 s=blk->slot;
2309                 length=blk->length;
2310         }
2311         
2312         pup_int8(p,&s);
2313         pup_int8(p,&length);
2314         n=length2slots(length);
2315         
2316         if (pup_isUnpacking(p)) 
2317         { /*Must allocate a new block in its old location*/
2318                 if (pup_isUserlevel(p) || pup_isRestarting(p))
2319                         /*Checkpoint: must grab old slots (even remote!)*/
2320                         all_slotOP(&grabOP,s,n);
2321                 blk=map_slots(s,n);
2322                 if (!blk) map_failed(s,n);
2323                 blk->slot=s;
2324                 blk->length=length;
2325                 *blockPtrPtr=block2pointer(blk);
2326         }
2327         
2328         /*Pup the allocated data*/
2329         pup_bytes(p,*blockPtrPtr,length);
2330         
2331         if (pup_isDeleting(p)) 
2332         { /*Unmap old slots, but do not mark as free*/
2333                 unmap_slots(s,n);
2334                 *blockPtrPtr=NULL; /*Zero out user's pointer*/
2335         }
2336 }
2337
2338 void CmiIsomallocFree(void *blockPtr)
2339 {
2340         if (isomallocStart==NULL) {
2341                 disabled_unmap(blockPtr);
2342         }
2343         else if (blockPtr!=NULL)
2344         {
2345                 CmiIsomallocBlock *blk=pointer2block(blockPtr);
2346                 CmiInt8 s=blk->slot; 
2347                 CmiInt8 n=length2slots(blk->length);
2348                 unmap_slots(s,n);
2349                 /*Mark used slots as free*/
2350                 all_slotOP(&freeOP,s,n);
2351         }
2352 }
2353
2354 CmiInt8   CmiIsomallocLength(void *block)
2355 {
2356         return pointer2block(block)->length;
2357 }
2358
2359 /*Return true if this address is in the region managed by isomalloc*/
2360 int CmiIsomallocInRange(void *addr)
2361 {
2362         if (isomallocStart==NULL) return 0; /* There is no range we manage! */
2363         return pointer_ge((char *)addr,isomallocStart) && 
2364                pointer_lt((char*)addr,isomallocEnd);
2365 }
2366
2367 void CmiIsomallocInit(char **argv)
2368 {
2369 #if CMK_NO_ISO_MALLOC
2370   disable_isomalloc("isomalloc disabled by conv-mach");
2371 #else
2372   if (CmiGetArgFlagDesc(argv,"+noisomalloc","disable isomalloc")) {
2373     disable_isomalloc("isomalloc disabled by user.");
2374     return;
2375   }
2376   if (CmiGetArgFlagDesc(argv,"+isomalloc_probe","mmap probe isomalloc region"))
2377     _mmap_probe = 1;
2378   if (CmiGetArgFlagDesc(argv,"+isomalloc_sync","synchronize isomalloc region globaly"))
2379     _sync_iso = 1;
2380   init_comm(argv);
2381   if (!init_map(argv)) {
2382     disable_isomalloc("mmap() does not work");
2383   }
2384   else {
2385     if (CmiMyPe() == 0) {
2386       if (read_randomflag() == 1) {    /* randomization stack pointer */
2387         if (_sync_iso == 1)
2388           printf("Warning> Randomization of stack pointer is turned on in kernel.\n");
2389         else
2390           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");
2391       }
2392     }
2393     init_ranges(argv);
2394   }
2395 #endif
2396 }
2397
2398 /***************** BlockList interface *********
2399 This was moved here from memory-isomalloc.c when it 
2400 was realized that a list-of-isomalloc'd-blocks is useful for
2401 more than just isomalloc heaps.
2402 */
2403
2404 /*Convert a slot to a user address*/
2405 static char *Slot_toUser(CmiIsomallocBlockList *s) {return (char *)(s+1);}
2406 static CmiIsomallocBlockList *Slot_fmUser(void *s) {return ((CmiIsomallocBlockList *)s)-1;}
2407
2408
2409 /*Build a new blockList.*/
2410 CmiIsomallocBlockList *CmiIsomallocBlockListNew(void)
2411 {
2412         CmiIsomallocBlockList *ret;
2413         ret=(CmiIsomallocBlockList *)CmiIsomalloc(sizeof(*ret));
2414         ret->next=ret; /*1-entry circular linked list*/
2415         ret->prev=ret;
2416         return ret;
2417 }
2418
2419
2420 /* BIGSIM_OOC DEBUGGING */
2421 static void print_myslots();
2422
2423 /*Pup all the blocks in this list.  This amounts to two circular
2424 list traversals.  Because everything's isomalloc'd, we don't even
2425 have to restore the pointers-- they'll be restored automatically!
2426 */
2427 void CmiIsomallocBlockListPup(pup_er p,CmiIsomallocBlockList **lp)
2428 {
2429         /* BIGSIM_OOC DEBUGGING */
2430         /* if(!pup_isUnpacking(p)) print_myslots(); */
2431
2432         int i,nBlocks=0;
2433         CmiIsomallocBlockList *cur=NULL, *start=*lp;
2434 #if 0 /*#ifndef CMK_OPTIMIZE*/
2435         if (CpvAccess(isomalloc_blocklist)!=NULL)
2436                 CmiAbort("Called CmiIsomallocBlockListPup while a blockList is active!\n"
2437                         "You should swap out the active blocklist before pupping.\n");
2438 #endif
2439         /*Count the number of blocks in the list*/
2440         if (!pup_isUnpacking(p)) {
2441                 nBlocks=1; /*<- Since we have to skip the start block*/
2442                 for (cur=start->next; cur!=start; cur=cur->next) 
2443                         nBlocks++;
2444                 /*Prepare for next trip around list:*/
2445                 cur=start;
2446         }
2447         pup_int(p,&nBlocks);
2448         
2449         /*Pup each block in the list*/
2450         for (i=0;i<nBlocks;i++) {
2451                 void *newBlock=cur;
2452                 if (!pup_isUnpacking(p)) 
2453                 { /*While packing, we traverse the list to find our blocks*/
2454                         cur=cur->next;
2455                 }
2456                 CmiIsomallocPup(p,&newBlock);
2457                 if (i==0 && pup_isUnpacking(p))
2458                         *lp=(CmiIsomallocBlockList *)newBlock;
2459         }
2460         if (pup_isDeleting(p))
2461                 *lp=NULL;
2462
2463         /* BIGSIM_OOC DEBUGGING */
2464         /* if(pup_isUnpacking(p)) print_myslots(); */
2465 }
2466
2467 /*Delete all the blocks in this list.*/
2468 void CmiIsomallocBlockListDelete(CmiIsomallocBlockList *l)
2469 {
2470     CmiIsomallocBlockList *start=l;
2471     CmiIsomallocBlockList *cur=start;
2472         if (cur==NULL) return; /*Already deleted*/
2473         do {
2474           CmiIsomallocBlockList *doomed=cur;
2475                 cur=cur->next; /*Have to stash next before deleting cur*/
2476                 CmiIsomallocFree(doomed);
2477         } while (cur!=start);
2478 }
2479
2480 /*Allocate a block from this blockList*/
2481 void *CmiIsomallocBlockListMalloc(CmiIsomallocBlockList *l,size_t nBytes)
2482 {
2483     CmiIsomallocBlockList *n; /*Newly created slot*/
2484         n=(CmiIsomallocBlockList *)CmiIsomalloc(sizeof(CmiIsomallocBlockList)+nBytes);
2485         /*Link the new block into the circular blocklist*/
2486         n->prev=l;
2487         n->next=l->next;
2488         l->next->prev=n;
2489         l->next=n;
2490         return Slot_toUser(n);
2491 }
2492
2493 /*Allocate a block from this blockList with alighment */
2494 void *CmiIsomallocBlockListMallocAlign(CmiIsomallocBlockList *l,size_t align,size_t nBytes)
2495 {
2496     CmiIsomallocBlockList *n; /*Newly created slot*/
2497         n=(CmiIsomallocBlockList *)_isomallocAlign(align,nBytes,sizeof(CmiIsomallocBlockList));
2498         /*Link the new block into the circular blocklist*/
2499         n->prev=l;
2500         n->next=l->next;
2501         l->next->prev=n;
2502         l->next=n;
2503         return Slot_toUser(n);
2504 }
2505
2506 /*Remove this block from its list and memory*/
2507 void CmiIsomallocBlockListFree(void *block)
2508 {
2509     CmiIsomallocBlockList *n=Slot_fmUser(block);
2510 #if DOHEAPCHECK
2511         if (n->prev->next!=n || n->next->prev!=n) 
2512                 CmiAbort("Heap corruption detected in isomalloc block list header!\n"
2513                         "  Run with ++debug and look for writes to negative array indices");
2514 #endif
2515         /*Link ourselves out of the blocklist*/
2516         n->prev->next=n->next;
2517         n->next->prev=n->prev;
2518         CmiIsomallocFree(n);
2519 }
2520
2521
2522
2523 /* BIGSIM_OOC DEBUGGING */
2524 static void print_myslots(){
2525     CmiPrintf("[%d] my slot set=%p\n", CmiMyPe(), CpvAccess(myss));
2526     print_slots(CpvAccess(myss));
2527 }
2528
2529
2530