check sys/mman.h
[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 statisfies 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
20 #include <stdlib.h>
21
22 /*Size in bytes of a single slot*/
23 static int slotsize;
24
25 /*Total number of slots per processor*/
26 static int numslots;
27
28 /*Start and end of isomalloc-managed addresses*/
29 static char *isomallocStart;
30 static char *isomallocEnd;
31
32 /*Utility conversion functions*/
33 static int addr2slot(void *addr) {
34         return (((char *)addr)-isomallocStart)/slotsize;
35 }
36 static void *slot2addr(int slot) {
37         return isomallocStart+slotsize*slot;
38 }
39 static int slot2pe(int slot) {
40         return slot/numslots;
41 }
42 static int pe2slot(int pe) {
43         return pe*numslots;
44 }
45 static int length2slots(int nBytes) {
46         return (nBytes+slotsize-1)/slotsize;
47 }
48 static int slots2length(int nSlots) {
49         return nSlots*slotsize;
50 }
51
52 typedef struct _slotblock
53 {
54   int startslot;
55   int nslots;
56 } slotblock;
57
58 typedef struct _slotset
59 {
60   int maxbuf;
61   slotblock *buf;
62   int emptyslots;
63 } slotset;
64
65 /*
66  * creates a new slotset of nslots entries, starting with all
67  * empty slots. The slot numbers are [startslot,startslot+nslot-1]
68  */
69 static slotset *
70 new_slotset(int startslot, int nslots)
71 {
72   int i;
73   slotset *ss = (slotset*) malloc(sizeof(slotset));
74   _MEMCHECK(ss);
75   ss->maxbuf = 16;
76   ss->buf = (slotblock *) malloc(sizeof(slotblock)*ss->maxbuf);
77   _MEMCHECK(ss->buf);
78   ss->emptyslots = nslots;
79   ss->buf[0].startslot = startslot;
80   ss->buf[0].nslots = nslots;
81   for (i=1; i<ss->maxbuf; i++)
82     ss->buf[i].nslots = 0;
83   return ss;
84 }
85
86 /*
87  * returns new block of empty slots. if it cannot find any, returns (-1).
88  */
89 static int
90 get_slots(slotset *ss, int nslots)
91 {
92   int i;
93   if(ss->emptyslots < nslots)
94     return (-1);
95   for(i=0;i<(ss->maxbuf);i++)
96     if(ss->buf[i].nslots >= nslots)
97       return ss->buf[i].startslot;
98   return (-1);
99 }
100
101 /* just adds a slotblock to an empty position in the given slotset. */
102 static void
103 add_slots(slotset *ss, int sslot, int nslots)
104 {
105   int pos, emptypos = -1;
106   if (nslots == 0)
107     return;
108   for (pos=0; pos < (ss->maxbuf); pos++) {
109     if (ss->buf[pos].nslots == 0) {
110       emptypos = pos;
111       break; /* found empty slotblock */
112     }
113   }
114   if (emptypos == (-1)) /*no empty slotblock found */
115   {
116     int i;
117     int newsize = ss->maxbuf*2;
118     slotblock *newbuf = (slotblock *) malloc(sizeof(slotblock)*newsize);
119     _MEMCHECK(newbuf);
120     for (i=0; i<(ss->maxbuf); i++)
121       newbuf[i] = ss->buf[i];
122     for (i=ss->maxbuf; i<newsize; i++)
123       newbuf[i].nslots  = 0;
124     free(ss->buf);
125     ss->buf = newbuf;
126     emptypos = ss->maxbuf;
127     ss->maxbuf = newsize;
128   }
129   ss->buf[emptypos].startslot = sslot;
130   ss->buf[emptypos].nslots = nslots;
131   ss->emptyslots += nslots;
132   return;
133 }
134
135 /* grab a slotblock with specified range of blocks
136  * this is different from get_slots, since it pre-specifies the
137  * slots to be grabbed.
138  */
139 static void
140 grab_slots(slotset *ss, int sslot, int nslots)
141 {
142   int pos, eslot, e;
143   eslot = sslot + nslots;
144   for (pos=0; pos < (ss->maxbuf); pos++)
145   {
146     if (ss->buf[pos].nslots == 0)
147       continue;
148     e = ss->buf[pos].startslot + ss->buf[pos].nslots;
149     if(sslot >= ss->buf[pos].startslot && eslot <= e)
150     {
151       int old_nslots;
152       old_nslots = ss->buf[pos].nslots;
153       ss->buf[pos].nslots = sslot - ss->buf[pos].startslot;
154       ss->emptyslots -= (old_nslots - ss->buf[pos].nslots);
155       add_slots(ss, sslot + nslots, old_nslots - ss->buf[pos].nslots - nslots);
156       return;
157     }
158   }
159   CmiAbort("requested a non-existent slotblock\n");
160 }
161
162 /*
163  * Frees slot by adding it to one of the blocks of empty slots.
164  * this slotblock is one which is contiguous with the slots to be freed.
165  * if it cannot find such a slotblock, it creates a new slotblock.
166  * If the buffer fills up, it adds up extra buffer space.
167  */
168 static void
169 free_slots(slotset *ss, int sslot, int nslots)
170 {
171   int pos;
172   /* eslot is the ending slot of the block to be freed */
173   int eslot = sslot + nslots;
174   for (pos=0; pos < (ss->maxbuf); pos++)
175   {
176     int e = ss->buf[pos].startslot + ss->buf[pos].nslots;
177     if (ss->buf[pos].nslots == 0)
178       continue;
179     /* e is the ending slot of pos'th slotblock */
180     if (e == sslot) /* append to the current slotblock */
181     {
182             ss->buf[pos].nslots += nslots;
183       ss->emptyslots += nslots;
184             return;
185     }
186     if(eslot == ss->buf[pos].startslot) /* prepend to the current slotblock */
187     {
188             ss->buf[pos].startslot = sslot;
189             ss->buf[pos].nslots += nslots;
190       ss->emptyslots += nslots;
191             return;
192     }
193   }
194   /* if we are here, it means we could not find a slotblock that the */
195   /* block to be freed was combined with. */
196   add_slots(ss, sslot, nslots);
197 }
198
199 /*
200  * destroys slotset
201  */
202 static void
203 delete_slotset(slotset* ss)
204 {
205   free(ss->buf);
206   free(ss);
207 }
208
209 #if CMK_THREADS_DEBUG
210 static void
211 print_slots(slotset *ss)
212 {
213   int i;
214   CmiPrintf("[%d] maxbuf = %d\n", CmiMyPe(), ss->maxbuf);
215   CmiPrintf("[%d] emptyslots = %d\n", CmiMyPe(), ss->emptyslots);
216   for(i=0;i<ss->maxbuf;i++) {
217     if(ss->buf[i].nslots)
218       CmiPrintf("[%d] (%d, %d) \n", CmiMyPe(), ss->buf[i].startslot, 
219           ss->buf[i].nslots);
220   }
221 }
222 #endif
223
224 #if CMK_THREADS_ARE_WIN32_FIBERS || ! CMK_HAS_MMAN_H
225 /****************** Manipulate memory map (Win32 non-version) *****************/
226 static void *
227 map_slots(int slot, int nslots)
228 {
229         CmiAbort("isomalloc: Cannot map/unmap memory");
230 }
231
232 static void
233 unmap_slots(int slot, int nslots)
234 {
235         CmiAbort("isomalloc: Cannot map/unmap memory");
236 }
237
238 static void 
239 init_map(char **argv)
240 {
241 }
242 #else
243 /****************** Manipulate memory map (UNIX version) *****************/
244 #include <sys/types.h>
245 #include <sys/mman.h>
246 #include <sys/stat.h>
247 #include <fcntl.h>
248
249 CpvStaticDeclare(int, zerofd); /*File descriptor for /dev/zero, for mmap*/
250
251 /*
252  * maps the virtual memory associated with slot using mmap
253  */
254 static void *
255 map_slots(int slot, int nslots)
256 {
257   void *pa;
258   void *addr=slot2addr(slot);
259   pa = mmap(addr, slotsize*nslots, 
260             PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED,
261             CpvAccess(zerofd), 0);
262   if((pa==((void*)(-1))) || (pa != addr)) {
263     CmiError("mmap call failed to allocate %d bytes at %p.\n", slotsize*nslots, addr);
264     CmiAbort("Exiting\n");
265   }
266 #if CMK_THREADS_DEBUG
267   CmiPrintf("[%d] mmap'd slots %d-%d to address %p\n",CmiMyPe(),
268             slot,slot+nslots-1,addr);
269 #endif
270   return pa;
271 }
272
273 /*
274  * unmaps the virtual memory associated with slot using munmap
275  */
276 static void
277 unmap_slots(int slot, int nslots)
278 {
279   void *addr=slot2addr(slot);
280   int retval = munmap(addr, slotsize*nslots);
281   if (retval==(-1))
282     CmiAbort("munmap call failed to deallocate requested memory.\n");
283 #if CMK_THREADS_DEBUG
284   CmiPrintf("[%d] munmap'd slots %d-%d from address %p\n",CmiMyPe(),
285             slot,slot+nslots-1,addr);
286 #endif
287 }
288
289 static void 
290 init_map(char **argv)
291 {
292   CpvInitialize(int, zerofd);  
293   CpvAccess(zerofd) = open("/dev/zero", O_RDWR);
294   if(CpvAccess(zerofd)<0)
295     CmiAbort("Cannot open /dev/zero. Aborting.\n");     
296 }
297
298 #endif /* UNIX memory map */
299
300 /************ Address space voodoo: find free address range **********/
301 CpvStaticDeclare(slotset *, myss); /*My managed slots*/
302
303 /*This struct describes a range of virtual addresses*/
304 typedef unsigned long memRange_t;
305 typedef struct {
306   char *start; /*First byte of region*/
307   memRange_t len; /*Number of bytes in region*/
308   const char *type; /*String describing memory in region (debugging only)*/
309 } memRegion_t;
310
311 /*Estimate the top of the current stack*/
312 static void *__cur_stack_frame(void)
313 {
314   char __dummy;
315   void *top_of_stack=(void *)&__dummy;
316   return top_of_stack;
317 }
318 /*Estimate the location of the static data region*/
319 static void *__static_data_loc(void)
320 {
321   static char __dummy;
322   return (void *)&__dummy;
323 }
324
325 static char *pmin(char *a,char *b) {return (a<b)?a:b;}
326 static char *pmax(char *a,char *b) {return (a>b)?a:b;}
327
328 /*Find the first available memory region of at least the
329   given size not touching any data in the used list.
330  */
331 static memRegion_t find_free_region(memRegion_t *used,int nUsed,int atLeast) 
332 {
333   memRegion_t max;
334   int i,j;  
335
336   /*Find the largest hole between regions*/
337   for (i=0;i<nUsed;i++) {
338     /*Consider a hole starting at the end of region i*/
339     char *holeStart=used[i].start+used[i].len;
340     char *holeEnd=(void *)(-1);
341     
342     /*Shrink the hole by all others*/ 
343     for (j=0;j<nUsed && holeStart<holeEnd;j++) {
344       if (used[j].start<holeStart) holeStart=pmax(holeStart,used[j].start+used[j].len);
345       else if (used[j].start<holeEnd) holeEnd=pmin(holeEnd,used[j].start);
346     } 
347     if (holeStart<holeEnd) 
348     { /*There is some room between these two regions*/
349       memRange_t len=((memRange_t)holeEnd)-((memRange_t)holeStart);
350 #if CMK_THREADS_DEBUG
351       CmiPrintf("[%d] Usable address space at %p - %p\n",CmiMyPe(),holeStart,holeEnd);
352 #endif
353       if (len>=atLeast) { /*This is a large enough hole-- return it*/
354         max.len=len;
355         max.start=holeStart;
356         max.type="Unused";
357         return max;
358       }
359     }
360   }
361
362   /*If we get here, there are no large enough holes*/
363   CmiAbort("ISOMALLOC cannot locate any free virtual address space!");
364   return max; /*<- never executed*/
365 }
366
367 static void init_ranges(char **argv)
368 {
369   /*Round slot size up to nearest page size*/
370   slotsize=16*1024;
371   slotsize=(slotsize+CMK_MEMORY_PAGESIZE-1) & ~(CMK_MEMORY_PAGESIZE-1);
372 #if CMK_THREADS_DEBUG
373   CmiPrintf("[%d] Using slotsize of %d\n", CmiMyPe(), slotsize);
374 #endif
375
376   /* Find the largest unused region of virtual address space */
377   {
378     char *staticData =(char *) __static_data_loc();
379     char *code = (char *)&init_ranges;
380     char *heapLil = (char*) malloc(1);
381     char *heapBig = (char*) malloc(4*1024*1024);
382     char *stack = (char *)__cur_stack_frame();
383
384     memRange_t meg=1024*1024; /*One megabyte*/
385     memRange_t gig=1024*meg; /*One gigabyte*/
386     int i,nRegions=6;
387     memRegion_t regions[6]; /*used portions of address space*/
388     memRegion_t freeRegion; /*Largest unused block of address space*/
389
390 /*Mark off regions of virtual address space as ususable*/
391     regions[0].type="NULL (inaccessible)";
392     regions[0].start=NULL; regions[0].len=16u*meg;
393     
394     regions[1].type="Static program data";
395     regions[1].start=staticData; regions[1].len=256u*meg;
396     
397     regions[2].type="Program executable code";
398     regions[2].start=code; regions[2].len=256u*meg;
399     
400     regions[3].type="Heap (small blocks)";
401     regions[3].start=heapLil; regions[3].len=2u*gig;
402
403     regions[4].type="Heap (large blocks)";
404     regions[4].start=heapBig; regions[4].len=2u*gig;
405     
406     regions[5].type="Stack space";
407     regions[5].start=stack; regions[5].len=256u*meg;
408
409     _MEMCHECK(heapBig); free(heapBig);
410     _MEMCHECK(heapLil); free(heapLil); 
411     
412     /*Align each memory region*/
413     for (i=0;i<nRegions;i++) {
414       memRange_t p=(memRange_t)regions[i].start;
415       p&=~(regions[i].len-1); /*Round down to a len-boundary (mask off low bits)*/
416       regions[i].start=(char *)p;
417 #if CMK_THREADS_DEBUG
418     CmiPrintf("[%d] Memory map: %p - %p  %s\n",CmiMyPe(),
419               regions[i].start,regions[i].start+regions[i].len,regions[i].type);
420 #endif
421     }
422     
423     /*Find the largest unused region*/
424     freeRegion=find_free_region(regions,nRegions,(512u+256u)*meg);
425
426     /*If the unused region is very large, pad it on both ends for safety*/
427     if (freeRegion.len/gig>64u) {
428       freeRegion.start+=16u*gig;
429       freeRegion.len-=20u*gig;
430     }
431
432 #if CMK_THREADS_DEBUG
433     CmiPrintf("[%d] Largest unused region: %p - %p (%d megs)\n",CmiMyPe(),
434               freeRegion.start,freeRegion.start+freeRegion.len,
435               freeRegion.len/meg);
436 #endif
437
438     /*Allocate stacks in unused region*/
439     isomallocStart=freeRegion.start;
440     isomallocEnd=freeRegion.start+freeRegion.len;
441     numslots=(freeRegion.len/slotsize)/CmiNumPes();
442
443 #if CMK_THREADS_DEBUG
444     CmiPrintf("[%d] Can isomalloc up to %d megs per pe\n",CmiMyPe(),
445               numslots*slotsize/1024/1024);
446 #endif
447   }
448
449   CpvInitialize(slotset *, myss);
450   CpvAccess(myss) = new_slotset(pe2slot(CmiMyPe()), numslots);
451 }
452
453
454 /************* Communication: for grabbing/freeing remote slots *********/
455 typedef struct _slotmsg
456 {
457   char cmicore[CmiMsgHeaderSizeBytes];
458   int pe; /*Source processor*/
459   int slot; /*First requested slot*/
460   int nslots; /*Number of requested slots*/
461 } slotmsg;
462
463 static slotmsg *prepare_slotmsg(int slot,int nslots)
464 {
465         slotmsg *m=(slotmsg *)CmiAlloc(sizeof(slotmsg));
466         m->pe=CmiMyPe();
467         m->slot=slot;
468         m->nslots=nslots;
469 }
470
471 static void grab_remote(slotmsg *msg)
472 {
473         grab_slots(CpvAccess(myss),msg->slot,msg->nslots);
474         CmiFree(msg);
475 }
476
477 static void free_remote(slotmsg *msg)
478 {
479         free_slots(CpvAccess(myss),msg->slot,msg->nslots);
480         CmiFree(msg);
481 }
482 static int grab_remote_idx, free_remote_idx;
483
484 struct slotOP {
485         /*Function pointer to perform local operation*/
486         void (*local)(slotset *ss,int s,int n);
487         /*Index to perform remote operation*/
488         int remote;
489 };
490 typedef struct slotOP slotOP;
491 static slotOP grabOP,freeOP;
492
493 static void init_comm(char **argv)
494 {
495         grab_remote_idx=CmiRegisterHandler((CmiHandler)grab_remote);
496         free_remote_idx=CmiRegisterHandler((CmiHandler)free_remote);    
497         grabOP.local=grab_slots;
498         grabOP.remote=grab_remote_idx;
499         freeOP.local=free_slots;
500         freeOP.remote=free_remote_idx;  
501 }
502
503 /*Apply the given operation to the given slots which
504   lie on the given processor.*/
505 static void one_slotOP(const slotOP *op,int pe,int s,int n)
506 {
507 /*Shrink range to only those covered by this processor*/
508         /*First and last slot for this processor*/
509         int p_s=pe2slot(pe), p_e=pe2slot(pe+1);
510         int e=s+n;
511         if (s<p_s) s=p_s;
512         if (e>p_e) e=p_e;
513         n=e-s;
514
515 /*Send off range*/
516         if (pe==CmiMyPe()) 
517                 op->local(CpvAccess(myss),s,n);
518         else 
519         {/*Remote request*/
520                 slotmsg *m=prepare_slotmsg(s,e);
521                 CmiSyncSendAndFree(pe,sizeof(slotmsg),m);
522         }
523 }
524
525 /*Apply the given operation to all slots in the range [s, s+n) 
526 After a restart from checkpoint, a slotset can cross an 
527 arbitrary set of processors.
528 */
529 static void all_slotOP(const slotOP *op,int s,int n)
530 {
531         int spe=slot2pe(s), epe=slot2pe(s+n-1);
532         int pe;
533         for (pe=spe; pe<=epe; pe++)
534                 one_slotOP(op,pe,s,n);
535 }
536
537 /************** External interface ***************/
538 void *CmiIsomalloc(int size,CmiIsomallocBlock *b)
539 {
540         int s,n;
541         n=length2slots(size);
542         /*Always satisfy mallocs with local slots:*/
543         s=get_slots(CpvAccess(myss),n);
544         if (s==-1) {
545                 CmiError("Not enough address space left on processor %d to isomalloc %d bytes!\n",
546                          CmiMyPe(),size);
547                 CmiAbort("Out of virtual address space for isomalloc");
548         }
549         grab_slots(CpvAccess(myss),s,n);
550         b->slot=s;
551         b->nslots=n;
552         return map_slots(s,n);
553 }
554
555 void *CmiIsomallocPup(pup_er p,CmiIsomallocBlock *b)
556 {
557         int s,n;
558         pup_int(p,&b->slot);
559         pup_int(p,&b->nslots);
560         s=b->slot, n=b->nslots;
561         if (pup_isUnpacking(p)) 
562         { /*Allocate block in its old location*/
563                 if (pup_isUserlevel(p))
564                         /*Checkpoint: must grab old slots (even remote!)*/
565                         all_slotOP(&grabOP,s,n);
566                 map_slots(s,n);
567         }
568         
569         /*Pup the allocated data*/
570         pup_bytes(p,slot2addr(s),slots2length(n));
571
572         if (pup_isDeleting(p)) 
573         { /*Unmap old slots, but do not mark as free*/
574                 unmap_slots(s,n);
575                 b->nslots=0;/*Mark as unmapped*/
576         }
577         return slot2addr(s);
578 }
579
580 void CmiIsomallocFree(CmiIsomallocBlock *b)
581 {
582         int s=b->slot, n=b->nslots;
583         if (n==0) return;
584         unmap_slots(s,n);
585         /*Mark used slots as free*/
586         all_slotOP(&freeOP,s,n);
587 }
588
589 /*Return true if this address is in the region managed by isomalloc*/
590 int CmiIsomallocInRange(void *addr)
591 {
592         return (isomallocStart<=((char *)addr)) && (((char *)addr)<isomallocEnd);
593 }
594
595 void CmiIsomallocInit(char **argv)
596 {
597   init_comm(argv);
598   init_ranges(argv);
599   init_map(argv);
600 }
601