git: b450c1d7f7f4 - main - routing: Fix the size of nexthop groups with mixed metrics

From: Pouria Mousavizadeh Tehrani <pouria_at_FreeBSD.org>
Date: Fri, 20 Nov 2026 10:23:21 UTC
The branch main has been updated by pouria:

URL: https://cgit.FreeBSD.org/src/commit/?id=b450c1d7f7f41aab9296b857d797122ef4c37f65

commit b450c1d7f7f41aab9296b857d797122ef4c37f65
Author:     Pouria Mousavizadeh Tehrani <pouria@FreeBSD.org>
AuthorDate: 2026-11-20 10:18:19 +0000
Commit:     Pouria Mousavizadeh Tehrani <pouria@FreeBSD.org>
CommitDate: 2026-11-20 10:19:30 +0000

    routing: Fix the size of nexthop groups with mixed metrics
    
    calc_min_mpath_slots_fast() selects the nexthops with the lowest
    metric through wn[i].nh, but reads their weights from wn[i].storage,
    a copy of the weights that is sorted independently of the nexthops.
    In a group with more than one metric the weights of the wrong
    nexthops are summed, and the weights of all nexthops take part in
    the divisibility check, so the group gets a wrong number of slots
    and a wrong traffic split.
    
    Calculate the number of slots as the sum of the weights divided by
    their greatest common divisor instead.  It needs no sorted copy of
    the weights and is exact where the old code gave up and used
    RIB_MAX_MPATH_WIDTH slots.
    
    The storage field is part of the bytes that identify a group.  It is
    no longer written by the calculation, so set it to zero.
    
    Reviewed by:    glebius
    Fixes:          c0256b31efcc ("routing: Add support for metric")
    Differential Revision:  https://reviews.freebsd.org/D61580
---
 sys/net/route/nhgrp_ctl.c | 102 +++++++++++++---------------------------------
 1 file changed, 29 insertions(+), 73 deletions(-)

diff --git a/sys/net/route/nhgrp_ctl.c b/sys/net/route/nhgrp_ctl.c
index 3d5546ffe317..d247024abd33 100644
--- a/sys/net/route/nhgrp_ctl.c
+++ b/sys/net/route/nhgrp_ctl.c
@@ -110,104 +110,57 @@ sort_weightened_nhops(struct weightened_nhop *wn, int num_nhops)
 }
 
 /*
- * In order to determine the minimum weight difference in the array
- * of weights, create a sorted array of weights, using spare "storage"
- * field in the `struct weightened_nhop`.
- * Assume weights to be (mostly) the same and use insertion sort to
- * make it sorted.
+ * Returns the greatest common divisor of @a and @b.
+ * The divisor of zero and x is x.
  */
-static void
-sort_weightened_nhops_weights(struct weightened_nhop *wn, int num_items)
+static uint32_t
+calc_gcd(uint32_t a, uint32_t b)
 {
-	wn[0].storage = wn[0].weight;
-	for (int i = 1, j = 0; i < num_items; i++) {
-		uint32_t weight = wn[i].weight; // read from 'weight' as it's not reordered
-		/* Move all weights > weight 1 position right */
-		for (j = i - 1; j >= 0 && wn[j].storage > weight; j--)
-			wn[j + 1].storage = wn[j].storage;
-		wn[j + 1].storage = weight;
+	uint32_t r;
+
+	while (b != 0) {
+		r = a % b;
+		a = b;
+		b = r;
 	}
+
+	return (a);
 }
 
 /*
  * Calculate minimum number of slots required to fit the existing
- * set of weights in the common use case where weights are "easily"
- * comparable.
- * Assumes @wn is sorted by weight ascending and each weight is > 0.
- * Returns number of slots or 0 if precise calculation failed.
+ * set of weights while maintaining weight coefficients
+ * after filtering by metric: the sum of the weights divided by
+ * their greatest common divisor.
+ *
  * Only calculate for nexthops with specified metric and ignore the rest.
+ * Returns number of slots, at most RIB_MAX_MPATH_WIDTH, or 0 if all
+ * weights are zero.
  *
  * Some examples:
  * note: (i, X) pair means (nhop=i, weight=X):
  * (1, 1) (2, 2) -> 3 slots [1, 2, 2]
  * (1, 100), (2, 200) -> 3 slots [1, 2, 2]
- * (1, 100), (2, 200), (3, 400) -> 7 slots [1, 2, 2, 3, 3, 3]
+ * (1, 100), (2, 200), (3, 400) -> 7 slots [1, 2, 2, 3, 3, 3, 3]
  */
 static uint32_t
-calc_min_mpath_slots_fast(struct weightened_nhop *wn, size_t num_items,
-    uint32_t metric, uint64_t *ptotal)
+calc_min_mpath_slots(const struct weightened_nhop *wn, size_t num_items,
+    uint32_t metric)
 {
-	uint32_t i, x, last, xmin = 0;
 	uint64_t total = 0;
+	uint32_t unit = 0;
 
-	// Get sorted array of weights in .storage field
-	sort_weightened_nhops_weights(wn, num_items);
-
-	/* start with lowest metric */
-	for (x = 0; x < num_items; x++) {
-		if (nhop_get_metric(wn[x].nh) == metric) {
-			xmin = wn[x].storage;
-			break;
-		}
-	}
-	last = 0;
-	for (i = x; i < num_items; i++) {
+	for (size_t i = 0; i < num_items; i++) {
 		if (nhop_get_metric(wn[i].nh) != metric)
 			continue;
 
-		total += wn[i].storage;
-		if ((wn[i].storage != last) &&
-		    ((wn[i].storage - last < xmin) || xmin == 0)) {
-			xmin = wn[i].storage - last;
-		}
-		last = wn[i].storage;
-	}
-	*ptotal = total;
-	/* xmin is the minimum unit of desired capacity */
-	if (xmin == 0 || (total % xmin) != 0)
-		return (0);
-	for (i = 0; i < num_items; i++) {
-		if ((wn[i].weight % xmin) != 0)
-			return (0);
+		total += wn[i].weight;
+		unit = calc_gcd(unit, wn[i].weight);
 	}
-
-	return ((uint32_t)(total / xmin));
-}
-
-/*
- * Calculate minimum number of slots required to fit the existing
- * set of weights while maintaining weight coefficients
- * after filtering by metric.
- *
- * Assume @wn is sorted by weight ascending and each weight is > 0.
- *
- * Tries to find simple precise solution first and falls back to
- *  RIB_MAX_MPATH_WIDTH in case of any failure.
- */
-static uint32_t
-calc_min_mpath_slots(struct weightened_nhop *wn, size_t num_items,
-    uint32_t metric)
-{
-	uint32_t v;
-	uint64_t total;
-
-	v = calc_min_mpath_slots_fast(wn, num_items, metric, &total);
 	if (total == 0)
 		return (0);
-	if ((v == 0) || (v > RIB_MAX_MPATH_WIDTH))
-		v = RIB_MAX_MPATH_WIDTH;
 
-	return (v);
+	return (MIN(total / unit, RIB_MAX_MPATH_WIDTH));
 }
 
 /*
@@ -549,6 +502,9 @@ nhgrp_alloc(uint32_t fibnum, int family, struct weightened_nhop *wn, int num_nho
 
 		if (nhop_get_metric(wn[i].nh) < min_metric)
 			min_metric = nhop_get_metric(wn[i].nh);
+
+		/* Groups are compared as bytes, do not leave this to the caller */
+		wn[i].storage = 0;
 	}
 
 	if ((nhg_priv = alloc_nhgrp(wn, num_nhops, min_metric)) == NULL) {