|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [PATCH 2/2] tootls/tests: introduce unit tests for rangesets
Introduce some basic infrastructure for doing rangeset unit tests, and add
a few tests that ensure correctness of rangeset subtraction.
Signed-off-by: Roger Pau Monné <roger.pau@xxxxxxxxxx>
---
tools/tests/Makefile | 1 +
tools/tests/rangeset/Makefile | 45 ++++++
tools/tests/rangeset/harness.h | 71 +++++++++
tools/tests/rangeset/test-rangeset.c | 228 +++++++++++++++++++++++++++
4 files changed, 345 insertions(+)
create mode 100644 tools/tests/rangeset/Makefile
create mode 100644 tools/tests/rangeset/harness.h
create mode 100644 tools/tests/rangeset/test-rangeset.c
diff --git a/tools/tests/Makefile b/tools/tests/Makefile
index 1319c3a9d88c..3e60ab6b268d 100644
--- a/tools/tests/Makefile
+++ b/tools/tests/Makefile
@@ -10,6 +10,7 @@ SUBDIRS-$(CONFIG_X86) += x86_emulator
endif
SUBDIRS-y += xenstore
SUBDIRS-y += depriv
+SUBDIRS-y += rangeset
SUBDIRS-y += vpci
SUBDIRS-y += paging-mempool
diff --git a/tools/tests/rangeset/Makefile b/tools/tests/rangeset/Makefile
new file mode 100644
index 000000000000..451f67e1920f
--- /dev/null
+++ b/tools/tests/rangeset/Makefile
@@ -0,0 +1,45 @@
+XEN_ROOT=$(CURDIR)/../../..
+include $(XEN_ROOT)/tools/Rules.mk
+
+TARGET := test-rangeset
+
+.PHONY: all
+all: $(TARGET)
+
+.PHONY: run
+run: $(TARGET)
+ ./$<
+
+.PHONY: clean
+clean:
+ $(RM) -- *.o $(TARGET) $(DEPS_RM)
+
+.PHONY: distclean
+distclean: clean
+ $(RM) -- *~
+
+.PHONY: install
+install: all
+ $(INSTALL_DIR) $(DESTDIR)$(LIBEXEC_BIN)
+ $(INSTALL_PROG) $(TARGET) $(DESTDIR)$(LIBEXEC_BIN)
+
+.PHONY: uninstall
+uninstall:
+ $(RM) -- $(addprefix $(DESTDIR)$(LIBEXEC_BIN)/,$(TARGET))
+
+list.h: $(XEN_ROOT)/xen/include/xen/list.h
+rangeset.h: $(XEN_ROOT)/xen/include/xen/rangeset.h
+list.h rangeset.h:
+ sed -e '/#include/d' <$< >$@
+
+rangeset.c: $(XEN_ROOT)/xen/common/rangeset.c list.h rangeset.h
+ # Remove includes and add the test harness header
+ sed -e '/#include/d' -e '1s/^/#include "harness.h"/' <$< >$@
+
+CFLAGS += -D__XEN_TOOLS__
+CFLAGS += $(APPEND_CFLAGS)
+CFLAGS += $(CFLAGS_xeninclude)
+LDFLAGS += $(APPEND_LDFLAGS)
+
+test-rangeset: rangeset.o test-rangeset.o
+ $(CC) $^ -o $@ $(LDFLAGS)
diff --git a/tools/tests/rangeset/harness.h b/tools/tests/rangeset/harness.h
new file mode 100644
index 000000000000..a60ebff72d0f
--- /dev/null
+++ b/tools/tests/rangeset/harness.h
@@ -0,0 +1,71 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+/*
+ * Unit tests for rangesets.
+ *
+ * Copyright (C) 2025 Cloud Software Group
+ */
+
+#ifndef _TEST_HARNESS_
+#define _TEST_HARNESS_
+
+#include <assert.h>
+#include <errno.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <xen-tools/common-macros.h>
+
+#define smp_wmb()
+#define __must_check __attribute__((__warn_unused_result__))
+#define cf_check
+
+#define BUG_ON(x) assert(!(x))
+#define ASSERT(x) assert(x)
+
+#include "list.h"
+#include "rangeset.h"
+
+typedef bool rwlock_t;
+typedef bool spinlock_t;
+
+struct domain {
+ unsigned int domain_id;
+ struct list_head rangesets;
+ spinlock_t rangesets_lock;
+};
+
+/* For rangeset_domain_{initialize,printk}() */
+#define spin_lock_init(l) (*(l) = false)
+#define spin_lock(l) (*(l) = true)
+#define spin_unlock(l) (*(l) = false)
+
+/* For rangeset->lock */
+#define rwlock_init(l) (*(l) = false)
+#define read_lock(l) (*(l) = true)
+#define read_unlock(l) (*(l) = false)
+#define write_lock(l) (*(l) = true)
+#define write_unlock(l) (*(l) = false)
+
+#define xmalloc(type) ((type *)malloc(sizeof(type)))
+#define xfree free
+
+#define unlikely
+
+#define safe_strcpy strcpy
+
+#define printk printf
+
+#endif
+
+/*
+ * Local variables:
+ * mode: C
+ * c-file-style: "BSD"
+ * c-basic-offset: 4
+ * indent-tabs-mode: nil
+ * End:
+ */
diff --git a/tools/tests/rangeset/test-rangeset.c
b/tools/tests/rangeset/test-rangeset.c
new file mode 100644
index 000000000000..b44cd217a050
--- /dev/null
+++ b/tools/tests/rangeset/test-rangeset.c
@@ -0,0 +1,228 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+/*
+ * Unit tests for rangesets.
+ *
+ * Copyright (C) 2025 Cloud Software Group
+ */
+
+#include "harness.h"
+
+struct range {
+ unsigned long start, end;
+};
+
+struct action {
+ enum {
+ ADD,
+ REMOVE,
+ } action;
+ struct range r;
+};
+
+#define DECLARE_ACTIONS(nr) static const struct action actions ## nr []
+#define DECLARE_RESULTS(nr) static const struct range results ## nr []
+
+/*
+ * Subtract range with tail overlap on existing range:
+ *
+ * { 0, 1, 4, 5 } - { 3, 4 } = { 0, 1, 5, 5 }
+ */
+DECLARE_ACTIONS(0) = {
+ { ADD, { 0, 1 } },
+ { ADD, { 4, 5 } },
+ { REMOVE, { 3, 4 } },
+};
+DECLARE_RESULTS(0) = {
+ { 0, 1 }, { 5, 5 },
+};
+
+/*
+ * Subtract range with complete and tail overlap on existing ranges:
+ *
+ * { 0, 1, 4, 5, 7, 8 } - { 3, 4, 5, 6, 7 } = { 0, 1, 8 }
+ */
+DECLARE_ACTIONS(1) = {
+ { ADD, { 0, 1 } },
+ { ADD, { 4, 5 } },
+ { ADD, { 7, 8 } },
+ { REMOVE, { 3, 7 } },
+};
+DECLARE_RESULTS(1) = {
+ { 0, 1 }, { 8, 8 },
+};
+
+/*
+ * Subtract range with no overlap:
+ *
+ * { 0, 1, 4, 5 } - { 2, 3 } = { 0, 1, 4, 5 }
+ */
+DECLARE_ACTIONS(2) = {
+ { ADD, { 0, 1 } },
+ { ADD, { 4, 5 } },
+ { REMOVE, { 2, 3 } },
+};
+DECLARE_RESULTS(2) = {
+ { 0, 1 }, { 4, 5 },
+};
+
+/*
+ * Subtract range with partial overlap on two existing ranges:
+ *
+ * { 0, 1, 4, 5 } - { 1, 4 } = { 0, 5 }
+ */
+DECLARE_ACTIONS(3) = {
+ { ADD, { 0, 1 } },
+ { ADD, { 4, 5 } },
+ { REMOVE, { 1, 4 } },
+};
+DECLARE_RESULTS(3) = {
+ { 0, 0 }, { 5, 5 },
+};
+
+static const struct test {
+ unsigned int nr_actions, nr_results;
+ const struct action *actions;
+ const struct range *result;
+} tests[] = {
+#define DECLARE_TEST(nr) \
+ { \
+ .actions = actions ## nr, \
+ .nr_actions = ARRAY_SIZE(actions ## nr), \
+ .result = results ## nr, \
+ .nr_results = ARRAY_SIZE(results ## nr), \
+ }
+
+ DECLARE_TEST(0),
+ DECLARE_TEST(1),
+ DECLARE_TEST(2),
+ DECLARE_TEST(3),
+
+#undef DECLARE_TEST
+};
+
+static int print_range(unsigned long s, unsigned long e, void *data)
+{
+ printf("[%ld, %ld]\n", s, e);
+
+ return 0;
+}
+
+static int count_ranges(unsigned long s, unsigned long e, void *data)
+{
+ unsigned int *nr = data;
+
+ ++*nr;
+ return 0;
+}
+
+const struct range *expected;
+static int check_ranges(unsigned long s, unsigned long e, void *data)
+{
+ unsigned int *nr = data;
+ int rc = 0;
+
+ if ( s != expected[*nr].start || e != expected[*nr].end )
+ rc = -EINVAL;
+
+ ++*nr;
+ return rc;
+}
+
+static void print_both(struct rangeset *r, const struct range *expected,
+ unsigned int nr_expected)
+{
+ unsigned int i;
+
+ printf("Result:\n");
+ rangeset_report_ranges(r, 0, ~0UL, print_range, NULL);
+ printf("Expected:\n");
+ for ( i = 0; i < nr_expected; i++ )
+ printf("[%ld, %ld]\n", expected[i].start, expected[i].end);
+}
+
+int main(int argc, char **argv)
+{
+ struct rangeset *r = rangeset_new(NULL, NULL, 0);
+ unsigned int i;
+ int ret_code = 0;
+
+ ASSERT(r);
+
+ for ( i = 0 ; i < ARRAY_SIZE(tests); i++ )
+ {
+ unsigned int j, nr = 0;
+ int rc = 0;
+
+ rangeset_purge(r);
+ for ( j = 0; j < tests[i].nr_actions; j++ )
+ {
+ const struct action *a = &tests[i].actions[j];
+
+ switch ( a->action )
+ {
+ case ADD:
+ rc = rangeset_add_range(r, a->r.start, a->r.end);
+ break;
+
+ case REMOVE:
+ rc = rangeset_remove_range(r, a->r.start, a->r.end);
+ break;
+ }
+
+ if ( rc )
+ {
+ printf("Test %u failed to %s range [%ld, %ld]\n",
+ i, a->action == ADD ? "add" : "remove",
+ a->r.start, a->r.end);
+ rangeset_report_ranges(r, 0, ~0UL, print_range, NULL);
+ break;
+ }
+ }
+
+ if ( rc )
+ {
+ /* Action failed, skip this test and set exit code to failure. */
+ ret_code = EXIT_FAILURE;
+ continue;
+ }
+
+ rc = rangeset_report_ranges(r, 0, ~0UL, count_ranges, &nr);
+ if ( rc )
+ {
+ printf("Test %u unable to count number of result ranges\n", i);
+ rangeset_report_ranges(r, 0, ~0UL, print_range, NULL);
+ ret_code = EXIT_FAILURE;
+ continue;
+ }
+ if ( nr != tests[i].nr_results )
+ {
+ printf("Test %u unexpected number of result ranges, expected: %u
got: %u\n",
+ i, tests[i].nr_results, nr);
+ print_both(r, tests[i].result, tests[i].nr_results);
+ ret_code = EXIT_FAILURE;
+ continue;
+ }
+
+ nr = 0;
+ expected = tests[i].result;
+ rc = rangeset_report_ranges(r, 0, ~0UL, check_ranges, &nr);
+ if ( rc )
+ {
+ printf("Test %u range checking failed\n", i);
+ print_both(r, tests[i].result, tests[i].nr_results);
+ ret_code = EXIT_FAILURE;
+ continue;
+ }
+ }
+
+ return 0;
+}
+
+/*
+ * Local variables:
+ * mode: C
+ * c-file-style: "BSD"
+ * c-basic-offset: 4
+ * indent-tabs-mode: nil
+ * End:
+ */
--
2.48.1
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |