[PATCH] fs/ntfs3: Fix logic in ntfs_cmp_names_cpu

[PATCH] fs/ntfs3: Fix logic in ntfs_cmp_names_cpu

[Mark Harmstone]

I'm not quite sure what was intended by the logic in ntfs_cmp_names_cpu,
but it was broken when comparing case-insensitively. If the strings
matched but differ in case, diff1 would be non-zero, meaning that the
function would always return a non-zero value.

Signed-off-by: Mark Harmstone <mark@harmstone.com>
---
 fs/ntfs3/upcase.c | 18 ++++++++----------
 1 file changed, 8 insertions(+), 10 deletions(-)

diff --git a/fs/ntfs3/upcase.c b/fs/ntfs3/upcase.c
index b5e8256fd710..dd28c2133a4c 100644
--- a/fs/ntfs3/upcase.c
+++ b/fs/ntfs3/upcase.c
@@ -74,31 +74,29 @@ int ntfs_cmp_names_cpu(const struct cpu_str *uni1, const struct le_str *uni2,
 	size_t l1 = uni1->len;
 	size_t l2 = uni2->len;
 	size_t len = min(l1, l2);
-	int diff1 = 0;
-	int diff2;
+	int diff;
 
 	if (!bothcase && upcase)
 		goto case_insentive;
 
 	for (; len; s1++, s2++, len--) {
-		diff1 = *s1 - le16_to_cpu(*s2);
-		if (diff1) {
+		diff = *s1 - le16_to_cpu(*s2);
+		if (diff) {
 			if (bothcase && upcase)
 				goto case_insentive;
 
-			return diff1;
+			return diff;
 		}
 	}
 	return l1 - l2;
 
 case_insentive:
 	for (; len; s1++, s2++, len--) {
-		diff2 = upcase_unicode_char(upcase, *s1) -
+		diff = upcase_unicode_char(upcase, *s1) -
 			upcase_unicode_char(upcase, le16_to_cpu(*s2));
-		if (diff2)
-			return diff2;
+		if (diff)
+			return diff;
 	}
 
-	diff2 = l1 - l2;
-	return diff2 ? diff2 : diff1;
+	return l1 - l2;
 }
-- 
2.31.1

Re: [PATCH] fs/ntfs3: Fix logic in ntfs_cmp_names_cpu

[Kari Argillander]

On Tue, Sep 28, 2021 at 07:33:00PM +0100, Mark Harmstone wrote:
> I'm not quite sure what was intended by the logic in ntfs_cmp_names_cpu,
> but it was broken when comparing case-insensitively. If the strings
> matched but differ in case, diff1 would be non-zero, meaning that the
> function would always return a non-zero value.

Original idea can be found in here [1]. So recap. If we need first check
lower case and then upcase we can actually do this in just one time. We
first find first mismatch. Then we in that point on try to find if we
find another mismatch when upcasing. This way only one compare round is
needed in worst case.

I will look this patch more closly soon.

[1]: https://lore.kernel.org/all/20210103231755.bcmyalz3maq4ama2@kari-VirtualBox/

> 
> Signed-off-by: Mark Harmstone <mark@harmstone.com>
> ---
>  fs/ntfs3/upcase.c | 18 ++++++++----------
>  1 file changed, 8 insertions(+), 10 deletions(-)
> 
> diff --git a/fs/ntfs3/upcase.c b/fs/ntfs3/upcase.c
> index b5e8256fd710..dd28c2133a4c 100644
> --- a/fs/ntfs3/upcase.c
> +++ b/fs/ntfs3/upcase.c
> @@ -74,31 +74,29 @@ int ntfs_cmp_names_cpu(const struct cpu_str *uni1, const struct le_str *uni2,
>  	size_t l1 = uni1->len;
>  	size_t l2 = uni2->len;
>  	size_t len = min(l1, l2);
> -	int diff1 = 0;
> -	int diff2;
> +	int diff;
>  
>  	if (!bothcase && upcase)
>  		goto case_insentive;
>  
>  	for (; len; s1++, s2++, len--) {
> -		diff1 = *s1 - le16_to_cpu(*s2);
> -		if (diff1) {
> +		diff = *s1 - le16_to_cpu(*s2);
> +		if (diff) {
>  			if (bothcase && upcase)
>  				goto case_insentive;
>  
> -			return diff1;
> +			return diff;
>  		}
>  	}
>  	return l1 - l2;
>  
>  case_insentive:
>  	for (; len; s1++, s2++, len--) {
> -		diff2 = upcase_unicode_char(upcase, *s1) -
> +		diff = upcase_unicode_char(upcase, *s1) -
>  			upcase_unicode_char(upcase, le16_to_cpu(*s2));
> -		if (diff2)
> -			return diff2;
> +		if (diff)
> +			return diff;
>  	}
>  
> -	diff2 = l1 - l2;
> -	return diff2 ? diff2 : diff1;
> +	return l1 - l2;
>  }
> -- 
> 2.31.1
> 
> 

Re: [PATCH] fs/ntfs3: Fix logic in ntfs_cmp_names_cpu

[Kari Argillander]

On Tue, Sep 28, 2021 at 07:33:00PM +0100, Mark Harmstone wrote:
> I'm not quite sure what was intended by the logic in ntfs_cmp_names_cpu,
> but it was broken when comparing case-insensitively. If the strings
> matched but differ in case, diff1 would be non-zero, meaning that the
> function would always return a non-zero value.

So I have checked this now. Yes function will always return non-zero
value if we use bothcase and this is intended behavier. But if 
bothcase is false and upcase is not NULL then function can return zero
value.

Do you have some problems? There could be that in some place this or
other cmp function is called with wrong parameters. Example with
bothcase true when only case_insentive is needed. 

I admit that this was not clenest way of implementing this. Maybe we
should make bothcase enum with three values. Example CASE_SENSITIVE,
CASE_INSENTIVE, CASE_BOTH. I do not like name BOTH so if anyone know
any better please tell.

  Argillander
> 
> Signed-off-by: Mark Harmstone <mark@harmstone.com>
> ---
>  fs/ntfs3/upcase.c | 18 ++++++++----------
>  1 file changed, 8 insertions(+), 10 deletions(-)
> 
> diff --git a/fs/ntfs3/upcase.c b/fs/ntfs3/upcase.c
> index b5e8256fd710..dd28c2133a4c 100644
> --- a/fs/ntfs3/upcase.c
> +++ b/fs/ntfs3/upcase.c
> @@ -74,31 +74,29 @@ int ntfs_cmp_names_cpu(const struct cpu_str *uni1, const struct le_str *uni2,
>  	size_t l1 = uni1->len;
>  	size_t l2 = uni2->len;
>  	size_t len = min(l1, l2);
> -	int diff1 = 0;
> -	int diff2;
> +	int diff;
>  
>  	if (!bothcase && upcase)
>  		goto case_insentive;
>  
>  	for (; len; s1++, s2++, len--) {
> -		diff1 = *s1 - le16_to_cpu(*s2);
> -		if (diff1) {
> +		diff = *s1 - le16_to_cpu(*s2);
> +		if (diff) {
>  			if (bothcase && upcase)
>  				goto case_insentive;
>  
> -			return diff1;
> +			return diff;
>  		}
>  	}
>  	return l1 - l2;
>  
>  case_insentive:
>  	for (; len; s1++, s2++, len--) {
> -		diff2 = upcase_unicode_char(upcase, *s1) -
> +		diff = upcase_unicode_char(upcase, *s1) -
>  			upcase_unicode_char(upcase, le16_to_cpu(*s2));
> -		if (diff2)
> -			return diff2;
> +		if (diff)
> +			return diff;
>  	}
>  
> -	diff2 = l1 - l2;
> -	return diff2 ? diff2 : diff1;
> +	return l1 - l2;
>  }
> -- 
> 2.31.1
> 
> 

Re: [PATCH] fs/ntfs3: Fix logic in ntfs_cmp_names_cpu

[Mark Harmstone]

On 28/9/21 23:07, Kari Argillander wrote:
 > So I have checked this now. Yes function will always return non-zero
 > value if we use bothcase and this is intended behavier. But if
 > bothcase is false and upcase is not NULL then function can return zero
 > value.

Thanks Kari. It's not clear to the casual observer what both_case even
means... It's only ever true when called from cmp_fnames for a non-DOS
$FILE_NAME. Given that DOS names are guaranteed to be uppercase, I'm
guessing it's supposed to mean "no need to uppercase this string as
well", but that's not what it's doing.

 > Do you have some problems? There could be that in some place this or
 > other cmp function is called with wrong parameters. Example with
 > bothcase true when only case_insentive is needed.

Yes, it forces case-sensitivity - i.e. `ls WINDOWS` give ENOENT, whereas
`ls Windows` succeeds. cmp_fnames <- indx_find <- dir_search_u <-
ntfs_lookup.

I think perhaps ntfs_cmp_names_cpu was supposed to look something like
the following?

int ntfs_cmp_names_cpu(const struct cpu_str *uni1, const struct le_str *uni2,
		       const u16 *upcase, bool uni2_not_uc)
{
	const u16 *s1 = uni1->name;
	const __le16 *s2 = uni2->name;
	size_t l1 = uni1->len;
	size_t l2 = uni2->len;
	size_t len = min(l1, l2);

	while (len > 0) {
		int diff = *s1 - le16_to_cpu(*s2);
		
		if (diff) {
			if (upcase)
				break;
			
			return diff;
		}

		s1++;
		s2++;
		len--;
	}

	if (len > 0 && upcase) {
		while (len > 0) {
			int diff;
			u16 c = le16_to_cpu(*s2);

			if (uni2_not_uc)
				c = upcase_unicode_char(upcase, c);

			diff = upcase_unicode_char(upcase, *s1) - c;

			if (diff)
				return diff;

			s1++;
			s2++;
			len--;
		}
	}

	return l1 - l2;
}

Mark

Re: [PATCH] fs/ntfs3: Fix logic in ntfs_cmp_names_cpu

[Mark Harmstone]

Kari, Konstantin, what's your conclusion on this? Do you agree that
case-insensitivity is broken at present, or is there something screwy
going on with my set-up?

Mark

Re: [PATCH] fs/ntfs3: Fix logic in ntfs_cmp_names_cpu

[Konstantin Komarov]

On 04.10.2021 21:25, Mark Harmstone wrote:
> Kari, Konstantin, what's your conclusion on this? Do you agree that
> case-insensitivity is broken at present, or is there something screwy
> going on with my set-up?
> 
> Mark


Hello.

Right now we can create two files "File" and "file" on ntfs3.
If we won't force case sensitivity, then it will become one and same file.
The same behavior you can see in
CreateFileA function with FILE_FLAG_POSIX_SEMANTICS [1]
or in NtSetInformationFile function with FileCaseSensitiveInformation [2].
So it's expected for `ls WINDOWS` to fail.

Should ntfs3 be the exact copy of windows api or not?
(ntfs.sys is case sensitive).
Should ntfs3 work with `ls WINDOWS`?
As I see, Microsoft makes steps towards case sensitivity.

There is indeed some dubious code with ntfs_cmp_names_cpu / ntfs_cmp_names.
We must always compare filenames with bothcase == true.
There will be patch to fix this situation.

Thanks for telling about this problem.

[1]: https://docs.microsoft.com/en-us/windows/win32/api/fileapi/nf-fileapi-createfilea
[2]: https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/ntifs/nf-ntifs-ntsetinformationfile

Re: [PATCH] fs/ntfs3: Fix logic in ntfs_cmp_names_cpu

[Mark Harmstone]

On 6/10/21 15:37, Konstantin Komarov wrote:
 > So it's expected for `ls WINDOWS` to fail.

I'm confused. If this deliberate, why does cmp_fnames pass the upcase pointer
to ntfs_cmp_names_cpu? Or for that matter, why do you bother loading the
upcase block at all?

 > The same behavior you can see in
 > CreateFileA function with FILE_FLAG_POSIX_SEMANTICS [1]
 > or in NtSetInformationFile function with FileCaseSensitiveInformation [2].

Two different things. AIUI, FILE_FLAG_POSIX_SEMANTICS passes the
SL_CASE_SENSITIVE flag through to the FS driver's IRP_MJ_CREATE function, doing
a case-sensitive lookup on what would otherwise be a normal directory. The
FileCaseSensitiveInformation flag is set on the inode and forces Windows 10 to
always do case-sensitive lookups for that directory (i.e. it's the inverse of
ext4's casefolding flag).

This issue came to my attention because I've been doing a lot of research into
NTFS recently, and want to add FileCaseSensitiveInformation support to your
driver. But obviously this issue is a blocker for that.

 > We must always compare filenames with bothcase == true.

You *really* need to rename this variable, it makes no sense at it is. As I
said, as far as I can make out it means "assume that one of the strings is
already uppercase".

 > There will be patch to fix this situation.

Not to be funny, but I've already provided you with one... You'll drive away
potential contributors if you ignore their patches without a good reason.

Re: [PATCH] fs/ntfs3: Fix logic in ntfs_cmp_names_cpu

[Konstantin Komarov]

On 06.10.2021 20:03, Mark Harmstone wrote:
> On 6/10/21 15:37, Konstantin Komarov wrote:
>> So it's expected for `ls WINDOWS` to fail.
> 
> I'm confused. If this deliberate, why does cmp_fnames pass the upcase pointer
> to ntfs_cmp_names_cpu? Or for that matter, why do you bother loading the
> upcase block at all?
> 

As I've said, it's expected, that ntfs3 case sensitive.
So it's expected for `ls WINDOWS` to fail.

About upcase block. How ntfs_cmp_names_cpu work:
First we compare case sensitive.
If we found something ( diff1 ), then we go to case insensitive loop
( that's where upcase is needed ).
There we compare case insensitive.
If we found something ( diff2 ), then we return it.
If not, then we return case sensitive result ( diff1 ).

Why such convoluted process?
This is optimized way of this algorithm ( from comment to ntfs_cmp_names ):
 * Straight way to compare names:
 * - Case insensitive
 * - If name equals and 'upcase' then
 * - Case sensitive

>> The same behavior you can see in
>> CreateFileA function with FILE_FLAG_POSIX_SEMANTICS [1]
>> or in NtSetInformationFile function with FileCaseSensitiveInformation [2].
> 
> Two different things. AIUI, FILE_FLAG_POSIX_SEMANTICS passes the
> SL_CASE_SENSITIVE flag through to the FS driver's IRP_MJ_CREATE function, doing
> a case-sensitive lookup on what would otherwise be a normal directory. The
> FileCaseSensitiveInformation flag is set on the inode and forces Windows 10 to
> always do case-sensitive lookups for that directory (i.e. it's the inverse of
> ext4's casefolding flag).
> 

Two different things from perspective of implementation.
From perspective of user they are similar: case sensitive lookup.

> This issue came to my attention because I've been doing a lot of research into
> NTFS recently, and want to add FileCaseSensitiveInformation support to your
> driver. But obviously this issue is a blocker for that.
> 
>> We must always compare filenames with bothcase == true.
> 
> You *really* need to rename this variable, it makes no sense at it is. As I
> said, as far as I can make out it means "assume that one of the strings is
> already uppercase".
> 

Yes, that's what I've meant by "There will be patch to fix this situation".
Patch fixes situation with bothcase variable.

>> There will be patch to fix this situation.
> 
> Not to be funny, but I've already provided you with one... You'll drive away
> potential contributors if you ignore their patches without a good reason.

As I've said previously right now ntfs3 is case sensitive.
Your patch will change it ( case sensitive result diff1 won't be returned ).
I've opened discussion on theme "should ntfs3 be case sensitive or case
insensitive" by writing "Should ntfs3 work with `ls WINDOWS`?".
I think, that ntfs3 need to be case sensitive.
And listed things, that I think support my opinion.
That's why I've mentioned that ntfs.sys is case sensitive.
That's why I've mentioned FILE_FLAG_POSIX_SEMANTICS and
FileCaseSensitiveInformation.
I don't think, that copying win32 api behavior is good,
when Microsoft makes steps to make ntfs work in posix way.
I'm sorry for not writing it more clear in previous letter.

Please don't think, that your work is disregarded.
You already found problem with bothcase.
I just can't accept patch, that will change default behavior of driver from
"case sensitive" to "case insensitive", without any discussion.

If I remember correctly, to make ntfs3 case insensitive you will need to provide
special functions d_hash and d_compare from struct dentry_operations
( examples: fs/fat and fs/exfat ).
Right now we use default versions, because they work with case sensitive fs.

Re: [PATCH] fs/ntfs3: Fix logic in ntfs_cmp_names_cpu

[Mark Harmstone]

On 7/10/21 15:33, Konstantin Komarov wrote:

 > This is optimized way of this algorithm ( from comment to ntfs_cmp_names ):
 >   * Straight way to compare names:
 >   * - Case insensitive
 >   * - If name equals and 'upcase' then
 >   * - Case sensitive

You have your first and third bullet points the wrong way round there. Am I
right then that the current case-insensitivity stuff is purely to determine
where the name goes in the $I30 B-tree?

 > I think, that ntfs3 need to be case sensitive.
 > And listed things, that I think support my opinion.
 > That's why I've mentioned that ntfs.sys is case sensitive.
 > That's why I've mentioned FILE_FLAG_POSIX_SEMANTICS and
 > FileCaseSensitiveInformation.
 > I don't think, that copying win32 api behavior is good,
 > when Microsoft makes steps to make ntfs work in posix way.

I'm surprised that what I wrote is controversial... NTFS is a case-insensitive
filesystem, that allows specific directories to override this with a flag. You
might wish it were otherwise, but the NTFS specification is defined by what
Microsoft's driver does.

Your driver lets me create a file called foo.txt and one called FOO.TXT in a
normal directory, and when I double-click on one in Windows the wrong file gets
opened. That's 100% a bug.

It's worth pointing out that the Linux vfat driver handles case-sensitivity on
Microsoft's other filesystem correctly.

Re: [PATCH] fs/ntfs3: Fix logic in ntfs_cmp_names_cpu

[Kari Argillander]

On Thu, Oct 07, 2021 at 07:26:26PM +0100, Mark Harmstone wrote:
> On 7/10/21 15:33, Konstantin Komarov wrote:
> 
> > This is optimized way of this algorithm ( from comment to ntfs_cmp_names ):
> >   * Straight way to compare names:
> >   * - Case insensitive
> >   * - If name equals and 'upcase' then
> >   * - Case sensitive
> 
> You have your first and third bullet points the wrong way round there. Am I
> right then that the current case-insensitivity stuff is purely to determine
> where the name goes in the $I30 B-tree?
> 
> > I think, that ntfs3 need to be case sensitive.
> > And listed things, that I think support my opinion.
> > That's why I've mentioned that ntfs.sys is case sensitive.
> > That's why I've mentioned FILE_FLAG_POSIX_SEMANTICS and
> > FileCaseSensitiveInformation.
> > I don't think, that copying win32 api behavior is good,
> > when Microsoft makes steps to make ntfs work in posix way.

I agree that Microsoft is making step towards POSIX.

> I'm surprised that what I wrote is controversial... NTFS is a case-insensitive
> filesystem, that allows specific directories to override this with a flag. You
> might wish it were otherwise, but the NTFS specification is defined by what
> Microsoft's driver does.

NTFS is case-sensitive filesystem which Windows treats with tricks like
case-insentive.

> Your driver lets me create a file called foo.txt and one called FOO.TXT in a
> normal directory, and when I double-click on one in Windows the wrong file gets
> opened. That's 100% a bug.

I disagree. NTFS point of view no bug at all. I agree that it maybe
Windows point view might be a bug. I agree that it might be good thing
to add mount option flag to control this behavier. Maybe nicest thing
would be that if we save other file which match case sensitive we just
raise flag for this folder and atleast never Windows will be able handle
those correctly. What do you think about this Konstantin?

> It's worth pointing out that the Linux vfat driver handles case-sensitivity on
> Microsoft's other filesystem correctly.

Re: [PATCH] fs/ntfs3: Fix logic in ntfs_cmp_names_cpu

[Mark Harmstone]

On 7/10/21 21:12, Kari Argillander wrote:
> NTFS is case-sensitive filesystem which Windows treats with tricks like
> case-insentive.

This is a distinction without a difference. It's not by default case-sensitive,
but it is case-preserving.

>> Your driver lets me create a file called foo.txt and one called FOO.TXT in a
>> normal directory, and when I double-click on one in Windows the wrong file gets
>> opened. That's 100% a bug.
> 
> I disagree. NTFS point of view no bug at all. I agree that it maybe
> Windows point view might be a bug. I agree that it might be good thing
> to add mount option flag to control this behavier. Maybe nicest thing
> would be that if we save other file which match case sensitive we just
> raise flag for this folder and atleast never Windows will be able handle
> those correctly. What do you think about this Konstantin?

Very dangerous. If you did this in System32 say, you could very easily nuke
your boot because Windows was looking for NTOSKRNL.EXE rather than ntoskrnl.exe -
even if that's not the file you were using.

>> It's worth pointing out that the Linux vfat driver handles case-sensitivity on
>> Microsoft's other filesystem correctly.

Question: do you disagree with the approach the vfat writers took? And if not,
what's the difference between FAT and NTFS in this regard?

Quite apart from anything else, the principle of least astonishment says that
Linux should follow what the reference implementation does. By all means add
a mount option to force case-sensitivity throughout, but this shouldn't be
the default.

Re: [PATCH] fs/ntfs3: Fix logic in ntfs_cmp_names_cpu

[Kari Argillander]

On Thu, Oct 07, 2021 at 09:34:02PM +0100, Mark Harmstone wrote:
> On 7/10/21 21:12, Kari Argillander wrote:
> > NTFS is case-sensitive filesystem which Windows treats with tricks like
> > case-insentive.
> 
> This is a distinction without a difference. It's not by default case-sensitive,
> but it is case-preserving.
> 
> > > Your driver lets me create a file called foo.txt and one called FOO.TXT in a
> > > normal directory, and when I double-click on one in Windows the wrong file gets
> > > opened. That's 100% a bug.
> > 
> > I disagree. NTFS point of view no bug at all. I agree that it maybe
> > Windows point view might be a bug. I agree that it might be good thing
> > to add mount option flag to control this behavier. Maybe nicest thing
> > would be that if we save other file which match case sensitive we just
> > raise flag for this folder and atleast never Windows will be able handle
> > those correctly. What do you think about this Konstantin?
> 
> Very dangerous. If you did this in System32 say, you could very easily nuke
> your boot because Windows was looking for NTOSKRNL.EXE rather than ntoskrnl.exe -
> even if that's not the file you were using.
> 
> > > It's worth pointing out that the Linux vfat driver handles case-sensitivity on
> > > Microsoft's other filesystem correctly.
> 
> Question: do you disagree with the approach the vfat writers took? And if not,
> what's the difference between FAT and NTFS in this regard?

Difference be that ntfs will be more commonly use at boot drive or home
folder in Linux.

> Quite apart from anything else, the principle of least astonishment says that
> Linux should follow what the reference implementation does. By all means add
> a mount option to force case-sensitivity throughout, but this shouldn't be
> the default.

Changing behavier before we have mount option or other solution to this
is totally wrong thing to do. Then you basically break Linux user
experience. Example you will not be able to save kernel source to ntfs
and build it from Linux. Sure Windows will not see couple of files, but
it will still work. If you do save something in Linux case sensitive
manner you usually have reason for it so there should not be many
problems to user. We can discuss default after we have solutions.