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
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));