1 /* 2 * Copyright (C) 2014 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef ART_RUNTIME_MONITOR_POOL_H_ 18 #define ART_RUNTIME_MONITOR_POOL_H_ 19 20 #include "monitor.h" 21 22 #include "base/allocator.h" 23 #ifdef __LP64__ 24 #include <stdint.h> 25 #include "base/atomic.h" 26 #include "runtime.h" 27 #else 28 #include "base/stl_util.h" // STLDeleteElements 29 #endif 30 31 namespace art { 32 33 // Abstraction to keep monitors small enough to fit in a lock word (32bits). On 32bit systems the 34 // monitor id loses the alignment bits of the Monitor*. 35 class MonitorPool { 36 public: Create()37 static MonitorPool* Create() { 38 #ifndef __LP64__ 39 return nullptr; 40 #else 41 return new MonitorPool(); 42 #endif 43 } 44 CreateMonitor(Thread * self,Thread * owner,ObjPtr<mirror::Object> obj,int32_t hash_code)45 static Monitor* CreateMonitor(Thread* self, 46 Thread* owner, 47 ObjPtr<mirror::Object> obj, 48 int32_t hash_code) 49 REQUIRES_SHARED(Locks::mutator_lock_) { 50 #ifndef __LP64__ 51 Monitor* mon = new Monitor(self, owner, obj, hash_code); 52 DCHECK_ALIGNED(mon, LockWord::kMonitorIdAlignment); 53 return mon; 54 #else 55 return GetMonitorPool()->CreateMonitorInPool(self, owner, obj, hash_code); 56 #endif 57 } 58 ReleaseMonitor(Thread * self,Monitor * monitor)59 static void ReleaseMonitor(Thread* self, Monitor* monitor) { 60 #ifndef __LP64__ 61 UNUSED(self); 62 delete monitor; 63 #else 64 GetMonitorPool()->ReleaseMonitorToPool(self, monitor); 65 #endif 66 } 67 ReleaseMonitors(Thread * self,MonitorList::Monitors * monitors)68 static void ReleaseMonitors(Thread* self, MonitorList::Monitors* monitors) { 69 #ifndef __LP64__ 70 UNUSED(self); 71 STLDeleteElements(monitors); 72 #else 73 GetMonitorPool()->ReleaseMonitorsToPool(self, monitors); 74 #endif 75 } 76 MonitorFromMonitorId(MonitorId mon_id)77 static Monitor* MonitorFromMonitorId(MonitorId mon_id) { 78 #ifndef __LP64__ 79 return reinterpret_cast<Monitor*>(mon_id << LockWord::kMonitorIdAlignmentShift); 80 #else 81 return GetMonitorPool()->LookupMonitor(mon_id); 82 #endif 83 } 84 MonitorIdFromMonitor(Monitor * mon)85 static MonitorId MonitorIdFromMonitor(Monitor* mon) { 86 #ifndef __LP64__ 87 return reinterpret_cast<MonitorId>(mon) >> LockWord::kMonitorIdAlignmentShift; 88 #else 89 return mon->GetMonitorId(); 90 #endif 91 } 92 ComputeMonitorId(Monitor * mon,Thread * self)93 static MonitorId ComputeMonitorId(Monitor* mon, Thread* self) { 94 #ifndef __LP64__ 95 UNUSED(self); 96 return MonitorIdFromMonitor(mon); 97 #else 98 return GetMonitorPool()->ComputeMonitorIdInPool(mon, self); 99 #endif 100 } 101 GetMonitorPool()102 static MonitorPool* GetMonitorPool() { 103 #ifndef __LP64__ 104 return nullptr; 105 #else 106 return Runtime::Current()->GetMonitorPool(); 107 #endif 108 } 109 ~MonitorPool()110 ~MonitorPool() { 111 #ifdef __LP64__ 112 FreeInternal(); 113 #endif 114 } 115 116 private: 117 #ifdef __LP64__ 118 // When we create a monitor pool, threads have not been initialized, yet, so ignore thread-safety 119 // analysis. 120 MonitorPool() NO_THREAD_SAFETY_ANALYSIS; 121 122 void AllocateChunk() REQUIRES(Locks::allocated_monitor_ids_lock_); 123 124 // Release all chunks and metadata. This is done on shutdown, where threads have been destroyed, 125 // so ignore thead-safety analysis. 126 void FreeInternal() NO_THREAD_SAFETY_ANALYSIS; 127 128 Monitor* CreateMonitorInPool(Thread* self, 129 Thread* owner, 130 ObjPtr<mirror::Object> obj, 131 int32_t hash_code) 132 REQUIRES_SHARED(Locks::mutator_lock_); 133 134 void ReleaseMonitorToPool(Thread* self, Monitor* monitor); 135 void ReleaseMonitorsToPool(Thread* self, MonitorList::Monitors* monitors); 136 137 // Note: This is safe as we do not ever move chunks. All needed entries in the monitor_chunks_ 138 // data structure are read-only once we get here. Updates happen-before this call because 139 // the lock word was stored with release semantics and we read it with acquire semantics to 140 // retrieve the id. LookupMonitor(MonitorId mon_id)141 Monitor* LookupMonitor(MonitorId mon_id) { 142 size_t offset = MonitorIdToOffset(mon_id); 143 size_t index = offset / kChunkSize; 144 size_t top_index = index / kMaxListSize; 145 size_t list_index = index % kMaxListSize; 146 size_t offset_in_chunk = offset % kChunkSize; 147 uintptr_t base = monitor_chunks_[top_index][list_index]; 148 return reinterpret_cast<Monitor*>(base + offset_in_chunk); 149 } 150 IsInChunk(uintptr_t base_addr,Monitor * mon)151 static bool IsInChunk(uintptr_t base_addr, Monitor* mon) { 152 uintptr_t mon_ptr = reinterpret_cast<uintptr_t>(mon); 153 return base_addr <= mon_ptr && (mon_ptr - base_addr < kChunkSize); 154 } 155 ComputeMonitorIdInPool(Monitor * mon,Thread * self)156 MonitorId ComputeMonitorIdInPool(Monitor* mon, Thread* self) { 157 MutexLock mu(self, *Locks::allocated_monitor_ids_lock_); 158 for (size_t i = 0; i <= current_chunk_list_index_; ++i) { 159 for (size_t j = 0; j < ChunkListCapacity(i); ++j) { 160 if (j >= num_chunks_ && i == current_chunk_list_index_) { 161 break; 162 } 163 uintptr_t chunk_addr = monitor_chunks_[i][j]; 164 if (IsInChunk(chunk_addr, mon)) { 165 return OffsetToMonitorId( 166 reinterpret_cast<uintptr_t>(mon) - chunk_addr 167 + i * (kMaxListSize * kChunkSize) + j * kChunkSize); 168 } 169 } 170 } 171 LOG(FATAL) << "Did not find chunk that contains monitor."; 172 return 0; 173 } 174 MonitorIdToOffset(MonitorId id)175 static constexpr size_t MonitorIdToOffset(MonitorId id) { 176 return id << 3; 177 } 178 OffsetToMonitorId(size_t offset)179 static constexpr MonitorId OffsetToMonitorId(size_t offset) { 180 return static_cast<MonitorId>(offset >> 3); 181 } 182 ChunkListCapacity(size_t index)183 static constexpr size_t ChunkListCapacity(size_t index) { 184 return kInitialChunkStorage << index; 185 } 186 187 // TODO: There are assumptions in the code that monitor addresses are 8B aligned (>>3). 188 static constexpr size_t kMonitorAlignment = 8; 189 // Size of a monitor, rounded up to a multiple of alignment. 190 static constexpr size_t kAlignedMonitorSize = (sizeof(Monitor) + kMonitorAlignment - 1) & 191 -kMonitorAlignment; 192 // As close to a page as we can get seems a good start. 193 static constexpr size_t kChunkCapacity = kPageSize / kAlignedMonitorSize; 194 // Chunk size that is referenced in the id. We can collapse this to the actually used storage 195 // in a chunk, i.e., kChunkCapacity * kAlignedMonitorSize, but this will mean proper divisions. 196 static constexpr size_t kChunkSize = kPageSize; 197 static_assert(IsPowerOfTwo(kChunkSize), "kChunkSize must be power of 2"); 198 // The number of chunks of storage that can be referenced by the initial chunk list. 199 // The total number of usable monitor chunks is typically 255 times this number, so it 200 // should be large enough that we don't run out. We run out of address bits if it's > 512. 201 // Currently we set it a bit smaller, to save half a page per process. We make it tiny in 202 // debug builds to catch growth errors. The only value we really expect to tune. 203 static constexpr size_t kInitialChunkStorage = kIsDebugBuild ? 8U : 256U; 204 static_assert(IsPowerOfTwo(kInitialChunkStorage), "kInitialChunkStorage must be power of 2"); 205 // The number of lists, each containing pointers to storage chunks. 206 static constexpr size_t kMaxChunkLists = 8; // Dictated by 3 bit index. Don't increase above 8. 207 static_assert(IsPowerOfTwo(kMaxChunkLists), "kMaxChunkLists must be power of 2"); 208 static constexpr size_t kMaxListSize = kInitialChunkStorage << (kMaxChunkLists - 1); 209 // We lose 3 bits in monitor id due to 3 bit monitor_chunks_ index, and gain it back from 210 // the 3 bit alignment constraint on monitors: 211 static_assert(kMaxListSize * kChunkSize < (1 << LockWord::kMonitorIdSize), 212 "Monitor id bits don't fit"); 213 static_assert(IsPowerOfTwo(kMaxListSize), "kMaxListSize must be power of 2"); 214 215 // Array of pointers to lists (again arrays) of pointers to chunks containing monitors. 216 // Zeroth entry points to a list (array) of kInitialChunkStorage pointers to chunks. 217 // Each subsequent list as twice as large as the preceding one. 218 // Monitor Ids are interpreted as follows: 219 // Top 3 bits (of 28): index into monitor_chunks_. 220 // Next 16 bits: index into the chunk list, i.e. monitor_chunks_[i]. 221 // Last 9 bits: offset within chunk, expressed as multiple of kMonitorAlignment. 222 // If we set kInitialChunkStorage to 512, this would allow us to use roughly 128K chunks of 223 // monitors, which is 0.5GB of monitors. With this maximum setting, the largest chunk list 224 // contains 64K entries, and we make full use of the available index space. With a 225 // kInitialChunkStorage value of 256, this is proportionately reduced to 0.25GB of monitors. 226 // Updates to monitor_chunks_ are guarded by allocated_monitor_ids_lock_ . 227 // No field in this entire data structure is ever updated once a monitor id whose lookup 228 // requires it has been made visible to another thread. Thus readers never race with 229 // updates, in spite of the fact that they acquire no locks. 230 uintptr_t* monitor_chunks_[kMaxChunkLists]; // uintptr_t is really a Monitor* . 231 // Highest currently used index in monitor_chunks_ . Used for newly allocated chunks. 232 size_t current_chunk_list_index_ GUARDED_BY(Locks::allocated_monitor_ids_lock_); 233 // Number of chunk pointers stored in monitor_chunks_[current_chunk_list_index_] so far. 234 size_t num_chunks_ GUARDED_BY(Locks::allocated_monitor_ids_lock_); 235 // After the initial allocation, this is always equal to 236 // ChunkListCapacity(current_chunk_list_index_). 237 size_t current_chunk_list_capacity_ GUARDED_BY(Locks::allocated_monitor_ids_lock_); 238 239 using Allocator = TrackingAllocator<uint8_t, kAllocatorTagMonitorPool>; 240 Allocator allocator_; 241 242 // Start of free list of monitors. 243 // Note: these point to the right memory regions, but do *not* denote initialized objects. 244 Monitor* first_free_ GUARDED_BY(Locks::allocated_monitor_ids_lock_); 245 #endif 246 }; 247 248 } // namespace art 249 250 #endif // ART_RUNTIME_MONITOR_POOL_H_ 251