AU: More graph utilities
EdgeProperties: support for listing blocks in a write-before
dependency. Blocks historically have only been listed for a
read-before dep. operator== for Extent and EdgeProperties.
Vertex: ability to mark invalid. An invalid vertex is not part of the
graph.
graph utils: Functions to add and drop dependencies.
Overloaded GetElement() to pull an element at a given index from
either a vector<Extent> or RepeatedPtrField<Extent>.
DumpGraph function, useful for debugging.
BUG=none
TEST=unittests
Review URL: http://codereview.chromium.org/3596007
diff --git a/graph_types.h b/graph_types.h
index e7867f6..e3220c0 100644
--- a/graph_types.h
+++ b/graph_types.h
@@ -18,12 +18,28 @@
namespace chromeos_update_engine {
+bool operator==(const Extent& a, const Extent& b);
+
struct EdgeProperties {
- std::vector<Extent> extents; // filesystem extents represented
+ // Read-before extents. I.e., blocks in |extents| must be read by the
+ // node pointed to before the pointing node runs (presumably b/c it
+ // overwrites these blocks).
+ std::vector<Extent> extents;
+
+ // Write before extents. I.e., blocks in |write_extents| must be written
+ // by the node pointed to before the pointing node runs (presumably
+ // b/c it reads the data written by the other node).
+ std::vector<Extent> write_extents;
+
+ bool operator==(const EdgeProperties& that) const {
+ return extents == that.extents && write_extents == that.write_extents;
+ }
};
struct Vertex {
- Vertex() : index(-1), lowlink(-1) {}
+ Vertex() : valid(true), index(-1), lowlink(-1) {}
+ bool valid;
+
typedef std::map<std::vector<Vertex>::size_type, EdgeProperties> EdgeMap;
EdgeMap out_edges;
@@ -51,6 +67,8 @@
typedef std::pair<Vertex::Index, Vertex::Index> Edge;
const uint64_t kSparseHole = kuint64max;
+const uint64_t kTempBlockStart = 1ULL << 60;
+COMPILE_ASSERT(kTempBlockStart != 0, kTempBlockStart_invalid);
} // namespace chromeos_update_engine
diff --git a/graph_utils.cc b/graph_utils.cc
index 5ad67cf..47d0c53 100644
--- a/graph_utils.cc
+++ b/graph_utils.cc
@@ -3,8 +3,17 @@
// found in the LICENSE file.
#include "update_engine/graph_utils.h"
-#include "base/basictypes.h"
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <base/basictypes.h>
+#include <base/logging.h>
+
+using std::make_pair;
+using std::pair;
+using std::string;
using std::vector;
namespace chromeos_update_engine {
@@ -45,6 +54,124 @@
extents->push_back(new_extent);
}
+void AddReadBeforeDep(Vertex* src,
+ Vertex::Index dst,
+ uint64_t block) {
+ Vertex::EdgeMap::iterator edge_it = src->out_edges.find(dst);
+ if (edge_it == src->out_edges.end()) {
+ // Must create new edge
+ pair<Vertex::EdgeMap::iterator, bool> result =
+ src->out_edges.insert(make_pair(dst, EdgeProperties()));
+ CHECK(result.second);
+ edge_it = result.first;
+ }
+ AppendBlockToExtents(&edge_it->second.extents, block);
+}
+
+void AddReadBeforeDepExtents(Vertex* src,
+ Vertex::Index dst,
+ const vector<Extent>& extents) {
+ // TODO(adlr): Be more efficient than adding each block individually.
+ for (vector<Extent>::const_iterator it = extents.begin(), e = extents.end();
+ it != e; ++it) {
+ const Extent& extent = *it;
+ for (uint64_t block = extent.start_block(),
+ block_end = extent.start_block() + extent.num_blocks();
+ block != block_end; ++block) {
+ AddReadBeforeDep(src, dst, block);
+ }
+ }
+}
+
+void DropWriteBeforeDeps(Vertex::EdgeMap* edge_map) {
+ // Specially crafted for-loop for the map-iterate-delete dance.
+ for (Vertex::EdgeMap::iterator it = edge_map->begin();
+ it != edge_map->end(); ) {
+ if (!it->second.write_extents.empty())
+ it->second.write_extents.clear();
+ if (it->second.extents.empty()) {
+ // Erase *it, as it contains no blocks
+ edge_map->erase(it++);
+ } else {
+ ++it;
+ }
+ }
+}
+
+// For each node N in graph, drop all edges N->|index|.
+void DropIncomingEdgesTo(Graph* graph, Vertex::Index index) {
+ // This would be much more efficient if we had doubly-linked
+ // edges in the graph.
+ for (Graph::iterator it = graph->begin(), e = graph->end(); it != e; ++it) {
+ it->out_edges.erase(index);
+ }
+}
+
+Extent GetElement(const std::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) {
+ string header(prepend_space_count, ' ');
+ for (int i = 0, e = field.size(); i != e; ++i) {
+ LOG(INFO) << header << "(" << GetElement(field, i).start_block() << ", "
+ << GetElement(field, i).num_blocks() << ")";
+ }
+}
+
+void DumpOutEdges(const Vertex::EdgeMap& out_edges) {
+ for (Vertex::EdgeMap::const_iterator it = out_edges.begin(),
+ e = out_edges.end(); it != e; ++it) {
+ LOG(INFO) << " " << it->first << " read-before:";
+ DumpExtents(it->second.extents, 6);
+ LOG(INFO) << " write-before:";
+ DumpExtents(it->second.write_extents, 6);
+ }
+}
+} // namespace {}
+
+void DumpGraph(const Graph& graph) {
+ LOG(INFO) << "Graph length: " << graph.size();
+ for (Graph::size_type i = 0, e = graph.size(); i != e; ++i) {
+ string type_str = "UNK";
+ switch(graph[i].op.type()) {
+ case DeltaArchiveManifest_InstallOperation_Type_BSDIFF:
+ type_str = "BSDIFF";
+ break;
+ case DeltaArchiveManifest_InstallOperation_Type_MOVE:
+ type_str = "MOVE";
+ break;
+ case DeltaArchiveManifest_InstallOperation_Type_REPLACE:
+ type_str = "REPLACE";
+ break;
+ case DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ:
+ type_str = "REPLACE_BZ";
+ break;
+ }
+ LOG(INFO) << i
+ << (graph[i].valid ? "" : "-INV")
+ << ": " << graph[i].file_name
+ << ": " << type_str;
+ LOG(INFO) << " src_extents:";
+ DumpExtents(graph[i].op.src_extents(), 4);
+ LOG(INFO) << " dst_extents:";
+ DumpExtents(graph[i].op.dst_extents(), 4);
+ LOG(INFO) << " out edges:";
+ DumpOutEdges(graph[i].out_edges);
+ }
+}
+
} // 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/graph_utils.h b/graph_utils.h
index fd602ea..6f7b9a2 100644
--- a/graph_utils.h
+++ b/graph_utils.h
@@ -19,11 +19,43 @@
// Returns the number of blocks represented by all extents in the edge.
uint64_t EdgeWeight(const Graph& graph, const Edge& edge);
+// These add a read-before dependency from graph[src] -> graph[dst]. If the dep
+// already exists, the block/s is/are added to the existing edge.
+void AddReadBeforeDep(Vertex* src,
+ Vertex::Index dst,
+ uint64_t block);
+void AddReadBeforeDepExtents(Vertex* src,
+ Vertex::Index dst,
+ const std::vector<Extent>& extents);
+
+void DropWriteBeforeDeps(Vertex::EdgeMap* edge_map);
+
+// 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
} // namespace chromeos_update_engine
diff --git a/graph_utils_unittest.cc b/graph_utils_unittest.cc
index d947ddd..cfa2b5c 100644
--- a/graph_utils_unittest.cc
+++ b/graph_utils_unittest.cc
@@ -4,8 +4,11 @@
#include <utility>
#include <vector>
+
#include <gtest/gtest.h>
+
#include "update_engine/graph_utils.h"
+#include "update_engine/extent_ranges.h"
using std::make_pair;
using std::vector;
@@ -38,4 +41,62 @@
EXPECT_EQ(4, graph_utils::EdgeWeight(graph, make_pair(0, 1)));
}
+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);
+
+ graph_utils::AddReadBeforeDep(&graph[0], 1, 3);
+ EXPECT_EQ(1, graph[0].out_edges.size());
+ {
+ Extent& extent = graph[0].out_edges[1].extents[0];
+ EXPECT_EQ(3, extent.start_block());
+ EXPECT_EQ(1, extent.num_blocks());
+ }
+ graph_utils::AddReadBeforeDep(&graph[0], 1, 4);
+ EXPECT_EQ(1, graph[0].out_edges.size());
+ {
+ Extent& extent = graph[0].out_edges[1].extents[0];
+ EXPECT_EQ(3, extent.start_block());
+ EXPECT_EQ(2, extent.num_blocks());
+ }
+ graph_utils::AddReadBeforeDepExtents(&graph[2], 1,
+ vector<Extent>(1, ExtentForRange(5, 2)));
+ EXPECT_EQ(1, graph[2].out_edges.size());
+ {
+ Extent& extent = graph[2].out_edges[1].extents[0];
+ EXPECT_EQ(5, extent.start_block());
+ EXPECT_EQ(2, extent.num_blocks());
+ }
+ // Change most recent edge from read-before to write-before
+ graph[2].out_edges[1].write_extents.swap(graph[2].out_edges[1].extents);
+ graph_utils::DropWriteBeforeDeps(&graph[2].out_edges);
+ EXPECT_EQ(0, graph[2].out_edges.size());
+
+ EXPECT_EQ(1, graph[0].out_edges.size());
+ graph_utils::DropIncomingEdgesTo(&graph, 1);
+ EXPECT_EQ(0, graph[0].out_edges.size());
+}
+
} // namespace chromeos_update_engine