TraceBuffer management
This CL introduces the initial logic for a proper
trace buffer than can handle reordering and gluing
trace packets. Most of the logic is commented in the
.h/.cc file.
Test: perfetto_unittest --gtest_filter=TraceBufferTest.*
Bug: 73612642
Change-Id: I8cf8515ad4c61c5ff85f24f23cd4ad7d5d04444b
diff --git a/Android.bp b/Android.bp
index 0f4466e..9b77f49 100644
--- a/Android.bp
+++ b/Android.bp
@@ -64,6 +64,7 @@
"src/tracing/core/shared_memory_abi.cc",
"src/tracing/core/shared_memory_arbiter_impl.cc",
"src/tracing/core/sliced_protobuf_input_stream.cc",
+ "src/tracing/core/trace_buffer.cc",
"src/tracing/core/trace_config.cc",
"src/tracing/core/trace_packet.cc",
"src/tracing/core/trace_writer_impl.cc",
@@ -135,6 +136,7 @@
"src/tracing/core/shared_memory_abi.cc",
"src/tracing/core/shared_memory_arbiter_impl.cc",
"src/tracing/core/sliced_protobuf_input_stream.cc",
+ "src/tracing/core/trace_buffer.cc",
"src/tracing/core/trace_config.cc",
"src/tracing/core/trace_packet.cc",
"src/tracing/core/trace_writer_impl.cc",
@@ -249,6 +251,7 @@
"src/tracing/core/shared_memory_abi.cc",
"src/tracing/core/shared_memory_arbiter_impl.cc",
"src/tracing/core/sliced_protobuf_input_stream.cc",
+ "src/tracing/core/trace_buffer.cc",
"src/tracing/core/trace_config.cc",
"src/tracing/core/trace_packet.cc",
"src/tracing/core/trace_writer_impl.cc",
@@ -2773,6 +2776,7 @@
"src/tracing/core/shared_memory_abi.cc",
"src/tracing/core/shared_memory_arbiter_impl.cc",
"src/tracing/core/sliced_protobuf_input_stream.cc",
+ "src/tracing/core/trace_buffer.cc",
"src/tracing/core/trace_config.cc",
"src/tracing/core/trace_packet.cc",
"src/tracing/core/trace_writer_impl.cc",
@@ -2913,6 +2917,8 @@
"src/tracing/core/shared_memory_arbiter_impl_unittest.cc",
"src/tracing/core/sliced_protobuf_input_stream.cc",
"src/tracing/core/sliced_protobuf_input_stream_unittest.cc",
+ "src/tracing/core/trace_buffer.cc",
+ "src/tracing/core/trace_buffer_unittest.cc",
"src/tracing/core/trace_config.cc",
"src/tracing/core/trace_packet.cc",
"src/tracing/core/trace_packet_unittest.cc",
@@ -2920,6 +2926,7 @@
"src/tracing/core/trace_writer_impl_unittest.cc",
"src/tracing/ipc/posix_shared_memory_unittest.cc",
"src/tracing/test/aligned_buffer_test.cc",
+ "src/tracing/test/fake_packet.cc",
"src/tracing/test/test_shared_memory.cc",
"src/tracing/test/tracing_integration_test.cc",
"tools/ftrace_proto_gen/ftrace_proto_gen.cc",
diff --git a/include/perfetto/base/utils.h b/include/perfetto/base/utils.h
index 0b464cf..3f49ea5 100644
--- a/include/perfetto/base/utils.h
+++ b/include/perfetto/base/utils.h
@@ -62,6 +62,13 @@
return value;
}
+// Round up |size| to a multiple of |alignment| (must be a power of two).
+template <int alignment>
+constexpr size_t AlignUp(size_t size) {
+ static_assert((alignment & (alignment - 1)) == 0, "alignment must be a pow2");
+ return (size + alignment - 1) & ~(alignment - 1);
+}
+
} // namespace base
} // namespace perfetto
diff --git a/src/base/utils_unittest.cc b/src/base/utils_unittest.cc
index 249d5ea..6c5f2f4 100644
--- a/src/base/utils_unittest.cc
+++ b/src/base/utils_unittest.cc
@@ -99,6 +99,20 @@
sigaction(SIGUSR2, &old_sa, nullptr);
}
+TEST(Utils, Align) {
+ EXPECT_EQ(0u, AlignUp<4>(0));
+ EXPECT_EQ(4u, AlignUp<4>(1));
+ EXPECT_EQ(4u, AlignUp<4>(3));
+ EXPECT_EQ(4u, AlignUp<4>(4));
+ EXPECT_EQ(8u, AlignUp<4>(5));
+ EXPECT_EQ(0u, AlignUp<16>(0));
+ EXPECT_EQ(16u, AlignUp<16>(1));
+ EXPECT_EQ(16u, AlignUp<16>(15));
+ EXPECT_EQ(16u, AlignUp<16>(16));
+ EXPECT_EQ(32u, AlignUp<16>(17));
+ EXPECT_EQ(0xffffff00u, AlignUp<16>(0xffffff00 - 1));
+}
+
} // namespace
} // namespace base
} // namespace perfetto
diff --git a/src/protozero/proto_utils.cc b/src/protozero/proto_utils.cc
index 8d1254a..baf1120 100644
--- a/src/protozero/proto_utils.cc
+++ b/src/protozero/proto_utils.cc
@@ -21,6 +21,7 @@
#include <limits>
#include "perfetto/base/logging.h"
+#include "perfetto/base/utils.h"
#define PERFETTO_CHECK_PTR_LE(a, b) \
PERFETTO_CHECK(reinterpret_cast<uintptr_t>(a) <= \
@@ -43,7 +44,10 @@
uint64_t shift = 0;
*value = 0;
do {
- PERFETTO_CHECK_PTR_LE(pos, end - 1);
+ if (PERFETTO_UNLIKELY(pos >= end)) {
+ *value = 0;
+ break;
+ }
PERFETTO_DCHECK(shift < 64ull);
*value |= static_cast<uint64_t>(*pos & 0x7f) << shift;
shift += 7;
diff --git a/src/protozero/proto_utils_unittest.cc b/src/protozero/proto_utils_unittest.cc
index 2ad6677..dd37bf2 100644
--- a/src/protozero/proto_utils_unittest.cc
+++ b/src/protozero/proto_utils_unittest.cc
@@ -156,6 +156,16 @@
}
}
+TEST(ProtoUtilsTest, VarIntDecodingOutOfBounds) {
+ uint8_t buf[] = {0xff, 0xff, 0xff, 0xff};
+ for (size_t i = 0; i < 5; i++) {
+ uint64_t value = -1;
+ const uint8_t* res = ParseVarInt(buf, buf + i, &value);
+ EXPECT_EQ(&buf[0] + i, res);
+ EXPECT_EQ(0u, value);
+ }
+}
+
TEST(ProtoUtilsTest, FieldDecoding) {
struct FieldExpectation {
const char* encoded;
diff --git a/src/tracing/BUILD.gn b/src/tracing/BUILD.gn
index d0dcf6c..567be03 100644
--- a/src/tracing/BUILD.gn
+++ b/src/tracing/BUILD.gn
@@ -43,6 +43,8 @@
"core/shared_memory_arbiter_impl.h",
"core/sliced_protobuf_input_stream.cc",
"core/sliced_protobuf_input_stream.h",
+ "core/trace_buffer.cc",
+ "core/trace_buffer.h",
"core/trace_config.cc",
"core/trace_packet.cc",
"core/trace_writer_impl.cc",
@@ -120,11 +122,14 @@
"core/shared_memory_abi_unittest.cc",
"core/shared_memory_arbiter_impl_unittest.cc",
"core/sliced_protobuf_input_stream_unittest.cc",
+ "core/trace_buffer_unittest.cc",
"core/trace_packet_unittest.cc",
"core/trace_writer_impl_unittest.cc",
"ipc/posix_shared_memory_unittest.cc",
"test/aligned_buffer_test.cc",
"test/aligned_buffer_test.h",
+ "test/fake_packet.cc",
+ "test/fake_packet.h",
"test/test_shared_memory.cc",
"test/test_shared_memory.h",
"test/tracing_integration_test.cc",
diff --git a/src/tracing/core/trace_buffer.cc b/src/tracing/core/trace_buffer.cc
new file mode 100644
index 0000000..55615a5
--- /dev/null
+++ b/src/tracing/core/trace_buffer.cc
@@ -0,0 +1,605 @@
+/*
+ * Copyright (C) 2018 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/tracing/core/trace_buffer.h"
+
+#include <sys/mman.h>
+#include <limits>
+
+#include "perfetto/base/logging.h"
+#include "perfetto/protozero/proto_utils.h"
+#include "perfetto/tracing/core/shared_memory_abi.h"
+
+// TODO(primiano): we need some flag to figure out if the packets on the
+// boundary require patching or have already been patched. The current
+// implementation considers all packets eligible to be read once we have all the
+// chunks that compose them.
+
+// TODO(primiano): copy over skyostil@'s trusted_uid logic.
+
+#define TRACE_BUFFER_VERBOSE_LOGGING() 0 // Set to 1 when debugging unittests.
+#if TRACE_BUFFER_VERBOSE_LOGGING()
+#define TRACE_BUFFER_DLOG PERFETTO_DLOG
+namespace {
+std::string HexDump(const uint8_t* src, size_t size) {
+ std::string buf;
+ buf.reserve(4096 * 4);
+ char line[64];
+ char* c = line;
+ for (size_t i = 0; i < size; i++) {
+ c += sprintf(c, "%02x ", src[i]);
+ if (i % 16 == 15) {
+ buf.append("\n");
+ buf.append(line);
+ c = line;
+ }
+ }
+ return buf;
+}
+} // namespace
+#else
+#define TRACE_BUFFER_DLOG(...) void()
+#endif
+
+namespace perfetto {
+
+namespace {
+constexpr uint8_t kFirstPacketContinuesFromPrevChunk =
+ SharedMemoryABI::ChunkHeader::kFirstPacketContinuesFromPrevChunk;
+constexpr uint8_t kLastPacketContinuesOnNextChunk =
+ SharedMemoryABI::ChunkHeader::kLastPacketContinuesOnNextChunk;
+} // namespace.
+
+constexpr size_t TraceBuffez::ChunkRecord::kMaxSize;
+const size_t TraceBuffez::InlineChunkHeaderSize = sizeof(ChunkRecord);
+
+// static
+std::unique_ptr<TraceBuffez> TraceBuffez::Create(size_t size_in_bytes) {
+ std::unique_ptr<TraceBuffez> trace_buffer(new TraceBuffez());
+ if (!trace_buffer->Initialize(size_in_bytes))
+ return nullptr;
+ return trace_buffer;
+}
+
+TraceBuffez::TraceBuffez() {
+ // See comments in ChunkRecord for the rationale of this.
+ static_assert(sizeof(ChunkRecord) == sizeof(SharedMemoryABI::PageHeader) +
+ sizeof(SharedMemoryABI::ChunkHeader),
+ "ChunkRecord out of sync with the layout of SharedMemoryABI");
+}
+
+TraceBuffez::~TraceBuffez() = default;
+
+bool TraceBuffez::Initialize(size_t size) {
+ static_assert(
+ base::kPageSize % sizeof(ChunkRecord) == 0,
+ "sizeof(ChunkRecord) must be an integer divider of a page size");
+ PERFETTO_CHECK(size % base::kPageSize == 0);
+ data_ = base::PageAllocator::AllocateMayFail(size);
+ if (!data_) {
+ PERFETTO_ELOG("Trace buffer allocation failed (size: %zu)", size);
+ return false;
+ }
+ size_ = size;
+ max_chunk_size_ = std::min(size, ChunkRecord::kMaxSize);
+ wptr_ = begin();
+ index_.clear();
+ last_chunk_id_.clear();
+ read_iter_ = GetReadIterForSequence(index_.end());
+ return true;
+}
+
+// Note: |src| points to a shmem region that is shared with the producer. Assume
+// that the producer is malicious and will change the content of |src|
+// while we execute here. Don't do any processing on it other than memcpy().
+void TraceBuffez::CopyChunkUntrusted(ProducerID producer_id_trusted,
+ WriterID writer_id,
+ ChunkID chunk_id,
+ uint16_t num_fragments,
+ uint8_t chunk_flags,
+ const uint8_t* src,
+ size_t size) {
+ // |record_size| = |size| + sizeof(ChunkRecord), rounded up to avoid to end
+ // up in a fragmented state where size_to_end() < sizeof(ChunkRecord).
+ const size_t record_size =
+ base::AlignUp<sizeof(ChunkRecord)>(size + sizeof(ChunkRecord));
+ if (PERFETTO_UNLIKELY(record_size > max_chunk_size_)) {
+ PERFETTO_DCHECK(suppress_sanity_dchecks_for_testing_);
+ return;
+ }
+
+ TRACE_BUFFER_DLOG("CopyChunk @ %lu, size=%zu", wptr_ - begin(), record_size);
+
+#if PERFETTO_DCHECK_IS_ON()
+ changed_since_last_read_ = true;
+#endif
+
+ // If there isn't enough room from the given write position. Write a padding
+ // record to clear the end of the buffer and wrap back.
+ const size_t cached_size_to_end = size_to_end();
+ if (PERFETTO_UNLIKELY(record_size > cached_size_to_end)) {
+ size_t res = DeleteNextChunksFor(cached_size_to_end);
+ PERFETTO_DCHECK(res <= cached_size_to_end);
+ AddPaddingRecord(cached_size_to_end);
+ wptr_ = begin();
+ stats_.write_wrap_count++;
+ PERFETTO_DCHECK(size_to_end() >= record_size);
+ }
+
+ ChunkRecord record(record_size);
+ record.producer_id = producer_id_trusted;
+ record.chunk_id = chunk_id;
+ record.writer_id = writer_id;
+ record.num_fragments = num_fragments;
+ record.flags = chunk_flags;
+
+ // At this point either |wptr_| points to an untouched part of the buffer
+ // (i.e. *wptr_ == 0) or we are about to overwrite one or more ChunkRecord(s).
+ // In the latter case we need to first figure out where the next valid
+ // ChunkRecord is (if it exists) and add padding between the new record.
+ // Example ((w) == write cursor):
+ //
+ // Initial state (wtpr_ == 0):
+ // |0 (w) |10 |30 |50
+ // +---------+-----------------+--------------------+--------------------+
+ // | Chunk 1 | Chunk 2 | Chunk 3 | Chunk 4 |
+ // +---------+-----------------+--------------------+--------------------+
+ //
+ // Let's assume we now want now write a 5th Chunk of size == 35. The final
+ // state should look like this:
+ // |0 |35 (w) |50
+ // +---------------------------------+---------------+--------------------+
+ // | Chunk 5 | Padding Chunk | Chunk 4 |
+ // +---------------------------------+---------------+--------------------+
+
+ // Deletes all chunks from |wptr_| to |wptr_| + |record_size|.
+ size_t padding_size = DeleteNextChunksFor(record_size);
+
+ // Now first insert the new chunk. At the end, if necessary, add the padding.
+ ChunkMeta::Key key(record);
+ auto it_and_inserted = index_.emplace(
+ key, ChunkMeta(GetChunkRecordAt(wptr_), num_fragments, chunk_flags));
+ if (PERFETTO_UNLIKELY(!it_and_inserted.second)) {
+ // More likely a producer bug, but could also be a malicious producer.
+ PERFETTO_DCHECK(suppress_sanity_dchecks_for_testing_);
+ index_.erase(it_and_inserted.first);
+ index_.emplace(
+ key, ChunkMeta(GetChunkRecordAt(wptr_), num_fragments, chunk_flags));
+ }
+ TRACE_BUFFER_DLOG(" copying @ [%lu - %lu] %zu", wptr_ - begin(),
+ wptr_ - begin() + record_size, record_size);
+ WriteChunkRecord(record, src, size);
+ TRACE_BUFFER_DLOG("Chunk raw: %s", HexDump(wptr_, record_size).c_str());
+ wptr_ += record_size;
+ if (wptr_ >= end()) {
+ PERFETTO_DCHECK(padding_size == 0);
+ wptr_ = begin();
+ stats_.write_wrap_count++;
+ }
+ DcheckIsAlignedAndWithinBounds(wptr_);
+
+ last_chunk_id_[std::make_pair(producer_id_trusted, writer_id)] = chunk_id;
+
+ if (padding_size)
+ AddPaddingRecord(padding_size);
+}
+
+size_t TraceBuffez::DeleteNextChunksFor(size_t bytes_to_clear) {
+ // Find the position of the first chunk which begins at or after
+ // (|wptr_| + |bytes|). Note that such a chunk might not exist and we might
+ // either reach the end of the buffer or a zeroed region of the buffer.
+ uint8_t* next_chunk_ptr = wptr_;
+ uint8_t* search_end = wptr_ + bytes_to_clear;
+ TRACE_BUFFER_DLOG("Delete [%zu %zu]", wptr_ - begin(), search_end - begin());
+ DcheckIsAlignedAndWithinBounds(wptr_);
+ PERFETTO_DCHECK(search_end <= end());
+ while (next_chunk_ptr < search_end) {
+ const ChunkRecord& next_chunk = *GetChunkRecordAt(next_chunk_ptr);
+ TRACE_BUFFER_DLOG(
+ " scanning chunk [%zu %zu] (valid=%d)", next_chunk_ptr - begin(),
+ next_chunk_ptr - begin() + next_chunk.size, next_chunk.is_valid());
+
+ // We just reached the untouched part of the buffer, it's going to be all
+ // zeroes from here to end().
+ // TODO(primiano): optimization: if during Initialize() we fill the buffer
+ // with padding records we could get rid of this branch.
+ if (!next_chunk.is_valid()) {
+ // This should happen only at the first iteration. The zeroed area can
+ // only begin precisely at the |wptr_|, not after. Otherwise it means that
+ // we wrapped but screwed up the ChunkRecord chain.
+ PERFETTO_DCHECK(next_chunk_ptr == wptr_);
+ return 0;
+ }
+
+ // Remove |next_chunk| from the index, unless it's a padding record (padding
+ // records are not part of the index).
+ if (PERFETTO_LIKELY(!next_chunk.is_padding)) {
+ ChunkMeta::Key key(next_chunk);
+ const size_t removed = index_.erase(key);
+ TRACE_BUFFER_DLOG(" del index {%" PRIu32 ",%" PRIu32
+ ",%u} @ [%lu - %lu] %zu",
+ key.producer_id, key.writer_id, key.chunk_id,
+ next_chunk_ptr - begin(),
+ next_chunk_ptr - begin() + next_chunk.size, removed);
+ PERFETTO_DCHECK(removed);
+ }
+
+ next_chunk_ptr += next_chunk.size;
+
+ // We should never hit this, unless we managed to screw up while writing
+ // to the buffer and breaking the ChunkRecord(s) chain.
+ // TODO(primiano): Write more meaningful logging with the status of the
+ // buffer, to get more actionable bugs in case we hit this.
+ PERFETTO_CHECK(next_chunk_ptr <= end());
+ }
+ PERFETTO_DCHECK(next_chunk_ptr >= search_end && next_chunk_ptr <= end());
+ return next_chunk_ptr - search_end;
+}
+
+void TraceBuffez::AddPaddingRecord(size_t size) {
+ PERFETTO_DCHECK(size >= sizeof(ChunkRecord) && size <= ChunkRecord::kMaxSize);
+ ChunkRecord record(size);
+ record.is_padding = 1;
+ TRACE_BUFFER_DLOG("AddPaddingRecord @ [%lu - %lu] %zu", wptr_ - begin(),
+ wptr_ - begin() + size, size);
+ WriteChunkRecord(record, nullptr, size - sizeof(ChunkRecord));
+ // |wptr_| is deliberately not advanced when writing a padding record.
+}
+
+bool TraceBuffez::TryPatchChunkContents(ProducerID producer_id,
+ WriterID writer_id,
+ ChunkID chunk_id,
+ size_t patch_offset_untrusted,
+ std::array<uint8_t, kPatchLen> patch) {
+ ChunkMeta::Key key(producer_id, writer_id, chunk_id);
+ auto it = index_.find(key);
+ if (it == index_.end()) {
+ stats_.failed_patches++;
+ return false;
+ }
+ const ChunkMeta& chunk_meta = it->second;
+
+ // Check that the index is consistent with the actual ProducerID/WriterID
+ // stored in the ChunkRecord.
+ PERFETTO_DCHECK(ChunkMeta::Key(*chunk_meta.chunk_record) == key);
+ uint8_t* chunk_begin = reinterpret_cast<uint8_t*>(chunk_meta.chunk_record);
+ PERFETTO_DCHECK(chunk_begin >= begin());
+ uint8_t* chunk_end = chunk_begin + chunk_meta.chunk_record->size;
+ PERFETTO_DCHECK(chunk_end <= end());
+
+ static_assert(kPatchLen == SharedMemoryABI::kPacketHeaderSize,
+ "kPatchLen out of sync with SharedMemoryABI");
+
+ uint8_t* ptr = chunk_begin + sizeof(ChunkRecord) + patch_offset_untrusted;
+ TRACE_BUFFER_DLOG("PatchChunk {%" PRIu32 ",%" PRIu32
+ ",%u} size=%zu @ %zu with {%02x %02x %02x %02x}",
+ producer_id, writer_id, chunk_id, chunk_end - chunk_begin,
+ patch_offset_untrusted, patch[0], patch[1], patch[2],
+ patch[3]);
+ if (ptr < chunk_begin + sizeof(ChunkRecord) || ptr > chunk_end - kPatchLen) {
+ // Either the IPC was so slow and in the meantime the writer managed to wrap
+ // over |chunk_id| or the producer sent a malicious IPC.
+ stats_.failed_patches++;
+ return false;
+ }
+
+ // DCHECK that we are writing into a size-field zero-filled by
+ // trace_writer_impl.cc and that we are not writing over other valid data.
+ char zero[kPatchLen]{};
+ PERFETTO_DCHECK(memcmp(ptr, &zero, kPatchLen) == 0);
+
+ memcpy(ptr, &patch, kPatchLen);
+ TRACE_BUFFER_DLOG(
+ "Chunk raw (after patch): %s",
+ HexDump(chunk_begin, chunk_meta.chunk_record->size).c_str());
+ stats_.succeeded_patches++;
+ return true;
+}
+
+void TraceBuffez::BeginRead() {
+ read_iter_ = GetReadIterForSequence(index_.begin());
+#if PERFETTO_DCHECK_IS_ON()
+ changed_since_last_read_ = false;
+#endif
+}
+
+TraceBuffez::SequenceIterator TraceBuffez::GetReadIterForSequence(
+ ChunkMap::iterator seq_begin) {
+ SequenceIterator iter;
+ iter.seq_begin = seq_begin;
+ if (seq_begin == index_.end()) {
+ iter.cur = iter.seq_end = index_.end();
+ return iter;
+ }
+
+#if PERFETTO_DCHECK_IS_ON()
+ // Either |seq_begin| is == index_.begin() or the item immediately before must
+ // belong to a different {ProducerID, WriterID} sequence.
+ if (seq_begin != index_.begin() && seq_begin != index_.end()) {
+ auto prev_it = seq_begin;
+ prev_it--;
+ PERFETTO_DCHECK(
+ seq_begin == index_.begin() ||
+ std::tie(prev_it->first.producer_id, prev_it->first.writer_id) <
+ std::tie(seq_begin->first.producer_id, seq_begin->first.writer_id));
+ }
+#endif
+
+ // Find the first entry that has a greater {ProducerID, WriterID} (or just
+ // index_.end() if we reached the end).
+ ChunkMeta::Key key = seq_begin->first; // Deliberate copy.
+ key.chunk_id = kMaxChunkID;
+ iter.seq_end = index_.upper_bound(key);
+ PERFETTO_DCHECK(iter.seq_begin != iter.seq_end);
+
+ // Now find the first entry between [seq_begin, seq_end) that is
+ // > last_chunk_id_. This is where we the sequence will start (see notes about
+ // wrapping in the header).
+ auto producer_and_writer_id = std::make_pair(key.producer_id, key.writer_id);
+ PERFETTO_DCHECK(last_chunk_id_.count(producer_and_writer_id));
+ iter.wrapping_id = last_chunk_id_[producer_and_writer_id];
+ key.chunk_id = iter.wrapping_id;
+ iter.cur = index_.upper_bound(key);
+ if (iter.cur == iter.seq_end)
+ iter.cur = iter.seq_begin;
+ return iter;
+}
+
+void TraceBuffez::SequenceIterator::MoveNext() {
+ // Note: |seq_begin| might be == |seq_end|.
+ if (cur == seq_end || cur->first.chunk_id == wrapping_id) {
+ cur = seq_end;
+ return;
+ }
+ if (++cur == seq_end)
+ cur = seq_begin;
+}
+
+bool TraceBuffez::ReadNextTracePacket(Slices* slices) {
+ // Note: MoveNext() moves only within the next chunk within the same
+ // {ProducerID, WriterID} sequence. Here we want to:
+ // - return the next patched+complete packet in the current sequence, if any.
+ // - return the first patched+complete packet in the next sequence, if any.
+ // - return false if none of the above is found.
+ TRACE_BUFFER_DLOG("ReadNextTracePacket()");
+#if PERFETTO_DCHECK_IS_ON()
+ PERFETTO_DCHECK(!changed_since_last_read_);
+#endif
+ for (;; read_iter_.MoveNext()) {
+ if (PERFETTO_UNLIKELY(!read_iter_.is_valid())) {
+ // We ran out of chunks in the current {ProducerID, WriterID} sequence or
+ // we just reached the index_.end().
+
+ if (PERFETTO_UNLIKELY(read_iter_.seq_end == index_.end()))
+ return false;
+
+ // We reached the end of sequence, move to the next one.
+ // Note: ++read_iter_.seq_end might become index_.end(), but
+ // GetReadIterForSequence() knows how to deal with that.
+ read_iter_ = GetReadIterForSequence(read_iter_.seq_end);
+ PERFETTO_DCHECK(read_iter_.is_valid() && read_iter_.cur != index_.end());
+ }
+
+ ChunkMeta& chunk_meta = *read_iter_;
+
+ // At this point we have a chunk in |chunk_meta| that has not been fully
+ // read. We don't know yet whether we have enough data to read the full
+ // packet (in the case it's fragmented over several chunks) and we are about
+ // to find that out. Specifically:
+ // A) If the first fragment is unread and is a fragment continuing from a
+ // previous chunk, it means we have missed the previous ChunkID. In
+ // fact, if this wasn't the case, a previous call to ReadNext() shouldn't
+ // have moved the cursor to this chunk.
+ // B) Any fragment > 0 && < last is always readable. By definition an inner
+ // packet is never fragmented and hence doesn't require neither stitching
+ // nor any out-of-band patching. The same applies to the last packet
+ // iff it doesn't continue on the next chunk.
+ // C) If the last packet (which might be also the only packet in the chunk)
+ // is a fragment and continues on the next chunk, we peek at the next
+ // chunks and, if we have all of them, mark as read and move the cursor.
+ //
+ // +---------------+ +-------------------+ +---------------+
+ // | ChunkID: 1 | | ChunkID: 2 | | ChunkID: 3 |
+ // |---------------+ +-------------------+ +---------------+
+ // | Packet 1 | | | | ... Packet 3 |
+ // | Packet 2 | | ... Packet 3 ... | | Packet 4 |
+ // | Packet 3 ... | | | | Packet 5 ... |
+ // +---------------+ +-------------------+ +---------------+
+
+ PERFETTO_DCHECK(chunk_meta.num_fragments_read <= chunk_meta.num_fragments);
+ while (chunk_meta.num_fragments_read < chunk_meta.num_fragments) {
+ enum { kSkip = 0, kReadOnePacket, kTryReadAhead } action;
+ if (chunk_meta.num_fragments_read == 0) {
+ if (chunk_meta.flags & kFirstPacketContinuesFromPrevChunk) {
+ action = kSkip; // Case A.
+ } else if (chunk_meta.num_fragments == 1 &&
+ (chunk_meta.flags & kLastPacketContinuesOnNextChunk)) {
+ action = kTryReadAhead; // Case C.
+ } else {
+ action = kReadOnePacket; // Case B.
+ }
+ } else if (chunk_meta.num_fragments_read < chunk_meta.num_fragments - 1 ||
+ !(chunk_meta.flags & kLastPacketContinuesOnNextChunk)) {
+ action = kReadOnePacket; // Case B.
+ } else {
+ action = kTryReadAhead; // Case C.
+ }
+
+ TRACE_BUFFER_DLOG(" chunk %u, packet %hu of %hu, action=%d",
+ read_iter_.chunk_id(), chunk_meta.num_fragments_read,
+ chunk_meta.num_fragments, action);
+
+ if (action == kSkip) {
+ // This fragment will be skipped forever, not just in this ReadPacket()
+ // iteration. This happens by virtue of ReadNextPacketInChunk()
+ // incrementing the |num_fragments_read| and marking the fragment as
+ // read even if we didn't really.
+ ReadNextPacketInChunk(&chunk_meta, nullptr);
+ continue;
+ }
+
+ if (action == kReadOnePacket) {
+ // The easy peasy case B.
+ if (PERFETTO_LIKELY(ReadNextPacketInChunk(&chunk_meta, slices)))
+ return true;
+
+ // In extremely rare cases (producer bugged / malicious) the chunk might
+ // contain an invalid fragment. In such case we don't want to stall the
+ // sequence but just skip the chunk and move on.
+ break;
+ }
+
+ PERFETTO_DCHECK(action == kTryReadAhead);
+ ReadAheadResult ra_res = ReadAhead(slices);
+ if (ra_res == ReadAheadResult::kSucceededReturnSlices) {
+ stats_.fragment_readahead_successes++;
+ return true;
+ }
+
+ if (ra_res == ReadAheadResult::kFailedMoveToNextSequence) {
+ // readahead didn't find a contigous packet sequence. We'll try again
+ // on the next ReadPacket() call.
+ stats_.fragment_readahead_failures++;
+
+ // TODO(primiano): optimization: this MoveToEnd() is the reason why
+ // MoveNext() (that is called in the outer for(;;MoveNext)) needs to
+ // deal gracefully with the case of |cur|==|seq_end|. Maybe we can do
+ // something to avoid that check by reshuffling the code here?
+ read_iter_.MoveToEnd();
+
+ // This break will go back to beginning of the for(;;MoveNext()). That
+ // will move to the next sequence because we set the read iterator to
+ // its end.
+ break;
+ }
+
+ PERFETTO_DCHECK(ra_res == ReadAheadResult::kFailedStayOnSameSequence);
+ } // while(...) [iterate over packet fragments for the current chunk].
+ } // for(;;MoveNext()) [iterate over chunks].
+}
+
+TraceBuffez::ReadAheadResult TraceBuffez::ReadAhead(Slices* slices) {
+ static_assert(static_cast<ChunkID>(kMaxChunkID + 1) == 0,
+ "relying on kMaxChunkID to wrap naturally");
+ TRACE_BUFFER_DLOG(" readahead start @ chunk %u", read_iter_.chunk_id());
+ ChunkID next_chunk_id = read_iter_.chunk_id() + 1;
+ SequenceIterator it = read_iter_;
+ for (it.MoveNext(); it.is_valid(); it.MoveNext(), next_chunk_id++) {
+ // We should stay within the same sequence while iterating here.
+ PERFETTO_DCHECK(it.producer_id() == read_iter_.producer_id() &&
+ it.writer_id() == read_iter_.writer_id());
+
+ TRACE_BUFFER_DLOG(" expected chunk ID: %u, actual ID: %u", next_chunk_id,
+ it.chunk_id());
+
+ if (PERFETTO_UNLIKELY((*it).num_fragments == 0))
+ continue;
+
+ // If we miss the next chunk, stop looking in the current sequence and
+ // try another sequence. This chunk might come in the near future.
+ // The second condition is the edge case of a buggy/malicious
+ // producer. The ChunkID is contiguous but its flags don't make sense.
+ if (it.chunk_id() != next_chunk_id ||
+ PERFETTO_UNLIKELY(
+ !((*it).flags & kFirstPacketContinuesFromPrevChunk))) {
+ return ReadAheadResult::kFailedMoveToNextSequence;
+ }
+
+ // This is the case of an intermediate chunk which contains only one
+ // fragment which continues on the next. This is the case for large
+ // packets, e.g.: [Packet0, Packet1(0)] [Packet1(1)] [Packet1(2), ...]
+ // (Packet1(X) := fragment X of Packet1).
+ if ((*it).num_fragments == 1 &&
+ ((*it).flags & kLastPacketContinuesOnNextChunk)) {
+ continue;
+ }
+
+ // We made it! We got all fragments for the packet without holes.
+ TRACE_BUFFER_DLOG(" readahead success @ chunk %u", it.chunk_id());
+ PERFETTO_DCHECK(((*it).num_fragments == 1 &&
+ !((*it).flags & kLastPacketContinuesOnNextChunk)) ||
+ (*it).num_fragments > 1);
+
+ // Now let's re-iterate over the [read_iter_, it] sequence and mark
+ // all the fragments as read.
+ bool packet_corruption = false;
+ for (;;) {
+ PERFETTO_DCHECK(read_iter_.is_valid());
+ TRACE_BUFFER_DLOG(" commit chunk %u", read_iter_.chunk_id());
+ if (PERFETTO_LIKELY((*read_iter_).num_fragments > 0)) {
+ // In the unlikely case of a corrupted packet, invalidate the all
+ // stitching and move on to the next chunk in the same sequence,
+ // if any.
+ packet_corruption |= !ReadNextPacketInChunk(&*read_iter_, slices);
+ }
+ if (read_iter_.cur == it.cur)
+ break;
+ read_iter_.MoveNext();
+ } // for(;;)
+ PERFETTO_DCHECK(read_iter_.cur == it.cur);
+
+ if (PERFETTO_UNLIKELY(packet_corruption)) {
+ slices->clear();
+ return ReadAheadResult::kFailedStayOnSameSequence;
+ }
+
+ return ReadAheadResult::kSucceededReturnSlices;
+ } // for(it...) [readahead loop]
+ return ReadAheadResult::kFailedMoveToNextSequence;
+}
+
+bool TraceBuffez::ReadNextPacketInChunk(ChunkMeta* chunk_meta, Slices* slices) {
+ PERFETTO_DCHECK(chunk_meta->num_fragments_read < chunk_meta->num_fragments);
+ // TODO DCHECK for chunks that are still awaiting patching.
+
+ const uint8_t* record_begin =
+ reinterpret_cast<const uint8_t*>(chunk_meta->chunk_record);
+ const uint8_t* record_end = record_begin + chunk_meta->chunk_record->size;
+ const uint8_t* packets_begin = record_begin + sizeof(ChunkRecord);
+ const uint8_t* packet_begin = packets_begin + chunk_meta->cur_fragment_offset;
+ PERFETTO_CHECK(packet_begin >= packets_begin && packet_begin < record_end);
+
+ // A packet (or a fragment) starts with a varint stating its size, followed
+ // by its content. The varint shouldn't be larger than 4 bytes (just in case
+ // the producer is using a redundant encoding)
+ uint64_t packet_size = 0;
+ const uint8_t* packet_data = protozero::proto_utils::ParseVarInt(
+ packet_begin,
+ packet_begin + protozero::proto_utils::kMessageLengthFieldSize,
+ &packet_size);
+
+ const uint8_t* next_packet = packet_data + packet_size;
+ if (PERFETTO_UNLIKELY(next_packet <= packet_begin ||
+ next_packet > record_end)) {
+ PERFETTO_DCHECK(suppress_sanity_dchecks_for_testing_);
+ chunk_meta->cur_fragment_offset = 0;
+ chunk_meta->num_fragments_read = chunk_meta->num_fragments;
+ return false;
+ }
+ chunk_meta->cur_fragment_offset =
+ static_cast<uint16_t>(next_packet - packets_begin);
+ chunk_meta->num_fragments_read++;
+
+ if (PERFETTO_UNLIKELY(packet_size == 0))
+ return false;
+
+ if (PERFETTO_LIKELY(slices))
+ slices->emplace_back(packet_data, static_cast<size_t>(packet_size));
+
+ return true;
+}
+
+} // namespace perfetto
diff --git a/src/tracing/core/trace_buffer.h b/src/tracing/core/trace_buffer.h
new file mode 100644
index 0000000..29a70c6
--- /dev/null
+++ b/src/tracing/core/trace_buffer.h
@@ -0,0 +1,518 @@
+/*
+ * Copyright (C) 2018 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_TRACING_CORE_TRACE_BUFFER_H_
+#define SRC_TRACING_CORE_TRACE_BUFFER_H_
+
+#include <stdint.h>
+#include <string.h>
+
+#include <limits>
+#include <map>
+#include <tuple>
+
+#include "perfetto/base/logging.h"
+#include "perfetto/base/page_allocator.h"
+#include "perfetto/tracing/core/basic_types.h"
+#include "perfetto/tracing/core/slice.h"
+
+namespace perfetto {
+
+// The main buffer, owned by the tracing service, where all the trace data is
+// ultimately stored into. The service will own several instances of this class,
+// at least one per active consumer (as defined in the |buffers| section of
+// trace_config.proto) and will copy chunks from the producer's shared memory
+// buffers into here when a NotifySharedMemoryUpdate IPC is received.
+//
+// Writing into the buffer
+// -----------------------
+// Data is copied from the SMB(s) using CopyChunkUntrusted(). The buffer will
+// hence contain data coming from different producers and different writer
+// sequences, more specifically:
+// - The service receives data by several producer(s), identified by their ID.
+// - Each producer writes several sequences identified by the same WriterID.
+// (they correspond to TraceWriter instances in the producer).
+// - Each Writer writes, in order, several chunks.
+// - Each chunk contains zero, one, or more TracePacket(s), or even just
+// fragments of packets (when they span across several chunks).
+//
+// So at any point in time, the buffer will contain a variable number of logical
+// sequences identified by the {ProducerID, WriterID} tuple. Any given chunk
+// will only contain packets (or fragments) belonging to the same sequence.
+//
+// The buffer operates by default as a ring buffer. Chunks are (over-)written
+// in the same order of the CopyChunkUntrusted() calls. When overwriting old
+// content, entire chunks are overwritten or clobbered. The buffer never leaves
+// a partial chunk around. Chunks' payload is copied as-is, but their header is
+// not and is repacked in order to keep the ProducerID around.
+//
+// Chunks are stored in the buffer next to each other. Each chunk is prefixed by
+// an inline header (ChunkRecord), which contains most of the fields of the
+// SharedMemoryABI ChunkHeader + the ProducerID + the size of the payload.
+// It's a conventional binary object stream essentially, where each ChunkRecord
+// tells where it ends and hence where to find the next one, like this:
+//
+// .-------------------------. 16 byte boundary
+// | ChunkRecord: 16 bytes |
+// | - chunk id: 4 bytes |
+// | - producer id: 2 bytes |
+// | - writer id: 2 bytes |
+// | - #fragments: 2 bytes |
+// +-----+ - record size: 2 bytes |
+// | | - flags+pad: 4 bytes |
+// | +-------------------------+
+// | | |
+// | : Chunk payload :
+// | | |
+// | +-------------------------+
+// | | Optional padding |
+// +---> +-------------------------+ 16 byte boundary
+// | ChunkRecord |
+// : :
+// Chunks stored in the buffer are always rounded up to 16 bytes (that is
+// sizeof(ChunkRecord)), in order to avoid further inner fragmentation.
+// Special "padding" chunks can be put in the buffer, e.g. in the case when we
+// try to write a chunk of size N while the write pointer is at the end of the
+// buffer, but the write pointer is < N bytes from the end (and hence needs to
+// wrap over).
+// Because of this, the buffer is self-describing: the contents of the buffer
+// can be reconstructed by just looking at the buffer content (this will be
+// quite useful in future to recover the buffer from crash reports).
+//
+// However, in order to keep some operations (patching and reading) fast, a
+// lookaside index is maintained (in |index_|), keeping each chunk in the buffer
+// indexed by their {ProducerID, WriterID, ChunkID} tuple.
+//
+// Patching data out-of-band
+// -------------------------
+// This buffer also supports patching chunks' payload out-of-band, after they
+// have been stored. This is to allow producers to backfill the "size" fields
+// of the protos that spawn across several chunks, when the previous chunks are
+// returned to the service. The MaybePatchChunkContents() deals with the fact
+// that a chunk might have been lost (because of wrapping) by the time the OOB
+// IPC comes.
+//
+// Reading from the buffer
+// -----------------------
+// This class supports one reader only (the consumer). Reads are NOT idempotent
+// as they move the read cursors around. Reading back the buffer is the most
+// conceptually complex part. The ReadPacket() method, in fact, operates with
+// whole packet granularity. Packets are returned only when all their fragments
+// are available.
+// This class takes care of:
+// - Gluing packets within the same sequence, even if they are not stored
+// adjacently in the buffer.
+// - Re-ordering chunks within a sequence (using the ChunkID, which wraps).
+// - Detecting holes in packet fragments (because of loss of chunks).
+// Reads guarantee that packets for the same sequence are read in FIFO order
+// (according to their ChunkID), but don't give any guarantee about the read
+// order of packets from different sequences (see ReadPacket() comments below).
+//
+// TODO(primiano): the name of this class is deliberately typo-ed as a temporary
+// situation until we replace TraceBuffer within service_impl.cc.
+class TraceBuffez {
+ public:
+ static const size_t InlineChunkHeaderSize; // For test/fake_packet.{cc,h}.
+ static constexpr size_t kPatchLen = 4; // SharedMemoryABI::kPacketHeaderSize.
+
+ struct Stats {
+ size_t failed_patches = 0;
+ size_t succeeded_patches = 0;
+ size_t fragment_readahead_successes = 0;
+ size_t fragment_readahead_failures = 0;
+ size_t write_wrap_count = 0;
+ // TODO(primiano): add packets_{read,written}.
+ // TODO(primiano): add bytes_{read,written}.
+ // TODO(primiano): add bytes_lost_for_padding.
+ };
+
+ // Can return nullptr if the memory allocation fails.
+ static std::unique_ptr<TraceBuffez> Create(size_t size_in_bytes);
+
+ ~TraceBuffez();
+
+ // Copies a Chunk from a producer Shared Memory Buffer into the trace buffer.
+ // |src| points to the first packet in the SharedMemoryABI's chunk shared
+ // with an untrusted producer. "untrusted" here means: the producer might be
+ // malicious and might change |src| concurrently while we read it (internally
+ // this method memcpy()-s first the chunk before processing it).
+ // None of the arguments should be trusted, unless otherwise stated. We can
+ // trust that |src| points to a valid memory area, but not its contents.
+ void CopyChunkUntrusted(ProducerID producer_id_trusted,
+ WriterID writer_id,
+ ChunkID chunk_id,
+ uint16_t num_fragments,
+ uint8_t chunk_flags,
+ const uint8_t* src,
+ size_t size);
+
+ // Patches SharedMemoryABI::kPacketHeaderSize bytes at the given
+ // |patch_offset|, replacing them with the contents of |patch_value|, if the
+ // given chunk exists. Does nothing if the given ChunkID is gone.
+ // Returns true if the chunk has been found and patched, false otherwise.
+ bool TryPatchChunkContents(ProducerID,
+ WriterID,
+ ChunkID,
+ size_t patch_offset,
+ std::array<uint8_t, kPatchLen> patch);
+
+ // To read the contents of the buffer the caller needs to:
+ // BeginRead()
+ // while (ReadNextTracePacket(packet_fragments)) { ... }
+ // No other calls to any other method should be interleaved between
+ // BeginRead() and ReadNextTracePacket().
+ // Reads in the TraceBuffer are NOT idempotent.
+ void BeginRead();
+
+ // Returns the next packet in the buffer, if any. Returns false if no packets
+ // can be read at this point.
+ // This function returns only complete packets. Specifically:
+ // When there is at least one complete packet in the buffer, this function
+ // returns true and populates the |slices| argument with the boundaries of
+ // each fragment for one packet.
+ // The output |slices|.size() will be >= 1 when this function returns true.
+ // When there are no whole packets eligible to read (e.g. we are still missing
+ // fragments) this function returns false.
+ // This function guarantees also that packets for a given
+ // {ProducerID, WriterID} are read in FIFO order.
+ // This function does not guarantee any ordering w.r.t. packets belonging to
+ // different WriterID(s). For instance, given the following packets copied
+ // into the buffer:
+ // {ProducerID: 1, WriterID: 1}: P1 P2 P3
+ // {ProducerID: 1, WriterID: 2}: P4 P5 P6
+ // {ProducerID: 2, WriterID: 1}: P7 P8 P9
+ // The following read sequence is possible:
+ // P1, P4, P7, P2, P3, P5, P8, P9, P6
+ // But the following is guaranteed to NOT happen:
+ // P1, P5, P7, P4 (P4 cannot come after P5)
+ bool ReadNextTracePacket(Slices* slices);
+
+ const Stats& stats() const { return stats_; }
+
+ private:
+ friend class TraceBufferTest;
+
+ // ChunkRecord is a Chunk header stored inline in the |data_| buffer, before
+ // the chunk payload (the packets' data). The |data_| buffer looks like this:
+ // +---------------+------------------++---------------+-----------------+
+ // | ChunkRecord 1 | Chunk payload 1 || ChunkRecord 2 | Chunk payload 2 | ...
+ // +---------------+------------------++---------------+-----------------+
+ // Most of the ChunkRecord fields are copied from SharedMemoryABI::ChunkHeader
+ // (the chunk header used in the the shared memory buffers).
+ // A ChunkRecord can be a special "padding" record. In this case its payload
+ // should be ignored and the record should be just skipped.
+ //
+ // Full page move optimization:
+ // This struct has to be exactly (sizeof(PageHeader) + sizeof(ChunkHeader))
+ // (from shared_memory_abi.h) to allow full page move optimizations
+ // (TODO(primiano): not implemented yet). In the special case of moving a full
+ // 4k page that contains only one chunk, in fact, we can just ask the kernel
+ // to move the full SHM page (see SPLICE_F_{GIFT,MOVE}) and overlay the
+ // ChunkRecord on top of the moved SMB's header (page + chunk header).
+ // This special requirement is covered by static_assert(s) in the .cc file.
+ struct ChunkRecord {
+ explicit ChunkRecord(size_t sz) : flags{0}, is_padding{0} {
+ PERFETTO_DCHECK(sz >= sizeof(ChunkRecord) &&
+ sz % sizeof(ChunkRecord) == 0 && sz <= kMaxSize);
+ size = static_cast<decltype(size)>(sz);
+ }
+
+ bool is_valid() const { return size != 0; }
+
+ // Keep this structure packed and exactly 16 bytes (128 bits) big.
+
+ // [32 bits] Monotonic counter within the same writer_id.
+ ChunkID chunk_id = 0;
+
+ // [16 bits] ID of the Producer from which the Chunk was copied from.
+ ProducerID producer_id = 0;
+
+ // [16 bits] Unique per Producer (but not within the service).
+ // If writer_id == kWriterIdPadding the record should just be skipped.
+ WriterID writer_id = 0;
+
+ // Number of fragments contained in the chunk.
+ uint16_t num_fragments = 0;
+
+ // Size in bytes, including sizeof(ChunkRecord) itself.
+ uint16_t size;
+
+ uint8_t flags : 6; // See SharedMemoryABI::ChunkHeader::flags.
+ uint8_t is_padding : 1;
+ uint8_t unused_flag : 1;
+
+ // Not strictly needed, can be reused for more fields in the future. But
+ // right now helps to spot chunks in hex dumps.
+ char unused[3] = {'C', 'H', 'U'};
+
+ static constexpr size_t kMaxSize =
+ std::numeric_limits<decltype(size)>::max();
+ };
+
+ // Lookaside index entry. This serves two purposes:
+ // 1) Allow a fast lookup of ChunkRecord by their ID (the tuple
+ // {ProducerID, WriterID, ChunkID}). This is used when applying out-of-band
+ // patches to the contents of the chunks after they have been copied into
+ // the TraceBuffer.
+ // 2) keep the chunks ordered by their ID. This is used when reading back.
+ // 3) Keep metadata about the status of the chunk, e.g. whether the contents
+ // have been read already and should be skipped in a future read pass.
+ // This struct should not have any field that is essential for reconstructing
+ // the contents of the buffer from a crash dump.
+ struct ChunkMeta {
+ // Key used for sorting in the map.
+ struct Key {
+ Key(ProducerID p, WriterID w, ChunkID c)
+ : producer_id{p}, writer_id{w}, chunk_id{c} {}
+
+ explicit Key(const ChunkRecord& cr)
+ : Key(cr.producer_id, cr.writer_id, cr.chunk_id) {}
+
+ // Note that this sorting doesn't keep into account the fact that ChunkID
+ // will wrap over at some point. The extra logic in SequenceIterator deals
+ // with that.
+ bool operator<(const Key& other) const {
+ return std::tie(producer_id, writer_id, chunk_id) <
+ std::tie(other.producer_id, other.writer_id, other.chunk_id);
+ }
+
+ bool operator==(const Key& other) const {
+ return std::tie(producer_id, writer_id, chunk_id) ==
+ std::tie(other.producer_id, other.writer_id, other.chunk_id);
+ }
+
+ // These fields should match at all times the corresponding fields in
+ // the |chunk_record|. They are copied here purely for efficiency to avoid
+ // dereferencing the buffer all the time.
+ ProducerID producer_id;
+ WriterID writer_id;
+ ChunkID chunk_id;
+ };
+
+ ChunkMeta(ChunkRecord* c, uint16_t p, uint8_t f)
+ : chunk_record{c}, flags{f}, num_fragments{p} {}
+
+ ChunkRecord* const chunk_record; // Addr of ChunkRecord within |data_|.
+ const uint8_t flags = 0; // See SharedMemoryABI::flags.
+ const uint16_t num_fragments = 0; // Total number of packet fragments.
+ uint16_t num_fragments_read = 0; // Number of fragments already read.
+
+ // The start offset of the next fragment (the |num_fragments_read|-th) to be
+ // read. This is the offset in bytes from the beginning of the ChunkRecord's
+ // payload (the 1st fragment starts at |chunk_record| +
+ // sizeof(ChunkRecord)).
+ uint16_t cur_fragment_offset = 0;
+
+ // If != 0 the last fragment in the chunk cannot be read, even if the
+ // subsequent ChunkID is already available, until a patch is applied through
+ // MaybePatchChunkContents().
+ // TODO(primiano): implement this logic in next CL.
+ };
+
+ using ChunkMap = std::map<ChunkMeta::Key, ChunkMeta>;
+
+ // Allows to iterate over a sub-sequence of |index_| for all keys belonging to
+ // the same {ProducerID,WriterID}. Furthermore takes into account the wrapping
+ // of ChunkID. Instances are valid only as long as the |index_| is not
+ // altered (can be used safely only between adjacent ReadPacket() calls).
+ // The order of the iteration will proceed in the following order:
+ // |wrapping_id| + 1 -> |seq_end|, |seq_begin| -> |wrapping_id|.
+ // Practical example:
+ // - Assume that kMaxChunkID == 7
+ // - Assume that we have all 8 chunks in the range (0..7).
+ // - Hence, |seq_begin| == c0, |seq_end| == c7
+ // - Assume |wrapping_id| = 4 (c4 is the last chunk copied over
+ // through a CopyChunkUntrusted()).
+ // The resulting iteration order will be: c5, c6, c7, c0, c1, c2, c3, c4.
+ struct SequenceIterator {
+ // Points to the 1st key (the one with the numerically min ChunkID).
+ ChunkMap::iterator seq_begin;
+
+ // Points one past the last key (the one with the numerically max ChunkID).
+ ChunkMap::iterator seq_end;
+
+ // Current iterator, always >= seq_begin && <= seq_end.
+ ChunkMap::iterator cur;
+
+ // The latest ChunkID written. Determines the start/end of the sequence.
+ ChunkID wrapping_id;
+
+ bool is_valid() const { return cur != seq_end; }
+
+ ProducerID producer_id() const {
+ PERFETTO_DCHECK(is_valid());
+ return cur->first.producer_id;
+ }
+
+ WriterID writer_id() const {
+ PERFETTO_DCHECK(is_valid());
+ return cur->first.writer_id;
+ }
+
+ ChunkID chunk_id() const {
+ PERFETTO_DCHECK(is_valid());
+ return cur->first.chunk_id;
+ }
+
+ ChunkMeta& operator*() {
+ PERFETTO_DCHECK(is_valid());
+ return cur->second;
+ }
+
+ // Moves |cur| to the next chunk in the index.
+ // is_valid() will become false after calling this, if this was the last
+ // entry of the sequence.
+ void MoveNext();
+
+ void MoveToEnd() { cur = seq_end; }
+ };
+
+ enum class ReadAheadResult {
+ kSucceededReturnSlices,
+ kFailedMoveToNextSequence,
+ kFailedStayOnSameSequence,
+ };
+
+ TraceBuffez();
+ TraceBuffez(const TraceBuffez&) = delete;
+ TraceBuffez& operator=(const TraceBuffez&) = delete;
+
+ bool Initialize(size_t size);
+
+ // Returns an object that allows to iterate over chunks in the |index_| that
+ // have the same {ProducerID, WriterID} of
+ // |seq_begin.first.{producer,writer}_id|. |seq_begin| must be an iterator to
+ // the first entry in the |index_| that has a different {ProducerID, WriterID}
+ // from the previous one. It is valid for |seq_begin| to be == index_.end()
+ // (i.e. if the index is empty). The iteration takes care of ChunkID wrapping,
+ // by using |last_chunk_id_|.
+ SequenceIterator GetReadIterForSequence(ChunkMap::iterator seq_begin);
+
+ // Used as a last resort when a buffer corruption is detected.
+ void ClearContentsAndResetRWCursors();
+
+ // Adds a padding record of the given size (must be a multiple of
+ // sizeof(ChunkRecord)).
+ void AddPaddingRecord(size_t);
+
+ // Look for contiguous fragment of the same packet starting from |read_iter_|.
+ // If a contiguous packet is found, all the fragments are pushed into |slices|
+ // and the function returns kSucceededReturnSlices. If not, the function
+ // returns either kFailedMoveToNextSequence or kFailedStayOnSameSequence,
+ // telling the caller to continue looking for packets.
+ ReadAheadResult ReadAhead(Slices* slices);
+
+ // Deletes (by marking the record invalid and removing form the index) all
+ // chunks from |wptr_| to |wptr_| + |bytes_to_clear|. Returns the size of the
+ // gap left between the next valid Chunk and the end of the deletion range, or
+ // 0 if such next valid chunk doesn't exist (if the buffer is still zeroed).
+ // Graphically, assume the initial situation is the following (|wptr_| = 10).
+ // |0 |10 (wptr_) |30 |40 |60
+ // +---------+-----------------+---------+-------------------+---------+
+ // | Chunk 1 | Chunk 2 | Chunk 3 | Chunk 4 | Chunk 5 |
+ // +---------+-----------------+---------+-------------------+---------+
+ // |_________Deletion range_______|~~return value~~|
+ //
+ // A call to DeleteNextChunksFor(32) will remove chunks 2,3,4 and return 18
+ // (60 - 42), the distance between chunk 5 and the end of the deletion range.
+ size_t DeleteNextChunksFor(size_t bytes_to_clear);
+
+ // Decodes the boundaries of the next packet (or a fragment) pointed by
+ // ChunkMeta and pushes that into |Slices*|. It also increments the
+ // |num_fragments_read| counter.
+ // The Slices pointer can be nullptr, in which case the read state is still
+ // advanced.
+ bool ReadNextPacketInChunk(ChunkMeta*, Slices*);
+
+ void DcheckIsAlignedAndWithinBounds(const uint8_t* ptr) const {
+ PERFETTO_DCHECK(ptr >= begin() && ptr <= end() - sizeof(ChunkRecord));
+ PERFETTO_DCHECK(
+ (reinterpret_cast<uintptr_t>(ptr) & (alignof(ChunkRecord) - 1)) == 0);
+ }
+
+ ChunkRecord* GetChunkRecordAt(uint8_t* ptr) const {
+ DcheckIsAlignedAndWithinBounds(ptr);
+ return reinterpret_cast<ChunkRecord*>(ptr);
+ }
+
+ // |src| can be nullptr (in which case |size| must be ==
+ // record.size - sizeof(ChunkRecord)), for the case of writing a padding
+ // record. |wptr_| is NOT advanced by this function, the caller must do that.
+ void WriteChunkRecord(const ChunkRecord& record,
+ const uint8_t* src,
+ size_t size) {
+ // Note: |record.size| will be slightly bigger than |size| because of the
+ // ChunkRecord header and rounding, to ensure that all ChunkRecord(s) are
+ // multiple of sizeof(ChunkRecord). The invariant is:
+ // record.size >= |size| + sizeof(ChunkRecord) (== if no rounding).
+ PERFETTO_DCHECK(size <= ChunkRecord::kMaxSize);
+ PERFETTO_DCHECK(record.size >= sizeof(record));
+ PERFETTO_DCHECK(record.size % sizeof(record) == 0);
+ PERFETTO_DCHECK(record.size >= size + sizeof(record));
+ PERFETTO_CHECK(record.size <= size_to_end());
+ DcheckIsAlignedAndWithinBounds(wptr_);
+
+ // Deliberately not a *D*CHECK.
+ PERFETTO_CHECK(wptr_ + sizeof(record) + size <= end());
+ memcpy(wptr_, &record, sizeof(record));
+ if (PERFETTO_LIKELY(src)) {
+ memcpy(wptr_ + sizeof(record), src, size);
+ } else {
+ PERFETTO_DCHECK(size == record.size - sizeof(record));
+ }
+ const size_t rounding_size = record.size - sizeof(record) - size;
+ memset(wptr_ + sizeof(record) + size, 0, rounding_size);
+ }
+
+ uint8_t* begin() const { return reinterpret_cast<uint8_t*>(data_.get()); }
+ uint8_t* end() const { return begin() + size_; }
+ size_t size_to_end() const { return end() - wptr_; }
+
+ base::PageAllocator::UniquePtr data_;
+ size_t size_ = 0; // Size in bytes of |data_|.
+ size_t max_chunk_size_ = 0; // Max size in bytes allowed for a chunk.
+ uint8_t* wptr_ = nullptr; // Write pointer.
+
+ // An index that keeps track of the positions and metadata of each
+ // ChunkRecord.
+ ChunkMap index_;
+
+ // Read iterator used for ReadNext(). It is reset by calling BeginRead().
+ // It becomes invalid after any call to methods that alters the |index_|.
+ SequenceIterator read_iter_;
+
+ // Keeps track of the last ChunkID written for a given writer.
+ // TODO(primiano): should clean up keys from this map. Right now this map
+ // grows without bounds (although realistically is not a problem unless we
+ // have too many producers/writers within the same trace session).
+ std::map<std::pair<ProducerID, WriterID>, ChunkID> last_chunk_id_;
+
+ // Statistics about buffer usage.
+ Stats stats_;
+
+#if PERFETTO_DCHECK_IS_ON()
+ bool changed_since_last_read_ = false;
+#endif
+
+ // When true disable some DCHECKs that have been put in place to detect
+ // bugs in the producers. This is for tests that feed malicious inputs and
+ // hence mimic a buggy producer.
+ bool suppress_sanity_dchecks_for_testing_ = false;
+};
+
+} // namespace perfetto
+
+#endif // SRC_TRACING_CORE_TRACE_BUFFER_H_
diff --git a/src/tracing/core/trace_buffer_unittest.cc b/src/tracing/core/trace_buffer_unittest.cc
new file mode 100644
index 0000000..0cb9ffb
--- /dev/null
+++ b/src/tracing/core/trace_buffer_unittest.cc
@@ -0,0 +1,919 @@
+/*
+ * Copyright (C) 2017 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 <string.h>
+
+#include <initializer_list>
+#include <random>
+#include <sstream>
+#include <vector>
+
+#include "perfetto/protozero/proto_utils.h"
+#include "perfetto/tracing/core/basic_types.h"
+#include "perfetto/tracing/core/shared_memory_abi.h"
+#include "src/tracing/core/trace_buffer.h"
+#include "src/tracing/test/fake_packet.h"
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace perfetto {
+
+using ::testing::ContainerEq;
+using ::testing::ElementsAre;
+using ::testing::IsEmpty;
+
+class TraceBufferTest : public testing::Test {
+ public:
+ using SequenceIterator = TraceBuffez::SequenceIterator;
+ using ChunkMetaKey = TraceBuffez::ChunkMeta::Key;
+ using ChunkRecord = TraceBuffez::ChunkRecord;
+
+ static constexpr uint8_t kContFromPrevChunk =
+ SharedMemoryABI::ChunkHeader::kFirstPacketContinuesFromPrevChunk;
+ static constexpr uint8_t kContOnNextChunk =
+ SharedMemoryABI::ChunkHeader::kLastPacketContinuesOnNextChunk;
+
+ FakeChunk CreateChunk(ProducerID p, WriterID w, ChunkID c) {
+ return FakeChunk(trace_buffer_.get(), p, w, c);
+ }
+
+ void ResetBuffer(size_t size_) {
+ trace_buffer_ = TraceBuffez::Create(size_);
+ ASSERT_TRUE(trace_buffer_);
+ }
+
+ bool TryPatchChunkContents(
+ ProducerID p,
+ WriterID w,
+ ChunkID c,
+ size_t offset,
+ std::array<uint8_t, TraceBuffez::kPatchLen> patch) {
+ return trace_buffer_->TryPatchChunkContents(p, w, c, offset, patch);
+ }
+
+ std::vector<FakePacketFragment> ReadPacket() {
+ std::vector<FakePacketFragment> fragments;
+ Slices slices;
+ if (!trace_buffer_->ReadNextTracePacket(&slices))
+ return fragments;
+ for (const Slice& slice : slices)
+ fragments.emplace_back(slice.start, slice.size);
+ return fragments;
+ }
+
+ void AppendChunks(
+ std::initializer_list<std::tuple<ProducerID, WriterID, ChunkID>> chunks) {
+ for (const auto& c : chunks) {
+ char seed =
+ static_cast<char>(std::get<0>(c) + std::get<1>(c) + std::get<2>(c));
+ CreateChunk(std::get<0>(c), std::get<1>(c), std::get<2>(c))
+ .AddPacket(4, seed)
+ .CopyIntoTraceBuffer();
+ }
+ }
+
+ bool IteratorSeqEq(ProducerID p,
+ WriterID w,
+ std::initializer_list<ChunkID> chunk_ids) {
+ std::stringstream expected_seq;
+ for (const auto& c : chunk_ids)
+ expected_seq << "{" << p << "," << w << "," << c << "},";
+
+ std::stringstream actual_seq;
+ for (auto it = GetReadIterForSequence(p, w); it.is_valid(); it.MoveNext()) {
+ actual_seq << "{" << it.producer_id() << "," << it.writer_id() << ","
+ << it.chunk_id() << "},";
+ }
+ std::string expected_seq_str = expected_seq.str();
+ std::string actual_seq_str = actual_seq.str();
+ EXPECT_EQ(expected_seq_str, actual_seq_str);
+ return expected_seq_str == actual_seq_str;
+ }
+
+ SequenceIterator GetReadIterForSequence(ProducerID p, WriterID w) {
+ TraceBuffez::ChunkMeta::Key key(p, w, 0);
+ return trace_buffer_->GetReadIterForSequence(
+ trace_buffer_->index_.lower_bound(key));
+ }
+
+ void SuppressSanityDchecksForTesting() {
+ trace_buffer_->suppress_sanity_dchecks_for_testing_ = true;
+ }
+
+ std::vector<ChunkMetaKey> GetIndex() {
+ std::vector<ChunkMetaKey> keys;
+ keys.reserve(trace_buffer_->index_.size());
+ for (const auto& it : trace_buffer_->index_)
+ keys.push_back(it.first);
+ return keys;
+ }
+
+ TraceBuffez* trace_buffer() { return trace_buffer_.get(); }
+ size_t size_to_end() { return trace_buffer_->size_to_end(); }
+
+ private:
+ std::unique_ptr<TraceBuffez> trace_buffer_;
+};
+
+// ----------------------
+// Main TraceBuffer tests
+// ----------------------
+
+// Note for the test code: remember that the resulting size of a chunk is:
+// SUM(packets) + 16 (that is sizeof(ChunkRecord)).
+// Also remember that chunks are rounded up to 16. So, unless we are testing the
+// rounding logic, might be a good idea to create chunks of that size.
+
+TEST_F(TraceBufferTest, ReadWrite_EmptyBuffer) {
+ ResetBuffer(4096);
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+// On each iteration writes a fixed-size chunk and reads it back.
+TEST_F(TraceBufferTest, ReadWrite_Simple) {
+ ResetBuffer(64 * 1024);
+ for (ChunkID chunk_id = 0; chunk_id < 1000; chunk_id++) {
+ char seed = static_cast<char>(chunk_id);
+ CreateChunk(ProducerID(1), WriterID(1), chunk_id)
+ .AddPacket(42, seed)
+ .CopyIntoTraceBuffer();
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(42, seed)));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+ }
+}
+
+TEST_F(TraceBufferTest, ReadWrite_OneChunkPerWriter) {
+ for (uint8_t num_writers = 1; num_writers <= 10; num_writers++) {
+ ResetBuffer(4096);
+ for (uint8_t i = 1; i <= num_writers; i++) {
+ ASSERT_EQ(32u, CreateChunk(ProducerID(i), WriterID(i), ChunkID(i))
+ .AddPacket(32 - 16, i)
+ .CopyIntoTraceBuffer());
+ }
+
+ // The expected read sequence now is: c3, c4, c5.
+ trace_buffer()->BeginRead();
+ for (uint8_t i = 1; i <= num_writers; i++)
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(32 - 16, i)));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+ } // for(num_writers)
+}
+
+// Writes chunk that up filling the buffer precisely until the end, like this:
+// [ c0: 512 ][ c1: 512 ][ c2: 1024 ][ c3: 2048 ]
+// | ---------------- 4k buffer --------------- |
+TEST_F(TraceBufferTest, ReadWrite_FillTillEnd) {
+ ResetBuffer(4096);
+ for (int i = 0; i < 3; i++) {
+ ASSERT_EQ(512u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(512 - 16, 'a')
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(512u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
+ .AddPacket(512 - 16, 'b')
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(1024u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
+ .AddPacket(1024 - 16, 'c')
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(2048u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(3))
+ .AddPacket(2048 - 16, 'd')
+ .CopyIntoTraceBuffer());
+
+ // At this point the write pointer should have been reset at the beginning.
+ ASSERT_EQ(4096u, size_to_end());
+
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(512 - 16, 'a')));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(512 - 16, 'b')));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(1024 - 16, 'c')));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(2048 - 16, 'd')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+ }
+}
+
+// Similar to the above, but this time leaves some gap at the end and then
+// tries to add a chunk that doesn't fit to exercise the padding-at-end logic.
+// Initial condition:
+// [ c0: 128 ][ c1: 256 ][ c2: 512 ][ c3: 1024 ][ c4: 2048 ]{ 128 padding }
+// | ------------------------------- 4k buffer ------------------------------ |
+//
+// At this point we try to insert a 512 Bytes chunk (c5). The result should be:
+// [ c5: 512 ]{ padding }[c3: 1024 ][ c4: 2048 ]{ 128 padding }
+// | ------------------------------- 4k buffer ------------------------------ |
+TEST_F(TraceBufferTest, ReadWrite_Padding) {
+ ResetBuffer(4096);
+ ASSERT_EQ(128u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(128 - 16, 'a')
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(256u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
+ .AddPacket(256 - 16, 'b')
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(512u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
+ .AddPacket(512 - 16, 'c')
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(1024u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(3))
+ .AddPacket(1024 - 16, 'd')
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(2048u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(4))
+ .AddPacket(2048 - 16, 'e')
+ .CopyIntoTraceBuffer());
+
+ // Now write c5 that will cause wrapping + padding.
+ ASSERT_EQ(128u, size_to_end());
+ ASSERT_EQ(512u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(5))
+ .AddPacket(512 - 16, 'f')
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(4096u - 512, size_to_end());
+
+ // The expected read sequence now is: c3, c4, c5.
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(1024 - 16, 'd')));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(2048 - 16, 'e')));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(512 - 16, 'f')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+// Like ReadWrite_Padding, but this time the padding introduced is the minimum
+// allowed (16 bytes). This is to exercise edge cases in the padding logic.
+// [c0: 2048 ][c1: 1024 ][c2: 1008 ][c3: 16]
+// [c4: 2032 ][c5: 1040 ][c6 :16][c7: 1080 ]
+TEST_F(TraceBufferTest, ReadWrite_MinimalPadding) {
+ ResetBuffer(4096);
+
+ ASSERT_EQ(2048u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(2048 - 16, 'a')
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(1024u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
+ .AddPacket(1024 - 16, 'b')
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(1008u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
+ .AddPacket(1008 - 16, 'c')
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(16u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(3))
+ .CopyIntoTraceBuffer());
+
+ ASSERT_EQ(4096u, size_to_end());
+
+ ASSERT_EQ(2032u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(4))
+ .AddPacket(2032 - 16, 'd')
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(1040u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(5))
+ .AddPacket(1040 - 16, 'e')
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(16u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(6))
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(1008u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(7))
+ .AddPacket(1008 - 16, 'f')
+ .CopyIntoTraceBuffer());
+
+ ASSERT_EQ(4096u, size_to_end());
+
+ // The expected read sequence now is: c3, c4, c5.
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(2032 - 16, 'd')));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(1040 - 16, 'e')));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(1008 - 16, 'f')));
+ for (int i = 0; i < 3; i++)
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+TEST_F(TraceBufferTest, ReadWrite_RandomChunksNoWrapping) {
+ for (int seed = 1; seed <= 32; seed++) {
+ std::minstd_rand0 rnd_engine(seed);
+ ResetBuffer(4096 * (1 + rnd_engine() % 32));
+ std::uniform_int_distribution<size_t> size_dist(18, 4096);
+ std::uniform_int_distribution<ProducerID> prod_dist(1, kMaxProducerID);
+ std::uniform_int_distribution<WriterID> wri_dist(1, kMaxWriterID);
+ ChunkID chunk_id = 0;
+ std::map<std::tuple<ProducerID, WriterID, ChunkID>, size_t> expected_chunks;
+ for (;;) {
+ const size_t chunk_size = size_dist(rnd_engine);
+ if (base::AlignUp<16>(chunk_size) >= size_to_end())
+ break;
+ ProducerID p = prod_dist(rnd_engine);
+ WriterID w = wri_dist(rnd_engine);
+ ChunkID c = chunk_id++;
+ expected_chunks.emplace(std::make_tuple(p, w, c), chunk_size);
+ ASSERT_EQ(chunk_size,
+ CreateChunk(p, w, c)
+ .AddPacket(chunk_size - 16, static_cast<char>(chunk_size))
+ .CopyIntoTraceBuffer());
+ } // for(;;)
+ trace_buffer()->BeginRead();
+ for (const auto& it : expected_chunks) {
+ const size_t chunk_size = it.second;
+ ASSERT_THAT(ReadPacket(),
+ ElementsAre(FakePacketFragment(
+ chunk_size - 16, static_cast<char>(chunk_size))));
+ }
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+ }
+}
+
+// Tests the case of writing a chunk that leaves just sizeof(ChunkRecord) at
+// the end of the buffer.
+TEST_F(TraceBufferTest, ReadWrite_WrappingCases) {
+ ResetBuffer(4096);
+ ASSERT_EQ(4080u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(4080 - 16, 'a')
+ .CopyIntoTraceBuffer());
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(4080 - 16, 'a')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+
+ ASSERT_EQ(16u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(2048u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
+ .AddPacket(2048 - 16, 'b')
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(2048u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(3))
+ .AddPacket(2048 - 16, 'c')
+ .CopyIntoTraceBuffer());
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(2048 - 16, 'b')));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(2048 - 16, 'c')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+// Tests that when records are removed when adding padding at the end because
+// there is no space left. The scenario is the following:
+// Initial condition: [ c0: 2048 ][ c1: 2048 ]
+// 2nd iteration: [ c2: 2048] <-- write pointer is here
+// At this point we try to add a 3072 bytes chunk. It won't fit because the
+// space left till the end is just 2048 bytes. At this point we expect that a
+// padding record is added in place of c1, and c1 is removed from the index.
+// Final situation: [ c3: 3072 ][ PAD ]
+TEST_F(TraceBufferTest, ReadWrite_PaddingAtEndUpdatesIndex) {
+ ResetBuffer(4096);
+ // Setup initial condition: [ c0: 2048 ][ c1: 2048 ]
+ ASSERT_EQ(2048u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(2048 - 16, 'a')
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(2048u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
+ .AddPacket(2048 - 16, 'b')
+ .CopyIntoTraceBuffer());
+ ASSERT_THAT(GetIndex(),
+ ElementsAre(ChunkMetaKey(1, 1, 0), ChunkMetaKey(1, 1, 1)));
+
+ // Wrap and get to this: [ c2: 2048] <-- write pointer is here
+ ASSERT_EQ(2048u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
+ .AddPacket(2048 - 16, 'c')
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(2048u, size_to_end());
+ ASSERT_THAT(GetIndex(),
+ ElementsAre(ChunkMetaKey(1, 1, 1), ChunkMetaKey(1, 1, 2)));
+
+ // Force wrap because of lack of space and get: [ c3: 3072 ][ PAD ].
+ ASSERT_EQ(3072u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(3))
+ .AddPacket(3072 - 16, 'd')
+ .CopyIntoTraceBuffer());
+ ASSERT_THAT(GetIndex(), ElementsAre(ChunkMetaKey(1, 1, 3)));
+
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(3072 - 16, 'd')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+// Similar to ReadWrite_PaddingAtEndUpdatesIndex but makes it so that the
+// various chunks don't perfectly align when wrapping.
+TEST_F(TraceBufferTest, ReadWrite_PaddingAtEndUpdatesIndexMisaligned) {
+ ResetBuffer(4096);
+
+ // [c0: 512][c1: 512][c2: 512][c3: 512][c4: 512][c5: 512][c6: 512][c7: 512]
+ for (uint8_t i = 0; i < 8; i++) {
+ ASSERT_EQ(512u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(i))
+ .AddPacket(512 - 16, 'a' + i)
+ .CopyIntoTraceBuffer());
+ }
+ ASSERT_EQ(8u, GetIndex().size());
+
+ // [c8: 2080..........................][PAD][c5: 512][c6: 512][c7: 512]
+ // ^ write pointer is here.
+ ASSERT_EQ(2080u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(8))
+ .AddPacket(2080 - 16, 'i')
+ .CopyIntoTraceBuffer());
+ ASSERT_EQ(2016u, size_to_end());
+ ASSERT_THAT(GetIndex(),
+ ElementsAre(ChunkMetaKey(1, 1, 5), ChunkMetaKey(1, 1, 6),
+ ChunkMetaKey(1, 1, 7), ChunkMetaKey(1, 1, 8)));
+
+ // [ c9: 3104....................................][ PAD...............].
+ ASSERT_EQ(3104u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(9))
+ .AddPacket(3104 - 16, 'j')
+ .CopyIntoTraceBuffer());
+ ASSERT_THAT(GetIndex(), ElementsAre(ChunkMetaKey(1, 1, 9)));
+
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(3104u - 16, 'j')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+// --------------------------------------
+// Fragments stitching and skipping logic
+// --------------------------------------
+
+TEST_F(TraceBufferTest, Fragments_Simple) {
+ ResetBuffer(4096);
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(10, 'a', kContFromPrevChunk)
+ .AddPacket(20, 'b')
+ .AddPacket(30, 'c')
+ .AddPacket(10, 'd', kContOnNextChunk)
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
+ .AddPacket(20, 'e', kContFromPrevChunk)
+ .AddPacket(30, 'f')
+ .CopyIntoTraceBuffer();
+
+ trace_buffer()->BeginRead();
+ // The (10, 'a') entry should be skipped because we don't have provided the
+ // previous chunk, hence should be treated as a data loss.
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(20, 'b')));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(30, 'c')));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'd'),
+ FakePacketFragment(20, 'e')));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(30, 'f')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+TEST_F(TraceBufferTest, Fragments_EdgeCases) {
+ ResetBuffer(4096);
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(2, 'a', kContFromPrevChunk)
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
+ .AddPacket(2, 'b', kContOnNextChunk)
+ .CopyIntoTraceBuffer();
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+
+ // Now add the missing fragment.
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
+ .AddPacket(2, 'c', kContFromPrevChunk)
+ .CopyIntoTraceBuffer();
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(2, 'b'),
+ FakePacketFragment(2, 'c')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+// Receive packet fragments for the sequence {1,1} in the chunk order {0,2,1}
+// and verify that they still get realigned properly, without breaking other
+// sequences.
+TEST_F(TraceBufferTest, Fragments_OutOfOrder) {
+ ResetBuffer(4096);
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(10, 'a', kContOnNextChunk)
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
+ .AddPacket(30, 'c', kContFromPrevChunk)
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(1), WriterID(2), ChunkID(0))
+ .AddPacket(10, 'd')
+ .CopyIntoTraceBuffer();
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'd')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
+ .AddPacket(20, 'b', kContFromPrevChunk | kContOnNextChunk)
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(3))
+ .AddPacket(40, 'd')
+ .CopyIntoTraceBuffer();
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'a'),
+ FakePacketFragment(20, 'b'),
+ FakePacketFragment(30, 'c')));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(40, 'd')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+TEST_F(TraceBufferTest, Fragments_EmptyChunkBefore) {
+ ResetBuffer(4096);
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(0)).CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
+ .AddPacket(10, 'a')
+ .AddPacket(20, 'b', kContOnNextChunk)
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
+ .AddPacket(30, 'c', kContFromPrevChunk)
+ .AddPacket(40, 'd', kContOnNextChunk)
+ .CopyIntoTraceBuffer();
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'a')));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(20, 'b'),
+ FakePacketFragment(30, 'c')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+TEST_F(TraceBufferTest, Fragments_EmptyChunkAfter) {
+ ResetBuffer(4096);
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(10, 'a')
+ .AddPacket(10, 'b', kContOnNextChunk)
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(1)).CopyIntoTraceBuffer();
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'a')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+// Set up a fragmented packet that happens to also have an empty chunk in the
+// middle of the sequence. Test that it just gets skipped.
+TEST_F(TraceBufferTest, Fragments_EmptyChunkInTheMiddle) {
+ ResetBuffer(4096);
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(10, 'a', kContOnNextChunk)
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(1)).CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
+ .AddPacket(10, 'b', kContFromPrevChunk)
+ .AddPacket(20, 'c')
+ .CopyIntoTraceBuffer();
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'a'),
+ FakePacketFragment(10, 'b')));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(20, 'c')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+// Generates sequences of fragmented packets of increasing length (|seq_len|),
+// from [P0, P1a][P1y] to [P0, P1a][P1b][P1c]...[P1y]. Test that they are always
+// read as one packet.
+TEST_F(TraceBufferTest, Fragments_LongPackets) {
+ for (unsigned seq_len = 1; seq_len <= 10; seq_len++) {
+ ResetBuffer(4096);
+ std::vector<FakePacketFragment> expected_fragments;
+ expected_fragments.emplace_back(20, 'b');
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(10, 'a')
+ .AddPacket(20, 'b', kContOnNextChunk)
+ .CopyIntoTraceBuffer();
+ for (unsigned i = 1; i <= seq_len; i++) {
+ char prefix = 'b' + static_cast<char>(i);
+ expected_fragments.emplace_back(20 + i, prefix);
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(i))
+ .AddPacket(20 + i, prefix, kContFromPrevChunk | kContOnNextChunk)
+ .CopyIntoTraceBuffer();
+ }
+ expected_fragments.emplace_back(30, 'y');
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(seq_len + 1))
+ .AddPacket(30, 'y', kContFromPrevChunk)
+ .AddPacket(50, 'z')
+ .CopyIntoTraceBuffer();
+
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'a')));
+ ASSERT_THAT(ReadPacket(), ContainerEq(expected_fragments));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(50, 'z')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+ }
+}
+
+// Similar to Fragments_LongPacket, but covers also the case of ChunkID wrapping
+// over its max value.
+TEST_F(TraceBufferTest, Fragments_LongPacketWithWrappingID) {
+ ResetBuffer(4096);
+ std::vector<FakePacketFragment> expected_fragments;
+
+ for (ChunkID chunk_id = -2; chunk_id <= 2; chunk_id++) {
+ char prefix = static_cast<char>('c' + chunk_id);
+ expected_fragments.emplace_back(10 + chunk_id, prefix);
+ CreateChunk(ProducerID(1), WriterID(1), chunk_id)
+ .AddPacket(10 + chunk_id, prefix, kContOnNextChunk)
+ .CopyIntoTraceBuffer();
+ }
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ContainerEq(expected_fragments));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+// --------------------------
+// Out of band patching tests
+// --------------------------
+
+TEST_F(TraceBufferTest, Patching_Simple) {
+ ResetBuffer(4096);
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(100, 'a')
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(2), WriterID(1), ChunkID(0))
+ .AddPacket(9, 'b')
+ .ClearBytes(5, 4) // 5 := 4th payload byte. Byte 0 is the varint header.
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(3), WriterID(1), ChunkID(0))
+ .AddPacket(100, 'c')
+ .CopyIntoTraceBuffer();
+ ASSERT_TRUE(TryPatchChunkContents(ProducerID(2), WriterID(1), ChunkID(0), 5,
+ {{'Y', 'M', 'C', 'A'}}));
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(100, 'a')));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment("b00-YMCA", 8)));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(100, 'c')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+TEST_F(TraceBufferTest, Patching_SkipIfChunkDoesntExist) {
+ ResetBuffer(4096);
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(100, 'a')
+ .CopyIntoTraceBuffer();
+ ASSERT_FALSE(TryPatchChunkContents(ProducerID(1), WriterID(2), ChunkID(0), 0,
+ {{'X', 'X', 'X', 'X'}}));
+ ASSERT_FALSE(TryPatchChunkContents(ProducerID(1), WriterID(1), ChunkID(1), 0,
+ {{'X', 'X', 'X', 'X'}}));
+ ASSERT_FALSE(TryPatchChunkContents(ProducerID(1), WriterID(1), ChunkID(-1), 0,
+ {{'X', 'X', 'X', 'X'}}));
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(100, 'a')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+TEST_F(TraceBufferTest, Patching_AtBoundariesOfChunk) {
+ ResetBuffer(4096);
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(100, 'a', kContOnNextChunk)
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
+ .AddPacket(16, 'b', kContFromPrevChunk | kContOnNextChunk)
+ .ClearBytes(1, 4)
+ .ClearBytes(16 - 4, 4)
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
+ .AddPacket(100, 'c', kContFromPrevChunk)
+ .CopyIntoTraceBuffer();
+ ASSERT_TRUE(TryPatchChunkContents(ProducerID(1), WriterID(1), ChunkID(1), 1,
+ {{'P', 'E', 'R', 'F'}}));
+ ASSERT_TRUE(TryPatchChunkContents(ProducerID(1), WriterID(1), ChunkID(1),
+ 16 - 4, {{'E', 'T', 'T', 'O'}}));
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(),
+ ElementsAre(FakePacketFragment(100, 'a'),
+ FakePacketFragment("PERFb01-b02ETTO", 15),
+ FakePacketFragment(100, 'c')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+// ---------------------
+// Malicious input tests
+// ---------------------
+
+TEST_F(TraceBufferTest, Malicious_ZeroSizedChunk) {
+ ResetBuffer(4096);
+ SuppressSanityDchecksForTesting();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(32, 'a')
+ .CopyIntoTraceBuffer();
+
+ uint8_t valid_ptr = 0;
+ trace_buffer()->CopyChunkUntrusted(ProducerID(1), WriterID(1), ChunkID(1),
+ 1 /* num packets */, 0 /* flags*/,
+ &valid_ptr, sizeof(valid_ptr));
+
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
+ .AddPacket(32, 'b')
+ .CopyIntoTraceBuffer();
+
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(32, 'a')));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(32, 'b')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+// Attempting to write a chunk bigger than ChunkRecord::kMaxSize should end up
+// in a no-op.
+TEST_F(TraceBufferTest, Malicious_ChunkTooBig) {
+ ResetBuffer(4096);
+ SuppressSanityDchecksForTesting();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(4096, 'a')
+ .AddPacket(2048, 'b')
+ .CopyIntoTraceBuffer();
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+TEST_F(TraceBufferTest, Malicious_RepeatedChunkID) {
+ ResetBuffer(4096);
+ SuppressSanityDchecksForTesting();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(2048, 'a')
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(1024, 'b')
+ .CopyIntoTraceBuffer();
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(1024, 'b')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+TEST_F(TraceBufferTest, Malicious_ZeroVarintHeader) {
+ ResetBuffer(4096);
+ SuppressSanityDchecksForTesting();
+ // Create a standalone chunk where the varint header is == 0.
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(4, 'a')
+ .ClearBytes(0, 1)
+ .AddPacket(4, 'b')
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(2), WriterID(1), ChunkID(0))
+ .AddPacket(4, 'c')
+ .CopyIntoTraceBuffer();
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(4, 'c')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+TEST_F(TraceBufferTest, Malicious_VarintHeaderTooBig) {
+ ResetBuffer(4096);
+ SuppressSanityDchecksForTesting();
+
+ // Add a valid chunk.
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(32, 'a')
+ .CopyIntoTraceBuffer();
+
+ // Forge a packet which has a varint header that is just off by one.
+ CreateChunk(ProducerID(2), WriterID(1), ChunkID(0))
+ .AddPacket({0x16, '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b',
+ 'c', 'd', 'e', 'f'})
+ .CopyIntoTraceBuffer();
+
+ // Forge a packet which has a varint header that tries to hit an overflow.
+ CreateChunk(ProducerID(3), WriterID(1), ChunkID(0))
+ .AddPacket({0xff, 0xff, 0xff, 0x7f})
+ .CopyIntoTraceBuffer();
+
+ // Forge a packet which has a jumbo varint header: 0xff, 0xff .. 0x7f.
+ std::vector<uint8_t> chunk;
+ chunk.insert(chunk.end(), 128 - sizeof(ChunkRecord), 0xff);
+ chunk.back() = 0x7f;
+ trace_buffer()->CopyChunkUntrusted(ProducerID(4), WriterID(1), ChunkID(1),
+ 1 /* num packets */, 0 /* flags*/,
+ chunk.data(), chunk.size());
+
+ // Add a valid chunk.
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
+ .AddPacket(32, 'b')
+ .CopyIntoTraceBuffer();
+
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(32, 'a')));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(32, 'b')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+// Similar to Malicious_VarintHeaderTooBig, but this time the full chunk
+// contains an enormous varint number that tries to overflow.
+TEST_F(TraceBufferTest, Malicious_JumboVarint) {
+ ResetBuffer(64 * 1024);
+ SuppressSanityDchecksForTesting();
+
+ std::vector<uint8_t> chunk;
+ chunk.insert(chunk.end(), 64 * 1024 - sizeof(ChunkRecord) * 2, 0xff);
+ chunk.back() = 0x7f;
+ for (int i = 0; i < 3; i++) {
+ trace_buffer()->CopyChunkUntrusted(ProducerID(1), WriterID(1), ChunkID(1),
+ 1 /* num packets */, 0 /* flags*/,
+ chunk.data(), chunk.size());
+ }
+
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+// Like the Malicious_ZeroVarintHeader, but put the chunk in the middle of a
+// sequence that would be otherwise valid.
+TEST_F(TraceBufferTest, Malicious_ZeroVarintHeaderInSequence) {
+ ResetBuffer(4096);
+ SuppressSanityDchecksForTesting();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(4, 'a', kContOnNextChunk)
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
+ .AddPacket(4, 'b', kContFromPrevChunk | kContOnNextChunk)
+ .ClearBytes(0, 1)
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
+ .AddPacket(4, 'c', kContFromPrevChunk)
+ .AddPacket(4, 'd')
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(3))
+ .AddPacket(4, 'e')
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(2), WriterID(1), ChunkID(3))
+ .AddPacket(5, 'f')
+ .CopyIntoTraceBuffer();
+
+ trace_buffer()->BeginRead();
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(4, 'e')));
+ ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(5, 'f')));
+ ASSERT_THAT(ReadPacket(), IsEmpty());
+}
+
+TEST_F(TraceBufferTest, Malicious_PatchOutOfBounds) {
+ ResetBuffer(4096);
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
+ .AddPacket(2048, 'a')
+ .CopyIntoTraceBuffer();
+ CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
+ .AddPacket(16, 'b')
+ .CopyIntoTraceBuffer();
+ size_t offsets[] = {13, 16, size_t(-17), size_t(-32), size_t(-1024)};
+ for (size_t offset : offsets) {
+ ASSERT_FALSE(TryPatchChunkContents(ProducerID(1), WriterID(1), ChunkID(1),
+ offset, {{'0', 'd', 'a', 'y'}}));
+ }
+}
+
+// -------------------
+// SequenceIterator tests
+// -------------------
+TEST_F(TraceBufferTest, Iterator_OneStreamOrdered) {
+ ResetBuffer(64 * 1024);
+ AppendChunks({
+ {ProducerID(1), WriterID(1), ChunkID(0)},
+ {ProducerID(1), WriterID(1), ChunkID(1)},
+ {ProducerID(1), WriterID(1), ChunkID(2)},
+ {ProducerID(1), WriterID(1), ChunkID(5)},
+ {ProducerID(1), WriterID(1), ChunkID(6)},
+ {ProducerID(1), WriterID(1), ChunkID(7)},
+ });
+ ASSERT_TRUE(IteratorSeqEq(ProducerID(1), WriterID(2), {}));
+ ASSERT_TRUE(IteratorSeqEq(ProducerID(-1), WriterID(-1), {}));
+ ASSERT_TRUE(IteratorSeqEq(ProducerID(1), WriterID(1), {0, 1, 2, 5, 6, 7}));
+}
+
+TEST_F(TraceBufferTest, Iterator_OneStreamWrapping) {
+ ResetBuffer(64 * 1024);
+ AppendChunks({
+ {ProducerID(1), WriterID(1), ChunkID(5)},
+ {ProducerID(1), WriterID(1), ChunkID(6)},
+ {ProducerID(1), WriterID(1), ChunkID(7)},
+ {ProducerID(1), WriterID(1), ChunkID(0)},
+ {ProducerID(1), WriterID(1), ChunkID(1)},
+ {ProducerID(1), WriterID(1), ChunkID(2)},
+ });
+ ASSERT_TRUE(IteratorSeqEq(ProducerID(1), WriterID(2), {}));
+ ASSERT_TRUE(IteratorSeqEq(ProducerID(-1), WriterID(-1), {}));
+ ASSERT_TRUE(IteratorSeqEq(ProducerID(1), WriterID(1), {5, 6, 7, 0, 1, 2}));
+}
+
+TEST_F(TraceBufferTest, Iterator_ManyStreamsOrdered) {
+ ResetBuffer(64 * 1024);
+ AppendChunks({
+ {ProducerID(1), WriterID(1), ChunkID(0)},
+ {ProducerID(1), WriterID(1), ChunkID(1)},
+ {ProducerID(1), WriterID(2), ChunkID(0)},
+ {ProducerID(3), WriterID(1), ChunkID(0)},
+ {ProducerID(1), WriterID(2), ChunkID(3)},
+ {ProducerID(1), WriterID(2), ChunkID(5)},
+ {ProducerID(3), WriterID(1), ChunkID(7)},
+ {ProducerID(1), WriterID(1), ChunkID(6)},
+ {ProducerID(3), WriterID(1), ChunkID(8)},
+ });
+ ASSERT_TRUE(IteratorSeqEq(ProducerID(1), WriterID(1), {0, 1, 6}));
+ ASSERT_TRUE(IteratorSeqEq(ProducerID(1), WriterID(2), {0, 3, 5}));
+ ASSERT_TRUE(IteratorSeqEq(ProducerID(3), WriterID(1), {0, 7, 8}));
+}
+
+TEST_F(TraceBufferTest, Iterator_ManyStreamsWrapping) {
+ ResetBuffer(64 * 1024);
+ auto Neg = [](int x) { return kMaxChunkID + x; };
+ AppendChunks({
+ {ProducerID(1), WriterID(1), ChunkID(Neg(-4))},
+ {ProducerID(1), WriterID(1), ChunkID(Neg(-3))},
+ {ProducerID(1), WriterID(2), ChunkID(Neg(-2))},
+ {ProducerID(3), WriterID(1), ChunkID(Neg(-1))},
+ {ProducerID(1), WriterID(2), ChunkID(0)},
+ {ProducerID(1), WriterID(2), ChunkID(1)},
+ {ProducerID(3), WriterID(1), ChunkID(2)},
+ {ProducerID(1), WriterID(1), ChunkID(3)},
+ {ProducerID(3), WriterID(1), ChunkID(4)},
+ });
+ ASSERT_TRUE(IteratorSeqEq(ProducerID(1), WriterID(1), {Neg(-4), Neg(-3), 3}));
+ ASSERT_TRUE(IteratorSeqEq(ProducerID(1), WriterID(2), {Neg(-2), 0, 1}));
+ ASSERT_TRUE(IteratorSeqEq(ProducerID(3), WriterID(1), {Neg(-1), 2, 4}));
+}
+
+// TODO(primiano): test stats().
+// TODO(primiano): test multiple streams interleaved.
+// TODO(primiano): more testing on packet merging.
+
+} // namespace perfetto
diff --git a/src/tracing/core/trace_writer_impl.cc b/src/tracing/core/trace_writer_impl.cc
index 63b5799..3695cc5 100644
--- a/src/tracing/core/trace_writer_impl.cc
+++ b/src/tracing/core/trace_writer_impl.cc
@@ -132,6 +132,8 @@
PERFETTO_DCHECK(patch_it != patch_list_.end());
}
#endif
+ // TODO(primiano): this needs to be adjusted to be the offset within the
+ // payload, not from the start of the chunk header.
auto cur_hdr_offset = static_cast<uint16_t>(cur_hdr - cur_chunk_.begin());
patch_list_.emplace_front(cur_chunk_id_, cur_hdr_offset);
Patch& patch = patch_list_.front();
diff --git a/src/tracing/core/trace_writer_impl.h b/src/tracing/core/trace_writer_impl.h
index 249e106..e1ea143 100644
--- a/src/tracing/core/trace_writer_impl.h
+++ b/src/tracing/core/trace_writer_impl.h
@@ -34,7 +34,6 @@
public protozero::ScatteredStreamWriter::Delegate {
public:
// TracePacketHandle is defined in trace_writer.h
-
TraceWriterImpl(SharedMemoryArbiterImpl*, WriterID, BufferID);
~TraceWriterImpl() override;
diff --git a/src/tracing/test/fake_packet.cc b/src/tracing/test/fake_packet.cc
new file mode 100644
index 0000000..a79145d
--- /dev/null
+++ b/src/tracing/test/fake_packet.cc
@@ -0,0 +1,142 @@
+/*
+ * Copyright (C) 2018 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/tracing/test/fake_packet.h"
+
+#include <ostream>
+
+#include "perfetto/base/logging.h"
+#include "perfetto/protozero/proto_utils.h"
+#include "perfetto/tracing/core/shared_memory_abi.h"
+#include "src/tracing/core/trace_buffer.h"
+
+using protozero::proto_utils::ParseVarInt;
+using protozero::proto_utils::WriteVarInt;
+
+namespace perfetto {
+
+FakePacketFragment::FakePacketFragment(size_t size, char prefix) {
+ // |size| has to be at least == 2, because one byte will be taken just by the
+ // varint header.
+ PERFETTO_CHECK(size > 1);
+
+ // Finding the |payload_size| from |size| is quite tricky:
+ // A packet with 127 bytes of payload requires:
+ // 1B header (to represent the number 127 in varint) + 127 = 128 bytes.
+ // A packet with 128 bytes payload requires:
+ // 2B header (to represent the number 128 in varint) + 128 = 130 bytes.
+ // So the only way to generate a packet of 129 bytes in total we need to
+ // generate a redundant varint header of 2 bytes + 127 bytes of payload.
+ if (size <= 128) {
+ header_[0] = static_cast<uint8_t>(size - 1);
+ header_size_ = 1;
+ payload_.resize(size - 1);
+ } else if (size == 129) {
+ header_[0] = 0x80 | 127;
+ header_size_ = 2;
+ payload_.resize(127);
+ } else {
+ WriteVarInt(size - 2, &header_[0]);
+ header_size_ = 2;
+ payload_.resize(size - 2);
+ }
+ // Fills the payload as follow: X00-X01-X02 (where X == |prefix|);
+ for (size_t i = 0; i < payload_.size(); i++) {
+ switch (i % 4) {
+ case 0:
+ payload_[i] = prefix;
+ break;
+ case 1:
+ payload_[i] = '0' + ((i / 4 / 10) % 10);
+ break;
+ case 2:
+ payload_[i] = '0' + ((i / 4) % 10);
+ break;
+ case 3:
+ payload_[i] = '-';
+ break;
+ }
+ }
+}
+
+FakePacketFragment::FakePacketFragment(const void* payload,
+ size_t payload_size) {
+ PERFETTO_CHECK(payload_size <= 4096 - 2);
+ payload_.assign(reinterpret_cast<const char*>(payload), payload_size);
+ uint8_t* end = WriteVarInt(payload_.size(), &header_[0]);
+ header_size_ = end - &header_[0];
+}
+
+void FakePacketFragment::CopyInto(std::vector<uint8_t>* data) const {
+ data->insert(data->end(), &header_[0], &header_[0] + header_size_);
+ data->insert(data->end(), payload_.begin(), payload_.end());
+}
+
+size_t FakePacketFragment::GetSizeHeader() const {
+ uint64_t size = 0;
+ ParseVarInt(&header_[0], &header_[0] + header_size_, &size);
+ return static_cast<size_t>(size);
+}
+
+bool FakePacketFragment::operator==(const FakePacketFragment& o) const {
+ if (payload_ != o.payload_)
+ return false;
+ PERFETTO_CHECK(GetSizeHeader() == o.GetSizeHeader());
+ return true;
+}
+
+std::ostream& operator<<(std::ostream& os, const FakePacketFragment& packet) {
+ return os << "{len:" << packet.payload().size() << ", payload:\""
+ << packet.payload() << "\"}";
+}
+
+FakeChunk::FakeChunk(TraceBuffez* t, ProducerID p, WriterID w, ChunkID c)
+ : trace_buffer_{t}, producer_id{p}, writer_id{w}, chunk_id{c} {}
+
+FakeChunk& FakeChunk::AddPacket(size_t size, char seed, uint8_t packet_flag) {
+ PERFETTO_DCHECK(size <= 4096);
+ PERFETTO_CHECK(
+ !(packet_flag &
+ SharedMemoryABI::ChunkHeader::kFirstPacketContinuesFromPrevChunk) ||
+ num_packets == 0);
+ PERFETTO_CHECK(
+ !(flags & SharedMemoryABI::ChunkHeader::kLastPacketContinuesOnNextChunk));
+ flags |= packet_flag;
+ FakePacketFragment(size, seed).CopyInto(&data);
+ num_packets++;
+ return *this;
+}
+
+FakeChunk& FakeChunk::AddPacket(std::initializer_list<uint8_t> raw) {
+ data.insert(data.end(), raw.begin(), raw.end());
+ num_packets++;
+ return *this;
+}
+
+FakeChunk& FakeChunk::ClearBytes(size_t offset, size_t len) {
+ PERFETTO_DCHECK(offset + len <= data.size());
+ memset(data.data() + offset, 0, len);
+ return *this;
+}
+
+size_t FakeChunk::CopyIntoTraceBuffer() {
+ trace_buffer_->CopyChunkUntrusted(producer_id, writer_id, chunk_id,
+ num_packets, flags, data.data(),
+ data.size());
+ return data.size() + TraceBuffez::InlineChunkHeaderSize;
+}
+
+} // namespace perfetto
diff --git a/src/tracing/test/fake_packet.h b/src/tracing/test/fake_packet.h
new file mode 100644
index 0000000..d82bb48
--- /dev/null
+++ b/src/tracing/test/fake_packet.h
@@ -0,0 +1,82 @@
+/*
+ * Copyright (C) 2018 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_TRACING_TEST_FAKE_PACKET_H_
+#define SRC_TRACING_TEST_FAKE_PACKET_H_
+
+#include <stdint.h>
+
+#include <array>
+#include <initializer_list>
+#include <string>
+#include <vector>
+
+#include "perfetto/tracing/core/basic_types.h"
+
+namespace perfetto {
+
+class TraceBuffez;
+
+class FakePacketFragment {
+ public:
+ // Generates a packet of given |size| with pseudo random payload. The |size|
+ // argument includes the size of the varint header.
+ FakePacketFragment(size_t size, char prefix);
+ FakePacketFragment(const void* payload, size_t payload_size);
+ void CopyInto(std::vector<uint8_t>* data) const;
+ size_t GetSizeHeader() const;
+ bool operator==(const FakePacketFragment& other) const;
+ const std::string& payload() const { return payload_; }
+
+ private:
+ std::array<uint8_t, 2> header_{};
+ size_t header_size_ = 0;
+ std::string payload_;
+};
+
+std::ostream& operator<<(std::ostream&, const FakePacketFragment&);
+
+class FakeChunk {
+ public:
+ FakeChunk(TraceBuffez* t, ProducerID p, WriterID w, ChunkID c);
+
+ // Appends a packet of exactly |size| bytes (including the varint header
+ // that states the size of the packet itself. The payload of the packet is
+ // NOT a valid proto and is just filled with pseudo-random bytes generated
+ // from |seed|.
+ FakeChunk& AddPacket(size_t size, char seed, uint8_t packet_flag = 0);
+
+ // Appends a packet with the given raw content (including varint header).
+ FakeChunk& AddPacket(std::initializer_list<uint8_t>);
+
+ FakeChunk& ClearBytes(size_t offset, size_t len);
+
+ // Returns the full size of the chunk including the ChunkRecord header.
+ size_t CopyIntoTraceBuffer();
+
+ private:
+ TraceBuffez* trace_buffer_;
+ ProducerID producer_id;
+ WriterID writer_id;
+ ChunkID chunk_id;
+ uint8_t flags = 0;
+ uint16_t num_packets = 0;
+ std::vector<uint8_t> data;
+};
+
+} // namespace perfetto
+
+#endif // SRC_TRACING_TEST_FAKE_PACKET_H_