1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
# Copyright 2020 The Chromium OS Authors. All rights reserved.
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.
This document is for future maintainers of the binary search/bisection tools.
Authors:
* Original Tool: asharif@, llozano@, cmtice@
* Updates after May 2016: cburden@
* chromeos-toolchain@
The following are good reference materials on how the tool works:
* Ahmad's original presentation:
https://goto.google.com/zxdfyi
* Bisection tool update design doc:
https://goto.google.com/zcwei
* Bisection tool webpage:
https://goto.google.com/ruwpyi
* Compiler wrapper webpage:
https://goto.google.com/xossn
TESTING:
All unit tests live under the ./test directory. However, these tests
specifically test binary_search_state.py, binary_search_perforce.py,
run_bisect.py.
These unit tests will not test the specific logic for ChromeOS/Android
bisection. To test the ChromeOS/Android bisectors, use the common/hash_test.sh
test. This is a simple test case that just checks the hashes of files on your
file system. This means you won't have to find a specific compiler error for
the bisector to triage in order to test each bisector.
TODO:
The bisection tool (I believe) is in a fairly good state. So these are mostly
wishlist items and things that could use some improvement.
1. Get rid of binary_search_perforce.py. This file is mostly legacy code and
the majority of it isn't even used to bisect object files. The file was
originally intended to bisect CLs, and binary_search_state.py just reused
the binary searching logic from it. Maybe just extract the binary searching
logic from binary_search_perforce.py and put it in its own module in
cros_utils?
2. Cleanup unit tests in ./test. These tests are a little hacked together,
and are all under one test suite. Maybe consider organizing them across
multiple directories.
3. Create a "checkout setup" system for bisection. Currently if you want to
bisect, you have to run scripts/edit sources in this repo. Ideally these
scripts would be static, and if you wanted to bisect/make changes you would
"checkout" or copy all the scripts to a working directory and have a unique
working directory for each bisection. Credits to Luis for this idea =)
4. Make all scripts relative to each other. Currently all scripts enforce the
idea that their cwd will be ./binary_search_tool/. But it would be less
confusing to have each script relative to each other. There's quite a few
stackoverflow topics on how to do this best, but each one has some sort of
downside or flaw.
5. Overall modularize code more, especially in binary_search_state.py
DESIGN EXPLANATIONS:
Some of the design decisions are a bit difficult to understand from just reading
the code unfortunately. I will attempt to clear up the major offenders of this:
1. common.py's argument dictionary:
binary_search_state.py and run_bisect.py both have to have near identical
arguments in order to support argument overriding in run_bisect.py. However
they do have to be slightly different. Mainly, run_bisect.py needs to have
no default values for arguments (so it can determine what's being
overriden).
In order to reduce huge amounts of code duplication for the argument
building, we put argument building in common.py. That way both modules
can reference the arguments, and they can have different configurations
across both.
2. Compiler wrapper:
The compiler wrapper is called before all compiler calls. It exists to
trick whatever build system (make, emerge, etc.) into thinking our
bisection is just a normal build, when really we're doing some tricks.
The biggest benefit the compiler wrapper gives is: knowing for sure which
files are actually generated by the compiler during bisection setup, and
potentially being able to skip compilations while triaging (speeding up the
triaging process significantly).
3. The weird options for the --verify, --verbose, --file_args, etc. arguments:
Some of the arguments for the bisection tool have a weird set of options
for the AddArgument method (nargs, const, default, StrToBool). This is so
we can make argument overriding workable. These options allow the following
functionality for a boolean argument (using --prune as an example):
* --prune (prune set to True)
* <not given> (prune set to False)
* --prune=True (prune set to True)
* --prune=False (prune set to False)
The first two are easy to implement (action='store_true'), but the last two
are why the extra weird arguments are required. Now, why would we want the
last two? Imagine if the Android bisector set --prune=True as a default
argument. With just the first two options above it would be impossible for
the user to override prune and set it to False. So the user needs the
--prune=False option. See the argparse documentation for more details.
4. General binary searching logic/pruning logic:
binary_search_state.py will enumerate all items into a list. The binary
search will find the *first* bad item (starting with lowest index).
Everything to the left of the "current" index is switched to good,
everything to right of the "current" index is switched to bad. Once a bad
item is found, it's put at the very end of the list.
If prune is set, the tool will continuing searching until all bad items are
found (instead of stopping after the first one). If the tool finds the same
item twice, that means no more bad items exist. This is because the item
was found, said item was put at the end of the list, and it was found
again. Because the binary search logic finds the bad item with the lowest
index, this means nothing in between the start of the list and the end of
the list is bad (thus no more bad items remain).
|
