update_engine: Refactor inplace payload generator algorithm code.
Create a class, InplaceGenerator, that contains all functionality
related to the inplace delta generation method (minor version 1).
BUG=chromium:459701
TEST=`FEATURES=test emerge-link update_engine`
Change-Id: Ib742f70030d6c2fcb1cc3138e0f4aef54eca6975
Reviewed-on: https://chromium-review.googlesource.com/251621
Reviewed-by: Alex Deymo <deymo@chromium.org>
Commit-Queue: Allie Wood <alliewood@chromium.org>
Tested-by: Allie Wood <alliewood@chromium.org>
diff --git a/delta_performer_unittest.cc b/delta_performer_unittest.cc
index 4e39c0c..71c650c 100644
--- a/delta_performer_unittest.cc
+++ b/delta_performer_unittest.cc
@@ -46,7 +46,6 @@
extern const char* kUnittestPrivateKey2Path;
extern const char* kUnittestPublicKey2Path;
-static const size_t kBlockSize = 4096;
static const char* kBogusMetadataSignature1 =
"awSFIUdUZz2VWFiR+ku0Pj00V7bPQPQFYQSXjEXr3vaw3TE4xHV5CraY3/YrZpBv"
"J5z4dSBskoeuaO1TNC/S6E05t+yt36tE4Fh79tMnJ/z9fogBDXWgXLEUyG78IEQr"
diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
index 0855232..77444e1 100644
--- a/payload_generator/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -13,7 +13,6 @@
#include <algorithm>
#include <map>
#include <memory>
-#include <set>
#include <string>
#include <utility>
#include <vector>
@@ -28,29 +27,25 @@
#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/cycle_breaker.h"
#include "update_engine/payload_generator/extent_mapper.h"
#include "update_engine/payload_generator/filesystem_iterator.h"
#include "update_engine/payload_generator/full_update_generator.h"
#include "update_engine/payload_generator/graph_types.h"
#include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/payload_generator/inplace_generator.h"
#include "update_engine/payload_generator/metadata.h"
#include "update_engine/payload_generator/payload_signer.h"
-#include "update_engine/payload_generator/topological_sort.h"
#include "update_engine/payload_verifier.h"
#include "update_engine/subprocess.h"
#include "update_engine/update_metadata.pb.h"
#include "update_engine/utils.h"
-using std::make_pair;
using std::map;
using std::max;
using std::min;
-using std::pair;
using std::set;
using std::string;
using std::unique_ptr;
@@ -61,9 +56,6 @@
const uint64_t kVersionNumber = 1;
const uint64_t kFullUpdateChunkSize = 1024 * 1024; // bytes
-const size_t kBlockSize = 4096; // bytes
-const char kEmptyPath[] = "";
-
// The maximum destination size allowed for bsdiff. In general, bsdiff should
// work for arbitrary big files, but the payload generation and payload
// application requires a significant amount of RAM. We put a hard-limit of
@@ -90,6 +82,9 @@
// bytes
const size_t kRootFSPartitionSize = static_cast<size_t>(2) * 1024 * 1024 * 1024;
+const size_t kBlockSize = 4096; // bytes
+const char* const kEmptyPath = "";
+const char* const kBsdiffPath = "bsdiff";
// Needed for testing purposes, in case we can't use actual filesystem objects.
// TODO(garnold) (chromium:331965) Replace this hack with a properly injected
@@ -112,92 +107,6 @@
return true;
}
-// For a given regular file which must exist at new_root + path, and
-// may exist at old_root + path, creates a new InstallOperation and
-// adds it to the graph. Also, populates the |blocks| array as
-// necessary, if |blocks| is non-null. Also, writes the data
-// necessary to send the file down to the client into data_fd, which
-// has length *data_file_size. *data_file_size is updated
-// appropriately. If |existing_vertex| is no kInvalidIndex, use that
-// rather than allocating a new vertex. Returns true on success.
-bool DeltaReadFile(Graph* graph,
- Vertex::Index existing_vertex,
- vector<Block>* blocks,
- const string& old_root,
- const string& new_root,
- const string& path, // within new_root
- off_t chunk_offset,
- off_t chunk_size,
- int data_fd,
- off_t* data_file_size) {
- chromeos::Blob data;
- DeltaArchiveManifest_InstallOperation operation;
-
- string old_path = (old_root == kEmptyPath) ? kEmptyPath :
- old_root + path;
-
- // If bsdiff breaks again, blacklist the problem file by using:
- // bsdiff_allowed = (path != "/foo/bar")
- //
- // TODO(dgarrett): chromium-os:15274 connect this test to the command line.
- bool bsdiff_allowed = true;
-
- if (utils::FileSize(new_root + path) > kMaxBsdiffDestinationSize)
- bsdiff_allowed = false;
-
- if (!bsdiff_allowed)
- LOG(INFO) << "bsdiff blacklisting: " << path;
-
- TEST_AND_RETURN_FALSE(DeltaDiffGenerator::ReadFileToDiff(old_path,
- new_root + path,
- chunk_offset,
- chunk_size,
- bsdiff_allowed,
- &data,
- &operation,
- true));
-
- // Check if the operation writes nothing.
- if (operation.dst_extents_size() == 0) {
- if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
- LOG(INFO) << "Empty MOVE operation (" << new_root + path << "), skipping";
- return true;
- } else {
- LOG(ERROR) << "Empty non-MOVE operation";
- return false;
- }
- }
-
- // Write the data
- if (operation.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE) {
- operation.set_data_offset(*data_file_size);
- operation.set_data_length(data.size());
- }
-
- TEST_AND_RETURN_FALSE(utils::WriteAll(data_fd, data.data(), data.size()));
- *data_file_size += data.size();
-
- // Now, insert into graph and blocks vector
- Vertex::Index vertex = existing_vertex;
- if (vertex == Vertex::kInvalidIndex) {
- graph->resize(graph->size() + 1);
- vertex = graph->size() - 1;
- }
- (*graph)[vertex].op = operation;
- CHECK((*graph)[vertex].op.has_type());
- (*graph)[vertex].file_name = path;
- (*graph)[vertex].chunk_offset = chunk_offset;
- (*graph)[vertex].chunk_size = chunk_size;
-
- if (blocks)
- TEST_AND_RETURN_FALSE(DeltaDiffGenerator::AddInstallOpToBlocksVector(
- (*graph)[vertex].op,
- *graph,
- vertex,
- blocks));
- return true;
-}
-
// For each regular file within new_root, creates a node in the graph,
// determines the best way to compress it (REPLACE, REPLACE_BZ, COPY, BSDIFF),
// and writes any necessary data to the end of data_fd.
@@ -252,41 +161,22 @@
if (offset + size >= dst_size) {
size = -1; // Read through the end of the file.
}
- TEST_AND_RETURN_FALSE(DeltaReadFile(graph,
- Vertex::kInvalidIndex,
- blocks,
- (should_diff_from_source ?
- old_root :
- kEmptyPath),
- new_root,
- fs_iter.GetPartialPath(),
- offset,
- size,
- data_fd,
- data_file_size));
+ TEST_AND_RETURN_FALSE(DeltaDiffGenerator::DeltaReadFile(
+ graph,
+ Vertex::kInvalidIndex,
+ blocks,
+ (should_diff_from_source ? old_root : kEmptyPath),
+ new_root,
+ fs_iter.GetPartialPath(),
+ offset,
+ size,
+ data_fd,
+ data_file_size));
}
}
return true;
}
-// This class allocates non-existent temp blocks, starting from
-// kTempBlockStart. Other code is responsible for converting these
-// temp blocks into real blocks, as the client can't read or write to
-// these blocks.
-class DummyExtentAllocator {
- public:
- DummyExtentAllocator() : next_block_(kTempBlockStart) {}
- vector<Extent> Allocate(const uint64_t block_count) {
- vector<Extent> ret(1);
- ret[0].set_start_block(next_block_);
- ret[0].set_num_blocks(block_count);
- next_block_ += block_count;
- return ret;
- }
- private:
- uint64_t next_block_;
-};
-
// Reads blocks from image_path that are not yet marked as being written in the
// blocks array. These blocks that remain are either unchanged files or
// non-file-data blocks. We compare each of them to the old image, and compress
@@ -486,12 +376,6 @@
}
}
-void CheckGraph(const Graph& graph) {
- for (const Vertex& v : graph) {
- CHECK(v.op.has_type());
- }
-}
-
// Delta compresses a kernel partition |new_kernel_part| with knowledge of the
// old kernel partition |old_kernel_part|. If |old_kernel_part| is an empty
// string, generates a full update of the partition.
@@ -704,6 +588,91 @@
} // namespace
+void DeltaDiffGenerator::CheckGraph(const Graph& graph) {
+ for (const Vertex& v : graph) {
+ CHECK(v.op.has_type());
+ }
+}
+
+bool DeltaDiffGenerator::DeltaReadFile(Graph* graph,
+ Vertex::Index existing_vertex,
+ vector<Block>* blocks,
+ const string& old_root,
+ const string& new_root,
+ const string& path, // within new_root
+ off_t chunk_offset,
+ off_t chunk_size,
+ int data_fd,
+ off_t* data_file_size) {
+ chromeos::Blob data;
+ DeltaArchiveManifest_InstallOperation operation;
+
+ string old_path = (old_root == kEmptyPath) ? kEmptyPath :
+ old_root + path;
+
+ // If bsdiff breaks again, blacklist the problem file by using:
+ // bsdiff_allowed = (path != "/foo/bar")
+ //
+ // TODO(dgarrett): chromium-os:15274 connect this test to the command line.
+ bool bsdiff_allowed = true;
+
+ if (utils::FileSize(new_root + path) > kMaxBsdiffDestinationSize)
+ bsdiff_allowed = false;
+
+ if (!bsdiff_allowed)
+ LOG(INFO) << "bsdiff blacklisting: " << path;
+
+ TEST_AND_RETURN_FALSE(DeltaDiffGenerator::ReadFileToDiff(old_path,
+ new_root + path,
+ chunk_offset,
+ chunk_size,
+ bsdiff_allowed,
+ &data,
+ &operation,
+ true));
+
+ // Check if the operation writes nothing.
+ if (operation.dst_extents_size() == 0) {
+ if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+ LOG(INFO) << "Empty MOVE operation (" << new_root + path << "), skipping";
+ return true;
+ } else {
+ LOG(ERROR) << "Empty non-MOVE operation";
+ return false;
+ }
+ }
+
+ // Write the data
+ if (operation.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+ operation.set_data_offset(*data_file_size);
+ operation.set_data_length(data.size());
+ }
+
+ TEST_AND_RETURN_FALSE(utils::WriteAll(data_fd, data.data(), data.size()));
+ *data_file_size += data.size();
+
+ // Now, insert into graph and blocks vector
+ Vertex::Index vertex = existing_vertex;
+ if (vertex == Vertex::kInvalidIndex) {
+ graph->resize(graph->size() + 1);
+ vertex = graph->size() - 1;
+ }
+ (*graph)[vertex].op = operation;
+ CHECK((*graph)[vertex].op.has_type());
+ (*graph)[vertex].file_name = path;
+ (*graph)[vertex].chunk_offset = chunk_offset;
+ (*graph)[vertex].chunk_size = chunk_size;
+
+ if (blocks)
+ TEST_AND_RETURN_FALSE(InplaceGenerator::AddInstallOpToBlocksVector(
+ (*graph)[vertex].op,
+ *graph,
+ vertex,
+ blocks));
+ return true;
+}
+
+
bool DeltaDiffGenerator::ReadFileToDiff(
const string& old_filename,
const string& new_filename,
@@ -899,139 +868,6 @@
return true;
}
-namespace {
-
-// Takes a collection (vector or RepeatedPtrField) of Extent and
-// returns a vector of the blocks referenced, in order.
-template<typename T>
-vector<uint64_t> ExpandExtents(const T& extents) {
- 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);
- if (extent.start_block() == kSparseHole) {
- ret.resize(ret.size() + extent.num_blocks(), kSparseHole);
- } else {
- for (uint64_t block = extent.start_block();
- block < (extent.start_block() + extent.num_blocks()); block++) {
- ret.push_back(block);
- }
- }
- }
- return ret;
-}
-
-// Takes a vector of blocks and returns an equivalent vector of Extent
-// objects.
-vector<Extent> CompressExtents(const vector<uint64_t>& blocks) {
- vector<Extent> new_extents;
- for (uint64_t block : blocks) {
- graph_utils::AppendBlockToExtents(&new_extents, block);
- }
- return new_extents;
-}
-
-} // namespace
-
-void DeltaDiffGenerator::SubstituteBlocks(
- Vertex* vertex,
- const vector<Extent>& remove_extents,
- const vector<Extent>& replace_extents) {
- // First, expand out the blocks that op reads from
- vector<uint64_t> read_blocks = ExpandExtents(vertex->op.src_extents());
- {
- // Expand remove_extents and replace_extents
- vector<uint64_t> remove_extents_expanded =
- ExpandExtents(remove_extents);
- vector<uint64_t> replace_extents_expanded =
- ExpandExtents(replace_extents);
- CHECK_EQ(remove_extents_expanded.size(), replace_extents_expanded.size());
- map<uint64_t, uint64_t> conversion;
- for (vector<uint64_t>::size_type i = 0;
- i < replace_extents_expanded.size(); i++) {
- conversion[remove_extents_expanded[i]] = replace_extents_expanded[i];
- }
- utils::ApplyMap(&read_blocks, conversion);
- for (auto& edge_prop_pair : vertex->out_edges) {
- vector<uint64_t> write_before_deps_expanded =
- ExpandExtents(edge_prop_pair.second.write_extents);
- utils::ApplyMap(&write_before_deps_expanded, conversion);
- edge_prop_pair.second.write_extents =
- CompressExtents(write_before_deps_expanded);
- }
- }
- // Convert read_blocks back to extents
- vertex->op.clear_src_extents();
- vector<Extent> new_extents = CompressExtents(read_blocks);
- DeltaDiffGenerator::StoreExtents(new_extents,
- vertex->op.mutable_src_extents());
-}
-
-bool DeltaDiffGenerator::CutEdges(Graph* graph,
- const set<Edge>& edges,
- vector<CutEdgeVertexes>* out_cuts) {
- DummyExtentAllocator scratch_allocator;
- vector<CutEdgeVertexes> cuts;
- cuts.reserve(edges.size());
-
- uint64_t scratch_blocks_used = 0;
- for (const Edge& edge : edges) {
- cuts.resize(cuts.size() + 1);
- vector<Extent> old_extents =
- (*graph)[edge.first].out_edges[edge.second].extents;
- // Choose some scratch space
- scratch_blocks_used += graph_utils::EdgeWeight(*graph, edge);
- cuts.back().tmp_extents =
- scratch_allocator.Allocate(graph_utils::EdgeWeight(*graph, edge));
- // create vertex to copy original->scratch
- cuts.back().new_vertex = graph->size();
- graph->resize(graph->size() + 1);
- cuts.back().old_src = edge.first;
- cuts.back().old_dst = edge.second;
-
- EdgeProperties& cut_edge_properties =
- (*graph)[edge.first].out_edges.find(edge.second)->second;
-
- // This should never happen, as we should only be cutting edges between
- // real file nodes, and write-before relationships are created from
- // a real file node to a temp copy node:
- CHECK(cut_edge_properties.write_extents.empty())
- << "Can't cut edge that has write-before relationship.";
-
- // make node depend on the copy operation
- (*graph)[edge.first].out_edges.insert(make_pair(graph->size() - 1,
- cut_edge_properties));
-
- // Set src/dst extents and other proto variables for copy operation
- graph->back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
- DeltaDiffGenerator::StoreExtents(
- cut_edge_properties.extents,
- graph->back().op.mutable_src_extents());
- DeltaDiffGenerator::StoreExtents(cuts.back().tmp_extents,
- graph->back().op.mutable_dst_extents());
- graph->back().op.set_src_length(
- graph_utils::EdgeWeight(*graph, edge) * kBlockSize);
- graph->back().op.set_dst_length(graph->back().op.src_length());
-
- // make the dest node read from the scratch space
- DeltaDiffGenerator::SubstituteBlocks(
- &((*graph)[edge.second]),
- (*graph)[edge.first].out_edges[edge.second].extents,
- cuts.back().tmp_extents);
-
- // delete the old edge
- CHECK_EQ(static_cast<Graph::size_type>(1),
- (*graph)[edge.first].out_edges.erase(edge.second));
-
- // Add an edge from dst to copy operation
- EdgeProperties write_before_edge_properties;
- write_before_edge_properties.write_extents = cuts.back().tmp_extents;
- (*graph)[edge.second].out_edges.insert(
- make_pair(graph->size() - 1, write_before_edge_properties));
- }
- out_cuts->swap(cuts);
- return true;
-}
-
// Stores all Extents in 'extents' into 'out'.
void DeltaDiffGenerator::StoreExtents(
const vector<Extent>& extents,
@@ -1042,274 +878,6 @@
}
}
-// Creates all the edges for the graph. Writers of a block point to
-// readers of the same block. This is because for an edge A->B, B
-// must complete before A executes.
-void DeltaDiffGenerator::CreateEdges(Graph* graph,
- const vector<Block>& blocks) {
- for (vector<Block>::size_type i = 0; i < blocks.size(); i++) {
- // Blocks with both a reader and writer get an edge
- if (blocks[i].reader == Vertex::kInvalidIndex ||
- blocks[i].writer == Vertex::kInvalidIndex)
- continue;
- // Don't have a node depend on itself
- if (blocks[i].reader == blocks[i].writer)
- continue;
- // See if there's already an edge we can add onto
- Vertex::EdgeMap::iterator edge_it =
- (*graph)[blocks[i].writer].out_edges.find(blocks[i].reader);
- if (edge_it == (*graph)[blocks[i].writer].out_edges.end()) {
- // No existing edge. Create one
- (*graph)[blocks[i].writer].out_edges.insert(
- make_pair(blocks[i].reader, EdgeProperties()));
- 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);
- }
-}
-
-namespace {
-
-class SortCutsByTopoOrderLess {
- public:
- explicit SortCutsByTopoOrderLess(
- const vector<vector<Vertex::Index>::size_type>& table)
- : table_(table) {}
- bool operator()(const CutEdgeVertexes& a, const CutEdgeVertexes& b) {
- return table_[a.old_dst] < table_[b.old_dst];
- }
- private:
- const vector<vector<Vertex::Index>::size_type>& table_;
-};
-
-} // namespace
-
-void DeltaDiffGenerator::GenerateReverseTopoOrderMap(
- const vector<Vertex::Index>& op_indexes,
- vector<vector<Vertex::Index>::size_type>* reverse_op_indexes) {
- vector<vector<Vertex::Index>::size_type> table(op_indexes.size());
- for (vector<Vertex::Index>::size_type i = 0, e = op_indexes.size();
- i != e; ++i) {
- Vertex::Index node = op_indexes[i];
- if (table.size() < (node + 1)) {
- table.resize(node + 1);
- }
- table[node] = i;
- }
- reverse_op_indexes->swap(table);
-}
-
-void DeltaDiffGenerator::SortCutsByTopoOrder(
- const vector<Vertex::Index>& op_indexes,
- vector<CutEdgeVertexes>* cuts) {
- // first, make a reverse lookup table.
- vector<vector<Vertex::Index>::size_type> table;
- GenerateReverseTopoOrderMap(op_indexes, &table);
- SortCutsByTopoOrderLess less(table);
- sort(cuts->begin(), cuts->end(), less);
-}
-
-void DeltaDiffGenerator::MoveFullOpsToBack(Graph* graph,
- vector<Vertex::Index>* op_indexes) {
- vector<Vertex::Index> ret;
- vector<Vertex::Index> full_ops;
- ret.reserve(op_indexes->size());
- for (vector<Vertex::Index>::size_type i = 0, e = op_indexes->size(); i != e;
- ++i) {
- DeltaArchiveManifest_InstallOperation_Type type =
- (*graph)[(*op_indexes)[i]].op.type();
- if (type == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
- type == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
- full_ops.push_back((*op_indexes)[i]);
- } else {
- ret.push_back((*op_indexes)[i]);
- }
- }
- LOG(INFO) << "Stats: " << full_ops.size() << " full ops out of "
- << (full_ops.size() + ret.size()) << " total ops.";
- ret.insert(ret.end(), full_ops.begin(), full_ops.end());
- op_indexes->swap(ret);
-}
-
-namespace {
-
-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);
- uint64_t start = extent.start_block();
- uint64_t num = extent.num_blocks();
- if (start == kSparseHole)
- continue;
- if (start >= kTempBlockStart ||
- (start + num) >= kTempBlockStart) {
- LOG(ERROR) << "temp block!";
- LOG(ERROR) << "start: " << start << ", num: " << num;
- LOG(ERROR) << "kTempBlockStart: " << kTempBlockStart;
- LOG(ERROR) << "returning true";
- return true;
- }
- // check for wrap-around, which would be a bug:
- CHECK(start <= (start + num));
- }
- return false;
-}
-
-// Converts the cuts, which must all have the same |old_dst| member,
-// to full. It does this by converting the |old_dst| to REPLACE or
-// REPLACE_BZ, dropping all incoming edges to |old_dst|, and marking
-// all temp nodes invalid.
-bool ConvertCutsToFull(
- Graph* graph,
- const string& new_root,
- int data_fd,
- off_t* data_file_size,
- vector<Vertex::Index>* op_indexes,
- vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
- const vector<CutEdgeVertexes>& cuts) {
- CHECK(!cuts.empty());
- set<Vertex::Index> deleted_nodes;
- for (const CutEdgeVertexes& cut : cuts) {
- TEST_AND_RETURN_FALSE(DeltaDiffGenerator::ConvertCutToFullOp(
- graph,
- cut,
- new_root,
- data_fd,
- data_file_size));
- deleted_nodes.insert(cut.new_vertex);
- }
- deleted_nodes.insert(cuts[0].old_dst);
-
- vector<Vertex::Index> new_op_indexes;
- new_op_indexes.reserve(op_indexes->size());
- for (Vertex::Index vertex_index : *op_indexes) {
- if (utils::SetContainsKey(deleted_nodes, vertex_index))
- continue;
- new_op_indexes.push_back(vertex_index);
- }
- new_op_indexes.push_back(cuts[0].old_dst);
- op_indexes->swap(new_op_indexes);
- DeltaDiffGenerator::GenerateReverseTopoOrderMap(*op_indexes,
- reverse_op_indexes);
- return true;
-}
-
-// Tries to assign temp blocks for a collection of cuts, all of which share
-// the same old_dst member. If temp blocks can't be found, old_dst will be
-// converted to a REPLACE or REPLACE_BZ operation. Returns true on success,
-// which can happen even if blocks are converted to full. Returns false
-// on exceptional error cases.
-bool AssignBlockForAdjoiningCuts(
- Graph* graph,
- const string& new_root,
- int data_fd,
- off_t* data_file_size,
- vector<Vertex::Index>* op_indexes,
- vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
- const vector<CutEdgeVertexes>& cuts) {
- CHECK(!cuts.empty());
- const Vertex::Index old_dst = cuts[0].old_dst;
- // Calculate # of blocks needed
- uint64_t blocks_needed = 0;
- vector<uint64_t> cuts_blocks_needed(cuts.size());
- for (vector<CutEdgeVertexes>::size_type i = 0; i < cuts.size(); ++i) {
- uint64_t cut_blocks_needed = 0;
- for (const Extent& extent : cuts[i].tmp_extents) {
- cut_blocks_needed += extent.num_blocks();
- }
- blocks_needed += cut_blocks_needed;
- cuts_blocks_needed[i] = cut_blocks_needed;
- }
-
- // Find enough blocks
- ExtentRanges scratch_ranges;
- // Each block that's supplying temp blocks and the corresponding blocks:
- typedef vector<pair<Vertex::Index, ExtentRanges>> SupplierVector;
- SupplierVector block_suppliers;
- uint64_t scratch_blocks_found = 0;
- for (vector<Vertex::Index>::size_type i = (*reverse_op_indexes)[old_dst] + 1,
- e = op_indexes->size(); i < e; ++i) {
- Vertex::Index test_node = (*op_indexes)[i];
- if (!(*graph)[test_node].valid)
- continue;
- // See if this node has sufficient blocks
- ExtentRanges ranges;
- ranges.AddRepeatedExtents((*graph)[test_node].op.dst_extents());
- ranges.SubtractExtent(ExtentForRange(
- kTempBlockStart, kSparseHole - kTempBlockStart));
- ranges.SubtractRepeatedExtents((*graph)[test_node].op.src_extents());
- // For now, for simplicity, subtract out all blocks in read-before
- // dependencies.
- for (Vertex::EdgeMap::const_iterator edge_i =
- (*graph)[test_node].out_edges.begin(),
- edge_e = (*graph)[test_node].out_edges.end();
- edge_i != edge_e; ++edge_i) {
- ranges.SubtractExtents(edge_i->second.extents);
- }
- if (ranges.blocks() == 0)
- continue;
-
- if (ranges.blocks() + scratch_blocks_found > blocks_needed) {
- // trim down ranges
- vector<Extent> new_ranges = ranges.GetExtentsForBlockCount(
- blocks_needed - scratch_blocks_found);
- ranges = ExtentRanges();
- ranges.AddExtents(new_ranges);
- }
- scratch_ranges.AddRanges(ranges);
- block_suppliers.push_back(make_pair(test_node, ranges));
- scratch_blocks_found += ranges.blocks();
- if (scratch_ranges.blocks() >= blocks_needed)
- break;
- }
- if (scratch_ranges.blocks() < blocks_needed) {
- LOG(INFO) << "Unable to find sufficient scratch";
- TEST_AND_RETURN_FALSE(ConvertCutsToFull(graph,
- new_root,
- data_fd,
- data_file_size,
- op_indexes,
- reverse_op_indexes,
- cuts));
- return true;
- }
- // Use the scratch we found
- TEST_AND_RETURN_FALSE(scratch_ranges.blocks() == scratch_blocks_found);
-
- // Make all the suppliers depend on this node
- for (const auto& index_range_pair : block_suppliers) {
- graph_utils::AddReadBeforeDepExtents(
- &(*graph)[index_range_pair.first],
- old_dst,
- index_range_pair.second.GetExtentsForBlockCount(
- index_range_pair.second.blocks()));
- }
-
- // Replace temp blocks in each cut
- for (vector<CutEdgeVertexes>::size_type i = 0; i < cuts.size(); ++i) {
- const CutEdgeVertexes& cut = cuts[i];
- vector<Extent> real_extents =
- scratch_ranges.GetExtentsForBlockCount(cuts_blocks_needed[i]);
- scratch_ranges.SubtractExtents(real_extents);
-
- // Fix the old dest node w/ the real blocks
- DeltaDiffGenerator::SubstituteBlocks(&(*graph)[old_dst],
- cut.tmp_extents,
- real_extents);
-
- // Fix the new node w/ the real blocks. Since the new node is just a
- // copy operation, we can replace all the dest extents w/ the real
- // blocks.
- DeltaArchiveManifest_InstallOperation *op = &(*graph)[cut.new_vertex].op;
- op->clear_dst_extents();
- DeltaDiffGenerator::StoreExtents(real_extents, op->mutable_dst_extents());
- }
- return true;
-}
-
-} // namespace
-
// Returns true if |op| is a no-op operation that doesn't do any useful work
// (e.g., a move operation that copies blocks onto themselves).
bool DeltaDiffGenerator::IsNoopOperation(
@@ -1318,84 +886,6 @@
ExpandExtents(op.src_extents()) == ExpandExtents(op.dst_extents()));
}
-bool DeltaDiffGenerator::AssignTempBlocks(
- Graph* graph,
- const string& new_root,
- int data_fd,
- off_t* data_file_size,
- vector<Vertex::Index>* op_indexes,
- vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
- const vector<CutEdgeVertexes>& cuts) {
- CHECK(!cuts.empty());
-
- // group of cuts w/ the same old_dst:
- vector<CutEdgeVertexes> cuts_group;
-
- for (vector<CutEdgeVertexes>::size_type i = cuts.size() - 1, e = 0;
- true ; --i) {
- LOG(INFO) << "Fixing temp blocks in cut " << i
- << ": old dst: " << cuts[i].old_dst << " new vertex: "
- << cuts[i].new_vertex << " path: "
- << (*graph)[cuts[i].old_dst].file_name;
-
- if (cuts_group.empty() || (cuts_group[0].old_dst == cuts[i].old_dst)) {
- cuts_group.push_back(cuts[i]);
- } else {
- CHECK(!cuts_group.empty());
- TEST_AND_RETURN_FALSE(AssignBlockForAdjoiningCuts(graph,
- new_root,
- data_fd,
- data_file_size,
- op_indexes,
- reverse_op_indexes,
- cuts_group));
- cuts_group.clear();
- cuts_group.push_back(cuts[i]);
- }
-
- if (i == e) {
- // break out of for() loop
- break;
- }
- }
- CHECK(!cuts_group.empty());
- TEST_AND_RETURN_FALSE(AssignBlockForAdjoiningCuts(graph,
- new_root,
- data_fd,
- data_file_size,
- op_indexes,
- reverse_op_indexes,
- cuts_group));
- return true;
-}
-
-bool DeltaDiffGenerator::NoTempBlocksRemain(const Graph& graph) {
- size_t idx = 0;
- for (Graph::const_iterator it = graph.begin(), e = graph.end(); it != e;
- ++it, ++idx) {
- if (!it->valid)
- continue;
- const DeltaArchiveManifest_InstallOperation& op = it->op;
- if (TempBlocksExistInExtents(op.dst_extents()) ||
- TempBlocksExistInExtents(op.src_extents())) {
- LOG(INFO) << "bad extents in node " << idx;
- LOG(INFO) << "so yeah";
- return false;
- }
-
- // Check out-edges:
- for (const auto& edge_prop_pair : it->out_edges) {
- if (TempBlocksExistInExtents(edge_prop_pair.second.extents) ||
- TempBlocksExistInExtents(edge_prop_pair.second.write_extents)) {
- LOG(INFO) << "bad out edge in node " << idx;
- LOG(INFO) << "so yeah";
- return false;
- }
- }
- }
- return true;
-}
-
bool DeltaDiffGenerator::ReorderDataBlobs(
DeltaArchiveManifest* manifest,
const string& data_blobs_path,
@@ -1451,120 +941,6 @@
return true;
}
-bool DeltaDiffGenerator::ConvertCutToFullOp(Graph* graph,
- const CutEdgeVertexes& cut,
- const string& new_root,
- int data_fd,
- off_t* data_file_size) {
- // Drop all incoming edges, keep all outgoing edges
-
- // Keep all outgoing edges
- if ((*graph)[cut.old_dst].op.type() !=
- DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ &&
- (*graph)[cut.old_dst].op.type() !=
- DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
- Vertex::EdgeMap out_edges = (*graph)[cut.old_dst].out_edges;
- graph_utils::DropWriteBeforeDeps(&out_edges);
-
- TEST_AND_RETURN_FALSE(DeltaReadFile(graph,
- cut.old_dst,
- nullptr,
- kEmptyPath,
- new_root,
- (*graph)[cut.old_dst].file_name,
- (*graph)[cut.old_dst].chunk_offset,
- (*graph)[cut.old_dst].chunk_size,
- data_fd,
- data_file_size));
-
- (*graph)[cut.old_dst].out_edges = out_edges;
-
- // Right now we don't have doubly-linked edges, so we have to scan
- // the whole graph.
- graph_utils::DropIncomingEdgesTo(graph, cut.old_dst);
- }
-
- // Delete temp node
- (*graph)[cut.old_src].out_edges.erase(cut.new_vertex);
- CHECK((*graph)[cut.old_dst].out_edges.find(cut.new_vertex) ==
- (*graph)[cut.old_dst].out_edges.end());
- (*graph)[cut.new_vertex].valid = false;
- LOG(INFO) << "marked node invalid: " << cut.new_vertex;
- return true;
-}
-
-bool DeltaDiffGenerator::ConvertGraphToDag(Graph* graph,
- const string& new_root,
- int fd,
- off_t* data_file_size,
- vector<Vertex::Index>* final_order,
- Vertex::Index scratch_vertex) {
- CycleBreaker cycle_breaker;
- LOG(INFO) << "Finding cycles...";
- set<Edge> cut_edges;
- cycle_breaker.BreakCycles(*graph, &cut_edges);
- LOG(INFO) << "done finding cycles";
- CheckGraph(*graph);
-
- // Calculate number of scratch blocks needed
-
- LOG(INFO) << "Cutting cycles...";
- vector<CutEdgeVertexes> cuts;
- TEST_AND_RETURN_FALSE(CutEdges(graph, cut_edges, &cuts));
- LOG(INFO) << "done cutting cycles";
- LOG(INFO) << "There are " << cuts.size() << " cuts.";
- CheckGraph(*graph);
-
- LOG(INFO) << "Creating initial topological order...";
- TopologicalSort(*graph, final_order);
- LOG(INFO) << "done with initial topo order";
- CheckGraph(*graph);
-
- LOG(INFO) << "Moving full ops to the back";
- MoveFullOpsToBack(graph, final_order);
- LOG(INFO) << "done moving full ops to back";
-
- vector<vector<Vertex::Index>::size_type> inverse_final_order;
- GenerateReverseTopoOrderMap(*final_order, &inverse_final_order);
-
- SortCutsByTopoOrder(*final_order, &cuts);
-
- if (!cuts.empty())
- TEST_AND_RETURN_FALSE(AssignTempBlocks(graph,
- new_root,
- fd,
- data_file_size,
- final_order,
- &inverse_final_order,
- cuts));
- LOG(INFO) << "Making sure all temp blocks have been allocated";
-
- // Remove the scratch node, if any
- if (scratch_vertex != Vertex::kInvalidIndex) {
- final_order->erase(final_order->begin() +
- inverse_final_order[scratch_vertex]);
- (*graph)[scratch_vertex].valid = false;
- GenerateReverseTopoOrderMap(*final_order, &inverse_final_order);
- }
-
- graph_utils::DumpGraph(*graph);
- CHECK(NoTempBlocksRemain(*graph));
- LOG(INFO) << "done making sure all temp blocks are allocated";
- return true;
-}
-
-void DeltaDiffGenerator::CreateScratchNode(uint64_t start_block,
- uint64_t num_blocks,
- Vertex* vertex) {
- vertex->file_name = "<scratch>";
- vertex->op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
- vertex->op.set_data_offset(0);
- vertex->op.set_data_length(0);
- Extent* extent = vertex->op.add_dst_extents();
- extent->set_start_block(start_block);
- extent->set_num_blocks(num_blocks);
-}
-
bool DeltaDiffGenerator::GenerateDeltaUpdateFile(
const string& old_root,
const string& old_image,
@@ -1686,9 +1062,10 @@
if (blocks.size() < (rootfs_partition_size / kBlockSize)) {
scratch_vertex = graph.size();
graph.resize(graph.size() + 1);
- CreateScratchNode(blocks.size(),
- (rootfs_partition_size / kBlockSize) - blocks.size(),
- &graph.back());
+ InplaceGenerator::CreateScratchNode(
+ blocks.size(),
+ (rootfs_partition_size / kBlockSize) - blocks.size(),
+ &graph.back());
}
// Read kernel partition
@@ -1702,16 +1079,17 @@
CheckGraph(graph);
LOG(INFO) << "Creating edges...";
- CreateEdges(&graph, blocks);
+ InplaceGenerator::CreateEdges(&graph, blocks);
LOG(INFO) << "Done creating edges";
CheckGraph(graph);
- TEST_AND_RETURN_FALSE(ConvertGraphToDag(&graph,
- new_root,
- fd,
- &data_file_size,
- &final_order,
- scratch_vertex));
+ TEST_AND_RETURN_FALSE(InplaceGenerator::ConvertGraphToDag(
+ &graph,
+ new_root,
+ fd,
+ &data_file_size,
+ &final_order,
+ scratch_vertex));
} else {
// Full update
off_t new_image_size =
@@ -1890,55 +1268,6 @@
return true;
}
-// The |blocks| vector contains a reader and writer for each block on the
-// filesystem that's being in-place updated. We populate the reader/writer
-// fields of |blocks| by calling this function.
-// For each block in |operation| that is read or written, find that block
-// in |blocks| and set the reader/writer field to the vertex passed.
-// |graph| is not strictly necessary, but useful for printing out
-// error messages.
-bool DeltaDiffGenerator::AddInstallOpToBlocksVector(
- const DeltaArchiveManifest_InstallOperation& operation,
- const Graph& graph,
- Vertex::Index vertex,
- vector<Block>* blocks) {
- // See if this is already present.
- TEST_AND_RETURN_FALSE(operation.dst_extents_size() > 0);
-
- enum BlockField { READER = 0, WRITER, BLOCK_FIELD_COUNT };
- for (int field = READER; field < BLOCK_FIELD_COUNT; field++) {
- const int extents_size =
- (field == READER) ? operation.src_extents_size() :
- operation.dst_extents_size();
- const char* past_participle = (field == READER) ? "read" : "written";
- const google::protobuf::RepeatedPtrField<Extent>& extents =
- (field == READER) ? operation.src_extents() : operation.dst_extents();
- Vertex::Index Block::*access_type =
- (field == READER) ? &Block::reader : &Block::writer;
-
- for (int i = 0; i < extents_size; i++) {
- const Extent& extent = extents.Get(i);
- if (extent.start_block() == kSparseHole) {
- // Hole in sparse file. skip
- continue;
- }
- for (uint64_t block = extent.start_block();
- block < (extent.start_block() + extent.num_blocks()); block++) {
- if ((*blocks)[block].*access_type != Vertex::kInvalidIndex) {
- LOG(FATAL) << "Block " << block << " is already "
- << past_participle << " by "
- << (*blocks)[block].*access_type << "("
- << graph[(*blocks)[block].*access_type].file_name
- << ") and also " << vertex << "("
- << graph[vertex].file_name << ")";
- }
- (*blocks)[block].*access_type = vertex;
- }
- }
- }
- return true;
-}
-
void DeltaDiffGenerator::AddSignatureOp(uint64_t signature_blob_offset,
uint64_t signature_blob_length,
DeltaArchiveManifest* manifest) {
@@ -1960,6 +1289,4 @@
kBlockSize);
}
-const char* const kBsdiffPath = "bsdiff";
-
}; // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_generator.h b/payload_generator/delta_diff_generator.h
index 8fc84eb..a28e1a8 100644
--- a/payload_generator/delta_diff_generator.h
+++ b/payload_generator/delta_diff_generator.h
@@ -12,7 +12,9 @@
#include <base/macros.h>
#include <chromeos/secure_blob.h>
+#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/update_metadata.pb.h"
// There is one function in DeltaDiffGenerator of importance to users
@@ -24,6 +26,10 @@
namespace chromeos_update_engine {
+extern const char* const kEmptyPath;
+extern const size_t kBlockSize;
+extern const size_t kRootFSPartitionSize;
+
// This struct stores all relevant info for an edge that is cut between
// nodes old_src -> old_dst by creating new vertex new_vertex. The new
// relationship is:
@@ -88,21 +94,24 @@
// These functions are public so that the unit tests can access them:
- // Takes a graph, which is not a DAG, which represents the files just
- // read from disk, and converts it into a DAG by breaking all cycles
- // and finding temp space to resolve broken edges.
- // The final order of the nodes is given in |final_order|
- // Some files may need to be reread from disk, thus |fd| and
- // |data_file_size| are be passed.
- // If |scratch_vertex| is not kInvalidIndex, removes it from
- // |final_order| before returning.
- // Returns true on success.
- static bool ConvertGraphToDag(Graph* graph,
- const std::string& new_root,
- int fd,
- off_t* data_file_size,
- std::vector<Vertex::Index>* final_order,
- Vertex::Index scratch_vertex);
+ // For a given regular file which must exist at new_root + path, and
+ // may exist at old_root + path, creates a new InstallOperation and
+ // adds it to the graph. Also, populates the |blocks| array as
+ // necessary, if |blocks| is non-null. Also, writes the data
+ // necessary to send the file down to the client into data_fd, which
+ // has length *data_file_size. *data_file_size is updated
+ // appropriately. If |existing_vertex| is no kInvalidIndex, use that
+ // rather than allocating a new vertex. Returns true on success.
+ static bool DeltaReadFile(Graph* graph,
+ Vertex::Index existing_vertex,
+ std::vector<Block>* blocks,
+ const std::string& old_root,
+ const std::string& new_root,
+ const std::string& path,
+ off_t chunk_offset,
+ off_t chunk_size,
+ int data_fd,
+ off_t* data_file_size);
// Reads old_filename (if it exists) and a new_filename and determines
// the smallest way to encode this file for the diff. It stores
@@ -123,62 +132,10 @@
DeltaArchiveManifest_InstallOperation* out_op,
bool gather_extents);
- // Creates a dummy REPLACE_BZ node in the given |vertex|. This can be used
- // to provide scratch space. The node writes |num_blocks| blocks starting at
- // |start_block|The node should be marked invalid before writing all nodes to
- // the output file.
- static void CreateScratchNode(uint64_t start_block,
- uint64_t num_blocks,
- Vertex* vertex);
-
- // Modifies blocks read by 'op' so that any blocks referred to by
- // 'remove_extents' are replaced with blocks from 'replace_extents'.
- // 'remove_extents' and 'replace_extents' must be the same number of blocks.
- // Blocks will be substituted in the order listed in the vectors.
- // E.g. if 'op' reads blocks 1, 2, 3, 4, 5, 6, 7, 8, remove_extents
- // contains blocks 6, 2, 3, 5, and replace blocks contains
- // 12, 13, 14, 15, then op will be changed to read from:
- // 1, 13, 14, 4, 15, 12, 7, 8
- static void SubstituteBlocks(Vertex* vertex,
- const std::vector<Extent>& remove_extents,
- const std::vector<Extent>& replace_extents);
-
- // Cuts 'edges' from 'graph' according to the AU algorithm. This means
- // for each edge A->B, remove the dependency that B occur before A.
- // Do this by creating a new operation X that copies from the blocks
- // specified by the edge's properties to temp space T. Modify B to read
- // from T rather than the blocks in the edge. Modify A to depend on X,
- // but not on B. Free space is found by looking in 'blocks'.
- // Returns true on success.
- static bool CutEdges(Graph* graph,
- const std::set<Edge>& edges,
- std::vector<CutEdgeVertexes>* out_cuts);
-
// Stores all Extents in 'extents' into 'out'.
static void StoreExtents(const std::vector<Extent>& extents,
google::protobuf::RepeatedPtrField<Extent>* out);
- // Creates all the edges for the graph. Writers of a block point to
- // readers of the same block. This is because for an edge A->B, B
- // must complete before A executes.
- static void CreateEdges(Graph* graph, const std::vector<Block>& blocks);
-
- // Given a topologically sorted graph |op_indexes| and |graph|, alters
- // |op_indexes| to move all the full operations to the end of the vector.
- // Full operations should not be depended on, so this is safe.
- static void MoveFullOpsToBack(Graph* graph,
- std::vector<Vertex::Index>* op_indexes);
-
- // Sorts the vector |cuts| by its |cuts[].old_dest| member. Order is
- // determined by the order of elements in op_indexes.
- static void SortCutsByTopoOrder(
- const std::vector<Vertex::Index>& op_indexes,
- std::vector<CutEdgeVertexes>* cuts);
-
- // Returns true iff there are no extents in the graph that refer to temp
- // blocks. Temp blocks are in the range [kTempBlockStart, kSparseHole).
- static bool NoTempBlocksRemain(const Graph& graph);
-
// Install operations in the manifest may reference data blobs, which
// are in data_blobs_path. This function creates a new data blobs file
// with the data blobs in the same order as the referencing install
@@ -199,41 +156,6 @@
static bool AddOperationHash(DeltaArchiveManifest_InstallOperation* op,
const chromeos::Blob& buf);
- // Handles allocation of temp blocks to a cut edge by converting the
- // dest node to a full op. This removes the need for temp blocks, but
- // comes at the cost of a worse compression ratio.
- // For example, say we have A->B->A. It would first be cut to form:
- // A->B->N<-A, where N copies blocks to temp space. If there are no
- // temp blocks, this function can be called to convert it to the form:
- // A->B. Now, A is a full operation.
- static bool ConvertCutToFullOp(Graph* graph,
- const CutEdgeVertexes& cut,
- const std::string& new_root,
- int data_fd,
- off_t* data_file_size);
-
- // Takes |op_indexes|, which is effectively a mapping from order in
- // which the op is performed -> graph vertex index, and produces the
- // reverse: a mapping from graph vertex index -> op_indexes index.
- static void GenerateReverseTopoOrderMap(
- const std::vector<Vertex::Index>& op_indexes,
- std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes);
-
- // Takes a |graph|, which has edges that must be cut, as listed in
- // |cuts|. Cuts the edges. Maintains a list in which the operations
- // will be performed (in |op_indexes|) and the reverse (in
- // |reverse_op_indexes|). Cutting edges requires scratch space, and
- // if insufficient scratch is found, the file is reread and will be
- // send down (either as REPLACE or REPLACE_BZ). Returns true on
- // success.
- static bool AssignTempBlocks(
- Graph* graph,
- const std::string& new_root,
- int data_fd,
- off_t* data_file_size,
- std::vector<Vertex::Index>* op_indexes,
- std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes,
- const std::vector<CutEdgeVertexes>& cuts);
// Returns true if |op| is a no-op operation that doesn't do any useful work
// (e.g., a move operation that copies blocks onto themselves).
@@ -249,33 +171,38 @@
const std::string& new_file,
chromeos::Blob* out);
- // The |blocks| vector contains a reader and writer for each block on the
- // filesystem that's being in-place updated. We populate the reader/writer
- // fields of |blocks| by calling this function.
- // For each block in |operation| that is read or written, find that block
- // in |blocks| and set the reader/writer field to the vertex passed.
- // |graph| is not strictly necessary, but useful for printing out
- // error messages.
- static bool AddInstallOpToBlocksVector(
- const DeltaArchiveManifest_InstallOperation& operation,
- const Graph& graph,
- Vertex::Index vertex,
- std::vector<DeltaDiffGenerator::Block>* blocks);
-
// Adds to |manifest| a dummy operation that points to a signature blob
// located at the specified offset/length.
static void AddSignatureOp(uint64_t signature_blob_offset,
uint64_t signature_blob_length,
DeltaArchiveManifest* manifest);
+ // Takes a collection (vector or RepeatedPtrField) of Extent and
+ // returns a vector of the blocks referenced, in order.
+ template<typename T>
+ 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);
+ if (extent.start_block() == kSparseHole) {
+ ret.resize(ret.size() + extent.num_blocks(), kSparseHole);
+ } else {
+ for (uint64_t block = extent.start_block();
+ block < (extent.start_block() + extent.num_blocks()); block++) {
+ ret.push_back(block);
+ }
+ }
+ }
+ return ret;
+ }
+
+ static void CheckGraph(const Graph& graph);
+
private:
// This should never be constructed.
DISALLOW_IMPLICIT_CONSTRUCTORS(DeltaDiffGenerator);
};
-extern const char* const kBsdiffPath;
-extern const size_t kRootFSPartitionSize;
-
}; // namespace chromeos_update_engine
#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_GENERATOR_H_
diff --git a/payload_generator/delta_diff_generator_unittest.cc b/payload_generator/delta_diff_generator_unittest.cc
index 88e1b75..d60aa79 100644
--- a/payload_generator/delta_diff_generator_unittest.cc
+++ b/payload_generator/delta_diff_generator_unittest.cc
@@ -23,7 +23,6 @@
#include "update_engine/delta_performer.h"
#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/extent_mapper.h"
#include "update_engine/payload_generator/graph_types.h"
#include "update_engine/payload_generator/graph_utils.h"
@@ -32,12 +31,9 @@
#include "update_engine/test_utils.h"
#include "update_engine/utils.h"
-using chromeos_update_engine::test_utils::FillWithData;
using chromeos_update_engine::test_utils::kRandomString;
-using chromeos_update_engine::test_utils::WriteFileVector;
using std::set;
using std::string;
-using std::stringstream;
using std::vector;
namespace chromeos_update_engine {
@@ -387,174 +383,6 @@
EXPECT_EQ(sizeof(kRandomString), op.dst_length());
}
-namespace {
-void AppendExtent(vector<Extent>* vect, uint64_t start, uint64_t length) {
- vect->resize(vect->size() + 1);
- vect->back().set_start_block(start);
- vect->back().set_num_blocks(length);
-}
-void OpAppendExtent(DeltaArchiveManifest_InstallOperation* op,
- uint64_t start,
- uint64_t length) {
- Extent* extent = op->add_src_extents();
- extent->set_start_block(start);
- extent->set_num_blocks(length);
-}
-} // namespace
-
-TEST_F(DeltaDiffGeneratorTest, SubstituteBlocksTest) {
- vector<Extent> remove_blocks;
- AppendExtent(&remove_blocks, 3, 3);
- AppendExtent(&remove_blocks, 7, 1);
- vector<Extent> replace_blocks;
- AppendExtent(&replace_blocks, 10, 2);
- AppendExtent(&replace_blocks, 13, 2);
- Vertex vertex;
- DeltaArchiveManifest_InstallOperation& op = vertex.op;
- OpAppendExtent(&op, 4, 3);
- OpAppendExtent(&op, kSparseHole, 4); // Sparse hole in file
- OpAppendExtent(&op, 3, 1);
- OpAppendExtent(&op, 7, 3);
-
- DeltaDiffGenerator::SubstituteBlocks(&vertex, remove_blocks, replace_blocks);
-
- EXPECT_EQ(7, op.src_extents_size());
- EXPECT_EQ(11, op.src_extents(0).start_block());
- EXPECT_EQ(1, op.src_extents(0).num_blocks());
- EXPECT_EQ(13, op.src_extents(1).start_block());
- EXPECT_EQ(1, op.src_extents(1).num_blocks());
- EXPECT_EQ(6, op.src_extents(2).start_block());
- EXPECT_EQ(1, op.src_extents(2).num_blocks());
- EXPECT_EQ(kSparseHole, op.src_extents(3).start_block());
- EXPECT_EQ(4, op.src_extents(3).num_blocks());
- EXPECT_EQ(10, op.src_extents(4).start_block());
- EXPECT_EQ(1, op.src_extents(4).num_blocks());
- EXPECT_EQ(14, op.src_extents(5).start_block());
- EXPECT_EQ(1, op.src_extents(5).num_blocks());
- EXPECT_EQ(8, op.src_extents(6).start_block());
- EXPECT_EQ(2, op.src_extents(6).num_blocks());
-}
-
-TEST_F(DeltaDiffGeneratorTest, CutEdgesTest) {
- Graph graph;
- vector<Block> blocks(9);
-
- // Create nodes in graph
- {
- graph.resize(graph.size() + 1);
- 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);
- DeltaDiffGenerator::StoreExtents(extents,
- graph.back().op.mutable_src_extents());
- blocks[3].reader = graph.size() - 1;
- blocks[5].reader = graph.size() - 1;
- blocks[7].reader = graph.size() - 1;
-
- // Writes to blocks 1, 2, 4
- extents.clear();
- graph_utils::AppendBlockToExtents(&extents, 1);
- graph_utils::AppendBlockToExtents(&extents, 2);
- graph_utils::AppendBlockToExtents(&extents, 4);
- DeltaDiffGenerator::StoreExtents(extents,
- graph.back().op.mutable_dst_extents());
- blocks[1].writer = graph.size() - 1;
- blocks[2].writer = graph.size() - 1;
- blocks[4].writer = graph.size() - 1;
- }
- {
- graph.resize(graph.size() + 1);
- 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);
- DeltaDiffGenerator::StoreExtents(extents,
- graph.back().op.mutable_src_extents());
- blocks[1].reader = graph.size() - 1;
- blocks[2].reader = graph.size() - 1;
- blocks[4].reader = graph.size() - 1;
-
- // Writes to blocks 3, 5, 6
- extents.clear();
- graph_utils::AppendBlockToExtents(&extents, 3);
- graph_utils::AppendBlockToExtents(&extents, 5);
- graph_utils::AppendBlockToExtents(&extents, 6);
- DeltaDiffGenerator::StoreExtents(extents,
- graph.back().op.mutable_dst_extents());
- blocks[3].writer = graph.size() - 1;
- blocks[5].writer = graph.size() - 1;
- blocks[6].writer = graph.size() - 1;
- }
-
- // Create edges
- DeltaDiffGenerator::CreateEdges(&graph, blocks);
-
- // Find cycles
- CycleBreaker cycle_breaker;
- set<Edge> cut_edges;
- cycle_breaker.BreakCycles(graph, &cut_edges);
-
- EXPECT_EQ(1, cut_edges.size());
- EXPECT_TRUE(cut_edges.end() != cut_edges.find(
- std::pair<Vertex::Index, Vertex::Index>(1, 0)));
-
- vector<CutEdgeVertexes> cuts;
- EXPECT_TRUE(DeltaDiffGenerator::CutEdges(&graph, cut_edges, &cuts));
-
- EXPECT_EQ(3, graph.size());
-
- // Check new node in graph:
- EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
- graph.back().op.type());
- EXPECT_EQ(2, graph.back().op.src_extents_size());
- EXPECT_EQ(1, graph.back().op.dst_extents_size());
- EXPECT_EQ(kTempBlockStart, graph.back().op.dst_extents(0).start_block());
- EXPECT_EQ(2, graph.back().op.dst_extents(0).num_blocks());
- EXPECT_TRUE(graph.back().out_edges.empty());
-
- // Check that old node reads from new blocks
- EXPECT_EQ(2, graph[0].op.src_extents_size());
- EXPECT_EQ(kTempBlockStart, graph[0].op.src_extents(0).start_block());
- EXPECT_EQ(2, graph[0].op.src_extents(0).num_blocks());
- EXPECT_EQ(7, graph[0].op.src_extents(1).start_block());
- EXPECT_EQ(1, graph[0].op.src_extents(1).num_blocks());
-
- // And that the old dst extents haven't changed
- EXPECT_EQ(2, graph[0].op.dst_extents_size());
- EXPECT_EQ(1, graph[0].op.dst_extents(0).start_block());
- EXPECT_EQ(2, graph[0].op.dst_extents(0).num_blocks());
- EXPECT_EQ(4, graph[0].op.dst_extents(1).start_block());
- EXPECT_EQ(1, graph[0].op.dst_extents(1).num_blocks());
-
- // Ensure it only depends on the next node and the new temp node
- EXPECT_EQ(2, graph[0].out_edges.size());
- EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(1));
- EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(graph.size() -
- 1));
-
- // Check second node has unchanged extents
- EXPECT_EQ(2, graph[1].op.src_extents_size());
- EXPECT_EQ(1, graph[1].op.src_extents(0).start_block());
- EXPECT_EQ(2, graph[1].op.src_extents(0).num_blocks());
- EXPECT_EQ(4, graph[1].op.src_extents(1).start_block());
- EXPECT_EQ(1, graph[1].op.src_extents(1).num_blocks());
-
- EXPECT_EQ(2, graph[1].op.dst_extents_size());
- EXPECT_EQ(3, graph[1].op.dst_extents(0).start_block());
- EXPECT_EQ(1, graph[1].op.dst_extents(0).num_blocks());
- EXPECT_EQ(5, graph[1].op.dst_extents(1).start_block());
- EXPECT_EQ(2, graph[1].op.dst_extents(1).num_blocks());
-
- // Ensure it only depends on the next node
- EXPECT_EQ(1, graph[1].out_edges.size());
- EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2));
-}
-
TEST_F(DeltaDiffGeneratorTest, ReorderBlobsTest) {
string orig_blobs;
EXPECT_TRUE(utils::MakeTempFile("ReorderBlobsTest.orig.XXXXXX", &orig_blobs,
@@ -594,395 +422,6 @@
unlink(new_blobs.c_str());
}
-TEST_F(DeltaDiffGeneratorTest, MoveFullOpsToBackTest) {
- Graph graph(4);
- graph[0].file_name = "A";
- graph[0].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
- graph[1].file_name = "B";
- graph[1].op.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
- graph[2].file_name = "C";
- graph[2].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
- graph[3].file_name = "D";
- graph[3].op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
-
- vector<Vertex::Index> vect(graph.size());
-
- for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) {
- vect[i] = i;
- }
- DeltaDiffGenerator::MoveFullOpsToBack(&graph, &vect);
- EXPECT_EQ(vect.size(), graph.size());
- EXPECT_EQ(graph[vect[0]].file_name, "B");
- EXPECT_EQ(graph[vect[1]].file_name, "D");
- EXPECT_EQ(graph[vect[2]].file_name, "A");
- EXPECT_EQ(graph[vect[3]].file_name, "C");
-}
-
-namespace {
-
-#define OP_BSDIFF DeltaArchiveManifest_InstallOperation_Type_BSDIFF
-#define OP_MOVE DeltaArchiveManifest_InstallOperation_Type_MOVE
-#define OP_REPLACE DeltaArchiveManifest_InstallOperation_Type_REPLACE
-#define OP_REPLACE_BZ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ
-
-void GenVertex(Vertex* out,
- const vector<Extent>& src_extents,
- const vector<Extent>& dst_extents,
- const string& path,
- DeltaArchiveManifest_InstallOperation_Type type) {
- out->op.set_type(type);
- out->file_name = path;
- DeltaDiffGenerator::StoreExtents(src_extents, out->op.mutable_src_extents());
- DeltaDiffGenerator::StoreExtents(dst_extents, out->op.mutable_dst_extents());
-}
-
-vector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) {
- return vector<Extent>(1, ExtentForRange(start_block, num_blocks));
-}
-
-EdgeProperties EdgeWithReadDep(const vector<Extent>& extents) {
- EdgeProperties ret;
- ret.extents = extents;
- return ret;
-}
-
-EdgeProperties EdgeWithWriteDep(const vector<Extent>& extents) {
- EdgeProperties ret;
- ret.write_extents = extents;
- return ret;
-}
-
-template<typename T>
-void DumpVect(const vector<T>& vect) {
- stringstream ss(stringstream::out);
- for (typename vector<T>::const_iterator it = vect.begin(), e = vect.end();
- it != e; ++it) {
- ss << *it << ", ";
- }
- LOG(INFO) << "{" << ss.str() << "}";
-}
-
-} // namespace
-
-TEST_F(DeltaDiffGeneratorTest, RunAsRootAssignTempBlocksTest) {
- Graph graph(9);
- const vector<Extent> empt; // empty
- const string kFilename = "/foo";
-
- // Some scratch space:
- GenVertex(&graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
- GenVertex(&graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
- GenVertex(&graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
-
- // A cycle that requires 10 blocks to break:
- GenVertex(&graph[3], VectOfExt(10, 11), VectOfExt(0, 9), "", OP_BSDIFF);
- graph[3].out_edges[4] = EdgeWithReadDep(VectOfExt(0, 9));
- GenVertex(&graph[4], VectOfExt(0, 9), VectOfExt(10, 11), "", OP_BSDIFF);
- graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
-
- // A cycle that requires 9 blocks to break:
- GenVertex(&graph[5], VectOfExt(40, 11), VectOfExt(30, 10), "", OP_BSDIFF);
- graph[5].out_edges[6] = EdgeWithReadDep(VectOfExt(30, 10));
- GenVertex(&graph[6], VectOfExt(30, 10), VectOfExt(40, 11), "", OP_BSDIFF);
- graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
-
- // A cycle that requires 40 blocks to break (which is too many):
- GenVertex(&graph[7],
- VectOfExt(120, 50),
- VectOfExt(60, 40),
- "",
- OP_BSDIFF);
- graph[7].out_edges[8] = EdgeWithReadDep(VectOfExt(60, 40));
- GenVertex(&graph[8],
- VectOfExt(60, 40),
- VectOfExt(120, 50),
- kFilename,
- OP_BSDIFF);
- graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
-
- graph_utils::DumpGraph(graph);
-
- vector<Vertex::Index> final_order;
-
-
- // Prepare the filesystem with the minimum required for this to work
- string temp_dir;
- EXPECT_TRUE(utils::MakeTempDirectory("AssignTempBlocksTest.XXXXXX",
- &temp_dir));
- ScopedDirRemover temp_dir_remover(temp_dir);
-
- const size_t kBlockSize = 4096;
- chromeos::Blob temp_data(kBlockSize * 50);
- FillWithData(&temp_data);
- EXPECT_TRUE(WriteFileVector(temp_dir + kFilename, temp_data));
- ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
-
- int fd;
- EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksTestData.XXXXXX",
- nullptr,
- &fd));
- ScopedFdCloser fd_closer(&fd);
- off_t data_file_size = 0;
-
-
- EXPECT_TRUE(DeltaDiffGenerator::ConvertGraphToDag(&graph,
- temp_dir,
- fd,
- &data_file_size,
- &final_order,
- Vertex::kInvalidIndex));
-
-
- Graph expected_graph(12);
- GenVertex(&expected_graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
- GenVertex(&expected_graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
- GenVertex(&expected_graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
- GenVertex(&expected_graph[3],
- VectOfExt(10, 11),
- VectOfExt(0, 9),
- "",
- OP_BSDIFF);
- expected_graph[3].out_edges[9] = EdgeWithReadDep(VectOfExt(0, 9));
- GenVertex(&expected_graph[4],
- VectOfExt(60, 9),
- VectOfExt(10, 11),
- "",
- OP_BSDIFF);
- expected_graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
- expected_graph[4].out_edges[9] = EdgeWithWriteDep(VectOfExt(60, 9));
- GenVertex(&expected_graph[5],
- VectOfExt(40, 11),
- VectOfExt(30, 10),
- "",
- OP_BSDIFF);
- expected_graph[5].out_edges[10] = EdgeWithReadDep(VectOfExt(30, 10));
-
- GenVertex(&expected_graph[6],
- VectOfExt(60, 10),
- VectOfExt(40, 11),
- "",
- OP_BSDIFF);
- expected_graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
- expected_graph[6].out_edges[10] = EdgeWithWriteDep(VectOfExt(60, 10));
-
- GenVertex(&expected_graph[7],
- VectOfExt(120, 50),
- VectOfExt(60, 40),
- "",
- OP_BSDIFF);
- expected_graph[7].out_edges[6] = EdgeWithReadDep(VectOfExt(60, 10));
-
- GenVertex(&expected_graph[8], empt, VectOfExt(0, 50), "/foo", OP_REPLACE_BZ);
- expected_graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
-
- GenVertex(&expected_graph[9],
- VectOfExt(0, 9),
- VectOfExt(60, 9),
- "",
- OP_MOVE);
-
- GenVertex(&expected_graph[10],
- VectOfExt(30, 10),
- VectOfExt(60, 10),
- "",
- OP_MOVE);
- expected_graph[10].out_edges[4] = EdgeWithReadDep(VectOfExt(60, 9));
-
- EXPECT_EQ(12, graph.size());
- EXPECT_FALSE(graph.back().valid);
- for (Graph::size_type i = 0; i < graph.size() - 1; i++) {
- EXPECT_TRUE(graph[i].out_edges == expected_graph[i].out_edges);
- if (i == 8) {
- // special case
- } else {
- // EXPECT_TRUE(graph[i] == expected_graph[i]) << "i = " << i;
- }
- }
-}
-
-// Test that sparse holes are not used as scratch. More specifically, test that
-// if all full operations write to sparse holes and there's no extra scratch
-// space, delta operations that need scratch are converted to full. See
-// crbug.com/238440.
-TEST_F(DeltaDiffGeneratorTest, RunAsRootNoSparseAsTempTest) {
- Graph graph(3);
- const vector<Extent> kEmpty;
- const string kFilename = "/foo";
-
- // Make sure this sparse hole is not used as scratch.
- GenVertex(&graph[0], kEmpty, VectOfExt(kSparseHole, 1), "", OP_REPLACE);
-
- // Create a single-block cycle.
- GenVertex(&graph[1], VectOfExt(0, 1), VectOfExt(1, 1), "", OP_BSDIFF);
- graph[1].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
- GenVertex(&graph[2], VectOfExt(1, 1), VectOfExt(0, 1), kFilename, OP_BSDIFF);
- graph[2].out_edges[1] = EdgeWithReadDep(VectOfExt(0, 1));
-
- graph_utils::DumpGraph(graph);
-
- vector<Vertex::Index> final_order;
-
- // Prepare the filesystem with the minimum required for this to work.
- string temp_dir;
- EXPECT_TRUE(utils::MakeTempDirectory("NoSparseAsTempTest.XXXXXX",
- &temp_dir));
- ScopedDirRemover temp_dir_remover(temp_dir);
-
- const size_t kBlockSize = 4096;
- chromeos::Blob temp_data(kBlockSize);
- FillWithData(&temp_data);
- EXPECT_TRUE(WriteFileVector(temp_dir + kFilename, temp_data));
- ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
-
- int fd = -1;
- EXPECT_TRUE(utils::MakeTempFile("NoSparseAsTempTestData.XXXXXX",
- nullptr,
- &fd));
- ScopedFdCloser fd_closer(&fd);
- off_t data_file_size = 0;
-
- EXPECT_TRUE(DeltaDiffGenerator::ConvertGraphToDag(&graph,
- temp_dir,
- fd,
- &data_file_size,
- &final_order,
- Vertex::kInvalidIndex));
-
- ASSERT_EQ(4, graph.size());
-
- // The second BSDIFF operation must have been converted to a full operation
- // (due to insufficient scratch space).
- EXPECT_TRUE(graph[2].op.type() == OP_REPLACE ||
- graph[2].op.type() == OP_REPLACE_BZ);
-
- // The temporary node created for breaking the cycle must have been marked as
- // invalid.
- EXPECT_FALSE(graph[3].valid);
-}
-
-// Test that sparse holes are not used as scratch. More specifically, test that
-// if scratch space comes only from full operations writing to real blocks as
-// well as sparse holes, only the real blocks are utilized. See
-// crbug.com/238440.
-TEST_F(DeltaDiffGeneratorTest, NoSparseAsTempTest) {
- Graph graph;
- vector<Block> blocks(4);
-
- // Create nodes in |graph|.
- {
- graph.resize(graph.size() + 1);
- graph.back().op.set_type(
- DeltaArchiveManifest_InstallOperation_Type_REPLACE);
-
- // Write to a sparse hole -- basically a no-op to ensure sparse holes are
- // not used as scratch.
- vector<Extent> extents;
- graph_utils::AppendBlockToExtents(&extents, kSparseHole);
- DeltaDiffGenerator::StoreExtents(extents,
- graph.back().op.mutable_dst_extents());
- }
- {
- graph.resize(graph.size() + 1);
- graph.back().op.set_type(OP_REPLACE);
-
- // Scratch space: write to block 0 with sparse holes around.
- vector<Extent> extents;
- graph_utils::AppendBlockToExtents(&extents, kSparseHole);
- graph_utils::AppendBlockToExtents(&extents, 0);
- graph_utils::AppendBlockToExtents(&extents, kSparseHole);
- DeltaDiffGenerator::StoreExtents(extents,
- graph.back().op.mutable_dst_extents());
- blocks[0].writer = graph.size() - 1;
- }
- {
- graph.resize(graph.size() + 1);
- graph.back().op.set_type(OP_REPLACE);
-
- // Write to a sparse hole.
- vector<Extent> extents;
- graph_utils::AppendBlockToExtents(&extents, kSparseHole);
- DeltaDiffGenerator::StoreExtents(extents,
- graph.back().op.mutable_dst_extents());
- }
- // Create a two-node cycle between (2, sparse, sparse) and (1, sparse, 3).
- {
- graph.resize(graph.size() + 1);
- graph.back().op.set_type(OP_MOVE);
- // Read from (2, sparse, sparse).
- vector<Extent> extents;
- graph_utils::AppendBlockToExtents(&extents, 2);
- graph_utils::AppendBlockToExtents(&extents, kSparseHole);
- graph_utils::AppendBlockToExtents(&extents, kSparseHole);
- DeltaDiffGenerator::StoreExtents(extents,
- graph.back().op.mutable_src_extents());
- blocks[2].reader = graph.size() - 1;
-
- // Write to (1, sparse, 3).
- extents.clear();
- graph_utils::AppendBlockToExtents(&extents, 1);
- graph_utils::AppendBlockToExtents(&extents, kSparseHole);
- graph_utils::AppendBlockToExtents(&extents, 3);
- DeltaDiffGenerator::StoreExtents(extents,
- graph.back().op.mutable_dst_extents());
- blocks[1].writer = graph.size() - 1;
- blocks[3].writer = graph.size() - 1;
- }
- {
- graph.resize(graph.size() + 1);
- graph.back().op.set_type(OP_MOVE);
- // Read from (1, sparse, 3).
- vector<Extent> extents;
- graph_utils::AppendBlockToExtents(&extents, 1);
- graph_utils::AppendBlockToExtents(&extents, kSparseHole);
- graph_utils::AppendBlockToExtents(&extents, 3);
- DeltaDiffGenerator::StoreExtents(extents,
- graph.back().op.mutable_src_extents());
- blocks[1].reader = graph.size() - 1;
- blocks[3].reader = graph.size() - 1;
-
- // Write to (2, sparse, sparse).
- extents.clear();
- graph_utils::AppendBlockToExtents(&extents, 2);
- graph_utils::AppendBlockToExtents(&extents, kSparseHole);
- graph_utils::AppendBlockToExtents(&extents, kSparseHole);
- DeltaDiffGenerator::StoreExtents(extents,
- graph.back().op.mutable_dst_extents());
- blocks[2].writer = graph.size() - 1;
- }
-
- graph_utils::DumpGraph(graph);
-
- // Create edges
- DeltaDiffGenerator::CreateEdges(&graph, blocks);
-
- graph_utils::DumpGraph(graph);
-
- vector<Vertex::Index> final_order;
- off_t data_file_size = 0;
- EXPECT_TRUE(DeltaDiffGenerator::ConvertGraphToDag(&graph,
- "/non/existent/dir",
- -1,
- &data_file_size,
- &final_order,
- Vertex::kInvalidIndex));
-
- // Check for a single temporary node writing to scratch.
- ASSERT_EQ(6, graph.size());
- EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
- graph[5].op.type());
- EXPECT_EQ(1, graph[5].op.src_extents_size());
- ASSERT_EQ(1, graph[5].op.dst_extents_size());
- EXPECT_EQ(0, graph[5].op.dst_extents(0).start_block());
- EXPECT_EQ(1, graph[5].op.dst_extents(0).num_blocks());
-
- // Make sure the cycle nodes still read from and write to sparse holes.
- for (int i = 3; i < 5; i++) {
- ASSERT_GE(graph[i].op.src_extents_size(), 2);
- EXPECT_EQ(kSparseHole, graph[i].op.src_extents(1).start_block());
- ASSERT_GE(graph[i].op.dst_extents_size(), 2);
- EXPECT_EQ(kSparseHole, graph[i].op.dst_extents(1).start_block());
- }
-}
TEST_F(DeltaDiffGeneratorTest, IsNoopOperationTest) {
DeltaArchiveManifest_InstallOperation op;
@@ -1009,124 +448,4 @@
EXPECT_FALSE(DeltaDiffGenerator::IsNoopOperation(op));
}
-TEST_F(DeltaDiffGeneratorTest, RunAsRootAssignTempBlocksReuseTest) {
- // AssignTempBlocks(Graph* graph,
- // const string& new_root,
- // int data_fd,
- // off_t* data_file_size,
- // vector<Vertex::Index>* op_indexes,
- // vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
- // const vector<CutEdgeVertexes>& cuts
- Graph graph(9);
-
- const vector<Extent> empt;
- uint64_t tmp = kTempBlockStart;
- const string kFilename = "/foo";
-
- vector<CutEdgeVertexes> cuts;
- cuts.resize(3);
-
- // Simple broken loop:
- GenVertex(&graph[0], VectOfExt(0, 1), VectOfExt(1, 1), "", OP_MOVE);
- GenVertex(&graph[1], VectOfExt(tmp, 1), VectOfExt(0, 1), "", OP_MOVE);
- GenVertex(&graph[2], VectOfExt(1, 1), VectOfExt(tmp, 1), "", OP_MOVE);
- // Corresponding edges:
- graph[0].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
- graph[1].out_edges[2] = EdgeWithWriteDep(VectOfExt(tmp, 1));
- graph[1].out_edges[0] = EdgeWithReadDep(VectOfExt(0, 1));
- // Store the cut:
- cuts[0].old_dst = 1;
- cuts[0].old_src = 0;
- cuts[0].new_vertex = 2;
- cuts[0].tmp_extents = VectOfExt(tmp, 1);
- tmp++;
-
- // Slightly more complex pair of loops:
- GenVertex(&graph[3], VectOfExt(4, 2), VectOfExt(2, 2), "", OP_MOVE);
- GenVertex(&graph[4], VectOfExt(6, 1), VectOfExt(7, 1), "", OP_MOVE);
- GenVertex(&graph[5], VectOfExt(tmp, 3), VectOfExt(4, 3), kFilename, OP_MOVE);
- GenVertex(&graph[6], VectOfExt(2, 2), VectOfExt(tmp, 2), "", OP_MOVE);
- GenVertex(&graph[7], VectOfExt(7, 1), VectOfExt(tmp + 2, 1), "", OP_MOVE);
- // Corresponding edges:
- graph[3].out_edges[6] = EdgeWithReadDep(VectOfExt(2, 2));
- graph[4].out_edges[7] = EdgeWithReadDep(VectOfExt(7, 1));
- graph[5].out_edges[6] = EdgeWithWriteDep(VectOfExt(tmp, 2));
- graph[5].out_edges[7] = EdgeWithWriteDep(VectOfExt(tmp + 2, 1));
- graph[5].out_edges[3] = EdgeWithReadDep(VectOfExt(4, 2));
- graph[5].out_edges[4] = EdgeWithReadDep(VectOfExt(6, 1));
- // Store the cuts:
- cuts[1].old_dst = 5;
- cuts[1].old_src = 3;
- cuts[1].new_vertex = 6;
- cuts[1].tmp_extents = VectOfExt(tmp, 2);
- cuts[2].old_dst = 5;
- cuts[2].old_src = 4;
- cuts[2].new_vertex = 7;
- cuts[2].tmp_extents = VectOfExt(tmp + 2, 1);
-
- // Supplier of temp block:
- GenVertex(&graph[8], empt, VectOfExt(8, 1), "", OP_REPLACE);
-
- // Specify the final order:
- vector<Vertex::Index> op_indexes;
- op_indexes.push_back(2);
- op_indexes.push_back(0);
- op_indexes.push_back(1);
- op_indexes.push_back(6);
- op_indexes.push_back(3);
- op_indexes.push_back(7);
- op_indexes.push_back(4);
- op_indexes.push_back(5);
- op_indexes.push_back(8);
-
- vector<vector<Vertex::Index>::size_type> reverse_op_indexes;
- DeltaDiffGenerator::GenerateReverseTopoOrderMap(op_indexes,
- &reverse_op_indexes);
-
- // Prepare the filesystem with the minimum required for this to work
- string temp_dir;
- EXPECT_TRUE(utils::MakeTempDirectory("AssignTempBlocksReuseTest.XXXXXX",
- &temp_dir));
- ScopedDirRemover temp_dir_remover(temp_dir);
-
- const size_t kBlockSize = 4096;
- chromeos::Blob temp_data(kBlockSize * 3);
- FillWithData(&temp_data);
- EXPECT_TRUE(WriteFileVector(temp_dir + kFilename, temp_data));
- ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
-
- int fd;
- EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksReuseTest.XXXXXX",
- nullptr,
- &fd));
- ScopedFdCloser fd_closer(&fd);
- off_t data_file_size = 0;
-
- EXPECT_TRUE(DeltaDiffGenerator::AssignTempBlocks(&graph,
- temp_dir,
- fd,
- &data_file_size,
- &op_indexes,
- &reverse_op_indexes,
- cuts));
- EXPECT_FALSE(graph[6].valid);
- EXPECT_FALSE(graph[7].valid);
- EXPECT_EQ(1, graph[1].op.src_extents_size());
- EXPECT_EQ(2, graph[1].op.src_extents(0).start_block());
- EXPECT_EQ(1, graph[1].op.src_extents(0).num_blocks());
- EXPECT_EQ(OP_REPLACE_BZ, graph[5].op.type());
-}
-
-TEST_F(DeltaDiffGeneratorTest, CreateScratchNodeTest) {
- Vertex vertex;
- DeltaDiffGenerator::CreateScratchNode(12, 34, &vertex);
- EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ,
- vertex.op.type());
- EXPECT_EQ(0, vertex.op.data_offset());
- EXPECT_EQ(0, vertex.op.data_length());
- EXPECT_EQ(1, vertex.op.dst_extents_size());
- EXPECT_EQ(12, vertex.op.dst_extents(0).start_block());
- EXPECT_EQ(34, vertex.op.dst_extents(0).num_blocks());
-}
-
} // namespace chromeos_update_engine
diff --git a/payload_generator/inplace_generator.cc b/payload_generator/inplace_generator.cc
new file mode 100644
index 0000000..0567b62
--- /dev/null
+++ b/payload_generator/inplace_generator.cc
@@ -0,0 +1,677 @@
+// 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/inplace_generator.h"
+
+#include <algorithm>
+#include <map>
+#include <set>
+#include <string>
+#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/graph_types.h"
+#include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/payload_generator/topological_sort.h"
+#include "update_engine/update_metadata.pb.h"
+#include "update_engine/utils.h"
+
+using std::make_pair;
+using std::map;
+using std::pair;
+using std::set;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+using Block = DeltaDiffGenerator::Block;
+
+// This class allocates non-existent temp blocks, starting from
+// kTempBlockStart. Other code is responsible for converting these
+// temp blocks into real blocks, as the client can't read or write to
+// these blocks.
+class DummyExtentAllocator {
+ public:
+ vector<Extent> Allocate(const uint64_t block_count) {
+ vector<Extent> ret(1);
+ ret[0].set_start_block(next_block_);
+ ret[0].set_num_blocks(block_count);
+ next_block_ += block_count;
+ return ret;
+ }
+
+ private:
+ uint64_t next_block_{kTempBlockStart};
+};
+
+// Takes a vector of blocks and returns an equivalent vector of Extent
+// objects.
+vector<Extent> CompressExtents(const vector<uint64_t>& blocks) {
+ vector<Extent> new_extents;
+ for (uint64_t block : blocks) {
+ graph_utils::AppendBlockToExtents(&new_extents, block);
+ }
+ return new_extents;
+}
+
+void InplaceGenerator::SubstituteBlocks(
+ Vertex* vertex,
+ const vector<Extent>& remove_extents,
+ const vector<Extent>& replace_extents) {
+ // First, expand out the blocks that op reads from
+ vector<uint64_t> read_blocks =
+ DeltaDiffGenerator::ExpandExtents(vertex->op.src_extents());
+ {
+ // Expand remove_extents and replace_extents
+ vector<uint64_t> remove_extents_expanded =
+ DeltaDiffGenerator::ExpandExtents(remove_extents);
+ vector<uint64_t> replace_extents_expanded =
+ DeltaDiffGenerator::ExpandExtents(replace_extents);
+ CHECK_EQ(remove_extents_expanded.size(), replace_extents_expanded.size());
+ map<uint64_t, uint64_t> conversion;
+ for (vector<uint64_t>::size_type i = 0;
+ i < replace_extents_expanded.size(); i++) {
+ conversion[remove_extents_expanded[i]] = replace_extents_expanded[i];
+ }
+ utils::ApplyMap(&read_blocks, conversion);
+ for (auto& edge_prop_pair : vertex->out_edges) {
+ vector<uint64_t> write_before_deps_expanded =
+ DeltaDiffGenerator::ExpandExtents(
+ edge_prop_pair.second.write_extents);
+ utils::ApplyMap(&write_before_deps_expanded, conversion);
+ edge_prop_pair.second.write_extents =
+ CompressExtents(write_before_deps_expanded);
+ }
+ }
+ // Convert read_blocks back to extents
+ vertex->op.clear_src_extents();
+ vector<Extent> new_extents = CompressExtents(read_blocks);
+ DeltaDiffGenerator::StoreExtents(new_extents,
+ vertex->op.mutable_src_extents());
+}
+
+bool InplaceGenerator::CutEdges(Graph* graph,
+ const set<Edge>& edges,
+ vector<CutEdgeVertexes>* out_cuts) {
+ DummyExtentAllocator scratch_allocator;
+ vector<CutEdgeVertexes> cuts;
+ cuts.reserve(edges.size());
+
+ uint64_t scratch_blocks_used = 0;
+ for (const Edge& edge : edges) {
+ cuts.resize(cuts.size() + 1);
+ vector<Extent> old_extents =
+ (*graph)[edge.first].out_edges[edge.second].extents;
+ // Choose some scratch space
+ scratch_blocks_used += graph_utils::EdgeWeight(*graph, edge);
+ cuts.back().tmp_extents =
+ scratch_allocator.Allocate(graph_utils::EdgeWeight(*graph, edge));
+ // create vertex to copy original->scratch
+ cuts.back().new_vertex = graph->size();
+ graph->resize(graph->size() + 1);
+ cuts.back().old_src = edge.first;
+ cuts.back().old_dst = edge.second;
+
+ EdgeProperties& cut_edge_properties =
+ (*graph)[edge.first].out_edges.find(edge.second)->second;
+
+ // This should never happen, as we should only be cutting edges between
+ // real file nodes, and write-before relationships are created from
+ // a real file node to a temp copy node:
+ CHECK(cut_edge_properties.write_extents.empty())
+ << "Can't cut edge that has write-before relationship.";
+
+ // make node depend on the copy operation
+ (*graph)[edge.first].out_edges.insert(make_pair(graph->size() - 1,
+ cut_edge_properties));
+
+ // Set src/dst extents and other proto variables for copy operation
+ graph->back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+ DeltaDiffGenerator::StoreExtents(
+ cut_edge_properties.extents,
+ graph->back().op.mutable_src_extents());
+ DeltaDiffGenerator::StoreExtents(cuts.back().tmp_extents,
+ graph->back().op.mutable_dst_extents());
+ graph->back().op.set_src_length(
+ graph_utils::EdgeWeight(*graph, edge) * kBlockSize);
+ graph->back().op.set_dst_length(graph->back().op.src_length());
+
+ // make the dest node read from the scratch space
+ SubstituteBlocks(
+ &((*graph)[edge.second]),
+ (*graph)[edge.first].out_edges[edge.second].extents,
+ cuts.back().tmp_extents);
+
+ // delete the old edge
+ CHECK_EQ(static_cast<Graph::size_type>(1),
+ (*graph)[edge.first].out_edges.erase(edge.second));
+
+ // Add an edge from dst to copy operation
+ EdgeProperties write_before_edge_properties;
+ write_before_edge_properties.write_extents = cuts.back().tmp_extents;
+ (*graph)[edge.second].out_edges.insert(
+ make_pair(graph->size() - 1, write_before_edge_properties));
+ }
+ out_cuts->swap(cuts);
+ return true;
+}
+
+// Creates all the edges for the graph. Writers of a block point to
+// readers of the same block. This is because for an edge A->B, B
+// must complete before A executes.
+void InplaceGenerator::CreateEdges(
+ Graph* graph,
+ const vector<DeltaDiffGenerator::Block>& blocks) {
+ for (vector<DeltaDiffGenerator::Block>::size_type i = 0;
+ i < blocks.size(); i++) {
+ // Blocks with both a reader and writer get an edge
+ if (blocks[i].reader == Vertex::kInvalidIndex ||
+ blocks[i].writer == Vertex::kInvalidIndex)
+ continue;
+ // Don't have a node depend on itself
+ if (blocks[i].reader == blocks[i].writer)
+ continue;
+ // See if there's already an edge we can add onto
+ Vertex::EdgeMap::iterator edge_it =
+ (*graph)[blocks[i].writer].out_edges.find(blocks[i].reader);
+ if (edge_it == (*graph)[blocks[i].writer].out_edges.end()) {
+ // No existing edge. Create one
+ (*graph)[blocks[i].writer].out_edges.insert(
+ make_pair(blocks[i].reader, EdgeProperties()));
+ 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);
+ }
+}
+
+namespace {
+
+class SortCutsByTopoOrderLess {
+ public:
+ explicit SortCutsByTopoOrderLess(
+ const vector<vector<Vertex::Index>::size_type>& table)
+ : table_(table) {}
+ bool operator()(const CutEdgeVertexes& a, const CutEdgeVertexes& b) {
+ return table_[a.old_dst] < table_[b.old_dst];
+ }
+ private:
+ const vector<vector<Vertex::Index>::size_type>& table_;
+};
+
+} // namespace
+
+void InplaceGenerator::GenerateReverseTopoOrderMap(
+ const vector<Vertex::Index>& op_indexes,
+ vector<vector<Vertex::Index>::size_type>* reverse_op_indexes) {
+ vector<vector<Vertex::Index>::size_type> table(op_indexes.size());
+ for (vector<Vertex::Index>::size_type i = 0, e = op_indexes.size();
+ i != e; ++i) {
+ Vertex::Index node = op_indexes[i];
+ if (table.size() < (node + 1)) {
+ table.resize(node + 1);
+ }
+ table[node] = i;
+ }
+ reverse_op_indexes->swap(table);
+}
+
+void InplaceGenerator::SortCutsByTopoOrder(
+ const vector<Vertex::Index>& op_indexes,
+ vector<CutEdgeVertexes>* cuts) {
+ // first, make a reverse lookup table.
+ vector<vector<Vertex::Index>::size_type> table;
+ GenerateReverseTopoOrderMap(op_indexes, &table);
+ SortCutsByTopoOrderLess less(table);
+ sort(cuts->begin(), cuts->end(), less);
+}
+
+void InplaceGenerator::MoveFullOpsToBack(Graph* graph,
+ vector<Vertex::Index>* op_indexes) {
+ vector<Vertex::Index> ret;
+ vector<Vertex::Index> full_ops;
+ ret.reserve(op_indexes->size());
+ for (vector<Vertex::Index>::size_type i = 0, e = op_indexes->size(); i != e;
+ ++i) {
+ DeltaArchiveManifest_InstallOperation_Type type =
+ (*graph)[(*op_indexes)[i]].op.type();
+ if (type == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+ type == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
+ full_ops.push_back((*op_indexes)[i]);
+ } else {
+ ret.push_back((*op_indexes)[i]);
+ }
+ }
+ LOG(INFO) << "Stats: " << full_ops.size() << " full ops out of "
+ << (full_ops.size() + ret.size()) << " total ops.";
+ ret.insert(ret.end(), full_ops.begin(), full_ops.end());
+ op_indexes->swap(ret);
+}
+
+namespace {
+
+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);
+ uint64_t start = extent.start_block();
+ uint64_t num = extent.num_blocks();
+ if (start == kSparseHole)
+ continue;
+ if (start >= kTempBlockStart || (start + num) >= kTempBlockStart) {
+ LOG(ERROR) << "temp block!";
+ LOG(ERROR) << "start: " << start << ", num: " << num;
+ LOG(ERROR) << "kTempBlockStart: " << kTempBlockStart;
+ LOG(ERROR) << "returning true";
+ return true;
+ }
+ // check for wrap-around, which would be a bug:
+ CHECK(start <= (start + num));
+ }
+ return false;
+}
+
+// Converts the cuts, which must all have the same |old_dst| member,
+// to full. It does this by converting the |old_dst| to REPLACE or
+// REPLACE_BZ, dropping all incoming edges to |old_dst|, and marking
+// all temp nodes invalid.
+bool ConvertCutsToFull(
+ Graph* graph,
+ const string& new_root,
+ int data_fd,
+ off_t* data_file_size,
+ vector<Vertex::Index>* op_indexes,
+ vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
+ const vector<CutEdgeVertexes>& cuts) {
+ CHECK(!cuts.empty());
+ set<Vertex::Index> deleted_nodes;
+ for (const CutEdgeVertexes& cut : cuts) {
+ TEST_AND_RETURN_FALSE(InplaceGenerator::ConvertCutToFullOp(
+ graph,
+ cut,
+ new_root,
+ data_fd,
+ data_file_size));
+ deleted_nodes.insert(cut.new_vertex);
+ }
+ deleted_nodes.insert(cuts[0].old_dst);
+
+ vector<Vertex::Index> new_op_indexes;
+ new_op_indexes.reserve(op_indexes->size());
+ for (Vertex::Index vertex_index : *op_indexes) {
+ if (utils::SetContainsKey(deleted_nodes, vertex_index))
+ continue;
+ new_op_indexes.push_back(vertex_index);
+ }
+ new_op_indexes.push_back(cuts[0].old_dst);
+ op_indexes->swap(new_op_indexes);
+ InplaceGenerator::GenerateReverseTopoOrderMap(*op_indexes,
+ reverse_op_indexes);
+ return true;
+}
+
+// Tries to assign temp blocks for a collection of cuts, all of which share
+// the same old_dst member. If temp blocks can't be found, old_dst will be
+// converted to a REPLACE or REPLACE_BZ operation. Returns true on success,
+// which can happen even if blocks are converted to full. Returns false
+// on exceptional error cases.
+bool AssignBlockForAdjoiningCuts(
+ Graph* graph,
+ const string& new_root,
+ int data_fd,
+ off_t* data_file_size,
+ vector<Vertex::Index>* op_indexes,
+ vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
+ const vector<CutEdgeVertexes>& cuts) {
+ CHECK(!cuts.empty());
+ const Vertex::Index old_dst = cuts[0].old_dst;
+ // Calculate # of blocks needed
+ uint64_t blocks_needed = 0;
+ vector<uint64_t> cuts_blocks_needed(cuts.size());
+ for (vector<CutEdgeVertexes>::size_type i = 0; i < cuts.size(); ++i) {
+ uint64_t cut_blocks_needed = 0;
+ for (const Extent& extent : cuts[i].tmp_extents) {
+ cut_blocks_needed += extent.num_blocks();
+ }
+ blocks_needed += cut_blocks_needed;
+ cuts_blocks_needed[i] = cut_blocks_needed;
+ }
+
+ // Find enough blocks
+ ExtentRanges scratch_ranges;
+ // Each block that's supplying temp blocks and the corresponding blocks:
+ typedef vector<pair<Vertex::Index, ExtentRanges>> SupplierVector;
+ SupplierVector block_suppliers;
+ uint64_t scratch_blocks_found = 0;
+ for (vector<Vertex::Index>::size_type i = (*reverse_op_indexes)[old_dst] + 1,
+ e = op_indexes->size(); i < e; ++i) {
+ Vertex::Index test_node = (*op_indexes)[i];
+ if (!(*graph)[test_node].valid)
+ continue;
+ // See if this node has sufficient blocks
+ ExtentRanges ranges;
+ ranges.AddRepeatedExtents((*graph)[test_node].op.dst_extents());
+ ranges.SubtractExtent(ExtentForRange(
+ kTempBlockStart, kSparseHole - kTempBlockStart));
+ ranges.SubtractRepeatedExtents((*graph)[test_node].op.src_extents());
+ // For now, for simplicity, subtract out all blocks in read-before
+ // dependencies.
+ for (Vertex::EdgeMap::const_iterator edge_i =
+ (*graph)[test_node].out_edges.begin(),
+ edge_e = (*graph)[test_node].out_edges.end();
+ edge_i != edge_e; ++edge_i) {
+ ranges.SubtractExtents(edge_i->second.extents);
+ }
+ if (ranges.blocks() == 0)
+ continue;
+
+ if (ranges.blocks() + scratch_blocks_found > blocks_needed) {
+ // trim down ranges
+ vector<Extent> new_ranges = ranges.GetExtentsForBlockCount(
+ blocks_needed - scratch_blocks_found);
+ ranges = ExtentRanges();
+ ranges.AddExtents(new_ranges);
+ }
+ scratch_ranges.AddRanges(ranges);
+ block_suppliers.push_back(make_pair(test_node, ranges));
+ scratch_blocks_found += ranges.blocks();
+ if (scratch_ranges.blocks() >= blocks_needed)
+ break;
+ }
+ if (scratch_ranges.blocks() < blocks_needed) {
+ LOG(INFO) << "Unable to find sufficient scratch";
+ TEST_AND_RETURN_FALSE(ConvertCutsToFull(graph,
+ new_root,
+ data_fd,
+ data_file_size,
+ op_indexes,
+ reverse_op_indexes,
+ cuts));
+ return true;
+ }
+ // Use the scratch we found
+ TEST_AND_RETURN_FALSE(scratch_ranges.blocks() == scratch_blocks_found);
+
+ // Make all the suppliers depend on this node
+ for (const auto& index_range_pair : block_suppliers) {
+ graph_utils::AddReadBeforeDepExtents(
+ &(*graph)[index_range_pair.first],
+ old_dst,
+ index_range_pair.second.GetExtentsForBlockCount(
+ index_range_pair.second.blocks()));
+ }
+
+ // Replace temp blocks in each cut
+ for (vector<CutEdgeVertexes>::size_type i = 0; i < cuts.size(); ++i) {
+ const CutEdgeVertexes& cut = cuts[i];
+ vector<Extent> real_extents =
+ scratch_ranges.GetExtentsForBlockCount(cuts_blocks_needed[i]);
+ scratch_ranges.SubtractExtents(real_extents);
+
+ // Fix the old dest node w/ the real blocks
+ InplaceGenerator::SubstituteBlocks(&(*graph)[old_dst],
+ cut.tmp_extents,
+ real_extents);
+
+ // Fix the new node w/ the real blocks. Since the new node is just a
+ // copy operation, we can replace all the dest extents w/ the real
+ // blocks.
+ DeltaArchiveManifest_InstallOperation *op = &(*graph)[cut.new_vertex].op;
+ op->clear_dst_extents();
+ DeltaDiffGenerator::StoreExtents(real_extents, op->mutable_dst_extents());
+ }
+ return true;
+}
+
+} // namespace
+
+bool InplaceGenerator::AssignTempBlocks(
+ Graph* graph,
+ const string& new_root,
+ int data_fd,
+ off_t* data_file_size,
+ vector<Vertex::Index>* op_indexes,
+ vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
+ const vector<CutEdgeVertexes>& cuts) {
+ CHECK(!cuts.empty());
+
+ // group of cuts w/ the same old_dst:
+ vector<CutEdgeVertexes> cuts_group;
+
+ for (vector<CutEdgeVertexes>::size_type i = cuts.size() - 1, e = 0;
+ true ; --i) {
+ LOG(INFO) << "Fixing temp blocks in cut " << i
+ << ": old dst: " << cuts[i].old_dst << " new vertex: "
+ << cuts[i].new_vertex << " path: "
+ << (*graph)[cuts[i].old_dst].file_name;
+
+ if (cuts_group.empty() || (cuts_group[0].old_dst == cuts[i].old_dst)) {
+ cuts_group.push_back(cuts[i]);
+ } else {
+ CHECK(!cuts_group.empty());
+ TEST_AND_RETURN_FALSE(AssignBlockForAdjoiningCuts(graph,
+ new_root,
+ data_fd,
+ data_file_size,
+ op_indexes,
+ reverse_op_indexes,
+ cuts_group));
+ cuts_group.clear();
+ cuts_group.push_back(cuts[i]);
+ }
+
+ if (i == e) {
+ // break out of for() loop
+ break;
+ }
+ }
+ CHECK(!cuts_group.empty());
+ TEST_AND_RETURN_FALSE(AssignBlockForAdjoiningCuts(graph,
+ new_root,
+ data_fd,
+ data_file_size,
+ op_indexes,
+ reverse_op_indexes,
+ cuts_group));
+ return true;
+}
+
+bool InplaceGenerator::NoTempBlocksRemain(const Graph& graph) {
+ size_t idx = 0;
+ for (Graph::const_iterator it = graph.begin(), e = graph.end(); it != e;
+ ++it, ++idx) {
+ if (!it->valid)
+ continue;
+ const DeltaArchiveManifest_InstallOperation& op = it->op;
+ if (TempBlocksExistInExtents(op.dst_extents()) ||
+ TempBlocksExistInExtents(op.src_extents())) {
+ LOG(INFO) << "bad extents in node " << idx;
+ LOG(INFO) << "so yeah";
+ return false;
+ }
+
+ // Check out-edges:
+ for (const auto& edge_prop_pair : it->out_edges) {
+ if (TempBlocksExistInExtents(edge_prop_pair.second.extents) ||
+ TempBlocksExistInExtents(edge_prop_pair.second.write_extents)) {
+ LOG(INFO) << "bad out edge in node " << idx;
+ LOG(INFO) << "so yeah";
+ return false;
+ }
+ }
+ }
+ return true;
+}
+
+bool InplaceGenerator::ConvertCutToFullOp(Graph* graph,
+ const CutEdgeVertexes& cut,
+ const string& new_root,
+ int data_fd,
+ off_t* data_file_size) {
+ // Drop all incoming edges, keep all outgoing edges
+
+ // Keep all outgoing edges
+ if ((*graph)[cut.old_dst].op.type() !=
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ &&
+ (*graph)[cut.old_dst].op.type() !=
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
+ Vertex::EdgeMap out_edges = (*graph)[cut.old_dst].out_edges;
+ graph_utils::DropWriteBeforeDeps(&out_edges);
+
+ TEST_AND_RETURN_FALSE(DeltaDiffGenerator::DeltaReadFile(
+ graph,
+ cut.old_dst,
+ nullptr,
+ kEmptyPath,
+ new_root,
+ (*graph)[cut.old_dst].file_name,
+ (*graph)[cut.old_dst].chunk_offset,
+ (*graph)[cut.old_dst].chunk_size,
+ data_fd,
+ data_file_size));
+
+ (*graph)[cut.old_dst].out_edges = out_edges;
+
+ // Right now we don't have doubly-linked edges, so we have to scan
+ // the whole graph.
+ graph_utils::DropIncomingEdgesTo(graph, cut.old_dst);
+ }
+
+ // Delete temp node
+ (*graph)[cut.old_src].out_edges.erase(cut.new_vertex);
+ CHECK((*graph)[cut.old_dst].out_edges.find(cut.new_vertex) ==
+ (*graph)[cut.old_dst].out_edges.end());
+ (*graph)[cut.new_vertex].valid = false;
+ LOG(INFO) << "marked node invalid: " << cut.new_vertex;
+ return true;
+}
+
+bool InplaceGenerator::ConvertGraphToDag(Graph* graph,
+ const string& new_root,
+ int fd,
+ off_t* data_file_size,
+ vector<Vertex::Index>* final_order,
+ Vertex::Index scratch_vertex) {
+ CycleBreaker cycle_breaker;
+ LOG(INFO) << "Finding cycles...";
+ set<Edge> cut_edges;
+ cycle_breaker.BreakCycles(*graph, &cut_edges);
+ LOG(INFO) << "done finding cycles";
+ DeltaDiffGenerator::CheckGraph(*graph);
+
+ // Calculate number of scratch blocks needed
+
+ LOG(INFO) << "Cutting cycles...";
+ vector<CutEdgeVertexes> cuts;
+ TEST_AND_RETURN_FALSE(CutEdges(graph, cut_edges, &cuts));
+ LOG(INFO) << "done cutting cycles";
+ LOG(INFO) << "There are " << cuts.size() << " cuts.";
+ DeltaDiffGenerator::CheckGraph(*graph);
+
+ LOG(INFO) << "Creating initial topological order...";
+ TopologicalSort(*graph, final_order);
+ LOG(INFO) << "done with initial topo order";
+ DeltaDiffGenerator::CheckGraph(*graph);
+
+ LOG(INFO) << "Moving full ops to the back";
+ MoveFullOpsToBack(graph, final_order);
+ LOG(INFO) << "done moving full ops to back";
+
+ vector<vector<Vertex::Index>::size_type> inverse_final_order;
+ GenerateReverseTopoOrderMap(*final_order, &inverse_final_order);
+
+ SortCutsByTopoOrder(*final_order, &cuts);
+
+ if (!cuts.empty())
+ TEST_AND_RETURN_FALSE(AssignTempBlocks(graph,
+ new_root,
+ fd,
+ data_file_size,
+ final_order,
+ &inverse_final_order,
+ cuts));
+ LOG(INFO) << "Making sure all temp blocks have been allocated";
+
+ // Remove the scratch node, if any
+ if (scratch_vertex != Vertex::kInvalidIndex) {
+ final_order->erase(final_order->begin() +
+ inverse_final_order[scratch_vertex]);
+ (*graph)[scratch_vertex].valid = false;
+ GenerateReverseTopoOrderMap(*final_order, &inverse_final_order);
+ }
+
+ graph_utils::DumpGraph(*graph);
+ CHECK(NoTempBlocksRemain(*graph));
+ LOG(INFO) << "done making sure all temp blocks are allocated";
+ return true;
+}
+
+void InplaceGenerator::CreateScratchNode(uint64_t start_block,
+ uint64_t num_blocks,
+ Vertex* vertex) {
+ vertex->file_name = "<scratch>";
+ vertex->op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+ vertex->op.set_data_offset(0);
+ vertex->op.set_data_length(0);
+ Extent* extent = vertex->op.add_dst_extents();
+ extent->set_start_block(start_block);
+ extent->set_num_blocks(num_blocks);
+}
+
+// The |blocks| vector contains a reader and writer for each block on the
+// filesystem that's being in-place updated. We populate the reader/writer
+// fields of |blocks| by calling this function.
+// For each block in |operation| that is read or written, find that block
+// in |blocks| and set the reader/writer field to the vertex passed.
+// |graph| is not strictly necessary, but useful for printing out
+// error messages.
+bool InplaceGenerator::AddInstallOpToBlocksVector(
+ const DeltaArchiveManifest_InstallOperation& operation,
+ const Graph& graph,
+ Vertex::Index vertex,
+ vector<DeltaDiffGenerator::Block>* blocks) {
+ // See if this is already present.
+ TEST_AND_RETURN_FALSE(operation.dst_extents_size() > 0);
+
+ enum BlockField { READER = 0, WRITER, BLOCK_FIELD_COUNT };
+ for (int field = READER; field < BLOCK_FIELD_COUNT; field++) {
+ const int extents_size =
+ (field == READER) ? operation.src_extents_size() :
+ operation.dst_extents_size();
+ const char* past_participle = (field == READER) ? "read" : "written";
+ const google::protobuf::RepeatedPtrField<Extent>& extents =
+ (field == READER) ? operation.src_extents() : operation.dst_extents();
+ Vertex::Index DeltaDiffGenerator::Block::*access_type =
+ (field == READER) ? &DeltaDiffGenerator::Block::reader
+ : &DeltaDiffGenerator::Block::writer;
+
+ for (int i = 0; i < extents_size; i++) {
+ const Extent& extent = extents.Get(i);
+ if (extent.start_block() == kSparseHole) {
+ // Hole in sparse file. skip
+ continue;
+ }
+ for (uint64_t block = extent.start_block();
+ block < (extent.start_block() + extent.num_blocks()); block++) {
+ if ((*blocks)[block].*access_type != Vertex::kInvalidIndex) {
+ LOG(FATAL) << "Block " << block << " is already "
+ << past_participle << " by "
+ << (*blocks)[block].*access_type << "("
+ << graph[(*blocks)[block].*access_type].file_name
+ << ") and also " << vertex << "("
+ << graph[vertex].file_name << ")";
+ }
+ (*blocks)[block].*access_type = vertex;
+ }
+ }
+ }
+ return true;
+}
+
+}; // namespace chromeos_update_engine
diff --git a/payload_generator/inplace_generator.h b/payload_generator/inplace_generator.h
new file mode 100644
index 0000000..73a791b
--- /dev/null
+++ b/payload_generator/inplace_generator.h
@@ -0,0 +1,148 @@
+// 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_INPLACE_GENERATOR_H_
+#define UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_
+
+#include <set>
+#include <string>
+#include <vector>
+
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/graph_types.h"
+
+// InplaceGenerator contains all functionality related to the inplace algorithm
+// for generating update payloads. These are the functions used when delta minor
+// version is 1.
+
+namespace chromeos_update_engine {
+
+class InplaceGenerator {
+ public:
+ // Modifies blocks read by 'op' so that any blocks referred to by
+ // 'remove_extents' are replaced with blocks from 'replace_extents'.
+ // 'remove_extents' and 'replace_extents' must be the same number of blocks.
+ // Blocks will be substituted in the order listed in the vectors.
+ // E.g. if 'op' reads blocks 1, 2, 3, 4, 5, 6, 7, 8, remove_extents
+ // contains blocks 6, 2, 3, 5, and replace blocks contains
+ // 12, 13, 14, 15, then op will be changed to read from:
+ // 1, 13, 14, 4, 15, 12, 7, 8
+ static void SubstituteBlocks(Vertex* vertex,
+ const std::vector<Extent>& remove_extents,
+ const std::vector<Extent>& replace_extents);
+
+ // Cuts 'edges' from 'graph' according to the AU algorithm. This means
+ // for each edge A->B, remove the dependency that B occur before A.
+ // Do this by creating a new operation X that copies from the blocks
+ // specified by the edge's properties to temp space T. Modify B to read
+ // from T rather than the blocks in the edge. Modify A to depend on X,
+ // but not on B. Free space is found by looking in 'blocks'.
+ // Returns true on success.
+ static bool CutEdges(Graph* graph,
+ const std::set<Edge>& edges,
+ std::vector<CutEdgeVertexes>* out_cuts);
+
+ // Creates all the edges for the graph. Writers of a block point to
+ // readers of the same block. This is because for an edge A->B, B
+ // must complete before A executes.
+ static void CreateEdges(Graph* graph,
+ const std::vector<DeltaDiffGenerator::Block>& blocks);
+
+ // Takes |op_indexes|, which is effectively a mapping from order in
+ // which the op is performed -> graph vertex index, and produces the
+ // reverse: a mapping from graph vertex index -> op_indexes index.
+ static void GenerateReverseTopoOrderMap(
+ const std::vector<Vertex::Index>& op_indexes,
+ std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes);
+
+ // Sorts the vector |cuts| by its |cuts[].old_dest| member. Order is
+ // determined by the order of elements in op_indexes.
+ static void SortCutsByTopoOrder(
+ const std::vector<Vertex::Index>& op_indexes,
+ std::vector<CutEdgeVertexes>* cuts);
+
+ // Given a topologically sorted graph |op_indexes| and |graph|, alters
+ // |op_indexes| to move all the full operations to the end of the vector.
+ // Full operations should not be depended on, so this is safe.
+ static void MoveFullOpsToBack(Graph* graph,
+ std::vector<Vertex::Index>* op_indexes);
+
+ // Returns true iff there are no extents in the graph that refer to temp
+ // blocks. Temp blocks are in the range [kTempBlockStart, kSparseHole).
+ static bool NoTempBlocksRemain(const Graph& graph);
+
+ // Takes a |graph|, which has edges that must be cut, as listed in
+ // |cuts|. Cuts the edges. Maintains a list in which the operations
+ // will be performed (in |op_indexes|) and the reverse (in
+ // |reverse_op_indexes|). Cutting edges requires scratch space, and
+ // if insufficient scratch is found, the file is reread and will be
+ // send down (either as REPLACE or REPLACE_BZ). Returns true on
+ // success.
+ static bool AssignTempBlocks(
+ Graph* graph,
+ const std::string& new_root,
+ int data_fd,
+ off_t* data_file_size,
+ std::vector<Vertex::Index>* op_indexes,
+ std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes,
+ const std::vector<CutEdgeVertexes>& cuts);
+
+ // Handles allocation of temp blocks to a cut edge by converting the
+ // dest node to a full op. This removes the need for temp blocks, but
+ // comes at the cost of a worse compression ratio.
+ // For example, say we have A->B->A. It would first be cut to form:
+ // A->B->N<-A, where N copies blocks to temp space. If there are no
+ // temp blocks, this function can be called to convert it to the form:
+ // A->B. Now, A is a full operation.
+ static bool ConvertCutToFullOp(Graph* graph,
+ const CutEdgeVertexes& cut,
+ const std::string& new_root,
+ int data_fd,
+ off_t* data_file_size);
+
+ // Takes a graph, which is not a DAG, which represents the files just
+ // read from disk, and converts it into a DAG by breaking all cycles
+ // and finding temp space to resolve broken edges.
+ // The final order of the nodes is given in |final_order|
+ // Some files may need to be reread from disk, thus |fd| and
+ // |data_file_size| are be passed.
+ // If |scratch_vertex| is not kInvalidIndex, removes it from
+ // |final_order| before returning.
+ // Returns true on success.
+ static bool ConvertGraphToDag(Graph* graph,
+ const std::string& new_root,
+ int fd,
+ off_t* data_file_size,
+ std::vector<Vertex::Index>* final_order,
+ Vertex::Index scratch_vertex);
+
+ // Creates a dummy REPLACE_BZ node in the given |vertex|. This can be used
+ // to provide scratch space. The node writes |num_blocks| blocks starting at
+ // |start_block|The node should be marked invalid before writing all nodes to
+ // the output file.
+ static void CreateScratchNode(uint64_t start_block,
+ uint64_t num_blocks,
+ Vertex* vertex);
+
+ // The |blocks| vector contains a reader and writer for each block on the
+ // filesystem that's being in-place updated. We populate the reader/writer
+ // fields of |blocks| by calling this function.
+ // For each block in |operation| that is read or written, find that block
+ // in |blocks| and set the reader/writer field to the vertex passed.
+ // |graph| is not strictly necessary, but useful for printing out
+ // error messages.
+ static bool AddInstallOpToBlocksVector(
+ const DeltaArchiveManifest_InstallOperation& operation,
+ const Graph& graph,
+ Vertex::Index vertex,
+ std::vector<DeltaDiffGenerator::Block>* blocks);
+
+ private:
+ // This should never be constructed.
+ DISALLOW_IMPLICIT_CONSTRUCTORS(InplaceGenerator);
+};
+
+}; // namespace chromeos_update_engine
+
+#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_
diff --git a/payload_generator/inplace_generator_unittest.cc b/payload_generator/inplace_generator_unittest.cc
new file mode 100644
index 0000000..051902f
--- /dev/null
+++ b/payload_generator/inplace_generator_unittest.cc
@@ -0,0 +1,710 @@
+// 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/inplace_generator.h"
+
+#include <set>
+#include <sstream>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <base/logging.h>
+#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/graph_types.h"
+#include "update_engine/test_utils.h"
+#include "update_engine/utils.h"
+
+using std::set;
+using std::string;
+using std::stringstream;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+typedef DeltaDiffGenerator::Block Block;
+
+namespace {
+
+#define OP_BSDIFF DeltaArchiveManifest_InstallOperation_Type_BSDIFF
+#define OP_MOVE DeltaArchiveManifest_InstallOperation_Type_MOVE
+#define OP_REPLACE DeltaArchiveManifest_InstallOperation_Type_REPLACE
+#define OP_REPLACE_BZ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ
+
+void GenVertex(Vertex* out,
+ const vector<Extent>& src_extents,
+ const vector<Extent>& dst_extents,
+ const string& path,
+ DeltaArchiveManifest_InstallOperation_Type type) {
+ out->op.set_type(type);
+ out->file_name = path;
+ DeltaDiffGenerator::StoreExtents(src_extents, out->op.mutable_src_extents());
+ DeltaDiffGenerator::StoreExtents(dst_extents, out->op.mutable_dst_extents());
+}
+
+vector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) {
+ return vector<Extent>(1, ExtentForRange(start_block, num_blocks));
+}
+
+EdgeProperties EdgeWithReadDep(const vector<Extent>& extents) {
+ EdgeProperties ret;
+ ret.extents = extents;
+ return ret;
+}
+
+EdgeProperties EdgeWithWriteDep(const vector<Extent>& extents) {
+ EdgeProperties ret;
+ ret.write_extents = extents;
+ return ret;
+}
+
+template<typename T>
+void DumpVect(const vector<T>& vect) {
+ stringstream ss(stringstream::out);
+ for (typename vector<T>::const_iterator it = vect.begin(), e = vect.end();
+ it != e; ++it) {
+ ss << *it << ", ";
+ }
+ LOG(INFO) << "{" << ss.str() << "}";
+}
+
+void AppendExtent(vector<Extent>* vect, uint64_t start, uint64_t length) {
+ vect->resize(vect->size() + 1);
+ vect->back().set_start_block(start);
+ vect->back().set_num_blocks(length);
+}
+
+void OpAppendExtent(DeltaArchiveManifest_InstallOperation* op,
+ uint64_t start,
+ uint64_t length) {
+ Extent* extent = op->add_src_extents();
+ extent->set_start_block(start);
+ extent->set_num_blocks(length);
+}
+
+} // namespace
+
+class InplaceGeneratorTest : public ::testing::Test {
+};
+
+TEST_F(InplaceGeneratorTest, SubstituteBlocksTest) {
+ vector<Extent> remove_blocks;
+ AppendExtent(&remove_blocks, 3, 3);
+ AppendExtent(&remove_blocks, 7, 1);
+ vector<Extent> replace_blocks;
+ AppendExtent(&replace_blocks, 10, 2);
+ AppendExtent(&replace_blocks, 13, 2);
+ Vertex vertex;
+ DeltaArchiveManifest_InstallOperation& op = vertex.op;
+ OpAppendExtent(&op, 4, 3);
+ OpAppendExtent(&op, kSparseHole, 4); // Sparse hole in file
+ OpAppendExtent(&op, 3, 1);
+ OpAppendExtent(&op, 7, 3);
+
+ InplaceGenerator::SubstituteBlocks(&vertex, remove_blocks, replace_blocks);
+
+ EXPECT_EQ(7, op.src_extents_size());
+ EXPECT_EQ(11, op.src_extents(0).start_block());
+ EXPECT_EQ(1, op.src_extents(0).num_blocks());
+ EXPECT_EQ(13, op.src_extents(1).start_block());
+ EXPECT_EQ(1, op.src_extents(1).num_blocks());
+ EXPECT_EQ(6, op.src_extents(2).start_block());
+ EXPECT_EQ(1, op.src_extents(2).num_blocks());
+ EXPECT_EQ(kSparseHole, op.src_extents(3).start_block());
+ EXPECT_EQ(4, op.src_extents(3).num_blocks());
+ EXPECT_EQ(10, op.src_extents(4).start_block());
+ EXPECT_EQ(1, op.src_extents(4).num_blocks());
+ EXPECT_EQ(14, op.src_extents(5).start_block());
+ EXPECT_EQ(1, op.src_extents(5).num_blocks());
+ EXPECT_EQ(8, op.src_extents(6).start_block());
+ EXPECT_EQ(2, op.src_extents(6).num_blocks());
+}
+
+TEST_F(InplaceGeneratorTest, CutEdgesTest) {
+ Graph graph;
+ vector<Block> blocks(9);
+
+ // Create nodes in graph
+ {
+ graph.resize(graph.size() + 1);
+ 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);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_src_extents());
+ blocks[3].reader = graph.size() - 1;
+ blocks[5].reader = graph.size() - 1;
+ blocks[7].reader = graph.size() - 1;
+
+ // Writes to blocks 1, 2, 4
+ extents.clear();
+ graph_utils::AppendBlockToExtents(&extents, 1);
+ graph_utils::AppendBlockToExtents(&extents, 2);
+ graph_utils::AppendBlockToExtents(&extents, 4);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ blocks[1].writer = graph.size() - 1;
+ blocks[2].writer = graph.size() - 1;
+ blocks[4].writer = graph.size() - 1;
+ }
+ {
+ graph.resize(graph.size() + 1);
+ 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);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_src_extents());
+ blocks[1].reader = graph.size() - 1;
+ blocks[2].reader = graph.size() - 1;
+ blocks[4].reader = graph.size() - 1;
+
+ // Writes to blocks 3, 5, 6
+ extents.clear();
+ graph_utils::AppendBlockToExtents(&extents, 3);
+ graph_utils::AppendBlockToExtents(&extents, 5);
+ graph_utils::AppendBlockToExtents(&extents, 6);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ blocks[3].writer = graph.size() - 1;
+ blocks[5].writer = graph.size() - 1;
+ blocks[6].writer = graph.size() - 1;
+ }
+
+ // Create edges
+ InplaceGenerator::CreateEdges(&graph, blocks);
+
+ // Find cycles
+ CycleBreaker cycle_breaker;
+ set<Edge> cut_edges;
+ cycle_breaker.BreakCycles(graph, &cut_edges);
+
+ EXPECT_EQ(1, cut_edges.size());
+ EXPECT_TRUE(cut_edges.end() != cut_edges.find(
+ std::pair<Vertex::Index, Vertex::Index>(1, 0)));
+
+ vector<CutEdgeVertexes> cuts;
+ EXPECT_TRUE(InplaceGenerator::CutEdges(&graph, cut_edges, &cuts));
+
+ EXPECT_EQ(3, graph.size());
+
+ // Check new node in graph:
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
+ graph.back().op.type());
+ EXPECT_EQ(2, graph.back().op.src_extents_size());
+ EXPECT_EQ(1, graph.back().op.dst_extents_size());
+ EXPECT_EQ(kTempBlockStart, graph.back().op.dst_extents(0).start_block());
+ EXPECT_EQ(2, graph.back().op.dst_extents(0).num_blocks());
+ EXPECT_TRUE(graph.back().out_edges.empty());
+
+ // Check that old node reads from new blocks
+ EXPECT_EQ(2, graph[0].op.src_extents_size());
+ EXPECT_EQ(kTempBlockStart, graph[0].op.src_extents(0).start_block());
+ EXPECT_EQ(2, graph[0].op.src_extents(0).num_blocks());
+ EXPECT_EQ(7, graph[0].op.src_extents(1).start_block());
+ EXPECT_EQ(1, graph[0].op.src_extents(1).num_blocks());
+
+ // And that the old dst extents haven't changed
+ EXPECT_EQ(2, graph[0].op.dst_extents_size());
+ EXPECT_EQ(1, graph[0].op.dst_extents(0).start_block());
+ EXPECT_EQ(2, graph[0].op.dst_extents(0).num_blocks());
+ EXPECT_EQ(4, graph[0].op.dst_extents(1).start_block());
+ EXPECT_EQ(1, graph[0].op.dst_extents(1).num_blocks());
+
+ // Ensure it only depends on the next node and the new temp node
+ EXPECT_EQ(2, graph[0].out_edges.size());
+ EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(1));
+ EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(graph.size() -
+ 1));
+
+ // Check second node has unchanged extents
+ EXPECT_EQ(2, graph[1].op.src_extents_size());
+ EXPECT_EQ(1, graph[1].op.src_extents(0).start_block());
+ EXPECT_EQ(2, graph[1].op.src_extents(0).num_blocks());
+ EXPECT_EQ(4, graph[1].op.src_extents(1).start_block());
+ EXPECT_EQ(1, graph[1].op.src_extents(1).num_blocks());
+
+ EXPECT_EQ(2, graph[1].op.dst_extents_size());
+ EXPECT_EQ(3, graph[1].op.dst_extents(0).start_block());
+ EXPECT_EQ(1, graph[1].op.dst_extents(0).num_blocks());
+ EXPECT_EQ(5, graph[1].op.dst_extents(1).start_block());
+ EXPECT_EQ(2, graph[1].op.dst_extents(1).num_blocks());
+
+ // Ensure it only depends on the next node
+ EXPECT_EQ(1, graph[1].out_edges.size());
+ EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2));
+}
+
+TEST_F(InplaceGeneratorTest, RunAsRootAssignTempBlocksReuseTest) {
+ // AssignTempBlocks(Graph* graph,
+ // const string& new_root,
+ // int data_fd,
+ // off_t* data_file_size,
+ // vector<Vertex::Index>* op_indexes,
+ // vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
+ // const vector<CutEdgeVertexes>& cuts
+ Graph graph(9);
+
+ const vector<Extent> empt;
+ uint64_t tmp = kTempBlockStart;
+ const string kFilename = "/foo";
+
+ vector<CutEdgeVertexes> cuts;
+ cuts.resize(3);
+
+ // Simple broken loop:
+ GenVertex(&graph[0], VectOfExt(0, 1), VectOfExt(1, 1), "", OP_MOVE);
+ GenVertex(&graph[1], VectOfExt(tmp, 1), VectOfExt(0, 1), "", OP_MOVE);
+ GenVertex(&graph[2], VectOfExt(1, 1), VectOfExt(tmp, 1), "", OP_MOVE);
+ // Corresponding edges:
+ graph[0].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
+ graph[1].out_edges[2] = EdgeWithWriteDep(VectOfExt(tmp, 1));
+ graph[1].out_edges[0] = EdgeWithReadDep(VectOfExt(0, 1));
+ // Store the cut:
+ cuts[0].old_dst = 1;
+ cuts[0].old_src = 0;
+ cuts[0].new_vertex = 2;
+ cuts[0].tmp_extents = VectOfExt(tmp, 1);
+ tmp++;
+
+ // Slightly more complex pair of loops:
+ GenVertex(&graph[3], VectOfExt(4, 2), VectOfExt(2, 2), "", OP_MOVE);
+ GenVertex(&graph[4], VectOfExt(6, 1), VectOfExt(7, 1), "", OP_MOVE);
+ GenVertex(&graph[5], VectOfExt(tmp, 3), VectOfExt(4, 3), kFilename, OP_MOVE);
+ GenVertex(&graph[6], VectOfExt(2, 2), VectOfExt(tmp, 2), "", OP_MOVE);
+ GenVertex(&graph[7], VectOfExt(7, 1), VectOfExt(tmp + 2, 1), "", OP_MOVE);
+ // Corresponding edges:
+ graph[3].out_edges[6] = EdgeWithReadDep(VectOfExt(2, 2));
+ graph[4].out_edges[7] = EdgeWithReadDep(VectOfExt(7, 1));
+ graph[5].out_edges[6] = EdgeWithWriteDep(VectOfExt(tmp, 2));
+ graph[5].out_edges[7] = EdgeWithWriteDep(VectOfExt(tmp + 2, 1));
+ graph[5].out_edges[3] = EdgeWithReadDep(VectOfExt(4, 2));
+ graph[5].out_edges[4] = EdgeWithReadDep(VectOfExt(6, 1));
+ // Store the cuts:
+ cuts[1].old_dst = 5;
+ cuts[1].old_src = 3;
+ cuts[1].new_vertex = 6;
+ cuts[1].tmp_extents = VectOfExt(tmp, 2);
+ cuts[2].old_dst = 5;
+ cuts[2].old_src = 4;
+ cuts[2].new_vertex = 7;
+ cuts[2].tmp_extents = VectOfExt(tmp + 2, 1);
+
+ // Supplier of temp block:
+ GenVertex(&graph[8], empt, VectOfExt(8, 1), "", OP_REPLACE);
+
+ // Specify the final order:
+ vector<Vertex::Index> op_indexes;
+ op_indexes.push_back(2);
+ op_indexes.push_back(0);
+ op_indexes.push_back(1);
+ op_indexes.push_back(6);
+ op_indexes.push_back(3);
+ op_indexes.push_back(7);
+ op_indexes.push_back(4);
+ op_indexes.push_back(5);
+ op_indexes.push_back(8);
+
+ vector<vector<Vertex::Index>::size_type> reverse_op_indexes;
+ InplaceGenerator::GenerateReverseTopoOrderMap(op_indexes,
+ &reverse_op_indexes);
+
+ // Prepare the filesystem with the minimum required for this to work
+ string temp_dir;
+ EXPECT_TRUE(utils::MakeTempDirectory("AssignTempBlocksReuseTest.XXXXXX",
+ &temp_dir));
+ ScopedDirRemover temp_dir_remover(temp_dir);
+
+ chromeos::Blob temp_data(kBlockSize * 3);
+ test_utils::FillWithData(&temp_data);
+ EXPECT_TRUE(test_utils::WriteFileVector(temp_dir + kFilename, temp_data));
+ ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
+
+ int fd;
+ EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksReuseTest.XXXXXX",
+ nullptr,
+ &fd));
+ ScopedFdCloser fd_closer(&fd);
+ off_t data_file_size = 0;
+
+ EXPECT_TRUE(InplaceGenerator::AssignTempBlocks(&graph,
+ temp_dir,
+ fd,
+ &data_file_size,
+ &op_indexes,
+ &reverse_op_indexes,
+ cuts));
+ EXPECT_FALSE(graph[6].valid);
+ EXPECT_FALSE(graph[7].valid);
+ EXPECT_EQ(1, graph[1].op.src_extents_size());
+ EXPECT_EQ(2, graph[1].op.src_extents(0).start_block());
+ EXPECT_EQ(1, graph[1].op.src_extents(0).num_blocks());
+ EXPECT_EQ(OP_REPLACE_BZ, graph[5].op.type());
+}
+
+TEST_F(InplaceGeneratorTest, MoveFullOpsToBackTest) {
+ Graph graph(4);
+ graph[0].file_name = "A";
+ graph[0].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+ graph[1].file_name = "B";
+ graph[1].op.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
+ graph[2].file_name = "C";
+ graph[2].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+ graph[3].file_name = "D";
+ graph[3].op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+
+ vector<Vertex::Index> vect(graph.size());
+
+ for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) {
+ vect[i] = i;
+ }
+ InplaceGenerator::MoveFullOpsToBack(&graph, &vect);
+ EXPECT_EQ(vect.size(), graph.size());
+ EXPECT_EQ(graph[vect[0]].file_name, "B");
+ EXPECT_EQ(graph[vect[1]].file_name, "D");
+ EXPECT_EQ(graph[vect[2]].file_name, "A");
+ EXPECT_EQ(graph[vect[3]].file_name, "C");
+}
+
+TEST_F(InplaceGeneratorTest, RunAsRootAssignTempBlocksTest) {
+ Graph graph(9);
+ const vector<Extent> empt; // empty
+ const string kFilename = "/foo";
+
+ // Some scratch space:
+ GenVertex(&graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
+ GenVertex(&graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
+ GenVertex(&graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
+
+ // A cycle that requires 10 blocks to break:
+ GenVertex(&graph[3], VectOfExt(10, 11), VectOfExt(0, 9), "", OP_BSDIFF);
+ graph[3].out_edges[4] = EdgeWithReadDep(VectOfExt(0, 9));
+ GenVertex(&graph[4], VectOfExt(0, 9), VectOfExt(10, 11), "", OP_BSDIFF);
+ graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
+
+ // A cycle that requires 9 blocks to break:
+ GenVertex(&graph[5], VectOfExt(40, 11), VectOfExt(30, 10), "", OP_BSDIFF);
+ graph[5].out_edges[6] = EdgeWithReadDep(VectOfExt(30, 10));
+ GenVertex(&graph[6], VectOfExt(30, 10), VectOfExt(40, 11), "", OP_BSDIFF);
+ graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
+
+ // A cycle that requires 40 blocks to break (which is too many):
+ GenVertex(&graph[7],
+ VectOfExt(120, 50),
+ VectOfExt(60, 40),
+ "",
+ OP_BSDIFF);
+ graph[7].out_edges[8] = EdgeWithReadDep(VectOfExt(60, 40));
+ GenVertex(&graph[8],
+ VectOfExt(60, 40),
+ VectOfExt(120, 50),
+ kFilename,
+ OP_BSDIFF);
+ graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
+
+ graph_utils::DumpGraph(graph);
+
+ vector<Vertex::Index> final_order;
+
+
+ // Prepare the filesystem with the minimum required for this to work
+ string temp_dir;
+ EXPECT_TRUE(utils::MakeTempDirectory("AssignTempBlocksTest.XXXXXX",
+ &temp_dir));
+ ScopedDirRemover temp_dir_remover(temp_dir);
+
+ chromeos::Blob temp_data(kBlockSize * 50);
+ test_utils::FillWithData(&temp_data);
+ EXPECT_TRUE(test_utils::WriteFileVector(temp_dir + kFilename, temp_data));
+ ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
+
+ int fd;
+ EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksTestData.XXXXXX",
+ nullptr,
+ &fd));
+ ScopedFdCloser fd_closer(&fd);
+ off_t data_file_size = 0;
+
+
+ EXPECT_TRUE(InplaceGenerator::ConvertGraphToDag(&graph,
+ temp_dir,
+ fd,
+ &data_file_size,
+ &final_order,
+ Vertex::kInvalidIndex));
+
+
+ Graph expected_graph(12);
+ GenVertex(&expected_graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
+ GenVertex(&expected_graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
+ GenVertex(&expected_graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
+ GenVertex(&expected_graph[3],
+ VectOfExt(10, 11),
+ VectOfExt(0, 9),
+ "",
+ OP_BSDIFF);
+ expected_graph[3].out_edges[9] = EdgeWithReadDep(VectOfExt(0, 9));
+ GenVertex(&expected_graph[4],
+ VectOfExt(60, 9),
+ VectOfExt(10, 11),
+ "",
+ OP_BSDIFF);
+ expected_graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
+ expected_graph[4].out_edges[9] = EdgeWithWriteDep(VectOfExt(60, 9));
+ GenVertex(&expected_graph[5],
+ VectOfExt(40, 11),
+ VectOfExt(30, 10),
+ "",
+ OP_BSDIFF);
+ expected_graph[5].out_edges[10] = EdgeWithReadDep(VectOfExt(30, 10));
+
+ GenVertex(&expected_graph[6],
+ VectOfExt(60, 10),
+ VectOfExt(40, 11),
+ "",
+ OP_BSDIFF);
+ expected_graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
+ expected_graph[6].out_edges[10] = EdgeWithWriteDep(VectOfExt(60, 10));
+
+ GenVertex(&expected_graph[7],
+ VectOfExt(120, 50),
+ VectOfExt(60, 40),
+ "",
+ OP_BSDIFF);
+ expected_graph[7].out_edges[6] = EdgeWithReadDep(VectOfExt(60, 10));
+
+ GenVertex(&expected_graph[8], empt, VectOfExt(0, 50), "/foo", OP_REPLACE_BZ);
+ expected_graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
+
+ GenVertex(&expected_graph[9],
+ VectOfExt(0, 9),
+ VectOfExt(60, 9),
+ "",
+ OP_MOVE);
+
+ GenVertex(&expected_graph[10],
+ VectOfExt(30, 10),
+ VectOfExt(60, 10),
+ "",
+ OP_MOVE);
+ expected_graph[10].out_edges[4] = EdgeWithReadDep(VectOfExt(60, 9));
+
+ EXPECT_EQ(12, graph.size());
+ EXPECT_FALSE(graph.back().valid);
+ for (Graph::size_type i = 0; i < graph.size() - 1; i++) {
+ EXPECT_TRUE(graph[i].out_edges == expected_graph[i].out_edges);
+ if (i == 8) {
+ // special case
+ } else {
+ // EXPECT_TRUE(graph[i] == expected_graph[i]) << "i = " << i;
+ }
+ }
+}
+
+// Test that sparse holes are not used as scratch. More specifically, test that
+// if all full operations write to sparse holes and there's no extra scratch
+// space, delta operations that need scratch are converted to full. See
+// crbug.com/238440.
+TEST_F(InplaceGeneratorTest, RunAsRootNoSparseAsTempTest) {
+ Graph graph(3);
+ const vector<Extent> kEmpty;
+ const string kFilename = "/foo";
+
+ // Make sure this sparse hole is not used as scratch.
+ GenVertex(&graph[0], kEmpty, VectOfExt(kSparseHole, 1), "", OP_REPLACE);
+
+ // Create a single-block cycle.
+ GenVertex(&graph[1], VectOfExt(0, 1), VectOfExt(1, 1), "", OP_BSDIFF);
+ graph[1].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
+ GenVertex(&graph[2], VectOfExt(1, 1), VectOfExt(0, 1), kFilename, OP_BSDIFF);
+ graph[2].out_edges[1] = EdgeWithReadDep(VectOfExt(0, 1));
+
+ graph_utils::DumpGraph(graph);
+
+ vector<Vertex::Index> final_order;
+
+ // Prepare the filesystem with the minimum required for this to work.
+ string temp_dir;
+ EXPECT_TRUE(utils::MakeTempDirectory("NoSparseAsTempTest.XXXXXX",
+ &temp_dir));
+ ScopedDirRemover temp_dir_remover(temp_dir);
+
+ chromeos::Blob temp_data(kBlockSize);
+ test_utils::FillWithData(&temp_data);
+ EXPECT_TRUE(test_utils::WriteFileVector(temp_dir + kFilename, temp_data));
+ ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
+
+ int fd = -1;
+ EXPECT_TRUE(utils::MakeTempFile("NoSparseAsTempTestData.XXXXXX",
+ nullptr,
+ &fd));
+ ScopedFdCloser fd_closer(&fd);
+ off_t data_file_size = 0;
+
+ EXPECT_TRUE(InplaceGenerator::ConvertGraphToDag(&graph,
+ temp_dir,
+ fd,
+ &data_file_size,
+ &final_order,
+ Vertex::kInvalidIndex));
+
+ ASSERT_EQ(4, graph.size());
+
+ // The second BSDIFF operation must have been converted to a full operation
+ // (due to insufficient scratch space).
+ EXPECT_TRUE(graph[2].op.type() == OP_REPLACE ||
+ graph[2].op.type() == OP_REPLACE_BZ);
+
+ // The temporary node created for breaking the cycle must have been marked as
+ // invalid.
+ EXPECT_FALSE(graph[3].valid);
+}
+
+// Test that sparse holes are not used as scratch. More specifically, test that
+// if scratch space comes only from full operations writing to real blocks as
+// well as sparse holes, only the real blocks are utilized. See
+// crbug.com/238440.
+TEST_F(InplaceGeneratorTest, NoSparseAsTempTest) {
+ Graph graph;
+ vector<Block> blocks(4);
+
+ // Create nodes in |graph|.
+ {
+ graph.resize(graph.size() + 1);
+ graph.back().op.set_type(
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+
+ // Write to a sparse hole -- basically a no-op to ensure sparse holes are
+ // not used as scratch.
+ vector<Extent> extents;
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ }
+ {
+ graph.resize(graph.size() + 1);
+ graph.back().op.set_type(OP_REPLACE);
+
+ // Scratch space: write to block 0 with sparse holes around.
+ vector<Extent> extents;
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ graph_utils::AppendBlockToExtents(&extents, 0);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ blocks[0].writer = graph.size() - 1;
+ }
+ {
+ graph.resize(graph.size() + 1);
+ graph.back().op.set_type(OP_REPLACE);
+
+ // Write to a sparse hole.
+ vector<Extent> extents;
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ }
+ // Create a two-node cycle between (2, sparse, sparse) and (1, sparse, 3).
+ {
+ graph.resize(graph.size() + 1);
+ graph.back().op.set_type(OP_MOVE);
+ // Read from (2, sparse, sparse).
+ vector<Extent> extents;
+ graph_utils::AppendBlockToExtents(&extents, 2);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_src_extents());
+ blocks[2].reader = graph.size() - 1;
+
+ // Write to (1, sparse, 3).
+ extents.clear();
+ graph_utils::AppendBlockToExtents(&extents, 1);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ graph_utils::AppendBlockToExtents(&extents, 3);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ blocks[1].writer = graph.size() - 1;
+ blocks[3].writer = graph.size() - 1;
+ }
+ {
+ graph.resize(graph.size() + 1);
+ graph.back().op.set_type(OP_MOVE);
+ // Read from (1, sparse, 3).
+ vector<Extent> extents;
+ graph_utils::AppendBlockToExtents(&extents, 1);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ graph_utils::AppendBlockToExtents(&extents, 3);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_src_extents());
+ blocks[1].reader = graph.size() - 1;
+ blocks[3].reader = graph.size() - 1;
+
+ // Write to (2, sparse, sparse).
+ extents.clear();
+ graph_utils::AppendBlockToExtents(&extents, 2);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ blocks[2].writer = graph.size() - 1;
+ }
+
+ graph_utils::DumpGraph(graph);
+
+ // Create edges
+ InplaceGenerator::CreateEdges(&graph, blocks);
+
+ graph_utils::DumpGraph(graph);
+
+ vector<Vertex::Index> final_order;
+ off_t data_file_size = 0;
+ EXPECT_TRUE(InplaceGenerator::ConvertGraphToDag(&graph,
+ "/non/existent/dir",
+ -1,
+ &data_file_size,
+ &final_order,
+ Vertex::kInvalidIndex));
+
+ // Check for a single temporary node writing to scratch.
+ ASSERT_EQ(6, graph.size());
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
+ graph[5].op.type());
+ EXPECT_EQ(1, graph[5].op.src_extents_size());
+ ASSERT_EQ(1, graph[5].op.dst_extents_size());
+ EXPECT_EQ(0, graph[5].op.dst_extents(0).start_block());
+ EXPECT_EQ(1, graph[5].op.dst_extents(0).num_blocks());
+
+ // Make sure the cycle nodes still read from and write to sparse holes.
+ for (int i = 3; i < 5; i++) {
+ ASSERT_GE(graph[i].op.src_extents_size(), 2);
+ EXPECT_EQ(kSparseHole, graph[i].op.src_extents(1).start_block());
+ ASSERT_GE(graph[i].op.dst_extents_size(), 2);
+ EXPECT_EQ(kSparseHole, graph[i].op.dst_extents(1).start_block());
+ }
+}
+
+TEST_F(InplaceGeneratorTest, CreateScratchNodeTest) {
+ Vertex vertex;
+ InplaceGenerator::CreateScratchNode(12, 34, &vertex);
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ,
+ vertex.op.type());
+ EXPECT_EQ(0, vertex.op.data_offset());
+ EXPECT_EQ(0, vertex.op.data_length());
+ EXPECT_EQ(1, vertex.op.dst_extents_size());
+ EXPECT_EQ(12, vertex.op.dst_extents(0).start_block());
+ EXPECT_EQ(34, vertex.op.dst_extents(0).num_blocks());
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/metadata.cc b/payload_generator/metadata.cc
index 7a6493c..a96071a 100644
--- a/payload_generator/metadata.cc
+++ b/payload_generator/metadata.cc
@@ -19,6 +19,7 @@
#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/inplace_generator.h"
#include "update_engine/utils.h"
using base::StringPrintf;
@@ -192,7 +193,7 @@
CHECK((*graph)[vertex].op.has_type());
(*graph)[vertex].file_name = metadata_name;
- TEST_AND_RETURN_FALSE(DeltaDiffGenerator::AddInstallOpToBlocksVector(
+ TEST_AND_RETURN_FALSE(InplaceGenerator::AddInstallOpToBlocksVector(
(*graph)[vertex].op,
*graph,
vertex,
diff --git a/update_engine.gyp b/update_engine.gyp
index 4212c5b..6fe642f 100644
--- a/update_engine.gyp
+++ b/update_engine.gyp
@@ -281,6 +281,7 @@
'payload_generator/filesystem_iterator.cc',
'payload_generator/full_update_generator.cc',
'payload_generator/graph_utils.cc',
+ 'payload_generator/inplace_generator.cc',
'payload_generator/metadata.cc',
'payload_generator/payload_signer.cc',
'payload_generator/tarjan.cc',
@@ -373,6 +374,7 @@
'payload_generator/filesystem_iterator_unittest.cc',
'payload_generator/full_update_generator_unittest.cc',
'payload_generator/graph_utils_unittest.cc',
+ 'payload_generator/inplace_generator_unittest.cc',
'payload_generator/metadata_unittest.cc',
'payload_generator/payload_signer_unittest.cc',
'payload_generator/tarjan_unittest.cc',