rev 33 - trunk/gc
jimb at sanpietro.red-bean.com
jimb at sanpietro.red-bean.com
Mon Aug 4 06:20:09 CDT 2003
Author: jimb
Date: 2003-08-04 06:20:05 -0500 (Mon, 04 Aug 2003)
New Revision: 33
Modified:
trunk/gc/generic-map.h
Log:
* gc/generic-map.h: Make this architecture-generic; let an
arch-specific header file provide parameters for the details.
Modified: trunk/gc/generic-map.h
===================================================================
--- trunk/gc/generic-map.h 2003-08-02 21:23:31 UTC (rev 32)
+++ trunk/gc/generic-map.h 2003-08-04 11:20:05 UTC (rev 33)
@@ -1,8 +1,8 @@
-/* map.h --- tracking GC'd memory
+/* generic-map.h --- tracking GC'd memory, given per-arch parameters
Jim Blandy <jimb at red-bean.com> --- July 2003 */
-#ifndef MINOR_GC_MAP_H
-#define MINOR_GC_MAP_H
+#ifndef MINOR_GC_GENERIC_MAP_H
+#define MINOR_GC_GENERIC_MAP_H
/* The GC map is a table mapping every heap object's address onto a
gc_page structure describing the page the object lives in.
@@ -132,14 +132,76 @@
synchronization when building them.
- Since mutator threads never access the GC map directly, we don't
- have to worry about synchronization when accessing it, either. */
+ have to worry about synchronization when accessing it, either.
-/* For every 4kb page managed by the garbage collector, we have an
+ Architecture Parameters ==========================================
+
+ The GC map data structure defined here is meant to be useable by
+ many different architectures. Rather than #including this file
+ directly, you should first #include a header file (traditionally
+ named gc-map.h) from the appropriate arch/FOO/gc directory, which
+ will #define some parameters, and then #include this file for you.
+ Here are the parameters the arch-specific gc-map.h file should
+ #define:
+
+ GC_MAP_LOG_OBJECT_ALIGN --- the log base 2 of the minimum alignment
+ for every object. For example, if every object must be aligned on
+ an eight-byte boundary, this would be 3.
+
+ GC_MAP_LOG_NUM_GENERATIONS --- the log base 2 of the number of
+ generations we support, including the nursery and the immortal
+ generation. This must not be greater than GC_MAP_LOG_OBJECT_ALIGN,
+ for bit-packing reasons; see "premature optimization", below.
+
+ GC_MAP_LOG_PAGE_SIZE --- the log base 2 of the number of bytes per
+ page on the system. By "page", what we really mean is the minimum
+ required alignment of the data and code segments, according to the
+ ABI. Choosing that as the page size helps us ensure that the heap
+ areas of two different executable / shared library ELF files will
+ never fall in the purview of the same gc_page structure.
+
+ GC_MAP_FIRST_LEVEL_BITS --- the number of bits to take from the
+ most significant end of the address to use as the index into the
+ top-level array.
+
+ GC_MAP_SECOND_LEVEL_BITS --- the number of bits to take from the
+ most significant end of the address, after the chunk for the
+ top-level index, to use as the index into the second-level array.
+
+ GC_MAP_ADDRESS_BITS --- the total number of bits in an address.
+ This must be GC_MAP_LOG_PAGE_SIZE + GC_MAP_FIRST_LEVEL_BITS
+ + GC_MAP_SECOND_LEVEL_BITS; it's just present as a checksum.
+
+ (To support systems with 64-bit addresses, we could have optional
+ GC_MAP_{THIRD,FOURTH}_LEVEL_BITS macros, whose presence would
+ request the creation of a deeper tree. Or perhaps someone can come
+ up with something more clever.) */
+
+#ifndef GC_MAP_LOG_PAGE_SIZE
+#error "must #include a processor-specific gc-map.h before generic-map.h"
+#endif
+
+#if GC_MAP_LOG_NUM_GENERATIONS > GC_MAP_LOG_OBJECT_ALIGN
+#error "generation count too large for object alignment"
+#endif
+
+#if (GC_MAP_ADDRESS_BITS \
+ != (GC_MAP_FIRST_LEVEL_BITS \
+ + GC_MAP_SECOND_LEVEL_BITS \
+ + GC_MAP_LOG_PAGE_SIZE))
+#error "address not subdivided properly"
+#endif
+
+#define GC_MAP_NUM_GENERATIONS (1 << GC_MAP_LOG_NUM_GENERATIONS)
+
+
+/* For every page managed by the garbage collector, we have an
instance of the following structure.
(Since there is an instance of this structure for every page, it
- needs to be kept small. 8b : 4kb :: 1 : 512.)
+ needs to be kept small. If GC_MAP_LOG_PAGE_SIZE is 12, then 8b :
+ 4kb :: 1 : 512.)
From the "premature optimization is the root of all evil" dept:
@@ -153,7 +215,8 @@
But note that a lot of fields in this struct are indices within a
page, or portions of page addresses. So the first thing we're
going to do with such values is shift them left again, to multiply
- by 8 (for first_doting_object and last_doting_object) or by 4k (for
+ by 1 << GC_MAP_LOG_OBJECT_ALIGN (for first_doting_object and
+ last_doting_object) or by 1 << GC_MAP_LOG_PAGE_SIZE (for
next_doting_page and next_generation_page). So the compiler could
combine the right shift of the field fetch and the left shift of
the multiply into a single operation, net left or net right.
@@ -170,70 +233,87 @@
address word, things fit together pretty nicely. */
struct gc_page
{
- /* The following three fields should all pack into a single 32-bit
- word. */
+ /* The following three fields should all pack into a single
+ address-sized word. */
/* The generation to which the objects in this page belong. Zero is
the youngest generation. Seven is the "dummy generation", used
for memory areas we haven't allocated a separate gc_page
arary for yet. */
- unsigned generation : 3;
+ unsigned generation : GC_MAP_LOG_NUM_GENERATIONS;
+ /* Make sure next bitfield is nicely aligned. */
+ int : GC_MAP_LOG_OBJECT_ALIGN - GC_MAP_LOG_NUM_GENERATIONS;
+
/* If this is a doting page, this is the offset within this page of
the start of the first doting object that begins on this page ---
- divided by eight. If this is not a doting page, then
- last_doting_object == 0 and first_doting_object > 0.
+ divided by 1 << GC_MAP_LOG_OBJECT_ALIGN. To find all the doting
+ pointers, we start here and scan until last_doting_object. If
+ this is not a doting page, then last_doting_object == 0 and
+ first_doting_object > 0. */
+ unsigned first_doting_object
+ : GC_MAP_LOG_PAGE_SIZE - GC_MAP_LOG_OBJECT_ALIGN;
- 4k / 8 == 512, so we need nine bits for this field. To find all
- the doting pointers, we start here and scan until
- last_doting_object. */
- unsigned first_doting_object : 9;
-
/* All the pages that contain doting objects are kept in a
singly-linked list; there is one list per generation. This field
is the link in that list: the address of the next such page in
- this generation, divided by 4k. For the last page in the chain,
- this field is zero. */
- unsigned next_doting_page : 20;
+ this generation, divided by 1 << GC_MAP_LOG_PAGE_SIZE. For the
+ last page in the chain, this field is zero. */
+ unsigned next_doting_page : GC_MAP_ADDRESS_BITS - GC_MAP_LOG_PAGE_SIZE;
- /* The following three fields should all pack into a single 32-bit
- word. */
+ /* The following three fields should all pack into a single
+ address-sized word. */
/* Unused bits! */
- unsigned : 3;
+ unsigned : GC_MAP_LOG_OBJECT_ALIGN;
/* If this is a doting page, this is the offset within this page of
the start of the last doting object that begins on this page ---
- divided by eight. If this is not a doting page, then this is
- zero. */
- unsigned last_doting_object : 9;
+ divided by 1 << GC_MAP_LOG_OBJECT_ALIGN. If this is not a doting
+ page, then this is zero. */
+ unsigned last_doting_object
+ : GC_MAP_LOG_PAGE_SIZE - GC_MAP_LOG_OBJECT_ALIGN;
/* All the pages in a generation are kept in a singly-linked list.
All free pages are kept in a list, too. This is the link in
those lists. This is the address of the next page in the list
- --- divided by 4k. If this is the last page in the list, this is
- zero. */
- unsigned next_generation_page : 20;
+ --- divided by 1 << GC_MAP_LOG_PAGE_SIZE. If this is the last
+ page in the list, this is zero. */
+ unsigned next_generation_page : GC_MAP_ADDRESS_BITS - GC_MAP_LOG_PAGE_SIZE;
};
-/* The map of all pages is a two-level tree. Given a 32-bit address
- ADDR, the 'struct gc_page' for that page is:
+#define GC_MAP_FIRST_LEVEL_SHIFT \
+ (GC_MAP_ADDRESS_BITS - GC_MAP_FIRST_LEVEL_BITS)
+#define GC_MAP_FIRST_LEVEL_MASK \
+ ((1 << GC_MAP_FIRST_LEVEL_BITS) - 1)
- mn__gc_map[(ADDR >> 22) & 0x3ff][(ADDR >> 12) & 0x3ff]
+#define GC_MAP_SECOND_LEVEL_SHIFT \
+ (GC_MAP_ADDRESS_BITS - GC_MAP_FIRST_LEVEL_BITS - GC_MAP_SECOND_LEVEL_BITS)
+#define GC_MAP_SECOND_LEVEL_MASK \
+ ((1 << GC_MAP_SECOND_LEVEL_BITS) - 1)
- In other words, we use the top ten bits of the object's address to
- index the top-level array, yielding a pointer to a second-level
- array; then we use the next ten bits to index into that array,
- yielding a gc_page structure for a particular page.
+/* The map of all pages is a two-level tree. Given an address ADDR,
+ the 'struct gc_page' for that page is:
+
+ mn__gc_map
+ [(ADDR >> GC_MAP_FIRST_LEVEL_SHIFT) & GC_MAP_FIRST_LEVEL_MASK]
+ [(ADDR >> GC_MAP_SECOND_LEVEL_SHIFT) & GC_MAP_SECOND_LEVEL_MASK]
+
+ In other words, we use the top clump of bits of the object's
+ address to index the top-level array, yielding a pointer to a
+ second-level array; then we use the next clump bits to index into
+ that array, yielding a gc_page structure for a particular page.
+
Initially, before we've allocated any heap pages at all, every
- entry in mn__gc_map points to the same second-level array
- object: mn__gc_immortal_pages. This creates the appearance of a
- fully populated tree, with a gc_page struct for every 4k
- page in the IA-32's 32-bit address space --- even though
- mn__gc_map and mn__gc_immortal_pages occupy only 1k * 4b +
- 1k * 8b == 12kb.
+ entry in mn__gc_map points to the same second-level array object:
+ mn__gc_immortal_pages. This creates the appearance of a fully
+ populated tree, with a gc_page struct for every page in the address
+ space --- even though mn__gc_map and mn__gc_immortal_pages occupy
+ only ((1 << GC_MAP_FIRST_LEVEL_BITS) * sizeof (a pointer)
+ + (1 << GC_MAP_SECOND_LEVEL_BITS) * sizeof (struct gc_map))
+ which is 12kb on a typical 32-bit system.
As we allocate pages for newly allocated objects, or for to-spaces
during collection, we need to record these allocations in the map.
@@ -274,7 +354,7 @@
Thus, the default gc_page struct looks like this:
{
- generation = 7,
+ generation = GC_MAP_NUM_GENERATIONS - 1,
first_doting_object = 1,
next_doting_page = 0,
last_doting_object = 0,
@@ -309,29 +389,32 @@
without interleaving other sections. So we don't have to worry
about intra-exec or intra-shared library interleavings.
- - The IA-32 ABI requires that ELF load segments be aligned on 4kb
- page boundaries. This means that two non-empty data segments
- can't appear on the same page. So we don't have to worry about
- inter-executable or inter-shared library interleavings, either.
+ - We choose GC_MAP_LOG_PAGE_SIZE so that the ABI requires that ELF
+ load segments be aligned at least on page boundaries. This means
+ that two non-empty data segments can't appear on the same page.
+ So we don't have to worry about inter-executable or inter-shared
+ library interleavings, either.
- Using the oldest generation, generation 7, as the "immortal"
- generation means that the collector's test for whether to scavenge
- an object doesn't need a special case to recognize immortal
- objects. The obvious way to write the test, "Is this object's
- generation less than or equal to the oldest generation we're
- collecting?" will correctly decline to traverse immortal objects.
- Since the collector asks this of every object it touches, it's
- important for this test to be fast. */
-extern struct gc_page *mn__gc_map[1 << 10];
+ Using the oldest generation as the "immortal" generation means that
+ the collector's test for whether to scavenge an object doesn't need
+ a special case to recognize immortal objects. The obvious way to
+ write the test, "Is this object's generation less than or equal to
+ the oldest generation we're collecting?" will correctly decline to
+ traverse immortal objects. Since the collector asks this of every
+ object it touches, it's important for this test to be fast. */
+extern struct gc_page *mn__gc_map[1 << GC_MAP_FIRST_LEVEL_BITS];
/* The array of immortal pages. */
-extern struct gc_page mn__gc_immortal_pages[1 << 10];
+extern struct gc_page mn__gc_immortal_pages[1 << GC_MAP_SECOND_LEVEL_BITS];
/* The 'struct gc_page' object for ADDR. */
#define GC_PAGE(addr) \
- (mn__gc_map[((unsigned int) (addr) >> 22) & 0x3ff] \
- [((unsigned int) (addr) >> 12) & 0x3ff])
+ (mn__gc_map \
+ [((unsigned int) (addr) >> GC_MAP_FIRST_LEVEL_SHIFT) \
+ & GC_MAP_FIRST_LEVEL_MASK] \
+ [((unsigned int) (addr) >> GC_MAP_SECOND_LEVEL_SHIFT) \
+ & GC_MAP_SECOND_LEVEL_SHIFT])
/* A single heap generation. */
@@ -353,9 +436,9 @@
/* The table of all generations. Generation zero is the youngest
- generation. Generation 7 is the immortal generation, for pages in
- executables and shared libraries (actually, for any page we didn't
- allocate ourselves). */
-extern struct gc_generation mn__gc_generations[8];
+ generation. Generation GC_MAP_NUM_GENERATIONS - 1 is the immortal
+ generation, for pages in executables and shared libraries
+ (actually, for any page we didn't allocate ourselves). */
+extern struct gc_generation mn__gc_generations[GC_MAP_NUM_GENERATIONS];
-#endif /* MINOR_GC_MAP_H */
+#endif /* MINOR_GC_GENERIC_MAP_H */
More information about the Minor
mailing list