Merge "Load-balancing update_verifier worker threads."
diff --git a/otautil/include/otautil/rangeset.h b/otautil/include/otautil/rangeset.h
index af8ae2d..e91d02c 100644
--- a/otautil/include/otautil/rangeset.h
+++ b/otautil/include/otautil/rangeset.h
@@ -49,6 +49,14 @@
// bounds. For example, "3,5" contains blocks 3 and 4. So "3,5" and "5,7" are not overlapped.
bool Overlaps(const RangeSet& other) const;
+ // Returns a vector of RangeSets that contain the same set of blocks represented by the current
+ // RangeSet. The RangeSets in the vector contain similar number of blocks, with a maximum delta
+ // of 1-block between any two of them. For example, 14 blocks would be split into 4 + 4 + 3 + 3,
+ // as opposed to 4 + 4 + 4 + 2. If the total number of blocks (T) is less than groups, it
+ // returns a vector of T 1-block RangeSets. Otherwise the number of the returned RangeSets must
+ // equal to groups. The current RangeSet remains intact after the split.
+ std::vector<RangeSet> Split(size_t groups) const;
+
// Returns the number of Range's in this RangeSet.
size_t size() const {
return ranges_.size();
diff --git a/otautil/rangeset.cpp b/otautil/rangeset.cpp
index 532cba4..96955b9 100644
--- a/otautil/rangeset.cpp
+++ b/otautil/rangeset.cpp
@@ -103,6 +103,46 @@
blocks_ = 0;
}
+std::vector<RangeSet> RangeSet::Split(size_t groups) const {
+ if (ranges_.empty() || groups == 0) return {};
+
+ if (blocks_ < groups) {
+ groups = blocks_;
+ }
+
+ // Evenly distribute blocks, with the first few groups possibly containing one more.
+ size_t mean = blocks_ / groups;
+ std::vector<size_t> blocks_per_group(groups, mean);
+ std::fill_n(blocks_per_group.begin(), blocks_ % groups, mean + 1);
+
+ std::vector<RangeSet> result;
+
+ // Forward iterate Ranges and fill up each group with the desired number of blocks.
+ auto it = ranges_.cbegin();
+ Range range = *it;
+ for (const auto& blocks : blocks_per_group) {
+ RangeSet buffer;
+ size_t needed = blocks;
+ while (needed > 0) {
+ size_t range_blocks = range.second - range.first;
+ if (range_blocks > needed) {
+ // Split the current range and don't advance the iterator.
+ buffer.PushBack({ range.first, range.first + needed });
+ range.first = range.first + needed;
+ break;
+ }
+ buffer.PushBack(range);
+ it++;
+ if (it != ranges_.cend()) {
+ range = *it;
+ }
+ needed -= range_blocks;
+ }
+ result.push_back(std::move(buffer));
+ }
+ return result;
+}
+
std::string RangeSet::ToString() const {
if (ranges_.empty()) {
return "";
diff --git a/tests/unit/rangeset_test.cpp b/tests/unit/rangeset_test.cpp
index 5141bb6..7ae193e 100644
--- a/tests/unit/rangeset_test.cpp
+++ b/tests/unit/rangeset_test.cpp
@@ -123,6 +123,86 @@
ASSERT_FALSE(RangeSet::Parse("2,5,7").Overlaps(RangeSet::Parse("2,3,5")));
}
+TEST(RangeSetTest, Split) {
+ RangeSet rs1 = RangeSet::Parse("2,1,2");
+ ASSERT_TRUE(rs1);
+ ASSERT_EQ((std::vector<RangeSet>{ RangeSet::Parse("2,1,2") }), rs1.Split(1));
+
+ RangeSet rs2 = RangeSet::Parse("2,5,10");
+ ASSERT_TRUE(rs2);
+ ASSERT_EQ((std::vector<RangeSet>{ RangeSet::Parse("2,5,8"), RangeSet::Parse("2,8,10") }),
+ rs2.Split(2));
+
+ RangeSet rs3 = RangeSet::Parse("4,0,1,5,10");
+ ASSERT_TRUE(rs3);
+ ASSERT_EQ((std::vector<RangeSet>{ RangeSet::Parse("4,0,1,5,7"), RangeSet::Parse("2,7,10") }),
+ rs3.Split(2));
+
+ RangeSet rs4 = RangeSet::Parse("6,1,3,3,4,4,5");
+ ASSERT_TRUE(rs4);
+ ASSERT_EQ((std::vector<RangeSet>{ RangeSet::Parse("2,1,3"), RangeSet::Parse("2,3,4"),
+ RangeSet::Parse("2,4,5") }),
+ rs4.Split(3));
+
+ RangeSet rs5 = RangeSet::Parse("2,0,10");
+ ASSERT_TRUE(rs5);
+ ASSERT_EQ((std::vector<RangeSet>{ RangeSet::Parse("2,0,3"), RangeSet::Parse("2,3,6"),
+ RangeSet::Parse("2,6,8"), RangeSet::Parse("2,8,10") }),
+ rs5.Split(4));
+
+ RangeSet rs6 = RangeSet::Parse(
+ "20,0,268,269,271,286,447,8350,32770,33022,98306,98558,163842,164094,196609,204800,229378,"
+ "229630,294914,295166,457564");
+ ASSERT_TRUE(rs6);
+ size_t rs6_blocks = rs6.blocks();
+ auto splits = rs6.Split(4);
+ ASSERT_EQ(
+ (std::vector<RangeSet>{
+ RangeSet::Parse("12,0,268,269,271,286,447,8350,32770,33022,98306,98558,118472"),
+ RangeSet::Parse("8,118472,163842,164094,196609,204800,229378,229630,237216"),
+ RangeSet::Parse("4,237216,294914,295166,347516"), RangeSet::Parse("2,347516,457564") }),
+ splits);
+ size_t sum = 0;
+ for (const auto& element : splits) {
+ sum += element.blocks();
+ }
+ ASSERT_EQ(rs6_blocks, sum);
+}
+
+TEST(RangeSetTest, Split_EdgeCases) {
+ // Empty RangeSet.
+ RangeSet rs1;
+ ASSERT_FALSE(rs1);
+ ASSERT_EQ((std::vector<RangeSet>{}), rs1.Split(2));
+ ASSERT_FALSE(rs1);
+
+ // Zero group.
+ RangeSet rs2 = RangeSet::Parse("2,1,5");
+ ASSERT_TRUE(rs2);
+ ASSERT_EQ((std::vector<RangeSet>{}), rs2.Split(0));
+
+ // The number of blocks equals to the number of groups.
+ RangeSet rs3 = RangeSet::Parse("2,1,5");
+ ASSERT_TRUE(rs3);
+ ASSERT_EQ((std::vector<RangeSet>{ RangeSet::Parse("2,1,2"), RangeSet::Parse("2,2,3"),
+ RangeSet::Parse("2,3,4"), RangeSet::Parse("2,4,5") }),
+ rs3.Split(4));
+
+ // Less blocks than the number of groups.
+ RangeSet rs4 = RangeSet::Parse("2,1,5");
+ ASSERT_TRUE(rs4);
+ ASSERT_EQ((std::vector<RangeSet>{ RangeSet::Parse("2,1,2"), RangeSet::Parse("2,2,3"),
+ RangeSet::Parse("2,3,4"), RangeSet::Parse("2,4,5") }),
+ rs4.Split(8));
+
+ // Less blocks than the number of groups.
+ RangeSet rs5 = RangeSet::Parse("2,0,3");
+ ASSERT_TRUE(rs5);
+ ASSERT_EQ((std::vector<RangeSet>{ RangeSet::Parse("2,0,1"), RangeSet::Parse("2,1,2"),
+ RangeSet::Parse("2,2,3") }),
+ rs5.Split(4));
+}
+
TEST(RangeSetTest, GetBlockNumber) {
RangeSet rs = RangeSet::Parse("2,1,10");
ASSERT_EQ(static_cast<size_t>(1), rs.GetBlockNumber(0));
diff --git a/update_verifier/Android.mk b/update_verifier/Android.mk
index 33c5fe9..0ff8854 100644
--- a/update_verifier/Android.mk
+++ b/update_verifier/Android.mk
@@ -22,6 +22,10 @@
update_verifier.cpp
LOCAL_MODULE := libupdate_verifier
+
+LOCAL_STATIC_LIBRARIES := \
+ libotautil
+
LOCAL_SHARED_LIBRARIES := \
libbase \
libcutils \
@@ -54,7 +58,9 @@
LOCAL_MODULE := update_verifier
LOCAL_STATIC_LIBRARIES := \
- libupdate_verifier
+ libupdate_verifier \
+ libotautil
+
LOCAL_SHARED_LIBRARIES := \
libbase \
libcutils \
diff --git a/update_verifier/update_verifier.cpp b/update_verifier/update_verifier.cpp
index ba7b7ae..c5e154f 100644
--- a/update_verifier/update_verifier.cpp
+++ b/update_verifier/update_verifier.cpp
@@ -58,6 +58,8 @@
#include <android/hardware/boot/1.0/IBootControl.h>
#include <cutils/android_reboot.h>
+#include "otautil/rangeset.h"
+
using android::sp;
using android::hardware::boot::V1_0::IBootControl;
using android::hardware::boot::V1_0::BoolResult;
@@ -129,42 +131,33 @@
// followed by 'count' number comma separated integers. Every two integers reprensent a
// block range with the first number included in range but second number not included.
// For example '4,64536,65343,74149,74150' represents: [64536,65343) and [74149,74150).
- std::vector<std::string> ranges = android::base::Split(range_str, ",");
- size_t range_count;
- bool status = android::base::ParseUint(ranges[0], &range_count);
- if (!status || (range_count == 0) || (range_count % 2 != 0) ||
- (range_count != ranges.size() - 1)) {
- LOG(ERROR) << "Error in parsing range string.";
+ RangeSet ranges = RangeSet::Parse(range_str);
+ if (!ranges) {
+ LOG(ERROR) << "Error parsing RangeSet string " << range_str;
return false;
}
- range_count /= 2;
+
+ // RangeSet::Split() splits the ranges into multiple groups with same number of blocks (except for
+ // the last group).
+ size_t thread_num = std::thread::hardware_concurrency() ?: 4;
+ std::vector<RangeSet> groups = ranges.Split(thread_num);
std::vector<std::future<bool>> threads;
- size_t thread_num = std::thread::hardware_concurrency() ?: 4;
- thread_num = std::min(thread_num, range_count);
- size_t group_range_count = (range_count + thread_num - 1) / thread_num;
-
- for (size_t t = 0; t < thread_num; t++) {
- auto thread_func = [t, group_range_count, &dm_block_device, &ranges, &partition]() {
- size_t blk_count = 0;
- static constexpr size_t kBlockSize = 4096;
- std::vector<uint8_t> buf(1024 * kBlockSize);
+ for (const auto& group : groups) {
+ auto thread_func = [&group, &dm_block_device, &partition]() {
android::base::unique_fd fd(TEMP_FAILURE_RETRY(open(dm_block_device.c_str(), O_RDONLY)));
if (fd.get() == -1) {
PLOG(ERROR) << "Error reading " << dm_block_device << " for partition " << partition;
return false;
}
- for (size_t i = group_range_count * 2 * t + 1;
- i < std::min(group_range_count * 2 * (t + 1) + 1, ranges.size()); i += 2) {
- unsigned int range_start, range_end;
- bool parse_status = android::base::ParseUint(ranges[i], &range_start);
- parse_status = parse_status && android::base::ParseUint(ranges[i + 1], &range_end);
- if (!parse_status || range_start >= range_end) {
- LOG(ERROR) << "Invalid range pair " << ranges[i] << ", " << ranges[i + 1];
- return false;
- }
+ static constexpr size_t kBlockSize = 4096;
+ std::vector<uint8_t> buf(1024 * kBlockSize);
+ size_t block_count = 0;
+ for (const auto& range : group) {
+ size_t range_start = range.first;
+ size_t range_end = range.second;
if (lseek64(fd.get(), static_cast<off64_t>(range_start) * kBlockSize, SEEK_SET) == -1) {
PLOG(ERROR) << "lseek to " << range_start << " failed";
return false;
@@ -179,9 +172,9 @@
}
remain -= to_read;
}
- blk_count += (range_end - range_start);
+ block_count += (range_end - range_start);
}
- LOG(INFO) << "Finished reading " << blk_count << " blocks on " << dm_block_device;
+ LOG(INFO) << "Finished reading " << block_count << " blocks on " << dm_block_device;
return true;
};