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

src/WasmTranslator.cpp

 //===- subzero/src/WasmTranslator.cpp - WASM to Subzero Translation -------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 1047 matching lines @@
     LOG(out << "Call Result = " << Node(Dest) << "\n");
     return OperandNode(Dest);
   }
   Node CallIndirect(uint32_t SigIndex, Node *Args) {
     LOG(out << "CallIndirect(" << SigIndex << ")\n");
     // TODO(eholk): Compile to something better than a switch.
     const auto *Module = this->Module->module;
     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());
 
     auto *Switch = InstSwitch::create(Func, IndirectTable.size(),
                                       Args[0].toOperand(), Abort);
     assert(Abort);
 
     const bool HasReturn = Module->signatures[SigIndex]->return_count() != 0;
     const Ice::Type DestTy =
         HasReturn ? toIceType(Module->signatures[SigIndex]->GetReturn())
@@ skipping 49 matching lines @@
     llvm::report_fatal_error("LoadGlobal");
   }
   Node StoreGlobal(uint32_t Index, Node Val) {
     (void)Index;
     (void)Val;
     llvm::report_fatal_error("StoreGlobal");
   }
 
   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 Base;

[Jim Stichnoth, 2016/04/22 20:48:54]

Another possibility is GlobalContext::getConstantZero() - your call.

[Eric Holk, 2016/04/22 22:32:48]

Returning 0 is better. It means that even this dereference manages to happen
somehow it will still trap by being a null pointer dereference.

Done.

+      }
       Base = Ctx->getConstantInt32(RealOffset);
       ConstZeroBase = (0 == RealOffset);
     } else if (0 != Offset) {
       auto *Addr = makeVariable(Ice::getPointerType());
       auto *OffsetConstant = Ctx->getConstantInt32(Offset);
       Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Add,
                                                    Addr, Base, OffsetConstant));
 
       Base = Addr;
     }
 
+    // Do the bounds check.

[Jim Stichnoth, 2016/04/22 20:48:54]

Maybe in a separate CL, but can you add a flag to allow suppressing the bounds
check?  This would be for perf-testing its impact.

Even better, make the flag be numeric instead of boolean, so that we could mock
the effect of having to make 2 (or more!) cmp/br operations per bounds check.

[Eric Holk, 2016/04/22 22:32:48]

I added a TODO.

     if (!llvm::dyn_cast<ConstantInteger32>(Base)) {
-      auto *ClampedAddr = makeVariable(Ice::getPointerType());
+      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);

[Jim Stichnoth, 2016/04/22 20:48:54]

This one is definitely for a separate CL.

I think it's going to be a big problem if every memory access effectively
creates a new basic block.

- Liveness analysis cost increases with the number of nodes.

- A number of low-cost optimizations are suppressed on variables with
multi-block live ranges.  Splitting "natural" blocks because of memory accesses
reduces the number of such opportunities.

To make this work, you might need to introduce a new flavor of InstBr.  There is
already one flavor for conditional branches, and one for unconditional.  The
third flavor would be an intra-block branch to a CfgNode, and this flavor of
branch would not be considered a terminator instruction.  (Actually, maybe that
should be a new instruction type separate from InstBr, to make it easier to roll
in.)

This assumes that the AbortTarget node unconditionally leaves the function and
doesn't have any out-edges to other nodes in this function.  Otherwise we might
have to make changes to liveness analysis.

One last point - in this approach, the AbortTarget wouldn't have any explicit
in-edges, so care would have to be taken that the node doesn't get removed for
being "unreachable".

[Eric Holk, 2016/04/22 22:32:48]

I added a TODO, with a link to this comment.

     }
 
     Ice::Operand *RealAddr = nullptr;
     auto MemBase = Ctx->getConstantSym(0, Ctx->getGlobalString("WASM_MEMORY"));
     if (!ConstZeroBase) {
       auto RealAddrV = Func->makeVariable(Ice::getPointerType());
       Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Add,
                                                    RealAddrV, Base, MemBase));
 
       RealAddr = RealAddrV;
@@ skipping 79 matching lines @@
   void set_effect_ptr(Node *Effect) { this->EffectPtr = Effect; }
 
 private:
   wasm::ModuleEnv *Module;
   Node *ControlPtr;
   Node *EffectPtr;
 
   class Cfg *Func;
   GlobalContext *Ctx;
 
+  CfgNode *AbortTarget = nullptr;
+
   SizeT NextArg = 0;
 
   CfgUnorderedMap<Operand *, InstPhi *> PhiMap;
   CfgUnorderedMap<Operand *, CfgNode *> DefNodeMap;
 
   InstPhi *getDefiningInst(Operand *Op) const {
     const auto &Iter = PhiMap.find(Op);
     if (Iter == PhiMap.end()) {
       return nullptr;
     }
@@ skipping 16 matching lines @@
   }
 
   CfgNode *getDefNode(Operand *Op) const {
     const auto &Iter = DefNodeMap.find(Op);
     if (Iter == DefNodeMap.end()) {
       return nullptr;
     }
     return Iter->second;
   }
 
+  CfgNode *getAbortTarget() {

[Karl, 2016/04/22 19:18:14]

Does this need an atomic or a mutex to avoid multiple generations.

You should be able to do this using an "std::atomic_bool createAbortTarget;",
initialize it to true, and then use:

   if (!AbortTarget) {
     if (createAbortTarget.exchange(false)) {
       ... create abort target
     }
   }

[Jim Stichnoth, 2016/04/22 20:48:54]

I don't think there's any concurrency at this level, so atomics should be
unnecessary.

[Eric Holk, 2016/04/22 21:02:10]

I think unless we have plans to parallelize Wasm decoding as finer granularity
than per function that there's no reason to do this.

The IceBuilder that contains this abort target is created and destroyed for each
function that is translated (see WasmTranslator::translateFunction around line
1343). There shouldn't be any way for this data to be shared between threads.

+    if (!AbortTarget) {
+      AbortTarget = Func->makeNode();

[Jim Stichnoth, 2016/04/22 20:48:54]

I think it's best if you can somehow force this node to be at the end of the
linearization list.  Or maybe it will just happen naturally during a
re-linearization pass?

[Eric Holk, 2016/04/22 22:32:48]

Do you know a good strategy for doing this off hand?

This node currently ends up somewhere in the middle of the function.

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

I would probably just do a post-pass that heavy-handedly moves it to the end of
the node vector, making sure to properly renumber the nodes.

Leave it as a TODO for now. :)

+      // 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());
       Ctx->getStrDump().flush();
     }
   }
 };
 
 std::unique_ptr<Cfg> WasmTranslator::translateFunction(Zone *Zone,
                                                        FunctionBody &Body) {
@@ skipping 153 matching lines @@
 
       // Add the data
       WasmMemory->addInitializer(VariableDeclaration::DataInitializer::create(
           Globals.get(), reinterpret_cast<const char *>(Module->module_start) +
                              Seg.source_offset,
           Seg.source_size));
 
       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) {
       WasmMemory->addInitializer(VariableDeclaration::ZeroInitializer::create(
           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));
   }
 
   // Translate each function.
   for (const auto Fn : Module->functions) {
     const auto FnName = getFunctionName(Module, Fn.func_index);
 
     LOG(out << "  " << Fn.func_index << ": " << FnName << "...");
 
     Body.sig = Fn.sig;
     Body.base = Buffer.get();
     Body.start = Buffer.get() + Fn.code_start_offset;
     Body.end = Buffer.get() + Fn.code_end_offset;
 
     auto Func = translateFunction(&Zone, Body);
     Func->setFunctionName(Ctx->getGlobalString(FnName));
 
     Ctx->optQueueBlockingPush(makeUnique<CfgOptWorkItem>(std::move(Func)));
     LOG(out << "done.\n");
   }
 
   return;
 }
 
 #endif // ALLOW_WASM