fbdab57dcd4334838a17a73c9ec1a134e416d366
[charm.git] / src / conv-core / isomalloc.c
1 /**************************************************************************
2 Isomalloc:
3   A way to allocate memory at the same address on every processor.
4 This enables linked data structures, like thread stacks, to be migrated
5 to the same address range on other processors.  This is similar to an
6 explicitly managed shared memory system.
7
8   The memory is used and released via the mmap()/mumap() calls, so unused
9 memory does not take any (RAM, swap or disk) space.
10
11   The way it's implemented is that each processor claims some section 
12 of the available virtual address space, and satisfies all new allocations
13 from that space.  Migrating structures use whatever space they started with.
14
15 Written for migratable threads by Milind Bhandarkar around August 2000;
16 generalized by Orion Lawlor November 2001.
17 */
18 #include "converse.h"
19 #include "memory-isomalloc.h"
20
21 #define CMK_THREADS_DEBUG 0
22
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <errno.h> /* just so I can find dynamically-linked symbols */
26
27 static int _sync_iso = 0;
28
29 static int read_randomflag(void)
30 {
31   FILE *fp;
32   int random_flag;
33   CmiLock(smp_mutex);
34   fp = fopen("/proc/sys/kernel/randomize_va_space", "r");
35   if (fp != NULL) {
36     fscanf(fp, "%d", &random_flag);
37   }
38   else {
39     random_flag = -1;
40   }
41   CmiUnlock(smp_mutex);
42   return random_flag;
43 }
44
45 struct CmiIsomallocBlock {
46       CmiInt8 slot; /*First mapped slot*/
47       CmiInt8 length; /*Length of (user portion of) mapping, in bytes*/
48 };
49 typedef struct CmiIsomallocBlock CmiIsomallocBlock;
50
51 /*Convert a heap block pointer to/from a CmiIsomallocBlock header*/
52 static void *block2pointer(CmiIsomallocBlock *blockHeader) {
53         return (void *)(blockHeader+1);
54 }
55 static CmiIsomallocBlock *pointer2block(void *heapBlock) {
56         return ((CmiIsomallocBlock *)heapBlock)-1;
57 }
58
59 /*Integral type to be used for pointer arithmetic:*/
60 typedef size_t memRange_t;
61
62 /*Size in bytes of a single slot*/
63 static size_t slotsize;
64
65 /*Total number of slots per processor*/
66 static CmiInt8 numslots=0;
67
68 /*Start and end of isomalloc-managed addresses.
69 If isomallocStart==NULL, isomalloc is disabled.
70 */
71 static char *isomallocStart=NULL;
72 static char *isomallocEnd=NULL;
73
74 /*Utility conversion functions*/
75 static void *slot2addr(CmiInt8 slot) {
76         return isomallocStart+((memRange_t)slotsize)*((memRange_t)slot);
77 }
78 static int slot2pe(CmiInt8 slot) {
79         return slot/numslots;
80 }
81 static CmiInt8 pe2slot(int pe) {
82         return pe*numslots;
83 }
84 /*Return the number of slots in a block with n user data bytes*/
85 static int length2slots(int nBytes) {
86         return (sizeof(CmiIsomallocBlock)+nBytes+slotsize-1)/slotsize;
87 }
88
89 typedef struct _slotblock
90 {
91   CmiInt8 startslot;
92   CmiInt8 nslots;
93 } slotblock;
94
95 typedef struct _slotset
96 {
97   int maxbuf;
98   slotblock *buf;
99   CmiInt8 emptyslots;
100 } slotset;
101
102 /*
103  * creates a new slotset of nslots entries, starting with all
104  * empty slots. The slot numbers are [startslot,startslot+nslot-1]
105  */
106 static slotset *
107 new_slotset(CmiInt8 startslot, CmiInt8 nslots)
108 {
109   int i;
110   slotset *ss = (slotset*) malloc_reentrant(sizeof(slotset));
111   _MEMCHECK(ss);
112   ss->maxbuf = 16;
113   ss->buf = (slotblock *) malloc_reentrant(sizeof(slotblock)*ss->maxbuf);
114   _MEMCHECK(ss->buf);
115   ss->emptyslots = nslots;
116   ss->buf[0].startslot = startslot;
117   ss->buf[0].nslots = nslots;
118   for (i=1; i<ss->maxbuf; i++)
119     ss->buf[i].nslots = 0;
120   return ss;
121 }
122
123 /*
124  * returns new block of empty slots. if it cannot find any, returns (-1).
125  */
126 static CmiInt8
127 get_slots(slotset *ss, CmiInt8 nslots)
128 {
129   int i;
130   if(ss->emptyslots < nslots)
131     return (-1);
132   for(i=0;i<(ss->maxbuf);i++)
133     if(ss->buf[i].nslots >= nslots)
134       return ss->buf[i].startslot;
135   return (-1);
136 }
137
138 /* just adds a slotblock to an empty position in the given slotset. */
139 static void
140 add_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots)
141 {
142   int pos; 
143   int emptypos = -1;
144   if (nslots == 0)
145     return;
146   for (pos=0; pos < (ss->maxbuf); pos++) {
147     if (ss->buf[pos].nslots == 0) {
148       emptypos = pos;
149       break; /* found empty slotblock */
150     }
151   }
152   if (emptypos == (-1)) /*no empty slotblock found */
153   {
154     int i;
155     int newsize = ss->maxbuf*2;
156     slotblock *newbuf = (slotblock *) malloc_reentrant(sizeof(slotblock)*newsize);
157     _MEMCHECK(newbuf);
158     for (i=0; i<(ss->maxbuf); i++)
159       newbuf[i] = ss->buf[i];
160     for (i=ss->maxbuf; i<newsize; i++)
161       newbuf[i].nslots  = 0;
162     free_reentrant(ss->buf);
163     ss->buf = newbuf;
164     emptypos = ss->maxbuf;
165     ss->maxbuf = newsize;
166   }
167   ss->buf[emptypos].startslot = sslot;
168   ss->buf[emptypos].nslots = nslots;
169   ss->emptyslots += nslots;
170   return;
171 }
172
173 /* grab a slotblock with specified range of blocks
174  * this is different from get_slots, since it pre-specifies the
175  * slots to be grabbed.
176  */
177 static void
178 grab_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots)
179 {
180   CmiInt8 pos, eslot, e;
181   eslot = sslot + nslots;
182   for (pos=0; pos < (ss->maxbuf); pos++)
183   {
184     if (ss->buf[pos].nslots == 0)
185       continue;
186     e = ss->buf[pos].startslot + ss->buf[pos].nslots;
187     if(sslot >= ss->buf[pos].startslot && eslot <= e)
188     {
189       CmiInt8 old_nslots;
190       old_nslots = ss->buf[pos].nslots;
191       ss->buf[pos].nslots = sslot - ss->buf[pos].startslot;
192       ss->emptyslots -= (old_nslots - ss->buf[pos].nslots);
193       add_slots(ss, sslot + nslots, old_nslots - ss->buf[pos].nslots - nslots);
194       return;
195     }
196   }
197   CmiAbort("requested a non-existent slotblock\n");
198 }
199
200 /*
201  * Frees slot by adding it to one of the blocks of empty slots.
202  * this slotblock is one which is contiguous with the slots to be freed.
203  * if it cannot find such a slotblock, it creates a new slotblock.
204  * If the buffer fills up, it adds up extra buffer space.
205  */
206 static void
207 free_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots)
208 {
209   int pos;
210   /* eslot is the ending slot of the block to be freed */
211   CmiInt8 eslot = sslot + nslots;
212   for (pos=0; pos < (ss->maxbuf); pos++)
213   {
214     CmiInt8 e = ss->buf[pos].startslot + ss->buf[pos].nslots;
215     if (ss->buf[pos].nslots == 0)
216       continue;
217     /* e is the ending slot of pos'th slotblock */
218     if (e == sslot) /* append to the current slotblock */
219     {
220             ss->buf[pos].nslots += nslots;
221             ss->emptyslots += nslots;
222             return;
223     }
224     if(eslot == ss->buf[pos].startslot) /* prepend to the current slotblock */
225     {
226             ss->buf[pos].startslot = sslot;
227             ss->buf[pos].nslots += nslots;
228             ss->emptyslots += nslots;
229             return;
230     }
231   }
232   /* if we are here, it means we could not find a slotblock that the */
233   /* block to be freed was combined with. */
234   add_slots(ss, sslot, nslots);
235 }
236
237 /*
238  * destroys slotset-- currently unused
239 static void
240 delete_slotset(slotset* ss)
241 {
242   free_reentrant(ss->buf);
243   free_reentrant(ss);
244 }
245  */
246
247 #if CMK_THREADS_DEBUG
248 static void
249 print_slots(slotset *ss)
250 {
251   int i;
252   CmiPrintf("[%d] maxbuf = %d\n", CmiMyPe(), ss->maxbuf);
253   CmiPrintf("[%d] emptyslots = %d\n", CmiMyPe(), ss->emptyslots);
254   for(i=0;i<ss->maxbuf;i++) {
255     if(ss->buf[i].nslots)
256       CmiPrintf("[%d] (%d, %d) \n", CmiMyPe(), ss->buf[i].startslot, 
257           ss->buf[i].nslots);
258   }
259 }
260 #else
261 #  define print_slots(ss) /*empty*/
262 #endif
263
264 /*This version of the allocate/deallocate calls are used if the 
265 real mmap versions are disabled.*/
266 static int disabled_map_warned=0;
267 static void *disabled_map(int nBytes) 
268 {
269         if (!disabled_map_warned) {
270                 disabled_map_warned=1;
271                 if (CmiMyPe()==0)
272                         CmiError("charm isomalloc.c> Warning: since mmap() doesn't work,"
273                         " you won't be able to migrate threads\n");
274         }
275         return malloc(nBytes);
276 }
277 static void disabled_unmap(void *bk) {
278         free(bk);
279 }
280
281 /*Turn off isomalloc memory, for the given reason*/
282 static void disable_isomalloc(const char *why)
283 {
284     isomallocStart=NULL;
285     isomallocEnd=NULL;
286 #if CMK_THREADS_DEBUG
287     CmiPrintf("[%d] isomalloc.c> Disabling isomalloc because %s\n",CmiMyPe(),why);
288 #endif
289 }
290
291 #if ! CMK_HAS_MMAP
292 /****************** Manipulate memory map (Win32 non-version) *****************/
293 static void *call_mmap_fixed(void *addr,size_t len) {
294         CmiAbort("isomalloc.c: mmap_fixed should never be called here.");
295 }
296 static void *call_mmap_anywhere(size_t len) {
297         CmiAbort("isomalloc.c: mmap_anywhere should never be called here.");
298 }
299 static void call_munmap(void *addr,size_t len) {
300         CmiAbort("isomalloc.c: munmap should never be called here.");
301 }
302
303 static int 
304 init_map(char **argv)
305 {
306   return 0; /*Isomalloc never works without mmap*/
307 }
308 #else /* CMK_HAS_MMAP */
309 /****************** Manipulate memory map (UNIX version) *****************/
310 #include <sys/types.h>
311 #include <sys/mman.h>
312 #include <sys/stat.h>
313 #include <fcntl.h>
314
315 #if !CMK_HAS_MMAP_ANON
316 CpvStaticDeclare(int, zerofd); /*File descriptor for /dev/zero, for mmap*/
317 #endif
318
319 /**
320  * Maps this address with these flags.
321  */
322 static void *call_mmap(void *addr,size_t len, int flags) {
323   void *ret=mmap(addr, len, PROT_READ|PROT_WRITE,
324 #if CMK_HAS_MMAP_ANON
325             flags|MAP_PRIVATE|MAP_ANON,-1,
326 #else
327             flags|MAP_PRIVATE,CpvAccess(zerofd),
328 #endif
329             0);
330   if (ret==((void*)(-1))) return (void *)0; /* all-ones means failure */
331   else return ret;
332 }
333 static void *call_mmap_fixed(void *addr,size_t len) {
334         return call_mmap(addr,len,MAP_FIXED);
335 }
336 static void *call_mmap_anywhere(size_t len) {
337         return call_mmap((void *)0,len,0);
338 }
339
340 /* Unmaps this address range */
341 static void call_munmap(void *addr,size_t len) {
342   int retval;
343   if (addr == 0) return; /* NULL address is never mapped */ 
344   retval = munmap(addr, len);
345   if (retval==(-1))
346     CmiAbort("munmap call failed to deallocate requested memory.\n");
347 }
348
349 static int 
350 init_map(char **argv)
351 {
352 #if CMK_HAS_MMAP_ANON
353   /*Don't need /dev/zero*/
354 #else
355   CpvInitialize(int, zerofd);  
356   CpvAccess(zerofd) = open("/dev/zero", O_RDWR);
357   if(CpvAccess(zerofd)<0)
358     return 0; /* Cannot open /dev/zero or use MMAP_ANON, so can't mmap memory */
359 #endif
360   return 1;
361 }
362
363 #endif /* UNIX memory map */
364
365
366 /**
367  * maps the virtual memory associated with slot using mmap
368  */
369 static CmiIsomallocBlock *
370 map_slots(CmiInt8 slot, CmiInt8 nslots)
371 {
372   void *pa;
373   void *addr=slot2addr(slot);
374   pa = call_mmap_fixed(addr, slotsize*nslots);
375   
376   if (pa==NULL) 
377   { /*Map just failed completely*/
378 #if CMK_THREADS_DEBUG
379     perror("mmap failed");
380     CmiPrintf("[%d] tried to mmap %p, but encountered error\n",CmiMyPe(),addr);
381 #endif
382     return NULL;
383   }
384   if (pa != addr)
385   { /*Map worked, but gave us back the wrong place*/
386 #if CMK_THREADS_DEBUG
387     CmiPrintf("[%d] tried to mmap %p, but got %p back\n",CmiMyPe(),addr,pa);
388 #endif
389     call_munmap(addr,slotsize*nslots);
390     return NULL;
391   }
392 #if CMK_THREADS_DEBUG
393   CmiPrintf("[%d] mmap'd slots %d-%d to address %p\n",CmiMyPe(),
394             slot,slot+nslots-1,addr);
395 #endif
396   return (CmiIsomallocBlock *)pa;
397 }
398
399 /*
400  * unmaps the virtual memory associated with slot using munmap
401  */
402 static void
403 unmap_slots(CmiInt8 slot, CmiInt8 nslots)
404 {
405   void *addr=slot2addr(slot);
406   call_munmap(addr, slotsize*nslots);
407 #if CMK_THREADS_DEBUG
408   CmiPrintf("[%d] munmap'd slots %d-%d from address %p\n",CmiMyPe(),
409             slot,slot+nslots-1,addr);
410 #endif
411 }
412
413 static void map_failed(CmiInt8 s,CmiInt8 n)
414 {
415   void *addr=slot2addr(s);
416   CmiError("charm isomalloc.c> map failed to allocate %d bytes at %p.\n",
417       slotsize*n, addr);
418   CmiAbort("Exiting\n");
419 }
420
421
422
423 /************ Address space voodoo: find free address range **********/
424
425 CpvStaticDeclare(slotset *, myss); /*My managed slots*/
426
427 /*This struct describes a range of virtual addresses*/
428 typedef struct {
429   char *start; /*First byte of region*/
430   memRange_t len; /*Number of bytes in region*/
431   const char *type; /*String describing memory in region (debugging only)*/
432 } memRegion_t;
433
434 /*Estimate the top of the current stack*/
435 static void *__cur_stack_frame(void)
436 {
437   char __dummy;
438   void *top_of_stack=(void *)&__dummy;
439   return top_of_stack;
440 }
441 /*Estimate the location of the static data region*/
442 static void *__static_data_loc(void)
443 {
444   static char __dummy;
445   return (void *)&__dummy;
446 }
447
448 /*Pointer comparison is in these subroutines, because
449   comparing arbitrary pointers is nonportable and tricky.
450 */
451 static int pointer_lt(const char *a,const char *b) {
452         return ((memRange_t)a)<((memRange_t)b);
453 }
454 static int pointer_ge(const char *a,const char *b) {
455         return ((memRange_t)a)>=((memRange_t)b);
456 }
457
458 static char *pmin(char *a,char *b) {return pointer_lt(a,b)?a:b;}
459 static char *pmax(char *a,char *b) {return pointer_lt(a,b)?b:a;}
460
461 const static memRange_t meg=1024u*1024u; /*One megabyte*/
462 const static memRange_t gig=1024u*1024u*1024u; /*One gigabyte*/
463
464 /*Check if this memory location is usable.  
465   If not, return 1.
466 */
467 static int bad_location(char *loc) {
468   void *addr;
469   addr=call_mmap_fixed(loc,slotsize);
470   if (addr==NULL) {
471 #if CMK_THREADS_DEBUG
472     CmiPrintf("[%d] Skipping unmappable space at %p\n",CmiMyPe(),loc);
473 #endif
474     return 1; /*No good*/
475   }
476   call_munmap(addr,slotsize);
477   return 0; /*This works*/
478 }
479
480 /* Split this range up into n pieces, returning the size of each piece */
481 static memRange_t divide_range(memRange_t len,int n) {
482         return (len+1)/n;
483 }
484
485 /* Return if this memory region has *any* good parts. */
486 static int partially_good(char *start,memRange_t len,int n) {
487   int i;
488   memRange_t quant=divide_range(len,n);
489   for (i=0;i<n;i++)
490     if (!bad_location(start+i*quant)) return 1; /* it's got some good parts */
491   return 0; /* all locations are bad */
492 }
493
494 /* Return if this memory region is usable at n samples.  
495 */
496 static int good_range(char *start,memRange_t len,int n) {
497   int i;
498   memRange_t quant=divide_range(len,n);
499   for (i=0;i<n;i++)
500     if (bad_location(start+i*quant)) return 0; /* it's got some bad parts */
501   /* It's all good: */
502   return 1;
503 }
504
505 /*Check if this entire memory range, or some subset 
506   of the range, is usable.  If so, write it into max.
507 */
508 static void check_range(char *start,char *end,memRegion_t *max)
509 {
510   memRange_t len;
511   char *initialStart=start, *initialEnd=end;
512   CmiUInt8 tb = (CmiUInt8)gig*1024ul;   /* One terabyte */
513   CmiUInt8 vm_limit = tb*256ul;   /* terabyte */
514
515   if (start>=end) return; /*Ran out of hole*/
516   len=(memRange_t)end-(memRange_t)start;
517   
518 #if 0
519     /* too conservative */
520   if (len/gig>64u) { /* This is an absurd amount of space-- cut it down, for safety */
521      start+=16u*gig;
522      end=start+32u*gig;
523      len=(memRange_t)end-(memRange_t)start;  
524   }
525 #else
526   /* Note: 256TB == 248 bytes.  So a 48-bit virtual-address CPU 
527    *    can only actually address 256TB of space. */
528   if (len/tb>10u) { /* This is an absurd amount of space-- cut it down, for safety */
529     const memRange_t other_libs=16ul*gig; /* space for other libraries to use */
530     start+=other_libs;
531     end=pmin(start+vm_limit-2*other_libs, end-other_libs);
532     len=(memRange_t)end-(memRange_t)start;
533   }
534 #endif
535   if (len<=max->len) return; /*It's too short already!*/
536 #if CMK_THREADS_DEBUG
537   CmiPrintf("[%d] Checking at %p - %p\n",CmiMyPe(),start,end);
538 #endif
539   
540   /* Check the middle of the range */
541   if (!good_range(start,len,256)) {
542     /* Try to split into subranges: */
543     int i,n=2;
544 #if CMK_THREADS_DEBUG
545     CmiPrintf("[%d] Trying to split bad address space at %p - %p...\n",CmiMyPe(),start,end);
546 #endif
547     len=divide_range(len,n);
548     for (i=0;i<n;i++) {
549         char *cur=start+i*len;
550         if (partially_good(cur,len,16))
551            check_range(cur,cur+len,max);
552     }
553     return; /* Hopefully one of the subranges will be any good */
554   }
555   else /* range is good */
556   { 
557 #if CMK_THREADS_DEBUG
558     CmiPrintf("[%d] Address space at %p - %p is largest\n",CmiMyPe(),start,end);
559 #endif
560
561     /*If we got here, we're the new largest usable range*/
562     max->len=len;
563     max->start=start;
564     max->type="Unused";
565   }
566 }
567
568 /*Find the first available memory region of at least the
569   given size not touching any data in the used list.
570  */
571 static memRegion_t find_free_region(memRegion_t *used,int nUsed,int atLeast) 
572 {
573   memRegion_t max;
574   int i,j;  
575
576   max.start=0; 
577   max.len=atLeast;
578   /*Find the largest hole between regions*/
579   for (i=0;i<nUsed;i++) {
580     /*Consider a hole starting at the end of region i*/
581     char *holeStart=used[i].start+used[i].len;
582     char *holeEnd=(void *)(-1);
583     
584     /*Shrink the hole by all others*/ 
585     for (j=0;j<nUsed && pointer_lt(holeStart,holeEnd);j++) {
586       if (pointer_lt(used[j].start,holeStart)) 
587         holeStart=pmax(holeStart,used[j].start+used[j].len);
588       else if (pointer_lt(used[j].start,holeEnd)) 
589         holeEnd=pmin(holeEnd,used[j].start);
590     } 
591
592     check_range(holeStart,holeEnd,&max);
593   }
594
595   return max; 
596 }
597
598 /*
599 By looking at the address range carefully, try to find 
600 the largest usable free region on the machine.
601 */
602 static int find_largest_free_region(memRegion_t *destRegion) {
603     char *staticData =(char *) __static_data_loc();
604     char *code = (char *)&find_free_region;
605     char *threadData = (char *)&errno;
606     char *codeDll = (char *)fprintf;
607     char *heapLil = (char*) malloc(1);
608     char *heapBig = (char*) malloc(6*meg);
609     char *stack = (char *)__cur_stack_frame();
610     size_t mmapAnyLen = 1*meg;
611     char *mmapAny = (char*) call_mmap_anywhere(mmapAnyLen);
612
613     int i,nRegions=9;
614     memRegion_t regions[10]; /*used portions of address space*/
615     memRegion_t freeRegion; /*Largest unused block of address space*/
616
617 /*Mark off regions of virtual address space as ususable*/
618     regions[0].type="NULL";
619     regions[0].start=NULL; regions[0].len=16u*meg;
620     
621     regions[1].type="Static program data";
622     regions[1].start=staticData; regions[1].len=256u*meg;
623     
624     regions[2].type="Program executable code";
625     regions[2].start=code; regions[2].len=256u*meg;
626     
627     regions[3].type="Heap (small blocks)";
628     regions[3].start=heapLil; regions[3].len=1u*gig;
629     
630     regions[4].type="Heap (large blocks)";
631     regions[4].start=heapBig; regions[4].len=1u*gig;
632     
633     regions[5].type="Stack space";
634     regions[5].start=stack; regions[5].len=256u*meg;
635
636     regions[6].type="Program dynamically linked code";
637     regions[6].start=codeDll; regions[6].len=256u*meg; 
638
639     regions[7].type="Result of a non-fixed call to mmap";
640     regions[7].start=mmapAny; regions[7].len=1u*gig; 
641
642     regions[8].type="Thread private data";
643     regions[8].start=threadData; regions[8].len=256u*meg; 
644
645     _MEMCHECK(heapBig); free(heapBig);
646     _MEMCHECK(heapLil); free(heapLil); 
647     call_munmap(mmapAny,mmapAnyLen);
648     
649     /*Align each memory region*/
650     for (i=0;i<nRegions;i++) {
651       memRegion_t old=regions[i];
652       memRange_t p=(memRange_t)regions[i].start;
653       p&=~(regions[i].len-1); /*Round start down to a len-boundary (mask off low bits)*/
654       regions[i].start=(char *)p;
655 #if CMK_THREADS_DEBUG
656       CmiPrintf("[%d] Memory map: %p - %p %s (at %p)\n",CmiMyPe(),
657               regions[i].start,regions[i].start+regions[i].len,
658               regions[i].type, old.start);
659 #endif
660     }
661     
662     /*Find a large, unused region in this map: */
663     freeRegion=find_free_region(regions,nRegions,(512u)*meg);
664     
665     if (freeRegion.start==0) 
666     { /*No free address space-- disable isomalloc:*/
667       return 0;
668     }
669     else /* freeRegion is valid */
670     {
671       *destRegion=freeRegion;
672       
673       return 1;
674     }
675 }
676
677 static void init_ranges(char **argv)
678 {
679   /*Largest value a signed int can hold*/
680   memRange_t intMax=(((memRange_t)1)<<(sizeof(int)*8-1))-1;
681
682   /*Round slot size up to nearest page size*/
683   slotsize=16*1024;
684   slotsize=(slotsize+CMK_MEMORY_PAGESIZE-1) & ~(CMK_MEMORY_PAGESIZE-1);
685 #if CMK_THREADS_DEBUG
686   CmiPrintf("[%d] Using slotsize of %d\n", CmiMyPe(), slotsize);
687 #endif
688
689   if (CmiMyRank()==0 && numslots==0)
690   { /* Find the largest unused region of virtual address space */
691       memRegion_t freeRegion;
692       freeRegion.len=0u;
693 #ifdef CMK_MMAP_START_ADDRESS /* Hardcoded start address, for machines where automatic fails */
694       freeRegion.start=CMK_MMAP_START_ADDRESS;
695       freeRegion.len=CMK_MMAP_LENGTH_MEGS*meg;
696 #endif
697       if (freeRegion.len==0u) find_largest_free_region(&freeRegion);
698       
699 #if 0
700       /*Make sure our largest slot number doesn't overflow an int:*/
701       if (freeRegion.len/slotsize>intMax)
702         freeRegion.len=intMax*slotsize;
703 #endif
704       
705       if (freeRegion.len==0u) {
706         disable_isomalloc("no free virtual address space");
707       }
708       else /* freeRegion.len>0, so can isomalloc */
709       {
710 #if CMK_THREADS_DEBUG
711         CmiPrintf("[%d] Isomalloc memory region: %p - %p (%d megs)\n",CmiMyPe(),
712               freeRegion.start,freeRegion.start+freeRegion.len,
713               freeRegion.len/meg);
714 #endif
715         
716           /*
717              on some machines, isomalloc memory regions on different nodes 
718              can be different. use +isomalloc_sync to calculate the
719              intersect of all memory regions on all nodes.
720           */
721         if (_sync_iso == 1) {
722           if (CmiBarrier() == -1) 
723             CmiAbort("Charm++ Error> +isomalloc_sync requires CmiBarrier() implemented.\n");
724           else {
725             CmiUInt8 s = (CmiUInt8)freeRegion.start;
726             CmiUInt8 e = (CmiUInt8)(freeRegion.start+freeRegion.len);
727             int fd, i;
728             char fname[128];
729
730             if (CmiMyNode()==0) printf("Charm++> synchronizing isomalloc memory region...\n");
731
732               /* write region into file */
733             sprintf(fname,".isomalloc.%d", CmiMyNode());
734             while ((fd = open(fname, O_WRONLY|O_TRUNC|O_CREAT, 0644)) == -1) sleep(1);
735             write(fd, &s, sizeof(CmiUInt8));
736             write(fd, &e, sizeof(CmiUInt8));
737             close(fd);
738
739             CmiBarrier();
740
741             for (i=0; i<CmiNumNodes(); i++) {
742               CmiUInt8 ss, ee; 
743               char fname[128];
744               if (i==CmiMyNode()) continue;
745               sprintf(fname,".isomalloc.%d", i);
746               while ((fd = open(fname, O_RDONLY)) == -1) sleep(1);
747               read(fd, &ss, sizeof(CmiUInt8));
748               read(fd, &ee, sizeof(CmiUInt8));
749               close(fd);
750               if (ss>s) s = ss;
751               if (ee<e) e = ee;
752             }
753
754             CmiBarrier();
755
756             unlink(fname);
757
758               /* update */
759             freeRegion.start = (void *)s;
760             freeRegion.len = (char *)e -(char *)s;
761 #if CMK_THREADS_DEBUG
762             CmiPrintf("[%d] consolidated Isomalloc memory region: %p - %p (%d megs)\n",CmiMyPe(),
763               freeRegion.start,freeRegion.start+freeRegion.len,
764               freeRegion.len/meg);
765 #endif
766           }   /* end of barrier test */
767         }
768
769         /*Isomalloc covers entire unused region*/
770         isomallocStart=freeRegion.start;
771         isomallocEnd=freeRegion.start+freeRegion.len;
772         numslots=(freeRegion.len/slotsize)/CmiNumPes();
773         
774 #if CMK_THREADS_DEBUG
775         CmiPrintf("[%d] Can isomalloc up to %lu megs per pe\n",CmiMyPe(),
776               ((memRange_t)numslots)*slotsize/meg);
777 #endif
778       }
779   }
780   /*SMP Mode: wait here for rank 0 to initialize numslots so we can set up myss*/
781   CmiNodeAllBarrier(); 
782   
783   if (isomallocStart!=NULL) {
784     CpvInitialize(slotset *, myss);
785     CpvAccess(myss) = new_slotset(pe2slot(CmiMyPe()), numslots);
786   }
787 }
788
789
790 /************* Communication: for grabbing/freeing remote slots *********/
791 typedef struct _slotmsg
792 {
793   char cmicore[CmiMsgHeaderSizeBytes];
794   int pe; /*Source processor*/
795   CmiInt8 slot; /*First requested slot*/
796   CmiInt8 nslots; /*Number of requested slots*/
797 } slotmsg;
798
799 static slotmsg *prepare_slotmsg(CmiInt8 slot,CmiInt8 nslots)
800 {
801         slotmsg *m=(slotmsg *)CmiAlloc(sizeof(slotmsg));
802         m->pe=CmiMyPe();
803         m->slot=slot;
804         m->nslots=nslots;
805         return m;
806 }
807
808 static void grab_remote(slotmsg *msg)
809 {
810         grab_slots(CpvAccess(myss),msg->slot,msg->nslots);
811         CmiFree(msg);
812 }
813
814 static void free_remote(slotmsg *msg)
815 {
816         free_slots(CpvAccess(myss),msg->slot,msg->nslots);
817         CmiFree(msg);
818 }
819 static int grab_remote_idx, free_remote_idx;
820
821 struct slotOP {
822         /*Function pointer to perform local operation*/
823         void (*local)(slotset *ss,CmiInt8 s,CmiInt8 n);
824         /*Index to perform remote operation*/
825         int remote;
826 };
827 typedef struct slotOP slotOP;
828 static slotOP grabOP,freeOP;
829
830 static void init_comm(char **argv)
831 {
832         grab_remote_idx=CmiRegisterHandler((CmiHandler)grab_remote);
833         free_remote_idx=CmiRegisterHandler((CmiHandler)free_remote);    
834         grabOP.local=grab_slots;
835         grabOP.remote=grab_remote_idx;
836         freeOP.local=free_slots;
837         freeOP.remote=free_remote_idx;  
838 }
839
840 /*Apply the given operation to the given slots which
841   lie on the given processor.*/
842 static void one_slotOP(const slotOP *op,int pe,CmiInt8 s,CmiInt8 n)
843 {
844 /*Shrink range to only those covered by this processor*/
845         /*First and last slot for this processor*/
846         CmiInt8 p_s=pe2slot(pe), p_e=pe2slot(pe+1);
847         CmiInt8 e=s+n;
848         if (s<p_s) s=p_s;
849         if (e>p_e) e=p_e;
850         n=e-s;
851
852 /*Send off range*/
853         if (pe==CmiMyPe()) 
854                 op->local(CpvAccess(myss),s,n);
855         else 
856         {/*Remote request*/
857                 slotmsg *m=prepare_slotmsg(s,n);
858                 CmiSetHandler(m, freeOP.remote);
859                 CmiSyncSendAndFree(pe,sizeof(slotmsg),m);
860         }
861 }
862
863 /*Apply the given operation to all slots in the range [s, s+n) 
864 After a restart from checkpoint, a slotset can cross an 
865 arbitrary set of processors.
866 */
867 static void all_slotOP(const slotOP *op,CmiInt8 s,CmiInt8 n)
868 {
869         int spe=slot2pe(s), epe=slot2pe(s+n-1);
870         int pe;
871         for (pe=spe; pe<=epe; pe++)
872                 one_slotOP(op,pe,s,n);
873 }
874
875 /************** External interface ***************/
876 void *CmiIsomalloc(int size)
877 {
878         CmiInt8 s,n;
879         CmiIsomallocBlock *blk;
880         if (isomallocStart==NULL) return disabled_map(size);
881         n=length2slots(size);
882         /*Always satisfy mallocs with local slots:*/
883         s=get_slots(CpvAccess(myss),n);
884         if (s==-1) {
885                 CmiError("Not enough address space left on processor %d to isomalloc %d bytes!\n",
886                          CmiMyPe(),size);
887                 CmiAbort("Out of virtual address space for isomalloc");
888         }
889         grab_slots(CpvAccess(myss),s,n);
890         blk=map_slots(s,n);
891         if (!blk) map_failed(s,n);
892         blk->slot=s;
893         blk->length=size;
894         return block2pointer(blk);
895 }
896
897 void CmiIsomallocPup(pup_er p,void **blockPtrPtr)
898 {
899         CmiIsomallocBlock *blk;
900         CmiInt8 s,length;
901         CmiInt8 n;
902         if (isomallocStart==NULL) CmiAbort("isomalloc is disabled-- cannot use IsomallocPup");
903
904         if (!pup_isUnpacking(p)) 
905         { /*We have an existing block-- unpack start slot & length*/
906                 blk=pointer2block(*blockPtrPtr);
907                 s=blk->slot;
908                 length=blk->length;
909         }
910         
911         pup_int8(p,&s);
912         pup_int8(p,&length);
913         n=length2slots(length);
914         
915         if (pup_isUnpacking(p)) 
916         { /*Must allocate a new block in its old location*/
917                 if (pup_isUserlevel(p) || pup_isRestarting(p))
918                         /*Checkpoint: must grab old slots (even remote!)*/
919                         all_slotOP(&grabOP,s,n);
920                 blk=map_slots(s,n);
921                 if (!blk) map_failed(s,n);
922                 blk->slot=s;
923                 blk->length=length;
924                 *blockPtrPtr=block2pointer(blk);
925         }
926         
927         /*Pup the allocated data*/
928         pup_bytes(p,*blockPtrPtr,length);
929         
930         if (pup_isDeleting(p)) 
931         { /*Unmap old slots, but do not mark as free*/
932                 unmap_slots(s,n);
933                 *blockPtrPtr=NULL; /*Zero out user's pointer*/
934         }
935 }
936
937 void CmiIsomallocFree(void *blockPtr)
938 {
939         if (isomallocStart==NULL) {
940                 disabled_unmap(blockPtr);
941         }
942         else if (blockPtr!=NULL)
943         {
944                 CmiIsomallocBlock *blk=pointer2block(blockPtr);
945                 CmiInt8 s=blk->slot; 
946                 CmiInt8 n=length2slots(blk->length);
947                 unmap_slots(s,n);
948                 /*Mark used slots as free*/
949                 all_slotOP(&freeOP,s,n);
950         }
951 }
952
953 CmiInt8   CmiIsomallocLength(void *block)
954 {
955         return pointer2block(block)->length;
956 }
957
958 /*Return true if this address is in the region managed by isomalloc*/
959 int CmiIsomallocInRange(void *addr)
960 {
961         if (isomallocStart==NULL) return 0; /* There is no range we manage! */
962         return pointer_ge((char *)addr,isomallocStart) && 
963                pointer_lt((char*)addr,isomallocEnd);
964 }
965
966 void CmiIsomallocInit(char **argv)
967 {
968 #if CMK_NO_ISO_MALLOC
969   disable_isomalloc("isomalloc disabled by conv-mach");
970 #else
971   if (CmiGetArgFlagDesc(argv,"+isomalloc_sync","synchronize isomalloc region globaly"))
972   _sync_iso = 1;
973   init_comm(argv);
974   if (!init_map(argv)) {
975     disable_isomalloc("mmap() does not work");
976   }
977   else {
978     if (read_randomflag() == 1) {    /* randomization stack pointer */
979       if (CmiMyPe() == 0)
980         printf("Charm warning> Randomization of stack pointer is turned on in Kernel, run 'echo 0 > /proc/sys/kernel/randomize_va_space' as root to disable it. Thread migration may not work! \n");
981     }
982     init_ranges(argv);
983   }
984 #endif
985 }
986
987 /***************** BlockList interface *********
988 This was moved here from memory-isomalloc.c when it 
989 was realized that a list-of-isomalloc'd-blocks is useful for
990 more than just isomalloc heaps.
991 */
992
993 typedef CmiIsomallocBlockList Slot;
994
995 /*Convert a slot to a user address*/
996 static char *Slot_toUser(Slot *s) {return (char *)(s+1);}
997 static Slot *Slot_fmUser(void *s) {return ((Slot *)s)-1;}
998
999
1000 /*Build a new blockList.*/
1001 CmiIsomallocBlockList *CmiIsomallocBlockListNew(void)
1002 {
1003         CmiIsomallocBlockList *ret;
1004         ret=(CmiIsomallocBlockList *)CmiIsomalloc(sizeof(*ret));
1005         ret->next=ret; /*1-entry circular linked list*/
1006         ret->prev=ret;
1007         return ret;
1008 }
1009
1010 /*Pup all the blocks in this list.  This amounts to two circular
1011 list traversals.  Because everything's isomalloc'd, we don't even
1012 have to restore the pointers-- they'll be restored automatically!
1013 */
1014 void CmiIsomallocBlockListPup(pup_er p,CmiIsomallocBlockList **lp)
1015 {
1016         int i,nBlocks=0;
1017         Slot *cur=NULL, *start=*lp;
1018 #if 0 /*#ifndef CMK_OPTIMIZE*/
1019         if (CpvAccess(isomalloc_blocklist)!=NULL)
1020                 CmiAbort("Called CmiIsomallocBlockListPup while a blockList is active!\n"
1021                         "You should swap out the active blocklist before pupping.\n");
1022 #endif
1023         /*Count the number of blocks in the list*/
1024         if (!pup_isUnpacking(p)) {
1025                 nBlocks=1; /*<- Since we have to skip the start block*/
1026                 for (cur=start->next; cur!=start; cur=cur->next) 
1027                         nBlocks++;
1028                 /*Prepare for next trip around list:*/
1029                 cur=start;
1030         }
1031         pup_int(p,&nBlocks);
1032         
1033         /*Pup each block in the list*/
1034         for (i=0;i<nBlocks;i++) {
1035                 void *newBlock=cur;
1036                 if (!pup_isUnpacking(p)) 
1037                 { /*While packing, we traverse the list to find our blocks*/
1038                         cur=cur->next;
1039                 }
1040                 CmiIsomallocPup(p,&newBlock);
1041                 if (i==0 && pup_isUnpacking(p))
1042                         *lp=(Slot *)newBlock;
1043         }
1044         if (pup_isDeleting(p))
1045                 *lp=NULL;
1046 }
1047
1048 /*Delete all the blocks in this list.*/
1049 void CmiIsomallocBlockListDelete(CmiIsomallocBlockList *l)
1050 {
1051         Slot *start=l;
1052         Slot *cur=start;
1053         if (cur==NULL) return; /*Already deleted*/
1054         do {
1055                 Slot *doomed=cur;
1056                 cur=cur->next; /*Have to stash next before deleting cur*/
1057                 CmiIsomallocFree(doomed);
1058         } while (cur!=start);
1059 }
1060
1061 /*Allocate a block from this blockList*/
1062 void *CmiIsomallocBlockListMalloc(CmiIsomallocBlockList *l,int nBytes)
1063 {
1064         Slot *n; /*Newly created slot*/
1065         n=(Slot *)CmiIsomalloc(sizeof(Slot)+nBytes);
1066         /*Link the new block into the circular blocklist*/
1067         n->prev=l;
1068         n->next=l->next;
1069         l->next->prev=n;
1070         l->next=n;
1071         return Slot_toUser(n);
1072 }
1073
1074 /*Remove this block from its list and memory*/
1075 void CmiIsomallocBlockListFree(void *block)
1076 {
1077         Slot *n=Slot_fmUser(block);
1078 #if DOHEAPCHECK
1079         if (n->prev->next!=n || n->next->prev!=n) 
1080                 CmiAbort("Heap corruption detected in isomalloc block list header!\n"
1081                         "  Run with ++debug and look for writes to negative array indices");
1082 #endif
1083         /*Link ourselves out of the blocklist*/
1084         n->prev->next=n->next;
1085         n->next->prev=n->prev;
1086         CmiIsomallocFree(n);
1087 }
1088
1089
1090
1091
1092