# Android's binary search tool

`binary_search_state.py` is a general binary search triage tool that
performs a binary search on a set of things to try to identify which
thing or thing(s) in the set is 'bad'.  `binary_search_state.py` assumes
that the user has two sets, one where everything is known to be good,
and one which contains at least one bad item.  `binary_search_state.py`
then copies items from the good and bad sets into a working set and
tests the result (good or bad).  `binary_search_state.py` requires that
a set of scripts be supplied to it for any particular job.  For more
information on `binary_search_state.py`, see

https://sites.google.com/a/google.com/chromeos-toolchain-team-home2/home/team-tools-and-scripts/binary-searcher-tool-for-triage

This particular set of scripts is designed to work with
`binary_search_state.py` in order to find the bad object or set of
bad objects in an Android build. Furthermore, it can also help find
the bad compiler pass and transformation when building that bad object.


## QUICKSTART

After setting up your 2 build trees (see Prerequisites section), do the
following:

-   Decide which test script to use (`boot_test.sh` or
    `interactive_test.sh`)
-   Get the serial number for the Android device you will use for testing.
-   Run the following:

    ```
    $ cd <android_src>
    $ source build/envsetup.sh
    $ lunch <android_device_lunch_combo>
    $ cd <path_to_toolchain_utils>/binary_search_tool/
    $ NUM_JOBS=10 ANDROID_SERIAL=<device_serial> \
          ./android/setup.sh <android_src>
    ```

    If you chose the boot test, then:

    ```
    TEST_SCRIPT=android/boot_test.sh
    ```

    If you chose the interactive test, then:

    ```
    TEST_SCRIPT=android/interactive_test.sh
    ```

    Finally, run the binary search tool:

    ```
    $ python ./binary_search_state.py \
        --get_initial_items=android/get_initial_items.sh \
        --switch_to_good=android/switch_to_good.sh \
        --switch_to_bad=android/switch_to_bad.sh \
        --test_setup_script=android/test_setup.sh \
        --test_script=$TEST_SCRIPT \
        --file_args \
        --prune
    ```

    Once you have completely finished doing the binary search/triage,
    run the cleanup script:

    ```
    $ android/cleanup.sh
    ```


## FILES AND SCRIPTS

Check the header comments for each script for more in depth documentation.

`boot_test.sh` - One of two possible test scripts used to determine
                 if the Android image built from the objects is good
                 or bad. This script tests to see if the image
                 booted, and requires no user intervention.

`cleanup.sh` - This is called after the binary search tool completes. This
               script will clean up the common.sh file generated by setup.sh

`get_initial_items.sh` - This script is used to determine all Android objects
                         that will be bisected.

`test_setup.sh` - This script will build and flash your image to the
                  Android device. If the flash fails, this script will
                  help the user troubleshoot by trying to flash again or
                  by asking the user to manually flash it.

`interactive_test.sh` - One of two possible scripts used to determine
                        if the Android image built from the objects
                        is good or bad.  This script requires user
                        interaction to determine if the image is
                        good or bad.

`setup.sh` - This is the first script the user should call, after
             taking care of the prerequisites.  It sets up the
             environment appropriately for running the Android
             object binary search triage, and it generates the
             necessary common script (see below).

`switch_to_bad.sh` - This script is used to link objects from the
                     'bad' build tree into the work area.

`switch_to_good.sh` - This script is used to link objects from the
                      'good' build tree into the work area.

`generate_cmd.sh` - This script will generate another temporary script, which
                    contains the command line options to build the bad object
                    file again with pass/transformation level limit.


## GENERATED SCRIPTS

`common.sh` - contains basic environment variable definitions for
              this binary search triage session.

## ASSUMPTIONS

-   There are two different Android builds, for the same board/lunch combo with
    the same set of generated object files.  One build creates a good working
    Android image and the other does not.

-   The toolchain bug you are tracking down is not related to the linker. If the
    linker is broken or generates bad code, this tool is unlikely to help you.


PREREQUISITES FOR USING THESE SCRIPTS:

1.  Decide where to store each build tree
    By default, each build tree is stored in `~/ANDROID_BISECT`. However you
    can override this by exporting `BISECT_DIR` set to whatever directory you
    please. Keep in mind these build trees take dozens of gigabytes each.

2.  Setup your android build environment

    ```
    cd <android_src>
    source build/envsetup.sh
    lunch <android_device_lunch_combo>
    ```

3.  Populate the good build tree

    1.  `make clean`
    2.  `export BISECT_STAGE=POPULATE_GOOD`
    3.  Install your "good" toolchain in Android, this will most likely be
        the toolchain that comes preinstalled with the Android source.
    4.  Build all of Android: `make -j10`. The "-j" parameter depends on how
        many cores your machine has. See Android documentation for more details.

4.  Populate the bad build tree

    1.  `make clean`
    2.  `export BISECT_STAGE=POPULATE_BAD`
    3.  Install your "bad" toolchain in Android.
    4.  Build all of Android again.

5.  Run the android setup script

    1.  `cd <path_to_toolchain_utils>/binary_search_tool/`
    2.  `NUM_JOBS=<jobs> ANDROID_SERIAL=<android_serial_num>
        android/setup.sh <android_src>`

WARNING: It's important that you leave the full `out/` directory in your
         Android source alone after Step 4. The binary search tool will
         use this directory as a skeleton to build each test image while
         triaging.

## USING THESE SCRIPTS FOR BINARY TRIAGE OF OBJECTS

To use these scripts, you must first run setup.sh, passing it the path to your
Android source directory. setup.sh will do the following:

-   Verify that your build trees are set up correctly (with good, bad).
-   Verify that each build tree has the same contents.
-   Verify that the android build environment (lunch, etc.) are setup in your
    current shell.
-   Create the common.sh file that the other scripts passed to the
    binary triage tool will need.


This set of scripts comes with two alternate test scripts.  One test
script, `boot_test.sh`, just checks to make sure that the image
booted (wait for device to boot to home screen) and assumes that is enough.
The other test script, `interactive_test.sh`, is interactive and asks YOU
to tell it whether the image on the android device is ok or not (it
prompts you and waits for a response).


Once you have run `setup.sh` (and decided which test script you
want to use) run the binary triage tool using these scripts to
isolate/identify the bad object:

```
./binary_search_state.py \
   --get_initial_items=android/get_initial_items.sh \
   --switch_to_good=android/switch_to_good.sh \
   --switch_to_bad=android/switch_to_bad.sh \
   --test_setup_script=android/test_setup.sh \
   --test_script=android/boot_test.sh \  # could use interactive_test.sh instead
   --prune
```

After you have finished running the tool and have identified the bad
object(s), you will want to run the cleanup script (android/cleanup.sh).