threads / patch / 47096

patch, 3 partsbisect: fix memory leak and document `find_bisection()`

Subject: [PATCH 1/3] bisect: fix memory leak and document `find_bisection()`

## tl;dr

10 messages between Nov 1, 2017 and Nov 5, 2017. Diffs are folded; open one to read it.

replies: 9people: 2as markdown or json

Martin Ågren· Nov 1, 2017, 20:34 UTC · lore

`find_bisection()` rebuilds the commit list it is given by reversing it and skipping uninteresting commits. The uninteresting list entries are leaked. Free them to fix the leak.

While we're here and understand what's going on, document the function. In particular, make sure to document that the original list should not be examined by the caller.

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
 bisect.c | 4 +++-
 bisect.h | 7 +++++++
 2 files changed, 10 insertions(+), 1 deletion(-)
Show changes to 2 files +10 −1

bisect.c, bisect.h

diff --git a/bisect.c b/bisect.c
index 96beeb5d1..f9de4f2e8 100644
--- a/bisect.c
+++ b/bisect.c
@@ -380,8 +380,10 @@ struct commit_list *find_bisection(struct commit_list *list,
 		unsigned flags = p->item->object.flags;
 
 		next = p->next;
-		if (flags & UNINTERESTING)
+		if (flags & UNINTERESTING) {
+			free(p);
 			continue;
+		}
 		p->next = last;
 		last = p;
 		if (!(flags & TREESAME))
diff --git a/bisect.h b/bisect.h
index acd12ef80..cf135f16e 100644
--- a/bisect.h
+++ b/bisect.h
@@ -1,6 +1,13 @@
 #ifndef BISECT_H
 #define BISECT_H
 
+/*
+ * Find bisection. If something is found, `reaches` will be the number of
+ * commits that the best commit reaches. `all` will be the count of
+ * non-SAMETREE commits. If `find_all` is set, all non-SAMETREE commits are
+ * returned sorted, otherwise only a single best commit is returned. The
+ * original list will be left in an undefined state and should not be examined.
+ */
 extern struct commit_list *find_bisection(struct commit_list *list,
 					  int *reaches, int *all,
 					  int find_all);
-- 
2.15.0.415.gac1375d7e
Martin Ågren· Nov 1, 2017, 20:34 UTC · re: Martin Ågren · lore

[PATCH 2/3] bisect: fix off-by-one error in `best_bisection_sorted()`

After we have sorted the `cnt`-many commits that we have selected, we place them into the commit list. We then set `p->next` to NULL, but as we do so, `p` is already pointing one beyond item number `cnt`. Indeed, we check whether `p` is NULL before dereferencing it.

This only matters if there are TREESAME-commits. Since they should be skipped, they are not included in `cnt` and we will hit the situation where we set `p->next` to NULL. As a result, the list will be one longer than it should be. The last commit in the list will be one which occurs earlier, or which shouldn't be included.

Do not update `p` the very last round in the loop. This ensures that after the loop, `p->next` points to the remainder of the list, and we can set it to NULL. While we're here, free that remainder to fix a memory leak.

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
 bisect.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)
Show changes to bisect.c +4 −3
diff --git a/bisect.c b/bisect.c
index f9de4f2e8..fda527b89 100644
--- a/bisect.c
+++ b/bisect.c
@@ -226,10 +226,11 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
 		add_name_decoration(DECORATION_NONE, buf.buf, obj);
 
 		p->item = array[i].commit;
-		p = p->next;
+		if (i < cnt - 1)
+			p = p->next;
 	}
-	if (p)
-		p->next = NULL;
+	free_commit_list(p->next);
+	p->next = NULL;
 	strbuf_release(&buf);
 	free(array);
 	return list;
-- 
2.15.0.415.gac1375d7e
Martin Ågren· Nov 1, 2017, 20:34 UTC · re: Martin Ågren · lore

[PATCH 3/3] bisect: fix memory leak when returning best element

When `find_bisection()` returns a single list entry, it leaks the other entries. Move the to-be-returned item to the front and free the remainder.

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
 bisect.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)
Show changes to bisect.c +5 −1
diff --git a/bisect.c b/bisect.c
index fda527b89..c1aaf632a 100644
--- a/bisect.c
+++ b/bisect.c
@@ -400,8 +400,12 @@ struct commit_list *find_bisection(struct commit_list *list,
 	/* Do the real work of finding bisection commit. */
 	best = do_find_bisection(list, nr, weights, find_all);
 	if (best) {
-		if (!find_all)
+		if (!find_all) {
+			list->item = best->item;
+			free_commit_list(list->next);
+			best = list;
 			best->next = NULL;
+		}
 		*reaches = weight(best);
 	}
 	free(weights);
-- 
2.15.0.415.gac1375d7e
Junio C Hamano· Nov 2, 2017, 04:54 UTC · re: Martin Ågren · lore

Re: [PATCH 1/3] bisect: fix memory leak and document `find_bisection()`

Martin Ågren <martin.agren@gmail.com> writes:
Show 7 quoted lines
> `find_bisection()` rebuilds the commit list it is given by reversing it
> and skipping uninteresting commits. The uninteresting list entries are
> leaked. Free them to fix the leak.
>
> While we're here and understand what's going on, document the function.
> In particular, make sure to document that the original list should not
> be examined by the caller.
Good.  Thanks.
I notice that this has only two callers and both of them do
	revs.commits = find_bisection(revs.commits, ...);
I wonder if updating its calling convention to
	(void) find_bisection(&revs.commits, ...);
makes sense.  This is obviously outside the scope of this patch.
Show 10 quoted lines
> +/*
> + * Find bisection. If something is found, `reaches` will be the number of
> + * commits that the best commit reaches. `all` will be the count of
> + * non-SAMETREE commits. If `find_all` is set, all non-SAMETREE commits are
> + * returned sorted, otherwise only a single best commit is returned. The
> + * original list will be left in an undefined state and should not be examined.
> + */
>  extern struct commit_list *find_bisection(struct commit_list *list,
>  					  int *reaches, int *all,
>  					  int find_all);
Martin Ågren· Nov 2, 2017, 10:47 UTC · re: Junio C Hamano · lore

Re: [PATCH 1/3] bisect: fix memory leak and document `find_bisection()`

On 2 November 2017 at 05:54, Junio C Hamano <gitster@pobox.com> wrote:
Show 21 quoted lines
> Martin Ågren <martin.agren@gmail.com> writes:
>
>> `find_bisection()` rebuilds the commit list it is given by reversing it
>> and skipping uninteresting commits. The uninteresting list entries are
>> leaked. Free them to fix the leak.
>>
>> While we're here and understand what's going on, document the function.
>> In particular, make sure to document that the original list should not
>> be examined by the caller.
>
> Good.  Thanks.
>
> I notice that this has only two callers and both of them do
>
>         revs.commits = find_bisection(revs.commits, ...);
>
> I wonder if updating its calling convention to
>
>         (void) find_bisection(&revs.commits, ...);
>
> makes sense.  This is obviously outside the scope of this patch.

I think it would. I considered it briefly but punted, though I don't really understand why now. In hindsight, it would have saved me some work, since I wouldn't have had to carefully document that the original list mustn't be examined. I'll let this simmer for a few days in case other comments turn up, then do a v2 with a preparatory patch that switches the calling convention as you suggested.

Thanks.
Martin Ågren· Nov 5, 2017, 20:24 UTC · re: Martin Ågren · lore

[PATCH v2 0/4] bisect: assorted leak-fixes

This fixes a couple of leaks around `find_bisection(). The first patch is new since v1 [1] to make the calling-convention of `find_bisection()` less prone to misuse. Patch 2 is similar to v1, the only difference is that the "while at it" has moved into patch 1. Patches 3 and 4 are identical to v1.

Martin
[1] https://public-inbox.org/git/4795556016c25e4a78241362547c5468877f808d.1509557518.git.martin.agren@gmail.com/
Martin Ågren (4):
  bisect: change calling-convention of `find_bisection()`
  bisect: fix memory leak in `find_bisection()`
  bisect: fix off-by-one error in `best_bisection_sorted()`
  bisect: fix memory leak when returning best element
 bisect.h           | 12 +++++++++---
 bisect.c           | 33 +++++++++++++++++++--------------
 builtin/rev-list.c |  3 +--
 3 files changed, 29 insertions(+), 19 deletions(-)
-- 
2.15.0.415.gac1375d7e
Martin Ågren· Nov 5, 2017, 20:24 UTC · re: Martin Ågren · lore

[PATCH v2 1/4] bisect: change calling-convention of `find_bisection()`

This function takes a commit list and returns a commit list. The returned list is built by modifying the original list. Thus the caller should not use the original list again (and after the next commit fixes a memory leak, it must not).

Change the function signature so that it takes a **list and has void return type. That should make it harder to misuse this function.

While we're here, document this function.
Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
 bisect.h           | 12 +++++++++---
 bisect.c           | 16 +++++++---------
 builtin/rev-list.c |  3 +--
 3 files changed, 17 insertions(+), 14 deletions(-)
Show changes to 3 files +17 −14

bisect.h, bisect.c, builtin/rev-list.c

diff --git a/bisect.h b/bisect.h
index acd12ef80..c535e6d12 100644
--- a/bisect.h
+++ b/bisect.h
@@ -1,9 +1,15 @@
 #ifndef BISECT_H
 #define BISECT_H
 
-extern struct commit_list *find_bisection(struct commit_list *list,
-					  int *reaches, int *all,
-					  int find_all);
+/*
+ * Find bisection. If something is found, `reaches` will be the number of
+ * commits that the best commit reaches. `all` will be the count of
+ * non-SAMETREE commits. If nothing is found, `list` will be NULL.
+ * Otherwise, it will be either all non-SAMETREE commits or the single
+ * best commit, as chosen by `find_all`.
+ */
+extern void find_bisection(struct commit_list **list, int *reaches, int *all,
+			   int find_all);
 
 extern struct commit_list *filter_skipped(struct commit_list *list,
 					  struct commit_list **tried,
diff --git a/bisect.c b/bisect.c
index 96beeb5d1..5a3ae4971 100644
--- a/bisect.c
+++ b/bisect.c
@@ -360,21 +360,20 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		return best_bisection_sorted(list, nr);
 }
 
-struct commit_list *find_bisection(struct commit_list *list,
-					  int *reaches, int *all,
-					  int find_all)
+void find_bisection(struct commit_list **commit_list, int *reaches,
+		    int *all, int find_all)
 {
 	int nr, on_list;
-	struct commit_list *p, *best, *next, *last;
+	struct commit_list *list, *p, *best, *next, *last;
 	int *weights;
 
-	show_list("bisection 2 entry", 0, 0, list);
+	show_list("bisection 2 entry", 0, 0, *commit_list);
 
 	/*
 	 * Count the number of total and tree-changing items on the
 	 * list, while reversing the list.
 	 */
-	for (nr = on_list = 0, last = NULL, p = list;
+	for (nr = on_list = 0, last = NULL, p = *commit_list;
 	     p;
 	     p = next) {
 		unsigned flags = p->item->object.flags;
@@ -402,7 +401,7 @@ struct commit_list *find_bisection(struct commit_list *list,
 		*reaches = weight(best);
 	}
 	free(weights);
-	return best;
+	*commit_list = best;
 }
 
 static int register_ref(const char *refname, const struct object_id *oid,
@@ -954,8 +953,7 @@ int bisect_next_all(const char *prefix, int no_checkout)
 
 	bisect_common(&revs);
 
-	revs.commits = find_bisection(revs.commits, &reaches, &all,
-				       !!skipped_revs.nr);
+	find_bisection(&revs.commits, &reaches, &all, !!skipped_revs.nr);
 	revs.commits = managed_skipped(revs.commits, &tried);
 
 	if (!revs.commits) {
diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index c1c74d4a7..fb1c36af6 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -397,8 +397,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	if (bisect_list) {
 		int reaches = reaches, all = all;
 
-		revs.commits = find_bisection(revs.commits, &reaches, &all,
-					      bisect_find_all);
+		find_bisection(&revs.commits, &reaches, &all, bisect_find_all);
 
 		if (bisect_show_vars)
 			return show_bisect_vars(&info, reaches, all);
-- 
2.15.0.415.gac1375d7e
Martin Ågren· Nov 5, 2017, 20:24 UTC · re: Martin Ågren · lore

[PATCH v2 2/4] bisect: fix memory leak in `find_bisection()`

`find_bisection()` rebuilds the commit list it is given by reversing it and skipping uninteresting commits. The uninteresting list entries are leaked. Free them to fix the leak.

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
 bisect.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)
Show changes to bisect.c +3 −1
diff --git a/bisect.c b/bisect.c
index 5a3ae4971..2f4321767 100644
--- a/bisect.c
+++ b/bisect.c
@@ -379,8 +379,10 @@ void find_bisection(struct commit_list **commit_list, int *reaches,
 		unsigned flags = p->item->object.flags;
 
 		next = p->next;
-		if (flags & UNINTERESTING)
+		if (flags & UNINTERESTING) {
+			free(p);
 			continue;
+		}
 		p->next = last;
 		last = p;
 		if (!(flags & TREESAME))
-- 
2.15.0.415.gac1375d7e
Martin Ågren· Nov 5, 2017, 20:24 UTC · re: Martin Ågren · lore

[PATCH v2 3/4] bisect: fix off-by-one error in `best_bisection_sorted()`

After we have sorted the `cnt`-many commits that we have selected, we place them into the commit list. We then set `p->next` to NULL, but as we do so, `p` is already pointing one beyond item number `cnt`. Indeed, we check whether `p` is NULL before dereferencing it.

This only matters if there are TREESAME-commits. Since they should be skipped, they are not included in `cnt` and we will hit the situation where we set `p->next` to NULL. As a result, the list will be one longer than it should be. The last commit in the list will be one which occurs earlier, or which shouldn't be included.

Do not update `p` the very last round in the loop. This ensures that after the loop, `p->next` points to the remainder of the list, and we can set it to NULL. While we're here, free that remainder to fix a memory leak.

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 bisect.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)
Show changes to bisect.c +4 −3
diff --git a/bisect.c b/bisect.c
index 2f4321767..b1941505b 100644
--- a/bisect.c
+++ b/bisect.c
@@ -226,10 +226,11 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
 		add_name_decoration(DECORATION_NONE, buf.buf, obj);
 
 		p->item = array[i].commit;
-		p = p->next;
+		if (i < cnt - 1)
+			p = p->next;
 	}
-	if (p)
-		p->next = NULL;
+	free_commit_list(p->next);
+	p->next = NULL;
 	strbuf_release(&buf);
 	free(array);
 	return list;
-- 
2.15.0.415.gac1375d7e
Martin Ågren· Nov 5, 2017, 20:24 UTC · re: Martin Ågren · lore

[PATCH v2 4/4] bisect: fix memory leak when returning best element

When `find_bisection()` returns a single list entry, it leaks the other entries. Move the to-be-returned item to the front and free the remainder.

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 bisect.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)
Show changes to bisect.c +5 −1
diff --git a/bisect.c b/bisect.c
index b1941505b..3756f127b 100644
--- a/bisect.c
+++ b/bisect.c
@@ -399,8 +399,12 @@ void find_bisection(struct commit_list **commit_list, int *reaches,
 	/* Do the real work of finding bisection commit. */
 	best = do_find_bisection(list, nr, weights, find_all);
 	if (best) {
-		if (!find_all)
+		if (!find_all) {
+			list->item = best->item;
+			free_commit_list(list->next);
+			best = list;
 			best->next = NULL;
+		}
 		*reaches = weight(best);
 	}
 	free(weights);
-- 
2.15.0.415.gac1375d7e

← back to recent threads