[PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for four elements

[PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for four elements

[Denys Vlasenko]

Seemingly innocuous sctp_trans_state_to_prio_map[] array
is way bigger than it looks, since
"[SCTP_UNKNOWN] = 2" expands into "[0xffff] = 2" !

This patch replaces it with switch() statement.

Signed-off-by: Denys Vlasenko <dvlasenk@redhat.com>
CC: Vlad Yasevich <vyasevich@gmail.com>
CC: Neil Horman <nhorman@tuxdriver.com>
CC: Marcelo Ricardo Leitner <marcelo.leitner@gmail.com>
CC: linux-sctp@vger.kernel.org
CC: netdev@vger.kernel.org
CC: linux-kernel@vger.kernel.org
---

Changes since v1: tweaked comments

 net/sctp/associola.c | 20 +++++++++++---------
 1 file changed, 11 insertions(+), 9 deletions(-)

diff --git a/net/sctp/associola.c b/net/sctp/associola.c
index 197c3f5..dae51ac 100644
--- a/net/sctp/associola.c
+++ b/net/sctp/associola.c
@@ -1208,20 +1208,22 @@ void sctp_assoc_update(struct sctp_association *asoc,
  *   within this document.
  *
  * Our basic strategy is to round-robin transports in priorities
- * according to sctp_state_prio_map[] e.g., if no such
+ * according to sctp_trans_score() e.g., if no such
  * transport with state SCTP_ACTIVE exists, round-robin through
  * SCTP_UNKNOWN, etc. You get the picture.
  */
-static const u8 sctp_trans_state_to_prio_map[] = {
-	[SCTP_ACTIVE]	= 3,	/* best case */
-	[SCTP_UNKNOWN]	= 2,
-	[SCTP_PF]	= 1,
-	[SCTP_INACTIVE] = 0,	/* worst case */
-};
-
 static u8 sctp_trans_score(const struct sctp_transport *trans)
 {
-	return sctp_trans_state_to_prio_map[trans->state];
+	switch (trans->state) {
+	case SCTP_ACTIVE:
+		return 3;	/* best case */
+	case SCTP_UNKNOWN:
+		return 2;
+	case SCTP_PF:
+		return 1;
+	default: /* case SCTP_INACTIVE */
+		return 0;	/* worst case */
+	}
 }
 
 static struct sctp_transport *sctp_trans_elect_tie(struct sctp_transport *trans1,
-- 
1.8.1.4

Re: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for four elements

[Marcelo Ricardo Leitner]

On Mon, Sep 28, 2015 at 02:34:04PM +0200, Denys Vlasenko wrote:
> Seemingly innocuous sctp_trans_state_to_prio_map[] array
> is way bigger than it looks, since
> "[SCTP_UNKNOWN] = 2" expands into "[0xffff] = 2" !
> 
> This patch replaces it with switch() statement.
> 
> Signed-off-by: Denys Vlasenko <dvlasenk@redhat.com>
> CC: Vlad Yasevich <vyasevich@gmail.com>
> CC: Neil Horman <nhorman@tuxdriver.com>
> CC: Marcelo Ricardo Leitner <marcelo.leitner@gmail.com>
> CC: linux-sctp@vger.kernel.org
> CC: netdev@vger.kernel.org
> CC: linux-kernel@vger.kernel.org

Acked-by: Marcelo Ricardo Leitner <marcelo.leitner@gmail.com>

Re: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for four elements

[Neil Horman]

On Mon, Sep 28, 2015 at 02:34:04PM +0200, Denys Vlasenko wrote:
> Seemingly innocuous sctp_trans_state_to_prio_map[] array
> is way bigger than it looks, since
> "[SCTP_UNKNOWN] = 2" expands into "[0xffff] = 2" !
> 
> This patch replaces it with switch() statement.
> 
> Signed-off-by: Denys Vlasenko <dvlasenk@redhat.com>
> CC: Vlad Yasevich <vyasevich@gmail.com>
> CC: Neil Horman <nhorman@tuxdriver.com>
> CC: Marcelo Ricardo Leitner <marcelo.leitner@gmail.com>
> CC: linux-sctp@vger.kernel.org
> CC: netdev@vger.kernel.org
> CC: linux-kernel@vger.kernel.org
> ---
> 
> Changes since v1: tweaked comments
> 
>  net/sctp/associola.c | 20 +++++++++++---------
>  1 file changed, 11 insertions(+), 9 deletions(-)
> 
> diff --git a/net/sctp/associola.c b/net/sctp/associola.c
> index 197c3f5..dae51ac 100644
> --- a/net/sctp/associola.c
> +++ b/net/sctp/associola.c
> @@ -1208,20 +1208,22 @@ void sctp_assoc_update(struct sctp_association *asoc,
>   *   within this document.
>   *
>   * Our basic strategy is to round-robin transports in priorities
> - * according to sctp_state_prio_map[] e.g., if no such
> + * according to sctp_trans_score() e.g., if no such
>   * transport with state SCTP_ACTIVE exists, round-robin through
>   * SCTP_UNKNOWN, etc. You get the picture.
>   */
> -static const u8 sctp_trans_state_to_prio_map[] = {
> -	[SCTP_ACTIVE]	= 3,	/* best case */
> -	[SCTP_UNKNOWN]	= 2,
> -	[SCTP_PF]	= 1,
> -	[SCTP_INACTIVE] = 0,	/* worst case */
> -};
> -
>  static u8 sctp_trans_score(const struct sctp_transport *trans)
>  {
> -	return sctp_trans_state_to_prio_map[trans->state];
> +	switch (trans->state) {
> +	case SCTP_ACTIVE:
> +		return 3;	/* best case */
> +	case SCTP_UNKNOWN:
> +		return 2;
> +	case SCTP_PF:
> +		return 1;
> +	default: /* case SCTP_INACTIVE */
> +		return 0;	/* worst case */
> +	}
>  }
>  
>  static struct sctp_transport *sctp_trans_elect_tie(struct sctp_transport *trans1,
> -- 
> 1.8.1.4
> 
> --
> 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
> 

Acked-by: Neil Horman <nhorman@tuxdriver.com>

RE: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for four elements

[David Laight]

From: Neil Horman
> Sent: 28 September 2015 14:51
> On Mon, Sep 28, 2015 at 02:34:04PM +0200, Denys Vlasenko wrote:
> > Seemingly innocuous sctp_trans_state_to_prio_map[] array
> > is way bigger than it looks, since
> > "[SCTP_UNKNOWN] = 2" expands into "[0xffff] = 2" !
> >
> > This patch replaces it with switch() statement.

What about just adding 1 (and masking) before indexing the array?
That might require a static inline function with a local static array.

Or define the array as (say) [16] and just mask the state before using
it as an index?

	David

Re: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for four elements

[Eric Dumazet]

On Mon, 2015-09-28 at 14:12 +0000, David Laight wrote:
> From: Neil Horman
> > Sent: 28 September 2015 14:51
> > On Mon, Sep 28, 2015 at 02:34:04PM +0200, Denys Vlasenko wrote:
> > > Seemingly innocuous sctp_trans_state_to_prio_map[] array
> > > is way bigger than it looks, since
> > > "[SCTP_UNKNOWN] = 2" expands into "[0xffff] = 2" !
> > >
> > > This patch replaces it with switch() statement.
> 
> What about just adding 1 (and masking) before indexing the array?
> That might require a static inline function with a local static array.
> 
> Or define the array as (say) [16] and just mask the state before using
> it as an index?

Just let the compiler do its job, instead of obfuscating source.

Compilers can transform a switch into an (optimal) table if it is really
a gain.

RE: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for four elements

[David Laight]

From: Eric Dumazet
> Sent: 28 September 2015 15:27
> On Mon, 2015-09-28 at 14:12 +0000, David Laight wrote:
> > From: Neil Horman
> > > Sent: 28 September 2015 14:51
> > > On Mon, Sep 28, 2015 at 02:34:04PM +0200, Denys Vlasenko wrote:
> > > > Seemingly innocuous sctp_trans_state_to_prio_map[] array
> > > > is way bigger than it looks, since
> > > > "[SCTP_UNKNOWN] = 2" expands into "[0xffff] = 2" !
> > > >
> > > > This patch replaces it with switch() statement.
> >
> > What about just adding 1 (and masking) before indexing the array?
> > That might require a static inline function with a local static array.
> >
> > Or define the array as (say) [16] and just mask the state before using
> > it as an index?
> 
> Just let the compiler do its job, instead of obfuscating source.
> 
> Compilers can transform a switch into an (optimal) table if it is really
> a gain.

The compiler can choose between a jump table and nested ifs for a switch
statement. I've never seen it convert one into a data array index.

	David

Re: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for four elements

[Denys Vlasenko]

On 09/28/2015 05:32 PM, David Laight wrote:
> From: Eric Dumazet
>> Sent: 28 September 2015 15:27
>> On Mon, 2015-09-28 at 14:12 +0000, David Laight wrote:
>>> From: Neil Horman
>>>> Sent: 28 September 2015 14:51
>>>> On Mon, Sep 28, 2015 at 02:34:04PM +0200, Denys Vlasenko wrote:
>>>>> Seemingly innocuous sctp_trans_state_to_prio_map[] array
>>>>> is way bigger than it looks, since
>>>>> "[SCTP_UNKNOWN] = 2" expands into "[0xffff] = 2" !
>>>>>
>>>>> This patch replaces it with switch() statement.
>>>
>>> What about just adding 1 (and masking) before indexing the array?
>>> That might require a static inline function with a local static array.
>>>
>>> Or define the array as (say) [16] and just mask the state before using
>>> it as an index?
>>
>> Just let the compiler do its job, instead of obfuscating source.
>>
>> Compilers can transform a switch into an (optimal) table if it is really
>> a gain.
> 
> The compiler can choose between a jump table and nested ifs for a switch
> statement. I've never seen it convert one into a data array index.

I don't know why people are fixated on a lookup table here.

For just four possible values, the amount of generated code
is less than one Icache cacheline.

Instruction cachelines are efficiently prefetched and branches
are predicted on all modern CPUs.
Possible data access for lookup table can not be prefetched
as efficiently.

Re: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for four elements

[David Miller]

From: Denys Vlasenko <dvlasenk@redhat.com>
Date: Mon, 28 Sep 2015 14:34:04 +0200

> Seemingly innocuous sctp_trans_state_to_prio_map[] array
> is way bigger than it looks, since
> "[SCTP_UNKNOWN] = 2" expands into "[0xffff] = 2" !
> 
> This patch replaces it with switch() statement.
> 
> Signed-off-by: Denys Vlasenko <dvlasenk@redhat.com>

Applied, thank you.