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