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/rangeset.cpp | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) (limited to 'otautil/rangeset.cpp') 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 ""; -- cgit v1.2.3