[PATCH] fast-export: avoid NULL pointer arithmetic

[PATCH] fast-export: avoid NULL pointer arithmetic

[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.

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

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

[Johannes Schindelin]

[-- 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

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

[René Scharfe]

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)
> 

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

[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.  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.

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

[René Scharfe]

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é

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

[Junio C Hamano]

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?

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

[Junio C Hamano]

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.

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

[Duy Nguyen]

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

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

[Jeff King]

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

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

[Duy Nguyen]

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

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

[Duy Nguyen]

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< --

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

[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.

-Peff

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

[René Scharfe]

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

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

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

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

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

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

[René Scharfe]

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

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

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

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

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

[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.

>
> ---
>  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);

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

[René Scharfe]

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é