[llvm-objdump] Add option to sort symbols during disassembly

[stephenneuendorffer]

Summary

Note: This only sorts the symbols within the same section.

[rupprecht]

Is there a particular use case for this feature?

The loop that prints each symbol might have some more assumptions that it's printed in address order; it's pretty complicated so I didn't fully review it, but I'm not confident this won't introduce some subtle bug. For an initial test, you might want run llvm-objdump -d --sort on some large binary, and make sure that it's equivalent to llvm-objdump -d after you've reordered the sections with a different post-processing script.

llvm/test/tools/llvm-objdump/X86/Inputs/sort-test.yaml

2

This doesn't appear to be an actual test. Can you add some test assertions, e.g. RUN: lines?

llvm/tools/llvm-objdump/llvm-objdump.cpp

299

Just --sort does not seem to be a specific flag. e.g. should we sort section headers by name? Or what about symbols *not* when disassembling, i.e. llvm-objdump --syms --sort

1330–1333

sortedSymbols should be preallocated (sortedSymbols.resize(Symbols.size())) to avoid the performance hit when increasing the size every time.

1342–1343

Demangling should happen earlier, so that the symbols are also sorted when demangled

[MaskRay]

Hi, can you describe the use case you have in mind? Is that for a more stable disassembly output when there can be several symbols defined at the same address?

There is no guarantee for the .symtab order but in practice it has some patterns. Both GNU as and llvm-mc sort symbols in object files. Linkers (GNU ld, gold, lld) seem to use a visiting order. So, say, you have several aliases:

.globl foo, _foo, __foo, ___foo
_foo:
__foo:
foo:
___foo:
  ret

After you add or delete instructions, the order among these *foo should not change.

For one thing, llvm-objdump currently uses the symbol table order while I think preferring STB_GLOBAL/STB_WEAK to STB_LOCAL may be nice. GNU objdump may have some other heuristics. I'll dig into its source.

[stephenneuendorffer]

The point of this is to disassemble symbols in a section in a fixed order. This might be useful because linking has moved symbols around, or because some other linker disassembles symbols in alphabetical order and one wants to compare. Basically, I found this useful and I thought other people might. It was much easier to modify llvm-objdump directly than to post-process the disassembly.

llvm/tools/llvm-objdump/llvm-objdump.cpp

299

I agree, but struggled what else to actually name it. --sort-symbols-when-disassembling? --sort-symbols, and then change other corresponding modes? I'm new to this code, so I'm not sure what other modes are interesting/appropriate.

1330–1333

Good point.

1342–1343

Makes sense.

[MaskRay]

In D75498#1904662, @stephenneuendorffer wrote:

The point of this is to disassemble symbols in a section in a fixed order. This might be useful because linking has moved symbols around, or because some other linker disassembles symbols in alphabetical order and one wants to compare. Basically, I found this useful and I thought other people might. It was much easier to modify llvm-objdump directly than to post-process the disassembly.

As I commented at https://reviews.llvm.org/D75498#1904244 , some other linker disassembles symbols in alphabetical order does not match what I have observed with GNU ld, gold and lld. Are you using a different linker or am I missing something?

If the symbol resolution does not change, functions have more of fewer instructions, the order should not change.

[stephenneuendorffer]

As I commented at https://reviews.llvm.org/D75498#1904244 , some other linker disassembles symbols in alphabetical order does not match what I have observed with GNU ld, gold and lld. Are you using a different linker or am I missing something?

You're not missing anything. The linker in question is not an open source linker.

[stephenneuendorffer]

llvm/tools/llvm-objdump/llvm-objdump.cpp

1342–1343

Except.... that this means allocating space for all the demangled strings, which would have a more significant memory, or a more significant runtime cost to demangling during sorting. Currently, the sorting just happens on StringRefs...
My intuition says that mangling shouldn't change the resulting order significantly (although it might mean that some mangled symbol foo(...)) might get reordered with a non-mangled symbol _foo, but this seems minimally concerning to me?

[MaskRay]

In D75498#1906052, @stephenneuendorffer wrote:

As I commented at https://reviews.llvm.org/D75498#1904244 , some other linker disassembles symbols in alphabetical order does not match what I have observed with GNU ld, gold and lld. Are you using a different linker or am I missing something?

You're not missing anything. The linker in question is not an open source linker.

Shouldn't that linker be fixed instead? It is usually a simple data structure replacement... For example, unordered_map -> MapVector.

Sorry that I will make some pushback here. A non-deterministic symbol order also affects other tools like readelf/nm. Fixing the linker is likely the simplest way to make every binary manipulation tool happy.

[stephenneuendorffer]

In D75498#1906660, @MaskRay wrote:

In D75498#1906052, @stephenneuendorffer wrote:

As I commented at https://reviews.llvm.org/D75498#1904244 , some other linker disassembles symbols in alphabetical order does not match what I have observed with GNU ld, gold and lld. Are you using a different linker or am I missing something?

You're not missing anything. The linker in question is not an open source linker.

Shouldn't that linker be fixed instead? It is usually a simple data structure replacement... For example, unordered_map -> begin.

Sorry that I will make some pushback here. A non-deterministic symbol order also affects other tools like readelf/nm. Fixing the linker is likely the simplest way to make every binary manipulation tool happy.

The short answer is no, we can't fix the other linker. I don't mind the pushback and I don't mind if you say "We don't want this." It's something that I'd rather not carry around internally, but maybe that's just what has to be done. :)

[jhenderson]

I might be getting the wrong end of the stick here, but since symbol tables have to have local symbols before global symbols already, isn't it possible (indeed quite likely) for linked output symbols to be in a different order other than address order? As far as I know, this ordering requirement is in fact the only requirement in the ELF gABI, and I think we should be writing our tools based on that rather than decisions that some linkers have made. In other words, I think we need to be able to nicely handle symbols in different orders. Whether that really justifies a new option, I'm not sure either way, but it's also worth noting that llvm-nm already provides options to sort the symbols it prints (and indeed does some sorting by default), so I think an argument can be made that there's some prior art here, especially if the switch doesn't introduce much complexity (it doesn't look like it does).

[jhenderson]

In D75498#1904130, @rupprecht wrote:

Is there a particular use case for this feature?

The loop that prints each symbol might have some more assumptions that it's printed in address order; it's pretty complicated so I didn't fully review it, but I'm not confident this won't introduce some subtle bug. For an initial test, you might want run llvm-objdump -d --sort on some large binary, and make sure that it's equivalent to llvm-objdump -d after you've reordered the sections with a different post-processing script.

I've not looked at the loop, but unless it handles local and global symbols differently, there can't be any assumption about address order, since locals always appear before globals in the symbol table, regardless of address order.

[stephenneuendorffer]

It sounds like @jhenderson is mildly positive on this. Is there consensus that something something like this should go in? it looks like llvm-nm sorts by default based on name and hence doesn't have an option, but provides:

-no-sort                             - Show symbols in order encountered
-numeric-sort                        - Sort symbols by address
-reverse-sort                        - Sort in reverse order
-size-sort                           - Sort symbols by size

So maybe "-alphabetical-sort" would be partially consistent?
I'm looking for other suggestions on what to name this.

[jhenderson]

In D75498#1910119, @stephenneuendorffer wrote:

So maybe "-alphabetical-sort" would be partially consistent?
I'm looking for other suggestions on what to name this.

If we go ahead with it, I'd recommend "--lexicographical-sort" or something like that, rather than "alphabetical".

llvm/test/tools/llvm-objdump/X86/Inputs/sort-test.yaml

+--- !ELF
+FileHeader:      
+  Class:           ELFCLASS64
+  Data:            ELFDATA2LSB
+  Type:            ET_EXEC
+  Machine:         EM_X86_64
+Sections:        
+  - Name:            .text
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    AddressAlign:    0x0000000000000010
+    Content:         554889E58B0425A80000005DC30F1F00
+  - Name:            .anothertext
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    Address:         0x0000000000000010
+    AddressAlign:    0x0000000000000010
+    Content:         554889E54883EC20488D0425A8000000C745FC00000000488945F0488B45F08B08894DECE8C7FFFFFF8B4DEC01C189C84883C4205D746573742073747200C3
+  - Name:            .eh_frame
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC ]
+    Address:         0x0000000000000050
+    AddressAlign:    0x0000000000000008
+    Content:         1400000000000000017A5200017810011B0C0708900100001C0000001C00000090FFFFFF0D00000000410E108602430D06000000000000001C0000003C00000080FFFFFF3F00000000410E108602430D0600000000000000
+  - Name:            .data
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_WRITE, SHF_ALLOC ]
+    Address:         0x00000000000000A8
+    AddressAlign:    0x0000000000000004
+    Content:         '01000000'
+  - Name:            .comment
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_MERGE, SHF_STRINGS ]
+    AddressAlign:    0x0000000000000001
+    Content:         5562756E747520636C616E672076657273696F6E20332E352D317562756E74753120287472756E6B2920286261736564206F6E204C4C564D20332E352900
+Symbols:
+  - Type:            STT_SECTION
+    Section:         .text
+  - Type:            STT_SECTION
+    Section:         .anothertext
+    Value:           0x0000000000000010
+  - Type:            STT_SECTION
+    Section:         .eh_frame
+    Value:           0x0000000000000050
+  - Type:            STT_SECTION
+    Section:         .data
+    Value:           0x00000000000000A8
+  - Type:            STT_SECTION
+    Section:         .comment
+  - Name:            /tmp/a.c
+    Type:            STT_FILE
+  - Type:            STT_FILE          
+  - Name:            somedata
+    Type:            STT_OBJECT
+    Section:         .anothertext
+    Value:           0x0000000000000045
+    Binding:         STB_GLOBAL
+  - Name:            main
+    Type:            STT_FUNC
+    Section:         .anothertext
+    Value:           0x0000000000000010
+    Size:            0x000000000000003F
+    Binding:         STB_GLOBAL
+  - Name:            foo
+    Type:            STT_FUNC
+    Section:         .text
+    Size:            0x0000000000000004
+    Binding:         STB_GLOBAL
+  - Name:            bar
+    Type:            STT_FUNC
+    Section:         .text
+    Value:           0x0000000000000004
+    Size:            0x000000000000000A
+    Binding:         STB_GLOBAL
+  - Name:            a
+    Type:            STT_OBJECT
+    Section:         .data
+    Value:           0x00000000000000A8
+    Size:            0x0000000000000004
+    Binding:         STB_GLOBAL
+...

llvm/test/tools/llvm-objdump/X86/disassemble-sorted.test

+## show that --sort does something
+
+# RUN: yaml2obj -o %t.out %p/Inputs/sort-test.yaml
+# RUN: llvm-objdump -d %t.out --sort \
+# RUN:   | FileCheck %s --check-prefix=CHECK-SORTED
+# RUN: llvm-objdump -d %t.out  \
+# RUN:   | FileCheck %s --check-prefix=CHECK-UNSORTED
+
+# CHECK-SORTED: bar:
+# CHECK-SORTED: foo:
+# CHECK-SORTED: main:
+# CHECK-UNSORTED: foo:
+# CHECK-UNSORTED: bar:
+# CHECK-UNSORTED: main:
+
+

llvm/tools/llvm-objdump/llvm-objdump.cpp

static cl::alias SectionHeadersShorter("h",
                                        cl::NotHidden, cl::Grouping,
                                        cl::aliasopt(SectionHeaders));
 
 static cl::opt<bool>
     ShowLMA("show-lma",
             cl::desc("Display LMA column when dumping ELF section headers"),
             cl::cat(ObjdumpCat));
 
+static cl::opt<bool> Sort("sort", cl::desc("Sort Symbols when Disassembling"),
+                          cl::cat(ObjdumpCat));
+
 static cl::opt<bool> PrintSource(
     "source",
     cl::desc(
         "Display source inlined with disassembly. Implies disassemble object"),
     cl::cat(ObjdumpCat));
 static cl::alias PrintSourceShort("S", cl::desc("Alias for -source"),
                                   cl::NotHidden, cl::Grouping,
                                   cl::aliasopt(PrintSource));
static const Target *getTarget(const ObjectFile *Obj) {
   TripleName = TheTriple.getTriple();
   return TheTarget;
 }
 
 bool isRelocAddressLess(RelocationRef A, RelocationRef B) {
   return A.getOffset() < B.getOffset();
 }
 
+// Sort strings, keeping track of the original order with the second entry.
+bool SymbolNameOrder(std::tuple<StringRef, int> A,
+                     std::tuple<StringRef, int> B) {
+  return std::get<0>(A) < std::get<0>(B);
+}
+
 static Error getRelocationValueString(const RelocationRef &Rel,
                                       SmallVectorImpl<char> &Result) {
   const ObjectFile *Obj = Rel.getObject();
   if (auto *ELF = dyn_cast<ELFObjectFileBase>(Obj))
     return getELFRelocationValueString(ELF, Rel, Result);
   if (auto *COFF = dyn_cast<COFFObjectFile>(Obj))
     return getCOFFRelocationValueString(COFF, Rel, Result);
   if (auto *Wasm = dyn_cast<WasmObjectFile>(Obj))
for (const SymbolRef &Symbol : Obj->symbols()) {
 
     uint8_t SymbolType = ELF::STT_NOTYPE;
     if (Obj->isELF()) {
       SymbolType = getElfSymbolType(Obj, Symbol);
       if (SymbolType == ELF::STT_SECTION)
         continue;
     }
 
-    // Don't ask a Mach-O STAB symbol for its section unless you know that 
+    // Don't ask a Mach-O STAB symbol for its section unless you know that
     // STAB symbol's section field refers to a valid section index. Otherwise
     // the symbol may error trying to load a section that does not exist.
     if (MachO) {
       DataRefImpl SymDRI = Symbol.getRawDataRefImpl();
       uint8_t NType = (MachO->is64Bit() ?
                        MachO->getSymbol64TableEntry(SymDRI).n_type:
                        MachO->getSymbolTableEntry(SymDRI).n_type);
       if (NType & MachO::N_STAB)
if (shouldAdjustVA(Section))
       VMAAdjustment = AdjustVMA;
 
     uint64_t Size;
     uint64_t Index;
     bool PrintedSection = false;
     std::vector<RelocationRef> Rels = RelocMap[Section];
     std::vector<RelocationRef>::const_iterator RelCur = Rels.begin();
     std::vector<RelocationRef>::const_iterator RelEnd = Rels.end();
-    // Disassemble symbol by symbol.
+
+    // name, index
+    typedef std::vector<std::tuple<StringRef, int>> SortedSectionSymbolsTy;
+    SortedSectionSymbolsTy sortedSymbols;
+    sortedSymbols.reserve(Symbols.size());
     for (unsigned SI = 0, SE = Symbols.size(); SI != SE; ++SI) {
+      sortedSymbols.emplace_back(Symbols[SI].Name, SI);
+    }
+    if (Sort)
+      llvm::stable_sort(sortedSymbols, SymbolNameOrder);
+
+    // Disassemble symbol by symbol.
+    for (unsigned SJ = 0, SE = sortedSymbols.size(); SJ != SE; ++SJ) {
+      unsigned SI = std::get<1>(sortedSymbols[SJ]);
       std::string SymbolName = Symbols[SI].Name.str();
       if (Demangle)
         SymbolName = demangle(SymbolName);
 
       // Skip if --disassemble-functions is not empty and the symbol is not in
       // the list.
       if (!DisasmFuncsSet.empty() && !DisasmFuncsSet.count(SymbolName))
         continue;
 
       uint64_t Start = Symbols[SI].Addr;
       if (Start < SectionAddr || StopAddress <= Start)
for (auto I = O->symbol_begin(), E = O->symbol_end(); I != E; ++I) {
     uint64_t Address = unwrapOrError(Symbol.getAddress(), FileName, ArchiveName,
                                      ArchitectureName);
     if ((Address < StartAddress) || (Address > StopAddress))
       continue;
     SymbolRef::Type Type = unwrapOrError(Symbol.getType(), FileName,
                                          ArchiveName, ArchitectureName);
     uint32_t Flags = Symbol.getFlags();
 
-    // Don't ask a Mach-O STAB symbol for its section unless you know that 
+    // Don't ask a Mach-O STAB symbol for its section unless you know that
     // STAB symbol's section field refers to a valid section index. Otherwise
     // the symbol may error trying to load a section that does not exist.
     bool isSTAB = false;
     if (MachO) {
       DataRefImpl SymDRI = Symbol.getRawDataRefImpl();
       uint8_t NType = (MachO->is64Bit() ?
                        MachO->getSymbol64TableEntry(SymDRI).n_type:
                        MachO->getSymbolTableEntry(SymDRI).n_type);