Add DiscardableMemoryAllocator to work around FD limit issue.

base/memory/discardable_memory_allocator_android.cc

Index: base/memory/discardable_memory_allocator_android.cc
diff --git a/base/memory/discardable_memory_allocator_android.cc b/base/memory/discardable_memory_allocator_android.cc
new file mode 100644
index 0000000000000000000000000000000000000000..33226cd045683eab2df1bdf1ee4e4b215248e68d
--- /dev/null
+++ b/base/memory/discardable_memory_allocator_android.cc
@@ -0,0 +1,368 @@
+// 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/bind.h"
+#include "base/callback.h"
+#include "base/compiler_specific.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;
+
+class DiscardableAshmemChunk : public DiscardableMemory {
+ public:
+  // Note that this is not replaced with base::Callback to save the extra heap

[willchan no longer on Chromium, 2013/11/18 14:53:13]

My initial inclination is to call this premature optimization. Do you expect
this code path to be hot enough that this would actually matter? Or do you think
this is a death by a thousand cuts thing and we should prefer this pattern in
general?

[Philippe, 2013/11/18 16:34:51]

I would also call that premature optimization if this code was in an upper layer
and not in a "memory allocator". We are already seeing performance issues on
Android because we do way too many heap allocations in general and dlmalloc
doesn't scale in multi-threaded environments (see
http://code.google.com/p/chromium/issues/detail?id=309658 and
http://code.google.com/p/chromium/issues/detail?id=303282 for instance). I would
like ideally to make discardable memory a first class citizen in Blink/make it
appealing in general. If one discardable memory allocation implies e.g. 5 heap
allocations + some atomicops then it's harder to sell :) I agree that such
choices should be preceded with profiling though (which I intend to do once we
submitted this "baseline"). I took the liberty here of very slightly (IMO)
optimizing prematurely since the "optimized" version (i.e. using the observer)
is not overly complicated (IMO) compared to the "non-optimized" one (using a
Callback). In fact people already mistakenly use single-method delegates
sometimes in place of callbacks in upper layers where performance doesn't
necessarily matter so I thought this would be reasonable here in base/.

What do you think?

Completely off-topic, but since we are talking about premature optimization, I
came across this nice read about mature optimization this weekend. I strongly
recommend it if you haven't seen it before: 
http://carlos.bueno.org/optimization/mature-optimization.pdf

[willchan no longer on Chromium, 2013/11/19 02:19:43]

Since this isn't in a public header, I don't mind so much. I defer to you. I
guess I don't really think of DiscardableMemory as being cheap anyway, so an
extra heap alloc doesn't bother me. It usually (except under memory pressure,
when it switches to the allocator) has to do a context switch to acquire an
ashmem region anyway. This is why I asked if you expect the code path to be hot.
If this were hot, I'd think it'd be nicer to use the DiscardableMemoryAllocator
more so as to avoid the kernel context switch.

That said, as I look at it again, why don't you just make this a sibling class
of AshmemRegion, so it'll also be nested within DiscardableMemoryAllocator. And
then pass in a AshmemRegion*, rather than use the extra interface class. Do you
think the interface layering buys very much? I think it'll make it more readable
(and save the virtual indirection) by avoiding requiring the reader to chase
down the indirection.
TL;DR yet, but maybe later. Looks interesting though.

+  // allocation.
+  struct DeletionObserver {

[willchan no longer on Chromium, 2013/11/18 14:53:13]

class?

[Philippe, 2013/11/18 16:34:51]

Done.

+    virtual void OnChunkDeletion(void* previous_chunk,
+                                 void* chunk,
+                                 size_t size) = 0;
+
+   protected:
+    virtual ~DeletionObserver() {}
+  };
+
+  DiscardableAshmemChunk(DeletionObserver* deletion_observer,

[willchan no longer on Chromium, 2013/11/18 14:53:13]

The lifetime of the deletion_observer needs to be documented. I assume it must
always outlive the DiscardableAshmemChunk.

[Philippe, 2013/11/18 16:34:51]

Yeah, done.

+                         int fd,
+                         void* previous_chunk,
+                         void* address,
+                         size_t offset,
+                         size_t size)
+      : deletion_observer_(deletion_observer),
+        fd_(fd),
+        previous_chunk_(previous_chunk),
+        address_(address),
+        offset_(offset),
+        size_(size),
+        locked_(true) {
+  }
+
+  virtual ~DiscardableAshmemChunk() {
+    if (locked_)
+      internal::UnlockAshmemRegion(fd_, offset_, size_, address_);
+    deletion_observer_->OnChunkDeletion(previous_chunk_, address_, size_);
+  }
+
+  // DiscardableMemory:
+  virtual size_t Size() const OVERRIDE {
+    return size_;
+  }
+
+  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:
+  DeletionObserver* const deletion_observer_;
+  const int fd_;
+  void* const previous_chunk_;
+  void* const address_;
+  const size_t offset_;
+  const size_t size_;
+  bool locked_;
+
+  DISALLOW_COPY_AND_ASSIGN(DiscardableAshmemChunk);
+};
+
+}  // namespace
+
+namespace internal {
+
+class DiscardableMemoryAllocator::AshmemRegion
+    : public DiscardableAshmemChunk::DeletionObserver {
+ public:
+  typedef Callback<void (scoped_ptr<AshmemRegion>)> DeletionCallback;
+
+  static scoped_ptr<AshmemRegion> Create(
+      size_t size,
+      const std::string& name,
+      Lock* lock,
+      const DeletionCallback& deletion_callback) {
+    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, lock, deletion_callback));
+  }
+
+  virtual ~AshmemRegion() {
+    const bool result = internal::CloseAshmemRegion(fd_, size_, base_);
+    DCHECK(result);
+  }
+
+  scoped_ptr<DiscardableMemory> Allocate(size_t client_requested_size,
+                                         size_t actual_size) {
+    lock_->AssertAcquired();
+    scoped_ptr<DiscardableMemory> memory = RecycleFreeChunk(
+        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_, last_allocated_chunk_, address,
+                                   offset_, actual_size));
+    last_allocated_chunk_ = address;
+    offset_ += actual_size;
+    return memory.Pass();
+  }
+
+ 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,
+               Lock* lock,
+               const DeletionCallback& deletion_callback)
+      : fd_(fd),
+        size_(size),
+        base_(base),
+        offset_(0),
+        lock_(lock),
+        deletion_callback_(deletion_callback),
+        last_allocated_chunk_(NULL) {
+  }
+
+  // DiscardableAshmemChunk::DeletionObserver:
+  virtual void OnChunkDeletion(void* previous_chunk,
+                               void* chunk,
+                               size_t size) OVERRIDE {
+    base::AutoLock auto_lock(*lock_);
+    MergeAndAddFreeChunk(previous_chunk, chunk, size);
+  }
+
+  // Tries to reuse a previously freed chunk by doing a closest size match.
+  scoped_ptr<DiscardableMemory> RecycleFreeChunk(size_t client_requested_size,
+                                                 size_t actual_size) {
+    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 recycled_chunk_size = chunk_it->size;
+    const size_t fragmentation_bytes = chunk_it->size - client_requested_size;
+    if (fragmentation_bytes >= kMaxChunkFragmentationBytes) {
+      // Split the free chunk being recycled if it's too large so that its
+      // unused tail doesn't get recycled (i.e. locked) which would prevent it
+      // from being evicted under memory pressure.
+      void* const previous_chunk = chunk_it->start;
+      void* const chunk_start =
+          static_cast<char*>(chunk_it->start) + actual_size;
+      const size_t chunk_size = chunk_it->size - actual_size;
+      // Note that merging is not needed here since there can't be contiguous
+      // free chunks at this point.
+      AddFreeChunk(FreeChunk(previous_chunk, chunk_start, chunk_size));
+      recycled_chunk_size = actual_size;
+    }
+    const size_t offset =
+        static_cast<char*>(chunk_it->start) - static_cast<char*>(base_);
+    internal::LockAshmemRegion(
+        fd_, offset, recycled_chunk_size, chunk_it->start);
+    scoped_ptr<DiscardableMemory> memory(
+        new DiscardableAshmemChunk(
+            this, fd_, chunk_it->previous_chunk, chunk_it->start, offset,
+            recycled_chunk_size));
+    free_chunk_for_address_.erase(reinterpret_cast<uintptr_t>(chunk_it->start));
+    free_chunks_.erase(chunk_it);
+    return memory.Pass();
+  }
+
+  // Makes the chunk identified with the provided arguments free and possibly
+  // merges this chunk with the previous and next contiguous ones according to
+  // the value of |chunk_merging_flags|.
+  // 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.
+  void MergeAndAddFreeChunk(void* previous_chunk, void* chunk, size_t size) {
+    lock_->AssertAcquired();
+    size_t new_free_chunk_size = size;
+    // Merge with the previous chunks.
+    void* first_free_chunk = chunk;
+    while (previous_chunk) {
+      const FreeChunk free_chunk = RemoveFreeChunk(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.
+    const void* next_chunk = static_cast<const char*>(chunk) + size;
+    while (true) {
+      const FreeChunk free_chunk = RemoveFreeChunk(next_chunk);
+      if (free_chunk.is_null())
+        break;
+      new_free_chunk_size += free_chunk.size;
+      next_chunk = static_cast<const 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(
+          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);
+    DCHECK(free_chunks_.empty() && free_chunk_for_address_.empty());
+    deletion_callback_.Run(make_scoped_ptr(this));  // Deletes |this|.
+  }
+
+  void AddFreeChunk(const FreeChunk& free_chunk) {
+    const std::multiset<FreeChunk>::iterator it = free_chunks_.insert(
+        free_chunk);
+    free_chunk_for_address_.insert(
+        std::make_pair(reinterpret_cast<uintptr_t>(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(const void* chunk_start) {
+    lock_->AssertAcquired();
+    const base::hash_map<
+        uintptr_t, std::multiset<FreeChunk>::iterator>::iterator it =
+            free_chunk_for_address_.find(
+                reinterpret_cast<uintptr_t>(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_;
+  base::Lock* const lock_;
+  const DeletionCallback deletion_callback_;
+  void* last_allocated_chunk_;
+  std::multiset<FreeChunk> free_chunks_;
+  base::hash_map<
+      uintptr_t, std::multiset<FreeChunk>::iterator> free_chunk_for_address_;
+
+  DISALLOW_COPY_AND_ASSIGN(AshmemRegion);
+};
+
+DiscardableMemoryAllocator::DiscardableMemoryAllocator(const std::string& name)
+    : name_(name) {
+}
+
+DiscardableMemoryAllocator::~DiscardableMemoryAllocator() {
+  DCHECK(thread_checker_.CalledOnValidThread());
+}
+
+scoped_ptr<DiscardableMemory> DiscardableMemoryAllocator::Allocate(
+    size_t size) {
+  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(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(),
+          &lock_,
+          base::Bind(&DiscardableMemoryAllocator::DeleteAshmemRegion,
+                     base::Unretained(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(size, aligned_size);
+}
+
+void DiscardableMemoryAllocator::DeleteAshmemRegion(
+    scoped_ptr<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.get());
+  DCHECK_NE(ashmem_regions_.end(), it);
+  std::swap(*it, ashmem_regions_.back());
+  ashmem_regions_.resize(ashmem_regions_.size() - 1);
+  // |region| was deleted by the resize() above.
+  ignore_result(region.release());
+}
+
+}  // namespace internal
+}  // namespace base