More parallel GC, rewritten parallel mark stack processing.

Card scanning may now be done in parallel. This speeds up sticky and
reduces pause times for all GC types.

Speedup on my mako (ritz perf):
Average pause time for sticky GC (~250 samples):
Without parallel cards scanning enabled: 2.524904215ms
Parallel card scanning (num_gc_threads_): 1.552123552ms
Throughput (~250 samples):
Sticky GC throughput with parallel card scanning: 69MB/s
Sticky GC throughput without parallel card scanning: 51MB/s

Rewrote the mark stack processing to be LIFO and use a prefetch queue
like the non parallel version.

Cleaned up some of the logcat printing for the activity manager
process state listening.

Added unlikely hints to object scanning since arrays and classes are
scanned much less often than normal objects.

Fixed a bug where the number of GC threads was clamped to 1 due to a
bool instead of a size_t.

Fixed a race condition when we added references to the reference
queues. Sharded the reference queue lock into one lock for each reference
type (weak, soft, phatom, finalizer).

Changed timing splits to be different for processing gray objects with
and without mutators paused since sticky GC does both.

Mask out the class bit when visiting fields as an optimization, this is
valid since classes are held live by the class linker.

Partially completed: Parallel recursive mark + finger.

Bug: 10245302
Bug: 9969166
Bug: 9986532
Bug: 9961698

Change-Id: I142d09718c4609b7c2387cb28f517a6983c73288

1 files changed, 74 insertions, 0 deletions

diff --git a/runtime/base/bounded_fifo.h b/runtime/base/bounded_fifo.h
new file mode 100644
index 0000000..cb92d40
--- /dev/null
+++ b/runtime/base/bounded_fifo.h
@@ -0,0 +1,74 @@
+/*
+ * Copyright (C) 2013 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_RUNTIME_BASE_BOUNDED_FIFO_H_
+#define ART_RUNTIME_BASE_BOUNDED_FIFO_H_
+
+#include "cutils/atomic.h"
+#include "cutils/atomic-inline.h"
+
+namespace art {
+
+// A bounded fifo is a fifo which has a bounded size. The power of two version uses a bit mask to
+// avoid needing to deal with wrapping integers around or using a modulo operation.
+template <typename T, const size_t MaxSize>
+class BoundedFifoPowerOfTwo {
+ public:
+  BoundedFifoPowerOfTwo() {
+    // TODO: Do this with a compile time check.
+    CHECK(IsPowerOfTwo(MaxSize));
+    clear();
+  }
+
+  void clear() {
+    back_index_ = 0;
+    size_ = 0;
+  }
+
+  bool empty() const {
+    return size() == 0;
+  }
+
+  size_t size() const {
+    return size_;
+  }
+
+  void push_back(const T& value) {
+    ++size_;
+    DCHECK_LE(size_, MaxSize);
+    // Relies on integer overflow behaviour.
+    data_[back_index_++ & mask_] = value;
+  }
+
+  const T& front() const {
+    DCHECK_GT(size_, 0U);
+    return data_[(back_index_ - size_) & mask_];
+  }
+
+  void pop_front() {
+    DCHECK_GT(size_, 0U);
+    --size_;
+  }
+
+ private:
+  static const size_t mask_ = MaxSize - 1;
+  size_t back_index_, size_;
+  T data_[MaxSize];
+};
+
+}  // namespace art
+
+#endif  // ART_RUNTIME_BASE_BOUNDED_FIFO_H_