[lld] Define DefinedAtom::sectionSize.

[ruiu]

Summary

Merge::mergeByLargestSection is half-baked since it's defined
in terms of section size, there's no way to get the section size
of an atom.

Currently we work around the issue by traversing the layout edges
to both directions and calculate the sum of all atoms reachable.
I wrote that code but I knew it's hacky. It's even not guaranteed
to work. If you add layout edges before the core linking, it
miscalculates a size.

Also it's of course slow. It's basically a linked list traversal.

In this patch I added DefinedAtom::sectionSize so that we can use
that for mergeByLargestSection. I'm not very happy to add a new
field to DefinedAtom base class, but I think it's legitimate since
mergeByLargestSection is defined for section size, and the section
size is currently just missing.

[• shankar.easwaran]

in my opinion this is a shared attribute for all atoms that belong to a section. Can we store this information for the atom in the context? The other way is to add a Reference to store the size. If the idea is to add all format specific attributes in the Atom I am fine but we need to discuss on llvmdev before adding those features.

Anyways this patch is not complete as it's missing YAML Support and native file format support.

[shankarke]

Thats a nice comparison, Ruiu. Once the YAML/Native code is changed, this LGTM. I have a usecase for section size for ELF too for internal purposes.

[ruiu]

• Added code for Native and YAML.

[• shankar.easwaran]

Other than the above mentioned comments code LGTM

include/lld/Core/DefinedAtom.h

239

Why are we mentioning the purpose if this function here. We could drop this comment.

lib/ReaderWriter/Native/ReaderNative.cpp

49

Can you add a new line before this function

[Eugene.Zelenko]

Committed in r231290.

include/lld/Core/DefinedAtom.h

public:
   virtual uint64_t ordinal() const = 0;
 
   /// \brief the number of bytes of space this atom's content will occupy in the
   /// final linked image.
   ///
   /// For a function atom, it is the number of bytes of code in the function.
   virtual uint64_t size() const = 0;
 
+  /// \brief The size of the section from which the atom is instantiated.
+  ///
+  /// Merge::mergeByLargestSection is defined in terms of section size
+  /// and not in terms of atom size, so we need this function separate
+  /// from size().
+  virtual uint64_t sectionSize() const { return 0; }
+
   /// \brief The visibility of this atom to other atoms.
   ///
   /// C static functions have scope scopeTranslationUnit.  Regular C functions
   /// have scope scopeGlobal.  Functions compiled with visibility=hidden have
   /// scope scopeLinkageUnit so they can be see by other atoms being linked but
   /// not by the OS loader.
   virtual Scope scope() const = 0;
 

lib/Core/SymbolTable.cpp

 
 static MergeResolution mergeSelect(DefinedAtom::Merge first,
                                    DefinedAtom::Merge second) {
   assert(first != DefinedAtom::mergeByContent);
   assert(second != DefinedAtom::mergeByContent);
   return mergeCases[first][second];
 }
 
-static const DefinedAtom *followReference(const DefinedAtom *atom,
-                                          uint32_t kind) {
-  for (const Reference *r : *atom)
-    if (r->kindNamespace() == Reference::KindNamespace::all &&
-        r->kindArch() == Reference::KindArch::all &&
-        r->kindValue() == kind)
-      return cast<const DefinedAtom>(r->target());
-  return nullptr;
-}
-
-static uint64_t getSizeFollowReferences(const DefinedAtom *atom,
-                                        uint32_t kind) {
-  uint64_t size = 0;
-  for (;;) {
-    atom = followReference(atom, kind);
-    if (!atom)
-      return size;
-    size += atom->size();
-  }
-}
-
-// Returns the size of the section containing the given atom. Atoms in the same
-// section are connected by layout-before and layout-after edges, so this
-// function traverses them to get the total size of atoms in the same section.
-static uint64_t sectionSize(const DefinedAtom *atom) {
-  return atom->size()
-      + getSizeFollowReferences(atom, lld::Reference::kindLayoutBefore)
-      + getSizeFollowReferences(atom, lld::Reference::kindLayoutAfter);
-}
-
 bool SymbolTable::addByName(const Atom &newAtom) {
   StringRef name = newAtom.name();
   assert(!name.empty());
   const Atom *existing = findByName(name);
   if (existing == nullptr) {
     // Name is not in symbol table yet, add it associate with this atom.
     _context.notifySymbolTableAdd(&newAtom);
     _nameTable[name] = &newAtom;
case NCR_DupDef: {
     switch (mergeSelect(existingDef->merge(), newDef->merge())) {
     case MCR_First:
       useNew = false;
       break;
     case MCR_Second:
       useNew = true;
       break;
     case MCR_Largest: {
-      uint64_t existingSize = sectionSize(existingDef);
-      uint64_t newSize = sectionSize(newDef);
+      uint64_t existingSize = existingDef->sectionSize();
+      uint64_t newSize = newDef->sectionSize();
       useNew = (newSize >= existingSize);
       break;
     }
     case MCR_SameSize: {
-      uint64_t existingSize = sectionSize(existingDef);
-      uint64_t newSize = sectionSize(newDef);
+      uint64_t existingSize = existingDef->sectionSize();
+      uint64_t newSize = newDef->sectionSize();
       if (existingSize == newSize) {
         useNew = true;
         break;
       }
       llvm::errs() << "Size mismatch: "
                    << existing->name() << " (" << existingSize << ") "
                    << newAtom.name() << " (" << newSize << ")\n";
       // fallthrough

lib/ReaderWriter/Native/NativeFileFormat.h

 //
 struct NativeDefinedAtomIvarsV1 {
   uint32_t  nameOffset;
   uint32_t  attributesOffset;
   uint32_t  referencesStartIndex;
   uint32_t  referencesCount;
   uint32_t  contentOffset;
   uint32_t  contentSize;
+  uint64_t  sectionSize;
 };
 
 
 //
 // The NCS_AttributesArrayV1 chunk contains an array of these structs
 //
 struct NativeAtomAttributesV1 {
   uint32_t  sectionNameOffset;

lib/ReaderWriter/Native/ReaderNative.cpp

public:
         : _file(&f), _ivarData(ivarData) { }
 
   const lld::File& file() const override;
 
   uint64_t ordinal() const override;
 
   StringRef name() const override;
 
-  uint64_t size() const override {
-    return _ivarData->contentSize;
-  }
+  uint64_t size() const override { return _ivarData->contentSize; }
+  uint64_t sectionSize() const override { return _ivarData->sectionSize; }
 
   DefinedAtom::Scope scope() const override {
     return (DefinedAtom::Scope)(attributes().scope);
   }
 
   DefinedAtom::Interposable interposable() const override {
     return (DefinedAtom::Interposable)(attributes().interposable);
   }

lib/ReaderWriter/Native/WriterNative.cpp

void addIVarsForDefinedAtom(const DefinedAtom& atom) {
     NativeDefinedAtomIvarsV1 ivar;
     unsigned refsCount;
     ivar.nameOffset = getNameOffset(atom);
     ivar.attributesOffset = getAttributeOffset(atom);
     ivar.referencesStartIndex = getReferencesIndex(atom, refsCount);
     ivar.referencesCount = refsCount;
     ivar.contentOffset = getContentOffset(atom);
     ivar.contentSize = atom.size();
+    ivar.sectionSize = atom.sectionSize();
     _definedAtomIvars.push_back(ivar);
   }
 
   void addIVarsForUndefinedAtom(const UndefinedAtom& atom) {
     _undefinedAtomIndex[&atom] = _undefinedAtomIvars.size();
     NativeUndefinedAtomIvarsV1 ivar;
     ivar.nameOffset = getNameOffset(atom);
     ivar.flags = (atom.canBeNull() & 0x03);

lib/ReaderWriter/PECOFF/Atoms.h

private:
   std::vector<std::unique_ptr<COFFReference> > _references;
 };
 
 /// This is the root class of the atom read from a file. This class have two
 /// subclasses; one for the regular atom and another for the BSS atom.
 class COFFDefinedFileAtom : public COFFBaseDefinedAtom {
 public:
   COFFDefinedFileAtom(const File &file, StringRef name, StringRef sectionName,
-                      Scope scope, ContentType contentType,
-                      ContentPermissions perms, uint64_t ordinal)
+                      uint64_t sectionSize, Scope scope,
+                      ContentType contentType, ContentPermissions perms,
+                      uint64_t ordinal)
       : COFFBaseDefinedAtom(file, name, Kind::File), _sectionName(sectionName),
-        _scope(scope), _contentType(contentType), _permissions(perms),
-        _ordinal(ordinal), _alignment(0) {}
+        _sectionSize(sectionSize), _scope(scope), _contentType(contentType),
+        _permissions(perms), _ordinal(ordinal), _alignment(0) {}
 
   static bool classof(const COFFBaseDefinedAtom *atom) {
     return atom->getKind() == Kind::File;
   }
 
   void setAlignment(Alignment val) { _alignment = val; }
   SectionChoice sectionChoice() const override { return sectionCustomRequired; }
   StringRef customSectionName() const override { return _sectionName; }
+  uint64_t sectionSize() const override { return _sectionSize; }
   Scope scope() const override { return _scope; }
   ContentType contentType() const override { return _contentType; }
   ContentPermissions permissions() const override { return _permissions; }
   uint64_t ordinal() const override { return _ordinal; }
   Alignment alignment() const override { return _alignment; }
 
   void addAssociate(const DefinedAtom *other) {
     auto *ref = new COFFReference(other, 0, lld::Reference::kindAssociate,
                                   Reference::KindArch::all,
                                   Reference::KindNamespace::all);
     addReference(std::unique_ptr<COFFReference>(ref));
   }
 
 private:
   StringRef _sectionName;
+  uint64_t _sectionSize;
   Scope _scope;
   ContentType _contentType;
   ContentPermissions _permissions;
   uint64_t _ordinal;
   Alignment _alignment;
   std::vector<std::unique_ptr<COFFReference> > _references;
 };
 
 // A COFFDefinedAtom represents an atom read from a file and has contents.
 class COFFDefinedAtom : public COFFDefinedFileAtom {
 public:
   COFFDefinedAtom(const File &file, StringRef name, StringRef sectionName,
-                  Scope scope, ContentType type, bool isComdat,
-                  ContentPermissions perms, Merge merge, ArrayRef<uint8_t> data,
-                  uint64_t ordinal)
-      : COFFDefinedFileAtom(file, name, sectionName, scope, type, perms,
-                            ordinal),
+                  uint64_t sectionSize, Scope scope, ContentType type,
+                  bool isComdat, ContentPermissions perms, Merge merge,
+                  ArrayRef<uint8_t> data, uint64_t ordinal)
+      : COFFDefinedFileAtom(file, name, sectionName, sectionSize,
+                            scope, type, perms, ordinal),
         _isComdat(isComdat), _merge(merge), _dataref(data) {}
 
   Merge merge() const override { return _merge; }
   uint64_t size() const override { return _dataref.size(); }
   ArrayRef<uint8_t> rawContent() const override { return _dataref; }
 
   DeadStripKind deadStrip() const override {
     // Only COMDAT symbols would be dead-stripped.
     return _isComdat ? deadStripNormal : deadStripNever;
   }
 
 private:
   bool _isComdat;
   Merge _merge;
   ArrayRef<uint8_t> _dataref;
 };
 
 // A COFFDefinedAtom represents an atom for BSS section.
 class COFFBSSAtom : public COFFDefinedFileAtom {
 public:
   COFFBSSAtom(const File &file, StringRef name, Scope scope,
               ContentPermissions perms, Merge merge, uint32_t size,
               uint64_t ordinal)
-      : COFFDefinedFileAtom(file, name, ".bss", scope, typeZeroFill, perms,
-                            ordinal),
+      : COFFDefinedFileAtom(file, name, ".bss", 0, scope, typeZeroFill,
+                            perms, ordinal),
         _merge(merge), _size(size) {}
 
   Merge merge() const override { return _merge; }
   uint64_t size() const override { return _size; }
   ArrayRef<uint8_t> rawContent() const override { return _contents; }
 
 private:
   Merge _merge;

lib/ReaderWriter/PECOFF/ReaderCOFF.cpp

std::error_code FileCOFF::AtomizeDefinedSymbolsInSection(
   // blobs that nobody would understand.
   if ((section->Characteristics & llvm::COFF::IMAGE_SCN_MEM_DISCARDABLE) &&
       (sectionName == ".debug" || sectionName.startswith(".debug$"))) {
     return std::error_code();
   }
 
   DefinedAtom::ContentType type = getContentType(section);
   DefinedAtom::ContentPermissions perms = getPermissions(section);
+  uint64_t sectionSize = section->SizeOfRawData;
   bool isComdat = (_comdatSections.count(section) == 1);
 
   // Create an atom for the entire section.
   if (symbols.empty()) {
     ArrayRef<uint8_t> data(secData.data(), secData.size());
     auto *atom = new (_alloc) COFFDefinedAtom(
-        *this, "", sectionName, Atom::scopeTranslationUnit, type, isComdat,
-        perms, _merge[section], data, getNextOrdinal());
+        *this, "", sectionName, sectionSize, Atom::scopeTranslationUnit,
+        type, isComdat, perms, _merge[section], data, getNextOrdinal());
     atoms.push_back(atom);
     _definedAtomLocations[section][0].push_back(atom);
     return std::error_code();
   }
 
   // Create an unnamed atom if the first atom isn't at the start of the
   // section.
   if (symbols[0].getValue() != 0) {
     uint64_t size = symbols[0].getValue();
     ArrayRef<uint8_t> data(secData.data(), size);
     auto *atom = new (_alloc) COFFDefinedAtom(
-        *this, "", sectionName, Atom::scopeTranslationUnit, type, isComdat,
-        perms, _merge[section], data, getNextOrdinal());
+        *this, "", sectionName, sectionSize, Atom::scopeTranslationUnit,
+        type, isComdat, perms, _merge[section], data, getNextOrdinal());
     atoms.push_back(atom);
     _definedAtomLocations[section][0].push_back(atom);
   }
 
   for (auto si = symbols.begin(), se = symbols.end(); si != se; ++si) {
     const uint8_t *start = secData.data() + si->getValue();
     // if this is the last symbol, take up the remaining data.
     const uint8_t *end = (si + 1 == se) ? secData.data() + secData.size()
                                         : secData.data() + (si + 1)->getValue();
     ArrayRef<uint8_t> data(start, end);
     auto *atom = new (_alloc) COFFDefinedAtom(
-        *this, _symbolName[*si], sectionName, getScope(*si), type, isComdat,
-        perms, _merge[section], data, getNextOrdinal());
+        *this, _symbolName[*si], sectionName, sectionSize, getScope(*si),
+        type, isComdat, perms, _merge[section], data, getNextOrdinal());
     atoms.push_back(atom);
     _symbolAtom[*si] = atom;
     _definedAtomLocations[section][si->getValue()].push_back(atom);
   }
   return std::error_code();
 }
 
 std::error_code FileCOFF::AtomizeDefinedSymbols(

 std::error_code FileCOFF::maybeCreateSXDataAtoms() {
   ArrayRef<uint8_t> sxdata;
   if (std::error_code ec = getSectionContents(".sxdata", sxdata))
     return ec;
   if (sxdata.empty())
     return std::error_code();
 
   auto *atom = new (_alloc) COFFDefinedAtom(
-      *this, "", ".sxdata", Atom::scopeTranslationUnit, DefinedAtom::typeData,
-      false /*isComdat*/, DefinedAtom::permR__, DefinedAtom::mergeNo,
-      sxdata, getNextOrdinal());
+      *this, "", ".sxdata", 0, Atom::scopeTranslationUnit,
+      DefinedAtom::typeData, false /*isComdat*/, DefinedAtom::permR__,
+      DefinedAtom::mergeNo, sxdata, getNextOrdinal());
 
   const ulittle32_t *symbolIndex =
       reinterpret_cast<const ulittle32_t *>(sxdata.data());
   int numSymbols = sxdata.size() / sizeof(uint32_t);
 
   for (int i = 0; i < numSymbols; ++i) {
     Atom *handlerFunc;
     if (std::error_code ec = getAtomBySymbolIndex(symbolIndex[i], handlerFunc))

lib/ReaderWriter/YAML/ReaderWriterYAML.cpp

NormalizedAtom(IO &io, const lld::DefinedAtom *atom)
         : _file(fileFromContext(io)), _name(atom->name()), _refName(),
           _scope(atom->scope()), _interpose(atom->interposable()),
           _merge(atom->merge()), _contentType(atom->contentType()),
           _alignment(atom->alignment()), _sectionChoice(atom->sectionChoice()),
           _sectionPosition(atom->sectionPosition()),
           _deadStrip(atom->deadStrip()), _dynamicExport(atom->dynamicExport()),
           _codeModel(atom->codeModel()),
           _permissions(atom->permissions()), _size(atom->size()),
-          _sectionName(atom->customSectionName()) {
+          _sectionName(atom->customSectionName()),
+          _sectionSize(atom->sectionSize()) {
       for (const lld::Reference *r : *atom)
         _references.push_back(r);
       if (!atom->occupiesDiskSpace())
         return;
       ArrayRef<uint8_t> cont = atom->rawContent();
       _content.reserve(cont.size());
       for (uint8_t x : cont)
         _content.push_back(x);
public:
     uint64_t size() const override { return _size; }
     Scope scope() const override { return _scope; }
     Interposable interposable() const override { return _interpose; }
     Merge merge() const override { return _merge; }
     ContentType contentType() const override { return _contentType; }
     Alignment alignment() const override { return _alignment; }
     SectionChoice sectionChoice() const override { return _sectionChoice; }
     StringRef customSectionName() const override { return _sectionName; }
+    uint64_t sectionSize() const override { return _sectionSize; }
     SectionPosition sectionPosition() const override { return _sectionPosition; }
     DeadStripKind deadStrip() const override { return _deadStrip; }
     DynamicExport dynamicExport() const override { return _dynamicExport; }
     CodeModel codeModel() const override { return _codeModel; }
     ContentPermissions permissions() const override { return _permissions; }
     void setGroupChild(bool val) { _isGroupChild = val; }
     bool isGroupChild() const { return _isGroupChild; }
     ArrayRef<uint8_t> rawContent() const override {
public:
     DeadStripKind                       _deadStrip;
     DynamicExport                       _dynamicExport;
     CodeModel                           _codeModel;
     ContentPermissions                  _permissions;
     uint32_t                            _ordinal;
     std::vector<ImplicitHex8>           _content;
     uint64_t                            _size;
     StringRef                           _sectionName;
+    uint64_t                            _sectionSize;
     std::vector<const lld::Reference *> _references;
     bool _isGroupChild;
   };
 
   static void mapping(IO &io, const lld::DefinedAtom *&atom) {
     MappingNormalizationHeap<NormalizedAtom, const lld::DefinedAtom *> keys(
         io, atom);
     if (io.outputting()) {
static void mapping(IO &io, const lld::DefinedAtom *&atom) {
     io.mapOptional("merge",            keys->_merge, DefinedAtom::mergeNo);
     io.mapOptional("alignment",        keys->_alignment,
                                          DefinedAtom::Alignment(0));
     io.mapOptional("section-choice",   keys->_sectionChoice,
                                          DefinedAtom::sectionBasedOnContent);
     io.mapOptional("section-name",     keys->_sectionName, StringRef());
     io.mapOptional("section-position", keys->_sectionPosition,
                                          DefinedAtom::sectionPositionAny);
+    io.mapOptional("section-size",     keys->_sectionSize, (uint64_t)0);
     io.mapOptional("dead-strip",       keys->_deadStrip,
                                          DefinedAtom::deadStripNormal);
     io.mapOptional("dynamic-export",   keys->_dynamicExport,
                                          DefinedAtom::dynamicExportNormal);
     io.mapOptional("code-model",       keys->_codeModel, DefinedAtom::codeNA);
     // default permissions based on content type
     io.mapOptional("permissions",      keys->_permissions,
                                          DefinedAtom::permissions(

test/pecoff/Inputs/merge-same-size3.obj.yaml

 symbols:
   - Name:            .text
     Value:           0
     SectionNumber:   1
     SimpleType:      IMAGE_SYM_TYPE_NULL
     ComplexType:     IMAGE_SYM_DTYPE_NULL
     StorageClass:    IMAGE_SYM_CLASS_STATIC
     SectionDefinition:
-      Length:          7
+      Length:          2
       NumberOfRelocations: 0
       NumberOfLinenumbers: 0
       CheckSum:        2532800969
       Number:          0
       Selection:       IMAGE_COMDAT_SELECT_SAME_SIZE
   - Name:            "_foo"
     Value:           0
     SectionNumber:   1
     SimpleType:      IMAGE_SYM_TYPE_NULL
     ComplexType:     IMAGE_SYM_DTYPE_FUNCTION
     StorageClass:    IMAGE_SYM_CLASS_EXTERNAL
 ...