Last modified on 20 July 2009, at 17:51

Ruby Hacking Guide/Garbage Collection

The Runtime Structure of a ProgramEdit

Before diving into the content of this chapter, let us review the organization of memory at program execution time. This chapter will involve some low-level components of computer architecture, so familiarizing oneself with some basic concepts ahead of time will be required. Moreover, these concepts will be required for later chapters as well. Let's get them out of the way here.

SegmentsEdit

Most C programs have the following components in their memory space:

  1. text area,
  2. a store of static and global variables,
  3. the machine stack,
  4. the heap.

The text area is where the code is stored. The second component should be clear. The machine stack is where functions' arguments and local variables are stacked. The heap is what is allocated by malloc().

Let's discuss the machine stack in detail. Being called a machine "stack", it obviously has a stack-like construction. In other words, we can keep adding new elements to the top. In practice values are added to the stack in individual int units but conceptually there is a larger unit called the stack frame.

Each stack frame corresponds to one function call. In other words, each function call will add one stack frame and a stack frame is taken off on return. If we extremely simplify this, the machine stack could look like Figure 1.

 the top
+-------------+
| stack frame | <-- the frame for the currently running function
+-------------+
| stack frame |
+-------------+
| stack frame |
+-------------+
| stack frame |
+-------------+
| stack frame |
+-------------+
 the bottom

Figure 1: The machine stack

In this figure we marked the extreme end of the stack "the top," but the machine stacks does not necessarily address frames from low to high. For example on x86 machines the stack grows from higher addresses to lower ones.

alloca()Edit

With malloc() memory of arbitrary size can be allocated. alloca() is the machine stack version of this. However, memory allocated by alloca() does not need to be deallocated. Or, rather, it may be better to say that that the memory "gets" deallocated with the function's return. Thus alloca()-allocated values cannot be used as a function's return value. This is the same as saying "pointers to local variables cannot be returned."

All this is fine. It basically means that we can locally allocate arrays which change in length dynamically.

However there are environments where there is no native alloca(). Many would prefer to use an alloca() in those environments as well, so a function with the same behavior could be written in C. In this case, however, it may only be implemented to "not require deallocation," but may not necessarily be allocating memory on the machine stack. In fact, it normally would not do this. If it could do that, there may as well be a native implementation of alloca().

How can we implement alloca() in C? The most straight-forward implementation first allocates memory with malloc(). It then stores the caller function and the allocated address on a global list. Then the next time alloca() is called, if there is any memory that was allocated for a function which has already concluded, it can be free()'ed (see Figure 2).

+-----------+      +------------+
| main      |      | main       |
+-----------+      +------------+
| A         | ===> | A          |
+-----------+      +------------+
| B         |      | B          | mark that B -> alloca(32)
+-----------+      | alloca(32) | free the memory allocated for D
| C         |      +------------+
+-----------+
| D         |
| alloca(8) | mark that D -> alloca(8)
+-----------+

Figure 2: The behavior of a C implementation of alloca()

Ruby's missing/alloca.c is an implementation of just such an emulated alloca().

OutlineEdit

Now let's begin the main subject of this chapter, garbage collection.

Introducing GCEdit

What GC doesEdit

Mark & sweepEdit

Sweep & copyEdit

Reference countingEdit

Object managementEdit

struct RVALUEEdit

Object heapEdit

freelistEdit

add_heap()Edit

rb_newobj()Edit

MarkEdit

rb_gc_mark()Edit

rb_gc_mark_children()Edit

rb_gc()Edit

The Ruby stackEdit

RegistersEdit

mark_locations_array()Edit

is_pointer_to_heap()Edit

Register windowsEdit

The machine stackEdit

Init_stack()Edit

STACK_ENDEdit

rb_gc_mark_locations()Edit

Other root objectsEdit

SweepEdit

Special NODE handlingEdit

The finalizerEdit

rb_gc_force_recycle()Edit

ConsiderationsEdit

Memory deallocationEdit

Generations of GCEdit

CompactionEdit

The volatile keyword in GCEdit

Initialization codeflowEdit

gc.c internalsEdit

Interpreter internalsEdit

Object CreationEdit

The allocation frameworkEdit

User-defined object creationEdit

Data_Wrap_Struct()Edit

Data_Get_Struct()Edit

Problems with the allocation frameworkEdit

<hline>

Comments, suggestions, and criticisms may be sent to Aoki MINERŌ <aamine@loveruby.net>. Please direct translation comments, suggestions, and criticisms to the translator of this chapter, mitcho (Michael Yoshitaka Erlewine) <mitcho@mitcho.com>.