From: Eric Wong <hidden> Date: 2021-06-24 00:58:08
With many alternates, the duplicate check in alt_odb_usable()
wastes many cycles doing repeated fspathcmp() on every existing
alternate. Use a khash to speed up lookups by odb->path.
Since the kh_put_* API uses the supplied key without
duplicating it, we also take advantage of it to replace both
xstrdup() and strbuf_release() in link_alt_odb_entry() with
strbuf_detach() to avoid the allocation and copy.
In a test repository with 50K alternates and each of those 50K
alternates having one alternate each (for a total of 100K total
alternates); this speeds up lookup of a non-existent blob from
over 16 minutes to roughly 8 seconds on my busy workstation.
Note: all underlying git object directories were small and
unpacked with only loose objects and no packs. Having to load
packs increases times significantly.
Signed-off-by: Eric Wong <redacted>
---
Note: this project I'm doing this for probably won't have 100K
alternates yet, but ~60K is a possibility. I hope to find
more speedups along these lines.
object-file.c | 33 ++++++++++++++++++++++-----------
object-store.h | 17 +++++++++++++++++
object.c | 2 ++
3 files changed, 41 insertions(+), 11 deletions(-)
From: Eric Wong <hidden> Date: 2021-06-27 02:47:21
Cc-ing Rene and Peff for their previous work on loose object
caching speedups (and also Peff on crit-bit trees).
I'm expecting a use case involving tens of thousands of
repos being tied together by alternates. I realize this is
an odd case, but there's some fairly small changes that
give significant speedups and memory savings.
I can't seem to get consistent benchmarks on my workstation
(since it doubles as a public-facing server :x), but things
seem generally in the ballpark...
1/5 is a resend and the biggest obvious time improvement
(at some cost to space).
2/5 and 4/5 are pretty obvious; 3/5 should be obvious, too,
but my arithmetic is terrible :x
5/5 is a big (and easily measured) space improvement that
will negate space regression caused by 1/5 (and then some).
I'm not sure if there's much or any change in time in
either direction, though...
Eric Wong (5):
speed up alt_odb_usable() with many alternates
avoid strlen via strbuf_addstr in link_alt_odb_entry
make object_directory.loose_objects_subdir_seen a bitmap
oidcpy_with_padding: constify `src' arg
oidtree: a crit-bit tree for odb_loose_cache
Makefile | 3 +
alloc.c | 6 ++
alloc.h | 1 +
cbtree.c | 167 ++++++++++++++++++++++++++++++++++++++++
cbtree.h | 56 ++++++++++++++
hash.h | 2 +-
object-file.c | 68 +++++++++-------
object-name.c | 28 +++----
object-store.h | 24 +++++-
object.c | 2 +
oidtree.c | 94 ++++++++++++++++++++++
oidtree.h | 29 +++++++
t/helper/test-oidtree.c | 45 +++++++++++
t/helper/test-tool.c | 1 +
t/helper/test-tool.h | 1 +
t/t0069-oidtree.sh | 52 +++++++++++++
16 files changed, 530 insertions(+), 49 deletions(-)
create mode 100644 cbtree.c
create mode 100644 cbtree.h
create mode 100644 oidtree.c
create mode 100644 oidtree.h
create mode 100644 t/helper/test-oidtree.c
create mode 100755 t/t0069-oidtree.sh
From: Eric Wong <hidden> Date: 2021-06-27 02:47:27
We can save a few milliseconds (across 100K odbs) by using
strbuf_addbuf() instead of strbuf_addstr() by passing `entry' as
a strbuf pointer rather than a "const char *".
Signed-off-by: Eric Wong <redacted>
---
object-file.c | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
From: Eric Wong <hidden> Date: 2021-06-27 02:47:27
With many alternates, the duplicate check in alt_odb_usable()
wastes many cycles doing repeated fspathcmp() on every existing
alternate. Use a khash to speed up lookups by odb->path.
Since the kh_put_* API uses the supplied key without
duplicating it, we also take advantage of it to replace both
xstrdup() and strbuf_release() in link_alt_odb_entry() with
strbuf_detach() to avoid the allocation and copy.
In a test repository with 50K alternates and each of those 50K
alternates having one alternate each (for a total of 100K total
alternates); this speeds up lookup of a non-existent blob from
over 16 minutes to roughly 2.7 seconds on my busy workstation.
Note: all underlying git object directories were small and
unpacked with only loose objects and no packs. Having to load
packs increases times significantly.
Signed-off-by: Eric Wong <redacted>
---
object-file.c | 33 ++++++++++++++++++++++-----------
object-store.h | 17 +++++++++++++++++
object.c | 2 ++
3 files changed, 41 insertions(+), 11 deletions(-)
From: Eric Wong <hidden> Date: 2021-06-27 02:47:28
There's no point in using 8 bits per-directory when 1 bit
will do. This saves us 224 bytes per object directory, which
ends up being 22MB when dealing with 100K alternates.
Signed-off-by: Eric Wong <redacted>
---
object-file.c | 10 +++++++---
object-store.h | 2 +-
2 files changed, 8 insertions(+), 4 deletions(-)
From: Eric Wong <hidden> Date: 2021-06-27 02:47:34
As with `oidcpy', the source struct will not be modified and
this will allow an upcoming const-correct caller to use it.
Signed-off-by: Eric Wong <redacted>
---
hash.h | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
From: Eric Wong <hidden> Date: 2021-06-27 02:47:35
This saves 8K per `struct object_directory', meaning it saves
around 800MB in my case involving 100K alternates (half or more
of those alternates are unlikely to hold loose objects).
This is implemented in two parts: a generic, allocation-free
`cbtree' and the `oidtree' wrapper on top of it. The latter
provides allocation using alloc_state as a memory pool to
improve locality and reduce free(3) overhead.
Unlike oid-array, the crit-bit tree does not require sorting.
Performance is bound by the key length, for oidtree that is
fixed at sizeof(struct object_id). There's no need to have
256 oidtrees to mitigate the O(n log n) overhead like we did
with oid-array.
Being a prefix trie, it is natively suited for expanding short
object IDs via prefix-limited iteration in
`find_short_object_filename'.
On my busy workstation, p4205 performance seems to be roughly
unchanged (+/-8%). Startup with 100K total alternates with no
loose objects seems around 10-20% faster on a hot cache.
(800MB in memory savings means more memory for the kernel FS
cache).
The generic cbtree implementation does impose some extra
overhead for oidtree in that it uses memcmp(3) on
"struct object_id" so it wastes cycles comparing 12 extra bytes
on SHA-1 repositories. I've not yet explored reducing this
overhead, but I expect there are many places in our code base
where we'd want to investigate this.
More information on crit-bit trees: https://cr.yp.to/critbit.html
Signed-off-by: Eric Wong <redacted>
---
Makefile | 3 +
alloc.c | 6 ++
alloc.h | 1 +
cbtree.c | 167 ++++++++++++++++++++++++++++++++++++++++
cbtree.h | 56 ++++++++++++++
object-file.c | 17 ++--
object-name.c | 28 +++----
object-store.h | 5 +-
oidtree.c | 94 ++++++++++++++++++++++
oidtree.h | 29 +++++++
t/helper/test-oidtree.c | 45 +++++++++++
t/helper/test-tool.c | 1 +
t/helper/test-tool.h | 1 +
t/t0069-oidtree.sh | 52 +++++++++++++
14 files changed, 476 insertions(+), 29 deletions(-)
create mode 100644 cbtree.c
create mode 100644 cbtree.h
create mode 100644 oidtree.c
create mode 100644 oidtree.h
create mode 100644 t/helper/test-oidtree.c
create mode 100755 t/t0069-oidtree.sh
@@ -0,0 +1,167 @@+/*+*crit-bittreeimplementation,doesnoallocationsinternally+*Formoreinformationoncrit-bittrees:https://cr.yp.to/critbit.html+*BasedonAdamLangley'sadaptationofDanBernstein'spublicdomaincode+*gitclonehttps://github.com/agl/critbit.git+*/+#include"cbtree.h"++staticstructcb_node*cb_node_of(constvoid*p)+{+return(structcb_node*)((uintptr_t)p-1);+}++/* locate the best match, does not do a final comparision */+staticstructcb_node*cb_internal_best_match(structcb_node*p,+constuint8_t*k,size_tklen)+{+while(1&(uintptr_t)p){+structcb_node*q=cb_node_of(p);+uint8_tc=q->byte<klen?k[q->byte]:0;+size_tdirection=(1+(q->otherbits|c))>>8;++p=q->child[direction];+}+returnp;+}++/* returns NULL if successful, existing cb_node if duplicate */+structcb_node*cb_insert(structcb_tree*t,structcb_node*node,size_tklen)+{+size_tnewbyte,newotherbits;+uint8_tc;+intnewdirection;+structcb_node**wherep,*p;++assert(!((uintptr_t)node&1));/* allocations must be aligned */++if(!t->root){/* insert into empty tree */+t->root=node;+returnNULL;/* success */+}++/* see if a node already exists */+p=cb_internal_best_match(t->root,node->k,klen);++/* find first differing byte */+for(newbyte=0;newbyte<klen;newbyte++){+if(p->k[newbyte]!=node->k[newbyte])+gotodifferent_byte_found;+}+returnp;/* element exists, let user deal with it */++different_byte_found:+newotherbits=p->k[newbyte]^node->k[newbyte];+newotherbits|=newotherbits>>1;+newotherbits|=newotherbits>>2;+newotherbits|=newotherbits>>4;+newotherbits=(newotherbits&~(newotherbits>>1))^255;+c=p->k[newbyte];+newdirection=(1+(newotherbits|c))>>8;++node->byte=newbyte;+node->otherbits=newotherbits;+node->child[1-newdirection]=node;++/* find a place to insert it */+wherep=&t->root;+for(;;){+structcb_node*q;+size_tdirection;++p=*wherep;+if(!(1&(uintptr_t)p))+break;+q=cb_node_of(p);+if(q->byte>newbyte)+break;+if(q->byte==newbyte&&q->otherbits>newotherbits)+break;+c=q->byte<klen?node->k[q->byte]:0;+direction=(1+(q->otherbits|c))>>8;+wherep=q->child+direction;+}++node->child[newdirection]=*wherep;+*wherep=(structcb_node*)(1+(uintptr_t)node);++returnNULL;/* success */+}++structcb_node*cb_lookup(structcb_tree*t,constuint8_t*k,size_tklen)+{+structcb_node*p=cb_internal_best_match(t->root,k,klen);++returnp&&!memcmp(p->k,k,klen)?p:NULL;+}++structcb_node*cb_unlink(structcb_tree*t,constuint8_t*k,size_tklen)+{+structcb_node**wherep=&t->root;+structcb_node**whereq=NULL;+structcb_node*q=NULL;+size_tdirection=0;+uint8_tc;+structcb_node*p=t->root;++if(!p)returnNULL;/* empty tree, nothing to delete */++/* traverse to find best match, keeping link to parent */+while(1&(uintptr_t)p){+whereq=wherep;+q=cb_node_of(p);+c=q->byte<klen?k[q->byte]:0;+direction=(1+(q->otherbits|c))>>8;+wherep=q->child+direction;+p=*wherep;+}++if(memcmp(p->k,k,klen))+returnNULL;/* no match, nothing unlinked */++/* found an exact match */+if(whereq)/* update parent */+*whereq=q->child[1-direction];+else+t->root=NULL;+returnp;+}++staticenumcb_nextcb_descend(structcb_node*p,cb_iterfn,void*arg)+{+if(1&(uintptr_t)p){+structcb_node*q=cb_node_of(p);+enumcb_nextn=cb_descend(q->child[0],fn,arg);++returnn==CB_BREAK?n:cb_descend(q->child[1],fn,arg);+}else{+returnfn(p,arg);+}+}++voidcb_each(structcb_tree*t,constuint8_t*kpfx,size_tklen,+cb_iterfn,void*arg)+{+structcb_node*p=t->root;+structcb_node*top=p;+size_ti=0;++if(!p)return;/* empty tree */++/* Walk tree, maintaining top pointer */+while(1&(uintptr_t)p){+structcb_node*q=cb_node_of(p);+uint8_tc=q->byte<klen?kpfx[q->byte]:0;+size_tdirection=(1+(q->otherbits|c))>>8;++p=q->child[direction];+if(q->byte<klen)+top=p;+}++for(i=0;i<klen;i++){+if(p->k[i]!=kpfx[i])+return;/* "best" match failed */+}+cb_descend(top,fn,arg);+}
@@ -87,27 +87,21 @@ static void update_candidates(struct disambiguate_state *ds, const struct objectstaticintmatch_hash(unsigned,constunsignedchar*,constunsignedchar*);+staticenumcb_nextmatch_prefix(conststructobject_id*oid,void*arg)+{+structdisambiguate_state*ds=arg;+/* no need to call match_hash, oidtree_each did prefix match */+update_candidates(ds,oid);+returnds->ambiguous?CB_BREAK:CB_CONTINUE;+}+staticvoidfind_short_object_filename(structdisambiguate_state*ds){structobject_directory*odb;-for(odb=ds->repo->objects->odb;odb&&!ds->ambiguous;odb=odb->next){-intpos;-structoid_array*loose_objects;--loose_objects=odb_loose_cache(odb,&ds->bin_pfx);-pos=oid_array_lookup(loose_objects,&ds->bin_pfx);-if(pos<0)-pos=-1-pos;-while(!ds->ambiguous&&pos<loose_objects->nr){-conststructobject_id*oid;-oid=loose_objects->oid+pos;-if(!match_hash(ds->len,ds->bin_pfx.hash,oid->hash))-break;-update_candidates(ds,oid);-pos++;-}-}+for(odb=ds->repo->objects->odb;odb&&!ds->ambiguous;odb=odb->next)+oidtree_each(odb_loose_cache(odb,&ds->bin_pfx),+&ds->bin_pfx,ds->len,match_prefix,ds);}staticintmatch_hash(unsignedlen,constunsignedchar*a,constunsignedchar*b)
@@ -0,0 +1,94 @@+/*+*Awrapperaroundcbtreewhichstoresoids+*Maybeusedtoreplaceoid-arrayforprefix(abbreviation)matches+*/+#include"oidtree.h"+#include"alloc.h"+#include"hash.h"++structoidtree_node{+/* n.k[] is used to store "struct object_id" */+structcb_noden;+};++structoidtree_iter_data{+oidtree_iterfn;+void*arg;+size_t*last_nibble_at;+intalgo;+uint8_tlast_byte;+};++voidoidtree_destroy(structoidtree*ot)+{+if(ot->mempool){+clear_alloc_state(ot->mempool);+FREE_AND_NULL(ot->mempool);+}+oidtree_init(ot);+}++voidoidtree_insert(structoidtree*ot,conststructobject_id*oid)+{+structoidtree_node*on;++if(!ot->mempool)+ot->mempool=allocate_alloc_state();+if(!oid->algo)+BUG("oidtree_insert requires oid->algo");++on=alloc_from_state(ot->mempool,sizeof(*on)+sizeof(*oid));+oidcpy_with_padding((structobject_id*)on->n.k,oid);++/*+*n.b.weshouldn'tgetduplicates,here,butwe'llhave+*asmallleakthatwon'tbefreeduntiloidtree_destroy+*/+cb_insert(&ot->t,&on->n,sizeof(*oid));+}++intoidtree_contains(structoidtree*ot,conststructobject_id*oid)+{+structobject_idk={0};+size_tklen=sizeof(k);+oidcpy_with_padding(&k,oid);++if(oid->algo==GIT_HASH_UNKNOWN){+k.algo=hash_algo_by_ptr(the_hash_algo);+klen-=sizeof(oid->algo);+}++returncb_lookup(&ot->t,(constuint8_t*)&k,klen)?1:0;+}++staticenumcb_nextiter(structcb_node*n,void*arg)+{+structoidtree_iter_data*x=arg;+conststructobject_id*oid=(conststructobject_id*)n->k;++if(x->algo!=GIT_HASH_UNKNOWN&&x->algo!=oid->algo)+returnCB_CONTINUE;++if(x->last_nibble_at){+if((oid->hash[*x->last_nibble_at]^x->last_byte)&0xf0)+returnCB_CONTINUE;+}++returnx->fn(oid,x->arg);+}++voidoidtree_each(structoidtree*ot,conststructobject_id*oid,+size_toidhexlen,oidtree_iterfn,void*arg)+{+size_tklen=oidhexlen/2;+structoidtree_iter_datax={0};++x.fn=fn;+x.arg=arg;+x.algo=oid->algo;+if(oidhexlen&1){+x.last_byte=oid->hash[klen];+x.last_nibble_at=&klen;+}+cb_each(&ot->t,(constuint8_t*)oid,klen,iter,&x);+}
@@ -0,0 +1,52 @@+#!/bin/sh++test_description='basic tests for the oidtree implementation'+../test-lib.sh++echoid(){+prefix="${1:+$1}"+shift+whiletest$#-gt0+do+echo"$1"+shift+done|awk-vprefix="$prefix"'{+printf("%s%s",prefix,$0);+need=40-length($0);+for(i=0;i<need;i++)+printf("0");+printf"\n";+}'+}++test_expect_success'oidtree insert and contains''+cat>expect<<EOF&&+0+0+0+1+1+0+EOF+{+echoidinsert44412345abcde&&+echoidcontains4444144044444404444+echodestroy+}|test-tooloidtree>actual&&+test_cmpexpectactual+'++test_expect_success'oidtree each''+echoid""123321321>expect&&+{+echoidinsertf98123321abcde+echoeach12300+echoeach3211+echoeach3210+echoeach32100+echodestroy+}|test-tooloidtree>actual&&+test_cmpexpectactual+'++test_done
From: René Scharfe <hidden> Date: 2021-06-27 10:23:36
Am 27.06.21 um 04:47 schrieb Eric Wong:
There's no point in using 8 bits per-directory when 1 bit
will do. This saves us 224 bytes per object directory, which
ends up being 22MB when dealing with 100K alternates.
The point was simplicity under the assumption that the number of
repositories is low -- for most users it's only one. That obviously
doesn't hold for your use case anymore. :)
A compact representation should also reduce dcache misses, so this
should be a win for the single-repo case as well.
quoted hunk
Signed-off-by: Eric Wong <redacted>
---
object-file.c | 10 +++++++---
object-store.h | 2 +-
2 files changed, 8 insertions(+), 4 deletions(-)
With that name I'd expect the variable to contain the number of bytes or
bits in the whole bitmap. And to not be a variable at all, but rather a
macro. Perhaps word_bits?
bitsizeof() does the same and is slightly shorter.
+ uint32_t *bitmap;
Ah, you call the array items bitmap, which they are. Hmm. I rather
think of the whole thing as a bitmap and its uint32_t elements as words.
Does it matter? Not sure.
+ uint32_t bit = 1 << (subdir_nr % BM_SIZE);
I'd call that mask, but bit is fine as well..
Anyway, it would look something like this:
size_t word_bits = bitsizeof(odb->loose_objects_subdir_seen[0]);
size_t word_index = subdir_nr / word_bits;
size_t mask = 1 << (subdir_nr % word_bits);
From: Eric Wong <hidden> Date: 2021-06-28 23:09:56
René Scharfe [off-list ref] wrote:
Am 27.06.21 um 04:47 schrieb Eric Wong:
Anyway, it would look something like this:
size_t word_bits = bitsizeof(odb->loose_objects_subdir_seen[0]);
size_t word_index = subdir_nr / word_bits;
size_t mask = 1 << (subdir_nr % word_bits);
@@ -13,6 +13,7 @@ int cmd__oidtree(int argc, const char **argv)structoidtreeot=OIDTREE_INIT;structstrbufline=STRBUF_INIT;intnongit_ok;+intalgo=GIT_HASH_UNKNOWN;setup_git_directory_gently(&nongit_ok);
@@ -21,20 +22,21 @@ int cmd__oidtree(int argc, const char **argv)structobject_idoid;if(skip_prefix(line.buf,"insert ",&arg)){-if(get_oid_hex(arg,&oid))-die("not a hexadecimal oid: %s",arg);+if(get_oid_hex_any(arg,&oid)==GIT_HASH_UNKNOWN)+die("insert not a hexadecimal oid: %s",arg);+algo=oid.algo;oidtree_insert(&ot,&oid);}elseif(skip_prefix(line.buf,"contains ",&arg)){if(get_oid_hex(arg,&oid))-die("not a hexadecimal oid: %s",arg);+die("contains not a hexadecimal oid: %s",arg);printf("%d\n",oidtree_contains(&ot,&oid));}elseif(skip_prefix(line.buf,"each ",&arg)){-charbuf[GIT_SHA1_HEXSZ+1]={'0'};+charbuf[GIT_MAX_HEXSZ+1]={'0'};memset(&oid,0,sizeof(oid));memcpy(buf,arg,strlen(arg));-buf[GIT_SHA1_HEXSZ]=0;+buf[hash_algos[algo].hexsz]=0;get_oid_hex_any(buf,&oid);-oid.algo=GIT_HASH_SHA1;+oid.algo=algo;oidtree_each(&ot,&oid,strlen(arg),print_oid,NULL);}elseif(!strcmp(line.buf,"destroy"))oidtree_destroy(&ot);
From: Eric Wong <hidden> Date: 2021-06-29 20:53:08
With many alternates, the duplicate check in alt_odb_usable()
wastes many cycles doing repeated fspathcmp() on every existing
alternate. Use a khash to speed up lookups by odb->path.
Since the kh_put_* API uses the supplied key without
duplicating it, we also take advantage of it to replace both
xstrdup() and strbuf_release() in link_alt_odb_entry() with
strbuf_detach() to avoid the allocation and copy.
In a test repository with 50K alternates and each of those 50K
alternates having one alternate each (for a total of 100K total
alternates); this speeds up lookup of a non-existent blob from
over 16 minutes to roughly 2.7 seconds on my busy workstation.
Note: all underlying git object directories were small and
unpacked with only loose objects and no packs. Having to load
packs increases times significantly.
Signed-off-by: Eric Wong <redacted>
---
object-file.c | 33 ++++++++++++++++++++++-----------
object-store.h | 17 +++++++++++++++++
object.c | 2 ++
3 files changed, 41 insertions(+), 11 deletions(-)
From: Eric Wong <hidden> Date: 2021-06-29 20:53:11
We can save a few milliseconds (across 100K odbs) by using
strbuf_addbuf() instead of strbuf_addstr() by passing `entry' as
a strbuf pointer rather than a "const char *".
Signed-off-by: Eric Wong <redacted>
---
object-file.c | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
From: Eric Wong <hidden> Date: 2021-06-29 20:53:14
There's no point in using 8 bits per-directory when 1 bit
will do. This saves us 224 bytes per object directory, which
ends up being 22MB when dealing with 100K alternates.
v2: use bitsizeof() macro and better variable names
Signed-off-by: Eric Wong <redacted>
---
object-file.c | 11 ++++++++---
object-store.h | 2 +-
2 files changed, 9 insertions(+), 4 deletions(-)
From: Eric Wong <hidden> Date: 2021-06-29 20:53:16
As with `oidcpy', the source struct will not be modified and
this will allow an upcoming const-correct caller to use it.
Signed-off-by: Eric Wong <redacted>
---
hash.h | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
From: Eric Wong <hidden> Date: 2021-06-29 20:53:20
This saves 8K per `struct object_directory', meaning it saves
around 800MB in my case involving 100K alternates (half or more
of those alternates are unlikely to hold loose objects).
This is implemented in two parts: a generic, allocation-free
`cbtree' and the `oidtree' wrapper on top of it. The latter
provides allocation using alloc_state as a memory pool to
improve locality and reduce free(3) overhead.
Unlike oid-array, the crit-bit tree does not require sorting.
Performance is bound by the key length, for oidtree that is
fixed at sizeof(struct object_id). There's no need to have
256 oidtrees to mitigate the O(n log n) overhead like we did
with oid-array.
Being a prefix trie, it is natively suited for expanding short
object IDs via prefix-limited iteration in
`find_short_object_filename'.
On my busy workstation, p4205 performance seems to be roughly
unchanged (+/-8%). Startup with 100K total alternates with no
loose objects seems around 10-20% faster on a hot cache.
(800MB in memory savings means more memory for the kernel FS
cache).
The generic cbtree implementation does impose some extra
overhead for oidtree in that it uses memcmp(3) on
"struct object_id" so it wastes cycles comparing 12 extra bytes
on SHA-1 repositories. I've not yet explored reducing this
overhead, but I expect there are many places in our code base
where we'd want to investigate this.
More information on crit-bit trees: https://cr.yp.to/critbit.html
v2: make oidtree test hash-agnostic
Signed-off-by: Eric Wong <redacted>
---
Makefile | 3 +
alloc.c | 6 ++
alloc.h | 1 +
cbtree.c | 167 ++++++++++++++++++++++++++++++++++++++++
cbtree.h | 56 ++++++++++++++
object-file.c | 17 ++--
object-name.c | 28 +++----
object-store.h | 5 +-
oidtree.c | 94 ++++++++++++++++++++++
oidtree.h | 29 +++++++
t/helper/test-oidtree.c | 47 +++++++++++
t/helper/test-tool.c | 1 +
t/helper/test-tool.h | 1 +
t/t0069-oidtree.sh | 52 +++++++++++++
14 files changed, 478 insertions(+), 29 deletions(-)
create mode 100644 cbtree.c
create mode 100644 cbtree.h
create mode 100644 oidtree.c
create mode 100644 oidtree.h
create mode 100644 t/helper/test-oidtree.c
create mode 100755 t/t0069-oidtree.sh
@@ -0,0 +1,167 @@+/*+*crit-bittreeimplementation,doesnoallocationsinternally+*Formoreinformationoncrit-bittrees:https://cr.yp.to/critbit.html+*BasedonAdamLangley'sadaptationofDanBernstein'spublicdomaincode+*gitclonehttps://github.com/agl/critbit.git+*/+#include"cbtree.h"++staticstructcb_node*cb_node_of(constvoid*p)+{+return(structcb_node*)((uintptr_t)p-1);+}++/* locate the best match, does not do a final comparision */+staticstructcb_node*cb_internal_best_match(structcb_node*p,+constuint8_t*k,size_tklen)+{+while(1&(uintptr_t)p){+structcb_node*q=cb_node_of(p);+uint8_tc=q->byte<klen?k[q->byte]:0;+size_tdirection=(1+(q->otherbits|c))>>8;++p=q->child[direction];+}+returnp;+}++/* returns NULL if successful, existing cb_node if duplicate */+structcb_node*cb_insert(structcb_tree*t,structcb_node*node,size_tklen)+{+size_tnewbyte,newotherbits;+uint8_tc;+intnewdirection;+structcb_node**wherep,*p;++assert(!((uintptr_t)node&1));/* allocations must be aligned */++if(!t->root){/* insert into empty tree */+t->root=node;+returnNULL;/* success */+}++/* see if a node already exists */+p=cb_internal_best_match(t->root,node->k,klen);++/* find first differing byte */+for(newbyte=0;newbyte<klen;newbyte++){+if(p->k[newbyte]!=node->k[newbyte])+gotodifferent_byte_found;+}+returnp;/* element exists, let user deal with it */++different_byte_found:+newotherbits=p->k[newbyte]^node->k[newbyte];+newotherbits|=newotherbits>>1;+newotherbits|=newotherbits>>2;+newotherbits|=newotherbits>>4;+newotherbits=(newotherbits&~(newotherbits>>1))^255;+c=p->k[newbyte];+newdirection=(1+(newotherbits|c))>>8;++node->byte=newbyte;+node->otherbits=newotherbits;+node->child[1-newdirection]=node;++/* find a place to insert it */+wherep=&t->root;+for(;;){+structcb_node*q;+size_tdirection;++p=*wherep;+if(!(1&(uintptr_t)p))+break;+q=cb_node_of(p);+if(q->byte>newbyte)+break;+if(q->byte==newbyte&&q->otherbits>newotherbits)+break;+c=q->byte<klen?node->k[q->byte]:0;+direction=(1+(q->otherbits|c))>>8;+wherep=q->child+direction;+}++node->child[newdirection]=*wherep;+*wherep=(structcb_node*)(1+(uintptr_t)node);++returnNULL;/* success */+}++structcb_node*cb_lookup(structcb_tree*t,constuint8_t*k,size_tklen)+{+structcb_node*p=cb_internal_best_match(t->root,k,klen);++returnp&&!memcmp(p->k,k,klen)?p:NULL;+}++structcb_node*cb_unlink(structcb_tree*t,constuint8_t*k,size_tklen)+{+structcb_node**wherep=&t->root;+structcb_node**whereq=NULL;+structcb_node*q=NULL;+size_tdirection=0;+uint8_tc;+structcb_node*p=t->root;++if(!p)returnNULL;/* empty tree, nothing to delete */++/* traverse to find best match, keeping link to parent */+while(1&(uintptr_t)p){+whereq=wherep;+q=cb_node_of(p);+c=q->byte<klen?k[q->byte]:0;+direction=(1+(q->otherbits|c))>>8;+wherep=q->child+direction;+p=*wherep;+}++if(memcmp(p->k,k,klen))+returnNULL;/* no match, nothing unlinked */++/* found an exact match */+if(whereq)/* update parent */+*whereq=q->child[1-direction];+else+t->root=NULL;+returnp;+}++staticenumcb_nextcb_descend(structcb_node*p,cb_iterfn,void*arg)+{+if(1&(uintptr_t)p){+structcb_node*q=cb_node_of(p);+enumcb_nextn=cb_descend(q->child[0],fn,arg);++returnn==CB_BREAK?n:cb_descend(q->child[1],fn,arg);+}else{+returnfn(p,arg);+}+}++voidcb_each(structcb_tree*t,constuint8_t*kpfx,size_tklen,+cb_iterfn,void*arg)+{+structcb_node*p=t->root;+structcb_node*top=p;+size_ti=0;++if(!p)return;/* empty tree */++/* Walk tree, maintaining top pointer */+while(1&(uintptr_t)p){+structcb_node*q=cb_node_of(p);+uint8_tc=q->byte<klen?kpfx[q->byte]:0;+size_tdirection=(1+(q->otherbits|c))>>8;++p=q->child[direction];+if(q->byte<klen)+top=p;+}++for(i=0;i<klen;i++){+if(p->k[i]!=kpfx[i])+return;/* "best" match failed */+}+cb_descend(top,fn,arg);+}
@@ -87,27 +87,21 @@ static void update_candidates(struct disambiguate_state *ds, const struct objectstaticintmatch_hash(unsigned,constunsignedchar*,constunsignedchar*);+staticenumcb_nextmatch_prefix(conststructobject_id*oid,void*arg)+{+structdisambiguate_state*ds=arg;+/* no need to call match_hash, oidtree_each did prefix match */+update_candidates(ds,oid);+returnds->ambiguous?CB_BREAK:CB_CONTINUE;+}+staticvoidfind_short_object_filename(structdisambiguate_state*ds){structobject_directory*odb;-for(odb=ds->repo->objects->odb;odb&&!ds->ambiguous;odb=odb->next){-intpos;-structoid_array*loose_objects;--loose_objects=odb_loose_cache(odb,&ds->bin_pfx);-pos=oid_array_lookup(loose_objects,&ds->bin_pfx);-if(pos<0)-pos=-1-pos;-while(!ds->ambiguous&&pos<loose_objects->nr){-conststructobject_id*oid;-oid=loose_objects->oid+pos;-if(!match_hash(ds->len,ds->bin_pfx.hash,oid->hash))-break;-update_candidates(ds,oid);-pos++;-}-}+for(odb=ds->repo->objects->odb;odb&&!ds->ambiguous;odb=odb->next)+oidtree_each(odb_loose_cache(odb,&ds->bin_pfx),+&ds->bin_pfx,ds->len,match_prefix,ds);}staticintmatch_hash(unsignedlen,constunsignedchar*a,constunsignedchar*b)
@@ -0,0 +1,94 @@+/*+*Awrapperaroundcbtreewhichstoresoids+*Maybeusedtoreplaceoid-arrayforprefix(abbreviation)matches+*/+#include"oidtree.h"+#include"alloc.h"+#include"hash.h"++structoidtree_node{+/* n.k[] is used to store "struct object_id" */+structcb_noden;+};++structoidtree_iter_data{+oidtree_iterfn;+void*arg;+size_t*last_nibble_at;+intalgo;+uint8_tlast_byte;+};++voidoidtree_destroy(structoidtree*ot)+{+if(ot->mempool){+clear_alloc_state(ot->mempool);+FREE_AND_NULL(ot->mempool);+}+oidtree_init(ot);+}++voidoidtree_insert(structoidtree*ot,conststructobject_id*oid)+{+structoidtree_node*on;++if(!ot->mempool)+ot->mempool=allocate_alloc_state();+if(!oid->algo)+BUG("oidtree_insert requires oid->algo");++on=alloc_from_state(ot->mempool,sizeof(*on)+sizeof(*oid));+oidcpy_with_padding((structobject_id*)on->n.k,oid);++/*+*n.b.weshouldn'tgetduplicates,here,butwe'llhave+*asmallleakthatwon'tbefreeduntiloidtree_destroy+*/+cb_insert(&ot->t,&on->n,sizeof(*oid));+}++intoidtree_contains(structoidtree*ot,conststructobject_id*oid)+{+structobject_idk={0};+size_tklen=sizeof(k);+oidcpy_with_padding(&k,oid);++if(oid->algo==GIT_HASH_UNKNOWN){+k.algo=hash_algo_by_ptr(the_hash_algo);+klen-=sizeof(oid->algo);+}++returncb_lookup(&ot->t,(constuint8_t*)&k,klen)?1:0;+}++staticenumcb_nextiter(structcb_node*n,void*arg)+{+structoidtree_iter_data*x=arg;+conststructobject_id*oid=(conststructobject_id*)n->k;++if(x->algo!=GIT_HASH_UNKNOWN&&x->algo!=oid->algo)+returnCB_CONTINUE;++if(x->last_nibble_at){+if((oid->hash[*x->last_nibble_at]^x->last_byte)&0xf0)+returnCB_CONTINUE;+}++returnx->fn(oid,x->arg);+}++voidoidtree_each(structoidtree*ot,conststructobject_id*oid,+size_toidhexlen,oidtree_iterfn,void*arg)+{+size_tklen=oidhexlen/2;+structoidtree_iter_datax={0};++x.fn=fn;+x.arg=arg;+x.algo=oid->algo;+if(oidhexlen&1){+x.last_byte=oid->hash[klen];+x.last_nibble_at=&klen;+}+cb_each(&ot->t,(constuint8_t*)oid,klen,iter,&x);+}
@@ -0,0 +1,47 @@+#include"test-tool.h"+#include"cache.h"+#include"oidtree.h"++staticenumcb_nextprint_oid(conststructobject_id*oid,void*data)+{+puts(oid_to_hex(oid));+returnCB_CONTINUE;+}++intcmd__oidtree(intargc,constchar**argv)+{+structoidtreeot=OIDTREE_INIT;+structstrbufline=STRBUF_INIT;+intnongit_ok;+intalgo=GIT_HASH_UNKNOWN;++setup_git_directory_gently(&nongit_ok);++while(strbuf_getline(&line,stdin)!=EOF){+constchar*arg;+structobject_idoid;++if(skip_prefix(line.buf,"insert ",&arg)){+if(get_oid_hex_any(arg,&oid)==GIT_HASH_UNKNOWN)+die("insert not a hexadecimal oid: %s",arg);+algo=oid.algo;+oidtree_insert(&ot,&oid);+}elseif(skip_prefix(line.buf,"contains ",&arg)){+if(get_oid_hex(arg,&oid))+die("contains not a hexadecimal oid: %s",arg);+printf("%d\n",oidtree_contains(&ot,&oid));+}elseif(skip_prefix(line.buf,"each ",&arg)){+charbuf[GIT_MAX_HEXSZ+1]={'0'};+memset(&oid,0,sizeof(oid));+memcpy(buf,arg,strlen(arg));+buf[hash_algos[algo].hexsz]=0;+get_oid_hex_any(buf,&oid);+oid.algo=algo;+oidtree_each(&ot,&oid,strlen(arg),print_oid,NULL);+}elseif(!strcmp(line.buf,"destroy"))+oidtree_destroy(&ot);+else+die("unknown command: %s",line.buf);+}+return0;+}
@@ -0,0 +1,52 @@+#!/bin/sh++test_description='basic tests for the oidtree implementation'+../test-lib.sh++echoid(){+prefix="${1:+$1}"+shift+whiletest$#-gt0+do+echo"$1"+shift+done|awk-vprefix="$prefix"-vZERO_OID=$ZERO_OID'{+printf("%s%s",prefix,$0);+need=length(ZERO_OID)-length($0);+for(i=0;i<need;i++)+printf("0");+printf"\n";+}'+}++test_expect_success'oidtree insert and contains''+cat>expect<<EOF&&+0+0+0+1+1+0+EOF+{+echoidinsert44412345abcde&&+echoidcontains4444144044444404444+echodestroy+}|test-tooloidtree>actual&&+test_cmpexpectactual+'++test_expect_success'oidtree each''+echoid""123321321>expect&&+{+echoidinsertf98123321abcde+echoeach12300+echoeach3211+echoeach3210+echoeach32100+echodestroy+}|test-tooloidtree>actual&&+test_cmpexpectactual+'++test_done
From: René Scharfe <hidden> Date: 2021-07-03 10:06:07
Am 29.06.21 um 22:53 schrieb Eric Wong:
With many alternates, the duplicate check in alt_odb_usable()
wastes many cycles doing repeated fspathcmp() on every existing
alternate. Use a khash to speed up lookups by odb->path.
Since the kh_put_* API uses the supplied key without
duplicating it, we also take advantage of it to replace both
xstrdup() and strbuf_release() in link_alt_odb_entry() with
strbuf_detach() to avoid the allocation and copy.
In a test repository with 50K alternates and each of those 50K
alternates having one alternate each (for a total of 100K total
alternates); this speeds up lookup of a non-existent blob from
over 16 minutes to roughly 2.7 seconds on my busy workstation.
Yay for hashmaps! :)
quoted hunk
Note: all underlying git object directories were small and
unpacked with only loose objects and no packs. Having to load
packs increases times significantly.
Signed-off-by: Eric Wong <redacted>
---
object-file.c | 33 ++++++++++++++++++++++-----------
object-store.h | 17 +++++++++++++++++
object.c | 2 ++
3 files changed, 41 insertions(+), 11 deletions(-)
@@ -533,14 +533,22 @@ static int alt_odb_usable(struct raw_object_store *o,*Preventthecommonmistakeoflistingthesame*thingtwice,orobjectdirectoryitself.*/-for(odb=o->odb;odb;odb=odb->next){-if(!fspathcmp(path->buf,odb->path))-return0;+if(!o->odb_by_path){+khiter_tp;++o->odb_by_path=kh_init_odb_path_map();+assert(!o->odb->next);+p=kh_put_odb_path_map(o->odb_by_path,o->odb->path,&r);
So on the first run you not just create the hashmap, but you also
pre-populate it with the main object directory. Makes sense. The
hashmap wouldn't even be created in repositories without alternates.
+ if (r < 0) die_errno(_("kh_put_odb_path_map"));
Our other callers don't handle a negative return code because it would
indicate an allocation failure, and in our version we use ALLOC_ARRAY,
which dies on error. So you don't need that check here, but we better
clarify that in khash.h.
+ assert(r == 1); /* never used */
+ kh_value(o->odb_by_path, p) = o->odb;
}
if (!fspathcmp(path->buf, normalized_objdir))
return 0;
-
- return 1;
+ *pos = kh_put_odb_path_map(o->odb_by_path, path->buf, &r);
+ if (r < 0) die_errno(_("kh_put_odb_path_map"));
The comment indicates that khash would be nicer to use if it had an
enum for the kh_put return values. Perhaps, but that should be done in
another series.
I like the solution in oidset.c to make this more readable, though: Call
the return value "added" instead of "r" and then a "return !added;"
makes sense without additional comments.
This is not specific to the object store. It could be called fspatheq
and live in dir.h. Or dir.c -- a surprising amount of code seems to
necessary for that negation (https://godbolt.org/z/MY7Wda3a7). Anyway,
it's just an idea for another series.
The internal Attractive Chaos (__ac_*) macros should be left confined
to khash.h, I think. Its alias kh_str_hash_func would be better
suited here.
Do we want to use the K&R hash function here at all, though? If we
use FNV-1 when ignoring case, why not also use it (i.e. strhash) when
respecting it? At least that's done in builtin/sparse-checkout.c,
dir.c and merge-recursive.c. This is just handwaving and yammering
about lack of symmetry, but I do wonder how your performance numbers
look with strhash. If it's fine then we could package this up as
fspathhash..
And I also wonder how it looks if you use strihash unconditionally.
I guess case collisions are usually rare and branching based on a
global variable may be more expensive than case folding..
Anyway, just ideas; kh_str_hash_func would be OK as well.
I like the solution in oidset.c to make this more readable, though: Call
the return value "added" instead of "r" and then a "return !added;"
makes sense without additional comments.
That's probably because I wrote that part; see 8b2f8cbcb1 (oidset: use
khash, 2018-10-04) -- I had somehow forgotten about that. o_O
And here we wouldn't negate. Passing on the value verbatim, without
normalizing 2 to 1, would work fine.
alt_odb_usable() and its caller become quite entangled due to the
hashmap insert operation being split between them. I suspect the code
would improve by inlining the function in a follow-up patch, making
return code considerations moot. The improvement is not significant
enough to hold up this series in case you don't like the idea, though.
Rough demo:
object-file.c | 82 +++++++++++++++++++++++++++--------------------------------
1 file changed, 37 insertions(+), 45 deletions(-)
From: René Scharfe <hidden> Date: 2021-07-04 09:02:41
Am 29.06.21 um 22:53 schrieb Eric Wong:
This saves 8K per `struct object_directory', meaning it saves
around 800MB in my case involving 100K alternates (half or more
of those alternates are unlikely to hold loose objects).
This is implemented in two parts: a generic, allocation-free
`cbtree' and the `oidtree' wrapper on top of it. The latter
provides allocation using alloc_state as a memory pool to
improve locality and reduce free(3) overhead.
Unlike oid-array, the crit-bit tree does not require sorting.
Performance is bound by the key length, for oidtree that is
fixed at sizeof(struct object_id). There's no need to have
256 oidtrees to mitigate the O(n log n) overhead like we did
with oid-array.
Being a prefix trie, it is natively suited for expanding short
object IDs via prefix-limited iteration in
`find_short_object_filename'.
Sounds like a good match.
quoted hunk
On my busy workstation, p4205 performance seems to be roughly
unchanged (+/-8%). Startup with 100K total alternates with no
loose objects seems around 10-20% faster on a hot cache.
(800MB in memory savings means more memory for the kernel FS
cache).
The generic cbtree implementation does impose some extra
overhead for oidtree in that it uses memcmp(3) on
"struct object_id" so it wastes cycles comparing 12 extra bytes
on SHA-1 repositories. I've not yet explored reducing this
overhead, but I expect there are many places in our code base
where we'd want to investigate this.
More information on crit-bit trees: https://cr.yp.to/critbit.html
v2: make oidtree test hash-agnostic
Signed-off-by: Eric Wong <redacted>
---
Makefile | 3 +
alloc.c | 6 ++
alloc.h | 1 +
cbtree.c | 167 ++++++++++++++++++++++++++++++++++++++++
cbtree.h | 56 ++++++++++++++
object-file.c | 17 ++--
object-name.c | 28 +++----
object-store.h | 5 +-
oidtree.c | 94 ++++++++++++++++++++++
oidtree.h | 29 +++++++
t/helper/test-oidtree.c | 47 +++++++++++
t/helper/test-tool.c | 1 +
t/helper/test-tool.h | 1 +
t/t0069-oidtree.sh | 52 +++++++++++++
14 files changed, 478 insertions(+), 29 deletions(-)
create mode 100644 cbtree.c
create mode 100644 cbtree.h
create mode 100644 oidtree.c
create mode 100644 oidtree.h
create mode 100644 t/helper/test-oidtree.c
create mode 100755 t/t0069-oidtree.sh
Why extend alloc.c instead of using mem-pool.c? (I don't know which fits
better, but when you say "memory pool" and not use mem-pool.c I just have
to ask..)
@@ -0,0 +1,94 @@+/*+*Awrapperaroundcbtreewhichstoresoids+*Maybeusedtoreplaceoid-arrayforprefix(abbreviation)matches+*/+#include"oidtree.h"+#include"alloc.h"+#include"hash.h"++structoidtree_node{+/* n.k[] is used to store "struct object_id" */+structcb_noden;+};++structoidtree_iter_data{+oidtree_iterfn;+void*arg;+size_t*last_nibble_at;+intalgo;+uint8_tlast_byte;+};++voidoidtree_destroy(structoidtree*ot)+{+if(ot->mempool){+clear_alloc_state(ot->mempool);+FREE_AND_NULL(ot->mempool);+}+oidtree_init(ot);+}++voidoidtree_insert(structoidtree*ot,conststructobject_id*oid)+{+structoidtree_node*on;++if(!ot->mempool)+ot->mempool=allocate_alloc_state();+if(!oid->algo)+BUG("oidtree_insert requires oid->algo");++on=alloc_from_state(ot->mempool,sizeof(*on)+sizeof(*oid));+oidcpy_with_padding((structobject_id*)on->n.k,oid);++/*+*n.b.weshouldn'tgetduplicates,here,butwe'llhave+*asmallleakthatwon'tbefreeduntiloidtree_destroy+*/
Why shouldn't we get duplicates? That depends on the usage of oidtree,
right? The current user is fine because we avoid reading the same loose
object directory twice using the loose_objects_subdir_seen bitmap.
The leak comes from the allocation above, which is not used in case we
already have the key in the oidtree. So we need memory for all
candidates, not just the inserted candidates. That's probably
acceptable in most use cases.
We can do better by keeping track of the unnecessary allocation in
struct oidtree and recycling it at the next insert attempt, however.
That way we'd only waste at most one slot.
This relies on the order of the members hash and algo in struct
object_id to find a matching hash if we don't actually know algo. It
also relies on the absence of padding after algo. Would something like
this make sense?
BUILD_ASSERT_OR_ZERO(offsetof(struct object_id, algo) + sizeof(k.algo) == sizeof(k));
And why set k.algo to some arbitrary value if we ignore it anyway? I.e.
why not keep it GIT_HASH_UNKNOWN, as set by oidcpy_with_padding()?
@@ -0,0 +1,47 @@+#include"test-tool.h"+#include"cache.h"+#include"oidtree.h"++staticenumcb_nextprint_oid(conststructobject_id*oid,void*data)+{+puts(oid_to_hex(oid));+returnCB_CONTINUE;+}++intcmd__oidtree(intargc,constchar**argv)+{+structoidtreeot=OIDTREE_INIT;+structstrbufline=STRBUF_INIT;+intnongit_ok;+intalgo=GIT_HASH_UNKNOWN;++setup_git_directory_gently(&nongit_ok);++while(strbuf_getline(&line,stdin)!=EOF){+constchar*arg;+structobject_idoid;++if(skip_prefix(line.buf,"insert ",&arg)){+if(get_oid_hex_any(arg,&oid)==GIT_HASH_UNKNOWN)+die("insert not a hexadecimal oid: %s",arg);+algo=oid.algo;+oidtree_insert(&ot,&oid);+}elseif(skip_prefix(line.buf,"contains ",&arg)){+if(get_oid_hex(arg,&oid))+die("contains not a hexadecimal oid: %s",arg);+printf("%d\n",oidtree_contains(&ot,&oid));+}elseif(skip_prefix(line.buf,"each ",&arg)){+charbuf[GIT_MAX_HEXSZ+1]={'0'};+memset(&oid,0,sizeof(oid));+memcpy(buf,arg,strlen(arg));+buf[hash_algos[algo].hexsz]=0;
= '\0' if it's the intent to have a NULL-terminated string is more
readable.
@@ -0,0 +1,52 @@+#!/bin/sh++test_description='basic tests for the oidtree implementation'+../test-lib.sh++echoid(){+prefix="${1:+$1}"+shift+whiletest$#-gt0+do+echo"$1"+shift+done|awk-vprefix="$prefix"-vZERO_OID=$ZERO_OID'{+printf("%s%s",prefix,$0);+need=length(ZERO_OID)-length($0);+for(i=0;i<need;i++)+printf("0");+printf"\n";+}'+}
Looks fairly easy to do in pure-shell, first of all you don't need a
length() on $ZERO_OID, use $(test_oid hexsz) instead. That applies for
the awk version too.
But once you have that and the N arguments just do a wc -c on the
argument, use $(()) to compute the $difference, and a loop with:
printf "%s%s%0${difference}d" "$prefix" "$shortoid" "0"
From: Eric Wong <hidden> Date: 2021-07-06 23:01:16
René Scharfe [off-list ref] wrote:
Am 29.06.21 um 22:53 schrieb Eric Wong:
quoted
With many alternates, the duplicate check in alt_odb_usable()
wastes many cycles doing repeated fspathcmp() on every existing
alternate. Use a khash to speed up lookups by odb->path.
Since the kh_put_* API uses the supplied key without
duplicating it, we also take advantage of it to replace both
xstrdup() and strbuf_release() in link_alt_odb_entry() with
strbuf_detach() to avoid the allocation and copy.
In a test repository with 50K alternates and each of those 50K
alternates having one alternate each (for a total of 100K total
alternates); this speeds up lookup of a non-existent blob from
over 16 minutes to roughly 2.7 seconds on my busy workstation.
Yay for hashmaps! :)
quoted
Note: all underlying git object directories were small and
unpacked with only loose objects and no packs. Having to load
packs increases times significantly.
Signed-off-by: Eric Wong <redacted>
---
object-file.c | 33 ++++++++++++++++++++++-----------
object-store.h | 17 +++++++++++++++++
object.c | 2 ++
3 files changed, 41 insertions(+), 11 deletions(-)
@@ -533,14 +533,22 @@ static int alt_odb_usable(struct raw_object_store *o,*Preventthecommonmistakeoflistingthesame*thingtwice,orobjectdirectoryitself.*/-for(odb=o->odb;odb;odb=odb->next){-if(!fspathcmp(path->buf,odb->path))-return0;+if(!o->odb_by_path){+khiter_tp;++o->odb_by_path=kh_init_odb_path_map();+assert(!o->odb->next);+p=kh_put_odb_path_map(o->odb_by_path,o->odb->path,&r);
So on the first run you not just create the hashmap, but you also
pre-populate it with the main object directory. Makes sense. The
hashmap wouldn't even be created in repositories without alternates.
quoted
+ if (r < 0) die_errno(_("kh_put_odb_path_map"));
Our other callers don't handle a negative return code because it would
indicate an allocation failure, and in our version we use ALLOC_ARRAY,
which dies on error. So you don't need that check here, but we better
clarify that in khash.h.
quoted
+ assert(r == 1); /* never used */
+ kh_value(o->odb_by_path, p) = o->odb;
}
if (!fspathcmp(path->buf, normalized_objdir))
return 0;
-
- return 1;
+ *pos = kh_put_odb_path_map(o->odb_by_path, path->buf, &r);
+ if (r < 0) die_errno(_("kh_put_odb_path_map"));
The comment indicates that khash would be nicer to use if it had an
enum for the kh_put return values. Perhaps, but that should be done in
another series.
Agreed for another series. I've also found myself wishing khash
used enums. But I'm also not sure how much changing of 3rd
party code we should be doing...
I like the solution in oidset.c to make this more readable, though: Call
the return value "added" instead of "r" and then a "return !added;"
makes sense without additional comments.
This is not specific to the object store. It could be called fspatheq
and live in dir.h. Or dir.c -- a surprising amount of code seems to
necessary for that negation (https://godbolt.org/z/MY7Wda3a7). Anyway,
it's just an idea for another series.
No JS here for godbolt, but there's also a bunch of "!fspathcmp"
here that could probably be changed to fspatheq.
The internal Attractive Chaos (__ac_*) macros should be left confined
to khash.h, I think. Its alias kh_str_hash_func would be better
suited here.
Do we want to use the K&R hash function here at all, though? If we
use FNV-1 when ignoring case, why not also use it (i.e. strhash) when
respecting it? At least that's done in builtin/sparse-checkout.c,
dir.c and merge-recursive.c. This is just handwaving and yammering
about lack of symmetry, but I do wonder how your performance numbers
look with strhash. If it's fine then we could package this up as
fspathhash..
Yeah, I think fspathhash should be path_hash in merge-recursive.c
(and path_hash eliminated).
I don't have performance numbers, and I doubt hash function
performance is much overhead, here. I used X31 since it was
local to khash.
I would prefer we only have one non-cryptographic hash
implementation to reduce cognitive overhead, so maybe we can
drop X31 entirely for FNV-1. I'd also prefer we only have khash
or hashmap, not both.
And I also wonder how it looks if you use strihash unconditionally.
I guess case collisions are usually rare and branching based on a
global variable may be more expensive than case folding.
*shrug* I'll let somebody with more appropriate systems do
benchmarks, there. But it could be an easy switch once
fspathhash is in place.
Why extend alloc.c instead of using mem-pool.c? (I don't know which fits
better, but when you say "memory pool" and not use mem-pool.c I just have
to ask..)
I didn't know mem-pool.c existed :x (And I've always known
about alloc.c).
Perhaps we could merge them in another series to avoid further
confusion.
quoted
+void oidtree_insert(struct oidtree *ot, const struct object_id *oid)
+{
+ struct oidtree_node *on;
+
+ if (!ot->mempool)
+ ot->mempool = allocate_alloc_state();
+ if (!oid->algo)
+ BUG("oidtree_insert requires oid->algo");
+
+ on = alloc_from_state(ot->mempool, sizeof(*on) + sizeof(*oid));
+ oidcpy_with_padding((struct object_id *)on->n.k, oid);
+
+ /*
+ * n.b. we shouldn't get duplicates, here, but we'll have
+ * a small leak that won't be freed until oidtree_destroy
+ */
Why shouldn't we get duplicates? That depends on the usage of oidtree,
right? The current user is fine because we avoid reading the same loose
object directory twice using the loose_objects_subdir_seen bitmap.
Yes, it reflects the current caller.
The leak comes from the allocation above, which is not used in case we
already have the key in the oidtree. So we need memory for all
candidates, not just the inserted candidates. That's probably
acceptable in most use cases.
Yes, I think the small, impossible-due-to-current-usage leak is
an acceptable trade off.
We can do better by keeping track of the unnecessary allocation in
struct oidtree and recycling it at the next insert attempt, however.
That way we'd only waste at most one slot.
It'd involve maintaining a free list; which may be better
suited to being in alloc_state or mem_pool. That would also
increase the size of a struct *somewhere* and add a small
amount of code complexity, too.
This relies on the order of the members hash and algo in struct
object_id to find a matching hash if we don't actually know algo. It
also relies on the absence of padding after algo. Would something like
this make sense?
BUILD_ASSERT_OR_ZERO(offsetof(struct object_id, algo) + sizeof(k.algo) == sizeof(k));
Maybe... I think a static assertion that object_id.hash be the
first element of "struct object_id" is definitely needed, at
least.
And why set k.algo to some arbitrary value if we ignore it anyway? I.e.
why not keep it GIT_HASH_UNKNOWN, as set by oidcpy_with_padding()?
Good point, shortening klen would've been all that was needed.
From: Eric Wong <hidden> Date: 2021-07-07 23:10:22
Implemented suggestions from Ævar and René, noticed a few more
things that's probably worth exploring at some point...
TODO items unrelated to this series (probably for somebody else):
* try fspatheq and fspathhash in more places in hopes it can
reduce binary + icache size
* favor ${#var} (instead of "wc -c" as as suggested by Ævar)
to reduce fork+execve overhead in tests. We already use ${#var}
in t/test-lib-functions.sh, and it works in shells I've tried
(dash, posh, ksh93, bash --posix)
* reduce internal redundancies (hash functions,
hash table and memory pool implementations, etc.)
Eric Wong (5):
speed up alt_odb_usable() with many alternates
avoid strlen via strbuf_addstr in link_alt_odb_entry
make object_directory.loose_objects_subdir_seen a bitmap
oidcpy_with_padding: constify `src' arg
oidtree: a crit-bit tree for odb_loose_cache
Makefile | 3 +
cbtree.c | 167 ++++++++++++++++++++++++++++++++++++++++
cbtree.h | 56 ++++++++++++++
dir.c | 10 +++
dir.h | 2 +
hash.h | 2 +-
object-file.c | 75 ++++++++++--------
object-name.c | 28 +++----
object-store.h | 14 +++-
object.c | 2 +
oidtree.c | 104 +++++++++++++++++++++++++
oidtree.h | 22 ++++++
t/helper/test-oidtree.c | 49 ++++++++++++
t/helper/test-tool.c | 1 +
t/helper/test-tool.h | 1 +
t/t0069-oidtree.sh | 49 ++++++++++++
16 files changed, 534 insertions(+), 51 deletions(-)
create mode 100644 cbtree.c
create mode 100644 cbtree.h
create mode 100644 oidtree.c
create mode 100644 oidtree.h
create mode 100644 t/helper/test-oidtree.c
create mode 100755 t/t0069-oidtree.sh
Interdiff against v2:
@@ -489,7 +489,9 @@ int remove_dir_recursively(struct strbuf *path, int flag);intremove_path(constchar*path);intfspathcmp(constchar*a,constchar*b);+intfspatheq(constchar*a,constchar*b);intfspathncmp(constchar*a,constchar*b,size_tcount);+unsignedintfspathhash(constchar*str);/**Theprefixpartofpatternmustnotcontainswildcards.
@@ -19,46 +19,55 @@ struct oidtree_iter_data {uint8_tlast_byte;};-voidoidtree_destroy(structoidtree*ot)+voidoidtree_init(structoidtree*ot){-if(ot->mempool){-clear_alloc_state(ot->mempool);-FREE_AND_NULL(ot->mempool);+cb_init(&ot->tree);+mem_pool_init(&ot->mem_pool,0);+}++voidoidtree_clear(structoidtree*ot)+{+if(ot){+mem_pool_discard(&ot->mem_pool,0);+oidtree_init(ot);}-oidtree_init(ot);}voidoidtree_insert(structoidtree*ot,conststructobject_id*oid){structoidtree_node*on;-if(!ot->mempool)-ot->mempool=allocate_alloc_state();if(!oid->algo)BUG("oidtree_insert requires oid->algo");-on=alloc_from_state(ot->mempool,sizeof(*on)+sizeof(*oid));+on=mem_pool_alloc(&ot->mem_pool,sizeof(*on)+sizeof(*oid));oidcpy_with_padding((structobject_id*)on->n.k,oid);/*-*n.b.weshouldn'tgetduplicates,here,butwe'llhave-*asmallleakthatwon'tbefreeduntiloidtree_destroy+*n.b.Currentcallerswon'tgetusduplicates,here.Ifa+*futurecallercausesduplicates,there'llbeaasmallleak+*thatwon'tbefreeduntiloidtree_clear.Currentlyit'snot+*worthmaintainingafreelist*/-cb_insert(&ot->t,&on->n,sizeof(*oid));+cb_insert(&ot->tree,&on->n,sizeof(*oid));}+intoidtree_contains(structoidtree*ot,conststructobject_id*oid){-structobject_idk={0};+structobject_idk;size_tklen=sizeof(k);+oidcpy_with_padding(&k,oid);-if(oid->algo==GIT_HASH_UNKNOWN){-k.algo=hash_algo_by_ptr(the_hash_algo);+if(oid->algo==GIT_HASH_UNKNOWN)klen-=sizeof(oid->algo);-}-returncb_lookup(&ot->t,(constuint8_t*)&k,klen)?1:0;+/* cb_lookup relies on memcmp on the struct, so order matters: */+klen+=BUILD_ASSERT_OR_ZERO(offsetof(structobject_id,hash)<+offsetof(structobject_id,algo));++returncb_lookup(&ot->tree,(constuint8_t*)&k,klen)?1:0;}staticenumcb_nextiter(structcb_node*n,void*arg)
@@ -3,35 +3,32 @@test_description='basic tests for the oidtree implementation' ../test-lib.sh+maxhexsz=$(test_oidhexsz) echoid(){prefix="${1:+$1}"shiftwhiletest$#-gt0do-echo"$1"+shortoid="$1"shift-done|awk-vprefix="$prefix"-vZERO_OID=$ZERO_OID'{-printf("%s%s",prefix,$0);-need=length(ZERO_OID)-length($0);-for(i=0;i<need;i++)-printf("0");-printf"\n";-}'+difference=$(($maxhexsz-${#shortoid}))+printf"%s%s%0${difference}d\\n""$prefix""$shortoid""0"+done} test_expect_success'oidtree insert and contains''-cat>expect<<EOF&&-0-0-0-1-1-0-EOF+cat>expect<<-\EOF&&+0+0+0+1+1+0+EOF{echoidinsert44412345abcde&&echoidcontains4444144044444404444-echodestroy+echoclear}|test-tooloidtree>actual&&test_cmpexpectactual'
From: Eric Wong <hidden> Date: 2021-07-07 23:10:39
With many alternates, the duplicate check in alt_odb_usable()
wastes many cycles doing repeated fspathcmp() on every existing
alternate. Use a khash to speed up lookups by odb->path.
Since the kh_put_* API uses the supplied key without
duplicating it, we also take advantage of it to replace both
xstrdup() and strbuf_release() in link_alt_odb_entry() with
strbuf_detach() to avoid the allocation and copy.
In a test repository with 50K alternates and each of those 50K
alternates having one alternate each (for a total of 100K total
alternates); this speeds up lookup of a non-existent blob from
over 16 minutes to roughly 2.7 seconds on my busy workstation.
Note: all underlying git object directories were small and
unpacked with only loose objects and no packs. Having to load
packs increases times significantly.
v3: Introduce and use fspatheq and fspathhash functions;
avoid unnecessary checks for allocation failures already
handled by our own *alloc wrappers.
Signed-off-by: Eric Wong <redacted>
---
dir.c | 10 ++++++++++
dir.h | 2 ++
object-file.c | 33 +++++++++++++++++++++------------
object-store.h | 7 +++++++
object.c | 2 ++
5 files changed, 42 insertions(+), 12 deletions(-)
@@ -489,7 +489,9 @@ int remove_dir_recursively(struct strbuf *path, int flag);intremove_path(constchar*path);intfspathcmp(constchar*a,constchar*b);+intfspatheq(constchar*a,constchar*b);intfspathncmp(constchar*a,constchar*b,size_tcount);+unsignedintfspathhash(constchar*str);/**Theprefixpartofpatternmustnotcontainswildcards.
From: Eric Wong <hidden> Date: 2021-07-07 23:10:50
We can save a few milliseconds (across 100K odbs) by using
strbuf_addbuf() instead of strbuf_addstr() by passing `entry' as
a strbuf pointer rather than a "const char *".
Signed-off-by: Eric Wong <redacted>
---
object-file.c | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
From: Eric Wong <hidden> Date: 2021-07-07 23:10:51
There's no point in using 8 bits per-directory when 1 bit
will do. This saves us 224 bytes per object directory, which
ends up being 22MB when dealing with 100K alternates.
v2: use bitsizeof() macro and better variable names
Signed-off-by: Eric Wong <redacted>
---
object-file.c | 11 ++++++++---
object-store.h | 2 +-
2 files changed, 9 insertions(+), 4 deletions(-)
From: Eric Wong <hidden> Date: 2021-07-07 23:10:52
As with `oidcpy', the source struct will not be modified and
this will allow an upcoming const-correct caller to use it.
Signed-off-by: Eric Wong <redacted>
---
hash.h | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
From: Eric Wong <hidden> Date: 2021-07-07 23:10:56
This saves 8K per `struct object_directory', meaning it saves
around 800MB in my case involving 100K alternates (half or more
of those alternates are unlikely to hold loose objects).
This is implemented in two parts: a generic, allocation-free
`cbtree' and the `oidtree' wrapper on top of it. The latter
provides allocation using alloc_state as a memory pool to
improve locality and reduce free(3) overhead.
Unlike oid-array, the crit-bit tree does not require sorting.
Performance is bound by the key length, for oidtree that is
fixed at sizeof(struct object_id). There's no need to have
256 oidtrees to mitigate the O(n log n) overhead like we did
with oid-array.
Being a prefix trie, it is natively suited for expanding short
object IDs via prefix-limited iteration in
`find_short_object_filename'.
On my busy workstation, p4205 performance seems to be roughly
unchanged (+/-8%). Startup with 100K total alternates with no
loose objects seems around 10-20% faster on a hot cache.
(800MB in memory savings means more memory for the kernel FS
cache).
The generic cbtree implementation does impose some extra
overhead for oidtree in that it uses memcmp(3) on
"struct object_id" so it wastes cycles comparing 12 extra bytes
on SHA-1 repositories. I've not yet explored reducing this
overhead, but I expect there are many places in our code base
where we'd want to investigate this.
More information on crit-bit trees: https://cr.yp.to/critbit.html
v2: make oidtree test hash-agnostic
v3: Implement suggestions by René and Ævar
use mem_pool instead of alloc_state
s/oidtree.t/oidtree.tree/
lazy-allocate entire loose_objects_state struct
remove no-longer-used OIDTREE_INIT macro, uninline oidtree_init
s/oidtree_destroy/oidtree_clear/
simplify and add extra assertions
s/hexlen/hexsz/
minor style and naming fixes
Signed-off-by: Eric Wong <redacted>
---
Makefile | 3 +
cbtree.c | 167 ++++++++++++++++++++++++++++++++++++++++
cbtree.h | 56 ++++++++++++++
object-file.c | 23 +++---
object-name.c | 28 +++----
object-store.h | 5 +-
oidtree.c | 104 +++++++++++++++++++++++++
oidtree.h | 22 ++++++
t/helper/test-oidtree.c | 49 ++++++++++++
t/helper/test-tool.c | 1 +
t/helper/test-tool.h | 1 +
t/t0069-oidtree.sh | 49 ++++++++++++
12 files changed, 478 insertions(+), 30 deletions(-)
create mode 100644 cbtree.c
create mode 100644 cbtree.h
create mode 100644 oidtree.c
create mode 100644 oidtree.h
create mode 100644 t/helper/test-oidtree.c
create mode 100755 t/t0069-oidtree.sh
@@ -0,0 +1,167 @@+/*+*crit-bittreeimplementation,doesnoallocationsinternally+*Formoreinformationoncrit-bittrees:https://cr.yp.to/critbit.html+*BasedonAdamLangley'sadaptationofDanBernstein'spublicdomaincode+*gitclonehttps://github.com/agl/critbit.git+*/+#include"cbtree.h"++staticstructcb_node*cb_node_of(constvoid*p)+{+return(structcb_node*)((uintptr_t)p-1);+}++/* locate the best match, does not do a final comparision */+staticstructcb_node*cb_internal_best_match(structcb_node*p,+constuint8_t*k,size_tklen)+{+while(1&(uintptr_t)p){+structcb_node*q=cb_node_of(p);+uint8_tc=q->byte<klen?k[q->byte]:0;+size_tdirection=(1+(q->otherbits|c))>>8;++p=q->child[direction];+}+returnp;+}++/* returns NULL if successful, existing cb_node if duplicate */+structcb_node*cb_insert(structcb_tree*t,structcb_node*node,size_tklen)+{+size_tnewbyte,newotherbits;+uint8_tc;+intnewdirection;+structcb_node**wherep,*p;++assert(!((uintptr_t)node&1));/* allocations must be aligned */++if(!t->root){/* insert into empty tree */+t->root=node;+returnNULL;/* success */+}++/* see if a node already exists */+p=cb_internal_best_match(t->root,node->k,klen);++/* find first differing byte */+for(newbyte=0;newbyte<klen;newbyte++){+if(p->k[newbyte]!=node->k[newbyte])+gotodifferent_byte_found;+}+returnp;/* element exists, let user deal with it */++different_byte_found:+newotherbits=p->k[newbyte]^node->k[newbyte];+newotherbits|=newotherbits>>1;+newotherbits|=newotherbits>>2;+newotherbits|=newotherbits>>4;+newotherbits=(newotherbits&~(newotherbits>>1))^255;+c=p->k[newbyte];+newdirection=(1+(newotherbits|c))>>8;++node->byte=newbyte;+node->otherbits=newotherbits;+node->child[1-newdirection]=node;++/* find a place to insert it */+wherep=&t->root;+for(;;){+structcb_node*q;+size_tdirection;++p=*wherep;+if(!(1&(uintptr_t)p))+break;+q=cb_node_of(p);+if(q->byte>newbyte)+break;+if(q->byte==newbyte&&q->otherbits>newotherbits)+break;+c=q->byte<klen?node->k[q->byte]:0;+direction=(1+(q->otherbits|c))>>8;+wherep=q->child+direction;+}++node->child[newdirection]=*wherep;+*wherep=(structcb_node*)(1+(uintptr_t)node);++returnNULL;/* success */+}++structcb_node*cb_lookup(structcb_tree*t,constuint8_t*k,size_tklen)+{+structcb_node*p=cb_internal_best_match(t->root,k,klen);++returnp&&!memcmp(p->k,k,klen)?p:NULL;+}++structcb_node*cb_unlink(structcb_tree*t,constuint8_t*k,size_tklen)+{+structcb_node**wherep=&t->root;+structcb_node**whereq=NULL;+structcb_node*q=NULL;+size_tdirection=0;+uint8_tc;+structcb_node*p=t->root;++if(!p)returnNULL;/* empty tree, nothing to delete */++/* traverse to find best match, keeping link to parent */+while(1&(uintptr_t)p){+whereq=wherep;+q=cb_node_of(p);+c=q->byte<klen?k[q->byte]:0;+direction=(1+(q->otherbits|c))>>8;+wherep=q->child+direction;+p=*wherep;+}++if(memcmp(p->k,k,klen))+returnNULL;/* no match, nothing unlinked */++/* found an exact match */+if(whereq)/* update parent */+*whereq=q->child[1-direction];+else+t->root=NULL;+returnp;+}++staticenumcb_nextcb_descend(structcb_node*p,cb_iterfn,void*arg)+{+if(1&(uintptr_t)p){+structcb_node*q=cb_node_of(p);+enumcb_nextn=cb_descend(q->child[0],fn,arg);++returnn==CB_BREAK?n:cb_descend(q->child[1],fn,arg);+}else{+returnfn(p,arg);+}+}++voidcb_each(structcb_tree*t,constuint8_t*kpfx,size_tklen,+cb_iterfn,void*arg)+{+structcb_node*p=t->root;+structcb_node*top=p;+size_ti=0;++if(!p)return;/* empty tree */++/* Walk tree, maintaining top pointer */+while(1&(uintptr_t)p){+structcb_node*q=cb_node_of(p);+uint8_tc=q->byte<klen?kpfx[q->byte]:0;+size_tdirection=(1+(q->otherbits|c))>>8;++p=q->child[direction];+if(q->byte<klen)+top=p;+}++for(i=0;i<klen;i++){+if(p->k[i]!=kpfx[i])+return;/* "best" match failed */+}+cb_descend(top,fn,arg);+}
@@ -87,27 +87,21 @@ static void update_candidates(struct disambiguate_state *ds, const struct objectstaticintmatch_hash(unsigned,constunsignedchar*,constunsignedchar*);+staticenumcb_nextmatch_prefix(conststructobject_id*oid,void*arg)+{+structdisambiguate_state*ds=arg;+/* no need to call match_hash, oidtree_each did prefix match */+update_candidates(ds,oid);+returnds->ambiguous?CB_BREAK:CB_CONTINUE;+}+staticvoidfind_short_object_filename(structdisambiguate_state*ds){structobject_directory*odb;-for(odb=ds->repo->objects->odb;odb&&!ds->ambiguous;odb=odb->next){-intpos;-structoid_array*loose_objects;--loose_objects=odb_loose_cache(odb,&ds->bin_pfx);-pos=oid_array_lookup(loose_objects,&ds->bin_pfx);-if(pos<0)-pos=-1-pos;-while(!ds->ambiguous&&pos<loose_objects->nr){-conststructobject_id*oid;-oid=loose_objects->oid+pos;-if(!match_hash(ds->len,ds->bin_pfx.hash,oid->hash))-break;-update_candidates(ds,oid);-pos++;-}-}+for(odb=ds->repo->objects->odb;odb&&!ds->ambiguous;odb=odb->next)+oidtree_each(odb_loose_cache(odb,&ds->bin_pfx),+&ds->bin_pfx,ds->len,match_prefix,ds);}staticintmatch_hash(unsignedlen,constunsignedchar*a,constunsignedchar*b)
@@ -0,0 +1,104 @@+/*+*Awrapperaroundcbtreewhichstoresoids+*Maybeusedtoreplaceoid-arrayforprefix(abbreviation)matches+*/+#include"oidtree.h"+#include"alloc.h"+#include"hash.h"++structoidtree_node{+/* n.k[] is used to store "struct object_id" */+structcb_noden;+};++structoidtree_iter_data{+oidtree_iterfn;+void*arg;+size_t*last_nibble_at;+intalgo;+uint8_tlast_byte;+};++voidoidtree_init(structoidtree*ot)+{+cb_init(&ot->tree);+mem_pool_init(&ot->mem_pool,0);+}++voidoidtree_clear(structoidtree*ot)+{+if(ot){+mem_pool_discard(&ot->mem_pool,0);+oidtree_init(ot);+}+}++voidoidtree_insert(structoidtree*ot,conststructobject_id*oid)+{+structoidtree_node*on;++if(!oid->algo)+BUG("oidtree_insert requires oid->algo");++on=mem_pool_alloc(&ot->mem_pool,sizeof(*on)+sizeof(*oid));+oidcpy_with_padding((structobject_id*)on->n.k,oid);++/*+*n.b.Currentcallerswon'tgetusduplicates,here.Ifa+*futurecallercausesduplicates,there'llbeaasmallleak+*thatwon'tbefreeduntiloidtree_clear.Currentlyit'snot+*worthmaintainingafreelist+*/+cb_insert(&ot->tree,&on->n,sizeof(*oid));+}+++intoidtree_contains(structoidtree*ot,conststructobject_id*oid)+{+structobject_idk;+size_tklen=sizeof(k);++oidcpy_with_padding(&k,oid);++if(oid->algo==GIT_HASH_UNKNOWN)+klen-=sizeof(oid->algo);++/* cb_lookup relies on memcmp on the struct, so order matters: */+klen+=BUILD_ASSERT_OR_ZERO(offsetof(structobject_id,hash)<+offsetof(structobject_id,algo));++returncb_lookup(&ot->tree,(constuint8_t*)&k,klen)?1:0;+}++staticenumcb_nextiter(structcb_node*n,void*arg)+{+structoidtree_iter_data*x=arg;+conststructobject_id*oid=(conststructobject_id*)n->k;++if(x->algo!=GIT_HASH_UNKNOWN&&x->algo!=oid->algo)+returnCB_CONTINUE;++if(x->last_nibble_at){+if((oid->hash[*x->last_nibble_at]^x->last_byte)&0xf0)+returnCB_CONTINUE;+}++returnx->fn(oid,x->arg);+}++voidoidtree_each(structoidtree*ot,conststructobject_id*oid,+size_toidhexsz,oidtree_iterfn,void*arg)+{+size_tklen=oidhexsz/2;+structoidtree_iter_datax={0};+assert(oidhexsz<=GIT_MAX_HEXSZ);++x.fn=fn;+x.arg=arg;+x.algo=oid->algo;+if(oidhexsz&1){+x.last_byte=oid->hash[klen];+x.last_nibble_at=&klen;+}+cb_each(&ot->tree,(constuint8_t*)oid,klen,iter,&x);+}
@@ -0,0 +1,49 @@+#include"test-tool.h"+#include"cache.h"+#include"oidtree.h"++staticenumcb_nextprint_oid(conststructobject_id*oid,void*data)+{+puts(oid_to_hex(oid));+returnCB_CONTINUE;+}++intcmd__oidtree(intargc,constchar**argv)+{+structoidtreeot;+structstrbufline=STRBUF_INIT;+intnongit_ok;+intalgo=GIT_HASH_UNKNOWN;++oidtree_init(&ot);+setup_git_directory_gently(&nongit_ok);++while(strbuf_getline(&line,stdin)!=EOF){+constchar*arg;+structobject_idoid;++if(skip_prefix(line.buf,"insert ",&arg)){+if(get_oid_hex_any(arg,&oid)==GIT_HASH_UNKNOWN)+die("insert not a hexadecimal oid: %s",arg);+algo=oid.algo;+oidtree_insert(&ot,&oid);+}elseif(skip_prefix(line.buf,"contains ",&arg)){+if(get_oid_hex(arg,&oid))+die("contains not a hexadecimal oid: %s",arg);+printf("%d\n",oidtree_contains(&ot,&oid));+}elseif(skip_prefix(line.buf,"each ",&arg)){+charbuf[GIT_MAX_HEXSZ+1]={'0'};+memset(&oid,0,sizeof(oid));+memcpy(buf,arg,strlen(arg));+buf[hash_algos[algo].hexsz]='\0';+get_oid_hex_any(buf,&oid);+oid.algo=algo;+oidtree_each(&ot,&oid,strlen(arg),print_oid,NULL);+}elseif(!strcmp(line.buf,"clear")){+oidtree_clear(&ot);+}else{+die("unknown command: %s",line.buf);+}+}+return0;+}
@@ -0,0 +1,49 @@+#!/bin/sh++test_description='basic tests for the oidtree implementation'+../test-lib.sh++maxhexsz=$(test_oidhexsz)+echoid(){+prefix="${1:+$1}"+shift+whiletest$#-gt0+do+shortoid="$1"+shift+difference=$(($maxhexsz-${#shortoid}))+printf"%s%s%0${difference}d\\n""$prefix""$shortoid""0"+done+}++test_expect_success'oidtree insert and contains''+cat>expect<<-\EOF&&+0+0+0+1+1+0+EOF+{+echoidinsert44412345abcde&&+echoidcontains4444144044444404444+echoclear+}|test-tooloidtree>actual&&+test_cmpexpectactual+'++test_expect_success'oidtree each''+echoid""123321321>expect&&+{+echoidinsertf98123321abcde+echoeach12300+echoeach3211+echoeach3210+echoeach32100+echoclear+}|test-tooloidtree>actual&&+test_cmpexpectactual+'++test_done
I'm using mem_pool, now. With the way mem_pool_init works,
I've decided to do away with OIDTREE_INIT and only use
oidtree_init (and lazy-malloc the entire loose_objects_cache)
quoted
+void oidtree_destroy(struct oidtree *);
Maybe s/destroy/release/, or if you actually need that reset behavior
oidtree_reset(). We've got
I'm renaming it oidtree_clear to match oid_array_clear.
An "arg" name for some arguments, but none for others, if there's a name
here call it "data" like you do elswhere?
OK, using "data". To reduce noise, I prefer to only name
variables in prototypes if the usage can't be easily inferred
from its type and function name.
@@ -0,0 +1,47 @@+#include"test-tool.h"+#include"cache.h"+#include"oidtree.h"++staticenumcb_nextprint_oid(conststructobject_id*oid,void*data)+{+puts(oid_to_hex(oid));+returnCB_CONTINUE;+}++intcmd__oidtree(intargc,constchar**argv)+{+structoidtreeot=OIDTREE_INIT;+structstrbufline=STRBUF_INIT;+intnongit_ok;+intalgo=GIT_HASH_UNKNOWN;++setup_git_directory_gently(&nongit_ok);++while(strbuf_getline(&line,stdin)!=EOF){+constchar*arg;+structobject_idoid;++if(skip_prefix(line.buf,"insert ",&arg)){+if(get_oid_hex_any(arg,&oid)==GIT_HASH_UNKNOWN)+die("insert not a hexadecimal oid: %s",arg);+algo=oid.algo;+oidtree_insert(&ot,&oid);+}elseif(skip_prefix(line.buf,"contains ",&arg)){+if(get_oid_hex(arg,&oid))+die("contains not a hexadecimal oid: %s",arg);+printf("%d\n",oidtree_contains(&ot,&oid));+}elseif(skip_prefix(line.buf,"each ",&arg)){+charbuf[GIT_MAX_HEXSZ+1]={'0'};+memset(&oid,0,sizeof(oid));+memcpy(buf,arg,strlen(arg));+buf[hash_algos[algo].hexsz]=0;
= '\0' if it's the intent to have a NULL-terminated string is more
readable.
@@ -0,0 +1,52 @@+#!/bin/sh++test_description='basic tests for the oidtree implementation'+../test-lib.sh++echoid(){+prefix="${1:+$1}"+shift+whiletest$#-gt0+do+echo"$1"+shift+done|awk-vprefix="$prefix"-vZERO_OID=$ZERO_OID'{+printf("%s%s",prefix,$0);+need=length(ZERO_OID)-length($0);+for(i=0;i<need;i++)+printf("0");+printf"\n";+}'+}
Looks fairly easy to do in pure-shell, first of all you don't need a
length() on $ZERO_OID, use $(test_oid hexsz) instead. That applies for
the awk version too.
Ah, I didn't know about test_oid, using it, now.
But once you have that and the N arguments just do a wc -c on the
argument, use $(()) to compute the $difference, and a loop with:
printf "%s%s%0${difference}d" "$prefix" "$shortoid" "0"
I also wanted to avoid repeated 'wc -c' and figured awk was
portable enough since we use it elsewhere in tests. I've now
noticed "${#var}" is portable and we're already relying on it in
packetize(), so I'm using that.
@@ -0,0 +1,94 @@+/*+*Awrapperaroundcbtreewhichstoresoids+*Maybeusedtoreplaceoid-arrayforprefix(abbreviation)matches+*/+#include"oidtree.h"+#include"alloc.h"+#include"hash.h"++structoidtree_node{+/* n.k[] is used to store "struct object_id" */+structcb_noden;+};+
I think this object_id cast introduced undefined behaviour - here's my
layperson's interepretation of what's going on (full UBSAN output is
pasted below):
cb_node.k is a uint8_t[], and hence can be 1-byte aligned (on my
machine: offsetof(struct cb_node, k) == 21). We're casting its pointer
to "struct object_id *", and later try to access object_id.hash within
oidcpy_with_padding. My compiler assumes that an object_id pointer needs
to be 4-byte aligned, and reading from a misaligned pointer means we hit
undefined behaviour. (I think the 4-byte alignment requirement comes
from the fact that object_id's largest member is an int?)
I'm not sure what an elegant and idiomatic fix might be - IIUC it's hard
to guarantee misaligned access can't happen with a flex array that's
being used for arbitrary data (you would presumably have to declare it
as an array of whatever the largest supported type is, so that you can
guarantee correct alignment even when cbtree is used with that type) -
which might imply that k needs to be declared as a void pointer? That in
turn would make cbtree.c harder to read.
Anyhow, here's the UBSAN output from t0000 running against next:
hash.h:277:14: runtime error: member access within misaligned address
0x7fcb31c4103d for type 'struct object_id', which requires 4 byte alignment
0x7fcb31c4103d: note: pointer points here
5a 5a 5a 5a 5a 5a 5a 5a 5a 5a 5a 5a 5a 5a 5a 5a 5a 5a 5a 5a 5a 5a 5a
5a 5a 5a 5a 5a 5a 5a 5a 5a
^
#0 0xc76d9d in oidcpy_with_padding hash.h:277:14
#1 0xc768f5 in oidtree_insert oidtree.c:44:2
#2 0xc418e3 in append_loose_object object-file.c:2398:2
#3 0xc3fbdc in for_each_file_in_obj_subdir object-file.c:2316:9
#4 0xc41785 in odb_loose_cache object-file.c:2424:2
#5 0xc50336 in find_short_object_filename object-name.c:103:16
#6 0xc50e04 in repo_find_unique_abbrev_r object-name.c:712:2
#7 0xc519a9 in repo_find_unique_abbrev object-name.c:727:2
#8 0x9b6ce2 in diff_abbrev_oid diff.c:4208:10
#9 0x9f13d0 in fill_metainfo diff.c:4286:8
#10 0x9f02d6 in run_diff_cmd diff.c:4322:3
#11 0x9efbef in run_diff diff.c:4422:3
#12 0x9c9ac9 in diff_flush_patch diff.c:5765:2
#13 0x9c9e74 in diff_flush_patch_all_file_pairs diff.c:6246:4
#14 0x9be33e in diff_flush diff.c:6387:3
#15 0xb8864e in log_tree_diff_flush log-tree.c:895:2
#16 0xb8987b in log_tree_diff log-tree.c:933:4
#17 0xb88c9a in log_tree_commit log-tree.c:988:10
#18 0x5b4257 in cmd_log_walk log.c:426:8
#19 0x5b6224 in cmd_show log.c:698:10
#20 0x42ec48 in run_builtin git.c:461:11
#21 0x4295e0 in handle_builtin git.c:714:3
#22 0x42d043 in run_argv git.c:781:4
#23 0x428cc2 in cmd_main git.c:912:19
#24 0x7791ce in main common-main.c:52:11
#25 0x7fcb30aab349 in __libc_start_main (/lib64/libc.so.6+0x24349)
#26 0x4074a9 in _start start.S:120
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior hash.h:277:14 in
+
+ /*
+ * n.b. we shouldn't get duplicates, here, but we'll have
+ * a small leak that won't be freed until oidtree_destroy
+ */
+ cb_insert(&ot->t, &on->n, sizeof(*oid));
+}
+
@@ -0,0 +1,94 @@+/*+*Awrapperaroundcbtreewhichstoresoids+*Maybeusedtoreplaceoid-arrayforprefix(abbreviation)matches+*/+#include"oidtree.h"+#include"alloc.h"+#include"hash.h"++structoidtree_node{+/* n.k[] is used to store "struct object_id" */+structcb_noden;+};+
I think this object_id cast introduced undefined behaviour - here's
my layperson's interepretation of what's going on (full UBSAN output
is pasted below):
cb_node.k is a uint8_t[], and hence can be 1-byte aligned (on my
machine: offsetof(struct cb_node, k) == 21). We're casting its
pointer to "struct object_id *", and later try to access
object_id.hash within oidcpy_with_padding. My compiler assumes that
an object_id pointer needs to be 4-byte aligned, and reading from a
misaligned pointer means we hit undefined behaviour. (I think the
4-byte alignment requirement comes from the fact that object_id's
largest member is an int?)
I'm not sure what an elegant and idiomatic fix might be - IIUC it's
hard to guarantee misaligned access can't happen with a flex array
that's being used for arbitrary data (you would presumably have to
declare it as an array of whatever the largest supported type is, so
that you can guarantee correct alignment even when cbtree is used
with that type) - which might imply that k needs to be declared as a
void pointer? That in turn would make cbtree.c harder to read.
C11 has alignas. We could also make the member before the flex array,
otherbits, wider, e.g. promote it to uint32_t.
A more parsimonious solution would be to turn the int member of struct
object_id, algo, into an unsigned char for now and reconsider the issue
once we support our 200th algorithm or so. This breaks notes, though.
Its GET_PTR_TYPE seems to require struct leaf_node to have 4-byte
alignment for some reason. That can be ensured by adding an int member.
Anyway, with either of these fixes UBSan is still unhappy about a
different issue. Here's a patch for that:
--- >8 ---
Subject: [PATCH] object-file: use unsigned arithmetic with bit mask
33f379eee6 (make object_directory.loose_objects_subdir_seen a bitmap,
2021-07-07) replaced a wasteful 256-byte array with a 32-byte array
and bit operations. The mask calculation shifts a literal 1 of type
int left by anything between 0 and 31. UndefinedBehaviorSanitizer
doesn't like that and reports:
object-file.c:2477:18: runtime error: left shift of 1 by 31 places cannot be represented in type 'int'
Make sure to use an unsigned 1 instead to avoid the issue.
Signed-off-by: René Scharfe <redacted>
---
object-file.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
+struct oidtree_node {
+ /* n.k[] is used to store "struct object_id" */
+ struct cb_node n;
+};
+
[... snip ...]
+
+void oidtree_insert(struct oidtree *ot, const struct object_id *oid)
+{
+ struct oidtree_node *on;
+
+ if (!ot->mempool)
+ ot->mempool = allocate_alloc_state();
+ if (!oid->algo)
+ BUG("oidtree_insert requires oid->algo");
+
+ on = alloc_from_state(ot->mempool, sizeof(*on) + sizeof(*oid));
+ oidcpy_with_padding((struct object_id *)on->n.k, oid);
I think this object_id cast introduced undefined behaviour - here's
my layperson's interepretation of what's going on (full UBSAN output
is pasted below):
cb_node.k is a uint8_t[], and hence can be 1-byte aligned (on my
machine: offsetof(struct cb_node, k) == 21). We're casting its
pointer to "struct object_id *", and later try to access
object_id.hash within oidcpy_with_padding. My compiler assumes that
an object_id pointer needs to be 4-byte aligned, and reading from a
misaligned pointer means we hit undefined behaviour. (I think the
4-byte alignment requirement comes from the fact that object_id's
largest member is an int?)
I seem to recall struct alignment requirements being
architecture-dependent; and x86/x86-64 are the most liberal
w.r.t alignment requirements.
quoted
I'm not sure what an elegant and idiomatic fix might be - IIUC it's
hard to guarantee misaligned access can't happen with a flex array
that's being used for arbitrary data (you would presumably have to
declare it as an array of whatever the largest supported type is, so
that you can guarantee correct alignment even when cbtree is used
with that type) - which might imply that k needs to be declared as a
void pointer? That in turn would make cbtree.c harder to read.
C11 has alignas. We could also make the member before the flex array,
otherbits, wider, e.g. promote it to uint32_t.
Ugh, no. cb_node should be as small as possible and (for our
current purposes) ->byte could be uint8_t.
A more parsimonious solution would be to turn the int member of struct
object_id, algo, into an unsigned char for now and reconsider the issue
once we support our 200th algorithm or so.
Yes, making struct object_id smaller would benefit all git users
(at least for the next few centuries :P).
This breaks notes, though.
Its GET_PTR_TYPE seems to require struct leaf_node to have 4-byte
alignment for some reason. That can be ensured by adding an int member.
Adding a 4-byte int to leaf_node after shaving 6-bytes off two
object_id structs would mean a net savings of 2 bytes;
sounds good to me.
I don't know much about notes nor the associated code,
but I also wonder if crit-bit tree can be used there, too.
Anyway, with either of these fixes UBSan is still unhappy about a
different issue. Here's a patch for that:
+struct oidtree_node {
+ /* n.k[] is used to store "struct object_id" */
+ struct cb_node n;
+};
+
[... snip ...]
+
+void oidtree_insert(struct oidtree *ot, const struct object_id *oid)
+{
+ struct oidtree_node *on;
+
+ if (!ot->mempool)
+ ot->mempool = allocate_alloc_state();
+ if (!oid->algo)
+ BUG("oidtree_insert requires oid->algo");
+
+ on = alloc_from_state(ot->mempool, sizeof(*on) + sizeof(*oid));
+ oidcpy_with_padding((struct object_id *)on->n.k, oid);
I think this object_id cast introduced undefined behaviour - here's
my layperson's interepretation of what's going on (full UBSAN output
is pasted below):
cb_node.k is a uint8_t[], and hence can be 1-byte aligned (on my
machine: offsetof(struct cb_node, k) == 21). We're casting its
pointer to "struct object_id *", and later try to access
object_id.hash within oidcpy_with_padding. My compiler assumes that
an object_id pointer needs to be 4-byte aligned, and reading from a
misaligned pointer means we hit undefined behaviour. (I think the
4-byte alignment requirement comes from the fact that object_id's
largest member is an int?)
I seem to recall struct alignment requirements being
architecture-dependent; and x86/x86-64 are the most liberal
w.r.t alignment requirements.
I think the problem here is not the alignment though, but the fact that
the nesting of structs with flexible arrays is forbidden by ISO/IEC
9899:2011 6.7.2.1¶3 that reads :
6.7.2.1 Structure and union specifiers
¶3 A structure or union shall not contain a member with incomplete or
function type (hence, a structure shall not contain an instance of
itself, but may contain a pointer to an instance of itself), except
that the last member of a structure with more than one named member
may have incomplete array type; such a structure (and any union
containing, possibly recursively, a member that is such a structure)
shall not be a member of a structure or an element of an array.
and it will throw a warning with clang 12
(-Wflexible-array-extensions) or gcc 11 (-Werror=pedantic) when using
DEVOPTS=pedantic
My somewhat naive suggestion was to avoid the struct nesting by
removing struct oidtree_node and using a struct cb_node directly.
Will reply with a small series of patches that fix pedantic related
warnings in ew/many-alternate-optim on top of next.
Carlo
From: Carlo Marcelo Arenas Belón <hidden> Date: 2021-08-09 01:38:52
Building next with pedantic enabled shows the following 2 issues that
were originally in ew/many-alternate-optim, apologies for not catching
them earlier.
the second one could be skipped, and has indeed another similar case
already in seen which will be send separately.
the third patch adds a CI job that could be used to detect this issues
early and that adds about 5m of computing time.
Carlo Marcelo Arenas Belón (3):
oidtree: avoid nested struct oidtree_node
object-store: avoid extra ';' from KHASH_INIT
ci: run a pedantic build as part of the GitHub workflow
.github/workflows/main.yml | 2 ++
ci/install-docker-dependencies.sh | 4 ++++
ci/run-build-and-tests.sh | 10 +++++++---
object-store.h | 2 +-
oidtree.c | 11 +++--------
5 files changed, 17 insertions(+), 12 deletions(-)
--
2.33.0.rc1.373.gc715f1a457
From: Carlo Marcelo Arenas Belón <hidden> Date: 2021-08-09 01:38:54
cf2dc1c238 (speed up alt_odb_usable() with many alternates, 2021-07-07)
introduces a KHASH_INIT invocation with a trailing ';', which while
commonly expected will trigger warnings with pedantic on both
clang[-Wextra-semi] and gcc[-Wpedantic], because that macro has already
a semicolon and is meant to be invoked without one.
while fixing the macro would be a worthy solution (specially considering
this is a common recurring problem), remove the extra ';' for now to
minimize churn.
Signed-off-by: Carlo Marcelo Arenas Belón <redacted>
---
object-store.h | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
From: Carlo Marcelo Arenas Belón <hidden> Date: 2021-08-09 01:38:56
92d8ed8ac1 (oidtree: a crit-bit tree for odb_loose_cache, 2021-07-07)
adds a struct oidtree_node that contains only an n field with a
struct cb_node.
unfortunately, while building in pedantic mode witch clang 12 (as well
as a similar error from gcc 11) it will show:
oidtree.c:11:17: error: 'n' may not be nested in a struct due to flexible array member [-Werror,-Wflexible-array-extensions]
struct cb_node n;
^
because of a constrain coded in ISO C 11 6.7.2.1¶3 that forbids using
structs that contain a flexible array as part of another struct.
use a strict cb_node directly instead.
Signed-off-by: Carlo Marcelo Arenas Belón <redacted>
---
oidtree.c | 11 +++--------
1 file changed, 3 insertions(+), 8 deletions(-)
@@ -6,11 +6,6 @@#include"alloc.h"#include"hash.h"-structoidtree_node{-/* n.k[] is used to store "struct object_id" */-structcb_noden;-};-structoidtree_iter_data{oidtree_iterfn;void*arg;
From: Carlo Marcelo Arenas Belón <hidden> Date: 2021-08-09 01:38:57
similar to the recently added sparse task, it is nice to know as early
as possible.
add a dockerized build using fedora (that usually has the latest gcc)
to be ahead of the curve and avoid older ISO C issues at the same time.
Signed-off-by: Carlo Marcelo Arenas Belón <redacted>
---
.github/workflows/main.yml | 2 ++
ci/install-docker-dependencies.sh | 4 ++++
ci/run-build-and-tests.sh | 10 +++++++---
3 files changed, 13 insertions(+), 3 deletions(-)
@@ -35,10 +40,9 @@ linux-clang)exportGIT_TEST_DEFAULT_HASH=sha256maketest;;-linux-gcc-4.8)+linux-gcc-4.8|pedantic)# Don't run the tests; we only care about whether Git can be-# built with GCC 4.8, as it errors out on some undesired (C99)-# constructs that newer compilers seem to quietly accept.+# built with GCC 4.8 or with pedantic;; *)maketest
On 09/08/21 08.38, Carlo Marcelo Arenas Belón wrote:
similar to the recently added sparse task, it is nice to know as early
as possible.
add a dockerized build using fedora (that usually has the latest gcc)
to be ahead of the curve and avoid older ISO C issues at the same time.
But from GCC manual [1], the default C dialect used is `-std=gnu17`,
while `-pedantic` is only relevant for ISO C (such as `-std=c17`).
And why not using `-pedantic-errors`, so that non-ISO features are
treated as errors?
Newcomers contributing to Git may think that based on what our CI do,
they can submit patches with C17 features (perhaps with GNU extensions).
Then at some time there is casual users that complain that Git doesn't
compile with their default older compiler (maybe they run LTS
distributions or pre-C17 compiler). Thus we want Git to be compiled
successfully using wide variety of compilers (maybe as old as GCC 4.8).
[1]: https://gcc.gnu.org/onlinedocs/gcc-11.2.0/gcc/Standards.html#Standards
--
An old man doll... just what I always wanted! - Clara
Hi Carlo
On 09/08/2021 02:38, Carlo Marcelo Arenas Belón wrote:
similar to the recently added sparse task, it is nice to know as early
as possible.
add a dockerized build using fedora (that usually has the latest gcc)
to be ahead of the curve and avoid older ISO C issues at the same time.
If we want to be able to compile with -Wpedantic then it might be better
just to turn it on unconditionally in config.mak.dev. Then developers
will see any errors before they push and the ci builds will all use it
rather than having to run an extra job. I had a quick scan of the mail
archive threads starting at [1,2] and it's not clear to me why
-Wpedaintic was added as an optional extra.
Totally unrelated to this patch but while looking at the ci scripts I
noticed that we only run the linux-gcc-4.8 job on travis, not on github.
Best Wishes
Phillip
[1] https://lore.kernel.org/git/20180721185933.32377-1-dev+git@drbeat.li/
[2] https://lore.kernel.org/git/20180721203647.2619-1-dev+git@drbeat.li/
@@ -35,10 +40,9 @@ linux-clang)exportGIT_TEST_DEFAULT_HASH=sha256maketest;;-linux-gcc-4.8)+linux-gcc-4.8|pedantic)# Don't run the tests; we only care about whether Git can be-# built with GCC 4.8, as it errors out on some undesired (C99)-# constructs that newer compilers seem to quietly accept.+# built with GCC 4.8 or with pedantic;;*)maketest
From: Carlo Arenas <hidden> Date: 2021-08-09 22:04:09
On Mon, Aug 9, 2021 at 3:50 AM Bagas Sanjaya [off-list ref] wrote:
On 09/08/21 08.38, Carlo Marcelo Arenas Belón wrote:
quoted
add a dockerized build using fedora (that usually has the latest gcc)
to be ahead of the curve and avoid older ISO C issues at the same time.
But from GCC manual [1], the default C dialect used is `-std=gnu17`,
while `-pedantic` is only relevant for ISO C (such as `-std=c17`).
sorry about that, my comment was confusing
I only meant to imply that newer compilers were not throwing any more
warnings than the ones that were fixed unlike what you would get if
using older compilers or targeting an older standard. This implies that
it will likely not have many false positives and the few breaks that would
come with newer compiled might be worth investigating or adding to the
ignore list.
a strict C89 compiler won't even build (ex: inline is a gnu extension
and the codebase has
been adding those officially since fe9dc6b08c (Merge branch
'jc/post-c89-rules-doc', 2019-07-25))
and so the pedantic check implied you would target at least gnu89 and
generate lots of warnings (so don't expect to build with DEVELOPER=1
that adds -Werror)
are you suggesting we need a more aggresive target like strict C99? at
least gcc 11.2.0
seems to be able to still build next without warnings.
And why not using `-pedantic-errors`, so that non-ISO features are
treated as errors?
warnings are already treated as errors, if you want to see all
warnings need DEVOPTS="no-error pedantic"
Newcomers contributing to Git may think that based on what our CI do,
they can submit patches with C17 features (perhaps with GNU extensions).
Then at some time there is casual users that complain that Git doesn't
compile with their default older compiler (maybe they run LTS
distributions or pre-C17 compiler). Thus we want Git to be compiled
successfully using wide variety of compilers (maybe as old as GCC 4.8).
the codebase was meant to be C89 compatible (as described in
Documentation/CodingGuidelines).
gcc-4 is a good target because AFAIK was the last one that defaulted
to gnu89 mode
and was also used as the system compiler for several really old
systems that still have support.
I tested with 4.9.4, which was the oldest I could get a hold off from
gcc's docker hub, but I suspect
will work the same in that old gcc from centos or debian as well.
Carlo
From: Carlo Arenas <hidden> Date: 2021-08-09 22:49:05
On Mon, Aug 9, 2021 at 7:56 AM Phillip Wood [off-list ref] wrote:
Totally unrelated to this patch but while looking at the ci scripts I
noticed that we only run the linux-gcc-4.8 job on travis, not on github.
it is actually related and part of the reason why I sent this as an RFC.
travis[1] itself is not running, probably because it broke when
travis-ci.org was
shutdown some time ago.
maybe wasn't as useful as a CI job using valuable CPU minutes when it could
run in the development environment before the code was submitted? the same
could apply to this request if you consider that unlike the other
similar jobs (ex: sparse or "Static Analysis")
there is no need to install an additional (probably tricky to get tool)
Carlo
[1] https://travis-ci.com/github/git
On Mon, Aug 9, 2021 at 7:56 AM Phillip Wood [off-list ref] wrote:
quoted
Totally unrelated to this patch but while looking at the ci scripts I
noticed that we only run the linux-gcc-4.8 job on travis, not on github.
it is actually related and part of the reason why I sent this as an RFC.
travis[1] itself is not running, probably because it broke when
travis-ci.org was
shutdown some time ago.
maybe wasn't as useful as a CI job using valuable CPU minutes when it could
run in the development environment before the code was submitted? the same
could apply to this request if you consider that unlike the other
similar jobs (ex: sparse or "Static Analysis")
there is no need to install an additional (probably tricky to get tool)
I think there is value in running the CI jobs with -Wpedantic otherwise
we'll continually fixing patches up after they've been merged, I just
wonder if we need a separate job to do it. We could export
DEVOPTS=pedantic in ci/build-and-run-tests.sh or change config.mak.dev
to turn on -Wpedantic with DEVELOPER=1. Having said all that your commit
message also mentioned using a recent compiler to pick up any problem
early, I'm not sure how common that is but perhaps that makes a new job
worth it. If so there is a gcc docker image[1] which always has the
latest compiler.
Best Wishes
Phillip
[1] https://hub.docker.com/_/gcc
+struct oidtree_node {
+ /* n.k[] is used to store "struct object_id" */
+ struct cb_node n;
+};
+
[... snip ...]
+
+void oidtree_insert(struct oidtree *ot, const struct object_id *oid)
+{
+ struct oidtree_node *on;
+
+ if (!ot->mempool)
+ ot->mempool = allocate_alloc_state();
+ if (!oid->algo)
+ BUG("oidtree_insert requires oid->algo");
+
+ on = alloc_from_state(ot->mempool, sizeof(*on) + sizeof(*oid));
+ oidcpy_with_padding((struct object_id *)on->n.k, oid);
I think this object_id cast introduced undefined behaviour - here's
my layperson's interepretation of what's going on (full UBSAN output
is pasted below):
cb_node.k is a uint8_t[], and hence can be 1-byte aligned (on my
machine: offsetof(struct cb_node, k) == 21). We're casting its
pointer to "struct object_id *", and later try to access
object_id.hash within oidcpy_with_padding. My compiler assumes that
an object_id pointer needs to be 4-byte aligned, and reading from a
misaligned pointer means we hit undefined behaviour. (I think the
4-byte alignment requirement comes from the fact that object_id's
largest member is an int?)
I seem to recall struct alignment requirements being
architecture-dependent; and x86/x86-64 are the most liberal
w.r.t alignment requirements.
I think the problem here is not the alignment though, but the fact that
the nesting of structs with flexible arrays is forbidden by ISO/IEC
9899:2011 6.7.2.1¶3 that reads :
6.7.2.1 Structure and union specifiers
¶3 A structure or union shall not contain a member with incomplete or
function type (hence, a structure shall not contain an instance of
itself, but may contain a pointer to an instance of itself), except
that the last member of a structure with more than one named member
may have incomplete array type; such a structure (and any union
containing, possibly recursively, a member that is such a structure)
shall not be a member of a structure or an element of an array.
and it will throw a warning with clang 12
(-Wflexible-array-extensions) or gcc 11 (-Werror=pedantic) when using
DEVOPTS=pedantic
That's an additional problem. UBSan still reports the alignment error
with your patches.
René
+struct oidtree_node {
+ /* n.k[] is used to store "struct object_id" */
+ struct cb_node n;
+};
+
[... snip ...]
+
+void oidtree_insert(struct oidtree *ot, const struct object_id *oid)
+{
+ struct oidtree_node *on;
+
+ if (!ot->mempool)
+ ot->mempool = allocate_alloc_state();
+ if (!oid->algo)
+ BUG("oidtree_insert requires oid->algo");
+
+ on = alloc_from_state(ot->mempool, sizeof(*on) + sizeof(*oid));
+ oidcpy_with_padding((struct object_id *)on->n.k, oid);
I think this object_id cast introduced undefined behaviour - here's
my layperson's interepretation of what's going on (full UBSAN output
is pasted below):
cb_node.k is a uint8_t[], and hence can be 1-byte aligned (on my
machine: offsetof(struct cb_node, k) == 21). We're casting its
pointer to "struct object_id *", and later try to access
object_id.hash within oidcpy_with_padding. My compiler assumes that
an object_id pointer needs to be 4-byte aligned, and reading from a
misaligned pointer means we hit undefined behaviour. (I think the
4-byte alignment requirement comes from the fact that object_id's
largest member is an int?)
I seem to recall struct alignment requirements being
architecture-dependent; and x86/x86-64 are the most liberal
w.r.t alignment requirements.
quoted
quoted
I'm not sure what an elegant and idiomatic fix might be - IIUC it's
hard to guarantee misaligned access can't happen with a flex array
that's being used for arbitrary data (you would presumably have to
declare it as an array of whatever the largest supported type is, so
that you can guarantee correct alignment even when cbtree is used
with that type) - which might imply that k needs to be declared as a
void pointer? That in turn would make cbtree.c harder to read.
C11 has alignas. We could also make the member before the flex array,
otherbits, wider, e.g. promote it to uint32_t.
Ugh, no. cb_node should be as small as possible and (for our
current purposes) ->byte could be uint8_t.
Well, we can make both byte and otherbits uint16_t. That would require
a good comment explaining the reasoning and probably some rework later,
but might be the least intrusive solution for now.
quoted
A more parsimonious solution would be to turn the int member of struct
object_id, algo, into an unsigned char for now and reconsider the issue
once we support our 200th algorithm or so.
Yes, making struct object_id smaller would benefit all git users
(at least for the next few centuries :P).
True, we're currently using 4 bytes to distinguish between SHA-1 and
SHA-256, i.e. to represent a single bit. Reducing the size of struct
object_id from 36 bytes to 33 bytes seems quite significant.
I don't know how important the 4-byte alignment is, though. cf0983213c
(hash: add an algo member to struct object_id, 2021-04-26) doesn't
mention it, but the notes code seems to rely on it -- strange.
Overall this seems to be a good way to go -- after the next release.
René
From: René Scharfe <hidden> Date: 2021-08-14 20:01:18
The flexible array member "k" of struct cb_node is used to store the key
of the crit-bit tree node. It offers no alignment guarantees -- in fact
the current struct layout puts it one byte after a 4-byte aligned
address, i.e. guaranteed to be misaligned.
oidtree uses a struct object_id as cb_node key. Since cf0983213c (hash:
add an algo member to struct object_id, 2021-04-26) it requires 4-byte
alignment. The mismatch is reported by UndefinedBehaviorSanitizer at
runtime like this:
hash.h:277:2: runtime error: member access within misaligned address 0x00015000802d for type 'struct object_id', which requires 4 byte alignment
0x00015000802d: note: pointer points here
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
^
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior hash.h:277:2 in
We can fix that by:
1. eliminating the alignment requirement of struct object_id,
2. providing the alignment in struct cb_node, or
3. avoiding the issue by only using memcpy to access "k".
Currently we only store one of two values in "algo" in struct object_id.
We could use a uint8_t for that instead and widen it only once we add
support for our twohundredth algorithm or so. That would not only avoid
alignment issues, but also reduce the memory requirements for each
instance of struct object_id by ca. 9%.
Supporting keys with alignment requirements might be useful to spread
the use of crit-bit trees. It can be achieved by using a wider type for
"k" (e.g. uintmax_t), using different types for the members "byte" and
"otherbits" (e.g. uint16_t or uint32_t for each), or by avoiding the use
of flexible arrays like khash.h does.
This patch implements the third option, though, because it has the least
potential for causing side-effects and we're close to the next release.
If one of the other options is implemented later as well to get their
additional benefits we can get rid of the extra copies introduced here.
Reported-by: Andrzej Hunt <redacted>
Signed-off-by: René Scharfe <redacted>
---
cbtree.h | 2 +-
hash.h | 2 +-
oidtree.c | 20 +++++++++++++++-----
3 files changed, 17 insertions(+), 7 deletions(-)
Hi Carlo
On 09/08/2021 02:38, Carlo Marcelo Arenas Belón wrote:
quoted
similar to the recently added sparse task, it is nice to know as early
as possible.
add a dockerized build using fedora (that usually has the latest
gcc)
to be ahead of the curve and avoid older ISO C issues at the same time.
If we want to be able to compile with -Wpedantic then it might be
better just to turn it on unconditionally in config.mak.dev. Then
developers will see any errors before they push and the ci builds will
all use it rather than having to run an extra job. I had a quick scan
of the mail archive threads starting at [1,2] and it's not clear to me
why -Wpedaintic was added as an optional extra.
This is from wetware memory, so maybe it's wrong: But I recall that with
DEVOPTS=pedantic we used to have a giant wall of warnings not too long
ago (i.e. 1-3 years), and not just that referenced
USE_PARENS_AROUND_GETTEXT_N issue.
So yeah, I take and agree with your point that perhaps we should turn
this on by default for DEVELOPER if that's not the case.
On the other hand we can't combine that with
USE_PARENS_AROUND_GETTEXT_N, and to the extent that we think DEVELOPER
is useful, the entire point of having USE_PARENS_AROUND_GETTEXT_N seems
to be to catch exactly that sort of in-development issue.
So if we turn pedantic on in DEVOPTS by default, wouldn't it make sense
to at least have a CI job where we test that we compile with
USE_PARENS_AROUND_GETTEXT_N (which at that point would no be the default
anymore).
Or maybe the existing CI config matrix would already cover that,
i.e. we've got some entry point to it that doesn't go through
ci/lib.sh's DEVELOPER=1 that I've missed, if so nevermind the last two
paragraphs (three, including this one).
On Sun, Aug 08 2021, Carlo Marcelo Arenas Belón wrote:
-linux-gcc-4.8)
+linux-gcc-4.8|pedantic)
# Don't run the tests; we only care about whether Git can be
- # built with GCC 4.8, as it errors out on some undesired (C99)
- # constructs that newer compilers seem to quietly accept.
+ # built with GCC 4.8 or with pedantic
;;
*)
make test
Aside from Junio's suggested squash in <xmqqeeb1dumx.fsf@gitster.g>
downthread, which would obsolete this comment:
I think this would be clearer by not combining these two, i.e. just:
linux-gcc-4.8)
# <existing comment about that setup>
;;
pedantic)
# <A new comment, or not>
;;
We'll surely eventually end up with not just one, but N setups that want
to compile-only, so not having to reword one big comment referring to
them all when we do so leads to less churn...
From: Carlo Arenas <hidden> Date: 2021-08-31 20:28:34
On Mon, Aug 30, 2021 at 4:40 AM Ævar Arnfjörð Bjarmason
[off-list ref] wrote:
On Mon, Aug 09 2021, Phillip Wood wrote:
quoted
On 09/08/2021 02:38, Carlo Marcelo Arenas Belón wrote:
quoted
similar to the recently added sparse task, it is nice to know as early
as possible.
add a dockerized build using fedora (that usually has the latest
gcc)
to be ahead of the curve and avoid older ISO C issues at the same time.
If we want to be able to compile with -Wpedantic then it might be
better just to turn it on unconditionally in config.mak.dev. Then
developers will see any errors before they push and the ci builds will
all use it rather than having to run an extra job. I had a quick scan
of the mail archive threads starting at [1,2] and it's not clear to me
why -Wpedaintic was added as an optional extra.
This is from wetware memory, so maybe it's wrong: But I recall that with
DEVOPTS=pedantic we used to have a giant wall of warnings not too long
ago (i.e. 1-3 years), and not just that referenced
USE_PARENS_AROUND_GETTEXT_N issue.
when gcc (and clang) moved to target C99 by default (after version 5)
then that wall of errors went away. Indeed git can build cleanly in a
strict C99 compiler and until reftable was able to build even with gcc
2.95.3
the nostalgic can get it back with `CC=gcc -std=gnu89`, and indeed I
was considering this might be a good alternative to the defunct
gcc-4.8 job, where the weather balloons breaking with strict C89
compatibility could be explicitly coded.
So if we turn pedantic on in DEVOPTS by default, wouldn't it make sense
to at least have a CI job where we test that we compile with
USE_PARENS_AROUND_GETTEXT_N (which at that point would not be the default
anymore).
agree, and indeed was thinking it might be worth combining this job
with the SANITIZE one for efficiency.
Carlo
On Mon, Aug 30, 2021 at 4:40 AM Ævar Arnfjörð Bjarmason
[off-list ref] wrote:
quoted
On Mon, Aug 09 2021, Phillip Wood wrote:
quoted
On 09/08/2021 02:38, Carlo Marcelo Arenas Belón wrote:
quoted
similar to the recently added sparse task, it is nice to know as early
as possible.
add a dockerized build using fedora (that usually has the latest
gcc)
to be ahead of the curve and avoid older ISO C issues at the same time.
If we want to be able to compile with -Wpedantic then it might be
better just to turn it on unconditionally in config.mak.dev. Then
developers will see any errors before they push and the ci builds will
all use it rather than having to run an extra job. I had a quick scan
of the mail archive threads starting at [1,2] and it's not clear to me
why -Wpedaintic was added as an optional extra.
This is from wetware memory, so maybe it's wrong: But I recall that with
DEVOPTS=pedantic we used to have a giant wall of warnings not too long
ago (i.e. 1-3 years), and not just that referenced
USE_PARENS_AROUND_GETTEXT_N issue.
when gcc (and clang) moved to target C99 by default (after version 5)
then that wall of errors went away. Indeed git can build cleanly in a
strict C99 compiler and until reftable was able to build even with gcc
2.95.3
the nostalgic can get it back with `CC=gcc -std=gnu89`, and indeed I
was considering this might be a good alternative to the defunct
gcc-4.8 job, where the weather balloons breaking with strict C89
compatibility could be explicitly coded.
quoted
So if we turn pedantic on in DEVOPTS by default, wouldn't it make sense
to at least have a CI job where we test that we compile with
USE_PARENS_AROUND_GETTEXT_N (which at that point would not be the default
anymore).
agree, and indeed was thinking it might be worth combining this job
with the SANITIZE one for efficiency.
On the other hand maybe we should just remove
USE_PARENS_AROUND_GETTEXT_N entirely, i.e. always use the parens.
That facility seems to have been added in response to a one-off mistake
in 9c9b4f2f8b7 (standardize usage info string format, 2015-01-13). See
https://lore.kernel.org/git/ecb18f9d6ac56da0a61c3b98f8f2236@74d39fa044aa309eaea14b9f57fe79c/. That
later landed as 290c8e7a3fe (gettext.h: add parentheses around N_
expansion if supported, 2015-01-11).
It doesn't seem worth the effort to forever maintain this special case
and use CI resources etc. to catch what was effectively a one-off typo.
From: Carlo Arenas <hidden> Date: 2021-08-31 23:55:07
On Tue, Aug 31, 2021 at 1:57 PM Ævar Arnfjörð Bjarmason
[off-list ref] wrote:
On the other hand maybe we should just remove
USE_PARENS_AROUND_GETTEXT_N entirely, i.e. always use the parens.
that would break pedantic in all versions of gcc since it is a GNU
extension and is not valid in any C standard.
(unlike the ones we are using with weather balloons and that are valid C99)
the C standard says arrays can be initialized by a string literal
(obviously with quotes) and allows only optional {} which would avoid
the accidental concatenation that triggered this, but can't be used as
an alternative.
It doesn't seem worth the effort to forever maintain this special case
and use CI resources etc. to catch what was effectively a one-off typo.
under that argument, removing this safeguard might be also possible.
Carlo
From: Jeff King <hidden> Date: 2021-09-01 01:52:35
On Tue, Aug 31, 2021 at 04:54:52PM -0700, Carlo Arenas wrote:
On Tue, Aug 31, 2021 at 1:57 PM Ævar Arnfjörð Bjarmason
[off-list ref] wrote:
quoted
On the other hand maybe we should just remove
USE_PARENS_AROUND_GETTEXT_N entirely, i.e. always use the parens.
that would break pedantic in all versions of gcc since it is a GNU
extension and is not valid in any C standard.
(unlike the ones we are using with weather balloons and that are valid C99)
I think Ævar might have mis-spoke there. It would make sense to get rid
of the feature and _never_ use parens, which is always valid C (and does
not tickle pedantic, but also does not catch any accidental string
concatenation).
That actually seems quite reasonable to me.
Something like this, I guess?
@@ -409,15 +409,6 @@ all::# Define NEEDS_LIBRT if your platform requires linking with librt (glibc version# before 2.17) for clock_gettime and CLOCK_MONOTONIC.#-# Define USE_PARENS_AROUND_GETTEXT_N to "yes" if your compiler happily-# compiles the following initialization:-#-# static const char s[] = ("FOO");-#-# and define it to "no" if you need to remove the parentheses () around the-# constant. The default is "auto", which means to use parentheses if your-# compiler is detected to support it.-## Define HAVE_BSD_SYSCTL if your platform has a BSD-compatible sysctl function.## Define HAVE_GETDELIM if your system has the getdelim() function.
@@ -497,8 +488,7 @@ all::## pedantic:#-# Enable -pedantic compilation. This also disables-# USE_PARENS_AROUND_GETTEXT_N to produce only relevant warnings.+# Enable -pedantic compilation.GIT-VERSION-FILE:FORCE@$(SHELL_PATH)./GIT-VERSION-GEN
@@ -55,31 +55,7 @@ const char *Q_(const char *msgid, const char *plu, unsigned long n)}/* Mark msgid for translation but do not translate it. */-#if !USE_PARENS_AROUND_GETTEXT_N#define N_(msgid) msgid-#else-/*-*Strictlyspeaking,thiswillleadtoinvalidCwhen-*usedthisway:-*staticconstchars[]=N_("FOO");-*whichwillexpandto-*staticconstchars[]=("FOO");-*andinvalidC,theinitializerontherighthandsidemust-*bewithouttheparentheses.Butmanycompilersdoacceptit-*asalanguageextensionanditwillallowustocatchmistakes-*like:-*staticconstchar*msgs[]={-*N_("one")-*N_("two"),-*N_("three"),-*NULL-*};-*(noticethemissingcommaononeofthelines)byforcing-*acompilationerror,becauseparenthesised("one")("two")-*willnotgetsilentlyturnedinto("onetwo").-*/-#define N_(msgid) (msgid)-#endifconstchar*get_preferred_languages(void);intis_utf8_locale(void);
From: Carlo Marcelo Arenas Belón <hidden> Date: 2021-09-01 09:20:09
WARNING: this will break CI with seen when merged and unless the
kwown pedantic issue still remaining from fsmonitor[0] is merged
first (expected to come in a reroll)
this series has a different subject than v1 and that is currently
tracked as cb/ci-build-pedantic, but is a reroll (even if it discards
all changes from v1) and was originally suggested by Phillip as an
alternative.
because of that, it might conflict with changes proposed by Ævar[2]
but that are still not in "seen" AFAIK and merges cleanly otherwise.
first patch was suggested[1] by Peff, so hopefully my commit message
and his assumed SoB are still worth not mixing it with patch 2 (which
has a slight different but related focus and touches the same files)
but since it is no longer a single patch, lets go wild.
patches 3 and 4 are optional and mostly for RFC, so that a solution
to any possible issue that the retiring of USE_PARENS_AROUND_GETTEXT_N
are addressed.
Carlo Marcelo Arenas Belón (3):
developer: enable pedantic by default
developer: add an alternative script for detecting broken N_()
developer: move detect-compiler out of the main directory
Jeff King (1):
developer: retire USE_PARENS_AROUND_GETTEXT_N support
Makefile | 22 +-----
config.mak.dev | 7 +-
detect-compiler => devtools/detect-compiler | 0
.../find_accidentally_concat_i18n_strings.pl | 69 +++++++++++++++++++
gettext.h | 24 -------
git-compat-util.h | 4 --
6 files changed, 74 insertions(+), 52 deletions(-)
rename detect-compiler => devtools/detect-compiler (100%)
create mode 100755 devtools/find_accidentally_concat_i18n_strings.pl
[0] https://lore.kernel.org/git/20210809063004.73736-3-carenas@gmail.com/
[1] https://lore.kernel.org/git/YS7c3169x5Wk4PlA@coredump.intra.peff.net/
[2] https://lore.kernel.org/git/cover-v3-0.8-00000000000-20210831T132546Z-avarab@gmail.com/
--
2.33.0.481.g26d3bed244
From: Carlo Marcelo Arenas Belón <hidden> Date: 2021-09-01 09:20:23
From: Jeff King <redacted>
290c8e7a3f (gettext.h: add parentheses around N_ expansion if supported,
2015-01-11) adds a trick for GNU compilers that breaks the build, if an
accidental concatenation of i18n strings is used, but relies on invalid
C that gcc/clang just happen to allow (unless in pedantic mode).
remove that code and all subsequent fixes so that pedantic can run.
an alternative will be provided in a future patch.
Signed-off-by: Jeff King <redacted>
Signed-off-by: Carlo Marcelo Arenas Belón <redacted>
---
Makefile | 20 +-------------------
config.mak.dev | 2 --
gettext.h | 24 ------------------------
git-compat-util.h | 4 ----
4 files changed, 1 insertion(+), 49 deletions(-)
@@ -409,15 +409,6 @@ all::# Define NEEDS_LIBRT if your platform requires linking with librt (glibc version# before 2.17) for clock_gettime and CLOCK_MONOTONIC.#-# Define USE_PARENS_AROUND_GETTEXT_N to "yes" if your compiler happily-# compiles the following initialization:-#-# static const char s[] = ("FOO");-#-# and define it to "no" if you need to remove the parentheses () around the-# constant. The default is "auto", which means to use parentheses if your-# compiler is detected to support it.-## Define HAVE_BSD_SYSCTL if your platform has a BSD-compatible sysctl function.## Define HAVE_GETDELIM if your system has the getdelim() function.
@@ -497,8 +488,7 @@ all::## pedantic:#-# Enable -pedantic compilation. This also disables-# USE_PARENS_AROUND_GETTEXT_N to produce only relevant warnings.+# Enable -pedantic compilation.GIT-VERSION-FILE:FORCE@$(SHELL_PATH)./GIT-VERSION-GEN
@@ -55,31 +55,7 @@ const char *Q_(const char *msgid, const char *plu, unsigned long n)}/* Mark msgid for translation but do not translate it. */-#if !USE_PARENS_AROUND_GETTEXT_N#define N_(msgid) msgid-#else-/*-*Strictlyspeaking,thiswillleadtoinvalidCwhen-*usedthisway:-*staticconstchars[]=N_("FOO");-*whichwillexpandto-*staticconstchars[]=("FOO");-*andinvalidC,theinitializerontherighthandsidemust-*bewithouttheparentheses.Butmanycompilersdoacceptit-*asalanguageextensionanditwillallowustocatchmistakes-*like:-*staticconstchar*msgs[]={-*N_("one")-*N_("two"),-*N_("three"),-*NULL-*};-*(noticethemissingcommaononeofthelines)byforcing-*acompilationerror,becauseparenthesised("one")("two")-*willnotgetsilentlyturnedinto("onetwo").-*/-#define N_(msgid) (msgid)-#endifconstchar*get_preferred_languages(void);intis_utf8_locale(void);
From: Carlo Marcelo Arenas Belón <hidden> Date: 2021-09-01 09:20:28
with the codebase firmly C99 compatible and most compilers supporting
newer versions by default, could help bring visibility to problems.
reverse the DEVOPTS=pedantic flag to provide a fallback for people stuck
with gcc < 5 or some other compiler that either doesn't support this flag
or has issues with it, and while at it also enable -Wpedantic which used
to be controversial when Apple compilers and clang had widely divergent
version numbers.
ideally any compiler found to have issues with these flags will be added
to an exception, but leaving it open for now as a weather balloon.
[1] https://lore.kernel.org/git/20181127100557.53891-1-carenas@gmail.com/
Signed-off-by: Carlo Marcelo Arenas Belón <redacted>
---
Makefile | 4 ++--
config.mak.dev | 3 ++-
2 files changed, 4 insertions(+), 3 deletions(-)
@@ -486,9 +486,9 @@ all::# setting this flag the exceptions are removed, and all of# -Wextra is used.#-# pedantic:+# no-pedantic:#-# Enable -pedantic compilation.+# Disable -pedantic compilation.GIT-VERSION-FILE:FORCE@$(SHELL_PATH)./GIT-VERSION-GEN
From: Carlo Marcelo Arenas Belón <hidden> Date: 2021-09-01 09:20:33
obviously incomplete and buggy (ex: won't detect two overlapping matches)
it could be added to some makefile target or documented better as an
alternative to the compilation errors the previous implementation did,
but I have to admit, I haven't found any place in the codebase where
a valid concatenation could take place, so at least the tracking of
exceptions might not be worthy, even if it might be the best part.
Signed-off-by: Carlo Marcelo Arenas Belón <redacted>
---
.../find_accidentally_concat_i18n_strings.pl | 69 +++++++++++++++++++
1 file changed, 69 insertions(+)
create mode 100755 devtools/find_accidentally_concat_i18n_strings.pl
From: Carlo Marcelo Arenas Belón <hidden> Date: 2021-09-01 09:21:04
as suggested by Junio[1], and using the newly created subdirectory for
dev helpers that was introduced in a previous patch.
[1] https://lore.kernel.org/git/xmqqva4gpits.fsf@gitster-ct.c.googlers.com/
Signed-off-by: Carlo Marcelo Arenas Belón <redacted>
---
config.mak.dev | 2 +-
detect-compiler => devtools/detect-compiler | 0
2 files changed, 1 insertion(+), 1 deletion(-)
rename detect-compiler => devtools/detect-compiler (100%)
diff --git a/detect-compiler b/devtools/detect-compilersimilarity index 100%rename from detect-compilerrename to devtools/detect-compiler
--
2.33.0.481.g26d3bed244
From: Jeff King <hidden> Date: 2021-09-01 10:10:20
On Wed, Sep 01, 2021 at 02:19:37AM -0700, Carlo Marcelo Arenas Belón wrote:
first patch was suggested[1] by Peff, so hopefully my commit message
and his assumed SoB are still worth not mixing it with patch 2 (which
has a slight different but related focus and touches the same files)
but since it is no longer a single patch, lets go wild.
My SoB is fine there (though really Ævar did the actual thinking; I just
deleted a lot of lines in vim :) ).
Patch 2 looks good to me, though I kind of wonder if it is even worth
having an option to turn it off.
patches 3 and 4 are optional and mostly for RFC, so that a solution
to any possible issue that the retiring of USE_PARENS_AROUND_GETTEXT_N
are addressed.
IMHO the issue it is trying to find is not worth the inevitable problems
that hacky perl parsing of C will cause (both false positives and
negatives). Not a statement on your perl code, but just based on
previous experience.
So I'd probably take the first two patches, and leave the others.
-Peff
Remove the USE_PARENS_AROUND_GETTEXT_N compile-time option which was
meant to catch an inadvertent mistakes which is too obscure to
maintain this facility.
The backstory of how USE_PARENS_AROUND_GETTEXT_N came about is: When I
added the N_() macro in 65784830366 (i18n: add no-op _() and N_()
wrappers, 2011-02-22) it was defined as:
#define N_(msgid) (msgid)
This is non-standard C, as was noticed and fixed in 642f85faab2 (i18n:
avoid parenthesized string as array initializer,
2011-04-07). I.e. this needed to be defined as:
#define N_(msgid) msgid
Then in e62cd35a3e8 (i18n: log: mark parseopt strings for translation,
2012-08-20) when "builtin_log_usage" was marked for translation the
string concatenation the string concatenation for passing to usage()
added in 1c370ea4e51 (Show usage string for 'git log -h', 'git show
-h' and 'git diff -h', 2009-08-06) was faithfully preserved:
- "git log [<options>] [<since>..<until>] [[--] <path>...]\n"
- " or: git show [options] <object>...",
+ N_("git log [<options>] [<since>..<until>] [[--] <path>...]\n")
+ N_(" or: git show [options] <object>..."),
This was then fixed to be the expected array of usage strings in
e66dc0cc4b1 (log.c: fix translation markings, 2015-01-06) rather than
a string with multiple "\n"-delimited usage strings, and finally in
290c8e7a3fe (gettext.h: add parentheses around N_ expansion if
supported, 2015-01-11) USE_PARENS_AROUND_GETTEXT_N was added to ensure
this mistake didn't happen again.
I think that even if this was a N_()-specific issue this
USE_PARENS_AROUND_GETTEXT_N facility wouldn't be worth it, the issue
would be too rare to worry about.
But I also think that 290c8e7a3fe which introduced
USE_PARENS_AROUND_GETTEXT_N misattributed the problem. The issue
wasn't with the N_() macro added in e62cd35a3e8, but that before the
N_() macro existed in the codebase the initial migration to
parse_options() in 1c370ea4e51 continued passsing in a "\n"-delimited
string, when the new API it was migrating to supported and expected
the passing of an array.
Signed-off-by: Ævar Arnfjörð Bjarmason <redacted>
---
On Wed, Sep 01 2021, Jeff King wrote:
On Wed, Sep 01, 2021 at 02:19:37AM -0700, Carlo Marcelo Arenas Belón wrote:
quoted
first patch was suggested[1] by Peff, so hopefully my commit message
and his assumed SoB are still worth not mixing it with patch 2 (which
has a slight different but related focus and touches the same files)
but since it is no longer a single patch, lets go wild.
My SoB is fine there (though really Ævar did the actual thinking; I just
deleted a lot of lines in vim :) ).
Patch 2 looks good to me, though I kind of wonder if it is even worth
having an option to turn it off.
quoted
patches 3 and 4 are optional and mostly for RFC, so that a solution
to any possible issue that the retiring of USE_PARENS_AROUND_GETTEXT_N
are addressed.
IMHO the issue it is trying to find is not worth the inevitable problems
that hacky perl parsing of C will cause (both false positives and
negatives). Not a statement on your perl code, but just based on
previous experience.
So I'd probably take the first two patches, and leave the others.
I came up with this after reading your
[off-list ref] (the patch content is the
same) but before seeing that Carlo had beaten me to it here in
[off-list ref] upthread.
I don't care how this lands exactly, but thin (eye of the beholder and
all that) that the commit message above is better. Carlo: Feel free to
steal it partially or entirely, I also made this a "PATCH" instead of
"RFC PATCH" in case Junio feels like queuing this, then you could
build your DEVOPTS=pedantic by default here on top.
Makefile | 20 +-------------------
config.mak.dev | 2 --
gettext.h | 24 ------------------------
git-compat-util.h | 4 ----
4 files changed, 1 insertion(+), 49 deletions(-)
@@ -409,15 +409,6 @@ all::# Define NEEDS_LIBRT if your platform requires linking with librt (glibc version# before 2.17) for clock_gettime and CLOCK_MONOTONIC.#-# Define USE_PARENS_AROUND_GETTEXT_N to "yes" if your compiler happily-# compiles the following initialization:-#-# static const char s[] = ("FOO");-#-# and define it to "no" if you need to remove the parentheses () around the-# constant. The default is "auto", which means to use parentheses if your-# compiler is detected to support it.-## Define HAVE_BSD_SYSCTL if your platform has a BSD-compatible sysctl function.## Define HAVE_GETDELIM if your system has the getdelim() function.
@@ -497,8 +488,7 @@ all::## pedantic:#-# Enable -pedantic compilation. This also disables-# USE_PARENS_AROUND_GETTEXT_N to produce only relevant warnings.+# Enable -pedantic compilation.GIT-VERSION-FILE:FORCE@$(SHELL_PATH)./GIT-VERSION-GEN
@@ -55,31 +55,7 @@ const char *Q_(const char *msgid, const char *plu, unsigned long n)}/* Mark msgid for translation but do not translate it. */-#if !USE_PARENS_AROUND_GETTEXT_N#define N_(msgid) msgid-#else-/*-*Strictlyspeaking,thiswillleadtoinvalidCwhen-*usedthisway:-*staticconstchars[]=N_("FOO");-*whichwillexpandto-*staticconstchars[]=("FOO");-*andinvalidC,theinitializerontherighthandsidemust-*bewithouttheparentheses.Butmanycompilersdoacceptit-*asalanguageextensionanditwillallowustocatchmistakes-*like:-*staticconstchar*msgs[]={-*N_("one")-*N_("two"),-*N_("three"),-*NULL-*};-*(noticethemissingcommaononeofthelines)byforcing-*acompilationerror,becauseparenthesised("one")("two")-*willnotgetsilentlyturnedinto("onetwo").-*/-#define N_(msgid) (msgid)-#endifconstchar*get_preferred_languages(void);intis_utf8_locale(void);
[I should have included this in my just-sent [1], but forgot]
On Wed, Sep 01 2021, Jeff King wrote:
On Wed, Sep 01, 2021 at 02:19:37AM -0700, Carlo Marcelo Arenas Belón wrote:
quoted
first patch was suggested[1] by Peff, so hopefully my commit message
and his assumed SoB are still worth not mixing it with patch 2 (which
has a slight different but related focus and touches the same files)
but since it is no longer a single patch, lets go wild.
My SoB is fine there (though really Ævar did the actual thinking; I just
deleted a lot of lines in vim :) ).
Patch 2 looks good to me, though I kind of wonder if it is even worth
having an option to turn it off.
quoted
patches 3 and 4 are optional and mostly for RFC, so that a solution
to any possible issue that the retiring of USE_PARENS_AROUND_GETTEXT_N
are addressed.
IMHO the issue it is trying to find is not worth the inevitable problems
that hacky perl parsing of C will cause (both false positives and
negatives). Not a statement on your perl code, but just based on
previous experience.
So I'd probably take the first two patches, and leave the others.
Agreed. Per the rationale in my version of the commit messsage for
Carlo's 1/4 at [1] I don't think this was ever worth it.
I.e. it wasn't even an N_()-specific issue to begin with, but just a
migration from usage() (takes a string) to usage_with_options() (takes
an array of strings).
I just submitted a related series at [2] to fix the alignment of
continued strings containing "\n" in parse-options.c, which is the
reason we need to support "\n"-continued strings at all in
parse-options.c.
So I think (per [1]) that we should just remove
USE_PARENS_AROUND_GETTEXT_N, and that the 3/4 here isn't needed at all
(aside from concerns about parsing C with Perl).
But in the future we needed any assertion for this sort of thing at all
it would be better built on top of my [2]. I.e. parse-options.c could do
some basic sanity checking on the usage array it takes, we'd then end up
detecting the issue USE_PARENS_AROUND_GETTEXT_N was trying to address,
and more (such as the alignment problems I fixed in 1/2 of my [2]).
1. https://lore.kernel.org/git/patch-1.1-d24f1df5d49-20210901T112248Z-avarab@gmail.com
2. https://lore.kernel.org/git/cover-0.2-00000000000-20210901T110917Z-avarab@gmail.com
From: Eric Sunshine <hidden> Date: 2021-09-01 17:31:27
On Wed, Sep 1, 2021 at 7:26 AM Ævar Arnfjörð Bjarmason [off-list ref] wrote:
[...]
Then in e62cd35a3e8 (i18n: log: mark parseopt strings for translation,
2012-08-20) when "builtin_log_usage" was marked for translation the
string concatenation the string concatenation for passing to usage()
added in 1c370ea4e51 (Show usage string for 'git log -h', 'git show
-h' and 'git diff -h', 2009-08-06) was faithfully preserved:
"...the string concatenation the string concatenation..."
From: Carlo Arenas <hidden> Date: 2021-09-01 18:03:21
On Wed, Sep 1, 2021 at 4:34 AM Ævar Arnfjörð Bjarmason [off-list ref] wrote:
On Wed, Sep 01 2021, Jeff King wrote:
quoted
Patch 2 looks good to me, though I kind of wonder if it is even worth
having an option to turn it off.
I failed to mention "Patch 2" isn't ready as it will break the mingw64
builds in Windows.
While I also hope there is no need to have an option to turn it off,
realistically I expect the wall of errors is still there for non
gcc/clang compilers and I am curious if some developer still using
RHEL 7 (or a clone) will report back and will be forced to use it.
quoted
IMHO the issue it is trying to find is not worth the inevitable problems
that hacky perl parsing of C will cause (both false positives and
negatives). Not a statement on your perl code, but just based on
previous experience.
So I'd probably take the first two patches, and leave the others.
Maybe better to discard the whole series and rebase it on top of Ævar's then
So I think (per [1]) that we should just remove
USE_PARENS_AROUND_GETTEXT_N, and that the 3/4 here isn't needed at all
(aside from concerns about parsing C with Perl).
But in the future we need any assertion for this sort of thing at all
it would be better built on top of my [2]. I.e. parse-options.c could do
some basic sanity checking on the usage array it takes, we'd then end up
detecting the issue USE_PARENS_AROUND_GETTEXT_N was trying to address,
and more (such as the alignment problems I fixed in 1/2 of my [2]).
Regardless of how ugly my perl script was, I don't think this specific
issue could be
handled by the C code, as it needs to be done with preprocessed sources.
note also, it is not really parsing C, but just looking at a regex
which could have been as well handled with a simple grep.
The script was built under the incorrect assumption it would be useful
to track exceptions and have a way to keep that state (as well as the
code) cleanly out of the way (which is why patch 4 is also there).
Carlo
From: Jeff King <hidden> Date: 2021-09-02 09:13:53
On Wed, Sep 01, 2021 at 01:25:52PM +0200, Ævar Arnfjörð Bjarmason wrote:
I don't care how this lands exactly, but thin (eye of the beholder and
all that) that the commit message above is better. Carlo: Feel free to
steal it partially or entirely, I also made this a "PATCH" instead of
"RFC PATCH" in case Junio feels like queuing this, then you could
build your DEVOPTS=pedantic by default here on top.
FWIW, I think it is better, too. :)
One small typo (in addition to the one Eric noted):
Remove the USE_PARENS_AROUND_GETTEXT_N compile-time option which was
meant to catch an inadvertent mistakes which is too obscure to
maintain this facility.
From: Carlo Marcelo Arenas Belón <hidden> Date: 2021-09-03 17:03:03
This series enables pedantic mode for building when DEVELOPER=1 is
used and as an alternative to only enabling it in one CI job, that
was merged to "seen" as part of cb/ci-build-pedantic.
The second patch is really an independent prerequisite to ensure
that it doesn't break the build for Windows and is the minimal change
possible.
Additional changes needed for the git-for-windows/git fork main to be
posted independently.
It merges and builds successfully all the way to "seen" IF the known
problem reported earlier[1] and expected as part of a reroll of
jh/builtin-fsmonitor is merged first.
[1] https://lore.kernel.org/git/20210809063004.73736-3-carenas@gmail.com/
Carlo Marcelo Arenas Belón (2):
win32: allow building with pedantic mode enabled
developer: enable pedantic by default
Ævar Arnfjörð Bjarmason (1):
gettext: remove optional non-standard parens in N_() definition
Makefile | 22 ++--------------------
compat/nedmalloc/nedmalloc.c | 2 +-
compat/win32/lazyload.h | 2 +-
config.mak.dev | 19 +++++++++++--------
gettext.h | 24 ------------------------
git-compat-util.h | 4 ----
6 files changed, 15 insertions(+), 58 deletions(-)
--
v3
- replace the first patch with an even better worded one from Ævar
- include minor changes needed for Windows
- version check new flags to avoid risk of breaking old compilers
- drop alternative
v2
- enable pedantic globally instead of single job as suggested by Phillip
- propose an alternative solution for USE_PARENS_AROUND_GETTEXT_N
v1
- create job to check for pedantic compilation (only in Linux, using
Fedora)
2.33.0.481.g26d3bed244
From: Carlo Marcelo Arenas Belón <hidden> Date: 2021-09-03 17:03:04
From: Ævar Arnfjörð Bjarmason <redacted>
Remove the USE_PARENS_AROUND_GETTEXT_N compile-time option which was
meant to catch an inadvertent mistake which is too obscure to
maintain this facility.
The backstory of how USE_PARENS_AROUND_GETTEXT_N came about is: When I
added the N_() macro in 65784830366 (i18n: add no-op _() and N_()
wrappers, 2011-02-22) it was defined as:
#define N_(msgid) (msgid)
This is non-standard C, as was noticed and fixed in 642f85faab2 (i18n:
avoid parenthesized string as array initializer, 2011-04-07).
I.e. this needed to be defined as:
#define N_(msgid) msgid
Then in e62cd35a3e8 (i18n: log: mark parseopt strings for translation,
2012-08-20) when "builtin_log_usage" was marked for translation the
string concatenation for passing to usage() added in 1c370ea4e51
(Show usage string for 'git log -h', 'git show -h' and 'git diff -h',
2009-08-06) was faithfully preserved:
- "git log [<options>] [<since>..<until>] [[--] <path>...]\n"
- " or: git show [options] <object>...",
+ N_("git log [<options>] [<since>..<until>] [[--] <path>...]\n")
+ N_(" or: git show [options] <object>..."),
This was then fixed to be the expected array of usage strings in
e66dc0cc4b1 (log.c: fix translation markings, 2015-01-06) rather than
a string with multiple "\n"-delimited usage strings, and finally in
290c8e7a3fe (gettext.h: add parentheses around N_ expansion if
supported, 2015-01-11) USE_PARENS_AROUND_GETTEXT_N was added to ensure
this mistake didn't happen again.
I think that even if this was a N_()-specific issue this
USE_PARENS_AROUND_GETTEXT_N facility wouldn't be worth it, the issue
would be too rare to worry about.
But I also think that 290c8e7a3fe which introduced
USE_PARENS_AROUND_GETTEXT_N misattributed the problem. The issue
wasn't with the N_() macro added in e62cd35a3e8, but that before the
N_() macro existed in the codebase the initial migration to
parse_options() in 1c370ea4e51 continued passsing in a "\n"-delimited
string, when the new API it was migrating to supported and expected
the passing of an array.
Helped-by: Eric Sunshine [off-list ref]
Signed-off-by: Ævar Arnfjörð Bjarmason <redacted>
Signed-off-by: Carlo Marcelo Arenas Belón <redacted>
---
Makefile | 20 +-------------------
config.mak.dev | 2 --
gettext.h | 24 ------------------------
git-compat-util.h | 4 ----
4 files changed, 1 insertion(+), 49 deletions(-)
@@ -409,15 +409,6 @@ all::# Define NEEDS_LIBRT if your platform requires linking with librt (glibc version# before 2.17) for clock_gettime and CLOCK_MONOTONIC.#-# Define USE_PARENS_AROUND_GETTEXT_N to "yes" if your compiler happily-# compiles the following initialization:-#-# static const char s[] = ("FOO");-#-# and define it to "no" if you need to remove the parentheses () around the-# constant. The default is "auto", which means to use parentheses if your-# compiler is detected to support it.-## Define HAVE_BSD_SYSCTL if your platform has a BSD-compatible sysctl function.## Define HAVE_GETDELIM if your system has the getdelim() function.
@@ -497,8 +488,7 @@ all::## pedantic:#-# Enable -pedantic compilation. This also disables-# USE_PARENS_AROUND_GETTEXT_N to produce only relevant warnings.+# Enable -pedantic compilation.GIT-VERSION-FILE:FORCE@$(SHELL_PATH)./GIT-VERSION-GEN
@@ -55,31 +55,7 @@ const char *Q_(const char *msgid, const char *plu, unsigned long n)}/* Mark msgid for translation but do not translate it. */-#if !USE_PARENS_AROUND_GETTEXT_N#define N_(msgid) msgid-#else-/*-*Strictlyspeaking,thiswillleadtoinvalidCwhen-*usedthisway:-*staticconstchars[]=N_("FOO");-*whichwillexpandto-*staticconstchars[]=("FOO");-*andinvalidC,theinitializerontherighthandsidemust-*bewithouttheparentheses.Butmanycompilersdoacceptit-*asalanguageextensionanditwillallowustocatchmistakes-*like:-*staticconstchar*msgs[]={-*N_("one")-*N_("two"),-*N_("three"),-*NULL-*};-*(noticethemissingcommaononeofthelines)byforcing-*acompilationerror,becauseparenthesised("one")("two")-*willnotgetsilentlyturnedinto("onetwo").-*/-#define N_(msgid) (msgid)-#endifconstchar*get_preferred_languages(void);intis_utf8_locale(void);
From: Carlo Marcelo Arenas Belón <hidden> Date: 2021-09-03 17:03:06
In preparation to building with pedantic mode enabled, change a couple
of places where the current mingw gcc compiler provided with the SDK
reports issues.
A full fix for the incompatible use of (void *) to store function
pointers has been punted, with the minimal change to instead use a
generic function pointer (FARPROC), and therefore the (hopefully)
temporary need to disable incompatible pointer warnings.
Signed-off-by: Carlo Marcelo Arenas Belón <redacted>
---
This is all that is needed to build cleanly once merged to maint/master/next
There is at least one fix needed on top for seen, that was sent already
and is expected as part of a different reroll as well of several more for
git-for-windows/main that will be send independently.
compat/nedmalloc/nedmalloc.c | 2 +-
compat/win32/lazyload.h | 2 +-
config.mak.dev | 13 ++++++++-----
3 files changed, 10 insertions(+), 7 deletions(-)
@@ -37,7 +37,7 @@ struct proc_addr {#define INIT_PROC_ADDR(function) \(function=get_proc_addr(&proc_addr_##function))-staticinlinevoid*get_proc_addr(structproc_addr*proc)+staticinlineFARPROCget_proc_addr(structproc_addr*proc){/* only do this once */if(!proc->initialized){
From: Carlo Marcelo Arenas Belón <hidden> Date: 2021-09-03 17:03:07
With the codebase firmly C99 compatible and most compilers supporting
newer versions by default, it could help bring visibility to problems.
Reverse the DEVOPTS=pedantic flag to provide a fallback for people stuck
with gcc < 5 or some other compiler that either doesn't support this flag
or has issues with it, and while at it also enable -Wpedantic which used
to be controversial[1] when Apple compilers and clang had widely divergent
version numbers.
Ideally any compiler found to have issues with these flags will be added
to an exception, and indeed, one was added to safely process windows
headers that would use non standard print identifiers, but it is expected
that more will be needed, so it could be considered a weather balloon.
[1] https://lore.kernel.org/git/20181127100557.53891-1-carenas@gmail.com/
Signed-off-by: Carlo Marcelo Arenas Belón <redacted>
---
Makefile | 4 ++--
config.mak.dev | 4 +++-
2 files changed, 5 insertions(+), 3 deletions(-)
@@ -486,9 +486,9 @@ all::# setting this flag the exceptions are removed, and all of# -Wextra is used.#-# pedantic:+# no-pedantic:#-# Enable -pedantic compilation.+# Disable -pedantic compilation.GIT-VERSION-FILE:FORCE@$(SHELL_PATH)./GIT-VERSION-GEN
From: René Scharfe <hidden> Date: 2021-09-03 18:47:45
Am 03.09.21 um 19:02 schrieb Carlo Marcelo Arenas Belón:
quoted hunk
In preparation to building with pedantic mode enabled, change a couple
of places where the current mingw gcc compiler provided with the SDK
reports issues.
A full fix for the incompatible use of (void *) to store function
pointers has been punted, with the minimal change to instead use a
generic function pointer (FARPROC), and therefore the (hopefully)
temporary need to disable incompatible pointer warnings.
Signed-off-by: Carlo Marcelo Arenas Belón <redacted>
---
This is all that is needed to build cleanly once merged to maint/master/next
There is at least one fix needed on top for seen, that was sent already
and is expected as part of a different reroll as well of several more for
git-for-windows/main that will be send independently.
compat/nedmalloc/nedmalloc.c | 2 +-
compat/win32/lazyload.h | 2 +-
config.mak.dev | 13 ++++++++-----
3 files changed, 10 insertions(+), 7 deletions(-)
This change is not mentioned in the commit message. Clang on MacOS
doesn't like the original code either and report if USE_NED_ALLOCATOR is
enabled it reports:
compat/nedmalloc/nedmalloc.c:513:82: error: format specifies type 'void *' but the argument has type 'threadcacheblk *' (aka 'struct threadcacheblk_t *') [-Werror,-Wformat-pedantic]
fprintf(stderr, "Attempt to free already freed memory block %p - aborting!\n", tck);
~~ ^~~
This makes no sense to me, though: Any pointer can be converted to a
void pointer without a cast in C. GCC doesn't require void pointers
for %p even with -pedantic.
A slightly shorter fix would be to replace "tck" with "mem". Not as
obvious without further context, though.
René
This change is not mentioned in the commit message.
got me there, I was intentionally trying to ignore it since nedmalloc gives
me PTSD and is obsoleted AFAIK[1], so just adding a casting to void (while
ugly) was also less intrusive.
compat/nedmalloc/nedmalloc.c:513:82: error: format specifies type 'void *' but the argument has type 'threadcacheblk *' (aka 'struct threadcacheblk_t *') [-Werror,-Wformat-pedantic]
fprintf(stderr, "Attempt to free already freed memory block %p - aborting!\n", tck);
~~ ^~~
This makes no sense to me, though: Any pointer can be converted to a
void pointer without a cast in C. GCC doesn't require void pointers
for %p even with -pedantic.
strange, gcc-11 prints the following in MacOS for me:
compat/nedmalloc/nedmalloc.c: In function 'threadcache_free':
compat/nedmalloc/nedmalloc.c:522:78: warning: format '%p' expects argument of type 'void *', but argument 3 has type 'threadcacheblk *' {aka 'struct threadcacheblk_t *'} [-Wformat=]
522 | fprintf(stderr, "Attempt to free already freed memory block %p - aborting!\n", tck);
| ~^ ~~~
| | |
| void * threadcacheblk * {aka struct threadcacheblk_t *}
I think the rationale is that it is better to be safe than sorry, and since
the parameter is variadic there is no chance for the compiler to do any
implicit type casting (unless one is provided explicitly).
clang 14 does also trigger a warning, so IMHO this code will be needed
until nedmalloc is retired.
A slightly shorter fix would be to replace "tck" with "mem". Not as
obvious without further context, though.
so something like this on top?
Carlo
---- > 8 ----
This change is not mentioned in the commit message.
got me there, I was intentionally trying to ignore it since nedmalloc gives
me PTSD and is obsoleted AFAIK[1], so just adding a casting to void (while
ugly) was also less intrusive.
quoted
compat/nedmalloc/nedmalloc.c:513:82: error: format specifies type 'void *' but the argument has type 'threadcacheblk *' (aka 'struct threadcacheblk_t *') [-Werror,-Wformat-pedantic]
fprintf(stderr, "Attempt to free already freed memory block %p - aborting!\n", tck);
~~ ^~~
This makes no sense to me, though: Any pointer can be converted to a
void pointer without a cast in C. GCC doesn't require void pointers
for %p even with -pedantic.
strange, gcc-11 prints the following in MacOS for me:
compat/nedmalloc/nedmalloc.c: In function 'threadcache_free':
compat/nedmalloc/nedmalloc.c:522:78: warning: format '%p' expects argument of type 'void *', but argument 3 has type 'threadcacheblk *' {aka 'struct threadcacheblk_t *'} [-Wformat=]
522 | fprintf(stderr, "Attempt to free already freed memory block %p - aborting!\n", tck);
| ~^ ~~~
| | |
| void * threadcacheblk * {aka struct threadcacheblk_t *}
I think the rationale is that it is better to be safe than sorry, and since
the parameter is variadic there is no chance for the compiler to do any
implicit type casting (unless one is provided explicitly).
True, other pointers could be smaller on some machines.
clang 14 does also trigger a warning, so IMHO this code will be needed
until nedmalloc is retired.
quoted
A slightly shorter fix would be to replace "tck" with "mem". Not as
obvious without further context, though.
so something like this on top?
Nah, I like your original version better now that I understand the warning..
Though for upstream it would make more sense to report the caller-supplied
pointer value in the error message than a casted one..
This change is not mentioned in the commit message.
got me there, I was intentionally trying to ignore it since nedmalloc gives
me PTSD and is obsoleted AFAIK[1], so just adding a casting to void (while
ugly) was also less intrusive.
Expected your [1] to stand for a footnote, and got confused when I found none.
The last commit in https://github.com/ned14/nedmalloc is from seven years ago
and this repository is archived, with the author still being active on GitHub.
Seems like nedmalloc reached its end of life. Has there been an official
announcement?
quoted
strange, gcc-11 prints the following in MacOS for me:
compat/nedmalloc/nedmalloc.c: In function 'threadcache_free':
compat/nedmalloc/nedmalloc.c:522:78: warning: format '%p' expects argument of type 'void *', but argument 3 has type 'threadcacheblk *' {aka 'struct threadcacheblk_t *'} [-Wformat=]
522 | fprintf(stderr, "Attempt to free already freed memory block %p - aborting!\n", tck);
| ~^ ~~~
| | |
| void * threadcacheblk * {aka struct threadcacheblk_t *}
This change is not mentioned in the commit message.
got me there, I was intentionally trying to ignore it since nedmalloc gives
me PTSD and is obsoleted AFAIK[1], so just adding a casting to void (while
ugly) was also less intrusive.
Expected your [1] to stand for a footnote, and got confused when I found none.
The last commit in https://github.com/ned14/nedmalloc is from seven years ago
and this repository is archived, with the author still being active on GitHub.
Seems like nedmalloc reached its end of life. Has there been an official
announcement?
Apologies; this is the [1] I was referring to:
[1] https://lore.kernel.org/git/nycvar.QRO.7.76.6.1908082213400.46@tvgsbejva
qbjf.bet/
TLDR; nedmalloc works but is only stable in Windows, and indeed shows other
warnings in macOS that would have broken a DEVELOPER=1 build as well
which I am ignoring.
compat/nedmalloc/nedmalloc.c:326:8: warning: address of array
'p->caches' will always evaluate to 'true' [-Wpointer-bool-conversion]
if(p->caches)
~~ ~~~^~~~~~
1 warning generated.
Carlo
On Fri, Sep 03 2021, Carlo Marcelo Arenas Belón wrote:
This series enables pedantic mode for building when DEVELOPER=1 is
used and as an alternative to only enabling it in one CI job, that
was merged to "seen" as part of cb/ci-build-pedantic.
The second patch is really an independent prerequisite to ensure
that it doesn't break the build for Windows and is the minimal change
possible.
Additional changes needed for the git-for-windows/git fork main to be
posted independently.
It merges and builds successfully all the way to "seen" IF the known
problem reported earlier[1] and expected as part of a reroll of
jh/builtin-fsmonitor is merged first.
[1] https://lore.kernel.org/git/20210809063004.73736-3-carenas@gmail.com/
Carlo Marcelo Arenas Belón (2):
win32: allow building with pedantic mode enabled
developer: enable pedantic by default
Ævar Arnfjörð Bjarmason (1):
gettext: remove optional non-standard parens in N_() definition
This whole series looks good to me, thanks for picking up my patch as
the 1/3. The only comment I have on it (doesn't need a re-roll) is that
I found the first paragraph in 2/3 slightly confusing, i.e.:
In preparation to building with pedantic mode enabled, change a couple
of places where the current mingw gcc compiler provided with the SDK
reports issues.
With "the SDK" we're talking about the Win32 SDK, which is implicit from
the subject line. I'd find something like this less confusing:
In preparation for building with DEVOPTS=pedantic enabled
everywhere, change a couple of places where we'd get Win32 breakes
under the GCC version provided wit hthe current MinGW version.
Or something. I'm not sure if this /only/ impacts Win32, or just that
compiler version. Some of the diffstat is win32-only, but nod nedmalloc,
but I see there's some parallel discussion about whether that's in
effect win32-specific.
Anyway, that's all a tiny nit. In general I like the change. I also
checked that an existing DEVOPTS=pedantic wouldn't accidentally enable
DEVOPTS=no-pedantic (i.e. that it wasn't a glob), but it doesn't, since
that's not how $(filter) works.
On Fri, Sep 03 2021, Carlo Marcelo Arenas Belón wrote:
quoted hunk
From: Ævar Arnfjörð Bjarmason <redacted>
Remove the USE_PARENS_AROUND_GETTEXT_N compile-time option which was
meant to catch an inadvertent mistake which is too obscure to
maintain this facility.
The backstory of how USE_PARENS_AROUND_GETTEXT_N came about is: When I
added the N_() macro in 65784830366 (i18n: add no-op _() and N_()
wrappers, 2011-02-22) it was defined as:
#define N_(msgid) (msgid)
This is non-standard C, as was noticed and fixed in 642f85faab2 (i18n:
avoid parenthesized string as array initializer, 2011-04-07).
I.e. this needed to be defined as:
#define N_(msgid) msgid
Then in e62cd35a3e8 (i18n: log: mark parseopt strings for translation,
2012-08-20) when "builtin_log_usage" was marked for translation the
string concatenation for passing to usage() added in 1c370ea4e51
(Show usage string for 'git log -h', 'git show -h' and 'git diff -h',
2009-08-06) was faithfully preserved:
- "git log [<options>] [<since>..<until>] [[--] <path>...]\n"
- " or: git show [options] <object>...",
+ N_("git log [<options>] [<since>..<until>] [[--] <path>...]\n")
+ N_(" or: git show [options] <object>..."),
This was then fixed to be the expected array of usage strings in
e66dc0cc4b1 (log.c: fix translation markings, 2015-01-06) rather than
a string with multiple "\n"-delimited usage strings, and finally in
290c8e7a3fe (gettext.h: add parentheses around N_ expansion if
supported, 2015-01-11) USE_PARENS_AROUND_GETTEXT_N was added to ensure
this mistake didn't happen again.
I think that even if this was a N_()-specific issue this
USE_PARENS_AROUND_GETTEXT_N facility wouldn't be worth it, the issue
would be too rare to worry about.
But I also think that 290c8e7a3fe which introduced
USE_PARENS_AROUND_GETTEXT_N misattributed the problem. The issue
wasn't with the N_() macro added in e62cd35a3e8, but that before the
N_() macro existed in the codebase the initial migration to
parse_options() in 1c370ea4e51 continued passsing in a "\n"-delimited
string, when the new API it was migrating to supported and expected
the passing of an array.
Helped-by: Eric Sunshine [off-list ref]
Signed-off-by: Ævar Arnfjörð Bjarmason <redacted>
Signed-off-by: Carlo Marcelo Arenas Belón <redacted>
---
Makefile | 20 +-------------------
config.mak.dev | 2 --
gettext.h | 24 ------------------------
git-compat-util.h | 4 ----
4 files changed, 1 insertion(+), 49 deletions(-)
@@ -409,15 +409,6 @@ all::# Define NEEDS_LIBRT if your platform requires linking with librt (glibc version# before 2.17) for clock_gettime and CLOCK_MONOTONIC.#-# Define USE_PARENS_AROUND_GETTEXT_N to "yes" if your compiler happily-# compiles the following initialization:-#-# static const char s[] = ("FOO");-#-# and define it to "no" if you need to remove the parentheses () around the-# constant. The default is "auto", which means to use parentheses if your-# compiler is detected to support it.-## Define HAVE_BSD_SYSCTL if your platform has a BSD-compatible sysctl function.## Define HAVE_GETDELIM if your system has the getdelim() function.
@@ -497,8 +488,7 @@ all::## pedantic:#-# Enable -pedantic compilation. This also disables-# USE_PARENS_AROUND_GETTEXT_N to produce only relevant warnings.+# Enable -pedantic compilation.GIT-VERSION-FILE:FORCE@$(SHELL_PATH)./GIT-VERSION-GEN
@@ -55,31 +55,7 @@ const char *Q_(const char *msgid, const char *plu, unsigned long n)}/* Mark msgid for translation but do not translate it. */-#if !USE_PARENS_AROUND_GETTEXT_N#define N_(msgid) msgid-#else-/*-*Strictlyspeaking,thiswillleadtoinvalidCwhen-*usedthisway:-*staticconstchars[]=N_("FOO");-*whichwillexpandto-*staticconstchars[]=("FOO");-*andinvalidC,theinitializerontherighthandsidemust-*bewithouttheparentheses.Butmanycompilersdoacceptit-*asalanguageextensionanditwillallowustocatchmistakes-*like:-*staticconstchar*msgs[]={-*N_("one")-*N_("two"),-*N_("three"),-*NULL-*};-*(noticethemissingcommaononeofthelines)byforcing-*acompilationerror,becauseparenthesised("one")("two")-*willnotgetsilentlyturnedinto("onetwo").-*/-#define N_(msgid) (msgid)-#endifconstchar*get_preferred_languages(void);intis_utf8_locale(void);
I noticed today that I wasn't warned about some incompatible function
pointer signatures (that I expected to be warned about) due to this
line - could the condition of adding this compiler flag be further
narrowed down? gcc -v says:
gcc version 10.3.0 (Debian 10.3.0-9+build2)
On my system, if I remove that line, "make DEVELOPER=1" is still
successful.
I noticed today that I wasn't warned about some incompatible function
pointer signatures (that I expected to be warned about) due to this
line - could the condition of adding this compiler flag be further
narrowed down? gcc -v says:
Apologies; it is gone already in "seen" (and hopefully soon in "next")
by merging js/win-lazyload-buildfix[1]
gcc version 10.3.0 (Debian 10.3.0-9+build2)
On my system, if I remove that line, "make DEVELOPER=1" is still
successful.