From 056fbf7e7dc727d020ba54e439f2b47411c58e76 Mon Sep 17 00:00:00 2001 From: Rose Hogenson Date: Thu, 3 Mar 2022 13:48:19 -0800 Subject: Start the garbage collector. I don't think we finished it, but I wrote this code a while ago and I'm just trying to get it committed. --- bytecode/src/bytecode.rs | 141 ++++++++++++++++++++++++++++++++--------------- 1 file changed, 98 insertions(+), 43 deletions(-) (limited to 'bytecode/src/bytecode.rs') diff --git a/bytecode/src/bytecode.rs b/bytecode/src/bytecode.rs index ab6edf9..84a9b8b 100644 --- a/bytecode/src/bytecode.rs +++ b/bytecode/src/bytecode.rs @@ -1,4 +1,5 @@ -use crate::heap::{Heap, Pointer}; +use crate::data::{Pointer, Value}; +use crate::heap::Heap; use std::io::{BufWriter, Read, StdinLock, Write}; // The cute scheme virtual machine has two stacks: @@ -39,21 +40,25 @@ pub enum Op { // ====== // ( n -- a ) - // Allocates n bytes and returns the address. + // Allocates n words and returns the address. Alloc, - // ( a -- u ) + // ( n -- a ) + // Allocates n bytes and returns the address. The contents of this allocation will be treated + // as raw data and not walked by the garbage collector. + AllocBytevector, + // ( a i -- u ) // Fetches a 64 bit word from the specified address plus the // given offset. - Peek(u8), - // ( u a ) + Peek, + // ( u a i ) // Stores a 64 bit word at the specified address plus the // given offset. - Poke(u8), - // ( a -- n ) - // Fetches a byte from the specified address. + Poke, + // ( a i -- n ) + // Fetches a byte from the specified address plus the given offset. PeekByte, - // ( n a ) - // Stores a byte at the specified address. + // ( n a i ) + // Stores a byte at the specified address plus the given offset. PokeByte, // Stack @@ -70,7 +75,7 @@ pub enum Op { // ============ // ( f -- ) - // Jumps to the specified offset if the argument is non-zero. + // Jumps to the specified offset if the argument is not false. If(i64), // ( i-addr a1 a2 ... an ) // ( Locals stack: -- instruction-ptr a1 a2 ... an argument-ptr ) @@ -98,36 +103,43 @@ pub enum Op { } struct Stack { - v: Vec, + v: Vec, } impl Stack { - fn pop(&mut self) -> Result { - self.v.pop().ok_or(String::from("stack underflow")) + fn pop(&mut self) -> Result { + return self.v.pop().ok_or(String::from("stack underflow")); } fn pop_int(&mut self) -> Result { - Ok(self.pop()? as i64 >> 1) + return self.pop()?.to_int(); } fn push_int(&mut self, i: i64) { - self.v.push((i as u64) << 1 | 1); + self.v.push(Value::from_int(i)); } fn pop_pointer(&mut self) -> Result { - Ok(Pointer::from_bytes(self.pop()?)) + return self.pop()?.to_pointer(); } fn push_pointer(&mut self, p: Pointer) { - self.v.push(p.bytes()); + self.v.push(Value::from_pointer(p)); } fn pop_usize(&mut self) -> Result { - Ok(usize::try_from(self.pop()?).unwrap() >> 1) + let Value(stack_representation) = self.pop()?; + Ok(usize::try_from(stack_representation).unwrap() >> 3) } fn push_usize(&mut self, p: usize) { - self.v.push(u64::try_from(p).unwrap() << 1 | 1); + // We're going to disguise p as a pointer by shifting. + if p >= 0x2000000000000000 + /* 2^61 */ + { + panic!("pointer overflow!"); + } + self.v.push(Value(u64::try_from(p).unwrap() << 3)); } } @@ -170,41 +182,53 @@ fn fn_mod(stack: &mut Stack) -> Result<(), String> { Ok(()) } -fn alloc(stack: &mut Stack, heap: &mut Heap) -> Result<(), String> { +fn alloc(stack: &mut Stack, locals: &mut Stack, heap: &mut Heap) -> Result<(), String> { let n = stack.pop_int()?; - let n_usize = match n.try_into() { - Ok(x) => x, - Err(_) => { - return Err(String::from("invalid size")); - } - }; - stack.push_pointer(heap.alloc(n_usize)); - Ok(()) + if n < 0 { + return Err(String::from("tried to allocate negative memory")); + } + let p = heap.alloc(usize::try_from(n).unwrap(), &mut stack.v, &mut locals.v)?; + stack.push_pointer(p); + return Ok(()); } -fn peek(stack: &mut Stack, heap: &Heap, n: u8) -> Result<(), String> { +fn alloc_bytevector(stack: &mut Stack, locals: &mut Stack, heap: &mut Heap) -> Result<(), String> { + let n = stack.pop_int()?; + if n < 0 { + return Err(String::from("tried to allocate negative memory")); + } + let p = heap.alloc_bytevector(usize::try_from(n).unwrap(), &mut stack.v, &mut locals.v)?; + stack.push_pointer(p); + return Ok(()); +} + +fn peek(stack: &mut Stack, heap: &Heap) -> Result<(), String> { + let i = stack.pop_int()?; let a = stack.pop_pointer()?; - stack.v.push(heap.peek(a.offset(n))?); + stack.v.push(heap.peek(a.offset(i))?); Ok(()) } -fn poke(stack: &mut Stack, heap: &mut Heap, n: u8) -> Result<(), String> { +fn poke(stack: &mut Stack, heap: &mut Heap) -> Result<(), String> { + let i = stack.pop_int()?; let a = stack.pop_pointer()?; let u = stack.pop()?; - heap.poke(u, a.offset(n))?; + heap.poke(u, a.offset(i))?; Ok(()) } fn peek_byte(stack: &mut Stack, heap: &Heap) -> Result<(), String> { + let i = stack.pop_int()?; let a = stack.pop_pointer()?; - stack.push_int(i64::from(heap.peek_byte(a))); + stack.push_int(i64::from(heap.peek_byte(a.offset(i)))); Ok(()) } fn poke_byte(stack: &mut Stack, heap: &mut Heap) -> Result<(), String> { + let i = stack.pop_int()?; let a = stack.pop_pointer()?; let n = stack.pop_int()?; - heap.poke_byte((n & 0xff).try_into().unwrap(), a); + heap.poke_byte((n & 0xff).try_into().unwrap(), a.offset(i)); Ok(()) } @@ -395,9 +419,10 @@ pub fn eval(prog: &[Op]) -> Result { Op::Mul => mul(&mut stack)?, Op::Div => div(&mut stack)?, Op::Mod => fn_mod(&mut stack)?, - Op::Alloc => alloc(&mut stack, &mut heap)?, - Op::Peek(n) => peek(&mut stack, &heap, n)?, - Op::Poke(n) => poke(&mut stack, &mut heap, n)?, + Op::Alloc => alloc(&mut stack, &mut locals_stack, &mut heap)?, + Op::AllocBytevector => alloc_bytevector(&mut stack, &mut locals_stack, &mut heap)?, + Op::Peek => peek(&mut stack, &heap)?, + Op::Poke => poke(&mut stack, &mut heap)?, Op::PeekByte => peek_byte(&mut stack, &heap)?, Op::PokeByte => poke_byte(&mut stack, &mut heap)?, Op::Pop => pop(&mut stack)?, @@ -409,7 +434,7 @@ pub fn eval(prog: &[Op]) -> Result { Op::GetC => getc(&mut stack, &mut files)?, Op::Exit => { let n = stack.pop_int()?; - return Ok(u8::try_from(n & 0xff).unwrap()); + return Ok((n & 0xff) as u8); } } ip += 1; @@ -456,29 +481,59 @@ mod tests { assert_eq!(Ok(0), eval(&vec![Const(10), Alloc, Pop, Const(0), Exit])); } + #[test] + fn eval_bytevector() { + assert_eq!( + Ok(0), + eval(&vec![Const(10), AllocBytevector, Pop, Const(0), Exit]) + ); + } + #[test] fn eval_peek() { - assert_eq!(Ok(0), eval(&vec![Const(8), Alloc, Peek(0), Exit])); + assert_eq!( + Ok(0), + eval(&vec![Const(8), Alloc, Const(0), Peek, Const(0), Exit]) + ); } #[test] fn eval_poke() { assert_eq!( Ok(0), - eval(&vec![Const(5), Const(8), Alloc, Poke(0), Const(0), Exit]) + eval(&vec![ + Const(5), + Const(8), + Alloc, + Const(0), + Poke, + Const(0), + Exit + ]) ); } #[test] fn eval_peek_byte() { - assert_eq!(Ok(0), eval(&vec![Const(1), Alloc, PeekByte, Exit])); + assert_eq!( + Ok(0), + eval(&vec![Const(1), Alloc, Const(0), PeekByte, Exit]) + ); } #[test] fn eval_poke_byte() { assert_eq!( Ok(0), - eval(&vec![Const(5), Const(1), Alloc, PokeByte, Const(0), Exit]) + eval(&vec![ + Const(5), + Const(1), + Alloc, + Const(0), + PokeByte, + Const(0), + Exit + ]) ); } -- cgit v1.3.1