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 --- tests/unit/rangeset_test.cpp | 80 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 80 insertions(+) (limited to 'tests/unit') 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)); -- cgit v1.2.3