[project @ 2002-10-21 11:38:53 by simonmar]

Bite the bullet and generalise the central memory allocation scheme.
Previously we tried to allocate memory starting from a fixed address,
which was set for each architecture (0x5000000 was a common one), and
to decide whether a particular address was in the heap or not we would
do a simple comparison against this address.

This doesn't work too well, because:

 - if we dynamically-load some objects above the boundary, the
   heap-allocated test becomes invalid

 - on windows we have less control, and the heap might be
   split into multiple sections

 - it turns out that on some Linux kernels we don't get memory where
   we asked for it.  This might be a bug in those kernels, but it
   exposes the fragility of our allocation scheme.

The solution is to bite the bullet and maintain a table mapping
addresses to a value indicating whether that address is in the heap or
not.  Since we normally allocate heap in chunks of 1Mb, the table is
quite small: 4k on a 32-bit machine, using one byte for each 1Mb
block.  Testing an address for heap residency now involves a memory
access, but the table is normally cache-resident.  I didn't manage to
measure any slowdown after making the change.

On a 64-bit machine, we'll need to use a 2-level table; I haven't
implemented that yet.

Now we can generalise the procedure used to grab memory from the OS.
In the general case, we allocate one megablock more than we need to,
and trim off the slop around the allocation to leave an aligned chunk.
The next time around, however, we try to allocate memory right after
the last chunk allocated, on the grounds that it is aligned and
probably free: if this doesn't work, we have to back off to the
general mechanism (it seems to work most of the time).

This cleans up the Windows story too: is_heap_alloced() has gone, and
we should be able to handle more than 256M of memory (or whatever the
arbitrary limit was before).

MERGE TO STABLE (after lots of testing)

1 files changed, 46 insertions, 48 deletions

diff --git a/ghc/rts/MBlock.h b/ghc/rts/MBlock.h
index 40461a0ef6..3845ca43a2 100644
--- a/ghc/rts/MBlock.h
+++ b/ghc/rts/MBlock.h
@@ -1,54 +1,20 @@
 /* -----------------------------------------------------------------------------
- * $Id: MBlock.h,v 1.14 2002/05/14 08:15:49 matthewc Exp $
+ * $Id: MBlock.h,v 1.15 2002/10/21 11:38:54 simonmar Exp $
  *
  * (c) The GHC Team, 1998-1999
  *
  * MegaBlock Allocator interface.
  *
  * ---------------------------------------------------------------------------*/
+
 #ifndef __MBLOCK_H__
 #define __MBLOCK_H__
 extern lnat mblocks_allocated;
 
-#if defined(mingw32_TARGET_OS)
-extern int is_heap_alloced(const void* p);
-#endif
-
 extern void * getMBlock(void);
 extern void * getMBlocks(nat n);
 
-#if freebsd2_TARGET_OS || freebsd_TARGET_OS
-/* Executable is loaded from      0x0
- * Shared libraries are loaded at 0x2000000
- * Stack is at the top of the address space.  The kernel probably owns
- * 0x8000000 onwards, so we'll pick 0x5000000.
- */
-#define HEAP_BASE 0x50000000
-
-#elif netbsd_TARGET_OS
-/* NetBSD i386 shared libs are at 0x40000000
- */
-#define HEAP_BASE 0x50000000
-#elif openbsd_TARGET_OS
-#define HEAP_BASE 0x50000000
-
-#elif linux_TARGET_OS
-#if ia64_TARGET_ARCH
-/* Shared libraries are in region 1, text in region 2, data in region 3.
- * Stack is at the top of region 4.  We use the bottom.
- */
-#define HEAP_BASE (4L<<61)
-#else
-/* Any ideas?
- */
-#define HEAP_BASE 0x50000000
-#endif
-
-#elif solaris2_TARGET_OS
-/* guess */
-#define HEAP_BASE 0x50000000
-
-#elif osf3_TARGET_OS
+#if osf3_TARGET_OS
 /* ToDo: Perhaps by adjusting this value we can make linking without
  * -static work (i.e., not generate a core-dumping executable)? */
 #if SIZEOF_VOID_P == 8
@@ -57,20 +23,52 @@ extern void * getMBlocks(nat n);
 #error I have no idea where to begin the heap on a non-64-bit osf3 machine.
 #endif
 
-#elif hpux_TARGET_OS
-/* guess */
-#define HEAP_BASE 0x50000000
+#else
 
-#elif darwin_TARGET_OS
-/* guess */
-#define HEAP_BASE 0x50000000
+// we're using the generic method
+#define HEAP_BASE 0
 
-#elif defined(mingw32_TARGET_OS) || defined(cygwin32_TARGET_OS)
-/* doesn't matter, we use a reserve/commit algorithm */
+#endif
+
+/* -----------------------------------------------------------------------------
+   The HEAP_ALLOCED() test.
 
+   HEAP_ALLOCED is called FOR EVERY SINGLE CLOSURE during GC.
+   It needs to be FAST.
+
+   Implementation of HEAP_ALLOCED
+   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+   Since heap is allocated in chunks of megablocks (MBLOCK_SIZE), we
+   can just use a table to record which megablocks in the address
+   space belong to the heap.  On a 32-bit machine, with 1Mb
+   megablocks, using 8 bits for each entry in the table, the table
+   requires 4k.  Lookups during GC will be fast, because the table
+   will be quickly cached (indeed, performance measurements showed no
+   measurable difference between doing the table lookup and using a
+   constant comparison).
+   -------------------------------------------------------------------------- */
+
+#if SIZEOF_VOID_P == 4
+
+// This is the table.  Each byte is non-zero if the appropriate MBlock
+// in the address space contains heap.
+extern StgWord8 mblock_map[];
+
+#define HEAP_ALLOCED(p) \
+  ((int)(mblock_map[((StgWord)(p) & ~MBLOCK_MASK) >> MBLOCK_SHIFT]))
+
+#else // SIZEOF_VOID_P != 4
+
+// on a 64-bit machine, we need to extend the above scheme to use a
+// 2-level mapping.  (ToDo)
+
+#ifdef TEXT_BEFORE_HEAP
+# define HEAP_ALLOCED(x)  ((StgPtr)(x) >= (StgPtr)(HEAP_BASE))
 #else
-#error Dont know where to get memory from on this architecture
-/* ToDo: memory locations on other architectures */
+#error HEAP_ALLOCED not defined
 #endif
 
-#endif
+#endif // SIZEOF_VOID_P != 4
+
+#endif // __MBLOCK_H__