Vicare Scheme: objects memory alloc

13.3.4 Basic memory allocation functions

A memory allocation operation that is allowed to trigger a garbage collection is performed as follows:

ikpcb_t *  pcb             = ...;
ikuword_t  number_of_bytes = ...;
ikuword_t  aligned_size    = IK_ALIGN(number_of_bytes);
ikptr_t    P = ik_safe_alloc(pcb, aligned_size);

while a memory allocation operation that is forbidden to trigger a garbage collection is performed as follows:

ikpcb_t *  pcb             = ...;
ikuword_t  number_of_bytes = ...;
ikuword_t  aligned_size    = IK_ALIGN(number_of_bytes);
ikptr_t    P = ik_unsafe_alloc(pcb, aligned_size);

where P is an untagged memory pointer and pcb is a pointer to the “Process Control Block” data structure.

To add a tag, for example the vector_tag, to an untagged memory pointer we can do:

ikpcb_t *  pcb             = ...;
ikuword_t  number_of_bytes = ...;
ikuword_t  aligned_size    = IK_ALIGN(number_of_bytes);
ikptr_t    S = ik_safe_alloc(pcb, aligned_size) | vector_tag;

Objects subject to garbage collection are allocated on the Scheme heap; a new Scheme object is allocated in the nursery’s hot memory block:

    allocated  allocated      allocated
    block      block          block
...|----------|--------------|--------|------...
    ^          ^              ^        ^
    |          |              |        |
  pointer    pointer        pointer   pointer to
                                      next block

every pointer must satisfy alignment constraints with the following purposes:

To make pointer indirection efficient for the underlying platform.
To have pointer values with the 3 least significant bits set to zero, so that such bits can be used to hold an object’s type tag.
To allocate a data area for Scheme objects at least 2 machine words wide; this is required for garbage collection purposes: the 2 words are used by the garbage collector to register informations when a live Scheme object is gathered.

for these reasons we must always filter the requested size (number of bytes) through the IK_ALIGN() macro.

The PCB always references a “pointer to the next free block” with alignment constraints satisfied; if we filter the requested number of bytes through IK_ALIGN(), we obtain a number of bytes which, added to the pointer, gives a correctly aligned pointer:

ikpcb_t   pcb             = ...;
ikuword_t requested_size  = ...;
uint8_t * allocated_block = (uint8_t *)pcb->allocation_pointer;
ikuword_t aligned_size    = IK_ALIGN(requested_size);
uint8_t * next_free_block = allocated_block + aligned_size;
pcb->allocation_pointer   = (ikptr_t)next_free_block;

the scenario is as follows:

       requested size      wasted
  |.......................|..|
          aligned size
--|--------------------------|--- nursery's hot block
   ^                          ^
   |                          |
pointer to an              pointer to the
allocated block            next block

if the aligned size is bigger than the requested size: the small chunk of memory at the end of the allocated block is wasted.

Function: ikpcb_t * ik_the_pcb (void): Return a pointer to the current process control block. It is rarely needed: when calling a C function from Scheme a pointer to the PCB is always pushed on the C stack as last argument.

Preprocessor Macro: ikuword_t IK_ALIGN (ikuword_t number_of_bytes)

Convert number_of_bytes to the number of bytes requested to satisfy pointer alignment constraints. The aligned size is always an exact multiple of the underlying platform’s word size (32-bit or 64-bit); precisely: it is the smallest multiple of the wordsize which is greater than number_of_bytes and makes the pointer have the 3 least significant bits set to zero.

This means that it is impossible to allocate less than 2 machine words.

Function: ikptr_t ik_safe_alloc (ikpcb_t * pcb, ikuword_t aligned_size)

Reserve a memory block on the Scheme heap’s nursery hot block and return a reference to it as an untagged pointer. pcb must reference the process control block, aligned_size must be the requested number of bytes filtered through IK_ALIGN().

If not enough memory is available on the current hot block: a garbage collection is triggered; then allocation is tried again: if it still fails the process is terminated with exit status EXIT_FAILURE.

The reserved memory is not initialised to safe values: its contents have to be considered invalid. However, notice that the heap’s nursery is not a garbage collection root; so if we leave some machine words uninitialised on the nursery, outside of Scheme objects: nothing bad happens, because the garbage collector never sees them.

Function: ikptr_t ik_unsafe_alloc (ikpcb_t * pcb, ikuword_t aligned_size)

If not enough memory is available on the current hot block: such hot block is stored away in a linked list referenced by the pcb, and a new hot block is allocated; if such allocation fails: the process is terminated with exit status EXIT_FAILURE.

We notice explicitly that this function does not trigger a garbage collection run, so, when using it, it is not needed to register C pointers as garbage collection roots.

Preprocessor Macro: IK_ASS (ikptr_t left, ikptr_t right)

Perform a C language assignment enforcing the order of evaluation of the left–side and right–side expressions:

Evaluate right.
Evaluate left.
Store the result of right in the lvalue resulting from evaluating left.

After a use of this macro: if right is a reference to a non–immediate Scheme object, the function ik_signal_dirt_in_page_of_pointer() must be applied to the lvalue resulting from evaluating left. For example, when allocating a pair filled with non–immediate numbers:

ikptr_t   s_pair = ika_pair_alloc(pcb);

pcb->root0 = &s_pair;
{
  IK_ASS(IK_CAR(s_pair), ika_integer_from_int(pcb, 1));
  IK_SIGNAL_DIRT(pcb, IK_CAR_PTR(s_pair));

  IK_ASS(IK_CDR(s_pair), ika_integer_from_int(pcb, 2));
  IK_SIGNAL_DIRT(pcb, IK_CDR_PTR(s_pair));
}
pcb->root = NULL;

Function: void ik_signal_dirt_in_page_of_pointer (ikpcb_t * pcb, ikptr_t pointer)

Register in the dirty vector that the memory page containing the location referenced by pointer has been mutated. This function must be called every time we mutate a pair, vector, structure, record, ratnum, cflonum, compnum, port, symbol slot by storing in it a reference to another non–immediate Scheme object that might be in a newer garbage collection generation.

If we call this function when there is no need for it: nothing bad will happen; the garbage collector will just do some useless work, slowing down the collection time a bit.

Preprocessor Macro: void IK_SIGNAL_DIRT (ikpcb_t * pcb, ikptr_t pointer): Just a wrapper for ik_signal_dirt_in_page_of_pointer(); it has a shorter name.