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 "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   return;
     77 }
     78 
     79 template <typename T>
     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