Page Menu
Home
FreeBSD
Search
Configure Global Search
Log In
Files
F177686667
D61580.1795032374.diff
No One
Temporary
Actions
View File
Edit File
Delete File
View Transforms
Subscribe
Flag For Later
Award Token
Authored By
Unknown
Size
4 KB
Referenced Files
None
Subscribers
None
D61580.1795032374.diff
View Options
diff --git a/sys/net/route/nhgrp_ctl.c b/sys/net/route/nhgrp_ctl.c
--- a/sys/net/route/nhgrp_ctl.c
+++ b/sys/net/route/nhgrp_ctl.c
@@ -110,104 +110,57 @@
}
/*
- * 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 @@
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) {
File Metadata
Details
Attached
Mime Type
text/plain
Expires
Wed, Nov 18, 8:06 PM (1 h, 39 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
41803183
Default Alt Text
D61580.1795032374.diff (4 KB)
Attached To
Mode
D61580: routing: Fix the size of nexthop groups with mixed metrics
Attached
Detach File
Event Timeline