From nobody Mon Jun 27 17:32:53 2022 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 AD45F8A32C1; Mon, 27 Jun 2022 17:32:53 +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 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4LWvv94X4hz3DHH; Mon, 27 Jun 2022 17:32:53 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1656351173; 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=PLtEbYc4HKd7ifYwzBIaZRAnlUBGmHLUioVL+w59m0A=; b=DSX0u9CicKeoAWWkgsfeEh7Emw8lHV9NjmKm4e467FNp54ESDAt2oBtBmafe18+FFknkaz 5UDmw09ep5cebJbzardVNBy65512VaIQF0nyyL95qIhgEP68FPSj7zt9EYKyM1uX0K6MrD JrlJk7NKmqQu2us4cV1+q8h07C5tLW3UekA6AwG9aWT1Z63Qmbk/DZUEPYEejBqNGUUmZF n3Mffak3DbYa+nlS1EUW7GkvagCaYK/MM1GAlQbEsMHfZyZYWe7DLUR392HinZrv8mMZsV 3kc3BLkFkQFjVS4veQhSHFAJA3cFQLVpe6bxxASYEtzmEQiGTdZjySB8uSAUdg== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (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) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 7B2184B19; Mon, 27 Jun 2022 17:32:53 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 25RHWrf2055310; Mon, 27 Jun 2022 17:32:53 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 25RHWr53055309; Mon, 27 Jun 2022 17:32:53 GMT (envelope-from git) Date: Mon, 27 Jun 2022 17:32:53 GMT Message-Id: <202206271732.25RHWr53055309@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: "Alexander V. Chernikov" Subject: git: 76f1ab8eff9e - main - routing: actually sort nexthops in nhgs by their index List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: melifaro X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 76f1ab8eff9ede509906e539c10373db44528690 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1656351173; 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=PLtEbYc4HKd7ifYwzBIaZRAnlUBGmHLUioVL+w59m0A=; b=nA+XwnTcXAPM79AxwjIp+MS1pVYMxPC27BYwvHcrdkMUG4DNjQ/XhZ+nm8xuU6vmKbcjFm rKYvqfCSwSOsvbzaVqiyyqudOkTpLFzV059KW84+J2y+wlCdmwzOnN1TehJxnHPgAZHz7f mKShD8Joj7NEXIgS4xBYccIp4roRX56g9/yykUPs/wB2BCv/W4UUs0hZdbxORkz+z+HDNf L5+5belcAyvEhh1Amcs1884Z4dGJ7NvtG3RcEG1j7o78MmlzbKmpTSlVqgVcDcBFvUpVCH a8vek+LBWXHM8jjr3t33YkP2m6R0ydwo/3o9dYxZSa2SEWZJRmNuCDen9N4QSg== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1656351173; a=rsa-sha256; cv=none; b=mbJtZxJQBiUUzbKt9Kj3Y8Rbnw2WjYbNLTNqZq7+AK+OqG6jMJ1V5Odz8tLqG1U+g/ijBI v30+gekpg8Ighfr2DUposjF0cUZdqCeonQr1asRgtxdj9FKRSsPJHA8Dmyt4C+rihXuOPa fwIJ+F969fs3cQUJla3uuL7RZrpBMLNS0pYe0w2GnNJlVVP6axPhE1EQC0YDx2Dtxd6IJV vZhAKmCs7C8EFOuL/Ak7ydLHnK8NuqZztX1uM3VFW8R7Uf3UyJdBK36UojuFuhiiNC2r5R uNo5Cc7lruAwQl+7duzguPKfMuzjZDPPqUFk6XV6qjAPIkLNgTbvwh3wGYTHmQ== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by melifaro: URL: https://cgit.FreeBSD.org/src/commit/?id=76f1ab8eff9ede509906e539c10373db44528690 commit 76f1ab8eff9ede509906e539c10373db44528690 Author: Alexander V. Chernikov AuthorDate: 2022-06-27 17:19:50 +0000 Commit: Alexander V. Chernikov CommitDate: 2022-06-27 17:30:52 +0000 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 Differential Revision: https://reviews.freebsd.org/D35599 MFC after: 2 weeks --- sys/net/route/nhgrp_ctl.c | 77 ++++++++++++++++++++++++++++++----------------- sys/net/route/nhop.h | 1 + 2 files changed, 50 insertions(+), 28 deletions(-) diff --git a/sys/net/route/nhgrp_ctl.c b/sys/net/route/nhgrp_ctl.c index ee3ac9bec3d6..bad237a334ef 100644 --- a/sys/net/route/nhgrp_ctl.c +++ b/sys/net/route/nhgrp_ctl.c @@ -76,7 +76,7 @@ CHK_STRUCT_FIELD_GENERIC(struct nhop_object, nh_flags, struct nhgrp_object, nhg_ /* Cap multipath to 64, as the larger values would break rib_cmd_info bmasks */ CTASSERT(RIB_MAX_MPATH_WIDTH <= 64); -static int wn_cmp(const void *a, const void *b); +static int wn_cmp_idx(const void *a, const void *b); static void sort_weightened_nhops(struct weightened_nhop *wn, int num_nhops); static struct nhgrp_priv *get_nhgrp(struct nh_control *ctl, @@ -86,40 +86,50 @@ static void destroy_nhgrp_epoch(epoch_context_t ctx); static void free_nhgrp_nhops(struct nhgrp_priv *nhg_priv); static int -wn_cmp(const void *a, const void *b) +wn_cmp_idx(const void *a, const void *b) { - const struct weightened_nhop *wa = a; - const struct weightened_nhop *wb = b; + const struct weightened_nhop *w_a = a; + const struct weightened_nhop *w_b = b; + uint32_t a_idx = w_a->nh->nh_priv->nh_idx; + uint32_t b_idx = w_b->nh->nh_priv->nh_idx; - if (wa->weight > wb->weight) - return (1); - else if (wa->weight < wb->weight) + if (a_idx < b_idx) return (-1); - - /* Compare nexthops by pointer */ - if (wa->nh > wb->nh) + else if (a_idx > b_idx) return (1); - else if (wa->nh < wb->nh) - return (-1); else return (0); } /* * Perform in-place sorting for array of nexthops in @wn. - * - * To avoid nh groups duplication, nexthops/weights in the - * @wn need to be ordered deterministically. - * As this sorting is needed only for the control plane functionality, - * there are no specific external requirements. - * - * Sort by weight first, to ease calculation of the slot sizes. + * Sort by nexthop index ascending. */ static void sort_weightened_nhops(struct weightened_nhop *wn, int num_nhops) { - qsort(wn, num_nhops, sizeof(struct weightened_nhop), wn_cmp); + qsort(wn, num_nhops, sizeof(struct weightened_nhop), wn_cmp_idx); +} + +/* + * 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. + */ +static void +sort_weightened_nhops_weights(struct weightened_nhop *wn, int num_items) +{ + 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; + } } /* @@ -136,19 +146,26 @@ sort_weightened_nhops(struct weightened_nhop *wn, int num_nhops) * (1, 100), (2, 200), (3, 400) -> 7 slots [1, 2, 2, 3, 3, 3] */ static uint32_t -calc_min_mpath_slots_fast(const struct weightened_nhop *wn, size_t num_items) +calc_min_mpath_slots_fast(struct weightened_nhop *wn, size_t num_items, + uint64_t *ptotal) { uint32_t i, last, xmin; uint64_t total = 0; + // Get sorted array of weights in .storage field + sort_weightened_nhops_weights(wn, num_items); + last = 0; - xmin = wn[0].weight; + xmin = wn[0].storage; for (i = 0; i < num_items; i++) { - total += wn[i].weight; - if ((wn[i].weight - last < xmin) && (wn[i].weight != last)) - xmin = wn[i].weight - last; - last = wn[i].weight; + 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 ((total % xmin) != 0) return (0); @@ -170,11 +187,14 @@ calc_min_mpath_slots_fast(const struct weightened_nhop *wn, size_t num_items) * RIB_MAX_MPATH_WIDTH in case of any failure. */ static uint32_t -calc_min_mpath_slots(const struct weightened_nhop *wn, size_t num_items) +calc_min_mpath_slots(struct weightened_nhop *wn, size_t num_items) { uint32_t v; + uint64_t total; - v = calc_min_mpath_slots_fast(wn, num_items); + v = calc_min_mpath_slots_fast(wn, num_items, &total); + if (total == 0) + return (0); if ((v == 0) || (v > RIB_MAX_MPATH_WIDTH)) v = RIB_MAX_MPATH_WIDTH; @@ -364,6 +384,7 @@ nhgrp_free(struct nhgrp_object *nhg) } NET_EPOCH_EXIT(et); + KASSERT((nhg_priv->nhg_idx == 0), ("gr_idx != 0")); epoch_call(net_epoch_preempt, destroy_nhgrp_epoch, &nhg_priv->nhg_epoch_ctx); } diff --git a/sys/net/route/nhop.h b/sys/net/route/nhop.h index 1d37a84b68b4..12bbe163788f 100644 --- a/sys/net/route/nhop.h +++ b/sys/net/route/nhop.h @@ -166,6 +166,7 @@ struct nhop_object { struct weightened_nhop { struct nhop_object *nh; uint32_t weight; + uint32_t storage; }; void nhop_free(struct nhop_object *nh);