Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1234092 > unrolled thread

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

Started byDenys Vlasenko <dvlasenk@redhat.com>
First post2015-09-28 14:40 +0200
Last post2015-09-29 08:00 +0200
Articles 8 — 6 participants

Back to article view | Back to linux.kernel

Contents

  [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for four elements Denys Vlasenko <dvlasenk@redhat.com> - 2015-09-28 14:40 +0200
    Re: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for  four elements Marcelo Ricardo Leitner <marcelo.leitner@gmail.com> - 2015-09-28 14:50 +0200
    Re: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for  four elements Neil Horman <nhorman@tuxdriver.com> - 2015-09-28 16:00 +0200
      RE: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for  four elements David Laight <David.Laight@ACULAB.COM> - 2015-09-28 16:20 +0200
        Re: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for  four elements Eric Dumazet <eric.dumazet@gmail.com> - 2015-09-28 16:30 +0200
          RE: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for  four elements David Laight <David.Laight@ACULAB.COM> - 2015-09-28 17:40 +0200
            Re: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for  four elements Denys Vlasenko <dvlasenk@redhat.com> - 2015-09-28 19:30 +0200
    Re: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for  four elements David Miller <davem@davemloft.net> - 2015-09-29 08:00 +0200

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

FromDenys Vlasenko <dvlasenk@redhat.com>
Date2015-09-28 14:40 +0200
Subject[PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for four elements
Message-ID<qdFSO-5O5-19@gated-at.bofh.it>
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-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [next] | [standalone]

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

FromMarcelo Ricardo Leitner <marcelo.leitner@gmail.com>
Date2015-09-28 14:50 +0200
SubjectRe: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for four elements
Message-ID<qdG2v-5Zh-27@gated-at.bofh.it>
In reply to#1234092
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>

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

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

FromNeil Horman <nhorman@tuxdriver.com>
Date2015-09-28 16:00 +0200
SubjectRe: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for four elements
Message-ID<qdH8e-1eq-13@gated-at.bofh.it>
In reply to#1234092
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>

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

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

FromDavid Laight <David.Laight@ACULAB.COM>
Date2015-09-28 16:20 +0200
SubjectRE: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for four elements
Message-ID<qdHrA-1Q9-5@gated-at.bofh.it>
In reply to#1234177
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

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

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

FromEric Dumazet <eric.dumazet@gmail.com>
Date2015-09-28 16:30 +0200
SubjectRe: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for four elements
Message-ID<qdHBg-21o-21@gated-at.bofh.it>
In reply to#1234189
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.


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

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

FromDavid Laight <David.Laight@ACULAB.COM>
Date2015-09-28 17:40 +0200
SubjectRE: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for four elements
Message-ID<qdIH0-3xT-11@gated-at.bofh.it>
In reply to#1234205
RnJvbTogRXJpYyBEdW1hemV0DQo+IFNlbnQ6IDI4IFNlcHRlbWJlciAyMDE1IDE1OjI3DQo+IE9u
IE1vbiwgMjAxNS0wOS0yOCBhdCAxNDoxMiArMDAwMCwgRGF2aWQgTGFpZ2h0IHdyb3RlOg0KPiA+
IEZyb206IE5laWwgSG9ybWFuDQo+ID4gPiBTZW50OiAyOCBTZXB0ZW1iZXIgMjAxNSAxNDo1MQ0K
PiA+ID4gT24gTW9uLCBTZXAgMjgsIDIwMTUgYXQgMDI6MzQ6MDRQTSArMDIwMCwgRGVueXMgVmxh
c2Vua28gd3JvdGU6DQo+ID4gPiA+IFNlZW1pbmdseSBpbm5vY3VvdXMgc2N0cF90cmFuc19zdGF0
ZV90b19wcmlvX21hcFtdIGFycmF5DQo+ID4gPiA+IGlzIHdheSBiaWdnZXIgdGhhbiBpdCBsb29r
cywgc2luY2UNCj4gPiA+ID4gIltTQ1RQX1VOS05PV05dID0gMiIgZXhwYW5kcyBpbnRvICJbMHhm
ZmZmXSA9IDIiICENCj4gPiA+ID4NCj4gPiA+ID4gVGhpcyBwYXRjaCByZXBsYWNlcyBpdCB3aXRo
IHN3aXRjaCgpIHN0YXRlbWVudC4NCj4gPg0KPiA+IFdoYXQgYWJvdXQganVzdCBhZGRpbmcgMSAo
YW5kIG1hc2tpbmcpIGJlZm9yZSBpbmRleGluZyB0aGUgYXJyYXk/DQo+ID4gVGhhdCBtaWdodCBy
ZXF1aXJlIGEgc3RhdGljIGlubGluZSBmdW5jdGlvbiB3aXRoIGEgbG9jYWwgc3RhdGljIGFycmF5
Lg0KPiA+DQo+ID4gT3IgZGVmaW5lIHRoZSBhcnJheSBhcyAoc2F5KSBbMTZdIGFuZCBqdXN0IG1h
c2sgdGhlIHN0YXRlIGJlZm9yZSB1c2luZw0KPiA+IGl0IGFzIGFuIGluZGV4Pw0KPiANCj4gSnVz
dCBsZXQgdGhlIGNvbXBpbGVyIGRvIGl0cyBqb2IsIGluc3RlYWQgb2Ygb2JmdXNjYXRpbmcgc291
cmNlLg0KPiANCj4gQ29tcGlsZXJzIGNhbiB0cmFuc2Zvcm0gYSBzd2l0Y2ggaW50byBhbiAob3B0
aW1hbCkgdGFibGUgaWYgaXQgaXMgcmVhbGx5DQo+IGEgZ2Fpbi4NCg0KVGhlIGNvbXBpbGVyIGNh
biBjaG9vc2UgYmV0d2VlbiBhIGp1bXAgdGFibGUgYW5kIG5lc3RlZCBpZnMgZm9yIGEgc3dpdGNo
DQpzdGF0ZW1lbnQuIEkndmUgbmV2ZXIgc2VlbiBpdCBjb252ZXJ0IG9uZSBpbnRvIGEgZGF0YSBh
cnJheSBpbmRleC4NCg0KCURhdmlkDQoNCg==
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

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

FromDenys Vlasenko <dvlasenk@redhat.com>
Date2015-09-28 19:30 +0200
SubjectRe: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for four elements
Message-ID<qdKps-62N-7@gated-at.bofh.it>
In reply to#1234258
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.

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

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

FromDavid Miller <davem@davemloft.net>
Date2015-09-29 08:00 +0200
SubjectRe: [PATCH v2] net: sctp: Don't use 64 kilobyte lookup table for four elements
Message-ID<qdW7f-5ZL-3@gated-at.bofh.it>
In reply to#1234092
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.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web