diff mbox series

[net-next,13/13] af_unix: Relax race in unix_autobind().

Message ID 20211106091712.15206-14-kuniyu@amazon.co.jp (mailing list archive)
State Superseded
Delegated to: Netdev Maintainers
Headers show
Series af_unix: Replace unix_table_lock with per-hash locks. | expand

Checks

Context Check Description
netdev/tree_selection success Clearly marked for net-next
netdev/fixes_present success Fixes tag not required for -next series
netdev/subject_prefix success Link
netdev/cover_letter success Series has a cover letter
netdev/patch_count success Link
netdev/header_inline success No static functions without inline keyword in header files
netdev/build_32bit success Errors and warnings before: 8 this patch: 8
netdev/cc_maintainers warning 1 maintainers not CCed: viro@zeniv.linux.org.uk
netdev/build_clang success Errors and warnings before: 0 this patch: 0
netdev/module_param success Was 0 now: 0
netdev/verify_signedoff success Signed-off-by tag matches author and committer
netdev/verify_fixes success No Fixes tag
netdev/build_allmodconfig_warn success Errors and warnings before: 8 this patch: 8
netdev/checkpatch warning CHECK: multiple assignments should be avoided
netdev/kdoc success Errors and warnings before: 0 this patch: 0
netdev/source_inline success Was 0 now: 0

Commit Message

Iwashima, Kuniyuki Nov. 6, 2021, 9:17 a.m. UTC
When we bind an AF_UNIX socket without a name specified, the kernel selects
an available one from 0x00000 to 0xFFFFF.  unix_autobind() starts searching
from a number in the 'static' variable and increments it after acquiring
two locks.

If multiple processes try autobind, they obtain the same lock and check if
a socket in the hash list has the same name.  If not, one process uses it,
and all except one end up retrying the _next_ number (actually not, it may
be incremented by the other processes).  The more we autobind sockets in
parallel, the longer the latency gets.  We can avoid such a race by
searching for a name from a random number.

These show latency in unix_autobind() while 64 CPUs are simultaneously
autobind-ing 1024 sockets for each.

  Without this patch:

     usec          : count     distribution
        0          : 1176     |***                                     |
        2          : 3655     |***********                             |
        4          : 4094     |*************                           |
        6          : 3831     |************                            |
        8          : 3829     |************                            |
        10         : 3844     |************                            |
        12         : 3638     |***********                             |
        14         : 2992     |*********                               |
        16         : 2485     |*******                                 |
        18         : 2230     |*******                                 |
        20         : 2095     |******                                  |
        22         : 1853     |*****                                   |
        24         : 1827     |*****                                   |
        26         : 1677     |*****                                   |
        28         : 1473     |****                                    |
        30         : 1573     |*****                                   |
        32         : 1417     |****                                    |
        34         : 1385     |****                                    |
        36         : 1345     |****                                    |
        38         : 1344     |****                                    |
        40         : 1200     |***                                     |

  With this patch:

     usec          : count     distribution
        0          : 1855     |******                                  |
        2          : 6464     |*********************                   |
        4          : 9936     |********************************        |
        6          : 12107    |****************************************|
        8          : 10441    |**********************************      |
        10         : 7264     |***********************                 |
        12         : 4254     |**************                          |
        14         : 2538     |********                                |
        16         : 1596     |*****                                   |
        18         : 1088     |***                                     |
        20         : 800      |**                                      |
        22         : 670      |**                                      |
        24         : 601      |*                                       |
        26         : 562      |*                                       |
        28         : 525      |*                                       |
        30         : 446      |*                                       |
        32         : 378      |*                                       |
        34         : 337      |*                                       |
        36         : 317      |*                                       |
        38         : 314      |*                                       |
        40         : 298      |                                        |

Signed-off-by: Kuniyuki Iwashima <kuniyu@amazon.co.jp>
---
 net/unix/af_unix.c | 21 +++++++++++----------
 1 file changed, 11 insertions(+), 10 deletions(-)

Comments

Eric Dumazet Nov. 8, 2021, 11:10 p.m. UTC | #1
On 11/6/21 2:17 AM, Kuniyuki Iwashima wrote:
> When we bind an AF_UNIX socket without a name specified, the kernel selects
> an available one from 0x00000 to 0xFFFFF.  unix_autobind() starts searching
> from a number in the 'static' variable and increments it after acquiring
> two locks.
> 
> If multiple processes try autobind, they obtain the same lock and check if
> a socket in the hash list has the same name.  If not, one process uses it,
> and all except one end up retrying the _next_ number (actually not, it may
> be incremented by the other processes).  The more we autobind sockets in
> parallel, the longer the latency gets.  We can avoid such a race by
> searching for a name from a random number.
> 
> These show latency in unix_autobind() while 64 CPUs are simultaneously
> autobind-ing 1024 sockets for each.
> 
>   Without this patch:
> 
>      usec          : count     distribution
>         0          : 1176     |***                                     |
>         2          : 3655     |***********                             |
>         4          : 4094     |*************                           |
>         6          : 3831     |************                            |
>         8          : 3829     |************                            |
>         10         : 3844     |************                            |
>         12         : 3638     |***********                             |
>         14         : 2992     |*********                               |
>         16         : 2485     |*******                                 |
>         18         : 2230     |*******                                 |
>         20         : 2095     |******                                  |
>         22         : 1853     |*****                                   |
>         24         : 1827     |*****                                   |
>         26         : 1677     |*****                                   |
>         28         : 1473     |****                                    |
>         30         : 1573     |*****                                   |
>         32         : 1417     |****                                    |
>         34         : 1385     |****                                    |
>         36         : 1345     |****                                    |
>         38         : 1344     |****                                    |
>         40         : 1200     |***                                     |
> 
>   With this patch:
> 
>      usec          : count     distribution
>         0          : 1855     |******                                  |
>         2          : 6464     |*********************                   |
>         4          : 9936     |********************************        |
>         6          : 12107    |****************************************|
>         8          : 10441    |**********************************      |
>         10         : 7264     |***********************                 |
>         12         : 4254     |**************                          |
>         14         : 2538     |********                                |
>         16         : 1596     |*****                                   |
>         18         : 1088     |***                                     |
>         20         : 800      |**                                      |
>         22         : 670      |**                                      |
>         24         : 601      |*                                       |
>         26         : 562      |*                                       |
>         28         : 525      |*                                       |
>         30         : 446      |*                                       |
>         32         : 378      |*                                       |
>         34         : 337      |*                                       |
>         36         : 317      |*                                       |
>         38         : 314      |*                                       |
>         40         : 298      |                                        |
> 
> Signed-off-by: Kuniyuki Iwashima <kuniyu@amazon.co.jp>
> ---
>  net/unix/af_unix.c | 21 +++++++++++----------
>  1 file changed, 11 insertions(+), 10 deletions(-)
> 
> diff --git a/net/unix/af_unix.c b/net/unix/af_unix.c
> index 643f0358bf7a..55d570b23475 100644
> --- a/net/unix/af_unix.c
> +++ b/net/unix/af_unix.c
> @@ -1075,8 +1075,7 @@ static int unix_autobind(struct sock *sk)
>  	unsigned int new_hash, old_hash = sk->sk_hash;
>  	struct unix_sock *u = unix_sk(sk);
>  	struct unix_address *addr;
> -	unsigned int retries = 0;
> -	static u32 ordernum = 1;
> +	u32 initnum, ordernum;
>  	int err;
>  
>  	err = mutex_lock_interruptible(&u->bindlock);
> @@ -1091,31 +1090,33 @@ static int unix_autobind(struct sock *sk)
>  	if (!addr)
>  		goto out;
>  
> +	addr->len = offsetof(struct sockaddr_un, sun_path) + 6;
>  	addr->name->sun_family = AF_UNIX;
>  	refcount_set(&addr->refcnt, 1);
>  
> +	initnum = ordernum = prandom_u32();
>  retry:
> -	addr->len = sprintf(addr->name->sun_path + 1, "%05x", ordernum) +
> -		offsetof(struct sockaddr_un, sun_path) + 1;
> +	ordernum = (ordernum + 1) & 0xFFFFF;
> +	sprintf(addr->name->sun_path + 1, "%05x", ordernum);
>  
>  	new_hash = unix_abstract_hash(addr->name, addr->len, sk->sk_type);
>  	unix_table_double_lock(old_hash, new_hash);
> -	ordernum = (ordernum+1)&0xFFFFF;
>  
>  	if (__unix_find_socket_byname(sock_net(sk), addr->name, addr->len, new_hash)) {
>  		unix_table_double_unlock(old_hash, new_hash);
>  
> -		/*
> -		 * __unix_find_socket_byname() may take long time if many names
> +		/* __unix_find_socket_byname() may take long time if many names
>  		 * are already in use.
>  		 */
>  		cond_resched();
> -		/* Give up if all names seems to be in use. */
> -		if (retries++ == 0xFFFFF) {
> +
> +		if (ordernum == initnum) {

Infinite loop alert, in the likely case initnum >= 2^16

> +			/* Give up if all names seems to be in use. */
>  			err = -ENOSPC;
> -			kfree(addr);
> +			unix_release_addr(addr);
>  			goto out;
>  		}
> +
>  		goto retry;
>  	}
>  
>
Iwashima, Kuniyuki Nov. 9, 2021, 2:24 a.m. UTC | #2
From:   Eric Dumazet <eric.dumazet@gmail.com>
Date:   Mon, 8 Nov 2021 15:10:24 -0800
> On 11/6/21 2:17 AM, Kuniyuki Iwashima wrote:
> > When we bind an AF_UNIX socket without a name specified, the kernel selects
> > an available one from 0x00000 to 0xFFFFF.  unix_autobind() starts searching
> > from a number in the 'static' variable and increments it after acquiring
> > two locks.
> > 
> > If multiple processes try autobind, they obtain the same lock and check if
> > a socket in the hash list has the same name.  If not, one process uses it,
> > and all except one end up retrying the _next_ number (actually not, it may
> > be incremented by the other processes).  The more we autobind sockets in
> > parallel, the longer the latency gets.  We can avoid such a race by
> > searching for a name from a random number.
> > 
> > These show latency in unix_autobind() while 64 CPUs are simultaneously
> > autobind-ing 1024 sockets for each.
> > 
> >   Without this patch:
> > 
> >      usec          : count     distribution
> >         0          : 1176     |***                                     |
> >         2          : 3655     |***********                             |
> >         4          : 4094     |*************                           |
> >         6          : 3831     |************                            |
> >         8          : 3829     |************                            |
> >         10         : 3844     |************                            |
> >         12         : 3638     |***********                             |
> >         14         : 2992     |*********                               |
> >         16         : 2485     |*******                                 |
> >         18         : 2230     |*******                                 |
> >         20         : 2095     |******                                  |
> >         22         : 1853     |*****                                   |
> >         24         : 1827     |*****                                   |
> >         26         : 1677     |*****                                   |
> >         28         : 1473     |****                                    |
> >         30         : 1573     |*****                                   |
> >         32         : 1417     |****                                    |
> >         34         : 1385     |****                                    |
> >         36         : 1345     |****                                    |
> >         38         : 1344     |****                                    |
> >         40         : 1200     |***                                     |
> > 
> >   With this patch:
> > 
> >      usec          : count     distribution
> >         0          : 1855     |******                                  |
> >         2          : 6464     |*********************                   |
> >         4          : 9936     |********************************        |
> >         6          : 12107    |****************************************|
> >         8          : 10441    |**********************************      |
> >         10         : 7264     |***********************                 |
> >         12         : 4254     |**************                          |
> >         14         : 2538     |********                                |
> >         16         : 1596     |*****                                   |
> >         18         : 1088     |***                                     |
> >         20         : 800      |**                                      |
> >         22         : 670      |**                                      |
> >         24         : 601      |*                                       |
> >         26         : 562      |*                                       |
> >         28         : 525      |*                                       |
> >         30         : 446      |*                                       |
> >         32         : 378      |*                                       |
> >         34         : 337      |*                                       |
> >         36         : 317      |*                                       |
> >         38         : 314      |*                                       |
> >         40         : 298      |                                        |
> > 
> > Signed-off-by: Kuniyuki Iwashima <kuniyu@amazon.co.jp>
> > ---
> >  net/unix/af_unix.c | 21 +++++++++++----------
> >  1 file changed, 11 insertions(+), 10 deletions(-)
> > 
> > diff --git a/net/unix/af_unix.c b/net/unix/af_unix.c
> > index 643f0358bf7a..55d570b23475 100644
> > --- a/net/unix/af_unix.c
> > +++ b/net/unix/af_unix.c
> > @@ -1075,8 +1075,7 @@ static int unix_autobind(struct sock *sk)
> >  	unsigned int new_hash, old_hash = sk->sk_hash;
> >  	struct unix_sock *u = unix_sk(sk);
> >  	struct unix_address *addr;
> > -	unsigned int retries = 0;
> > -	static u32 ordernum = 1;
> > +	u32 initnum, ordernum;
> >  	int err;
> >  
> >  	err = mutex_lock_interruptible(&u->bindlock);
> > @@ -1091,31 +1090,33 @@ static int unix_autobind(struct sock *sk)
> >  	if (!addr)
> >  		goto out;
> >  
> > +	addr->len = offsetof(struct sockaddr_un, sun_path) + 6;
> >  	addr->name->sun_family = AF_UNIX;
> >  	refcount_set(&addr->refcnt, 1);
> >  
> > +	initnum = ordernum = prandom_u32();
> >  retry:
> > -	addr->len = sprintf(addr->name->sun_path + 1, "%05x", ordernum) +
> > -		offsetof(struct sockaddr_un, sun_path) + 1;
> > +	ordernum = (ordernum + 1) & 0xFFFFF;
> > +	sprintf(addr->name->sun_path + 1, "%05x", ordernum);
> >  
> >  	new_hash = unix_abstract_hash(addr->name, addr->len, sk->sk_type);
> >  	unix_table_double_lock(old_hash, new_hash);
> > -	ordernum = (ordernum+1)&0xFFFFF;
> >  
> >  	if (__unix_find_socket_byname(sock_net(sk), addr->name, addr->len, new_hash)) {
> >  		unix_table_double_unlock(old_hash, new_hash);
> >  
> > -		/*
> > -		 * __unix_find_socket_byname() may take long time if many names
> > +		/* __unix_find_socket_byname() may take long time if many names
> >  		 * are already in use.
> >  		 */
> >  		cond_resched();
> > -		/* Give up if all names seems to be in use. */
> > -		if (retries++ == 0xFFFFF) {
> > +
> > +		if (ordernum == initnum) {
> 
> Infinite loop alert, in the likely case initnum >= 2^16

Good catch!
Thank you for reviewing.

And I'm sorry for distraction in the merge window.
I'll post v2 after that.


> 
> > +			/* Give up if all names seems to be in use. */
> >  			err = -ENOSPC;
> > -			kfree(addr);
> > +			unix_release_addr(addr);
> >  			goto out;
> >  		}
> > +
> >  		goto retry;
> >  	}
> >  
> >
diff mbox series

Patch

diff --git a/net/unix/af_unix.c b/net/unix/af_unix.c
index 643f0358bf7a..55d570b23475 100644
--- a/net/unix/af_unix.c
+++ b/net/unix/af_unix.c
@@ -1075,8 +1075,7 @@  static int unix_autobind(struct sock *sk)
 	unsigned int new_hash, old_hash = sk->sk_hash;
 	struct unix_sock *u = unix_sk(sk);
 	struct unix_address *addr;
-	unsigned int retries = 0;
-	static u32 ordernum = 1;
+	u32 initnum, ordernum;
 	int err;
 
 	err = mutex_lock_interruptible(&u->bindlock);
@@ -1091,31 +1090,33 @@  static int unix_autobind(struct sock *sk)
 	if (!addr)
 		goto out;
 
+	addr->len = offsetof(struct sockaddr_un, sun_path) + 6;
 	addr->name->sun_family = AF_UNIX;
 	refcount_set(&addr->refcnt, 1);
 
+	initnum = ordernum = prandom_u32();
 retry:
-	addr->len = sprintf(addr->name->sun_path + 1, "%05x", ordernum) +
-		offsetof(struct sockaddr_un, sun_path) + 1;
+	ordernum = (ordernum + 1) & 0xFFFFF;
+	sprintf(addr->name->sun_path + 1, "%05x", ordernum);
 
 	new_hash = unix_abstract_hash(addr->name, addr->len, sk->sk_type);
 	unix_table_double_lock(old_hash, new_hash);
-	ordernum = (ordernum+1)&0xFFFFF;
 
 	if (__unix_find_socket_byname(sock_net(sk), addr->name, addr->len, new_hash)) {
 		unix_table_double_unlock(old_hash, new_hash);
 
-		/*
-		 * __unix_find_socket_byname() may take long time if many names
+		/* __unix_find_socket_byname() may take long time if many names
 		 * are already in use.
 		 */
 		cond_resched();
-		/* Give up if all names seems to be in use. */
-		if (retries++ == 0xFFFFF) {
+
+		if (ordernum == initnum) {
+			/* Give up if all names seems to be in use. */
 			err = -ENOSPC;
-			kfree(addr);
+			unix_release_addr(addr);
 			goto out;
 		}
+
 		goto retry;
 	}