Compute delta_ip and delta_stp in side table by zhouwfang · Pull Request #626 · google/wasefire

zhouwfang · 2024-10-01T04:18:51Z

ia0

There are a few issues:

side_table_last_entry is wrong, you need to supported nested blocks. You might need to put an index to the side table in Label or LabelKind.
I don't think instruction index is the correct abstraction, I think we want instruction address. So you don't need instr_idx at all and can use parser.save().as_ptr() as i32.

Then in terms of design, I think we should keep Context constant in Expr and make Expr::check_body return the side-table. We can then set it from Context::check_module where check_body is called.

zhouwfang · 2024-10-02T04:30:55Z

There are a few issues:

side_table_last_entry is wrong, you need to supported nested blocks. You might need to put an index to the side table in Label or LabelKind.

I don't think instruction index is the correct abstraction, I think we want instruction address. So you don't need instr_idx at all and can use parser.save().as_ptr() as i32.

Then in terms of design, I think we should keep Context constant in Expr and make Expr::check_body return the side-table. We can then set it from Context::check_module where check_body is called.

Thanks! The issues with parser.save().as_ptr() as i32 are

parser.save().as_ptr() overflows.
The DELTA_IP_MASK is too small to hold it.

ia0

I'm not sure it's worth iterating too much. It's simpler to just design correctly from the start, which means understanding the goal. Essentially, we want all occurrences of skip_to_{else,end}() in exec.rs to be resolved from the side-table (to which we can add Loop to handle everything uniformly). This means If, Else, Br{,If} should each have an entry in the side-table and BrTable as much as its arguments. This defines when an entry is added. Then we need to fill their content, which is done on Loop, Else, and End (with Loop done before the entry is added). This means that for Loop we can store the parser position in the LabelKind (like done in exec.rs). For Else and End, we need the side-table entries to register themselves in their labels. This means that Label should contain an entries: Vec<(&'m [u8], usize)> recording for each side-table entry the parser position and the side-table length when it was added. Then in end_label() we can simply go over all entries compute the difference between the current parser position and the saved one to compute the delta IP, as well as the difference between the current side-table length and the index for the delta STP. We can then update the side-table entry.

ia0 · 2024-10-02T08:25:31Z

Thanks! The issues with parser.save().as_ptr() as i32 are

parser.save().as_ptr() overflows.

The DELTA_IP_MASK is too small to hold it.

Those are not issues because we only care about deltas between parser.save(). In the proposed design, I store directly the &'m [u8] delays converting to i32 until after we compute the delta.

zhouwfang · 2024-10-08T05:36:27Z

I'm not sure it's worth iterating too much. It's simpler to just design correctly from the start, which means understanding the goal. Essentially, we want all occurrences of skip_to_{else,end}() in exec.rs to be resolved from the side-table (to which we can add Loop to handle everything uniformly). This means If, Else, Br{,If} should each have an entry in the side-table and BrTable as much as its arguments. This defines when an entry is added. Then we need to fill their content, which is done on Loop, Else, and End (with Loop done before the entry is added). This means that for Loop we can store the parser position in the LabelKind (like done in exec.rs). For Else and End, we need the side-table entries to register themselves in their labels. This means that Label should contain an entries: Vec<(&'m [u8], usize)> recording for each side-table entry the parser position and the side-table length when it was added. Then in end_label() we can simply go over all entries compute the difference between the current parser position and the saved one to compute the delta IP, as well as the difference between the current side-table length and the index for the delta STP. We can then update the side-table entry.

Thanks! I implemented this design except Loop for the moment. I'll run some tests in the meanwhile.

zhouwfang · 2024-10-08T05:38:04Z

        if label.kind == LabelKind::If {
            check(label.type_.params == label.type_.results)?;


@ia0 Could you explain the purpose of this if block? Thanks.

This is because the binary format allows an if without else (see the note of https://webassembly.github.io/spec/core/binary/instructions.html#control-instructions) and defines it as having an empty sequence for the else. So here we are validating the empty sequence according to https://webassembly.github.io/spec/core/valid/instructions.html#empty-instruction-sequence-epsilon which essentially says that the params and results must be the same.

ia0

Thanks! It starts to get in shape but there is still some confusion between "branches" and "entries". I introduced those new names to help make the distinction. An entry is an element in the side table. A branch is a marker left by an entry in the label it wishes to know the End (or Loop for Loop). There is thus a one-to-one mapping between branches and entries. This is ensured by used Option<SideTableEntryView> and making sure we write Some only on None and we only have Some at the end. We have a stitch function that stitches an entry based on its branch (with assumption that the parser is at the End of the label in which the branch is, or Else for If).

ia0 · 2024-10-08T08:18:05Z

        if label.kind == LabelKind::If {
            check(label.type_.params == label.type_.results)?;


This is because the binary format allows an if without else (see the note of https://webassembly.github.io/spec/core/binary/instructions.html#control-instructions) and defines it as having an empty sequence for the else. So here we are validating the empty sequence according to https://webassembly.github.io/spec/core/valid/instructions.html#empty-instruction-sequence-epsilon which essentially says that the params and results must be the same.

ia0

Thanks! There are still some fundamental issues but the overall shape is getting there.

ia0

Thanks, it's almost there. The main question is how to deal with pathological examples in the test suite. I think the strategy of using a sentinel value in the side table entries and returning an error at runtime is a good option. If this results in performance problems (because we need to check the sentinel at runtime), we can gate this behavior behind a feature (like toctou). The feature would move returning an error from exec.rs to valid.rs ensuring that there are no sentinel values at runtime.

ia0 · 2024-10-17T15:30:08Z

I've merge main into dev/fast-interp. You might want to pull and merge your add-delta-ip branch into dev/fast-interp. This adds better support for unsupported operations, such that we can still run parts of a test instead of having to ignore it completely.

zhouwfang · 2024-10-19T05:17:50Z

Could you clarify the hw-host error? I guess it results from the side table bit mask size issue.

zhouwfang · 2024-10-20T04:36:51Z

I posted zhouwfang#2 to add val_cnt and pop_cnt on top of this PR. Could you also take a look at that? Thanks.

ia0

Thanks! I think this should work modulo off-by-one errors. While updating exec.rs we might want to change the exact location of the branches or how to interpret the side table.

ia0 · 2024-10-21T12:10:33Z

Could you clarify the hw-host error? I guess it results from the side table bit mask size issue.

Yes, this is indeed the side table masks being too short. So we'll probably have to use a u64 for the bit fields. You can also apply the following patch:

--- a/crates/interpreter/src/bit_field.rs
+++ b/crates/interpreter/src/bit_field.rs
@@ -29,6 +29,8 @@ fn offset(mask: u32) -> i32 {
 pub fn into_field(mask: u32, value: u32) -> Result<u32, Error> {
     let field = (value << mask.trailing_zeros()) & mask;
     if from_field(mask, field) != value {
+        #[cfg(feature = "debug")]
+        eprintln!("Bit field value {value:08x} doesn't fit in mask {mask:08x}.");
         return Err(unsupported(if_debug!(Unsupported::SideTable)));
     }
     Ok(field)

This is similar to what we do in the memory_too_small function.

ia0

Thanks! I've refactored the side table out to help the borrow checker understand it's alright. I also split branch() into branch_source() and branch_target() to be more explicit why we're taking a branch and avoid accidents of forgetting to allocate a side-table entry when taking a source branch.

zhouwfang requested a review from ia0 as a code owner October 1, 2024 04:18

zhouwfang changed the title ~~Compute delta_ip in side table for if and else~~ Compute delta_ip in side table for If/Else Oct 1, 2024

ia0 reviewed Oct 1, 2024

View reviewed changes

zhouwfang requested a review from ia0 October 2, 2024 04:33

ia0 reviewed Oct 2, 2024

View reviewed changes

Comment thread crates/interpreter/src/valid.rs Outdated

Comment thread crates/interpreter/src/valid.rs Outdated

zhouwfang changed the title ~~Compute delta_ip in side table for If/Else~~ Compute delta_ip in side table Oct 8, 2024

zhouwfang commented Oct 8, 2024

View reviewed changes

zhouwfang requested a review from ia0 October 8, 2024 05:38

ia0 reviewed Oct 8, 2024

View reviewed changes

zhouwfang requested a review from ia0 October 9, 2024 06:18

ia0 reviewed Oct 9, 2024

View reviewed changes

zhouwfang requested a review from ia0 October 14, 2024 06:10

zhouwfang commented Oct 14, 2024

View reviewed changes

Comment thread crates/interpreter/src/valid.rs Outdated

zhouwfang changed the title ~~Compute delta_ip in side table~~ Compute delta_ip and delta_stp in side table Oct 15, 2024

zhouwfang commented Oct 17, 2024

View reviewed changes

Comment thread crates/interpreter/src/side_table.rs Outdated

ia0 reviewed Oct 17, 2024

View reviewed changes

zhouwfang added 10 commits October 17, 2024 20:13

feat: compute delta_ip for if and else

4d992d3

fix: increment self.instr_idx

4241b0b

revert

4a8c3d0

feat: compute delta_ip for If/Else

f5c7e76

refactor: remove the Option on is_block_under_else

ba6bbb5

feat!: compute delta_ip except loop

142698a

refactor!: introduce SideTableBranch

70f7c58

fix!: delta_ip computation bugs

9b81dd8

feat!: compute delta_stp

6c2672e

fix: enlarge DELTA_IP_MASK to fix runner-host

f172736

ia0 reviewed Oct 18, 2024

View reviewed changes

Comment thread crates/interpreter/src/valid.rs Outdated

Comment thread crates/interpreter/src/valid.rs Outdated

fix!: if without else

8ef39d1

zhouwfang force-pushed the add-delta-ip branch from 6176de2 to 8ef39d1 Compare October 19, 2024 04:59

zhouwfang requested a review from ia0 October 19, 2024 05:18

ia0 reviewed Oct 21, 2024

View reviewed changes

Comment thread crates/interpreter/src/valid.rs

Comment thread crates/interpreter/src/valid.rs Outdated

Comment thread crates/interpreter/src/valid.rs Outdated

Comment thread crates/interpreter/src/valid.rs Outdated

Comment thread crates/interpreter/src/valid.rs Outdated

zhouwfang added 3 commits October 21, 2024 20:18

refactor: minor

52afc25

fix: increase mask size to 64 bits

6ef2c1c

chore: add debug print

073b143

zhouwfang requested a review from ia0 October 22, 2024 04:27

review

b1b4009

ia0 approved these changes Oct 22, 2024

View reviewed changes

Comment thread crates/interpreter/src/bit_field.rs Outdated

Comment thread crates/interpreter/src/bit_field.rs Outdated

Comment thread crates/interpreter/src/bit_field.rs Outdated

Comment thread crates/interpreter/src/side_table.rs Outdated

ia0 merged commit cc48cb9 into google:dev/fast-interp Oct 22, 2024

		if label.kind == LabelKind::If {
		check(label.type_.params == label.type_.results)?;

Uh oh!

Conversation

zhouwfang commented Oct 1, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ia0 left a comment

Choose a reason for hiding this comment

Uh oh!

zhouwfang commented Oct 2, 2024

Uh oh!

ia0 left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

ia0 commented Oct 2, 2024

Uh oh!

zhouwfang commented Oct 8, 2024

Uh oh!

zhouwfang Oct 8, 2024

Choose a reason for hiding this comment

Uh oh!

ia0 Oct 8, 2024

Choose a reason for hiding this comment

Uh oh!

ia0 left a comment

Choose a reason for hiding this comment

Uh oh!

ia0 Oct 8, 2024

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

ia0 left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

ia0 left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

ia0 commented Oct 17, 2024

Uh oh!

Uh oh!

Uh oh!

zhouwfang commented Oct 19, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

zhouwfang commented Oct 20, 2024

Uh oh!

ia0 left a comment

Choose a reason for hiding this comment

Uh oh!

zhouwfang commented Oct 1, 2024 •

edited

Loading

zhouwfang commented Oct 19, 2024 •

edited

Loading