[PATCH 6/8] ktest/config-bisect: Try harder to find a new config

[Scott Wood <swood@redhat.com>]

From: Scott Wood <oss@buserror.net>

It's possible that the arbitrarily chosen half of the config differences
fails to make any actual difference in the output config, due to options
that are present in .config but not independently changeable (e.g. the
mutually-exclusive symbols of a "choice" kconfig construct, or a symbol
that has been "select"ed by another).

Try harder to generate a new and different config by randomizing the key
order and bisection percentage, and repeating a few times.

Explicitly randomizing also makes it possible to skip a broken generated
config by simply calling the script again, even on older versions of Perl
that didn't automatically randomize hash order.

Signed-off-by: Scott Wood <swood@redhat.com>
---
 tools/testing/ktest/config-bisect.pl | 41 +++++++++++++++++++++---------------
 1 file changed, 24 insertions(+), 17 deletions(-)

diff --git a/tools/testing/ktest/config-bisect.pl b/tools/testing/ktest/config-bisect.pl
index 63a3a940b5de..54f27b45079f 100755
--- a/tools/testing/ktest/config-bisect.pl
+++ b/tools/testing/ktest/config-bisect.pl
@@ -5,6 +5,7 @@
 #
 
 use strict;
+use List::Util qw(shuffle);
 
 my $outputdir;
 
@@ -153,9 +154,11 @@ sub run_config_bisect {
 	my @diff_arr = diff_config_vals \%good_configs, \%bad_configs;
 	my $len_diff = $#diff_arr + 1;
 
-	my $runtest = 1;
+	my $rand_tries = 10;
+	my $runtest = 0;
 	my %new_configs;
 	my $ret;
+	my $count = 0;
 
 	print "d=$len_diff\n";
 
@@ -164,33 +167,37 @@ sub run_config_bisect {
 		exit 2;
 	}
 
-	my %tmp_config = %bad_configs;
-
-	my $half = int($#diff_arr / 2);
-	my @tophalf = @diff_arr[0 .. $half];
-
-	print "Settings bisect with top half:\n";
-	foreach my $item (@tophalf) {
-		$tmp_config{$item} = $good_configs{$item};
-	}
+	while ($runtest == 0 && ++$count <= $rand_tries) {
+		my %tmp_config = %bad_configs;
 
-	$runtest = process_new_config \%tmp_config, \%new_configs,
-		\%good_configs, \%bad_configs, $outfile;
+		# If we fail to generate a new config (due to the top half
+		# configs being unchangeable without the bottom half configs)
+		# then try a few random permutations, and if those fail try
+		# each option one at a time.
 
-	if (!$runtest) {
-		my %tmp_config = %bad_configs;
+		if ($count <= $rand_tries) {
+			@diff_arr = shuffle(@diff_arr);
+		}
 
-		print "Try bottom half\n";
+		my $half = int($#diff_arr / 2);
+		if ($count > 2) {
+			$half = int(rand($#diff_arr));
+		}
 
-		my @bottomhalf = @diff_arr[$half+1 .. $#diff_arr];
+		my @tophalf = @diff_arr[0 .. $half];
 
-		foreach my $item (@bottomhalf) {
+		foreach my $item (@tophalf) {
 			$tmp_config{$item} = $good_configs{$item};
 		}
 
 		$runtest = process_new_config \%tmp_config, \%new_configs,
 				\%good_configs, \%bad_configs, $outfile;
 	}
+
+	if ($runtest == 0) {
+		print "$0: No more bisecting possible\n";
+		exit 2;
+	}
 }
 
 sub cb_by_file {
-- 
2.9.4