To add overlayfs support casefold filesystems, create a new function
ovl_strcmp() with support for casefold names.

If the ovl_cache_entry have stored a casefold name, use it and create
a casfold version of the name that is going to be compared to.

For the casefold support, just comparing the strings does not work
because we need the dentry enconding, so make this function find the
equivalent dentry for a giving directory, if any.

As this function is used for search and insertion in the red-black tree,
that means that the tree node keys are going to be the casefolded
version of the dentry's names. Otherwise, the search would not work for
case-insensitive mount points.

For the non-casefold names, nothing changes.

Signed-off-by: André Almeida <andrealmeid@igalia.com>
---
I wonder what should be done here if kmalloc fails, if the strcmp()
should fail as well or just fallback to the normal name?
---
 fs/overlayfs/readdir.c | 42 ++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 40 insertions(+), 2 deletions(-)

diff --git a/fs/overlayfs/readdir.c b/fs/overlayfs/readdir.c
index 83bca1bcb0488461b08effa70b32ff2fefba134e..1b8eb10e72a229ade40d18795746d3c779797a06 100644
--- a/fs/overlayfs/readdir.c
+++ b/fs/overlayfs/readdir.c
@@ -72,6 +72,44 @@ static struct ovl_cache_entry *ovl_cache_entry_from_node(struct rb_node *n)
 	return rb_entry(n, struct ovl_cache_entry, node);
 }
 
+/*
+ * Compare a string with a cache entry, with support for casefold names.
+ */
+static int ovl_strcmp(const char *str, struct ovl_cache_entry *p, int len)
+{
+
+	const struct qstr qstr = { .name = str, .len = len };
+	const char *p_name = p->name, *name = str;
+	char *dst = NULL;
+	int cmp, cf_len;
+
+	if (p->cf_name)
+		p_name = p->cf_name;
+
+	if (p->map && !is_dot_dotdot(str, len)) {
+		dst = kmalloc(OVL_NAME_LEN, GFP_KERNEL);
+
+		/*
+		 * strcmp can't fail, so we fallback to the use the original
+		 * name
+		 */
+		if (dst) {
+			cf_len = utf8_casefold(p->map, &qstr, dst, OVL_NAME_LEN);
+
+			if (cf_len > 0) {
+				name = dst;
+				dst[cf_len] = '\0';
+			}
+		}
+	}
+
+	cmp = strncmp(name, p_name, cf_len);
+
+	kfree(dst);
+
+	return cmp;
+}
+
 static bool ovl_cache_entry_find_link(const char *name, int len,
 				      struct rb_node ***link,
 				      struct rb_node **parent)
@@ -85,7 +123,7 @@ static bool ovl_cache_entry_find_link(const char *name, int len,
 
 		*parent = *newp;
 		tmp = ovl_cache_entry_from_node(*newp);
-		cmp = strncmp(name, tmp->name, len);
+		cmp = ovl_strcmp(name, tmp, len);
 		if (cmp > 0)
 			newp = &tmp->node.rb_right;
 		else if (cmp < 0 || len < tmp->len)
@@ -107,7 +145,7 @@ static struct ovl_cache_entry *ovl_cache_entry_find(struct rb_root *root,
 	while (node) {
 		struct ovl_cache_entry *p = ovl_cache_entry_from_node(node);
 
-		cmp = strncmp(name, p->name, len);
+		cmp = ovl_strcmp(name, p, len);
 		if (cmp > 0)
 			node = p->node.rb_right;
 		else if (cmp < 0 || len < p->len)

-- 
2.50.1

On Tue, Aug 05, 2025 at 12:09:06AM -0300, André Almeida wrote:

> +static int ovl_strcmp(const char *str, struct ovl_cache_entry *p, int len)

> +	if (p->map && !is_dot_dotdot(str, len)) {
> +		dst = kmalloc(OVL_NAME_LEN, GFP_KERNEL);

...`

> +	kfree(dst);
> +
> +	return cmp;
> +}
> +

> @@ -107,7 +145,7 @@ static struct ovl_cache_entry *ovl_cache_entry_find(struct rb_root *root,
>  	while (node) {
>  		struct ovl_cache_entry *p = ovl_cache_entry_from_node(node);
>  
> -		cmp = strncmp(name, p->name, len);
> +		cmp = ovl_strcmp(name, p, len);
>  		if (cmp > 0)
>  			node = p->node.rb_right;
>  		else if (cmp < 0 || len < p->len)

Am I misreading that, or do really we get a kmalloc()/kfree() for each
sodding tree node we traverse on rbtree lookup here?

Em 05/08/2025 02:08, Al Viro escreveu:
> On Tue, Aug 05, 2025 at 12:09:06AM -0300, André Almeida wrote:
> 
>> +static int ovl_strcmp(const char *str, struct ovl_cache_entry *p, int len)
> 
>> +	if (p->map && !is_dot_dotdot(str, len)) {
>> +		dst = kmalloc(OVL_NAME_LEN, GFP_KERNEL);
> 
> ...`
> 
>> +	kfree(dst);
>> +
>> +	return cmp;
>> +}
>> +
> 
>> @@ -107,7 +145,7 @@ static struct ovl_cache_entry *ovl_cache_entry_find(struct rb_root *root,
>>   	while (node) {
>>   		struct ovl_cache_entry *p = ovl_cache_entry_from_node(node);
>>   
>> -		cmp = strncmp(name, p->name, len);
>> +		cmp = ovl_strcmp(name, p, len);
>>   		if (cmp > 0)
>>   			node = p->node.rb_right;
>>   		else if (cmp < 0 || len < p->len)
> 
> Am I misreading that, or do really we get a kmalloc()/kfree() for each
> sodding tree node we traverse on rbtree lookup here?

Yes, this is what's implemented here, as it is. Alternatively, I could 
allocate one buffer prior to the rbtree search/insert to be reused, and 
free it later... I going to add that for the v3.

André Almeida <andrealmeid@igalia.com> writes:

> To add overlayfs support casefold filesystems, create a new function
> ovl_strcmp() with support for casefold names.
>
> If the ovl_cache_entry have stored a casefold name, use it and create
> a casfold version of the name that is going to be compared to.
>
> For the casefold support, just comparing the strings does not work
> because we need the dentry enconding, so make this function find the
> equivalent dentry for a giving directory, if any.
>
> As this function is used for search and insertion in the red-black tree,
> that means that the tree node keys are going to be the casefolded
> version of the dentry's names. Otherwise, the search would not work for
> case-insensitive mount points.
>
> For the non-casefold names, nothing changes.
>
> Signed-off-by: André Almeida <andrealmeid@igalia.com>
> ---
> I wonder what should be done here if kmalloc fails, if the strcmp()
> should fail as well or just fallback to the normal name?
> ---
>  fs/overlayfs/readdir.c | 42 ++++++++++++++++++++++++++++++++++++++++--
>  1 file changed, 40 insertions(+), 2 deletions(-)
>
> diff --git a/fs/overlayfs/readdir.c b/fs/overlayfs/readdir.c
> index 83bca1bcb0488461b08effa70b32ff2fefba134e..1b8eb10e72a229ade40d18795746d3c779797a06 100644
> --- a/fs/overlayfs/readdir.c
> +++ b/fs/overlayfs/readdir.c
> @@ -72,6 +72,44 @@ static struct ovl_cache_entry *ovl_cache_entry_from_node(struct rb_node *n)
>  	return rb_entry(n, struct ovl_cache_entry, node);
>  }
>  
> +/*
> + * Compare a string with a cache entry, with support for casefold names.
> + */
> +static int ovl_strcmp(const char *str, struct ovl_cache_entry *p, int len)
> +{

Why do you need to re-casefold str on every call to ovl_strcmp?  Isn't
it done in a loop while walking the rbtree with a constant "str" (i.e.,
the name being added, see ovl_cache_entry_find)? Can't you do it once,
outside of ovl_strcmp? This way you don't repeatedly allocate/free
memory for each node of the tree (as Viro mentioned), and you don't have
to deal with kmalloc failures here.

> +
> +	const struct qstr qstr = { .name = str, .len = len };
> +	const char *p_name = p->name, *name = str;
> +	char *dst = NULL;
> +	int cmp, cf_len;
> +
> +	if (p->cf_name)
> +		p_name = p->cf_name;

This should check IS_ENABLED(CONFIG_UNICODE) so it can be
compiled out by anyone doing CONFIG_UNICODE=n

> +
> +	if (p->map && !is_dot_dotdot(str, len)) {
> +		dst = kmalloc(OVL_NAME_LEN, GFP_KERNEL);
> +
> +		/*
> +		 * strcmp can't fail, so we fallback to the use the original
> +		 * name
> +		 */
> +		if (dst) {
> +			cf_len = utf8_casefold(p->map, &qstr, dst, OVL_NAME_LEN);

utf8_casefold can fail, as you know and checked.  But if it does, a
negative cf_len is passed to strncmp and cast to a very high
value.

> +
> +			if (cf_len > 0) {
> +				name = dst;
> +				dst[cf_len] = '\0';
> +			}

utf8_casefold ensures the string is NULL-terminated on success already.

> +		}
> +	}
> +
> +	cmp = strncmp(name, p_name, cf_len);
> +
> +	kfree(dst);
> +
> +	return cmp;
> +}
> +
>  static bool ovl_cache_entry_find_link(const char *name, int len,
>  				      struct rb_node ***link,
>  				      struct rb_node **parent)
> @@ -85,7 +123,7 @@ static bool ovl_cache_entry_find_link(const char *name, int len,
>  
>  		*parent = *newp;
>  		tmp = ovl_cache_entry_from_node(*newp);
> -		cmp = strncmp(name, tmp->name, len);
> +		cmp = ovl_strcmp(name, tmp, len);
>  		if (cmp > 0)
>  			newp = &tmp->node.rb_right;
>  		else if (cmp < 0 || len < tmp->len)
> @@ -107,7 +145,7 @@ static struct ovl_cache_entry *ovl_cache_entry_find(struct rb_root *root,
>  	while (node) {
>  		struct ovl_cache_entry *p = ovl_cache_entry_from_node(node);
>  
> -		cmp = strncmp(name, p->name, len);
> +		cmp = ovl_strcmp(name, p, len);
>  		if (cmp > 0)
>  			node = p->node.rb_right;
>  		else if (cmp < 0 || len < p->len)

-- 
Gabriel Krisman Bertazi

Hi Gabriel!

Em 05/08/2025 11:56, Gabriel Krisman Bertazi escreveu:
> André Almeida <andrealmeid@igalia.com> writes:
> 
>> To add overlayfs support casefold filesystems, create a new function
>> ovl_strcmp() with support for casefold names.
>>
>> If the ovl_cache_entry have stored a casefold name, use it and create
>> a casfold version of the name that is going to be compared to.
>>
>> For the casefold support, just comparing the strings does not work
>> because we need the dentry enconding, so make this function find the
>> equivalent dentry for a giving directory, if any.
>>
>> As this function is used for search and insertion in the red-black tree,
>> that means that the tree node keys are going to be the casefolded
>> version of the dentry's names. Otherwise, the search would not work for
>> case-insensitive mount points.
>>
>> For the non-casefold names, nothing changes.
>>
>> Signed-off-by: André Almeida <andrealmeid@igalia.com>
>> ---
>> I wonder what should be done here if kmalloc fails, if the strcmp()
>> should fail as well or just fallback to the normal name?
>> ---
>>   fs/overlayfs/readdir.c | 42 ++++++++++++++++++++++++++++++++++++++++--
>>   1 file changed, 40 insertions(+), 2 deletions(-)
>>
>> diff --git a/fs/overlayfs/readdir.c b/fs/overlayfs/readdir.c
>> index 83bca1bcb0488461b08effa70b32ff2fefba134e..1b8eb10e72a229ade40d18795746d3c779797a06 100644
>> --- a/fs/overlayfs/readdir.c
>> +++ b/fs/overlayfs/readdir.c
>> @@ -72,6 +72,44 @@ static struct ovl_cache_entry *ovl_cache_entry_from_node(struct rb_node *n)
>>   	return rb_entry(n, struct ovl_cache_entry, node);
>>   }
>>   
>> +/*
>> + * Compare a string with a cache entry, with support for casefold names.
>> + */
>> +static int ovl_strcmp(const char *str, struct ovl_cache_entry *p, int len)
>> +{
> 
> Why do you need to re-casefold str on every call to ovl_strcmp?  Isn't
> it done in a loop while walking the rbtree with a constant "str" (i.e.,
> the name being added, see ovl_cache_entry_find)? Can't you do it once,
> outside of ovl_strcmp? This way you don't repeatedly allocate/free
> memory for each node of the tree (as Viro mentioned), and you don't have
> to deal with kmalloc failures here.
> 

Yes, that's a more reasonable approach, I will do it for v3

>> +
>> +	const struct qstr qstr = { .name = str, .len = len };
>> +	const char *p_name = p->name, *name = str;
>> +	char *dst = NULL;
>> +	int cmp, cf_len;
>> +
>> +	if (p->cf_name)
>> +		p_name = p->cf_name;
> 
> This should check IS_ENABLED(CONFIG_UNICODE) so it can be
> compiled out by anyone doing CONFIG_UNICODE=n
> 
>> +
>> +	if (p->map && !is_dot_dotdot(str, len)) {
>> +		dst = kmalloc(OVL_NAME_LEN, GFP_KERNEL);
>> +
>> +		/*
>> +		 * strcmp can't fail, so we fallback to the use the original
>> +		 * name
>> +		 */
>> +		if (dst) {
>> +			cf_len = utf8_casefold(p->map, &qstr, dst, OVL_NAME_LEN);
> 
> utf8_casefold can fail, as you know and checked.  But if it does, a
> negative cf_len is passed to strncmp and cast to a very high
> value.
> 

ops, that's right, thanks for the feedback!