[PATCH 0/2] xen/rangeset: one bugfix and unit testing

[PATCH 0/2] xen/rangeset: one bugfix and unit testing

[Roger Pau Monne]

Hello,

Rangesets are extensively used inside of Xen, yet we had no
unit tests to ensure it's correctness.  rangeset_remove_range() is in
fact bogus and will generate an incorrect output rangeset depending on
the inputs.

Patch 1 fixes the bug, patch 2 adds some basic unit testing to ensure
the fix done by patch 1 is correct.  The unit testing should likely be
expanded (in a different series) to further assert the correctness of
other rangeset operations.

Thanks, Roger.

Roger Pau Monne (2):
  xen/rangeset: fix incorrect subtraction
  tootls/tests: introduce unit tests for rangesets

 tools/tests/Makefile                 |   1 +
 tools/tests/rangeset/Makefile        |  45 ++++++
 tools/tests/rangeset/harness.h       |  71 +++++++++
 tools/tests/rangeset/test-rangeset.c | 228 +++++++++++++++++++++++++++
 xen/common/rangeset.c                |   3 +-
 5 files changed, 347 insertions(+), 1 deletion(-)
 create mode 100644 tools/tests/rangeset/Makefile
 create mode 100644 tools/tests/rangeset/harness.h
 create mode 100644 tools/tests/rangeset/test-rangeset.c

-- 
2.48.1

[PATCH 1/2] xen/rangeset: fix incorrect subtraction

[Roger Pau Monne]

Given the following rangset operation:

{ [0, 1], [4, 5] } - { [3, 4] }

The current rangeset logic will output a rangeset:

{ [0, 2], [5, 5] }

This is incorrect, and also has the undesirable property of being bogus in
a way that the resulting rangeset is expanded.

Fix this by making sure the bounds are correctly checked before modifying
the previous range.

Fixes: 484a058c4828 ('Add auto-destructing per-domain rangeset data structure...')
Signed-off-by: Roger Pau Monné <roger.pau@citrix.com>
---
 xen/common/rangeset.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/xen/common/rangeset.c b/xen/common/rangeset.c
index b75590f90744..e75871039087 100644
--- a/xen/common/rangeset.c
+++ b/xen/common/rangeset.c
@@ -227,7 +227,8 @@ int rangeset_remove_range(
 
         if ( x->s < s )
         {
-            x->e = s - 1;
+            if ( x->e >= s )
+                x->e = s - 1;
             x = next_range(r, x);
         }
 
-- 
2.48.1

[PATCH 2/2] tootls/tests: introduce unit tests for rangesets

[Roger Pau Monne]

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@citrix.com>
---
 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

Re: [PATCH 1/2] xen/rangeset: fix incorrect subtraction

[Jan Beulich]

On 11.04.2025 09:55, Roger Pau Monne wrote:
> Given the following rangset operation:
> 
> { [0, 1], [4, 5] } - { [3, 4] }
> 
> The current rangeset logic will output a rangeset:
> 
> { [0, 2], [5, 5] }
> 
> This is incorrect, and also has the undesirable property of being bogus in
> a way that the resulting rangeset is expanded.
> 
> Fix this by making sure the bounds are correctly checked before modifying
> the previous range.
> 
> Fixes: 484a058c4828 ('Add auto-destructing per-domain rangeset data structure...')
> Signed-off-by: Roger Pau Monné <roger.pau@citrix.com>

Reviewed-by: Jan Beulich <jbeulich@suse.com>

Re: [PATCH 2/2] tootls/tests: introduce unit tests for rangesets

[Jan Beulich]

On 11.04.2025 09:55, Roger Pau Monne wrote:
> 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@citrix.com>

It's okay as is, so:
Reviewed-by: Jan Beulich <jbeulich@suse.com>
Nevertheless a couple of remarks.

> --- /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)

The mix of padding ahead of the += is a little odd here.

> --- /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;

Are spinlocks really required for the rangeset code?

> --- /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?

Jan

Re: [PATCH 2/2] tootls/tests: introduce unit tests for rangesets

[Roger Pau Monné]

On Fri, Apr 11, 2025 at 10:21:08AM +0200, Jan Beulich wrote:
> On 11.04.2025 09:55, Roger Pau Monne wrote:
> > --- /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;
> 
> Are spinlocks really required for the rangeset code?

It's noted a bit below in this same file:

/* For rangeset_domain_{initialize,printk}() */

Otherwise rangeset.c won't build.

Will adjust the rest of your comments before commit, thanks!

Roger.