lkml.org 
[lkml]   [2014]   [Jun]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectBisecting the heisenbugs (was Re: 3.15-rc: regression in suspend)
    On Mon 2014-06-09 13:03:31, Jiri Kosina wrote:
    > On Mon, 9 Jun 2014, Pavel Machek wrote:
    >
    > > > > Strange. It seems 3.15 with the patch reverted only boots in 30% or so
    > > > > cases... And I've seen resume failure, too, so maybe I was just lucky
    > > > > that it worked for a while.
    > > >
    > > > git bisect really likes 25f397a429dfa43f22c278d0119a60 - you're about
    > > > the 5th report or so that claims this is the culprit but it's
    > > > something else. The above code is definitely not used in i915 so bogus
    > > > bisect result.
    > >
    > > Note I did not do the bisect, I only attempted revert and test.
    > >
    > > And did three boots of successful s2ram.. only to find out that it
    > > does not really fix s2ram, I was just lucky :-(.
    > >
    > > Unfortunately, this means my s2ram problem will be tricky/impossible
    > > to bisect :-(.
    >
    > Welcome to the situation I have been in for past several months.

    I attempted to do some analysis. It should be possible to bisect when
    tests are not reliable, but it will take time and it will be almost
    neccessary to have the bisection automated.

    How long does the testing take for you to get to 50% test reliability?

    It seems to be one minute here.

    Trivial strategy is to repeat each test to get to 99% test
    reliability. That should make the test about 2x longer.

    There are other strategies possible -- like selecting bisect points
    closer to the "bad" end, and tricky "lets compute probabilities for
    each point", that work well for some parameter settings. There is
    probably even better strategy possible... if you have an idea, you can
    try it below.

    Monte carlo simulation is attached.

    Bisector on reliable bug
    -----
    1024 versions bug with probability of 0 false success, monte carlo
    of 30000 tries
    Assume compilation takes 6 minutes and test takes 1 minutes
    Average cost 71.0522 minutes
    Average tests 9.99793333333
    Bisector
    -----
    1024 versions bug with probability of 0.5 false success, monte carlo
    of 30000 tries
    Assume compilation takes 6 minutes and test takes 1 minutes
    Average cost 143.393933333 minutes
    Average tests 44.5374666667
    Trisector
    -----
    1024 versions bug with probability of 0.5 false success, monte carlo
    of 30000 tries
    Assume compilation takes 6 minutes and test takes 1 minutes
    Average cost 160.554 minutes
    Average tests 39.9552666667
    Strange
    -----
    1024 versions bug with probability of 0.5 false success, monte carlo
    of 3000 tries
    Assume compilation takes 6 minutes and test takes 1 minutes
    Average cost 246.658 minutes
    Average tests 38.412
    pavel@amd:~/WWW$


    Pavel
    --
    (english) http://www.livejournal.com/~pavelmachek
    (cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
    #!/usr/bin/python

    import random
    import numpy

    class Devil:
    def init(m):
    m.versions = 1024
    # Costs in minutes
    m.cost_compile = 6
    m.cost_test = 1
    # Penalty for wrongly identifying a commit.
    m.cost_failure = 1000
    # 0. == nicely behaved bug which always triggers
    m.p_false_success = .5
    m.verbose = 2

    def init_run(m):
    m.broken = random.randint(0, m.versions-1)
    m.tests = 0
    m.last_ver = -1
    m.cost = 0

    def test_failed(m, ver):
    m.tests += 1
    if ver != m.last_ver:
    m.cost += m.cost_compile
    m.cost += m.cost_test
    m.last_ver = ver
    if m.verbose > 1:
    print " testing version ", ver, "(tests %d, cost %d)" % (m.tests, m.cost),
    if ver >= m.broken:
    if m.verbose > 1:
    print "(bad)",
    if random.random() > m.p_false_success:
    if m.verbose > 1:
    print "FAIL"
    return 1
    if m.verbose > 1:
    print "pass"
    return 0

    def evaluate(m):
    ver = m.run()
    if ver == m.broken:
    if m.verbose:
    print "success"
    else:
    if m.verbose:
    print "FAILURE"
    m.cost += m.cost_failure

    class Bisector(Devil):
    def init_run(m):
    Devil.init_run(m)
    m.good = 0
    m.bad = m.versions-1

    def run(m):
    while m.good+1 < m.bad:
    ver = (m.good + m.bad) / 2
    p_bad = 1
    failed = 0
    while p_bad > .01:
    if m.test_failed(ver):
    m.bad = ver
    failed = 1
    break
    p_bad *= m.p_false_success
    if not failed:
    m.good = ver
    return m.bad

    class Trisector(Devil):
    def init_run(m):
    Devil.init_run(m)
    m.good = 0
    m.bad = m.versions-1

    def run(m):
    while m.good+1 < m.bad:
    ver = (m.good*6 + m.bad*14) / 20
    p_bad = 1
    failed = 0
    while p_bad > .01:
    if m.test_failed(ver):
    m.bad = ver
    failed = 1
    break
    p_bad *= m.p_false_success
    if not failed:
    m.good = ver
    return m.bad


    class Strange(Devil):
    def init_run(m):
    Devil.init_run(m)
    m.good = 0
    m.bad = m.versions-1
    m.prob_bad = numpy.zeros([m.versions], float)
    m.prob_bad[:m.versions] = .9

    def ask_for(m, ver):
    if m.test_failed(ver):
    m.bad = ver
    m.prob_bad[:ver+1] /= m.prob_bad[ver]
    m.prob_bad[ver:] = 1
    return

    m.prob_bad[:ver+1] *= m.p_false_success
    m.good = ver

    def last_good(m, prob):
    g = 0
    for i in range(m.bad):
    if m.prob_bad[i] <= prob:
    g = i
    return g

    def run(m):

    while m.last_good(.01)+1 < m.bad:
    if m.verbose > 1:
    print m.prob_bad
    m.good = m.last_good(.5)
    ver = (m.good*10 + m.bad*10) / 20
    m.ask_for(ver)
    m.good = m.last_good(.1)
    ver = (m.good*10 + m.bad*10) / 20
    m.ask_for(ver)


    return m.bad

    def monte_carlo(bis, tries = 30000):
    total_cost = 0.
    total_tests = 0.
    for i in range(tries):
    bis.init_run()
    if tries > 500:
    bis.verbose = 0
    bis.evaluate()
    total_cost += bis.cost
    total_tests += bis.tests

    print "-----"
    print bis.versions, "versions bug with probability of ", bis.p_false_success, " false success, monte carlo of ", tries, " tries"
    print "Assume compilation takes ", bis.cost_compile, "minutes and test takes", bis.cost_test, "minutes"
    print "Average cost ", total_cost / tries, "minutes"
    print "Average tests ", total_tests / tries

    print "Bisector on reliable bug"
    bis = Bisector()
    bis.init()
    bis.p_false_success = 0
    monte_carlo(bis)

    print "Bisector"
    bis = Bisector()
    bis.init()
    monte_carlo(bis)

    print "Trisector"
    bis = Trisector()
    bis.init()
    monte_carlo(bis)

    print "Strange"
    bis = Strange()
    bis.init()
    monte_carlo(bis, 3000)




    \
     
     \ /
      Last update: 2014-06-10 14:21    [W:2.647 / U:0.076 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site