[PATCH 0/3] fat: add a cache for msdos_format_name()

[PATCH 0/3] fat: add a cache for msdos_format_name()

[Caleb D.S. Brzezinski]

Hi all,

This patch series adds a cache for the formatted names created by
msdos_format_name(). In my testing, it resulted in approximately a 0.2 ms
decrease in kernel time for listing a small directory.

The overhead is in memory, but each entry is only 25 bytes plus
sizeof(struct hlist_node), and the cache also actively collects
infrequently used nodes, keeping overall memory usage low.

Caleb D.S. Brzezinski (3):
  fat: define functions and data structures for a formatted name cache
  fat: add the msdos_format_name() filename cache
  fat: add hash machinery to relevant filesystem operations

 fs/fat/namei_msdos.c | 140 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 140 insertions(+)


base-commit: 85a90500f9a1717c4e142ce92e6c1cb1a339ec78
-- 
2.32.0

[PATCH 1/3] fat: define functions and data structures for a formatted name cache

[Caleb D.S. Brzezinski]

Define the functions and data structures to use as a name formatting
cache for msdos, using the generic Linux hashtable.

Signed-off-by: Caleb D.S. Brzezinski <calebdsb@protonmail.com>
---
 fs/fat/namei_msdos.c | 96 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 96 insertions(+)

diff --git a/fs/fat/namei_msdos.c b/fs/fat/namei_msdos.c
index efba301d6..7561674b1 100644
--- a/fs/fat/namei_msdos.c
+++ b/fs/fat/namei_msdos.c
@@ -9,12 +9,108 @@
 
 #include <linux/module.h>
 #include <linux/iversion.h>
+#include <linux/types.h>
+#include <linux/hashtable.h>
+#include <linux/slab.h>
+#include <linux/mutex.h>
 #include "fat.h"
 
 /* Characters that are undesirable in an MS-DOS file name */
 static unsigned char bad_chars[] = "*?<>|\"";
 static unsigned char bad_if_strict[] = "+=,; ";
 
+
+/**
+ * struct msdos_name_node - A formatted filename cache node
+ * @fname: the formatted filename
+ * @gc: a use counter for removing non-frequently used names
+ * @hash: the key for the item in the hash table
+ * @h_list: the list to the next set of values in this node's bucket
+ */
+struct msdos_name_node {
+	u16 gc;
+	char fname[9];
+	u64 hash;
+	struct hlist_node h_list;
+};
+
+DEFINE_HASHTABLE(msdos_ncache, 6);
+DEFINE_MUTEX(msdos_ncache_mutex); /* protect the name cache */
+
+/**
+ * msdos_fname_hash() - quickly "hash" an msdos filename
+ * @name: the name to hash, assumed to be a maximum of eight characters
+ *
+ * Bitwise-or the characters in an msdos filename into a simple "hash" that can
+ * be used as a fast hash for an msdos filename.
+ */
+static u64 msdos_fname_hash(const unsigned char *name)
+{
+	u64 res = 0;
+	short i;
+
+	for (i = 0; i < 8 && name[i] != '\0'; i++)
+		res |= (u64)(name[i] << (8 * i));
+
+	return res;
+}
+
+/**
+ * find_fname_in_cache() - retrieve a filename from the cache given a hash
+ * @out: the result buffer for the filename
+ * @ihash: the hash to check for
+ */
+static bool find_fname_in_cache(char *out, u64 ihash)
+{
+	struct msdos_name_node *node;
+	bool found = false;
+
+	mutex_lock(&msdos_ncache_mutex);
+	hash_for_each_possible(msdos_ncache, node, h_list, ihash) {
+		if (node->hash == ihash) {
+			strscpy(out, node->fname, 9);
+			found = true;
+			node->gc++;
+			goto out;
+		}
+	}
+
+out:
+	mutex_unlock(&msdos_ncache_mutex);
+	return found;
+}
+
+/**
+ * drop_fname_from_cache() - delete and free a filename from the hash entry
+ * @ihash: the hash to remove from the cache
+ */
+static void drop_fname_from_cache(u64 ihash)
+{
+	struct msdos_name_node *node, *gc;
+
+	gc = NULL;
+
+	mutex_lock(&msdos_ncache_mutex);
+	hash_for_each_possible(msdos_ncache, node, h_list, ihash) {
+		if (unlikely(gc)) {
+			hash_del(&gc->h_list);
+			kfree(gc);
+			gc = NULL;
+		}
+		if (node->hash == ihash) {
+			hash_del(&node->h_list);
+			kfree(node);
+			goto out;
+		}
+		/* if we don't find it, collect unused nodes until we do */
+		if (node->gc < 4)
+			gc = node;
+	}
+
+out:
+	mutex_unlock(&msdos_ncache_mutex);
+}
+
 /***** Formats an MS-DOS file name. Rejects invalid names. */
 static int msdos_format_name(const unsigned char *name, int len,
 			     unsigned char *res, struct fat_mount_options *opts)

base-commit: 85a90500f9a1717c4e142ce92e6c1cb1a339ec78
-- 
2.32.0

Re: [PATCH 1/3] fat: define functions and data structures for a formatted name cache

[kernel test robot]

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

Hi "Caleb,

Thank you for the patch! Perhaps something to improve:

[auto build test WARNING on 85a90500f9a1717c4e142ce92e6c1cb1a339ec78]

url:    https://github.com/0day-ci/linux/commits/Caleb-D-S-Brzezinski/fat-add-a-cache-for-msdos_format_name/20210829-222721
base:   85a90500f9a1717c4e142ce92e6c1cb1a339ec78
config: x86_64-randconfig-s021-20210829 (attached as .config)
compiler: gcc-9 (Debian 9.3.0-22) 9.3.0
reproduce:
        # apt-get install sparse
        # sparse version: v0.6.3-348-gf0e6938b-dirty
        # https://github.com/0day-ci/linux/commit/146971c07a5f865afc968df1d25fa312a5a38b24
        git remote add linux-review https://github.com/0day-ci/linux
        git fetch --no-tags linux-review Caleb-D-S-Brzezinski/fat-add-a-cache-for-msdos_format_name/20210829-222721
        git checkout 146971c07a5f865afc968df1d25fa312a5a38b24
        # save the attached .config to linux build tree
        make W=1 C=1 CF='-fdiagnostic-prefix -D__CHECK_ENDIAN__' O=build_dir ARCH=x86_64 SHELL=/bin/bash fs/fat/

If you fix the issue, kindly add following tag as appropriate
Reported-by: kernel test robot <lkp@intel.com>


sparse warnings: (new ones prefixed by >>)
>> fs/fat/namei_msdos.c:37:1: sparse: sparse: symbol 'msdos_ncache' was not declared. Should it be static?
>> fs/fat/namei_msdos.c:38:1: sparse: sparse: symbol 'msdos_ncache_mutex' was not declared. Should it be static?

Please review and possibly fold the followup patch.

---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all@lists.01.org

[-- Attachment #2: .config.gz --]
[-- Type: application/gzip, Size: 36697 bytes --]

[RFC PATCH] fat: msdos_ncache can be static

[kernel test robot]

fs/fat/namei_msdos.c:37:1: warning: symbol 'msdos_ncache' was not declared. Should it be static?
fs/fat/namei_msdos.c:38:1: warning: symbol 'msdos_ncache_mutex' was not declared. Should it be static?

Reported-by: kernel test robot <lkp@intel.com>
Signed-off-by: kernel test robot <lkp@intel.com>
---
 namei_msdos.c |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/fs/fat/namei_msdos.c b/fs/fat/namei_msdos.c
index 7561674b16a22..f44d590a11583 100644
--- a/fs/fat/namei_msdos.c
+++ b/fs/fat/namei_msdos.c
@@ -34,8 +34,8 @@ struct msdos_name_node {
 	struct hlist_node h_list;
 };
 
-DEFINE_HASHTABLE(msdos_ncache, 6);
-DEFINE_MUTEX(msdos_ncache_mutex); /* protect the name cache */
+static DEFINE_HASHTABLE(msdos_ncache, 6);
+static DEFINE_MUTEX(msdos_ncache_mutex); /* protect the name cache */
 
 /**
  * msdos_fname_hash() - quickly "hash" an msdos filename

[PATCH 2/3] fat: add the msdos_format_name() filename cache

[Caleb D.S. Brzezinski]

Implement the main msdos_format_name() filename cache. If used as a
module, all memory allocated for the cache is freed when the module is
de-registered.

Signed-off-by: Caleb D.S. Brzezinski <calebdsb@protonmail.com>
---
 fs/fat/namei_msdos.c | 35 +++++++++++++++++++++++++++++++++++
 1 file changed, 35 insertions(+)

diff --git a/fs/fat/namei_msdos.c b/fs/fat/namei_msdos.c
index 7561674b1..f9d4f63c3 100644
--- a/fs/fat/namei_msdos.c
+++ b/fs/fat/namei_msdos.c
@@ -124,6 +124,16 @@ static int msdos_format_name(const unsigned char *name, int len,
 	unsigned char *walk;
 	unsigned char c;
 	int space;
+	u64 hash;
+	struct msdos_name_node *node;
+
+	/* check if the name is already in the cache */
+
+	hash = msdos_fname_hash(name);
+	if (find_fname_in_cache(res, hash))
+		return 0;
+
+	/* The node wasn't in the cache, so format it normally */
 
 	if (name[0] == '.') {	/* dotfile because . and .. already done */
 		if (opts->dotsOK) {
@@ -208,6 +218,18 @@ static int msdos_format_name(const unsigned char *name, int len,
 	while (walk - res < MSDOS_NAME)
 		*walk++ = ' ';
 
+	/* allocate memory now */
+	node = kmalloc(sizeof(*node), GFP_KERNEL);
+	if (!node)
+		return -ENOMEM;
+
+	/* fill in the name cache */
+	node->hash = hash;
+	strscpy(node->fname, res, 9);
+	mutex_lock(&msdos_ncache_mutex);
+	hash_add(msdos_ncache, &node->h_list, node->hash);
+	mutex_unlock(&msdos_ncache_mutex);
+
 	return 0;
 }
 
@@ -677,6 +699,7 @@ static int do_msdos_rename(struct inode *old_dir, unsigned char *old_name,
 		 * shouldn't be serious corruption.
 		 */
 		int err2 = fat_remove_entries(new_dir, &sinfo);
+
 		if (corrupt)
 			corrupt |= err2;
 		sinfo.bh = NULL;
@@ -774,6 +797,18 @@ static int __init init_msdos_fs(void)
 
 static void __exit exit_msdos_fs(void)
 {
+	int bkt;
+	struct msdos_name_node *c, *prev;
+
+	prev = NULL;
+	/* do this one behind to prevent bad memory access */
+	hash_for_each(msdos_ncache, bkt, c, h_list) {
+		kfree(prev);
+		prev = c;
+	}
+
+	kfree(prev);
+
 	unregister_filesystem(&msdos_fs_type);
 }
 
-- 
2.32.0

Re: [PATCH 2/3] fat: add the msdos_format_name() filename cache

[Al Viro]

On Sun, Aug 29, 2021 at 02:25:29PM +0000, Caleb D.S. Brzezinski wrote:
> Implement the main msdos_format_name() filename cache. If used as a
> module, all memory allocated for the cache is freed when the module is
> de-registered.
> 
> Signed-off-by: Caleb D.S. Brzezinski <calebdsb@protonmail.com>
> ---
>  fs/fat/namei_msdos.c | 35 +++++++++++++++++++++++++++++++++++
>  1 file changed, 35 insertions(+)
> 
> diff --git a/fs/fat/namei_msdos.c b/fs/fat/namei_msdos.c
> index 7561674b1..f9d4f63c3 100644
> --- a/fs/fat/namei_msdos.c
> +++ b/fs/fat/namei_msdos.c
> @@ -124,6 +124,16 @@ static int msdos_format_name(const unsigned char *name, int len,
>  	unsigned char *walk;
>  	unsigned char c;
>  	int space;
> +	u64 hash;
> +	struct msdos_name_node *node;
> +
> +	/* check if the name is already in the cache */
> +
> +	hash = msdos_fname_hash(name);
> +	if (find_fname_in_cache(res, hash))
> +		return 0;

Huh?  How could that possibly work, seeing that
	* your hash function only looks at the first 8 characters
	* your find_fname_in_cache() assumes that hash collisions
are impossible, which is... unlikely, considering the nature of
that hash function
	* find_fname_in_cache(res, hash) copies at most 8 characters
into res in case of match.  Where does the extension come from?

Out of curiosity, how have you tested that thing?

Re: [PATCH 2/3] fat: add the msdos_format_name() filename cache

[Al Viro]

On Sun, Aug 29, 2021 at 03:11:22PM +0000, Al Viro wrote:
> On Sun, Aug 29, 2021 at 02:25:29PM +0000, Caleb D.S. Brzezinski wrote:
> > Implement the main msdos_format_name() filename cache. If used as a
> > module, all memory allocated for the cache is freed when the module is
> > de-registered.
> > 
> > Signed-off-by: Caleb D.S. Brzezinski <calebdsb@protonmail.com>
> > ---
> >  fs/fat/namei_msdos.c | 35 +++++++++++++++++++++++++++++++++++
> >  1 file changed, 35 insertions(+)
> > 
> > diff --git a/fs/fat/namei_msdos.c b/fs/fat/namei_msdos.c
> > index 7561674b1..f9d4f63c3 100644
> > --- a/fs/fat/namei_msdos.c
> > +++ b/fs/fat/namei_msdos.c
> > @@ -124,6 +124,16 @@ static int msdos_format_name(const unsigned char *name, int len,
> >  	unsigned char *walk;
> >  	unsigned char c;
> >  	int space;
> > +	u64 hash;
> > +	struct msdos_name_node *node;
> > +
> > +	/* check if the name is already in the cache */
> > +
> > +	hash = msdos_fname_hash(name);
> > +	if (find_fname_in_cache(res, hash))
> > +		return 0;
> 
> Huh?  How could that possibly work, seeing that
> 	* your hash function only looks at the first 8 characters
> 	* your find_fname_in_cache() assumes that hash collisions
> are impossible, which is... unlikely, considering the nature of
> that hash function
> 	* find_fname_in_cache(res, hash) copies at most 8 characters
> into res in case of match.  Where does the extension come from?
> 
> Out of curiosity, how have you tested that thing?

While we are at it, your "fast path" doesn't even look at opts
argument...

Re: [PATCH 2/3] fat: add the msdos_format_name() filename cache

[Caleb D.S. Brzezinski]

Hi Al,

"Al Viro" <viro@zeniv.linux.org.uk> writes:

> On Sun, Aug 29, 2021 at 03:11:22PM +0000, Al Viro wrote:
>> On Sun, Aug 29, 2021 at 02:25:29PM +0000, Caleb D.S. Brzezinski wrote:
>> > Implement the main msdos_format_name() filename cache. If used as a
>> > module, all memory allocated for the cache is freed when the module is
>> > de-registered.
>> >
>> > Signed-off-by: Caleb D.S. Brzezinski <calebdsb@protonmail.com>
>> > ---
>> >  fs/fat/namei_msdos.c | 35 +++++++++++++++++++++++++++++++++++
>> >  1 file changed, 35 insertions(+)
>> >
>> > diff --git a/fs/fat/namei_msdos.c b/fs/fat/namei_msdos.c
>> > index 7561674b1..f9d4f63c3 100644
>> > --- a/fs/fat/namei_msdos.c
>> > +++ b/fs/fat/namei_msdos.c
>> > @@ -124,6 +124,16 @@ static int msdos_format_name(const unsigned char *name, int len,
>> >  	unsigned char *walk;
>> >  	unsigned char c;
>> >  	int space;
>> > +	u64 hash;
>> > +	struct msdos_name_node *node;
>> > +
>> > +	/* check if the name is already in the cache */
>> > +
>> > +	hash = msdos_fname_hash(name);
>> > +	if (find_fname_in_cache(res, hash))
>> > +		return 0;
>>
>> Huh?  How could that possibly work, seeing that
>> 	* your hash function only looks at the first 8 characters
>> 	* your find_fname_in_cache() assumes that hash collisions
>> are impossible, which is... unlikely, considering the nature of
>> that hash function
>> 	* find_fname_in_cache(res, hash) copies at most 8 characters

>> Where does the extension come from?

I'll be honest, I don't have any. Before I started writing this code I
poked msdos_format_name() with a lot of sticks to make sure I understood
the behavior, and it never carried over extentions into the FAT system;
at least, not that I saw through this function.

> While we are at it, your "fast path" doesn't even look at opts
> argument...

My understanding is that opts is a semi-global/per-drive setting. If
that's wrong then again, yes, this won't function correctly, but it does
seem to work.

Thanks.
Caleb B.

-- 
"Come now, and let us reason together," Says the LORD
    -- Isaiah 1:18a, NASB

Re: [PATCH 2/3] fat: add the msdos_format_name() filename cache

[Caleb D.S. Brzezinski]

Hi Al,

"Al Viro" <viro@zeniv.linux.org.uk> writes:

> On Sun, Aug 29, 2021 at 02:25:29PM +0000, Caleb D.S. Brzezinski wrote:
>> Implement the main msdos_format_name() filename cache. If used as a
>> module, all memory allocated for the cache is freed when the module is
>> de-registered.
>>
>> Signed-off-by: Caleb D.S. Brzezinski <calebdsb@protonmail.com>
>> ---
>>  fs/fat/namei_msdos.c | 35 +++++++++++++++++++++++++++++++++++
>>  1 file changed, 35 insertions(+)
>>
>> diff --git a/fs/fat/namei_msdos.c b/fs/fat/namei_msdos.c
>> index 7561674b1..f9d4f63c3 100644
>> --- a/fs/fat/namei_msdos.c
>> +++ b/fs/fat/namei_msdos.c
>> @@ -124,6 +124,16 @@ static int msdos_format_name(const unsigned char *name, int len,
>>  	unsigned char *walk;
>>  	unsigned char c;
>>  	int space;
>> +	u64 hash;
>> +	struct msdos_name_node *node;
>> +
>> +	/* check if the name is already in the cache */
>> +
>> +	hash = msdos_fname_hash(name);
>> +	if (find_fname_in_cache(res, hash))
>> +		return 0;

> Huh?  How could that possibly work, seeing that
> 	* your hash function only looks at the first 8 characters

My understanding was that the maximum length of the name considered when
passed to msdos_format_name() was eight characters; see:

		while (walk - res < 8)

and

		for (walk = res; len && walk - res < 8; walk++) {

If that's an incorrect understanding, then yes, it definitely wouldn't
work. A larger, more computationally intensive hash function would be
required, which would most likely cancel out the improved lookup from
the cache.

> 	* your find_fname_in_cache() assumes that hash collisions
> are impossible, which is... unlikely, considering the nature of
> that hash function

If the names are 8 character limited, then logically any name with the
exact same set of characters would "collide" into the same formatted
name. Again, if I misunderstood the constraints on the filenames, then
yes, this is unnecessary.

> Out of curiosity, how have you tested that thing?

I've used it on my own FAT32 drives for profiling, run it through
kmemleak, ksan, some stress tests, etc. for a few weeks. Like I said, I
benchmarked it and it shaved about 0.2ms of time off my most common use
case.

Thanks.
Caleb B.

-- 
"Come now, and let us reason together," Says the LORD
    -- Isaiah 1:18a, NASB

Re: [PATCH 2/3] fat: add the msdos_format_name() filename cache

[Al Viro]

On Sun, Aug 29, 2021 at 05:11:56PM +0000, Caleb D.S. Brzezinski wrote:

> My understanding was that the maximum length of the name considered when
> passed to msdos_format_name() was eight characters; see:
> 
> 		while (walk - res < 8)
> 
> and
> 
> 		for (walk = res; len && walk - res < 8; walk++) {

Err...  You have noticed that the function does not end on that loop,
haven't you?  Exercise: figure out what that function does.  I.e.
what inputs are allowed and what outputs are produced.  You might
find some description of FAT directory layout to be useful...

> > 	* your find_fname_in_cache() assumes that hash collisions
> > are impossible, which is... unlikely, considering the nature of
> > that hash function
> 
> If the names are 8 character limited, then logically any name with the
> exact same set of characters would "collide" into the same formatted
> name.

Huh?  Collision is when two *different* values of argument yield the
same result.  What makes you assume that yours won't have any such
pairs shorter than 8 bytes?

[PATCH 3/3] fat: add hash machinery to relevant filesystem operations

[Caleb D.S. Brzezinski]

Add hash freeing functionality to the following functions which remove
or rename files:

msdos_rmdir()
msdos_unlink()
do_msdos_rename()

Whenever these functions are called, the memory associated with the
old, now obsolete filename is freed and dropped from the cache.

Signed-off-by: Caleb D.S. Brzezinski <calebdsb@protonmail.com>
---
 fs/fat/namei_msdos.c | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/fs/fat/namei_msdos.c b/fs/fat/namei_msdos.c
index f9d4f63c3..40a7d6df0 100644
--- a/fs/fat/namei_msdos.c
+++ b/fs/fat/namei_msdos.c
@@ -430,9 +430,11 @@ static int msdos_rmdir(struct inode *dir, struct dentry *dentry)
 	struct super_block *sb = dir->i_sb;
 	struct inode *inode = d_inode(dentry);
 	struct fat_slot_info sinfo;
+	u64 hash;
 	int err;
 
 	mutex_lock(&MSDOS_SB(sb)->s_lock);
+	hash = msdos_fname_hash(dentry->d_name.name);
 	err = fat_dir_empty(inode);
 	if (err)
 		goto out;
@@ -448,6 +450,7 @@ static int msdos_rmdir(struct inode *dir, struct dentry *dentry)
 	clear_nlink(inode);
 	fat_truncate_time(inode, NULL, S_CTIME);
 	fat_detach(inode);
+	drop_fname_from_cache(hash);
 out:
 	mutex_unlock(&MSDOS_SB(sb)->s_lock);
 	if (!err)
@@ -522,10 +525,12 @@ static int msdos_unlink(struct inode *dir, struct dentry *dentry)
 	struct inode *inode = d_inode(dentry);
 	struct super_block *sb = inode->i_sb;
 	struct fat_slot_info sinfo;
+	u64 hash;
 	int err;
 
 	mutex_lock(&MSDOS_SB(sb)->s_lock);
 	err = msdos_find(dir, dentry->d_name.name, dentry->d_name.len, &sinfo);
+	hash = msdos_fname_hash(dentry->d_name.name);
 	if (err)
 		goto out;
 
@@ -535,6 +540,8 @@ static int msdos_unlink(struct inode *dir, struct dentry *dentry)
 	clear_nlink(inode);
 	fat_truncate_time(inode, NULL, S_CTIME);
 	fat_detach(inode);
+	drop_fname_from_cache(hash);
+
 out:
 	mutex_unlock(&MSDOS_SB(sb)->s_lock);
 	if (!err)
@@ -670,6 +677,8 @@ static int do_msdos_rename(struct inode *old_dir, unsigned char *old_name,
 			drop_nlink(new_inode);
 		fat_truncate_time(new_inode, &ts, S_CTIME);
 	}
+	drop_fname_from_cache(msdos_fname_hash(old_name));
+
 out:
 	brelse(sinfo.bh);
 	brelse(dotdot_bh);
-- 
2.32.0