Ruby: GCAndExtensions

Introduction

ProgrammingRuby has a decent [introduction to Ruby's C API]. After writing some extensions however, I (TimSuth) found that I needed to know more about Ruby's garbage collector in order to write robust extensions. This page is an attempt to fill this gap. It assumes the reader has some knowledge of Ruby's C API, for example they have read the above introduction.

(Update: The section on Ruby's C API has been much improved in the second edition of ProgrammingRuby. It discusses some of the same issues as this page.)

Ruby from a C perspective

Ruby objects are represented by VALUE in the Ruby C API. This is a typedef for unsigned long. The value 0 is used for false and 4 is used for nil. Otherwise, if the two least significant bits are 00 it is a pointer to a structure on the heap which represents the Ruby object. (i.e. if "value & 0b11 == 0.") Other values are immediate objects or special constants (small integers, symbols, true). This works because the structures are always quad-aligned in memory. (So the pointer is always a multiple of 4, i.e. has lower bits 00.) Then for example FIX2INT converts a Fixnum to a C int by right-shifting the VALUE.

Ruby uses a "mark and sweep" garbage collection algorithm for automatic memory management. Every object (aside from the "immediate" objects mentioned earlier) has a "mark" flag (FL_MARK in ruby.h). When the garbage collector runs, it finds all the "root" objects, then for each root sets its mark flag to true and calls rb_gc_mark(VALUE) on the object. The job of rb_gc_mark is to (recursively) mark all the objects the root has a reference to (ignoring those objects that have already been marked). For example, if the root was an instance of Array then every element in the array will be (recursively) marked.

In this way, every object which is "currently reachable" will be marked. After this, the "sweep" part of the algorithm occurs - every object which was not marked is released (finalizers called, freed, user-defined free function called) and the mark flags of the other objects are reset.

At the C level, it is possible to define your own mark function for a class that gets called when instances of this class are being marked. (This mark function is passed as an argument to Data_Wrap_Struct or Data_Make_Struct.) This mark function can call rb_gc_mark on other objects. For example, instances of Array mark every object that is stored in the array. (Note: Data_Wrap_Struct and Data_Make_Struct are used to associate a C structure with an instances of the class. This structure is only available at the C level. For example, each instances of the standard Array class has a structure containing a C array of VALUEs and an integer for the length of the array.)

The "root objects" used to begin the collection include those represented by

local variables
global variables
global constants
hardware registers
C stack

The last two are the most important when considering C extensions. Ruby looks through hardware registers and the C stack for things that "look like" pointers to Ruby objects (i.e. VALUEs). This is known as conservative garbage collection because it will find all objects that are reachable, but may get some "false positives" - values that look like pointers but aren't. For example, if an integer coincides with an actual VALUE then the the garbage collector will not release the object associated with that VALUE even if it is in fact unreachable. Ruby does this is to make writing C extensions easy.

Listing 1: Example of C code that utilises the conservative collector

1.	void add_to_array(VALUE arr) {
2.		VALUE c, d;
3.		c = rb_str_new2("cat");
4.		d = rb_str_new2("dog");
5.		
6.		rb_ary_push(arr, c);
7.		rb_ary_push(arr, d);
8.	}

Consider line 6 of listing 1. If the call to rb_ary_push resulted in the garbage collector being run, the only thing preventing the string referred to by d from being collected is that a pointer to it is stored on the C stack.

If Ruby did not have this conservative phase then it would be necessary for C programmers to protect objects from garbage collection in some other way. For example, Python extensions must explicitly deal with reference counting, using Py_INCREF(x) and Py_DECREF(x).

C code can also call rb_gc_register_address(void *addr) to say that a Ruby VALUE is stored at *addr and the object refered to it should not be collected. The object is then treated as a root object. For example, global variables in C are not automatically seen by the garbage collector so it is common to use rb_gc_register_address inside the initialisation function of an extension to protect these.

rb_gc_unregister_address(void *addr) removes the address from the global linked-list. Removing an address in this way takes time linear to the number of entries in the list.

When the collector can run

An important question is "when can the garbage collector run?" From the point of view of Ruby code, it can run at any time. (Uness GC.disable has been called.) When writing C code it is a different story. The garbage collector is not running in a separate system thread as in systems like .NET. Instead, the Ruby interpreter collects when rb_gc_start is called. This is done explicitly by the user (GC.start) or when a Ruby function tries to allocate memory (using ALLOC) and either the allocation fails or Ruby has allocated around 7 MB since the last collection. This means that the C code only has to be concerned about the possibility of garbage collection when Ruby functions are used.

Compiler over-optimisations and "volatile"

There is a further complication. Consider the code in listing 2.

Listing 2: GC Bug caused by compiler over-optimisation

1.	VALUE get_a_string() {
2.		/* Create a new String out of the C string "street". */
3.		VALUE str = rb_str_new2("street");
4.		VALUE str2;
5.	
6.		/* Get the buffer underlying the String. */
7.		char *ptr = RSTRING(str)->ptr;
8.	
9.		/* We just want the next line to do something that could potentially run the garbage collector.
10.		e.g. it could be replaced with
11.			rb_gc_start();
12.		*/
13.		str2 = rb_str_new2("hello");
14.	
15.		ptr[1] = 'w';
16.	
17.		return rb_str_new2(ptr);
}

Suppose that line 13 causes the garbage collector to be run. Could str be collected? We would say "no", since a reference to it is stored on the C stack (or in a register). However, the C compiler may be 'clever' enough to notice that str is never referred to after line 7 and therefore not bother keeping the value after that point. So the garbage collector can remove str and free the buffer that ptr refers to. This makes lines 15 and 17 invalid - they could result in a crash or other bad behaviour.

The solution is to mark the variable as volatile to indicate to the C compiler that it must not perform such optimisations on it. Changing line 3 to

3.		volatile VALUE str = rb_str_new2("street");

makes the code correct.

Determining the stack start and end

For Ruby to traverse the stack it must know where in memory the stack starts and ends. (Since the stack of a process is simply a fixed-size block of memory allocated to it.)

Finding the end is easy: simply declare a variable on the stack and check its address. rb_gc() does this. In contrast, rb_gc() has no automatic way of determining the start of the stack.

The value for the start is set by calling Init_stack(void* addr). The ruby_init() function (which is called by the Ruby interpreter or software which embeds Ruby) is similar to listing 3.

Listing 3: Initialising the stack end

void
ruby_init()
{
	int state;
	...
	Init_stack(&state);
	...
}

It is therefore important that any Ruby API function is called with a stack pointer no higher (or lower, depending on which direction the stack grows on your architecture) than this value - otherwise Ruby can collect an object before a C function has finished using it. A programmer need only be concerned with this when Ruby is being embedded in C (rather than extended). i.e. when their code is responsible for calling ruby_init().

Init_stack can be called multiple times. The "most conservative" value will be used.

Just a couple notes on things that have bitten me.

If you use Data_Wrap_Struct to convert a structure into a Ruby object, Ruby's memory management only keeps track of the little object stub, not the memory that the structure occupies. If the structure is very big or you have a lot of these structures, it's possible to use up all available memory yet Ruby doesn't think it needs to call GC.start. The only solution I know of is to manually insert calls to GC.start in the script.

If you define a free routine with Data_****_Struct and your particular class contains Ruby objects, you can't rely on those objects still being available when GC calls the free routine as the interpreter is terminating. There's no guarantee of the order in which GC frees memory and it may have freed those objects already.

TimHunter

Maintainers:

: Tim Sutherland <timsuth@ihug.co.nz> (TimSuth)