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