Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

206 lines (179 sloc) 5.598 kb
/**
* A mark table, used during a mark-and-sweep garbage collection cycle.
*
* This implementation is somewhat slower than fastmarktable.c, but is
* copy-on-write friendly. It stores mark information for objects in a bit
* field located at the beginning of the heap. Mark information for filenames
* are stored in a pointer set.
*/
#ifndef _MARK_TABLE_C_
#define _MARK_TABLE_C_
#include "pointerset.h"
/* A mark table for filenames and objects that are not on the heap. */
static PointerSet *mark_table = NULL;
static struct heaps_slot *last_heap = NULL;
static inline struct heaps_slot *
find_heap_slot_for_object(RVALUE *object)
{
register int i;
/* Look in the cache first. */
if (last_heap != NULL && object >= last_heap->slot
&& object < last_heap->slotlimit) {
return last_heap;
}
for (i = 0; i < heaps_used; i++) {
struct heaps_slot *heap = &heaps[i];
if (object >= heap->slot
&& object < heap->slotlimit) {
/* Cache this result. According to empirical evidence, the chance is
* high that the next lookup will be for the same heap slot.
*/
last_heap = heap;
return heap;
}
}
return NULL;
}
static inline void
find_position_in_bitfield(struct heaps_slot *hs, RVALUE *object,
unsigned int *bitfield_index, unsigned int *bitfield_offset)
{
unsigned int index;
index = object - hs->slot;
/*
* We use bit operators to calculate the position in the bit field, whenever possible.
* This only works if sizeof(int) is a multiple of 2, but I don't know of any platform
* on which that is not true.
*/
if (sizeof(int) == 4 || sizeof(int) == 8 || sizeof(int) == 16) {
int int_bits_log; /* Must be equal to the base 2 logarithm of sizeof(int) * 8 */
switch (sizeof(int)) {
case 4:
int_bits_log = 5;
break;
case 8:
int_bits_log = 6;
break;
case 16:
int_bits_log = 7;
break;
default:
int_bits_log = 0; /* Shut up compiler warning. */
abort();
}
*bitfield_index = index >> int_bits_log;
*bitfield_offset = index & ((sizeof(int) * 8) - 1);
} else {
*bitfield_index = index / (sizeof(int) * 8);
*bitfield_offset = index % (sizeof(int) * 8);
}
}
static void
rb_bf_mark_table_init()
{
if (mark_table == NULL) {
mark_table = pointer_set_new();
}
}
static void
rb_bf_mark_table_prepare()
{
last_heap = NULL;
}
static void
rb_bf_mark_table_finalize()
{
/* Do nothing. */
}
static inline void
rb_bf_mark_table_add(RVALUE *object)
{
struct heaps_slot *hs;
unsigned int bitfield_index, bitfield_offset;
hs = find_heap_slot_for_object(object);
if (hs != NULL) {
find_position_in_bitfield(hs, object, &bitfield_index, &bitfield_offset);
hs->marks[bitfield_index] |= (1 << bitfield_offset);
} else {
pointer_set_insert(mark_table, (void *) object);
}
}
static inline void
rb_bf_mark_table_heap_add(struct heaps_slot *hs, RVALUE *object)
{
unsigned int bitfield_index, bitfield_offset;
find_position_in_bitfield(hs, object, &bitfield_index, &bitfield_offset);
hs->marks[bitfield_index] |= (1 << bitfield_offset);
}
static inline int
rb_bf_mark_table_contains(RVALUE *object)
{
struct heaps_slot *hs;
unsigned int bitfield_index, bitfield_offset;
hs = find_heap_slot_for_object(object);
if (hs != NULL) {
find_position_in_bitfield(hs, object, &bitfield_index, &bitfield_offset);
return hs->marks[bitfield_index] & (1 << bitfield_offset);
} else {
return pointer_set_contains(mark_table, (void *) object);
}
}
static inline int
rb_bf_mark_table_heap_contains(struct heaps_slot *hs, RVALUE *object)
{
unsigned int bitfield_index, bitfield_offset;
find_position_in_bitfield(hs, object, &bitfield_index, &bitfield_offset);
last_heap = hs;
return hs->marks[bitfield_index] & (1 << bitfield_offset);
}
static inline void
rb_bf_mark_table_remove(RVALUE *object)
{
struct heaps_slot *hs;
unsigned int bitfield_index, bitfield_offset;
hs = find_heap_slot_for_object(object);
if (hs != NULL) {
find_position_in_bitfield(hs, object, &bitfield_index, &bitfield_offset);
hs->marks[bitfield_index] &= ~(1 << bitfield_offset);
} else {
pointer_set_delete(mark_table, (void *) object);
}
}
static inline void
rb_bf_mark_table_heap_remove(struct heaps_slot *hs, RVALUE *object)
{
unsigned int bitfield_index, bitfield_offset;
find_position_in_bitfield(hs, object, &bitfield_index, &bitfield_offset);
hs->marks[bitfield_index] &= ~(1 << bitfield_offset);
}
static inline void
rb_bf_mark_table_add_filename(char *filename)
{
pointer_set_insert(mark_table, (void *) filename);
}
static inline int
rb_bf_mark_table_contains_filename(const char *filename)
{
return pointer_set_contains(mark_table, (void *) filename);
}
static inline void
rb_bf_mark_table_remove_filename(char *filename)
{
pointer_set_delete(mark_table, (void *) filename);
}
static void
rb_use_bf_mark_table() {
rb_mark_table_init = rb_bf_mark_table_init;
rb_mark_table_prepare = rb_bf_mark_table_prepare;
rb_mark_table_finalize = rb_bf_mark_table_finalize;
rb_mark_table_add = rb_bf_mark_table_add;
rb_mark_table_heap_add = rb_bf_mark_table_heap_add;
rb_mark_table_contains = rb_bf_mark_table_contains;
rb_mark_table_heap_contains = rb_bf_mark_table_heap_contains;
rb_mark_table_remove = rb_bf_mark_table_remove;
rb_mark_table_heap_remove = rb_bf_mark_table_heap_remove;
rb_mark_table_add_filename = rb_bf_mark_table_add_filename;
rb_mark_table_contains_filename = rb_bf_mark_table_contains_filename;
rb_mark_table_remove_filename = rb_bf_mark_table_remove_filename;
}
#endif /* _MARK_TABLE_C_ */
Jump to Line
Something went wrong with that request. Please try again.