git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 1/3] commit-reach: deduplicate queue entries in paint_down_to_common

From
Kristofer Karlsson <krka@spotify.com>
Date
May 25, 2026, 06:50 UTC
Message-ID
<CAL71e4NxpbM8QZYhVA_SSC4vDmAFv-Kpe6qDcurefgPkSSdSnQ@mail.gmail.com>
In-Reply-To
<ca39c8ca-ca4c-4954-a1ab-633bfa55f64b@gmail.com>
I ran an audit of the flag allocation table and found three stale entries:
1. sha1-name.c was renamed to object-name.c.
2. builtin/show-branch.c uses bits 0 and 2-28, not 0-26.
3. negotiator/skipping.c is missing — it uses bits 2-5 like
negotiator/default.c, with ADVERTISED on bit 3 instead of
COMMON_REF.

I have a fixup commit ready - mini-preview below. I can submit it on top of this patchset or create a separate patch if you prefer that?

+ * negotiator/skipping.c: 2--5
- * sha1-name.c:                                         20
+ * object-name.c:                                       20
- * builtin/show-branch.c: 0-------------------------------------------26
+ * builtin/show-branch.c: 0-----------------------------------------------28

While doing the audit I noticed that reasoning about flag safety is currently entirely manual. Would there be interest in something more systematic (e.g. runtime registration/assertion, dynamic allocation or static analysis of flag usage)? I have some local work on that already, but I was not sure if this was something worth spending time on or not.

- Kristofer
On Mon, 25 May 2026 at 03:43, Derrick Stolee <stolee@gmail.com> wrote:
Show 70 quoted lines
>
> On 5/24/26 7:40 PM, Junio C Hamano wrote:
> > "Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>
> > writes:
> >
> >> diff --git a/commit-reach.c b/commit-reach.c
> >> index d3a9b3ed6f..c16d4b061c 100644
> >> --- a/commit-reach.c
> >> +++ b/commit-reach.c
> >> @@ -17,8 +17,9 @@
> >>   #define PARENT2            (1u<<17)
> >>   #define STALE              (1u<<18)
> >>   #define RESULT             (1u<<19)
> >> +#define ENQUEUED    (1u<<20)
> >>
> >> -static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);
> >> +static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT | ENQUEUED);
> >> ...
> >> diff --git a/object.h b/object.h
> >> index d814647ebe..05cbf728e9 100644
> >> --- a/object.h
> >> +++ b/object.h
> >> @@ -74,7 +74,7 @@ void object_array_init(struct object_array *array);
> >>    * bundle.c:                                        16
> >>    * http-push.c:                          11-----14
> >>    * commit-graph.c:                                15
> >> - * commit-reach.c:                                  16-----19
> >> + * commit-reach.c:                                  16-------20
> >>    * builtin/last-modified.c:                         1617
> >>    * sha1-name.c:                                              20
> >>    * list-objects-filter.c:                                      21
> >
> > Not directly the fault of this series, but we'd need to audit and
> > update this table of bit assignment to match more recent reality.
> >
> > For example, there no longer exists sha1-name.c but the table claims
> > that bit 20 is in use for its own purpose, and it being stale makes
> > it harder to audit and ensure that this new use would not crash with
> > these existing uses (note. there are other uses of bit 20 in other
> > subsystems).
>
> It would be worth adding an update patch before this patch, that
> only makes these adjustments
>
> > FWIW, object-name.c, which was formerly known as sha1-name.c, uses
> > the bit 20 as ONELINE_SEEN bit, which is used to turn textual object
> > names like :/string (i.e., commit with that string in its message)
> > into raw object name, and bit 20 is cleared from all the objects
> > involved in the search before the helper function returns.
>
> This appears to me like the only interaction that _could_ have
> overlap with paint_down_to_common().
>
> > Presumably, once commit-reach.c starts queueing commits and reuses
> > this bit for its own purpose, we will never try to parse a textual
> > commit object name to clobber what we thought is ENQUEUED bit,
> > breaking the code introduced here, so we are probably safe against
> > its use.
> >
> > I didn't check all other uses of bit 20, though.
>
> FLAG_LINK in builtin/index-pack.c and FLAG_OPEN in
> builtin/unpack-objects.c both seem to be completely independent from
> this use in commit-reach.c.
>
> Thanks,
> -Stolee
>
>
>
Previous: Derrick StoleeNext: Junio C Hamano
Message 5 of 26 in “commit-reach: replace queue_has_nonstale with a counter”
  1. 0/3 commit-reach: replace queue_has_nonstale with a counterKristofer Karlsson via GitGitGadget, May 24, 2026
  2. 1/3 commit-reach: deduplicate queue entries in paint_down_to_commonKristofer Karlsson via GitGitGadget, May 24, 2026
  3. Junio C HamanoMay 24, 2026
  4. Derrick StoleeMay 25, 2026
  5. Kristofer KarlssonMay 25, 2026
  6. Junio C HamanoMay 25, 2026
  7. Kristofer KarlssonMay 25, 2026
  8. Jeff KingMay 25, 2026
  9. Jeff KingMay 25, 2026
  10. Jeff KingMay 25, 2026
  11. 2/3 commit-reach: optimize queue scan in paint_down_to_commonKristofer Karlsson via GitGitGadget, May 24, 2026
  12. Derrick StoleeMay 25, 2026
  13. Kristofer KarlssonMay 25, 2026
  14. 3/3 commit-reach: optimize queue scan in ahead_behindKristofer Karlsson via GitGitGadget, May 24, 2026
  15. Jeff KingMay 25, 2026
  16. Jeff KingMay 25, 2026
  17. Kristofer KarlssonMay 25, 2026
  18. Junio C HamanoMay 25, 2026
  19. Jeff KingMay 25, 2026
  20. Kristofer KarlssonMay 25, 2026
  21. 0/3 commit-reach: replace queue_has_nonstale() scan with O(1) trackingKristofer Karlsson via GitGitGadget, May 25, 2026
  22. 1/3 object.h: fix stale entries in object flag allocation tableKristofer Karlsson via GitGitGadget, May 25, 2026
  23. 2/3 commit-reach: deduplicate queue entries in paint_down_to_commonKristofer Karlsson via GitGitGadget, May 25, 2026
  24. Junio C HamanoMay 25, 2026
  25. Kristofer KarlssonMay 26, 2026
  26. 3/3 commit-reach: replace queue_has_nonstale() scan with O(1) trackingKristofer Karlsson via GitGitGadget, May 25, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.