Update AshmemRegion::highest_allocated_chunk_ when merging free chunks.

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>
@@ skipping 109 matching lines @@
     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));
   }
 
   ~AshmemRegion() {
     const bool result = internal::CloseAshmemRegion(fd_, size_, base_);
     DCHECK(result);
+    DCHECK(!highest_allocated_chunk_);
   }
 
   // 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();
+
+    // Check that the |highest_allocated_chunk_| field doesn't contain a stale
+    // pointer. It should point to either a free chunk or a used chunk.
+    DCHECK(!highest_allocated_chunk_ ||
+           address_to_free_chunk_map_.find(highest_allocated_chunk_) !=
+               address_to_free_chunk_map_.end() ||
+           used_to_previous_chunk_map_.find(highest_allocated_chunk_) !=
+               used_to_previous_chunk_map_.end());
+
     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));
+
     used_to_previous_chunk_map_.insert(
         std::make_pair(address, highest_allocated_chunk_));
     highest_allocated_chunk_ = address;
     offset_ += actual_size;
     DCHECK_LE(offset_, size_);
     return memory.Pass();
   }
 
   void OnChunkDeletion(void* chunk, size_t size) {
     AutoLock auto_lock(allocator_->lock_);
     MergeAndAddFreeChunk_Locked(chunk, size);
     // Note that |this| might be deleted beyond this point.
   }
 
  private:
   struct FreeChunk {
     FreeChunk() : previous_chunk(NULL), start(NULL), size(0) {}
 
     explicit FreeChunk(size_t size)
         : previous_chunk(NULL),
           start(NULL),
           size(size) {
     }
 
     FreeChunk(void* previous_chunk, void* start, size_t size)
         : previous_chunk(previous_chunk),
           start(start),
           size(size) {
-      DCHECK_NE(previous_chunk, start);
+      DCHECK_LT(previous_chunk, start);
     }
 
     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;
@@ skipping 84 matching lines @@
     allocator_->lock_.AssertAcquired();
     size_t new_free_chunk_size = size;
     // Merge with the previous chunk.
     void* first_free_chunk = chunk;
     DCHECK(!used_to_previous_chunk_map_.empty());
     const hash_map<void*, void*>::iterator previous_chunk_it =
         used_to_previous_chunk_map_.find(chunk);
     DCHECK(previous_chunk_it != used_to_previous_chunk_map_.end());
     void* previous_chunk = previous_chunk_it->second;
     used_to_previous_chunk_map_.erase(previous_chunk_it);
+
     if (previous_chunk) {
       const FreeChunk free_chunk = RemoveFreeChunk_Locked(previous_chunk);
       if (!free_chunk.is_null()) {
         new_free_chunk_size += free_chunk.size;
         first_free_chunk = previous_chunk;
+        if (chunk == highest_allocated_chunk_)
+          highest_allocated_chunk_ = previous_chunk;
+
         // There should not be more contiguous previous free chunks.
         previous_chunk = free_chunk.previous_chunk;
         DCHECK(!address_to_free_chunk_map_.count(previous_chunk));
       }
     }
+
     // Merge with the next chunk if free and present.
     void* next_chunk = static_cast<char*>(chunk) + size;
     const FreeChunk next_free_chunk = RemoveFreeChunk_Locked(next_chunk);
     if (!next_free_chunk.is_null()) {
       new_free_chunk_size += next_free_chunk.size;
+      if (next_free_chunk.start == highest_allocated_chunk_)
+        highest_allocated_chunk_ = first_free_chunk;
+
       // Same as above.
       DCHECK(!address_to_free_chunk_map_.count(static_cast<char*>(next_chunk) +
                                                next_free_chunk.size));
     }
+
     const bool whole_ashmem_region_is_free =
         used_to_previous_chunk_map_.empty();
     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(base_, first_free_chunk);
+    DCHECK_EQ(base_, highest_allocated_chunk_);
     DCHECK(free_chunks_.empty());
     DCHECK(address_to_free_chunk_map_.empty());
     DCHECK(used_to_previous_chunk_map_.empty());
+    highest_allocated_chunk_ = NULL;
     allocator_->DeleteAshmemRegion_Locked(this);  // Deletes |this|.
   }
 
   void AddFreeChunk_Locked(const FreeChunk& free_chunk) {
     allocator_->lock_.AssertAcquired();
     const std::multiset<FreeChunk>::iterator it = free_chunks_.insert(
         free_chunk);
     address_to_free_chunk_map_.insert(std::make_pair(free_chunk.start, it));
     // Update the next used contiguous chunk, if any, since its previous chunk
     // may have changed due to free chunks merging/splitting.
@@ skipping 28 matching lines @@
     const FreeChunk free_chunk(*free_chunk_it);
     address_to_free_chunk_map_.erase(free_chunk_it->start);
     free_chunks_.erase(free_chunk_it);
     return free_chunk;
   }
 
   const int fd_;
   const size_t size_;
   void* const base_;
   DiscardableMemoryAllocator* const allocator_;
+  // Points to the chunk with the highest address in the region. This pointer
+  // needs to be carefully updated when chunks are merged/split.
   void* highest_allocated_chunk_;
   // Points to the end of |highest_allocated_chunk_|.
   size_t offset_;
   // 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}()
@@ skipping 79 matching lines @@
   DCHECK_LE(ashmem_regions_.size(), 5U);
   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_.pop_back();
 }
 
 }  // namespace internal
 }  // namespace base