update_engine: Remove unused IsIdempotentOperation().
All the minor-version=2 are idempotent, so since we switched to minor
version 2, this function becomes trivial now. This patch removes this
function from the code and moves the ExtentRanges class to the
payload_generator/ directory since now it is only used there.
BUG=None
TEST=Unittest still pass.
Change-Id: Ib9dbbdded0ca2ef2128bb6c470de7a00720c4038
Reviewed-on: https://chromium-review.googlesource.com/275806
Reviewed-by: Alex Deymo <[email protected]>
Tested-by: Alex Deymo <[email protected]>
Commit-Queue: Alex Deymo <[email protected]>
diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
index 34b9737..8676086 100644
--- a/payload_generator/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -27,11 +27,11 @@
#include "update_engine/bzip.h"
#include "update_engine/delta_performer.h"
-#include "update_engine/extent_ranges.h"
#include "update_engine/file_writer.h"
#include "update_engine/omaha_hash_calculator.h"
#include "update_engine/payload_constants.h"
#include "update_engine/payload_generator/ext2_filesystem.h"
+#include "update_engine/payload_generator/extent_ranges.h"
#include "update_engine/payload_generator/full_update_generator.h"
#include "update_engine/payload_generator/inplace_generator.h"
#include "update_engine/payload_generator/payload_signer.h"
@@ -161,7 +161,7 @@
manifest_metadata_size));
total_size += manifest_metadata_size;
- std::sort(objects.begin(), objects.end());
+ sort(objects.begin(), objects.end());
static const char kFormatString[] = "%6.2f%% %10jd %-10s %s\n";
for (const DeltaObject& object : objects) {
diff --git a/payload_generator/delta_diff_generator_unittest.cc b/payload_generator/delta_diff_generator_unittest.cc
index c198916..baf308f 100644
--- a/payload_generator/delta_diff_generator_unittest.cc
+++ b/payload_generator/delta_diff_generator_unittest.cc
@@ -27,8 +27,8 @@
#include "update_engine/bzip.h"
#include "update_engine/delta_performer.h"
-#include "update_engine/extent_ranges.h"
#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/extent_ranges.h"
#include "update_engine/payload_generator/extent_utils.h"
#include "update_engine/payload_generator/fake_filesystem.h"
#include "update_engine/payload_generator/graph_types.h"
@@ -36,7 +36,6 @@
#include "update_engine/test_utils.h"
#include "update_engine/utils.h"
-using chromeos_update_engine::test_utils::kRandomString;
using std::set;
using std::string;
using std::unique_ptr;
diff --git a/payload_generator/ext2_filesystem.cc b/payload_generator/ext2_filesystem.cc
index d3e0930..0467b80 100644
--- a/payload_generator/ext2_filesystem.cc
+++ b/payload_generator/ext2_filesystem.cc
@@ -14,7 +14,7 @@
#include <base/logging.h>
#include <base/strings/stringprintf.h>
-#include "update_engine/extent_ranges.h"
+#include "update_engine/payload_generator/extent_ranges.h"
#include "update_engine/payload_generator/extent_utils.h"
#include "update_engine/update_metadata.pb.h"
#include "update_engine/utils.h"
diff --git a/payload_generator/extent_ranges.cc b/payload_generator/extent_ranges.cc
new file mode 100644
index 0000000..d86bcfc
--- /dev/null
+++ b/payload_generator/extent_ranges.cc
@@ -0,0 +1,277 @@
+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "update_engine/payload_generator/extent_ranges.h"
+
+#include <algorithm>
+#include <set>
+#include <utility>
+#include <vector>
+
+#include <base/logging.h>
+
+#include "update_engine/payload_constants.h"
+
+using std::set;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+bool ExtentRanges::ExtentsOverlapOrTouch(const Extent& a, const Extent& b) {
+ if (a.start_block() == b.start_block())
+ return true;
+ if (a.start_block() == kSparseHole || b.start_block() == kSparseHole)
+ return false;
+ if (a.start_block() < b.start_block()) {
+ return a.start_block() + a.num_blocks() >= b.start_block();
+ } else {
+ return b.start_block() + b.num_blocks() >= a.start_block();
+ }
+}
+
+bool ExtentRanges::ExtentsOverlap(const Extent& a, const Extent& b) {
+ if (a.start_block() == b.start_block())
+ return true;
+ if (a.start_block() == kSparseHole || b.start_block() == kSparseHole)
+ return false;
+ if (a.start_block() < b.start_block()) {
+ return a.start_block() + a.num_blocks() > b.start_block();
+ } else {
+ return b.start_block() + b.num_blocks() > a.start_block();
+ }
+}
+
+void ExtentRanges::AddBlock(uint64_t block) {
+ AddExtent(ExtentForRange(block, 1));
+}
+
+void ExtentRanges::SubtractBlock(uint64_t block) {
+ SubtractExtent(ExtentForRange(block, 1));
+}
+
+namespace {
+
+Extent UnionOverlappingExtents(const Extent& first, const Extent& second) {
+ CHECK_NE(kSparseHole, first.start_block());
+ CHECK_NE(kSparseHole, second.start_block());
+ uint64_t start = std::min(first.start_block(), second.start_block());
+ uint64_t end = std::max(first.start_block() + first.num_blocks(),
+ second.start_block() + second.num_blocks());
+ return ExtentForRange(start, end - start);
+}
+
+} // namespace
+
+void ExtentRanges::AddExtent(Extent extent) {
+ if (extent.start_block() == kSparseHole || extent.num_blocks() == 0)
+ return;
+
+ ExtentSet::iterator begin_del = extent_set_.end();
+ ExtentSet::iterator end_del = extent_set_.end();
+ uint64_t del_blocks = 0;
+ for (ExtentSet::iterator it = extent_set_.begin(), e = extent_set_.end();
+ it != e; ++it) {
+ if (ExtentsOverlapOrTouch(*it, extent)) {
+ end_del = it;
+ ++end_del;
+ del_blocks += it->num_blocks();
+ if (begin_del == extent_set_.end())
+ begin_del = it;
+
+ extent = UnionOverlappingExtents(extent, *it);
+ }
+ }
+ extent_set_.erase(begin_del, end_del);
+ extent_set_.insert(extent);
+ blocks_ -= del_blocks;
+ blocks_ += extent.num_blocks();
+}
+
+namespace {
+// Returns base - subtractee (set subtraction).
+ExtentRanges::ExtentSet SubtractOverlappingExtents(const Extent& base,
+ const Extent& subtractee) {
+ ExtentRanges::ExtentSet ret;
+ if (subtractee.start_block() > base.start_block()) {
+ ret.insert(ExtentForRange(base.start_block(),
+ subtractee.start_block() - base.start_block()));
+ }
+ uint64_t base_end = base.start_block() + base.num_blocks();
+ uint64_t subtractee_end = subtractee.start_block() + subtractee.num_blocks();
+ if (base_end > subtractee_end) {
+ ret.insert(ExtentForRange(subtractee_end, base_end - subtractee_end));
+ }
+ return ret;
+}
+} // namespace
+
+void ExtentRanges::SubtractExtent(const Extent& extent) {
+ if (extent.start_block() == kSparseHole || extent.num_blocks() == 0)
+ return;
+
+ ExtentSet::iterator begin_del = extent_set_.end();
+ ExtentSet::iterator end_del = extent_set_.end();
+ uint64_t del_blocks = 0;
+ ExtentSet new_extents;
+ for (ExtentSet::iterator it = extent_set_.begin(), e = extent_set_.end();
+ it != e; ++it) {
+ if (!ExtentsOverlap(*it, extent))
+ continue;
+
+ if (begin_del == extent_set_.end())
+ begin_del = it;
+ end_del = it;
+ ++end_del;
+
+ del_blocks += it->num_blocks();
+
+ ExtentSet subtraction = SubtractOverlappingExtents(*it, extent);
+ for (ExtentSet::iterator jt = subtraction.begin(), je = subtraction.end();
+ jt != je; ++jt) {
+ new_extents.insert(*jt);
+ del_blocks -= jt->num_blocks();
+ }
+ }
+ extent_set_.erase(begin_del, end_del);
+ extent_set_.insert(new_extents.begin(), new_extents.end());
+ blocks_ -= del_blocks;
+}
+
+void ExtentRanges::AddRanges(const ExtentRanges& ranges) {
+ for (ExtentSet::const_iterator it = ranges.extent_set_.begin(),
+ e = ranges.extent_set_.end(); it != e; ++it) {
+ AddExtent(*it);
+ }
+}
+
+void ExtentRanges::SubtractRanges(const ExtentRanges& ranges) {
+ for (ExtentSet::const_iterator it = ranges.extent_set_.begin(),
+ e = ranges.extent_set_.end(); it != e; ++it) {
+ SubtractExtent(*it);
+ }
+}
+
+void ExtentRanges::AddExtents(const vector<Extent>& extents) {
+ for (vector<Extent>::const_iterator it = extents.begin(), e = extents.end();
+ it != e; ++it) {
+ AddExtent(*it);
+ }
+}
+
+void ExtentRanges::SubtractExtents(const vector<Extent>& extents) {
+ for (vector<Extent>::const_iterator it = extents.begin(), e = extents.end();
+ it != e; ++it) {
+ SubtractExtent(*it);
+ }
+}
+
+void ExtentRanges::AddRepeatedExtents(
+ const ::google::protobuf::RepeatedPtrField<Extent> &exts) {
+ for (int i = 0, e = exts.size(); i != e; ++i) {
+ AddExtent(exts.Get(i));
+ }
+}
+
+void ExtentRanges::SubtractRepeatedExtents(
+ const ::google::protobuf::RepeatedPtrField<Extent> &exts) {
+ for (int i = 0, e = exts.size(); i != e; ++i) {
+ SubtractExtent(exts.Get(i));
+ }
+}
+
+void ExtentRanges::Dump() const {
+ LOG(INFO) << "ExtentRanges Dump. blocks: " << blocks_;
+ for (ExtentSet::const_iterator it = extent_set_.begin(),
+ e = extent_set_.end();
+ it != e; ++it) {
+ LOG(INFO) << "{" << it->start_block() << ", " << it->num_blocks() << "}";
+ }
+}
+
+Extent ExtentForRange(uint64_t start_block, uint64_t num_blocks) {
+ Extent ret;
+ ret.set_start_block(start_block);
+ ret.set_num_blocks(num_blocks);
+ return ret;
+}
+
+vector<Extent> ExtentRanges::GetExtentsForBlockCount(
+ uint64_t count) const {
+ vector<Extent> out;
+ if (count == 0)
+ return out;
+ uint64_t out_blocks = 0;
+ CHECK(count <= blocks_);
+ for (ExtentSet::const_iterator it = extent_set_.begin(),
+ e = extent_set_.end();
+ it != e; ++it) {
+ const uint64_t blocks_needed = count - out_blocks;
+ const Extent& extent = *it;
+ out.push_back(extent);
+ out_blocks += extent.num_blocks();
+ if (extent.num_blocks() < blocks_needed)
+ continue;
+ if (extent.num_blocks() == blocks_needed)
+ break;
+ // If we get here, we just added the last extent needed, but it's too big
+ out_blocks -= extent.num_blocks();
+ out_blocks += blocks_needed;
+ out.back().set_num_blocks(blocks_needed);
+ break;
+ }
+ return out;
+}
+
+vector<Extent> FilterExtentRanges(const std::vector<Extent>& extents,
+ const ExtentRanges& ranges) {
+ vector<Extent> result;
+ const ExtentRanges::ExtentSet& extent_set = ranges.extent_set();
+ for (Extent extent : extents) {
+ // The extents are sorted by the start_block. We want to iterate all the
+ // Extents in the ExtentSet possibly overlapping the current |extent|. This
+ // is achieved by looking from the extent whose start_block is *lower* than
+ // the extent.start_block() up to the greatest extent whose start_block is
+ // lower than extent.start_block() + extent.num_blocks().
+ auto lower = extent_set.lower_bound(extent);
+ // We need to decrement the lower_bound to look at the extent that could
+ // overlap the beginning of the current |extent|.
+ if (lower != extent_set.begin())
+ lower--;
+ auto upper = extent_set.lower_bound(
+ ExtentForRange(extent.start_block() + extent.num_blocks(), 0));
+ for (auto iter = lower; iter != upper; ++iter) {
+ if (!ExtentRanges::ExtentsOverlap(extent, *iter))
+ continue;
+ if (iter->start_block() <= extent.start_block()) {
+ // We need to cut blocks from the beginning of the |extent|.
+ uint64_t cut_blocks = iter->start_block() + iter->num_blocks() -
+ extent.start_block();
+ if (cut_blocks >= extent.num_blocks()) {
+ extent.set_num_blocks(0);
+ break;
+ }
+ extent = ExtentForRange(extent.start_block() + cut_blocks,
+ extent.num_blocks() - cut_blocks);
+ } else {
+ // We need to cut blocks on the middle of the extent, possible up to the
+ // end of it.
+ result.push_back(
+ ExtentForRange(extent.start_block(),
+ iter->start_block() - extent.start_block()));
+ uint64_t new_start = iter->start_block() + iter->num_blocks();
+ uint64_t old_end = extent.start_block() + extent.num_blocks();
+ if (new_start >= old_end) {
+ extent.set_num_blocks(0);
+ break;
+ }
+ extent = ExtentForRange(new_start, old_end - new_start);
+ }
+ }
+ if (extent.num_blocks() > 0)
+ result.push_back(extent);
+ }
+ return result;
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/extent_ranges.h b/payload_generator/extent_ranges.h
new file mode 100644
index 0000000..fc15149
--- /dev/null
+++ b/payload_generator/extent_ranges.h
@@ -0,0 +1,79 @@
+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_
+#define UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_
+
+#include <map>
+#include <set>
+#include <vector>
+
+#include <base/macros.h>
+
+#include "update_engine/update_metadata.pb.h"
+
+// An ExtentRanges object represents an unordered collection of extents (and
+// therefore blocks). Such an object may be modified by adding or subtracting
+// blocks (think: set addition or set subtraction). Note that ExtentRanges
+// ignores sparse hole extents mostly to avoid confusion between extending a
+// sparse hole range vs. set addition but also to ensure that the delta
+// generator doesn't use sparse holes as scratch space.
+
+namespace chromeos_update_engine {
+
+struct ExtentLess {
+ bool operator()(const Extent& x, const Extent& y) const {
+ return x.start_block() < y.start_block();
+ }
+};
+
+Extent ExtentForRange(uint64_t start_block, uint64_t num_blocks);
+
+class ExtentRanges {
+ public:
+ typedef std::set<Extent, ExtentLess> ExtentSet;
+
+ ExtentRanges() : blocks_(0) {}
+ void AddBlock(uint64_t block);
+ void SubtractBlock(uint64_t block);
+ void AddExtent(Extent extent);
+ void SubtractExtent(const Extent& extent);
+ void AddExtents(const std::vector<Extent>& extents);
+ void SubtractExtents(const std::vector<Extent>& extents);
+ void AddRepeatedExtents(
+ const ::google::protobuf::RepeatedPtrField<Extent> &exts);
+ void SubtractRepeatedExtents(
+ const ::google::protobuf::RepeatedPtrField<Extent> &exts);
+ void AddRanges(const ExtentRanges& ranges);
+ void SubtractRanges(const ExtentRanges& ranges);
+
+ static bool ExtentsOverlapOrTouch(const Extent& a, const Extent& b);
+ static bool ExtentsOverlap(const Extent& a, const Extent& b);
+
+ // Dumps contents to the log file. Useful for debugging.
+ void Dump() const;
+
+ uint64_t blocks() const { return blocks_; }
+ const ExtentSet& extent_set() const { return extent_set_; }
+
+ // Returns an ordered vector of extents for |count| blocks,
+ // using extents in extent_set_. The returned extents are not
+ // removed from extent_set_. |count| must be less than or equal to
+ // the number of blocks in this extent set.
+ std::vector<Extent> GetExtentsForBlockCount(uint64_t count) const;
+
+ private:
+ ExtentSet extent_set_;
+ uint64_t blocks_;
+};
+
+// Filters out from the passed list of extents |extents| all the blocks in the
+// ExtentRanges set. Note that the order of the blocks in |extents| is preserved
+// omitting blocks present in the ExtentRanges |ranges|.
+std::vector<Extent> FilterExtentRanges(const std::vector<Extent>& extents,
+ const ExtentRanges& ranges);
+
+} // namespace chromeos_update_engine
+
+#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_
diff --git a/payload_generator/extent_ranges_unittest.cc b/payload_generator/extent_ranges_unittest.cc
new file mode 100644
index 0000000..b7036a5
--- /dev/null
+++ b/payload_generator/extent_ranges_unittest.cc
@@ -0,0 +1,314 @@
+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "update_engine/payload_generator/extent_ranges.h"
+
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/extent_utils.h"
+#include "update_engine/test_utils.h"
+
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class ExtentRangesTest : public ::testing::Test {};
+
+namespace {
+void ExpectRangeEq(const ExtentRanges& ranges,
+ const uint64_t* expected,
+ size_t sz,
+ int line) {
+ uint64_t blocks = 0;
+ for (size_t i = 1; i < sz; i += 2) {
+ blocks += expected[i];
+ }
+ EXPECT_EQ(blocks, ranges.blocks()) << "line: " << line;
+
+ const ExtentRanges::ExtentSet& result = ranges.extent_set();
+ ExtentRanges::ExtentSet::const_iterator it = result.begin();
+ for (size_t i = 0; i < sz; i += 2) {
+ EXPECT_FALSE(it == result.end()) << "line: " << line;
+ EXPECT_EQ(expected[i], it->start_block()) << "line: " << line;
+ EXPECT_EQ(expected[i + 1], it->num_blocks()) << "line: " << line;
+ ++it;
+ }
+}
+
+#define EXPECT_RANGE_EQ(ranges, var) \
+ do { \
+ ExpectRangeEq(ranges, var, arraysize(var), __LINE__); \
+ } while (0)
+
+void ExpectRangesOverlapOrTouch(uint64_t a_start, uint64_t a_num,
+ uint64_t b_start, uint64_t b_num) {
+ EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start,
+ a_num),
+ ExtentForRange(b_start,
+ b_num)));
+ EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start,
+ b_num),
+ ExtentForRange(a_start,
+ a_num)));
+}
+
+void ExpectFalseRangesOverlapOrTouch(uint64_t a_start, uint64_t a_num,
+ uint64_t b_start, uint64_t b_num) {
+ EXPECT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start,
+ a_num),
+ ExtentForRange(b_start,
+ b_num)));
+ EXPECT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start,
+ b_num),
+ ExtentForRange(a_start,
+ a_num)));
+ EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start,
+ a_num),
+ ExtentForRange(b_start,
+ b_num)));
+ EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start,
+ b_num),
+ ExtentForRange(a_start,
+ a_num)));
+}
+
+void ExpectRangesOverlap(uint64_t a_start, uint64_t a_num,
+ uint64_t b_start, uint64_t b_num) {
+ EXPECT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start,
+ a_num),
+ ExtentForRange(b_start,
+ b_num)));
+ EXPECT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start,
+ b_num),
+ ExtentForRange(a_start,
+ a_num)));
+ EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start,
+ a_num),
+ ExtentForRange(b_start,
+ b_num)));
+ EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start,
+ b_num),
+ ExtentForRange(a_start,
+ a_num)));
+}
+
+void ExpectFalseRangesOverlap(uint64_t a_start, uint64_t a_num,
+ uint64_t b_start, uint64_t b_num) {
+ EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start,
+ a_num),
+ ExtentForRange(b_start,
+ b_num)));
+ EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start,
+ b_num),
+ ExtentForRange(a_start,
+ a_num)));
+}
+
+} // namespace
+
+TEST(ExtentRangesTest, ExtentsOverlapTest) {
+ ExpectRangesOverlapOrTouch(10, 20, 30, 10);
+ ExpectRangesOverlap(10, 20, 25, 10);
+ ExpectFalseRangesOverlapOrTouch(10, 20, 35, 10);
+ ExpectFalseRangesOverlap(10, 20, 30, 10);
+ ExpectRangesOverlap(12, 4, 12, 3);
+
+ ExpectRangesOverlapOrTouch(kSparseHole, 2, kSparseHole, 3);
+ ExpectRangesOverlap(kSparseHole, 2, kSparseHole, 3);
+ ExpectFalseRangesOverlapOrTouch(kSparseHole, 2, 10, 3);
+ ExpectFalseRangesOverlapOrTouch(10, 2, kSparseHole, 3);
+ ExpectFalseRangesOverlap(kSparseHole, 2, 10, 3);
+ ExpectFalseRangesOverlap(10, 2, kSparseHole, 3);
+}
+
+TEST(ExtentRangesTest, SimpleTest) {
+ ExtentRanges ranges;
+ {
+ static const uint64_t expected[] = {};
+ // Can't use arraysize() on 0-length arrays:
+ ExpectRangeEq(ranges, expected, 0, __LINE__);
+ }
+ ranges.SubtractBlock(2);
+ {
+ static const uint64_t expected[] = {};
+ // Can't use arraysize() on 0-length arrays:
+ ExpectRangeEq(ranges, expected, 0, __LINE__);
+ }
+
+ ranges.AddBlock(0);
+ ranges.Dump();
+ ranges.AddBlock(1);
+ ranges.AddBlock(3);
+
+ {
+ static const uint64_t expected[] = {0, 2, 3, 1};
+ EXPECT_RANGE_EQ(ranges, expected);
+ }
+ ranges.AddBlock(2);
+ {
+ static const uint64_t expected[] = {0, 4};
+ EXPECT_RANGE_EQ(ranges, expected);
+ ranges.AddBlock(kSparseHole);
+ EXPECT_RANGE_EQ(ranges, expected);
+ ranges.SubtractBlock(kSparseHole);
+ EXPECT_RANGE_EQ(ranges, expected);
+ }
+ ranges.SubtractBlock(2);
+ {
+ static const uint64_t expected[] = {0, 2, 3, 1};
+ EXPECT_RANGE_EQ(ranges, expected);
+ }
+
+ for (uint64_t i = 100; i < 1000; i += 100) {
+ ranges.AddExtent(ExtentForRange(i, 50));
+ }
+ {
+ static const uint64_t expected[] = {
+ 0, 2, 3, 1, 100, 50, 200, 50, 300, 50, 400, 50,
+ 500, 50, 600, 50, 700, 50, 800, 50, 900, 50
+ };
+ EXPECT_RANGE_EQ(ranges, expected);
+ }
+
+ ranges.SubtractExtent(ExtentForRange(210, 410 - 210));
+ {
+ static const uint64_t expected[] = {
+ 0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
+ 600, 50, 700, 50, 800, 50, 900, 50
+ };
+ EXPECT_RANGE_EQ(ranges, expected);
+ }
+ ranges.AddExtent(ExtentForRange(100000, 0));
+ {
+ static const uint64_t expected[] = {
+ 0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
+ 600, 50, 700, 50, 800, 50, 900, 50
+ };
+ EXPECT_RANGE_EQ(ranges, expected);
+ }
+ ranges.SubtractExtent(ExtentForRange(3, 0));
+ {
+ static const uint64_t expected[] = {
+ 0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
+ 600, 50, 700, 50, 800, 50, 900, 50
+ };
+ EXPECT_RANGE_EQ(ranges, expected);
+ }
+}
+
+TEST(ExtentRangesTest, MultipleRanges) {
+ ExtentRanges ranges_a, ranges_b;
+ ranges_a.AddBlock(0);
+ ranges_b.AddBlock(4);
+ ranges_b.AddBlock(3);
+ {
+ uint64_t expected[] = {3, 2};
+ EXPECT_RANGE_EQ(ranges_b, expected);
+ }
+ ranges_a.AddRanges(ranges_b);
+ {
+ uint64_t expected[] = {0, 1, 3, 2};
+ EXPECT_RANGE_EQ(ranges_a, expected);
+ }
+ ranges_a.SubtractRanges(ranges_b);
+ {
+ uint64_t expected[] = {0, 1};
+ EXPECT_RANGE_EQ(ranges_a, expected);
+ }
+ {
+ uint64_t expected[] = {3, 2};
+ EXPECT_RANGE_EQ(ranges_b, expected);
+ }
+}
+
+TEST(ExtentRangesTest, GetExtentsForBlockCountTest) {
+ ExtentRanges ranges;
+ ranges.AddExtents(vector<Extent>(1, ExtentForRange(10, 30)));
+ {
+ vector<Extent> zero_extents = ranges.GetExtentsForBlockCount(0);
+ EXPECT_TRUE(zero_extents.empty());
+ }
+ ::google::protobuf::RepeatedPtrField<Extent> rep_field;
+ *rep_field.Add() = ExtentForRange(30, 40);
+ ranges.AddRepeatedExtents(rep_field);
+ ranges.SubtractExtents(vector<Extent>(1, ExtentForRange(20, 10)));
+ *rep_field.Mutable(0) = ExtentForRange(50, 10);
+ ranges.SubtractRepeatedExtents(rep_field);
+ EXPECT_EQ(40, ranges.blocks());
+
+ for (int i = 0; i < 2; i++) {
+ vector<Extent> expected(2);
+ expected[0] = ExtentForRange(10, 10);
+ expected[1] = ExtentForRange(30, i == 0 ? 10 : 20);
+ vector<Extent> actual =
+ ranges.GetExtentsForBlockCount(10 + expected[1].num_blocks());
+ EXPECT_EQ(expected.size(), actual.size());
+ for (vector<Extent>::size_type j = 0, e = expected.size(); j != e; ++j) {
+ EXPECT_EQ(expected[j].start_block(), actual[j].start_block())
+ << "j = " << j;
+ EXPECT_EQ(expected[j].num_blocks(), actual[j].num_blocks())
+ << "j = " << j;
+ }
+ }
+}
+
+TEST(ExtentRangesTest, FilterExtentRangesEmptyRanges) {
+ ExtentRanges ranges;
+ EXPECT_EQ(vector<Extent>(),
+ FilterExtentRanges(vector<Extent>(), ranges));
+ EXPECT_EQ(
+ vector<Extent>{ ExtentForRange(50, 10) },
+ FilterExtentRanges(vector<Extent>{ ExtentForRange(50, 10) }, ranges));
+ // Check that the empty Extents are ignored.
+ EXPECT_EQ(
+ (vector<Extent>{ ExtentForRange(10, 10), ExtentForRange(20, 10) }),
+ FilterExtentRanges(vector<Extent>{
+ ExtentForRange(10, 10),
+ ExtentForRange(3, 0),
+ ExtentForRange(20, 10) }, ranges));
+}
+
+TEST(ExtentRangesTest, FilterExtentRangesMultipleRanges) {
+ // Two overlaping extents, with three ranges to remove.
+ vector<Extent> extents {
+ ExtentForRange(10, 100),
+ ExtentForRange(30, 100) };
+ ExtentRanges ranges;
+ // This overlaps the beginning of the second extent.
+ ranges.AddExtent(ExtentForRange(28, 3));
+ ranges.AddExtent(ExtentForRange(50, 10));
+ ranges.AddExtent(ExtentForRange(70, 10));
+ // This overlaps the end of the second extent.
+ ranges.AddExtent(ExtentForRange(108, 6));
+ EXPECT_EQ(
+ (vector<Extent>{
+ // For the first extent:
+ ExtentForRange(10, 18),
+ ExtentForRange(31, 19),
+ ExtentForRange(60, 10),
+ ExtentForRange(80, 28),
+ // For the second extent:
+ ExtentForRange(31, 19),
+ ExtentForRange(60, 10),
+ ExtentForRange(80, 28),
+ ExtentForRange(114, 16)}),
+ FilterExtentRanges(extents, ranges));
+}
+
+TEST(ExtentRangesTest, FilterExtentRangesOvelapping) {
+ ExtentRanges ranges;
+ ranges.AddExtent(ExtentForRange(10, 3));
+ ranges.AddExtent(ExtentForRange(20, 5));
+ // Requested extent overlaps with one of the ranges.
+ EXPECT_EQ(vector<Extent>(),
+ FilterExtentRanges(vector<Extent>{
+ ExtentForRange(10, 1),
+ ExtentForRange(22, 1) },
+ ranges));
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/extent_utils.cc b/payload_generator/extent_utils.cc
index 6896678..71aae1d 100644
--- a/payload_generator/extent_utils.cc
+++ b/payload_generator/extent_utils.cc
@@ -11,9 +11,9 @@
#include <base/logging.h>
#include <base/macros.h>
-#include "update_engine/extent_ranges.h"
#include "update_engine/payload_constants.h"
#include "update_engine/payload_generator/annotated_operation.h"
+#include "update_engine/payload_generator/extent_ranges.h"
using std::string;
using std::vector;
diff --git a/payload_generator/extent_utils_unittest.cc b/payload_generator/extent_utils_unittest.cc
index 6e685e0..b9f9ef2 100644
--- a/payload_generator/extent_utils_unittest.cc
+++ b/payload_generator/extent_utils_unittest.cc
@@ -9,8 +9,8 @@
#include <gtest/gtest.h>
-#include "update_engine/extent_ranges.h"
#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/extent_ranges.h"
#include "update_engine/test_utils.h"
using std::vector;
diff --git a/payload_generator/graph_utils_unittest.cc b/payload_generator/graph_utils_unittest.cc
index 3253f71..bd6c979 100644
--- a/payload_generator/graph_utils_unittest.cc
+++ b/payload_generator/graph_utils_unittest.cc
@@ -9,8 +9,8 @@
#include <gtest/gtest.h>
-#include "update_engine/extent_ranges.h"
#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/extent_ranges.h"
#include "update_engine/payload_generator/extent_utils.h"
using std::make_pair;
diff --git a/payload_generator/inplace_generator.cc b/payload_generator/inplace_generator.cc
index fd19d14..64c8226 100644
--- a/payload_generator/inplace_generator.cc
+++ b/payload_generator/inplace_generator.cc
@@ -11,11 +11,11 @@
#include <utility>
#include <vector>
-#include "update_engine/extent_ranges.h"
#include "update_engine/payload_constants.h"
#include "update_engine/payload_generator/cycle_breaker.h"
#include "update_engine/payload_generator/delta_diff_generator.h"
#include "update_engine/payload_generator/ext2_filesystem.h"
+#include "update_engine/payload_generator/extent_ranges.h"
#include "update_engine/payload_generator/graph_types.h"
#include "update_engine/payload_generator/graph_utils.h"
#include "update_engine/payload_generator/topological_sort.h"
diff --git a/payload_generator/inplace_generator_unittest.cc b/payload_generator/inplace_generator_unittest.cc
index 5c563c5..b988787 100644
--- a/payload_generator/inplace_generator_unittest.cc
+++ b/payload_generator/inplace_generator_unittest.cc
@@ -14,9 +14,9 @@
#include <base/strings/string_util.h>
#include <gtest/gtest.h>
-#include "update_engine/extent_ranges.h"
#include "update_engine/payload_generator/cycle_breaker.h"
#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/extent_ranges.h"
#include "update_engine/payload_generator/graph_types.h"
#include "update_engine/payload_generator/graph_utils.h"
#include "update_engine/test_utils.h"
diff --git a/payload_generator/raw_filesystem.cc b/payload_generator/raw_filesystem.cc
index ee4423e..f24096e 100644
--- a/payload_generator/raw_filesystem.cc
+++ b/payload_generator/raw_filesystem.cc
@@ -4,7 +4,7 @@
#include "update_engine/payload_generator/raw_filesystem.h"
-#include "update_engine/extent_ranges.h"
+#include "update_engine/payload_generator/extent_ranges.h"
#include "update_engine/update_metadata.pb.h"
#include "update_engine/utils.h"
