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