[PATCH] sctp: Fix port hash table size computation

[PATCH] sctp: Fix port hash table size computation

[Neil Horman]

Dmitry Vyukov noted recently that the sctp_port_hashtable had an error in
its size computation, observing that the current method never guaranteed
that the hashsize (measured in number of entries) would be a power of two,
which the input hash function for that table requires.  The root cause of
the problem is that two values need to be computed (one, the allocation
order of the storage requries, as passed to __get_free_pages, and two the
number of entries for the hash table).  Both need to be ^2, but for
different reasons, and the existing code is simply computing one order
value, and using it as the basis for both, which is wrong (i.e. it assumes
that ((1<<order)*PAGE_SIZE)/sizeof(bucket) is still ^2 when its not).

To fix this, we change the logic slightly.  We start by computing a goal
allocation order (which is limited by the maximum size hash table we want
to support.  Then we attempt to allocate that size table, decreasing the
order until a successful allocation is made.  Then, with the resultant
successful order we compute the number of buckets that hash table supports,
which we then round down to the nearest power of two, giving us the number
of entries the table actually supports.

I've tested this locally here, using non-debug and spinlock-debug kernels,
and the number of entries in the hashtable consistently work out to be
powers of two in all cases.

Signed-off-by: Neil Horman <nhorman@tuxdriver.com>
Reported-by: Dmitry Vyukov <dvyukov@google.com>
CC: Dmitry Vyukov <dvyukov@google.com>
CC: Vladislav Yasevich <vyasevich@gmail.com>
CC: "David S. Miller" <davem@davemloft.net>
---
 net/sctp/protocol.c | 46 ++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 38 insertions(+), 8 deletions(-)

diff --git a/net/sctp/protocol.c b/net/sctp/protocol.c
index ab0d538..779ebee 100644
--- a/net/sctp/protocol.c
+++ b/net/sctp/protocol.c
@@ -60,6 +60,8 @@
 #include <net/inet_common.h>
 #include <net/inet_ecn.h>
 
+#define MAX_SCTP_PORT_HASH_ENTRIES (64 * 1024)
+
 /* Global data structures. */
 struct sctp_globals sctp_globals __read_mostly;
 
@@ -1355,6 +1357,8 @@ static __init int sctp_init(void)
 	unsigned long limit;
 	int max_share;
 	int order;
+	unsigned long num_entries;
+	unsigned long max_entry_order;
 
 	sock_skb_cb_check_size(sizeof(struct sctp_ulpevent));
 
@@ -1407,14 +1411,24 @@ static __init int sctp_init(void)
 
 	/* Size and allocate the association hash table.
 	 * The methodology is similar to that of the tcp hash tables.
+	 * Though not identical.  Start by getting a goal size
 	 */
 	if (totalram_pages >= (128 * 1024))
 		goal = totalram_pages >> (22 - PAGE_SHIFT);
 	else
 		goal = totalram_pages >> (24 - PAGE_SHIFT);
 
-	for (order = 0; (1UL << order) < goal; order++)
-		;
+	/* Then compute the page order for said goal */
+	order = get_order(goal);
+
+	/* Now compute the required page order for the maximum sized table we
+	 * want to create
+	 */
+	max_entry_order = get_order(MAX_SCTP_PORT_HASH_ENTRIES *
+				    sizeof(struct sctp_bind_hashbucket));
+
+	/* Limit the page order by that maximum hash table size */
+	order = min(order, max_entry_order);
 
 	/* Allocate and initialize the endpoint hash table.  */
 	sctp_ep_hashsize = 64;
@@ -1430,20 +1444,35 @@ static __init int sctp_init(void)
 		INIT_HLIST_HEAD(&sctp_ep_hashtable[i].chain);
 	}
 
-	/* Allocate and initialize the SCTP port hash table.  */
+	/* Allocate and initialize the SCTP port hash table.
+	 * Note that order is initalized to start at the max sized
+	 * table we want to support.  If we can't get that many pages
+	 * reduce the order and try again
+	 */
 	do {
-		sctp_port_hashsize = (1UL << order) * PAGE_SIZE /
-					sizeof(struct sctp_bind_hashbucket);
-		if ((sctp_port_hashsize > (64 * 1024)) && order > 0)
-			continue;
 		sctp_port_hashtable = (struct sctp_bind_hashbucket *)
 			__get_free_pages(GFP_KERNEL | __GFP_NOWARN, order);
 	} while (!sctp_port_hashtable && --order > 0);
+
 	if (!sctp_port_hashtable) {
 		pr_err("Failed bind hash alloc\n");
 		status = -ENOMEM;
 		goto err_bhash_alloc;
 	}
+
+	/* Now compute the number of entries that will fit in the
+	 * port hash space we allocated
+	 */
+	num_entries = (1UL << order) * PAGE_SIZE /
+		      sizeof(struct sctp_bind_hashbucket);
+
+	/* And finish by rounding it down to the nearest power of two
+	 * this wastes some memory of course, but its needed because
+	 * the hash function operates based on the assumption that
+	 * that the number of entries is a power of two
+	 */
+	sctp_port_hashsize = rounddown_pow_of_two(num_entries);
+
 	for (i = 0; i < sctp_port_hashsize; i++) {
 		spin_lock_init(&sctp_port_hashtable[i].lock);
 		INIT_HLIST_HEAD(&sctp_port_hashtable[i].chain);
@@ -1452,7 +1481,8 @@ static __init int sctp_init(void)
 	if (sctp_transport_hashtable_init())
 		goto err_thash_alloc;
 
-	pr_info("Hash tables configured (bind %d)\n", sctp_port_hashsize);
+	pr_info("Hash tables configured (bind %d/%d)\n", sctp_port_hashsize,
+		num_entries);
 
 	sctp_sysctl_register();
 
-- 
2.5.0

Re: [PATCH] sctp: Fix port hash table size computation

[David Miller]

From: Neil Horman <nhorman@tuxdriver.com>
Date: Thu, 18 Feb 2016 10:02:04 -0500

> Dmitry Vyukov noted recently that the sctp_port_hashtable had an error in
> its size computation, observing that the current method never guaranteed
> that the hashsize (measured in number of entries) would be a power of two,
> which the input hash function for that table requires.  The root cause of
> the problem is that two values need to be computed (one, the allocation
> order of the storage requries, as passed to __get_free_pages, and two the
> number of entries for the hash table).  Both need to be ^2, but for
> different reasons, and the existing code is simply computing one order
> value, and using it as the basis for both, which is wrong (i.e. it assumes
> that ((1<<order)*PAGE_SIZE)/sizeof(bucket) is still ^2 when its not).
> 
> To fix this, we change the logic slightly.  We start by computing a goal
> allocation order (which is limited by the maximum size hash table we want
> to support.  Then we attempt to allocate that size table, decreasing the
> order until a successful allocation is made.  Then, with the resultant
> successful order we compute the number of buckets that hash table supports,
> which we then round down to the nearest power of two, giving us the number
> of entries the table actually supports.
> 
> I've tested this locally here, using non-debug and spinlock-debug kernels,
> and the number of entries in the hashtable consistently work out to be
> powers of two in all cases.
> 
> Signed-off-by: Neil Horman <nhorman@tuxdriver.com>
> Reported-by: Dmitry Vyukov <dvyukov@google.com>

This needs some work:

In file included from include/linux/list.h:8:0,
  from include/linux/module.h:9, from net/sctp/protocol.c:44:
  net/sctp/protocol.c: In function ‘sctp_init’:
  include/linux/kernel.h:752:17: warning: comparison of distinct
  pointer types lacks a cast (void) (&_min1 == &_min2); \ ^
  net/sctp/protocol.c:1431:10: note: in expansion of macro ‘min’ order
  = min(order, max_entry_order); ^ In file included from
  include/linux/printk.h:6:0, from include/linux/kernel.h:13, from
  include/linux/list.h:8, from include/linux/module.h:9, from
  net/sctp/protocol.c:44:
include/linux/kern_levels.h:4:18: warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘long unsigned int’ [-Wformat=]
 #define KERN_SOH "\001"  /* ASCII Start Of Header */
                  ^
include/linux/kern_levels.h:13:19: note: in expansion of macro ‘KERN_SOH’
 #define KERN_INFO KERN_SOH "6" /* informational */
                   ^
include/linux/printk.h:259:9: note: in expansion of macro ‘KERN_INFO’
  printk(KERN_INFO pr_fmt(fmt), ##__VA_ARGS__)
         ^
net/sctp/protocol.c:1484:2: note: in expansion of macro ‘pr_info’
  pr_info("Hash tables configured (bind %d/%d)\n", sctp_port_hashsize,
  ^

[PATCHv2] sctp: Fix port hash table size computation

[Neil Horman]

Dmitry Vyukov noted recently that the sctp_port_hashtable had an error in
its size computation, observing that the current method never guaranteed
that the hashsize (measured in number of entries) would be a power of two,
which the input hash function for that table requires.  The root cause of
the problem is that two values need to be computed (one, the allocation
order of the storage requries, as passed to __get_free_pages, and two the
number of entries for the hash table).  Both need to be ^2, but for
different reasons, and the existing code is simply computing one order
value, and using it as the basis for both, which is wrong (i.e. it assumes
that ((1<<order)*PAGE_SIZE)/sizeof(bucket) is still ^2 when its not).

To fix this, we change the logic slightly.  We start by computing a goal
allocation order (which is limited by the maximum size hash table we want
to support.  Then we attempt to allocate that size table, decreasing the
order until a successful allocation is made.  Then, with the resultant
successful order we compute the number of buckets that hash table supports,
which we then round down to the nearest power of two, giving us the number
of entries the table actually supports.

I've tested this locally here, using non-debug and spinlock-debug kernels,
and the number of entries in the hashtable consistently work out to be
powers of two in all cases.

Signed-off-by: Neil Horman <nhorman@tuxdriver.com>
Reported-by: Dmitry Vyukov <dvyukov@google.com>
CC: Dmitry Vyukov <dvyukov@google.com>
CC: Vladislav Yasevich <vyasevich@gmail.com>
CC: "David S. Miller" <davem@davemloft.net>

---
Change notes:

v2) Fix type error for num_entries and max_entry_order.  Should have caught
that, sorry Dave
---
 net/sctp/protocol.c | 46 ++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 38 insertions(+), 8 deletions(-)

diff --git a/net/sctp/protocol.c b/net/sctp/protocol.c
index ab0d538..1099e99 100644
--- a/net/sctp/protocol.c
+++ b/net/sctp/protocol.c
@@ -60,6 +60,8 @@
 #include <net/inet_common.h>
 #include <net/inet_ecn.h>
 
+#define MAX_SCTP_PORT_HASH_ENTRIES (64 * 1024)
+
 /* Global data structures. */
 struct sctp_globals sctp_globals __read_mostly;
 
@@ -1355,6 +1357,8 @@ static __init int sctp_init(void)
 	unsigned long limit;
 	int max_share;
 	int order;
+	int num_entries;
+	int max_entry_order;
 
 	sock_skb_cb_check_size(sizeof(struct sctp_ulpevent));
 
@@ -1407,14 +1411,24 @@ static __init int sctp_init(void)
 
 	/* Size and allocate the association hash table.
 	 * The methodology is similar to that of the tcp hash tables.
+	 * Though not identical.  Start by getting a goal size
 	 */
 	if (totalram_pages >= (128 * 1024))
 		goal = totalram_pages >> (22 - PAGE_SHIFT);
 	else
 		goal = totalram_pages >> (24 - PAGE_SHIFT);
 
-	for (order = 0; (1UL << order) < goal; order++)
-		;
+	/* Then compute the page order for said goal */
+	order = get_order(goal);
+
+	/* Now compute the required page order for the maximum sized table we
+	 * want to create
+	 */
+	max_entry_order = get_order(MAX_SCTP_PORT_HASH_ENTRIES *
+				    sizeof(struct sctp_bind_hashbucket));
+
+	/* Limit the page order by that maximum hash table size */
+	order = min(order, max_entry_order);
 
 	/* Allocate and initialize the endpoint hash table.  */
 	sctp_ep_hashsize = 64;
@@ -1430,20 +1444,35 @@ static __init int sctp_init(void)
 		INIT_HLIST_HEAD(&sctp_ep_hashtable[i].chain);
 	}
 
-	/* Allocate and initialize the SCTP port hash table.  */
+	/* Allocate and initialize the SCTP port hash table.
+	 * Note that order is initalized to start at the max sized
+	 * table we want to support.  If we can't get that many pages
+	 * reduce the order and try again
+	 */
 	do {
-		sctp_port_hashsize = (1UL << order) * PAGE_SIZE /
-					sizeof(struct sctp_bind_hashbucket);
-		if ((sctp_port_hashsize > (64 * 1024)) && order > 0)
-			continue;
 		sctp_port_hashtable = (struct sctp_bind_hashbucket *)
 			__get_free_pages(GFP_KERNEL | __GFP_NOWARN, order);
 	} while (!sctp_port_hashtable && --order > 0);
+
 	if (!sctp_port_hashtable) {
 		pr_err("Failed bind hash alloc\n");
 		status = -ENOMEM;
 		goto err_bhash_alloc;
 	}
+
+	/* Now compute the number of entries that will fit in the
+	 * port hash space we allocated
+	 */
+	num_entries = (1UL << order) * PAGE_SIZE /
+		      sizeof(struct sctp_bind_hashbucket);
+
+	/* And finish by rounding it down to the nearest power of two
+	 * this wastes some memory of course, but its needed because
+	 * the hash function operates based on the assumption that
+	 * that the number of entries is a power of two
+	 */
+	sctp_port_hashsize = rounddown_pow_of_two(num_entries);
+
 	for (i = 0; i < sctp_port_hashsize; i++) {
 		spin_lock_init(&sctp_port_hashtable[i].lock);
 		INIT_HLIST_HEAD(&sctp_port_hashtable[i].chain);
@@ -1452,7 +1481,8 @@ static __init int sctp_init(void)
 	if (sctp_transport_hashtable_init())
 		goto err_thash_alloc;
 
-	pr_info("Hash tables configured (bind %d)\n", sctp_port_hashsize);
+	pr_info("Hash tables configured (bind %d/%d)\n", sctp_port_hashsize,
+		num_entries);
 
 	sctp_sysctl_register();
 
-- 
2.5.0

Re: [PATCHv2] sctp: Fix port hash table size computation

[Eric Dumazet]

On jeu., 2016-02-18 at 16:10 -0500, Neil Horman wrote:
> Dmitry Vyukov noted recently that the sctp_port_hashtable had an error in
> its size computation, observing that the current method never guaranteed
> that the hashsize (measured in number of entries) would be a power of two,
> which the input hash function for that table requires.  The root cause of
> the problem is that two values need to be computed (one, the allocation
> order of the storage requries, as passed to __get_free_pages, and two the
> number of entries for the hash table).  Both need to be ^2, but for
> different reasons, and the existing code is simply computing one order
> value, and using it as the basis for both, which is wrong (i.e. it assumes
> that ((1<<order)*PAGE_SIZE)/sizeof(bucket) is still ^2 when its not).

Looks complicated for a stable submission.

What about reusing existing trick instead ?


diff --git a/net/sctp/protocol.c b/net/sctp/protocol.c
index ab0d538..3e4e11b 100644
--- a/net/sctp/protocol.c
+++ b/net/sctp/protocol.c
@@ -1434,6 +1434,10 @@ static __init int sctp_init(void)
 	do {
 		sctp_port_hashsize = (1UL << order) * PAGE_SIZE /
 					sizeof(struct sctp_bind_hashbucket);
+
+		while (sctp_port_hashsize & (sctp_port_hashsize - 1))
+			sctp_port_hashsize--;
+
 	if ((sctp_port_hashsize > (64 * 1024)) && order > 0)
 		continue;
 	sctp_port_hashtable = (struct sctp_bind_hashbucket *)

Re: [PATCHv2] sctp: Fix port hash table size computation

[Neil Horman]

On Fri, Feb 19, 2016 at 11:28:50AM +0100, Eric Dumazet wrote:
> On jeu., 2016-02-18 at 16:10 -0500, Neil Horman wrote:
> > Dmitry Vyukov noted recently that the sctp_port_hashtable had an error in
> > its size computation, observing that the current method never guaranteed
> > that the hashsize (measured in number of entries) would be a power of two,
> > which the input hash function for that table requires.  The root cause of
> > the problem is that two values need to be computed (one, the allocation
> > order of the storage requries, as passed to __get_free_pages, and two the
> > number of entries for the hash table).  Both need to be ^2, but for
> > different reasons, and the existing code is simply computing one order
> > value, and using it as the basis for both, which is wrong (i.e. it assumes
> > that ((1<<order)*PAGE_SIZE)/sizeof(bucket) is still ^2 when its not).
> 
> Looks complicated for a stable submission.
> 
> What about reusing existing trick instead ?
> 
> 
> diff --git a/net/sctp/protocol.c b/net/sctp/protocol.c
> index ab0d538..3e4e11b 100644
> --- a/net/sctp/protocol.c
> +++ b/net/sctp/protocol.c
> @@ -1434,6 +1434,10 @@ static __init int sctp_init(void)
>  	do {
>  		sctp_port_hashsize = (1UL << order) * PAGE_SIZE /
>  					sizeof(struct sctp_bind_hashbucket);
> +
> +		while (sctp_port_hashsize & (sctp_port_hashsize - 1))
> +			sctp_port_hashsize--;
> +
>  	if ((sctp_port_hashsize > (64 * 1024)) && order > 0)
>  		continue;
>  	sctp_port_hashtable = (struct sctp_bind_hashbucket *)
> 
> 
> 

I had actually thought about that, but to be frank I felt like the logic to
compute the hashsize was complex the way it was presented currently, and that my
rewite made it more clear, breaking it down into a few easy steps:

1) compute a goal size order
2) compute the target order for the largest table we want to support
3) select the minimum of (1) and (2)
4) allocated the largest table we can up to the size in (3)
5) compute how many buckets the table we allocated in (4) supports


I'm happy to use your suggestion above if the consensus is that its more clear,
but it took me a bit to figure out what exactly the existing code was trying to
do (especially given the dual use of the order variable), so I thought some
additional clarity was called for.

Neil

Re: [PATCHv2] sctp: Fix port hash table size computation

[Eric Dumazet]

On ven., 2016-02-19 at 09:07 -0500, Neil Horman wrote:

> I had actually thought about that, but to be frank I felt like the logic to
> compute the hashsize was complex the way it was presented currently, and that my
> rewite made it more clear, breaking it down into a few easy steps:
> 
> 1) compute a goal size order
> 2) compute the target order for the largest table we want to support
> 3) select the minimum of (1) and (2)
> 4) allocated the largest table we can up to the size in (3)
> 5) compute how many buckets the table we allocated in (4) supports
> 
> 
> I'm happy to use your suggestion above if the consensus is that its more clear,
> but it took me a bit to figure out what exactly the existing code was trying to
> do (especially given the dual use of the order variable), so I thought some
> additional clarity was called for.

No strong feelings. I only took a look in other places like
net/dccp/proto.c for similar problem.

Re: [PATCHv2] sctp: Fix port hash table size computation

[Neil Horman]

On Fri, Feb 19, 2016 at 03:41:09PM +0100, Eric Dumazet wrote:
> On ven., 2016-02-19 at 09:07 -0500, Neil Horman wrote:
> 
> > I had actually thought about that, but to be frank I felt like the logic to
> > compute the hashsize was complex the way it was presented currently, and that my
> > rewite made it more clear, breaking it down into a few easy steps:
> > 
> > 1) compute a goal size order
> > 2) compute the target order for the largest table we want to support
> > 3) select the minimum of (1) and (2)
> > 4) allocated the largest table we can up to the size in (3)
> > 5) compute how many buckets the table we allocated in (4) supports
> > 
> > 
> > I'm happy to use your suggestion above if the consensus is that its more clear,
> > but it took me a bit to figure out what exactly the existing code was trying to
> > do (especially given the dual use of the order variable), so I thought some
> > additional clarity was called for.
> 
> No strong feelings. I only took a look in other places like
> net/dccp/proto.c for similar problem.
> 
Understood. Its clear that sctp lifted the code from dccp (or perhaps vice
versa).  Either way, looking at it, it appears dccp has the same problem that
sctp does in this area.

As you don't have strong feelings, if its all the same to Dave and Vlad, I'm
happy with the way this patch is laid out, and will move on to fix dccp in the
same manner.

Best
Neil

> 
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-sctp" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: [PATCHv2] sctp: Fix port hash table size computation

[David Miller]

From: Neil Horman <nhorman@tuxdriver.com>
Date: Thu, 18 Feb 2016 16:10:57 -0500

> Dmitry Vyukov noted recently that the sctp_port_hashtable had an error in
> its size computation, observing that the current method never guaranteed
> that the hashsize (measured in number of entries) would be a power of two,
> which the input hash function for that table requires.  The root cause of
> the problem is that two values need to be computed (one, the allocation
> order of the storage requries, as passed to __get_free_pages, and two the
> number of entries for the hash table).  Both need to be ^2, but for
> different reasons, and the existing code is simply computing one order
> value, and using it as the basis for both, which is wrong (i.e. it assumes
> that ((1<<order)*PAGE_SIZE)/sizeof(bucket) is still ^2 when its not).
> 
> To fix this, we change the logic slightly.  We start by computing a goal
> allocation order (which is limited by the maximum size hash table we want
> to support.  Then we attempt to allocate that size table, decreasing the
> order until a successful allocation is made.  Then, with the resultant
> successful order we compute the number of buckets that hash table supports,
> which we then round down to the nearest power of two, giving us the number
> of entries the table actually supports.
> 
> I've tested this locally here, using non-debug and spinlock-debug kernels,
> and the number of entries in the hashtable consistently work out to be
> powers of two in all cases.
> 
> Signed-off-by: Neil Horman <nhorman@tuxdriver.com>
> Reported-by: Dmitry Vyukov <dvyukov@google.com>

Applied and queued up for -stable, thanks Neil.