On Mon, Mar 22, 2021 at 07:38:15PM +0100, Aurélien Aptel wrote:
> Al Viro <viro@xxxxxxxxxxxxxxxxxx> writes:
> > Either the key comparison or the hash function is wrong here. *IF* something
> > external guarantees the full match, we don't need strcasecmp() - strcmp()
> > would work. Otherwise, the hash function needs to be changed.
>
> I think here we need to make the hash case-insensitive.
>
> Perhaps calling jhash() with lower-cased bytes like so (pseudo-code):
[snip]
Then you really do not want to recalculate it again and again.
Look:
__lookup_cache_entry() calculates it for the key
lookup_cache_entry() contains
if (cnt < 3) {
h = cache_entry_hash(path, strlen(path));
ce = __lookup_cache_entry(path);
goto out;
}
... and
ce = __lookup_cache_entry(npath);
if (!IS_ERR(ce)) {
h = cache_entry_hash(npath, strlen(npath));
break;
}
(in a loop, at that)
Take a look at that the aforementioned loop:
h = cache_entry_hash(npath, strlen(npath));
e = npath + strlen(npath) - 1;
while (e > s) {
char tmp;
/* skip separators */
while (e > s && *e == sep)
e--;
if (e == s)
goto out;
tmp = *(e+1);
*(e+1) = 0;
ce = __lookup_cache_entry(npath);
if (!IS_ERR(ce)) {
h = cache_entry_hash(npath, strlen(npath));
break;
}
*(e+1) = tmp;
/* backward until separator */
while (e > s && *e != sep)
e--;
}
We call __lookup_cache_entry() for shorter and shorter prefixes of
npath. They get NUL-terminated for the duration of __lookup_cache_entry(),
then reverted to the original. What for? cache_entry_hash() already
gets length as explicit argument. And strcasecmp() is trivially
replaced with strncasecmp().
Just have __lookup_cache_entry() take key, hash and length. Then it
turns into
len = e + 1 - s;
hash = cache_entry_hash(path, len);
ce = __lookup_cache_entry(path, hash, len);
if (!IS_ERR(ce)) {
h = hash;
break;
}
and we are done. No need to modify npath contents, undo the modifications
or *have* npath in the first place - the reason the current variant needs to
copy path is precisely that it goes to those contortions.
Incidentally, you also have a problem with trailing separators - anything
with those inserted into hash won't be found by lookup_cache_entry(),
since you trim the trailing separators from the key on searches.
