From 160514bf2bac2ad8b1af6cb5a72d88439596ada1 Mon Sep 17 00:00:00 2001 From: Tao Bao Date: Sat, 4 Nov 2017 00:08:08 -0700 Subject: Load-balancing update_verifier worker threads. Prior to this CL, the block verification works were assigned based on the pattern of the ranges, which could lead to unbalanced workloads. This CL adds RangeSet::Split() and moves update_verifier over. a) For the following care_map.txt on walleye: system 20,0,347,348,540,556,32770,33084,98306,98620,163842,164156,229378,229692,294914,295228,524289,524291,524292,524348,529059 vendor 8,0,120,135,32770,32831,94564,98304,98306 Measured the time costs prior to and with this CL with the following script. $ cat test_update_verifier.sh #!/bin/sh adb shell stop adb shell "cp /data/local/tmp/care_map.txt /data/ota_package/" for i in $(seq 1 50) do echo "Iteration: $i" adb shell "bootctl set-active-boot-slot 0" adb shell "echo 3 > /proc/sys/vm/drop_caches" adb shell "time /data/local/tmp/update_verifier" sleep 3 done Without this CL, the average time cost is 5.66s, while with the CL it's reduced to 3.2s. b) For the following care_map.txt, measured the performance on marlin: system 18,0,271,286,457,8350,32770,33022,98306,98558,163842,164094,196609,204800,229378,229630,294914,295166,501547 vendor 10,0,42,44,85,2408,32770,32806,32807,36902,74242 It takes 12.9s and 5.6s without and with the CL respectively. Fixes: 68553827 Test: recovery_unit_test Test: Flash new build and trigger update_verifier. Check the balanced block verification. Change-Id: I5fa4bf09a84e6b9b0975ee5f522724464181333f --- otautil/include/otautil/rangeset.h | 8 ++++ otautil/rangeset.cpp | 40 +++++++++++++++++++ tests/unit/rangeset_test.cpp | 80 +++++++++++++++++++++++++++++++++++++ update_verifier/Android.mk | 8 +++- update_verifier/update_verifier.cpp | 45 +++++++++------------ 5 files changed, 154 insertions(+), 27 deletions(-) diff --git a/otautil/include/otautil/rangeset.h b/otautil/include/otautil/rangeset.h index af8ae2dee..e91d02ca6 100644 --- a/otautil/include/otautil/rangeset.h +++ b/otautil/include/otautil/rangeset.h @@ -49,6 +49,14 @@ class RangeSet { // 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 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 532cba4a8..96955b9d0 100644 --- a/otautil/rangeset.cpp +++ b/otautil/rangeset.cpp @@ -103,6 +103,46 @@ void RangeSet::Clear() { blocks_ = 0; } +std::vector 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 blocks_per_group(groups, mean); + std::fill_n(blocks_per_group.begin(), blocks_ % groups, mean + 1); + + std::vector 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 5141bb67f..7ae193e18 100644 --- a/tests/unit/rangeset_test.cpp +++ b/tests/unit/rangeset_test.cpp @@ -123,6 +123,86 @@ TEST(RangeSetTest, Overlaps) { 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::Parse("2,1,2") }), rs1.Split(1)); + + RangeSet rs2 = RangeSet::Parse("2,5,10"); + ASSERT_TRUE(rs2); + ASSERT_EQ((std::vector{ 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::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::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::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::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{}), rs1.Split(2)); + ASSERT_FALSE(rs1); + + // Zero group. + RangeSet rs2 = RangeSet::Parse("2,1,5"); + ASSERT_TRUE(rs2); + ASSERT_EQ((std::vector{}), 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::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::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::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(1), rs.GetBlockNumber(0)); diff --git a/update_verifier/Android.mk b/update_verifier/Android.mk index 33c5fe9e7..0ff88546f 100644 --- a/update_verifier/Android.mk +++ b/update_verifier/Android.mk @@ -22,6 +22,10 @@ LOCAL_SRC_FILES := \ update_verifier.cpp LOCAL_MODULE := libupdate_verifier + +LOCAL_STATIC_LIBRARIES := \ + libotautil + LOCAL_SHARED_LIBRARIES := \ libbase \ libcutils \ @@ -54,7 +58,9 @@ LOCAL_SRC_FILES := \ 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 ba7b7aec4..c5e154f03 100644 --- a/update_verifier/update_verifier.cpp +++ b/update_verifier/update_verifier.cpp @@ -58,6 +58,8 @@ #include #include +#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 @@ static bool read_blocks(const std::string& partition, const std::string& range_s // 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 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; - std::vector> threads; + // 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; - thread_num = std::min(thread_num, range_count); - size_t group_range_count = (range_count + thread_num - 1) / thread_num; + std::vector groups = ranges.Split(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 buf(1024 * kBlockSize); + std::vector> threads; + 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 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(range_start) * kBlockSize, SEEK_SET) == -1) { PLOG(ERROR) << "lseek to " << range_start << " failed"; return false; @@ -179,9 +172,9 @@ static bool read_blocks(const std::string& partition, const std::string& range_s } 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; }; -- cgit v1.2.3