BumpPtr allocate SimpleReferences

[kledzik]

Summary

The mach-o part of lld has a leak because it BumpPtr allocates SimpleDefinedAtoms. The problem is SimpleDefinedAtom has a ivar that is a vector of SimpleReferences. Since BumpPtr allocated objects are not destructed, the allocations done in the vector are leaked.

This fix is to add a BumpPtrAllocator to the base lld::File class and alter SimpleDefinedAtom to allocate its SimpleReference in the BumpPtr pool. The mess is that vectors don't BumpPtrAllocate well, so I switched to using a linked list (llvm::ilist<>) for the SimpleReference.

I tried adding the BumpPtrAllocator instead to some subclasses of lld::File, but failed because a handful of places add SimpleDefinedAtom to lots of different subclasses of File. And since the general model is that Atoms are owned by their File, it makes sense to have an allocator in the File for allocating various objects related to the file or atoms (e.g. strings).

[ruiu]

Why don't you make a new instance of Reference using operator new and store the pointer to File's std::vector<std::unique_ptr<Reference>>? If you do that, Reference's destructor would be called. Is there any reason to continue using BumpPtrAllocator?

[kledzik]

Even if you add a std::vector<std::unique_ptr<Reference>> to lld::File (so the SimpleReferences are deleted when the File is deleted), you still need a std::vector<SimpleReference*> in each SimpleDefineAtom to track which references are used by that atom. And the allocations for that vector would be leaked if the Atom is BumpPtr allocated.

References are not that big and are never removed. The current std::vector<SimpleReference> in SimpleDefinedAtom does a lot of copying as references are added. This is a good use case for BumpPtr allocation.

The only other sane thing to do is never BumpPtr allocate Simple Atoms. But that is sad because BumpPtr allocation is an efficient way to create atoms while parsing a file.

[shankarke]

I like the idea of using the file allocator for all objects that would be owned by that file. If you keep a vector of std::vector<SimpleReference *> and allocate the simple references by using the file allocator, wouldn't it suffice ?

This would essentially destroy all the references when the File goes away, Am I missing something ?

[Jean-Daniel]

In D6518#7, @shankarke wrote:

This would essentially destroy all the references when the File goes away, Am I missing something ?

Yes, you miss the memory allocated by the vector to store the pointers themselves. The problem is that whatever you store in the vector, it need to allocate storage, and as the vector destructor is never called, that memory will leaks.

[shankarke]

We could use include/clang/Analysis/Support/BumpVector.h which simplifies things. For this the header file has to be moved to llvm/Support.

http://clang.llvm.org/doxygen/BumpVector_8h_source.html.

The vector class takes a

BumpVectorContext(llvm::BumpPtrAllocator &A)

[ruiu]

I think the other way is to pass a custom Allocator backed by a BumpPtr owned by File to std::vector owned by DefinedAtom, so that the vector in a DefinedAtom is freed when the file is deleted. I'd expect it would be faster than the linked list (because of better memory locality). Also could eliminate the copy-to-vector-and-sort code.

[kledzik]

A downside to BumpVector is that as the vector grows (by adding References), the capacity is doubled by bump allocating a new chunk. All the previous allocations (e.g. if current at 8 elements, the allocs for 1, 2, and 4) are wasted space in the bumpptr pool.

A linked list does not have this problem because the elements never move and are never copying. They just have a pointer to the next one.

[shankarke]

But using the BumpVector makes the code cleaner too right ? and also the memory sanitizers will not show any more leaks as they are going to be freed.

Another possiblity would be to resize the BumpVector by the size of references we need completely(by counting the number of relocation records).

[kledzik]

But using the BumpVector makes the code cleaner too right ?

Only because you are adding new BumpVector code. We could also add a new BumpList class to ADT and that would make the lld code very clean too.

and also the memory sanitizers will not show any more leaks as they are going to be freed.

That is a false negative. There will be leaks (unuseable memory lost) in the BumPtr pools.

Another possiblity would be to resize the BumpVector by the size of references we need completely(by counting the number of relocation records).

On mach-o, there is not a one-to-one mapping of relocations to references. Also that would take an extra pass to group relocs by atom before creating the References. Right now, it takes one pass to iterate across all relocs, create a Reference, then figure out what atom to add it to.

[colinl]

Won't "RefList _reference" leak the nodes of the linked list in the same way it leaks the vector backing allocation? Without an allocator template llvm:ilist is using new under the hood to allocate list nodes.

N/M, the pointers are internal to the items themselves.

[kledzik]

Won't "RefList _reference" leak the nodes of the linked list

They are allocated in the BumpPtr pool at:

node = new (_file.allocator()) SimpleReference(...)

[colinl]

It doesn't seem like there's any memory different between the linked list version and the bumpvector version. The linked list version requires 2*(pointer_size)*N memory and if a bumpvector is resized to double each time, the sum of all intermediate backing allocations comes out the same.

16 Items in a linked list requires 2*16*pointer
16 Items in a bumpvector requires (1+2+4+8+16)*pointer

[ruiu]

I think Colin's calculation is correct. That makes me think of whether or
not we really want to use BumpPtr allocator at all. We might be trying to
optimize too much without knowing if this is important for performance (I
could be easily convinced if there's benchmark result). Regular memory
allocator shouldn't be that slow, and instead of doing something clever
with BumpPtr, we can always use operator new and smart pointers.

[kledzik]

Colin's calculation is based on the bumpvector containing only the *pointer* to the Reference. The current implementation has a vector< SimpleReference>, so the wasted space is not just a pointer size (repeatedly doubled). A SimpleReference is 64 bytes in size, so that value keeps getting doubled (and wasted).

Even if we switched to using a bumpvector for a pointer to reference, we still need to allocate the SimpleReference body somewhere.

For Atoms and References, the best allocator is a BumpPtr allocator. Because, 1) Atoms (and References) are owned by their File and ownership never changes, 2) they are never destructed (until the File is destructed). If either of those was false, then we could not use BumpPtr.

The reason for this patch is because the current SimpleDefinedAtom has an embedded vector which means SimpleDefinedAtom (and subclasses) cannot be BumpPtr allocated (without leaking). If we don't want to change SimpleDefinedAtom, I can change MachODefinedATom to not subclass SimpleDefinedAtom.

[ruiu]

I was thinking that Colin has suggested to store pointers to the vector
instead of the object itself.

I think the patch is good to land. There seems to be other ways to do the
same thing, but the code is mostly at one place, so we can revisit this
topic if we need to. This patch wouldn't harm anyone who doesn't touch this
code.

And the memory leak is a real issue which has to be resolved.

[ruiu]

Looks like no serious concerns regarding this change. LGTM in case you need this word.

[Jean-Daniel]

Just a side note. After this patch, we should probably take some time to review all subclasses of File that also provide a bump allocator and remove it to use the File's one instead.

[kledzik]

commited in r 223528

include/lld/Core/File.h

 
   template <typename T> class atom_iterator; // forward reference
 
+  /// For allocating any objects owned by this File.
+  llvm::BumpPtrAllocator &allocator() const {
+    return _allocator;
+  }
+
   /// \brief For use interating over DefinedAtoms in this File.
   typedef atom_iterator<DefinedAtom>  defined_iterator;
 

   static atom_collection_empty<UndefinedAtom>     _noUndefinedAtoms;
   static atom_collection_empty<SharedLibraryAtom> _noSharedLibraryAtoms;
   static atom_collection_empty<AbsoluteAtom>      _noAbsoluteAtoms;
+  mutable llvm::BumpPtrAllocator                  _allocator;
 
 private:
   StringRef _path;

include/lld/Core/Simple.h

 #ifndef LLD_CORE_SIMPLE_H
 #define LLD_CORE_SIMPLE_H
 
+#include "llvm/ADT/ilist.h"
+#include "llvm/ADT/ilist_node.h"
 #include "lld/Core/DefinedAtom.h"
 #include "lld/Core/File.h"
 #include "lld/Core/Reference.h"

   SimpleReference(Reference::KindNamespace ns, Reference::KindArch arch,
                   Reference::KindValue value, uint64_t off, const Atom *t,
                   Reference::Addend a)
-      : Reference(ns, arch, value), _target(t), _offsetInAtom(off), _addend(a) {
+      : Reference(ns, arch, value), _target(t), _offsetInAtom(off), _addend(a),
+        _next(nullptr), _prev(nullptr) {
+  }
+  SimpleReference()
+      : Reference(Reference::KindNamespace::all, Reference::KindArch::all, 0),
+        _target(nullptr), _offsetInAtom(0), _addend(0), _next(nullptr),
+        _prev(nullptr) {
   }
 
   uint64_t offsetInAtom() const override { return _offsetInAtom; }

   Addend addend() const override { return _addend; }
   void setAddend(Addend a) override { _addend = a; }
   void setTarget(const Atom *newAtom) override { _target = newAtom; }
+  SimpleReference *getNext() const { return _next; }
+  SimpleReference *getPrev() const { return _prev; }
+  void setNext(SimpleReference *n) { _next = n; }
+  void setPrev(SimpleReference *p) { _prev = p; }
 
 private:
   const Atom *_target;
   uint64_t _offsetInAtom;
   Addend _addend;
+  SimpleReference *_next;
+  SimpleReference *_prev;
 };
 
+}
+
+// ilist will lazily create a sentinal (so end() can return a node past the
+// end of the list). We need this trait so that the sentinal is allocated
+// via the BumpPtrAllocator.
+namespace llvm {
+template<>
+struct ilist_sentinel_traits<lld::SimpleReference> {
+
+  ilist_sentinel_traits() : _allocator(nullptr) { }
+
+  void setAllocator(llvm::BumpPtrAllocator *alloc) {
+    _allocator = alloc;
+  }
+
+  lld::SimpleReference *createSentinel() const {
+    return new (*_allocator) lld::SimpleReference();
+  }
+
+  static void destroySentinel(lld::SimpleReference*) {}
+
+  static lld::SimpleReference *provideInitialHead() { return nullptr; }
+
+  lld::SimpleReference *ensureHead(lld::SimpleReference *&head) const {
+    if (!head) {
+      head = createSentinel();
+      noteHead(head, head);
+      ilist_traits<lld::SimpleReference>::setNext(head, nullptr);
+      return head;
+    }
+    return ilist_traits<lld::SimpleReference>::getPrev(head);
+  }
+
+  void noteHead(lld::SimpleReference *newHead,
+                lld::SimpleReference *sentinel) const {
+    ilist_traits<lld::SimpleReference>::setPrev(newHead, sentinel);
+  }
+
+private:
+  mutable llvm::BumpPtrAllocator *_allocator;
+};
+}
+
+namespace lld {
+
 class SimpleDefinedAtom : public DefinedAtom {
 public:
   explicit SimpleDefinedAtom(const File &f) : _file(f) {
     static uint32_t lastOrdinal = 0;
     _ordinal = lastOrdinal++;
+    _references.setAllocator(&f.allocator());
   }
 
   const File &file() const override { return _file; }

   }
 
   DefinedAtom::reference_iterator begin() const override {
-    uintptr_t index = 0;
-    const void *it = reinterpret_cast<const void *>(index);
+    const void *it = reinterpret_cast<const void *>(&*_references.begin());
     return reference_iterator(*this, it);
   }
 
   DefinedAtom::reference_iterator end() const override {
-    uintptr_t index = _references.size();
-    const void *it = reinterpret_cast<const void *>(index);
+    const void *it = reinterpret_cast<const void *>(&*_references.end());
     return reference_iterator(*this, it);
   }
 
   const Reference *derefIterator(const void *it) const override {
-    uintptr_t index = reinterpret_cast<uintptr_t>(it);
-    assert(index < _references.size());
-    return &_references[index];
+    return reinterpret_cast<const Reference*>(it);
   }
 
   void incrementIterator(const void *&it) const override {
-    uintptr_t index = reinterpret_cast<uintptr_t>(it);
-    ++index;
-    it = reinterpret_cast<const void *>(index);
+    const SimpleReference* node = reinterpret_cast<const SimpleReference*>(it);
+    const SimpleReference* next = node->getNext();
+    it = reinterpret_cast<const void*>(next);
   }
 
   void addReference(Reference::KindNamespace ns, Reference::KindArch arch,
                     Reference::KindValue kindValue, uint64_t off,
                     const Atom *target, Reference::Addend a) {
     assert(target && "trying to create reference to nothing");
-    _references.push_back(SimpleReference(ns, arch, kindValue, off, target, a));
+    auto node = new (_file.allocator()) SimpleReference(ns, arch, kindValue, off, target, a);
+    _references.push_back(node);
   }
 
   /// Sort references in a canonical order (by offset, then by kind).
   void sortReferences() const {
-    std::sort(_references.begin(), _references.end(),
-        [] (const SimpleReference &lhs, const SimpleReference &rhs) -> bool {
-          uint64_t lhsOffset = lhs.offsetInAtom();
-          uint64_t rhsOffset = rhs.offsetInAtom();
+    // Cannot sort a linked  list, so move elements into a temporary vector,
+    // sort the vector, then reconstruct the list.
+    llvm::SmallVector<SimpleReference *, 16> elements;
+    for (SimpleReference &node : _references) {
+      elements.push_back(&node);
+    }
+    std::sort(elements.begin(), elements.end(),
+        [] (const SimpleReference *lhs, const SimpleReference *rhs) -> bool {
+          uint64_t lhsOffset = lhs->offsetInAtom();
+          uint64_t rhsOffset = rhs->offsetInAtom();
           if (rhsOffset != lhsOffset)
             return (lhsOffset < rhsOffset);
-          if (rhs.kindNamespace() != lhs.kindNamespace())
-            return (lhs.kindNamespace() < rhs.kindNamespace());
-          if (rhs.kindArch() != lhs.kindArch())
-            return (lhs.kindArch() < rhs.kindArch());
-          return (lhs.kindValue() < rhs.kindValue());
+          if (rhs->kindNamespace() != lhs->kindNamespace())
+            return (lhs->kindNamespace() < rhs->kindNamespace());
+          if (rhs->kindArch() != lhs->kindArch())
+            return (lhs->kindArch() < rhs->kindArch());
+          return (lhs->kindValue() < rhs->kindValue());
         });
+    _references.clearAndLeakNodesUnsafely();
+    for (SimpleReference *node : elements) {
+      _references.push_back(node);
+    }
   }
   void setOrdinal(uint64_t ord) { _ordinal = ord; }
 
 private:
+  typedef llvm::ilist<SimpleReference> RefList;
+
   const File                   &_file;
   uint64_t                      _ordinal;
-  mutable std::vector<SimpleReference>  _references;
+  mutable RefList               _references;
 };
 
 class SimpleUndefinedAtom : public UndefinedAtom {