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

[willchan no longer on Chromium, 2013/11/27 06:52:07]

Can you add a DCHECK to enforce this invariant?

[Philippe, 2013/11/27 14:22:10]

Done.

+  // Allocation works as follows:
+  // 1) Recycle a previously freed chunk and return it if it succeeded. See
+  // RecycleFreeChunk_Locked() below for more information.
+  // 2) If no free chunk could be recycled 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) {
+    allocator_->lock_.AssertAcquired();
+    scoped_ptr<DiscardableMemory> memory = RecycleFreeChunk_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(
+        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) {
+  }
+
+  // Tries to reuse a previously freed chunk by doing a closest size match.
+  scoped_ptr<DiscardableMemory> RecycleFreeChunk_Locked(

[willchan no longer on Chromium, 2013/11/27 06:52:07]

Nit: WDYT about s/Recycle/Reuse/? My mental model for recycling is the act of
throwing something away in a recycling bin so it can be reused in the future,
whereas here we're actually reusing it in the present.

[Philippe, 2013/11/27 14:22:10]

Done. Egor wasn't very comfortable either with the term recycle so I guess I
misused it :)

+      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 recycled_chunk_size = chunk_it->size;
+    const size_t fragmentation_bytes = chunk_it->size - client_requested_size;
+    if (fragmentation_bytes >= kMaxChunkFragmentationBytes) {
+      SplitFreeChunk_Locked(*chunk_it, actual_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->start, offset,
+                                   recycled_chunk_size));
+    previous_chunk_for_used_chunk_.insert(
+        std::make_pair(chunk_it->start, chunk_it->previous_chunk));

[willchan no longer on Chromium, 2013/11/27 06:52:07]

I'm trying to understand this. It looks like the previous chunk information is
duplicated. It's stored as a const in FreeChunk, and in the
previous_chunk_for_used_chunk_ map. It looks to me like various operations can
modify previous_chunk_for_used_chunk_, such as SplitFreeChunk_Locked(). Doesn't
that mean it's wrong to use chunk_it->previous_chunk here?

Hm...let me see if I can concoct an example and ask you to write a test for it
so we can validate it works.
1) Allocate 16KB chunk (triggers an ashmem region of 32KB,
FreeChunk::previous_chunk is NULL)
2) Allocate 16KB chunk (uses the rest of the ashmem region of 32KB,
FreeChunk::previous_chunk points to chunk in (1))
3) Free the first chunk from (1).
4) Allocate a 8KB chunk. This splits the free chunk into two. Now we have 8KB
(used), 8KB (free), 16KB (used) [its FreeChunk::previous_chunk points to the
front of the split chunk].
5) Allocate a 8KB chunk. Now we have 8KB (used), 8KB (used), 16KB (used)[but its
FreeChunk::previous_chunk member now points to the wrong chunk]

I guess to trigger a problem, you'd have to reuse the 16KB chunk to set the
dangling FreeChunk::previous_chunk member into |previous_chunk_for_used_chunk_|.

Ultimately, I think that we shouldn't duplicate the previous_chunk information
in two places, and it should not be const, since it can obviously change over
the lifetime of a chunk.

[Philippe, 2013/11/27 14:22:10]

I added your unit test (please make sure that it fully reflects what you wrote
since I might have misunderstood) and it seems to pass this time :) The thing
you might have missed is the fact that the previous chunk information is not
duplicated strictly speaking. |previous_chunk_for_used_chunk_| only covers the
chunks being *used* so the previous chunk information is rather moved from
|previous_chunk_for_used_chunk_| to |FreeChunk::previous_chunk| when a chunk
gets deleted by the client (and also moved back from |FreeChunk::previous_chunk|
to |previous_chunk_for_used_chunk_| when a chunk gets recycled).
I might be the one being jetlagged though :) I uploaded a separate patch set
(#36) that tries to remove |FreeChunk::previous_chunk| but unfortunately fails
currently since a DCHECK is failing. I find it more complicated without
|FreeChunk::previous_chunk| to be honest. Let me know which version you
prefer/looks simpler to you. If patch set 36 looks better to you then I will
make it pass the unit tests but as you may have understood I have a slight
preference for patch set 38 (which is a revert of patch set 36 + addresses the
rest of your comments).

What do you think?

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

I think I was too jetlagged last night and wrong :) Thanks for the explanation
and test.

+    free_chunk_for_address_.erase(chunk_it->start);
+    free_chunks_.erase(chunk_it);
+    return memory.Pass();
+  }
+
+  // Splits the free chunk being recycled so that its unused tail doesn't get
+  // recycled (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;
+    // 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) {
+      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) {
+      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);
+    DCHECK(free_chunks_.empty() && free_chunk_for_address_.empty());
+    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_;
+  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());
+}
+
+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.
+  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);
+}
+
+}  // namespace internal
+}  // namespace base