The initialization routines of the histogram type
do not behave properly for some values.
In the linear initialization, each wall value
is computed with incorrect precedence, resulting sometimes in decreasing
values.
In the logarithmic initialization, the type used (int) does not support
the full range of input types (u32). It sometimes overflow to negative
values, rendering the whole logic bogus.
Some edge cases were also forgotten, resulting in not perfectly clean
values sometimes.
Linear init with [min, max]:
[0, UINT32_MAX]:
.wall = {0, 143165576 <repeats 16 times>,
143165575 <repeats 14 times>,
4294967295},
[99536792, 1704485614]:
.wall[2] = 206533380,
.wall[3] = 116866097, (decreasing)
.wall[5] = 223862685,
.wall[6] = 134195403, (decreasing)
[...]
[82308811, 3821578143]:
.wall[15] = 2433814800,
.wall[16] = 2300193595, (decreasing)
[...]
Logarithmic init with [min, max]:
[2086073122, 3209049844]:
.wall = {2086073122, 2116237594, 2146838243,
2147483648 <repeats 27 times>,
3209049844, 4294967295},
Fix the issues and add unit-tests for the relevant functions.
Signed-off-by: Gaetan Rivet <[email protected]>
---
lib/dpif-netdev-perf.c | 16 +++--
lib/dpif-netdev-perf.h | 4 ++
tests/automake.mk | 1 +
tests/library.at | 5 ++
tests/test-histogram.c | 155 +++++++++++++++++++++++++++++++++++++++++
5 files changed, 175 insertions(+), 6 deletions(-)
create mode 100644 tests/test-histogram.c
diff --git a/lib/dpif-netdev-perf.c b/lib/dpif-netdev-perf.c
index 1cd4ee0842..0d029ff00e 100644
--- a/lib/dpif-netdev-perf.c
+++ b/lib/dpif-netdev-perf.c
@@ -102,22 +102,26 @@ pmd_perf_estimate_tsc_frequency(void)
/* Histogram functions. */
-static void
+void
histogram_walls_set_lin(struct histogram *hist, uint32_t min, uint32_t max)
{
- int i;
+ uint32_t i, inc;
ovs_assert(min < max);
+ inc = (max - min) / (NUM_BINS - 2);
for (i = 0; i < NUM_BINS-1; i++) {
- hist->wall[i] = min + (i * (max - min)) / (NUM_BINS - 2);
+ hist->wall[i] = min + (i * inc);
+ }
+ if (max != UINT32_MAX) {
+ hist->wall[NUM_BINS - 2] = max;
}
hist->wall[NUM_BINS-1] = UINT32_MAX;
}
-static void
+void
histogram_walls_set_log(struct histogram *hist, uint32_t min, uint32_t max)
{
- int i, start, bins, wall;
+ uint32_t i, start, bins, wall;
double log_min, log_max;
ovs_assert(min < max);
@@ -139,7 +143,7 @@ histogram_walls_set_log(struct histogram *hist, uint32_t
min, uint32_t max)
wall = MAX(wall, exp(log_min + (i * (log_max - log_min)) / (bins-1)));
hist->wall[start + i] = wall++;
}
- if (hist->wall[NUM_BINS-2] < max) {
+ if (hist->wall[NUM_BINS - 2] < max && max != UINT32_MAX) {
hist->wall[NUM_BINS-2] = max;
}
hist->wall[NUM_BINS-1] = UINT32_MAX;
diff --git a/lib/dpif-netdev-perf.h b/lib/dpif-netdev-perf.h
index 84beced151..9bfc474293 100644
--- a/lib/dpif-netdev-perf.h
+++ b/lib/dpif-netdev-perf.h
@@ -346,6 +346,10 @@ histogram_add_sample(struct histogram *hist, uint32_t val)
hist->bin[NUM_BINS-1]++;
}
+void histogram_walls_set_lin(struct histogram *hist,
+ uint32_t min, uint32_t max);
+void histogram_walls_set_log(struct histogram *hist,
+ uint32_t min, uint32_t max);
uint64_t histogram_samples(const struct histogram *hist);
/* This function is used to advance the given history index by positive
diff --git a/tests/automake.mk b/tests/automake.mk
index 59f5387612..b92dd70f37 100644
--- a/tests/automake.mk
+++ b/tests/automake.mk
@@ -461,6 +461,7 @@ tests_ovstest_SOURCES = \
tests/test-hash.c \
tests/test-heap.c \
tests/test-hindex.c \
+ tests/test-histogram.c \
tests/test-hmap.c \
tests/test-id-fpool.c \
tests/test-json.c \
diff --git a/tests/library.at b/tests/library.at
index 82ac80a271..20899bde00 100644
--- a/tests/library.at
+++ b/tests/library.at
@@ -32,6 +32,11 @@ AT_CHECK([ovstest test-rculist], [0], [.....
])
AT_CLEANUP
+AT_SETUP([histogram])
+AT_KEYWORDS([histogram])
+AT_CHECK([ovstest test-histogram], [0], [])
+AT_CLEANUP
+
AT_SETUP([cuckoo hash])
AT_KEYWORDS([cmap])
AT_CHECK([ovstest test-cmap check 1], [0], [...
diff --git a/tests/test-histogram.c b/tests/test-histogram.c
new file mode 100644
index 0000000000..d43f8d7012
--- /dev/null
+++ b/tests/test-histogram.c
@@ -0,0 +1,155 @@
+/*
+ * Copyright (c) 2025 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <config.h>
+
+#include <stdint.h>
+
+#include "dpif-netdev-perf.h"
+#include "openvswitch/util.h"
+#include "ovstest.h"
+#include "random.h"
+#include "util.h"
+
+#define FUZZ(v) { v == 0 ? 0 : v - 1, v, v == UINT32_MAX ? v : v + 1 }
+
+static inline bool
+fuzzy_eq(uint32_t v, uint32_t target)
+{
+ uint32_t bounds[3] = FUZZ(target);
+
+ return (v == bounds[0]
+ || v == bounds[1]
+ || v == bounds[2]);
+}
+
+static inline bool eq(uint32_t v, uint32_t target){ return v == target; }
+
+static inline bool
+fuzzy_lt(uint32_t v, uint32_t target)
+{
+ uint32_t bounds[3] = FUZZ(target);
+ return (v < bounds[0]);
+}
+
+static inline bool lt(uint32_t v, uint32_t target){ return v < target; }
+
+static void
+test_histogram_check(struct histogram *hist,
+ uint32_t min, uint32_t max,
+ bool fuzzy)
+{
+ enum { EQ, LT };
+ bool (*ops[])(uint32_t, uint32_t) = {
+ [EQ] = fuzzy ? fuzzy_eq : eq,
+ [LT] = fuzzy ? fuzzy_lt : lt,
+ };
+ bool min_found = false, max_found = false;
+
+ for (size_t i = 0; i < NUM_BINS; i++) {
+ if (ops[EQ](hist->wall[i], min)) {
+ min_found = true;
+ }
+ if (hist->wall[i] == max) {
+ max_found = true;
+ }
+ }
+ ovs_assert(min_found);
+ ovs_assert(max_found);
+ for (size_t i = 0; i < NUM_BINS - 1; i++) {
+ if (ops[LT](hist->wall[i], min)) {
+ ovs_abort(0, "A bucket is under the requested minimum. "
+ "For [%"PRIu32",%"PRIu32"]: "
+ "wall[%"PRIuSIZE"](%"PRIu32") < min(%"PRIu32")",
+ min, max, i, hist->wall[i], min);
+ }
+ if (hist->wall[i] > max) {
+ ovs_abort(0, "A bucket is over the requested maximum. "
+ "For [%"PRIu32",%"PRIu32"]: "
+ "wall[%"PRIuSIZE"](%"PRIu32") > max(%"PRIu32")",
+ min, max, i, hist->wall[i], max);
+ }
+ if (hist->wall[i] >= hist->wall[i + 1]) {
+ char res = hist->wall[i] > hist->wall[i + 1] ? '>' : '=';
+ ovs_abort(0, "The histogram buckets are not strictly increasing.\n"
+ "For [%"PRIu32",%"PRIu32"]: "
+ "wall[%"PRIuSIZE"](%"PRIu32") %c "
+ "wall[%"PRIuSIZE"](%"PRIu32")",
+ min, max, i, hist->wall[i], res, i + 1, hist->wall[i + 1]);
+ }
+ }
+}
+
+static void
+test_histogram_linear(uint32_t min, uint32_t max)
+{
+ struct histogram hist;
+
+ memset(&hist, 0, sizeof hist);
+ histogram_walls_set_lin(&hist, min, max);
+ test_histogram_check(&hist, min, max, false);
+}
+
+static void
+test_histogram_logarithmic(uint32_t min, uint32_t max)
+{
+ struct histogram hist;
+
+ memset(&hist, 0, sizeof hist);
+ histogram_walls_set_log(&hist, min, max);
+ test_histogram_check(&hist, min, max, true);
+}
+
+static void
+test_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
+{
+ enum { LIN = 1, LOG = 2 };
+ struct {
+ uint32_t type;
+ uint32_t min, max;
+ } test_cases[] = {
+ /* Edge cases. */
+ { LIN | LOG, 0, UINT32_MAX },
+ { LIN | LOG, 1, UINT32_MAX },
+ { LIN | LOG, 0, UINT32_MAX - 1 },
+ { LIN | LOG, 1, UINT32_MAX - 1 },
+ { LIN , UINT32_MAX - (NUM_BINS - 1), UINT32_MAX },
+ { LIN , UINT32_MAX - (NUM_BINS - 1), UINT32_MAX - 1 },
+ /* Congruent case with inc=1. */
+ { LIN , 5, 5 + NUM_BINS },
+ /* Non-congruent case with inc<1. */
+ { LIN , 5, 5 + (NUM_BINS - 1) },
+ /* Non-congruent case with inc<1. */
+ { LIN , 5, 5 + (NUM_BINS - 2) },
+ { LIN | LOG, 0x88888888, 0x99999999 },
+ { LIN | LOG, 2203470768, 2441348688 },
+ { LIN | LOG, 1732474832, 2432533624 },
+ };
+
+ for (size_t i = 0; i < ARRAY_SIZE(test_cases); i++) {
+ if (test_cases[i].type & LIN) {
+ test_histogram_linear(test_cases[i].min, test_cases[i].max);
+ }
+ }
+
+ for (size_t i = 0; i < ARRAY_SIZE(test_cases); i++) {
+ if (test_cases[i].type & LOG) {
+ test_histogram_logarithmic(test_cases[i].min, test_cases[i].max);
+ }
+ }
+}
+
+OVSTEST_REGISTER("test-histogram", test_main);
--
2.34.1
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
