Home | History | Annotate | Download | only in bsdiff 
      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 
     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 
     30 ExtentsFile::~ExtentsFile() {
     31   Close();
     32 }
     33 
     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 
     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 
     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 
     61 bool ExtentsFile::Close() {
     62   return file_->Close();
     63 }
     64 
     65 bool ExtentsFile::GetSize(uint64_t* size) {
     66   *size = total_ex_len_;
     67   return true;
     68 }
     69 
     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>
     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