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