* [PATCH 0/3] fat: add a cache for msdos_format_name()
@ 2021-08-29 14:25 Caleb D.S. Brzezinski
2021-08-29 14:25 ` [PATCH 1/3] fat: define functions and data structures for a formatted name cache Caleb D.S. Brzezinski
` (2 more replies)
0 siblings, 3 replies; 11+ messages in thread
From: Caleb D.S. Brzezinski @ 2021-08-29 14:25 UTC (permalink / raw)
To: hirofumi; +Cc: linux-kernel, linux-fsdevel, 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
^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 1/3] fat: define functions and data structures for a formatted name cache
2021-08-29 14:25 [PATCH 0/3] fat: add a cache for msdos_format_name() Caleb D.S. Brzezinski
@ 2021-08-29 14:25 ` Caleb D.S. Brzezinski
2021-08-29 21:05 ` kernel test robot
2021-08-29 21:05 ` [RFC PATCH] fat: msdos_ncache can be static kernel test robot
2021-08-29 14:25 ` [PATCH 2/3] fat: add the msdos_format_name() filename cache Caleb D.S. Brzezinski
2021-08-29 14:25 ` [PATCH 3/3] fat: add hash machinery to relevant filesystem operations Caleb D.S. Brzezinski
2 siblings, 2 replies; 11+ messages in thread
From: Caleb D.S. Brzezinski @ 2021-08-29 14:25 UTC (permalink / raw)
To: hirofumi; +Cc: linux-kernel, linux-fsdevel, 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
^ permalink raw reply related [flat|nested] 11+ messages in thread
* [PATCH 2/3] fat: add the msdos_format_name() filename cache
2021-08-29 14:25 [PATCH 0/3] fat: add a cache for msdos_format_name() Caleb D.S. Brzezinski
2021-08-29 14:25 ` [PATCH 1/3] fat: define functions and data structures for a formatted name cache Caleb D.S. Brzezinski
@ 2021-08-29 14:25 ` Caleb D.S. Brzezinski
2021-08-29 15:11 ` Al Viro
2021-08-29 14:25 ` [PATCH 3/3] fat: add hash machinery to relevant filesystem operations Caleb D.S. Brzezinski
2 siblings, 1 reply; 11+ messages in thread
From: Caleb D.S. Brzezinski @ 2021-08-29 14:25 UTC (permalink / raw)
To: hirofumi; +Cc: linux-kernel, linux-fsdevel, 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
^ permalink raw reply related [flat|nested] 11+ messages in thread
* [PATCH 3/3] fat: add hash machinery to relevant filesystem operations
2021-08-29 14:25 [PATCH 0/3] fat: add a cache for msdos_format_name() Caleb D.S. Brzezinski
2021-08-29 14:25 ` [PATCH 1/3] fat: define functions and data structures for a formatted name cache Caleb D.S. Brzezinski
2021-08-29 14:25 ` [PATCH 2/3] fat: add the msdos_format_name() filename cache Caleb D.S. Brzezinski
@ 2021-08-29 14:25 ` Caleb D.S. Brzezinski
2 siblings, 0 replies; 11+ messages in thread
From: Caleb D.S. Brzezinski @ 2021-08-29 14:25 UTC (permalink / raw)
To: hirofumi; +Cc: linux-kernel, linux-fsdevel, 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
^ permalink raw reply related [flat|nested] 11+ messages in thread
* Re: [PATCH 2/3] fat: add the msdos_format_name() filename cache
2021-08-29 14:25 ` [PATCH 2/3] fat: add the msdos_format_name() filename cache Caleb D.S. Brzezinski
@ 2021-08-29 15:11 ` Al Viro
2021-08-29 15:26 ` Al Viro
2021-08-29 17:11 ` Caleb D.S. Brzezinski
0 siblings, 2 replies; 11+ messages in thread
From: Al Viro @ 2021-08-29 15:11 UTC (permalink / raw)
To: Caleb D.S. Brzezinski; +Cc: hirofumi, linux-kernel, linux-fsdevel
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?
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 2/3] fat: add the msdos_format_name() filename cache
2021-08-29 15:11 ` Al Viro
@ 2021-08-29 15:26 ` Al Viro
2021-08-29 17:19 ` Caleb D.S. Brzezinski
2021-08-29 17:11 ` Caleb D.S. Brzezinski
1 sibling, 1 reply; 11+ messages in thread
From: Al Viro @ 2021-08-29 15:26 UTC (permalink / raw)
To: Caleb D.S. Brzezinski; +Cc: hirofumi, linux-kernel, linux-fsdevel
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...
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 2/3] fat: add the msdos_format_name() filename cache
2021-08-29 15:11 ` Al Viro
2021-08-29 15:26 ` Al Viro
@ 2021-08-29 17:11 ` Caleb D.S. Brzezinski
2021-08-29 21:23 ` Al Viro
1 sibling, 1 reply; 11+ messages in thread
From: Caleb D.S. Brzezinski @ 2021-08-29 17:11 UTC (permalink / raw)
To: Al Viro; +Cc: hirofumi, linux-kernel, linux-fsdevel
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 2/3] fat: add the msdos_format_name() filename cache
2021-08-29 15:26 ` Al Viro
@ 2021-08-29 17:19 ` Caleb D.S. Brzezinski
0 siblings, 0 replies; 11+ messages in thread
From: Caleb D.S. Brzezinski @ 2021-08-29 17:19 UTC (permalink / raw)
To: Al Viro; +Cc: hirofumi, linux-kernel, linux-fsdevel
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 1/3] fat: define functions and data structures for a formatted name cache
2021-08-29 14:25 ` [PATCH 1/3] fat: define functions and data structures for a formatted name cache Caleb D.S. Brzezinski
@ 2021-08-29 21:05 ` kernel test robot
2021-08-29 21:05 ` [RFC PATCH] fat: msdos_ncache can be static kernel test robot
1 sibling, 0 replies; 11+ messages in thread
From: kernel test robot @ 2021-08-29 21:05 UTC (permalink / raw)
To: Caleb D.S. Brzezinski, hirofumi
Cc: kbuild-all, linux-kernel, linux-fsdevel, Caleb D.S. Brzezinski
[-- 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 --]
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RFC PATCH] fat: msdos_ncache can be static
2021-08-29 14:25 ` [PATCH 1/3] fat: define functions and data structures for a formatted name cache Caleb D.S. Brzezinski
2021-08-29 21:05 ` kernel test robot
@ 2021-08-29 21:05 ` kernel test robot
1 sibling, 0 replies; 11+ messages in thread
From: kernel test robot @ 2021-08-29 21:05 UTC (permalink / raw)
To: Caleb D.S. Brzezinski, hirofumi
Cc: kbuild-all, linux-kernel, linux-fsdevel, Caleb D.S. Brzezinski
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
^ permalink raw reply related [flat|nested] 11+ messages in thread
* Re: [PATCH 2/3] fat: add the msdos_format_name() filename cache
2021-08-29 17:11 ` Caleb D.S. Brzezinski
@ 2021-08-29 21:23 ` Al Viro
0 siblings, 0 replies; 11+ messages in thread
From: Al Viro @ 2021-08-29 21:23 UTC (permalink / raw)
To: Caleb D.S. Brzezinski; +Cc: hirofumi, linux-kernel, linux-fsdevel
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?
^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2021-08-29 21:23 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-08-29 14:25 [PATCH 0/3] fat: add a cache for msdos_format_name() Caleb D.S. Brzezinski
2021-08-29 14:25 ` [PATCH 1/3] fat: define functions and data structures for a formatted name cache Caleb D.S. Brzezinski
2021-08-29 21:05 ` kernel test robot
2021-08-29 21:05 ` [RFC PATCH] fat: msdos_ncache can be static kernel test robot
2021-08-29 14:25 ` [PATCH 2/3] fat: add the msdos_format_name() filename cache Caleb D.S. Brzezinski
2021-08-29 15:11 ` Al Viro
2021-08-29 15:26 ` Al Viro
2021-08-29 17:19 ` Caleb D.S. Brzezinski
2021-08-29 17:11 ` Caleb D.S. Brzezinski
2021-08-29 21:23 ` Al Viro
2021-08-29 14:25 ` [PATCH 3/3] fat: add hash machinery to relevant filesystem operations Caleb D.S. Brzezinski
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).