aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--bytecode/src/bytecode.rs4
-rw-r--r--bytecode/src/heap.rs131
2 files changed, 68 insertions, 67 deletions
diff --git a/bytecode/src/bytecode.rs b/bytecode/src/bytecode.rs
index e784d57..41302ad 100644
--- a/bytecode/src/bytecode.rs
+++ b/bytecode/src/bytecode.rs
@@ -183,7 +183,7 @@ impl Interpreter {
if o < 0 {
return Err(String::from("pointer offset can't be negative"));
}
- let result = self.heap.peek(p.offset(usize::try_from(o).unwrap()))?;
+ let result = self.heap.peek(p, usize::try_from(o).unwrap())?;
self.set_arg(dest, result);
Ok(())
}
@@ -195,7 +195,7 @@ impl Interpreter {
if o < 0 {
return Err(String::from("pointer offset can't be negative"));
}
- self.heap.poke(w, p.offset(usize::try_from(o).unwrap()))?;
+ self.heap.poke(w, p, usize::try_from(o).unwrap())?;
Ok(())
}
diff --git a/bytecode/src/heap.rs b/bytecode/src/heap.rs
index d047d5a..c61a30a 100644
--- a/bytecode/src/heap.rs
+++ b/bytecode/src/heap.rs
@@ -1,5 +1,5 @@
use crate::data::{Pointer, Value};
-use std::collections::HashMap;
+use std::collections::{HashMap, VecDeque};
use std::iter::Iterator;
fn rewrite_pointers(
@@ -29,7 +29,6 @@ fn open_ptr(p: Pointer) -> (usize, usize) {
pub struct Heap {
heap: Vec<u64>,
- free_pointer: usize,
spare_heap: Vec<u64>,
last_reachable_cells: usize,
}
@@ -37,14 +36,13 @@ pub struct Heap {
impl Heap {
pub fn new() -> Self {
Heap {
- heap: vec![0; 512], // 4 kB
- free_pointer: 0,
- spare_heap: vec![0; 512],
+ heap: Vec::with_capacity(512),
+ spare_heap: Vec::with_capacity(512),
last_reachable_cells: 0,
}
}
- fn alloc_size(&mut self, p: Pointer) -> Result<usize, String> {
+ fn alloc_size(&self, p: Pointer) -> Result<usize, String> {
let (u, _) = open_ptr(p);
if u == 0 {
return Err(String::from("cannot get the size of a nil pointer"));
@@ -61,71 +59,60 @@ impl Heap {
return Ok(size & 1 != 0);
}
- fn gc_process_value(
- &mut self,
- val: Value,
- spare_heap_ptr: &mut usize,
- rewrites: &mut HashMap<Pointer, Pointer>,
- ) -> Result<(), String> {
- let p = if val.is_pointer() {
- val.to_pointer().unwrap()
- } else {
- return Ok(());
- };
- if rewrites.contains_key(&p) {
- // Already copied this one.
- return Ok(());
- }
- let Pointer(u) = p;
- let object_size = self.alloc_size(p)?;
- // Copy object and size.
- self.spare_heap[*spare_heap_ptr..*spare_heap_ptr + object_size + 8]
- .copy_from_slice(&self.heap[u - 8..u + object_size]);
- rewrites.insert(p, Pointer(*spare_heap_ptr + 8));
- *spare_heap_ptr += object_size + 8;
- if self.is_bytevector(p)? {
- // Don't process bytevectors recursively. We're all done.
- return Ok(());
- }
- for i in (u..u + object_size).step_by(8) {
- self.gc_process_value(self.peek(Pointer(i))?, spare_heap_ptr, rewrites)?;
- }
- return Ok(());
- }
-
fn walk_gc_roots(
&mut self,
roots: &[Value],
- spare_heap_ptr: &mut usize,
rewrites: &mut HashMap<Pointer, Pointer>,
) -> Result<(), String> {
- for &val in roots {
- self.gc_process_value(val, spare_heap_ptr, rewrites)?;
+ let mut queue: VecDeque<Value> = VecDeque::with_capacity(roots.len());
+ queue.extend(roots);
+ while let Some(val) = queue.pop_front() {
+ let p = if val.is_pointer() {
+ val.to_pointer().unwrap()
+ } else {
+ continue;
+ };
+ if rewrites.contains_key(&p) {
+ // Already copied this one.
+ continue;
+ }
+ let (u, _) = open_ptr(p);
+ let object_size = self.alloc_size(p)?;
+ let object_size_words = object_size / 8;
+ // Copy object and size.
+ rewrites.insert(p, Pointer(self.spare_heap.len() * 8 + 8));
+ self.spare_heap
+ .extend(&self.heap[u - 1..u + object_size_words]);
+ if self.is_bytevector(p)? {
+ // Don't process bytevectors recursively. We're all done.
+ continue;
+ }
+ for i in u..u + object_size_words {
+ queue.push_back(Value(self.heap[i]));
+ }
}
return Ok(());
}
fn collect_garbage(&mut self, locals: &mut [Value]) -> Result<(), String> {
- self.spare_heap.resize(self.heap.len(), 0);
- let mut spare_heap_ptr = 0;
+ self.spare_heap.truncate(0);
let mut rewrites = HashMap::new();
- self.walk_gc_roots(locals, &mut spare_heap_ptr, &mut rewrites)?;
+ self.walk_gc_roots(locals, &mut rewrites)?;
// Rewrite values.
rewrite_pointers(locals, &rewrites)?;
// Activate the new heap!
std::mem::swap(&mut self.heap, &mut self.spare_heap);
- self.free_pointer = spare_heap_ptr;
// Walk objects in the heap and rewrite pointers. First object is at address 8.
let mut i = 8;
- while i < self.free_pointer {
+ while i < self.heap.len() * 8 {
let p = Pointer(i);
if self.is_bytevector(p)? {
i += self.alloc_size(p)?;
continue;
}
- for j in (i..i + self.alloc_size(p)?).step_by(8) {
- let q = Pointer(j);
- let val = self.peek(q)?;
+ let sz = self.alloc_size(p)?;
+ for j in (0..sz).step_by(8) {
+ let val = self.peek(p, j)?;
let vp = if val.is_pointer() {
val.to_pointer().unwrap()
} else {
@@ -138,12 +125,16 @@ impl Heap {
.get(&vp)
.ok_or(format!("no rewrite found for {:x}", u))?,
),
- q,
+ p,
+ j,
)?;
}
- i += self.alloc_size(p)?;
+ if sz == 0 {
+ return Err(String::from("object with size 0 found on the heap"));
+ }
+ i += sz + 8;
}
- self.last_reachable_cells = spare_heap_ptr;
+ self.last_reachable_cells = self.heap.len();
// Done??
return Ok(());
}
@@ -154,22 +145,20 @@ impl Heap {
locals: &mut [Value],
bytevector_p: bool,
) -> Result<Pointer, String> {
- if self.free_pointer > 2 * self.last_reachable_cells {
+ if self.heap.len() > 2 * self.last_reachable_cells {
self.collect_garbage(locals)?;
}
let n_cells = (n + 7) / 8;
- if self.free_pointer + n_cells + 1 > self.heap.len() {
- self.heap.resize(self.free_pointer + n_cells + 1, 0);
- }
- let len_p = &mut self.heap[self.free_pointer];
+ let len_idx = self.heap.len();
+ self.heap.resize(self.heap.len() + n_cells + 1, 0);
+ let len_p = &mut self.heap[len_idx];
*len_p = u64::try_from(n).unwrap() << 1;
if bytevector_p {
*len_p |= 1;
}
- self.free_pointer += 1;
- let p = Pointer(self.free_pointer * 8);
- self.heap[self.free_pointer..self.free_pointer + n_cells].fill(0);
- self.free_pointer += n_cells;
+ let obj_start = len_idx + 1;
+ let p = Pointer(obj_start * 8);
+ self.heap[obj_start..obj_start + n_cells].fill(0);
return Ok(p);
}
@@ -181,16 +170,28 @@ impl Heap {
return self.alloc_b(n, locals, true);
}
- pub fn peek(&self, p: Pointer) -> Result<Value, String> {
- let (u, _) = open_ptr(p);
+ pub fn peek(&self, p: Pointer, offset: usize) -> Result<Value, String> {
+ let obj_sz = self.alloc_size(p)?;
+ if offset >= obj_sz {
+ return Err(format!(
+ "invalid offset {offset} in an object of size {obj_sz}"
+ ));
+ }
+ let (u, _) = open_ptr(p.offset(offset));
if u >= self.heap.len() {
return Err(format!("invalid pointer {:x}", p));
}
return Ok(Value(self.heap[u]));
}
- pub fn poke(&mut self, v: Value, p: Pointer) -> Result<(), String> {
- let (u, _) = open_ptr(p);
+ pub fn poke(&mut self, v: Value, p: Pointer, offset: usize) -> Result<(), String> {
+ let obj_sz = self.alloc_size(p)?;
+ if offset >= obj_sz {
+ return Err(format!(
+ "invalid offset {offset} in an object of size {obj_sz}"
+ ));
+ }
+ let (u, _) = open_ptr(p.offset(offset));
let Value(x) = v;
if u >= self.heap.len() {
return Err(format!("invalid pointer {:x}", p));
generated by cgit v1.3.1 (git 2.54.0) at 2026-09-04 03:54:51 +0000