[lldb-test] Add a testing harness for the JIT's IRMemoryMap

[vsk]

Summary

This teaches lldb-test how to launch a process, set up an IRMemoryMap,
and issue memory allocations in the target process through the map. This
makes it possible to test IRMemoryMap in a targeted way.

This has uncovered two bugs so far. The first bug is that Malloc
performs an adjustment on the pointer returned from AllocateMemory (for
alignment purposes) which ultimately allows overlapping memory regions
to be created. The second bug is that after most of the address space on
the host side is exhausted, Malloc may return the same address multiple
times. These bugs (and hopefully more!) can be uncovered and tested for
with targeted lldb-test commands.

At an even higher level, the motivation for addressing these bugs is
that they can lead to strange user-visible failures (e.g, variables
assume the wrong value during expression evaluation, or the debugger
crashes). See my third comment on this swift-lldb PR for an example:

https://github.com/apple/swift-lldb/pull/652

I hope lldb-test is the right place to add this testing harness. Setting
up a gtest-style unit test proved too cumbersome (you need to recreate
or mock way too much debugger state), as did writing end-to-end tests
(it's hard to write a test that actually hits a buggy path).

With lldb-test, it's easy to read/generate the test input and parse the
test output. I'll attach a simple "fuzz" tester which generates failing
test cases to the Phab review. Here's an example:

Command: malloc(size=1024, alignment=32)
Malloc: address = 0xca000
Command: malloc(size=64, alignment=16)
Malloc: address = 0xca400
Command: malloc(size=1024, alignment=16)
Malloc: address = 0xca440
Command: malloc(size=16, alignment=8)
Malloc: address = 0xca840
Command: malloc(size=2048, alignment=16)
Malloc: address = 0xcb000
Command: malloc(size=64, alignment=32)
Malloc: address = 0xca860
Command: malloc(size=1024, alignment=16)
Malloc: address = 0xca890
Malloc error: overlapping allocation detected, previous allocation at [0xca860, 0xca8a0)

fuzz_malloc.py835 BDownload

[labath]

The idea that came to me while looking at this is testing this gdb-client style. This would allow you to mock the server responses to allocation and e.g. test handling of allocation failures. However, the problem is these tests sit on top of SBAPI and there seems to be no way to issue "raw" allocation requests through that (although maybe there is a case to be made for SBProcess.AllocateMemory as a generally useful API).

However, if this does the job you want, then I'm fine with that too.

tools/lldb-test/lldb-test.cpp

509

is Line null-terminated here? Also a size_t arg should have a %zu modifier, but I am not sure if all msvc versions support that. It might be best to make the type uint64_t and then use SCNu64.

542–548

It looks like this won't detect the case when a larger interval is placed on top of a smaller one (e.g. 0x1000-0x4000 and 0x2000-0x3000).

[vsk]

• Use %zu, and improve detection of overlapping allocations.

tools/lldb-test/lldb-test.cpp

509

Yes, Line is null-terminated because MemoryBuffer::getFileOrSTDIN defaults to adding a null terminator.

509

LLVM currently requires MSVC >= 2015 Update 3 (see: https://reviews.llvm.org/D47073), which supports %zu (see: https://blogs.msdn.microsoft.com/vcblog/2014/06/03/visual-studio-14-ctp/#div-comment-77743). I'll just use %zu.

542–548

Thanks for pointing this out. I wasn't sure how to do this efficiently. Taking another look at things, it looks like IntervalMap surfaces iterators which can be used to scan a range quickly. I'll try that out.

[vsk]

• Really fix the allocation overlap test. The previous version of this patch would not detect overlaps in which the end of the new allocation is contained within an existing allocation.

The idea that came to me while looking at this is testing this gdb-client style. This would allow you to mock the server responses to allocation and e.g. test handling of allocation failures. However, the problem is these tests sit on top of SBAPI and there seems to be no way to issue "raw" allocation requests through that (although maybe there is a case to be made for SBProcess.AllocateMemory as a generally useful API).

However, if this does the job you want, then I'm fine with that too.

Testing at this level looks to be sufficient to uncover the bugs I'm concerned about, so I'd prefer not to extend the SB API if possible.

[labath]

Thank you for making the changes. This looks fine to me. The more testing, the better.

tools/lldb-test/lldb-test.cpp

534

%x is not right here. Maybe use formatv?

lit/Expr/TestIRMemoryMap.test

+# RUN: %cxx %p/Inputs/call-function.cpp -g -o %t
+# RUN: lldb-test ir-memory-map %t %s
+
+malloc 0 1
+malloc 1 1
+
+malloc 2 1
+malloc 2 2
+malloc 2 4
+
+malloc 3 1
+malloc 3 2
+malloc 3 4
+
+malloc 128 1
+malloc 128 2
+malloc 128 4
+malloc 128 128
+
+malloc 2048 1
+malloc 2048 2
+malloc 2048 4
+
+malloc 3968 1
+malloc 3968 2
+malloc 3968 4
+
+malloc 0 1

source/Target/Process.cpp

if (!error.Success())
       break;
   }
   return error;
 }
 
 #define USE_ALLOCATE_MEMORY_CACHE 1
 addr_t Process::AllocateMemory(size_t size, uint32_t permissions,
                                Status &error) {
-  if (GetPrivateState() != eStateStopped)
+  if (GetPrivateState() != eStateStopped) {
+    error.SetErrorToGenericError();
     return LLDB_INVALID_ADDRESS;
+  }
 
 #if defined(USE_ALLOCATE_MEMORY_CACHE)
   return m_allocated_memory_cache.AllocateMemory(size, permissions, error);
 #else
   addr_t allocated_addr = DoAllocateMemory(size, permissions, error);
   Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_PROCESS));
   if (log)
     log->Printf("Process::AllocateMemory(size=%" PRIu64

tools/lldb-test/lldb-test.cpp

 #include "FormatUtil.h"
 #include "SystemInitializerTest.h"
 
 #include "Plugins/SymbolFile/DWARF/SymbolFileDWARF.h"
 #include "lldb/Breakpoint/BreakpointLocation.h"
 #include "lldb/Core/Debugger.h"
 #include "lldb/Core/Module.h"
 #include "lldb/Core/Section.h"
+#include "lldb/Expression/IRMemoryMap.h"
 #include "lldb/Initialization/SystemLifetimeManager.h"
 #include "lldb/Interpreter/CommandInterpreter.h"
 #include "lldb/Interpreter/CommandReturnObject.h"
 #include "lldb/Symbol/ClangASTContext.h"
 #include "lldb/Symbol/ClangASTImporter.h"
 #include "lldb/Symbol/SymbolVendor.h"
 #include "lldb/Symbol/TypeList.h"
 #include "lldb/Symbol/VariableList.h"
+#include "lldb/Target/Process.h"
+#include "lldb/Target/Target.h"
 #include "lldb/Utility/CleanUp.h"
 #include "lldb/Utility/DataExtractor.h"
 #include "lldb/Utility/StreamString.h"
 
+#include "llvm/ADT/IntervalMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Support/MathExtras.h"
 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/PrettyStackTrace.h"
 #include "llvm/Support/Signals.h"
 #include "llvm/Support/WithColor.h"
+#include <cstdio>
 #include <thread>
 
 using namespace lldb;
 using namespace lldb_private;
 using namespace llvm;
 
 namespace opts {
+
 static cl::SubCommand BreakpointSubcommand("breakpoints",
                                            "Test breakpoint resolution");
 cl::SubCommand ModuleSubcommand("module-sections",
                                 "Display LLDB Module Information");
 cl::SubCommand SymbolsSubcommand("symbols", "Dump symbols for an object file");
+cl::SubCommand IRMemoryMapSubcommand("ir-memory-map", "Test IRMemoryMap");
+cl::opt<std::string> Log("log", cl::desc("Path to a log file"), cl::init(""),
+                         cl::sub(IRMemoryMapSubcommand));
+
+/// Create a target using the file pointed to by \p Filename, or abort.
+TargetSP createTarget(Debugger &Dbg, const std::string &Filename);
+
+/// Read \p Filename into a null-terminated buffer, or abort.
+std::unique_ptr<MemoryBuffer> openFile(const std::string &Filename);
 
 namespace breakpoint {
 static cl::opt<std::string> Target(cl::Positional, cl::desc("<target>"),
                                    cl::Required, cl::sub(BreakpointSubcommand));
 static cl::opt<std::string> CommandFile(cl::Positional,
                                         cl::desc("<command-file>"),
                                         cl::init("-"),
                                         cl::sub(BreakpointSubcommand));

 static Error findFunctions(lldb_private::Module &Module);
 static Error findNamespaces(lldb_private::Module &Module);
 static Error findTypes(lldb_private::Module &Module);
 static Error findVariables(lldb_private::Module &Module);
 static Error dumpModule(lldb_private::Module &Module);
 
 static int dumpSymbols(Debugger &Dbg);
 }
+
+namespace irmemorymap {
+static cl::opt<std::string> Target(cl::Positional, cl::desc("<target>"),
+                                   cl::Required,
+                                   cl::sub(IRMemoryMapSubcommand));
+static cl::opt<std::string> CommandFile(cl::Positional,
+                                        cl::desc("<command-file>"),
+                                        cl::init("-"),
+                                        cl::sub(IRMemoryMapSubcommand));
+using AllocationT = std::pair<addr_t, addr_t>;
+bool areAllocationsOverlapping(const AllocationT &L, const AllocationT &R);
+using AddrIntervalMap =
+      IntervalMap<addr_t, bool, 8, IntervalMapHalfOpenInfo<addr_t>>;
+bool evalMalloc(IRMemoryMap &IRMemMap, StringRef Line,
+                AddrIntervalMap &AllocatedIntervals);
+int evaluateMemoryMapCommands(Debugger &Dbg);
+} // namespace irmemorymap
+
 } // namespace opts
 
+TargetSP opts::createTarget(Debugger &Dbg, const std::string &Filename) {
+  TargetSP Target;
+  Status ST =
+      Dbg.GetTargetList().CreateTarget(Dbg, Filename, /*triple*/ "",
+                                       /*get_dependent_modules*/ false,
+                                       /*platform_options*/ nullptr, Target);
+  if (ST.Fail()) {
+    errs() << formatv("Failed to create target '{0}: {1}\n", Filename, ST);
+    exit(1);
+  }
+  return Target;
+}
+
+std::unique_ptr<MemoryBuffer> opts::openFile(const std::string &Filename) {
+  auto MB = MemoryBuffer::getFileOrSTDIN(Filename);
+  if (!MB) {
+    errs() << formatv("Could not open file '{0}: {1}\n", Filename,
+                      MB.getError().message());
+    exit(1);
+  }
+  return std::move(*MB);
+}
+
 void opts::breakpoint::dumpState(const BreakpointList &List, LinePrinter &P) {
   P.formatLine("{0} breakpoint{1}", List.GetSize(), plural(List.GetSize()));
   if (List.GetSize() > 0)
     P.formatLine("At least one breakpoint.");
   for (size_t i = 0, e = List.GetSize(); i < e; ++i) {
     BreakpointSP BP = List.GetBreakpointAtIndex(i);
     P.formatLine("Breakpoint ID {0}:", BP->GetID());
     AutoIndent Indent(P, 2);

 
 std::string opts::breakpoint::substitute(StringRef Cmd) {
   std::string Result;
   raw_string_ostream OS(Result);
   while (!Cmd.empty()) {
     switch (Cmd[0]) {
     case '%':
       if (Cmd.consume_front("%p") && (Cmd.empty() || !isalnum(Cmd[0]))) {
-        OS << sys::path::parent_path(CommandFile);
+        OS << sys::path::parent_path(breakpoint::CommandFile);
         break;
       }
       // fall through
     default:
       size_t pos = Cmd.find('%');
       OS << Cmd.substr(0, pos);
       Cmd = Cmd.substr(pos);
       break;
     }
   }
   return std::move(OS.str());
 }
 
 int opts::breakpoint::evaluateBreakpoints(Debugger &Dbg) {
-  TargetSP Target;
-  Status ST =
-      Dbg.GetTargetList().CreateTarget(Dbg, breakpoint::Target, /*triple*/ "",
-                                       /*get_dependent_modules*/ false,
-                                       /*platform_options*/ nullptr, Target);
-  if (ST.Fail()) {
-    errs() << formatv("Failed to create target '{0}: {1}\n", breakpoint::Target,
-                      ST);
-    exit(1);
-  }
-
-  auto MB = MemoryBuffer::getFileOrSTDIN(CommandFile);
-  if (!MB) {
-    errs() << formatv("Could not open file '{0}: {1}\n", CommandFile,
-                      MB.getError().message());
-    exit(1);
-  }
+  TargetSP Target = opts::createTarget(Dbg, breakpoint::Target);
+  std::unique_ptr<MemoryBuffer> MB = opts::openFile(breakpoint::CommandFile);
 
   LinePrinter P(4, outs());
-  StringRef Rest = (*MB)->getBuffer();
+  StringRef Rest = MB->getBuffer();
   int HadErrors = 0;
   while (!Rest.empty()) {
     StringRef Line;
     std::tie(Line, Rest) = Rest.split('\n');
     Line = Line.ltrim();
     if (Line.empty() || Line[0] == '#')
       continue;
 
for (size_t I = 0; I < Count; ++I) {
         Printer.formatBinary("Data: ", Bytes, 0);
       }
       Printer.NewLine();
     }
   }
   return HadErrors;
 }
 
+/// Check if two half-open intervals intersect:
+///   http://world.std.com/~swmcd/steven/tech/interval.html
+bool areAllocationsOverlapping(const AllocationT &L, const AllocationT &R) {
+  return R.first < L.second && L.first < R.second;
+}
+
+bool opts::irmemorymap::evalMalloc(IRMemoryMap &IRMemMap, StringRef Line,
+                                   AddrIntervalMap &AllocatedIntervals) {
+  // ::= malloc <size> <alignment>
+  size_t Size;
+  uint8_t Alignment;
+  int Matches = sscanf(Line.data(), "malloc %zu %hhu", &Size, &Alignment);
+  if (Matches != 2)
+    return false;
+
+  outs() << formatv("Command: malloc(size={0}, alignment={1})\n", Size,
+                    Alignment);
+  if (!isPowerOf2_32(Alignment)) {
+    outs() << "Malloc error: alignment is not a power of 2\n";
+    exit(1);
+  }
+
+  // Issue the malloc in the target process with "-rw" permissions.
+  const uint32_t Permissions = 0x3;
+  const bool ZeroMemory = false;
+  IRMemoryMap::AllocationPolicy Policy =
+      IRMemoryMap::eAllocationPolicyProcessOnly;
+  Status ST;
+  addr_t Addr =
+      IRMemMap.Malloc(Size, Alignment, Permissions, Policy, ZeroMemory, ST);
+  if (ST.Fail()) {
+    outs() << formatv("Malloc error: {0}\n", ST);
+    return true;
+  }
+
+  // Print the result of the allocation before checking its validity.
+  outs() << format("Malloc: address = 0x%x\n", Addr);
+
+  // Check that the allocation is aligned.
+  if (!Addr || Addr % Alignment != 0) {
+    outs() << "Malloc error: zero or unaligned allocation detected\n";
+    exit(1);
+  }
+
+  // Check that the allocation does not overlap another allocation. Do so by
+  // testing each allocation which may cover the interval [Addr, EndOfRegion).
+  addr_t EndOfRegion = Addr + Size;
+  auto Probe = AllocatedIntervals.begin();
+  Probe.advanceTo(Addr); //< First interval s.t stop >= Addr.
+  AllocationT NewAllocation = {Addr, EndOfRegion};
+  auto End = AllocatedIntervals.begin();
+  End.advanceTo(EndOfRegion); //< First interval s.t stop >= EndOfRegion.
+  while (Probe != End) {
+    AllocationT ProbeAllocation = {Probe.start(), Probe.stop()};
+    if (areAllocationsOverlapping(ProbeAllocation, NewAllocation)) {
+      outs() << "Malloc error: overlapping allocation detected"
+             << format(", previous allocation at [0x%x, 0x%x)\n", Probe.start(),
+                       Probe.stop());
+      exit(1);
+    }
+    ++Probe;
+  }
+
+  // Insert the new allocation into the interval map.
+  if (Size)
+    AllocatedIntervals.insert(Addr, EndOfRegion, true);
+
+  return true;
+}
+
+int opts::irmemorymap::evaluateMemoryMapCommands(Debugger &Dbg) {
+  // Set up a Target.
+  TargetSP Target = opts::createTarget(Dbg, irmemorymap::Target);
+
+  // Set up a Process. In order to allocate memory within a target, this
+  // process must be alive and must support JIT'ing.
+  CommandReturnObject Result;
+  Dbg.SetAsyncExecution(false);
+  CommandInterpreter &CI = Dbg.GetCommandInterpreter();
+  auto IssueCmd = [&](const char *Cmd) -> bool {
+    return CI.HandleCommand(Cmd, eLazyBoolNo, Result);
+  };
+  if (!IssueCmd("b main") || !IssueCmd("run")) {
+    outs() << formatv("Failed: {0}\n", Result.GetErrorData());
+    exit(1);
+  }
+
+  ProcessSP Process = Target->GetProcessSP();
+  if (!Process || !Process->IsAlive() || !Process->CanJIT()) {
+    outs() << "Cannot use process to test IRMemoryMap\n";
+    exit(1);
+  }
+
+  // Set up an IRMemoryMap and associated testing state.
+  IRMemoryMap IRMemMap(Target);
+  AddrIntervalMap::Allocator AIMapAllocator;
+  AddrIntervalMap AllocatedIntervals(AIMapAllocator);
+
+  // Parse and apply commands from the command file.
+  std::unique_ptr<MemoryBuffer> MB = opts::openFile(irmemorymap::CommandFile);
+  StringRef Rest = MB->getBuffer();
+  while (!Rest.empty()) {
+    StringRef Line;
+    std::tie(Line, Rest) = Rest.split('\n');
+    Line = Line.ltrim();
+
+    if (Line.empty() || Line[0] == '#')
+      continue;
+
+    if (evalMalloc(IRMemMap, Line, AllocatedIntervals))
+      continue;
+
+    errs() << "Could not parse line: " << Line << "\n";
+    exit(1);
+  }
+  return 0;
+}
+
 int main(int argc, const char *argv[]) {
   StringRef ToolName = argv[0];
   sys::PrintStackTraceOnErrorSignal(ToolName);
   PrettyStackTraceProgram X(argc, argv);
   llvm_shutdown_obj Y;
 
   cl::ParseCommandLineOptions(argc, argv, "LLDB Testing Utility\n");
 
   SystemLifetimeManager DebuggerLifetime;
   DebuggerLifetime.Initialize(llvm::make_unique<SystemInitializerTest>(),
                               nullptr);
   CleanUp TerminateDebugger([&] { DebuggerLifetime.Terminate(); });
 
   auto Dbg = lldb_private::Debugger::CreateInstance();
 
+  if (!opts::Log.empty())
+    Dbg->EnableLog("lldb", {"all"}, opts::Log, 0, errs());
+
   if (opts::BreakpointSubcommand)
     return opts::breakpoint::evaluateBreakpoints(*Dbg);
   if (opts::ModuleSubcommand)
     return dumpModules(*Dbg);
   if (opts::SymbolsSubcommand)
     return opts::symbols::dumpSymbols(*Dbg);
+  if (opts::IRMemoryMapSubcommand)
+    return opts::irmemorymap::evaluateMemoryMapCommands(*Dbg);
 
   WithColor::error() << "No command specified.\n";
   return 1;
 }