From 356aaae9580f0a05ccbe8a7e69baddf25847e79c Mon Sep 17 00:00:00 2001
From: "Michael D. Lowis" <mike@mdlowis.com>
Date: Fri, 3 Apr 2015 18:16:33 -0400
Subject: [PATCH] Implemented heap module find and mark routines

---
 source/runtime/gc.c      |  3 ++-
 source/runtime/heap.c    | 43 +++++++++++++++++++++++++++++++++++-----
 source/runtime/heap.h    |  3 ++-
 source/runtime/segment.c |  6 ++++++
 source/runtime/segment.h |  2 ++
 5 files changed, 50 insertions(+), 7 deletions(-)

diff --git a/source/runtime/gc.c b/source/runtime/gc.c
index 2ecf2de..e8c16f7 100644
--- a/source/runtime/gc.c
+++ b/source/runtime/gc.c
@@ -60,7 +60,7 @@ static void gc_scan_object(void* object) {
 
 static void gc_scan_region(uintptr_t* start, uintptr_t* stop) {
     for (; start < stop; start++) {
-        obj_t* obj = (obj_t*)heap_find_and_mark(Heap, start);
+        obj_t* obj = (obj_t*)heap_find_and_mark(Heap, *start);
         if (NULL != obj)
             gc_scan_object(obj);
     }
@@ -92,3 +92,4 @@ void gc_collect(void)
     gc_scan_object(NULL);
     heap_finish_collection(Heap);
 }
+
diff --git a/source/runtime/heap.c b/source/runtime/heap.c
index 1fcccdd..3b84885 100644
--- a/source/runtime/heap.c
+++ b/source/runtime/heap.c
@@ -44,8 +44,10 @@ static void* allocate_small_block(heap_t* heap, uintptr_t num_slots)
 
 static void* allocate_large_block(heap_t* heap, uintptr_t num_slots)
 {
-    block_t* blk = (block_t*)malloc(sizeof(block_t) + (num_slots * sizeof(uintptr_t)));
+    uintptr_t size = (num_slots * sizeof(uintptr_t));
+    block_t* blk = (block_t*)malloc(sizeof(block_t) + size);
     blk->next = heap->blocks;
+    blk->size = size;
     heap->blocks = blk;
     return (&blk->data[0]);
 }
@@ -77,10 +79,41 @@ void heap_finish_collection(heap_t* heap)
     destroy_large_blocks(heap->greylist);
 }
 
-void* heap_find_and_mark(heap_t* heap, uintptr_t* addr)
+static void* subheap_find_and_mark(heap_t* heap, uintptr_t addr) {
+    void* obj = NULL;
+    for (uintptr_t i = 0; i < NUM_HEAP_STACKS; i++) {
+        for(segment_t* curr = heap->heaps[i]; curr != NULL; curr = curr->next) {
+            obj = segment_find_and_mark(heap->heaps[i], addr);
+            if (NULL != obj) {
+                i = NUM_HEAP_STACKS;
+                break;
+            }
+        }
+    }
+    return obj;
+}
+
+static void* block_find_and_mark(heap_t* heap, uintptr_t addr) {
+    void* obj = NULL;
+    block_t* prev = NULL;
+    block_t* curr = heap->greylist;
+    while (curr != NULL) {
+        uintptr_t start = (uintptr_t)&(curr->data[0]);
+        uintptr_t end   = start + curr->size;
+        if ((start <= addr) && (addr <= end)) {
+
+        }
+        prev = curr;
+        curr = curr->next;
+    }
+    return obj;
+}
+
+void* heap_find_and_mark(heap_t* heap, uintptr_t addr)
 {
-    (void)heap;
-    (void)addr;
-    return NULL;
+    void* obj = subheap_find_and_mark(heap, addr);
+    if (NULL == obj)
+        obj = block_find_and_mark(heap, addr);
+    return obj;
 }
 
diff --git a/source/runtime/heap.h b/source/runtime/heap.h
index f56f757..39b2a92 100644
--- a/source/runtime/heap.h
+++ b/source/runtime/heap.h
@@ -17,6 +17,7 @@
 
 typedef struct block_t {
     struct block_t* next;
+    uintptr_t size;
     uintptr_t data[];
 } block_t;
 
@@ -36,6 +37,6 @@ void heap_start_collection(heap_t* heap);
 
 void heap_finish_collection(heap_t* heap);
 
-void* heap_find_and_mark(heap_t* heap, uintptr_t* addr);
+void* heap_find_and_mark(heap_t* heap, uintptr_t addr);
 
 #endif /* HEAP_H */
diff --git a/source/runtime/segment.c b/source/runtime/segment.c
index 3177376..ee9226b 100644
--- a/source/runtime/segment.c
+++ b/source/runtime/segment.c
@@ -62,3 +62,9 @@ void segment_clear_map(segment_t* seg)
     memset(seg->blockmap, 0xFFu, sizeof(seg->blockmap));
 }
 
+void* segment_find_and_mark(segment_t* seg, uintptr_t addr) {
+    (void)seg;
+    (void)addr;
+    return NULL;
+}
+
diff --git a/source/runtime/segment.h b/source/runtime/segment.h
index 611699d..318d625 100644
--- a/source/runtime/segment.h
+++ b/source/runtime/segment.h
@@ -30,4 +30,6 @@ void* segment_alloc(segment_t* seg);
 
 void segment_clear_map(segment_t* seg);
 
+void* segment_find_and_mark(segment_t* seg, uintptr_t addr);
+
 #endif /* SEGMENT_H */
-- 
2.54.0