• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //
2 // Copyright (C) 2020 The Android Open Source Project
3 //
4 // Licensed under the Apache License, Version 2.0 (the "License");
5 // you may not use this file except in compliance with the License.
6 // You may obtain a copy of the License at
7 //
8 //      http://www.apache.org/licenses/LICENSE-2.0
9 //
10 // Unless required by applicable law or agreed to in writing, software
11 // distributed under the License is distributed on an "AS IS" BASIS,
12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 // See the License for the specific language governing permissions and
14 // limitations under the License.
15 //
16 
17 #include <sys/types.h>
18 #include <unistd.h>
19 
20 #include <limits>
21 #include <optional>
22 #include <set>
23 #include <unordered_map>
24 #include <unordered_set>
25 #include <vector>
26 
27 #include <android-base/file.h>
28 #include <android-base/logging.h>
29 #include <libsnapshot/cow_reader.h>
30 #include <zlib.h>
31 
32 #include "cow_decompress.h"
33 
34 namespace android {
35 namespace snapshot {
36 
CowReader(ReaderFlags reader_flag,bool is_merge)37 CowReader::CowReader(ReaderFlags reader_flag, bool is_merge)
38     : fd_(-1),
39       header_(),
40       fd_size_(0),
41       block_pos_index_(std::make_shared<std::vector<int>>()),
42       reader_flag_(reader_flag),
43       is_merge_(is_merge) {}
44 
SHA256(const void *,size_t,uint8_t[])45 static void SHA256(const void*, size_t, uint8_t[]) {
46 #if 0
47     SHA256_CTX c;
48     SHA256_Init(&c);
49     SHA256_Update(&c, data, length);
50     SHA256_Final(out, &c);
51 #endif
52 }
53 
CloneCowReader()54 std::unique_ptr<CowReader> CowReader::CloneCowReader() {
55     auto cow = std::make_unique<CowReader>();
56     cow->owned_fd_.reset();
57     cow->header_ = header_;
58     cow->footer_ = footer_;
59     cow->fd_size_ = fd_size_;
60     cow->last_label_ = last_label_;
61     cow->ops_ = ops_;
62     cow->merge_op_start_ = merge_op_start_;
63     cow->num_total_data_ops_ = num_total_data_ops_;
64     cow->num_ordered_ops_to_merge_ = num_ordered_ops_to_merge_;
65     cow->has_seq_ops_ = has_seq_ops_;
66     cow->data_loc_ = data_loc_;
67     cow->block_pos_index_ = block_pos_index_;
68     cow->is_merge_ = is_merge_;
69     return cow;
70 }
71 
InitForMerge(android::base::unique_fd && fd)72 bool CowReader::InitForMerge(android::base::unique_fd&& fd) {
73     owned_fd_ = std::move(fd);
74     fd_ = owned_fd_.get();
75 
76     auto pos = lseek(fd_.get(), 0, SEEK_END);
77     if (pos < 0) {
78         PLOG(ERROR) << "lseek end failed";
79         return false;
80     }
81     fd_size_ = pos;
82 
83     if (lseek(fd_.get(), 0, SEEK_SET) < 0) {
84         PLOG(ERROR) << "lseek header failed";
85         return false;
86     }
87     if (!android::base::ReadFully(fd_, &header_, sizeof(header_))) {
88         PLOG(ERROR) << "read header failed";
89         return false;
90     }
91 
92     return true;
93 }
94 
Parse(android::base::unique_fd && fd,std::optional<uint64_t> label)95 bool CowReader::Parse(android::base::unique_fd&& fd, std::optional<uint64_t> label) {
96     owned_fd_ = std::move(fd);
97     return Parse(android::base::borrowed_fd{owned_fd_}, label);
98 }
99 
Parse(android::base::borrowed_fd fd,std::optional<uint64_t> label)100 bool CowReader::Parse(android::base::borrowed_fd fd, std::optional<uint64_t> label) {
101     fd_ = fd;
102 
103     auto pos = lseek(fd_.get(), 0, SEEK_END);
104     if (pos < 0) {
105         PLOG(ERROR) << "lseek end failed";
106         return false;
107     }
108     fd_size_ = pos;
109 
110     if (lseek(fd_.get(), 0, SEEK_SET) < 0) {
111         PLOG(ERROR) << "lseek header failed";
112         return false;
113     }
114     if (!android::base::ReadFully(fd_, &header_, sizeof(header_))) {
115         PLOG(ERROR) << "read header failed";
116         return false;
117     }
118 
119     if (header_.magic != kCowMagicNumber) {
120         LOG(ERROR) << "Header Magic corrupted. Magic: " << header_.magic
121                    << "Expected: " << kCowMagicNumber;
122         return false;
123     }
124     if (header_.footer_size != sizeof(CowFooter)) {
125         LOG(ERROR) << "Footer size unknown, read " << header_.footer_size << ", expected "
126                    << sizeof(CowFooter);
127         return false;
128     }
129     if (header_.op_size != sizeof(CowOperation)) {
130         LOG(ERROR) << "Operation size unknown, read " << header_.op_size << ", expected "
131                    << sizeof(CowOperation);
132         return false;
133     }
134     if (header_.cluster_ops == 1) {
135         LOG(ERROR) << "Clusters must contain at least two operations to function.";
136         return false;
137     }
138     if (header_.op_size != sizeof(CowOperation)) {
139         LOG(ERROR) << "Operation size unknown, read " << header_.op_size << ", expected "
140                    << sizeof(CowOperation);
141         return false;
142     }
143     if (header_.cluster_ops == 1) {
144         LOG(ERROR) << "Clusters must contain at least two operations to function.";
145         return false;
146     }
147 
148     if ((header_.major_version > kCowVersionMajor) || (header_.minor_version != kCowVersionMinor)) {
149         LOG(ERROR) << "Header version mismatch";
150         LOG(ERROR) << "Major version: " << header_.major_version
151                    << "Expected: " << kCowVersionMajor;
152         LOG(ERROR) << "Minor version: " << header_.minor_version
153                    << "Expected: " << kCowVersionMinor;
154         return false;
155     }
156 
157     if (!ParseOps(label)) {
158         return false;
159     }
160     // If we're resuming a write, we're not ready to merge
161     if (label.has_value()) return true;
162     return PrepMergeOps();
163 }
164 
ParseOps(std::optional<uint64_t> label)165 bool CowReader::ParseOps(std::optional<uint64_t> label) {
166     uint64_t pos;
167     auto data_loc = std::make_shared<std::unordered_map<uint64_t, uint64_t>>();
168 
169     // Skip the scratch space
170     if (header_.major_version >= 2 && (header_.buffer_size > 0)) {
171         LOG(DEBUG) << " Scratch space found of size: " << header_.buffer_size;
172         size_t init_offset = header_.header_size + header_.buffer_size;
173         pos = lseek(fd_.get(), init_offset, SEEK_SET);
174         if (pos != init_offset) {
175             PLOG(ERROR) << "lseek ops failed";
176             return false;
177         }
178     } else {
179         pos = lseek(fd_.get(), header_.header_size, SEEK_SET);
180         if (pos != header_.header_size) {
181             PLOG(ERROR) << "lseek ops failed";
182             return false;
183         }
184         // Reading a v1 version of COW which doesn't have buffer_size.
185         header_.buffer_size = 0;
186     }
187     uint64_t data_pos = 0;
188 
189     if (header_.cluster_ops) {
190         data_pos = pos + header_.cluster_ops * sizeof(CowOperation);
191     } else {
192         data_pos = pos + sizeof(CowOperation);
193     }
194 
195     auto ops_buffer = std::make_shared<std::vector<CowOperation>>();
196     uint64_t current_op_num = 0;
197     uint64_t cluster_ops = header_.cluster_ops ?: 1;
198     bool done = false;
199 
200     // Alternating op clusters and data
201     while (!done) {
202         uint64_t to_add = std::min(cluster_ops, (fd_size_ - pos) / sizeof(CowOperation));
203         if (to_add == 0) break;
204         ops_buffer->resize(current_op_num + to_add);
205         if (!android::base::ReadFully(fd_, &ops_buffer->data()[current_op_num],
206                                       to_add * sizeof(CowOperation))) {
207             PLOG(ERROR) << "read op failed";
208             return false;
209         }
210         // Parse current cluster to find start of next cluster
211         while (current_op_num < ops_buffer->size()) {
212             auto& current_op = ops_buffer->data()[current_op_num];
213             current_op_num++;
214             if (current_op.type == kCowXorOp) {
215                 data_loc->insert({current_op.new_block, data_pos});
216             }
217             pos += sizeof(CowOperation) + GetNextOpOffset(current_op, header_.cluster_ops);
218             data_pos += current_op.data_length + GetNextDataOffset(current_op, header_.cluster_ops);
219 
220             if (current_op.type == kCowClusterOp) {
221                 break;
222             } else if (current_op.type == kCowLabelOp) {
223                 last_label_ = {current_op.source};
224 
225                 // If we reach the requested label, stop reading.
226                 if (label && label.value() == current_op.source) {
227                     done = true;
228                     break;
229                 }
230             } else if (current_op.type == kCowFooterOp) {
231                 footer_.emplace();
232                 CowFooter* footer = &footer_.value();
233                 memcpy(&footer_->op, &current_op, sizeof(footer->op));
234                 off_t offs = lseek(fd_.get(), pos, SEEK_SET);
235                 if (offs < 0 || pos != static_cast<uint64_t>(offs)) {
236                     PLOG(ERROR) << "lseek next op failed " << offs;
237                     return false;
238                 }
239                 if (!android::base::ReadFully(fd_, &footer->data, sizeof(footer->data))) {
240                     LOG(ERROR) << "Could not read COW footer";
241                     return false;
242                 }
243 
244                 // Drop the footer from the op stream.
245                 current_op_num--;
246                 done = true;
247                 break;
248             } else if (current_op.type == kCowSequenceOp) {
249                 has_seq_ops_ = true;
250             }
251         }
252 
253         // Position for next cluster read
254         off_t offs = lseek(fd_.get(), pos, SEEK_SET);
255         if (offs < 0 || pos != static_cast<uint64_t>(offs)) {
256             PLOG(ERROR) << "lseek next op failed " << offs;
257             return false;
258         }
259         ops_buffer->resize(current_op_num);
260     }
261 
262     LOG(DEBUG) << "COW file read complete. Total ops: " << ops_buffer->size();
263     // To successfully parse a COW file, we need either:
264     //  (1) a label to read up to, and for that label to be found, or
265     //  (2) a valid footer.
266     if (label) {
267         if (!last_label_) {
268             LOG(ERROR) << "Did not find label " << label.value()
269                        << " while reading COW (no labels found)";
270             return false;
271         }
272         if (last_label_.value() != label.value()) {
273             LOG(ERROR) << "Did not find label " << label.value()
274                        << ", last label=" << last_label_.value();
275             return false;
276         }
277     } else if (!footer_) {
278         LOG(ERROR) << "No COW footer found";
279         return false;
280     }
281 
282     uint8_t csum[32];
283     memset(csum, 0, sizeof(uint8_t) * 32);
284 
285     if (footer_) {
286         if (ops_buffer->size() != footer_->op.num_ops) {
287             LOG(ERROR) << "num ops does not match, expected " << footer_->op.num_ops << ", found "
288                        << ops_buffer->size();
289             return false;
290         }
291         if (ops_buffer->size() * sizeof(CowOperation) != footer_->op.ops_size) {
292             LOG(ERROR) << "ops size does not match ";
293             return false;
294         }
295         SHA256(&footer_->op, sizeof(footer_->op), footer_->data.footer_checksum);
296         if (memcmp(csum, footer_->data.ops_checksum, sizeof(csum)) != 0) {
297             LOG(ERROR) << "ops checksum does not match";
298             return false;
299         }
300         SHA256(ops_buffer->data(), footer_->op.ops_size, csum);
301         if (memcmp(csum, footer_->data.ops_checksum, sizeof(csum)) != 0) {
302             LOG(ERROR) << "ops checksum does not match";
303             return false;
304         }
305     }
306 
307     ops_ = ops_buffer;
308     ops_->shrink_to_fit();
309     data_loc_ = data_loc;
310 
311     return true;
312 }
313 
314 //
315 // This sets up the data needed for MergeOpIter. MergeOpIter presents
316 // data in the order we intend to merge in.
317 //
318 // We merge all order sensitive ops up front, and sort the rest to allow for
319 // batch merging. Order sensitive ops can either be presented in their proper
320 // order in the cow, or be ordered by sequence ops (kCowSequenceOp), in which
321 // case we want to merge those ops first, followed by any ops not specified by
322 // new_block value by the sequence op, in sorted order.
323 // We will re-arrange the vector in such a way that
324 // kernel can batch merge. Ex:
325 //
326 // Existing COW format; All the copy operations
327 // are at the beginning.
328 // =======================================
329 // Copy-op-1    - cow_op->new_block = 1
330 // Copy-op-2    - cow_op->new_block = 2
331 // Copy-op-3    - cow_op->new_block = 3
332 // Replace-op-4 - cow_op->new_block = 6
333 // Replace-op-5 - cow_op->new_block = 4
334 // Replace-op-6 - cow_op->new_block = 8
335 // Replace-op-7 - cow_op->new_block = 9
336 // Zero-op-8    - cow_op->new_block = 7
337 // Zero-op-9    - cow_op->new_block = 5
338 // =======================================
339 //
340 // First find the operation which isn't a copy-op
341 // and then sort all the operations in descending order
342 // with the key being cow_op->new_block (source block)
343 //
344 // The data-structure will look like:
345 //
346 // =======================================
347 // Copy-op-1    - cow_op->new_block = 1
348 // Copy-op-2    - cow_op->new_block = 2
349 // Copy-op-3    - cow_op->new_block = 3
350 // Replace-op-7 - cow_op->new_block = 9
351 // Replace-op-6 - cow_op->new_block = 8
352 // Zero-op-8    - cow_op->new_block = 7
353 // Replace-op-4 - cow_op->new_block = 6
354 // Zero-op-9    - cow_op->new_block = 5
355 // Replace-op-5 - cow_op->new_block = 4
356 // =======================================
357 //
358 // Daemon will read the above data-structure in reverse-order
359 // when reading metadata. Thus, kernel will get the metadata
360 // in the following order:
361 //
362 // ========================================
363 // Replace-op-5 - cow_op->new_block = 4
364 // Zero-op-9    - cow_op->new_block = 5
365 // Replace-op-4 - cow_op->new_block = 6
366 // Zero-op-8    - cow_op->new_block = 7
367 // Replace-op-6 - cow_op->new_block = 8
368 // Replace-op-7 - cow_op->new_block = 9
369 // Copy-op-3    - cow_op->new_block = 3
370 // Copy-op-2    - cow_op->new_block = 2
371 // Copy-op-1    - cow_op->new_block = 1
372 // ===========================================
373 //
374 // When merging begins, kernel will start from the last
375 // metadata which was read: In the above format, Copy-op-1
376 // will be the first merge operation.
377 //
378 // Now, batching of the merge operations happens only when
379 // 1: origin block numbers in the base device are contiguous
380 // (cow_op->new_block) and,
381 // 2: cow block numbers which are assigned by daemon in ReadMetadata()
382 // are contiguous. These are monotonically increasing numbers.
383 //
384 // When both (1) and (2) are true, kernel will batch merge the operations.
385 // In the above case, we have to ensure that the copy operations
386 // are merged first before replace operations are done. Hence,
387 // we will not change the order of copy operations. Since,
388 // cow_op->new_block numbers are contiguous, we will ensure that the
389 // cow block numbers assigned in ReadMetadata() for these respective copy
390 // operations are not contiguous forcing kernel to issue merge for each
391 // copy operations without batch merging.
392 //
393 // For all the other operations viz. Replace and Zero op, the cow block
394 // numbers assigned by daemon will be contiguous allowing kernel to batch
395 // merge.
396 //
397 // The final format after assiging COW block numbers by the daemon will
398 // look something like:
399 //
400 // =========================================================
401 // Replace-op-5 - cow_op->new_block = 4  cow-block-num = 2
402 // Zero-op-9    - cow_op->new_block = 5  cow-block-num = 3
403 // Replace-op-4 - cow_op->new_block = 6  cow-block-num = 4
404 // Zero-op-8    - cow_op->new_block = 7  cow-block-num = 5
405 // Replace-op-6 - cow_op->new_block = 8  cow-block-num = 6
406 // Replace-op-7 - cow_op->new_block = 9  cow-block-num = 7
407 // Copy-op-3    - cow_op->new_block = 3  cow-block-num = 9
408 // Copy-op-2    - cow_op->new_block = 2  cow-block-num = 11
409 // Copy-op-1    - cow_op->new_block = 1  cow-block-num = 13
410 // ==========================================================
411 //
412 // Merge sequence will look like:
413 //
414 // Merge-1 - Batch-merge { Copy-op-1, Copy-op-2, Copy-op-3 }
415 // Merge-2 - Batch-merge {Replace-op-7, Replace-op-6, Zero-op-8,
416 //                        Replace-op-4, Zero-op-9, Replace-op-5 }
417 //==============================================================
PrepMergeOps()418 bool CowReader::PrepMergeOps() {
419     auto merge_op_blocks = std::make_unique<std::vector<uint32_t>>();
420     std::vector<int> other_ops;
421     auto seq_ops_set = std::unordered_set<uint32_t>();
422     auto block_map = std::make_unique<std::unordered_map<uint32_t, int>>();
423     size_t num_seqs = 0;
424     size_t read;
425 
426     for (size_t i = 0; i < ops_->size(); i++) {
427         auto& current_op = ops_->data()[i];
428 
429         if (current_op.type == kCowSequenceOp) {
430             size_t seq_len = current_op.data_length / sizeof(uint32_t);
431 
432             merge_op_blocks->resize(merge_op_blocks->size() + seq_len);
433             if (!GetRawBytes(current_op.source, &merge_op_blocks->data()[num_seqs],
434                              current_op.data_length, &read)) {
435                 PLOG(ERROR) << "Failed to read sequence op!";
436                 return false;
437             }
438             for (size_t j = num_seqs; j < num_seqs + seq_len; j++) {
439                 seq_ops_set.insert(merge_op_blocks->data()[j]);
440             }
441             num_seqs += seq_len;
442         }
443 
444         if (IsMetadataOp(current_op)) {
445             continue;
446         }
447 
448         if (!has_seq_ops_ && IsOrderedOp(current_op)) {
449             merge_op_blocks->emplace_back(current_op.new_block);
450         } else if (seq_ops_set.count(current_op.new_block) == 0) {
451             other_ops.push_back(current_op.new_block);
452         }
453         block_map->insert({current_op.new_block, i});
454     }
455     for (auto block : *merge_op_blocks) {
456         if (block_map->count(block) == 0) {
457             LOG(ERROR) << "Invalid Sequence Ops. Could not find Cow Op for new block " << block;
458             return false;
459         }
460     }
461 
462     if (merge_op_blocks->size() > header_.num_merge_ops) {
463         num_ordered_ops_to_merge_ = merge_op_blocks->size() - header_.num_merge_ops;
464     } else {
465         num_ordered_ops_to_merge_ = 0;
466     }
467 
468     // Sort the vector in increasing order if merging in user-space as
469     // we can batch merge them when iterating from forward.
470     //
471     // dm-snapshot-merge requires decreasing order as we iterate the blocks
472     // in reverse order.
473     if (reader_flag_ == ReaderFlags::USERSPACE_MERGE) {
474         std::sort(other_ops.begin(), other_ops.end());
475     } else {
476         std::sort(other_ops.begin(), other_ops.end(), std::greater<int>());
477     }
478 
479     merge_op_blocks->insert(merge_op_blocks->end(), other_ops.begin(), other_ops.end());
480 
481     num_total_data_ops_ = merge_op_blocks->size();
482     if (header_.num_merge_ops > 0) {
483         merge_op_start_ = header_.num_merge_ops;
484     }
485 
486     if (is_merge_) {
487         // Metadata ops are not required for merge. Thus, just re-arrange
488         // the ops vector as required for merge operations.
489         auto merge_ops_buffer = std::make_shared<std::vector<CowOperation>>();
490         merge_ops_buffer->reserve(num_total_data_ops_);
491         for (auto block : *merge_op_blocks) {
492             merge_ops_buffer->emplace_back(ops_->data()[block_map->at(block)]);
493         }
494         ops_->clear();
495         ops_ = merge_ops_buffer;
496         ops_->shrink_to_fit();
497     } else {
498         for (auto block : *merge_op_blocks) {
499             block_pos_index_->push_back(block_map->at(block));
500         }
501     }
502 
503     block_map->clear();
504     merge_op_blocks->clear();
505 
506     return true;
507 }
508 
VerifyMergeOps()509 bool CowReader::VerifyMergeOps() {
510     auto itr = GetMergeOpIter(true);
511     std::unordered_map<uint64_t, CowOperation> overwritten_blocks;
512     while (!itr->Done()) {
513         CowOperation op = itr->Get();
514         uint64_t block;
515         bool offset;
516         if (op.type == kCowCopyOp) {
517             block = op.source;
518             offset = false;
519         } else if (op.type == kCowXorOp) {
520             block = op.source / BLOCK_SZ;
521             offset = (op.source % BLOCK_SZ) != 0;
522         } else {
523             itr->Next();
524             continue;
525         }
526 
527         CowOperation* overwrite = nullptr;
528         if (overwritten_blocks.count(block)) {
529             overwrite = &overwritten_blocks[block];
530             LOG(ERROR) << "Invalid Sequence! Block needed for op:\n"
531                        << op << "\noverwritten by previously merged op:\n"
532                        << *overwrite;
533         }
534         if (offset && overwritten_blocks.count(block + 1)) {
535             overwrite = &overwritten_blocks[block + 1];
536             LOG(ERROR) << "Invalid Sequence! Block needed for op:\n"
537                        << op << "\noverwritten by previously merged op:\n"
538                        << *overwrite;
539         }
540         if (overwrite != nullptr) return false;
541         overwritten_blocks[op.new_block] = op;
542         itr->Next();
543     }
544     return true;
545 }
546 
GetHeader(CowHeader * header)547 bool CowReader::GetHeader(CowHeader* header) {
548     *header = header_;
549     return true;
550 }
551 
GetFooter(CowFooter * footer)552 bool CowReader::GetFooter(CowFooter* footer) {
553     if (!footer_) return false;
554     *footer = footer_.value();
555     return true;
556 }
557 
GetLastLabel(uint64_t * label)558 bool CowReader::GetLastLabel(uint64_t* label) {
559     if (!last_label_) return false;
560     *label = last_label_.value();
561     return true;
562 }
563 
564 class CowOpIter final : public ICowOpIter {
565   public:
566     CowOpIter(std::shared_ptr<std::vector<CowOperation>>& ops, uint64_t start);
567 
568     bool Done() override;
569     const CowOperation& Get() override;
570     void Next() override;
571 
572     void Prev() override;
573     bool RDone() override;
574 
575   private:
576     std::shared_ptr<std::vector<CowOperation>> ops_;
577     std::vector<CowOperation>::iterator op_iter_;
578 };
579 
CowOpIter(std::shared_ptr<std::vector<CowOperation>> & ops,uint64_t start)580 CowOpIter::CowOpIter(std::shared_ptr<std::vector<CowOperation>>& ops, uint64_t start) {
581     ops_ = ops;
582     op_iter_ = ops_->begin() + start;
583 }
584 
RDone()585 bool CowOpIter::RDone() {
586     return op_iter_ == ops_->begin();
587 }
588 
Prev()589 void CowOpIter::Prev() {
590     CHECK(!RDone());
591     op_iter_--;
592 }
593 
Done()594 bool CowOpIter::Done() {
595     return op_iter_ == ops_->end();
596 }
597 
Next()598 void CowOpIter::Next() {
599     CHECK(!Done());
600     op_iter_++;
601 }
602 
Get()603 const CowOperation& CowOpIter::Get() {
604     CHECK(!Done());
605     return (*op_iter_);
606 }
607 
608 class CowRevMergeOpIter final : public ICowOpIter {
609   public:
610     explicit CowRevMergeOpIter(std::shared_ptr<std::vector<CowOperation>> ops,
611                                std::shared_ptr<std::vector<int>> block_pos_index, uint64_t start);
612 
613     bool Done() override;
614     const CowOperation& Get() override;
615     void Next() override;
616 
617     void Prev() override;
618     bool RDone() override;
619 
620   private:
621     std::shared_ptr<std::vector<CowOperation>> ops_;
622     std::vector<int>::reverse_iterator block_riter_;
623     std::shared_ptr<std::vector<int>> cow_op_index_vec_;
624     uint64_t start_;
625 };
626 
627 class CowMergeOpIter final : public ICowOpIter {
628   public:
629     explicit CowMergeOpIter(std::shared_ptr<std::vector<CowOperation>> ops,
630                             std::shared_ptr<std::vector<int>> block_pos_index, uint64_t start);
631 
632     bool Done() override;
633     const CowOperation& Get() override;
634     void Next() override;
635 
636     void Prev() override;
637     bool RDone() override;
638 
639   private:
640     std::shared_ptr<std::vector<CowOperation>> ops_;
641     std::vector<int>::iterator block_iter_;
642     std::shared_ptr<std::vector<int>> cow_op_index_vec_;
643     uint64_t start_;
644 };
645 
CowMergeOpIter(std::shared_ptr<std::vector<CowOperation>> ops,std::shared_ptr<std::vector<int>> block_pos_index,uint64_t start)646 CowMergeOpIter::CowMergeOpIter(std::shared_ptr<std::vector<CowOperation>> ops,
647                                std::shared_ptr<std::vector<int>> block_pos_index, uint64_t start) {
648     ops_ = ops;
649     start_ = start;
650     cow_op_index_vec_ = block_pos_index;
651     block_iter_ = cow_op_index_vec_->begin() + start;
652 }
653 
RDone()654 bool CowMergeOpIter::RDone() {
655     return block_iter_ == cow_op_index_vec_->begin();
656 }
657 
Prev()658 void CowMergeOpIter::Prev() {
659     CHECK(!RDone());
660     block_iter_--;
661 }
662 
Done()663 bool CowMergeOpIter::Done() {
664     return block_iter_ == cow_op_index_vec_->end();
665 }
666 
Next()667 void CowMergeOpIter::Next() {
668     CHECK(!Done());
669     block_iter_++;
670 }
671 
Get()672 const CowOperation& CowMergeOpIter::Get() {
673     CHECK(!Done());
674     return ops_->data()[*block_iter_];
675 }
676 
CowRevMergeOpIter(std::shared_ptr<std::vector<CowOperation>> ops,std::shared_ptr<std::vector<int>> block_pos_index,uint64_t start)677 CowRevMergeOpIter::CowRevMergeOpIter(std::shared_ptr<std::vector<CowOperation>> ops,
678                                      std::shared_ptr<std::vector<int>> block_pos_index,
679                                      uint64_t start) {
680     ops_ = ops;
681     start_ = start;
682     cow_op_index_vec_ = block_pos_index;
683     block_riter_ = cow_op_index_vec_->rbegin();
684 }
685 
RDone()686 bool CowRevMergeOpIter::RDone() {
687     return block_riter_ == cow_op_index_vec_->rbegin();
688 }
689 
Prev()690 void CowRevMergeOpIter::Prev() {
691     CHECK(!RDone());
692     block_riter_--;
693 }
694 
Done()695 bool CowRevMergeOpIter::Done() {
696     return block_riter_ == cow_op_index_vec_->rend() - start_;
697 }
698 
Next()699 void CowRevMergeOpIter::Next() {
700     CHECK(!Done());
701     block_riter_++;
702 }
703 
Get()704 const CowOperation& CowRevMergeOpIter::Get() {
705     CHECK(!Done());
706     return ops_->data()[*block_riter_];
707 }
708 
GetOpIter(bool merge_progress)709 std::unique_ptr<ICowOpIter> CowReader::GetOpIter(bool merge_progress) {
710     return std::make_unique<CowOpIter>(ops_, merge_progress ? merge_op_start_ : 0);
711 }
712 
GetRevMergeOpIter(bool ignore_progress)713 std::unique_ptr<ICowOpIter> CowReader::GetRevMergeOpIter(bool ignore_progress) {
714     return std::make_unique<CowRevMergeOpIter>(ops_, block_pos_index_,
715                                                ignore_progress ? 0 : merge_op_start_);
716 }
717 
GetMergeOpIter(bool ignore_progress)718 std::unique_ptr<ICowOpIter> CowReader::GetMergeOpIter(bool ignore_progress) {
719     return std::make_unique<CowMergeOpIter>(ops_, block_pos_index_,
720                                             ignore_progress ? 0 : merge_op_start_);
721 }
722 
GetRawBytes(uint64_t offset,void * buffer,size_t len,size_t * read)723 bool CowReader::GetRawBytes(uint64_t offset, void* buffer, size_t len, size_t* read) {
724     // Validate the offset, taking care to acknowledge possible overflow of offset+len.
725     if (offset < header_.header_size || offset >= fd_size_ - sizeof(CowFooter) || len >= fd_size_ ||
726         offset + len > fd_size_ - sizeof(CowFooter)) {
727         LOG(ERROR) << "invalid data offset: " << offset << ", " << len << " bytes";
728         return false;
729     }
730     if (lseek(fd_.get(), offset, SEEK_SET) < 0) {
731         PLOG(ERROR) << "lseek to read raw bytes failed";
732         return false;
733     }
734     ssize_t rv = TEMP_FAILURE_RETRY(::read(fd_.get(), buffer, len));
735     if (rv < 0) {
736         PLOG(ERROR) << "read failed";
737         return false;
738     }
739     *read = rv;
740     return true;
741 }
742 
743 class CowDataStream final : public IByteStream {
744   public:
CowDataStream(CowReader * reader,uint64_t offset,size_t data_length)745     CowDataStream(CowReader* reader, uint64_t offset, size_t data_length)
746         : reader_(reader), offset_(offset), data_length_(data_length) {
747         remaining_ = data_length_;
748     }
749 
Read(void * buffer,size_t length,size_t * read)750     bool Read(void* buffer, size_t length, size_t* read) override {
751         size_t to_read = std::min(length, remaining_);
752         if (!to_read) {
753             *read = 0;
754             return true;
755         }
756         if (!reader_->GetRawBytes(offset_, buffer, to_read, read)) {
757             return false;
758         }
759         offset_ += *read;
760         remaining_ -= *read;
761         return true;
762     }
763 
Size() const764     size_t Size() const override { return data_length_; }
765 
766   private:
767     CowReader* reader_;
768     uint64_t offset_;
769     size_t data_length_;
770     size_t remaining_;
771 };
772 
ReadData(const CowOperation & op,IByteSink * sink)773 bool CowReader::ReadData(const CowOperation& op, IByteSink* sink) {
774     std::unique_ptr<IDecompressor> decompressor;
775     switch (op.compression) {
776         case kCowCompressNone:
777             decompressor = IDecompressor::Uncompressed();
778             break;
779         case kCowCompressGz:
780             decompressor = IDecompressor::Gz();
781             break;
782         case kCowCompressBrotli:
783             decompressor = IDecompressor::Brotli();
784             break;
785         case kCowCompressLz4:
786             decompressor = IDecompressor::Lz4();
787             break;
788         default:
789             LOG(ERROR) << "Unknown compression type: " << op.compression;
790             return false;
791     }
792 
793     uint64_t offset;
794     if (op.type == kCowXorOp) {
795         offset = data_loc_->at(op.new_block);
796     } else {
797         offset = op.source;
798     }
799     CowDataStream stream(this, offset, op.data_length);
800     decompressor->set_stream(&stream);
801     decompressor->set_sink(sink);
802     return decompressor->Decompress(header_.block_size);
803 }
804 
805 }  // namespace snapshot
806 }  // namespace android
807