blob: 1b767f15555f9fb28ee2ba38924d163b8b446161 [file] [log] [blame]
// Copyright (c) 2010 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 <vector>
#include <gtest/gtest.h>
#include "update_engine/extent_ranges.h"
#include "update_engine/test_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(40, 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;
}
}
}
} // namespace chromeos_update_engine