bisect: fix memory leak and document `find_bisection()`

PATCH In review Martin Ågren 2 participants 10 messages Nov 1, 2017 – Nov 5, 2017

Share & tools

Martin Ågren

author

2017-11-01 20:35 UTC #0 lore raw

PATCH 1/3 bisect: fix memory leak and document `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.

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 <[email protected]>

---
 bisect.c | 4 +++-
 bisect.h | 7 +++++++
 2 files changed, 10 insertions(+), 1 deletion(-)

bisect.c +3 -1

index 96beeb5d1..f9de4f2e8 100644
@@ -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))

bisect.h +7 -0

index acd12ef80..cf135f16e 100644
@@ -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);

Signature · 1 line

2.15.0.415.gac1375d7e

Martin Ågren

author

2017-11-01 20:35 UTC #1 lore raw

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 <[email protected]>

---
 bisect.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

bisect.c +4 -3

index f9de4f2e8..fda527b89 100644
@@ -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;

Signature · 1 line

2.15.0.415.gac1375d7e

Martin Ågren

author

2017-11-01 20:35 UTC #2 lore raw

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

In reply to 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 <[email protected]>

---
 bisect.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

bisect.c +5 -1

index fda527b89..c1aaf632a 100644
@@ -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);

Signature · 1 line

2.15.0.415.gac1375d7e

Junio C Hamano

2017-11-02 04:54 UTC #3 lore raw

In reply to Martin Ågren

Quoted 7 lines · 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.

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.

Quoted 10 lines

bisect.h +7 -0

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

author

2017-11-02 10:47 UTC #4 lore raw

Quoted 14 lines · Junio C Hamano

Quoted 7 lines · 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.
Good. Thanks.
I notice that this has only two callers and both of them do

Quoted 7 lines

        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

author

2017-11-05 20:25 UTC #5 lore raw

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

Signature · 1 line

2.15.0.415.gac1375d7e

Martin Ågren

author

2017-11-05 20:25 UTC #6 lore raw

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 <[email protected]>

---
 bisect.h           | 12 +++++++++---
 bisect.c           | 16 +++++++---------
 builtin/rev-list.c |  3 +--
 3 files changed, 17 insertions(+), 14 deletions(-)

bisect.h +9 -3

index acd12ef80..c535e6d12 100644
@@ -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,

bisect.c +7 -9

index 96beeb5d1..5a3ae4971 100644
@@ -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) {

builtin/rev-list.c +1 -2

index c1c74d4a7..fb1c36af6 100644
@@ -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);

Signature · 1 line

2.15.0.415.gac1375d7e

Martin Ågren

author

2017-11-05 20:25 UTC #7 lore raw

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

In reply to 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 <[email protected]>

---
 bisect.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

bisect.c +3 -1

index 5a3ae4971..2f4321767 100644
@@ -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))

Signature · 1 line

2.15.0.415.gac1375d7e

Martin Ågren

author

2017-11-05 20:25 UTC #8 lore raw

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

In reply to Martin Ågren

Signed-off-by Martin Ågren <[email protected]>

Signed-off-by Junio C Hamano <[email protected]>

---
 bisect.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

bisect.c +4 -3

index 2f4321767..b1941505b 100644
@@ -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;

Signature · 1 line

2.15.0.415.gac1375d7e

Martin Ågren

author

2017-11-05 20:25 UTC #9 lore raw

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

In reply to 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 <[email protected]>

Signed-off-by Junio C Hamano <[email protected]>

---
 bisect.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

bisect.c +5 -1

index b1941505b..3756f127b 100644
@@ -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);

Signature · 1 line

2.15.0.415.gac1375d7e