[lld-macho] Fix symbol name returned from InputSection::getLocation

[BertalanD]

Summary

This commit fixes the issue that getLocation always printed the name of
the first symbol in the section.

For clarity, upper_bound is used instead of a linear search for finding
the closest symbol name. Note that this change does not affect
performance: this function is only called when printing errors and
symbols typically contains a single symbol because of
.subsections_via_symbols.

Please commit this diff with the following author info:
Daniel Bertalan <[e-mail]>

[thakis]

Thanks for the patch!

As a general guideline, I think it helps if every patch is either a behavior-preserving refactoring (these patches can be larger), or something that changes behavior (these patches are ideally smaller). That makes it easier to reason about invariants, and makes the patch easier to review.

In this case, the patch is tiny either way, and it doesn't matter all that much. But it does two separate things: 1. Change the search algorithm implementation (behavior-preserving) 2. Change the diag (not behavior preserving). So abstractly, it seems kind of nice to split them, or at least to talk about both parts separately.

For the refactor patch: There are usually few symbols per section, so a linear scan is likely faster in practice. Also, this function is only called when emitting errors, so it's not performance-critical anyways, probably. So I guess the motivation for that part is clarity?

For the behavior change: Nice catch! Patches that change behavior ideally come with tests – do you think you could include one? In practice, we'd only handle this in files without .subsections_via_symbols, right?

[BertalanD]

Clarified that the use of upper_bound is purely a code style change, and added a test.

[thakis]

Thanks!

[int3]

For the refactor patch: There are usually few symbols per section, so a linear scan is likely faster in practice. Also, this function is only called when emitting errors, so it's not performance-critical anyways, probably. So I guess the motivation for that part is clarity?

Yep, those were my reasons. But yeah no harm changing it to a binary search either since it's not perf-critical

lld/MachO/InputSection.cpp

static uint64_t resolveSymbolVA(const Symbol *sym, uint8_t type) {
   if (relocAttrs.hasAttr(RelocAttrBits::TLV))
     return sym->resolveTlvVA();
   return sym->getVA();
 }
 
 std::string InputSection::getLocation(uint64_t off) const {
   // First, try to find a symbol that's near the offset. Use it as a reference
   // point.
-  for (size_t i = 0; i < symbols.size(); ++i)
-    if (symbols[i]->value <= off &&
-        (i + 1 == symbols.size() || symbols[i + 1]->value > off))
-      return (toString(getFile()) + ":(symbol " + symbols.front()->getName() +
-              "+0x" + Twine::utohexstr(off - symbols[i]->value) + ")")
-          .str();
+  auto *nextSym = llvm::upper_bound(
+      symbols, off, [](uint64_t a, const Defined *b) { return a < b->value; });
+  if (nextSym != symbols.begin()) {
+    auto &sym = *std::prev(nextSym);
+    return (toString(getFile()) + ":(symbol " + sym->getName() + "+0x" +
+            Twine::utohexstr(off - sym->value) + ")")
+  }
 
   // If that fails, use the section itself as a reference point.
   for (const Subsection &subsec : section.subsections) {
     if (subsec.isec == this) {
       off += subsec.offset;
       break;
     }
   }

lld/test/MachO/invalid/range-check.s

 # CHECK-DAG: error: stub helper header is out of range: [[#]] is not in [-2147483648, 2147483647]
 # CHECK-DAG: error: stub helper header is out of range: [[#]] is not in [-2147483648, 2147483647]
 
 #--- bar.s
 .globl _bar
 _bar:
 
 #--- test.s
+
+# Added to ensure that the error mentions the right function.
+_baz:
+  ret
+
 .globl _main, _foo
 
 _main:
   movq _foo@GOTPCREL(%rip), %rax
   callq _bar
   ret
 
 .int _foo
 .zerofill __TEXT,bss,_zero,0xffffffff
 
 .data
 _foo:
   .space 0