1 // Copyright 2015 The Chromium OS Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "bsdiff/extents_file.h"
6
7 #include <string.h>
8
9 #include <algorithm>
10
11 // Extent files implementation extending FileInterface.
12 //
13 // This class allows to map linear positions in a file to a list of regions in
14 // another file. All the reads and writes are unbuffered, passed directly to the
15 // underlying file. Seeking is done in O(log(N)), where N is the number of
16 // extents in the file, but sequential reads jump to the next extent in O(1).
17
18 namespace bsdiff {
19
ExtentsFile(std::unique_ptr<FileInterface> file,const std::vector<ex_t> & extents)20 ExtentsFile::ExtentsFile(std::unique_ptr<FileInterface> file,
21 const std::vector<ex_t>& extents)
22 : file_(std::move(file)), extents_(extents) {
23 acc_len_.reserve(extents.size());
24 for (const ex_t& extent : extents) {
25 acc_len_.push_back(total_ex_len_);
26 total_ex_len_ += extent.len;
27 }
28 }
29
~ExtentsFile()30 ExtentsFile::~ExtentsFile() {
31 Close();
32 }
33
Read(void * buf,size_t count,size_t * bytes_read)34 bool ExtentsFile::Read(void* buf, size_t count, size_t* bytes_read) {
35 return IOOperation(&FileInterface::Read, buf, count, bytes_read);
36 }
37
38
Write(const void * buf,size_t count,size_t * bytes_written)39 bool ExtentsFile::Write(const void* buf, size_t count, size_t* bytes_written) {
40 return IOOperation(&FileInterface::Write, buf, count, bytes_written);
41 }
42
Seek(off_t pos)43 bool ExtentsFile::Seek(off_t pos) {
44 if (pos < 0 || static_cast<uint64_t>(pos) > total_ex_len_)
45 return false;
46 if (acc_len_.empty())
47 return true;
48 // Note that the first element of acc_len_ is always 0, and pos is at least 0,
49 // so the upper_bound will never return acc_len_.begin().
50 curr_pos_ = pos;
51 curr_ex_idx_ = std::upper_bound(acc_len_.begin(), acc_len_.end(), pos) -
52 acc_len_.begin();
53 // We handle the corner case where |pos| is the size of all the extents by
54 // leaving the value of curr_ex_idx_ the same way AdvancePos(0) would leave it
55 // after the seek.
56 if (curr_pos_ < total_ex_len_)
57 curr_ex_idx_--;
58 return true;
59 }
60
Close()61 bool ExtentsFile::Close() {
62 return file_->Close();
63 }
64
GetSize(uint64_t * size)65 bool ExtentsFile::GetSize(uint64_t* size) {
66 *size = total_ex_len_;
67 return true;
68 }
69
AdvancePos(uint64_t size)70 void ExtentsFile::AdvancePos(uint64_t size) {
71 curr_pos_ += size;
72 for (; curr_ex_idx_ < extents_.size(); curr_ex_idx_++) {
73 if (curr_pos_ < acc_len_[curr_ex_idx_] + extents_[curr_ex_idx_].len)
74 return;
75 }
76 }
77
78 template <typename T>
IOOperation(bool (FileInterface::* io_op)(T *,size_t,size_t *),T * buf,size_t count,size_t * bytes_processed)79 bool ExtentsFile::IOOperation(bool (FileInterface::*io_op)(T*, size_t, size_t*),
80 T* buf,
81 size_t count,
82 size_t* bytes_processed) {
83 bool result = true;
84 size_t processed = 0;
85 AdvancePos(0);
86 while (count > 0 && curr_ex_idx_ < extents_.size()) {
87 const ex_t& ex = extents_[curr_ex_idx_];
88 off_t curr_ex_off = curr_pos_ - acc_len_[curr_ex_idx_];
89 size_t chunk_size =
90 std::min(static_cast<uint64_t>(count), ex.len - curr_ex_off);
91 size_t chunk_processed = 0;
92 if (ex.off < 0) {
93 chunk_processed = chunk_size;
94 } else {
95 if (!file_->Seek(ex.off + curr_ex_off) ||
96 !(file_.get()->*io_op)(buf, chunk_size, &chunk_processed)) {
97 processed += chunk_processed;
98 result = processed > 0;
99 break;
100 }
101 }
102 processed += chunk_processed;
103 count -= chunk_processed;
104 // T can be either const void* or void*. We const_cast it back to void* and
105 // then char* to do the arithmetic operation, but |buf| will continue to be
106 // const void* if it was defined that way.
107 buf = static_cast<char*>(const_cast<void*>(buf)) + chunk_processed;
108 AdvancePos(chunk_processed);
109 if (!chunk_processed)
110 break;
111 }
112 *bytes_processed = processed;
113 return result;
114 }
115
116 } // namespace bsdiff
117