From 3ddbeb0a17fc60b9af8482cd12d8e33da252a42b Mon Sep 17 00:00:00 2001 From: Cassie Jones Date: Fri, 28 Feb 2020 21:39:37 +0100 Subject: [PATCH] Add runtime library and example assembly This is further exploration into what the code could look time, but this time there were productive results. This has a few parts: - The runtime is written as Rust code! It's almost 100% unsafe code because I didn't want to think about safety boundaries with the assembly code that's outside the runtime. I can probably end up making almost all of it safe code with a little bit of work. - The code mostly works by constructing lambdas with the runtime function, and then lambda bodies are mostly just applying objects to each other with the ivy_app function. This sample program implements doing arithmetic on Church numerals, and then uses it to run the debug print 64 times. --- rt/.gitignore | 2 + rt/Cargo.toml | 20 ++++ rt/example.s | 178 ++++++++++++++++++++++++++++++++ rt/src/lib.rs | 279 ++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 479 insertions(+) create mode 100644 rt/.gitignore create mode 100644 rt/Cargo.toml create mode 100644 rt/example.s create mode 100644 rt/src/lib.rs diff --git a/rt/.gitignore b/rt/.gitignore new file mode 100644 index 0000000..e9e2199 --- /dev/null +++ b/rt/.gitignore @@ -0,0 +1,2 @@ +/target/ +/Cargo.lock diff --git a/rt/Cargo.toml b/rt/Cargo.toml new file mode 100644 index 0000000..067272c --- /dev/null +++ b/rt/Cargo.toml @@ -0,0 +1,20 @@ +[package] +name = "rt" +version = "0.1.0" +authors = ["Cassie Jones "] +edition = "2018" + +[lib] +crate-type = ["staticlib"] + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] + +[profile.dev] +panic = "abort" + +[profile.release] +lto = true +panic = "abort" +debug = true diff --git a/rt/example.s b/rt/example.s new file mode 100644 index 0000000..7d1c3d5 --- /dev/null +++ b/rt/example.s @@ -0,0 +1,178 @@ +// clang -masm=intel -nostdlib -Ltarget/release -lrt -lSystem -Wl,-e,_start -g example.s -o target/example + +.data +ZERO: .zero 8 +SUCC: .zero 8 +ADD: .zero 8 +MUL: .zero 8 +DEBUG: .zero 8 + +.text +.global _start +_start: + // Align the stack + sub rsp, 64 + and spl, 0xF0 + + lea rdi, [rip + zero] + mov rsi, 2 + mov rdx, 0 + call _ivy_make_lam + mov [rip + ZERO], rax + mov rdi, rax + call _ivy_incref + + lea rdi, [rip + succ] + mov rsi, 3 + mov rdx, 0 + call _ivy_make_lam + mov [rip + SUCC], rax + mov rdi, rax + call _ivy_incref + + lea rdi, [rip + add] + mov rsi, 4 + mov rdx, 0 + call _ivy_make_lam + mov [rip + ADD], rax + mov rdi, rax + call _ivy_incref + + lea rdi, [rip + mul] + mov rsi, 4 + mov rdx, 0 + call _ivy_make_lam + mov [rip + MUL], rax + mov rdi, rax + call _ivy_incref + + lea rdi, [rip + debug] + mov rsi, 1 + mov rdx, 0 + call _ivy_make_lam + mov [rip + DEBUG], rax + mov rdi, rax + call _ivy_incref + +main: + mov rdi, [rip + SUCC] + mov rsi, [rip + ZERO] + call _ivy_app // succ zero + mov rdi, [rip + SUCC] + mov rsi, rax + call _ivy_app // succ (succ zero) + // RAX contains Church #2 + mov [rsp], rax // 2 := succ (succ zero) + mov rdi, [rip + ADD] + mov rsi, rax + call _ivy_app // add 2 + mov rdi, rax + mov rsi, [rsp] + call _ivy_app // add 2 2 + mov [rsp], rax + // RAX contains Church #4 + mov rdi, [rip + MUL] + mov rsi, rax + call _ivy_app // mul (add 2 2) + mov rdi, rax + mov rsi, [rsp] + call _ivy_app // 16 := mul (add 2 2) (add 2 2) + mov rdi, [rip + MUL] + mov rsi, rax + call _ivy_app // mul (add 2 2) + mov rdi, rax + mov rsi, [rsp] + call _ivy_app // 64 := mul (add 2 2) 16 + // RAX contains Church #16 + mov rdi, rax + mov rsi, [rip + DEBUG] + call _ivy_app // 64 debug + mov rdi, rax + mov rsi, [rip + ZERO] + call _ivy_app // 64 debug zero + // This should print out "DBUG <0-addr>" 16 times. I hope. + + mov rdi, 0 + call _exit + +/* +let + zero = lam (f x) => x; + succ = lam (n f x) => f (n f x); + add = lam (m n f x) => m f (n f x); + mul = lam (m n f x) => m (n f) x; + debug = some magic nonsense +in let + two = succ (succ zero); + four = add two two; + _64 = mul (mul four four) four +in + _64 debug zero +*/ + +// \fx.x +zero: + mov rax, [rdi + (0x18 + 8)] + ret + +// \nfx.f(nfx) +succ: + push rbx + mov rbx, rdi + mov rdi, [rbx + 0x18] + mov rsi, [rbx + (0x18 + 8)] + call _ivy_app // nf + mov rdi, rax + mov rsi, [rbx + (0x18 + 16) + call _ivy_app // nfx + mov rdi, [rbx + (0x18 + 8)] + mov rsi, rax + call _ivy_app // f(nfx) + pop rbx + ret + +// \mnfx.mf(nfx) +add: + push rbx + sub rsp, 16 + mov rbx, rdi + mov rdi, [rbx + 0x18] + mov rsi, [rbx + (0x18 + 16)] + call _ivy_app // mf + mov [rsp], rax + mov rdi, [rbx + (0x18 + 8)] + mov rsi, [rbx + (0x18 + 16)] + call _ivy_app // nf + mov rdi, rax + mov rsi, [rbx + (0x18 + 24)] + call _ivy_app // nfx + mov rdi, [rsp] + mov rsi, rax + call _ivy_app // mf(nfx) + add rsp, 16 + pop rbx + ret + +// \mnfx.m(nf)x +mul: + push rbx + mov rbx, rdi + mov rdi, [rbx + (0x18 + 8)] + mov rsi, [rbx + (0x18 + 16)] + call _ivy_app // nf + mov rdi, [rbx + 0x18] + mov rsi, rax + call _ivy_app // m(nf) + mov rdi, rax + mov rsi, [rbx + (0x18 + 24)] + call _ivy_app // m(nf)x + pop rbx + ret + +// \x.debug x +debug: + push rbx + mov rdi, [rdi + 0x18] + call _ivy_debug + pop rbx + ret diff --git a/rt/src/lib.rs b/rt/src/lib.rs new file mode 100644 index 0000000..7250dad --- /dev/null +++ b/rt/src/lib.rs @@ -0,0 +1,279 @@ +#![no_std] +use core::{sync::atomic::{AtomicU32, Ordering}, panic::PanicInfo, fmt::Write}; + +#[panic_handler] +fn handle_panic(panic_info: &PanicInfo) -> ! { + if let Some(s) = panic_info.payload().downcast_ref::<&str>() { + abort(s); + } else { + abort("a panic occurred\n"); + } +} + +const STDOUT: i32 = 1; +const STDERR: i32 = 2; + +#[repr(u8)] +#[derive(PartialEq, Eq)] +pub enum ObjTag { + Lam = 0, + Int = 1, +} + +#[repr(C)] +pub struct ObjHeader { + tag: ObjTag, + rc: AtomicU32, +} + +#[repr(C)] +pub struct ObjInt { + tag: ObjTag, + rc: AtomicU32, + value: i64, +} + +#[repr(C)] +pub struct ObjLam { + tag: ObjTag, + upvars: u16, + rc: AtomicU32, + func: fn(&ObjLam) -> Obj, + params: u16, + filled: u16, +} + +#[derive(Clone, Copy)] +pub union Obj { + int: i64, + header: *mut ObjHeader, + box_int: *mut ObjInt, + box_lam: *mut ObjLam, +} + +mod sys { + extern "C" { + pub fn write(fd: i32, buf: *const u8, len: usize) -> isize; + pub fn exit(code: i32) -> !; + pub fn malloc(size: usize) -> *mut u8; + pub fn free(ptr: *mut u8); + } +} + +#[no_mangle] +pub unsafe extern "C" fn ivy_debug(obj: Obj) -> Obj { + // let mut buffer = String::new(); + // writeln!(&mut buffer, "DBUG {:016x}", obj.int); + const BUFFER: &str = "DEBUG\n"; + sys::write(STDOUT, BUFFER.as_ptr(), BUFFER.len()); + obj +} + +#[no_mangle] +pub unsafe extern "C" fn ivy_abort(msg: *const u8, len: usize) -> ! { + sys::write(STDERR, msg, len); + sys::exit(1); +} + +#[no_mangle] +pub unsafe extern "C" fn ivy_check_int(obj: Obj) { + if !obj.is_int() { + abort("Abort: ivy_check_int called with non-integer object.\n"); + } +} + +#[no_mangle] +pub unsafe extern "C" fn ivy_check_lam(obj: Obj) { + if !obj.is_lam() { + abort("Abort: ivy_check_lam called with non-lambda object.\n"); + } +} + +// This should probably be a macro rather than a call? +// But it might be good to have it for completeness. +// Or maybe it's valuable if we want to support big integers. +#[no_mangle] +pub unsafe extern "C" fn ivy_make_int(value: i64) -> Obj { + Obj { int: value << 1 } +} + +#[no_mangle] +pub unsafe extern "C" fn ivy_make_lam(func: fn(&ObjLam) -> Obj, params: u16, upvars: u16) -> Obj { + let size = ObjLam::size_of(params, upvars); + let box_lam = sys::malloc(size) as *mut ObjLam; + box_lam.write(ObjLam { + tag: ObjTag::Lam, + upvars, + rc: AtomicU32::new(0), + func, + params, + filled: 0, + }); + (*box_lam) + .raw_fields_mut() + .write_bytes(0, (params + upvars) as usize); + // println!("MAKE {:016x}", box_lam as usize); + Obj { box_lam } +} + +#[no_mangle] +pub unsafe extern "C" fn ivy_free(obj: Obj) { + if !obj.is_box() { + return; + } + sys::free(obj.header as *mut u8) +} + +#[no_mangle] +pub unsafe extern "C" fn ivy_incref(obj: Obj) { + obj.incref(); +} + +#[no_mangle] +pub unsafe extern "C" fn ivy_decref(obj: Obj) { + obj.decref(); +} + +#[no_mangle] +pub unsafe extern "C" fn ivy_clone(obj: Obj) -> Obj { + if obj.is_null() || !obj.is_box() { + return obj; + } + if obj.is_int() { + abort("Abort: copying boxed integers is not implemented.\n") + } + let lam = &*obj.box_lam; + let size = lam.size(); + let data = sys::malloc(size); + core::ptr::copy(obj.box_lam as *const u8, data, size); + let box_lam = data as *mut ObjLam; + *(*box_lam).rc.get_mut() = 0; + // println!("COPY {:016x} {:016x}", obj.int, box_lam as usize); + Obj { box_lam } +} + +#[no_mangle] +pub unsafe extern "C" fn ivy_app(mut fun: Obj, arg: Obj) -> Obj { + ivy_app_mut(ivy_clone(fun), arg) +} + +#[no_mangle] +pub unsafe extern "C" fn ivy_app_mut(fun: Obj, arg: Obj) -> Obj { + // println!("APP {:016x} {:016x}", fun.int, arg.int); + if !fun.is_lam() { + abort("Abort: ivy_app called with a non-lam as the function.\n"); + } + let lam = &mut *fun.box_lam; + if lam.filled < lam.params { + if arg.is_null() { + abort("Abort: ivy_app called with a null arg.\n"); + } + arg.incref(); + let idx = lam.filled as usize; + lam.params_mut()[idx] = arg; + lam.filled += 1; + } else if lam.params == lam.filled { + if !arg.is_null() { + abort("Abort: ivy_app called for a 0-arity application with a non-null arg.\n"); + } + } + + if lam.params == lam.filled { + // println!("RUN {:016x}", fun.int); + (lam.func)(lam) + } else { + // println!("UPD8 {:016x}", fun.int); + fun.incref(); + fun + } +} + +fn abort(msg: &str) -> ! { + unsafe { ivy_abort(msg.as_ptr(), msg.len()) } +} + +impl Obj { + fn is_null(self) -> bool { + unsafe { self.int == 0 } + } + + fn is_box(self) -> bool { + !self.is_null() && unsafe { self.int & 1 == 0 } + } + + unsafe fn refcount(self) -> u32 { + if self.is_box() { + (*self.header).rc.load(Ordering::SeqCst) + } else { + 1 + } + } + + unsafe fn unique(self) -> bool { + self.refcount() == 1 + } + + unsafe fn is_int(self) -> bool { + !self.is_null() && (!self.is_box() || (*self.header).tag == ObjTag::Int) + } + + unsafe fn is_lam(self) -> bool { + self.is_box() && (*self.header).tag == ObjTag::Lam + } + + unsafe fn incref(self) { + if !self.is_box() { + return; + } + (*self.header).rc.fetch_add(1, Ordering::SeqCst); + } + + unsafe fn decref(self) { + if !self.is_box() { + return; + } + if (*self.header).rc.fetch_sub(1, Ordering::SeqCst) == 1 { + self.dealloc(); + } + } + + unsafe fn dealloc(self) { + if !self.is_box() { + return; + } + if self.is_lam() { + let lam = &mut *self.box_lam; + for param in lam.params_mut() { + param.decref(); + } + for upvar in lam.upvars_mut() { + upvar.decref(); + } + } + sys::free(self.header as *mut u8); + } +} + +impl ObjLam { + fn size_of(params: u16, upvars: u16) -> usize { + core::mem::size_of::() + params as usize * 8 + upvars as usize * 8 + } + + fn size(&self) -> usize { + ObjLam::size_of(self.params, self.upvars) + } + + unsafe fn raw_fields_mut(&mut self) -> *mut Obj { + (self as *mut ObjLam).add(1) as *mut Obj + } + + unsafe fn params_mut(&mut self) -> &mut [Obj] { + let ptr = self.raw_fields_mut(); + core::slice::from_raw_parts_mut(ptr, self.params as usize) + } + + unsafe fn upvars_mut(&mut self) -> &mut [Obj] { + let ptr = self.raw_fields_mut().add(self.params as usize); + core::slice::from_raw_parts_mut(ptr, self.upvars as usize) + } +} -- 2.47.0