Create separate Android.mk for main build targets

The runtime, compiler, dex2oat, and oatdump now are in seperate trees
to prevent dependency creep.  They can now be individually built
without rebuilding the rest of the art projects. dalvikvm and jdwpspy
were already this way. Builds in the art directory should behave as
before, building everything including tests.

Change-Id: Ic6b1151e5ed0f823c3dd301afd2b13eb2d8feb81

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_