path: root/round-robin-bisect.sh

#!/bin/bash

set -ef -o pipefail

scripts=$(dirname $0)
# shellcheck source=jenkins-helpers.sh
. $scripts/jenkins-helpers.sh

declare -A rr

# Process bisect-only args
convert_args_to_variables "$@"
shift "$SHIFT_CONVERTED_ARGS"

obligatory_variables bad_git build_script current_project
declare bad_git build_script current_project

# Relative artifacts are used for generation of manifests and reproduction
# instructions.
rel_artifacts="${rel_artifacts-artifacts}"
artifacts=$(pwd)/$rel_artifacts

fresh_dir $artifacts \
	  "$artifacts/manifest.sh" \
	  "$artifacts/build-parameters/manifest.sh" \
	  "$artifacts/jenkins/*"

BUILD_URL="${BUILD_URL:-$(pwd)}"
replay_log="${replay_log-}"
reproduce_bisect="${reproduce_bisect:-false}"

# Process build args and record them in build-parameters.sh
convert_args_to_variables ^^ $reproduce_bisect %%build_parameters $artifacts/build-parameters "$@"
$reproduce_bisect || manifest_pop

obligatory_variables build_parameters rr[ci_project] rr[ci_config]
declare build_parameters

verbose="${verbose-true}"

set -u

if $verbose; then set -x; fi

mkdir -p $artifacts/jenkins
touch $artifacts/jenkins/build-name

trap print_traceback EXIT

bad_url="${bad_git%#*}"
bad_branch="${bad_git#*#}"

rebase_workaround=false
rebase_workaround_opts=()

case "${rr[ci_project]}/${rr[ci_config]}:$current_project" in
    tcwg_kernel/*-next-*:linux)
	# Workaround linux-next/master rebasing on top of linux-next/stable.
	# Search for regressions against linux-mainline:master (aka linux-next:stable).
	clone_or_update_repo $current_project stable $bad_url
	# Just in case linux-next:stable has advanced between the build and bisect jobs,
	# use merge base between linux-next:stable and $bad_git.
	bad_rev="${bad_rev-$(git_rev_parse_long $current_project $bad_branch)}"
	linux_next_stable="${linux_next_stable-$(git -C $current_project merge-base HEAD $bad_rev)}"
	cat <<EOF | manifest_out
declare -g linux_next_stable=$linux_next_stable
EOF
	echo "Rebase workaround: forcing linux baseline to $linux_next_stable"
	rebase_workaround=true
	rebase_workaround_opts+=("==rr[linux_git]"
				 "$bad_url#$linux_next_stable")
	;;
esac

# Build baseline that we are going to re-use to speed-up bisection.
# (This also confirms that infrastructure is OK.)
echo "Testing baseline (should be success)"
$build_script \
    ^^ $reproduce_bisect \
    %%rr[top_artifacts] "$rel_artifacts/build-baseline" \
    @@ $build_parameters/manifest.sh \
    ==rr[mode] build \
    ==rr[update_baseline] force \
    --verbose "$verbose" \
    "${rebase_workaround_opts[@]}"

baseline_rev="${baseline_rev-$(git -C ${current_project} rev-parse HEAD)}"
cat <<EOF | manifest_out
declare -g baseline_rev=$baseline_rev
EOF

ln -f -s "build-baseline" "$artifacts/build-$baseline_rev"

case "${rr[ci_project]}" in
    tcwg_gcc_check*|tcwg_gnu_*_check_*)
	(
	# Build up lists of flaky tests.  We do this by comparing
	# just-created baseline vs sumfiles in base-artifacts.
	fails=$(find $rel_artifacts/build-baseline \
		     -path "*-check_regression/fails.sum")
	if ! [ -f "$fails" ]; then
	    exit
	fi

	xfail_short="contrib/testsuite-management/flaky/${rr[ci_project]}-${rr[ci_config]}.xfail"
	xfail="gcc-compare-results/$xfail_short"

	if ! [ -f "$xfail" ]; then
	    echo "@include ../flaky.xfail" > "$xfail"
	fi

	(
	    echo
	    echo "# From $BUILD_URL:"
	    cat "$fails" | sed -e "s/^\([A-Z]\+: \)/flaky \| \1/"
	) >> "$xfail"

	git -C gcc-compare-results add "$xfail_short"
	git -C gcc-compare-results commit -m "From $BUILD_URL"
	git -C gcc-compare-results review -s
	git -C gcc-compare-results pull --rebase gerrit refs/heads/master
	git -C gcc-compare-results push gerrit HEAD:refs/heads/master
	) &
	res=0 && wait $! || res=$?
	# Ignore any failures in the above.
	;;
esac

mkdir -p ./bisect

# Save baseline build state, which we restore before individual bisect tests.
# This ensures that "bad" bisect tests won't affect "good" ones and vice versa.
baseline_exclude=(
    --exclude /bisect/ --exclude "/$rel_artifacts/" --exclude "/$current_project/"
)
rsync -a --del --delete-excluded "${baseline_exclude[@]}" ./ ./bisect/baseline/

mkdir $artifacts/git-logs

# Make sure the sources are clean before bisecting
git -C $current_project reset --hard

if [ -f "$replay_log" ]; then
    cp "$replay_log" $artifacts/git-logs/bisect_replay.sh
    git -C $current_project bisect replay $artifacts/git-logs/bisect_replay.sh
else
    git -C $current_project bisect start
fi

# Hard-link BISECT_LOG inside $artifacts to guarantee its upload to jenkins.
ln -f "$(pwd)"/$current_project/.git/BISECT_LOG $artifacts/git-logs/bisect_log

if ! git -C $current_project bisect log \
	| grep -q "^git bisect .* $baseline_rev\$"; then
    git -C $current_project bisect good $baseline_rev
fi

# Bisect script.
#
# With this script we find the first commit that has regressed compared
# to baseline, but not, necessarily, the commit that caused regression in
# $bad_rev.  Consider the scenario:
# - rev_10 produced good result "2000" -- this is current baseline
# - rev_20 completely broke the build (say, result "10")
# - rev_22 fixed the build
# - rev_30 regressed the build to result "1000" -- this is the regression we
#   detected vs "2000" baseline.
#
# The script will identify rev_20 as the first failing commit, which will
# cause the baseline to be reset to rev_20 with metric "10".  When we then
# rebuild master (at rev_30) we will see a /progression/ from "10" to "1000",
# thus missing the regression of "2000" to "1000".
#
# To catch the "2000" to "1000" regression someone would need to manually
# trigger bisect between rev_22 and rev_30.
#
# We reduce the impact of the above by assigning negative values to result
# metric for builds that look very broken, and do not bisect regressions into
# the "negative" side.
cat > $artifacts/test.sh <<EOF
#!/bin/bash

set -euf -o pipefail

rev=\$(git rev-parse HEAD)

if git bisect log | grep -q "^git bisect bad \$rev\\\$"; then
  exit 1
elif git bisect log | grep -q "^git bisect skip \$rev\\\$"; then
  exit 125
elif git bisect log | grep -q "^git bisect good \$rev\\\$"; then
  exit 0
fi

cd ..

# Restore known-good baseline state.
rsync -a --del ${baseline_exclude[@]} ./bisect/baseline/ ./

$build_script \
  ^^ $reproduce_bisect \
  %%rr[top_artifacts] $rel_artifacts/build-\$rev \
  @@ $rel_artifacts/build-parameters/manifest.sh \
  ==rr[mode] bisect \
  ==rr[update_baseline] ignore \
  ==rr[${current_project}_git] "$bad_url#\$rev" \
  --verbose "$verbose" &
res=0 && wait \$! || res=\$?

git -C $current_project reset --hard

if [ x"\$res" != x"0" ]; then
  if [ -f $rel_artifacts/build-\$rev/trigger-build-$current_project ]; then
    exit 1
  else
    # The build failed due to an uninteresting problem -- a prerequisite
    # failed to build or benchmarking harness went down.  We mark such
    # revisions "skipped", but up to a point.  If we skip more revisions
    # in a row, than half the number of tests necessary to finish the bisect,
    # then we mark such "skipped" revision as "bad".

    # Number of "git bisect skip" in a row
    n_skips=\$(git -C $current_project bisect log | awk '
BEGIN { n_skips=0 }
/git bisect skip/ { n_skips++; next }
/git bisect/ { n_skips=0 }
END { print n_skips }
')
    revs_left=\$(git -C $current_project bisect view --pretty=%H | wc -l)
    # Half the number of steps to finish the bisect
    n_steps_2=\$(echo "n_steps=l(\$revs_left)/l(2); scale=0; n_steps/2" | bc -l)
    if [ \$n_steps_2 -lt 2 ]; then
      # Avoid skipping revisions at the end of the bisect.
      n_steps_2=2
    fi
    if [ \$n_skips -le \$n_steps_2 ]; then
      exit 125
    else
      # We had several skips in a row and still have many revisions to bisect.
      # Mark this one "bad" to progress the bisect.
      exit 1
    fi
  fi
else
  exit 0
fi
EOF
chmod +x $artifacts/test.sh

# Fetch $bad_branch/$bad_rev from $bad_url
prev_rev=$(git -C $current_project rev-parse HEAD)
clone_or_update_repo $current_project "$bad_branch" "$bad_url"
bad_rev="${bad_rev-$(git_rev_parse_long $current_project $bad_branch)}"
cat <<EOF | manifest_out
declare -g bad_rev=$bad_rev
EOF

if [ x"$baseline_rev" = x"$bad_rev" ]; then
    echo "WARNING: Detected regression with no change in sources of $current_project"
    sed -i -e "s/\$/-no_change/" $artifacts/jenkins/build-name
    res=0
else
    # Confirm regression in $bad_rev vs $baseline_rev.
    git -C $current_project checkout --detach $bad_rev
    cd $current_project
    $artifacts/test.sh &
    res=0 && wait $! || res=$?
    cd ..
fi

# Restore revision previously checked out.  Otherwise "git bisect run"
# below will not use replay info.
git -C $current_project checkout --detach $prev_rev

if [ x"$res" = x"0" ]; then
    if $rebase_workaround; then
	echo "Rebase workaround: no regression between $baseline_rev and $bad_rev"
	sed -i -e "s/\$/-bad_rev-good/" $artifacts/jenkins/build-name
	cat >> $artifacts/trigger-build-rebase <<EOF
linux_git=$bad_url#$baseline_rev
update_baseline=force
EOF
    else
	echo "WARNING: build for bad_rev $bad_rev succeeded"
	sed -i -e "s/\$/-spurious/" $artifacts/jenkins/build-name
	# Regressions in speed benchmarking are not stable,
	# so retry with resetting baseline artifacts.
	case "${rr[ci_project]}/${rr[ci_config]}" in
	    tcwg_bmk*/*-O[23]*)
		cat > $artifacts/trigger-build-reset <<EOF
update_baseline=force
EOF
		;;
	esac
    fi
    trap "" EXIT
    exit 0
elif [ x"$res" = x"125" ]; then
    # We have confirmed a regression, but not what we have been triggered
    # to bisect.
    echo "WARNING: build for bad_rev $bad_rev showed uninteresting regression"
    sed -i -e "s/\$/-uninteresting/" $artifacts/jenkins/build-name
    trap "" EXIT
    exit 0
fi

if ! git -C $current_project bisect log \
	| grep -q "^git bisect .* $bad_rev\$"; then
    git -C $current_project bisect bad $bad_rev
    ln -f -s "build-$bad_rev" "$artifacts/build-bad"
fi

# Print first_bad revision (if detected)
get_first_bad ()
{
    (
    # Allow pipefail to handle error exit codes from git bisect log and grep.
    # Note that child shell inherits settings from parent shell, so we need
    # excplicitly set "+o pipefail".
    set -euf +o pipefail

    git -C $current_project bisect log | tail -n1 \
	| grep "^# first bad commit:" \
	| sed -e "s/^# first bad commit: \[\([0-9a-f]*\)\].*/\1/"
    )
}

# Print revs tested during bisect.
# $1 -- Revision kind -- good/bad/skip.
#       Print all revisions if no $1 given.
print_tested_revs ()
{
    (
    # Allow pipefail to handle error exit codes from git bisect log and grep.
    # Note that child shell inherits settings from parent shell, so we need
    # excplicitly set "+o pipefail".
    set -euf +o pipefail

    local kind="${1-[a-z]*}"
    git -C $current_project bisect log | grep "^git bisect $kind " \
	| sed -e "s/^git bisect $kind //"
    )
}

# Generate list of commits inside the bisection range.
commits_to_test=$artifacts/git-logs/commits_to_test
git -C $current_project bisect view --pretty=%H > $commits_to_test

# Record commits in the bisect range.  These are commits_to_test plus
# commits that have been tested.
commits_in_range=$artifacts/git-logs/commits_in_range
cp $commits_to_test $commits_in_range
print_tested_revs >> $commits_in_range

# Try to reduce bisection range by testing regressions (and their parents)
# identified in other configurations.
print_interesting_commits ()
{
    (
    set -euf -o pipefail

    # Bisecting linux-next.git regressions is difficult enough due to how
    # the tree is constructed, so we prefer to not use interesting-commits
    # when $rebase_workaround is true.  This makes linux-next bisects as
    # natural as they can be.
    if $rebase_workaround; then
	return
    fi

    # Clone interesting-commits.git repo, which contains a list of SHA1s
    # that might cut down bisection time.  Mostly, these are first_bad and
    # last_good commits.
    local icommits="bisect/interesting-commits"
    clone_or_update_repo $icommits master \
			 https://git-us.linaro.org/toolchain/ci/interesting-commits.git \
			 auto master >/dev/null 2>&1

    local project_dir
    project_dir=$icommits/$(interesting_subdir $current_project)

    if ! [ -d "$project_dir" ]; then
	return
    fi

    # Below loop can generate lots of console noise.
    set +x

    local sha1
    while read sha1; do
	# Ignore commits outside of bisection range.
	if ! grep -q "^$sha1\$" $commits_to_test; then
	    continue
	fi
	while read prev_sha1; do
	    if ! grep -q "^$prev_sha1\$" $commits_to_test; then
		continue
	    fi
	    echo "$prev_sha1"
	done < <(cd "$project_dir/$sha1"
		 find -name last_good -print0 | xargs -0 cat | sort -u)
	# Print last_good revisions first, then print out first_bad sha1.
	# It's a minor heuristic optimization in bisect order.
	echo "$sha1"
    done < <(cd "$project_dir"; ls)
    )
}

IFS=" " read -r -a interesting_sha1s <<< "$(print_interesting_commits)"

echo "We have ${#interesting_sha1s[@]} interesting commits to try"
while [ ${#interesting_sha1s[@]} != 0 ] \
	  && [ x"$(get_first_bad </dev/null)" = x"" ]; do
    sha1=${interesting_sha1s[0]}
    interesting_sha1s=("${interesting_sha1s[@]:1}")

    # Ignore commits outside of bisection range.
    if ! grep -q "^$sha1\$" $commits_to_test; then
	continue
    fi

    # Skip revisions that were already tested.  Good revisions are filtered
    # out in the above $commits_to_test check, and here we filter out
    # "bad" and "skip" revisions.
    if git -C $current_project bisect log | grep -q "^git bisect .* $sha1\$"; then
	continue
    fi

    if $verbose; then set -x; fi

    git -C $current_project checkout --detach $sha1
    cd $current_project
    $artifacts/test.sh &
    res=0 && wait $! || res=$?
    cd ..
    if [ x"$res" = x"0" ]; then
	git -C $current_project bisect good
    elif [ x"$res" = x"125" ]; then
	git -C $current_project bisect skip
    else
	git -C $current_project bisect bad
    fi
    git -C $current_project bisect view --pretty=%H > $commits_to_test
done

if [ x"$(get_first_bad)" = x"" ]; then
    cd $current_project
    git bisect run $artifacts/test.sh &
    res=0 && wait $! || res=$?
    cd ..

    if [ x"$res" = x"0" ]; then
	assert_with_msg "Didn't find first bad commit!" [ x"$(get_first_bad)" != x"" ]
    fi
fi

first_bad=$(get_first_bad)

if [ x"$first_bad" != x"" ] \
       && ! [ -f $artifacts/build-$first_bad/trigger-build-$current_project ]; then
    # First_bad is not a real or "interesting" regression.  Perhaps it was
    # a "skipped" commit marked as "bad.
    first_bad=""
fi

if [ x"$first_bad" != x"" ]; then
    # "git bisect run" succeeded.  Check whether this is an actual regression
    # or bisection artifact.
    last_good=""
    bad_last_good=""
    for sha1 in $(git -C $current_project rev-parse $first_bad^@); do
	# It seems that git-bisect assumes parent commit as "good" on
	# the basis of one of its children being "good".  Therefore we
	# can have a situation when we have parent P with children C1 and C2,
	# and child C1 has a child of its own CB.  Git-bisect tests C2 as
	# "good", and CB as "bad".  From C2 being good it assumes P as "good",
	# and it knows CB is "bad", so git-bisect returns C1 as the first bad
	# commit.
	# To simplify investigations we explicitly test parent of $first_bad.

	# Ignore commits outside of bisection range, but make an exception
	# for commits that weren't tested due to their child tested good.
	# This happens in projects that actively use merges, e.g., linux.
	if ! grep -q "^$sha1\$" $commits_in_range; then
	    child_tested_good=false
	    for tested_good in $(print_tested_revs good); do
		if git -C $current_project merge-base --is-ancestor $sha1 $tested_good; then
		    child_tested_good=true
		    break
		fi
	    done
	    if ! $child_tested_good; then
		continue
	    fi
	fi

	echo "Testing first_bad's parent $sha1 (hoping for success)"
	git -C $current_project checkout --detach "$sha1"
	cd $current_project
	$artifacts/test.sh &
	res=0 && wait $! || res=$?
	cd ..
	if [ x"$res" = x"0" ]; then
	    last_good=$sha1
	    break
	fi
	bad_last_good=$sha1
    done

    if [ x"$last_good" = x"" ]; then
	assert_with_msg "Broken bisection range" [ x"$bad_last_good" != x"" ]
	# All parents of $first_bad tested bad.  This is, essencially,
	# same situation as "git bisect" failing, which we handle below.
	first_bad=""
    fi
fi

reset_rev=""
if [ x"$first_bad" != x"" ]; then
    reset_rev="$first_bad"
else
    # "Git bisect" didn't find the first_bad commit or this commit points to
    # an uninteresting regression.
    # Possible reasons include:
    # - We have marked the regressing commit as "skip", which can happen
    #   to tcwg_bmk* projects when benchmarking infra has a problem.
    #
    # - Merge-base of $baseline_rev and $bad_rev is worse than $baseline_rev.
    #   We want to reset baseline to HEAD in this case, so that we catch most
    #   of the commits that introduced change in the result metric.
    #
    # - We have marked a skipped commit as bad to advance bisect, even though
    #   the failure was uninteresting.
    #
    # So, to make at least some progress on narrowing down the regression ...
    # - look for the last commit that tested "good".  If it's not $baseline_rev,
    #   then we have narrowed down the bisection range somewhat.  Therefore,
    #   trigger two builds:
    #   - one to ADVANCE baseline to the last GOOD commit, and
    #   - another to expose the regression again.
    #
    # - If $baseline_rev is the only good commit, then we have got ourselves
    #   into a tricky situation: we can't find the regression and can't make
    #   a good build, which would advance the baseline.  To resolve this,
    #   trigger two builds:
    #   - one to RESET baseline to the last BAD commit, and
    #   - another to advance the baseline and expose another regression.
    #   Note that this approach correctly handles case when merge-base of
    #   $baseline_rev and $bad_rev tests "bad".

    last_good=$(print_tested_revs good | tail -n1)
    assert_with_msg "We should have at least baseline_rev as a good commit" \
		    [ x"$last_good" != x"" ]

    if [ x"$last_good" != x"$baseline_rev" ]; then
	sed -i -e "s/\$/-advance-baseline/" $artifacts/jenkins/build-name
    else
	# Reset baseline to the earliest bad revision with a true regression.
	# For this we look through tested-bad revisions in reverse order.
	for reset_rev in $(print_tested_revs bad | tac); do
	    if [ -f $artifacts/build-$reset_rev/trigger-build-$current_project ]; then
		break
	    fi
	done
	sed -i -e "s/\$/-reset-baseline/" $artifacts/jenkins/build-name
    fi
fi

# Bisect is officially over.

# Create trigger-build-* files for subsequent builds.

# Advance the baseline to $last_good revision.  Don't trigger unnecessary
# build for $baseline_rev itself.
if [ x"$last_good" != x"$baseline_rev" ]; then
    assert_with_msg "last_good should not be empty" [ x"$last_good" != x"" ]
    cat > $artifacts/trigger-build-1-last-good <<EOF
${current_project}_git=$bad_url#$last_good
update_baseline=force
EOF
    # Note that even though $last_good build should succeed, we are forcing
    # it to update the baseline.  Otherwise, should the last-good build fail,
    # it will start a bisect job, which will trigger some more builds.
    # The problem is that, as soon as our first-bad build resets the baseline,
    # all those builds triggered by the 2nd bisect will operate "in the past".
    # Therefore, we either need to handle builds "from the past", or, easier,
    # just force the last-good build to always succeed.
fi

if ! [ -f $artifacts/build-$bad_rev/trigger-build-$current_project ]; then
    # This can happen *only* when replaying bisects.
    # Otherwise $bad_rev is always tested second to $baseline_rev.
    bad_build=$(find $artifacts -path "$artifacts/build-*/trigger-build-$current_project" | tail -n1)
    assert_with_msg "No bad build during this bisect" [ x"$bad_build" != x"" ]
    mkdir -p $artifacts/build-$bad_rev
    cp $bad_build $artifacts/build-$bad_rev/trigger-build-$current_project
    sed -i -e "s/^\(${current_project}_git=.*\)#.*\$/\1#$bad_rev/" \
	$artifacts/build-$bad_rev/trigger-build-$current_project
fi

if [ x"$reset_rev" != x"" ]; then \
    if ! [ -f $artifacts/build-$reset_rev/trigger-build-$current_project ]; then
	# This is rare, but can happen that $reset_rev hasn't been tested.
	# Workaround by constructing trigger-build file from that of $bad_rev's.
	mkdir -p $artifacts/build-$reset_rev
	cp $artifacts/build-$bad_rev/trigger-build-$current_project \
	   $artifacts/build-$reset_rev/trigger-build-$current_project
	sed -i -e "s/^\(${current_project}_git=.*\)#$bad_rev\$/\1#$reset_rev/" \
	    $artifacts/build-$reset_rev/trigger-build-$current_project
    fi

    # Reset baseline to the regressed commit so that we will catch subsequent
    # regressions (worse than $bad_rev).
    cp $artifacts/build-$reset_rev/trigger-build-$current_project \
       $artifacts/trigger-build-2-reset
    echo "update_baseline=force" >> $artifacts/trigger-build-2-reset
fi

# Trigger master build now instead of waiting for next timed SCM trigger.
cp $artifacts/build-$bad_rev/trigger-build-$current_project \
   $artifacts/trigger-build-3-default

# Save BISECT_* logs
find "$current_project" -path "$current_project/.git/BISECT_*" -print0 \
    | xargs -0 -I@ mv @ $artifacts/git-logs/

if [ x"$first_bad" != x"" ]; then
    sed -i -e "s/\$/-$first_bad/" $artifacts/jenkins/build-name

    ln -f -s "build-$first_bad" "$artifacts/build-first_bad"
    ln -f -s "build-$last_good" "$artifacts/build-last_good"
fi

trap "" EXIT