tools/testing/ktest/config-bisect.pl

   1 #!/usr/bin/perl -w
   2 # SPDX-License-Identifier: GPL-2.0-only
   3 #
   4 # Copyright 2015 - Steven Rostedt, Red Hat Inc.
   5 # Copyright 2017 - Steven Rostedt, VMware, Inc.
   6 #
   7
   8 # usage:
   9 #  config-bisect.pl [options] good-config bad-config [good|bad]
  10 #
  11
  12 # Compares a good config to a bad config, then takes half of the diffs
  13 # and produces a config that is somewhere between the good config and
  14 # the bad config. That is, the resulting config will start with the
  15 # good config and will try to make half of the differences of between
  16 # the good and bad configs match the bad config. It tries because of
  17 # dependencies between the two configs it may not be able to change
  18 # exactly half of the configs that are different between the two config
  19 # files.
  20
  21 # Here's a normal way to use it:
  22 #
  23 #  $ cd /path/to/linux/kernel
  24 #  $ config-bisect.pl /path/to/good/config /path/to/bad/config
  25
  26 # This will now pull in good config (blowing away .config in that directory
  27 # so do not make that be one of the good or bad configs), and then
  28 # build the config with "make oldconfig" to make sure it matches the
  29 # current kernel. It will then store the configs in that result for
  30 # the good config. It does the same for the bad config as well.
  31 # The algorithm will run, merging half of the differences between
  32 # the two configs and building them with "make oldconfig" to make sure
  33 # the result changes (dependencies may reset changes the tool had made).
  34 # It then copies the result of its good config to /path/to/good/config.tmp
  35 # and the bad config to /path/to/bad/config.tmp (just appends ".tmp" to the
  36 # files passed in). And the ".config" that you should test will be in
  37 # directory
  38
  39 # After the first run, determine if the result is good or bad then
  40 # run the same command appending the result
  41
  42 # For good results:
  43 #  $ config-bisect.pl /path/to/good/config /path/to/bad/config good
  44
  45 # For bad results:
  46 #  $ config-bisect.pl /path/to/good/config /path/to/bad/config bad
  47
  48 # Do not change the good-config or bad-config, config-bisect.pl will
  49 # copy the good-config to a temp file with the same name as good-config
  50 # but with a ".tmp" after it. It will do the same with the bad-config.
  51
  52 # If "good" or "bad" is not stated at the end, it will copy the good and
  53 # bad configs to the .tmp versions. If a .tmp version already exists, it will
  54 # warn before writing over them (-r will not warn, and just write over them).
  55 # If the last config is labeled "good", then it will copy it to the good .tmp
  56 # version. If the last config is labeled "bad", it will copy it to the bad
  57 # .tmp version. It will continue this until it can not merge the two any more
  58 # without the result being equal to either the good or bad .tmp configs.
  59
  60 my $start = 0;
  61 my $val = "";
  62
  63 my $pwd = `pwd`;
  64 chomp $pwd;
  65 my $tree = $pwd;
  66 my $build;
  67
  68 my $output_config;
  69 my $reset_bisect;
  70
  71 sub usage {
  72     print << "EOF"
  73
  74 usage: config-bisect.pl [-l linux-tree][-b build-dir] good-config bad-config [good|bad]
  75   -l [optional] define location of linux-tree (default is current directory)
  76   -b [optional] define location to build (O=build-dir) (default is linux-tree)
  77   good-config the config that is considered good
  78   bad-config the config that does not work
  79   "good" add this if the last run produced a good config
  80   "bad" add this if the last run produced a bad config
  81   If "good" or "bad" is not specified, then it is the start of a new bisect
  82
  83   Note, each run will create copy of good and bad configs with ".tmp" appended.
  84
  85 EOF
  86 ;
  87
  88     exit(-1);
  89 }
  90
  91 sub doprint {
  92     print @_;
  93 }
  94
  95 sub dodie {
  96     doprint "CRITICAL FAILURE... ", @_, "\n";
  97
  98     die @_, "\n";
  99 }
 100
 101 sub expand_path {
 102     my ($file) = @_;
 103
 104     if ($file =~ m,^/,) {
 105         return $file;
 106     }
 107     return "$pwd/$file";
 108 }
 109
 110 sub read_prompt {
 111     my ($cancel, $prompt) = @_;
 112
 113     my $ans;
 114
 115     for (;;) {
 116         if ($cancel) {
 117             print "$prompt [y/n/C] ";
 118         } else {
 119             print "$prompt [y/N] ";
 120         }
 121         $ans = <STDIN>;
 122         chomp $ans;
 123         if ($ans =~ /^\s*$/) {
 124             if ($cancel) {
 125                 $ans = "c";
 126             } else {
 127                 $ans = "n";
 128             }
 129         }
 130         last if ($ans =~ /^y$/i || $ans =~ /^n$/i);
 131         if ($cancel) {
 132             last if ($ans =~ /^c$/i);
 133             print "Please answer either 'y', 'n' or 'c'.\n";
 134         } else {
 135             print "Please answer either 'y' or 'n'.\n";
 136         }
 137     }
 138     if ($ans =~ /^c/i) {
 139         exit;
 140     }
 141     if ($ans !~ /^y$/i) {
 142         return 0;
 143     }
 144     return 1;
 145 }
 146
 147 sub read_yn {
 148     my ($prompt) = @_;
 149
 150     return read_prompt 0, $prompt;
 151 }
 152
 153 sub read_ync {
 154     my ($prompt) = @_;
 155
 156     return read_prompt 1, $prompt;
 157 }
 158
 159 sub run_command {
 160     my ($command, $redirect) = @_;
 161     my $start_time;
 162     my $end_time;
 163     my $dord = 0;
 164     my $pid;
 165
 166     $start_time = time;
 167
 168     doprint("$command ... ");
 169
 170     $pid = open(CMD, "$command 2>&1 |") or
 171         dodie "unable to exec $command";
 172
 173     if (defined($redirect)) {
 174         open (RD, ">$redirect") or
 175             dodie "failed to write to redirect $redirect";
 176         $dord = 1;
 177     }
 178
 179     while (<CMD>) {
 180         print RD  if ($dord);
 181     }
 182
 183     waitpid($pid, 0);
 184     my $failed = $?;
 185
 186     close(CMD);
 187     close(RD)  if ($dord);
 188
 189     $end_time = time;
 190     my $delta = $end_time - $start_time;
 191
 192     if ($delta == 1) {
 193         doprint "[1 second] ";
 194     } else {
 195         doprint "[$delta seconds] ";
 196     }
 197
 198     if ($failed) {
 199         doprint "FAILED!\n";
 200     } else {
 201         doprint "SUCCESS\n";
 202     }
 203
 204     return !$failed;
 205 }
 206
 207 ###### CONFIG BISECT ######
 208
 209 # config_ignore holds the configs that were set (or unset) for
 210 # a good config and we will ignore these configs for the rest
 211 # of a config bisect. These configs stay as they were.
 212 my %config_ignore;
 213
 214 # config_set holds what all configs were set as.
 215 my %config_set;
 216
 217 # config_off holds the set of configs that the bad config had disabled.
 218 # We need to record them and set them in the .config when running
 219 # olddefconfig, because olddefconfig keeps the defaults.
 220 my %config_off;
 221
 222 # config_off_tmp holds a set of configs to turn off for now
 223 my @config_off_tmp;
 224
 225 # config_list is the set of configs that are being tested
 226 my %config_list;
 227 my %null_config;
 228
 229 my %dependency;
 230
 231 my $make;
 232
 233 sub make_oldconfig {
 234
 235     if (!run_command "$make olddefconfig") {
 236         # Perhaps olddefconfig doesn't exist in this version of the kernel
 237         # try oldnoconfig
 238         doprint "olddefconfig failed, trying make oldnoconfig\n";
 239         if (!run_command "$make oldnoconfig") {
 240             doprint "oldnoconfig failed, trying yes '' | make oldconfig\n";
 241             # try a yes '' | oldconfig
 242             run_command "yes '' | $make oldconfig" or
 243                 dodie "failed make config oldconfig";
 244         }
 245     }
 246 }
 247
 248 sub assign_configs {
 249     my ($hash, $config) = @_;
 250
 251     doprint "Reading configs from $config\n";
 252
 253     open (IN, $config)
 254         or dodie "Failed to read $config";
 255
 256     while (<IN>) {
 257         chomp;
 258         if (/^((CONFIG\S*)=.*)/) {
 259             ${$hash}{$2} = $1;
 260         } elsif (/^(# (CONFIG\S*) is not set)/) {
 261             ${$hash}{$2} = $1;
 262         }
 263     }
 264
 265     close(IN);
 266 }
 267
 268 sub process_config_ignore {
 269     my ($config) = @_;
 270
 271     assign_configs \%config_ignore, $config;
 272 }
 273
 274 sub get_dependencies {
 275     my ($config) = @_;
 276
 277     my $arr = $dependency{$config};
 278     if (!defined($arr)) {
 279         return ();
 280     }
 281
 282     my @deps = @{$arr};
 283
 284     foreach my $dep (@{$arr}) {
 285         print "ADD DEP $dep\n";
 286         @deps = (@deps, get_dependencies $dep);
 287     }
 288
 289     return @deps;
 290 }
 291
 292 sub save_config {
 293     my ($pc, $file) = @_;
 294
 295     my %configs = %{$pc};
 296
 297     doprint "Saving configs into $file\n";
 298
 299     open(OUT, ">$file") or dodie "Can not write to $file";
 300
 301     foreach my $config (keys %configs) {
 302         print OUT "$configs{$config}\n";
 303     }
 304     close(OUT);
 305 }
 306
 307 sub create_config {
 308     my ($name, $pc) = @_;
 309
 310     doprint "Creating old config from $name configs\n";
 311
 312     save_config $pc, $output_config;
 313
 314     make_oldconfig;
 315 }
 316
 317 # compare two config hashes, and return configs with different vals.
 318 # It returns B's config values, but you can use A to see what A was.
 319 sub diff_config_vals {
 320     my ($pa, $pb) = @_;
 321
 322     # crappy Perl way to pass in hashes.
 323     my %a = %{$pa};
 324     my %b = %{$pb};
 325
 326     my %ret;
 327
 328     foreach my $item (keys %a) {
 329         if (defined($b{$item}) && $b{$item} ne $a{$item}) {
 330             $ret{$item} = $b{$item};
 331         }
 332     }
 333
 334     return %ret;
 335 }
 336
 337 # compare two config hashes and return the configs in B but not A
 338 sub diff_configs {
 339     my ($pa, $pb) = @_;
 340
 341     my %ret;
 342
 343     # crappy Perl way to pass in hashes.
 344     my %a = %{$pa};
 345     my %b = %{$pb};
 346
 347     foreach my $item (keys %b) {
 348         if (!defined($a{$item})) {
 349             $ret{$item} = $b{$item};
 350         }
 351     }
 352
 353     return %ret;
 354 }
 355
 356 # return if two configs are equal or not
 357 # 0 is equal +1 b has something a does not
 358 # +1 if a and b have a different item.
 359 # -1 if a has something b does not
 360 sub compare_configs {
 361     my ($pa, $pb) = @_;
 362
 363     my %ret;
 364
 365     # crappy Perl way to pass in hashes.
 366     my %a = %{$pa};
 367     my %b = %{$pb};
 368
 369     foreach my $item (keys %b) {
 370         if (!defined($a{$item})) {
 371             return 1;
 372         }
 373         if ($a{$item} ne $b{$item}) {
 374             return 1;
 375         }
 376     }
 377
 378     foreach my $item (keys %a) {
 379         if (!defined($b{$item})) {
 380             return -1;
 381         }
 382     }
 383
 384     return 0;
 385 }
 386
 387 sub process_failed {
 388     my ($config) = @_;
 389
 390     doprint "\n\n***************************************\n";
 391     doprint "Found bad config: $config\n";
 392     doprint "***************************************\n\n";
 393 }
 394
 395 sub process_new_config {
 396     my ($tc, $nc, $gc, $bc) = @_;
 397
 398     my %tmp_config = %{$tc};
 399     my %good_configs = %{$gc};
 400     my %bad_configs = %{$bc};
 401
 402     my %new_configs;
 403
 404     my $runtest = 1;
 405     my $ret;
 406
 407     create_config "tmp_configs", \%tmp_config;
 408     assign_configs \%new_configs, $output_config;
 409
 410     $ret = compare_configs \%new_configs, \%bad_configs;
 411     if (!$ret) {
 412         doprint "New config equals bad config, try next test\n";
 413         $runtest = 0;
 414     }
 415
 416     if ($runtest) {
 417         $ret = compare_configs \%new_configs, \%good_configs;
 418         if (!$ret) {
 419             doprint "New config equals good config, try next test\n";
 420             $runtest = 0;
 421         }
 422     }
 423
 424     %{$nc} = %new_configs;
 425
 426     return $runtest;
 427 }
 428
 429 sub convert_config {
 430     my ($config) = @_;
 431
 432     if ($config =~ /^# (.*) is not set/) {
 433         $config = "$1=n";
 434     }
 435
 436     $config =~ s/^CONFIG_//;
 437     return $config;
 438 }
 439
 440 sub print_config {
 441     my ($sym, $config) = @_;
 442
 443     $config = convert_config $config;
 444     doprint "$sym$config\n";
 445 }
 446
 447 sub print_config_compare {
 448     my ($good_config, $bad_config) = @_;
 449
 450     $good_config = convert_config $good_config;
 451     $bad_config = convert_config $bad_config;
 452
 453     my $good_value = $good_config;
 454     my $bad_value = $bad_config;
 455     $good_value =~ s/(.*)=//;
 456     my $config = $1;
 457
 458     $bad_value =~ s/.*=//;
 459
 460     doprint " $config $good_value -> $bad_value\n";
 461 }
 462
 463 # Pass in:
 464 # $phalf: half of the configs names you want to add
 465 # $oconfigs: The orginial configs to start with
 466 # $sconfigs: The source to update $oconfigs with (from $phalf)
 467 # $which: The name of which half that is updating (top / bottom)
 468 # $type: The name of the source type (good / bad)
 469 sub make_half {
 470     my ($phalf, $oconfigs, $sconfigs, $which, $type) = @_;
 471
 472     my @half = @{$phalf};
 473     my %orig_configs = %{$oconfigs};
 474     my %source_configs = %{$sconfigs};
 475
 476     my %tmp_config = %orig_configs;
 477
 478     doprint "Settings bisect with $which half of $type configs:\n";
 479     foreach my $item (@half) {
 480         doprint "Updating $item to $source_configs{$item}\n";
 481         $tmp_config{$item} = $source_configs{$item};
 482     }
 483
 484     return %tmp_config;
 485 }
 486
 487 sub run_config_bisect {
 488     my ($pgood, $pbad) = @_;
 489
 490     my %good_configs = %{$pgood};
 491     my %bad_configs = %{$pbad};
 492
 493     my %diff_configs = diff_config_vals \%good_configs, \%bad_configs;
 494     my %b_configs = diff_configs \%good_configs, \%bad_configs;
 495     my %g_configs = diff_configs \%bad_configs, \%good_configs;
 496
 497     # diff_arr is what is in both good and bad but are different (y->n)
 498     my @diff_arr = keys %diff_configs;
 499     my $len_diff = $#diff_arr + 1;
 500
 501     # b_arr is what is in bad but not in good (has depends)
 502     my @b_arr = keys %b_configs;
 503     my $len_b = $#b_arr + 1;
 504
 505     # g_arr is what is in good but not in bad
 506     my @g_arr = keys %g_configs;
 507     my $len_g = $#g_arr + 1;
 508
 509     my $runtest = 0;
 510     my %new_configs;
 511     my $ret;
 512
 513     # Look at the configs that are different between good and bad.
 514     # This does not include those that depend on other configs
 515     #  (configs depending on other configs that are not set would
 516     #   not show up even as a "# CONFIG_FOO is not set"
 517
 518
 519     doprint "# of configs to check:             $len_diff\n";
 520     doprint "# of configs showing only in good: $len_g\n";
 521     doprint "# of configs showing only in bad:  $len_b\n";
 522
 523     if ($len_diff > 0) {
 524         # Now test for different values
 525
 526         doprint "Configs left to check:\n";
 527         doprint "  Good Config\t\t\tBad Config\n";
 528         doprint "  -----------\t\t\t----------\n";
 529         foreach my $item (@diff_arr) {
 530             doprint "  $good_configs{$item}\t$bad_configs{$item}\n";
 531         }
 532
 533         my $half = int($#diff_arr / 2);
 534         my @tophalf = @diff_arr[0 .. $half];
 535
 536         doprint "Set tmp config to be good config with some bad config values\n";
 537
 538         my %tmp_config = make_half \@tophalf, \%good_configs,
 539             \%bad_configs, "top", "bad";
 540
 541         $runtest = process_new_config \%tmp_config, \%new_configs,
 542                             \%good_configs, \%bad_configs;
 543
 544         if (!$runtest) {
 545             doprint "Set tmp config to be bad config with some good config values\n";
 546
 547             my %tmp_config = make_half \@tophalf, \%bad_configs,
 548                 \%good_configs, "top", "good";
 549
 550             $runtest = process_new_config \%tmp_config, \%new_configs,
 551                 \%good_configs, \%bad_configs;
 552         }
 553     }
 554
 555     if (!$runtest && $len_diff > 0) {
 556         # do the same thing, but this time with bottom half
 557
 558         my $half = int($#diff_arr / 2);
 559         my @bottomhalf = @diff_arr[$half+1 .. $#diff_arr];
 560
 561         doprint "Set tmp config to be good config with some bad config values\n";
 562
 563         my %tmp_config = make_half \@bottomhalf, \%good_configs,
 564             \%bad_configs, "bottom", "bad";
 565
 566         $runtest = process_new_config \%tmp_config, \%new_configs,
 567                             \%good_configs, \%bad_configs;
 568
 569         if (!$runtest) {
 570             doprint "Set tmp config to be bad config with some good config values\n";
 571
 572             my %tmp_config = make_half \@bottomhalf, \%bad_configs,
 573                 \%good_configs, "bottom", "good";
 574
 575             $runtest = process_new_config \%tmp_config, \%new_configs,
 576                 \%good_configs, \%bad_configs;
 577         }
 578     }
 579
 580     if ($runtest) {
 581         make_oldconfig;
 582         doprint "READY TO TEST .config IN $build\n";
 583         return 0;
 584     }
 585
 586     doprint "\n%%%%%%%% FAILED TO FIND SINGLE BAD CONFIG %%%%%%%%\n";
 587     doprint "Hmm, can't make any more changes without making good == bad?\n";
 588     doprint "Difference between good (+) and bad (-)\n";
 589
 590     foreach my $item (keys %bad_configs) {
 591         if (!defined($good_configs{$item})) {
 592             print_config "-", $bad_configs{$item};
 593         }
 594     }
 595
 596     foreach my $item (keys %good_configs) {
 597         next if (!defined($bad_configs{$item}));
 598         if ($good_configs{$item} ne $bad_configs{$item}) {
 599             print_config_compare $good_configs{$item}, $bad_configs{$item};
 600         }
 601     }
 602
 603     foreach my $item (keys %good_configs) {
 604         if (!defined($bad_configs{$item})) {
 605             print_config "+", $good_configs{$item};
 606         }
 607     }
 608     return -1;
 609 }
 610
 611 sub config_bisect {
 612     my ($good_config, $bad_config) = @_;
 613     my $ret;
 614
 615     my %good_configs;
 616     my %bad_configs;
 617     my %tmp_configs;
 618
 619     doprint "Run good configs through make oldconfig\n";
 620     assign_configs \%tmp_configs, $good_config;
 621     create_config "$good_config", \%tmp_configs;
 622     assign_configs \%good_configs, $output_config;
 623
 624     doprint "Run bad configs through make oldconfig\n";
 625     assign_configs \%tmp_configs, $bad_config;
 626     create_config "$bad_config", \%tmp_configs;
 627     assign_configs \%bad_configs, $output_config;
 628
 629     save_config \%good_configs, $good_config;
 630     save_config \%bad_configs, $bad_config;
 631
 632     return run_config_bisect \%good_configs, \%bad_configs;
 633 }
 634
 635 while ($#ARGV >= 0) {
 636     if ($ARGV[0] !~ m/^-/) {
 637         last;
 638     }
 639     my $opt = shift @ARGV;
 640
 641     if ($opt eq "-b") {
 642         $val = shift @ARGV;
 643         if (!defined($val)) {
 644             die "-b requires value\n";
 645         }
 646         $build = $val;
 647     }
 648
 649     elsif ($opt eq "-l") {
 650         $val = shift @ARGV;
 651         if (!defined($val)) {
 652             die "-l requires value\n";
 653         }
 654         $tree = $val;
 655     }
 656
 657     elsif ($opt eq "-r") {
 658         $reset_bisect = 1;
 659     }
 660
 661     elsif ($opt eq "-h") {
 662         usage;
 663     }
 664
 665     else {
 666         die "Unknown option $opt\n";
 667     }
 668 }
 669
 670 $build = $tree if (!defined($build));
 671
 672 $tree = expand_path $tree;
 673 $build = expand_path $build;
 674
 675 if ( ! -d $tree ) {
 676     die "$tree not a directory\n";
 677 }
 678
 679 if ( ! -d $build ) {
 680     die "$build not a directory\n";
 681 }
 682
 683 usage if $#ARGV < 1;
 684
 685 if ($#ARGV == 1) {
 686     $start = 1;
 687 } elsif ($#ARGV == 2) {
 688     $val = $ARGV[2];
 689     if ($val ne "good" && $val ne "bad") {
 690         die "Unknown command '$val', bust be either \"good\" or \"bad\"\n";
 691     }
 692 } else {
 693     usage;
 694 }
 695
 696 my $good_start = expand_path $ARGV[0];
 697 my $bad_start = expand_path $ARGV[1];
 698
 699 my $good = "$good_start.tmp";
 700 my $bad = "$bad_start.tmp";
 701
 702 $make = "make";
 703
 704 if ($build ne $tree) {
 705     $make = "make O=$build"
 706 }
 707
 708 $output_config = "$build/.config";
 709
 710 if ($start) {
 711     if ( ! -f $good_start ) {
 712         die "$good_start not found\n";
 713     }
 714     if ( ! -f $bad_start ) {
 715         die "$bad_start not found\n";
 716     }
 717     if ( -f $good || -f $bad ) {
 718         my $p = "";
 719
 720         if ( -f $good ) {
 721             $p = "$good exists\n";
 722         }
 723
 724         if ( -f $bad ) {
 725             $p = "$p$bad exists\n";
 726         }
 727
 728         if (!defined($reset_bisect)) {
 729             if (!read_yn "${p}Overwrite and start new bisect anyway?") {
 730                 exit (-1);
 731             }
 732         }
 733     }
 734     run_command "cp $good_start $good" or die "failed to copy to $good\n";
 735     run_command "cp $bad_start $bad" or die "failed to copy to $bad\n";
 736 } else {
 737     if ( ! -f $good ) {
 738         die "Can not find file $good\n";
 739     }
 740     if ( ! -f $bad ) {
 741         die "Can not find file $bad\n";
 742     }
 743     if ($val eq "good") {
 744         run_command "cp $output_config $good" or die "failed to copy $config to $good\n";
 745     } elsif ($val eq "bad") {
 746         run_command "cp $output_config $bad" or die "failed to copy $config to $bad\n";
 747     }
 748 }
 749
 750 chdir $tree || die "can't change directory to $tree";
 751
 752 my $ret = config_bisect $good, $bad;
 753
 754 if (!$ret) {
 755     exit(0);
 756 }
 757
 758 if ($ret > 0) {
 759     doprint "Cleaning temp files\n";
 760     run_command "rm $good";
 761     run_command "rm $bad";
 762     exit(1);
 763 } else {
 764     doprint "See good and bad configs for details:\n";
 765     doprint "good: $good\n";
 766     doprint "bad:  $bad\n";
 767     doprint "%%%%%%%% FAILED TO FIND SINGLE BAD CONFIG %%%%%%%%\n";
 768 }
 769 exit(2);