LibJS: Implement basic conservative garbage collection

We now scan the stack and CPU registers for potential pointers into the
GC heap, and include any valid Cell pointers in the set of roots.

This works pretty well but we'll also need to solve marking of things
passed to native functions, since those are currently in Vector<Value>
and the Vector storage is on the heap (not scanned.)

3 files changed, 81 insertions, 2 deletions

diff --git a/Libraries/LibJS/Heap/Heap.cpp b/Libraries/LibJS/Heap/Heap.cpp
index 9838242a1b..31707a1150 100644
--- a/Libraries/LibJS/Heap/Heap.cpp
+++ b/Libraries/LibJS/Heap/Heap.cpp
@@ -30,6 +30,9 @@
 #include <LibJS/Heap/HeapBlock.h>
 #include <LibJS/Interpreter.h>
 #include <LibJS/Runtime/Object.h>
+#include <serenity.h>
+#include <setjmp.h>
+#include <stdio.h>
 
 #define HEAP_DEBUG
 
@@ -71,14 +74,76 @@ void Heap::gather_roots(HashTable<Cell*>& roots)
 {
     m_interpreter.gather_roots({}, roots);
 
+    gather_conservative_roots(roots);
+
 #ifdef HEAP_DEBUG
-    dbg() << "collect_roots:";
+    dbg() << "gather_roots:";
     for (auto* root : roots) {
         dbg() << "  + " << root;
     }
 #endif
 }
 
+void Heap::gather_conservative_roots(HashTable<Cell*>& roots)
+{
+    FlatPtr dummy;
+
+#ifdef HEAP_DEBUG
+    dbg() << "gather_conservative_roots:";
+#endif
+
+    jmp_buf buf;
+    setjmp(buf);
+
+    HashTable<FlatPtr> possible_pointers;
+
+    for (size_t i = 0; i < (sizeof(buf->regs) / sizeof(FlatPtr)); ++i)
+        possible_pointers.set(buf->regs[i]);
+
+    FlatPtr stack_base;
+    size_t stack_size;
+    if (get_stack_bounds(&stack_base, &stack_size) < 0) {
+        perror("get_stack_bounds");
+        ASSERT_NOT_REACHED();
+    }
+
+    FlatPtr stack_reference = reinterpret_cast<FlatPtr>(&dummy);
+    FlatPtr stack_top = stack_base + stack_size;
+
+    for (FlatPtr stack_address = stack_reference; stack_address < stack_top; stack_address += sizeof(FlatPtr)) {
+        auto data = *reinterpret_cast<FlatPtr*>(stack_address);
+        possible_pointers.set(data);
+    }
+
+    for (auto possible_pointer : possible_pointers) {
+        if (!possible_pointer)
+            continue;
+#ifdef HEAP_DEBUG
+        dbg() << "  ? " << (const void*)possible_pointer;
+#endif
+        if (auto* cell = cell_from_possible_pointer(possible_pointer)) {
+            if (cell->is_live()) {
+#ifdef HEAP_DEBUG
+                dbg() << "  ?-> " << (const void*)cell;
+#endif
+                roots.set(cell);
+            } else {
+#ifdef HEAP_DEBUG
+                dbg() << "  #-> " << (const void*)cell;
+#endif
+            }
+        }
+    }
+}
+
+Cell* Heap::cell_from_possible_pointer(FlatPtr pointer)
+{
+    auto* possible_heap_block = HeapBlock::from_cell(reinterpret_cast<const Cell*>(pointer));
+    if (m_blocks.find([possible_heap_block](auto& block) { return block.ptr() == possible_heap_block; }) == m_blocks.end())
+        return nullptr;
+    return possible_heap_block->cell_from_possible_pointer(pointer);
+}
+
 class MarkingVisitor final : public Cell::Visitor {
 public:
     MarkingVisitor() {}
@@ -101,8 +166,11 @@ void Heap::mark_live_cells(const HashTable<Cell*>& roots)
     dbg() << "mark_live_cells:";
 #endif
     MarkingVisitor visitor;
-    for (auto* root : roots)
+    for (auto* root : roots) {
+        if (!root)
+            continue;
         visitor.visit(root);
+    }
 }
 
 void Heap::sweep_dead_cells()
diff --git a/Libraries/LibJS/Heap/Heap.h b/Libraries/LibJS/Heap/Heap.h
index 8366c80898..691c362f35 100644
--- a/Libraries/LibJS/Heap/Heap.h
+++ b/Libraries/LibJS/Heap/Heap.h
@@ -59,9 +59,12 @@ private:
     Cell* allocate_cell(size_t);
 
     void gather_roots(HashTable<Cell*>&);
+    void gather_conservative_roots(HashTable<Cell*>&);
     void mark_live_cells(const HashTable<Cell*>& live_cells);
     void sweep_dead_cells();
 
+    Cell* cell_from_possible_pointer(FlatPtr);
+
     Interpreter& m_interpreter;
     Vector<NonnullOwnPtr<HeapBlock>> m_blocks;
 };
diff --git a/Libraries/LibJS/Heap/HeapBlock.h b/Libraries/LibJS/Heap/HeapBlock.h
index f1cfd2674c..ecb1266eb6 100644
--- a/Libraries/LibJS/Heap/HeapBlock.h
+++ b/Libraries/LibJS/Heap/HeapBlock.h
@@ -61,6 +61,14 @@ public:
         return reinterpret_cast<HeapBlock*>((FlatPtr)cell & ~(block_size - 1));
     }
 
+    Cell* cell_from_possible_pointer(FlatPtr pointer)
+    {
+        if (pointer < reinterpret_cast<FlatPtr>(m_storage))
+            return nullptr;
+        size_t cell_index = (pointer - reinterpret_cast<FlatPtr>(m_storage)) / m_cell_size;
+        return cell(cell_index);
+    }
+
 private:
     HeapBlock(Heap&, size_t cell_size);