* [PATCH] fast-export: avoid NULL pointer arithmetic @ 2018-05-09 21:06 René Scharfe 2018-05-09 21:43 ` Johannes Schindelin 2018-05-10 9:24 ` René Scharfe 0 siblings, 2 replies; 16+ messages in thread From: René Scharfe @ 2018-05-09 21:06 UTC (permalink / raw) To: Git List; +Cc: Junio C Hamano, Johannes Schindelin Clang 6 reports the following warning, which is turned into an error in a DEVELOPER build: builtin/fast-export.c:162:28: error: performing pointer arithmetic on a null pointer has undefined behavior [-Werror,-Wnull-pointer-arithmetic] return ((uint32_t *)NULL) + mark; ~~~~~~~~~~~~~~~~~~ ^ 1 error generated. The compiler is correct, and the error message speaks for itself. There is no need for any undefined operation -- just cast mark to void * or uint32_t after an intermediate cast to uintptr_t. That encodes the integer value into a pointer and later decodes it as intended. While at it remove an outdated comment -- intptr_t has been used since ffe659f94d (parse-options: make some arguments optional, add callbacks), committed in October 2007. Signed-off-by: Rene Scharfe <l.s.r@web.de> --- builtin/fast-export.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) diff --git a/builtin/fast-export.c b/builtin/fast-export.c index 530df12f05..fa556a3c93 100644 --- a/builtin/fast-export.c +++ b/builtin/fast-export.c @@ -156,15 +156,14 @@ static void anonymize_path(struct strbuf *out, const char *path, } } -/* Since intptr_t is C99, we do not use it here */ -static inline uint32_t *mark_to_ptr(uint32_t mark) +static inline void *mark_to_ptr(uint32_t mark) { - return ((uint32_t *)NULL) + mark; + return (void *)(uintptr_t)mark; } static inline uint32_t ptr_to_mark(void * mark) { - return (uint32_t *)mark - (uint32_t *)NULL; + return (uint32_t)(uintptr_t)mark; } static inline void mark_object(struct object *object, uint32_t mark) -- 2.17.0 ^ permalink raw reply related [flat|nested] 16+ messages in thread
* Re: [PATCH] fast-export: avoid NULL pointer arithmetic 2018-05-09 21:06 [PATCH] fast-export: avoid NULL pointer arithmetic René Scharfe @ 2018-05-09 21:43 ` Johannes Schindelin 2018-05-10 9:24 ` René Scharfe 1 sibling, 0 replies; 16+ messages in thread From: Johannes Schindelin @ 2018-05-09 21:43 UTC (permalink / raw) To: René Scharfe; +Cc: Git List, Junio C Hamano [-- Attachment #1: Type: text/plain, Size: 899 bytes --] Hi René, On Wed, 9 May 2018, René Scharfe wrote: > Clang 6 reports the following warning, which is turned into an error in a > DEVELOPER build: > > builtin/fast-export.c:162:28: error: performing pointer arithmetic on a null pointer has undefined behavior [-Werror,-Wnull-pointer-arithmetic] > return ((uint32_t *)NULL) + mark; > ~~~~~~~~~~~~~~~~~~ ^ > 1 error generated. > > The compiler is correct, and the error message speaks for itself. There > is no need for any undefined operation -- just cast mark to void * or > uint32_t after an intermediate cast to uintptr_t. That encodes the > integer value into a pointer and later decodes it as intended. > > While at it remove an outdated comment -- intptr_t has been used since > ffe659f94d (parse-options: make some arguments optional, add callbacks), > committed in October 2007. ACK. Thanks, Dscho ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH] fast-export: avoid NULL pointer arithmetic 2018-05-09 21:06 [PATCH] fast-export: avoid NULL pointer arithmetic René Scharfe 2018-05-09 21:43 ` Johannes Schindelin @ 2018-05-10 9:24 ` René Scharfe 2018-05-10 10:51 ` Junio C Hamano 1 sibling, 1 reply; 16+ messages in thread From: René Scharfe @ 2018-05-10 9:24 UTC (permalink / raw) To: Git List; +Cc: Junio C Hamano, Johannes Schindelin Am 09.05.2018 um 23:06 schrieb René Scharfe: > Clang 6 reports the following warning, which is turned into an error in a > DEVELOPER build: > > builtin/fast-export.c:162:28: error: performing pointer arithmetic on a null pointer has undefined behavior [-Werror,-Wnull-pointer-arithmetic] > return ((uint32_t *)NULL) + mark; > ~~~~~~~~~~~~~~~~~~ ^ > 1 error generated. > > The compiler is correct, and the error message speaks for itself. There > is no need for any undefined operation -- just cast mark to void * or > uint32_t after an intermediate cast to uintptr_t. That encodes the > integer value into a pointer and later decodes it as intended. Having thought about it a bit more I have to say: That seems to work, but it's not portable. The standard says about uintptr_t that "any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer". So void * -> uintptr_t -> void * is a proper roundtrip, but that doesn't imply that casting arbitrary uintptr_t values to void * would be lossless. I don't know an architecture where this would bite us, but I wonder if there is a cleaner way. Perhaps changing the type of the decoration member of struct decoration_entry in decorate.h to uintptr_t? > While at it remove an outdated comment -- intptr_t has been used since > ffe659f94d (parse-options: make some arguments optional, add callbacks), > committed in October 2007. > > Signed-off-by: Rene Scharfe <l.s.r@web.de> > --- > builtin/fast-export.c | 7 +++---- > 1 file changed, 3 insertions(+), 4 deletions(-) > > diff --git a/builtin/fast-export.c b/builtin/fast-export.c > index 530df12f05..fa556a3c93 100644 > --- a/builtin/fast-export.c > +++ b/builtin/fast-export.c > @@ -156,15 +156,14 @@ static void anonymize_path(struct strbuf *out, const char *path, > } > } > > -/* Since intptr_t is C99, we do not use it here */ > -static inline uint32_t *mark_to_ptr(uint32_t mark) > +static inline void *mark_to_ptr(uint32_t mark) > { > - return ((uint32_t *)NULL) + mark; > + return (void *)(uintptr_t)mark; > } > > static inline uint32_t ptr_to_mark(void * mark) > { > - return (uint32_t *)mark - (uint32_t *)NULL; > + return (uint32_t)(uintptr_t)mark; > } > > static inline void mark_object(struct object *object, uint32_t mark) > ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH] fast-export: avoid NULL pointer arithmetic 2018-05-10 9:24 ` René Scharfe @ 2018-05-10 10:51 ` Junio C Hamano 2018-05-10 19:47 ` René Scharfe 0 siblings, 1 reply; 16+ messages in thread From: Junio C Hamano @ 2018-05-10 10:51 UTC (permalink / raw) To: René Scharfe; +Cc: Git List, Johannes Schindelin René Scharfe <l.s.r@web.de> writes: > The standard says about uintptr_t that "any valid pointer to void can > be converted to this type, then converted back to pointer to void, and > the result will compare equal to the original pointer". So void * -> > uintptr_t -> void * is a proper roundtrip, but that doesn't imply that > casting arbitrary uintptr_t values to void * would be lossless. > > I don't know an architecture where this would bite us, but I wonder if > there is a cleaner way. Perhaps changing the type of the decoration > member of struct decoration_entry in decorate.h to uintptr_t? In order to ensure "void * -> uintptr_t -> void *" roundtrip holds, the implementation would guarantee that uintptr_t is wider than void*, so what you suggest technically makes sense. We should be able to store any pointer in the field. And we should be able to store any value of an unsigned integral type that is narrower than uintptr_t. But it somehow feels backwards in spirit to me, as the reason why we use "void *" there in the decoration field is because we expect that we'd have a pointer to some struture most of the time, and we have to occasionally store a small integer there. So I'd naively expect that uint32_t mark = 23; de->decoration = (void *)mark; would be a good way to store mark #23 in the field and uint32_t mark; mark = (typeof(mark))de->decoration; would be a good way to read it off of the "void *" field. Of course, this assume that (void *) is at least as wide as 32-bit and it also ignores the standard ;-) This is an unrelated tangent but the mark-to-ptr() and ptr-to-mark() implementations feel wasteful, especially when we worry about 32-bit archs. A naive platform implementation of (uint32_t *)mark - (uint32_t *)NULL; would be ((uintptr_t)mark) / 4, i.e. the de->decoration field will always have two LSB clear and only utilize top 30-bit to represent the value of mark. ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH] fast-export: avoid NULL pointer arithmetic 2018-05-10 10:51 ` Junio C Hamano @ 2018-05-10 19:47 ` René Scharfe 2018-05-11 2:16 ` Junio C Hamano 0 siblings, 1 reply; 16+ messages in thread From: René Scharfe @ 2018-05-10 19:47 UTC (permalink / raw) To: Junio C Hamano; +Cc: Git List, Johannes Schindelin Am 10.05.2018 um 12:51 schrieb Junio C Hamano: > René Scharfe <l.s.r@web.de> writes: > >> The standard says about uintptr_t that "any valid pointer to void can >> be converted to this type, then converted back to pointer to void, and >> the result will compare equal to the original pointer". So void * -> >> uintptr_t -> void * is a proper roundtrip, but that doesn't imply that >> casting arbitrary uintptr_t values to void * would be lossless. >> >> I don't know an architecture where this would bite us, but I wonder if >> there is a cleaner way. Perhaps changing the type of the decoration >> member of struct decoration_entry in decorate.h to uintptr_t? > > In order to ensure "void * -> uintptr_t -> void *" roundtrip holds, > the implementation would guarantee that uintptr_t is wider than > void*, so what you suggest technically makes sense. We should be > able to store any pointer in the field. And we should be able to > store any value of an unsigned integral type that is narrower than > uintptr_t. > > But it somehow feels backwards in spirit to me, as the reason why we > use "void *" there in the decoration field is because we expect that > we'd have a pointer to some struture most of the time, and we have > to occasionally store a small integer there. Yes, fast-export seems to be the only place that stores an integer as a decoration. > So I'd naively expect > that > > uint32_t mark = 23; > de->decoration = (void *)mark; > > would be a good way to store mark #23 in the field and > > uint32_t mark; > mark = (typeof(mark))de->decoration; > > would be a good way to read it off of the "void *" field. Of > course, this assume that (void *) is at least as wide as 32-bit and > it also ignores the standard ;-) Right, it looks deceptively good and works fine if memory is flat and valid values for pointers are in a contiguous range starting at zero. The standard allows for other models as well, though. > This is an unrelated tangent but the mark-to-ptr() and ptr-to-mark() > implementations feel wasteful, especially when we worry about 32-bit > archs. A naive platform implementation of > > (uint32_t *)mark - (uint32_t *)NULL; > > would be ((uintptr_t)mark) / 4, i.e. the de->decoration field will > always have two LSB clear and only utilize top 30-bit to represent > the value of mark. That's right, but I don't see what's naive about it, or how a 32-bit architecture could avoid wasting those two bits. Using struct decorate in fast-export has the benefit of not requiring separate allocations for individual entries. Switching to struct hashmap would require individual allocations. Adding a custom clone of decorate with a uint32_t payload would be an option. René ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH] fast-export: avoid NULL pointer arithmetic 2018-05-10 19:47 ` René Scharfe @ 2018-05-11 2:16 ` Junio C Hamano 2018-05-11 4:49 ` Junio C Hamano 0 siblings, 1 reply; 16+ messages in thread From: Junio C Hamano @ 2018-05-11 2:16 UTC (permalink / raw) To: René Scharfe; +Cc: Git List, Johannes Schindelin René Scharfe <l.s.r@web.de> writes: >> But it somehow feels backwards in spirit to me, as the reason why we >> use "void *" there in the decoration field is because we expect that >> we'd have a pointer to some struture most of the time, and we have >> to occasionally store a small integer there. > > Yes, fast-export seems to be the only place that stores an integer as > a decoration. With the decoration subsystem that might be the case, but I think we have other codepaths where "void * .util" field in the structure is used to store (void *)1, expecting that a normal allocation will never yield a pointer that is indistinguishable from that value. > Using struct decorate in fast-export has the benefit of not > requiring separate allocations for individual entries. Switching to > struct hashmap would require individual allocations. Adding a > custom clone of decorate with a uint32_t payload would be an option. As long as we know uint32_t is no wider than uintptr_t, your patch should be safe, shouldn't it? ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH] fast-export: avoid NULL pointer arithmetic 2018-05-11 2:16 ` Junio C Hamano @ 2018-05-11 4:49 ` Junio C Hamano 2018-05-11 6:19 ` Duy Nguyen 0 siblings, 1 reply; 16+ messages in thread From: Junio C Hamano @ 2018-05-11 4:49 UTC (permalink / raw) To: René Scharfe; +Cc: Git List, Johannes Schindelin Junio C Hamano <gitster@pobox.com> writes: > René Scharfe <l.s.r@web.de> writes: > >>> But it somehow feels backwards in spirit to me, as the reason why we >>> use "void *" there in the decoration field is because we expect that >>> we'd have a pointer to some struture most of the time, and we have >>> to occasionally store a small integer there. >> >> Yes, fast-export seems to be the only place that stores an integer as >> a decoration. > > With the decoration subsystem that might be the case, but I think > we have other codepaths where "void * .util" field in the structure > is used to store (void *)1, expecting that a normal allocation will > never yield a pointer that is indistinguishable from that value. I was looking at a different topic and noticed that bisect.c uses commit->util (which is of type "void *") to always store an int (it never stores a pointer and there is no mixing). This one is equally unportable as fast-export after your fix. ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH] fast-export: avoid NULL pointer arithmetic 2018-05-11 4:49 ` Junio C Hamano @ 2018-05-11 6:19 ` Duy Nguyen 2018-05-11 8:56 ` Jeff King 0 siblings, 1 reply; 16+ messages in thread From: Duy Nguyen @ 2018-05-11 6:19 UTC (permalink / raw) To: Junio C Hamano; +Cc: René Scharfe, Git List, Johannes Schindelin On Fri, May 11, 2018 at 6:49 AM, Junio C Hamano <gitster@pobox.com> wrote: > Junio C Hamano <gitster@pobox.com> writes: > >> René Scharfe <l.s.r@web.de> writes: >> >>>> But it somehow feels backwards in spirit to me, as the reason why we >>>> use "void *" there in the decoration field is because we expect that >>>> we'd have a pointer to some struture most of the time, and we have >>>> to occasionally store a small integer there. >>> >>> Yes, fast-export seems to be the only place that stores an integer as >>> a decoration. >> >> With the decoration subsystem that might be the case, but I think >> we have other codepaths where "void * .util" field in the structure >> is used to store (void *)1, expecting that a normal allocation will >> never yield a pointer that is indistinguishable from that value. > > I was looking at a different topic and noticed that bisect.c uses > commit->util (which is of type "void *") to always store an int (it > never stores a pointer and there is no mixing). This one is equally > unportable as fast-export after your fix. > In both cases we should be able to use commit-slab instead of commit->util. We could go even further and kill "util" pointer but that's more work. -- Duy ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH] fast-export: avoid NULL pointer arithmetic 2018-05-11 6:19 ` Duy Nguyen @ 2018-05-11 8:56 ` Jeff King 2018-05-11 13:11 ` Duy Nguyen 0 siblings, 1 reply; 16+ messages in thread From: Jeff King @ 2018-05-11 8:56 UTC (permalink / raw) To: Duy Nguyen Cc: Junio C Hamano, René Scharfe, Git List, Johannes Schindelin On Fri, May 11, 2018 at 08:19:59AM +0200, Duy Nguyen wrote: > On Fri, May 11, 2018 at 6:49 AM, Junio C Hamano <gitster@pobox.com> wrote: > > Junio C Hamano <gitster@pobox.com> writes: > > > >> René Scharfe <l.s.r@web.de> writes: > >> > >>>> But it somehow feels backwards in spirit to me, as the reason why we > >>>> use "void *" there in the decoration field is because we expect that > >>>> we'd have a pointer to some struture most of the time, and we have > >>>> to occasionally store a small integer there. > >>> > >>> Yes, fast-export seems to be the only place that stores an integer as > >>> a decoration. > >> > >> With the decoration subsystem that might be the case, but I think > >> we have other codepaths where "void * .util" field in the structure > >> is used to store (void *)1, expecting that a normal allocation will > >> never yield a pointer that is indistinguishable from that value. > > > > I was looking at a different topic and noticed that bisect.c uses > > commit->util (which is of type "void *") to always store an int (it > > never stores a pointer and there is no mixing). This one is equally > > unportable as fast-export after your fix. > > > > In both cases we should be able to use commit-slab instead of > commit->util. We could go even further and kill "util" pointer but > that's more work. I would love it if we could kill the util pointer in favor of commit-slab. Unfortunately the fast-export case is decorating non-commit objects, too. I'm not sure how possible/easy it would be to have an "object slab". Some complications are: 1. It would increase the size of "struct tree" and "struct blob" by at least 4 bytes (possibly 8, due to alignment) to store the slab index. Commits would stay the same, but my experience is that most repositories have 5-10 times as many trees/blobs as commits. Some of that memory might be reclaimable. E.g., if we moved tree->buffer and tree->size into a slab, callers which don't use them would actually come out ahead (and more callers than you might expect could do this, since many only need to look at the tree contents inside a single function). 2. If we allocate the indices for all types as a single sequence, then callers who only care about a specific type will have very sparse slabs (so they'll over-allocate, and it will have poor cache behavior). It might be possible to do something more clever. E.g., give each object type its own index counter, but then for a full object-slab, store per-type slabs and dereference obj->type to know which slab to look in. There'd be some complication with any_object. We'd probably need an OBJ_NONE slab, and then to allocate a type-specific index when the type is assigned. There's already a central point for this in object_as_type(). But we'd also have to migrate any previously-stored slab data (stored when it was OBJ_NONE), which implies having a global list of slabs. So I dunno. It seems do-able but complicated. -Peff ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH] fast-export: avoid NULL pointer arithmetic 2018-05-11 8:56 ` Jeff King @ 2018-05-11 13:11 ` Duy Nguyen 2018-05-11 13:34 ` Duy Nguyen 0 siblings, 1 reply; 16+ messages in thread From: Duy Nguyen @ 2018-05-11 13:11 UTC (permalink / raw) To: Jeff King Cc: Junio C Hamano, René Scharfe, Git List, Johannes Schindelin On Fri, May 11, 2018 at 10:56 AM, Jeff King <peff@peff.net> wrote: > On Fri, May 11, 2018 at 08:19:59AM +0200, Duy Nguyen wrote: > >> On Fri, May 11, 2018 at 6:49 AM, Junio C Hamano <gitster@pobox.com> wrote: >> > Junio C Hamano <gitster@pobox.com> writes: >> > >> >> René Scharfe <l.s.r@web.de> writes: >> >> >> >>>> But it somehow feels backwards in spirit to me, as the reason why we >> >>>> use "void *" there in the decoration field is because we expect that >> >>>> we'd have a pointer to some struture most of the time, and we have >> >>>> to occasionally store a small integer there. >> >>> >> >>> Yes, fast-export seems to be the only place that stores an integer as >> >>> a decoration. >> >> >> >> With the decoration subsystem that might be the case, but I think >> >> we have other codepaths where "void * .util" field in the structure >> >> is used to store (void *)1, expecting that a normal allocation will >> >> never yield a pointer that is indistinguishable from that value. >> > >> > I was looking at a different topic and noticed that bisect.c uses >> > commit->util (which is of type "void *") to always store an int (it >> > never stores a pointer and there is no mixing). This one is equally >> > unportable as fast-export after your fix. >> > >> >> In both cases we should be able to use commit-slab instead of >> commit->util. We could go even further and kill "util" pointer but >> that's more work. > > I would love it if we could kill the util pointer in favor of > commit-slab. Unfortunately the fast-export case is decorating non-commit > objects, too. Right. The "util" thing was a side discussion. Back to fast-export, can we just allocate a new int on heap and point it there? Allocating small pieces becomes quite cheap and fast with mem-pool.h and we can avoid this storing integer in pointer business. -- Duy ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH] fast-export: avoid NULL pointer arithmetic 2018-05-11 13:11 ` Duy Nguyen @ 2018-05-11 13:34 ` Duy Nguyen 2018-05-11 17:42 ` Jeff King 0 siblings, 1 reply; 16+ messages in thread From: Duy Nguyen @ 2018-05-11 13:34 UTC (permalink / raw) To: Jeff King Cc: Junio C Hamano, René Scharfe, Git List, Johannes Schindelin On Fri, May 11, 2018 at 03:11:46PM +0200, Duy Nguyen wrote: > Back to fast-export, can we just allocate a new int on heap and point > it there? Allocating small pieces becomes quite cheap and fast with > mem-pool.h and we can avoid this storing integer in pointer business. Something like this seems to work, but we use 4-ish more bytes per object, or 100MB overhead on a repo with 25M objects. I think it's a reasonable trade off. -- 8< -- diff --git a/builtin/fast-export.c b/builtin/fast-export.c index 530df12f05..de593035b1 100644 --- a/builtin/fast-export.c +++ b/builtin/fast-export.c @@ -21,6 +21,7 @@ #include "quote.h" #include "remote.h" #include "blob.h" +#include "mem-pool.h" static const char *fast_export_usage[] = { N_("git fast-export [rev-list-opts]"), @@ -38,6 +39,7 @@ static struct string_list extra_refs = STRING_LIST_INIT_NODUP; static struct refspec *refspecs; static int refspecs_nr; static int anonymize; +static struct mem_pool int_pool = MEM_POOL_INIT(2 * 1024 * 1024); static int parse_opt_signed_tag_mode(const struct option *opt, const char *arg, int unset) @@ -156,20 +158,22 @@ static void anonymize_path(struct strbuf *out, const char *path, } } -/* Since intptr_t is C99, we do not use it here */ -static inline uint32_t *mark_to_ptr(uint32_t mark) +static inline uint32_t ptr_to_mark(void *mark) { - return ((uint32_t *)NULL) + mark; -} - -static inline uint32_t ptr_to_mark(void * mark) -{ - return (uint32_t *)mark - (uint32_t *)NULL; + if (!mark) + BUG("not marked!"); + return *(uint32_t *)mark; } static inline void mark_object(struct object *object, uint32_t mark) { - add_decoration(&idnums, object, mark_to_ptr(mark)); + uint32_t *ptr = lookup_decoration(&idnums, object); + + if (!ptr) + ptr = mem_pool_alloc(&int_pool, sizeof(uint32_t)); + + *ptr = mark; + add_decoration(&idnums, object, ptr); } static inline void mark_next_object(struct object *object) diff --git a/fast-import.c b/fast-import.c index 34edf3fb8f..ce5ce2081f 100644 --- a/fast-import.c +++ b/fast-import.c @@ -300,8 +300,7 @@ static int global_argc; static const char **global_argv; /* Memory pools */ -static struct mem_pool fi_mem_pool = {NULL, 2*1024*1024 - - sizeof(struct mp_block), 0 }; +static struct mem_pool fi_mem_pool = MEM_POOL_INIT(2*1024*1024); /* Atom management */ static unsigned int atom_table_sz = 4451; diff --git a/mem-pool.h b/mem-pool.h index 829ad58ecf..bccbd3f224 100644 --- a/mem-pool.h +++ b/mem-pool.h @@ -21,6 +21,8 @@ struct mem_pool { size_t pool_alloc; }; +#define MEM_POOL_INIT(block_size) { NULL, (block_size) - sizeof(struct mp_block), 0 } + /* * Alloc memory from the mem_pool. */ -- 8< -- ^ permalink raw reply related [flat|nested] 16+ messages in thread
* Re: [PATCH] fast-export: avoid NULL pointer arithmetic 2018-05-11 13:34 ` Duy Nguyen @ 2018-05-11 17:42 ` Jeff King 2018-05-12 8:45 ` René Scharfe 0 siblings, 1 reply; 16+ messages in thread From: Jeff King @ 2018-05-11 17:42 UTC (permalink / raw) To: Duy Nguyen Cc: Junio C Hamano, René Scharfe, Git List, Johannes Schindelin On Fri, May 11, 2018 at 03:34:19PM +0200, Duy Nguyen wrote: > On Fri, May 11, 2018 at 03:11:46PM +0200, Duy Nguyen wrote: > > Back to fast-export, can we just allocate a new int on heap and point > > it there? Allocating small pieces becomes quite cheap and fast with > > mem-pool.h and we can avoid this storing integer in pointer business. > > Something like this seems to work, but we use 4-ish more bytes per > object, or 100MB overhead on a repo with 25M objects. I think it's a > reasonable trade off. I'm not sure I agree. 4 bytes per object certainly isn't the end of the world, but what was the problem we were solving in the first place? Just that we weren't comfortable with the round-trip from uintptr_t to void and back? Is this actually a problem on real platforms? If not, it seems silly to incur a run-time cost. -Peff ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH] fast-export: avoid NULL pointer arithmetic 2018-05-11 17:42 ` Jeff King @ 2018-05-12 8:45 ` René Scharfe 2018-05-12 8:49 ` René Scharfe 2018-05-14 1:37 ` Junio C Hamano 0 siblings, 2 replies; 16+ messages in thread From: René Scharfe @ 2018-05-12 8:45 UTC (permalink / raw) To: Jeff King, Duy Nguyen; +Cc: Junio C Hamano, Git List, Johannes Schindelin Am 11.05.2018 um 19:42 schrieb Jeff King: > On Fri, May 11, 2018 at 03:34:19PM +0200, Duy Nguyen wrote: > >> On Fri, May 11, 2018 at 03:11:46PM +0200, Duy Nguyen wrote: >>> Back to fast-export, can we just allocate a new int on heap and point >>> it there? Allocating small pieces becomes quite cheap and fast with >>> mem-pool.h and we can avoid this storing integer in pointer business. >> >> Something like this seems to work, but we use 4-ish more bytes per >> object, or 100MB overhead on a repo with 25M objects. I think it's a >> reasonable trade off. > > I'm not sure I agree. 4 bytes per object certainly isn't the end of the > world, but what was the problem we were solving in the first place? Just > that we weren't comfortable with the round-trip from uintptr_t to void > and back? Is this actually a problem on real platforms? If not, it seems > silly to incur a run-time cost. Storing integer values in pointers is a trick that seems to have worked so far for fast-export. A portable way to avoid that trick without requiring more memory would be to use a union. Or we could roll our own custom hash map, as I mused in an earlier post. That would duplicate quite a bit of code; are there reusable pieces hidden within that could be extracted into common functions? --- builtin/fast-export.c | 105 ++++++++++++++++++++++++++++++++---------- 1 file changed, 81 insertions(+), 24 deletions(-) diff --git a/builtin/fast-export.c b/builtin/fast-export.c index 530df12f05..627b0032f3 100644 --- a/builtin/fast-export.c +++ b/builtin/fast-export.c @@ -14,7 +14,6 @@ #include "diffcore.h" #include "log-tree.h" #include "revision.h" -#include "decorate.h" #include "string-list.h" #include "utf8.h" #include "parse-options.h" @@ -71,9 +70,65 @@ static int parse_opt_tag_of_filtered_mode(const struct option *opt, return 0; } -static struct decoration idnums; +struct object_mark_entry { + const struct object *base; + uint32_t mark; +}; + +struct object_marks { + unsigned int size; + unsigned int nr; + struct object_mark_entry *entries; +}; + +static struct object_marks idnums; static uint32_t last_idnum; +static unsigned int hash_obj(const struct object *obj, unsigned int n) +{ + return sha1hash(obj->oid.hash) % n; +} + +static void set_object_mark(struct object_marks *n, const struct object *base, + uint32_t mark) +{ + unsigned int size = n->size; + struct object_mark_entry *entries = n->entries; + unsigned int j = hash_obj(base, size); + + while (entries[j].base) { + if (entries[j].base == base) { + entries[j].mark = mark; + return; + } + if (++j >= size) + j = 0; + } + entries[j].base = base; + entries[j].mark = mark; + n->nr++; +} + +static void grow_object_marks(struct object_marks *n) +{ + unsigned int i; + unsigned int old_size = n->size; + struct object_mark_entry *old_entries = n->entries; + + n->size = (old_size + 1000) * 3 / 2; + n->entries = xcalloc(n->size, sizeof(n->entries[0])); + n->nr = 0; + + for (i = 0; i < old_size; i++) { + const struct object *base = old_entries[i].base; + uint32_t mark = old_entries[i].mark; + + if (mark) + set_object_mark(n, base, mark); + } + free(old_entries); +} + static int has_unshown_parent(struct commit *commit) { struct commit_list *parent; @@ -156,20 +211,13 @@ static void anonymize_path(struct strbuf *out, const char *path, } } -/* Since intptr_t is C99, we do not use it here */ -static inline uint32_t *mark_to_ptr(uint32_t mark) -{ - return ((uint32_t *)NULL) + mark; -} - -static inline uint32_t ptr_to_mark(void * mark) -{ - return (uint32_t *)mark - (uint32_t *)NULL; -} - static inline void mark_object(struct object *object, uint32_t mark) { - add_decoration(&idnums, object, mark_to_ptr(mark)); + unsigned int nr = idnums.nr + 1; + + if (nr > idnums.size * 2 / 3) + grow_object_marks(&idnums); + return set_object_mark(&idnums, object, mark); } static inline void mark_next_object(struct object *object) @@ -179,10 +227,21 @@ static inline void mark_next_object(struct object *object) static int get_object_mark(struct object *object) { - void *decoration = lookup_decoration(&idnums, object); - if (!decoration) + unsigned int j; + + /* nothing to lookup */ + if (!idnums.size) return 0; - return ptr_to_mark(decoration); + j = hash_obj(object, idnums.size); + for (;;) { + struct object_mark_entry *ref = idnums.entries + j; + if (ref->base == object) + return ref->mark; + if (!ref->base) + return 0; + if (++j == idnums.size) + j = 0; + } } static void show_progress(void) @@ -897,8 +956,7 @@ static void handle_tags_and_duplicates(void) static void export_marks(char *file) { unsigned int i; - uint32_t mark; - struct decoration_entry *deco = idnums.entries; + struct object_mark_entry *entry = idnums.entries; FILE *f; int e = 0; @@ -907,15 +965,14 @@ static void export_marks(char *file) die_errno("Unable to open marks file %s for writing.", file); for (i = 0; i < idnums.size; i++) { - if (deco->base && deco->base->type == 1) { - mark = ptr_to_mark(deco->decoration); - if (fprintf(f, ":%"PRIu32" %s\n", mark, - oid_to_hex(&deco->base->oid)) < 0) { + if (entry->base && entry->base->type == 1) { + if (fprintf(f, ":%"PRIu32" %s\n", entry->mark, + oid_to_hex(&entry->base->oid)) < 0) { e = 1; break; } } - deco++; + entry++; } e |= ferror(f); -- 2.17.0 ^ permalink raw reply related [flat|nested] 16+ messages in thread
* Re: [PATCH] fast-export: avoid NULL pointer arithmetic 2018-05-12 8:45 ` René Scharfe @ 2018-05-12 8:49 ` René Scharfe 2018-05-14 1:37 ` Junio C Hamano 1 sibling, 0 replies; 16+ messages in thread From: René Scharfe @ 2018-05-12 8:49 UTC (permalink / raw) To: Jeff King, Duy Nguyen; +Cc: Junio C Hamano, Git List, Johannes Schindelin Am 12.05.2018 um 10:45 schrieb René Scharfe: > Or we could roll our own custom hash map, as I mused in an earlier post. > That would duplicate quite a bit of code; are there reusable pieces > hidden within that could be extracted into common functions? At least it would allow us to save four bytes of padding per object on x64 by using a separate array for the hash map values; not sure how that would impact performance, though. --- builtin/fast-export.c | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-) diff --git a/builtin/fast-export.c b/builtin/fast-export.c index 627b0032f3..086fcaf9ea 100644 --- a/builtin/fast-export.c +++ b/builtin/fast-export.c @@ -72,13 +72,13 @@ static int parse_opt_tag_of_filtered_mode(const struct option *opt, struct object_mark_entry { const struct object *base; - uint32_t mark; }; struct object_marks { unsigned int size; unsigned int nr; struct object_mark_entry *entries; + uint32_t *marks; }; static struct object_marks idnums; @@ -98,14 +98,14 @@ static void set_object_mark(struct object_marks *n, const struct object *base, while (entries[j].base) { if (entries[j].base == base) { - entries[j].mark = mark; + n->marks[j] = mark; return; } if (++j >= size) j = 0; } entries[j].base = base; - entries[j].mark = mark; + n->marks[j] = mark; n->nr++; } @@ -114,19 +114,22 @@ static void grow_object_marks(struct object_marks *n) unsigned int i; unsigned int old_size = n->size; struct object_mark_entry *old_entries = n->entries; + uint32_t *old_marks = n->marks; n->size = (old_size + 1000) * 3 / 2; n->entries = xcalloc(n->size, sizeof(n->entries[0])); + n->marks = xcalloc(n->size, sizeof(n->marks[0])); n->nr = 0; for (i = 0; i < old_size; i++) { const struct object *base = old_entries[i].base; - uint32_t mark = old_entries[i].mark; + uint32_t mark = old_marks[i]; if (mark) set_object_mark(n, base, mark); } free(old_entries); + free(old_marks); } static int has_unshown_parent(struct commit *commit) @@ -236,7 +239,7 @@ static int get_object_mark(struct object *object) for (;;) { struct object_mark_entry *ref = idnums.entries + j; if (ref->base == object) - return ref->mark; + return idnums.marks[j]; if (!ref->base) return 0; if (++j == idnums.size) @@ -966,7 +969,7 @@ static void export_marks(char *file) for (i = 0; i < idnums.size; i++) { if (entry->base && entry->base->type == 1) { - if (fprintf(f, ":%"PRIu32" %s\n", entry->mark, + if (fprintf(f, ":%"PRIu32" %s\n", idnums.marks[i], oid_to_hex(&entry->base->oid)) < 0) { e = 1; break; -- 2.17.0 ^ permalink raw reply related [flat|nested] 16+ messages in thread
* Re: [PATCH] fast-export: avoid NULL pointer arithmetic 2018-05-12 8:45 ` René Scharfe 2018-05-12 8:49 ` René Scharfe @ 2018-05-14 1:37 ` Junio C Hamano 2018-05-15 19:36 ` René Scharfe 1 sibling, 1 reply; 16+ messages in thread From: Junio C Hamano @ 2018-05-14 1:37 UTC (permalink / raw) To: René Scharfe; +Cc: Jeff King, Duy Nguyen, Git List, Johannes Schindelin René Scharfe <l.s.r@web.de> writes: > Storing integer values in pointers is a trick that seems to have worked > so far for fast-export. A portable way to avoid that trick without > requiring more memory would be to use a union. > > Or we could roll our own custom hash map, as I mused in an earlier post. > That would duplicate quite a bit of code; are there reusable pieces > hidden within that could be extracted into common functions? Hmm, this together with your follow-up does not look too bad, but it does introduce quite a lot of code that could be refactored, so I am not sure if I really like it or not. > > --- > builtin/fast-export.c | 105 ++++++++++++++++++++++++++++++++---------- > 1 file changed, 81 insertions(+), 24 deletions(-) > > diff --git a/builtin/fast-export.c b/builtin/fast-export.c > index 530df12f05..627b0032f3 100644 > --- a/builtin/fast-export.c > +++ b/builtin/fast-export.c > @@ -14,7 +14,6 @@ > #include "diffcore.h" > #include "log-tree.h" > #include "revision.h" > -#include "decorate.h" > #include "string-list.h" > #include "utf8.h" > #include "parse-options.h" > @@ -71,9 +70,65 @@ static int parse_opt_tag_of_filtered_mode(const struct option *opt, > return 0; > } > > -static struct decoration idnums; > +struct object_mark_entry { > + const struct object *base; > + uint32_t mark; > +}; > + > +struct object_marks { > + unsigned int size; > + unsigned int nr; > + struct object_mark_entry *entries; > +}; > + > +static struct object_marks idnums; > static uint32_t last_idnum; > > +static unsigned int hash_obj(const struct object *obj, unsigned int n) > +{ > + return sha1hash(obj->oid.hash) % n; > +} > + > +static void set_object_mark(struct object_marks *n, const struct object *base, > + uint32_t mark) > +{ > + unsigned int size = n->size; > + struct object_mark_entry *entries = n->entries; > + unsigned int j = hash_obj(base, size); > + > + while (entries[j].base) { > + if (entries[j].base == base) { > + entries[j].mark = mark; > + return; > + } > + if (++j >= size) > + j = 0; > + } > + entries[j].base = base; > + entries[j].mark = mark; > + n->nr++; > +} > + > +static void grow_object_marks(struct object_marks *n) > +{ > + unsigned int i; > + unsigned int old_size = n->size; > + struct object_mark_entry *old_entries = n->entries; > + > + n->size = (old_size + 1000) * 3 / 2; > + n->entries = xcalloc(n->size, sizeof(n->entries[0])); > + n->nr = 0; > + > + for (i = 0; i < old_size; i++) { > + const struct object *base = old_entries[i].base; > + uint32_t mark = old_entries[i].mark; > + > + if (mark) > + set_object_mark(n, base, mark); > + } > + free(old_entries); > +} > + > static int has_unshown_parent(struct commit *commit) > { > struct commit_list *parent; > @@ -156,20 +211,13 @@ static void anonymize_path(struct strbuf *out, const char *path, > } > } > > -/* Since intptr_t is C99, we do not use it here */ > -static inline uint32_t *mark_to_ptr(uint32_t mark) > -{ > - return ((uint32_t *)NULL) + mark; > -} > - > -static inline uint32_t ptr_to_mark(void * mark) > -{ > - return (uint32_t *)mark - (uint32_t *)NULL; > -} > - > static inline void mark_object(struct object *object, uint32_t mark) > { > - add_decoration(&idnums, object, mark_to_ptr(mark)); > + unsigned int nr = idnums.nr + 1; > + > + if (nr > idnums.size * 2 / 3) > + grow_object_marks(&idnums); > + return set_object_mark(&idnums, object, mark); > } > > static inline void mark_next_object(struct object *object) > @@ -179,10 +227,21 @@ static inline void mark_next_object(struct object *object) > > static int get_object_mark(struct object *object) > { > - void *decoration = lookup_decoration(&idnums, object); > - if (!decoration) > + unsigned int j; > + > + /* nothing to lookup */ > + if (!idnums.size) > return 0; > - return ptr_to_mark(decoration); > + j = hash_obj(object, idnums.size); > + for (;;) { > + struct object_mark_entry *ref = idnums.entries + j; > + if (ref->base == object) > + return ref->mark; > + if (!ref->base) > + return 0; > + if (++j == idnums.size) > + j = 0; > + } > } > > static void show_progress(void) > @@ -897,8 +956,7 @@ static void handle_tags_and_duplicates(void) > static void export_marks(char *file) > { > unsigned int i; > - uint32_t mark; > - struct decoration_entry *deco = idnums.entries; > + struct object_mark_entry *entry = idnums.entries; > FILE *f; > int e = 0; > > @@ -907,15 +965,14 @@ static void export_marks(char *file) > die_errno("Unable to open marks file %s for writing.", file); > > for (i = 0; i < idnums.size; i++) { > - if (deco->base && deco->base->type == 1) { > - mark = ptr_to_mark(deco->decoration); > - if (fprintf(f, ":%"PRIu32" %s\n", mark, > - oid_to_hex(&deco->base->oid)) < 0) { > + if (entry->base && entry->base->type == 1) { > + if (fprintf(f, ":%"PRIu32" %s\n", entry->mark, > + oid_to_hex(&entry->base->oid)) < 0) { > e = 1; > break; > } > } > - deco++; > + entry++; > } > > e |= ferror(f); ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH] fast-export: avoid NULL pointer arithmetic 2018-05-14 1:37 ` Junio C Hamano @ 2018-05-15 19:36 ` René Scharfe 0 siblings, 0 replies; 16+ messages in thread From: René Scharfe @ 2018-05-15 19:36 UTC (permalink / raw) To: Junio C Hamano; +Cc: Jeff King, Duy Nguyen, Git List, Johannes Schindelin Am 14.05.2018 um 03:37 schrieb Junio C Hamano: > René Scharfe <l.s.r@web.de> writes: > >> Storing integer values in pointers is a trick that seems to have worked >> so far for fast-export. A portable way to avoid that trick without >> requiring more memory would be to use a union. >> >> Or we could roll our own custom hash map, as I mused in an earlier post. >> That would duplicate quite a bit of code; are there reusable pieces >> hidden within that could be extracted into common functions? > > Hmm, this together with your follow-up does not look too bad, but it > does introduce quite a lot of code that could be refactored, so I am > not sure if I really like it or not. Putting keys and values into separate arrays probably causes stores and lookups to hit (at least) two cache lines instead of just one. Not sure how much of an impact that has on the overall performance (probably not much), but we'd need at least a perf test for that. And we have enough hash map implementations already. Casting should be good enough for now, to avoid the compiler warning. René ^ permalink raw reply [flat|nested] 16+ messages in thread
end of thread, other threads:[~2018-05-15 19:36 UTC | newest] Thread overview: 16+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2018-05-09 21:06 [PATCH] fast-export: avoid NULL pointer arithmetic René Scharfe 2018-05-09 21:43 ` Johannes Schindelin 2018-05-10 9:24 ` René Scharfe 2018-05-10 10:51 ` Junio C Hamano 2018-05-10 19:47 ` René Scharfe 2018-05-11 2:16 ` Junio C Hamano 2018-05-11 4:49 ` Junio C Hamano 2018-05-11 6:19 ` Duy Nguyen 2018-05-11 8:56 ` Jeff King 2018-05-11 13:11 ` Duy Nguyen 2018-05-11 13:34 ` Duy Nguyen 2018-05-11 17:42 ` Jeff King 2018-05-12 8:45 ` René Scharfe 2018-05-12 8:49 ` René Scharfe 2018-05-14 1:37 ` Junio C Hamano 2018-05-15 19:36 ` René Scharfe
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.