src/base/memory/discardable_memory_ashmem_allocator.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "base/memory/discardable_memory_ashmem_allocator.h"
   6
   7 #include <sys/mman.h>
   8 #include <unistd.h>
   9
  10 #include <algorithm>
  11 #include <cmath>
  12 #include <limits>
  13 #include <set>
  14 #include <utility>
  15
  16 #include "base/basictypes.h"
  17 #include "base/containers/hash_tables.h"
  18 #include "base/file_util.h"
  19 #include "base/files/scoped_file.h"
  20 #include "base/logging.h"
  21 #include "base/memory/scoped_vector.h"
  22 #include "third_party/ashmem/ashmem.h"
  23
  24 // The allocator consists of three parts (classes):
  25 // - DiscardableMemoryAshmemAllocator: entry point of all allocations (through
  26 // its Allocate() method) that are dispatched to the AshmemRegion instances
  27 // (which it owns).
  28 // - AshmemRegion: manages allocations and destructions inside a single large
  29 // (e.g. 32 MBytes) ashmem region.
  30 // - DiscardableAshmemChunk: class mimicking the DiscardableMemory interface
  31 // whose instances are returned to the client.
  32
  33 namespace base {
  34 namespace {
  35
  36 // Only tolerate fragmentation in used chunks *caused by the client* (as opposed
  37 // to the allocator when a free chunk is reused). The client can cause such
  38 // fragmentation by e.g. requesting 4097 bytes. This size would be rounded up to
  39 // 8192 by the allocator which would cause 4095 bytes of fragmentation (which is
  40 // currently the maximum allowed). If the client requests 4096 bytes and a free
  41 // chunk of 8192 bytes is available then the free chunk gets splitted into two
  42 // pieces to minimize fragmentation (since 8192 - 4096 = 4096 which is greater
  43 // than 4095).
  44 // TODO(pliard): tune this if splitting chunks too often leads to performance
  45 // issues.
  46 const size_t kMaxChunkFragmentationBytes = 4096 - 1;
  47
  48 const size_t kMinAshmemRegionSize = 32 * 1024 * 1024;
  49
  50 // Returns 0 if the provided size is too high to be aligned.
  51 size_t AlignToNextPage(size_t size) {
  52   const size_t kPageSize = 4096;
  53   DCHECK_EQ(static_cast<int>(kPageSize), getpagesize());
  54   if (size > std::numeric_limits<size_t>::max() - kPageSize + 1)
  55     return 0;
  56   const size_t mask = ~(kPageSize - 1);
  57   return (size + kPageSize - 1) & mask;
  58 }
  59
  60 bool CreateAshmemRegion(const char* name,
  61                         size_t size,
  62                         int* out_fd,
  63                         void** out_address) {
  64   base::ScopedFD fd(ashmem_create_region(name, size));
  65   if (!fd.is_valid()) {
  66     DLOG(ERROR) << "ashmem_create_region() failed";
  67     return false;
  68   }
  69
  70   const int err = ashmem_set_prot_region(fd.get(), PROT_READ | PROT_WRITE);
  71   if (err < 0) {
  72     DLOG(ERROR) << "Error " << err << " when setting protection of ashmem";
  73     return false;
  74   }
  75
  76   // There is a problem using MAP_PRIVATE here. As we are constantly calling
  77   // Lock() and Unlock(), data could get lost if they are not written to the
  78   // underlying file when Unlock() gets called.
  79   void* const address = mmap(
  80       NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd.get(), 0);
  81   if (address == MAP_FAILED) {
  82     DPLOG(ERROR) << "Failed to map memory.";
  83     return false;
  84   }
  85
  86   *out_fd = fd.release();
  87   *out_address = address;
  88   return true;
  89 }
  90
  91 bool CloseAshmemRegion(int fd, size_t size, void* address) {
  92   if (munmap(address, size) == -1) {
  93     DPLOG(ERROR) << "Failed to unmap memory.";
  94     close(fd);
  95     return false;
  96   }
  97   return close(fd) == 0;
  98 }
  99
 100 bool LockAshmemRegion(int fd, size_t off, size_t size) {
 101   return ashmem_pin_region(fd, off, size) != ASHMEM_WAS_PURGED;
 102 }
 103
 104 bool UnlockAshmemRegion(int fd, size_t off, size_t size) {
 105   const int failed = ashmem_unpin_region(fd, off, size);
 106   if (failed)
 107     DLOG(ERROR) << "Failed to unpin memory.";
 108   return !failed;
 109 }
 110
 111 }  // namespace
 112
 113 namespace internal {
 114
 115 class AshmemRegion {
 116  public:
 117   // Note that |allocator| must outlive |this|.
 118   static scoped_ptr<AshmemRegion> Create(
 119       size_t size,
 120       const std::string& name,
 121       DiscardableMemoryAshmemAllocator* allocator) {
 122     DCHECK_EQ(size, AlignToNextPage(size));
 123     int fd;
 124     void* base;
 125     if (!CreateAshmemRegion(name.c_str(), size, &fd, &base))
 126       return scoped_ptr<AshmemRegion>();
 127     return make_scoped_ptr(new AshmemRegion(fd, size, base, allocator));
 128   }
 129
 130   ~AshmemRegion() {
 131     const bool result = CloseAshmemRegion(fd_, size_, base_);
 132     DCHECK(result);
 133     DCHECK(!highest_allocated_chunk_);
 134   }
 135
 136   // Returns a new instance of DiscardableAshmemChunk whose size is greater or
 137   // equal than |actual_size| (which is expected to be greater or equal than
 138   // |client_requested_size|).
 139   // Allocation works as follows:
 140   // 1) Reuse a previously freed chunk and return it if it succeeded. See
 141   // ReuseFreeChunk_Locked() below for more information.
 142   // 2) If no free chunk could be reused and the region is not big enough for
 143   // the requested size then NULL is returned.
 144   // 3) If there is enough room in the ashmem region then a new chunk is
 145   // returned. This new chunk starts at |offset_| which is the end of the
 146   // previously highest chunk in the region.
 147   scoped_ptr<DiscardableAshmemChunk> Allocate_Locked(
 148       size_t client_requested_size,
 149       size_t actual_size) {
 150     DCHECK_LE(client_requested_size, actual_size);
 151     allocator_->lock_.AssertAcquired();
 152
 153     // Check that the |highest_allocated_chunk_| field doesn't contain a stale
 154     // pointer. It should point to either a free chunk or a used chunk.
 155     DCHECK(!highest_allocated_chunk_ ||
 156            address_to_free_chunk_map_.find(highest_allocated_chunk_) !=
 157                address_to_free_chunk_map_.end() ||
 158            used_to_previous_chunk_map_.find(highest_allocated_chunk_) !=
 159                used_to_previous_chunk_map_.end());
 160
 161     scoped_ptr<DiscardableAshmemChunk> memory = ReuseFreeChunk_Locked(
 162         client_requested_size, actual_size);
 163     if (memory)
 164       return memory.Pass();
 165
 166     if (size_ - offset_ < actual_size) {
 167       // This region does not have enough space left to hold the requested size.
 168       return scoped_ptr<DiscardableAshmemChunk>();
 169     }
 170
 171     void* const address = static_cast<char*>(base_) + offset_;
 172     memory.reset(
 173         new DiscardableAshmemChunk(this, fd_, address, offset_, actual_size));
 174
 175     used_to_previous_chunk_map_.insert(
 176         std::make_pair(address, highest_allocated_chunk_));
 177     highest_allocated_chunk_ = address;
 178     offset_ += actual_size;
 179     DCHECK_LE(offset_, size_);
 180     return memory.Pass();
 181   }
 182
 183   void OnChunkDeletion(void* chunk, size_t size) {
 184     AutoLock auto_lock(allocator_->lock_);
 185     MergeAndAddFreeChunk_Locked(chunk, size);
 186     // Note that |this| might be deleted beyond this point.
 187   }
 188
 189  private:
 190   struct FreeChunk {
 191     FreeChunk() : previous_chunk(NULL), start(NULL), size(0) {}
 192
 193     explicit FreeChunk(size_t size)
 194         : previous_chunk(NULL),
 195           start(NULL),
 196           size(size) {
 197     }
 198
 199     FreeChunk(void* previous_chunk, void* start, size_t size)
 200         : previous_chunk(previous_chunk),
 201           start(start),
 202           size(size) {
 203       DCHECK_LT(previous_chunk, start);
 204     }
 205
 206     void* const previous_chunk;
 207     void* const start;
 208     const size_t size;
 209
 210     bool is_null() const { return !start; }
 211
 212     bool operator<(const FreeChunk& other) const {
 213       return size < other.size;
 214     }
 215   };
 216
 217   // Note that |allocator| must outlive |this|.
 218   AshmemRegion(int fd,
 219                size_t size,
 220                void* base,
 221                DiscardableMemoryAshmemAllocator* allocator)
 222       : fd_(fd),
 223         size_(size),
 224         base_(base),
 225         allocator_(allocator),
 226         highest_allocated_chunk_(NULL),
 227         offset_(0) {
 228     DCHECK_GE(fd_, 0);
 229     DCHECK_GE(size, kMinAshmemRegionSize);
 230     DCHECK(base);
 231     DCHECK(allocator);
 232   }
 233
 234   // Tries to reuse a previously freed chunk by doing a closest size match.
 235   scoped_ptr<DiscardableAshmemChunk> ReuseFreeChunk_Locked(
 236       size_t client_requested_size,
 237       size_t actual_size) {
 238     allocator_->lock_.AssertAcquired();
 239     const FreeChunk reused_chunk = RemoveFreeChunkFromIterator_Locked(
 240         free_chunks_.lower_bound(FreeChunk(actual_size)));
 241     if (reused_chunk.is_null())
 242       return scoped_ptr<DiscardableAshmemChunk>();
 243
 244     used_to_previous_chunk_map_.insert(
 245         std::make_pair(reused_chunk.start, reused_chunk.previous_chunk));
 246     size_t reused_chunk_size = reused_chunk.size;
 247     // |client_requested_size| is used below rather than |actual_size| to
 248     // reflect the amount of bytes that would not be usable by the client (i.e.
 249     // wasted). Using |actual_size| instead would not allow us to detect
 250     // fragmentation caused by the client if he did misaligned allocations.
 251     DCHECK_GE(reused_chunk.size, client_requested_size);
 252     const size_t fragmentation_bytes =
 253         reused_chunk.size - client_requested_size;
 254
 255     if (fragmentation_bytes > kMaxChunkFragmentationBytes) {
 256       // Split the free chunk being recycled so that its unused tail doesn't get
 257       // reused (i.e. locked) which would prevent it from being evicted under
 258       // memory pressure.
 259       reused_chunk_size = actual_size;
 260       void* const new_chunk_start =
 261           static_cast<char*>(reused_chunk.start) + actual_size;
 262       if (reused_chunk.start == highest_allocated_chunk_) {
 263         // We also need to update the pointer to the highest allocated chunk in
 264         // case we are splitting the highest chunk.
 265         highest_allocated_chunk_ = new_chunk_start;
 266       }
 267       DCHECK_GT(reused_chunk.size, actual_size);
 268       const size_t new_chunk_size = reused_chunk.size - actual_size;
 269       // Note that merging is not needed here since there can't be contiguous
 270       // free chunks at this point.
 271       AddFreeChunk_Locked(
 272           FreeChunk(reused_chunk.start, new_chunk_start, new_chunk_size));
 273     }
 274
 275     const size_t offset =
 276         static_cast<char*>(reused_chunk.start) - static_cast<char*>(base_);
 277     LockAshmemRegion(fd_, offset, reused_chunk_size);
 278     scoped_ptr<DiscardableAshmemChunk> memory(
 279         new DiscardableAshmemChunk(
 280             this, fd_, reused_chunk.start, offset, reused_chunk_size));
 281     return memory.Pass();
 282   }
 283
 284   // Makes the chunk identified with the provided arguments free and possibly
 285   // merges this chunk with the previous and next contiguous ones.
 286   // If the provided chunk is the only one used (and going to be freed) in the
 287   // region then the internal ashmem region is closed so that the underlying
 288   // physical pages are immediately released.
 289   // Note that free chunks are unlocked therefore they can be reclaimed by the
 290   // kernel if needed (under memory pressure) but they are not immediately
 291   // released unfortunately since madvise(MADV_REMOVE) and
 292   // fallocate(FALLOC_FL_PUNCH_HOLE) don't seem to work on ashmem. This might
 293   // change in versions of kernel >=3.5 though. The fact that free chunks are
 294   // not immediately released is the reason why we are trying to minimize
 295   // fragmentation in order not to cause "artificial" memory pressure.
 296   void MergeAndAddFreeChunk_Locked(void* chunk, size_t size) {
 297     allocator_->lock_.AssertAcquired();
 298     size_t new_free_chunk_size = size;
 299     // Merge with the previous chunk.
 300     void* first_free_chunk = chunk;
 301     DCHECK(!used_to_previous_chunk_map_.empty());
 302     const hash_map<void*, void*>::iterator previous_chunk_it =
 303         used_to_previous_chunk_map_.find(chunk);
 304     DCHECK(previous_chunk_it != used_to_previous_chunk_map_.end());
 305     void* previous_chunk = previous_chunk_it->second;
 306     used_to_previous_chunk_map_.erase(previous_chunk_it);
 307
 308     if (previous_chunk) {
 309       const FreeChunk free_chunk = RemoveFreeChunk_Locked(previous_chunk);
 310       if (!free_chunk.is_null()) {
 311         new_free_chunk_size += free_chunk.size;
 312         first_free_chunk = previous_chunk;
 313         if (chunk == highest_allocated_chunk_)
 314           highest_allocated_chunk_ = previous_chunk;
 315
 316         // There should not be more contiguous previous free chunks.
 317         previous_chunk = free_chunk.previous_chunk;
 318         DCHECK(!address_to_free_chunk_map_.count(previous_chunk));
 319       }
 320     }
 321
 322     // Merge with the next chunk if free and present.
 323     void* next_chunk = static_cast<char*>(chunk) + size;
 324     const FreeChunk next_free_chunk = RemoveFreeChunk_Locked(next_chunk);
 325     if (!next_free_chunk.is_null()) {
 326       new_free_chunk_size += next_free_chunk.size;
 327       if (next_free_chunk.start == highest_allocated_chunk_)
 328         highest_allocated_chunk_ = first_free_chunk;
 329
 330       // Same as above.
 331       DCHECK(!address_to_free_chunk_map_.count(static_cast<char*>(next_chunk) +
 332                                                next_free_chunk.size));
 333     }
 334
 335     const bool whole_ashmem_region_is_free =
 336         used_to_previous_chunk_map_.empty();
 337     if (!whole_ashmem_region_is_free) {
 338       AddFreeChunk_Locked(
 339           FreeChunk(previous_chunk, first_free_chunk, new_free_chunk_size));
 340       return;
 341     }
 342
 343     // The whole ashmem region is free thus it can be deleted.
 344     DCHECK_EQ(base_, first_free_chunk);
 345     DCHECK_EQ(base_, highest_allocated_chunk_);
 346     DCHECK(free_chunks_.empty());
 347     DCHECK(address_to_free_chunk_map_.empty());
 348     DCHECK(used_to_previous_chunk_map_.empty());
 349     highest_allocated_chunk_ = NULL;
 350     allocator_->DeleteAshmemRegion_Locked(this);  // Deletes |this|.
 351   }
 352
 353   void AddFreeChunk_Locked(const FreeChunk& free_chunk) {
 354     allocator_->lock_.AssertAcquired();
 355     const std::multiset<FreeChunk>::iterator it = free_chunks_.insert(
 356         free_chunk);
 357     address_to_free_chunk_map_.insert(std::make_pair(free_chunk.start, it));
 358     // Update the next used contiguous chunk, if any, since its previous chunk
 359     // may have changed due to free chunks merging/splitting.
 360     void* const next_used_contiguous_chunk =
 361         static_cast<char*>(free_chunk.start) + free_chunk.size;
 362     hash_map<void*, void*>::iterator previous_it =
 363         used_to_previous_chunk_map_.find(next_used_contiguous_chunk);
 364     if (previous_it != used_to_previous_chunk_map_.end())
 365       previous_it->second = free_chunk.start;
 366   }
 367
 368   // Finds and removes the free chunk, if any, whose start address is
 369   // |chunk_start|. Returns a copy of the unlinked free chunk or a free chunk
 370   // whose content is null if it was not found.
 371   FreeChunk RemoveFreeChunk_Locked(void* chunk_start) {
 372     allocator_->lock_.AssertAcquired();
 373     const hash_map<
 374         void*, std::multiset<FreeChunk>::iterator>::iterator it =
 375             address_to_free_chunk_map_.find(chunk_start);
 376     if (it == address_to_free_chunk_map_.end())
 377       return FreeChunk();
 378     return RemoveFreeChunkFromIterator_Locked(it->second);
 379   }
 380
 381   // Same as above but takes an iterator in.
 382   FreeChunk RemoveFreeChunkFromIterator_Locked(
 383       std::multiset<FreeChunk>::iterator free_chunk_it) {
 384     allocator_->lock_.AssertAcquired();
 385     if (free_chunk_it == free_chunks_.end())
 386       return FreeChunk();
 387     DCHECK(free_chunk_it != free_chunks_.end());
 388     const FreeChunk free_chunk(*free_chunk_it);
 389     address_to_free_chunk_map_.erase(free_chunk_it->start);
 390     free_chunks_.erase(free_chunk_it);
 391     return free_chunk;
 392   }
 393
 394   const int fd_;
 395   const size_t size_;
 396   void* const base_;
 397   DiscardableMemoryAshmemAllocator* const allocator_;
 398   // Points to the chunk with the highest address in the region. This pointer
 399   // needs to be carefully updated when chunks are merged/split.
 400   void* highest_allocated_chunk_;
 401   // Points to the end of |highest_allocated_chunk_|.
 402   size_t offset_;
 403   // Allows free chunks recycling (lookup, insertion and removal) in O(log N).
 404   // Note that FreeChunk values are indexed by their size and also note that
 405   // multiple free chunks can have the same size (which is why multiset<> is
 406   // used instead of e.g. set<>).
 407   std::multiset<FreeChunk> free_chunks_;
 408   // Used while merging free contiguous chunks to erase free chunks (from their
 409   // start address) in constant time. Note that multiset<>::{insert,erase}()
 410   // don't invalidate iterators (except the one for the element being removed
 411   // obviously).
 412   hash_map<
 413       void*, std::multiset<FreeChunk>::iterator> address_to_free_chunk_map_;
 414   // Maps the address of *used* chunks to the address of their previous
 415   // contiguous chunk.
 416   hash_map<void*, void*> used_to_previous_chunk_map_;
 417
 418   DISALLOW_COPY_AND_ASSIGN(AshmemRegion);
 419 };
 420
 421 DiscardableAshmemChunk::~DiscardableAshmemChunk() {
 422   if (locked_)
 423     UnlockAshmemRegion(fd_, offset_, size_);
 424   ashmem_region_->OnChunkDeletion(address_, size_);
 425 }
 426
 427 bool DiscardableAshmemChunk::Lock() {
 428   DCHECK(!locked_);
 429   locked_ = true;
 430   return LockAshmemRegion(fd_, offset_, size_);
 431 }
 432
 433 void DiscardableAshmemChunk::Unlock() {
 434   DCHECK(locked_);
 435   locked_ = false;
 436   UnlockAshmemRegion(fd_, offset_, size_);
 437 }
 438
 439 void* DiscardableAshmemChunk::Memory() const {
 440   return address_;
 441 }
 442
 443 // Note that |ashmem_region| must outlive |this|.
 444 DiscardableAshmemChunk::DiscardableAshmemChunk(AshmemRegion* ashmem_region,
 445                                                int fd,
 446                                                void* address,
 447                                                size_t offset,
 448                                                size_t size)
 449     : ashmem_region_(ashmem_region),
 450       fd_(fd),
 451       address_(address),
 452       offset_(offset),
 453       size_(size),
 454       locked_(true) {
 455 }
 456
 457 DiscardableMemoryAshmemAllocator::DiscardableMemoryAshmemAllocator(
 458     const std::string& name,
 459     size_t ashmem_region_size)
 460     : name_(name),
 461       ashmem_region_size_(
 462           std::max(kMinAshmemRegionSize, AlignToNextPage(ashmem_region_size))),
 463       last_ashmem_region_size_(0) {
 464   DCHECK_GE(ashmem_region_size_, kMinAshmemRegionSize);
 465 }
 466
 467 DiscardableMemoryAshmemAllocator::~DiscardableMemoryAshmemAllocator() {
 468   DCHECK(ashmem_regions_.empty());
 469 }
 470
 471 scoped_ptr<DiscardableAshmemChunk> DiscardableMemoryAshmemAllocator::Allocate(
 472     size_t size) {
 473   const size_t aligned_size = AlignToNextPage(size);
 474   if (!aligned_size)
 475     return scoped_ptr<DiscardableAshmemChunk>();
 476   // TODO(pliard): make this function less naive by e.g. moving the free chunks
 477   // multiset to the allocator itself in order to decrease even more
 478   // fragmentation/speedup allocation. Note that there should not be more than a
 479   // couple (=5) of AshmemRegion instances in practice though.
 480   AutoLock auto_lock(lock_);
 481   DCHECK_LE(ashmem_regions_.size(), 5U);
 482   for (ScopedVector<AshmemRegion>::iterator it = ashmem_regions_.begin();
 483        it != ashmem_regions_.end(); ++it) {
 484     scoped_ptr<DiscardableAshmemChunk> memory(
 485         (*it)->Allocate_Locked(size, aligned_size));
 486     if (memory)
 487       return memory.Pass();
 488   }
 489   // The creation of the (large) ashmem region might fail if the address space
 490   // is too fragmented. In case creation fails the allocator retries by
 491   // repetitively dividing the size by 2.
 492   const size_t min_region_size = std::max(kMinAshmemRegionSize, aligned_size);
 493   for (size_t region_size = std::max(ashmem_region_size_, aligned_size);
 494        region_size >= min_region_size;
 495        region_size = AlignToNextPage(region_size / 2)) {
 496     scoped_ptr<AshmemRegion> new_region(
 497         AshmemRegion::Create(region_size, name_.c_str(), this));
 498     if (!new_region)
 499       continue;
 500     last_ashmem_region_size_ = region_size;
 501     ashmem_regions_.push_back(new_region.release());
 502     return ashmem_regions_.back()->Allocate_Locked(size, aligned_size);
 503   }
 504   // TODO(pliard): consider adding an histogram to see how often this happens.
 505   return scoped_ptr<DiscardableAshmemChunk>();
 506 }
 507
 508 size_t DiscardableMemoryAshmemAllocator::last_ashmem_region_size() const {
 509   AutoLock auto_lock(lock_);
 510   return last_ashmem_region_size_;
 511 }
 512
 513 void DiscardableMemoryAshmemAllocator::DeleteAshmemRegion_Locked(
 514     AshmemRegion* region) {
 515   lock_.AssertAcquired();
 516   // Note that there should not be more than a couple of ashmem region instances
 517   // in |ashmem_regions_|.
 518   DCHECK_LE(ashmem_regions_.size(), 5U);
 519   const ScopedVector<AshmemRegion>::iterator it = std::find(
 520       ashmem_regions_.begin(), ashmem_regions_.end(), region);
 521   DCHECK_NE(ashmem_regions_.end(), it);
 522   std::swap(*it, ashmem_regions_.back());
 523   ashmem_regions_.pop_back();
 524 }
 525
 526 }  // namespace internal
 527 }  // namespace base