blob: 80bae7ff6939d5d86216f07c2badb62508c2d31c [file] [log] [blame]
Ian Rogersef7d42f2014-01-06 12:55:46 -08001/*
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
Ian Rogersb0fa5dc2014-04-28 16:47:08 -070020#include "monitor.h"
21
Mathieu Chartierbad02672014-08-25 13:08:22 -070022#include "base/allocator.h"
Ian Rogers44d6ff12014-03-06 23:11:11 -080023#ifdef __LP64__
Ian Rogersef7d42f2014-01-06 12:55:46 -080024#include <stdint.h>
Andreas Gampe74240812014-04-17 10:35:09 -070025#include "atomic.h"
Ian Rogers44d6ff12014-03-06 23:11:11 -080026#include "runtime.h"
Andreas Gampe74240812014-04-17 10:35:09 -070027#else
28#include "base/stl_util.h" // STLDeleteElements
Ian Rogers44d6ff12014-03-06 23:11:11 -080029#endif
30
Ian Rogersef7d42f2014-01-06 12:55:46 -080031namespace 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*.
35class MonitorPool {
36 public:
37 static MonitorPool* Create() {
38#ifndef __LP64__
39 return nullptr;
40#else
41 return new MonitorPool();
42#endif
43 }
44
Andreas Gampe74240812014-04-17 10:35:09 -070045 static Monitor* CreateMonitor(Thread* self, Thread* owner, mirror::Object* obj, int32_t hash_code)
Andreas Gampebdf7f1c2016-08-30 16:38:47 -070046 REQUIRES_SHARED(Locks::mutator_lock_) {
Andreas Gampe74240812014-04-17 10:35:09 -070047#ifndef __LP64__
Hiroshi Yamauchie15ea082015-02-09 17:11:42 -080048 Monitor* mon = new Monitor(self, owner, obj, hash_code);
49 DCHECK_ALIGNED(mon, LockWord::kMonitorIdAlignment);
50 return mon;
Andreas Gampe74240812014-04-17 10:35:09 -070051#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__
Ian Rogers6a3c1fc2014-10-31 00:33:20 -070058 UNUSED(self);
Andreas Gampe74240812014-04-17 10:35:09 -070059 delete monitor;
60#else
61 GetMonitorPool()->ReleaseMonitorToPool(self, monitor);
62#endif
63 }
64
Mathieu Chartierbad02672014-08-25 13:08:22 -070065 static void ReleaseMonitors(Thread* self, MonitorList::Monitors* monitors) {
Andreas Gampe74240812014-04-17 10:35:09 -070066#ifndef __LP64__
Ian Rogers6a3c1fc2014-10-31 00:33:20 -070067 UNUSED(self);
Andreas Gampe74240812014-04-17 10:35:09 -070068 STLDeleteElements(monitors);
69#else
70 GetMonitorPool()->ReleaseMonitorsToPool(self, monitors);
71#endif
72 }
73
Ian Rogersef7d42f2014-01-06 12:55:46 -080074 static Monitor* MonitorFromMonitorId(MonitorId mon_id) {
75#ifndef __LP64__
Hiroshi Yamauchie15ea082015-02-09 17:11:42 -080076 return reinterpret_cast<Monitor*>(mon_id << LockWord::kMonitorIdAlignmentShift);
Ian Rogersef7d42f2014-01-06 12:55:46 -080077#else
Andreas Gampe74240812014-04-17 10:35:09 -070078 return GetMonitorPool()->LookupMonitor(mon_id);
Ian Rogersef7d42f2014-01-06 12:55:46 -080079#endif
80 }
81
82 static MonitorId MonitorIdFromMonitor(Monitor* mon) {
83#ifndef __LP64__
Hiroshi Yamauchie15ea082015-02-09 17:11:42 -080084 return reinterpret_cast<MonitorId>(mon) >> LockWord::kMonitorIdAlignmentShift;
Ian Rogersef7d42f2014-01-06 12:55:46 -080085#else
86 return mon->GetMonitorId();
87#endif
88 }
89
Andreas Gampe74240812014-04-17 10:35:09 -070090 static MonitorId ComputeMonitorId(Monitor* mon, Thread* self) {
Ian Rogersef7d42f2014-01-06 12:55:46 -080091#ifndef __LP64__
Ian Rogers6a3c1fc2014-10-31 00:33:20 -070092 UNUSED(self);
Ian Rogersef7d42f2014-01-06 12:55:46 -080093 return MonitorIdFromMonitor(mon);
94#else
Andreas Gampe74240812014-04-17 10:35:09 -070095 return GetMonitorPool()->ComputeMonitorIdInPool(mon, self);
Ian Rogersef7d42f2014-01-06 12:55:46 -080096#endif
97 }
98
Andreas Gampe74240812014-04-17 10:35:09 -070099 static MonitorPool* GetMonitorPool() {
Ian Rogersef7d42f2014-01-06 12:55:46 -0800100#ifndef __LP64__
Andreas Gampe74240812014-04-17 10:35:09 -0700101 return nullptr;
Ian Rogersef7d42f2014-01-06 12:55:46 -0800102#else
Andreas Gampe74240812014-04-17 10:35:09 -0700103 return Runtime::Current()->GetMonitorPool();
Ian Rogersef7d42f2014-01-06 12:55:46 -0800104#endif
105 }
106
Andreas Gampe057134b2016-03-10 08:33:45 -0800107 ~MonitorPool() {
108#ifdef __LP64__
109 FreeInternal();
110#endif
111 }
112
Ian Rogersef7d42f2014-01-06 12:55:46 -0800113 private:
114#ifdef __LP64__
Andreas Gampe74240812014-04-17 10:35:09 -0700115 // When we create a monitor pool, threads have not been initialized, yet, so ignore thread-safety
116 // analysis.
117 MonitorPool() NO_THREAD_SAFETY_ANALYSIS;
Ian Rogersef7d42f2014-01-06 12:55:46 -0800118
Mathieu Chartier90443472015-07-16 20:32:27 -0700119 void AllocateChunk() REQUIRES(Locks::allocated_monitor_ids_lock_);
Ian Rogersef7d42f2014-01-06 12:55:46 -0800120
Andreas Gampe057134b2016-03-10 08:33:45 -0800121 // 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
Andreas Gampe74240812014-04-17 10:35:09 -0700125 Monitor* CreateMonitorInPool(Thread* self, Thread* owner, mirror::Object* obj, int32_t hash_code)
Andreas Gampebdf7f1c2016-08-30 16:38:47 -0700126 REQUIRES_SHARED(Locks::mutator_lock_);
Ian Rogersef7d42f2014-01-06 12:55:46 -0800127
Andreas Gampe74240812014-04-17 10:35:09 -0700128 void ReleaseMonitorToPool(Thread* self, Monitor* monitor);
Mathieu Chartierbad02672014-08-25 13:08:22 -0700129 void ReleaseMonitorsToPool(Thread* self, MonitorList::Monitors* monitors);
Ian Rogersef7d42f2014-01-06 12:55:46 -0800130
Hans Boehma319f4d2016-04-27 15:04:24 -0700131 // 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.
Andreas Gampe74240812014-04-17 10:35:09 -0700135 Monitor* LookupMonitor(MonitorId mon_id) {
136 size_t offset = MonitorIdToOffset(mon_id);
137 size_t index = offset / kChunkSize;
Hans Boehma319f4d2016-04-27 15:04:24 -0700138 size_t top_index = index / kMaxListSize;
139 size_t list_index = index % kMaxListSize;
Andreas Gampe74240812014-04-17 10:35:09 -0700140 size_t offset_in_chunk = offset % kChunkSize;
Hans Boehma319f4d2016-04-27 15:04:24 -0700141 uintptr_t base = monitor_chunks_[top_index][list_index];
Andreas Gampe74240812014-04-17 10:35:09 -0700142 return reinterpret_cast<Monitor*>(base + offset_in_chunk);
143 }
Ian Rogersef7d42f2014-01-06 12:55:46 -0800144
Andreas Gampe74240812014-04-17 10:35:09 -0700145 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
Andreas Gampe74240812014-04-17 10:35:09 -0700150 MonitorId ComputeMonitorIdInPool(Monitor* mon, Thread* self) {
151 MutexLock mu(self, *Locks::allocated_monitor_ids_lock_);
Hans Boehma319f4d2016-04-27 15:04:24 -0700152 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 }
Andreas Gampe74240812014-04-17 10:35:09 -0700163 }
164 }
165 LOG(FATAL) << "Did not find chunk that contains monitor.";
166 return 0;
167 }
168
Hans Boehma319f4d2016-04-27 15:04:24 -0700169 static constexpr size_t MonitorIdToOffset(MonitorId id) {
Andreas Gampe74240812014-04-17 10:35:09 -0700170 return id << 3;
171 }
172
Hans Boehma319f4d2016-04-27 15:04:24 -0700173 static constexpr MonitorId OffsetToMonitorId(size_t offset) {
Andreas Gampe74240812014-04-17 10:35:09 -0700174 return static_cast<MonitorId>(offset >> 3);
175 }
176
Hans Boehma319f4d2016-04-27 15:04:24 -0700177 static constexpr size_t ChunkListCapacity(size_t index) {
178 return kInitialChunkStorage << index;
179 }
180
Andreas Gampe74240812014-04-17 10:35:09 -0700181 // 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;
Hans Boehma319f4d2016-04-27 15:04:24 -0700191 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");
Andreas Gampe74240812014-04-17 10:35:09 -0700208
Hans Boehma319f4d2016-04-27 15:04:24 -0700209 // 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.
Andreas Gampe74240812014-04-17 10:35:09 -0700228 size_t num_chunks_ GUARDED_BY(Locks::allocated_monitor_ids_lock_);
Hans Boehma319f4d2016-04-27 15:04:24 -0700229 // 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_);
Andreas Gampe74240812014-04-17 10:35:09 -0700232
Ian Rogers13735952014-10-08 12:43:28 -0700233 typedef TrackingAllocator<uint8_t, kAllocatorTagMonitorPool> Allocator;
Mathieu Chartierbad02672014-08-25 13:08:22 -0700234 Allocator allocator_;
235
Andreas Gampe74240812014-04-17 10:35:09 -0700236 // 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_);
Ian Rogersef7d42f2014-01-06 12:55:46 -0800239#endif
240};
241
242} // namespace art
243
244#endif // ART_RUNTIME_MONITOR_POOL_H_