1 // Copyright (C) 2018 The Android Open Source Project
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 //      http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 #include <sys/stat.h>
16 
17 #include <cstdio>
18 #include <iostream>
19 #include <memory>
20 #include <string_view>
21 #include <vector>
22 
23 #include <android-base/file.h>
24 #include <android-base/logging.h>
25 #include <gtest/gtest.h>
26 #include <libsnapshot/cow_reader.h>
27 #include <libsnapshot/cow_writer.h>
28 #include "cow_decompress.h"
29 #include "writer_v2.h"
30 
31 using android::base::unique_fd;
32 using testing::AssertionFailure;
33 using testing::AssertionResult;
34 using testing::AssertionSuccess;
35 
36 namespace android {
37 namespace snapshot {
38 
39 class CowTest : public ::testing::Test {
40   protected:
SetUp()41     virtual void SetUp() override {
42         cow_ = std::make_unique<TemporaryFile>();
43         ASSERT_GE(cow_->fd, 0) << strerror(errno);
44     }
45 
TearDown()46     virtual void TearDown() override { cow_ = nullptr; }
47 
GetCowFd()48     unique_fd GetCowFd() { return unique_fd{dup(cow_->fd)}; }
49 
50     std::unique_ptr<TemporaryFile> cow_;
51 };
52 
53 // Helper to check read sizes.
ReadData(CowReader & reader,const CowOperation * op,void * buffer,size_t size)54 static inline bool ReadData(CowReader& reader, const CowOperation* op, void* buffer, size_t size) {
55     return reader.ReadData(op, buffer, size) == size;
56 }
57 
TEST_F(CowTest,CopyContiguous)58 TEST_F(CowTest, CopyContiguous) {
59     CowOptions options;
60     options.cluster_ops = 0;
61     CowWriterV2 writer(options, GetCowFd());
62 
63     ASSERT_TRUE(writer.Initialize());
64 
65     ASSERT_TRUE(writer.AddCopy(10, 1000, 100));
66     ASSERT_TRUE(writer.Finalize());
67     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
68 
69     CowReader reader;
70     ASSERT_TRUE(reader.Parse(cow_->fd));
71 
72     const auto& header = reader.GetHeader();
73     ASSERT_EQ(header.prefix.magic, kCowMagicNumber);
74     ASSERT_EQ(header.prefix.major_version, kCowVersionMajor);
75     ASSERT_EQ(header.prefix.minor_version, kCowVersionMinor);
76     ASSERT_EQ(header.block_size, options.block_size);
77 
78     CowFooter footer;
79     ASSERT_TRUE(reader.GetFooter(&footer));
80     ASSERT_EQ(footer.op.num_ops, 100);
81 
82     auto iter = reader.GetOpIter();
83     ASSERT_NE(iter, nullptr);
84     ASSERT_FALSE(iter->AtEnd());
85 
86     size_t i = 0;
87     while (!iter->AtEnd()) {
88         auto op = iter->Get();
89         ASSERT_EQ(op->type(), kCowCopyOp);
90         ASSERT_EQ(op->data_length, 0);
91         ASSERT_EQ(op->new_block, 10 + i);
92         ASSERT_EQ(op->source(), 1000 + i);
93         iter->Next();
94         i += 1;
95     }
96 
97     ASSERT_EQ(i, 100);
98 }
99 
TEST_F(CowTest,ReadWrite)100 TEST_F(CowTest, ReadWrite) {
101     CowOptions options;
102     options.cluster_ops = 0;
103     CowWriterV2 writer(options, GetCowFd());
104 
105     ASSERT_TRUE(writer.Initialize());
106 
107     std::string data = "This is some data, believe it";
108     data.resize(options.block_size, '\0');
109 
110     ASSERT_TRUE(writer.AddCopy(10, 20));
111     ASSERT_TRUE(writer.AddRawBlocks(50, data.data(), data.size()));
112     ASSERT_TRUE(writer.AddZeroBlocks(51, 2));
113     ASSERT_TRUE(writer.Finalize());
114 
115     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
116 
117     CowReader reader;
118     ASSERT_TRUE(reader.Parse(cow_->fd));
119 
120     const auto& header = reader.GetHeader();
121     ASSERT_EQ(header.prefix.magic, kCowMagicNumber);
122     ASSERT_EQ(header.prefix.major_version, kCowVersionMajor);
123     ASSERT_EQ(header.prefix.minor_version, kCowVersionMinor);
124     ASSERT_EQ(header.block_size, options.block_size);
125 
126     CowFooter footer;
127     ASSERT_TRUE(reader.GetFooter(&footer));
128     ASSERT_EQ(footer.op.num_ops, 4);
129 
130     auto iter = reader.GetOpIter();
131     ASSERT_NE(iter, nullptr);
132     ASSERT_FALSE(iter->AtEnd());
133     auto op = iter->Get();
134 
135     ASSERT_EQ(op->type(), kCowCopyOp);
136     ASSERT_EQ(op->data_length, 0);
137     ASSERT_EQ(op->new_block, 10);
138     ASSERT_EQ(op->source(), 20);
139 
140     std::string sink(data.size(), '\0');
141 
142     iter->Next();
143     ASSERT_FALSE(iter->AtEnd());
144     op = iter->Get();
145 
146     ASSERT_EQ(op->type(), kCowReplaceOp);
147     ASSERT_EQ(op->data_length, 4096);
148     ASSERT_EQ(op->new_block, 50);
149     ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
150     ASSERT_EQ(sink, data);
151 
152     iter->Next();
153     ASSERT_FALSE(iter->AtEnd());
154     op = iter->Get();
155 
156     // Note: the zero operation gets split into two blocks.
157     ASSERT_EQ(op->type(), kCowZeroOp);
158     ASSERT_EQ(op->data_length, 0);
159     ASSERT_EQ(op->new_block, 51);
160     ASSERT_EQ(op->source(), 0);
161 
162     iter->Next();
163     ASSERT_FALSE(iter->AtEnd());
164     op = iter->Get();
165 
166     ASSERT_EQ(op->type(), kCowZeroOp);
167     ASSERT_EQ(op->data_length, 0);
168     ASSERT_EQ(op->new_block, 52);
169     ASSERT_EQ(op->source(), 0);
170 
171     iter->Next();
172     ASSERT_TRUE(iter->AtEnd());
173 }
174 
TEST_F(CowTest,ReadWriteXor)175 TEST_F(CowTest, ReadWriteXor) {
176     CowOptions options;
177     options.cluster_ops = 0;
178     CowWriterV2 writer(options, GetCowFd());
179 
180     ASSERT_TRUE(writer.Initialize());
181 
182     std::string data = "This is some data, believe it";
183     data.resize(options.block_size, '\0');
184 
185     ASSERT_TRUE(writer.AddCopy(10, 20));
186     ASSERT_TRUE(writer.AddXorBlocks(50, data.data(), data.size(), 24, 10));
187     ASSERT_TRUE(writer.AddZeroBlocks(51, 2));
188     ASSERT_TRUE(writer.Finalize());
189 
190     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
191 
192     CowReader reader;
193     ASSERT_TRUE(reader.Parse(cow_->fd));
194 
195     const auto& header = reader.GetHeader();
196     ASSERT_EQ(header.prefix.magic, kCowMagicNumber);
197     ASSERT_EQ(header.prefix.major_version, kCowVersionMajor);
198     ASSERT_EQ(header.prefix.minor_version, kCowVersionMinor);
199     ASSERT_EQ(header.block_size, options.block_size);
200 
201     CowFooter footer;
202     ASSERT_TRUE(reader.GetFooter(&footer));
203     ASSERT_EQ(footer.op.num_ops, 4);
204 
205     auto iter = reader.GetOpIter();
206     ASSERT_NE(iter, nullptr);
207     ASSERT_FALSE(iter->AtEnd());
208     auto op = iter->Get();
209 
210     ASSERT_EQ(op->type(), kCowCopyOp);
211     ASSERT_EQ(op->data_length, 0);
212     ASSERT_EQ(op->new_block, 10);
213     ASSERT_EQ(op->source(), 20);
214 
215     std::string sink(data.size(), '\0');
216 
217     iter->Next();
218     ASSERT_FALSE(iter->AtEnd());
219     op = iter->Get();
220 
221     ASSERT_EQ(op->type(), kCowXorOp);
222     ASSERT_EQ(op->data_length, 4096);
223     ASSERT_EQ(op->new_block, 50);
224     ASSERT_EQ(op->source(), 98314);  // 4096 * 24 + 10
225     ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
226     ASSERT_EQ(sink, data);
227 
228     iter->Next();
229     ASSERT_FALSE(iter->AtEnd());
230     op = iter->Get();
231 
232     // Note: the zero operation gets split into two blocks.
233     ASSERT_EQ(op->type(), kCowZeroOp);
234     ASSERT_EQ(op->data_length, 0);
235     ASSERT_EQ(op->new_block, 51);
236     ASSERT_EQ(op->source(), 0);
237 
238     iter->Next();
239     ASSERT_FALSE(iter->AtEnd());
240     op = iter->Get();
241 
242     ASSERT_EQ(op->type(), kCowZeroOp);
243     ASSERT_EQ(op->data_length, 0);
244     ASSERT_EQ(op->new_block, 52);
245     ASSERT_EQ(op->source(), 0);
246 
247     iter->Next();
248     ASSERT_TRUE(iter->AtEnd());
249 }
250 
TEST_F(CowTest,CompressGz)251 TEST_F(CowTest, CompressGz) {
252     CowOptions options;
253     options.cluster_ops = 0;
254     options.compression = "gz";
255     CowWriterV2 writer(options, GetCowFd());
256 
257     ASSERT_TRUE(writer.Initialize());
258 
259     std::string data = "This is some data, believe it";
260     data.resize(options.block_size, '\0');
261 
262     ASSERT_TRUE(writer.AddRawBlocks(50, data.data(), data.size()));
263     ASSERT_TRUE(writer.Finalize());
264 
265     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
266 
267     CowReader reader;
268     ASSERT_TRUE(reader.Parse(cow_->fd));
269 
270     auto iter = reader.GetOpIter();
271     ASSERT_NE(iter, nullptr);
272     ASSERT_FALSE(iter->AtEnd());
273     auto op = iter->Get();
274 
275     std::string sink(data.size(), '\0');
276 
277     ASSERT_EQ(op->type(), kCowReplaceOp);
278     ASSERT_EQ(op->data_length, 56);  // compressed!
279     ASSERT_EQ(op->new_block, 50);
280     ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
281     ASSERT_EQ(sink, data);
282 
283     iter->Next();
284     ASSERT_TRUE(iter->AtEnd());
285 }
286 
287 class CompressionTest : public CowTest, public testing::WithParamInterface<const char*> {};
288 
TEST_P(CompressionTest,ThreadedBatchWrites)289 TEST_P(CompressionTest, ThreadedBatchWrites) {
290     CowOptions options;
291     options.compression = GetParam();
292     options.num_compress_threads = 2;
293 
294     CowWriterV2 writer(options, GetCowFd());
295 
296     ASSERT_TRUE(writer.Initialize());
297 
298     std::string xor_data = "This is test data-1. Testing xor";
299     xor_data.resize(options.block_size, '\0');
300     ASSERT_TRUE(writer.AddXorBlocks(50, xor_data.data(), xor_data.size(), 24, 10));
301 
302     std::string data = "This is test data-2. Testing replace ops";
303     data.resize(options.block_size * 2048, '\0');
304     ASSERT_TRUE(writer.AddRawBlocks(100, data.data(), data.size()));
305 
306     std::string data2 = "This is test data-3. Testing replace ops";
307     data2.resize(options.block_size * 259, '\0');
308     ASSERT_TRUE(writer.AddRawBlocks(6000, data2.data(), data2.size()));
309 
310     std::string data3 = "This is test data-4. Testing replace ops";
311     data3.resize(options.block_size, '\0');
312     ASSERT_TRUE(writer.AddRawBlocks(9000, data3.data(), data3.size()));
313 
314     ASSERT_TRUE(writer.Finalize());
315 
316     int expected_blocks = (1 + 2048 + 259 + 1);
317     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
318 
319     CowReader reader;
320     ASSERT_TRUE(reader.Parse(cow_->fd));
321 
322     auto iter = reader.GetOpIter();
323     ASSERT_NE(iter, nullptr);
324 
325     int total_blocks = 0;
326     while (!iter->AtEnd()) {
327         auto op = iter->Get();
328 
329         if (op->type() == kCowXorOp) {
330             total_blocks += 1;
331             std::string sink(xor_data.size(), '\0');
332             ASSERT_EQ(op->new_block, 50);
333             ASSERT_EQ(op->source(), 98314);  // 4096 * 24 + 10
334             ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
335             ASSERT_EQ(sink, xor_data);
336         }
337 
338         if (op->type() == kCowReplaceOp) {
339             total_blocks += 1;
340             if (op->new_block == 100) {
341                 data.resize(options.block_size);
342                 std::string sink(data.size(), '\0');
343                 ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
344                 ASSERT_EQ(sink.size(), data.size());
345                 ASSERT_EQ(sink, data);
346             }
347             if (op->new_block == 6000) {
348                 data2.resize(options.block_size);
349                 std::string sink(data2.size(), '\0');
350                 ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
351                 ASSERT_EQ(sink, data2);
352             }
353             if (op->new_block == 9000) {
354                 std::string sink(data3.size(), '\0');
355                 ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
356                 ASSERT_EQ(sink, data3);
357             }
358         }
359 
360         iter->Next();
361     }
362 
363     ASSERT_EQ(total_blocks, expected_blocks);
364 }
365 
TEST_P(CompressionTest,NoBatchWrites)366 TEST_P(CompressionTest, NoBatchWrites) {
367     CowOptions options;
368     options.compression = GetParam();
369     options.num_compress_threads = 1;
370     options.cluster_ops = 0;
371 
372     CowWriterV2 writer(options, GetCowFd());
373 
374     ASSERT_TRUE(writer.Initialize());
375 
376     std::string data = "Testing replace ops without batch writes";
377     data.resize(options.block_size * 1024, '\0');
378     ASSERT_TRUE(writer.AddRawBlocks(50, data.data(), data.size()));
379 
380     std::string data2 = "Testing odd blocks without batch writes";
381     data2.resize(options.block_size * 111, '\0');
382     ASSERT_TRUE(writer.AddRawBlocks(3000, data2.data(), data2.size()));
383 
384     std::string data3 = "Testing single 4k block";
385     data3.resize(options.block_size, '\0');
386     ASSERT_TRUE(writer.AddRawBlocks(5000, data3.data(), data3.size()));
387 
388     ASSERT_TRUE(writer.Finalize());
389 
390     int expected_blocks = (1024 + 111 + 1);
391     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
392 
393     CowReader reader;
394     ASSERT_TRUE(reader.Parse(cow_->fd));
395 
396     auto iter = reader.GetOpIter();
397     ASSERT_NE(iter, nullptr);
398 
399     int total_blocks = 0;
400     while (!iter->AtEnd()) {
401         auto op = iter->Get();
402 
403         if (op->type() == kCowReplaceOp) {
404             total_blocks += 1;
405             if (op->new_block == 50) {
406                 data.resize(options.block_size);
407                 std::string sink(data.size(), '\0');
408                 ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
409                 ASSERT_EQ(sink, data);
410             }
411             if (op->new_block == 3000) {
412                 data2.resize(options.block_size);
413                 std::string sink(data2.size(), '\0');
414                 ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
415                 ASSERT_EQ(sink, data2);
416             }
417             if (op->new_block == 5000) {
418                 std::string sink(data3.size(), '\0');
419                 ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
420                 ASSERT_EQ(sink, data3);
421             }
422         }
423 
424         iter->Next();
425     }
426 
427     ASSERT_EQ(total_blocks, expected_blocks);
428 }
429 
430 template <typename T>
431 class HorribleStream : public IByteStream {
432   public:
HorribleStream(const std::vector<T> & input)433     HorribleStream(const std::vector<T>& input) : input_(input) {}
434 
Read(void * buffer,size_t length)435     ssize_t Read(void* buffer, size_t length) override {
436         if (pos_ >= input_.size()) {
437             return 0;
438         }
439         if (length) {
440             *reinterpret_cast<char*>(buffer) = input_[pos_];
441         }
442         pos_++;
443         return 1;
444     }
Size() const445     size_t Size() const override { return input_.size(); }
446 
447   private:
448     std::vector<T> input_;
449     size_t pos_ = 0;
450 };
451 
TEST(HorribleStream,ReadFully)452 TEST(HorribleStream, ReadFully) {
453     std::string expected_str = "this is some data";
454     std::vector<char> expected{expected_str.begin(), expected_str.end()};
455 
456     HorribleStream<char> stream(expected);
457 
458     std::vector<char> buffer(expected.size(), '\0');
459     ASSERT_TRUE(stream.ReadFully(buffer.data(), buffer.size()));
460     ASSERT_EQ(buffer, expected);
461 }
462 
TEST_P(CompressionTest,HorribleStream)463 TEST_P(CompressionTest, HorribleStream) {
464     if (strcmp(GetParam(), "none") == 0) {
465         GTEST_SKIP();
466     }
467     CowCompression compression;
468     auto algorithm = CompressionAlgorithmFromString(GetParam());
469     ASSERT_TRUE(algorithm.has_value());
470     compression.algorithm = algorithm.value();
471 
472     std::string expected = "The quick brown fox jumps over the lazy dog.";
473     expected.resize(4096, '\0');
474 
475     std::unique_ptr<ICompressor> compressor = ICompressor::Create(compression, 4096);
476     auto result = compressor->Compress(expected.data(), expected.size());
477     ASSERT_FALSE(result.empty());
478 
479     HorribleStream<uint8_t> stream(result);
480     auto decomp = IDecompressor::FromString(GetParam());
481     ASSERT_NE(decomp, nullptr);
482     decomp->set_stream(&stream);
483 
484     expected = expected.substr(10, 500);
485 
486     std::string buffer(expected.size(), '\0');
487     ASSERT_EQ(decomp->Decompress(buffer.data(), 500, 4096, 10), 500);
488     ASSERT_EQ(buffer, expected);
489 }
490 
491 INSTANTIATE_TEST_SUITE_P(AllCompressors, CompressionTest,
492                          testing::Values("none", "gz", "brotli", "lz4"));
493 
TEST_F(CowTest,ClusterCompressGz)494 TEST_F(CowTest, ClusterCompressGz) {
495     CowOptions options;
496     options.compression = "gz";
497     options.cluster_ops = 2;
498     CowWriterV2 writer(options, GetCowFd());
499 
500     ASSERT_TRUE(writer.Initialize());
501 
502     std::string data = "This is some data, believe it";
503     data.resize(options.block_size, '\0');
504     ASSERT_TRUE(writer.AddRawBlocks(50, data.data(), data.size()));
505 
506     std::string data2 = "More data!";
507     data2.resize(options.block_size, '\0');
508     ASSERT_TRUE(writer.AddRawBlocks(51, data2.data(), data2.size()));
509 
510     ASSERT_TRUE(writer.Finalize());
511 
512     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
513 
514     CowReader reader;
515     ASSERT_TRUE(reader.Parse(cow_->fd));
516 
517     auto iter = reader.GetOpIter();
518     ASSERT_NE(iter, nullptr);
519     ASSERT_FALSE(iter->AtEnd());
520     auto op = iter->Get();
521 
522     std::string sink(data.size(), '\0');
523 
524     ASSERT_EQ(op->type(), kCowReplaceOp);
525     ASSERT_EQ(op->data_length, 56);  // compressed!
526     ASSERT_EQ(op->new_block, 50);
527     ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
528     ASSERT_EQ(sink, data);
529 
530     iter->Next();
531     ASSERT_FALSE(iter->AtEnd());
532     op = iter->Get();
533 
534     ASSERT_EQ(op->type(), kCowClusterOp);
535 
536     iter->Next();
537     ASSERT_FALSE(iter->AtEnd());
538     op = iter->Get();
539 
540     sink = {};
541     sink.resize(data2.size(), '\0');
542     ASSERT_EQ(op->data_length, 41);  // compressed!
543     ASSERT_EQ(op->new_block, 51);
544     ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
545     ASSERT_EQ(sink, data2);
546 
547     iter->Next();
548     ASSERT_FALSE(iter->AtEnd());
549     op = iter->Get();
550 
551     ASSERT_EQ(op->type(), kCowClusterOp);
552 
553     iter->Next();
554     ASSERT_TRUE(iter->AtEnd());
555 }
556 
TEST_F(CowTest,CompressTwoBlocks)557 TEST_F(CowTest, CompressTwoBlocks) {
558     CowOptions options;
559     options.compression = "gz";
560     options.cluster_ops = 0;
561     CowWriterV2 writer(options, GetCowFd());
562 
563     ASSERT_TRUE(writer.Initialize());
564 
565     std::string data = "This is some data, believe it";
566     data.resize(options.block_size * 2, '\0');
567 
568     ASSERT_TRUE(writer.AddRawBlocks(50, data.data(), data.size()));
569     ASSERT_TRUE(writer.Finalize());
570 
571     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
572 
573     CowReader reader;
574     ASSERT_TRUE(reader.Parse(cow_->fd));
575 
576     auto iter = reader.GetOpIter();
577     ASSERT_NE(iter, nullptr);
578     ASSERT_FALSE(iter->AtEnd());
579     iter->Next();
580     ASSERT_FALSE(iter->AtEnd());
581 
582     std::string sink(options.block_size, '\0');
583 
584     auto op = iter->Get();
585     ASSERT_EQ(op->type(), kCowReplaceOp);
586     ASSERT_EQ(op->new_block, 51);
587     ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
588 }
589 
TEST_F(CowTest,GetSize)590 TEST_F(CowTest, GetSize) {
591     CowOptions options;
592     options.cluster_ops = 0;
593     CowWriterV2 writer(options, GetCowFd());
594     if (ftruncate(cow_->fd, 0) < 0) {
595         perror("Fails to set temp file size");
596         FAIL();
597     }
598     ASSERT_TRUE(writer.Initialize());
599 
600     std::string data = "This is some data, believe it";
601     data.resize(options.block_size, '\0');
602 
603     ASSERT_TRUE(writer.AddCopy(10, 20));
604     ASSERT_TRUE(writer.AddRawBlocks(50, data.data(), data.size()));
605     ASSERT_TRUE(writer.AddZeroBlocks(51, 2));
606     auto size_before = writer.GetCowSizeInfo().cow_size;
607     ASSERT_TRUE(writer.Finalize());
608     auto size_after = writer.GetCowSizeInfo().cow_size;
609     ASSERT_EQ(size_before, size_after);
610     struct stat buf;
611 
612     ASSERT_GE(fstat(cow_->fd, &buf), 0) << strerror(errno);
613     ASSERT_EQ(buf.st_size, writer.GetCowSizeInfo().cow_size);
614 }
615 
TEST_F(CowTest,AppendLabelSmall)616 TEST_F(CowTest, AppendLabelSmall) {
617     CowOptions options;
618     options.cluster_ops = 0;
619     auto writer = std::make_unique<CowWriterV2>(options, GetCowFd());
620     ASSERT_TRUE(writer->Initialize());
621 
622     std::string data = "This is some data, believe it";
623     data.resize(options.block_size, '\0');
624     ASSERT_TRUE(writer->AddRawBlocks(50, data.data(), data.size()));
625     ASSERT_TRUE(writer->AddLabel(3));
626     ASSERT_TRUE(writer->Finalize());
627 
628     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
629 
630     writer = std::make_unique<CowWriterV2>(options, GetCowFd());
631     ASSERT_TRUE(writer->Initialize({3}));
632 
633     std::string data2 = "More data!";
634     data2.resize(options.block_size, '\0');
635     ASSERT_TRUE(writer->AddRawBlocks(51, data2.data(), data2.size()));
636     ASSERT_TRUE(writer->Finalize());
637 
638     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
639 
640     struct stat buf;
641     ASSERT_EQ(fstat(cow_->fd, &buf), 0);
642     ASSERT_EQ(buf.st_size, writer->GetCowSizeInfo().cow_size);
643 
644     // Read back both operations, and label.
645     CowReader reader;
646     uint64_t label;
647     ASSERT_TRUE(reader.Parse(cow_->fd));
648     ASSERT_TRUE(reader.GetLastLabel(&label));
649     ASSERT_EQ(label, 3);
650 
651     std::string sink(data.size(), '\0');
652 
653     auto iter = reader.GetOpIter();
654     ASSERT_NE(iter, nullptr);
655 
656     ASSERT_FALSE(iter->AtEnd());
657     auto op = iter->Get();
658     ASSERT_EQ(op->type(), kCowReplaceOp);
659     ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
660     ASSERT_EQ(sink, data);
661 
662     iter->Next();
663     sink = {};
664     sink.resize(data2.size(), '\0');
665 
666     ASSERT_FALSE(iter->AtEnd());
667     op = iter->Get();
668     ASSERT_EQ(op->type(), kCowLabelOp);
669     ASSERT_EQ(op->source(), 3);
670 
671     iter->Next();
672 
673     ASSERT_FALSE(iter->AtEnd());
674     op = iter->Get();
675     ASSERT_EQ(op->type(), kCowReplaceOp);
676     ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
677     ASSERT_EQ(sink, data2);
678 
679     iter->Next();
680     ASSERT_TRUE(iter->AtEnd());
681 }
682 
TEST_F(CowTest,AppendLabelMissing)683 TEST_F(CowTest, AppendLabelMissing) {
684     CowOptions options;
685     options.cluster_ops = 0;
686     auto writer = std::make_unique<CowWriterV2>(options, GetCowFd());
687     ASSERT_TRUE(writer->Initialize());
688 
689     ASSERT_TRUE(writer->AddLabel(0));
690     std::string data = "This is some data, believe it";
691     data.resize(options.block_size, '\0');
692     ASSERT_TRUE(writer->AddRawBlocks(50, data.data(), data.size()));
693     ASSERT_TRUE(writer->AddLabel(1));
694     // Drop the tail end of the last op header, corrupting it.
695     ftruncate(cow_->fd, writer->GetCowSizeInfo().cow_size - sizeof(CowFooter) - 3);
696 
697     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
698 
699     writer = std::make_unique<CowWriterV2>(options, GetCowFd());
700     ASSERT_FALSE(writer->Initialize({1}));
701     ASSERT_TRUE(writer->Initialize({0}));
702 
703     ASSERT_TRUE(writer->AddZeroBlocks(51, 1));
704     ASSERT_TRUE(writer->Finalize());
705 
706     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
707 
708     struct stat buf;
709     ASSERT_EQ(fstat(cow_->fd, &buf), 0);
710     ASSERT_EQ(buf.st_size, writer->GetCowSizeInfo().cow_size);
711 
712     // Read back both operations.
713     CowReader reader;
714     ASSERT_TRUE(reader.Parse(cow_->fd));
715 
716     auto iter = reader.GetOpIter();
717     ASSERT_NE(iter, nullptr);
718 
719     ASSERT_FALSE(iter->AtEnd());
720     auto op = iter->Get();
721     ASSERT_EQ(op->type(), kCowLabelOp);
722     ASSERT_EQ(op->source(), 0);
723 
724     iter->Next();
725 
726     ASSERT_FALSE(iter->AtEnd());
727     op = iter->Get();
728     ASSERT_EQ(op->type(), kCowZeroOp);
729 
730     iter->Next();
731 
732     ASSERT_TRUE(iter->AtEnd());
733 }
734 
TEST_F(CowTest,AppendExtendedCorrupted)735 TEST_F(CowTest, AppendExtendedCorrupted) {
736     CowOptions options;
737     options.cluster_ops = 0;
738     auto writer = std::make_unique<CowWriterV2>(options, GetCowFd());
739     ASSERT_TRUE(writer->Initialize());
740 
741     ASSERT_TRUE(writer->AddLabel(5));
742 
743     std::string data = "This is some data, believe it";
744     data.resize(options.block_size * 2, '\0');
745     ASSERT_TRUE(writer->AddRawBlocks(50, data.data(), data.size()));
746     ASSERT_TRUE(writer->AddLabel(6));
747 
748     // fail to write the footer. Cow Format does not know if Label 6 is valid
749 
750     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
751 
752     // Get the last known good label
753     CowReader label_reader;
754     uint64_t label;
755     ASSERT_TRUE(label_reader.Parse(cow_->fd, {5}));
756     ASSERT_TRUE(label_reader.GetLastLabel(&label));
757     ASSERT_EQ(label, 5);
758 
759     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
760 
761     writer = std::make_unique<CowWriterV2>(options, GetCowFd());
762     ASSERT_TRUE(writer->Initialize({5}));
763 
764     ASSERT_TRUE(writer->Finalize());
765 
766     struct stat buf;
767     ASSERT_EQ(fstat(cow_->fd, &buf), 0);
768     ASSERT_EQ(buf.st_size, writer->GetCowSizeInfo().cow_size);
769 
770     // Read back all valid operations
771     CowReader reader;
772     ASSERT_TRUE(reader.Parse(cow_->fd));
773 
774     auto iter = reader.GetOpIter();
775     ASSERT_NE(iter, nullptr);
776 
777     ASSERT_FALSE(iter->AtEnd());
778     auto op = iter->Get();
779     ASSERT_EQ(op->type(), kCowLabelOp);
780     ASSERT_EQ(op->source(), 5);
781 
782     iter->Next();
783     ASSERT_TRUE(iter->AtEnd());
784 }
785 
TEST_F(CowTest,AppendbyLabel)786 TEST_F(CowTest, AppendbyLabel) {
787     CowOptions options;
788     options.cluster_ops = 0;
789     auto writer = std::make_unique<CowWriterV2>(options, GetCowFd());
790     ASSERT_TRUE(writer->Initialize());
791 
792     std::string data = "This is some data, believe it";
793     data.resize(options.block_size * 2, '\0');
794     ASSERT_TRUE(writer->AddRawBlocks(50, data.data(), data.size()));
795 
796     ASSERT_TRUE(writer->AddLabel(4));
797 
798     ASSERT_TRUE(writer->AddZeroBlocks(50, 2));
799 
800     ASSERT_TRUE(writer->AddLabel(5));
801 
802     ASSERT_TRUE(writer->AddCopy(5, 6));
803 
804     ASSERT_TRUE(writer->AddLabel(6));
805 
806     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
807 
808     writer = std::make_unique<CowWriterV2>(options, GetCowFd());
809     ASSERT_FALSE(writer->Initialize({12}));
810     ASSERT_TRUE(writer->Initialize({5}));
811 
812     // This should drop label 6
813     ASSERT_TRUE(writer->Finalize());
814 
815     struct stat buf;
816     ASSERT_EQ(fstat(cow_->fd, &buf), 0);
817     ASSERT_EQ(buf.st_size, writer->GetCowSizeInfo().cow_size);
818 
819     // Read back all ops
820     CowReader reader;
821     ASSERT_TRUE(reader.Parse(cow_->fd));
822 
823     std::string sink(options.block_size, '\0');
824 
825     auto iter = reader.GetOpIter();
826     ASSERT_NE(iter, nullptr);
827 
828     ASSERT_FALSE(iter->AtEnd());
829     auto op = iter->Get();
830     ASSERT_EQ(op->type(), kCowReplaceOp);
831     ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
832     ASSERT_EQ(sink, data.substr(0, options.block_size));
833 
834     iter->Next();
835     sink = {};
836     sink.resize(options.block_size, '\0');
837 
838     ASSERT_FALSE(iter->AtEnd());
839     op = iter->Get();
840     ASSERT_EQ(op->type(), kCowReplaceOp);
841     ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
842     ASSERT_EQ(sink, data.substr(options.block_size, 2 * options.block_size));
843 
844     iter->Next();
845 
846     ASSERT_FALSE(iter->AtEnd());
847     op = iter->Get();
848     ASSERT_EQ(op->type(), kCowLabelOp);
849     ASSERT_EQ(op->source(), 4);
850 
851     iter->Next();
852 
853     ASSERT_FALSE(iter->AtEnd());
854     op = iter->Get();
855     ASSERT_EQ(op->type(), kCowZeroOp);
856 
857     iter->Next();
858 
859     ASSERT_FALSE(iter->AtEnd());
860     op = iter->Get();
861     ASSERT_EQ(op->type(), kCowZeroOp);
862 
863     iter->Next();
864     ASSERT_FALSE(iter->AtEnd());
865     op = iter->Get();
866     ASSERT_EQ(op->type(), kCowLabelOp);
867     ASSERT_EQ(op->source(), 5);
868 
869     iter->Next();
870 
871     ASSERT_TRUE(iter->AtEnd());
872 }
873 
TEST_F(CowTest,ClusterTest)874 TEST_F(CowTest, ClusterTest) {
875     CowOptions options;
876     options.cluster_ops = 4;
877     auto writer = std::make_unique<CowWriterV2>(options, GetCowFd());
878     ASSERT_TRUE(writer->Initialize());
879 
880     std::string data = "This is some data, believe it";
881     data.resize(options.block_size, '\0');
882     ASSERT_TRUE(writer->AddRawBlocks(50, data.data(), data.size()));
883 
884     ASSERT_TRUE(writer->AddLabel(4));
885 
886     ASSERT_TRUE(writer->AddZeroBlocks(50, 2));  // Cluster split in middle
887 
888     ASSERT_TRUE(writer->AddLabel(5));
889 
890     ASSERT_TRUE(writer->AddCopy(5, 6));
891 
892     // Cluster split
893 
894     ASSERT_TRUE(writer->AddLabel(6));
895 
896     ASSERT_TRUE(writer->Finalize());  // No data for cluster, so no cluster split needed
897 
898     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
899 
900     // Read back all ops
901     CowReader reader;
902     ASSERT_TRUE(reader.Parse(cow_->fd));
903 
904     std::string sink(data.size(), '\0');
905 
906     auto iter = reader.GetOpIter();
907     ASSERT_NE(iter, nullptr);
908 
909     ASSERT_FALSE(iter->AtEnd());
910     auto op = iter->Get();
911     ASSERT_EQ(op->type(), kCowReplaceOp);
912     ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
913     ASSERT_EQ(sink, data.substr(0, options.block_size));
914 
915     iter->Next();
916 
917     ASSERT_FALSE(iter->AtEnd());
918     op = iter->Get();
919     ASSERT_EQ(op->type(), kCowLabelOp);
920     ASSERT_EQ(op->source(), 4);
921 
922     iter->Next();
923 
924     ASSERT_FALSE(iter->AtEnd());
925     op = iter->Get();
926     ASSERT_EQ(op->type(), kCowZeroOp);
927 
928     iter->Next();
929 
930     ASSERT_FALSE(iter->AtEnd());
931     op = iter->Get();
932     ASSERT_EQ(op->type(), kCowClusterOp);
933 
934     iter->Next();
935 
936     ASSERT_FALSE(iter->AtEnd());
937     op = iter->Get();
938     ASSERT_EQ(op->type(), kCowZeroOp);
939 
940     iter->Next();
941 
942     ASSERT_FALSE(iter->AtEnd());
943     op = iter->Get();
944     ASSERT_EQ(op->type(), kCowLabelOp);
945     ASSERT_EQ(op->source(), 5);
946 
947     iter->Next();
948 
949     ASSERT_FALSE(iter->AtEnd());
950     op = iter->Get();
951     ASSERT_EQ(op->type(), kCowCopyOp);
952 
953     iter->Next();
954 
955     ASSERT_FALSE(iter->AtEnd());
956     op = iter->Get();
957     ASSERT_EQ(op->type(), kCowClusterOp);
958 
959     iter->Next();
960 
961     ASSERT_FALSE(iter->AtEnd());
962     op = iter->Get();
963     ASSERT_EQ(op->type(), kCowLabelOp);
964     ASSERT_EQ(op->source(), 6);
965 
966     iter->Next();
967 
968     ASSERT_TRUE(iter->AtEnd());
969 }
970 
TEST_F(CowTest,ClusterAppendTest)971 TEST_F(CowTest, ClusterAppendTest) {
972     CowOptions options;
973     options.cluster_ops = 3;
974     auto writer = std::make_unique<CowWriterV2>(options, GetCowFd());
975     ASSERT_TRUE(writer->Initialize());
976 
977     ASSERT_TRUE(writer->AddLabel(50));
978     ASSERT_TRUE(writer->Finalize());  // Adds a cluster op, should be dropped on append
979 
980     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
981 
982     writer = std::make_unique<CowWriterV2>(options, GetCowFd());
983     ASSERT_TRUE(writer->Initialize({50}));
984 
985     std::string data2 = "More data!";
986     data2.resize(options.block_size, '\0');
987     ASSERT_TRUE(writer->AddRawBlocks(51, data2.data(), data2.size()));
988     ASSERT_TRUE(writer->Finalize());  // Adds a cluster op
989 
990     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
991 
992     struct stat buf;
993     ASSERT_EQ(fstat(cow_->fd, &buf), 0);
994     ASSERT_EQ(buf.st_size, writer->GetCowSizeInfo().cow_size);
995 
996     // Read back both operations, plus cluster op at end
997     CowReader reader;
998     uint64_t label;
999     ASSERT_TRUE(reader.Parse(cow_->fd));
1000     ASSERT_TRUE(reader.GetLastLabel(&label));
1001     ASSERT_EQ(label, 50);
1002 
1003     std::string sink(data2.size(), '\0');
1004 
1005     auto iter = reader.GetOpIter();
1006     ASSERT_NE(iter, nullptr);
1007 
1008     ASSERT_FALSE(iter->AtEnd());
1009     auto op = iter->Get();
1010     ASSERT_EQ(op->type(), kCowLabelOp);
1011     ASSERT_EQ(op->source(), 50);
1012 
1013     iter->Next();
1014 
1015     ASSERT_FALSE(iter->AtEnd());
1016     op = iter->Get();
1017     ASSERT_EQ(op->type(), kCowReplaceOp);
1018     ASSERT_TRUE(ReadData(reader, op, sink.data(), sink.size()));
1019     ASSERT_EQ(sink, data2);
1020 
1021     iter->Next();
1022 
1023     ASSERT_FALSE(iter->AtEnd());
1024     op = iter->Get();
1025     ASSERT_EQ(op->type(), kCowClusterOp);
1026 
1027     iter->Next();
1028 
1029     ASSERT_TRUE(iter->AtEnd());
1030 }
1031 
TEST_F(CowTest,AppendAfterFinalize)1032 TEST_F(CowTest, AppendAfterFinalize) {
1033     CowOptions options;
1034     options.cluster_ops = 0;
1035     auto writer = std::make_unique<CowWriterV2>(options, GetCowFd());
1036     ASSERT_TRUE(writer->Initialize());
1037 
1038     std::string data = "This is some data, believe it";
1039     data.resize(options.block_size, '\0');
1040     ASSERT_TRUE(writer->AddRawBlocks(50, data.data(), data.size()));
1041     ASSERT_TRUE(writer->AddLabel(3));
1042     ASSERT_TRUE(writer->Finalize());
1043 
1044     std::string data2 = "More data!";
1045     data2.resize(options.block_size, '\0');
1046     ASSERT_TRUE(writer->AddRawBlocks(51, data2.data(), data2.size()));
1047     ASSERT_TRUE(writer->Finalize());
1048 
1049     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
1050 
1051     // COW should be valid.
1052     CowReader reader;
1053     ASSERT_TRUE(reader.Parse(cow_->fd));
1054 }
1055 
WriteDataBlock(ICowWriter * writer,uint64_t new_block,std::string data)1056 AssertionResult WriteDataBlock(ICowWriter* writer, uint64_t new_block, std::string data) {
1057     data.resize(writer->GetBlockSize(), '\0');
1058     if (!writer->AddRawBlocks(new_block, data.data(), data.size())) {
1059         return AssertionFailure() << "Failed to add raw block";
1060     }
1061     return AssertionSuccess();
1062 }
1063 
CompareDataBlock(CowReader * reader,const CowOperation * op,const std::string & data)1064 AssertionResult CompareDataBlock(CowReader* reader, const CowOperation* op,
1065                                  const std::string& data) {
1066     const auto& header = reader->GetHeader();
1067 
1068     std::string cmp = data;
1069     cmp.resize(header.block_size, '\0');
1070 
1071     std::string sink(cmp.size(), '\0');
1072     if (!reader->ReadData(op, sink.data(), sink.size())) {
1073         return AssertionFailure() << "Failed to read data block";
1074     }
1075     if (cmp != sink) {
1076         return AssertionFailure() << "Data blocks did not match, expected " << cmp << ", got "
1077                                   << sink;
1078     }
1079 
1080     return AssertionSuccess();
1081 }
1082 
TEST_F(CowTest,ResumeMidCluster)1083 TEST_F(CowTest, ResumeMidCluster) {
1084     CowOptions options;
1085     options.cluster_ops = 7;
1086     auto writer = std::make_unique<CowWriterV2>(options, GetCowFd());
1087     ASSERT_TRUE(writer->Initialize());
1088 
1089     ASSERT_TRUE(WriteDataBlock(writer.get(), 1, "Block 1"));
1090     ASSERT_TRUE(WriteDataBlock(writer.get(), 2, "Block 2"));
1091     ASSERT_TRUE(WriteDataBlock(writer.get(), 3, "Block 3"));
1092     ASSERT_TRUE(writer->AddLabel(1));
1093     ASSERT_TRUE(writer->Finalize());
1094     ASSERT_TRUE(WriteDataBlock(writer.get(), 4, "Block 4"));
1095     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
1096 
1097     writer = std::make_unique<CowWriterV2>(options, GetCowFd());
1098     ASSERT_TRUE(writer->Initialize({1}));
1099     ASSERT_TRUE(WriteDataBlock(writer.get(), 4, "Block 4"));
1100     ASSERT_TRUE(WriteDataBlock(writer.get(), 5, "Block 5"));
1101     ASSERT_TRUE(WriteDataBlock(writer.get(), 6, "Block 6"));
1102     ASSERT_TRUE(WriteDataBlock(writer.get(), 7, "Block 7"));
1103     ASSERT_TRUE(WriteDataBlock(writer.get(), 8, "Block 8"));
1104     ASSERT_TRUE(writer->AddLabel(2));
1105     ASSERT_TRUE(writer->Finalize());
1106     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
1107 
1108     CowReader reader;
1109     ASSERT_TRUE(reader.Parse(cow_->fd));
1110 
1111     auto iter = reader.GetOpIter();
1112     size_t num_replace = 0;
1113     size_t max_in_cluster = 0;
1114     size_t num_in_cluster = 0;
1115     size_t num_clusters = 0;
1116     while (!iter->AtEnd()) {
1117         const auto& op = iter->Get();
1118 
1119         num_in_cluster++;
1120         max_in_cluster = std::max(max_in_cluster, num_in_cluster);
1121 
1122         if (op->type() == kCowReplaceOp) {
1123             num_replace++;
1124 
1125             ASSERT_EQ(op->new_block, num_replace);
1126             ASSERT_TRUE(CompareDataBlock(&reader, op, "Block " + std::to_string(num_replace)));
1127         } else if (op->type() == kCowClusterOp) {
1128             num_in_cluster = 0;
1129             num_clusters++;
1130         }
1131 
1132         iter->Next();
1133     }
1134     ASSERT_EQ(num_replace, 8);
1135     ASSERT_EQ(max_in_cluster, 7);
1136     ASSERT_EQ(num_clusters, 2);
1137 }
1138 
TEST_F(CowTest,ResumeEndCluster)1139 TEST_F(CowTest, ResumeEndCluster) {
1140     CowOptions options;
1141     int cluster_ops = 5;
1142     options.cluster_ops = cluster_ops;
1143     auto writer = std::make_unique<CowWriterV2>(options, GetCowFd());
1144     ASSERT_TRUE(writer->Initialize());
1145 
1146     ASSERT_TRUE(WriteDataBlock(writer.get(), 1, "Block 1"));
1147     ASSERT_TRUE(WriteDataBlock(writer.get(), 2, "Block 2"));
1148     ASSERT_TRUE(WriteDataBlock(writer.get(), 3, "Block 3"));
1149     ASSERT_TRUE(writer->AddLabel(1));
1150     ASSERT_TRUE(writer->Finalize());
1151     ASSERT_TRUE(WriteDataBlock(writer.get(), 4, "Block 4"));
1152     ASSERT_TRUE(WriteDataBlock(writer.get(), 5, "Block 5"));
1153     ASSERT_TRUE(WriteDataBlock(writer.get(), 6, "Block 6"));
1154     ASSERT_TRUE(WriteDataBlock(writer.get(), 7, "Block 7"));
1155     ASSERT_TRUE(WriteDataBlock(writer.get(), 8, "Block 8"));
1156     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
1157 
1158     writer = std::make_unique<CowWriterV2>(options, GetCowFd());
1159     ASSERT_TRUE(writer->Initialize({1}));
1160     ASSERT_TRUE(WriteDataBlock(writer.get(), 4, "Block 4"));
1161     ASSERT_TRUE(WriteDataBlock(writer.get(), 5, "Block 5"));
1162     ASSERT_TRUE(WriteDataBlock(writer.get(), 6, "Block 6"));
1163     ASSERT_TRUE(WriteDataBlock(writer.get(), 7, "Block 7"));
1164     ASSERT_TRUE(WriteDataBlock(writer.get(), 8, "Block 8"));
1165     ASSERT_TRUE(writer->AddLabel(2));
1166     ASSERT_TRUE(writer->Finalize());
1167     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
1168 
1169     CowReader reader;
1170     ASSERT_TRUE(reader.Parse(cow_->fd));
1171 
1172     auto iter = reader.GetOpIter();
1173     size_t num_replace = 0;
1174     size_t max_in_cluster = 0;
1175     size_t num_in_cluster = 0;
1176     size_t num_clusters = 0;
1177     while (!iter->AtEnd()) {
1178         const auto& op = iter->Get();
1179 
1180         num_in_cluster++;
1181         max_in_cluster = std::max(max_in_cluster, num_in_cluster);
1182 
1183         if (op->type() == kCowReplaceOp) {
1184             num_replace++;
1185 
1186             ASSERT_EQ(op->new_block, num_replace);
1187             ASSERT_TRUE(CompareDataBlock(&reader, op, "Block " + std::to_string(num_replace)));
1188         } else if (op->type() == kCowClusterOp) {
1189             num_in_cluster = 0;
1190             num_clusters++;
1191         }
1192 
1193         iter->Next();
1194     }
1195     ASSERT_EQ(num_replace, 8);
1196     ASSERT_EQ(max_in_cluster, cluster_ops);
1197     ASSERT_EQ(num_clusters, 3);
1198 }
1199 
TEST_F(CowTest,DeleteMidCluster)1200 TEST_F(CowTest, DeleteMidCluster) {
1201     CowOptions options;
1202     options.cluster_ops = 7;
1203     auto writer = std::make_unique<CowWriterV2>(options, GetCowFd());
1204     ASSERT_TRUE(writer->Initialize());
1205 
1206     ASSERT_TRUE(WriteDataBlock(writer.get(), 1, "Block 1"));
1207     ASSERT_TRUE(WriteDataBlock(writer.get(), 2, "Block 2"));
1208     ASSERT_TRUE(WriteDataBlock(writer.get(), 3, "Block 3"));
1209     ASSERT_TRUE(writer->AddLabel(1));
1210     ASSERT_TRUE(writer->Finalize());
1211     ASSERT_TRUE(WriteDataBlock(writer.get(), 4, "Block 4"));
1212     ASSERT_TRUE(WriteDataBlock(writer.get(), 5, "Block 5"));
1213     ASSERT_TRUE(WriteDataBlock(writer.get(), 6, "Block 6"));
1214     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
1215 
1216     writer = std::make_unique<CowWriterV2>(options, GetCowFd());
1217     ASSERT_TRUE(writer->Initialize({1}));
1218     ASSERT_TRUE(writer->Finalize());
1219     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
1220 
1221     CowReader reader;
1222     ASSERT_TRUE(reader.Parse(cow_->fd));
1223 
1224     auto iter = reader.GetOpIter();
1225     size_t num_replace = 0;
1226     size_t max_in_cluster = 0;
1227     size_t num_in_cluster = 0;
1228     size_t num_clusters = 0;
1229     while (!iter->AtEnd()) {
1230         const auto& op = iter->Get();
1231 
1232         num_in_cluster++;
1233         max_in_cluster = std::max(max_in_cluster, num_in_cluster);
1234         if (op->type() == kCowReplaceOp) {
1235             num_replace++;
1236 
1237             ASSERT_EQ(op->new_block, num_replace);
1238             ASSERT_TRUE(CompareDataBlock(&reader, op, "Block " + std::to_string(num_replace)));
1239         } else if (op->type() == kCowClusterOp) {
1240             num_in_cluster = 0;
1241             num_clusters++;
1242         }
1243 
1244         iter->Next();
1245     }
1246     ASSERT_EQ(num_replace, 3);
1247     ASSERT_EQ(max_in_cluster, 5);  // 3 data, 1 label, 1 cluster op
1248     ASSERT_EQ(num_clusters, 1);
1249 }
1250 
TEST_F(CowTest,BigSeqOp)1251 TEST_F(CowTest, BigSeqOp) {
1252     CowOptions options;
1253     CowWriterV2 writer(options, GetCowFd());
1254     const int seq_len = std::numeric_limits<uint16_t>::max() / sizeof(uint32_t) + 1;
1255     uint32_t sequence[seq_len];
1256     for (int i = 0; i < seq_len; i++) {
1257         sequence[i] = i + 1;
1258     }
1259 
1260     ASSERT_TRUE(writer.Initialize());
1261 
1262     ASSERT_TRUE(writer.AddSequenceData(seq_len, sequence));
1263     ASSERT_TRUE(writer.AddZeroBlocks(1, seq_len));
1264     ASSERT_TRUE(writer.Finalize());
1265 
1266     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
1267 
1268     CowReader reader;
1269     ASSERT_TRUE(reader.Parse(cow_->fd));
1270     auto iter = reader.GetRevMergeOpIter();
1271 
1272     for (int i = 0; i < seq_len; i++) {
1273         ASSERT_TRUE(!iter->AtEnd());
1274         const auto& op = iter->Get();
1275 
1276         ASSERT_EQ(op->new_block, seq_len - i);
1277 
1278         iter->Next();
1279     }
1280     ASSERT_TRUE(iter->AtEnd());
1281 }
1282 
TEST_F(CowTest,MissingSeqOp)1283 TEST_F(CowTest, MissingSeqOp) {
1284     CowOptions options;
1285     CowWriterV2 writer(options, GetCowFd());
1286     const int seq_len = 10;
1287     uint32_t sequence[seq_len];
1288     for (int i = 0; i < seq_len; i++) {
1289         sequence[i] = i + 1;
1290     }
1291 
1292     ASSERT_TRUE(writer.Initialize());
1293 
1294     ASSERT_TRUE(writer.AddSequenceData(seq_len, sequence));
1295     ASSERT_TRUE(writer.AddZeroBlocks(1, seq_len - 1));
1296     ASSERT_TRUE(writer.Finalize());
1297 
1298     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
1299 
1300     CowReader reader;
1301     ASSERT_FALSE(reader.Parse(cow_->fd));
1302 }
1303 
TEST_F(CowTest,ResumeSeqOp)1304 TEST_F(CowTest, ResumeSeqOp) {
1305     CowOptions options;
1306     auto writer = std::make_unique<CowWriterV2>(options, GetCowFd());
1307     const int seq_len = 10;
1308     uint32_t sequence[seq_len];
1309     for (int i = 0; i < seq_len; i++) {
1310         sequence[i] = i + 1;
1311     }
1312 
1313     ASSERT_TRUE(writer->Initialize());
1314 
1315     ASSERT_TRUE(writer->AddSequenceData(seq_len, sequence));
1316     ASSERT_TRUE(writer->AddZeroBlocks(1, seq_len / 2));
1317     ASSERT_TRUE(writer->AddLabel(1));
1318     ASSERT_TRUE(writer->AddZeroBlocks(1 + seq_len / 2, 1));
1319 
1320     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
1321     auto reader = std::make_unique<CowReader>();
1322     ASSERT_TRUE(reader->Parse(cow_->fd, 1));
1323     auto itr = reader->GetRevMergeOpIter();
1324     ASSERT_TRUE(itr->AtEnd());
1325 
1326     writer = std::make_unique<CowWriterV2>(options, GetCowFd());
1327     ASSERT_TRUE(writer->Initialize({1}));
1328     ASSERT_TRUE(writer->AddZeroBlocks(1 + seq_len / 2, seq_len / 2));
1329     ASSERT_TRUE(writer->Finalize());
1330 
1331     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
1332 
1333     reader = std::make_unique<CowReader>();
1334     ASSERT_TRUE(reader->Parse(cow_->fd));
1335 
1336     auto iter = reader->GetRevMergeOpIter();
1337 
1338     uint64_t expected_block = 10;
1339     while (!iter->AtEnd() && expected_block > 0) {
1340         ASSERT_FALSE(iter->AtEnd());
1341         const auto& op = iter->Get();
1342 
1343         ASSERT_EQ(op->new_block, expected_block);
1344 
1345         iter->Next();
1346         expected_block--;
1347     }
1348     ASSERT_EQ(expected_block, 0);
1349     ASSERT_TRUE(iter->AtEnd());
1350 }
1351 
TEST_F(CowTest,RevMergeOpItrTest)1352 TEST_F(CowTest, RevMergeOpItrTest) {
1353     CowOptions options;
1354     options.cluster_ops = 5;
1355     options.num_merge_ops = 1;
1356     CowWriterV2 writer(options, GetCowFd());
1357     uint32_t sequence[] = {2, 10, 6, 7, 3, 5};
1358 
1359     ASSERT_TRUE(writer.Initialize());
1360 
1361     ASSERT_TRUE(writer.AddSequenceData(6, sequence));
1362     ASSERT_TRUE(writer.AddCopy(6, 13));
1363     ASSERT_TRUE(writer.AddZeroBlocks(12, 1));
1364     ASSERT_TRUE(writer.AddZeroBlocks(8, 1));
1365     ASSERT_TRUE(writer.AddZeroBlocks(11, 1));
1366     ASSERT_TRUE(writer.AddCopy(3, 15));
1367     ASSERT_TRUE(writer.AddCopy(2, 11));
1368     ASSERT_TRUE(writer.AddZeroBlocks(4, 1));
1369     ASSERT_TRUE(writer.AddZeroBlocks(9, 1));
1370     ASSERT_TRUE(writer.AddCopy(5, 16));
1371     ASSERT_TRUE(writer.AddZeroBlocks(1, 1));
1372     ASSERT_TRUE(writer.AddCopy(10, 12));
1373     ASSERT_TRUE(writer.AddCopy(7, 14));
1374     ASSERT_TRUE(writer.Finalize());
1375 
1376     // New block in cow order is 6, 12, 8, 11, 3, 2, 4, 9, 5, 1, 10, 7
1377     // New block in merge order is 2, 10, 6, 7, 3, 5, 12, 11, 9, 8, 4, 1
1378     // RevMergeOrder is 1, 4, 8, 9, 11, 12, 5, 3, 7, 6, 10, 2
1379     // new block 2 is "already merged", so will be left out.
1380 
1381     std::vector<uint64_t> revMergeOpSequence = {1, 4, 8, 9, 11, 12, 5, 3, 7, 6, 10};
1382 
1383     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
1384 
1385     CowReader reader;
1386     ASSERT_TRUE(reader.Parse(cow_->fd));
1387     auto iter = reader.GetRevMergeOpIter();
1388     auto expected_new_block = revMergeOpSequence.begin();
1389 
1390     while (!iter->AtEnd() && expected_new_block != revMergeOpSequence.end()) {
1391         const auto& op = iter->Get();
1392 
1393         ASSERT_EQ(op->new_block, *expected_new_block);
1394 
1395         iter->Next();
1396         expected_new_block++;
1397     }
1398     ASSERT_EQ(expected_new_block, revMergeOpSequence.end());
1399     ASSERT_TRUE(iter->AtEnd());
1400 }
1401 
TEST_F(CowTest,ParseOptionsTest)1402 TEST_F(CowTest, ParseOptionsTest) {
1403     CowOptions options;
1404     std::vector<std::pair<std::string, bool>> testcases = {
1405             {"gz,4", true},   {"gz,4,4", false}, {"lz4,4", true}, {"brotli,4", true},
1406             {"zstd,4", true}, {"zstd,x", false}, {"zs,4", false}, {"zstd.4", false}};
1407     for (size_t i = 0; i < testcases.size(); i++) {
1408         options.compression = testcases[i].first;
1409         CowWriterV2 writer(options, GetCowFd());
1410         ASSERT_EQ(writer.Initialize(), testcases[i].second);
1411     }
1412 }
1413 
TEST_F(CowTest,LegacyRevMergeOpItrTest)1414 TEST_F(CowTest, LegacyRevMergeOpItrTest) {
1415     CowOptions options;
1416     options.cluster_ops = 5;
1417     options.num_merge_ops = 1;
1418     CowWriterV2 writer(options, GetCowFd());
1419 
1420     ASSERT_TRUE(writer.Initialize());
1421 
1422     ASSERT_TRUE(writer.AddCopy(2, 11));
1423     ASSERT_TRUE(writer.AddCopy(10, 12));
1424     ASSERT_TRUE(writer.AddCopy(6, 13));
1425     ASSERT_TRUE(writer.AddCopy(7, 14));
1426     ASSERT_TRUE(writer.AddCopy(3, 15));
1427     ASSERT_TRUE(writer.AddCopy(5, 16));
1428     ASSERT_TRUE(writer.AddZeroBlocks(12, 1));
1429     ASSERT_TRUE(writer.AddZeroBlocks(8, 1));
1430     ASSERT_TRUE(writer.AddZeroBlocks(11, 1));
1431     ASSERT_TRUE(writer.AddZeroBlocks(4, 1));
1432     ASSERT_TRUE(writer.AddZeroBlocks(9, 1));
1433     ASSERT_TRUE(writer.AddZeroBlocks(1, 1));
1434 
1435     ASSERT_TRUE(writer.Finalize());
1436 
1437     // New block in cow order is 2, 10, 6, 7, 3, 5, 12, 8, 11, 4, 9, 1
1438     // New block in merge order is 2, 10, 6, 7, 3, 5, 12, 11, 9, 8, 4, 1
1439     // RevMergeOrder is 1, 4, 8, 9, 11, 12, 5, 3, 7, 6, 10, 2
1440     // new block 2 is "already merged", so will be left out.
1441 
1442     std::vector<uint64_t> revMergeOpSequence = {1, 4, 8, 9, 11, 12, 5, 3, 7, 6, 10};
1443 
1444     ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
1445 
1446     CowReader reader;
1447     ASSERT_TRUE(reader.Parse(cow_->fd));
1448     auto iter = reader.GetRevMergeOpIter();
1449     auto expected_new_block = revMergeOpSequence.begin();
1450 
1451     while (!iter->AtEnd() && expected_new_block != revMergeOpSequence.end()) {
1452         const auto& op = iter->Get();
1453 
1454         ASSERT_EQ(op->new_block, *expected_new_block);
1455 
1456         iter->Next();
1457         expected_new_block++;
1458     }
1459     ASSERT_EQ(expected_new_block, revMergeOpSequence.end());
1460     ASSERT_TRUE(iter->AtEnd());
1461 }
1462 
TEST_F(CowTest,InvalidMergeOrderTest)1463 TEST_F(CowTest, InvalidMergeOrderTest) {
1464     CowOptions options;
1465     options.cluster_ops = 5;
1466     options.num_merge_ops = 1;
1467     std::string data = "This is some data, believe it";
1468     data.resize(options.block_size, '\0');
1469     auto writer = std::make_unique<CowWriterV2>(options, GetCowFd());
1470     CowReader reader;
1471 
1472     ASSERT_TRUE(writer->Initialize());
1473 
1474     ASSERT_TRUE(writer->AddCopy(3, 2));
1475     ASSERT_TRUE(writer->AddCopy(2, 1));
1476     ASSERT_TRUE(writer->AddLabel(1));
1477     ASSERT_TRUE(writer->Finalize());
1478     ASSERT_TRUE(reader.Parse(cow_->fd));
1479     ASSERT_TRUE(reader.VerifyMergeOps());
1480 
1481     ASSERT_TRUE(writer->Initialize({1}));
1482     ASSERT_TRUE(writer->AddCopy(4, 2));
1483     ASSERT_TRUE(writer->Finalize());
1484     ASSERT_TRUE(reader.Parse(cow_->fd));
1485     ASSERT_FALSE(reader.VerifyMergeOps());
1486 
1487     writer = std::make_unique<CowWriterV2>(options, GetCowFd());
1488     ASSERT_TRUE(writer->Initialize());
1489     ASSERT_TRUE(writer->AddCopy(2, 1));
1490     ASSERT_TRUE(writer->AddXorBlocks(3, &data, data.size(), 1, 1));
1491     ASSERT_TRUE(writer->Finalize());
1492     ASSERT_TRUE(reader.Parse(cow_->fd));
1493     ASSERT_FALSE(reader.VerifyMergeOps());
1494 }
1495 
OpenTestFile(const std::string & file,int flags)1496 unique_fd OpenTestFile(const std::string& file, int flags) {
1497     std::string path = "tools/testdata/" + file;
1498 
1499     unique_fd fd(open(path.c_str(), flags));
1500     if (fd >= 0) {
1501         return fd;
1502     }
1503 
1504     path = android::base::GetExecutableDirectory() + "/" + path;
1505     return unique_fd{open(path.c_str(), flags)};
1506 }
1507 
TEST_F(CowTest,CompatibilityTest)1508 TEST_F(CowTest, CompatibilityTest) {
1509     std::string filename = "cow_v2";
1510     auto fd = OpenTestFile(filename, O_RDONLY);
1511     if (fd.get() == -1) {
1512         LOG(ERROR) << filename << " not found";
1513         GTEST_SKIP();
1514     }
1515     CowReader reader;
1516     reader.Parse(fd);
1517 
1518     const auto& header = reader.GetHeader();
1519     ASSERT_EQ(header.prefix.magic, kCowMagicNumber);
1520     ASSERT_EQ(header.prefix.major_version, kCowVersionMajor);
1521     ASSERT_EQ(header.prefix.minor_version, kCowVersionMinor);
1522 
1523     CowFooter footer;
1524     ASSERT_TRUE(reader.GetFooter(&footer));
1525 }
1526 
TEST_F(CowTest,DecompressIncompressibleBlock)1527 TEST_F(CowTest, DecompressIncompressibleBlock) {
1528     auto fd = OpenTestFile("incompressible_block", O_RDONLY);
1529     ASSERT_GE(fd, 0);
1530 
1531     std::string original;
1532     ASSERT_TRUE(android::base::ReadFdToString(fd, &original)) << strerror(errno);
1533     ASSERT_EQ(original.size(), 4096);
1534 
1535     CowOptions options;
1536     options.compression = "gz";
1537     auto writer = CreateCowWriter(2, options, GetCowFd());
1538     ASSERT_NE(writer, nullptr);
1539     ASSERT_TRUE(writer->AddRawBlocks(0, original.data(), original.size()));
1540     ASSERT_TRUE(writer->Finalize());
1541 
1542     CowReader reader;
1543     ASSERT_TRUE(reader.Parse(cow_->fd));
1544 
1545     auto iter = reader.GetOpIter();
1546     ASSERT_NE(iter, nullptr);
1547     ASSERT_FALSE(iter->AtEnd());
1548 
1549     std::string block(original.size(), '\0');
1550     ASSERT_EQ(iter->Get()->data_length, 4096);
1551     ASSERT_TRUE(ReadData(reader, iter->Get(), block.data(), block.size()));
1552 
1553     for (size_t i = 0; i < block.size(); i++) {
1554         ASSERT_EQ(block[i], original[i]) << "mismatch at byte " << i;
1555     }
1556 }
1557 
1558 }  // namespace snapshot
1559 }  // namespace android
1560 
main(int argc,char ** argv)1561 int main(int argc, char** argv) {
1562     ::testing::InitGoogleTest(&argc, argv);
1563     return RUN_ALL_TESTS();
1564 }
1565