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 <limits>
24 #include <string>
25 
26 #include <android-base/logging.h>
27 
28 #include "base/bit_utils.h"
29 #include "base/locks.h"
30 #include "base/macros.h"
31 #include "base/mem_map.h"
32 #include "gc_root.h"
33 #include "obj_ptr.h"
34 #include "offsets.h"
35 #include "read_barrier_option.h"
36 
37 namespace art {
38 
39 class RootInfo;
40 
41 namespace mirror {
42 class Object;
43 }  // namespace mirror
44 
45 // Maintain a table of indirect references.  Used for local/global JNI references.
46 //
47 // The table contains object references, where the strong (local/global) references are part of the
48 // GC root set (but not the weak global references). When an object is added we return an
49 // IndirectRef that is not a valid pointer but can be used to find the original value in O(1) time.
50 // Conversions to and from indirect references are performed on upcalls and downcalls, so they need
51 // to be very fast.
52 //
53 // To be efficient for JNI local variable storage, we need to provide operations that allow us to
54 // operate on segments of the table, where segments are pushed and popped as if on a stack. For
55 // example, deletion of an entry should only succeed if it appears in the current segment, and we
56 // want to be able to strip off the current segment quickly when a method returns. Additions to the
57 // table must be made in the current segment even if space is available in an earlier area.
58 //
59 // A new segment is created when we call into native code from interpreted code, or when we handle
60 // the JNI PushLocalFrame function.
61 //
62 // The GC must be able to scan the entire table quickly.
63 //
64 // In summary, these must be very fast:
65 //  - adding or removing a segment
66 //  - adding references to a new segment
67 //  - converting an indirect reference back to an Object
68 // These can be a little slower, but must still be pretty quick:
69 //  - adding references to a "mature" segment
70 //  - removing individual references
71 //  - scanning the entire table straight through
72 //
73 // If there's more than one segment, we don't guarantee that the table will fill completely before
74 // we fail due to lack of space. We do ensure that the current segment will pack tightly, which
75 // should satisfy JNI requirements (e.g. EnsureLocalCapacity).
76 //
77 // Only SynchronizedGet is synchronized.
78 
79 // Indirect reference definition.  This must be interchangeable with JNI's jobject, and it's
80 // convenient to let null be null, so we use void*.
81 //
82 // We need a (potentially) large table index and a 2-bit reference type (global, local, weak
83 // global). We also reserve some bits to be used to detect stale indirect references: we put a
84 // serial number in the extra bits, and keep a copy of the serial number in the table. This requires
85 // more memory and additional memory accesses on add/get, but is moving-GC safe. It will catch
86 // additional problems, e.g.: create iref1 for obj, delete iref1, create iref2 for same obj,
87 // lookup iref1. A pattern based on object bits will miss this.
88 typedef void* IndirectRef;
89 
90 // Indirect reference kind, used as the two low bits of IndirectRef.
91 //
92 // For convenience these match up with enum jobjectRefType from jni.h.
93 enum IndirectRefKind {
94   kJniTransitionOrInvalid = 0,  // <<JNI transition frame reference or invalid reference>>
95   kLocal                  = 1,  // <<local reference>>
96   kGlobal                 = 2,  // <<global reference>>
97   kWeakGlobal             = 3,  // <<weak global reference>>
98   kLastKind               = kWeakGlobal
99 };
100 std::ostream& operator<<(std::ostream& os, IndirectRefKind rhs);
101 const char* GetIndirectRefKindString(const IndirectRefKind& kind);
102 
103 // Table definition.
104 //
105 // For the global reference table, the expected common operations are adding a new entry and
106 // removing a recently-added entry (usually the most-recently-added entry).  For JNI local
107 // references, the common operations are adding a new entry and removing an entire table segment.
108 //
109 // If we delete entries from the middle of the list, we will be left with "holes".  We track the
110 // number of holes so that, when adding new elements, we can quickly decide to do a trivial append
111 // or go slot-hunting.
112 //
113 // When the top-most entry is removed, any holes immediately below it are also removed. Thus,
114 // deletion of an entry may reduce "top_index" by more than one.
115 //
116 // To get the desired behavior for JNI locals, we need to know the bottom and top of the current
117 // "segment". The top is managed internally, and the bottom is passed in as a function argument.
118 // When we call a native method or push a local frame, the current top index gets pushed on, and
119 // serves as the new bottom. When we pop a frame off, the value from the stack becomes the new top
120 // index, and the value stored in the previous frame becomes the new bottom.
121 //
122 // Holes are being locally cached for the segment. Otherwise we'd have to pass bottom index and
123 // number of holes, which restricts us to 16 bits for the top index. The value is cached within the
124 // table. To avoid code in generated JNI transitions, which implicitly form segments, the code for
125 // adding and removing references needs to detect the change of a segment. Helper fields are used
126 // for this detection.
127 //
128 // Common alternative implementation: make IndirectRef a pointer to the actual reference slot.
129 // Instead of getting a table and doing a lookup, the lookup can be done instantly. Operations like
130 // determining the type and deleting the reference are more expensive because the table must be
131 // hunted for (i.e. you have to do a pointer comparison to see which table it's in), you can't move
132 // the table when expanding it (so realloc() is out), and tricks like serial number checking to
133 // detect stale references aren't possible (though we may be able to get similar benefits with other
134 // approaches).
135 //
136 // TODO: consider a "lastDeleteIndex" for quick hole-filling when an add immediately follows a
137 // delete; must invalidate after segment pop might be worth only using it for JNI globals.
138 //
139 // TODO: may want completely different add/remove algorithms for global and local refs to improve
140 // performance.  A large circular buffer might reduce the amortized cost of adding global
141 // references.
142 
143 // The state of the current segment. We only store the index. Splitting it for index and hole
144 // count restricts the range too much.
145 struct IRTSegmentState {
146   uint32_t top_index;
147 };
148 
149 // Use as initial value for "cookie", and when table has only one segment.
150 static constexpr IRTSegmentState kIRTFirstSegment = { 0 };
151 
152 // Try to choose kIRTPrevCount so that sizeof(IrtEntry) is a power of 2.
153 // Contains multiple entries but only one active one, this helps us detect use after free errors
154 // since the serial stored in the indirect ref wont match.
155 static constexpr size_t kIRTPrevCount = kIsDebugBuild ? 7 : 3;
156 
157 class IrtEntry {
158  public:
159   void Add(ObjPtr<mirror::Object> obj) REQUIRES_SHARED(Locks::mutator_lock_);
160 
GetReference()161   GcRoot<mirror::Object>* GetReference() {
162     DCHECK_LT(serial_, kIRTPrevCount);
163     return &references_[serial_];
164   }
165 
GetReference()166   const GcRoot<mirror::Object>* GetReference() const {
167     DCHECK_LT(serial_, kIRTPrevCount);
168     return &references_[serial_];
169   }
170 
GetSerial()171   uint32_t GetSerial() const {
172     return serial_;
173   }
174 
175   void SetReference(ObjPtr<mirror::Object> obj) REQUIRES_SHARED(Locks::mutator_lock_);
176 
177  private:
178   uint32_t serial_;
179   GcRoot<mirror::Object> references_[kIRTPrevCount];
180 };
181 static_assert(sizeof(IrtEntry) == (1 + kIRTPrevCount) * sizeof(uint32_t),
182               "Unexpected sizeof(IrtEntry)");
183 static_assert(IsPowerOfTwo(sizeof(IrtEntry)), "Unexpected sizeof(IrtEntry)");
184 
185 class IrtIterator {
186  public:
IrtIterator(IrtEntry * table,size_t i,size_t capacity)187   IrtIterator(IrtEntry* table, size_t i, size_t capacity) REQUIRES_SHARED(Locks::mutator_lock_)
188       : table_(table), i_(i), capacity_(capacity) {
189     // capacity_ is used in some target; has warning with unused attribute.
190     UNUSED(capacity_);
191   }
192 
193   IrtIterator& operator++() REQUIRES_SHARED(Locks::mutator_lock_) {
194     ++i_;
195     return *this;
196   }
197 
REQUIRES_SHARED(Locks::mutator_lock_)198   GcRoot<mirror::Object>* operator*() REQUIRES_SHARED(Locks::mutator_lock_) {
199     // This does not have a read barrier as this is used to visit roots.
200     return table_[i_].GetReference();
201   }
202 
equals(const IrtIterator & rhs)203   bool equals(const IrtIterator& rhs) const {
204     return (i_ == rhs.i_ && table_ == rhs.table_);
205   }
206 
207  private:
208   IrtEntry* const table_;
209   size_t i_;
210   const size_t capacity_;
211 };
212 
213 bool inline operator==(const IrtIterator& lhs, const IrtIterator& rhs) {
214   return lhs.equals(rhs);
215 }
216 
217 bool inline operator!=(const IrtIterator& lhs, const IrtIterator& rhs) {
218   return !lhs.equals(rhs);
219 }
220 
221 class IndirectReferenceTable {
222  public:
223   enum class ResizableCapacity {
224     kNo,
225     kYes
226   };
227 
228   // WARNING: Construction of the IndirectReferenceTable may fail.
229   // error_msg must not be null. If error_msg is set by the constructor, then
230   // construction has failed and the IndirectReferenceTable will be in an
231   // invalid state. Use IsValid to check whether the object is in an invalid
232   // state.
233   IndirectReferenceTable(size_t max_count,
234                          IndirectRefKind kind,
235                          ResizableCapacity resizable,
236                          std::string* error_msg);
237 
238   ~IndirectReferenceTable();
239 
240   /*
241    * Checks whether construction of the IndirectReferenceTable succeeded.
242    *
243    * This object must only be used if IsValid() returns true. It is safe to
244    * call IsValid from multiple threads without locking or other explicit
245    * synchronization.
246    */
247   bool IsValid() const;
248 
249   // Add a new entry. "obj" must be a valid non-null object reference. This function will
250   // return null if an error happened (with an appropriate error message set).
251   IndirectRef Add(IRTSegmentState previous_state,
252                   ObjPtr<mirror::Object> obj,
253                   std::string* error_msg)
254       REQUIRES_SHARED(Locks::mutator_lock_);
255 
256   // Given an IndirectRef in the table, return the Object it refers to.
257   //
258   // This function may abort under error conditions.
259   template<ReadBarrierOption kReadBarrierOption = kWithReadBarrier>
260   ObjPtr<mirror::Object> Get(IndirectRef iref) const REQUIRES_SHARED(Locks::mutator_lock_)
261       ALWAYS_INLINE;
262 
263   // Synchronized get which reads a reference, acquiring a lock if necessary.
264   template<ReadBarrierOption kReadBarrierOption = kWithReadBarrier>
SynchronizedGet(IndirectRef iref)265   ObjPtr<mirror::Object> SynchronizedGet(IndirectRef iref) const
266       REQUIRES_SHARED(Locks::mutator_lock_) {
267     return Get<kReadBarrierOption>(iref);
268   }
269 
270   // Updates an existing indirect reference to point to a new object.
271   void Update(IndirectRef iref, ObjPtr<mirror::Object> obj) REQUIRES_SHARED(Locks::mutator_lock_);
272 
273   // Remove an existing entry.
274   //
275   // If the entry is not between the current top index and the bottom index
276   // specified by the cookie, we don't remove anything.  This is the behavior
277   // required by JNI's DeleteLocalRef function.
278   //
279   // Returns "false" if nothing was removed.
280   bool Remove(IRTSegmentState previous_state, IndirectRef iref);
281 
282   void AssertEmpty() REQUIRES_SHARED(Locks::mutator_lock_);
283 
284   void Dump(std::ostream& os) const
285       REQUIRES_SHARED(Locks::mutator_lock_)
286       REQUIRES(!Locks::alloc_tracker_lock_);
287 
GetKind()288   IndirectRefKind GetKind() const {
289     return kind_;
290   }
291 
292   // Return the #of entries in the entire table.  This includes holes, and
293   // so may be larger than the actual number of "live" entries.
Capacity()294   size_t Capacity() const {
295     return segment_state_.top_index;
296   }
297 
298   // Ensure that at least free_capacity elements are available, or return false.
299   bool EnsureFreeCapacity(size_t free_capacity, std::string* error_msg)
300       REQUIRES_SHARED(Locks::mutator_lock_);
301   // See implementation of EnsureFreeCapacity. We'll only state here how much is trivially free,
302   // without recovering holes. Thus this is a conservative estimate.
303   size_t FreeCapacity() const;
304 
305   // Note IrtIterator does not have a read barrier as it's used to visit roots.
begin()306   IrtIterator begin() {
307     return IrtIterator(table_, 0, Capacity());
308   }
309 
end()310   IrtIterator end() {
311     return IrtIterator(table_, Capacity(), Capacity());
312   }
313 
314   void VisitRoots(RootVisitor* visitor, const RootInfo& root_info)
315       REQUIRES_SHARED(Locks::mutator_lock_);
316 
GetSegmentState()317   IRTSegmentState GetSegmentState() const {
318     return segment_state_;
319   }
320 
321   void SetSegmentState(IRTSegmentState new_state);
322 
SegmentStateOffset(size_t pointer_size ATTRIBUTE_UNUSED)323   static Offset SegmentStateOffset(size_t pointer_size ATTRIBUTE_UNUSED) {
324     // Note: Currently segment_state_ is at offset 0. We're testing the expected value in
325     //       jni_internal_test to make sure it stays correct. It is not OFFSETOF_MEMBER, as that
326     //       is not pointer-size-safe.
327     return Offset(0);
328   }
329 
330   // Release pages past the end of the table that may have previously held references.
331   void Trim() REQUIRES_SHARED(Locks::mutator_lock_);
332 
333   // Determine what kind of indirect reference this is. Opposite of EncodeIndirectRefKind.
GetIndirectRefKind(IndirectRef iref)334   ALWAYS_INLINE static inline IndirectRefKind GetIndirectRefKind(IndirectRef iref) {
335     return DecodeIndirectRefKind(reinterpret_cast<uintptr_t>(iref));
336   }
337 
338   /* Reference validation for CheckJNI. */
339   bool IsValidReference(IndirectRef, /*out*/std::string* error_msg) const
340       REQUIRES_SHARED(Locks::mutator_lock_);
341 
342  private:
343   static constexpr size_t kSerialBits = MinimumBitsToStore(kIRTPrevCount);
344   static constexpr uint32_t kShiftedSerialMask = (1u << kSerialBits) - 1;
345 
346   static constexpr size_t kKindBits = MinimumBitsToStore(
347       static_cast<uint32_t>(IndirectRefKind::kLastKind));
348   static constexpr uint32_t kKindMask = (1u << kKindBits) - 1;
349 
EncodeIndex(uint32_t table_index)350   static constexpr uintptr_t EncodeIndex(uint32_t table_index) {
351     static_assert(sizeof(IndirectRef) == sizeof(uintptr_t), "Unexpected IndirectRef size");
352     DCHECK_LE(MinimumBitsToStore(table_index), BitSizeOf<uintptr_t>() - kSerialBits - kKindBits);
353     return (static_cast<uintptr_t>(table_index) << kKindBits << kSerialBits);
354   }
DecodeIndex(uintptr_t uref)355   static constexpr uint32_t DecodeIndex(uintptr_t uref) {
356     return static_cast<uint32_t>((uref >> kKindBits) >> kSerialBits);
357   }
358 
EncodeIndirectRefKind(IndirectRefKind kind)359   static constexpr uintptr_t EncodeIndirectRefKind(IndirectRefKind kind) {
360     return static_cast<uintptr_t>(kind);
361   }
DecodeIndirectRefKind(uintptr_t uref)362   static constexpr IndirectRefKind DecodeIndirectRefKind(uintptr_t uref) {
363     return static_cast<IndirectRefKind>(uref & kKindMask);
364   }
365 
EncodeSerial(uint32_t serial)366   static constexpr uintptr_t EncodeSerial(uint32_t serial) {
367     DCHECK_LE(MinimumBitsToStore(serial), kSerialBits);
368     return serial << kKindBits;
369   }
DecodeSerial(uintptr_t uref)370   static constexpr uint32_t DecodeSerial(uintptr_t uref) {
371     return static_cast<uint32_t>(uref >> kKindBits) & kShiftedSerialMask;
372   }
373 
EncodeIndirectRef(uint32_t table_index,uint32_t serial)374   constexpr uintptr_t EncodeIndirectRef(uint32_t table_index, uint32_t serial) const {
375     DCHECK_LT(table_index, max_entries_);
376     return EncodeIndex(table_index) | EncodeSerial(serial) | EncodeIndirectRefKind(kind_);
377   }
378 
379   static void ConstexprChecks();
380 
381   // Extract the table index from an indirect reference.
ExtractIndex(IndirectRef iref)382   ALWAYS_INLINE static uint32_t ExtractIndex(IndirectRef iref) {
383     return DecodeIndex(reinterpret_cast<uintptr_t>(iref));
384   }
385 
ToIndirectRef(uint32_t table_index)386   IndirectRef ToIndirectRef(uint32_t table_index) const {
387     DCHECK_LT(table_index, max_entries_);
388     uint32_t serial = table_[table_index].GetSerial();
389     return reinterpret_cast<IndirectRef>(EncodeIndirectRef(table_index, serial));
390   }
391 
392   // Resize the backing table to be at least new_size elements long. Currently
393   // must be larger than the current size. After return max_entries_ >= new_size.
394   bool Resize(size_t new_size, std::string* error_msg);
395 
396   void RecoverHoles(IRTSegmentState from);
397 
398   // Abort if check_jni is not enabled. Otherwise, just log as an error.
399   static void AbortIfNoCheckJNI(const std::string& msg);
400 
401   /* extra debugging checks */
402   bool CheckEntry(const char*, IndirectRef, uint32_t) const;
403 
404   /// semi-public - read/write by jni down calls.
405   IRTSegmentState segment_state_;
406 
407   // Mem map where we store the indirect refs.
408   MemMap table_mem_map_;
409   // bottom of the stack. Do not directly access the object references
410   // in this as they are roots. Use Get() that has a read barrier.
411   IrtEntry* table_;
412   // bit mask, ORed into all irefs.
413   const IndirectRefKind kind_;
414 
415   // max #of entries allowed (modulo resizing).
416   size_t max_entries_;
417 
418   // Some values to retain old behavior with holes. Description of the algorithm is in the .cc
419   // file.
420   // TODO: Consider other data structures for compact tables, e.g., free lists.
421   size_t current_num_holes_;
422   IRTSegmentState last_known_previous_state_;
423 
424   // Whether the table's capacity may be resized. As there are no locks used, it is the caller's
425   // responsibility to ensure thread-safety.
426   ResizableCapacity resizable_;
427 };
428 
429 }  // namespace art
430 
431 #endif  // ART_RUNTIME_INDIRECT_REFERENCE_TABLE_H_
432