1 files changed, 381 insertions, 0 deletions
diff --git a/runtime/indirect_reference_table.h b/runtime/indirect_reference_table.h
new file mode 100644
index 0000000000..e09043dba7
--- /dev/null
+++ b/runtime/indirect_reference_table.h
@@ -0,0 +1,381 @@
+/*
+ * Copyright (C) 2009 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_SRC_INDIRECT_REFERENCE_TABLE_H_
+#define ART_SRC_INDIRECT_REFERENCE_TABLE_H_
+
+#include <stdint.h>
+
+#include <iosfwd>
+#include <string>
+
+#include "base/logging.h"
+#include "offsets.h"
+#include "root_visitor.h"
+
+namespace art {
+namespace mirror {
+class Object;
+}  // namespace mirror
+
+/*
+ * 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.
+ *
+ * None of the table functions are 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.
+ */
+typedef void* IndirectRef;
+
+// Magic failure values; must not pass Heap::ValidateObject() or Heap::IsHeapAddress().
+static mirror::Object* const kInvalidIndirectRefObject = reinterpret_cast<mirror::Object*>(0xdead4321);
+static mirror::Object* const kClearedJniWeakGlobal = reinterpret_cast<mirror::Object*>(0xdead1234);
+
+/*
+ * Indirect reference kind, used as the two low bits of IndirectRef.
+ *
+ * For convenience these match up with enum jobjectRefType from jni.h.
+ */
+enum IndirectRefKind {
+  kSirtOrInvalid = 0, // <<stack indirect reference table or invalid reference>>
+  kLocal         = 1, // <<local reference>>
+  kGlobal        = 2, // <<global reference>>
+  kWeakGlobal    = 3  // <<weak global reference>>
+};
+std::ostream& operator<<(std::ostream& os, const IndirectRefKind& rhs);
+
+/*
+ * Determine what kind of indirect reference this is.
+ */
+static inline IndirectRefKind GetIndirectRefKind(IndirectRef iref) {
+  return static_cast<IndirectRefKind>(reinterpret_cast<uintptr_t>(iref) & 0x03);
+}
+
+/*
+ * Extended debugging structure.  We keep a parallel array of these, one
+ * per slot in the table.
+ */
+static const size_t kIRTPrevCount = 4;
+struct IndirectRefSlot {
+  uint32_t serial;
+  const mirror::Object* previous[kIRTPrevCount];
+};
+
+/* 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 "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.
+ *
+ * TODO: if we can guarantee that the underlying storage doesn't move,
+ * e.g. by using oversized mmap regions to handle expanding tables, we may
+ * be able to avoid having to synchronize lookups.  Might make sense to
+ * add a "synchronized lookup" call that takes the mutex as an argument,
+ * and either locks or doesn't lock based on internal details.
+ */
+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;
+};
+
+class IrtIterator {
+ public:
+  explicit IrtIterator(const mirror::Object** table, size_t i, size_t capacity)
+      : table_(table), i_(i), capacity_(capacity) {
+    SkipNullsAndTombstones();
+  }
+
+  IrtIterator& operator++() {
+    ++i_;
+    SkipNullsAndTombstones();
+    return *this;
+  }
+
+  const mirror::Object** operator*() {
+    return &table_[i_];
+  }
+
+  bool equals(const IrtIterator& rhs) const {
+    return (i_ == rhs.i_ && table_ == rhs.table_);
+  }
+
+ private:
+  void SkipNullsAndTombstones() {
+    // We skip NULLs and tombstones. Clients don't want to see implementation details.
+    while (i_ < capacity_ && (table_[i_] == NULL || table_[i_] == kClearedJniWeakGlobal)) {
+      ++i_;
+    }
+  }
+
+  const mirror::Object** table_;
+  size_t i_;
+  size_t capacity_;
+};
+
+bool inline operator==(const IrtIterator& lhs, const IrtIterator& rhs) {
+  return lhs.equals(rhs);
+}
+
+bool inline operator!=(const IrtIterator& lhs, const IrtIterator& rhs) {
+  return !lhs.equals(rhs);
+}
+
+class IndirectReferenceTable {
+ public:
+  typedef IrtIterator iterator;
+
+  IndirectReferenceTable(size_t initialCount, size_t maxCount, IndirectRefKind kind);
+
+  ~IndirectReferenceTable();
+
+  /*
+   * Add a new entry.  "obj" must be a valid non-NULL object reference.
+   *
+   * Returns NULL if the table is full (max entries reached, or alloc
+   * failed during expansion).
+   */
+  IndirectRef Add(uint32_t cookie, const mirror::Object* obj)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
+  /*
+   * Given an IndirectRef in the table, return the Object it refers to.
+   *
+   * Returns kInvalidIndirectRefObject if iref is invalid.
+   */
+  const mirror::Object* Get(IndirectRef iref) const {
+    if (!GetChecked(iref)) {
+      return kInvalidIndirectRefObject;
+    }
+    return table_[ExtractIndex(iref)];
+  }
+
+  // TODO: remove when we remove work_around_app_jni_bugs support.
+  bool ContainsDirectPointer(mirror::Object* direct_pointer) const;
+
+  /*
+   * 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);
+
+  void AssertEmpty();
+
+  void Dump(std::ostream& os) const SHARED_LOCKS_REQUIRED(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.
+   */
+  size_t Capacity() const {
+    return segment_state_.parts.topIndex;
+  }
+
+  iterator begin() {
+    return iterator(table_, 0, Capacity());
+  }
+
+  iterator end() {
+    return iterator(table_, Capacity(), Capacity());
+  }
+
+  void VisitRoots(RootVisitor* visitor, void* arg);
+
+  uint32_t GetSegmentState() const {
+    return segment_state_.all;
+  }
+
+  void SetSegmentState(uint32_t new_state) {
+    segment_state_.all = new_state;
+  }
+
+  static Offset SegmentStateOffset() {
+    return Offset(OFFSETOF_MEMBER(IndirectReferenceTable, segment_state_));
+  }
+
+ private:
+  /*
+   * Extract the table index from an indirect reference.
+   */
+  static uint32_t ExtractIndex(IndirectRef iref) {
+    uint32_t uref = (uint32_t) iref;
+    return (uref >> 2) & 0xffff;
+  }
+
+  /*
+   * The object pointer itself is subject to relocation in some GC
+   * implementations, so we shouldn't really be using it here.
+   */
+  IndirectRef ToIndirectRef(const mirror::Object* /*o*/, uint32_t tableIndex) const {
+    DCHECK_LT(tableIndex, 65536U);
+    uint32_t serialChunk = slot_data_[tableIndex].serial;
+    uint32_t uref = serialChunk << 20 | (tableIndex << 2) | kind_;
+    return (IndirectRef) uref;
+  }
+
+  /*
+   * Update extended debug info when an entry is added.
+   *
+   * We advance the serial number, invalidating any outstanding references to
+   * this slot.
+   */
+  void UpdateSlotAdd(const mirror::Object* obj, int slot) {
+    if (slot_data_ != NULL) {
+      IndirectRefSlot* pSlot = &slot_data_[slot];
+      pSlot->serial++;
+      pSlot->previous[pSlot->serial % kIRTPrevCount] = obj;
+    }
+  }
+
+  /* extra debugging checks */
+  bool GetChecked(IndirectRef) const;
+  bool CheckEntry(const char*, IndirectRef, int) const;
+
+  /* semi-public - read/write by jni down calls */
+  IRTSegmentState segment_state_;
+
+  /* bottom of the stack */
+  const mirror::Object** table_;
+  /* bit mask, ORed into all irefs */
+  IndirectRefKind kind_;
+  /* extended debugging info */
+  IndirectRefSlot* slot_data_;
+  /* #of entries we have space for */
+  size_t alloc_entries_;
+  /* max #of entries allowed */
+  size_t max_entries_;
+};
+
+}  // namespace art
+
+#endif  // ART_SRC_INDIRECT_REFERENCE_TABLE_H_