From 96b047f5d209e16f3ef6f95838ff230ce2a79af4 Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Mon, 18 Sep 2023 19:06:59 +0300 Subject: [PATCH 1/7] MIR: Return Result from interpret --- contrib/mir/src/interpreter.rs | 118 +++++++++++++++++++++------------ contrib/mir/src/main.rs | 6 +- 2 files changed, 79 insertions(+), 45 deletions(-) diff --git a/contrib/mir/src/interpreter.rs b/contrib/mir/src/interpreter.rs index 3d1f206966f3..107c9ee5c2fa 100644 --- a/contrib/mir/src/interpreter.rs +++ b/contrib/mir/src/interpreter.rs @@ -8,10 +8,13 @@ use crate::ast::*; use crate::stack::*; -pub fn interpret(ast: &AST, stack: &mut IStack) { +pub enum InterpretError {} + +pub fn interpret(ast: &AST, stack: &mut IStack) -> Result<(), InterpretError> { for i in ast { - interpret_one(&i, stack); + interpret_one(&i, stack)?; } + Ok(()) } fn unreachable_state() -> ! { @@ -20,7 +23,7 @@ fn unreachable_state() -> ! { panic!("Unreachable state reached during interpreting, possibly broken typechecking!") } -fn interpret_one(i: &Instruction, stack: &mut IStack) { +fn interpret_one(i: &Instruction, stack: &mut IStack) -> Result<(), InterpretError> { use Instruction::*; use Value::*; @@ -37,7 +40,7 @@ fn interpret_one(i: &Instruction, stack: &mut IStack) { Dip(opt_height, nested) => { let protected_height: usize = opt_height.unwrap_or(1); let mut live = stack.split_off(protected_height); - interpret(nested, &mut live); + interpret(nested, &mut live)?; stack.append(&mut live); } Drop(opt_height) => { @@ -57,9 +60,9 @@ fn interpret_one(i: &Instruction, stack: &mut IStack) { If(nested_t, nested_f) => { if let Some(BooleanValue(b)) = stack.pop_front() { if b { - interpret(nested_t, stack); + interpret(nested_t, stack)?; } else { - interpret(nested_f, stack); + interpret(nested_f, stack)?; } } else { unreachable_state(); @@ -74,7 +77,7 @@ fn interpret_one(i: &Instruction, stack: &mut IStack) { Loop(nested) => loop { if let Some(BooleanValue(b)) = stack.pop_front() { if b { - interpret(nested, stack); + interpret(nested, stack)?; } else { break; } @@ -89,6 +92,7 @@ fn interpret_one(i: &Instruction, stack: &mut IStack) { stack.swap(0, 1); } } + Ok(()) } #[cfg(test)] @@ -103,127 +107,157 @@ mod interpreter_tests { fn test_add() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(30)]); - interpret_one(&Add, &mut stack); - assert!(stack == expected_stack); + assert!(interpret_one(&Add, &mut stack).is_ok()); + assert_eq!(stack, expected_stack); } #[test] fn test_dip() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(5), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(10), NumberValue(25)]); - interpret_one(&Dip(None, parse("{ADD}").unwrap()), &mut stack); - assert!(stack == expected_stack); + assert!(interpret_one(&Dip(None, parse("{ADD}").unwrap()), &mut stack).is_ok()); + assert_eq!(stack, expected_stack); } #[test] fn test_dip2() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(5), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(10), NumberValue(5)]); - interpret_one(&Dip(Some(2), parse("{DROP}").unwrap()), &mut stack); - assert!(stack == expected_stack); + assert!(interpret_one(&Dip(Some(2), parse("{DROP}").unwrap()), &mut stack,).is_ok()); + assert_eq!(stack, expected_stack); } #[test] fn test_drop() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(5), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(5), NumberValue(20)]); - interpret_one(&Drop(None), &mut stack); - assert!(stack == expected_stack); + assert!(interpret_one(&Drop(None), &mut stack).is_ok()); + assert_eq!(stack, expected_stack); } - #[test] + #[test] fn test_drop2() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(5), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(20)]); - interpret_one(&Drop(Some(2)), &mut stack); - assert!(stack == expected_stack); + assert!(interpret_one(&Drop(Some(2)), &mut stack).is_ok()); + assert_eq!(stack, expected_stack); } #[test] fn test_dup() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(5), NumberValue(20)]); - let expected_stack = VecDeque::from([NumberValue(10), NumberValue(10), NumberValue(5), NumberValue(20)]); - interpret_one(&Dup(None), &mut stack); - assert!(stack == expected_stack); + let expected_stack = VecDeque::from([ + NumberValue(10), + NumberValue(10), + NumberValue(5), + NumberValue(20), + ]); + assert!(interpret_one(&Dup(None), &mut stack).is_ok()); + assert_eq!(stack, expected_stack); } #[test] fn test_dup2() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(5), NumberValue(20)]); - let expected_stack = VecDeque::from([NumberValue(5), NumberValue(10), NumberValue(5), NumberValue(20)]); - interpret_one(&Dup(Some(2)), &mut stack); - assert!(stack == expected_stack); + let expected_stack = VecDeque::from([ + NumberValue(5), + NumberValue(10), + NumberValue(5), + NumberValue(20), + ]); + assert!(interpret_one(&Dup(Some(2)), &mut stack).is_ok()); + assert_eq!(stack, expected_stack); } #[test] fn test_gt() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(20)]); let expected_stack = VecDeque::from([BooleanValue(true), NumberValue(20)]); - interpret_one(&Gt, &mut stack); - assert!(stack == expected_stack); + assert!(interpret_one(&Gt, &mut stack).is_ok()); + assert_eq!(stack, expected_stack); } #[test] fn test_if_t() { let mut stack = VecDeque::from([BooleanValue(true), NumberValue(5), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(20)]); - interpret_one(&If(parse("{DROP}").unwrap(), parse("{ADD}").unwrap()), &mut stack); - assert!(stack == expected_stack); + assert!(interpret_one( + &If(parse("{DROP}").unwrap(), parse("{ADD}").unwrap()), + &mut stack, + ) + .is_ok()); + assert_eq!(stack, expected_stack); } #[test] fn test_if_f() { let mut stack = VecDeque::from([BooleanValue(false), NumberValue(5), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(25)]); - interpret_one(&If(parse("{DROP}").unwrap(), parse("{ADD}").unwrap()), &mut stack); - assert!(stack == expected_stack); + assert!(interpret_one( + &If(parse("{DROP}").unwrap(), parse("{ADD}").unwrap()), + &mut stack, + ) + .is_ok()); + assert_eq!(stack, expected_stack); } #[test] fn test_int() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(10), NumberValue(20)]); - interpret_one(&Int, &mut stack); - assert!(stack == expected_stack); + assert!(interpret_one(&Int, &mut stack).is_ok()); + assert_eq!(stack, expected_stack); } #[test] fn test_push() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(0), NumberValue(10), NumberValue(20)]); - interpret_one(&Push(Type::Nat, NumberValue(0)), &mut stack); - assert!(stack == expected_stack); + assert!(interpret_one(&Push(Type::Nat, NumberValue(0)), &mut stack).is_ok()); + assert_eq!(stack, expected_stack); } #[test] fn test_loop_0() { let mut stack = VecDeque::from([BooleanValue(false), NumberValue(10), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(10), NumberValue(20)]); - interpret_one(&Loop(parse("{PUSH nat 1; ADD; PUSH bool False}").unwrap()), &mut stack); - assert!(stack == expected_stack); + assert!(interpret_one( + &Loop(parse("{PUSH nat 1; ADD; PUSH bool False}").unwrap()), + &mut stack, + ) + .is_ok()); + assert_eq!(stack, expected_stack); } #[test] fn test_loop_1() { let mut stack = VecDeque::from([BooleanValue(true), NumberValue(10), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(11), NumberValue(20)]); - interpret_one(&Loop(parse("{PUSH nat 1; ADD; PUSH bool False}").unwrap()), &mut stack); - assert!(stack == expected_stack); + assert!(interpret_one( + &Loop(parse("{PUSH nat 1; ADD; PUSH bool False}").unwrap()), + &mut stack, + ) + .is_ok()); + assert_eq!(stack, expected_stack); } #[test] fn test_loop_many() { let mut stack = VecDeque::from([BooleanValue(true), NumberValue(10), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(0), NumberValue(20)]); - interpret_one(&Loop(parse("{PUSH int -1; ADD; DUP; GT}").unwrap()), &mut stack); - assert!(stack == expected_stack); + assert!(interpret_one( + &Loop(parse("{PUSH int -1; ADD; DUP; GT}").unwrap()), + &mut stack, + ) + .is_ok()); + assert_eq!(stack, expected_stack); } #[test] fn test_swap() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(20), NumberValue(10)]); - interpret_one(&Swap, &mut stack); - assert!(stack == expected_stack); + assert!(interpret_one(&Swap, &mut stack).is_ok()); + assert_eq!(stack, expected_stack); } } diff --git a/contrib/mir/src/main.rs b/contrib/mir/src/main.rs index 59f929fb7281..11783a5419b8 100644 --- a/contrib/mir/src/main.rs +++ b/contrib/mir/src/main.rs @@ -7,11 +7,11 @@ mod ast; mod gas; +mod interpreter; mod parser; mod stack; mod syntax; mod typechecker; -mod interpreter; fn main() {} @@ -21,15 +21,15 @@ mod tests { use crate::ast::*; use crate::gas::Gas; + use crate::interpreter; use crate::parser; use crate::typechecker; - use crate::interpreter; #[test] fn interpret_test_expect_success() { let ast = parser::parse(&FIBONACCI_SRC).unwrap(); let mut istack = VecDeque::from([Value::NumberValue(10)]); - interpreter::interpret(&ast, &mut istack); + assert!(interpreter::interpret(&ast, &mut istack).is_ok()); assert!(istack.len() == 1 && istack[0] == Value::NumberValue(55)); } -- GitLab From ef95ca26398c19892cdc95663b9d7b6e0adff889 Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Mon, 18 Sep 2023 19:10:30 +0300 Subject: [PATCH 2/7] MIR: pass gas counter to the interpreter --- contrib/mir/src/interpreter.rs | 63 ++++++++++++++++++++++++---------- contrib/mir/src/main.rs | 3 +- 2 files changed, 47 insertions(+), 19 deletions(-) diff --git a/contrib/mir/src/interpreter.rs b/contrib/mir/src/interpreter.rs index 107c9ee5c2fa..6ed9eaf5a9f9 100644 --- a/contrib/mir/src/interpreter.rs +++ b/contrib/mir/src/interpreter.rs @@ -6,13 +6,14 @@ /******************************************************************************/ use crate::ast::*; +use crate::gas::Gas; use crate::stack::*; pub enum InterpretError {} -pub fn interpret(ast: &AST, stack: &mut IStack) -> Result<(), InterpretError> { +pub fn interpret(ast: &AST, gas: &mut Gas, stack: &mut IStack) -> Result<(), InterpretError> { for i in ast { - interpret_one(&i, stack)?; + interpret_one(&i, gas, stack)?; } Ok(()) } @@ -23,7 +24,7 @@ fn unreachable_state() -> ! { panic!("Unreachable state reached during interpreting, possibly broken typechecking!") } -fn interpret_one(i: &Instruction, stack: &mut IStack) -> Result<(), InterpretError> { +fn interpret_one(i: &Instruction, gas: &mut Gas, stack: &mut IStack) -> Result<(), InterpretError> { use Instruction::*; use Value::*; @@ -40,7 +41,7 @@ fn interpret_one(i: &Instruction, stack: &mut IStack) -> Result<(), InterpretErr Dip(opt_height, nested) => { let protected_height: usize = opt_height.unwrap_or(1); let mut live = stack.split_off(protected_height); - interpret(nested, &mut live)?; + interpret(nested, gas, &mut live)?; stack.append(&mut live); } Drop(opt_height) => { @@ -60,9 +61,9 @@ fn interpret_one(i: &Instruction, stack: &mut IStack) -> Result<(), InterpretErr If(nested_t, nested_f) => { if let Some(BooleanValue(b)) = stack.pop_front() { if b { - interpret(nested_t, stack)?; + interpret(nested_t, gas, stack)?; } else { - interpret(nested_f, stack)?; + interpret(nested_f, gas, stack)?; } } else { unreachable_state(); @@ -77,7 +78,7 @@ fn interpret_one(i: &Instruction, stack: &mut IStack) -> Result<(), InterpretErr Loop(nested) => loop { if let Some(BooleanValue(b)) = stack.pop_front() { if b { - interpret(nested, stack)?; + interpret(nested, gas, stack)?; } else { break; } @@ -107,7 +108,8 @@ mod interpreter_tests { fn test_add() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(30)]); - assert!(interpret_one(&Add, &mut stack).is_ok()); + let mut gas = Gas::default(); + assert!(interpret_one(&Add, &mut gas, &mut stack).is_ok()); assert_eq!(stack, expected_stack); } @@ -115,7 +117,8 @@ mod interpreter_tests { fn test_dip() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(5), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(10), NumberValue(25)]); - assert!(interpret_one(&Dip(None, parse("{ADD}").unwrap()), &mut stack).is_ok()); + let mut gas = Gas::default(); + assert!(interpret_one(&Dip(None, parse("{ADD}").unwrap()), &mut gas, &mut stack).is_ok()); assert_eq!(stack, expected_stack); } @@ -123,7 +126,13 @@ mod interpreter_tests { fn test_dip2() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(5), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(10), NumberValue(5)]); - assert!(interpret_one(&Dip(Some(2), parse("{DROP}").unwrap()), &mut stack,).is_ok()); + let mut gas = Gas::default(); + assert!(interpret_one( + &Dip(Some(2), parse("{DROP}").unwrap()), + &mut gas, + &mut stack, + ) + .is_ok()); assert_eq!(stack, expected_stack); } @@ -131,7 +140,8 @@ mod interpreter_tests { fn test_drop() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(5), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(5), NumberValue(20)]); - assert!(interpret_one(&Drop(None), &mut stack).is_ok()); + let mut gas = Gas::default(); + assert!(interpret_one(&Drop(None), &mut gas, &mut stack).is_ok()); assert_eq!(stack, expected_stack); } @@ -139,7 +149,8 @@ mod interpreter_tests { fn test_drop2() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(5), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(20)]); - assert!(interpret_one(&Drop(Some(2)), &mut stack).is_ok()); + let mut gas = Gas::default(); + assert!(interpret_one(&Drop(Some(2)), &mut gas, &mut stack).is_ok()); assert_eq!(stack, expected_stack); } @@ -152,7 +163,8 @@ mod interpreter_tests { NumberValue(5), NumberValue(20), ]); - assert!(interpret_one(&Dup(None), &mut stack).is_ok()); + let mut gas = Gas::default(); + assert!(interpret_one(&Dup(None), &mut gas, &mut stack).is_ok()); assert_eq!(stack, expected_stack); } @@ -165,7 +177,8 @@ mod interpreter_tests { NumberValue(5), NumberValue(20), ]); - assert!(interpret_one(&Dup(Some(2)), &mut stack).is_ok()); + let mut gas = Gas::default(); + assert!(interpret_one(&Dup(Some(2)), &mut gas, &mut stack).is_ok()); assert_eq!(stack, expected_stack); } @@ -173,7 +186,8 @@ mod interpreter_tests { fn test_gt() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(20)]); let expected_stack = VecDeque::from([BooleanValue(true), NumberValue(20)]); - assert!(interpret_one(&Gt, &mut stack).is_ok()); + let mut gas = Gas::default(); + assert!(interpret_one(&Gt, &mut gas, &mut stack).is_ok()); assert_eq!(stack, expected_stack); } @@ -181,8 +195,10 @@ mod interpreter_tests { fn test_if_t() { let mut stack = VecDeque::from([BooleanValue(true), NumberValue(5), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(20)]); + let mut gas = Gas::default(); assert!(interpret_one( &If(parse("{DROP}").unwrap(), parse("{ADD}").unwrap()), + &mut gas, &mut stack, ) .is_ok()); @@ -193,8 +209,10 @@ mod interpreter_tests { fn test_if_f() { let mut stack = VecDeque::from([BooleanValue(false), NumberValue(5), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(25)]); + let mut gas = Gas::default(); assert!(interpret_one( &If(parse("{DROP}").unwrap(), parse("{ADD}").unwrap()), + &mut gas, &mut stack, ) .is_ok()); @@ -205,7 +223,8 @@ mod interpreter_tests { fn test_int() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(10), NumberValue(20)]); - assert!(interpret_one(&Int, &mut stack).is_ok()); + let mut gas = Gas::default(); + assert!(interpret_one(&Int, &mut gas, &mut stack).is_ok()); assert_eq!(stack, expected_stack); } @@ -213,7 +232,8 @@ mod interpreter_tests { fn test_push() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(0), NumberValue(10), NumberValue(20)]); - assert!(interpret_one(&Push(Type::Nat, NumberValue(0)), &mut stack).is_ok()); + let mut gas = Gas::default(); + assert!(interpret_one(&Push(Type::Nat, NumberValue(0)), &mut gas, &mut stack).is_ok()); assert_eq!(stack, expected_stack); } @@ -221,8 +241,10 @@ mod interpreter_tests { fn test_loop_0() { let mut stack = VecDeque::from([BooleanValue(false), NumberValue(10), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(10), NumberValue(20)]); + let mut gas = Gas::default(); assert!(interpret_one( &Loop(parse("{PUSH nat 1; ADD; PUSH bool False}").unwrap()), + &mut gas, &mut stack, ) .is_ok()); @@ -233,8 +255,10 @@ mod interpreter_tests { fn test_loop_1() { let mut stack = VecDeque::from([BooleanValue(true), NumberValue(10), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(11), NumberValue(20)]); + let mut gas = Gas::default(); assert!(interpret_one( &Loop(parse("{PUSH nat 1; ADD; PUSH bool False}").unwrap()), + &mut gas, &mut stack, ) .is_ok()); @@ -245,8 +269,10 @@ mod interpreter_tests { fn test_loop_many() { let mut stack = VecDeque::from([BooleanValue(true), NumberValue(10), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(0), NumberValue(20)]); + let mut gas = Gas::default(); assert!(interpret_one( &Loop(parse("{PUSH int -1; ADD; DUP; GT}").unwrap()), + &mut gas, &mut stack, ) .is_ok()); @@ -257,7 +283,8 @@ mod interpreter_tests { fn test_swap() { let mut stack = VecDeque::from([NumberValue(10), NumberValue(20)]); let expected_stack = VecDeque::from([NumberValue(20), NumberValue(10)]); - assert!(interpret_one(&Swap, &mut stack).is_ok()); + let mut gas = Gas::default(); + assert!(interpret_one(&Swap, &mut gas, &mut stack).is_ok()); assert_eq!(stack, expected_stack); } } diff --git a/contrib/mir/src/main.rs b/contrib/mir/src/main.rs index 11783a5419b8..58d9ac901f5a 100644 --- a/contrib/mir/src/main.rs +++ b/contrib/mir/src/main.rs @@ -29,7 +29,8 @@ mod tests { fn interpret_test_expect_success() { let ast = parser::parse(&FIBONACCI_SRC).unwrap(); let mut istack = VecDeque::from([Value::NumberValue(10)]); - assert!(interpreter::interpret(&ast, &mut istack).is_ok()); + let mut gas = Gas::default(); + assert!(interpreter::interpret(&ast, &mut gas, &mut istack).is_ok()); assert!(istack.len() == 1 && istack[0] == Value::NumberValue(55)); } -- GitLab From 76c464af6f950be7ac1e093185edf8a41a8d7396 Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Mon, 18 Sep 2023 20:53:01 +0300 Subject: [PATCH 3/7] MIR: consume gas in the interpreter --- contrib/mir/src/gas.rs | 64 ++++++++++++++++++++++++++++++++-- contrib/mir/src/interpreter.rs | 57 +++++++++++++++++++++--------- contrib/mir/src/main.rs | 9 +++++ 3 files changed, 112 insertions(+), 18 deletions(-) diff --git a/contrib/mir/src/gas.rs b/contrib/mir/src/gas.rs index 12ba4057575b..8e2837bd0ae4 100644 --- a/contrib/mir/src/gas.rs +++ b/contrib/mir/src/gas.rs @@ -46,8 +46,8 @@ impl Gas { } pub mod tc_cost { - // Due to the quirk of Octez implementation, step gas is charged twice as - // often as in MIR. + // Due to the quirk of the Tezos protocol implementation, step gas is + // charged twice as often as in MIR. pub const INSTR_STEP: u32 = 220 * 2; pub const VALUE_STEP: u32 = 100; @@ -71,6 +71,66 @@ pub mod tc_cost { } } +pub mod interpret_cost { + pub const DIP: u32 = 10; + pub const DROP: u32 = 10; + pub const DUP: u32 = 10; + pub const GT: u32 = 10; + pub const IF: u32 = 10; + pub const LOOP: u32 = 10; + pub const SWAP: u32 = 10; + pub const INT_NAT: u32 = 10; + pub const PUSH: u32 = 10; + + pub const INTERPRET_RET: u32 = 15; // corresponds to KNil in the Tezos protocol + pub const LOOP_ENTER: u32 = 10; // corresponds to KLoop_in in the Tezos protocol + pub const LOOP_EXIT: u32 = 10; + + fn dropn(n: usize) -> u32 { + // Approximates 30 + 2.713108*n, copied from the Tezos protocol + (30 + (2 * n) + (n >> 1) + (n >> 3)).try_into().unwrap() + } + + pub fn drop(mb_n: Option) -> u32 { + mb_n.map(dropn).unwrap_or(DROP) + } + + fn dipn(n: usize) -> u32 { + // Approximates 15 + 4.05787663635*n, copied from the Tezos protocol + (15 + (4 * n)).try_into().unwrap() + } + + pub fn dip(mb_n: Option) -> u32 { + mb_n.map(dipn).unwrap_or(DIP) + } + + pub fn undip(n: usize) -> u32 { + // this is derived by observing gas costs as of Nairobi, as charged by + // the Tezos protocol. It seems undip cost is charged as + // cost_N_KUndip * n + cost_N_KCons, + // where cost_N_KUndip = cost_N_KCons = 10 + (10 * (n + 1)).try_into().unwrap() + } + + fn dupn(n: usize) -> u32 { + // Approximates 20 + 1.222263*n, copied from the Tezos protocol + (20 + n + (n >> 2)).try_into().unwrap() + } + + pub fn dup(mb_n: Option) -> u32 { + mb_n.map(dupn).unwrap_or(DUP) + } + + pub fn add_int(i1: i32, i2: i32) -> u32 { + // NB: eventually when using BigInts, use BigInt::bits() &c + use std::mem::size_of_val; + // max is copied from the Tezos protocol, ostensibly adding two big ints depends on + // the larger of the two due to result allocation + let sz = std::cmp::max(size_of_val(&i1), size_of_val(&i2)); + (35 + (sz >> 1)).try_into().unwrap() + } +} + #[cfg(test)] mod test { use super::*; diff --git a/contrib/mir/src/interpreter.rs b/contrib/mir/src/interpreter.rs index 6ed9eaf5a9f9..12062cc49ce1 100644 --- a/contrib/mir/src/interpreter.rs +++ b/contrib/mir/src/interpreter.rs @@ -6,15 +6,24 @@ /******************************************************************************/ use crate::ast::*; -use crate::gas::Gas; +use crate::gas::{interpret_cost, Gas, OutOfGas}; use crate::stack::*; -pub enum InterpretError {} +pub enum InterpretError { + OutOfGas, +} + +impl From for InterpretError { + fn from(_: OutOfGas) -> Self { + InterpretError::OutOfGas + } +} pub fn interpret(ast: &AST, gas: &mut Gas, stack: &mut IStack) -> Result<(), InterpretError> { for i in ast { interpret_one(&i, gas, stack)?; } + gas.consume(interpret_cost::INTERPRET_RET)?; Ok(()) } @@ -31,6 +40,7 @@ fn interpret_one(i: &Instruction, gas: &mut Gas, stack: &mut IStack) -> Result<( match i { Add => match stack.make_contiguous() { [NumberValue(o1), NumberValue(o2), ..] => { + gas.consume(interpret_cost::add_int(*o1, *o2))?; let sum = *o1 + *o2; stack.pop_front(); stack.pop_front(); @@ -39,26 +49,34 @@ fn interpret_one(i: &Instruction, gas: &mut Gas, stack: &mut IStack) -> Result<( _ => unimplemented!(), }, Dip(opt_height, nested) => { + gas.consume(interpret_cost::dip(*opt_height))?; let protected_height: usize = opt_height.unwrap_or(1); let mut live = stack.split_off(protected_height); interpret(nested, gas, &mut live)?; + gas.consume(interpret_cost::undip(protected_height))?; stack.append(&mut live); } Drop(opt_height) => { + gas.consume(interpret_cost::drop(*opt_height))?; let drop_height: usize = opt_height.unwrap_or(1); *stack = stack.split_off(drop_height); } Dup(opt_height) => { + gas.consume(interpret_cost::dup(*opt_height))?; let dup_height: usize = opt_height.unwrap_or(1); stack.push_front(stack.get(dup_height - 1).unwrap().clone()); } - Gt => match stack.make_contiguous() { - [NumberValue(i), ..] => { - stack[0] = BooleanValue(*i > 0); + Gt => { + gas.consume(interpret_cost::GT)?; + match stack.make_contiguous() { + [NumberValue(i), ..] => { + stack[0] = BooleanValue(*i > 0); + } + _ => unreachable_state(), } - _ => unreachable_state(), - }, + } If(nested_t, nested_f) => { + gas.consume(interpret_cost::IF)?; if let Some(BooleanValue(b)) = stack.pop_front() { if b { interpret(nested_t, gas, stack)?; @@ -70,26 +88,33 @@ fn interpret_one(i: &Instruction, gas: &mut Gas, stack: &mut IStack) -> Result<( } } Instruction::Int => match stack.make_contiguous() { - [NumberValue(_), ..] => {} + [NumberValue(_), ..] => gas.consume(interpret_cost::INT_NAT)?, _ => { unreachable_state(); } }, - Loop(nested) => loop { - if let Some(BooleanValue(b)) = stack.pop_front() { - if b { - interpret(nested, gas, stack)?; + Loop(nested) => { + gas.consume(interpret_cost::LOOP_ENTER)?; + loop { + gas.consume(interpret_cost::LOOP)?; + if let Some(BooleanValue(b)) = stack.pop_front() { + if b { + interpret(nested, gas, stack)?; + } else { + gas.consume(interpret_cost::LOOP_EXIT)?; + break; + } } else { - break; + unreachable_state(); } - } else { - unreachable_state(); } - }, + } Push(_, v) => { + gas.consume(interpret_cost::PUSH)?; stack.push_front(v.clone()); } Swap => { + gas.consume(interpret_cost::SWAP)?; stack.swap(0, 1); } } diff --git a/contrib/mir/src/main.rs b/contrib/mir/src/main.rs index 58d9ac901f5a..0a8aa147e840 100644 --- a/contrib/mir/src/main.rs +++ b/contrib/mir/src/main.rs @@ -34,6 +34,15 @@ mod tests { assert!(istack.len() == 1 && istack[0] == Value::NumberValue(55)); } + #[test] + fn interpret_test_gas_consumption() { + let ast = parser::parse(&FIBONACCI_SRC).unwrap(); + let mut istack = VecDeque::from([Value::NumberValue(5)]); + let mut gas = Gas::new(1305); + assert!(interpreter::interpret(&ast, &mut gas, &mut istack).is_ok()); + assert_eq!(gas.milligas(), 0); + } + #[test] fn typecheck_test_expect_success() { let ast = parser::parse(&FIBONACCI_SRC).unwrap(); -- GitLab From 7e8207dd8e3b04789bc206e1292fd6a71203688d Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Mon, 18 Sep 2023 21:12:14 +0300 Subject: [PATCH 4/7] MIR: add interpreter out-of-gas test --- contrib/mir/src/interpreter.rs | 1 + contrib/mir/src/main.rs | 11 +++++++++++ 2 files changed, 12 insertions(+) diff --git a/contrib/mir/src/interpreter.rs b/contrib/mir/src/interpreter.rs index 12062cc49ce1..0922f6661701 100644 --- a/contrib/mir/src/interpreter.rs +++ b/contrib/mir/src/interpreter.rs @@ -9,6 +9,7 @@ use crate::ast::*; use crate::gas::{interpret_cost, Gas, OutOfGas}; use crate::stack::*; +#[derive(Debug, PartialEq, Eq)] pub enum InterpretError { OutOfGas, } diff --git a/contrib/mir/src/main.rs b/contrib/mir/src/main.rs index 0a8aa147e840..5c898001b284 100644 --- a/contrib/mir/src/main.rs +++ b/contrib/mir/src/main.rs @@ -43,6 +43,17 @@ mod tests { assert_eq!(gas.milligas(), 0); } + #[test] + fn interpret_test_gas_out_of_gas() { + let ast = parser::parse(&FIBONACCI_SRC).unwrap(); + let mut istack = VecDeque::from([Value::NumberValue(5)]); + let mut gas = Gas::new(1); + assert_eq!( + interpreter::interpret(&ast, &mut gas, &mut istack), + Err(interpreter::InterpretError::OutOfGas), + ); + } + #[test] fn typecheck_test_expect_success() { let ast = parser::parse(&FIBONACCI_SRC).unwrap(); -- GitLab From 6f7e0e8170e6c4767f1307a801616a07d6ef482f Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Wed, 20 Sep 2023 16:27:54 +0300 Subject: [PATCH 5/7] MIR: Report gas consumption in select tests --- contrib/mir/README.md | 4 ++++ contrib/mir/src/main.rs | 16 ++++++++++++++-- 2 files changed, 18 insertions(+), 2 deletions(-) diff --git a/contrib/mir/README.md b/contrib/mir/README.md index b00c844a7a2b..4f58ad77b8ed 100644 --- a/contrib/mir/README.md +++ b/contrib/mir/README.md @@ -15,3 +15,7 @@ command to build the project. You can run the included tests by the following command. `cargo test` + +Some tests print gas consumption information (in addition to testing it), but `cargo test` omits output from successful tests by default. To see it, run + +`cargo test -- --show-output` diff --git a/contrib/mir/src/main.rs b/contrib/mir/src/main.rs index 5c898001b284..77005019af9c 100644 --- a/contrib/mir/src/main.rs +++ b/contrib/mir/src/main.rs @@ -25,6 +25,14 @@ mod tests { use crate::parser; use crate::typechecker; + fn report_gas R>(gas: &mut Gas, f: F) -> R { + let initial_milligas = gas.milligas(); + let r = f(gas); + let gas_diff = initial_milligas - gas.milligas(); + println!("Gas consumed: {}.{:0>3}", gas_diff / 1000, gas_diff % 1000,); + r + } + #[test] fn interpret_test_expect_success() { let ast = parser::parse(&FIBONACCI_SRC).unwrap(); @@ -39,7 +47,9 @@ mod tests { let ast = parser::parse(&FIBONACCI_SRC).unwrap(); let mut istack = VecDeque::from([Value::NumberValue(5)]); let mut gas = Gas::new(1305); - assert!(interpreter::interpret(&ast, &mut gas, &mut istack).is_ok()); + report_gas(&mut gas, |gas| { + assert!(interpreter::interpret(&ast, gas, &mut istack).is_ok()); + }); assert_eq!(gas.milligas(), 0); } @@ -67,7 +77,9 @@ mod tests { let ast = parser::parse(&FIBONACCI_SRC).unwrap(); let mut stack = VecDeque::from([Type::Nat]); let mut gas = Gas::new(11460); - assert!(typechecker::typecheck(&ast, &mut gas, &mut stack).is_ok()); + report_gas(&mut gas, |gas| { + assert!(typechecker::typecheck(&ast, gas, &mut stack).is_ok()); + }); assert_eq!(gas.milligas(), 0); } -- GitLab From c232468b3c6ee96682b796f29a750c62e18276a2 Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Fri, 22 Sep 2023 14:19:15 +0300 Subject: [PATCH 6/7] MIR: treat overflow during gas estimation as out of gas --- contrib/mir/src/ast.rs | 2 +- contrib/mir/src/gas.rs | 87 ++++++++++++++++++++++++---------- contrib/mir/src/interpreter.rs | 10 ++-- contrib/mir/src/stack.rs | 2 +- contrib/mir/src/typechecker.rs | 4 +- 5 files changed, 72 insertions(+), 33 deletions(-) diff --git a/contrib/mir/src/ast.rs b/contrib/mir/src/ast.rs index 0e763ac4e608..7852b4224bf7 100644 --- a/contrib/mir/src/ast.rs +++ b/contrib/mir/src/ast.rs @@ -32,7 +32,7 @@ pub enum Value { pub type InstructionBlock = Vec; -#[derive(Debug, Eq, PartialEq)] +#[derive(Debug, Eq, PartialEq, Clone)] pub enum Instruction { Add, Dip(Option, InstructionBlock), diff --git a/contrib/mir/src/gas.rs b/contrib/mir/src/gas.rs index 8e2837bd0ae4..882916f6090b 100644 --- a/contrib/mir/src/gas.rs +++ b/contrib/mir/src/gas.rs @@ -13,6 +13,13 @@ pub struct Gas { #[derive(Debug, PartialEq, Eq)] pub struct OutOfGas; +/// Overflow errors can be treated as out-of-gas errors +impl From for OutOfGas { + fn from(_: std::num::TryFromIntError) -> Self { + OutOfGas + } +} + // Default gas limit per transaction, according to // https://opentezos.com/tezos-basics/economics-and-rewards/#transaction-cost const DEFAULT_GAS_AMOUNT: u32 = 1_040_000; @@ -46,32 +53,39 @@ impl Gas { } pub mod tc_cost { + use super::OutOfGas; + // Due to the quirk of the Tezos protocol implementation, step gas is // charged twice as often as in MIR. pub const INSTR_STEP: u32 = 220 * 2; pub const VALUE_STEP: u32 = 100; - fn variadic(depth: usize) -> u32 { - (depth * 50).try_into().unwrap() + fn variadic(depth: usize) -> Result { + Ok(depth.checked_mul(50).ok_or(OutOfGas)?.try_into()?) } - pub fn drop_n(depth: &Option) -> u32 { - depth.map(variadic).unwrap_or(0) + pub fn drop_n(depth: &Option) -> Result { + depth.map_or(Ok(0), variadic) } - pub fn dip_n(depth: &Option) -> u32 { - depth.map(variadic).unwrap_or(0) + pub fn dip_n(depth: &Option) -> Result { + depth.map_or(Ok(0), variadic) } - pub fn ty_eq(sz1: usize, sz2: usize) -> u32 { + pub fn ty_eq(sz1: usize, sz2: usize) -> Result { // complexity of comparing types T and U is O(min(|T|, |U|)), as // comparison short-circuits at the first mismatch - (std::cmp::min(sz1, sz2) * 60).try_into().unwrap() // according to Nairobi + Ok(std::cmp::min(sz1, sz2) + .checked_mul(60) // according to Nairobi + .ok_or(OutOfGas)? + .try_into()?) } } pub mod interpret_cost { + use super::OutOfGas; + pub const DIP: u32 = 10; pub const DROP: u32 = 10; pub const DUP: u32 = 10; @@ -86,48 +100,57 @@ pub mod interpret_cost { pub const LOOP_ENTER: u32 = 10; // corresponds to KLoop_in in the Tezos protocol pub const LOOP_EXIT: u32 = 10; - fn dropn(n: usize) -> u32 { + fn dropn(n: usize) -> Result { // Approximates 30 + 2.713108*n, copied from the Tezos protocol - (30 + (2 * n) + (n >> 1) + (n >> 3)).try_into().unwrap() + let go = |n: usize| { + n.checked_mul(2)? + .checked_add(30)? + .checked_add(n >> 1)? + .checked_add(n >> 3) + }; + Ok(go(n).ok_or(OutOfGas)?.try_into()?) } - pub fn drop(mb_n: Option) -> u32 { - mb_n.map(dropn).unwrap_or(DROP) + pub fn drop(mb_n: Option) -> Result { + mb_n.map_or(Ok(DROP), dropn) } - fn dipn(n: usize) -> u32 { + fn dipn(n: usize) -> Result { // Approximates 15 + 4.05787663635*n, copied from the Tezos protocol - (15 + (4 * n)).try_into().unwrap() + let go = |n: usize| n.checked_mul(4)?.checked_add(15); + Ok(go(n).ok_or(OutOfGas)?.try_into()?) } - pub fn dip(mb_n: Option) -> u32 { - mb_n.map(dipn).unwrap_or(DIP) + pub fn dip(mb_n: Option) -> Result { + mb_n.map_or(Ok(DIP), dipn) } - pub fn undip(n: usize) -> u32 { + pub fn undip(n: usize) -> Result { // this is derived by observing gas costs as of Nairobi, as charged by // the Tezos protocol. It seems undip cost is charged as // cost_N_KUndip * n + cost_N_KCons, // where cost_N_KUndip = cost_N_KCons = 10 - (10 * (n + 1)).try_into().unwrap() + let go = |n: usize| n.checked_add(1)?.checked_mul(10); + Ok(go(n).ok_or(OutOfGas)?.try_into()?) } - fn dupn(n: usize) -> u32 { + fn dupn(n: usize) -> Result { // Approximates 20 + 1.222263*n, copied from the Tezos protocol - (20 + n + (n >> 2)).try_into().unwrap() + let go = |n: usize| n.checked_add(20)?.checked_add(n >> 2); + Ok(go(n).ok_or(OutOfGas)?.try_into()?) } - pub fn dup(mb_n: Option) -> u32 { - mb_n.map(dupn).unwrap_or(DUP) + pub fn dup(mb_n: Option) -> Result { + mb_n.map_or(Ok(DUP), dupn) } - pub fn add_int(i1: i32, i2: i32) -> u32 { + pub fn add_int(i1: i32, i2: i32) -> Result { // NB: eventually when using BigInts, use BigInt::bits() &c use std::mem::size_of_val; // max is copied from the Tezos protocol, ostensibly adding two big ints depends on // the larger of the two due to result allocation let sz = std::cmp::max(size_of_val(&i1), size_of_val(&i2)); - (35 + (sz >> 1)).try_into().unwrap() + Ok((sz >> 1).checked_add(35).ok_or(OutOfGas)?.try_into()?) } } @@ -156,4 +179,20 @@ mod test { let _ = gas.consume(1000); // panics } + + #[test] + fn overflow_to_out_of_gas() { + fn check Result>(f: F) -> () { + assert_eq!(f(usize::MAX), Err(OutOfGas)); + assert_eq!(f(usize::MAX / 2), Err(OutOfGas)); + assert_eq!(f(usize::MAX / 4), Err(OutOfGas)); + } + check(|n| super::tc_cost::dip_n(&Some(n))); + check(|n| super::tc_cost::drop_n(&Some(n))); + check(|n| super::tc_cost::ty_eq(n, n)); + check(|n| super::interpret_cost::dip(Some(n))); + check(|n| super::interpret_cost::drop(Some(n))); + check(|n| super::interpret_cost::dup(Some(n))); + check(|n| super::interpret_cost::undip(n)); + } } diff --git a/contrib/mir/src/interpreter.rs b/contrib/mir/src/interpreter.rs index 0922f6661701..5a36909c5192 100644 --- a/contrib/mir/src/interpreter.rs +++ b/contrib/mir/src/interpreter.rs @@ -41,7 +41,7 @@ fn interpret_one(i: &Instruction, gas: &mut Gas, stack: &mut IStack) -> Result<( match i { Add => match stack.make_contiguous() { [NumberValue(o1), NumberValue(o2), ..] => { - gas.consume(interpret_cost::add_int(*o1, *o2))?; + gas.consume(interpret_cost::add_int(*o1, *o2)?)?; let sum = *o1 + *o2; stack.pop_front(); stack.pop_front(); @@ -50,20 +50,20 @@ fn interpret_one(i: &Instruction, gas: &mut Gas, stack: &mut IStack) -> Result<( _ => unimplemented!(), }, Dip(opt_height, nested) => { - gas.consume(interpret_cost::dip(*opt_height))?; + gas.consume(interpret_cost::dip(*opt_height)?)?; let protected_height: usize = opt_height.unwrap_or(1); let mut live = stack.split_off(protected_height); interpret(nested, gas, &mut live)?; - gas.consume(interpret_cost::undip(protected_height))?; + gas.consume(interpret_cost::undip(protected_height)?)?; stack.append(&mut live); } Drop(opt_height) => { - gas.consume(interpret_cost::drop(*opt_height))?; + gas.consume(interpret_cost::drop(*opt_height)?)?; let drop_height: usize = opt_height.unwrap_or(1); *stack = stack.split_off(drop_height); } Dup(opt_height) => { - gas.consume(interpret_cost::dup(*opt_height))?; + gas.consume(interpret_cost::dup(*opt_height)?)?; let dup_height: usize = opt_height.unwrap_or(1); stack.push_front(stack.get(dup_height - 1).unwrap().clone()); } diff --git a/contrib/mir/src/stack.rs b/contrib/mir/src/stack.rs index f2c905f160fb..3790acca583b 100644 --- a/contrib/mir/src/stack.rs +++ b/contrib/mir/src/stack.rs @@ -37,7 +37,7 @@ pub fn ensure_stacks_eq(gas: &mut Gas, stack1: &[Type], stack2: &[Type]) -> Resu } fn ensure_ty_eq(gas: &mut Gas, ty1: &Type, ty2: &Type) -> Result<(), TcError> { - gas.consume(gas::tc_cost::ty_eq(ty1.size_for_gas(), ty2.size_for_gas()))?; + gas.consume(gas::tc_cost::ty_eq(ty1.size_for_gas(), ty2.size_for_gas())?)?; if ty1 != ty2 { Err(TcError::StacksNotEqual) } else { diff --git a/contrib/mir/src/typechecker.rs b/contrib/mir/src/typechecker.rs index 20a2322aab58..501fcb31d8ae 100644 --- a/contrib/mir/src/typechecker.rs +++ b/contrib/mir/src/typechecker.rs @@ -56,7 +56,7 @@ fn typecheck_instruction( Dip(opt_height, nested) => { let protected_height: usize = opt_height.unwrap_or(1); - gas.consume(gas::tc_cost::dip_n(opt_height))?; + gas.consume(gas::tc_cost::dip_n(opt_height)?)?; ensure_stack_len(stack, protected_height)?; // Here we split the stack into protected and live segments, and after typechecking @@ -68,7 +68,7 @@ fn typecheck_instruction( } Drop(opt_height) => { let drop_height: usize = opt_height.unwrap_or(1); - gas.consume(gas::tc_cost::drop_n(opt_height))?; + gas.consume(gas::tc_cost::drop_n(opt_height)?)?; ensure_stack_len(&stack, drop_height)?; *stack = stack.split_off(drop_height); } -- GitLab From 32f05ec33712174efd4aabc34f92d15da5c6e3f2 Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Wed, 20 Sep 2023 17:46:56 +0300 Subject: [PATCH 7/7] MIR: Add a design description for gas consumption --- contrib/mir/DESIGN.md | 51 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 51 insertions(+) diff --git a/contrib/mir/DESIGN.md b/contrib/mir/DESIGN.md index f5513e44db5a..64c435feb89f 100644 --- a/contrib/mir/DESIGN.md +++ b/contrib/mir/DESIGN.md @@ -18,3 +18,54 @@ too hard to switch away from such a basic component later in the project. We used the Lalrpop library because we had some experience with it, and it seemed to work well in our initial trials. + +#### Gas consumption + +Gas counter is represented as the type `Gas`, containing an `Option` with the current milligas amount (or `None` after gas exhaustion). A mutable reference to the gas counter is passed to typechecker and interpreter. + +A method `consume` is implemented on the `Gas` type, which tries to consume the +cost passed as an argument; if there is enough gas remaining, the internal +counter is decreased by the appropriate amount; otherwise an error `OutOfGas` is +returned, and the internal counter is set to `None`. Any further calls to +`consume` are considered a logic error, and thus trigger a panic. + +It is possible to request the current milligas amount (useful for reporting and +debugging purposes) using the method `milligas()`. It is a logic error to +request the current remaining gas after gas exhaustion, and thus triggers a +panic. + +Gas costs are defined in submodules (i.e. namespaces) to avoid naming clashes. +Constant costs are declared as `const: u32`, while parametric costs are +implemented as functions returning `Result`. In case of overflow, +`Err(OutOfGas)` is returned. + +Gas consumption is done in-line in typechecker and interpreter. Both typechecker +and interpreter will immediately abort the computation on `OutOfGas` errors and +return the corresponding version of the error (`TcError::OutOfGas` or +`InterpretError::OutOfGas` respectively). + +The current design is broadly consistent with the design used by the Tezos +protocol, modulo the mutable reference and triggering a panic on accessing the +gas counter post exhaustion. + +Alternative designs: + +- Instead of a mutable reference, `typecheck` and `interpret` could return the + remaining gas amount. This is more in line with the approach used by the Tezos + protocol, however it's not idiomatic for Rust. + +- Gas consumption could, in theory, be handled entirely separately from the main + typechecker/interpreter code, however as gas consumption is highly dependent + on what typechecker/interpreter actually do, it would lead to a lot of + unnecessary code duplication and considerable difficulty in predicting the + interpreter's behaviour without doing the interpretation proper. + +- There was some discussion related to handling possible gas consumption after + `OutOfGas` error is thrown. Alternatives included setting the gas counter to + `0` after exhaustion (such that future calls to `consume` would trigger + `OutOfGas` again), or leaving it be in some consistent but undefined state + (which would simplify the code somewhat). + + Ultimately, trying to consume gas post-exhaustion was deemed to always + indicate a logic error, and thus, instead of masking such errors, a decision + was made to panic instead. -- GitLab