Author: Nicolas Truessel <[email protected]>
Branch: quad-color-gc
Changeset: r86305:45d8ca00efff
Date: 2016-08-19 09:41 +0200
http://bitbucket.org/pypy/pypy/changeset/45d8ca00efff/
Log: Import qcgc codebase
diff --git a/rpython/translator/c/src/qcgc/allocator.c
b/rpython/translator/c/src/qcgc/allocator.c
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/allocator.c
@@ -0,0 +1,293 @@
+#include "allocator.h"
+
+#include <assert.h>
+#include <stdbool.h>
+#include <string.h>
+
+QCGC_STATIC size_t bytes_to_cells(size_t bytes);
+
+QCGC_STATIC void bump_allocator_assign(cell_t *ptr, size_t cells);
+QCGC_STATIC cell_t *bump_allocator_allocate(size_t cells);
+QCGC_STATIC void bump_allocator_advance(size_t cells);
+
+QCGC_STATIC bool is_small(size_t cells);
+QCGC_STATIC size_t small_index(size_t cells);
+QCGC_STATIC size_t large_index(size_t cells);
+QCGC_STATIC size_t small_index_to_cells(size_t index);
+
+QCGC_STATIC cell_t *fit_allocator_allocate(size_t cells);
+QCGC_STATIC cell_t *fit_allocator_small_first_fit(size_t index, size_t cells);
+QCGC_STATIC cell_t *fit_allocator_large_fit(size_t index, size_t cells);
+QCGC_STATIC cell_t *fit_allocator_large_first_fit(size_t index, size_t cells);
+
+QCGC_STATIC bool valid_block(cell_t *ptr, size_t cells);
+
+void qcgc_allocator_initialize(void) {
+ qcgc_allocator_state.arenas =
+ qcgc_arena_bag_create(QCGC_ARENA_BAG_INIT_SIZE);
+
+ // Bump Allocator
+ qcgc_allocator_state.bump_state.bump_ptr = NULL;
+ qcgc_allocator_state.bump_state.remaining_cells = 0;
+
+ // Fit Allocator
+ for (size_t i = 0; i < QCGC_SMALL_FREE_LISTS; i++) {
+ qcgc_allocator_state.fit_state.small_free_list[i] =
+
qcgc_linear_free_list_create(QCGC_SMALL_FREE_LIST_INIT_SIZE);
+ }
+
+ for (size_t i = 0; i < QCGC_LARGE_FREE_LISTS; i++) {
+ qcgc_allocator_state.fit_state.large_free_list[i] =
+
qcgc_exp_free_list_create(QCGC_LARGE_FREE_LIST_INIT_SIZE);
+ }
+}
+
+void qcgc_allocator_destroy(void) {
+ // Fit Allocator
+ for (size_t i = 0; i < QCGC_SMALL_FREE_LISTS; i++) {
+ free(qcgc_allocator_state.fit_state.small_free_list[i]);
+ }
+
+ for (size_t i = 0; i < QCGC_LARGE_FREE_LISTS; i++) {
+ free(qcgc_allocator_state.fit_state.large_free_list[i]);
+ }
+
+ // Arenas
+ size_t arena_count = qcgc_allocator_state.arenas->count;
+ for (size_t i = 0; i < arena_count; i++) {
+ qcgc_arena_destroy(qcgc_allocator_state.arenas->items[i]);
+ }
+
+ free(qcgc_allocator_state.arenas);
+}
+
+cell_t *qcgc_allocator_allocate(size_t bytes) {
+ size_t size_in_cells = bytes_to_cells(bytes);
+#if CHECKED
+ assert(size_in_cells > 0);
+ assert(size_in_cells <= QCGC_ARENA_CELLS_COUNT -
QCGC_ARENA_FIRST_CELL_INDEX);
+#endif
+ cell_t *result;
+
+ // TODO: Implement switch for bump/fit allocator
+ if (true) {
+ result = bump_allocator_allocate(size_in_cells);
+ } else {
+ result = fit_allocator_allocate(size_in_cells);
+ }
+
+ qcgc_arena_mark_allocated(result, size_in_cells);
+#if QCGC_INIT_ZERO
+ memset(result, 0, bytes);
+#endif
+ return result;
+}
+
+void qcgc_fit_allocator_add(cell_t *ptr, size_t cells) {
+ if (cells > 0) {
+ if (is_small(cells)) {
+ size_t index = small_index(cells);
+ qcgc_allocator_state.fit_state.small_free_list[index] =
+ qcgc_linear_free_list_add(
+
qcgc_allocator_state.fit_state.small_free_list[index],
+ ptr);
+ } else {
+ size_t index = large_index(cells);
+ qcgc_allocator_state.fit_state.large_free_list[index] =
+ qcgc_exp_free_list_add(
+
qcgc_allocator_state.fit_state.large_free_list[index],
+ (struct exp_free_list_item_s)
{ptr, cells});
+ }
+ }
+}
+
+QCGC_STATIC void bump_allocator_assign(cell_t *ptr, size_t cells) {
+ qcgc_allocator_state.bump_state.bump_ptr = ptr;
+ qcgc_allocator_state.bump_state.remaining_cells = cells;
+}
+
+QCGC_STATIC void bump_allocator_advance(size_t cells) {
+ qcgc_allocator_state.bump_state.bump_ptr += cells;
+ qcgc_allocator_state.bump_state.remaining_cells -= cells;
+}
+
+QCGC_STATIC cell_t *bump_allocator_allocate(size_t cells) {
+ if (cells > qcgc_allocator_state.bump_state.remaining_cells) {
+ // Grab a new arena
+ arena_t *arena = qcgc_arena_create();
+
bump_allocator_assign(&(arena->cells[QCGC_ARENA_FIRST_CELL_INDEX]),
+ QCGC_ARENA_CELLS_COUNT -
QCGC_ARENA_FIRST_CELL_INDEX);
+ qcgc_allocator_state.arenas =
+ qcgc_arena_bag_add(qcgc_allocator_state.arenas, arena);
+ }
+ cell_t *result = qcgc_allocator_state.bump_state.bump_ptr;
+ bump_allocator_advance(cells);
+ return result;
+}
+
+QCGC_STATIC cell_t *fit_allocator_allocate(size_t cells) {
+ cell_t *result;
+
+ if (is_small(cells)) {
+ size_t index = small_index(cells);
+ result = fit_allocator_small_first_fit(index, cells);
+ } else {
+ size_t index = large_index(cells);
+ result = fit_allocator_large_fit(index, cells);
+ }
+
+ if (result == NULL) {
+ // No valid block found
+ result = bump_allocator_allocate(cells);
+ }
+
+ return result;
+}
+
+QCGC_STATIC cell_t *fit_allocator_small_first_fit(size_t index, size_t cells) {
+#if CHECKED
+ assert(small_index_to_cells(index) >= cells);
+#endif
+ cell_t *result = NULL;
+ for ( ; index < QCGC_SMALL_FREE_LISTS; index++) {
+ linear_free_list_t *free_list =
+ qcgc_allocator_state.fit_state.small_free_list[index];
+ size_t list_cell_size = small_index_to_cells(index);
+
+ while (free_list->count > 0) {
+ result = free_list->items[free_list->count - 1];
+ free_list =
qcgc_linear_free_list_remove_index(free_list,
+ free_list->count - 1);
+
+ // Check whether block is still valid
+ if (valid_block(result, list_cell_size)) {
+ qcgc_fit_allocator_add(result + cells,
list_cell_size - cells);
+ break;
+ } else {
+ result = NULL;
+ }
+ }
+
+ qcgc_allocator_state.fit_state.small_free_list[index] =
free_list;
+ if (result != NULL) {
+ return result;
+ }
+ }
+ return fit_allocator_large_first_fit(0, cells);
+}
+
+QCGC_STATIC cell_t *fit_allocator_large_fit(size_t index, size_t cells) {
+#if CHECKED
+ assert(1u<<(index + QCGC_LARGE_FREE_LIST_FIRST_EXP) <= cells);
+ assert(1u<<(index + QCGC_LARGE_FREE_LIST_FIRST_EXP + 1) > cells);
+#endif
+ exp_free_list_t *free_list =
+ qcgc_allocator_state.fit_state.large_free_list[index];
+ size_t best_fit_index = free_list->count;
+
+ cell_t *result = NULL;
+ size_t best_fit_cells = SIZE_MAX;
+ size_t i = 0;
+ while (i < free_list->count) {
+ if (valid_block(free_list->items[i].ptr,
free_list->items[i].size)) {
+ if (free_list->items[i].size >= cells &&
+ free_list->items[i].size <
best_fit_cells) {
+ result = free_list->items[i].ptr;
+ best_fit_cells = free_list->items[i].size;
+ best_fit_index = i;
+ }
+ i++;
+ } else {
+ free_list = qcgc_exp_free_list_remove_index(free_list,
i);
+ // NO i++ !
+ }
+
+ if (best_fit_cells == cells) {
+ break;
+ }
+ }
+
+ if (result != NULL) {
+ // Best fit was found
+ assert(best_fit_index < free_list->count);
+ free_list = qcgc_exp_free_list_remove_index(free_list,
best_fit_index);
+ qcgc_fit_allocator_add(result + cells, best_fit_cells - cells);
+ } else {
+ // No best fit, go for first fit
+ result = fit_allocator_large_first_fit(index + 1, cells);
+ }
+ qcgc_allocator_state.fit_state.large_free_list[index] = free_list;
+ return result;
+}
+
+QCGC_STATIC cell_t *fit_allocator_large_first_fit(size_t index, size_t cells) {
+#if CHECKED
+ assert(1u<<(index + QCGC_LARGE_FREE_LIST_FIRST_EXP) >= cells);
+#endif
+ cell_t *result = NULL;
+ for ( ; index < QCGC_LARGE_FREE_LISTS; index++) {
+ exp_free_list_t *free_list =
+ qcgc_allocator_state.fit_state.large_free_list[index];
+ while(free_list->count > 0) {
+ struct exp_free_list_item_s item =
+ free_list->items[free_list->count - 1];
+ free_list = qcgc_exp_free_list_remove_index(free_list,
+ free_list->count - 1);
+
+ // Check whether block is still valid
+ if (valid_block(item.ptr, item.size)) {
+ qcgc_fit_allocator_add(item.ptr + cells,
item.size - cells);
+ result = item.ptr;
+ break;
+ }
+ }
+ qcgc_allocator_state.fit_state.large_free_list[index] =
free_list;
+ if (result != NULL) {
+ return result;
+ }
+ }
+ return NULL;
+}
+
+QCGC_STATIC size_t bytes_to_cells(size_t bytes) {
+ return (bytes + sizeof(cell_t) - 1) / sizeof(cell_t);
+}
+
+QCGC_STATIC bool is_small(size_t cells) {
+ return cells <= QCGC_SMALL_FREE_LISTS;
+}
+
+QCGC_STATIC size_t small_index(size_t cells) {
+#if CHECKED
+ assert(is_small(cells));
+#endif
+ return cells - 1;
+}
+
+QCGC_STATIC size_t large_index(size_t cells) {
+#if CHECKED
+ assert(!is_small(cells));
+#endif
+ // shift such that the meaningless part disappears, i.e. everything that
+ // belongs into the first free list will become 1.
+ cells = cells >> QCGC_LARGE_FREE_LIST_FIRST_EXP;
+
+ // calculates floor(log(cells))
+ return (8 * sizeof(unsigned long)) - __builtin_clzl(cells) - 1;
+}
+
+QCGC_STATIC size_t small_index_to_cells(size_t index) {
+#if CHECKED
+ assert(index < QCGC_SMALL_FREE_LISTS);
+#endif
+ return index + 1;
+}
+
+QCGC_STATIC bool valid_block(cell_t *ptr, size_t cells) {
+#if CHECKED
+ assert(ptr != NULL);
+ assert(cells > 0);
+#endif
+ return (qcgc_arena_get_blocktype(ptr) == BLOCK_FREE &&
+ qcgc_arena_get_blocktype(ptr + cells) != BLOCK_EXTENT);
+}
diff --git a/rpython/translator/c/src/qcgc/allocator.h
b/rpython/translator/c/src/qcgc/allocator.h
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/allocator.h
@@ -0,0 +1,75 @@
+#pragma once
+
+#include "config.h"
+
+#include <stddef.h>
+
+#include "arena.h"
+#include "bag.h"
+#include "object.h"
+
+/**
+ * Free lists:
+ *
+ * Small free lists:
+ * +---+---+-----+----+
+ * index: | 0 | 1 | ... | 30 |
+ * +---+---+-----+----+
+ * size (cells): | 1 | 2 | ... | 31 |
+ * +---+---+-----+----+
+ *
+ * Large free lists:
+ * +-----+-----+-----+---------+
+ * index: | 0 | 1 | ... | x |
+ * +-----+-----+-----+---------+
+ * minimal size (cells): | 2^5 | 2^6 | ... | 2^(x+5) |
+ * +-----+-----+-----+---------+
+ *
+ * where x is chosen such that x + 5 + 1 = QCGC_ARENA_SIZE_EXP - 4 (i.e. the
+ * next bin would hold chunks that have the size of at least one arena size,
+ * which is impossible as an arena contains overhead)
+ */
+
+#define QCGC_LARGE_FREE_LISTS (QCGC_ARENA_SIZE_EXP - 4 -
QCGC_LARGE_FREE_LIST_FIRST_EXP)
+
+#define QCGC_SMALL_FREE_LISTS ((1<<QCGC_LARGE_FREE_LIST_FIRST_EXP) - 1)
+
+struct qcgc_allocator_state {
+ arena_bag_t *arenas;
+ struct bump_state {
+ cell_t *bump_ptr;
+ size_t remaining_cells;
+ } bump_state;
+ struct fit_state {
+ linear_free_list_t *small_free_list[QCGC_SMALL_FREE_LISTS];
+ exp_free_list_t *large_free_list[QCGC_LARGE_FREE_LISTS];
+ } fit_state;
+} qcgc_allocator_state;
+
+/**
+ * Initialize allocator
+ */
+void qcgc_allocator_initialize(void);
+
+/**
+ * Destroy allocator
+ */
+void qcgc_allocator_destroy(void);
+
+/**
+ * Allocate new memory region
+ *
+ * @param bytes Desired size of the memory region in bytes
+ * @return Pointer to memory large enough to hold size bytes, NULL in case
of
+ * errors, already zero initialized if QCGC_INIT_ZERO is
set
+ */
+cell_t *qcgc_allocator_allocate(size_t bytes);
+
+
+/**
+ * Add memory to free lists
+ *
+ * @param ptr Pointer to memory region
+ * @param cells Size of memory region in cells
+ */
+void qcgc_fit_allocator_add(cell_t *ptr, size_t cells);
diff --git a/rpython/translator/c/src/qcgc/arena.c
b/rpython/translator/c/src/qcgc/arena.c
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/arena.c
@@ -0,0 +1,322 @@
+#include "arena.h"
+
+#include <assert.h>
+#include <stdlib.h>
+#include <sys/mman.h>
+#include <unistd.h>
+
+#include "allocator.h"
+#include "event_logger.h"
+
+/**
+ * Internal functions
+ */
+QCGC_STATIC blocktype_t get_blocktype(arena_t *arena, size_t index);
+QCGC_STATIC void set_blocktype(arena_t *arena, size_t index, blocktype_t type);
+
+arena_t *qcgc_arena_create(void) {
+ qcgc_event_logger_log(EVENT_NEW_ARENA, 0, NULL);
+
+ arena_t *result;
+ // Linux: MAP_ANONYMOUS is initialized to zero
+ cell_t *mem = (cell_t *) mmap(0, 2 * QCGC_ARENA_SIZE,
+ PROT_READ | PROT_WRITE,
+ MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
+ if (mem == MAP_FAILED) {
+ // ERROR: OUT OF MEMORY
+ return NULL;
+ }
+ if (mem != qcgc_arena_addr(mem)->cells) {
+ // Not aligned -> align
+ cell_t *aligned_mem = (cell_t *)(
+ (intptr_t) qcgc_arena_addr(mem) +
QCGC_ARENA_SIZE);
+ size_t size_before = (size_t)((intptr_t) aligned_mem -
(intptr_t) mem);
+ size_t size_after = QCGC_ARENA_SIZE - size_before;
+
+ munmap((void *) mem, size_before);
+ munmap((void *)((intptr_t) aligned_mem + QCGC_ARENA_SIZE),
size_after);
+ result = (arena_t *) aligned_mem;
+ } else {
+ // free second half
+ munmap((void *)((intptr_t) mem + QCGC_ARENA_SIZE),
QCGC_ARENA_SIZE);
+ result = (arena_t *) mem;
+ }
+
+ // Init bitmaps: One large free block
+ qcgc_arena_set_bitmap_entry(result->mark_bitmap,
QCGC_ARENA_FIRST_CELL_INDEX, true);
+
+ // Create gray stack
+ result->gray_stack = qcgc_gray_stack_create(QCGC_GRAY_STACK_INIT_SIZE);
+ return result;
+}
+
+void qcgc_arena_destroy(arena_t *arena) {
+#if CHECKED
+ assert(arena != NULL);
+#endif
+ free(arena->gray_stack);
+ munmap((void *) arena, QCGC_ARENA_SIZE);
+}
+
+arena_t *qcgc_arena_addr(cell_t *ptr) {
+ return (arena_t *)((intptr_t) ptr & ~(QCGC_ARENA_SIZE - 1));
+}
+
+size_t qcgc_arena_cell_index(cell_t *ptr) {
+ return (size_t)((intptr_t) ptr & (QCGC_ARENA_SIZE - 1)) >> 4;
+}
+
+bool qcgc_arena_get_bitmap_entry(uint8_t *bitmap, size_t index) {
+#if CHECKED
+ assert(bitmap != NULL);
+#endif
+ return (((bitmap[index / 8] >> (index % 8)) & 0x1) == 0x01);
+}
+
+void qcgc_arena_set_bitmap_entry(uint8_t *bitmap, size_t index, bool value) {
+#if CHECKED
+ assert(bitmap != NULL);
+#endif
+ if (value) {
+ bitmap[index / 8] |= 1<<(index % 8);
+ } else {
+ bitmap[index / 8] &= ~(1<<(index % 8));
+ }
+}
+
+QCGC_STATIC blocktype_t get_blocktype(arena_t *arena, size_t index) {
+#if CHECKED
+ assert(arena != NULL);
+#endif
+ uint8_t block_bit = qcgc_arena_get_bitmap_entry(arena->block_bitmap,
index);
+ uint8_t mark_bit = qcgc_arena_get_bitmap_entry(arena->mark_bitmap,
index);
+
+ if (block_bit) {
+ if (mark_bit) {
+ return BLOCK_BLACK;
+ } else {
+ return BLOCK_WHITE;
+ }
+ } else {
+ if (mark_bit) {
+ return BLOCK_FREE;
+ } else {
+ return BLOCK_EXTENT;
+ }
+ }
+}
+
+blocktype_t qcgc_arena_get_blocktype(cell_t *ptr) {
+ size_t index = qcgc_arena_cell_index(ptr);
+ arena_t *arena = qcgc_arena_addr(ptr);
+
+ return get_blocktype(arena, index);
+}
+
+QCGC_STATIC void set_blocktype(arena_t *arena, size_t index, blocktype_t type)
{
+#if CHECKED
+ assert(arena != NULL);
+#endif
+ switch(type) {
+ case BLOCK_EXTENT:
+ qcgc_arena_set_bitmap_entry(arena->block_bitmap, index,
false);
+ qcgc_arena_set_bitmap_entry(arena->mark_bitmap, index,
false);
+ break;
+ case BLOCK_FREE:
+ qcgc_arena_set_bitmap_entry(arena->block_bitmap, index,
false);
+ qcgc_arena_set_bitmap_entry(arena->mark_bitmap, index,
true);
+ break;
+ case BLOCK_WHITE:
+ qcgc_arena_set_bitmap_entry(arena->block_bitmap, index,
true);
+ qcgc_arena_set_bitmap_entry(arena->mark_bitmap, index,
false);
+ break;
+ case BLOCK_BLACK:
+ qcgc_arena_set_bitmap_entry(arena->mark_bitmap, index,
true);
+ qcgc_arena_set_bitmap_entry(arena->block_bitmap, index,
true);
+ break;
+ }
+}
+
+void qcgc_arena_set_blocktype(cell_t *ptr, blocktype_t type) {
+ size_t index = qcgc_arena_cell_index(ptr);
+ arena_t *arena = qcgc_arena_addr(ptr);
+ set_blocktype(arena, index, type);
+}
+
+void qcgc_arena_mark_allocated(cell_t *ptr, size_t cells) {
+ size_t index = qcgc_arena_cell_index(ptr);
+ arena_t *arena = qcgc_arena_addr(ptr);
+ set_blocktype(arena, index, BLOCK_WHITE);
+ size_t index_of_next_block = index + cells;
+ if (index_of_next_block < QCGC_ARENA_CELLS_COUNT &&
+ get_blocktype(arena, index_of_next_block) ==
BLOCK_EXTENT) {
+ set_blocktype(arena, index_of_next_block, BLOCK_FREE);
+ }
+}
+
+void qcgc_arena_mark_free(cell_t *ptr) {
+ qcgc_arena_set_blocktype(ptr, BLOCK_FREE);
+ // No coalescing, collector will do this
+}
+
+bool qcgc_arena_sweep(arena_t *arena) {
+#if CHECKED
+ assert(arena != NULL);
+#endif
+ bool free = true;
+ bool coalesce = false;
+ size_t last_free_cell = QCGC_ARENA_FIRST_CELL_INDEX;
+ for (size_t cell = QCGC_ARENA_FIRST_CELL_INDEX;
+ cell < QCGC_ARENA_CELLS_COUNT;
+ cell++) {
+ switch (qcgc_arena_get_blocktype(arena->cells + cell)) {
+ case BLOCK_EXTENT:
+ break;
+ case BLOCK_FREE:
+ if (coalesce) {
+ set_blocktype(arena, cell,
BLOCK_EXTENT);
+ } else {
+ last_free_cell = cell;
+ }
+ coalesce = true;
+ break;
+ case BLOCK_WHITE:
+ if (coalesce) {
+ set_blocktype(arena, cell,
BLOCK_EXTENT);
+ } else {
+ set_blocktype(arena, cell, BLOCK_FREE);
+ last_free_cell = cell;
+ }
+ coalesce = true;
+ break;
+ case BLOCK_BLACK:
+ set_blocktype(arena, cell, BLOCK_WHITE);
+ if (coalesce) {
+
qcgc_fit_allocator_add(&(arena->cells[last_free_cell]),
+ cell - last_free_cell);
+ }
+ free = false;
+ coalesce = false;
+ break;
+ }
+ }
+ if (coalesce && !free) {
+ qcgc_fit_allocator_add(&(arena->cells[last_free_cell]),
+ QCGC_ARENA_CELLS_COUNT
- last_free_cell);
+ }
+ return free;
+}
+
+bool qcgc_arena_is_empty(arena_t *arena) {
+#if CHECKED
+ assert(arena != NULL);
+#endif
+ for (size_t cell = QCGC_ARENA_FIRST_CELL_INDEX;
+ cell < QCGC_ARENA_CELLS_COUNT;
+ cell++) {
+ switch (qcgc_arena_get_blocktype((void *) &arena->cells[cell]))
{
+ case BLOCK_WHITE: // Fall through
+ case BLOCK_BLACK:
+ return false;
+
+ default:
+ break;
+ }
+ }
+ return true;
+}
+
+bool qcgc_arena_is_coalesced(arena_t *arena) {
+#if CHECKED
+ assert(arena != NULL);
+#endif
+ bool prev_was_free = false;
+ for (size_t cell = QCGC_ARENA_FIRST_CELL_INDEX;
+ cell < QCGC_ARENA_CELLS_COUNT;
+ cell++) {
+ switch (qcgc_arena_get_blocktype((void *) &arena->cells[cell]))
{
+ case BLOCK_WHITE: // Fall through
+ case BLOCK_BLACK:
+ prev_was_free = false;
+ break;
+
+ case BLOCK_FREE:
+ if (prev_was_free) {
+ return false;
+ } else {
+ prev_was_free = true;
+ }
+ break;
+
+ case BLOCK_EXTENT:
+ break;
+ }
+ }
+ return true;
+}
+
+size_t qcgc_arena_free_blocks(arena_t *arena) {
+#if CHECKED
+ assert(arena != NULL);
+#endif
+ size_t result = 0;
+ for (size_t cell = QCGC_ARENA_FIRST_CELL_INDEX;
+ cell < QCGC_ARENA_CELLS_COUNT;
+ cell++) {
+ switch (qcgc_arena_get_blocktype((void *) &arena->cells[cell]))
{
+ case BLOCK_WHITE: // Fall through
+ case BLOCK_BLACK:
+ case BLOCK_EXTENT:
+ break;
+
+ case BLOCK_FREE:
+ result++;
+ break;
+ }
+ }
+ return result;
+}
+
+size_t qcgc_arena_white_blocks(arena_t *arena) {
+#if CHECKED
+ assert(arena != NULL);
+#endif
+ size_t result = 0;
+ for (size_t cell = QCGC_ARENA_FIRST_CELL_INDEX;
+ cell < QCGC_ARENA_CELLS_COUNT;
+ cell++) {
+ switch (qcgc_arena_get_blocktype((void *) &arena->cells[cell]))
{
+ case BLOCK_BLACK: // Fall through
+ case BLOCK_EXTENT:
+ case BLOCK_FREE:
+ break;
+
+ case BLOCK_WHITE:
+ result++;
+ break;
+ }
+ }
+ return result;
+}
+
+size_t qcgc_arena_black_blocks(arena_t *arena) {
+#if CHECKED
+ assert(arena != NULL);
+#endif
+ size_t result = 0;
+ for (size_t cell = QCGC_ARENA_FIRST_CELL_INDEX;
+ cell < QCGC_ARENA_CELLS_COUNT;
+ cell++) {
+ switch (qcgc_arena_get_blocktype((void *) &arena->cells[cell]))
{
+ case BLOCK_WHITE: // Fall through
+ case BLOCK_FREE:
+ case BLOCK_EXTENT:
+ break;
+
+ case BLOCK_BLACK:
+ result++;
+ break;
+ }
+ }
+ return result;
+}
diff --git a/rpython/translator/c/src/qcgc/arena.h
b/rpython/translator/c/src/qcgc/arena.h
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/arena.h
@@ -0,0 +1,188 @@
+/**
+ * @file arena.h
+ */
+
+#pragma once
+
+#include "config.h"
+
+#include <stdbool.h>
+#include <stdint.h>
+#include <sys/types.h>
+
+#include "gray_stack.h"
+
+#define QCGC_ARENA_SIZE (1<<QCGC_ARENA_SIZE_EXP)
+
+#define QCGC_ARENA_BITMAP_SIZE (1<<(QCGC_ARENA_SIZE_EXP - 7)) // 1 / 128
+#define QCGC_ARENA_CELLS_COUNT (1<<(QCGC_ARENA_SIZE_EXP - 4))
+
+#define QCGC_ARENA_FIRST_CELL_INDEX (1<<(QCGC_ARENA_SIZE_EXP - 10))
+
+/**
+ * @typedef cell_t
+ * The smallest unit of memory that can be addressed and allocated in arenas.
+ */
+typedef uint8_t cell_t[16];
+
+/**
+ * @typedef arena_t
+ * Arena object
+ */
+typedef union {
+ struct {
+ union {
+ gray_stack_t *gray_stack;
+ uint8_t block_bitmap[QCGC_ARENA_BITMAP_SIZE];
+ };
+ uint8_t mark_bitmap[QCGC_ARENA_BITMAP_SIZE];
+ };
+ cell_t cells[QCGC_ARENA_CELLS_COUNT];
+} arena_t;
+
+/**
+ * @typedef blocktype_t
+ * Blocktypes:
+ * - BLOCK_EXTENT Extension of previous block
+ * - BLOCK_FREE Free block
+ * - BLOCK_WHITE Allocated block, marked white
+ * - BLOCK_BLACK Allocated block, marked black
+ */
+typedef enum blocktype {
+ BLOCK_EXTENT,
+ BLOCK_FREE,
+ BLOCK_WHITE,
+ BLOCK_BLACK,
+} blocktype_t;
+
+/**
+ * Create a new arena.
+ *
+ * @return Pointer to new arena, NULL in case of errors
+ */
+arena_t *qcgc_arena_create(void);
+
+/**
+ * Destroys an arena (return to OS).
+ *
+ * @param arena The arena to destroy
+ */
+void qcgc_arena_destroy(arena_t *arena);
+
+/**
+ * Arena pointer for given cell.
+ *
+ * @param ptr Pointer to cell for which you want to know the
corresponding
+ * arena
+ * @return The arena the pointer belongs to
+ */
+arena_t *qcgc_arena_addr(cell_t *ptr);
+
+/**
+ * Index of cell in arena.
+ *
+ * @param ptr Pointer to cell for which you want to know the
cell index
+ * @return Index of the cell to which ptr points to
+ */
+size_t qcgc_arena_cell_index(cell_t *ptr);
+
+/**
+ * Get bitmap value for given bitmap and cell index.
+ *
+ * @param bitmap Bitmap
+ * @param index Index of cell
+ * @return true if bitmap entry is set, false otherwise
+ */
+bool qcgc_arena_get_bitmap_entry(uint8_t *bitmap, size_t index);
+
+/**
+ * Set bitmap value for given bitmap and cell index.
+ *
+ * @param bitmap Bitmap
+ * @param index Index of cell
+ * @param value true to set entry, false to reset entry
+ */
+void qcgc_arena_set_bitmap_entry(uint8_t *bitmap, size_t index, bool value);
+
+/**
+ * Get blocktype.
+ *
+ * @param ptr Pointer to cell for which you want to know the
blocktype
+ * @return Blocktype
+ */
+blocktype_t qcgc_arena_get_blocktype(cell_t *ptr);
+
+/**
+ * Set blocktype.
+ *
+ * @param ptr Pointer to cell for which you want to set the
blocktype
+ * @param type Blocktype that should be set
+ */
+void qcgc_arena_set_blocktype(cell_t *ptr, blocktype_t type);
+
+/**
+ * Mark ptr as allocated area with given size.
+ *
+ * @param ptr Pointer to first cell of area
+ * @param cells Size in cells
+ */
+void qcgc_arena_mark_allocated(cell_t *ptr, size_t cells);
+
+/**
+ * Mark cell ptr point to as free (no coalescing).
+ *
+ * @param ptr Pointer to cell that should be marked as free
+ */
+void qcgc_arena_mark_free(cell_t *ptr);
+
+/**
+ * Sweep given arena.
+ *
+ * @param arena Arena
+ * @return Whether arena is empty after sweeping
+ */
+bool qcgc_arena_sweep(arena_t *arena);
+
+/*******************************************************************************
+ * Debug functions
*
+
******************************************************************************/
+
+/**
+ * Check whether arena is empty.
+ *
+ * @param arena Arena
+ * @return true iff given arena is empty
+ */
+bool qcgc_arena_is_empty(arena_t *arena);
+
+/**
+ * Check whether arena is coalesced (no consecutive free blocks).
+ *
+ * @param arena Arena
+ * @return true iff given arena is coalesced
+ */
+bool qcgc_arena_is_coalesced(arena_t *arena);
+
+/**
+ * Count free blocks.
+ *
+ * @param arena Arena
+ * @return Number of free blocks
+ */
+size_t qcgc_arena_free_blocks(arena_t *arena);
+
+/**
+ * Count white blocks.
+ *
+ * @param arena Arena
+ * @return Number of white blocks
+ */
+size_t qcgc_arena_white_blocks(arena_t *arena);
+
+/**
+ * Count black blocks.
+ *
+ * @param arena Arena
+ * @return Number of black blocks
+ */
+size_t qcgc_arena_black_blocks(arena_t *arena);
diff --git a/rpython/translator/c/src/qcgc/bag.c
b/rpython/translator/c/src/qcgc/bag.c
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/bag.c
@@ -0,0 +1,7 @@
+#include "bag.h"
+
+#include <assert.h>
+
+DEFINE_BAG(arena_bag, arena_t *);
+DEFINE_BAG(linear_free_list, cell_t *);
+DEFINE_BAG(exp_free_list, struct exp_free_list_item_s);
diff --git a/rpython/translator/c/src/qcgc/bag.h
b/rpython/translator/c/src/qcgc/bag.h
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/bag.h
@@ -0,0 +1,82 @@
+#pragma once
+
+#include "config.h"
+
+#include <stddef.h>
+#include <stdlib.h>
+
+#include "arena.h"
+
+#define DECLARE_BAG(name, type)
\
+typedef struct name##_s {
\
+ size_t size;
\
+ size_t count;
\
+ type items[];
\
+} name##_t;
\
+
\
+name##_t *qcgc_##name##_create(size_t size);
\
+name##_t *qcgc_##name##_add(name##_t *self, type item);
\
+name##_t *qcgc_##name##_remove_index(name##_t *self, size_t index);
+
+#define DEFINE_BAG(name, type)
\
+QCGC_STATIC size_t name##_size(size_t size);
\
+QCGC_STATIC name##_t *name##_grow(name##_t *self);
\
+QCGC_STATIC name##_t *name##_shrink(name##_t *self);
\
+
\
+name##_t *qcgc_##name##_create(size_t size) {
\
+ name##_t *result = (name##_t *) malloc(name##_size(size));
\
+ result->size = size;
\
+ result->count = 0;
\
+ return result;
\
+}
\
+
\
+name##_t *qcgc_##name##_add(name##_t *self, type item) {
\
+ if (self->count >= self->size) {
\
+ self = name##_grow(self);
\
+ }
\
+ self->items[self->count++] = item;
\
+ return self;
\
+}
\
+
\
+name##_t *qcgc_##name##_remove_index(name##_t *self, size_t index) {
\
+ if (index + 1 < self->count) {
\
+ self->items[index] = self->items[self->count - 1];
\
+ }
\
+ self->count--;
\
+
\
+ if (self->count < self->size / 4) {
\
+ self = name##_shrink(self);
\
+ }
\
+ return self;
\
+}
\
+
\
+QCGC_STATIC name##_t *name##_grow(name##_t *self) {
\
+ name##_t *new_self = (name##_t *) realloc(self,
\
+ name##_size(self->size * 2));
\
+ assert(new_self != NULL);
\
+ self = new_self;
\
+ self->size *= 2;
\
+ return self;
\
+}
\
+
\
+QCGC_STATIC name##_t *name##_shrink(name##_t *self) {
\
+ name##_t *new_self = (name##_t *) realloc(self,
\
+ name##_size(self->size / 2));
\
+ assert(new_self != NULL);
\
+ self = new_self;
\
+ self->size /= 2;
\
+ return self;
\
+}
\
+
\
+QCGC_STATIC size_t name##_size(size_t size) {
\
+ return sizeof(name##_t) + size * sizeof(type);
\
+}
+
+struct exp_free_list_item_s {
+ cell_t *ptr;
+ size_t size;
+};
+
+DECLARE_BAG(arena_bag, arena_t *);
+DECLARE_BAG(linear_free_list, cell_t *);
+DECLARE_BAG(exp_free_list, struct exp_free_list_item_s);
diff --git a/rpython/translator/c/src/qcgc/config.h
b/rpython/translator/c/src/qcgc/config.h
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/config.h
@@ -0,0 +1,39 @@
+#pragma once
+
+#define CHECKED 1 //
Enable runtime sanity checks
+
+#define QCGC_INIT_ZERO 1 // Init new
objects with zero bytes
+
+/**
+ * Event logger
+ */
+#define EVENT_LOG 1 //
Enable event log
+#define LOGFILE "./qcgc_events.log" // Default logfile
+#define LOG_ALLOCATION 0 // Enable
allocation log (warning:
+
// significant performance impact)
+
+#define QCGC_SHADOWSTACK_SIZE 128 // Number of initial
entries for
+
// shadow stack
+#define QCGC_ARENA_BAG_INIT_SIZE 16 // Initial size of the
arena bag
+#define QCGC_ARENA_SIZE_EXP 20 // Between 16 (64kB)
and 20 (1MB)
+#define QCGC_LARGE_ALLOC_THRESHOLD 1<<14
+#define QCGC_MARK_LIST_SEGMENT_SIZE 64 // TODO: Tune for performance
+#define QCGC_GRAY_STACK_INIT_SIZE 128 // TODO: Tune for performance
+#define QCGC_INC_MARK_MIN 64 // TODO: Tune for
performance
+
+/**
+ * Fit allocator
+ */
+#define QCGC_LARGE_FREE_LIST_FIRST_EXP 5 // First exponent of large free
list
+#define QCGC_LARGE_FREE_LIST_INIT_SIZE 4 // Initial size for large free
lists
+#define QCGC_SMALL_FREE_LIST_INIT_SIZE 16 // Initial size for small free
lists
+
+/**
+ * DO NOT MODIFY BELOW HERE
+ */
+
+#ifdef TESTING
+#define QCGC_STATIC
+#else
+#define QCGC_STATIC static
+#endif
diff --git a/rpython/translator/c/src/qcgc/event_logger.c
b/rpython/translator/c/src/qcgc/event_logger.c
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/event_logger.c
@@ -0,0 +1,81 @@
+#include "event_logger.h"
+
+#include <assert.h>
+#include <time.h>
+#include <stdio.h>
+
+#if EVENT_LOG
+static struct {
+ FILE *logfile;
+} event_logger_state;
+
+#endif
+
+void qcgc_event_logger_initialize(void) {
+#if EVENT_LOG
+ event_logger_state.logfile = fopen(LOGFILE, "w");
+ qcgc_event_logger_log(EVENT_LOG_START, 0, NULL);
+
+ if (event_logger_state.logfile == NULL) {
+ fprintf(stderr, "%s\n", "Failed to create logfile.");
+ }
+#endif
+}
+
+void qcgc_event_logger_destroy(void) {
+#if EVENT_LOG
+ qcgc_event_logger_log(EVENT_LOG_STOP, 0, NULL);
+
+ if (event_logger_state.logfile != NULL) {
+ fflush(event_logger_state.logfile);
+ fclose(event_logger_state.logfile);
+ event_logger_state.logfile = NULL;
+ }
+#endif
+}
+
+void qcgc_event_logger_log(enum event_e event, uint32_t additional_data_size,
+ uint8_t *additional_data) {
+#if EVENT_LOG
+#if CHECKED
+ assert((additional_data_size == 0) == (additional_data == NULL));
+#endif // CHECKED
+ struct {
+ uint32_t sec;
+ uint32_t nsec;
+ uint8_t event_id;
+ uint32_t additional_data_size;
+ } __attribute__ ((packed)) log_entry;
+
+ if (event_logger_state.logfile != NULL) {
+ struct timespec t;
+ clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t);
+
+ log_entry.sec = (uint32_t) t.tv_sec;
+ log_entry.nsec = (uint32_t) t.tv_nsec;
+ log_entry.event_id = (uint8_t) event;
+ log_entry.additional_data_size = additional_data_size;
+
+ // The size and nmemb fields are flipped intentionally
+ int result = 0;
+ result = fwrite(&log_entry, sizeof(log_entry), 1,
+ event_logger_state.logfile);
+ if (result != 1) {
+ fprintf(stderr, "%s\n", "Failed to write log entry.");
+ event_logger_state.logfile = NULL;
+ return;
+ }
+ if (additional_data_size > 0) {
+ result = fwrite(additional_data, additional_data_size,
1,
+ event_logger_state.logfile);
+
+ if (result != 1) {
+ fprintf(stderr, "%s\n", "Failed to write
additional data.");
+ event_logger_state.logfile = NULL;
+ return;
+ }
+ }
+ }
+
+#endif // EVENT_LOG
+}
diff --git a/rpython/translator/c/src/qcgc/event_logger.h
b/rpython/translator/c/src/qcgc/event_logger.h
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/event_logger.h
@@ -0,0 +1,42 @@
+#pragma once
+
+#include "config.h"
+
+#include <stddef.h>
+#include <stdint.h>
+
+/**
+ * All events
+ */
+enum event_e {
+ EVENT_LOG_START, // = 0
+ EVENT_LOG_STOP,
+
+ EVENT_SWEEP_START,
+ EVENT_SWEEP_DONE,
+
+ EVENT_ALLOCATE_START,
+ EVENT_ALLOCATE_DONE, // = 5
+
+ EVENT_NEW_ARENA,
+
+ EVENT_MARK_START,
+ EVENT_INCMARK_START,
+ EVENT_MARK_DONE,
+};
+
+/**
+ * Initialize logger
+ */
+void qcgc_event_logger_initialize(void);
+
+/**
+ * Destroy logger
+ */
+void qcgc_event_logger_destroy(void);
+
+/**
+ * Log event
+ */
+void qcgc_event_logger_log(enum event_e event, uint32_t additional_data_size,
+ uint8_t *additional_data);
diff --git a/rpython/translator/c/src/qcgc/gc_state.h
b/rpython/translator/c/src/qcgc/gc_state.h
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/gc_state.h
@@ -0,0 +1,29 @@
+#pragma once
+
+#include <stddef.h>
+
+#include "shadow_stack.h"
+
+/**
+ * @typedef gc_state_t
+ * Garbage collection states.
+ * - GC_PAUSE No gc in progress
+ * - GC_MARK Currently marking
+ * - GC_COLLECT Currently collecting
+ */
+typedef enum gc_phase {
+ GC_PAUSE,
+ GC_MARK,
+ GC_COLLECT,
+} gc_phase_t;
+
+/**
+ * @var qcgc_state
+ *
+ * Global state of the garbage collector
+ */
+struct qcgc_state {
+ shadow_stack_t *shadow_stack;
+ size_t gray_stack_size;
+ gc_phase_t phase;
+} qcgc_state;
diff --git a/rpython/translator/c/src/qcgc/gray_stack.c
b/rpython/translator/c/src/qcgc/gray_stack.c
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/gray_stack.c
@@ -0,0 +1,60 @@
+#include "gray_stack.h"
+
+#include <assert.h>
+#include <stdlib.h>
+
+#include "gc_state.h"
+
+QCGC_STATIC size_t gray_stack_size(size_t size);
+QCGC_STATIC gray_stack_t *gray_stack_grow(gray_stack_t *stack);
+QCGC_STATIC gray_stack_t *gray_stack_shrink(gray_stack_t *stack);
+
+gray_stack_t *qcgc_gray_stack_create(size_t size) {
+ gray_stack_t *result = (gray_stack_t *) malloc(gray_stack_size(size));
+ result->size = size;
+ result->index = 0;
+ return result;
+}
+
+gray_stack_t *qcgc_gray_stack_push(gray_stack_t *stack, object_t *item) {
+ if (stack->size == stack->index) {
+ stack = gray_stack_grow(stack);
+ }
+ stack->items[stack->index] = item;
+ stack->index++;
+ qcgc_state.gray_stack_size++;
+ return stack;
+}
+
+object_t *qcgc_gray_stack_top(gray_stack_t *stack) {
+#if CHECKED
+ assert(stack->index != 0);
+#endif
+ return stack->items[stack->index - 1];
+}
+
+gray_stack_t *qcgc_gray_stack_pop(gray_stack_t *stack) {
+ // TODO: Add lower bound for size (config.h)
+ if (stack->index < stack->size / 4) {
+ stack = gray_stack_shrink(stack);
+ }
+ stack->index--;
+ qcgc_state.gray_stack_size--;
+ return stack;
+}
+
+QCGC_STATIC size_t gray_stack_size(size_t size) {
+ return (sizeof(gray_stack_t) + size * sizeof(object_t *));
+}
+
+QCGC_STATIC gray_stack_t *gray_stack_grow(gray_stack_t *stack) {
+ stack = (gray_stack_t *) realloc(stack, gray_stack_size(stack->size *
2));
+ stack->size *= 2;
+ return stack;
+}
+
+QCGC_STATIC gray_stack_t *gray_stack_shrink(gray_stack_t *stack) {
+ stack = (gray_stack_t *) realloc(stack, gray_stack_size(stack->size /
2));
+ stack->size /= 2;
+ return stack;
+}
diff --git a/rpython/translator/c/src/qcgc/gray_stack.h
b/rpython/translator/c/src/qcgc/gray_stack.h
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/gray_stack.h
@@ -0,0 +1,19 @@
+#pragma once
+
+#include "config.h"
+
+#include <stddef.h>
+
+#include "object.h"
+
+typedef struct gray_stack_s {
+ size_t index;
+ size_t size;
+ object_t *items[];
+} gray_stack_t;
+
+gray_stack_t *qcgc_gray_stack_create(size_t size);
+
+gray_stack_t *qcgc_gray_stack_push(gray_stack_t *stack, object_t *item);
+object_t *qcgc_gray_stack_top(gray_stack_t *stack);
+gray_stack_t *qcgc_gray_stack_pop(gray_stack_t *stack);
diff --git a/rpython/translator/c/src/qcgc/mark_list.c
b/rpython/translator/c/src/qcgc/mark_list.c
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/mark_list.c
@@ -0,0 +1,180 @@
+#include "mark_list.h"
+
+#include <assert.h>
+
+#include <stdlib.h>
+#include <string.h>
+
+QCGC_STATIC mark_list_t *qcgc_mark_list_grow(mark_list_t *list);
+QCGC_STATIC void qcgc_mark_list_check_invariant(mark_list_t *list);
+
+mark_list_t *qcgc_mark_list_create(size_t initial_size) {
+ size_t length = (initial_size + QCGC_MARK_LIST_SEGMENT_SIZE - 1) /
QCGC_MARK_LIST_SEGMENT_SIZE;
+ length += (size_t) length == 0;
+ mark_list_t *result = (mark_list_t *)
+ malloc(sizeof(mark_list_t) + length * sizeof(object_t **));
+ result->head = 0;
+ result->tail = 0;
+ result->length = length;
+ result->insert_index = 0;
+ result->count = 0;
+ result->segments[result->head] = (object_t **)
+ calloc(QCGC_MARK_LIST_SEGMENT_SIZE, sizeof(object_t *));
+#if CHECKED
+ qcgc_mark_list_check_invariant(result);
+#endif
+ return result;
+}
+
+void qcgc_mark_list_destroy(mark_list_t *list) {
+#if CHECKED
+ qcgc_mark_list_check_invariant(list);
+#endif
+
+ size_t i = list->head;
+ while (i != list->tail) {
+ free(list->segments[i]);
+ i = (i + 1) % list->length;
+ }
+ free(list->segments[list->tail]);
+ free(list);
+}
+
+mark_list_t *qcgc_mark_list_push(mark_list_t *list, object_t *object) {
+#if CHECKED
+ assert(list != NULL);
+ assert(object != NULL);
+
+ qcgc_mark_list_check_invariant(list);
+ size_t old_count = list->count;
+#endif
+ if (list->insert_index >= QCGC_MARK_LIST_SEGMENT_SIZE) {
+ if ((list->tail + 1) % list->length == list->head) {
+ list = qcgc_mark_list_grow(list);
+ }
+ list->insert_index = 0;
+ list->tail = (list->tail + 1) % list->length;
+ list->segments[list->tail] = (object_t **)
+ calloc(QCGC_MARK_LIST_SEGMENT_SIZE, sizeof(object_t *));
+ }
+ list->segments[list->tail][list->insert_index] = object;
+ list->insert_index++;
+ list->count++;
+#if CHECKED
+ assert(list->count == old_count + 1);
+ assert(list->segments[list->tail][list->insert_index - 1] == object);
+ qcgc_mark_list_check_invariant(list);
+#endif
+ return list;
+}
+
+mark_list_t *qcgc_mark_list_push_all(mark_list_t *list,
+ object_t **objects, size_t count) {
+#if CHECKED
+ assert(list != NULL);
+ assert(objects != NULL);
+
+ qcgc_mark_list_check_invariant(list);
+
+ size_t old_count = list->count;
+ for (size_t i = 0; i < count; i++) {
+ assert(objects[i] != NULL);
+ }
+#endif
+ // FIXME: Optimize or remove
+ for (size_t i = 0; i < count; i++) {
+ list = qcgc_mark_list_push(list, objects[i]);
+ }
+#if CHECKED
+ assert(list->count == old_count + count);
+ qcgc_mark_list_check_invariant(list);
+#endif
+ return list;
+}
+
+object_t **qcgc_mark_list_get_head_segment(mark_list_t *list) {
+#if CHECKED
+ assert(list != NULL);
+ assert(list->segments[list->head] != NULL);
+ qcgc_mark_list_check_invariant(list);
+#endif
+ return list->segments[list->head];
+}
+
+mark_list_t *qcgc_mark_list_drop_head_segment(mark_list_t *list) {
+#if CHECKED
+ assert(list != NULL);
+ size_t old_head = list->head;
+ size_t old_tail = list->tail;
+ qcgc_mark_list_check_invariant(list);
+#endif
+ if (list->head != list->tail) {
+ free(list->segments[list->head]);
+ list->segments[list->head] = NULL;
+ list->head = (list->head + 1) % list->length;
+ list->count -= QCGC_MARK_LIST_SEGMENT_SIZE;
+ } else {
+ memset(list->segments[list->head], 0,
+ sizeof(object_t *) *
QCGC_MARK_LIST_SEGMENT_SIZE);
+ list->insert_index = 0;
+ list->count = 0;
+ }
+#if CHECKED
+ assert(old_tail == list->tail);
+ if (old_head == old_tail) {
+ assert(old_head == list->head);
+ } else {
+ assert((old_head + 1) % list->length == list->head);
+ }
+ qcgc_mark_list_check_invariant(list);
+#endif
+ return list;
+}
+
+QCGC_STATIC mark_list_t *qcgc_mark_list_grow(mark_list_t *list) {
+#if CHECKED
+ assert(list != NULL);
+ size_t old_length = list->length;
+ size_t old_tail = list->tail;
+ qcgc_mark_list_check_invariant(list);
+#endif
+ mark_list_t *new_list = (mark_list_t *) realloc(list,
+ sizeof(mark_list_t) + 2 * list->length *
sizeof(object_t **));
+ if (new_list->tail < new_list->head) {
+ memcpy(new_list->segments + new_list->length,
+ new_list->segments, (new_list->tail + 1) *
sizeof(object_t **));
+ new_list->tail = new_list->length + new_list->tail;
+ }
+ new_list->length = 2 * new_list->length;
+#if CHECKED
+ assert(new_list->length == 2 * old_length);
+ if (old_tail < new_list->head) {
+ assert(new_list->tail == old_tail + old_length);
+ for (size_t i = 0; i < old_tail; i++) {
+ assert(new_list->segments[i] == new_list->segments[i +
old_length]);
+ }
+ } else {
+ assert(new_list->tail == old_tail);
+ }
+ qcgc_mark_list_check_invariant(new_list);
+#endif
+ return new_list;
+}
+
+QCGC_STATIC void qcgc_mark_list_check_invariant(mark_list_t *list) {
+ assert(list->head < list->length);
+ assert(list->tail < list->length);
+ assert(list->count == (list->tail - list->head + list->length) %
list->length * QCGC_MARK_LIST_SEGMENT_SIZE + list->insert_index);
+ for (size_t i = 0; i < list->length; i++) {
+ if ((list->head <= i && i <= list->tail) || (list->tail <
list->head &&
+ (i <= list->tail || i >= list->head))) {
+ for (size_t j = 0; j < QCGC_MARK_LIST_SEGMENT_SIZE;
j++) {
+ if (i != list->tail || j < list->insert_index) {
+ assert(list->segments[i][j] != NULL);
+ } else {
+ assert(list->segments[i][j] == NULL);
+ }
+ }
+ }
+ }
+}
diff --git a/rpython/translator/c/src/qcgc/mark_list.h
b/rpython/translator/c/src/qcgc/mark_list.h
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/mark_list.h
@@ -0,0 +1,35 @@
+/**
+ * @file mark_list.h
+ *
+ * Object list for marking step
+ */
+
+#pragma once
+
+#include "config.h"
+
+#include <stddef.h>
+
+#include "object.h"
+
+/**
+ * Mark list - circular buffer.
+ */
+typedef struct mark_list_s {
+ size_t head;
+ size_t tail;
+ size_t length;
+ size_t count;
+ size_t insert_index;
+ object_t **segments[];
+} mark_list_t;
+
+mark_list_t *qcgc_mark_list_create(size_t initial_size);
+void qcgc_mark_list_destroy(mark_list_t *list);
+
+mark_list_t *qcgc_mark_list_push(mark_list_t *list, object_t *object);
+mark_list_t *qcgc_mark_list_push_all(mark_list_t *list,
+ object_t **objects, size_t count);
+
+object_t **qcgc_mark_list_get_head_segment(mark_list_t *list);
+mark_list_t *qcgc_mark_list_drop_head_segment(mark_list_t *list);
diff --git a/rpython/translator/c/src/qcgc/object.h
b/rpython/translator/c/src/qcgc/object.h
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/object.h
@@ -0,0 +1,11 @@
+#pragma once
+
+
+#include "config.h"
+#include <stdint.h>
+
+#define QCGC_GRAY_FLAG 0x01
+
+typedef struct object_s {
+ uint32_t flags;
+} object_t;
diff --git a/rpython/translator/c/src/qcgc/qcgc.c
b/rpython/translator/c/src/qcgc/qcgc.c
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/qcgc.c
@@ -0,0 +1,255 @@
+#include "qcgc.h"
+
+#include <assert.h>
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "allocator.h"
+#include "event_logger.h"
+
+// TODO: Eventually move to own header?
+#define MAX(a,b) (((a)>(b))?(a):(b))
+#define MIN(a,b) (((a)<(b))?(a):(b))
+
+void qcgc_mark(void);
+void qcgc_mark_all(void);
+void qcgc_mark_incremental(void);
+void qcgc_pop_object(object_t *object);
+void qcgc_push_object(object_t *object);
+void qcgc_sweep(void);
+
+void qcgc_initialize(void) {
+ qcgc_state.shadow_stack =
qcgc_shadow_stack_create(QCGC_SHADOWSTACK_SIZE);
+ qcgc_state.gray_stack_size = 0;
+ qcgc_state.phase = GC_PAUSE;
+ qcgc_allocator_initialize();
+ qcgc_event_logger_initialize();
+}
+
+void qcgc_destroy(void) {
+ qcgc_event_logger_destroy();
+ qcgc_allocator_destroy();
+ free(qcgc_state.shadow_stack);
+}
+
+/**
+ * Shadow stack
+ */
+void qcgc_shadowstack_push(object_t *object) {
+ qcgc_state.shadow_stack =
+ qcgc_shadow_stack_push(qcgc_state.shadow_stack, object);
+}
+
+object_t *qcgc_shadowstack_pop(void) {
+ object_t *result = qcgc_shadow_stack_top(qcgc_state.shadow_stack);
+ qcgc_state.shadow_stack =
qcgc_shadow_stack_pop(qcgc_state.shadow_stack);
+ return result;
+}
+
+/*******************************************************************************
+ * Write barrier
*
+
******************************************************************************/
+void qcgc_write(object_t *object) {
+#if CHECKED
+ assert(object != NULL);
+#endif
+ if ((object->flags & QCGC_GRAY_FLAG) == 0) {
+ object->flags |= QCGC_GRAY_FLAG;
+ if (qcgc_state.phase != GC_PAUSE) {
+ if (qcgc_arena_get_blocktype((cell_t *) object) ==
BLOCK_BLACK) {
+ // This was black before, push it to gray stack
again
+ arena_t *arena = qcgc_arena_addr((cell_t *)
object);
+ arena->gray_stack = qcgc_gray_stack_push(
+ arena->gray_stack, object);
+ }
+ }
+ }
+}
+
+/*******************************************************************************
+ * Allocation
*
+
******************************************************************************/
+
+object_t *qcgc_allocate(size_t size) {
+#if LOG_ALLOCATION
+ qcgc_event_logger_log(EVENT_ALLOCATE_START, sizeof(size_t),
+ (uint8_t *) &size);
+#endif
+
+ object_t *result = (object_t *) qcgc_allocator_allocate(size);
+ result->flags |= QCGC_GRAY_FLAG;
+
+#if LOG_ALLOCATION
+ qcgc_event_logger_log(EVENT_ALLOCATE_DONE, sizeof(object_t *),
+ (uint8_t *) &result);
+#endif
+ return result;
+}
+
+/*******************************************************************************
+ * Collection
*
+
******************************************************************************/
+
+mark_color_t qcgc_get_mark_color(object_t *object) {
+#if CHECKED
+ assert(object != NULL);
+#endif
+ blocktype_t blocktype = qcgc_arena_get_blocktype((cell_t *) object);
+ bool gray = (object->flags & QCGC_GRAY_FLAG) == QCGC_GRAY_FLAG;
+ if (blocktype == BLOCK_WHITE) {
+ if (gray) {
+ return MARK_COLOR_LIGHT_GRAY;
+ } else {
+ return MARK_COLOR_WHITE;
+ }
+ } else if(blocktype == BLOCK_BLACK) {
+ if (gray) {
+ return MARK_COLOR_DARK_GRAY;
+ } else {
+ return MARK_COLOR_BLACK;
+ }
+ } else {
+#if CHECKED
+ assert(false);
+#endif
+ }
+}
+
+void qcgc_mark(void) {
+ qcgc_mark_all();
+}
+
+void qcgc_mark_all(void) {
+#if CHECKED
+ assert(qcgc_state.phase == GC_PAUSE || qcgc_state.phase == GC_MARK);
+#endif
+ qcgc_event_logger_log(EVENT_MARK_START, 0, NULL);
+
+ qcgc_state.phase = GC_MARK;
+
+ // Push all roots
+ for (size_t i = 0; i < qcgc_state.shadow_stack->count; i++) {
+ qcgc_push_object(qcgc_state.shadow_stack->items[i]);
+ }
+
+ while(qcgc_state.gray_stack_size > 0) {
+ for (size_t i = 0; i < qcgc_allocator_state.arenas->count; i++)
{
+ arena_t *arena = qcgc_allocator_state.arenas->items[i];
+ while (arena->gray_stack->index > 0) {
+ object_t *top =
+ qcgc_gray_stack_top(arena->gray_stack);
+ arena->gray_stack =
+ qcgc_gray_stack_pop(arena->gray_stack);
+ qcgc_pop_object(top);
+ }
+ }
+ }
+
+ qcgc_state.phase = GC_COLLECT;
+
+ qcgc_event_logger_log(EVENT_MARK_DONE, 0, NULL);
+}
+
+void qcgc_mark_incremental(void) {
+#if CHECKED
+ assert(qcgc_state.phase == GC_PAUSE || qcgc_state.phase == GC_MARK);
+#endif
+ unsigned long gray_stack_size = qcgc_state.gray_stack_size;
+ qcgc_event_logger_log(EVENT_INCMARK_START, sizeof(gray_stack_size),
+ (uint8_t *) &gray_stack_size);
+
+ qcgc_state.phase = GC_MARK;
+
+ // Push all roots
+ for (size_t i = 0; i < qcgc_state.shadow_stack->count; i++) {
+ qcgc_push_object(qcgc_state.shadow_stack->items[i]);
+ }
+
+ for (size_t i = 0; i < qcgc_allocator_state.arenas->count; i++) {
+ arena_t *arena = qcgc_allocator_state.arenas->items[i];
+ size_t initial_stack_size = arena->gray_stack->index;
+ size_t to_process = MIN(arena->gray_stack->index,
+ MAX(initial_stack_size / 2, QCGC_INC_MARK_MIN));
+ while (to_process > 0) {
+ object_t *top =
+ qcgc_gray_stack_top(arena->gray_stack);
+ arena->gray_stack =
+ qcgc_gray_stack_pop(arena->gray_stack);
+ qcgc_pop_object(top);
+ to_process--;
+ }
+ }
+
+ if (qcgc_state.gray_stack_size == 0) {
+ qcgc_state.phase = GC_COLLECT;
+ }
+
+ gray_stack_size = qcgc_state.gray_stack_size;
+ qcgc_event_logger_log(EVENT_INCMARK_START, sizeof(gray_stack_size),
+ (uint8_t *) &gray_stack_size);
+}
+
+void qcgc_pop_object(object_t *object) {
+#if CHECKED
+ assert(object != NULL);
+ assert((object->flags & QCGC_GRAY_FLAG) == QCGC_GRAY_FLAG);
+ assert(qcgc_arena_get_blocktype((cell_t *) object) == BLOCK_BLACK);
+#endif
+ object->flags &= ~QCGC_GRAY_FLAG;
+ qcgc_trace_cb(object, &qcgc_push_object);
+#if CHECKED
+ assert(qcgc_get_mark_color(object) == MARK_COLOR_BLACK);
+#endif
+}
+
+void qcgc_push_object(object_t *object) {
+#if CHECKED
+ size_t old_stack_size = qcgc_state.gray_stack_size;
+ assert(qcgc_state.phase == GC_MARK);
+#endif
+ if (object != NULL) {
+ if (qcgc_arena_get_blocktype((cell_t *) object) == BLOCK_WHITE)
{
+ object->flags |= QCGC_GRAY_FLAG;
+ qcgc_arena_set_blocktype((cell_t *) object,
BLOCK_BLACK);
+ arena_t *arena = qcgc_arena_addr((cell_t *) object);
+ arena->gray_stack =
qcgc_gray_stack_push(arena->gray_stack, object);
+ }
+ }
+#if CHECKED
+ if (object != NULL) {
+ if (old_stack_size == qcgc_state.gray_stack_size) {
+ assert(qcgc_get_mark_color(object) == MARK_COLOR_BLACK
||
+ qcgc_get_mark_color(object) ==
MARK_COLOR_DARK_GRAY);
+ } else {
+ assert(qcgc_state.gray_stack_size == old_stack_size +
1);
+ assert(qcgc_get_mark_color(object) ==
MARK_COLOR_DARK_GRAY);
+ }
+ } else {
+ assert(old_stack_size == qcgc_state.gray_stack_size);
+ }
+#endif
+}
+
+void qcgc_sweep(void) {
+#if CHECKED
+ assert(qcgc_state.phase == GC_COLLECT);
+#endif
+ unsigned long arena_count;
+ arena_count = qcgc_allocator_state.arenas->count;
+ qcgc_event_logger_log(EVENT_SWEEP_START, sizeof(arena_count),
+ (uint8_t *) &arena_count);
+
+ for (size_t i = 0; i < qcgc_allocator_state.arenas->count; i++) {
+ qcgc_arena_sweep(qcgc_allocator_state.arenas->items[i]);
+ }
+ qcgc_state.phase = GC_PAUSE;
+
+ qcgc_event_logger_log(EVENT_SWEEP_DONE, 0, NULL);
+}
+
+void qcgc_collect(void) {
+ qcgc_mark();
+ qcgc_sweep();
+}
diff --git a/rpython/translator/c/src/qcgc/qcgc.h
b/rpython/translator/c/src/qcgc/qcgc.h
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/qcgc.h
@@ -0,0 +1,93 @@
+/**
+ * @file qcgc.h
+ */
+
+#pragma once
+
+#include "config.h"
+
+#include <stdint.h>
+#include <sys/types.h>
+
+#include "arena.h"
+#include "gc_state.h"
+#include "gray_stack.h"
+#include "object.h"
+
+/**
+ * @typedef mark_color
+ * Object state during collection
+ * - MARK_COLOR_WHITE Clean and unprocessed
+ * - MARK_COLOR_LIGHT_GRAY Dirty and unprocessed
+ * - MARK_COLOR_DARK_GRAY Processing
+ * - MARK_COLOR_BLACK Processed
+ */
+typedef enum mark_color {
+ MARK_COLOR_WHITE,
+ MARK_COLOR_LIGHT_GRAY,
+ MARK_COLOR_DARK_GRAY,
+ MARK_COLOR_BLACK,
+} mark_color_t;
+
+/**
+ * Initialize the garbage collector.
+ */
+void qcgc_initialize(void);
+
+/**
+ * Destroy the garbage collector.
+ */
+void qcgc_destroy(void);
+
+/**
+ * Write barrier.
+ *
+ * @param object Object to write to
+ */
+void qcgc_write(object_t *object);
+
+/**
+ * Allocate new memory region
+ *
+ * @param size Desired size of the memory region
+ * @return Pointer to memory large enough to hold size bytes, NULL in case
of
+ * errors
+ */
+object_t *qcgc_allocate(size_t size);
+
+/**
+ * Run garbage collection.
+ */
+void qcgc_collect(void);
+
+/**
+ * Return color of object.
+ *
+ * @returs The color of the object, according to the mark algorithm.
+ */
+mark_color_t qcgc_get_mark_color(object_t *object);
+
+/**
+ * Add object to shadow stack
+ *
+ * @param object The object to push
+ */
+void qcgc_shadowstack_push(object_t *object);
+
+/**
+ * Pop object from shadow stack
+ *
+ * @return Top element of the shadowstack
+ */
+object_t *qcgc_shadowstack_pop(void);
+
+/**
+ * Tracing function.
+ *
+ * This function traces an object, i.e. calls visit on every object referenced
+ * by the given object. Has to be provided by the library user.
+ *
+ * @param object The object to trace
+ * @param visit The function to be called on the referenced objects
+ */
+extern void qcgc_trace_cb(object_t *object, void (*visit)(object_t *object));
diff --git a/rpython/translator/c/src/qcgc/shadow_stack.c
b/rpython/translator/c/src/qcgc/shadow_stack.c
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/shadow_stack.c
@@ -0,0 +1,56 @@
+#include "shadow_stack.h"
+
+#include <assert.h>
+#include <stdlib.h>
+
+QCGC_STATIC size_t shadow_stack_size(size_t size);
+QCGC_STATIC shadow_stack_t *shadow_stack_grow(shadow_stack_t *stack);
+QCGC_STATIC shadow_stack_t *shadow_stack_shrink(shadow_stack_t *stack);
+
+shadow_stack_t *qcgc_shadow_stack_create(size_t size) {
+ shadow_stack_t *result = (shadow_stack_t *)
malloc(shadow_stack_size(size));
+ result->size = size;
+ result->count = 0;
+ return result;
+}
+
+shadow_stack_t *qcgc_shadow_stack_push(shadow_stack_t *stack, object_t *item) {
+ if (stack->size == stack->count) {
+ stack = shadow_stack_grow(stack);
+ }
+ stack->items[stack->count] = item;
+ stack->count++;
+ return stack;
+}
+
+object_t *qcgc_shadow_stack_top(shadow_stack_t *stack) {
+#if CHECKED
+ assert(stack->count != 0);
+#endif
+ return stack->items[stack->count - 1];
+}
+
+shadow_stack_t *qcgc_shadow_stack_pop(shadow_stack_t *stack) {
+ // TODO: Add lower bound for size (config.h)
+ if (stack->count < stack->size / 4) {
+ stack = shadow_stack_shrink(stack);
+ }
+ stack->count--;
+ return stack;
+}
+
+QCGC_STATIC size_t shadow_stack_size(size_t size) {
+ return (sizeof(shadow_stack_t) + size * sizeof(object_t *));
+}
+
+QCGC_STATIC shadow_stack_t *shadow_stack_grow(shadow_stack_t *stack) {
+ stack = (shadow_stack_t *) realloc(stack, shadow_stack_size(stack->size
* 2));
+ stack->size *= 2;
+ return stack;
+}
+
+QCGC_STATIC shadow_stack_t *shadow_stack_shrink(shadow_stack_t *stack) {
+ stack = (shadow_stack_t *) realloc(stack, shadow_stack_size(stack->size
/ 2));
+ stack->size /= 2;
+ return stack;
+}
diff --git a/rpython/translator/c/src/qcgc/shadow_stack.h
b/rpython/translator/c/src/qcgc/shadow_stack.h
new file mode 100644
--- /dev/null
+++ b/rpython/translator/c/src/qcgc/shadow_stack.h
@@ -0,0 +1,19 @@
+#pragma once
+
+#include "config.h"
+
+#include <stddef.h>
+
+#include "object.h"
+
+typedef struct shadow_stack_s {
+ size_t count;
+ size_t size;
+ object_t *items[];
+} shadow_stack_t;
+
+shadow_stack_t *qcgc_shadow_stack_create(size_t size);
+
+shadow_stack_t *qcgc_shadow_stack_push(shadow_stack_t *stack, object_t *item);
+object_t *qcgc_shadow_stack_top(shadow_stack_t *stack);
+shadow_stack_t *qcgc_shadow_stack_pop(shadow_stack_t *stack);
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
