rts/sm/MBlock.c

   1 /* -----------------------------------------------------------------------------
   2  *
   3  * (c) The GHC Team 1998-1999
   4  *
   5  * MegaBlock Allocator Interface.  This file contains all the dirty
   6  * architecture-dependent hackery required to get a chunk of aligned
   7  * memory from the operating system.
   8  *
   9  * ---------------------------------------------------------------------------*/
  10
  11 /* This is non-posix compliant. */
  12 /* #include "PosixSource.h" */
  13
  14 #include "Rts.h"
  15 #include "RtsUtils.h"
  16 #include "RtsFlags.h"
  17 #include "MBlock.h"
  18 #include "BlockAlloc.h"
  19 #include "Trace.h"
  20
  21 #ifdef HAVE_STDLIB_H
  22 #include <stdlib.h>
  23 #endif
  24 #ifdef HAVE_STRING_H
  25 #include <string.h>
  26 #endif
  27 #ifdef HAVE_UNISTD_H
  28 #include <unistd.h>
  29 #endif
  30 #ifdef HAVE_SYS_TYPES_H
  31 #include <sys/types.h>
  32 #endif
  33 #ifndef mingw32_HOST_OS
  34 # ifdef HAVE_SYS_MMAN_H
  35 # include <sys/mman.h>
  36 # endif
  37 #endif
  38 #ifdef HAVE_FCNTL_H
  39 #include <fcntl.h>
  40 #endif
  41 #if HAVE_WINDOWS_H
  42 #include <windows.h>
  43 #endif
  44 #if darwin_HOST_OS
  45 #include <mach/mach.h>
  46 #include <mach/vm_map.h>
  47 #endif
  48
  49 #include <errno.h>
  50
  51 lnat mblocks_allocated = 0;
  52
  53 #if !defined(mingw32_HOST_OS) && !defined(cygwin32_HOST_OS)
  54 static caddr_t next_request = 0;
  55 #endif
  56
  57 void
  58 initMBlocks(void)
  59 {
  60 #if !defined(mingw32_HOST_OS) && !defined(cygwin32_HOST_OS)
  61     next_request = (caddr_t)RtsFlags.GcFlags.heapBase;
  62 #endif
  63 }
  64
  65 /* -----------------------------------------------------------------------------
  66    The MBlock Map: provides our implementation of HEAP_ALLOCED()
  67    -------------------------------------------------------------------------- */
  68
  69 #if SIZEOF_VOID_P == 4
  70 StgWord8 mblock_map[MBLOCK_MAP_SIZE]; // initially all zeros
  71 #elif SIZEOF_VOID_P == 8
  72 static MBlockMap dummy_mblock_map;
  73 MBlockMap *mblock_cache = &dummy_mblock_map;
  74 int mblock_map_count = 0;
  75 MBlockMap **mblock_maps = NULL;
  76
  77 static MBlockMap *
  78 findMBlockMap(void *p)
  79 {
  80     int i;
  81     StgWord32 hi = (StgWord32) (((StgWord)p) >> 32);
  82     for( i = 0; i < mblock_map_count; i++ )
  83     {
  84         if(mblock_maps[i]->addrHigh32 == hi)
  85         {
  86             return mblock_maps[i];
  87         }
  88     }
  89     return NULL;
  90 }
  91
  92 StgBool
  93 slowIsHeapAlloced(void *p)
  94 {
  95     MBlockMap *map = findMBlockMap(p);
  96     if(map)
  97     {
  98         mblock_cache = map;
  99         return map->mblocks[MBLOCK_MAP_ENTRY(p)];
 100     }
 101     else
 102         return 0;
 103 }
 104 #endif
 105
 106 static void
 107 markHeapAlloced(void *p)
 108 {
 109 #if SIZEOF_VOID_P == 4
 110     mblock_map[MBLOCK_MAP_ENTRY(p)] = 1;
 111 #elif SIZEOF_VOID_P == 8
 112     MBlockMap *map = findMBlockMap(p);
 113     if(map == NULL)
 114     {
 115         mblock_map_count++;
 116         mblock_maps = realloc(mblock_maps,
 117                               sizeof(MBlockMap*) * mblock_map_count);
 118         map = mblock_maps[mblock_map_count-1] = calloc(1,sizeof(MBlockMap));
 119         map->addrHigh32 = (StgWord32) (((StgWord)p) >> 32);
 120     }
 121     map->mblocks[MBLOCK_MAP_ENTRY(p)] = 1;
 122     mblock_cache = map;
 123 #endif
 124 }
 125
 126 /* -----------------------------------------------------------------------------
 127    Allocate new mblock(s)
 128    -------------------------------------------------------------------------- */
 129
 130 void *
 131 getMBlock(void)
 132 {
 133   return getMBlocks(1);
 134 }
 135
 136 /* -----------------------------------------------------------------------------
 137    The mmap() method
 138
 139    On Unix-like systems, we use mmap() to allocate our memory.  We
 140    want memory in chunks of MBLOCK_SIZE, and aligned on an MBLOCK_SIZE
 141    boundary.  The mmap() interface doesn't give us this level of
 142    control, so we have to use some heuristics.
 143
 144    In the general case, if we want a block of n megablocks, then we
 145    allocate n+1 and trim off the slop from either side (using
 146    munmap()) to get an aligned chunk of size n.  However, the next
 147    time we'll try to allocate directly after the previously allocated
 148    chunk, on the grounds that this is aligned and likely to be free.
 149    If it turns out that we were wrong, we have to munmap() and try
 150    again using the general method.
 151
 152    Note on posix_memalign(): this interface is available on recent
 153    systems and appears to provide exactly what we want.  However, it
 154    turns out not to be as good as our mmap() implementation, because
 155    it wastes extra space (using double the address space, in a test on
 156    x86_64/Linux).  The problem seems to be that posix_memalign()
 157    returns memory that can be free()'d, so the library must store
 158    extra information along with the allocated block, thus messing up
 159    the alignment.  Hence, we don't use posix_memalign() for now.
 160
 161    -------------------------------------------------------------------------- */
 162
 163 #if !defined(mingw32_HOST_OS) && !defined(cygwin32_HOST_OS)
 164
 165 // A wrapper around mmap(), to abstract away from OS differences in
 166 // the mmap() interface.
 167
 168 static void *
 169 my_mmap (void *addr, lnat size)
 170 {
 171     void *ret;
 172
 173 #if defined(solaris2_HOST_OS) || defined(irix_HOST_OS)
 174     {
 175         int fd = open("/dev/zero",O_RDONLY);
 176         ret = mmap(addr, size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
 177         close(fd);
 178     }
 179 #elif hpux_HOST_OS
 180     ret = mmap(addr, size, PROT_READ | PROT_WRITE,
 181                MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
 182 #elif darwin_HOST_OS
 183     // Without MAP_FIXED, Apple's mmap ignores addr.
 184     // With MAP_FIXED, it overwrites already mapped regions, whic
 185     // mmap(0, ... MAP_FIXED ...) is worst of all: It unmaps the program text
 186     // and replaces it with zeroes, causing instant death.
 187     // This behaviour seems to be conformant with IEEE Std 1003.1-2001.
 188     // Let's just use the underlying Mach Microkernel calls directly,
 189     // they're much nicer.
 190
 191     kern_return_t err;
 192     ret = addr;
 193     if(addr)    // try to allocate at adress
 194         err = vm_allocate(mach_task_self(),(vm_address_t*) &ret, size, FALSE);
 195     if(!addr || err)    // try to allocate anywhere
 196         err = vm_allocate(mach_task_self(),(vm_address_t*) &ret, size, TRUE);
 197
 198     if(err) {
 199         // don't know what the error codes mean exactly, assume it's
 200         // not our problem though.
 201         errorBelch("memory allocation failed (requested %lu bytes)", size);
 202         stg_exit(EXIT_FAILURE);
 203     } else {
 204         vm_protect(mach_task_self(),(vm_address_t)ret,size,FALSE,VM_PROT_READ|VM_PROT_WRITE);
 205     }
 206 #else
 207     ret = mmap(addr, size, PROT_READ | PROT_WRITE | PROT_EXEC,
 208                MAP_ANON | MAP_PRIVATE, -1, 0);
 209 #endif
 210
 211     if (ret == (void *)-1) {
 212         if (errno == ENOMEM ||
 213             (errno == EINVAL && sizeof(void*)==4 && size >= 0xc0000000)) {
 214             // If we request more than 3Gig, then we get EINVAL
 215             // instead of ENOMEM (at least on Linux).
 216             errorBelch("out of memory (requested %lu bytes)", size);
 217             stg_exit(EXIT_FAILURE);
 218         } else {
 219             barf("getMBlock: mmap: %s", strerror(errno));
 220         }
 221     }
 222
 223     return ret;
 224 }
 225
 226 // Implements the general case: allocate a chunk of memory of 'size'
 227 // mblocks.
 228
 229 static void *
 230 gen_map_mblocks (lnat size)
 231 {
 232     int slop;
 233     void *ret;
 234
 235     // Try to map a larger block, and take the aligned portion from
 236     // it (unmap the rest).
 237     size += MBLOCK_SIZE;
 238     ret = my_mmap(0, size);
 239
 240     // unmap the slop bits around the chunk we allocated
 241     slop = (W_)ret & MBLOCK_MASK;
 242
 243     if (munmap(ret, MBLOCK_SIZE - slop) == -1) {
 244       barf("gen_map_mblocks: munmap failed");
 245     }
 246     if (slop > 0 && munmap(ret+size-slop, slop) == -1) {
 247       barf("gen_map_mblocks: munmap failed");
 248     }
 249
 250     // ToDo: if we happened to get an aligned block, then don't
 251     // unmap the excess, just use it. For this to work, you
 252     // need to keep in mind the following:
 253     //     * Calling my_mmap() with an 'addr' arg pointing to
 254     //       already my_mmap()ed space is OK and won't fail.
 255     //     * If my_mmap() can't satisfy the request at the
 256     //       given 'next_request' address in getMBlocks(), that
 257     //       you unmap the extra mblock mmap()ed here (or simply
 258     //       satisfy yourself that the slop introduced isn't worth
 259     //       salvaging.)
 260     //
 261
 262     // next time, try after the block we just got.
 263     ret += MBLOCK_SIZE - slop;
 264     return ret;
 265 }
 266
 267
 268 // The external interface: allocate 'n' mblocks, and return the
 269 // address.
 270
 271 void *
 272 getMBlocks(nat n)
 273 {
 274   caddr_t ret;
 275   lnat size = MBLOCK_SIZE * n;
 276   nat i;
 277
 278   if (next_request == 0) {
 279       // use gen_map_mblocks the first time.
 280       ret = gen_map_mblocks(size);
 281   } else {
 282       ret = my_mmap(next_request, size);
 283
 284       if (((W_)ret & MBLOCK_MASK) != 0) {
 285           // misaligned block!
 286 #if 0 // defined(DEBUG)
 287           errorBelch("warning: getMBlock: misaligned block %p returned when allocating %d megablock(s) at %p", ret, n, next_request);
 288 #endif
 289
 290           // unmap this block...
 291           if (munmap(ret, size) == -1) {
 292               barf("getMBlock: munmap failed");
 293           }
 294           // and do it the hard way
 295           ret = gen_map_mblocks(size);
 296       }
 297   }
 298
 299   // Next time, we'll try to allocate right after the block we just got.
 300   // ToDo: check that we haven't already grabbed the memory at next_request
 301   next_request = ret + size;
 302
 303   debugTrace(DEBUG_gc, "allocated %d megablock(s) at %p",n,ret);
 304
 305   // fill in the table
 306   for (i = 0; i < n; i++) {
 307       markHeapAlloced( ret + i * MBLOCK_SIZE );
 308   }
 309
 310   mblocks_allocated += n;
 311
 312   return ret;
 313 }
 314
 315 void
 316 freeAllMBlocks(void)
 317 {
 318   /* XXX Do something here */
 319 }
 320
 321 #else /* defined(mingw32_HOST_OS) || defined(cygwin32_HOST_OS) */
 322
 323 /* alloc_rec keeps the info we need to have matching VirtualAlloc and
 324    VirtualFree calls.
 325 */
 326 typedef struct alloc_rec_ {
 327     char* base;     /* non-aligned base address, directly from VirtualAlloc */
 328     int size;       /* Size in bytes */
 329     struct alloc_rec_* next;
 330 } alloc_rec;
 331
 332 typedef struct block_rec_ {
 333     char* base;         /* base address, non-MBLOCK-aligned */
 334     int size;           /* size in bytes */
 335     struct block_rec_* next;
 336 } block_rec;
 337
 338 static alloc_rec* allocs = 0;
 339 static block_rec* free_blocks = 0;
 340
 341 static
 342 alloc_rec*
 343 allocNew(nat n) {
 344     alloc_rec* rec;
 345     rec = (alloc_rec*)stgMallocBytes(sizeof(alloc_rec),"getMBlocks: allocNew");
 346     rec->size = (n+1)*MBLOCK_SIZE;
 347     rec->base =
 348         VirtualAlloc(NULL, rec->size, MEM_RESERVE, PAGE_READWRITE);
 349     if(rec->base==0) {
 350         stgFree((void*)rec);
 351         rec=0;
 352         if (GetLastError() == ERROR_NOT_ENOUGH_MEMORY) {
 353
 354             errorBelch("out of memory");
 355         } else {
 356             sysErrorBelch(
 357                 "getMBlocks: VirtualAlloc MEM_RESERVE %d blocks failed", n);
 358         }
 359     } else {
 360                 alloc_rec temp;
 361                 temp.base=0; temp.size=0; temp.next=allocs;
 362
 363         alloc_rec* it;
 364         it=&temp;
 365         for(; it->next!=0 && it->next->base<rec->base; it=it->next) ;
 366         rec->next=it->next;
 367         it->next=rec;
 368
 369                 allocs=temp.next;
 370         debugTrace(DEBUG_gc, "allocated %d megablock(s) at 0x%x",n,(nat)rec->base);
 371     }
 372     return rec;
 373 }
 374
 375 static
 376 void
 377 insertFree(char* alloc_base, int alloc_size) {
 378     block_rec temp;
 379     block_rec* it;
 380     block_rec* prev;
 381
 382     temp.base=0; temp.size=0; temp.next=free_blocks;
 383     it = free_blocks;
 384     prev = &temp;
 385     for( ; it!=0 && it->base<alloc_base; prev=it, it=it->next) {}
 386
 387     if(it!=0 && alloc_base+alloc_size == it->base) {
 388         if(prev->base + prev->size == alloc_base) {        /* Merge it, alloc, prev */
 389             prev->size += alloc_size + it->size;
 390             prev->next = it->next;
 391             stgFree(it);
 392         } else {                                            /* Merge it, alloc */
 393             it->base = alloc_base;
 394             it->size += alloc_size;
 395         }
 396     } else if(prev->base + prev->size == alloc_base) {     /* Merge alloc, prev */
 397         prev->size += alloc_size;
 398     } else {                                                /* Merge none */
 399         block_rec* rec;
 400         rec = (block_rec*)stgMallocBytes(sizeof(block_rec),"getMBlocks: insertFree");
 401         rec->base=alloc_base;
 402         rec->size=alloc_size;
 403         rec->next = it;
 404         prev->next=rec;
 405     }
 406     free_blocks=temp.next;
 407 }
 408
 409 static
 410 void*
 411 findFreeBlocks(nat n) {
 412     void* ret=0;
 413     block_rec* it;
 414     block_rec temp;
 415     block_rec* prev;
 416
 417     int required_size;
 418     it=free_blocks;
 419     required_size = n*MBLOCK_SIZE;
 420     temp.next=free_blocks; temp.base=0; temp.size=0;
 421     prev=&temp;
 422     /* TODO: Don't just take first block, find smallest sufficient block */
 423     for( ; it!=0 && it->size<required_size; prev=it, it=it->next ) {}
 424     if(it!=0) {
 425         if( (((unsigned long)it->base) & MBLOCK_MASK) == 0) { /* MBlock aligned */
 426             ret = (void*)it->base;
 427             if(it->size==required_size) {
 428                 prev->next=it->next;
 429                 stgFree(it);
 430             } else {
 431                 it->base += required_size;
 432                 it->size -=required_size;
 433             }
 434         } else {
 435             char* need_base;
 436             block_rec* next;
 437             int new_size;
 438             need_base = (char*)(((unsigned long)it->base) & ((unsigned long)~MBLOCK_MASK)) + MBLOCK_SIZE;
 439             next = (block_rec*)stgMallocBytes(
 440                     sizeof(block_rec)
 441                     , "getMBlocks: findFreeBlocks: splitting");
 442             new_size = need_base - it->base;
 443             next->base = need_base +required_size;
 444             next->size = it->size - (new_size+required_size);
 445             it->size = new_size;
 446             next->next = it->next;
 447             it->next = next;
 448             ret=(void*)need_base;
 449         }
 450     }
 451     free_blocks=temp.next;
 452     return ret;
 453 }
 454
 455 /* VirtualAlloc MEM_COMMIT can't cross boundaries of VirtualAlloc MEM_RESERVE,
 456    so we might need to do many VirtualAlloc MEM_COMMITs.  We simply walk the
 457    (ordered) allocated blocks. */
 458 static void
 459 commitBlocks(char* base, int size) {
 460     alloc_rec* it;
 461     it=allocs;
 462     for( ; it!=0 && (it->base+it->size)<=base; it=it->next ) {}
 463     for( ; it!=0 && size>0; it=it->next ) {
 464         int size_delta;
 465         void* temp;
 466         size_delta = it->size - (base-it->base);
 467         if(size_delta>size) size_delta=size;
 468         temp = VirtualAlloc(base, size_delta, MEM_COMMIT, PAGE_READWRITE);
 469         if(temp==0) {
 470             sysErrorBelch("getMBlocks: VirtualAlloc MEM_COMMIT failed");
 471             stg_exit(EXIT_FAILURE);
 472         }
 473         size-=size_delta;
 474         base+=size_delta;
 475     }
 476 }
 477
 478 void *
 479 getMBlocks(nat n) {
 480     void* ret;
 481     ret = findFreeBlocks(n);
 482     if(ret==0) {
 483         alloc_rec* alloc;
 484         alloc = allocNew(n);
 485         /* We already belch in allocNew if it fails */
 486         if (alloc == 0) {
 487             stg_exit(EXIT_FAILURE);
 488         } else {
 489             insertFree(alloc->base, alloc->size);
 490             ret = findFreeBlocks(n);
 491         }
 492     }
 493
 494     if(ret!=0) {
 495         /* (In)sanity tests */
 496         if (((W_)ret & MBLOCK_MASK) != 0) {
 497             barf("getMBlocks: misaligned block returned");
 498         }
 499
 500         commitBlocks(ret, MBLOCK_SIZE*n);
 501
 502         /* Global bookkeeping */
 503         mblocks_allocated += n;
 504         int i;
 505         for(i=0; i<(int)n; ++i) {
 506             markHeapAlloced( ret + i * MBLOCK_SIZE );
 507         }
 508     }
 509
 510     return ret;
 511 }
 512
 513 void
 514 freeAllMBlocks(void)
 515 {
 516     {
 517         block_rec* next;
 518         block_rec* it;
 519         next=0;
 520         it = free_blocks;
 521         for(; it!=0; ) {
 522             next = it->next;
 523             stgFree(it);
 524             it=next;
 525         }
 526     }
 527     {
 528         alloc_rec* next;
 529         alloc_rec* it;
 530         next=0;
 531         it=allocs;
 532         for(; it!=0; ) {
 533             if(!VirtualFree((void*)it->base, 0, MEM_RELEASE)) {
 534                 sysErrorBelch("freeAllMBlocks: VirtualFree MEM_RELEASE failed");
 535                 stg_exit(EXIT_FAILURE);
 536             }
 537             next = it->next;
 538             stgFree(it);
 539             it=next;
 540         }
 541     }
 542 }
 543
 544 #endif