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 "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   return;
77 }
78 
79 template <typename T>
IOOperation(bool (FileInterface::* io_op)(T *,size_t,size_t *),T * buf,size_t count,size_t * bytes_processed)80 bool ExtentsFile::IOOperation(bool (FileInterface::*io_op)(T*, size_t, size_t*),
81                               T* buf,
82                               size_t count,
83                               size_t* bytes_processed) {
84   bool result = true;
85   size_t processed = 0;
86   AdvancePos(0);
87   while (count > 0 && curr_ex_idx_ < extents_.size()) {
88     const ex_t& ex = extents_[curr_ex_idx_];
89     off_t curr_ex_off = curr_pos_ - acc_len_[curr_ex_idx_];
90     size_t chunk_size =
91         std::min(static_cast<uint64_t>(count), ex.len - curr_ex_off);
92     size_t chunk_processed = 0;
93     if (ex.off < 0) {
94       chunk_processed = chunk_size;
95     } else {
96       if (!file_->Seek(ex.off + curr_ex_off) ||
97           !(file_.get()->*io_op)(buf, chunk_size, &chunk_processed)) {
98         processed += chunk_processed;
99         result = processed > 0;
100         break;
101       }
102     }
103     processed += chunk_processed;
104     count -= chunk_processed;
105     // T can be either const void* or void*. We const_cast it back to void* and
106     // then char* to do the arithmetic operation, but |buf| will continue to be
107     // const void* if it was defined that way.
108     buf = static_cast<char*>(const_cast<void*>(buf)) + chunk_processed;
109     AdvancePos(chunk_processed);
110     if (!chunk_processed)
111       break;
112   }
113   *bytes_processed = processed;
114   return result;
115 }
116 
117 }  // namespace bsdiff
118