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