Implementing a Basic Mark-and-Sweep Garbage Collector in Go

This challenge asks you to implement a simplified mark-and-sweep garbage collector in Go. Understanding garbage collection is crucial for efficient memory management, especially in languages like Go that rely on automatic memory management. This exercise will provide a foundational understanding of how garbage collectors work under the hood.

Problem Description

You are tasked with creating a rudimentary mark-and-sweep garbage collector for a custom memory arena. The arena will allocate memory blocks, and your garbage collector will periodically identify and reclaim unused blocks. The collector should:

1. Maintain a list of allocated memory blocks: These blocks are represented by pointers to allocated memory regions within the arena.
2. Implement a mark function: This function traverses the allocated blocks, starting from a set of "root" objects (which you'll define as a slice of pointers). It marks reachable blocks by setting a flag on them.
3. Implement a sweep function: This function iterates through all allocated blocks. Unmarked blocks are considered garbage and should be removed from the list of allocated blocks, effectively freeing the memory.
4. Provide an allocate function: This function allocates a new block of memory from the arena and returns a pointer to it.
5. Provide a free function: This function removes a block from the list of allocated blocks, marking it as available for future allocation. Note: This function does NOT actually deallocate the memory from the OS; it simply removes the block from the managed list.

Key Requirements:

• The garbage collector should be able to handle cycles (though the implementation doesn't need to be perfectly robust against them – a simple marking strategy is sufficient).
• The arena size is fixed.
• The collector should be triggered periodically (you'll simulate this with a simple timer).
• The mark function should use a depth-first search (DFS) approach.
• The sweep function should iterate through the allocated blocks in the order they were allocated.

Expected Behavior:

The garbage collector should correctly identify and reclaim memory blocks that are no longer reachable from the root objects. The allocate function should return valid pointers within the arena, and the free function should remove blocks from the managed list. The arena should not run out of memory if allocations and frees are balanced.

Edge Cases to Consider:

• Empty arena.
• All blocks allocated.
• Cycles in the object graph.
• Root objects pointing to each other.
• Freeing the same block twice. (This should not cause a crash, but the behavior is not strictly defined).

Examples

Example 1:

Input:
Arena size: 1024 bytes
Root objects: [ptr1, ptr2]
ptr1 points to block A
ptr2 points to block B
Block C is not reachable from any root object.

Output:
After garbage collection, only blocks A and B remain allocated. Block C is freed.

Example 2:

Input:
Arena size: 512 bytes
Root objects: [ptr1]
ptr1 points to block A
Block A points to block B
Block B points to block A (cycle)

Output:
After garbage collection, both blocks A and B remain allocated. The cycle is preserved.

Example 3: (Edge Case - All blocks allocated)

Input:
Arena size: 256 bytes
Root objects: [ptr1]
All 256 bytes are allocated into blocks reachable from ptr1.

Output:
After garbage collection, all blocks remain allocated. No memory is freed.

Constraints

• Arena Size: The arena size will be between 128 and 2048 bytes.
• Block Size: Allocated blocks will be multiples of 8 bytes.
• Number of Root Objects: The number of root objects will be between 0 and 10.
• Performance: The garbage collection process should complete within 100ms for a 1024-byte arena. (This is a soft constraint; correctness is more important than strict performance).
• Memory Safety: The code must be memory-safe and avoid memory leaks or segmentation faults.

Notes

• You don't need to implement a sophisticated memory allocator within the arena. A simple first-fit allocator is sufficient.
• Focus on the core mark-and-sweep algorithm.
• Consider using a sync.Mutex to protect the allocated blocks list from concurrent access (although this challenge doesn't explicitly require concurrency, it's good practice).
• The "timer" triggering the garbage collection can be a simple time.Sleep call in your testing code.
• You can represent allocated blocks as structs containing a pointer to the memory and a "marked" flag.
• This is a simplified implementation. Real-world garbage collectors are significantly more complex.