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 avoid the extra heap
+  // allocation and atomicops.
+  class DeletionObserver {
+   public:
+    virtual void OnChunkDeletion(void* previous_chunk,
+                                 void* chunk,
+                                 size_t size) = 0;
+
+   protected:
+    virtual ~DeletionObserver() {}
+  };
+
+  // Note that |deletion_observer| must outlive |this|.
+  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(previous_chunk_, address_, size_);
+  }
+
+  // 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:
+  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,

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

DiscardableMemoryAllocator::AshmemRegion is a nested class, so it has access to
DiscardableMemoryAllocator (the enclosing class)'s private members. Why don't
you just pass DiscardableMemoryAllocator*, rather than a private member pointer
and a callback. This also saves the extra heap allocations. And it makes things
a bit clearer in terms of ownership, since |lock|'s lifetime is not clear.
DiscardableMemoryAllocator and AshmemRegion are already pretty tightly coupled
after all, so the weak layering boundaries don't buy that much, and it's all
internal to this .cc file anyway. I think giving up and accepting the tight
coupling will improve readability since the reader doesn't have to chase down
the indirection to find out what the concrete references are.

[Philippe, 2013/11/19 15:43:00]

Agreed, although I'm still doing the heap allocation (that happens very rarely
since we are not expecting more than a couple of AshmemRegion instances) since
the regions (pushed to a vector) are not copyable.

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

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

Can you document this function?

[Philippe, 2013/11/19 15:43:00]

Yes, sorry.

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

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

Is this the highest allocated chunk? What do you mean by "last"? It's unclear if
"last" includes a just recycled chunk. It looks like it does not, since you
don't update this variable when you can RecycleFreeChunk().

[Philippe, 2013/11/19 15:43:00]

Good point. Renamed to |highest_allocated_chunk_|.

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

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

chunk_merging_flags?

[Philippe, 2013/11/19 15:43:00]

This was stale. I removed it.

+  // 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.

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

This comment section wasn't completely clear. Just doublechecking, are you
saying that free chunks are unlocked and thus may be purged by the kernel under
memory pressure, but without memory pressure, it won't immediately get released?
If there's no memory pressure, then what's the problem? And what does minimizing
fragmentation do? Increase the likelihood that we'll be able to free an entire
region?

[Philippe, 2013/11/19 15:43:00]

Yeah, this is correct. We are trying to minimize fragmentation to avoid causing
memory pressure ourselves. The free chunks are unpinned but they can still cause
memory pressure if we are keeping too many of them (which would happen without
merging them). We still want to avoid causing "artificial" memory pressure even
if the ashmem subranges are evictable since the ashmem shrinker would
unnecessarily evict some ashmem subranges (that might belong to other processes)
that could be precious. More space for free chunks also means less space for
page cache (which would be one of the first candidates for eviction I believe).
More importantly the Android framework is quite disconnected from the kernel
unfortunately and has its own low-memory notification system (that is not really
"ashmem aware"). If we start causing "artificial" memory pressure Android would
start sending those notifications to background apps (and ourselves). This would
trigger a lot of activity on the system (and could even increase memory usage).

Does that make any sense? I clarified a bit the last sentence.

+  void MergeAndAddFreeChunk(void* previous_chunk, void* chunk, size_t size) {

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

I defer to you, but I kinda like adding a suffix to indicate this is locked.
Makes it more obvious when reading code. MergeAndFreeChunk_Locked() for example.

[Philippe, 2013/11/19 15:43:00]

Yeah, good idea. I used the assert at the beginning of the function's body to
document that but it was not visible at the call side. I also like suffixing
functions with e.g. "OnUIThread" when it makes sense.

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

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

I dislike this, because in my mind, this is saying that |this| owns itself,
which makes little sense. The allocator owns the AshmemRegion. This is simply
releasing the region back to the allocator (which will probably delete it).

[Philippe, 2013/11/19 15:43:00]

Yes. It was a form of indirect self-deletion IMO which is why I did this but I'm
fine with a raw pointer too.

+  }
+
+  void AddFreeChunk(const FreeChunk& free_chunk) {

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

This should be locked already, right? AssertAcquired()?

[Philippe, 2013/11/19 15:43:00]

Yes, the assert was missing.

+    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_;

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

FYI, I'm spending a lot of time evaluating your data structure choices in doing
this review right now. What would help me and future readers/reviewers is
explaining what operations you expect, and how your choice in data structures
facilitates those operations. There's no documentation anywhere explaining how
the actual recycling/allocation works.

[Philippe, 2013/11/19 15:43:00]

Yeah, sorry. I added a comment here and below.

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

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

This allocation scheme sure is naive :) That's fine, although I'd definitely
leave a TODO that it's worth looking into. Not saying you have to do the TODO,
but it's nice to note it.

[Philippe, 2013/11/19 15:43:00]

Yeah :) I added a TODO. I favored simplicity here since I don't expect us to
have more than 2/3 AshmemRegion instances. But I will definitely look into that
later.

+    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