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