1#! /bin/bash 2 3######################################################################## 4# 5# File: reg_search 6# Author: Janis Johnson <janis187@us.ibm.com> 7# Date: 2002/12/15 8# 9# Search for a small time interval within a range of dates in which 10# results for a test changed, using a binary search. The functionality 11# for getting sources, building the component to test, and running the 12# test are in other scripts that are run from here. Before the search 13# begins, we verify that we get the expected behavior for the first and 14# last dates. 15# 16# Define these in a file whose name is the argument to this script: 17# LOW_DATE: Date string recognized by the date command (local time). 18# HIGH_DATE: Date string recognized by the date command (local time). 19# REG_UPDATE: Pathname of script to update your source tree; returns 20# zero for success, nonzero for failure. 21# REG_BUILD: Pathname of script to build enough of the product to run 22# the test; returns zero for success, nonzero for failure. 23# REG_TEST: Pathname of script to run the test; returns 1 if we 24# should search later dates, 0 if we should search earlier 25# dates. 26# Optional: 27# DELTA: Search to an interval within this many seconds; default 28# is one hour (although 300 works well). 29# REG_FINISH Pathname of script to call at the end with the two final 30# dates as arguments. 31# SKIP_LOW If 1, skip verifying the low date of the range; 32# define this only if you're restarting and have already 33# tested the low date. 34# SKIP_HIGH If 1, skip verifying the high date of the range; 35# define this only if you're restarting and have already 36# tested the high date. 37# FIRST_MID Use this as the first midpoint, to avoid a midpoint that 38# is known not to build. 39# HAS_CHANGES Pathname of script to report whether the current date has 40# no differences from one of the ends of the current range 41# to skip unnecessary build and testing; default is "true". 42# VERBOSITY Default is 0, to print only errors and final message. 43# DATE_IN_MSG If set to anything but 0, include the time and date in 44# messages. 45# 46# 47# 48# Copyright (c) 2002, 2003, 2005 Free Software Foundation, Inc. 49# 50# This file is free software; you can redistribute it and/or modify 51# it under the terms of the GNU General Public License as published by 52# the Free Software Foundation; either version 2 of the License, or 53# (at your option) any later version. 54# 55# This program is distributed in the hope that it will be useful, 56# but WITHOUT ANY WARRANTY; without even the implied warranty of 57# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 58# GNU General Public License for more details. 59# 60# For a copy of the GNU General Public License, write the the 61# Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 62# Boston, MA 02110-1301, USA. 63# 64######################################################################## 65 66######################################################################## 67# Functions 68######################################################################## 69 70# Issue a message if its verbosity level is high enough. 71 72msg() { 73 test ${1} -gt ${VERBOSITY} && return 74 75 if [ "x${DATE_IN_MSG}" = "x" ]; then 76 echo "${2}" 77 else 78 echo "`${DATE}` ${2}" 79 fi 80} 81 82# Issue an error message and exit with a non-zero status. If there 83# is a valid current range whose end points have been tested, report 84# it so the user can start again from there. 85 86error() { 87 msg 0 "error: ${1}" 88 test ${VALID_RANGE} -eq 1 && \ 89 echo "current range:" 90 echo "LOW_DATE=\"${LATER_THAN}\"" 91 echo "HIGH_DATE=\"${EARLIER_THAN}\"" 92 exit 1 93} 94 95# Turn seconds since the epoch into a date we can use with source 96# control tools and report to the user. 97 98make_date() { 99 MADE_DATE="`${DATE} -u +\"%Y-%m-%d %H:%M %Z\" --date \"1970-01-01 ${1} seconds\"`" \ 100 || error "make_date: date command failed" 101} 102 103# Build the components to test using sources as of a particular date and 104# run a test case. Pass each of the scripts the date that we're 105# testing; the first one needs it, the others can ignore it if they want. 106 107process_date() { 108 TEST_DATE="${1}" 109 110 ${REG_UPDATE} "${TEST_DATE}" || error "source update failed for ${TEST_DATE}" 111 112 # If we're already in a valid range, skip this date if there are no 113 # differences from either end of the range and adjust LATER. 114 115 if [ ${VALID_RANGE} = 1 ]; then 116 ${HAS_CHANGES} "${TEST_DATE}" "${LATER_THAN}" "${EARLIER_THAN}" 117 RET=$? 118 case ${RET} in 119 0) ;; 120 1) LATER=1; return;; 121 2) LATER=0; return;; 122 *) error "process_date: unexpected return value from ${HAS_CHANGES}";; 123 esac 124 fi 125 126 ${REG_BUILD} "${TEST_DATE}" || error "build failed for ${TEST_DATE}" 127 ${REG_TEST} "${TEST_DATE}" 128 LATER=$? 129} 130 131# Perform a binary search on dates within the range specified by 132# the arguments, bounded by the number of seconds in DELTA. 133 134search_dates() { 135 let LOW=$1 136 let HIGH=$2 137 let DIFF=HIGH-LOW 138 139 # Get the date in the middle of the range; MID is in seconds since 140 # the epoch, DATE is readable by humans and tools. The user can 141 # override the initial mid date if it is known to have problems, 142 # e.g., if a build fails for that date. 143 144 if [ ${FIRST_MID} -ne 0 ]; then 145 let MID=${FIRST_MID} 146 else 147 let MID=LOW/2+HIGH/2 148 fi 149 150 while [ ${DIFF} -ge ${DELTA} ]; do 151 make_date ${MID} 152 TEST_DATE="${MADE_DATE}" 153 154 # Test it. 155 156 process_date "${TEST_DATE}" 157 158 # Narrow the search based on the outcome of testing DATE. 159 160 if [ ${LATER} -eq 1 ]; then 161 msg 1 "search dates later than \"${TEST_DATE}\"" 162 LATER_THAN="${TEST_DATE}" 163 let LOW=MID 164 else 165 msg 1 "search dates earlier than \"${TEST_DATE}\"" 166 EARLIER_THAN="${TEST_DATE}" 167 let HIGH=MID 168 fi 169 170 let DIFF=HIGH-LOW 171 let MID=LOW/2+HIGH/2 172 done 173} 174 175######################################################################## 176# Main program (so to speak) 177######################################################################## 178 179# If DATE isn't defined, use the default date command; the configuration 180# file can override this. 181 182if [ "x${DATE}" = "x" ]; then 183 DATE=date 184fi 185 186# The error function uses this. 187 188VALID_RANGE=0 189 190# Process the configuration file. 191 192if [ $# != 1 ]; then 193 echo Usage: $0 config_file 194 exit 1 195fi 196 197CONFIG=${1} 198if [ ! -f ${CONFIG} ]; then 199 error "configuration file ${CONFIG} does not exist" 200fi 201 202# OK, the config file exists. Source it, make sure required parameters 203# are defined and their files exist, and give default values to optional 204# parameters. 205 206. ${CONFIG} 207 208test "x${REG_UPDATE}" = "x" && error "REG_UPDATE is not defined" 209test "x${REG_BUILD}" = "x" && error "REG_BUILD is not defined" 210test "x${REG_TEST}" = "x" && error "REG_TEST is not defined" 211test -x ${REG_TEST} || error "REG_TEST is not an executable file" 212test "x${SKIP_LOW}" = "x" && SKIP_LOW=0 213test "x${SKIP_HIGH}" = "x" && SKIP_HIGH=0 214test "x${DELTA}" = "x" && DELTA=3600 215test "x${VERBOSITY}" = "x" && VERBOSITY=0 216test "x${HAS_CHANGES}" = "x" && HAS_CHANGES=true 217test "x${REG_FINISH}" = "x" && REG_FINISH=true 218 219msg 2 "LOW_DATE = ${LOW_DATE}" 220msg 2 "HIGH_DATE = ${HIGH_DATE}" 221msg 2 "REG_UPDATE = ${REG_UPDATE}" 222msg 2 "REG_BUILD = ${REG_BUILD}" 223msg 2 "REG_TEST = ${REG_TEST}" 224msg 2 "SKIP_LOW = ${SKIP_LOW}" 225msg 2 "SKIP_HIGH = ${SKIP_HIGH}" 226msg 2 "FIRST_MID = ${FIRST_MID}" 227msg 2 "VERBOSITY = ${VERBOSITY}" 228msg 2 "DELTA = ${DELTA}" 229 230# Verify that DELTA is at least two minutes. 231 232test ${DELTA} -lt 120 && \ 233 error "DELTA is ${DELTA}, must be at least 120 (two minutes)" 234 235# Change the dates into seconds since the epoch. This uses an extension 236# in GNU date. 237 238LOW_DATE=`${DATE} +%s --date "${LOW_DATE}"` || \ 239 error "date command failed for \"${LOW_DATE}\"" 240HIGH_DATE=`${DATE} +%s --date "${HIGH_DATE}"` || \ 241 error "date command failed for \"${LOW_DATE}\"" 242 243# If FIRST_MID was defined, convert it and make sure it's in the range. 244 245if [ "x${FIRST_MID}" != "x" ]; then 246 FIRST_MID=`${DATE} +%s --date "${FIRST_MID}"` || \ 247 error "date command failed for \"${FIRST_MID}\"" 248 test ${FIRST_MID} -le ${LOW_DATE} && \ 249 error "FIRST_MID date is earlier than LOW_DATE" 250 test ${FIRST_MID} -ge ${HIGH_DATE} && \ 251 error "FIRST_MID is later than HIGH_DATE" 252else 253 FIRST_MID=0 254fi 255 256# Keep track of the bounds of the range where the test behavior changes, 257# using a human-readable version of each date. 258 259make_date ${LOW_DATE} 260LATER_THAN="${MADE_DATE}" 261make_date ${HIGH_DATE} 262EARLIER_THAN="${MADE_DATE}" 263 264msg 2 "LATER_THAN = ${LATER_THAN}" 265msg 2 "EARLIER_THAN = ${EARLIER_THAN}" 266 267# Verify that the range isn't backwards. 268 269test ${LOW_DATE} -lt ${HIGH_DATE} || error "date range is backwards" 270 271# Verify that the first and last date in the range get the results we 272# expect. If not, quit, because any of several things could be wrong. 273 274if [ ${SKIP_LOW} -eq 0 ]; then 275 process_date "${LATER_THAN}" 276 test ${LATER} -ne 1 && \ 277 error "unexpected result for low date ${LATER_THAN}" 278 msg 1 "result for low date is as expected" 279fi 280 281if [ ${SKIP_HIGH} -eq 0 ]; then 282 process_date "${EARLIER_THAN}" 283 test ${LATER} -ne 0 && \ 284 error "unexpected result for high date ${EARLIER_THAN}" 285 msg 1 "result for high date is as expected" 286fi 287 288# Search within the range, now that we know that the end points are valid. 289 290VALID_RANGE=1 291search_dates ${LOW_DATE} ${HIGH_DATE} 292 293# Report the range that's left to investigate. 294 295echo "Continue search between ${LATER_THAN} and ${EARLIER_THAN}" 296 297# Invoke the optional script to report additional information about 298# changes between the two dates. 299 300${REG_FINISH} "${LATER_THAN}" "${EARLIER_THAN}" 301