[llvm-objcopy] [WIP] Librarify llvm-objcopy

[abrachet]

Summary

This is for my GSoC project to librarify llvm-objcopy. See bug 41044

The current code is in a very rough state and is a work in progress (WIP). It will of course be different however this is just for a check in and giving an example of renaming sections. This approach does so by keeping a map of modified sections which allows sections to be immutable but also seemingly modified in place. For example, if we rename section at index 1, then the iterator (hypothetical at this point but see MutableObject::getSection() ) at 1 will expose the new one. This lets sections be both immutable and rewritten to the file in their original order. Also I like that in this way methods like renameSection aren't themselves virtual, of course relying on virtual methods but I think this is a good start for code reuse.

I have never been great at designing class hierarchies and would love tips on how to structure the relationship between the classes. Jake had previously suggested having a hierarchy based on semantic meaning not implementation details, clearly there is a lot of work to be done here, I'm not blind to the fact that this code is a very rough draft.

Of note, something like SectionBase::clone() feels really bad to me. I don't really know a better way to do this though.

I would also say to ignore access modifiers for now, and also that everything is in the header file, I know this isn't conformant with the coding standards but I figured this was easier to keep in one file for now.

[jhenderson]

At least with renaming a section, what is stopping you just modifying SectionBase.Name?

More generally, I guess I don't understand why you need to make a copy of a section when you want to update it rather than just modifying it in-place?

Also, I'd steer away from a single Object base class that is intended to be shared between formats. There's a good reason why we don't do this in llvm-objcopy currently: the file formats are different enough that trying to have a common interface is messy.

My feeling is that you should focus on the structure required to make changes and then lay out a file to be written. If you look at how llvm-objcopy was originally developed, it started off as just doing enough to copy everything, and then hooks were added to allow modifications of different parts as time went on. However, I'm not saying that's the only way to design this, so I'm open to alternatives, if you've got a good reason to do it a different way.

[abrachet]

At least with renaming a section, what is stopping you just modifying SectionBase.Name?
More generally, I guess I don't understand why you need to make a copy of a section when you want to update it rather than just modifying it in-place?

The current code uses some OrginalXXX fields, also Jake had said in response to an email of mine on llvm-dev (although I cannot find his response on Google groups so I'm not quite sure how to link it) that there were many things that were left mutable in the current code. This seemed like it could be used to keep the original file if it ever needed to be referenced again after modification, also leaving things like sections immutable, only changed by adding a new one. FWIW Jake had also said that OriginalXXX were only used in objcopy and wouldn't make sense to prioritize for a library, but I thought this might be a clever way to incorporate that.

Also, I'd steer away from a single Object base class that is intended to be shared between formats.

Do you think there should be no common base class like there is in the current llvm-objcopy code? I would say that libObject has quite a bit in the ObjectFile (and in SymbolicFile and Binary) class and leaves only the truly file dependent routines in their respective classes. Currently what I have, in MutableObject take renameSection for example depends on the classes inheriting from SectionBase to fulfill their contracts leaving differences there, but leaving common code in renameSection. Is the alternative you are suggesting how the current code is? You had said that the current code is not a library in LLVM terms, what is the biggest factor making this true?

My feeling is that you should focus on the structure required to make changes and then lay out a file to be written.

Great, I'll do this next. Thank you for all the feedback, James!

[abrachet]

llvm/tools/llvm-objcopy/MutableObject/MutableObject.h

7 ↗

(On Diff #204221)

Ignore this, I just wanted access to ObjectFile::base(), it didn't even work and I forgot to remove it.

[jhenderson]

Okay, I think I see what you're getting at now. By creating a copy, you don't need to have the OriginalX fields. I think this makes sense now, okay.

(although I cannot find his response on Google groups so I'm not quite sure how to link it)

There's an archive for the email threads which I usually use to link to past llvm-dev emails: http://lists.llvm.org/pipermail/llvm-dev/

FWIW Jake had also said that OriginalXXX were only used in objcopy and wouldn't make sense to prioritize for a library, but I thought this might be a clever way to incorporate that.

I think you'll find once you start trying to write file layout code that you'll need access to the "Original" values at various points. That's why they exist in llvm-objcopy. I don't think we should leave laying the file out to the user (or at least, I think we should have a function that they can choose to call to lay it out, if they want to follow the default layout routine), so you'll need the data.

Do you think there should be no common base class like there is in the current llvm-objcopy code? I would say that libObject has quite a bit in the ObjectFile (and in SymbolicFile and Binary) class and leaves only the truly file dependent routines in their respective classes.

I'll admit that I haven't thought too much about the differences between the file formats, and how libObject is designed. Thinking about it a bit more, I guess it might be a nice design to have effectively a mutable mirror that sits on top of libObject, with a parallel hierarchy like you have started. I don't have strong feelings either way though. I guess I want to know how you envisage a regular user using the library as a whole, because I suspect we might have slightly different visions here that could explain some of the differences.

Is the alternative you are suggesting how the current code is? You had said that the current code is not a library in LLVM terms, what is the biggest factor making this true?

I assume by current code you are referring to the existing llvm-objcopy code. At the moment, the code is in a location that is not intended to be used outside the llvm-objcopy tree (llvm-strip is similar enough that it is effectively just a clone of llvm-objcopy). A library needs to live in llvm/include and llvm/lib, so that different tools can link against it. In my mind, the only part that should really be outside the library is the driver components in llvm-objcopy.cpp (and maybe CopyConfig.cpp, but I'm not convinced on that point). However, that being said, your design sounds like it might provide a bit more flexibility for library users in the future, so please keep going with it.

[abrachet]

Adds an iterator which iterates over sections only exposing the updated ones and skipping over removed ones. This is used to write an (incomplete but still readable by llvm-readelf) file. Next I will work to move this code to make it much cleaner because it really needs it, moving it into lib/ and include/ directories.

[jhenderson]

You're going to need to account for program headers in your layout code. If you take a look at llvm-objcopy, a lot of the layout work is done based on those, rather than the sections, because sections within segments should move with their segment.

llvm/tools/llvm-objcopy/MutableObject/MutableObject.h

38 ↗

(On Diff #205509)

You should consider using smart pointers rather than new. Probably a unique_ptr is sufficient.

44 ↗

(On Diff #205509)

Maybe "clone" isn't the right name for this function? It's doing more than cloning.

324 ↗

(On Diff #205509)

The MC library already has a StringTableBuilder class that does a lot of this work, so you should probably use that, rather than writing things from scratch.

383–384 ↗

(On Diff #205509)

It probably doesn't make sense for the elf header to be updated in this method. That should be derivable right before writing the header to disk. Possible exception is that we need the section header offset somewhere.

390 ↗

(On Diff #205509)

writeToDisk is probably the wrong name for a function that writes to a buffer... ;)

[abrachet]

Large rework moving towards adding support for segments.

[abrachet]

llvm/lib/Object/MutableObject.cpp

56–62

I need help here. I just can't get it to compile. I guess I'm not understanding templates correctly? The constructor looks like this MutableObjectRange<T>::MutableObjectRange(UpdadableList<T>). I want the compiler to deduce the template parameter to type T when I pass an UpdadableList<T>. Either way even if I declare the template parameter like I do on line 61, it still doesn't compile. Any tips?

[jhenderson]

llvm/include/llvm/Object/MutableELFObject.h

1

Even though this is WIP, you should probably include the LLVM license at the top of the new files, as this is technically an LLVM contribution already.

20

Is there a particular reason this takes both a Name and a section header?

46

FWIW, I don't think this assert adds anything.

llvm/lib/Object/CMakeLists.txt

18

This is causing me a problem on my Windows machine at least - CMake doesn't like it when there's no such file. Did you forget to add it?

llvm/lib/Object/MutableObject.cpp

56–62

MutableObjectRange's constructor takes a non-const reference: MutableObjectRange(UpdatableList<Iterable> &List);. However, sections() and segments() are listed as const methods, which makes the members of MutableObject (i.e. Sections and Segments) const, and therefore the input arguments don't match up with the signature (passing in a const & when a plain & is expected. Changing the signature to const & was enough ot fix this issue.

You also need to be explicit about the template you are using, as MutableObjectRange is a type. It's the same as a std::vector for example. You wouldn't expect the following to compile, even though it could deduce the constructor argument: return std::vector(1234). Methods can have template argument deduction, but not types. Thus if the constructor itself was templated, you might reasonable expect the template arguments to be deducible.

65

This and getMutableSegment aren't returning a value.

llvm/include/llvm/Object/MutableELFObject.h

+#ifndef LLVM_OBJECT_MUTABLEELFOBJECT_H
+#define LLVM_OBJECT_MUTABLEELFOBJECT_H
+
+#include "MutableObject.h"
+#include "ELFTypes.h"
+#include "ELFObjectFile.h"
+
+namespace llvm {
+namespace object {
+namespace mutable_object {
+
+template <typename ELFT>
+class ELFSection : public SectionBase {
+  Elf_Shdr_Base<ELFT> SectionHeader;
+
+public:
+  ELFSection(const ELFSection &) = default;
+  ELFSection(ELFSection &&) = default;
+  ELFSection(const MutableObject &OwningObject,
+             ArrayRef<uint8_t> Data, StringRef Name, Elf_Shdr_Base<ELFT> &Shdr)
+  : SectionBase(OwningObject, Data, Name), SectionHeader(Shdr) {}
+
+  ~ELFSection() override {}
+
+
+  static bool classof(const SectionBase *Sec) {
+    return isa<ELFObjectFileBase>(Sec->getOwningObject());
+  }
+
+  std::unique_ptr<SectionBase> clone() const override {
+    return make_unique<ELFSection>(*this);
+  }
+};
+
+template <typename ELFT>
+class ELFSegment : public SegmentBase {
+  Elf_Phdr_Impl<ELFT> ProgramHeader;
+};
+
+template <typename ELFT>
+class MutableELFObject : public MutableObject {
+  Elf_Ehdr_Impl<ELFT> Header;
+
+  const ELFObjectFile<ELFT> &getObjectFile() const override {
+    auto *Ret = dyn_cast<ELFObjectFile<ELFT>>(ObjFile);
+    assert(Ret);
+    return *Ret;
+  }
+
+  MutableELFObject(const ObjectFile &ObjFile) : MutableObject(ObjFile) {}
+public:
+  static Expected<std::unique_ptr<MutableObject>> 
+  create(const ObjectFile &ObjFile) {
+    MutableELFObject Object(ObjFile);
+    auto ELFObjFile = Object.getObjectFile();
+    Object.Header = ELFObjFile.getHeader();
+    auto *Base = ELFObjFile.getData().data();
+
+    ArrayRef<Elf_Shdr_Base<ELFT>> SectionHeaders(Base + Object.Header.e_shoff,
+                                                 Object.Header.e_shnum);
+    auto *Shstrtab = Base + Object.Header.e_shstrndx;
+    std::vector<std::unique_ptr<SectionBase>> OriginalSections;
+    for (const auto &Shdr : SectionHeaders) {
+      OriginalSections.push_back(make_unique<ELFSection>(
+        Object, ArrayRef<uint8_t>(Shdr.sh_offset, Shdr.sh_size),
+        Shstrtab + Shdr.sh_name, Shdr));
+    }
+
+    Object.Sections = SectionList(std::move(OriginalSections));
+
+    return std::unique_ptr<MutableObject>(Object);
+  }
+
+};
+
+} // namespace mutable_object
+} // namespace object
+} // namespace llvm
+
+#endif // LLVM_OBJECT_MUTABLEELFOBJECT_H

llvm/include/llvm/Object/MutableObject.h

+
+#ifndef LLVM_OBJECT_MUTABLEOBJECT_H
+#define LLVM_OBJECT_MUTABLEOBJECT_H
+
+#include "ObjectFile.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/Errc.h"
+#include <vector>
+#include <map>
+#include <memory>
+#include <set>
+
+namespace llvm {
+namespace object {
+namespace mutable_object {
+
+class MutableObject;
+class SectionBase;
+class SegmentBase;
+
+struct alignas(8) DataRef {
+  uint64_t Index : 63;
+  bool New : 1;
+
+  DataRef() : Index(0), New(false) {}
+  DataRef(uint64_t Index) : Index(Index), New(true) {}
+  DataRef(uint64_t Index, bool Updated) : Index(Index), New(Updated) {}
+
+  operator unsigned long() const { return Index; }
+  DataRef operator++() { return ++Index; }
+
+  bool operator==(const DataRef &Other) {
+    return Other.Index == Index && Other.New == New;
+  }
+
+  bool operator<(const DataRef &Rhs) {
+    if (New == Rhs.New)
+      return Index < Rhs.Index;
+    return New < Rhs.New;
+  }
+};
+
+template <typename Entity>
+class UpdatableList {
+  template <typename Iterable>
+  friend class MutableObjectRange;
+
+  using Ptr = std::unique_ptr<Entity>;
+
+  // Should be formally made by MutableObject::init.
+  // MutableObject::Mutableobject uses the default constructor so
+  // use this to ensure that no member functions are called unless
+  // it has been properly made with UpdatableList(const ArrayRef<Entity>).
+  bool Made = false;
+
+  const std::vector<Ptr> Original;
+  std::map<uint64_t, Ptr> Updated;
+
+public:
+  UpdatableList() = default;
+  UpdatableList(const std::vector<Ptr> &&Original) : Made(true), Original(Original) {}
+
+  const Entity &operator[](uint64_t Index) const {
+    assert(Made && "Invalid object");
+    auto Found = Updated.find(Index);
+    if (Found != Updated.end()) {
+      assert(Found->second.get() && "nullptr in updated map");
+      return *Found->second.get();
+    }
+    return *Original[Index].get();
+  }
+
+  /// Original sections are immutable, return them as const
+  /// this is the same as operator[](uint64_t) for original indexes.
+  const Entity &getOriginal(uint64_t Index) const {
+    assert(Index < Original.size() && "Out of range");
+    return *Original[Index].get();
+  }
+
+  /// Sections that have been updated should not be immutable
+  /// so return them as non const.
+  Entity &getNew(uint64_t Index) {
+    auto Found = Updated.find(Index);
+    if (Found == Updated.end()) {
+      const Entity &Original = getOriginal(Index);
+      Updated[Index] = Original.clone();
+      return *Updated.find(Index)->second;
+    }
+    return *Found->second.get();
+  }
+
+  Error remove(DataRef Index) {
+    assert(Made && "Invalid object");
+    if (Index.New) {
+      auto Found = Updated.find(Index);
+      if (Found == Updated.end())
+        return createStringError(errc::argument_out_of_domain,
+                                 "Removing updated section that doesn't exist");
+    } else {
+      assert(Index.Index < Original.size() && "Out of range");
+    }
+    Updated[Index] = nullptr;
+    return Error::success();
+  }
+
+  Error update(DataRef Index, Ptr New) {
+    assert(Made && "Invalid object");
+    if (Index.New) {
+      auto Found = Updated.find(Index);
+      if (Found == Updated.end())
+        return createStringError(errc::argument_out_of_domain,
+                                 "Updating section that doesn't exist");
+    } else {
+      assert(Index.Index < Original.size() && "Out of range");
+    }
+    Updated[Index] = std::move(New);
+    return Error::success();
+  }
+};
+
+template <typename Iterable>
+class MutableObjectRange {
+  friend class MutableObject;
+  UpdatableList<Iterable> &List;
+
+  using reference = Iterable&;
+  using pointer = Iterable*;
+
+public:
+  MutableObjectRange(UpdatableList<Iterable> &List);
+
+  // template <bool ExposeNew = true>
+  class Iter {
+    friend class MutableObjectRange;
+
+    UpdatableList<Iterable> &List;
+
+    DataRef Index = UINT64_MAX;
+    pointer Current = nullptr;
+
+    Iter(UpdatableList<Iterable> &List) : List(List) {
+      operator++();
+    }
+
+    static Iter createEnd(UpdatableList<Iterable> &List) {
+      Iter Ret(List);
+      Ret.Index = DataRef(List.Original.size(), false);
+      Ret.Current = nullptr;
+      return Ret;
+    }
+
+  public:
+    Iter operator++() {
+      const auto End = List.Updated.end();
+      for (;;) {
+        ++Index;
+        auto Found = List.Updated.find(Index);
+        if (Found != End) {
+          // nullptr in UpdatedSections means it was removed, skip it.
+          if (!Found->second.get())
+            continue;
+
+          Index.New = true;
+          Current = Found->second.get();
+          return *this;
+        }
+
+        Index.New = false;
+        if (Index >= List.Original.size()) {
+          assert(Index.Index == List.Original.size() && "Should not have gone past");
+          Index.Index = List.Original.size();
+          Current = nullptr;
+          return *this;
+        }
+
+        Current = List.Original[Index].get();
+        return *this;
+      }
+      llvm_unreachable("impossible to exit loop without returning");
+    }
+
+    const pointer operator->() const { return Current; }
+    reference operator*() const {
+      assert(Current && "Current was nullptr");
+      return *Current;
+    }
+
+    bool operator==(const Iter &Other) const {
+      return Other.Current == Current;
+    }
+
+    bool operator!=(const Iter &Other) const {
+      return !operator==(Other);
+    }
+
+    DataRef getCurrentDataRef() const {
+      return Index;
+    }
+  };
+
+  Iter begin() { return Iter(List); }
+  Iter end() { return Iter::createEnd(List); }
+};
+
+class SectionBase {
+  const MutableObject &OwningObject;
+  const SegmentBase *OwnedSegment = nullptr;
+  ArrayRef<uint8_t> Data;
+  StringRef Name;
+
+public:
+  SectionBase(const SectionBase &) = default;
+  SectionBase(SectionBase &&) = default;
+  SectionBase(const MutableObject &OwningObject,
+              ArrayRef<uint8_t> Data, StringRef Name);
+  virtual ~SectionBase();
+
+  StringRef name() const;
+  ArrayRef<uint8_t> data() const;
+  const MutableObject &getOwningObject() const;
+
+  virtual std::unique_ptr<SectionBase> clone() const;
+};
+
+class SegmentBase {
+  const MutableObject &OwningObject;
+  std::set<uint64_t> Sections;
+
+public:
+  SegmentBase(const MutableObject &OwningObject);
+  virtual ~SegmentBase();
+
+  virtual std::unique_ptr<SegmentBase> clone() const;
+
+  void removeSection(uint64_t Section);
+  void addSection(uint64_t Section);
+};
+
+using SectionList = UpdatableList<SectionBase>;
+using SegmentList = UpdatableList<SegmentBase>;
+
+class MutableObject {
+protected:
+  const ObjectFile &ObjFile;
+
+  SectionList Sections;
+  SegmentList Segments;
+
+  virtual const ObjectFile &getObjectFile() const;
+
+  MutableObject(const ObjectFile &ObjFile);
+public:
+  virtual ~MutableObject();
+
+  static Expected<std::unique_ptr<MutableObject>>
+  createMutableObject(const ObjectFile &ObjFile);
+
+  virtual Error init() = 0;
+
+  virtual void finalize();
+
+  Optional<DataRef> findSectionByName(StringRef Name) const;
+  Error removeSection(DataRef Section);
+  Error replaceSection(DataRef ToReplace, std::unique_ptr<SectionBase> New);
+
+  MutableObjectRange<SectionBase> sections() const;
+  MutableObjectRange<SegmentBase> segments() const;
+
+  /// Creates a new section if Section is larger than the number of sections,
+  /// or returns a mutable copy of a current section.
+  SectionBase &getMutableSection(DataRef Section);
+
+  SegmentBase &getMutableSegment(DataRef Segment);
+};
+
+} // namespace mutable_object
+} // namespace object
+} // namespace llvm
+
+#endif // LLVM_OBJECT_MUTABLEOBJECT_H

llvm/lib/Object/CMakeLists.txt

add_llvm_library(LLVMObject
   ELFObjectFile.cpp
   Error.cpp
   IRObjectFile.cpp
   IRSymtab.cpp
   MachOObjectFile.cpp
   MachOUniversal.cpp
   Minidump.cpp
   ModuleSymbolTable.cpp
+  MutableELFObject.cpp
+  MutableObject.cpp
   Object.cpp
   ObjectFile.cpp
   RecordStreamer.cpp
   RelocationResolver.cpp
   SymbolicFile.cpp
   SymbolSize.cpp
   WasmObjectFile.cpp
   WindowsMachineFlag.cpp

llvm/lib/Object/MutableObject.cpp

+#include "llvm/Object/MutableObject.h"
+
+namespace llvm {
+namespace object {
+namespace mutable_object {
+
+SectionBase::SectionBase(const MutableObject &OwningObject,
+              ArrayRef<uint8_t> Data, StringRef Name)
+: OwningObject(OwningObject), Data(Data), Name(Name) {}
+
+StringRef SectionBase::name() const {
+  return Name;
+}
+
+ArrayRef<uint8_t> SectionBase::data() const {
+  return Data;
+}
+
+const MutableObject &SectionBase::getOwningObject() const {
+  return OwningObject;
+}
+
+SegmentBase::SegmentBase(const MutableObject &OwningObject)
+: OwningObject(OwningObject) {}
+
+void SegmentBase::removeSection(uint64_t Section) {
+  Sections.erase(Section);
+}
+
+void SegmentBase::addSection(uint64_t Section) {
+  Sections.insert(Section);
+}
+
+const ObjectFile &MutableObject::getObjectFile() const {
+  return ObjFile;
+}
+
+Optional<DataRef> MutableObject::findSectionByName(StringRef Name) const {
+  auto Range = sections();
+  const auto End = Range.end();
+  for (auto Iter = Range.begin(); Iter != End; ++Iter)
+    if (Iter->name() == Name)
+      return Iter.getCurrentDataRef();
+  return None;
+}
+
+Error MutableObject::removeSection(DataRef Section) {
+  return Sections.remove(Section);
+}
+
+Error MutableObject::replaceSection(DataRef ToReplace,
+                                    std::unique_ptr<SectionBase> New) {
+  return Sections.update(ToReplace, std::move(New));
+}
+
+MutableObjectRange<SectionBase> MutableObject::sections() const {
+  return MutableObjectRange(Sections);
+}
+
+MutableObjectRange<SegmentBase> MutableObject::segments() const {
+  return MutableObjectRange<SegmentBase>(Segments);
+}
+
+SectionBase &MutableObject::getMutableSection(DataRef Section) {
+  Sections.getNew(Section);
+}
+
+SegmentBase &MutableObject::getMutableSegment(DataRef Segment) {
+  Segments.getNew(Segment);
+}
+
+} // namespace mutable_object
+} // namespace object
+} // namespace llvm