1 /* 2 * Copyright (C) 2009 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_INDIRECT_REFERENCE_TABLE_H_ 18 #define ART_RUNTIME_INDIRECT_REFERENCE_TABLE_H_ 19 20 #include <stdint.h> 21 22 #include <iosfwd> 23 #include <string> 24 25 #include "base/logging.h" 26 #include "base/mutex.h" 27 #include "gc_root.h" 28 #include "object_callbacks.h" 29 #include "offsets.h" 30 #include "read_barrier_option.h" 31 32 namespace art { 33 34 class RootInfo; 35 36 namespace mirror { 37 class Object; 38 } // namespace mirror 39 40 class MemMap; 41 42 /* 43 * Maintain a table of indirect references. Used for local/global JNI 44 * references. 45 * 46 * The table contains object references that are part of the GC root set. 47 * When an object is added we return an IndirectRef that is not a valid 48 * pointer but can be used to find the original value in O(1) time. 49 * Conversions to and from indirect references are performed on upcalls 50 * and downcalls, so they need to be very fast. 51 * 52 * To be efficient for JNI local variable storage, we need to provide 53 * operations that allow us to operate on segments of the table, where 54 * segments are pushed and popped as if on a stack. For example, deletion 55 * of an entry should only succeed if it appears in the current segment, 56 * and we want to be able to strip off the current segment quickly when 57 * a method returns. Additions to the table must be made in the current 58 * segment even if space is available in an earlier area. 59 * 60 * A new segment is created when we call into native code from interpreted 61 * code, or when we handle the JNI PushLocalFrame function. 62 * 63 * The GC must be able to scan the entire table quickly. 64 * 65 * In summary, these must be very fast: 66 * - adding or removing a segment 67 * - adding references to a new segment 68 * - converting an indirect reference back to an Object 69 * These can be a little slower, but must still be pretty quick: 70 * - adding references to a "mature" segment 71 * - removing individual references 72 * - scanning the entire table straight through 73 * 74 * If there's more than one segment, we don't guarantee that the table 75 * will fill completely before we fail due to lack of space. We do ensure 76 * that the current segment will pack tightly, which should satisfy JNI 77 * requirements (e.g. EnsureLocalCapacity). 78 * 79 * To make everything fit nicely in 32-bit integers, the maximum size of 80 * the table is capped at 64K. 81 * 82 * Only SynchronizedGet is synchronized. 83 */ 84 85 /* 86 * Indirect reference definition. This must be interchangeable with JNI's 87 * jobject, and it's convenient to let null be null, so we use void*. 88 * 89 * We need a 16-bit table index and a 2-bit reference type (global, local, 90 * weak global). Real object pointers will have zeroes in the low 2 or 3 91 * bits (4- or 8-byte alignment), so it's useful to put the ref type 92 * in the low bits and reserve zero as an invalid value. 93 * 94 * The remaining 14 bits can be used to detect stale indirect references. 95 * For example, if objects don't move, we can use a hash of the original 96 * Object* to make sure the entry hasn't been re-used. (If the Object* 97 * we find there doesn't match because of heap movement, we could do a 98 * secondary check on the preserved hash value; this implies that creating 99 * a global/local ref queries the hash value and forces it to be saved.) 100 * 101 * A more rigorous approach would be to put a serial number in the extra 102 * bits, and keep a copy of the serial number in a parallel table. This is 103 * easier when objects can move, but requires 2x the memory and additional 104 * memory accesses on add/get. It will catch additional problems, e.g.: 105 * create iref1 for obj, delete iref1, create iref2 for same obj, lookup 106 * iref1. A pattern based on object bits will miss this. 107 */ 108 typedef void* IndirectRef; 109 110 /* 111 * Indirect reference kind, used as the two low bits of IndirectRef. 112 * 113 * For convenience these match up with enum jobjectRefType from jni.h. 114 */ 115 enum IndirectRefKind { 116 kHandleScopeOrInvalid = 0, // <<stack indirect reference table or invalid reference>> 117 kLocal = 1, // <<local reference>> 118 kGlobal = 2, // <<global reference>> 119 kWeakGlobal = 3 // <<weak global reference>> 120 }; 121 std::ostream& operator<<(std::ostream& os, const IndirectRefKind& rhs); 122 const char* GetIndirectRefKindString(const IndirectRefKind& kind); 123 124 /* 125 * Determine what kind of indirect reference this is. 126 */ 127 static inline IndirectRefKind GetIndirectRefKind(IndirectRef iref) { 128 return static_cast<IndirectRefKind>(reinterpret_cast<uintptr_t>(iref) & 0x03); 129 } 130 131 /* use as initial value for "cookie", and when table has only one segment */ 132 static const uint32_t IRT_FIRST_SEGMENT = 0; 133 134 /* 135 * Table definition. 136 * 137 * For the global reference table, the expected common operations are 138 * adding a new entry and removing a recently-added entry (usually the 139 * most-recently-added entry). For JNI local references, the common 140 * operations are adding a new entry and removing an entire table segment. 141 * 142 * If "alloc_entries_" is not equal to "max_entries_", the table may expand 143 * when entries are added, which means the memory may move. If you want 144 * to keep pointers into "table" rather than offsets, you must use a 145 * fixed-size table. 146 * 147 * If we delete entries from the middle of the list, we will be left with 148 * "holes". We track the number of holes so that, when adding new elements, 149 * we can quickly decide to do a trivial append or go slot-hunting. 150 * 151 * When the top-most entry is removed, any holes immediately below it are 152 * also removed. Thus, deletion of an entry may reduce "topIndex" by more 153 * than one. 154 * 155 * To get the desired behavior for JNI locals, we need to know the bottom 156 * and top of the current "segment". The top is managed internally, and 157 * the bottom is passed in as a function argument. When we call a native method or 158 * push a local frame, the current top index gets pushed on, and serves 159 * as the new bottom. When we pop a frame off, the value from the stack 160 * becomes the new top index, and the value stored in the previous frame 161 * becomes the new bottom. 162 * 163 * To avoid having to re-scan the table after a pop, we want to push the 164 * number of holes in the table onto the stack. Because of our 64K-entry 165 * cap, we can combine the two into a single unsigned 32-bit value. 166 * Instead of a "bottom" argument we take a "cookie", which includes the 167 * bottom index and the count of holes below the bottom. 168 * 169 * Common alternative implementation: make IndirectRef a pointer to the 170 * actual reference slot. Instead of getting a table and doing a lookup, 171 * the lookup can be done instantly. Operations like determining the 172 * type and deleting the reference are more expensive because the table 173 * must be hunted for (i.e. you have to do a pointer comparison to see 174 * which table it's in), you can't move the table when expanding it (so 175 * realloc() is out), and tricks like serial number checking to detect 176 * stale references aren't possible (though we may be able to get similar 177 * benefits with other approaches). 178 * 179 * TODO: consider a "lastDeleteIndex" for quick hole-filling when an 180 * add immediately follows a delete; must invalidate after segment pop 181 * (which could increase the cost/complexity of method call/return). 182 * Might be worth only using it for JNI globals. 183 * 184 * TODO: may want completely different add/remove algorithms for global 185 * and local refs to improve performance. A large circular buffer might 186 * reduce the amortized cost of adding global references. 187 * 188 */ 189 union IRTSegmentState { 190 uint32_t all; 191 struct { 192 uint32_t topIndex:16; /* index of first unused entry */ 193 uint32_t numHoles:16; /* #of holes in entire table */ 194 } parts; 195 }; 196 197 // Try to choose kIRTPrevCount so that sizeof(IrtEntry) is a power of 2. 198 // Contains multiple entries but only one active one, this helps us detect use after free errors 199 // since the serial stored in the indirect ref wont match. 200 static const size_t kIRTPrevCount = kIsDebugBuild ? 7 : 3; 201 class IrtEntry { 202 public: 203 void Add(mirror::Object* obj) SHARED_REQUIRES(Locks::mutator_lock_) { 204 ++serial_; 205 if (serial_ == kIRTPrevCount) { 206 serial_ = 0; 207 } 208 references_[serial_] = GcRoot<mirror::Object>(obj); 209 } 210 GcRoot<mirror::Object>* GetReference() { 211 DCHECK_LT(serial_, kIRTPrevCount); 212 return &references_[serial_]; 213 } 214 uint32_t GetSerial() const { 215 return serial_; 216 } 217 void SetReference(mirror::Object* obj) { 218 DCHECK_LT(serial_, kIRTPrevCount); 219 references_[serial_] = GcRoot<mirror::Object>(obj); 220 } 221 222 private: 223 uint32_t serial_; 224 GcRoot<mirror::Object> references_[kIRTPrevCount]; 225 }; 226 static_assert(sizeof(IrtEntry) == (1 + kIRTPrevCount) * sizeof(uint32_t), 227 "Unexpected sizeof(IrtEntry)"); 228 229 class IrtIterator { 230 public: 231 IrtIterator(IrtEntry* table, size_t i, size_t capacity) SHARED_REQUIRES(Locks::mutator_lock_) 232 : table_(table), i_(i), capacity_(capacity) { 233 } 234 235 IrtIterator& operator++() SHARED_REQUIRES(Locks::mutator_lock_) { 236 ++i_; 237 return *this; 238 } 239 240 GcRoot<mirror::Object>* operator*() { 241 // This does not have a read barrier as this is used to visit roots. 242 return table_[i_].GetReference(); 243 } 244 245 bool equals(const IrtIterator& rhs) const { 246 return (i_ == rhs.i_ && table_ == rhs.table_); 247 } 248 249 private: 250 IrtEntry* const table_; 251 size_t i_; 252 const size_t capacity_; 253 }; 254 255 bool inline operator==(const IrtIterator& lhs, const IrtIterator& rhs) { 256 return lhs.equals(rhs); 257 } 258 259 bool inline operator!=(const IrtIterator& lhs, const IrtIterator& rhs) { 260 return !lhs.equals(rhs); 261 } 262 263 class IndirectReferenceTable { 264 public: 265 // WARNING: When using with abort_on_error = false, the object may be in a partially 266 // initialized state. Use IsValid() to check. 267 IndirectReferenceTable(size_t initialCount, size_t maxCount, IndirectRefKind kind, 268 bool abort_on_error = true); 269 270 ~IndirectReferenceTable(); 271 272 bool IsValid() const; 273 274 /* 275 * Add a new entry. "obj" must be a valid non-nullptr object reference. 276 * 277 * Returns nullptr if the table is full (max entries reached, or alloc 278 * failed during expansion). 279 */ 280 IndirectRef Add(uint32_t cookie, mirror::Object* obj) 281 SHARED_REQUIRES(Locks::mutator_lock_); 282 283 /* 284 * Given an IndirectRef in the table, return the Object it refers to. 285 * 286 * Returns kInvalidIndirectRefObject if iref is invalid. 287 */ 288 template<ReadBarrierOption kReadBarrierOption = kWithReadBarrier> 289 mirror::Object* Get(IndirectRef iref) const SHARED_REQUIRES(Locks::mutator_lock_) 290 ALWAYS_INLINE; 291 292 // Synchronized get which reads a reference, acquiring a lock if necessary. 293 template<ReadBarrierOption kReadBarrierOption = kWithReadBarrier> 294 mirror::Object* SynchronizedGet(IndirectRef iref) const SHARED_REQUIRES(Locks::mutator_lock_) { 295 return Get<kReadBarrierOption>(iref); 296 } 297 298 /* 299 * Update an existing entry. 300 * 301 * Updates an existing indirect reference to point to a new object. 302 */ 303 void Update(IndirectRef iref, mirror::Object* obj) SHARED_REQUIRES(Locks::mutator_lock_); 304 305 /* 306 * Remove an existing entry. 307 * 308 * If the entry is not between the current top index and the bottom index 309 * specified by the cookie, we don't remove anything. This is the behavior 310 * required by JNI's DeleteLocalRef function. 311 * 312 * Returns "false" if nothing was removed. 313 */ 314 bool Remove(uint32_t cookie, IndirectRef iref); 315 316 void AssertEmpty(); 317 318 void Dump(std::ostream& os) const SHARED_REQUIRES(Locks::mutator_lock_); 319 320 /* 321 * Return the #of entries in the entire table. This includes holes, and 322 * so may be larger than the actual number of "live" entries. 323 */ 324 size_t Capacity() const { 325 return segment_state_.parts.topIndex; 326 } 327 328 // Note IrtIterator does not have a read barrier as it's used to visit roots. 329 IrtIterator begin() { 330 return IrtIterator(table_, 0, Capacity()); 331 } 332 333 IrtIterator end() { 334 return IrtIterator(table_, Capacity(), Capacity()); 335 } 336 337 void VisitRoots(RootVisitor* visitor, const RootInfo& root_info) 338 SHARED_REQUIRES(Locks::mutator_lock_); 339 340 uint32_t GetSegmentState() const { 341 return segment_state_.all; 342 } 343 344 void SetSegmentState(uint32_t new_state) { 345 segment_state_.all = new_state; 346 } 347 348 static Offset SegmentStateOffset(size_t pointer_size ATTRIBUTE_UNUSED) { 349 // Note: Currently segment_state_ is at offset 0. We're testing the expected value in 350 // jni_internal_test to make sure it stays correct. It is not OFFSETOF_MEMBER, as that 351 // is not pointer-size-safe. 352 return Offset(0); 353 } 354 355 // Release pages past the end of the table that may have previously held references. 356 void Trim() SHARED_REQUIRES(Locks::mutator_lock_); 357 358 private: 359 // Extract the table index from an indirect reference. 360 static uint32_t ExtractIndex(IndirectRef iref) { 361 uintptr_t uref = reinterpret_cast<uintptr_t>(iref); 362 return (uref >> 2) & 0xffff; 363 } 364 365 /* 366 * The object pointer itself is subject to relocation in some GC 367 * implementations, so we shouldn't really be using it here. 368 */ 369 IndirectRef ToIndirectRef(uint32_t tableIndex) const { 370 DCHECK_LT(tableIndex, 65536U); 371 uint32_t serialChunk = table_[tableIndex].GetSerial(); 372 uintptr_t uref = (serialChunk << 20) | (tableIndex << 2) | kind_; 373 return reinterpret_cast<IndirectRef>(uref); 374 } 375 376 // Abort if check_jni is not enabled. Otherwise, just log as an error. 377 static void AbortIfNoCheckJNI(const std::string& msg); 378 379 /* extra debugging checks */ 380 bool GetChecked(IndirectRef) const; 381 bool CheckEntry(const char*, IndirectRef, int) const; 382 383 /* semi-public - read/write by jni down calls */ 384 IRTSegmentState segment_state_; 385 386 // Mem map where we store the indirect refs. 387 std::unique_ptr<MemMap> table_mem_map_; 388 // bottom of the stack. Do not directly access the object references 389 // in this as they are roots. Use Get() that has a read barrier. 390 IrtEntry* table_; 391 /* bit mask, ORed into all irefs */ 392 const IndirectRefKind kind_; 393 /* max #of entries allowed */ 394 const size_t max_entries_; 395 }; 396 397 } // namespace art 398 399 #endif // ART_RUNTIME_INDIRECT_REFERENCE_TABLE_H_ 400