1 /*
2  * Copyright (C) 2017 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include <string.h>
18 
19 #include <initializer_list>
20 #include <random>
21 #include <sstream>
22 #include <vector>
23 
24 #include "perfetto/protozero/proto_utils.h"
25 #include "perfetto/tracing/core/basic_types.h"
26 #include "perfetto/tracing/core/shared_memory_abi.h"
27 #include "perfetto/tracing/core/trace_packet.h"
28 #include "src/tracing/core/trace_buffer.h"
29 #include "src/tracing/test/fake_packet.h"
30 
31 #include "gmock/gmock.h"
32 #include "gtest/gtest.h"
33 
34 namespace perfetto {
35 
36 using ::testing::ContainerEq;
37 using ::testing::ElementsAre;
38 using ::testing::IsEmpty;
39 
40 class TraceBufferTest : public testing::Test {
41  public:
42   using SequenceIterator = TraceBuffer::SequenceIterator;
43   using ChunkMetaKey = TraceBuffer::ChunkMeta::Key;
44   using ChunkRecord = TraceBuffer::ChunkRecord;
45 
46   static constexpr uint8_t kContFromPrevChunk =
47       SharedMemoryABI::ChunkHeader::kFirstPacketContinuesFromPrevChunk;
48   static constexpr uint8_t kContOnNextChunk =
49       SharedMemoryABI::ChunkHeader::kLastPacketContinuesOnNextChunk;
50   static constexpr uint8_t kChunkNeedsPatching =
51       SharedMemoryABI::ChunkHeader::kChunkNeedsPatching;
52 
CreateChunk(ProducerID p,WriterID w,ChunkID c)53   FakeChunk CreateChunk(ProducerID p, WriterID w, ChunkID c) {
54     return FakeChunk(trace_buffer_.get(), p, w, c);
55   }
56 
ResetBuffer(size_t size_,TraceBuffer::OverwritePolicy policy=TraceBuffer::kOverwrite)57   void ResetBuffer(
58       size_t size_,
59       TraceBuffer::OverwritePolicy policy = TraceBuffer::kOverwrite) {
60     trace_buffer_ = TraceBuffer::Create(size_, policy);
61     ASSERT_TRUE(trace_buffer_);
62   }
63 
TryPatchChunkContents(ProducerID p,WriterID w,ChunkID c,std::vector<TraceBuffer::Patch> patches,bool other_patches_pending=false)64   bool TryPatchChunkContents(ProducerID p,
65                              WriterID w,
66                              ChunkID c,
67                              std::vector<TraceBuffer::Patch> patches,
68                              bool other_patches_pending = false) {
69     return trace_buffer_->TryPatchChunkContents(
70         p, w, c, patches.data(), patches.size(), other_patches_pending);
71   }
72 
ReadPacket(TraceBuffer::PacketSequenceProperties * sequence_properties=nullptr,bool * previous_packet_dropped=nullptr)73   std::vector<FakePacketFragment> ReadPacket(
74       TraceBuffer::PacketSequenceProperties* sequence_properties = nullptr,
75       bool* previous_packet_dropped = nullptr) {
76     std::vector<FakePacketFragment> fragments;
77     TracePacket packet;
78     TraceBuffer::PacketSequenceProperties ignored_sequence_properties{};
79     bool ignored_previous_packet_dropped;
80     if (!trace_buffer_->ReadNextTracePacket(
81             &packet,
82             sequence_properties ? sequence_properties
83                                 : &ignored_sequence_properties,
84             previous_packet_dropped ? previous_packet_dropped
85                                     : &ignored_previous_packet_dropped)) {
86       return fragments;
87     }
88     for (const Slice& slice : packet.slices())
89       fragments.emplace_back(slice.start, slice.size);
90     return fragments;
91   }
92 
AppendChunks(std::initializer_list<std::tuple<ProducerID,WriterID,ChunkID>> chunks)93   void AppendChunks(
94       std::initializer_list<std::tuple<ProducerID, WriterID, ChunkID>> chunks) {
95     for (const auto& c : chunks) {
96       char seed =
97           static_cast<char>(std::get<0>(c) + std::get<1>(c) + std::get<2>(c));
98       CreateChunk(std::get<0>(c), std::get<1>(c), std::get<2>(c))
99           .AddPacket(4, seed)
100           .CopyIntoTraceBuffer();
101     }
102   }
103 
IteratorSeqEq(ProducerID p,WriterID w,std::initializer_list<ChunkID> chunk_ids)104   bool IteratorSeqEq(ProducerID p,
105                      WriterID w,
106                      std::initializer_list<ChunkID> chunk_ids) {
107     std::stringstream expected_seq;
108     for (const auto& c : chunk_ids)
109       expected_seq << "{" << p << "," << w << "," << c << "},";
110 
111     std::stringstream actual_seq;
112     for (auto it = GetReadIterForSequence(p, w); it.is_valid(); it.MoveNext()) {
113       actual_seq << "{" << it.producer_id() << "," << it.writer_id() << ","
114                  << it.chunk_id() << "},";
115     }
116     std::string expected_seq_str = expected_seq.str();
117     std::string actual_seq_str = actual_seq.str();
118     EXPECT_EQ(expected_seq_str, actual_seq_str);
119     return expected_seq_str == actual_seq_str;
120   }
121 
GetReadIterForSequence(ProducerID p,WriterID w)122   SequenceIterator GetReadIterForSequence(ProducerID p, WriterID w) {
123     TraceBuffer::ChunkMeta::Key key(p, w, 0);
124     return trace_buffer_->GetReadIterForSequence(
125         trace_buffer_->index_.lower_bound(key));
126   }
127 
SuppressSanityDchecksForTesting()128   void SuppressSanityDchecksForTesting() {
129     trace_buffer_->suppress_sanity_dchecks_for_testing_ = true;
130   }
131 
GetIndex()132   std::vector<ChunkMetaKey> GetIndex() {
133     std::vector<ChunkMetaKey> keys;
134     keys.reserve(trace_buffer_->index_.size());
135     for (const auto& it : trace_buffer_->index_)
136       keys.push_back(it.first);
137     return keys;
138   }
139 
trace_buffer()140   TraceBuffer* trace_buffer() { return trace_buffer_.get(); }
size_to_end()141   size_t size_to_end() { return trace_buffer_->size_to_end(); }
142 
143  private:
144   std::unique_ptr<TraceBuffer> trace_buffer_;
145 };
146 
147 // ----------------------
148 // Main TraceBuffer tests
149 // ----------------------
150 
151 // Note for the test code: remember that the resulting size of a chunk is:
152 // SUM(packets) + 16 (that is sizeof(ChunkRecord)).
153 // Also remember that chunks are rounded up to 16. So, unless we are testing the
154 // rounding logic, might be a good idea to create chunks of that size.
155 
TEST_F(TraceBufferTest,ReadWrite_EmptyBuffer)156 TEST_F(TraceBufferTest, ReadWrite_EmptyBuffer) {
157   ResetBuffer(4096);
158   trace_buffer()->BeginRead();
159   ASSERT_THAT(ReadPacket(), IsEmpty());
160 }
161 
162 // On each iteration writes a fixed-size chunk and reads it back.
TEST_F(TraceBufferTest,ReadWrite_Simple)163 TEST_F(TraceBufferTest, ReadWrite_Simple) {
164   ResetBuffer(64 * 1024);
165   for (ChunkID chunk_id = 0; chunk_id < 1000; chunk_id++) {
166     char seed = static_cast<char>(chunk_id);
167     CreateChunk(ProducerID(1), WriterID(1), chunk_id)
168         .AddPacket(42, seed)
169         .CopyIntoTraceBuffer();
170     trace_buffer()->BeginRead();
171     ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(42, seed)));
172     ASSERT_THAT(ReadPacket(), IsEmpty());
173     EXPECT_EQ(chunk_id + 1u, trace_buffer()->stats().chunks_written());
174     EXPECT_EQ(trace_buffer()->stats().chunks_written(),
175               trace_buffer()->stats().chunks_read());
176     EXPECT_LT(0u, trace_buffer()->stats().bytes_written());
177     EXPECT_EQ(trace_buffer()->stats().bytes_written(),
178               trace_buffer()->stats().bytes_read());
179     EXPECT_EQ(0u, trace_buffer()->stats().padding_bytes_written());
180     EXPECT_EQ(0u, trace_buffer()->stats().padding_bytes_cleared());
181   }
182 }
183 
TEST_F(TraceBufferTest,ReadWrite_OneChunkPerWriter)184 TEST_F(TraceBufferTest, ReadWrite_OneChunkPerWriter) {
185   for (int8_t num_writers = 1; num_writers <= 10; num_writers++) {
186     ResetBuffer(4096);
187     for (char i = 1; i <= num_writers; i++) {
188       ASSERT_EQ(32u, CreateChunk(ProducerID(i), WriterID(i), ChunkID(i))
189                          .AddPacket(32 - 16, i)
190                          .CopyIntoTraceBuffer());
191     }
192 
193     // The expected read sequence now is: c3, c4, c5.
194     trace_buffer()->BeginRead();
195     for (char i = 1; i <= num_writers; i++)
196       ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(32 - 16, i)));
197     ASSERT_THAT(ReadPacket(), IsEmpty());
198   }  // for(num_writers)
199 }
200 
201 // Writes chunk that up filling the buffer precisely until the end, like this:
202 // [ c0: 512 ][ c1: 512 ][ c2: 1024 ][ c3: 2048 ]
203 // | ---------------- 4k buffer --------------- |
TEST_F(TraceBufferTest,ReadWrite_FillTillEnd)204 TEST_F(TraceBufferTest, ReadWrite_FillTillEnd) {
205   ResetBuffer(4096);
206   for (int i = 0; i < 3; i++) {
207     ASSERT_EQ(512u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(i * 4))
208                         .AddPacket(512 - 16, 'a')
209                         .CopyIntoTraceBuffer());
210     ASSERT_EQ(512u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(i * 4 + 1))
211                         .AddPacket(512 - 16, 'b')
212                         .CopyIntoTraceBuffer());
213     ASSERT_EQ(1024u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(i * 4 + 2))
214                          .AddPacket(1024 - 16, 'c')
215                          .CopyIntoTraceBuffer());
216     ASSERT_EQ(2048u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(i * 4 + 3))
217                          .AddPacket(2048 - 16, 'd')
218                          .CopyIntoTraceBuffer());
219 
220     // At this point the write pointer should have been reset at the beginning.
221     ASSERT_EQ(4096u, size_to_end());
222 
223     trace_buffer()->BeginRead();
224     ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(512 - 16, 'a')));
225     ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(512 - 16, 'b')));
226     ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(1024 - 16, 'c')));
227     ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(2048 - 16, 'd')));
228     ASSERT_THAT(ReadPacket(), IsEmpty());
229   }
230 }
231 
232 // Similar to the above, but this time leaves some gap at the end and then
233 // tries to add a chunk that doesn't fit to exercise the padding-at-end logic.
234 // Initial condition:
235 // [ c0: 128 ][ c1: 256 ][ c2: 512   ][ c3: 1024 ][ c4: 2048 ]{ 128 padding }
236 // | ------------------------------- 4k buffer ------------------------------ |
237 //
238 // At this point we try to insert a 512 Bytes chunk (c5). The result should be:
239 // [ c5: 512              ]{ padding }[c3: 1024 ][ c4: 2048 ]{ 128 padding }
240 // | ------------------------------- 4k buffer ------------------------------ |
TEST_F(TraceBufferTest,ReadWrite_Padding)241 TEST_F(TraceBufferTest, ReadWrite_Padding) {
242   ResetBuffer(4096);
243   ASSERT_EQ(128u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
244                       .AddPacket(128 - 16, 'a')
245                       .CopyIntoTraceBuffer());
246   ASSERT_EQ(256u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
247                       .AddPacket(256 - 16, 'b')
248                       .CopyIntoTraceBuffer());
249   ASSERT_EQ(512u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
250                       .AddPacket(512 - 16, 'c')
251                       .CopyIntoTraceBuffer());
252   ASSERT_EQ(1024u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(3))
253                        .AddPacket(1024 - 16, 'd')
254                        .CopyIntoTraceBuffer());
255   ASSERT_EQ(2048u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(4))
256                        .AddPacket(2048 - 16, 'e')
257                        .CopyIntoTraceBuffer());
258 
259   // Now write c5 that will cause wrapping + padding.
260   ASSERT_EQ(128u, size_to_end());
261   ASSERT_EQ(512u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(5))
262                       .AddPacket(512 - 16, 'f')
263                       .CopyIntoTraceBuffer());
264   ASSERT_EQ(4096u - 512, size_to_end());
265 
266   // The expected read sequence now is: c3, c4, c5.
267   trace_buffer()->BeginRead();
268   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(1024 - 16, 'd')));
269   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(2048 - 16, 'e')));
270   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(512 - 16, 'f')));
271   ASSERT_THAT(ReadPacket(), IsEmpty());
272 
273   EXPECT_EQ(6u, trace_buffer()->stats().chunks_written());
274   EXPECT_EQ(3u, trace_buffer()->stats().chunks_overwritten());
275   EXPECT_EQ(3u, trace_buffer()->stats().chunks_read());
276   EXPECT_EQ(4480u, trace_buffer()->stats().bytes_written());
277   EXPECT_EQ(896u, trace_buffer()->stats().bytes_overwritten());
278   EXPECT_EQ(3584u, trace_buffer()->stats().bytes_read());
279   EXPECT_EQ(512u, trace_buffer()->stats().padding_bytes_written());
280   EXPECT_EQ(0u, trace_buffer()->stats().padding_bytes_cleared());
281 
282   // Adding another chunk should clear some of the padding.
283   ASSERT_EQ(128u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(6))
284                       .AddPacket(128 - 16, 'g')
285                       .CopyIntoTraceBuffer());
286   EXPECT_EQ(384u, trace_buffer()->stats().padding_bytes_cleared());
287 }
288 
289 // Like ReadWrite_Padding, but this time the padding introduced is the minimum
290 // allowed (16 bytes). This is to exercise edge cases in the padding logic.
291 // [c0: 2048               ][c1: 1024         ][c2: 1008       ][c3: 16]
292 // [c4: 2032            ][c5: 1040                ][c6 :16][c7: 1080   ]
TEST_F(TraceBufferTest,ReadWrite_MinimalPadding)293 TEST_F(TraceBufferTest, ReadWrite_MinimalPadding) {
294   ResetBuffer(4096);
295 
296   ASSERT_EQ(2048u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
297                        .AddPacket(2048 - 16, 'a')
298                        .CopyIntoTraceBuffer());
299   ASSERT_EQ(1024u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
300                        .AddPacket(1024 - 16, 'b')
301                        .CopyIntoTraceBuffer());
302   ASSERT_EQ(1008u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
303                        .AddPacket(1008 - 16, 'c')
304                        .CopyIntoTraceBuffer());
305   ASSERT_EQ(16u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(3))
306                      .CopyIntoTraceBuffer());
307 
308   ASSERT_EQ(4096u, size_to_end());
309 
310   ASSERT_EQ(2032u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(4))
311                        .AddPacket(2032 - 16, 'd')
312                        .CopyIntoTraceBuffer());
313   ASSERT_EQ(1040u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(5))
314                        .AddPacket(1040 - 16, 'e')
315                        .CopyIntoTraceBuffer());
316   ASSERT_EQ(16u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(6))
317                      .CopyIntoTraceBuffer());
318   ASSERT_EQ(1008u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(7))
319                        .AddPacket(1008 - 16, 'f')
320                        .CopyIntoTraceBuffer());
321 
322   ASSERT_EQ(4096u, size_to_end());
323 
324   // The expected read sequence now is: c3, c4, c5.
325   trace_buffer()->BeginRead();
326   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(2032 - 16, 'd')));
327   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(1040 - 16, 'e')));
328   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(1008 - 16, 'f')));
329   for (int i = 0; i < 3; i++)
330     ASSERT_THAT(ReadPacket(), IsEmpty());
331 }
332 
TEST_F(TraceBufferTest,ReadWrite_RandomChunksNoWrapping)333 TEST_F(TraceBufferTest, ReadWrite_RandomChunksNoWrapping) {
334   for (unsigned int seed = 1; seed <= 32; seed++) {
335     std::minstd_rand0 rnd_engine(seed);
336     ResetBuffer(4096 * (1 + rnd_engine() % 32));
337     std::uniform_int_distribution<size_t> size_dist(18, 4096);
338     std::uniform_int_distribution<ProducerID> prod_dist(1, kMaxProducerID);
339     std::uniform_int_distribution<WriterID> wri_dist(1, kMaxWriterID);
340     ChunkID chunk_id = 0;
341     std::map<std::tuple<ProducerID, WriterID, ChunkID>, size_t> expected_chunks;
342     for (;;) {
343       const size_t chunk_size = size_dist(rnd_engine);
344       if (base::AlignUp<16>(chunk_size) >= size_to_end())
345         break;
346       ProducerID p = prod_dist(rnd_engine);
347       WriterID w = wri_dist(rnd_engine);
348       ChunkID c = chunk_id++;
349       expected_chunks.emplace(std::make_tuple(p, w, c), chunk_size);
350       ASSERT_EQ(chunk_size,
351                 CreateChunk(p, w, c)
352                     .AddPacket(chunk_size - 16, static_cast<char>(chunk_size))
353                     .CopyIntoTraceBuffer());
354     }  // for(;;)
355     trace_buffer()->BeginRead();
356     for (const auto& it : expected_chunks) {
357       const size_t chunk_size = it.second;
358       ASSERT_THAT(ReadPacket(),
359                   ElementsAre(FakePacketFragment(
360                       chunk_size - 16, static_cast<char>(chunk_size))));
361     }
362     ASSERT_THAT(ReadPacket(), IsEmpty());
363   }
364 }
365 
366 // Tests the case of writing a chunk that leaves just sizeof(ChunkRecord) at
367 // the end of the buffer.
TEST_F(TraceBufferTest,ReadWrite_WrappingCases)368 TEST_F(TraceBufferTest, ReadWrite_WrappingCases) {
369   ResetBuffer(4096);
370   ASSERT_EQ(4080u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
371                        .AddPacket(4080 - 16, 'a')
372                        .CopyIntoTraceBuffer());
373   trace_buffer()->BeginRead();
374   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(4080 - 16, 'a')));
375   ASSERT_THAT(ReadPacket(), IsEmpty());
376 
377   ASSERT_EQ(16u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
378                      .CopyIntoTraceBuffer());
379   ASSERT_EQ(2048u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
380                        .AddPacket(2048 - 16, 'b')
381                        .CopyIntoTraceBuffer());
382   ASSERT_EQ(2048u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(3))
383                        .AddPacket(2048 - 16, 'c')
384                        .CopyIntoTraceBuffer());
385   trace_buffer()->BeginRead();
386   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(2048 - 16, 'b')));
387   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(2048 - 16, 'c')));
388   ASSERT_THAT(ReadPacket(), IsEmpty());
389 }
390 
391 // Tests that when records are removed when adding padding at the end because
392 // there is no space left. The scenario is the following:
393 // Initial condition: [ c0: 2048 ][ c1: 2048 ]
394 // 2nd iteration:     [ c2: 2048] <-- write pointer is here
395 // At this point we try to add a 3072 bytes chunk. It won't fit because the
396 // space left till the end is just 2048 bytes. At this point we expect that a
397 // padding record is added in place of c1, and c1 is removed from the index.
398 // Final situation:   [ c3: 3072     ][ PAD ]
TEST_F(TraceBufferTest,ReadWrite_PaddingAtEndUpdatesIndex)399 TEST_F(TraceBufferTest, ReadWrite_PaddingAtEndUpdatesIndex) {
400   ResetBuffer(4096);
401   // Setup initial condition: [ c0: 2048 ][ c1: 2048 ]
402   ASSERT_EQ(2048u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
403                        .AddPacket(2048 - 16, 'a')
404                        .CopyIntoTraceBuffer());
405   ASSERT_EQ(2048u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
406                        .AddPacket(2048 - 16, 'b')
407                        .CopyIntoTraceBuffer());
408   ASSERT_THAT(GetIndex(),
409               ElementsAre(ChunkMetaKey(1, 1, 0), ChunkMetaKey(1, 1, 1)));
410 
411   // Wrap and get to this: [ c2: 2048] <-- write pointer is here
412   ASSERT_EQ(2048u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
413                        .AddPacket(2048 - 16, 'c')
414                        .CopyIntoTraceBuffer());
415   ASSERT_EQ(2048u, size_to_end());
416   ASSERT_THAT(GetIndex(),
417               ElementsAre(ChunkMetaKey(1, 1, 1), ChunkMetaKey(1, 1, 2)));
418 
419   // Force wrap because of lack of space and get: [ c3: 3072     ][ PAD ].
420   ASSERT_EQ(3072u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(3))
421                        .AddPacket(3072 - 16, 'd')
422                        .CopyIntoTraceBuffer());
423   ASSERT_THAT(GetIndex(), ElementsAre(ChunkMetaKey(1, 1, 3)));
424 
425   trace_buffer()->BeginRead();
426   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(3072 - 16, 'd')));
427   ASSERT_THAT(ReadPacket(), IsEmpty());
428 }
429 
430 // Similar to ReadWrite_PaddingAtEndUpdatesIndex but makes it so that the
431 // various chunks don't perfectly align when wrapping.
TEST_F(TraceBufferTest,ReadWrite_PaddingAtEndUpdatesIndexMisaligned)432 TEST_F(TraceBufferTest, ReadWrite_PaddingAtEndUpdatesIndexMisaligned) {
433   ResetBuffer(4096);
434 
435   // [c0: 512][c1: 512][c2: 512][c3: 512][c4: 512][c5: 512][c6: 512][c7: 512]
436   for (char i = 0; i < 8; i++) {
437     ASSERT_EQ(512u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(i))
438                         .AddPacket(512 - 16, 'a' + i)
439                         .CopyIntoTraceBuffer());
440   }
441   ASSERT_EQ(8u, GetIndex().size());
442 
443   // [c8: 2080..........................][PAD][c5: 512][c6: 512][c7: 512]
444   //                                     ^ write pointer is here.
445   ASSERT_EQ(2080u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(8))
446                        .AddPacket(2080 - 16, 'i')
447                        .CopyIntoTraceBuffer());
448   ASSERT_EQ(2016u, size_to_end());
449   ASSERT_THAT(GetIndex(),
450               ElementsAre(ChunkMetaKey(1, 1, 5), ChunkMetaKey(1, 1, 6),
451                           ChunkMetaKey(1, 1, 7), ChunkMetaKey(1, 1, 8)));
452 
453   // [ c9: 3104....................................][ PAD...............].
454   ASSERT_EQ(3104u, CreateChunk(ProducerID(1), WriterID(1), ChunkID(9))
455                        .AddPacket(3104 - 16, 'j')
456                        .CopyIntoTraceBuffer());
457   ASSERT_THAT(GetIndex(), ElementsAre(ChunkMetaKey(1, 1, 9)));
458 
459   trace_buffer()->BeginRead();
460   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(3104u - 16, 'j')));
461   ASSERT_THAT(ReadPacket(), IsEmpty());
462 }
463 
464 // Verify that empty packets are skipped.
TEST_F(TraceBufferTest,ReadWrite_EmptyPacket)465 TEST_F(TraceBufferTest, ReadWrite_EmptyPacket) {
466   ResetBuffer(4096);
467   CreateChunk(ProducerID(1), WriterID(1), 0)
468       .AddPacket(42, 1)
469       .AddPacket(1, 2)
470       .AddPacket(42, 3)
471       .CopyIntoTraceBuffer();
472 
473   trace_buffer()->BeginRead();
474   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(42, 1)));
475   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(42, 3)));
476   ASSERT_THAT(ReadPacket(), IsEmpty());
477 
478   EXPECT_EQ(0u, trace_buffer()->stats().abi_violations());
479 }
480 
481 // --------------------------------------
482 // Fragments stitching and skipping logic
483 // --------------------------------------
484 
TEST_F(TraceBufferTest,Fragments_Simple)485 TEST_F(TraceBufferTest, Fragments_Simple) {
486   ResetBuffer(4096);
487   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
488       .AddPacket(10, 'a', kContFromPrevChunk)
489       .AddPacket(20, 'b')
490       .AddPacket(30, 'c')
491       .AddPacket(10, 'd', kContOnNextChunk)
492       .CopyIntoTraceBuffer();
493   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
494       .AddPacket(20, 'e', kContFromPrevChunk)
495       .AddPacket(30, 'f')
496       .CopyIntoTraceBuffer();
497 
498   trace_buffer()->BeginRead();
499   // The (10, 'a') entry should be skipped because we don't have provided the
500   // previous chunk, hence should be treated as a data loss.
501   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(20, 'b')));
502   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(30, 'c')));
503   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'd'),
504                                         FakePacketFragment(20, 'e')));
505   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(30, 'f')));
506   ASSERT_THAT(ReadPacket(), IsEmpty());
507 }
508 
TEST_F(TraceBufferTest,Fragments_EdgeCases)509 TEST_F(TraceBufferTest, Fragments_EdgeCases) {
510   ResetBuffer(4096);
511   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
512       .AddPacket(2, 'a', kContFromPrevChunk)
513       .CopyIntoTraceBuffer();
514   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
515       .AddPacket(2, 'b', kContOnNextChunk)
516       .CopyIntoTraceBuffer();
517   trace_buffer()->BeginRead();
518   ASSERT_THAT(ReadPacket(), IsEmpty());
519 
520   // Now add the missing fragment.
521   CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
522       .AddPacket(2, 'c', kContFromPrevChunk)
523       .CopyIntoTraceBuffer();
524   trace_buffer()->BeginRead();
525   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(2, 'b'),
526                                         FakePacketFragment(2, 'c')));
527   ASSERT_THAT(ReadPacket(), IsEmpty());
528 }
529 
530 // The following tests verify that chunks received out-of-order are read in the
531 // correct order.
532 //
533 // Fragment order {0,2,1} for sequence {1,1}, without fragmenting packets.
TEST_F(TraceBufferTest,Fragments_OutOfOrderLastChunkIsMiddle)534 TEST_F(TraceBufferTest, Fragments_OutOfOrderLastChunkIsMiddle) {
535   ResetBuffer(4096);
536   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
537       .AddPacket(10, 'a')
538       .CopyIntoTraceBuffer();
539   CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
540       .AddPacket(30, 'c')
541       .CopyIntoTraceBuffer();
542   EXPECT_EQ(0u, trace_buffer()->stats().chunks_committed_out_of_order());
543   trace_buffer()->BeginRead();
544   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'a')));
545   ASSERT_THAT(ReadPacket(), IsEmpty());
546 
547   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
548       .AddPacket(20, 'b')
549       .CopyIntoTraceBuffer();
550   EXPECT_EQ(1u, trace_buffer()->stats().chunks_committed_out_of_order());
551   trace_buffer()->BeginRead();
552   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(20, 'b')));
553   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(30, 'c')));
554   ASSERT_THAT(ReadPacket(), IsEmpty());
555 }
556 
557 // Fragment order {0,2,1} for sequence {1,1}, with fragmenting packets.
TEST_F(TraceBufferTest,Fragments_OutOfOrderLastChunkIsMiddleFragmentation)558 TEST_F(TraceBufferTest, Fragments_OutOfOrderLastChunkIsMiddleFragmentation) {
559   ResetBuffer(4096);
560   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
561       .AddPacket(10, 'a', kContOnNextChunk)
562       .CopyIntoTraceBuffer();
563   CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
564       .AddPacket(30, 'c', kContFromPrevChunk)
565       .CopyIntoTraceBuffer();
566   trace_buffer()->BeginRead();
567   ASSERT_THAT(ReadPacket(), IsEmpty());
568 
569   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
570       .AddPacket(20, 'b', kContFromPrevChunk | kContOnNextChunk)
571       .CopyIntoTraceBuffer();
572   trace_buffer()->BeginRead();
573   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'a'),
574                                         FakePacketFragment(20, 'b'),
575                                         FakePacketFragment(30, 'c')));
576   ASSERT_THAT(ReadPacket(), IsEmpty());
577 }
578 
579 // Fragment order {0,2,1,3} for sequence {1,1}, with fragmenting packets. Also
580 // verifies that another sequence isn't broken.
TEST_F(TraceBufferTest,Fragments_OutOfOrderLastChunkIsMaxFragmentation)581 TEST_F(TraceBufferTest, Fragments_OutOfOrderLastChunkIsMaxFragmentation) {
582   ResetBuffer(4096);
583   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
584       .AddPacket(10, 'a', kContOnNextChunk)
585       .CopyIntoTraceBuffer();
586   CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
587       .AddPacket(30, 'c', kContFromPrevChunk)
588       .CopyIntoTraceBuffer();
589   CreateChunk(ProducerID(1), WriterID(2), ChunkID(0))
590       .AddPacket(10, 'd')
591       .CopyIntoTraceBuffer();
592   trace_buffer()->BeginRead();
593   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'd')));
594   ASSERT_THAT(ReadPacket(), IsEmpty());
595 
596   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
597       .AddPacket(20, 'b', kContFromPrevChunk | kContOnNextChunk)
598       .CopyIntoTraceBuffer();
599   CreateChunk(ProducerID(1), WriterID(1), ChunkID(3))
600       .AddPacket(40, 'd')
601       .CopyIntoTraceBuffer();
602   trace_buffer()->BeginRead();
603   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'a'),
604                                         FakePacketFragment(20, 'b'),
605                                         FakePacketFragment(30, 'c')));
606   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(40, 'd')));
607   ASSERT_THAT(ReadPacket(), IsEmpty());
608 }
609 
610 // Fragment order {-2,1,-1,0} for sequence {1,1}, without fragmenting packets.
TEST_F(TraceBufferTest,Fragments_OutOfOrderWithIdOverflowADCB)611 TEST_F(TraceBufferTest, Fragments_OutOfOrderWithIdOverflowADCB) {
612   ResetBuffer(4096);
613   CreateChunk(ProducerID(1), WriterID(1), ChunkID(kMaxChunkID - 1))
614       .AddPacket(10, 'a')
615       .CopyIntoTraceBuffer();
616   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
617       .AddPacket(40, 'd')
618       .CopyIntoTraceBuffer();
619   trace_buffer()->BeginRead();
620   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'a')));
621   ASSERT_THAT(ReadPacket(), IsEmpty());
622 
623   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
624       .AddPacket(30, 'c')
625       .CopyIntoTraceBuffer();
626   trace_buffer()->BeginRead();
627   ASSERT_THAT(ReadPacket(), IsEmpty());
628 
629   CreateChunk(ProducerID(1), WriterID(1), ChunkID(kMaxChunkID))
630       .AddPacket(20, 'b')
631       .CopyIntoTraceBuffer();
632   trace_buffer()->BeginRead();
633   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(20, 'b')));
634   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(30, 'c')));
635   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(40, 'd')));
636   ASSERT_THAT(ReadPacket(), IsEmpty());
637 }
638 
639 // Fragment order {-2,0,-1,1} for sequence {1,1}, without fragmenting packets.
TEST_F(TraceBufferTest,Fragments_OutOfOrderWithIdOverflowACBD)640 TEST_F(TraceBufferTest, Fragments_OutOfOrderWithIdOverflowACBD) {
641   ResetBuffer(4096);
642   CreateChunk(ProducerID(1), WriterID(1), ChunkID(kMaxChunkID - 1))
643       .AddPacket(10, 'a')
644       .CopyIntoTraceBuffer();
645   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
646       .AddPacket(30, 'c')
647       .CopyIntoTraceBuffer();
648   trace_buffer()->BeginRead();
649   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'a')));
650   ASSERT_THAT(ReadPacket(), IsEmpty());
651 
652   CreateChunk(ProducerID(1), WriterID(1), ChunkID(kMaxChunkID))
653       .AddPacket(20, 'b')
654       .CopyIntoTraceBuffer();
655   trace_buffer()->BeginRead();
656   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(20, 'b')));
657   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(30, 'c')));
658   ASSERT_THAT(ReadPacket(), IsEmpty());
659 
660   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
661       .AddPacket(40, 'd')
662       .CopyIntoTraceBuffer();
663   trace_buffer()->BeginRead();
664   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(40, 'd')));
665   ASSERT_THAT(ReadPacket(), IsEmpty());
666 }
667 
TEST_F(TraceBufferTest,Fragments_EmptyChunkBefore)668 TEST_F(TraceBufferTest, Fragments_EmptyChunkBefore) {
669   ResetBuffer(4096);
670   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0)).CopyIntoTraceBuffer();
671   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
672       .AddPacket(10, 'a')
673       .AddPacket(20, 'b', kContOnNextChunk)
674       .CopyIntoTraceBuffer();
675   CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
676       .AddPacket(30, 'c', kContFromPrevChunk)
677       .AddPacket(40, 'd', kContOnNextChunk)
678       .CopyIntoTraceBuffer();
679   trace_buffer()->BeginRead();
680   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'a')));
681   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(20, 'b'),
682                                         FakePacketFragment(30, 'c')));
683   ASSERT_THAT(ReadPacket(), IsEmpty());
684 }
685 
TEST_F(TraceBufferTest,Fragments_EmptyChunkAfter)686 TEST_F(TraceBufferTest, Fragments_EmptyChunkAfter) {
687   ResetBuffer(4096);
688   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
689       .AddPacket(10, 'a')
690       .AddPacket(10, 'b', kContOnNextChunk)
691       .CopyIntoTraceBuffer();
692   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1)).CopyIntoTraceBuffer();
693   trace_buffer()->BeginRead();
694   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'a')));
695   ASSERT_THAT(ReadPacket(), IsEmpty());
696 }
697 
698 // Set up a fragmented packet that happens to also have an empty chunk in the
699 // middle of the sequence. Test that it just gets skipped.
TEST_F(TraceBufferTest,Fragments_EmptyChunkInTheMiddle)700 TEST_F(TraceBufferTest, Fragments_EmptyChunkInTheMiddle) {
701   ResetBuffer(4096);
702   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
703       .AddPacket(10, 'a', kContOnNextChunk)
704       .CopyIntoTraceBuffer();
705   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1)).CopyIntoTraceBuffer();
706   CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
707       .AddPacket(10, 'b', kContFromPrevChunk)
708       .AddPacket(20, 'c')
709       .CopyIntoTraceBuffer();
710   trace_buffer()->BeginRead();
711   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'a'),
712                                         FakePacketFragment(10, 'b')));
713   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(20, 'c')));
714   ASSERT_THAT(ReadPacket(), IsEmpty());
715 }
716 
717 // Generates sequences of fragmented packets of increasing length (|seq_len|),
718 // from [P0, P1a][P1y] to [P0, P1a][P1b][P1c]...[P1y]. Test that they are always
719 // read as one packet.
TEST_F(TraceBufferTest,Fragments_LongPackets)720 TEST_F(TraceBufferTest, Fragments_LongPackets) {
721   for (unsigned seq_len = 1; seq_len <= 10; seq_len++) {
722     ResetBuffer(4096);
723     std::vector<FakePacketFragment> expected_fragments;
724     expected_fragments.emplace_back(20, 'b');
725     CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
726         .AddPacket(10, 'a')
727         .AddPacket(20, 'b', kContOnNextChunk)
728         .CopyIntoTraceBuffer();
729     for (unsigned i = 1; i <= seq_len; i++) {
730       char prefix = 'b' + static_cast<char>(i);
731       expected_fragments.emplace_back(20 + i, prefix);
732       CreateChunk(ProducerID(1), WriterID(1), ChunkID(i))
733           .AddPacket(20 + i, prefix, kContFromPrevChunk | kContOnNextChunk)
734           .CopyIntoTraceBuffer();
735     }
736     expected_fragments.emplace_back(30, 'y');
737     CreateChunk(ProducerID(1), WriterID(1), ChunkID(seq_len + 1))
738         .AddPacket(30, 'y', kContFromPrevChunk)
739         .AddPacket(50, 'z')
740         .CopyIntoTraceBuffer();
741 
742     trace_buffer()->BeginRead();
743     ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'a')));
744     ASSERT_THAT(ReadPacket(), ContainerEq(expected_fragments));
745     ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(50, 'z')));
746     ASSERT_THAT(ReadPacket(), IsEmpty());
747   }
748 }
749 
750 // Similar to Fragments_LongPacket, but covers also the case of ChunkID wrapping
751 // over its max value.
TEST_F(TraceBufferTest,Fragments_LongPacketWithWrappingID)752 TEST_F(TraceBufferTest, Fragments_LongPacketWithWrappingID) {
753   ResetBuffer(4096);
754   std::vector<FakePacketFragment> expected_fragments;
755 
756   for (ChunkID chunk_id = static_cast<ChunkID>(-2); chunk_id <= 2; chunk_id++) {
757     char prefix = static_cast<char>('c' + chunk_id);
758     expected_fragments.emplace_back(10 + chunk_id, prefix);
759     CreateChunk(ProducerID(1), WriterID(1), chunk_id)
760         .AddPacket(10 + chunk_id, prefix, kContOnNextChunk)
761         .CopyIntoTraceBuffer();
762   }
763   trace_buffer()->BeginRead();
764   ASSERT_THAT(ReadPacket(), ContainerEq(expected_fragments));
765   ASSERT_THAT(ReadPacket(), IsEmpty());
766 }
767 
TEST_F(TraceBufferTest,Fragments_PreserveUID)768 TEST_F(TraceBufferTest, Fragments_PreserveUID) {
769   ResetBuffer(4096);
770   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
771       .AddPacket(10, 'a')
772       .AddPacket(10, 'b', kContOnNextChunk)
773       .SetUID(11)
774       .CopyIntoTraceBuffer();
775   CreateChunk(ProducerID(2), WriterID(1), ChunkID(0))
776       .AddPacket(10, 'c')
777       .AddPacket(10, 'd')
778       .SetUID(22)
779       .CopyIntoTraceBuffer();
780   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
781       .AddPacket(10, 'e', kContFromPrevChunk)
782       .AddPacket(10, 'f')
783       .SetUID(11)
784       .CopyIntoTraceBuffer();
785   trace_buffer()->BeginRead();
786   TraceBuffer::PacketSequenceProperties sequence_properties;
787   ASSERT_THAT(ReadPacket(&sequence_properties),
788               ElementsAre(FakePacketFragment(10, 'a')));
789   ASSERT_EQ(11u, sequence_properties.producer_uid_trusted);
790 
791   ASSERT_THAT(
792       ReadPacket(&sequence_properties),
793       ElementsAre(FakePacketFragment(10, 'b'), FakePacketFragment(10, 'e')));
794   ASSERT_EQ(11u, sequence_properties.producer_uid_trusted);
795 
796   ASSERT_THAT(ReadPacket(&sequence_properties),
797               ElementsAre(FakePacketFragment(10, 'f')));
798   ASSERT_EQ(11u, sequence_properties.producer_uid_trusted);
799 
800   ASSERT_THAT(ReadPacket(&sequence_properties),
801               ElementsAre(FakePacketFragment(10, 'c')));
802   ASSERT_EQ(22u, sequence_properties.producer_uid_trusted);
803 
804   ASSERT_THAT(ReadPacket(&sequence_properties),
805               ElementsAre(FakePacketFragment(10, 'd')));
806   ASSERT_EQ(22u, sequence_properties.producer_uid_trusted);
807 
808   ASSERT_THAT(ReadPacket(), IsEmpty());
809 }
810 
811 // --------------------------
812 // Out of band patching tests
813 // --------------------------
814 
TEST_F(TraceBufferTest,Patching_Simple)815 TEST_F(TraceBufferTest, Patching_Simple) {
816   ResetBuffer(4096);
817   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
818       .AddPacket(100, 'a')
819       .CopyIntoTraceBuffer();
820   CreateChunk(ProducerID(2), WriterID(1), ChunkID(0))
821       .AddPacket(9, 'b')
822       .ClearBytes(5, 4)  // 5 := 4th payload byte. Byte 0 is the varint header.
823       .CopyIntoTraceBuffer();
824   CreateChunk(ProducerID(3), WriterID(1), ChunkID(0))
825       .AddPacket(100, 'c')
826       .CopyIntoTraceBuffer();
827   ASSERT_TRUE(TryPatchChunkContents(ProducerID(2), WriterID(1), ChunkID(0),
828                                     {{5, {{'Y', 'M', 'C', 'A'}}}}));
829   trace_buffer()->BeginRead();
830   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(100, 'a')));
831   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment("b00-YMCA", 8)));
832   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(100, 'c')));
833   ASSERT_THAT(ReadPacket(), IsEmpty());
834 }
835 
TEST_F(TraceBufferTest,Patching_SkipIfChunkDoesntExist)836 TEST_F(TraceBufferTest, Patching_SkipIfChunkDoesntExist) {
837   ResetBuffer(4096);
838   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
839       .AddPacket(100, 'a')
840       .CopyIntoTraceBuffer();
841   ASSERT_FALSE(TryPatchChunkContents(ProducerID(1), WriterID(2), ChunkID(0),
842                                      {{0, {{'X', 'X', 'X', 'X'}}}}));
843   ASSERT_FALSE(TryPatchChunkContents(ProducerID(1), WriterID(1), ChunkID(1),
844                                      {{0, {{'X', 'X', 'X', 'X'}}}}));
845   ASSERT_FALSE(TryPatchChunkContents(ProducerID(1), WriterID(1), ChunkID(-1),
846                                      {{0, {{'X', 'X', 'X', 'X'}}}}));
847   trace_buffer()->BeginRead();
848   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(100, 'a')));
849   ASSERT_THAT(ReadPacket(), IsEmpty());
850 }
851 
TEST_F(TraceBufferTest,Patching_AtBoundariesOfChunk)852 TEST_F(TraceBufferTest, Patching_AtBoundariesOfChunk) {
853   ResetBuffer(4096);
854   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
855       .AddPacket(100, 'a', kContOnNextChunk)
856       .CopyIntoTraceBuffer();
857   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
858       .AddPacket(16, 'b', kContFromPrevChunk | kContOnNextChunk)
859       .ClearBytes(1, 4)
860       .ClearBytes(16 - 4, 4)
861       .CopyIntoTraceBuffer();
862   CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
863       .AddPacket(100, 'c', kContFromPrevChunk)
864       .CopyIntoTraceBuffer();
865   ASSERT_TRUE(TryPatchChunkContents(
866       ProducerID(1), WriterID(1), ChunkID(1),
867       {{1, {{'P', 'E', 'R', 'F'}}}, {16 - 4, {{'E', 'T', 'T', 'O'}}}}));
868   trace_buffer()->BeginRead();
869   ASSERT_THAT(ReadPacket(),
870               ElementsAre(FakePacketFragment(100, 'a'),
871                           FakePacketFragment("PERFb01-b02ETTO", 15),
872                           FakePacketFragment(100, 'c')));
873   ASSERT_THAT(ReadPacket(), IsEmpty());
874 }
875 
876 // Tests kChunkNeedsPatching logic: chunks that are marked as "pending patch"
877 // should not be read until the patch has happened.
TEST_F(TraceBufferTest,Patching_ReadWaitsForPatchComplete)878 TEST_F(TraceBufferTest, Patching_ReadWaitsForPatchComplete) {
879   ResetBuffer(4096);
880 
881   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
882       .AddPacket(16, 'a', kChunkNeedsPatching)
883       .ClearBytes(1, 4)  // 1 := 0th payload byte. Byte 0 is the varint header.
884       .CopyIntoTraceBuffer();
885   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
886       .AddPacket(16, 'b')
887       .CopyIntoTraceBuffer();
888 
889   CreateChunk(ProducerID(2), WriterID(1), ChunkID(0))
890       .AddPacket(16, 'c')
891       .CopyIntoTraceBuffer();
892   CreateChunk(ProducerID(2), WriterID(1), ChunkID(1))
893       .AddPacket(16, 'd', kChunkNeedsPatching)
894       .ClearBytes(1, 4)  // 1 := 0th payload byte. Byte 0 is the varint header.
895       .CopyIntoTraceBuffer();
896   CreateChunk(ProducerID(2), WriterID(1), ChunkID(2))
897       .AddPacket(16, 'e')
898       .CopyIntoTraceBuffer();
899 
900   CreateChunk(ProducerID(3), WriterID(1), ChunkID(0))
901       .AddPacket(16, 'f', kChunkNeedsPatching)
902       .ClearBytes(1, 8)  // 1 := 0th payload byte. Byte 0 is the varint header.
903       .CopyIntoTraceBuffer();
904 
905   // The only thing that can be read right now is the 1st packet of the 2nd
906   // sequence. All the rest is blocked waiting for patching.
907   trace_buffer()->BeginRead();
908   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(16, 'c')));
909   ASSERT_THAT(ReadPacket(), IsEmpty());
910 
911   // Now patch the 2nd sequence and check that the sequence is unblocked.
912   ASSERT_TRUE(TryPatchChunkContents(ProducerID(2), WriterID(1), ChunkID(1),
913                                     {{1, {{'P', 'A', 'T', 'C'}}}}));
914   trace_buffer()->BeginRead();
915   ASSERT_THAT(ReadPacket(),
916               ElementsAre(FakePacketFragment("PATCd01-d02-d03", 15)));
917   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(16, 'e')));
918   ASSERT_THAT(ReadPacket(), IsEmpty());
919 
920   // Now patch the 3rd sequence, but in the first patch set
921   // |other_patches_pending| to true, so that the sequence is unblocked only
922   // after the 2nd patch.
923   ASSERT_TRUE(TryPatchChunkContents(ProducerID(3), WriterID(1), ChunkID(0),
924                                     {{1, {{'P', 'E', 'R', 'F'}}}},
925                                     /*other_patches_pending=*/true));
926   trace_buffer()->BeginRead();
927   ASSERT_THAT(ReadPacket(), IsEmpty());
928 
929   ASSERT_TRUE(TryPatchChunkContents(ProducerID(3), WriterID(1), ChunkID(0),
930                                     {{5, {{'E', 'T', 'T', 'O'}}}},
931                                     /*other_patches_pending=*/false));
932   trace_buffer()->BeginRead();
933   ASSERT_THAT(ReadPacket(),
934               ElementsAre(FakePacketFragment("PERFETTOf02-f03", 15)));
935   ASSERT_THAT(ReadPacket(), IsEmpty());
936 
937 }  // namespace perfetto
938 
939 // ---------------------
940 // Malicious input tests
941 // ---------------------
942 
TEST_F(TraceBufferTest,Malicious_ZeroSizedChunk)943 TEST_F(TraceBufferTest, Malicious_ZeroSizedChunk) {
944   ResetBuffer(4096);
945   SuppressSanityDchecksForTesting();
946   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
947       .AddPacket(32, 'a')
948       .CopyIntoTraceBuffer();
949 
950   uint8_t valid_ptr = 0;
951   trace_buffer()->CopyChunkUntrusted(
952       ProducerID(1), uid_t(0), WriterID(1), ChunkID(1), 1 /* num packets */,
953       0 /* flags */, true /* chunk_complete */, &valid_ptr, sizeof(valid_ptr));
954 
955   CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
956       .AddPacket(32, 'b')
957       .CopyIntoTraceBuffer();
958 
959   trace_buffer()->BeginRead();
960   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(32, 'a')));
961   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(32, 'b')));
962   ASSERT_THAT(ReadPacket(), IsEmpty());
963 }
964 
965 // Attempting to write a chunk bigger than ChunkRecord::kMaxSize should end up
966 // in a no-op.
TEST_F(TraceBufferTest,Malicious_ChunkTooBig)967 TEST_F(TraceBufferTest, Malicious_ChunkTooBig) {
968   ResetBuffer(4096);
969   SuppressSanityDchecksForTesting();
970   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
971       .AddPacket(4096, 'a')
972       .AddPacket(2048, 'b')
973       .CopyIntoTraceBuffer();
974   trace_buffer()->BeginRead();
975   ASSERT_THAT(ReadPacket(), IsEmpty());
976 }
977 
TEST_F(TraceBufferTest,Malicious_DeclareMorePacketsBeyondBoundaries)978 TEST_F(TraceBufferTest, Malicious_DeclareMorePacketsBeyondBoundaries) {
979   ResetBuffer(4096);
980   SuppressSanityDchecksForTesting();
981   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
982       .AddPacket(64, 'a')
983       .IncrementNumPackets()
984       .IncrementNumPackets()
985       .CopyIntoTraceBuffer();
986   CreateChunk(ProducerID(1), WriterID(2), ChunkID(0))
987       .IncrementNumPackets()
988       .CopyIntoTraceBuffer();
989   CreateChunk(ProducerID(1), WriterID(3), ChunkID(0))
990       .AddPacket(32, 'b')
991       .CopyIntoTraceBuffer();
992   trace_buffer()->BeginRead();
993   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(64, 'a')));
994   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(32, 'b')));
995   ASSERT_THAT(ReadPacket(), IsEmpty());
996   ASSERT_THAT(ReadPacket(), IsEmpty());
997 }
998 
TEST_F(TraceBufferTest,Malicious_ZeroVarintHeader)999 TEST_F(TraceBufferTest, Malicious_ZeroVarintHeader) {
1000   ResetBuffer(4096);
1001   SuppressSanityDchecksForTesting();
1002   // Create a standalone chunk where the varint header is == 0.
1003   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1004       .AddPacket(4, 'a')
1005       .ClearBytes(0, 1)
1006       .AddPacket(4, 'b')
1007       .CopyIntoTraceBuffer();
1008   CreateChunk(ProducerID(2), WriterID(1), ChunkID(0))
1009       .AddPacket(4, 'c')
1010       .CopyIntoTraceBuffer();
1011   trace_buffer()->BeginRead();
1012   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(4, 'c')));
1013   ASSERT_THAT(ReadPacket(), IsEmpty());
1014 }
1015 
1016 // Forge a chunk where the first packet is valid but the second packet has a
1017 // varint header that continues beyond the end of the chunk (and also beyond the
1018 // end of the buffer).
TEST_F(TraceBufferTest,Malicious_OverflowingVarintHeader)1019 TEST_F(TraceBufferTest, Malicious_OverflowingVarintHeader) {
1020   ResetBuffer(4096);
1021   SuppressSanityDchecksForTesting();
1022   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1023       .AddPacket(4079, 'a')  // 4079 := 4096 - sizeof(ChunkRecord) - 1
1024       .AddPacket({0x82})  // 0x8*: that the varint continues on the next byte.
1025       .CopyIntoTraceBuffer();
1026   trace_buffer()->BeginRead();
1027   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(4079, 'a')));
1028   ASSERT_THAT(ReadPacket(), IsEmpty());
1029   ASSERT_THAT(ReadPacket(), IsEmpty());
1030 }
1031 
TEST_F(TraceBufferTest,Malicious_VarintHeaderTooBig)1032 TEST_F(TraceBufferTest, Malicious_VarintHeaderTooBig) {
1033   ResetBuffer(4096);
1034   SuppressSanityDchecksForTesting();
1035 
1036   // Add a valid chunk.
1037   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1038       .AddPacket(32, 'a')
1039       .CopyIntoTraceBuffer();
1040 
1041   // Forge a packet which has a varint header that is just off by one.
1042   CreateChunk(ProducerID(2), WriterID(1), ChunkID(0))
1043       .AddPacket({0x16, '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b',
1044                   'c', 'd', 'e', 'f'})
1045       .CopyIntoTraceBuffer();
1046 
1047   // Forge a packet which has a varint header that tries to hit an overflow.
1048   CreateChunk(ProducerID(3), WriterID(1), ChunkID(0))
1049       .AddPacket({0xff, 0xff, 0xff, 0x7f})
1050       .CopyIntoTraceBuffer();
1051 
1052   // Forge a packet which has a jumbo varint header: 0xff, 0xff .. 0x7f.
1053   std::vector<uint8_t> chunk;
1054   chunk.insert(chunk.end(), 128 - sizeof(ChunkRecord), 0xff);
1055   chunk.back() = 0x7f;
1056   trace_buffer()->CopyChunkUntrusted(
1057       ProducerID(4), uid_t(0), WriterID(1), ChunkID(1), 1 /* num packets */,
1058       0 /* flags*/, true /* chunk_complete */, chunk.data(), chunk.size());
1059 
1060   // Add a valid chunk.
1061   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
1062       .AddPacket(32, 'b')
1063       .CopyIntoTraceBuffer();
1064 
1065   trace_buffer()->BeginRead();
1066   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(32, 'a')));
1067   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(32, 'b')));
1068   ASSERT_THAT(ReadPacket(), IsEmpty());
1069 }
1070 
1071 // Similar to Malicious_VarintHeaderTooBig, but this time the full chunk
1072 // contains an enormous varint number that tries to overflow.
TEST_F(TraceBufferTest,Malicious_JumboVarint)1073 TEST_F(TraceBufferTest, Malicious_JumboVarint) {
1074   ResetBuffer(64 * 1024);
1075   SuppressSanityDchecksForTesting();
1076 
1077   std::vector<uint8_t> chunk;
1078   chunk.insert(chunk.end(), 64 * 1024 - sizeof(ChunkRecord) * 2, 0xff);
1079   chunk.back() = 0x7f;
1080   for (int i = 0; i < 3; i++) {
1081     trace_buffer()->CopyChunkUntrusted(
1082         ProducerID(1), uid_t(0), WriterID(1), ChunkID(1), 1 /* num packets */,
1083         0 /* flags */, true /* chunk_complete */, chunk.data(), chunk.size());
1084   }
1085 
1086   trace_buffer()->BeginRead();
1087   ASSERT_THAT(ReadPacket(), IsEmpty());
1088 }
1089 
1090 // Like the Malicious_ZeroVarintHeader, but put the chunk in the middle of a
1091 // sequence that would be otherwise valid. The zero-sized fragment should be
1092 // skipped.
TEST_F(TraceBufferTest,Malicious_ZeroVarintHeaderInSequence)1093 TEST_F(TraceBufferTest, Malicious_ZeroVarintHeaderInSequence) {
1094   ResetBuffer(4096);
1095   SuppressSanityDchecksForTesting();
1096   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1097       .AddPacket(4, 'a', kContOnNextChunk)
1098       .CopyIntoTraceBuffer();
1099   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
1100       .AddPacket(4, 'b', kContFromPrevChunk | kContOnNextChunk)
1101       .ClearBytes(0, 1)
1102       .CopyIntoTraceBuffer();
1103   CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
1104       .AddPacket(4, 'c', kContFromPrevChunk)
1105       .AddPacket(4, 'd')
1106       .CopyIntoTraceBuffer();
1107   CreateChunk(ProducerID(1), WriterID(1), ChunkID(3))
1108       .AddPacket(4, 'e')
1109       .CopyIntoTraceBuffer();
1110   CreateChunk(ProducerID(2), WriterID(1), ChunkID(3))
1111       .AddPacket(5, 'f')
1112       .CopyIntoTraceBuffer();
1113 
1114   trace_buffer()->BeginRead();
1115   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(4, 'a'),
1116                                         FakePacketFragment(4, 'c')));
1117   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(4, 'd')));
1118   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(4, 'e')));
1119   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(5, 'f')));
1120   ASSERT_THAT(ReadPacket(), IsEmpty());
1121 }
1122 
1123 // Similar to Malicious_ZeroVarintHeaderInSequence, but this time the zero-sized
1124 // fragment is the last fragment for a chunk and is marked for continuation. The
1125 // zero-sized fragment should be skipped.
TEST_F(TraceBufferTest,Malicious_ZeroVarintHeaderAtEndOfChunk)1126 TEST_F(TraceBufferTest, Malicious_ZeroVarintHeaderAtEndOfChunk) {
1127   ResetBuffer(4096);
1128   SuppressSanityDchecksForTesting();
1129   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1130       .AddPacket(4, 'a')
1131       .AddPacket(4, 'b', kContOnNextChunk)
1132       .ClearBytes(4, 4)
1133       .CopyIntoTraceBuffer();
1134   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
1135       .AddPacket(4, 'c', kContFromPrevChunk)
1136       .AddPacket(4, 'd')
1137       .CopyIntoTraceBuffer();
1138   CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
1139       .AddPacket(4, 'e')
1140       .CopyIntoTraceBuffer();
1141   CreateChunk(ProducerID(2), WriterID(1), ChunkID(3))
1142       .AddPacket(4, 'f')
1143       .CopyIntoTraceBuffer();
1144 
1145   trace_buffer()->BeginRead();
1146   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(4, 'a')));
1147   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(4, 'c')));
1148   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(4, 'd')));
1149   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(4, 'e')));
1150   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(4, 'f')));
1151   ASSERT_THAT(ReadPacket(), IsEmpty());
1152 }
1153 
TEST_F(TraceBufferTest,Malicious_PatchOutOfBounds)1154 TEST_F(TraceBufferTest, Malicious_PatchOutOfBounds) {
1155   ResetBuffer(4096);
1156   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1157       .AddPacket(2048, 'a')
1158       .CopyIntoTraceBuffer();
1159   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
1160       .AddPacket(16, 'b')
1161       .CopyIntoTraceBuffer();
1162   size_t offsets[] = {13,          16,          size_t(-4),
1163                       size_t(-8),  size_t(-12), size_t(-16),
1164                       size_t(-20), size_t(-32), size_t(-1024)};
1165   for (size_t offset : offsets) {
1166     ASSERT_FALSE(TryPatchChunkContents(ProducerID(1), WriterID(1), ChunkID(1),
1167                                        {{offset, {{'0', 'd', 'a', 'y'}}}}));
1168   }
1169 }
1170 
TEST_F(TraceBufferTest,Malicious_OverrideWithShorterChunkSize)1171 TEST_F(TraceBufferTest, Malicious_OverrideWithShorterChunkSize) {
1172   ResetBuffer(4096);
1173   SuppressSanityDchecksForTesting();
1174   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1175       .AddPacket(2048, 'a')
1176       .CopyIntoTraceBuffer();
1177   // The service should ignore this override of the chunk since the chunk size
1178   // is different.
1179   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1180       .AddPacket(1024, 'b')
1181       .CopyIntoTraceBuffer();
1182   trace_buffer()->BeginRead();
1183   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(2048, 'a')));
1184   ASSERT_THAT(ReadPacket(), IsEmpty());
1185 }
1186 
TEST_F(TraceBufferTest,Malicious_OverrideWithShorterChunkSizeAfterRead)1187 TEST_F(TraceBufferTest, Malicious_OverrideWithShorterChunkSizeAfterRead) {
1188   ResetBuffer(4096);
1189   SuppressSanityDchecksForTesting();
1190 
1191   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1192       .AddPacket(30, 'a')
1193       .AddPacket(40, 'b')
1194       .CopyIntoTraceBuffer();
1195   trace_buffer()->BeginRead();
1196   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(30, 'a')));
1197   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(40, 'b')));
1198 
1199   // The service should ignore this override of the chunk since the chunk size
1200   // is different.
1201   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1202       .AddPacket(10, 'a')
1203       .AddPacket(10, 'b')
1204       .AddPacket(10, 'c')
1205       .CopyIntoTraceBuffer();
1206   trace_buffer()->BeginRead();
1207   ASSERT_THAT(ReadPacket(), IsEmpty());
1208 
1209   // Test that the service didn't get stuck in some indeterminate state.
1210   // Writing a valid chunk with a larger ID should make things work again.
1211   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
1212       .AddPacket(10, 'd')
1213       .AddPacket(10, 'e')
1214       .CopyIntoTraceBuffer();
1215   trace_buffer()->BeginRead();
1216   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'd')));
1217   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'e')));
1218   ASSERT_THAT(ReadPacket(), IsEmpty());
1219 }
1220 
TEST_F(TraceBufferTest,Malicious_OverrideWithDifferentOffsetAfterRead)1221 TEST_F(TraceBufferTest, Malicious_OverrideWithDifferentOffsetAfterRead) {
1222   ResetBuffer(4096);
1223   SuppressSanityDchecksForTesting();
1224 
1225   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1226       .AddPacket(30, 'a')
1227       .AddPacket(40, 'b')
1228       .PadTo(512)
1229       .CopyIntoTraceBuffer();
1230   trace_buffer()->BeginRead();
1231   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(30, 'a')));
1232   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(40, 'b')));
1233 
1234   // The attacker in this case speculates on the fact that the read pointer is
1235   // @ 70 which is >> the size of the new chunk we overwrite.
1236   // The service will not discard this override since the chunk size is correct.
1237   // However, it should detect that the packet headers at the current read
1238   // offset are invalid and skip the read of this chunk.
1239   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1240       .AddPacket(10, 'a')
1241       .AddPacket(10, 'b')
1242       .AddPacket(10, 'c')
1243       .PadTo(512)
1244       .CopyIntoTraceBuffer();
1245   trace_buffer()->BeginRead();
1246   ASSERT_THAT(ReadPacket(), IsEmpty());
1247 
1248   // Test that the service didn't get stuck in some indeterminate state.
1249   // Writing a valid chunk with a larger ID should make things work again.
1250   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
1251       .AddPacket(10, 'd')
1252       .AddPacket(10, 'e')
1253       .PadTo(512)
1254       .CopyIntoTraceBuffer();
1255   trace_buffer()->BeginRead();
1256   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'd')));
1257   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(10, 'e')));
1258   ASSERT_THAT(ReadPacket(), IsEmpty());
1259 }
1260 
1261 // -------------------
1262 // SequenceIterator tests
1263 // -------------------
TEST_F(TraceBufferTest,Iterator_OneStreamOrdered)1264 TEST_F(TraceBufferTest, Iterator_OneStreamOrdered) {
1265   ResetBuffer(64 * 1024);
1266   AppendChunks({
1267       {ProducerID(1), WriterID(1), ChunkID(0)},
1268       {ProducerID(1), WriterID(1), ChunkID(1)},
1269       {ProducerID(1), WriterID(1), ChunkID(2)},
1270       {ProducerID(1), WriterID(1), ChunkID(5)},
1271       {ProducerID(1), WriterID(1), ChunkID(6)},
1272       {ProducerID(1), WriterID(1), ChunkID(7)},
1273   });
1274   ASSERT_TRUE(IteratorSeqEq(ProducerID(1), WriterID(2), {}));
1275   ASSERT_TRUE(IteratorSeqEq(ProducerID(-1), WriterID(-1), {}));
1276   ASSERT_TRUE(IteratorSeqEq(ProducerID(1), WriterID(1), {0, 1, 2}));
1277 }
1278 
TEST_F(TraceBufferTest,Iterator_OneStreamWrapping)1279 TEST_F(TraceBufferTest, Iterator_OneStreamWrapping) {
1280   ResetBuffer(64 * 1024);
1281   AppendChunks({
1282       {ProducerID(1), WriterID(1), ChunkID(kMaxChunkID - 2)},
1283       {ProducerID(1), WriterID(1), ChunkID(kMaxChunkID - 1)},
1284       {ProducerID(1), WriterID(1), ChunkID(kMaxChunkID)},
1285       {ProducerID(1), WriterID(1), ChunkID(0)},
1286       {ProducerID(1), WriterID(1), ChunkID(1)},
1287       {ProducerID(1), WriterID(1), ChunkID(2)},
1288   });
1289   ASSERT_TRUE(IteratorSeqEq(ProducerID(1), WriterID(2), {}));
1290   ASSERT_TRUE(IteratorSeqEq(ProducerID(-1), WriterID(-1), {}));
1291   ASSERT_TRUE(
1292       IteratorSeqEq(ProducerID(1), WriterID(1),
1293                     {kMaxChunkID - 2, kMaxChunkID - 1, kMaxChunkID, 0, 1, 2}));
1294 }
1295 
TEST_F(TraceBufferTest,Iterator_ManyStreamsOrdered)1296 TEST_F(TraceBufferTest, Iterator_ManyStreamsOrdered) {
1297   ResetBuffer(64 * 1024);
1298   AppendChunks({
1299       {ProducerID(1), WriterID(1), ChunkID(0)},
1300       {ProducerID(1), WriterID(1), ChunkID(1)},
1301       {ProducerID(1), WriterID(2), ChunkID(0)},
1302       {ProducerID(3), WriterID(1), ChunkID(0)},
1303       {ProducerID(1), WriterID(2), ChunkID(1)},
1304       {ProducerID(1), WriterID(2), ChunkID(2)},
1305       {ProducerID(3), WriterID(1), ChunkID(1)},
1306       {ProducerID(1), WriterID(1), ChunkID(2)},
1307       {ProducerID(3), WriterID(1), ChunkID(2)},
1308   });
1309   ASSERT_TRUE(IteratorSeqEq(ProducerID(1), WriterID(1), {0, 1, 2}));
1310   ASSERT_TRUE(IteratorSeqEq(ProducerID(1), WriterID(2), {0, 1, 2}));
1311   ASSERT_TRUE(IteratorSeqEq(ProducerID(3), WriterID(1), {0, 1, 2}));
1312 }
1313 
TEST_F(TraceBufferTest,Iterator_ManyStreamsWrapping)1314 TEST_F(TraceBufferTest, Iterator_ManyStreamsWrapping) {
1315   ResetBuffer(64 * 1024);
1316   auto Neg = [](int x) -> ChunkID {
1317     return kMaxChunkID + static_cast<ChunkID>(x) + 1;
1318   };
1319   AppendChunks({
1320       {ProducerID(1), WriterID(1), ChunkID(Neg(-2))},
1321       {ProducerID(1), WriterID(1), ChunkID(Neg(-1))},
1322       {ProducerID(1), WriterID(2), ChunkID(Neg(-1))},
1323       {ProducerID(3), WriterID(1), ChunkID(Neg(-1))},
1324       {ProducerID(1), WriterID(2), ChunkID(0)},
1325       {ProducerID(1), WriterID(2), ChunkID(1)},
1326       {ProducerID(3), WriterID(1), ChunkID(0)},
1327       {ProducerID(1), WriterID(1), ChunkID(0)},
1328       {ProducerID(3), WriterID(1), ChunkID(1)},
1329   });
1330   ASSERT_TRUE(IteratorSeqEq(ProducerID(1), WriterID(1), {Neg(-2), Neg(-1), 0}));
1331   ASSERT_TRUE(IteratorSeqEq(ProducerID(1), WriterID(2), {Neg(-1), 0, 1}));
1332   ASSERT_TRUE(IteratorSeqEq(ProducerID(3), WriterID(1), {Neg(-1), 0, 1}));
1333 }
1334 
1335 // -------------------
1336 // Re-writing same chunk id
1337 // -------------------
1338 
TEST_F(TraceBufferTest,Override_ReCommitBeforeRead)1339 TEST_F(TraceBufferTest, Override_ReCommitBeforeRead) {
1340   ResetBuffer(4096);
1341   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1342       .AddPacket(100, 'a')
1343       .AddPacket(100, 'b')
1344       .PadTo(512)
1345       .CopyIntoTraceBuffer(/*chunk_complete=*/false);
1346   EXPECT_EQ(0u, trace_buffer()->stats().chunks_rewritten());
1347   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1348       .AddPacket(100, 'a')
1349       .AddPacket(100, 'b')
1350       .AddPacket(100, 'c')
1351       .AddPacket(100, 'd')
1352       .PadTo(512)
1353       .CopyIntoTraceBuffer();
1354   trace_buffer()->BeginRead();
1355   EXPECT_EQ(1u, trace_buffer()->stats().chunks_rewritten());
1356   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(100, 'a')));
1357   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(100, 'b')));
1358   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(100, 'c')));
1359   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(100, 'd')));
1360   ASSERT_THAT(ReadPacket(), IsEmpty());
1361 }
1362 
TEST_F(TraceBufferTest,Override_ReCommitAfterPartialRead)1363 TEST_F(TraceBufferTest, Override_ReCommitAfterPartialRead) {
1364   ResetBuffer(4096);
1365   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1366       .AddPacket(20, 'a')
1367       .AddPacket(30, 'b')
1368       .PadTo(512)
1369       .CopyIntoTraceBuffer(/*chunk_complete=*/false);
1370   trace_buffer()->BeginRead();
1371   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(20, 'a')));
1372 
1373   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1374       .AddPacket(20, 'a')
1375       .AddPacket(30, 'b')
1376       .AddPacket(40, 'c')
1377       .AddPacket(50, 'd')
1378       .PadTo(512)
1379       .CopyIntoTraceBuffer();
1380   trace_buffer()->BeginRead();
1381   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(30, 'b')));
1382   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(40, 'c')));
1383   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(50, 'd')));
1384   ASSERT_THAT(ReadPacket(), IsEmpty());
1385 }
1386 
TEST_F(TraceBufferTest,Override_ReCommitAfterFullRead)1387 TEST_F(TraceBufferTest, Override_ReCommitAfterFullRead) {
1388   ResetBuffer(4096);
1389   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1390       .AddPacket(20, 'a')
1391       .AddPacket(30, 'b')
1392       .PadTo(512)
1393       .CopyIntoTraceBuffer();
1394   trace_buffer()->BeginRead();
1395   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(20, 'a')));
1396   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(30, 'b')));
1397 
1398   // Overriding a complete packet here would trigger a DCHECK because the packet
1399   // was already marked as complete.
1400   SuppressSanityDchecksForTesting();
1401   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1402       .AddPacket(20, 'a')
1403       .AddPacket(30, 'b')
1404       .AddPacket(40, 'c')
1405       .AddPacket(50, 'd')
1406       .PadTo(512)
1407       .CopyIntoTraceBuffer();
1408   trace_buffer()->BeginRead();
1409   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(40, 'c')));
1410   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(50, 'd')));
1411   ASSERT_THAT(ReadPacket(), IsEmpty());
1412 }
1413 
1414 // See also the Malicious_Override* tests above.
TEST_F(TraceBufferTest,Override_ReCommitInvalid)1415 TEST_F(TraceBufferTest, Override_ReCommitInvalid) {
1416   ResetBuffer(4096);
1417   SuppressSanityDchecksForTesting();
1418   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1419       .AddPacket(20, 'a')
1420       .AddPacket(30, 'b')
1421       .PadTo(512)
1422       .CopyIntoTraceBuffer();
1423   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
1424       .AddPacket(40, 'c')
1425       .AddPacket(50, 'd')
1426       .PadTo(512)
1427       .CopyIntoTraceBuffer();
1428   trace_buffer()->BeginRead();
1429   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(20, 'a')));
1430   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(30, 'b')));
1431   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(40, 'c')));
1432 
1433   // This should not happen when the producer behaves correctly, since it
1434   // shouldn't change the contents of chunk 0 after having allocated chunk 1.
1435   //
1436   // Since we've already started reading from chunk 1, TraceBuffer will
1437   // recognize this and discard the override.
1438   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1439       .AddPacket(20, 'e')
1440       .AddPacket(60, 'f')
1441       .AddPacket(70, 'g')
1442       .PadTo(512)
1443       .CopyIntoTraceBuffer();
1444   trace_buffer()->BeginRead();
1445   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(50, 'd')));
1446   ASSERT_THAT(ReadPacket(), IsEmpty());
1447 }
1448 
TEST_F(TraceBufferTest,Override_ReCommitReordered)1449 TEST_F(TraceBufferTest, Override_ReCommitReordered) {
1450   ResetBuffer(4096);
1451   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1452       .AddPacket(20, 'a')
1453       .AddPacket(30, 'b')
1454       .PadTo(512)
1455       .CopyIntoTraceBuffer(/*chunk_complete=*/false);
1456 
1457   trace_buffer()->BeginRead();
1458   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(20, 'a')));
1459 
1460   // Recommit chunk 0 and add chunk 1, but do this out of order.
1461   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
1462       .AddPacket(50, 'd')
1463       .AddPacket(60, 'e')
1464       .PadTo(512)
1465       .CopyIntoTraceBuffer();
1466   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1467       .AddPacket(20, 'a')
1468       .AddPacket(30, 'b')
1469       .AddPacket(40, 'c')
1470       .PadTo(512)
1471       .CopyIntoTraceBuffer();
1472 
1473   trace_buffer()->BeginRead();
1474   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(30, 'b')));
1475   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(40, 'c')));
1476   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(50, 'd')));
1477   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(60, 'e')));
1478 }
1479 
TEST_F(TraceBufferTest,Override_ReCommitReorderedFragmenting)1480 TEST_F(TraceBufferTest, Override_ReCommitReorderedFragmenting) {
1481   ResetBuffer(4096);
1482   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1483       .AddPacket(20, 'a')
1484       .AddPacket(30, 'b')
1485       .PadTo(512)
1486       .CopyIntoTraceBuffer(/*chunk_complete=*/false);
1487 
1488   trace_buffer()->BeginRead();
1489   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(20, 'a')));
1490 
1491   // Recommit chunk 0 and add chunk 1, but do this out of order.
1492   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
1493       .AddPacket(50, 'd', kContFromPrevChunk)
1494       .AddPacket(60, 'e')
1495       .PadTo(512)
1496       .CopyIntoTraceBuffer();
1497   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1498       .AddPacket(20, 'a')
1499       .AddPacket(30, 'b')
1500       .AddPacket(40, 'c', kContOnNextChunk)
1501       .PadTo(512)
1502       .CopyIntoTraceBuffer();
1503 
1504   trace_buffer()->BeginRead();
1505   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(30, 'b')));
1506   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(40, 'c'),
1507                                         FakePacketFragment(50, 'd')));
1508   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(60, 'e')));
1509 }
1510 
TEST_F(TraceBufferTest,Override_ReCommitSameBeforeRead)1511 TEST_F(TraceBufferTest, Override_ReCommitSameBeforeRead) {
1512   ResetBuffer(4096);
1513   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1514       .AddPacket(20, 'a')
1515       .AddPacket(30, 'b')
1516       .PadTo(512)
1517       .CopyIntoTraceBuffer();
1518 
1519   // Commit again the same chunk.
1520   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1521       .AddPacket(20, 'a')
1522       .AddPacket(30, 'b')
1523       .PadTo(512)
1524       .CopyIntoTraceBuffer();
1525 
1526   // Then write some new content in a new chunk.
1527   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
1528       .AddPacket(40, 'c')
1529       .AddPacket(50, 'd')
1530       .PadTo(512)
1531       .CopyIntoTraceBuffer();
1532 
1533   // The reader should keep reading from the new chunk.
1534   trace_buffer()->BeginRead();
1535   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(20, 'a')));
1536   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(30, 'b')));
1537   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(40, 'c')));
1538   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(50, 'd')));
1539   ASSERT_THAT(ReadPacket(), IsEmpty());
1540 }
1541 
TEST_F(TraceBufferTest,Override_ReCommitSameAfterRead)1542 TEST_F(TraceBufferTest, Override_ReCommitSameAfterRead) {
1543   ResetBuffer(4096);
1544   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1545       .AddPacket(20, 'a')
1546       .AddPacket(30, 'b')
1547       .PadTo(512)
1548       .CopyIntoTraceBuffer();
1549   trace_buffer()->BeginRead();
1550   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(20, 'a')));
1551   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(30, 'b')));
1552 
1553   // This re-commit should be ignored. We just re-committed an identical chunk.
1554   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1555       .AddPacket(20, 'a')
1556       .AddPacket(30, 'b')
1557       .PadTo(512)
1558       .CopyIntoTraceBuffer();
1559 
1560   // Then write some new content in a new chunk.
1561   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
1562       .AddPacket(40, 'c')
1563       .AddPacket(50, 'd')
1564       .PadTo(512)
1565       .CopyIntoTraceBuffer();
1566 
1567   // The reader should keep reading from the new chunk.
1568   trace_buffer()->BeginRead();
1569   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(40, 'c')));
1570   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(50, 'd')));
1571   ASSERT_THAT(ReadPacket(), IsEmpty());
1572 }
1573 
TEST_F(TraceBufferTest,Override_ReCommitIncompleteAfterReadOutOfOrder)1574 TEST_F(TraceBufferTest, Override_ReCommitIncompleteAfterReadOutOfOrder) {
1575   ResetBuffer(4096);
1576   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1577       .AddPacket(20, 'a')
1578       .AddPacket(30, 'b')
1579       .PadTo(512)
1580       .CopyIntoTraceBuffer(/*chunk_complete=*/false);
1581   trace_buffer()->BeginRead();
1582   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(20, 'a')));
1583   // The last packet in an incomplete chunk should be ignored as the producer
1584   // may not have completed writing it.
1585   ASSERT_THAT(ReadPacket(), IsEmpty());
1586 
1587   // Then write some new content in a new chunk.
1588   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
1589       .AddPacket(40, 'c')
1590       .AddPacket(50, 'd')
1591       .PadTo(512)
1592       .CopyIntoTraceBuffer();
1593   // The read still shouldn't be advancing past the incomplete chunk.
1594   trace_buffer()->BeginRead();
1595   ASSERT_THAT(ReadPacket(), IsEmpty());
1596 
1597   // Recommit the original chunk with no changes but mark as complete.
1598   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1599       .AddPacket(20, 'a')
1600       .AddPacket(30, 'b')
1601       .PadTo(512)
1602       .CopyIntoTraceBuffer(/*chunk_complete=*/true);
1603 
1604   // Reading should resume from the now completed chunk.
1605   trace_buffer()->BeginRead();
1606   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(30, 'b')));
1607   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(40, 'c')));
1608   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(50, 'd')));
1609   ASSERT_THAT(ReadPacket(), IsEmpty());
1610 }
1611 
TEST_F(TraceBufferTest,Override_ReCommitIncompleteFragmenting)1612 TEST_F(TraceBufferTest, Override_ReCommitIncompleteFragmenting) {
1613   ResetBuffer(4096);
1614   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1615       .AddPacket(20, 'a')
1616       .AddPacket(30, 'b', kContOnNextChunk)
1617       .PadTo(512)
1618       .CopyIntoTraceBuffer(/*chunk_complete=*/false);
1619   trace_buffer()->BeginRead();
1620   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(20, 'a')));
1621   // The last packet in an incomplete chunk should be ignored as the producer
1622   // may not have completed writing it.
1623   ASSERT_THAT(ReadPacket(), IsEmpty());
1624 
1625   // Then write some new content in a new chunk.
1626   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
1627       .AddPacket(40, 'c', kContFromPrevChunk)
1628       .AddPacket(50, 'd')
1629       .PadTo(512)
1630       .CopyIntoTraceBuffer();
1631   // The read still shouldn't be advancing past the incomplete chunk.
1632   trace_buffer()->BeginRead();
1633   ASSERT_THAT(ReadPacket(), IsEmpty());
1634 
1635   // Recommit the original chunk with no changes but mark as complete.
1636   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1637       .AddPacket(20, 'a')
1638       .AddPacket(30, 'b', kContOnNextChunk)
1639       .PadTo(512)
1640       .CopyIntoTraceBuffer(/*chunk_complete=*/true);
1641 
1642   // Reading should resume from the now completed chunk.
1643   trace_buffer()->BeginRead();
1644   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(30, 'b'),
1645                                         FakePacketFragment(40, 'c')));
1646   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(50, 'd')));
1647   ASSERT_THAT(ReadPacket(), IsEmpty());
1648 }
1649 
TEST_F(TraceBufferTest,DiscardPolicy)1650 TEST_F(TraceBufferTest, DiscardPolicy) {
1651   ResetBuffer(4096, TraceBuffer::kDiscard);
1652 
1653   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1654       .AddPacket(96 - 16, 'a')
1655       .CopyIntoTraceBuffer();
1656   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
1657       .AddPacket(4000 - 16, 'b')
1658       .CopyIntoTraceBuffer();
1659 
1660   trace_buffer()->BeginRead();
1661   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(96 - 16, 'a')));
1662 
1663   // As long as the reader catches up, writes should succeed.
1664   CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
1665       .AddPacket(48 - 16, 'c')
1666       .CopyIntoTraceBuffer();
1667   CreateChunk(ProducerID(1), WriterID(1), ChunkID(3))
1668       .AddPacket(48 - 16, 'd')
1669       .CopyIntoTraceBuffer();
1670 
1671   trace_buffer()->BeginRead();
1672   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(4000 - 16, 'b')));
1673   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(48 - 16, 'c')));
1674   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(48 - 16, 'd')));
1675   ASSERT_THAT(ReadPacket(), IsEmpty());
1676 
1677   // This will succeed.
1678   CreateChunk(ProducerID(1), WriterID(1), ChunkID(4))
1679       .AddPacket(4000 - 16, 'e')
1680       .CopyIntoTraceBuffer();
1681 
1682   // But this will fail, preventing any further write.
1683   for (int i = 0; i < 3; i++) {
1684     CreateChunk(ProducerID(1), WriterID(i + 2), ChunkID(0))
1685         .AddPacket(120 - 16, 'X')
1686         .CopyIntoTraceBuffer();
1687   }
1688 
1689   trace_buffer()->BeginRead();
1690   ASSERT_THAT(ReadPacket(), ElementsAre(FakePacketFragment(4000 - 16, 'e')));
1691   ASSERT_THAT(ReadPacket(), IsEmpty());
1692 
1693   // Even after the reader catches up, writes should still be discarded.
1694   for (int i = 0; i < 3; i++) {
1695     CreateChunk(ProducerID(1), WriterID(i + 10), ChunkID(0))
1696         .AddPacket(64 - 16, 'X')
1697         .CopyIntoTraceBuffer();
1698   }
1699   trace_buffer()->BeginRead();
1700   ASSERT_THAT(ReadPacket(), IsEmpty());
1701 }
1702 
TEST_F(TraceBufferTest,MissingPacketsOnSequence)1703 TEST_F(TraceBufferTest, MissingPacketsOnSequence) {
1704   ResetBuffer(4096);
1705   SuppressSanityDchecksForTesting();
1706   CreateChunk(ProducerID(1), WriterID(1), ChunkID(0))
1707       .AddPacket(10, 'a')
1708       .AddPacket(10, 'b')
1709       .AddPacket(10, 'c', kContOnNextChunk)
1710       .CopyIntoTraceBuffer();
1711   CreateChunk(ProducerID(2), WriterID(1), ChunkID(0))
1712       .AddPacket(10, 'u')
1713       .AddPacket(10, 'v')
1714       .AddPacket(10, 'w')
1715       .ClearBytes(10, 1)  // Clears the varint header of packet "v".
1716       .CopyIntoTraceBuffer();
1717 
1718   bool previous_packet_dropped = false;
1719 
1720   trace_buffer()->BeginRead();
1721   ASSERT_THAT(ReadPacket(nullptr, &previous_packet_dropped),
1722               ElementsAre(FakePacketFragment(10, 'a')));
1723   // First packet in first sequence, so previous one didn't exist.
1724   ASSERT_TRUE(previous_packet_dropped);
1725 
1726   ASSERT_THAT(ReadPacket(nullptr, &previous_packet_dropped),
1727               ElementsAre(FakePacketFragment(10, 'b')));
1728   // We read packet "a" before.
1729   ASSERT_FALSE(previous_packet_dropped);
1730 
1731   ASSERT_THAT(ReadPacket(nullptr, &previous_packet_dropped),
1732               ElementsAre(FakePacketFragment(10, 'u')));
1733   // First packet in second sequence, so previous one didn't exist.
1734   ASSERT_TRUE(previous_packet_dropped);
1735 
1736   // Packet "v" in second sequence is corrupted, so chunk will be skipped.
1737   ASSERT_THAT(ReadPacket(), IsEmpty());
1738 
1739   CreateChunk(ProducerID(2), WriterID(1), ChunkID(1))
1740       .AddPacket(10, 'x')
1741       .AddPacket(10, 'y')
1742       .CopyIntoTraceBuffer();
1743   CreateChunk(ProducerID(1), WriterID(1), ChunkID(1))
1744       .AddPacket(10, 'd', kContFromPrevChunk)
1745       .AddPacket(10, 'e')
1746       .CopyIntoTraceBuffer();
1747 
1748   trace_buffer()->BeginRead();
1749   ASSERT_THAT(
1750       ReadPacket(nullptr, &previous_packet_dropped),
1751       ElementsAre(FakePacketFragment(10, 'c'), FakePacketFragment(10, 'd')));
1752   // We read packet "b" before.
1753   ASSERT_FALSE(previous_packet_dropped);
1754 
1755   ASSERT_THAT(ReadPacket(nullptr, &previous_packet_dropped),
1756               ElementsAre(FakePacketFragment(10, 'e')));
1757   // We read packet "d" before.
1758   ASSERT_FALSE(previous_packet_dropped);
1759 
1760   ASSERT_THAT(ReadPacket(nullptr, &previous_packet_dropped),
1761               ElementsAre(FakePacketFragment(10, 'x')));
1762   // We didn't read packets "v" and "w".
1763   ASSERT_TRUE(previous_packet_dropped);
1764 
1765   ASSERT_THAT(ReadPacket(nullptr, &previous_packet_dropped),
1766               ElementsAre(FakePacketFragment(10, 'y')));
1767   // We read packet "x".
1768   ASSERT_FALSE(previous_packet_dropped);
1769 
1770   ASSERT_THAT(ReadPacket(), IsEmpty());
1771 
1772   // Write two large chunks that don't fit into the buffer at the same time. We
1773   // will drop the former one before we can read it.
1774   CreateChunk(ProducerID(1), WriterID(1), ChunkID(2))
1775       .AddPacket(2000, 'f')
1776       .CopyIntoTraceBuffer();
1777   CreateChunk(ProducerID(1), WriterID(1), ChunkID(3))
1778       .AddPacket(3000, 'g')
1779       .CopyIntoTraceBuffer();
1780 
1781   trace_buffer()->BeginRead();
1782   ASSERT_THAT(ReadPacket(nullptr, &previous_packet_dropped),
1783               ElementsAre(FakePacketFragment(3000, 'g')));
1784   // We didn't read packet "f".
1785   ASSERT_TRUE(previous_packet_dropped);
1786 
1787   CreateChunk(ProducerID(2), WriterID(1), ChunkID(2))
1788       .AddPacket(10, 'z')
1789       .CopyIntoTraceBuffer();
1790 
1791   trace_buffer()->BeginRead();
1792   ASSERT_THAT(ReadPacket(nullptr, &previous_packet_dropped),
1793               ElementsAre(FakePacketFragment(10, 'z')));
1794   // We've lost any state from the second producer's sequence because all its
1795   // previous chunks were removed from the buffer due to the two large chunks.
1796   // So the buffer can't be sure that no packets were dropped.
1797   ASSERT_TRUE(previous_packet_dropped);
1798 }
1799 
1800 // TODO(primiano): test stats().
1801 // TODO(primiano): test multiple streams interleaved.
1802 // TODO(primiano): more testing on packet merging.
1803 
1804 }  // namespace perfetto
1805