update_engine: Further move Extent manipulation to extent_utils.
This patch moves more Extent manipulation functions to extent_utils.
It moves NormalizeExtents() and creates a new ExtentsSublist() function
that will be used by a follow up CL.
BUG=None
TEST=Added unittests.
Change-Id: Icf0ef0af208aa45c9f44e1a73662b3efd8bbbb45
Reviewed-on: https://chromium-review.googlesource.com/275801
Reviewed-by: Alex Deymo <[email protected]>
Commit-Queue: Alex Deymo <[email protected]>
Tested-by: Alex Deymo <[email protected]>
diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
index ef8b8ff..c9259b5 100644
--- a/payload_generator/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -1364,26 +1364,6 @@
extents->end());
}
-void DeltaDiffGenerator::NormalizeExtents(vector<Extent>* extents) {
- vector<Extent> new_extents;
- for (const Extent& curr_ext : *extents) {
- if (new_extents.empty()) {
- new_extents.push_back(curr_ext);
- continue;
- }
- Extent& last_ext = new_extents.back();
- if (last_ext.start_block() + last_ext.num_blocks() ==
- curr_ext.start_block()) {
- // If the extents are touching, we want to combine them.
- last_ext.set_num_blocks(last_ext.num_blocks() + curr_ext.num_blocks());
- } else {
- // Otherwise just include the extent as is.
- new_extents.push_back(curr_ext);
- }
- }
- *extents = new_extents;
-}
-
bool DeltaDiffGenerator::FragmentOperations(
vector<AnnotatedOperation>* aops,
const string& target_part_path,
diff --git a/payload_generator/delta_diff_generator.h b/payload_generator/delta_diff_generator.h
index 07e26ad..06f84a3 100644
--- a/payload_generator/delta_diff_generator.h
+++ b/payload_generator/delta_diff_generator.h
@@ -233,11 +233,6 @@
// Takes a vector of extents and removes extents that begin in a sparse hole.
static void ClearSparseHoles(std::vector<Extent>* extents);
- // Takes a vector of extents and normalizes those extents. Expects the extents
- // to be sorted by start block. E.g. if |extents| is [(1, 2), (3, 5), (10, 2)]
- // then |extents| will be changed to [(1, 7), (10, 2)].
- static void NormalizeExtents(std::vector<Extent>* extents);
-
// Takes a vector of AnnotatedOperations |aops| and fragments those operations
// such that there is only one dst extent per operation. Sets |aops| to a
// vector of the new fragmented operations.
diff --git a/payload_generator/delta_diff_generator_unittest.cc b/payload_generator/delta_diff_generator_unittest.cc
index 050f25b..da82d14 100644
--- a/payload_generator/delta_diff_generator_unittest.cc
+++ b/payload_generator/delta_diff_generator_unittest.cc
@@ -1076,25 +1076,6 @@
EXPECT_EQ(extents[1], ExtentForRange(29, 1));
}
-TEST_F(DeltaDiffGeneratorTest, NormalizeExtentsTest) {
- vector<Extent> extents;
- AddExtent(0, 3, &extents);
- // Make sure it works when there's just one extent.
- DeltaDiffGenerator::NormalizeExtents(&extents);
- EXPECT_EQ(extents.size(), 1);
- EXPECT_EQ(extents[0], ExtentForRange(0, 3));
- AddExtent(3, 2, &extents);
- AddExtent(5, 1, &extents);
- AddExtent(8, 4, &extents);
- AddExtent(13, 1, &extents);
- AddExtent(14, 2, &extents);
- DeltaDiffGenerator::NormalizeExtents(&extents);
- EXPECT_EQ(extents.size(), 3);
- EXPECT_EQ(extents[0], ExtentForRange(0, 6));
- EXPECT_EQ(extents[1], ExtentForRange(8, 4));
- EXPECT_EQ(extents[2], ExtentForRange(13, 3));
-}
-
TEST_F(DeltaDiffGeneratorTest, SplitSourceCopyTest) {
DeltaArchiveManifest_InstallOperation op;
op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
diff --git a/payload_generator/extent_utils.cc b/payload_generator/extent_utils.cc
index dcb8bf8..6896678 100644
--- a/payload_generator/extent_utils.cc
+++ b/payload_generator/extent_utils.cc
@@ -11,6 +11,7 @@
#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"
@@ -46,6 +47,60 @@
return collection.Get(index);
}
+void NormalizeExtents(vector<Extent>* extents) {
+ vector<Extent> new_extents;
+ for (const Extent& curr_ext : *extents) {
+ if (new_extents.empty()) {
+ new_extents.push_back(curr_ext);
+ continue;
+ }
+ Extent& last_ext = new_extents.back();
+ if (last_ext.start_block() + last_ext.num_blocks() ==
+ curr_ext.start_block()) {
+ // If the extents are touching, we want to combine them.
+ last_ext.set_num_blocks(last_ext.num_blocks() + curr_ext.num_blocks());
+ } else {
+ // Otherwise just include the extent as is.
+ new_extents.push_back(curr_ext);
+ }
+ }
+ *extents = new_extents;
+}
+
+vector<Extent> ExtentsSublist(const vector<Extent>& extents,
+ uint64_t block_offset, uint64_t block_count) {
+ vector<Extent> result;
+ uint64_t scanned_blocks = 0;
+ if (block_count == 0)
+ return result;
+ uint64_t end_block_offset = block_offset + block_count;
+ for (const Extent& extent : extents) {
+ // The loop invariant is that if |extents| has enough blocks, there's
+ // still some extent to add to |result|. This implies that at the beginning
+ // of the loop scanned_blocks < block_offset + block_count.
+ if (scanned_blocks + extent.num_blocks() > block_offset) {
+ // This case implies that |extent| has some overlapping with the requested
+ // subsequence.
+ uint64_t new_start = extent.start_block();
+ uint64_t new_num_blocks = extent.num_blocks();
+ if (scanned_blocks + new_num_blocks > end_block_offset) {
+ // Cut the end part of the extent.
+ new_num_blocks = end_block_offset - scanned_blocks;
+ }
+ if (block_offset > scanned_blocks) {
+ // Cut the begin part of the extent.
+ new_num_blocks -= block_offset - scanned_blocks;
+ new_start += block_offset - scanned_blocks;
+ }
+ result.push_back(ExtentForRange(new_start, new_num_blocks));
+ }
+ scanned_blocks += extent.num_blocks();
+ if (scanned_blocks >= end_block_offset)
+ break;
+ }
+ return result;
+}
+
bool operator==(const Extent& a, const Extent& b) {
return a.start_block() == b.start_block() && a.num_blocks() == b.num_blocks();
}
diff --git a/payload_generator/extent_utils.h b/payload_generator/extent_utils.h
index 1583618..e9ab9eb 100644
--- a/payload_generator/extent_utils.h
+++ b/payload_generator/extent_utils.h
@@ -34,6 +34,18 @@
return ret;
}
+// Takes a vector of extents and normalizes those extents. Expects the extents
+// to be sorted by start block. E.g. if |extents| is [(1, 2), (3, 5), (10, 2)]
+// then |extents| will be changed to [(1, 7), (10, 2)].
+void NormalizeExtents(std::vector<Extent>* extents);
+
+// Return a subsequence of the list of blocks passed. Both the passed list of
+// blocks |extents| and the return value are expressed as a list of Extent, not
+// blocks. The returned list skips the first |block_offset| blocks from the
+// |extents| and cotains |block_count| blocks (or less if |extents| is shorter).
+std::vector<Extent> ExtentsSublist(const std::vector<Extent>& extents,
+ uint64_t block_offset, uint64_t block_count);
+
bool operator==(const Extent& a, const Extent& b);
} // namespace chromeos_update_engine
diff --git a/payload_generator/extent_utils_unittest.cc b/payload_generator/extent_utils_unittest.cc
index fe1d000..6e685e0 100644
--- a/payload_generator/extent_utils_unittest.cc
+++ b/payload_generator/extent_utils_unittest.cc
@@ -11,6 +11,7 @@
#include "update_engine/extent_ranges.h"
#include "update_engine/payload_constants.h"
+#include "update_engine/test_utils.h"
using std::vector;
@@ -61,4 +62,73 @@
}
}
+TEST(ExtentUtilsTest, NormalizeExtentsSimpleList) {
+ // Make sure it works when there's just one extent.
+ vector<Extent> extents;
+ NormalizeExtents(&extents);
+ EXPECT_EQ(0, extents.size());
+
+ extents = { ExtentForRange(0, 3) };
+ NormalizeExtents(&extents);
+ EXPECT_EQ(1, extents.size());
+ EXPECT_EQ(ExtentForRange(0, 3), extents[0]);
+}
+
+TEST(ExtentUtilsTest, NormalizeExtentsTest) {
+ vector<Extent> extents = {
+ ExtentForRange(0, 3),
+ ExtentForRange(3, 2),
+ ExtentForRange(5, 1),
+ ExtentForRange(8, 4),
+ ExtentForRange(13, 1),
+ ExtentForRange(14, 2)
+ };
+ NormalizeExtents(&extents);
+ EXPECT_EQ(3, extents.size());
+ EXPECT_EQ(ExtentForRange(0, 6), extents[0]);
+ EXPECT_EQ(ExtentForRange(8, 4), extents[1]);
+ EXPECT_EQ(ExtentForRange(13, 3), extents[2]);
+}
+
+TEST(ExtentUtilsTest, ExtentsSublistTest) {
+ vector<Extent> extents = {
+ ExtentForRange(10, 10),
+ ExtentForRange(30, 10),
+ ExtentForRange(50, 10)
+ };
+
+ // Simple empty result cases.
+ EXPECT_EQ(vector<Extent>(),
+ ExtentsSublist(extents, 1000, 20));
+ EXPECT_EQ(vector<Extent>(),
+ ExtentsSublist(extents, 5, 0));
+ EXPECT_EQ(vector<Extent>(),
+ ExtentsSublist(extents, 30, 1));
+
+ // Normal test cases.
+ EXPECT_EQ(vector<Extent>{ ExtentForRange(13, 2) },
+ ExtentsSublist(extents, 3, 2));
+ EXPECT_EQ(vector<Extent>{ ExtentForRange(15, 5) },
+ ExtentsSublist(extents, 5, 5));
+ EXPECT_EQ((vector<Extent>{ ExtentForRange(15, 5), ExtentForRange(30, 5) }),
+ ExtentsSublist(extents, 5, 10));
+ EXPECT_EQ((vector<Extent>{
+ ExtentForRange(13, 7),
+ ExtentForRange(30, 10),
+ ExtentForRange(50, 3), }),
+ ExtentsSublist(extents, 3, 20));
+
+ // Extact match case.
+ EXPECT_EQ(vector<Extent>{ ExtentForRange(30, 10) },
+ ExtentsSublist(extents, 10, 10));
+ EXPECT_EQ(vector<Extent>{ ExtentForRange(50, 10) },
+ ExtentsSublist(extents, 20, 10));
+
+ // Cases where the requested num_blocks is too big.
+ EXPECT_EQ(vector<Extent>{ ExtentForRange(53, 7) },
+ ExtentsSublist(extents, 23, 100));
+ EXPECT_EQ((vector<Extent>{ ExtentForRange(34, 6), ExtentForRange(50, 10) }),
+ ExtentsSublist(extents, 14, 100));
+}
+
} // namespace chromeos_update_engine
diff --git a/test_utils.cc b/test_utils.cc
index e2361a5..712df64 100644
--- a/test_utils.cc
+++ b/test_utils.cc
@@ -31,6 +31,10 @@
namespace chromeos_update_engine {
+void PrintTo(const Extent& extent, ::std::ostream* os) {
+ *os << "(" << extent.start_block() << ", " << extent.num_blocks() << ")";
+}
+
namespace test_utils {
const char* const kMountPathTemplate = "UpdateEngineTests_mnt-XXXXXX";
diff --git a/test_utils.h b/test_utils.h
index a65b042..dddd563 100644
--- a/test_utils.h
+++ b/test_utils.h
@@ -9,6 +9,8 @@
#include <sys/types.h>
#include <unistd.h>
+// Streams used for gtest's PrintTo() functions.
+#include <iostream> // NOLINT(readability/streams)
#include <memory>
#include <set>
#include <string>
@@ -20,11 +22,17 @@
#include "update_engine/action.h"
#include "update_engine/subprocess.h"
+#include "update_engine/update_metadata.pb.h"
#include "update_engine/utils.h"
// These are some handy functions for unittests.
namespace chromeos_update_engine {
+
+// PrintTo() functions are used by gtest to log these objects. These PrintTo()
+// functions must be defined in the same namespace as the first argument.
+void PrintTo(const Extent& extent, ::std::ostream* os);
+
namespace test_utils {
// 300 byte pseudo-random string. Not null terminated.
