Fix Atomics fuzz bugs in interpreter (#2760)

I am working to bring up the fuzzer on comparisons between VMs.
Comparing between the binaryen interpreter and v8, it found some
atomics issues:

Atomic operations, including loads and stores, must be aligned
or they trap.

AtomicRMW did the wrong thing with the operands.

AtomicCmpxchg must wrap the input to the proper size (if we
only load 1 byte, only look at 1 byte of the expected value too).

AtomicWait and AtomicNotify must take into account their
offsets. Also SIMDLoadExtend was missing that. This was
confusing in the code as two getFinalAddresses existed,
one that doesn't compute with an offset, and one that does.
I renamed the one without to getFinalAddressWithoutOffset
so it's explicit and we can easily see we only call that one on
an instruction without an offset (which is the case for
MemoryInit, MemoryCopy, and MemoryFill).

AtomicNotify must check its address to see if it should trap,
even though we don't actually have multiple threads running.

Atomic loads of fewer bytes than the type always do an
unsigned extension, not signed.

5 files changed, 423 insertions, 114 deletions

diff --git a/src/wasm-interpreter.h b/src/wasm-interpreter.h
index ca8041d5a..7a1fc1784 100644
--- a/src/wasm-interpreter.h
+++ b/src/wasm-interpreter.h
@@ -1689,6 +1689,9 @@ private:
       }
       NOTE_EVAL1(flow);
       auto addr = instance.getFinalAddress(curr, flow.getSingleValue());
+      if (curr->isAtomic) {
+        instance.checkAtomicAddress(addr, curr->bytes);
+      }
       auto ret = instance.externalInterface->load(curr, addr);
       NOTE_EVAL1(addr);
       NOTE_EVAL1(ret);
@@ -1705,6 +1708,9 @@ private:
         return value;
       }
       auto addr = instance.getFinalAddress(curr, ptr.getSingleValue());
+      if (curr->isAtomic) {
+        instance.checkAtomicAddress(addr, curr->bytes);
+      }
       NOTE_EVAL1(addr);
       NOTE_EVAL1(value);
       instance.externalInterface->store(curr, addr, value.getSingleValue());
@@ -1730,22 +1736,21 @@ private:
       auto computed = value.getSingleValue();
       switch (curr->op) {
         case Add:
-          computed = computed.add(value.getSingleValue());
+          computed = loaded.add(computed);
           break;
         case Sub:
-          computed = computed.sub(value.getSingleValue());
+          computed = loaded.sub(computed);
           break;
         case And:
-          computed = computed.and_(value.getSingleValue());
+          computed = loaded.and_(computed);
           break;
         case Or:
-          computed = computed.or_(value.getSingleValue());
+          computed = loaded.or_(computed);
           break;
         case Xor:
-          computed = computed.xor_(value.getSingleValue());
+          computed = loaded.xor_(computed);
           break;
         case Xchg:
-          computed = value.getSingleValue();
           break;
       }
       instance.doAtomicStore(addr, curr->bytes, computed);
@@ -1767,6 +1772,8 @@ private:
         return replacement;
       }
       auto addr = instance.getFinalAddress(curr, ptr.getSingleValue());
+      expected =
+        Flow(wrapToSmallerSize(expected.getSingleValue(), curr->bytes));
       NOTE_EVAL1(addr);
       NOTE_EVAL1(expected);
       NOTE_EVAL1(replacement);
@@ -1795,7 +1802,7 @@ private:
         return timeout;
       }
       auto bytes = curr->expectedType.getByteSize();
-      auto addr = instance.getFinalAddress(ptr.getSingleValue(), bytes);
+      auto addr = instance.getFinalAddress(curr, ptr.getSingleValue(), bytes);
       auto loaded = instance.doAtomicLoad(addr, bytes, curr->expectedType);
       NOTE_EVAL1(loaded);
       if (loaded != expected.getSingleValue()) {
@@ -1817,7 +1824,9 @@ private:
       if (count.breaking()) {
         return count;
       }
-      // TODO: add threads support!
+      auto addr = instance.getFinalAddress(curr, ptr.getSingleValue(), 4);
+      // Just check TODO actual threads support
+      instance.checkAtomicAddress(addr, 4);
       return Literal(int32_t(0)); // none woken up
     }
     Flow visitSIMDLoad(SIMDLoad* curr) {
@@ -1901,7 +1910,7 @@ private:
       auto fillLanes = [&](auto lanes, size_t laneBytes) {
         for (auto& lane : lanes) {
           lane = loadLane(
-            instance.getFinalAddress(Literal(uint32_t(src)), laneBytes));
+            instance.getFinalAddress(curr, Literal(uint32_t(src)), laneBytes));
           src = Address(uint32_t(src) + laneBytes);
         }
         return Literal(lanes);
@@ -1997,8 +2006,9 @@ private:
       }
       for (size_t i = 0; i < sizeVal; ++i) {
         Literal addr(uint32_t(destVal + i));
-        instance.externalInterface->store8(instance.getFinalAddress(addr, 1),
-                                           segment.data[offsetVal + i]);
+        instance.externalInterface->store8(
+          instance.getFinalAddressWithoutOffset(addr, 1),
+          segment.data[offsetVal + i]);
       }
       return {};
     }
@@ -2046,9 +2056,11 @@ private:
       }
       for (int64_t i = start; i != end; i += step) {
         instance.externalInterface->store8(
-          instance.getFinalAddress(Literal(uint32_t(destVal + i)), 1),
+          instance.getFinalAddressWithoutOffset(Literal(uint32_t(destVal + i)),
+                                                1),
           instance.externalInterface->load8s(
-            instance.getFinalAddress(Literal(uint32_t(sourceVal + i)), 1)));
+            instance.getFinalAddressWithoutOffset(
+              Literal(uint32_t(sourceVal + i)), 1)));
       }
       return {};
     }
@@ -2079,7 +2091,9 @@ private:
       uint8_t val(value.getSingleValue().geti32());
       for (size_t i = 0; i < sizeVal; ++i) {
         instance.externalInterface->store8(
-          instance.getFinalAddress(Literal(uint32_t(destVal + i)), 1), val);
+          instance.getFinalAddressWithoutOffset(Literal(uint32_t(destVal + i)),
+                                                1),
+          val);
       }
       return {};
     }
@@ -2103,6 +2117,44 @@ private:
     void trap(const char* why) override {
       instance.externalInterface->trap(why);
     }
+
+    // Given a value, wrap it to a smaller given number of bytes.
+    Literal wrapToSmallerSize(Literal value, Index bytes) {
+      if (value.type == Type::i32) {
+        switch (bytes) {
+          case 1: {
+            return value.and_(Literal(uint32_t(0xff)));
+          }
+          case 2: {
+            return value.and_(Literal(uint32_t(0xffff)));
+          }
+          case 4: {
+            break;
+          }
+          default:
+            WASM_UNREACHABLE("unexpected bytes");
+        }
+      } else {
+        assert(value.type == Type::i64);
+        switch (bytes) {
+          case 1: {
+            return value.and_(Literal(uint64_t(0xff)));
+          }
+          case 2: {
+            return value.and_(Literal(uint64_t(0xffff)));
+          }
+          case 4: {
+            return value.and_(Literal(uint64_t(0xffffffffUL)));
+          }
+          case 8: {
+            break;
+          }
+          default:
+            WASM_UNREACHABLE("unexpected bytes");
+        }
+      }
+      return value;
+    }
   };
 
 public:
@@ -2173,21 +2225,25 @@ protected:
     }
   }
 
-  template<class LS> Address getFinalAddress(LS* curr, Literal ptr) {
+  template<class LS>
+  Address getFinalAddress(LS* curr, Literal ptr, Index bytes) {
     Address memorySizeBytes = memorySize * Memory::kPageSize;
     uint64_t addr = ptr.type == Type::i32 ? ptr.geti32() : ptr.geti64();
     trapIfGt(curr->offset, memorySizeBytes, "offset > memory");
     trapIfGt(addr, memorySizeBytes - curr->offset, "final > memory");
     addr += curr->offset;
-    trapIfGt(curr->bytes, memorySizeBytes, "bytes > memory");
-    checkLoadAddress(addr, curr->bytes);
+    trapIfGt(bytes, memorySizeBytes, "bytes > memory");
+    checkLoadAddress(addr, bytes);
     return addr;
   }
 
-  Address getFinalAddress(Literal ptr, Index bytes) {
-    Address memorySizeBytes = memorySize * Memory::kPageSize;
+  template<class LS> Address getFinalAddress(LS* curr, Literal ptr) {
+    return getFinalAddress(curr, ptr, curr->bytes);
+  }
+
+  Address getFinalAddressWithoutOffset(Literal ptr, Index bytes) {
     uint64_t addr = ptr.type == Type::i32 ? ptr.geti32() : ptr.geti64();
-    trapIfGt(addr, memorySizeBytes - bytes, "highest > memory");
+    checkLoadAddress(addr, bytes);
     return addr;
   }
 
@@ -2196,14 +2252,26 @@ protected:
     trapIfGt(addr, memorySizeBytes - bytes, "highest > memory");
   }
 
-  Literal doAtomicLoad(Address addr, Index bytes, Type type) {
+  void checkAtomicAddress(Address addr, Index bytes) {
     checkLoadAddress(addr, bytes);
+    // Unaligned atomics trap.
+    if (bytes > 1) {
+      if (addr & (bytes - 1)) {
+        externalInterface->trap("unaligned atomic operation");
+      }
+    }
+  }
+
+  Literal doAtomicLoad(Address addr, Index bytes, Type type) {
+    checkAtomicAddress(addr, bytes);
     Const ptr;
     ptr.value = Literal(int32_t(addr));
     ptr.type = Type::i32;
     Load load;
     load.bytes = bytes;
-    load.signed_ = true;
+    // When an atomic loads a partial number of bytes for the type, it is
+    // always an unsigned extension.
+    load.signed_ = false;
     load.align = bytes;
     load.isAtomic = true; // understatement
     load.ptr = &ptr;
@@ -2212,6 +2280,7 @@ protected:
   }
 
   void doAtomicStore(Address addr, Index bytes, Literal toStore) {
+    checkAtomicAddress(addr, bytes);
     Const ptr;
     ptr.value = Literal(int32_t(addr));
     ptr.type = Type::i32;
diff --git a/test/passes/fuzz-exec_all-features.txt b/test/passes/fuzz-exec_all-features.txt
new file mode 100644
index 000000000..a6b25e8ca
--- /dev/null
+++ b/test/passes/fuzz-exec_all-features.txt
@@ -0,0 +1,209 @@
+[fuzz-exec] calling a
+[fuzz-exec] note result: a => -69
+[fuzz-exec] calling b
+[fuzz-exec] note result: b => -31768
+[fuzz-exec] calling c
+[fuzz-exec] note result: c => -69
+[fuzz-exec] calling d
+[fuzz-exec] note result: d => -31768
+[fuzz-exec] calling e
+[fuzz-exec] note result: e => -2146649112
+(module
+ (type $none_=>_i64 (func (result i64)))
+ (type $none_=>_i32 (func (result i32)))
+ (export "a" (func $a))
+ (export "b" (func $b))
+ (export "c" (func $c))
+ (export "d" (func $d))
+ (export "e" (func $e))
+ (func $a (result i32)
+  (i32.extend8_s
+   (i32.const 187)
+  )
+ )
+ (func $b (result i32)
+  (i32.extend16_s
+   (i32.const 33768)
+  )
+ )
+ (func $c (result i64)
+  (i64.extend8_s
+   (i64.const 187)
+  )
+ )
+ (func $d (result i64)
+  (i64.extend16_s
+   (i64.const 33768)
+  )
+ )
+ (func $e (result i64)
+  (i64.extend32_s
+   (i64.const 2148318184)
+  )
+ )
+)
+[fuzz-exec] calling a
+[fuzz-exec] note result: a => -69
+[fuzz-exec] calling b
+[fuzz-exec] note result: b => -31768
+[fuzz-exec] calling c
+[fuzz-exec] note result: c => -69
+[fuzz-exec] calling d
+[fuzz-exec] note result: d => -31768
+[fuzz-exec] calling e
+[fuzz-exec] note result: e => -2146649112
+[fuzz-exec] comparing a
+[fuzz-exec] comparing b
+[fuzz-exec] comparing c
+[fuzz-exec] comparing d
+[fuzz-exec] comparing e
+[fuzz-exec] calling unaligned_load
+[trap unaligned atomic operation]
+[fuzz-exec] calling unaligned_load_offset
+[trap unaligned atomic operation]
+[fuzz-exec] calling aligned_for_size
+[fuzz-exec] note result: aligned_for_size => 0
+[fuzz-exec] calling unaligned_notify
+[trap unaligned atomic operation]
+[fuzz-exec] calling wrap_cmpxchg
+[LoggingExternalInterface logging 42]
+[fuzz-exec] calling oob_notify
+[trap final > memory: 18446744073709551512 > 65514]
+(module
+ (type $none_=>_i32 (func (result i32)))
+ (type $none_=>_none (func))
+ (type $i32_=>_none (func (param i32)))
+ (type $i32_i32_=>_none (func (param i32 i32)))
+ (import "fuzzing-support" "log-i32" (func $fimport$0 (param i32)))
+ (memory $0 (shared 1 1))
+ (export "unaligned_load" (func $0))
+ (export "unaligned_load_offset" (func $1))
+ (export "aligned_for_size" (func $2))
+ (export "unaligned_notify" (func $3))
+ (export "wrap_cmpxchg" (func $4))
+ (export "oob_notify" (func $5))
+ (func $0 (result i32)
+  (i32.atomic.load
+   (i32.const 1)
+  )
+ )
+ (func $1 (result i32)
+  (i32.atomic.load offset=1
+   (i32.const 0)
+  )
+ )
+ (func $2 (result i32)
+  (i32.atomic.load16_u offset=2
+   (i32.const 0)
+  )
+ )
+ (func $3 (result i32)
+  (atomic.notify
+   (i32.const 1)
+   (i32.const 1)
+  )
+ )
+ (func $4 (param $0 i32) (param $1 i32)
+  (drop
+   (i32.atomic.rmw8.cmpxchg_u
+    (i32.const 0)
+    (i32.const 256)
+    (i32.const 42)
+   )
+  )
+  (call $fimport$0
+   (i32.load
+    (i32.const 0)
+   )
+  )
+ )
+ (func $5
+  (drop
+   (atomic.notify offset=22
+    (i32.const -104)
+    (i32.const -72)
+   )
+  )
+ )
+)
+[fuzz-exec] calling unaligned_load
+[trap unaligned atomic operation]
+[fuzz-exec] calling unaligned_load_offset
+[trap unaligned atomic operation]
+[fuzz-exec] calling aligned_for_size
+[fuzz-exec] note result: aligned_for_size => 0
+[fuzz-exec] calling unaligned_notify
+[trap unaligned atomic operation]
+[fuzz-exec] calling wrap_cmpxchg
+[LoggingExternalInterface logging 42]
+[fuzz-exec] calling oob_notify
+[trap final > memory: 18446744073709551512 > 65514]
+[fuzz-exec] comparing aligned_for_size
+[fuzz-exec] comparing unaligned_load
+[fuzz-exec] comparing unaligned_load_offset
+[fuzz-exec] comparing unaligned_notify
+[fuzz-exec] calling unsigned_2_bytes
+[fuzz-exec] note result: unsigned_2_bytes => 65535
+(module
+ (type $none_=>_i32 (func (result i32)))
+ (memory $0 (shared 1 1))
+ (data (i32.const 0) "\ff\ff")
+ (export "unsigned_2_bytes" (func $0))
+ (func $0 (result i32)
+  (i32.atomic.rmw16.xor_u
+   (i32.const 0)
+   (i32.const 0)
+  )
+ )
+)
+[fuzz-exec] calling unsigned_2_bytes
+[fuzz-exec] note result: unsigned_2_bytes => 65535
+[fuzz-exec] comparing unsigned_2_bytes
+[fuzz-exec] calling rmw-reads-modifies-and-writes
+[LoggingExternalInterface logging 0]
+(module
+ (type $none_=>_none (func))
+ (type $i32_=>_none (func (param i32)))
+ (import "fuzzing-support" "log-i32" (func $fimport$0 (param i32)))
+ (memory $0 (shared 1 1))
+ (export "rmw-reads-modifies-and-writes" (func $0))
+ (func $0
+  (drop
+   (i64.atomic.rmw16.and_u offset=4
+    (i32.const 0)
+    (i64.const 65535)
+   )
+  )
+  (call $fimport$0
+   (i32.load8_u
+    (i32.const 5)
+   )
+  )
+ )
+)
+[fuzz-exec] calling rmw-reads-modifies-and-writes
+[LoggingExternalInterface logging 0]
+[fuzz-exec] calling rmw-reads-modifies-and-writes-asymmetrical
+[LoggingExternalInterface logging 214]
+(module
+ (type $none_=>_none (func))
+ (type $i32_=>_none (func (param i32)))
+ (import "fuzzing-support" "log-i32" (func $fimport$0 (param i32)))
+ (memory $0 (shared 1 1))
+ (export "rmw-reads-modifies-and-writes-asymmetrical" (func $0))
+ (func $0
+  (drop
+   (i32.atomic.rmw8.sub_u
+    (i32.const 3)
+    (i32.const 42)
+   )
+  )
+  (call $fimport$0
+   (i32.load8_u
+    (i32.const 3)
+   )
+  )
+ )
+)
+[fuzz-exec] calling rmw-reads-modifies-and-writes-asymmetrical
+[LoggingExternalInterface logging 214]
diff --git a/test/passes/fuzz-exec_all-features.wast b/test/passes/fuzz-exec_all-features.wast
new file mode 100644
index 000000000..fd3018502
--- /dev/null
+++ b/test/passes/fuzz-exec_all-features.wast
@@ -0,0 +1,123 @@
+(module
+ (export "a" (func $a))
+ (export "b" (func $b))
+ (export "c" (func $c))
+ (export "d" (func $d))
+ (export "e" (func $e))
+ (func $a (result i32)
+  (i32.extend8_s
+   (i32.const 187)
+  )
+ )
+ (func $b (result i32)
+  (i32.extend16_s
+   (i32.const 33768)
+  )
+ )
+ (func $c (result i64)
+  (i64.extend8_s
+   (i64.const 187)
+  )
+ )
+ (func $d (result i64)
+  (i64.extend16_s
+   (i64.const 33768)
+  )
+ )
+ (func $e (result i64)
+  (i64.extend32_s
+   (i64.const 2148318184)
+  )
+ )
+)
+(module
+ (import "fuzzing-support" "log-i32" (func $fimport$0 (param i32)))
+ (memory $0 (shared 1 1))
+ (func "unaligned_load" (result i32)
+  (i32.atomic.load
+   (i32.const 1) ;; unaligned ptr
+   (i32.const 1)
+  )
+ )
+ (func "unaligned_load_offset" (result i32)
+  (i32.atomic.load offset=1 ;; unaligned with offset
+   (i32.const 0)
+   (i32.const 1)
+  )
+ )
+ (func "aligned_for_size" (result i32)
+  (i32.atomic.load16_u offset=2 ;; just 2 bytes loaded, so size is ok
+   (i32.const 0)
+  )
+ )
+ (func "unaligned_notify" (result i32)
+  (atomic.notify
+   (i32.const 1) ;; unaligned
+   (i32.const 1)
+  )
+ )
+ (func "wrap_cmpxchg" (param $0 i32) (param $1 i32)
+  (drop
+   (i32.atomic.rmw8.cmpxchg_u
+    (i32.const 0)
+    (i32.const 256) ;; 0x100, lower byte is 0 - should be wrapped to that
+    (i32.const 42)
+   )
+  )
+  (call $fimport$0
+   (i32.load (i32.const 0))
+  )
+ )
+ (func "oob_notify"
+  (drop
+   (atomic.notify offset=22
+    (i32.const -104) ;; illegal address
+    (i32.const -72)
+   )
+  )
+ )
+)
+(module
+ (memory $0 (shared 1 1))
+ (data (i32.const 0) "\ff\ff")
+ (func "unsigned_2_bytes" (result i32)
+  (i32.atomic.rmw16.xor_u ;; should be unsigned
+   (i32.const 0)
+   (i32.const 0)
+  )
+ )
+)
+(module
+ (import "fuzzing-support" "log-i32" (func $fimport$0 (param i32)))
+ (memory $0 (shared 1 1))
+ (func "rmw-reads-modifies-and-writes"
+  (drop
+   (i64.atomic.rmw16.and_u offset=4
+    (i32.const 0)
+    (i64.const 65535)
+   )
+  )
+  (call $fimport$0
+   (i32.load8_u
+    (i32.const 5)
+   )
+  )
+ )
+)
+(module
+ (import "fuzzing-support" "log-i32" (func $fimport$0 (param i32)))
+ (memory $0 (shared 1 1))
+ (func "rmw-reads-modifies-and-writes-asymmetrical"
+  (drop
+   (i32.atomic.rmw8.sub_u
+    (i32.const 3)
+    (i32.const 42)
+   )
+  )
+  (call $fimport$0
+   (i32.load8_u
+    (i32.const 3)
+   )
+  )
+ )
+)
diff --git a/test/passes/fuzz-exec_enable-sign-ext.txt b/test/passes/fuzz-exec_enable-sign-ext.txt
deleted file mode 100644
index 6b95234f4..000000000
--- a/test/passes/fuzz-exec_enable-sign-ext.txt
+++ /dev/null
@@ -1,59 +0,0 @@
-[fuzz-exec] calling a
-[fuzz-exec] note result: a => -69
-[fuzz-exec] calling b
-[fuzz-exec] note result: b => -31768
-[fuzz-exec] calling c
-[fuzz-exec] note result: c => -69
-[fuzz-exec] calling d
-[fuzz-exec] note result: d => -31768
-[fuzz-exec] calling e
-[fuzz-exec] note result: e => -2146649112
-(module
- (type $none_=>_i64 (func (result i64)))
- (type $none_=>_i32 (func (result i32)))
- (export "a" (func $a))
- (export "b" (func $b))
- (export "c" (func $c))
- (export "d" (func $d))
- (export "e" (func $e))
- (func $a (result i32)
-  (i32.extend8_s
-   (i32.const 187)
-  )
- )
- (func $b (result i32)
-  (i32.extend16_s
-   (i32.const 33768)
-  )
- )
- (func $c (result i64)
-  (i64.extend8_s
-   (i64.const 187)
-  )
- )
- (func $d (result i64)
-  (i64.extend16_s
-   (i64.const 33768)
-  )
- )
- (func $e (result i64)
-  (i64.extend32_s
-   (i64.const 2148318184)
-  )
- )
-)
-[fuzz-exec] calling a
-[fuzz-exec] note result: a => -69
-[fuzz-exec] calling b
-[fuzz-exec] note result: b => -31768
-[fuzz-exec] calling c
-[fuzz-exec] note result: c => -69
-[fuzz-exec] calling d
-[fuzz-exec] note result: d => -31768
-[fuzz-exec] calling e
-[fuzz-exec] note result: e => -2146649112
-[fuzz-exec] comparing a
-[fuzz-exec] comparing b
-[fuzz-exec] comparing c
-[fuzz-exec] comparing d
-[fuzz-exec] comparing e
diff --git a/test/passes/fuzz-exec_enable-sign-ext.wast b/test/passes/fuzz-exec_enable-sign-ext.wast
deleted file mode 100644
index 08042d2b9..000000000
--- a/test/passes/fuzz-exec_enable-sign-ext.wast
+++ /dev/null
@@ -1,33 +0,0 @@
-(module
- (export "a" (func $a))
- (export "b" (func $b))
- (export "c" (func $c))
- (export "d" (func $d))
- (export "e" (func $e))
- (func $a (result i32)
-  (i32.extend8_s
-   (i32.const 187)
-  )
- )
- (func $b (result i32)
-  (i32.extend16_s
-   (i32.const 33768)
-  )
- )
- (func $c (result i64)
-  (i64.extend8_s
-   (i64.const 187)
-  )
- )
- (func $d (result i64)
-  (i64.extend16_s
-   (i64.const 33768)
-  )
- )
- (func $e (result i64)
-  (i64.extend32_s
-   (i64.const 2148318184)
-  )
- )
-)
-