[Clang interpreter] Avoid storing pointers at unaligned locations

[jrtc27]

Summary

The Clang interpreter's bytecode uses a packed stream of bytes
representation, but also wants to have some opcodes take pointers as
arguments, which are currently embedded in the bytecode directly.

However, CHERI, and thus Arm's upcoming experimental Morello prototype,
provide spatial memory safety for C/C++ by implementing language-level
(and sub-language-level) pointers as capabilities, which track bounds,
permissions and validity in hardware. This uses tagged memory with a
single tag bit at every capability-aligned address, and so storing
pointers to unaligned addresses results in the tag being stripped,
leading to a tag fault when the pointer is ultimately dereferenced at a
later point.

In order to support a stricter C/C++ implementation like CHERI, we no
longer store pointers directly in the bytecode, instead storing them in
a table and embedding the index in the bytecode.

[jrtc27]

Reworked code slightly to make it look nicer after clang-format uglified it

[jrtc27]

Is there any way I can usefully test this? As far as I can tell there's only a single constexpr test in the tree that uses the new interpreter, and it's pretty trivial?

[nand]

The patches implementing more features/control flow constructs have not yet been committed, so if the pre-existing test passes, the functionality should be fine. Adjustments can be made later on when those patches are rebased.

clang/lib/AST/Interp/Program.h

51

This works for now, but in the future we might want to have a unique integer - pointer mapping for all types that need to be stored in the bytecode.

clang/lib/AST/Interp/ByteCodeEmitter.cpp

 //===--- ByteCodeEmitter.cpp - Instruction emitter for the VM ---*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "ByteCodeEmitter.h"
 #include "Context.h"
 #include "Opcode.h"
 #include "Program.h"
 #include "clang/AST/DeclCXX.h"
+#include <type_traits>
 
 using namespace clang;
 using namespace clang::interp;
 
 using APSInt = llvm::APSInt;
 using Error = llvm::Error;
 
 Expected<Function *> ByteCodeEmitter::compileFunc(const FunctionDecl *F) {

 }
 
 bool ByteCodeEmitter::bail(const SourceLocation &Loc) {
   if (!BailLocation)
     BailLocation = Loc;
   return false;
 }
 
-template <typename... Tys>
-bool ByteCodeEmitter::emitOp(Opcode Op, const Tys &... Args, const SourceInfo &SI) {
-  bool Success = true;
-
-  /// Helper to write bytecode and bail out if 32-bit offsets become invalid.
-  auto emit = [this, &Success](const char *Data, size_t Size) {
-    if (Code.size() + Size > std::numeric_limits<unsigned>::max()) {
-      Success = false;
-      return;
-    }
-    Code.insert(Code.end(), Data, Data + Size);
-  };
+/// Pointers will be automatically marshalled as 32-bit IDs.
+template <typename T>
+static std::enable_if_t<!std::is_pointer<T>::value, void>
+emit(Program &P, std::vector<char> &Code, const T &Val, bool &Success) {
+  size_t Size = sizeof(Val);
+  if (Code.size() + Size > std::numeric_limits<unsigned>::max()) {
+    Success = false;
+    return;
+  }
+
+  const char *Data = reinterpret_cast<const char *>(&Val);
+  Code.insert(Code.end(), Data, Data + Size);
+}
+
+template <typename T>
+static std::enable_if_t<std::is_pointer<T>::value, void>
+emit(Program &P, std::vector<char> &Code, const T &Val, bool &Success) {
+  size_t Size = sizeof(uint32_t);
+
+  uint32_t ID = P.getOrCreateNativePointer(Val);
+  const char *Data = reinterpret_cast<const char *>(&ID);
+}
+
+template <typename... Tys>
+bool ByteCodeEmitter::emitOp(Opcode Op, const Tys &... Args, const SourceInfo &SI) {
+  bool Success = true;
 
   /// The opcode is followed by arguments. The source info is
   /// attached to the address after the opcode.
-  emit(reinterpret_cast<const char *>(&Op), sizeof(Opcode));
+  emit(P, Code, Op, Success);
   if (SI)
     SrcMap.emplace_back(Code.size(), SI);
 
   /// The initializer list forces the expression to be evaluated
   /// for each argument in the variadic template, in order.
-  (void)std::initializer_list<int>{
-      (emit(reinterpret_cast<const char *>(&Args), sizeof(Args)), 0)...};
+  (void)std::initializer_list<int>{(emit(P, Code, Args, Success), 0)...};
 
   return Success;
 }
 
 bool ByteCodeEmitter::jumpTrue(const LabelTy &Label) {
   return emitJt(getOffset(Label), SourceInfo{});
 }
 

clang/lib/AST/Interp/Disasm.cpp

 #include "Program.h"
 #include "clang/AST/DeclCXX.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Format.h"
 
 using namespace clang;
 using namespace clang::interp;
 
+template <typename T>
+inline std::enable_if_t<!std::is_pointer<T>::value, T> ReadArg(Program &P,
+                                                               CodePtr OpPC) {
+  return OpPC.read<T>();
+}
+
+template <typename T>
+inline std::enable_if_t<std::is_pointer<T>::value, T> ReadArg(Program &P,
+                                                              CodePtr OpPC) {
+  uint32_t ID = OpPC.read<uint32_t>();
+  return reinterpret_cast<T>(P.getNativePointer(ID));
+}
+
 LLVM_DUMP_METHOD void Function::dump() const { dump(llvm::errs()); }
 
 LLVM_DUMP_METHOD void Function::dump(llvm::raw_ostream &OS) const {
   if (F) {
     if (auto *Cons = dyn_cast<CXXConstructorDecl>(F)) {
       DeclarationName Name = Cons->getParent()->getDeclName();
       OS << Name << "::" << Name << ":\n";
     } else {

clang/lib/AST/Interp/Interp.h

 //===--- Interp.h - Interpreter for the constexpr VM ------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Definition of the interpreter state and entry point.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_AST_INTERP_INTERP_H
 #define LLVM_CLANG_AST_INTERP_INTERP_H
 
-#include <limits>
-#include <vector>
 #include "Function.h"
 #include "InterpFrame.h"
 #include "InterpStack.h"
 #include "InterpState.h"
 #include "Opcode.h"
 #include "PrimType.h"
 #include "Program.h"
 #include "State.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/ASTDiagnostic.h"
 #include "clang/AST/CXXInheritance.h"
 #include "clang/AST/Expr.h"
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/APSInt.h"
 #include "llvm/Support/Endian.h"
+#include <limits>
+#include <type_traits>
+#include <vector>
 
 namespace clang {
 namespace interp {
 
 using APInt = llvm::APInt;
 using APSInt = llvm::APSInt;
 
 /// Convers a value to an APValue.

 }
 
 inline bool ExpandPtr(InterpState &S, CodePtr OpPC) {
   const Pointer &Ptr = S.Stk.pop<Pointer>();
   S.Stk.push<Pointer>(Ptr.expand());
   return true;
 }
 
+//===----------------------------------------------------------------------===//
+// Read opcode arguments
+//===----------------------------------------------------------------------===//
+
+template <typename T>
+inline std::enable_if_t<!std::is_pointer<T>::value, T> ReadArg(InterpState &S,
+                                                               CodePtr OpPC) {
+  return OpPC.read<T>();
+}
+
+template <typename T>
+inline std::enable_if_t<std::is_pointer<T>::value, T> ReadArg(InterpState &S,
+                                                              CodePtr OpPC) {
+  uint32_t ID = OpPC.read<uint32_t>();
+  return reinterpret_cast<T>(S.P.getNativePointer(ID));
+}
+
 /// Interpreter entry point.
 bool Interpret(InterpState &S, APValue &Result);
 
 } // namespace interp
 } // namespace clang
 
 #endif

clang/lib/AST/Interp/Program.h

 class Record;
 class Scope;
 
 /// The program contains and links the bytecode for all functions.
 class Program {
 public:
   Program(Context &Ctx) : Ctx(Ctx) {}
 
+  /// Marshals a native pointer to an ID for embedding in bytecode.
+  unsigned getOrCreateNativePointer(const void *Ptr);
+
+  /// Returns the value of a marshalled native pointer.
+  const void *getNativePointer(unsigned Idx);
+
   /// Emits a string literal among global data.
   unsigned createGlobalString(const StringLiteral *S);
 
   /// Returns a pointer to a global.
   Pointer getPtrGlobal(unsigned Idx);
 
   /// Returns the value of a global.
   Block *getGlobal(unsigned Idx) {
private:
   /// Mapping from decls to cached bytecode functions.
   llvm::DenseMap<const FunctionDecl *, std::unique_ptr<Function>> Funcs;
   /// List of anonymous functions.
   std::vector<std::unique_ptr<Function>> AnonFuncs;
 
   /// Function relocation locations.
   llvm::DenseMap<const FunctionDecl *, std::vector<unsigned>> Relocs;
 
+  /// Native pointers referenced by bytecode.
+  std::vector<const void *> NativePointers;
+  /// Cached native pointer indices.
+  llvm::DenseMap<const void *, unsigned> NativePointerIndices;
+
   /// Custom allocator for global storage.
   using PoolAllocTy = llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator>;
 
   /// Descriptor + storage for a global object.
   ///
   /// Global objects never go out of scope, thus they do not track pointers.
   class Global {
   public:

clang/lib/AST/Interp/Program.cpp

 #include "Opcode.h"
 #include "PrimType.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclCXX.h"
 
 using namespace clang;
 using namespace clang::interp;
 
+unsigned Program::getOrCreateNativePointer(const void *Ptr) {
+  auto It = NativePointerIndices.find(Ptr);
+  if (It != NativePointerIndices.end())
+    return It->second;
+
+  unsigned Idx = NativePointers.size();
+  NativePointers.push_back(Ptr);
+  NativePointerIndices[Ptr] = Idx;
+  return Idx;
+}
+
+const void *Program::getNativePointer(unsigned Idx) {
+  return NativePointers[Idx];
+}
+
 unsigned Program::createGlobalString(const StringLiteral *S) {
   const size_t CharWidth = S->getCharByteWidth();
   const size_t BitWidth = CharWidth * Ctx.getCharBit();
 
   PrimType CharType;
   switch (CharWidth) {
   case 1:
     CharType = PT_Sint8;

clang/lib/AST/Interp/Source.h

public:
   CodePtr operator-(size_t RHS) const {
     assert(Ptr != nullptr && "Invalid code pointer");
     return CodePtr(Ptr - RHS);
   }
 
   bool operator!=(const CodePtr &RHS) const { return Ptr != RHS.Ptr; }
 
   /// Reads data and advances the pointer.
-  template <typename T> T read() {
-    T Value = ReadHelper<T>(Ptr);
+  template <typename T> std::enable_if_t<!std::is_pointer<T>::value, T> read() {
+    using namespace llvm::support;
+    T Value = endian::read<T, endianness::native, 1>(Ptr);
     Ptr += sizeof(T);
     return Value;
   }
 
 private:
   /// Constructor used by Function to generate pointers.
   CodePtr(const char *Ptr) : Ptr(Ptr) {}
 
-  /// Helper to decode a value or a pointer.
-  template <typename T>
-  static std::enable_if_t<!std::is_pointer<T>::value, T>
-  ReadHelper(const char *Ptr) {
-    using namespace llvm::support;
-    return endian::read<T, endianness::native, 1>(Ptr);
-  }
-
-  template <typename T>
-  static std::enable_if_t<std::is_pointer<T>::value, T>
-  ReadHelper(const char *Ptr) {
-    using namespace llvm::support;
-    auto Punned = endian::read<uintptr_t, endianness::native, 1>(Ptr);
-    return reinterpret_cast<T>(Punned);
-  }
-
 private:
   friend class Function;
 
   /// Pointer into the code owned by a function.
   const char *Ptr;
 };
 
 /// Describes the statement/declaration an opcode was generated from.

clang/utils/TableGen/ClangOpcodesEmitter.cpp

Enumerate(R, N, [this, R, &OS, &N](ArrayRef<Record *> TS, const Twine &ID) {
     auto Args = R->getValueAsListOfDefs("Args");
 
     OS << "case OP_" << ID << ": {\n";
 
     // Emit calls to read arguments.
     for (size_t I = 0, N = Args.size(); I < N; ++I) {
       OS << "  auto V" << I;
       OS << " = ";
-      OS << "PC.read<" << Args[I]->getValueAsString("Name") << ">();\n";
+      OS << "ReadArg<" << Args[I]->getValueAsString("Name") << ">(S, PC);\n";
     }
 
     // Emit a call to the template method and pass arguments.
     OS << "  if (!" << N;
     PrintTypes(OS, TS);
     OS << "(S";
     if (ChangesPC)
       OS << ", PC";

 
 void ClangOpcodesEmitter::EmitDisasm(raw_ostream &OS, StringRef N, Record *R) {
   OS << "#ifdef GET_DISASM\n";
   Enumerate(R, N, [R, &OS](ArrayRef<Record *>, const Twine &ID) {
     OS << "case OP_" << ID << ":\n";
     OS << "  PrintName(\"" << ID << "\");\n";
     OS << "  OS << \"\\t\"";
 
-    for (auto *Arg : R->getValueAsListOfDefs("Args"))
-      OS << " << PC.read<" << Arg->getValueAsString("Name") << ">() << \" \"";
+    for (auto *Arg : R->getValueAsListOfDefs("Args")) {
+      OS << " << ReadArg<" << Arg->getValueAsString("Name") << ">(P, PC)";
+      OS << " << \" \"";
+    }
 
     OS << " << \"\\n\";\n";
     OS << "  continue;\n";
   });
   OS << "#endif\n";
 }
 
 void ClangOpcodesEmitter::EmitEmitter(raw_ostream &OS, StringRef N, Record *R) {