[RFC,net-next] ipv6: Attempt to improve options code parsing

As per Eric's comment on a previous patchset that was adding a new HopbyHop
option, i.e. why should a new option appear before or after existing ones in the
list, here is an attempt to suppress such competition. It also improves the
efficiency and fasten the process of matching a Hbh or Dst option, which is
probably something we want regarding the list of new options that could quickly
grow in the future.

Basically, the two "lists" of options (Hbh and Dst) are replaced by two arrays.
Each array has a size of 256 (for each code point). Each code point points to a
function to process its specific option.

Thoughts?

Signed-off-by: Justin Iurman <justin.iurman@uliege.be>
---
 net/ipv6/exthdrs.c | 86 ++++++++++++++++++----------------------------
 1 file changed, 33 insertions(+), 53 deletions(-)

On 8/2/21 10:51 PM, Justin Iurman wrote:
> As per Eric's comment on a previous patchset that was adding a new HopbyHop

> option, i.e. why should a new option appear before or after existing ones in the

> list, here is an attempt to suppress such competition. It also improves the

> efficiency and fasten the process of matching a Hbh or Dst option, which is

> probably something we want regarding the list of new options that could quickly

> grow in the future.

> 

> Basically, the two "lists" of options (Hbh and Dst) are replaced by two arrays.

> Each array has a size of 256 (for each code point). Each code point points to a

> function to process its specific option.

> 

> Thoughts?

> 

Hi Justin

I think this still suffers from indirect call costs (CONFIG_RETPOLINE=y),
and eventually use more dcache.

Since we only deal with two sets/arrays, I would simply get rid of them
and inline the code using two switch() clauses.

I cooked the following patch instead:


 net/ipv6/exthdrs.c |  102 ++++++++++++++++++++++++++++++++++++++++++++++--------------------------------------------------------
 1 file changed, 46 insertions(+), 56 deletions(-)

diff --git a/net/ipv6/exthdrs.c b/net/ipv6/exthdrs.c
index d897faa4e9e63831b9b4f0ad0e59bf7032b2bd96..5acdc62bb5419b81cac46c935d7436f490dc3e74 100644
--- a/net/ipv6/exthdrs.c
+++ b/net/ipv6/exthdrs.c
@@ -55,19 +55,6 @@
 
 #include <linux/uaccess.h>
 
-/*
- *     Parsing tlv encoded headers.
- *
- *     Parsing function "func" returns true, if parsing succeed
- *     and false, if it failed.
- *     It MUST NOT touch skb->h.
- */
-
-struct tlvtype_proc {
-       int     type;
-       bool    (*func)(struct sk_buff *skb, int offset);
-};
-
 /*********************
   Generic functions
  *********************/
@@ -112,9 +99,17 @@ static bool ip6_tlvopt_unknown(struct sk_buff *skb, int optoff,
        return false;
 }
 
+static bool ipv6_hop_ra(struct sk_buff *skb, int optoff);
+static bool ipv6_hop_ioam(struct sk_buff *skb, int optoff);
+static bool ipv6_hop_jumbo(struct sk_buff *skb, int optoff);
+static bool ipv6_hop_calipso(struct sk_buff *skb, int optoff);
+#if IS_ENABLED(CONFIG_IPV6_MIP6)
+static bool ipv6_dest_hao(struct sk_buff *skb, int optoff);
+#endif
+
 /* Parse tlv encoded option header (hop-by-hop or destination) */
 
-static bool ip6_parse_tlv(const struct tlvtype_proc *procs,
+static bool ip6_parse_tlv(bool hopbyhop,
                          struct sk_buff *skb,
                          int max_count)
 {
@@ -176,20 +171,45 @@ static bool ip6_parse_tlv(const struct tlvtype_proc *procs,
                        if (tlv_count > max_count)
                                goto bad;
 
-                       for (curr = procs; curr->type >= 0; curr++) {
-                               if (curr->type == nh[off]) {
-                                       /* type specific length/alignment
-                                          checks will be performed in the
-                                          func(). */
-                                       if (curr->func(skb, off) == false)
+                       if (hopbyhop) {
+                               switch (nh[off]) {
+                               case IPV6_TLV_ROUTERALERT:
+                                       if (!ipv6_hop_ra(skb, off))
+                                               return false;
+                                       break;
+                               case IPV6_TLV_IOAM:
+                                       if (!ipv6_hop_ioam(skb, off))
+                                               return false;
+                                       break;
+                               case IPV6_TLV_JUMBO:
+                                       if (!ipv6_hop_jumbo(skb, off))
+                                               return false;
+                                       break;
+                               case IPV6_TLV_CALIPSO:
+                                       if (!ipv6_hop_calipso(skb, off))
+                                               return false;
+                                       break;
+                               default:
+                                       if (!ip6_tlvopt_unknown(skb, off,
+                                                               disallow_unknowns))
+                                               return false;
+                                       break;
+                               }
+                       } else {
+                               switch (nh[off]) {
+#if IS_ENABLED(CONFIG_IPV6_MIP6)
+                               case IPV6_TLV_HAO:
+                                       if (!ipv6_dest_hao(skb, off))
+                                               return false;
+                                       break;
+#endif
+                               default:
+                                       if (!ip6_tlvopt_unknown(skb, off,
+                                                               disallow_unknowns))
                                                return false;
                                        break;
                                }
                        }
-                       if (curr->type < 0 &&
-                           !ip6_tlvopt_unknown(skb, off, disallow_unknowns))
-                               return false;
-
                        padlen = 0;
                }
                off += optlen;
@@ -267,16 +287,6 @@ static bool ipv6_dest_hao(struct sk_buff *skb, int optoff)
 }
 #endif
 
-static const struct tlvtype_proc tlvprocdestopt_lst[] = {
-#if IS_ENABLED(CONFIG_IPV6_MIP6)
-       {
-               .type   = IPV6_TLV_HAO,
-               .func   = ipv6_dest_hao,
-       },
-#endif
-       {-1,                    NULL}
-};
-
 static int ipv6_destopt_rcv(struct sk_buff *skb)
 {
        struct inet6_dev *idev = __in6_dev_get(skb->dev);
@@ -307,7 +317,7 @@ static int ipv6_destopt_rcv(struct sk_buff *skb)
        dstbuf = opt->dst1;
 #endif
 
-       if (ip6_parse_tlv(tlvprocdestopt_lst, skb,
+       if (ip6_parse_tlv(false, skb,
                          net->ipv6.sysctl.max_dst_opts_cnt)) {
                skb->transport_header += extlen;
                opt = IP6CB(skb);
@@ -1051,26 +1061,6 @@ static bool ipv6_hop_calipso(struct sk_buff *skb, int optoff)
        return false;
 }
 
-static const struct tlvtype_proc tlvprochopopt_lst[] = {
-       {
-               .type   = IPV6_TLV_ROUTERALERT,
-               .func   = ipv6_hop_ra,
-       },
-       {
-               .type   = IPV6_TLV_IOAM,
-               .func   = ipv6_hop_ioam,
-       },
-       {
-               .type   = IPV6_TLV_JUMBO,
-               .func   = ipv6_hop_jumbo,
-       },
-       {
-               .type   = IPV6_TLV_CALIPSO,
-               .func   = ipv6_hop_calipso,
-       },
-       { -1, }
-};
-
 int ipv6_parse_hopopts(struct sk_buff *skb)
 {
        struct inet6_skb_parm *opt = IP6CB(skb);
@@ -1096,7 +1086,7 @@ int ipv6_parse_hopopts(struct sk_buff *skb)
                goto fail_and_free;
 
        opt->flags |= IP6SKB_HOPBYHOP;
-       if (ip6_parse_tlv(tlvprochopopt_lst, skb,
+       if (ip6_parse_tlv(true, skb,
                          net->ipv6.sysctl.max_hbh_opts_cnt)) {
                skb->transport_header += extlen;
                opt = IP6CB(skb);

>> As per Eric's comment on a previous patchset that was adding a new HopbyHop

>> option, i.e. why should a new option appear before or after existing ones in the

>> list, here is an attempt to suppress such competition. It also improves the

>> efficiency and fasten the process of matching a Hbh or Dst option, which is

>> probably something we want regarding the list of new options that could quickly

>> grow in the future.

>> 

>> Basically, the two "lists" of options (Hbh and Dst) are replaced by two arrays.

>> Each array has a size of 256 (for each code point). Each code point points to a

>> function to process its specific option.

>> 

>> Thoughts?

>> 

> Hi Justin

> 

> I think this still suffers from indirect call costs (CONFIG_RETPOLINE=y),

> and eventually use more dcache.


Agree with both. It was the compromise for such a solution, unfortunately.

> Since we only deal with two sets/arrays, I would simply get rid of them

> and inline the code using two switch() clauses.


Indeed, this is the more efficient. However, we still have two "issues":
 - ip6_parse_tlv will keep growing and code could look ugly at some point
 - there is still a "competition" between options, i.e. "I want to be at the top of the list"

Anyway, your solution is better than the current one so it's probably the way to go right now.

On 8/3/21 6:06 PM, Justin Iurman wrote:
>>> As per Eric's comment on a previous patchset that was adding a new HopbyHop

>>> option, i.e. why should a new option appear before or after existing ones in the

>>> list, here is an attempt to suppress such competition. It also improves the

>>> efficiency and fasten the process of matching a Hbh or Dst option, which is

>>> probably something we want regarding the list of new options that could quickly

>>> grow in the future.

>>>

>>> Basically, the two "lists" of options (Hbh and Dst) are replaced by two arrays.

>>> Each array has a size of 256 (for each code point). Each code point points to a

>>> function to process its specific option.

>>>

>>> Thoughts?

>>>

>> Hi Justin

>>

>> I think this still suffers from indirect call costs (CONFIG_RETPOLINE=y),

>> and eventually use more dcache.

> 

> Agree with both. It was the compromise for such a solution, unfortunately.

> 

>> Since we only deal with two sets/arrays, I would simply get rid of them

>> and inline the code using two switch() clauses.

> 

> Indeed, this is the more efficient. However, we still have two "issues":

>  - ip6_parse_tlv will keep growing and code could look ugly at some point


Well, in 10 years there has not been a lot of growth.

>  - there is still a "competition" between options, i.e. "I want to be at the top of the list"


Why would that be ?

A switch() is compiled with no particular order by the compiler.

Code generation depends on case density, and will use bisection-like strategy.

> 

> Anyway, your solution is better than the current one so it's probably the way to go right now.

>

>>>> As per Eric's comment on a previous patchset that was adding a new HopbyHop

>>>> option, i.e. why should a new option appear before or after existing ones in the

>>>> list, here is an attempt to suppress such competition. It also improves the

>>>> efficiency and fasten the process of matching a Hbh or Dst option, which is

>>>> probably something we want regarding the list of new options that could quickly

>>>> grow in the future.

>>>>

>>>> Basically, the two "lists" of options (Hbh and Dst) are replaced by two arrays.

>>>> Each array has a size of 256 (for each code point). Each code point points to a

>>>> function to process its specific option.

>>>>

>>>> Thoughts?

>>>>

>>> Hi Justin

>>>

>>> I think this still suffers from indirect call costs (CONFIG_RETPOLINE=y),

>>> and eventually use more dcache.

>> 

>> Agree with both. It was the compromise for such a solution, unfortunately.

>> 

>>> Since we only deal with two sets/arrays, I would simply get rid of them

>>> and inline the code using two switch() clauses.

>> 

>> Indeed, this is the more efficient. However, we still have two "issues":

>>  - ip6_parse_tlv will keep growing and code could look ugly at some point

> 

> Well, in 10 years there has not been a lot of growth.


Indeed, but I think it could grow a lot more in short/middle term. Just have a look at current discussions in the IETF (e.g., 6man) about HopbyHop limitations and anything related, as a way to widely improve their support and not just drop them. A better support could bring new options.