- At the beginning of the sweep stage, the conses in the cons
- blocks are in one of three states: in use and marked, in use
- but not marked, and not in use (already freed). Any conses
- that are marked have been marked in the mark stage just
- executed, because as part of the sweep stage we unmark any
- marked objects. The way we tell whether or not a cons cell
- is in use is through the FREE_STRUCT_P macro. This basically
- looks at the first 4 bytes (or however many bytes a pointer
- fits in) to see if all the bits in those bytes are 1. The
- resulting value (0xFFFFFFFF) is not a valid pointer and is
- not a valid Lisp_Object. All current fixed-size types have
- a pointer or Lisp_Object as their first element with the
- exception of strings; they have a size value, which can
- never be less than zero, and so 0xFFFFFFFF is invalid for
- strings as well. Now assuming that a cons cell is in use,
- the way we tell whether or not it is marked is to look at
- the mark bit of its car (each Lisp_Object has one bit
- reserved as a mark bit, in case it's needed). Note that
- different types of objects use different fields to indicate
- whether the object is marked, but the principle is the same.
-
- Conses on the free_cons_list are threaded through a pointer
- stored in the bytes directly after the bytes that are set
- to 0xFFFFFFFF (we cannot overwrite these because the cons
- is still in a cons_block and needs to remain marked as
- not in use for the next time that GC happens). This
- implies that all fixed-size types must be at least big
- enough to store two pointers, which is indeed the case
- for all current fixed-size types.
+ At the beginning of the sweep stage, the conses in the cons blocks
+ are in one of three states: in use and marked, in use but not
+ marked, and not in use (already freed). Any conses that are marked
+ have been marked in the mark stage just executed, because as part
+ of the sweep stage we unmark any marked objects. The way we tell
+ whether or not a cons cell is in use is through the LRECORD_FREE_P
+ macro. This uses a special lrecord type `lrecord_type_free',
+ which is never associated with any valid object.
+
+ Conses on the free_cons_list are threaded through a pointer stored
+ in the conses themselves. Because the cons is still in a
+ cons_block and needs to remain marked as not in use for the next
+ time that GC happens, we need room to store both the "free"
+ indicator and the chaining pointer. So this pointer is stored
+ after the lrecord header (actually where C places a pointer after
+ the lrecord header; they are not necessarily contiguous). This
+ implies that all fixed-size types must be big enough to contain at
+ least one pointer. This is true for all current fixed-size types,
+ with the possible exception of Lisp_Floats, for which we define the
+ meat of the struct using a union of a pointer and a double to
+ ensure adequate space for the free list chain pointer.