Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

On Wed, Jul 08, 2009 at 03:14:13PM -0700, Paul E. McKenney wrote:
On Thu, Jul 09, 2009 at 07:42:27AM +1000, tridge@xxxxxxxxx wrote:
Hi Paul,

These probabilities are way off. They assume that whatever interaction
happens in XP has infinite memory. The testing I've done indicates
that the memory for this interaction is very small (maybe 3 or 4? it's
hard to know precisely).

Good to know! I will rework assuming that the memory is 4, let me
know if you learn more.

I've also confirmed this with lots of testing. If the probability was
39% for any directory size then I would have found it.

This new information will likely reduce the predicted probability of
bluescreen by several orders of magnitude for large directories. Not
that much effect for small directories, but not a real issue given
how low the probabilities are to begin with.

In all my testing I did not once produce a XP crash with the full
patch. To produce the XP crash I needed to have a reduced version of
the patch with less randomness.

Well, let's see if I can produce a reasonably realistic model. :-)
(I knew I should have gotten more sleep last night!!!)

This model assumes a finite memory, so that at least two files out of
a group of "l" recently opened files have to collide to result in a
bluescreen. I don't trust it yet, but thought I should give people a
chance to poke holes in it.

Thanx, Paul

------------------------------------------------------------------------

Results

Assuming the worst case where the user opens each file in the directory
of interest, the probability depends on the number of long-named files
in the given directory as follows (derivation at EOM):

Files Probability Odds
----- -------------------- -------
32767 9.15401625433259b-5 (1 in 11,000)
16384 4.576973184985319b-5 (1 in 22,000)
8192 2.288233388567135b-5 (1 in 44,000)
4096 1.143843845796893b-5 (1 in 87,000)
2048 5.716441632059139b-6 (1 in 170,000)
1024 2.855430941007629b-6 (1 in 350,000)
512 1.424922525947476b-6 (1 in 700,000)
256 7.096675510325187b-7 (1 in 1,400,000)
128 3.520398717286601b-7 (1 in 2,800,000)
64 1.732259841151157b-7 (1 in 5,800,000)
32 8.381902831793723b-8 (1 in 12,000,000)
16 3.911554742174612b-8 (1 in 26,000,000)
8 1.676380622425006b-8 (1 in 60,000,000)
4 5.587935438151892b-9 (1 in 179,000,000)
2 9.313225746154785b-10 (1 in 1,000,000,000)
1 0.0b0

This is for 2^32 random values per entry and a WinXP "memory" of four
entries.

------------------------------------------------------------------------

Derivation:

o The patch uses 6 random bytes, with 6 bits each, for
32^6 = 1,073,741,824 possible combinations. (Based on code
in vfat_build_dummy_83_buffer() in the patch Tridge posted on
June 27th.)

o There are a maximum of 32,767 entries in a VFAT directory.

o In the worst case, the user application will open each and
every file in the directory. WinXP seems to have a limited
memory for recently opened files, and we assume that once this
memory is full, opening a new file causes one of the recently
opened files to be forgotten. The size of its memory appears
to be in the range of 3-4 based on Tridge's testing, so we
will assume the worst case (4) and parameterize with l=4.

o As noted earlier, the probability the infamous Birthday Paradox
is given by:

P(n, m) = (n-1)! / ((n-m)! * n^(m-1))

Here "n" is the number of possible birthdays (1,073,741,824 in
this case) and "m" is the number of people (32,767 in this case).
P(n, m) is the probability of -no- common birthday. This is not
the probability of no bluescreen, but we will use this result
to calculate this probability while initially filling WinXP's
memory. I again use maxima, and again use the optimized form
based on the binomial function:

b(n,m):=binomial(n,m)*m!/n^m;

o See the attached .eps...

o The probability of no bluescreen while opening the first "l"
files is given by b(n,l), just as before.

o Given no bluescreen while opening the first "l" files, the
probability of no bluescreen while opening the "l+1"st file
is the probability of missing the "l-1" files that remain
after ejecting one of them to make room is "(n-l+1)/n".

The cumulative probability of no bluescreen is thus:

P(n,m,l) = b(n,l)*(n-l+1)/n

o We have the same situation when opening the "l+2"nd file,
the probability of no bluescreen is again "(n-l+1)/n".

o This situation will repeat "m-l" times, so that we have:

P(n,m,l) = b(n,l)*((n-l+1)/n)^(m-l)

In maxima-speak:

b(n,m):=binomial(n,m)*m!/n^m;
nbs(n,m,l):=b(n,l)*((n-l+1)/n)^(m-l);

The probability of bluescreening when faced with 32767 files
in a directory, 32^6 possible random values, and the capacity
to remember four files is then:

1-nbs(32^6,32767,4);

For floating-point results instead of a massive fraction:

bfloat(1-nbs(32^6,32767,4));

See below for the actual maxima output, typos and all.

------------------------------------------------------------------------

maxima

paulmck@paulmck-laptop:~$ maxima

Maxima 5.12.0 http://maxima.sourceforge.net
Using Lisp GNU Common Lisp (GCL) GCL 2.6.7 (aka GCL)
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
This is a development version of Maxima. The function bug_report()
provides bug reporting information.
(%i1) b(n,m):=binomial(n,m)*m!/n^m;
binomial(n, m) m!
(%o1) b(n, m) := -----------------
m
n
(%i2) nbs(n,m,l):=b(n,l)*((n-l+1)/n)^(m-l);
n - l + 1 m - l
(%o2) nbs(n, m, l) := b(n, l) (---------)
n
(%i3) bfloat(1-nbs(32^6,32767,4));
(%o3) 9.15401625433259b-5
(%i4) bfloat(1-nbs(32^6,2^14,4));
(%o4) 4.576973184985319b-5
(%i5) bfloat(1-nbs(32^6,2^13,4));
(%o5) 2.288233388567135b-5
(%i6) bfloat(1-nbs(32^6,2^12,4));
(%o6) 1.143843845796893b-5
(%i7) bfloat(1-nbs(32^6,2^11,4));
(%o7) 5.716441632059139b-6
(%i8) bfloat(1-nbs(32^6,2^10,4));
(%o8) 2.855430941007629b-6
(%i9) bfloat(1-nbs(32^6,2^9,4));
(%o9) 1.424922525947476b-6
(%i10) bfloat(1-nbs(32^6,2^8,4));
(%o10) 7.096675510325187b-7
(%i11) bfloat(1-nbs(32^6,2^7,4));
(%o11) 3.520398717286601b-7
(%i12) bfloat(1-nbs(32^6,2^6,4));
(%o12) 1.732259841151157b-7
(%i13) bfloat(1-nbs(32^6,2^5,4));
(%o13) 8.381902831793723b-8
(%i14) bfloat(1-nbs(32^6,2^4,4));
(%o14) 3.911554742174612b-8
(%i15) bfloat(1-nbs(32^6,2^3,4));
(%o15) 1.676380622425006b-8
(%i16) bfloat(1-nbs(32^6,2^2,4));
(%o16) 5.587935438151892b-9
(%i17) bfloat(1-nbs(32^6,2^1,4));
(%o17) - 1.734723480823569b-18
(%i18) bfloat(1-b(32^6,2));
(%o18) 9.313225746154785b-10
(%i19) bfloat(1-b(32^6,1));
(%o19) 0.0b0

Attachment: WinXPmodel.eps
Description: WinXPmodel.eps

Relevant Pages

  • Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option
    ... so what is your estimate of XP crash probability? ... memory sticks, there will eventually be a WinXP bluescreen. ... has a highly optimized maxima implementation. ...
    (Linux-Kernel)
  • Re: ESRs fortune.pl redone in python - request for critique
    ... > This has no effect because once the program exits, the file pointer ... > the memory requirements of reading the contents of all of those files ... > > with a generator function that collects lines until it ... The probability for the if branches to be executed is thus ...
    (comp.lang.python)
  • Causation/Causality, Memory, and Convolution 4: Memory vs Complexity
    ... being able to reach anywhere back into memory from ... by the fact that conditional probability isn't as intuitive as Probable ... Memory in Markov chains is the minimal ... could theoretically devise a conditional probability analog of PI ...
    (sci.physics)
  • Re: OutOfMemory is intermittent, maybe heres why
    ... The probability of an error has some correlation with the size of the image but is not reliable. ... It's possible memory is getting fragmented and while there is a lot of free memory there isn't a free contiguous block of memory. ... Does the .Net Framework fragment its virtual memory differently under Vista than it does under XP? ... I still think it looks like the stack is getting smashed because the collector does move something when the rest of the runtime isn't ready for it to be moved. ...
    (microsoft.public.dotnet.framework.drawing)
  • Quantum Gravity 294.6: Probable Causation/Influence --> Memory --> Life (Czech Repub
    ... Now along comes a series of papers from the Czech Republic's Raji ... Golden ratio, and their linear dependence on bond energy," arXiv: ... Probable Causation/Influence, to remind Readers, involves Memory, ... and Conditional Probability respectively reduce to: ...
    (sci.physics)