From: Petr Machata <petrm@nvidia.com> Date: 2021-01-28 12:51:25
At this moment, there is only one type of next-hop group: an mpath group.
Mpath groups implement the hash-threshold algorithm, described in RFC
2992[1].
To select a next hop, hash-threshold algorithm first assigns a range of
hashes to each next hop in the group, and then selects the next hop by
comparing the SKB hash with the individual ranges. When a next hop is
removed from the group, the ranges are recomputed, which leads to
reassignment of parts of hash space from one next hop to another. RFC 2992
illustrates it thus:
+-------+-------+-------+-------+-------+
| 1 | 2 | 3 | 4 | 5 |
+-------+-+-----+---+---+-----+-+-------+
| 1 | 2 | 4 | 5 |
+---------+---------+---------+---------+
Before and after deletion of next hop 3
under the hash-threshold algorithm.
Note how next hop 2 gave up part of the hash space in favor of next hop 1,
and 4 in favor of 5. While there will usually be some overlap between the
previous and the new distribution, some traffic flows change the next hop
that they resolve to.
If a multipath group is used for load-balancing between multiple servers,
this hash space reassignment causes an issue that packets from a single
flow suddenly end up arriving at a server that does not expect them, which
may lead to TCP reset.
If a multipath group is used for load-balancing among available paths to
the same server, the issue is that different latencies and reordering along
the way causes the packets to arrive in wrong order.
Resilient hashing is a technique to address the above problem. Resilient
next-hop group has another layer of indirection between the group itself
and its constituent next hops: a hash table. The selection algorithm uses a
straightforward modulo operation to choose a hash bucket, and then reads
the next hop that this bucket contains, and forwards traffic there.
This indirection brings an important feature. In the hash-threshold
algorithm, the range of hashes associated with a next hop must be
continuous. With a hash table, mapping between the hash table buckets and
the individual next hops is arbitrary. Therefore when a next hop is deleted
the buckets that held it are simply reassigned to other next hops:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1|1|1|1|2|2|2|2|3|3|3|3|4|4|4|4|5|5|5|5|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
v v v v
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1|1|1|1|2|2|2|2|1|2|4|5|4|4|4|4|5|5|5|5|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Before and after deletion of next hop 3
under the resilient hashing algorithm.
When weights of next hops in a group are altered, it may be possible to
choose a subset of buckets that are currently not used for forwarding
traffic, and use those to satisfy the new next-hop distribution demands,
keeping the "busy" buckets intact. This way, established flows are ideally
kept being forwarded to the same endpoints through the same paths as before
the next-hop group change.
This patchset prepares the next-hop code for eventual introduction of
resilient hashing groups.
- Patches #1-#4 carry otherwise disjoint changes that just remove certain
assumptions in the next-hop code.
- Patches #5-#6 extend the in-kernel next-hop notifiers to support more
next-hop group types.
- Patches #7-#12 refactor RTNL message handlers. Resilient next-hop groups
will introduce a new logical object, a hash table bucket. It turns out
that handling bucket-related messages is similar to how next-hop messages
are handled. These patches extract the commonalities into reusable
components.
The plan is to contribute approximately the following patchsets:
1) Nexthop policy refactoring (already pushed)
2) Preparations for resilient next hop groups (this patchset)
3) Implementation of resilient next hop group
4) Netdevsim offload plus a suite of selftests
5) Preparations for mlxsw offload of resilient next-hop groups
6) mlxsw offload including selftests
Interested parties can look at the current state of the code at [2] and
[3].
[1] https://tools.ietf.org/html/rfc2992
[2] https://github.com/idosch/linux/commits/submit/res_integ_v1
[3] https://github.com/idosch/iproute2/commits/submit/res_v1
David Ahern (1):
nexthop: Rename nexthop_free_mpath
Ido Schimmel (1):
nexthop: Use enum to encode notification type
Petr Machata (10):
nexthop: Dispatch nexthop_select_path() by group type
nexthop: Introduce to struct nh_grp_entry a per-type union
nexthop: Assert the invariant that a NH group is of only one type
nexthop: Dispatch notifier init()/fini() by group type
nexthop: Extract dump filtering parameters into a single structure
nexthop: Extract a common helper for parsing dump attributes
nexthop: Strongly-type context of rtm_dump_nexthop()
nexthop: Extract a helper for walking the next-hop tree
nexthop: Add a callback parameter to rtm_dump_walk_nexthops()
nexthop: Extract a helper for validation of get/del RTNL requests
.../ethernet/mellanox/mlxsw/spectrum_router.c | 54 +++-
drivers/net/netdevsim/fib.c | 23 +-
include/net/nexthop.h | 14 +-
net/ipv4/nexthop.c | 270 ++++++++++++------
4 files changed, 245 insertions(+), 116 deletions(-)
--
2.26.2
From: Petr Machata <petrm@nvidia.com> Date: 2021-01-28 12:51:51
The values that a next-hop group needs to keep track of depend on the group
type. Introduce a union to separate fields specific to the mpath groups
from fields specific to other group types.
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
include/net/nexthop.h | 7 ++++++-
net/ipv4/nexthop.c | 4 ++--
2 files changed, 8 insertions(+), 3 deletions(-)
@@ -66,7 +66,12 @@ struct nh_info {structnh_grp_entry{structnexthop*nh;u8weight;-atomic_tupper_bound;++union{+struct{+atomic_tupper_bound;+}mpath;+};structlist_headnh_list;structnexthop*nh_parent;/* nexthop of group with this entry */
From: Petr Machata <petrm@nvidia.com> Date: 2021-01-28 12:52:00
The logic for selecting path depends on the next-hop group type. Adapt the
nexthop_select_path() to dispatch according to the group type.
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
net/ipv4/nexthop.c | 22 ++++++++++++++++------
1 file changed, 16 insertions(+), 6 deletions(-)
From: Petr Machata <petrm@nvidia.com> Date: 2021-01-28 12:52:00
Most of the code that deals with nexthop groups relies on the fact that the
group is of exactly one well-known type. Currently there is only one type,
"mpath", but as more next-hop group types come, it becomes desirable to
have a central place where the setting is validated. Introduce such place
into nexthop_create_group(), such that the check is done before the code
that relies on that invariant is invoked.
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
net/ipv4/nexthop.c | 7 +++++--
1 file changed, 5 insertions(+), 2 deletions(-)
From: Petr Machata <petrm@nvidia.com> Date: 2021-01-28 12:52:15
From: Ido Schimmel <idosch@nvidia.com>
Currently there are only two types of in-kernel nexthop notification.
The two are distinguished by the 'is_grp' boolean field in 'struct
nh_notifier_info'.
As more notification types are introduced for more next-hop group types, a
boolean is not an easily extensible interface. Instead, convert it to an
enum.
Signed-off-by: Ido Schimmel <idosch@nvidia.com>
Reviewed-by: Petr Machata <petrm@nvidia.com>
Signed-off-by: Petr Machata <petrm@nvidia.com>
---
.../ethernet/mellanox/mlxsw/spectrum_router.c | 54 ++++++++++++++-----
drivers/net/netdevsim/fib.c | 23 ++++----
include/net/nexthop.h | 7 ++-
net/ipv4/nexthop.c | 14 ++---
4 files changed, 69 insertions(+), 29 deletions(-)
@@ -92,6 +93,7 @@ static int nh_notifier_grp_info_init(struct nh_notifier_info *info,u16num_nh=nhg->num_nh;inti;+info->type=NH_NOTIFIER_INFO_TYPE_GRP;info->nh_grp=kzalloc(struct_size(info->nh_grp,nh_entries,num_nh),GFP_KERNEL);if(!info->nh_grp)
@@ -121,17 +123,17 @@ static int nh_notifier_info_init(struct nh_notifier_info *info,conststructnexthop*nh){info->id=nh->id;-info->is_grp=nh->is_group;-if(info->is_grp)+if(nh->is_group)returnnh_notifier_grp_info_init(info,nh);elsereturnnh_notifier_single_info_init(info,nh);}-staticvoidnh_notifier_info_fini(structnh_notifier_info*info)+staticvoidnh_notifier_info_fini(structnh_notifier_info*info,+conststructnexthop*nh){-if(info->is_grp)+if(nh->is_group)nh_notifier_grp_info_fini(info);elsenh_notifier_single_info_fini(info);
@@ -161,7 +163,7 @@ static int call_nexthop_notifiers(struct net *net,err=blocking_notifier_call_chain(&net->nexthop.notifier_chain,event_type,&info);-nh_notifier_info_fini(&info);+nh_notifier_info_fini(&info,nh);returnnotifier_to_errno(err);}
@@ -182,7 +184,7 @@ static int call_nexthop_notifier(struct notifier_block *nb, struct net *net,returnerr;err=nb->notifier_call(nb,event_type,&info);-nh_notifier_info_fini(&info);+nh_notifier_info_fini(&info,nh);returnnotifier_to_errno(err);}
From: Petr Machata <petrm@nvidia.com> Date: 2021-01-28 12:52:32
After there are several next-hop group types, initialization and
finalization of notifier type needs to reflect the actual type. Transform
nh_notifier_grp_info_init() and _fini() to make extending them easier.
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
net/ipv4/nexthop.c | 25 +++++++++++++++++++------
1 file changed, 19 insertions(+), 6 deletions(-)
From: Petr Machata <petrm@nvidia.com> Date: 2021-01-28 12:52:48
Requests to dump nexthops have many attributes in common with those that
requests to dump buckets of resilient NH groups will have. However, they
have different policies. To allow reuse of this code, extract a
policy-agnostic wrapper out of nh_valid_dump_req(), and convert this
function into a thin wrapper around it.
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
net/ipv4/nexthop.c | 31 +++++++++++++++++++------------
1 file changed, 19 insertions(+), 12 deletions(-)
From: Petr Machata <petrm@nvidia.com> Date: 2021-01-28 12:52:50
Extract from rtm_dump_nexthop() a helper to walk the next hop tree. A
separate function for this will be reusable from the bucket dumper.
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
net/ipv4/nexthop.c | 52 +++++++++++++++++++++++++++++-----------------
1 file changed, 33 insertions(+), 19 deletions(-)
From: Petr Machata <petrm@nvidia.com> Date: 2021-01-28 12:52:53
Requests to dump nexthops have many attributes in common with those that
requests to dump buckets of resilient NH groups will have. In order to make
reuse of this code simpler, convert the code to use a single structure with
filtering configuration instead of passing around the parameters one by
one.
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
net/ipv4/nexthop.c | 44 ++++++++++++++++++++++++--------------------
1 file changed, 24 insertions(+), 20 deletions(-)
From: Petr Machata <petrm@nvidia.com> Date: 2021-01-28 12:53:12
The dump operations need to keep state from one invocation to another. A
scratch area is dedicated for this purpose in the passed-in argument, cb,
namely via two aliased arrays, struct netlink_callback.args and .ctx.
Dumping of buckets will end up having to iterate over next hops as well,
and it would be nice to be able to reuse the iteration logic with the NH
dumper. The fact that the logic currently relies on fixed index to the
.args array, and the indices would have to be coordinated between the two
dumpers, makes this somewhat awkward.
To make the access patters clearer, introduce a helper struct with a NH
index, and instead of using the .args array directly, use it through this
structure.
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
net/ipv4/nexthop.c | 18 ++++++++++++++++--
1 file changed, 16 insertions(+), 2 deletions(-)
From: Petr Machata <petrm@nvidia.com> Date: 2021-01-28 12:53:23
In order to allow different handling for next-hop tree dumper and for
bucket dumper, parameterize the next-hop tree walker with a callback. Add
rtm_dump_nexthop_cb() with just the bits relevant for next-hop tree
dumping.
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
net/ipv4/nexthop.c | 32 ++++++++++++++++++++++----------
1 file changed, 22 insertions(+), 10 deletions(-)
From: Petr Machata <petrm@nvidia.com> Date: 2021-01-28 12:53:55
Validation of messages for get / del of a next hop is the same as will be
validation of messages for get of a resilient next hop group bucket. The
difference is that policy for resilient next hop group buckets is a
superset of that used for next-hop get.
It is therefore possible to reuse the code that validates the nhmsg fields,
extracts the next-hop ID, and validates that. To that end, extract from
nh_valid_get_del_req() a helper __nh_valid_get_del_req() that does just
that.
Make the nlh argument const so that the function can be called from the
dump context, which only has a const nlh. Propagate the constness to
nh_valid_get_del_req().
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
net/ipv4/nexthop.c | 43 +++++++++++++++++++++++++------------------
1 file changed, 25 insertions(+), 18 deletions(-)
From: David Ahern <hidden> Date: 2021-01-29 03:09:02
On 1/28/21 5:49 AM, Petr Machata wrote:
quoted hunk
The logic for selecting path depends on the next-hop group type. Adapt the
nexthop_select_path() to dispatch according to the group type.
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
net/ipv4/nexthop.c | 22 ++++++++++++++++------
1 file changed, 16 insertions(+), 6 deletions(-)
FYI: you can use nh as an abbreviation for nexthop for all static
functions in nexthop.c. Helps keep name lengths in check.
Reviewed-by: David Ahern <dsahern@kernel.org>
From: David Ahern <hidden> Date: 2021-01-29 03:11:00
On 1/28/21 5:49 AM, Petr Machata wrote:
The values that a next-hop group needs to keep track of depend on the group
type. Introduce a union to separate fields specific to the mpath groups
from fields specific to other group types.
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
include/net/nexthop.h | 7 ++++++-
net/ipv4/nexthop.c | 4 ++--
2 files changed, 8 insertions(+), 3 deletions(-)
From: David Ahern <hidden> Date: 2021-01-29 03:11:25
On 1/28/21 5:49 AM, Petr Machata wrote:
Most of the code that deals with nexthop groups relies on the fact that the
group is of exactly one well-known type. Currently there is only one type,
"mpath", but as more next-hop group types come, it becomes desirable to
have a central place where the setting is validated. Introduce such place
into nexthop_create_group(), such that the check is done before the code
that relies on that invariant is invoked.
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
net/ipv4/nexthop.c | 7 +++++--
1 file changed, 5 insertions(+), 2 deletions(-)
From: David Ahern <hidden> Date: 2021-01-29 03:13:23
On 1/28/21 5:49 AM, Petr Machata wrote:
From: Ido Schimmel <idosch@nvidia.com>
Currently there are only two types of in-kernel nexthop notification.
The two are distinguished by the 'is_grp' boolean field in 'struct
nh_notifier_info'.
As more notification types are introduced for more next-hop group types, a
boolean is not an easily extensible interface. Instead, convert it to an
enum.
Signed-off-by: Ido Schimmel <idosch@nvidia.com>
Reviewed-by: Petr Machata <petrm@nvidia.com>
Signed-off-by: Petr Machata <petrm@nvidia.com>
---
.../ethernet/mellanox/mlxsw/spectrum_router.c | 54 ++++++++++++++-----
drivers/net/netdevsim/fib.c | 23 ++++----
include/net/nexthop.h | 7 ++-
net/ipv4/nexthop.c | 14 ++---
4 files changed, 69 insertions(+), 29 deletions(-)
From: David Ahern <hidden> Date: 2021-01-29 03:14:29
On 1/28/21 5:49 AM, Petr Machata wrote:
After there are several next-hop group types, initialization and
finalization of notifier type needs to reflect the actual type. Transform
nh_notifier_grp_info_init() and _fini() to make extending them easier.
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
net/ipv4/nexthop.c | 25 +++++++++++++++++++------
1 file changed, 19 insertions(+), 6 deletions(-)
From: David Ahern <hidden> Date: 2021-01-29 03:17:13
On 1/28/21 5:49 AM, Petr Machata wrote:
quoted hunk
Requests to dump nexthops have many attributes in common with those that
requests to dump buckets of resilient NH groups will have. In order to make
reuse of this code simpler, convert the code to use a single structure with
filtering configuration instead of passing around the parameters one by
one.
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
net/ipv4/nexthop.c | 44 ++++++++++++++++++++++++--------------------
1 file changed, 24 insertions(+), 20 deletions(-)
From: David Ahern <hidden> Date: 2021-01-29 03:18:21
On 1/28/21 5:49 AM, Petr Machata wrote:
Requests to dump nexthops have many attributes in common with those that
requests to dump buckets of resilient NH groups will have. However, they
have different policies. To allow reuse of this code, extract a
policy-agnostic wrapper out of nh_valid_dump_req(), and convert this
function into a thin wrapper around it.
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
net/ipv4/nexthop.c | 31 +++++++++++++++++++------------
1 file changed, 19 insertions(+), 12 deletions(-)
From: David Ahern <hidden> Date: 2021-01-29 03:19:25
On 1/28/21 5:49 AM, Petr Machata wrote:
The dump operations need to keep state from one invocation to another. A
scratch area is dedicated for this purpose in the passed-in argument, cb,
namely via two aliased arrays, struct netlink_callback.args and .ctx.
Dumping of buckets will end up having to iterate over next hops as well,
and it would be nice to be able to reuse the iteration logic with the NH
dumper. The fact that the logic currently relies on fixed index to the
.args array, and the indices would have to be coordinated between the two
dumpers, makes this somewhat awkward.
To make the access patters clearer, introduce a helper struct with a NH
index, and instead of using the .args array directly, use it through this
structure.
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
net/ipv4/nexthop.c | 18 ++++++++++++++++--
1 file changed, 16 insertions(+), 2 deletions(-)
From: David Ahern <hidden> Date: 2021-01-29 03:20:24
On 1/28/21 5:49 AM, Petr Machata wrote:
Extract from rtm_dump_nexthop() a helper to walk the next hop tree. A
separate function for this will be reusable from the bucket dumper.
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
net/ipv4/nexthop.c | 52 +++++++++++++++++++++++++++++-----------------
1 file changed, 33 insertions(+), 19 deletions(-)
From: David Ahern <hidden> Date: 2021-01-29 03:21:27
On 1/28/21 5:49 AM, Petr Machata wrote:
In order to allow different handling for next-hop tree dumper and for
bucket dumper, parameterize the next-hop tree walker with a callback. Add
rtm_dump_nexthop_cb() with just the bits relevant for next-hop tree
dumping.
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
net/ipv4/nexthop.c | 32 ++++++++++++++++++++++----------
1 file changed, 22 insertions(+), 10 deletions(-)
From: David Ahern <hidden> Date: 2021-01-29 03:22:44
On 1/28/21 5:49 AM, Petr Machata wrote:
Validation of messages for get / del of a next hop is the same as will be
validation of messages for get of a resilient next hop group bucket. The
difference is that policy for resilient next hop group buckets is a
superset of that used for next-hop get.
It is therefore possible to reuse the code that validates the nhmsg fields,
extracts the next-hop ID, and validates that. To that end, extract from
nh_valid_get_del_req() a helper __nh_valid_get_del_req() that does just
that.
Make the nlh argument const so that the function can be called from the
dump context, which only has a const nlh. Propagate the constness to
nh_valid_get_del_req().
Signed-off-by: Petr Machata <petrm@nvidia.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
---
net/ipv4/nexthop.c | 43 +++++++++++++++++++++++++------------------
1 file changed, 25 insertions(+), 18 deletions(-)
From: David Ahern <hidden> Date: 2021-01-29 03:25:20
On 1/28/21 5:49 AM, Petr Machata wrote:
At this moment, there is only one type of next-hop group: an mpath group.
Mpath groups implement the hash-threshold algorithm, described in RFC
2992[1].
To select a next hop, hash-threshold algorithm first assigns a range of
hashes to each next hop in the group, and then selects the next hop by
comparing the SKB hash with the individual ranges. When a next hop is
removed from the group, the ranges are recomputed, which leads to
reassignment of parts of hash space from one next hop to another. RFC 2992
illustrates it thus:
+-------+-------+-------+-------+-------+
| 1 | 2 | 3 | 4 | 5 |
+-------+-+-----+---+---+-----+-+-------+
| 1 | 2 | 4 | 5 |
+---------+---------+---------+---------+
Before and after deletion of next hop 3
under the hash-threshold algorithm.
Note how next hop 2 gave up part of the hash space in favor of next hop 1,
and 4 in favor of 5. While there will usually be some overlap between the
previous and the new distribution, some traffic flows change the next hop
that they resolve to.
If a multipath group is used for load-balancing between multiple servers,
this hash space reassignment causes an issue that packets from a single
flow suddenly end up arriving at a server that does not expect them, which
may lead to TCP reset.
If a multipath group is used for load-balancing among available paths to
the same server, the issue is that different latencies and reordering along
the way causes the packets to arrive in wrong order.
Resilient hashing is a technique to address the above problem. Resilient
next-hop group has another layer of indirection between the group itself
and its constituent next hops: a hash table. The selection algorithm uses a
straightforward modulo operation to choose a hash bucket, and then reads
the next hop that this bucket contains, and forwards traffic there.
This indirection brings an important feature. In the hash-threshold
algorithm, the range of hashes associated with a next hop must be
continuous. With a hash table, mapping between the hash table buckets and
the individual next hops is arbitrary. Therefore when a next hop is deleted
the buckets that held it are simply reassigned to other next hops:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1|1|1|1|2|2|2|2|3|3|3|3|4|4|4|4|5|5|5|5|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
v v v v
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1|1|1|1|2|2|2|2|1|2|4|5|4|4|4|4|5|5|5|5|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Before and after deletion of next hop 3
under the resilient hashing algorithm.
When weights of next hops in a group are altered, it may be possible to
choose a subset of buckets that are currently not used for forwarding
traffic, and use those to satisfy the new next-hop distribution demands,
keeping the "busy" buckets intact. This way, established flows are ideally
kept being forwarded to the same endpoints through the same paths as before
the next-hop group change.
This patchset prepares the next-hop code for eventual introduction of
resilient hashing groups.
- Patches #1-#4 carry otherwise disjoint changes that just remove certain
assumptions in the next-hop code.
- Patches #5-#6 extend the in-kernel next-hop notifiers to support more
next-hop group types.
- Patches #7-#12 refactor RTNL message handlers. Resilient next-hop groups
will introduce a new logical object, a hash table bucket. It turns out
that handling bucket-related messages is similar to how next-hop messages
are handled. These patches extract the commonalities into reusable
components.
The plan is to contribute approximately the following patchsets:
1) Nexthop policy refactoring (already pushed)
2) Preparations for resilient next hop groups (this patchset)
3) Implementation of resilient next hop group
4) Netdevsim offload plus a suite of selftests
5) Preparations for mlxsw offload of resilient next-hop groups
6) mlxsw offload including selftests
Interested parties can look at the current state of the code at [2] and
[3].
[1] https://tools.ietf.org/html/rfc2992
[2] https://github.com/idosch/linux/commits/submit/res_integ_v1
[3] https://github.com/idosch/iproute2/commits/submit/res_v1
Very easy to review patchset. Thank you for that and for this cover
letter with the end goal and progress.
Hello:
This series was applied to netdev/net-next.git (refs/heads/master):
On Thu, 28 Jan 2021 13:49:12 +0100 you wrote:
At this moment, there is only one type of next-hop group: an mpath group.
Mpath groups implement the hash-threshold algorithm, described in RFC
2992[1].
To select a next hop, hash-threshold algorithm first assigns a range of
hashes to each next hop in the group, and then selects the next hop by
comparing the SKB hash with the individual ranges. When a next hop is
removed from the group, the ranges are recomputed, which leads to
reassignment of parts of hash space from one next hop to another. RFC 2992
illustrates it thus:
[...]