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