[ELF] .gdb_index: use lower_bound to compute relative CU index in an object file

[MaskRay]

Summary

This reinstates what I originally intended to do in D54361.
It removes the assumption that .debug_gnu_pubnames has increasing CuOffset.

[dblaikie]

ELF/SyntheticSections.cpp

2442–2448

I get where @ruiu is coming from in this being a bit harder to read - and if he'd prefer it to be a linear search (N^2, ultimately where N is the number of pub tables in the file - which would usually be small, except for LTO situations), that's OK.

I'd prefer a binary search - though perhaps there are more legible ways to write it, maybe having a nicer general algorithm, something like:

auto I = llvm::BinarySearch(CUs, [](GDBIndexSection::CuEntry CU) {
  return CU.CuOffset == Offset ? 0 : CU.CuOffset < Offset ? -1 : 1;
});
if (I == CUs.end()) {
  /* invalid debug info, a pubnames seciton with a CU offset that's not the offset of any CU in the input */
}
... *I ...

Might be nice - open to ideas on naming "BinarySearch" so that it's not confusing with other similar APIs, etc. Though I don't think it could be misused terribly easily - if someone mistook it for std::binary_search it'd only successfully compile if the object being searched for also happened to have an operator() that matched this usage, et.c

test/ELF/gdb-index-multiple-cu.s

63–64

Probably worth explaining why they're swapped - what this is intending to test for (that it's testing the case where the pubnames are not in the same order as the CUs), something like, perhaps:

1. Swap the pubname sections to test the case where pubnames are in a different order than the CUs they refer to

[MaskRay]

Rebase because of the Kind: -> Attributes: change

[MaskRay]

Elaborate the rationale behind swapping as dblaikie suggested

[MaskRay]

ELF/SyntheticSections.cpp

2442–2448

Yes, the layout clang-format uses is not pretty. I don't know if additional error checking is worth the few more lines of code, as gold only handles the first set of .debug_gnu_pubnames. I'm not sure if the implementer has noticed that, but I won't be surprised if they don't as debug symbol accelerating in the partially linked object files does not seem very noticeable.

As to llvm::BinarySearch, I'm unclear if the end()-returning behavior when there is no element equal to the needle is useful. stdlib.h bsearch and std::binary_search look mostly useless to me.

It is important to get CuIndex of subsequent object files correct (that was the main merit of D54361)

[dblaikie]

ELF/SyntheticSections.cpp

2442–2448

Not sure I follow a few things

• Error checking seems necessary to me (but I know lld takes a different approach to error handling than I would - not sure how far that extends, whether only to invalid object files, or invalid data (like this DWARF) inside a valid object file)

• There are several things I meant to imply by the llvm::BinarySerach example - one, that it wouldn't take the needle parameter and pass it back into the comparator (this seemed to be Rui's cited complaint - and it is a bit awkward/unnecessary), returning end rather than the next element (seems more likely what most users want when they're searching for something in a list), and container (rather than begin/end) support

• stdlib.h/std::binary_search - yeah, neither look particularly helpful for this problem/making this code more readable

• Not sure I follow why any of the solutions discussed would cause/risk the CuIndex of subsequent object files to be incorrect

[MaskRay]

ELF/SyntheticSections.cpp

2442–2448

Sorry I didn't notice that llvm::BinarySearch does not take the needle parameter. Yeah it indeed looks better than std::binary_search!

(this seemed to be Rui's cited complaint - and it is a bit awkward/unnecessary)

std::binary_search has reserved the third parameter as the needle with a generic type. As it cannot overload on that parameter to express a comparator, when both the needle and the comparator appear, it does look a bit redundant when we pass a lambda as a comparator.

Not sure I follow why any of the solutions discussed would cause/risk the CuIndex of subsequent object files to be incorrect

That bug has been fixed and is no longer relevant. These revisions are just polishing the interface and fixing some corner cases that people may not notice. They are good from a quality of implementation view, though.

[MaskRay]

Change std::lower_bound to llvm::lower_bound

but i'm still unclear if we should handle nonexistence case and if so, what error message we should use. It is difficult as LLDDwarfObj does not know the object name.

[ruiu]

ELF/SyntheticSections.cpp

2445

Hmm, not sure if I follow. This new code still assume that CUs is sorted by CuOffset, no?

[dblaikie]

ELF/SyntheticSections.cpp

2445

It's not that CUs could be unordered wrt CuOffset - they're read from the section linearly, so they're necessarily ordered from smallest to largest CuOffset.

But the order of references from pubnames contributions isn't ordered relative to them - so the first pubnames contribution might reference the last CU, for instance.

The currently committed solution assumes that the pubnames contribution are in the same order as the CU contributions (for each pubnames contribution, it walks from the last CU referenced from a pubnames contribution (or from the start if it's the first) expecting to find the next one - never doubling back).

[MaskRay]

Thanks that dblaikie gave his point. Should we move forward with this revision? This patch makes the code correct in this corner case that gold would fail at the cost of one more line. The local lower_bound usage is indeed a bit uglier but it shouldn't be a huge problem. When more needs emerge we can add a utility to STLExtras.h and improve the binary search call sites like this place.

[ruiu]

LGTM

ELF/SyntheticSections.cpp

 readPubNamesAndTypes(const LLDDwarfObj<ELFT> &Obj,
                      const std::vector<GdbIndexSection::CuEntry> &CUs) {
   const DWARFSection &PubNames = Obj.getGnuPubNamesSection();
   const DWARFSection &PubTypes = Obj.getGnuPubTypesSection();
 
   std::vector<GdbIndexSection::NameAttrEntry> Ret;
   for (const DWARFSection *Pub : {&PubNames, &PubTypes}) {
     DWARFDebugPubTable Table(Obj, *Pub, Config->IsLE, true);
-    uint32_t I = 0;
     for (const DWARFDebugPubTable::Set &Set : Table.getData()) {
       // The value written into the constant pool is Kind << 24 | CuIndex. As we
       // don't know how many compilation units precede this object to compute
       // CuIndex, we compute (Kind << 24 | CuIndexInThisObject) instead, and add
       // the number of preceding compilation units later.
-      //
-      // We assume both CUs[*].CuOff and Set.Offset are increasing.
-      while (I < CUs.size() && CUs[I].CuOffset < Set.Offset)
-        ++I;
+      uint32_t I =
+          lower_bound(CUs, Set.Offset,
+                      [](GdbIndexSection::CuEntry CU, uint32_t Offset) {
+                        return CU.CuOffset < Offset;
+                      }) -
+          CUs.begin();
       for (const DWARFDebugPubTable::Entry &Ent : Set.Entries)
         Ret.push_back({{Ent.Name, computeGdbHash(Ent.Name)},
                        (Ent.Descriptor.toBits() << 24) | I});
     }
   }
   return Ret;
 }
 
 // Create a list of symbols from a given list of symbol names and types

test/ELF/gdb-index-multiple-cu.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
 # RUN: ld.lld --gdb-index %t.o -o %t
 # RUN: llvm-dwarfdump -gdb-index %t | FileCheck %s
 
-# Attributes << 24 | CuIndex = 48 << 24 | 1 = 0x30000001
-# CHECK: Constant pool
-# CHECK-NEXT: 0(0x0): 0x30000001
+# CuIndexAndAttrs of _start:
+#   Attributes << 24 | CuIndex = 48 << 24 | 0 = 0x30000000
+# CuIndexAndAttrs of foo:
+#   Attributes << 24 | CuIndex = 48 << 24 | 1 = 0x30000001
+# CHECK:      Symbol table
+# CHECK-DAG:      String name: _start, CU vector index: 0
+# CHECK-DAG:      String name: foo, CU vector index: 1
+# CHECK:      Constant pool
+# CHECK-NEXT:   0(0x0): 0x30000000
+# CHECK-NEXT:   1(0x8): 0x30000001
 
-.globl _start
+.globl _start, foo
 _start:
-  ret
+foo:
 
 .section .debug_abbrev,"",@progbits
   .byte 1              # Abbreviation Code
   .byte 17             # DW_TAG_compile_unit
   .byte 1              # DW_CHILDREN_yes
   .ascii  "\264B"        # DW_AT_GNU_pubnames
-  .byte 12             # DW_FORM_flag
+  .byte 25             # DW_FORM_flag_present
   .byte 0              # EOM(1)
   .byte 0              # EOM(2)
   .byte 2              # Abbreviation Code
   .byte 46             # DW_TAG_subprogram
   .byte 0              # DW_CHILDREN_no
   .byte 3              # DW_AT_name
   .byte 8              # DW_FORM_string
   .byte 0              # EOM(1)
   .byte 0              # EOM(2)
   .byte 0
 
 .section .debug_info,"",@progbits
 .Lcu_begin0:
   .long .Lcu_end0 - .Lcu_begin0 - 4
   .short  4              # DWARF version number
   .long 0              # Offset Into Abbrev. Section
   .byte 4              # Address Size
+.Ldie0:
   .byte 1              # Abbrev [1] DW_TAG_compile_unit
-  .byte 0              # DW_AT_GNU_pubnames
+  .byte 2              # Abbrev [2] DW_TAG_subprogram
+  .asciz  "_start"       # DW_AT_name
+  .byte 0
   .byte 0
 .Lcu_end0:
 .Lcu_begin1:
   .long .Lcu_end1 - .Lcu_begin1 - 4
   .short  4              # DWARF version number
   .long 0              # Offset Into Abbrev. Section
   .byte 4              # Address Size
-.Ldie:
+.Ldie1:
   .byte 1              # Abbrev [1] DW_TAG_compile_unit
-  .byte 1              # DW_AT_GNU_pubnames
   .byte 2              # Abbrev [2] DW_TAG_subprogram
-  .asciz  "_start"       # DW_AT_name
+  .asciz  "foo"          # DW_AT_name
   .byte 0
 .Lcu_end1:
 
-# .debug_gnu_pubnames has just one set, associated with .Lcu_begin1 (CuIndex: 1)
+# Swap sets to test the case where pubnames are in a
+# different order than the CUs they refer to.
 .section .debug_gnu_pubnames,"",@progbits
-  .long .LpubNames_end1-.LpubNames_begin1
+  # CuIndex: 1
+  .long .LpubNames_end1 - .LpubNames_begin1
 .LpubNames_begin1:
   .short  2              # Version
   .long .Lcu_begin1    # CU Offset
   .long .Lcu_end1 - .Lcu_begin1
-  .long .Ldie - .Lcu_begin1
+  .long .Ldie1 - .Lcu_begin1
   .byte 48             # Attributes: FUNCTION, EXTERNAL
-  .asciz  "_start"       # External Name
+  .asciz  "foo"          # External Name
   .long 0
 .LpubNames_end1:
+
+  # CuIndex: 0
+  .long .LpubNames_end0 - .LpubNames_begin0
+.LpubNames_begin0:
+  .short  2              # Version
+  .long .Lcu_begin0    # CU Offset
+  .long .Lcu_end0 - .Lcu_begin0
+  .long .Ldie0 - .Lcu_begin0
+  .byte 48             # Attributes: FUNCTION, EXTERNAL
+  .asciz  "_start"       # External Name
+  .long 0
+.LpubNames_end0: