+
+/* -----------------------------------------------------------------------------
+ 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).
+ -------------------------------------------------------------------------- */
+
+extern StgWord8 mblock_map[];
+
+#if SIZEOF_VOID_P == 4
+/* On a 32-bit machine a 4KB table is always sufficient */
+# define MBLOCK_MAP_SIZE 4096
+# define MBLOCK_MAP_ENTRY(p) ((StgWord)(p) >> MBLOCK_SHIFT)
+# define HEAP_ALLOCED(p) mblock_map[MBLOCK_MAP_ENTRY(p)]
+# define MARK_HEAP_ALLOCED(p) (mblock_map[MBLOCK_MAP_ENTRY(p)] = 1)
+
+#elif defined(ia64_TARGET_ARCH)
+/* Instead of trying to cover the whole 64-bit address space (which would
+ * require a better data structure), we assume that mmap allocates mappings
+ * from the bottom of region 1, and track some portion of address space from
+ * there upwards (currently 4GB). */
+# define MBLOCK_MAP_SIZE 4096
+# define MBLOCK_MAP_ENTRY(p) (((StgWord)(p) - (1UL << 61)) >> MBLOCK_SHIFT)
+# define HEAP_ALLOCED(p) ((MBLOCK_MAP_ENTRY(p) < MBLOCK_MAP_SIZE) \
+ && mblock_map[MBLOCK_MAP_ENTRY(p)])
+# define MARK_HEAP_ALLOCED(p) ((MBLOCK_MAP_ENTRY(p) < MBLOCK_MAP_SIZE) \
+ && (mblock_map[MBLOCK_MAP_ENTRY(p)] = 1))
+
+#elif SIZEOF_VOID_P == 8
+/* XXX: This is a HACK, and will not work in general! We just use the
+ * lower 32 bits of the address, and do the same as for the 32-bit
+ * version. As long as the OS gives us memory in a roughly linear
+ * fashion, it won't go wrong until we've allocated 4G. */
+# define MBLOCK_MAP_SIZE 4096
+# define MBLOCK_MAP_ENTRY(p) (((StgWord)(p) & 0xffffffff) >> MBLOCK_SHIFT)
+# define HEAP_ALLOCED(p) (mblock_map[MBLOCK_MAP_ENTRY(p)])
+# define MARK_HEAP_ALLOCED(p) (mblock_map[MBLOCK_MAP_ENTRY(p)] = 1)
+
+
+#else
+# error HEAP_ALLOCED not defined
+#endif
+
+#endif // __MBLOCK_H__