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/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
+  // allocation.
+  struct DeletionObserver {
+    virtual void OnChunkDeletion(int fd,
+                                 void* previous_chunk,
+                                 void* chunk,
+                                 size_t size) = 0;
+
+   protected:
+    virtual ~DeletionObserver() {}
+  };
+
+  DiscardableAshmemChunk(DeletionObserver* deletion_observer,
+                         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(fd_, 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(int fd,
+                               void* previous_chunk,
+                               void* chunk,
+                               size_t size) OVERRIDE {
+    base::AutoLock auto_lock(*lock_);
+    MergeAndAddFreeChunk(fd, 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(int fd,

[pasko, 2013/10/28 17:44:45]

FYI: parameter |fd| is not used.

[Philippe, 2013/10/28 17:50:22]

Wow, thanks! It was used at some point I believe but not anymore.

+                            void* previous_chunk,
+                            void* chunk,
+                            size_t size) {
+    lock_->AssertAcquired();
+    size_t new_free_chunk_size = size;
+    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;
+    }
+    const void* next_chunk = static_cast<const char*>(chunk) + size;
+    while (true) {

[pasko, 2013/10/28 18:10:33]

Really a nit:

I generally prefer this style of loops: with a minimum number of break
statements:
== begin code fragment ==
next_chunk = chunk;
free_chunk_size = size;
do {
  next_chunk = next_chunk + free_chunk_size;
  const FreeChunk free_chunk = RemoveFreeChunk(next_chunk);
  free_chunk_size = free_chunk.size;
while (!free_chunk.is_null());
== end code fragment ==

Also minimizes the number of lines in the loop. Do you like it?

I would also add some comments like:
// Merge with the previous chunks.

// Merge with the next chunks.

There was no need for that before, there was a self-descriptive constant, but
now it would look nicer.

[Philippe, 2013/10/29 10:11:25]

Thanks for the snippet Egor :) The while loop looks more like some code that
could have been written by a kid :) but I find it slightly more readable. In
particular I would be concerned with the asymmetry of the while loop for
previous chunks and the do while loop for the next chunks. Making the previous
chunks merging use a do while loop would require a small non-super readable hack
I believe (I'm open to suggestions though :)) or an extra variable which is fine
from the performance perspective but again makes readability slightly less
easier IMO (I like to involve as less mutable state as possible and also limit
the scope/lifetime of the variables as much as possible).

What do you think?

[pasko, 2013/10/29 10:47:57]

Hm, I did not think of asymmetry being a concern. But well, that's just a nit,
consistency sometimes probably maybe in some sense is good to maintain.

Thanks for adding comments BTW, I generally like to prepend such block-level
comments with an empty line, but at the same time I'm trying to resist being too
picky here, so up to you.

[Philippe, 2013/10/29 10:54:35]

As you may have noticed I'm not super generous in terms of adding blank lines :)
I used to add a lot of blank lines before joining Google but I got used to the
very packed style in Google3 (in my previous team at least). That's kind of an
extreme point of view but IMO blank lines create inconsistencies since everyone
has its own preferences regarding their position/amount. I find generally
comments enough to distinguish blocks in an editor with syntax highlighting. If
a function gets particularly long/unreadable I prefer to split it (when it can).
Just my 2 cents though :)

+      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 unlinks 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