# [PATCH] test-mergesort: plug memory leaks in sort_stdin() 7 messages from 2026-10-07 to 2026-10-07. Participants: Muhammed Dilshad A, Patrick Steinhardt, Junio C Hamano. Thread: https://gitlist.dev/t/66479 ## Muhammed Dilshad A, 2026-10-07 03:42 Subject: [PATCH] test-mergesort: plug memory leaks in sort_stdin() Message-ID: <20261007034205.32619-1-dilsheddilu123@gmail.com> URL: https://gitlist.dev/e/20261007034205.32619-1-dilsheddilu123%40gmail.com ``` The sort_stdin() helper allocates an input buffer and a memory pool for the list of lines, but returns without releasing either. Discard the pool and release the strbuf after printing the sorted lines. Add a test for the sort subcommand to t0071. The existing test only exercises the test subcommand, leaving these leaks undetected by the regular leak-sanitized test suite. Signed-off-by: Muhammed Dilshad A --- t/helper/test-mergesort.c | 2 ++ t/t0071-sort.sh | 7 +++++++ 2 files changed, 9 insertions(+) diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c index 791e128793..3b8c428b14 100644 --- a/t/helper/test-mergesort.c +++ b/t/helper/test-mergesort.c @@ -61,6 +61,8 @@ static int sort_stdin(void) puts(lines->text); lines = lines->next; } + mem_pool_discard(&lines_pool, 0); + strbuf_release(&sb); return 0; } diff --git a/t/t0071-sort.sh b/t/t0071-sort.sh index 2236a7e956..97890da29f 100755 --- a/t/t0071-sort.sh +++ b/t/t0071-sort.sh @@ -8,4 +8,11 @@ test_expect_success 'DEFINE_LIST_SORT_DEBUG' ' test-tool mergesort test ' +test_expect_success 'sort stdin' ' + printf "%s\n" c a b >input && + printf "%s\n" a b c >expect && + test-tool mergesort sort actual && + test_cmp expect actual +' + test_done -- 2.55.0 ``` ## Patrick Steinhardt, 2026-10-07 06:13 Subject: Re: [PATCH] test-mergesort: plug memory leaks in sort_stdin() Message-ID: URL: https://gitlist.dev/e/asXi-1RlWhqPMWjL%40pks.im In-Reply-To: <20261007034205.32619-1-dilsheddilu123@gmail.com> ``` On Wed, Oct 07, 2026 at 09:12:05AM +0530, Muhammed Dilshad A wrote: > The sort_stdin() helper allocates an input buffer and a memory pool for > the list of lines, but returns without releasing either. Discard the > pool and release the strbuf after printing the sorted lines. Makes sense. > Add a test for the sort subcommand to t0071. The existing test only > exercises the test subcommand, leaving these leaks undetected by the > regular leak-sanitized test suite. I was briefly wondering whether we could get rid of t0071 altogether in favor of converting the tests into a unit test, and then drop the test helper. And that's certainly doable, and I'd argue it would also be the right thing to do. But unfortunately it wouldn't allow us to get rid of the test helper completely as the "mergesort sort" subcommand is used as part of our performance tests. I would claim that the benchmark itself is of dubious value. It was nice enough to have some numbers when we were working on the implementation of the mergesort, but carrying it with us nowadays feels like a bit of a waste as chances for regression are somewhat slim here. And if we ever wanted to iterate further on the merge sort implementation we could still introduce a new benchmark, that's easy enough to do. But anyway, that's of course a much bigger scope, and I'm fine to just fix the bugs for now. > diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c > index 791e128793..3b8c428b14 100644 > --- a/t/helper/test-mergesort.c > +++ b/t/helper/test-mergesort.c > @@ -61,6 +61,8 @@ static int sort_stdin(void) > puts(lines->text); > lines = lines->next; > } > + mem_pool_discard(&lines_pool, 0); > + strbuf_release(&sb); > return 0; > } The fix is obviously correct. > diff --git a/t/t0071-sort.sh b/t/t0071-sort.sh > index 2236a7e956..97890da29f 100755 > --- a/t/t0071-sort.sh > +++ b/t/t0071-sort.sh > @@ -8,4 +8,11 @@ test_expect_success 'DEFINE_LIST_SORT_DEBUG' ' > test-tool mergesort test > ' > > +test_expect_success 'sort stdin' ' > + printf "%s\n" c a b >input && > + printf "%s\n" a b c >expect && > + test-tool mergesort sort actual && > + test_cmp expect actual > +' And having a test makes sense, I guess. I noticed that there's another "generate" subcommand here that is entirely unused. Do we maybe want to also remove it while at it? The test suite passes with the below diff. Thanks! Patrick diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c index 791e128793..9200c4bb4a 100644 --- a/t/helper/test-mergesort.c +++ b/t/helper/test-mergesort.c @@ -114,16 +114,6 @@ static struct dist { DIST(shuffle), }; -static const struct dist *get_dist_by_name(const char *name) -{ - int i; - for (i = 0; i < ARRAY_SIZE(dist); i++) { - if (!strcmp(dist[i].name, name)) - return &dist[i]; - } - return NULL; -} - static void mode_copy(int *arr UNUSED, int n UNUSED) { /* nothing */ @@ -237,41 +227,6 @@ static struct mode { MODE(unriffle_skewed), }; -static const struct mode *get_mode_by_name(const char *name) -{ - int i; - for (i = 0; i < ARRAY_SIZE(mode); i++) { - if (!strcmp(mode[i].name, name)) - return &mode[i]; - } - return NULL; -} - -static int generate(int argc, const char **argv) -{ - const struct dist *dist = NULL; - const struct mode *mode = NULL; - int i, n, m, *arr; - - if (argc != 4) - return 1; - - dist = get_dist_by_name(argv[0]); - mode = get_mode_by_name(argv[1]); - n = strtol(argv[2], NULL, 10); - m = strtol(argv[3], NULL, 10); - if (!dist || !mode) - return 1; - - ALLOC_ARRAY(arr, n); - dist->fn(arr, n, m); - mode->fn(arr, n); - for (i = 0; i < n; i++) - printf("%08x\n", arr[i]); - free(arr); - return 0; -} - static struct stats { int get_next, set_next, compare; } stats; @@ -388,14 +343,11 @@ int cmd__mergesort(int argc, const char **argv) int i; const char *sep; - if (argc == 6 && !strcmp(argv[1], "generate")) - return generate(argc - 2, argv + 2); if (argc == 2 && !strcmp(argv[1], "sort")) return sort_stdin(); if (argc > 1 && !strcmp(argv[1], "test")) return run_tests(argc - 2, argv + 2); - fprintf(stderr, "usage: test-tool mergesort generate \n"); - fprintf(stderr, " or: test-tool mergesort sort\n"); + fprintf(stderr, "usage: test-tool mergesort sort\n"); fprintf(stderr, " or: test-tool mergesort test [...]\n"); fprintf(stderr, "\n"); for (i = 0, sep = "distributions: "; i < ARRAY_SIZE(dist); i++, sep = ", ") ``` ## Muhammed Dilshad A, 2026-10-07 13:50 Subject: [PATCH v2 0/3] mergesort: move tests to Clar and retire the helper Message-ID: URL: https://gitlist.dev/e/cover.1791365181.git.dilsheddilu123%40gmail.com In-Reply-To: <20261007034205.32619-1-dilsheddilu123@gmail.com> ``` Hi Patrick, Thanks for the review. I followed up on the larger cleanup you mentioned. The sorting tests now run in Clar, and I have removed the old benchmark and its helper. This also removes the unused generate subcommand. The new suite keeps all 1,680 cases from the old certification test and adds checks for empty and small lists using both sort macros. It checks sorting order, stability and list length. Cleanup frees the backing arrays directly, so a failed assertion does not need to walk list links. Changes since v1: * Patch 1 is unchanged. * Patch 2 moves the tests to Clar and removes the unused generate and test commands. The sort command remains available for the benchmark. * Patch 3 removes p0071 and the remaining sort helper, along with their build and command registrations. I kept the leak fix first so it can still be applied on its own if you would prefer to keep the broader cleanup for a separate series. The Make and Meson unit tests pass, and the mergesort unit suite also passes with LeakSanitizer enabled. The production sorting implementation is unchanged. Muhammed Dilshad A (3): test-mergesort: plug memory leaks in sort_stdin() mergesort: move sorting tests to the unit-test framework t: retire the sorting benchmark and mergesort helper Makefile | 2 +- t/helper/meson.build | 1 - t/helper/test-mergesort.c | 408 ------------------------------------- t/helper/test-tool.c | 1 - t/helper/test-tool.h | 1 - t/meson.build | 3 +- t/perf/p0071-sort.sh | 52 ----- t/t0071-sort.sh | 11 - t/unit-tests/u-mergesort.c | 369 +++++++++++++++++++++++++++++++++ 9 files changed, 371 insertions(+), 477 deletions(-) delete mode 100644 t/helper/test-mergesort.c delete mode 100755 t/perf/p0071-sort.sh delete mode 100755 t/t0071-sort.sh create mode 100644 t/unit-tests/u-mergesort.c base-commit: 6de20f6092dcf9bdb1c8efe03db4b70c82b423dd -- 2.55.0 ``` ## Muhammed Dilshad A, 2026-10-07 13:50 Subject: [PATCH v2 1/3] test-mergesort: plug memory leaks in sort_stdin() Message-ID: <2a91f29982cf18ef6ee6770c671b33e042acd308.1791365181.git.dilsheddilu123@gmail.com> URL: https://gitlist.dev/e/2a91f29982cf18ef6ee6770c671b33e042acd308.1791365181.git.dilsheddilu123%40gmail.com In-Reply-To: ``` The sort_stdin() helper allocates an input buffer and a memory pool for the list of lines, but returns without releasing either. Discard the pool and release the strbuf after printing the sorted lines. Add a test for the sort subcommand to t0071. The existing test only exercises the test subcommand, leaving these leaks undetected by the regular leak-sanitized test suite. Signed-off-by: Muhammed Dilshad A --- t/helper/test-mergesort.c | 2 ++ t/t0071-sort.sh | 7 +++++++ 2 files changed, 9 insertions(+) diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c index 791e128793..3b8c428b14 100644 --- a/t/helper/test-mergesort.c +++ b/t/helper/test-mergesort.c @@ -61,6 +61,8 @@ static int sort_stdin(void) puts(lines->text); lines = lines->next; } + mem_pool_discard(&lines_pool, 0); + strbuf_release(&sb); return 0; } diff --git a/t/t0071-sort.sh b/t/t0071-sort.sh index 2236a7e956..97890da29f 100755 --- a/t/t0071-sort.sh +++ b/t/t0071-sort.sh @@ -8,4 +8,11 @@ test_expect_success 'DEFINE_LIST_SORT_DEBUG' ' test-tool mergesort test ' +test_expect_success 'sort stdin' ' + printf "%s\n" c a b >input && + printf "%s\n" a b c >expect && + test-tool mergesort sort actual && + test_cmp expect actual +' + test_done -- 2.55.0 ``` ## Muhammed Dilshad A, 2026-10-07 13:50 Subject: [PATCH v2 2/3] mergesort: move sorting tests to the unit-test framework Message-ID: <0429552774367ddcc3c2fda78e09a83650ccfa02.1791365181.git.dilsheddilu123@gmail.com> URL: https://gitlist.dev/e/0429552774367ddcc3c2fda78e09a83650ccfa02.1791365181.git.dilsheddilu123%40gmail.com In-Reply-To: ``` The mergesort certification checks exercise C code directly, so they do not need a shell test and test-tool command. Move their distributions and transformations to Clar, retaining the sorted-value, stability and list length checks. Add small cases for both list sort macros and debug hooks. Keep node storage available to the cleanup fixture and bound validation so a failed assertion can release it without walking a broken list. Remove the unused generate command along with the old test command, leaving sort available for the sorting benchmark. Suggested-by: Patrick Steinhardt Signed-off-by: Muhammed Dilshad A --- Makefile | 1 + t/helper/test-mergesort.c | 345 +--------------------------------- t/meson.build | 2 +- t/t0071-sort.sh | 18 -- t/unit-tests/u-mergesort.c | 369 +++++++++++++++++++++++++++++++++++++ 5 files changed, 372 insertions(+), 363 deletions(-) delete mode 100755 t/t0071-sort.sh create mode 100644 t/unit-tests/u-mergesort.c diff --git a/Makefile b/Makefile index a96be506b5..cac535ba19 100644 --- a/Makefile +++ b/Makefile @@ -1541,6 +1541,7 @@ CLAR_TEST_SUITES += u-hash CLAR_TEST_SUITES += u-hashmap CLAR_TEST_SUITES += u-list-objects-filter-options CLAR_TEST_SUITES += u-mem-pool +CLAR_TEST_SUITES += u-mergesort CLAR_TEST_SUITES += u-odb-inmemory CLAR_TEST_SUITES += u-oid-array CLAR_TEST_SUITES += u-oidmap diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c index 3b8c428b14..e8b8de239b 100644 --- a/t/helper/test-mergesort.c +++ b/t/helper/test-mergesort.c @@ -1,16 +1,8 @@ -#define DISABLE_SIGN_COMPARE_WARNINGS - #include "test-tool.h" #include "mem-pool.h" #include "mergesort.h" #include "strbuf.h" -static uint32_t minstd_rand(uint32_t *state) -{ - *state = (uint64_t)*state * 48271 % 2147483647; - return *state; -} - struct line { char *text; struct line *next; @@ -66,345 +58,10 @@ static int sort_stdin(void) return 0; } -static void dist_sawtooth(int *arr, int n, int m) -{ - int i; - for (i = 0; i < n; i++) - arr[i] = i % m; -} - -static void dist_rand(int *arr, int n, int m) -{ - int i; - uint32_t seed = 1; - for (i = 0; i < n; i++) - arr[i] = minstd_rand(&seed) % m; -} - -static void dist_stagger(int *arr, int n, int m) -{ - int i; - for (i = 0; i < n; i++) - arr[i] = (i * m + i) % n; -} - -static void dist_plateau(int *arr, int n, int m) -{ - int i; - for (i = 0; i < n; i++) - arr[i] = (i < m) ? i : m; -} - -static void dist_shuffle(int *arr, int n, int m) -{ - int i, j, k; - uint32_t seed = 1; - for (i = j = 0, k = 1; i < n; i++) - arr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2); -} - -#define DIST(name) { #name, dist_##name } - -static struct dist { - const char *name; - void (*fn)(int *arr, int n, int m); -} dist[] = { - DIST(sawtooth), - DIST(rand), - DIST(stagger), - DIST(plateau), - DIST(shuffle), -}; - -static const struct dist *get_dist_by_name(const char *name) -{ - int i; - for (i = 0; i < ARRAY_SIZE(dist); i++) { - if (!strcmp(dist[i].name, name)) - return &dist[i]; - } - return NULL; -} - -static void mode_copy(int *arr UNUSED, int n UNUSED) -{ - /* nothing */ -} - -static void mode_reverse(int *arr, int n) -{ - int i, j; - for (i = 0, j = n - 1; i < j; i++, j--) - SWAP(arr[i], arr[j]); -} - -static void mode_reverse_1st_half(int *arr, int n) -{ - mode_reverse(arr, n / 2); -} - -static void mode_reverse_2nd_half(int *arr, int n) -{ - int half = n / 2; - mode_reverse(arr + half, n - half); -} - -static int compare_ints(const void *av, const void *bv) -{ - const int *ap = av, *bp = bv; - int a = *ap, b = *bp; - return (a > b) - (a < b); -} - -static void mode_sort(int *arr, int n) -{ - QSORT(arr, n, compare_ints); -} - -static void mode_dither(int *arr, int n) -{ - int i; - for (i = 0; i < n; i++) - arr[i] += i % 5; -} - -static void unriffle(int *arr, int n, int *tmp) -{ - int i, j; - COPY_ARRAY(tmp, arr, n); - for (i = j = 0; i < n; i += 2) - arr[j++] = tmp[i]; - for (i = 1; i < n; i += 2) - arr[j++] = tmp[i]; -} - -static void unriffle_recursively(int *arr, int n, int *tmp) -{ - if (n > 1) { - int half = n / 2; - unriffle(arr, n, tmp); - unriffle_recursively(arr, half, tmp); - unriffle_recursively(arr + half, n - half, tmp); - } -} - -static void mode_unriffle(int *arr, int n) -{ - int *tmp; - ALLOC_ARRAY(tmp, n); - unriffle_recursively(arr, n, tmp); - free(tmp); -} - -static unsigned int prev_pow2(unsigned int n) -{ - unsigned int pow2 = 1; - while (pow2 * 2 < n) - pow2 *= 2; - return pow2; -} - -static void unriffle_recursively_skewed(int *arr, int n, int *tmp) -{ - if (n > 1) { - int pow2 = prev_pow2(n); - int rest = n - pow2; - unriffle(arr + pow2 - rest, rest * 2, tmp); - unriffle_recursively_skewed(arr, pow2, tmp); - unriffle_recursively_skewed(arr + pow2, rest, tmp); - } -} - -static void mode_unriffle_skewed(int *arr, int n) -{ - int *tmp; - ALLOC_ARRAY(tmp, n); - unriffle_recursively_skewed(arr, n, tmp); - free(tmp); -} - -#define MODE(name) { #name, mode_##name } - -static struct mode { - const char *name; - void (*fn)(int *arr, int n); -} mode[] = { - MODE(copy), - MODE(reverse), - MODE(reverse_1st_half), - MODE(reverse_2nd_half), - MODE(sort), - MODE(dither), - MODE(unriffle), - MODE(unriffle_skewed), -}; - -static const struct mode *get_mode_by_name(const char *name) -{ - int i; - for (i = 0; i < ARRAY_SIZE(mode); i++) { - if (!strcmp(mode[i].name, name)) - return &mode[i]; - } - return NULL; -} - -static int generate(int argc, const char **argv) -{ - const struct dist *dist = NULL; - const struct mode *mode = NULL; - int i, n, m, *arr; - - if (argc != 4) - return 1; - - dist = get_dist_by_name(argv[0]); - mode = get_mode_by_name(argv[1]); - n = strtol(argv[2], NULL, 10); - m = strtol(argv[3], NULL, 10); - if (!dist || !mode) - return 1; - - ALLOC_ARRAY(arr, n); - dist->fn(arr, n, m); - mode->fn(arr, n); - for (i = 0; i < n; i++) - printf("%08x\n", arr[i]); - free(arr); - return 0; -} - -static struct stats { - int get_next, set_next, compare; -} stats; - -struct number { - int value, rank; - struct number *next; -}; - -DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next, - stats.get_next++, stats.set_next++); - -static int compare_numbers(const struct number *an, const struct number *bn) -{ - int a = an->value, b = bn->value; - stats.compare++; - return (a > b) - (a < b); -} - -static void clear_numbers(struct number *list) -{ - while (list) { - struct number *next = list->next; - free(list); - list = next; - } -} - -static int test(const struct dist *dist, const struct mode *mode, int n, int m) -{ - int *arr; - size_t i; - struct number *curr, *list, **tail; - int is_sorted = 1; - int is_stable = 1; - const char *verdict; - int result = -1; - - ALLOC_ARRAY(arr, n); - dist->fn(arr, n, m); - mode->fn(arr, n); - for (i = 0, tail = &list; i < n; i++) { - curr = xmalloc(sizeof(*curr)); - curr->value = arr[i]; - curr->rank = i; - *tail = curr; - tail = &curr->next; - } - *tail = NULL; - - stats.get_next = stats.set_next = stats.compare = 0; - sort_numbers(&list, compare_numbers); - - QSORT(arr, n, compare_ints); - for (i = 0, curr = list; i < n && curr; i++, curr = curr->next) { - if (arr[i] != curr->value) - is_sorted = 0; - if (curr->next && curr->value == curr->next->value && - curr->rank >= curr->next->rank) - is_stable = 0; - } - if (i < n) { - verdict = "too short"; - } else if (curr) { - verdict = "too long"; - } else if (!is_sorted) { - verdict = "not sorted"; - } else if (!is_stable) { - verdict = "unstable"; - } else { - verdict = "OK"; - result = 0; - } - - printf("%-9s %-16s %8d %8d %8d %8d %8d %s\n", - dist->name, mode->name, n, m, stats.get_next, stats.set_next, - stats.compare, verdict); - - clear_numbers(list); - free(arr); - - return result; -} - -/* - * A version of the qsort certification program from "Engineering a Sort - * Function" by Bentley and McIlroy, Software—Practice and Experience, - * Volume 23, Issue 11, 1249–1265 (November 1993). - */ -static int run_tests(int argc, const char **argv) -{ - const char *argv_default[] = { "100", "1023", "1024", "1025" }; - if (!argc) - return run_tests(ARRAY_SIZE(argv_default), argv_default); - printf("%-9s %-16s %8s %8s %8s %8s %8s %s\n", - "distribut", "mode", "n", "m", "get_next", "set_next", - "compare", "verdict"); - while (argc--) { - int i, j, m, n = strtol(*argv++, NULL, 10); - for (i = 0; i < ARRAY_SIZE(dist); i++) { - for (j = 0; j < ARRAY_SIZE(mode); j++) { - for (m = 1; m < 2 * n; m *= 2) { - if (test(&dist[i], &mode[j], n, m)) - return 1; - } - } - } - } - return 0; -} - int cmd__mergesort(int argc, const char **argv) { - int i; - const char *sep; - - if (argc == 6 && !strcmp(argv[1], "generate")) - return generate(argc - 2, argv + 2); if (argc == 2 && !strcmp(argv[1], "sort")) return sort_stdin(); - if (argc > 1 && !strcmp(argv[1], "test")) - return run_tests(argc - 2, argv + 2); - fprintf(stderr, "usage: test-tool mergesort generate \n"); - fprintf(stderr, " or: test-tool mergesort sort\n"); - fprintf(stderr, " or: test-tool mergesort test [...]\n"); - fprintf(stderr, "\n"); - for (i = 0, sep = "distributions: "; i < ARRAY_SIZE(dist); i++, sep = ", ") - fprintf(stderr, "%s%s", sep, dist[i].name); - fprintf(stderr, "\n"); - for (i = 0, sep = "modes: "; i < ARRAY_SIZE(mode); i++, sep = ", ") - fprintf(stderr, "%s%s", sep, mode[i].name); - fprintf(stderr, "\n"); + fprintf(stderr, "usage: test-tool mergesort sort\n"); return 129; } diff --git a/t/meson.build b/t/meson.build index f65eb04684..2752321e0d 100644 --- a/t/meson.build +++ b/t/meson.build @@ -6,6 +6,7 @@ clar_test_suites = [ 'unit-tests/u-hashmap.c', 'unit-tests/u-list-objects-filter-options.c', 'unit-tests/u-mem-pool.c', + 'unit-tests/u-mergesort.c', 'unit-tests/u-odb-inmemory.c', 'unit-tests/u-oid-array.c', 'unit-tests/u-oidmap.c', @@ -119,7 +120,6 @@ integration_tests = [ 't0067-parse_pathspec_file.sh', 't0068-for-each-repo.sh', 't0070-fundamental.sh', - 't0071-sort.sh', 't0080-unit-test-output.sh', 't0081-find-pack.sh', 't0090-cache-tree.sh', diff --git a/t/t0071-sort.sh b/t/t0071-sort.sh deleted file mode 100755 index 97890da29f..0000000000 --- a/t/t0071-sort.sh +++ /dev/null @@ -1,18 +0,0 @@ -#!/bin/sh - -test_description='verify sort functions' - -. ./test-lib.sh - -test_expect_success 'DEFINE_LIST_SORT_DEBUG' ' - test-tool mergesort test -' - -test_expect_success 'sort stdin' ' - printf "%s\n" c a b >input && - printf "%s\n" a b c >expect && - test-tool mergesort sort actual && - test_cmp expect actual -' - -test_done diff --git a/t/unit-tests/u-mergesort.c b/t/unit-tests/u-mergesort.c new file mode 100644 index 0000000000..e621c9ec21 --- /dev/null +++ b/t/unit-tests/u-mergesort.c @@ -0,0 +1,369 @@ +#include "unit-test.h" +#include "mergesort.h" + +static uint32_t minstd_rand(uint32_t *state) +{ + *state = (uint64_t)*state * 48271 % 2147483647; + return *state; +} + +static void dist_sawtooth(int *arr, int n, int m) +{ + int i; + for (i = 0; i < n; i++) + arr[i] = i % m; +} + +static void dist_rand(int *arr, int n, int m) +{ + int i; + uint32_t seed = 1; + for (i = 0; i < n; i++) + arr[i] = minstd_rand(&seed) % m; +} + +static void dist_stagger(int *arr, int n, int m) +{ + int i; + for (i = 0; i < n; i++) + arr[i] = (i * m + i) % n; +} + +static void dist_plateau(int *arr, int n, int m) +{ + int i; + for (i = 0; i < n; i++) + arr[i] = (i < m) ? i : m; +} + +static void dist_shuffle(int *arr, int n, int m) +{ + int i, j, k; + uint32_t seed = 1; + for (i = j = 0, k = 1; i < n; i++) + arr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2); +} + +#define DIST(name) { #name, dist_##name } + +static struct dist { + const char *name; + void (*fn)(int *arr, int n, int m); +} dist[] = { + DIST(sawtooth), + DIST(rand), + DIST(stagger), + DIST(plateau), + DIST(shuffle), +}; + +static void mode_copy(int *arr UNUSED, int n UNUSED) +{ + /* nothing */ +} + +static void mode_reverse(int *arr, int n) +{ + int i, j; + for (i = 0, j = n - 1; i < j; i++, j--) + SWAP(arr[i], arr[j]); +} + +static void mode_reverse_1st_half(int *arr, int n) +{ + mode_reverse(arr, n / 2); +} + +static void mode_reverse_2nd_half(int *arr, int n) +{ + int half = n / 2; + mode_reverse(arr + half, n - half); +} + +static int compare_ints(const void *av, const void *bv) +{ + const int *ap = av, *bp = bv; + int a = *ap, b = *bp; + return (a > b) - (a < b); +} + +static void mode_sort(int *arr, int n) +{ + QSORT(arr, n, compare_ints); +} + +static void mode_dither(int *arr, int n) +{ + int i; + for (i = 0; i < n; i++) + arr[i] += i % 5; +} + +static void unriffle(int *arr, int n, int *tmp) +{ + int i, j; + COPY_ARRAY(tmp, arr, n); + for (i = j = 0; i < n; i += 2) + arr[j++] = tmp[i]; + for (i = 1; i < n; i += 2) + arr[j++] = tmp[i]; +} + +static void unriffle_recursively(int *arr, int n, int *tmp) +{ + if (n > 1) { + int half = n / 2; + unriffle(arr, n, tmp); + unriffle_recursively(arr, half, tmp); + unriffle_recursively(arr + half, n - half, tmp); + } +} + +static void mode_unriffle(int *arr, int n) +{ + int *tmp; + ALLOC_ARRAY(tmp, n); + unriffle_recursively(arr, n, tmp); + free(tmp); +} + +static unsigned int prev_pow2(unsigned int n) +{ + unsigned int pow2 = 1; + while (pow2 * 2 < n) + pow2 *= 2; + return pow2; +} + +static void unriffle_recursively_skewed(int *arr, int n, int *tmp) +{ + if (n > 1) { + int pow2 = prev_pow2(n); + int rest = n - pow2; + unriffle(arr + pow2 - rest, rest * 2, tmp); + unriffle_recursively_skewed(arr, pow2, tmp); + unriffle_recursively_skewed(arr + pow2, rest, tmp); + } +} + +static void mode_unriffle_skewed(int *arr, int n) +{ + int *tmp; + ALLOC_ARRAY(tmp, n); + unriffle_recursively_skewed(arr, n, tmp); + free(tmp); +} + +#define MODE(name) { #name, mode_##name } + +static struct mode { + const char *name; + void (*fn)(int *arr, int n); +} mode[] = { + MODE(copy), + MODE(reverse), + MODE(reverse_1st_half), + MODE(reverse_2nd_half), + MODE(sort), + MODE(dither), + MODE(unriffle), + MODE(unriffle_skewed), +}; + +static struct stats { + int get_next, set_next; +} stats; + +struct number { + int value, rank; + struct number *next; +}; + +DEFINE_LIST_SORT_DEBUG(static, sort_numbers_debug, struct number, next, + stats.get_next++, stats.set_next++); +DEFINE_LIST_SORT(static, sort_numbers, struct number, next); + +static int compare_numbers(const struct number *an, const struct number *bn) +{ + int a = an->value, b = bn->value; + return (a > b) - (a < b); +} + +/* Free the storage directly, even if an assertion fails on a broken list. */ +static int *values; +static struct number *numbers; + +void test_mergesort__cleanup(void) +{ + FREE_AND_NULL(values); + FREE_AND_NULL(numbers); +} + +static struct number *prepare_list(const int *arr, int n) +{ + int i; + + ALLOC_ARRAY(numbers, n); + for (i = 0; i < n; i++) { + numbers[i].value = arr[i]; + numbers[i].rank = i; + numbers[i].next = i + 1 < n ? &numbers[i + 1] : NULL; + } + stats.get_next = stats.set_next = 0; + return n ? numbers : NULL; +} + +static void check_list(struct number *list, const int *expected, + const int *ranks, int n, const char *context) +{ + struct number *previous = NULL; + int i; + + /* Bound traversal so a cycle is reported as an overlong list. */ + for (i = 0; i < n; i++) { + cl_assert_(list, context); + cl_assert_equal_i_(list->value, expected[i], "%s: index %d", + context, i); + if (previous && previous->value == list->value) + cl_assert_lt_i_(previous->rank, list->rank, + "%s: stability at index %d", context, i); + if (ranks) + cl_assert_equal_i_(list->rank, ranks[i], + "%s: rank at index %d", context, i); + previous = list; + list = list->next; + } + cl_assert_(list == NULL, context); +} + +/* + * A version of the qsort certification program from "Engineering a Sort + * Function" by Bentley and McIlroy, Software—Practice and Experience, + * Volume 23, Issue 11, 1249–1265 (November 1993). + */ +static void certify(const struct dist *distribution) +{ + static const int sizes[] = { 100, 1023, 1024, 1025 }; + size_t i, j; + int m; + + for (i = 0; i < ARRAY_SIZE(sizes); i++) { + int n = sizes[i]; + + for (j = 0; j < ARRAY_SIZE(mode); j++) { + for (m = 1; m < 2 * n; m *= 2) { + struct number *list; + char context[128]; + + xsnprintf(context, sizeof(context), + "%s %s n=%d m=%d", + distribution->name, mode[j].name, n, m); + ALLOC_ARRAY(values, n); + distribution->fn(values, n, m); + mode[j].fn(values, n); + list = prepare_list(values, n); + sort_numbers_debug(&list, compare_numbers); + QSORT(values, n, compare_ints); + check_list(list, values, NULL, n, context); + test_mergesort__cleanup(); + } + } + } +} + +void test_mergesort__sawtooth(void) +{ + certify(&dist[0]); +} + +void test_mergesort__rand(void) +{ + certify(&dist[1]); +} + +void test_mergesort__stagger(void) +{ + certify(&dist[2]); +} + +void test_mergesort__plateau(void) +{ + certify(&dist[3]); +} + +void test_mergesort__shuffle(void) +{ + certify(&dist[4]); +} + +static void check_small(const int *input, const int *expected, + const int *ranks, int n, const char *name) +{ + int debug; + + for (debug = 0; debug < 2; debug++) { + struct number *list = prepare_list(input, n); + char context[128]; + + xsnprintf(context, sizeof(context), "%s %s n=%d", + debug ? "debug" : "normal", name, n); + if (debug) + sort_numbers_debug(&list, compare_numbers); + else + sort_numbers(&list, compare_numbers); + check_list(list, expected, ranks, n, context); + test_mergesort__cleanup(); + } +} + +void test_mergesort__empty(void) +{ + check_small(NULL, NULL, NULL, 0, "empty"); +} + +void test_mergesort__singleton(void) +{ + const int input[] = { 42 }; + const int ranks[] = { 0 }; + + check_small(input, input, ranks, ARRAY_SIZE(input), "singleton"); +} + +void test_mergesort__reversed_pair(void) +{ + const int input[] = { 2, 1 }; + const int expected[] = { 1, 2 }; + const int ranks[] = { 1, 0 }; + + check_small(input, expected, ranks, ARRAY_SIZE(input), "reversed pair"); +} + +void test_mergesort__equal_pair(void) +{ + const int input[] = { 1, 1 }; + const int ranks[] = { 0, 1 }; + + check_small(input, input, ranks, ARRAY_SIZE(input), "equal pair"); +} + +void test_mergesort__mixed_values(void) +{ + const int input[] = { INT_MAX, -1, 0, INT_MIN, -1, INT_MAX, 0 }; + const int expected[] = { INT_MIN, -1, -1, 0, 0, INT_MAX, INT_MAX }; + const int ranks[] = { 3, 1, 4, 2, 6, 0, 5 }; + + check_small(input, expected, ranks, ARRAY_SIZE(input), "mixed values"); +} + +void test_mergesort__debug_hooks(void) +{ + const int input[] = { 2, 1 }; + const int expected[] = { 1, 2 }; + const int ranks[] = { 1, 0 }; + struct number *list = prepare_list(input, ARRAY_SIZE(input)); + + sort_numbers_debug(&list, compare_numbers); + check_list(list, expected, ranks, ARRAY_SIZE(input), "debug hooks"); + cl_assert_gt_i(stats.get_next, 0); + cl_assert_gt_i(stats.set_next, 0); +} -- 2.55.0 ``` ## Muhammed Dilshad A, 2026-10-07 13:50 Subject: [PATCH v2 3/3] t: retire the sorting benchmark and mergesort helper Message-ID: URL: https://gitlist.dev/e/b540e3a3d2c30bccaaa0d8dca3428a77c1d2ea76.1791365181.git.dilsheddilu123%40gmail.com In-Reply-To: ``` p0071 compared sorting implementations during mergesort development. Retire it as suggested during the unit-test conversion. A new benchmark can be added if later optimization work needs performance measurements. The benchmark was the last caller of the sort-only mergesort helper. Removing it allows us to delete the helper and its build and command registrations as well. Suggested-by: Patrick Steinhardt Signed-off-by: Muhammed Dilshad A --- Makefile | 1 - t/helper/meson.build | 1 - t/helper/test-mergesort.c | 67 --------------------------------------- t/helper/test-tool.c | 1 - t/helper/test-tool.h | 1 - t/meson.build | 1 - t/perf/p0071-sort.sh | 52 ------------------------------ 7 files changed, 124 deletions(-) delete mode 100644 t/helper/test-mergesort.c delete mode 100755 t/perf/p0071-sort.sh diff --git a/Makefile b/Makefile index cac535ba19..4b35808b2e 100644 --- a/Makefile +++ b/Makefile @@ -835,7 +835,6 @@ TEST_BUILTINS_OBJS += test-hexdump.o TEST_BUILTINS_OBJS += test-json-writer.o TEST_BUILTINS_OBJS += test-lazy-init-name-hash.o TEST_BUILTINS_OBJS += test-match-trees.o -TEST_BUILTINS_OBJS += test-mergesort.o TEST_BUILTINS_OBJS += test-mktemp.o TEST_BUILTINS_OBJS += test-name-hash.o TEST_BUILTINS_OBJS += test-online-cpus.o diff --git a/t/helper/meson.build b/t/helper/meson.build index 3235f10ab8..e94e6f10fb 100644 --- a/t/helper/meson.build +++ b/t/helper/meson.build @@ -32,7 +32,6 @@ test_tool_sources = [ 'test-json-writer.c', 'test-lazy-init-name-hash.c', 'test-match-trees.c', - 'test-mergesort.c', 'test-mktemp.c', 'test-name-hash.c', 'test-online-cpus.c', diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c deleted file mode 100644 index e8b8de239b..0000000000 --- a/t/helper/test-mergesort.c +++ /dev/null @@ -1,67 +0,0 @@ -#include "test-tool.h" -#include "mem-pool.h" -#include "mergesort.h" -#include "strbuf.h" - -struct line { - char *text; - struct line *next; -}; - -DEFINE_LIST_SORT(static, sort_lines, struct line, next); - -static int compare_strings(const struct line *x, const struct line *y) -{ - return strcmp(x->text, y->text); -} - -static int sort_stdin(void) -{ - struct line *lines; - struct line **tail = &lines; - struct strbuf sb = STRBUF_INIT; - struct mem_pool lines_pool; - char *p; - - strbuf_read(&sb, 0, 0); - - /* - * Split by newline, but don't create an item - * for the empty string after the last separator. - */ - if (sb.len && sb.buf[sb.len - 1] == '\n') - strbuf_setlen(&sb, sb.len - 1); - - mem_pool_init(&lines_pool, 0); - p = sb.buf; - for (;;) { - char *eol = strchr(p, '\n'); - struct line *line = mem_pool_alloc(&lines_pool, sizeof(*line)); - line->text = p; - *tail = line; - tail = &line->next; - if (!eol) - break; - *eol = '\0'; - p = eol + 1; - } - *tail = NULL; - - sort_lines(&lines, compare_strings); - - while (lines) { - puts(lines->text); - lines = lines->next; - } - mem_pool_discard(&lines_pool, 0); - strbuf_release(&sb); - return 0; -} - -int cmd__mergesort(int argc, const char **argv) -{ - if (argc == 2 && !strcmp(argv[1], "sort")) - return sort_stdin(); - fprintf(stderr, "usage: test-tool mergesort sort\n"); - return 129; -} diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c index b71a22b43b..2e80dc7ab8 100644 --- a/t/helper/test-tool.c +++ b/t/helper/test-tool.c @@ -42,7 +42,6 @@ static struct test_cmd cmds[] = { { "json-writer", cmd__json_writer }, { "lazy-init-name-hash", cmd__lazy_init_name_hash }, { "match-trees", cmd__match_trees }, - { "mergesort", cmd__mergesort }, { "mktemp", cmd__mktemp }, { "name-hash", cmd__name_hash }, { "online-cpus", cmd__online_cpus }, diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h index f2885b33d5..9442c61ffd 100644 --- a/t/helper/test-tool.h +++ b/t/helper/test-tool.h @@ -35,7 +35,6 @@ int cmd__hexdump(int argc, const char **argv); int cmd__json_writer(int argc, const char **argv); int cmd__lazy_init_name_hash(int argc, const char **argv); int cmd__match_trees(int argc, const char **argv); -int cmd__mergesort(int argc, const char **argv); int cmd__mktemp(int argc, const char **argv); int cmd__name_hash(int argc, const char **argv); int cmd__online_cpus(int argc, const char **argv); diff --git a/t/meson.build b/t/meson.build index 2752321e0d..07436b63f4 100644 --- a/t/meson.build +++ b/t/meson.build @@ -1146,7 +1146,6 @@ benchmarks = [ 'perf/p0006-read-tree-checkout.sh', 'perf/p0007-write-cache.sh', 'perf/p0008-odb-fsync.sh', - 'perf/p0071-sort.sh', 'perf/p0090-cache-tree.sh', 'perf/p0100-globbing.sh', 'perf/p1006-cat-file.sh', diff --git a/t/perf/p0071-sort.sh b/t/perf/p0071-sort.sh deleted file mode 100755 index ae4ddac864..0000000000 --- a/t/perf/p0071-sort.sh +++ /dev/null @@ -1,52 +0,0 @@ -#!/bin/sh - -test_description='Basic sort performance tests' -. ./perf-lib.sh - -test_perf_default_repo - -test_expect_success 'setup' ' - git ls-files --stage "*.[ch]" "*.sh" | - cut -f2 -d" " | - git cat-file --batch >unsorted -' - -test_perf 'sort(1) unsorted' ' - sort sorted -' - -test_expect_success 'reverse' ' - sort -r reversed -' - -for file in sorted reversed -do - test_perf "sort(1) $file" " - sort <$file >actual - " -done - -for file in unsorted sorted reversed -do - - test_perf "string_list_sort() $file" " - test-tool string-list sort <$file >actual - " - - test_expect_success "string_list_sort() $file sorts like sort(1)" " - test_cmp_bin sorted actual - " -done - -for file in unsorted sorted reversed -do - test_perf "DEFINE_LIST_SORT $file" " - test-tool mergesort sort <$file >actual - " - - test_expect_success "DEFINE_LIST_SORT $file sorts like sort(1)" " - test_cmp_bin sorted actual - " -done - -test_done -- 2.55.0 ``` ## Junio C Hamano, 2026-10-07 17:27 Subject: Re: [PATCH] test-mergesort: plug memory leaks in sort_stdin() Message-ID: URL: https://gitlist.dev/e/xmqqzewp8lqw.fsf%40gitster.g In-Reply-To: ``` Patrick Steinhardt writes: > I was briefly wondering whether we could get rid of t0071 altogether in > favor of converting the tests into a unit test, and then drop the test > helper. And that's certainly doable, and I'd argue it would also be the > right thing to do. Yup, unlike any "test-tool" feature that is specific to some Git operation, things like mergesort does not need to be part of end-to-end t[0-9]{4}-*.sh test suite. > But anyway, that's of course a much bigger scope, and I'm fine to just > fix the bugs for now. ;-). > I noticed that there's another "generate" subcommand here that is > entirely unused. Do we maybe want to also remove it while at it? The > test suite passes with the below diff. Great. Thanks. ```