[PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

This is a new patch for VFAT long filename support, replacing the one
that I posted last month. It retains a lot more functionality then the
previous patch.

A FAQ will be posted immediately after this patch to answer the
questions that were raised from the previous discussion.

Cheers, Tridge


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

When VFAT_FS_DUALNAMES is disabled we avoid the creation of 8.3 short
filenames for files on VFAT filesystems that require a long name. The
patch uses a pattern of 11 bytes in the directory entry which contains
invalid characters such that it cannot be considered to be a valid short
filename.

Signed-off-by: Andrew Tridgell <tridge@samba.org>
Acked-by: Dave Kleikamp <shaggy@linux.vnet.ibm.com>
Acked-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---
 fs/fat/Kconfig      |   20 +++++++++++++++++
 fs/fat/dir.c        |   15 ++++++-------
 fs/fat/namei_vfat.c |   59 +++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 86 insertions(+), 8 deletions(-)

diff --git a/fs/fat/Kconfig b/fs/fat/Kconfig
index 182f9ff..907a5de 100644
--- a/fs/fat/Kconfig
+++ b/fs/fat/Kconfig
@@ -74,6 +74,26 @@ config VFAT_FS
 	  To compile this as a module, choose M here: the module will be called
 	  vfat.
 
+config VFAT_FS_DUALNAMES
+	bool "VFAT dual names support"
+	depends on VFAT_FS
+	help
+	  This option provides support for dual filenames on VFAT filesystems.
+	  If this option is disabled then file creation will either put
+	  a short (8.3) name or a long name on the file, but never both.
+	  The field where a shortname would normally go is filled with
+	  invalid characters such that it cannot be considered a valid
+	  short filename.
+
+	  That means that long filenames created with this option
+	  disabled will not be accessible at all to operating systems
+	  that do not understand the VFAT extensions.
+
+	  Users considering enabling this option should consider the implications
+	  of any patents that may exist on dual filenames in VFAT.
+
+	  If unsure, say N
+
 config FAT_DEFAULT_CODEPAGE
 	int "Default codepage for FAT"
 	depends on MSDOS_FS || VFAT_FS
diff --git a/fs/fat/dir.c b/fs/fat/dir.c
index 38ff75a..cd5d3ec 100644
--- a/fs/fat/dir.c
+++ b/fs/fat/dir.c
@@ -420,14 +420,13 @@ parse_record:
 			}
 			i += chl;
 		}
-		if (!last_u)
-			continue;
-
-		/* Compare shortname */
-		bufuname[last_u] = 0x0000;
-		len = fat_uni_to_x8(sbi, bufuname, bufname, sizeof(bufname));
-		if (fat_name_match(sbi, name, name_len, bufname, len))
-			goto found;
+		if (last_u) {
+			/* Compare shortname */
+			bufuname[last_u] = 0x0000;
+			len = fat_uni_to_x8(sbi, bufuname, bufname, sizeof(bufname));
+			if (fat_name_match(sbi, name, name_len, bufname, len))
+				goto found;
+		}
 
 		if (nr_slots) {
 			void *longname = unicode + FAT_MAX_UNI_CHARS;
diff --git a/fs/fat/namei_vfat.c b/fs/fat/namei_vfat.c
index 73471b7..894f44d 100644
--- a/fs/fat/namei_vfat.c
+++ b/fs/fat/namei_vfat.c
@@ -22,6 +22,7 @@
 #include <linux/smp_lock.h>
 #include <linux/buffer_head.h>
 #include <linux/namei.h>
+#include <linux/random.h>
 #include "fat.h"
 
 /*
@@ -586,6 +587,59 @@ xlate_to_uni(const unsigned char *name, int len, unsigned char *outname,
 	return 0;
 }
 
+#ifndef CONFIG_VFAT_FS_DUALNAMES
+/*
+ * build a 11 byte 8.3 buffer which is not a short filename. We want 11
+ * bytes which:
+ *    - will be seen as a constant string to all APIs on Linux and Windows
+ *    - cannot be matched with wildcard patterns
+ *    - cannot be used to access the file
+ *    - has a low probability of collision within a directory
+ *    - has an invalid 3 byte extension
+ *    - contains at least one non-space and non-nul byte
+ */
+static void vfat_build_dummy_83_buffer(struct inode *dir, char *msdos_name)
+{
+	u32 rand_num = random32() & 0x3FFFFFFF;
+	int i;
+
+	/* a value of zero would leave us with only nul and spaces,
+	 * which would not work with older linux systems
+	 */
+	if (rand_num == 0)
+		rand_num = 1;
+
+	/* we start with a space followed by nul as spaces at the
+	 * start of an entry are trimmed in FAT, which means that
+	 * starting the 11 bytes with 0x20 0x00 gives us a value which
+	 * cannot be used to access the file. It also means that the
+	 * value as seen from all Windows and Linux APIs is a constant
+	 */
+	msdos_name[0]  = ' ';
+	msdos_name[1]  = 0;
+
+	/* we use / and 2 nul bytes for the extension. These are
+	 * invalid in FAT and mean that utilities that show the
+	 * directory show no extension, but still work via the long
+	 * name for old Linux kernels
+	 */
+	msdos_name[8]  = '/';
+	msdos_name[9]  = 0;
+	msdos_name[10] = 0;
+
+	/*
+	 * fill the remaining 6 bytes with random invalid values
+	 * This gives us a low collision rate, which means a low
+	 * chance of problems with chkdsk.exe and WindowsXP
+	 */
+	for (i = 2; i < 8; i++) {
+		msdos_name[i] = rand_num & 0x1F;
+		rand_num >>= 5;
+	}
+}
+#endif
+
+
 static int vfat_build_slots(struct inode *dir, const unsigned char *name,
 			    int len, int is_dir, int cluster,
 			    struct timespec *ts,
@@ -628,6 +682,11 @@ static int vfat_build_slots(struct inode *dir, const unsigned char *name,
 		goto shortname;
 	}
 
+#ifndef CONFIG_VFAT_FS_DUALNAMES
+	vfat_build_dummy_83_buffer(dir, msdos_name);
+	lcase = 0;
+#endif
+
 	/* build the entry of long file name */
 	cksum = fat_checksum(msdos_name);
 
-- 
1.6.0.4

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[H. Peter Anvin]

tridge@samba.org wrote:
> This is a new patch for VFAT long filename support, replacing the one
> that I posted last month. It retains a lot more functionality then the
> previous patch.
> 
> A FAQ will be posted immediately after this patch to answer the
> questions that were raised from the previous discussion.
> 

>From a purely technical perspective, there is a major advantage to this
patch: it creates a "pure VFAT" filesystem, without a spurious filename
alias which still occupies namespace, hiddenly, and therefore could
cause an ill-defined amount of problems.  UMSDOS at least had the
decency to not expose its shortnames to a longname-aware OS.

However, as such it really should be paired with a "don't even recognize
the shortname if a longname exists" option.

It's also questionable IMO if this shouldn't be another FAT superdriver,
just as we have VFAT, MS-DOS etc. we could have "purevfat".

	-hpa

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

hpa wrote:
 > However, as such it really should be paired with a "don't even recognize
 > the shortname if a longname exists" option.

Right, we could just skip the 8.3 name matching and go straight to the
longname match in fat_search_long(). I wonder if anyone ever relies on
the 8.3 matching when a file has a long name on Linux?

 > It's also questionable IMO if this shouldn't be another FAT superdriver,
 > just as we have VFAT, MS-DOS etc. we could have "purevfat".

It would be only a few lines of code difference between the two
drivers - is it worth the maintainence overhead of splitting it up?

Maybe a mount option to ignore 8.3 names for files with long names
would be better? Perhaps even the default?

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[OGAWA Hirofumi]

tridge@samba.org writes:

> hpa wrote:
>  > However, as such it really should be paired with a "don't even recognize
>  > the shortname if a longname exists" option.
>
> Right, we could just skip the 8.3 name matching and go straight to the
> longname match in fat_search_long(). I wonder if anyone ever relies on
> the 8.3 matching when a file has a long name on Linux?

Wine or such is using it.

>  > It's also questionable IMO if this shouldn't be another FAT superdriver,
>  > just as we have VFAT, MS-DOS etc. we could have "purevfat".
>
> It would be only a few lines of code difference between the two
> drivers - is it worth the maintainence overhead of splitting it up?
>
> Maybe a mount option to ignore 8.3 names for files with long names
> would be better? Perhaps even the default?

It sounds like to be start of yet another UMSDOS with minimal one. I
wouldn't like to repeat UMSDOS history, i.e. I think it needs real users
and developers. If not, I wouldn't like to add.

Thanks.
-- 
OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[OGAWA Hirofumi]

tridge@samba.org writes:

> This is a new patch for VFAT long filename support, replacing the one
> that I posted last month. It retains a lot more functionality then the
> previous patch.
>
> A FAQ will be posted immediately after this patch to answer the
> questions that were raised from the previous discussion.

Looks good to me. It seems to be trying to be minimal change, and I
guess it would be worth a try for realworld problem.  Like FAQ is
saying, the default might be arguable though.

> When VFAT_FS_DUALNAMES is disabled we avoid the creation of 8.3 short
> filenames for files on VFAT filesystems that require a long name. The
> patch uses a pattern of 11 bytes in the directory entry which contains
> invalid characters such that it cannot be considered to be a valid short
> filename.
>
> Signed-off-by: Andrew Tridgell <tridge@samba.org>
> Acked-by: Dave Kleikamp <shaggy@linux.vnet.ibm.com>
> Acked-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> ---
>  fs/fat/Kconfig      |   20 +++++++++++++++++
>  fs/fat/dir.c        |   15 ++++++-------
>  fs/fat/namei_vfat.c |   59 +++++++++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 86 insertions(+), 8 deletions(-)
>
> diff --git a/fs/fat/Kconfig b/fs/fat/Kconfig
> index 182f9ff..907a5de 100644
> --- a/fs/fat/Kconfig
> +++ b/fs/fat/Kconfig
> @@ -74,6 +74,26 @@ config VFAT_FS
>  	  To compile this as a module, choose M here: the module will be called
>  	  vfat.
>  
> +config VFAT_FS_DUALNAMES
> +	bool "VFAT dual names support"
> +	depends on VFAT_FS
> +	help
> +	  This option provides support for dual filenames on VFAT filesystems.
> +	  If this option is disabled then file creation will either put
> +	  a short (8.3) name or a long name on the file, but never both.
> +	  The field where a shortname would normally go is filled with
> +	  invalid characters such that it cannot be considered a valid
> +	  short filename.
> +
> +	  That means that long filenames created with this option
> +	  disabled will not be accessible at all to operating systems
> +	  that do not understand the VFAT extensions.
> +
> +	  Users considering enabling this option should consider the implications
> +	  of any patents that may exist on dual filenames in VFAT.
> +
> +	  If unsure, say N
> +
>  config FAT_DEFAULT_CODEPAGE
>  	int "Default codepage for FAT"
>  	depends on MSDOS_FS || VFAT_FS
> diff --git a/fs/fat/dir.c b/fs/fat/dir.c
> index 38ff75a..cd5d3ec 100644
> --- a/fs/fat/dir.c
> +++ b/fs/fat/dir.c
> @@ -420,14 +420,13 @@ parse_record:
>  			}
>  			i += chl;
>  		}
> -		if (!last_u)
> -			continue;
> -
> -		/* Compare shortname */
> -		bufuname[last_u] = 0x0000;
> -		len = fat_uni_to_x8(sbi, bufuname, bufname, sizeof(bufname));
> -		if (fat_name_match(sbi, name, name_len, bufname, len))
> -			goto found;
> +		if (last_u) {
> +			/* Compare shortname */
> +			bufuname[last_u] = 0x0000;
> +			len = fat_uni_to_x8(sbi, bufuname, bufname, sizeof(bufname));
> +			if (fat_name_match(sbi, name, name_len, bufname, len))
> +				goto found;
> +		}
>  
>  		if (nr_slots) {
>  			void *longname = unicode + FAT_MAX_UNI_CHARS;
> diff --git a/fs/fat/namei_vfat.c b/fs/fat/namei_vfat.c
> index 73471b7..894f44d 100644
> --- a/fs/fat/namei_vfat.c
> +++ b/fs/fat/namei_vfat.c
> @@ -22,6 +22,7 @@
>  #include <linux/smp_lock.h>
>  #include <linux/buffer_head.h>
>  #include <linux/namei.h>
> +#include <linux/random.h>
>  #include "fat.h"
>  
>  /*
> @@ -586,6 +587,59 @@ xlate_to_uni(const unsigned char *name, int len, unsigned char *outname,
>  	return 0;
>  }
>  
> +#ifndef CONFIG_VFAT_FS_DUALNAMES
> +/*
> + * build a 11 byte 8.3 buffer which is not a short filename. We want 11
> + * bytes which:
> + *    - will be seen as a constant string to all APIs on Linux and Windows
> + *    - cannot be matched with wildcard patterns
> + *    - cannot be used to access the file
> + *    - has a low probability of collision within a directory
> + *    - has an invalid 3 byte extension
> + *    - contains at least one non-space and non-nul byte
> + */
> +static void vfat_build_dummy_83_buffer(struct inode *dir, char *msdos_name)
> +{
> +	u32 rand_num = random32() & 0x3FFFFFFF;
> +	int i;
> +
> +	/* a value of zero would leave us with only nul and spaces,
> +	 * which would not work with older linux systems
> +	 */
> +	if (rand_num == 0)
> +		rand_num = 1;
> +
> +	/* we start with a space followed by nul as spaces at the
> +	 * start of an entry are trimmed in FAT, which means that
> +	 * starting the 11 bytes with 0x20 0x00 gives us a value which
> +	 * cannot be used to access the file. It also means that the
> +	 * value as seen from all Windows and Linux APIs is a constant
> +	 */
> +	msdos_name[0]  = ' ';
> +	msdos_name[1]  = 0;
> +
> +	/* we use / and 2 nul bytes for the extension. These are
> +	 * invalid in FAT and mean that utilities that show the
> +	 * directory show no extension, but still work via the long
> +	 * name for old Linux kernels
> +	 */
> +	msdos_name[8]  = '/';
> +	msdos_name[9]  = 0;
> +	msdos_name[10] = 0;
> +
> +	/*
> +	 * fill the remaining 6 bytes with random invalid values
> +	 * This gives us a low collision rate, which means a low
> +	 * chance of problems with chkdsk.exe and WindowsXP
> +	 */
> +	for (i = 2; i < 8; i++) {
> +		msdos_name[i] = rand_num & 0x1F;
> +		rand_num >>= 5;
> +	}
> +}
> +#endif
> +
> +
>  static int vfat_build_slots(struct inode *dir, const unsigned char *name,
>  			    int len, int is_dir, int cluster,
>  			    struct timespec *ts,
> @@ -628,6 +682,11 @@ static int vfat_build_slots(struct inode *dir, const unsigned char *name,
>  		goto shortname;
>  	}
>  
> +#ifndef CONFIG_VFAT_FS_DUALNAMES
> +	vfat_build_dummy_83_buffer(dir, msdos_name);
> +	lcase = 0;
> +#endif
> +
>  	/* build the entry of long file name */
>  	cksum = fat_checksum(msdos_name);

-- 
OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Jan Engelhardt]

On Sat, 27 Jun 2009 05:19:33 +1000, tridge@samba.org wrote:
>
>When VFAT_FS_DUALNAMES is disabled we avoid the creation of 8.3
>short filenames for files on VFAT filesystems that require a long
>name. The patch uses a pattern of 11 bytes in the directory entry
>which contains invalid characters such that it cannot be considered
>to be a valid short filename.

Can't we make this a runtime option?

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Jan Engelhardt]

On Sat, 27 Jun 2009 10:48:25 +0900, OGAWA Hirofumi wrote:

>It sounds like to be start of yet another UMSDOS with minimal one. I 
>wouldn't like to repeat UMSDOS history, i.e. I think it needs real 
>users and developers. If not, I wouldn't like to add.

And in that regard, there is http://posixovl.sf.net/ for everybody who 
needs UMSDOS functionality.

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Eric W. Biederman]

tridge@samba.org writes:

> This is a new patch for VFAT long filename support, replacing the one
> that I posted last month. It retains a lot more functionality then the
> previous patch.
>
> A FAQ will be posted immediately after this patch to answer the
> questions that were raised from the previous discussion.
>
> Cheers, Tridge
>
>
> ------------
>
> When VFAT_FS_DUALNAMES is disabled we avoid the creation of 8.3 short
> filenames for files on VFAT filesystems that require a long name. The
> patch uses a pattern of 11 bytes in the directory entry which contains
> invalid characters such that it cannot be considered to be a valid short
> filename.
>
> Signed-off-by: Andrew Tridgell <tridge@samba.org>
> Acked-by: Dave Kleikamp <shaggy@linux.vnet.ibm.com>
> Acked-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> ---
>  fs/fat/Kconfig      |   20 +++++++++++++++++
>  fs/fat/dir.c        |   15 ++++++-------
>  fs/fat/namei_vfat.c |   59 +++++++++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 86 insertions(+), 8 deletions(-)
>
> diff --git a/fs/fat/Kconfig b/fs/fat/Kconfig
> index 182f9ff..907a5de 100644
> --- a/fs/fat/Kconfig
> +++ b/fs/fat/Kconfig
> @@ -74,6 +74,26 @@ config VFAT_FS
>  	  To compile this as a module, choose M here: the module will be called
>  	  vfat.
>  
> +config VFAT_FS_DUALNAMES
> +	bool "VFAT dual names support"
> +	depends on VFAT_FS
> +	help
> +	  This option provides support for dual filenames on VFAT filesystems.
> +	  If this option is disabled then file creation will either put
> +	  a short (8.3) name or a long name on the file, but never both.
> +	  The field where a shortname would normally go is filled with
> +	  invalid characters such that it cannot be considered a valid
> +	  short filename.
> +
> +	  That means that long filenames created with this option
> +	  disabled will not be accessible at all to operating systems
> +	  that do not understand the VFAT extensions.
> +
> +	  Users considering enabling this option should consider the implications
> +	  of any patents that may exist on dual filenames in VFAT.
> +
> +	  If unsure, say N
> +
>  config FAT_DEFAULT_CODEPAGE
>  	int "Default codepage for FAT"
>  	depends on MSDOS_FS || VFAT_FS
> diff --git a/fs/fat/dir.c b/fs/fat/dir.c
> index 38ff75a..cd5d3ec 100644
> --- a/fs/fat/dir.c
> +++ b/fs/fat/dir.c
> @@ -420,14 +420,13 @@ parse_record:
>  			}
>  			i += chl;
>  		}
> -		if (!last_u)
> -			continue;
> -
> -		/* Compare shortname */
> -		bufuname[last_u] = 0x0000;
> -		len = fat_uni_to_x8(sbi, bufuname, bufname, sizeof(bufname));
> -		if (fat_name_match(sbi, name, name_len, bufname, len))
> -			goto found;
> +		if (last_u) {
> +			/* Compare shortname */
> +			bufuname[last_u] = 0x0000;
> +			len = fat_uni_to_x8(sbi, bufuname, bufname, sizeof(bufname));
> +			if (fat_name_match(sbi, name, name_len, bufname, len))
> +				goto found;
> +		}
>  
>  		if (nr_slots) {
>  			void *longname = unicode + FAT_MAX_UNI_CHARS;

This hunk allowing the examination of the long name if there is not a
short name is something else entirely.

You don't describe it in your summary, and don't make the case that
this is the correct behavior.

This should probably be split out into a separate patch if it is the
right thing to do, or drop it if (as it looks) there is no point in
that change.

Eric

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Eric,

 > This hunk allowing the examination of the long name if there is not a
 > short name is something else entirely.
 > 
 > You don't describe it in your summary, and don't make the case that
 > this is the correct behavior.

Sorry for not explaining that part of the patch in my posting.

The reason I initially included it was that during the development of
this patch we were experimenting with variations of the
vfat_build_dummy_83_buffer() function which put a wide varity of
different values in the 11 bytes where a short filename would normally
go.

The most technically attractive varient was to put 11 spaces in
there. That has the advantage that Windows then returns the long name
to the GetShortPathName() API call, which is also what Windows does on
a NTFS filesystem when the NTFS filesystem is configured not to have
8.3 names. So it would have been very nice to have this same behaviour
on VFAT, instead of getting a single space back from
GetShortPathName() as we get with the patch I posted.

The reason we didn't go with the 11 spaces varient is that it causes
WindowsXP to bluescreen. This is just a bug in WinXP, and is not
present in Vista or Windows7.

The 2nd technical problem with 11 spaces is that current Linux kernels
would not see the long names, as the last_u logic in fat_search_long()
will skip files where the the 11 bytes don't have at least one
non-space byte before the first nul byte in either the 8 byte prefix
or the 3 byte extension.

The last_u logic is at odds with the behaviour of other operating
systems for VFAT. On all windows varients that I have tested (and on
MacOSX), the long name is still used no matter what values are in the
11 bytes. You can stick all nul bytes, all spaces, or anything else
you like in there and Windows will still allow you to operate on the
file by the long name and the filesystem will work perfectly.

So that part of the patch is bringing us inline with the behaviour of
other VFAT implementations.

More importantly, it gives us the opportunity in the future to move to
the techically better 11 spaces solution when either Microsoft fixes
their WindowsXP crash bug, or WindowsXP has such a low market share
that nobody cares any more (say like WfWg and maybe Win95 has now).

If we don't put in this change now then we won't be able to move to
the technically better solution later as we wouldn't have given Linux
distros a chance to include support for the 11 spaces in distros. By
putting that change in now, when (if?) we change to 11 spaces later we
will not be breaking recent Linux kernels.

 > This should probably be split out into a separate patch if it is the
 > right thing to do, or drop it if (as it looks) there is no point in
 > that change.

hopefully the above explanation makes it clear why the last_u change
should go together with the vfat_build_slots() change.

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Jan,

 > Can't we make this a runtime option?

John may be able to give you a more detailed answer, but the short
answer is that it is much safer legally to not have the code in the
binary kernel image at all.

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Eric W. Biederman]

tridge@samba.org writes:

> Hi Eric,
>
>  > This hunk allowing the examination of the long name if there is not a
>  > short name is something else entirely.
>  > 
>  > You don't describe it in your summary, and don't make the case that
>  > this is the correct behavior.
>
> Sorry for not explaining that part of the patch in my posting.
>
> The reason I initially included it was that during the development of
> this patch we were experimenting with variations of the
> vfat_build_dummy_83_buffer() function which put a wide varity of
> different values in the 11 bytes where a short filename would normally
> go.
>
> The most technically attractive varient was to put 11 spaces in
> there. That has the advantage that Windows then returns the long name
> to the GetShortPathName() API call, which is also what Windows does on
> a NTFS filesystem when the NTFS filesystem is configured not to have
> 8.3 names. So it would have been very nice to have this same behaviour
> on VFAT, instead of getting a single space back from
> GetShortPathName() as we get with the patch I posted.
>
> The reason we didn't go with the 11 spaces varient is that it causes
> WindowsXP to bluescreen. This is just a bug in WinXP, and is not
> present in Vista or Windows7.
>
> The 2nd technical problem with 11 spaces is that current Linux kernels
> would not see the long names, as the last_u logic in fat_search_long()
> will skip files where the the 11 bytes don't have at least one
> non-space byte before the first nul byte in either the 8 byte prefix
> or the 3 byte extension.
>
> The last_u logic is at odds with the behaviour of other operating
> systems for VFAT. On all windows varients that I have tested (and on
> MacOSX), the long name is still used no matter what values are in the
> 11 bytes. You can stick all nul bytes, all spaces, or anything else
> you like in there and Windows will still allow you to operate on the
> file by the long name and the filesystem will work perfectly.
>
> So that part of the patch is bringing us inline with the behaviour of
> other VFAT implementations.
>
> More importantly, it gives us the opportunity in the future to move to
> the techically better 11 spaces solution when either Microsoft fixes
> their WindowsXP crash bug, or WindowsXP has such a low market share
> that nobody cares any more (say like WfWg and maybe Win95 has now).
>
> If we don't put in this change now then we won't be able to move to
> the technically better solution later as we wouldn't have given Linux
> distros a chance to include support for the 11 spaces in distros. By
> putting that change in now, when (if?) we change to 11 spaces later we
> will not be breaking recent Linux kernels.
>
>  > This should probably be split out into a separate patch if it is the
>  > right thing to do, or drop it if (as it looks) there is no point in
>  > that change.
>
> hopefully the above explanation makes it clear why the last_u change
> should go together with the vfat_build_slots() change.

It is part of the same investigation certainly.

Given what you have said our interpretation of vfat has a bug,
and that small change is a candidate for -stable.  If it could
be it's own patch.

That change seems much less controversial and obviously correct
than the other.

Eric

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Eric,

 > Given what you have said our interpretation of vfat has a bug,
 > and that small change is a candidate for -stable.  If it could
 > be it's own patch.

good point. 

Hirofumi-san, would you support putting the last_u change into stable?

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[OGAWA Hirofumi]

tridge@samba.org writes:

>  > Given what you have said our interpretation of vfat has a bug,
>  > and that small change is a candidate for -stable.  If it could
>  > be it's own patch.
>
> good point. 
>
> Hirofumi-san, would you support putting the last_u change into stable?

If you want, I have no problem to do. However, I'm not thinking that
part is a bug.  And -stable rule is also "a real bug that bothers
people", but there is even a no bug reporter which tell actual problem.

Thanks.
-- 
OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Eric W. Biederman]

OGAWA Hirofumi <hirofumi@mail.parknet.co.jp> writes:

> tridge@samba.org writes:
>
>>  > Given what you have said our interpretation of vfat has a bug,
>>  > and that small change is a candidate for -stable.  If it could
>>  > be it's own patch.
>>
>> good point. 
>>
>> Hirofumi-san, would you support putting the last_u change into stable?
>
> If you want, I have no problem to do. However, I'm not thinking that
> part is a bug.  And -stable rule is also "a real bug that bothers
> people", but there is even a no bug reporter which tell actual problem.


Tridge.  Is there any reason to believe that Microsoft will continue
to treat Longfilenames without short filenames as valid in vfat?

If this turns into a contest of who can do the silliest things in
their vfat code microsoft could easily introduce a stricter directory
parser and cause all kinds of grief.

It wouldn't even surprise me if you haven't seen such shenanigans
while working on samba.

Eric

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[James Bottomley]

On Sun, 2009-06-28 at 12:51 -0700, Eric W. Biederman wrote:
> OGAWA Hirofumi <hirofumi@mail.parknet.co.jp> writes:
> 
> > tridge@samba.org writes:
> >
> >>  > Given what you have said our interpretation of vfat has a bug,
> >>  > and that small change is a candidate for -stable.  If it could
> >>  > be it's own patch.
> >>
> >> good point. 
> >>
> >> Hirofumi-san, would you support putting the last_u change into stable?
> >
> > If you want, I have no problem to do. However, I'm not thinking that
> > part is a bug.  And -stable rule is also "a real bug that bothers
> > people", but there is even a no bug reporter which tell actual problem.
> 
> 
> Tridge.  Is there any reason to believe that Microsoft will continue
> to treat Longfilenames without short filenames as valid in vfat?
> 
> If this turns into a contest of who can do the silliest things in
> their vfat code microsoft could easily introduce a stricter directory
> parser and cause all kinds of grief.
> 
> It wouldn't even surprise me if you haven't seen such shenanigans
> while working on samba.

If you own the platform, like Microsoft does, there are many things you
*could* do to make life difficult for others (like shipping a slightly
incompatible version of java, for instance ...).  However, having had
one or two consumer and regulatory backlashes from shipping updates
primarily designed to hobble what you think of as a competitor, you tend
to be much more wary about doing it so openly ... particularly when
you're trying to convince a wary customer base that you're the champion
of interoperability nowadays.

The bottom line is that we need to consider the current patch on its
merits for evading the vfat patent.  Speculating about what Microsoft
might or might not do to retaliate doesn't really help with this.

James

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Eric W. Biederman]

James Bottomley <James.Bottomley@HansenPartnership.com> writes:

> On Sun, 2009-06-28 at 12:51 -0700, Eric W. Biederman wrote:
>> OGAWA Hirofumi <hirofumi@mail.parknet.co.jp> writes:
>> 
>> > tridge@samba.org writes:
>> >
>> >>  > Given what you have said our interpretation of vfat has a bug,
>> >>  > and that small change is a candidate for -stable.  If it could
>> >>  > be it's own patch.
>> >>
>> >> good point. 
>> >>
>> >> Hirofumi-san, would you support putting the last_u change into stable?
>> >
>> > If you want, I have no problem to do. However, I'm not thinking that
>> > part is a bug.  And -stable rule is also "a real bug that bothers
>> > people", but there is even a no bug reporter which tell actual problem.
>> 
>> 
>> Tridge.  Is there any reason to believe that Microsoft will continue
>> to treat Longfilenames without short filenames as valid in vfat?
>> 
>> If this turns into a contest of who can do the silliest things in
>> their vfat code microsoft could easily introduce a stricter directory
>> parser and cause all kinds of grief.
>> 
>> It wouldn't even surprise me if you haven't seen such shenanigans
>> while working on samba.
>
> If you own the platform, like Microsoft does, there are many things you
> *could* do to make life difficult for others (like shipping a slightly
> incompatible version of java, for instance ...).  However, having had
> one or two consumer and regulatory backlashes from shipping updates
> primarily designed to hobble what you think of as a competitor, you tend
> to be much more wary about doing it so openly ... particularly when
> you're trying to convince a wary customer base that you're the champion
> of interoperability nowadays.
>
> The bottom line is that we need to consider the current patch on its
> merits for evading the vfat patent.  Speculating about what Microsoft
> might or might not do to retaliate doesn't really help with this.

This is a technical question.  Are we really in spec with the patch?

If we are not in spec. If we break things like checkdisk.exe.   Microsoft
can legitimately say we broke things and take technical measures to avoid
broken filesystems.  We have dome similar things to close source binary
modules.

My impression is that this patch puts us on the hairy edge.  If no
one is generating files without a short filename now.  That may cause
problems.

All else being equal this is a technically problematic patch as it
reduces the chances of interoperability.  I am just trying to gage
what those chances are.

Eric

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Eric,

 > Tridge.  Is there any reason to believe that Microsoft will continue
 > to treat Longfilenames without short filenames as valid in vfat?

I'd be quite surprised if they deliberately changed their VFAT code to
break Linux with this patch. I'd say it is more likely that once Linux
kernels with this change are in widespread use that Microsoft will
start to test any changes in their VFAT filesystem to make sure it
works with Linux with this patch.

 > It wouldn't even surprise me if you haven't seen such shenanigans
 > while working on samba.

In recent times Microsoft has been testing new OS releases against
Samba, and has been actively working with the Samba Team to try to
prevent breakages with new releases. That doesn't mean the scenario
you describe is impossible, it just means it isn't as likely as
perhaps it once was.

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[James Bottomley]

On Sun, 2009-06-28 at 13:45 -0700, Eric W. Biederman wrote:
> James Bottomley <James.Bottomley@HansenPartnership.com> writes:
> 
> > On Sun, 2009-06-28 at 12:51 -0700, Eric W. Biederman wrote:
> >> OGAWA Hirofumi <hirofumi@mail.parknet.co.jp> writes:
> >> 
> >> > tridge@samba.org writes:
> >> >
> >> >>  > Given what you have said our interpretation of vfat has a bug,
> >> >>  > and that small change is a candidate for -stable.  If it could
> >> >>  > be it's own patch.
> >> >>
> >> >> good point. 
> >> >>
> >> >> Hirofumi-san, would you support putting the last_u change into stable?
> >> >
> >> > If you want, I have no problem to do. However, I'm not thinking that
> >> > part is a bug.  And -stable rule is also "a real bug that bothers
> >> > people", but there is even a no bug reporter which tell actual problem.
> >> 
> >> 
> >> Tridge.  Is there any reason to believe that Microsoft will continue
> >> to treat Longfilenames without short filenames as valid in vfat?
> >> 
> >> If this turns into a contest of who can do the silliest things in
> >> their vfat code microsoft could easily introduce a stricter directory
> >> parser and cause all kinds of grief.
> >> 
> >> It wouldn't even surprise me if you haven't seen such shenanigans
> >> while working on samba.
> >
> > If you own the platform, like Microsoft does, there are many things you
> > *could* do to make life difficult for others (like shipping a slightly
> > incompatible version of java, for instance ...).  However, having had
> > one or two consumer and regulatory backlashes from shipping updates
> > primarily designed to hobble what you think of as a competitor, you tend
> > to be much more wary about doing it so openly ... particularly when
> > you're trying to convince a wary customer base that you're the champion
> > of interoperability nowadays.
> >
> > The bottom line is that we need to consider the current patch on its
> > merits for evading the vfat patent.  Speculating about what Microsoft
> > might or might not do to retaliate doesn't really help with this.
> 
> This is a technical question.  Are we really in spec with the patch?

Yes, the spec is here:

http://www.microsoft.com/whdc/system/platform/firmware/fatgen.mspx

(sorry, nasty licence agreement required to read it).

It says that long filenames *may* be created without short ones (but
that if you do this you'll have backwards compatibility problems on FAT
rather than FAT32 systems, which has been explicitly noted: after this
patch you can't read created files on 8.3 FAT).

> If we are not in spec. If we break things like checkdisk.exe.   Microsoft
> can legitimately say we broke things and take technical measures to avoid
> broken filesystems.  We have dome similar things to close source binary
> modules.

The question about spec isn't really that relevant with MS ... as you
can see from the Windows XP problems, they don't follow their own
spec ... the real question is has this been tested against existing
Windows versions; the answer is Yes (see FAQ).

> My impression is that this patch puts us on the hairy edge.  If no
> one is generating files without a short filename now.  That may cause
> problems.

Only for backwards compatibility ... and IBM has explicitly checked that
according to the FAQ.  They actually found Windows XP to be out of spec
(crashed with empty short filename) which is why the patch places an
invisible string in there now.

> All else being equal this is a technically problematic patch as it
> reduces the chances of interoperability.  I am just trying to gage
> what those chances are.

So the patch has been tested with Vista, Windows 7 and Windows XP ...
I'm sure IBM would be willing to do further interop testing if you
request.

James

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Jamie Lokier]

tridge@samba.org wrote:
> Hi Jan,
> 
>  > Can't we make this a runtime option?
> 
> John may be able to give you a more detailed answer, but the short
> answer is that it is much safer legally to not have the code in the
> binary kernel image at all.

Understood.

For those of us who don't want to omit the code, because we like
compatibility and we're not in affected countries, or for research, it
would be useful to have it as a mount option.

So there should be these compile-time options:

    1. CONFIG_VFAT_FS_DUALNAMES disabled:  Don't create shortnames.

    2. CONFIG_VFAT_FS_DUALNAMES enabled: Create shortnames, unless
       mount option "dualnames=no" is given, in which case that mount
       behaves as if CONFIG_VFAT_FS_DUALNAMES is disabled.

-- Jamie

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Jan Engelhardt]

On Sunday 2009-06-28 23:57, Jamie Lokier wrote:
>For those of us who don't want to omit the code, because we like
>compatibility and we're not in affected countries, or for research, it
>would be useful to have it as a mount option.
>
>So there should be these compile-time options:
>    2. CONFIG_VFAT_FS_DUALNAMES enabled: Create shortnames, unless
>       mount option "dualnames=no" is given, in which case that mount
>       behaves as if CONFIG_VFAT_FS_DUALNAMES is disabled.

If you are not in an affected country, why would you even want
to disable dualnames? [ on a per-mount basis...]

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Jamie Lokier]

Jan Engelhardt wrote:
> 
> On Sunday 2009-06-28 23:57, Jamie Lokier wrote:
> >For those of us who don't want to omit the code, because we like
> >compatibility and we're not in affected countries, or for research, it
> >would be useful to have it as a mount option.
> >
> >So there should be these compile-time options:
> >    2. CONFIG_VFAT_FS_DUALNAMES enabled: Create shortnames, unless
> >       mount option "dualnames=no" is given, in which case that mount
> >       behaves as if CONFIG_VFAT_FS_DUALNAMES is disabled.
> 
> If you are not in an affected country, why would you even want
> to disable dualnames? [ on a per-mount basis...]

   1. To test it's behaviour, without changing the whole running system.

   2. To produce disk images which are the same as would be produced
      in an affected country, or would be produced by a Linux distro
      adopting the behaviour.

-- Jamie

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Jamie,

 > For those of us who don't want to omit the code, because we like
 > compatibility and we're not in affected countries, or for research, it
 > would be useful to have it as a mount option.

For research I think having to recompile the module is not a big
burden.

The compatibility argument is more debatable, and if the patch
involved the loss of a large degree of functionality then I would
probably agree. As it is, the patch loses very little functionality -
it is hard to find real scenarios where not storing a 8.3 name along
with the long name will actually cause any problems.

I also don't think it is worth having a different kernel in different
countries for this change, again because the loss of functionality is
so small. The relevant patents exist in several countries (in various
forms), and while the US might be the country of choice for enforcing
patents it is not the only country where patents are a concern.

I would rather see us err on the side of caution and ensure that
Microsoft is not left with an opportunity to continue to spread FUD
about Linux with regards to these patents.

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Hirofumi-san,

 > If you want, I have no problem to do. However, I'm not thinking that
 > part is a bug.  And -stable rule is also "a real bug that bothers
 > people", but there is even a no bug reporter which tell actual problem.

ok, then what about pushing the whole patch into -stable?

The 'bug' in this case is like a security hole, with Microsoft
demonstrating an active exploit. This falls outside the normal range
of bug fixes for -stable, but I think you'd have to agree that the
whole situation is unusual.

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Greg KH]

On Mon, Jun 29, 2009 at 11:30:39AM +1000, tridge@samba.org wrote:
> Hi Hirofumi-san,
> 
>  > If you want, I have no problem to do. However, I'm not thinking that
>  > part is a bug.  And -stable rule is also "a real bug that bothers
>  > people", but there is even a no bug reporter which tell actual problem.
> 
> ok, then what about pushing the whole patch into -stable?
> 
> The 'bug' in this case is like a security hole, with Microsoft
> demonstrating an active exploit. This falls outside the normal range
> of bug fixes for -stable, but I think you'd have to agree that the
> whole situation is unusual.

I have no objection to take this patch for the -stable releases when it
goes into Linus's tree.  Just forward the git commit ids to
stable@kernel.org and I can take care of it.

thanks,

greg k-h

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

 > I have no objection to take this patch for the -stable releases when it
 > goes into Linus's tree.  Just forward the git commit ids to
 > stable@kernel.org and I can take care of it.

ok, thanks Greg.

Hirofumi-san tells me we've missed the merge window for 2.6.31, so it
seems that this will go first into the fatfs tree, then go into
Linus's tree via -next for 2.6.32. So hopefully the patch will get
some more testing (perhaps in -mm?) before it needs to be considered
for -stable.

Meanwhile some of the distros and other vendors might decide to apply
it sooner depending on their level of legal concern.

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Greg KH]

On Tue, Jun 30, 2009 at 08:42:42AM +1000, tridge@samba.org wrote:
>  > I have no objection to take this patch for the -stable releases when it
>  > goes into Linus's tree.  Just forward the git commit ids to
>  > stable@kernel.org and I can take care of it.
> 
> ok, thanks Greg.
> 
> Hirofumi-san tells me we've missed the merge window for 2.6.31, so it
> seems that this will go first into the fatfs tree, then go into
> Linus's tree via -next for 2.6.32. So hopefully the patch will get
> some more testing (perhaps in -mm?) before it needs to be considered
> for -stable.

That sounds reasonable.  Just add a:
	Cc: stable <stable@kernel.org>
in the "signed-off-by:" area of the patch, and when it goes into Linus's
tree, the -stable team will be automatically notified of it and we will
pick it up.

It needs to be in Linus's tree before we can add it to the -stable
releases.

thanks,

greg k-h

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[OGAWA Hirofumi]

tridge@samba.org writes:

>  > I have no objection to take this patch for the -stable releases when it
>  > goes into Linus's tree.  Just forward the git commit ids to
>  > stable@kernel.org and I can take care of it.
>
> ok, thanks Greg.
>
> Hirofumi-san tells me we've missed the merge window for 2.6.31, so it
> seems that this will go first into the fatfs tree, then go into
> Linus's tree via -next for 2.6.32. So hopefully the patch will get
> some more testing (perhaps in -mm?) before it needs to be considered
> for -stable.

Yes. And I will not drop this patch even if it's not perfect on test. I
can understand it would not be the option for some users. The default
may be arguable though, like I said at first.

My choice is to provide the option of those to users.

> Meanwhile some of the distros and other vendors might decide to apply
> it sooner depending on their level of legal concern.

Yes, it's good.

Thanks.
-- 
OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hirofumi-san writes:
 > Yes. And I will not drop this patch even if it's not perfect on test. I
 > can understand it would not be the option for some users.

ok, good

 > The default may be arguable though, like I said at first.

I suggest we leave the default as "no dual names" for now to let it
get some more testing, then if any problems come up then we can look
at the choice of default again. If no problems come up we can keep the
default as it is in the patch now.

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[OGAWA Hirofumi]

tridge@samba.org writes:

>  > The default may be arguable though, like I said at first.
>
> I suggest we leave the default as "no dual names" for now to let it
> get some more testing, then if any problems come up then we can look
> at the choice of default again. If no problems come up we can keep the
> default as it is in the patch now.

Ok, I've applied the patch + Cc: to fatfs-2.6.git.
-- 
OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Pavel Machek]

> When VFAT_FS_DUALNAMES is disabled we avoid the creation of 8.3 short
> filenames for files on VFAT filesystems that require a long name. The
> patch uses a pattern of 11 bytes in the directory entry which contains
> invalid characters such that it cannot be considered to be a valid short
> filename.
> 
> Signed-off-by: Andrew Tridgell <tridge@samba.org>
> Acked-by: Dave Kleikamp <shaggy@linux.vnet.ibm.com>
> Acked-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> ---
>  fs/fat/Kconfig      |   20 +++++++++++++++++
>  fs/fat/dir.c        |   15 ++++++-------
>  fs/fat/namei_vfat.c |   59 +++++++++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 86 insertions(+), 8 deletions(-)
> 
> diff --git a/fs/fat/Kconfig b/fs/fat/Kconfig
> index 182f9ff..907a5de 100644
> --- a/fs/fat/Kconfig
> +++ b/fs/fat/Kconfig
> @@ -74,6 +74,26 @@ config VFAT_FS
>  	  To compile this as a module, choose M here: the module will be called
>  	  vfat.
>  
> +config VFAT_FS_DUALNAMES
> +	bool "VFAT dual names support"
> +	depends on VFAT_FS


Defaults should be back-compatible.

> +
> +	  Users considering enabling this option should consider the implications
> +	  of any patents that may exist on dual filenames in VFAT.
> +
> +	  If unsure, say N

Say Y.

Users considering disabling this should understand that filesystem
they write to will not be valid vfat filesystems, and may trigger bugs
in  some devices.

> +#ifndef CONFIG_VFAT_FS_DUALNAMES
> +/*
> + * build a 11 byte 8.3 buffer which is not a short filename. We want 11
> + * bytes which:
> + *    - will be seen as a constant string to all APIs on Linux and Windows
> + *    - cannot be matched with wildcard patterns
> + *    - cannot be used to access the file
> + *    - has a low probability of collision within a directory
> + *    - has an invalid 3 byte extension
> + *    - contains at least one non-space and non-nul byte
> + */

What happens on collision? With 60000 entries in directory, there will
be 50% chance of collision. BAD.

Why not use something like position in directory instead of random
number?
									Pavel
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Alan Cox]

> What happens on collision? With 60000 entries in directory, there will
> be 50% chance of collision. BAD.

Far more surely - its a birthday paradox.

> Why not use something like position in directory instead of random
> number?

Agreed 100%. I'm also not sure it should be called "vfat" when operating
in this mode as it's not vfat any more - it needs a new name.

Alan

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Rusty Russell]

On Tue, 30 Jun 2009 04:01:03 pm Pavel Machek wrote:
> > +config VFAT_FS_DUALNAMES
> > +	bool "VFAT dual names support"
> > +	depends on VFAT_FS
>
> Defaults should be back-compatible.

Hi Pavel,

I disagree with this: given there's been testing with no known issues, it's 
not a back compat question.

I'd actually prefer to see the code ripped out and no config option available; 
it would the clearest avoidance case possible.

I really don't want us to have to do this more than once :(
Rusty.

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Pavel,

 > Defaults should be back-compatible.

I would usually agree, but I think we have an unusual situation here,
in some ways similar to a demonstrated security hole. The previous
behaviour exposed a lot of Linux vendors to the possibility of an
expensive legal fight.

If we had some way to be completely backwards compatible while
avoiding the legal issues then of course we should take that. I tried
hard to find a varient that achieved that, but the best I could manage
was what I have posted. It may be that someone else can find a better
varient that avoids the legal issues while remaining fully backward
compatible.

 > Users considering disabling this should understand that filesystem
 > they write to will not be valid vfat filesystems, and may trigger bugs
 > in some devices.

If we find any devices that exhibit any problems with this patch while
it is in linux-next (and maybe linux-mm?) then this warning would
indeed be appropriate. It no such devices are known then I think the
warning is going a bit far. 

Do you have a specific device in mind with regard to this warning?

 > What happens on collision? With 60000 entries in directory, there will
 > be 50% chance of collision. BAD.

Why do you say it is bad? You need to remember that those 11 bytes
cannot be used as a filename, so it isn't a filename collision. As I
mentioned in the reply to Eric's question, a quite good choice is to
use 11 spaces for every file, and that only falls down because
WindowsXP has a bug that causes that varient to bluescreen.

The only risks with collisions that I am aware of are:

  - there is a very small chance (much, _much_ less than 50% with 60k
    files) of WindowsXP bluescreening. I've never in fact managed to
    reproduce this with the current patch, despite many days of
    continuous randomised testing. The reason the probability is much
    smaller than 50% at 60k is that it doesn't bluescreen just because
    there is a duplicate 8.3 entry - it bluescreens with a particular
    access pattern that involves 2 entries with the same 11 bytes,
    that access pattern is very hard to produce.

  - chkdsk.exe will complain about duplicates, and will rename one of
    the two files. That is a 50% chance of 1 file being renamed for a
    single directory containing 60k files. Given it isn't all that
    common to run chkdsk on removable media that is shared between
    Linux and Windows, I thought that this is not a terribly large
    concern.

 > Why not use something like position in directory instead of random
 > number?

We did of course consider that, and the changes to the patch to
implement collision avoidance are relatively simple. We didn't do it
as it would weaken the legal basis behind the patch. I'll leave it to
John Lanza (the LF patent attorney) to expand on that if you want more
information.

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Alan,

 > > What happens on collision? With 60000 entries in directory, there will
 > > be 50% chance of collision. BAD.
 > 
 > Far more surely - its a birthday paradox.

If you want to do it accurately, the maximum number of long filenames
in a VFAT directory is actually 32767. (it isn't 65536, as each long
filename consumes at least two 8.3 entries, plus you lose the . and
.. entries).

With the patch I've posted there are 30 bits of randomness in each
entry. You could do an accurate binomial expansion to get the exact
probability, but a very good approximation using exponentiation comes
out as a 39.3% chance of a single duplicate appearing in a directory
that is fully populated.

As I mentioned to Pavel, this isn't the whole story though. To cause
the bluescreen the duplicate entries need to be accessed by WindowsXP
in quick succession in a particular pattern. This lowers the
probability a lot. Exactly how much is hard to estimate, but
experiments I've done with deliberately higher probabilities (ie. less
bits of randomness) show that the probability of the bluescreen is
_very_ low.

 > Agreed 100%. I'm also not sure it should be called "vfat" when operating
 > in this mode as it's not vfat any more - it needs a new name.

If the code differed significantly between the two implementations I'd
probably agree, but as the two are extremely close I think maintaining
a separate filesystem isn't worth it.

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Alan Cox]

> I'd actually prefer to see the code ripped out and no config option available; 
> it would the clearest avoidance case possible.

What about the free world - why should we suffer because Americans have
a broken patent system ? That just leads to a Farenheit 451 model where
the kernel sources end up containing no code, text or image that can
offend, harm or be found wanting in any possible legal jurisdiction.

If we put in VFAT american fixes presumably we need to put in monitoring
features required by dubious governments ?

If you want to rip stuff out of your copy feel free. I am quite sure many
US based vendors will do that (because they do so already with things
like video codecs rather than just disabling the build option).

Also please stop calling it VFAT. With the changes made it isn't VFAT and
it's misleading to an end user to advertise it as vfat and users
shouldn't accidentally be able to specify -o vfat and get non-vfat. Thats
asking for incompatibility, data loss and unpleasant unwarned of suprises.

Its "linfat" or something which when you've fixed the bugs Pavel has
pointed out might be semi-compatible with other products (most *FAT using
products don't use Microsofts implementation). Testing it versus Windows
and saying it works is not really adequate. Thats what ACPI and BIOS
people do that *we* moan about all the time.

Alan

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Alan Cox]

> I would usually agree, but I think we have an unusual situation here,
> in some ways similar to a demonstrated security hole. The previous
> behaviour exposed a lot of Linux vendors to the possibility of an
> expensive legal fight.

They don't have to ship the code. They can rip it out. They deal with
video players the same way for the USSA market and have done for years.

>   - chkdsk.exe will complain about duplicates, and will rename one of
>     the two files. That is a 50% chance of 1 file being renamed for a
>     single directory containing 60k files. Given it isn't all that
>     common to run chkdsk on removable media that is shared between

Its a standard usage pattern for some people. Think about Linux based
commodity devices such as the N770 and plugging it into the users general
purpose PC box. Whenever it got pulled out wrongly it *will* get a chkdsk
in Windows.

>     Linux and Windows, I thought that this is not a terribly large
>     concern.

Disagree. Its a rapidly growing market segment.

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Alan Cox]

>  > Agreed 100%. I'm also not sure it should be called "vfat" when operating
>  > in this mode as it's not vfat any more - it needs a new name.
> 
> If the code differed significantly between the two implementations I'd
> probably agree, but as the two are extremely close I think maintaining
> a separate filesystem isn't worth it.

It needs a different name to the user. If the new fs isn't vfat (which it
isn't) and doubly so if it can crash Windows XP at random on very rare
occasions then users need to know its different.

Imagine someone sticks a Linux written disk into a mission critical
windows server - I think they have a right to know and not accidentally
wander into a situation where they bring that box down ?

mount -o vfat should fail for this non-vfat.

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Boaz Harrosh]

On 07/01/2009 01:50 PM, tridge@samba.org wrote:
> Hi Pavel,
> 
> We did of course consider that, and the changes to the patch to
> implement collision avoidance are relatively simple. We didn't do it
> as it would weaken the legal basis behind the patch. I'll leave it to
> John Lanza (the LF patent attorney) to expand on that if you want more
> information.
> 

You completely lost me here. And I thought I did understand the patent
and the fix.

what is the difference between.

short_name = rand(sid);
and
short_name = sid++;

Now if you would do
short_name = MD5(long_name);

That I understand since short_name is some function of long_name
but if I'm just inventing the short_name out of my hat. In what legal
system does it matter what is my random function I use?

> Cheers, Tridge

Boaz

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Boaz,

 > That I understand since short_name is some function of long_name
 > but if I'm just inventing the short_name out of my hat. In what legal
 > system does it matter what is my random function I use?

I like to defer to John Lanza for a more complete answer to this, but
I can tell you that it is not related to the choice of random
function.

I'd also suggest that if anyone wants to go into this in any depth
then private email with John Lanza is the best option.

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Alan,

 > They don't have to ship the code. They can rip it out. They deal with
 > video players the same way for the USSA market and have done for years.

yes, vendors can make the patch unconditional of course. I thought
that we were not trying to encourage divergance between the kernel.org
tree and the vendor trees though? I know some divergance is always
going to happen, but it seems counter productive to be encouraging it.

 > Its a standard usage pattern for some people. Think about Linux based
 > commodity devices such as the N770 and plugging it into the users general
 > purpose PC box. Whenever it got pulled out wrongly it *will* get a chkdsk
 > in Windows.

really? I haven't noticed that behaviour for removable devices in
windows. You can manually set a drive to be checked on reboot, but I
wasn't aware of any automatic chkdsk mechanism for VFAT removable
media in windows. Have you seen this yourself?

In testing this patch I've pulled USB keys in and out of WinXP, Vista
and Windows7 hundreds of time, and done it programatically millions of
times via scripting on virtual machines, but I never noticed this
feature. Perhaps it happens only under some specific circumstances I
haven't seen?

 > >     Linux and Windows, I thought that this is not a terribly large
 > >     concern.
 > 
 > Disagree. Its a rapidly growing market segment.

you chopped off a word or two in the quote :-)

Of course I care about Linux/Windows interop, as I'm sure you know!
What I'm saying is that running chkdsk on a shared removable media
which contains 30k files in a single directory is not a common event,
and even when it does happen the consequences are that approximately
one in 3 times you do this, one of those 30k files gets renamed.

As evidence for this I'd like to point out that windows chkdsk has
complained about the Linux VFAT implementation for a long time, even
without my patch. If you create a filesystem with mformat and then
chkdsk it on windows you get:

  Bad links in lost chains at cluster 2 corrected
  Convert lost chains to files (Y/N)

yet I can't find a single instance of anyone complaining about this
with a google search. If a chkdsk was automated for removable media
then a lot of peoples machines would be asking them this question a
lot of the time. If people manually ran windows chkdsk on removable
VFAT media created on Linux then they also would have hit this and I
would have expected at least someone to have mentioned it.

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Alan Cox]

> yes, vendors can make the patch unconditional of course. I thought
> that we were not trying to encourage divergance between the kernel.org
> tree and the vendor trees though? I know some divergance is always
> going to happen, but it seems counter productive to be encouraging it.

What about all the other damage vendors do to the tree and the junk they
stuff in their kernels - we don't accept that upstream either ?

> 
>  > Its a standard usage pattern for some people. Think about Linux based
>  > commodity devices such as the N770 and plugging it into the users general
>  > purpose PC box. Whenever it got pulled out wrongly it *will* get a chkdsk
>  > in Windows.
> 
> really? I haven't noticed that behaviour for removable devices in
> windows. You can manually set a drive to be checked on reboot, but I
> wasn't aware of any automatic chkdsk mechanism for VFAT removable
> media in windows. Have you seen this yourself?

Its manual unless the device is visibly corrupted but it should still
work. The point I was making is that the world of "Windows PC & Linux
handheld device" is an important one.

> lot of the time. If people manually ran windows chkdsk on removable
> VFAT media created on Linux then they also would have hit this and I
> would have expected at least someone to have mentioned it.

Devices come formatted for VFAT already - and I can't duplicate your bug
report on a USB key here so presumably some specific size/defaults are
needed ? (Would be good to fix that anyway)

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Alan,

 > What about all the other damage vendors do to the tree and the junk they
 > stuff in their kernels - we don't accept that upstream either ?

sure, but there is no need to encourage bad behaviour by building it
into the upstream :-)

 > Its manual unless the device is visibly corrupted but it should still
 > work.

ok, with the patch I've posted applied, can you reproduce this?
Perhaps by deliberately corrupting the device in some other way (using
dd?) then running a chkdsk?

If you try to reproduce it then make sure you completely fill the VFAT
directory. If you have (for example) only 1000 files in a directory
then you'd have to redo the deliberate corruption test with new files
about 2000 times before you get a single error and rename from
chkdsk. If you only have 100 files then you'll have to do it nearly a
million times per rename.

 > The point I was making is that the world of "Windows PC & Linux
 > handheld device" is an important one.

yes, it's an extremely important use for Linux. That is why I've spent
the last 4 months working on ensuring that it continues to be viable,
by trying to create the most legally robust, most compatible patch I
can that allows these devices to continue to exist without running
significant legal risks.

If there is another approach that achieves this goal in a better way
then we should look at it. Can you suggest an alternative that will
work better for Linux handheld device makers?

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Theodore Tso]

On Wed, Jul 01, 2009 at 12:25:58PM +0100, Alan Cox wrote:
> 
> Also please stop calling it VFAT. With the changes made it isn't VFAT and
> it's misleading to an end user to advertise it as vfat and users
> shouldn't accidentally be able to specify -o vfat and get non-vfat. Thats
> asking for incompatibility, data loss and unpleasant unwarned of suprises.

There really was no such thing as "vfat" anyway.  VFAT in the Windows
world names a specific implementation (the "V" stands for virtual)
back in the days when Windows 3.1 was primarily a 16-bit OS, and there
were two instances of the "fat" filesystem code; one for the 16 bit
implementation, and one for 32-bit applications.  As it happened the
32-bit implementation under Windows 3.1 happened to contain support
for the Long File Names extension, and due to this confusion of
implementation vs. specification, in Linux is misnamed something as
"vfat" when most of the rest of the world simply just calls it "FAT".

Arguably what we should have done is kept it as a single filesystem,
with a mount options "lfn" and "nolfn", but that's water under the
bridge now.

> (most *FAT using products don't use Microsofts
> implementation). Testing it versus Windows and saying it works is
> not really adequate. Thats what ACPI and BIOS people do that *we*
> moan about all the time.

This *is* a legitimate concern.  I'll note that many of the modern-day
products actually use Linux (i.e., the Sony eReader, the Kindle,
etc. --- and so as much as you might kvetch about the rest of the
"Free World" not having the same broken patent system as the US, the
economic realities of these products losing access to the US market
would be quite devastating to most of these products' manufacturers
even if some of them are developed and manufactured outside of the
US), and so doing compatibility testing with Linux is relatively easy.

The other big user I can think of are digital cameras, but (a)
normally most users read from them and then delete the pictures, and
rarely write to media meant for a digital camera, and (b) the DCIM
standard for digital cameras explicitly only supports 8.3 filenames
and so digital camera manufacturers explicitly don't need to deal with
Long File Names at all.  (Hmm.... I wonder why....)  

This suggests that some userspace mechanism for detecting media cards
used for cameras and explicitly mounting them with FAT might be useful
--- since the camera isn't going to be able to recognize LFN's anyway.
It also suggests that some testing to make sure there aren't bugs in
various non-Linux FAT using devices would probably be useful, and that
a config option might be a good way to enable people to do such
testing and fall back if it turns out to be problems with such
devices.

Ultimately, though, requiring that every single possible device be
tested is probably not reasonable, so the best way to do this testing
is the way do most of our testing; we do basic due diligence, but then
we merge it into mainline and let our huge user community try it out.
If there are regressions we can work through those issues if and when
they arise.

						- Ted

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Alan Cox]

> > shouldn't accidentally be able to specify -o vfat and get non-vfat. Thats
> > asking for incompatibility, data loss and unpleasant unwarned of suprises.
> 
> There really was no such thing as "vfat" anyway.  VFAT in the Windows

In the eyes of the end user there is such a thing as vfat. This is about
expectations not technical issues.
 
> Arguably what we should have done is kept it as a single filesystem,
> with a mount options "lfn" and "nolfn", but that's water under the
> bridge now.

Well we didn't so now we need to add "lfat" or similar for our fat style.
Doesn't need new code just making sure that USSA_COMPLIANCE_MODE=y
causes mount -o lfat to work and without it both lfat and vfat work.

> The other big user I can think of are digital cameras, but (a)
> normally most users read from them and then delete the pictures, and
> rarely write to media meant for a digital camera, and (b) the DCIM

Except when they hit save instead of "save as" and they get a long file
name and invisible loss of space on the camera.

> standard for digital cameras explicitly only supports 8.3 filenames
> and so digital camera manufacturers explicitly don't need to deal with
> Long File Names at all.  (Hmm.... I wonder why....)  

Can't think - but HAL should clearly mount those 8.3 to avoid the
problem. It seems to use the dcim to find them.

> This suggests that some userspace mechanism for detecting media cards
> used for cameras and explicitly mounting them with FAT might be useful

HAL is very good at that already.

> Ultimately, though, requiring that every single possible device be
> tested is probably not reasonable, so the best way to do this testing
> is the way do most of our testing; we do basic due diligence, but then
> we merge it into mainline and let our huge user community try it out.
> If there are regressions we can work through those issues if and when
> they arise.

>From the funnies we've had in the past with FAT my gut impression is
there are only a few implementations out there. Psion seems to have their
own but most of the rest behave remarkably similarly which makes me
suspect they all licensed a tiny number of implementations (DRDOS one
perhaps ?). If we can keep most of those devices mounted 8.3 we nicely
sidestep the issue anyway.

Alan

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Alan Cox]

> If there is another approach that achieves this goal in a better way
> then we should look at it. Can you suggest an alternative that will
> work better for Linux handheld device makers?

They can type 

patch -p1 < linux-foundation-recommended-ussa-fat.patch

which removes all the subversive terrorist code that Americans are scared
to posess.

As has already been said from their point of view thats lowest risk so
they will go that path anyway because the question is always "how do I
cover my backside maximally"

Vendors already do this for other stuff. Why is the kernel special or
different ? Take a look at Red Hat RPMS of music players, video players,
even things like netpbm for a while where JBIG had patent issues and was
simply ripped out of the package.

I think you are in real danger of creating a compromise that helps nobody

Putting the stuff in kernel upsets everyone who isn't under US rule,
creates situations where things cannot be discussed and doesn't make one
iota of difference to the vendors because they will remove the code from
the source tree options and all anyway - because as has already been said
it reduces risk.

It also sets a very dangerous precedent. What do you want to do about say
our Kconfig help for 'Taiwanese' if it doesn't meet Chinese regulations.
What about the Burmese code page. What about code submissions from Iran ?

The kernel really cannot and should not get involved in these. Its a
vendor problem. They deal with it every day of the year already from MP3
to Taiwanese flags to US crypto export regulations to patents to the
openssh option for using the DVD crypto algorithm to making sure their
language definitions don't get their product banned in some jurisdiction
or another. They have to remove games that glorify war in any way from
German product, and so on..

None of this other mass of red tape, bogocracy and the like gets dumped
on users all over the world. It's handled by specialists in vendor
companies supported by qualified legal personnel with whom they can have
full and frank discussion.

Another problem with this is that the foundation lawyers goals are almost
certainly influenced by the goal to maximise arse coverage for large
businesses with US connections. That is who pays them, that is who asks
their advice. That puts them partly at odds with the general good.

Alan

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[James Bottomley]

On Wed, 2009-07-01 at 14:48 +0300, Boaz Harrosh wrote:
> On 07/01/2009 01:50 PM, tridge@samba.org wrote:
> > Hi Pavel,
> > 
> > We did of course consider that, and the changes to the patch to
> > implement collision avoidance are relatively simple. We didn't do it
> > as it would weaken the legal basis behind the patch. I'll leave it to
> > John Lanza (the LF patent attorney) to expand on that if you want more
> > information.
> > 
> 
> You completely lost me here. And I thought I did understand the patent
> and the fix.
> 
> what is the difference between.
> 
> short_name = rand(sid);
> and
> short_name = sid++;
> 
> Now if you would do
> short_name = MD5(long_name);
> 
> That I understand since short_name is some function of long_name
> but if I'm just inventing the short_name out of my hat. In what legal
> system does it matter what is my random function I use?

We're sort of arguing moot technicalities here.  If you look at the way
the filename is constructed, given the constraints of a leading space
and a NULL, the need for a NULL padded leading slash extension and the
need to put control characters in the remaining bytes, we've only got 30
bits to play with, we're never going to avoid collisions in a space of
up to 31 bits.  Technically, a random function is at least as good at
collision avoidance as any deterministic solution ... and it's a lot
easier to code.

James

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Stefan Richter]

Theodore Tso wrote:
> I'll note that many of the modern-day
> products actually use Linux (i.e., the Sony eReader, the Kindle,
> etc.

Many MP3/Video players surely do not run an embedded Linux.

Besides, it doesn't matter what "many" devices run if the talk is about 
defaults, or even about ripping the working, proven code out of the 
mainline.  (Well, that suggestion was absurd.)

> The other big user I can think of are digital cameras, but (a)
> normally most users read from them and then delete the pictures,

I use my SD cards not only in the camera but also as generic mobile 
storage with laptops and media player.

There is no way for software to detect that a medium is going to be used 
with a 8.3-only device exclusively.
-- 
Stefan Richter
-=====-==--= -=== ----=
http://arcgraph.de/sr/

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Rusty Russell]

On Wed, 1 Jul 2009 08:55:58 pm Alan Cox wrote:
> > I'd actually prefer to see the code ripped out and no config option
> > available; it would the clearest avoidance case possible.
>
> What about the free world - why should we suffer because Americans have
> a broken patent system ? That just leads to a Farenheit 451 model where
> the kernel sources end up containing no code, text or image that can
> offend, harm or be found wanting in any possible legal jurisdiction.

We put in workarounds for broken hardware, even though we rightfully dislike 
it.  Similarly, in this case a minor change prevents a real problem 
experienced by our users (yes, I know we only have one public bug report).

It's bad.  Yes, let's bitch about it.  And workaround it anyway.
Rusty.

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Alan,

 > > There really was no such thing as "vfat" anyway.  VFAT in the Windows
 > 
 > In the eyes of the end user there is such a thing as vfat. This is about
 > expectations not technical issues.

Do you have an example of an end user device that would be affected by
this change, and which is never distributed in any of the countries
where a varient of this patent exists?

 > From the funnies we've had in the past with FAT my gut impression is
 > there are only a few implementations out there. Psion seems to have their
 > own but most of the rest behave remarkably similarly which makes me
 > suspect they all licensed a tiny number of implementations (DRDOS one
 > perhaps ?).

Do you happen to have a Psion and/or DRDOS based device in your
collection of toys so you can test with the proposed patch and see if
there are any problems?

Apart from Windows varients and MacOSX I have also tested on the
following mobile phones (via a microSD card):

  Samsumg SGH-E250
  Nokia 6120

They both worked fine with long filename images saved on a Linux
system with this patch. I don't know what OSes these phones are based
on.

Maybe you could test on the various devices with removable media you
have and see how it goes?

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Alan,

 > They can type 
 > 
 > patch -p1 < linux-foundation-recommended-ussa-fat.patch
 > 
 > which removes all the subversive terrorist code that Americans are scared
 > to posess.

I think you'll find that most distro makers and most vendors of Linux
based devices will want to have this patch applied. So if we took the
approach you suggest, then the testing done via kernel.org trees will
not match what the vast majority of Linux users will actually be
running. That would seem to be counter to good QA practices.

If the patch had significant negative consequences for normal use then
I'd be proposing the default be for dualnames to be enabled, which is
why the first patch I posted in May that disabled creation of long
filenames defaulted to off.

So please do as much testing as you have time for, and I'll continue
to ask people to let me try their mobile phones with a microSD card
and see how many different embedded OSes I can test that way. So far
the count is zero devices affected in a negative way by the proposed
patch.

If we get some real examples of devices that are badly affected then
we could revisit the question of what the default should be. With the
count at zero it seems counter-productive to disable this change in
the git trees that will allow it to get some wider testing.

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Alan Cox]

> I think you'll find that most distro makers and most vendors of Linux
> based devices will want to have this patch applied. So if we took the

Good for them

> approach you suggest, then the testing done via kernel.org trees will
> not match what the vast majority of Linux users will actually be
> running. That would seem to be counter to good QA practices.

The vendor trees all contain patches and have done for years, often lots
of them. They will apply the patch if you put VFAT_DUALNAMES into the
kernel as well so your argument is totally bogus. It always was totally
bogus, it always will be. Vendors do not use the base kernel as is in
normal product. They ship

	Base kernel
	+ Patches for packaging systems
	+ .1/.2/.3 bits
	+ Cherry pick of stuff that deals with bugs they think have to be
	  stomped by some means
	+ drivers they add which are not yet fit for kernel
	+ exciting stuff they think is cool and makes their distro
	  special (eg KMS patches)


Its starting to sound like the Foundation and someone have signed some
kind of settlement to get this change into the Linux kernel regardless of
the technical issues, practicality or community and this is all for show
anyway.

> If the patch had significant negative consequences for normal use then

You said yourself it can crash XP.

> If we get some real examples of devices that are badly affected

XP crashing by suprise if you are really really unlucky strikes me as a
good example and one you provided.

You've also ignored entirely the fact that this isn't a VFAT file system
so irrespective of whether this goes in it should not be used for mount
-o vfat.

There is a clear end user expectation that vfat means "microsoft fat with
extended names". By all means add support for "not vfat" but don't call
it "vfat" as that is misleading an interface breakage.

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Alan Cox]

On Thu, 2 Jul 2009 11:42:39 +1000
tridge@samba.org wrote:

> Hi Alan,
> 
>  > > There really was no such thing as "vfat" anyway.  VFAT in the Windows
>  > 
>  > In the eyes of the end user there is such a thing as vfat. This is about
>  > expectations not technical issues.
> 
> Do you have an example of an end user device that would be affected by
> this change, and which is never distributed in any of the countries
> where a varient of this patent exists?

You gave one: Microsoft Windows XP. Risk of very rare system crashes.

Thats enough in a high reliability environment to require the file system
in question is banned from use site wide at may locations. Can't have a
flash card bringing down a windows dependant US destroyer can they.

Getting "not vfat" by suprise is thus really really bad

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Alan,

 > The vendor trees all contain patches and have done for years, often lots
 > of them. They will apply the patch if you put VFAT_DUALNAMES into the
 > kernel as well so your argument is totally bogus. It always was totally
 > bogus, it always will be.

well, I certainly don't have your experience with kernel development,
but it seems fairly basic to me that if a patch is likely to be in use
by the majority of Linux users (via distros/vendors) that having it in
the upstream kernel makes sense. 

If I'm wrong and a large proportion of distros/vendors won't want this
patch then of course the argument falls down, and in that case it
would seem perfectly reasonable for the upstream kernel not to have
it, or for it to be inactive by default.

Meanwhile it has gone into fatfs-2.6, and linux-next where I hope it
will get some testing. Whether it then goes into Linus's tree for
2.6.32 is a decision for Hirofumi (and presumably Linus if he decides
to weigh in on this). Similarly what the default should be is their
decision. I'm happy that it is getting some testing now, and I hope
that if that testing doesn't show any issues that it will be accepted
for 2.6.32.

 > Its starting to sound like the Foundation and someone have signed some
 > kind of settlement to get this change into the Linux kernel regardless of
 > the technical issues, practicality or community and this is all for show
 > anyway.

err, no. The idea for this patch came when I was reading the first lwn
article on the TomTom suit, and because I happen to have a TomTom at
home and like it. I then started investigating and found some ways to
avoid the patent. I do patent avoidance work quite frequently,
although usually for Samba and in that case I just put the patches
into Samba along with the rest of my code.

There is no "settlement" here (who exactly are you saying is settling
with whom??). There is just a patent avoidance patch that I think is a
very good idea, and that I have gone to the effort of getting very
carefully checked by the appropriate experts. I was helped in this by
some extremely good people (such as Paul McKenney, who has a lot of
experience in this area), and I think the result is a good one.

This discussion is not for show. If Hirofumi/Linus or whoever else is
responsible reject the patch then we don't have any secret backdoor to
get it in. All we can do is present the patch and hope to persuade the
kernel community that it is a good idea.

 > > If the patch had significant negative consequences for normal use then
 > 
 > You said yourself it can crash XP.

well, the WindowsXP fastfat driver isn't exactly known as being
stable! Do a search for fastfat bluescreen and you'll find a huge
number of hits on people complaining about it bluescreening when it
opens FAT filesystems created by all sorts of systems (eg. iPods).

 > You've also ignored entirely the fact that this isn't a VFAT file system
 > so irrespective of whether this goes in it should not be used for mount
 > -o vfat.

Other OSes (eg. Windows) don't tend to distinguish between FAT and
VFAT. It is just a FAT filesystem with a varying range of features. On
Linux we've chosen one particular set of features and labelled that
VFAT, then we've chosen a different set of features and labelled it
'MSDOS'. Within what we have labelled as VFAT we have some existing
runtime options that select different varients. I would have liked to
do the 'dualnames' patch as a runtime option, but that doesn't satisfy
the legal requirements.

So I think you're coming at this very much from a Linux centric point
of view (not surprising!), and even there I very much doubt that many
end users think about the intricacies of what FAT filesystem options
they want. Most systems just auto-mount removable media these days
with whatever options the distro vendors choose (or via HAL rules).

Thus I don't think the "end user expectation" is a strong argument for
making this an entirely new filesystem.

It really is up to Hirofumi-san though. If he asks me to redo the
patch so that it creates a new FAT filesystem varient then I'd be more
than happy to do that. I personally think it will create more
maintainence overhead than it is worth, but as the FAT filesystem
maintainer it is certainly his choice.

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Alan,

 > You gave one: Microsoft Windows XP. Risk of very rare system crashes.
 > 
 > Thats enough in a high reliability environment to require the file system
 > in question is banned from use site wide at may locations. Can't have a
 > flash card bringing down a windows dependant US destroyer can they.

I think it could indeed be very wise not to insert FAT removable media
into 'high reliability' WindowsXP machines, but not because of the
patch I've proposed. A prudent IT manager might take a look at how
many fastfat.sys crashes are being reported on WindowsXP and realise
that viewing ones holiday photos on your heart bypass machine isn't a
great idea :-)

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[James Bottomley]

On Thu, 2009-07-02 at 11:32 +0100, Alan Cox wrote:
> > I think you'll find that most distro makers and most vendors of Linux
> > based devices will want to have this patch applied. So if we took the
> 
> Good for them
> 
> > approach you suggest, then the testing done via kernel.org trees will
> > not match what the vast majority of Linux users will actually be
> > running. That would seem to be counter to good QA practices.
> 
> The vendor trees all contain patches and have done for years, often lots
> of them. They will apply the patch if you put VFAT_DUALNAMES into the
> kernel as well so your argument is totally bogus. It always was totally
> bogus, it always will be. Vendors do not use the base kernel as is in
> normal product. They ship

As a linux maintainer, you know we try very hard to encourage vendors
not to carry long lived out of tree patches because of the complexity it
causes for everyone.

> 	Base kernel
> 	+ Patches for packaging systems
> 	+ .1/.2/.3 bits
> 	+ Cherry pick of stuff that deals with bugs they think have to be
> 	  stomped by some means
> 	+ drivers they add which are not yet fit for kernel
> 	+ exciting stuff they think is cool and makes their distro
> 	  special (eg KMS patches)

Right but all of the above are short lived except the packaging patches
(which are distro kernel specific), meaning they eventually go upstream.
You're proposing a permanent out of tree patch, which is counter to
this.

> Its starting to sound like the Foundation and someone have signed some
> kind of settlement to get this change into the Linux kernel regardless of
> the technical issues, practicality or community and this is all for show
> anyway.

This is getting a bit far into conspiracy theories even for you, but if
I must I can categorically deny this.  The involvement of the Linux
foundation in this area is threefold:

     1. Pulling together OIN, OSAPA and a few other patent projects into
        a workable patent shield around Linux.
     2. Specifically for TomTom, assisting with their patent defence by
        explaining open source to their lawyers and also putting them in
        touch with OIN.
     3. For this patch, since there are legal issues which could harm
        the defence of any company to be discussed openly, the LF is
        paying the retainer for John Lanza to be available to any member
        of the community on a one on one basis, so that the discussions
        they engage in would be protected by client privilege (i.e. not
        subject to discovery).

In my book that amounts to trying to mitigate some of the impacts of the
US patent system on open source and linux rather than conspiracy.  You
could also see the "undisclosed settlement" in the TomTom case, with
virtually no repercussions for Tom Tom shipping Linux, as a reasonable
success of the above strategy.

> > If the patch had significant negative consequences for normal use then
> 
> You said yourself it can crash XP.
> 
> > If we get some real examples of devices that are badly affected
> 
> XP crashing by suprise if you are really really unlucky strikes me as a
> good example and one you provided.

OK, so this is a legitimate technical concern ... somewhat mitigated by
the fact that a lot of other FAT32 implementations also crash XP.

> You've also ignored entirely the fact that this isn't a VFAT file system
> so irrespective of whether this goes in it should not be used for mount
> -o vfat.
> 
> There is a clear end user expectation that vfat means "microsoft fat with
> extended names". By all means add support for "not vfat" but don't call
> it "vfat" as that is misleading an interface breakage.

The Microsoft FAT32 standard only says files with long names *may* be
visible on 8.3 FAT systems, it doesn't say *shall*.  Therefore, my
reading is that this patch is fully compliant with the FAT32 standard,
and thus *is* definitely what we call vfat in Linux.  Or are you
claiming that we've somehow extended the definition of vfat to mean
complies with FAT32 + makes 8.3 names available as well?

James

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Theodore Tso]

On Thu, Jul 02, 2009 at 02:56:07PM +0000, James Bottomley wrote:
>      3. For this patch, since there are legal issues which could harm
>         the defence of any company to be discussed openly, the LF is
>         paying the retainer for John Lanza to be available to any member
>         of the community on a one on one basis, so that the discussions
>         they engage in would be protected by client privilege (i.e. not
>         subject to discovery).

I believe what has been made available is that people who have some
detailed legal questions can contact John Lanza who can either respond
off-line via e-mail, schedule time for a phone call, and if really
necessary, it _can_ be possible to establish a formal client/attorney
privilege with John.  These different options are listed in order of
increasing cost to the Linux Foundation.  

Which option gets chosen will depend on the specific question and who
is asking the question; which is to say, setting up a formal
client/attorney privilege might be more appropriate for Hirofumi or
Linus, but obviously the LF can't afford to set up relationships where
client privilege would apply for any random LKML reader who is
randomly curious about the way things work.

So just to make it clear, with respect to expectations, simply sending
e-mail to John doesn't automatically set up a client relationship that
which protects the discussion under client/attorney privilege.
Setting that up *does* cost LF real money, so I would ask folks to be
considerate about the LF's resources!

BTW, Tridge has offered to be available for phone conversations, since
he's probably asked the various lawyers that have been consulted most
of the questions that people might have; so that's another option for
people who have legal questions that would be kinder and gentler to
the LF's budget.

And of course, keep in mind that this offer is really only for people
who want to clarification of any background legal issues, not to
debate the issue of whether or not the patch should go in.  That
policy discussion should happen openly, like any other proposed patch,
and ultimately it's Hirofumi-san's and/or Linus's call.

						- Ted

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Alan Cox]

> but it seems fairly basic to me that if a patch is likely to be in use
> by the majority of Linux users (via distros/vendors) that having it in
> the upstream kernel makes sense. 
> 
> If I'm wrong and a large proportion of distros/vendors won't want this
> patch then of course the argument falls down, and in that case it

It's an open list so they can speak their minds here....

> would seem perfectly reasonable for the upstream kernel not to have
> it, or for it to be inactive by default.

You said yourself that the vendors would prefer to simply remove the code
which means they will carry the "unpatch" anyway.

> Other OSes (eg. Windows) don't tend to distinguish between FAT and
> VFAT. It is just a FAT filesystem with a varying range of features. On
> Linux we've chosen one particular set of features and labelled that
> VFAT, then we've chosen a different set of features and labelled it
> 'MSDOS'. Within what we have labelled as VFAT we have some existing
> runtime options that select different varients. I would have liked to
> do the 'dualnames' patch as a runtime option, but that doesn't satisfy
> the legal requirements.

That I don't believe for one minute providing the dualnames option (or -t
vfat) does not work in the non VFAT case.

That is

CONFIG_VFAT_DUALNAMES = y
	mount -t vfat		works
	mount -o dualnames=1    works
	mount -o tridgefat	works (gives you dualnames = 0)

CONFIG_VFAT_DUALNAMES = n
	mount -t vfat		fails
	mount -t vfat,-o dualnames=0 maybe works
	mount-o tridgefat	works

I can believe that shipping code supporting vfat dualnames and not using
the option at runtime would be a problem IFF the patent is shown to be
valid and software patents are valid in the USA. Thus for the problem
space you are worried about it needs to be compiled out. Given the GPL
says I can ask for the source to match the binaries I'm very very sure
any worried distro would go further and never ship that source either -
its lower risk/lower hassle.

Question for the lawyers: If the option is runtime but the case of
concern cannot be selected (viz support is not even compiled in is that a
problem. If not then -o dualnames= makes life much easier)

I have no problem with the idea of a compile time option for not doing
true VFAT so certain US people can provide it. I don't howeve believe
anyone will use it because they either

a) think it is a problem and have US issues in which case they will
remove the code entirely as that is the lowest risk option and with
little other internal inconvenience

b) they don't think it is a problem (the vast array of non-US
distributions from Ubuntu to Red Flag) and don't select it.

> end users think about the intricacies of what FAT filesystem options
> they want. Most systems just auto-mount removable media these days

That is precisely why it needs to not mount as vfat

> with whatever options the distro vendors choose (or via HAL rules).
> 
> Thus I don't think the "end user expectation" is a strong argument for
> making this an entirely new filesystem.

Its a name not a file system. As simple as

#ifdef CONFIG_FOO
	register vfat
#else
	register lfat
#endif


To my mind we need to be careful of three things

- Harming the kernel to work around a potentially country specific
  unproven problem for the benefit of a few big corporations only
- Getting into situations where big companies behind closed doors make
  unaccountable decisions about a project they do not own
- Setting trends for country specific fixups. There are a lot of
  countries and if we keep the US happy we have to keep China happy and
  so it goes on. Big corporations employ armies of specialists for these
  purposes and make the gain from it. The community doesn't so it should
  no more carry the pain of it than of long term stable releases and
  supporting five year old vendor kernels

So IMHO

	Put dualnames in by all means - but don't pretend it makes any
	difference on the QA front or concerned vendors would set the
	option - they won't, they'll go further.

	Don't make the non dualnames mode "vfat", it's not, and the very
	fact users are casual about assuming vfat/fat/windows compatible
	is why it is so important. (As an analogy most end users don't
	know that a 'CD' is specified by a pile of specs, they don't
	care. But they most definitely care if their CD won't play on
	everything).

And a question: Is there a trivial way to make tridge fat differentiable
from vfat/fat without Windows noticing. That way HAL can preserve the
type settings given a kernel that supports it.

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Alan Cox]

> As a linux maintainer, you know we try very hard to encourage vendors
> not to carry long lived out of tree patches because of the complexity it
> causes for everyone.

For the non kernel cases with patent questions this isn't the pattern you
see. And for good reasons. A US patent compliant version of mplayer is
probably a jpeg viewer. It would be very harmful to the rest of the world
to gut the main package in that case.

For the kernel case the reality is this

If we include no patch the people concerned will remove the code from
their distributed source tarball

If we include a config option, the people concerned will *STILL* remove
the code from their distributed source tarball.

so the debate about out of tree patches is not as relevant as might at
first seem obvious. The simple problem is that the GPL says if you give
me the binaries I can ask for the sources which produced them. If those
sources contain the source to an algorithm where there are claims of
possible patent problems then the lawyers will prefer to play as safe as
possible and pull the sources that concern them before they even permit
anyone to type "make". A quick look at some packages from big US
based vendors will show you that is happening all the time to pull out
stuff as varied as mp3 playing and the openssh decss crypto mode.

[Other bits cut, conspiracy case point noted and its why you should not
post to linux-kernel with a fever temperature ;) ]

> > There is a clear end user expectation that vfat means "microsoft fat with
> > extended names". By all means add support for "not vfat" but don't call
> > it "vfat" as that is misleading an interface breakage.
> 
> The Microsoft FAT32 standard only says files with long names *may* be
> visible on 8.3 FAT systems, it doesn't say *shall*.  Therefore, my
> reading is that this patch is fully compliant with the FAT32 standard,
> and thus *is* definitely what we call vfat in Linux.  Or are you
> claiming that we've somehow extended the definition of vfat to mean
> complies with FAT32 + makes 8.3 names available as well?

I'm simply of the viewpoint that users expect certain behaviours and
compatibilities and that therefore it would be best if the new filesystem
variant had a new name. I'm not saying cp -r fs/foo fs/bar, just a new
mount name.

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[James Bottomley]

On Thu, 2009-07-02 at 19:12 +0100, Alan Cox wrote:
> > As a linux maintainer, you know we try very hard to encourage vendors
> > not to carry long lived out of tree patches because of the complexity it
> > causes for everyone.
> 
> For the non kernel cases with patent questions this isn't the pattern you
> see. And for good reasons. A US patent compliant version of mplayer is
> probably a jpeg viewer. It would be very harmful to the rest of the world
> to gut the main package in that case.

I'd agree *if* we were gutting the package ... and for that reason I
believe not accepting the first incarnation of this patch, which
basically lost the ability to create long filenames was correct.

I think the loss of functionality with this patch is pretty minor so it
is worth carrying it in the kernel.  Obviously, this type of thing has
to be decided on a case by case basis, so there's no precedent (at least
as I see it) being set here.

> For the kernel case the reality is this
> 
> If we include no patch the people concerned will remove the code from
> their distributed source tarball
> 
> If we include a config option, the people concerned will *STILL* remove
> the code from their distributed source tarball.
> 
> so the debate about out of tree patches is not as relevant as might at
> first seem obvious. The simple problem is that the GPL says if you give
> me the binaries I can ask for the sources which produced them. If those
> sources contain the source to an algorithm where there are claims of
> possible patent problems then the lawyers will prefer to play as safe as
> possible and pull the sources that concern them before they even permit
> anyone to type "make". A quick look at some packages from big US
> based vendors will show you that is happening all the time to pull out
> stuff as varied as mp3 playing and the openssh decss crypto mode.

So the advice of our lawyers is that in the US infringement only comes
from practising the patent ... i.e. having a working implementation.
Just giving someone source code for a method to practise it isn't
sufficient ... after all, that's really what a patent specification is
supposed to be: source code in english sufficient to reduce the patent
to practice.

> [Other bits cut, conspiracy case point noted and its why you should not
> post to linux-kernel with a fever temperature ;) ]

Gosh, sorry to hear that ... I find hot honey lemon and brandy useful
for this ... in extreme cases, I just skip the honey and lemon.

> > > There is a clear end user expectation that vfat means "microsoft fat with
> > > extended names". By all means add support for "not vfat" but don't call
> > > it "vfat" as that is misleading an interface breakage.
> > 
> > The Microsoft FAT32 standard only says files with long names *may* be
> > visible on 8.3 FAT systems, it doesn't say *shall*.  Therefore, my
> > reading is that this patch is fully compliant with the FAT32 standard,
> > and thus *is* definitely what we call vfat in Linux.  Or are you
> > claiming that we've somehow extended the definition of vfat to mean
> > complies with FAT32 + makes 8.3 names available as well?
> 
> I'm simply of the viewpoint that users expect certain behaviours and
> compatibilities and that therefore it would be best if the new filesystem
> variant had a new name. I'm not saying cp -r fs/foo fs/bar, just a new
> mount name.

It's a plausible argument.  My counter argument is that in the US with
this patch applied and your fs name change, it would cause all vfat
mounts to have to change mount type ... this is really a massive
surprise to all USB key users here and smoothing it over in the distros
would end up being quite a bit of work.  So, I'd favour, on the
principle of least surprise, keeping the mount name vfat for what is a
compliant implementation of the FAT32 filesystem, albeit missing one
small piece of functionality we previously had.

James

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Pavel Machek]

On Wed 2009-07-01 20:19:51, Rusty Russell wrote:
> On Tue, 30 Jun 2009 04:01:03 pm Pavel Machek wrote:
> > > +config VFAT_FS_DUALNAMES
> > > +	bool "VFAT dual names support"
> > > +	depends on VFAT_FS
> >
> > Defaults should be back-compatible.
> 
> Hi Pavel,
> 
> I disagree with this: given there's been testing with no known issues, it's 
> not a back compat question.

The testing uncovered some pretty serious issues. ('Causes XP to
bluescreen').
									Pavel

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

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Pavel Machek]

> > Ultimately, though, requiring that every single possible device be
> > tested is probably not reasonable, so the best way to do this testing
> > is the way do most of our testing; we do basic due diligence, but then
> > we merge it into mainline and let our huge user community try it out.
> > If there are regressions we can work through those issues if and when
> > they arise.
> 
> From the funnies we've had in the past with FAT my gut impression is
> there are only a few implementations out there. Psion seems to have their
> own but most of the rest behave remarkably similarly which makes me
> suspect they all licensed a tiny number of implementations (DRDOS one
> perhaps ?). If we can keep most of those devices mounted 8.3 we nicely
> sidestep the issue anyway.

I'm pretty sure there's more. There's stuff such as 'make your own mp3
player with pic and few more circuits'. I'd actually expect many mp3
players to be affected by this; many are really cheap & nasty.

								Pavel

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

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Pavel Machek]

Hi!

>  > Defaults should be back-compatible.
> 
> I would usually agree, but I think we have an unusual situation here,
> in some ways similar to a demonstrated security hole. The previous
> behaviour exposed a lot of Linux vendors to the possibility of an
> expensive legal fight.

I'd actually like to see all-out software patent war in the U.S. It
would make sure that software patents do not spread to the rest of
world. Bad for U.S.? Yes. Good for world? Yes!

>  > Users considering disabling this should understand that filesystem
>  > they write to will not be valid vfat filesystems, and may trigger bugs
>  > in some devices.
> 
> If we find any devices that exhibit any problems with this patch while
> it is in linux-next (and maybe linux-mm?) then this warning would
> indeed be appropriate. It no such devices are known then I think the
> warning is going a bit far. 

You already know that it breaks XP and older linuxes. So... what are
you arguing about?! Chkdsk marks it as invalid filesystem... not a
vfat.

If mickey$oft intentionally modified windows 8 to intentionally corrupt
ext3 filesystems so that linux oopses on accessing them, how'd you
like that?

>  > Why not use something like position in directory instead of random
>  > number?
> 
> We did of course consider that, and the changes to the patch to
> implement collision avoidance are relatively simple. We didn't do it
> as it would weaken the legal basis behind the patch. I'll leave it to

Consider it again. Or put fair 'this makes XP crash' warning in
kconfig.

								Pavel
PS: I find it bad that original patch description did not contain XP
crashing / chkdsk explanation.
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Pavel Machek]

On Wed 2009-07-01 10:44:47, James Bottomley wrote:
> On Wed, 2009-07-01 at 14:48 +0300, Boaz Harrosh wrote:
> > On 07/01/2009 01:50 PM, tridge@samba.org wrote:
> > > Hi Pavel,
> > > 
> > > We did of course consider that, and the changes to the patch to
> > > implement collision avoidance are relatively simple. We didn't do it
> > > as it would weaken the legal basis behind the patch. I'll leave it to
> > > John Lanza (the LF patent attorney) to expand on that if you want more
> > > information.
> > > 
> > 
> > You completely lost me here. And I thought I did understand the patent
> > and the fix.
> > 
> > what is the difference between.
> > 
> > short_name = rand(sid);
> > and
> > short_name = sid++;
> > 
> > Now if you would do
> > short_name = MD5(long_name);
> > 
> > That I understand since short_name is some function of long_name
> > but if I'm just inventing the short_name out of my hat. In what legal
> > system does it matter what is my random function I use?
> 
> We're sort of arguing moot technicalities here.  If you look at the way
> the filename is constructed, given the constraints of a leading space
> and a NULL, the need for a NULL padded leading slash extension and the
> need to put control characters in the remaining bytes, we've only got 30
> bits to play with, we're never going to avoid collisions in a space of
> up to 31 bits.  Technically, a random function is at least as good at
> collision avoidance as any deterministic solution ... and it's a lot
> easier to code.

You could be deterministic and restrict maximum number of entries in
directory?

You could do random function but check if duplicate exists, and return
-EPERM if it does?

								Pavel 

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

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Pavel,

 > > I disagree with this: given there's been testing with no known issues, it's 
 > > not a back compat question.
 > 
 > The testing uncovered some pretty serious issues. ('Causes XP to
 > bluescreen').

no, that's not quite correct. I have never been able to produce a
bluescreen with the patch I have posted.

I did manage to produce a bluescreen with a different patch that
deliberately lowers the number of bits of randomness used (ie. just
change the mask to random32() in vfat_build_dummy_83_buffer()). Even
then, producing a bluescreen is not trivial, though it is definately
possible.

As I explained in a previous posting, the WindowsXP bug doesn't happen
just because two 8.3 entries have the same 11 bytes. There are
additional strong constraints on the access patterns by the WindowsXP
kernel before the bluescreen happens. I reproduced it by running 4
processes in parallel doing massive numbers of random file operations,
with a controlling script transferring control of the USB key between
the WindowsXP box and a Linux host every minute (so both are doing
random file operations).

Even with that, if I had even a few bits of randomness then it took a
lot of testing (often hours) to produce the bluescreen. I wouldn't
have even known the problem was possible if I hadn't been
experimenting with patch varients where all the bytes are always the
same (such as the 11 spaces varient I mentioned). With those varients
(where there is no randomness at all), you can produce a bluescreen
with a bit of effort on the DOS command line.

So I hope you can see why I don't think this is a particularly large
problem, especially given that the WindowsXP FAT driver is notoriously
prone to crashing, as a quick google search will show you.

If someone can actually demonstrate the bluescreen with the patch I've
posted in some access pattern that is at all likely to be made by a
WindowsXP user then I would be more concerned. As it is, I don't think
we should hold off on this patch for what amounts to a theoretical
issue.

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Pavel,

 > You already know that it breaks XP and older linuxes. So... what are
 > you arguing about?! Chkdsk marks it as invalid filesystem... not a
 > vfat.

no, wrong on all 3 counts.

For the "breaks XP", see my previous message where I point out that I
have never been able to crash XP with this patch, only with other
varients on the patch that reduce the number of random bits we use.

The "breaks older linuxes" claim is also wrong. The patch I have
posted works fine with all older versions of the Linux kernel that I
have tested. If you know of a old version of the Linux kernel that
doesn't work with a filesystem written when this patch is enabled then
please let me know. I think you may be getting confused by the
discussion I had with Eric where I explained about the reasons for the
change in fat/dir.c. I won't repeat that long discussion again here,
but please re-read the reply I sent to Eric and if you still have
questions about it then please ask.

Finally, saying that "chkdsk marks it as an invalid filesystem" is not
correct. It only complains if there happens (with a very low
probability!) to be two files with the same 11 bytes in their
respective 8.3 entries. When it complains it renames one of the two
files.

That rename would not in itself be a problem at all, as changing the
8.3 entry would not affect the long filename, except that chkdsk has a
bug where it doesn't follow the Microsoft FAT specification. When you
rename a file on a FAT filesystem you are supposed to also update the
8 bit checksum field in the corresponding long filename entries. If
you don't do that update then you effectively strip off the long
filename. Current versions of Microsoft chkdsk neglect to update the
long filename checksum when renaming after detecting a duplicate 8.3
entry.

So it is Microsoft's chkdsk, not the patched Linux kernel, that is in
violation of the FAT spec. Luckily the probability of this bug
cropping up is quite small in practice.

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Pavel Machek]

On Fri 2009-07-03 08:06:54, tridge@samba.org wrote:
> Hi Pavel,
> 
>  > > I disagree with this: given there's been testing with no known issues, it's 
>  > > not a back compat question.
>  > 
>  > The testing uncovered some pretty serious issues. ('Causes XP to
>  > bluescreen').
> 
> no, that's not quite correct. I have never been able to produce a
> bluescreen with the patch I have posted.

So you know it causes XP to bluescreen, but can not reproduce that. So
what? Someone, somewhere _will_ reproduce it.
										Pavel
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Pavel,

 > So you know it causes XP to bluescreen, but can not reproduce that. So
 > what? Someone, somewhere _will_ reproduce it.

yes, like someone, somewhere will get data corruption in a TCP
connection because the checksum is quite weak and networking hardware
ain't perfect. 

Once the probabilties become small enough then it is normal to accept
imperfection in operating systems. If I could make it perfect I would,
but I haven't thought of a way to do that while being absolutely sure
of maintaining the full strength of the legal defence.

If you find a way to actually produce this problem in a way that is
realistic for Linux users then let me know. Otherwise I think it is
the best option we have, imperfect though it is. 

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Pavel Machek]

On Fri 2009-07-03 08:23:34, tridge@samba.org wrote:
> Hi Pavel,
> 
>  > You already know that it breaks XP and older linuxes. So... what are
>  > you arguing about?! Chkdsk marks it as invalid filesystem... not a
>  > vfat.
> 
> no, wrong on all 3 counts.
> 
> For the "breaks XP", see my previous message where I point out that I
> have never been able to crash XP with this patch, only with other
> varients on the patch that reduce the number of random bits we use.

...where you point out that probability of breakage is not too
high. But ammount of XP machines out there _is_ quite high, so someone
will hit it. You are deliberately breaking XP.

> The "breaks older linuxes" claim is also wrong. The patch I have
> posted works fine with all older versions of the Linux kernel that I
> have tested. If you know of a old version of the Linux kernel that
> doesn't work with a filesystem written when this patch is enabled then
> please let me know. I think you may be getting confused by the
> discussion I had with Eric where I explained about the reasons for the
> change in fat/dir.c. I won't repeat that long discussion again here,
> but please re-read the reply I sent to Eric and if you still have
> questions about it then please ask.

Ok, I guess I misunderstood. So what is the reason for pushing stable patch?

> Finally, saying that "chkdsk marks it as an invalid filesystem" is not
> correct. It only complains if there happens (with a very low
> probability!) to be two files with the same 11 bytes in their
> respective 8.3 entries. When it complains it renames one of the two
> files.

The "very low probability" is 50% for 30000 entries in directory,
AFAICT.

> That rename would not in itself be a problem at all, as changing the
> 8.3 entry would not affect the long filename, except that chkdsk has a
> bug where it doesn't follow the Microsoft FAT specification. When

Yeah, when map and reality disagree, trust the map. Not.

I don't care what M$ spec says, and you should not care, either. It is
M$ chkdsk that matters, and M$ VFAT implementation that matters.

> So it is Microsoft's chkdsk, not the patched Linux kernel, that is in
> violation of the FAT spec. Luckily the probability of this bug
> cropping up is quite small in practice.

Yes, explain that to the people. Actually, write it to the Kconfig.
"Turn this option ON to show bugs in M$ chkdsk". 

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

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Pavel Machek]

On Fri 2009-07-03 08:41:13, tridge@samba.org wrote:
> Hi Pavel,
> 
>  > So you know it causes XP to bluescreen, but can not reproduce that. So
>  > what? Someone, somewhere _will_ reproduce it.
> 
> yes, like someone, somewhere will get data corruption in a TCP
> connection because the checksum is quite weak and networking hardware
> ain't perfect.

That's why we have ethernet checksums. 

> Once the probabilties become small enough then it is normal to accept
> imperfection in operating systems. If I could make it perfect I
> but I haven't thought of a way to do that while being absolutely sure
> of maintaining the full strength of the legal defence.

It already _was_ perfect before you started patching it.

> If you find a way to actually produce this problem in a way that is
> realistic for Linux users then let me know. Otherwise I think it is
> the best option we have, imperfect though it is. 

So, you know that particular option will cause someone's XP to
bluescreen, and  you still want it to default to "Y"?
											Pavel
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Rusty Russell]

On Fri, 3 Jul 2009 07:16:46 am Pavel Machek wrote:
> On Wed 2009-07-01 20:19:51, Rusty Russell wrote:
> > On Tue, 30 Jun 2009 04:01:03 pm Pavel Machek wrote:
> > > > +config VFAT_FS_DUALNAMES
> > > > +	bool "VFAT dual names support"
> > > > +	depends on VFAT_FS
> > >
> > > Defaults should be back-compatible.
> >
> > Hi Pavel,
> >
> > I disagree with this: given there's been testing with no known issues,
> > it's not a back compat question.
>
> The testing uncovered some pretty serious issues. ('Causes XP to
> bluescreen').

No, read more carefully: testing revealed "couldn't cause XP to bluescreen".  
It took a deliberately hobbled version of the patch to tickle the XP bug, 
under a day of stress testing.

Cheers,
Rusty.

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Pavel,

 > That's why we have ethernet checksums. 

which of course just changes the number of bits. The argument remains
the same. 

 > It already _was_ perfect before you started patching it.

wow, I really didn't expect the objection to my patch to be that VFAT
is perfect!

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Rusty Russell]

On Fri, 3 Jul 2009 08:14:46 am Pavel Machek wrote:
> On Fri 2009-07-03 08:41:13, tridge@samba.org wrote:
> > If you find a way to actually produce this problem in a way that is
> > realistic for Linux users then let me know. Otherwise I think it is
> > the best option we have, imperfect though it is.
>
> So, you know that particular option will cause someone's XP to
> bluescreen, and  you still want it to default to "Y"?

No, his point is the opposite: the rate of incidence of bluescreens on XP will 
not measurably increase due to this patch.

Cheers,
Rusty.

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[OGAWA Hirofumi]

Alan Cox <alan@lxorguk.ukuu.org.uk> writes:

> To my mind we need to be careful of three things
>
> - Harming the kernel to work around a potentially country specific
>   unproven problem for the benefit of a few big corporations only

My choice is to provide the option of those to users. I'm not saying to
ripping out the code for some users.

> - Getting into situations where big companies behind closed doors make
>   unaccountable decisions about a project they do not own

Now, I'm not working for any companies. I can say there is no closed
doors for me.

> - Setting trends for country specific fixups. There are a lot of
>   countries and if we keep the US happy we have to keep China happy and
>   so it goes on. Big corporations employ armies of specialists for these
>   purposes and make the gain from it. The community doesn't so it should
>   no more carry the pain of it than of long term stable releases and
>   supporting five year old vendor kernels

I'm just thinking about users. If vendors shipped the buggy code like
first buggy patch, I just thought it's more bad for our users. That's
all.

If there is community decision, I'll be really glad to follow it.

Thanks.
-- 
OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Jamie Lokier]

Alan Cox wrote:
> From the funnies we've had in the past with FAT my gut impression is
> there are only a few implementations out there. Psion seems to have their
> own but most of the rest behave remarkably similarly which makes me
> suspect they all licensed a tiny number of implementations (DRDOS one
> perhaps ?). If we can keep most of those devices mounted 8.3 we nicely
> sidestep the issue anyway.

>From recently witnessing someone write another FAT implementation, for
an 8-bit AVR microcontroller reading SD cards, based in part on
someone elses public domain FAT implementation, fixing significant
bugs in that (including directory parsing), and then seeing it
translated from C to hand-coded AVR assembly language to save space,
with me helping teach C to the person doing it, for a commercial
product which is to be released in the next couple of months, and will
be updated with SD cards written by Linux and Windows...

>From witnessing that, for one obscure product among millions, I'd
guess there are more FAT implementations than a "few".  Perhaps there
aren't many VFAT implementations, but my gut says there are quite a
lot of independently written 8.3-only FAT ones.

-- Jamie

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Jamie Lokier]

James Bottomley wrote:
> On Wed, 2009-07-01 at 14:48 +0300, Boaz Harrosh wrote:
> > On 07/01/2009 01:50 PM, tridge@samba.org wrote:
> > > Hi Pavel,
> > > 
> > > We did of course consider that, and the changes to the patch to
> > > implement collision avoidance are relatively simple. We didn't do it
> > > as it would weaken the legal basis behind the patch. I'll leave it to
> > > John Lanza (the LF patent attorney) to expand on that if you want more
> > > information.
> > > 
> > 
> > You completely lost me here. And I thought I did understand the patent
> > and the fix.
> > 
> > what is the difference between.
> > 
> > short_name = rand(sid);
> > and
> > short_name = sid++;
> > 
> > Now if you would do
> > short_name = MD5(long_name);
> > 
> > That I understand since short_name is some function of long_name
> > but if I'm just inventing the short_name out of my hat. In what legal
> > system does it matter what is my random function I use?
> 
> We're sort of arguing moot technicalities here.  If you look at the way
> the filename is constructed, given the constraints of a leading space
> and a NULL, the need for a NULL padded leading slash extension and the
> need to put control characters in the remaining bytes, we've only got 30
> bits to play with, we're never going to avoid collisions in a space of
> up to 31 bits.

> Technically, a random function is at least as good at
> collision avoidance as any deterministic solution ...

No, it isn't.

A deterministic value based on position in the directory, or by
checking for collisions and avoiding them, will _never_ collide,
provided you limit directories to no more than 2^30 entries, which is
reasonable for FAT.

Whereas a random value can collide.
That's a fundamental technical difference.

A quick read of the Birthday Problem page on Wikipedia leads to:

    With a directory of 1000 files, not especially rare with a camera
    or MP3 players, and 30-bit random numbers:

    The probably of a collision is 0.04% [1]

    If 10000 people each have a directory of 1000 files (not
    unreasonable given the huge number of people who use FAT media),
    the probability that any of them have a collision is approximately
    100%.

    
[1] perl -e '$d = 2.0**30; $n = 1000; $x = 1; for $k (1..$n-1) { $x *= (1 - $k/$d); } printf "Probability = %f%%\n", 100*(1-$x);'

In other words, using random values you are _guaranteeing_ collisions
for a few users.

So the argument comes down to: Does it matter if there are collisions?

Tridge's testing didn't blue screen Windows XP.
Tridge's testing did run a lot of operaitons.

But Tridge isn't 10000 people doing crazy diverse things with
different devices in all sorts of systematic but different patterns
over a period of years.

Given it's technically trivial to avoid collisions completely, and
there is some risk of breakage, even though it would be rare, there
had better be a good reason for not doing it.

-- Jamie

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Boaz Harrosh]

On 07/06/2009 11:41 PM, Jamie Lokier wrote:
> James Bottomley wrote:
>> On Wed, 2009-07-01 at 14:48 +0300, Boaz Harrosh wrote:
>>> On 07/01/2009 01:50 PM, tridge@samba.org wrote:
>>>> Hi Pavel,
>>>>
>>>> We did of course consider that, and the changes to the patch to
>>>> implement collision avoidance are relatively simple. We didn't do it
>>>> as it would weaken the legal basis behind the patch. I'll leave it to
>>>> John Lanza (the LF patent attorney) to expand on that if you want more
>>>> information.
>>>>
>>> You completely lost me here. And I thought I did understand the patent
>>> and the fix.
>>>
>>> what is the difference between.
>>>
>>> short_name = rand(sid);
>>> and
>>> short_name = sid++;
>>>
>>> Now if you would do
>>> short_name = MD5(long_name);
>>>
>>> That I understand since short_name is some function of long_name
>>> but if I'm just inventing the short_name out of my hat. In what legal
>>> system does it matter what is my random function I use?
>> We're sort of arguing moot technicalities here.  If you look at the way
>> the filename is constructed, given the constraints of a leading space
>> and a NULL, the need for a NULL padded leading slash extension and the
>> need to put control characters in the remaining bytes, we've only got 30
>> bits to play with, we're never going to avoid collisions in a space of
>> up to 31 bits.
> 
>> Technically, a random function is at least as good at
>> collision avoidance as any deterministic solution ...
> 
> No, it isn't.
> 
> A deterministic value based on position in the directory, or by
> checking for collisions and avoiding them, will _never_ collide,
> provided you limit directories to no more than 2^30 entries, which is

Exactly this is the key, find the real limit and enforce it.

> reasonable for FAT.
> 
> Whereas a random value can collide.
> That's a fundamental technical difference.
> 
> A quick read of the Birthday Problem page on Wikipedia leads to:
> 
>     With a directory of 1000 files, not especially rare with a camera
>     or MP3 players, and 30-bit random numbers:
> 
>     The probably of a collision is 0.04% [1]
> 
>     If 10000 people each have a directory of 1000 files (not
>     unreasonable given the huge number of people who use FAT media),
>     the probability that any of them have a collision is approximately
>     100%.
> 
>     
> [1] perl -e '$d = 2.0**30; $n = 1000; $x = 1; for $k (1..$n-1) { $x *= (1 - $k/$d); } printf "Probability = %f%%\n", 100*(1-$x);'
> 
> In other words, using random values you are _guaranteeing_ collisions
> for a few users.
> 

Thanks, I thought it was just me.

> So the argument comes down to: Does it matter if there are collisions?
> 
> Tridge's testing didn't blue screen Windows XP.
> Tridge's testing did run a lot of operaitons.
> 
> But Tridge isn't 10000 people doing crazy diverse things with
> different devices in all sorts of systematic but different patterns
> over a period of years.
> 

What? you say there are 10,000 people with cameras that are using Linux
in the world ;-)

> Given it's technically trivial to avoid collisions completely, and
> there is some risk of breakage, even though it would be rare, there
> had better be a good reason for not doing it.
> 

I wish the lawyers people would come forward, as promised,,and explain what
are the constraints on the short_name, given a long_name is present.
I'm still waiting for that private mail in my e-box. If the names do not
correspond at all but are both valid, why is that a problem?

> -- Jamie

Thanks
Boaz

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Jamie Lokier]

Boaz Harrosh wrote:
> I wish the lawyers people would come forward, as promised,,and explain what
> are the constraints on the short_name, given a long_name is present.
> I'm still waiting for that private mail in my e-box. If the names do not
> correspond at all but are both valid, why is that a problem?

To be fair Tridge said there is a reason.

The only problem is we don't know what it is...

-- Jamie

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Boaz Harrosh]

On 07/07/2009 02:25 PM, Jamie Lokier wrote:
> Boaz Harrosh wrote:
>> I wish the lawyers people would come forward, as promised,,and explain what
>> are the constraints on the short_name, given a long_name is present.
>> I'm still waiting for that private mail in my e-box. If the names do not
>> correspond at all but are both valid, why is that a problem?
> 
> To be fair Tridge said there is a reason.
> 
> The only problem is we don't know what it is...
> 

He also said someone will answer this in a private e-mail, I'm still
waiting.

> -- Jamie

Boaz

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

Hi Boaz,

 > He also said someone will answer this in a private e-mail, I'm still
 > waiting.

My apologies, I assumed John had sent you something.

John, can you please look at this?

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Pavel Machek]

On Fri 2009-07-03 09:59:35, tridge@samba.org wrote:
> Hi Pavel,
> 
>  > That's why we have ethernet checksums. 
> 
> which of course just changes the number of bits. The argument remains
> the same. 

Ok, so what is your estimate of XP crash probability?

>  > It already _was_ perfect before you started patching it.
> 
> wow, I really didn't expect the objection to my patch to be that VFAT
> is perfect!

But ... it was, and there is still possibility of just using position
in directory to avoid collisions completely.
									Pavel
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Paul E. McKenney]

On Wed, Jul 08, 2009 at 11:21:33AM +0200, Pavel Machek wrote:
> On Fri 2009-07-03 09:59:35, tridge@samba.org wrote:
> > Hi Pavel,
> > 
> >  > That's why we have ethernet checksums. 
> > 
> > which of course just changes the number of bits. The argument remains
> > the same. 
> 
> Ok, so what is your estimate of XP crash probability?

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	3.934446601778345b-1	(39.3%)
16384	1.174969255061134b-1	(11.7%)
 8192	3.076314519945223b-2	( 3.1%)
 4096	7.780179085651447b-3	( 0.8%)
 2048	1.950268317016874b-3	( 0.2%)
 1024	4.87685610530225b-4	(1 in 2,000)
  512	1.218244920604881b-4	(1 in 8,000)
  256	3.039790922077076b-5	(1 in 30,000)
  128	7.569761535306629b-6	(1 in 100,000)
   64	1.877544584847826b-6	(1 in 500,000)
   32	4.61935894834079b-7	(1 in 2,000,000)
   16	1.117587032466174b-7	(1 in 9,000,000)
    8	2.607703180994292b-8	(1 in 38,000,000)
    4	5.587935438151892b-9	(1 in 180,000,000)
    2	9.313225746154785b-10	(1 in 1,000,000,000)
    1	0.0b0

The number of files that people keep in a given directory will vary,
but in my admittedly limited experience, most people tend towards the
low end of this range.  What number of files per directory do you see
on embedded-device memory sticks?

Furthermore, this assumes that the user actually opens each and every file
in the directory.  If the user keeps (say) 1024 files in the directory,
but only opens two of them on any given memory-stick insertion, then
the odds are one in a billion rather than one in two thousand.

[Tridge -- isn't this only for subdirectories?  Or can collisions in
the root directory also result in WinXP bluescreens?]

> >  > It already _was_ perfect before you started patching it.
> > 
> > wow, I really didn't expect the objection to my patch to be that VFAT
> > is perfect!
> 
> But ... it was, and there is still possibility of just using position
> in directory to avoid collisions completely.

Almost.  The imperfection comes from the fact that storage media are not
totally reliable, so that given enough uses of large enough numbers of
memory sticks, there will eventually be a WinXP bluescreen.  Please note
that people really have reported this WinXP bug.

							Thanx, Paul

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

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.  I don't have any information on
	whether WinXP has a limited memory for recently open files.
	I therefore assume the worst case, namely that WinXP remembers
	every file that it has opened.

o	As noted in this thread, the probability of bluescreen is
	given by the infamous Birthday Paradox:

		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, so the
	probability of WinXP bluescreen is 1-P(n,m).

	Because I don't want to worry about round-off error, I use the
	arbitrary-precision arithmetic in the "maxima" symbolic-math
	package, which is related to the fabled Macsyma project.  However,
	computing the factorials without cancellation takes too long,
	so we transform the factorials into the binomial function, which
	has a highly optimized maxima implementation.  The equivalent
	but more efficient representation is as follows:

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

	Then 1-b(32^6,32767) gives the exact probability of bluescreen
	on a maximal-sized directory, which is the ratio of a pair of
	extremely large integers.  More usefully, bfloat(1-b(32^6,32767))
	gives an approximation in scientific notation.  (Don't forget
	the trailing semicolon that maxima requires.)

	Computing bfloat(1-b(32^6,32767)) takes about 70 seconds on my
	2GHz x86 laptop.

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

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

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) bfloat(1-b(32^6,32767));
(%o2)                        3.934446601778345b-1
(%i3) bfloat(1-b(32^6,2^14));
(%o3)                        1.174969255061134b-1
(%i4) bfloat(1-b(32^6,2^13));
(%o4)                        3.076314519945223b-2
(%i5) bfloat(1-b(32^6,2^12));
(%o5)                        7.780179085651447b-3
(%i6) bfloat(1-b(32^6,2^11));
(%o6)                        1.950268317016874b-3
(%i7) bfloat(1-b(32^6,2^10));
(%o7)                         4.87685610530225b-4
(%i8) bfloat(1-b(32^6,2^9));
(%o8)                        1.218244920604881b-4
(%i9) bfloat(1-b(32^6,2^8));
(%o9)                        3.039790922077076b-5
(%i10) bfloat(1-b(32^6,2^7));
(%o10)                       7.569761535306629b-6
(%i11) bfloat(1-b(32^6,2^6));
(%o11)                       1.877544584847826b-6
(%i12) bfloat(1-b(32^6,2^));
Incorrect syntax: Illegal use of delimiter )
bfloat(1-b(32^6,2^)
                 ^
(%i12) bfloat(1-b(32^6,2^5));
(%o12)                        4.61935894834079b-7
(%i13) bfloat(1-b(32^6,2^4));
(%o13)                       1.117587032466174b-7
(%i14) bfloat(1-b(32^6,2^3));
(%o14)                       2.607703180994292b-8
(%i15) bfloat(1-b(32^6,2^2));
(%o15)                       5.587935438151892b-9
(%i16) bfloat(1-b(32^6,2^1));
(%o16)                       9.313225746154785b-10
(%i17) bfloat(1-b(32^6,2^0));
(%o17)                               0.0b0
(%i18)

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[H. Peter Anvin]

Pavel Machek wrote:
> 
> But ... it was, and there is still possibility of just using position
> in directory to avoid collisions completely.

I was just going to ask this.  Rather than using a random number, we
should use something based on the position in the directory, and I
suspect we should still verify that it is unique (since some FAT
implementation may garbage-collect the directory thereby moving the offset.)

	-hpa

-- 
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[tridge]

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).

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

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.

Cheers, Tridge

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Paul E. McKenney]

On Thu, Jul 09, 2009 at 07:42:27AM +1000, tridge@samba.org 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!!!)

							Thanx, Paul

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[Paul E. McKenney]

[-- Attachment #1: Type: text/plain, Size: 7283 bytes --]

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@samba.org 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 #2: WinXPmodel.eps --]
[-- Type: application/postscript, Size: 8861 bytes --]

Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option

[John Lanza]

I apologize to those of you who have already gotten this email.  I am
resending because I just learned the mailing list has been rejecting
my emails beacuse they are in HTML format.

johnl

On Wed, Jul 8, 2009 at 11:14 PM, John Lanza<jdlanza@gmail.com> wrote:
> All:
>
> I apologize for the lack of responsiveness on my part over the past couple
> of days.  Although I checked in dutifully over the weekend, most of Monday
> and Tuesday were consumed with a project.
>
> At this point, though, I have reached out to certain members of this
> community and provided at least an initial explanation.  I am willing to do
> the same for anyone interested -- simply reply back to this email and let me
> know of your interest.
>
> johnl
>
> On Tue, Jul 7, 2009 at 7:25 AM, Jamie Lokier <jamie@shareable.org> wrote:
>>
>> Boaz Harrosh wrote:
>> > I wish the lawyers people would come forward, as promised,,and explain
>> > what
>> > are the constraints on the short_name, given a long_name is present.
>> > I'm still waiting for that private mail in my e-box. If the names do not
>> > correspond at all but are both valid, why is that a problem?
>>
>> To be fair Tridge said there is a reason.
>>
>> The only problem is we don't know what it is...
>>
>> -- Jamie
>
>
--
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html