11.4.4 gc_sweep

The job of this function is to free all unmarked records from memory. As we know, there are different types of objects implemented and managed, and consequently different ways to free them from memory. See Introduction to Allocation.

We start with all objects stored through lcrecords. All bulkier objects are allocated and handled using that scheme of lcrecords. Each object is malloced separately instead of placing it in one of the contiguous frob blocks. All types that are currently stored using lcrecords’s alloc_lcrecord and make_lcrecord_list are the types: vectors, buffers, char-table, char-table-entry, console, weak-list, database, device, ldap, hash-table, command-builder, extent-auxiliary, extent-info, face, coding-system, frame, image-instance, glyph, popup-data, gui-item, keymap, charset, color_instance, font_instance, opaque, opaque-list, process, range-table, specifier, symbol-value-buffer-local, symbol-value-lisp-magic, symbol-value-varalias, toolbar-button, window, and window-configuration. We take care of them in the fist place in order to be able to handle and to finalize items stored in them more easily. The function sweep_lcrecords_1 as described below is doing the whole job for us. For a description about the internals: See lrecords.

Our next candidates are the other objects that behave quite differently than everything else: the strings. They consists of two parts, a fixed-size portion (struct Lisp_String) holding the string’s length, its property list and a pointer to the second part, and the actual string data, which is stored in string-chars blocks comparable to frob blocks. In this block, the data is not only freed, but also a compression of holes is made, i.e. all strings are relocated together. See String. This compacting phase is performed by the function compact_string_chars, the actual sweeping by the function sweep_strings is described below.

After that, the other types are swept step by step using functions sweep_conses, sweep_bit_vectors_1, sweep_compiled_functions, sweep_floats, sweep_symbols, sweep_extents, sweep_markers and sweep_extents. They are the fixed-size types cons, floats, compiled-functions, symbol, marker, extent, and event stored in so-called "frob blocks", and therefore we can basically do the same on every type objects, using the same macros, especially defined only to handle everything with respect to fixed-size blocks. The only fixed-size type that is not handled here are the fixed-size portion of strings, because we took special care of them earlier.

The only big exceptions are bit vectors stored differently and therefore treated differently by the function sweep_bit_vectors_1 described later.

At first, we need some brief information about how these fixed-size types are managed in general, in order to understand how the sweeping is done. They have all a fixed size, and are therefore stored in big blocks of memory - allocated at once - that can hold a certain amount of objects of one type. The macro DECLARE_FIXED_TYPE_ALLOC creates the suitable structures for every type. More precisely, we have the block struct (holding a pointer to the previous block prev and the objects in block[]), a pointer to current block (current_..._block)) and its last index (current_..._block_index), and a pointer to the free list that will be created. Also a macro FIXED_TYPE_FROM_BLOCK plus some related macros exists that are used to obtain a new object, either from the free list ALLOCATE_FIXED_TYPE_1 if there is an unused object of that type stored or by allocating a completely new block using ALLOCATE_FIXED_TYPE_FROM_BLOCK.

The rest works as follows: all of them define a macro UNMARK_... that is used to unmark the object. They define a macro ADDITIONAL_FREE_... that defines additional work that has to be done when converting an object from in use to not in use (so far, only markers use it in order to unchain them). Then, they all call the macro SWEEP_FIXED_TYPE_BLOCK instantiated with their type name and their struct name.

This call in particular does the following: we go over all blocks starting with the current moving towards the oldest. For each block, we look at every object in it. If the object already freed (checked with FREE_STRUCT_P using the first pointer of the object), or if it is set to read only (C_READONLY_RECORD_HEADER_P, nothing must be done. If it is unmarked (checked with MARKED_RECORD_HEADER_P), it is put in the free list and set free (using the macro FREE_FIXED_TYPE, otherwise it stays in the block, but is unmarked (by UNMARK_...). While going through one block, we note if the whole block is empty. If so, the whole block is freed (using xfree) and the free list state is set to the state it had before handling this block.