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