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);
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.