Add IndirectReferenceTable and initialize all the instances.

We're not _using_ any of the tables yet (except in tests), but all the
reference tables are now in place.

Change-Id: Ifd3fc114254460b4a1302520f2a4653319b113e5

8 files changed, 929 insertions, 18 deletions

diff --git a/build/Android.common.mk b/build/Android.common.mk
index ae276f591c..fd0acf2546 100644
--- a/build/Android.common.mk
+++ b/build/Android.common.mk
@@ -44,6 +44,7 @@ LIBART_COMMON_SRC_FILES := \
 	src/file_linux.cc \
 	src/heap.cc \
 	src/image_writer.cc \
+	src/indirect_reference_table.cc \
 	src/intern_table.cc \
 	src/jni_compiler.cc \
 	src/jni_internal.cc \
@@ -95,6 +96,7 @@ TEST_COMMON_SRC_FILES := \
 	src/exception_test.cc \
 	src/file_test.cc \
 	src/image_test.cc \
+	src/indirect_reference_table_test.cc \
 	src/intern_table_test.cc \
 	src/jni_internal_test.cc.arm \
 	src/jni_compiler_test.cc.arm \
diff --git a/src/indirect_reference_table.cc b/src/indirect_reference_table.cc
new file mode 100644
index 0000000000..20f39b6d5d
--- /dev/null
+++ b/src/indirect_reference_table.cc
@@ -0,0 +1,323 @@
+/*
+ * 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.
+ */
+
+#include "indirect_reference_table.h"
+#include "reference_table.h"
+
+#include <cstdlib>
+
+namespace art {
+
+// TODO: implement this for art. (only needed for non-CheckJNI operation.)
+static void AbortMaybe() {
+  // If CheckJNI is on, it'll give a more detailed error before aborting.
+  // Otherwise, we want to abort rather than hand back a bad reference.
+//  if (!gDvmJni.useCheckJni) {
+//    LOG(FATAL) << "bye!";
+//  }
+}
+
+IndirectReferenceTable::IndirectReferenceTable(size_t initialCount,
+    size_t maxCount, IndirectRefKind desiredKind)
+{
+  CHECK_GT(initialCount, 0U);
+  CHECK_LE(initialCount, maxCount);
+  CHECK_NE(desiredKind, kInvalid);
+
+  table_ = reinterpret_cast<Object**>(malloc(initialCount * sizeof(Object*)));
+  CHECK(table_ != NULL);
+#ifndef NDEBUG
+  memset(table_, 0xd1, initialCount * sizeof(Object*));
+#endif
+
+  slot_data_ = reinterpret_cast<IndirectRefSlot*>(calloc(initialCount, sizeof(IndirectRefSlot)));
+  CHECK(slot_data_ != NULL);
+
+  segmentState.all = IRT_FIRST_SEGMENT;
+  alloc_entries_ = initialCount;
+  max_entries_ = maxCount;
+  kind_ = desiredKind;
+}
+
+IndirectReferenceTable::~IndirectReferenceTable() {
+  free(table_);
+  free(slot_data_);
+  table_ = NULL;
+  slot_data_ = NULL;
+  alloc_entries_ = max_entries_ = -1;
+}
+
+/*
+ * Make sure that the entry at "idx" is correctly paired with "iref".
+ */
+bool IndirectReferenceTable::CheckEntry(const char* what, IndirectRef iref, int idx) const {
+  Object* obj = table_[idx];
+  IndirectRef checkRef = ToIndirectRef(obj, idx);
+  if (checkRef != iref) {
+    LOG(ERROR) << "JNI ERROR (app bug): attempt to " << what
+               << " stale " << kind_ << " " << iref
+               << " (should be " << checkRef << ")";
+    AbortMaybe();
+    return false;
+  }
+  return true;
+}
+
+IndirectRef IndirectReferenceTable::Add(uint32_t cookie, Object* obj) {
+  IRTSegmentState prevState;
+  prevState.all = cookie;
+  size_t topIndex = segmentState.parts.topIndex;
+
+  DCHECK(obj != NULL);
+  //DCHECK(dvmIsHeapAddress(obj));
+  DCHECK(table_ != NULL);
+  DCHECK_LE(alloc_entries_, max_entries_);
+  DCHECK_GE(segmentState.parts.numHoles, prevState.parts.numHoles);
+
+  if (topIndex == alloc_entries_) {
+    /* reached end of allocated space; did we hit buffer max? */
+    if (topIndex == max_entries_) {
+      LOG(ERROR) << "JNI ERROR (app bug): " << kind_ << " table overflow "
+                 << "(max=" << max_entries_ << ")";
+      Dump();
+      LOG(FATAL); // TODO: operator<< for IndirectReferenceTable
+    }
+
+    size_t newSize = alloc_entries_ * 2;
+    if (newSize > max_entries_) {
+      newSize = max_entries_;
+    }
+    DCHECK_GT(newSize, alloc_entries_);
+
+    table_ = (Object**) realloc(table_, newSize * sizeof(Object*));
+    slot_data_ = (IndirectRefSlot*) realloc(slot_data_, newSize * sizeof(IndirectRefSlot));
+    if (table_ == NULL || slot_data_ == NULL) {
+      LOG(ERROR) << "JNI ERROR (app bug): unable to expand "
+                 << kind_ << " table (from "
+                 << alloc_entries_ << " to " << newSize
+                 << ", max=" << max_entries_ << ")";
+      Dump();
+      LOG(FATAL); // TODO: operator<< for IndirectReferenceTable
+    }
+
+    // Clear the newly-allocated slot_data_ elements.
+    memset(slot_data_ + alloc_entries_, 0, (newSize - alloc_entries_) * sizeof(IndirectRefSlot));
+
+    alloc_entries_ = newSize;
+  }
+
+  /*
+   * We know there's enough room in the table.  Now we just need to find
+   * the right spot.  If there's a hole, find it and fill it; otherwise,
+   * add to the end of the list.
+   */
+  IndirectRef result;
+  int numHoles = segmentState.parts.numHoles - prevState.parts.numHoles;
+  if (numHoles > 0) {
+    DCHECK_GT(topIndex, 1U);
+    /* find the first hole; likely to be near the end of the list */
+    Object** pScan = &table_[topIndex - 1];
+    DCHECK(*pScan != NULL);
+    while (*--pScan != NULL) {
+      DCHECK_GE(pScan, table_ + prevState.parts.topIndex);
+    }
+    UpdateSlotAdd(obj, pScan - table_);
+    result = ToIndirectRef(obj, pScan - table_);
+    *pScan = obj;
+    segmentState.parts.numHoles--;
+  } else {
+    /* add to the end */
+    UpdateSlotAdd(obj, topIndex);
+    result = ToIndirectRef(obj, topIndex);
+    table_[topIndex++] = obj;
+    segmentState.parts.topIndex = topIndex;
+  }
+
+  DCHECK(result != NULL);
+  return result;
+}
+
+/*
+ * Verify that the indirect table lookup is valid.
+ *
+ * Returns "false" if something looks bad.
+ */
+bool IndirectReferenceTable::GetChecked(IndirectRef iref) const {
+  if (iref == NULL) {
+    LOG(WARNING) << "Attempt to look up NULL " << kind_;
+    return false;
+  }
+  if (GetIndirectRefKind(iref) == kInvalid) {
+    LOG(ERROR) << "JNI ERROR (app bug): invalid " << kind_ << " " << iref;
+    AbortMaybe();
+    return false;
+  }
+
+  int topIndex = segmentState.parts.topIndex;
+  int idx = ExtractIndex(iref);
+  if (idx >= topIndex) {
+    /* bad -- stale reference? */
+    LOG(ERROR) << "JNI ERROR (app bug): accessed stale " << kind_ << " " << iref << " (index " << idx << " in a table of size " << topIndex << ")";
+    AbortMaybe();
+    return false;
+  }
+
+  if (table_[idx] == NULL) {
+    LOG(ERROR) << "JNI ERROR (app bug): accessed deleted " << kind_ << " " << iref;
+    AbortMaybe();
+    return false;
+  }
+
+  if (!CheckEntry("use", iref, idx)) {
+    return false;
+  }
+
+  return true;
+}
+
+static int LinearScan(IndirectRef iref, int bottomIndex, int topIndex, Object** table) {
+  for (int i = bottomIndex; i < topIndex; ++i) {
+    if (table[i] == reinterpret_cast<Object*>(iref)) {
+      return i;
+    }
+  }
+  return -1;
+}
+
+bool IndirectReferenceTable::Contains(IndirectRef iref) const {
+  return LinearScan(iref, 0, segmentState.parts.topIndex, table_) != -1;
+}
+
+/*
+ * Remove "obj" from "pRef".  We extract the table offset bits from "iref"
+ * and zap the corresponding entry, leaving a hole if it's not at the top.
+ *
+ * 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.
+ *
+ * Note this is NOT called when a local frame is popped.  This is only used
+ * for explicit single removals.
+ *
+ * Returns "false" if nothing was removed.
+ */
+bool IndirectReferenceTable::Remove(uint32_t cookie, IndirectRef iref) {
+  IRTSegmentState prevState;
+  prevState.all = cookie;
+  int topIndex = segmentState.parts.topIndex;
+  int bottomIndex = prevState.parts.topIndex;
+
+  DCHECK(table_ != NULL);
+  DCHECK_LE(alloc_entries_, max_entries_);
+  DCHECK_GE(segmentState.parts.numHoles, prevState.parts.numHoles);
+
+  int idx = ExtractIndex(iref);
+  bool workAroundAppJniBugs = false;
+
+  if (GetIndirectRefKind(iref) == kInvalid /*&& gDvmJni.workAroundAppJniBugs*/) { // TODO
+    idx = LinearScan(iref, bottomIndex, topIndex, table_);
+    workAroundAppJniBugs = true;
+    if (idx == -1) {
+      LOG(WARNING) << "trying to work around app JNI bugs, but didn't find " << iref << " in table!";
+      return false;
+    }
+  }
+
+  if (idx < bottomIndex) {
+    /* wrong segment */
+    LOG(INFO) << "Attempt to remove index outside index area (" << idx << " vs " << bottomIndex << "-" << topIndex << ")";
+    return false;
+  }
+  if (idx >= topIndex) {
+    /* bad -- stale reference? */
+    LOG(INFO) << "Attempt to remove invalid index " << idx << " (bottom=" << bottomIndex << " top=" << topIndex << ")";
+    return false;
+  }
+
+  if (idx == topIndex-1) {
+    // Top-most entry.  Scan up and consume holes.
+
+    if (workAroundAppJniBugs == false && !CheckEntry("remove", iref, idx)) {
+      return false;
+    }
+
+    table_[idx] = NULL;
+    int numHoles = segmentState.parts.numHoles - prevState.parts.numHoles;
+    if (numHoles != 0) {
+      while (--topIndex > bottomIndex && numHoles != 0) {
+        //LOG(INFO) << "+++ checking for hole at " << topIndex-1 << " (cookie=" << cookie << ") val=" << table_[topIndex-1];
+        if (table_[topIndex-1] != NULL) {
+          break;
+        }
+        //LOG(INFO) << "+++ ate hole at " << (topIndex-1);
+        numHoles--;
+      }
+      segmentState.parts.numHoles = numHoles + prevState.parts.numHoles;
+      segmentState.parts.topIndex = topIndex;
+    } else {
+      segmentState.parts.topIndex = topIndex-1;
+      LOG(INFO) << "+++ ate last entry " << topIndex-1;
+    }
+  } else {
+    /*
+     * Not the top-most entry.  This creates a hole.  We NULL out the
+     * entry to prevent somebody from deleting it twice and screwing up
+     * the hole count.
+     */
+    if (table_[idx] == NULL) {
+      LOG(INFO) << "--- WEIRD: removing null entry " << idx;
+      return false;
+    }
+    if (workAroundAppJniBugs == false && !CheckEntry("remove", iref, idx)) {
+      return false;
+    }
+
+    table_[idx] = NULL;
+    segmentState.parts.numHoles++;
+    //LOG(INFO) << "+++ left hole at " << idx << ", holes=" << segmentState.parts.numHoles;
+  }
+
+  return true;
+}
+
+std::ostream& operator<<(std::ostream& os, IndirectRefKind rhs) {
+  switch (rhs) {
+  case kInvalid:
+    os << "invalid reference";
+    break;
+  case kLocal:
+    os << "local reference";
+    break;
+  case kGlobal:
+    os << "global reference";
+    break;
+  case kWeakGlobal:
+    os << "weak global reference";
+    break;
+  default:
+    os << "IndirectRefKind[" << static_cast<int>(rhs) << "]";
+    break;
+  }
+  return os;
+}
+
+void IndirectReferenceTable::Dump() const {
+  LOG(WARNING) << kind_ << " table dump:";
+  std::vector<Object*> entries(table_, table_ + Capacity());
+  ReferenceTable::Dump(entries);
+}
+
+}  // namespace art
diff --git a/src/indirect_reference_table.h b/src/indirect_reference_table.h
new file mode 100644
index 0000000000..857b9cd939
--- /dev/null
+++ b/src/indirect_reference_table.h
@@ -0,0 +1,365 @@
+/*
+ * 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 "logging.h"
+
+#include <iosfwd>
+#include <stdint.h>
+#include <string>
+
+namespace art {
+
+class Object;
+
+/*
+ * 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 refs are performed on JNI method calls
+ * in and out of the VM, 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 dvmIsHeapAddress() */
+static Object* const kInvalidIndirectRefObject = reinterpret_cast<Object*>(0xdead4321);
+static Object* const kClearedJniWeakGlobal = reinterpret_cast<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 {
+    kInvalid    = 0,
+    kLocal      = 1,
+    kGlobal     = 2,
+    kWeakGlobal = 3
+};
+std::ostream& operator<<(std::ostream& os, 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;
+  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 (the VM keeps it in a
+ * slot in the interpreted stack frame).  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.
+ *
+ * We need to minimize method call/return overhead.  If we store the
+ * "cookie" externally, on the interpreted call stack, the VM can handle
+ * pushes and pops with a single 4-byte load and store.  (We could also
+ * store it internally in a public structure, but the local JNI refs are
+ * logically tied to interpreted stack frames anyway.)
+ *
+ * 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(Object** table, size_t i, size_t capacity)
+      : table_(table), i_(i), capacity_(capacity) {
+    SkipNullsAndTombstones();
+  }
+
+  IrtIterator& operator++() {
+    ++i_;
+    SkipNullsAndTombstones();
+    return *this;
+  }
+
+  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_;
+    }
+  }
+
+  Object** table_;
+  size_t i_;
+  size_t capacity_;
+};
+
+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
+   * (though it's okay if it's not fully-formed, e.g. the result from
+   * dvmMalloc doesn't have obj->clazz set).
+   *
+   * Returns NULL if the table is full (max entries reached, or alloc
+   * failed during expansion).
+   */
+  IndirectRef Add(uint32_t cookie, Object* obj);
+
+  /*
+   * Given an IndirectRef in the table, return the Object it refers to.
+   *
+   * Returns kInvalidIndirectRefObject if iref is invalid.
+   */
+  Object* Get(IndirectRef iref) const {
+    if (!GetChecked(iref)) {
+      return kInvalidIndirectRefObject;
+    }
+    return table_[ExtractIndex(iref)];
+  }
+
+  // TODO: only used for workAroundAppJniBugs support.
+  bool Contains(IndirectRef iref) 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 Dump() const;
+
+  /*
+   * 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 segmentState.parts.topIndex;
+  }
+
+  iterator begin() {
+    return iterator(table_, 0, Capacity());
+  }
+
+  iterator end() {
+    return iterator(table_, Capacity(), Capacity());
+  }
+
+ 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(Object* obj, 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(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 interpreter in native call handler */
+  IRTSegmentState segmentState;
+
+  /* bottom of the stack */
+  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_
diff --git a/src/indirect_reference_table_test.cc b/src/indirect_reference_table_test.cc
new file mode 100644
index 0000000000..97e3a70259
--- /dev/null
+++ b/src/indirect_reference_table_test.cc
@@ -0,0 +1,198 @@
+/*
+ * 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.
+ */
+
+#include "common_test.h"
+
+#include "indirect_reference_table.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+class IndirectReferenceTableTest : public RuntimeTest {
+};
+
+TEST_F(IndirectReferenceTableTest, BasicTest) {
+  static const size_t kTableInitial = 10;
+  static const size_t kTableMax = 20;
+  IndirectReferenceTable irt(kTableInitial, kTableMax, kGlobal);
+
+  Class* c = class_linker_->FindSystemClass("Ljava/lang/Object;");
+  ASSERT_TRUE(c != NULL);
+  Object* obj0 = c->NewInstance();
+  ASSERT_TRUE(obj0 != NULL);
+  Object* obj1 = c->NewInstance();
+  ASSERT_TRUE(obj1 != NULL);
+  Object* obj2 = c->NewInstance();
+  ASSERT_TRUE(obj2 != NULL);
+  Object* obj3 = c->NewInstance();
+  ASSERT_TRUE(obj3 != NULL);
+
+  const uint32_t cookie = IRT_FIRST_SEGMENT;
+
+  IndirectRef iref0 = (IndirectRef) 0x11110;
+  EXPECT_FALSE(irt.Remove(cookie, iref0)) << "unexpectedly successful removal";
+
+  // Add three, check, remove in the order in which they were added.
+  iref0 = irt.Add(cookie, obj0);
+  EXPECT_TRUE(iref0 != NULL);
+  IndirectRef iref1 = irt.Add(cookie, obj1);
+  EXPECT_TRUE(iref1 != NULL);
+  IndirectRef iref2 = irt.Add(cookie, obj2);
+  EXPECT_TRUE(iref2 != NULL);
+
+  irt.Dump();
+
+  EXPECT_EQ(obj0, irt.Get(iref0));
+  EXPECT_EQ(obj1, irt.Get(iref1));
+  EXPECT_EQ(obj2, irt.Get(iref2));
+
+  EXPECT_TRUE(irt.Remove(cookie, iref0));
+  EXPECT_TRUE(irt.Remove(cookie, iref1));
+  EXPECT_TRUE(irt.Remove(cookie, iref2));
+
+  // Table should be empty now.
+  EXPECT_EQ(0U, irt.Capacity());
+
+  // Get invalid entry (off the end of the list).
+  EXPECT_EQ(kInvalidIndirectRefObject, irt.Get(iref0));
+
+  // Add three, remove in the opposite order.
+  iref0 = irt.Add(cookie, obj0);
+  EXPECT_TRUE(iref0 != NULL);
+  iref1 = irt.Add(cookie, obj1);
+  EXPECT_TRUE(iref1 != NULL);
+  iref2 = irt.Add(cookie, obj2);
+  EXPECT_TRUE(iref2 != NULL);
+
+  ASSERT_TRUE(irt.Remove(cookie, iref2));
+  ASSERT_TRUE(irt.Remove(cookie, iref1));
+  ASSERT_TRUE(irt.Remove(cookie, iref0));
+
+  // Table should be empty now.
+  ASSERT_EQ(0U, irt.Capacity());
+
+  // Add three, remove middle / middle / bottom / top.  (Second attempt
+  // to remove middle should fail.)
+  iref0 = irt.Add(cookie, obj0);
+  EXPECT_TRUE(iref0 != NULL);
+  iref1 = irt.Add(cookie, obj1);
+  EXPECT_TRUE(iref1 != NULL);
+  iref2 = irt.Add(cookie, obj2);
+  EXPECT_TRUE(iref2 != NULL);
+
+  ASSERT_EQ(3U, irt.Capacity());
+
+  ASSERT_TRUE(irt.Remove(cookie, iref1));
+  ASSERT_FALSE(irt.Remove(cookie, iref1));
+
+  // Get invalid entry (from hole).
+  EXPECT_EQ(kInvalidIndirectRefObject, irt.Get(iref1));
+
+  ASSERT_TRUE(irt.Remove(cookie, iref2));
+  ASSERT_TRUE(irt.Remove(cookie, iref0));
+
+  // Table should be empty now.
+  ASSERT_EQ(0U, irt.Capacity());
+
+  // Add four entries.  Remove #1, add new entry, verify that table size
+  // is still 4 (i.e. holes are getting filled).  Remove #1 and #3, verify
+  // that we delete one and don't hole-compact the other.
+  iref0 = irt.Add(cookie, obj0);
+  EXPECT_TRUE(iref0 != NULL);
+  iref1 = irt.Add(cookie, obj1);
+  EXPECT_TRUE(iref1 != NULL);
+  iref2 = irt.Add(cookie, obj2);
+  EXPECT_TRUE(iref2 != NULL);
+  IndirectRef iref3 = irt.Add(cookie, obj3);
+  EXPECT_TRUE(iref3 != NULL);
+
+  ASSERT_TRUE(irt.Remove(cookie, iref1));
+
+  iref1 = irt.Add(cookie, obj1);
+  EXPECT_TRUE(iref1 != NULL);
+
+  ASSERT_EQ(4U, irt.Capacity()) << "hole not filled";
+
+  ASSERT_TRUE(irt.Remove(cookie, iref1));
+  ASSERT_TRUE(irt.Remove(cookie, iref3));
+
+  ASSERT_EQ(3U, irt.Capacity()) << "should be 3 after two deletions";
+
+  ASSERT_TRUE(irt.Remove(cookie, iref2));
+  ASSERT_TRUE(irt.Remove(cookie, iref0));
+
+  ASSERT_EQ(0U, irt.Capacity()) << "not empty after split remove";
+
+  // Add an entry, remove it, add a new entry, and try to use the original
+  // iref.  They have the same slot number but are for different objects.
+  // With the extended checks in place, this should fail.
+  iref0 = irt.Add(cookie, obj0);
+  EXPECT_TRUE(iref0 != NULL);
+  ASSERT_TRUE(irt.Remove(cookie, iref0));
+  iref1 = irt.Add(cookie, obj1);
+  EXPECT_TRUE(iref1 != NULL);
+  ASSERT_FALSE(irt.Remove(cookie, iref0)) << "mismatched del succeeded";
+  ASSERT_TRUE(irt.Remove(cookie, iref1)) << "switched del failed";
+  ASSERT_EQ(0U, irt.Capacity()) << "switching del not empty";
+
+  // Same as above, but with the same object.  A more rigorous checker
+  // (e.g. with slot serialization) will catch this.
+  iref0 = irt.Add(cookie, obj0);
+  EXPECT_TRUE(iref0 != NULL);
+  ASSERT_TRUE(irt.Remove(cookie, iref0));
+  iref1 = irt.Add(cookie, obj0);
+  EXPECT_TRUE(iref1 != NULL);
+  if (iref0 != iref1) {
+    // Try 0, should not work.
+    ASSERT_FALSE(irt.Remove(cookie, iref0)) << "temporal del succeeded";
+  }
+  ASSERT_TRUE(irt.Remove(cookie, iref1)) << "temporal cleanup failed";
+  ASSERT_EQ(0U, irt.Capacity()) << "temporal del not empty";
+
+  // NULL isn't a valid iref.
+  ASSERT_EQ(kInvalidIndirectRefObject, irt.Get(NULL));
+
+  // Stale lookup.
+  iref0 = irt.Add(cookie, obj0);
+  EXPECT_TRUE(iref0 != NULL);
+  ASSERT_TRUE(irt.Remove(cookie, iref0));
+  EXPECT_EQ(kInvalidIndirectRefObject, irt.Get(iref0)) << "stale lookup succeeded";
+
+  // Test table resizing.
+  // These ones fit...
+  IndirectRef manyRefs[kTableInitial];
+  for (size_t i = 0; i < kTableInitial; i++) {
+    manyRefs[i] = irt.Add(cookie, obj0);
+    ASSERT_TRUE(manyRefs[i] != NULL) << "Failed adding " << i;
+  }
+  // ...this one causes overflow.
+  iref0 = irt.Add(cookie, obj0);
+  ASSERT_TRUE(iref0 != NULL);
+  ASSERT_EQ(kTableInitial + 1, irt.Capacity());
+
+  for (size_t i = 0; i < kTableInitial; i++) {
+    ASSERT_TRUE(irt.Remove(cookie, manyRefs[i])) << "failed removing " << i;
+  }
+  // Because of removal order, should have 11 entries, 10 of them holes.
+  ASSERT_EQ(kTableInitial + 1, irt.Capacity());
+
+  ASSERT_TRUE(irt.Remove(cookie, iref0)) << "multi-remove final failed";
+
+  ASSERT_EQ(0U, irt.Capacity()) << "multi-del not empty";
+}
+
+}  // namespace art
diff --git a/src/jni_internal.cc b/src/jni_internal.cc
index d6cfcb9401..ef3bf57770 100644
--- a/src/jni_internal.cc
+++ b/src/jni_internal.cc
@@ -2024,15 +2024,19 @@ static const struct JNINativeInterface gNativeInterface = {
   GetObjectRefType,
 };
 
-static const size_t kMonitorTableInitialSize = 32; // Arbitrary.
-static const size_t kMonitorTableMaxSize = 4096; // Arbitrary sanity check.
+static const size_t kMonitorsInitial = 32; // Arbitrary.
+static const size_t kMonitorsMax = 4096; // Arbitrary sanity check.
+
+static const size_t kLocalsInitial = 64; // Arbitrary.
+static const size_t kLocalsMax = 512; // Arbitrary sanity check.
 
 JNIEnvExt::JNIEnvExt(Thread* self, bool check_jni)
     : fns(&gNativeInterface),
       self(self),
       check_jni(check_jni),
       critical(false),
-      monitor_table("monitor table", kMonitorTableInitialSize, kMonitorTableMaxSize) {
+      monitors("monitors", kMonitorsInitial, kMonitorsMax),
+      locals(kLocalsInitial, kLocalsMax, kLocal) {
 }
 
 // JNI Invocation interface.
@@ -2167,11 +2171,19 @@ struct JNIInvokeInterface gInvokeInterface = {
 static const size_t kPinTableInitialSize = 16;
 static const size_t kPinTableMaxSize = 1024;
 
+static const size_t kGlobalsInitial = 512; // Arbitrary.
+static const size_t kGlobalsMax = 51200; // Arbitrary sanity check.
+
+static const size_t kWeakGlobalsInitial = 16; // Arbitrary.
+static const size_t kWeakGlobalsMax = 51200; // Arbitrary sanity check.
+
 JavaVMExt::JavaVMExt(Runtime* runtime, bool check_jni)
     : fns(&gInvokeInterface),
       runtime(runtime),
       check_jni(check_jni),
-      pin_table("pin table", kPinTableInitialSize, kPinTableMaxSize) {
+      pin_table("pin table", kPinTableInitialSize, kPinTableMaxSize),
+      globals(kGlobalsInitial, kGlobalsMax, kGlobal),
+      weak_globals(kWeakGlobalsInitial, kWeakGlobalsMax, kWeakGlobal) {
 }
 
 }  // namespace art
diff --git a/src/jni_internal.h b/src/jni_internal.h
index 9cf8d57de7..50e3925618 100644
--- a/src/jni_internal.h
+++ b/src/jni_internal.h
@@ -6,6 +6,7 @@
 #include "jni.h"
 
 #include "assembler.h"
+#include "indirect_reference_table.h"
 #include "macros.h"
 #include "reference_table.h"
 
@@ -26,6 +27,12 @@ struct JavaVMExt {
 
   // Used to hold references to pinned primitive arrays.
   ReferenceTable pin_table;
+
+  // JNI global references.
+  IndirectReferenceTable globals;
+
+  // JNI weak global references.
+  IndirectReferenceTable weak_globals;
 };
 
 struct JNIEnvExt {
@@ -42,7 +49,10 @@ struct JNIEnvExt {
   bool critical;
 
   // Entered JNI monitors, for bulk exit on thread detach.
-  ReferenceTable  monitor_table;
+  ReferenceTable  monitors;
+
+  // JNI local references.
+  IndirectReferenceTable locals;
 };
 
 }  // namespace art
diff --git a/src/reference_table.cc b/src/reference_table.cc
index df908afdc9..0fc038a58f 100644
--- a/src/reference_table.cc
+++ b/src/reference_table.cc
@@ -16,6 +16,8 @@
 
 #include "reference_table.h"
 
+#include "indirect_reference_table.h"
+
 #include "object.h"
 
 namespace art {
@@ -125,28 +127,27 @@ size_t ReferenceTable::Size() const {
   return entries_.size();
 }
 
-// Dump a summary of an array of references to the log file.
-//
-// This is used to dump the contents of ReferenceTable and IndirectRefTable
-// structs.
 void ReferenceTable::Dump() const {
   LOG(WARNING) << name_ << " reference table dump:";
+  Dump(entries_);
+}
 
-  if (entries_.empty()) {
+void ReferenceTable::Dump(const std::vector<Object*>& entries) {
+  if (entries.empty()) {
     LOG(WARNING) << "  (empty)";
     return;
   }
 
   // Dump the most recent N entries.
   const size_t kLast = 10;
-  size_t count = entries_.size();
+  size_t count = entries.size();
   int first = count - kLast;
   if (first < 0) {
     first = 0;
   }
   LOG(WARNING) << "  Last " << (count - first) << " entries (of " << count << "):";
   for (int idx = count - 1; idx >= first; --idx) {
-    const Object* ref = entries_[idx];
+    const Object* ref = entries[idx];
     if (ref == NULL) {
       continue;
     }
@@ -191,7 +192,7 @@ void ReferenceTable::Dump() const {
   }
 
   // Make a copy of the table and sort it.
-  std::vector<Object*> sorted_entries(entries_.begin(), entries_.end());
+  std::vector<Object*> sorted_entries(entries.begin(), entries.end());
   std::sort(sorted_entries.begin(), sorted_entries.end(), ObjectComparator());
 
   // Remove any uninteresting stuff from the list. The sort moved them all to the end.
diff --git a/src/reference_table.h b/src/reference_table.h
index 1181304ab4..2e4d95401b 100644
--- a/src/reference_table.h
+++ b/src/reference_table.h
@@ -26,11 +26,8 @@ namespace art {
 
 class Object;
 
-static const Object* const kInvalidIndirectRefObject = reinterpret_cast<Object*>(0xdead4321);
-static const Object* const kClearedJniWeakGlobal = reinterpret_cast<Object*>(0xdead1234);
-
-// Maintain a table of references.  Used for internal local references,
-// JNI monitor references, and JNI pinned array references.
+// Maintain a table of references.  Used for JNI monitor references and
+// JNI pinned array references.
 //
 // None of the functions are synchronized.
 class ReferenceTable {
@@ -46,6 +43,9 @@ class ReferenceTable {
   void Dump() const;
 
  private:
+  static void Dump(const std::vector<Object*>& entries);
+  friend class IndirectReferenceTable; // For Dump.
+
   std::string name_;
   std::vector<Object*> entries_;
   size_t max_size_;