Page MenuHomeFreeBSD
Files F177571452

D61580.1794771130.diff
No OneTemporary
Actions

Authored By
Unknown
Size
11 KB
Referenced Files
None
Subscribers
None

D61580.1794771130.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
@@ -73,7 +73,6 @@
/* Cap multipath to 64, as the larger values would break rib_cmd_info bmasks */
CTASSERT(RIB_MAX_MPATH_WIDTH <= 64);
-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,
@@ -82,14 +81,22 @@
static void destroy_nhgrp_epoch(epoch_context_t ctx);
static void free_nhgrp_nhops(struct nhgrp_priv *nhg_priv);
-static int
-wn_cmp_idx(const void *a, const void *b)
+/*
+ * Compares the position of two nexthops in a group: nexthops are ordered
+ * by metric first and by nexthop index second.
+ */
+int
+nhgrp_cmp_wn(const void *a, const void *b)
{
const struct weightened_nhop *w_a = a;
const struct weightened_nhop *w_b = b;
+ uint32_t a_metric = w_a->nh->nh_priv->nh_metric;
+ uint32_t b_metric = w_b->nh->nh_priv->nh_metric;
uint32_t a_idx = w_a->nh->nh_priv->nh_idx;
uint32_t b_idx = w_b->nh->nh_priv->nh_idx;
+ if (a_metric != b_metric)
+ return (a_metric < b_metric ? -1 : 1);
if (a_idx < b_idx)
return (-1);
else if (a_idx > b_idx)
@@ -100,114 +107,68 @@
/*
* Perform in-place sorting for array of nexthops in @wn.
- * Sort by nexthop index ascending.
+ * Sort by metric ascending, then by nexthop index ascending:
+ * the nexthops with the lowest metric come first.
*/
static void
sort_weightened_nhops(struct weightened_nhop *wn, int num_nhops)
{
- qsort(wn, num_nhops, sizeof(struct weightened_nhop), wn_cmp_idx);
+ qsort(wn, num_nhops, sizeof(struct weightened_nhop), nhgrp_cmp_wn);
}
/*
- * 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.
- * Only calculate for nexthops with specified metric and ignore the rest.
+ * set of weights while maintaining weight coefficients
+ * after filtering by metric: the sum of the weights divided by
+ * their greatest common divisor.
+ *
+ * Assume @wn is sorted by metric ascending and only calculate for
+ * nexthops with the lowest metric.
+ * 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 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;
+ for (size_t i = 0; i < num_items; i++) {
+ if (wn[i].metric != wn[0].metric)
break;
- }
- }
- last = 0;
- for (i = x; 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;
+ total += wn[i].weight;
+ unit = calc_gcd(unit, wn[i].weight);
}
- *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);
- }
-
- 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));
}
/*
@@ -237,8 +198,7 @@
* Compile actual list of nexthops to be used by datapath from
* the nexthop group @dst.
* Since we only need nexthops with lowest metric, only process
- * nexthops with specified metric. The metric argument is taken
- * from input and is expected to be the lowest metric in weightened_nhop.
+ * the first nexthops of @x, which is sorted by metric ascending.
*
* For example, compiling control plane list of 2 nexthops
* [(200, A), (100, B)] would result in the datapath array
@@ -246,7 +206,7 @@
*/
static void
compile_nhgrp(struct nhgrp_priv *dst_priv, const struct weightened_nhop *x,
- uint32_t num_slots, uint32_t metric)
+ uint32_t num_slots)
{
struct nhgrp_object *dst;
int i, slot_idx, remaining_slots;
@@ -258,16 +218,17 @@
/* Calculate sum of all weights with lowest metric */
remaining_sum = nh_weight = 0;
for (i = 0; i < dst_priv->nhg_nh_count; i++) {
- if (nhop_get_metric(x[i].nh) == metric) {
- /*
- * Temporary store weight of unreachable nhops in nh_weight
- * to ensure we have at least one reachable nexthop.
- */
- if (NH_IS_VALID(x[i].nh))
- remaining_sum += x[i].weight;
- else
- nh_weight += x[i].weight;
- }
+ if (x[i].metric != x[0].metric)
+ break;
+
+ /*
+ * Temporary store weight of unreachable nhops in nh_weight
+ * to ensure we have at least one reachable nexthop.
+ */
+ if (NH_IS_VALID(x[i].nh))
+ remaining_sum += x[i].weight;
+ else
+ nh_weight += x[i].weight;
}
/* If no reachable nhops exist, include all */
@@ -278,10 +239,10 @@
remaining_slots = num_slots;
FIB_NH_LOG(LOG_DEBUG3, x[0].nh, "sum: %lu, slots: %d, lowest_metric: %u",
- remaining_sum, remaining_slots, metric);
+ remaining_sum, remaining_slots, x[0].metric);
for (i = 0; i < dst_priv->nhg_nh_count; i++) {
- if (nhop_get_metric(x[i].nh) != metric)
- continue;
+ if (x[i].metric != x[0].metric)
+ break;
/*
* Calculate number of slots for the current nexthop.
@@ -315,13 +276,13 @@
* Returns group with refcount=1 or NULL.
*/
static struct nhgrp_priv *
-alloc_nhgrp(struct weightened_nhop *wn, int num_nhops, uint32_t min_metric)
+alloc_nhgrp(struct weightened_nhop *wn, int num_nhops)
{
uint32_t nhgrp_size;
struct nhgrp_object *nhg;
struct nhgrp_priv *nhg_priv;
- nhgrp_size = calc_min_mpath_slots(wn, num_nhops, min_metric);
+ nhgrp_size = calc_min_mpath_slots(wn, num_nhops);
if (nhgrp_size == 0) {
/* Zero weights, abort */
return (NULL);
@@ -354,7 +315,7 @@
FIB_NH_LOG(LOG_DEBUG, wn[0].nh, "num_nhops: %d, compiled_nhop: %u",
num_nhops, nhgrp_size);
- compile_nhgrp(nhg_priv, wn, nhg->nhg_size, min_metric);
+ compile_nhgrp(nhg_priv, wn, nhg->nhg_size);
return (nhg_priv);
}
@@ -535,7 +496,6 @@
/* Sort nexthops & check there are no duplicates */
sort_weightened_nhops(wn, num_nhops);
uint32_t last_id = 0;
- uint32_t min_metric = nhop_get_metric(wn[0].nh);
for (int i = 0; i < num_nhops; i++) {
if (wn[i].nh->nh_priv->nh_control != ctl) {
*perror = EINVAL;
@@ -547,11 +507,11 @@
}
last_id = wn[i].nh->nh_priv->nh_idx;
- if (nhop_get_metric(wn[i].nh) < min_metric)
- min_metric = nhop_get_metric(wn[i].nh);
+ /* Cache the metric, the group is compiled from this array */
+ wn[i].metric = nhop_get_metric(wn[i].nh);
}
- if ((nhg_priv = alloc_nhgrp(wn, num_nhops, min_metric)) == NULL) {
+ if ((nhg_priv = alloc_nhgrp(wn, num_nhops)) == NULL) {
*perror = ENOMEM;
return (NULL);
}
@@ -1114,13 +1074,10 @@
{
struct nhgrp_object *nhg = nhg_priv->nhg;
const struct weightened_nhop *wn;
- uint32_t num_nhops, min_metric;
+ uint32_t num_nhops;
wn = nhgrp_get_nhops(nhg, &num_nhops);
-
- /* dataplane only has the lowest metric nhops, just pick one */
- min_metric = nhop_get_metric(nhg->nhops[0]);
- compile_nhgrp(nhg_priv, wn, nhg->nhg_size, min_metric);
+ compile_nhgrp(nhg_priv, wn, nhg->nhg_size);
}
void
diff --git a/sys/net/route/nhop.h b/sys/net/route/nhop.h
--- a/sys/net/route/nhop.h
+++ b/sys/net/route/nhop.h
@@ -158,7 +158,7 @@
struct weightened_nhop {
struct nhop_object *nh;
uint32_t weight;
- uint32_t storage;
+ uint32_t metric;
};
void nhop_free(struct nhop_object *nh);
diff --git a/sys/net/route/route_helpers.c b/sys/net/route/route_helpers.c
--- a/sys/net/route/route_helpers.c
+++ b/sys/net/route/route_helpers.c
@@ -330,17 +330,17 @@
* of primitive (RTM_DEL, RTM_ADD) operations.
*
* Leverage the fact that each nexthop group has its nexthops sorted
- * by their indices.
+ * by their metrics first and by their indices second. The numbers
+ * below are the positions of the nexthops in that order.
* [1] -> [1, 2] = A{2}
* [1, 2] -> [1] = D{2}
* [1, 2, 4] -> [1, 3, 4] = D{2}, A{3}
* [1, 2] -> [3, 4] = D{1}, D{2}, A{3}, A{4]
*/
while ((idx_old < num_old) && (idx_new < num_new)) {
- uint32_t nh_idx_old = wn_old[idx_old].nh->nh_priv->nh_idx;
- uint32_t nh_idx_new = wn_new[idx_new].nh->nh_priv->nh_idx;
+ int cmp = nhgrp_cmp_wn(&wn_old[idx_old], &wn_new[idx_new]);
- if (nh_idx_old == nh_idx_new) {
+ if (cmp == 0) {
if (wn_old[idx_old].weight != wn_new[idx_new].weight) {
/* Update weight by providing del/add notifications */
notify_del(&rc_del, &wn_old[idx_old], cb, cbdata);
@@ -348,12 +348,12 @@
}
idx_old++;
idx_new++;
- } else if (nh_idx_old < nh_idx_new) {
+ } else if (cmp < 0) {
/* [1, ~2~, 4], [1, ~3~, 4] */
notify_del(&rc_del, &wn_old[idx_old], cb, cbdata);
idx_old++;
} else {
- /* nh_idx_old > nh_idx_new. */
+ /* The new nexthop sorts before the old one. */
notify_add(&rc_add, &wn_new[idx_new], cb, cbdata);
idx_new++;
}
diff --git a/sys/net/route/route_var.h b/sys/net/route/route_var.h
--- a/sys/net/route/route_var.h
+++ b/sys/net/route/route_var.h
@@ -311,6 +311,7 @@
struct route_nhop_data *rnd_orig, struct route_nhop_data *rnd_add,
struct route_nhop_data *rnd_new);
void nhgrp_recompile(struct rib_head *rh);
+int nhgrp_cmp_wn(const void *a, const void *b);
void nhgrp_ref_object(struct nhgrp_object *nhg);
uint32_t nhgrp_get_idx(const struct nhgrp_object *nhg);

File Metadata

Mime Type
text/plain
Expires
Sun, Nov 15, 7:32 PM (23 h, 25 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
41747521
Default Alt Text
D61580.1794771130.diff (11 KB)

Event Timeline