11.4.2 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_protecting 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. See 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. See 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. See 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. See 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). See 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 SXEmacs 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.