GCSIM

Mark-Sweep GC simulator written in C++23.

Getting Started

Prerequisites

• Clang (any version compatible with C++23)
• make
• Pthread Support (the build uses the -pthread flag)

Installation

1. Clone the repository:

   git clone https://github.com/rdkc4/ikp-team-16.git
   cd ikp-team-16

2. Build the project:

   make

   or (recommended, to use all available cores for a faster build):

   make -j$(nproc)

Usage

To start the simulations, run:

./gcsim

Architecture

Architecture Diagram

HEAP

heap consists of 8 segments, 16MB each:

• 4 small object segments
• 2 medium object segments
• 2 large object segments

each block on the heap starts with header, which consists of:

• pointer to the next free block (if current block is free), nullptr otherwise
• size of the block
• flags (is_marked, is_free)

ROOT-SET-TABLE

root_set_table uses hash_map to map name of the root to a pointer to the root_set_base.

root_set_base types:

• thread_local_stack
• global_root
• register_root

THREAD-LOCAL-STACK

thread_local_stack uses indexed_stack to store variables allocated by the thread, indexed_stack stores pointers to headers on the heap.

thread_local_stack has a hash_map that maps name of the variable to its index for easier reassignation and deletion.

GLOBAL-ROOT & REGISTER-ROOT

global_root and register_root have pointers to headers on the heap.

SEGMENT-FREE-MEMORY-TABLE

segment_free_memory_table uses hash_map that maps index of the segment to segment_info.

segment_free_memory_table_entry consists of:

• pointer to the head of the free block linked list
• number of free bytes in the segment

GARBAGE-COLLECTOR

mark-sweep stop-the-world garbage_collector.

during its execution all allocator threads are sleeping.

garbage_collector uses thread pool to mark all objects reachable from the root_set_table.

garbage_collector uses thread_pool to sweep all segments.

HEAP-MANAGER

heap_manager manages all allocations.

heap_manager owns root_set_table, segment_free_memory_table and heap.

garbage_collector is run either periodically or on allocation failure if enough time has passed since last garbage collection.

heap_manager uses thread_pool to coalesce free segments after the garbage collection.

ALLOCATORS

allocators simulate multi-threaded allocation of the memory on the heap.

allocators use thread_pool to simulate multi-threaded allocation from threads, global variables and registers.

simulation has two modes:

• stress mode
• relaxed mode

after simulation performance is measured in:

• execution time in milliseconds and seconds
• number of allocations during the simulation
• allocation throughput in allocs/ms and allocs/s