diff mbox series

[v2,2/2] negotiator/skipping: fix some problems in mark_common()

Message ID abbb1bc0b35d03e13249ec2e5bb8229a0a123685.1682473718.git.hanxin.hx@bytedance.com (mailing list archive)
State New, archived
Headers show
Series [v1] negotiator/default.c: avoid stack overflow | expand

Commit Message

Han Xin April 26, 2023, 4:05 a.m. UTC
Fixed the following problems:

1. prio_queue() should be used with clear_prio_queue(), otherwise there
   will be a memory leak.
2. It does not do duplicate protection before prio_queue_put().
   (The COMMON bit would work here, too.)
3. When it translated from recursive to iterative it kept "return"
   statements that should probably be "continue" statements.
4. It does not attempt to parse commits, and instead returns
   immediately when finding an unparsed commit. This is something
   that it did in its original version, so maybe it is by design,
   but it doesn't match the doc comment for the method.

Helped-by: Derrick Stolee <derrickstolee@github.com>
Signed-off-by: Han Xin <hanxin.hx@bytedance.com>
---
 negotiator/skipping.c | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

Comments

Derrick Stolee April 26, 2023, 11:08 a.m. UTC | #1
On 4/26/2023 12:05 AM, Han Xin wrote:
> Fixed the following problems:

This might be a good time to reference the change from recursive to
iterative:

  The mark_common() method in negotiator/skipping.c was converted
  from recursive to iterative in 4654134976f (negotiator/skipping:
  avoid stack overflow, 2022-10-25), but there is some more work
  to do:
 
> 1. prio_queue() should be used with clear_prio_queue(), otherwise there
>    will be a memory leak.
> 2. It does not do duplicate protection before prio_queue_put().
>    (The COMMON bit would work here, too.)
> 3. When it translated from recursive to iterative it kept "return"
>    statements that should probably be "continue" statements.
> 4. It does not attempt to parse commits, and instead returns
>    immediately when finding an unparsed commit. This is something
>    that it did in its original version, so maybe it is by design,
>    but it doesn't match the doc comment for the method.
> 
> Helped-by: Derrick Stolee <derrickstolee@github.com>
> Signed-off-by: Han Xin <hanxin.hx@bytedance.com>
> ---
>  negotiator/skipping.c | 10 ++++++----
>  1 file changed, 6 insertions(+), 4 deletions(-)
> 
> diff --git a/negotiator/skipping.c b/negotiator/skipping.c
> index c7d6ab39bc..b06dcb197b 100644
> --- a/negotiator/skipping.c
> +++ b/negotiator/skipping.c
> @@ -85,7 +85,7 @@ static int clear_marks(const char *refname, const struct object_id *oid,
>  }
>  
>  /*
> - * Mark this SEEN commit and all its SEEN ancestors as COMMON.
> + * Mark this SEEN commit and all its parsed SEEN ancestors as COMMON.

Ok, the doc comment is updated here instead of starting to parse
commits. Since this is the behavior since it was first introduced
in 42cc7485a2e (negotiator/skipping: skip commits during fetch,
2018-07-16), this is the best thing to do.

I notice from a second glance that we are only walking the commits
that are marked SEEN, so we are only visiting commits with respect
to a previous walk of some kind, which provides some explanation.

>  	while ((c = prio_queue_get(&queue))) {
>  		struct commit_list *p;
>  		if (c->object.flags & COMMON)
> -			return;
> +			continue;
>  		c->object.flags |= COMMON;
>  		if (!(c->object.flags & POPPED))
>  			data->non_common_revs--;
>  
>  		if (!c->object.parsed)
> -			return;
> +			continue;
>  		for (p = c->parents; p; p = p->next) {
> -			if (p->item->object.flags & SEEN)
> +			if (p->item->object.flags & SEEN || p->item->object.flags & COMMON)
>  				prio_queue_put(&queue, p->item);

This is the incorrect check for the COMMON bit, because it is
a positive check (we add the common bit after we pop a commit
from the queue) _and_ because we could add a commit multiple
times before it is first popped and that bit is added.

Instead, we need

			if ((p->item->object.flags & SEEN) &&
			    !(p->item->object.flags & COMMON)) {
				p->item->object.flags |= COMMON;
				prio_queue_put(&queue, p->item);
			}

and at the start of the loop we need to add the COMMON bit to
the starting commit. We also need to remove this bit from the
main section of the loop:

  		if (c->object.flags & COMMON)
			continue;
 		c->object.flags |= COMMON;

because it does nothing if the COMMON bit is added before
being added to the queue.

I'm very suspicious that this change did not trigger a test
failure, since the behavior is quite different from the previous
version. Of course, the recursive-to-iterative change was first
to change the behavior, so I'm not surprised that it isn't caught
by tests. What kind of tests can we introduce to harden our
coverage here?

>  		}
>  	}
> +
> +	clear_prio_queue(&queue);

Good to clean up this queue.

Thanks,
-Stolee
Han Xin April 26, 2023, 11:55 a.m. UTC | #2
On Wed, Apr 26, 2023 at 7:09 PM Derrick Stolee <derrickstolee@github.com> wrote:
>
> On 4/26/2023 12:05 AM, Han Xin wrote:
> > Fixed the following problems:
>
> This might be a good time to reference the change from recursive to
> iterative:
>
>   The mark_common() method in negotiator/skipping.c was converted
>   from recursive to iterative in 4654134976f (negotiator/skipping:
>   avoid stack overflow, 2022-10-25), but there is some more work
>   to do:
>

Make sense.

> >       while ((c = prio_queue_get(&queue))) {
> >               struct commit_list *p;
> >               if (c->object.flags & COMMON)
> > -                     return;
> > +                     continue;
> >               c->object.flags |= COMMON;
> >               if (!(c->object.flags & POPPED))
> >                       data->non_common_revs--;
> >
> >               if (!c->object.parsed)
> > -                     return;
> > +                     continue;
> >               for (p = c->parents; p; p = p->next) {
> > -                     if (p->item->object.flags & SEEN)
> > +                     if (p->item->object.flags & SEEN || p->item->object.flags & COMMON)
> >                               prio_queue_put(&queue, p->item);
>
> This is the incorrect check for the COMMON bit, because it is
> a positive check (we add the common bit after we pop a commit
> from the queue) _and_ because we could add a commit multiple
> times before it is first popped and that bit is added.
>

Yes, I introduced a silly thing.

> Instead, we need
>
>                         if ((p->item->object.flags & SEEN) &&
>                             !(p->item->object.flags & COMMON)) {
>                                 p->item->object.flags |= COMMON;
>                                 prio_queue_put(&queue, p->item);
>                         }
>
> and at the start of the loop we need to add the COMMON bit to
> the starting commit. We also need to remove this bit from the
> main section of the loop:
>
>                 if (c->object.flags & COMMON)
>                         continue;
>                 c->object.flags |= COMMON;
>
> because it does nothing if the COMMON bit is added before
> being added to the queue.
>

Make sense.
And with this, we should do return before loop:

                if (seen_commit->object.flags & COMMON)
                        return;

                prio_queue_put(&queue, seen_commit);
                while ((c = prio_queue_get(&queue))) {

> I'm very suspicious that this change did not trigger a test
> failure, since the behavior is quite different from the previous
> version. Of course, the recursive-to-iterative change was first
> to change the behavior, so I'm not surprised that it isn't caught
> by tests. What kind of tests can we introduce to harden our
> coverage here?
>

With "p->item->object.flags & COMMON", it takes more meaningless
walking, but doesn't seem to introduce any errors. I haven't found any
good way to avoid similar problems.

Thanks
-Han Xin
diff mbox series

Patch

diff --git a/negotiator/skipping.c b/negotiator/skipping.c
index c7d6ab39bc..b06dcb197b 100644
--- a/negotiator/skipping.c
+++ b/negotiator/skipping.c
@@ -85,7 +85,7 @@  static int clear_marks(const char *refname, const struct object_id *oid,
 }
 
 /*
- * Mark this SEEN commit and all its SEEN ancestors as COMMON.
+ * Mark this SEEN commit and all its parsed SEEN ancestors as COMMON.
  */
 static void mark_common(struct data *data, struct commit *seen_commit)
 {
@@ -96,18 +96,20 @@  static void mark_common(struct data *data, struct commit *seen_commit)
 	while ((c = prio_queue_get(&queue))) {
 		struct commit_list *p;
 		if (c->object.flags & COMMON)
-			return;
+			continue;
 		c->object.flags |= COMMON;
 		if (!(c->object.flags & POPPED))
 			data->non_common_revs--;
 
 		if (!c->object.parsed)
-			return;
+			continue;
 		for (p = c->parents; p; p = p->next) {
-			if (p->item->object.flags & SEEN)
+			if (p->item->object.flags & SEEN || p->item->object.flags & COMMON)
 				prio_queue_put(&queue, p->item);
 		}
 	}
+
+	clear_prio_queue(&queue);
 }
 
 /*