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, ¤t_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