discardable_memory_ashmem_allocator.cc revision 5c02ac1a9c1b504631c0a3d2b6e737b5d738bae1
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 33namespace base { 34namespace { 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. 46const size_t kMaxChunkFragmentationBytes = 4096 - 1; 47 48const size_t kMinAshmemRegionSize = 32 * 1024 * 1024; 49 50// Returns 0 if the provided size is too high to be aligned. 51size_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 60bool 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 91bool 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 100bool LockAshmemRegion(int fd, size_t off, size_t size) { 101 return ashmem_pin_region(fd, off, size) != ASHMEM_WAS_PURGED; 102} 103 104bool 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 113namespace internal { 114 115class 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 421DiscardableAshmemChunk::~DiscardableAshmemChunk() { 422 if (locked_) 423 UnlockAshmemRegion(fd_, offset_, size_); 424 ashmem_region_->OnChunkDeletion(address_, size_); 425} 426 427bool DiscardableAshmemChunk::Lock() { 428 DCHECK(!locked_); 429 locked_ = true; 430 return LockAshmemRegion(fd_, offset_, size_); 431} 432 433void DiscardableAshmemChunk::Unlock() { 434 DCHECK(locked_); 435 locked_ = false; 436 UnlockAshmemRegion(fd_, offset_, size_); 437} 438 439void* DiscardableAshmemChunk::Memory() const { 440 return address_; 441} 442 443// Note that |ashmem_region| must outlive |this|. 444DiscardableAshmemChunk::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 457DiscardableMemoryAshmemAllocator::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 467DiscardableMemoryAshmemAllocator::~DiscardableMemoryAshmemAllocator() { 468 DCHECK(ashmem_regions_.empty()); 469} 470 471scoped_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 508size_t DiscardableMemoryAshmemAllocator::last_ashmem_region_size() const { 509 AutoLock auto_lock(lock_); 510 return last_ashmem_region_size_; 511} 512 513void 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 528