# Copyright (C) 2001-2004, The Perl Foundation.
# $Id: memory_internals.pod 23014 2007-11-24 12:05:52Z bernhard $

=head1 NAME

docs/memory_internals.pod - Memory Internals

=head1 ABSTRACT

This document tries to explain the internals of parrot structures related to
memory management and should give the answer 42, when questions are related to
the whole and everything and memory management.

=head1 OVERVIEW

All allocated items are managed in memory pools. Memory pools hold collections
of similar items. These pools can be roughly divided into two kinds: pools
holding fixed sized items and variable sized items.

A pool is organized as a linked list of big chunks, holding many managed items
of one kind.

=head2 Abbreviations used here

DOD ... dead object detection, see F<docs/pdds/pdd09_gc.pod> for details.

By scanning through all the interpreter's registers, stacks and the processor
stack, all objects that are detected here are marked as alive. Objects in all
pools not alive are considered dead.

=head1 Top down: the interpreter

A overall layout of the interpreter's memory management looks like so:

    typedef Interp {
        ...
        struct Arenas *arena_base;
        ...
    } Interp;

All object-like things that get allocated during the execution of parrot
bytecode are managed here.

=head1 Arenas

C<struct Arenas> holds pointers to different subkinds of managed memory. A
simplification looks similar to this:

    struct Arenas {
        struct Memory_Pool *memory_pool;
        ...
        struct Small_Object_Pool * header_pool;
    }

C<Memory_pool> and C<header_pool> are variable and fixed sized pool pointers
respectively.

=head1 Memory_Pool

Here all variable sized items are allocated, managed in linked lists of
C<Memory_Blocks> - but see below.

=head1 Small_Object_Pool

This pool manages C<Small_Object_Arena>s, linked together, which provide the
space for the fixed sized objects.

=head1 Fixed sized items

These items are either objects by themselves, like a C<PMC>, or are a header
structure of a variable sized object like a C<STRING>.  The general object of
this kind is a buffer-like object, which consists of a C<Buffer> or a C<PObj>
at the beginning and a variable but fixed sized part after the buffer
structure. Examples of this are a C<STRING> or an C<IntList>.

Buffer-like objects of the same size are maintained in the
I<sized_header_pools>, which manage objects of the same size in one slot.

All fixed sized objects are allocated with C<alloc_objects()>, and first put
onto the pool's C<free_list>. When there is need for a new object it is taken
off the free list, and when it stops being used, it will be put back on the
free list again. DOD detects which objects are no longer being used.

If the free list is empty then a DOD run is started, which may be able to
refill the free list with dead objects it detects are free for re-use.  If it
finds none then a new pool is allocated to hold more objects.

These fixed sized objects are never freed during the lifetime of an
interpreter, they just get reused or recycled.

=head2 General structure of a buffer-like item

    struct parrot_object_t {
    struct {
        void *bufstart;
        size_t buflen;
    } b;
    unsigned flags;
    ...
    } PObj;

This does not totally reflect the current implementation, but is the spirit of
the abstraction of current objects. Above structure including C<flags> is the
current C<Buffer>. With some additional fields like C<strstart> and C<bufused>,
inserted at the ellipses, you get a C<STRING>.  Adding a I<vtable> (and some
other structure members) yields a C<PMC>.

=head2 ARENA_DOD_FLAGS

Only three flags need to be checked during a DOD run: C<PObj_live_FLAG>,
C<PObj_on_free_list_FLAG>, and C<PObj_is_special_PMC_FLAG>.  Normally these
flags are stored in C<PObj-E<gt>flags>, meaning that each PMC must be accessed
during the DOD run.

An alternative approach is to store the DOD-Flags in the Arenas as a packed
array of bits. This approach will be used if the preprocessor variable
C<ARENA_DOD_FLAGS> is defined to 1, which happens by default if the system
provides a memory alignment primitive such as C<memalign>. In this case the
C<struct Small_Object_Arena> is extended with a pointer to the packed bitarray

    struct Small_Object_Arena {
        UINTVAL *dod_flags;
        size_t object_size;
        ...
    };

The memory for this Small_Object_Arena is allocated at the beginning of a 
large aligned block of memory (currently 4Mib) and the objects in this arena 
come from this memory block. Therefore the arena of an object can be found by 
simply masking out the lower bits of the pointer to the object:

    arena = object & ARENA_MASK;

The macro C<GET_ARENA> does exactly this, including the necessary type casts to
remove warnings. The dod_flags are accessed by getting the element number in
the arena (this is possible because the C<object_size> is fixed and stored in
the C<struct Small_Object_Arena>), creating the appropriate bitmask by shifting
and accessing the right element of C<dod_flags[]>.

    n = (object - arena->start_objects) / arena->object_size;
    arena->dod_flags[n >> ARENA_FLAG_SHIFT] 
        & flag << ((n & ARENA_FLAG_MASK) << 2)


F<pobj.h> provides macros to facilitate referencing individual object flags:
C<DOD_flag_SET>, C<DOD_flag_CLEAR> and C<DOD_flag_TEST>. They are also defined
in the case without ARENA_DOD_FLAGS, so they make up a portable way of
manipulating the DOD-relevant object flags.

=head3 Flag packing format

The three object flags consulted during DOD are packed into one 4-bit nibble
per object (one bit is currently unused).  Since C<arena-E<gt>dod_flags[]> is
an array of native-sized UINTVALs ("words"), the number of nibbles per array
entry varies depending on the platform.

To reference a particular flag in a test, set, or clear operation, we require
both the word containing the object's flags and a bitmask to isolate the flag.

The flag word for object o is found as follows:

- Get the C<dod_flags[]> array for the object's arena

    [GET_ARENA(o)->dod_flags]

- Get the index of the object in its arena

    [n=GET_OBJ_N(arena,o)]

- Determine which word in dod_flags contains the needed flag nibble

    [(obj index)/(obj flag sets per word) = n>>ARENA_FLAG_SHIFT]

The composite expression to reference the flag word is then

    GET_ARENA(o)->dod_flags[ GET_OBJ_N(GET_ARENA(o), o) >> ARENA_FLAG_SHIFT ]

The bitmask for the desired flag is constructed as follows:

- Determine the index into the flag word of the object's nibble

    [(obj index)%(nibbles per word) = n & ARENA_FLAG_MASK]

- Convert nibble index into bit index

    [(nibble index)*(bits per nibble) = (n & ARENA_FLAG_MASK) << 2]

- Create bitmask for desired flag by shifting base flag by bit index

    [d_PObj_whatever_FLAG << (nibble index)]

The composite expression to form the bitmask is then

    (d_PObj_ ## flag ## _FLAG << (( GET_OBJ_N(GET_ARENA(o), o) &
        ARENA_FLAG_MASK ) << 2))

The DOD_flag_* macros combine these constructions to access the flags.

=head1 Variable sized items

These items never live alone, they are part of a C<Buffer> structure, described
above. They are allocated at C<bufstart>. This is, for example, used to manage
the buffer's free list, where C<bufstart> is used as a pointer to the next
object.

These items are managed in two different pools: the C<memory_pool> and the
C<constant_string_pool>. The former holds all variable sized items, while the
latter containing the word "string", holds constant strings only, as we don't
have other variable sized constant items to store.

Here, different memory allocation schemes jump in:

=head2 Copying GC

A C<memory_pool> gets allocated in big blocks, namely a C<Memory_Block>.

When some part is needed, e.g. to store a string, this part is carved out of
the memory block, until this block is used up. If no more space is available in
this memory block, a garbage collection (GC) is started.  This copies all
living items of all used memory blocks into one new block, which holds
thereafter only used items tightly packed together.

The old memory blocks, containing sparse unused parts and used parts already
copied to the new place, are then unused altogether and get C<free()>ed
thereafter.

When GC doesn't provide enough free space needed for a new item, a new block is
added to the memory pool.

This also implies that buffers are moved around during their life. Users of
these buffers are therefore not allowed to hold pointers to buffers over pieces
of code that might trigger a GC run, like C<Parrot_allocate()> or
C<string_compare()>.

=head2 Defragmenting allocator

An alternative to the above is to use a memory allocator, which is as fast as
the above and does reuse C<free()>ed items in a memory conserving way.
Actually, the malloc implementations in some systems' F<libc> efficiently
provide this, such as the glibc malloc based on Doug Lea's allocator.

Using this allocator, all variable sized items are just allocated via a plain
C<malloc()> call, or resized with C<realloc()>, and after they lose their
existence (ie when DOD detects that the managing buffer header is no longer in
use) they are C<free()>ed. That's all. The underlying allocator collects these
pieces, coalesces them if possible to form bigger pieces, and then puts them on
free lists, sorted by size.  Eventually, when a new allocation request arrives,
it may give them back to Parrot.

So here, the variable length C<memory_pool> is unused. You can consider this
pool to live inside the allocator.

Buffers allocated this way don't move around, except when reallocated of
course.

The F<Configure.pl> option C<--gc> allows one to use either method.

=head2 Buffer_Tail and COW

Both implementations have the same problem to solve: C<STRING>s that get
copied, or parts of strings as the result of a substr() call, do not allocate
new space in the memory pool to hold this string or part of string. They just
use a C<new_string_header()> and set up a pointer (C<strstart>) pointing
somewhere into the original string and remember the used length there in
C<bufused>.

This is all OK, as long as the original and the lazy copy of the string are not
modified. So that's well-known and called COW (copy on write).

Now, during GC (or freeing buffers) the problem arises: to whom does this
string belong? You shouldn't copy the same string to different places, thus
rendering COW to a noop, nor are you allowed to free this same string more then
once (your debugger will tell you why...).

Both allocation schemes therefore use a part of the allocated string to do this
bookkeeping.

Copying GC uses a C<Buffer_Tail> after the end of the actual variable length
string and marks such COW strings with C<TAIL_moved> and stores the new address
in the buffer header, so other users of this string can be updated to reuse the
same string (RT#47764 one or all other users?).

The C<malloc()>/C<free()> approach stores a refcount at C<bufstart>. During DOD
all dead users increment the refcount, living users set it to an huge value.
When freeing the buffer, the string is only freed if the refcount reaches zero.

=head1 Simplified Figure

                             +--------+
      +------------------<---| Arenas |<-----------+
      |                      +--------+-->--+      |
      |                                     |      |
      |         +------+    +-----------+   |  +=============+
      |         | S0   |<---| Registers |<--)--| Interpreter |
      |         +------+    +-----------+   |  +=============+
      |     +---| S1   |                    |
      |     |   +------+                    +----------+
 +-------+  |                                          |
 | Blk 1 |--)-->+----------+    +--------------+   +---------+
 +-------+  |   | Buffer 1 |    | OnestringAno |   | Block 1 |
 | Blk 2 |  |   +----------+    | therstring.. |   +---------+
 +-------+  |   | Buffer 2 |    | ..String...  |<--| Block 2 |
 | .     |  |   +----------+    +--------------+   +---------+
 +-------+  |   | ...      |        ^    ^         | ...     |
 Small Obj  |   +----------+        |    |         +---------+
 Pool       +-->| Buffer N |--------+----+         Memory Pool
                +----------+
                 Buffer          Memory Block

Now consider, that the I<Interpreter> shall be a C<PMC> living in C<Buffer X>
of the underlying interpreter and is currently running F<perldoc
docs/memory_internals.pod>, and then redo this figure, with all the blanks
filled in ;-)

=head1 FILES

smallobject.[ch], headers.c, resources.[ch], res_lea.c, dod.c, string.[ch],
pobj.h.

=head1 BUGS

All spelling errors belong to those who honestly collected them, as well as all
errors related to my abuse of the English language - I'm not natively speaking
it.

To minimize this bugs section - please patch this document and keep it up to
date - thanks.

=head1 AUTHOR

Leopold Tötsch C<lt@toetsch.at>

=head1 VERSION

0.1.0 Mar 2004