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

Re: [PATCH v2 2/2] fsck: use oidset for skiplist

From
Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Date
Aug 27, 2018, 07:37 UTC
Message-ID
<87r2ikdzvc.fsf@evledraar.gmail.com>
In-Reply-To
<ae61a845-16fa-e2d6-935d-ce5eb1e33e5a@web.de>
On Sat, Aug 25 2018, René Scharfe wrote:
Show 13 quoted lines
> diff --git a/Documentation/config.txt b/Documentation/config.txt
> index 2fa65b7516..80ab570579 100644
> --- a/Documentation/config.txt
> +++ b/Documentation/config.txt
> @@ -1715,7 +1715,7 @@ doing the same for `receive.fsck.<msg-id>` and `fetch.fsck.<msg-id>`
>  will only cause git to warn.
>
>  fsck.skipList::
> -	The path to a sorted list of object names (i.e. one SHA-1 per
> +	The path to a list of object names (i.e. one SHA-1 per
>  	line) that are known to be broken in a non-fatal way and should
>  	be ignored. This feature is useful when an established project
>  	should be accepted despite early commits containing errors that

I was going to say that since this is a file format we're likely to support across versions we should make a note that "up to version so-and-so this needed to be sorted, but that's longer the case. So e.g. someone wouldn't test this on 2.20 (or read the online docs) and then deploy this for older clients..

But...
Show 20 quoted lines
> -	if (options->skiplist)
> -		sorted = options->skiplist->sorted;
> -	else {
> -		sorted = 1;
> -		options->skiplist = &skiplist;
> -	}
> -
>  	fp = fopen(path, "r");
>  	if (!fp)
>  		die("Could not open skip list: %s", path);
> @@ -202,19 +192,12 @@ static void init_skiplist(struct fsck_options *options, const char *path)
>  		const char *p;
>  		if (parse_oid_hex(sb.buf, &oid, &p) || *p != '\0')
>  			die("Invalid SHA-1: %s", sb.buf);
> -		oid_array_append(&skiplist, &oid);
> -		if (sorted && skiplist.nr > 1 &&
> -				oidcmp(&skiplist.oid[skiplist.nr - 2],
> -				       &oid) > 0)
> -			sorted = 0;
> +		oidset_insert(&options->skiplist, &oid);

...reading this implementation, where we always called oid_array_append(), but then just kept track of whether the set was sorted...

Show 8 quoted lines
>  	}
>  	if (ferror(fp))
>  		die_errno("Could not read '%s'", path);
>  	fclose(fp);
>  	strbuf_release(&sb);
> -
> -	if (sorted)
> -		skiplist.sorted = 1;
...and here where we assigned to the .sorted member of the oid_array...
Show 7 quoted lines
>  static int object_on_skiplist(struct fsck_options *opts, struct object *obj)
>  {
> -	if (opts && opts->skiplist && obj)
> -		return oid_array_lookup(opts->skiplist, &obj->oid) >= 0;
> -	return 0;
> +	return opts && obj && oidset_contains(&opts->skiplist, &obj->oid);
>  }

....and here where we'd always do the lookup if the skiplist was initialized, *not* just if it's sorted, and how the sha1-array.c code has looked ever since cd94c6f91 ("fsck: git receive-pack: support excluding objects from fsck'ing", 2015-06-22) when this was first added:

    $ git show cd94c6f91:sha1-array.c|grep -A5 sha1_array_lookup
    int sha1_array_lookup(struct sha1_array *array, const unsigned char *sha1)
    {
            if (!array->sorted)
                    sha1_array_sort(array);
            return sha1_pos(sha1, array->sha1, array->nr, sha1_access);
    }

So I think it makes sense to make this series a three-part, where in the first part we only change these docs to say s/sorted //, and modify the tests I added in 65a836fa6b ("fsck: add stress tests for fsck.skipList", 2018-07-27) to assert that an unsorted & sorted list of SHA-1s works just as well.

Then following up with your [12]/2, where the internal implementation is changed, but we make it clear that it's *just* the internal implementation. I.e. from a UI perspective the list never had to be pre-sorted, we'd just spend some work sorting it on the first lookup if it wasn't sorted already.

Now without some very careful reading it's not clear what "we don't need to worry about any sort order anymore" in the commit message means, i.e. what it really means is "for the purposes of the internal implementation, and as an opt-in user-side optimization ...".

I.e. an alternate version of this whole patch series could also be:
    diff --git a/Documentation/config.txt b/Documentation/config.txt
    index 1c4236498..930807e43 100644
    --- a/Documentation/config.txt
    +++ b/Documentation/config.txt
    @@ -1709,5 +1709,5 @@ will only cause git to warn.
     fsck.skipList::
    -       The path to a sorted list of object names (i.e. one SHA-1 per
    +       The path to a list of object names (i.e. one SHA-1 per
            line) that are known to be broken in a non-fatal way and should
            be ignored. This feature is useful when an established project
    diff --git a/fsck.c b/fsck.c
    index a0cee0be5..9d4e938ad 100644
    --- a/fsck.c
    +++ b/fsck.c
    @@ -184,14 +184,10 @@ static void init_skiplist(struct fsck_options *options, const char *path)
     {
            static struct oid_array skiplist = OID_ARRAY_INIT;
    -       int sorted, fd;
    +       int fd;
            char buffer[GIT_MAX_HEXSZ + 1];
            struct object_id oid;
    -       if (options->skiplist)
    -               sorted = options->skiplist->sorted;
    -       else {
    -               sorted = 1;
    +       if (!options->skiplist)
                    options->skiplist = &skiplist;
    -       }
            fd = open(path, O_RDONLY);
    @@ -208,13 +204,6 @@ static void init_skiplist(struct fsck_options *options, const char *path)
                            die("Invalid SHA-1: %s", buffer);
                    oid_array_append(&skiplist, &oid);
    -               if (sorted && skiplist.nr > 1 &&
    -                               oidcmp(&skiplist.oid[skiplist.nr - 2],
    -                                      &oid) > 0)
    -                       sorted = 0;
            }
            close(fd);
    -
    -       if (sorted)
    -               skiplist.sorted = 1;
     }

Now, I like yours much better. I'm just saying that currently the patch/commit message combo is confusing about *what* it's doing. I.e. let's not mix up the correction of docs that were always wrong with a non-change in the user facing implementation, and some internal optimization all in one patch.

Previous: René ScharfeNext: René Scharfe
Message 28 of 31 in “fsck: use strbuf_getline() to read skiplist file”
  1. 1/2 fsck: use strbuf_getline() to read skiplist fileRené Scharfe, Aug 11, 2018
  2. 2/2 fsck: use oidset for skiplistRené Scharfe, Aug 11, 2018
  3. Jeff KingAug 11, 2018
  4. Jeff KingAug 11, 2018
  5. René ScharfeAug 11, 2018
  6. René ScharfeAug 13, 2018
  7. Jeff KingAug 14, 2018
  8. Jeff KingAug 14, 2018
  9. René ScharfeAug 26, 2018
  10. Jeff KingAug 27, 2018
  11. René ScharfeOct 1, 2018
  12. Jeff KingOct 1, 2018
  13. René ScharfeOct 2, 2018
  14. Jeff KingOct 2, 2018
  15. René ScharfeAug 13, 2018
  16. Jeff KingAug 14, 2018
  17. Ævar Arnfjörð BjarmasonAug 11, 2018
  18. René ScharfeAug 25, 2018
  19. Ramsay JonesAug 11, 2018
  20. René ScharfeAug 25, 2018
  21. Junio C HamanoAug 13, 2018
  22. René ScharfeAug 13, 2018
  23. Junio C HamanoAug 13, 2018
  24. René ScharfeAug 13, 2018
  25. Jeff KingAug 11, 2018
  26. René ScharfeAug 11, 2018
  27. 2/2 fsck: use oidset for skiplistRené Scharfe, Aug 25, 2018
  28. Ævar Arnfjörð BjarmasonAug 27, 2018
  29. René ScharfeAug 27, 2018
  30. 1/2 fsck: use strbuf_getline() to read skiplist fileRené Scharfe, Aug 25, 2018
  31. Jeff KingAug 27, 2018

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.