1# Android's binary search tool 2 3`binary_search_state.py` is a general binary search triage tool that 4performs a binary search on a set of things to try to identify which 5thing or thing(s) in the set is 'bad'. `binary_search_state.py` assumes 6that the user has two sets, one where everything is known to be good, 7and one which contains at least one bad item. `binary_search_state.py` 8then copies items from the good and bad sets into a working set and 9tests the result (good or bad). `binary_search_state.py` requires that 10a set of scripts be supplied to it for any particular job. For more 11information on `binary_search_state.py`, see 12 13https://sites.google.com/a/google.com/chromeos-toolchain-team-home2/home/team-tools-and-scripts/binary-searcher-tool-for-triage 14 15This particular set of scripts is designed to work with 16`binary_search_state.py` in order to find the bad object or set of 17bad objects in an Android build. Furthermore, it can also help find 18the bad compiler pass and transformation when building that bad object. 19 20 21## QUICKSTART 22 23After setting up your 2 build trees (see Prerequisites section), do the 24following: 25 26- Decide which test script to use (`boot_test.sh` or 27 `interactive_test.sh`) 28- Get the serial number for the Android device you will use for testing. 29- Run the following: 30 31 ``` 32 $ cd <android_src> 33 $ source build/envsetup.sh 34 $ lunch <android_device_lunch_combo> 35 $ cd <path_to_toolchain_utils>/binary_search_tool/ 36 $ NUM_JOBS=10 ANDROID_SERIAL=<device_serial> \ 37 ./android/setup.sh <android_src> 38 ``` 39 40 If you chose the boot test, then: 41 42 ``` 43 TEST_SCRIPT=android/boot_test.sh 44 ``` 45 46 If you chose the interactive test, then: 47 48 ``` 49 TEST_SCRIPT=android/interactive_test.sh 50 ``` 51 52 Finally, run the binary search tool: 53 54 ``` 55 $ python ./binary_search_state.py \ 56 --get_initial_items=android/get_initial_items.sh \ 57 --switch_to_good=android/switch_to_good.sh \ 58 --switch_to_bad=android/switch_to_bad.sh \ 59 --test_setup_script=android/test_setup.sh \ 60 --test_script=$TEST_SCRIPT \ 61 --file_args \ 62 --prune 63 ``` 64 65 Once you have completely finished doing the binary search/triage, 66 run the cleanup script: 67 68 ``` 69 $ android/cleanup.sh 70 ``` 71 72 73## FILES AND SCRIPTS 74 75Check the header comments for each script for more in depth documentation. 76 77`boot_test.sh` - One of two possible test scripts used to determine 78 if the Android image built from the objects is good 79 or bad. This script tests to see if the image 80 booted, and requires no user intervention. 81 82`cleanup.sh` - This is called after the binary search tool completes. This 83 script will clean up the common.sh file generated by setup.sh 84 85`get_initial_items.sh` - This script is used to determine all Android objects 86 that will be bisected. 87 88`test_setup.sh` - This script will build and flash your image to the 89 Android device. If the flash fails, this script will 90 help the user troubleshoot by trying to flash again or 91 by asking the user to manually flash it. 92 93`interactive_test.sh` - One of two possible scripts used to determine 94 if the Android image built from the objects 95 is good or bad. This script requires user 96 interaction to determine if the image is 97 good or bad. 98 99`setup.sh` - This is the first script the user should call, after 100 taking care of the prerequisites. It sets up the 101 environment appropriately for running the Android 102 object binary search triage, and it generates the 103 necessary common script (see below). 104 105`switch_to_bad.sh` - This script is used to link objects from the 106 'bad' build tree into the work area. 107 108`switch_to_good.sh` - This script is used to link objects from the 109 'good' build tree into the work area. 110 111`generate_cmd.sh` - This script will generate another temporary script, which 112 contains the command line options to build the bad object 113 file again with pass/transformation level limit. 114 115 116## GENERATED SCRIPTS 117 118`common.sh` - contains basic environment variable definitions for 119 this binary search triage session. 120 121## ASSUMPTIONS 122 123- There are two different Android builds, for the same board/lunch combo with 124 the same set of generated object files. One build creates a good working 125 Android image and the other does not. 126 127- The toolchain bug you are tracking down is not related to the linker. If the 128 linker is broken or generates bad code, this tool is unlikely to help you. 129 130 131PREREQUISITES FOR USING THESE SCRIPTS: 132 1331. Decide where to store each build tree 134 By default, each build tree is stored in `~/ANDROID_BISECT`. However you 135 can override this by exporting `BISECT_DIR` set to whatever directory you 136 please. Keep in mind these build trees take dozens of gigabytes each. 137 1382. Setup your android build environment 139 140 ``` 141 cd <android_src> 142 source build/envsetup.sh 143 lunch <android_device_lunch_combo> 144 ``` 145 1463. Populate the good build tree 147 148 1. `make clean` 149 2. `export BISECT_STAGE=POPULATE_GOOD` 150 3. Install your "good" toolchain in Android, this will most likely be 151 the toolchain that comes preinstalled with the Android source. 152 4. Build all of Android: `make -j10`. The "-j" parameter depends on how 153 many cores your machine has. See Android documentation for more details. 154 1554. Populate the bad build tree 156 157 1. `make clean` 158 2. `export BISECT_STAGE=POPULATE_BAD` 159 3. Install your "bad" toolchain in Android. 160 4. Build all of Android again. 161 1625. Run the android setup script 163 164 1. `cd <path_to_toolchain_utils>/binary_search_tool/` 165 2. `NUM_JOBS=<jobs> ANDROID_SERIAL=<android_serial_num> 166 android/setup.sh <android_src>` 167 168WARNING: It's important that you leave the full `out/` directory in your 169 Android source alone after Step 4. The binary search tool will 170 use this directory as a skeleton to build each test image while 171 triaging. 172 173## USING THESE SCRIPTS FOR BINARY TRIAGE OF OBJECTS 174 175To use these scripts, you must first run setup.sh, passing it the path to your 176Android source directory. setup.sh will do the following: 177 178- Verify that your build trees are set up correctly (with good, bad). 179- Verify that each build tree has the same contents. 180- Verify that the android build environment (lunch, etc.) are setup in your 181 current shell. 182- Create the common.sh file that the other scripts passed to the 183 binary triage tool will need. 184 185 186This set of scripts comes with two alternate test scripts. One test 187script, `boot_test.sh`, just checks to make sure that the image 188booted (wait for device to boot to home screen) and assumes that is enough. 189The other test script, `interactive_test.sh`, is interactive and asks YOU 190to tell it whether the image on the android device is ok or not (it 191prompts you and waits for a response). 192 193 194Once you have run `setup.sh` (and decided which test script you 195want to use) run the binary triage tool using these scripts to 196isolate/identify the bad object: 197 198``` 199./binary_search_state.py \ 200 --get_initial_items=android/get_initial_items.sh \ 201 --switch_to_good=android/switch_to_good.sh \ 202 --switch_to_bad=android/switch_to_bad.sh \ 203 --test_setup_script=android/test_setup.sh \ 204 --test_script=android/boot_test.sh \ # could use interactive_test.sh instead 205 --prune 206``` 207 208After you have finished running the tool and have identified the bad 209object(s), you will want to run the cleanup script (android/cleanup.sh). 210