ART: Change IndirectReferenceTable
Change cookie structure to allow for more entries. Use a local
hole-count caching scheme. The design is driven by two
considerations. For one, the change is small and mostly local.
The other point is to still allow inlining of functions involved
with JNI transitions.
This change is in preparation for a resizable backing table for
"unlimite" local references.
micro_native tests show changes are in the noise.
Bug: 32125344
Test: m test-art-host
Change-Id: I08ff5d6eaed75d13ec88f469fb0d18328a0eeb70
diff --git a/runtime/indirect_reference_table.h b/runtime/indirect_reference_table.h
index c0355de..652fcdf 100644
--- a/runtime/indirect_reference_table.h
+++ b/runtime/indirect_reference_table.h
@@ -20,6 +20,7 @@
#include <stdint.h>
#include <iosfwd>
+#include <limits>
#include <string>
#include "base/bit_utils.h"
@@ -41,79 +42,54 @@
class MemMap;
-/*
- * Maintain a table of indirect references. Used for local/global JNI
- * references.
- *
- * The table contains object references that are part of the GC root set.
- * When an object is added we return an IndirectRef that is not a valid
- * pointer but can be used to find the original value in O(1) time.
- * Conversions to and from indirect references are performed on upcalls
- * and downcalls, so they need to be very fast.
- *
- * To be efficient for JNI local variable storage, we need to provide
- * operations that allow us to operate on segments of the table, where
- * segments are pushed and popped as if on a stack. For example, deletion
- * of an entry should only succeed if it appears in the current segment,
- * and we want to be able to strip off the current segment quickly when
- * a method returns. Additions to the table must be made in the current
- * segment even if space is available in an earlier area.
- *
- * A new segment is created when we call into native code from interpreted
- * code, or when we handle the JNI PushLocalFrame function.
- *
- * The GC must be able to scan the entire table quickly.
- *
- * In summary, these must be very fast:
- * - adding or removing a segment
- * - adding references to a new segment
- * - converting an indirect reference back to an Object
- * These can be a little slower, but must still be pretty quick:
- * - adding references to a "mature" segment
- * - removing individual references
- * - scanning the entire table straight through
- *
- * If there's more than one segment, we don't guarantee that the table
- * will fill completely before we fail due to lack of space. We do ensure
- * that the current segment will pack tightly, which should satisfy JNI
- * requirements (e.g. EnsureLocalCapacity).
- *
- * To make everything fit nicely in 32-bit integers, the maximum size of
- * the table is capped at 64K.
- *
- * Only SynchronizedGet is synchronized.
- */
+// Maintain a table of indirect references. Used for local/global JNI references.
+//
+// The table contains object references, where the strong (local/global) references are part of the
+// GC root set (but not the weak global references). When an object is added we return an
+// IndirectRef that is not a valid pointer but can be used to find the original value in O(1) time.
+// Conversions to and from indirect references are performed on upcalls and downcalls, so they need
+// to be very fast.
+//
+// To be efficient for JNI local variable storage, we need to provide operations that allow us to
+// operate on segments of the table, where segments are pushed and popped as if on a stack. For
+// example, deletion of an entry should only succeed if it appears in the current segment, and we
+// want to be able to strip off the current segment quickly when a method returns. Additions to the
+// table must be made in the current segment even if space is available in an earlier area.
+//
+// A new segment is created when we call into native code from interpreted code, or when we handle
+// the JNI PushLocalFrame function.
+//
+// The GC must be able to scan the entire table quickly.
+//
+// In summary, these must be very fast:
+// - adding or removing a segment
+// - adding references to a new segment
+// - converting an indirect reference back to an Object
+// These can be a little slower, but must still be pretty quick:
+// - adding references to a "mature" segment
+// - removing individual references
+// - scanning the entire table straight through
+//
+// If there's more than one segment, we don't guarantee that the table will fill completely before
+// we fail due to lack of space. We do ensure that the current segment will pack tightly, which
+// should satisfy JNI requirements (e.g. EnsureLocalCapacity).
+//
+// Only SynchronizedGet is synchronized.
-/*
- * Indirect reference definition. This must be interchangeable with JNI's
- * jobject, and it's convenient to let null be null, so we use void*.
- *
- * We need a 16-bit table index and a 2-bit reference type (global, local,
- * weak global). Real object pointers will have zeroes in the low 2 or 3
- * bits (4- or 8-byte alignment), so it's useful to put the ref type
- * in the low bits and reserve zero as an invalid value.
- *
- * The remaining 14 bits can be used to detect stale indirect references.
- * For example, if objects don't move, we can use a hash of the original
- * Object* to make sure the entry hasn't been re-used. (If the Object*
- * we find there doesn't match because of heap movement, we could do a
- * secondary check on the preserved hash value; this implies that creating
- * a global/local ref queries the hash value and forces it to be saved.)
- *
- * A more rigorous approach would be to put a serial number in the extra
- * bits, and keep a copy of the serial number in a parallel table. This is
- * easier when objects can move, but requires 2x the memory and additional
- * memory accesses on add/get. It will catch additional problems, e.g.:
- * create iref1 for obj, delete iref1, create iref2 for same obj, lookup
- * iref1. A pattern based on object bits will miss this.
- */
+// Indirect reference definition. This must be interchangeable with JNI's jobject, and it's
+// convenient to let null be null, so we use void*.
+//
+// We need a (potentially) large table index and a 2-bit reference type (global, local, weak
+// global). We also reserve some bits to be used to detect stale indirect references: we put a
+// serial number in the extra bits, and keep a copy of the serial number in the table. This requires
+// more memory and additional memory accesses on add/get, but is moving-GC safe. It will catch
+// additional problems, e.g.: create iref1 for obj, delete iref1, create iref2 for same obj,
+// lookup iref1. A pattern based on object bits will miss this.
typedef void* IndirectRef;
-/*
- * Indirect reference kind, used as the two low bits of IndirectRef.
- *
- * For convenience these match up with enum jobjectRefType from jni.h.
- */
+// Indirect reference kind, used as the two low bits of IndirectRef.
+//
+// For convenience these match up with enum jobjectRefType from jni.h.
enum IndirectRefKind {
kHandleScopeOrInvalid = 0, // <<stack indirect reference table or invalid reference>>
kLocal = 1, // <<local reference>>
@@ -124,72 +100,55 @@
std::ostream& operator<<(std::ostream& os, const IndirectRefKind& rhs);
const char* GetIndirectRefKindString(const IndirectRefKind& kind);
-/* use as initial value for "cookie", and when table has only one segment */
-static const uint32_t IRT_FIRST_SEGMENT = 0;
+// Table definition.
+//
+// For the global reference table, the expected common operations are adding a new entry and
+// removing a recently-added entry (usually the most-recently-added entry). For JNI local
+// references, the common operations are adding a new entry and removing an entire table segment.
+//
+// If we delete entries from the middle of the list, we will be left with "holes". We track the
+// number of holes so that, when adding new elements, we can quickly decide to do a trivial append
+// or go slot-hunting.
+//
+// When the top-most entry is removed, any holes immediately below it are also removed. Thus,
+// deletion of an entry may reduce "top_index" by more than one.
+//
+// To get the desired behavior for JNI locals, we need to know the bottom and top of the current
+// "segment". The top is managed internally, and the bottom is passed in as a function argument.
+// When we call a native method or push a local frame, the current top index gets pushed on, and
+// serves as the new bottom. When we pop a frame off, the value from the stack becomes the new top
+// index, and the value stored in the previous frame becomes the new bottom.
+//
+// Holes are being locally cached for the segment. Otherwise we'd have to pass bottom index and
+// number of holes, which restricts us to 16 bits for the top index. The value is cached within the
+// table. To avoid code in generated JNI transitions, which implicitly form segments, the code for
+// adding and removing references needs to detect the change of a segment. Helper fields are used
+// for this detection.
+//
+// Common alternative implementation: make IndirectRef a pointer to the actual reference slot.
+// Instead of getting a table and doing a lookup, the lookup can be done instantly. Operations like
+// determining the type and deleting the reference are more expensive because the table must be
+// hunted for (i.e. you have to do a pointer comparison to see which table it's in), you can't move
+// the table when expanding it (so realloc() is out), and tricks like serial number checking to
+// detect stale references aren't possible (though we may be able to get similar benefits with other
+// approaches).
+//
+// TODO: consider a "lastDeleteIndex" for quick hole-filling when an add immediately follows a
+// delete; must invalidate after segment pop might be worth only using it for JNI globals.
+//
+// TODO: may want completely different add/remove algorithms for global and local refs to improve
+// performance. A large circular buffer might reduce the amortized cost of adding global
+// references.
-/*
- * Table definition.
- *
- * For the global reference table, the expected common operations are
- * adding a new entry and removing a recently-added entry (usually the
- * most-recently-added entry). For JNI local references, the common
- * operations are adding a new entry and removing an entire table segment.
- *
- * If "alloc_entries_" is not equal to "max_entries_", the table may expand
- * when entries are added, which means the memory may move. If you want
- * to keep pointers into "table" rather than offsets, you must use a
- * fixed-size table.
- *
- * If we delete entries from the middle of the list, we will be left with
- * "holes". We track the number of holes so that, when adding new elements,
- * we can quickly decide to do a trivial append or go slot-hunting.
- *
- * When the top-most entry is removed, any holes immediately below it are
- * also removed. Thus, deletion of an entry may reduce "topIndex" by more
- * than one.
- *
- * To get the desired behavior for JNI locals, we need to know the bottom
- * and top of the current "segment". The top is managed internally, and
- * the bottom is passed in as a function argument. When we call a native method or
- * push a local frame, the current top index gets pushed on, and serves
- * as the new bottom. When we pop a frame off, the value from the stack
- * becomes the new top index, and the value stored in the previous frame
- * becomes the new bottom.
- *
- * To avoid having to re-scan the table after a pop, we want to push the
- * number of holes in the table onto the stack. Because of our 64K-entry
- * cap, we can combine the two into a single unsigned 32-bit value.
- * Instead of a "bottom" argument we take a "cookie", which includes the
- * bottom index and the count of holes below the bottom.
- *
- * Common alternative implementation: make IndirectRef a pointer to the
- * actual reference slot. Instead of getting a table and doing a lookup,
- * the lookup can be done instantly. Operations like determining the
- * type and deleting the reference are more expensive because the table
- * must be hunted for (i.e. you have to do a pointer comparison to see
- * which table it's in), you can't move the table when expanding it (so
- * realloc() is out), and tricks like serial number checking to detect
- * stale references aren't possible (though we may be able to get similar
- * benefits with other approaches).
- *
- * TODO: consider a "lastDeleteIndex" for quick hole-filling when an
- * add immediately follows a delete; must invalidate after segment pop
- * (which could increase the cost/complexity of method call/return).
- * Might be worth only using it for JNI globals.
- *
- * TODO: may want completely different add/remove algorithms for global
- * and local refs to improve performance. A large circular buffer might
- * reduce the amortized cost of adding global references.
- *
- */
-union IRTSegmentState {
- uint32_t all;
- struct {
- uint32_t topIndex:16; /* index of first unused entry */
- uint32_t numHoles:16; /* #of holes in entire table */
- } parts;
+// The state of the current segment. We only store the index. Splitting it for index and hole
+// count restricts the range too much.
+struct IRTSegmentState {
+ uint32_t top_index;
};
+// Use as initial value for "cookie", and when table has only one segment.
+static constexpr IRTSegmentState kIRTFirstSegment = { 0 };
+
// Try to choose kIRTPrevCount so that sizeof(IrtEntry) is a power of 2.
// Contains multiple entries but only one active one, this helps us detect use after free errors
// since the serial stored in the indirect ref wont match.
@@ -204,6 +163,11 @@
return &references_[serial_];
}
+ const GcRoot<mirror::Object>* GetReference() const {
+ DCHECK_LT(serial_, kIRTPrevCount);
+ return &references_[serial_];
+ }
+
uint32_t GetSerial() const {
return serial_;
}
@@ -254,13 +218,11 @@
class IndirectReferenceTable {
public:
- /*
- * WARNING: Construction of the IndirectReferenceTable may fail.
- * error_msg must not be null. If error_msg is set by the constructor, then
- * construction has failed and the IndirectReferenceTable will be in an
- * invalid state. Use IsValid to check whether the object is in an invalid
- * state.
- */
+ // WARNING: Construction of the IndirectReferenceTable may fail.
+ // error_msg must not be null. If error_msg is set by the constructor, then
+ // construction has failed and the IndirectReferenceTable will be in an
+ // invalid state. Use IsValid to check whether the object is in an invalid
+ // state.
IndirectReferenceTable(size_t max_count, IndirectRefKind kind, std::string* error_msg);
~IndirectReferenceTable();
@@ -274,20 +236,14 @@
*/
bool IsValid() const;
- /*
- * Add a new entry. "obj" must be a valid non-nullptr object reference.
- *
- * Returns nullptr if the table is full (max entries reached, or alloc
- * failed during expansion).
- */
- IndirectRef Add(uint32_t cookie, ObjPtr<mirror::Object> obj)
+ // Add a new entry. "obj" must be a valid non-null object reference. This function will
+ // abort if the table is full (max entries reached, or expansion failed).
+ IndirectRef Add(IRTSegmentState previous_state, ObjPtr<mirror::Object> obj)
REQUIRES_SHARED(Locks::mutator_lock_);
- /*
- * Given an IndirectRef in the table, return the Object it refers to.
- *
- * Returns kInvalidIndirectRefObject if iref is invalid.
- */
+ // Given an IndirectRef in the table, return the Object it refers to.
+ //
+ // This function may abort under error conditions.
template<ReadBarrierOption kReadBarrierOption = kWithReadBarrier>
ObjPtr<mirror::Object> Get(IndirectRef iref) const REQUIRES_SHARED(Locks::mutator_lock_)
ALWAYS_INLINE;
@@ -299,34 +255,26 @@
return Get<kReadBarrierOption>(iref);
}
- /*
- * Update an existing entry.
- *
- * Updates an existing indirect reference to point to a new object.
- */
+ // Updates an existing indirect reference to point to a new object.
void Update(IndirectRef iref, ObjPtr<mirror::Object> obj) REQUIRES_SHARED(Locks::mutator_lock_);
- /*
- * Remove an existing entry.
- *
- * If the entry is not between the current top index and the bottom index
- * specified by the cookie, we don't remove anything. This is the behavior
- * required by JNI's DeleteLocalRef function.
- *
- * Returns "false" if nothing was removed.
- */
- bool Remove(uint32_t cookie, IndirectRef iref);
+ // Remove an existing entry.
+ //
+ // If the entry is not between the current top index and the bottom index
+ // specified by the cookie, we don't remove anything. This is the behavior
+ // required by JNI's DeleteLocalRef function.
+ //
+ // Returns "false" if nothing was removed.
+ bool Remove(IRTSegmentState previous_state, IndirectRef iref);
void AssertEmpty() REQUIRES_SHARED(Locks::mutator_lock_);
void Dump(std::ostream& os) const REQUIRES_SHARED(Locks::mutator_lock_);
- /*
- * Return the #of entries in the entire table. This includes holes, and
- * so may be larger than the actual number of "live" entries.
- */
+ // Return the #of entries in the entire table. This includes holes, and
+ // so may be larger than the actual number of "live" entries.
size_t Capacity() const {
- return segment_state_.parts.topIndex;
+ return segment_state_.top_index;
}
// Note IrtIterator does not have a read barrier as it's used to visit roots.
@@ -341,13 +289,11 @@
void VisitRoots(RootVisitor* visitor, const RootInfo& root_info)
REQUIRES_SHARED(Locks::mutator_lock_);
- uint32_t GetSegmentState() const {
- return segment_state_.all;
+ IRTSegmentState GetSegmentState() const {
+ return segment_state_;
}
- void SetSegmentState(uint32_t new_state) {
- segment_state_.all = new_state;
- }
+ void SetSegmentState(IRTSegmentState new_state);
static Offset SegmentStateOffset(size_t pointer_size ATTRIBUTE_UNUSED) {
// Note: Currently segment_state_ is at offset 0. We're testing the expected value in
@@ -414,14 +360,19 @@
return reinterpret_cast<IndirectRef>(EncodeIndirectRef(table_index, serial));
}
+ // Resize the backing table. Currently must be larger than the current size.
+ bool Resize(size_t new_size, std::string* error_msg);
+
+ void RecoverHoles(IRTSegmentState from);
+
// Abort if check_jni is not enabled. Otherwise, just log as an error.
static void AbortIfNoCheckJNI(const std::string& msg);
/* extra debugging checks */
bool GetChecked(IndirectRef) const REQUIRES_SHARED(Locks::mutator_lock_);
- bool CheckEntry(const char*, IndirectRef, int) const;
+ bool CheckEntry(const char*, IndirectRef, uint32_t) const;
- /* semi-public - read/write by jni down calls */
+ /// semi-public - read/write by jni down calls.
IRTSegmentState segment_state_;
// Mem map where we store the indirect refs.
@@ -429,10 +380,17 @@
// bottom of the stack. Do not directly access the object references
// in this as they are roots. Use Get() that has a read barrier.
IrtEntry* table_;
- /* bit mask, ORed into all irefs */
+ // bit mask, ORed into all irefs.
const IndirectRefKind kind_;
- /* max #of entries allowed */
- const size_t max_entries_;
+
+ // max #of entries allowed.
+ size_t max_entries_;
+
+ // Some values to retain old behavior with holes. Description of the algorithm is in the .cc
+ // file.
+ // TODO: Consider other data structures for compact tables, e.g., free lists.
+ size_t current_num_holes_;
+ IRTSegmentState last_known_previous_state_;
};
} // namespace art