[llvm-ar][Object] Fix detection of need for 64-bit archive symbol tables

[andrewng]

Summary

The code to detect the requirement for 64-bit offsets in the archive
symbol table was not correctly accounting for the archive file signature
and the size of all the contents of the symbol table itself, e.g. the
symbol table's header and string table. Also was not considering the
variation in symbol table formats. This could result in the creation of
large archives with a corrupt symbol table.

Change the testing environment variable SYM64_THRESHOLD to be an
absolute value rather than a power of 2 in order to enable precise
testing of this detection code.

[MaskRay]

I understand that a test may be problematic because it requires 4+GiB output. Do you have a script to craft such a test case so that people working on llvm-ar can run it on demand? The test can have UNSUPPORTED: *.

[grimar]

llvm/lib/Object/ArchiveWriter.cpp

294

Size is a size of the symbol table, not a number of entries, right? Though I am not sure it makes much sense to have a comment about it, I think it is clear from the function name?

337

Perhaps just is64BitKind(Kind) ? 8 : 4? (it is a very often used construction in LLVM).

610

I was a bit confused when saw writeSymbolTableHeader here.
Kind can be changed below:

if (LastOffset >= (1ULL << Sym64Threshold)) {
  if (Kind == object::Archive::K_DARWIN)
    Kind = object::Archive::K_DARWIN64;
  else
    Kind = object::Archive::K_GNU64;
}

I think would be more natural to call writeSymbolTableHeader after last possible modification of Kind, i.e. after this code block. Is it possible?

[grimar]

llvm/lib/Object/ArchiveWriter.cpp

294

Ah, I see now. It describes that the number of entries is written first.

[andrewng]

Updated to address review comments and updated to add better testing. Whilst adding this testing, found another bug in the detection code; it was also not accounting for the size of the file signature!

[grimar]

llvm/lib/Object/ArchiveWriter.cpp

610

This wasn't addressed?

aside: could you please mask addressed comments as "Done"? So that reviewers can see the status.

610

mask -> mark

[andrewng]

In D89891#2345374, @MaskRay wrote:

I understand that a test may be problematic because it requires 4+GiB output. Do you have a script to craft such a test case so that people working on llvm-ar can run it on demand? The test can have UNSUPPORTED: *.

No, I don't have such a script. I actually had a use case that was showing the issue. I've updated the existing testing to be more precise to provide coverage.

llvm/lib/Object/ArchiveWriter.cpp

610

This call to writeSymbolTableHeader is purely used to determine the size of the header and is not a write to the output which happens later.

[grimar]

llvm/lib/Object/ArchiveWriter.cpp

610

This call to writeSymbolTableHeader is purely used to determine the size of the header and is not a write to the output which happens later.

writeSymbolTableHeader still uses Kind. It is just not clean to give it one Kind and change it to another later.

[andrewng]

llvm/lib/Object/ArchiveWriter.cpp

610

But this is by design. This call to writeSymbolTableHeader is used as part of the calculation of the 32-bit symbol table size in order to determine whether a 64-bit symbol table is required. If this is required, then the Kind is changed and the appropriate format is output. Does that make sense?

[grimar]

llvm/lib/Object/ArchiveWriter.cpp

610

I believe that the behavior of original code was:

1. Calculate the size of the symbol table.
2. Switch to 64-bit symbol table Kind if needed.
3. Write the header and the body of the symbol table in one move.

Now the behavior with this patch is:

1. Calculate the size of the symbol table.
2. Write the symbol table header using the Kind (Kind1) we have at this step.
3. Switch to 64-bit symbol table Kind (Kind2) if needed.
4. Write the body of the symbol table using the new Kind (Kind2)

computeSymbolTableSize uses Kind for isBSDLike(Kind) call.
Perhaps instead of Kind it could take bool IsBSDLike? That way we know that
changing of Kind from 32->64 does not affect anything. What do you think?

[andrewng]

llvm/lib/Object/ArchiveWriter.cpp

610

Sorry if I haven't explained clearly, but the behaviour with this patch is:

1. Correctly calculate LastOffset including the correct calculation for the 32-bit symbol table size and also include the file signature.
2. The above calculation includes a call to writeSymbolTableHeader with the original Kind to a temporary buffer in order to determine the symbol table header size.
3. Switch to a 64-bit symbol table Kind if required.
4. Write archive which includes a call to writeSymbolTableHeader with the final Kind and the actual output buffer.

Hope that clarifies the situation.

[andrewng]

llvm/lib/Object/ArchiveWriter.cpp

610

Perhaps it would make it clearer if I wrap this use of writeSymbolTableHeader (in point 2 above) in a function such as computeSymbolTableHeaderSize? Although this would be the only place that it would be used. What do you think?

[grimar]

llvm/lib/Object/ArchiveWriter.cpp

610

Perhaps it would make it clearer if I wrap this use of writeSymbolTableHeader (in point 2 above) in a function such as computeSymbolTableHeaderSize

Makes sense I think. Probably you can just have a lambda names like that instead of having a function.

610

names -> named

[andrewng]

Update to clarify the purpose of the initial call to writeSymbolTableHeader.

[grimar]

I think this reads much better, thanks! I have no more comments.

[jyknight]

LGTM.

llvm/lib/Object/ArchiveWriter.cpp

 static void printNBits(raw_ostream &Out, object::Archive::Kind Kind,
                        uint64_t Val) {
   if (is64BitKind(Kind))
     print<uint64_t>(Out, Kind, Val);
   else
     print<uint32_t>(Out, Kind, Val);
 }
 
-static void writeSymbolTable(raw_ostream &Out, object::Archive::Kind Kind,
-                             bool Deterministic, ArrayRef<MemberData> Members,
-                             StringRef StringTable) {
-  // We don't write a symbol table on an archive with no members -- except on
-  // Darwin, where the linker will abort unless the archive has a symbol table.
-  if (StringTable.empty() && !isDarwin(Kind))
-    return;
-
-  unsigned NumSyms = 0;
-  for (const MemberData &M : Members)
-    NumSyms += M.Symbols.size();
-
-  unsigned Size = 0;
-  unsigned OffsetSize = is64BitKind(Kind) ? sizeof(uint64_t) : sizeof(uint32_t);
-
-  Size += OffsetSize; // Number of entries
+static uint64_t computeSymbolTableSize(object::Archive::Kind Kind,
+                                       uint64_t NumSyms, uint64_t OffsetSize,
+                                       StringRef StringTable,
+                                       uint32_t *Padding = nullptr) {
+  assert((OffsetSize == 4 || OffsetSize == 8) && "Unsupported OffsetSize");
+  uint64_t Size = OffsetSize; // Number of entries
   if (isBSDLike(Kind))
     Size += NumSyms * OffsetSize * 2; // Table
   else
     Size += NumSyms * OffsetSize; // Table
   if (isBSDLike(Kind))
     Size += OffsetSize; // byte count
   Size += StringTable.size();
   // ld64 expects the members to be 8-byte aligned for 64-bit content and at
   // least 4-byte aligned for 32-bit content.  Opt for the larger encoding
   // uniformly.
   // We do this for all bsd formats because it simplifies aligning members.
-  const Align Alignment(isBSDLike(Kind) ? 8 : 2);
-  unsigned Pad = offsetToAlignment(Size, Alignment);
+  uint32_t Pad = offsetToAlignment(Size, Align(isBSDLike(Kind) ? 8 : 2));
   Size += Pad;
+  if (Padding)
+    *Padding = Pad;
+  return Size;
+}
 
+static void writeSymbolTableHeader(raw_ostream &Out, object::Archive::Kind Kind,
+                                   bool Deterministic, uint64_t Size) {
   if (isBSDLike(Kind)) {
     const char *Name = is64BitKind(Kind) ? "__.SYMDEF_64" : "__.SYMDEF";
     printBSDMemberHeader(Out, Out.tell(), Name, now(Deterministic), 0, 0, 0,
                          Size);
   } else {
     const char *Name = is64BitKind(Kind) ? "/SYM64" : "";
     printGNUSmallMemberHeader(Out, Name, now(Deterministic), 0, 0, 0, Size);
   }
+}
+
+static void writeSymbolTable(raw_ostream &Out, object::Archive::Kind Kind,
+                             bool Deterministic, ArrayRef<MemberData> Members,
+                             StringRef StringTable) {
+  // We don't write a symbol table on an archive with no members -- except on
+  // Darwin, where the linker will abort unless the archive has a symbol table.
+  if (StringTable.empty() && !isDarwin(Kind))
+    return;
+
+  unsigned NumSyms = 0;
+  for (const MemberData &M : Members)
+    NumSyms += M.Symbols.size();
+
+  uint64_t OffsetSize = is64BitKind(Kind) ? 8 : 4;
+  uint32_t Pad;
+  uint64_t Size = computeSymbolTableSize(Kind, NumSyms, OffsetSize, StringTable, &Pad);
+  writeSymbolTableHeader(Out, Kind, Deterministic, Size);
 
   uint64_t Pos = Out.tell() + Size;
 
   if (isBSDLike(Kind))
     printNBits(Out, Kind, NumSyms * 2 * OffsetSize);
   else
     printNBits(Out, Kind, NumSyms);
 
if (Error E = DataOrErr.takeError())
     return E;
   std::vector<MemberData> &Data = *DataOrErr;
 
   if (!StringTableBuf.empty())
     Data.insert(Data.begin(), computeStringTable(StringTableBuf));
 
   // We would like to detect if we need to switch to a 64-bit symbol table.
   if (WriteSymtab) {
-    uint64_t MaxOffset = 0;
+    uint64_t MaxOffset = 8; // For the file signature.
     uint64_t LastOffset = MaxOffset;
+    uint64_t NumSyms = 0;
     for (const auto &M : Data) {
       // Record the start of the member's offset
       LastOffset = MaxOffset;
       // Account for the size of each part associated with the member.
       MaxOffset += M.Header.size() + M.Data.size() + M.Padding.size();
-      // We assume 32-bit symbols to see if 32-bit symbols are possible or not.
-      MaxOffset += M.Symbols.size() * 4;
+      NumSyms += M.Symbols.size();
     }
 
+    // We assume 32-bit offsets to see if 32-bit symbols are possible or not.
+    uint64_t SymtabSize = computeSymbolTableSize(Kind, NumSyms, 4, SymNamesBuf);
+    auto computeSymbolTableHeaderSize =
+        [=] {
+          SmallString<0> TmpBuf;
+          raw_svector_ostream Tmp(TmpBuf);
+          writeSymbolTableHeader(Tmp, Kind, Deterministic, SymtabSize);
+          return TmpBuf.size();
+        };
+    LastOffset += computeSymbolTableHeaderSize() + SymtabSize;
+
     // The SYM64 format is used when an archive's member offsets are larger than
     // 32-bits can hold. The need for this shift in format is detected by
     // writeArchive. To test this we need to generate a file with a member that
     // has an offset larger than 32-bits but this demands a very slow test. To
     // speed the test up we use this environment variable to pretend like the
     // cutoff happens before 32-bits and instead happens at some much smaller
     // value.
+    uint64_t Sym64Threshold = 1ULL << 32;
     const char *Sym64Env = std::getenv("SYM64_THRESHOLD");
-    int Sym64Threshold = 32;
     if (Sym64Env)
       StringRef(Sym64Env).getAsInteger(10, Sym64Threshold);
 
     // If LastOffset isn't going to fit in a 32-bit varible we need to switch
     // to 64-bit. Note that the file can be larger than 4GB as long as the last
     // member starts before the 4GB offset.
-    if (LastOffset >= (1ULL << Sym64Threshold)) {
+    if (LastOffset >= Sym64Threshold) {
       if (Kind == object::Archive::K_DARWIN)
         Kind = object::Archive::K_DARWIN64;
       else
         Kind = object::Archive::K_GNU64;
     }
   }
 
   if (Thin)

llvm/test/Object/archive-symtab.test

- Name:    main
     Binding: STB_GLOBAL
     Value:   0x0000000000000016
 
 # RUN: rm -f %t.a
 # RUN: llvm-ar rcsU %t.a %t.elf-x86-64 %t2.elf-x86-64
 # RUN: llvm-nm -M %t.a | FileCheck %s
 
 # RUN: rm -f %t.a
-# RUN: env SYM64_THRESHOLD=1 llvm-ar rcsU %t.a %t.elf-x86-64 %t2.elf-x86-64
+# RUN: env SYM64_THRESHOLD=836 llvm-ar rcsU %t.a %t.elf-x86-64 %t2.elf-x86-64
 # RUN: llvm-nm -M %t.a | FileCheck %s
-# RUXX: grep SYM64 %t.a
+# RUN: grep '/SYM64/' %t.a
+
+# RUN: rm -f %t.a
+# RUN: env SYM64_THRESHOLD=837 llvm-ar rcsU %t.a %t.elf-x86-64 %t2.elf-x86-64
+# RUN: llvm-nm -M %t.a | FileCheck %s
+# RUN: not grep '/SYM64/' %t.a
 
 # CHECK: Archive map
 # CHECK-NEXT: main in {{.*}}.elf-x86-64
 # CHECK-NEXT: foo in {{.*}}2.elf-x86-64
 # CHECK-NEXT: main in {{.*}}2.elf-x86-64
 # CHECK-NOT: bar
 
 

 # BSD-MachO: _bar in bar.o
 # BSD-MachO: _foo in foo.o
 
 # RUN: rm -f %t.a
 # RUN: llvm-ar --format=bsd rcsU %t.a %p/Inputs/trivial-object-test.macho-x86-64 %p/Inputs/trivial-object-test2.macho-x86-64
 # RUN: llvm-nm -M %t.a | FileCheck --check-prefix=MACHO %s
 
 # RUN: rm -f %t.a
-# RUN: env SYM64_THRESHOLD=1 llvm-ar --format=darwin rcsU %t.a %p/Inputs/trivial-object-test.macho-x86-64 %p/Inputs/trivial-object-test2.macho-x86-64
+# RUN: env SYM64_THRESHOLD=784 llvm-ar --format=darwin rcsU %t.a %p/Inputs/trivial-object-test.macho-x86-64 %p/Inputs/trivial-object-test2.macho-x86-64
 # RUN: llvm-nm -M %t.a | FileCheck --check-prefix=MACHO %s
 # RUN: grep '__\.SYMDEF_64' %t.a
 
+# RUN: rm -f %t.a
+# RUN: env SYM64_THRESHOLD=785 llvm-ar --format=darwin rcsU %t.a %p/Inputs/trivial-object-test.macho-x86-64 %p/Inputs/trivial-object-test2.macho-x86-64
+# RUN: llvm-nm -M %t.a | FileCheck --check-prefix=MACHO %s
+# RUN: not grep '__\.SYMDEF_64' %t.a
+
 # MACHO: Archive map
 # MACHO-NEXT: _main in trivial-object-test.macho-x86-64
 # MACHO-NEXT: _foo in trivial-object-test2.macho-x86-64
 # MACHO-NEXT: _main in trivial-object-test2.macho-x86-64
 # MACHO-NOT: {{^}}bar
 
 # MACHO: trivial-object-test.macho-x86-64
 # MACHO-NEXT: 0000000000000028 s L_.str