[PATCH] fs: improve codegen in link_path_walk()

[PATCH] fs: improve codegen in link_path_walk()

[Mateusz Guzik]

Looking at the asm produced by gcc 13.3 for x86-64:
1. may_lookup() usage was not optimized for succeeding, despite the
   routine being inlined and rightfully starting with likely(!err)
2. the compiler assumed the path will have an indefinite amount of
   slashes to skip, after which the result will be an empty name

As such:
1. predict may_lookup() succeeding
2. check for one slash, no explicit predicts. do roll forward with
   skipping more slashes while predicting there is only one
3. predict the path to find was not a mere slash

This also has a side effect of shrinking the file:
add/remove: 1/1 grow/shrink: 0/3 up/down: 934/-1012 (-78)
Function                                     old     new   delta
link_path_walk                                 -     934    +934
path_parentat                                138     112     -26
path_openat                                 4864    4823     -41
path_lookupat                                418     374     -44
link_path_walk.part.constprop                901       -    -901
Total: Before=46639, After=46561, chg -0.17%

Signed-off-by: Mateusz Guzik <mjguzik@gmail.com>
---

I'm looking at skipping perm checks with an "everybody can MAY_EXEC and
there are no acls" bit for opflags. This crapper is a side effect of
straighetning out the code before I get there.

 fs/namei.c | 11 +++++++----
 1 file changed, 7 insertions(+), 4 deletions(-)

diff --git a/fs/namei.c b/fs/namei.c
index 360a86ca1f02..40a636bbfa0c 100644
--- a/fs/namei.c
+++ b/fs/namei.c
@@ -2424,9 +2424,12 @@ static int link_path_walk(const char *name, struct nameidata *nd)
 	nd->flags |= LOOKUP_PARENT;
 	if (IS_ERR(name))
 		return PTR_ERR(name);
-	while (*name=='/')
-		name++;
-	if (!*name) {
+	if (*name == '/') {
+		do {
+			name++;
+		} while (unlikely(*name == '/'));
+	}
+	if (unlikely(!*name)) {
 		nd->dir_mode = 0; // short-circuit the 'hardening' idiocy
 		return 0;
 	}
@@ -2439,7 +2442,7 @@ static int link_path_walk(const char *name, struct nameidata *nd)
 
 		idmap = mnt_idmap(nd->path.mnt);
 		err = may_lookup(idmap, nd);
-		if (err)
+		if (unlikely(err))
 			return err;
 
 		nd->last.name = name;
-- 
2.43.0

Re: [PATCH] fs: improve codegen in link_path_walk()

[Christian Brauner]

On Sat, 12 Apr 2025 13:09:35 +0200, Mateusz Guzik wrote:
> Looking at the asm produced by gcc 13.3 for x86-64:
> 1. may_lookup() usage was not optimized for succeeding, despite the
>    routine being inlined and rightfully starting with likely(!err)
> 2. the compiler assumed the path will have an indefinite amount of
>    slashes to skip, after which the result will be an empty name
> 
> As such:
> 1. predict may_lookup() succeeding
> 2. check for one slash, no explicit predicts. do roll forward with
>    skipping more slashes while predicting there is only one
> 3. predict the path to find was not a mere slash
> 
> [...]

Applied to the vfs-6.16.misc branch of the vfs/vfs.git tree.
Patches in the vfs-6.16.misc branch should appear in linux-next soon.

Please report any outstanding bugs that were missed during review in a
new review to the original patch series allowing us to drop it.

It's encouraged to provide Acked-bys and Reviewed-bys even though the
patch has now been applied. If possible patch trailers will be updated.

Note that commit hashes shown below are subject to change due to rebase,
trailer updates or similar. If in doubt, please check the listed branch.

tree:   https://git.kernel.org/pub/scm/linux/kernel/git/vfs/vfs.git
branch: vfs-6.16.misc

[1/1] fs: improve codegen in link_path_walk()
      https://git.kernel.org/vfs/vfs/c/80cf41f567f5

Re: [PATCH] fs: improve codegen in link_path_walk()

[Jan Kara]

On Sat 12-04-25 13:09:35, Mateusz Guzik wrote:
> Looking at the asm produced by gcc 13.3 for x86-64:
> 1. may_lookup() usage was not optimized for succeeding, despite the
>    routine being inlined and rightfully starting with likely(!err)
> 2. the compiler assumed the path will have an indefinite amount of
>    slashes to skip, after which the result will be an empty name
> 
> As such:
> 1. predict may_lookup() succeeding
> 2. check for one slash, no explicit predicts. do roll forward with
>    skipping more slashes while predicting there is only one
> 3. predict the path to find was not a mere slash
> 
> This also has a side effect of shrinking the file:
> add/remove: 1/1 grow/shrink: 0/3 up/down: 934/-1012 (-78)
> Function                                     old     new   delta
> link_path_walk                                 -     934    +934
> path_parentat                                138     112     -26
> path_openat                                 4864    4823     -41
> path_lookupat                                418     374     -44
> link_path_walk.part.constprop                901       -    -901
> Total: Before=46639, After=46561, chg -0.17%
> 
> Signed-off-by: Mateusz Guzik <mjguzik@gmail.com>

Looks sensible. Feel free to add:

Reviewed-by: Jan Kara <jack@suse.cz>

								Honza

> ---
> 
> I'm looking at skipping perm checks with an "everybody can MAY_EXEC and
> there are no acls" bit for opflags. This crapper is a side effect of
> straighetning out the code before I get there.
> 
>  fs/namei.c | 11 +++++++----
>  1 file changed, 7 insertions(+), 4 deletions(-)
> 
> diff --git a/fs/namei.c b/fs/namei.c
> index 360a86ca1f02..40a636bbfa0c 100644
> --- a/fs/namei.c
> +++ b/fs/namei.c
> @@ -2424,9 +2424,12 @@ static int link_path_walk(const char *name, struct nameidata *nd)
>  	nd->flags |= LOOKUP_PARENT;
>  	if (IS_ERR(name))
>  		return PTR_ERR(name);
> -	while (*name=='/')
> -		name++;
> -	if (!*name) {
> +	if (*name == '/') {
> +		do {
> +			name++;
> +		} while (unlikely(*name == '/'));
> +	}
> +	if (unlikely(!*name)) {
>  		nd->dir_mode = 0; // short-circuit the 'hardening' idiocy
>  		return 0;
>  	}
> @@ -2439,7 +2442,7 @@ static int link_path_walk(const char *name, struct nameidata *nd)
>  
>  		idmap = mnt_idmap(nd->path.mnt);
>  		err = may_lookup(idmap, nd);
> -		if (err)
> +		if (unlikely(err))
>  			return err;
>  
>  		nd->last.name = name;
> -- 
> 2.43.0
> 
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR