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

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

[Martin Ågren]

`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(-)

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

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

[Martin Ågren]

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

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

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

[Martin Ågren]

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

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

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

[Junio C Hamano]

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.

> +/*
> + * 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);

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

[Martin Ågren]

On 2 November 2017 at 05:54, Junio C Hamano <gitster@pobox.com> wrote:
> 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.

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

[Martin Ågren]

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

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

[Martin Ågren]

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

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

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

[Martin Ågren]

`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(-)

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

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

[Martin Ågren]

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

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

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

[Martin Ågren]

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

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