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