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