[COFF] Store alignment in log2 form, NFC

[rnk]

Summary

Valid section or chunk alignments are powers of 2 in the range [1,
8192]. These can be stored more canonically in log2 form to free up some
bits in Chunk. Combined with D61696, SectionChunk gets 8 bytes smaller.

[ruiu]

lld/COFF/Chunks.cpp

860 ↗

(On Diff #198721)

I'd think we should always pass a power-of-two instead of log2 to constructors for the sake of consistency.

lld/COFF/Chunks.h

47–48 ↗

(On Diff #198721)

Is this enforced by the file format?

73 ↗

(On Diff #198721)

If this can be triggered by feeding a bad file, this should be a call of error() instead of assert().

136 ↗

(On Diff #198721)

Instead of emphasizing that the maximum alignment is 2^13, can we support an alignment up to a reasonable upper limit, say, 2^32? That's apparently large enough, and by doing that, we do not have to explain a trivia that what value is the maximum alignment value we can express by COFF. (And the runtime cost of doing that is virtually nothing.)

lld/COFF/Driver.cpp

1744–1745 ↗

(On Diff #198721)

Can you eliminate {set,get}Log2Alignment and consistently use {set,get}Alignment, so that the details about how it is represented internally is hidden from the user?

[aganea]

lld/COFF/Chunks.h

47–48 ↗

(On Diff #198721)

Yes there's a hard limit in the SectionCharacteristics, see PE Format

[rnk]

In the long term, I think we want to hoist section characteristics up into chunk, and that's going to create the 8192 max alignment constraint. This is just a first step to refactor the code to use the accessors.

lld/COFF/Chunks.h

73 ↗

(On Diff #198721)

I don't think it's possible. I think it might be possible with -aligncomm or -functionpadmin, though, since those raise alignment on the command line and take arbitrary input.

136 ↗

(On Diff #198721)

Originally I was planning to make this a bitfield, in which case, the comment is relevant, but if we store the characteristics in the on-disk format here, then this comment isn't really needed. It makes more sense to move it to the setter, since that has to deal with the edge case of invalid alignments.

[rnk]

• remove [gs]etLog2Alignment

[rnk]

ptal

[aganea]

lld/COFF/Chunks.cpp

865 ↗

(On Diff #198920)

This is essentially the same code as Chunk::setAlignment, can you make it so that a static version of that function is used here instead?

lld/COFF/Chunks.h

71 ↗

(On Diff #198920)

assert(P2Align<=Log2MaxSectionAlignment) ?

[ruiu]

By the way, the other idea I had in mind for this problem is to define a new integer-ish class that can hold only a 2^n value, by overriding cast from/to an integer. I don't know if that is a good idea or a disgusting idea, though.

[rnk]

In D61698#1502875, @ruiu wrote:

By the way, the other idea I had in mind for this problem is to define a new integer-ish class that can hold only a 2^n value, by overriding cast from/to an integer. I don't know if that is a good idea or a disgusting idea, though.

Well, the next logical step, IMO, is to store the section characteristics directly in Chunk. I don't think that would work well with the custom type idea.

[ruiu]

LGTM

lld/COFF/Chunks.h

70 ↗

(On Diff #198920)

A little off-topic, but llvm::Log2_32 seems to be a redundant function, as I think we can just use countTrailingZeros.

[rnk]

lld/COFF/Chunks.cpp

865 ↗

(On Diff #198920)

I'm not sure it's worth it, it's only combining the assert with the log. The simplification I would prefer is to add back the log2 accessor, which is what I had originally, but I did this since it was requested.

lld/COFF/Chunks.h

71 ↗

(On Diff #198920)

Added

[rnk]

• assert

lld/trunk/COFF/Chunks.h

 class Symbol;
 
 // Mask for permissions (discardable, writable, readable, executable, etc).
 const uint32_t PermMask = 0xFE000000;
 
 // Mask for section types (code, data, bss).
 const uint32_t TypeMask = 0x000000E0;
 
+// The log base 2 of the largest section alignment, which is log2(8192), or 13.
+enum : unsigned { Log2MaxSectionAlignment = 13 };
+
 // A Chunk represents a chunk of data that will occupy space in the
 // output (if the resolver chose that). It may or may not be backed by
 // a section of an input file. It could be linker-created data, or
 // doesn't even have actual data (if common or bss).
 class Chunk {
 public:
   enum Kind : uint8_t { SectionKind, OtherKind };
   Kind kind() const { return ChunkKind; }
   virtual ~Chunk() = default;
 
   // Returns the size of this chunk (even if this is a common or BSS.)
   virtual size_t getSize() const = 0;
 
+  // Returns chunk alignment in power of two form. Value values are powers of
+  // two from 1 to 8192.
+  uint32_t getAlignment() const { return 1U << P2Align; }
+  void setAlignment(uint32_t Align) {
+    // Treat zero byte alignment as 1 byte alignment.
+    Align = Align ? Align : 1;
+    assert(llvm::isPowerOf2_32(Align) && "alignment is not a power of 2");
+    P2Align = llvm::Log2_32(Align);
+    assert(P2Align <= Log2MaxSectionAlignment &&
+           "impossible requested alignment");
+  }
+
   // Write this chunk to a mmap'ed file, assuming Buf is pointing to
   // beginning of the file. Because this function may use RVA values
   // of other chunks for relocations, you need to set them properly
   // before calling this function.
   virtual void writeTo(uint8_t *Buf) const {}
 
   // Called by the writer after an RVA is assigned, but before calling
   // getSize().
public:
   // Windows-specific.
   // Collect all locations that contain absolute addresses for base relocations.
   virtual void getBaserels(std::vector<Baserel> *Res) {}
 
   // Returns a human-readable name of this chunk. Chunks are unnamed chunks of
   // bytes, so this is used only for logging or debugging.
   virtual StringRef getDebugName() { return ""; }
 
-  // The alignment of this chunk. The writer uses the value.
-  uint32_t Alignment = 1;
-
   virtual bool isHotPatchable() const { return false; }
 
 protected:
   Chunk(Kind K = OtherKind) : ChunkKind(K) {}
   const Kind ChunkKind;
 
 public:
   // Whether this section needs to be kept distinct from other sections during
   // ICF. This is set by the driver using address-significance tables.
   bool KeepUnique = false;
 
 protected:
+  // The alignment of this chunk, stored in log2 form. The writer uses the
+  // value.
+  uint8_t P2Align = 0;
+
   // The RVA of this chunk in the output. The writer sets a value.
   uint32_t RVA = 0;
 
 protected:
   // The output section for this chunk.
   OutputSection *Out = nullptr;
 };
 
public:
   static void addSection(SectionChunk *C);
   void finalizeContents() override;
 
   uint32_t getOutputCharacteristics() const override;
   StringRef getSectionName() const override { return ".rdata"; }
   size_t getSize() const override;
   void writeTo(uint8_t *Buf) const override;
 
-  static std::map<uint32_t, MergeChunk *> Instances;
+  static MergeChunk *Instances[Log2MaxSectionAlignment + 1];
   std::vector<SectionChunk *> Sections;
 
 private:
   llvm::StringTableBuilder Builder;
   bool Finalized = false;
 };
 
 // A chunk for common symbols. Common chunks don't have actual data.
public:
   Defined *Target;
 };
 
 // Windows-specific.
 // See comments for DefinedLocalImport class.
 class LocalImportChunk : public Chunk {
 public:
   explicit LocalImportChunk(Defined *S) : Sym(S) {
-    Alignment = Config->Wordsize;
+    setAlignment(Config->Wordsize);
   }
   size_t getSize() const override;
   void getBaserels(std::vector<Baserel> *Res) override;
   void writeTo(uint8_t *Buf) const override;
 
 private:
   Defined *Sym;
 };

 // references that turned out to need to be imported from a DLL even though
 // the reference didn't use the dllimport attribute. The MinGW runtime will
 // process this table after loading, before handling control over to user
 // code.
 class PseudoRelocTableChunk : public Chunk {
 public:
   PseudoRelocTableChunk(std::vector<RuntimePseudoReloc> &Relocs)
       : Relocs(std::move(Relocs)) {
-    Alignment = 4;
+    setAlignment(4);
   }
   size_t getSize() const override;
   void writeTo(uint8_t *Buf) const override;
 
 private:
   std::vector<RuntimePseudoReloc> Relocs;
 };
 
public:
   // flags are currently defined.
   int Flags;
 };
 
 // MinGW specific. A Chunk that contains one pointer-sized absolute value.
 class AbsolutePointerChunk : public Chunk {
 public:
   AbsolutePointerChunk(uint64_t Value) : Value(Value) {
-    Alignment = getSize();
+    setAlignment(getSize());
   }
   size_t getSize() const override;
   void writeTo(uint8_t *Buf) const override;
 
 private:
   uint64_t Value;
 };
 

lld/trunk/COFF/Chunks.cpp

SectionChunk::SectionChunk(ObjFile *F, const coff_section *H)
 
   // Initialize SectionName.
   StringRef SectionName;
   if (Expected<StringRef> E = File->getCOFFObj()->getSectionName(Header))
     SectionName = *E;
   SectionNameData = SectionName.data();
   SectionNameSize = SectionName.size();
 
-  Alignment = Header->getAlignment();
+  setAlignment(Header->getAlignment());
 
   // If linker GC is disabled, every chunk starts out alive.  If linker GC is
   // enabled, treat non-comdat sections as roots. Generally optimized object
   // files will be built with -ffunction-sections or /Gy, so most things worth
   // stripping will be in a comdat.
   Live = !Config->DoGC || !isCOMDAT();
 }
 
 // SectionChunk is one of the most frequently allocated classes, so it is
 // important to keep it as compact as possible. As of this writing, the number
 // below is the size of this class on x64 platforms.
-static_assert(sizeof(SectionChunk) <= 112, "SectionChunk grew unexpectedly");
+static_assert(sizeof(SectionChunk) <= 104, "SectionChunk grew unexpectedly");
 
 static void add16(uint8_t *P, int16_t V) { write16le(P, read16le(P) + V); }
 static void add32(uint8_t *P, int32_t V) { write32le(P, read32le(P) + V); }
 static void add64(uint8_t *P, int64_t V) { write64le(P, read64le(P) + V); }
 static void or16(uint8_t *P, uint16_t V) { write16le(P, read16le(P) | V); }
 static void or32(uint8_t *P, uint32_t V) { write32le(P, read32le(P) | V); }
 
 // Verify that given sections are appropriate targets for SECREL
SectionChunk *SectionChunk::findByName(ArrayRef<SectionChunk *> Sections,
                                        StringRef Name) {
   for (SectionChunk *C : Sections)
     if (C->getSectionName() == Name)
       return C;
   return nullptr;
 }
 
 void SectionChunk::replace(SectionChunk *Other) {
-  Alignment = std::max(Alignment, Other->Alignment);
+  P2Align = std::max(P2Align, Other->P2Align);
   Other->Repl = Repl;
   Other->Live = false;
 }
 
 uint32_t SectionChunk::getSectionNumber() const {
   DataRefImpl R;
   R.p = reinterpret_cast<uintptr_t>(Header);
   SectionRef S(R, File->getCOFFObj());
   return S.getIndex() + 1;
 }
 
 CommonChunk::CommonChunk(const COFFSymbolRef S) : Sym(S) {
   // Common symbols are aligned on natural boundaries up to 32 bytes.
   // This is what MSVC link.exe does.
-  Alignment = std::min(uint64_t(32), PowerOf2Ceil(Sym.getValue()));
+  setAlignment(std::min(32U, Sym.getValue()));
 }
 
 uint32_t CommonChunk::getOutputCharacteristics() const {
   return IMAGE_SCN_CNT_UNINITIALIZED_DATA | IMAGE_SCN_MEM_READ |
          IMAGE_SCN_MEM_WRITE;
 }
 
 void StringChunk::writeTo(uint8_t *Buf) const {
   memcpy(Buf, Str.data(), Str.size());
   Buf[Str.size()] = '\0';
 }
 
 ImportThunkChunkX64::ImportThunkChunkX64(Defined *S) : ImpSymbol(S) {
   // Intel Optimization Manual says that all branch targets
   // should be 16-byte aligned. MSVC linker does this too.
-  Alignment = 16;
+  setAlignment(16);
 }
 
 void ImportThunkChunkX64::writeTo(uint8_t *Buf) const {
   memcpy(Buf, ImportThunkX86, sizeof(ImportThunkX86));
   // The first two bytes is a JMP instruction. Fill its operand.
   write32le(Buf + 2, ImpSymbol->getRVA() - RVA - getSize());
 }
 
uint8_t Baserel::getDefaultType() {
   case I386:
   case ARMNT:
     return IMAGE_REL_BASED_HIGHLOW;
   default:
     llvm_unreachable("unknown machine type");
   }
 }
 
-std::map<uint32_t, MergeChunk *> MergeChunk::Instances;
+MergeChunk *MergeChunk::Instances[Log2MaxSectionAlignment + 1] = {};
 
 MergeChunk::MergeChunk(uint32_t Alignment)
     : Builder(StringTableBuilder::RAW, Alignment) {
-  this->Alignment = Alignment;
+  setAlignment(Alignment);
 }
 
 void MergeChunk::addSection(SectionChunk *C) {
-  auto *&MC = Instances[C->Alignment];
+  assert(isPowerOf2_32(C->getAlignment()));
+  uint8_t P2Align = llvm::Log2_32(C->getAlignment());
+  assert(P2Align >= 0 && P2Align < array_lengthof(Instances));
+  auto *&MC = Instances[P2Align];
   if (!MC)
-    MC = make<MergeChunk>(C->Alignment);
+    MC = make<MergeChunk>(C->getAlignment());
   MC->Sections.push_back(C);
 }
 
 void MergeChunk::finalizeContents() {
   if (!Finalized) {
     for (SectionChunk *C : Sections)
       if (C->Live)
         Builder.add(toStringRef(C->getContents()));

lld/trunk/COFF/DLL.cpp

 private:
   StringRef Name;
   uint16_t Hint;
 };
 
 // A chunk for the import descriptor table.
 class LookupChunk : public Chunk {
 public:
-  explicit LookupChunk(Chunk *C) : HintName(C) { Alignment = Config->Wordsize; }
+  explicit LookupChunk(Chunk *C) : HintName(C) {
+    setAlignment(Config->Wordsize);
+  }
   size_t getSize() const override { return Config->Wordsize; }
 
   void writeTo(uint8_t *Buf) const override {
     if (Config->is64())
       write64le(Buf, HintName->getRVA());
     else
       write32le(Buf, HintName->getRVA());
   }
 
   Chunk *HintName;
 };
 
 // A chunk for the import descriptor table.
 // This chunk represent import-by-ordinal symbols.
 // See Microsoft PE/COFF spec 7.1. Import Header for details.
 class OrdinalOnlyChunk : public Chunk {
 public:
   explicit OrdinalOnlyChunk(uint16_t V) : Ordinal(V) {
-    Alignment = Config->Wordsize;
+    setAlignment(Config->Wordsize);
   }
   size_t getSize() const override { return Config->Wordsize; }
 
   void writeTo(uint8_t *Buf) const override {
     // An import-by-ordinal slot has MSB 1 to indicate that
     // this is import-by-ordinal (and not import-by-name).
     if (Config->is64()) {
       write64le(Buf, (1ULL << 63) | Ordinal);
public:
   Chunk *Desc = nullptr;
   Defined *Helper = nullptr;
 };
 
 // A chunk for the import descriptor table.
 class DelayAddressChunk : public Chunk {
 public:
   explicit DelayAddressChunk(Chunk *C) : Thunk(C) {
-    Alignment = Config->Wordsize;
+    setAlignment(Config->Wordsize);
   }
   size_t getSize() const override { return Config->Wordsize; }
 
   void writeTo(uint8_t *Buf) const override {
     if (Config->is64()) {
       write64le(Buf, Thunk->getRVA() + Config->ImageBase);
     } else {
       uint32_t Bit = 0;
for (std::vector<DefinedImportData *> &Syms : V) {
     }
     // Terminate with null values.
     Addresses.push_back(make<NullChunk>(8));
     Names.push_back(make<NullChunk>(8));
 
     for (int I = 0, E = Syms.size(); I < E; ++I)
       Syms[I]->setLocation(Addresses[Base + I]);
     auto *MH = make<NullChunk>(8);
-    MH->Alignment = 8;
+    MH->setAlignment(8);
     ModuleHandles.push_back(MH);
 
     // Fill the delay import table header fields.
     Dir->ModuleHandle = MH;
     Dir->AddressTab = Addresses[Base];
     Dir->NameTab = Names[Base];
     Dirs.push_back(Dir);
   }

lld/trunk/COFF/Driver.cpp

for (auto Pair : Config->AlignComm) {
 
     // If the symbol isn't common, it must have been replaced with a regular
     // symbol, which will carry its own alignment.
     auto *DC = dyn_cast<DefinedCommon>(Sym);
     if (!DC)
       continue;
 
     CommonChunk *C = DC->getChunk();
-    C->Alignment = std::max(C->Alignment, Alignment);
+    C->setAlignment(std::max(C->getAlignment(), Alignment));
   }
 
   // Windows specific -- Create a side-by-side manifest file.
   if (Config->Manifest == Configuration::SideBySide)
     createSideBySideManifest();
 
   // Handle /order. We want to do this at this moment because we
   // need a complete list of comdat sections to warn on nonexistent

lld/trunk/COFF/ICF.cpp

if (auto *SC = dyn_cast<SectionChunk>(C)) {
         Chunks.push_back(SC);
       else
         SC->Class[0] = NextId++;
     }
   }
 
   // Make sure that ICF doesn't merge sections that are being handled by string
   // tail merging.
-  for (auto &P : MergeChunk::Instances)
-    for (SectionChunk *SC : P.second->Sections)
+  for (MergeChunk *MC : MergeChunk::Instances)
+    if (MC)
+      for (SectionChunk *SC : MC->Sections)
         SC->Class[0] = NextId++;
 
   // Initially, we use hash values to partition sections.
   parallelForEach(Chunks, [&](SectionChunk *SC) {
     SC->Class[0] = xxHash64(SC->getContents());
   });
 
   // Combine the hashes of the sections referenced by each section into its
   // hash.

lld/trunk/COFF/MapFile.cpp

for (OutputSection *Sec : OutputSections) {
     writeHeader(OS, Sec->getRVA(), Sec->getVirtualSize(), /*Align=*/PageSize);
     OS << Sec->Name << '\n';
 
     for (Chunk *C : Sec->Chunks) {
       auto *SC = dyn_cast<SectionChunk>(C);
       if (!SC)
         continue;
 
-      writeHeader(OS, SC->getRVA(), SC->getSize(), SC->Alignment);
+      writeHeader(OS, SC->getRVA(), SC->getSize(), SC->getAlignment());
       OS << Indent8 << SC->File->getName() << ":(" << SC->getSectionName()
          << ")\n";
       for (DefinedRegular *Sym : SectionSyms[SC])
         OS << SymStr[Sym] << '\n';
     }
   }
 }

lld/trunk/COFF/Writer.cpp

void Writer::createSections() {
   };
   llvm::stable_sort(OutputSections,
                     [&](const OutputSection *S, const OutputSection *T) {
                       return SectionOrder(S) < SectionOrder(T);
                     });
 }
 
 void Writer::createMiscChunks() {
-  for (auto &P : MergeChunk::Instances)
-    RdataSec->addChunk(P.second);
+  for (MergeChunk *P : MergeChunk::Instances)
+    if (P)
+      RdataSec->addChunk(P);
 
   // Create thunks for locally-dllimported symbols.
   if (!Symtab->LocalImportChunks.empty()) {
     for (Chunk *C : Symtab->LocalImportChunks)
       RdataSec->addChunk(C);
   }
 
   // Create Debug Information Chunks
const bool IsCodeSection =
         (Sec->Header.Characteristics & IMAGE_SCN_CNT_CODE) &&
         (Sec->Header.Characteristics & IMAGE_SCN_MEM_READ) &&
         (Sec->Header.Characteristics & IMAGE_SCN_MEM_EXECUTE);
     uint32_t Padding = IsCodeSection ? Config->FunctionPadMin : 0;
 
     for (Chunk *C : Sec->Chunks) {
       if (Padding && C->isHotPatchable())
         VirtualSize += Padding;
-      VirtualSize = alignTo(VirtualSize, C->Alignment);
+      VirtualSize = alignTo(VirtualSize, C->getAlignment());
       C->setRVA(RVA + VirtualSize);
       C->finalizeContents();
       VirtualSize += C->getSize();
       if (C->hasData())
         RawSize = alignTo(VirtualSize, SectorSize);
     }
     if (VirtualSize > UINT32_MAX)
       error("section larger than 4 GiB: " + Sec->Name);
if (Config->Entry)
     maybeAddAddressTakenFunction(AddressTakenSyms, Config->Entry);
 
   // Mark exported symbols in executable sections as address-taken.
   for (Export &E : Config->Exports)
     maybeAddAddressTakenFunction(AddressTakenSyms, E.Sym);
 
   // Ensure sections referenced in the gfid table are 16-byte aligned.
   for (const ChunkAndOffset &C : AddressTakenSyms)
-    if (C.InputChunk->Alignment < 16)
-      C.InputChunk->Alignment = 16;
+    if (C.InputChunk->getAlignment() < 16)
+      C.InputChunk->setAlignment(16);
 
   maybeAddRVATable(std::move(AddressTakenSyms), "__guard_fids_table",
                    "__guard_fids_count");
 
   // Add the longjmp target table unless the user told us not to.
   if (Config->GuardCF == GuardCFLevel::Full)
     maybeAddRVATable(std::move(LongJmpTargets), "__guard_longjmp_table",
                      "__guard_longjmp_count");