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