diff options
Diffstat (limited to 'binary_search_tool/MAINTENANCE')
| -rw-r--r-- | binary_search_tool/MAINTENANCE | 115 |
1 files changed, 115 insertions, 0 deletions
diff --git a/binary_search_tool/MAINTENANCE b/binary_search_tool/MAINTENANCE new file mode 100644 index 00000000..8e5b3c61 --- /dev/null +++ b/binary_search_tool/MAINTENANCE @@ -0,0 +1,115 @@ +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, 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 bisect.py both have to have near identical + arguments in order to support argument overriding in bisect.py. However + they do have to be slightly different. Mainly, 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). |