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