| # 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). |