Add DiscardableMemoryAllocator to work around FD limit issue.

base/memory/discardable_memory_allocator_android.cc

+// Copyright 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/memory/discardable_memory_allocator_android.h"
+
+#include <algorithm>
+#include <cmath>
+#include <set>
+#include <utility>
+
+#include "base/basictypes.h"
+#include "base/containers/hash_tables.h"
+#include "base/logging.h"
+#include "base/memory/discardable_memory.h"
+#include "base/memory/discardable_memory_android.h"
+#include "base/memory/scoped_vector.h"
+#include "base/strings/stringprintf.h"
+#include "base/synchronization/lock.h"
+#include "base/threading/thread_checker.h"
+
+// The allocator consists of three parts (classes):
+// - DiscardableMemoryAllocator: entry point of all allocations (through its
+// Allocate() method) that are dispatched to the AshmemRegion instances (which
+// it owns).
+// - AshmemRegion: manages allocations and destructions inside a single large
+// (e.g. 32 MBytes) ashmem region.
+// - DiscardableAshmemChunk: class implementing the DiscardableMemory interface
+// whose instances are returned to the client. DiscardableAshmemChunk lets the
+// client seamlessly operate on a subrange of the ashmem region managed by
+// AshmemRegion.
+
+namespace base {
+namespace {
+
+// Allow 8 KBytes of fragmentation inside used chunks.
+const size_t kMaxChunkFragmentationBytes = 8192;
+
+}  // namespace
+
+namespace internal {
+
+class DiscardableMemoryAllocator::DiscardableAshmemChunk
+    : public DiscardableMemory {
+ public:
+  // Note that |ashmem_region| must outlive |this|.
+  DiscardableAshmemChunk(AshmemRegion* ashmem_region,
+                         int fd,
+                         void* address,
+                         size_t offset,
+                         size_t size)
+      : ashmem_region_(ashmem_region),
+        fd_(fd),
+        address_(address),
+        offset_(offset),
+        size_(size),
+        locked_(true) {
+  }
+
+  // Implemented below AshmemRegion since this requires the full definition of
+  // AshmemRegion.
+  virtual ~DiscardableAshmemChunk();
+
+  // DiscardableMemory:
+  virtual LockDiscardableMemoryStatus Lock() OVERRIDE {
+    DCHECK(!locked_);
+    locked_ = true;
+    return internal::LockAshmemRegion(fd_, offset_, size_, address_);
+  }
+
+  virtual void Unlock() OVERRIDE {
+    DCHECK(locked_);
+    locked_ = false;
+    internal::UnlockAshmemRegion(fd_, offset_, size_, address_);
+  }
+
+  virtual void* Memory() const OVERRIDE {
+    return address_;
+  }
+
+ private:
+  AshmemRegion* const ashmem_region_;
+  const int fd_;
+  void* const address_;
+  const size_t offset_;
+  const size_t size_;
+  bool locked_;
+
+  DISALLOW_COPY_AND_ASSIGN(DiscardableAshmemChunk);
+};
+
+class DiscardableMemoryAllocator::AshmemRegion {
+ public:
+  // Note that |allocator| must outlive |this|.
+  static scoped_ptr<AshmemRegion> Create(
+      size_t size,
+      const std::string& name,
+      DiscardableMemoryAllocator* allocator) {
+    int fd;
+    void* base;
+    if (!internal::CreateAshmemRegion(name.c_str(), size, &fd, &base))
+      return scoped_ptr<AshmemRegion>();
+    return make_scoped_ptr(new AshmemRegion(fd, size, base, allocator));
+  }
+
+  virtual ~AshmemRegion() {
+    const bool result = internal::CloseAshmemRegion(fd_, size_, base_);
+    DCHECK(result);
+  }
+
+  // Returns a new instance of DiscardableMemory whose size is greater or equal
+  // than |actual_size| (which is expected to be greater or equal than
+  // |client_requested_size|).
+  // Allocation works as follows:
+  // 1) Reuse a previously freed chunk and return it if it succeeded. See
+  // ReuseFreeChunk_Locked() below for more information.
+  // 2) If no free chunk could be reused and the region is not big enough for
+  // the requested size then NULL is returned.
+  // 3) If there is enough room in the ashmem region then a new chunk is
+  // returned. This new chunk starts at |offset_| which is the end of the
+  // previously highest chunk in the region.
+  scoped_ptr<DiscardableMemory> Allocate_Locked(size_t client_requested_size,
+                                                size_t actual_size) {
+    DCHECK_LE(client_requested_size, actual_size);
+    allocator_->lock_.AssertAcquired();
+    scoped_ptr<DiscardableMemory> memory = ReuseFreeChunk_Locked(
+        client_requested_size, actual_size);
+    if (memory)
+      return memory.Pass();
+    if (size_ - offset_ < actual_size) {
+      // This region does not have enough space left to hold the requested size.
+      return scoped_ptr<DiscardableMemory>();
+    }
+    void* const address = static_cast<char*>(base_) + offset_;
+    memory.reset(
+        new DiscardableAshmemChunk(this, fd_, address, offset_, actual_size));
+    previous_chunk_for_used_chunk_.insert(

[willchan no longer on Chromium, 2013/11/28 06:16:37]

Nit: I don't know if my suggestion will be any better, but it took me a little
bit earlier to understand this member variable. I had to go look it up, see it
was a hash_map, and then look at the uses to figure out which was the key and
which was the value. FWIW, I'd go with |used_to_previous_chunk_map_|. But up to
you. Naming is Hard (TM).

[Philippe, 2013/11/28 16:42:53]

Yeah, I also renamed |free_chunk_for_address_| accordingly for consistency.

+        std::make_pair(address, highest_allocated_chunk_));
+    highest_allocated_chunk_ = address;
+    offset_ += actual_size;
+    return memory.Pass();
+  }
+
+  void OnChunkDeletion(void* chunk, size_t size) OVERRIDE {
+    base::AutoLock auto_lock(allocator_->lock_);
+    MergeAndAddFreeChunk_Locked(chunk, size);
+  }
+
+ private:
+  struct FreeChunk {
+    FreeChunk(void* previous_chunk, void* start, size_t size)
+        : previous_chunk(previous_chunk),
+          start(start),
+          size(size) {
+    }
+
+    void* const previous_chunk;
+    void* const start;
+    const size_t size;
+
+    bool is_null() const { return !start; }
+
+    bool operator<(const FreeChunk& other) const {
+      return size < other.size;
+    }
+  };
+
+  AshmemRegion(int fd,
+               size_t size,
+               void* base,
+               DiscardableMemoryAllocator* allocator)
+      : fd_(fd),
+        size_(size),
+        base_(base),
+        offset_(0),
+        allocator_(allocator),
+        highest_allocated_chunk_(NULL) {

[willchan no longer on Chromium, 2013/11/28 06:16:37]

Can you DCHECK the parameters and comment that |allocator| must outlive
AshmemRegion?

[Philippe, 2013/11/28 16:42:53]

Sure. One of the good points about immutability is that the parameters can be
checked only once at construction.

+  }
+
+  // Tries to reuse a previously freed chunk by doing a closest size match.
+  scoped_ptr<DiscardableMemory> ReuseFreeChunk_Locked(
+      size_t client_requested_size,
+      size_t actual_size) {
+    allocator_->lock_.AssertAcquired();
+    const std::multiset<FreeChunk>::iterator chunk_it =
+        free_chunks_.lower_bound(FreeChunk(NULL, NULL, actual_size));
+    if (chunk_it == free_chunks_.end())
+      return scoped_ptr<DiscardableMemory>();
+    size_t reused_chunk_size = chunk_it->size;
+    const size_t fragmentation_bytes = chunk_it->size - client_requested_size;

[willchan no longer on Chromium, 2013/11/28 06:16:37]

I'm trying to understand why you're subtracting the chunk size by
|client_requested_size| here rather than |actual_size|. Here is the case I'm
considering:
Free chunk of size 10KB. If trying to allocate <=2KB, then it'll be split, but
it won't be split when allocating 2KB<x<=4KB bytes. That's even though the
actual size allocated in each is 4KB due to page alignment.

I'm not objecting to this algorithmic choice...I just don't understand the
pros/cons here. Why is it better to split the chunk in the <=2KB case, but not
the 2KB<x<=4KB case? Comments would be appreciated.

[Philippe, 2013/11/28 16:42:53]

I might be missing something here but my initial intent was to consider as
fragmentation all the bytes that would not be visible by the client. If the
client asks for 2 KBytes and the free chunk size is 4 KBytes, then there is a
waste of 2 KBytes (i.e. nobody would use those 2 KBytes). If we use
|actual_size| to do the computation then we would not see this waste (i.e.
|fragmentation_bytes| would be 0). I agree that the current value of
|kMaxChunkFragmentationBytes| (8192) is quite arbitrary/wrong though and I'm
quite tempted to decrease it since this allocator tries to be optimized for
memory rather than speed. We can see later if splitting chunks too often leads
to performance issues. I added a comment at the top where the constant is
defined. Also I will have a follow up CLs to report statistics. Two of them will
be fragmentation (in pinned memory) caused by the client (since I'm now
forbidding the allocator to cause fragmentation when a chunk gets reused) and
"discardable fragmentation" (unpinned memory in the free chunks).

Does that make any sense? What do you think?

[willchan no longer on Chromium, 2013/11/28 17:44:19]

I agree that the current calculation is more accurate in terms of determining
unused bytes / fragmentation. I guess what I was thinking is it's not how many
bytes get wasted that matters, but rather how many bytes can be gained by
splitting.

I'm having difficulty thinking through the implications of this fragmentation.
I'm inclined to let you do what you want here and take on the responsibility of
fixing it once you have data on actual performance.

[Philippe, 2013/11/29 12:41:05]

Right, I understand now your point of view. I will profile this once we
submitted this to have a baseline.

+    if (fragmentation_bytes >= kMaxChunkFragmentationBytes) {
+      SplitFreeChunk_Locked(*chunk_it, actual_size);

[willchan no longer on Chromium, 2013/11/28 06:16:37]

OK, I thought about it. Keep it if you prefer, but I'd like to restructure the
code thusly:
* Kill off SplitFreeChunk_Locked(), move the code in here.
* Actually remove the FreeChunk (update |free_chunk_for_address_| and
|free_chunks_|) sooner rather than at the end of the function. Store a copy of
it in a local variable. Ah, I see you have a RemoveFreeChunk_Locked() function.
That sounds perfect to me.

My reasoning is, although I like smaller, more granular functions, I feel like
these are fairly tightly coupled. SplitFreeChunk_Locked() isn't actually
splitting the chunk. It's adding another (smaller) FreeChunk and updating the
next used chunk to point to the new smaller one. But at the end of this
function, we have this weird state where the data structures have two
FreeChunks, one of which is subsumed by the other larger one, which is in
process of being removed. That's what I mean by coupling. I then have to look to
make sure that there are no other consumers for this SplitFreeChunk_Locked()
function, and have to make sure there is never any new consumer that violates
the invariants. That's why I think it's simpler to just move it into the calling
function. I think this also enables actually removing the FreeChunk from the
various data structures before adding the new one.

Up to you though if you feel the current/another way is cleaner.

[Philippe, 2013/11/28 16:42:53]

Agreed. I had externalized free chunk splitting to improve "visual readability"
by making this function smaller but it was at the cost of actual readability.

+      reused_chunk_size = actual_size;
+    }
+    const size_t offset =
+        static_cast<char*>(chunk_it->start) - static_cast<char*>(base_);
+    internal::LockAshmemRegion(
+        fd_, offset, reused_chunk_size, chunk_it->start);
+    scoped_ptr<DiscardableMemory> memory(
+        new DiscardableAshmemChunk(this, fd_, chunk_it->start, offset,
+                                   reused_chunk_size));
+    previous_chunk_for_used_chunk_.insert(
+        std::make_pair(chunk_it->start, chunk_it->previous_chunk));
+    free_chunk_for_address_.erase(chunk_it->start);
+    free_chunks_.erase(chunk_it);
+    return memory.Pass();
+  }
+
+  // Splits the free chunk being reused so that its unused tail doesn't get
+  // reused (i.e. locked) which would prevent it from being evicted under memory
+  // pressure.
+  void SplitFreeChunk_Locked(const FreeChunk& free_chunk,
+                             size_t allocation_size) {
+    allocator_->lock_.AssertAcquired();
+    void* const previous_chunk = free_chunk.start;
+    void* const new_chunk_start =
+        static_cast<char*>(free_chunk.start) + allocation_size;
+    const size_t new_chunk_size = free_chunk.size - allocation_size;

[willchan no longer on Chromium, 2013/11/28 06:16:37]

Please add a DCHECK_GT(free_chunk.size, allocation_size).

[Philippe, 2013/11/28 16:42:53]

Yeah good point.

+    // Note that merging is not needed here since there can't be contiguous
+    // free chunks at this point.
+    AddFreeChunk_Locked(
+        FreeChunk(previous_chunk, new_chunk_start, new_chunk_size));
+    // Update the next used contiguous chunk, if any, since its previous chunk
+    // is no longer |free_chunk.start|.
+    void* const next_used_contiguous_chunk =
+        static_cast<char*>(free_chunk.start) + free_chunk.size;
+    base::hash_map<void*, void*>::iterator previous_it =
+        previous_chunk_for_used_chunk_.find(next_used_contiguous_chunk);
+    if (previous_it != previous_chunk_for_used_chunk_.end())
+      previous_it->second = new_chunk_start;
+  }
+
+  // Makes the chunk identified with the provided arguments free and possibly
+  // merges this chunk with the previous and next contiguous ones.
+  // If the provided chunk is the only one used (and going to be freed) in the
+  // region then the internal ashmem region is closed so that the underlying
+  // physical pages are immediately released.
+  // Note that free chunks are unlocked therefore they can be reclaimed by the
+  // kernel if needed (under memory pressure) but they are not immediately
+  // released unfortunately since madvise(MADV_REMOVE) and
+  // fallocate(FALLOC_FL_PUNCH_HOLE) don't seem to work on ashmem. This might
+  // change in versions of kernel >=3.5 though. The fact that free chunks are
+  // not immediately released is the reason why we are trying to minimize
+  // fragmentation in order not to cause "artificial" memory pressure.
+  void MergeAndAddFreeChunk_Locked(void* chunk, size_t size) {
+    allocator_->lock_.AssertAcquired();
+    size_t new_free_chunk_size = size;
+    // Merge with the previous chunks.
+    void* first_free_chunk = chunk;
+    const base::hash_map<void*, void*>::iterator previous_chunk_it =
+        previous_chunk_for_used_chunk_.find(chunk);
+    DCHECK(previous_chunk_it != previous_chunk_for_used_chunk_.end());
+    void* previous_chunk = previous_chunk_it->second;
+    previous_chunk_for_used_chunk_.erase(previous_chunk_it);
+    while (previous_chunk) {

[willchan no longer on Chromium, 2013/11/28 06:16:37]

I don't understand this while loop. There shouldn't be more than one
_contiguous_ previous _free_ chunk, right? Otherwise, it should already have
been merged...

If previous_chunk is non-NULL on the 2nd iteration, I think it must be a used
chunk.

[Philippe, 2013/11/28 16:42:53]

Yeah, you're right. I added a DCHECK though :)

+      const FreeChunk free_chunk = RemoveFreeChunk_Locked(previous_chunk);
+      if (free_chunk.is_null())
+        break;
+      new_free_chunk_size += free_chunk.size;
+      first_free_chunk = previous_chunk;
+      previous_chunk = free_chunk.previous_chunk;
+    }
+    // Merge with the next chunks.
+    void* next_chunk = static_cast<char*>(chunk) + size;
+    while (true) {

[willchan no longer on Chromium, 2013/11/28 06:16:37]

Ditto, unsure if the while loop is necessary.

[Philippe, 2013/11/28 16:42:53]

Done.

+      const FreeChunk free_chunk = RemoveFreeChunk_Locked(next_chunk);
+      if (free_chunk.is_null())
+        break;
+      new_free_chunk_size += free_chunk.size;
+      next_chunk = static_cast<char*>(next_chunk) + free_chunk.size;
+    }
+    const bool whole_ashmem_region_is_free = new_free_chunk_size == size_;
+    if (!whole_ashmem_region_is_free) {
+      AddFreeChunk_Locked(
+          FreeChunk(previous_chunk, first_free_chunk, new_free_chunk_size));
+      return;
+    }
+    // The whole ashmem region is free thus it can be deleted.
+    DCHECK_EQ(size_, new_free_chunk_size);

[willchan no longer on Chromium, 2013/11/28 06:16:37]

Unneeded, this was just checked above. It'd be good to DCHECK_EQ(base_,
first_free_chunk) though.

[Philippe, 2013/11/28 16:42:53]

Yeah, good point. The DCHECK you suggested actually raised a bug :) (which made
me move the code updating the next contiguous chunk to AddFreeChunk()).

+    DCHECK(free_chunks_.empty() && free_chunk_for_address_.empty());

[willchan no longer on Chromium, 2013/11/28 06:16:37]

previous_chunk_for_used_chunk_ should be empty too, right?

[Philippe, 2013/11/28 16:42:53]

Yes, I had forgotten to update this code when I added
|previous_chunk_for_used_chunk_|.

+    allocator_->DeleteAshmemRegion_Locked(this);
+  }
+
+  void AddFreeChunk_Locked(const FreeChunk& free_chunk) {
+    allocator_->lock_.AssertAcquired();
+    const std::multiset<FreeChunk>::iterator it = free_chunks_.insert(
+        free_chunk);
+    free_chunk_for_address_.insert(std::make_pair(free_chunk.start, it));
+  }
+
+  // Finds and removes the free chunk, if any, whose start address is
+  // |chunk_start|. Returns a copy of the unlinked free chunk or a free chunk
+  // whose content is null if it was not found.
+  FreeChunk RemoveFreeChunk_Locked(void* chunk_start) {
+    allocator_->lock_.AssertAcquired();
+    const base::hash_map<
+        void*, std::multiset<FreeChunk>::iterator>::iterator it =
+            free_chunk_for_address_.find(chunk_start);
+    if (it == free_chunk_for_address_.end())
+      return FreeChunk(NULL, NULL, 0U);
+    const std::multiset<FreeChunk>::iterator free_chunk_it = it->second;
+    const FreeChunk free_chunk(*free_chunk_it);
+    DCHECK_EQ(chunk_start, free_chunk.start);
+    free_chunk_for_address_.erase(it);
+    free_chunks_.erase(free_chunk_it);
+    return free_chunk;
+  }
+
+  const int fd_;
+  const size_t size_;
+  void* const base_;
+  size_t offset_;

[willchan no longer on Chromium, 2013/11/28 06:16:37]

Can you move this next to highest_allocated_chunk_? And comment what it is (the
end of the highest allocated chunk).

[Philippe, 2013/11/28 16:42:53]

Done.

+  DiscardableMemoryAllocator* const allocator_;
+  void* highest_allocated_chunk_;
+  // Allows free chunks recycling (lookup, insertion and removal) in O(log N).
+  // Note that FreeChunk values are indexed by their size and also note that
+  // multiple free chunks can have the same size (which is why multiset<> is
+  // used instead of e.g. set<>).
+  std::multiset<FreeChunk> free_chunks_;
+  // Used while merging free contiguous chunks to erase free chunks (from their
+  // start address) in constant time. Note that multiset<>::{insert,erase}()
+  // don't invalidate iterators (except the one for the element being removed
+  // obviously).
+  base::hash_map<
+      void*, std::multiset<FreeChunk>::iterator> free_chunk_for_address_;
+  // Maps the address of *used* chunks to the address of their previous
+  // contiguous chunk.
+  base::hash_map<void*, void*> previous_chunk_for_used_chunk_;
+
+  DISALLOW_COPY_AND_ASSIGN(AshmemRegion);
+};
+
+DiscardableMemoryAllocator::DiscardableAshmemChunk::~DiscardableAshmemChunk() {
+  if (locked_)
+    internal::UnlockAshmemRegion(fd_, offset_, size_, address_);
+  ashmem_region_->OnChunkDeletion(address_, size_);
+}
+
+DiscardableMemoryAllocator::DiscardableMemoryAllocator(const std::string& name)
+    : name_(name) {
+}
+
+DiscardableMemoryAllocator::~DiscardableMemoryAllocator() {
+  DCHECK(thread_checker_.CalledOnValidThread());

[willchan no longer on Chromium, 2013/11/28 06:16:37]

I think it'd be good to DCHECK(ashmem_regions_.empty()). Might catch a leak in
the tests that way.

[Philippe, 2013/11/28 16:42:53]

Great idea! This might also catch uses after free btw since the used chunks have
a pointer to their ashmem region. In practice this code path will be very
rarely/never taken in production though since this is used in a leaky lazy
instance but anyway, good idea.

Also, this caught another small bug which made me change
|whole_ashmem_region_is_free| in the chunks merging function.

+}
+
+scoped_ptr<DiscardableMemory> DiscardableMemoryAllocator::Allocate(
+    size_t size) {
+  // TODO(pliard): make this function less naive by e.g. moving the free chunks
+  // multiset to the allocator itself in order to decrease even more
+  // fragmentation/speedup allocation. Note that there should not be more than a
+  // couple of AshmemRegion instances in practice though.

[willchan no longer on Chromium, 2013/11/28 06:16:37]

Can we throw up a DCHECK() for this, so people hit the DCHECK and notice that
they should be optimizing this? Pick whatever arbitrary constant you think makes
sense.

[Philippe, 2013/11/28 16:42:53]

Good idea!

+  const size_t aligned_size = internal::AlignToNextPage(size);
+  base::AutoLock auto_lock(lock_);
+  for (ScopedVector<AshmemRegion>::iterator it = ashmem_regions_.begin();
+       it != ashmem_regions_.end(); ++it) {
+    scoped_ptr<DiscardableMemory> memory(
+        (*it)->Allocate_Locked(size, aligned_size));
+    if (memory)
+      return memory.Pass();
+  }
+  scoped_ptr<AshmemRegion> new_region(
+      AshmemRegion::Create(
+          std::max(static_cast<size_t>(kMinAshmemRegionSize), aligned_size),
+          name_.c_str(), this));
+  if (!new_region) {
+    // TODO(pliard): consider adding an histogram to see how often this happens.
+    return scoped_ptr<DiscardableMemory>();
+  }
+  ashmem_regions_.push_back(new_region.release());
+  return ashmem_regions_.back()->Allocate_Locked(size, aligned_size);
+}
+
+void DiscardableMemoryAllocator::DeleteAshmemRegion_Locked(
+    AshmemRegion* region) {
+  lock_.AssertAcquired();
+  // Note that there should not be more than a couple of ashmem region instances
+  // in |ashmem_regions_|.
+  const ScopedVector<AshmemRegion>::iterator it = std::find(
+      ashmem_regions_.begin(), ashmem_regions_.end(), region);
+  DCHECK_NE(ashmem_regions_.end(), it);
+  std::swap(*it, ashmem_regions_.back());
+  ashmem_regions_.resize(ashmem_regions_.size() - 1);

[willchan no longer on Chromium, 2013/11/28 06:16:37]

why not pop_back() instead?

[Philippe, 2013/11/28 16:42:53]

Yeah good point :) I added ScopedVector::pop_back(). Let me know if you want me
to revert that change.

+}
+
+}  // namespace internal
+}  // namespace base