update_engine: Split Extent utils from graph_utils.
"Graph" related utils should only concern parts of the code using the
inplace generator, since other generators don't use a dependency graph.
This patch splits the Extent related utils from the graph related ones
creating a new extent_utils.h file.
BUG=None
TEST=unittest still pass.
Change-Id: I0941698b0a47a6cc222e8dc062fc54eb3cdf4de2
Reviewed-on: https://chromium-review.googlesource.com/274899
Reviewed-by: Gilad Arnold <garnold@chromium.org>
Commit-Queue: Alex Deymo <deymo@chromium.org>
Tested-by: Alex Deymo <deymo@chromium.org>
diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
index 077b8fb..ef8b8ff 100644
--- a/payload_generator/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -767,7 +767,7 @@
for (vector<Block>::size_type i = 0; i < blocks.size(); i++) {
if (blocks[i].writer != Vertex::kInvalidIndex)
continue;
- graph_utils::AppendBlockToExtents(&extents, i);
+ AppendBlockToExtents(&extents, i);
block_count++;
}
@@ -825,7 +825,7 @@
graph_utils::AddReadBeforeDep(vertex, blocks[block_idx].reader,
block_idx);
}
- graph_utils::AppendBlockToExtents(&changed_extents, block_idx);
+ AppendBlockToExtents(&changed_extents, block_idx);
changed_block_count++;
}
buf_offset = buf_end_offset;
diff --git a/payload_generator/delta_diff_generator.h b/payload_generator/delta_diff_generator.h
index 800168e..07e26ad 100644
--- a/payload_generator/delta_diff_generator.h
+++ b/payload_generator/delta_diff_generator.h
@@ -13,8 +13,8 @@
#include <chromeos/secure_blob.h>
#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/extent_utils.h"
#include "update_engine/payload_generator/graph_types.h"
-#include "update_engine/payload_generator/graph_utils.h"
#include "update_engine/payload_generator/operations_generator.h"
#include "update_engine/payload_generator/payload_generation_config.h"
#include "update_engine/update_metadata.pb.h"
@@ -217,7 +217,7 @@
static std::vector<uint64_t> ExpandExtents(const T& extents) {
std::vector<uint64_t> ret;
for (size_t i = 0, e = static_cast<size_t>(extents.size()); i != e; ++i) {
- const Extent extent = graph_utils::GetElement(extents, i);
+ const Extent extent = GetElement(extents, i);
if (extent.start_block() == kSparseHole) {
ret.resize(ret.size() + extent.num_blocks(), kSparseHole);
} else {
diff --git a/payload_generator/delta_diff_generator_unittest.cc b/payload_generator/delta_diff_generator_unittest.cc
index cf393db..94dd1e4 100644
--- a/payload_generator/delta_diff_generator_unittest.cc
+++ b/payload_generator/delta_diff_generator_unittest.cc
@@ -29,7 +29,6 @@
#include "update_engine/payload_constants.h"
#include "update_engine/payload_generator/extent_mapper.h"
#include "update_engine/payload_generator/graph_types.h"
-#include "update_engine/payload_generator/graph_utils.h"
#include "update_engine/subprocess.h"
#include "update_engine/test_utils.h"
#include "update_engine/utils.h"
diff --git a/payload_generator/extent_mapper.cc b/payload_generator/extent_mapper.cc
index ce490d2..c936450 100644
--- a/payload_generator/extent_mapper.cc
+++ b/payload_generator/extent_mapper.cc
@@ -17,8 +17,7 @@
#include <algorithm>
#include "update_engine/payload_constants.h"
-#include "update_engine/payload_generator/graph_types.h"
-#include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/payload_generator/extent_utils.h"
#include "update_engine/utils.h"
using std::string;
@@ -71,7 +70,7 @@
const uint64_t block = (block32 == 0 ? kSparseHole : block32);
- graph_utils::AppendBlockToExtents(out, block);
+ AppendBlockToExtents(out, block);
}
return true;
}
diff --git a/payload_generator/extent_utils.cc b/payload_generator/extent_utils.cc
new file mode 100644
index 0000000..dcb8bf8
--- /dev/null
+++ b/payload_generator/extent_utils.cc
@@ -0,0 +1,53 @@
+// Copyright (c) 2009 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_utils.h"
+
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <base/logging.h>
+#include <base/macros.h>
+
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/annotated_operation.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+void AppendBlockToExtents(vector<Extent>* extents, uint64_t block) {
+ // First try to extend the last extent in |extents|, if any.
+ if (!extents->empty()) {
+ Extent& extent = extents->back();
+ uint64_t next_block = extent.start_block() == kSparseHole ?
+ kSparseHole : extent.start_block() + extent.num_blocks();
+ if (next_block == block) {
+ extent.set_num_blocks(extent.num_blocks() + 1);
+ return;
+ }
+ }
+ // If unable to extend the last extent, append a new single-block extent.
+ Extent new_extent;
+ new_extent.set_start_block(block);
+ new_extent.set_num_blocks(1);
+ extents->push_back(new_extent);
+}
+
+Extent GetElement(const vector<Extent>& collection, size_t index) {
+ return collection[index];
+}
+Extent GetElement(
+ const google::protobuf::RepeatedPtrField<Extent>& collection,
+ size_t index) {
+ return collection.Get(index);
+}
+
+bool operator==(const Extent& a, const Extent& b) {
+ return a.start_block() == b.start_block() && a.num_blocks() == b.num_blocks();
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/extent_utils.h b/payload_generator/extent_utils.h
new file mode 100644
index 0000000..1583618
--- /dev/null
+++ b/payload_generator/extent_utils.h
@@ -0,0 +1,41 @@
+// Copyright 2015 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_UTILS_H_
+#define UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_UTILS_H_
+
+#include <vector>
+
+#include "update_engine/update_metadata.pb.h"
+
+// Utility functions for manipulating Extents and lists of blocks.
+
+namespace chromeos_update_engine {
+
+// |block| must either be the next block in the last extent or a block
+// in the next extent. This function will not handle inserting block
+// into an arbitrary place in the extents.
+void AppendBlockToExtents(std::vector<Extent>* extents, uint64_t block);
+
+// Get/SetElement are intentionally overloaded so that templated functions
+// can accept either type of collection of Extents.
+Extent GetElement(const std::vector<Extent>& collection, size_t index);
+Extent GetElement(
+ const google::protobuf::RepeatedPtrField<Extent>& collection,
+ size_t index);
+
+template<typename T>
+uint64_t BlocksInExtents(const T& collection) {
+ uint64_t ret = 0;
+ for (size_t i = 0; i < static_cast<size_t>(collection.size()); ++i) {
+ ret += GetElement(collection, i).num_blocks();
+ }
+ return ret;
+}
+
+bool operator==(const Extent& a, const Extent& b);
+
+} // namespace chromeos_update_engine
+
+#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_UTILS_H_
diff --git a/payload_generator/extent_utils_unittest.cc b/payload_generator/extent_utils_unittest.cc
new file mode 100644
index 0000000..fe1d000
--- /dev/null
+++ b/payload_generator/extent_utils_unittest.cc
@@ -0,0 +1,64 @@
+// Copyright 2015 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_utils.h"
+
+#include <utility>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/extent_ranges.h"
+#include "update_engine/payload_constants.h"
+
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class ExtentUtilsTest : public ::testing::Test {};
+
+TEST(ExtentUtilsTest, AppendSparseToExtentsTest) {
+ vector<Extent> extents;
+
+ EXPECT_EQ(0, extents.size());
+ AppendBlockToExtents(&extents, kSparseHole);
+ EXPECT_EQ(1, extents.size());
+ AppendBlockToExtents(&extents, 0);
+ EXPECT_EQ(2, extents.size());
+ AppendBlockToExtents(&extents, kSparseHole);
+ AppendBlockToExtents(&extents, kSparseHole);
+
+ ASSERT_EQ(3, extents.size());
+ EXPECT_EQ(kSparseHole, extents[0].start_block());
+ EXPECT_EQ(1, extents[0].num_blocks());
+ EXPECT_EQ(0, extents[1].start_block());
+ EXPECT_EQ(1, extents[1].num_blocks());
+ EXPECT_EQ(kSparseHole, extents[2].start_block());
+ EXPECT_EQ(2, extents[2].num_blocks());
+}
+
+TEST(ExtentUtilsTest, BlocksInExtentsTest) {
+ {
+ vector<Extent> extents;
+ EXPECT_EQ(0, BlocksInExtents(extents));
+ extents.push_back(ExtentForRange(0, 1));
+ EXPECT_EQ(1, BlocksInExtents(extents));
+ extents.push_back(ExtentForRange(23, 55));
+ EXPECT_EQ(56, BlocksInExtents(extents));
+ extents.push_back(ExtentForRange(1, 2));
+ EXPECT_EQ(58, BlocksInExtents(extents));
+ }
+ {
+ google::protobuf::RepeatedPtrField<Extent> extents;
+ EXPECT_EQ(0, BlocksInExtents(extents));
+ *extents.Add() = ExtentForRange(0, 1);
+ EXPECT_EQ(1, BlocksInExtents(extents));
+ *extents.Add() = ExtentForRange(23, 55);
+ EXPECT_EQ(56, BlocksInExtents(extents));
+ *extents.Add() = ExtentForRange(1, 2);
+ EXPECT_EQ(58, BlocksInExtents(extents));
+ }
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/graph_utils.cc b/payload_generator/graph_utils.cc
index 3f9b28f..7b03236 100644
--- a/payload_generator/graph_utils.cc
+++ b/payload_generator/graph_utils.cc
@@ -13,6 +13,7 @@
#include "update_engine/payload_constants.h"
#include "update_engine/payload_generator/annotated_operation.h"
+#include "update_engine/payload_generator/extent_utils.h"
using std::make_pair;
using std::pair;
@@ -20,7 +21,6 @@
using std::vector;
namespace chromeos_update_engine {
-
namespace graph_utils {
uint64_t EdgeWeight(const Graph& graph, const Edge& edge) {
@@ -35,24 +35,6 @@
return weight;
}
-void AppendBlockToExtents(vector<Extent>* extents, uint64_t block) {
- // First try to extend the last extent in |extents|, if any.
- if (!extents->empty()) {
- Extent& extent = extents->back();
- uint64_t next_block = extent.start_block() == kSparseHole ?
- kSparseHole : extent.start_block() + extent.num_blocks();
- if (next_block == block) {
- extent.set_num_blocks(extent.num_blocks() + 1);
- return;
- }
- }
- // If unable to extend the last extent, append a new single-block extent.
- Extent new_extent;
- new_extent.set_start_block(block);
- new_extent.set_num_blocks(1);
- extents->push_back(new_extent);
-}
-
void AddReadBeforeDep(Vertex* src,
Vertex::Index dst,
uint64_t block) {
@@ -106,15 +88,6 @@
}
}
-Extent GetElement(const vector<Extent>& collection, size_t index) {
- return collection[index];
-}
-Extent GetElement(
- const google::protobuf::RepeatedPtrField<Extent>& collection,
- size_t index) {
- return collection.Get(index);
-}
-
namespace {
template<typename T>
void DumpExtents(const T& field, int prepend_space_count) {
@@ -154,9 +127,4 @@
}
} // namespace graph_utils
-
-bool operator==(const Extent& a, const Extent& b) {
- return a.start_block() == b.start_block() && a.num_blocks() == b.num_blocks();
-}
-
} // namespace chromeos_update_engine
diff --git a/payload_generator/graph_utils.h b/payload_generator/graph_utils.h
index e4692e0..6595e57 100644
--- a/payload_generator/graph_utils.h
+++ b/payload_generator/graph_utils.h
@@ -35,27 +35,6 @@
// For each node N in graph, drop all edges N->|index|.
void DropIncomingEdgesTo(Graph* graph, Vertex::Index index);
-// block must either be the next block in the last extent or a block
-// in the next extent. This function will not handle inserting block
-// into an arbitrary place in the extents.
-void AppendBlockToExtents(std::vector<Extent>* extents, uint64_t block);
-
-// Get/SetElement are intentionally overloaded so that templated functions
-// can accept either type of collection of Extents.
-Extent GetElement(const std::vector<Extent>& collection, size_t index);
-Extent GetElement(
- const google::protobuf::RepeatedPtrField<Extent>& collection,
- size_t index);
-
-template<typename T>
-uint64_t BlocksInExtents(const T& collection) {
- uint64_t ret = 0;
- for (size_t i = 0; i < static_cast<size_t>(collection.size()); ++i) {
- ret += GetElement(collection, i).num_blocks();
- }
- return ret;
-}
-
void DumpGraph(const Graph& graph);
} // namespace graph_utils
diff --git a/payload_generator/graph_utils_unittest.cc b/payload_generator/graph_utils_unittest.cc
index c96927f..3253f71 100644
--- a/payload_generator/graph_utils_unittest.cc
+++ b/payload_generator/graph_utils_unittest.cc
@@ -11,6 +11,7 @@
#include "update_engine/extent_ranges.h"
#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/extent_utils.h"
using std::make_pair;
using std::vector;
@@ -27,12 +28,12 @@
vector<Extent>& extents = graph[0].out_edges[1].extents;
EXPECT_EQ(0, extents.size());
- graph_utils::AppendBlockToExtents(&extents, 0);
+ AppendBlockToExtents(&extents, 0);
EXPECT_EQ(1, extents.size());
- graph_utils::AppendBlockToExtents(&extents, 1);
- graph_utils::AppendBlockToExtents(&extents, 2);
+ AppendBlockToExtents(&extents, 1);
+ AppendBlockToExtents(&extents, 2);
EXPECT_EQ(1, extents.size());
- graph_utils::AppendBlockToExtents(&extents, 4);
+ AppendBlockToExtents(&extents, 4);
EXPECT_EQ(2, extents.size());
EXPECT_EQ(0, extents[0].start_block());
@@ -43,48 +44,6 @@
EXPECT_EQ(4, graph_utils::EdgeWeight(graph, make_pair(0, 1)));
}
-TEST(GraphUtilsTest, AppendSparseToExtentsTest) {
- vector<Extent> extents;
-
- EXPECT_EQ(0, extents.size());
- graph_utils::AppendBlockToExtents(&extents, kSparseHole);
- EXPECT_EQ(1, extents.size());
- graph_utils::AppendBlockToExtents(&extents, 0);
- EXPECT_EQ(2, extents.size());
- graph_utils::AppendBlockToExtents(&extents, kSparseHole);
- graph_utils::AppendBlockToExtents(&extents, kSparseHole);
-
- ASSERT_EQ(3, extents.size());
- EXPECT_EQ(kSparseHole, extents[0].start_block());
- EXPECT_EQ(1, extents[0].num_blocks());
- EXPECT_EQ(0, extents[1].start_block());
- EXPECT_EQ(1, extents[1].num_blocks());
- EXPECT_EQ(kSparseHole, extents[2].start_block());
- EXPECT_EQ(2, extents[2].num_blocks());
-}
-
-TEST(GraphUtilsTest, BlocksInExtentsTest) {
- {
- vector<Extent> extents;
- EXPECT_EQ(0, graph_utils::BlocksInExtents(extents));
- extents.push_back(ExtentForRange(0, 1));
- EXPECT_EQ(1, graph_utils::BlocksInExtents(extents));
- extents.push_back(ExtentForRange(23, 55));
- EXPECT_EQ(56, graph_utils::BlocksInExtents(extents));
- extents.push_back(ExtentForRange(1, 2));
- EXPECT_EQ(58, graph_utils::BlocksInExtents(extents));
- }
- {
- google::protobuf::RepeatedPtrField<Extent> extents;
- EXPECT_EQ(0, graph_utils::BlocksInExtents(extents));
- *extents.Add() = ExtentForRange(0, 1);
- EXPECT_EQ(1, graph_utils::BlocksInExtents(extents));
- *extents.Add() = ExtentForRange(23, 55);
- EXPECT_EQ(56, graph_utils::BlocksInExtents(extents));
- *extents.Add() = ExtentForRange(1, 2);
- EXPECT_EQ(58, graph_utils::BlocksInExtents(extents));
- }
-}
TEST(GraphUtilsTest, DepsTest) {
Graph graph(3);
diff --git a/payload_generator/inplace_generator.cc b/payload_generator/inplace_generator.cc
index febb5e6..29d53e3 100644
--- a/payload_generator/inplace_generator.cc
+++ b/payload_generator/inplace_generator.cc
@@ -56,7 +56,7 @@
vector<Extent> CompressExtents(const vector<uint64_t>& blocks) {
vector<Extent> new_extents;
for (uint64_t block : blocks) {
- graph_utils::AppendBlockToExtents(&new_extents, block);
+ AppendBlockToExtents(&new_extents, block);
}
return new_extents;
}
@@ -194,7 +194,7 @@
edge_it = (*graph)[blocks[i].writer].out_edges.find(blocks[i].reader);
CHECK(edge_it != (*graph)[blocks[i].writer].out_edges.end());
}
- graph_utils::AppendBlockToExtents(&edge_it->second.extents, i);
+ AppendBlockToExtents(&edge_it->second.extents, i);
}
}
@@ -266,7 +266,7 @@
template<typename T>
bool TempBlocksExistInExtents(const T& extents) {
for (int i = 0, e = extents.size(); i < e; ++i) {
- Extent extent = graph_utils::GetElement(extents, i);
+ Extent extent = GetElement(extents, i);
uint64_t start = extent.start_block();
uint64_t num = extent.num_blocks();
if (start >= kTempBlockStart || (start + num) >= kTempBlockStart) {
diff --git a/payload_generator/inplace_generator_unittest.cc b/payload_generator/inplace_generator_unittest.cc
index fdf3aba..6c4f36b 100644
--- a/payload_generator/inplace_generator_unittest.cc
+++ b/payload_generator/inplace_generator_unittest.cc
@@ -18,6 +18,7 @@
#include "update_engine/payload_generator/cycle_breaker.h"
#include "update_engine/payload_generator/delta_diff_generator.h"
#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/payload_generator/graph_utils.h"
#include "update_engine/test_utils.h"
#include "update_engine/utils.h"
@@ -136,9 +137,9 @@
graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
// Reads from blocks 3, 5, 7
vector<Extent> extents;
- graph_utils::AppendBlockToExtents(&extents, 3);
- graph_utils::AppendBlockToExtents(&extents, 5);
- graph_utils::AppendBlockToExtents(&extents, 7);
+ AppendBlockToExtents(&extents, 3);
+ AppendBlockToExtents(&extents, 5);
+ AppendBlockToExtents(&extents, 7);
DeltaDiffGenerator::StoreExtents(extents,
graph.back().op.mutable_src_extents());
blocks[3].reader = graph.size() - 1;
@@ -147,9 +148,9 @@
// Writes to blocks 1, 2, 4
extents.clear();
- graph_utils::AppendBlockToExtents(&extents, 1);
- graph_utils::AppendBlockToExtents(&extents, 2);
- graph_utils::AppendBlockToExtents(&extents, 4);
+ AppendBlockToExtents(&extents, 1);
+ AppendBlockToExtents(&extents, 2);
+ AppendBlockToExtents(&extents, 4);
DeltaDiffGenerator::StoreExtents(extents,
graph.back().op.mutable_dst_extents());
blocks[1].writer = graph.size() - 1;
@@ -161,9 +162,9 @@
graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
// Reads from blocks 1, 2, 4
vector<Extent> extents;
- graph_utils::AppendBlockToExtents(&extents, 1);
- graph_utils::AppendBlockToExtents(&extents, 2);
- graph_utils::AppendBlockToExtents(&extents, 4);
+ AppendBlockToExtents(&extents, 1);
+ AppendBlockToExtents(&extents, 2);
+ AppendBlockToExtents(&extents, 4);
DeltaDiffGenerator::StoreExtents(extents,
graph.back().op.mutable_src_extents());
blocks[1].reader = graph.size() - 1;
@@ -172,9 +173,9 @@
// Writes to blocks 3, 5, 6
extents.clear();
- graph_utils::AppendBlockToExtents(&extents, 3);
- graph_utils::AppendBlockToExtents(&extents, 5);
- graph_utils::AppendBlockToExtents(&extents, 6);
+ AppendBlockToExtents(&extents, 3);
+ AppendBlockToExtents(&extents, 5);
+ AppendBlockToExtents(&extents, 6);
DeltaDiffGenerator::StoreExtents(extents,
graph.back().op.mutable_dst_extents());
blocks[3].writer = graph.size() - 1;
diff --git a/payload_generator/metadata.cc b/payload_generator/metadata.cc
index 77e02fa..f185465 100644
--- a/payload_generator/metadata.cc
+++ b/payload_generator/metadata.cc
@@ -18,7 +18,7 @@
#include "update_engine/extent_ranges.h"
#include "update_engine/payload_generator/delta_diff_generator.h"
#include "update_engine/payload_generator/ext2_utils.h"
-#include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/payload_generator/extent_utils.h"
#include "update_engine/payload_generator/inplace_generator.h"
#include "update_engine/utils.h"
@@ -281,7 +281,7 @@
int ref_offset,
void* priv) {
vector<Extent>* extents = static_cast<vector<Extent>*>(priv);
- graph_utils::AppendBlockToExtents(extents, *blocknr);
+ AppendBlockToExtents(extents, *blocknr);
return 0;
}
@@ -295,7 +295,7 @@
void* priv) {
vector<Extent>* extents = static_cast<vector<Extent>*>(priv);
if (blockcnt < 0) {
- graph_utils::AppendBlockToExtents(extents, *blocknr);
+ AppendBlockToExtents(extents, *blocknr);
}
return 0;
}