diff options
21 files changed, 559 insertions, 452 deletions
diff --git a/.cargo/config.toml b/.cargo/config.toml index b27192b..e702802 100644 --- a/.cargo/config.toml +++ b/.cargo/config.toml @@ -4,3 +4,4 @@ test-wasm-1="test --package tinywasm --test test-wasm-1 --release" test-wasm-2="test --package tinywasm --test test-wasm-2 --release" test-wasm-3="test --package tinywasm --test test-wasm-3 --release" test-wast="test --package tinywasm --test test-wast" +test-wasm-custom="test --package tinywasm --test test-wasm-custom --release" diff --git a/.vscode/settings.json b/.vscode/settings.json deleted file mode 100644 index 48a2e0d..0000000 --- a/.vscode/settings.json +++ /dev/null @@ -1,8 +0,0 @@ -{ - "search.exclude": { - "**/wasm-testsuite/data": true - }, - "rust-analyzer.linkedProjects": [ - "./Cargo.toml", - ], -}
\ No newline at end of file diff --git a/crates/parser/src/visit.rs b/crates/parser/src/visit.rs index cb9a3d2..9a707af 100644 --- a/crates/parser/src/visit.rs +++ b/crates/parser/src/visit.rs @@ -1,13 +1,37 @@ use crate::Result; -use crate::conversion::{convert_heaptype, convert_valtype}; +use crate::conversion::convert_heaptype; use alloc::string::ToString; +use alloc::vec; use alloc::vec::Vec; use tinywasm_types::{Instruction, MemoryArg, WasmFunctionData}; use wasmparser::{ - FuncValidator, FuncValidatorAllocations, FunctionBody, VisitOperator, VisitSimdOperator, WasmModuleResources, + FrameKind, FuncValidator, FuncValidatorAllocations, FunctionBody, VisitOperator, VisitSimdOperator, + WasmModuleResources, }; +#[derive(Debug, Clone, Copy)] +enum BlockKind { + Block, + Loop, + If, +} + +#[derive(Debug, Clone, Copy, Default)] +struct StackBase { + s32: u16, + s64: u16, + s128: u16, + sref: u16, +} + +struct LoweringCtx { + kind: BlockKind, + has_else: bool, + start_ip: usize, + branch_jumps: Vec<usize>, +} + struct ValidateThenVisit<'a, R: WasmModuleResources>(usize, &'a mut FunctionBuilder<R>); macro_rules! validate_then_visit { @@ -112,7 +136,7 @@ pub(crate) struct FunctionBuilder<R: WasmModuleResources> { validator: FuncValidator<R>, instructions: Vec<Instruction>, v128_constants: Vec<i128>, - label_ptrs: Vec<usize>, + ctx_stack: Vec<LoweringCtx>, local_addr_map: Vec<u32>, errors: Vec<crate::ParseError>, } @@ -124,23 +148,157 @@ impl<R: WasmModuleResources> FunctionBuilder<R> { ) -> impl VisitOperator<'_, Output = Result<(), wasmparser::BinaryReaderError>> + VisitSimdOperator<'_> { self.validator.simd_visitor(offset) } -} -impl<R: WasmModuleResources> FunctionBuilder<R> { pub(crate) fn new(instr_capacity: usize, validator: FuncValidator<R>, local_addr_map: Vec<u32>) -> Self { Self { validator, local_addr_map, instructions: Vec::with_capacity(instr_capacity), v128_constants: Vec::new(), - label_ptrs: Vec::with_capacity(256), + ctx_stack: Vec::with_capacity(256), errors: Vec::new(), } } + fn stack_base_at_frame(&self, depth: usize) -> StackBase { + let frame = match self.validator.get_control_frame(depth) { + Some(f) => f, + None => return StackBase::default(), + }; + let height = frame.height; + let current = self.validator.operand_stack_height() as usize; + + let mut base = StackBase::default(); + for i in 0..height { + let depth_from_top = current - 1 - i; + if let Some(Some(ty)) = self.validator.get_operand_type(depth_from_top) { + match ty { + wasmparser::ValType::I32 | wasmparser::ValType::F32 => base.s32 += 1, + wasmparser::ValType::I64 | wasmparser::ValType::F64 => base.s64 += 1, + wasmparser::ValType::V128 => base.s128 += 1, + wasmparser::ValType::Ref(_) => base.sref += 1, + } + } + } + + base + } + fn unsupported(&mut self, name: &str) { self.errors.push(crate::ParseError::UnsupportedOperator(name.to_string())); } + + fn current_ip(&self) -> u32 { + self.instructions.len() as u32 + } + + fn is_unreachable(&self) -> bool { + self.validator.get_control_frame(0).is_none_or(|f| f.unreachable) + } + + fn get_ctx_idx(&self, depth: u32) -> Option<usize> { + let len = self.ctx_stack.len(); + let idx = len.checked_sub(depth as usize + 1)?; + Some(idx) + } + + fn emit_dropkeep(&mut self, base: StackBase, c32: u16, c64: u16, c128: u16, cref: u16) { + let fits_u8 = base.s32 <= u8::MAX as u16 + && c32 <= u8::MAX as u16 + && base.s64 <= u8::MAX as u16 + && c64 <= u8::MAX as u16 + && base.s128 <= u8::MAX as u16 + && c128 <= u8::MAX as u16 + && base.sref <= u8::MAX as u16 + && cref <= u8::MAX as u16; + + if fits_u8 { + self.instructions.push(Instruction::DropKeepSmall { + base32: base.s32 as u8, + keep32: c32 as u8, + base64: base.s64 as u8, + keep64: c64 as u8, + base128: base.s128 as u8, + keep128: c128 as u8, + base_ref: base.sref as u8, + keep_ref: cref as u8, + }); + } else { + self.instructions.push(Instruction::DropKeep32(base.s32, c32)); + self.instructions.push(Instruction::DropKeep64(base.s64, c64)); + self.instructions.push(Instruction::DropKeep128(base.s128, c128)); + self.instructions.push(Instruction::DropKeepRef(base.sref, cref)); + } + } + + fn patch_jump(&mut self, jump_ip: usize, target: u32) { + if let Instruction::Jump(ip) = &mut self.instructions[jump_ip] { + *ip = target; + } + } + + fn patch_jump_if_zero(&mut self, jump_ip: usize, target: u32) { + if let Instruction::JumpIfZero(ip) = &mut self.instructions[jump_ip] { + *ip = target; + } + } + + fn label_keep_counts(label_types: &[wasmparser::ValType]) -> (u16, u16, u16, u16) { + let mut c32: u16 = 0; + let mut c64: u16 = 0; + let mut c128: u16 = 0; + let mut cref: u16 = 0; + + for ty in label_types { + match ty { + wasmparser::ValType::I32 | wasmparser::ValType::F32 => c32 += 1, + wasmparser::ValType::I64 | wasmparser::ValType::F64 => c64 += 1, + wasmparser::ValType::V128 => c128 += 1, + wasmparser::ValType::Ref(_) => cref += 1, + } + } + + (c32, c64, c128, cref) + } + + fn emit_dropkeep_to_label(&mut self, label_depth: u32) { + if self.is_unreachable() { + return; + } + + let frame = match self.validator.get_control_frame(label_depth as usize) { + Some(f) => f, + None => return, + }; + + let base = self.stack_base_at_frame(label_depth as usize); + let label_types: Vec<_> = self.label_types_for_frame(frame); + let (c32, c64, c128, cref) = Self::label_keep_counts(&label_types); + + self.emit_dropkeep(base, c32, c64, c128, cref); + } + + fn label_types_for_frame(&self, frame: &wasmparser::Frame) -> Vec<wasmparser::ValType> { + let ty = &frame.block_type; + match ty { + wasmparser::BlockType::Empty => Vec::new(), + wasmparser::BlockType::Type(ty) => match frame.kind { + FrameKind::Loop => Vec::new(), + _ => vec![*ty], + }, + wasmparser::BlockType::FuncType(idx) => { + let sub_type = self.validator.resources().sub_type_at(*idx); + let func_ty = match sub_type { + Some(st) => st.composite_type.unwrap_func(), + None => return Vec::new(), + }; + match frame.kind { + FrameKind::Loop => func_ty.params().to_vec(), + _ => func_ty.results().to_vec(), + } + } + } + } } macro_rules! impl_visit_operator { @@ -177,7 +335,7 @@ impl<'a, R: WasmModuleResources> wasmparser::VisitOperator<'a> for FunctionBuild define_operands! { // basic instructions - visit_br(Br, u32), visit_br_if(BrIf, u32), visit_global_get(GlobalGet, u32), visit_i32_const(I32Const, i32), visit_i64_const(I64Const, i64), visit_call(Call, u32), visit_return_call(ReturnCall, u32), visit_memory_size(MemorySize, u32), visit_memory_grow(MemoryGrow, u32), visit_unreachable(Unreachable), visit_nop(Nop), visit_return(Return), visit_i32_eqz(I32Eqz), visit_i32_eq(I32Eq), visit_i32_ne(I32Ne), visit_i32_lt_s(I32LtS), visit_i32_lt_u(I32LtU), visit_i32_gt_s(I32GtS), visit_i32_gt_u(I32GtU), visit_i32_le_s(I32LeS), visit_i32_le_u(I32LeU), visit_i32_ge_s(I32GeS), visit_i32_ge_u(I32GeU), visit_i64_eqz(I64Eqz), visit_i64_eq(I64Eq), visit_i64_ne(I64Ne), visit_i64_lt_s(I64LtS), visit_i64_lt_u(I64LtU), visit_i64_gt_s(I64GtS), visit_i64_gt_u(I64GtU), visit_i64_le_s(I64LeS), visit_i64_le_u(I64LeU), visit_i64_ge_s(I64GeS), visit_i64_ge_u(I64GeU), visit_f32_eq(F32Eq), visit_f32_ne(F32Ne), visit_f32_lt(F32Lt), visit_f32_gt(F32Gt), visit_f32_le(F32Le), visit_f32_ge(F32Ge), visit_f64_eq(F64Eq), visit_f64_ne(F64Ne), visit_f64_lt(F64Lt), visit_f64_gt(F64Gt), visit_f64_le(F64Le), visit_f64_ge(F64Ge), visit_i32_clz(I32Clz), visit_i32_ctz(I32Ctz), visit_i32_popcnt(I32Popcnt), visit_i32_add(I32Add), visit_i32_sub(I32Sub), visit_i32_mul(I32Mul), visit_i32_div_s(I32DivS), visit_i32_div_u(I32DivU), visit_i32_rem_s(I32RemS), visit_i32_rem_u(I32RemU), visit_i32_and(I32And), visit_i32_or(I32Or), visit_i32_xor(I32Xor), visit_i32_shl(I32Shl), visit_i32_shr_s(I32ShrS), visit_i32_shr_u(I32ShrU), visit_i32_rotl(I32Rotl), visit_i32_rotr(I32Rotr), visit_i64_clz(I64Clz), visit_i64_ctz(I64Ctz), visit_i64_popcnt(I64Popcnt), visit_i64_add(I64Add), visit_i64_sub(I64Sub), visit_i64_mul(I64Mul), visit_i64_div_s(I64DivS), visit_i64_div_u(I64DivU), visit_i64_rem_s(I64RemS), visit_i64_rem_u(I64RemU), visit_i64_and(I64And), visit_i64_or(I64Or), visit_i64_xor(I64Xor), visit_i64_shl(I64Shl), visit_i64_shr_s(I64ShrS), visit_i64_shr_u(I64ShrU), visit_i64_rotl(I64Rotl), visit_i64_rotr(I64Rotr), visit_f32_abs(F32Abs), visit_f32_neg(F32Neg), visit_f32_ceil(F32Ceil), visit_f32_floor(F32Floor), visit_f32_trunc(F32Trunc), visit_f32_nearest(F32Nearest), visit_f32_sqrt(F32Sqrt), visit_f32_add(F32Add), visit_f32_sub(F32Sub), visit_f32_mul(F32Mul), visit_f32_div(F32Div), visit_f32_min(F32Min), visit_f32_max(F32Max), visit_f32_copysign(F32Copysign), visit_f64_abs(F64Abs), visit_f64_neg(F64Neg), visit_f64_ceil(F64Ceil), visit_f64_floor(F64Floor), visit_f64_trunc(F64Trunc), visit_f64_nearest(F64Nearest), visit_f64_sqrt(F64Sqrt), visit_f64_add(F64Add), visit_f64_sub(F64Sub), visit_f64_mul(F64Mul), visit_f64_div(F64Div), visit_f64_min(F64Min), visit_f64_max(F64Max), visit_f64_copysign(F64Copysign), visit_i32_wrap_i64(I32WrapI64), visit_i32_trunc_f32_s(I32TruncF32S), visit_i32_trunc_f32_u(I32TruncF32U), visit_i32_trunc_f64_s(I32TruncF64S), visit_i32_trunc_f64_u(I32TruncF64U), visit_i64_extend_i32_s(I64ExtendI32S), visit_i64_extend_i32_u(I64ExtendI32U), visit_i64_trunc_f32_s(I64TruncF32S), visit_i64_trunc_f32_u(I64TruncF32U), visit_i64_trunc_f64_s(I64TruncF64S), visit_i64_trunc_f64_u(I64TruncF64U), visit_f32_convert_i32_s(F32ConvertI32S), visit_f32_convert_i32_u(F32ConvertI32U), visit_f32_convert_i64_s(F32ConvertI64S), visit_f32_convert_i64_u(F32ConvertI64U), visit_f32_demote_f64(F32DemoteF64), visit_f64_convert_i32_s(F64ConvertI32S), visit_f64_convert_i32_u(F64ConvertI32U), visit_f64_convert_i64_s(F64ConvertI64S), visit_f64_convert_i64_u(F64ConvertI64U), visit_f64_promote_f32(F64PromoteF32), visit_i32_reinterpret_f32(I32ReinterpretF32), visit_i64_reinterpret_f64(I64ReinterpretF64), visit_f32_reinterpret_i32(F32ReinterpretI32), visit_f64_reinterpret_i64(F64ReinterpretI64), + visit_global_get(GlobalGet, u32), visit_i32_const(I32Const, i32), visit_i64_const(I64Const, i64), visit_call(Call, u32), visit_return_call(ReturnCall, u32), visit_memory_size(MemorySize, u32), visit_memory_grow(MemoryGrow, u32), visit_unreachable(Unreachable), visit_nop(Nop), visit_return(Return), visit_i32_eqz(I32Eqz), visit_i32_eq(I32Eq), visit_i32_ne(I32Ne), visit_i32_lt_s(I32LtS), visit_i32_lt_u(I32LtU), visit_i32_gt_s(I32GtS), visit_i32_gt_u(I32GtU), visit_i32_le_s(I32LeS), visit_i32_le_u(I32LeU), visit_i32_ge_s(I32GeS), visit_i32_ge_u(I32GeU), visit_i64_eqz(I64Eqz), visit_i64_eq(I64Eq), visit_i64_ne(I64Ne), visit_i64_lt_s(I64LtS), visit_i64_lt_u(I64LtU), visit_i64_gt_s(I64GtS), visit_i64_gt_u(I64GtU), visit_i64_le_s(I64LeS), visit_i64_le_u(I64LeU), visit_i64_ge_s(I64GeS), visit_i64_ge_u(I64GeU), visit_f32_eq(F32Eq), visit_f32_ne(F32Ne), visit_f32_lt(F32Lt), visit_f32_gt(F32Gt), visit_f32_le(F32Le), visit_f32_ge(F32Ge), visit_f64_eq(F64Eq), visit_f64_ne(F64Ne), visit_f64_lt(F64Lt), visit_f64_gt(F64Gt), visit_f64_le(F64Le), visit_f64_ge(F64Ge), visit_i32_clz(I32Clz), visit_i32_ctz(I32Ctz), visit_i32_popcnt(I32Popcnt), visit_i32_add(I32Add), visit_i32_sub(I32Sub), visit_i32_mul(I32Mul), visit_i32_div_s(I32DivS), visit_i32_div_u(I32DivU), visit_i32_rem_s(I32RemS), visit_i32_rem_u(I32RemU), visit_i32_and(I32And), visit_i32_or(I32Or), visit_i32_xor(I32Xor), visit_i32_shl(I32Shl), visit_i32_shr_s(I32ShrS), visit_i32_shr_u(I32ShrU), visit_i32_rotl(I32Rotl), visit_i32_rotr(I32Rotr), visit_i64_clz(I64Clz), visit_i64_ctz(I64Ctz), visit_i64_popcnt(I64Popcnt), visit_i64_add(I64Add), visit_i64_sub(I64Sub), visit_i64_mul(I64Mul), visit_i64_div_s(I64DivS), visit_i64_div_u(I64DivU), visit_i64_rem_s(I64RemS), visit_i64_rem_u(I64RemU), visit_i64_and(I64And), visit_i64_or(I64Or), visit_i64_xor(I64Xor), visit_i64_shl(I64Shl), visit_i64_shr_s(I64ShrS), visit_i64_shr_u(I64ShrU), visit_i64_rotl(I64Rotl), visit_i64_rotr(I64Rotr), visit_f32_abs(F32Abs), visit_f32_neg(F32Neg), visit_f32_ceil(F32Ceil), visit_f32_floor(F32Floor), visit_f32_trunc(F32Trunc), visit_f32_nearest(F32Nearest), visit_f32_sqrt(F32Sqrt), visit_f32_add(F32Add), visit_f32_sub(F32Sub), visit_f32_mul(F32Mul), visit_f32_div(F32Div), visit_f32_min(F32Min), visit_f32_max(F32Max), visit_f32_copysign(F32Copysign), visit_f64_abs(F64Abs), visit_f64_neg(F64Neg), visit_f64_ceil(F64Ceil), visit_f64_floor(F64Floor), visit_f64_trunc(F64Trunc), visit_f64_nearest(F64Nearest), visit_f64_sqrt(F64Sqrt), visit_f64_add(F64Add), visit_f64_sub(F64Sub), visit_f64_mul(F64Mul), visit_f64_div(F64Div), visit_f64_min(F64Min), visit_f64_max(F64Max), visit_f64_copysign(F64Copysign), visit_i32_wrap_i64(I32WrapI64), visit_i32_trunc_f32_s(I32TruncF32S), visit_i32_trunc_f32_u(I32TruncF32U), visit_i32_trunc_f64_s(I32TruncF64S), visit_i32_trunc_f64_u(I32TruncF64U), visit_i64_extend_i32_s(I64ExtendI32S), visit_i64_extend_i32_u(I64ExtendI32U), visit_i64_trunc_f32_s(I64TruncF32S), visit_i64_trunc_f32_u(I64TruncF32U), visit_i64_trunc_f64_s(I64TruncF64S), visit_i64_trunc_f64_u(I64TruncF64U), visit_f32_convert_i32_s(F32ConvertI32S), visit_f32_convert_i32_u(F32ConvertI32U), visit_f32_convert_i64_s(F32ConvertI64S), visit_f32_convert_i64_u(F32ConvertI64U), visit_f32_demote_f64(F32DemoteF64), visit_f64_convert_i32_s(F64ConvertI32S), visit_f64_convert_i32_u(F64ConvertI32U), visit_f64_convert_i64_s(F64ConvertI64S), visit_f64_convert_i64_u(F64ConvertI64U), visit_f64_promote_f32(F64PromoteF32), visit_i32_reinterpret_f32(I32ReinterpretF32), visit_i64_reinterpret_f64(I64ReinterpretF64), visit_f32_reinterpret_i32(F32ReinterpretI32), visit_f64_reinterpret_i64(F64ReinterpretI64), // sign_extension visit_i32_extend8_s(I32Extend8S), visit_i32_extend16_s(I32Extend16S), visit_i64_extend8_s(I64Extend8S), visit_i64_extend16_s(I64Extend16S), visit_i64_extend32_s(I64Extend32S), @@ -328,110 +486,205 @@ impl<'a, R: WasmModuleResources> wasmparser::VisitOperator<'a> for FunctionBuild } } - fn visit_block(&mut self, blockty: wasmparser::BlockType) -> Self::Output { - self.label_ptrs.push(self.instructions.len()); - self.instructions.push(match blockty { - wasmparser::BlockType::Empty => Instruction::Block(0), - wasmparser::BlockType::FuncType(idx) => Instruction::BlockWithFuncType(idx, 0), - wasmparser::BlockType::Type(ty) => Instruction::BlockWithType(convert_valtype(&ty), 0), + fn visit_block(&mut self, _blockty: wasmparser::BlockType) -> Self::Output { + let start_ip = self.current_ip() as usize; + self.ctx_stack.push(LoweringCtx { + kind: BlockKind::Block, + has_else: false, + start_ip, + branch_jumps: Vec::new(), }); } - fn visit_loop(&mut self, ty: wasmparser::BlockType) -> Self::Output { - self.label_ptrs.push(self.instructions.len()); - self.instructions.push(match ty { - wasmparser::BlockType::Empty => Instruction::Loop(0), - wasmparser::BlockType::FuncType(idx) => Instruction::LoopWithFuncType(idx, 0), - wasmparser::BlockType::Type(ty) => Instruction::LoopWithType(convert_valtype(&ty), 0), - }); + fn visit_loop(&mut self, _ty: wasmparser::BlockType) -> Self::Output { + let start_ip = self.current_ip() as usize; + self.ctx_stack.push(LoweringCtx { kind: BlockKind::Loop, has_else: false, start_ip, branch_jumps: Vec::new() }); } - fn visit_if(&mut self, ty: wasmparser::BlockType) -> Self::Output { - self.label_ptrs.push(self.instructions.len()); - self.instructions.push(match ty { - wasmparser::BlockType::Empty => Instruction::If(0, 0), - wasmparser::BlockType::FuncType(idx) => Instruction::IfWithFuncType(idx, 0, 0), - wasmparser::BlockType::Type(ty) => Instruction::IfWithType(convert_valtype(&ty), 0, 0), + fn visit_if(&mut self, _ty: wasmparser::BlockType) -> Self::Output { + let cond_jump_ip = self.current_ip() as usize; + self.instructions.push(Instruction::JumpIfZero(0)); + let start_ip = self.current_ip() as usize; + self.ctx_stack.push(LoweringCtx { + kind: BlockKind::If, + has_else: false, + start_ip, + branch_jumps: alloc::vec![cond_jump_ip], }); } fn visit_else(&mut self) -> Self::Output { - self.label_ptrs.push(self.instructions.len()); - self.instructions.push(Instruction::Else(0)); + let Some(cond_jump_ip) = self + .ctx_stack + .last() + .and_then(|ctx| if matches!(ctx.kind, BlockKind::If) { Some(ctx.branch_jumps[0]) } else { None }) + else { + return; + }; + + let jump_ip = self.current_ip() as usize; + self.instructions.push(Instruction::Jump(0)); + + let after_jump_ip = self.current_ip(); + let Some(ctx) = self.ctx_stack.last_mut() else { + return; + }; + ctx.has_else = true; + ctx.branch_jumps.push(jump_ip); + self.patch_jump_if_zero(cond_jump_ip, after_jump_ip); } fn visit_end(&mut self) -> Self::Output { - let Some(label_pointer) = self.label_ptrs.pop() else { - return self.instructions.push(Instruction::Return); - }; + if self.ctx_stack.is_empty() { + self.instructions.push(Instruction::Return); + return; + } - let current_instr_ptr = self.instructions.len(); - match self.instructions.get_mut(label_pointer) { - Some(Instruction::Else(else_instr_end_offset)) => { - *else_instr_end_offset = (current_instr_ptr - label_pointer) - .try_into() - .expect("else_instr_end_offset is too large, tinywasm does not support if blocks that large"); + let ctx = self.ctx_stack.pop().unwrap(); + let end_ip = self.current_ip(); - // since we're ending an else block, we need to end the if block as well - let Some(if_label_pointer) = self.label_ptrs.pop() else { - self.errors.push(crate::ParseError::UnsupportedOperator( - "Expected to end an if block, but there was no if block to end".to_string(), - )); + match ctx.kind { + BlockKind::Block | BlockKind::Loop => { + let target = if matches!(ctx.kind, BlockKind::Loop) { ctx.start_ip as u32 } else { end_ip }; + for &jump_ip in &ctx.branch_jumps { + self.patch_jump(jump_ip, target); + } + } + BlockKind::If => { + let cond_jump_ip = ctx.branch_jumps[0]; + if !ctx.has_else { + self.patch_jump_if_zero(cond_jump_ip, end_ip); + } + for &jump_ip in &ctx.branch_jumps[1..] { + self.patch_jump(jump_ip, end_ip); + } + } + } + } - return; - }; + fn visit_br(&mut self, depth: u32) -> Self::Output { + self.emit_dropkeep_to_label(depth); - let if_instruction = &mut self.instructions[if_label_pointer]; + if let Some(ctx_idx) = self.get_ctx_idx(depth) { + let jump_ip = self.current_ip() as usize; + self.instructions.push(Instruction::Jump(0)); + self.ctx_stack[ctx_idx].branch_jumps.push(jump_ip); + } else { + self.instructions.push(Instruction::Return); + } + } - let (Instruction::If(else_offset, end_offset) - | Instruction::IfWithFuncType(_, else_offset, end_offset) - | Instruction::IfWithType(_, else_offset, end_offset)) = if_instruction - else { - return self.errors.push(crate::ParseError::UnsupportedOperator( - "Expected to end an if block, but the last label was not an if".to_string(), - )); - }; + fn visit_br_if(&mut self, depth: u32) -> Self::Output { + let cond_jump_ip = self.current_ip() as usize; + self.instructions.push(Instruction::JumpIfZero(0)); - *else_offset = (label_pointer - if_label_pointer) - .try_into() - .expect("else_instr_end_offset is too large, tinywasm does not support blocks that large"); + self.emit_dropkeep_to_label(depth); - *end_offset = (current_instr_ptr - if_label_pointer) - .try_into() - .expect("else_instr_end_offset is too large, tinywasm does not support blocks that large"); - } - Some( - Instruction::Block(end_offset) - | Instruction::BlockWithType(_, end_offset) - | Instruction::BlockWithFuncType(_, end_offset) - | Instruction::Loop(end_offset) - | Instruction::LoopWithFuncType(_, end_offset) - | Instruction::LoopWithType(_, end_offset) - | Instruction::If(_, end_offset) - | Instruction::IfWithFuncType(_, _, end_offset) - | Instruction::IfWithType(_, _, end_offset), - ) => { - *end_offset = (current_instr_ptr - label_pointer) - .try_into() - .expect("else_instr_end_offset is too large, tinywasm does not support blocks that large"); - } - _ => { - unreachable!("Expected to end a block, but the last label was not a block") - } - }; + if let Some(ctx_idx) = self.get_ctx_idx(depth) { + let jump_ip = self.current_ip() as usize; + self.instructions.push(Instruction::Jump(0)); + self.ctx_stack[ctx_idx].branch_jumps.push(jump_ip); + } else { + self.instructions.push(Instruction::Return); + } - self.instructions.push(Instruction::EndBlockFrame); + self.patch_jump_if_zero(cond_jump_ip, self.current_ip()); } fn visit_br_table(&mut self, targets: wasmparser::BrTable<'_>) -> Self::Output { - let def = targets.default(); - let instrs = targets + let ts = targets .targets() - .map(|t| t.map(Instruction::BrLabel)) - .collect::<Result<Vec<Instruction>, wasmparser::BinaryReaderError>>() - .expect("visit_br_table: BrTable targets are invalid, this should have been caught by the validator"); + .collect::<Result<Vec<_>, wasmparser::BinaryReaderError>>() + .expect("visit_br_table: BrTable targets are invalid"); - self.instructions.extend(([Instruction::BrTable(def, instrs.len() as u32)].into_iter()).chain(instrs)); + let default_depth = targets.default(); + let len = ts.len() as u32; + let target_depths: Vec<u32> = ts; + + let header_ip = self.current_ip() as usize; + self.instructions.push(Instruction::BranchTable(0, len)); + + let target_table_ip = self.current_ip() as usize; + for _ in 0..len { + self.instructions.push(Instruction::BranchTableTarget(0)); + } + let default_target_ip = self.current_ip() as usize; + self.instructions.push(Instruction::BranchTableTarget(0)); + + let mut seen = alloc::collections::BTreeMap::<u32, usize>::new(); + struct PadInfo { + depth: u32, + pad_start: u32, + jump_or_ret_ip: usize, + is_return: bool, + } + let mut pads: Vec<PadInfo> = Vec::new(); + + for &depth in target_depths.iter().chain(core::iter::once(&default_depth)) { + if seen.contains_key(&depth) { + continue; + } + seen.insert(depth, pads.len()); + + let pad_start = self.current_ip(); + + let frame = if self.is_unreachable() { None } else { self.validator.get_control_frame(depth as usize) }; + let Some(frame) = frame else { + let ip = self.current_ip() as usize; + self.instructions.push(Instruction::Return); + pads.push(PadInfo { depth, pad_start, jump_or_ret_ip: ip, is_return: true }); + continue; + }; + + let base = self.stack_base_at_frame(depth as usize); + let label_types: Vec<_> = self.label_types_for_frame(frame); + let (c32, c64, c128, cref) = Self::label_keep_counts(&label_types); + + self.emit_dropkeep(base, c32, c64, c128, cref); + + let jump_ip = self.current_ip() as usize; + self.instructions.push(Instruction::Jump(0)); + pads.push(PadInfo { depth, pad_start, jump_or_ret_ip: jump_ip, is_return: false }); + } + + for (i, &depth) in target_depths.iter().enumerate() { + let pad_idx = seen[&depth]; + if let Instruction::BranchTableTarget(ip) = &mut self.instructions[target_table_ip + i] { + *ip = pads[pad_idx].pad_start; + } + } + + let default_pad_idx = seen[&default_depth]; + if let Instruction::BranchTableTarget(ip) = &mut self.instructions[default_target_ip] { + *ip = pads[default_pad_idx].pad_start; + } + if let Instruction::BranchTable(default_ip, _) = &mut self.instructions[header_ip] { + *default_ip = pads[default_pad_idx].pad_start; + } + + for pad in &pads { + if pad.is_return { + continue; + } + let Some(frame) = self.validator.get_control_frame(pad.depth as usize) else { + self.instructions[pad.jump_or_ret_ip] = Instruction::Return; + continue; + }; + let Some(ctx_idx) = self.get_ctx_idx(pad.depth) else { + self.instructions[pad.jump_or_ret_ip] = Instruction::Return; + continue; + }; + match frame.kind { + FrameKind::Loop => { + if let Instruction::Jump(target) = &mut self.instructions[pad.jump_or_ret_ip] { + *target = self.ctx_stack[ctx_idx].start_ip as u32; + } + } + _ => { + self.ctx_stack[ctx_idx].branch_jumps.push(pad.jump_or_ret_ip); + } + } + } } fn visit_call_indirect(&mut self, ty: u32, table: u32) -> Self::Output { diff --git a/crates/tinywasm/Cargo.toml b/crates/tinywasm/Cargo.toml index d1a0839..18f0365 100644 --- a/crates/tinywasm/Cargo.toml +++ b/crates/tinywasm/Cargo.toml @@ -73,6 +73,10 @@ name="test-wasm-custom-page-sizes" harness=false [[test]] +name="test-wasm-custom" +harness=false + +[[test]] name="test-wasm-tail-call" harness=false diff --git a/crates/tinywasm/benches/argon2id.rs b/crates/tinywasm/benches/argon2id.rs index aa8b38b..74ce1ad 100644 --- a/crates/tinywasm/benches/argon2id.rs +++ b/crates/tinywasm/benches/argon2id.rs @@ -5,6 +5,10 @@ use types::TinyWasmModule; const WASM: &[u8] = include_bytes!("../../../examples/rust/out/argon2id.opt.wasm"); +fn init_log() { + let _ = pretty_env_logger::formatted_timed_builder().filter_level(log::LevelFilter::Off).try_init(); +} + fn argon2id_parse() -> Result<TinyWasmModule> { let parser = tinywasm_parser::Parser::new(); let data = parser.parse_module_bytes(WASM)?; @@ -30,6 +34,7 @@ fn argon2id_run(module: TinyWasmModule) -> Result<()> { } fn criterion_benchmark(c: &mut Criterion) { + init_log(); let module = argon2id_parse().expect("argon2id_parse"); let twasm = argon2id_to_twasm(&module).expect("argon2id_to_twasm"); diff --git a/crates/tinywasm/benches/tinywasm.rs b/crates/tinywasm/benches/tinywasm.rs index 4848a4a..7ad2082 100644 --- a/crates/tinywasm/benches/tinywasm.rs +++ b/crates/tinywasm/benches/tinywasm.rs @@ -35,9 +35,9 @@ fn criterion_benchmark(c: &mut Criterion) { let module = tinywasm_parse().expect("tinywasm_parse"); let twasm = tinywasm_to_twasm(&module).expect("tinywasm_to_twasm"); - c.bench_function("tinywasm_parse", |b| b.iter(tinywasm_parse)); - c.bench_function("tinywasm_to_twasm", |b| b.iter(|| tinywasm_to_twasm(&module))); - c.bench_function("tinywasm_from_twasm", |b| b.iter(|| tinywasm_from_twasm(&twasm))); + // c.bench_function("tinywasm_parse", |b| b.iter(tinywasm_parse)); + // c.bench_function("tinywasm_to_twasm", |b| b.iter(|| tinywasm_to_twasm(&module))); + // c.bench_function("tinywasm_from_twasm", |b| b.iter(|| tinywasm_from_twasm(&twasm))); c.bench_function("tinywasm", |b| b.iter(|| tinywasm_run(module.clone()))); } diff --git a/crates/tinywasm/src/engine.rs b/crates/tinywasm/src/engine.rs index fe30513..f03f749 100644 --- a/crates/tinywasm/src/engine.rs +++ b/crates/tinywasm/src/engine.rs @@ -51,9 +51,6 @@ pub const DEFAULT_VALUE_STACK_128_SIZE: usize = 4 * 1024; // 4k slots /// Default initial size for the reference value stack (funcref, externref values). pub const DEFAULT_VALUE_STACK_REF_SIZE: usize = 4 * 1024; // 4k slots -/// Default initial size for the block stack (control frames). -pub const DEFAULT_BLOCK_STACK_SIZE: usize = 2048; // 1024 frames - /// Default initial size for the call stack (function frames). pub const DEFAULT_CALL_STACK_SIZE: usize = 2048; // 1024 frames @@ -71,9 +68,6 @@ pub struct Config { pub stack_ref_size: usize, /// Initial size of the call stack. pub call_stack_size: usize, - - /// Initial size of the block stack. - pub block_stack_initial_size: usize, } impl Config { @@ -91,7 +85,6 @@ impl Default for Config { stack_128_size: DEFAULT_VALUE_STACK_128_SIZE, stack_ref_size: DEFAULT_VALUE_STACK_REF_SIZE, call_stack_size: DEFAULT_CALL_STACK_SIZE, - block_stack_initial_size: DEFAULT_BLOCK_STACK_SIZE, } } } diff --git a/crates/tinywasm/src/error.rs b/crates/tinywasm/src/error.rs index 51b5c46..106f9d1 100644 --- a/crates/tinywasm/src/error.rs +++ b/crates/tinywasm/src/error.rs @@ -121,9 +121,6 @@ pub enum Trap { /// Call stack overflow CallStackOverflow, - /// Block stack overflow - BlockStackOverflow, - /// Value stack overflow ValueStackOverflow, @@ -159,7 +156,6 @@ impl Trap { Self::InvalidConversionToInt => "invalid conversion to integer", Self::IntegerOverflow => "integer overflow", Self::CallStackOverflow => "call stack exhausted", - Self::BlockStackOverflow => "block stack exhausted", Self::ValueStackOverflow => "value stack exhausted", Self::UndefinedElement { .. } => "undefined element", Self::UninitializedElement { .. } => "uninitialized element", @@ -243,7 +239,6 @@ impl Display for Trap { Self::InvalidConversionToInt => write!(f, "invalid conversion to integer"), Self::IntegerOverflow => write!(f, "integer overflow"), Self::CallStackOverflow => write!(f, "call stack exhausted"), - Self::BlockStackOverflow => write!(f, "block stack exhausted"), Self::ValueStackOverflow => write!(f, "value stack exhausted"), Self::UndefinedElement { index } => write!(f, "undefined element: index={index}"), Self::UninitializedElement { index } => { diff --git a/crates/tinywasm/src/func.rs b/crates/tinywasm/src/func.rs index 6cf0c8c..a741e0f 100644 --- a/crates/tinywasm/src/func.rs +++ b/crates/tinywasm/src/func.rs @@ -56,7 +56,7 @@ impl FuncHandle { }; // 6. Let f be the dummy frame - let callframe = CallFrame::new_with_params(wasm_func.locals, self.addr, func_inst.owner, params, 0); + let callframe = CallFrame::new_with_params(wasm_func.locals, self.addr, func_inst.owner, params); // 7. Push the frame f to the call stack // & 8. Push the values to the stack diff --git a/crates/tinywasm/src/interpreter/executor.rs b/crates/tinywasm/src/interpreter/executor.rs index 5dfad85..9d98cce 100644 --- a/crates/tinywasm/src/interpreter/executor.rs +++ b/crates/tinywasm/src/interpreter/executor.rs @@ -10,7 +10,6 @@ use interpreter::stack::CallFrame; use tinywasm_types::*; use super::num_helpers::*; -use super::stack::{BlockFrame, BlockType}; use super::values::*; use crate::instance::ModuleInstanceInner; use crate::interpreter::Value128; @@ -88,7 +87,7 @@ impl<'store> Executor<'store> { #[rustfmt::skip] match next { - Nop | BrLabel(_) | I32ReinterpretF32 | I64ReinterpretF64 | F32ReinterpretI32 | F64ReinterpretI64 => {} + Nop | I32ReinterpretF32 | I64ReinterpretF64 | F32ReinterpretI32 | F64ReinterpretI64 => {} Unreachable => return ControlFlow::Break(Some(Trap::Unreachable.into())), Drop32 => self.store.stack.values.drop::<Value32>(), Drop64 => self.store.stack.values.drop::<Value64>(), @@ -102,21 +101,70 @@ impl<'store> Executor<'store> { CallIndirect(ty, table) => return self.exec_call_indirect::<false>(*ty, *table), ReturnCall(v) => return self.exec_call_direct::<true>(*v), ReturnCallIndirect(ty, table) => return self.exec_call_indirect::<true>(*ty, *table), - If(end, el) => self.exec_if(*end, *el, (StackHeight::default(), StackHeight::default())), - IfWithType(ty, end, el) => self.exec_if(*end, *el, (StackHeight::default(), (*ty).into())), - IfWithFuncType(ty, end, el) => self.exec_if(*end, *el, self.resolve_functype(*ty)), - Else(end_offset) => self.exec_else(*end_offset), - Loop(end) => self.enter_block(*end, BlockType::Loop, (StackHeight::default(), StackHeight::default())), - LoopWithType(ty, end) => self.enter_block(*end, BlockType::Loop, (StackHeight::default(), (*ty).into())), - LoopWithFuncType(ty, end) => self.enter_block(*end, BlockType::Loop, self.resolve_functype(*ty)), - Block(end) => self.enter_block(*end, BlockType::Block, (StackHeight::default(), StackHeight::default())), - BlockWithType(ty, end) => self.enter_block(*end, BlockType::Block, (StackHeight::default(), (*ty).into())), - BlockWithFuncType(ty, end) => self.enter_block(*end, BlockType::Block, self.resolve_functype(*ty)), - Br(v) => return self.exec_br(*v), - BrIf(v) => return self.exec_br_if(*v), - BrTable(default, len) => return self.exec_brtable(*default, *len), + Jump(ip) => { + self.cf.instr_ptr = *ip as usize; + return ControlFlow::Continue(()); + } + JumpIfZero(ip) => { + let cond = self.store.stack.values.pop::<i32>(); + + if cond == 0 { + self.cf.instr_ptr = *ip as usize; + } else { + self.cf.incr_instr_ptr(); + } + return ControlFlow::Continue(()); + } + DropKeepSmall { base32, keep32, base64, keep64, base128, keep128, base_ref, keep_ref } => { + let b32 = self.cf.stack_base.s32 as usize + *base32 as usize; + let k32 = *keep32 as usize; + self.store.stack.values.stack_32.truncate_keep(b32, k32); + let b64 = self.cf.stack_base.s64 as usize + *base64 as usize; + let k64 = *keep64 as usize; + self.store.stack.values.stack_64.truncate_keep(b64, k64); + let b128 = self.cf.stack_base.s128 as usize + *base128 as usize; + let k128 = *keep128 as usize; + self.store.stack.values.stack_128.truncate_keep(b128, k128); + let bref = self.cf.stack_base.sref as usize + *base_ref as usize; + let kref = *keep_ref as usize; + self.store.stack.values.stack_ref.truncate_keep(bref, kref); + } + DropKeep32(base, keep) => { + let b = self.cf.stack_base.s32 as usize + *base as usize; + let k = *keep as usize; + self.store.stack.values.stack_32.truncate_keep(b, k); + } + DropKeep64(base, keep) => { + let b = self.cf.stack_base.s64 as usize + *base as usize; + let k = *keep as usize; + self.store.stack.values.stack_64.truncate_keep(b, k); + } + DropKeep128(base, keep) => { + let b = self.cf.stack_base.s128 as usize + *base as usize; + let k = *keep as usize; + self.store.stack.values.stack_128.truncate_keep(b, k); + } + DropKeepRef(base, keep) => { + let b = self.cf.stack_base.sref as usize + *base as usize; + let k = *keep as usize; + self.store.stack.values.stack_ref.truncate_keep(b, k); + } + BranchTable(default_ip, len) => { + let idx = self.store.stack.values.pop::<i32>(); + let start = self.cf.instr_ptr + 1; + + let target_ip = if idx >= 0 && (idx as u32) < *len { + match self.instructions.0.get(start + idx as usize) { + Some(Instruction::BranchTableTarget(ip)) => *ip, + _ => *default_ip, + } + } else { + *default_ip + }; + self.cf.instr_ptr = target_ip as usize; + return ControlFlow::Continue(()); + } Return => return self.exec_return(), - EndBlockFrame => self.exec_end_block(), LocalGet32(local_index) => self.store.stack.values.push(self.cf.locals.get::<Value32>(*local_index)).to_cf()?, LocalGet64(local_index) => self.store.stack.values.push(self.cf.locals.get::<Value64>(*local_index)).to_cf()?, LocalGet128(local_index) => self.store.stack.values.push(self.cf.locals.get::<Value128>(*local_index)).to_cf()?, @@ -588,10 +636,12 @@ impl<'store> Executor<'store> { if IS_RETURN_CALL { let locals = self.store.stack.values.pop_locals(wasm_func.params, wasm_func.locals); - self.cf.reuse_for(func_addr, locals, self.store.stack.blocks.len() as u32, owner); + let stack_base = self.store.stack.values.height(); + self.cf.reuse_for(func_addr, locals, owner, stack_base); } else { let locals = self.store.stack.values.pop_locals(wasm_func.params, wasm_func.locals); - let new_call_frame = CallFrame::new(func_addr, owner, locals, self.store.stack.blocks.len() as u32); + let stack_base = self.store.stack.values.height(); + let new_call_frame = CallFrame::new(func_addr, owner, locals, stack_base); self.cf.incr_instr_ptr(); // skip the call instruction self.store.stack.call_stack.push(core::mem::replace(&mut self.cf, new_call_frame)).to_cf()?; } @@ -661,84 +711,7 @@ impl<'store> Executor<'store> { } } - fn exec_if(&mut self, else_offset: u32, end_offset: u32, (params, results): (StackHeight, StackHeight)) { - // truthy value is on the top of the stack, so enter the then block - if self.store.stack.values.pop::<i32>() != 0 { - self.enter_block(end_offset, BlockType::If, (params, results)); - return; - } - - // falsy value is on the top of the stack - if else_offset == 0 { - self.cf.jump(end_offset); - return; - } - - self.cf.jump(else_offset); - self.enter_block(end_offset - else_offset, BlockType::Else, (params, results)); - } - fn exec_else(&mut self, end_offset: u32) { - self.exec_end_block(); - self.cf.jump(end_offset); - } - fn resolve_functype(&self, idx: u32) -> (StackHeight, StackHeight) { - let ty = self.module.func_ty(idx); - ((&*ty.params).into(), (&*ty.results).into()) - } - fn enter_block(&mut self, end_instr_offset: u32, ty: BlockType, (params, results): (StackHeight, StackHeight)) { - self.store.stack.blocks.push(BlockFrame { - instr_ptr: self.cf.instr_ptr as u32, - end_instr_offset, - stack_ptr: self.store.stack.values.height(), - results, - params, - ty, - }) - } - fn exec_br(&mut self, to: u32) -> ControlFlow<Option<Error>> { - if self.cf.break_to(to, &mut self.store.stack.values, &mut self.store.stack.blocks).is_none() { - return self.exec_return(); - } - - self.cf.incr_instr_ptr(); - ControlFlow::Continue(()) - } - fn exec_br_if(&mut self, to: u32) -> ControlFlow<Option<Error>> { - if self.store.stack.values.pop::<i32>() != 0 - && self.cf.break_to(to, &mut self.store.stack.values, &mut self.store.stack.blocks).is_none() - { - return self.exec_return(); - } - self.cf.incr_instr_ptr(); - ControlFlow::Continue(()) - } - fn exec_brtable(&mut self, default: u32, len: u32) -> ControlFlow<Option<Error>> { - let start = self.cf.instr_ptr + 1; - let end = start + len as usize; - if end > self.func.instructions.len() { - return ControlFlow::Break(Some(Error::Other(format!( - "br_table out of bounds: {} >= {}", - end, - self.func.instructions.len() - )))); - } - - let idx = self.store.stack.values.pop::<i32>(); - let to = match self.func.instructions[start..end].get(idx as usize) { - None => default, - Some(Instruction::BrLabel(to)) => *to, - _ => return ControlFlow::Break(Some(Error::Other("br_table out of bounds".to_string()))), - }; - - if self.cf.break_to(to, &mut self.store.stack.values, &mut self.store.stack.blocks).is_none() { - return self.exec_return(); - } - - self.cf.incr_instr_ptr(); - ControlFlow::Continue(()) - } fn exec_return(&mut self) -> ControlFlow<Option<Error>> { - let old = self.cf.block_ptr; let Some(cf) = self.store.stack.call_stack.pop() else { return ControlFlow::Break(None) }; if cf.func_addr != self.cf.func_addr { @@ -750,18 +723,9 @@ impl<'store> Executor<'store> { } } - if old > cf.block_ptr { - self.store.stack.blocks.truncate(old); - } - self.cf = cf; ControlFlow::Continue(()) } - fn exec_end_block(&mut self) { - let block = self.store.stack.blocks.pop(); - self.store.stack.values.truncate_keep(block.stack_ptr, block.results); - } - fn exec_global_get(&mut self, global_index: u32) -> Result<()> { self.store.stack.values.push_dyn(self.store.state.get_global_val(self.module.resolve_global_addr(global_index))) } diff --git a/crates/tinywasm/src/interpreter/stack/block_stack.rs b/crates/tinywasm/src/interpreter/stack/block_stack.rs deleted file mode 100644 index f653460..0000000 --- a/crates/tinywasm/src/interpreter/stack/block_stack.rs +++ /dev/null @@ -1,69 +0,0 @@ -use crate::engine::Config; -use alloc::vec::Vec; - -use crate::interpreter::values::{StackHeight, StackLocation}; - -#[derive(Debug)] -pub(crate) struct BlockStack(Vec<BlockFrame>); - -impl BlockStack { - pub(crate) fn new(config: &Config) -> Self { - Self(Vec::with_capacity(config.block_stack_initial_size)) - } - - pub(crate) fn clear(&mut self) { - self.0.clear(); - } - - pub(crate) fn len(&self) -> usize { - self.0.len() - } - - pub(crate) fn push(&mut self, block: BlockFrame) { - self.0.push(block); - } - - /// get the label at the given index, where 0 is the top of the stack - pub(crate) fn get_relative_to(&self, index: u32, offset: u32) -> Option<&BlockFrame> { - let len = (self.0.len() as u32).checked_sub(offset)?; - - // the vast majority of wasm functions don't use break to return, but it is allowed in the spec - if index >= len { - return None; - } - - Some(&self.0[self.0.len() - index as usize - 1]) - } - - pub(crate) fn pop(&mut self) -> BlockFrame { - match self.0.pop() { - Some(frame) => frame, - None => unreachable!("Block stack underflow, this is a bug"), - } - } - - /// keep the top `len` blocks and discard the rest - pub(crate) fn truncate(&mut self, len: u32) { - self.0.truncate(len as usize); - } -} - -#[derive(Debug)] -pub(crate) struct BlockFrame { - pub(crate) instr_ptr: u32, // position of the instruction pointer when the block was entered - pub(crate) end_instr_offset: u32, // position of the end instruction of the block - - pub(crate) stack_ptr: StackLocation, // stack pointer when the block was entered - pub(crate) results: StackHeight, - pub(crate) params: StackHeight, - - pub(crate) ty: BlockType, -} - -#[derive(Debug)] -pub(crate) enum BlockType { - Loop, - If, - Else, - Block, -} diff --git a/crates/tinywasm/src/interpreter/stack/call_stack.rs b/crates/tinywasm/src/interpreter/stack/call_stack.rs index 9c588b3..4750b03 100644 --- a/crates/tinywasm/src/interpreter/stack/call_stack.rs +++ b/crates/tinywasm/src/interpreter/stack/call_stack.rs @@ -1,4 +1,3 @@ -use super::BlockType; use crate::interpreter::{Value128, values::*}; use crate::{Result, Trap, unlikely}; @@ -37,10 +36,18 @@ impl CallStack { #[derive(Debug)] pub(crate) struct CallFrame { pub(crate) instr_ptr: usize, - pub(crate) block_ptr: u32, pub(crate) locals: Locals, pub(crate) module_addr: ModuleInstanceAddr, pub(crate) func_addr: FuncAddr, + pub(crate) stack_base: StackBase, +} + +#[derive(Debug, Clone, Copy, Default)] +pub(crate) struct StackBase { + pub(crate) s32: u32, + pub(crate) s64: u32, + pub(crate) s128: u32, + pub(crate) sref: u32, } #[derive(Debug)] @@ -62,8 +69,13 @@ impl Locals { } impl CallFrame { - pub(crate) fn new(func_addr: FuncAddr, module_addr: ModuleInstanceAddr, locals: Locals, block_ptr: u32) -> Self { - Self { instr_ptr: 0, func_addr, module_addr, block_ptr, locals } + pub(crate) fn new( + func_addr: FuncAddr, + module_addr: ModuleInstanceAddr, + locals: Locals, + stack_base: StackBase, + ) -> Self { + Self { instr_ptr: 0, func_addr, module_addr, locals, stack_base } } pub(crate) fn new_with_params( @@ -71,7 +83,6 @@ impl CallFrame { func_addr: FuncAddr, module_addr: ModuleInstanceAddr, params: &[WasmValue], - block_ptr: u32, ) -> Self { let locals = { let mut locals_32 = Vec::with_capacity(local_count.c32 as usize); @@ -101,72 +112,24 @@ impl CallFrame { } }; - Self::new(func_addr, module_addr, locals, block_ptr) + Self::new(func_addr, module_addr, locals, StackBase::default()) } pub(crate) fn incr_instr_ptr(&mut self) { self.instr_ptr += 1; } - pub(crate) fn jump(&mut self, offset: u32) { - self.instr_ptr += offset as usize; - } - pub(crate) fn reuse_for( &mut self, func_addr: FuncAddr, locals: Locals, - block_depth: u32, module_addr: ModuleInstanceAddr, + stack_base: StackBase, ) { self.func_addr = func_addr; self.module_addr = module_addr; self.locals = locals; - self.block_ptr = block_depth; - self.instr_ptr = 0; // Reset to function entry - } - - /// Break to a block at the given index (relative to the current frame) - /// Returns `None` if there is no block at the given index (e.g. if we need to return, this is handled by the caller) - pub(crate) fn break_to( - &mut self, - break_to_relative: u32, - values: &mut super::ValueStack, - blocks: &mut super::BlockStack, - ) -> Option<()> { - let break_to = blocks.get_relative_to(break_to_relative, self.block_ptr)?; - - // instr_ptr points to the label instruction, but the next step - // will increment it by 1 since we're changing the "current" instr_ptr - match break_to.ty { - BlockType::Loop => { - // this is a loop, so we want to jump back to the start of the loop - self.instr_ptr = break_to.instr_ptr as usize; - - // We also want to push the params to the stack - values.truncate_keep(break_to.stack_ptr, break_to.params); - - // check if we're breaking to the loop - if break_to_relative != 0 { - // we also want to trim the label stack to the loop (but not including the loop) - blocks.truncate(blocks.len() as u32 - break_to_relative); - return Some(()); - } - } - - BlockType::Block | BlockType::If | BlockType::Else => { - // this is a block, so we want to jump to the next instruction after the block ends - // We also want to push the block's results to the stack - values.truncate_keep(break_to.stack_ptr, break_to.results); - - // (the inst_ptr will be incremented by 1 before the next instruction is executed) - self.instr_ptr = (break_to.instr_ptr + break_to.end_instr_offset) as usize; - - // we also want to trim the label stack, including the block - blocks.truncate(blocks.len() as u32 - (break_to_relative + 1)); - } - } - - Some(()) + self.stack_base = stack_base; + self.instr_ptr = 0; } } diff --git a/crates/tinywasm/src/interpreter/stack/mod.rs b/crates/tinywasm/src/interpreter/stack/mod.rs index 68b9164..5912de1 100644 --- a/crates/tinywasm/src/interpreter/stack/mod.rs +++ b/crates/tinywasm/src/interpreter/stack/mod.rs @@ -1,9 +1,7 @@ -mod block_stack; mod call_stack; mod value_stack; -pub(crate) use block_stack::{BlockFrame, BlockStack, BlockType}; -pub(crate) use call_stack::{CallFrame, CallStack, Locals}; +pub(crate) use call_stack::{CallFrame, CallStack, Locals, StackBase}; pub(crate) use value_stack::ValueStack; use crate::engine::Config; @@ -12,18 +10,16 @@ use crate::engine::Config; #[derive(Debug)] pub(crate) struct Stack { pub(crate) values: ValueStack, - pub(crate) blocks: BlockStack, pub(crate) call_stack: CallStack, } impl Stack { pub(crate) fn new(config: &Config) -> Self { - Self { values: ValueStack::new(config), blocks: BlockStack::new(config), call_stack: CallStack::new(config) } + Self { values: ValueStack::new(config), call_stack: CallStack::new(config) } } pub(crate) fn clear(&mut self) { self.values.clear(); - self.blocks.clear(); self.call_stack.clear(); } } diff --git a/crates/tinywasm/src/interpreter/stack/value_stack.rs b/crates/tinywasm/src/interpreter/stack/value_stack.rs index b579a04..9ce73d9 100644 --- a/crates/tinywasm/src/interpreter/stack/value_stack.rs +++ b/crates/tinywasm/src/interpreter/stack/value_stack.rs @@ -4,7 +4,7 @@ use tinywasm_types::{ExternRef, FuncRef, ValType, ValueCounts, ValueCountsSmall, use crate::{Result, Trap, engine::Config, interpreter::*}; -use super::Locals; +use super::{Locals, StackBase}; #[derive(Debug)] pub(crate) struct ValueStack { @@ -74,6 +74,7 @@ impl<T: Copy + Default> Stack<T> { } let keep_tail = end_keep.min(self.len - n); + if keep_tail == 0 { self.len = n; return; @@ -113,19 +114,19 @@ impl ValueStack { self.stack_ref.clear(); } - pub(crate) fn height(&self) -> StackLocation { - StackLocation { - s32: self.stack_32.len() as u32, - s64: self.stack_64.len() as u32, - s128: self.stack_128.len() as u32, - sref: self.stack_ref.len() as u32, - } - } - pub(crate) fn len(&self) -> usize { self.stack_32.len() + self.stack_64.len() + self.stack_128.len() + self.stack_ref.len() } + pub(crate) fn height(&self) -> StackBase { + StackBase { + s32: u32::try_from(self.stack_32.len()).expect("stack32 height overflow"), + s64: u32::try_from(self.stack_64.len()).expect("stack64 height overflow"), + s128: u32::try_from(self.stack_128.len()).expect("stack128 height overflow"), + sref: u32::try_from(self.stack_ref.len()).expect("stack_ref height overflow"), + } + } + pub(crate) fn peek<T: InternalValue>(&self) -> T { T::stack_peek(self) } @@ -209,13 +210,6 @@ impl ValueStack { } } - pub(crate) fn truncate_keep(&mut self, to: StackLocation, keep: StackHeight) { - self.stack_32.truncate_keep(to.s32 as usize, usize::from(keep.s32)); - self.stack_64.truncate_keep(to.s64 as usize, usize::from(keep.s64)); - self.stack_128.truncate_keep(to.s128 as usize, usize::from(keep.s128)); - self.stack_ref.truncate_keep(to.sref as usize, usize::from(keep.sref)); - } - pub(crate) fn push_dyn(&mut self, value: TinyWasmValue) -> Result<()> { match value { TinyWasmValue::Value32(v) => self.stack_32.push(v)?, diff --git a/crates/tinywasm/src/interpreter/values.rs b/crates/tinywasm/src/interpreter/values.rs index 3535725..41db383 100644 --- a/crates/tinywasm/src/interpreter/values.rs +++ b/crates/tinywasm/src/interpreter/values.rs @@ -20,51 +20,6 @@ pub enum TinyWasmValue { ValueRef(ValueRef), } -#[derive(Debug, Clone, Copy)] -pub(crate) struct StackLocation { - pub(crate) s32: u32, - pub(crate) s64: u32, - pub(crate) s128: u32, - pub(crate) sref: u32, -} - -#[derive(Debug, Clone, Copy, Default)] -pub(crate) struct StackHeight { - pub(crate) s32: u16, - pub(crate) s64: u16, - pub(crate) s128: u16, - pub(crate) sref: u16, -} - -impl From<ValType> for StackHeight { - fn from(value: ValType) -> Self { - match value { - ValType::I32 | ValType::F32 => Self { s32: 1, ..Default::default() }, - ValType::I64 | ValType::F64 => Self { s64: 1, ..Default::default() }, - ValType::V128 => Self { s128: 1, ..Default::default() }, - ValType::RefExtern | ValType::RefFunc => Self { sref: 1, ..Default::default() }, - } - } -} - -impl From<&[ValType]> for StackHeight { - fn from(value: &[ValType]) -> Self { - let mut s32 = 0; - let mut s64 = 0; - let mut s128 = 0; - let mut sref = 0; - for val_type in value { - match val_type { - ValType::I32 | ValType::F32 => s32 += 1, - ValType::I64 | ValType::F64 => s64 += 1, - ValType::V128 => s128 += 1, - ValType::RefExtern | ValType::RefFunc => sref += 1, - } - } - Self { s32, s64, s128, sref } - } -} - impl TinyWasmValue { /// Asserts that the value is a 32-bit value and returns it (panics if the value is the wrong size) pub fn unwrap_32(&self) -> Value32 { diff --git a/crates/tinywasm/src/store/memory.rs b/crates/tinywasm/src/store/memory.rs index c1df263..46226b9 100644 --- a/crates/tinywasm/src/store/memory.rs +++ b/crates/tinywasm/src/store/memory.rs @@ -125,25 +125,29 @@ impl MemoryInstance { } pub(crate) fn grow(&mut self, pages_delta: i64) -> Option<i64> { + if pages_delta < 0 { + log::debug!("memory.grow failed: negative delta {}", pages_delta); + return None; + } + let current_pages = self.page_count; - let new_pages = current_pages as i64 + pages_delta; + let pages_delta = usize::try_from(pages_delta).ok()?; + let new_pages = current_pages.checked_add(pages_delta)?; - if new_pages < 0 || new_pages as usize > self.max_pages() { + if new_pages > self.max_pages() { log::debug!("memory.grow failed: new_pages={}, max_pages={}", new_pages, self.max_pages()); - log::debug!("{} {}", self.kind.page_count_max(), self.kind.page_size()); return None; } - let new_size = (new_pages as u64 * self.kind.page_size()) as usize; - if new_size as u64 > self.kind.max_size() { + let new_size = (new_pages as u64).checked_mul(self.kind.page_size())?; + if new_size > self.kind.max_size() { + log::debug!("memory.grow failed: new_size={}, max_size={}", new_size, self.kind.max_size()); return None; } - // Zero initialize the new pages - self.data.reserve_exact(new_size); - self.data.resize_with(new_size, Default::default); - self.page_count = new_pages as usize; - Some(current_pages as i64) + self.data.resize(usize::try_from(new_size).ok()?, 0); + self.page_count = new_pages; + i64::try_from(current_pages).ok() } } @@ -250,6 +254,15 @@ mod memory_instance_tests { } #[test] + fn test_memory_grow_negative_delta() { + let mut memory = create_test_memory(); + let original_pages = memory.page_count; + + assert_eq!(memory.grow(-1), None); + assert_eq!(memory.page_count, original_pages); + } + + #[test] fn test_memory_custom_page_size_out_of_bounds() { let kind = MemoryType::new(MemoryArch::I32, 1, Some(2), Some(1)); let owner = ModuleInstanceAddr::default(); diff --git a/crates/tinywasm/tests/test-wasm-custom.rs b/crates/tinywasm/tests/test-wasm-custom.rs new file mode 100644 index 0000000..ae08142 --- /dev/null +++ b/crates/tinywasm/tests/test-wasm-custom.rs @@ -0,0 +1,19 @@ +mod testsuite; +use eyre::Result; +use testsuite::TestSuite; + +fn main() -> Result<()> { + TestSuite::set_log_level(log::LevelFilter::Off); + + let custom_dir = std::path::Path::new("./tests/wasm-custom"); + let mut files: Vec<std::path::PathBuf> = std::fs::read_dir(custom_dir)? + .filter_map(|e| e.ok()) + .map(|e| e.path()) + .filter(|p| p.extension().is_some_and(|ext| ext == "wast")) + .collect(); + files.sort(); + + let mut test_suite = TestSuite::new(); + test_suite.run_paths(&files)?; + test_suite.report_status() +} diff --git a/crates/tinywasm/tests/wasm-custom/debug-if-then.wast b/crates/tinywasm/tests/wasm-custom/debug-if-then.wast new file mode 100644 index 0000000..6faf339 --- /dev/null +++ b/crates/tinywasm/tests/wasm-custom/debug-if-then.wast @@ -0,0 +1,12 @@ +(module + (func (export "as-if-then") (param i32 i32) (result i32) + (block (result i32) + (if (result i32) (local.get 0) + (then (br 1 (i32.const 3))) + (else (local.get 1)) + ) + ) + ) +) +(assert_return (invoke "as-if-then" (i32.const 0) (i32.const 6)) (i32.const 6)) +(assert_return (invoke "as-if-then" (i32.const 1) (i32.const 6)) (i32.const 3)) diff --git a/crates/tinywasm/tests/wasm-custom/dropkeep-small-zero-zero.wast b/crates/tinywasm/tests/wasm-custom/dropkeep-small-zero-zero.wast new file mode 100644 index 0000000..01a4f6b --- /dev/null +++ b/crates/tinywasm/tests/wasm-custom/dropkeep-small-zero-zero.wast @@ -0,0 +1,38 @@ +(module + (func $leak (result i32) + (block + (i64.const 7) + (i32.const 1) + (br_if 0) + (unreachable) + ) + (i32.const 0) + ) + + (func (export "run") (param i32) (result i32) + (local i32) + (local.get 0) + (local.set 1) + + (block + (loop + (local.get 1) + (i32.eqz) + (br_if 1) + + (call $leak) + (drop) + + (local.get 1) + (i32.const 1) + (i32.sub) + (local.set 1) + (br 0) + ) + ) + + (i32.const 0) + ) +) + +(assert_return (invoke "run" (i32.const 40000)) (i32.const 0)) diff --git a/crates/types/src/instructions.rs b/crates/types/src/instructions.rs index ee99601..5c1627a 100644 --- a/crates/types/src/instructions.rs +++ b/crates/types/src/instructions.rs @@ -1,4 +1,4 @@ -use super::{FuncAddr, GlobalAddr, LabelAddr, LocalAddr, TableAddr, TypeAddr, ValType}; +use super::{FuncAddr, GlobalAddr, LocalAddr, TableAddr, TypeAddr, ValType}; use crate::{ConstIdx, DataAddr, ElemAddr, ExternAddr, MemAddr}; /// Represents a memory immediate in a WebAssembly memory instruction. @@ -23,11 +23,6 @@ impl MemoryArg { } } -type BrTableDefault = u32; -type BrTableLen = u32; -type EndOffset = u32; -type ElseOffset = u32; - #[derive(Debug, Clone, Copy, PartialEq)] #[cfg_attr(feature = "archive", derive(serde::Serialize, serde::Deserialize))] pub enum ConstInstruction { @@ -46,43 +41,26 @@ pub enum ConstInstruction { /// These are our own internal bytecode instructions so they may not match the spec exactly. /// Wasm Bytecode can map to multiple of these instructions. /// -/// # Differences to the spec -/// * `br_table` stores the jump labels in the following `br_label` instructions to keep this enum small. -/// * Lables/Blocks: we store the label end offset in the instruction itself and use `EndBlockFrame` to mark the end of a block. -/// This makes it easier to implement the label stack iteratively. -/// /// See <https://webassembly.github.io/spec/core/binary/instructions.html> #[derive(Debug, Clone, Copy, PartialEq)] #[cfg_attr(feature = "archive", derive(serde::Serialize, serde::Deserialize))] -// should be kept as small as possible (16 bytes max) #[rustfmt::skip] pub enum Instruction { LocalCopy32(LocalAddr, LocalAddr), LocalCopy64(LocalAddr, LocalAddr), LocalCopy128(LocalAddr, LocalAddr), LocalCopyRef(LocalAddr, LocalAddr), - // LocalsStore32(LocalAddr, LocalAddr, u32, MemAddr), LocalsStore64(LocalAddr, LocalAddr, u32, MemAddr), LocalsStore128(LocalAddr, LocalAddr, u32, MemAddr), LocalsStoreRef(LocalAddr, LocalAddr, u32, MemAddr), - // > Control Instructions + // > Control Instructions (jump-oriented, lowered from structured control during parsing) // See <https://webassembly.github.io/spec/core/binary/instructions.html#control-instructions> Unreachable, Nop, - - Block(EndOffset), - BlockWithType(ValType, EndOffset), - BlockWithFuncType(TypeAddr, EndOffset), - - Loop(EndOffset), - LoopWithType(ValType, EndOffset), - LoopWithFuncType(TypeAddr, EndOffset), - - If(ElseOffset, EndOffset), - IfWithType(ValType, ElseOffset, EndOffset), - IfWithFuncType(TypeAddr, ElseOffset, EndOffset), - - Else(EndOffset), - EndBlockFrame, - Br(LabelAddr), - BrIf(LabelAddr), - BrTable(BrTableDefault, BrTableLen), // has to be followed by multiple BrLabel instructions - BrLabel(LabelAddr), + Jump(u32), + JumpIfZero(u32), + DropKeepSmall { base32: u8, keep32: u8, base64: u8, keep64: u8, base128: u8, keep128: u8, base_ref: u8, keep_ref: u8 }, + DropKeep32(u16, u16), + DropKeep64(u16, u16), + DropKeep128(u16, u16), + DropKeepRef(u16, u16), + BranchTable(u32, u32), // (default_landing_pad_ip, target_count) — followed by BranchTableTarget entries + BranchTableTarget(u32), // (landing_pad_ip) Return, Call(FuncAddr), CallIndirect(TypeAddr, TableAddr), diff --git a/crates/types/src/lib.rs b/crates/types/src/lib.rs index 969620d..ba2cb56 100644 --- a/crates/types/src/lib.rs +++ b/crates/types/src/lib.rs @@ -155,7 +155,6 @@ pub type ConstIdx = Addr; // additional internal addresses pub type TypeAddr = Addr; pub type LocalAddr = u16; // there can't be more than 50.000 locals in a function -pub type LabelAddr = Addr; pub type ModuleInstanceAddr = Addr; /// A WebAssembly External Value. @@ -288,12 +287,14 @@ impl<T: Debug> Debug for ArcSlice<T> { } } +#[cfg(feature = "archive")] impl<T: serde::Serialize + Debug> serde::Serialize for ArcSlice<T> { fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> { self.0.as_ref().serialize(serializer) } } +#[cfg(feature = "archive")] impl<'de, T: serde::Deserialize<'de> + Debug> serde::Deserialize<'de> for ArcSlice<T> { fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> { let vec: alloc::vec::Vec<T> = alloc::vec::Vec::deserialize(deserializer)?; |