script to automate binary search for regression

script to automate binary search for regression

[Janis Johnson]

[-- Attachment #1: Type: text/plain, Size: 1068 bytes --]

Here's the script I'm using to do binary searches to locate regressions.
It invokes separate scripts to do the real work: update CVS, build GCC,
and run the test.  It starts with two specified dates and calls the
user-provided scripts in a binary search to narrow the time range where
the test behaviour changed to a specified time range, one hour by
default.  There are no restrictions on the starting dates, they just
need to be recognized by the date command.  It uses an extension in GNU
date to convert a date to seconds from the epoch, but on a system where
GNU date isn't an option that part could be replaced by a small C
program to do the conversion.

Since you provide the other scripts, they can do whatever you want: use
a CVS branch, build only cc1plus or do a full bootstrap, and whatever it
takes to run the test.

The length of the script is mostly due to comments and lots of error
checking.  I've tested it fairly thoroughly.  If you find this helpful,
let me know and I'll ask about adding it to contrib.

Janis Johnson
IBM Linux Technology Center


[-- Attachment #2: regsearch --]
[-- Type: text/plain, Size: 7929 bytes --]

#! /bin/sh

########################################################################
#
# File:    regsearch
# Author:  Janis Johnson <janis187@us.ibm.com>
# Date:    2002/12/15
#
# Search for a small time interval within a range of dates in which
# results for a test changed, using a binary search.  The functionality
# for getting GCC sources, building a compiler, and running the test are
# in other scripts that are run from here.  Before the search begins, we
# verify that we get the expected behavior for the first and last dates.
#
# Define these in a file whose name is the argument to this script:
#   LOW_DATE:   Date string recognized by the date command.
#   HIGH_DATE:  Date string recognized by the date command.
#   UPDATE_CVS: Script to update your GCC source tree.
#   BUILD_GCC:  Script to build enough of GCC to run the test.
#   RUN_TEST:   Script to run the test; returns 1 if we should search
#               later dates, 0 if we should search earlier dates.
# Optional:
#   DELTA:      Search to an interval within this many seconds; default
#               is one hour.
#   SKIP_ENDS   Skip verifying the end points of the range if this is 1;
#               define this only if you're restarting and have already
#               tested the low and high dates.
#   FIRST_MID   Use this as the first midpoint, for avoiding a midpoint
#               that is known not to build.
#   VERBOSITY   Default is 0, to print only errors and final message.
#   DATE_IN_MSG If defined, include the time and date in messages.
#
# Janis has scripts to test this one, including error checking.
#
#
# Copyright (c) 2002 Free Software Foundation, Inc.
#
# This file is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# For a copy of the GNU General Public License, write the the
# Free Software Foundation, Inc., 59 Temple Place - Suite 330,
# Boston, MA 02111-1307, USA.
# 
########################################################################

########################################################################
# Functions
########################################################################

# Issue a message if it's verbosity level is high enough.

msg() {
  test ${1} -gt ${VERBOSITY}  && return

  if [ "x${DATE_IN_MSG}" = "x" ]; then
    echo "${2}"
  else
    echo "`date`  ${2}"
  fi
}

# Issue an error message and exit with a non-zero status.  If there
# is a valid current range whose end points have been tested, report
# it so the user can start again from there.

error() {
  msg 0 "error: ${1}"
  test ${VALID_RANGE} -eq 1 && \
    echo "current range is between ${LATER_THAN} and ${EARLIER_THAN}"
  exit 1
}

# Turn seconds since the epoch into a date we can use with CVS and
# report to the user.

make_date() {
  MADE_DATE="`date +\"%Y-%m-%d %H:%M\" --date \"1970-01-01 00:00:${1} UTC\"`" \
    || error "make_date: date command failed"
}

# Build a compiler using sources as of a particular date and run a
# test case.  Pass each of the scripts the date that we're testing;
# the first one needs it, the others can ignore it if they want.

process_date() {
  DATE="${1}"

  ${UPDATE_CVS} "${DATE}" || error "cvs update failed for ${DATE}"
  ${BUILD_GCC} "${DATE}"  || error "compiler build failed for ${DATE}"
  ${RUN_TEST} "${DATE}"
  LATER=$?
}

# Perform a binary search on dates within the range specified by
# the arguments, bounded by the number of seconds in DELTA.

search_dates() {
  let LOW=$1
  let HIGH=$2
  let DIFF=HIGH-LOW

  # Get the date in the middle of the range; MID is in seconds since
  # the epoch, DATE is readable by humans and CVS.  The user can
  # override the initial mid date if it is known to have problems,
  # e.g., if GCC doesn't build on that date.

  if [ ${FIRST_MID} -ne 0 ]; then
    let MID=${FIRST_MID}
  else
    let MID=LOW/2+HIGH/2
  fi

  while [ ${DIFF} -ge ${DELTA} ]; do
    make_date ${MID}
    DATE="${MADE_DATE}"

    # Test it.

    process_date "${DATE}"

    # Narrow the search based on the outcome of testing DATE.

    if [ ${LATER} -eq 1 ]; then
      msg 1 "search dates later than ${DATE}"
      LATER_THAN="${DATE}"
      let LOW=MID
    else
      msg 1 "search dates earlier than ${DATE}"
      EARLIER_THAN="${DATE}"
      let HIGH=MID
    fi

    let DIFF=HIGH-LOW
    let MID=LOW/2+HIGH/2
  done
}

########################################################################
# Main program (so to speak)
########################################################################

# The error function uses this.

VALID_RANGE=0

# Process the configuration file.

if [ $# != 1 ]; then
  echo Usage: $0 config_file
  exit 1
fi

CONFIG=${1}
if [ ! -f ${CONFIG} ]; then
  error "configuration file ${CONFIG} does not exist"
fi

# OK, the config file exists.  Source it, make sure required parameters
# are defined and their files exist, and give default values to optional
# parameters.

. ${CONFIG}

test "x${UPDATE_CVS}" = "x" && error "UPDATE_CVS is not defined"
test "x${BUILD_GCC}" = "x" && error "BUILD_GCC is not defined"
test "x${RUN_TEST}" = "x" && error "RUN_TEST is not defined"
test -x ${RUN_TEST} || error "RUN_TEST is not an executable file"
test "x${SKIP_ENDS}" = "x" && SKIP_ENDS=0
test "x${DELTA}" = "x" && DELTA=3600
test "x${VERBOSITY}" = "x" && VERBOSITY=0

msg 2 "LOW_DATE   = ${LOW_DATE}"
msg 2 "HIGH_DATE  = ${HIGH_DATE}"
msg 2 "UPDATE_CVS = ${UPDATE_CVS}"
msg 2 "BUILD_GCC  = ${BUILD_GCC}"
msg 2 "RUN_TEST   = ${RUN_TEST}"
msg 2 "SKIP_ENDS  = ${SKIP_ENDS}"
msg 2 "FIRST_MID  = ${FIRST_MID}"
msg 2 "VERBOSITY  = ${VERBOSITY}"
msg 2 "DELTA      = ${DELTA}"

# Verify that DELTA is at least two minutes.

test ${DELTA} -le 120 && \
  error "DELTA is ${DELTA}, must be at least 120 (two minutes)"

# Change the dates into seconds since the epoch.  This uses an extension
# in GNU date.

LOW_DATE=`date +%s --date "${LOW_DATE}"` || \
  error "date command failed for \"${LOW_DATE}\""
HIGH_DATE=`date +%s --date "${HIGH_DATE}"` || \
  error "date command failed for \"${LOW_DATE}\""

# If FIRST_MID was defined, convert it and make sure it's in the range.

if [ "x${FIRST_MID}" != "x" ]; then
  FIRST_MID=`date +%s --date "${FIRST_MID}"` || \
    error "date command failed for \"${FIRST_MID}\""
  test ${FIRST_MID} -le ${LOW_DATE}  && \
    error "FIRST_MID date is earlier than LOW_DATE"
  test ${FIRST_MID} -ge ${HIGH_DATE} && \
    error "FIRST_MID is later than HIGH_DATE"
else
  FIRST_MID=0
fi 

# Keep track of the bounds of the range where the test behavior changes,
# using a human-readable version of each date.

make_date ${LOW_DATE}
LATER_THAN="${MADE_DATE}"
make_date ${HIGH_DATE}
EARLIER_THAN="${MADE_DATE}"

# Verify that the range isn't backwards.

test ${LOW_DATE} -lt ${HIGH_DATE} || error "date range is backwards"

# Verify that the first and last date in the range get the results we
# expect.  If not, quit, because any of several things could be wrong.

if [ ${SKIP_ENDS} -eq 0 ]; then
  process_date "${LATER_THAN}"
  test ${LATER} -ne 1 && \
    error "unexpected result for low date ${LATER_THAN}"
  msg 1 "result for low date is as expected"

  process_date "${EARLIER_THAN}"
  test ${LATER} -ne 0 && \
    error "unexpected result for high date ${EARLIER_THAN}"
  msg 1 "result for high date is as expected"
fi

# Search within the range, now that we know that the end points are valid.

VALID_RANGE=1
search_dates ${LOW_DATE} ${HIGH_DATE}

# Report the range that's left to investigate.

echo "Continue search between ${LATER_THAN} and ${EARLIER_THAN}"

Re: script to automate binary search for regression

[Phil Edwards]

On Mon, Dec 16, 2002 at 09:23:50AM -0800, Janis Johnson wrote:
> The length of the script is mostly due to comments and lots of error
> checking.  I've tested it fairly thoroughly.  If you find this helpful,
> let me know and I'll ask about adding it to contrib.

Yes, please.  This is very useful.  We should probably also check in an
initial "config file", and some simple skeleton scripts for the cvs calls.
And yes, by "we" I mean I'll help once this one's checked in.  :-)

> #! /bin/sh

Since the "let" builtin is a POSIX thing, and it's been made woefully clear
that GCC can't depend on /bin/sh actually being POSIX, this script should
either a) document that fact, or b) just use a different shell.


Phil

-- 
I would therefore like to posit that computing's central challenge, viz. "How
not to make a mess of it," has /not/ been met.
                                                 - Edsger Dijkstra, 1930-2002

Re: script to automate binary search for regression

[Janis Johnson]

On Mon, Dec 16, 2002 at 09:43:41PM -0500, Phil Edwards wrote:
> On Mon, Dec 16, 2002 at 09:23:50AM -0800, Janis Johnson wrote:
> > The length of the script is mostly due to comments and lots of error
> > checking.  I've tested it fairly thoroughly.  If you find this helpful,
> > let me know and I'll ask about adding it to contrib.
> 
> Yes, please.  This is very useful.  We should probably also check in an
> initial "config file", and some simple skeleton scripts for the cvs calls.
> And yes, by "we" I mean I'll help once this one's checked in.  :-)
> 
> > #! /bin/sh
> 
> Since the "let" builtin is a POSIX thing, and it's been made woefully clear
> that GCC can't depend on /bin/sh actually being POSIX, this script should
> either a) document that fact, or b) just use a different shell.

I don't know if Phil has authority to say this can go into contrib, but
here's the latest version of my framework for hunting regressions, with
a few more nifty ways to cut down a search.  It works for bash, but
probably not other shells, and depends on an extension in GNU date.

This script doesn't do the real work; that's done by scripts the user
provides to get the sources, do the build, and run the test, which will
vary greatly depending on the kind of bug being hunted.  I can put
examples of those somewhere.

May I add this to contrib?

Janis Johnson
IBM Linux Technology Center, OzLabs North

--- /tmp/empty	Wed Dec 18 11:32:07 2002
+++ contrib/reg_search	Wed Dec 18 11:30:32 2002
@@ -0,0 +1,273 @@
+#! /bin/bash
+
+########################################################################
+#
+# File:    reg_search
+# Author:  Janis Johnson <janis187@us.ibm.com>
+# Date:    2002/12/18
+#
+# Search for a small time interval within a range of dates in which
+# results for a test changed, using a binary search.  The functionality
+# for getting sources, building the component to test, and running the
+# test are in other scripts that are run from here.  Before the search
+# begins, we verify that we get the expected behavior for the first and
+# last dates.
+#
+# Define these in a file whose name is the argument to this script:
+#   LOW_DATE:   Date string recognized by the date command (UTC).
+#   HIGH_DATE:  Date string recognized by the date command (UTC).
+#   UPDATE_SRC: Pathname of script to update your source tree.
+#   BUILD:      Pathname of script to build enough of the product to run
+#               the test.
+#   RUN_TEST:   Pathname of script to run the test; returns 1 if we
+#               should search later dates, 0 if we should search earlier
+#               dates.
+# Optional:
+#   DELTA:      Search to an interval within this many seconds; default
+#               is one hour.
+#   SKIP_ENDS   If 1, skip verifying the end points of the range; define
+#               this only if you're restarting and have already tested
+#               the low and high dates.
+#   FIRST_MID   Use this as the first midpoint, to avoid a midpoint that
+#               is known not to build.
+#   VERBOSITY   Default is 0, to print only errors and final message.
+#   HAS_CHANGES Pathname of script to report whether the current date has
+#               no differences from one of the ends of the current range
+#               to skip unnecessary build and testing; default is "true".
+#   DATE_IN_MSG If set to anything but 0, include the time and date in
+#               messages.
+#
+# Janis has scripts to test this one, including error checking.
+#
+#
+# Copyright (c) 2002 Free Software Foundation, Inc.
+#
+# This file is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# For a copy of the GNU General Public License, write the the
+# Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+# Boston, MA 02111-1307, USA.
+# 
+########################################################################
+
+########################################################################
+# Functions
+########################################################################
+
+# Issue a message if it's verbosity level is high enough.
+
+msg() {
+  test ${1} -gt ${VERBOSITY}  && return
+
+  if [ "x${DATE_IN_MSG}" = "x" ]; then
+    echo "${2}"
+  else
+    echo "`date`  ${2}"
+  fi
+}
+
+# Issue an error message and exit with a non-zero status.  If there
+# is a valid current range whose end points have been tested, report
+# it so the user can start again from there.
+
+error() {
+  msg 0 "error: ${1}"
+  test ${VALID_RANGE} -eq 1 && \
+    echo "current range is between ${LATER_THAN} and ${EARLIER_THAN}"
+  exit 1
+}
+
+# Turn seconds since the epoch into a date we can use with source
+# control tools and report to the user.
+
+make_date() {
+  MADE_DATE="`date -u +\"%Y-%m-%d %H:%M\" --date \"1970-01-01 00:00:${1} UTC\"`" \
+    || error "make_date: date command failed"
+}
+
+# Build the components to test using sources as of a particular date and
+# run a test case.  Pass each of the scripts the date that we're
+# testing; the first one needs it, the others can ignore it if they want.
+
+process_date() {
+  DATE="${1}"
+
+  ${UPDATE_SRC} "${DATE}" || error "source update failed for ${DATE}"
+
+  # If we're already in a valid range, skip this date if there are no
+  # differences from either end of the range and adjust LATER.
+
+  if [ ${VALID_RANGE} = 1 ]; then
+    ${HAS_CHANGES} "${DATE}" "${LATER_THAN}" "${EARLIER_THAN}"
+    RET=$?
+    case ${RET} in
+    0) ;;
+    1) LATER=1; return;;
+    2) LATER=0; return;;
+    *) error "process_date: unexpected return value from ${HAS_CHANGES}";;
+    esac
+  fi
+
+  ${BUILD} "${DATE}"  || error "build failed for ${DATE}"
+  ${RUN_TEST} "${DATE}"
+  LATER=$?
+}
+
+# Perform a binary search on dates within the range specified by
+# the arguments, bounded by the number of seconds in DELTA.
+
+search_dates() {
+  let LOW=$1
+  let HIGH=$2
+  let DIFF=HIGH-LOW
+
+  # Get the date in the middle of the range; MID is in seconds since
+  # the epoch, DATE is readable by humans and tools.  The user can
+  # override the initial mid date if it is known to have problems,
+  # e.g., if a build fails for that date.
+
+  if [ ${FIRST_MID} -ne 0 ]; then
+    let MID=${FIRST_MID}
+  else
+    let MID=LOW/2+HIGH/2
+  fi
+
+  while [ ${DIFF} -ge ${DELTA} ]; do
+    make_date ${MID}
+    DATE="${MADE_DATE}"
+
+    # Test it.
+
+    process_date "${DATE}"
+
+    # Narrow the search based on the outcome of testing DATE.
+
+    if [ ${LATER} -eq 1 ]; then
+      msg 1 "search dates later than ${DATE}"
+      LATER_THAN="${DATE}"
+      let LOW=MID
+    else
+      msg 1 "search dates earlier than ${DATE}"
+      EARLIER_THAN="${DATE}"
+      let HIGH=MID
+    fi
+
+    let DIFF=HIGH-LOW
+    let MID=LOW/2+HIGH/2
+  done
+}
+
+########################################################################
+# Main program (so to speak)
+########################################################################
+
+# The error function uses this.
+
+VALID_RANGE=0
+
+# Process the configuration file.
+
+if [ $# != 1 ]; then
+  echo Usage: $0 config_file
+  exit 1
+fi
+
+CONFIG=${1}
+if [ ! -f ${CONFIG} ]; then
+  error "configuration file ${CONFIG} does not exist"
+fi
+
+# OK, the config file exists.  Source it, make sure required parameters
+# are defined and their files exist, and give default values to optional
+# parameters.
+
+. ${CONFIG}
+
+test "x${UPDATE_SRC}" = "x" && error "UPDATE_SRC is not defined"
+test "x${BUILD}" = "x" && error "BUILD is not defined"
+test "x${RUN_TEST}" = "x" && error "RUN_TEST is not defined"
+test -x ${RUN_TEST} || error "RUN_TEST is not an executable file"
+test "x${SKIP_ENDS}" = "x" && SKIP_ENDS=0
+test "x${DELTA}" = "x" && DELTA=3600
+test "x${VERBOSITY}" = "x" && VERBOSITY=0
+test "x${HAS_CHANGES}" = "x" && HAS_CHANGES=true
+
+msg 2 "LOW_DATE   = ${LOW_DATE}"
+msg 2 "HIGH_DATE  = ${HIGH_DATE}"
+msg 2 "UPDATE_SRC = ${UPDATE_SRC}"
+msg 2 "BUILD      = ${BUILD}"
+msg 2 "RUN_TEST   = ${RUN_TEST}"
+msg 2 "SKIP_ENDS  = ${SKIP_ENDS}"
+msg 2 "FIRST_MID  = ${FIRST_MID}"
+msg 2 "VERBOSITY  = ${VERBOSITY}"
+msg 2 "DELTA      = ${DELTA}"
+
+# Verify that DELTA is at least two minutes.
+
+test ${DELTA} -le 120 && \
+  error "DELTA is ${DELTA}, must be at least 120 (two minutes)"
+
+# Change the dates into seconds since the epoch.  This uses an extension
+# in GNU date.
+
+LOW_DATE=`date +%s --date "${LOW_DATE}"` || \
+  error "date command failed for \"${LOW_DATE}\""
+HIGH_DATE=`date +%s --date "${HIGH_DATE}"` || \
+  error "date command failed for \"${LOW_DATE}\""
+
+# If FIRST_MID was defined, convert it and make sure it's in the range.
+
+if [ "x${FIRST_MID}" != "x" ]; then
+  FIRST_MID=`date +%s --date "${FIRST_MID}"` || \
+    error "date command failed for \"${FIRST_MID}\""
+  test ${FIRST_MID} -le ${LOW_DATE}  && \
+    error "FIRST_MID date is earlier than LOW_DATE"
+  test ${FIRST_MID} -ge ${HIGH_DATE} && \
+    error "FIRST_MID is later than HIGH_DATE"
+else
+  FIRST_MID=0
+fi 
+
+# Keep track of the bounds of the range where the test behavior changes,
+# using a human-readable version of each date.
+
+make_date ${LOW_DATE}
+LATER_THAN="${MADE_DATE}"
+make_date ${HIGH_DATE}
+EARLIER_THAN="${MADE_DATE}"
+
+# Verify that the range isn't backwards.
+
+test ${LOW_DATE} -lt ${HIGH_DATE} || error "date range is backwards"
+
+# Verify that the first and last date in the range get the results we
+# expect.  If not, quit, because any of several things could be wrong.
+
+if [ ${SKIP_ENDS} -eq 0 ]; then
+  process_date "${LATER_THAN}"
+  test ${LATER} -ne 1 && \
+    error "unexpected result for low date ${LATER_THAN}"
+  msg 1 "result for low date is as expected"
+
+  process_date "${EARLIER_THAN}"
+  test ${LATER} -ne 0 && \
+    error "unexpected result for high date ${EARLIER_THAN}"
+  msg 1 "result for high date is as expected"
+fi
+
+# Search within the range, now that we know that the end points are valid.
+
+VALID_RANGE=1
+search_dates ${LOW_DATE} ${HIGH_DATE}
+
+# Report the range that's left to investigate.
+
+echo "Continue search between ${LATER_THAN} and ${EARLIER_THAN}"

Re: script to automate binary search for regression

[Phil Edwards]

Digging this out of the archives...


On Wed, Dec 18, 2002 at 11:44:20AM -0800, Janis Johnson wrote:
> On Mon, Dec 16, 2002 at 09:43:41PM -0500, Phil Edwards wrote:
> > On Mon, Dec 16, 2002 at 09:23:50AM -0800, Janis Johnson wrote:
> > > The length of the script is mostly due to comments and lots of error
> > > checking.  I've tested it fairly thoroughly.  If you find this helpful,
> > > let me know and I'll ask about adding it to contrib.
> > 
> > Yes, please.  This is very useful.  We should probably also check in an
> > initial "config file", and some simple skeleton scripts for the cvs calls.
> > And yes, by "we" I mean I'll help once this one's checked in.  :-)
> > 
> > > #! /bin/sh
> > 
> > Since the "let" builtin is a POSIX thing, and it's been made woefully clear
> > that GCC can't depend on /bin/sh actually being POSIX, this script should
> > either a) document that fact, or b) just use a different shell.
> 
> I don't know if Phil has authority to say this can go into contrib, but

I don't know either.


> here's the latest version of my framework for hunting regressions, with
> a few more nifty ways to cut down a search.  It works for bash, but
> probably not other shells, and depends on an extension in GNU date.
> 
> This script doesn't do the real work; that's done by scripts the user
> provides to get the sources, do the build, and run the test, which will
> vary greatly depending on the kind of bug being hunted.  I can put
> examples of those somewhere.
> 
> May I add this to contrib?
> 
> Janis Johnson
> IBM Linux Technology Center, OzLabs North
> 
> --- /tmp/empty	Wed Dec 18 11:32:07 2002
> +++ contrib/reg_search	Wed Dec 18 11:30:32 2002
> @@ -0,0 +1,273 @@
> +#! /bin/bash
> +
[...]

How about making a contrib/reg_search directory, checking the script in
there, along with some sample config files?

Any objections from anyone?


Phil

-- 
I would therefore like to posit that computing's central challenge, viz. "How
not to make a mess of it," has /not/ been met.
                                                 - Edsger Dijkstra, 1930-2002