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