From nobody Fri Nov 20 10:23:21 2026 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4jWBHs4n2xz71Xks for ; Fri, 20 Nov 2026 10:23:21 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange x25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by mx1.freebsd.org (Postfix) with ESMTPS id 4jWBHs2Vwbz3Bqg for ; Fri, 20 Nov 2026 10:23:21 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1795170201; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=0IYn4Rge6ixKCAxEBKK1jqJdqMLi0sJefbB7TlppJRY=; b=XRoCqIwBYZ+f6VUcDcnTMlkS0xTziy4vd2fN3UqfBY9YJyiZaFs2vaYNEqjNliGH8Bajnh NWgF3NVJa5Vkll0f8wRYwiqqCKII+c0PYqA8AKECWAtdEH9in6vBWcVdjdURwa4BTzau6y xTjI8FaA1y8QOdHMZSCQdjb4gmbgjUWH1s+3w+cfea63HIEBc0FUgppMlrMTJ3Jhl5Xrub 3YwZu7K87HR+VyHN0aVobvPVWqtRONa0casiya8SlapM/mblWqu5NzJ8By9+NtAAdLzsE7 pksoCwLNE6lf1NdukyDPdldJxH8g0oAvHJdxV0VLfyeJP2jv3VjErXkWXLIqHg== ARC-Seal: i=1; a=rsa-sha256; d=freebsd.org; s=dkim; cv=none; t=1795170201; b=nWfBhJPEWZ8os0CuNfCaDu0yzkulIaQqpwVZThLAy+7pghQq9ep3DtJEhotRWApSGG66OO SUnHRTrrXbkrz9Z34m0FkEe1x5SiMOiPXmSSkSNJ5GzlMkcPaX1ZZpHBNaQmVbAkvX3r4t 9EXFjn/GjCq0bVgmnE4xeSzbkkcIKjIhU3em5Tpgts2Umr13Yb5xsdhZMyzxWihX7HldhY IzBXSUc6hEQEVTxGHxxX00fLuW5GcVeOZSY+iIdfOCAU5Lj6WjMQQ+w7ubM7IkXBJP3aKy ea44DgeB2mBUKdxNVpA+HwSg8Jkgep35lAFDYt4S0nV9mKv5bJrJFvW7zcCQOA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1795170201; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=0IYn4Rge6ixKCAxEBKK1jqJdqMLi0sJefbB7TlppJRY=; b=V1TAiH8pyXdU3aBD9WIUk03t/wNsUtzFhxe8Xgf7DZPJZhnFwfrNLZJ642gMmS1XjBihhu SA3+UJuYKbSEsV5136tOFPTaHET4ZCWQ55cmBETl+G+qroodZD+kVHVThLclGChiL0l2ed AzdmRRvf8bhX5q1Hz1WuhB8JaG3F3IO6bbhWkzbQsxt9C/JPOESGSMHnGjZXvrV5KZWlxz Mj/Knc8Ij/e2ha5ZzKYIdR8pycZgpBjUSc1pPZApV4pdUPtArLKfNPAIW2ThyKO2CmYHpc Frx9TLKoE9KnX1NJvGO+hqVFbjuWtiF8paIsa6EIOrcDuRmMAqPm0JNwt+7c/w== ARC-Authentication-Results: i=1; mx1.freebsd.org; none Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) by mxrelay.nyi.freebsd.org (Postfix) with ESMTP id 4jWBHs28QQzkms for ; Fri, 20 Nov 2026 10:23:21 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from git (uid 1279) (envelope-from git@FreeBSD.org) id 192be by gitrepo.freebsd.org (DragonFly Mail Agent v0.13+ on gitrepo.freebsd.org); Fri, 20 Nov 2026 10:23:21 +0000 To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Pouria Mousavizadeh Tehrani Subject: git: b450c1d7f7f4 - main - routing: Fix the size of nexthop groups with mixed metrics List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all X-BeenThere: dev-commits-src-all@freebsd.org List-Id: Commit messages for all branches of the src repository List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: pouria X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: b450c1d7f7f41aab9296b857d797122ef4c37f65 Auto-Submitted: auto-generated Date: Fri, 20 Nov 2026 10:23:21 +0000 Message-Id: <6b001f99.192be.65280b65@gitrepo.freebsd.org> The branch main has been updated by pouria: URL: https://cgit.FreeBSD.org/src/commit/?id=b450c1d7f7f41aab9296b857d797122ef4c37f65 commit b450c1d7f7f41aab9296b857d797122ef4c37f65 Author: Pouria Mousavizadeh Tehrani AuthorDate: 2026-11-20 10:18:19 +0000 Commit: Pouria Mousavizadeh Tehrani 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) {