A friend told me of a non-deterministic bug that he had found that only crashed occasionally.  He wrote a test case, ran it once, and the bug appeared after 3.5 hours of testing.  He sent the bug report and test case to code owners, who ran it for 4 hours but couldn’t reproduce the bug.  Intuitively we can see that they might have just been unlucky and thus not seen the crash.

So it got me wondering what the minimum amount of time that they need to run the test for, all other factors being equal, to be 95%  likely to reproduce the bug again. (i.e. 2 sigma)

Assuming that the bug appears randomly, with an equal probability of per hour, then after 3.5 hours of running, there’s a probability of the bug appearing of:

Rearranging:

To have the tester reproduce the results in the end with a 95% chance, we need to 90% confidence in the probability of us producing the bug in the first place, and a 90% confidence of the reproducer reproducing the bug, so that combined we get a confidence in overall result.  So the percentage chance, , of the observed outcome of seeing the crash after 3.5 hours is between 10% to 90%.  Setting p to 0.1 and 0.9 in the above equation, we get that the probability of the bug appearing per hour is between 2.8%  to 20%.

Taking the lowest probability, to get a total of 95% chance of reproducing the bug (and thus 90% chance of reproducing the bug GIVEN the probability of the bug appearing for us being 90%) we need to run for:

23 hours.

So to be 95% confident that the bug does not appear on the reproducer’s system, they would need to run the test case for 23 hours, assuming similar hardware etc.

This can be drastically brought down if the initial tester does a second run, to increase the value for .

Rerunning the test

The original tester reran the test himself and reproduced the bug 4 times and found that it always appeared in less than 6 hours.

To be 95% confidence in the overall results, and thus 90% confidence for just ,  we want the probability of the occurring 4 times in 4 runs in less than 6 hours to be 10%.  Thus the probability of it occurring in 1 run in less than 6 hours is simply:

So setting p = 34%  and using the equation above but with the number of hours set to 6, we get:

Which gives x = 5.0%. This means that with 90% confidence, the bug appears with a minimum probability of 5% per hour.  So the amount of time, y, that the reproducer needs to run to be 95% likely to reproduce the bug is:

13 hours

I wanted to do a physics-based layout in QML, to have bouncing bubbles etc.

D3.js  has everything that I needed, but it needed to be tweaked to get it to run:

• Create some dummy functions to stub the webbrowser javascript functions clearTimeout() and setTimeout()  that we don’t have
• Create a QML Timer to replace them and manually call force.tick()
• Use dummy objects for D3 to manipulate, and then set the position of our real graphics to the determined position of the dummy objects.  This is needed because D3 takes x,y coordinates to be the center of the object, whereas qml uses x,y to mean the top left.

It worked pretty well, and now I can do things like this in QML:

diff --git a/d3.js b/d3.js
index 8868e42..7aac164 100644
--- a/d3.js
+++ b/d3.js
@@ -1,4 +1,9 @@
-!function() {
-  var d3 = {
+function clearTimeout() {
+};
+function setTimeout() {
+};
+var d3;
+!function(){
+  d3 = {
     version: "3.5.5"
   };
@@ -9503,2 +9508,1 @@
-  this.d3 = d3;
-}();
\ No newline at end of file
+}();

(The ds.min.js file is also patched in the same way)

And in QML:

import QtQuick 2.2
import "."
import QtSensors 5.0
import "d3.js" as D3

Rectangle {
    id: bubbleContainer
    width: 1000
    height: 1000
    //clip: true

    property int numbubbles: 200;
    property real bubbleScaleFactor: 0.1
    property real maxBubbleRadius: width*0.15*bubbleScaleFactor + width/20*bubbleScaleFactor
    property variant bubblesprites: []

    function createBubbles() {
        var bubblecomponent = Qt.createComponent("bubble.qml");
        var radius = Math.random()*width*0.15*bubbleScaleFactor + width/20*bubbleScaleFactor
        bubblesprites.push(bubblecomponent.createObject(bubbleContainer, {"x": width/2-radius , "y": height/2 - radius, "radius":radius, "color":  "#ec7e78" } ));
        var xLeft = -radius
        var xRight = radius
        for (var i=1; i < numbubbles; ++i) {             var radius2 = Math.random()*width*0.15*bubbleScaleFactor + width/20*bubbleScaleFactor             var y = height*(0.5 + (Math.random()-0.5))-radius2             if (i % 2 === 0) {                 bubblesprites.push(bubblecomponent.createObject(bubbleContainer, {"x": xLeft, "y": y, "radius":radius2 } ));                 xLeft += radius2*2             } else {                 xRight -= radius2*2                 bubblesprites.push(bubblecomponent.createObject(bubbleContainer, {"x": xRight, "y": y, "radius":radius2 } ));             }         }     }     function boundParticle(b) {         if (b.y > height - b.radius)
            b.y = height - b.radius
        if (b.y < b.radius)             b.y = b.radius         if (b.x > width*2.5)
            b.x = width*2.5
        if (b.x < -width*2)
            b.x = -width*2
    }

    property real padding: width/100*bubbleScaleFactor;
    function collide(node) {
        var r = node.radius + maxBubbleRadius+10,
              nx1 = node.x - r,
              nx2 = node.x + r,
              ny1 = node.y - r,
              ny2 = node.y + r;
        boundParticle(node)
        return function(quad, x1, y1, x2, y2) {
            if (quad.point && (quad.point !== node)) {
              var x = node.x - quad.point.x,
                  y = node.y - quad.point.y,
                  l = Math.sqrt(x * x + y * y),
                  r = node.radius + quad.point.radius + padding;
              if (l < r) {                 l = (l - r) / l * .5;                 node.x -= x *= l;                 node.y -= y *= l;                 quad.point.x += x;                 quad.point.y += y;               }             }             return x1 > nx2 || x2 < nx1 || y1 > ny2 || y2 < ny1;
        };
    }

    property var nodes;
    property var force;

    Component.onCompleted: {
        initializeTimer.start()
    }

    Timer {
        id: initializeTimer
        interval: 20;
        running: false;
        repeat: false;
        onTriggered: {
            createBubbles();
            nodes = D3.d3.range(numbubbles).map(function() { return {radius: bubblesprites[this.index]}; });
            for(var i = 0; i < numbubbles; ++i) {
                nodes[i].radius = bubblesprites[i].radius;
                nodes[i].px = nodes[i].x = bubblesprites[i].x+bubblesprites[i].radius
                nodes[i].py = nodes[i].y = bubblesprites[i].y+bubblesprites[i].radius
            }
            nodes[0].fixed = true;

            force = D3.d3.layout.force().gravity(0.05).charge(function(d, i) { return 0; }).nodes(nodes).size([width,height])
            force.start()
            nodes[0].px = width/2
            nodes[0].py = height/2
            force.on("tick", function(e) {
                var q = D3.d3.geom.quadtree(nodes),i = 0,
                        n = nodes.length;
                while (++i < n) q.visit(collide(nodes[i]));
                for(var i = 0; i < numbubbles; ++i) {
                    bubblesprites[i].x = nodes[i].x - nodes[i].radius;
                    bubblesprites[i].y = nodes[i].y - nodes[i].radius;
                }
            });
            timer.start();
        }
    }

    Timer {
        id: timer
        interval: 26;
        running: false;
        repeat: true;
        onTriggered: {
            force.resume();
            force.tick();
        }
    }
}

And bubble.qml is trivial:

import QtQuick 2.0
Rectangle {
    color: "#f3bab3"
    radius: 5
    width: radius*2
    height: width
}

The full code is here

I had a play with the kenel framebuffer, and managed to lock up my machine:

[  701.790000] c3 [] (mutex_lock+0xc/0x24) from [] (lock_fb_info+0x14/0x38)
[  701.790000] c3 [] (lock_fb_info+0x14/0x38) from [] (fbcon_blank+0x234/0x260)
[  701.790000] c3 [] (fbcon_blank+0x234/0x260) from [] (do_blank_screen+0x1d0/0x27c)
[  701.790000] c3 [] (do_blank_screen+0x1d0/0x27c) from [] (console_callback+0x8c/0x140)
[  701.790000] c3 [] (console_callback+0x8c/0x140) from [] (process_one_work+0x12c/0x3d0)
[  701.790000] c3 [] (process_one_work+0x12c/0x3d0) from [] (worker_thread+0x190/0x3dc)
[  701.790000] c3 [] (worker_thread+0x190/0x3dc) from [] (kthread+0x90/0x94)
[  701.790000] c3 [] (kthread+0x90/0x94) from [] (kernel_thread_exit+0x0/0x8)

In another thread:
[  701.790000] c3 SurfaceFlinger  D 02517c7c     0   258      1 0x00000001
[  701.790000] c3 [] (__schedule+0x214/0x6f8) from [] (schedule_timeout+0x180/0x1d0)
[  701.790000] c3 [] (schedule_timeout+0x180/0x1d0) from [] (__down+0x78/0xac)
[  701.790000] c3 [] (__down+0x78/0xac) from [] (down+0x44/0x4c)
[  701.790000] c3 [] (down+0x44/0x4c) from [] (console_lock+0x2c/0x60)
[  701.790000] c3 [] (console_lock+0x2c/0x60) from [] (do_fb_ioctl+0x394/0x450)
[  701.790000] c3 [] (do_fb_ioctl+0x394/0x450) from [] (do_vfs_ioctl+0x84/0x4ec)
[  701.790000] c3 [] (do_vfs_ioctl+0x84/0x4ec) from [] (sys_ioctl+0x38/0x60)

Subject: [PATCH] Fix deadlock between fb_info and console.  Do not lock
 fb_info when calling sending the FB_EVENT_CONBLANK

In fbmem.c, the semantics are that we acquire the lock_fb_info first,
and then console_lock.  However when fbcon.c fbcon_generic_blank() is
called, the console lock could already be held.  Locking fb_info can
thus cause a deadlock.

fbmem.c sends the FB_EVENT_BLANK without locking lock_fb_info first, so
this change introduces similar behaviour.
---
 drivers/video/console/fbcon.c | 4 ----
 1 file changed, 4 deletions(-)

diff --git a/drivers/video/console/fbcon.c b/drivers/video/console/fbcon.c
index 6b4fb5c..8546441 100644
--- a/drivers/video/console/fbcon.c
+++ b/drivers/video/console/fbcon.c
@@ -2333,13 +2333,9 @@ static void fbcon_generic_blank(struct vc_data *vc, struct fb_info *info,
         vc->vc_video_erase_char = oldc;
     }
 
-
-    if (!lock_fb_info(info))
-        return;
     event.info = info;
     event.data = ␣
     fb_notifier_call_chain(FB_EVENT_CONBLANK, &event);
-    unlock_fb_info(info);
 }
 
 static int fbcon_blank(struct vc_data *vc, int blank, int mode_switch)
-- 
1.8.1.2

I passed the patch onto the framebuffer developers, but they weren't very interested because this whole code should be going away at sometime.