HomeFreeBSD

routing: actually sort nexthops in nhgs by their index

Description

routing: actually sort nexthops in nhgs by their index

Nexthops in the nexthop groups needs to be deterministically sorted
by some their property to simplify reporting cost when changing
large nexthop groups.

Fix reporting by actually sorting next hops by their indices (wn_cmp_idx()).
As calc_min_mpath_slots_fast() has an assumption that next hops are sorted
using their relative weight in the nexthop groups, it needs to be
addressed as well. The latter sorting is required to quickly determine the
layout of the next hops in the actual forwarding group. For example,
what's the best way to split the traffic between nhops with weights
19,31 and 47 if the maximum nexthop group width is 64?
It is worth mentioning that such sorting is only required during nexthop
group creation and is not used elsewhere. Lastly, normally all nexthop
are of the same weight. With that in mind, (a) use spare 32 bytes inside
struct weightened_nexthop to avoid another memory allocation and
(b) use insertion sort to sort the nexthop weights.

Reported by: thj
Tested by: Claudio Jeker<claudio.jeker@klarasystems.com>
Differential Revision: https://reviews.freebsd.org/D35599
MFC after: 2 weeks

(cherry picked from commit 76f1ab8eff9ede509906e539c10373db44528690)

Details

Provenance
melifaroAuthored on Jun 27 2022, 5:19 PM
Differential Revision
D35599: routing: actually sort nexthops in nhgs by # ascending.
Parents
rGf7db1d569890: routing: fix debug headers added in 6fa8ed43ee0c.
Branches
Unknown
Tags
Unknown