Skip to contentSkip to conversation

Add a bhash2 table hashed by port + address

PATCH Superseded Joanne Koong 2 participants 7 messages May 10, 2022

Subsystems (5)

v2 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

v2 cover Add a bhash2 table hashed by port + address

This patchset proposes adding a bhash2 table that hashes by port and address. The motivation behind bhash2 is to expedite bind requests in situations where the port has many sockets in its bhash table entry, which makes checking bind conflicts costly especially given that we acquire the table entry spinlock while doing so, which can cause softirq cpu lockups and can prevent new tcp connections.

We ran into this problem at Meta where the traffic team binds a large number of IPs to port 443 and the bind() call took a significant amount of time which led to cpu softirq lockups, which caused packet drops and other failures on the machine

The patches are as follows:
1/2 - Adds a second bhash table (bhash2) hashed by port and address 2/2 - Adds a test for timing how long an additional bind request takes when the bhash entry is populated

When experimentally testing this on a local server for ~24k sockets bound to the port, the results seen were:

ipv4:
before - 0.002317 seconds
with bhash2 - 0.000018 seconds

ipv6:
before - 0.002431 seconds
with bhash2 - 0.000021 seconds

v1 -> v2:
v1:
https://lore.kernel.org/netdev/[email protected]/

* Attached test for timing bind request

Joanne Koong (2):
net: Add a second bind table hashed by port and address
selftests: Add test for timing a bind request to a port with a
populated bhash entry

 include/net/inet_connection_sock.h            |   3 +
 include/net/inet_hashtables.h                 |  56 ++++-
 include/net/sock.h                            |  14 ++
 net/dccp/proto.c                              |  14 +-
 net/ipv4/inet_connection_sock.c               | 227 +++++++++++++-----
 net/ipv4/inet_hashtables.c                    | 188 ++++++++++++++-
 net/ipv4/tcp.c                                |  14 +-
 tools/testing/selftests/net/.gitignore        |   1 +
 tools/testing/selftests/net/Makefile          |   2 +
 tools/testing/selftests/net/bind_bhash_test.c | 119 +++++++++
 10 files changed, 560 insertions(+), 78 deletions(-)
 create mode 100644 tools/testing/selftests/net/bind_bhash_test.c
Signature · 1 line
2.30.2
#1 lore raw

PATCH v2 1/2 net: Add a second bind table hashed by port and address

We currently have one tcp bind table (bhash) which hashes by port number only. In the socket bind path, we check for bind conflicts by traversing the specified port's inet_bind2_bucket while holding the bucket's spinlock (see inet_csk_get_port() and inet_csk_bind_conflict()).

In instances where there are tons of sockets hashed to the same port at different addresses, checking for a bind conflict is time-intensive and can cause softirq cpu lockups, as well as stops new tcp connections since __inet_inherit_port() also contests for the spinlock.

This patch proposes adding a second bind table, bhash2, that hashes by port and ip address. Searching the bhash2 table leads to significantly faster conflict resolution and less time holding the spinlock.

---
 include/net/inet_connection_sock.h |   3 +
 include/net/inet_hashtables.h      |  56 ++++++-
 include/net/sock.h                 |  14 ++
 net/dccp/proto.c                   |  14 +-
 net/ipv4/inet_connection_sock.c    | 227 +++++++++++++++++++++--------
 net/ipv4/inet_hashtables.c         | 188 ++++++++++++++++++++++--
 net/ipv4/tcp.c                     |  14 +-
 7 files changed, 438 insertions(+), 78 deletions(-)
include/net/inet_connection_sock.h +3 -0
index 3908296d103f..d89a78d10294 100644
@@ -25,6 +25,7 @@
 #undef INET_CSK_CLEAR_TIMERS
 
 struct inet_bind_bucket;
+struct inet_bind2_bucket;
 struct tcp_congestion_ops;
 
 /*
@@ -57,6 +58,7 @@ struct inet_connection_sock_af_ops {
  *
  * @icsk_accept_queue:	   FIFO of established children
  * @icsk_bind_hash:	   Bind node
+ * @icsk_bind2_hash:	   Bind node in the bhash2 table
  * @icsk_timeout:	   Timeout
  * @icsk_retransmit_timer: Resend (no ack)
  * @icsk_rto:		   Retransmit timeout
@@ -84,6 +86,7 @@ struct inet_connection_sock {
 	struct inet_sock	  icsk_inet;
 	struct request_sock_queue icsk_accept_queue;
 	struct inet_bind_bucket	  *icsk_bind_hash;
+	struct inet_bind2_bucket  *icsk_bind2_hash;
 	unsigned long		  icsk_timeout;
  	struct timer_list	  icsk_retransmit_timer;
  	struct timer_list	  icsk_delack_timer;
include/net/inet_hashtables.h +55 -1

91 lines not on this page · raw message

include/net/sock.h +14 -0
index 663041b92c21..1070c6cb36fb 100644
@@ -351,6 +351,7 @@ struct sk_filter;
   *	@sk_txtime_report_errors: set report errors mode for SO_TXTIME
   *	@sk_txtime_unused: unused txtime flags
   *	@ns_tracker: tracker for netns reference
+  *	@sk_bind2_node: bind node in the bhash2 table
   */
 struct sock {
 	/*
@@ -540,6 +541,7 @@ struct sock {
 #endif
 	struct rcu_head		sk_rcu;
 	netns_tracker		ns_tracker;
+	struct hlist_node	sk_bind2_node;
 };
 
 enum sk_pacing {
@@ -820,6 +822,16 @@ static inline void sk_add_bind_node(struct sock *sk,
 	hlist_add_head(&sk->sk_bind_node, list);
 }
 
+static inline void __sk_del_bind2_node(struct sock *sk)
+{
+	__hlist_del(&sk->sk_bind2_node);
+}
+
+static inline void sk_add_bind2_node(struct sock *sk, struct hlist_head *list)
+{
+	hlist_add_head(&sk->sk_bind2_node, list);
+}
+
 #define sk_for_each(__sk, list) \
 	hlist_for_each_entry(__sk, list, sk_node)
 #define sk_for_each_rcu(__sk, list) \
@@ -837,6 +849,8 @@ static inline void sk_add_bind_node(struct sock *sk,
 	hlist_for_each_entry_safe(__sk, tmp, list, sk_node)
 #define sk_for_each_bound(__sk, list) \
 	hlist_for_each_entry(__sk, list, sk_bind_node)
+#define sk_for_each_bound_bhash2(__sk, list) \
+	hlist_for_each_entry(__sk, list, sk_bind2_node)
 
 /**
  * sk_for_each_entry_offset_rcu - iterate over a list at a given struct offset
net/dccp/proto.c +13 -1
index 58421f94427e..01498a821f3c 100644
@@ -1121,6 +1121,12 @@ static int __init dccp_init(void)
 				  SLAB_HWCACHE_ALIGN | SLAB_ACCOUNT, NULL);
 	if (!dccp_hashinfo.bind_bucket_cachep)
 		goto out_free_hashinfo2;
+	dccp_hashinfo.bind2_bucket_cachep =
+		kmem_cache_create("dccp_bind2_bucket",
+				  sizeof(struct inet_bind2_bucket), 0,
+				  SLAB_HWCACHE_ALIGN | SLAB_ACCOUNT, NULL);
+	if (!dccp_hashinfo.bind2_bucket_cachep)
+		goto out_free_bind_bucket_cachep;
 
 	/*
 	 * Size and allocate the main established and bind bucket
@@ -1151,7 +1157,7 @@ static int __init dccp_init(void)
 
 	if (!dccp_hashinfo.ehash) {
 		DCCP_CRIT("Failed to allocate DCCP established hash table");
-		goto out_free_bind_bucket_cachep;
+		goto out_free_bind2_bucket_cachep;
 	}
 
 	for (i = 0; i <= dccp_hashinfo.ehash_mask; i++)
@@ -1170,6 +1176,8 @@ static int __init dccp_init(void)
 			continue;
 		dccp_hashinfo.bhash = (struct inet_bind_hashbucket *)
 			__get_free_pages(GFP_ATOMIC|__GFP_NOWARN, bhash_order);
+		dccp_hashinfo.bhash2 = (struct inet_bind2_hashbucket *)
+			__get_free_pages(GFP_ATOMIC | __GFP_NOWARN, bhash_order);
 	} while (!dccp_hashinfo.bhash && --bhash_order >= 0);
 
 	if (!dccp_hashinfo.bhash) {
@@ -1180,6 +1188,7 @@ static int __init dccp_init(void)
 	for (i = 0; i < dccp_hashinfo.bhash_size; i++) {
 		spin_lock_init(&dccp_hashinfo.bhash[i].lock);
 		INIT_HLIST_HEAD(&dccp_hashinfo.bhash[i].chain);
+		INIT_HLIST_HEAD(&dccp_hashinfo.bhash2[i].chain);
 	}
 
 	rc = dccp_mib_init();
@@ -1214,6 +1223,8 @@ static int __init dccp_init(void)
 	inet_ehash_locks_free(&dccp_hashinfo);
 out_free_dccp_ehash:
 	free_pages((unsigned long)dccp_hashinfo.ehash, ehash_order);
+out_free_bind2_bucket_cachep:
+	kmem_cache_destroy(dccp_hashinfo.bind2_bucket_cachep);
 out_free_bind_bucket_cachep:
 	kmem_cache_destroy(dccp_hashinfo.bind_bucket_cachep);
 out_free_hashinfo2:
@@ -1222,6 +1233,7 @@ static int __init dccp_init(void)
 	dccp_hashinfo.bhash = NULL;
 	dccp_hashinfo.ehash = NULL;
 	dccp_hashinfo.bind_bucket_cachep = NULL;
+	dccp_hashinfo.bind2_bucket_cachep = NULL;
 	return rc;
 }
 
net/ipv4/inet_connection_sock.c +164 -63

314 lines not on this page · raw message

net/ipv4/inet_hashtables.c +177 -11

295 lines not on this page · raw message

net/ipv4/tcp.c +12 -2
index db55af9eb37b..f884f33b9f55 100644
@@ -4601,6 +4601,12 @@ void __init tcp_init(void)
 				  SLAB_HWCACHE_ALIGN | SLAB_PANIC |
 				  SLAB_ACCOUNT,
 				  NULL);
+	tcp_hashinfo.bind2_bucket_cachep =
+		kmem_cache_create("tcp_bind2_bucket",
+				  sizeof(struct inet_bind2_bucket), 0,
+				  SLAB_HWCACHE_ALIGN | SLAB_PANIC |
+				  SLAB_ACCOUNT,
+				  NULL);
 
 	/* Size and allocate the main established and bind bucket
 	 * hash tables.
@@ -4623,8 +4629,9 @@ void __init tcp_init(void)
 	if (inet_ehash_locks_alloc(&tcp_hashinfo))
 		panic("TCP: failed to alloc ehash_locks");
 	tcp_hashinfo.bhash =
-		alloc_large_system_hash("TCP bind",
-					sizeof(struct inet_bind_hashbucket),
+		alloc_large_system_hash("TCP bind bhash tables",
+					sizeof(struct inet_bind_hashbucket) +
+					sizeof(struct inet_bind2_hashbucket),
 					tcp_hashinfo.ehash_mask + 1,
 					17, /* one slot per 128 KB of memory */
 					0,
@@ -4633,9 +4640,12 @@ void __init tcp_init(void)
 					0,
 					64 * 1024);
 	tcp_hashinfo.bhash_size = 1U << tcp_hashinfo.bhash_size;
+	tcp_hashinfo.bhash2 =
+		(struct inet_bind2_hashbucket *)(tcp_hashinfo.bhash + tcp_hashinfo.bhash_size);
 	for (i = 0; i < tcp_hashinfo.bhash_size; i++) {
 		spin_lock_init(&tcp_hashinfo.bhash[i].lock);
 		INIT_HLIST_HEAD(&tcp_hashinfo.bhash[i].chain);
+		INIT_HLIST_HEAD(&tcp_hashinfo.bhash2[i].chain);
 	}
 
 
Signature · 1 line
2.30.2
#2 lore raw

Re: [PATCH net-next v2 1/2] net: Add a second bind table hashed by port and address

Quoted 227 lines · Joanne Koong

We currently have one tcp bind table (bhash) which hashes by port number only. In the socket bind path, we check for bind conflicts by traversing the specified port's inet_bind2_bucket while holding the bucket's spinlock (see inet_csk_get_port() and inet_csk_bind_conflict()).

In instances where there are tons of sockets hashed to the same port at different addresses, checking for a bind conflict is time-intensive and can cause softirq cpu lockups, as well as stops new tcp connections since __inet_inherit_port() also contests for the spinlock.

This patch proposes adding a second bind table, bhash2, that hashes by port and ip address. Searching the bhash2 table leads to significantly faster conflict resolution and less time holding the spinlock.

---
 include/net/inet_connection_sock.h |   3 +
 include/net/inet_hashtables.h      |  56 ++++++-
 include/net/sock.h                 |  14 ++
 net/dccp/proto.c                   |  14 +-
 net/ipv4/inet_connection_sock.c    | 227 +++++++++++++++++++++--------
 net/ipv4/inet_hashtables.c         | 188 ++++++++++++++++++++++--
 net/ipv4/tcp.c                     |  14 +-
 7 files changed, 438 insertions(+), 78 deletions(-)
include/net/inet_connection_sock.h +3 -0
index 3908296d103f..d89a78d10294 100644
@@ -25,6 +25,7 @@
 #undef INET_CSK_CLEAR_TIMERS
 
 struct inet_bind_bucket;
+struct inet_bind2_bucket;
 struct tcp_congestion_ops;
 
 /*
@@ -57,6 +58,7 @@ struct inet_connection_sock_af_ops {
  *
  * @icsk_accept_queue:    FIFO of established children
  * @icsk_bind_hash:       Bind node
+ * @icsk_bind2_hash:      Bind node in the bhash2 table
  * @icsk_timeout:         Timeout
  * @icsk_retransmit_timer: Resend (no ack)
  * @icsk_rto:             Retransmit timeout
@@ -84,6 +86,7 @@ struct inet_connection_sock {
        struct inet_sock          icsk_inet;
        struct request_sock_queue icsk_accept_queue;
        struct inet_bind_bucket   *icsk_bind_hash;
+       struct inet_bind2_bucket  *icsk_bind2_hash;
        unsigned long             icsk_timeout;
        struct timer_list         icsk_retransmit_timer;
        struct timer_list         icsk_delack_timer;
include/net/inet_hashtables.h +55 -1
index f72ec113ae56..143a33d815c2 100644
@@ -90,11 +90,30 @@ struct inet_bind_bucket {
        struct hlist_head       owners;
 };
 
+struct inet_bind2_bucket {
+       possible_net_t          ib_net;
+       int                     l3mdev;
+       unsigned short          port;
+       union {
+#if IS_ENABLED(CONFIG_IPV6)
+               struct in6_addr         v6_rcv_saddr;
+#endif
+               __be32                  rcv_saddr;
+       };
+       struct hlist_node       node;           /* Node in the inet2_bind_hashbucket chain */
+       struct hlist_head       owners;         /* List of sockets hashed to this bucket */
+};
+
 static inline struct net *ib_net(struct inet_bind_bucket *ib)
 {
        return read_pnet(&ib->ib_net);
 }
 
+static inline struct net *ib2_net(struct inet_bind2_bucket *ib)
+{
+       return read_pnet(&ib->ib_net);
+}
+
 #define inet_bind_bucket_for_each(tb, head) \
        hlist_for_each_entry(tb, head, node)
 
@@ -103,6 +122,15 @@ struct inet_bind_hashbucket {
        struct hlist_head       chain;
 };
 
+/* This is synchronized using the inet_bind_hashbucket's spinlock.
+ * Instead of having separate spinlocks, the inet_bind2_hashbucket can share
+ * the inet_bind_hashbucket's given that in every case where the bhash2 table
+ * is useful, a lookup in the bhash table also occurs.
+ */
+struct inet_bind2_hashbucket {
+       struct hlist_head       chain;
+};
+
 /* Sockets can be hashed in established or listening table.
  * We must use different 'nulls' end-of-chain value for all hash buckets :
  * A socket might transition from ESTABLISH to LISTEN state without
@@ -138,6 +166,11 @@ struct inet_hashinfo {
         */
        struct kmem_cache               *bind_bucket_cachep;
        struct inet_bind_hashbucket     *bhash;
+       /* The 2nd binding table hashed by port and address.
+        * This is used primarily for expediting the resolution of bind conflicts.
+        */
+       struct kmem_cache               *bind2_bucket_cachep;
+       struct inet_bind2_hashbucket    *bhash2;
        unsigned int                    bhash_size;
 
        /* The 2nd listener table hashed by local port and address */
@@ -221,6 +254,27 @@ inet_bind_bucket_create(struct kmem_cache *cachep, struct net *net,
 void inet_bind_bucket_destroy(struct kmem_cache *cachep,
                              struct inet_bind_bucket *tb);
 
+static inline bool check_bind_bucket_match(struct inet_bind_bucket *tb, struct net *net,
+                                          const unsigned short port, int l3mdev)
+{
+       return net_eq(ib_net(tb), net) && tb->port == port && tb->l3mdev == l3mdev;
+}
+
+struct inet_bind2_bucket *
+inet_bind2_bucket_create(struct kmem_cache *cachep, struct net *net,
+                        struct inet_bind2_hashbucket *head, const unsigned short port,
+                        int l3mdev, const struct sock *sk);
+
+void inet_bind2_bucket_destroy(struct kmem_cache *cachep, struct inet_bind2_bucket *tb);
+
+struct inet_bind2_bucket *
+inet_bind2_bucket_find(struct inet_hashinfo *hinfo, struct net *net, const unsigned short port,
+                      int l3mdev, struct sock *sk, struct inet_bind2_hashbucket **head);
+
+bool check_bind2_bucket_match_nulladdr(struct inet_bind2_bucket *tb, struct net *net,
+                                      const unsigned short port, int l3mdev,
+                                      const struct sock *sk);
+
 static inline u32 inet_bhashfn(const struct net *net, const __u16 lport,
                               const u32 bhash_size)
 {
@@ -228,7 +282,7 @@ static inline u32 inet_bhashfn(const struct net *net, const __u16 lport,
 }
 
 void inet_bind_hash(struct sock *sk, struct inet_bind_bucket *tb,
-                   const unsigned short snum);
+                   struct inet_bind2_bucket *tb2, const unsigned short snum);
 
 /* These can have wildcards, don't try too hard. */
 static inline u32 inet_lhashfn(const struct net *net, const unsigned short num)
include/net/sock.h +14 -0
index 663041b92c21..1070c6cb36fb 100644
@@ -351,6 +351,7 @@ struct sk_filter;
   *    @sk_txtime_report_errors: set report errors mode for SO_TXTIME
   *    @sk_txtime_unused: unused txtime flags
   *    @ns_tracker: tracker for netns reference
+  *    @sk_bind2_node: bind node in the bhash2 table
   */
 struct sock {
        /*
@@ -540,6 +541,7 @@ struct sock {
 #endif
        struct rcu_head         sk_rcu;
        netns_tracker           ns_tracker;
+       struct hlist_node       sk_bind2_node;
 };
 
 enum sk_pacing {
@@ -820,6 +822,16 @@ static inline void sk_add_bind_node(struct sock *sk,
        hlist_add_head(&sk->sk_bind_node, list);
 }
 
+static inline void __sk_del_bind2_node(struct sock *sk)
+{
+       __hlist_del(&sk->sk_bind2_node);
+}
+
+static inline void sk_add_bind2_node(struct sock *sk, struct hlist_head *list)
+{
+       hlist_add_head(&sk->sk_bind2_node, list);
+}
+
 #define sk_for_each(__sk, list) \
        hlist_for_each_entry(__sk, list, sk_node)
 #define sk_for_each_rcu(__sk, list) \
@@ -837,6 +849,8 @@ static inline void sk_add_bind_node(struct sock *sk,
        hlist_for_each_entry_safe(__sk, tmp, list, sk_node)
 #define sk_for_each_bound(__sk, list) \
        hlist_for_each_entry(__sk, list, sk_bind_node)
+#define sk_for_each_bound_bhash2(__sk, list) \
+       hlist_for_each_entry(__sk, list, sk_bind2_node)
 
 /**
  * sk_for_each_entry_offset_rcu - iterate over a list at a given struct offset
net/dccp/proto.c +7 -1
index 58421f94427e..01498a821f3c 100644
@@ -1121,6 +1121,12 @@ static int __init dccp_init(void)
                                  SLAB_HWCACHE_ALIGN | SLAB_ACCOUNT, NULL);
        if (!dccp_hashinfo.bind_bucket_cachep)
                goto out_free_hashinfo2;
+       dccp_hashinfo.bind2_bucket_cachep =
+               kmem_cache_create("dccp_bind2_bucket",
+                                 sizeof(struct inet_bind2_bucket), 0,
+                                 SLAB_HWCACHE_ALIGN | SLAB_ACCOUNT, NULL);
+       if (!dccp_hashinfo.bind2_bucket_cachep)
+               goto out_free_bind_bucket_cachep;
 
        /*
         * Size and allocate the main established and bind bucket
@@ -1151,7 +1157,7 @@ static int __init dccp_init(void)
 
        if (!dccp_hashinfo.ehash) {
                DCCP_CRIT("Failed to allocate DCCP established hash table");
-               goto out_free_bind_bucket_cachep;
+               goto out_free_bind2_bucket_cachep;
        }
 
        for (i = 0; i <= dccp_hashinfo.ehash_mask; i++)

net/dccp/proto.c static int __init dccp_init(void) · line 1180

Quoted 5 lines
net/dccp/proto.c +2 -0
@@ -1170,6 +1176,8 @@ static int __init dccp_init(void)
                        continue;
                dccp_hashinfo.bhash = (struct inet_bind_hashbucket *)
                        __get_free_pages(GFP_ATOMIC|__GFP_NOWARN, bhash_order);
+               dccp_hashinfo.bhash2 = (struct inet_bind2_hashbucket *)
+                       __get_free_pages(GFP_ATOMIC | __GFP_NOWARN, bhash_order);

You have to take care of allocation errors, and make sure to not leak memory.

Alternative would be to allow bhash2 to be NULL, and you do not have to change dccp.
(only TCP would request bhash2 to be not NULL)

net/dccp/proto.c static int __init dccp_init(void) · line 1182

Quoted 2 lines
net/dccp/proto.c +0 -0
        } while (!dccp_hashinfo.bhash && --bhash_order >= 0);
 

Can you rebase your patch and resend (after this dccp) issue is resolved, because it does not apply cleanly on net-next.

Thanks.

#3 lore raw

Re: [PATCH net-next v2 1/2] net: Add a second bind table hashed by port and address

Quoted 241 lines · Eric Dumazet
Quoted 227 lines · Joanne Koong

We currently have one tcp bind table (bhash) which hashes by port number only. In the socket bind path, we check for bind conflicts by traversing the specified port's inet_bind2_bucket while holding the bucket's spinlock (see inet_csk_get_port() and inet_csk_bind_conflict()).

In instances where there are tons of sockets hashed to the same port at different addresses, checking for a bind conflict is time-intensive and can cause softirq cpu lockups, as well as stops new tcp connections since __inet_inherit_port() also contests for the spinlock.

This patch proposes adding a second bind table, bhash2, that hashes by port and ip address. Searching the bhash2 table leads to significantly faster conflict resolution and less time holding the spinlock.

---
 include/net/inet_connection_sock.h |   3 +
 include/net/inet_hashtables.h      |  56 ++++++-
 include/net/sock.h                 |  14 ++
 net/dccp/proto.c                   |  14 +-
 net/ipv4/inet_connection_sock.c    | 227 +++++++++++++++++++++--------
 net/ipv4/inet_hashtables.c         | 188 ++++++++++++++++++++++--
 net/ipv4/tcp.c                     |  14 +-
 7 files changed, 438 insertions(+), 78 deletions(-)
include/net/inet_connection_sock.h +3 -0
index 3908296d103f..d89a78d10294 100644
@@ -25,6 +25,7 @@
 #undef INET_CSK_CLEAR_TIMERS
 
 struct inet_bind_bucket;
+struct inet_bind2_bucket;
 struct tcp_congestion_ops;
 
 /*
@@ -57,6 +58,7 @@ struct inet_connection_sock_af_ops {
  *
  * @icsk_accept_queue:    FIFO of established children
  * @icsk_bind_hash:       Bind node
+ * @icsk_bind2_hash:      Bind node in the bhash2 table
  * @icsk_timeout:         Timeout
  * @icsk_retransmit_timer: Resend (no ack)
  * @icsk_rto:             Retransmit timeout
@@ -84,6 +86,7 @@ struct inet_connection_sock {
        struct inet_sock          icsk_inet;
        struct request_sock_queue icsk_accept_queue;
        struct inet_bind_bucket   *icsk_bind_hash;
+       struct inet_bind2_bucket  *icsk_bind2_hash;
        unsigned long             icsk_timeout;
        struct timer_list         icsk_retransmit_timer;
        struct timer_list         icsk_delack_timer;
include/net/inet_hashtables.h +55 -1
index f72ec113ae56..143a33d815c2 100644
@@ -90,11 +90,30 @@ struct inet_bind_bucket {
        struct hlist_head       owners;
 };
 
+struct inet_bind2_bucket {
+       possible_net_t          ib_net;
+       int                     l3mdev;
+       unsigned short          port;
+       union {
+#if IS_ENABLED(CONFIG_IPV6)
+               struct in6_addr         v6_rcv_saddr;
+#endif
+               __be32                  rcv_saddr;
+       };
+       struct hlist_node       node;           /* Node in the inet2_bind_hashbucket chain */
+       struct hlist_head       owners;         /* List of sockets hashed to this bucket */
+};
+
 static inline struct net *ib_net(struct inet_bind_bucket *ib)
 {
        return read_pnet(&ib->ib_net);
 }
 
+static inline struct net *ib2_net(struct inet_bind2_bucket *ib)
+{
+       return read_pnet(&ib->ib_net);
+}
+
 #define inet_bind_bucket_for_each(tb, head) \
        hlist_for_each_entry(tb, head, node)
 
@@ -103,6 +122,15 @@ struct inet_bind_hashbucket {
        struct hlist_head       chain;
 };
 
+/* This is synchronized using the inet_bind_hashbucket's spinlock.
+ * Instead of having separate spinlocks, the inet_bind2_hashbucket can share
+ * the inet_bind_hashbucket's given that in every case where the bhash2 table
+ * is useful, a lookup in the bhash table also occurs.
+ */
+struct inet_bind2_hashbucket {
+       struct hlist_head       chain;
+};
+
 /* Sockets can be hashed in established or listening table.
  * We must use different 'nulls' end-of-chain value for all hash buckets :
  * A socket might transition from ESTABLISH to LISTEN state without
@@ -138,6 +166,11 @@ struct inet_hashinfo {
         */
        struct kmem_cache               *bind_bucket_cachep;
        struct inet_bind_hashbucket     *bhash;
+       /* The 2nd binding table hashed by port and address.
+        * This is used primarily for expediting the resolution of bind conflicts.
+        */
+       struct kmem_cache               *bind2_bucket_cachep;
+       struct inet_bind2_hashbucket    *bhash2;
        unsigned int                    bhash_size;
 
        /* The 2nd listener table hashed by local port and address */
@@ -221,6 +254,27 @@ inet_bind_bucket_create(struct kmem_cache *cachep, struct net *net,
 void inet_bind_bucket_destroy(struct kmem_cache *cachep,
                              struct inet_bind_bucket *tb);
 
+static inline bool check_bind_bucket_match(struct inet_bind_bucket *tb, struct net *net,
+                                          const unsigned short port, int l3mdev)
+{
+       return net_eq(ib_net(tb), net) && tb->port == port && tb->l3mdev == l3mdev;
+}
+
+struct inet_bind2_bucket *
+inet_bind2_bucket_create(struct kmem_cache *cachep, struct net *net,
+                        struct inet_bind2_hashbucket *head, const unsigned short port,
+                        int l3mdev, const struct sock *sk);
+
+void inet_bind2_bucket_destroy(struct kmem_cache *cachep, struct inet_bind2_bucket *tb);
+
+struct inet_bind2_bucket *
+inet_bind2_bucket_find(struct inet_hashinfo *hinfo, struct net *net, const unsigned short port,
+                      int l3mdev, struct sock *sk, struct inet_bind2_hashbucket **head);
+
+bool check_bind2_bucket_match_nulladdr(struct inet_bind2_bucket *tb, struct net *net,
+                                      const unsigned short port, int l3mdev,
+                                      const struct sock *sk);
+
 static inline u32 inet_bhashfn(const struct net *net, const __u16 lport,
                               const u32 bhash_size)
 {
@@ -228,7 +282,7 @@ static inline u32 inet_bhashfn(const struct net *net, const __u16 lport,
 }
 
 void inet_bind_hash(struct sock *sk, struct inet_bind_bucket *tb,
-                   const unsigned short snum);
+                   struct inet_bind2_bucket *tb2, const unsigned short snum);
 
 /* These can have wildcards, don't try too hard. */
 static inline u32 inet_lhashfn(const struct net *net, const unsigned short num)
include/net/sock.h +14 -0
index 663041b92c21..1070c6cb36fb 100644
@@ -351,6 +351,7 @@ struct sk_filter;
   *    @sk_txtime_report_errors: set report errors mode for SO_TXTIME
   *    @sk_txtime_unused: unused txtime flags
   *    @ns_tracker: tracker for netns reference
+  *    @sk_bind2_node: bind node in the bhash2 table
   */
 struct sock {
        /*
@@ -540,6 +541,7 @@ struct sock {
 #endif
        struct rcu_head         sk_rcu;
        netns_tracker           ns_tracker;
+       struct hlist_node       sk_bind2_node;
 };
 
 enum sk_pacing {
@@ -820,6 +822,16 @@ static inline void sk_add_bind_node(struct sock *sk,
        hlist_add_head(&sk->sk_bind_node, list);
 }
 
+static inline void __sk_del_bind2_node(struct sock *sk)
+{
+       __hlist_del(&sk->sk_bind2_node);
+}
+
+static inline void sk_add_bind2_node(struct sock *sk, struct hlist_head *list)
+{
+       hlist_add_head(&sk->sk_bind2_node, list);
+}
+
 #define sk_for_each(__sk, list) \
        hlist_for_each_entry(__sk, list, sk_node)
 #define sk_for_each_rcu(__sk, list) \
@@ -837,6 +849,8 @@ static inline void sk_add_bind_node(struct sock *sk,
        hlist_for_each_entry_safe(__sk, tmp, list, sk_node)
 #define sk_for_each_bound(__sk, list) \
        hlist_for_each_entry(__sk, list, sk_bind_node)
+#define sk_for_each_bound_bhash2(__sk, list) \
+       hlist_for_each_entry(__sk, list, sk_bind2_node)
 
 /**
  * sk_for_each_entry_offset_rcu - iterate over a list at a given struct offset
net/dccp/proto.c +7 -1
index 58421f94427e..01498a821f3c 100644
@@ -1121,6 +1121,12 @@ static int __init dccp_init(void)
                                  SLAB_HWCACHE_ALIGN | SLAB_ACCOUNT, NULL);
        if (!dccp_hashinfo.bind_bucket_cachep)
                goto out_free_hashinfo2;
+       dccp_hashinfo.bind2_bucket_cachep =
+               kmem_cache_create("dccp_bind2_bucket",
+                                 sizeof(struct inet_bind2_bucket), 0,
+                                 SLAB_HWCACHE_ALIGN | SLAB_ACCOUNT, NULL);
+       if (!dccp_hashinfo.bind2_bucket_cachep)
+               goto out_free_bind_bucket_cachep;
 
        /*
         * Size and allocate the main established and bind bucket
@@ -1151,7 +1157,7 @@ static int __init dccp_init(void)
 
        if (!dccp_hashinfo.ehash) {
                DCCP_CRIT("Failed to allocate DCCP established hash table");
-               goto out_free_bind_bucket_cachep;
+               goto out_free_bind2_bucket_cachep;
        }
 
        for (i = 0; i <= dccp_hashinfo.ehash_mask; i++)

net/dccp/proto.c static int __init dccp_init(void) · line 1180

Quoted 5 lines
net/dccp/proto.c +2 -0
@@ -1170,6 +1176,8 @@ static int __init dccp_init(void)
                        continue;
                dccp_hashinfo.bhash = (struct inet_bind_hashbucket *)
                        __get_free_pages(GFP_ATOMIC|__GFP_NOWARN, bhash_order);
+               dccp_hashinfo.bhash2 = (struct inet_bind2_hashbucket *)
+                       __get_free_pages(GFP_ATOMIC | __GFP_NOWARN, bhash_order);

You have to take care of allocation errors, and make sure to not leak memory.

Alternative would be to allow bhash2 to be NULL, and you do not have to change dccp.
(only TCP would request bhash2 to be not NULL)

Quoted 5 lines

net/dccp/proto.c static int __init dccp_init(void) · line 1182

Quoted 2 lines
net/dccp/proto.c +0 -0
        } while (!dccp_hashinfo.bhash && --bhash_order >= 0);
 

Can you rebase your patch and resend (after this dccp) issue is resolved, because it does not apply cleanly on net-next.

Thanks for taking a look at this, Eric. I will rebase and resend after fixing the dccp allocation error handling.

Quoted 2 lines

Thanks.

#4 lore raw

PATCH v2 2/2 selftests: Add test for timing a bind request to a port with a populated bhash entry

In reply to Joanne Koong

This test populates the bhash table for a given port with MAX_THREADS * MAX_CONNECTIONS sockets, and then times how long a bind request on the port takes.

When populating the bhash table, we create the sockets and then bind the sockets to the same address and port (SO_REUSEADDR and SO_REUSEPORT are set). When timing how long a bind on the port takes, we bind on a different address without SO_REUSEPORT set. We do not set SO_REUSEPORT because we are interested in the case where the bind request does not go through the tb->fastreuseport path, which is fragile (eg tb->fastreuseport path does not work if binding with a different uid).

To run the test locally, I did:
* ulimit -n 65535000
* ip addr add 2001:0db8:0:f101::1 dev eth0
* ./bind_bhash_test 443

---
 tools/testing/selftests/net/.gitignore        |   1 +
 tools/testing/selftests/net/Makefile          |   2 +
 tools/testing/selftests/net/bind_bhash_test.c | 119 ++++++++++++++++++
 3 files changed, 122 insertions(+)
 create mode 100644 tools/testing/selftests/net/bind_bhash_test.c
tools/testing/selftests/net/.gitignore +1 -0
index 21a411b04890..735423136bc4 100644
@@ -36,3 +36,4 @@ gro
 ioam6_parser
 toeplitz
 cmsg_sender
+bind_bhash_test
tools/testing/selftests/net/Makefile +2 -0
index af7f6e6ff182..b2cf3fa152ad 100644
@@ -55,6 +55,7 @@ TEST_GEN_PROGS = reuseport_bpf reuseport_bpf_cpu reuseport_bpf_numa
 TEST_GEN_PROGS += reuseport_dualstack reuseaddr_conflict tls
 TEST_GEN_FILES += toeplitz
 TEST_GEN_FILES += cmsg_sender
+TEST_GEN_FILES += bind_bhash_test
 
 TEST_FILES := settings
 
@@ -63,4 +64,5 @@ include ../lib.mk
 
 $(OUTPUT)/reuseport_bpf_numa: LDLIBS += -lnuma
 $(OUTPUT)/tcp_mmap: LDLIBS += -lpthread
+$(OUTPUT)/bind_bhash_test: LDLIBS += -lpthread
 $(OUTPUT)/tcp_inq: LDLIBS += -lpthread
tools/testing/selftests/net/bind_bhash_test.c new file +119 -0

119 lines not on this page · raw message

Signature · 1 line
2.30.2
#5 lore raw

Re: [PATCH net-next v2 2/2] selftests: Add test for timing a bind request to a port with a populated bhash entry

Quoted 168 lines · Joanne Koong

This test populates the bhash table for a given port with MAX_THREADS * MAX_CONNECTIONS sockets, and then times how long a bind request on the port takes.

When populating the bhash table, we create the sockets and then bind the sockets to the same address and port (SO_REUSEADDR and SO_REUSEPORT are set). When timing how long a bind on the port takes, we bind on a different address without SO_REUSEPORT set. We do not set SO_REUSEPORT because we are interested in the case where the bind request does not go through the tb->fastreuseport path, which is fragile (eg tb->fastreuseport path does not work if binding with a different uid).

To run the test locally, I did:
* ulimit -n 65535000
* ip addr add 2001:0db8:0:f101::1 dev eth0
* ./bind_bhash_test 443

---
 tools/testing/selftests/net/.gitignore        |   1 +
 tools/testing/selftests/net/Makefile          |   2 +
 tools/testing/selftests/net/bind_bhash_test.c | 119 ++++++++++++++++++
 3 files changed, 122 insertions(+)
 create mode 100644 tools/testing/selftests/net/bind_bhash_test.c
tools/testing/selftests/net/.gitignore +1 -0
index 21a411b04890..735423136bc4 100644
@@ -36,3 +36,4 @@ gro
 ioam6_parser
 toeplitz
 cmsg_sender
+bind_bhash_test
tools/testing/selftests/net/Makefile +2 -0
index af7f6e6ff182..b2cf3fa152ad 100644
@@ -55,6 +55,7 @@ TEST_GEN_PROGS = reuseport_bpf reuseport_bpf_cpu reuseport_bpf_numa
 TEST_GEN_PROGS += reuseport_dualstack reuseaddr_conflict tls
 TEST_GEN_FILES += toeplitz
 TEST_GEN_FILES += cmsg_sender
+TEST_GEN_FILES += bind_bhash_test
 
 TEST_FILES := settings
 
@@ -63,4 +64,5 @@ include ../lib.mk
 
 $(OUTPUT)/reuseport_bpf_numa: LDLIBS += -lnuma
 $(OUTPUT)/tcp_mmap: LDLIBS += -lpthread
+$(OUTPUT)/bind_bhash_test: LDLIBS += -lpthread
 $(OUTPUT)/tcp_inq: LDLIBS += -lpthread
tools/testing/selftests/net/bind_bhash_test.c new file +109 -0
new file mode 100644
index 000000000000..252e73754e76
@@ -0,0 +1,119 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * This times how long it takes to bind to a port when the port already
+ * has multiple sockets in its bhash table.
+ *
+ * In the setup(), we populate the port's bhash table with
+ * MAX_THREADS * MAX_CONNECTIONS number of entries.
+ */
+
+#include <unistd.h>
+#include <stdio.h>
+#include <netdb.h>
+#include <pthread.h>
+
+#define MAX_THREADS 600
+#define MAX_CONNECTIONS 40
+
+static const char *bind_addr = "::1";
+static const char *port;
+
+static int fd_array[MAX_THREADS][MAX_CONNECTIONS];
+
+static int bind_socket(int opt, const char *addr)
+{
+       struct addrinfo *res, hint = {};
+       int sock_fd, reuse = 1, err;
+
+       sock_fd = socket(AF_INET6, SOCK_STREAM, 0);
+       if (sock_fd < 0) {
+               perror("socket fd err");
+               return -1;
+       }
+
+       hint.ai_family = AF_INET6;
+       hint.ai_socktype = SOCK_STREAM;
+
+       err = getaddrinfo(addr, port, &hint, &res);
+       if (err) {
+               perror("getaddrinfo failed");
+               return -1;
+       }
+
+       if (opt) {
+               err = setsockopt(sock_fd, SOL_SOCKET, opt, &reuse, sizeof(reuse));
+               if (err) {
+                       perror("setsockopt failed");
+                       return -1;
+               }
+       }
+
+       err = bind(sock_fd, res->ai_addr, res->ai_addrlen);
+       if (err) {
+               perror("failed to bind to port");
+               return -1;
+       }
+
+       return sock_fd;
+}
+
+static void *setup(void *arg)
+{
+       int sock_fd, i;
+       int *array = (int *)arg;
+
+       for (i = 0; i < MAX_CONNECTIONS; i++) {
+               sock_fd = bind_socket(SO_REUSEADDR | SO_REUSEPORT, bind_addr);
+               if (sock_fd < 0)
+                       return NULL;
+               array[i] = sock_fd;
+       }
+
+       return NULL;
+}
+
+int main(int argc, const char *argv[])
+{
+       int listener_fd, sock_fd, i, j;
+       pthread_t tid[MAX_THREADS];
+       clock_t begin, end;
+
+       if (argc != 2) {
+               printf("Usage: listener <port>\n");
+               return -1;
+       }
+
+       port = argv[1];
+
+       listener_fd = bind_socket(SO_REUSEADDR | SO_REUSEPORT, bind_addr);
+       if (listen(listener_fd, 100) < 0) {
+               perror("listen failed");
+               return -1;
+       }
+
+       /* Set up threads to populate the bhash table entry for the port */
+       for (i = 0; i < MAX_THREADS; i++)
+               pthread_create(&tid[i], NULL, setup, fd_array[i]);
+
+       for (i = 0; i < MAX_THREADS; i++)
+               pthread_join(tid[i], NULL);
+
+       begin = clock();
+
+       /* Bind to the same port on a different address */
+       sock_fd  = bind_socket(0, "2001:0db8:0:f101::1");
+
+       end = clock();
+
+       printf("time spent = %f\n", (double)(end - begin) / CLOCKS_PER_SEC);
+

tools/testing/selftests/net/bind_bhash_test.c line 119

Quoted 10 lines
tools/testing/selftests/net/bind_bhash_test.c new file +10 -0
+       /* clean up */
+       close(sock_fd);
+       close(listener_fd);
+       for (i = 0; i < MAX_THREADS; i++) {
+               for (j = 0; i < MAX_THREADS; i++)
+                       close(fd_array[i][j]);
+       }
+
+       return 0;
+}

Eric, this is what I used locally to test the bind request. Depending on what you think about this bhash2 proposal, I am happy to clean up this test in a v3 follow-up.

Quoted 3 lines

--
2.30.2

#6 lore raw

Re: [PATCH net-next v2 2/2] selftests: Add test for timing a bind request to a port with a populated bhash entry

Quoted 5 lines · Joanne Koong

Eric, this is what I used locally to test the bind request. Depending on what you think about this bhash2 proposal, I am happy to clean up this test in a v3 follow-up.

Thanks, I will take a look at the series tomorrow.