Page MenuHomeFreeBSD
Files F132603090

D35599.id107440.diff
No OneTemporary
Actions

D35599.id107440.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
@@ -76,7 +76,7 @@
/* 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 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 @@
* (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 @@
* 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 @@
}
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
--- a/sys/net/route/nhop.h
+++ b/sys/net/route/nhop.h
@@ -166,6 +166,7 @@
struct weightened_nhop {
struct nhop_object *nh;
uint32_t weight;
+ uint32_t storage;
};
void nhop_free(struct nhop_object *nh);

File Metadata

Mime Type
text/plain
Expires
Sun, Oct 19, 8:27 AM (15 h, 34 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
23917795
Default Alt Text
D35599.id107440.diff (4 KB)

Event Timeline