Skip to content

Garbage collector

Jump to bottom
aaaaaa123456789 edited this page Jan 11, 2020 · 5 revisions

Garbage collector

Since there are more valid 16-bit indexes than there are available 8-bit IDs, the latter will always be in short supply. Without any way of releasing IDs that are no longer in use, the conversion table would hopelessly fill up and become useless after some time.

The garbage collector, therefore, is the component that ensures that IDs are recycled when no longer in use. As shown in the macro functions page, the garbage collector is part of the function that writes indexes to the conversion table and allocates IDs; it is executed automatically by the ID allocation routine when there are no more IDs available.

Definition and requirements

The garbage collector must be defined right after the function that writes indexes to the conversion table. While it is possible to simply write its code underneath that function's macro, declaring a symbol for the garbage collector itself (that is, giving it a function name) is strongly recommended, like so:

_ConvertSomeIndexToID:
	___conversion_table_store wSomethingTable, SOMETHING_TABLE
	; fallthrough
SomethingTableGarbageCollection:
	; garbage collector goes here

The garbage collector function must preserve de; all other registers can be freely clobbered by the function. Also, rSVBK must be set to the bank of the conversion table both on input and on output — in other words, the function will be called with the current WRAMX bank set to the conversion table's bank, and it must preserve that value.

It is permissible to far call a garbage collector; this may be done to take advantage of an idle period (such as before saving the game) in order to execute this relatively expensive operation. The calling convention for such manual calls is the same as the one described in the previous paragraph: rSVBK must be set to the conversion table's WRAMX bank, and the function will preserve that and de and clobber everything else.

Garbage collection is expected to eventually succeed. When the ID allocation routine calls the garbage collector, it expects to find at least one free ID after the call completes. If there are no free IDs, it will simply call the garbage collector again, as the free ID search loop won't find any free IDs. This loop will become endless unless and until the garbage collector frees up at least one ID. (This implies that the conversion table must be large enough to contain all IDs in use and a few extra.)

Overview

Given the requirements mentioned above and the expected behavior of the garbage collector, the high-level approach to this function is usually like so:

  1. Push de and rSVBK.
  2. Initialize the bitmap and mark locked and recent IDs as in use.
  3. Find IDs in use at several known locations and mark them in use in the bitmap.
  4. Restore rSVBK.
  5. Free up all table IDs that weren't marked in use by the previous steps.
  6. Restore de and return.

Steps 1, 4 and 6 come directly from the requirement to preserve those two values; rSVBK is restored early because the macro that frees up table IDs requires rSVBK to be set to the table's WRAM bank. The remaining steps will be described in subsequent sections, along with the helper macros that can be used to define them.

Note that the garbage collector will require a subfunction to set bits in the bitmap used to track IDs in use. (Almost all of the code for this subfunction is identical across all instances of this subfunction; the requirement for a different one for each table comes from the initial check for validity of an ID. Since this subfunction is called very often while the garbage collector runs and it is quite slow, the performance gain brought by having a separate copy for each table is worthwhile.) This subfunction will also be described in a later section.

Sample code

Based on the steps explained in the previous section, the garbage collector function will generally look like this:

SomethingTableGarbageCollection:
	; step 1: preserve de and rSVBK
	push de
	ldh a, [rSVBK]
	push af
	; step 2: initialize the bitmap
	___conversion_bitmap_initialize wSomethingTable, SOMETHING_TABLE, .set_bit
	; step 3: find IDs in use
	; (elided - set the bits manually in the bitmap and/or use macros to do so)
	; step 4: restore rSVBK
	pop af
	ldh [rSVBK], a
	; step 5: free up unused table IDs
	___conversion_table_free_unused wSomethingTable, SOMETHING_TABLE
	; step 6: restore de and return
	pop de
	ret

.set_bit
	; bit setting function: takes an ID in a, and sets the corresponding bitmap bit if the ID is valid
	___conversion_bitmap_set SOMETHING_TABLE

The macros used in this example, as well as the macros available for step 3, will be explained in subsequent sections.

Bitmap and bit-setting function

The garbage collector relies on a $20-byte structure called the bitmap, which is a simple array of bits used to mark which IDs are in use. This structure is defined in WRAM0, called wConversionTableBitmap, and it can be anywhere in the bank as long as it doesn't straddle a $100 alignment boundary; it is defined as aligned to $20 for simplicity. The structure contains a single bit for each ID, and it is shared by all garbage collectors from all conversion tables (since only one can run at a time); since the maximum number of IDs in a conversion table is $FE, $20 bytes are enough to hold a single bit for each one of them.

This structure is initialized to all zeros during the initialization step in the garbage collector; subsequent steps will set bits to 1 as they find IDs in use, thus letting the final step of the garbage collector know which IDs are available to be freed. This setting of bits is carried out by the bit-setting function at the end of the garbage collector code, which is defined with a macro, which only takes the constant prefix as its argument and defines the entirety of the function, like so:

.set_bit
	___conversion_bitmap_set SOMETHING_TABLE

Almost all of the code in this function is identical for all conversion tables; in fact, only an initial range check differs. However, since the conversion table code is optimized for speed rather than size, the entire contents of the function are copied each time. If this is undesirable, it is possible to simply replicate the first part of the macro, and jump to a common bit-setting function, like so:

.set_bit
	dec a
	cp SOMETHING_TABLE_ENTRIES
	; define the following function somewhere, containing all of the macro after "ret nc"
	jp c, ConversionTableBitSettingFunction
	ret

Initialization

Within the garbage collector proper, the first action that is carried out after the initial register preservation is initialization. This is executed via a macro, ___conversion_bitmap_initialize, that takes three arguments: the conversion table's WRAM label prefix, the corresponding constant prefix, and the bit-setting function defined in the previous section. The macro therefore looks like this:

	___conversion_bitmap_initialize	wSomethingTable, SOMETHING_TABLE, .set_bit

Initialization has a double purpose. First of all, it sets the bitmap to zero, ensuring that all IDs are initially marked as not in use. Afterwards, it iterates over the two ID lists in the conversion table (namely, the locked ID and recently allocated ID lists), marking all of the table IDs contained in those lists as in use (by calling the bit-setting function passed to the macro), ensuring that none of those IDs are erroneously freed by the garbage collector.

Marking IDs in use

(WIP)

Clone this wiki locally