From 160514bf2bac2ad8b1af6cb5a72d88439596ada1 Mon Sep 17 00:00:00 2001
From: Tao Bao <tbao@google.com>
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 ++++++++++++++++++++++++++++++++++++++
 2 files changed, 48 insertions(+)

(limited to 'otautil')

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<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 532cba4a8..96955b9d0 100644
--- a/otautil/rangeset.cpp
+++ b/otautil/rangeset.cpp
@@ -103,6 +103,46 @@ void RangeSet::Clear() {
   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 "";
-- 
cgit v1.2.3