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