binary search tool: Add sample NDK bisection

Add sample NDK bisection that can be given to those inside or outside of
Google. This sample includes a compressed source tree of the Teapot
sample NDK app, and a script showing the full setup and process for
running the bisection tool. It also includes a couple patches that show
the necessary changes to the build system, and the "compiler error" that
we will be bisecting.

TEST=Run DO_BISECTION.sh

Change-Id: I11279fe33e833b0dfe2fb147fde6f46b347d62be
Reviewed-on: https://chrome-internal-review.googlesource.com/274145
Commit-Ready: Cassidy Burden <cburden@google.com>
Tested-by: Cassidy Burden <cburden@google.com>
Reviewed-by: Luis Lozano <llozano@chromium.org>

10 files changed, 363 insertions, 0 deletions

diff --git a/binary_search_tool/ndk/DO_BISECTION.sh b/binary_search_tool/ndk/DO_BISECTION.sh
new file mode 100755
index 00000000..298d5747
--- /dev/null
+++ b/binary_search_tool/ndk/DO_BISECTION.sh
@@ -0,0 +1,92 @@
+#!/bin/bash
+#
+# Copyright 2016 Google Inc. All Rights Reserved.
+#
+# This is an example script to show users the steps for bisecting an NDK
+# application for Android. Our example is the Teapot app that comes bundled with
+# the NDK as a sample app.
+#
+# Our Teapot app only has 12 or so object files generated per build. Bisection
+# for just 12 object files is overkill, but this bisection process easily scales
+# to thousands of object files (as seen with the Android source).
+#
+# Setup:
+#   1. Install NDK (make sure it is in your PATH)
+#   2. Install compiler_wrapper.py
+#   3. Connect an arm7 device (tested with Nexus 5X)
+#     a. See README for supporting other device archs
+#
+# Tested in bash on Linux.
+
+# Set CWD to where this script lives
+pushd "$(dirname "$0")"
+
+# If Teapot dir already exists remove it.
+if [[ -d Teapot ]]; then
+  rm -rf Teapot
+fi
+
+# Unzip our repository we'll be testing with.
+tar -xzf Teapot.tar.gz
+
+# Apply small setup patch. This patch makes a small change to the build system
+# to make this bisecting example a little easier. It inserts the option to only
+# build for an arm7. See the patch file for details.
+# (This patch file was generated with git, -p1 will remove the a/ and b/)
+patch -p1 -i PATCH1
+
+# We want all of our cached files to be stored in ~/NDK_EXAMPLE_BISECT
+# Remove directory if already exists
+export BISECT_DIR=~/NDK_EXAMPLE_BISECT
+if [[ -d ${BISECT_DIR} ]]; then
+  rm -rf ${BISECT_DIR}
+fi
+
+# We will now take our normal "good compiler" and do a full build of the app. We
+# need to clean before building. This ensures that all objects are generated and
+# can be cached.
+pushd Teapot
+export BISECT_STAGE=POPULATE_GOOD
+./gradlew clean
+./gradlew installArm7Debug
+popd
+
+# Inserting "compiler error". Really this is just a patch that inserts a simple
+# error in the code, but this is used to simulate our compiler error. This patch
+# will simply cause the app to crash as soon as it starts. See the patch file
+# for details.
+# (This patch file was generated with git, -p1 will remove the a/ and b/)
+patch -p1 -i PATCH2
+
+# Now that we have installed our bad compiler (i.e. applied the above patch that
+# acts like a compiler error), we want to enumerate and cache all objects
+# generated by this "bad compiler". So again, we clean the build tree so that
+# all objects are regenerated and can be cached.
+pushd Teapot
+export BISECT_STAGE=POPULATE_BAD
+./gradlew clean
+./gradlew installArm7Debug
+popd
+
+# Now ~/NDK_EXAMPLE_BISECT holds the caches for both good and bad compiler
+# outputs. We will now use these to bisect our problem. We should find that
+# TeapotRenderer.o is the bad file (because this is where PATCH2 inserted the
+# "compiler error").
+
+# Tell the compiler wrapper to not cache outputs, and instead begin bisecting.
+export BISECT_STAGE=TRIAGE
+
+# Run the actual bisection tool. This will automatically narrow down which
+# object file has the error. The test_setup.sh script will rebuild our app
+# with gradle, and boot_test.sh will ping the device to see if the app crashed
+# or not.
+cd ..
+./binary_search_state.py \
+  --get_initial_items=ndk/get_initial_items.sh \
+  --switch_to_good=ndk/switch_to_good.sh \
+  --switch_to_bad=ndk/switch_to_bad.sh \
+  --test_setup_script=ndk/test_setup.sh \
+  --test_script=ndk/boot_test.sh \
+  --file_args
+
+popd
diff --git a/binary_search_tool/ndk/PATCH1 b/binary_search_tool/ndk/PATCH1
new file mode 100644
index 00000000..eddf61cf
--- /dev/null
+++ b/binary_search_tool/ndk/PATCH1
@@ -0,0 +1,40 @@
+From 93395bf49f856abac5ab06d4bcaa7cdbf76a77fc Mon Sep 17 00:00:00 2001
+From: Cassidy Burden <cburden@google.com>
+Date: Tue, 9 Aug 2016 09:38:41 -0700
+Subject: [PATCH] FOR BINARY SEARCH TOOL: Add arm7 target
+
+Add arm7 target to build.gradle file. This is so the bisection tool only
+has to triage the object files generated for our specific device.
+Without this target we would have to binary search across object files
+meant for x86 targets (that we can't even test on our ARM device).
+---
+ Teapot/app/build.gradle | 7 ++++++-
+ 1 file changed, 6 insertions(+), 1 deletion(-)
+
+diff --git a/Teapot/app/build.gradle b/Teapot/app/build.gradle
+index 78cf54d..c322114 100644
+--- a/Teapot/app/build.gradle
++++ b/Teapot/app/build.gradle
+@@ -29,7 +29,7 @@ model {
+             cppFlags.addAll(['-I' + "${ndkDir}/sources/android/cpufeatures",
+                              '-I' + file('src/main/jni/ndk_helper')])
+             cppFlags.addAll(['-std=c++11', '-Wall',
+-                             '-fno-exceptions', '-fno-rtti'])
++                             '-fno-exceptions', '-fno-rtti', '-gsplit-dwarf'])
+             ldLibs.addAll(['android', 'log', 'EGL', 'GLESv2','atomic'])
+         }
+         sources {
+@@ -51,5 +51,10 @@ model {
+                 proguardFiles.add(file('proguard-rules.txt'))
+             }
+         }
++	productFlavors{
++            create("arm7") {
++                ndk.abiFilters.add("armeabi-v7a")
++            }
++	}
+     }
+ }
+-- 
+2.8.0.rc3.226.g39d4020
+
diff --git a/binary_search_tool/ndk/PATCH2 b/binary_search_tool/ndk/PATCH2
new file mode 100644
index 00000000..9fcf45d0
--- /dev/null
+++ b/binary_search_tool/ndk/PATCH2
@@ -0,0 +1,34 @@
+From 960134fb87a194595f2a0a36290be7961e12b946 Mon Sep 17 00:00:00 2001
+From: Cassidy Burden <cburden@google.com>
+Date: Tue, 9 Aug 2016 09:46:27 -0700
+Subject: [PATCH] FOR BISECTION TOOL: Insert error
+
+Insert error into code that will cause crash. This is the "compiler
+error" that we will be triaging. We will be pretending the compiler
+mistakenly inserted a nullptr where it shouldn't have.
+
+This error causes the app to immediately crash upon starting. This makes
+it very easy to automatically test the app through adb. Not all compiler
+problems will be this easy to test, and may require manual testing from
+you (the user). See android/interactive_test.sh for an example on
+manual testing from the user.
+---
+ Teapot/app/src/main/jni/TeapotRenderer.cpp | 2 +-
+ 1 file changed, 1 insertion(+), 1 deletion(-)
+
+diff --git a/Teapot/app/src/main/jni/TeapotRenderer.cpp b/Teapot/app/src/main/jni/TeapotRenderer.cpp
+index 7cafdb3..75cadbf 100644
+--- a/Teapot/app/src/main/jni/TeapotRenderer.cpp
++++ b/Teapot/app/src/main/jni/TeapotRenderer.cpp
+@@ -58,7 +58,7 @@ void TeapotRenderer::Init() {
+   num_vertices_ = sizeof(teapotPositions) / sizeof(teapotPositions[0]) / 3;
+   int32_t stride = sizeof(TEAPOT_VERTEX);
+   int32_t index = 0;
+-  TEAPOT_VERTEX* p = new TEAPOT_VERTEX[num_vertices_];
++  TEAPOT_VERTEX* p = nullptr; //new TEAPOT_VERTEX[num_vertices_];
+   for (int32_t i = 0; i < num_vertices_; ++i) {
+     p[i].pos[0] = teapotPositions[index];
+     p[i].pos[1] = teapotPositions[index + 1];
+-- 
+2.8.0.rc3.226.g39d4020
+
diff --git a/binary_search_tool/ndk/README b/binary_search_tool/ndk/README
new file mode 100644
index 00000000..324d1391
--- /dev/null
+++ b/binary_search_tool/ndk/README
@@ -0,0 +1,84 @@
+
+This is an example bisection for an NDK build system. This example specifically
+bisects the sample NDK Teapot app. All steps (setup and otherwise) for bisection
+can be found in DO_BISECTION.sh. This shell script is meant to show the process
+required to bisect a compiler problem in an arbitrary NDK app build system.
+
+There are three necessary setup steps to run this example:
+
+  1. Install the NDK (known to work with r12b)
+    a. See here for NDK: https://developer.android.com/ndk/index.html
+    b. Go here for older NDK downloads: https://github.com/android-ndk/ndk/wiki
+
+  2. Install the compiler wrapper provided with this repo. See
+     compiler_wrapper.py for more details.
+    a. Essentially you must go into the NDK source (or where you build system
+       stores its toolchain), rename your compilers to <compiler>.real, and
+       create a symlink pointing to compiler_wrapper.py named <compiler>
+       (where your compiler used to be).
+    b. If you're using the toolchains that come with the NDK they live at:
+         <ndk_path>/toolchains/<arch>/prebuilt/<host>/bin
+       example:
+         <ndk_path>/toolchains/llvm/prebuilt/linux-x86_64/bin/clang
+
+  3. Plug in an Arm7 compatible Android device with usb debugging enabled.
+    a. This bisection example was tested with a Nexus 5X
+    b. It should be relatively simple to change the example to work with other
+       types of devices. Just change the scripts, and change PATCH1 to use a
+       different build flavor (like x86). See below for more details.
+
+This example contains two patches:
+
+  PATCH1 - This is the necessary changes to the build system to make the
+  bisection easier. More specifically, it adds an arm7 build flavor to gradle.
+  By default, this project will build objects for all possible architectures and
+  package them into one big apk. These object files meant for another
+  architecture just sit there and don't actually execute. By adding a build
+  flavor for arm7, our compiler wrapper won't try to bisect object files meant
+  for another device.
+
+  PATCH2 - This patch is what inserts the "compiler error". This is a simple
+  nullptr error in one of the source files, but it is meant to mimic bad code
+  generation. The result of the error is the app simply crashes immediately
+  after starting.
+
+Using another device architecture:
+
+  If we want to bisect for an x86-64 device we first need to provide a arch
+  specific build flavor in our app/build.gradle file:
+
+      create("x86-64") {
+        ndk.abiFilters.add("x86_64")
+      }
+
+  We want to add this under the same "productFlavors" section that our arm7
+  build flavor is in (see PATCH1). Now we should have the "installx86-64Debug"
+  task in our build system. We can use this to build and install an x86-64
+  version of our app.
+
+  Now we want to change our test_setup.sh script to run our new gradle task:
+    ./gradlew installx86-64Debug
+
+  Keep in mind, these specific build flavors are not required. If your build
+  system makes these device specific builds difficult to implement, the
+  bisection tool will function perfectly fine without them. However, the
+  downside of not having targetting a single architecture is the bisection will
+  take longer (as it will need to search across more object files).
+
+Additional Documentation:
+  These are internal Google documents, if you are a developer external to
+  Google please ask whoever gave you this sample for access or copies to the
+  documentation. If you cannot gain access, the various READMEs paired with the
+  bisector should help you.
+
+  * 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
diff --git a/binary_search_tool/ndk/Teapot.tar.gz b/binary_search_tool/ndk/Teapot.tar.gz
new file mode 100644
index 00000000..87faf54b
--- /dev/null
+++ b/binary_search_tool/ndk/Teapot.tar.gz
diff --git a/binary_search_tool/ndk/boot_test.sh b/binary_search_tool/ndk/boot_test.sh
new file mode 100755
index 00000000..b8c34aa5
--- /dev/null
+++ b/binary_search_tool/ndk/boot_test.sh
@@ -0,0 +1,27 @@
+#!/bin/bash -u
+#
+# Copyright 2016 Google Inc. All Rights Reserved.
+#
+# This script checks the android device to determine if the app is currently
+# running. For our specific test case we will be checking if the Teapot app
+# has crashed.
+#
+# This script is intended to be used by binary_search_state.py, as
+# part of the binary search triage on the Android NDK apps. It
+# waits for the test setup script to build and install the app, then checks if
+# app boots or not. It should return '0' if the test succeeds
+# (the image is 'good'); '1' if the test fails (the image is 'bad'); and '125'
+# if it could not determine (does not apply in this case).
+#
+
+echo "Starting Teapot app..."
+adb shell am start -n com.sample.teapot/com.sample.teapot.TeapotNativeActivity
+sleep 3
+
+echo "Checking if Teapot app crashed..."
+adb shell ps | grep com.sample.teapot
+
+retval=$?
+
+
+exit ${retval}
diff --git a/binary_search_tool/ndk/get_initial_items.sh b/binary_search_tool/ndk/get_initial_items.sh
new file mode 100755
index 00000000..bc2d05cd
--- /dev/null
+++ b/binary_search_tool/ndk/get_initial_items.sh
@@ -0,0 +1,12 @@
+#!/bin/bash -u
+#
+# Copyright 2016 Google Inc. All Rights Reserved.
+#
+# This script is intended to be used by binary_search_state.py, as
+# part of the binary search triage on the Android NDK apps.  This script
+# generates the list of object files to be bisected. This list is generated
+# by the compiler wrapper during the POPULATE_GOOD and POPULATE_BAD stages.
+#
+
+cat ${BISECT_DIR}/good/_LIST
+
diff --git a/binary_search_tool/ndk/switch_to_bad.sh b/binary_search_tool/ndk/switch_to_bad.sh
new file mode 120000
index 00000000..0172bce5
--- /dev/null
+++ b/binary_search_tool/ndk/switch_to_bad.sh
@@ -0,0 +1 @@
+switch_to_good.sh
\ No newline at end of file
diff --git a/binary_search_tool/ndk/switch_to_good.sh b/binary_search_tool/ndk/switch_to_good.sh
new file mode 100755
index 00000000..cb8d5fd9
--- /dev/null
+++ b/binary_search_tool/ndk/switch_to_good.sh
@@ -0,0 +1,46 @@
+#!/bin/bash -u
+#
+# Copyright 2016 Google Inc. All Rights Reserved.
+#
+# This script is intended to be used by binary_search_state.py, as
+# part of the binary search triage on Android NDK apps. This script simply
+# deletes all given objects, signaling gradle to execute a recompilation of said
+# object files.
+#
+
+# Input is a file, with newline seperated list of files we will be switching
+OBJ_LIST_FILE=$1
+
+# Check that number of arguments == 1
+if [ $# -ne 1 ] ; then
+  echo "ERROR:"
+  echo "Got multiple inputs to switch script!"
+  echo "Run binary_search_state.py with --file_args"
+  exit 1
+fi
+
+# Remove any file that's being switched. This is because Gradle only recompiles
+# if:
+#   1. The resultant object file doesn't exist
+#   2. The hash of the source file has changed
+#
+# Because we have no reliable way to edit the source file, we instead remove the
+# object file and have the compiler wrapper insert the file from the appropriate
+# cache (good or bad).
+#
+# Not entirely relevant to the Teapot example, but something to consider:
+# This removing strategy has the side effect that all switched items cause the
+# invocation of the compiler wrapper, which can add up and slow the build
+# process. With Android's source tree, Make checks the timestamp of the object
+# file. So we symlink in the appropriate file and touch it to tell Make it needs
+# to be relinked. This avoids having to call the compiler wrapper in the
+# majority of cases.
+#
+# However, a similar construct doesn't seem to exist in Gradle. It may be better
+# to add a build target to Gradle that will always relink all given object
+# files. This way we can avoid calling the compiler wrapper while Triaging and
+# save some time. Not really necessary
+
+cat $OBJ_LIST_FILE | xargs rm
+exit 0
+
diff --git a/binary_search_tool/ndk/test_setup.sh b/binary_search_tool/ndk/test_setup.sh
new file mode 100755
index 00000000..477bcb21
--- /dev/null
+++ b/binary_search_tool/ndk/test_setup.sh
@@ -0,0 +1,27 @@
+#!/bin/bash
+#
+# Copyright 2016 Google Inc. All Rights Reserved.
+#
+# This is the setup script for generating and installing the ndk app.
+#
+# This script is intended to be used by binary_search_state.py, as
+# part of the binary search triage on the Android source tree. It should
+# return '0' if the setup succeeds; and '1' if the setup fails (the image
+# could not build or be flashed).
+#
+
+echo
+echo "INSTALLATION BEGIN"
+echo
+
+# This normally shouldn't be hardcoded, but this is a sample bisection.
+# Also keep in mind that the bisection tool mandates all paths are
+# relative to binary_search_state.py
+cd ndk/Teapot
+
+echo "BUILDING APP"
+
+./gradlew installArm7Debug
+gradle_status=$?
+
+exit ${gradle_status}