Fix llvm-symbolizer to correctly sort a symbol array and calculate symbol sizes

[kubamracek]

Summary

I noticed that llvm-symbolizer gives wrong results sometimes, this was due to incorrect sizes of some symbols. The reason for that was an incorrectly sorted array in computeSymbolSizes. The comparison function used subtraction of unsigned types, which is incorrect. Let's change this to return explicit -1 or 1.

[kubamracek]

testcase?

Unfortunately, it's hard to come up with a reasonable testcase because the issue is hard to reproduce on small inputs (because the sorting usually works and only edge cases sort incorrectly). One of compiler-rt tests fail due to this, however. So with this patch, I can enable the test again. Is that enough?

[kubamracek]

Is it possible to manufacture a test in unittests/Object/ ?

I spend some time trying to, and I'm giving up on writing a subclass of ObjectFile that I could give to computeSymbolSizes. The best I could come up with was to pull SymEntry and compareAddress into a header file and just test that array_pod_sort sorts correctly. Will that do?

[kubamracek]

Updating patch with a unittest.

[dberris]

unittests/Object/SymbolSizeTest.cpp

17–25 ↗

(On Diff #77699)

This looks like you can use an initialiser list instead:

auto it = symbol_iterator(SymbolRef());
std::vector<SymEntry> Syms{
  SymEntry{it, ...},
  SymEntry{it, ...}};

29–31 ↗

(On Diff #77699)

How about using something like std::is_sorted(...)?

33 ↗

(On Diff #77699)

Do you even need this?

[kubamracek]

unittests/Object/SymbolSizeTest.cpp

17–25 ↗

(On Diff #77699)

Right.

29–31 ↗

(On Diff #77699)

The test is trying to make sure the sorting predicate is correct. Using is_sorted with the same predicate that sorted the array will not test that.

33 ↗

(On Diff #77699)

Right, this shouldn't be here.

[dberris]

lib/Object/SymbolSize.cpp

19–25 ↗

(On Diff #77835)

It would be good to document what the ordering guarantees are at the interface level for this function -- for instance, is this a strict weak ordering on (section id, address)?

[kubamracek]

LLVM: r287028
compiler-rt: r287029

llvm/trunk/include/llvm/Object/SymbolSize.h

 
 #ifndef LLVM_OBJECT_SYMBOLSIZE_H
 #define LLVM_OBJECT_SYMBOLSIZE_H
 
 #include "llvm/Object/ObjectFile.h"
 
 namespace llvm {
 namespace object {
+
+struct SymEntry {
+  symbol_iterator I;
+  uint64_t Address;
+  unsigned Number;
+  unsigned SectionID;
+};
+
+int compareAddress(const SymEntry *A, const SymEntry *B);
+
 std::vector<std::pair<SymbolRef, uint64_t>>
 computeSymbolSizes(const ObjectFile &O);
+
 }
 } // namespace llvm
 
 #endif

llvm/trunk/lib/Object/SymbolSize.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Object/COFF.h"
 #include "llvm/Object/ELFObjectFile.h"
 #include "llvm/Object/MachO.h"
 
 using namespace llvm;
 using namespace object;
 
-namespace {
-struct SymEntry {
-  symbol_iterator I;
-  uint64_t Address;
-  unsigned Number;
-  unsigned SectionID;
-};
-}
-
-static int compareAddress(const SymEntry *A, const SymEntry *B) {
+// Orders increasingly by (SectionID, Address).
+int llvm::object::compareAddress(const SymEntry *A, const SymEntry *B) {
   if (A->SectionID != B->SectionID)
-    return A->SectionID - B->SectionID;
-  return A->Address - B->Address;
+    return A->SectionID < B->SectionID ? -1 : 1;
+  if (A->Address != B->Address)
+    return A->Address < B->Address ? -1 : 1;
+  return 0;
 }
 
 static unsigned getSectionID(const ObjectFile &O, SectionRef Sec) {
   if (auto *M = dyn_cast<MachOObjectFile>(&O))
     return M->getSectionID(Sec);
   return cast<COFFObjectFile>(O).getSectionID(Sec);
 }
 

llvm/trunk/unittests/CMakeLists.txt

 add_subdirectory(CodeGen)
 add_subdirectory(DebugInfo)
 add_subdirectory(ExecutionEngine)
 add_subdirectory(IR)
 add_subdirectory(LineEditor)
 add_subdirectory(Linker)
 add_subdirectory(MC)
 add_subdirectory(MI)
+add_subdirectory(Object)
 add_subdirectory(ObjectYAML)
 add_subdirectory(Option)
 add_subdirectory(ProfileData)
 add_subdirectory(Support)
 add_subdirectory(Target)
 add_subdirectory(Transforms)

llvm/trunk/unittests/Object/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  Object
+  )
+
+add_llvm_unittest(ObjectTests
+  SymbolSizeTest.cpp
+  )
+

llvm/trunk/unittests/Object/SymbolSizeTest.cpp

+//===- SymbolSizeTest.cpp - Tests for SymbolSize.cpp ----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Object/SymbolSize.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+using namespace llvm::object;
+
+TEST(Object, SymbolSizeSort) {
+  auto it = symbol_iterator(SymbolRef());
+  std::vector<SymEntry> Syms{
+      SymEntry{it, 0xffffffff00000000ull, 1, 0},
+      SymEntry{it, 0x00ffffff00000000ull, 2, 0},
+      SymEntry{it, 0x00ffffff000000ffull, 3, 0},
+      SymEntry{it, 0x0000000100000000ull, 4, 0},
+      SymEntry{it, 0x00000000000000ffull, 5, 0},
+      SymEntry{it, 0x00000001000000ffull, 6, 0},
+      SymEntry{it, 0x000000010000ffffull, 7, 0},
+  };
+
+  array_pod_sort(Syms.begin(), Syms.end(), compareAddress);
+
+  for (unsigned I = 0, N = Syms.size(); I < N - 1; ++I) {
+    EXPECT_LE(Syms[I].Address, Syms[I + 1].Address);
+  }
+}