[PATCH 0/2] Adapt to glibc qsort() turned unstable
glibc reworked qsort() which now uses an unstable sorting algorithm. This is causing issues to our tests (see broken pipeline for rawhide). Green pipeline: https://gitlab.com/MichalPrivoznik/libvirt/-/pipelines/1081297468 Michal Prívozník (2): tests: Introduce virqsortmock nwfilterxml2firewalltest: Use virqsortmock for stable sorting tests/meson.build | 1 + tests/nwfilterxml2firewalltest.c | 4 ++- tests/virqsortmock.c | 58 ++++++++++++++++++++++++++++++++ 3 files changed, 62 insertions(+), 1 deletion(-) create mode 100644 tests/virqsortmock.c -- 2.41.0
While glibc provides qsort(), which usually is just a mergesort, until sorting arrays so huge that temporary array used by mergesort would not fit into physical memory (which in our case is never), we are not guaranteed it'll use mergesort. The advantage of mergesort is clear - it's stable. IOW, if we have an array of values parsed from XML, qsort() it and produce some output based on those values, we can then compare the output with some expected output, line by line. But with newer glibc this is all history. After [1], qsort() is no longer mergesort but introsort instead, which is not stable and thus unusable for our test suite. Provide an alternative implementation for qsort() and let it do bubblesort. We don't really have huge arrays to sort and thus O(n^2) time complexity is bearable. 1: https://sourceware.org/git/?p=glibc.git;a=commitdiff;h=03bf8357e8291857a435a... Signed-off-by: Michal Privoznik <mprivozn@redhat.com> --- tests/meson.build | 1 + tests/virqsortmock.c | 58 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 59 insertions(+) create mode 100644 tests/virqsortmock.c diff --git a/tests/meson.build b/tests/meson.build index e1cd57654a..d0167363eb 100644 --- a/tests/meson.build +++ b/tests/meson.build @@ -88,6 +88,7 @@ mock_libs = [ { 'name': 'virpcimock' }, { 'name': 'virportallocatormock' }, { 'name': 'virprocessmock' }, + { 'name': 'virqsortmock' }, { 'name': 'virrandommock' }, ] diff --git a/tests/virqsortmock.c b/tests/virqsortmock.c new file mode 100644 index 0000000000..c16197f908 --- /dev/null +++ b/tests/virqsortmock.c @@ -0,0 +1,58 @@ +/* + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library. If not, see + * <http://www.gnu.org/licenses/>. + */ + +#include <config.h> + +#include <stdlib.h> + +#define SWAP_WITH_SIZE(a, b, size) \ +do { \ + size_t __size = (size); \ + char *__a = (a); \ + char *__b = (b); \ + do { \ + char __tmp = *__a; \ + *__a++ = *__b; \ + *__b++ = __tmp; \ + } while (--__size > 0); \ +} while (0) + +void qsort(void *base, size_t nmemb, size_t size, + int (*compar)(const void *, const void *)) +{ + int xchg = 0; + + if (size < 2) + return; + + do { + size_t i = 0; + char *a = base; + char *b = base; + + xchg = 0; + + for (i = 0; i < nmemb - 1; i++) { + a = b; + b += size; + + if (compar(a, b) > 0) { + SWAP_WITH_SIZE(a, b, size); + xchg = 1; + } + } + } while (xchg); +} -- 2.41.0
The way that nwfilterxml2firewalltest works is: it loads a NWFilter XML from a file, parses it and then calls ebiptablesApplyNewRules() recording all commands that would be executed when instantiating the rule. This is then compared to expected output. But the very first thing that ebiptablesApplyNewRules() does, it calls qsort() to sort the rules. But with new glibc, qsort() is not stable anymore and thus the order in which two rules with equal priorities are applied is not guaranteed. Use qsort() from virqsortmock which produces stable results. Signed-off-by: Michal Privoznik <mprivozn@redhat.com> --- tests/nwfilterxml2firewalltest.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/tests/nwfilterxml2firewalltest.c b/tests/nwfilterxml2firewalltest.c index b78b1b7947..8dadc50054 100644 --- a/tests/nwfilterxml2firewalltest.c +++ b/tests/nwfilterxml2firewalltest.c @@ -461,7 +461,9 @@ mymain(void) return ret == 0 ? EXIT_SUCCESS : EXIT_FAILURE; } -VIR_TEST_MAIN_PRELOAD(mymain, VIR_TEST_MOCK("virfirewall")) +VIR_TEST_MAIN_PRELOAD(mymain, + VIR_TEST_MOCK("virqsort"), + VIR_TEST_MOCK("virfirewall")) #else /* ! defined (__linux__) */ -- 2.41.0
On Wed, Nov 22, 2023 at 11:49:55AM +0100, Michal Privoznik wrote:
The way that nwfilterxml2firewalltest works is: it loads a NWFilter XML from a file, parses it and then calls ebiptablesApplyNewRules() recording all commands that would be executed when instantiating the rule. This is then compared to expected output.
But the very first thing that ebiptablesApplyNewRules() does, it calls qsort() to sort the rules. But with new glibc, qsort() is not stable anymore and thus the order in which two rules with equal priorities are applied is not guaranteed.
Use qsort() from virqsortmock which produces stable results.
Aside from the test suite, I'm not too happy with the idea that our ordering of applying rules is non-deterministic :-( There is a well defined ordering for rules - the order in which the user/app listed them in the virNWFilterDef XML document. We have to override this for sorting by priority, but when priority matches, IMHO we should honour the XML rules ordering. I have no idea how hard that is to achieve though, as the place where we do the qsort() seems quite remote from the place where we know the XML doc ordering.
Signed-off-by: Michal Privoznik <mprivozn@redhat.com> --- tests/nwfilterxml2firewalltest.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-)
diff --git a/tests/nwfilterxml2firewalltest.c b/tests/nwfilterxml2firewalltest.c index b78b1b7947..8dadc50054 100644 --- a/tests/nwfilterxml2firewalltest.c +++ b/tests/nwfilterxml2firewalltest.c @@ -461,7 +461,9 @@ mymain(void) return ret == 0 ? EXIT_SUCCESS : EXIT_FAILURE; }
-VIR_TEST_MAIN_PRELOAD(mymain, VIR_TEST_MOCK("virfirewall")) +VIR_TEST_MAIN_PRELOAD(mymain, + VIR_TEST_MOCK("virqsort"), + VIR_TEST_MOCK("virfirewall"))
#else /* ! defined (__linux__) */
-- 2.41.0 _______________________________________________ Devel mailing list -- devel@lists.libvirt.org To unsubscribe send an email to devel-leave@lists.libvirt.org
With regards, Daniel -- |: https://berrange.com -o- https://www.flickr.com/photos/dberrange :| |: https://libvirt.org -o- https://fstop138.berrange.com :| |: https://entangle-photo.org -o- https://www.instagram.com/dberrange :|
On 11/22/23 12:11, Daniel P. Berrangé wrote:
On Wed, Nov 22, 2023 at 11:49:55AM +0100, Michal Privoznik wrote:
The way that nwfilterxml2firewalltest works is: it loads a NWFilter XML from a file, parses it and then calls ebiptablesApplyNewRules() recording all commands that would be executed when instantiating the rule. This is then compared to expected output.
But the very first thing that ebiptablesApplyNewRules() does, it calls qsort() to sort the rules. But with new glibc, qsort() is not stable anymore and thus the order in which two rules with equal priorities are applied is not guaranteed.
Use qsort() from virqsortmock which produces stable results.
Aside from the test suite, I'm not too happy with the idea that our ordering of applying rules is non-deterministic :-(
There is a well defined ordering for rules - the order in which the user/app listed them in the virNWFilterDef XML document.
We have to override this for sorting by priority, but when priority matches, IMHO we should honour the XML rules ordering. I have no idea how hard that is to achieve though, as the place where we do the qsort() seems quite remote from the place where we know the XML doc ordering.
Well, glib has g_qsort_with_data() which implements mergesort. We can switch to use that and if glib ever decides to use an unstable sorting algorithm, well, then we can implement something on our own. Let me see if I can cook up a patch. Michal
participants (3)
-
Daniel P. Berrangé -
Michal Privoznik -
Michal Prívozník