Re: [PATCH] merge-ort: only do pointer arithmetic for non-empty lists

From: "René Scharfe" <l.s.r@web.de>
To: Andrzej Hunt via GitGitGadget <gitgitgadget@gmail.com>,
	git@vger.kernel.org
Cc: Elijah Newren <newren@gmail.com>,
	Andrzej Hunt <andrzej@ahunt.org>,
	Andrzej Hunt <ajrhunt@google.com>
Subject: Re: [PATCH] merge-ort: only do pointer arithmetic for non-empty lists
Date: Sat, 10 Apr 2021 13:48:18 +0200	[thread overview]
Message-ID: <1866b90b-fe07-18df-0d60-e2350d935375@web.de> (raw)
In-Reply-To: <pull.930.git.1618043449249.gitgitgadget@gmail.com>

Am 10.04.21 um 10:30 schrieb Andrzej Hunt via GitGitGadget:
> From: Andrzej Hunt <ajrhunt@google.com>
>
> versions could be an empty string_list. In that case, versions->items is
> NULL, and we shouldn't be trying to perform pointer arithmetic with it (as
> that results in undefined behaviour).
>
> This issue has probably existed since:
>   ee4012dcf9 (merge-ort: step 2 of tree writing -- function to create tree object, 2020-12-13)
> But it only started occurring during tests since tests started using
> merge-ort:
>   f3b964a07e (Add testing with merge-ort merge strategy, 2021-03-20)
>
> For reference - here's the original UBSAN commit that implemented this
> check, it sounds like this behaviour isn't actually likely to cause any
> issues (but we might as well fix it regardless):
> https://reviews.llvm.org/D67122
>
> UBSAN output from t3404 or t5601:
>
> merge-ort.c:2669:43: runtime error: applying zero offset to null pointer
>     #0 0x78bb53 in write_tree merge-ort.c:2669:43
>     #1 0x7856c9 in process_entries merge-ort.c:3303:2
>     #2 0x782317 in merge_ort_nonrecursive_internal merge-ort.c:3744:2
>     #3 0x77feef in merge_incore_nonrecursive merge-ort.c:3853:2
>     #4 0x6f6a5c in do_recursive_merge sequencer.c:640:3
>     #5 0x6f6a5c in do_pick_commit sequencer.c:2221:9
>     #6 0x6ef055 in single_pick sequencer.c:4814:9
>     #7 0x6ef055 in sequencer_pick_revisions sequencer.c:4867:10
>     #8 0x4fb392 in run_sequencer revert.c:225:9
>     #9 0x4fa5b0 in cmd_revert revert.c:235:8
>     #10 0x42abd7 in run_builtin git.c:453:11
>     #11 0x429531 in handle_builtin git.c:704:3
>     #12 0x4282fb in run_argv git.c:771:4
>     #13 0x4282fb in cmd_main git.c:902:19
>     #14 0x524b63 in main common-main.c:52:11
>     #15 0x7fc2ca340349 in __libc_start_main (/lib64/libc.so.6+0x24349)
>     #16 0x4072b9 in _start start.S:120
>
> SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior merge-ort.c:2669:43 in
>
> Signed-off-by: Andrzej Hunt <ajrhunt@google.com>
> ---
>     merge-ort: only do pointer arithmetic for non-empty lists
>
>     Here's a small and inconsequential UBSAN issue that started happening
>     when running tests on next since yesterday (since the merge of
>     en/ort-readiness).
>
>     It can be reproduced with something like this (t3404 also triggers the
>     same issue):
>
>     make SANITIZE=undefined COPTS="-Og -g" T="$(wildcard t5601-*.sh)"
>     GIT_TEST_OPTS="-v" UBSAN_OPTIONS=print_stacktrace=1 test
>
>     ATB, Andrzej
>
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-930%2Fahunt%2Fmerge-ort-ubsan-v1
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-930/ahunt/merge-ort-ubsan-v1
> Pull-Request: https://github.com/gitgitgadget/git/pull/930
>
>  merge-ort.c | 6 ++++--
>  1 file changed, 4 insertions(+), 2 deletions(-)
>
> diff --git a/merge-ort.c b/merge-ort.c
> index 5e118a85ee04..4da4b4688336 100644
> --- a/merge-ort.c
> +++ b/merge-ort.c
> @@ -2504,8 +2504,10 @@ static void write_tree(struct object_id *result_oid,
>  	 * We won't use relevant_entries again and will let it just pop off the
>  	 * stack, so there won't be allocation worries or anything.
>  	 */
> -	relevant_entries.items = versions->items + offset;
> -	relevant_entries.nr = versions->nr - offset;
> +	if (versions->nr) {
> +		relevant_entries.items = versions->items + offset;
> +		relevant_entries.nr = versions->nr - offset;
> +	}
>  	QSORT(relevant_entries.items, relevant_entries.nr, tree_entry_order);

Reading the diff I was wondering if QSORT now gets handed uninitialized
values if version-nr is 0.  The answer is no -- relevant_entries is
initialized at declaration.  Otherwise the compiler would have probably
warned, but sometimes it gets confused.

I wonder why relevant_entries is introduced at all, though.  It's not
referenced later.  So how about this instead?

	if (versions->nr)
		QSORT(versions->items + offset, nr, tree_entry_order);

The intent to sort the last versions->nr-offset entries of versions,
but only if it's not empty, is easier to see like this, I think.

>
>  	/* Pre-allocate some space in buf */
>
> base-commit: 89b43f80a514aee58b662ad606e6352e03eaeee4
>