//
// Copyright (C) 2010 The Android Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
#include "update_engine/payload_generator/extent_ranges.h"
#include <vector>
#include <gtest/gtest.h>
#include "update_engine/common/test_utils.h"
#include "update_engine/payload_consumer/payload_constants.h"
#include "update_engine/payload_generator/extent_utils.h"
using std::vector;
namespace chromeos_update_engine {
class ExtentRangesTest : public ::testing::Test {};
namespace {
void ExpectRangeEq(const ExtentRanges& ranges,
const uint64_t* expected,
size_t sz,
int line) {
uint64_t blocks = 0;
for (size_t i = 1; i < sz; i += 2) {
blocks += expected[i];
}
EXPECT_EQ(blocks, ranges.blocks()) << "line: " << line;
const ExtentRanges::ExtentSet& result = ranges.extent_set();
ExtentRanges::ExtentSet::const_iterator it = result.begin();
for (size_t i = 0; i < sz; i += 2) {
EXPECT_FALSE(it == result.end()) << "line: " << line;
EXPECT_EQ(expected[i], it->start_block()) << "line: " << line;
EXPECT_EQ(expected[i + 1], it->num_blocks()) << "line: " << line;
++it;
}
}
#define EXPECT_RANGE_EQ(ranges, var) \
do { \
ExpectRangeEq(ranges, var, arraysize(var), __LINE__); \
} while (0)
void ExpectRangesOverlapOrTouch(uint64_t a_start,
uint64_t a_num,
uint64_t b_start,
uint64_t b_num) {
EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(
ExtentForRange(a_start, a_num), ExtentForRange(b_start, b_num)));
EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(
ExtentForRange(b_start, b_num), ExtentForRange(a_start, a_num)));
}
void ExpectFalseRangesOverlapOrTouch(uint64_t a_start,
uint64_t a_num,
uint64_t b_start,
uint64_t b_num) {
EXPECT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(
ExtentForRange(a_start, a_num), ExtentForRange(b_start, b_num)));
EXPECT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(
ExtentForRange(b_start, b_num), ExtentForRange(a_start, a_num)));
EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start, a_num),
ExtentForRange(b_start, b_num)));
EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start, b_num),
ExtentForRange(a_start, a_num)));
}
void ExpectRangesOverlap(uint64_t a_start,
uint64_t a_num,
uint64_t b_start,
uint64_t b_num) {
EXPECT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start, a_num),
ExtentForRange(b_start, b_num)));
EXPECT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start, b_num),
ExtentForRange(a_start, a_num)));
EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(
ExtentForRange(a_start, a_num), ExtentForRange(b_start, b_num)));
EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(
ExtentForRange(b_start, b_num), ExtentForRange(a_start, a_num)));
}
void ExpectFalseRangesOverlap(uint64_t a_start,
uint64_t a_num,
uint64_t b_start,
uint64_t b_num) {
EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start, a_num),
ExtentForRange(b_start, b_num)));
EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start, b_num),
ExtentForRange(a_start, a_num)));
}
} // namespace
TEST(ExtentRangesTest, ExtentsOverlapTest) {
ExpectRangesOverlapOrTouch(10, 20, 30, 10);
ExpectRangesOverlap(10, 20, 25, 10);
ExpectFalseRangesOverlapOrTouch(10, 20, 35, 10);
ExpectFalseRangesOverlap(10, 20, 30, 10);
ExpectRangesOverlap(12, 4, 12, 3);
ExpectRangesOverlapOrTouch(kSparseHole, 2, kSparseHole, 3);
ExpectRangesOverlap(kSparseHole, 2, kSparseHole, 3);
ExpectFalseRangesOverlapOrTouch(kSparseHole, 2, 10, 3);
ExpectFalseRangesOverlapOrTouch(10, 2, kSparseHole, 3);
ExpectFalseRangesOverlap(kSparseHole, 2, 10, 3);
ExpectFalseRangesOverlap(10, 2, kSparseHole, 3);
}
TEST(ExtentRangesTest, SimpleTest) {
ExtentRanges ranges;
{
static const uint64_t expected[] = {};
// Can't use arraysize() on 0-length arrays:
ExpectRangeEq(ranges, expected, 0, __LINE__);
}
ranges.SubtractBlock(2);
{
static const uint64_t expected[] = {};
// Can't use arraysize() on 0-length arrays:
ExpectRangeEq(ranges, expected, 0, __LINE__);
}
ranges.AddBlock(0);
ranges.Dump();
ranges.AddBlock(1);
ranges.AddBlock(3);
{
static const uint64_t expected[] = {0, 2, 3, 1};
EXPECT_RANGE_EQ(ranges, expected);
}
ranges.AddBlock(2);
{
static const uint64_t expected[] = {0, 4};
EXPECT_RANGE_EQ(ranges, expected);
ranges.AddBlock(kSparseHole);
EXPECT_RANGE_EQ(ranges, expected);
ranges.SubtractBlock(kSparseHole);
EXPECT_RANGE_EQ(ranges, expected);
}
ranges.SubtractBlock(2);
{
static const uint64_t expected[] = {0, 2, 3, 1};
EXPECT_RANGE_EQ(ranges, expected);
}
for (uint64_t i = 100; i < 1000; i += 100) {
ranges.AddExtent(ExtentForRange(i, 50));
}
{
static const uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 50,
300, 50, 400, 50, 500, 50, 600, 50,
700, 50, 800, 50, 900, 50};
EXPECT_RANGE_EQ(ranges, expected);
}
ranges.SubtractExtent(ExtentForRange(210, 410 - 210));
{
static const uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200,
10, 410, 40, 500, 50, 600, 50,
700, 50, 800, 50, 900, 50};
EXPECT_RANGE_EQ(ranges, expected);
}
ranges.AddExtent(ExtentForRange(100000, 0));
{
static const uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200,
10, 410, 40, 500, 50, 600, 50,
700, 50, 800, 50, 900, 50};
EXPECT_RANGE_EQ(ranges, expected);
}
ranges.SubtractExtent(ExtentForRange(3, 0));
{
static const uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200,
10, 410, 40, 500, 50, 600, 50,
700, 50, 800, 50, 900, 50};
EXPECT_RANGE_EQ(ranges, expected);
}
}
TEST(ExtentRangesTest, MultipleRanges) {
ExtentRanges ranges_a, ranges_b;
ranges_a.AddBlock(0);
ranges_b.AddBlock(4);
ranges_b.AddBlock(3);
{
uint64_t expected[] = {3, 2};
EXPECT_RANGE_EQ(ranges_b, expected);
}
ranges_a.AddRanges(ranges_b);
{
uint64_t expected[] = {0, 1, 3, 2};
EXPECT_RANGE_EQ(ranges_a, expected);
}
ranges_a.SubtractRanges(ranges_b);
{
uint64_t expected[] = {0, 1};
EXPECT_RANGE_EQ(ranges_a, expected);
}
{
uint64_t expected[] = {3, 2};
EXPECT_RANGE_EQ(ranges_b, expected);
}
}
TEST(ExtentRangesTest, GetExtentsForBlockCountTest) {
ExtentRanges ranges;
ranges.AddExtents(vector<Extent>(1, ExtentForRange(10, 30)));
{
vector<Extent> zero_extents = ranges.GetExtentsForBlockCount(0);
EXPECT_TRUE(zero_extents.empty());
}
::google::protobuf::RepeatedPtrField<Extent> rep_field;
*rep_field.Add() = ExtentForRange(30, 40);
ranges.AddRepeatedExtents(rep_field);
ranges.SubtractExtents(vector<Extent>(1, ExtentForRange(20, 10)));
*rep_field.Mutable(0) = ExtentForRange(50, 10);
ranges.SubtractRepeatedExtents(rep_field);
EXPECT_EQ(40U, ranges.blocks());
for (int i = 0; i < 2; i++) {
vector<Extent> expected(2);
expected[0] = ExtentForRange(10, 10);
expected[1] = ExtentForRange(30, i == 0 ? 10 : 20);
vector<Extent> actual =
ranges.GetExtentsForBlockCount(10 + expected[1].num_blocks());
EXPECT_EQ(expected.size(), actual.size());
for (vector<Extent>::size_type j = 0, e = expected.size(); j != e; ++j) {
EXPECT_EQ(expected[j].start_block(), actual[j].start_block())
<< "j = " << j;
EXPECT_EQ(expected[j].num_blocks(), actual[j].num_blocks())
<< "j = " << j;
}
}
}
TEST(ExtentRangesTest, ContainsBlockTest) {
ExtentRanges ranges;
EXPECT_FALSE(ranges.ContainsBlock(123));
ranges.AddExtent(ExtentForRange(10, 10));
ranges.AddExtent(ExtentForRange(100, 1));
EXPECT_FALSE(ranges.ContainsBlock(9));
EXPECT_TRUE(ranges.ContainsBlock(10));
EXPECT_TRUE(ranges.ContainsBlock(15));
EXPECT_TRUE(ranges.ContainsBlock(19));
EXPECT_FALSE(ranges.ContainsBlock(20));
// Test for an extent with just the block we are requesting.
EXPECT_FALSE(ranges.ContainsBlock(99));
EXPECT_TRUE(ranges.ContainsBlock(100));
EXPECT_FALSE(ranges.ContainsBlock(101));
}
TEST(ExtentRangesTest, FilterExtentRangesEmptyRanges) {
ExtentRanges ranges;
EXPECT_EQ(vector<Extent>(), FilterExtentRanges(vector<Extent>(), ranges));
EXPECT_EQ(vector<Extent>{ExtentForRange(50, 10)},
FilterExtentRanges(vector<Extent>{ExtentForRange(50, 10)}, ranges));
// Check that the empty Extents are ignored.
EXPECT_EQ((vector<Extent>{ExtentForRange(10, 10), ExtentForRange(20, 10)}),
FilterExtentRanges(vector<Extent>{ExtentForRange(10, 10),
ExtentForRange(3, 0),
ExtentForRange(20, 10)},
ranges));
}
TEST(ExtentRangesTest, FilterExtentRangesMultipleRanges) {
// Two overlapping extents, with three ranges to remove.
vector<Extent> extents{ExtentForRange(10, 100), ExtentForRange(30, 100)};
ExtentRanges ranges;
// This overlaps the beginning of the second extent.
ranges.AddExtent(ExtentForRange(28, 3));
ranges.AddExtent(ExtentForRange(50, 10));
ranges.AddExtent(ExtentForRange(70, 10));
// This overlaps the end of the second extent.
ranges.AddExtent(ExtentForRange(108, 6));
EXPECT_EQ((vector<Extent>{// For the first extent:
ExtentForRange(10, 18),
ExtentForRange(31, 19),
ExtentForRange(60, 10),
ExtentForRange(80, 28),
// For the second extent:
ExtentForRange(31, 19),
ExtentForRange(60, 10),
ExtentForRange(80, 28),
ExtentForRange(114, 16)}),
FilterExtentRanges(extents, ranges));
}
TEST(ExtentRangesTest, FilterExtentRangesOvelapping) {
ExtentRanges ranges;
ranges.AddExtent(ExtentForRange(10, 3));
ranges.AddExtent(ExtentForRange(20, 5));
// Requested extent overlaps with one of the ranges.
EXPECT_EQ(vector<Extent>(),
FilterExtentRanges(
vector<Extent>{ExtentForRange(10, 1), ExtentForRange(22, 1)},
ranges));
}
} // namespace chromeos_update_engine