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 "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,mirror::Object * obj,int32_t hash_code)45   static Monitor* CreateMonitor(Thread* self, Thread* owner, mirror::Object* obj, int32_t hash_code)
46       SHARED_REQUIRES(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 
ReleaseMonitor(Thread * self,Monitor * monitor)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 
ReleaseMonitors(Thread * self,MonitorList::Monitors * monitors)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 
MonitorFromMonitorId(MonitorId mon_id)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 
MonitorIdFromMonitor(Monitor * mon)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 
ComputeMonitorId(Monitor * mon,Thread * self)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 
GetMonitorPool()99   static MonitorPool* GetMonitorPool() {
100 #ifndef __LP64__
101     return nullptr;
102 #else
103     return Runtime::Current()->GetMonitorPool();
104 #endif
105   }
106 
~MonitorPool()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       SHARED_REQUIRES(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.
LookupMonitor(MonitorId mon_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 
IsInChunk(uintptr_t base_addr,Monitor * mon)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 
ComputeMonitorIdInPool(Monitor * mon,Thread * self)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 
MonitorIdToOffset(MonitorId id)169   static constexpr size_t MonitorIdToOffset(MonitorId id) {
170     return id << 3;
171   }
172 
OffsetToMonitorId(size_t offset)173   static constexpr MonitorId OffsetToMonitorId(size_t offset) {
174     return static_cast<MonitorId>(offset >> 3);
175   }
176 
ChunkListCapacity(size_t index)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