Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 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_SRC_INDIRECT_REFERENCE_TABLE_H_ |
| 18 | #define ART_SRC_INDIRECT_REFERENCE_TABLE_H_ |
| 19 | |
Elliott Hughes | 410c0c8 | 2011-09-01 17:58:25 -0700 | [diff] [blame] | 20 | #include "heap.h" |
Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 21 | #include "logging.h" |
| 22 | |
| 23 | #include <iosfwd> |
| 24 | #include <stdint.h> |
| 25 | #include <string> |
| 26 | |
| 27 | namespace art { |
| 28 | |
| 29 | class Object; |
| 30 | |
| 31 | /* |
| 32 | * Maintain a table of indirect references. Used for local/global JNI |
| 33 | * references. |
| 34 | * |
| 35 | * The table contains object references that are part of the GC root set. |
| 36 | * When an object is added we return an IndirectRef that is not a valid |
| 37 | * pointer but can be used to find the original value in O(1) time. |
| 38 | * Conversions to and from indirect refs are performed on JNI method calls |
| 39 | * in and out of the VM, so they need to be very fast. |
| 40 | * |
| 41 | * To be efficient for JNI local variable storage, we need to provide |
| 42 | * operations that allow us to operate on segments of the table, where |
| 43 | * segments are pushed and popped as if on a stack. For example, deletion |
| 44 | * of an entry should only succeed if it appears in the current segment, |
| 45 | * and we want to be able to strip off the current segment quickly when |
| 46 | * a method returns. Additions to the table must be made in the current |
| 47 | * segment even if space is available in an earlier area. |
| 48 | * |
| 49 | * A new segment is created when we call into native code from interpreted |
| 50 | * code, or when we handle the JNI PushLocalFrame function. |
| 51 | * |
| 52 | * The GC must be able to scan the entire table quickly. |
| 53 | * |
| 54 | * In summary, these must be very fast: |
| 55 | * - adding or removing a segment |
| 56 | * - adding references to a new segment |
| 57 | * - converting an indirect reference back to an Object |
| 58 | * These can be a little slower, but must still be pretty quick: |
| 59 | * - adding references to a "mature" segment |
| 60 | * - removing individual references |
| 61 | * - scanning the entire table straight through |
| 62 | * |
| 63 | * If there's more than one segment, we don't guarantee that the table |
| 64 | * will fill completely before we fail due to lack of space. We do ensure |
| 65 | * that the current segment will pack tightly, which should satisfy JNI |
| 66 | * requirements (e.g. EnsureLocalCapacity). |
| 67 | * |
| 68 | * To make everything fit nicely in 32-bit integers, the maximum size of |
| 69 | * the table is capped at 64K. |
| 70 | * |
| 71 | * None of the table functions are synchronized. |
| 72 | */ |
| 73 | |
| 74 | /* |
| 75 | * Indirect reference definition. This must be interchangeable with JNI's |
| 76 | * jobject, and it's convenient to let null be null, so we use void*. |
| 77 | * |
| 78 | * We need a 16-bit table index and a 2-bit reference type (global, local, |
| 79 | * weak global). Real object pointers will have zeroes in the low 2 or 3 |
| 80 | * bits (4- or 8-byte alignment), so it's useful to put the ref type |
| 81 | * in the low bits and reserve zero as an invalid value. |
| 82 | * |
| 83 | * The remaining 14 bits can be used to detect stale indirect references. |
| 84 | * For example, if objects don't move, we can use a hash of the original |
| 85 | * Object* to make sure the entry hasn't been re-used. (If the Object* |
| 86 | * we find there doesn't match because of heap movement, we could do a |
| 87 | * secondary check on the preserved hash value; this implies that creating |
| 88 | * a global/local ref queries the hash value and forces it to be saved.) |
| 89 | * |
| 90 | * A more rigorous approach would be to put a serial number in the extra |
| 91 | * bits, and keep a copy of the serial number in a parallel table. This is |
| 92 | * easier when objects can move, but requires 2x the memory and additional |
| 93 | * memory accesses on add/get. It will catch additional problems, e.g.: |
| 94 | * create iref1 for obj, delete iref1, create iref2 for same obj, lookup |
| 95 | * iref1. A pattern based on object bits will miss this. |
| 96 | */ |
| 97 | typedef void* IndirectRef; |
| 98 | |
Elliott Hughes | b3bd5f0 | 2012-03-08 21:05:27 -0800 | [diff] [blame^] | 99 | // Magic failure values; must not pass Heap::ValidateObject() or Heap::IsHeapAddress(). |
Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 100 | static Object* const kInvalidIndirectRefObject = reinterpret_cast<Object*>(0xdead4321); |
| 101 | static Object* const kClearedJniWeakGlobal = reinterpret_cast<Object*>(0xdead1234); |
| 102 | |
| 103 | /* |
| 104 | * Indirect reference kind, used as the two low bits of IndirectRef. |
| 105 | * |
| 106 | * For convenience these match up with enum jobjectRefType from jni.h. |
| 107 | */ |
| 108 | enum IndirectRefKind { |
Ian Rogers | 408f79a | 2011-08-23 18:22:33 -0700 | [diff] [blame] | 109 | kSirtOrInvalid = 0, |
| 110 | kLocal = 1, |
| 111 | kGlobal = 2, |
| 112 | kWeakGlobal = 3 |
Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 113 | }; |
| 114 | std::ostream& operator<<(std::ostream& os, IndirectRefKind rhs); |
| 115 | |
| 116 | /* |
| 117 | * Determine what kind of indirect reference this is. |
| 118 | */ |
| 119 | static inline IndirectRefKind GetIndirectRefKind(IndirectRef iref) { |
| 120 | return static_cast<IndirectRefKind>(reinterpret_cast<uintptr_t>(iref) & 0x03); |
| 121 | } |
| 122 | |
| 123 | /* |
| 124 | * Extended debugging structure. We keep a parallel array of these, one |
| 125 | * per slot in the table. |
| 126 | */ |
| 127 | static const size_t kIRTPrevCount = 4; |
| 128 | struct IndirectRefSlot { |
| 129 | uint32_t serial; |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 130 | const Object* previous[kIRTPrevCount]; |
Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 131 | }; |
| 132 | |
| 133 | /* use as initial value for "cookie", and when table has only one segment */ |
| 134 | static const uint32_t IRT_FIRST_SEGMENT = 0; |
| 135 | |
| 136 | /* |
| 137 | * Table definition. |
| 138 | * |
| 139 | * For the global reference table, the expected common operations are |
| 140 | * adding a new entry and removing a recently-added entry (usually the |
| 141 | * most-recently-added entry). For JNI local references, the common |
| 142 | * operations are adding a new entry and removing an entire table segment. |
| 143 | * |
| 144 | * If "alloc_entries_" is not equal to "max_entries_", the table may expand |
| 145 | * when entries are added, which means the memory may move. If you want |
| 146 | * to keep pointers into "table" rather than offsets, you must use a |
| 147 | * fixed-size table. |
| 148 | * |
| 149 | * If we delete entries from the middle of the list, we will be left with |
| 150 | * "holes". We track the number of holes so that, when adding new elements, |
| 151 | * we can quickly decide to do a trivial append or go slot-hunting. |
| 152 | * |
| 153 | * When the top-most entry is removed, any holes immediately below it are |
| 154 | * also removed. Thus, deletion of an entry may reduce "topIndex" by more |
| 155 | * than one. |
| 156 | * |
| 157 | * To get the desired behavior for JNI locals, we need to know the bottom |
| 158 | * and top of the current "segment". The top is managed internally, and |
| 159 | * the bottom is passed in as a function argument (the VM keeps it in a |
| 160 | * slot in the interpreted stack frame). When we call a native method or |
| 161 | * push a local frame, the current top index gets pushed on, and serves |
| 162 | * as the new bottom. When we pop a frame off, the value from the stack |
| 163 | * becomes the new top index, and the value stored in the previous frame |
| 164 | * becomes the new bottom. |
| 165 | * |
| 166 | * To avoid having to re-scan the table after a pop, we want to push the |
| 167 | * number of holes in the table onto the stack. Because of our 64K-entry |
| 168 | * cap, we can combine the two into a single unsigned 32-bit value. |
| 169 | * Instead of a "bottom" argument we take a "cookie", which includes the |
| 170 | * bottom index and the count of holes below the bottom. |
| 171 | * |
| 172 | * We need to minimize method call/return overhead. If we store the |
| 173 | * "cookie" externally, on the interpreted call stack, the VM can handle |
| 174 | * pushes and pops with a single 4-byte load and store. (We could also |
| 175 | * store it internally in a public structure, but the local JNI refs are |
| 176 | * logically tied to interpreted stack frames anyway.) |
| 177 | * |
| 178 | * Common alternative implementation: make IndirectRef a pointer to the |
| 179 | * actual reference slot. Instead of getting a table and doing a lookup, |
| 180 | * the lookup can be done instantly. Operations like determining the |
| 181 | * type and deleting the reference are more expensive because the table |
| 182 | * must be hunted for (i.e. you have to do a pointer comparison to see |
| 183 | * which table it's in), you can't move the table when expanding it (so |
| 184 | * realloc() is out), and tricks like serial number checking to detect |
| 185 | * stale references aren't possible (though we may be able to get similar |
| 186 | * benefits with other approaches). |
| 187 | * |
| 188 | * TODO: consider a "lastDeleteIndex" for quick hole-filling when an |
| 189 | * add immediately follows a delete; must invalidate after segment pop |
| 190 | * (which could increase the cost/complexity of method call/return). |
| 191 | * Might be worth only using it for JNI globals. |
| 192 | * |
| 193 | * TODO: may want completely different add/remove algorithms for global |
| 194 | * and local refs to improve performance. A large circular buffer might |
| 195 | * reduce the amortized cost of adding global references. |
| 196 | * |
| 197 | * TODO: if we can guarantee that the underlying storage doesn't move, |
| 198 | * e.g. by using oversized mmap regions to handle expanding tables, we may |
| 199 | * be able to avoid having to synchronize lookups. Might make sense to |
| 200 | * add a "synchronized lookup" call that takes the mutex as an argument, |
| 201 | * and either locks or doesn't lock based on internal details. |
| 202 | */ |
| 203 | union IRTSegmentState { |
| 204 | uint32_t all; |
| 205 | struct { |
| 206 | uint32_t topIndex:16; /* index of first unused entry */ |
| 207 | uint32_t numHoles:16; /* #of holes in entire table */ |
| 208 | } parts; |
| 209 | }; |
| 210 | |
| 211 | class IrtIterator { |
| 212 | public: |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 213 | explicit IrtIterator(const Object** table, size_t i, size_t capacity) |
Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 214 | : table_(table), i_(i), capacity_(capacity) { |
| 215 | SkipNullsAndTombstones(); |
| 216 | } |
| 217 | |
| 218 | IrtIterator& operator++() { |
| 219 | ++i_; |
| 220 | SkipNullsAndTombstones(); |
| 221 | return *this; |
| 222 | } |
| 223 | |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 224 | const Object** operator*() { |
Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 225 | return &table_[i_]; |
| 226 | } |
| 227 | |
| 228 | bool equals(const IrtIterator& rhs) const { |
| 229 | return (i_ == rhs.i_ && table_ == rhs.table_); |
| 230 | } |
| 231 | |
| 232 | private: |
| 233 | void SkipNullsAndTombstones() { |
| 234 | // We skip NULLs and tombstones. Clients don't want to see implementation details. |
| 235 | while (i_ < capacity_ && (table_[i_] == NULL || table_[i_] == kClearedJniWeakGlobal)) { |
| 236 | ++i_; |
| 237 | } |
| 238 | } |
| 239 | |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 240 | const Object** table_; |
Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 241 | size_t i_; |
| 242 | size_t capacity_; |
| 243 | }; |
| 244 | |
Elliott Hughes | 726079d | 2011-10-07 18:43:44 -0700 | [diff] [blame] | 245 | bool inline operator==(const IrtIterator& lhs, const IrtIterator& rhs) { |
| 246 | return lhs.equals(rhs); |
| 247 | } |
| 248 | |
Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 249 | bool inline operator!=(const IrtIterator& lhs, const IrtIterator& rhs) { |
| 250 | return !lhs.equals(rhs); |
| 251 | } |
| 252 | |
| 253 | class IndirectReferenceTable { |
| 254 | public: |
| 255 | typedef IrtIterator iterator; |
| 256 | |
| 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 | * (though it's okay if it's not fully-formed, e.g. the result from |
| 264 | * dvmMalloc doesn't have obj->clazz set). |
| 265 | * |
| 266 | * Returns NULL if the table is full (max entries reached, or alloc |
| 267 | * failed during expansion). |
| 268 | */ |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 269 | IndirectRef Add(uint32_t cookie, const Object* obj); |
Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 270 | |
| 271 | /* |
| 272 | * Given an IndirectRef in the table, return the Object it refers to. |
| 273 | * |
| 274 | * Returns kInvalidIndirectRefObject if iref is invalid. |
| 275 | */ |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 276 | const Object* Get(IndirectRef iref) const { |
Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 277 | if (!GetChecked(iref)) { |
| 278 | return kInvalidIndirectRefObject; |
| 279 | } |
| 280 | return table_[ExtractIndex(iref)]; |
| 281 | } |
| 282 | |
Elliott Hughes | c5bfa8f | 2011-08-30 14:32:49 -0700 | [diff] [blame] | 283 | // TODO: remove when we remove work_around_app_jni_bugs support. |
Elliott Hughes | 2ced6a5 | 2011-10-16 18:44:48 -0700 | [diff] [blame] | 284 | bool ContainsDirectPointer(Object* direct_pointer) const; |
Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 285 | |
| 286 | /* |
| 287 | * Remove an existing entry. |
| 288 | * |
| 289 | * If the entry is not between the current top index and the bottom index |
| 290 | * specified by the cookie, we don't remove anything. This is the behavior |
| 291 | * required by JNI's DeleteLocalRef function. |
| 292 | * |
| 293 | * Returns "false" if nothing was removed. |
| 294 | */ |
| 295 | bool Remove(uint32_t cookie, IndirectRef iref); |
| 296 | |
Elliott Hughes | 726079d | 2011-10-07 18:43:44 -0700 | [diff] [blame] | 297 | void AssertEmpty(); |
| 298 | |
Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 299 | void Dump() const; |
| 300 | |
| 301 | /* |
| 302 | * Return the #of entries in the entire table. This includes holes, and |
| 303 | * so may be larger than the actual number of "live" entries. |
| 304 | */ |
| 305 | size_t Capacity() const { |
Ian Rogers | dc51b79 | 2011-09-22 20:41:37 -0700 | [diff] [blame] | 306 | return segment_state_.parts.topIndex; |
Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 307 | } |
| 308 | |
| 309 | iterator begin() { |
| 310 | return iterator(table_, 0, Capacity()); |
| 311 | } |
| 312 | |
| 313 | iterator end() { |
| 314 | return iterator(table_, Capacity(), Capacity()); |
| 315 | } |
| 316 | |
Elliott Hughes | 410c0c8 | 2011-09-01 17:58:25 -0700 | [diff] [blame] | 317 | void VisitRoots(Heap::RootVisitor* visitor, void* arg); |
| 318 | |
Ian Rogers | ad25ac5 | 2011-10-04 19:13:33 -0700 | [diff] [blame] | 319 | uint32_t GetSegmentState() const { |
| 320 | return segment_state_.all; |
| 321 | } |
| 322 | |
| 323 | void SetSegmentState(uint32_t new_state) { |
| 324 | segment_state_.all = new_state; |
| 325 | } |
| 326 | |
Ian Rogers | dc51b79 | 2011-09-22 20:41:37 -0700 | [diff] [blame] | 327 | static Offset SegmentStateOffset() { |
| 328 | return Offset(OFFSETOF_MEMBER(IndirectReferenceTable, segment_state_)); |
| 329 | } |
Elliott Hughes | b3bd5f0 | 2012-03-08 21:05:27 -0800 | [diff] [blame^] | 330 | |
Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 331 | private: |
| 332 | /* |
| 333 | * Extract the table index from an indirect reference. |
| 334 | */ |
| 335 | static uint32_t ExtractIndex(IndirectRef iref) { |
| 336 | uint32_t uref = (uint32_t) iref; |
| 337 | return (uref >> 2) & 0xffff; |
| 338 | } |
| 339 | |
| 340 | /* |
| 341 | * The object pointer itself is subject to relocation in some GC |
| 342 | * implementations, so we shouldn't really be using it here. |
| 343 | */ |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 344 | IndirectRef ToIndirectRef(const Object* obj, uint32_t tableIndex) const { |
Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 345 | DCHECK_LT(tableIndex, 65536U); |
| 346 | uint32_t serialChunk = slot_data_[tableIndex].serial; |
| 347 | uint32_t uref = serialChunk << 20 | (tableIndex << 2) | kind_; |
| 348 | return (IndirectRef) uref; |
| 349 | } |
| 350 | |
| 351 | /* |
| 352 | * Update extended debug info when an entry is added. |
| 353 | * |
| 354 | * We advance the serial number, invalidating any outstanding references to |
| 355 | * this slot. |
| 356 | */ |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 357 | void UpdateSlotAdd(const Object* obj, int slot) { |
Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 358 | if (slot_data_ != NULL) { |
| 359 | IndirectRefSlot* pSlot = &slot_data_[slot]; |
| 360 | pSlot->serial++; |
| 361 | pSlot->previous[pSlot->serial % kIRTPrevCount] = obj; |
| 362 | } |
| 363 | } |
| 364 | |
| 365 | /* extra debugging checks */ |
| 366 | bool GetChecked(IndirectRef) const; |
| 367 | bool CheckEntry(const char*, IndirectRef, int) const; |
| 368 | |
Ian Rogers | dc51b79 | 2011-09-22 20:41:37 -0700 | [diff] [blame] | 369 | /* semi-public - read/write by jni down calls */ |
| 370 | IRTSegmentState segment_state_; |
Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 371 | |
| 372 | /* bottom of the stack */ |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 373 | const Object** table_; |
Elliott Hughes | 6c1a394 | 2011-08-17 15:00:06 -0700 | [diff] [blame] | 374 | /* bit mask, ORed into all irefs */ |
| 375 | IndirectRefKind kind_; |
| 376 | /* extended debugging info */ |
| 377 | IndirectRefSlot* slot_data_; |
| 378 | /* #of entries we have space for */ |
| 379 | size_t alloc_entries_; |
| 380 | /* max #of entries allowed */ |
| 381 | size_t max_entries_; |
| 382 | }; |
| 383 | |
| 384 | } // namespace art |
| 385 | |
| 386 | #endif // ART_SRC_INDIRECT_REFERENCE_TABLE_H_ |