update_engine: Implement FilterExtentRanges.
This patch includes a new FilterExtentRanges() function to filter out
a set of blocks from a list of extents. This function is useful to remove
overlapping lists of blocks when generating operations during delta
generation. While this function is included in the main update_engine
daemon as well, the whole extent_ranges.{cc,h} module will be migrated
to the payload_generator/ directory. This function will be used in a
follow up CL.
BUG=None
TEST=Added unittests.
Change-Id: Ia9d561550fd6f59d59a9e178dd866fd71a095375
Reviewed-on: https://chromium-review.googlesource.com/275802
Reviewed-by: Alex Deymo <deymo@chromium.org>
Commit-Queue: Alex Deymo <deymo@chromium.org>
Tested-by: Alex Deymo <deymo@chromium.org>
diff --git a/extent_ranges.cc b/extent_ranges.cc
index 326dbbd..b425a86 100644
--- a/extent_ranges.cc
+++ b/extent_ranges.cc
@@ -223,4 +223,55 @@
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/extent_ranges.h b/extent_ranges.h
index 4376d05..ec3547c 100644
--- a/extent_ranges.h
+++ b/extent_ranges.h
@@ -68,6 +68,12 @@
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_EXTENT_RANGES_H_
diff --git a/extent_ranges_unittest.cc b/extent_ranges_unittest.cc
index b4de3bc..7624f3d 100644
--- a/extent_ranges_unittest.cc
+++ b/extent_ranges_unittest.cc
@@ -9,6 +9,7 @@
#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;
@@ -255,4 +256,59 @@
}
}
+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