speed up alt_odb_usable() with many alternates
PATCH 1/1 speed up alt_odb_usable() with many alternates
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.
---
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(-)
object-file.c +22 -11
@@ -517,9 +517,9 @@ const char *loose_object_path(struct repository *r, struct strbuf *buf,*/ static int alt_odb_usable (struct raw_object_store *o,struct strbuf *path, -const char *normalized_objdir) +const char *normalized_objdir,khiter_t *pos) { -struct object_directory *odb; +int r;/* Detect cases where alternate disappeared */ if (!is_directory (path->buf)) {
@@ -533,14 +533,22 @@ static int alt_odb_usable(struct raw_object_store *o,* Prevent the common mistake of listing the same * thing twice, or object directory itself. */ -for (odb = o->odb; odb; odb = odb->next) { -if (!fspathcmp (path->buf, odb->path)) -return 0 ; +if (!o->odb_by_path) { +khiter_t p; + + 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); +if (r <0 )die_errno (_ ("kh_put_odb_path_map" )); +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" )); +/* r: 0 = exists, 1 = never used, 2 = deleted */ +return r ==0 ?0 :1 ; }/*
@@ -566,6 +574,7 @@ static int link_alt_odb_entry(struct repository *r, const char *entry, {struct object_directory *ent;struct strbuf pathbuf =STRBUF_INIT ; +khiter_t pos;if (!is_absolute_path (entry) && relative_base) {strbuf_realpath (&pathbuf, relative_base,1 );
@@ -587,23 +596,25 @@ static int link_alt_odb_entry(struct repository *r, const char *entry,while (pathbuf.len && pathbuf.buf[pathbuf.len -1 ] =='/' )strbuf_setlen (&pathbuf, pathbuf.len -1 ); -if (!alt_odb_usable (r->objects, &pathbuf, normalized_objdir)) { +if (!alt_odb_usable (r->objects, &pathbuf, normalized_objdir, &pos)) {strbuf_release (&pathbuf);return -1 ; }CALLOC_ARRAY (ent,1 ); - ent->path =xstrdup (pathbuf.buf); +/* pathbuf.buf is already in r->objects->odb_by_path */ + ent->path =strbuf_detach (&pathbuf,NULL );/* add the alternate entry */ *r->objects->odb_tail = ent; r->objects->odb_tail = &(ent->next); ent->next =NULL ; +assert (r->objects->odb_by_path); +kh_value (r->objects->odb_by_path, pos) = ent;/* recursively add alternates */ -read_info_alternates (r, pathbuf.buf, depth +1 ); +read_info_alternates (r, ent->path, depth +1 ); -strbuf_release (&pathbuf);return 0 ; }
object-store.h +17 -0
@@ -7,6 +7,8 @@#include "oid-array.h" #include "strbuf.h" #include "thread-utils.h" +#include "khash.h" +#include "dir.h" struct object_directory {struct object_directory *next;
@@ -30,6 +32,19 @@ struct object_directory {char *path; }; +static inline int odb_path_eq (const char *a,const char *b) +{ +return !fspathcmp (a, b); +} + +static inline int odb_path_hash (const char *str) +{ +return ignore_case ?strihash (str) :__ac_X31_hash_string (str); +} + +KHASH_INIT(odb_path_map, const char * /* key: odb_path */, + struct object_directory *, 1, odb_path_hash, odb_path_eq); +void prepare_alt_odb (struct repository *r);char *compute_alternate_path (const char *path,struct strbuf *err);typedef int alt_odb_fn (struct object_directory *,void *);
@@ -116,6 +131,8 @@ struct raw_object_store {*/ struct object_directory *odb;struct object_directory **odb_tail; +kh_odb_path_map_t *odb_by_path; +int loaded_alternates;/*
object.c +2 -0
@@ -511,6 +511,8 @@ static void free_object_directories(struct raw_object_store *o)free_object_directory (o->odb); o->odb = next; } +kh_destroy_odb_path_map (o->odb_by_path); + o->odb_by_path =NULL ; }void raw_object_store_clear (struct raw_object_store *o)
cover optimizations for many odb alternates
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
PATCH 1/5 speed up alt_odb_usable() with many alternates
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.
--- object-file.c | 33 ++++++++++++++++++++++----------- object-store.h | 17 +++++++++++++++++ object.c | 2 ++ 3 files changed, 41 insertions(+), 11 deletions(-)
object-file.c +22 -11
@@ -517,9 +517,9 @@ const char *loose_object_path(struct repository *r, struct strbuf *buf,*/ static int alt_odb_usable (struct raw_object_store *o,struct strbuf *path, -const char *normalized_objdir) +const char *normalized_objdir,khiter_t *pos) { -struct object_directory *odb; +int r;/* Detect cases where alternate disappeared */ if (!is_directory (path->buf)) {
@@ -533,14 +533,22 @@ static int alt_odb_usable(struct raw_object_store *o,* Prevent the common mistake of listing the same * thing twice, or object directory itself. */ -for (odb = o->odb; odb; odb = odb->next) { -if (!fspathcmp (path->buf, odb->path)) -return 0 ; +if (!o->odb_by_path) { +khiter_t p; + + 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); +if (r <0 )die_errno (_ ("kh_put_odb_path_map" )); +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" )); +/* r: 0 = exists, 1 = never used, 2 = deleted */ +return r ==0 ?0 :1 ; }/*
@@ -566,6 +574,7 @@ static int link_alt_odb_entry(struct repository *r, const char *entry, {struct object_directory *ent;struct strbuf pathbuf =STRBUF_INIT ; +khiter_t pos;if (!is_absolute_path (entry) && relative_base) {strbuf_realpath (&pathbuf, relative_base,1 );
@@ -587,23 +596,25 @@ static int link_alt_odb_entry(struct repository *r, const char *entry,while (pathbuf.len && pathbuf.buf[pathbuf.len -1 ] =='/' )strbuf_setlen (&pathbuf, pathbuf.len -1 ); -if (!alt_odb_usable (r->objects, &pathbuf, normalized_objdir)) { +if (!alt_odb_usable (r->objects, &pathbuf, normalized_objdir, &pos)) {strbuf_release (&pathbuf);return -1 ; }CALLOC_ARRAY (ent,1 ); - ent->path =xstrdup (pathbuf.buf); +/* pathbuf.buf is already in r->objects->odb_by_path */ + ent->path =strbuf_detach (&pathbuf,NULL );/* add the alternate entry */ *r->objects->odb_tail = ent; r->objects->odb_tail = &(ent->next); ent->next =NULL ; +assert (r->objects->odb_by_path); +kh_value (r->objects->odb_by_path, pos) = ent;/* recursively add alternates */ -read_info_alternates (r, pathbuf.buf, depth +1 ); +read_info_alternates (r, ent->path, depth +1 ); -strbuf_release (&pathbuf);return 0 ; }
object-store.h +17 -0
@@ -7,6 +7,8 @@#include "oid-array.h" #include "strbuf.h" #include "thread-utils.h" +#include "khash.h" +#include "dir.h" struct object_directory {struct object_directory *next;
@@ -30,6 +32,19 @@ struct object_directory {char *path; }; +static inline int odb_path_eq (const char *a,const char *b) +{ +return !fspathcmp (a, b); +} + +static inline int odb_path_hash (const char *str) +{ +return ignore_case ?strihash (str) :__ac_X31_hash_string (str); +} + +KHASH_INIT(odb_path_map, const char * /* key: odb_path */, + struct object_directory *, 1, odb_path_hash, odb_path_eq); +void prepare_alt_odb (struct repository *r);char *compute_alternate_path (const char *path,struct strbuf *err);typedef int alt_odb_fn (struct object_directory *,void *);
@@ -116,6 +131,8 @@ struct raw_object_store {*/ struct object_directory *odb;struct object_directory **odb_tail; +kh_odb_path_map_t *odb_by_path; +int loaded_alternates;/*
object.c +2 -0
@@ -511,6 +511,8 @@ static void free_object_directories(struct raw_object_store *o)free_object_directory (o->odb); o->odb = next; } +kh_destroy_odb_path_map (o->odb_by_path); + o->odb_by_path =NULL ; }void raw_object_store_clear (struct raw_object_store *o)
PATCH 2/5 avoid strlen via strbuf_addstr in link_alt_odb_entry
In reply to Eric WongWe 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 *".
--- object-file.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)
object-file.c +4 -4
@@ -569,18 +569,18 @@ static int alt_odb_usable(struct raw_object_store *o,static void read_info_alternates (struct repository *r,const char *relative_base,int depth); -static int link_alt_odb_entry (struct repository *r,const char *entry, +static int link_alt_odb_entry (struct repository *r,const struct strbuf *entry,const char *relative_base,int depth,const char *normalized_objdir) {struct object_directory *ent;struct strbuf pathbuf =STRBUF_INIT ;khiter_t pos; -if (!is_absolute_path (entry) && relative_base) { +if (!is_absolute_path (entry->buf) && relative_base) {strbuf_realpath (&pathbuf, relative_base,1 );strbuf_addch (&pathbuf,'/' ); } -strbuf_addstr (&pathbuf, entry); +strbuf_addbuf (&pathbuf, entry);if (strbuf_normalize_path (&pathbuf) <0 && relative_base) { error(_("unable to normalize alternate object path: %s"),
@@ -671,7 +671,7 @@ static void link_alt_odb_entries(struct repository *r, const char *alt, alt =parse_alt_odb_entry (alt, sep, &entry);if (!entry.len)continue ; -link_alt_odb_entry (r, entry.buf, +link_alt_odb_entry (r, &entry, relative_base, depth, objdirbuf.buf); }strbuf_release (&entry);
PATCH 3/5 make object_directory.loose_objects_subdir_seen a bitmap
In reply to Eric WongThere'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.
--- object-file.c | 10 +++++++--- object-store.h | 2 +- 2 files changed, 8 insertions(+), 4 deletions(-)
object-file.c +7 -3
@@ -2463,12 +2463,16 @@ struct oid_array *odb_loose_cache(struct object_directory *odb, {int subdir_nr = oid->hash[0 ];struct strbuf buf =STRBUF_INIT ; +size_t BM_SIZE =sizeof (odb->loose_objects_subdir_seen[0 ]) *CHAR_BIT ; +uint32_t *bitmap; +uint32_t bit =1 << (subdir_nr %BM_SIZE );if (subdir_nr <0 || - subdir_nr >=ARRAY_SIZE (odb->loose_objects_subdir_seen)) + subdir_nr >=ARRAY_SIZE (odb->loose_objects_subdir_seen) *BM_SIZE )BUG ("subdir_nr out of range" ); -if (odb->loose_objects_subdir_seen[subdir_nr]) + bitmap = &odb->loose_objects_subdir_seen[subdir_nr /BM_SIZE ]; +if (*bitmap & bit)return &odb->loose_objects_cache[subdir_nr];strbuf_addstr (&buf, odb->path);
@@ -2476,7 +2480,7 @@ struct oid_array *odb_loose_cache(struct object_directory *odb, append_loose_object,NULL ,NULL , &odb->loose_objects_cache[subdir_nr]); - odb->loose_objects_subdir_seen[subdir_nr] =1 ; + *bitmap |= bit;strbuf_release (&buf);return &odb->loose_objects_cache[subdir_nr]; }
object-store.h +1 -1
@@ -22,7 +22,7 @@ struct object_directory {* * Be sure to call odb_load_loose_cache() before using. */ -char loose_objects_subdir_seen[256 ]; +uint32_t loose_objects_subdir_seen[8 ];/* 256 bits */ struct oid_array loose_objects_cache[256 ];/*
Re: [PATCH 3/5] make object_directory.loose_objects_subdir_seen a bitmap
Am 27.06.21 um 04:47 schrieb Eric Wong:
Quoted 3 lines
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 11 lines
Signed-off-by Eric Wong <[email protected]>--- object-file.c | 10 +++++++--- object-store.h | 2 +- 2 files changed, 8 insertions(+), 4 deletions(-)object-file.c +0
-0
object-file.c struct oid_array *odb_loose_cache(struct object_directory *odb, · line 2466
Quoted 4 lines
object-file.c +1
-0@@ -2463,12 +2463,16 @@ struct oid_array *odb_loose_cache(struct object_directory *odb, {int subdir_nr = oid->hash[0 ];struct strbuf buf =STRBUF_INIT ; +size_t BM_SIZE =sizeof (odb->loose_objects_subdir_seen[0 ]) *CHAR_BIT ;
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.
object-file.c struct oid_array *odb_loose_cache(struct object_directory *odb, · line 2467
Quoted 1 line
object-file.c +1
-0+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.
object-file.c struct oid_array *odb_loose_cache(struct object_directory *odb, · line 2468
Quoted 1 line
object-file.c +1
-0+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);
object-file.c struct oid_array *odb_loose_cache(struct object_directory *odb, · line 2471
Quoted 4 lines
object-file.c +1
-1if (subdir_nr <0 || - subdir_nr >=ARRAY_SIZE (odb->loose_objects_subdir_seen)) + subdir_nr >=ARRAY_SIZE (odb->loose_objects_subdir_seen) *BM_SIZE )
bitsizeof(odb->loose_objects_subdir_seen) would be easier to read and understand, I think.
Quoted 22 lines
object-file.c +3
-2BUG ("subdir_nr out of range" ); -if (odb->loose_objects_subdir_seen[subdir_nr]) + bitmap = &odb->loose_objects_subdir_seen[subdir_nr /BM_SIZE ]; +if (*bitmap & bit)return &odb->loose_objects_cache[subdir_nr];strbuf_addstr (&buf, odb->path);@@ -2476,7 +2480,7 @@ struct oid_array *odb_loose_cache(struct object_directory *odb, append_loose_object,NULL ,NULL , &odb->loose_objects_cache[subdir_nr]); - odb->loose_objects_subdir_seen[subdir_nr] =1 ; + *bitmap |= bit;strbuf_release (&buf);return &odb->loose_objects_cache[subdir_nr]; }object-store.h +0
-0
object-store.h struct object_directory { · line 25
Quoted 5 lines
object-store.h +1
-1@@ -22,7 +22,7 @@ struct object_directory {* * Be sure to call odb_load_loose_cache() before using. */ -char loose_objects_subdir_seen[256 ]; +uint32_t loose_objects_subdir_seen[8 ];/* 256 bits */
Perhaps DIV_ROUND_UP(256, bitsizeof(uint32_t))? The comment explains
it nicely already, though.
object-store.h struct object_directory { · line 28
Quoted 4 lines
object-store.h +0
-0struct oid_array loose_objects_cache[256 ];/*
Summary: Good idea, the implementation looks correct, I stumbled over some of the names, bitsizeof() could be used.
René
Re: [PATCH 3/5] make object_directory.loose_objects_subdir_seen a bitmap
Quoted 6 lines · René Scharfe
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);
<snip> yeah, I missed bitsizeof :x
Quoted 11 lines
object-store.h struct object_directory { · line 25
Quoted 8 lines
object-store.h +1
-1@@ -22,7 +22,7 @@ struct object_directory {* * Be sure to call odb_load_loose_cache() before using. */ -char loose_objects_subdir_seen[256 ]; +uint32_t loose_objects_subdir_seen[8 ];/* 256 bits */ Perhaps
DIV_ROUND_UP(256, bitsizeof(uint32_t))? The comment explains
it nicely already, though.
I think I'll keep my original there... IMHO the macros obfuscate the meaning for those less familiar with our codebase (myself included :x)
Quoted 7 lines
object-store.h struct object_directory { · line 28
Quoted 4 lines
object-store.h +0
-0struct oid_array loose_objects_cache[256 ];/* Summary: Good idea, the implementation looks correct, I stumbled over some of the names,
bitsizeof()could be used.
Thanks for the review.
I'll squash up the following for v2 while awaiting feedback for the rest of the series:
object-file.c +7 -6
@@ -2463,16 +2463,17 @@ struct oidtree *odb_loose_cache(struct object_directory *odb, {int subdir_nr = oid->hash[0 ];struct strbuf buf =STRBUF_INIT ; -size_t BM_SIZE =sizeof (odb->loose_objects_subdir_seen[0 ]) *CHAR_BIT ; +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);uint32_t *bitmap; -uint32_t bit =1 << (subdir_nr %BM_SIZE );if (subdir_nr <0 || - subdir_nr >=ARRAY_SIZE (odb->loose_objects_subdir_seen) *BM_SIZE ) + subdir_nr >=bitsizeof (odb->loose_objects_subdir_seen))BUG ("subdir_nr out of range" ); - bitmap = &odb->loose_objects_subdir_seen[subdir_nr /BM_SIZE ]; -if (*bitmap & bit) + bitmap = &odb->loose_objects_subdir_seen[word_index]; +if (*bitmap & mask)return &odb->loose_objects_cache;strbuf_addstr (&buf, odb->path);
@@ -2480,7 +2481,7 @@ struct oidtree *odb_loose_cache(struct object_directory *odb, append_loose_object,NULL ,NULL , &odb->loose_objects_cache); - *bitmap |= bit; + *bitmap |= mask;strbuf_release (&buf);return &odb->loose_objects_cache; }
PATCH 4/5 oidcpy_with_padding: constify `src' arg
In reply to Eric WongAs with `oidcpy', the source struct will not be modified and this will allow an upcoming const-correct caller to use it.
--- hash.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
hash.h +1 -1
@@ -265,7 +265,7 @@ static inline void oidcpy(struct object_id *dst, const struct object_id *src)/* Like oidcpy() but zero-pads the unused bytes in dst's hash array. */ static inline void oidcpy_with_padding (struct object_id *dst, -struct object_id *src) +const struct object_id *src) {size_t hashsz;
PATCH 5/5 oidtree: a crit-bit tree for odb_loose_cache
In reply to Eric WongThis 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
--- 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
Makefile +3 -0
@@ -722,6 +722,7 @@ TEST_BUILTINS_OBJS += test-mergesort.o TEST_BUILTINS_OBJS += test-mktemp.o TEST_BUILTINS_OBJS += test-oid-array.o TEST_BUILTINS_OBJS += test-oidmap.o +TEST_BUILTINS_OBJS += test-oidtree.o TEST_BUILTINS_OBJS += test-online-cpus.o TEST_BUILTINS_OBJS += test-parse-options.o TEST_BUILTINS_OBJS += test-parse-pathspec-file.o
@@ -845,6 +846,7 @@ LIB_OBJS += branch.o LIB_OBJS += bulk-checkin.o LIB_OBJS += bundle.o LIB_OBJS += cache-tree.o +LIB_OBJS += cbtree.o LIB_OBJS += chdir-notify.o LIB_OBJS += checkout.o LIB_OBJS += chunk-format.o
@@ -940,6 +942,7 @@ LIB_OBJS += object.o LIB_OBJS += oid-array.o LIB_OBJS += oidmap.o LIB_OBJS += oidset.o +LIB_OBJS += oidtree.o LIB_OBJS += pack-bitmap-write.o LIB_OBJS += pack-bitmap.o LIB_OBJS += pack-check.o
alloc.c +6 -0
@@ -14,6 +14,7 @@#include "tree.h" #include "commit.h" #include "tag.h" +#include "oidtree.h" #include "alloc.h" #define BLOCKING 1024
@@ -123,6 +124,11 @@ void *alloc_commit_node(struct repository *r)return c; } +void *alloc_from_state (struct alloc_state *alloc_state,size_t n) +{ +return alloc_node (alloc_state, n); +} +static void report (const char *name,unsigned int count,size_t size) { fprintf(stderr, "%10s: %8u (%"PRIuMAX" kB)\n",
alloc.h +1 -0
@@ -13,6 +13,7 @@ void init_commit_node(struct commit *c);void *alloc_commit_node (struct repository *r);void *alloc_tag_node (struct repository *r);void *alloc_object_node (struct repository *r); +void *alloc_from_state (struct alloc_state *,size_t n);void alloc_report (struct repository *r);struct alloc_state *allocate_alloc_state (void );
cbtree.c new file +167 -0
167 lines not on this page · raw message
cbtree.h new file +56 -0
56 lines not on this page · raw message
object-file.c +7 -10
@@ -1175,7 +1175,7 @@ static int quick_has_loose(struct repository *r,prepare_alt_odb (r);for (odb = r->objects->odb; odb; odb = odb->next) { -if (oid_array_lookup (odb_loose_cache (odb, oid), oid) >=0 ) +if (oidtree_contains (odb_loose_cache (odb, oid), oid))return 1 ; }return 0 ;
@@ -2454,11 +2454,11 @@ int for_each_loose_object(each_loose_object_fn cb, void *data,static int append_loose_object (const struct object_id *oid,const char *path,void *data) { -oid_array_append (data, oid); +oidtree_insert (data, oid);return 0 ; } -struct oid_array *odb_loose_cache (struct object_directory *odb, +struct oidtree *odb_loose_cache (struct object_directory *odb,const struct object_id *oid) {int subdir_nr = oid->hash[0 ];
@@ -2473,24 +2473,21 @@ struct oid_array *odb_loose_cache(struct object_directory *odb, bitmap = &odb->loose_objects_subdir_seen[subdir_nr /BM_SIZE ];if (*bitmap & bit) -return &odb->loose_objects_cache[subdir_nr]; +return &odb->loose_objects_cache;strbuf_addstr (&buf, odb->path);for_each_file_in_obj_subdir (subdir_nr, &buf, append_loose_object,NULL ,NULL , - &odb->loose_objects_cache[subdir_nr]); + &odb->loose_objects_cache); *bitmap |= bit;strbuf_release (&buf); -return &odb->loose_objects_cache[subdir_nr]; +return &odb->loose_objects_cache; }void odb_clear_loose_cache (struct object_directory *odb) { -int i; - -for (i =0 ; i <ARRAY_SIZE (odb->loose_objects_cache); i++) -oid_array_clear (&odb->loose_objects_cache[i]); +oidtree_destroy (&odb->loose_objects_cache);memset (&odb->loose_objects_subdir_seen,0 ,sizeof (odb->loose_objects_subdir_seen)); }
object-name.c +11 -17
@@ -87,27 +87,21 @@ static void update_candidates(struct disambiguate_state *ds, const struct objectstatic int match_hash (unsigned ,const unsigned char *,const unsigned char *); +static enum cb_next match_prefix (const struct object_id *oid,void *arg) +{ +struct disambiguate_state *ds = arg; +/* no need to call match_hash, oidtree_each did prefix match */ +update_candidates (ds, oid); +return ds->ambiguous ?CB_BREAK :CB_CONTINUE ; +} +static void find_short_object_filename (struct disambiguate_state *ds) {struct object_directory *odb; -for (odb = ds->repo->objects->odb; odb && !ds->ambiguous; odb = odb->next) { -int pos; -struct oid_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) { -const struct object_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); }static int match_hash (unsigned len,const unsigned char *a,const unsigned char *b)
object-store.h +3 -2
@@ -9,6 +9,7 @@#include "thread-utils.h" #include "khash.h" #include "dir.h" +#include "oidtree.h" struct object_directory {struct object_directory *next;
@@ -23,7 +24,7 @@ struct object_directory {* Be sure to call odb_load_loose_cache() before using. */ uint32_t loose_objects_subdir_seen[8 ];/* 256 bits */ -struct oid_array loose_objects_cache[256 ]; +struct oidtree loose_objects_cache;/* * Path to the alternative object store. If this is a relative path,
@@ -69,7 +70,7 @@ void add_to_alternates_memory(const char *dir);* Populate and return the loose object cache array corresponding to the * given object ID. */ -struct oid_array *odb_loose_cache (struct object_directory *odb, +struct oidtree *odb_loose_cache (struct object_directory *odb,const struct object_id *oid);/* Empty the loose object cache for the specified object directory. */
oidtree.c new file +94 -0
94 lines not on this page · raw message
oidtree.h new file +29 -0
@@ -0,0 +1,29 @@ +#ifndef OIDTREE_H +#define OIDTREE_H + +#include "cbtree.h" +#include "hash.h" + +struct alloc_state ; +struct oidtree { +struct cb_tree t; +struct alloc_state *mempool; +}; + +#define OIDTREE_INIT { .t = CBTREE_INIT, .mempool = NULL } + +static inline void oidtree_init (struct oidtree *ot) +{ +cb_init (&ot->t); + ot->mempool =NULL ; +} + +void oidtree_destroy (struct oidtree *); +void oidtree_insert (struct oidtree *,const struct object_id *); +int oidtree_contains (struct oidtree *,const struct object_id *); + +typedef enum cb_next (*oidtree_iter )(const struct object_id *,void *arg); +void oidtree_each (struct oidtree *,const struct object_id *, +size_t oidhexlen,oidtree_iter ,void *arg); + +#endif /* OIDTREE_H */
t/helper/test-oidtree.c new file +45 -0
45 lines not on this page · raw message
t/helper/test-tool.c +1 -0
@@ -43,6 +43,7 @@ static struct test_cmd cmds[] = { { "mktemp", cmd__mktemp }, { "oid-array", cmd__oid_array }, { "oidmap", cmd__oidmap }, + { "oidtree", cmd__oidtree }, { "online-cpus", cmd__online_cpus }, { "parse-options", cmd__parse_options }, { "parse-pathspec-file", cmd__parse_pathspec_file },
t/helper/test-tool.h +1 -0
@@ -32,6 +32,7 @@ int cmd__match_trees(int argc, const char **argv);int cmd__mergesort (int argc,const char **argv);int cmd__mktemp (int argc,const char **argv);int cmd__oidmap (int argc,const char **argv); +int cmd__oidtree (int argc,const char **argv);int cmd__online_cpus (int argc,const char **argv);int cmd__parse_options (int argc,const char **argv);int cmd__parse_pathspec_file (int argc,const char ** argv);
t/t0069-oidtree.sh new file +52 -0
52 lines not on this page · raw message
Re: [PATCH 5/5] oidtree: a crit-bit tree for odb_loose_cache
Quoted 8 lines · 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 theoidtree' wrapper on top of it. The latter provides allocation usingalloc_stateas a memory pool to improve locality and reduce free(3) overhead.
This seems to break CI test, with "fatal: not a hexadecimal oid", perhaps because there is hardcoded 40 here?
Quoted 23 lines
index 0000000000..bb4229210c
t/t0069-oidtree.sh new file +19
-0@@ -0,0 +1,52 @@ +#!/bin/sh + +test_description='basic tests for the oidtree implementation' +. ./test-lib.sh + +echoid () { + prefix="${1:+$1 }" + shift + while test $# -gt 0 + do + echo "$1" + shift + done | awk -v prefix="$prefix" '{ + printf("%s%s", prefix, $0); + need = 40 - length($0); + for (i = 0; i < need; i++) + printf("0"); + printf "\n"; + }'
Re: [PATCH 5/5] oidtree: a crit-bit tree for odb_loose_cache
Quoted 6 lines · Junio C Hamano
Quoted 4 lines · 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).
Quoted 7 lines
Quoted 4 lines
This is implemented in two parts: a generic, allocation-free
cbtree' and theoidtree' wrapper on top of it. The latter provides allocation usingalloc_stateas a memory pool to improve locality and reduce free(3) overhead.This seems to break CI test, with "fatal: not a hexadecimal oid", perhaps because there is hardcoded 40 here?
Yes, I think this needs to be squashed in:
--------8<------
Subject: [PATCH] t0069: make oidtree test hash-agnostic
Tested with both:
make -C t t0069-oidtree.sh GIT_TEST_DEFAULT_HASH=sha1 make -C t t0069-oidtree.sh GIT_TEST_DEFAULT_HASH=sha256
--- t/helper/test-oidtree.c | 14 ++++++++------ t/t0069-oidtree.sh | 4 ++-- 2 files changed, 10 insertions(+), 8 deletions(-)
t/helper/test-oidtree.c +8 -6
@@ -13,6 +13,7 @@ int cmd__oidtree(int argc, const char **argv)struct oidtree ot =OIDTREE_INIT ;struct strbuf line =STRBUF_INIT ;int nongit_ok; +int algo =GIT_HASH_UNKNOWN ;setup_git_directory_gently (&nongit_ok);
@@ -21,20 +22,21 @@ int cmd__oidtree(int argc, const char **argv)struct object_id oid;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); }else if (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)); }else if (skip_prefix (line.buf,"each " , &arg)) { -char buf[GIT_SHA1_HEXSZ +1 ] = {'0' }; +char buf[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 ); }else if (!strcmp (line.buf,"destroy" ))oidtree_destroy (&ot);
t/t0069-oidtree.sh +2 -2
@@ -10,9 +10,9 @@ echoid () { do echo "$1" shift - done | awk -v prefix="$prefix" '{ + done | awk -v prefix="$prefix" -v ZERO_OID=$ZERO_OID '{ printf("%s%s", prefix, $0); - need = 40 - length($0); + need = length(ZERO_OID) - length($0); for (i = 0; i < need; i++) printf("0"); printf "\n";
v2 cover optimizations for many alternates
In reply to Eric Wongv2 has better naming for 3/5, fix test for sha256 in 5/5 Thanks to René and Junio for feedback so far.
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 | 69 ++++++++++------- object-name.c | 28 +++---- object-store.h | 24 +++++- object.c | 2 + 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 +++++++++++++ 16 files changed, 533 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
Interdiff against v1:
object-file.c +7 -6
@@ -2463,16 +2463,17 @@ struct oidtree *odb_loose_cache(struct object_directory *odb, {int subdir_nr = oid->hash[0 ];struct strbuf buf =STRBUF_INIT ; -size_t BM_SIZE =sizeof (odb->loose_objects_subdir_seen[0 ]) *CHAR_BIT ; +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);uint32_t *bitmap; -uint32_t bit =1 << (subdir_nr %BM_SIZE );if (subdir_nr <0 || - subdir_nr >=ARRAY_SIZE (odb->loose_objects_subdir_seen) *BM_SIZE ) + subdir_nr >=bitsizeof (odb->loose_objects_subdir_seen))BUG ("subdir_nr out of range" ); - bitmap = &odb->loose_objects_subdir_seen[subdir_nr /BM_SIZE ]; -if (*bitmap & bit) + bitmap = &odb->loose_objects_subdir_seen[word_index]; +if (*bitmap & mask)return &odb->loose_objects_cache;strbuf_addstr (&buf, odb->path);
@@ -2480,7 +2481,7 @@ struct oidtree *odb_loose_cache(struct object_directory *odb, append_loose_object,NULL ,NULL , &odb->loose_objects_cache); - *bitmap |= bit; + *bitmap |= mask;strbuf_release (&buf);return &odb->loose_objects_cache; }
t/helper/test-oidtree.c +8 -6
@@ -13,6 +13,7 @@ int cmd__oidtree(int argc, const char **argv)struct oidtree ot =OIDTREE_INIT ;struct strbuf line =STRBUF_INIT ;int nongit_ok; +int algo =GIT_HASH_UNKNOWN ;setup_git_directory_gently (&nongit_ok);
@@ -21,20 +22,21 @@ int cmd__oidtree(int argc, const char **argv)struct object_id oid;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); }else if (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)); }else if (skip_prefix (line.buf,"each " , &arg)) { -char buf[GIT_SHA1_HEXSZ +1 ] = {'0' }; +char buf[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 ); }else if (!strcmp (line.buf,"destroy" ))oidtree_destroy (&ot);
t/t0069-oidtree.sh +2 -2
@@ -10,9 +10,9 @@ echoid () { do echo "$1" shift - done | awk -v prefix="$prefix" '{ + done | awk -v prefix="$prefix" -v ZERO_OID=$ZERO_OID '{ printf("%s%s", prefix, $0); - need = 40 - length($0); + need = length(ZERO_OID) - length($0); for (i = 0; i < need; i++) printf("0"); printf "\n";
v3 cover optimizations for many alternates
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:
alloc.c +0 -6
@@ -14,7 +14,6 @@#include "tree.h" #include "commit.h" #include "tag.h" -#include "oidtree.h" #include "alloc.h" #define BLOCKING 1024
@@ -124,11 +123,6 @@ void *alloc_commit_node(struct repository *r)return c; } -void *alloc_from_state (struct alloc_state *alloc_state,size_t n) -{ -return alloc_node (alloc_state, n); -} -static void report (const char *name,unsigned int count,size_t size) { fprintf(stderr, "%10s: %8u (%"PRIuMAX" kB)\n",
alloc.h +0 -1
@@ -13,7 +13,6 @@ void init_commit_node(struct commit *c);void *alloc_commit_node (struct repository *r);void *alloc_tag_node (struct repository *r);void *alloc_object_node (struct repository *r); -void *alloc_from_state (struct alloc_state *,size_t n);void alloc_report (struct repository *r);struct alloc_state *allocate_alloc_state (void );
dir.c +10 -0
@@ -84,11 +84,21 @@ int fspathcmp(const char *a, const char *b)return ignore_case ?strcasecmp (a, b) :strcmp (a, b); } +int fspatheq (const char *a,const char *b) +{ +return !fspathcmp (a, b); +} +int fspathncmp (const char *a,const char *b,size_t count) {return ignore_case ?strncasecmp (a, b, count) :strncmp (a, b, count); } +unsigned int fspathhash (const char *str) +{ +return ignore_case ?strihash (str) :strhash (str); +} +int git_fnmatch (const struct pathspec_item *item,const char *pattern,const char *string,int prefix)
dir.h +2 -0
@@ -489,7 +489,9 @@ int remove_dir_recursively(struct strbuf *path, int flag);int remove_path (const char *path);int fspathcmp (const char *a,const char *b); +int fspatheq (const char *a,const char *b);int fspathncmp (const char *a,const char *b,size_t count); +unsigned int fspathhash (const char *str);/* * The prefix part of pattern must not contains wildcards.
object-file.c +10 -8
@@ -539,14 +539,12 @@ static int alt_odb_usable(struct raw_object_store *o, 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); -if (r <0 )die_errno (_ ("kh_put_odb_path_map" ));assert (r ==1 );/* never used */ kh_value (o->odb_by_path, p) = o->odb; } -if (!fspathcmp (path->buf, normalized_objdir)) +if (fspatheq (path->buf, normalized_objdir))return 0 ; *pos =kh_put_odb_path_map (o->odb_by_path, path->buf, &r); -if (r <0 )die_errno (_ ("kh_put_odb_path_map" ));/* r: 0 = exists, 1 = never used, 2 = deleted */ return r ==0 ?0 :1 ; }
@@ -2474,21 +2472,25 @@ struct oidtree *odb_loose_cache(struct object_directory *odb, bitmap = &odb->loose_objects_subdir_seen[word_index];if (*bitmap & mask) -return &odb->loose_objects_cache; - +return odb->loose_objects_cache; +if (!odb->loose_objects_cache) { +ALLOC_ARRAY (odb->loose_objects_cache,1 ); +oidtree_init (odb->loose_objects_cache); + }strbuf_addstr (&buf, odb->path);for_each_file_in_obj_subdir (subdir_nr, &buf, append_loose_object,NULL ,NULL , - &odb->loose_objects_cache); + odb->loose_objects_cache); *bitmap |= mask;strbuf_release (&buf); -return &odb->loose_objects_cache; +return odb->loose_objects_cache; }void odb_clear_loose_cache (struct object_directory *odb) { -oidtree_destroy (&odb->loose_objects_cache); +oidtree_clear (odb->loose_objects_cache); +FREE_AND_NULL (odb->loose_objects_cache);memset (&odb->loose_objects_subdir_seen,0 ,sizeof (odb->loose_objects_subdir_seen)); }
object-store.h +2 -12
@@ -24,7 +24,7 @@ struct object_directory {* Be sure to call odb_load_loose_cache() before using. */ uint32_t loose_objects_subdir_seen[8 ];/* 256 bits */ -struct oidtree loose_objects_cache; +struct oidtree *loose_objects_cache;/* * Path to the alternative object store. If this is a relative path,
@@ -33,18 +33,8 @@ struct object_directory {char *path; }; -static inline int odb_path_eq (const char *a,const char *b) -{ -return !fspathcmp (a, b); -} - -static inline int odb_path_hash (const char *str) -{ -return ignore_case ?strihash (str) :__ac_X31_hash_string (str); -} - KHASH_INIT(odb_path_map, const char * /* key: odb_path */, - struct object_directory *, 1, odb_path_hash, odb_path_eq); + struct object_directory *, 1, fspathhash, fspatheq);void prepare_alt_odb (struct repository *r);char *compute_alternate_path (const char *path,struct strbuf *err);
oidtree.c +30 -20
93 lines not on this page · raw message
oidtree.h +7 -14
@@ -3,27 +3,20 @@#include "cbtree.h" #include "hash.h" +#include "mem-pool.h" -struct alloc_state ;struct oidtree { -struct cb_tree t; -struct alloc_state *mempool; +struct cb_tree tree; +struct mem_pool mem_pool; }; -#define OIDTREE_INIT { .t = CBTREE_INIT, .mempool = NULL } - -static inline void oidtree_init (struct oidtree *ot) -{ -cb_init (&ot->t); - ot->mempool =NULL ; -} - -void oidtree_destroy (struct oidtree *); +void oidtree_init (struct oidtree *); +void oidtree_clear (struct oidtree *);void oidtree_insert (struct oidtree *,const struct object_id *);int oidtree_contains (struct oidtree *,const struct object_id *); -typedef enum cb_next (*oidtree_iter )(const struct object_id *,void *arg); +typedef enum cb_next (*oidtree_iter )(const struct object_id *,void *data);void oidtree_each (struct oidtree *,const struct object_id *, -size_t oidhexlen,oidtree_iter ,void *arg); +size_t oidhexsz,oidtree_iter ,void *data);#endif /* OIDTREE_H */
t/helper/test-oidtree.c +7 -5
@@ -10,11 +10,12 @@ static enum cb_next print_oid(const struct object_id *oid, void *data)int cmd__oidtree (int argc,const char **argv) { -struct oidtree ot =OIDTREE_INIT ; +struct oidtree ot;struct strbuf line =STRBUF_INIT ;int nongit_ok;int algo =GIT_HASH_UNKNOWN ; +oidtree_init (&ot);setup_git_directory_gently (&nongit_ok);while (strbuf_getline (&line, stdin) !=EOF ) {
@@ -34,14 +35,15 @@ int cmd__oidtree(int argc, const char **argv)char buf[GIT_MAX_HEXSZ +1 ] = {'0' };memset (&oid,0 ,sizeof (oid));memcpy (buf, arg,strlen (arg)); - buf[hash_algos[algo].hexsz] =0 ; + buf[hash_algos[algo].hexsz] ='\0' ;get_oid_hex_any (buf, &oid); oid.algo = algo;oidtree_each (&ot, &oid,strlen (arg), print_oid,NULL ); - }else if (!strcmp (line.buf,"destroy" )) -oidtree_destroy (&ot); -else + }else if (!strcmp (line.buf,"clear" )) { +oidtree_clear (&ot); + }else {die ("unknown command: %s" , line.buf); + } }return 0 ; }
t/t0069-oidtree.sh +15 -18
@@ -3,35 +3,32 @@ test_description='basic tests for the oidtree implementation' . ./test-lib.sh +maxhexsz=$(test_oid hexsz) echoid () { prefix="${1:+$1 }" shift while test $# -gt 0 do - echo "$1" + shortoid="$1" shift - done | awk -v prefix="$prefix" -v ZERO_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 { echoid insert 444 1 2 3 4 5 a b c d e && echoid contains 44 441 440 444 4440 4444 - echo destroy + echo clear } | test-tool oidtree >actual && test_cmp expect actual '
@@ -44,7 +41,7 @@ test_expect_success 'oidtree each' ' echo each 3211 echo each 3210 echo each 32100 - echo destroy + echo clear } | test-tool oidtree >actual && test_cmp expect actual '
PATCH v3 1/5 speed up alt_odb_usable() with many alternates
In reply to Eric WongWith 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.
--- dir.c | 10 ++++++++++ dir.h | 2 ++ object-file.c | 33 +++++++++++++++++++++------------ object-store.h | 7 +++++++ object.c | 2 ++ 5 files changed, 42 insertions(+), 12 deletions(-)
dir.c +10 -0
@@ -84,11 +84,21 @@ int fspathcmp(const char *a, const char *b)return ignore_case ?strcasecmp (a, b) :strcmp (a, b); } +int fspatheq (const char *a,const char *b) +{ +return !fspathcmp (a, b); +} +int fspathncmp (const char *a,const char *b,size_t count) {return ignore_case ?strncasecmp (a, b, count) :strncmp (a, b, count); } +unsigned int fspathhash (const char *str) +{ +return ignore_case ?strihash (str) :strhash (str); +} +int git_fnmatch (const struct pathspec_item *item,const char *pattern,const char *string,int prefix)
dir.h +2 -0
@@ -489,7 +489,9 @@ int remove_dir_recursively(struct strbuf *path, int flag);int remove_path (const char *path);int fspathcmp (const char *a,const char *b); +int fspatheq (const char *a,const char *b);int fspathncmp (const char *a,const char *b,size_t count); +unsigned int fspathhash (const char *str);/* * The prefix part of pattern must not contains wildcards.
object-file.c +21 -12
@@ -517,9 +517,9 @@ const char *loose_object_path(struct repository *r, struct strbuf *buf,*/ static int alt_odb_usable (struct raw_object_store *o,struct strbuf *path, -const char *normalized_objdir) +const char *normalized_objdir,khiter_t *pos) { -struct object_directory *odb; +int r;/* Detect cases where alternate disappeared */ if (!is_directory (path->buf)) {
@@ -533,14 +533,20 @@ static int alt_odb_usable(struct raw_object_store *o,* Prevent the common mistake of listing the same * thing twice, or object directory itself. */ -for (odb = o->odb; odb; odb = odb->next) { -if (!fspathcmp (path->buf, odb->path)) -return 0 ; +if (!o->odb_by_path) { +khiter_t p; + + 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); +assert (r ==1 );/* never used */ +kh_value (o->odb_by_path, p) = o->odb; } -if (!fspathcmp (path->buf, normalized_objdir)) +if (fspatheq (path->buf, normalized_objdir))return 0 ; - -return 1 ; + *pos =kh_put_odb_path_map (o->odb_by_path, path->buf, &r); +/* r: 0 = exists, 1 = never used, 2 = deleted */ +return r ==0 ?0 :1 ; }/*
@@ -566,6 +572,7 @@ static int link_alt_odb_entry(struct repository *r, const char *entry, {struct object_directory *ent;struct strbuf pathbuf =STRBUF_INIT ; +khiter_t pos;if (!is_absolute_path (entry) && relative_base) {strbuf_realpath (&pathbuf, relative_base,1 );
@@ -587,23 +594,25 @@ static int link_alt_odb_entry(struct repository *r, const char *entry,while (pathbuf.len && pathbuf.buf[pathbuf.len -1 ] =='/' )strbuf_setlen (&pathbuf, pathbuf.len -1 ); -if (!alt_odb_usable (r->objects, &pathbuf, normalized_objdir)) { +if (!alt_odb_usable (r->objects, &pathbuf, normalized_objdir, &pos)) {strbuf_release (&pathbuf);return -1 ; }CALLOC_ARRAY (ent,1 ); - ent->path =xstrdup (pathbuf.buf); +/* pathbuf.buf is already in r->objects->odb_by_path */ + ent->path =strbuf_detach (&pathbuf,NULL );/* add the alternate entry */ *r->objects->odb_tail = ent; r->objects->odb_tail = &(ent->next); ent->next =NULL ; +assert (r->objects->odb_by_path); +kh_value (r->objects->odb_by_path, pos) = ent;/* recursively add alternates */ -read_info_alternates (r, pathbuf.buf, depth +1 ); +read_info_alternates (r, ent->path, depth +1 ); -strbuf_release (&pathbuf);return 0 ; }
object-store.h +7 -0
@@ -7,6 +7,8 @@#include "oid-array.h" #include "strbuf.h" #include "thread-utils.h" +#include "khash.h" +#include "dir.h" struct object_directory {struct object_directory *next;
@@ -30,6 +32,9 @@ struct object_directory {char *path; }; +KHASH_INIT(odb_path_map, const char * /* key: odb_path */, + struct object_directory *, 1, fspathhash, fspatheq); +void prepare_alt_odb (struct repository *r);char *compute_alternate_path (const char *path,struct strbuf *err);typedef int alt_odb_fn (struct object_directory *,void *);
@@ -116,6 +121,8 @@ struct raw_object_store {*/ struct object_directory *odb;struct object_directory **odb_tail; +kh_odb_path_map_t *odb_by_path; +int loaded_alternates;/*
object.c +2 -0
@@ -511,6 +511,8 @@ static void free_object_directories(struct raw_object_store *o)free_object_directory (o->odb); o->odb = next; } +kh_destroy_odb_path_map (o->odb_by_path); + o->odb_by_path =NULL ; }void raw_object_store_clear (struct raw_object_store *o)
Quoted 14 lines · Eric Wong
With many alternates, the duplicate check in
alt_odb_usable()wastes many cycles doing repeatedfspathcmp()on every existing alternate. Use a khash to speed up lookups byodb->path.Since the kh_put_* API uses the supplied key without duplicating it, we also take advantage of it to replace both
xstrdup()andstrbuf_release()inlink_alt_odb_entry()withstrbuf_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.
Quoted 7 lines
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.
The last one does not belong to the commit log message, as "git log" readers do not care about and will not have access to v2 and earlier.
Quoted 7 lines · Junio C Hamano
Quoted 3 lines · Eric Wong
v3: Introduce and use fspatheq and fspathhash functions;
avoid unnecessary checks for allocation failures already handled by our own *alloc wrappers.The last one does not belong to the commit log message, as "git log" readers do not care about and will not have access to v2 and earlier.
Oops :x Are you going to remove that on your end or do you want a resend? Looking at "git log", it looks like I've done it a bit over the years :x
Quoted 11 lines · Eric Wong
Quoted 7 lines · Junio C Hamano
Quoted 3 lines · Eric Wong
v3: Introduce and use fspatheq and fspathhash functions;
avoid unnecessary checks for allocation failures already handled by our own *alloc wrappers.The last one does not belong to the commit log message, as "git log" readers do not care about and will not have access to v2 and earlier.
Oops :x Are you going to remove that on your end or do you want a resend? Looking at "git log", it looks like I've done it a bit over the years :x
OK. I guess there are a few more patches in the series with the same issue. "rebase -i" is our friend ;-)
PATCH v3 2/5 avoid strlen via strbuf_addstr in link_alt_odb_entry
In reply to Eric WongWe 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 *".
--- object-file.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)
object-file.c +4 -4
@@ -567,18 +567,18 @@ static int alt_odb_usable(struct raw_object_store *o,static void read_info_alternates (struct repository *r,const char *relative_base,int depth); -static int link_alt_odb_entry (struct repository *r,const char *entry, +static int link_alt_odb_entry (struct repository *r,const struct strbuf *entry,const char *relative_base,int depth,const char *normalized_objdir) {struct object_directory *ent;struct strbuf pathbuf =STRBUF_INIT ;khiter_t pos; -if (!is_absolute_path (entry) && relative_base) { +if (!is_absolute_path (entry->buf) && relative_base) {strbuf_realpath (&pathbuf, relative_base,1 );strbuf_addch (&pathbuf,'/' ); } -strbuf_addstr (&pathbuf, entry); +strbuf_addbuf (&pathbuf, entry);if (strbuf_normalize_path (&pathbuf) <0 && relative_base) { error(_("unable to normalize alternate object path: %s"),
@@ -669,7 +669,7 @@ static void link_alt_odb_entries(struct repository *r, const char *alt, alt =parse_alt_odb_entry (alt, sep, &entry);if (!entry.len)continue ; -link_alt_odb_entry (r, entry.buf, +link_alt_odb_entry (r, &entry, relative_base, depth, objdirbuf.buf); }strbuf_release (&entry);
Re: [PATCH v3 2/5] avoid strlen via strbuf_addstr in link_alt_odb_entry
Quoted 3 lines · Eric Wong
We can save a few milliseconds (across 100K odbs) by using
strbuf_addbuf()instead ofstrbuf_addstr()by passing `entry' as a strbuf pointer rather than a "const char *".
OK; trivially corect ;-)
Quoted 41 lines
Signed-off-by Eric Wong <[email protected]>--- object-file.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)object-file.c +4
-4@@ -567,18 +567,18 @@ static int alt_odb_usable(struct raw_object_store *o,static void read_info_alternates (struct repository *r,const char *relative_base,int depth); -static int link_alt_odb_entry (struct repository *r,const char *entry, +static int link_alt_odb_entry (struct repository *r,const struct strbuf *entry,const char *relative_base,int depth,const char *normalized_objdir) {struct object_directory *ent;struct strbuf pathbuf =STRBUF_INIT ;khiter_t pos; -if (!is_absolute_path (entry) && relative_base) { +if (!is_absolute_path (entry->buf) && relative_base) {strbuf_realpath (&pathbuf, relative_base,1 );strbuf_addch (&pathbuf,'/' ); } -strbuf_addstr (&pathbuf, entry); +strbuf_addbuf (&pathbuf, entry);if (strbuf_normalize_path (&pathbuf) <0 && relative_base) { error(_("unable to normalize alternate object path: %s"),@@ -669,7 +669,7 @@ static void link_alt_odb_entries(struct repository *r, const char *alt, alt =parse_alt_odb_entry (alt, sep, &entry);if (!entry.len)continue ; -link_alt_odb_entry (r, entry.buf, +link_alt_odb_entry (r, &entry, relative_base, depth, objdirbuf.buf); }strbuf_release (&entry);
PATCH v3 3/5 make object_directory.loose_objects_subdir_seen a bitmap
In reply to Eric WongThere'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
--- object-file.c | 11 ++++++++--- object-store.h | 2 +- 2 files changed, 9 insertions(+), 4 deletions(-)
object-file.c +8 -3
@@ -2461,12 +2461,17 @@ struct oid_array *odb_loose_cache(struct object_directory *odb, {int subdir_nr = oid->hash[0 ];struct strbuf buf =STRBUF_INIT ; +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); +uint32_t *bitmap;if (subdir_nr <0 || - subdir_nr >=ARRAY_SIZE (odb->loose_objects_subdir_seen)) + subdir_nr >=bitsizeof (odb->loose_objects_subdir_seen))BUG ("subdir_nr out of range" ); -if (odb->loose_objects_subdir_seen[subdir_nr]) + bitmap = &odb->loose_objects_subdir_seen[word_index]; +if (*bitmap & mask)return &odb->loose_objects_cache[subdir_nr];strbuf_addstr (&buf, odb->path);
@@ -2474,7 +2479,7 @@ struct oid_array *odb_loose_cache(struct object_directory *odb, append_loose_object,NULL ,NULL , &odb->loose_objects_cache[subdir_nr]); - odb->loose_objects_subdir_seen[subdir_nr] =1 ; + *bitmap |= mask;strbuf_release (&buf);return &odb->loose_objects_cache[subdir_nr]; }
object-store.h +1 -1
@@ -22,7 +22,7 @@ struct object_directory {* * Be sure to call odb_load_loose_cache() before using. */ -char loose_objects_subdir_seen[256 ]; +uint32_t loose_objects_subdir_seen[8 ];/* 256 bits */ struct oid_array loose_objects_cache[256 ];/*
PATCH v3 4/5 oidcpy_with_padding: constify `src' arg
In reply to Eric WongAs with `oidcpy', the source struct will not be modified and this will allow an upcoming const-correct caller to use it.
--- hash.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
hash.h +1 -1
@@ -265,7 +265,7 @@ static inline void oidcpy(struct object_id *dst, const struct object_id *src)/* Like oidcpy() but zero-pads the unused bytes in dst's hash array. */ static inline void oidcpy_with_padding (struct object_id *dst, -struct object_id *src) +const struct object_id *src) {size_t hashsz;
PATCH v3 5/5 oidtree: a crit-bit tree for odb_loose_cache
In reply to Eric WongThis 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
--- 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
Makefile +3 -0
@@ -722,6 +722,7 @@ TEST_BUILTINS_OBJS += test-mergesort.o TEST_BUILTINS_OBJS += test-mktemp.o TEST_BUILTINS_OBJS += test-oid-array.o TEST_BUILTINS_OBJS += test-oidmap.o +TEST_BUILTINS_OBJS += test-oidtree.o TEST_BUILTINS_OBJS += test-online-cpus.o TEST_BUILTINS_OBJS += test-parse-options.o TEST_BUILTINS_OBJS += test-parse-pathspec-file.o
@@ -845,6 +846,7 @@ LIB_OBJS += branch.o LIB_OBJS += bulk-checkin.o LIB_OBJS += bundle.o LIB_OBJS += cache-tree.o +LIB_OBJS += cbtree.o LIB_OBJS += chdir-notify.o LIB_OBJS += checkout.o LIB_OBJS += chunk-format.o
@@ -940,6 +942,7 @@ LIB_OBJS += object.o LIB_OBJS += oid-array.o LIB_OBJS += oidmap.o LIB_OBJS += oidset.o +LIB_OBJS += oidtree.o LIB_OBJS += pack-bitmap-write.o LIB_OBJS += pack-bitmap.o LIB_OBJS += pack-check.o
cbtree.c new file +167 -0
167 lines not on this page · raw message
cbtree.h new file +56 -0
56 lines not on this page · raw message
object-file.c +12 -11
@@ -1173,7 +1173,7 @@ static int quick_has_loose(struct repository *r,prepare_alt_odb (r);for (odb = r->objects->odb; odb; odb = odb->next) { -if (oid_array_lookup (odb_loose_cache (odb, oid), oid) >=0 ) +if (oidtree_contains (odb_loose_cache (odb, oid), oid))return 1 ; }return 0 ;
@@ -2452,11 +2452,11 @@ int for_each_loose_object(each_loose_object_fn cb, void *data,static int append_loose_object (const struct object_id *oid,const char *path,void *data) { -oid_array_append (data, oid); +oidtree_insert (data, oid);return 0 ; } -struct oid_array *odb_loose_cache (struct object_directory *odb, +struct oidtree *odb_loose_cache (struct object_directory *odb,const struct object_id *oid) {int subdir_nr = oid->hash[0 ];
@@ -2472,24 +2472,25 @@ struct oid_array *odb_loose_cache(struct object_directory *odb, bitmap = &odb->loose_objects_subdir_seen[word_index];if (*bitmap & mask) -return &odb->loose_objects_cache[subdir_nr]; - +return odb->loose_objects_cache; +if (!odb->loose_objects_cache) { +ALLOC_ARRAY (odb->loose_objects_cache,1 ); +oidtree_init (odb->loose_objects_cache); + }strbuf_addstr (&buf, odb->path);for_each_file_in_obj_subdir (subdir_nr, &buf, append_loose_object,NULL ,NULL , - &odb->loose_objects_cache[subdir_nr]); + odb->loose_objects_cache); *bitmap |= mask;strbuf_release (&buf); -return &odb->loose_objects_cache[subdir_nr]; +return odb->loose_objects_cache; }void odb_clear_loose_cache (struct object_directory *odb) { -int i; - -for (i =0 ; i <ARRAY_SIZE (odb->loose_objects_cache); i++) -oid_array_clear (&odb->loose_objects_cache[i]); +oidtree_clear (odb->loose_objects_cache); +FREE_AND_NULL (odb->loose_objects_cache);memset (&odb->loose_objects_subdir_seen,0 ,sizeof (odb->loose_objects_subdir_seen)); }
object-name.c +11 -17
@@ -87,27 +87,21 @@ static void update_candidates(struct disambiguate_state *ds, const struct objectstatic int match_hash (unsigned ,const unsigned char *,const unsigned char *); +static enum cb_next match_prefix (const struct object_id *oid,void *arg) +{ +struct disambiguate_state *ds = arg; +/* no need to call match_hash, oidtree_each did prefix match */ +update_candidates (ds, oid); +return ds->ambiguous ?CB_BREAK :CB_CONTINUE ; +} +static void find_short_object_filename (struct disambiguate_state *ds) {struct object_directory *odb; -for (odb = ds->repo->objects->odb; odb && !ds->ambiguous; odb = odb->next) { -int pos; -struct oid_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) { -const struct object_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); }static int match_hash (unsigned len,const unsigned char *a,const unsigned char *b)
object-store.h +3 -2
@@ -9,6 +9,7 @@#include "thread-utils.h" #include "khash.h" #include "dir.h" +#include "oidtree.h" struct object_directory {struct object_directory *next;
@@ -23,7 +24,7 @@ struct object_directory {* Be sure to call odb_load_loose_cache() before using. */ uint32_t loose_objects_subdir_seen[8 ];/* 256 bits */ -struct oid_array loose_objects_cache[256 ]; +struct oidtree *loose_objects_cache;/* * Path to the alternative object store. If this is a relative path,
@@ -59,7 +60,7 @@ void add_to_alternates_memory(const char *dir);* Populate and return the loose object cache array corresponding to the * given object ID. */ -struct oid_array *odb_loose_cache (struct object_directory *odb, +struct oidtree *odb_loose_cache (struct object_directory *odb,const struct object_id *oid);/* Empty the loose object cache for the specified object directory. */
oidtree.c new file +104 -0
104 lines not on this page · raw message
oidtree.h new file +22 -0
@@ -0,0 +1,22 @@ +#ifndef OIDTREE_H +#define OIDTREE_H + +#include "cbtree.h" +#include "hash.h" +#include "mem-pool.h" + +struct oidtree { +struct cb_tree tree; +struct mem_pool mem_pool; +}; + +void oidtree_init (struct oidtree *); +void oidtree_clear (struct oidtree *); +void oidtree_insert (struct oidtree *,const struct object_id *); +int oidtree_contains (struct oidtree *,const struct object_id *); + +typedef enum cb_next (*oidtree_iter )(const struct object_id *,void *data); +void oidtree_each (struct oidtree *,const struct object_id *, +size_t oidhexsz,oidtree_iter ,void *data); + +#endif /* OIDTREE_H */
t/helper/test-oidtree.c new file +49 -0
49 lines not on this page · raw message
t/helper/test-tool.c +1 -0
@@ -43,6 +43,7 @@ static struct test_cmd cmds[] = { { "mktemp", cmd__mktemp }, { "oid-array", cmd__oid_array }, { "oidmap", cmd__oidmap }, + { "oidtree", cmd__oidtree }, { "online-cpus", cmd__online_cpus }, { "parse-options", cmd__parse_options }, { "parse-pathspec-file", cmd__parse_pathspec_file },
t/helper/test-tool.h +1 -0
@@ -32,6 +32,7 @@ int cmd__match_trees(int argc, const char **argv);int cmd__mergesort (int argc,const char **argv);int cmd__mktemp (int argc,const char **argv);int cmd__oidmap (int argc,const char **argv); +int cmd__oidtree (int argc,const char **argv);int cmd__online_cpus (int argc,const char **argv);int cmd__parse_options (int argc,const char **argv);int cmd__parse_pathspec_file (int argc,const char ** argv);
t/t0069-oidtree.sh new file +49 -0
49 lines not on this page · raw message
PATCH v2 1/5 speed up alt_odb_usable() with many alternates
In reply to Eric WongWith 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.
--- object-file.c | 33 ++++++++++++++++++++++----------- object-store.h | 17 +++++++++++++++++ object.c | 2 ++ 3 files changed, 41 insertions(+), 11 deletions(-)
object-file.c +22 -11
@@ -517,9 +517,9 @@ const char *loose_object_path(struct repository *r, struct strbuf *buf,*/ static int alt_odb_usable (struct raw_object_store *o,struct strbuf *path, -const char *normalized_objdir) +const char *normalized_objdir,khiter_t *pos) { -struct object_directory *odb; +int r;/* Detect cases where alternate disappeared */ if (!is_directory (path->buf)) {
@@ -533,14 +533,22 @@ static int alt_odb_usable(struct raw_object_store *o,* Prevent the common mistake of listing the same * thing twice, or object directory itself. */ -for (odb = o->odb; odb; odb = odb->next) { -if (!fspathcmp (path->buf, odb->path)) -return 0 ; +if (!o->odb_by_path) { +khiter_t p; + + 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); +if (r <0 )die_errno (_ ("kh_put_odb_path_map" )); +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" )); +/* r: 0 = exists, 1 = never used, 2 = deleted */ +return r ==0 ?0 :1 ; }/*
@@ -566,6 +574,7 @@ static int link_alt_odb_entry(struct repository *r, const char *entry, {struct object_directory *ent;struct strbuf pathbuf =STRBUF_INIT ; +khiter_t pos;if (!is_absolute_path (entry) && relative_base) {strbuf_realpath (&pathbuf, relative_base,1 );
@@ -587,23 +596,25 @@ static int link_alt_odb_entry(struct repository *r, const char *entry,while (pathbuf.len && pathbuf.buf[pathbuf.len -1 ] =='/' )strbuf_setlen (&pathbuf, pathbuf.len -1 ); -if (!alt_odb_usable (r->objects, &pathbuf, normalized_objdir)) { +if (!alt_odb_usable (r->objects, &pathbuf, normalized_objdir, &pos)) {strbuf_release (&pathbuf);return -1 ; }CALLOC_ARRAY (ent,1 ); - ent->path =xstrdup (pathbuf.buf); +/* pathbuf.buf is already in r->objects->odb_by_path */ + ent->path =strbuf_detach (&pathbuf,NULL );/* add the alternate entry */ *r->objects->odb_tail = ent; r->objects->odb_tail = &(ent->next); ent->next =NULL ; +assert (r->objects->odb_by_path); +kh_value (r->objects->odb_by_path, pos) = ent;/* recursively add alternates */ -read_info_alternates (r, pathbuf.buf, depth +1 ); +read_info_alternates (r, ent->path, depth +1 ); -strbuf_release (&pathbuf);return 0 ; }
object-store.h +17 -0
@@ -7,6 +7,8 @@#include "oid-array.h" #include "strbuf.h" #include "thread-utils.h" +#include "khash.h" +#include "dir.h" struct object_directory {struct object_directory *next;
@@ -30,6 +32,19 @@ struct object_directory {char *path; }; +static inline int odb_path_eq (const char *a,const char *b) +{ +return !fspathcmp (a, b); +} + +static inline int odb_path_hash (const char *str) +{ +return ignore_case ?strihash (str) :__ac_X31_hash_string (str); +} + +KHASH_INIT(odb_path_map, const char * /* key: odb_path */, + struct object_directory *, 1, odb_path_hash, odb_path_eq); +void prepare_alt_odb (struct repository *r);char *compute_alternate_path (const char *path,struct strbuf *err);typedef int alt_odb_fn (struct object_directory *,void *);
@@ -116,6 +131,8 @@ struct raw_object_store {*/ struct object_directory *odb;struct object_directory **odb_tail; +kh_odb_path_map_t *odb_by_path; +int loaded_alternates;/*
object.c +2 -0
@@ -511,6 +511,8 @@ static void free_object_directories(struct raw_object_store *o)free_object_directory (o->odb); o->odb = next; } +kh_destroy_odb_path_map (o->odb_by_path); + o->odb_by_path =NULL ; }void raw_object_store_clear (struct raw_object_store *o)
Am 29.06.21 um 22:53 schrieb Eric Wong:
Quoted 9 lines
With many alternates, the duplicate check in
alt_odb_usable()wastes many cycles doing repeatedfspathcmp()on every existing alternate. Use a khash to speed up lookups byodb->path.Since the kh_put_* API uses the supplied key without duplicating it, we also take advantage of it to replace both
xstrdup()andstrbuf_release()inlink_alt_odb_entry()withstrbuf_detach()to avoid the allocation and copy.
Quoted 4 lines
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 30 lines
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 <[email protected]>--- object-file.c | 33 ++++++++++++++++++++++----------- object-store.h | 17 +++++++++++++++++ object.c | 2 ++ 3 files changed, 41 insertions(+), 11 deletions(-)object-file.c +2
-2@@ -517,9 +517,9 @@ const char *loose_object_path(struct repository *r, struct strbuf *buf,*/ static int alt_odb_usable (struct raw_object_store *o,struct strbuf *path, -const char *normalized_objdir) +const char *normalized_objdir,khiter_t *pos) { -struct object_directory *odb; +int r;/* Detect cases where alternate disappeared */ if (!is_directory (path->buf)) {@@ -533,14 +533,22 @@ static int alt_odb_usable(struct raw_object_store *o,* Prevent the common mistake of listing the same * thing twice, or object directory itself.
object-file.c static int alt_odb_usable(struct raw_object_store *o, · line 541
Quoted 10 lines
object-file.c +6
-3*/ -for (odb = o->odb; odb; odb = odb->next) { -if (!fspathcmp (path->buf, odb->path)) -return 0 ; +if (!o->odb_by_path) { +khiter_t p; + + 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.
object-file.c static int alt_odb_usable(struct raw_object_store *o, · line 542
Quoted 1 line
object-file.c +1
-0+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.
object-file.c static int alt_odb_usable(struct raw_object_store *o, · line 549
Quoted 9 lines
object-file.c +4
-2+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" ));
Dito.
object-file.c static int alt_odb_usable(struct raw_object_store *o, · line 551
Quoted 2 lines
object-file.c +2
-0+/* r: 0 = exists, 1 = never used, 2 = deleted */ +return r ==0 ?0 :1 ;
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.
Quoted 14 lines
object-file.c +1
-0}/* @@ -566,6 +574,7 @@ static int link_alt_odb_entry(struct repository *r, const char *entry, {struct object_directory *ent;struct strbuf pathbuf =STRBUF_INIT ; +khiter_t pos;if (!is_absolute_path (entry) && relative_base) {strbuf_realpath (&pathbuf, relative_base,1 );@@ -587,23 +596,25 @@ static int link_alt_odb_entry(struct repository *r, const char *entry,while (pathbuf.len && pathbuf.buf[pathbuf.len -1 ] =='/' )strbuf_setlen (&pathbuf, pathbuf.len -1 );
object-file.c static int link_alt_odb_entry(struct repository *r, const char *entry, · line 605
Quoted 10 lines
object-file.c +2
-2-if (!alt_odb_usable (r->objects, &pathbuf, normalized_objdir)) { +if (!alt_odb_usable (r->objects, &pathbuf, normalized_objdir, &pos)) {strbuf_release (&pathbuf);return -1 ; }CALLOC_ARRAY (ent,1 ); - ent->path =xstrdup (pathbuf.buf); +/* pathbuf.buf is already in r->objects->odb_by_path */
Tricky stuff (to me), important comment.
Quoted 31 lines
object-file.c +4
-2+ ent->path =strbuf_detach (&pathbuf,NULL );/* add the alternate entry */ *r->objects->odb_tail = ent; r->objects->odb_tail = &(ent->next); ent->next =NULL ; +assert (r->objects->odb_by_path); +kh_value (r->objects->odb_by_path, pos) = ent;/* recursively add alternates */ -read_info_alternates (r, pathbuf.buf, depth +1 ); +read_info_alternates (r, ent->path, depth +1 ); -strbuf_release (&pathbuf);return 0 ; }object-store.h +2
-0@@ -7,6 +7,8 @@#include "oid-array.h" #include "strbuf.h" #include "thread-utils.h" +#include "khash.h" +#include "dir.h" struct object_directory {struct object_directory *next;
object-store.h struct object_directory { · line 38
Quoted 7 lines
object-store.h +4
-0@@ -30,6 +32,19 @@ struct object_directory {char *path; }; +static inline int odb_path_eq (const char *a,const char *b) +{ +return !fspathcmp (a, b); +}
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.
object-store.h struct object_directory { · line 43
Quoted 5 lines
object-store.h +5
-0+ +static inline int odb_path_hash (const char *str) +{ +return ignore_case ?strihash (str) :__ac_X31_hash_string (str); +}
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.
Quoted 30 lines
object-store.h +6
-0+ +KHASH_INIT(odb_path_map, const char * /* key: odb_path */, + struct object_directory *, 1, odb_path_hash, odb_path_eq); +void prepare_alt_odb (struct repository *r);char *compute_alternate_path (const char *path,struct strbuf *err);typedef int alt_odb_fn (struct object_directory *,void *);@@ -116,6 +131,8 @@ struct raw_object_store {*/ struct object_directory *odb;struct object_directory **odb_tail; +kh_odb_path_map_t *odb_by_path; +int loaded_alternates;/* object.c +2
-0@@ -511,6 +511,8 @@ static void free_object_directories(struct raw_object_store *o)free_object_directory (o->odb); o->odb = next; } +kh_destroy_odb_path_map (o->odb_by_path); + o->odb_by_path =NULL ; }void raw_object_store_clear (struct raw_object_store *o)
Am 03.07.21 um 12:05 schrieb René Scharfe:
Quoted 10 lines
Am 29.06.21 um 22:53 schrieb Eric Wong:
Review
Quoted 5 lines
(quoted diff) +4
-0+ *pos = kh_put_odb_path_map(o->odb_by_path, path->buf, &r); + if (r < 0) die_errno(_("kh_put_odb_path_map")); + /* r: 0 = exists, 1 = never used, 2 = deleted */ + return r == 0 ? 0 : 1;I like the solution in
oidset.cto 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(-)
object-file.c +37 -45
@@ -512,45 +512,6 @@ const char *loose_object_path(struct repository *r, struct strbuf *buf,return odb_loose_path (r->objects->odb, buf, oid); } -/* -* Return non-zero iff the path is usable as an alternate object database. -*/ -static int alt_odb_usable (struct raw_object_store *o, -struct strbuf *path, -const char *normalized_objdir,khiter_t *pos) -{ -int r; - -/* Detect cases where alternate disappeared */ -if (!is_directory (path->buf)) { -error (_ ("object directory %s does not exist; " -"check .git/objects/info/alternates" ), - path->buf); -return 0 ; - } - -/* -* Prevent the common mistake of listing the same -* thing twice, or object directory itself. -*/ -if (!o->odb_by_path) { -khiter_t p; - - 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); -if (r <0 )die_errno (_ ("kh_put_odb_path_map" )); -assert (r ==1 );/* never used */ -kh_value (o->odb_by_path, p) = o->odb; - } -if (!fspathcmp (path->buf, normalized_objdir)) -return 0 ; - *pos =kh_put_odb_path_map (o->odb_by_path, path->buf, &r); -if (r <0 )die_errno (_ ("kh_put_odb_path_map" )); -/* r: 0 = exists, 1 = never used, 2 = deleted */ -return r ==0 ?0 :1 ; -} -/* * Prepare alternate object database registry. *
@@ -575,6 +536,9 @@ static int link_alt_odb_entry(struct repository *r, const char *entry,struct object_directory *ent;struct strbuf pathbuf =STRBUF_INIT ;khiter_t pos; +int ret =-1 ; +int added; +struct raw_object_store *o = r->objects;if (!is_absolute_path (entry) && relative_base) {strbuf_realpath (&pathbuf, relative_base,1 );
@@ -585,8 +549,7 @@ static int link_alt_odb_entry(struct repository *r, const char *entry,if (strbuf_normalize_path (&pathbuf) <0 && relative_base) {error (_ ("unable to normalize alternate object path: %s" ), pathbuf.buf); -strbuf_release (&pathbuf); -return -1 ; + goto out; }/*
@@ -596,11 +559,37 @@ static int link_alt_odb_entry(struct repository *r, const char *entry,while (pathbuf.len && pathbuf.buf[pathbuf.len -1 ] =='/' )strbuf_setlen (&pathbuf, pathbuf.len -1 ); -if (!alt_odb_usable (r->objects, &pathbuf, normalized_objdir, &pos)) { -strbuf_release (&pathbuf); -return -1 ; +/* Detect cases where alternate disappeared */ +if (!is_directory (pathbuf.buf)) { +error (_ ("object directory %s does not exist; " +"check .git/objects/info/alternates" ), + pathbuf.buf); + goto out; + } + +/* +* Prevent the common mistake of listing the same +* thing twice, or object directory itself. +*/ +if (!o->odb_by_path) { +khiter_t p; + + 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, &added); +if (added <0 )die_errno (_ ("kh_put_odb_path_map" )); +assert (added); +kh_value (o->odb_by_path, p) = o->odb; } +if (!fspathcmp (pathbuf.buf, normalized_objdir)) + goto out; + + pos =kh_put_odb_path_map (o->odb_by_path, pathbuf.buf, &added); +if (added <0 )die_errno (_ ("kh_put_odb_path_map" )); +if (!added) + goto out; +CALLOC_ARRAY (ent,1 );/* pathbuf.buf is already in r->objects->odb_by_path */ ent->path =strbuf_detach (&pathbuf,NULL );
@@ -615,7 +604,10 @@ static int link_alt_odb_entry(struct repository *r, const char *entry,/* recursively add alternates */ read_info_alternates (r, ent->path, depth +1 ); -return 0 ; + ret =0 ; +out: +strbuf_release (&pathbuf); +return ret; } static const char *parse_alt_odb_entry(const char *string,
Quoted 81 lines · René Scharfe
Am 29.06.21 um 22:53 schrieb Eric Wong:
Quoted 9 lines
With many alternates, the duplicate check in
alt_odb_usable()wastes many cycles doing repeatedfspathcmp()on every existing alternate. Use a khash to speed up lookups byodb->path.Since the kh_put_* API uses the supplied key without duplicating it, we also take advantage of it to replace both
xstrdup()andstrbuf_release()inlink_alt_odb_entry()withstrbuf_detach()to avoid the allocation and copy.Quoted 4 lines
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 30 lines
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 <[email protected]>--- object-file.c | 33 ++++++++++++++++++++++----------- object-store.h | 17 +++++++++++++++++ object.c | 2 ++ 3 files changed, 41 insertions(+), 11 deletions(-)object-file.c +2
-2@@ -517,9 +517,9 @@ const char *loose_object_path(struct repository *r, struct strbuf *buf,*/ static int alt_odb_usable (struct raw_object_store *o,struct strbuf *path, -const char *normalized_objdir) +const char *normalized_objdir,khiter_t *pos) { -struct object_directory *odb; +int r;/* Detect cases where alternate disappeared */ if (!is_directory (path->buf)) {@@ -533,14 +533,22 @@ static int alt_odb_usable(struct raw_object_store *o,* Prevent the common mistake of listing the same * thing twice, or object directory itself. object-file.c static int alt_odb_usable(struct raw_object_store *o, · line 541
Quoted 10 lines
object-file.c +6
-3*/ -for (odb = o->odb; odb; odb = odb->next) { -if (!fspathcmp (path->buf, odb->path)) -return 0 ; +if (!o->odb_by_path) { +khiter_t p; + + 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.
object-file.c static int alt_odb_usable(struct raw_object_store *o, · line 542
Quoted 1 line
object-file.c +1
-0+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 inkhash.h.object-file.c static int alt_odb_usable(struct raw_object_store *o, · line 549
Quoted 9 lines
object-file.c +4
-2+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" ));Dito.
Quoted 6 lines
object-file.c static int alt_odb_usable(struct raw_object_store *o, · line 551
Quoted 2 lines
object-file.c +2
-0+/* r: 0 = exists, 1 = never used, 2 = deleted */ +return r ==0 ?0 :1 ;The comment indicates that khash would be nicer to use if it had an enum for the
kh_putreturn 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...
Quoted 24 lines
I like the solution in
oidset.cto make this more readable, though: Call the return value "added" instead of "r" and then a "return !added;" makes sense without additional comments.Quoted 20 lines
object-file.c +0
-0}/* object-store.h +2
-0@@ -7,6 +7,8 @@#include "oid-array.h" #include "strbuf.h" #include "thread-utils.h" +#include "khash.h" +#include "dir.h" struct object_directory {struct object_directory *next;@@ -30,6 +32,19 @@ struct object_directory {char *path; };
Quoted 9 lines
object-store.h struct object_directory { · line 38
Quoted 4 lines
object-store.h +4
-0+static inline int odb_path_eq (const char *a,const char *b) +{ +return !fspathcmp (a, b); +}This is not specific to the object store. It could be called fspatheq and live in
dir.h. Ordir.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.
Quoted 10 lines
object-store.h struct object_directory { · line 43
Quoted 5 lines
object-store.h +5
-0+ +static inline int odb_path_hash (const char *str) +{ +return ignore_case ?strihash (str) :__ac_X31_hash_string (str); +}The internal Attractive Chaos (__ac_*) macros should be left confined to
khash.h, I think. Its aliaskh_str_hash_funcwould be better suited here.
Quoted 7 lines
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.candmerge-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.
Quoted 3 lines
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.
PATCH v2 2/5 avoid strlen via strbuf_addstr in link_alt_odb_entry
In reply to Eric WongWe 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 *".
--- object-file.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)
object-file.c +4 -4
@@ -569,18 +569,18 @@ static int alt_odb_usable(struct raw_object_store *o,static void read_info_alternates (struct repository *r,const char *relative_base,int depth); -static int link_alt_odb_entry (struct repository *r,const char *entry, +static int link_alt_odb_entry (struct repository *r,const struct strbuf *entry,const char *relative_base,int depth,const char *normalized_objdir) {struct object_directory *ent;struct strbuf pathbuf =STRBUF_INIT ;khiter_t pos; -if (!is_absolute_path (entry) && relative_base) { +if (!is_absolute_path (entry->buf) && relative_base) {strbuf_realpath (&pathbuf, relative_base,1 );strbuf_addch (&pathbuf,'/' ); } -strbuf_addstr (&pathbuf, entry); +strbuf_addbuf (&pathbuf, entry);if (strbuf_normalize_path (&pathbuf) <0 && relative_base) { error(_("unable to normalize alternate object path: %s"),
@@ -671,7 +671,7 @@ static void link_alt_odb_entries(struct repository *r, const char *alt, alt =parse_alt_odb_entry (alt, sep, &entry);if (!entry.len)continue ; -link_alt_odb_entry (r, entry.buf, +link_alt_odb_entry (r, &entry, relative_base, depth, objdirbuf.buf); }strbuf_release (&entry);
PATCH v2 3/5 make object_directory.loose_objects_subdir_seen a bitmap
In reply to Eric WongThere'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
--- object-file.c | 11 ++++++++--- object-store.h | 2 +- 2 files changed, 9 insertions(+), 4 deletions(-)
object-file.c +8 -3
@@ -2463,12 +2463,17 @@ struct oid_array *odb_loose_cache(struct object_directory *odb, {int subdir_nr = oid->hash[0 ];struct strbuf buf =STRBUF_INIT ; +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); +uint32_t *bitmap;if (subdir_nr <0 || - subdir_nr >=ARRAY_SIZE (odb->loose_objects_subdir_seen)) + subdir_nr >=bitsizeof (odb->loose_objects_subdir_seen))BUG ("subdir_nr out of range" ); -if (odb->loose_objects_subdir_seen[subdir_nr]) + bitmap = &odb->loose_objects_subdir_seen[word_index]; +if (*bitmap & mask)return &odb->loose_objects_cache[subdir_nr];strbuf_addstr (&buf, odb->path);
@@ -2476,7 +2481,7 @@ struct oid_array *odb_loose_cache(struct object_directory *odb, append_loose_object,NULL ,NULL , &odb->loose_objects_cache[subdir_nr]); - odb->loose_objects_subdir_seen[subdir_nr] =1 ; + *bitmap |= mask;strbuf_release (&buf);return &odb->loose_objects_cache[subdir_nr]; }
object-store.h +1 -1
@@ -22,7 +22,7 @@ struct object_directory {* * Be sure to call odb_load_loose_cache() before using. */ -char loose_objects_subdir_seen[256 ]; +uint32_t loose_objects_subdir_seen[8 ];/* 256 bits */ struct oid_array loose_objects_cache[256 ];/*
PATCH v2 4/5 oidcpy_with_padding: constify `src' arg
In reply to Eric WongAs with `oidcpy', the source struct will not be modified and this will allow an upcoming const-correct caller to use it.
--- hash.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
hash.h +1 -1
@@ -265,7 +265,7 @@ static inline void oidcpy(struct object_id *dst, const struct object_id *src)/* Like oidcpy() but zero-pads the unused bytes in dst's hash array. */ static inline void oidcpy_with_padding (struct object_id *dst, -struct object_id *src) +const struct object_id *src) {size_t hashsz;
PATCH v2 5/5 oidtree: a crit-bit tree for odb_loose_cache
In reply to Eric WongThis 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
--- 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
Makefile +3 -0
@@ -722,6 +722,7 @@ TEST_BUILTINS_OBJS += test-mergesort.o TEST_BUILTINS_OBJS += test-mktemp.o TEST_BUILTINS_OBJS += test-oid-array.o TEST_BUILTINS_OBJS += test-oidmap.o +TEST_BUILTINS_OBJS += test-oidtree.o TEST_BUILTINS_OBJS += test-online-cpus.o TEST_BUILTINS_OBJS += test-parse-options.o TEST_BUILTINS_OBJS += test-parse-pathspec-file.o
@@ -845,6 +846,7 @@ LIB_OBJS += branch.o LIB_OBJS += bulk-checkin.o LIB_OBJS += bundle.o LIB_OBJS += cache-tree.o +LIB_OBJS += cbtree.o LIB_OBJS += chdir-notify.o LIB_OBJS += checkout.o LIB_OBJS += chunk-format.o
@@ -940,6 +942,7 @@ LIB_OBJS += object.o LIB_OBJS += oid-array.o LIB_OBJS += oidmap.o LIB_OBJS += oidset.o +LIB_OBJS += oidtree.o LIB_OBJS += pack-bitmap-write.o LIB_OBJS += pack-bitmap.o LIB_OBJS += pack-check.o
alloc.c +6 -0
@@ -14,6 +14,7 @@#include "tree.h" #include "commit.h" #include "tag.h" +#include "oidtree.h" #include "alloc.h" #define BLOCKING 1024
@@ -123,6 +124,11 @@ void *alloc_commit_node(struct repository *r)return c; } +void *alloc_from_state (struct alloc_state *alloc_state,size_t n) +{ +return alloc_node (alloc_state, n); +} +static void report (const char *name,unsigned int count,size_t size) { fprintf(stderr, "%10s: %8u (%"PRIuMAX" kB)\n",
alloc.h +1 -0
@@ -13,6 +13,7 @@ void init_commit_node(struct commit *c);void *alloc_commit_node (struct repository *r);void *alloc_tag_node (struct repository *r);void *alloc_object_node (struct repository *r); +void *alloc_from_state (struct alloc_state *,size_t n);void alloc_report (struct repository *r);struct alloc_state *allocate_alloc_state (void );
cbtree.c new file +167 -0
167 lines not on this page · raw message
cbtree.h new file +56 -0
56 lines not on this page · raw message
object-file.c +7 -10
@@ -1175,7 +1175,7 @@ static int quick_has_loose(struct repository *r,prepare_alt_odb (r);for (odb = r->objects->odb; odb; odb = odb->next) { -if (oid_array_lookup (odb_loose_cache (odb, oid), oid) >=0 ) +if (oidtree_contains (odb_loose_cache (odb, oid), oid))return 1 ; }return 0 ;
@@ -2454,11 +2454,11 @@ int for_each_loose_object(each_loose_object_fn cb, void *data,static int append_loose_object (const struct object_id *oid,const char *path,void *data) { -oid_array_append (data, oid); +oidtree_insert (data, oid);return 0 ; } -struct oid_array *odb_loose_cache (struct object_directory *odb, +struct oidtree *odb_loose_cache (struct object_directory *odb,const struct object_id *oid) {int subdir_nr = oid->hash[0 ];
@@ -2474,24 +2474,21 @@ struct oid_array *odb_loose_cache(struct object_directory *odb, bitmap = &odb->loose_objects_subdir_seen[word_index];if (*bitmap & mask) -return &odb->loose_objects_cache[subdir_nr]; +return &odb->loose_objects_cache;strbuf_addstr (&buf, odb->path);for_each_file_in_obj_subdir (subdir_nr, &buf, append_loose_object,NULL ,NULL , - &odb->loose_objects_cache[subdir_nr]); + &odb->loose_objects_cache); *bitmap |= mask;strbuf_release (&buf); -return &odb->loose_objects_cache[subdir_nr]; +return &odb->loose_objects_cache; }void odb_clear_loose_cache (struct object_directory *odb) { -int i; - -for (i =0 ; i <ARRAY_SIZE (odb->loose_objects_cache); i++) -oid_array_clear (&odb->loose_objects_cache[i]); +oidtree_destroy (&odb->loose_objects_cache);memset (&odb->loose_objects_subdir_seen,0 ,sizeof (odb->loose_objects_subdir_seen)); }
object-name.c +11 -17
@@ -87,27 +87,21 @@ static void update_candidates(struct disambiguate_state *ds, const struct objectstatic int match_hash (unsigned ,const unsigned char *,const unsigned char *); +static enum cb_next match_prefix (const struct object_id *oid,void *arg) +{ +struct disambiguate_state *ds = arg; +/* no need to call match_hash, oidtree_each did prefix match */ +update_candidates (ds, oid); +return ds->ambiguous ?CB_BREAK :CB_CONTINUE ; +} +static void find_short_object_filename (struct disambiguate_state *ds) {struct object_directory *odb; -for (odb = ds->repo->objects->odb; odb && !ds->ambiguous; odb = odb->next) { -int pos; -struct oid_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) { -const struct object_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); }static int match_hash (unsigned len,const unsigned char *a,const unsigned char *b)
object-store.h +3 -2
@@ -9,6 +9,7 @@#include "thread-utils.h" #include "khash.h" #include "dir.h" +#include "oidtree.h" struct object_directory {struct object_directory *next;
@@ -23,7 +24,7 @@ struct object_directory {* Be sure to call odb_load_loose_cache() before using. */ uint32_t loose_objects_subdir_seen[8 ];/* 256 bits */ -struct oid_array loose_objects_cache[256 ]; +struct oidtree loose_objects_cache;/* * Path to the alternative object store. If this is a relative path,
@@ -69,7 +70,7 @@ void add_to_alternates_memory(const char *dir);* Populate and return the loose object cache array corresponding to the * given object ID. */ -struct oid_array *odb_loose_cache (struct object_directory *odb, +struct oidtree *odb_loose_cache (struct object_directory *odb,const struct object_id *oid);/* Empty the loose object cache for the specified object directory. */
oidtree.c new file +94 -0
94 lines not on this page · raw message
oidtree.h new file +29 -0
@@ -0,0 +1,29 @@ +#ifndef OIDTREE_H +#define OIDTREE_H + +#include "cbtree.h" +#include "hash.h" + +struct alloc_state ; +struct oidtree { +struct cb_tree t; +struct alloc_state *mempool; +}; + +#define OIDTREE_INIT { .t = CBTREE_INIT, .mempool = NULL } + +static inline void oidtree_init (struct oidtree *ot) +{ +cb_init (&ot->t); + ot->mempool =NULL ; +} + +void oidtree_destroy (struct oidtree *); +void oidtree_insert (struct oidtree *,const struct object_id *); +int oidtree_contains (struct oidtree *,const struct object_id *); + +typedef enum cb_next (*oidtree_iter )(const struct object_id *,void *arg); +void oidtree_each (struct oidtree *,const struct object_id *, +size_t oidhexlen,oidtree_iter ,void *arg); + +#endif /* OIDTREE_H */
t/helper/test-oidtree.c new file +47 -0
47 lines not on this page · raw message
t/helper/test-tool.c +1 -0
@@ -43,6 +43,7 @@ static struct test_cmd cmds[] = { { "mktemp", cmd__mktemp }, { "oid-array", cmd__oid_array }, { "oidmap", cmd__oidmap }, + { "oidtree", cmd__oidtree }, { "online-cpus", cmd__online_cpus }, { "parse-options", cmd__parse_options }, { "parse-pathspec-file", cmd__parse_pathspec_file },
t/helper/test-tool.h +1 -0
@@ -32,6 +32,7 @@ int cmd__match_trees(int argc, const char **argv);int cmd__mergesort (int argc,const char **argv);int cmd__mktemp (int argc,const char **argv);int cmd__oidmap (int argc,const char **argv); +int cmd__oidtree (int argc,const char **argv);int cmd__online_cpus (int argc,const char **argv);int cmd__parse_options (int argc,const char **argv);int cmd__parse_pathspec_file (int argc,const char ** argv);
t/t0069-oidtree.sh new file +52 -0
52 lines not on this page · raw message
Re: [PATCH v2 5/5] oidtree: a crit-bit tree for odb_loose_cache
Am 29.06.21 um 22:53 schrieb Eric Wong:
Quoted 15 lines
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 theoidtree' wrapper on top of it. The latter provides allocation usingalloc_stateas 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.
Quoted 3 lines
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 83 lines
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 <[email protected]>--- 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.shMakefile +3
-0@@ -722,6 +722,7 @@ TEST_BUILTINS_OBJS += test-mergesort.o TEST_BUILTINS_OBJS += test-mktemp.o TEST_BUILTINS_OBJS += test-oid-array.o TEST_BUILTINS_OBJS += test-oidmap.o +TEST_BUILTINS_OBJS += test-oidtree.o TEST_BUILTINS_OBJS += test-online-cpus.o TEST_BUILTINS_OBJS += test-parse-options.o TEST_BUILTINS_OBJS += test-parse-pathspec-file.o@@ -845,6 +846,7 @@ LIB_OBJS += branch.o LIB_OBJS += bulk-checkin.o LIB_OBJS += bundle.o LIB_OBJS += cache-tree.o +LIB_OBJS += cbtree.o LIB_OBJS += chdir-notify.o LIB_OBJS += checkout.o LIB_OBJS += chunk-format.o@@ -940,6 +942,7 @@ LIB_OBJS += object.o LIB_OBJS += oid-array.o LIB_OBJS += oidmap.o LIB_OBJS += oidset.o +LIB_OBJS += oidtree.o LIB_OBJS += pack-bitmap-write.o LIB_OBJS += pack-bitmap.o LIB_OBJS += pack-check.oalloc.c +1
-0@@ -14,6 +14,7 @@#include "tree.h" #include "commit.h" #include "tag.h" +#include "oidtree.h" #include "alloc.h" #define BLOCKING 1024
alloc.c void *alloc_commit_node(struct repository *r) · line 131
Quoted 8 lines
alloc.c +5
-0@@ -123,6 +124,11 @@ void *alloc_commit_node(struct repository *r)return c; } +void *alloc_from_state (struct alloc_state *alloc_state,size_t n) +{ +return alloc_node (alloc_state, n); +} +
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..)
Quoted 42 lines
oidtree.c new file +36
-0@@ -0,0 +1,94 @@ +/* +* A wrapper around cbtree which stores oids +* May be used to replace oid-array for prefix (abbreviation) matches +*/ +#include "oidtree.h" +#include "alloc.h" +#include "hash.h" + +struct oidtree_node { +/* n.k[] is used to store "struct object_id" */ +struct cb_node n; +}; + +struct oidtree_iter_data { +oidtree_iter fn; +void *arg; +size_t *last_nibble_at; +int algo; +uint8_t last_byte; +}; + +void oidtree_destroy (struct oidtree *ot) +{ +if (ot->mempool) { +clear_alloc_state (ot->mempool); +FREE_AND_NULL (ot->mempool); + } +oidtree_init (ot); +} + +void oidtree_insert (struct oidtree *ot,const struct object_id *oid) +{ +struct oidtree_node *on; + +if (!ot->mempool) + ot->mempool =allocate_alloc_state ();
oidtree.c line 46
Quoted 10 lines
oidtree.c new file +10
-0+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.
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.
oidtree.c line 54
Quoted 8 lines
oidtree.c new file +8
-0+cb_insert (&ot->t, &on->n,sizeof (*oid)); +} + +int oidtree_contains (struct oidtree *ot,const struct object_id *oid) +{ +struct object_id k = {0 }; +size_t klen =sizeof (k); +oidcpy_with_padding (&k, oid);
Why initialize k; isn't oidcpy_with_padding() supposed to overwrite it completely?
oidtree.c line 59
Quoted 5 lines
oidtree.c new file +5
-0+ +if (oid->algo ==GIT_HASH_UNKNOWN ) { + k.algo =hash_algo_by_ptr (the_hash_algo); + klen -=sizeof (oid->algo); + }
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()?
Quoted 25 lines
oidtree.c new file +25
-0+ +return cb_lookup (&ot->t, (const uint8_t *)&k, klen) ?1 :0 ; +} + +static enum cb_next iter (struct cb_node *n,void *arg) +{ +struct oidtree_iter_data *x = arg; +const struct object_id *oid = (const struct object_id *)n->k; + +if (x->algo !=GIT_HASH_UNKNOWN && x->algo != oid->algo) +return CB_CONTINUE ; + +if (x->last_nibble_at) { +if ((oid->hash[*x->last_nibble_at] ^ x->last_byte) &0xf0 ) +return CB_CONTINUE ; + } + +return x->fn (oid, x->arg); +} + +void oidtree_each (struct oidtree *ot,const struct object_id *oid, +size_t oidhexlen,oidtree_iter fn,void *arg) +{ +size_t klen = oidhexlen /2 ; +struct oidtree_iter_data x = {0 };
oidtree.c line 94
Quoted 10 lines
oidtree.c new file +10
-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, (const uint8_t *)oid, klen, iter, &x); +}
Clamp oidhexlen at GIT_MAX_HEXSZ? Or die?
René
Re: [PATCH v2 5/5] oidtree: a crit-bit tree for odb_loose_cache
Quoted 15 lines · René Scharfe
Am 29.06.21 um 22:53 schrieb Eric Wong:
Quoted 14 lines
alloc.c +1
-0@@ -14,6 +14,7 @@#include "tree.h" #include "commit.h" #include "tag.h" +#include "oidtree.h" #include "alloc.h" #define BLOCKING 1024@@ -123,6 +124,11 @@ void *alloc_commit_node(struct repository *r)return c; }
Quoted 9 lines
alloc.c void *alloc_commit_node(struct repository *r) · line 131
Quoted 5 lines
alloc.c +5
-0+void *alloc_from_state (struct alloc_state *alloc_state,size_t n) +{ +return alloc_node (alloc_state, n); +} +Why extend
alloc.cinstead of usingmem-pool.c? (I don't know which fits better, but when you say "memory pool" and not usemem-pool.cI 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 12 lines
Quoted 12 lines
alloc.c +12
-0+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); +
Quoted 8 lines
alloc.c
Quoted 4 lines
alloc.c +4
-0+/* +* 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_seenbitmap.
Yes, it reflects the current caller.
Quoted 4 lines
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.
Quoted 3 lines
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.
Quoted 11 lines
alloc.c
Quoted 8 lines
alloc.c +8
-0+cb_insert (&ot->t, &on->n,sizeof (*oid)); +} + +int oidtree_contains (struct oidtree *ot,const struct object_id *oid) +{ +struct object_id k = {0 }; +size_t klen =sizeof (k); +oidcpy_with_padding (&k, oid);Why initialize k; isn't
oidcpy_with_padding()supposed to overwrite it completely?
Ah, I only added oidcpy_with_padding later into the development of this patch.
Quoted 11 lines
alloc.c
Quoted 5 lines
alloc.c +5
-0+ +if (oid->algo ==GIT_HASH_UNKNOWN ) { + k.algo =hash_algo_by_ptr (the_hash_algo); + klen -=sizeof (oid->algo); + }This relies on the order of the members hash and algo in struct
object_idto 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?
Quoted 1 line
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.
Quoted 2 lines
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 byoidcpy_with_padding()?
Good point, shortening klen would've been all that was needed.
Quoted 9 lines
Quoted 9 lines
alloc.c +9
-0+void oidtree_each (struct oidtree *ot,const struct object_id *oid, +size_t oidhexlen,oidtree_iter fn,void *arg) +{ +size_t klen = oidhexlen /2 ; +struct oidtree_iter_data x = {0 }; + + x.fn = fn; + x.arg = arg; + x.algo = oid->algo;
Quoted 8 lines
alloc.c
Quoted 6 lines
alloc.c +6
-0+if (oidhexlen &1 ) { + x.last_byte = oid->hash[klen]; + x.last_nibble_at = &klen; + } +cb_each (&ot->t, (const uint8_t *)oid, klen, iter, &x); +}Clamp oidhexlen at
GIT_MAX_HEXSZ? Or die?
I think an assertion would be enough, here. init_object_disambiguation already clamps to the_hash_algo->hexsz
Re: [PATCH v2 5/5] oidtree: a crit-bit tree for odb_loose_cache
In reply to Eric Wongoidtree.h line 9
Quoted 3 lines · Eric Wong
oidtree.h new file +3
-0+struct alloc_state ; +struct oidtree { +struct cb_tree t;
s/t/tree/? Too short a name for an interface IMO.
oidtree.h line 13
Quoted 4 lines
oidtree.h new file +4
-0+struct alloc_state *mempool; +}; + +#define OIDTREE_INIT { .t = CBTREE_INIT, .mempool = NULL }
Let's use designated initilaizers for new code. Just:
#define OIDTREE_init { \
.tere = CBTREE_INIT, \
}Will do, no need for the ".mempool = NULL"
oidtree.h line 19
Quoted 5 lines
oidtree.h new file +5
-0+static inline void oidtree_init (struct oidtree *ot) +{ +cb_init (&ot->t); + ot->mempool =NULL ; +}
You can use the "memcpy() a blank" trick/idiom here:
https://lore.kernel.org/git/[email protected]/
Also, is this even needed? Why have the "destroy" re-initialize it?
Quoted 1 line
+void
oidtree_destroy(struct oidtree *);
Maybe s/destroy/release/, or if you actually need that reset behavior oidtree_reset(). We've got
oidtree.h line 25
Quoted 4 lines
oidtree.h new file +4
-0+void oidtree_insert (struct oidtree *,const struct object_id *); +int oidtree_contains (struct oidtree *,const struct object_id *); + +typedef enum cb_next (*oidtree_iter )(const struct object_id *,void *arg);
An "arg" name for some arguments, but none for others, if there's a name here call it "data" like you do elswhere?
oidtree.h line 27
Quoted 2 lines
oidtree.h new file +2
-0+void oidtree_each (struct oidtree *,const struct object_id *, +size_t oidhexlen,oidtree_iter ,void *arg);
s/oidhexlen/hexsz/, like in git_hash_algo.a
Quoted 35 lines
oidtree.h new file +2
-0+ +#endif /* OIDTREE_H */ t/helper/test-oidtree.c new file +27
-0@@ -0,0 +1,47 @@ +#include "test-tool.h" +#include "cache.h" +#include "oidtree.h" + +static enum cb_next print_oid (const struct object_id *oid,void *data) +{ +puts (oid_to_hex (oid)); +return CB_CONTINUE ; +} + +int cmd__oidtree (int argc,const char **argv) +{ +struct oidtree ot =OIDTREE_INIT ; +struct strbuf line =STRBUF_INIT ; +int nongit_ok; +int algo =GIT_HASH_UNKNOWN ; + +setup_git_directory_gently (&nongit_ok); + +while (strbuf_getline (&line, stdin) !=EOF ) { +const char *arg; +struct object_id oid; + +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;
t/helper/test-oidtree.c line 37
Quoted 10 lines
t/helper/test-oidtree.c new file +10
-0+oidtree_insert (&ot, &oid); + }else if (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)); + }else if (skip_prefix (line.buf,"each " , &arg)) { +char buf[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.
t/helper/test-oidtree.c line 44
Quoted 7 lines
t/helper/test-oidtree.c new file +7
-0+get_oid_hex_any (buf, &oid); + oid.algo = algo; +oidtree_each (&ot, &oid,strlen (arg), print_oid,NULL ); + }else if (!strcmp (line.buf,"destroy" )) +oidtree_destroy (&ot); +else +die ("unknown command: %s" , line.buf);
Missing braces.
Quoted 43 lines
t/helper/test-oidtree.c new file +3
-0+ } +return 0 ; +}t/helper/test-tool.c +1
-0@@ -43,6 +43,7 @@ static struct test_cmd cmds[] = { { "mktemp", cmd__mktemp }, { "oid-array", cmd__oid_array }, { "oidmap", cmd__oidmap }, + { "oidtree", cmd__oidtree }, { "online-cpus", cmd__online_cpus }, { "parse-options", cmd__parse_options }, { "parse-pathspec-file", cmd__parse_pathspec_file },t/helper/test-tool.h +1
-0@@ -32,6 +32,7 @@ int cmd__match_trees(int argc, const char **argv);int cmd__mergesort (int argc,const char **argv);int cmd__mktemp (int argc,const char **argv);int cmd__oidmap (int argc,const char **argv); +int cmd__oidtree (int argc,const char **argv);int cmd__online_cpus (int argc,const char **argv);int cmd__parse_options (int argc,const char **argv);int cmd__parse_pathspec_file (int argc,const char ** argv);t/t0069-oidtree.sh new file +10
-0@@ -0,0 +1,52 @@ +#!/bin/sh + +test_description='basic tests for the oidtree implementation' +. ./test-lib.sh + +echoid () { + prefix="${1:+$1 }" + shift + while test $# -gt 0 + do
t/t0069-oidtree.sh line 20
Quoted 10 lines
t/t0069-oidtree.sh new file +10
-0+ echo "$1" + shift + done | awk -v prefix="$prefix" -v ZERO_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"t/t0069-oidtree.sh line 30
Quoted 10 lines
t/t0069-oidtree.sh new file +10
-0+ +test_expect_success 'oidtree insert and contains' ' + cat >expect <<EOF && +0 +0 +0 +1 +1 +0 +EOF
use "<<-\EOF" and indent it.
Quoted 22 lines
t/t0069-oidtree.sh new file +22
-0+ { + echoid insert 444 1 2 3 4 5 a b c d e && + echoid contains 44 441 440 444 4440 4444 + echo destroy + } | test-tool oidtree >actual && + test_cmp expect actual +' + +test_expect_success 'oidtree each' ' + echoid "" 123 321 321 >expect && + { + echoid insert f 9 8 123 321 a b c d e + echo each 12300 + echo each 3211 + echo each 3210 + echo each 32100 + echo destroy + } | test-tool oidtree >actual && + test_cmp expect actual +' + +test_done
Re: [PATCH v2 5/5] oidtree: a crit-bit tree for odb_loose_cache
Quoted 8 lines · Ævar Arnfjörð Bjarmason
oidtree.h line 9
Quoted 3 lines · Eric Wong
oidtree.h new file +3
-0+struct alloc_state ; +struct oidtree { +struct cb_tree t;s/t/tree/? Too short a name for an interface IMO.
Done. I was keeping `t' to match agl's published version (and it remains that way in cbtree.[ch])
Quoted 22 lines
oidtree.h line 13
Quoted 4 lines
oidtree.h new file +4
-0+struct alloc_state *mempool; +}; + +#define OIDTREE_INIT { .t = CBTREE_INIT, .mempool = NULL }Let's use designated initilaizers for new code. Just:
#define OIDTREE_init { \ .tere = CBTREE_INIT, \ }Will do, no need for the ".mempool = NULL"
oidtree.h line 19
Quoted 5 lines
oidtree.h new file +5
-0+static inline void oidtree_init (struct oidtree *ot) +{ +cb_init (&ot->t); + ot->mempool =NULL ; +}You can use the "
memcpy()a blank" trick/idiom here:
https://lore.kernel.org/git/[email protected]/
Quoted 1 line
Also, is this even needed? Why have the "destroy" re-initialize it?
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 4 lines
Quoted 1 line
+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.
Quoted 7 lines
oidtree.h line 25
Quoted 4 lines
oidtree.h new file +4
-0+void oidtree_insert (struct oidtree *,const struct object_id *); +int oidtree_contains (struct oidtree *,const struct object_id *); + +typedef enum cb_next (*oidtree_iter )(const struct object_id *,void *arg);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.
Quoted 4 lines
oidtree.h line 27
Quoted 2 lines
oidtree.h new file +2
-0+void oidtree_each (struct oidtree *,const struct object_id *, +size_t oidhexlen,oidtree_iter ,void *arg);s/oidhexlen/hexsz/, like in git_hash_algo.a
done
Quoted 34 lines
Quoted 34 lines
+++
b/t/helper/test-oidtree.ct/helper/test-oidtree.c new file +32
-0@@ -0,0 +1,47 @@ +#include "test-tool.h" +#include "cache.h" +#include "oidtree.h" + +static enum cb_next print_oid (const struct object_id *oid,void *data) +{ +puts (oid_to_hex (oid)); +return CB_CONTINUE ; +} + +int cmd__oidtree (int argc,const char **argv) +{ +struct oidtree ot =OIDTREE_INIT ; +struct strbuf line =STRBUF_INIT ; +int nongit_ok; +int algo =GIT_HASH_UNKNOWN ; + +setup_git_directory_gently (&nongit_ok); + +while (strbuf_getline (&line, stdin) !=EOF ) { +const char *arg; +struct object_id oid; + +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); + }else if (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));
Quoted 8 lines
t/helper/test-oidtree.c line 37
Quoted 5 lines
t/helper/test-oidtree.c new file +5
-0+ }else if (skip_prefix (line.buf,"each " , &arg)) { +char buf[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.
done
Quoted 9 lines
t/helper/test-oidtree.c line 44
Quoted 7 lines
t/helper/test-oidtree.c new file +7
-0+get_oid_hex_any (buf, &oid); + oid.algo = algo; +oidtree_each (&ot, &oid,strlen (arg), print_oid,NULL ); + }else if (!strcmp (line.buf,"destroy" )) +oidtree_destroy (&ot); +else +die ("unknown command: %s" , line.buf);Missing braces.
Added.
Quoted 49 lines
Quoted 49 lines
t/helper/test-oidtree.c new file +3
-0+ } +return 0 ; +}t/helper/test-tool.c +1
-0@@ -43,6 +43,7 @@ static struct test_cmd cmds[] = { { "mktemp", cmd__mktemp }, { "oid-array", cmd__oid_array }, { "oidmap", cmd__oidmap }, + { "oidtree", cmd__oidtree }, { "online-cpus", cmd__online_cpus }, { "parse-options", cmd__parse_options }, { "parse-pathspec-file", cmd__parse_pathspec_file },t/helper/test-tool.h +1
-0@@ -32,6 +32,7 @@ int cmd__match_trees(int argc, const char **argv);int cmd__mergesort (int argc,const char **argv);int cmd__mktemp (int argc,const char **argv);int cmd__oidmap (int argc,const char **argv); +int cmd__oidtree (int argc,const char **argv);int cmd__online_cpus (int argc,const char **argv);int cmd__parse_options (int argc,const char **argv);int cmd__parse_pathspec_file (int argc,const char ** argv);t/t0069-oidtree.sh new file +16
-0@@ -0,0 +1,52 @@ +#!/bin/sh + +test_description='basic tests for the oidtree implementation' +. ./test-lib.sh + +echoid () { + prefix="${1:+$1 }" + shift + while test $# -gt 0 + do + echo "$1" + shift + done | awk -v prefix="$prefix" -v ZERO_OID=$ZERO_OID '{ + printf("%s%s", prefix, $0); + need = length(ZERO_OID) - length($0); + for (i = 0; i < need; i++)
Quoted 8 lines
t/t0069-oidtree.sh line 20
Quoted 4 lines
t/t0069-oidtree.sh new file +4
-0+ 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.
Quoted 4 lines
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.
Quoted 4 lines
Quoted 4 lines
t/t0069-oidtree.sh new file +4
-0+ +test_expect_success 'oidtree insert and contains' ' + cat >expect <<EOF && +0
Quoted 8 lines
t/t0069-oidtree.sh line 30
Quoted 6 lines
t/t0069-oidtree.sh new file +6
-0+0 +0 +1 +1 +0 +EOFuse "<<-\EOF" and indent it.
done
Thanks all for the reviews.
Re: [PATCH v2 5/5] oidtree: a crit-bit tree for odb_loose_cache
In reply to Eric WongQuoted 23 lines · Eric Wong
[...snip...]
oidtree.c new file +15
-0@@ -0,0 +1,94 @@ +/* +* A wrapper around cbtree which stores oids +* May be used to replace oid-array for prefix (abbreviation) matches +*/ +#include "oidtree.h" +#include "alloc.h" +#include "hash.h" + +struct oidtree_node { +/* n.k[] is used to store "struct object_id" */ +struct cb_node n; +}; + + +void oidtree_insert (struct oidtree *ot,const struct object_id *oid)
oidtree.c line 41
Quoted 10 lines
oidtree.c new file +10
-0+{ +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'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:120SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior hash.h:277:14 in
oidtree.c line 49
Quoted 8 lines
oidtree.c new file +8
-0+ +/* +* 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)); +} +
ATB,
Andrzej
Re: [PATCH v2 5/5] oidtree: a crit-bit tree for odb_loose_cache
Am 06.08.21 um 17:31 schrieb Andrzej Hunt:
Quoted 50 lines · Eric Wong
Quoted 23 lines
[...snip...]
oidtree.c new file +15
-0@@ -0,0 +1,94 @@ +/* +* A wrapper around cbtree which stores oids +* May be used to replace oid-array for prefix (abbreviation) matches +*/ +#include "oidtree.h" +#include "alloc.h" +#include "hash.h" + +struct oidtree_node { + /* n.k[] is used to store "struct object_id" */ + struct cb_node n; +}; + + +void oidtree_insert (struct oidtree *ot,const struct object_id *oid)oidtree.c
Quoted 10 lines
oidtree.c new file +10
-0+{ + 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_idcast 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 "structobject_id*", and later try to access object_id.hash withinoidcpy_with_padding. My compiler assumes that anobject_idpointer 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?)
Quoted 7 lines
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.charder 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.
--- object-file.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
object-file.c +1 -1
@@ -2474,7 +2474,7 @@ struct oidtree *odb_loose_cache(struct object_directory *odb,struct strbuf buf =STRBUF_INIT ;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); +size_t mask =1u << (subdir_nr % word_bits);uint32_t *bitmap; if (subdir_nr < 0 ||
--
2.32.0
Re: [PATCH v2 5/5] oidtree: a crit-bit tree for odb_loose_cache
Quoted 40 lines · René Scharfe
Am 06.08.21 um 17:31 schrieb Andrzej Hunt:
Quoted 39 lines · Eric Wong
Quoted 15 lines
[...snip...]
oidtree.c new file +7
-0+struct oidtree_node { + /* n.k[] is used to store "struct object_id" */ + struct cb_node n; +}; + + +void oidtree_insert (struct oidtree *ot,const struct object_id *oid)oidtree.c
Quoted 10 lines
oidtree.c new file +10
-0+{ + 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_idcast 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 "structobject_id*", and later try to access object_id.hash withinoidcpy_with_padding. My compiler assumes that anobject_idpointer 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 10 lines
Quoted 7 lines
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.charder 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.
Quoted 3 lines
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).
Quoted 3 lines
This breaks notes, though.
ItsGET_PTR_TYPEseems to require structleaf_nodeto 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.
Quoted 2 lines
Anyway, with either of these fixes UBSan is still unhappy about a different issue. Here's a patch for that:
Thanks <snip>
Re: [PATCH v2 5/5] oidtree: a crit-bit tree for odb_loose_cache
Quoted 43 lines · Eric Wong
Quoted 40 lines · René Scharfe
Am 06.08.21 um 17:31 schrieb Andrzej Hunt:
Quoted 39 lines · Eric Wong
Quoted 15 lines
[...snip...]
oidtree.c new file +7
-0+struct oidtree_node { +/* n.k[] is used to store "struct object_id" */ +struct cb_node n; +}; + + +void oidtree_insert (struct oidtree *ot,const struct object_id *oid)oidtree.c
Quoted 10 lines
oidtree.c new file +10
-0+{ +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_idcast 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 "structobject_id*", and later try to access object_id.hash withinoidcpy_with_padding. My compiler assumes that anobject_idpointer 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?)
Quoted 3 lines
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
cover pedantic errors in next
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(-)
Signature · 1 line
2.33.0.rc1.373.gc715f1a457
PATCH 1/3 oidtree: avoid nested struct oidtree_node
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.
--- oidtree.c | 11 +++-------- 1 file changed, 3 insertions(+), 8 deletions(-)
oidtree.c +3 -8
@@ -6,11 +6,6 @@#include "alloc.h" #include "hash.h" -struct oidtree_node { -/* n.k[] is used to store "struct object_id" */ -struct cb_node n; -}; -struct oidtree_iter_data {oidtree_iter fn;void *arg;
@@ -35,13 +30,13 @@ void oidtree_clear(struct oidtree *ot)void oidtree_insert (struct oidtree *ot,const struct object_id *oid) { -struct oidtree_node *on; +struct cb_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 ((struct object_id *)on->n.k, oid); +oidcpy_with_padding ((struct object_id *)on->k, oid);/* * n.b. Current callers won't get us duplicates, here. If a
@@ -49,7 +44,7 @@ void oidtree_insert(struct oidtree *ot, const struct object_id *oid)* that won't be freed until oidtree_clear. Currently it's not * worth maintaining a free list */ -cb_insert (&ot->tree, &on->n,sizeof (*oid)); +cb_insert (&ot->tree, on,sizeof (*oid)); }
Signature · 1 line
2.33.0.rc1.373.gc715f1a457
PATCH 2/3 object-store: avoid extra ';' from KHASH_INIT
In reply to Carlo Marcelo Arenas Belóncf2dc1c238 (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.
--- object-store.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
object-store.h +1 -1
@@ -34,7 +34,7 @@ struct object_directory { }; KHASH_INIT(odb_path_map, const char * /* key: odb_path */, - struct object_directory *, 1, fspathhash, fspatheq); + struct object_directory *, 1, fspathhash, fspatheq)void prepare_alt_odb (struct repository *r);char *compute_alternate_path (const char *path,struct strbuf *err);
Signature · 1 line
2.33.0.rc1.373.gc715f1a457
Re: [PATCH/RFC 2/3] object-store: avoid extra ';' from KHASH_INIT
Quoted 9 lines · Carlo Marcelo Arenas Belón
cf2dc1c238(speed upalt_odb_usable()with many alternates, 2021-07-07) introduces aKHASH_INITinvocation 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.
Thanks. I fully agree with the reasoning.
Quoted 19 lines
Signed-off-by Carlo Marcelo Arenas Belón <[email protected]>--- object-store.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)object-store.h +1
-1@@ -34,7 +34,7 @@ struct object_directory { }; KHASH_INIT(odb_path_map, const char * /* key: odb_path */, - struct object_directory *, 1, fspathhash, fspatheq); + struct object_directory *, 1, fspathhash, fspatheq)void prepare_alt_odb (struct repository *r);char *compute_alternate_path (const char *path,struct strbuf *err);
PATCH 3/3 ci: run a pedantic build as part of the GitHub workflow
In reply to Carlo Marcelo Arenas Belónsimilar 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.
--- .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(-)
.github/workflows/main.yml +2 -0
@@ -259,6 +259,8 @@ jobs: image: alpine - jobname: Linux32 image: daald/ubuntu32:xenial + - jobname: pedantic + image: fedora env: jobname: ${{matrix.vector.jobname}} runs-on: ubuntu-latest
ci/install-docker-dependencies.sh +4 -0
@@ -15,4 +15,8 @@ linux-musl) apk add --update build-base curl-dev openssl-dev expat-dev gettext \ pcre2-dev python3 musl-libintl perl-utils ncurses >/dev/null ;; +pedantic) + dnf -yq update >/dev/null && + dnf -yq install make gcc findutils diffutils perl python3 gettext zlib-devel expat-devel openssl-devel curl-devel pcre2-devel >/dev/null + ;; esac
ci/run-build-and-tests.sh +7 -3
@@ -10,6 +10,11 @@ windows*) cmd //c mklink //j t\\.prove "$(cygpath -aw "$cache_dir/.prove")";; *) ln -s "$cache_dir/.prove" t/.prove;; esac +if test "$jobname" = "pedantic" +then + export DEVOPTS=pedantic +fi + make case "$jobname" in linux-gcc)
@@ -35,10 +40,9 @@ linux-clang) export GIT_TEST_DEFAULT_HASH=sha256 make test ;; -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
Signature · 1 line
2.33.0.rc1.373.gc715f1a457
Re: [PATCH/RFC 3/3] ci: run a pedantic build as part of the GitHub workflow
Quoted 6 lines · Carlo Marcelo Arenas Belón
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
Signature · 1 line
An old man doll... just what I always wanted! - Clara
Re: [PATCH/RFC 3/3] ci: run a pedantic build as part of the GitHub workflow
Quoted 7 lines · Bagas Sanjaya
Quoted 2 lines · Carlo Marcelo Arenas Belón
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-pedanticis 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.
Quoted 2 lines
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"
Quoted 6 lines
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
Re: [PATCH/RFC 3/3] ci: run a pedantic build as part of the GitHub workflow
In reply to Carlo Marcelo Arenas BelónHi Carlo
Quoted 5 lines · Carlo Marcelo Arenas Belón
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/[email protected]/
[2] https://lore.kernel.org/git/[email protected]/
Quoted 63 lines
Signed-off-by Carlo Marcelo Arenas Belón <[email protected]>--- .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(-).github/workflows/main.yml +2
-0@@ -259,6 +259,8 @@ jobs: image: alpine - jobname: Linux32 image: daald/ubuntu32:xenial + - jobname: pedantic + image: fedora env: jobname: ${{matrix.vector.jobname}} runs-on: ubuntu-latestci/install-docker-dependencies.sh +4
-0@@ -15,4 +15,8 @@ linux-musl) apk add --update build-base curl-dev openssl-dev expat-dev gettext \ pcre2-dev python3 musl-libintl perl-utils ncurses >/dev/null ;; +pedantic) + dnf -yq update >/dev/null && + dnf -yq install make gcc findutils diffutils perl python3 gettext zlib-devel expat-devel openssl-devel curl-devel pcre2-devel >/dev/null + ;; esacci/run-build-and-tests.sh +7
-3@@ -10,6 +10,11 @@ windows*) cmd //c mklink //j t\\.prove "$(cygpath -aw "$cache_dir/.prove")";; *) ln -s "$cache_dir/.prove" t/.prove;; esac +if test "$jobname" = "pedantic" +then + export DEVOPTS=pedantic +fi + make case "$jobname" in linux-gcc)@@ -35,10 +40,9 @@ linux-clang) export GIT_TEST_DEFAULT_HASH=sha256 make test ;; -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
Re: [PATCH/RFC 3/3] ci: run a pedantic build as part of the GitHub workflow
Quoted 3 lines · Phillip Wood
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
Re: [PATCH/RFC 3/3] ci: run a pedantic build as part of the GitHub workflow
Quoted 10 lines · Carlo Arenas
Quoted 3 lines · Phillip Wood
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.
Quoted 5 lines
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
Quoted 4 lines
Carlo
Re: [PATCH/RFC 3/3] ci: run a pedantic build as part of the GitHub workflow
Quoted 3 lines · Phillip Wood
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.
Seeing https://github.com/git/git/actions/runs/1114402527 for example, I notice that we run three dockerized jobs and this one takes about 3 minutes to compile everything. The other two take about 9 minutes and compile and run tests.
Shouldn't we be running tests in this job, too? I know the new comment in ci/run-build-and-tests.sh says "Don't run the tests; we only care about ...", but I do not see a reason to declare that we do not care if the resulting binary passes the tests or not.
It also seems that the environment does not have an access to any working "git" binary and "save_good_tree" helper seems to fail because of it.
https://github.com/git/git/runs/3284998605?check_suite_focus=true#step:5:692
I wonder if this untested patch on top of the patch under discussion is sufficient, if we wanted to also run tests on the fedora image?
ci/install-docker-dependencies.sh +3 -1
@@ -17,6 +17,8 @@ linux-musl) ;; pedantic) dnf -yq update >/dev/null && - dnf -yq install make gcc findutils diffutils perl python3 gettext zlib-devel expat-devel openssl-devel curl-devel pcre2-devel >/dev/null + dnf -yq install git make gcc findutils diffutils perl python3 \ + gettext zlib-devel expat-devel openssl-devel \ + curl-devel pcre2-devel >/dev/null ;; esac
ci/run-build-and-tests.sh +3 -2
@@ -40,9 +40,10 @@ linux-clang) export GIT_TEST_DEFAULT_HASH=sha256 make test ;; -linux-gcc-4.8|pedantic) +linux-gcc-4.8) # Don't run the tests; we only care about whether Git can be - # built with GCC 4.8 or with pedantic + # built with GCC 4.8, as it errors out on some undesired (C99) + # constructs that newer compilers seem to quietly accept. ;; *) make test
Re: [PATCH/RFC 3/3] ci: run a pedantic build as part of the GitHub workflow
In reply to Phillip WoodQuoted 9 lines · Phillip Wood
Hi Carlo
Quoted 5 lines · Carlo Marcelo Arenas Belón
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.
Quoted 6 lines
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).
Re: [PATCH/RFC 3/3] ci: run a pedantic build as part of the GitHub workflow
Quoted 15 lines · Ævar Arnfjörð Bjarmason
Quoted 7 lines · Phillip Wood
Quoted 5 lines · Carlo Marcelo Arenas Belón
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.Quoted 6 lines
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.
Quoted 4 lines
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_Nissue.
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 4 lines
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
Re: [PATCH/RFC 3/3] ci: run a pedantic build as part of the GitHub workflow
Quoted 32 lines · Carlo Arenas
Quoted 15 lines · Ævar Arnfjörð Bjarmason
Quoted 7 lines · Phillip Wood
Quoted 5 lines · Carlo Marcelo Arenas Belón
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.Quoted 6 lines
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.
Quoted 4 lines
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_Nissue.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 7 lines
Quoted 4 lines
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.
Re: [PATCH/RFC 3/3] ci: run a pedantic build as part of the GitHub workflow
Quoted 3 lines · Ævar Arnfjörð Bjarmason
On the other hand maybe we should just remove
USE_PARENS_AROUND_GETTEXT_Nentirely, 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.
Quoted 2 lines
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
Re: [PATCH/RFC 3/3] ci: run a pedantic build as part of the GitHub workflow
Quoted 9 lines · Carlo Arenas
Quoted 3 lines · Ævar Arnfjörð Bjarmason
On the other hand maybe we should just remove
USE_PARENS_AROUND_GETTEXT_Nentirely, 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?
Makefile +1 -19
@@ -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
@@ -1347,14 +1337,6 @@ ifneq (,$(SOCKLEN_T)) BASIC_CFLAGS += -Dsocklen_t=$(SOCKLEN_T) endif -ifeq (yes,$(USE_PARENS_AROUND_GETTEXT_N)) - BASIC_CFLAGS += -DUSE_PARENS_AROUND_GETTEXT_N=1 -else -ifeq (no,$(USE_PARENS_AROUND_GETTEXT_N)) - BASIC_CFLAGS += -DUSE_PARENS_AROUND_GETTEXT_N=0 -endif -endif - ifeq ($(uname_S),Darwin) ifndef NO_FINK ifeq ($(shell test -d /sw/lib && echo y),y)
config.mak.dev +0 -2
@@ -4,8 +4,6 @@ SPARSE_FLAGS += -Wsparse-error endif ifneq ($(filter pedantic,$(DEVOPTS)),) DEVELOPER_CFLAGS += -pedantic -# don't warn for each N_ use -DEVELOPER_CFLAGS += -DUSE_PARENS_AROUND_GETTEXT_N=0 endif DEVELOPER_CFLAGS += -Wall DEVELOPER_CFLAGS += -Wdeclaration-after-statement
gettext.h +0 -24
@@ -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 -/* -* Strictly speaking, this will lead to invalid C when -* used this way: -* static const char s[] = N_("FOO"); -* which will expand to -* static const char s[] = ("FOO"); -* and in valid C, the initializer on the right hand side must -* be without the parentheses. But many compilers do accept it -* as a language extension and it will allow us to catch mistakes -* like: -* static const char *msgs[] = { -* N_("one") -* N_("two"), -* N_("three"), -* NULL -* }; -* (notice the missing comma on one of the lines) by forcing -* a compilation error, because parenthesised ("one") ("two") -* will not get silently turned into ("onetwo"). -*/ -#define N_ (msgid) (msgid) -#endif const char *get_preferred_languages (void );int is_utf8_locale (void );
git-compat-util.h +0 -4
@@ -1253,10 +1253,6 @@ int warn_on_fopen_errors(const char *path);*/ int open_nofollow (const char *path,int flags); -#if !defined(USE_PARENS_AROUND_GETTEXT_N ) && defined(__GNUC__) -#define USE_PARENS_AROUND_GETTEXT_N 1 -#endif -#ifndef SHELL_PATH # define SHELL_PATH "/bin/sh"#endif
Re: [PATCH/RFC 3/3] ci: run a pedantic build as part of the GitHub workflow
Quoted 12 lines · Jeff King
Quoted 9 lines · Carlo Arenas
Quoted 3 lines · Ævar Arnfjörð Bjarmason
On the other hand maybe we should just remove
USE_PARENS_AROUND_GETTEXT_Nentirely, 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)
Quoted 6 lines
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.
That does sound sensible.
Quoted 1 line
Something like this, I guess?
Looks good. We could give a warning when the now defunct knob is used, but I don't think there is anything gained by doing so (over just silently ignoring it).
Re: [PATCH/RFC 3/3] ci: run a pedantic build as part of the GitHub workflow
In reply to Carlo Marcelo Arenas Belónci/run-build-and-tests.sh linux-clang) · line 48
Quoted 9 lines · Carlo Marcelo Arenas Belón
ci/run-build-and-tests.sh +2
-3-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 <[email protected]> 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...
v2 cover developer: support pedantic
In reply to Carlo Marcelo Arenas BelónWARNING: 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/[email protected]/
[1] https://lore.kernel.org/git/[email protected]/
[2] https://lore.kernel.org/git/[email protected]/
Signature · 1 line
2.33.0.481.g26d3bed244
RFC PATCH v2 1/4 developer: retire USE_PARENS_AROUND_GETTEXT_N support
From: Jeff King <[email protected]>
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.
--- Makefile | 20 +------------------- config.mak.dev | 2 -- gettext.h | 24 ------------------------ git-compat-util.h | 4 ---- 4 files changed, 1 insertion(+), 49 deletions(-)
Makefile +1 -19
@@ -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
@@ -1347,14 +1337,6 @@ ifneq (,$(SOCKLEN_T)) BASIC_CFLAGS += -Dsocklen_t=$(SOCKLEN_T) endif -ifeq (yes,$(USE_PARENS_AROUND_GETTEXT_N)) - BASIC_CFLAGS += -DUSE_PARENS_AROUND_GETTEXT_N=1 -else -ifeq (no,$(USE_PARENS_AROUND_GETTEXT_N)) - BASIC_CFLAGS += -DUSE_PARENS_AROUND_GETTEXT_N=0 -endif -endif - ifeq ($(uname_S),Darwin) ifndef NO_FINK ifeq ($(shell test -d /sw/lib && echo y),y)
config.mak.dev +0 -2
@@ -4,8 +4,6 @@ SPARSE_FLAGS += -Wsparse-error endif ifneq ($(filter pedantic,$(DEVOPTS)),) DEVELOPER_CFLAGS += -pedantic -# don't warn for each N_ use -DEVELOPER_CFLAGS += -DUSE_PARENS_AROUND_GETTEXT_N=0 endif DEVELOPER_CFLAGS += -Wall DEVELOPER_CFLAGS += -Wdeclaration-after-statement
gettext.h +0 -24
@@ -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 -/* -* Strictly speaking, this will lead to invalid C when -* used this way: -* static const char s[] = N_("FOO"); -* which will expand to -* static const char s[] = ("FOO"); -* and in valid C, the initializer on the right hand side must -* be without the parentheses. But many compilers do accept it -* as a language extension and it will allow us to catch mistakes -* like: -* static const char *msgs[] = { -* N_("one") -* N_("two"), -* N_("three"), -* NULL -* }; -* (notice the missing comma on one of the lines) by forcing -* a compilation error, because parenthesised ("one") ("two") -* will not get silently turned into ("onetwo"). -*/ -#define N_ (msgid) (msgid) -#endif const char *get_preferred_languages (void );int is_utf8_locale (void );
git-compat-util.h +0 -4
@@ -1253,10 +1253,6 @@ int warn_on_fopen_errors(const char *path);*/ int open_nofollow (const char *path,int flags); -#if !defined(USE_PARENS_AROUND_GETTEXT_N ) && defined(__GNUC__) -#define USE_PARENS_AROUND_GETTEXT_N 1 -#endif -#ifndef SHELL_PATH # define SHELL_PATH "/bin/sh"#endif
Signature · 1 line
2.33.0.481.g26d3bed244
RFC PATCH v2 2/4 developer: enable pedantic by default
In reply to Carlo Marcelo Arenas Belónwith 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/[email protected]/
--- Makefile | 4 ++-- config.mak.dev | 3 ++- 2 files changed, 4 insertions(+), 3 deletions(-)
Makefile +2 -2
@@ -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
config.mak.dev +2 -1
@@ -2,8 +2,9 @@ ifeq ($(filter no-error,$(DEVOPTS)),) DEVELOPER_CFLAGS += -Werror SPARSE_FLAGS += -Wsparse-error endif -ifneq ($(filter pedantic,$(DEVOPTS)),) +ifeq ($(filter no-pedantic,$(DEVOPTS)),) DEVELOPER_CFLAGS += -pedantic +DEVELOPER_CFLAGS += -Wpedantic endif DEVELOPER_CFLAGS += -Wall DEVELOPER_CFLAGS += -Wdeclaration-after-statement
Signature · 1 line
2.33.0.481.g26d3bed244
RFC PATCH v2 3/4 developer: add an alternative script for detecting broken N_()
In reply to Carlo Marcelo Arenas Belónobviously 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.
--- .../find_accidentally_concat_i18n_strings.pl | 69 +++++++++++++++++++ 1 file changed, 69 insertions(+) create mode 100755 devtools/find_accidentally_concat_i18n_strings.pl
devtools/find_accidentally_concat_i18n_strings.pl new file +69 -0
@@ -0,0 +1,69 @@ +#!/usr/bin/perl + +# +# find .. \( -name "*.c" -o -name "*.h" \) -exec ./find_accidentally_concat_i18n_strings.pl {} \; +# +# this will help find places in the code that might have strings that +# are marked for translation but are not correctly separated, causing +# problems like the one reported in : +# +# https://lore.kernel.org/git/ecb18f9d6ac56da0a61c3b98f8f2236@74d39fa044aa309eaea14b9f57fe79c/ +# + +use strict; +use warnings; + +my $myself = $0; +my $file = $ARGV[0]; +my $errors = 0; +my $key; + +chomp(my @exceptions = <DATA>); + +sub ask { + local $| = 1; + print "possible bug found in $key:\n"; + print "\n$&\n"; + print "\nadd exception (y/N): "; + chomp(my $answer = <STDIN>); + if (lc($answer) ne 'y') { + ++$errors; + return; + } + return 1; +} + +sub process_file { + my $content; + open(my $fh, '<', $file) or die; + { + local $/; + $content = <$fh>; + } + close($fh); + while ($content =~ /N_\(.*?\)[ \t\n]+N_\(.*?\)/g) { + my $index = length($`); + $key = "$file:$index"; + if (!grep {/^$key$/} @exceptions) { + push @exceptions, $key if ask(); + } + } +} + +&process_file; + +{ + local *MYSELF; + local $/ = "\n__END__"; + open (MYSELF, $myself); + chomp(my $file = <MYSELF>); + close MYSELF; + open (MYSELF, ">$myself") || die "can't update myself"; + print MYSELF $file, "\n__END__\n"; + foreach (@exceptions) { + print MYSELF "$_\n"; + } + close MYSELF; +} +exit($errors); +__END__
Signature · 1 line
2.33.0.481.g26d3bed244
RFC PATCH v2 4/4 developer: move detect-compiler out of the main directory
In reply to Carlo Marcelo Arenas Belónas 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/[email protected]/
--- config.mak.dev | 2 +- detect-compiler => devtools/detect-compiler | 0 2 files changed, 1 insertion(+), 1 deletion(-) rename detect-compiler => devtools/detect-compiler (100%)
config.mak.dev +1 -1
@@ -18,7 +18,7 @@ DEVELOPER_CFLAGS += -Wvla DEVELOPER_CFLAGS += -fno-common ifndef COMPILER_FEATURES -COMPILER_FEATURES := $(shell ./detect-compiler $(CC)) +COMPILER_FEATURES := $(shell ./devtools/detect-compiler $(CC)) endif ifneq ($(filter clang4,$(COMPILER_FEATURES)),)
devtools/detect-compiler renamed from detect-compiler +0 -0
Signature · 1 line
2.33.0.481.g26d3bed244
Re: [RFC PATCH v2 0/4] developer: support pedantic
In reply to Carlo Marcelo Arenas BelónQuoted 4 lines · Carlo Marcelo Arenas Belón
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 3 lines
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_Nare 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
PATCH 1/1 gettext: remove optional non-standard parens in N_() definition
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.
---
Quoted 17 lines · Jeff King
Quoted 4 lines · Carlo Marcelo Arenas Belón
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 3 lines
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_Nare addressed.
Quoted 6 lines
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 <[email protected]> (the patch content is the same) but before seeing that Carlo had beaten me to it here in <[email protected]> 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(-)
Makefile +1 -19
@@ -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
@@ -1347,14 +1337,6 @@ ifneq (,$(SOCKLEN_T)) BASIC_CFLAGS += -Dsocklen_t=$(SOCKLEN_T) endif -ifeq (yes,$(USE_PARENS_AROUND_GETTEXT_N)) - BASIC_CFLAGS += -DUSE_PARENS_AROUND_GETTEXT_N=1 -else -ifeq (no,$(USE_PARENS_AROUND_GETTEXT_N)) - BASIC_CFLAGS += -DUSE_PARENS_AROUND_GETTEXT_N=0 -endif -endif - ifeq ($(uname_S),Darwin) ifndef NO_FINK ifeq ($(shell test -d /sw/lib && echo y),y)
config.mak.dev +0 -2
@@ -4,8 +4,6 @@ SPARSE_FLAGS += -Wsparse-error endif ifneq ($(filter pedantic,$(DEVOPTS)),) DEVELOPER_CFLAGS += -pedantic -# don't warn for each N_ use -DEVELOPER_CFLAGS += -DUSE_PARENS_AROUND_GETTEXT_N=0 endif DEVELOPER_CFLAGS += -Wall DEVELOPER_CFLAGS += -Wdeclaration-after-statement
gettext.h +0 -24
@@ -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 -/* -* Strictly speaking, this will lead to invalid C when -* used this way: -* static const char s[] = N_("FOO"); -* which will expand to -* static const char s[] = ("FOO"); -* and in valid C, the initializer on the right hand side must -* be without the parentheses. But many compilers do accept it -* as a language extension and it will allow us to catch mistakes -* like: -* static const char *msgs[] = { -* N_("one") -* N_("two"), -* N_("three"), -* NULL -* }; -* (notice the missing comma on one of the lines) by forcing -* a compilation error, because parenthesised ("one") ("two") -* will not get silently turned into ("onetwo"). -*/ -#define N_ (msgid) (msgid) -#endif const char *get_preferred_languages (void );int is_utf8_locale (void );
git-compat-util.h +0 -4
@@ -1253,10 +1253,6 @@ int warn_on_fopen_errors(const char *path);*/ int open_nofollow (const char *path,int flags); -#if !defined(USE_PARENS_AROUND_GETTEXT_N ) && defined(__GNUC__) -#define USE_PARENS_AROUND_GETTEXT_N 1 -#endif -#ifndef SHELL_PATH # define SHELL_PATH "/bin/sh"#endif
Signature · 1 line
2.33.0.807.gf14ecf9c2e9
Re: [PATCH] gettext: remove optional non-standard parens in N_() definition
Quoted 6 lines · Ævar Arnfjörð Bjarmason
[...]
Then ine62cd35a3e8(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 tousage()added in1c370ea4e51(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..."
Re: [PATCH] gettext: remove optional non-standard parens in N_() definition
In reply to Ævar Arnfjörð BjarmasonQuoted 5 lines · Ævar Arnfjörð Bjarmason
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):
Quoted 3 lines
Remove the
USE_PARENS_AROUND_GETTEXT_Ncompile-time option which was meant to catch an inadvertent mistakes which is too obscure to maintain this facility.
s/mistakes/mistake/
-Peff
Re: [PATCH] gettext: remove optional non-standard parens in N_() definition
In reply to Ævar Arnfjörð BjarmasonQuoted 9 lines · Ævar Arnfjörð Bjarmason
Remove the
USE_PARENS_AROUND_GETTEXT_Ncompile-time option which was meant to catch an inadvertent mistakes which is too obscure to maintain this facility.
...
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 this goes in the right direction, and I'd rather not to have to handle too many multi-patch topics in which one step takes hostage the other steps.
Thanks, all.
Re: [RFC PATCH v2 0/4] developer: support pedantic
In reply to Jeff King[I should have included this in my just-sent [1], but forgot]
Quoted 17 lines · Jeff King
Quoted 4 lines · Carlo Marcelo Arenas Belón
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 3 lines
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_Nare addressed.
Quoted 6 lines
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/[email protected]
2. https://lore.kernel.org/git/[email protected]
Re: [RFC PATCH v2 0/4] developer: support pedantic
Quoted 5 lines · Ævar Arnfjörð Bjarmason
Quoted 2 lines · Jeff King
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 6 lines
Quoted 6 lines
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
Quoted 9 lines
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.ccould do some basic sanity checking on the usage array it takes, we'd then end up detecting the issueUSE_PARENS_AROUND_GETTEXT_Nwas 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
v3 cover support pedantic in developer mode
In reply to Carlo Marcelo Arenas BelónThis 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/[email protected]/
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
PATCH v3 1/3 gettext: remove optional non-standard parens in N_() definition
From: Ævar Arnfjörð Bjarmason <[email protected]>
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.
--- Makefile | 20 +------------------- config.mak.dev | 2 -- gettext.h | 24 ------------------------ git-compat-util.h | 4 ---- 4 files changed, 1 insertion(+), 49 deletions(-)
Makefile +1 -19
@@ -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
@@ -1347,14 +1337,6 @@ ifneq (,$(SOCKLEN_T)) BASIC_CFLAGS += -Dsocklen_t=$(SOCKLEN_T) endif -ifeq (yes,$(USE_PARENS_AROUND_GETTEXT_N)) - BASIC_CFLAGS += -DUSE_PARENS_AROUND_GETTEXT_N=1 -else -ifeq (no,$(USE_PARENS_AROUND_GETTEXT_N)) - BASIC_CFLAGS += -DUSE_PARENS_AROUND_GETTEXT_N=0 -endif -endif - ifeq ($(uname_S),Darwin) ifndef NO_FINK ifeq ($(shell test -d /sw/lib && echo y),y)
config.mak.dev +0 -2
@@ -4,8 +4,6 @@ SPARSE_FLAGS += -Wsparse-error endif ifneq ($(filter pedantic,$(DEVOPTS)),) DEVELOPER_CFLAGS += -pedantic -# don't warn for each N_ use -DEVELOPER_CFLAGS += -DUSE_PARENS_AROUND_GETTEXT_N=0 endif DEVELOPER_CFLAGS += -Wall DEVELOPER_CFLAGS += -Wdeclaration-after-statement
gettext.h +0 -24
@@ -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 -/* -* Strictly speaking, this will lead to invalid C when -* used this way: -* static const char s[] = N_("FOO"); -* which will expand to -* static const char s[] = ("FOO"); -* and in valid C, the initializer on the right hand side must -* be without the parentheses. But many compilers do accept it -* as a language extension and it will allow us to catch mistakes -* like: -* static const char *msgs[] = { -* N_("one") -* N_("two"), -* N_("three"), -* NULL -* }; -* (notice the missing comma on one of the lines) by forcing -* a compilation error, because parenthesised ("one") ("two") -* will not get silently turned into ("onetwo"). -*/ -#define N_ (msgid) (msgid) -#endif const char *get_preferred_languages (void );int is_utf8_locale (void );
git-compat-util.h +0 -4
@@ -1253,10 +1253,6 @@ int warn_on_fopen_errors(const char *path);*/ int open_nofollow (const char *path,int flags); -#if !defined(USE_PARENS_AROUND_GETTEXT_N ) && defined(__GNUC__) -#define USE_PARENS_AROUND_GETTEXT_N 1 -#endif -#ifndef SHELL_PATH # define SHELL_PATH "/bin/sh"#endif
Signature · 1 line
2.33.0.481.g26d3bed244
Re: [PATCH v3 1/3] gettext: remove optional non-standard parens in N_() definition
Quoted 157 lines · Carlo Marcelo Arenas Belón
From: Ævar Arnfjörð Bjarmason <[email protected]>
Remove the
USE_PARENS_AROUND_GETTEXT_Ncompile-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_Ncame about is: When I added theN_()macro in 65784830366 (i18n: add no-op_()andN_()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) msgidThen 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 tousage()added in1c370ea4e51(Show usage string for 'git log -h', 'git show -h' and 'git diff -h', 2009-08-06) was faithfully preserved:(quoted diff) +2
-2- "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 in290c8e7a3fe(gettext.h: add parentheses around N_ expansion if supported, 2015-01-11)USE_PARENS_AROUND_GETTEXT_Nwas 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_Nfacility wouldn't be worth it, the issue would be too rare to worry about.But I also think that
290c8e7a3fewhich introducedUSE_PARENS_AROUND_GETTEXT_Nmisattributed the problem. The issue wasn't with theN_()macro added ine62cd35a3e8, but that before theN_()macro existed in the codebase the initial migration toparse_options()in1c370ea4e51continued 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 <[email protected]>Signed-off-by Ævar Arnfjörð Bjarmason <[email protected]>Signed-off-by Carlo Marcelo Arenas Belón <[email protected]>--- Makefile | 20 +------------------- config.mak.dev | 2 -- gettext.h | 24 ------------------------ git-compat-util.h | 4 ---- 4 files changed, 1 insertion(+), 49 deletions(-)Makefile +1
-19@@ -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@@ -1347,14 +1337,6 @@ ifneq (,$(SOCKLEN_T)) BASIC_CFLAGS += -Dsocklen_t=$(SOCKLEN_T) endif -ifeq (yes,$(USE_PARENS_AROUND_GETTEXT_N)) - BASIC_CFLAGS += -DUSE_PARENS_AROUND_GETTEXT_N=1 -else -ifeq (no,$(USE_PARENS_AROUND_GETTEXT_N)) - BASIC_CFLAGS += -DUSE_PARENS_AROUND_GETTEXT_N=0 -endif -endif - ifeq ($(uname_S),Darwin) ifndef NO_FINK ifeq ($(shell test -d /sw/lib && echo y),y)config.mak.dev +0
-2@@ -4,8 +4,6 @@ SPARSE_FLAGS += -Wsparse-error endif ifneq ($(filter pedantic,$(DEVOPTS)),) DEVELOPER_CFLAGS += -pedantic -# don't warn for each N_ use -DEVELOPER_CFLAGS += -DUSE_PARENS_AROUND_GETTEXT_N=0 endif DEVELOPER_CFLAGS += -Wall DEVELOPER_CFLAGS += -Wdeclaration-after-statementgettext.h +0
-24@@ -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 -/* -* Strictly speaking, this will lead to invalid C when -* used this way: -* static const char s[] = N_("FOO"); -* which will expand to -* static const char s[] = ("FOO"); -* and in valid C, the initializer on the right hand side must -* be without the parentheses. But many compilers do accept it -* as a language extension and it will allow us to catch mistakes -* like: -* static const char *msgs[] = { -* N_("one") -* N_("two"), -* N_("three"), -* NULL -* }; -* (notice the missing comma on one of the lines) by forcing -* a compilation error, because parenthesised ("one") ("two") -* will not get silently turned into ("onetwo"). -*/ -#define N_ (msgid) (msgid) -#endif const char *get_preferred_languages (void );int is_utf8_locale (void );git-compat-util.h +0
-0
git-compat-util.h int warn_on_fopen_errors(const char *path); · line 1258
Quoted 10 lines
git-compat-util.h +0
-4@@ -1253,10 +1253,6 @@ int warn_on_fopen_errors(const char *path);*/ int open_nofollow (const char *path,int flags); -#if !defined(USE_PARENS_AROUND_GETTEXT_N ) && defined(__GNUC__) -#define USE_PARENS_AROUND_GETTEXT_N 1 -#endif -#ifndef SHELL_PATH # define SHELL_PATH "/bin/sh"#endif
A note & cross-link: I've submitted a v2 of another series where we'll effectively duplicate the check being removed here, see
https://lore.kernel.org/git/[email protected]/
Well, it's not a general N_() multi-line checker like the proposed
https://lore.kernel.org/git/[email protected]/
and this USE_PARENS_AROUND_GETTEXT_N, but we added USE_PARENS_AROUND_GETTEXT_N to begin with for these usage strings. The bad usage of that usage API (phew!, that's a mouthful) will be caught by that usage CAPI being stricter now.
PATCH v3 2/3 win32: allow building with pedantic mode enabled
In reply to Carlo Marcelo Arenas BelónIn 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.
---
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(-)
compat/nedmalloc/nedmalloc.c +1 -1
@@ -510,7 +510,7 @@ static void threadcache_free(nedpool *p, threadcache *tc, int mymspace, void *meassert (idx<=THREADCACHEMAXBINS );if (tck==*binsptr) { -fprintf (stderr,"Attempt to free already freed memory block %p - aborting!\n" , tck); +fprintf (stderr,"Attempt to free already freed memory block %p - aborting!\n" , (void *)tck);abort (); }#ifdef FULLSANITYCHECKS
compat/win32/lazyload.h +1 -1
@@ -37,7 +37,7 @@ struct proc_addr {#define INIT_PROC_ADDR (function) \ (function = get_proc_addr(&proc_addr_##function)) -static inline void *get_proc_addr (struct proc_addr *proc) +static inline FARPROC get_proc_addr (struct proc_addr *proc) {/* only do this once */ if (!proc->initialized) {
config.mak.dev +8 -5
@@ -1,11 +1,18 @@ +ifndef COMPILER_FEATURES +COMPILER_FEATURES := $(shell ./detect-compiler $(CC)) +endif + ifeq ($(filter no-error,$(DEVOPTS)),) DEVELOPER_CFLAGS += -Werror SPARSE_FLAGS += -Wsparse-error endif +DEVELOPER_CFLAGS += -Wall ifneq ($(filter pedantic,$(DEVOPTS)),) DEVELOPER_CFLAGS += -pedantic +ifneq ($(filter gcc5,$(COMPILER_FEATURES)),) +DEVELOPER_CFLAGS += -Wno-incompatible-pointer-types +endif endif -DEVELOPER_CFLAGS += -Wall DEVELOPER_CFLAGS += -Wdeclaration-after-statement DEVELOPER_CFLAGS += -Wformat-security DEVELOPER_CFLAGS += -Wold-style-definition
@@ -16,10 +23,6 @@ DEVELOPER_CFLAGS += -Wunused DEVELOPER_CFLAGS += -Wvla DEVELOPER_CFLAGS += -fno-common -ifndef COMPILER_FEATURES -COMPILER_FEATURES := $(shell ./detect-compiler $(CC)) -endif - ifneq ($(filter clang4,$(COMPILER_FEATURES)),) DEVELOPER_CFLAGS += -Wtautological-constant-out-of-range-compare endif
Signature · 1 line
2.33.0.481.g26d3bed244
Re: [PATCH v3 2/3] win32: allow building with pedantic mode enabled
Am 03.09.21 um 19:02 schrieb Carlo Marcelo Arenas Belón:
Quoted 27 lines
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 <[email protected]>---
This is all that is needed to build cleanly once merged to maint/master/nextThere 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(-)compat/nedmalloc/nedmalloc.c +0
-0
compat/nedmalloc/nedmalloc.c static void threadcache_free(nedpool *p, threadcache *tc, int mymspace, void *me · line 513
Quoted 5 lines
compat/nedmalloc/nedmalloc.c +1
-1@@ -510,7 +510,7 @@ static void threadcache_free(nedpool *p, threadcache *tc, int mymspace, void *meassert (idx<=THREADCACHEMAXBINS );if (tck==*binsptr) { -fprintf (stderr,"Attempt to free already freed memory block %p - aborting!\n" , tck); +fprintf (stderr,"Attempt to free already freed memory block %p - aborting!\n" , (void *)tck);
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é
Re: [PATCH v3 2/3] win32: allow building with pedantic mode enabled
Quoted 13 lines · René Scharfe
Am 03.09.21 um 19:02 schrieb Carlo Marcelo Arenas Belón:
compat/nedmalloc/nedmalloc.c static void threadcache_free(nedpool *p, threadcache *tc, int mymspace, void *me · line 513
Quoted 10 lines
compat/nedmalloc/nedmalloc.c +1
-1@@ -510,7 +510,7 @@ static void threadcache_free(nedpool *p, threadcache *tc, int mymspace, void *meassert (idx<=THREADCACHEMAXBINS );if (tck==*binsptr) { -fprintf (stderr,"Attempt to free already freed memory block %p - aborting!\n" , tck); +fprintf (stderr,"Attempt to free already freed memory block %p - aborting!\n" , (void *)tck);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 6 lines
compat/nedmalloc/nedmalloc.c:513:82: error: format specifies type 'void *' but the argument has type 'threadcacheblk *' (aka 'structthreadcacheblk_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.
Quoted 2 lines
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 ----
compat/nedmalloc/nedmalloc.c +9 -1
@@ -510,7 +510,15 @@ static void threadcache_free(nedpool *p, threadcache *tc, int mymspace, void *meassert (idx<=THREADCACHEMAXBINS );if (tck==*binsptr) { -fprintf (stderr,"Attempt to free already freed memory block %p - aborting!\n" , (void *)tck); +/* +* Original code used tck instead of mem, but that was changed +* to workaround a pedantic warning from mingw64 gcc 10.3 that +* requires %p to have a explicit (void *) as a parameter. +* +* This might seem to be a compiler bug or limitation that +* should be changed back if fixed for maintanability. +*/ +fprintf (stderr,"Attempt to free already freed memory block %p - aborting!\n" , mem);abort (); }#ifdef FULLSANITYCHECKS
Re: [PATCH v3 2/3] win32: allow building with pedantic mode enabled
Quoted 17 lines · Carlo Marcelo Arenas Belón
Quoted 2 lines
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 ----compat/nedmalloc/nedmalloc.c +1
-1@@ -510,7 +510,15 @@ static void threadcache_free(nedpool *p, threadcache *tc, int mymspace, void *meassert (idx<=THREADCACHEMAXBINS );if (tck==*binsptr) { -fprintf (stderr,"Attempt to free already freed memory block %p - aborting!\n" , (void *)tck); +/*
compat/nedmalloc/nedmalloc.c static void threadcache_free(nedpool *p, threadcache *tc, int mymspace, void *me · line 523
Quoted 10 lines
compat/nedmalloc/nedmalloc.c +8
-0+* Original code used tck instead of mem, but that was changed +* to workaround a pedantic warning from mingw64 gcc 10.3 that +* requires %p to have a explicit (void *) as a parameter. +* +* This might seem to be a compiler bug or limitation that +* should be changed back if fixed for maintanability. +*/ +fprintf (stderr,"Attempt to free already freed memory block %p - aborting!\n" , mem);abort (); }
The new comment explains why the original (i.e. unadorned 'tck'), which should work fine, needs to be changed. The reason is because a version of compiler wants an explict (void *) cast to go with the placeholder "%p".
Given that, it would be much better to pass (void *)tck instead of mem, no? Especially since the comment does not say tck and mem have the same pointer value.
Having said lal that, I have to wonder if how much help the developer who is hunting for allocation bug is getting out of a raw pointer value in this message, though.
Re: [PATCH v3 2/3] win32: allow building with pedantic mode enabled
In reply to Carlo Marcelo Arenas BelónAm 03.09.21 um 22:13 schrieb Carlo Marcelo Arenas Belón:
Quoted 30 lines · René Scharfe
Quoted 13 lines
Am 03.09.21 um 19:02 schrieb Carlo Marcelo Arenas Belón:
compat/nedmalloc/nedmalloc.c static void threadcache_free(nedpool *p, threadcache *tc, int mymspace, void *me · line 513
Quoted 10 lines
compat/nedmalloc/nedmalloc.c +1
-1@@ -510,7 +510,7 @@ static void threadcache_free(nedpool *p, threadcache *tc, int mymspace, void *meassert (idx<=THREADCACHEMAXBINS );if (tck==*binsptr) { -fprintf (stderr,"Attempt to free already freed memory block %p - aborting!\n" , tck); +fprintf (stderr,"Attempt to free already freed memory block %p - aborting!\n" , (void *)tck);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 6 lines
compat/nedmalloc/nedmalloc.c:513:82: error: format specifies type 'void *' but the argument has type 'threadcacheblk *' (aka 'structthreadcacheblk_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 'structthreadcacheblk_t*'} [-Wformat=]
Quoted 8 lines
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.
Quoted 7 lines
clang 14 does also trigger a warning, so IMHO this code will be needed until nedmalloc is retired.
Quoted 2 lines
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..
Quoted 25 lines
Carlo
---- > 8 ----compat/nedmalloc/nedmalloc.c +9
-1@@ -510,7 +510,15 @@ static void threadcache_free(nedpool *p, threadcache *tc, int mymspace, void *meassert (idx<=THREADCACHEMAXBINS );if (tck==*binsptr) { -fprintf (stderr,"Attempt to free already freed memory block %p - aborting!\n" , (void *)tck); +/* +* Original code used tck instead of mem, but that was changed +* to workaround a pedantic warning from mingw64 gcc 10.3 that +* requires %p to have a explicit (void *) as a parameter. +* +* This might seem to be a compiler bug or limitation that +* should be changed back if fixed for maintanability. +*/ +fprintf (stderr,"Attempt to free already freed memory block %p - aborting!\n" , mem);abort (); }#ifdef FULLSANITYCHECKS
Re: [PATCH v3 2/3] win32: allow building with pedantic mode enabled
Am 03.09.21 um 22:38 schrieb René Scharfe:
Quoted 19 lines
Am 03.09.21 um 22:13 schrieb Carlo Marcelo Arenas Belón:
Quoted 18 lines · René Scharfe
Quoted 13 lines
Am 03.09.21 um 19:02 schrieb Carlo Marcelo Arenas Belón:
compat/nedmalloc/nedmalloc.c static void threadcache_free(nedpool *p, threadcache *tc, int mymspace, void *me · line 513
Quoted 10 lines
compat/nedmalloc/nedmalloc.c +1
-1@@ -510,7 +510,7 @@ static void threadcache_free(nedpool *p, threadcache *tc, int mymspace, void *meassert (idx<=THREADCACHEMAXBINS );if (tck==*binsptr) { -fprintf (stderr,"Attempt to free already freed memory block %p - aborting!\n" , tck); +fprintf (stderr,"Attempt to free already freed memory block %p - aborting!\n" , (void *)tck);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 8 lines
Quoted 8 lines
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 'structthreadcacheblk_t*'} [-Wformat=]522 | fprintf(stderr, "Attempt to free already freed memory block %p - aborting!\n", tck); | ~^ ~~~ | | | | void * threadcacheblk * {aka struct threadcacheblk_t *}
I don't have GCC installed, only checked with https://godbolt.org/z/jc356vqb4
René
Re: [PATCH v3 2/3] win32: allow building with pedantic mode enabled
Quoted 22 lines · René Scharfe
Am 03.09.21 um 22:38 schrieb René Scharfe:
Quoted 19 lines
Am 03.09.21 um 22:13 schrieb Carlo Marcelo Arenas Belón:
Quoted 18 lines · René Scharfe
Quoted 13 lines
Am 03.09.21 um 19:02 schrieb Carlo Marcelo Arenas Belón:
compat/nedmalloc/nedmalloc.c static void threadcache_free(nedpool *p, threadcache *tc, int mymspace, void *me · line 513
Quoted 10 lines
compat/nedmalloc/nedmalloc.c +1
-1@@ -510,7 +510,7 @@ static void threadcache_free(nedpool *p, threadcache *tc, int mymspace, void *meassert (idx<=THREADCACHEMAXBINS );if (tck==*binsptr) { -fprintf (stderr,"Attempt to free already freed memory block %p - aborting!\n" , tck); +fprintf (stderr,"Attempt to free already freed memory block %p - aborting!\n" , (void *)tck);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 6 lines
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
Re: [PATCH v3 2/3] win32: allow building with pedantic mode enabled
In reply to Carlo Marcelo Arenas Belónconfig.mak.dev line 14
Quoted 3 lines
config.mak.dev +3
-0+ifneq ($(filter gcc5,$(COMPILER_FEATURES)),) +DEVELOPER_CFLAGS += -Wno-incompatible-pointer-types +endif
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.
Re: [PATCH v3 2/3] win32: allow building with pedantic mode enabled
Quoted 9 lines · Jonathan Tan
config.mak.dev line 14
Quoted 4 lines
config.mak.dev +3
-0+ifneq ($(filter gcc5,$(COMPILER_FEATURES)),) +DEVELOPER_CFLAGS += -Wno-incompatible-pointer-types +endifI 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]
Quoted 4 lines
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.
Correct; it was only needed in Windows, will narrow it further.
Carlo
[1] https://github.com/gitster/git/tree/js/win-lazyload-buildfix
Re: [PATCH v3 2/3] win32: allow building with pedantic mode enabled
Quoted 2 lines
Apologies; it is gone already in "seen" (and hopefully soon in "next") by merging js/win-lazyload-buildfix[1]
Ah, thanks for having fixed this.
Re: [PATCH v3 2/3] win32: allow building with pedantic mode enabled
In reply to Carlo ArenasQuoted 11 lines · Carlo Arenas
Quoted 9 lines · Jonathan Tan
config.mak.dev line 14
Quoted 4 lines
config.mak.dev +3
-0+ifneq ($(filter gcc5,$(COMPILER_FEATURES)),) +DEVELOPER_CFLAGS += -Wno-incompatible-pointer-types +endifI 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:
Quoted 2 lines
Apologies; it is gone already in "seen" (and hopefully soon in "next") by merging js/win-lazyload-buildfix[1]
I will mark it not ready for 'next', while waiting for a fix-up. Thanks for stopping me.
Re: [PATCH v3 2/3] win32: allow building with pedantic mode enabled
Quoted 13 lines
Quoted 11 lines · Carlo Arenas
Quoted 9 lines · Jonathan Tan
config.mak.dev line 14
Quoted 4 lines
config.mak.dev +3
-0+ifneq ($(filter gcc5,$(COMPILER_FEATURES)),) +DEVELOPER_CFLAGS += -Wno-incompatible-pointer-types +endifI 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:
Quoted 5 lines
Quoted 2 lines
Apologies; it is gone already in "seen" (and hopefully soon in "next") by merging js/win-lazyload-buildfix[1]
I will mark it not ready for 'next', while waiting for a fix-up. Thanks for stopping me.
Just checking - which branch is not ready for next? The issue I noticed is already in master, and js/win-lazyload-buildfix contains the fix for the issue (which ideally would be merged as soon as possible, but merging according to the usual schedule is fine).
Re: [PATCH v3 2/3] win32: allow building with pedantic mode enabled
Quoted 6 lines · Jonathan Tan
Quoted 6 lines
Quoted 2 lines · Carlo Arenas
Apologies; it is gone already in "seen" (and hopefully soon in "next") by merging js/win-lazyload-buildfix[1]
Quoted 7 lines
Quoted 2 lines
I will mark it not ready for 'next', while waiting for a fix-up. Thanks for stopping me.
Just checking - which branch is not ready for next? The issue I noticed is already in master, and js/win-lazyload-buildfix contains the fix for the issue (which ideally would be merged as soon as possible, but merging according to the usual schedule is fine).
My guess was that he meant to have also the windows specific check added as part of this branch, and that would have prevented the issue you reported originally as well.
Either way, a v4 has been posted[1] (sorry, forgot to CC you), and hopefully that is now ready for next ;)
Carlo
Re: [PATCH v3 2/3] win32: allow building with pedantic mode enabled
Quoted 2 lines · Carlo Arenas
Either way, a v4 has been posted[1] (sorry, forgot to CC you), and hopefully that is now ready for next ;)
Thanks, both.
PATCH v3 3/3 developer: enable pedantic by default
In reply to Carlo Marcelo Arenas BelónWith 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/[email protected]/
---
Makefile | 4 ++-- config.mak.dev | 4 +++- 2 files changed, 5 insertions(+), 3 deletions(-)
Makefile +2 -2
@@ -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
config.mak.dev +3 -1
@@ -7,9 +7,11 @@ DEVELOPER_CFLAGS += -Werror SPARSE_FLAGS += -Wsparse-error endif DEVELOPER_CFLAGS += -Wall -ifneq ($(filter pedantic,$(DEVOPTS)),) +ifeq ($(filter no-pedantic,$(DEVOPTS)),) DEVELOPER_CFLAGS += -pedantic +DEVELOPER_CFLAGS += -Wpedantic ifneq ($(filter gcc5,$(COMPILER_FEATURES)),) +DEVELOPER_CFLAGS += -Wno-pedantic-ms-format DEVELOPER_CFLAGS += -Wno-incompatible-pointer-types endif endif
Signature · 1 line
2.33.0.481.g26d3bed244
Re: [PATCH v3 0/3] support pedantic in developer mode
In reply to Carlo Marcelo Arenas BelónQuoted 15 lines · Carlo Marcelo Arenas Belón
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.
Quoted 8 lines
[1] https://lore.kernel.org/git/[email protected]/
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 inN_()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.
Re: [PATCH/RFC 0/3] pedantic errors in next
In reply to Carlo Marcelo Arenas BelónQuoted 3 lines · Carlo Marcelo Arenas Belón
Building next with pedantic enabled shows the following 2 issues that were originally in ew/many-alternate-optim, apologies for not catching them earlier.
This of course affects 'master'.
The first two look trivially correct and I am tempted to take them in -rc2; the last one, from my cursory look, I didn't see anything wrong in it, but is not all that urgent, either.
Quoted 2 lines
the second one could be skipped, and has indeed another similar case already in seen which will be send separately.
Thanks.
Re: [PATCH/RFC 0/3] pedantic errors in next
Quoted 11 lines · Junio C Hamano
Quoted 3 lines · Carlo Marcelo Arenas Belón
Building next with pedantic enabled shows the following 2 issues that were originally in ew/many-alternate-optim, apologies for not catching them earlier.
This of course affects 'master'.
The first two look trivially correct and I am tempted to take them in -rc2; the last one, from my cursory look, I didn't see anything wrong in it, but is not all that urgent, either.
Agreed on all counts.
I've been starting to think oidtree/cbtree would be better done as BSD-style macro-defined functions (similar to how khash.h is, or sys/{queue,tree}.h on *BSD systems).
I prefer Linux(kernel)-style container_of generics since I find them easier-to-follow and have extra type-checking, but with a flex-array it's not pedantically correct.
So I guess using CPP like khash does might be a better way to go, here.
Thoughts?
Side note: I've also been considering Perl as a more powerful CPP replacement so I could use the same code for a persistent on-disk store (it would be easier to swap in pread/mmap use). An on-disk format could make it good for refs and pre-packed object storage (perhaps replacing loose objects).
Re: [PATCH/RFC 0/3] pedantic errors in next
In reply to Junio C HamanoThanks,
in the discussion above René[1] proposed a fix for UBsan issues that were reported and that it is still missing.
my version of it didn't require the extra 4 bytes or showed issues with notes so is probably incomplete and should be replaced from the original if possible, but follows below:
Carlo
[1] https://lore.kernel.org/git/[email protected]/
+CC René for advise
--- >8 ---
Date: Sun, 8 Aug 2021 20:45:56 -0700
Subject: [PATCH] build: fixes for SANITIZE=undefined (WIP)
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
mostly from instructions/code provided by René in :
https://lore.kernel.org/git/20210807224957.GA5068@dcvr/
tested with Xcode in macOS 11.5.1 (x86_64)
--- hash.h | 2 +- object-file.c | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-)
hash.h +1 -1
@@ -115,7 +115,7 @@ static inline void git_SHA256_Clone(git_SHA256_CTX *dst, const git_SHA256_CTX *sstruct object_id {unsigned char hash[GIT_MAX_RAWSZ ]; -int algo; +uint8_t algo; };/* A suitably aligned type for stack allocations of hash contexts. */
object-file.c +1 -1
@@ -2406,7 +2406,7 @@ struct oidtree *odb_loose_cache(struct object_directory *odb,struct strbuf buf =STRBUF_INIT ;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); +size_t mask =1U << (subdir_nr % word_bits);uint32_t *bitmap; if (subdir_nr < 0 ||
Signature · 1 line
2.33.0.rc1.379.g2890ef5eb6
Re: [PATCH/RFC 0/3] pedantic errors in next
Am 10.08.21 um 08:16 schrieb Carlo Marcelo Arenas Belón:
Quoted 8 lines
Thanks,
in the discussion above René[1] proposed a fix for UBsan issues that were reported and that it is still missing.
my version of it didn't require the extra 4 bytes or showed issues with notes so is probably incomplete and should be replaced from the original if possible, but follows below:
With your three patches plus the one below t3301-notes.sh and several more fail on an Apple M1. Adding an unused int member to struct leaf_node fixes that. I didn't dig deeper into the notes code to understand the actual issue, though.
Quoted 42 lines
Carlo
[1] https://lore.kernel.org/git/[email protected]/
+CC René for advise
--- >8 ---
Date: Sun, 8 Aug 2021 20:45:56 -0700
Subject: [PATCH] build: fixes for SANITIZE=undefined (WIP)
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bitmostly from instructions/code provided by René in :
https://lore.kernel.org/git/20210807224957.GA5068@dcvr/
tested with Xcode in macOS 11.5.1 (
x86_64)--- hash.h | 2 +- object-file.c | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-)hash.h +1
-1@@ -115,7 +115,7 @@ static inline void git_SHA256_Clone(git_SHA256_CTX *dst, const git_SHA256_CTX *sstruct object_id {unsigned char hash[GIT_MAX_RAWSZ ]; -int algo; +uint8_t algo; };/* A suitably aligned type for stack allocations of hash contexts. */ object-file.c +0
-0
object-file.c struct oidtree *odb_loose_cache(struct object_directory *odb, · line 2412
Quoted 8 lines
object-file.c +1
-1@@ -2406,7 +2406,7 @@ struct oidtree *odb_loose_cache(struct object_directory *odb,struct strbuf buf =STRBUF_INIT ;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); +size_t mask =1U << (subdir_nr % word_bits);uint32_t *bitmap; if (subdir_nr < 0 ||
The first hunk is about alignment (and missing the notes fix, as mentioned). The second hunk is about shifting a signed 32-bit value 31 places to the left, which is undefined (because technically there are only 31 value bits). Those are different issues and they should be addressed by separate patches, I think. That's why I submitted a patch for the the second one in
http://public-inbox.org/git/[email protected]/.
René
Re: [PATCH/RFC 0/3] pedantic errors in next
Quoted 4 lines · René Scharfe
Those are different issues and they should be addressed by separate patches, I think. That's why I submitted a patch for the second one in
http://public-inbox.org/git/[email protected]/.
agree, and that is why I mentioned not to merge mine but use your whole series instead when it is published (mine was just a stopgap to see if I could get SANITIZE=undefined to behave meanwhile, but that I thought would be worth making public so anyone else affected might have something to start with)
would at least the two included in the chunks above be safe enough for RC2 as I hope?, is the one with the additional int too hacky to be considered for release?; FWIW hadn't been able to reproduce that issue you reported in t3301 even with an Apple M1 with macOS 11.5.1 (I use NO_GETTEXT=1 though, not sure that might be why)
Anything I can help with?
Carlo
Re: [PATCH/RFC 0/3] pedantic errors in next
Quoted 3 lines · Carlo Arenas
FWIW hadn't been able to reproduce that issue
you reported in t3301 even with an Apple M1 with macOS 11.5.1 (I use NO_GETTEXT=1 though, not sure that might be why)
but it seems to be reproducible in the 32bit linux job from CI[1] :
git: notes.c:206: note_tree_remove: Assertion `GET_PTR_TYPE(entry)
== 0' failed.
Carlo
[1] https://github.com/carenas/git/runs/3295672049?check_suite_focus=true
Re: [PATCH/RFC 0/3] pedantic errors in next
In reply to Carlo ArenasHi Carlo,
Am 11.08.21 um 01:49 schrieb Carlo Arenas:
Quoted 12 lines · René Scharfe
Quoted 4 lines
Those are different issues and they should be addressed by separate patches, I think. That's why I submitted a patch for the second one in
http://public-inbox.org/git/[email protected]/.agree, and that is why I mentioned not to merge mine but use your whole series instead when it is published (mine was just a stopgap to see if I could get SANITIZE=undefined to behave meanwhile, but that I thought would be worth making public so anyone else affected might have something to start with)
Quoted 3 lines
would at least the two included in the chunks above be safe enough for RC2 as I hope?, is the one with the additional int too hacky to be considered for release?;
I think your -pedantic fixes 1 and 2 should go into the next possible release candidate because they fix regressions.
Same for my signed-left-shift fix in
http://public-inbox.org/git/[email protected]/
(or some improved version if it's lacking in some way) and the yet to be published fix for the alignment issue. I assume Andrzej as the reporter or Eric as the original author would like to have a shot at the latter.
Quoted 3 lines
FWIW hadn't been able to reproduce that issue
you reported in t3301 even with an Apple M1 with macOS 11.5.1 (I use NO_GETTEXT=1 though, not sure that might be why)
Strange. I use Apple clang version 12.0.5 (clang-1205.0.22.11) on the same OS.
At least the reproduction on Linux that you mentioned in your reply means I can calm down a bit because it's not just a problem on my system..
Thank you,
René
Re: [PATCH/RFC 0/3] pedantic errors in next
Quoted 6 lines · René Scharfe
Quoted 3 lines
would at least the two included in the chunks above be safe enough for RC2 as I hope?, is the one with the additional int too hacky to be considered for release?;
I think your -pedantic fixes 1 and 2 should go into the next possible release candidate because they fix regressions.
I agree. They are at the bottom of 'seen' just above 'master' in last night's pushout for this exact reason.
Quoted 5 lines
Same for my signed-left-shift fix in
http://public-inbox.org/git/[email protected]/
(or some improved version if it's lacking in some way) and the yet to be published fix for the alignment issue. I assume Andrzej as the reporter or Eric as the original author would like to have a shot at the latter.
Thanks. It was missed as it was buried in the discussion exchange. Will queue together with cb/many-alternate-optim-fixup topic.
Re: [PATCH v2 5/5] oidtree: a crit-bit tree for odb_loose_cache
In reply to Carlo ArenasAm 09.08.21 um 03:35 schrieb Carlo Arenas:
Quoted 62 lines · Eric Wong
Quoted 43 lines
Quoted 40 lines · René Scharfe
Am 06.08.21 um 17:31 schrieb Andrzej Hunt:
Quoted 39 lines · Eric Wong
Quoted 15 lines
[...snip...]
oidtree.c new file +7
-0+struct oidtree_node { +/* n.k[] is used to store "struct object_id" */ +struct cb_node n; +}; + + +void oidtree_insert (struct oidtree *ot,const struct object_id *oid)oidtree.c
Quoted 10 lines
oidtree.c new file +10
-0+{ +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_idcast 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 "structobject_id*", and later try to access object_id.hash withinoidcpy_with_padding. My compiler assumes that anobject_idpointer 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?)Quoted 3 lines
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.
Quoted 3 lines
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é
Re: [PATCH v2 5/5] oidtree: a crit-bit tree for odb_loose_cache
In reply to Eric WongAm 08.08.21 um 00:49 schrieb Eric Wong:
Quoted 54 lines
Quoted 40 lines · René Scharfe
Am 06.08.21 um 17:31 schrieb Andrzej Hunt:
Quoted 39 lines · Eric Wong
Quoted 15 lines
[...snip...]
oidtree.c new file +7
-0+struct oidtree_node { + /* n.k[] is used to store "struct object_id" */ + struct cb_node n; +}; + + +void oidtree_insert (struct oidtree *ot,const struct object_id *oid)oidtree.c
Quoted 10 lines
oidtree.c new file +10
-0+{ + 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_idcast 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 "structobject_id*", and later try to access object_id.hash withinoidcpy_with_padding. My compiler assumes that anobject_idpointer 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 8 lines
Quoted 7 lines
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.charder to read.
Quoted 5 lines
Quoted 2 lines
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_nodeshould be as small as possible and (for our current purposes) ->byte could beuint8_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 6 lines
Quoted 3 lines
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_idsmaller 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é
PATCH 1/1 oidtree: avoid unaligned access to crit-bit tree
In reply to Andrzej HuntThe 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.
--- cbtree.h | 2 +- hash.h | 2 +- oidtree.c | 20 +++++++++++++++----- 3 files changed, 17 insertions(+), 7 deletions(-)
cbtree.h +1 -1
@@ -25,7 +25,7 @@ struct cb_node {*/ uint32_t byte;uint8_t otherbits; -uint8_t k[FLEX_ARRAY ];/* arbitrary data */ +uint8_t k[FLEX_ARRAY ];/* arbitrary data, unaligned */ };struct cb_tree {
hash.h +1 -1
@@ -115,7 +115,7 @@ static inline void git_SHA256_Clone(git_SHA256_CTX *dst, const git_SHA256_CTX *sstruct object_id {unsigned char hash[GIT_MAX_RAWSZ ]; -int algo; +int algo;/* XXX requires 4-byte alignment */ };/* A suitably aligned type for stack allocations of hash contexts. */
oidtree.c +15 -5
@@ -31,12 +31,19 @@ void oidtree_clear(struct oidtree *ot)void oidtree_insert (struct oidtree *ot,const struct object_id *oid) {struct cb_node *on; +struct object_id k;if (!oid->algo)BUG ("oidtree_insert requires oid->algo" ); on =mem_pool_alloc (&ot->mem_pool,sizeof (*on) +sizeof (*oid)); -oidcpy_with_padding ((struct object_id *)on->k, oid); + +/* +* Clear the padding and copy the result in separate steps to +* respect the 4-byte alignment needed by struct object_id. +*/ +oidcpy_with_padding (&k, oid); +memcpy (on->k, &k,sizeof (k));/* * n.b. Current callers won't get us duplicates, here. If a
@@ -68,17 +75,20 @@ int oidtree_contains(struct oidtree *ot, const struct object_id *oid)static enum cb_next iter (struct cb_node *n,void *arg) {struct oidtree_iter_data *x = arg; -const struct object_id *oid = (const struct object_id *)n->k; +struct object_id k; + +/* Copy to provide 4-byte alignment needed by struct object_id. */ +memcpy (&k, n->k,sizeof (k)); -if (x->algo !=GIT_HASH_UNKNOWN && x->algo != oid->algo) +if (x->algo !=GIT_HASH_UNKNOWN && x->algo != k.algo)return CB_CONTINUE ;if (x->last_nibble_at) { -if ((oid->hash[*x->last_nibble_at] ^ x->last_byte) &0xf0 ) +if ((k.hash[*x->last_nibble_at] ^ x->last_byte) &0xf0 )return CB_CONTINUE ; } -return x->fn (oid, x->arg); +return x->fn (&k, x->arg); } void oidtree_each(struct oidtree *ot, const struct object_id *oid,
--
2.32.0
Re: [PATCH] oidtree: avoid unaligned access to crit-bit tree
Quoted 39 lines · René Scharfe
The flexible array member "k" of struct
cb_nodeis 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_idascb_nodekey. Sincecf0983213c(hash:
add an algo member to structobject_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
0x00015000802dfor type 'structobject_id', which requires 4 byte alignment0x00015000802d: 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 structcb_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 auint8_tfor 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 structobject_idby 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_toruint32_tfor each), or by avoiding the use of flexible arrays likekhash.hdoes.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.
Quoted 7 lines
Reported-by Andrzej Hunt <[email protected]>Signed-off-by René Scharfe <[email protected]>--- cbtree.h | 2 +- hash.h | 2 +- oidtree.c | 20 +++++++++++++++----- 3 files changed, 17 insertions(+), 7 deletions(-)
Thanks. Among the choices you considered (and I agree that each of them is a solution that goes in a reasonable direction), the one chosen here certainly is the least risky one.