+signals, as for example the ones raised by every `QUIT'-macro triggered
+after pressing Ctrl-g.
+
+\1f
+File: internals.info, Node: garbage_collect_1, Next: mark_object, Prev: Invocation, Up: Garbage Collection - Step by Step
+
+`garbage_collect_1'
+-------------------
+
+ We can now describe exactly what happens after the invocation takes
+place.
+ 1. There are several cases in which the garbage collector is left
+ immediately: when we are already garbage collecting
+ (`gc_in_progress'), when the garbage collection is somehow
+ forbidden (`gc_currently_forbidden'), when we are currently
+ displaying something (`in_display') or when we are preparing for
+ the armageddon of the whole system (`preparing_for_armageddon').
+
+ 2. Next the correct frame in which to put all the output occurring
+ during garbage collecting is determined. In order to be able to
+ restore the old display's state after displaying the message, some
+ data about the current cursor position has to be saved. The
+ variables `pre_gc_cursor' and `cursor_changed' take care of that.
+
+ 3. The state of `gc_currently_forbidden' must be restored after the
+ garbage collection, no matter what happens during the process. We
+ accomplish this by `record_unwind_protect'ing the suitable function
+ `restore_gc_inhibit' together with the current value of
+ `gc_currently_forbidden'.
+
+ 4. If we are concurrently running an interactive xemacs session, the
+ next step is simply to show the garbage collector's cursor/message.
+
+ 5. The following steps are the intrinsic steps of the garbage
+ collector, therefore `gc_in_progress' is set.
+
+ 6. For debugging purposes, it is possible to copy the current C stack
+ frame. However, this seems to be a currently unused feature.
+
+ 7. Before actually starting to go over all live objects, references to
+ objects that are no longer used are pruned. We only have to do
+ this for events (`clear_event_resource') and for specifiers
+ (`cleanup_specifiers').
+
+ 8. Now the mark phase begins and marks all accessible elements. In
+ order to start from all slots that serve as roots of
+ accessibility, the function `mark_object' is called for each root
+ individually to go out from there to mark all reachable objects.
+ All roots that are traversed are shown in their processed order:
+ * all constant symbols and static variables that are registered
+ via `staticpro' in the dynarr `staticpros'. *Note Adding
+ Global Lisp Variables::.
+
+ * all Lisp objects that are created in C functions and that
+ must be protected from freeing them. They are registered in
+ the global list `gcprolist'. *Note GCPROing::.
+
+ * all local variables (i.e. their name fields `symbol' and old
+ values `old_values') that are bound during the evaluation by
+ the Lisp engine. They are stored in `specbinding' structs
+ pushed on a stack called `specpdl'. *Note Dynamic Binding;
+ The specbinding Stack; Unwind-Protects::.
+
+ * all catch blocks that the Lisp engine encounters during the
+ evaluation cause the creation of structs `catchtag' inserted
+ in the list `catchlist'. Their tag (`tag') and value (`val'
+ fields are freshly created objects and therefore have to be
+ marked. *Note Catch and Throw::.
+
+ * every function application pushes new structs `backtrace' on
+ the call stack of the Lisp engine (`backtrace_list'). The
+ unique parts that have to be marked are the fields for each
+ function (`function') and all their arguments (`args').
+ *Note Evaluation::.
+
+ * all objects that are used by the redisplay engine that must
+ not be freed are marked by a special function called
+ `mark_redisplay' (in `redisplay.c').
+
+ * all objects created for profiling purposes are allocated by C
+ functions instead of using the lisp allocation mechanisms. In
+ order to receive the right ones during the sweep phase, they
+ also have to be marked manually. That is done by the function
+ `mark_profiling_info'
+
+ 9. Hash tables in XEmacs belong to a kind of special objects that
+ make use of a concept often called 'weak pointers'. To make a
+ long story short, these kind of pointers are not followed during
+ the estimation of the live objects during garbage collection. Any
+ object referenced only by weak pointers is collected anyway, and
+ the reference to it is cleared. In hash tables there are different
+ usage patterns of them, manifesting in different types of hash
+ tables, namely 'non-weak', 'weak', 'key-weak' and 'value-weak'
+ (internally also 'key-car-weak' and 'value-car-weak') hash tables,
+ each clearing entries depending on different conditions. More
+ information can be found in the documentation to the function
+ `make-hash-table'.
+
+ Because there are complicated dependency rules about when and what
+ to mark while processing weak hash tables, the standard `marker'
+ method is only active if it is marking non-weak hash tables. As
+ soon as a weak component is in the table, the hash table entries
+ are ignored while marking. Instead their marking is done each
+ separately by the function `finish_marking_weak_hash_tables'. This
+ function iterates over each hash table entry `hentries' for each
+ weak hash table in `Vall_weak_hash_tables'. Depending on the type
+ of a table, the appropriate action is performed. If a table is
+ acting as `HASH_TABLE_KEY_WEAK', and a key already marked,
+ everything reachable from the `value' component is marked. If it is
+ acting as a `HASH_TABLE_VALUE_WEAK' and the value component is
+ already marked, the marking starts beginning only from the `key'
+ component. If it is a `HASH_TABLE_KEY_CAR_WEAK' and the car of
+ the key entry is already marked, we mark both the `key' and
+ `value' components. Finally, if the table is of the type
+ `HASH_TABLE_VALUE_CAR_WEAK' and the car of the value components is
+ already marked, again both the `key' and the `value' components
+ get marked.
+
+ Again, there are lists with comparable properties called weak
+ lists. There exist different peculiarities of their types called
+ `simple', `assoc', `key-assoc' and `value-assoc'. You can find
+ further details about them in the description to the function
+ `make-weak-list'. The scheme of their marking is similar: all weak
+ lists are listed in `Qall_weak_lists', therefore we iterate over
+ them. The marking is advanced until we hit an already marked pair.
+ Then we know that during a former run all the rest has been marked
+ completely. Again, depending on the special type of the weak list,
+ our jobs differ. If it is a `WEAK_LIST_SIMPLE' and the elem is
+ marked, we mark the `cons' part. If it is a `WEAK_LIST_ASSOC' and
+ not a pair or a pair with both marked car and cdr, we mark the
+ `cons' and the `elem'. If it is a `WEAK_LIST_KEY_ASSOC' and not a
+ pair or a pair with a marked car of the elem, we mark the `cons'
+ and the `elem'. Finally, if it is a `WEAK_LIST_VALUE_ASSOC' and
+ not a pair or a pair with a marked cdr of the elem, we mark both
+ the `cons' and the `elem'.
+
+ Since, by marking objects in reach from weak hash tables and weak
+ lists, other objects could get marked, this perhaps implies
+ further marking of other weak objects, both finishing functions
+ are redone as long as yet unmarked objects get freshly marked.
+
+ 10. After completing the special marking for the weak hash tables and
+ for the weak lists, all entries that point to objects that are
+ going to be swept in the further process are useless, and
+ therefore have to be removed from the table or the list.
+
+ The function `prune_weak_hash_tables' does the job for weak hash
+ tables. Totally unmarked hash tables are removed from the list
+ `Vall_weak_hash_tables'. The other ones are treated more carefully
+ by scanning over all entries and removing one as soon as one of
+ the components `key' and `value' is unmarked.
+
+ The same idea applies to the weak lists. It is accomplished by
+ `prune_weak_lists': An unmarked list is pruned from
+ `Vall_weak_lists' immediately. A marked list is treated more
+ carefully by going over it and removing just the unmarked pairs.
+
+ 11. The function `prune_specifiers' checks all listed specifiers held
+ in `Vall_specifiers' and removes the ones from the lists that are
+ unmarked.
+
+ 12. All syntax tables are stored in a list called
+ `Vall_syntax_tables'. The function `prune_syntax_tables' walks
+ through it and unlinks the tables that are unmarked.
+
+ 13. Next, we will attack the complete sweeping - the function
+ `gc_sweep' which holds the predominance.
+
+ 14. First, all the variables with respect to garbage collection are
+ reset. `consing_since_gc' - the counter of the created cells since
+ the last garbage collection - is set back to 0, and
+ `gc_in_progress' is not `true' anymore.
+
+ 15. In case the session is interactive, the displayed cursor and
+ message are removed again.
+
+ 16. The state of `gc_inhibit' is restored to the former value by
+ unwinding the stack.
+
+ 17. A small memory reserve is always held back that can be reached by
+ `breathing_space'. If nothing more is left, we create a new reserve
+ and exit.
+
+\1f
+File: internals.info, Node: mark_object, Next: gc_sweep, Prev: garbage_collect_1, Up: Garbage Collection - Step by Step
+
+`mark_object'
+-------------
+
+ The first thing that is checked while marking an object is whether
+the object is a real Lisp object `Lisp_Type_Record' or just an integer
+or a character. Integers and characters are the only two types that are
+stored directly - without another level of indirection, and therefore
+they don't have to be marked and collected. *Note How Lisp Objects Are
+Represented in C::.
+
+ The second case is the one we have to handle. It is the one when we
+are dealing with a pointer to a Lisp object. But, there exist also three
+possibilities, that prevent us from doing anything while marking: The
+object is read only which prevents it from being garbage collected,
+i.e. marked (`C_READONLY_RECORD_HEADER'). The object in question is
+already marked, and need not be marked for the second time (checked by
+`MARKED_RECORD_HEADER_P'). If it is a special, unmarkable object
+(`UNMARKABLE_RECORD_HEADER_P', apparently, these are objects that sit
+in some const space, and can therefore not be marked, see
+`this_one_is_unmarkable' in `alloc.c').
+
+ Now, the actual marking is feasible. We do so by once using the macro
+`MARK_RECORD_HEADER' to mark the object itself (actually the special
+flag in the lrecord header), and calling its special marker "method"
+`marker' if available. The marker method marks every other object that
+is in reach from our current object. Note, that these marker methods
+should not call `mark_object' recursively, but instead should return
+the next object from where further marking has to be performed.
+
+ In case another object was returned, as mentioned before, we
+reiterate the whole `mark_object' process beginning with this next
+object.