Substantial change to how isomalloc searches for memory--
[charm.git] / src / conv-core / isomalloc.c
index 1365754b51360d4178ed8d89e13eee871d3dd9fc..fd8f7bfb11c0bf2202d4024dbd23b88b8a69525c 100644 (file)
@@ -22,6 +22,7 @@ generalized by Orion Lawlor November 2001.
 
 #include <stdio.h>
 #include <stdlib.h>
+#include <errno.h> /* just so I can find dynamically-linked symbols */
 
 struct CmiIsomallocBlock {
       int slot; /*First mapped slot*/
@@ -41,7 +42,7 @@ static CmiIsomallocBlock *pointer2block(void *heapBlock) {
 typedef unsigned long memRange_t;
 
 /*Size in bytes of a single slot*/
-static int slotsize;
+static size_t slotsize;
 
 /*Total number of slots per processor*/
 static int numslots=0;
@@ -270,16 +271,14 @@ static void disable_isomalloc(const char *why)
 
 #if ! CMK_HAS_MMAP
 /****************** Manipulate memory map (Win32 non-version) *****************/
-static CmiIsomallocBlock *
-map_slots(int slot, int nslots)
-{
-       CmiAbort("isomalloc.c: map_slots should never be called here.");
+static void *call_mmap_fixed(void *addr,size_t len) {
+       CmiAbort("isomalloc.c: mmap_fixed should never be called here.");
 }
-
-static void
-unmap_slots(int slot, int nslots)
-{
-       CmiAbort("isomalloc.c: unmap_slots should never be called here.");      
+static void *call_mmap_anywhere(size_t len) {
+       CmiAbort("isomalloc.c: mmap_anywhere should never be called here.");
+}
+static void call_munmap(void *addr,size_t len) {
+       CmiAbort("isomalloc.c: munmap should never be called here.");
 }
 
 static int 
@@ -298,7 +297,52 @@ init_map(char **argv)
 CpvStaticDeclare(int, zerofd); /*File descriptor for /dev/zero, for mmap*/
 #endif
 
-/*
+/**
+ * Maps this address with these flags.
+ */
+static void *call_mmap(void *addr,size_t len, int flags) {
+  void *ret=mmap(addr, len, PROT_READ|PROT_WRITE,
+#if CMK_HAS_MMAP_ANON
+           flags|MAP_PRIVATE|MAP_ANON,-1,
+#else
+           flags|MAP_PRIVATE,CpvAccess(zerofd),
+#endif
+           0);
+  if (ret==((void*)(-1))) return (void *)0; /* all-ones means failure */
+  else return ret;
+}
+static void *call_mmap_fixed(void *addr,size_t len) {
+       return call_mmap(addr,len,MAP_FIXED);
+}
+static void *call_mmap_anywhere(size_t len) {
+       return call_mmap((void *)0,len,0);
+}
+
+/* Unmaps this address range */
+static void call_munmap(void *addr,size_t len) {
+  int retval = munmap(addr, len);
+  if (retval==(-1))
+    CmiAbort("munmap call failed to deallocate requested memory.\n");
+}
+
+static int 
+init_map(char **argv)
+{
+#if CMK_HAS_MMAP_ANON
+  /*Don't need /dev/zero*/
+#else
+  CpvInitialize(int, zerofd);  
+  CpvAccess(zerofd) = open("/dev/zero", O_RDWR);
+  if(CpvAccess(zerofd)<0)
+    return 0; /* Cannot open /dev/zero or use MMAP_ANON, so can't mmap memory */
+#endif
+  return 1;
+}
+
+#endif /* UNIX memory map */
+
+
+/**
  * maps the virtual memory associated with slot using mmap
  */
 static CmiIsomallocBlock *
@@ -306,15 +350,9 @@ map_slots(int slot, int nslots)
 {
   void *pa;
   void *addr=slot2addr(slot);
-  pa = mmap(addr, slotsize*nslots, 
-            PROT_READ|PROT_WRITE, 
-#if CMK_HAS_MMAP_ANON
-           MAP_PRIVATE|MAP_FIXED|MAP_ANON,-1,
-#else
-           MAP_PRIVATE|MAP_FIXED,CpvAccess(zerofd),
-#endif
-           0);
-  if (pa==((void*)(-1)) || pa==NULL) 
+  pa = call_mmap_fixed(addr, slotsize*nslots);
+  
+  if (pa==NULL) 
   { /*Map just failed completely*/
 #if CMK_THREADS_DEBUG
     perror("mmap failed");
@@ -327,7 +365,7 @@ map_slots(int slot, int nslots)
 #if CMK_THREADS_DEBUG
     CmiPrintf("[%d] tried to mmap %p, but got %p back\n",CmiMyPe(),addr,pa);
 #endif
-    munmap(addr,slotsize*nslots);
+    call_munmap(addr,slotsize*nslots);
     return NULL;
   }
 #if CMK_THREADS_DEBUG
@@ -344,32 +382,13 @@ static void
 unmap_slots(int slot, int nslots)
 {
   void *addr=slot2addr(slot);
-  int retval = munmap(addr, slotsize*nslots);
-  if (retval==(-1))
-    CmiAbort("munmap call failed to deallocate requested memory.\n");
+  call_munmap(addr, slotsize*nslots);
 #if CMK_THREADS_DEBUG
   CmiPrintf("[%d] munmap'd slots %d-%d from address %p\n",CmiMyPe(),
            slot,slot+nslots-1,addr);
 #endif
 }
 
-static int 
-init_map(char **argv)
-{
-#if CMK_HAS_MMAP_ANON
-  /*Don't need /dev/zero*/
-#else
-  CpvInitialize(int, zerofd);  
-  CpvAccess(zerofd) = open("/dev/zero", O_RDWR);
-  if(CpvAccess(zerofd)<0)
-    return 0; /* Cannot open /dev/zero or use MMAP_ANON, so can't mmap memory */
-#endif
-  return 1;
-}
-
-#endif /* UNIX memory map */
-
-
 static void map_failed(int s,int n)
 {
   void *addr=slot2addr(s);
@@ -418,69 +437,97 @@ static int pointer_ge(const char *a,const char *b) {
 static char *pmin(char *a,char *b) {return pointer_lt(a,b)?a:b;}
 static char *pmax(char *a,char *b) {return pointer_lt(a,b)?b:a;}
 
+const static memRange_t meg=1024u*1024u; /*One megabyte*/
+const static memRange_t gig=1024u*1024u*1024u; /*One gigabyte*/
+
 /*Check if this memory location is usable.  
   If not, return 1.
 */
-static int bad_range(char *loc) {
+static int bad_location(char *loc) {
   void *addr;
-  isomallocStart=loc;
-  addr=map_slots(0,1);
+  addr=call_mmap_fixed(loc,slotsize);
   if (addr==NULL) {
 #if CMK_THREADS_DEBUG
     CmiPrintf("[%d] Skipping unmappable space at %p\n",CmiMyPe(),loc);
 #endif
     return 1; /*No good*/
   }
-  unmap_slots(0,1);
+  call_munmap(addr,slotsize);
   return 0; /*This works*/
 }
 
-/*Check if this memory range is usable.  
-  If so, write it into max.
+/* Split this range up into n pieces, returning the size of each piece */
+static memRange_t divide_range(memRange_t len,int n) {
+       return (len+1)/n;
+}
+
+/* Return if this memory region has *any* good parts. */
+static int partially_good(char *start,memRange_t len,int n) {
+  int i;
+  memRange_t quant=divide_range(len,n);
+  for (i=0;i<n;i++)
+    if (!bad_location(start+i*quant)) return 1; /* it's got some good parts */
+  return 0; /* all locations are bad */
+}
+
+/* Return if this memory region is usable at n samples.  
+*/
+static int good_range(char *start,memRange_t len,int n) {
+  int i;
+  memRange_t quant=divide_range(len,n);
+  for (i=0;i<n;i++)
+    if (bad_location(start+i*quant)) return 0; /* it's got some bad parts */
+  /* It's all good: */
+  return 1;
+}
+
+/*Check if this entire memory range, or some subset 
+  of the range, is usable.  If so, write it into max.
 */
 static void check_range(char *start,char *end,memRegion_t *max)
 {
   memRange_t len;
-  memRange_t searchQuantStart=128u*1024*1024; /*Shift search location by this far*/
-  memRange_t searchQuant;
   char *initialStart=start, *initialEnd=end;
 
   if (start>=end) return; /*Ran out of hole*/
   len=(memRange_t)end-(memRange_t)start;
+  
+  if (len/gig>64u) { /* This is an absurd amount of space-- cut it down, for safety */
+     start+=16u*gig;
+     end=start+32u*gig;
+     len=(memRange_t)end-(memRange_t)start;  
+  }
   if (len<=max->len) return; /*It's too short already!*/
 #if CMK_THREADS_DEBUG
-  CmiPrintf("[%d] Checking usable address space at %p - %p\n",CmiMyPe(),start,end);
+  CmiPrintf("[%d] Checking at %p - %p\n",CmiMyPe(),start,end);
 #endif
-
-  /* Trim off start of range until we hit usable memory*/  
-  searchQuant=searchQuantStart;
-  while (bad_range(start)) {
-       start=initialStart+searchQuant;
-        if (pointer_ge(start,end)) return; /*Ran out of hole*/
-       searchQuant*=2; /*Exponential search*/
-        if (searchQuant==0) return; /*SearchQuant overflowed-- no good memory anywhere*/
-  }
-
-  /* Trim off end of range until we hit usable memory*/
-  searchQuant=searchQuantStart;
-  while (bad_range(end-slotsize)) {
-       end=initialEnd-searchQuant;
-        if (pointer_ge(start,end)) return; /*Ran out of hole*/
-       searchQuant*=2;
-        if (searchQuant==0) return; /*SearchQuant overflowed-- no good memory anywhere*/
-  }
-  
-  len=(memRange_t)end-(memRange_t)start;
-  if (len<max->len) return; /*It's now too short.*/
   
+  /* Check the middle of the range */
+  if (!good_range(start,len,256)) {
+    /* Try to split into subranges: */
+    int i,n=2;
 #if CMK_THREADS_DEBUG
-  CmiPrintf("[%d] Address space at %p - %p is largest\n",CmiMyPe(),start,end);
+    CmiPrintf("[%d] Trying to split bad address space at %p - %p...\n",CmiMyPe(),start,end);
+#endif
+    len=divide_range(len,n);
+    for (i=0;i<n;i++) {
+        char *cur=start+i*len;
+       if (partially_good(cur,len,16))
+          check_range(cur,cur+len,max);
+    }
+    return; /* Hopefully one of the subranges will be any good */
+  }
+  else /* range is good */
+  { 
+#if CMK_THREADS_DEBUG
+    CmiPrintf("[%d] Address space at %p - %p is largest\n",CmiMyPe(),start,end);
 #endif
 
-  /*If we got here, we're the new largest usable range*/
-  max->len=len;
-  max->start=start;
-  max->type="Unused";
+    /*If we got here, we're the new largest usable range*/
+    max->len=len;
+    max->start=start;
+    max->type="Unused";
+  }
 }
 
 /*Find the first available memory region of at least the
@@ -491,7 +538,8 @@ static memRegion_t find_free_region(memRegion_t *used,int nUsed,int atLeast)
   memRegion_t max;
   int i,j;  
 
-  max.len=0;
+  max.start=0; 
+  max.len=atLeast;
   /*Find the largest hole between regions*/
   for (i=0;i<nUsed;i++) {
     /*Consider a hole starting at the end of region i*/
@@ -512,35 +560,26 @@ static memRegion_t find_free_region(memRegion_t *used,int nUsed,int atLeast)
   return max; 
 }
 
-static void init_ranges(char **argv)
-{
-  /*Largest value a signed int can hold*/
-  memRange_t intMax=(((memRange_t)1)<<(sizeof(int)*8-1))-1;
-
-  /*Round slot size up to nearest page size*/
-  slotsize=16*1024;
-  slotsize=(slotsize+CMK_MEMORY_PAGESIZE-1) & ~(CMK_MEMORY_PAGESIZE-1);
-#if CMK_THREADS_DEBUG
-  CmiPrintf("[%d] Using slotsize of %d\n", CmiMyPe(), slotsize);
-#endif
-
-  if (CmiMyRank()==0 && numslots==0)
-  { /* Find the largest unused region of virtual address space */
+/*
+By looking at the address range carefully, try to find 
+the largest usable free region on the machine.
+*/
+static int find_largest_free_region(memRegion_t *destRegion) {
     char *staticData =(char *) __static_data_loc();
-    char *code = (char *)&init_ranges;
-    char *codeDll = (char *)&fclose;
+    char *code = (char *)&find_free_region;
+    char *codeDll = (char *)&errno;
     char *heapLil = (char*) malloc(1);
-    char *heapBig = (char*) malloc(4*1024*1024);
+    char *heapBig = (char*) malloc(6*meg);
     char *stack = (char *)__cur_stack_frame();
+    size_t mmapAnyLen = 1*meg;
+    char *mmapAny = (char*) call_mmap_anywhere(mmapAnyLen);
 
-    memRange_t meg=1024*1024; /*One megabyte*/
-    memRange_t gig=1024*meg; /*One gigabyte*/
-    int i,nRegions=7;
+    int i,nRegions=8;
     memRegion_t regions[10]; /*used portions of address space*/
     memRegion_t freeRegion; /*Largest unused block of address space*/
 
 /*Mark off regions of virtual address space as ususable*/
-    regions[0].type="NULL (inaccessible)";
+    regions[0].type="NULL";
     regions[0].start=NULL; regions[0].len=16u*meg;
     
     regions[1].type="Static program data";
@@ -550,7 +589,7 @@ static void init_ranges(char **argv)
     regions[2].start=code; regions[2].len=256u*meg;
     
     regions[3].type="Heap (small blocks)";
-    regions[3].start=heapLil; regions[3].len=2u*gig;
+    regions[3].start=heapLil; regions[3].len=1u*gig;
     
     regions[4].type="Heap (large blocks)";
     regions[4].start=heapBig; regions[4].len=1u*gig;
@@ -559,64 +598,90 @@ static void init_ranges(char **argv)
     regions[5].start=stack; regions[5].len=256u*meg;
 
     regions[6].type="Program dynamically linked code";
-    regions[6].start=codeDll; regions[6].len=256u*meg;    
+    regions[6].start=codeDll; regions[6].len=256u*meg; 
 
-#ifdef CMK_BAD_MMAP_ADDRESS 
-    regions[nRegions].type="Region to skip from the conv-mach.h file";
-    regions[nRegions].start=(void *)CMK_BAD_MMAP_ADDRESS; regions[nRegions].len=0x10000000u;
-    nRegions++;
-#endif
+    regions[7].type="Result of a non-fixed call to mmap";
+    regions[7].start=mmapAny; regions[7].len=1u*gig; 
 
     _MEMCHECK(heapBig); free(heapBig);
     _MEMCHECK(heapLil); free(heapLil); 
+    call_munmap(mmapAny,mmapAnyLen);
     
     /*Align each memory region*/
     for (i=0;i<nRegions;i++) {
+      memRegion_t old=regions[i];
       memRange_t p=(memRange_t)regions[i].start;
-      p&=~(regions[i].len-1); /*Round down to a len-boundary (mask off low bits)*/
+      p&=~(regions[i].len-1); /*Round start down to a len-boundary (mask off low bits)*/
       regions[i].start=(char *)p;
 #if CMK_THREADS_DEBUG
-      CmiPrintf("[%d] Memory map: %p - %p  %s\n",CmiMyPe(),
-             regions[i].start,regions[i].start+regions[i].len,regions[i].type);
+      CmiPrintf("[%d] Memory map: %p - %p %s (at %p)\n",CmiMyPe(),
+             regions[i].start,regions[i].start+regions[i].len,
+             regions[i].type, old.start);
 #endif
     }
     
-    /*Find a large, unused region*/
+    /*Find a large, unused region in this map: */
     freeRegion=find_free_region(regions,nRegions,(512u)*meg);
     
-    if (freeRegion.len==0) 
+    if (freeRegion.start==0) 
     { /*No free address space-- disable isomalloc:*/
-      disable_isomalloc("no free virtual address space");
+      return 0;
     }
-    else 
+    else /* freeRegion is valid */
     {
-      /*If the unused region is very large, pad it on both ends for safety*/
-      if (freeRegion.len/gig>64u) {
-        freeRegion.start+=16u*gig;
-        freeRegion.len-=20u*gig;
-      }
+      *destRegion=freeRegion;
+      
+      return 1;
+    }
+}
 
+static void init_ranges(char **argv)
+{
+  /*Largest value a signed int can hold*/
+  memRange_t intMax=(((memRange_t)1)<<(sizeof(int)*8-1))-1;
+
+  /*Round slot size up to nearest page size*/
+  slotsize=16*1024;
+  slotsize=(slotsize+CMK_MEMORY_PAGESIZE-1) & ~(CMK_MEMORY_PAGESIZE-1);
 #if CMK_THREADS_DEBUG
-      CmiPrintf("[%d] Largest unused region: %p - %p (%d megs)\n",CmiMyPe(),
-             freeRegion.start,freeRegion.start+freeRegion.len,
-             freeRegion.len/meg);
+  CmiPrintf("[%d] Using slotsize of %d\n", CmiMyPe(), slotsize);
 #endif
 
-      /*Allocate stacks in unused region*/
-      isomallocStart=freeRegion.start;
-      isomallocEnd=freeRegion.start+freeRegion.len;
-
+  if (CmiMyRank()==0 && numslots==0)
+  { /* Find the largest unused region of virtual address space */
+      memRegion_t freeRegion;
+      freeRegion.len=0u;
+#ifdef CMK_MMAP_START_ADDRESS /* Hardcoded start address, for machines where automatic fails */
+      freeRegion.start=CMK_MMAP_START_ADDRESS;
+      freeRegion.len=CMK_MMAP_LENGTH_MEGS*meg;
+#endif
+      if (freeRegion.len==0u) find_largest_free_region(&freeRegion);
+      
       /*Make sure our largest slot number doesn't overflow an int:*/
       if (freeRegion.len/slotsize>intMax)
         freeRegion.len=intMax*slotsize;
-    
-      numslots=(freeRegion.len/slotsize)/CmiNumPes();
-    
+      
+      if (freeRegion.len==0u) {
+        disable_isomalloc("no free virtual address space");
+      }
+      else /* freeRegion.len>0, so can isomalloc */
+      {
+#if CMK_THREADS_DEBUG
+        CmiPrintf("[%d] Isomalloc memory region: %p - %p (%d megs)\n",CmiMyPe(),
+             freeRegion.start,freeRegion.start+freeRegion.len,
+             freeRegion.len/meg);
+#endif
+        
+        /*Isomalloc covers entire unused region*/
+        isomallocStart=freeRegion.start;
+        isomallocEnd=freeRegion.start+freeRegion.len;
+        numslots=(freeRegion.len/slotsize)/CmiNumPes();
+        
 #if CMK_THREADS_DEBUG
-      CmiPrintf("[%d] Can isomalloc up to %lu megs per pe\n",CmiMyPe(),
+        CmiPrintf("[%d] Can isomalloc up to %lu megs per pe\n",CmiMyPe(),
              ((memRange_t)numslots)*slotsize/meg);
 #endif
-    }
+      }
   }
   /*SMP Mode: wait here for rank 0 to initialize numslots so we can set up myss*/
   CmiNodeAllBarrier();