Subzero. Wasm. Implement sbrk and correctly do bounds checks.

src/WasmTranslator.cpp

Index: src/WasmTranslator.cpp
diff --git a/src/WasmTranslator.cpp b/src/WasmTranslator.cpp
index a3ca88d4d2ba0c68c39ec1780992ad9f8e334ba4..acc2aa0b3ca16bcf43db8fdd0d7599d921fe78e3 100644
--- a/src/WasmTranslator.cpp
+++ b/src/WasmTranslator.cpp
@@ -1065,9 +1065,7 @@ public:
     assert(Module);
     const auto &IndirectTable = Module->function_table;
 
-    // TODO(eholk): This should probably actually call abort instead.
-    auto *Abort = Func->makeNode();
-    Abort->appendInst(InstUnreachable::create(Func));
+    auto *Abort = getAbortTarget();
 
     assert(Args[0].toOperand());
 
@@ -1137,14 +1135,23 @@ public:
 
   Operand *sanitizeAddress(Operand *Base, uint32_t Offset) {
     SizeT MemSize = Module->module->min_mem_pages * WASM_PAGE_SIZE;
-    SizeT MemMask = MemSize - 1;
 
     bool ConstZeroBase = false;
 
     // first, add the index and the offset together.
     if (auto *ConstBase = llvm::dyn_cast<ConstantInteger32>(Base)) {
       uint32_t RealOffset = Offset + ConstBase->getValue();
-      RealOffset &= MemMask;
+      if (RealOffset >= MemSize) {
+        // We've proven this will always be an out of bounds access, so insert
+        // an unconditional trap.
+        Control()->appendInst(InstUnreachable::create(Func));
+        // It doesn't matter what we return here, so return something that will
+        // allow the rest of code generation to happen.
+        //
+        // We might be tempted to just abort translation here, but out of bounds
+        // memory access is a runtime trap, not a compile error.
+        return Ctx->getConstantZero(IceType_i32);

[Jim Stichnoth, 2016/04/23 16:23:04]

Maybe use getPointerType() instead of IceType_i32, to be a bit more
future-proof?

[Eric Holk, 2016/04/25 19:53:03]

Done.

+      }
       Base = Ctx->getConstantInt32(RealOffset);
       ConstZeroBase = (0 == RealOffset);
     } else if (0 != Offset) {
@@ -1156,12 +1163,25 @@ public:
       Base = Addr;
     }
 
+    // Do the bounds check.
+    //
+    // TODO (eholk): Add a command line argument to control whether bounds
+    // checks are inserted, and maybe add a way to duplicate bounds checks to
+    // get a better sense of the overhead.
     if (!llvm::dyn_cast<ConstantInteger32>(Base)) {
-      auto *ClampedAddr = makeVariable(Ice::getPointerType());
+      // TODO (eholk): creating a new basic block on every memory access is
+      // terrible (see https://goto.google.com/aqydy).  Try adding a new

[Jim Stichnoth, 2016/04/23 16:23:04]

Use a link that is externally viewable...

[Eric Holk, 2016/04/25 19:53:03]

I thought goto was, but just to be safe, I switched it to a goo.gl link.

+      // instruction that encapsulates this "abort if false" pattern.
+      auto *CheckPassed = Func->makeNode();
+      auto *CheckFailed = getAbortTarget();
+
+      auto *Check = makeVariable(IceType_i1);
+      Control()->appendInst(InstIcmp::create(Func, InstIcmp::Ult, Check, Base,
+                                             Ctx->getConstantInt32(MemSize)));
       Control()->appendInst(
-          InstArithmetic::create(Func, InstArithmetic::And, ClampedAddr, Base,
-                                 Ctx->getConstantInt32(MemSize - 1)));
-      Base = ClampedAddr;
+          InstBr::create(Func, Check, CheckPassed, CheckFailed));
+
+      *ControlPtr = OperandNode(CheckPassed);
     }
 
     Ice::Operand *RealAddr = nullptr;
@@ -1261,6 +1281,8 @@ private:
   class Cfg *Func;
   GlobalContext *Ctx;
 
+  CfgNode *AbortTarget = nullptr;
+
   SizeT NextArg = 0;
 
   CfgUnorderedMap<Operand *, InstPhi *> PhiMap;
@@ -1297,6 +1319,16 @@ private:
     return Iter->second;
   }
 
+  CfgNode *getAbortTarget() {
+    if (!AbortTarget) {
+      AbortTarget = Func->makeNode();
+      // TODO(eholk): This should probably actually call abort instead.
+      AbortTarget->appendInst(InstUnreachable::create(Func));
+    }
+
+    return AbortTarget;
+  }
+
   template <typename F = std::function<void(Ostream &)>> void log(F Fn) const {
     if (BuildDefs::dump() && (getFlags().getVerbose() & IceV_Wasm)) {
       Fn(Ctx->getStrDump());
@@ -1470,6 +1502,14 @@ void WasmTranslator::translate(
       WritePtr += Seg.source_size;
     }
 
+    // Save the size of the initialized data in a global variable so the runtime
+    // can use it to determine the initial heap break.
+    auto *GlobalDataSize = VariableDeclaration::createExternal(Globals.get());
+    GlobalDataSize->setName(Ctx->getGlobalString("WASM_DATA_SIZE"));
+    GlobalDataSize->addInitializer(VariableDeclaration::DataInitializer::create(
+        Globals.get(), reinterpret_cast<const char *>(&WritePtr),
+        sizeof(WritePtr)));
+
     // Pad the rest with zeros
     SizeT DataSize = Module->min_mem_pages * WASM_PAGE_SIZE;
     if (WritePtr < DataSize) {
@@ -1477,7 +1517,16 @@ void WasmTranslator::translate(
           Globals.get(), DataSize - WritePtr));
     }
 
+    // Save the number of pages for the runtime
+    auto *GlobalNumPages = VariableDeclaration::createExternal(Globals.get());
+    GlobalNumPages->setName(Ctx->getGlobalString("WASM_NUM_PAGES"));
+    GlobalNumPages->addInitializer(VariableDeclaration::DataInitializer::create(
+        Globals.get(), reinterpret_cast<const char *>(&Module->min_mem_pages),
+        sizeof(Module->min_mem_pages)));
+
     Globals->push_back(WasmMemory);
+    Globals->push_back(GlobalDataSize);
+    Globals->push_back(GlobalNumPages);
 
     lowerGlobals(std::move(Globals));
   }