Re: [PATCH 8/9] sha1-file: use loose object cache for quick existence check

[René Scharfe]

Am 05.12.2018 um 09:15 schrieb Jeff King:
> On Wed, Dec 05, 2018 at 01:51:36AM -0500, Jeff King wrote:
> 
>>> This
>>> function is easily converted to struct object_id, though, as its single
>>> caller can pass one on -- this makes the copy unnecessary.
>>
>> If you mean modifying sha1_loose_object_info() to take an oid, then
>> sure, I agree that is a good step forward (and that is exactly the "punt
>> until" moment I meant).
> 
> So the simple thing is to do that, and then have it pass oid->hash to
> the other functions it uses.

Yes.

> If we start to convert those, there's a
> little bit of a rabbit hole, but it's actually not too bad.

You don't need to crawl in just for quick_has_loose(), but eventually
everything has to be converted.  It seems a bit much for one patch, but
perhaps that's just my ever-decreasing attention span speaking.

Converting one function prototype or struct member at a time seems
about the right amount of change per patch to me.  That's not always
possible due to entanglement, of course.

> Most of the spill-over is into the dumb-http code. Note that it actually
> uses sha1 itself! That probably needs to be the_hash_algo (though I'm
> not even sure how we'd negotiate the algorithm across a dumb fetch). At
> any rate, I don't think this patch makes anything _worse_ in that
> respect.

Right.

> diff --git a/sha1-file.c b/sha1-file.c
> index 3ddf4c9426..0705709036 100644
> --- a/sha1-file.c
> +++ b/sha1-file.c
> @@ -333,12 +333,12 @@ int raceproof_create_file(const char *path, 
> create_file_fn fn, void *cb)
>   return ret;
>  }
>  
> -static void fill_sha1_path(struct strbuf *buf, const unsigned char *sha1)
> +static void fill_loose_path(struct strbuf *buf, const struct object_id *oid)

The new name fits.

> @@ -879,15 +879,15 @@ int git_open_cloexec(const char *name, int flags)
>   * Note that it may point to static storage and is only valid until another
>   * call to stat_sha1_file().
>   */
> -static int stat_sha1_file(struct repository *r, const unsigned char *sha1,
> -   struct stat *st, const char **path)
> +static int stat_loose_object(struct repository *r, const struct object_id 
> *oid,
> +  struct stat *st, const char **path)

Hmm, read_sha1_file() was renamed to read_object_file() earlier this
year, and I'd have expected this to become stat_object_file().  Names..

Anyway, the comment above and one a few lines below should be updated
as well.

>  {
>   struct object_directory *odb;
>   static struct strbuf buf = STRBUF_INIT;
>  
>   prepare_alt_odb(r);
>   for (odb = r->objects->odb; odb; odb = odb->next) {
> - *path = odb_loose_path(odb, , sha1);
> + *path = odb_loose_path(odb, , oid);
>   if (!lstat(*path, st))
>   return 0;
>   }
> @@ -900,7 +900,7 @@ static int stat_sha1_file(struct repository *r, const 
> unsigned char *sha1,
>   * descriptor. See the caveats on the "path" parameter above.
>   */
>  static int open_sha1_file(struct repository *r,
> -   const unsigned char *sha1, const char **path)
> +   const struct object_id *oid, const char **path)

That function should lose the "sha1" in its name as well.

> -static void *map_sha1_file_1(struct repository *r, const char *path,
> -  const unsigned char *sha1, unsigned long *size)
> +static void *map_loose_object_1(struct repository *r, const char *path,
> +  const struct object_id *oid, unsigned long *size)

Similarly, map_object_file_1()?

> -void *map_sha1_file(struct repository *r,
> - const unsigned char *sha1, unsigned long *size)
> +void *map_loose_object(struct repository *r,
> +const struct object_id *oid,
> +unsigned long *size)

Similar.

> @@ -1045,7 +1043,9 @@ static int unpack_sha1_header_to_strbuf(git_zstream 
> *stream, unsigned char *map,
>   return -1;
>  }
>  
> -static void *unpack_sha1_rest(git_zstream *stream, void *buffer, unsigned 
> long size, const unsigned char *sha1)
> +static void *unpack_loose_rest(git_zstream *stream,
> +void *buffer, unsigned long size,
> +const struct object_id *oid)

Hmm, both old and new name here look weird to me at this point.

> -static int sha1_loose_object_info(struct repository *r,
> -   const unsigned char *sha1,
> -   struct object_info *oi, int flags)
> +static int loose_object_info(struct repository *r,
> +  const struct object_id *oid,
> +  struct object_info *oi, int flags)

And nothing of value was lost. :)

René

Re: [PATCH 8/9] sha1-file: use loose object cache for quick existence check

[René Scharfe]

Am 05.12.2018 um 05:46 schrieb Jeff King:
> On Tue, Dec 04, 2018 at 10:45:13PM +0100, René Scharfe wrote:
> 
>>> The comment in the context there is warning callers to remember to load
>>> the cache first. Now that we have individual caches, might it make sense
>>> to change the interface a bit, and make these members private. I.e.,
>>> something like:
>>>
>>>   struct oid_array *odb_loose_cache(struct object_directory *odb,
>>> int subdir_nr) 
>>>   {
>>> if (!loose_objects_subdir_seen[subdir_nr])
>>> odb_load_loose_cache(odb, subdir_nr); /* or just inline it here 
>>> */
>>>
>>> return >loose_objects_cache[subdir_nr];
>>>   }
>>
>> Sure.  And it should take an object_id pointer instead of a subdir_nr --
>> less duplication, nicer interface (patch below).
> 
> I had considered that initially, but it's a little less flexible if a
> caller doesn't actually have an oid. Though both of the proposed callers
> do, so it's probably OK to worry about that if and when it ever comes up
> (the most plausible thing in my mind is doing some abbrev-like analysis
> without looking to abbreviate a _particular_ oid).

Right, let's focus on concrete requirements of current callers.  YAGNI..
:)

>> And quick_has_loose() should be converted to object_id as well -- adding
>> a function that takes a SHA-1 is a regression. :D
> 
> I actually wrote it that way initially, but doing the hashcpy() in the
> caller is a bit more awkward. My thought was to punt on that until the
> rest of the surrounding code starts handling oids.

The level of awkwardness is the same to me, but sha1_loose_object_info()
is much longer already, so it might feel worse to add it there.  This
function is easily converted to struct object_id, though, as its single
caller can pass one on -- this makes the copy unnecessary.

> This patch looks sane. How do you want to handle it? I'd assumed your
> earlier one would be for applying on top, but this one doesn't have a
> commit message. Did you want me to squash down the individual hunks?

I'm waiting for the first one (object-store: use one oid_array per
subdirectory for loose cache) to be accepted, as it aims to solve a
user-visible performance regression, i.e. that's where the meat is.
I'm particularly interested in performance numbers from Ævar for it.

I can send the last one properly later, and add patches for converting
quick_has_loose() to struct object_id.  Those are just cosmetic..

René

Re: [PATCH 8/9] sha1-file: use loose object cache for quick existence check

[René Scharfe]

Am 03.12.2018 um 23:04 schrieb Jeff King:
> On Sun, Dec 02, 2018 at 11:52:50AM +0100, René Scharfe wrote:
> 
>>> And for mu.git, a ~20k object repo:
>>>
>>> Test origin/master 
>>> peff/jk/loose-cache   avar/check-collisions-config
>>> 
>>> -
>>> 0008.2: index-pack with 256*1 loose objects  0.59(0.91+0.06)   
>>> 0.58(0.93+0.03) -1.7% 0.57(0.89+0.04) -3.4%
>>> 0008.3: index-pack with 256*10 loose objects 0.59(0.91+0.07)   
>>> 0.59(0.92+0.03) +0.0% 0.57(0.89+0.03) -3.4%
>>> 0008.4: index-pack with 256*100 loose objects0.59(0.91+0.05)   
>>> 0.81(1.13+0.04) +37.3%0.58(0.91+0.04) -1.7%
>>> 0008.5: index-pack with 256*250 loose objects0.59(0.91+0.05)   
>>> 1.23(1.51+0.08) +108.5%   0.58(0.91+0.04) -1.7%
>>> 0008.6: index-pack with 256*500 loose objects0.59(0.90+0.06)   
>>> 1.96(2.20+0.12) +232.2%   0.58(0.91+0.04) -1.7%
>>> 0008.7: index-pack with 256*750 loose objects0.59(0.92+0.05)   
>>> 2.72(2.92+0.17) +361.0%   0.58(0.90+0.04) -1.7%
>>> 0008.8: index-pack with 256*1000 loose objects   0.59(0.90+0.06)   
>>> 3.50(3.67+0.21) +493.2%   0.57(0.90+0.04) -3.4%
>>
>> OK, here's another theory: The cache scales badly with increasing
>> numbers of loose objects because it sorts the array 256 times as it is
>> filled.  Loading it fully and sorting once would help, as would using
>> one array per subdirectory.
> 
> Yeah, that makes sense. This was actually how I had planned to do it
> originally, but then I ended up just reusing the existing single-array
> approach from the abbrev code.
> 
> I hadn't actually thought about the repeated sortings (but that
> definitely makes sense that they would hurt in these pathological
> cases), but more just that we get a 256x reduction in N for our binary
> search (in fact we already do this first-byte lookup-table trick for
> pack index lookups).

Skipping eight steps in a binary search is something, but it's faster
even without that.

Just realized that the demo code can use "lookup" instead of the much
more expensive "for_each_unique" to sort.  D'oh!  With that change:

  for command in '
  foreach (0..255) {
$subdir = sprintf("%02x", $_);
foreach (1..$ARGV[0]) {
  printf("append %s%038d\n", $subdir, $_);
}
# intermediate sort
print "lookup " . "0" x 40 . "\n";
  }
' '
  foreach (0..255) {
$subdir = sprintf("%02x", $_);
foreach (1..$ARGV[0]) {
  printf("append %s%038d\n", $subdir, $_);
}
  }
  # sort once at the end
  print "lookup " . "0" x 40 . "\n";
' '
  foreach (0..255) {
$subdir = sprintf("%02x", $_);
foreach (1..$ARGV[0]) {
  printf("append %s%038d\n", $subdir, $_);
}
# sort each subdirectory separately
print "lookup " . "0" x 40 . "\n";
print "clear\n";
  }
'
  do
time perl -e "$command" 1000 | t/helper/test-tool sha1-array | wc -l
  done

And the results make the scale of the improvement more obvious:

  256

  real0m3.476s
  user0m3.466s
  sys 0m0.099s
  1

  real0m0.157s
  user0m0.148s
  sys 0m0.046s
  256

  real0m0.117s
  user0m0.116s
  sys 0m0.051s

> Your patch looks good to me. We may want to do one thing on top:
> 
>> diff --git a/object-store.h b/object-store.h
>> index 8dceed0f31..ee67a50980 100644
>> --- a/object-store.h
>> +++ b/object-store.h
>> @@ -20,7 +20,7 @@ struct object_directory {
>>   * Be sure to call odb_load_loose_cache() before using.
>>   */
>>  char loose_objects_subdir_seen[256];
>> -struct oid_array loose_objects_cache;
>> +struct oid_array loose_objects_cache[256];
> 
> The comment in the context there is warning callers to remember to load
> the cache first. Now that we have individual caches, might it make sense
> to change the interface a bit, and make these members private. I.e.,
> something like:
> 
>   struct oid_array *odb_loose_cache(struct object_directory *odb,
> int subdir_nr) 
>   {
>   if (!loose_objects_subdir_seen[subdir_nr])
>   odb_load_loose_cache(odb, subdir_nr); /* or just inline it here 
> */
> 
>   return >loose_objects_cache[subdir_nr];
&g

Re: [PATCH 8/9] sha1-file: use loose object cache for quick existence check

[René Scharfe]

Am 13.11.2018 um 11:02 schrieb Ævar Arnfjörð Bjarmason:
> 
> On Mon, Nov 12 2018, Ævar Arnfjörð Bjarmason wrote:
> 
>> On Mon, Nov 12 2018, Ævar Arnfjörð Bjarmason wrote:
>>
>>> I get:
>>>
>>> Test origin/master 
>>> peff/jk/loose-cache  avar/check-collisions-config
>>> 
>>> 
>>> 0008.2: index-pack with 256*1 loose objects  4.31(0.55+0.18)   
>>> 0.41(0.40+0.02) -90.5%   0.23(0.36+0.01) -94.7%
>>> 0008.3: index-pack with 256*10 loose objects 4.37(0.45+0.21)   
>>> 0.45(0.40+0.02) -89.7%   0.25(0.38+0.01) -94.3%
>>> 0008.4: index-pack with 256*100 loose objects4.47(0.53+0.23)   
>>> 0.67(0.63+0.02) -85.0%   0.24(0.38+0.01) -94.6%
>>> 0008.5: index-pack with 256*250 loose objects5.01(0.67+0.30)   
>>> 1.04(0.98+0.06) -79.2%   0.24(0.37+0.01) -95.2%
>>> 0008.6: index-pack with 256*500 loose objects5.11(0.57+0.21)   
>>> 1.81(1.70+0.09) -64.6%   0.25(0.38+0.01) -95.1%
>>> 0008.7: index-pack with 256*750 loose objects5.12(0.60+0.22)   
>>> 2.54(2.38+0.14) -50.4%   0.24(0.38+0.01) -95.3%
>>> 0008.8: index-pack with 256*1000 loose objects   4.52(0.52+0.21)   
>>> 3.36(3.17+0.17) -25.7%   0.23(0.36+0.01) -94.9%
>>>
>>> I then hacked it to test against git.git, but skipped origin/master for
>>> that one because it takes *ages*. So just mine v.s. yours:
>>>
>>> $ GIT_PERF_REPEAT_COUNT=3 GIT_PERF_MAKE_OPTS='-j56 CFLAGS="-O3"' ./run 
>>> peff/jk/loose-cache avar/check-collisions-config p0008-index-pack.sh
>>> [...]
>>> Test peff/jk/loose-cache   
>>> avar/check-collisions-config
>>> 
>>> ---
>>> 0008.2: index-pack with 256*1 loose objects  12.57(28.72+0.61) 
>>> 12.68(29.36+0.62) +0.9%
>>> 0008.3: index-pack with 256*10 loose objects 12.77(28.75+0.61) 
>>> 12.50(28.88+0.56) -2.1%
>>> 0008.4: index-pack with 256*100 loose objects13.20(29.49+0.66) 
>>> 12.38(28.58+0.60) -6.2%
>>> 0008.5: index-pack with 256*250 loose objects14.10(30.59+0.64) 
>>> 12.54(28.22+0.57) -11.1%
>>> 0008.6: index-pack with 256*500 loose objects14.48(31.06+0.74) 
>>> 12.43(28.59+0.60) -14.2%
>>> 0008.7: index-pack with 256*750 loose objects15.31(31.91+0.74) 
>>> 12.67(29.23+0.64) -17.2%
>>> 0008.8: index-pack with 256*1000 loose objects   16.34(32.84+0.76) 
>>> 13.11(30.19+0.68) -19.8%
>>>
>>> So not much of a practical difference perhaps. But then again this isn't
>>> a very realistic test case of anything. Rarely are you going to push a
>>> history of something the size of git.git into a repo with this many
>>> loose objects.
>>>
>>> Using sha1collisiondetection.git is I think the most realistic scenario,
>>> i.e. you'll often end up fetching/pushing something roughly the size of
>>> its entire history on a big repo, and with it:
>>>
>>> Test peff/jk/loose-cache   
>>> avar/check-collisions-config
>>> 
>>> ---
>>> 0008.2: index-pack with 256*1 loose objects  0.16(0.04+0.01)   
>>> 0.05(0.03+0.00) -68.8%
>>> 0008.3: index-pack with 256*10 loose objects 0.19(0.04+0.02)   
>>> 0.05(0.02+0.00) -73.7%
>>> 0008.4: index-pack with 256*100 loose objects0.32(0.17+0.02)   
>>> 0.04(0.02+0.00) -87.5%
>>> 0008.5: index-pack with 256*250 loose objects0.57(0.41+0.03)   
>>> 0.04(0.02+0.00) -93.0%
>>> 0008.6: index-pack with 256*500 loose objects1.02(0.83+0.06)   
>>> 0.04(0.03+0.00) -96.1%
>>> 0008.7: index-pack with 256*750 loose objects1.47(1.24+0.10)   
>>> 0.04(0.02+0.00) -97.3%
>>> 0008.8: index-pack with 256*1000 loose objects   1.94(1.70+0.10)   
>>> 0.04(0.02+0.00) -97.9%
>>>
>>> As noted in previous threads I have an in-house monorepo where (due to
>>> expiry policies) loose objects hover around the 256*250 mark.
>>>
>>> The script, which is hacky as hell and takes shortcuts not to re-create
>>> the huge fake loose object collection every time (takes ages). Perhaps
>>> you're interested in incorporating some version of this into a v2. To be
>>> useful it should take some target path as an env variable.
>>
>> I forgot perhaps the most useful metric. Testing against origin/master
>> too on the sha1collisiondetection.git repo, which as noted above I think
>> is a good stand-in for making a medium sized push to a big repo. This
>> shows when the loose cache becomes counterproductive:
>>
>> Test origin/master 
>> peff/jk/loose-cache   avar/check-collisions-config
>> 
>> 

Re: [PATCH 8/9] sha1-file: use loose object cache for quick existence check

[René Scharfe]

Am 12.11.2018 um 15:54 schrieb Jeff King:
> diff --git a/sha1-file.c b/sha1-file.c
> index 4aae716a37..e53da0b701 100644
> --- a/sha1-file.c
> +++ b/sha1-file.c
> @@ -921,6 +921,24 @@ static int open_sha1_file(struct repository *r,
>   return -1;
>  }
>  
> +static int quick_has_loose(struct repository *r,
> +const unsigned char *sha1)
> +{
> + int subdir_nr = sha1[0];
> + struct object_id oid;
> + struct object_directory *odb;
> +
> + hashcpy(oid.hash, sha1);
> +
> + prepare_alt_odb(r);
> + for (odb = r->objects->odb; odb; odb = odb->next) {
> + odb_load_loose_cache(odb, subdir_nr);

Is this thread-safe?  What happens if e.g. one index-pack thread resizes
the array while another one sorts it?

Loading the cache explicitly up-front would avoid that, and improves
performance a bit in my (very limited) tests on an SSD.  Demo patch for
next at the bottom.  How does it do against your test cases?

> + if (oid_array_lookup(>loose_objects_cache, ) >= 0)
> + return 1;
> + }
> + return 0;
> +}
> +
>  /*
>   * Map the loose object at "path" if it is not NULL, or the path found by
>   * searching for a loose object named "sha1".
> @@ -1171,6 +1189,8 @@ static int sha1_loose_object_info(struct repository *r,
>   if (!oi->typep && !oi->type_name && !oi->sizep && !oi->contentp) {
>   const char *path;
>   struct stat st;
> + if (!oi->disk_sizep && (flags & OBJECT_INFO_QUICK))
> + return quick_has_loose(r, sha1) ? 0 : -1;
>   if (stat_sha1_file(r, sha1, , ) < 0)
>   return -1;
>   if (oi->disk_sizep)
> 

 builtin/fetch.c  |  2 ++
 builtin/index-pack.c |  2 ++
 fetch-pack.c |  2 ++
 object-store.h   |  1 +
 sha1-file.c  | 30 +++---
 5 files changed, 34 insertions(+), 3 deletions(-)

diff --git a/builtin/fetch.c b/builtin/fetch.c
index e0140327aa..4b031f5da5 100644
--- a/builtin/fetch.c
+++ b/builtin/fetch.c
@@ -301,6 +301,8 @@ static void find_non_local_tags(const struct ref *refs,
refname_hash_init(_refs);
refname_hash_init(_refs);
 
+   repo_load_loose_cache(the_repository);
+
for_each_ref(add_one_refname, _refs);
for (ref = refs; ref; ref = ref->next) {
if (!starts_with(ref->name, "refs/tags/"))
diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index ac1f4ea9a7..7fc6321c77 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -1772,6 +1772,8 @@ int cmd_index_pack(int argc, const char **argv, const 
char *prefix)
if (show_stat)
obj_stat = xcalloc(st_add(nr_objects, 1), sizeof(struct 
object_stat));
ofs_deltas = xcalloc(nr_objects, sizeof(struct ofs_delta_entry));
+   if (startup_info->have_repository)
+   repo_load_loose_cache(the_repository);
parse_pack_objects(pack_hash);
if (report_end_of_input)
write_in_full(2, "\0", 1);
diff --git a/fetch-pack.c b/fetch-pack.c
index dd6700bda9..96c4624d9e 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -656,6 +656,8 @@ static void mark_complete_and_common_ref(struct 
fetch_negotiator *negotiator,
 
save_commit_buffer = 0;
 
+   repo_load_loose_cache(the_repository);
+
for (ref = *refs; ref; ref = ref->next) {
struct object *o;
 
diff --git a/object-store.h b/object-store.h
index 8dceed0f31..f98dd3c857 100644
--- a/object-store.h
+++ b/object-store.h
@@ -53,6 +53,7 @@ void add_to_alternates_memory(const char *dir);
  * from 0 to 255 inclusive).
  */
 void odb_load_loose_cache(struct object_directory *odb, int subdir_nr);
+void repo_load_loose_cache(struct repository *r);
 
 struct packed_git {
struct packed_git *next;
diff --git a/sha1-file.c b/sha1-file.c
index 05f63dfd4e..ae12f0a198 100644
--- a/sha1-file.c
+++ b/sha1-file.c
@@ -921,10 +921,19 @@ static int open_sha1_file(struct repository *r,
return -1;
 }
 
+static int quick_has_loose_odb(struct object_directory *odb,
+  const struct object_id *oid)
+{
+   int subdir_nr = oid->hash[0];
+
+   if (odb->loose_objects_subdir_seen[subdir_nr])
+   return oid_array_lookup(>loose_objects_cache, oid) >= 0;
+   return check_and_freshen_odb(odb, oid, 0);
+}
+
 static int quick_has_loose(struct repository *r,
   const unsigned char *sha1)
 {
-   int subdir_nr = sha1[0];
struct object_id oid;
struct object_directory *odb;
 
@@ -932,8 +941,7 @@ static int quick_has_loose(struct repository *r,
 
prepare_alt_odb(r);
for (odb = r->objects->odb; odb; odb = odb->next) {
-   odb_load_loose_cache(odb, subdir_nr);
-   if (oid_array_lookup(>loose_objects_cache, ) >= 0)
+   if (quick_has_loose_odb(odb, ))
return 1;
}

Re: [PATCH/RFC v1 1/1] Use size_t instead of unsigned long

[René Scharfe]

Am 19.11.2018 um 06:33 schrieb Torsten Bögershausen:
> The archive-tar.c is actually a good example, why a step-by-step update
> is not ideal (the code would not work any more on Win64).
> 
> If we look here:
> 
> static int stream_blocked(const struct object_id *oid)
> {
>   struct git_istream *st;
>   enum object_type type;
>   size_t sz;
>   char buf[BLOCKSIZE];
>   ssize_t readlen;
> 
>   st = open_istream(oid, , , NULL);
>   ^
>   if (!st)
>   return error(_("cannot stream blob %s"), oid_to_hex(oid));
>   for (;;) {
> 
> The sz variable must follow whatever open_istream() uses, so if we start
> with archive-tar.c, we must use either size_t or ulong, whatever
> open_istream() needs. Otherwise things will break:
> archive-tar.c uses ulong, open_istream() size_t, but we are passing pointers
> around, and here  != _t
> 
> If we only update open_istream(), but not archive-tar.c, then
> things are not better:
> _t != 
> 
> I don't have a good idea how to split the patch.

sz is not actually used later in that function; this change can
be done independently of any other ulong/size_t conversion in that
file.

Hmm, looking at that call I wonder why open_istream() doesn't return
type and size in the struct git_istream.  To make it match
read_object_file(), I suppose.  Perhaps it's an opportunity to
improve its interface?

René

Re: [PATCH 8/9] sha1-file: use loose object cache for quick existence check

[René Scharfe]

Am 13.11.2018 um 11:02 schrieb Ævar Arnfjörð Bjarmason:
> So here's the same test not against NFS, but the local ext4 fs (CO7;
> Linux 3.10) for sha1collisiondetection.git:
> 
> Test origin/master 
> peff/jk/loose-cacheavar/check-collisions-config
> 
> --
> 0008.2: index-pack with 256*1 loose objects  0.02(0.02+0.00)   
> 0.02(0.02+0.01) +0.0%  0.02(0.02+0.00) +0.0%
> 0008.3: index-pack with 256*10 loose objects 0.02(0.02+0.00)   
> 0.03(0.03+0.00) +50.0% 0.02(0.02+0.00) +0.0%
> 0008.4: index-pack with 256*100 loose objects0.02(0.02+0.00)   
> 0.17(0.16+0.01) +750.0%0.02(0.02+0.00) +0.0%
> 0008.5: index-pack with 256*250 loose objects0.02(0.02+0.00)   
> 0.43(0.40+0.03) +2050.0%   0.02(0.02+0.00) +0.0%
> 0008.6: index-pack with 256*500 loose objects0.02(0.02+0.00)   
> 0.88(0.80+0.09) +4300.0%   0.02(0.02+0.00) +0.0%
> 0008.7: index-pack with 256*750 loose objects0.02(0.02+0.00)   
> 1.35(1.27+0.09) +6650.0%   0.02(0.02+0.00) +0.0%
> 0008.8: index-pack with 256*1000 loose objects   0.02(0.02+0.00)   
> 1.83(1.70+0.14) +9050.0%   0.02(0.02+0.00) +0.0%

Ouch.

> And for mu.git, a ~20k object repo:
> 
> Test origin/master 
> peff/jk/loose-cache   avar/check-collisions-config
> 
> -
> 0008.2: index-pack with 256*1 loose objects  0.59(0.91+0.06)   
> 0.58(0.93+0.03) -1.7% 0.57(0.89+0.04) -3.4%
> 0008.3: index-pack with 256*10 loose objects 0.59(0.91+0.07)   
> 0.59(0.92+0.03) +0.0% 0.57(0.89+0.03) -3.4%
> 0008.4: index-pack with 256*100 loose objects0.59(0.91+0.05)   
> 0.81(1.13+0.04) +37.3%0.58(0.91+0.04) -1.7%
> 0008.5: index-pack with 256*250 loose objects0.59(0.91+0.05)   
> 1.23(1.51+0.08) +108.5%   0.58(0.91+0.04) -1.7%
> 0008.6: index-pack with 256*500 loose objects0.59(0.90+0.06)   
> 1.96(2.20+0.12) +232.2%   0.58(0.91+0.04) -1.7%
> 0008.7: index-pack with 256*750 loose objects0.59(0.92+0.05)   
> 2.72(2.92+0.17) +361.0%   0.58(0.90+0.04) -1.7%
> 0008.8: index-pack with 256*1000 loose objects   0.59(0.90+0.06)   
> 3.50(3.67+0.21) +493.2%   0.57(0.90+0.04) -3.4%
> 
> All of which is to say that I think it definitely makes sense to re-roll
> this with a perf test, and a switch to toggle it + docs explaining the
> caveats & pointing to the perf test. It's a clear win in some scenarios,
> but a big loss in others.

Right, but can we perhaps find a way to toggle it automatically, like
the special fetch-pack cache tried to do?

So the code needs to decide between using lstat() on individual loose
objects files or opendir()+readdir() to load the names in a whole
fan-out directory.  Intuitively I'd try to solve it using red tape, by
measuring the duration of both kinds of calls, and then try to find a
heuristic based on those numbers.  Is the overhead worth it?

But first, may I interest you in some further complication?  We can
also use access(2) to check for the existence of files.  It doesn't
need to fill in struct stat, so may have a slight advantage if we
don't need any of that information.  The following patch is a
replacement for patch 8 and improves performance by ca. 3% with
git.git on an SSD for me; I'm curious to see how it does on NFS:

---
 sha1-file.c | 15 ++-
 1 file changed, 10 insertions(+), 5 deletions(-)

diff --git a/sha1-file.c b/sha1-file.c
index b77dacedc7..5315c37cbc 100644
--- a/sha1-file.c
+++ b/sha1-file.c
@@ -888,8 +888,13 @@ static int stat_sha1_file(struct repository *r, const 
unsigned char *sha1,
prepare_alt_odb(r);
for (odb = r->objects->odb; odb; odb = odb->next) {
*path = odb_loose_path(odb, , sha1);
-   if (!lstat(*path, st))
-   return 0;
+   if (st) {
+   if (!lstat(*path, st))
+   return 0;
+   } else {
+   if (!access(*path, F_OK))
+   return 0;
+   }
}
 
return -1;
@@ -1171,7 +1176,8 @@ static int sha1_loose_object_info(struct repository *r,
if (!oi->typep && !oi->type_name && !oi->sizep && !oi->contentp) {
const char *path;
struct stat st;
-   if (stat_sha1_file(r, sha1, , ) < 0)
+   struct stat *stp = oi->disk_sizep ?  : NULL;
+   if (stat_sha1_file(r, sha1, stp, ) < 0)
return -1;
if (oi->disk_sizep)
*oi->disk_sizep = st.st_size;
@@ -1382,7 +1388,6 @@ void *read_object_file_extended(const struct object_id 
*oid,
void 

Re: [PATCH 9/9] fetch-pack: drop custom loose object cache

[René Scharfe]

Am 12.11.2018 um 20:32 schrieb Ævar Arnfjörð Bjarmason:
> 
> On Mon, Nov 12 2018, René Scharfe wrote:
>> This removes the only user of OBJECT_INFO_IGNORE_LOOSE.  #leftoverbits
> 
> With this series applied there's still a use of it left in
> oid_object_info_extended()

OK, rephrasing: With that patch, OBJECT_INFO_IGNORE_LOOSE is never set
anymore, and its check in oid_object_info_extended() as well as its
definition can be removed.

René

Re: [PATCH 7/9] object-store: provide helpers for loose_objects_cache

[René Scharfe]

Am 12.11.2018 um 15:50 schrieb Jeff King:
> --- a/sha1-file.c
> +++ b/sha1-file.c
> @@ -2125,6 +2125,32 @@ int for_each_loose_object(each_loose_object_fn cb, 
> void *data,
>   return 0;
>  }
>  
> +static int append_loose_object(const struct object_id *oid, const char *path,
> +void *data)
> +{
> + oid_array_append(data, oid);
> + return 0;
> +}
> +
> +void odb_load_loose_cache(struct object_directory *odb, int subdir_nr)
> +{
> + struct strbuf buf = STRBUF_INIT;
> +
> + if (subdir_nr < 0 ||

Why not make subdir_nr unsigned (like in for_each_file_in_obj_subdir()), and
get rid of this first check?

> + subdir_nr >= ARRAY_SIZE(odb->loose_objects_subdir_seen))

Using unsigned char for subdir_nr would allow removing the second check as
well, but might hide invalid values in implicit conversions, I guess.

> + BUG("subdir_nr out of range");

Showing the invalid value (like in for_each_file_in_obj_subdir()) would make
debugging easier in case the impossible actually happens.

> +
> + if (odb->loose_objects_subdir_seen[subdir_nr])
> + return;
> +
> + strbuf_addstr(, odb->path);
> + for_each_file_in_obj_subdir(subdir_nr, ,
> + append_loose_object,
> + NULL, NULL,
> + >loose_objects_cache);
> + odb->loose_objects_subdir_seen[subdir_nr] = 1;

About here would be the ideal new home for ...

> +}
> +
>  static int check_stream_sha1(git_zstream *stream,
>const char *hdr,
>unsigned long size,
> diff --git a/sha1-name.c b/sha1-name.c
> index 358ca5e288..b24502811b 100644
> --- a/sha1-name.c
> +++ b/sha1-name.c
> @@ -83,36 +83,19 @@ static void update_candidates(struct disambiguate_state 
> *ds, const struct object
>   /* otherwise, current can be discarded and candidate is still good */
>  }
>  
> -static int append_loose_object(const struct object_id *oid, const char *path,
> -void *data)
> -{
> - oid_array_append(data, oid);
> - return 0;
> -}
> -
>  static int match_sha(unsigned, const unsigned char *, const unsigned char *);
>  
>  static void find_short_object_filename(struct disambiguate_state *ds)
>  {
>   int subdir_nr = ds->bin_pfx.hash[0];
>   struct object_directory *odb;
> - struct strbuf buf = STRBUF_INIT;
>  
>   for (odb = the_repository->objects->odb;
>odb && !ds->ambiguous;
>odb = odb->next) {
>   int pos;
>  
> - if (!odb->loose_objects_subdir_seen[subdir_nr]) {
> - strbuf_reset();
> - strbuf_addstr(, odb->path);
> - for_each_file_in_obj_subdir(subdir_nr, ,
> - append_loose_object,
> - NULL, NULL,
> - >loose_objects_cache);
> - odb->loose_objects_subdir_seen[subdir_nr] = 1;
> - }
> -
> + odb_load_loose_cache(odb, subdir_nr);
>   pos = oid_array_lookup(>loose_objects_cache, >bin_pfx);
>   if (pos < 0)
>   pos = -1 - pos;
> @@ -125,8 +108,6 @@ static void find_short_object_filename(struct 
> disambiguate_state *ds)
>   pos++;
>   }
>   }
> -
> - strbuf_release();

... this line.

>  }
>  
>  static int match_sha(unsigned len, const unsigned char *a, const unsigned 
> char *b)
> 

Re: [PATCH 9/9] fetch-pack: drop custom loose object cache

[René Scharfe]

Am 12.11.2018 um 15:55 schrieb Jeff King:
> Commit 024aa4696c (fetch-pack.c: use oidset to check existence of loose
> object, 2018-03-14) added a cache to avoid calling stat() for a bunch of
> loose objects we don't have.
> 
> Now that OBJECT_INFO_QUICK handles this caching itself, we can drop the
> custom solution.
> 
> Note that this might perform slightly differently, as the original code
> stopped calling readdir() when we saw more loose objects than there were
> refs. So:
> 
>   1. The old code might have spent work on readdir() to fill the cache,
>  but then decided there were too many loose objects, wasting that
>  effort.
> 
>   2. The new code might spend a lot of time on readdir() if you have a
>  lot of loose objects, even though there are very few objects to
>  ask about.

Plus the old code used an oidset while the new one uses an oid_array.

> In practice it probably won't matter either way; see the previous commit
> for some discussion of the tradeoff.
> 
> Signed-off-by: Jeff King 
> ---
>  fetch-pack.c | 39 ++-
>  1 file changed, 2 insertions(+), 37 deletions(-)
> 
> diff --git a/fetch-pack.c b/fetch-pack.c
> index b3ed7121bc..25a88f4eb2 100644
> --- a/fetch-pack.c
> +++ b/fetch-pack.c
> @@ -636,23 +636,6 @@ struct loose_object_iter {
>   struct ref *refs;
>  };
>  
> -/*
> - *  If the number of refs is not larger than the number of loose objects,
> - *  this function stops inserting.
> - */
> -static int add_loose_objects_to_set(const struct object_id *oid,
> - const char *path,
> - void *data)
> -{
> - struct loose_object_iter *iter = data;
> - oidset_insert(iter->loose_object_set, oid);
> - if (iter->refs == NULL)
> - return 1;
> -
> - iter->refs = iter->refs->next;
> - return 0;
> -}
> -
>  /*
>   * Mark recent commits available locally and reachable from a local ref as
>   * COMPLETE. If args->no_dependents is false, also mark COMPLETE remote refs 
> as
> @@ -670,30 +653,14 @@ static void mark_complete_and_common_ref(struct 
> fetch_negotiator *negotiator,
>   struct ref *ref;
>   int old_save_commit_buffer = save_commit_buffer;
>   timestamp_t cutoff = 0;
> - struct oidset loose_oid_set = OIDSET_INIT;
> - int use_oidset = 0;
> - struct loose_object_iter iter = {_oid_set, *refs};
> -
> - /* Enumerate all loose objects or know refs are not so many. */
> - use_oidset = !for_each_loose_object(add_loose_objects_to_set,
> - , 0);
>  
>   save_commit_buffer = 0;
>  
>   for (ref = *refs; ref; ref = ref->next) {
>   struct object *o;
> - unsigned int flags = OBJECT_INFO_QUICK;
>  
> - if (use_oidset &&
> - !oidset_contains(_oid_set, >old_oid)) {
> - /*
> -  * I know this does not exist in the loose form,
> -  * so check if it exists in a non-loose form.
> -  */
> - flags |= OBJECT_INFO_IGNORE_LOOSE;

This removes the only user of OBJECT_INFO_IGNORE_LOOSE.  #leftoverbits

> - }
> -
> - if (!has_object_file_with_flags(>old_oid, flags))
> + if (!has_object_file_with_flags(>old_oid,
> + OBJECT_INFO_QUICK))
>   continue;
>   o = parse_object(the_repository, >old_oid);
>   if (!o)
> @@ -710,8 +677,6 @@ static void mark_complete_and_common_ref(struct 
> fetch_negotiator *negotiator,
>   }
>   }
>  
> - oidset_clear(_oid_set);
> -
>   if (!args->deepen) {
>   for_each_ref(mark_complete_oid, NULL);
>   for_each_cached_alternate(NULL, mark_alternate_complete);
> 

Re: [PATCH] khash: silence -Wunused-function

[René Scharfe]

Am 23.10.2018 um 13:34 schrieb Carlo Marcelo Arenas Belón:
> after 36da893114 ("config.mak.dev: enable -Wunused-function", 2018-10-18)
> macro generated code should use a similar solution than commit-slab to
> silence the compiler.

With Clang 6 and GCC 8 on Debian I don't get any warnings on master or
36da893114.

With Clang 6 on OpenBSD I get warnings about the unused khash functions
in delta-islands.c on master, though.

What do you get, or in other words: why did you send this patch?

> Signed-off-by: Carlo Marcelo Arenas Belón 
> ---
>  khash.h | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/khash.h b/khash.h
> index d10caa0c35..39c2833877 100644
> --- a/khash.h
> +++ b/khash.h
> @@ -234,7 +234,7 @@ static const double __ac_HASH_UPPER = 0.77;
>   __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, 
> __hash_equal)
>  
>  #define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, 
> __hash_equal) \
> - KHASH_INIT2(name, static inline, khkey_t, khval_t, kh_is_map, 
> __hash_func, __hash_equal)
> + KHASH_INIT2(name, __attribute__((__unused__)) static inline, khkey_t, 
> khval_t, kh_is_map, __hash_func, __hash_equal)
>  
>  /* Other convenient macros... */
>  

This fixes the warning on OpenBSD for me.  So does moving the KHASH_INIT
line from delta-islands.c to a header file (e.g. khash.h or
delta-islands.h).

René

Re: [PATCH] commit-reach: fix sorting commits by generation

[René Scharfe]

Am 22.10.2018 um 23:10 schrieb Thomas Gummerer:
> compare_commit_by_gen is used to sort a list of pointers to 'struct
> commit'.  The comparison function for qsort is called with pointers to
> the objects it needs to compare, so when sorting a list of 'struct
> commit *', the arguments are of type 'struct commit **'.  However,
> currently the comparison function casts it's arguments to 'struct
> commit *' and uses those, leading to out of bounds memory access and
> potentially to wrong results.  Fix that.
> 
> Signed-off-by: Thomas Gummerer 
> ---
> 
> I noticed this by running the test suite through valgrind.  I'm not
> familiar with this code, so I'm not sure why this didn't cause any
> issues or how they would manifest, but this seems like the right fix
> for this function either way.

Right; I sent a similar patch a while ago, but it seems to have fallen
through the cracks:

https://public-inbox.org/git/d1b58614-989f-5998-6c53-c19eee409...@web.de/

Anyway, your implied question was discussed back then.  Derrick wrote:

   The reason to sort is to hopefully minimize the amount we walk by 
   exploring the "lower" commits first. This is a performance-only thing, 
   not a correctness issue (which is why the bug exists). Even then, it is 
   just a heuristic.

Does b6723e4671 in pu (commit-reach: fix first-parent heuristic) change
that picture?  Did a quick test and found no performance difference with
and without the fix on top, i.e. proper sorting didn't seem to matter.

>  commit-reach.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/commit-reach.c b/commit-reach.c
> index bc522d6840..9efddfd7a0 100644
> --- a/commit-reach.c
> +++ b/commit-reach.c
> @@ -516,8 +516,8 @@ int commit_contains(struct ref_filter *filter, struct 
> commit *commit,
>  
>  static int compare_commits_by_gen(const void *_a, const void *_b)
>  {
> - const struct commit *a = (const struct commit *)_a;
> - const struct commit *b = (const struct commit *)_b;
> + const struct commit *a = *(const struct commit **)_a;
> + const struct commit *b = *(const struct commit **)_b;
>  
>   if (a->generation < b->generation)
>   return -1;
> 

Looks good to me.

René

Re: [PATCH 15/16] commit-reach: make can_all_from_reach... linear

[René Scharfe]

Am 15.10.2018 um 17:31 schrieb Derrick Stolee:
> On 10/14/2018 10:29 AM, René Scharfe wrote:
>> diff --git a/git-compat-util.h b/git-compat-util.h
>> index 5f2e90932f..491230fc57 100644
>> --- a/git-compat-util.h
>> +++ b/git-compat-util.h
>> @@ -1066,6 +1066,21 @@ static inline void sane_qsort(void *base, size_t 
>> nmemb, size_t size,
>>  qsort(base, nmemb, size, compar);
>>   }
>>   
>> +#define DECLARE_SORT(scope, name, elemtype) \
>> +scope void name(elemtype, size_t)
>> +
>> +#define DEFINE_SORT(scope, name, elemtype, one, two)
>> \
>> +static int name##_compare(const elemtype, const elemtype);  \
>> +static int name##_compare_void(const void *a, const void *b)
>> \
>> +{   \
>> +return name##_compare(a, b);\
>> +}   \
>> +scope void name(elemtype base, size_t nmemb)
>> \
>> +{   \
>> +QSORT(base, nmemb, name##_compare_void);\
>> +}   \
>> +static int name##_compare(const elemtype one, const elemtype two)
>> +
> 
> Since you were worried about the "private" name of the compare function, 
> maybe split this macro into two: DEFINE_COMPARE and DEFINE_SORT. Then, 
> if someone wants direct access to the compare function, they could use 
> the DEFINE_COMPARE to ensure the typing is correct, and use QSORT as 
> normal with name##_compare_void.

The pointers are converted to const void * somewhere along the way from
qsort() to compare function.  Splitting the macro would require type
check tricks to make sure the types of the compare function matches the
array to be sorted.  Letting a single macro bake it all into a layer
cake of generated functions is a lot simpler.

> As I think about this, I think this is less of a problem than is worth 
> this split. The commit-slab definitions generate a lot of methods using 
> the "name##" convention, so perhaps we should just trust developers 
> using the macros to look up the macro definition or similar examples. In 
> that sense, including a conversion that consumes the compare function 
> directly can be a signpost for future callers.

Using the generated compare function name directly is a bit awkward; e.g.
in the two example cases it would be sort_by_score_compare() and
sort_packed_ref_records_compare().  Defining the real compare function
the usual way (with a proper name) and having the DEFINE_SORT block call
it is a bit more repetitive, but clean and understandable IMHO.

We also could just leave complicated cases alone..

> I would say that maybe the times where you need to do something special 
> should be pulled out into their own patches, so we can call attention to 
> them directly.

Right; this patch was just a sketch.

> I like this "sort_by_" convention..
> 
>>   
>>  for (i = 0; i < nr_packs; i++) {
>>  pack_names[i] = pairs[i].pack_name;
>> @@ -455,10 +453,8 @@ struct pack_midx_entry {
>>  uint64_t offset;
>>   };
>>   
>> -static int midx_oid_compare(const void *_a, const void *_b)
>> +DEFINE_SORT(static, sort_midx, struct pack_midx_entry *, a, b)
>>   {
>> -const struct pack_midx_entry *a = (const struct pack_midx_entry *)_a;
>> -const struct pack_midx_entry *b = (const struct pack_midx_entry *)_b;
>>  int cmp = oidcmp(>oid, >oid);
>>   
>>  if (cmp)
>> @@ -573,7 +569,7 @@ static struct pack_midx_entry *get_sorted_entries(struct 
>> multi_pack_index *m,
>>  }
>>  }
>>   
>> -QSORT(entries_by_fanout, nr_fanout, midx_oid_compare);
>> +sort_midx(entries_by_fanout, nr_fanout);
> 
> ...but it isn't followed here. Perhaps "sort_by_oid"?

That function sorts by oid, pack_mtime, and pack_int_id, but including
all these fields in the name is a bit unwieldy.  Being unspecific by
calling it sort_midx() was the lazy way out.  Mentioning only oid is a
bit misleading.  Perhaps sort_by_oid_etc()?

René

Re: [PATCH 15/16] commit-reach: make can_all_from_reach... linear

[René Scharfe]

Am 05.10.2018 um 21:42 schrieb Jeff King:
> On Fri, Oct 05, 2018 at 09:36:28PM +0200, René Scharfe wrote:
> 
>> Am 05.10.2018 um 21:08 schrieb Jeff King:
>>> On Fri, Oct 05, 2018 at 08:48:27PM +0200, René Scharfe wrote:
>>>> +#define DEFINE_SORT(name, type, compare)  \
>>>> +static int compare##_void(const void *one, const void *two)   
>>>> \
>>>> +{ \
>>>> +  return compare(one, two);   \
>>>> +} \
>>>> +static void name(type base, size_t nmemb) \
>>>> +{ \
>>>> +  const type dummy = NULL;\
>>>> +  if (nmemb > 1)  \
>>>> +  qsort(base, nmemb, sizeof(base[0]), compare##_void);\
>>>> +  else if (0) \
>>>> +  compare(dummy, dummy);  \
>>>> +}
>>>
>>> I do like that this removes the need to have the code block aspart of
>>> the macro.
>>>
>>> Did you measure to see if there is any runtime impact?
>>
>> No, but I wouldn't expect any -- the generated code should be the same
>> in most cases.
>>
>> Here's an example: https://godbolt.org/z/gwXENy.
> 
> OK, that's good enough for me.
> 
>> The typed comparison function can be inlined into the one with the void
>> pointers, though.
> 
> Right, that makes sense. I suspect it depends on the comparison function
> being static, but in a DEFINE_SORT() world, they generally could be.
> 
> So I like this approach.

It still has some repetition, converted code is a bit longer than the
current one, and I don't know how to build a Coccinelle rule that would
do that conversion.

Looked for a possibility to at least leave QSORT call-sites alone by
enhancing that macro, but didn't find any.  Found a few websites
showing off mindblowing macros, thouhg, this one in particular:

https://github.com/pfultz2/Cloak/wiki/C-Preprocessor-tricks,-tips,-and-idioms

Anyway, drove the generative approach a bit further, and came up with
the new DEFINE_SORT below.  I'm unsure about the name; perhaps it should
be called DEFINE_SORT_BY_COMPARE_FUNCTION_BODY, but that's a bit long.
It handles casts and const attributes behind the scenes and avoids
repetition, but looks a bit weird, as it is placed where a function
signature would go.

Apart from that the macro is simple and doesn't use any tricks or
added checks.  It just sets up boilerplate functions to offer type-safe
sorting.

diffcore-rename.c and refs/packed-backend.c receive special treatment in
the patch because their compare functions are used outside of sorting as
well.  I made them take typed pointers nevertheless and used them from
DEFINE_SORT; the wrapper generated by that macro is supposed to be
private.  Given that such reuse is rare and I think we don't need a way
to make it public.

What do y'all think about this direction?

---
 bisect.c|  8 ++--
 builtin/describe.c  |  6 ++
 builtin/fmt-merge-msg.c | 10 --
 builtin/index-pack.c| 14 --
 builtin/name-rev.c  |  5 ++---
 builtin/pack-objects.c  |  7 ++-
 builtin/remote.c|  6 ++
 builtin/shortlog.c  | 15 ---
 commit-graph.c  |  6 ++
 delta-islands.c |  8 +++-
 diff.c  |  8 +++-
 diffcore-delta.c|  7 ++-
 diffcore-order.c|  7 ++-
 diffcore-rename.c   | 11 +++
 git-compat-util.h   | 15 +++
 help.c  |  7 ++-
 line-log.c  |  7 ++-
 midx.c  | 12 
 pack-check.c|  6 ++
 pathspec.c  |  8 ++--
 refs/packed-backend.c   | 11 ---
 sha1-array.c|  4 ++--
 sha1-name.c |  4 ++--
 23 files changed, 84 insertions(+), 108 deletions(-)

diff --git a/bisect.c b/bisect.c
index e8b17cf7e1..25257c2e69 100644
--- a/bisect.c
+++ b/bisect.c
@@ -192,12 +192,8 @@ struct commit_dist {
int distance;
 };
 
-static int compare_commit_dist(const void *a_, const void *b_)
+DEFINE_SORT(static, sort_by_commit_dist, struct commit_dist *, a, b)
 {
-   struct commit_dist *a, *b;
-
-   a = (struct commit_dist *)a_;
-   b = (struct commit_dist *)b_;
if (a->distance != b->distance)
return b->distance - a->distance; /* desc sort */
return oidcmp(>commit->object.oid, >commit-&g

Re: [PATCH v3] coccicheck: process every source file at once

[René Scharfe]

Am 05.10.2018 um 21:00 schrieb Jeff King:
> On Fri, Oct 05, 2018 at 08:50:50PM +0200, SZEDER Gábor wrote:
> 
>> On Fri, Oct 05, 2018 at 12:59:01PM -0400, Jeff King wrote:
>>> On Fri, Oct 05, 2018 at 04:53:35PM +, Keller, Jacob E wrote:
>>>
> Are we OK with saying 1.3-1.8GB is necessary to run coccicheck? That
> doesn't feel like an exorbitant request for a developer-only tool these
> days, but I have noticed some people on the list tend to have lousier
> machines than I do. ;)
>
> -Peff

 It's probably not worth trying to make this more complicated and scale
 up how many files we do at once based on the amount of available
 memory on the system...
>>>
>>> Yeah, that sounds too complicated. At most I'd give a Makefile knob to
>>> say "spatch in batches of $(N)". But I'd prefer to avoid even that
>>> complexity if we can.
>>
>> But perhaps one more if-else, e.g.:
>>
>>   if test -n "$(COCCICHECK_ALL_AT_ONCE)"; then \
>>   
>>   else
>>   
>>   fi
>>
>> would be an acceptable compromise?  Dunno.
> 
> That's OK, too, assuming people would actually want to use it. I'm also
> OK shipping this (with the "make -j" fix you suggested) and seeing if
> anybody actually complains. I assume there are only a handful of people
> running coccicheck in the first place.

FWIW, my development environment is a virtual machine with 1200MB RAM
and 900MB swap space.  coccicheck takes almost eight minutes
sequentially, and four and a half minutes with -j4.

Unsurprisingly, it fails after almost three minutes with the patch,
reporting that it ran out of memory.  With 2900MB it fails after almost
two minutes, with 3000MB it succeeds after a good two minutes.

time(1) says (for -j1):

433.30user 36.17system 7:49.84elapsed 99%CPU (0avgtext+0avgdata 
108212maxresident)k
192inputs+1512outputs (0major+16409056minor)pagefaults 0swaps

129.74user 2.06system 2:13.27elapsed 98%CPU (0avgtext+0avgdata 
1884568maxresident)k
236896inputs+1096outputs (795major+462129minor)pagefaults 0swaps

So with the patch it's more than three times faster, but needs more
than seventeen times more memory.  And I need a bigger VM. :-/

René

Re: [PATCH v3 2/5] fetch-pack: load tip_oids eagerly iff needed

[René Scharfe]

Am 05.10.2018 um 22:27 schrieb Jeff King:
> On Fri, Oct 05, 2018 at 10:13:34PM +0200, René Scharfe wrote:
> 
>>>> -{
>>>> -  /*
>>>> -   * Note that this only looks at the ref lists the first time it's
>>>> -   * called. This works out in filter_refs() because even though it may
>>>> -   * add to "newlist" between calls, the additions will always be for
>>>> -   * oids that are already in the set.
>>>> -   */
>>>
>>> I don't think the subtle point this comment is making goes away. We're
>>> still growing the list in the loop that calls tip_oids_contain() (and
>>> which now calls just oidset_contains). That's OK for the reasons given
>>> here, but I think that would need to be moved down to this code:
>>>
>>>> +  if (strict) {
>>>> +  for (i = 0; i < nr_sought; i++) {
>>>> +  ref = sought[i];
>>>> +  if (!is_unmatched_ref(ref))
>>>> +  continue;
>>>> +
>>>> +  add_refs_to_oidset(_oids, unmatched);
>>>> +  add_refs_to_oidset(_oids, newlist);
>>>> +  break;
>>>> +  }
>>>> +  }
>>>
>>> I.e., we need to say here why it's OK to summarize newlist in the
>>> oidset, even though we're adding to it later.
>>
>> There is already this comment:
>>
>>  /* Append unmatched requests to the list */
>>
>> And that's enough in my eyes.  The refs loop at the top splits the list
>> into matched ("the list") and unmatched, and the loop below said comment
>> adds a few more.  I see no subtlety left -- what do I miss?
> 
> It looks like tip_oids is meant as a fast lookup into what's in
> unmatched and newlist. But in the second loop we continue appending to
> newlist. Why is it OK that we do not update tip_oids when we do so?

`tip_oids` contains the object_ids of the all `refs` passed to
filter_refs().  Instead of adding them at the top of the function that
is done only when it has become clear that there are unmatched ones,
as an optimization.  (That optimization was implemented by lazy-loading
in tip_oids_contain() earlier.)  At that point the list has been split
into `newlist` and `unmatched`, so we load from them instead of `refs`.

> 
> I.e., something like this explains it:
> 
> diff --git a/fetch-pack.c b/fetch-pack.c
> index 53914563b5..c0a1b80f4c 100644
> --- a/fetch-pack.c
> +++ b/fetch-pack.c
> @@ -606,6 +606,12 @@ static void filter_refs(struct fetch_pack_args *args,
>   ref->match_status = REF_MATCHED;
>   *newtail = copy_ref(ref);
>   newtail = &(*newtail)->next;
> + /*
> +  * No need to update tip_oids with ref->old_oid; we got
> +  * here because either it was already there, or we are
> +  * in !strict mode, in which case we do not use
> +  * tip_oids at all.
> +  */
>   } else {
>   ref->match_status = REF_UNADVERTISED_NOT_ALLOWED;
>   }

This comment puzzles me -- why ask the question it answers?
`tip_oids` has been loaded with all `refs` at that point; adding
more seems odd.

I feel the code needs be simplified further; not sure how, though,
except perhaps by using the `unfound` array added in another reply.

René

Re: [PATCH v3 2/5] fetch-pack: load tip_oids eagerly iff needed

[René Scharfe]

Am 05.10.2018 um 00:11 schrieb René Scharfe:
> Am 04.10.2018 um 23:38 schrieb Jonathan Tan:
>> I don't think the concerns are truly separated - the first loop quoted
>> needs to know that in the second loop, tip_oids is accessed only if
>> there is at least one unmatched ref.
> 
> Right, the two loops are still closely related, but only the first one
> is concerned with loading refs.
> 
> For a true separation we could first build a list of unmatched refs and
> then loop through that instead of `sought`.  Not sure if that's better,
> but maybe the overhead I imagine it would introduce isn't all that big.

Here's what I mean, on top of the other two patches:

---
 fetch-pack.c | 27 +--
 1 file changed, 13 insertions(+), 14 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 53914563b5..7f28584bce 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -543,6 +543,8 @@ static void filter_refs(struct fetch_pack_args *args,
struct ref *newlist = NULL;
struct ref **newtail = 
struct ref *unmatched = NULL;
+   struct ref **unfound;
+   int nr_unfound = 0;
struct ref *ref, *next;
struct oidset tip_oids = OIDSET_INIT;
int i;
@@ -584,23 +586,19 @@ static void filter_refs(struct fetch_pack_args *args,
}
}
 
-   if (strict) {
-   for (i = 0; i < nr_sought; i++) {
-   ref = sought[i];
-   if (!is_unmatched_ref(ref))
-   continue;
-
-   add_refs_to_oidset(_oids, unmatched);
-   add_refs_to_oidset(_oids, newlist);
-   break;
-   }
+   ALLOC_ARRAY(unfound, nr_sought);
+   for (i = 0; i < nr_sought; i++) {
+   if (is_unmatched_ref(sought[i]))
+   unfound[nr_unfound++] = sought[i];
+   }
+   if (strict && nr_unfound) {
+   add_refs_to_oidset(_oids, unmatched);
+   add_refs_to_oidset(_oids, newlist);
}
 
/* Append unmatched requests to the list */
-   for (i = 0; i < nr_sought; i++) {
-   ref = sought[i];
-   if (!is_unmatched_ref(ref))
-   continue;
+   for (i = 0; i < nr_unfound; i++) {
+   ref = unfound[i];
 
if (!strict || oidset_contains(_oids, >old_oid)) {
ref->match_status = REF_MATCHED;
@@ -611,6 +609,7 @@ static void filter_refs(struct fetch_pack_args *args,
}
}
 
+   free(unfound);
oidset_clear(_oids);
for (ref = unmatched; ref; ref = next) {
next = ref->next;
-- 
2.19.0

Re: [PATCH v3 2/5] fetch-pack: load tip_oids eagerly iff needed

[René Scharfe]

Am 05.10.2018 um 00:07 schrieb Jeff King:
> On Thu, Oct 04, 2018 at 05:09:39PM +0200, René Scharfe wrote:
> 
>> tip_oids_contain() lazily loads refs into an oidset at its first call.
>> It abuses the internal (sub)member .map.tablesize of that oidset to
>> check if it has done that already.
>>
>> Determine if the oidset needs to be populated upfront and then do that
>> instead.  This duplicates a loop, but simplifies the existing one by
>> separating concerns between the two.
> 
> I like this approach much better than what I showed earlier. But...
> 
>> diff --git a/fetch-pack.c b/fetch-pack.c
>> index 3b317952f0..53914563b5 100644
>> --- a/fetch-pack.c
>> +++ b/fetch-pack.c
>> @@ -526,23 +526,6 @@ static void add_refs_to_oidset(struct oidset *oids, 
>> struct ref *refs)
>>  oidset_insert(oids, >old_oid);
>>  }
>>  
>> -static int tip_oids_contain(struct oidset *tip_oids,
>> -struct ref *unmatched, struct ref *newlist,
>> -const struct object_id *id)
>> -{
>> -/*
>> - * Note that this only looks at the ref lists the first time it's
>> - * called. This works out in filter_refs() because even though it may
>> - * add to "newlist" between calls, the additions will always be for
>> - * oids that are already in the set.
>> - */
> 
> I don't think the subtle point this comment is making goes away. We're
> still growing the list in the loop that calls tip_oids_contain() (and
> which now calls just oidset_contains). That's OK for the reasons given
> here, but I think that would need to be moved down to this code:
> 
>> +if (strict) {
>> +for (i = 0; i < nr_sought; i++) {
>> +ref = sought[i];
>> +if (!is_unmatched_ref(ref))
>> +continue;
>> +
>> +add_refs_to_oidset(_oids, unmatched);
>> +add_refs_to_oidset(_oids, newlist);
>> +break;
>> +}
>> +}
> 
> I.e., we need to say here why it's OK to summarize newlist in the
> oidset, even though we're adding to it later.

There is already this comment:

/* Append unmatched requests to the list */

And that's enough in my eyes.  The refs loop at the top splits the list
into matched ("the list") and unmatched, and the loop below said comment
adds a few more.  I see no subtlety left -- what do I miss?

René

Re: [PATCH 15/16] commit-reach: make can_all_from_reach... linear

[René Scharfe]

Am 05.10.2018 um 21:08 schrieb Jeff King:
> On Fri, Oct 05, 2018 at 08:48:27PM +0200, René Scharfe wrote:
>> +#define DEFINE_SORT(name, type, compare)\
>> +static int compare##_void(const void *one, const void *two) \
>> +{   \
>> +return compare(one, two);   \
>> +}   \
>> +static void name(type base, size_t nmemb)   \
>> +{   \
>> +const type dummy = NULL;\
>> +if (nmemb > 1)  \
>> +qsort(base, nmemb, sizeof(base[0]), compare##_void);\
>> +else if (0) \
>> +compare(dummy, dummy);  \
>> +}
> 
> I do like that this removes the need to have the code block aspart of
> the macro.
> 
> Did you measure to see if there is any runtime impact?

No, but I wouldn't expect any -- the generated code should be the same
in most cases.

Here's an example: https://godbolt.org/z/gwXENy.

> As an aside, we may need to take a "scope" argument in case somebody
> wants to do this in a non-static way.

Sure.  (They could easily wrap the static function, but a macro
parameter is simpler still.)

> It would be nice if we could make
> this "static inline", but I don't think even a clever compiler would be
> able to omit the wrapper call.

It could, if it was to inline qsort(3).  Current compilers don't do
that AFAIK, but I wouldn't be too surprised if they started to.

The typed comparison function can be inlined into the one with the void
pointers, though.

René

Re: [PATCH 15/16] commit-reach: make can_all_from_reach... linear

[René Scharfe]

Am 05.10.2018 um 18:51 schrieb Jeff King:
> On Fri, Oct 05, 2018 at 12:59:02AM +0200, René Scharfe wrote:
> 
>> We could also do something like this to reduce the amount of manual
>> casting, but do we want to?  (Macro at the bottom, three semi-random
>> examples at the top.)
>> [...]
>> diff --git a/git-compat-util.h b/git-compat-util.h
>> index 5f2e90932f..f9e78d69a2 100644
>> --- a/git-compat-util.h
>> +++ b/git-compat-util.h
>> @@ -1066,6 +1066,18 @@ static inline void sane_qsort(void *base, size_t 
>> nmemb, size_t size,
>>  qsort(base, nmemb, size, compar);
>>  }
>>  
>> +#define DEFINE_SORT(name, elemtype, one, two, code) \
>> +static int name##_compare(const void *one##_v_, const void *two##_v_)   
>> \
>> +{   \
>> +elemtype const *one = one##_v_; \
>> +elemtype const *two = two##_v_; \
>> +code;   \
>> +}   \
>> +static void name(elemtype *array, size_t n) \
>> +{   \
>> +QSORT(array, n, name##_compare);\
>> +}
> 
> Interesting. When I saw the callers of this macro, I first thought you
> were just removing the casts from the comparison function, but the real
> value here is the matching QSORT() wrapper which provides the type
> safety.

Indeed.

> I'm not wild about declaring functions inside macros, just because it
> makes tools like ctags like useful (but I have certainly been guilty of
> it myself). I'd also worry that taking "code" as a macro parameter might
> not scale (what happens if the code has a comma in it?)

It works fine, as long as the comma is surrounded by parentheses, so
function calls with more than one parameter are fine without any change.

> I think we can address that last part by switching the definition order.
> Like:
> 
>   #define DEFINE_SORT(name, elemtype, one, two) \
>   static int name##_compare(const void *, const void *);\
>   static void name(elemtype *array, size_t n)   \
>   { \
>   QSORT(array, n, name##_compare);\
>   } \
>   static int name##_compare(const void *one##_v_, const void *two##_v_) \
>   { \
>   elemtype const *one = one##_v_; \
>   elemtype const *two = two##_v_; \
> 
> And then expecting the caller to do:
> 
>   DEFINE_SORT(foo, struct foo, a, b)
>  /* code goes here */
>   }
> 
> The unbalanced braces are nasty, though (and likely to screw up editor
> formatting, highlighting, etc).

Adding an extra pair of parentheses if needed is also not ideal, but has
less downsides, I think.

> I wonder if it would be possible to just declare the comparison function
> with its real types, and then teach QSORT() to do a type check. That
> would require typeof() at least, but it would be OK for the type-check
> to be available only to gcc/clang users, I think.
> 
> I'm not quite sure what that type-check would look like, but I was
> thinking something along the lines of (inside the QSORT macro):
> 
>   do {
> /* this will yield a type mismatch if fed the wrong function */
> int (*check)(const typeof(array), const typeof(array)) = compar;
> sane_qsort(array, n, sizeof(*array), n);
>   } while (0)
> 
> I have no idea if that even comes close to compiling, though.

If the comparison function has proper types then we need to declare a
version with void pointer parameters as well to give to qsort(3).  I
think using cast function pointers is undefined.  Perhaps like this?

---
 bisect.c  | 11 +--
 commit-graph.c|  8 
 commit-reach.c| 12 +++-
 git-compat-util.h | 14 ++
 4 files changed, 30 insertions(+), 15 deletions(-)

diff --git a/bisect.c b/bisect.c
index e8b17cf7e1..1fc6278c6b 100644
--- a/bisect.c
+++ b/bisect.c
@@ -192,17 +192,16 @@ struct commit_dist {
int distance;
 };
 
-static int compare_commit_dist(const void *a_, const void *b_)
+static int compare_commit_dist(const struct commit_dist *a,
+  const struct commit_dist *b)
 {
-   struct commit_dist *a, *b;
-
-   a = (struct commit_dist *)

Re: [PATCH 15/16] commit-reach: make can_all_from_reach... linear

[René Scharfe]

Am 01.10.2018 um 22:37 schrieb René Scharfe:
> Am 01.10.2018 um 21:26 schrieb Derrick Stolee:
>> On 10/1/2018 3:16 PM, René Scharfe wrote:
>>> Am 28.06.2018 um 14:31 schrieb Derrick Stolee via GitGitGadget:
>>>> diff --git a/commit-reach.c b/commit-reach.c
>>>> index c58e50fbb..ac132c8e4 100644
>>>> --- a/commit-reach.c
>>>> +++ b/commit-reach.c
>>>> @@ -513,65 +513,88 @@ int commit_contains(struct ref_filter *filter, 
>>>> struct commit *commit,
>>>>return is_descendant_of(commit, list);
>>>>   }
>>>>   
>>>> -int reachable(struct commit *from, int with_flag, int assign_flag,
>>>> -time_t min_commit_date)
>>>> +static int compare_commits_by_gen(const void *_a, const void *_b)
>>>>   {
>>>> -  struct prio_queue work = { compare_commits_by_commit_date };
>>>> +  const struct commit *a = (const struct commit *)_a;
>>>> +  const struct commit *b = (const struct commit *)_b;
>>> This cast is bogus.  QSORT gets handed a struct commit **, i.e. an array
>>> of pointers, and qsort(1) passes references to those pointers to the
>>> compare function, and not the pointer values.
>>
>> Good catch! I'm disappointed that we couldn't use type-checking here, as 
>> it is quite difficult to discover that the types are wrong here.
> 
> Generics in C are hard, and type checking traditionally falls by the
> wayside.  You could use macros for that, like klib [*] does, but that
> has its own downsides (more object text, debugging the sort macros
> themselves is harder).
> 
> [*] https://github.com/attractivechaos/klib/blob/master/ksort.h

We could also do something like this to reduce the amount of manual
casting, but do we want to?  (Macro at the bottom, three semi-random
examples at the top.)
---
 bisect.c  | 11 +++
 commit-graph.c|  9 ++---
 commit-reach.c| 12 +---
 git-compat-util.h | 12 
 4 files changed, 22 insertions(+), 22 deletions(-)

diff --git a/bisect.c b/bisect.c
index e8b17cf7e1..06be3a3c15 100644
--- a/bisect.c
+++ b/bisect.c
@@ -192,16 +192,11 @@ struct commit_dist {
int distance;
 };
 
-static int compare_commit_dist(const void *a_, const void *b_)
-{
-   struct commit_dist *a, *b;
-
-   a = (struct commit_dist *)a_;
-   b = (struct commit_dist *)b_;
+DEFINE_SORT(sort_by_commit_dist, struct commit_dist, a, b, {
if (a->distance != b->distance)
return b->distance - a->distance; /* desc sort */
return oidcmp(>commit->object.oid, >commit->object.oid);
-}
+})
 
 static struct commit_list *best_bisection_sorted(struct commit_list *list, int 
nr)
 {
@@ -223,7 +218,7 @@ static struct commit_list *best_bisection_sorted(struct 
commit_list *list, int n
array[cnt].distance = distance;
cnt++;
}
-   QSORT(array, cnt, compare_commit_dist);
+   sort_by_commit_dist(array, cnt);
for (p = list, i = 0; i < cnt; i++) {
struct object *obj = &(array[i].commit->object);
 
diff --git a/commit-graph.c b/commit-graph.c
index 7f4519ec3b..a2202414e0 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -550,12 +550,7 @@ static void write_graph_chunk_large_edges(struct hashfile 
*f,
}
 }
 
-static int commit_compare(const void *_a, const void *_b)
-{
-   const struct object_id *a = (const struct object_id *)_a;
-   const struct object_id *b = (const struct object_id *)_b;
-   return oidcmp(a, b);
-}
+DEFINE_SORT(sort_oids, struct object_id, a, b, return oidcmp(a, b))
 
 struct packed_commit_list {
struct commit **list;
@@ -780,7 +775,7 @@ void write_commit_graph(const char *obj_dir,
 
close_reachable();
 
-   QSORT(oids.list, oids.nr, commit_compare);
+   sort_oids(oids.list, oids.nr);
 
count_distinct = 1;
for (i = 1; i < oids.nr; i++) {
diff --git a/commit-reach.c b/commit-reach.c
index 2f5e592d16..3aef47c3dd 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -527,17 +527,15 @@ int commit_contains(struct ref_filter *filter, struct 
commit *commit,
return is_descendant_of(commit, list);
 }
 
-static int compare_commits_by_gen(const void *_a, const void *_b)
-{
-   const struct commit *a = *(const struct commit * const *)_a;
-   const struct commit *b = *(const struct commit * const *)_b;
-
+DEFINE_SORT(sort_commits_by_gen, struct commit *, ap, bp, {
+   const struct commit *a = *ap;
+   const struct commit *b = *bp;
if (a->generation < b->generation)
return -1;
if (a->generation > b->generation)
return 1;
return 0;
-}
+})
 
 int can_all_from_reach_with_flag(struct object_arra

Re: [PATCH v3 2/5] fetch-pack: load tip_oids eagerly iff needed

[René Scharfe]

Am 04.10.2018 um 23:38 schrieb Jonathan Tan:
>> Determine if the oidset needs to be populated upfront and then do that
>> instead.  This duplicates a loop, but simplifies the existing one by
>> separating concerns between the two.
> 
> [snip]
> 
>> +if (strict) {
>> +for (i = 0; i < nr_sought; i++) {
>> +ref = sought[i];
>> +if (!is_unmatched_ref(ref))
>> +continue;
>> +
>> +add_refs_to_oidset(_oids, unmatched);
>> +add_refs_to_oidset(_oids, newlist);
>> +break;
>> +}
>> +}
>> +
>>  /* Append unmatched requests to the list */
>>  for (i = 0; i < nr_sought; i++) {
>>  ref = sought[i];
>>  if (!is_unmatched_ref(ref))
>>  continue;
>>  
>> -if ((allow_unadvertised_object_request &
>> - (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1)) ||
>> -tip_oids_contain(_oids, unmatched, newlist,
>> - >old_oid)) {
>> +if (!strict || oidset_contains(_oids, >old_oid)) {
>>  ref->match_status = REF_MATCHED;
>>  *newtail = copy_ref(ref);
>>  newtail = &(*newtail)->next;
> 
> I don't think the concerns are truly separated - the first loop quoted
> needs to know that in the second loop, tip_oids is accessed only if
> there is at least one unmatched ref.

Right, the two loops are still closely related, but only the first one
is concerned with loading refs.

For a true separation we could first build a list of unmatched refs and
then loop through that instead of `sought`.  Not sure if that's better,
but maybe the overhead I imagine it would introduce isn't all that big.

> Would it be better to expose the
> size of the oidset and then use it in place of
> "tip_oids->map.map.tablesize"? Checking for initialization (using
> "tablesize") is conceptually different from checking the size, but in
> this code, both initialization and the first increase in size occur upon
> the first oidset_insert(), so we should still get the same result.

It would work in practice.  If there are no refs to load then it would
try to load those zero refs for each unmatched ref, which shouldn't
really be a problem, but I still find it a wee bit sloppy.  Too
theoretical?

René

[PATCH 5/5] oidset: uninline oidset_init()

[René Scharfe]

There is no need to inline oidset_init(), as it's typically only called
twice in the lifetime of an oidset (once at the beginning and at the end
by oidset_clear()) and kh_resize_* is quite big, so move its definition
to oidset.c.  Document it while we're at it.

Signed-off-by: Rene Scharfe 
---
 oidset.c |  7 +++
 oidset.h | 13 +++--
 2 files changed, 14 insertions(+), 6 deletions(-)

diff --git a/oidset.c b/oidset.c
index 9836d427ef..fe4eb921df 100644
--- a/oidset.c
+++ b/oidset.c
@@ -1,6 +1,13 @@
 #include "cache.h"
 #include "oidset.h"
 
+void oidset_init(struct oidset *set, size_t initial_size)
+{
+   memset(>set, 0, sizeof(set->set));
+   if (initial_size)
+   kh_resize_oid(>set, initial_size);
+}
+
 int oidset_contains(const struct oidset *set, const struct object_id *oid)
 {
khiter_t pos = kh_get_oid(>set, *oid);
diff --git a/oidset.h b/oidset.h
index 4b90540cd4..c9d0f6d3cc 100644
--- a/oidset.h
+++ b/oidset.h
@@ -38,12 +38,13 @@ struct oidset {
 #define OIDSET_INIT { { 0 } }
 
 
-static inline void oidset_init(struct oidset *set, size_t initial_size)
-{
-   memset(>set, 0, sizeof(set->set));
-   if (initial_size)
-   kh_resize_oid(>set, initial_size);
-}
+/**
+ * Initialize the oidset structure `set`.
+ *
+ * If `initial_size` is bigger than 0 then preallocate to allow inserting
+ * the specified number of elements without further allocations.
+ */
+void oidset_init(struct oidset *set, size_t initial_size);
 
 /**
  * Returns true iff `set` contains `oid`.
-- 
2.19.0

[PATCH v3 4/5] oidset: use khash

[René Scharfe]

Reimplement oidset using khash.h in order to reduce its memory footprint
and make it faster.

Performance of a command that mainly checks for duplicate objects using
an oidset, with master and Clang 6.0.1:

  $ cmd="./git-cat-file --batch-all-objects --unordered --buffer 
--batch-check='%(objectname)'"

  $ /usr/bin/time $cmd >/dev/null
  0.22user 0.03system 0:00.25elapsed 99%CPU (0avgtext+0avgdata 
48484maxresident)k
  0inputs+0outputs (0major+11204minor)pagefaults 0swaps

  $ hyperfine "$cmd"
  Benchmark #1: ./git-cat-file --batch-all-objects --unordered --buffer 
--batch-check='%(objectname)'

Time (mean ± σ): 250.0 ms ±   6.0 ms[User: 225.9 ms, System: 23.6 
ms]

Range (min … max):   242.0 ms … 261.1 ms

And with this patch:

  $ /usr/bin/time $cmd >/dev/null
  0.14user 0.00system 0:00.15elapsed 100%CPU (0avgtext+0avgdata 
41396maxresident)k
  0inputs+0outputs (0major+8318minor)pagefaults 0swaps

  $ hyperfine "$cmd"
  Benchmark #1: ./git-cat-file --batch-all-objects --unordered --buffer 
--batch-check='%(objectname)'

Time (mean ± σ): 151.9 ms ±   4.9 ms[User: 130.5 ms, System: 21.2 
ms]

Range (min … max):   148.2 ms … 170.4 ms

Initial-patch-by: Jeff King 
Signed-off-by: Rene Scharfe 
---
 oidset.c | 34 --
 oidset.h | 36 
 2 files changed, 40 insertions(+), 30 deletions(-)

diff --git a/oidset.c b/oidset.c
index 454c54f933..9836d427ef 100644
--- a/oidset.c
+++ b/oidset.c
@@ -3,38 +3,28 @@
 
 int oidset_contains(const struct oidset *set, const struct object_id *oid)
 {
-   if (!set->map.map.tablesize)
-   return 0;
-   return !!oidmap_get(>map, oid);
+   khiter_t pos = kh_get_oid(>set, *oid);
+   return pos != kh_end(>set);
 }
 
 int oidset_insert(struct oidset *set, const struct object_id *oid)
 {
-   struct oidmap_entry *entry;
-
-   if (!set->map.map.tablesize)
-   oidmap_init(>map, 0);
-   else if (oidset_contains(set, oid))
-   return 1;
-
-   entry = xmalloc(sizeof(*entry));
-   oidcpy(>oid, oid);
-
-   oidmap_put(>map, entry);
-   return 0;
+   int added;
+   kh_put_oid(>set, *oid, );
+   return !added;
 }
 
 int oidset_remove(struct oidset *set, const struct object_id *oid)
 {
-   struct oidmap_entry *entry;
-
-   entry = oidmap_remove(>map, oid);
-   free(entry);
-
-   return (entry != NULL);
+   khiter_t pos = kh_get_oid(>set, *oid);
+   if (pos == kh_end(>set))
+   return 0;
+   kh_del_oid(>set, pos);
+   return 1;
 }
 
 void oidset_clear(struct oidset *set)
 {
-   oidmap_free(>map, 1);
+   kh_release_oid(>set);
+   oidset_init(set, 0);
 }
diff --git a/oidset.h b/oidset.h
index 40ec5f87fe..4b90540cd4 100644
--- a/oidset.h
+++ b/oidset.h
@@ -1,7 +1,8 @@
 #ifndef OIDSET_H
 #define OIDSET_H
 
-#include "oidmap.h"
+#include "hashmap.h"
+#include "khash.h"
 
 /**
  * This API is similar to sha1-array, in that it maintains a set of object ids
@@ -15,19 +16,33 @@
  *  table overhead.
  */
 
+static inline unsigned int oid_hash(struct object_id oid)
+{
+   return sha1hash(oid.hash);
+}
+
+static inline int oid_equal(struct object_id a, struct object_id b)
+{
+   return oideq(, );
+}
+
+KHASH_INIT(oid, struct object_id, int, 0, oid_hash, oid_equal)
+
 /**
  * A single oidset; should be zero-initialized (or use OIDSET_INIT).
  */
 struct oidset {
-   struct oidmap map;
+   kh_oid_t set;
 };
 
-#define OIDSET_INIT { OIDMAP_INIT }
+#define OIDSET_INIT { { 0 } }
 
 
 static inline void oidset_init(struct oidset *set, size_t initial_size)
 {
-   oidmap_init(>map, initial_size);
+   memset(>set, 0, sizeof(set->set));
+   if (initial_size)
+   kh_resize_oid(>set, initial_size);
 }
 
 /**
@@ -58,19 +73,24 @@ int oidset_remove(struct oidset *set, const struct 
object_id *oid);
 void oidset_clear(struct oidset *set);
 
 struct oidset_iter {
-   struct oidmap_iter m_iter;
+   kh_oid_t *set;
+   khiter_t iter;
 };
 
 static inline void oidset_iter_init(struct oidset *set,
struct oidset_iter *iter)
 {
-   oidmap_iter_init(>map, >m_iter);
+   iter->set = >set;
+   iter->iter = kh_begin(iter->set);
 }
 
 static inline struct object_id *oidset_iter_next(struct oidset_iter *iter)
 {
-   struct oidmap_entry *e = oidmap_iter_next(>m_iter);
-   return e ? >oid : NULL;
+   for (; iter->iter != kh_end(iter->set); iter->iter++) {
+   if (kh_exist(iter->set, iter->iter))
+   return _key(iter->set, iter->iter++);
+   }
+   return NULL;
 }
 
 static inline struct object_id *oidset_iter_first(struct oidset *set,
-- 
2.19.0

[PATCH v3 3/5] khash: factor out kh_release_*

[René Scharfe]

Add a function for releasing the khash-internal allocations, but not the
khash structure itself.  It can be used with on-stack khash structs.

Signed-off-by: Rene Scharfe 
---
1 tab = 4 spaces here.

 khash.h | 9 +++--
 1 file changed, 7 insertions(+), 2 deletions(-)

diff --git a/khash.h b/khash.h
index 07b4cc2e67..d10caa0c35 100644
--- a/khash.h
+++ b/khash.h
@@ -82,11 +82,16 @@ static const double __ac_HASH_UPPER = 0.77;
SCOPE kh_##name##_t *kh_init_##name(void) { 
\
return (kh_##name##_t*)xcalloc(1, sizeof(kh_##name##_t));   
\
}   
\
+   SCOPE void kh_release_##name(kh_##name##_t *h)  
\
+   {   
\
+   free(h->flags); 
\
+   free((void *)h->keys);  
\
+   free((void *)h->vals);  
\
+   }   
\
SCOPE void kh_destroy_##name(kh_##name##_t *h)  
\
{   
\
if (h) {
\
-   free((void *)h->keys); free(h->flags);  
\
-   free((void *)h->vals);  
\
+   kh_release_##name(h);   
\
free(h);
\
}   
\
}   
\
-- 
2.19.0

[PATCH v3 2/5] fetch-pack: load tip_oids eagerly iff needed

[René Scharfe]

tip_oids_contain() lazily loads refs into an oidset at its first call.
It abuses the internal (sub)member .map.tablesize of that oidset to
check if it has done that already.

Determine if the oidset needs to be populated upfront and then do that
instead.  This duplicates a loop, but simplifies the existing one by
separating concerns between the two.

Signed-off-by: Rene Scharfe 
---
 fetch-pack.c | 36 +++-
 1 file changed, 15 insertions(+), 21 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 3b317952f0..53914563b5 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -526,23 +526,6 @@ static void add_refs_to_oidset(struct oidset *oids, struct 
ref *refs)
oidset_insert(oids, >old_oid);
 }
 
-static int tip_oids_contain(struct oidset *tip_oids,
-   struct ref *unmatched, struct ref *newlist,
-   const struct object_id *id)
-{
-   /*
-* Note that this only looks at the ref lists the first time it's
-* called. This works out in filter_refs() because even though it may
-* add to "newlist" between calls, the additions will always be for
-* oids that are already in the set.
-*/
-   if (!tip_oids->map.map.tablesize) {
-   add_refs_to_oidset(tip_oids, unmatched);
-   add_refs_to_oidset(tip_oids, newlist);
-   }
-   return oidset_contains(tip_oids, id);
-}
-
 static int is_unmatched_ref(const struct ref *ref)
 {
struct object_id oid;
@@ -563,6 +546,8 @@ static void filter_refs(struct fetch_pack_args *args,
struct ref *ref, *next;
struct oidset tip_oids = OIDSET_INIT;
int i;
+   int strict = !(allow_unadvertised_object_request &
+  (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1));
 
i = 0;
for (ref = *refs; ref; ref = next) {
@@ -599,16 +584,25 @@ static void filter_refs(struct fetch_pack_args *args,
}
}
 
+   if (strict) {
+   for (i = 0; i < nr_sought; i++) {
+   ref = sought[i];
+   if (!is_unmatched_ref(ref))
+   continue;
+
+   add_refs_to_oidset(_oids, unmatched);
+   add_refs_to_oidset(_oids, newlist);
+   break;
+   }
+   }
+
/* Append unmatched requests to the list */
for (i = 0; i < nr_sought; i++) {
ref = sought[i];
if (!is_unmatched_ref(ref))
continue;
 
-   if ((allow_unadvertised_object_request &
-(ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1)) ||
-   tip_oids_contain(_oids, unmatched, newlist,
->old_oid)) {
+   if (!strict || oidset_contains(_oids, >old_oid)) {
ref->match_status = REF_MATCHED;
*newtail = copy_ref(ref);
newtail = &(*newtail)->next;
-- 
2.19.0

[PATCH v3 1/5] fetch-pack: factor out is_unmatched_ref()

[René Scharfe]

Move the code to determine if a request is unmatched to its own little
helper.  This allows us to reuse it in a subsequent patch.

Signed-off-by: Rene Scharfe 
---
 fetch-pack.c | 19 +++
 1 file changed, 11 insertions(+), 8 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 75047a4b2a..3b317952f0 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -543,6 +543,16 @@ static int tip_oids_contain(struct oidset *tip_oids,
return oidset_contains(tip_oids, id);
 }
 
+static int is_unmatched_ref(const struct ref *ref)
+{
+   struct object_id oid;
+   const char *p;
+   return  ref->match_status == REF_NOT_MATCHED &&
+   !parse_oid_hex(ref->name, , ) &&
+   *p == '\0' &&
+   oideq(, >old_oid);
+}
+
 static void filter_refs(struct fetch_pack_args *args,
struct ref **refs,
struct ref **sought, int nr_sought)
@@ -591,15 +601,8 @@ static void filter_refs(struct fetch_pack_args *args,
 
/* Append unmatched requests to the list */
for (i = 0; i < nr_sought; i++) {
-   struct object_id oid;
-   const char *p;
-
ref = sought[i];
-   if (ref->match_status != REF_NOT_MATCHED)
-   continue;
-   if (parse_oid_hex(ref->name, , ) ||
-   *p != '\0' ||
-   !oideq(, >old_oid))
+   if (!is_unmatched_ref(ref))
continue;
 
if ((allow_unadvertised_object_request &
-- 
2.19.0

Re: [PATCH v2 2/2] oidset: use khash

[René Scharfe]

Am 04.10.2018 um 08:48 schrieb Jeff King:
> On Thu, Oct 04, 2018 at 07:56:44AM +0200, René Scharfe wrote:
> 
>>> As the comment above notes, I think we're really looking at the case
>>> where this gets populated on the first call, but not subsequent ones. It
>>> might be less hacky to use a "static int initialized" here. Or if we
>>> want to avoid hidden globals, put the logic into filter_refs() to decide
>>> when to populate.
>>
>> Right.  I'd prefer the latter, but was unable to find a nice way that
>> still populates the oidset lazily.  It's certainly worth another look,
>> and a separate series.
> 
> It's a little awkward because the lazy load happens in a conditional.
> You can fully encapsulate it like the patch below, but I actually don't
> think it's really helping readability.

*Shudder*

>>> It might be nice if these functions could hide inside oidset.c (and just
>>> declare the struct here). It looks like we might be able to do that with
>>> __KHASH_TYPE(), but the double-underscore implies that we're not
>>> supposed to. ;)
>>>
>>> I guess we also use a few of them in our inlines here. I'm not 100% sure
>>> that oidset_* needs to be inlined either, but this is at least a pretty
>>> faithful conversion of the original.
>>
>> We could inline all of the oidset functions, following the spirit of
>> klib/khash.h.
>>
>> Or we could uninline all of them and then may be able to clean up
>> oidset.h by using KHASH_DECLARE.  Perhaps we'd need to guard with an
>> "#ifndef THIS_IS_OIDSET_C" or similar to avoid a clash with KHASH_INIT.
>>
>> Not sure if any of that would be a worthwhile improvement..
> 
> Unless we know something is a performance win to inline, I'd generally
> prefer not to.

Agreed.

> For a case like this with auto-generated functions, I'm mostly worried
> about bloating the compiled code. Either with a bunch of inlined
> non-trivial functions, or cases where the compiler says "this is too big
> to inline" and generates an anonymous file-scope function, but we end up
> with a bunch of duplicates, because we're generating the same functions
> in a bunch of C files.

The _iter_ functions look harmless in this regard, as the only use small
functions that are not even type-specific.

oidset_init() would better be moved to oidset.c, as the code for resizing
is quite big.

René

[PATCH v3 0/5] oidset: use khash

[René Scharfe]

Two new patches to avoid using oidset internals in fetch-pack:

  fetch-pack: factor out is_unmatched_ref()
  fetch-pack: load tip_oids eagerly iff needed

Unchanged patch:

  khash: factor out kh_release_*

Unchanged, except it doesn't touch fetch-pack anymore:

  oidset: use khash

A new patch, to reduce object text size:

  oidset: uninline oidset_init()

 fetch-pack.c | 49 +++--
 khash.h  |  9 +++--
 oidset.c | 41 +++--
 oidset.h | 43 ---
 4 files changed, 81 insertions(+), 61 deletions(-)

-- 
2.19.0

Re: [PATCH v2 2/2] oidset: use khash

[René Scharfe]

Am 03.10.2018 um 21:40 schrieb Jeff King:
> On Wed, Oct 03, 2018 at 03:16:39PM +0200, René Scharfe wrote:
>> diff --git a/fetch-pack.c b/fetch-pack.c
>> index 75047a4b2a..a839315726 100644
>> --- a/fetch-pack.c
>> +++ b/fetch-pack.c
>> @@ -536,7 +536,7 @@ static int tip_oids_contain(struct oidset *tip_oids,
>>   * add to "newlist" between calls, the additions will always be for
>>   * oids that are already in the set.
>>   */
>> -if (!tip_oids->map.map.tablesize) {
>> +if (!tip_oids->set.n_buckets) {
>>  add_refs_to_oidset(tip_oids, unmatched);
>>  add_refs_to_oidset(tip_oids, newlist);
>>  }
> 
> This is a little intimate with the implementation of khash, but I think
> it's probably OK (and really no worse than what was there before).
> 
> As the comment above notes, I think we're really looking at the case
> where this gets populated on the first call, but not subsequent ones. It
> might be less hacky to use a "static int initialized" here. Or if we
> want to avoid hidden globals, put the logic into filter_refs() to decide
> when to populate.

Right.  I'd prefer the latter, but was unable to find a nice way that
still populates the oidset lazily.  It's certainly worth another look,
and a separate series.

>> diff --git a/oidset.h b/oidset.h
>> index 40ec5f87fe..4b90540cd4 100644
>> --- a/oidset.h
>> +++ b/oidset.h
>> [...]
>> +KHASH_INIT(oid, struct object_id, int, 0, oid_hash, oid_equal)
> 
> This will declare these "static inline". Our other major "macros become
> inline functions" code is commit-slab.h, and there we found it necessary
> to add MAYBE_UNUSED. I wonder if we ought to be doing the same here (I
> don't get any warnings, but I suspect sparse might complain).

I doubt it (but didn't check) because khash.h defines kh_clear_##name(),
which we don't use it anywhere and there have been no complaints so far.
And if we wanted to add MAYBE_UNUSED then the right place for that would
be in KHASH_INIT, no?

> It might be nice if these functions could hide inside oidset.c (and just
> declare the struct here). It looks like we might be able to do that with
> __KHASH_TYPE(), but the double-underscore implies that we're not
> supposed to. ;)
> 
> I guess we also use a few of them in our inlines here. I'm not 100% sure
> that oidset_* needs to be inlined either, but this is at least a pretty
> faithful conversion of the original.

We could inline all of the oidset functions, following the spirit of
klib/khash.h.

Or we could uninline all of them and then may be able to clean up
oidset.h by using KHASH_DECLARE.  Perhaps we'd need to guard with an
"#ifndef THIS_IS_OIDSET_C" or similar to avoid a clash with KHASH_INIT.

Not sure if any of that would be a worthwhile improvement..

René

[PATCH v2 2/2] oidset: use khash

[René Scharfe]

Reimplement oidset using khash.h in order to reduce its memory footprint
and make it faster.

Performance of a command that mainly checks for duplicate objects using
an oidset, with master and Clang 6.0.1:

  $ cmd="./git-cat-file --batch-all-objects --unordered --buffer 
--batch-check='%(objectname)'"

  $ /usr/bin/time $cmd >/dev/null
  0.22user 0.03system 0:00.25elapsed 99%CPU (0avgtext+0avgdata 
48484maxresident)k
  0inputs+0outputs (0major+11204minor)pagefaults 0swaps

  $ hyperfine "$cmd"
  Benchmark #1: ./git-cat-file --batch-all-objects --unordered --buffer 
--batch-check='%(objectname)'

Time (mean ± σ): 250.0 ms ±   6.0 ms[User: 225.9 ms, System: 23.6 
ms]

Range (min … max):   242.0 ms … 261.1 ms

And with this patch:

  $ /usr/bin/time $cmd >/dev/null
  0.14user 0.00system 0:00.15elapsed 100%CPU (0avgtext+0avgdata 
41396maxresident)k
  0inputs+0outputs (0major+8318minor)pagefaults 0swaps

  $ hyperfine "$cmd"
  Benchmark #1: ./git-cat-file --batch-all-objects --unordered --buffer 
--batch-check='%(objectname)'

Time (mean ± σ): 151.9 ms ±   4.9 ms[User: 130.5 ms, System: 21.2 
ms]

Range (min … max):   148.2 ms … 170.4 ms

Initial-patch-by: Jeff King 
Signed-off-by: Rene Scharfe 
---
 fetch-pack.c |  2 +-
 oidset.c | 34 --
 oidset.h | 36 
 3 files changed, 41 insertions(+), 31 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 75047a4b2a..a839315726 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -536,7 +536,7 @@ static int tip_oids_contain(struct oidset *tip_oids,
 * add to "newlist" between calls, the additions will always be for
 * oids that are already in the set.
 */
-   if (!tip_oids->map.map.tablesize) {
+   if (!tip_oids->set.n_buckets) {
add_refs_to_oidset(tip_oids, unmatched);
add_refs_to_oidset(tip_oids, newlist);
}
diff --git a/oidset.c b/oidset.c
index 454c54f933..9836d427ef 100644
--- a/oidset.c
+++ b/oidset.c
@@ -3,38 +3,28 @@
 
 int oidset_contains(const struct oidset *set, const struct object_id *oid)
 {
-   if (!set->map.map.tablesize)
-   return 0;
-   return !!oidmap_get(>map, oid);
+   khiter_t pos = kh_get_oid(>set, *oid);
+   return pos != kh_end(>set);
 }
 
 int oidset_insert(struct oidset *set, const struct object_id *oid)
 {
-   struct oidmap_entry *entry;
-
-   if (!set->map.map.tablesize)
-   oidmap_init(>map, 0);
-   else if (oidset_contains(set, oid))
-   return 1;
-
-   entry = xmalloc(sizeof(*entry));
-   oidcpy(>oid, oid);
-
-   oidmap_put(>map, entry);
-   return 0;
+   int added;
+   kh_put_oid(>set, *oid, );
+   return !added;
 }
 
 int oidset_remove(struct oidset *set, const struct object_id *oid)
 {
-   struct oidmap_entry *entry;
-
-   entry = oidmap_remove(>map, oid);
-   free(entry);
-
-   return (entry != NULL);
+   khiter_t pos = kh_get_oid(>set, *oid);
+   if (pos == kh_end(>set))
+   return 0;
+   kh_del_oid(>set, pos);
+   return 1;
 }
 
 void oidset_clear(struct oidset *set)
 {
-   oidmap_free(>map, 1);
+   kh_release_oid(>set);
+   oidset_init(set, 0);
 }
diff --git a/oidset.h b/oidset.h
index 40ec5f87fe..4b90540cd4 100644
--- a/oidset.h
+++ b/oidset.h
@@ -1,7 +1,8 @@
 #ifndef OIDSET_H
 #define OIDSET_H
 
-#include "oidmap.h"
+#include "hashmap.h"
+#include "khash.h"
 
 /**
  * This API is similar to sha1-array, in that it maintains a set of object ids
@@ -15,19 +16,33 @@
  *  table overhead.
  */
 
+static inline unsigned int oid_hash(struct object_id oid)
+{
+   return sha1hash(oid.hash);
+}
+
+static inline int oid_equal(struct object_id a, struct object_id b)
+{
+   return oideq(, );
+}
+
+KHASH_INIT(oid, struct object_id, int, 0, oid_hash, oid_equal)
+
 /**
  * A single oidset; should be zero-initialized (or use OIDSET_INIT).
  */
 struct oidset {
-   struct oidmap map;
+   kh_oid_t set;
 };
 
-#define OIDSET_INIT { OIDMAP_INIT }
+#define OIDSET_INIT { { 0 } }
 
 
 static inline void oidset_init(struct oidset *set, size_t initial_size)
 {
-   oidmap_init(>map, initial_size);
+   memset(>set, 0, sizeof(set->set));
+   if (initial_size)
+   kh_resize_oid(>set, initial_size);
 }
 
 /**
@@ -58,19 +73,24 @@ int oidset_remove(struct oidset *set, const struct 
object_id *oid);
 void oidset_clear(struct oidset *set);
 
 struct oidset_iter {
-   struct oidmap_iter m_iter;
+   kh_oid_t *set;
+   khiter_t iter;
 };
 
 static inline void oidset_iter_init(struct oidset *set,
struct oidset_iter *iter)
 {
-   oidmap_iter_init(>map, >m_iter);
+   iter->set = >set;
+   iter->iter = kh_begin(iter->set);
 }
 
 static inline struct object_id *oidset_iter_next(struct oidset_iter *iter)
 {
-   struct oidmap_entry *e = 

[PATCH v2 1/2] khash: factor out kh_release_*

[René Scharfe]

Add a function for releasing the khash-internal allocations, but not the
khash structure itself.  It can be used with on-stack khash structs.

Signed-off-by: Rene Scharfe 
---
1 tab = 4 spaces here.

 khash.h | 9 +++--
 1 file changed, 7 insertions(+), 2 deletions(-)

diff --git a/khash.h b/khash.h
index 07b4cc2e67..d10caa0c35 100644
--- a/khash.h
+++ b/khash.h
@@ -82,11 +82,16 @@ static const double __ac_HASH_UPPER = 0.77;
SCOPE kh_##name##_t *kh_init_##name(void) { 
\
return (kh_##name##_t*)xcalloc(1, sizeof(kh_##name##_t));   
\
}   
\
+   SCOPE void kh_release_##name(kh_##name##_t *h)  
\
+   {   
\
+   free(h->flags); 
\
+   free((void *)h->keys);  
\
+   free((void *)h->vals);  
\
+   }   
\
SCOPE void kh_destroy_##name(kh_##name##_t *h)  
\
{   
\
if (h) {
\
-   free((void *)h->keys); free(h->flags);  
\
-   free((void *)h->vals);  
\
+   kh_release_##name(h);   
\
free(h);
\
}   
\
}   
\
-- 
2.19.0

[PATCH v2 0/2] oidset: use khash

[René Scharfe]

Continue the discussion of speeding up oidset started in [1] here in
its own thread.

[1] https://public-inbox.org/git/20180811172350.ga2...@sigill.intra.peff.net/

The first patch does a mild refactoring to support khash structures
on the stack, and the second one converts oidset to khash.

  khash: factor out kh_release_*
  oidset: use khash

 fetch-pack.c |  2 +-
 khash.h  |  9 +++--
 oidset.c | 34 --
 oidset.h | 36 
 4 files changed, 48 insertions(+), 33 deletions(-)

-- 
2.19.0

[PATCH] sequencer: use return value of oidset_insert()

[René Scharfe]

oidset_insert() returns 1 if the object ID is already in the set and
doesn't add it again, or 0 if it hadn't been present.  Make use of that
fact instead of checking with an extra oidset_contains() call.

Signed-off-by: Rene Scharfe 
---
 sequencer.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)

diff --git a/sequencer.c b/sequencer.c
index ddb41a62d9..6387c9ee6e 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -4146,9 +4146,7 @@ static int make_script_with_merges(struct 
pretty_print_context *pp,
struct object_id *oid = >item->object.oid;
if (!oidset_contains(, oid))
continue;
-   if (!oidset_contains(_seen, oid))
-   oidset_insert(_seen, oid);
-   else
+   if (oidset_insert(_seen, oid))
label_oid(oid, "branch-point", );
}
 
-- 
2.19.0

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

[René Scharfe]

Am 01.10.2018 um 22:26 schrieb Jeff King:
> On Mon, Oct 01, 2018 at 09:15:53PM +0200, René Scharfe wrote:
> The reason hashmap.c was added was to avoid open addressing. ;)
Because efficient removal of elements is easier to implement with
chaining, according to 6a364ced49 (add a hashtable implementation that
supports O(1) removal).  khash.h deletes using its flags bitmap.  We
didn't compare their performance when entries are removed so far.

> So yeah, I think it could perhaps be improved, but in my mind talking
> about "hashmap.c" is fundamentally talking about chained buckets.

Admittedly I wouldn't touch hashmap.c, as I find its interface too
complex to wrap my head around.  But perhaps I just didn't try hard
enough, yet.

>> But I like how khash.h is both already in the tree and also really easy
>> to deploy, as it's just a single header file.  It's a tasty low-hanging
>> fruit.
> 
> Yeah. And if it really does perform better, I think we should stick with
> it in the code base. I wonder if we could stand to clean up the
> interfaces a little.  E.g., I had a hard time declaring a hash in one
> place, and then defining it somewhere else.

You can't use KHASH_DECLARE and KHASH_INIT together, as both declare
the same structs.  So I guess the idea is to have a header file with
KHASH_DECLARE and a .c file with KHASH_INIT, the latter *not* including
the former, but both including khash.h.  I didn't actually try that,
though.

> And I think as you found
> that it insists on heap-allocating the hash-table struct itself, which
> does not match our usual style.

Perhaps we can fix that with little effort (see below).

>> This is straight-forward, except for oidset_clear(), which needs to
>> allocate a kh_oid_t on the heap in order to be able to feed it to
>> kh_destroy_oid() for release it.  Alternatively we could open-code the
>> relevant parts of the latter, but that would be a layering violation.
> 
> This is kind of a layering violation, too. You're assuming that struct
> assignment is sufficient to make one kh struct freeable from another
> pointer. That's probably reasonable, since you're just destroying them
> both (e.g., some of our FLEX structs point into their own struct memory,
> making a hidden dependency; but they obviously would not need to free
> such a field).

Fair enough.  How about this on top?  (The khash.h part would go in
first in a separate patch in a proper series.)

NB: I stuck to the 4-spaces-tabs formatting in khash.h here.

---
 khash.h  | 9 +++--
 oidset.c | 4 +---
 2 files changed, 8 insertions(+), 5 deletions(-)

diff --git a/khash.h b/khash.h
index 07b4cc2e67..d10caa0c35 100644
--- a/khash.h
+++ b/khash.h
@@ -82,11 +82,16 @@ static const double __ac_HASH_UPPER = 0.77;
SCOPE kh_##name##_t *kh_init_##name(void) { 
\
return (kh_##name##_t*)xcalloc(1, sizeof(kh_##name##_t));   
\
}   
\
+   SCOPE void kh_release_##name(kh_##name##_t *h)  
\
+   {   
\
+   free(h->flags); 
\
+   free((void *)h->keys);  
\
+   free((void *)h->vals);  
\
+   }   
\
SCOPE void kh_destroy_##name(kh_##name##_t *h)  
\
{   
\
if (h) {
\
-   free((void *)h->keys); free(h->flags);  
\
-   free((void *)h->vals);  
\
+   kh

Re: What's cooking in git.git (Sep 2018, #04; Thu, 20)

[René Scharfe]

Am 01.10.2018 um 22:12 schrieb Jeff King:
> On Mon, Oct 01, 2018 at 09:16:07PM +0200, René Scharfe wrote:
> 
>> Am 21.09.2018 um 07:22 schrieb Junio C Hamano:
>>> * cc/delta-islands (2018-08-16) 7 commits
>> [...]
>>> * jk/pack-delta-reuse-with-bitmap (2018-08-21) 6 commits
>>
>> Not sure if it's the interaction of the two topics or if only one of
>> them is to blame, but the result of the merge can dereference a NULL
>> pointer.  Found using Clang's UBSan and t5310.
>>
>> Here's a patch that avoids the issue, but I don't know if it's the
>> right thing to do -- should we rather treat a non-existing base as
>> "not from the same island" instead?
>>
>> And it's certainly ugly -- that condition is complicated enough
>> already.  Splitting it up in a nice way would probably help, but how?
> 
> Perhaps like in 2fa233a554 (pack-objects: handle island check for
> "external" delta base, 2018-09-18)?

Perhaps indeed. ;-)  That patch looks exactly like the fix I wished for,
and then some.  I'm just not fully sure about the added branch for the
combination of the two features, because I don't know either of them in
depth.

René

Re: [PATCH 15/16] commit-reach: make can_all_from_reach... linear

[René Scharfe]

Am 01.10.2018 um 21:26 schrieb Derrick Stolee:
> On 10/1/2018 3:16 PM, René Scharfe wrote:
>> Am 28.06.2018 um 14:31 schrieb Derrick Stolee via GitGitGadget:
>>> diff --git a/commit-reach.c b/commit-reach.c
>>> index c58e50fbb..ac132c8e4 100644
>>> --- a/commit-reach.c
>>> +++ b/commit-reach.c
>>> @@ -513,65 +513,88 @@ int commit_contains(struct ref_filter *filter, struct 
>>> commit *commit,
>>> return is_descendant_of(commit, list);
>>>   }
>>>   
>>> -int reachable(struct commit *from, int with_flag, int assign_flag,
>>> - time_t min_commit_date)
>>> +static int compare_commits_by_gen(const void *_a, const void *_b)
>>>   {
>>> -   struct prio_queue work = { compare_commits_by_commit_date };
>>> +   const struct commit *a = (const struct commit *)_a;
>>> +   const struct commit *b = (const struct commit *)_b;
>> This cast is bogus.  QSORT gets handed a struct commit **, i.e. an array
>> of pointers, and qsort(1) passes references to those pointers to the
>> compare function, and not the pointer values.
> 
> Good catch! I'm disappointed that we couldn't use type-checking here, as 
> it is quite difficult to discover that the types are wrong here.

Generics in C are hard, and type checking traditionally falls by the
wayside.  You could use macros for that, like klib [*] does, but that
has its own downsides (more object text, debugging the sort macros
themselves is harder).

[*] https://github.com/attractivechaos/klib/blob/master/ksort.h

>> diff --git a/commit-reach.c b/commit-reach.c
>> index 00e5ceee6f..2f5e592d16 100644
>> --- a/commit-reach.c
>> +++ b/commit-reach.c
>> @@ -529,8 +529,8 @@ int commit_contains(struct ref_filter *filter, struct 
>> commit *commit,
>>   
>>   static int compare_commits_by_gen(const void *_a, const void *_b)
>>   {
>> -const struct commit *a = (const struct commit *)_a;
>> -const struct commit *b = (const struct commit *)_b;
>> +const struct commit *a = *(const struct commit * const *)_a;
>> +const struct commit *b = *(const struct commit * const *)_b;
> 
> I would expect s/* const */**/ here, but I'm guessing your formulation 
> is a bit extra careful about types.

Yeah, that second const is not necessary, as the dereference in the same
line makes it inconsequential, but I added it to make clear that this
function is really not supposed to write at all..

René

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

[René Scharfe]

Am 28.08.2018 um 01:03 schrieb Jeff King:
> On Sun, Aug 26, 2018 at 01:37:41PM +0200, René Scharfe wrote:
>> So it seems worth it.
> 
> Hmm, that really does. Which is a shame, because I hoped that one day we
> could get rid of the nasty macro-infestation that is khash.h. But it
> really is a lot faster than the alternatives.

Well, we only compare it to hashmap.c here.  There might be better
implementations out there.  Hash tables in plain old C seem to be much
harder to find than e.g. in C++, though.

And then there are several possible variations that affect
performance -- perhaps hashmap.c could be improved by using open
addressing, maybe with Robin Hood hashing, and/or by offering better
support for sets, and/or by having a few macros to allow type
specialization.

But I like how khash.h is both already in the tree and also really easy
to deploy, as it's just a single header file.  It's a tasty low-hanging
fruit.

> Do you want to pick up this topic and carry it forward?

Well, I tried to simplify the implementation as much as possible and
ended up doing the opposite of what I wrote earlier.  Hmm.

The patch below postpones struct allocation until cleanup time, which is
a bit weird.  We can't avoid it fully without reimplementing kh_destroy,
but we can use structs supplied by callers for basically all other
operations.  That avoids NULL checks, and the main benefits of that are
simplicity and safety; performance is not much better without them.

This patch doesn't provide a _count (or _is_empty) method.  It would be
cleaner to have one added as the first step and just change its
implementation when switching to khash, but it's harder than expected
with hashmap.c; doing that later (if at all) is easier.

Using sha1hash instead of open-coding it may seem a bit anachronistic,
but is the best way to document the usage of that pattern (i.e. to
truncate a SHA1 hash to get a shorter one for a hash table).

-- >8 --
Subject: [PATCH] oidset: use khash

Reimplement struct oidset using khash.h in order to reduce its memory
footprint and make it faster.

This is straight-forward, except for oidset_clear(), which needs to
allocate a kh_oid_t on the heap in order to be able to feed it to
kh_destroy_oid() for release it.  Alternatively we could open-code the
relevant parts of the latter, but that would be a layering violation.

Performance of a command that mainly checks for duplicate objects
using an oidset, with master and Clang 6.0.1:

$ cmd="./git-cat-file --batch-all-objects --unordered --buffer 
--batch-check='%(objectname)'"

$ /usr/bin/time $cmd >/dev/null
0.22user 0.03system 0:00.25elapsed 99%CPU (0avgtext+0avgdata 48484maxresident)k
0inputs+0outputs (0major+11204minor)pagefaults 0swaps

$ hyperfine "$cmd"
Benchmark #1: ./git-cat-file --batch-all-objects --unordered --buffer 
--batch-check='%(objectname)'

  Time (mean ± σ): 250.0 ms ±   6.0 ms[User: 225.9 ms, System: 23.6 ms]

  Range (min … max):   242.0 ms … 261.1 ms

And with this patch:

$ /usr/bin/time $cmd >/dev/null
0.14user 0.00system 0:00.15elapsed 100%CPU (0avgtext+0avgdata 41396maxresident)k
0inputs+0outputs (0major+8318minor)pagefaults 0swaps

$ hyperfine "$cmd"
Benchmark #1: ./git-cat-file --batch-all-objects --unordered --buffer 
--batch-check='%(objectname)'

  Time (mean ± σ): 151.9 ms ±   4.9 ms[User: 130.5 ms, System: 21.2 ms]

  Range (min … max):   148.2 ms … 170.4 ms

Initial-patch-by: Jeff King 
Signed-off-by: Rene Scharfe 
---
 fetch-pack.c |  2 +-
 oidset.c | 36 ++--
 oidset.h | 36 
 3 files changed, 43 insertions(+), 31 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 75047a4b2a..a839315726 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -536,7 +536,7 @@ static int tip_oids_contain(struct oidset *tip_oids,
 * add to "newlist" between calls, the additions will always be for
 * oids that are already in the set.
 */
-   if (!tip_oids->map.map.tablesize) {
+   if (!tip_oids->set.n_buckets) {
add_refs_to_oidset(tip_oids, unmatched);
add_refs_to_oidset(tip_oids, newlist);
}
diff --git a/oidset.c b/oidset.c
index 454c54f933..d15b2b7a89 100644
--- a/oidset.c
+++ b/oidset.c
@@ -3,38 +3,30 @@
 
 int oidset_contains(const struct oidset *set, const struct object_id *oid)
 {
-   if (!set->map.map.tablesize)
-   return 0;
-   return !!oidmap_get(>map, oid);
+   khiter_t pos = kh_get_oid(>set, *oid);
+   return pos != kh_end(>set);
 }
 
 int oidset_insert(struct oidset *set, const struct object_id *oid)
 {
-   struct oidmap_entry *entry;
-
-   if (!set->map.map.tablesize)
-   oidmap_init(>map, 0);
-   else if (oidset_contains(set, oid))
-   return 1;
-
-   entry = xmalloc(sizeof(*entry));
-   oidcpy(>o

Re: What's cooking in git.git (Sep 2018, #04; Thu, 20)

[René Scharfe]

Am 21.09.2018 um 07:22 schrieb Junio C Hamano:
> * cc/delta-islands (2018-08-16) 7 commits
>   (merged to 'next' on 2018-08-27 at cf3d7bd93f)
>  + pack-objects: move 'layer' into 'struct packing_data'
>  + pack-objects: move tree_depth into 'struct packing_data'
>  + t5320: tests for delta islands
>  + repack: add delta-islands support
>  + pack-objects: add delta-islands support
>  + pack-objects: refactor code into compute_layer_order()
>  + Add delta-islands.{c,h}
> 
>  Lift code from GitHub to restrict delta computation so that an
>  object that exists in one fork is not made into a delta against
>  another object that does not appear in the same forked repository.

> * jk/pack-delta-reuse-with-bitmap (2018-08-21) 6 commits
>   (merged to 'next' on 2018-08-22 at fc50b59dab)
>  + pack-objects: reuse on-disk deltas for thin "have" objects
>  + pack-bitmap: save "have" bitmap from walk
>  + t/perf: add perf tests for fetches from a bitmapped server
>  + t/perf: add infrastructure for measuring sizes
>  + t/perf: factor out percent calculations
>  + t/perf: factor boilerplate out of test_perf
>  (this branch is used by jk/pack-objects-with-bitmap-fix.)
> 
>  When creating a thin pack, which allows objects to be made into a
>  delta against another object that is not in the resulting pack but
>  is known to be present on the receiving end, the code learned to
>  take advantage of the reachability bitmap; this allows the server
>  to send a delta against a base beyond the "boundary" commit.

Not sure if it's the interaction of the two topics or if only one of
them is to blame, but the result of the merge can dereference a NULL
pointer.  Found using Clang's UBSan and t5310.

Here's a patch that avoids the issue, but I don't know if it's the
right thing to do -- should we rather treat a non-existing base as
"not from the same island" instead?

And it's certainly ugly -- that condition is complicated enough
already.  Splitting it up in a nice way would probably help, but how?

---
 builtin/pack-objects.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index e6316d294d..9abed4a0f0 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -1559,7 +1559,8 @@ static void check_object(struct object_entry *entry)
(base_entry = packlist_find(_pack, base_ref, NULL)) ||
(thin &&
 bitmap_has_sha1_in_uninteresting(bitmap_git, base_ref))) &&
-   in_same_island(>idx.oid, _entry->idx.oid)) {
+   (!base_entry ||
+in_same_island(>idx.oid, _entry->idx.oid))) {
/*
 * If base_ref was set above that means we wish to
 * reuse delta data, and either we found that object in
-- 
2.19.0

Re: [PATCH] grep: provide a noop --recursive option

[René Scharfe]

Am 29.09.2018 um 19:11 schrieb Junio C Hamano:
> I however do not mind if we added "--recursive" with matching
> "--no-recursive", and
> 
>  - made "--recursive" the default (obviously)
> 
>  - made "--no-recursive" a synonym to setting the recursion limit
>to "never recurse"
> 
>  - and made "--recursive" a synonym to setting the recursion limit
>to "infinity".
> 
> That would be more work than this patch.  But if I see "--recursive"
> advertised as a feature, and the command by default goes recursive,
> I do expect to be able to tell it not to recurse.

-- >8 --
Subject: [PATCH] grep: add -r/--[no-]recursive

Recognize -r and --recursive as synonyms for --max-depth=-1 for
compatibility with GNU grep; it's still the default for git grep.

This also adds --no-recursive as synonym for --max-depth=0 for free,
which is welcome for completeness and consistency.

Fix the description for --max-depth, while we're at it -- negative
values other than -1 actually disable recursion, i.e. they are
equivalent to --max-depth=0.

Requested-by: Christoph Berg 
Suggested-by: Junio C Hamano 
Initial-patch-by: Ævar Arnfjörð Bjarmason 
Signed-off-by: Rene Scharfe 
---
 Documentation/git-grep.txt | 11 +--
 builtin/grep.c |  2 ++
 t/t7810-grep.sh| 12 
 3 files changed, 23 insertions(+), 2 deletions(-)

diff --git a/Documentation/git-grep.txt b/Documentation/git-grep.txt
index a3049af1a3..84fe236a8e 100644
--- a/Documentation/git-grep.txt
+++ b/Documentation/git-grep.txt
@@ -18,7 +18,7 @@ SYNOPSIS
   [(-O | --open-files-in-pager) []]
   [-z | --null]
   [ -o | --only-matching ] [-c | --count] [--all-match] [-q | --quiet]
-  [--max-depth ]
+  [--max-depth ] [--[no-]recursive]
   [--color[=] | --no-color]
   [--break] [--heading] [-p | --show-function]
   [-A ] [-B ] [-C ]
@@ -119,11 +119,18 @@ OPTIONS
 
 --max-depth ::
For each  given on command line, descend at most 
-   levels of directories. A negative value means no limit.
+   levels of directories. A value of -1 means no limit.
This option is ignored if  contains active wildcards.
In other words if "a*" matches a directory named "a*",
"*" is matched literally so --max-depth is still effective.
 
+-r::
+--recursive::
+   Same as `--max-depth=-1`; this is the default.
+
+--no-recursive::
+   Same as `--max-depth=0`.
+
 -w::
 --word-regexp::
Match the pattern only at word boundary (either begin at the
diff --git a/builtin/grep.c b/builtin/grep.c
index 601f801158..f6e127f0bc 100644
--- a/builtin/grep.c
+++ b/builtin/grep.c
@@ -811,6 +811,8 @@ int cmd_grep(int argc, const char **argv, const char 
*prefix)
GREP_BINARY_NOMATCH),
OPT_BOOL(0, "textconv", _textconv,
 N_("process binary files with textconv filters")),
+   OPT_SET_INT('r', "recursive", _depth,
+   N_("search in subdirectories (default)"), -1),
{ OPTION_INTEGER, 0, "max-depth", _depth, N_("depth"),
N_("descend at most  levels"), PARSE_OPT_NONEG,
NULL, 1 },
diff --git a/t/t7810-grep.sh b/t/t7810-grep.sh
index be5c1bd553..43aa4161cf 100755
--- a/t/t7810-grep.sh
+++ b/t/t7810-grep.sh
@@ -309,6 +309,8 @@ do
echo ${HC}v:1:vvv
} >expected &&
git grep --max-depth -1 -n -e vvv $H >actual &&
+   test_cmp expected actual &&
+   git grep --recursive -n -e vvv $H >actual &&
test_cmp expected actual
'
 
@@ -317,6 +319,8 @@ do
echo ${HC}v:1:vvv
} >expected &&
git grep --max-depth 0 -n -e vvv $H >actual &&
+   test_cmp expected actual &&
+   git grep --no-recursive -n -e vvv $H >actual &&
test_cmp expected actual
'
 
@@ -327,6 +331,8 @@ do
echo ${HC}v:1:vvv
} >expected &&
git grep --max-depth 0 -n -e vvv $H -- "*" >actual &&
+   test_cmp expected actual &&
+   git grep --no-recursive -n -e vvv $H -- "*" >actual &&
test_cmp expected actual
'
 
@@ -344,6 +350,8 @@ do
echo ${HC}t/v:1:vvv
} >expected &&
git grep --max-depth 0 -n -e vvv $H -- t >actual &&
+   test_cmp expected actual &&
+   git grep --no-recursive -n -e vvv $H -- t >actual &&
test_cmp expected actual
'
 
@@ -353,6 +361,8 @@ do
echo ${HC}v:1:vvv
} >expected &&
git grep --max-depth 0 -n -e vvv $H -- . t >actual &&
+   test_cmp expected actual &&
+   git grep --no-recursive -n -e vvv $H -- . t >actual &&
test_cmp expected actual
'
 
@@ 

Re: [PATCH 15/16] commit-reach: make can_all_from_reach... linear

[René Scharfe]

Am 28.06.2018 um 14:31 schrieb Derrick Stolee via GitGitGadget:
> diff --git a/commit-reach.c b/commit-reach.c
> index c58e50fbb..ac132c8e4 100644
> --- a/commit-reach.c
> +++ b/commit-reach.c
> @@ -513,65 +513,88 @@ int commit_contains(struct ref_filter *filter, struct 
> commit *commit,
>   return is_descendant_of(commit, list);
>  }
>  
> -int reachable(struct commit *from, int with_flag, int assign_flag,
> -   time_t min_commit_date)
> +static int compare_commits_by_gen(const void *_a, const void *_b)
>  {
> - struct prio_queue work = { compare_commits_by_commit_date };
> + const struct commit *a = (const struct commit *)_a;
> + const struct commit *b = (const struct commit *)_b;

This cast is bogus.  QSORT gets handed a struct commit **, i.e. an array
of pointers, and qsort(1) passes references to those pointers to the
compare function, and not the pointer values.

As a result it's unlikely that the array is sorted in the intended
order.  Given that, a silly question: Is sorting even necessary here?

Anyway, the patch below should fix it.

>  
> - prio_queue_put(, from);
> - while (work.nr) {
> - struct commit_list *list;
> - struct commit *commit = prio_queue_get();
> -
> - if (commit->object.flags & with_flag) {
> - from->object.flags |= assign_flag;
> - break;
> - }
> - if (!commit->object.parsed)
> - parse_object(the_repository, >object.oid);
> - if (commit->object.flags & REACHABLE)
> - continue;
> - commit->object.flags |= REACHABLE;
> - if (commit->date < min_commit_date)
> - continue;
> - for (list = commit->parents; list; list = list->next) {
> - struct commit *parent = list->item;
> - if (!(parent->object.flags & REACHABLE))
> - prio_queue_put(, parent);
> - }
> - }
> - from->object.flags |= REACHABLE;
> - clear_commit_marks(from, REACHABLE);
> - clear_prio_queue();
> - return (from->object.flags & assign_flag);
> + if (a->generation < b->generation)
> + return -1;
> + if (a->generation > b->generation)
> + return 1;
> + return 0;
>  }
>  
>  int can_all_from_reach_with_flag(struct object_array *from,
>int with_flag, int assign_flag,
> -  time_t min_commit_date)
> +  time_t min_commit_date,
> +  uint32_t min_generation)
>  {
> + struct commit **list = NULL;
>   int i;
> + int result = 1;
>  
> + ALLOC_ARRAY(list, from->nr);
>   for (i = 0; i < from->nr; i++) {
> - struct object *from_one = from->objects[i].item;
> + list[i] = (struct commit *)from->objects[i].item;
>  
> - if (from_one->flags & assign_flag)
> - continue;
> - from_one = deref_tag(the_repository, from_one, "a from object", 
> 0);
> - if (!from_one || from_one->type != OBJ_COMMIT) {
> - /* no way to tell if this is reachable by
> -  * looking at the ancestry chain alone, so
> -  * leave a note to ourselves not to worry about
> -  * this object anymore.
> -  */
> - from->objects[i].item->flags |= assign_flag;
> - continue;
> - }
> - if (!reachable((struct commit *)from_one, with_flag, 
> assign_flag,
> -min_commit_date))
> + parse_commit(list[i]);
> +
> + if (list[i]->generation < min_generation)
>   return 0;
>   }
> - return 1;
> +
> + QSORT(list, from->nr, compare_commits_by_gen);

-- >8 --
Subject: [PATCH] commit-reach: fix cast in compare_commits_by_gen()

The elements of the array to be sorted are commit pointers, so the
comparison function gets handed references to these pointers, not
pointers to commit objects.  Cast to the right type and dereference
once to correctly get the commit reference.

Found using Clang's ASan and t5500.

Signed-off-by: Rene Scharfe 
---
Has this patch a performance impact?

 commit-reach.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/commit-reach.c b/commit-reach.c
index 00e5ceee6f..2f5e592d16 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -529,8 +529,8 @@ int commit_contains(struct ref_filter *filter, struct 
commit *commit,
 
 static int compare_commits_by_gen(const void *_a, const void *_b)
 {
-   const struct commit *a = (const struct commit *)_a;
-   const struct commit *b = (const struct commit *)_b;
+   const struct commit *a = *(const struct commit * const *)_a;
+   const struct commit *b = *(const struct commit * 

Re: [PATCH v4 8/8] fsck: support comments & empty lines in skipList

[René Scharfe]

Am 28.08.2018 um 11:52 schrieb Ævar Arnfjörð Bjarmason:
> It's annoying not to be able to put comments and empty lines in the
> skipList, when e.g. keeping a big central list of commits to skip in
> /etc/gitconfig, which was my motivation for 1362df0d41 ("fetch:
> implement fetch.fsck.*", 2018-07-27).
> 
> Implement that, and document what version of Git this was changed in,
> since this on-disk format can be expected to be used by multiple
> versions of git.
> 
> There is no notable performance impact from this change, using the
> test setup described a couple of commist back:
> 
> Test HEAD~ HEAD
> 
> 
> 1450.3: fsck with 0 skipped bad commits  7.81(7.42+0.39)   
> 7.72(7.34+0.38) -1.2%
> 1450.5: fsck with 1 skipped bad commits  7.75(7.36+0.38)   
> 7.66(7.26+0.39) -1.2%
> 1450.7: fsck with 10 skipped bad commits 7.81(7.43+0.38)   
> 7.70(7.30+0.39) -1.4%
> 1450.9: fsck with 100 skipped bad commits7.85(7.42+0.42)   
> 7.73(7.31+0.41) -1.5%
> 1450.11: fsck with 1000 skipped bad commits  7.81(7.43+0.38)   
> 7.84(7.46+0.38) +0.4%
> 1450.13: fsck with 1 skipped bad commits 7.87(7.47+0.40)   
> 7.86(7.46+0.40) -0.1%
> 1450.15: fsck with 10 skipped bad commits7.77(7.39+0.38)   
> 7.83(7.48+0.34) +0.8%
> 1450.17: fsck with 100 skipped bad commits   7.17(6.92+0.24)   
> 7.11(6.85+0.26) -0.8%
> 
> Signed-off-by: Ævar Arnfjörð Bjarmason 
> ---
>  Documentation/config.txt| 4 ++--
>  fsck.c  | 2 ++
>  t/t5504-fetch-receive-strict.sh | 6 +++---
>  3 files changed, 7 insertions(+), 5 deletions(-)
> 
> diff --git a/Documentation/config.txt b/Documentation/config.txt
> index ebaa044689..824634c412 100644
> --- a/Documentation/config.txt
> +++ b/Documentation/config.txt
> @@ -1712,8 +1712,8 @@ will only cause git to warn.
>  fsck.skipList::
>   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. Comments ('#') and empty lines are not supported, and
> - will error out.
> + be ignored. On versions of Git 2.20 and later comments ('#') and empty
> + lines are ignored, but will error out on older versions.
>  +
>  This feature is useful when an established project should be accepted
>  despite early commits containing errors that can be safely ignored
> diff --git a/fsck.c b/fsck.c
> index 4c643f1d40..589548308a 100644
> --- a/fsck.c
> +++ b/fsck.c
> @@ -190,6 +190,8 @@ static void init_skiplist(struct fsck_options *options, 
> const char *path)
>   die("Could not open skip list: %s", path);
>   while (!strbuf_getline(, fp)) {
>   const char *p;
> + if (!strcmp(sb.buf, "") || starts_with(sb.buf, "#"))
> + continue;

Checking sb.len == 0 is simpler and might be slightly quicker.

But what is an empty line?  Shouldn't whitespace-only lines qualify?
And why not allow trailing comments, while we're at it?  I.e. what
about something like this instead?

const char *hash = strchr(sb.buf, '#);
if (hash)
strbuf_setlen(, hash - sb.buf);
strbuf_rtrim();
if (!sb.len)
continue;

Too much?

>   if (parse_oid_hex(sb.buf, , ) || *p != '\0')
>   die("Invalid SHA-1: %s", sb.buf);
>   oidset_insert(>skiplist, );
> diff --git a/t/t5504-fetch-receive-strict.sh b/t/t5504-fetch-receive-strict.sh
> index c7224db3bb..a1bac164d1 100755
> --- a/t/t5504-fetch-receive-strict.sh
> +++ b/t/t5504-fetch-receive-strict.sh
> @@ -169,20 +169,20 @@ test_expect_success 'fsck with invalid or bogus 
> skipList input' '
>   test_i18ngrep "Invalid SHA-1: \[core\]" err
>  '
>  
> -test_expect_success 'fsck with invalid or bogus skipList input (comments & 
> empty lines)' '
> +test_expect_success 'fsck with other accepted skipList input (comments & 
> empty lines)' '
>   cat >SKIP.with-comment <<-EOF &&
>   # Some bad commit
>   0001
>   EOF
>   test_must_fail git -c fsck.skipList=SKIP.with-comment fsck 
> 2>err-with-comment &&
> - test_i18ngrep "^fatal: Invalid SHA-1: # Some bad commit$" 
> err-with-comment &&
> + test_i18ngrep "missingEmail" err-with-comment &&
>   cat >SKIP.with-empty-line <<-EOF &&
>   0001
>  
>   0002
>   EOF
>   test_must_fail git -c fsck.skipList=SKIP.with-empty-line fsck 
> 2>err-with-empty-line &&
> - test_i18ngrep "^fatal: Invalid SHA-1: " err-with-empty-line
> + test_i18ngrep "missingEmail" err-with-empty-line
>  '
>  
>  test_expect_success 'fsck no garbage output from comments & empty 

Re: [PATCH v3 6/7] fsck: use oidset for skiplist

[René Scharfe]

Am 27.08.2018 um 22:15 schrieb Ævar Arnfjörð Bjarmason:
> 
> On Mon, Aug 27 2018, Ævar Arnfjörð Bjarmason wrote:
> 
>> From: René Scharfe 
>>
>> Object IDs to skip are stored in a shared static oid_array.  Lookups do
>> a binary search on the sorted array.  The code checks if the object IDs
>> are already in the correct order while loading and skips sorting in that
>> case.  Lookups are done before reporting a (non-fatal) corruption and
>> before checking .gitmodules files.
>>
>> Simplify the code by using an oidset instead.  Memory usage is a bit
>> higher, but we don't need to worry about any sort order anymore.  Embed
>> the oidset into struct fsck_options to make its ownership clear (no
>> hidden sharing) and avoid unnecessary pointer indirection.
>>
>> Performance on repositories with a low number of reported issues and
>> .gitmodules files (i.e. the usual case) won't be affected much.  The
>> oidset should be a bit quicker with higher numbers of bad objects in
>> the skipList.
> 
> I didn't change this commit message at all, but FWIW this still has me
> somewhat confused. What is the interaction with .gitmodules being
> described here? You also mentioned it in
> https://public-inbox.org/git/113aa2d7-6f66-8d03-dda4-7337cda9b...@web.de/
> (but I don't get that either)

The skipList is consulted before checking .gitmodules blobs, since
fb16287719 (fsck: check skiplist for object in fsck_blob()).

> Does that just mean that when cloning with --recursive with
> transfer.fsckObjects=true we'll re-read the file for each "clone"
> invocation, both for the main project and everything listed in
> .gitmodules?

That is probably true, but I didn't mean that.  I was only talking
about when an object is looked up in the skiplist (oid_array/oidset).

> If so, I think something like this commit message would be clearer:
> 
> fsck: use oidset instead of oid_array for skipList
> 
> Change the implementation of the skipList feature to use oidset
> instead of oid_array to store SHA-1s for later lookup.
> 
> This list is parsed once on startup by fsck, fetch-pack or
> receive-pack depending on the *.skipList config in use, so for fetch
> it's currently re-parsed for each submodule fetch.

OK; the patch doesn't change that, though.  Mentioning it sound like
a good idea if the load takes a significant amount of time -- I
didn't measure this separately, so perhaps this needs to be explored
further if people use big skipLists.

> Memory usage is a bit higher, but we don't need to keep track of the
> sort order anymore. Embed the oidset into struct fsck_options to
> make its ownership clear (no hidden sharing) and avoid unnecessary
> pointer indirection.
> 
> Then let's just attach the test program you wrote in
> https://public-inbox.org/git/113aa2d7-6f66-8d03-dda4-7337cda9b...@web.de/
> and note the results and let them speak for themselves.

I was surprised that such a big repo can be mocked up relatively
quickly, but the numbers are a bit underwhelming -- there is not a
lot of change.  The script is not too expensive, so I don't mind
adding it.

> I can do all that if that seems fine to you. I also notice that the test
> case only sets up a case where all the items on the skip list are bad
> commits in the repo, it would be interesting to test with a few needles
> in a large haystack (I can modify it to do that...).

I tried something like this first, and its results are even more
boring.  Since skipList lookups are done only for bad objects (and
.gitmodules) you won't see  any difference at all.  Having only bad
objects is the edge case, this test being designed to highlight the
performance of the skipList implementation.

René

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

[René Scharfe]

Am 27.08.2018 um 09:37 schrieb Ævar Arnfjörð Bjarmason:
> 
> On Sat, Aug 25 2018, René Scharfe wrote:
> 
>> 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.` and 
>> `fetch.fsck.`
>>  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...
> 
>> -if (options->skiplist)
>> -sorted = options->skiplist->sorted;
>> -else {
>> -sorted = 1;
>> -options->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, , ) || *p != '\0')
>>  die("Invalid SHA-1: %s", sb.buf);
>> -oid_array_append(, );
>> -if (sorted && skiplist.nr > 1 &&
>> -oidcmp([skiplist.nr - 2],
>> -   ) > 0)
>> -sorted = 0;
>> +oidset_insert(>skiplist, );
> 
> ...reading this implementation, where we always called
> oid_array_append(), but then just kept track of whether the set was
> sorted...
> 
>>  }
>>  if (ferror(fp))
>>  die_errno("Could not read '%s'", path);
>>  fclose(fp);
>>  strbuf_release();
>> -
>> -if (sorted)
>> -skiplist.sorted = 1;
> 
> ...and here where we assigned to the .sorted member of the oid_array...
> 
>>  static int object_on_skiplist(struct fsck_options *opts, struct object *obj)
>>  {
>> -if (opts && opts->skiplist && obj)
>> -return oid_array_lookup(opts->skiplist, >oid) >= 0;
>> -return 0;
>> +return opts && obj && oidset_contains(>skiplist, >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/Document

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

[René Scharfe]

Am 14.08.2018 um 03:58 schrieb Jeff King:
> Your suggestion can be implemented using khash (my patch below).
> 
>> Before:
>> Benchmark #1: ./git-cat-file --batch-all-objects --buffer --unordered 
>> --batch-check='%(objectname)'
>>
>>   Time (mean ± σ): 269.5 ms ±  26.7 ms[User: 247.7 ms, System: 21.4 
>> ms]
>>
>>   Range (min … max):   240.3 ms … 339.3 ms
>>
>> After:
>> Benchmark #1: ./git-cat-file --batch-all-objects --buffer --unordered 
>> --batch-check='%(objectname)'
>>
>>   Time (mean ± σ): 224.2 ms ±  18.2 ms[User: 201.7 ms, System: 22.1 
>> ms]
>>
>>   Range (min … max):   205.0 ms … 259.0 ms
> 
> Yeah. My best-of-five dropped from 300ms to 247ms. That 300 was using
> the memory pool, though khash's deletion strategy isn't all that
> different (the wasted memory hangs around until the next hash resize,
> but if you're evenly dropping and adding, you likely won't need to
> resize).

With your khash patch:

Benchmark #1: ./git-cat-file --batch-all-objects --buffer --unordered 
--batch-check='%(objectname)'

  Time (mean ± σ): 159.1 ms ±  20.5 ms[User: 140.3 ms, System: 18.5 ms]

  Range (min … max):   140.0 ms … 214.0 ms

So it seems worth it.

> Anyway, here's the khash patch for reference.
> 
> diff --git a/fetch-pack.c b/fetch-pack.c
> index 5714bcbddd..5a86b10a5e 100644
> --- a/fetch-pack.c
> +++ b/fetch-pack.c
> @@ -534,7 +534,7 @@ static int tip_oids_contain(struct oidset *tip_oids,
>* add to "newlist" between calls, the additions will always be for
>* oids that are already in the set.
>*/
> - if (!tip_oids->map.map.tablesize) {
> + if (!tip_oids->map) {
>   add_refs_to_oidset(tip_oids, unmatched);
>   add_refs_to_oidset(tip_oids, newlist);
>   }

The caller shouldn't look at the private parts of the implementation
like this.  tablesize is the allocation count, which becomes non-zero
if at least one entry was added.  tip_oids is only inserted into, never
deleted from, so a count or size function could be used instead as a
cleaner interface.  (In a separate patch..)

> diff --git a/oidset.c b/oidset.c
> index 454c54f933..2964b43b2d 100644
> --- a/oidset.c
> +++ b/oidset.c
> @@ -3,38 +3,44 @@
>  
>  int oidset_contains(const struct oidset *set, const struct object_id *oid)
>  {
> - if (!set->map.map.tablesize)
> + khiter_t pos;
> +
> + if (!set->map)
>   return 0;
> - return !!oidmap_get(>map, oid);
> +
> + pos = kh_get_oid(set->map, *oid);
> + return pos < kh_end(set->map);
>  }
>  
>  int oidset_insert(struct oidset *set, const struct object_id *oid)
>  {
> - struct oidmap_entry *entry;
> + int hash_ret;
>  
> - if (!set->map.map.tablesize)
> - oidmap_init(>map, 0);
> - else if (oidset_contains(set, oid))
> - return 1;
> + if (!set->map)
> + set->map = kh_init_oid();
>  
> - entry = xmalloc(sizeof(*entry));
> - oidcpy(>oid, oid);
> -
> - oidmap_put(>map, entry);
> - return 0;
> + kh_put_oid(set->map, *oid, _ret);
> + return !hash_ret;
>  }

So initialization is deferred to the first insert, and the empty set
can be represented in two ways -- map == NULL and map->size == 0.

I wondered about the performance impact of all those NULL checks at
insert and lookup and converted it to stack storage, with a dirty
hand-rolled oidset_clear() implementation.  It wasn't any faster.

>  
>  int oidset_remove(struct oidset *set, const struct object_id *oid)
>  {
> - struct oidmap_entry *entry;
> + khiter_t pos;
>  
> - entry = oidmap_remove(>map, oid);
> - free(entry);
> + if (!set->map)
> + return 0;
> +
> + pos = kh_get_oid(set->map, *oid);
> + if (pos < kh_end(set->map)) {
> + kh_del_oid(set->map, pos);
> + return 1;
> + }
>  
> - return (entry != NULL);
> + return 0;
>  }
>  
>  void oidset_clear(struct oidset *set)
>  {
> - oidmap_free(>map, 1);
> + kh_destroy_oid(set->map);
> + set->map = NULL;
>  }
> diff --git a/oidset.h b/oidset.h
> index 40ec5f87fe..4c4c5a42fe 100644
> --- a/oidset.h
> +++ b/oidset.h
> @@ -2,6 +2,7 @@
>  #define OIDSET_H
>  
>  #include "oidmap.h"

This can go.

> +#include "khash.h"
>  
>  /**
>   * This API is similar to sha1-array, in that it maintains a set of object 
> ids
> @@ -15,19 +16,34 @@
>   *  table overhead.
>   */
>  
> +static inline unsigned int oid_hash(const struct object_id oid)
> +{
> + unsigned int hash;
> + memcpy(, oid.hash, sizeof(hash));
> + return hash;
> +}
> +
> +static inline int oid_equal(const struct object_id a,
> + const struct object_id b)
> +{
> + return !oidcmp(, );
> +}

Look, it's oideq() from that other series in disguise! :)

> +
> +KHASH_INIT(oid, struct object_id, int, 0, oid_hash, oid_equal)

Note to self: The 0 is for kh_is_map, which means that no values are
kept and the given value type (int) doesn't 

[PATCH] mailinfo: support format=flowed

[René Scharfe]

Add best-effort support for patches sent using format=flowed (RFC 3676).
Remove leading spaces ("unstuff"), remove soft line breaks (indicated
by space + newline), but leave the signature separator (dash dash space
newline) alone.

Warn in git am when encountering a format=flowed patch, because any
trailing spaces would most probably be lost, as the sending MUA is
encouraged to remove them when preparing the email.

Provide a test patch formatted by Mozilla Thunderbird 60 using its
default configuration.  It reuses the contents of the file mailinfo.c
before and after this patch.

Signed-off-by: Rene Scharfe 
---
A test for DelSp=yes would be nice (in a separate patch; this one is
quite big already), but I don't know how to create one.

 builtin/am.c|4 +
 mailinfo.c  |   64 +-
 mailinfo.h  |2 +
 t/t4256-am-format-flowed.sh |   19 +
 t/t4256/1/mailinfo.c| 1245 +++
 t/t4256/1/mailinfo.c.orig   | 1185 +
 t/t4256/1/patch |  129 
 7 files changed, 2646 insertions(+), 2 deletions(-)
 create mode 100755 t/t4256-am-format-flowed.sh
 create mode 100644 t/t4256/1/mailinfo.c
 create mode 100644 t/t4256/1/mailinfo.c.orig
 create mode 100644 t/t4256/1/patch

diff --git a/builtin/am.c b/builtin/am.c
index 9f7ecf6ecb..2a7341cf48 100644
--- a/builtin/am.c
+++ b/builtin/am.c
@@ -1244,6 +1244,10 @@ static int parse_mail(struct am_state *state, const char 
*mail)
fclose(mi.input);
fclose(mi.output);
 
+   if (mi.format_flowed)
+   warning(_("Patch sent with format=flowed; "
+ "space at the end of lines might be lost."));
+
/* Extract message and author information */
fp = xfopen(am_path(state, "info"), "r");
while (!strbuf_getline_lf(, fp)) {
diff --git a/mailinfo.c b/mailinfo.c
index 3281a37d51..b395adbdf2 100644
--- a/mailinfo.c
+++ b/mailinfo.c
@@ -237,11 +237,22 @@ static int slurp_attr(const char *line, const char *name, 
struct strbuf *attr)
return 1;
 }
 
+static int has_attr_value(const char *line, const char *name, const char 
*value)
+{
+   struct strbuf sb = STRBUF_INIT;
+   int rc = slurp_attr(line, name, ) && !strcasecmp(sb.buf, value);
+   strbuf_release();
+   return rc;
+}
+
 static void handle_content_type(struct mailinfo *mi, struct strbuf *line)
 {
struct strbuf *boundary = xmalloc(sizeof(struct strbuf));
strbuf_init(boundary, line->len);
 
+   mi->format_flowed = has_attr_value(line->buf, "format=", "flowed");
+   mi->delsp = has_attr_value(line->buf, "delsp=", "yes");
+
if (slurp_attr(line->buf, "boundary=", boundary)) {
strbuf_insert(boundary, 0, "--", 2);
if (++mi->content_top >= >content[MAX_BOUNDARIES]) {
@@ -964,6 +975,52 @@ static int handle_boundary(struct mailinfo *mi, struct 
strbuf *line)
return 1;
 }
 
+static void handle_filter_flowed(struct mailinfo *mi, struct strbuf *line,
+struct strbuf *prev)
+{
+   size_t len = line->len;
+   const char *rest;
+
+   if (!mi->format_flowed) {
+   handle_filter(mi, line);
+   return;
+   }
+
+   if (line->buf[len - 1] == '\n') {
+   len--;
+   if (len && line->buf[len - 1] == '\r')
+   len--;
+   }
+
+   /* Keep signature separator as-is. */
+   if (skip_prefix(line->buf, "-- ", ) && rest - line->buf == len) {
+   if (prev->len) {
+   handle_filter(mi, prev);
+   strbuf_reset(prev);
+   }
+   handle_filter(mi, line);
+   return;
+   }
+
+   /* Unstuff space-stuffed line. */
+   if (len && line->buf[0] == ' ') {
+   strbuf_remove(line, 0, 1);
+   len--;
+   }
+
+   /* Save flowed line for later, but without the soft line break. */
+   if (len && line->buf[len - 1] == ' ') {
+   strbuf_add(prev, line->buf, len - !!mi->delsp);
+   return;
+   }
+
+   /* Prepend any previous partial lines */
+   strbuf_insert(line, 0, prev->buf, prev->len);
+   strbuf_reset(prev);
+
+   handle_filter(mi, line);
+}
+
 static void handle_body(struct mailinfo *mi, struct strbuf *line)
 {
struct strbuf prev = STRBUF_INIT;
@@ -1012,7 +1069,7 @@ static void handle_body(struct mailinfo *mi, struct 
strbuf *line)
strbuf_addbuf(, sb);
break;
}
-   handle_filter(mi, sb);
+   handle_filter_flowed(mi, sb, );
}
/*
 * The partial chunk is saved in "prev" and will be
@@ -1022,13 +1079,16 @@ static void 

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

[René Scharfe]

Object IDs to skip are stored in a shared static oid_array.  Lookups do
a binary search on the sorted array.  The code checks if the object IDs
are already in the correct order while loading and skips sorting in that
case.  Lookups are done before reporting a (non-fatal) corruption and
before checking .gitmodules files.

Simplify the code by using an oidset instead.  Memory usage is a bit
higher, but we don't need to worry about any sort order anymore.  Embed
the oidset into struct fsck_options to make its ownership clear (no
hidden sharing) and avoid unnecessary pointer indirection.

Performance on repositories with a low number of reported issues and
.gitmodules files (i.e. the usual case) won't be affected much.  The
oidset should be a bit quicker with higher numbers of bad objects in
the skipList.

Helped-by: Ævar Arnfjörð Bjarmason 
Signed-off-by: Rene Scharfe 
---
Added small documentation update.

 Documentation/config.txt |  2 +-
 fsck.c   | 23 ++-
 fsck.h   |  8 +---
 3 files changed, 8 insertions(+), 25 deletions(-)

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.` and 
`fetch.fsck.`
 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
diff --git a/fsck.c b/fsck.c
index 972a26b9ba..4c643f1d40 100644
--- a/fsck.c
+++ b/fsck.c
@@ -10,7 +10,6 @@
 #include "fsck.h"
 #include "refs.h"
 #include "utf8.h"
-#include "sha1-array.h"
 #include "decorate.h"
 #include "oidset.h"
 #include "packfile.h"
@@ -182,19 +181,10 @@ static int fsck_msg_type(enum fsck_msg_id msg_id,
 
 static void init_skiplist(struct fsck_options *options, const char *path)
 {
-   static struct oid_array skiplist = OID_ARRAY_INIT;
-   int sorted;
FILE *fp;
struct strbuf sb = STRBUF_INIT;
struct object_id oid;
 
-   if (options->skiplist)
-   sorted = options->skiplist->sorted;
-   else {
-   sorted = 1;
-   options->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, , ) || *p != '\0')
die("Invalid SHA-1: %s", sb.buf);
-   oid_array_append(, );
-   if (sorted && skiplist.nr > 1 &&
-   oidcmp([skiplist.nr - 2],
-  ) > 0)
-   sorted = 0;
+   oidset_insert(>skiplist, );
}
if (ferror(fp))
die_errno("Could not read '%s'", path);
fclose(fp);
strbuf_release();
-
-   if (sorted)
-   skiplist.sorted = 1;
 }
 
 static int parse_msg_type(const char *str)
@@ -319,9 +302,7 @@ static void append_msg_id(struct strbuf *sb, const char 
*msg_id)
 
 static int object_on_skiplist(struct fsck_options *opts, struct object *obj)
 {
-   if (opts && opts->skiplist && obj)
-   return oid_array_lookup(opts->skiplist, >oid) >= 0;
-   return 0;
+   return opts && obj && oidset_contains(>skiplist, >oid);
 }
 
 __attribute__((format (printf, 4, 5)))
diff --git a/fsck.h b/fsck.h
index 0c7e8c9428..b95595ae5f 100644
--- a/fsck.h
+++ b/fsck.h
@@ -1,6 +1,8 @@
 #ifndef GIT_FSCK_H
 #define GIT_FSCK_H
 
+#include "oidset.h"
+
 #define FSCK_ERROR 1
 #define FSCK_WARN 2
 #define FSCK_IGNORE 3
@@ -35,12 +37,12 @@ struct fsck_options {
fsck_error error_func;
unsigned strict:1;
int *msg_type;
-   struct oid_array *skiplist;
+   struct oidset skiplist;
struct decoration *object_names;
 };
 
-#define FSCK_OPTIONS_DEFAULT { NULL, fsck_error_function, 0, NULL }
-#define FSCK_OPTIONS_STRICT { NULL, fsck_error_function, 1, NULL }
+#define FSCK_OPTIONS_DEFAULT { NULL, fsck_error_function, 0, NULL, OIDSET_INIT 
}
+#define FSCK_OPTIONS_STRICT { NULL, fsck_error_function, 1, NULL, OIDSET_INIT }
 
 /* descend in all linked child objects
  * the return value is:
-- 
2.18.0

[PATCH v2 1/2] fsck: use strbuf_getline() to read skiplist file

[René Scharfe]

buffer is unlikely to contain a NUL character, so printing its contents
using %s in a die() format is unsafe (detected with ASan).

Use an idiomatic strbuf_getline() loop instead, which ensures the buffer
is always NUL-terminated, supports CRLF files as well, accepts files
without a newline after the last line, supports any hash length
automatically, and is shorter.

Helped-by: Jeff King 
Signed-off-by: Rene Scharfe 
---
Added error check.
Hopefully fixed my MUA config..

 fsck.c | 25 -
 1 file changed, 12 insertions(+), 13 deletions(-)

diff --git a/fsck.c b/fsck.c
index a0cee0be59..972a26b9ba 100644
--- a/fsck.c
+++ b/fsck.c
@@ -183,8 +183,9 @@ static int fsck_msg_type(enum fsck_msg_id msg_id,
 static void init_skiplist(struct fsck_options *options, const char *path)
 {
static struct oid_array skiplist = OID_ARRAY_INIT;
-   int sorted, fd;
-   char buffer[GIT_MAX_HEXSZ + 1];
+   int sorted;
+   FILE *fp;
+   struct strbuf sb = STRBUF_INIT;
struct object_id oid;
 
if (options->skiplist)
@@ -194,25 +195,23 @@ static void init_skiplist(struct fsck_options *options, 
const char *path)
options->skiplist = 
}
 
-   fd = open(path, O_RDONLY);
-   if (fd < 0)
+   fp = fopen(path, "r");
+   if (!fp)
die("Could not open skip list: %s", path);
-   for (;;) {
+   while (!strbuf_getline(, fp)) {
const char *p;
-   int result = read_in_full(fd, buffer, sizeof(buffer));
-   if (result < 0)
-   die_errno("Could not read '%s'", path);
-   if (!result)
-   break;
-   if (parse_oid_hex(buffer, , ) || *p != '\n')
-   die("Invalid SHA-1: %s", buffer);
+   if (parse_oid_hex(sb.buf, , ) || *p != '\0')
+   die("Invalid SHA-1: %s", sb.buf);
oid_array_append(, );
if (sorted && skiplist.nr > 1 &&
oidcmp([skiplist.nr - 2],
   ) > 0)
sorted = 0;
}
-   close(fd);
+   if (ferror(fp))
+   die_errno("Could not read '%s'", path);
+   fclose(fp);
+   strbuf_release();
 
if (sorted)
skiplist.sorted = 1;
-- 
2.18.0

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

[René Scharfe]

Am 11.08.2018 um 18:54 schrieb Ævar Arnfjörð Bjarmason:
> 
> On Sat, Aug 11 2018, René Scharfe wrote:
> 
>> Object IDs to skip are stored in a shared static oid_array.  Lookups do
>> a binary search on the sorted array.  The code checks if the object IDs
>> are already in the correct order while loading and skips sorting in that
>> case.
> 
> I think this change makes sense, but it's missing an update to the
> relevant documentation in Documentation/config.txt:
> 
> fsck.skipList::
>   The path to a sorted 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
>   can be safely ignored such as invalid committer email addresses.
>   Note: corrupt objects cannot be skipped with this setting.
> 
> Also, while I use the skipList feature it's for something on the order
> of 10-100 objects, so whatever algorithm the lookup uses isn't going to
> matter, but I think it's interesting to describe the trade-off in the
> commit message.
> 
> I.e. what if I have 100K objects listed in the skipList, is it only
> going to be read lazily during fsck if there's an issue, or on every
> object etc? What's the difference in performance?

The list is loaded once up-front and a lookup is done for each
reportable issue and .gitmodules file.  Repositories without them
won't be affected at all.

100K bad objects sounds a bit extreme, but a fast-import can create
such a repository relatively quickly.  Here are the numbers with and
without the two patches:

Testorigin/master HEAD

1450.3: fsck with 0 skipped bad commits 0.84(0.78+0.05)   
0.83(0.80+0.03) -1.2%
1450.5: fsck with 1 skipped bad commits 0.84(0.77+0.07)   
0.84(0.79+0.05) +0.0%
1450.7: fsck with 10 skipped bad commits0.86(0.81+0.05)   
0.84(0.78+0.06) -2.3%
1450.9: fsck with 100 skipped bad commits   0.85(0.78+0.07)   
0.84(0.78+0.05) -1.2%
1450.11: fsck with 1000 skipped bad commits 0.85(0.80+0.05)   
0.84(0.79+0.05) -1.2%
1450.13: fsck with 1 skipped bad commits0.85(0.78+0.07)   
0.82(0.75+0.06) -3.5%
1450.15: fsck with 10 skipped bad commits   0.73(0.64+0.09)   
0.64(0.62+0.02) -12.3%

They look the same for most sizes, but with all 10 bad objects in
the skiplist the oidset wins decisively.  Dialing it up a notch:

Test origin/master HEAD
-
1450.3: fsck with 0 skipped bad commits  8.61(7.94+0.66)   
8.72(8.14+0.58) +1.3%
1450.5: fsck with 1 skipped bad commits  8.51(7.87+0.63)   
8.53(7.93+0.60) +0.2%
1450.7: fsck with 10 skipped bad commits 8.56(7.98+0.57)   
8.54(7.91+0.63) -0.2%
1450.9: fsck with 100 skipped bad commits8.65(8.00+0.65)   
8.47(7.93+0.53) -2.1%
1450.11: fsck with 1000 skipped bad commits  8.69(8.16+0.53)   
8.49(8.00+0.49) -2.3%
1450.13: fsck with 1 skipped bad commits 8.69(8.13+0.56)   
8.50(7.93+0.56) -2.2%
1450.15: fsck with 10 skipped bad commits8.78(8.18+0.60)   
8.36(7.85+0.50) -4.8%
1450.17: fsck with 100 skipped bad commits   7.83(7.07+0.76)   
6.55(6.42+0.12) -16.3%

So it looks like successful lookups are faster in the oidset and
the oid_array is quicker with just a handful of entries.

A L1 cache line of 64 bytes holds 3 consecutive SHA1 hashes, which
might explain it.

Here's the perf test code:

---
 t/perf/p1450-fsck.sh | 40 
 1 file changed, 40 insertions(+)
 create mode 100755 t/perf/p1450-fsck.sh

diff --git a/t/perf/p1450-fsck.sh b/t/perf/p1450-fsck.sh
new file mode 100755
index 00..7c89690777
--- /dev/null
+++ b/t/perf/p1450-fsck.sh
@@ -0,0 +1,40 @@
+#!/bin/sh
+
+test_description='Test fsck skipList performance'
+
+. ./perf-lib.sh
+
+test_perf_fresh_repo
+
+n=10
+
+test_expect_success "setup $n bad commits" '
+   for i in $(test_seq 1 $n)
+   do
+   echo "commit refs/heads/master" &&
+   echo "committer C  1234567890 +" &&
+   echo "data <skiplist
+   '
+
+   test_perf "fsck with $skip skipped bad commits" '
+   git -c fsck.skipList=skiplist fsck
+   '
+
+   case $skip in
+   0) skip=1 ;;
+   *) skip=${skip}0 ;;
+   esac
+done
+
+test_done
-- 
2.18.0

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

[René Scharfe]

Am 11.08.2018 um 22:48 schrieb Ramsay Jones:
> On 11/08/18 16:47, René Scharfe wrote:
>> @@ -34,12 +36,12 @@ struct fsck_options {
>>  fsck_error error_func;
>>  unsigned strict:1;
>>  int *msg_type;
>> -    struct oid_array *skiplist;
>> +    struct oidset skiplist;
>>  struct decoration *object_names;
>>  };
>>  
>> -#define FSCK_OPTIONS_DEFAULT { NULL, fsck_error_function, 0, NULL }
>> -#define FSCK_OPTIONS_STRICT { NULL, fsck_error_function, 1, NULL }
>> +#define FSCK_OPTIONS_DEFAULT { NULL, fsck_error_function, 0, NULL, 
>> OIDSET_INIT }
>> +#define FSCK_OPTIONS_STRICT { NULL, fsck_error_function, 1, NULL, 
>> OIDSET_INIT }
> 
> Note that a NULL initialiser, for the object_names field, is missing
> (not introduced by this patch). Since you have bumped into the 80th
> column, you may not want to add that NULL to the end of these macros
> (it is not _necessary_ after all). However, ... :-D

Exactly my thoughts -- except the "However" part. :)

I even thought about reordering the struct to move the NULL-initialized
elements to the end, allowing us to drop them from the initializer, but
felt that this would be a bit too much..

René

[PATCH] remote: improve argument help for add --mirror

[René Scharfe]

Group the possible values using a pair of parentheses and don't mark
them for translation, as they are literal strings that have to be used
as-is in any locale.

Signed-off-by: Rene Scharfe 
---
 builtin/remote.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/builtin/remote.c b/builtin/remote.c
index 07bd51f8eb..7876db1c20 100644
--- a/builtin/remote.c
+++ b/builtin/remote.c
@@ -168,7 +168,7 @@ static int add(int argc, const char **argv)
OPT_STRING_LIST('t', "track", , N_("branch"),
N_("branch(es) to track")),
OPT_STRING('m', "master", , N_("branch"), N_("master 
branch")),
-   { OPTION_CALLBACK, 0, "mirror", , N_("push|fetch"),
+   { OPTION_CALLBACK, 0, "mirror", , "(push|fetch)",
N_("set up remote as a mirror to push to or fetch 
from"),
PARSE_OPT_OPTARG | PARSE_OPT_COMP_ARG, parse_mirror_opt 
},
OPT_END()
-- 
2.18.0

[PATCH] parseopt: group literal string alternatives in argument help

[René Scharfe]

This formally clarifies that the "--option=" part is the same for all
alternatives.

Signed-off-by: Rene Scharfe 
---
 builtin/pull.c  | 2 +-
 builtin/push.c  | 4 ++--
 builtin/send-pack.c | 2 +-
 3 files changed, 4 insertions(+), 4 deletions(-)

diff --git a/builtin/pull.c b/builtin/pull.c
index 53bc5facfd..681c127a07 100644
--- a/builtin/pull.c
+++ b/builtin/pull.c
@@ -135,7 +135,7 @@ static struct option pull_options[] = {
/* Options passed to git-merge or git-rebase */
OPT_GROUP(N_("Options related to merging")),
{ OPTION_CALLBACK, 'r', "rebase", _rebase,
- "false|true|merges|preserve|interactive",
+ "(false|true|merges|preserve|interactive)",
  N_("incorporate changes by rebasing rather than merging"),
  PARSE_OPT_OPTARG, parse_opt_rebase },
OPT_PASSTHRU('n', NULL, _diffstat, NULL,
diff --git a/builtin/push.c b/builtin/push.c
index ef4c188895..d09a42062c 100644
--- a/builtin/push.c
+++ b/builtin/push.c
@@ -561,7 +561,7 @@ int cmd_push(int argc, const char **argv, const char 
*prefix)
  0, CAS_OPT_NAME, , N_(":"),
  N_("require old value of ref to be at this value"),
  PARSE_OPT_OPTARG | PARSE_OPT_LITERAL_ARGHELP, 
parseopt_push_cas_option },
-   { OPTION_CALLBACK, 0, "recurse-submodules", 
_submodules, "check|on-demand|no",
+   { OPTION_CALLBACK, 0, "recurse-submodules", 
_submodules, "(check|on-demand|no)",
N_("control recursive pushing of submodules"),
PARSE_OPT_OPTARG, option_parse_recurse_submodules },
OPT_BOOL_F( 0 , "thin", , N_("use thin pack"), 
PARSE_OPT_NOCOMPLETE),
@@ -576,7 +576,7 @@ int cmd_push(int argc, const char **argv, const char 
*prefix)
OPT_BIT(0, "follow-tags", , N_("push missing but relevant 
tags"),
TRANSPORT_PUSH_FOLLOW_TAGS),
{ OPTION_CALLBACK,
- 0, "signed", _cert, "yes|no|if-asked", N_("GPG sign the 
push"),
+ 0, "signed", _cert, "(yes|no|if-asked)", N_("GPG sign 
the push"),
  PARSE_OPT_OPTARG, option_parse_push_signed },
OPT_BIT(0, "atomic", , N_("request atomic transaction on 
remote side"), TRANSPORT_PUSH_ATOMIC),
OPT_STRING_LIST('o', "push-option", _options_cmdline, 
N_("server-specific"), N_("option to transmit")),
diff --git a/builtin/send-pack.c b/builtin/send-pack.c
index 724b484850..8e3c7490f7 100644
--- a/builtin/send-pack.c
+++ b/builtin/send-pack.c
@@ -166,7 +166,7 @@ int cmd_send_pack(int argc, const char **argv, const char 
*prefix)
OPT_BOOL(0, "mirror", _mirror, N_("mirror all refs")),
OPT_BOOL('f', "force", _update, N_("force updates")),
{ OPTION_CALLBACK,
- 0, "signed", _cert, "yes|no|if-asked", N_("GPG sign the 
push"),
+ 0, "signed", _cert, "(yes|no|if-asked)", N_("GPG sign 
the push"),
  PARSE_OPT_OPTARG, option_parse_push_signed },
OPT_STRING_LIST(0, "push-option", _options,
N_("server-specific"),
-- 
2.18.0

[PATCH] checkout-index: improve argument help for --stage

[René Scharfe]

Spell out all alternatives and avoid using a numerical range operator,
as it is not mentioned in CodingGuidelines and the resulting string is
still concise.  Wrap them in parentheses to document clearly that the
"--stage=" part is common among them.

Signed-off-by: Rene Scharfe 
---
 builtin/checkout-index.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/builtin/checkout-index.c b/builtin/checkout-index.c
index a730f6a1aa..92e9d0d69f 100644
--- a/builtin/checkout-index.c
+++ b/builtin/checkout-index.c
@@ -172,7 +172,7 @@ int cmd_checkout_index(int argc, const char **argv, const 
char *prefix)
N_("write the content to temporary files")),
OPT_STRING(0, "prefix", _dir, N_("string"),
N_("when creating files, prepend ")),
-   { OPTION_CALLBACK, 0, "stage", NULL, "1-3|all",
+   { OPTION_CALLBACK, 0, "stage", NULL, "(1|2|3|all)",
N_("copy out the files from named stage"),
PARSE_OPT_NONEG, option_parse_stage },
OPT_END()
-- 
2.18.0

Re: [PATCH 3/4] cat-file: use a single strbuf for all output

[René Scharfe]

Am 14.08.2018 um 20:20 schrieb Jeff King:
> When we're in batch mode, we end up in batch_object_write()
> for each object, which allocates its own strbuf for each
> call. Instead, we can provide a single "scratch" buffer that
> gets reused for each output. When running:
> 
>   git cat-file --batch-all-objects --batch-check='%(objectname)'
> 
> on git.git, my best-of-five time drops from:
> 
>   real0m0.171s
>   user0m0.159s
>   sys 0m0.012s
> 
> to:
> 
>   real0m0.133s
>   user0m0.121s
>   sys 0m0.012s
> 
> Note that we could do this just by putting the "scratch"
> pointer into "struct expand_data", but I chose instead to
> add an extra parameter to the callstack. That's more
> verbose, but it makes it a bit more obvious what is going
> on, which in turn makes it easy to see where we need to be
> releasing the string in the caller (right after the loop
> which uses it in each case).
> 
> Based-on-a-patch-by: René Scharfe 
> Signed-off-by: Jeff King 
> ---
> It also made it easy to see that without the prior patch,
> we'd have been using "buf" for two parameters. :)

Good catch.

> 
>  builtin/cat-file.c | 28 +---
>  1 file changed, 17 insertions(+), 11 deletions(-)
> 
> diff --git a/builtin/cat-file.c b/builtin/cat-file.c
> index 3ed1d0be80..08dced2614 100644
> --- a/builtin/cat-file.c
> +++ b/builtin/cat-file.c
> @@ -338,11 +338,11 @@ static void print_object_or_die(struct batch_options 
> *opt, struct expand_data *d
>   }
>  }
>  
> -static void batch_object_write(const char *obj_name, struct batch_options 
> *opt,
> +static void batch_object_write(const char *obj_name,
> +struct strbuf *scratch,
> +struct batch_options *opt,
>  struct expand_data *data)
>  {
> - struct strbuf buf = STRBUF_INIT;

We could also avoid passing that buffer around by making it static.  I
shy away from adding static variables because the resulting code won't
be thread-safe, but that fear might be irrational, especially with
cat-file.

> -
>   if (!data->skip_object_info &&
>   oid_object_info_extended(the_repository, >oid, >info,
>OBJECT_INFO_LOOKUP_REPLACE) < 0) {
> @@ -352,10 +352,10 @@ static void batch_object_write(const char *obj_name, 
> struct batch_options *opt,
>   return;
>   }
>  
> - strbuf_expand(, opt->format, expand_format, data);
> - strbuf_addch(, '\n');
> - batch_write(opt, buf.buf, buf.len);
> - strbuf_release();
> + strbuf_reset(scratch);
> + strbuf_expand(scratch, opt->format, expand_format, data);
> + strbuf_addch(scratch, '\n');
> + batch_write(opt, scratch->buf, scratch->len);
>  
>   if (opt->print_contents) {
>   print_object_or_die(opt, data);
> @@ -363,7 +363,9 @@ static void batch_object_write(const char *obj_name, 
> struct batch_options *opt,
>   }
>  }
>  
> -static void batch_one_object(const char *obj_name, struct batch_options *opt,
> +static void batch_one_object(const char *obj_name,
> +  struct strbuf *scratch,
> +  struct batch_options *opt,
>struct expand_data *data)
>  {
>   struct object_context ctx;
> @@ -405,20 +407,21 @@ static void batch_one_object(const char *obj_name, 
> struct batch_options *opt,
>   return;
>   }
>  
> - batch_object_write(obj_name, opt, data);
> + batch_object_write(obj_name, scratch, opt, data);
>  }
>  
>  struct object_cb_data {
>   struct batch_options *opt;
>   struct expand_data *expand;
>   struct oidset *seen;
> + struct strbuf *scratch;
>  };
>  
>  static int batch_object_cb(const struct object_id *oid, void *vdata)
>  {
>   struct object_cb_data *data = vdata;
>   oidcpy(>expand->oid, oid);
> - batch_object_write(NULL, data->opt, data->expand);
> + batch_object_write(NULL, data->scratch, data->opt, data->expand);
>   return 0;
>  }
>  
> @@ -509,6 +512,7 @@ static int batch_objects(struct batch_options *opt)
>  
>   cb.opt = opt;
>   cb.expand = 
> + cb.scratch = 
>  
>   if (opt->unordered) {
>   struct oidset seen = OIDSET_INIT;
> @@ -531,6 +535,7 @@ static int batch_objects(struct batch_options *opt)
>   oid_array_clear();
>   }
>  
> + strbuf_release();
>   return 0;
>   }
>  
> @@ -559,10 +564,11 @@ static int batch_objects(struct batch_options *opt)
>   data.rest = p;
>   }
>  
> - batch_one_object(input.buf, opt, );
> + batch_one_object(input.buf, , opt, );
>   }
>  
>   strbuf_release();
> + strbuf_release();
>   warn_on_object_refname_ambiguity = save_warning;
>   return retval;
>  }
> 

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

[René Scharfe]

Am 13.08.2018 um 23:07 schrieb Junio C Hamano:
> René Scharfe  writes:
> 
>> the mailing list [1], nor on the web interface [2].  The latter shows
>> extra spaces on the context lines of the first hunk, though, which I
>> can't see anywhere else.  All the lines look fine in the citation of
>> Ramsay's reply [3].  So I don't know where these extra spaces are
>> coming from. :-/
> 
> Hmph, interesting.
> 
> https://public-inbox.org/git/54a5367f-f832-402c-f51b-3225c92b4...@web.de/raw
> 
> has "Content-Type: text/plain; charset=utf-8; format=flowed".  That
> page's rendition is more faithful to the bare text.

That explains it: Thunderbird 60 disables most older Add-ons, among them
Toggle Word Wrap, which used to turn off format=flowed for me.  I did
that now using the config settings mailnews.send_plaintext_flowed and
mailnews.display.disable_format_flowed_support.

> The funky " -" one I showed was what Gnus/Emacs came up with as the
> result of its best effort to make the format=flawed into something
> closer to "text", I think X-<.  

Sorry. :(

> In any case, I do not think format=flowed can be reverted reliably
> (or can it be?  If so we should teach mailinfo to repair them).

RFC3676 gives me a headache, perhaps I should go to bed.  If we can
assume that lines don't have trailing spaces originally then we should
be able to reconstruct their contents, no?  "A generating agent SHOULD:
[...] Trim spaces before user-inserted hard line breaks.", i.e. lines
with trailing spaces are doomed to truncation without hope for repair.

René

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

[René Scharfe]

Am 13.08.2018 um 20:43 schrieb Junio C Hamano:

René Scharfe  writes:


@@ -182,19 +181,10 @@ static int fsck_msg_type(enum fsck_msg_id msg_id,
  static void init_skiplist(struct fsck_options *options, const char
*path)
  {
-   static struct oid_array skiplist = OID_ARRAY_INIT;
-   int sorted;
FILE *fp;
struct strbuf sb = STRBUF_INIT;
struct object_id oid;
  - if (options->skiplist)
-   sorted = options->skiplist->sorted;
-   else {


That SP before '-' on the removed line is the most curious aspect of
this patch; I do not recall the last time I saw a corrupt patch from
you---changed where you read/write your mails recently?


Well, I updated Thunderbird to version 60 a few days ago, but I can't
see that extra space in my Sent folder, nor via the NNTP interface of
the mailing list [1], nor on the web interface [2].  The latter shows
extra spaces on the context lines of the first hunk, though, which I
can't see anywhere else.  All the lines look fine in the citation of
Ramsay's reply [3].  So I don't know where these extra spaces are
coming from. :-/

René


[1] news://news.public-inbox.org:119/54a5367f-f832-402c-f51b-3225c92b4...@web.de
[2] https://public-inbox.org/git/54a5367f-f832-402c-f51b-3225c92b4...@web.de/
[3] 
https://public-inbox.org/git/bc9f21c6-b362-2e3f-1820-7da93a76a...@ramsayjones.plus.com/

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

[René Scharfe]

Am 11.08.2018 um 22:59 schrieb René Scharfe:

If the current oidset implementation is so bad, why not replace it with
one based on oid_array? ;-)

Intuitively I'd try a hashmap with no payload and open addressing via
sha1hash(), which should reduce memory allocations quite a bit -- no
need to store hash codes and next pointers, only an array of object IDs
with a fill rate of 50% or so.  Deletions are a bit awkward with that
scheme, though; they could perhaps be implemented as insertions into a
second hashmap.


Here's roughly what I had in mind, only with a free/occupied bitmap (or
a one-bit payload, if you will).  I tried a variant that encoded empty
slots as null_oid first, which has lower memory usage, but isn't any
faster than the current code.

# in git.git
$ hyperfine "./git-cat-file --batch-all-objects --buffer --unordered 
--batch-check='%(objectname)'"

Before:
Benchmark #1: ./git-cat-file --batch-all-objects --buffer --unordered 
--batch-check='%(objectname)'

  Time (mean ± σ): 269.5 ms ±  26.7 ms[User: 247.7 ms, System: 21.4 ms]

  Range (min … max):   240.3 ms … 339.3 ms

After:
Benchmark #1: ./git-cat-file --batch-all-objects --buffer --unordered 
--batch-check='%(objectname)'

  Time (mean ± σ): 224.2 ms ±  18.2 ms[User: 201.7 ms, System: 22.1 ms]

  Range (min … max):   205.0 ms … 259.0 ms

So that's only slightly faster. :-|

---
 builtin/cat-file.c | 93 +++---
 1 file changed, 88 insertions(+), 5 deletions(-)

diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index 45992c9be9..b197cca861 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -408,10 +408,93 @@ static void batch_one_object(const char *obj_name, struct 
batch_options *opt,
batch_object_write(obj_name, opt, data);
 }
 
+struct oidset2 {

+   size_t nr, alloc;
+   struct object_id *entries;
+   uint32_t *bitmap;
+};
+
+static int is_bit_set(const uint32_t *bitmap, size_t idx)
+{
+   uint32_t mask = 1 << (idx % bitsizeof(bitmap[0]));
+   return bitmap[idx / bitsizeof(bitmap[0])] & mask;
+}
+
+static void set_bit(uint32_t *bitmap, size_t idx)
+{
+   uint32_t mask = 1 << (idx % bitsizeof(bitmap[0]));
+   bitmap[idx / bitsizeof(bitmap[0])] |= mask;
+}
+
+static void oidset2_add(struct oidset2 *set, const struct object_id *oid)
+{
+   size_t idx;
+
+   for (idx = sha1hash(oid->hash) % set->alloc;;) {
+   if (!is_bit_set(set->bitmap, idx))
+   break;
+   if (!oidcmp(>entries[idx], oid))
+   return;
+   if (++idx >= set->alloc)
+   idx = 0;
+   }
+   oidcpy(>entries[idx], oid);
+   set_bit(set->bitmap, idx);
+   set->nr++;
+}
+
+static void oidset2_grow(struct oidset2 *set)
+{
+   struct oidset2 old_set = *set;
+   size_t idx;
+
+   set->alloc = (old_set.alloc + 1000) * 3 / 2;
+   set->nr = 0;
+   set->entries = xcalloc(set->alloc, sizeof(set->entries[0]));
+   set->bitmap = xcalloc(set->alloc / 32 + 1, sizeof(set->bitmap[0]));
+   for (idx = 0; idx < old_set.alloc; idx++) {
+   if (!is_bit_set(old_set.bitmap, idx))
+   continue;
+   oidset2_add(set, _set.entries[idx]);
+   }
+   free(old_set.entries);
+   free(old_set.bitmap);
+}
+
+static void oidset2_insert(struct oidset2 *set, const struct object_id *oid)
+{
+   if (set->nr + 1 > set->alloc * 2 / 3)
+   oidset2_grow(set);
+   oidset2_add(set, oid);
+}
+
+static int oidset2_contains(struct oidset2 *set, const struct object_id *oid)
+{
+   size_t idx;
+
+   if (!set->nr)
+   return 0;
+   for (idx = sha1hash(oid->hash) % set->alloc;;) {
+   if (!is_bit_set(set->bitmap, idx))
+   return 0;
+   if (!oidcmp(>entries[idx], oid))
+   return 1;
+   if (++idx >= set->alloc)
+   idx = 0;
+   }
+}
+
+static void oidset2_clear(struct oidset2 *set)
+{
+   FREE_AND_NULL(set->entries);
+   FREE_AND_NULL(set->bitmap);
+   set->alloc = set->nr = 0;
+}
+
 struct object_cb_data {
struct batch_options *opt;
struct expand_data *expand;
-   struct oidset *seen;
+   struct oidset2 *seen;
 };
 
 static int batch_object_cb(const struct object_id *oid, void *vdata)

@@ -443,9 +526,9 @@ static int batch_unordered_object(const struct object_id 
*oid, void *vdata)
 {
struct object_cb_data *data = vdata;
 
-	if (oidset_contains(data->seen, oid))

+   if (oidset2_contains(data->seen, oid))
return 0;
-   oidset_insert(data->seen, oid);
+   oidset2_insert(data->seen, oid);
 
 	return batch_object_cb(oid, data);

 }
@@ -510,7 +593,7 @@ static int batch_objects(struct

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

[René Scharfe]

Am 11.08.2018 um 19:23 schrieb Jeff King:

On Sat, Aug 11, 2018 at 01:02:48PM -0400, Jeff King wrote:


   - we could probably improve the speed of oidset. Two things I notice
 about its implementation:

   - it has to malloc for each entry, which I suspect is the main
bottleneck. We could probably pool-allocate blocks, and when
entries get removed just leave the allocations in place until we
clear(). Most callers tend to build up a set and then query it a
lot, or possibly remove items from the set until it's empty. But
my guess is that few or none want a long-lived set that they add
and remove from randomly.

   - insertion lets you do check-and-insert as a single operation
(something I failed to notice in [1]). But it's not implemented
as efficiently as it could be, since the "contains" and "put"
operations do separate lookups. This doesn't matter for a set
that's queried a lot more, but for something like de-duping
(like I was doing in [1]) most operations are check-and-insert.
[...]
[1] https://public-inbox.org/git/20180810232457.gg19...@sigill.intra.peff.net/
 but note that it's buried pretty deep.


Some notes on this, based on the cat-file patch that I linked to.

Before any optimizations, my best-of-five timing for:

   git cat-file --batch-all-objects --unordered --buffer \
--batch-check='%(objectname)' >/dev/null

in git.git was:

   real 0m0.434s
   user 0m0.414s
   sys  0m0.020s

That's enumerating every object in the repo but not doing much more than
de-duping the names and printing them.

Applying this patch:

diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index 45992c9be9..04b5cda191 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -443,9 +443,8 @@ static int batch_unordered_object(const struct object_id 
*oid, void *vdata)
  {
struct object_cb_data *data = vdata;
  
-	if (oidset_contains(data->seen, oid))

+   if (oidset_insert(data->seen, oid))
return 0;
-   oidset_insert(data->seen, oid);
  
  	return batch_object_cb(oid, data);

  }

to use the single-call set-and-replace doesn't seem to help (any
improvement is within the run-to-run noise). So a single hash lookup per
object does not seem to be measurable. And thus teaching oidset_insert()
to do a single hash lookup for check-and-insert is unlikely to help us.

On top of that, I tried using a pool to store the set entries:

diff --git a/oidset.c b/oidset.c
index 454c54f933..504929f177 100644
--- a/oidset.c
+++ b/oidset.c
@@ -17,7 +17,10 @@ int oidset_insert(struct oidset *set, const struct object_id 
*oid)
else if (oidset_contains(set, oid))
return 1;
  
-	entry = xmalloc(sizeof(*entry));

+   if (!set->pool)
+   mem_pool_init(>pool, 0);
+
+   entry = mem_pool_alloc(set->pool, sizeof(*entry));
oidcpy(>oid, oid);
  
  	oidmap_put(>map, entry);

@@ -29,12 +32,13 @@ int oidset_remove(struct oidset *set, const struct 
object_id *oid)
struct oidmap_entry *entry;
  
  	entry = oidmap_remove(>map, oid);

-   free(entry);
+   /* abandon pool memory for "entry" */
  
  	return (entry != NULL);

  }
  
  void oidset_clear(struct oidset *set)

  {
-   oidmap_free(>map, 1);
+   oidmap_free(>map, 0);
+   mem_pool_discard(set->pool, 0);
  }
diff --git a/oidset.h b/oidset.h
index 40ec5f87fe..6b8b802987 100644
--- a/oidset.h
+++ b/oidset.h
@@ -20,6 +20,7 @@
   */
  struct oidset {
struct oidmap map;
+   struct mem_pool *pool;
  };
  
  #define OIDSET_INIT { OIDMAP_INIT }


That drops my best-of-five to:

   real 0m0.300s
   user 0m0.288s
   sys  0m0.012s

which is over a 25% speedup. So that does seem worth pursuing.

For reference, the oid_array code path for cat-file is still:

   real 0m0.161s
   user 0m0.157s
   sys  0m0.004s

but that's not completely apples to apples. The oidset code is also
iterating the packfiles in a different order and generating a revidx
(which I know is about 25ms in this repo). So a better test would
actually swap one data structure out for the other with no other changes
(I just happened to have this test handy, and really wanted to know
whether the mem_pool stuff would help).


Getting sidetracked here, but the following patch helps both sides a bit:

-- >8 --
Subject: [PATCH] cat-file: reuse strbuf in batch_object_write()

Avoid allocating and then releasing memory for constructing the output
for each object by reusing the strbuf for all of them.

Signed-off-by: Rene Scharfe 
---
# on git.git
$ hyperfine "./git-cat-file --batch-all-objects --buffer 
--batch-check='%(objectname)'"

Before:
Benchmark #1: ./git-cat-file --batch-all-objects --buffer 
--batch-check='%(objectname)'

  Time (mean ± σ): 139.3 ms ±  20.1 ms[User: 124.2 ms, System: 14.8 ms]

  Range (min … max):   124.4 ms … 205.9 ms

After:
Benchmark #1: ./git-cat-file --batch-all-objects 

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

[René Scharfe]

Am 11.08.2018 um 19:23 schrieb Jeff King:

On Sat, Aug 11, 2018 at 01:02:48PM -0400, Jeff King wrote:


   - we could probably improve the speed of oidset. Two things I notice
 about its implementation:



Before any optimizations, my best-of-five timing for:

   git cat-file --batch-all-objects --unordered --buffer \
--batch-check='%(objectname)' >/dev/null

in git.git was:

   real 0m0.434s
   user 0m0.414s
   sys  0m0.020s

That's enumerating every object in the repo but not doing much more than
de-duping the names and printing them.



So a single hash lookup per
object does not seem to be measurable. And thus teaching oidset_insert()
to do a single hash lookup for check-and-insert is unlikely to help us.



On top of that, I tried using a pool to store the set entries:



That drops my best-of-five to:

   real 0m0.300s
   user 0m0.288s
   sys  0m0.012s

which is over a 25% speedup. So that does seem worth pursuing.



For reference, the oid_array code path for cat-file is still:

   real 0m0.161s
   user 0m0.157s
   sys  0m0.004s

but that's not completely apples to apples. The oidset code is also
iterating the packfiles in a different order and generating a revidx
(which I know is about 25ms in this repo). So a better test would
actually swap one data structure out for the other with no other changes
(I just happened to have this test handy, and really wanted to know
whether the mem_pool stuff would help).


If the current oidset implementation is so bad, why not replace it with
one based on oid_array? ;-)

Intuitively I'd try a hashmap with no payload and open addressing via
sha1hash(), which should reduce memory allocations quite a bit -- no
need to store hash codes and next pointers, only an array of object IDs
with a fill rate of 50% or so.  Deletions are a bit awkward with that
scheme, though; they could perhaps be implemented as insertions into a
second hashmap.

Balancing might become a problem.  Your cat-file example should be fine,
but someone could decide to add only hashes with a certain prefix to
their skiplist, and lookups would lopsided.

But first we'd need something like test-sha1-array for oidset and
some kind of performance tests based on these helpers, right?

René

Re: [PATCH 1/2] fsck: use strbuf_getline() to read skiplist file

[René Scharfe]

Am 11.08.2018 um 18:48 schrieb Jeff King:

And one I'm not sure about:

  - a read() error will now be quietly ignored; I guess we'd have to
check ferror(fp) to cover this. I'm not sure if it matters.


I'm not sure, either.  It would catch media errors or file system
corruption, right?  Sounds useful, actually.  We should check the other
callers of strbuf_getline and friends as well, though, as reporting such
errors seems to be omitted in most cases:

$ git grep strbuf_getline | wc -l
99
$ git grep ferror | wc -l
35

René

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

[René Scharfe]

Object IDs to skip are stored in a shared static oid_array.  Lookups do
a binary search on the sorted array.  The code checks if the object IDs
are already in the correct order while loading and skips sorting in that
case.

Simplify the code by using an oidset instead.  Memory usage is a bit
higher, but lookups are done in constant time and there is no need to
worry about any sort order.

Embed the oidset into struct fsck_options to make its ownership clear
(no hidden sharing) and avoid unnecessary pointer indirection.

Signed-off-by: Rene Scharfe 
---
 fsck.c | 23 ++-
 fsck.h |  8 +---
 2 files changed, 7 insertions(+), 24 deletions(-)

diff --git a/fsck.c b/fsck.c
index 83f4562390..9246afee22 100644
--- a/fsck.c
+++ b/fsck.c
@@ -10,7 +10,6 @@
 #include "fsck.h"
 #include "refs.h"
 #include "utf8.h"
-#include "sha1-array.h"
 #include "decorate.h"
 #include "oidset.h"
 #include "packfile.h"
@@ -182,19 +181,10 @@ static int fsck_msg_type(enum fsck_msg_id msg_id,
 
 static void init_skiplist(struct fsck_options *options, const char *path)

 {
-   static struct oid_array skiplist = OID_ARRAY_INIT;
-   int sorted;
FILE *fp;
struct strbuf sb = STRBUF_INIT;
struct object_id oid;
 
-	if (options->skiplist)

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

@@ -317,9 +300,7 @@ static void append_msg_id(struct strbuf *sb, const char 
*msg_id)
 
 static int object_on_skiplist(struct fsck_options *opts, struct object *obj)

 {
-   if (opts && opts->skiplist && obj)
-   return oid_array_lookup(opts->skiplist, >oid) >= 0;
-   return 0;
+   return opts && obj && oidset_contains(>skiplist, >oid);
 }
 
 __attribute__((format (printf, 4, 5)))

diff --git a/fsck.h b/fsck.h
index c3cf5e0034..26120e6186 100644
--- a/fsck.h
+++ b/fsck.h
@@ -1,6 +1,8 @@
 #ifndef GIT_FSCK_H
 #define GIT_FSCK_H
 
+#include "oidset.h"

+
 #define FSCK_ERROR 1
 #define FSCK_WARN 2
 #define FSCK_IGNORE 3
@@ -34,12 +36,12 @@ struct fsck_options {
fsck_error error_func;
unsigned strict:1;
int *msg_type;
-   struct oid_array *skiplist;
+   struct oidset skiplist;
struct decoration *object_names;
 };
 
-#define FSCK_OPTIONS_DEFAULT { NULL, fsck_error_function, 0, NULL }

-#define FSCK_OPTIONS_STRICT { NULL, fsck_error_function, 1, NULL }
+#define FSCK_OPTIONS_DEFAULT { NULL, fsck_error_function, 0, NULL, OIDSET_INIT 
}
+#define FSCK_OPTIONS_STRICT { NULL, fsck_error_function, 1, NULL, OIDSET_INIT }
 
 /* descend in all linked child objects

  * the return value is:
--
2.18.0

[PATCH 1/2] fsck: use strbuf_getline() to read skiplist file

[René Scharfe]

The char array named "buffer" is unlikely to contain a NUL character, so
printing its contents using %s in a die() format is unsafe.  Clang's
ASan reports running over the end of buffer in the recently added
skiplist tests in t5504-fetch-receive-strict.sh as a result.

Use an idiomatic strbuf_getline() loop instead, which ensures the buffer
is always NUL-terminated.  As a side-effect this also adds support for
skiplist files with CRLF line endings.

Signed-off-by: Rene Scharfe 
---
 fsck.c | 23 ++-
 1 file changed, 10 insertions(+), 13 deletions(-)

diff --git a/fsck.c b/fsck.c
index a0cee0be59..83f4562390 100644
--- a/fsck.c
+++ b/fsck.c
@@ -183,8 +183,9 @@ static int fsck_msg_type(enum fsck_msg_id msg_id,
 static void init_skiplist(struct fsck_options *options, const char *path)
 {
static struct oid_array skiplist = OID_ARRAY_INIT;
-   int sorted, fd;
-   char buffer[GIT_MAX_HEXSZ + 1];
+   int sorted;
+   FILE *fp;
+   struct strbuf sb = STRBUF_INIT;
struct object_id oid;
 
 	if (options->skiplist)

@@ -194,25 +195,21 @@ static void init_skiplist(struct fsck_options *options, 
const char *path)
options->skiplist = 
}
 
-	fd = open(path, O_RDONLY);

-   if (fd < 0)
+   fp = fopen(path, "r");
+   if (!fp)
die("Could not open skip list: %s", path);
-   for (;;) {
+   while (!strbuf_getline(, fp)) {
const char *p;
-   int result = read_in_full(fd, buffer, sizeof(buffer));
-   if (result < 0)
-   die_errno("Could not read '%s'", path);
-   if (!result)
-   break;
-   if (parse_oid_hex(buffer, , ) || *p != '\n')
-   die("Invalid SHA-1: %s", buffer);
+   if (parse_oid_hex(sb.buf, , ) || *p != '\0')
+   die("Invalid SHA-1: %s", sb.buf);
oid_array_append(, );
if (sorted && skiplist.nr > 1 &&
oidcmp([skiplist.nr - 2],
   ) > 0)
sorted = 0;
}
-   close(fd);
+   fclose(fp);
+   strbuf_release();
 
 	if (sorted)

skiplist.sorted = 1;
--
2.18.0

Re: Re* [PATCH] push: comment on a funny unbalanced option help

[René Scharfe]

Am 02.08.2018 um 22:36 schrieb Junio C Hamano:
> Ævar Arnfjörð Bjarmason  writes:
> 
>> Thanks, FWIW that's fine by me, and also if you want to drop this "fake"
>> patch of mine and replace it with something René came up with (I have
>> not yet read his 1-6 patches submitted on this topic, so maybe they're
>> not mutually exclusive).
> 
> I think the 6-patch series supersedes this one.  Thanks anyway.

Actually no, I specifically avoided touching builtin/push.c because this
patch already handled it; it should still be applied before patch 6 from
my series.

René

Re: [PATCH] push: comment on a funny unbalanced option help

[René Scharfe]

Am 02.08.2018 um 22:01 schrieb Junio C Hamano:
> René Scharfe  writes:
> 
>> Am 02.08.2018 um 18:54 schrieb Jeff King:
>>> PS I actually would have made the rule simply "does it begin with a
>>>  '<'", which seems simpler still. If people accidentally write ">>  forgetting to close their brackets, that is a bug under both the
>>>  old and new behavior (just with slightly different outcomes).
>>
>> Good point.
> 
> Straying sideways into a tangent, but do we know if any locale wants
> to use something other than "<>" as an enclosing braket around a
> placeholder?

Bulgarian seems to use capitals instead; here are some examples found
with git grep -A1 'msgid "<' po/:

po/bg.po:msgid ""
po/bg.po-msgstr "ОТДАЛЕЧЕНО_ХРАНИЛИЩЕ"
--
po/bg.po:msgid ""
po/bg.po-msgstr "КЛОН"
--
po/bg.po:msgid "/"
po/bg.po-msgstr "ПОДДИРЕКТОРИЯ/"
--
po/bg.po:msgid "[,]"
po/bg.po-msgstr "БРОЙ[,БАЗА]"

>  This arg-help text, for example,
> 
>   N_("refspec")   without LIT-ARG-HELP
> 
> would be irritating for such a locale's translator, who cannot
> defeat the "<>" that is hardcoded and not inside _()
> 
>   s = literal ? "%s" : "<%s>";
>  
> that appear in parse-options.c::usage_argh().
> 
> Perhaps we should do _("<%s>") here?  That way, the result would
> hopefully be made consistent with
> 
>   N_("[:]")  with LIT-ARG-HELP
> 
> which allows translator to use the bracket of the locale's choice.

@Alexander: Would that help you?

René

[PATCH 6/6] parse-options: automatically infer PARSE_OPT_LITERAL_ARGHELP

[René Scharfe]

Parseopt wraps argument help strings in a pair of angular brackets by
default, to tell users that they need to replace it with an actual
value.  This is useful in most cases, because most option arguments
are indeed single values of a certain type.  The option
PARSE_OPT_LITERAL_ARGHELP needs to be used in option definitions with
arguments that have multiple parts or are literal strings.

Stop adding these angular brackets if special characters are present,
as they indicate that we don't deal with a simple placeholder.  This
simplifies the code a bit and makes defining special options slightly
easier.

Remove the flag PARSE_OPT_LITERAL_ARGHELP in the cases where the new
and more cautious handling suffices.

Signed-off-by: Rene Scharfe 
---
The patch to add PARSE_OPT_LITERAL_ARGHELP for push --force-with-lease
should be applied before this one.

 builtin/add.c  | 5 ++---
 builtin/pack-objects.c | 2 +-
 builtin/read-tree.c| 2 +-
 builtin/send-pack.c| 3 +--
 builtin/shortlog.c | 3 +--
 builtin/show-branch.c  | 2 +-
 builtin/update-index.c | 2 +-
 builtin/write-tree.c   | 5 ++---
 parse-options.c| 3 ++-
 9 files changed, 12 insertions(+), 15 deletions(-)

diff --git a/builtin/add.c b/builtin/add.c
index 84bfec9b73..ba1ff5689d 100644
--- a/builtin/add.c
+++ b/builtin/add.c
@@ -304,9 +304,8 @@ static struct option builtin_add_options[] = {
OPT_BOOL( 0 , "refresh", _only, N_("don't add, only refresh the 
index")),
OPT_BOOL( 0 , "ignore-errors", _add_errors, N_("just skip files 
which cannot be added because of errors")),
OPT_BOOL( 0 , "ignore-missing", _missing, N_("check if - even 
missing - files are ignored in dry run")),
-   { OPTION_STRING, 0, "chmod", _arg, "(+|-)x",
- N_("override the executable bit of the listed files"),
- PARSE_OPT_LITERAL_ARGHELP },
+   OPT_STRING(0, "chmod", _arg, "(+|-)x",
+  N_("override the executable bit of the listed files")),
OPT_HIDDEN_BOOL(0, "warn-embedded-repo", _on_embedded_repo,
N_("warn when adding an embedded repository")),
OPT_END(),
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 3a5d1fa317..b2323613bc 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -3112,7 +3112,7 @@ int cmd_pack_objects(int argc, const char **argv, const 
char *prefix)
 N_("similar to --all-progress when progress meter is 
shown")),
{ OPTION_CALLBACK, 0, "index-version", NULL, 
N_("[,]"),
  N_("write the pack index file in the specified idx format 
version"),
- PARSE_OPT_LITERAL_ARGHELP, option_parse_index_version },
+ 0, option_parse_index_version },
OPT_MAGNITUDE(0, "max-pack-size", _size_limit,
  N_("maximum size of each output pack file")),
OPT_BOOL(0, "local", ,
diff --git a/builtin/read-tree.c b/builtin/read-tree.c
index ebc43eb805..fbbc98e516 100644
--- a/builtin/read-tree.c
+++ b/builtin/read-tree.c
@@ -133,7 +133,7 @@ int cmd_read_tree(int argc, const char **argv, const char 
*unused_prefix)
 N_("same as -m, but discard unmerged entries")),
{ OPTION_STRING, 0, "prefix", , 
N_("/"),
  N_("read the tree into the index under /"),
- PARSE_OPT_NONEG | PARSE_OPT_LITERAL_ARGHELP },
+ PARSE_OPT_NONEG },
OPT_BOOL('u', NULL, ,
 N_("update working tree with merge result")),
{ OPTION_CALLBACK, 0, "exclude-per-directory", ,
diff --git a/builtin/send-pack.c b/builtin/send-pack.c
index 0b517c9368..724b484850 100644
--- a/builtin/send-pack.c
+++ b/builtin/send-pack.c
@@ -180,8 +180,7 @@ int cmd_send_pack(int argc, const char **argv, const char 
*prefix)
{ OPTION_CALLBACK,
  0, CAS_OPT_NAME, , N_(":"),
  N_("require old value of ref to be at this value"),
- PARSE_OPT_OPTARG | PARSE_OPT_LITERAL_ARGHELP,
- parseopt_push_cas_option },
+ PARSE_OPT_OPTARG, parseopt_push_cas_option },
OPT_END()
};
 
diff --git a/builtin/shortlog.c b/builtin/shortlog.c
index f555cf9e4f..3898a2c9c4 100644
--- a/builtin/shortlog.c
+++ b/builtin/shortlog.c
@@ -269,8 +269,7 @@ int cmd_shortlog(int argc, const char **argv, const char 
*prefix)
OPT_BOOL('e', "email", ,
 N_("Show the email address of each author")),
{ OPTION_CALLBACK, 'w', NULL, , N_("[,[,]]"),
-   N_("Linewrap output"),
-   PARSE_OPT_OPTARG | PARSE_OPT_LITERAL_ARGHELP,
+   N_("Linewrap output"), PARSE_OPT_OPTARG,
_wrap_args },
OPT_END(),
};
diff --git a/builtin/show-branch.c b/builtin/show-branch.c
index f2e985c00a..9106da1985 100644
--- 

[PATCH 5/6] shortlog: correct option help for -w

[René Scharfe]

Wrap the placeholders in the option help string for -w in pairs of
angular brackets to document that users need to replace them with actual
numbers.  Use the flag PARSE_OPT_LITERAL_ARGHELP to prevent parseopt
from adding another pair.

Signed-off-by: Rene Scharfe 
---
 builtin/shortlog.c | 6 --
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/builtin/shortlog.c b/builtin/shortlog.c
index 608d6ba77b..f555cf9e4f 100644
--- a/builtin/shortlog.c
+++ b/builtin/shortlog.c
@@ -268,8 +268,10 @@ int cmd_shortlog(int argc, const char **argv, const char 
*prefix)
 N_("Suppress commit descriptions, only provides commit 
count")),
OPT_BOOL('e', "email", ,
 N_("Show the email address of each author")),
-   { OPTION_CALLBACK, 'w', NULL, , N_("w[,i1[,i2]]"),
-   N_("Linewrap output"), PARSE_OPT_OPTARG, 
_wrap_args },
+   { OPTION_CALLBACK, 'w', NULL, , N_("[,[,]]"),
+   N_("Linewrap output"),
+   PARSE_OPT_OPTARG | PARSE_OPT_LITERAL_ARGHELP,
+   _wrap_args },
OPT_END(),
};
 
-- 
2.18.0

[PATCH 4/6] send-pack: specify --force-with-lease argument help explicitly

[René Scharfe]

Wrap each part of the argument help string in angular brackets to show
that users need to replace them with actual values.  Do that explicitly
to balance the pairs nicely in the code and avoid confusing casual
readers.  Add the flag PARSE_OPT_LITERAL_ARGHELP to keep parseopt from
adding another pair.

Signed-off-by: Rene Scharfe 
---
 builtin/send-pack.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/builtin/send-pack.c b/builtin/send-pack.c
index 42fd8d1a35..0b517c9368 100644
--- a/builtin/send-pack.c
+++ b/builtin/send-pack.c
@@ -178,9 +178,10 @@ int cmd_send_pack(int argc, const char **argv, const char 
*prefix)
OPT_BOOL(0, "stdin", _stdin, N_("read refs from stdin")),
OPT_BOOL(0, "helper-status", _status, N_("print status 
from remote helper")),
{ OPTION_CALLBACK,
- 0, CAS_OPT_NAME, , N_("refname>::"),
  N_("require old value of ref to be at this value"),
- PARSE_OPT_OPTARG, parseopt_push_cas_option },
+ PARSE_OPT_OPTARG | PARSE_OPT_LITERAL_ARGHELP,
+ parseopt_push_cas_option },
OPT_END()
};
 
-- 
2.18.0

[PATCH 3/6] pack-objects: specify --index-version argument help explicitly

[René Scharfe]

Wrap both placeholders in the argument help string in angular brackets
to signal that users needs replace them with some actual value.  Use the
flag PARSE_OPT_LITERAL_ARGHELP to prevent parseopt from adding another
pair.

Signed-off-by: Rene Scharfe 
---
 builtin/pack-objects.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index ebc8cefb53..3a5d1fa317 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -3110,9 +3110,9 @@ int cmd_pack_objects(int argc, const char **argv, const 
char *prefix)
OPT_BOOL(0, "all-progress-implied",
 _progress_implied,
 N_("similar to --all-progress when progress meter is 
shown")),
-   { OPTION_CALLBACK, 0, "index-version", NULL, 
N_("version[,offset]"),
+   { OPTION_CALLBACK, 0, "index-version", NULL, 
N_("[,]"),
  N_("write the pack index file in the specified idx format 
version"),
- 0, option_parse_index_version },
+ PARSE_OPT_LITERAL_ARGHELP, option_parse_index_version },
OPT_MAGNITUDE(0, "max-pack-size", _size_limit,
  N_("maximum size of each output pack file")),
OPT_BOOL(0, "local", ,
-- 
2.18.0

[PATCH 2/6] difftool: remove angular brackets from argument help

[René Scharfe]

Parseopt wraps arguments in a pair of angular brackets by default,
signifying that the user needs to replace it with a value of the
documented type.  Remove the pairs from the option definitions to
duplication and confusion.

Signed-off-by: Rene Scharfe 
---
 builtin/difftool.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/builtin/difftool.c b/builtin/difftool.c
index 51f6c9cdb4..172af0448b 100644
--- a/builtin/difftool.c
+++ b/builtin/difftool.c
@@ -703,7 +703,7 @@ int cmd_difftool(int argc, const char **argv, const char 
*prefix)
1, PARSE_OPT_NONEG | PARSE_OPT_HIDDEN),
OPT_BOOL(0, "symlinks", ,
 N_("use symlinks in dir-diff mode")),
-   OPT_STRING('t', "tool", _cmd, N_(""),
+   OPT_STRING('t', "tool", _cmd, N_("tool"),
   N_("use the specified diff tool")),
OPT_BOOL(0, "tool-help", _help,
 N_("print a list of diff tools that may be used with "
@@ -711,7 +711,7 @@ int cmd_difftool(int argc, const char **argv, const char 
*prefix)
OPT_BOOL(0, "trust-exit-code", _exit_code,
 N_("make 'git-difftool' exit when an invoked diff "
"tool returns a non - zero exit code")),
-   OPT_STRING('x', "extcmd", , N_(""),
+   OPT_STRING('x', "extcmd", , N_("command"),
   N_("specify a custom command for viewing diffs")),
OPT_END()
};
-- 
2.18.0

[PATCH 1/6] add, update-index: fix --chmod argument help

[René Scharfe]

Don't translate the argument specification for --chmod; "+x" and "-x"
are the literal strings that the commands accept.

Separate alternatives using a pipe character instead of a slash, for
consistency.

Use the flag PARSE_OPT_LITERAL_ARGHELP to prevent parseopt from adding a
pair of angular brackets around the argument help string, as that would
wrongly indicate that users need to replace the literal strings with
some kind of value.

Signed-off-by: Rene Scharfe 
---
 builtin/add.c  | 4 +++-
 builtin/update-index.c | 2 +-
 2 files changed, 4 insertions(+), 2 deletions(-)

diff --git a/builtin/add.c b/builtin/add.c
index 8a155dd41e..84bfec9b73 100644
--- a/builtin/add.c
+++ b/builtin/add.c
@@ -304,7 +304,9 @@ static struct option builtin_add_options[] = {
OPT_BOOL( 0 , "refresh", _only, N_("don't add, only refresh the 
index")),
OPT_BOOL( 0 , "ignore-errors", _add_errors, N_("just skip files 
which cannot be added because of errors")),
OPT_BOOL( 0 , "ignore-missing", _missing, N_("check if - even 
missing - files are ignored in dry run")),
-   OPT_STRING( 0 , "chmod", _arg, N_("(+/-)x"), N_("override the 
executable bit of the listed files")),
+   { OPTION_STRING, 0, "chmod", _arg, "(+|-)x",
+ N_("override the executable bit of the listed files"),
+ PARSE_OPT_LITERAL_ARGHELP },
OPT_HIDDEN_BOOL(0, "warn-embedded-repo", _on_embedded_repo,
N_("warn when adding an embedded repository")),
OPT_END(),
diff --git a/builtin/update-index.c b/builtin/update-index.c
index a8709a26ec..7feda6e271 100644
--- a/builtin/update-index.c
+++ b/builtin/update-index.c
@@ -971,7 +971,7 @@ int cmd_update_index(int argc, const char **argv, const 
char *prefix)
PARSE_OPT_NOARG | /* disallow --cacheinfo= form */
PARSE_OPT_NONEG | PARSE_OPT_LITERAL_ARGHELP,
(parse_opt_cb *) cacheinfo_callback},
-   {OPTION_CALLBACK, 0, "chmod", _executable_bit, N_("(+/-)x"),
+   {OPTION_CALLBACK, 0, "chmod", _executable_bit, "(+|-)x",
N_("override the executable bit of the listed files"),
PARSE_OPT_NONEG | PARSE_OPT_LITERAL_ARGHELP,
chmod_callback},
-- 
2.18.0

Re: [PATCH] push: comment on a funny unbalanced option help

[René Scharfe]

Am 02.08.2018 um 18:54 schrieb Jeff King:
> PS I actually would have made the rule simply "does it begin with a
> '<'", which seems simpler still. If people accidentally write " forgetting to close their brackets, that is a bug under both the
> old and new behavior (just with slightly different outcomes).

Good point.  We could also extend it further and check if it contains
any special character, which would allow us to convert the remaining
user of the flag as well:

{OPTION_CALLBACK, 0, "chmod", _executable_bit, N_("(+/-)x"),
N_("override the executable bit of the listed files"),
PARSE_OPT_NONEG | PARSE_OPT_LITERAL_ARGHELP,
chmod_callback},

Special characters are (, ), <, >, [, ], and |.

The idea is that we shouldn't automatically treat a string as a
simple replacement specifier if it looks like it has some structure
to it.

Side note: "(+/-)x" is marked for translation above.  Any translation
that is not identical would be wrong, though, because the command only
accepts a literal "+x" or "-x" in any locale.  So the N_ wrapper is
bogus, right?

Checked the output with that extended check by generating all help
pages with:

for cmd in $(git --list-cmds=parseopt)
do git-$cmd -h
done

... and found a few differences:

git add:
---chmod <(+/-)x>  override the executable bit of the listed files
+--chmod (+/-)xoverride the executable bit of the listed files

Good change.  We also should change the slash to a pipe.

git checkout-index:
---stage <1-3|all> copy out the files from named stage
+--stage 1-3|all   copy out the files from named stage

Good change, but perhaps mention number two explicitly?

git difftool:
--t, --tool <>   use the specified diff tool
+-t, --tool  use the specified diff tool
--x, --extcmd <>
+-x, --extcmd 

Aha, double angle brackets in the wild!  Good change.  We could
also remove the explicit pairs from the option definitions.

git pack-objects:
---index-version 
+--index-version version[,offset]

Not good before, worse after. Should be to "[,]".

git pull:
--r, --rebase[=]
+-r, --rebase[=false|true|merges|preserve|interactive]

Good change, but wouldn't we want to add a pair of parentheses around
the list of alternatives?

git push:
---force-with-lease[=:]
+--force-with-lease[=refname>:]
+--recurse-submodules[=check|on-demand|no]
---signed[=]
+--signed[=yes|no|if-asked]

git send-pack:
---signed[=]
+--signed[=yes|no|if-asked]

Good changes all three, but need parentheses..

---force-with-lease[=:]
+--force-with-lease[=refname>:] Linewrap output
+-w[w[,i1[,i2]]]   Linewrap output

Not good before, worse after.  Should be "[[,[,]]]".

git update-index:
---cacheinfo ,,
-  add the specified entry to the index
+--cacheinfo   add the specified entry to the index

Eh, what?  Ah, that option is defined with PARSE_OPT_NOARG, and we only
show argument help because PARSE_OPT_LITERAL_ARGHELP is also given, so
we need to keep that flag for this special option.

René

Re: [PATCH] push: comment on a funny unbalanced option help

[René Scharfe]

Am 02.08.2018 um 17:31 schrieb Junio C Hamano:
> René Scharfe  writes:
>> diff --git a/parse-options.c b/parse-options.c
>> index 7db84227ab..fadfc6a833 100644
>> --- a/parse-options.c
>> +++ b/parse-options.c
>> @@ -660,7 +660,8 @@ int parse_options(int argc, const char **argv, const 
>> char *prefix,
>>   static int usage_argh(const struct option *opts, FILE *outfile)
>>   {
>>  const char *s;
>> -int literal = (opts->flags & PARSE_OPT_LITERAL_ARGHELP) || !opts->argh;
>> +int literal = (opts->flags & PARSE_OPT_LITERAL_ARGHELP) || !opts->argh 
>> ||
>> +(opts->argh[0] == '<' && strchr(opts->argh, '>'));
> 
> You are greedier than what I thought ;-) I would have limited this
> magic to the case where argh is surrounded by "<>", but you allow
> one closing ">" anywhere, which allows us to grab more complex cases.

That's what I had initially, but only one of the current cases would
have benefited from that strict behavior, so it's not useful enough.

> The lack of escape hatch to decline this auto-literal magic makes me
> somewhat nervous, but I do not offhand think of a reason why I do
> want an arg-help string that _begins_ with '<' to be enclosed by
> another set of "<>", so perhaps this is a good kind of magic.

The escape hatch is to add the extra pair manually to the argh string.

René

Re: Re* [PATCH] push: comment on a funny unbalanced option help

[René Scharfe]

Am 02.08.2018 um 17:44 schrieb Junio C Hamano:
> Subject: [PATCH] push: use PARSE_OPT_LITERAL_ARGHELP instead of unbalanced 
> brackets
> From: Ævar Arnfjörð Bjarmason 
> Date: Thu, 02 Aug 2018 00:31:33 +0200
> 
> The option help text for the force-with-lease option to "git push"
> reads like this:
> 
>  $ git push -h 2>&1 | grep -e force-with-lease
> --force-with-lease[=:]
> 
> which comes from having N_("refname>: text in the source code, with an aparent lack of "<" and ">" at both
> ends.
> 
> It turns out that parse-options machinery takes the whole string and
> encloses it inside a pair of "<>", to make it easier for majority
> cases that uses a single token placeholder.
> 
> The help string was written in a funnily unbalanced way knowing that
> the end result would balance out, by somebody who forgot the
> presence of PARSE_OPT_LITERAL_ARGHELP, which is the escape hatch
> mechanism designed to help such a case.  We just should use the
> official escape hatch instead.
> 
> Helped-by: René Scharfe 

I didn't do anything for this particular patch so far?  But...

> Signed-off-by: Junio C Hamano 
> ---
>   builtin/push.c | 4 ++--
>   1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/builtin/push.c b/builtin/push.c
> index 1c28427d82..ef4032a9ef 100644
> --- a/builtin/push.c
> +++ b/builtin/push.c
> @@ -542,9 +542,9 @@ int cmd_push(int argc, const char **argv, const char 
> *prefix)
>   OPT_BIT( 0,  "porcelain", , N_("machine-readable 
> output"), TRANSPORT_PUSH_PORCELAIN),
>   OPT_BIT('f', "force", , N_("force updates"), 
> TRANSPORT_PUSH_FORCE),
>   { OPTION_CALLBACK,
> -   0, CAS_OPT_NAME, , N_("refname>: +   0, CAS_OPT_NAME, , N_(":"),

... shouldn't we use this opportunity to document that "expect" is
optional?

+ 0, CAS_OPT_NAME, , N_("[:]"),

> N_("require old value of ref to be at this value"),
> -   PARSE_OPT_OPTARG, parseopt_push_cas_option },
> +   PARSE_OPT_OPTARG | PARSE_OPT_LITERAL_ARGHELP, 
> parseopt_push_cas_option },
>   { OPTION_CALLBACK, 0, "recurse-submodules", 
> _submodules, "check|on-demand|no",
>   N_("control recursive pushing of submodules"),
>   PARSE_OPT_OPTARG, option_parse_recurse_submodules },
> 

Re: [PATCH] push: comment on a funny unbalanced option help

[René Scharfe]

Am 02.08.2018 um 17:06 schrieb René Scharfe:
> According to its manpage the option should rather be shown like this:
> 
>   --force-with-lease[=[:]]
> 
> ... to indicate that all three forms are valid:
> 
>   --force-with-lease
>   --force-with-lease=some_ref
>   --force-with-lease=some_ref:but_not_this
> 
> The current code doesn't allow that to be expressed, while it's possible
> with my patch.
Err, anything is possible with PARSE_OPT_LITERAL_ARGHELP, of course, but
with my patch that flag is automatically inferred if you use the argh
string "[:]".

René

Re: [PATCH] push: comment on a funny unbalanced option help

[René Scharfe]

Am 02.08.2018 um 16:21 schrieb Ævar Arnfjörð Bjarmason:
> 
> On Thu, Aug 02 2018, René Scharfe wrote:
> 
>> Am 02.08.2018 um 00:31 schrieb Ævar Arnfjörð Bjarmason:
>>> But looking at this again it looks like this whole thing should just be
>>> replaced by:
>>>
>>>   diff --git a/builtin/push.c b/builtin/push.c
>>>   index 9cd8e8cd56..b8fa15c101 100644
>>>   --- a/builtin/push.c
>>>   +++ b/builtin/push.c
>>>   @@ -558,9 +558,10 @@ int cmd_push(int argc, const char **argv, const 
>>> char *prefix)
>>>   OPT_BIT( 0,  "porcelain", , 
>>> N_("machine-readable output"), TRANSPORT_PUSH_PORCELAIN),
>>>   OPT_BIT('f', "force", , N_("force updates"), 
>>> TRANSPORT_PUSH_FORCE),
>>>   { OPTION_CALLBACK,
>>>   - 0, CAS_OPT_NAME, , N_("refname>:>>   + 0, CAS_OPT_NAME, , N_(":"),
>>> N_("require old value of ref to be at this value"),
>>>   - PARSE_OPT_OPTARG, parseopt_push_cas_option },
>>>   + PARSE_OPT_OPTARG | PARSE_OPT_LITERAL_ARGHELP,
>>>   + parseopt_push_cas_option },
>>>   { OPTION_CALLBACK, 0, "recurse-submodules", 
>>> _submodules, "check|on-demand|no",
>>>   N_("control recursive pushing of submodules"),
>>>   PARSE_OPT_OPTARG, 
>>> option_parse_recurse_submodules },
>>>
>>> I.e. the reason this is confusing is because the code originally added
>>> in 28f5d17611 ("remote.c: add command line option parser for
>>> "--force-with-lease"", 2013-07-08) didn't use PARSE_OPT_LITERAL_ARGHELP,
>>> which I also see is what read-tree etc. use already to not end up with
>>> these double <>'s, see also 29f25d493c ("parse-options: add
>>> PARSE_OPT_LITERAL_ARGHELP for complicated argh's", 2009-05-21).
>>
>> We could check if argh comes with its own angle brackets already and
>> not add a second pair in that case, making PARSE_OPT_LITERAL_ARGHELP
>> redundant in most cases, including the one above.  Any downsides?
>> Too magical?
> 
> I'm more inclined to say that we should stop using
> PARSE_OPT_LITERAL_ARGHELP in some of these cases, and change
> "refname>::" in push.c, so that the help
> we emit is --force-with-lease[=<:>].
> 
> As noted in 29f25d493c this facility wasn't added with the intent
> turning --refspec=<> into --refspec=, but to do stuff
> like --option=[,] for options that take comma-delimited
> options.
> 
> If we're magically removing <>'s we have no consistent convention to
> tell apart --opt= meaning "one of a, b or c", --refspec=
> meaning "the literal string 'refspec'" and --refspec=<> meaning
> add a  string, i.e. fill in your refspec here.

The notation for requiring a literal string is to use no special markers:

--option=literal_string

Alternatives can be grouped with parentheses:

--option=(either|or)

In both cases you'd need PARSE_OPT_LITERAL_ARGHELP.

I haven't seen double angle brackets before in command line help strings.
The commit message of 29f25d493c doesn't mention them either.  A single
pair is used to indicate that users need to fill in a value of a certain
type:

--refspec=

Multi-part options aren't special in this syntax:

--force-with-lease=:

NB: The "--refspec=" in the example before that is a literal string, so
this is also already a multi-part option if you will.

According to its manpage the option should rather be shown like this:

--force-with-lease[=[:]]

... to indicate that all three forms are valid:

--force-with-lease
--force-with-lease=some_ref
--force-with-lease=some_ref:but_not_this

The current code doesn't allow that to be expressed, while it's possible
with my patch.  And nothing is removed -- you can specify as many angle
brackets as you like, if that turns out to be useful; parseopt just won't
add any more on top automatically anymore if you do that.

Side note: The remaining user of PARSE_OPT_LITERAL_ARGHELP in
builtin/update-index.c uses a slash for alternatives; we should probably
use pipe instead:

{OPTION_CALLBACK, 0, "chmod", _executable_bit, N_("(+/-)x"),
N_("override the executable bit of the listed files"),
PARSE_OPT_NONEG | PARSE_OPT_LITERAL_ARGHELP,
chmod_callback},

René

Re: [PoC] coccinelle: make Coccinelle-related make targets more fine-grained

[René Scharfe]

Am 02.08.2018 um 13:55 schrieb SZEDER Gábor:
> Let's add a bit of Makefile metaprogramming to generate finer-grained
> make targets applying one semantic patch to only a single source file,
> and specify these as dependencies of the targets applying one semantic
> patch to all source files.  This way that shell loop can be avoided,
> semantic patches will only be applied to changed source files, and the
> same semantic patch can be applied in parallel to multiple source
> files.  The only remaining sequential part is aggregating the
> suggested transformations from the individual targets into a single
> patch file, which is comparatively cheap (especially since ideally
> there aren't any suggestions).
> 
> This change brings spectacular speedup in the scenario described in
> point (1) above.  When the results of a previous 'make coccicheck' are
> there, the time needed to run
> 
>touch apply.c ; time make -j4 coccicheck
> 
> went from 3m42s to 1.848s, which is just over 99% speedup, yay!, and
> 'apply.c' is the second longest source file in our codebase.  In the
> scenario in point (2), running
> 
>touch contrib/coccinelle/array.cocci ; time make -j4 coccicheck
> 
> went from 56.364s to 35.883s, which is ~36% speedup.

Awesome!

> Unfortunately, this new approach has some disadvantages compared to
> the current situation:
> 
>- [RFC]
>  With this patch 'make coccicheck's output will look like this
>  ('make' apparently doesn't iterate over semantic patches in
>  lexicographical order):
> 
>SPATCH commit.cocci  abspath.c
>SPATCH commit.cocci  advice.c
><... lots of lines ...>
>SPATCH array.cocci   http-walker.c
>SPATCH array.cocci   remote-curl.c
> 
>  which means that the number of lines in the output grows from
>  "Nr-of-semantic-patches" to "Nr-of-semantic-patches *
>  Nr-of-source-files".

The output is mostly interesting to see if something is happening, to
see if some semantic patch generated a non-empty diff and to get
error details.  We have ca. 400 .c files and 8 .cocci files -- that
means the lines would fill up my scroll-back buffer.  Hmm.

Would it be possible to have a phony target (or directory) per source
file that just prints a line and depends on the individual file+cocci
targets?  (I don't know much make, you probably thought about it
already.)

Or to select one random .cocci file (let's say the first one) and
only print SPATCH lines for this one (without mentioning its name)?
(A dirty hack..)

> ---
>   Makefile  | 52 ---
>   contrib/coccinelle/.gitignore |  3 +-
>   2 files changed, 38 insertions(+), 17 deletions(-)
> 
> diff --git a/Makefile b/Makefile
> index d616c04125..f516dd93d1 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -2674,25 +2674,44 @@ COCCI_SOURCES = $(filter-out 
> sha1collisiondetection/%,$(C_SOURCES))
>   else
>   COCCI_SOURCES = $(filter-out sha1dc/%,$(C_SOURCES))
>   endif
> +COCCI_SEM_PATCHES = $(wildcard contrib/coccinelle/*.cocci)
>   
> -%.cocci.patch: %.cocci $(COCCI_SOURCES)
> - @echo '' SPATCH $<; \
> - ret=0; \
> - for f in $(COCCI_SOURCES); do \
> - $(SPATCH) --sp-file $< $$f $(SPATCH_FLAGS) || \
> - { ret=$$?; break; }; \
> - done >$@+ 2>$@.log; \
> - if test $$ret != 0; \
> +define cocci_template
> +$(cocci_sem_patch)_dirs := $$(addprefix $(cocci_sem_patch).patches/,$$(sort 
> $$(dir $$(COCCI_SOURCES
> +
> +$$($(cocci_sem_patch)_dirs):
> + @mkdir -p $$@
> +
> +# e.g. 'contrib/coccinelle/strbuf.cocci.patches/builtin/commit.c.patch'
> +# Applies one semantic patch to _one_ source file.
> +$(cocci_sem_patch).patches/%.patch: % $(cocci_sem_patch)
> + @printf ' SPATCH %-25s %s\n' $$(notdir $(cocci_sem_patch)) $$<; \
> + if ! $$(SPATCH) --sp-file $(cocci_sem_patch) $$< $$(SPATCH_FLAGS) >$$@ 
> 2>$$@.log; \
>   then \
> - cat $@.log; \
> + rm -f $$@; \
> + cat $$@.log; \
>   exit 1; \
> - fi; \
> - mv $@+ $@; \
> - if test -s $@; \
> - then \
> - echo '' SPATCH result: $@; \
>   fi
> -coccicheck: $(addsuffix .patch,$(wildcard contrib/coccinelle/*.cocci))
> +
> +# e.g. 'contrib/coccinelle/strbuf.cocci.patch'
> +# Applies one semantic patch to _all_ source files.
> +$(cocci_sem_patch).patch: $(cocci_sem_patch) $$($(cocci_sem_patch)_dirs) 
> $$(patsubst %,$(cocci_sem_patch).patches/%.patch,$(COCCI_SOURCES))

Are the dependencies correct (before and after the patch)?  E.g. are all
semantic patches reapplied after cache.h was changed?  I think we ignore
header files currently, and that becomes more of a problem if the check
becomes more fine-grained.

René

Re: [PATCH] push: comment on a funny unbalanced option help

[René Scharfe]

Am 02.08.2018 um 00:31 schrieb Ævar Arnfjörð Bjarmason:
> But looking at this again it looks like this whole thing should just be
> replaced by:
> 
>  diff --git a/builtin/push.c b/builtin/push.c
>  index 9cd8e8cd56..b8fa15c101 100644
>  --- a/builtin/push.c
>  +++ b/builtin/push.c
>  @@ -558,9 +558,10 @@ int cmd_push(int argc, const char **argv, const 
> char *prefix)
>  OPT_BIT( 0,  "porcelain", , N_("machine-readable 
> output"), TRANSPORT_PUSH_PORCELAIN),
>  OPT_BIT('f', "force", , N_("force updates"), 
> TRANSPORT_PUSH_FORCE),
>  { OPTION_CALLBACK,
>  - 0, CAS_OPT_NAME, , N_("refname>:  + 0, CAS_OPT_NAME, , N_(":"),
>N_("require old value of ref to be at this value"),
>  - PARSE_OPT_OPTARG, parseopt_push_cas_option },
>  + PARSE_OPT_OPTARG | PARSE_OPT_LITERAL_ARGHELP,
>  + parseopt_push_cas_option },
>  { OPTION_CALLBACK, 0, "recurse-submodules", 
> _submodules, "check|on-demand|no",
>  N_("control recursive pushing of submodules"),
>  PARSE_OPT_OPTARG, 
> option_parse_recurse_submodules },
> 
> I.e. the reason this is confusing is because the code originally added
> in 28f5d17611 ("remote.c: add command line option parser for
> "--force-with-lease"", 2013-07-08) didn't use PARSE_OPT_LITERAL_ARGHELP,
> which I also see is what read-tree etc. use already to not end up with
> these double <>'s, see also 29f25d493c ("parse-options: add
> PARSE_OPT_LITERAL_ARGHELP for complicated argh's", 2009-05-21).

We could check if argh comes with its own angle brackets already and
not add a second pair in that case, making PARSE_OPT_LITERAL_ARGHELP
redundant in most cases, including the one above.  Any downsides?
Too magical?

-- >8 --
Subject: [PATCH] parse-options: automatically infer PARSE_OPT_LITERAL_ARGHELP

Avoid adding an extra pair of angular brackets if the argh string
already contains one.  Remove the flag PARSE_OPT_LITERAL_ARGHELP in the
cases where the new automatic handling suffices.  This shortens and
simplifies option definitions with special argument help strings a bit.

Signed-off-by: Rene Scharfe 
---
 builtin/read-tree.c| 2 +-
 builtin/show-branch.c  | 2 +-
 builtin/update-index.c | 2 +-
 builtin/write-tree.c   | 5 ++---
 parse-options.c| 3 ++-
 5 files changed, 7 insertions(+), 7 deletions(-)

diff --git a/builtin/read-tree.c b/builtin/read-tree.c
index ebc43eb805..fbbc98e516 100644
--- a/builtin/read-tree.c
+++ b/builtin/read-tree.c
@@ -133,7 +133,7 @@ int cmd_read_tree(int argc, const char **argv, const char 
*unused_prefix)
 N_("same as -m, but discard unmerged entries")),
{ OPTION_STRING, 0, "prefix", , 
N_("/"),
  N_("read the tree into the index under /"),
- PARSE_OPT_NONEG | PARSE_OPT_LITERAL_ARGHELP },
+ PARSE_OPT_NONEG },
OPT_BOOL('u', NULL, ,
 N_("update working tree with merge result")),
{ OPTION_CALLBACK, 0, "exclude-per-directory", ,
diff --git a/builtin/show-branch.c b/builtin/show-branch.c
index f2e985c00a..9106da1985 100644
--- a/builtin/show-branch.c
+++ b/builtin/show-branch.c
@@ -673,7 +673,7 @@ int cmd_show_branch(int ac, const char **av, const char 
*prefix)
{ OPTION_CALLBACK, 'g', "reflog", _base, 
N_("[,]"),
N_("show  most recent ref-log entries starting 
at "
   "base"),
-   PARSE_OPT_OPTARG | PARSE_OPT_LITERAL_ARGHELP,
+   PARSE_OPT_OPTARG,
parse_reflog_param },
OPT_END()
};
diff --git a/builtin/update-index.c b/builtin/update-index.c
index a8709a26ec..22749fc2c7 100644
--- a/builtin/update-index.c
+++ b/builtin/update-index.c
@@ -969,7 +969,7 @@ int cmd_update_index(int argc, const char **argv, const 
char *prefix)
N_(",,"),
N_("add the specified entry to the index"),
PARSE_OPT_NOARG | /* disallow --cacheinfo= form */
-   PARSE_OPT_NONEG | PARSE_OPT_LITERAL_ARGHELP,
+   PARSE_OPT_NONEG,
(parse_opt_cb *) cacheinfo_callback},
{OPTION_CALLBACK, 0, "chmod", _executable_bit, N_("(+/-)x"),
N_("override the executable bit of the listed files"),
diff --git a/builtin/write-tree.c b/builtin/write-tree.c
index c9d3c544e7..cdcbf8264e 100644
--- a/builtin/write-tree.c
+++ b/builtin/write-tree.c
@@ -24,9 +24,8 @@ int cmd_write_tree(int argc, const char **argv, const char 
*unused_prefix)
struct option write_tree_options[] = {
OPT_BIT(0, "missing-ok", , N_("allow missing objects"),
   

Re: [PATCH] remote: clear string_list after use in mv()

[René Scharfe]

Thank you for the review!

Am 02.08.2018 um 04:56 schrieb Jonathan Nieder:
> René Scharfe wrote:
> 
>> Subject: remote: clear string_list after use in mv()
> 
> This subject line doesn't fully reflect the goodness of this change.
> How about something like:
> 
>   remote mv: avoid leaking ref names in string_list
> 
> ?

Hmm, "clearing" a string_list is how we release its memory, and since we
didn't do it before (otherwise we wouldn't need the patch) it leaked
before.  So I think the title implies plugging a leak already.

The ref names don't take up much space -- they are probably in the range
of hundreds to thousands and probably take up less than 100 bytes each.
The command exits after calling mv(), so this is a minor leak which
won't be noticed by users.

The benefit of this patch is to bring this function in line with its
siblings, which all release their string_lists when done.

>> --- a/builtin/remote.c
>> +++ b/builtin/remote.c
>> @@ -558,23 +558,23 @@ struct rename_info {
> 
> optional: Would it be worth a comment in the struct definition to say
> this string_list owns its items (or in other words that it's a _DUP
> string_list)?

Such a comment could easily get out of sync with the assignment later in
the code.  And the struct could easily be used with both types of
string_lists, even if that's not the case here, so I don't think that's
the right place.

We could add an assert(rename->remote_branches->strdup_strings) before
the string_list_append() call instead, which would document that
requirement in the right place in a way that shouldn't get out of sync
silently, but I'm not sure it's worth it here.

>>  if (!refspec_updated)
>>  return 0;
>>   
>>  /*
>>   * First remove symrefs, then rename the rest, finally create
>>   * the new symrefs.
>>   */
>>  for_each_ref(read_remote_branches, );
> 
> As you noted, this is the first caller that writes to the string_list,
> so we don't have to worry about the 'return 0' above.  That said, I
> wonder if it might be simpler and more futureproof to use
> destructor-style cleanup handling anyway:
> 
>   if (!refspec_updated)
>   goto done;
>   [...]
>done:
>   string_list_clear(_branches, 1);
>   return 0;

There are some more early returns higher up, which would have to be
adjusted as well.  Such a restructuring would be helpful if we decide
to release the various strbufs in that function as well..

But perhaps the main problem is that the function is too long. Could
it be split up into sensible parts with a lower number of allocations
each that can be kept track of more easily?

(Sounds like a bigger bite than I can chew at the moment, though.)

>> +string_list_clear(_branches, 1);
> 
> not about this patch: I wonder if we should make the free_util
> parameter a flag word so the behavior is more obvious in the caller:
> 
>   string_list_clear(_branches, STRING_LIST_FREE_UTIL);
> 
> Or maybe even having a separate function:
> 
>   string_list_clear_free_util(_branches);

I agree that naming variants instead of using binary options is a good
idea in general, as it makes the code self-documenting.

I'd like to suggest another option: remove the second parameter of
string_list_clear() and add string_list_free_util(), which only free(3)s
->util pointers.  Users that attached heap objects to string_list items
would have to call both functions; no need to glue them together.

René

[PATCH] remote: clear string_list after use in mv()

[René Scharfe]

Switch to the _DUP variant of string_list for remote_branches to allow
string_list_clear() to release the allocated memory at the end, and
actually call that function.  Free the util pointer as well; it is
allocated in read_remote_branches().

NB: This string_list is empty until read_remote_branches() is called
via for_each_ref(), so there is no need to clean it up when returning
before that point.

Signed-off-by: Rene Scharfe 
---
Patch generated with ---function-context for easier review -- that
makes it look much bigger than it actually is, though.

 builtin/remote.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/builtin/remote.c b/builtin/remote.c
index c74ee88690..07bd51f8eb 100644
--- a/builtin/remote.c
+++ b/builtin/remote.c
@@ -558,23 +558,23 @@ struct rename_info {
 static int read_remote_branches(const char *refname,
const struct object_id *oid, int flags, void *cb_data)
 {
struct rename_info *rename = cb_data;
struct strbuf buf = STRBUF_INIT;
struct string_list_item *item;
int flag;
const char *symref;
 
strbuf_addf(, "refs/remotes/%s/", rename->old_name);
if (starts_with(refname, buf.buf)) {
-   item = string_list_append(rename->remote_branches, 
xstrdup(refname));
+   item = string_list_append(rename->remote_branches, refname);
symref = resolve_ref_unsafe(refname, RESOLVE_REF_READING,
NULL, );
if (symref && (flag & REF_ISSYMREF))
item->util = xstrdup(symref);
else
item->util = NULL;
}
strbuf_release();
 
return 0;
 }
@@ -607,133 +607,134 @@ static int migrate_file(struct remote *remote)
 static int mv(int argc, const char **argv)
 {
struct option options[] = {
OPT_END()
};
struct remote *oldremote, *newremote;
struct strbuf buf = STRBUF_INIT, buf2 = STRBUF_INIT, buf3 = STRBUF_INIT,
old_remote_context = STRBUF_INIT;
-   struct string_list remote_branches = STRING_LIST_INIT_NODUP;
+   struct string_list remote_branches = STRING_LIST_INIT_DUP;
struct rename_info rename;
int i, refspec_updated = 0;
 
if (argc != 3)
usage_with_options(builtin_remote_rename_usage, options);
 
rename.old_name = argv[1];
rename.new_name = argv[2];
rename.remote_branches = _branches;
 
oldremote = remote_get(rename.old_name);
if (!remote_is_configured(oldremote, 1))
die(_("No such remote: %s"), rename.old_name);
 
if (!strcmp(rename.old_name, rename.new_name) && oldremote->origin != 
REMOTE_CONFIG)
return migrate_file(oldremote);
 
newremote = remote_get(rename.new_name);
if (remote_is_configured(newremote, 1))
die(_("remote %s already exists."), rename.new_name);
 
strbuf_addf(, "refs/heads/test:refs/remotes/%s/test", 
rename.new_name);
if (!valid_fetch_refspec(buf.buf))
die(_("'%s' is not a valid remote name"), rename.new_name);
 
strbuf_reset();
strbuf_addf(, "remote.%s", rename.old_name);
strbuf_addf(, "remote.%s", rename.new_name);
if (git_config_rename_section(buf.buf, buf2.buf) < 1)
return error(_("Could not rename config section '%s' to '%s'"),
buf.buf, buf2.buf);
 
strbuf_reset();
strbuf_addf(, "remote.%s.fetch", rename.new_name);
git_config_set_multivar(buf.buf, NULL, NULL, 1);
strbuf_addf(_remote_context, ":refs/remotes/%s/", rename.old_name);
for (i = 0; i < oldremote->fetch.raw_nr; i++) {
char *ptr;
 
strbuf_reset();
strbuf_addstr(, oldremote->fetch.raw[i]);
ptr = strstr(buf2.buf, old_remote_context.buf);
if (ptr) {
refspec_updated = 1;
strbuf_splice(,
  ptr-buf2.buf + strlen(":refs/remotes/"),
  strlen(rename.old_name), rename.new_name,
  strlen(rename.new_name));
} else
warning(_("Not updating non-default fetch refspec\n"
  "\t%s\n"
  "\tPlease update the configuration manually 
if necessary."),
buf2.buf);
 
git_config_set_multivar(buf.buf, buf2.buf, "^$", 0);
}
 
read_branches();
for (i = 0; i < branch_list.nr; i++) {
struct string_list_item *item = branch_list.items + i;
struct branch_info *info = item->util;
if (info->remote_name && !strcmp(info->remote_name, 
rename.old_name)) {

Re: git merge -s subtree seems to be broken.

[René Scharfe]

Am 31.07.2018 um 17:50 schrieb Jeff King:
> On Tue, Jul 31, 2018 at 11:03:17AM -0400, George Shammas wrote:
> 
>> Bisecting around, this might be the commit that introduced the breakage.
>>
>> https://github.com/git/git/commit/d8febde
>>
>> I really hope that it hasn't been broken for 5 years and I am just doing
>> something wrong.
> 
> Unfortunately, I think it has been broken for five years.

I don't remember this change at all. :-(  Sorry for the trouble, everyone.
I should feel ashamed, but I'm only staring in bewilderment.

René

Re: git merge -s subtree seems to be broken.

[René Scharfe]

Am 31.07.2018 um 23:06 schrieb Junio C Hamano:
> Jeff King  writes:
> 
>> On Tue, Jul 31, 2018 at 01:23:04PM -0400, Jeff King wrote:
>> ...
>> So here it is fixed, and with a commit message. I'm not happy to omit a
>> regression test, but I actually couldn't come up with a minimal one that
>> tickled the problem, because we're playing around with heuristics.
How about something like this? (squashable)

---
 t/t6029-merge-subtree.sh | 28 
 1 file changed, 28 insertions(+)

diff --git a/t/t6029-merge-subtree.sh b/t/t6029-merge-subtree.sh
index 3e692454a7..474a850de6 100755
--- a/t/t6029-merge-subtree.sh
+++ b/t/t6029-merge-subtree.sh
@@ -29,6 +29,34 @@ test_expect_success 'subtree available and works like 
recursive' '
 
 '
 
+test_expect_success 'setup branch sub' '
+   git checkout --orphan sub &&
+   git rm -rf . &&
+   test_commit foo
+'
+
+test_expect_success 'setup branch main' '
+   git checkout -b main master &&
+   git merge -s ours --no-commit --allow-unrelated-histories sub &&
+   git read-tree --prefix=dir/ -u sub &&
+   git commit -m "initial merge of sub into main" &&
+   test_path_is_file dir/foo.t &&
+   test_path_is_file hello
+'
+
+test_expect_success 'update branch sub' '
+   git checkout sub &&
+   test_commit bar
+'
+
+test_expect_success 'update branch main' '
+   git checkout main &&
+   git merge -s subtree sub -m "second merge of sub into main" &&
+   test_path_is_file dir/bar.t &&
+   test_path_is_file dir/foo.t &&
+   test_path_is_file hello
+'
+
 test_expect_success 'setup' '
mkdir git-gui &&
cd git-gui &&
-- 
2.18.0

Re: Proposed approaches to supporting HTTP remotes in "git archive"

[René Scharfe]

Am 28.07.2018 um 00:32 schrieb Junio C Hamano:
> Josh Steadmon  writes:
> 
>> # Supporting HTTP remotes in "git archive"
>>
>> We would like to allow remote archiving from HTTP servers. There are a
>> few possible implementations to be discussed:
>>
>> ## Shallow clone to temporary repo
>>
>> This approach builds on existing endpoints. Clients will connect to the
>> remote server's git-upload-pack service and fetch a shallow clone of the
>> requested commit into a temporary local repo. The write_archive()
>> function is then called on the local clone to write out the requested
>> archive.

A prototype would require just a few lines of shell script, I guess..

A downside that was only stated implicitly: This method needs temporary
disk space for the clone, while the existing archive modes only ever
write out the resulting file.  I guess the required space is in the same
order as the compressed archive.  This shouldn't be a problem if we
assume the user would eventually want to extract its contents, right?

>> ## Summary
>>
>> Personally, I lean towards the first approach. It could give us an
>> opportunity to remove server-side complexity; there is no reason that
>> the shallow-clone approach must be restricted to the HTTP transport, and
>> we could re-implement other transports using this method.  Additionally,
>> it would allow clients to pull archives from remotes that would not
>> otherwise support it.
> 
> I consider the first one (i.e. make a shallow clone and tar it up
> locally) a hack that does *not* belong to "git archive --remote"
> command, especially when it is only done to "http remotes".  The
> only reason HTTP remotes are special is because there is no ready
> "http-backend" equivalent that passes the "git archive" traffic over
> smart-http transport, unlike the one that exists for "git
> upload-pack".
> 
> It however still _is_ attractive to drive such a hack from "git
> archive" at the UI level, as the end users do not care how ugly the
> hack is ;-)  As you mentioned, the approach would work for any
> transport that allows one-commit shallow clone, so it might become
> more palatable if it is designed as a different _mode_ of operation
> of "git archive" that is orthogonal to the underlying transport,
> i.e.
> 
>$ git archive --remote= --shallow-clone-then-local-archive-hack 
> master
> 
> or
> 
>$ git config archive..useShallowCloneThenLocalArchiveHack true
>$ git archive --remote= master

Archive-via-clone would also work with full clones (if shallow ones are
not available), but that would be wasteful and a bit cruel, of course.

Anyway, I think we should find a better (shorter) name for that option;
that could turn out to be the hardest part. :)

> It might turn out that it may work better than the native "git
> archive" access against servers that offer both shallow clone
> and native archive access.  I doubt a single-commit shallow clone
> would benefit from reusing of premade deltas and compressed bases
> streamed straight out of packfiles from the server side that much,
> but you'd never know until you measure ;-)

It could benefit from GIT_ALTERNATE_OBJECT_DIRECTORIES, but I guess
typical users of git archive --remote won't have any good ones lying
around.

René

Re: [PATCH 0/5] Misc Coccinelle-related improvements

[René Scharfe]

Am 23.07.2018 um 15:50 schrieb SZEDER Gábor:
> Just a couple of minor Coccinelle-related improvements:
> 
>- The first two patches are small cleanups.
> 
>- The last three could make life perhaps just a tad bit easier for
>  devs running 'make coccicheck'.
> 
> 
> SZEDER Gábor (5):
>coccinelle: mark the 'coccicheck' make target as .PHONY
>coccinelle: use $(addsuffix) in 'coccicheck' make target
>coccinelle: exclude sha1dc source files from static analysis
>coccinelle: put sane filenames into output patches
>coccinelle: extract dedicated make target to clean Coccinelle's
>  results

These patches look good to me.  Thanks a lot!

René

Re: [PATCH 0/7] grep.c: teach --column to 'git-grep(1)'

[René Scharfe]

Am 19.06.2018 um 21:11 schrieb Jeff King:
> On Tue, Jun 19, 2018 at 08:50:16PM +0200, René Scharfe wrote:
> 
>> Negation causes the whole non-matching line to match, with --column
>> reporting 1 or nothing in such a case, right?  Or I think doing the
>> same when the operator is applied a second time is explainable.

(Not sure where that extra "Or" came from.)

> Yes to your first question.
> 
> Regarding the final sentence, yes, I agree it's explainable. But I
> thought that handling negation like this was one of the main complaints
> of earlier iterations?

That's possible -- I didn't read the full thread, and I didn't argue
for or against any specific behavior in this regard before AFAIR.

So let's see what your example does:

   $ git grep --column --not \( --not -e foo --or --not -e bar \) trace.h
   trace.h:13: *  #define foo(format, ...) bar(format, __VA_ARGS__)
   $ git grep --column --not \( --not -e bar --or --not -e foo \) trace.h
   trace.h:13: *  #define foo(format, ...) bar(format, __VA_ARGS__)

Impressive.  That expression is confusing at first sight, but showing
the first matching column anyway requires no further explanation.  I
like it.

René

Re: [PATCH 0/7] grep.c: teach --column to 'git-grep(1)'

[René Scharfe]

Am 19.06.2018 um 19:44 schrieb Taylor Blau:
> diff --git a/grep.c b/grep.c
> index f3329d82ed..a09935d8c5 100644
> --- a/grep.c
> +++ b/grep.c
> @@ -1257,8 +1257,8 @@ static int match_one_pattern(struct grep_pat *p, char 
> *bol, char *eol,
>   return hit;
>   }
> 
> -static int match_expr_eval(struct grep_expr *x, char *bol, char *eol,
> -enum grep_context ctx, ssize_t *col,
> +static int match_expr_eval(struct grep_opt *opt, struct grep_expr *x, char 
> *bol,
> +char *eol, enum grep_context ctx, ssize_t *col,
>  ssize_t *icol, int collect_hits)

Passing opt in is one way.  Piggy-backing on collect_hits and making it
a flags parameter for two bits might be easier.  At least it wouldn't
increase the number of function arguments any further.  Not sure.

Anyway, something like this would be needed as well; or we could
force opt->columnnum to switch opt->extended on:

diff --git a/grep.c b/grep.c
index 8ffa94c791..a724ca3010 100644
--- a/grep.c
+++ b/grep.c
@@ -1325,6 +1321,7 @@ static int match_line(struct grep_opt *opt, char *bol, 
char *eol,
  enum grep_context ctx, int collect_hits)
 {
struct grep_pat *p;
+   int hit = 0;
 
if (opt->extended)
return match_expr(opt, bol, eol, ctx, col, icol,
@@ -1334,11 +1331,14 @@ static int match_line(struct grep_opt *opt, char *bol, 
char *eol,
for (p = opt->pattern_list; p; p = p->next) {
regmatch_t tmp;
if (match_one_pattern(p, bol, eol, ctx, , 0)) {
-   *col = tmp.rm_so;
-   return 1;
+   hit |= 1;
+   if (!opt->columnnum)
+   break;
+   if (*col < 0 || tmp.rm_so < *col)
+   *col = tmp.rm_so;
}
}
-   return 0;
+   return hit;
 }
 
 static int match_next_pattern(struct grep_pat *p, char *bol, char *eol,

Re: [PATCH 0/7] grep.c: teach --column to 'git-grep(1)'

[René Scharfe]

Am 19.06.2018 um 19:48 schrieb Jeff King:
> On Tue, Jun 19, 2018 at 07:33:39PM +0200, René Scharfe wrote:
> 
>>> The key thing about this iteration is that it doesn't regress
>>> performance, because we always short-circuit where we used to. The other
>>> obvious route is to stop short-circuiting only when "--column" is in
>>> effect, which would have the same property (at the expense of a little
>>> extra code in match_expr_eval()).
>>
>> The performance impact of the exhaustive search for --color scales with
>> the number of shown lines, while it would scale with the total number of
>> lines for --column.  Coloring the results of highly selective patterns
>> is relatively cheap, short-circuiting them still helps significantly.
> 
> I thought that at first, too, but I think we'd still scale with the
> number of shown lines. We're talking about short-circuiting OR, so by
> definition we stop the short-circuit because we matched the first half
> of the OR.
> 
> If you stop short-circuiting AND, then yes, you incur a penalty for
> every line. But I don't think --column would need to do that.

Good point.  So disabling that optimization for --column (or in even
in general) shouldn't be a dramatic loss.

> Although there are interesting cases around inversion. For example:
> 
>git grep --not \( --not -e a --and --not -e b \)
> 
> is equivalent to:
> 
>git grep -e a --or -e b
> 
> Do people care if we actually hunt down the exact column where we
> _didn't_ match "b" in the first case?  The two are equivalent, but I
> have to wonder if somebody writing the first one really cares.

I'd rather not guess the intentions of someone using such convoluted
expressions. ;-)

Negation causes the whole non-matching line to match, with --column
reporting 1 or nothing in such a case, right?  Or I think doing the
same when the operator is applied a second time is explainable.

>> Disabling that optimization for --column wouldn't be a regression since
>> it's a new option..  Picking a random result (based on the order of
>> evaluation) seems sloppy and is probably going to surprise users.
> 
> I don't see it as a random result; short-circuiting logic is well
> understood and we follow the user's ordering.

When ORing multiple expressions I don't pay attention to their order
as that operator is commutative.  Having results depend on that
order would at least surprise me.

> I think the place where it's _most_ ugly is "--column --color", where we
> may color the short-circuited value in the second pass.

The double negative example you gave above has that discrepancy as
well, but I think in that case it just highlights the different
intentions (--color: highlight search terms, --column: show leftmost
match).

>> We could add an optimizer pass to reduce the number of regular
>> expressions in certain cases if that is really too slow.  E.g. this:
> 
> Yes, we actually discussed this kind of transformation. I think it's way
> out of scope for this patch series, though. If we do anything more, I
> think it should be to disable short-circuiting when --column is in use.

Yep.

René

Re: [PATCH 0/7] grep.c: teach --column to 'git-grep(1)'

[René Scharfe]

Am 19.06.2018 um 19:44 schrieb Taylor Blau:
> On Tue, Jun 19, 2018 at 07:33:39PM +0200, René Scharfe wrote:
>> Am 19.06.2018 um 18:35 schrieb Jeff King:
>>> On Mon, Jun 18, 2018 at 06:43:01PM -0500, Taylor Blau wrote:
>> We could add an optimizer pass to reduce the number of regular
>> expressions in certain cases if that is really too slow.  E.g. this:
>>
>>  $ git grep -e b -e a
>>
>> ... is equivalent to:
>>
>>  $ git grep -e '\(b\)\|\(a\)'
>>
>> In that example the optimizer should use a single kwset instead of a
>> regex, but you get the idea, namely to leave the short-circuiting to the
>> regex engine or kwset, which probably do a good job of it.
> 
> I think that--while this pushes that decision to the appropriate level
> of indirection--that it is out of scope for this series, and that the
> above patch should do a sufficient job at not surprising users.

Definitely.  I'm not even convinced that performance problem is real --
otherwise someone would have added such an optimization already, right?
:)

René

Re: [PATCH 0/7] grep.c: teach --column to 'git-grep(1)'

[René Scharfe]

Am 19.06.2018 um 18:35 schrieb Jeff King:
> On Mon, Jun 18, 2018 at 06:43:01PM -0500, Taylor Blau wrote:
>> The notable case that it does _not_ cover is matching the following
>> line:
>>
>>a ... b
>>
>> with the following expression
>>
>>git grep --column -e b --or -e a
>>
>> This will produce the column for 'b' rather than the column for 'a',
>> since we short-circuit an --or when the left child finds a match, in
>> this case 'b'. So, we break the semantics for this case, at the benefit
>> of not having to do twice the work.
>>
>> In the future, I'd like to revisit this, since any performance gains
>> that we _do_ make in this area are moot when we rescan all lines in
>> show_line() with --color. A path forward, I imagine, would look like a
>> list of regmatch_t's, or a set of locations in the expression tree, such
>> that we could either enumerate the list or walk the tree in order to
>> colorize the line. But, I think for now that is #leftoverbits.
> 
> The key thing about this iteration is that it doesn't regress
> performance, because we always short-circuit where we used to. The other
> obvious route is to stop short-circuiting only when "--column" is in
> effect, which would have the same property (at the expense of a little
> extra code in match_expr_eval()).

The performance impact of the exhaustive search for --color scales with
the number of shown lines, while it would scale with the total number of
lines for --column.  Coloring the results of highly selective patterns
is relatively cheap, short-circuiting them still helps significantly.

Disabling that optimization for --column wouldn't be a regression since
it's a new option..  Picking a random result (based on the order of
evaluation) seems sloppy and is probably going to surprise users.

We could add an optimizer pass to reduce the number of regular
expressions in certain cases if that is really too slow.  E.g. this:

$ git grep -e b -e a

... is equivalent to:

$ git grep -e '\(b\)\|\(a\)'

In that example the optimizer should use a single kwset instead of a
regex, but you get the idea, namely to leave the short-circuiting to the
regex engine or kwset, which probably do a good job of it.

René

Re: [PATCH 24/30] merge-recursive: Add computation of collisions due to dir rename & merging

[René Scharfe]

Am 10.06.2018 um 12:56 schrieb René Scharfe:
> Am 10.11.2017 um 20:05 schrieb Elijah Newren:
>> +static struct dir_rename_entry *check_dir_renamed(const char *path,
>> +  struct hashmap *dir_renames) {
>> +char temp[PATH_MAX];
>> +char *end;
>> +struct dir_rename_entry *entry;
>> +
>> +strcpy(temp, path);
>> +while ((end = strrchr(temp, '/'))) {
>> +*end = '\0';
>> +entry = dir_rename_find_entry(dir_renames, temp);
>> +if (entry)
>> +return entry;
>> +}
>> +return NULL;
>> +}
> 
> The value of PATH_MAX is platform-dependent, so it's easy to exceed when
> doing cross-platform development.  It's also not a hard limit on most
> operating systems, not even on Windows.  Further reading:
> 
> https://insanecoding.blogspot.com/2007/11/pathmax-simply-isnt.html
> 
> So using a fixed buffer is not a good idea, and writing to it without
> checking is dangerous.  Here's a fix:

Argh, I meant to reply to v10 of that patch, i.e. this:

   https://public-inbox.org/git/20180419175823.7946-21-new...@gmail.com/

The cited code wasn't changed and is in current master, though, so both
that part and my patch are still relevant.

René

Re: [PATCH 24/30] merge-recursive: Add computation of collisions due to dir rename & merging

[René Scharfe]

Am 10.11.2017 um 20:05 schrieb Elijah Newren:
> +static struct dir_rename_entry *check_dir_renamed(const char *path,
> +   struct hashmap *dir_renames) {
> + char temp[PATH_MAX];
> + char *end;
> + struct dir_rename_entry *entry;
> +
> + strcpy(temp, path);
> + while ((end = strrchr(temp, '/'))) {
> + *end = '\0';
> + entry = dir_rename_find_entry(dir_renames, temp);
> + if (entry)
> + return entry;
> + }
> + return NULL;
> +}

The value of PATH_MAX is platform-dependent, so it's easy to exceed when
doing cross-platform development.  It's also not a hard limit on most
operating systems, not even on Windows.  Further reading:

   https://insanecoding.blogspot.com/2007/11/pathmax-simply-isnt.html

So using a fixed buffer is not a good idea, and writing to it without
checking is dangerous.  Here's a fix:

-- >8 --
Subject: [PATCH] merge-recursive: use xstrdup() instead of fixed buffer

Paths can be longer than PATH_MAX.  Avoid a buffer overrun in
check_dir_renamed() by using xstrdup() to make a private copy safely.

Signed-off-by: Rene Scharfe 
---
 merge-recursive.c | 10 +-
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index ac27abbd4c..db708176c5 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -2211,18 +2211,18 @@ static struct hashmap *get_directory_renames(struct 
diff_queue_struct *pairs,
 static struct dir_rename_entry *check_dir_renamed(const char *path,
  struct hashmap *dir_renames)
 {
-   char temp[PATH_MAX];
+   char *temp = xstrdup(path);
char *end;
-   struct dir_rename_entry *entry;
+   struct dir_rename_entry *entry = NULL;;
 
-   strcpy(temp, path);
while ((end = strrchr(temp, '/'))) {
*end = '\0';
entry = dir_rename_find_entry(dir_renames, temp);
if (entry)
-   return entry;
+   break;
}
-   return NULL;
+   free(temp);
+   return entry;
 }
 
 static void compute_collisions(struct hashmap *collisions,
-- 
2.17.1

Re: [PATCH 2/2] builtin/blame: highlight recently changed lines

[René Scharfe]

Am 17.04.2018 um 23:30 schrieb Stefan Beller:
> +static void parse_color_fields(const char *s)
> +{
> + struct string_list l = STRING_LIST_INIT_DUP;
> + struct string_list_item *item;
> + enum { EXPECT_DATE, EXPECT_COLOR } next = EXPECT_COLOR;
> +
> + colorfield_nr = 0;
> +
> + /* Ideally this would be stripped and split at the same time? */

Why?  Both approxidate() and color_parse() handle spaces.

> + string_list_split(, s, ',', -1);
> + ALLOC_GROW(colorfield, colorfield_nr + 1, colorfield_alloc);
> +
> + for_each_string_list_item(item, ) {
> + switch (next) {
> + case EXPECT_DATE:
> + colorfield[colorfield_nr].hop = 
> approxidate(item->string);
> + next = EXPECT_COLOR;
> + colorfield_nr++;
> + ALLOC_GROW(colorfield, colorfield_nr + 1, 
> colorfield_alloc);
> + break;
> + case EXPECT_COLOR:
> + if (color_parse(item->string, 
> colorfield[colorfield_nr].col))
> + die(_("expecting a color: %s"), item->string);
> + next = EXPECT_DATE;
> + break;
> + }
> + }
> +
> + if (next == EXPECT_COLOR)
> + die (_("must end with a color"));
> +
> + colorfield[colorfield_nr].hop = TIME_MAX;
> +}

This adds a minor memory leak; fix below.

-- >8 --
Subject: [PATCH] blame: release string_list after use in parse_color_fields()

Signed-off-by: Rene Scharfe 
---
 builtin/blame.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/builtin/blame.c b/builtin/blame.c
index 4202584f97..3295718841 100644
--- a/builtin/blame.c
+++ b/builtin/blame.c
@@ -411,6 +411,7 @@ static void parse_color_fields(const char *s)
die (_("must end with a color"));
 
colorfield[colorfield_nr].hop = TIME_MAX;
+   string_list_clear(, 0);
 }
 
 static void setup_default_color_by_age(void)
-- 
2.17.1

Re: [PATCH v8 1/2] json_writer: new routines to create data in JSON format

[René Scharfe]

Am 07.06.2018 um 16:12 schrieb g...@jeffhostetler.com:
>   Makefile|   2 +
>   json-writer.c   | 419 
>   json-writer.h   | 113 +
>   t/helper/test-json-writer.c | 572 
> 
>   t/t0019-json-writer.sh  | 236 ++
>   5 files changed, 1342 insertions(+)
>   create mode 100644 json-writer.c
>   create mode 100644 json-writer.h
>   create mode 100644 t/helper/test-json-writer.c
>   create mode 100755 t/t0019-json-writer.sh

$ git grep 'static inline' '*json*'
json-writer.c:static inline void indent_pretty(struct json_writer *jw)
json-writer.c:static inline void begin(struct json_writer *jw, char ch_open, 
int pretty)
json-writer.c:static inline void assert_in_object(const struct json_writer *jw, 
const char *key)
json-writer.c:static inline void assert_in_array(const struct json_writer *jw)
json-writer.c:static inline void maybe_add_comma(struct json_writer *jw)
json-writer.c:static inline void fmt_double(struct json_writer *jw, int 
precision,
json-writer.c:static inline void object_common(struct json_writer *jw, const 
char *key)
json-writer.c:static inline void array_common(struct json_writer *jw)
json-writer.c:static inline void assert_is_terminated(const struct json_writer 
*jw)
t/helper/test-json-writer.c:static inline int scripted(int argc, const char 
**argv)
t/helper/test-json-writer.c:static inline int my_usage(void)

Do you need all those inline keywords?  I'd rather leave the decision
about inlining to the compiler and (via optimization flags) the user
as much as possible.  Not a biggie, but the high frequency of that
word made me blink..

René

Re: [PATCH v8 1/2] json_writer: new routines to create data in JSON format

[René Scharfe]

Am 07.06.2018 um 16:12 schrieb g...@jeffhostetler.com:
> From: Jeff Hostetler 
> +/*
> + * Add comma if we have already seen a member at this level.
> + */
> +static inline void maybe_add_comma(struct json_writer *jw)
> +{
> + if (!jw->open_stack.len)
> + return;

This is impossible.  maybe_add_comma() is only called directly after
assert_in_object() and assert_in_object(), which abort if open_stack 
is empty.

> + if (jw->first_stack.buf[jw->first_stack.len - 1] == '1')
> + jw->first_stack.buf[jw->first_stack.len - 1] = '0';
> + else
> + strbuf_addch(>json, ',');

You only need a binary flag to indicate if a comma is needed, not a
stack.  We need a comma at the current level if and only if we already
wrote a child item.  If we finish a level then we do need a comma at the
previous level because we just wrote a sub-object or sub-array there.
And that should cover all cases.  Am I missing something?

I get a sense of déjà vu, by the way. :)

Here's what I mean:
---
 json-writer.c | 17 ++---
 json-writer.h | 13 +
 2 files changed, 11 insertions(+), 19 deletions(-)

diff --git a/json-writer.c b/json-writer.c
index f35ce1912a..14a4e89188 100644
--- a/json-writer.c
+++ b/json-writer.c
@@ -5,7 +5,7 @@ void jw_init(struct json_writer *jw)
 {
strbuf_reset(>json);
strbuf_reset(>open_stack);
-   strbuf_reset(>first_stack);
+   jw->need_comma = 0;
jw->pretty = 0;
 }
 
@@ -13,7 +13,6 @@ void jw_release(struct json_writer *jw)
 {
strbuf_release(>json);
strbuf_release(>open_stack);
-   strbuf_release(>first_stack);
 }
 
 /*
@@ -69,7 +68,7 @@ static inline void begin(struct json_writer *jw, char 
ch_open, int pretty)
strbuf_addch(>json, ch_open);
 
strbuf_addch(>open_stack, ch_open);
-   strbuf_addch(>first_stack, '1');
+   jw->need_comma = 0;
 }
 
 /*
@@ -99,12 +98,10 @@ static inline void assert_in_array(const struct json_writer 
*jw)
  */
 static inline void maybe_add_comma(struct json_writer *jw)
 {
-   if (!jw->open_stack.len)
-   return;
-   if (jw->first_stack.buf[jw->first_stack.len - 1] == '1')
-   jw->first_stack.buf[jw->first_stack.len - 1] = '0';
-   else
+   if (jw->need_comma)
strbuf_addch(>json, ',');
+   else
+   jw->need_comma = 1;
 }
 
 static inline void fmt_double(struct json_writer *jw, int precision,
@@ -397,8 +394,6 @@ void jw_end(struct json_writer *jw)
char ch_open;
int len;
 
-   if (jw->open_stack.len != jw->first_stack.len)
-   BUG("jwon-writer: open_ and first_ stacks out of sync");
if (!jw->open_stack.len)
BUG("json-writer: too many jw_end(): '%s'", jw->json.buf);
 
@@ -406,7 +401,7 @@ void jw_end(struct json_writer *jw)
ch_open = jw->open_stack.buf[len];
 
strbuf_setlen(>open_stack, len);
-   strbuf_setlen(>first_stack, len);
+   jw->need_comma = 1;
 
if (jw->pretty)
strbuf_addch(>json, '\n');
diff --git a/json-writer.h b/json-writer.h
index af9c2612f8..c437462ba8 100644
--- a/json-writer.h
+++ b/json-writer.h
@@ -59,18 +59,15 @@ struct json_writer
struct strbuf open_stack;
 
/*
-* Another simple stack of the currently open array and object
-* forms.  This is used in parallel to "open_stack" (same length).
-* It contains a string of '1' and '0' where '1' indicates that
-* the next child-element seen will be the first child (and does
-* not need a leading comma).
+* Indicates if the next child item needs a leading comma.
+* Only the first item of arrays and objects doesn't need one.
 */
-   struct strbuf first_stack;
+   unsigned int need_comma:1;
 
-   int pretty;
+   unsigned int pretty:1;
 };
 
-#define JSON_WRITER_INIT { STRBUF_INIT, STRBUF_INIT, STRBUF_INIT, 0 }
+#define JSON_WRITER_INIT { STRBUF_INIT, STRBUF_INIT, 0, 0 }
 
 void jw_init(struct json_writer *jw);
 void jw_release(struct json_writer *jw);
-- 
2.17.1

Re: [PATCH v8 1/2] json_writer: new routines to create data in JSON format

[René Scharfe]

Am 07.06.2018 um 16:12 schrieb g...@jeffhostetler.com:
> From: Jeff Hostetler 
> 
> Add a series of jw_ routines and "struct json_writer" structure to compose
> JSON data.  The resulting string data can then be output by commands wanting
> to support a JSON output format.
> 
> The json-writer routines can be used to generate structured data in a
> JSON-like format.  We say "JSON-like" because we do not enforce the Unicode
> (usually UTF-8) requirement on string fields.  Internally, Git does not
> necessarily have Unicode/UTF-8 data for most fields, so it is currently
> unclear the best way to enforce that requirement.  For example, on Linx
> pathnames can contain arbitrary 8-bit character data, so a command like
> "status" would not know how to encode the reported pathnames.  We may want
> to revisit this (or double encode such strings) in the future.
> 
> The initial use for the json-writer routines is for generating telemetry
> data for executed Git commands.  Later, we may want to use them in other
> commands, such as status.
> 
> Helped-by: René Scharfe 
> Helped-by: Wink Saville 
> Helped-by: Ramsay Jones 
> Signed-off-by: Jeff Hostetler 
> ---
>   Makefile|   2 +
>   json-writer.c   | 419 
>   json-writer.h   | 113 +
>   t/helper/test-json-writer.c | 572 
> 
>   t/t0019-json-writer.sh  | 236 ++
>   5 files changed, 1342 insertions(+)
>   create mode 100644 json-writer.c
>   create mode 100644 json-writer.h
>   create mode 100644 t/helper/test-json-writer.c
>   create mode 100755 t/t0019-json-writer.sh
> 
> diff --git a/Makefile b/Makefile
> index a1d8775..4ae6946 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -666,6 +666,7 @@ TEST_PROGRAMS_NEED_X += test-fake-ssh
>  TEST_PROGRAMS_NEED_X += test-genrandom
>  TEST_PROGRAMS_NEED_X += test-hashmap
>  TEST_PROGRAMS_NEED_X += test-index-version
> +TEST_PROGRAMS_NEED_X += test-json-writer>  TEST_PROGRAMS_NEED_X += 
> test-lazy-init-name-hash
>  TEST_PROGRAMS_NEED_X += test-line-buffer
>  TEST_PROGRAMS_NEED_X += test-match-trees

This doesn't apply cleanly on master, because most test helpers have
been combined into a single binary to reduce their disk footprint and
link times.  See efd71f8913 (t/helper: add an empty test-tool program)
for the overall rationale.

test-json-writer could become a built-in as well, I think.  You can see
e.g. in c932a5ff28 (t/helper: merge test-string-list into test-tool)
what needs to be done to convert a helper.

René

Re: [PATCH 3/5] query_fsmonitor: use xsnprintf for formatting integers

[René Scharfe]

Am 19.05.2018 um 03:57 schrieb Jeff King:
> These formatted integers should always fit into their
> 64-byte buffers. Let's use xsnprintf() to add an assertion
> that this is the case, which makes auditing for other
> unchecked snprintfs() easier.

How about this instead?

-- >8 --
Subject: [PATCH] fsmonitor: use internal argv_array of struct child_process

Avoid magic array sizes and indexes by constructing the fsmonitor
command line using the embedded argv_array of the child_process.  The
resulting code is shorter and easier to extend.

Getting rid of the snprintf() calls is a bonus -- even though the
buffers were big enough here to avoid truncation -- as it makes auditing
the remaining callers easier.

Inspired-by: Jeff King 
Signed-off-by: Rene Scharfe 
---
 fsmonitor.c | 14 --
 1 file changed, 4 insertions(+), 10 deletions(-)

diff --git a/fsmonitor.c b/fsmonitor.c
index ed3d1a074d..665bd2d425 100644
--- a/fsmonitor.c
+++ b/fsmonitor.c
@@ -97,19 +97,13 @@ void write_fsmonitor_extension(struct strbuf *sb, struct 
index_state *istate)
 static int query_fsmonitor(int version, uint64_t last_update, struct strbuf 
*query_result)
 {
struct child_process cp = CHILD_PROCESS_INIT;
-   char ver[64];
-   char date[64];
-   const char *argv[4];
 
-   if (!(argv[0] = core_fsmonitor))
+   if (!core_fsmonitor)
return -1;
 
-   snprintf(ver, sizeof(ver), "%d", version);
-   snprintf(date, sizeof(date), "%" PRIuMAX, (uintmax_t)last_update);
-   argv[1] = ver;
-   argv[2] = date;
-   argv[3] = NULL;
-   cp.argv = argv;
+   argv_array_push(, core_fsmonitor);
+   argv_array_pushf(, "%d", version);
+   argv_array_pushf(, "%" PRIuMAX, (uintmax_t)last_update);
cp.use_shell = 1;
cp.dir = get_git_work_tree();
 
-- 
2.17.0

Re: [PATCH] fast-export: avoid NULL pointer arithmetic

[René Scharfe]

Am 14.05.2018 um 03:37 schrieb Junio C Hamano:
> René Scharfe <l@web.de> writes:
> 
>> Storing integer values in pointers is a trick that seems to have worked
>> so far for fast-export.  A portable way to avoid that trick without
>> requiring more memory would be to use a union.
>>
>> Or we could roll our own custom hash map, as I mused in an earlier post.
>> That would duplicate quite a bit of code; are there reusable pieces
>> hidden within that could be extracted into common functions?
> 
> Hmm, this together with your follow-up does not look too bad, but it
> does introduce quite a lot of code that could be refactored, so I am
> not sure if I really like it or not.

Putting keys and values into separate arrays probably causes stores and
lookups to hit (at least) two cache lines instead of just one.  Not sure
how much of an impact that has on the overall performance (probably not
much), but we'd need at least a perf test for that.

And we have enough hash map implementations already.

Casting should be good enough for now, to avoid the compiler warning.

René

Re: [PATCH] fast-export: avoid NULL pointer arithmetic

[René Scharfe]

Am 12.05.2018 um 10:45 schrieb René Scharfe:
> Or we could roll our own custom hash map, as I mused in an earlier post.
> That would duplicate quite a bit of code; are there reusable pieces
> hidden within that could be extracted into common functions?

At least it would allow us to save four bytes of padding per object on
x64 by using a separate array for the hash map values; not sure how that
would impact performance, though.

---
 builtin/fast-export.c | 15 +--
 1 file changed, 9 insertions(+), 6 deletions(-)

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index 627b0032f3..086fcaf9ea 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -72,13 +72,13 @@ static int parse_opt_tag_of_filtered_mode(const struct 
option *opt,
 
 struct object_mark_entry {
const struct object *base;
-   uint32_t mark;
 };
 
 struct object_marks {
unsigned int size;
unsigned int nr;
struct object_mark_entry *entries;
+   uint32_t *marks;
 };
 
 static struct object_marks idnums;
@@ -98,14 +98,14 @@ static void set_object_mark(struct object_marks *n, const 
struct object *base,
 
while (entries[j].base) {
if (entries[j].base == base) {
-   entries[j].mark = mark;
+   n->marks[j] = mark;
return;
}
if (++j >= size)
j = 0;
}
entries[j].base = base;
-   entries[j].mark = mark;
+   n->marks[j] = mark;
n->nr++;
 }
 
@@ -114,19 +114,22 @@ static void grow_object_marks(struct object_marks *n)
unsigned int i;
unsigned int old_size = n->size;
struct object_mark_entry *old_entries = n->entries;
+   uint32_t *old_marks = n->marks;
 
n->size = (old_size + 1000) * 3 / 2;
n->entries = xcalloc(n->size, sizeof(n->entries[0]));
+   n->marks = xcalloc(n->size, sizeof(n->marks[0]));
n->nr = 0;
 
for (i = 0; i < old_size; i++) {
const struct object *base = old_entries[i].base;
-   uint32_t mark = old_entries[i].mark;
+   uint32_t mark = old_marks[i];
 
if (mark)
set_object_mark(n, base, mark);
}
free(old_entries);
+   free(old_marks);
 }
 
 static int has_unshown_parent(struct commit *commit)
@@ -236,7 +239,7 @@ static int get_object_mark(struct object *object)
for (;;) {
struct object_mark_entry *ref = idnums.entries + j;
if (ref->base == object)
-   return ref->mark;
+   return idnums.marks[j];
if (!ref->base)
return 0;
if (++j == idnums.size)
@@ -966,7 +969,7 @@ static void export_marks(char *file)
 
for (i = 0; i < idnums.size; i++) {
if (entry->base && entry->base->type == 1) {
-   if (fprintf(f, ":%"PRIu32" %s\n", entry->mark,
+   if (fprintf(f, ":%"PRIu32" %s\n", idnums.marks[i],
oid_to_hex(>base->oid)) < 0) {
e = 1;
break;
-- 
2.17.0

Re: [PATCH v14 4/4] ls-remote: create '--sort' option

[René Scharfe]

Am 09.04.2018 um 03:42 schrieb Harald Nordgren:
> diff --git a/t/t5512-ls-remote.sh b/t/t5512-ls-remote.sh
> index 02106c922..83cd35c39 100755
> --- a/t/t5512-ls-remote.sh
> +++ b/t/t5512-ls-remote.sh

> @@ -170,14 +206,18 @@ test_expect_success 'overrides work between mixed 
> transfer/upload-pack hideRefs'
>   grep refs/tags/magic actual
>   '
>   
> +git fetch origin
>   test_expect_success 'ls-remote --symref' '
> - cat >expect <<-\EOF &&
> + cat >expect <<-EOF &&
>   ref: refs/heads/master  HEAD
> - 1bd44cb9d13204b0fe1958db0082f5028a16eb3aHEAD
> - 1bd44cb9d13204b0fe1958db0082f5028a16eb3arefs/heads/master
> - 1bd44cb9d13204b0fe1958db0082f5028a16eb3arefs/remotes/origin/HEAD
> - 1bd44cb9d13204b0fe1958db0082f5028a16eb3a
> refs/remotes/origin/master
> - 1bd44cb9d13204b0fe1958db0082f5028a16eb3arefs/tags/mark
> + $(git rev-parse HEAD)   HEAD
> + $(git rev-parse refs/heads/master)  refs/heads/master
> + $(git rev-parse HEAD)   refs/remotes/origin/HEAD
> + $(git rev-parse refs/remotes/origin/master) 
> refs/remotes/origin/master
> + $(git rev-parse refs/tags/mark) refs/tags/mark
> + $(git rev-parse refs/tags/mark1.1)  refs/tags/mark1.1
> + $(git rev-parse refs/tags/mark1.10) refs/tags/mark1.10
> + $(git rev-parse refs/tags/mark1.2)  refs/tags/mark1.2
>   EOF
>   git ls-remote --symref >actual &&
>   test_cmp expect actual

Why is fetch called outside of the test?  Its output is shown among the
test messages, where it doesn't belong:

ok 23 - overrides work between mixed transfer/upload-pack hideRefs
From /home/lsr/src/git/t/trash directory.t5512-ls-remote/
 * [new branch]  master -> origin/master
ok 24 - ls-remote --symref

-- >8 --
Subject: [PATCH] t5512: run git fetch inside test

Do the preparatory fetch inside the test of ls-remote --symref to avoid
cluttering the test output and to be able to catch unexpected fetch
failures.

Signed-off-by: Rene Scharfe 
---
 t/t5512-ls-remote.sh | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/t/t5512-ls-remote.sh b/t/t5512-ls-remote.sh
index 83cd35c391..6a949484d0 100755
--- a/t/t5512-ls-remote.sh
+++ b/t/t5512-ls-remote.sh
@@ -206,8 +206,8 @@ test_expect_success 'overrides work between mixed 
transfer/upload-pack hideRefs'
grep refs/tags/magic actual
 '
 
-git fetch origin
 test_expect_success 'ls-remote --symref' '
+   git fetch origin &&
cat >expect <<-EOF &&
ref: refs/heads/master  HEAD
$(git rev-parse HEAD)   HEAD
-- 
2.17.0

Re: [PATCH] fast-export: avoid NULL pointer arithmetic

[René Scharfe]

Am 11.05.2018 um 19:42 schrieb Jeff King:
> On Fri, May 11, 2018 at 03:34:19PM +0200, Duy Nguyen wrote:
> 
>> On Fri, May 11, 2018 at 03:11:46PM +0200, Duy Nguyen wrote:
>>> Back to fast-export, can we just allocate a new int on heap and point
>>> it there? Allocating small pieces becomes quite cheap and fast with
>>> mem-pool.h and we can avoid this storing integer in pointer business.
>>
>> Something like this seems to work, but we use 4-ish more bytes per
>> object, or 100MB overhead on a repo with 25M objects. I think it's a
>> reasonable trade off.
> 
> I'm not sure I agree. 4 bytes per object certainly isn't the end of the
> world, but what was the problem we were solving in the first place? Just
> that we weren't comfortable with the round-trip from uintptr_t to void
> and back? Is this actually a problem on real platforms? If not, it seems
> silly to incur a run-time cost.

Storing integer values in pointers is a trick that seems to have worked
so far for fast-export.  A portable way to avoid that trick without
requiring more memory would be to use a union.

Or we could roll our own custom hash map, as I mused in an earlier post.
That would duplicate quite a bit of code; are there reusable pieces
hidden within that could be extracted into common functions?

---
 builtin/fast-export.c | 105 --
 1 file changed, 81 insertions(+), 24 deletions(-)

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index 530df12f05..627b0032f3 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -14,7 +14,6 @@
 #include "diffcore.h"
 #include "log-tree.h"
 #include "revision.h"
-#include "decorate.h"
 #include "string-list.h"
 #include "utf8.h"
 #include "parse-options.h"
@@ -71,9 +70,65 @@ static int parse_opt_tag_of_filtered_mode(const struct 
option *opt,
return 0;
 }
 
-static struct decoration idnums;
+struct object_mark_entry {
+   const struct object *base;
+   uint32_t mark;
+};
+
+struct object_marks {
+   unsigned int size;
+   unsigned int nr;
+   struct object_mark_entry *entries;
+};
+
+static struct object_marks idnums;
 static uint32_t last_idnum;
 
+static unsigned int hash_obj(const struct object *obj, unsigned int n)
+{
+   return sha1hash(obj->oid.hash) % n;
+}
+
+static void set_object_mark(struct object_marks *n, const struct object *base,
+   uint32_t mark)
+{
+   unsigned int size = n->size;
+   struct object_mark_entry *entries = n->entries;
+   unsigned int j = hash_obj(base, size);
+
+   while (entries[j].base) {
+   if (entries[j].base == base) {
+   entries[j].mark = mark;
+   return;
+   }
+   if (++j >= size)
+   j = 0;
+   }
+   entries[j].base = base;
+   entries[j].mark = mark;
+   n->nr++;
+}
+
+static void grow_object_marks(struct object_marks *n)
+{
+   unsigned int i;
+   unsigned int old_size = n->size;
+   struct object_mark_entry *old_entries = n->entries;
+
+   n->size = (old_size + 1000) * 3 / 2;
+   n->entries = xcalloc(n->size, sizeof(n->entries[0]));
+   n->nr = 0;
+
+   for (i = 0; i < old_size; i++) {
+   const struct object *base = old_entries[i].base;
+   uint32_t mark = old_entries[i].mark;
+
+   if (mark)
+   set_object_mark(n, base, mark);
+   }
+   free(old_entries);
+}
+
 static int has_unshown_parent(struct commit *commit)
 {
struct commit_list *parent;
@@ -156,20 +211,13 @@ static void anonymize_path(struct strbuf *out, const char 
*path,
}
 }
 
-/* Since intptr_t is C99, we do not use it here */
-static inline uint32_t *mark_to_ptr(uint32_t mark)
-{
-   return ((uint32_t *)NULL) + mark;
-}
-
-static inline uint32_t ptr_to_mark(void * mark)
-{
-   return (uint32_t *)mark - (uint32_t *)NULL;
-}
-
 static inline void mark_object(struct object *object, uint32_t mark)
 {
-   add_decoration(, object, mark_to_ptr(mark));
+   unsigned int nr = idnums.nr + 1;
+
+   if (nr > idnums.size * 2 / 3)
+   grow_object_marks();
+   return set_object_mark(, object, mark);
 }
 
 static inline void mark_next_object(struct object *object)
@@ -179,10 +227,21 @@ static inline void mark_next_object(struct object *object)
 
 static int get_object_mark(struct object *object)
 {
-   void *decoration = lookup_decoration(, object);
-   if (!decoration)
+   unsigned int j;
+
+   /* nothing to lookup */
+   if (!idnums.size)
return 0;
-   return ptr_to_mark(decoration);
+   j = hash_obj(object, idnums.size);
+   for (;;) {
+   struct object_mark_entry *ref = idnums.entries + j;
+   if (ref->base == object)
+   return ref->mark;
+   if (!ref->base)
+   return 0;
+   if (++j == 

Re: [PATCH] fast-export: avoid NULL pointer arithmetic

[René Scharfe]

Am 10.05.2018 um 12:51 schrieb Junio C Hamano:
> René Scharfe <l@web.de> writes:
> 
>> The standard says about uintptr_t that "any valid pointer to void can
>> be converted to this type, then converted back to pointer to void, and
>> the result will compare equal to the original pointer".  So void * ->
>> uintptr_t -> void * is a proper roundtrip, but that doesn't imply that
>> casting arbitrary uintptr_t values to void * would be lossless.
>>
>> I don't know an architecture where this would bite us, but I wonder if
>> there is a cleaner way.  Perhaps changing the type of the decoration
>> member of struct decoration_entry in decorate.h to uintptr_t?
> 
> In order to ensure "void * -> uintptr_t -> void *" roundtrip holds,
> the implementation would guarantee that uintptr_t is wider than
> void*, so what you suggest technically makes sense.  We should be
> able to store any pointer in the field.  And we should be able to
> store any value of an unsigned integral type that is narrower than
> uintptr_t.
> 
> But it somehow feels backwards in spirit to me, as the reason why we
> use "void *" there in the decoration field is because we expect that
> we'd have a pointer to some struture most of the time, and we have
> to occasionally store a small integer there.

Yes, fast-export seems to be the only place that stores an integer as
a decoration.

>  So I'd naively expect
> that
> 
>   uint32_t mark = 23;
>   de->decoration = (void *)mark;
> 
> would be a good way to store mark #23 in the field and
> 
>   uint32_t mark;
>   mark = (typeof(mark))de->decoration;
> 
> would be a good way to read it off of the "void *" field.  Of
> course, this assume that (void *) is at least as wide as 32-bit and
> it also ignores the standard ;-)

Right, it looks deceptively good and works fine if memory is flat and
valid values for pointers are in a contiguous range starting at zero.
The standard allows for other models as well, though.

> This is an unrelated tangent but the mark-to-ptr() and ptr-to-mark()
> implementations feel wasteful, especially when we worry about 32-bit
> archs.  A naive platform implementation of
> 
>   (uint32_t *)mark - (uint32_t *)NULL;
> 
> would be ((uintptr_t)mark) / 4, i.e. the de->decoration field will
> always have two LSB clear and only utilize top 30-bit to represent
> the value of mark.

That's right, but I don't see what's naive about it, or how a 32-bit
architecture could avoid wasting those two bits.


Using struct decorate in fast-export has the benefit of not
requiring separate allocations for individual entries.  Switching to
struct hashmap would require individual allocations.  Adding a
custom clone of decorate with a uint32_t payload would be an option.

René