-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_curser' 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 array `staticvec'. *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_speficiers' 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.
-
-\1f