traced_perf: unwind queue type
In the perf profiler, there's a need for samples to be enqueued between
the reader, and the unwinder. There will be a single writer thread, and
a (separate) single reader thread.
The queue is implemented as a basic ring buffer of an arbitrary type
(std::array<T, N> + atomic rd/wr pointers). The implementation is
generic, but I've kept the type with a dedicated name (UnwindQueue)
until we find a need to reuse it.
Likewise, the read and write primitives are skewed towards the expected
use-case: writer commits entries one by one, reader can consume a batch
of contiguous entries.
See follow-up patch for more context.
Bug: 144281346
Change-Id: I83d7d6100f5cf52fa91c93d6c75624af6b788b7e
diff --git a/Android.bp b/Android.bp
index 6c873f7..6f56224 100644
--- a/Android.bp
+++ b/Android.bp
@@ -5948,6 +5948,7 @@
name: "perfetto_src_profiling_perf_producer_unittests",
srcs: [
"src/profiling/perf/event_config_unittest.cc",
+ "src/profiling/perf/unwind_queue_unittest.cc",
],
}
@@ -5967,6 +5968,11 @@
],
}
+// GN: //src/profiling/perf:unwinding
+filegroup {
+ name: "perfetto_src_profiling_perf_unwinding",
+}
+
// GN: //src/profiling/symbolizer:symbolize_database
filegroup {
name: "perfetto_src_profiling_symbolizer_symbolize_database",
@@ -7237,6 +7243,7 @@
":perfetto_src_profiling_perf_producer",
":perfetto_src_profiling_perf_producer_unittests",
":perfetto_src_profiling_perf_regs_parsing",
+ ":perfetto_src_profiling_perf_unwinding",
":perfetto_src_profiling_unittests",
":perfetto_src_protozero_protozero",
":perfetto_src_protozero_testing_messages_cpp_gen",
diff --git a/src/profiling/perf/BUILD.gn b/src/profiling/perf/BUILD.gn
index 0d9a916..dcf57d7 100644
--- a/src/profiling/perf/BUILD.gn
+++ b/src/profiling/perf/BUILD.gn
@@ -96,10 +96,19 @@
]
}
+source_set("unwinding") {
+ deps = [
+ "../../../gn:default_deps",
+ "../../../src/base",
+ ]
+ sources = [ "unwind_queue.h" ]
+}
+
source_set("producer_unittests") {
testonly = true
deps = [
":producer",
+ ":unwinding",
"../../../gn:default_deps",
"../../../gn:gtest_and_gmock",
"../../../protos/perfetto/config:cpp",
@@ -109,5 +118,8 @@
"../../../src/protozero",
"../../base",
]
- sources = [ "event_config_unittest.cc" ]
+ sources = [
+ "event_config_unittest.cc",
+ "unwind_queue_unittest.cc",
+ ]
}
diff --git a/src/profiling/perf/unwind_queue.h b/src/profiling/perf/unwind_queue.h
new file mode 100644
index 0000000..8231251
--- /dev/null
+++ b/src/profiling/perf/unwind_queue.h
@@ -0,0 +1,94 @@
+/*
+ * Copyright (C) 2020 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 SRC_PROFILING_PERF_UNWIND_QUEUE_H_
+#define SRC_PROFILING_PERF_UNWIND_QUEUE_H_
+
+#include <array>
+#include <atomic>
+
+#include "perfetto/base/logging.h"
+
+namespace perfetto {
+namespace profiling {
+
+struct WriteView {
+ bool valid; // if false: buffer is full, and |write_pos| is invalid
+ uint64_t write_pos;
+};
+
+struct ReadView {
+ uint64_t read_pos;
+ uint64_t write_pos;
+};
+
+// Single-writer, single-reader ring buffer of fixed-size entries (of any
+// default-constructible type). Size of the buffer is static for the lifetime of
+// UnwindQueue, and must be a power of two.
+// Writer side appends entries once at a time, and must stop if there
+// is no available capacity.
+// Reader side sees all unconsumed entries, and can advance the reader position
+// by any amount.
+template <typename T, uint32_t QueueSize>
+class UnwindQueue {
+ public:
+ UnwindQueue() {
+ static_assert(QueueSize != 0 && ((QueueSize & (QueueSize - 1)) == 0),
+ "not a power of two");
+ }
+
+ UnwindQueue(const UnwindQueue&) = delete;
+ UnwindQueue& operator=(const UnwindQueue&) = delete;
+ UnwindQueue(UnwindQueue&&) = delete;
+ UnwindQueue& operator=(UnwindQueue&&) = delete;
+
+ T& at(uint64_t pos) { return data_[pos % QueueSize]; }
+
+ WriteView BeginWrite() {
+ uint64_t rd = rd_pos_.load(std::memory_order_acquire);
+ uint64_t wr = wr_pos_.load(std::memory_order_relaxed);
+
+ PERFETTO_DCHECK(wr >= rd);
+ if (wr - rd >= QueueSize)
+ return WriteView{false, 0}; // buffer fully occupied
+
+ return WriteView{true, wr};
+ }
+
+ void CommitWrite() { wr_pos_.fetch_add(1u, std::memory_order_release); }
+
+ ReadView BeginRead() {
+ uint64_t wr = wr_pos_.load(std::memory_order_acquire);
+ uint64_t rd = rd_pos_.load(std::memory_order_relaxed);
+
+ PERFETTO_DCHECK(wr >= rd && wr - rd <= QueueSize);
+ return ReadView{rd, wr};
+ }
+
+ void CommitNewReadPosition(uint64_t pos) {
+ rd_pos_.store(pos, std::memory_order_release);
+ }
+
+ private:
+ std::array<T, QueueSize> data_;
+ std::atomic<uint64_t> wr_pos_{0};
+ std::atomic<uint64_t> rd_pos_{0};
+};
+
+} // namespace profiling
+} // namespace perfetto
+
+#endif // SRC_PROFILING_PERF_UNWIND_QUEUE_H_
diff --git a/src/profiling/perf/unwind_queue_unittest.cc b/src/profiling/perf/unwind_queue_unittest.cc
new file mode 100644
index 0000000..e906d59
--- /dev/null
+++ b/src/profiling/perf/unwind_queue_unittest.cc
@@ -0,0 +1,116 @@
+/*
+ * Copyright (C) 2020 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 "src/profiling/perf/unwind_queue.h"
+
+#include "test/gtest_and_gmock.h"
+
+namespace perfetto {
+namespace profiling {
+namespace {
+
+TEST(UnwindQueueTest, SinglePass) {
+ static constexpr uint32_t kCapacity = 4;
+ UnwindQueue<int, kCapacity> queue;
+
+ // write kCapacity entries
+ for (int i = 0; i < static_cast<int>(kCapacity); i++) {
+ WriteView v = queue.BeginWrite();
+ ASSERT_TRUE(v.valid);
+ queue.at(v.write_pos) = i;
+ queue.CommitWrite();
+ }
+ {
+ // no more available capacity
+ WriteView v = queue.BeginWrite();
+ ASSERT_FALSE(v.valid);
+ }
+
+ // reader sees all four writes
+ ReadView v = queue.BeginRead();
+ ASSERT_EQ(v.read_pos, 0u);
+ ASSERT_EQ(v.write_pos, 4u);
+
+ std::vector<int> read_back;
+ for (auto pos = v.read_pos; pos < v.write_pos; pos++) {
+ read_back.push_back(queue.at(pos));
+ }
+ queue.CommitNewReadPosition(v.write_pos);
+
+ ASSERT_THAT(read_back, ::testing::ElementsAre(0, 1, 2, 3));
+
+ // writer sees an available slot
+ ASSERT_TRUE(queue.BeginWrite().valid);
+ // reader caught up
+ ASSERT_TRUE(queue.BeginRead().read_pos == queue.BeginRead().write_pos);
+}
+
+TEST(UnwindQueueTest, Wrapped) {
+ static constexpr uint32_t kCapacity = 4;
+ UnwindQueue<int, kCapacity> queue;
+
+ // write kCapacity entries
+ for (int i = 0; i < static_cast<int>(kCapacity); i++) {
+ WriteView v = queue.BeginWrite();
+ ASSERT_TRUE(v.valid);
+ queue.at(v.write_pos) = i;
+ queue.CommitWrite();
+ }
+
+ // no more available capacity
+ ASSERT_FALSE(queue.BeginWrite().valid);
+
+ {
+ // consume 2 entries (partial read)
+ ReadView v = queue.BeginRead();
+ ASSERT_EQ(v.read_pos, 0u);
+ ASSERT_EQ(v.write_pos, 4u);
+ queue.CommitNewReadPosition(v.read_pos + 2);
+ }
+
+ // write 2 more entries
+ for (int i = 0; i < 2; i++) {
+ WriteView v = queue.BeginWrite();
+ ASSERT_TRUE(v.valid);
+ queue.at(v.write_pos) = 4 + i;
+ queue.CommitWrite();
+ }
+
+ // no more available capacity
+ ASSERT_FALSE(queue.BeginWrite().valid);
+
+ // read the remainder of the buffer
+ ReadView v = queue.BeginRead();
+ ASSERT_EQ(v.read_pos, 2u);
+ ASSERT_EQ(v.write_pos, 6u);
+
+ std::vector<int> read_back;
+ for (auto pos = v.read_pos; pos < v.write_pos; pos++) {
+ read_back.push_back(queue.at(pos));
+ }
+ queue.CommitNewReadPosition(v.write_pos);
+
+ ASSERT_THAT(read_back, ::testing::ElementsAre(2, 3, 4, 5));
+
+ // writer sees an available slot
+ ASSERT_TRUE(queue.BeginWrite().valid);
+ // reader caught up
+ ASSERT_TRUE(queue.BeginRead().read_pos == queue.BeginRead().write_pos);
+}
+
+} // namespace
+} // namespace profiling
+} // namespace perfetto
diff --git a/src/protozero/test/example_proto/test_messages.descriptor.h b/src/protozero/test/example_proto/test_messages.descriptor.h
index cdda498..417a711 100644
--- a/src/protozero/test/example_proto/test_messages.descriptor.h
+++ b/src/protozero/test/example_proto/test_messages.descriptor.h
@@ -223,19 +223,19 @@
0x72, 0x42, 0x61, 0x7a, 0x12, 0x16, 0x0a, 0x06, 0x62, 0x61, 0x72, 0x42,
0x61, 0x7a, 0x18, 0x02, 0x20, 0x01, 0x28, 0x08, 0x52, 0x06, 0x62, 0x61,
0x72, 0x42, 0x61, 0x7a, 0x12, 0x16, 0x0a, 0x06, 0x4d, 0x6f, 0x6f, 0x4d,
- 0x6f, 0x6f, 0x18, 0x03, 0x20, 0x01, 0x28, 0x08, 0x52, 0x06, 0x6d, 0x6f,
+ 0x6f, 0x6f, 0x18, 0x03, 0x20, 0x01, 0x28, 0x08, 0x52, 0x06, 0x4d, 0x6f,
0x6f, 0x4d, 0x6f, 0x6f, 0x12, 0x1e, 0x0a, 0x0a, 0x55, 0x52, 0x4c, 0x45,
0x6e, 0x63, 0x6f, 0x64, 0x65, 0x72, 0x18, 0x04, 0x20, 0x01, 0x28, 0x08,
- 0x52, 0x0a, 0x75, 0x52, 0x4c, 0x45, 0x6e, 0x63, 0x6f, 0x64, 0x65, 0x72,
+ 0x52, 0x0a, 0x55, 0x52, 0x4c, 0x45, 0x6e, 0x63, 0x6f, 0x64, 0x65, 0x72,
0x12, 0x12, 0x0a, 0x04, 0x58, 0x4d, 0x61, 0x70, 0x18, 0x05, 0x20, 0x01,
- 0x28, 0x08, 0x52, 0x04, 0x78, 0x4d, 0x61, 0x70, 0x12, 0x21, 0x0a, 0x0d,
+ 0x28, 0x08, 0x52, 0x04, 0x58, 0x4d, 0x61, 0x70, 0x12, 0x21, 0x0a, 0x0d,
0x55, 0x72, 0x4c, 0x45, 0x5f, 0x6e, 0x63, 0x6f, 0x5f, 0x5f, 0x64, 0x65,
- 0x72, 0x18, 0x06, 0x20, 0x01, 0x28, 0x08, 0x52, 0x0a, 0x75, 0x72, 0x4c,
+ 0x72, 0x18, 0x06, 0x20, 0x01, 0x28, 0x08, 0x52, 0x0a, 0x55, 0x72, 0x4c,
0x45, 0x4e, 0x63, 0x6f, 0x44, 0x65, 0x72, 0x12, 0x1a, 0x0a, 0x09, 0x5f,
0x5f, 0x62, 0x69, 0x67, 0x42, 0x61, 0x6e, 0x67, 0x18, 0x07, 0x20, 0x01,
- 0x28, 0x08, 0x52, 0x07, 0x62, 0x69, 0x67, 0x42, 0x61, 0x6e, 0x67, 0x12,
+ 0x28, 0x08, 0x52, 0x07, 0x42, 0x69, 0x67, 0x42, 0x61, 0x6e, 0x67, 0x12,
0x0e, 0x0a, 0x02, 0x55, 0x32, 0x18, 0x08, 0x20, 0x01, 0x28, 0x08, 0x52,
- 0x02, 0x75, 0x32, 0x12, 0x1a, 0x0a, 0x09, 0x62, 0x61, 0x6e, 0x67, 0x42,
+ 0x02, 0x55, 0x32, 0x12, 0x1a, 0x0a, 0x09, 0x62, 0x61, 0x6e, 0x67, 0x42,
0x69, 0x67, 0x5f, 0x5f, 0x18, 0x09, 0x20, 0x01, 0x28, 0x08, 0x52, 0x07,
0x62, 0x61, 0x6e, 0x67, 0x42, 0x69, 0x67, 0x22, 0x8f, 0x01, 0x0a, 0x14,
0x50, 0x61, 0x63, 0x6b, 0x65, 0x64, 0x52, 0x65, 0x70, 0x65, 0x61, 0x74,
