[Symbolizer] Map from module-relative addresses in ProcessContext.

[mysterymath]

Summary

This makes it an error for module-relative addresses to overlap. mmap
addresses are expected to be the runtime locations of the
module-relative virtual addresses, so the mapping should always be 1:1.

[mysterymath]

Tag commit message.

[mysterymath]

Rebase.

[mysterymath]

Rebase.

[mcgrathr]

llvm/lib/DebugInfo/Symbolize/MarkupFilter.cpp

120

Is it not desirable to report the column location of the address field? This error is indicating that the address and/or size is problematic, so calling one of them the precise error location rather than the beginning of the line seems to make sense.

llvm/include/llvm/DebugInfo/Symbolize/MarkupContext.h

 //===- MarkupContext.h ------------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// This file declares an object that represents a process context that relates
-/// virtual addresses to module addresses.
+/// addresses to module addresses.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DEBUGINFO_SYMBOLIZE_MARKUPCONTEXT_H
 #define LLVM_DEBUGINFO_SYMBOLIZE_MARKUPCONTEXT_H
 
 #include "Markup.h"
 
 #include <map>
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Object/BuildID.h"
 
 namespace llvm {
 
 namespace json {
 class OStream;
 } // namespace json
 
 namespace symbolize {
 
-/// A process context that allows converting between virtual addresses and
+/// A process context that allows converting between addresses and
 /// module-relative addresses.
 class MarkupContext {
 public:
   struct Module {
     uint64_t ID;
     std::string Name;
     object::BuildID BuildID;
   };
 
   struct MMap {
     uint64_t Addr;
     uint64_t Size;
     const Module *Mod;
     std::string Mode; // Lowercase
     uint64_t ModuleRelativeAddr;
 
     bool contains(uint64_t Addr) const;
-    uint64_t getModuleRelativeAddr(uint64_t Addr) const;
+    bool containsMRAddr(uint64_t MRAddr) const;
+    uint64_t toModuleRelativeAddr(uint64_t Addr) const;
+    uint64_t fromModuleRelativeAddr(uint64_t MRAddr) const;
   };
 
 private:
   // Map from Module ID to Module.
   DenseMap<uint64_t, std::unique_ptr<Module>> Modules;
 
   // Ordered map from starting address to mmap.
   std::map<uint64_t, MMap> MMaps;
 
+  // Ordered map from starting module-relative address to mmap.
+  std::map<uint64_t, MMap *> MMapsByMRAddr;
+
 public:
   bool empty() const;
   void clear();
 
   void dump(json::OStream &JOS) const;
 
   std::pair<const Module *, bool> insertModule(Module M);
   const Module *getModule(uint64_t ID) const;
 
   /// Inserts an mmap if no existing mmap overlaps; otherwise returns the
   /// existing one.
   std::pair<const MMap *, bool> insertMMap(MMap MM);
 
   /// Returns the MMap that contains the given address or nullptr if none.
   const MMap *getContainingMMap(uint64_t Addr) const;
 
+  /// Returns the MMap that contains the given module-relative address or
+  /// nullptr if none.
+  const MMap *getContainingMMapForMRAddr(uint64_t MRAddr) const;
+
 private:
   const MMap *getOverlappingMMap(const MMap &Map) const;
+  const MMap *getOverlappingMRAddrMMap(const MMap &Map) const;
 };
 
 } // end namespace symbolize
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_SYMBOLIZE_MARKUPCONTEXT_H

llvm/lib/DebugInfo/Symbolize/MarkupContext.cpp

 using namespace llvm;
 using namespace llvm::symbolize;
 
 bool MarkupContext::empty() const { return Modules.empty() && MMaps.empty(); }
 
 void MarkupContext::clear() {
   Modules.clear();
   MMaps.clear();
+  MMapsByMRAddr.clear();
 }
 
 void MarkupContext::dump(json::OStream &JOS) const {
   JOS.object([&] {
     JOS.attributeArray("modules", [&] {
       for (const auto &[_, Module] : Modules) {
         JOS.objectBegin();
         JOS.attribute("id", Module->ID);

 std::pair<const MarkupContext::MMap *, bool>
 MarkupContext::insertMMap(MMap MM) {
   if (const MMap *Overlap = getOverlappingMMap(MM))
     return {Overlap, false};
   const auto Res = MMaps.try_emplace(MM.Addr, std::move(MM));
   (void)Res;
   assert(Res.second &&
          "Overlap check should have ensured unique starting address.");
-  return {&Res.first->second, true};
+  auto ReverseRes =
+      MMapsByMRAddr.try_emplace(MM.ModuleRelativeAddr, &Res.first->second);
+  (void)ReverseRes;
+  assert(ReverseRes.second &&
+         "Overlap check should have ensured unique starting address.");
+  return {&Res.first->second, Res.second};
 }
 
 const MarkupContext::MMap *
 MarkupContext::getContainingMMap(uint64_t Addr) const {
   // Find the first mmap starting >= Addr.
   auto I = MMaps.lower_bound(Addr);
   if (I != MMaps.end() && I->second.contains(Addr))
     return &I->second;
 
   // The previous mmap is the last one starting < Addr.
   if (I == MMaps.begin())
     return nullptr;
   --I;
   return I->second.contains(Addr) ? &I->second : nullptr;
 }
 
+const MarkupContext::MMap *
+MarkupContext::getContainingMMapForMRAddr(uint64_t MRAddr) const {
+  // Find the first mmap starting >= MRAddr.
+  auto I = MMapsByMRAddr.lower_bound(MRAddr);
+  if (I != MMapsByMRAddr.end() && I->second->containsMRAddr(MRAddr))
+    return I->second;
+
+  // The previous mmap is the last one starting < MRAddr.
+  if (I == MMapsByMRAddr.begin())
+    return nullptr;
+  --I;
+  return I->second->containsMRAddr(MRAddr) ? I->second : nullptr;
+}
+
 // Checks for an existing mmap that overlaps the given one and returns a pointer
 // to it. Checking for overlaps in insertMMap ensures the overlap is unique.
 const MarkupContext::MMap *
 MarkupContext::getOverlappingMMap(const MMap &Map) const {
   // If the given map contains the start of another mmap, they overlap.
   auto I = MMaps.upper_bound(Map.Addr);
   if (I != MMaps.end() && Map.contains(I->second.Addr))
     return &I->second;
 
   // If no element starts inside the given mmap, the only possible overlap would
   // be if the preceding mmap contains the start point of the given mmap.
   if (I != MMaps.begin()) {
     --I;
     if (I->second.contains(Map.Addr))
       return &I->second;
   }
+  return getOverlappingMRAddrMMap(Map);
+}
+
+const MarkupContext::MMap *
+MarkupContext::getOverlappingMRAddrMMap(const MMap &Map) const {
+  // If the given map contains the start of another mmap, they overlap.
+  auto I = MMapsByMRAddr.upper_bound(Map.ModuleRelativeAddr);
+  if (I != MMapsByMRAddr.end() &&
+      Map.containsMRAddr(I->second->ModuleRelativeAddr))
+    return I->second;
+
+  // If no element starts inside the given mmap, the only possible overlap would
+  // be if the preceding mmap contains the start point of the given mmap.
+  if (I != MMapsByMRAddr.begin()) {
+    --I;
+    if (I->second->containsMRAddr(Map.ModuleRelativeAddr))
+      return I->second;
+  }
   return nullptr;
 }
 
 bool MarkupContext::MMap::contains(uint64_t Addr) const {
   return this->Addr <= Addr && Addr < this->Addr + Size;
 }
 
-// Returns the module-relative address for a given virtual address.
-uint64_t MarkupContext::MMap::getModuleRelativeAddr(uint64_t Addr) const {
+bool MarkupContext::MMap::containsMRAddr(uint64_t MRAddr) const {
+  return this->ModuleRelativeAddr <= MRAddr &&
+         MRAddr < this->ModuleRelativeAddr + Size;
+}
+
+uint64_t MarkupContext::MMap::toModuleRelativeAddr(uint64_t Addr) const {
   return Addr - this->Addr + ModuleRelativeAddr;
 }
+
+uint64_t MarkupContext::MMap::fromModuleRelativeAddr(uint64_t MRAddr) const {
+  return MRAddr - ModuleRelativeAddr + this->Addr;
+}

llvm/lib/DebugInfo/Symbolize/MarkupFilter.cpp

if (!ParsedMMap)
     return true;
 
   auto Res = Context.insertMMap(std::move(*ParsedMMap));
   const MarkupContext::MMap &MMap = *Res.first;
   if (!Res.second) {
     WithColor::error(errs())
         << formatv("overlapping mmap: #{0:x} [{1:x}-{2:x}]\n", MMap.Mod->ID,
                    MMap.Addr, MMap.Addr + MMap.Size - 1);
-    reportLocation(Node.Fields[0].begin());
+    reportLocation(Node.Text.begin());
     return true;
   }
 
   if (!MIL || MIL->Mod != MMap.Mod) {
     endAnyModuleInfoLine();
     for (const MarkupNode &Node : DeferredNodes)
       filterNode(Node);
     beginModuleInfoLine(MMap.Mod);
bool MarkupFilter::tryPC(const MarkupNode &Node) {
   if (!MMap) {
     WithColor::error() << "no mmap covers address\n";
     reportLocation(Node.Fields[0].begin());
     printRawElement(Node);
     return true;
   }
 
   Expected<DILineInfo> LI = Symbolizer.symbolizeCode(
-      MMap->Mod->BuildID, {MMap->getModuleRelativeAddr(*Addr)});
+      MMap->Mod->BuildID, {MMap->toModuleRelativeAddr(*Addr)});
   if (!LI) {
     WithColor::defaultErrorHandler(LI.takeError());
     printRawElement(Node);
     return true;
   }
   if (!*LI) {
     printRawElement(Node);
     return true;
bool MarkupFilter::tryBackTrace(const MarkupNode &Node) {
 
   const MarkupContext::MMap *MMap = Context.getContainingMMap(*Addr);
   if (!MMap) {
     WithColor::error() << "no mmap covers address\n";
     reportLocation(Node.Fields[0].begin());
     printRawElement(Node);
     return true;
   }
-  uint64_t MRA = MMap->getModuleRelativeAddr(*Addr);
+  uint64_t MRA = MMap->toModuleRelativeAddr(*Addr);
 
   Expected<DIInliningInfo> II =
       Symbolizer.symbolizeInlinedCode(MMap->Mod->BuildID, {MRA});
   if (!II) {
     WithColor::defaultErrorHandler(II.takeError());
     printRawElement(Node);
     return true;
   }
bool MarkupFilter::tryData(const MarkupNode &Node) {
   if (!MMap) {
     WithColor::error() << "no mmap covers address\n";
     reportLocation(Node.Fields[0].begin());
     printRawElement(Node);
     return true;
   }
 
   Expected<DIGlobal> Symbol = Symbolizer.symbolizeData(
-      MMap->Mod->BuildID, {MMap->getModuleRelativeAddr(*Addr)});
+      MMap->Mod->BuildID, {MMap->toModuleRelativeAddr(*Addr)});
   if (!Symbol) {
     WithColor::defaultErrorHandler(Symbol.takeError());
     printRawElement(Node);
     return true;
   }
 
   highlight();
   OS << Symbol->Name;

llvm/test/DebugInfo/symbolize-filter-markup-data.test

 REQUIRES: x86-registered-target
 RUN: split-file %s %t
 RUN: mkdir -p %t/.build-id/ab
 RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %t/asm.s \
 RUN:   -o %t/.build-id/ab/cdef.debug
 RUN: llvm-symbolizer --debug-file-directory=%t --filter-markup < %t/input \
 RUN:   > %t.output 2> %t.err
 RUN: FileCheck %s --input-file=%t.output --match-full-lines \
 RUN:   --implicit-check-not {{.}}
 RUN: FileCheck %s --check-prefix=ERR --input-file=%t.err --match-full-lines
 
-CHECK: [[BEGIN:\[{3}]]ELF module #0x0 "a.o"; BuildID=abcdef [0x0-0x4](r),[0x10-0x11](r)[[END:\]{3}]]
-CHECK: long long byte
-CHECK: long byte
+CHECK: [[BEGIN:\[{3}]]ELF module #0x0 "a.o"; BuildID=abcdef [0x0-0x3](r),[0x10-0x10](r)[[END:\]{3}]]
+CHECK: long long
+CHECK: byte
 CHECK: [[BEGIN]]data:0x5[[END]]
 
 ERR: error: expected 1 field(s); found 0
 ERR: error: no mmap covers address
 
 ;--- input
 {{{module:0:a.o:elf:abcdef}}}
-{{{mmap:0:5:load:0:r:0}}}
-{{{mmap:0x10:2:load:0:r:0x3}}}
-{{{data:0x0}}} {{{data:0x1}}} {{{data:0x4}}}
-{{{data:0x10}}} {{{data:0x11}}}
+{{{mmap:0:4:load:0:r:0}}}
+{{{mmap:0x10:1:load:0:r:0x4}}}
+{{{data:0x0}}} {{{data:0x1}}}
+{{{data:0x10}}}
 
 {{{data}}}
 {{{data:0x5}}}
 ;--- asm.s
 long:
   .long 0x11223344
   .size long, 4
 byte:
   .byte 0x42
   .size byte, 1

llvm/test/DebugInfo/symbolize-filter-markup-dump-context.test

 CHECK-NEXT:     ],
 CHECK-NEXT:     "mmaps": [
 CHECK-NEXT:       {
 CHECK-NEXT:         "address": 16,
 CHECK-NEXT:         "size": 16,
 CHECK-NEXT:         "type": "load",
 CHECK-NEXT:         "moduleID": 1,
 CHECK-NEXT:         "mode": "r",
-CHECK-NEXT:         "moduleRelativeAddress": 2
+CHECK-NEXT:         "moduleRelativeAddress": 32
 CHECK-NEXT:       },
 CHECK-NEXT:       {
 CHECK-NEXT:         "address": 32,
 CHECK-NEXT:         "size": 48,
 CHECK-NEXT:         "type": "load",
 CHECK-NEXT:         "moduleID": 1,
 CHECK-NEXT:         "mode": "w",
-CHECK-NEXT:         "moduleRelativeAddress": 3
+CHECK-NEXT:         "moduleRelativeAddress": 64
 CHECK-NEXT:       },
 CHECK-NEXT:       {
 CHECK-NEXT:         "address": 80,
 CHECK-NEXT:         "size": 96,
 CHECK-NEXT:         "type": "load",
 CHECK-NEXT:         "moduleID": 0,
 CHECK-NEXT:         "mode": "rx",
-CHECK-NEXT:         "moduleRelativeAddress": 4
+CHECK-NEXT:         "moduleRelativeAddress": 128
 CHECK-NEXT:       }
 CHECK-NEXT:     ]
 CHECK-NEXT:   },
 CHECK-NEXT:   {
 CHECK-NEXT:     "modules": [
 CHECK-NEXT:       {
 CHECK-NEXT:         "id": 0,
 CHECK-NEXT:         "name": "c.o",
 CHECK-NEXT:         "type": "elf",
 CHECK-NEXT:         "buildID": "ef"
 CHECK-NEXT:       }
 CHECK-NEXT:     ],
 CHECK-NEXT:     "mmaps": []
 CHECK-NEXT:   }
 CHECK-NEXT: ]
 
 ERR: error: --[no-]dump-context can only be used with --filter-markup
 
 ;--- log
 {{{module:1:a.o:elf:cd}}}
 {{{module:0:b.o:elf:ab}}}
-{{{mmap:0x10:0x10:load:1:r:0x2}}}
-{{{mmap:0x20:0x30:load:1:w:0x3}}}
-{{{mmap:0x50:0x60:load:0:rx:0x4}}}
+{{{mmap:0x10:0x10:load:1:r:0x20}}}
+{{{mmap:0x20:0x30:load:1:w:0x40}}}
+{{{mmap:0x50:0x60:load:0:rx:0x80}}}
 {{{pc:0x20}}}
 {{{reset}}}
 {{{module:0:c.o:elf:ef}}}

llvm/test/DebugInfo/symbolize-filter-markup-mmap.test

 ERR: error: expected address; found '1'
 ERR: error: expected size; found '-1'
 ERR: error: expected mode; found ''
 ERR: error: expected mode; found 'g'
 ERR: error: expected mode; found 'wr'
 ERR: error: overlapping mmap: #0x0 [0xa-0xb]
 ERR: error: overlapping mmap: #0x0 [0xa-0xb]
 ERR: error: overlapping mmap: #0x0 [0xa-0xb]
+ERR: error: overlapping mmap: #0x0 [0x1-0x1]
 
 ;--- log
 {{{module:0:a.o:elf:abb50d82b6bdc861}}}
 {{{mmap:0x1:1:load:0:r:0}}}
-{{{mmap:0x2:1:load:0:w:0}}}
-{{{mmap:0x3:1:load:0:x:0}}}
-{{{mmap:0x4:1:load:0:rwx:0}}}
-{{{mmap:0x0:1:load:0:RWX:0}}}
-{{{mmap:0xa:2:load:0:r:0}}}
+{{{mmap:0x2:1:load:0:w:0x4}}}
+{{{mmap:0x3:1:load:0:x:0x6}}}
+{{{mmap:0x4:1:load:0:rwx:0x8}}}
+{{{mmap:0x0:1:load:0:RWX:0xa}}}
+{{{mmap:0xa:2:load:0:r:0xc}}}
 
 {{{mmap}}}
 {{{mmap:0:1:unknown}}}
 {{{mmap:0:10000000:load}}}
 {{{mmap:1:10000000:load:0:r:0}}}
 {{{mmap:0:-1:load:0:r:0}}}
 {{{mmap:0:10000000:load:0::0}}}
 {{{mmap:0:10000000:load:0:g:0}}}
 {{{mmap:0:10000000:load:0:wr:0}}}
-{{{mmap:0xa:1:load:0:r:0}}}
-{{{mmap:0x9:2:load:0:r:0}}}
-{{{mmap:0x9:5:load:0:r:0}}}
+{{{mmap:0xa:1:load:0:r:0xe}}}
+{{{mmap:0x9:2:load:0:r:0x11}}}
+{{{mmap:0x9:5:load:0:r:0x13}}}
+{{{mmap:0xc:1:load:0:r:0}}}