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_