Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Paul E. McKenney]

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