[RFC 0/2] Case-insensitive filename lookup for XFS

[RFC 0/2] Case-insensitive filename lookup for XFS

[Barry Naujok]

Following is the initial test version of case-insensitive support
for XFS in Linux. It implements case-insensitivity utilising a
Unicode case folding table stored on disk generated from
http://www.unicode.org/Public/UNIDATA/CaseFolding.txt

As the filesystem stores names as Unicode (UTF-8), the "nls"
mount option has been added to support systems not utilising
UTF-8 natively. If the nls mount option is not used, it will
use the default NLS defined in the kernel's config.

To allow case-insensitivity to be a mount option rather than
a mkfs option, the hashes stored on disk are always case-folded.
This is indicated by the new "unicode" bit in the superblock.
This bit also associated with the presence of the case-folding
table on disk.

With the case-folding table on disk, it allows us to upgrade
the table in the future while retaining backwards and forwards
compatibility. It also allows special case tables such as
Turkic case which is supported in this patch set.

The case-insensitive support also installs a couple of
dentry_operations for the XFS inodes: hash and compare.

Currently, there is a couple of outstanding issues with the
dentry cache interaction:

   - The first lookup if case-mismatched will continue to
     have the mismatched case in the cache. Not really sure
     if this is an issue or not. If it is an issue, how
     should I resolve it?

   - As above, but with a non-existing lookup, then creating
     the file with a different case, the first failed lookup
     will define the case used. I have partially resolved
     this with a memcpy if the two lengths are the same.
     How do I fix this if the lengths are different?
     (TODO's show the location of this problem.)

Other TODOs:

   - support for case-insensitve extended attributes
     as a separate mount option.

   - Other xfsprogs updates: xfs_repair, xfs_db

Re: [RFC 0/2] Case-insensitive filename lookup for XFS

[Anton Altaparmakov]

Hi,

On 23 Oct 2007, at 08:53, Barry Naujok wrote:
> Following is the initial test version of case-insensitive support
> for XFS in Linux. It implements case-insensitivity utilising a
> Unicode case folding table stored on disk generated from
> http://www.unicode.org/Public/UNIDATA/CaseFolding.txt
>
> As the filesystem stores names as Unicode (UTF-8), the "nls"
> mount option has been added to support systems not utilising
> UTF-8 natively. If the nls mount option is not used, it will
> use the default NLS defined in the kernel's config.
>
> To allow case-insensitivity to be a mount option rather than
> a mkfs option, the hashes stored on disk are always case-folded.
> This is indicated by the new "unicode" bit in the superblock.
> This bit also associated with the presence of the case-folding
> table on disk.
>
> With the case-folding table on disk, it allows us to upgrade
> the table in the future while retaining backwards and forwards
> compatibility. It also allows special case tables such as
> Turkic case which is supported in this patch set.
>
> The case-insensitive support also installs a couple of
> dentry_operations for the XFS inodes: hash and compare.
>
> Currently, there is a couple of outstanding issues with the
> dentry cache interaction:
>
>  - The first lookup if case-mismatched will continue to
>    have the mismatched case in the cache. Not really sure
>    if this is an issue or not. If it is an issue, how
>    should I resolve it?
>
>  - As above, but with a non-existing lookup, then creating
>    the file with a different case, the first failed lookup
>    will define the case used. I have partially resolved
>    this with a memcpy if the two lengths are the same.
>    How do I fix this if the lengths are different?
>    (TODO's show the location of this problem.)

Both of the above can be fairly easily fixed if you want.  NTFS does  
it in the stock kernel.

You would need to change the XFS ->lookup inode operation so that when  
it reads the directory to check whether a name exists, if it is found  
but the case is not matched, you need to make a copy of the correctly  
cased name (if NTFS this is done in fs/ntfs/ 
dir.c::ntfs_lookup_inode_by_name() if you want to take a look, the  
name is stored in the "ntfs_name" structure that is allocated during  
the lookup if a case mismatched match is found and this is returned to  
the caller).

Then in ->lookup() if you got a correctly cased name structure (if the  
name was cased correctly the correctly cased named structure pointer  
would be NULL) then you need to replace the dentry passed into - 
 >lookup with a new one with the correct case.  This is a little  
complicated because such a dentry may already exist in which case you  
have to use the existing one (instantiating it if it was negative) and  
if it does not already exist you need to allocate a new one,  
instantiate it and then move it over the old one.  Again a little  
complicated because of disconnected dentries for NFS.  But it is not  
too bad and it works well in NTFS (see fs/ntfs/namei.c::ntfs_lookup()  
the code that does all of this starts at the "handle_name" goto label).

Doing things this way means that you never have wrong case dentries in  
dcache.  And this in turn means that things like handling ->unlink and  
->rename inode operations is much easier as the dentry you receive  
there is returned from a ->lookup() call thus you know it is correctly  
cased already so you can do a case-sensitive match when looking up the  
directory entry to remove/rename!  (I am afraid you cannot look at the  
NTFS code for that as that is not publicly available yet. )-:)

Best regards,

	Anton

> Other TODOs:
>
>  - support for case-insensitve extended attributes
>    as a separate mount option.
>
>  - Other xfsprogs updates: xfs_repair, xfs_db

-- 
Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @)
Unix Support, Computing Service, University of Cambridge, CB2 3QH, UK
Linux NTFS maintainer, http://www.linux-ntfs.org/

Re: [RFC 0/2] Case-insensitive filename lookup for XFS

[Anton Altaparmakov]

I forgot to say:  If you do what I did for NTFS you can also throw  
away your custom dentry operations that your patch adds as the dcache  
then only holds correctly cased names so you are fine to do case  
sensitive dcache lookups at all times.  Access via wrongly cased name  
will always go to ->lookup inode operation and that is fine because  
such lookups almost never happen because majority of users will either  
use a GUI in which case all names are always correctly cased as the  
names displayed in the GUI are obtained from a ->readdir and thus show  
the correct case or they will use the command line in which case they  
will be savvy enough to use tab-completion in which case the names are  
correct case, too.  Tab-completion does not work on wrongly cased  
names so you are very unlikely to ever get a wrongly cased name at all.

And yes of course you can on purpose construct a test / benchmark  
where having to do the ->lookup each time will be really slow because  
you keep creating files and then accessing them by wrongly cased name  
on purpose (or whatever) but I would hope that you do not care about  
such artificial benchmarks that do not reflect any real-world loads...

Best regards,

	Anton

On 23 Oct 2007, at 11:01, Anton Altaparmakov wrote:

> Hi,
>
> On 23 Oct 2007, at 08:53, Barry Naujok wrote:
>> Following is the initial test version of case-insensitive support
>> for XFS in Linux. It implements case-insensitivity utilising a
>> Unicode case folding table stored on disk generated from
>> http://www.unicode.org/Public/UNIDATA/CaseFolding.txt
>>
>> As the filesystem stores names as Unicode (UTF-8), the "nls"
>> mount option has been added to support systems not utilising
>> UTF-8 natively. If the nls mount option is not used, it will
>> use the default NLS defined in the kernel's config.
>>
>> To allow case-insensitivity to be a mount option rather than
>> a mkfs option, the hashes stored on disk are always case-folded.
>> This is indicated by the new "unicode" bit in the superblock.
>> This bit also associated with the presence of the case-folding
>> table on disk.
>>
>> With the case-folding table on disk, it allows us to upgrade
>> the table in the future while retaining backwards and forwards
>> compatibility. It also allows special case tables such as
>> Turkic case which is supported in this patch set.
>>
>> The case-insensitive support also installs a couple of
>> dentry_operations for the XFS inodes: hash and compare.
>>
>> Currently, there is a couple of outstanding issues with the
>> dentry cache interaction:
>>
>> - The first lookup if case-mismatched will continue to
>>   have the mismatched case in the cache. Not really sure
>>   if this is an issue or not. If it is an issue, how
>>   should I resolve it?
>>
>> - As above, but with a non-existing lookup, then creating
>>   the file with a different case, the first failed lookup
>>   will define the case used. I have partially resolved
>>   this with a memcpy if the two lengths are the same.
>>   How do I fix this if the lengths are different?
>>   (TODO's show the location of this problem.)
>
> Both of the above can be fairly easily fixed if you want.  NTFS does  
> it in the stock kernel.
>
> You would need to change the XFS ->lookup inode operation so that  
> when it reads the directory to check whether a name exists, if it is  
> found but the case is not matched, you need to make a copy of the  
> correctly cased name (if NTFS this is done in fs/ntfs/ 
> dir.c::ntfs_lookup_inode_by_name() if you want to take a look, the  
> name is stored in the "ntfs_name" structure that is allocated during  
> the lookup if a case mismatched match is found and this is returned  
> to the caller).
>
> Then in ->lookup() if you got a correctly cased name structure (if  
> the name was cased correctly the correctly cased named structure  
> pointer would be NULL) then you need to replace the dentry passed  
> into ->lookup with a new one with the correct case.  This is a  
> little complicated because such a dentry may already exist in which  
> case you have to use the existing one (instantiating it if it was  
> negative) and if it does not already exist you need to allocate a  
> new one, instantiate it and then move it over the old one.  Again a  
> little complicated because of disconnected dentries for NFS.  But it  
> is not too bad and it works well in NTFS (see fs/ntfs/ 
> namei.c::ntfs_lookup() the code that does all of this starts at the  
> "handle_name" goto label).
>
> Doing things this way means that you never have wrong case dentries  
> in dcache.  And this in turn means that things like handling - 
> >unlink and ->rename inode operations is much easier as the dentry  
> you receive there is returned from a ->lookup() call thus you know  
> it is correctly cased already so you can do a case-sensitive match  
> when looking up the directory entry to remove/rename!  (I am afraid  
> you cannot look at the NTFS code for that as that is not publicly  
> available yet. )-:)
>
> Best regards,
>
> 	Anton
>
>> Other TODOs:
>>
>> - support for case-insensitve extended attributes
>>   as a separate mount option.
>>
>> - Other xfsprogs updates: xfs_repair, xfs_db


-- 
Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @)
Unix Support, Computing Service, University of Cambridge, CB2 3QH, UK
Linux NTFS maintainer, http://www.linux-ntfs.org/

Re: [RFC 0/2] Case-insensitive filename lookup for XFS

[Martin Steigerwald]

Am Dienstag, 23. Oktober 2007 schrieb Barry Naujok:

Hi Barry,

> To allow case-insensitivity to be a mount option rather than
> a mkfs option, the hashes stored on disk are always case-folded.
> This is indicated by the new "unicode" bit in the superblock.
> This bit also associated with the presence of the case-folding
> table on disk.

What would happen in the following scenario?

mount -t xfs /dev/somedevice /mnt/tmp
touch /mnt/tmp/testfile
touch /mnt/tmp/Testfile
touch /mnt/tmp/TESTFILE

mount -t xfs -o remount,ci /dev/somedevice /mnt/tmp
rm /mnt/tmp/testfile

(I think I do not understand enough of XFS to read that myself out of your 
patch.)

Ciao,
-- 
Martin Steigerwald - team(ix) GmbH - http://www.teamix.de
gpg: 19E3 8D42 896F D004 08AC A0CA 1E10 C593 0399 AE90

Re: [RFC 0/2] Case-insensitive filename lookup for XFS

[Barry Naujok]

On Tue, 23 Oct 2007 22:22:21 +1000, Martin Steigerwald <ms@teamix.de> wrote:

> Am Dienstag, 23. Oktober 2007 schrieb Barry Naujok:
>
> Hi Barry,
>
>> To allow case-insensitivity to be a mount option rather than
>> a mkfs option, the hashes stored on disk are always case-folded.
>> This is indicated by the new "unicode" bit in the superblock.
>> This bit also associated with the presence of the case-folding
>> table on disk.
>
> What would happen in the following scenario?
>
> mount -t xfs /dev/somedevice /mnt/tmp
> touch /mnt/tmp/testfile
> touch /mnt/tmp/Testfile
> touch /mnt/tmp/TESTFILE
>
> mount -t xfs -o remount,ci /dev/somedevice /mnt/tmp
> rm /mnt/tmp/testfile

testfile would be deleted, Testfile and TESTFILE will remain.
Subsequent rm's should remove the rest.

Re: [RFC 0/2] Case-insensitive filename lookup for XFS

[Barry Naujok]

Hi Anton,

On Tue, 23 Oct 2007 20:07:47 +1000, Anton Altaparmakov <aia21@cam.ac.uk> wrote:

> I forgot to say:  If you do what I did for NTFS you can also throw
> away your custom dentry operations that your patch adds as the dcache
> then only holds correctly cased names so you are fine to do case
> sensitive dcache lookups at all times.  Access via wrongly cased name
> will always go to ->lookup inode operation and that is fine because
> such lookups almost never happen because majority of users will either
> use a GUI in which case all names are always correctly cased as the
> names displayed in the GUI are obtained from a ->readdir and thus show
> the correct case or they will use the command line in which case they
> will be savvy enough to use tab-completion in which case the names are
> correct case, too.  Tab-completion does not work on wrongly cased
> names so you are very unlikely to ever get a wrongly cased name at all.
>
> And yes of course you can on purpose construct a test / benchmark
> where having to do the ->lookup each time will be really slow because
> you keep creating files and then accessing them by wrongly cased name
> on purpose (or whatever) but I would hope that you do not care about
> such artificial benchmarks that do not reflect any real-world loads...

I have been looking at ntfs_lookup() and seeing how it does its stuff.
It seems that is the best way to go.

One thing I have noticed is with two or more attempted case-insensitive
lookups that don't exist yet case match the same
(ie. ntfs_lookup_inode_by_name() fails with -ENOENT), d_add(dent, NULL)
is called, populating the dentry with effective duplicates.

Eg:
  # cat /mnt/foo/fileNOTexist
  # cat /mnt/foo/FILEnotEXIST

Will have two negative dentries, am I correct?

Regards,
Barry.

Re: [RFC 0/2] Case-insensitive filename lookup for XFS

[Martin Steigerwald]

Am Mittwoch, 24. Oktober 2007 schrieb Barry Naujok:
> On Tue, 23 Oct 2007 22:22:21 +1000, Martin Steigerwald <ms@teamix.de> wrote:

> > What would happen in the following scenario?
> >
> > mount -t xfs /dev/somedevice /mnt/tmp
> > touch /mnt/tmp/testfile
> > touch /mnt/tmp/Testfile
> > touch /mnt/tmp/TESTFILE
> >
> > mount -t xfs -o remount,ci /dev/somedevice /mnt/tmp
> > rm /mnt/tmp/testfile
>
> testfile would be deleted, Testfile and TESTFILE will remain.
> Subsequent rm's should remove the rest.

Sounds indeed quite clever to me ;-)

I look forward to that feature which could be interesting for samba file 
shares cause samba would not have to map case-insensitive paths from Windows 
to the case-sensitive paths under Linux anymore.

-- 
Martin Steigerwald - team(ix) GmbH - http://www.teamix.de
gpg: 19E3 8D42 896F D004 08AC A0CA 1E10 C593 0399 AE90

Re: [RFC 0/2] Case-insensitive filename lookup for XFS

[Olaf Frączyk]

On Wed, 2007-10-24 at 10:34 +1000, Barry Naujok wrote:
> On Tue, 23 Oct 2007 22:22:21 +1000, Martin Steigerwald <ms@teamix.de> wrote:
> 
> > Am Dienstag, 23. Oktober 2007 schrieb Barry Naujok:
> >
> > Hi Barry,
> >
> >> To allow case-insensitivity to be a mount option rather than
> >> a mkfs option, the hashes stored on disk are always case-folded.
> >> This is indicated by the new "unicode" bit in the superblock.
> >> This bit also associated with the presence of the case-folding
> >> table on disk.
> >
> > What would happen in the following scenario?
> >
> > mount -t xfs /dev/somedevice /mnt/tmp
> > touch /mnt/tmp/testfile
> > touch /mnt/tmp/Testfile
> > touch /mnt/tmp/TESTFILE
> >
> > mount -t xfs -o remount,ci /dev/somedevice /mnt/tmp
> > rm /mnt/tmp/testfile
> 
> testfile would be deleted, Testfile and TESTFILE will remain.
> Subsequent rm's should remove the rest.

Or maybe testfile and Testfile will remain? If it is mounted as ci you
have no idea which one will be deleted.

IMO having this as mount option is broken by design. If you do it as
mkfs option then you avoid most of ugly problems.
1. What if you have the following code in your program

if (exists lala){
	error=remove lala
	if(error) die
	if(!error) error=create lala
	if(error) die
}

the create will fail, and it is clearly not expected behaviour.

2. What will ls show:
Test.txt
test.txt
TeSt.txt
when mount as ci?

3. Which one will be removed if you do rm on ci mounted filesystem?

4. If it were mkfs option you could avoid expensive filename lookups.
Just store all files in lowercase and on lookup convert the argument to
lowercase. If you want to preserve case you could use eg. file attribute
to store filename with case preserved.

Regards,

Olaf Frączyk



-- 
Olaf Frączyk <olaf@cbk.poznan.pl>

Re: [RFC 0/2] Case-insensitive filename lookup for XFS

[Anton Altaparmakov]

Hi Barry,

On 24 Oct 2007, at 08:39, Barry Naujok wrote:
> On Tue, 23 Oct 2007 20:07:47 +1000, Anton Altaparmakov <aia21@cam.ac.uk 
> > wrote:
>> I forgot to say:  If you do what I did for NTFS you can also throw
>> away your custom dentry operations that your patch adds as the dcache
>> then only holds correctly cased names so you are fine to do case
>> sensitive dcache lookups at all times.  Access via wrongly cased name
>> will always go to ->lookup inode operation and that is fine because
>> such lookups almost never happen because majority of users will  
>> either
>> use a GUI in which case all names are always correctly cased as the
>> names displayed in the GUI are obtained from a ->readdir and thus  
>> show
>> the correct case or they will use the command line in which case they
>> will be savvy enough to use tab-completion in which case the names  
>> are
>> correct case, too.  Tab-completion does not work on wrongly cased
>> names so you are very unlikely to ever get a wrongly cased name at  
>> all.
>>
>> And yes of course you can on purpose construct a test / benchmark
>> where having to do the ->lookup each time will be really slow because
>> you keep creating files and then accessing them by wrongly cased name
>> on purpose (or whatever) but I would hope that you do not care about
>> such artificial benchmarks that do not reflect any real-world  
>> loads...
>
> I have been looking at ntfs_lookup() and seeing how it does its stuff.
> It seems that is the best way to go.
>
> One thing I have noticed is with two or more attempted case- 
> insensitive
> lookups that don't exist yet case match the same
> (ie. ntfs_lookup_inode_by_name() fails with -ENOENT), d_add(dent,  
> NULL)
> is called, populating the dentry with effective duplicates.
>
> Eg:
>  # cat /mnt/foo/fileNOTexist
>  # cat /mnt/foo/FILEnotEXIST
>
> Will have two negative dentries, am I correct?


Yes, that is correct.  Well spotted!  That means NTFS needs to start  
killing all negative dentries belonging to a directory each time a  
directory entry is created in that directory.  That is what I do for  
NTFS on Mac OS X already but I had forgotten about needing to do it on  
Linux, too.  )-:

In OSX there the VFS provides a function to do this "xnu/bsd/vfs/ 
vfs_cache.c::cache_purge_negatives()", we will need to implement an  
equivalent on Linux:

<quote from xnu/bsd/vfs/vfs_cache.c>
/*
  * Purge all negative cache entries that are children of the
  * given vnode.  A case-insensitive file system (or any file
  * system that has multiple equivalent names for the same
  * directory entry) can use this when creating or renaming
  * to remove negative entries that may no longer apply.
  */
void
cache_purge_negatives(vnode_t vp)
{
         struct namecache *ncp;

         NAME_CACHE_LOCK();

         LIST_FOREACH(ncp, &vp->v_ncchildren, nc_child)
                 if (ncp->nc_vp == NULL)
                         cache_delete(ncp, 1);

         NAME_CACHE_UNLOCK();
}
</quote>

The Linux version should be analogous AFAICS, i.e. take the dentry of  
the directory in which an entry is being created and iterate over its  
d_subdirs list and for each dentry on that list if it is a negative  
dentry, i.e. d_inode is NULL, throw the dentry away.  Basically very  
similar to the OSX function but I can't quite see which dcache  
function we need to call to do the "throw the dentry away" bit.  None  
of the functions in fs/dcache.c look quite right.  I imagine we want  
to take the dcache_lock, traverse d_subdirs list of the directory  
dentry and for each negative dentry on the list, do a __dget_locked(),  
__d_drop(), spin_unlock(&dentry->d_lock), then move it from d_subdirs  
of its parent to a private list and when when we are done, drop the  
dcache_lock and go over the private list and do a dput() for each  
dentry on the private list which will result in them all being  
d_kill()ed.  This can probably be made more efficient by someone who  
understands the dcache better than me but it seems what I suggest  
would at least do the right thing...

Best regards,

	Anton
-- 
Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @)
Unix Support, Computing Service, University of Cambridge, CB2 3QH, UK
Linux NTFS maintainer, http://www.linux-ntfs.org/