[lld-macho] Warn on method name collisions from category definitions

[int3]

Summary

This implements ld64's checks for duplicate method names in categories &
classes.

In addition, this sets us up for implementing Obj-C category merging.
This diff handles the most of the parsing work; what's left is rewriting
those category / class structures.

Numbers for chromium_framework:

           base           diff           difference (95% CI)
sys_time   2.182 ± 0.027  2.200 ± 0.047  [  -0.2% ..   +1.8%]
user_time  6.451 ± 0.034  6.479 ± 0.062  [  -0.0% ..   +0.9%]
wall_time  6.841 ± 0.048  6.885 ± 0.105  [  -0.1% ..   +1.4%]
samples    33             22

Fixes https://github.com/llvm/llvm-project/issues/54912.

[int3]

update test

[int3]

update

[int3]

namespace

[int3]

update

[int3]

more test updates

[thevinster]

lld/MachO/Layout.h

21–25

Not against the macros, but it did take me a while to grok this and visualize what it produces. The "equivalent" is useful to some extent if I'm just trying to get an idea. But, I think it would be more useful to just show the exact text that it produces after preprocessing.

In this example, it would be

struct FooLayout {
  uint32_t barOffset;
  uint32_t bazOffset;
  
  FooLayout(size_t wordSize) {
    if (wordSize == 8)
      init<uint64_t>(); 
    else {
      assert(wordSize == 4); 
      init<uint32_t>(); 
    }  
  }    
  
  private:
   ....
};

27

type looks unused here. Should this have been type name##Offset?

lld/MachO/ObjC.cpp

196

Could we have a better variable name than just s? Maybe methodName?

231

ld64 also checks for class/instance properties. Just wondering, if the plan for that was to implement that in a follow up or if that was forgotten.

284–290

Benchmarks don't show a huge regression, but would it better to parallelize this loop? The only downside I see is warning diagnostics being indeterministic, but that might be a blocker for others.

[int3]

lld/MachO/Layout.h

21–25

sounds good!

27

no, uint32_t is indeed desired (it's the type of the offset, not the type of the field)

It's unused because FOR_EACH_FIELD expects a macro argument that itself takes 2 params. I'll rename this to _ to make it clear that it's supposed to be unused

lld/MachO/ObjC.cpp

231

does it? I mean I see that it parses & handles them as part of category merging. But I don't think it does any validation / raises any warnings for those -- at least, I didn't see any related warnings in ld64's objc pass

284–290

I want to wait till the category merging itself is implemented before attempting parallelization

I might also just delay landing this for a while

[int3]

address comments

[thevinster]

lld/MachO/ObjC.cpp

231

👍 I didn't read it in close detail until now. Yep it looks like it's only being parsed for the actual objc-optimization as opposed to the warnings. Carry on...

[oontvoo]

Thanks!

lld/MachO/Driver.cpp

1918

maybe conditioned this under -ObjC ? (i mean, no reason to do the checks, walking thru lots of isecs if we know there's no objc code?)

lld/MachO/ObjC.cpp

284–290

We'd love to have this check asap =)

(This should fix https://github.com/llvm/llvm-project/issues/54912)

[int3]

lld/MachO/Driver.cpp

1918

Heh we actually have builds that contain ObjC but don't use the -ObjC flag

lld/MachO/ObjC.cpp

284–290

ok, will land it soon :)

[int3]

lld/MachO/ObjC.cpp

284–290

actually, it might be a while -- I'm seeing some crashes when running this on our builds

[oontvoo]

Seems to cause segfaults in a lot of our builds .... :( Should we possibly revert this while investigating?

[int3]

Reverted. A repro would be helpful!

[oontvoo]

In D142916#4179641, @int3 wrote:

Reverted. A repro would be helpful!

Thanks! Working on making a small repro - will share when ready

[int3]

JFYI I have a repro of this -- will put up the fix soon (I found other issues along the way)

lld/MachO/Driver.cpp

if (config->timeTraceEnabled)
 
     gatherInputSections();
     if (config->callGraphProfileSort)
       priorityBuilder.extractCallGraphProfile();
 
     if (config->deadStrip)
       markLive();
 
+    objc::checkCategories();
+
     // ICF assumes that all literals have been folded already, so we must run
     // foldIdenticalLiterals before foldIdenticalSections.
     foldIdenticalLiterals();
     if (config->icfLevel != ICFLevel::none) {
       if (config->icfLevel == ICFLevel::safe)
         markAddrSigSymbols();
       foldIdenticalSections(/*onlyCfStrings=*/false);
     } else if (config->dedupStrings) {

lld/MachO/InputFiles.cpp

case 'R': {
                                Twine::utohexstr(pointerEnc));
       break;
     }
     default:
       break;
     }
   }
   if (personalityAddrOff != 0) {
-    auto personalityRelocIt =
-        llvm::find_if(isec->relocs, [=](const macho::Reloc &r) {
-          return r.offset == personalityAddrOff;
-        });
-    if (personalityRelocIt == isec->relocs.end())
+    const auto *personalityReloc = isec->getRelocAt(personalityAddrOff);
+    if (!personalityReloc)
       reader.failOn(off, "Failed to locate relocation for personality symbol");
-    cie.personalitySymbol = personalityRelocIt->referent.get<macho::Symbol *>();
+    cie.personalitySymbol = personalityReloc->referent.get<macho::Symbol *>();
   }
   return cie;
 }
 
 // EH frame target addresses may be encoded as pcrel offsets. However, instead
 // of using an actual pcrel reloc, ld64 emits subtractor relocations instead.
 // This function recovers the target address from the subtractors, essentially
 // performing the inverse operation of EhRelocator.

lld/MachO/InputSection.h

public:
   // The offset from the beginning of the file.
   uint64_t getVA(uint64_t off) const;
   // Return a user-friendly string for use in diagnostics.
   // Format: /path/to/object.o:(symbol _func+0x123)
   std::string getLocation(uint64_t off) const;
   // Return the source line corresponding to an address, or the empty string.
   // Format: Source.cpp:123 (/path/to/Source.cpp:123)
   std::string getSourceLocation(uint64_t off) const;
+  // Return the relocation at \p off, if it exists. This does a linear search.
+  const Reloc *getRelocAt(uint32_t off) const;
   // Whether the data at \p off in this InputSection is live.
   virtual bool isLive(uint64_t off) const = 0;
   virtual void markLive(uint64_t off) = 0;
   virtual InputSection *canonical() { return this; }
   virtual const InputSection *canonical() const { return this; }
 
 protected:
   InputSection(Kind kind, const Section &section, ArrayRef<uint8_t> data,
StringRef getStringRef(size_t i) const {
     size_t begin = pieces[i].inSecOff;
     // The endpoint should be *at* the null terminator, not after. This matches
     // the behavior of StringRef(const char *Str).
     size_t end =
         ((pieces.size() - 1 == i) ? data.size() : pieces[i + 1].inSecOff) - 1;
     return toStringRef(data.slice(begin, end - begin));
   }
 
+  StringRef getStringRefAtOffset(uint64_t off) const {
+    return getStringRef(getStringPieceIndex(off));
+  }
+
   // Returns i'th piece as a CachedHashStringRef. This function is very hot when
   // string merging is enabled, so we want to inline.
   LLVM_ATTRIBUTE_ALWAYS_INLINE
   llvm::CachedHashStringRef getCachedHashStringRef(size_t i) const {
     assert(deduplicateLiterals);
     return {getStringRef(i), pieces[i].hash};
   }
 
   static bool classof(const InputSection *isec) {
     return isec->kind() == CStringLiteralKind;
   }
 
   bool deduplicateLiterals = false;
   std::vector<StringPiece> pieces;
+
+private:
+  size_t getStringPieceIndex(uint64_t off) const;
 };
 
 class WordLiteralInputSection final : public InputSection {
 public:
   WordLiteralInputSection(const Section &section, ArrayRef<uint8_t> data,
                           uint32_t align);
   uint64_t getOffset(uint64_t off) const override;
   bool isLive(uint64_t off) const override {

lld/MachO/InputSection.cpp

std::string InputSection::getSourceLocation(uint64_t off) const {
 
   // Try to get the source file's name from the DWARF information.
   if (obj->compileUnit)
     return obj->sourceFile();
 
   return {};
 }
 
+const Reloc *InputSection::getRelocAt(uint32_t off) const {
+  auto it = llvm::find_if(
+      relocs, [=](const macho::Reloc &r) { return r.offset == off; });
+  if (it == relocs.end())
+    return nullptr;
+  return &*it;
+}
+
 void ConcatInputSection::foldIdentical(ConcatInputSection *copy) {
   align = std::max(align, copy->align);
   copy->live = false;
   copy->wasCoalesced = true;
   copy->replacement = this;
   for (auto &copySym : copy->symbols) {
     copySym->wasIdenticalCodeFolded = true;
     copySym->size = 0;
auto it =
       partition_point(pieces, [=](StringPiece p) { return p.inSecOff <= off; });
   return it[-1];
 }
 
 const StringPiece &CStringInputSection::getStringPiece(uint64_t off) const {
   return const_cast<CStringInputSection *>(this)->getStringPiece(off);
 }
 
+size_t CStringInputSection::getStringPieceIndex(uint64_t off) const {
+  if (off >= data.size())
+    fatal(toString(this) + ": offset is outside the section");
+
+  auto it =
+      partition_point(pieces, [=](StringPiece p) { return p.inSecOff <= off; });
+  return std::distance(pieces.begin(), it) - 1;
+}
+
 uint64_t CStringInputSection::getOffset(uint64_t off) const {
   const StringPiece &piece = getStringPiece(off);
   uint64_t addend = off - piece.inSecOff;
   return piece.outSecOff + addend;
 }
 
 WordLiteralInputSection::WordLiteralInputSection(const Section &section,
                                                  ArrayRef<uint8_t> data,

lld/MachO/Layout.h

+//===- Layout.h -----------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// Convenience macros for obtaining offsets of members in structs.
+//
+// Usage:
+//
+//   #define FOR_EACH_FOO_FIELD(DO) \
+//     DO(Ptr, bar)                 \
+//     DO(uint32_t, baz)            \
+//   CREATE_LAYOUT_CLASS(Foo, FOR_EACH_FOO_FIELD)
+//   #undef FOR_EACH_FOO_FIELD
+//
+// This will generate the equivalent of
+//
+//   struct FooLayout {
+//     uint32_t barOffset = 0;
+//     uint32_t bazOffset = sizeof(uintptr_t);
+//     uint32_t totalSize = sizeof(uintptr_t) + sizeof(uint32_t);
+//   };
+
+#define _OFFSET_FOR_FIELD(type, name) uint32_t name##Offset;
+#define _INIT_OFFSET(type, name) name##Offset = offsetof(Layout<Ptr>, name);
+#define _LAYOUT_ENTRY(type, name) type name;
+
+#define CREATE_LAYOUT_CLASS(className, FOR_EACH_FIELD)                         \
+  struct className##Layout {                                                   \
+    FOR_EACH_FIELD(_OFFSET_FOR_FIELD)                                          \
+    uint32_t totalSize;                                                        \
+                                                                               \
+    className##Layout(size_t wordSize) {                                       \
+      if (wordSize == 8)                                                       \
+        init<uint64_t>();                                                      \
+      else {                                                                   \
+        assert(wordSize == 4);                                                 \
+        init<uint32_t>();                                                      \
+      }                                                                        \
+    }                                                                          \
+                                                                               \
+  private:                                                                     \
+    template <class Ptr> void init() {                                         \
+      FOR_EACH_FIELD(_INIT_OFFSET);                                            \
+      totalSize = sizeof(Layout<Ptr>);                                         \
+    }                                                                          \
+    template <class Ptr> struct Layout {                                       \
+      FOR_EACH_FIELD(_LAYOUT_ENTRY)                                            \
+    };                                                                         \
+  }

lld/MachO/ObjC.h

 
 namespace objc {
 
 constexpr const char klass[] = "_OBJC_CLASS_$_";
 constexpr const char metaclass[] = "_OBJC_METACLASS_$_";
 constexpr const char ehtype[] = "_OBJC_EHTYPE_$_";
 constexpr const char ivar[] = "_OBJC_IVAR_$_";
 
+// Check for duplicate method names within related categories / classes.
+void checkCategories();
+
 } // namespace objc
 
 bool hasObjCSection(llvm::MemoryBufferRef);
 
 } // namespace lld::macho
 
 #endif

lld/MachO/ObjC.cpp

 //===- ObjC.cpp -----------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "ObjC.h"
 #include "InputFiles.h"
 #include "InputSection.h"
+#include "Layout.h"
 #include "OutputSegment.h"
 #include "Target.h"
 
 #include "lld/Common/ErrorHandler.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/BinaryFormat/MachO.h"
 #include "llvm/Bitcode/BitcodeReader.h"
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace lld;
 using namespace lld::macho;
 
bool macho::hasObjCSection(MemoryBufferRef mb) {
   case file_magic::macho_object:
     return objectHasObjCSection(mb);
   case file_magic::bitcode:
     return check(isBitcodeContainingObjCCategory(mb));
   default:
     return false;
   }
 }
+
+namespace {
+
+#define FOR_EACH_CATEGORY_FIELD(DO)                                            \
+  DO(Ptr, name)                                                                \
+  DO(Ptr, klass)                                                               \
+  DO(Ptr, instanceMethods)                                                     \
+  DO(Ptr, classMethods)                                                        \
+  DO(Ptr, protocols)                                                           \
+  DO(Ptr, instanceProps)                                                       \
+  DO(Ptr, classProps)
+
+CREATE_LAYOUT_CLASS(Category, FOR_EACH_CATEGORY_FIELD);
+
+#undef FOR_EACH_CATEGORY_FIELD
+
+#define FOR_EACH_CLASS_FIELD(DO)                                               \
+  DO(Ptr, metaClass)                                                           \
+  DO(Ptr, superClass)                                                          \
+  DO(Ptr, methodCache)                                                         \
+  DO(Ptr, vtable)                                                              \
+  DO(Ptr, roData)
+
+CREATE_LAYOUT_CLASS(Class, FOR_EACH_CLASS_FIELD);
+
+#undef FOR_EACH_CLASS_FIELD
+
+#define FOR_EACH_RO_CLASS_FIELD(DO)                                            \
+  DO(uint32_t, flags)                                                          \
+  DO(uint32_t, instanceStart)                                                  \
+  DO(Ptr, instanceSize)                                                        \
+  DO(Ptr, ivarLayout)                                                          \
+  DO(Ptr, name)                                                                \
+  DO(Ptr, baseMethods)                                                         \
+  DO(Ptr, baseProtocols)                                                       \
+  DO(Ptr, ivars)                                                               \
+  DO(Ptr, weakIvarLayout)                                                      \
+  DO(Ptr, baseProperties)
+
+CREATE_LAYOUT_CLASS(ROClass, FOR_EACH_RO_CLASS_FIELD);
+
+#undef FOR_EACH_RO_CLASS_FIELD
+
+#define FOR_EACH_LIST_HEADER(DO)                                               \
+  DO(uint32_t, size)                                                           \
+  DO(uint32_t, count)
+
+CREATE_LAYOUT_CLASS(ListHeader, FOR_EACH_LIST_HEADER);
+
+#undef FOR_EACH_LIST_HEADER
+
+#define FOR_EACH_METHOD(DO)                                                    \
+  DO(Ptr, name)                                                                \
+  DO(Ptr, type)                                                                \
+  DO(Ptr, impl)
+
+CREATE_LAYOUT_CLASS(Method, FOR_EACH_METHOD);
+
+#undef FOR_EACH_METHOD
+
+enum MethodContainerKind {
+  MCK_Class,
+  MCK_Category,
+};
+
+struct MethodContainer {
+  MethodContainerKind kind;
+  const ConcatInputSection *isec;
+};
+
+enum MethodKind {
+  MK_Instance,
+  MK_Static,
+};
+
+struct ObjcClass {
+  DenseMap<CachedHashStringRef, MethodContainer> instanceMethods;
+  DenseMap<CachedHashStringRef, MethodContainer> classMethods;
+};
+
+} // namespace
+
+class ObjcCategoryChecker {
+public:
+  ObjcCategoryChecker();
+  void parseCategory(const ConcatInputSection *catListIsec);
+
+private:
+  void parseClass(const Defined *classSym);
+  void parseMethods(const ConcatInputSection *methodsIsec,
+                    const Symbol *methodContainer,
+                    const ConcatInputSection *containerIsec,
+                    MethodContainerKind, MethodKind);
+
+  CategoryLayout catLayout;
+  ClassLayout classLayout;
+  ROClassLayout roClassLayout;
+  ListHeaderLayout listHeaderLayout;
+  MethodLayout methodLayout;
+
+  DenseMap<const Symbol *, ObjcClass> classMap;
+};
+
+ObjcCategoryChecker::ObjcCategoryChecker()
+    : catLayout(target->wordSize), classLayout(target->wordSize),
+      roClassLayout(target->wordSize), listHeaderLayout(target->wordSize),
+      methodLayout(target->wordSize) {}
+
+// \p r must point to an offset within a cstring section.
+static StringRef getReferentString(const Reloc &r) {
+  return cast<CStringInputSection>(r.referent.get<InputSection *>())
+      ->getStringRefAtOffset(r.addend);
+}
+
+void ObjcCategoryChecker::parseMethods(const ConcatInputSection *methodsIsec,
+                                       const Symbol *methodContainerSym,
+                                       const ConcatInputSection *containerIsec,
+                                       MethodContainerKind mcKind,
+                                       MethodKind mKind) {
+  ObjcClass &klass = classMap[methodContainerSym];
+  for (const Reloc &r : methodsIsec->relocs) {
+    if ((r.offset - listHeaderLayout.totalSize) % methodLayout.totalSize !=
+        methodLayout.nameOffset)
+      continue;
+
+    CachedHashStringRef s(getReferentString(r));
+    auto &methodMap =
+        mKind == MK_Instance ? klass.instanceMethods : klass.classMethods;
+    if (methodMap.try_emplace(s, MethodContainer{mcKind, containerIsec}).second)
+      continue;
+
+    // We have a duplicate; generate a warning message.
+    const auto &mc = methodMap.lookup(s);
+    const Reloc *nameReloc = nullptr;
+    if (mc.kind == MCK_Category) {
+      nameReloc = mc.isec->getRelocAt(catLayout.nameOffset);
+    } else {
+      assert(mc.kind == MCK_Class);
+      const auto *roIsec = mc.isec->getRelocAt(classLayout.roDataOffset)
+                         ->getReferentInputSection();
+      nameReloc = roIsec->getRelocAt(roClassLayout.nameOffset);
+    }
+    StringRef containerName = getReferentString(*nameReloc);
+    StringRef methPrefix = mKind == MK_Instance ? "-" : "+";
+
+    // We should only ever encounter collisions when parsing category methods
+    // (since the Class struct is parsed before any of its categories).
+    assert(mcKind == MCK_Category);
+    StringRef newCatName =
+        getReferentString(*containerIsec->getRelocAt(catLayout.nameOffset));
+
+    StringRef containerType = mc.kind == MCK_Category ? "category" : "class";
+    warn("method '" + methPrefix + s.val() +
+         "' has conflicting definitions:\n>>> defined in category " +
+         newCatName + " from " + toString(containerIsec->getFile()) +
+         "\n>>> defined in " + containerType + " " + containerName + " from " +
+         toString(mc.isec->getFile()));
+  }
+}
+
+void ObjcCategoryChecker::parseCategory(const ConcatInputSection *catIsec) {
+  auto *classReloc = catIsec->getRelocAt(catLayout.klassOffset);
+  if (!classReloc)
+    return;
+
+  auto *classSym = classReloc->referent.get<Symbol *>();
+  if (auto *d = dyn_cast<Defined>(classSym))
+    if (!classMap.count(d))
+      parseClass(d);
+
+  if (const auto *r = catIsec->getRelocAt(catLayout.classMethodsOffset)) {
+    parseMethods(cast<ConcatInputSection>(r->getReferentInputSection()),
+                 classSym, catIsec, MCK_Category, MK_Static);
+  }
+
+  if (const auto *r = catIsec->getRelocAt(catLayout.instanceMethodsOffset)) {
+    parseMethods(cast<ConcatInputSection>(r->getReferentInputSection()),
+                 classSym, catIsec, MCK_Category, MK_Instance);
+  }
+}
+
+void ObjcCategoryChecker::parseClass(const Defined *classSym) {
+  // Given a Class struct, get its corresponding Methods struct
+  auto getMethodsIsec =
+      [&](const InputSection *classIsec) -> ConcatInputSection * {
+    if (const auto *r = classIsec->getRelocAt(classLayout.roDataOffset)) {
+      const auto *roIsec =
+          cast<ConcatInputSection>(r->getReferentInputSection());
+      if (const auto *r = roIsec->getRelocAt(roClassLayout.baseMethodsOffset)) {
+        if (auto *methodsIsec =
+                cast_or_null<ConcatInputSection>(r->getReferentInputSection()))
+          return methodsIsec;
+      }
+    }
+    return nullptr;
+  };
+
+  const auto *classIsec = cast<ConcatInputSection>(classSym->isec);
+
+  // Parse instance methods.
+  if (const auto *instanceMethodsIsec = getMethodsIsec(classIsec))
+    parseMethods(instanceMethodsIsec, classSym, classIsec, MCK_Class,
+                 MK_Instance);
+
+  // Class methods are contained in the metaclass.
+  if (const auto *r = classSym->isec->getRelocAt(classLayout.metaClassOffset))
+    if (const auto *classMethodsIsec = getMethodsIsec(
+            cast<ConcatInputSection>(r->getReferentInputSection())))
+      parseMethods(classMethodsIsec, classSym, classIsec, MCK_Class, MK_Static);
+}
+
+void objc::checkCategories() {
+  ObjcCategoryChecker checker;
+  for (const InputSection *isec : inputSections) {
+    if (isec->getName() == section_names::objcCatList)
+      for (const Reloc &r : isec->relocs) {
+        auto *catIsec = cast<ConcatInputSection>(r.getReferentInputSection());
+        checker.parseCategory(catIsec);
+      }
+  }
+}

lld/MachO/Relocations.h

struct Reloc {
   llvm::PointerUnion<Symbol *, InputSection *> referent = nullptr;
 
   Reloc() = default;
 
   Reloc(uint8_t type, bool pcrel, uint8_t length, uint32_t offset,
         int64_t addend, llvm::PointerUnion<Symbol *, InputSection *> referent)
       : type(type), pcrel(pcrel), length(length), offset(offset),
         addend(addend), referent(referent) {}
+
+  InputSection *getReferentInputSection() const;
 };
 
 bool validateSymbolRelocation(const Symbol *, const InputSection *,
                               const Reloc &);
 
 /*
  * v: The value the relocation is attempting to encode
  * bits: The number of bits actually available to encode this relocation

lld/MachO/Relocations.cpp

 
 using namespace llvm;
 using namespace lld;
 using namespace lld::macho;
 
 static_assert(sizeof(void *) != 8 || sizeof(Reloc) == 24,
               "Try to minimize Reloc's size; we create many instances");
 
+InputSection *Reloc::getReferentInputSection() const {
+  if (const auto *sym = referent.dyn_cast<Symbol *>()) {
+    if (const auto *d = dyn_cast<Defined>(sym))
+      return d->isec;
+    return nullptr;
+  } else {
+    return referent.get<InputSection *>();
+  }
+}
+
 bool macho::validateSymbolRelocation(const Symbol *sym,
                                      const InputSection *isec, const Reloc &r) {
   const RelocAttrs &relocAttrs = target->getRelocAttrs(r.type);
   bool valid = true;
   auto message = [&](const Twine &diagnostic) {
     valid = false;
     return (isec->getLocation(r.offset) + ": " + relocAttrs.name +
             " relocation " + diagnostic)

lld/MachO/UnwindInfoSection.cpp

 //===- UnwindInfoSection.cpp ----------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "UnwindInfoSection.h"
 #include "InputSection.h"
+#include "Layout.h"
 #include "OutputSection.h"
 #include "OutputSegment.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 
 #include "lld/Common/ErrorHandler.h"

 // number of entries.
 //
 // Refer to the definition of unwind_info_section_header in
 // compact_unwind_encoding.h for an overview of the format we are encoding
 // here.
 
 // TODO(gkm): how do we align the 2nd-level pages?
 
-// The offsets of various fields in the on-disk representation of each compact
-// unwind entry.
-struct CompactUnwindOffsets {
-  uint32_t functionAddress;
-  uint32_t functionLength;
-  uint32_t encoding;
-  uint32_t personality;
-  uint32_t lsda;
-
-  CompactUnwindOffsets(size_t wordSize) {
-    if (wordSize == 8)
-      init<uint64_t>();
-    else {
-      assert(wordSize == 4);
-      init<uint32_t>();
-    }
-  }
+// The various fields in the on-disk representation of each compact unwind
+// entry.
+#define FOR_EACH_CU_FIELD(DO)                                                  \
+  DO(Ptr, functionAddress)                                                     \
+  DO(uint32_t, functionLength)                                                 \
+  DO(compact_unwind_encoding_t, encoding)                                      \
+  DO(Ptr, personality)                                                         \
+  DO(Ptr, lsda)
 
-private:
-  template <class Ptr> void init() {
-    functionAddress = offsetof(Layout<Ptr>, functionAddress);
-    functionLength = offsetof(Layout<Ptr>, functionLength);
-    encoding = offsetof(Layout<Ptr>, encoding);
-    personality = offsetof(Layout<Ptr>, personality);
-    lsda = offsetof(Layout<Ptr>, lsda);
-  }
+CREATE_LAYOUT_CLASS(CompactUnwind, FOR_EACH_CU_FIELD);
 
-  template <class Ptr> struct Layout {
-    Ptr functionAddress;
-    uint32_t functionLength;
-    compact_unwind_encoding_t encoding;
-    Ptr personality;
-    Ptr lsda;
-  };
-};
+#undef FOR_EACH_CU_FIELD
 
 // LLD's internal representation of a compact unwind entry.
 struct CompactUnwindEntry {
   uint64_t functionAddress;
   uint32_t functionLength;
   compact_unwind_encoding_t encoding;
   Symbol *personality;
   InputSection *lsda;
struct SecondLevelPage {
   std::vector<compact_unwind_encoding_t> localEncodings;
   EncodingMap localEncodingIndexes;
 };
 
 // UnwindInfoSectionImpl allows us to avoid cluttering our header file with a
 // lengthy definition of UnwindInfoSection.
 class UnwindInfoSectionImpl final : public UnwindInfoSection {
 public:
-  UnwindInfoSectionImpl() : cuOffsets(target->wordSize) {}
+  UnwindInfoSectionImpl() : cuLayout(target->wordSize) {}
   uint64_t getSize() const override { return unwindInfoSize; }
   void prepare() override;
   void finalize() override;
   void writeTo(uint8_t *buf) const override;
 
 private:
   void prepareRelocations(ConcatInputSection *);
   void relocateCompactUnwind(std::vector<CompactUnwindEntry> &);
   void encodePersonalities();
   Symbol *canonicalizePersonality(Symbol *);
 
   uint64_t unwindInfoSize = 0;
   std::vector<decltype(symbols)::value_type> symbolsVec;
-  CompactUnwindOffsets cuOffsets;
+  CompactUnwindLayout cuLayout;
   std::vector<std::pair<compact_unwind_encoding_t, size_t>> commonEncodings;
   EncodingMap commonEncodingIndexes;
   // The entries here will be in the same order as their originating symbols
   // in symbolsVec.
   std::vector<CompactUnwindEntry> cuEntries;
   // Indices into the cuEntries vector.
   std::vector<size_t> cuIndices;
   std::vector<Symbol *> personalities;
for (size_t i = 0; i < isec->relocs.size(); ++i) {
     // canonicalization here.
     if (auto *referentIsec = r.referent.dyn_cast<InputSection *>())
       r.referent = referentIsec->canonical();
 
     // Functions and LSDA entries always reside in the same object file as the
     // compact unwind entries that references them, and thus appear as section
     // relocs. There is no need to prepare them. We only prepare relocs for
     // personality functions.
-    if (r.offset != cuOffsets.personality)
+    if (r.offset != cuLayout.personalityOffset)
       continue;
 
     if (auto *s = r.referent.dyn_cast<Symbol *>()) {
       // Personality functions are nearly always system-defined (e.g.,
       // ___gxx_personality_v0 for C++) and relocated as dylib symbols.  When an
       // application provides its own personality function, it might be
       // referenced by an extern Defined symbol reloc, or a local section reloc.
       if (auto *defined = dyn_cast<Defined>(s)) {
if (d->unwindEntry->getName() == section_names::ehFrame) {
       return;
     }
 
     assert(d->unwindEntry->getName() == section_names::compactUnwind);
 
     auto buf = reinterpret_cast<const uint8_t *>(d->unwindEntry->data.data()) -
                target->wordSize;
     cu.functionLength =
-        support::endian::read32le(buf + cuOffsets.functionLength);
-    cu.encoding = support::endian::read32le(buf + cuOffsets.encoding);
+        support::endian::read32le(buf + cuLayout.functionLengthOffset);
+    cu.encoding = support::endian::read32le(buf + cuLayout.encodingOffset);
     for (const Reloc &r : d->unwindEntry->relocs) {
-      if (r.offset == cuOffsets.personality) {
+      if (r.offset == cuLayout.personalityOffset)
         cu.personality = r.referent.get<Symbol *>();
-      } else if (r.offset == cuOffsets.lsda) {
-        if (auto *referentSym = r.referent.dyn_cast<Symbol *>())
-          cu.lsda = cast<Defined>(referentSym)->isec;
-        else
-          cu.lsda = r.referent.get<InputSection *>();
-      }
+      else if (r.offset == cuLayout.lsdaOffset)
+        cu.lsda = r.getReferentInputSection();
     }
   });
 }
 
 // There should only be a handful of unique personality pointers, so we can
 // encode them as 2-bit indices into a small array.
 void UnwindInfoSectionImpl::encodePersonalities() {
   for (size_t idx : cuIndices) {

lld/test/MachO/Inputs/MacOSX.sdk/usr/lib/libobjc.tbd

+--- !tapi-tbd-v3
+archs:            [ i386, x86_64, arm64 ]
+uuids:            [ 'i386: 00000000-0000-0000-0000-000000000000', 'x86_64: 00000000-0000-0000-0000-000000000001', 'arm64: 00000000-0000-0000-0000-000000000002' ]
+platform:         macosx
+install-name:     '/usr/lib/libobjc.dylib'
+current-version:  1281
+exports:
+  - archs:        [ i386, x86_64, arm64 ]
+    symbols:      [ __objc_empty_cache ]
+...

lld/test/MachO/objc-category-conflicts.s

+# REQUIRES: x86
+# RUN: rm -rf %t; split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos11.0 -I %t %t/cat1.s -o %t/cat1.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos11.0 -I %t %t/cat2.s -o %t/cat2.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos11.0 -I %t %t/klass.s -o %t/klass.o
+# RUN: %lld -dylib -lobjc %t/klass.o -o %t/libklass.dylib
+
+# RUN: %no-fatal-warnings-lld -dylib -lobjc %t/klass.o %t/cat1.o %t/cat2.o -o \
+# RUN:   /dev/null 2>&1 | FileCheck %s --check-prefixes=CATCLS,CATCAT
+# RUN: %no-fatal-warnings-lld -dylib -lobjc %t/libklass.dylib %t/cat1.o \
+# RUN:   %t/cat2.o -o /dev/null 2>&1 | FileCheck %s --check-prefix=CATCAT
+
+# CATCLS:      warning: method '+s1' has conflicting definitions:
+# CATCLS-NEXT: >>> defined in category Cat1 from {{.*}}cat1.o
+# CATCLS-NEXT: >>> defined in class Foo from {{.*}}klass.o
+
+# CATCLS:      warning: method '-m1' has conflicting definitions:
+# CATCLS-NEXT: >>> defined in category Cat1 from {{.*}}cat1.o
+# CATCLS-NEXT: >>> defined in class Foo from {{.*}}klass.o
+
+# CATCAT:      warning: method '+s2' has conflicting definitions:
+# CATCAT-NEXT: >>> defined in category Cat2 from {{.*}}cat2.o
+# CATCAT-NEXT: >>> defined in category Cat1 from {{.*}}cat1.o
+
+# CATCAT:      warning: method '-m2' has conflicting definitions:
+# CATCAT-NEXT: >>> defined in category Cat2 from {{.*}}cat2.o
+# CATCAT-NEXT: >>> defined in category Cat1 from {{.*}}cat1.o
+
+#--- cat1.s
+
+.include "objc-macros.s"
+
+## @interface Foo(Cat1)
+## -(void) m1;
+## -(void) m2;
+## +(void) s1;
+## +(void) s2;
+## @end
+## 
+## @implementation Foo(Cat1)
+## -(void) m1 {}
+## -(void) m2 {}
+## +(void) s1 {}
+## +(void) s2 {}
+## @end
+
+.section __DATA,__objc_catlist,regular,no_dead_strip
+  .quad __OBJC_$_CATEGORY_Foo_$_Cat1
+
+.section __DATA,__objc_const
+__OBJC_$_CATEGORY_Foo_$_Cat1:
+  .objc_classname "Cat1"
+  .quad _OBJC_CLASS_$_Foo
+  .quad __OBJC_$_CATEGORY_INSTANCE_METHODS_Foo_$_Cat1
+  .quad __OBJC_$_CATEGORY_CLASS_METHODS_Foo_$_Cat1
+  .quad 0
+  .quad 0
+  .quad 0
+  .long 64
+  .space 4
+
+__OBJC_$_CATEGORY_INSTANCE_METHODS_Foo_$_Cat1:
+  .long 24 # size of method entry
+  .long 2 # number of methods
+  .empty_objc_method "m1", "v16@0:8", "-[Foo(Cat1) m1]"
+  .empty_objc_method "m2", "v16@0:8", "-[Foo(Cat2) m2]"
+
+__OBJC_$_CATEGORY_CLASS_METHODS_Foo_$_Cat1:
+  .long 24
+  .long 2
+  .empty_objc_method "s1", "v16@0:8", "+[Foo(Cat1) s1]"
+  .empty_objc_method "s2", "v16@0:8", "+[Foo(Cat1) s2]"
+
+.section __DATA,__objc_imageinfo,regular,no_dead_strip
+  .long 0
+  .long 64
+
+.subsections_via_symbols
+
+#--- cat2.s
+
+.include "objc-macros.s"
+
+## @interface Foo(Cat2)
+## -(void) m2;
+## +(void) s2;
+## @end
+## 
+## @implementation Foo(Cat2)
+## -(void) m2 {}
+## +(void) s2 {}
+## @end
+
+.section __DATA,__objc_catlist,regular,no_dead_strip
+  .quad __OBJC_$_CATEGORY_Foo_$_Cat2
+
+.section __DATA,__objc_const
+__OBJC_$_CATEGORY_Foo_$_Cat2:
+  .objc_classname "Cat2"
+  .quad _OBJC_CLASS_$_Foo
+  .quad __OBJC_$_CATEGORY_INSTANCE_METHODS_Foo_$_Cat2
+  .quad __OBJC_$_CATEGORY_CLASS_METHODS_Foo_$_Cat2
+  .quad 0
+  .quad 0
+  .quad 0
+  .long 64
+  .space 4
+
+__OBJC_$_CATEGORY_INSTANCE_METHODS_Foo_$_Cat2:
+  .long 24
+  .long 1
+  .empty_objc_method "m2", "v16@0:8", "-[Foo(Cat2) m2]"
+
+__OBJC_$_CATEGORY_CLASS_METHODS_Foo_$_Cat2:
+  .long 24
+  .long 1
+  .empty_objc_method "s2", "v16@0:8", "+[Foo(Cat2) m2]"
+
+.section __DATA,__objc_imageinfo,regular,no_dead_strip
+  .long 0
+  .long 64
+
+.subsections_via_symbols
+
+#--- klass.s
+
+.include "objc-macros.s"
+
+## @interface Foo
+## -(void) m1;
+## +(void) s1;
+## @end
+##
+## @implementation Foo
+## -(void) m1 {}
+## +(void) s1 {}
+## @end
+
+.globl _OBJC_CLASS_$_Foo, _OBJC_METACLASS_$_Foo
+
+.section __DATA,__objc_data
+_OBJC_CLASS_$_Foo:
+  .quad _OBJC_METACLASS_$_Foo
+  .quad 0
+  .quad __objc_empty_cache
+  .quad 0
+  .quad __OBJC_CLASS_RO_$_Foo
+
+_OBJC_METACLASS_$_Foo:
+  .quad _OBJC_METACLASS_$_Foo
+  .quad _OBJC_CLASS_$_Foo
+  .quad __objc_empty_cache
+  .quad 0
+  .quad __OBJC_METACLASS_RO_$_Foo
+
+.section __DATA,__objc_const
+__OBJC_METACLASS_RO_$_Foo:
+  .long 3
+  .long 40
+  .long 40
+  .space 4
+  .quad 0
+  .objc_classname "Foo"
+  .quad __OBJC_$_CLASS_METHODS_Foo
+  .quad 0
+  .quad 0
+  .quad 0
+  .quad 0
+
+__OBJC_CLASS_RO_$_Foo:
+  .long 2
+  .long 0
+  .long 0
+  .space 4
+  .quad 0
+  .objc_classname "Foo"
+  .quad __OBJC_$_INSTANCE_METHODS_Foo
+  .quad 0
+  .quad 0
+  .quad 0
+  .quad 0
+
+__OBJC_$_CLASS_METHODS_Foo:
+  .long 24
+  .long 1
+  .empty_objc_method "s1", "v16@0:8", "+[Foo s1]"
+
+__OBJC_$_INSTANCE_METHODS_Foo:
+  .long 24
+  .long 1
+  .empty_objc_method "m1", "v16@0:8", "-[Foo m1]"
+
+.section __DATA,__objc_classlist,regular,no_dead_strip
+  .quad _OBJC_CLASS_$_Foo
+
+.section __DATA,__objc_imageinfo,regular,no_dead_strip
+  .long 0
+  .long 64
+
+.subsections_via_symbols
+
+#--- objc-macros.s
+
+# Macros for taking some of the boilerplate out of defining objc structs.
+
+# NOTE: \@ below is a variable that gets auto-incremented by the assembler on
+# each macro invocation. It serves as a mechanism for generating unique symbol
+# names for each macro call.
+
+.macro .objc_classname name
+
+  .section __TEXT,__objc_classname,cstring_literals
+  L_OBJC_CLASS_NAME_.\@:
+    .asciz "\name"
+
+  .section __DATA,__objc_const
+  .quad L_OBJC_CLASS_NAME_.\@
+
+.endm
+
+# struct method_t {
+#   const char *name;
+#   const char *type;
+#   void *impl;
+# }
+.macro .objc_method name, type, impl
+
+  .section __TEXT,__objc_methname,cstring_literals
+  L_OBJC_METH_VAR_NAME_.\@:
+    .asciz "\name"
+
+  .section __TEXT,__objc_methtype,cstring_literals
+  L_OBJC_METH_VAR_TYPE_.\@:
+    .asciz "\type"
+
+  .section __DATA,__objc_const
+    .quad L_OBJC_METH_VAR_NAME_.\@
+    .quad L_OBJC_METH_VAR_TYPE_.\@
+    .quad "\impl"
+
+.endm
+
+# Generate a method_t with a basic impl that just contains `ret`.
+.macro .empty_objc_method name, type, impl
+
+  .text
+  "\impl":
+    ret
+
+  .objc_method "\name", "\type", "\impl"
+
+.endm

lld/test/MachO/objc-imageinfo.s

 
 .section __DATA,__objc_data
 .p2align 3
 _OBJC_CLASS_$_FooClass:
 .space 40
 
 .section __DATA,__objc_const
 .p2align 3
-__OBJC_$_CATEGORY_INSTANCE_METHODS_FooClass_$_barcat:
-
-.p2align 3
 __OBJC_$_CATEGORY_FooClass_$_barcat:
 .quad L_CAT_NAME
 .quad _OBJC_CLASS_$_FooClass
-.quad __OBJC_$_CATEGORY_INSTANCE_METHODS_FooClass_$_barcat
+.quad 0
 .quad 0
 .quad 0
 .quad 0
 .quad 0
 .long 64
 .space 4
 
 .section __DATA,__objc_catlist,regular,no_dead_strip
 .p2align 3
 .quad __OBJC_$_CATEGORY_FooClass_$_barcat