[PATCH/RFC 0/5] Some ThreadSanitizer-results

[PATCH/RFC 0/5] Some ThreadSanitizer-results

[Martin Ågren]

I tried running the test suite on Git compiled with ThreadSanitizer
(SANITIZE=thread). Maybe this series could be useful for someone else
trying to do the same. I needed the first patch to avoid warnings when
compiling, although it actually has nothing to do with threads.

The last four patches are about avoiding some issues where
ThreadSanitizer complains for reasonable reasons, but which to the best
of my understanding are not real problems. These patches could be useful
to make "actual" problems stand out more. Of course, if no-one ever runs
ThreadSanitizer, they are of little to no (or even negative) value...

I'll follow up with the two remaining issues that I found but which I do
not try to address in this series.

Martin

Martin Ågren (5):
  convert: initialize attr_action in convert_attrs
  pack-objects: take lock before accessing `remaining`
  Makefile: define GIT_THREAD_SANITIZER
  strbuf_reset: don't write to slopbuf with ThreadSanitizer
  ThreadSanitizer: add suppressions

 strbuf.h               | 12 ++++++++++++
 builtin/pack-objects.c |  6 ++++++
 convert.c              |  2 +-
 Makefile               |  3 +++
 .tsan-suppressions     | 12 ++++++++++++
 5 files changed, 34 insertions(+), 1 deletion(-)
 create mode 100644 .tsan-suppressions

-- 
2.14.1.151.gdfeca7a7e

[PATCH 1/5] convert: initialize attr_action in convert_attrs

[Martin Ågren]

convert_attrs populates a struct conv_attrs. The field attr_action is
not set in all code paths, but still one caller unconditionally reads
it. Since git_check_attr always returns the same value, we'll always end
up in the same code path and there is no problem right now. But
convert_attrs is obviously trying not to rely on such an
implementation-detail of another component.

Initialize attr_action to CRLF_UNDEFINED in the dead code path.

Actually, in the code path that /is/ taken, the variable is assigned to
twice and the first assignment has no effect. That's not wrong, but
let's remove that first assignment while we're here.

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
I hit a warning about attr_action possibly being uninitialized when
building with SANITIZE=thread. I guess it's some random interaction
between code added by tsan, the optimizer (-O3) and the warning
machinery. (This was with gcc 5.4.0.)

 convert.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/convert.c b/convert.c
index 1012462e3..943d957b4 100644
--- a/convert.c
+++ b/convert.c
@@ -1040,7 +1040,6 @@ static void convert_attrs(struct conv_attrs *ca, const char *path)
 		ca->crlf_action = git_path_check_crlf(ccheck + 4);
 		if (ca->crlf_action == CRLF_UNDEFINED)
 			ca->crlf_action = git_path_check_crlf(ccheck + 0);
-		ca->attr_action = ca->crlf_action;
 		ca->ident = git_path_check_ident(ccheck + 1);
 		ca->drv = git_path_check_convert(ccheck + 2);
 		if (ca->crlf_action != CRLF_BINARY) {
@@ -1058,6 +1057,7 @@ static void convert_attrs(struct conv_attrs *ca, const char *path)
 	} else {
 		ca->drv = NULL;
 		ca->crlf_action = CRLF_UNDEFINED;
+		ca->attr_action = CRLF_UNDEFINED;
 		ca->ident = 0;
 	}
 	if (ca->crlf_action == CRLF_TEXT)
-- 
2.14.1.151.gdfeca7a7e

Re: [PATCH 1/5] convert: initialize attr_action in convert_attrs

[Torsten Bögershausen]

On Tue, Aug 15, 2017 at 02:53:01PM +0200, Martin Ågren wrote:
> convert_attrs populates a struct conv_attrs. The field attr_action is
> not set in all code paths, but still one caller unconditionally reads
> it. Since git_check_attr always returns the same value, we'll always end
> up in the same code path and there is no problem right now. But
> convert_attrs is obviously trying not to rely on such an
> implementation-detail of another component.
> 
> Initialize attr_action to CRLF_UNDEFINED in the dead code path.
> 
> Actually, in the code path that /is/ taken, the variable is assigned to
> twice and the first assignment has no effect. That's not wrong, but
> let's remove that first assignment while we're here.
> 
> Signed-off-by: Martin Ågren <martin.agren@gmail.com>
> ---
> I hit a warning about attr_action possibly being uninitialized when
> building with SANITIZE=thread. I guess it's some random interaction
> between code added by tsan, the optimizer (-O3) and the warning
> machinery. (This was with gcc 5.4.0.)
> 
>  convert.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/convert.c b/convert.c
> index 1012462e3..943d957b4 100644
> --- a/convert.c
> +++ b/convert.c
> @@ -1040,7 +1040,6 @@ static void convert_attrs(struct conv_attrs *ca, const char *path)
>  		ca->crlf_action = git_path_check_crlf(ccheck + 4);
>  		if (ca->crlf_action == CRLF_UNDEFINED)
>  			ca->crlf_action = git_path_check_crlf(ccheck + 0);
> -		ca->attr_action = ca->crlf_action;

I don't think the removal of that line is correct.

>  		ca->ident = git_path_check_ident(ccheck + 1);
>  		ca->drv = git_path_check_convert(ccheck + 2);
>  		if (ca->crlf_action != CRLF_BINARY) {
> @@ -1058,6 +1057,7 @@ static void convert_attrs(struct conv_attrs *ca, const char *path)
>  	} else {
>  		ca->drv = NULL;
>  		ca->crlf_action = CRLF_UNDEFINED;
> +		ca->attr_action = CRLF_UNDEFINED;

But this one can be avoided, when the line
ca->attr_action = ca->crlf_action;
would move completely out of the "if/else" block.

>  		ca->ident = 0;
>  	}
>  	if (ca->crlf_action == CRLF_TEXT)
> -- 
> 2.14.1.151.gdfeca7a7e
> 

Thanks for spotting my mess.
What do you think about the following:


diff --git a/convert.c b/convert.c
index 1012462e3c..fd91b91ada 100644
--- a/convert.c
+++ b/convert.c
@@ -1040,7 +1040,6 @@ static void convert_attrs(struct conv_attrs *ca, const char *path)
 		ca->crlf_action = git_path_check_crlf(ccheck + 4);
 		if (ca->crlf_action == CRLF_UNDEFINED)
 			ca->crlf_action = git_path_check_crlf(ccheck + 0);
-		ca->attr_action = ca->crlf_action;
 		ca->ident = git_path_check_ident(ccheck + 1);
 		ca->drv = git_path_check_convert(ccheck + 2);
 		if (ca->crlf_action != CRLF_BINARY) {
@@ -1060,6 +1059,8 @@ static void convert_attrs(struct conv_attrs *ca, const char *path)
 		ca->crlf_action = CRLF_UNDEFINED;
 		ca->ident = 0;
 	}
+	/* Save attr and make a decision for action */
+	ca->attr_action = ca->crlf_action;
 	if (ca->crlf_action == CRLF_TEXT)
 		ca->crlf_action = text_eol_is_crlf() ? CRLF_TEXT_CRLF : CRLF_TEXT_INPUT;
 	if (ca->crlf_action == CRLF_UNDEFINED && auto_crlf == AUTO_CRLF_FALSE)

Re: [PATCH 1/5] convert: initialize attr_action in convert_attrs

[Torsten Bögershausen]

> > diff --git a/convert.c b/convert.c
> > index 1012462e3..943d957b4 100644
> > --- a/convert.c
> > +++ b/convert.c
> > @@ -1040,7 +1040,6 @@ static void convert_attrs(struct conv_attrs *ca, const char *path)
> >  		ca->crlf_action = git_path_check_crlf(ccheck + 4);
> >  		if (ca->crlf_action == CRLF_UNDEFINED)
> >  			ca->crlf_action = git_path_check_crlf(ccheck + 0);
> > -		ca->attr_action = ca->crlf_action;
> 
> I don't think the removal of that line is correct.

Sorry, that went wrong, should have been:
 I think that the line can be removed here.

Re: [PATCH 1/5] convert: initialize attr_action in convert_attrs

[Martin Ågren]

On 15 August 2017 at 16:17, Torsten Bögershausen <tboegi@web.de> wrote:
> On Tue, Aug 15, 2017 at 02:53:01PM +0200, Martin Ågren wrote:
>> convert_attrs populates a struct conv_attrs. The field attr_action is
>> not set in all code paths, but still one caller unconditionally reads
>> it. Since git_check_attr always returns the same value, we'll always end
>> up in the same code path and there is no problem right now. But
>> convert_attrs is obviously trying not to rely on such an
>> implementation-detail of another component.
>>
>> Initialize attr_action to CRLF_UNDEFINED in the dead code path.
>>
>> Actually, in the code path that /is/ taken, the variable is assigned to
>> twice and the first assignment has no effect. That's not wrong, but
>> let's remove that first assignment while we're here.
>>
>> Signed-off-by: Martin Ågren <martin.agren@gmail.com>
>> ---
>> I hit a warning about attr_action possibly being uninitialized when
>> building with SANITIZE=thread. I guess it's some random interaction
>> between code added by tsan, the optimizer (-O3) and the warning
>> machinery. (This was with gcc 5.4.0.)
>>
>>  convert.c | 2 +-
>>  1 file changed, 1 insertion(+), 1 deletion(-)
>>
>> diff --git a/convert.c b/convert.c
>> index 1012462e3..943d957b4 100644
>> --- a/convert.c
>> +++ b/convert.c
>> @@ -1040,7 +1040,6 @@ static void convert_attrs(struct conv_attrs *ca, const char *path)
>>               ca->crlf_action = git_path_check_crlf(ccheck + 4);
>>               if (ca->crlf_action == CRLF_UNDEFINED)
>>                       ca->crlf_action = git_path_check_crlf(ccheck + 0);
>> -             ca->attr_action = ca->crlf_action;
>
> I don't think the removal of that line is correct.

(Thanks for confirming in a follow-up mail that you meant that you /do/
think the removal is correct.)

>
>>               ca->ident = git_path_check_ident(ccheck + 1);
>>               ca->drv = git_path_check_convert(ccheck + 2);
>>               if (ca->crlf_action != CRLF_BINARY) {
>> @@ -1058,6 +1057,7 @@ static void convert_attrs(struct conv_attrs *ca, const char *path)
>>       } else {
>>               ca->drv = NULL;
>>               ca->crlf_action = CRLF_UNDEFINED;
>> +             ca->attr_action = CRLF_UNDEFINED;
>
> But this one can be avoided, when the line
> ca->attr_action = ca->crlf_action;
> would move completely out of the "if/else" block.
>
>>               ca->ident = 0;
>>       }
>>       if (ca->crlf_action == CRLF_TEXT)
>> --
>> 2.14.1.151.gdfeca7a7e
>>
>
> Thanks for spotting my mess.
> What do you think about the following:
>
>
> diff --git a/convert.c b/convert.c
> index 1012462e3c..fd91b91ada 100644
> --- a/convert.c
> +++ b/convert.c
> @@ -1040,7 +1040,6 @@ static void convert_attrs(struct conv_attrs *ca, const char *path)
>                 ca->crlf_action = git_path_check_crlf(ccheck + 4);
>                 if (ca->crlf_action == CRLF_UNDEFINED)
>                         ca->crlf_action = git_path_check_crlf(ccheck + 0);
> -               ca->attr_action = ca->crlf_action;
>                 ca->ident = git_path_check_ident(ccheck + 1);
>                 ca->drv = git_path_check_convert(ccheck + 2);
>                 if (ca->crlf_action != CRLF_BINARY) {
> @@ -1060,6 +1059,8 @@ static void convert_attrs(struct conv_attrs *ca, const char *path)
>                 ca->crlf_action = CRLF_UNDEFINED;
>                 ca->ident = 0;
>         }
> +       /* Save attr and make a decision for action */
> +       ca->attr_action = ca->crlf_action;
>         if (ca->crlf_action == CRLF_TEXT)
>                 ca->crlf_action = text_eol_is_crlf() ? CRLF_TEXT_CRLF : CRLF_TEXT_INPUT;
>         if (ca->crlf_action == CRLF_UNDEFINED && auto_crlf == AUTO_CRLF_FALSE)

Yeah, makes lots of sense. Then we could also remove the second
assignment to attr_action. That is, this function would set attr_action
at one place, always. I'll do this in a v2.

Thanks.

[PATCH 2/5] pack-objects: take lock before accessing `remaining`

[Martin Ågren]

When checking the conditional of "while (me->remaining)", we did not
hold the lock. Calling find_deltas would still be safe, since it checks
"remaining" (after taking the lock) and is able to handle all values. In
fact, this could (currently) not trigger any bug: a bug could happen if
`remaining` transitioning from zero to non-zero races with the evaluation
of the while-condition, but these are always separated by the
data_ready-mechanism.

Make sure we have the lock when we read `remaining`. This does mean we
release it just so that find_deltas can take it immediately again. We
could tweak the contract so that the lock should be taken before calling
find_deltas, but let's defer that until someone can actually show that
"unlock+lock" has a measurable negative impact.

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
I don't think this corrects any real error. The benefits of this patch
would be "future-proofs things slightly" and "silences tsan, so that
other errors don't drown in noise". Feel free to tell me those benefits
are negligible and that this change actually hurts.

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

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index c753e9237..bd391e97a 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -2170,7 +2170,10 @@ static void *threaded_find_deltas(void *arg)
 {
 	struct thread_params *me = arg;
 
+	progress_lock();
 	while (me->remaining) {
+		progress_unlock();
+
 		find_deltas(me->list, &me->remaining,
 			    me->window, me->depth, me->processed);
 
@@ -2192,7 +2195,10 @@ static void *threaded_find_deltas(void *arg)
 			pthread_cond_wait(&me->cond, &me->mutex);
 		me->data_ready = 0;
 		pthread_mutex_unlock(&me->mutex);
+
+		progress_lock();
 	}
+	progress_unlock();
 	/* leave ->working 1 so that this doesn't get more work assigned */
 	return NULL;
 }
-- 
2.14.1.151.gdfeca7a7e

Re: [PATCH 2/5] pack-objects: take lock before accessing `remaining`

[Johannes Sixt]

Am 15.08.2017 um 14:53 schrieb Martin Ågren:
> When checking the conditional of "while (me->remaining)", we did not
> hold the lock. Calling find_deltas would still be safe, since it checks
> "remaining" (after taking the lock) and is able to handle all values. In
> fact, this could (currently) not trigger any bug: a bug could happen if
> `remaining` transitioning from zero to non-zero races with the evaluation
> of the while-condition, but these are always separated by the
> data_ready-mechanism.
> 
> Make sure we have the lock when we read `remaining`. This does mean we
> release it just so that find_deltas can take it immediately again. We
> could tweak the contract so that the lock should be taken before calling
> find_deltas, but let's defer that until someone can actually show that
> "unlock+lock" has a measurable negative impact.
> 
> Signed-off-by: Martin Ågren <martin.agren@gmail.com>
> ---
> I don't think this corrects any real error. The benefits of this patch
> would be "future-proofs things slightly" and "silences tsan, so that
> other errors don't drown in noise". Feel free to tell me those benefits
> are negligible and that this change actually hurts.
> 
>   builtin/pack-objects.c | 6 ++++++
>   1 file changed, 6 insertions(+)
> 
> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
> index c753e9237..bd391e97a 100644
> --- a/builtin/pack-objects.c
> +++ b/builtin/pack-objects.c
> @@ -2170,7 +2170,10 @@ static void *threaded_find_deltas(void *arg)
>   {
>   	struct thread_params *me = arg;
>   
> +	progress_lock();
>   	while (me->remaining) {
> +		progress_unlock();
> +
>   		find_deltas(me->list, &me->remaining,
>   			    me->window, me->depth, me->processed);
>   
> @@ -2192,7 +2195,10 @@ static void *threaded_find_deltas(void *arg)
>   			pthread_cond_wait(&me->cond, &me->mutex);
>   		me->data_ready = 0;
>   		pthread_mutex_unlock(&me->mutex);
> +
> +		progress_lock();
>   	}
> +	progress_unlock();
>   	/* leave ->working 1 so that this doesn't get more work assigned */
>   	return NULL;
>   }
> 

It is correct that this access of me->remaining requires a lock. It 
could be solved in the way you did. I tried to do it differently, but 
all cleaner solutions that I can think of are overkill...

-- Hannes

[PATCH 3/5] Makefile: define GIT_THREAD_SANITIZER

[Martin Ågren]

When using ThreadSanitizer (tsan), it can be useful to avoid triggering
false or irrelevant alarms. This should obviously be done with care and
not to paper over real problems. Detecting that tsan is in use in a
cross-compiler way is non-trivial.

Tie into our existing SANITIZE=...-framework and define
GIT_THREAD_SANITIZER when we are compiling for tsan.

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
 Makefile | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/Makefile b/Makefile
index 461c845d3..e77a60d1f 100644
--- a/Makefile
+++ b/Makefile
@@ -1033,6 +1033,9 @@ BASIC_CFLAGS += -fno-omit-frame-pointer
 ifneq ($(filter undefined,$(SANITIZERS)),)
 BASIC_CFLAGS += -DNO_UNALIGNED_LOADS
 endif
+ifneq ($(filter thread,$(SANITIZERS)),)
+BASIC_CFLAGS += -DGIT_THREAD_SANITIZER
+endif
 endif
 
 ifndef sysconfdir
-- 
2.14.1.151.gdfeca7a7e

[PATCH 4/5] strbuf_reset: don't write to slopbuf with ThreadSanitizer

[Martin Ågren]

If two threads have one freshly initialized string buffer each and call
strbuf_reset on them at roughly the same time, both threads will be
writing a '\0' to strbuf_slopbuf. That is not a problem in practice
since it doesn't matter in which order the writes happen. But
ThreadSanitizer will consider this a race.

When compiling with GIT_THREAD_SANITIZER, avoid writing to
strbuf_slopbuf. Let's instead assert on the first byte of strbuf_slopbuf
being '\0', since it ensures the promised invariant of "buf[len] ==
'\0'". (Writing to strbuf_slopbuf is normally bad, but could become even
more bad if we stop covering it up in strbuf_reset.)

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
 strbuf.h | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/strbuf.h b/strbuf.h
index e705b94db..295654d39 100644
--- a/strbuf.h
+++ b/strbuf.h
@@ -153,7 +153,19 @@ static inline void strbuf_setlen(struct strbuf *sb, size_t len)
 /**
  * Empty the buffer by setting the size of it to zero.
  */
+#ifdef GIT_THREAD_SANITIZER
+#define strbuf_reset(sb)						\
+	do {								\
+		struct strbuf *_sb = sb; 				\
+		_sb->len = 0;						\
+		if (_sb->buf == strbuf_slopbuf)				\
+			assert(!strbuf_slopbuf[0]);			\
+		else							\
+			_sb->buf[0] = '\0';				\
+	} while (0)
+#else
 #define strbuf_reset(sb)  strbuf_setlen(sb, 0)
+#endif
 
 
 /**
-- 
2.14.1.151.gdfeca7a7e

Re: [PATCH 4/5] strbuf_reset: don't write to slopbuf with ThreadSanitizer

[Junio C Hamano]

Martin Ågren <martin.agren@gmail.com> writes:

> If two threads have one freshly initialized string buffer each and call
> strbuf_reset on them at roughly the same time, both threads will be
> writing a '\0' to strbuf_slopbuf. That is not a problem in practice
> since it doesn't matter in which order the writes happen. But
> ThreadSanitizer will consider this a race.
>
> When compiling with GIT_THREAD_SANITIZER, avoid writing to
> strbuf_slopbuf. Let's instead assert on the first byte of strbuf_slopbuf
> being '\0', since it ensures the promised invariant of "buf[len] ==
> '\0'". (Writing to strbuf_slopbuf is normally bad, but could become even
> more bad if we stop covering it up in strbuf_reset.)
>
> Signed-off-by: Martin Ågren <martin.agren@gmail.com>
> ---
>  strbuf.h | 12 ++++++++++++
>  1 file changed, 12 insertions(+)
>
> diff --git a/strbuf.h b/strbuf.h
> index e705b94db..295654d39 100644
> --- a/strbuf.h
> +++ b/strbuf.h
> @@ -153,7 +153,19 @@ static inline void strbuf_setlen(struct strbuf *sb, size_t len)
>  /**
>   * Empty the buffer by setting the size of it to zero.
>   */
> +#ifdef GIT_THREAD_SANITIZER
> +#define strbuf_reset(sb)						\
> +	do {								\
> +		struct strbuf *_sb = sb; 				\
> +		_sb->len = 0;						\
> +		if (_sb->buf == strbuf_slopbuf)				\
> +			assert(!strbuf_slopbuf[0]);			\
> +		else							\
> +			_sb->buf[0] = '\0';				\
> +	} while (0)
> +#else
>  #define strbuf_reset(sb)  strbuf_setlen(sb, 0)
> +#endif
>  
>  
>  /**

The strbuf_slopbuf[] is a shared resource that is expected by
everybody to stay a holder of a NUL.  Even though it is defined as
"char [1]", it in spirit ought to be considered const.  And from
that point of view, your new definition that is conditionally used
only when sanitizer is in use _is_ the more correct one than the
current "we do not care if it is slopbuf, we are writing \0 so it
will be no-op anyway" code.

I wonder if we excessively call strbuf_reset() in the real code to
make your version unacceptably expensive?  If not, I somehow feel
that using this version unconditionally may be a better approach.

What happens when a caller calls "strbuf_setlen(&sb, 0)" on a strbuf
that happens to have nothing and whose buffer still points at the
slopbuf (instead of calling _reset())?  Shouldn't your patch fix
that function instead, i.e. something like the following without the
above?  Is that make things noticeably and measurably too expensive?

Thanks.

 strbuf.h | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/strbuf.h b/strbuf.h
index 2075384e0b..1a77fe146a 100644
--- a/strbuf.h
+++ b/strbuf.h
@@ -147,7 +147,10 @@ static inline void strbuf_setlen(struct strbuf *sb, size_t len)
 	if (len > (sb->alloc ? sb->alloc - 1 : 0))
 		die("BUG: strbuf_setlen() beyond buffer");
 	sb->len = len;
-	sb->buf[len] = '\0';
+	if (sb->buf != strbuf_slopbuf)
+		sb->buf[len] = '\0';
+	else
+		assert(!strbuf_slopbuf[0]);
 }
 
 /**

Re: [PATCH 4/5] strbuf_reset: don't write to slopbuf with ThreadSanitizer

[Martin Ågren]

On 15 August 2017 at 20:43, Junio C Hamano <gitster@pobox.com> wrote:
> Martin Ågren <martin.agren@gmail.com> writes:
>
>> If two threads have one freshly initialized string buffer each and call
>> strbuf_reset on them at roughly the same time, both threads will be
>> writing a '\0' to strbuf_slopbuf. That is not a problem in practice
>> since it doesn't matter in which order the writes happen. But
>> ThreadSanitizer will consider this a race.
>>
>> When compiling with GIT_THREAD_SANITIZER, avoid writing to
>> strbuf_slopbuf. Let's instead assert on the first byte of strbuf_slopbuf
>> being '\0', since it ensures the promised invariant of "buf[len] ==
>> '\0'". (Writing to strbuf_slopbuf is normally bad, but could become even
>> more bad if we stop covering it up in strbuf_reset.)
>>
>> Signed-off-by: Martin Ågren <martin.agren@gmail.com>
>> ---
>>  strbuf.h | 12 ++++++++++++
>>  1 file changed, 12 insertions(+)
>>
>> diff --git a/strbuf.h b/strbuf.h
>> index e705b94db..295654d39 100644
>> --- a/strbuf.h
>> +++ b/strbuf.h
>> @@ -153,7 +153,19 @@ static inline void strbuf_setlen(struct strbuf *sb, size_t len)
>>  /**
>>   * Empty the buffer by setting the size of it to zero.
>>   */
>> +#ifdef GIT_THREAD_SANITIZER
>> +#define strbuf_reset(sb)                                             \
>> +     do {                                                            \
>> +             struct strbuf *_sb = sb;                                \
>> +             _sb->len = 0;                                           \
>> +             if (_sb->buf == strbuf_slopbuf)                         \
>> +                     assert(!strbuf_slopbuf[0]);                     \
>> +             else                                                    \
>> +                     _sb->buf[0] = '\0';                             \
>> +     } while (0)
>> +#else
>>  #define strbuf_reset(sb)  strbuf_setlen(sb, 0)
>> +#endif
>>
>>
>>  /**
>
> The strbuf_slopbuf[] is a shared resource that is expected by
> everybody to stay a holder of a NUL.  Even though it is defined as
> "char [1]", it in spirit ought to be considered const.  And from
> that point of view, your new definition that is conditionally used
> only when sanitizer is in use _is_ the more correct one than the
> current "we do not care if it is slopbuf, we are writing \0 so it
> will be no-op anyway" code.
>
> I wonder if we excessively call strbuf_reset() in the real code to
> make your version unacceptably expensive?  If not, I somehow feel
> that using this version unconditionally may be a better approach.
>
> What happens when a caller calls "strbuf_setlen(&sb, 0)" on a strbuf
> that happens to have nothing and whose buffer still points at the
> slopbuf (instead of calling _reset())?  Shouldn't your patch fix
> that function instead, i.e. something like the following without the
> above?  Is that make things noticeably and measurably too expensive?

Good thinking. There are about 300 users of strbuf_reset and 10 users of
strbuf_setlen(., 0) with a literal zero. Obviously, there might be more
users which end up setting the length to 0 for some reason or other. So
your idea seems the better one. I would assume that whoever resets a
buffer is about to add something to it, which should be more expensive,
but that's obviously just hand-waving. I'll see if I can find some
interesting caller and/or performance numbers.

>  strbuf.h | 5 ++++-
>  1 file changed, 4 insertions(+), 1 deletion(-)
>
> diff --git a/strbuf.h b/strbuf.h
> index 2075384e0b..1a77fe146a 100644
> --- a/strbuf.h
> +++ b/strbuf.h
> @@ -147,7 +147,10 @@ static inline void strbuf_setlen(struct strbuf *sb, size_t len)
>         if (len > (sb->alloc ? sb->alloc - 1 : 0))
>                 die("BUG: strbuf_setlen() beyond buffer");
>         sb->len = len;
> -       sb->buf[len] = '\0';
> +       if (sb->buf != strbuf_slopbuf)
> +               sb->buf[len] = '\0';
> +       else
> +               assert(!strbuf_slopbuf[0]);
>  }
>
>  /**

When writing my patch, I used assert() and figured that with tsan, we're
in some sort of "debug"-mode anyway. If we decide to always do the
check, would it make sense to do "else if (strbuf_slopbuf[0]) BUG(..);"
instead of the assert? Or, if we do prefer the assert, would the
performance-worry be moot?

Thanks for the feedback.

Re: [PATCH 4/5] strbuf_reset: don't write to slopbuf with ThreadSanitizer

[Junio C Hamano]

Martin Ågren <martin.agren@gmail.com> writes:

>> diff --git a/strbuf.h b/strbuf.h
>> index 2075384e0b..1a77fe146a 100644
>> --- a/strbuf.h
>> +++ b/strbuf.h
>> @@ -147,7 +147,10 @@ static inline void strbuf_setlen(struct strbuf *sb, size_t len)
>>         if (len > (sb->alloc ? sb->alloc - 1 : 0))
>>                 die("BUG: strbuf_setlen() beyond buffer");
>>         sb->len = len;
>> -       sb->buf[len] = '\0';
>> +       if (sb->buf != strbuf_slopbuf)
>> +               sb->buf[len] = '\0';
>> +       else
>> +               assert(!strbuf_slopbuf[0]);
>>  }
>>
>>  /**
>
> When writing my patch, I used assert() and figured that with tsan, we're
> in some sort of "debug"-mode anyway. If we decide to always do the
> check, would it make sense to do "else if (strbuf_slopbuf[0]) BUG(..);"
> instead of the assert? Or, if we do prefer the assert, would the
> performance-worry be moot?

I wasn't thinking about performance impact of having an assert();
the use of it in the above was merely copied from yours ;-)

[PATCH 5/5] ThreadSanitizer: add suppressions

[Martin Ågren]

Add .tsan-suppressions for want_color() and transfer_debug(). Both of
these use the pattern

	static int foo = -1;
	if (foo == -1)
		foo = func();

where func always returns the same value. This can cause ThreadSanitizer
to diagnose a race when foo is written from two threads, although it
doesn't matter in practice since it's always the same value that is
written.

The suppressions-file is used by setting the environment variable
TSAN_OPTIONS to, e.g., "suppressions=$(pwd)/.tsan-suppressions". Observe
that relative paths such as ".tsan-suppressions" might not work.

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
I am no memory-model expert. Maybe (aligned) stores and loads of int are
not actually atomic on all the various hardware that Git wants to run
on. Or maybe the compiler is allowed to compile them into 4 1-byte
accesses anyway...

 .tsan-suppressions | 12 ++++++++++++
 1 file changed, 12 insertions(+)
 create mode 100644 .tsan-suppressions

diff --git a/.tsan-suppressions b/.tsan-suppressions
new file mode 100644
index 000000000..910c02e59
--- /dev/null
+++ b/.tsan-suppressions
@@ -0,0 +1,12 @@
+# Suppressions for ThreadSanitizer (tsan).
+#
+# This file is used by setting the environment variable TSAN_OPTIONS to, e.g.,
+# "suppressions=$(pwd)/.tsan-suppressions". Observe that relative paths such as
+# ".tsan-suppressions" might not work.
+#
+# These suppressions can be, e.g., that a static variable is written to and it
+# is always the same value being written, so it doesn't really matter that two
+# or more such writes race.
+
+race:^want_color$
+race:^transfer_debug$
-- 
2.14.1.151.gdfeca7a7e

tsan: t3008: hashmap_add touches size from multiple threads

[Martin Ågren]

Using SANITIZE=thread made t3008-ls-files-lazy-init-name-hash.sh hit
the potential race below.

What seems to happen is, threaded_lazy_init_name_hash ends up using
hashmap_add on the_index.dir_hash from two threads in a way that tsan
considers racy. While the buckets each have their own mutex, the "size"
does not. So it might end up with the wrong (lower) value. The size is
used to determine when to resize, but that should be fine, since
resizing is turned off due to threading anyway.

If the size is ever used for something else, the consequences might
range from cosmetic error to devastating. I have a "feeling" the size is
not used at the time, although maybe it is, in some roundabout way which
I'm not seeing.

Martin

WARNING: ThreadSanitizer: data race (pid=10554)
  Read of size 4 at 0x00000082d488 by thread T2 (mutexes: write M16):
    #0 hashmap_add hashmap.c:209 (test-lazy-init-name-hash+0x000000438b7d)
    #1 hash_dir_entry_with_parent_and_prefix name-hash.c:302 (test-lazy-init-name-hash+0x00000043ea6c)
    #2 handle_range_dir name-hash.c:347 (test-lazy-init-name-hash+0x00000043ea6c)
    #3 handle_range_1 name-hash.c:415 (test-lazy-init-name-hash+0x00000043ea6c)
    #4 lazy_dir_thread_proc name-hash.c:471 (test-lazy-init-name-hash+0x00000043ea6c)
    #5 <null> <null> (libtsan.so.0+0x0000000230d9)

  Previous write of size 4 at 0x00000082d488 by thread T1 (mutexes: write M31):
    #0 hashmap_add hashmap.c:209 (test-lazy-init-name-hash+0x000000438b90)
    #1 hash_dir_entry_with_parent_and_prefix name-hash.c:302 (test-lazy-init-name-hash+0x00000043e0f2)
    #2 handle_range_dir name-hash.c:347 (test-lazy-init-name-hash+0x00000043e0f2)
    #3 handle_range_1 name-hash.c:415 (test-lazy-init-name-hash+0x00000043e0f2)
    #4 handle_range_dir name-hash.c:380 (test-lazy-init-name-hash+0x00000043e709)
    #5 handle_range_1 name-hash.c:415 (test-lazy-init-name-hash+0x00000043e709)
    #6 lazy_dir_thread_proc name-hash.c:471 (test-lazy-init-name-hash+0x00000043e709)
    #7 <null> <null> (libtsan.so.0+0x0000000230d9)

  Location is global 'the_index' of size 208 at 0x00000082d400 (test-lazy-init-name-hash+0x00000082d488)

  Mutex M16 (0x7d640001a5b8) created at:
    #0 pthread_mutex_init <null> (libtsan.so.0+0x0000000280b5)
    #1 init_recursive_mutex thread-utils.c:73 (test-lazy-init-name-hash+0x0000004d829b)
    #2 init_dir_mutex name-hash.c:241 (test-lazy-init-name-hash+0x00000043d714)
    #3 threaded_lazy_init_name_hash name-hash.c:526 (test-lazy-init-name-hash+0x00000043d714)
    #4 lazy_init_name_hash name-hash.c:588 (test-lazy-init-name-hash+0x00000043d714)
    #5 lazy_init_name_hash name-hash.c:581 (test-lazy-init-name-hash+0x00000043ec34)
    #6 test_lazy_init_name_hash name-hash.c:613 (test-lazy-init-name-hash+0x00000043ec34)
    #7 time_runs t/helper/test-lazy-init-name-hash.c:74 (test-lazy-init-name-hash+0x000000405ac2)
    #8 cmd_main t/helper/test-lazy-init-name-hash.c:261 (test-lazy-init-name-hash+0x0000004066c1)
    #9 main common-main.c:43 (test-lazy-init-name-hash+0x000000404f91)

  Mutex M31 (0x7d640001a810) created at:
    #0 pthread_mutex_init <null> (libtsan.so.0+0x0000000280b5)
    #1 init_recursive_mutex thread-utils.c:73 (test-lazy-init-name-hash+0x0000004d829b)
    #2 init_dir_mutex name-hash.c:241 (test-lazy-init-name-hash+0x00000043d714)
    #3 threaded_lazy_init_name_hash name-hash.c:526 (test-lazy-init-name-hash+0x00000043d714)
    #4 lazy_init_name_hash name-hash.c:588 (test-lazy-init-name-hash+0x00000043d714)
    #5 lazy_init_name_hash name-hash.c:581 (test-lazy-init-name-hash+0x00000043ec34)
    #6 test_lazy_init_name_hash name-hash.c:613 (test-lazy-init-name-hash+0x00000043ec34)
    #7 time_runs t/helper/test-lazy-init-name-hash.c:74 (test-lazy-init-name-hash+0x000000405ac2)
    #8 cmd_main t/helper/test-lazy-init-name-hash.c:261 (test-lazy-init-name-hash+0x0000004066c1)
    #9 main common-main.c:43 (test-lazy-init-name-hash+0x000000404f91)

  Thread T2 (tid=10557, running) created by main thread at:
    #0 pthread_create <null> (libtsan.so.0+0x000000027577)
    #1 threaded_lazy_init_name_hash name-hash.c:541 (test-lazy-init-name-hash+0x00000043d7ab)
    #2 lazy_init_name_hash name-hash.c:588 (test-lazy-init-name-hash+0x00000043d7ab)
    #3 lazy_init_name_hash name-hash.c:581 (test-lazy-init-name-hash+0x00000043ec34)
    #4 test_lazy_init_name_hash name-hash.c:613 (test-lazy-init-name-hash+0x00000043ec34)
    #5 time_runs t/helper/test-lazy-init-name-hash.c:74 (test-lazy-init-name-hash+0x000000405ac2)
    #6 cmd_main t/helper/test-lazy-init-name-hash.c:261 (test-lazy-init-name-hash+0x0000004066c1)
    #7 main common-main.c:43 (test-lazy-init-name-hash+0x000000404f91)

  Thread T1 (tid=10556, finished) created by main thread at:
    #0 pthread_create <null> (libtsan.so.0+0x000000027577)
    #1 threaded_lazy_init_name_hash name-hash.c:541 (test-lazy-init-name-hash+0x00000043d7ab)
    #2 lazy_init_name_hash name-hash.c:588 (test-lazy-init-name-hash+0x00000043d7ab)
    #3 lazy_init_name_hash name-hash.c:581 (test-lazy-init-name-hash+0x00000043ec34)
    #4 test_lazy_init_name_hash name-hash.c:613 (test-lazy-init-name-hash+0x00000043ec34)
    #5 time_runs t/helper/test-lazy-init-name-hash.c:74 (test-lazy-init-name-hash+0x000000405ac2)
    #6 cmd_main t/helper/test-lazy-init-name-hash.c:261 (test-lazy-init-name-hash+0x0000004066c1)
    #7 main common-main.c:43 (test-lazy-init-name-hash+0x000000404f91)

SUMMARY: ThreadSanitizer: data race hashmap.c:209 hashmap_add

Re: tsan: t3008: hashmap_add touches size from multiple threads

[Jeff Hostetler]

On 8/15/2017 8:53 AM, Martin Ågren wrote:
> Using SANITIZE=thread made t3008-ls-files-lazy-init-name-hash.sh hit
> the potential race below.
> 
> What seems to happen is, threaded_lazy_init_name_hash ends up using
> hashmap_add on the_index.dir_hash from two threads in a way that tsan
> considers racy. While the buckets each have their own mutex, the "size"
> does not. So it might end up with the wrong (lower) value. The size is
> used to determine when to resize, but that should be fine, since
> resizing is turned off due to threading anyway.
 >
> If the size is ever used for something else, the consequences might
> range from cosmetic error to devastating. I have a "feeling" the size is
> not used at the time, although maybe it is, in some roundabout way which
> I'm not seeing.

Good catch!  Yes, the size field is unguarded.  The only references to
it that I found were used in _add() and _remove() in the need-to-rehash
check.

Since auto-rehash is turned off, this shouldn't be a problem, but it
does feel odd to have a possibly incorrect size due to races.

Rather than adding something like (a cross-platform version of)
InterlockedIncrement(), I'm wondering if it would be better to
disable/invalidate the size field when auto-rehash is turned off
so we don't have to worry about it.

Something like this:


$ git diff
diff --git a/hashmap.c b/hashmap.c
index 9b6a12859b..be97642daa 100644
--- a/hashmap.c
+++ b/hashmap.c
@@ -205,6 +205,9 @@ void hashmap_add(struct hashmap *map, void *entry)
         ((struct hashmap_entry *) entry)->next = map->table[b];
         map->table[b] = entry;

+       if (map->disallow_rehash)
+               return;
+
         /* fix size and rehash if appropriate */
         map->size++;
         if (map->size > map->grow_at)
@@ -223,6 +226,9 @@ void *hashmap_remove(struct hashmap *map, const void 
*key, const void *keydata)
         *e = old->next;
         old->next = NULL;

+       if (map->disallow_rehash)
+               return;
+
         /* fix size and rehash if appropriate */
         map->size--;
         if (map->size < map->shrink_at)
diff --git a/hashmap.h b/hashmap.h
index 7a8fa7fa3d..ec9541b981 100644
--- a/hashmap.h
+++ b/hashmap.h
@@ -183,7 +183,8 @@ struct hashmap {
         const void *cmpfn_data;

         /* total number of entries (0 means the hashmap is empty) */
-       unsigned int size;
+       /* -1 means size is unknown for threading reasons */
+       int size;

         /*
          * tablesize is the allocated size of the hash table. A non-0 value
@@ -360,6 +361,15 @@ int hashmap_bucket(const struct hashmap *map, 
unsigned int hash);
  static inline void hashmap_disallow_rehash(struct hashmap *map, 
unsigned value)
  {
         map->disallow_rehash = value;
+       if (value) {
+               /*
+                * Assume threaded operations starting, so don't
+                * try to keep size current.
+                */
+               size = -1;
+       } else {
+               /* TODO count items in all buckets and set size. */
+       }
  }

  /*


Jeff

Re: tsan: t3008: hashmap_add touches size from multiple threads

[Stefan Beller]

On Tue, Aug 15, 2017 at 10:59 AM, Jeff Hostetler <git@jeffhostetler.com> wrote:
>
>
> On 8/15/2017 8:53 AM, Martin Ågren wrote:
>>
>> Using SANITIZE=thread made t3008-ls-files-lazy-init-name-hash.sh hit
>> the potential race below.
>>
>> What seems to happen is, threaded_lazy_init_name_hash ends up using
>> hashmap_add on the_index.dir_hash from two threads in a way that tsan
>> considers racy. While the buckets each have their own mutex, the "size"
>> does not. So it might end up with the wrong (lower) value. The size is
>> used to determine when to resize, but that should be fine, since
>> resizing is turned off due to threading anyway.
>
>>
>>
>> If the size is ever used for something else, the consequences might
>> range from cosmetic error to devastating. I have a "feeling" the size is
>> not used at the time, although maybe it is, in some roundabout way which
>> I'm not seeing.
>
>
> Good catch!  Yes, the size field is unguarded.  The only references to
> it that I found were used in _add() and _remove() in the need-to-rehash
> check.
>
> Since auto-rehash is turned off, this shouldn't be a problem, but it
> does feel odd to have a possibly incorrect size due to races.
>
> Rather than adding something like (a cross-platform version of)
> InterlockedIncrement(), I'm wondering if it would be better to
> disable/invalidate the size field when auto-rehash is turned off
> so we don't have to worry about it.
>
> Something like this:
>
>
> $ git diff
> diff --git a/hashmap.c b/hashmap.c
> index 9b6a12859b..be97642daa 100644
> --- a/hashmap.c
> +++ b/hashmap.c
> @@ -205,6 +205,9 @@ void hashmap_add(struct hashmap *map, void *entry)
>         ((struct hashmap_entry *) entry)->next = map->table[b];
>         map->table[b] = entry;
>
> +       if (map->disallow_rehash)
> +               return;
> +
>         /* fix size and rehash if appropriate */
>         map->size++;
>         if (map->size > map->grow_at)
> @@ -223,6 +226,9 @@ void *hashmap_remove(struct hashmap *map, const void
> *key, const void *keydata)
>         *e = old->next;
>         old->next = NULL;
>
> +       if (map->disallow_rehash)
> +               return;
> +


Once we have these two checks, the check in rehash itself becomes
redundant (as any code path leading to the check in rehash already
had the check).

Which leads me to wonder if we want to make the size (in/de)crease
part of the rehash function, which could be

    adjust_size(struct hashmap *map, int n)

with `n` either +1 or -1 (the increase value). Depending on 'n', we could
compute the newsize for the potential rehash in that function as well.

Note sure if that is a cleaner internal API.

>         /* fix size and rehash if appropriate */
>         map->size--;
>         if (map->size < map->shrink_at)
> diff --git a/hashmap.h b/hashmap.h
> index 7a8fa7fa3d..ec9541b981 100644
> --- a/hashmap.h
> +++ b/hashmap.h
> @@ -183,7 +183,8 @@ struct hashmap {
>         const void *cmpfn_data;
>
>         /* total number of entries (0 means the hashmap is empty) */
> -       unsigned int size;
> +       /* -1 means size is unknown for threading reasons */
> +       int size;

This double-encodes the state of disallow_rehash (i.e. if we had
signed size, then the invariant disallow_rehash === (size < 0)
is true, such that we could omit either the flag and just check for
size < 0 or we do not need the negative size as any user would
need to check disallow_rehash first. Not sure which API is harder
to misuse. I'd think just having the size and getting rid of
disallow_rehash might be hard to to reused.

>
>         /*
>          * tablesize is the allocated size of the hash table. A non-0 value
> @@ -360,6 +361,15 @@ int hashmap_bucket(const struct hashmap *map, unsigned
> int hash);
>  static inline void hashmap_disallow_rehash(struct hashmap *map, unsigned
> value)
>  {
>         map->disallow_rehash = value;
> +       if (value) {
> +               /*
> +                * Assume threaded operations starting, so don't
> +                * try to keep size current.
> +                */
> +               size = -1;
> +       } else {
> +               /* TODO count items in all buckets and set size. */
> +       }
>  }
>
>  /*
>
>
> Jeff

Re: tsan: t3008: hashmap_add touches size from multiple threads

[Martin Ågren]

On 15 August 2017 at 20:17, Stefan Beller <sbeller@google.com> wrote:
> On Tue, Aug 15, 2017 at 10:59 AM, Jeff Hostetler <git@jeffhostetler.com> wrote:
>>
>>
>> On 8/15/2017 8:53 AM, Martin Ågren wrote:
>>>
>>> Using SANITIZE=thread made t3008-ls-files-lazy-init-name-hash.sh hit
>>> the potential race below.
>>>
>>> What seems to happen is, threaded_lazy_init_name_hash ends up using
>>> hashmap_add on the_index.dir_hash from two threads in a way that tsan
>>> considers racy. While the buckets each have their own mutex, the "size"
>>> does not. So it might end up with the wrong (lower) value. The size is
>>> used to determine when to resize, but that should be fine, since
>>> resizing is turned off due to threading anyway.
>>
>>>
>>>
>>> If the size is ever used for something else, the consequences might
>>> range from cosmetic error to devastating. I have a "feeling" the size is
>>> not used at the time, although maybe it is, in some roundabout way which
>>> I'm not seeing.
>>
>>
>> Good catch!  Yes, the size field is unguarded.  The only references to
>> it that I found were used in _add() and _remove() in the need-to-rehash
>> check.
>>
>> Since auto-rehash is turned off, this shouldn't be a problem, but it
>> does feel odd to have a possibly incorrect size due to races.
>>
>> Rather than adding something like (a cross-platform version of)
>> InterlockedIncrement(), I'm wondering if it would be better to
>> disable/invalidate the size field when auto-rehash is turned off
>> so we don't have to worry about it.
>>
>> Something like this:
>>
>>
>> $ git diff
>> diff --git a/hashmap.c b/hashmap.c
>> index 9b6a12859b..be97642daa 100644
>> --- a/hashmap.c
>> +++ b/hashmap.c
>> @@ -205,6 +205,9 @@ void hashmap_add(struct hashmap *map, void *entry)
>>         ((struct hashmap_entry *) entry)->next = map->table[b];
>>         map->table[b] = entry;
>>
>> +       if (map->disallow_rehash)
>> +               return;
>> +
>>         /* fix size and rehash if appropriate */
>>         map->size++;
>>         if (map->size > map->grow_at)
>> @@ -223,6 +226,9 @@ void *hashmap_remove(struct hashmap *map, const void
>> *key, const void *keydata)
>>         *e = old->next;
>>         old->next = NULL;
>>
>> +       if (map->disallow_rehash)
>> +               return;
>> +
>
>
> Once we have these two checks, the check in rehash itself becomes
> redundant (as any code path leading to the check in rehash already
> had the check).
>
> Which leads me to wonder if we want to make the size (in/de)crease
> part of the rehash function, which could be
>
>     adjust_size(struct hashmap *map, int n)
>
> with `n` either +1 or -1 (the increase value). Depending on 'n', we could
> compute the newsize for the potential rehash in that function as well.
>
> Note sure if that is a cleaner internal API.
>
>>         /* fix size and rehash if appropriate */
>>         map->size--;
>>         if (map->size < map->shrink_at)
>> diff --git a/hashmap.h b/hashmap.h
>> index 7a8fa7fa3d..ec9541b981 100644
>> --- a/hashmap.h
>> +++ b/hashmap.h
>> @@ -183,7 +183,8 @@ struct hashmap {
>>         const void *cmpfn_data;
>>
>>         /* total number of entries (0 means the hashmap is empty) */
>> -       unsigned int size;
>> +       /* -1 means size is unknown for threading reasons */
>> +       int size;
>
> This double-encodes the state of disallow_rehash (i.e. if we had
> signed size, then the invariant disallow_rehash === (size < 0)
> is true, such that we could omit either the flag and just check for
> size < 0 or we do not need the negative size as any user would
> need to check disallow_rehash first. Not sure which API is harder
> to misuse. I'd think just having the size and getting rid of
> disallow_rehash might be hard to to reused.

(Do you mean "might be hard to be misused"?)

One good thing about turning off the size-tracking with threading is
that someone who later wants to know the size in a threaded application
will not introduce any subtle bugs by misusing size, but will be forced
to provide and use some sort of InterlockedIncrement(). When/if that
change happens, it would be nice if no-one relied on the value of size
to say anything about threading. So it might make sense to have an
implementation-independent way of accessing disallow_rehash a.k.a.
(size < 0).

For example a function hashmap_disallow_rehash(), except that's
obviously taken. :-) Maybe the existing function would then be
hashmap_set_disallow_rehash(). Oh well..

>
>>
>>         /*
>>          * tablesize is the allocated size of the hash table. A non-0 value
>> @@ -360,6 +361,15 @@ int hashmap_bucket(const struct hashmap *map, unsigned
>> int hash);
>>  static inline void hashmap_disallow_rehash(struct hashmap *map, unsigned
>> value)
>>  {
>>         map->disallow_rehash = value;
>> +       if (value) {
>> +               /*
>> +                * Assume threaded operations starting, so don't
>> +                * try to keep size current.
>> +                */
>> +               size = -1;
>> +       } else {
>> +               /* TODO count items in all buckets and set size. */
>> +       }
>>  }
>>
>>  /*
>>
>>
>> Jeff

Re: tsan: t3008: hashmap_add touches size from multiple threads

[Stefan Beller]

>>>         /* total number of entries (0 means the hashmap is empty) */
>>> -       unsigned int size;
>>> +       /* -1 means size is unknown for threading reasons */
>>> +       int size;
>>
>> This double-encodes the state of disallow_rehash (i.e. if we had
>> signed size, then the invariant disallow_rehash === (size < 0)
>> is true, such that we could omit either the flag and just check for
>> size < 0 or we do not need the negative size as any user would
>> need to check disallow_rehash first. Not sure which API is harder
>> to misuse. I'd think just having the size and getting rid of
>> disallow_rehash might be hard to to reused.
>
> (Do you mean "might be hard to be misused"?)

yes, I do.

> One good thing about turning off the size-tracking with threading is
> that someone who later wants to know the size in a threaded application
> will not introduce any subtle bugs by misusing size, but will be forced
> to provide and use some sort of InterlockedIncrement().

agreed.

> When/if that
> change happens, it would be nice if no-one relied on the value of size
> to say anything about threading. So it might make sense to have an
> implementation-independent way of accessing disallow_rehash a.k.a.
> (size < 0).

Yes, and my point was whether we want to keep disallow_rehash around,
as when a patch as this is applied, we'd have it encoded twice,
both size < 0 as well as disallow_rehash set indicate the rehashing
disabled.

If we were to reduce it to one, we would not have "invalid" state possible
such as size < 0 and disallow_rehash = 0.

In the future we may have more options that make size impossible to
compute efficiently, such that in that case we'd want to know which
condition lead to it. In that case we'd want to have the flags around.

> For example a function hashmap_disallow_rehash(), except that's
> obviously taken. :-) Maybe the existing function would then be
> hashmap_set_disallow_rehash(). Oh well..

Not sure I understand this one.

Re: tsan: t3008: hashmap_add touches size from multiple threads

[Martin Ågren]

On 15 August 2017 at 20:48, Stefan Beller <sbeller@google.com> wrote:
>>>>         /* total number of entries (0 means the hashmap is empty) */
>>>> -       unsigned int size;
>>>> +       /* -1 means size is unknown for threading reasons */
>>>> +       int size;
>>>
>>> This double-encodes the state of disallow_rehash (i.e. if we had
>>> signed size, then the invariant disallow_rehash === (size < 0)
>>> is true, such that we could omit either the flag and just check for
>>> size < 0 or we do not need the negative size as any user would
>>> need to check disallow_rehash first. Not sure which API is harder
>>> to misuse. I'd think just having the size and getting rid of
>>> disallow_rehash might be hard to to reused.
>>
>> (Do you mean "might be hard to be misused"?)
>
> yes, I do.
>
>> One good thing about turning off the size-tracking with threading is
>> that someone who later wants to know the size in a threaded application
>> will not introduce any subtle bugs by misusing size, but will be forced
>> to provide and use some sort of InterlockedIncrement().
>
> agreed.
>
>> When/if that
>> change happens, it would be nice if no-one relied on the value of size
>> to say anything about threading. So it might make sense to have an
>> implementation-independent way of accessing disallow_rehash a.k.a.
>> (size < 0).
>
> Yes, and my point was whether we want to keep disallow_rehash around,
> as when a patch as this is applied, we'd have it encoded twice,
> both size < 0 as well as disallow_rehash set indicate the rehashing
> disabled.
>
> If we were to reduce it to one, we would not have "invalid" state possible
> such as size < 0 and disallow_rehash = 0.

Agreed.

> In the future we may have more options that make size impossible to
> compute efficiently, such that in that case we'd want to know which
> condition lead to it. In that case we'd want to have the flags around.

Good point.

>> For example a function hashmap_disallow_rehash(), except that's
>> obviously taken. :-) Maybe the existing function would then be
>> hashmap_set_disallow_rehash(). Oh well..
>
> Not sure I understand this one.

Sorry. What I meant was, if we drop the disallow_rehash-field, someone
might be tempted to use size < 0 (or size == -1) to answer the question
"is rehashing disallowed?". (Or "am I threaded?" which already is a
question which the hashmap as it is today doesn't know about.)

So instead of looking at "disallow_rehash" one should perhaps be calling
"hashmap_is_disallow_rehash()" or "hashmap_get_disallow_rehash()", which
would be implemented as "return disallow_rehash", or possibly "return
size == -1".

Except such names are, to the best of my understanding, not the Git-way,
so it should be, e.g., "hashmap_disallow_rehash()".

Except ... that name is taken.... So to free that name up, the existing
function should perhaps be renamed "hashmap_set_disallow_rehash()",
again assuming I've picked up the right conventions in my recent
browsing of the Git-code.

The final "Oh well" was a short form of "it began with an observation
which currently has no practical effect, and is slowly turning into a
chain of ideas on how to rebuild the interface".

Re: tsan: t3008: hashmap_add touches size from multiple threads

[Jeff Hostetler]

On 8/15/2017 3:21 PM, Martin Ågren wrote:
> On 15 August 2017 at 20:48, Stefan Beller <sbeller@google.com> wrote:
>>>>>          /* total number of entries (0 means the hashmap is empty) */
>>>>> -       unsigned int size;
>>>>> +       /* -1 means size is unknown for threading reasons */
>>>>> +       int size;
>>>>
>>>> This double-encodes the state of disallow_rehash (i.e. if we had
>>>> signed size, then the invariant disallow_rehash === (size < 0)
>>>> is true, such that we could omit either the flag and just check for
>>>> size < 0 or we do not need the negative size as any user would
>>>> need to check disallow_rehash first. Not sure which API is harder
>>>> to misuse. I'd think just having the size and getting rid of
>>>> disallow_rehash might be hard to to reused.
>>>
>>> (Do you mean "might be hard to be misused"?)
>>
>> yes, I do.
>>
>>> One good thing about turning off the size-tracking with threading is
>>> that someone who later wants to know the size in a threaded application
>>> will not introduce any subtle bugs by misusing size, but will be forced
>>> to provide and use some sort of InterlockedIncrement().
>>
>> agreed.
>>
>>> When/if that
>>> change happens, it would be nice if no-one relied on the value of size
>>> to say anything about threading. So it might make sense to have an
>>> implementation-independent way of accessing disallow_rehash a.k.a.
>>> (size < 0).
>>
>> Yes, and my point was whether we want to keep disallow_rehash around,
>> as when a patch as this is applied, we'd have it encoded twice,
>> both size < 0 as well as disallow_rehash set indicate the rehashing
>> disabled.
>>
>> If we were to reduce it to one, we would not have "invalid" state possible
>> such as size < 0 and disallow_rehash = 0.
> 
> Agreed.
> 
>> In the future we may have more options that make size impossible to
>> compute efficiently, such that in that case we'd want to know which
>> condition lead to it. In that case we'd want to have the flags around.
> 
> Good point.

I feel like we're trying to push hashmaps a little beyond
their capability.  I mean the core hashmap code is NOT thread
safe.  The caller is responsible for carefully controlling how
the hashmap is used and whatever locking strategy it wants --
whether it is a single lock on the entire hashmap -- or a set
of partition-specific locks like I created here.  Whatever the
strategy, it is outside of hashmap.[ch].

Perhaps it would be best to just define things as:
* let (size < 0) mean we choose not to compute/track it (without
   saying why).
* keep "disallow_rehash = 1" to mean we do not want automatic
   resizing (without saying why).

Thread-aware callers will set both.

Thread-aware callers (when finished with threaded operations)
can themselves choose whether to compute the correct size and
re-allow rehashing.  And we can add a method to hashmap.c to
re-calculate the size if we want.


In my lazy_init_name_hash() I set "disallow", do the threaded
code, and then unset "disallow" -- mainly to keep the usage
consistent with the non-threaded case.  I could just as easily
set "disallow" and leave it that way -- the question is whether
we care if the hashmap automatically resizes later.  (I don't.)


>>> For example a function hashmap_disallow_rehash(), except that's
>>> obviously taken. :-) Maybe the existing function would then be
>>> hashmap_set_disallow_rehash(). Oh well..
>>
>> Not sure I understand this one.
> 
> Sorry. What I meant was, if we drop the disallow_rehash-field, someone
> might be tempted to use size < 0 (or size == -1) to answer the question
> "is rehashing disallowed?". (Or "am I threaded?" which already is a
> question which the hashmap as it is today doesn't know about.)
> 
> So instead of looking at "disallow_rehash" one should perhaps be calling
> "hashmap_is_disallow_rehash()" or "hashmap_get_disallow_rehash()", which
> would be implemented as "return disallow_rehash", or possibly "return
> size == -1".
> 
> Except such names are, to the best of my understanding, not the Git-way,
> so it should be, e.g., "hashmap_disallow_rehash()".
> 
> Except ... that name is taken.... So to free that name up, the existing
> function should perhaps be renamed "hashmap_set_disallow_rehash()",
> again assuming I've picked up the right conventions in my recent
> browsing of the Git-code.
> 
> The final "Oh well" was a short form of "it began with an observation
> which currently has no practical effect, and is slowly turning into a
> chain of ideas on how to rebuild the interface".
> 

[PATCH] hashmap: address ThreadSanitizer concerns

[Jeff Hostetler]

From: Jeff Hostetler <jeffhost@microsoft.com>

This is to address concerns raised by ThreadSanitizer on the
mailing list about threaded unprotected R/W access to map.size with my previous
"disallow rehash" change (0607e10009ee4e37cb49b4cec8d28a9dda1656a4).

See:
https://public-inbox.org/git/adb37b70139fd1e2bac18bfd22c8b96683ae18eb.1502780344.git.martin.agren@gmail.com/

TODO  This version contains methods to disable item counting and automatic
rehashing independently.  Since the latter is implicit with the former, we
could get by with just the one, but I thought we could discuss it since it
does provide a little extra clarity of intent.


Jeff Hostetler (1):
  hashmap: add API to disable item counting when threaded

 attr.c                  | 14 ++++---
 builtin/describe.c      |  2 +-
 hashmap.c               | 31 +++++++++++-----
 hashmap.h               | 98 ++++++++++++++++++++++++++++++++++++++-----------
 name-hash.c             |  6 ++-
 t/helper/test-hashmap.c |  2 +-
 6 files changed, 113 insertions(+), 40 deletions(-)

-- 
2.9.3

[PATCH] hashmap: add API to disable item counting when threaded

[Jeff Hostetler]

From: Jeff Hostetler <jeffhost@microsoft.com>

This is to address concerns raised by ThreadSanitizer on the
mailing list about threaded unprotected R/W access to map.size with my previous
"disallow rehash" change (0607e10009ee4e37cb49b4cec8d28a9dda1656a4).  See:
https://public-inbox.org/git/adb37b70139fd1e2bac18bfd22c8b96683ae18eb.1502780344.git.martin.agren@gmail.com/

Add API to hashmap to disable item counting and to disable automatic rehashing.  
Also include APIs to re-enable item counting and automatica rehashing.

When item counting is disabled, the map.size field is invalid.  So to
prevent accidents, the field has been renamed and an accessor function
hashmap_get_size() has been added.  All direct references to this
field have been been updated.  And the name of the field changed
to map.private_size to communicate thie.

Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
---
 attr.c                  | 14 ++++---
 builtin/describe.c      |  2 +-
 hashmap.c               | 31 +++++++++++-----
 hashmap.h               | 98 ++++++++++++++++++++++++++++++++++++++-----------
 name-hash.c             |  6 ++-
 t/helper/test-hashmap.c |  2 +-
 6 files changed, 113 insertions(+), 40 deletions(-)

diff --git a/attr.c b/attr.c
index 56961f0..a987f37 100644
--- a/attr.c
+++ b/attr.c
@@ -149,10 +149,12 @@ struct all_attrs_item {
 static void all_attrs_init(struct attr_hashmap *map, struct attr_check *check)
 {
 	int i;
+	unsigned int size;
 
 	hashmap_lock(map);
 
-	if (map->map.size < check->all_attrs_nr)
+	size = hashmap_get_size(&map->map);
+	if (size < check->all_attrs_nr)
 		die("BUG: interned attributes shouldn't be deleted");
 
 	/*
@@ -161,13 +163,13 @@ static void all_attrs_init(struct attr_hashmap *map, struct attr_check *check)
 	 * field), reallocate the provided attr_check instance's all_attrs
 	 * field and fill each entry with its corresponding git_attr.
 	 */
-	if (map->map.size != check->all_attrs_nr) {
+	if (size != check->all_attrs_nr) {
 		struct attr_hash_entry *e;
 		struct hashmap_iter iter;
 		hashmap_iter_init(&map->map, &iter);
 
-		REALLOC_ARRAY(check->all_attrs, map->map.size);
-		check->all_attrs_nr = map->map.size;
+		REALLOC_ARRAY(check->all_attrs, size);
+		check->all_attrs_nr = size;
 
 		while ((e = hashmap_iter_next(&iter))) {
 			const struct git_attr *a = e->value;
@@ -235,10 +237,10 @@ static const struct git_attr *git_attr_internal(const char *name, int namelen)
 
 	if (!a) {
 		FLEX_ALLOC_MEM(a, name, name, namelen);
-		a->attr_nr = g_attr_hashmap.map.size;
+		a->attr_nr = hashmap_get_size(&g_attr_hashmap.map);
 
 		attr_hashmap_add(&g_attr_hashmap, a->name, namelen, a);
-		assert(a->attr_nr == (g_attr_hashmap.map.size - 1));
+		assert(a->attr_nr == (hashmap_get_size(&g_attr_hashmap.map) - 1));
 	}
 
 	hashmap_unlock(&g_attr_hashmap);
diff --git a/builtin/describe.c b/builtin/describe.c
index 89ea1cd..1e3cbc7 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -505,7 +505,7 @@ int cmd_describe(int argc, const char **argv, const char *prefix)
 
 	hashmap_init(&names, (hashmap_cmp_fn) commit_name_cmp, NULL, 0);
 	for_each_rawref(get_name, NULL);
-	if (!names.size && !always)
+	if (!hashmap_get_size(&names) && !always)
 		die(_("No names found, cannot describe anything."));
 
 	if (argc == 0) {
diff --git a/hashmap.c b/hashmap.c
index 9b6a128..054f334 100644
--- a/hashmap.c
+++ b/hashmap.c
@@ -116,9 +116,6 @@ static void rehash(struct hashmap *map, unsigned int newsize)
 	unsigned int i, oldsize = map->tablesize;
 	struct hashmap_entry **oldtable = map->table;
 
-	if (map->disallow_rehash)
-		return;
-
 	alloc_table(map, newsize);
 	for (i = 0; i < oldsize; i++) {
 		struct hashmap_entry *e = oldtable[i];
@@ -166,6 +163,17 @@ void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,
 	while (initial_size > size)
 		size <<= HASHMAP_RESIZE_BITS;
 	alloc_table(map, size);
+
+	/*
+	 * By default, we want to:
+	 * [] keep track of the number of items in the map and
+	 * [] allow the map to automatically grow as necessary.
+	 *
+	 * We probably only need to disable these if we are being
+	 * used by a threaded caller.
+	 */
+	map->do_count_items = 1;
+	map->do_auto_rehash = 1;
 }
 
 void hashmap_free(struct hashmap *map, int free_entries)
@@ -206,9 +214,11 @@ void hashmap_add(struct hashmap *map, void *entry)
 	map->table[b] = entry;
 
 	/* fix size and rehash if appropriate */
-	map->size++;
-	if (map->size > map->grow_at)
-		rehash(map, map->tablesize << HASHMAP_RESIZE_BITS);
+	if (map->do_count_items) {
+		map->private_size++;
+		if (map->do_auto_rehash && map->private_size > map->grow_at)
+			rehash(map, map->tablesize << HASHMAP_RESIZE_BITS);
+	}
 }
 
 void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)
@@ -224,9 +234,12 @@ void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)
 	old->next = NULL;
 
 	/* fix size and rehash if appropriate */
-	map->size--;
-	if (map->size < map->shrink_at)
-		rehash(map, map->tablesize >> HASHMAP_RESIZE_BITS);
+	if (map->do_count_items) {
+		map->private_size--;
+		if (map->do_auto_rehash && map->private_size < map->shrink_at)
+			rehash(map, map->tablesize >> HASHMAP_RESIZE_BITS);
+	}
+
 	return old;
 }
 
diff --git a/hashmap.h b/hashmap.h
index 7a8fa7f..7b8e6f4 100644
--- a/hashmap.h
+++ b/hashmap.h
@@ -183,7 +183,7 @@ struct hashmap {
 	const void *cmpfn_data;
 
 	/* total number of entries (0 means the hashmap is empty) */
-	unsigned int size;
+	unsigned int private_size; /* use hashmap_get_size() */
 
 	/*
 	 * tablesize is the allocated size of the hash table. A non-0 value
@@ -196,8 +196,8 @@ struct hashmap {
 	unsigned int grow_at;
 	unsigned int shrink_at;
 
-	/* See `hashmap_disallow_rehash`. */
-	unsigned disallow_rehash : 1;
+	unsigned int do_count_items : 1;
+	unsigned int do_auto_rehash : 1;
 };
 
 /* hashmap functions */
@@ -253,6 +253,19 @@ static inline void hashmap_entry_init(void *entry, unsigned int hash)
 }
 
 /*
+ * Return the number of items in the map.
+ */
+inline unsigned int hashmap_get_size(struct hashmap *map)
+{
+	if (map->do_count_items)
+		return map->private_size;
+
+	/* TODO Consider counting them and returning that. */
+	die("hashmap_get_size: size not set");
+	return 0;
+}
+
+/*
  * Returns the hashmap entry for the specified key, or NULL if not found.
  *
  * `map` is the hashmap structure.
@@ -345,24 +358,6 @@ extern void *hashmap_remove(struct hashmap *map, const void *key,
 int hashmap_bucket(const struct hashmap *map, unsigned int hash);
 
 /*
- * Disallow/allow rehashing of the hashmap.
- * This is useful if the caller knows that the hashmap needs multi-threaded
- * access.  The caller is still required to guard/lock searches and inserts
- * in a manner appropriate to their usage.  This simply prevents the table
- * from being unexpectedly re-mapped.
- *
- * It is up to the caller to ensure that the hashmap is initialized to a
- * reasonable size to prevent poor performance.
- *
- * A call to allow rehashing does not force a rehash; that might happen
- * with the next insert or delete.
- */
-static inline void hashmap_disallow_rehash(struct hashmap *map, unsigned value)
-{
-	map->disallow_rehash = value;
-}
-
-/*
  * Used to iterate over all entries of a hashmap. Note that it is
  * not safe to add or remove entries to the hashmap while
  * iterating.
@@ -387,6 +382,67 @@ static inline void *hashmap_iter_first(struct hashmap *map,
 	return hashmap_iter_next(iter);
 }
 
+/*
+ * Disable item counting when adding/removing items.
+ *
+ * Normally, the hashmap keeps track of the number of items in the map
+ * and uses it to dynamically resize it.  This (both the counting and
+ * the resizing) can cause problems when the map is being used by
+ * threaded callers (because the hashmap code does not know about the
+ * locking strategy used by the threaded callers and therefore, does
+ * not know how to protect the "private_size" counter).
+ *
+ * (This will implicitly disable auto resizing.)
+ */
+static inline void hashmap_disable_item_counting(struct hashmap *map)
+{
+	map->do_count_items = 0;
+}
+
+/*
+ * Re-enable item couting when adding/removing items.
+ * If counting is currently disabled, it will force count them.
+ *
+ * This might be used after leaving a threaded section.
+ */
+static inline void hashmap_enable_item_counting(struct hashmap *map)
+{
+	void *item;
+	unsigned int n = 0;
+	struct hashmap_iter iter;
+
+	hashmap_iter_init(map, &iter);
+	while ((item = hashmap_iter_next(&iter)))
+		n++;
+
+	map->do_count_items = 1;
+	map->private_size = n;
+}
+
+/*
+ * Disable automatic resizing when adding/removing items.
+ *
+ * This prevents the hashmap from resizing the table size and
+ * redistributing the items into new bucket chains.  This causes
+ * problems when the map is being used by threaded callers (because
+ * the hashmap code does not know about the locking strategy used by
+ * the threaded callers and therefore, does not know how to safely
+ * build new chains while other threads may be walking them).
+ */
+static inline void hashmap_disable_auto_rehash(struct hashmap *map)
+{
+	map->do_auto_rehash = 0;
+}
+
+/*
+ * Re-enable automatic resizing when adding/removing items.
+ * This DOES NOT force an immediate rehash.
+ */
+static inline void hashmap_enable_auto_rehash(struct hashmap *map)
+{
+	map->do_auto_rehash = 1;
+}
+
 /* String interning */
 
 /*
diff --git a/name-hash.c b/name-hash.c
index 0e10f3e..829ff59 100644
--- a/name-hash.c
+++ b/name-hash.c
@@ -580,9 +580,11 @@ static void lazy_init_name_hash(struct index_state *istate)
 			NULL, istate->cache_nr);
 
 	if (lookup_lazy_params(istate)) {
-		hashmap_disallow_rehash(&istate->dir_hash, 1);
+		hashmap_disable_item_counting(&istate->dir_hash);
+		hashmap_disable_auto_rehash(&istate->dir_hash);
 		threaded_lazy_init_name_hash(istate);
-		hashmap_disallow_rehash(&istate->dir_hash, 0);
+		hashmap_enable_auto_rehash(&istate->dir_hash);
+		hashmap_enable_item_counting(&istate->dir_hash);
 	} else {
 		int nr;
 		for (nr = 0; nr < istate->cache_nr; nr++)
diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c
index 095d739..84c57b9 100644
--- a/t/helper/test-hashmap.c
+++ b/t/helper/test-hashmap.c
@@ -237,7 +237,7 @@ int cmd_main(int argc, const char **argv)
 		} else if (!strcmp("size", cmd)) {
 
 			/* print table sizes */
-			printf("%u %u\n", map.tablesize, map.size);
+			printf("%u %u\n", map.tablesize, hashmap_get_size(&map));
 
 		} else if (!strcmp("intern", cmd) && l1) {
 
-- 
2.9.3

Re: [PATCH] hashmap: add API to disable item counting when threaded

[Johannes Schindelin]

Hi Jeff,

On Wed, 30 Aug 2017, Jeff Hostetler wrote:

> From: Jeff Hostetler <jeffhost@microsoft.com>
> 
> This is to address concerns raised by ThreadSanitizer on the mailing
> list about threaded unprotected R/W access to map.size with my previous
> "disallow rehash" change (0607e10009ee4e37cb49b4cec8d28a9dda1656a4).
> See:
> https://public-inbox.org/git/adb37b70139fd1e2bac18bfd22c8b96683ae18eb.1502780344.git.martin.agren@gmail.com/
> 
> Add API to hashmap to disable item counting and to disable automatic
> rehashing.  Also include APIs to re-enable item counting and automatica
> rehashing.
> 
> When item counting is disabled, the map.size field is invalid.  So to
> prevent accidents, the field has been renamed and an accessor function
> hashmap_get_size() has been added.  All direct references to this field
> have been been updated.  And the name of the field changed to
> map.private_size to communicate thie.
> 
> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
> ---

The Git contribution process forces me to point out lines longer than 80
columns. I wish there was already an automated tool to fix that, but we
(as in "the core Git developers") have not yet managed to agree on one. So
I'll have to ask you to identify and fix them manually.

> @@ -253,6 +253,19 @@ static inline void hashmap_entry_init(void *entry, unsigned int hash)
>  }
>  
>  /*
> + * Return the number of items in the map.
> + */
> +inline unsigned int hashmap_get_size(struct hashmap *map)
> +{
> +	if (map->do_count_items)
> +		return map->private_size;
> +
> +	/* TODO Consider counting them and returning that. */

I'd rather not. If counting is disabled, it is disabled.

> +	die("hashmap_get_size: size not set");

Before anybody can ask for this message to be wrapped in _(...) to be
translateable, let me suggest instead to add the prefix "BUG: ".

> +static inline void hashmap_enable_item_counting(struct hashmap *map)
> +{
> +	void *item;
> +	unsigned int n = 0;
> +	struct hashmap_iter iter;
> +
> +	hashmap_iter_init(map, &iter);
> +	while ((item = hashmap_iter_next(&iter)))
> +		n++;
> +
> +	map->do_count_items = 1;
> +	map->private_size = n;
> +}

BTW this made me think that we may have a problem in our code since
switching from my original hashmap implementation to the bucket one added
in 6a364ced497 (add a hashtable implementation that supports O(1) removal,
2013-11-14): while it is not expected that there are many collisions, the
"grow_at" logic still essentially assumes the number of buckets to be
equal to the number of hashmap entries.

Your code simply reiterates that assumption, so I do not blame you for
anything here, nor ask you to change your patch.

But it does look a bit weird to assume so much about the nature of our
data, without having any real-life numbers. I wish I had more time so that
I could afford to run a couple of tests on this hashmap, such as: what is
the typical difference between bucket count and entry count, or the median
of the bucket sizes when the map is 80% full (i.e. *just* below the grow
threshold).

> diff --git a/name-hash.c b/name-hash.c
> index 0e10f3e..829ff59 100644
> --- a/name-hash.c
> +++ b/name-hash.c
> @@ -580,9 +580,11 @@ static void lazy_init_name_hash(struct index_state *istate)
>  			NULL, istate->cache_nr);
>  
>  	if (lookup_lazy_params(istate)) {
> -		hashmap_disallow_rehash(&istate->dir_hash, 1);
> +		hashmap_disable_item_counting(&istate->dir_hash);
> +		hashmap_disable_auto_rehash(&istate->dir_hash);
>  		threaded_lazy_init_name_hash(istate);
> -		hashmap_disallow_rehash(&istate->dir_hash, 0);
> +		hashmap_enable_auto_rehash(&istate->dir_hash);
> +		hashmap_enable_item_counting(&istate->dir_hash);

By your rationale, it would be enough to simply disable and re-enable
counting...

The rest of the patch looks just dandy to me.

Thanks,
Dscho

Re: [PATCH] hashmap: add API to disable item counting when threaded

[Jonathan Nieder]

Hi,

Johannes Schindelin wrote:
> On Wed, 30 Aug 2017, Jeff Hostetler wrote:

>> This is to address concerns raised by ThreadSanitizer on the mailing
>> list about threaded unprotected R/W access to map.size with my previous
>> "disallow rehash" change (0607e10009ee4e37cb49b4cec8d28a9dda1656a4).

Nice!

What does the message from TSan look like?  (The full message doesn't
need to go in the commit message, but a snippet can help.)  How can I
reproduce it?


>> See:
>> https://public-inbox.org/git/adb37b70139fd1e2bac18bfd22c8b96683ae18eb.1502780344.git.martin.agren@gmail.com/
>>
>> Add API to hashmap to disable item counting and to disable automatic
>> rehashing.  Also include APIs to re-enable item counting and automatica
>> rehashing.
>>
>> When item counting is disabled, the map.size field is invalid.  So to
>> prevent accidents, the field has been renamed and an accessor function
>> hashmap_get_size() has been added.  All direct references to this field
>> have been been updated.  And the name of the field changed to
>> map.private_size to communicate thie.
>>
>> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
>> ---
>
> The Git contribution process forces me to point out lines longer than 80
> columns. I wish there was already an automated tool to fix that, but we
> (as in "the core Git developers") have not yet managed to agree on one. So
> I'll have to ask you to identify and fix them manually.

I *think* (but am not sure) that there is an implied bug report in this
comment, but I am not sure what that bug report is and how I can help
with it!  If you have a link to an issue tracker, thread, wiki page, or
other pointer where I can learn more, then that might help me.

Have you experimented with the patches in Junio's branch
bw/git-clang-format?

[...]
>> +	/* TODO Consider counting them and returning that. */
>
> I'd rather not. If counting is disabled, it is disabled.
>
>> +	die("hashmap_get_size: size not set");
>
> Before anybody can ask for this message to be wrapped in _(...) to be
> translateable, let me suggest instead to add the prefix "BUG: ".

Nowadays (since v2.13.2~26^2~3, 2017-05-12), there is a BUG() function
that you can use in place of die():

	BUG("hashmap_get_size: size not set");

Thanks and hope that helps,
Jonathan

Re: [PATCH] hashmap: add API to disable item counting when threaded

[Jeff Hostetler]

On 9/1/2017 7:50 PM, Jonathan Nieder wrote:
> Hi,
> 
> Johannes Schindelin wrote:
>> On Wed, 30 Aug 2017, Jeff Hostetler wrote:
> 
>>> This is to address concerns raised by ThreadSanitizer on the mailing
>>> list about threaded unprotected R/W access to map.size with my previous
>>> "disallow rehash" change (0607e10009ee4e37cb49b4cec8d28a9dda1656a4).
> 
> Nice!
> 
> What does the message from TSan look like?  (The full message doesn't
> need to go in the commit message, but a snippet can help.)  How can I
> reproduce it?

I'll let Martin common on how to run TSan; I'm just going on
what he reported in the "tsan: t3008..." message from the URL
I quoted.  I didn't think to copy that text into the commit
message because it is just stack traces and too long, but I
could include a snippet.

Thanks,
Jeff

Re: [PATCH] hashmap: add API to disable item counting when threaded

[Martin Ågren]

On 5 September 2017 at 18:39, Jeff Hostetler <git@jeffhostetler.com> wrote:
>
>
> On 9/1/2017 7:50 PM, Jonathan Nieder wrote:
>>
>> Hi,
>>
>> Johannes Schindelin wrote:
>>>
>>> On Wed, 30 Aug 2017, Jeff Hostetler wrote:
>>
>>
>>>> This is to address concerns raised by ThreadSanitizer on the mailing
>>>> list about threaded unprotected R/W access to map.size with my previous
>>>> "disallow rehash" change (0607e10009ee4e37cb49b4cec8d28a9dda1656a4).
>>
>>
>> Nice!
>>
>> What does the message from TSan look like?  (The full message doesn't
>> need to go in the commit message, but a snippet can help.)  How can I
>> reproduce it?
>
>
> I'll let Martin common on how to run TSan; I'm just going on
> what he reported in the "tsan: t3008..." message from the URL
> I quoted.  I didn't think to copy that text into the commit
> message because it is just stack traces and too long, but I
> could include a snippet.

I ran the test suite with ThreadSanitizer:

$ make SANITIZE=thread test

Any failures were then inspected:

$ cd t
$ ./t3008-ls-files-lazy-init-name-hash.sh --verbose

That can be done with or without ma/ts-cleanups. That series adds a file
.tsan-suppressions, which can be used by defining the environment
variable

TSAN_OPTIONS="suppressions=/some/absolute/path/.tsan-suppressions"

in order to suppress some findings which are indeed races, but which are
"not a problem in practice".

Martin

Re: [PATCH] hashmap: add API to disable item counting when threaded

[Jeff King]

On Sat, Sep 02, 2017 at 01:31:19AM +0200, Johannes Schindelin wrote:

> > https://public-inbox.org/git/adb37b70139fd1e2bac18bfd22c8b96683ae18eb.1502780344.git.martin.agren@gmail.com/
> [...]
> > Add API to hashmap to disable item counting and to disable automatic
> > rehashing.  Also include APIs to re-enable item counting and automatica
> > rehashing.
> [...]
> 
> The Git contribution process forces me to point out lines longer than 80
> columns. I wish there was already an automated tool to fix that, but we
> (as in "the core Git developers") have not yet managed to agree on one. So
> I'll have to ask you to identify and fix them manually.

Perhaps it would be helpful if you pointed out the lines that are too
long. Because I don't see any being added by the patch. There are two in
the commit message. One is a URL. For the other, which is 82 characters,
I'm not sure there is a better tool than "turn on text wrapping in your
editor".

> > +	/* TODO Consider counting them and returning that. */
> 
> I'd rather not. If counting is disabled, it is disabled.
> 
> > +	die("hashmap_get_size: size not set");
> 
> Before anybody can ask for this message to be wrapped in _(...) to be
> translateable, let me suggest instead to add the prefix "BUG: ".

Agreed on both (and Jonathan's suggestion to just use BUG()).

> > +static inline void hashmap_enable_item_counting(struct hashmap *map)
> > +{
> > +	void *item;
> > +	unsigned int n = 0;
> > +	struct hashmap_iter iter;
> > +
> > +	hashmap_iter_init(map, &iter);
> > +	while ((item = hashmap_iter_next(&iter)))
> > +		n++;
> > +
> > +	map->do_count_items = 1;
> > +	map->private_size = n;
> > +}
> 
> BTW this made me think that we may have a problem in our code since
> switching from my original hashmap implementation to the bucket one added
> in 6a364ced497 (add a hashtable implementation that supports O(1) removal,
> 2013-11-14): while it is not expected that there are many collisions, the
> "grow_at" logic still essentially assumes the number of buckets to be
> equal to the number of hashmap entries.

I'm confused about what the problem is. If I am reading the code
correctly, "size" is always the number of elements and "grow_at" is the
table size times a load factor. Those are the same numbers you'd use to
decide to grow in an open-address table.

It's true that this does not take into account the actual number of
collisions we see (or the average per bucket, or however you want to
count it). But generally nor do open-address schemes (and certainly our
other hash tables just use load factor to decide when to grow).

Am I missing something?

-Peff

Re: [PATCH] hashmap: add API to disable item counting when threaded

[Johannes Schindelin]

Hi Peff,

On Sat, 2 Sep 2017, Jeff King wrote:

> On Sat, Sep 02, 2017 at 01:31:19AM +0200, Johannes Schindelin wrote:
> 
> > > https://public-inbox.org/git/adb37b70139fd1e2bac18bfd22c8b96683ae18eb.1502780344.git.martin.agren@gmail.com/
> > [...]
> > > +static inline void hashmap_enable_item_counting(struct hashmap *map)
> > > +{
> > > +	void *item;
> > > +	unsigned int n = 0;
> > > +	struct hashmap_iter iter;
> > > +
> > > +	hashmap_iter_init(map, &iter);
> > > +	while ((item = hashmap_iter_next(&iter)))
> > > +		n++;
> > > +
> > > +	map->do_count_items = 1;
> > > +	map->private_size = n;
> > > +}
> > 
> > BTW this made me think that we may have a problem in our code since
> > switching from my original hashmap implementation to the bucket one
> > added in 6a364ced497 (add a hashtable implementation that supports
> > O(1) removal, 2013-11-14): while it is not expected that there are
> > many collisions, the "grow_at" logic still essentially assumes the
> > number of buckets to be equal to the number of hashmap entries.
> 
> I'm confused about what the problem is. If I am reading the code
> correctly, "size" is always the number of elements and "grow_at" is the
> table size times a load factor. Those are the same numbers you'd use to
> decide to grow in an open-address table.
> 
> It's true that this does not take into account the actual number of
> collisions we see (or the average per bucket, or however you want to
> count it). But generally nor do open-address schemes (and certainly our
> other hash tables just use load factor to decide when to grow).

In the worst case, there is only one bucket when the table is grown
already, is all I tried to point out.

Ciao,
Dscho

Re: [PATCH] hashmap: add API to disable item counting when threaded

[Jeff Hostetler]

On 9/2/2017 4:17 AM, Jeff King wrote:
> On Sat, Sep 02, 2017 at 01:31:19AM +0200, Johannes Schindelin wrote:
>> Before anybody can ask for this message to be wrapped in _(...) to be
>> translateable, let me suggest instead to add the prefix "BUG: ".
> 
> Agreed on both (and Jonathan's suggestion to just use BUG()).

will do.  thanks.

> 
>>> +static inline void hashmap_enable_item_counting(struct hashmap *map)
>>> +{
>>> +	void *item;
>>> +	unsigned int n = 0;
>>> +	struct hashmap_iter iter;
>>> +
>>> +	hashmap_iter_init(map, &iter);
>>> +	while ((item = hashmap_iter_next(&iter)))
>>> +		n++;
>>> +
>>> +	map->do_count_items = 1;
>>> +	map->private_size = n;
>>> +}
>>
>> BTW this made me think that we may have a problem in our code since
>> switching from my original hashmap implementation to the bucket one added
>> in 6a364ced497 (add a hashtable implementation that supports O(1) removal,
>> 2013-11-14): while it is not expected that there are many collisions, the
>> "grow_at" logic still essentially assumes the number of buckets to be
>> equal to the number of hashmap entries.
> 
> I'm confused about what the problem is. If I am reading the code
> correctly, "size" is always the number of elements and "grow_at" is the
> table size times a load factor. Those are the same numbers you'd use to
> decide to grow in an open-address table.
> 
> It's true that this does not take into account the actual number of
> collisions we see (or the average per bucket, or however you want to
> count it). But generally nor do open-address schemes (and certainly our
> other hash tables just use load factor to decide when to grow).
> 
> Am I missing something?
> 
> -Peff
> 

Hashmap is not thread-safe by itself.  There are several uses of
it in a threaded context and they all handle their own locking
before accessing the hashmap.  Those usually work by locking the
whole hashmap.

My changes in "lazy-init-name-hash" deviated from that pattern
by locking on individual hash chains.  That is, n locks each
controlling 1/nth of the chains.

https://public-inbox.org/git/1490202865-31325-1-git-send-email-git@jeffhostetler.com/

To do that I had to disable automatic rehashing for the duration
of my threaded computation.  The problem that TSan identified is
that "size" is always incremented during inserts and it doesn't
have any locks protecting it.  So even though auto-rehash was
disabled, we are still counting the number of items in the map.
Not a terrible problem, but still a race.

Jeff

Re: [PATCH] hashmap: add API to disable item counting when threaded

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Sat, Sep 02, 2017 at 01:31:19AM +0200, Johannes Schindelin wrote:
>
>> BTW this made me think that we may have a problem in our code since
>> switching from my original hashmap implementation to the bucket one added
>> in 6a364ced497 (add a hashtable implementation that supports O(1) removal,
>> 2013-11-14): while it is not expected that there are many collisions, the
>> "grow_at" logic still essentially assumes the number of buckets to be
>> equal to the number of hashmap entries.
>
> I'm confused about what the problem is. If I am reading the code
> correctly, "size" is always the number of elements and "grow_at" is the
> table size times a load factor. Those are the same numbers you'd use to
> decide to grow in an open-address table.
>
> It's true that this does not take into account the actual number of
> collisions we see (or the average per bucket, or however you want to
> count it). But generally nor do open-address schemes (and certainly our
> other hash tables just use load factor to decide when to grow).

Are we comparing the hashmap.[ch] with the hash.[ch] added in
9027f53c ("Do linear-time/space rename logic for exact renames",
2007-10-25)?  I am a bit confused because Johannes calls it "my"
original.

Unless the real person in this discussion thread sending the
messages under Johannes's name is Linus, that is ;-).  Or maybe the
"original" being compared is something other than the series with
6a364ced497 replaced with its hashmap.[ch]?

In any case, I do think your reading of the code is correct in that
the comparison between size and grow-at/shrink-at is done correctly
with the true load factor of the table, not how many buckets out of
the possible buckets are filled.  

Old one used to grow at 50% full and never shrunk it, but the
current one grows at 80% and shrinks at a bit below 40%; I agree
with Dscho's feeling (in part not quoted above) that 50% vs 80%
doesn't seem to have been backed by any numbers, but optimizing the
load factor is outside the scope of this series, I would think.

6a364ced ("add a hashtable implementation that supports O(1)
removal", 2013-11-14) credits less frequent resizing for gain of
insert performance, but my hunch is that the need for frequent
resizing in the version before it primarily comes from the fact that
the table started empty (as opposed to having an initial size of 64,
which is what the current implementation uses).

Re: [PATCH] hashmap: add API to disable item counting when threaded

[Jeff Hostetler]

On 9/1/2017 7:31 PM, Johannes Schindelin wrote:
> Hi Jeff,
> 
> On Wed, 30 Aug 2017, Jeff Hostetler wrote:
> 
>> From: Jeff Hostetler <jeffhost@microsoft.com>
>>
>> This is to address concerns raised by ThreadSanitizer on the mailing
>> list about threaded unprotected R/W access to map.size with my previous
>> "disallow rehash" change (0607e10009ee4e37cb49b4cec8d28a9dda1656a4).
>> See:
>> https://public-inbox.org/git/adb37b70139fd1e2bac18bfd22c8b96683ae18eb.1502780344.git.martin.agren@gmail.com/
>>
>> Add API to hashmap to disable item counting and to disable automatic
>> rehashing.  Also include APIs to re-enable item counting and automatica
>> rehashing.
>>
>> When item counting is disabled, the map.size field is invalid.  So to
>> prevent accidents, the field has been renamed and an accessor function
>> hashmap_get_size() has been added.  All direct references to this field
>> have been been updated.  And the name of the field changed to
>> map.private_size to communicate thie.
>>
>> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
>> ---
> 
> The Git contribution process forces me to point out lines longer than 80
> columns. I wish there was already an automated tool to fix that, but we
> (as in "the core Git developers") have not yet managed to agree on one. So
> I'll have to ask you to identify and fix them manually.

I'm not sure which lines you're talking about, but I'll
give it another scan and double check.

There's not much I can do about the public-inbox.org URL.

> 
>> @@ -253,6 +253,19 @@ static inline void hashmap_entry_init(void *entry, unsigned int hash)
>>   }
>>   
>>   /*
>> + * Return the number of items in the map.
>> + */
>> +inline unsigned int hashmap_get_size(struct hashmap *map)
>> +{
>> +	if (map->do_count_items)
>> +		return map->private_size;
>> +
>> +	/* TODO Consider counting them and returning that. */
> 
> I'd rather not. If counting is disabled, it is disabled.
> 
>> +	die("hashmap_get_size: size not set");
> 
> Before anybody can ask for this message to be wrapped in _(...) to be
> translateable, let me suggest instead to add the prefix "BUG: ".

Good point.  Thanks.

> 
>> +static inline void hashmap_enable_item_counting(struct hashmap *map)
>> +{
>> +	void *item;
>> +	unsigned int n = 0;
>> +	struct hashmap_iter iter;
>> +
>> +	hashmap_iter_init(map, &iter);
>> +	while ((item = hashmap_iter_next(&iter)))
>> +		n++;
>> +
>> +	map->do_count_items = 1;
>> +	map->private_size = n;
>> +}
> 
> BTW this made me think that we may have a problem in our code since
> switching from my original hashmap implementation to the bucket one added
> in 6a364ced497 (add a hashtable implementation that supports O(1) removal,
> 2013-11-14): while it is not expected that there are many collisions, the
> "grow_at" logic still essentially assumes the number of buckets to be
> equal to the number of hashmap entries.
> 
> Your code simply reiterates that assumption, so I do not blame you for
> anything here, nor ask you to change your patch.

I'm not sure what you're saying here.  The iterator iterates over
all entries (and handles walking collision chains), so my newly
computed count should be correct and all of this is independent of
the "grow-at" and table-size logic.

I'm not forcing a rehash when counting is enabled.  I'm just
reestablishing the expected state.  The next insert may cause
a rehash, but I'm not forcing it.

However, there is an assumption that the caller pre-allocated sufficient
table-size space to avoid poor performance for the duration of the
non-counting period.

> 
> But it does look a bit weird to assume so much about the nature of our
> data, without having any real-life numbers. I wish I had more time so that
> I could afford to run a couple of tests on this hashmap, such as: what is
> the typical difference between bucket count and entry count, or the median
> of the bucket sizes when the map is 80% full (i.e. *just* below the grow
> threshold).

Personally, I think the 80% threshold is too aggressive (and the
default size is too small), but that's a different question.

The hashmap in question contains directory pathnames, so the
distribution will be completely dependent on the shape of the
data.

FWIW, I created a tool to dump some of this data.  See:
     t/helper/test-lazy-init-name-hash.c

> 
>> diff --git a/name-hash.c b/name-hash.c
>> index 0e10f3e..829ff59 100644
>> --- a/name-hash.c
>> +++ b/name-hash.c
>> @@ -580,9 +580,11 @@ static void lazy_init_name_hash(struct index_state *istate)
>>   			NULL, istate->cache_nr);
>>   
>>   	if (lookup_lazy_params(istate)) {
>> -		hashmap_disallow_rehash(&istate->dir_hash, 1);
>> +		hashmap_disable_item_counting(&istate->dir_hash);
>> +		hashmap_disable_auto_rehash(&istate->dir_hash);
>>   		threaded_lazy_init_name_hash(istate);
>> -		hashmap_disallow_rehash(&istate->dir_hash, 0);
>> +		hashmap_enable_auto_rehash(&istate->dir_hash);
>> +		hashmap_enable_item_counting(&istate->dir_hash);
> 
> By your rationale, it would be enough to simply disable and re-enable
> counting...
> 
> The rest of the patch looks just dandy to me.
> 
> Thanks,
> Dscho
> 

thanks
Jeff

Re: [PATCH] hashmap: add API to disable item counting when threaded

[Jeff King]

On Wed, Aug 30, 2017 at 06:59:22PM +0000, Jeff Hostetler wrote:

> From: Jeff Hostetler <jeffhost@microsoft.com>
> 
> This is to address concerns raised by ThreadSanitizer on the
> mailing list about threaded unprotected R/W access to map.size with my previous
> "disallow rehash" change (0607e10009ee4e37cb49b4cec8d28a9dda1656a4).  See:
> https://public-inbox.org/git/adb37b70139fd1e2bac18bfd22c8b96683ae18eb.1502780344.git.martin.agren@gmail.com/
> 
> Add API to hashmap to disable item counting and to disable automatic rehashing.  
> Also include APIs to re-enable item counting and automatica rehashing.

It may be worth summarizing the discussion at that thread here.

At first glance, it looks like this is woefully inadequate for allowing
multi-threaded access. But after digging, the issue is that we're really
trying to accommodate one specific callers which is doing its own
per-bucket locking, and which needs the internals of the hashmap to be
truly read-only.

I suspect the code might be easier to follow if that pattern were pushed
into its own threaded_hashmap that disabled the size and handled the
mod-n locking, but I don't insist on that as a blocker to this fix.

-Peff

Re: [PATCH] hashmap: add API to disable item counting when threaded

[Jeff Hostetler]

On 9/2/2017 4:05 AM, Jeff King wrote:
> On Wed, Aug 30, 2017 at 06:59:22PM +0000, Jeff Hostetler wrote:
> 
>> From: Jeff Hostetler <jeffhost@microsoft.com>
>>
>> This is to address concerns raised by ThreadSanitizer on the
>> mailing list about threaded unprotected R/W access to map.size with my previous
>> "disallow rehash" change (0607e10009ee4e37cb49b4cec8d28a9dda1656a4).  See:
>> https://public-inbox.org/git/adb37b70139fd1e2bac18bfd22c8b96683ae18eb.1502780344.git.martin.agren@gmail.com/
>>
>> Add API to hashmap to disable item counting and to disable automatic rehashing.
>> Also include APIs to re-enable item counting and automatica rehashing.
> 
> It may be worth summarizing the discussion at that thread here.
> 
> At first glance, it looks like this is woefully inadequate for allowing
> multi-threaded access. But after digging, the issue is that we're really
> trying to accommodate one specific callers which is doing its own
> per-bucket locking, and which needs the internals of the hashmap to be
> truly read-only.
> 
> I suspect the code might be easier to follow if that pattern were pushed
> into its own threaded_hashmap that disabled the size and handled the
> mod-n locking, but I don't insist on that as a blocker to this fix.

Agreed.  It would be better and easier to understand to produce
a thread-safe version of the hashmap code -- there are other uses
of the code that are currently doing their own locking that might
benefit, but I'm not looking to gratuitously refactor things.

The other issue was that we are multi-threaded during the
lazy-init phase, but the main status-or-whatever code that then
uses the hashmap is not.  So we only pay for the locking during
the multi-threaded usage.

Thanks,
Jeff

Re: [PATCH] hashmap: add API to disable item counting when threaded

[Simon Ruderich]

On Wed, Aug 30, 2017 at 06:59:22PM +0000, Jeff Hostetler wrote:
> [snip]
> +/*
> + * Re-enable item couting when adding/removing items.
> + * If counting is currently disabled, it will force count them.

The code always recounts them. Either the comment or the
code should be adjusted.

> + * This might be used after leaving a threaded section.
> + */
> +static inline void hashmap_enable_item_counting(struct hashmap *map)
> +{
> +	void *item;
> +	unsigned int n = 0;
> +	struct hashmap_iter iter;
> +
> +	hashmap_iter_init(map, &iter);
> +	while ((item = hashmap_iter_next(&iter)))
> +		n++;
> +
> +	map->do_count_items = 1;
> +	map->private_size = n;
> +}

Regards
Simon
-- 
+ privacy is necessary
+ using gnupg http://gnupg.org
+ public key id: 0x92FEFDB7E44C32F9

Re: [PATCH] hashmap: add API to disable item counting when threaded

[Junio C Hamano]

Jeff Hostetler <git@jeffhostetler.com> writes:

> From: Jeff Hostetler <jeffhost@microsoft.com>
>
> This is to address concerns raised by ThreadSanitizer on the
> mailing list about threaded unprotected R/W access to map.size with my previous
> "disallow rehash" change (0607e10009ee4e37cb49b4cec8d28a9dda1656a4).  See:
> https://public-inbox.org/git/adb37b70139fd1e2bac18bfd22c8b96683ae18eb.1502780344.git.martin.agren@gmail.com/
>
> Add API to hashmap to disable item counting and to disable automatic rehashing.  
> Also include APIs to re-enable item counting and automatica rehashing.
>
> When item counting is disabled, the map.size field is invalid.  So to
> prevent accidents, the field has been renamed and an accessor function
> hashmap_get_size() has been added.  All direct references to this
> field have been been updated.  And the name of the field changed
> to map.private_size to communicate thie.
>
> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
> ---
>  attr.c                  | 14 ++++---
>  builtin/describe.c      |  2 +-
>  hashmap.c               | 31 +++++++++++-----
>  hashmap.h               | 98 ++++++++++++++++++++++++++++++++++++++-----------
>  name-hash.c             |  6 ++-
>  t/helper/test-hashmap.c |  2 +-
>  6 files changed, 113 insertions(+), 40 deletions(-)

I feel somewhat stupid to say this, especially after seeing many
people applaud this patch, but I do not seem to be able to even
build Git with this patch.  I am getting:

    common-main.o: In function `hashmap_get_size':
    /home/gitster/w/git.git/hashmap.h:260: multiple definition of `hashmap_get_size'
    fast-import.o:/home/gitster/w/git.git/hashmap.h:260: first defined here
    libgit.a(argv-array.o): In function `hashmap_get_size':
    /home/gitster/w/git.git/hashmap.h:260: multiple definition of `hashmap_get_size'
    fast-import.o:/home/gitster/w/git.git/hashmap.h:260: first defined here
    libgit.a(attr.o): In function `hashmap_get_size':
    ...

and wonder if others are building with different options or something..

> diff --git a/hashmap.h b/hashmap.h
> index 7a8fa7f..7b8e6f4 100644
> --- a/hashmap.h
> +++ b/hashmap.h
> @@ -253,6 +253,19 @@ static inline void hashmap_entry_init(void *entry, unsigned int hash)
>  }
>  
>  /*
> + * Return the number of items in the map.
> + */
> +inline unsigned int hashmap_get_size(struct hashmap *map)

I think this must become static inline like everybody else in this
file, at least.

I also wonder if this header is excessively inlining too many
functions without measuring first, but that is a different story.

Re: [PATCH] hashmap: add API to disable item counting when threaded

[Jeff Hostetler]

On 9/5/2017 9:24 PM, Junio C Hamano wrote:
> Jeff Hostetler <git@jeffhostetler.com> writes:
> 
>> From: Jeff Hostetler <jeffhost@microsoft.com>
>>
> 
> I feel somewhat stupid to say this, especially after seeing many
> people applaud this patch, but I do not seem to be able to even
> build Git with this patch.  I am getting:
> 
>      common-main.o: In function `hashmap_get_size':
>      /home/gitster/w/git.git/hashmap.h:260: multiple definition of `hashmap_get_size'
>      fast-import.o:/home/gitster/w/git.git/hashmap.h:260: first defined here
>      libgit.a(argv-array.o): In function `hashmap_get_size':
>      /home/gitster/w/git.git/hashmap.h:260: multiple definition of `hashmap_get_size'
>      fast-import.o:/home/gitster/w/git.git/hashmap.h:260: first defined here
>      libgit.a(attr.o): In function `hashmap_get_size':
>      ...
> 
> and wonder if others are building with different options or something..

That's odd. I'm not seeing that.  My Ubuntu VM is reporting:
     $ gcc --version
     gcc (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005

I'll change it to static in the next version.  Hopefully that will
take care of it.

Thanks,
Jeff

[PATCH v2] hashmap: address ThreadSanitizer concerns

[Jeff Hostetler]

From: Jeff Hostetler <jeffhost@microsoft.com>

Version 2 addresses the comments and suggestions on version 1.
It removes the explicit disable/enable rehash and just relies
on the state of hashmap counting.
It changes the declaration of the hashmap_get_size() to be
static to avoid issues seen on some compilers.
It uses BUG() rather than die() for an error condition.
It adds a comment describing why lazy-init needs to disable
couting.
It fixes line length problems.
It add details from TSan in the commit message.

Jeff Hostetler (1):
  hashmap: add API to disable item counting when threaded

 attr.c                  | 15 ++++++-----
 builtin/describe.c      |  2 +-
 hashmap.c               | 26 +++++++++++-------
 hashmap.h               | 72 ++++++++++++++++++++++++++++++++++---------------
 name-hash.c             | 10 +++++--
 t/helper/test-hashmap.c |  3 ++-
 6 files changed, 88 insertions(+), 40 deletions(-)

-- 
2.9.3

[PATCH v2] hashmap: add API to disable item counting when threaded

[Jeff Hostetler]

From: Jeff Hostetler <jeffhost@microsoft.com>

This is to address concerns raised by ThreadSanitizer on the mailing list
about threaded unprotected R/W access to map.size with my previous "disallow
rehash" change (0607e10009ee4e37cb49b4cec8d28a9dda1656a4).

See:
https://public-inbox.org/git/adb37b70139fd1e2bac18bfd22c8b96683ae18eb.1502780344.git.martin.agren@gmail.com/

Add API to hashmap to disable item counting and thus automatic rehashing.
Also include API to later re-enable them.

When item counting is disabled, the map.size field is invalid.  So to
prevent accidents, the field has been renamed and an accessor function
hashmap_get_size() has been added.  All direct references to this
field have been been updated.  And the name of the field changed
to map.private_size to communicate this.

Here is the relevant output from ThreadSanitizer showing the problem:

WARNING: ThreadSanitizer: data race (pid=10554)
  Read of size 4 at 0x00000082d488 by thread T2 (mutexes: write M16):
    #0 hashmap_add hashmap.c:209
    #1 hash_dir_entry_with_parent_and_prefix name-hash.c:302
    #2 handle_range_dir name-hash.c:347
    #3 handle_range_1 name-hash.c:415
    #4 lazy_dir_thread_proc name-hash.c:471
    #5 <null> <null>

  Previous write of size 4 at 0x00000082d488 by thread T1 (mutexes: write M31):
    #0 hashmap_add hashmap.c:209
    #1 hash_dir_entry_with_parent_and_prefix name-hash.c:302
    #2 handle_range_dir name-hash.c:347
    #3 handle_range_1 name-hash.c:415
    #4 handle_range_dir name-hash.c:380
    #5 handle_range_1 name-hash.c:415
    #6 lazy_dir_thread_proc name-hash.c:471
    #7 <null> <null>

Martin gives instructions for running TSan on test t3008 in this post:
https://public-inbox.org/git/CAN0heSoJDL9pWELD6ciLTmWf-a=oyxe4EXXOmCKvsG5MSuzxsA@mail.gmail.com/

Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
---
 attr.c                  | 15 ++++++-----
 builtin/describe.c      |  2 +-
 hashmap.c               | 26 +++++++++++-------
 hashmap.h               | 72 ++++++++++++++++++++++++++++++++++---------------
 name-hash.c             | 10 +++++--
 t/helper/test-hashmap.c |  3 ++-
 6 files changed, 88 insertions(+), 40 deletions(-)

diff --git a/attr.c b/attr.c
index 56961f0..195aa6d 100644
--- a/attr.c
+++ b/attr.c
@@ -149,10 +149,12 @@ struct all_attrs_item {
 static void all_attrs_init(struct attr_hashmap *map, struct attr_check *check)
 {
 	int i;
+	unsigned int size;
 
 	hashmap_lock(map);
 
-	if (map->map.size < check->all_attrs_nr)
+	size = hashmap_get_size(&map->map);
+	if (size < check->all_attrs_nr)
 		die("BUG: interned attributes shouldn't be deleted");
 
 	/*
@@ -161,13 +163,13 @@ static void all_attrs_init(struct attr_hashmap *map, struct attr_check *check)
 	 * field), reallocate the provided attr_check instance's all_attrs
 	 * field and fill each entry with its corresponding git_attr.
 	 */
-	if (map->map.size != check->all_attrs_nr) {
+	if (size != check->all_attrs_nr) {
 		struct attr_hash_entry *e;
 		struct hashmap_iter iter;
 		hashmap_iter_init(&map->map, &iter);
 
-		REALLOC_ARRAY(check->all_attrs, map->map.size);
-		check->all_attrs_nr = map->map.size;
+		REALLOC_ARRAY(check->all_attrs, size);
+		check->all_attrs_nr = size;
 
 		while ((e = hashmap_iter_next(&iter))) {
 			const struct git_attr *a = e->value;
@@ -235,10 +237,11 @@ static const struct git_attr *git_attr_internal(const char *name, int namelen)
 
 	if (!a) {
 		FLEX_ALLOC_MEM(a, name, name, namelen);
-		a->attr_nr = g_attr_hashmap.map.size;
+		a->attr_nr = hashmap_get_size(&g_attr_hashmap.map);
 
 		attr_hashmap_add(&g_attr_hashmap, a->name, namelen, a);
-		assert(a->attr_nr == (g_attr_hashmap.map.size - 1));
+		assert(a->attr_nr ==
+		       (hashmap_get_size(&g_attr_hashmap.map) - 1));
 	}
 
 	hashmap_unlock(&g_attr_hashmap);
diff --git a/builtin/describe.c b/builtin/describe.c
index 89ea1cd..1e3cbc7 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -505,7 +505,7 @@ int cmd_describe(int argc, const char **argv, const char *prefix)
 
 	hashmap_init(&names, (hashmap_cmp_fn) commit_name_cmp, NULL, 0);
 	for_each_rawref(get_name, NULL);
-	if (!names.size && !always)
+	if (!hashmap_get_size(&names) && !always)
 		die(_("No names found, cannot describe anything."));
 
 	if (argc == 0) {
diff --git a/hashmap.c b/hashmap.c
index 9b6a128..d42f01f 100644
--- a/hashmap.c
+++ b/hashmap.c
@@ -116,9 +116,6 @@ static void rehash(struct hashmap *map, unsigned int newsize)
 	unsigned int i, oldsize = map->tablesize;
 	struct hashmap_entry **oldtable = map->table;
 
-	if (map->disallow_rehash)
-		return;
-
 	alloc_table(map, newsize);
 	for (i = 0; i < oldsize; i++) {
 		struct hashmap_entry *e = oldtable[i];
@@ -166,6 +163,12 @@ void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,
 	while (initial_size > size)
 		size <<= HASHMAP_RESIZE_BITS;
 	alloc_table(map, size);
+
+	/*
+	 * Keep track of the number of items in the map and
+	 * allow the map to automatically grow as necessary.
+	 */
+	map->do_count_items = 1;
 }
 
 void hashmap_free(struct hashmap *map, int free_entries)
@@ -206,9 +209,11 @@ void hashmap_add(struct hashmap *map, void *entry)
 	map->table[b] = entry;
 
 	/* fix size and rehash if appropriate */
-	map->size++;
-	if (map->size > map->grow_at)
-		rehash(map, map->tablesize << HASHMAP_RESIZE_BITS);
+	if (map->do_count_items) {
+		map->private_size++;
+		if (map->private_size > map->grow_at)
+			rehash(map, map->tablesize << HASHMAP_RESIZE_BITS);
+	}
 }
 
 void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)
@@ -224,9 +229,12 @@ void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)
 	old->next = NULL;
 
 	/* fix size and rehash if appropriate */
-	map->size--;
-	if (map->size < map->shrink_at)
-		rehash(map, map->tablesize >> HASHMAP_RESIZE_BITS);
+	if (map->do_count_items) {
+		map->private_size--;
+		if (map->private_size < map->shrink_at)
+			rehash(map, map->tablesize >> HASHMAP_RESIZE_BITS);
+	}
+
 	return old;
 }
 
diff --git a/hashmap.h b/hashmap.h
index 7a8fa7f..7cb29a6 100644
--- a/hashmap.h
+++ b/hashmap.h
@@ -183,7 +183,7 @@ struct hashmap {
 	const void *cmpfn_data;
 
 	/* total number of entries (0 means the hashmap is empty) */
-	unsigned int size;
+	unsigned int private_size; /* use hashmap_get_size() */
 
 	/*
 	 * tablesize is the allocated size of the hash table. A non-0 value
@@ -196,8 +196,7 @@ struct hashmap {
 	unsigned int grow_at;
 	unsigned int shrink_at;
 
-	/* See `hashmap_disallow_rehash`. */
-	unsigned disallow_rehash : 1;
+	unsigned int do_count_items : 1;
 };
 
 /* hashmap functions */
@@ -253,6 +252,18 @@ static inline void hashmap_entry_init(void *entry, unsigned int hash)
 }
 
 /*
+ * Return the number of items in the map.
+ */
+static inline unsigned int hashmap_get_size(struct hashmap *map)
+{
+	if (map->do_count_items)
+		return map->private_size;
+
+	BUG("hashmap_get_size: size not set");
+	return 0;
+}
+
+/*
  * Returns the hashmap entry for the specified key, or NULL if not found.
  *
  * `map` is the hashmap structure.
@@ -345,24 +356,6 @@ extern void *hashmap_remove(struct hashmap *map, const void *key,
 int hashmap_bucket(const struct hashmap *map, unsigned int hash);
 
 /*
- * Disallow/allow rehashing of the hashmap.
- * This is useful if the caller knows that the hashmap needs multi-threaded
- * access.  The caller is still required to guard/lock searches and inserts
- * in a manner appropriate to their usage.  This simply prevents the table
- * from being unexpectedly re-mapped.
- *
- * It is up to the caller to ensure that the hashmap is initialized to a
- * reasonable size to prevent poor performance.
- *
- * A call to allow rehashing does not force a rehash; that might happen
- * with the next insert or delete.
- */
-static inline void hashmap_disallow_rehash(struct hashmap *map, unsigned value)
-{
-	map->disallow_rehash = value;
-}
-
-/*
  * Used to iterate over all entries of a hashmap. Note that it is
  * not safe to add or remove entries to the hashmap while
  * iterating.
@@ -387,6 +380,43 @@ static inline void *hashmap_iter_first(struct hashmap *map,
 	return hashmap_iter_next(iter);
 }
 
+/*
+ * Disable item counting and automatic rehashing when adding/removing items.
+ *
+ * Normally, the hashmap keeps track of the number of items in the map
+ * and uses it to dynamically resize it.  This (both the counting and
+ * the resizing) can cause problems when the map is being used by
+ * threaded callers (because the hashmap code does not know about the
+ * locking strategy used by the threaded callers and therefore, does
+ * not know how to protect the "private_size" counter).
+ */
+static inline void hashmap_disable_item_counting(struct hashmap *map)
+{
+	map->do_count_items = 0;
+}
+
+/*
+ * Re-enable item couting when adding/removing items.
+ * If counting is currently disabled, it will force count them.
+ * It WILL NOT automatically rehash them.
+ */
+static inline void hashmap_enable_item_counting(struct hashmap *map)
+{
+	void *item;
+	unsigned int n = 0;
+	struct hashmap_iter iter;
+
+	if (map->do_count_items)
+		return;
+
+	hashmap_iter_init(map, &iter);
+	while ((item = hashmap_iter_next(&iter)))
+		n++;
+
+	map->do_count_items = 1;
+	map->private_size = n;
+}
+
 /* String interning */
 
 /*
diff --git a/name-hash.c b/name-hash.c
index 0e10f3e..3ac2e57 100644
--- a/name-hash.c
+++ b/name-hash.c
@@ -580,9 +580,15 @@ static void lazy_init_name_hash(struct index_state *istate)
 			NULL, istate->cache_nr);
 
 	if (lookup_lazy_params(istate)) {
-		hashmap_disallow_rehash(&istate->dir_hash, 1);
+		/*
+		 * Disable item counting and automatic rehashing because
+		 * we do per-chain (mod n) locking rather than whole hashmap
+		 * locking and we need to prevent the table-size from changing
+		 * and bucket items from being redistributed.
+		 */
+		hashmap_disable_item_counting(&istate->dir_hash);
 		threaded_lazy_init_name_hash(istate);
-		hashmap_disallow_rehash(&istate->dir_hash, 0);
+		hashmap_enable_item_counting(&istate->dir_hash);
 	} else {
 		int nr;
 		for (nr = 0; nr < istate->cache_nr; nr++)
diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c
index 095d739..4956d1d 100644
--- a/t/helper/test-hashmap.c
+++ b/t/helper/test-hashmap.c
@@ -237,7 +237,8 @@ int cmd_main(int argc, const char **argv)
 		} else if (!strcmp("size", cmd)) {
 
 			/* print table sizes */
-			printf("%u %u\n", map.tablesize, map.size);
+			printf("%u %u\n", map.tablesize,
+			       hashmap_get_size(&map));
 
 		} else if (!strcmp("intern", cmd) && l1) {
 
-- 
2.9.3

tsan: t5400: set_try_to_free_routine

[Martin Ågren]

Using SANITIZE=thread made t5400-send-pack.sh hit the potential race
below.

This is set_try_to_free_routine in wrapper.c. The race relates to the
reading of the "old" value. The caller doesn't care about the "old"
value, so this should be harmless right now. But it seems that using
this mechanism from multiple threads and restoring the earlier value
will probably not work out every time. (Not necessarily because of the
race in set_try_to_free_routine, but, e.g., because callers might not
restore the function pointer in the reverse order of how they
originally set it.)

Properly "fixing" this for thread-safety would probably require some
redesigning, which at the time might not be warranted. I'm just posting
this for completeness.

Martin

WARNING: ThreadSanitizer: data race (pid=21382)
  Read of size 8 at 0x000000979970 by thread T1:
    #0 set_try_to_free_routine wrapper.c:35 (git+0x0000006cde1c)
    #1 prepare_trace_line trace.c:105 (git+0x0000006a3bf0)
    #2 trace_strbuf_fl trace.c:185 (git+0x0000006a3bf0)
    #3 packet_trace pkt-line.c:80 (git+0x0000005f9f43)
    #4 packet_read pkt-line.c:309 (git+0x0000005fbe10)
    #5 recv_sideband sideband.c:37 (git+0x000000684c5e)
    #6 sideband_demux send-pack.c:216 (git+0x00000065a38c)
    #7 run_thread run-command.c:933 (git+0x000000655a93)
    #8 <null> <null> (libtsan.so.0+0x0000000230d9)

  Previous write of size 8 at 0x000000979970 by main thread:
    #0 set_try_to_free_routine wrapper.c:38 (git+0x0000006cde39)
    #1 prepare_trace_line trace.c:105 (git+0x0000006a3bf0)
    #2 trace_strbuf_fl trace.c:185 (git+0x0000006a3bf0)
    #3 packet_trace pkt-line.c:80 (git+0x0000005f9f43)
    #4 packet_read pkt-line.c:324 (git+0x0000005fc0bb)
    #5 packet_read_line_generic pkt-line.c:332 (git+0x0000005fc0bb)
    #6 packet_read_line pkt-line.c:342 (git+0x0000005fc0bb)
    #7 receive_unpack_status send-pack.c:149 (git+0x00000065c1e4)
    #8 send_pack send-pack.c:581 (git+0x00000065c1e4)
    #9 git_transport_push transport.c:574 (git+0x0000006ab2c1)
    #10 transport_push transport.c:1068 (git+0x0000006ae5d5)
    #11 push_with_options builtin/push.c:336 (git+0x00000049d580)
    #12 do_push builtin/push.c:419 (git+0x00000049f57d)
    #13 cmd_push builtin/push.c:591 (git+0x00000049f57d)
    #14 run_builtin git.c:330 (git+0x00000040949e)
    #15 handle_builtin git.c:538 (git+0x00000040949e)
    #16 run_argv git.c:590 (git+0x000000409a0e)
    #17 cmd_main git.c:667 (git+0x000000409a0e)
    #18 main common-main.c:43 (git+0x0000004079d1)

  Location is global 'try_to_free_routine' of size 8 at 0x000000979970 (git+0x000000979970)

  Thread T1 (tid=21405, running) created by main thread at:
    #0 pthread_create <null> (libtsan.so.0+0x000000027577)
    #1 start_async run-command.c:1130 (git+0x0000006582e7)
    #2 send_pack send-pack.c:562 (git+0x00000065b7c8)
    #3 git_transport_push transport.c:574 (git+0x0000006ab2c1)
    #4 transport_push transport.c:1068 (git+0x0000006ae5d5)
    #5 push_with_options builtin/push.c:336 (git+0x00000049d580)
    #6 do_push builtin/push.c:419 (git+0x00000049f57d)
    #7 cmd_push builtin/push.c:591 (git+0x00000049f57d)
    #8 run_builtin git.c:330 (git+0x00000040949e)
    #9 handle_builtin git.c:538 (git+0x00000040949e)
    #10 run_argv git.c:590 (git+0x000000409a0e)
    #11 cmd_main git.c:667 (git+0x000000409a0e)
    #12 main common-main.c:43 (git+0x0000004079d1)

SUMMARY: ThreadSanitizer: data race wrapper.c:35 set_try_to_free_routine

Re: tsan: t5400: set_try_to_free_routine

[Stefan Beller]

On Tue, Aug 15, 2017 at 5:53 AM, Martin Ågren <martin.agren@gmail.com> wrote:
> Using SANITIZE=thread made t5400-send-pack.sh hit the potential race
> below.
>
> This is set_try_to_free_routine in wrapper.c. The race relates to the
> reading of the "old" value. The caller doesn't care about the "old"
> value, so this should be harmless right now. But it seems that using
> this mechanism from multiple threads and restoring the earlier value
> will probably not work out every time. (Not necessarily because of the
> race in set_try_to_free_routine, but, e.g., because callers might not
> restore the function pointer in the reverse order of how they
> originally set it.)
>
> Properly "fixing" this for thread-safety would probably require some
> redesigning, which at the time might not be warranted. I'm just posting
> this for completeness.

Maybe related read (also error handling in threads):
https://public-inbox.org/git/20170619220036.22656-1-avarab@gmail.com/

>
> Martin
>
> WARNING: ThreadSanitizer: data race (pid=21382)
>   Read of size 8 at 0x000000979970 by thread T1:
>     #0 set_try_to_free_routine wrapper.c:35 (git+0x0000006cde1c)
>     #1 prepare_trace_line trace.c:105 (git+0x0000006a3bf0)
>     #2 trace_strbuf_fl trace.c:185 (git+0x0000006a3bf0)
>     #3 packet_trace pkt-line.c:80 (git+0x0000005f9f43)
>     #4 packet_read pkt-line.c:309 (git+0x0000005fbe10)
>     #5 recv_sideband sideband.c:37 (git+0x000000684c5e)
>     #6 sideband_demux send-pack.c:216 (git+0x00000065a38c)
>     #7 run_thread run-command.c:933 (git+0x000000655a93)
>     #8 <null> <null> (libtsan.so.0+0x0000000230d9)
>
>   Previous write of size 8 at 0x000000979970 by main thread:
>     #0 set_try_to_free_routine wrapper.c:38 (git+0x0000006cde39)
>     #1 prepare_trace_line trace.c:105 (git+0x0000006a3bf0)
>     #2 trace_strbuf_fl trace.c:185 (git+0x0000006a3bf0)
>     #3 packet_trace pkt-line.c:80 (git+0x0000005f9f43)
>     #4 packet_read pkt-line.c:324 (git+0x0000005fc0bb)
>     #5 packet_read_line_generic pkt-line.c:332 (git+0x0000005fc0bb)
>     #6 packet_read_line pkt-line.c:342 (git+0x0000005fc0bb)
>     #7 receive_unpack_status send-pack.c:149 (git+0x00000065c1e4)
>     #8 send_pack send-pack.c:581 (git+0x00000065c1e4)
>     #9 git_transport_push transport.c:574 (git+0x0000006ab2c1)
>     #10 transport_push transport.c:1068 (git+0x0000006ae5d5)
>     #11 push_with_options builtin/push.c:336 (git+0x00000049d580)
>     #12 do_push builtin/push.c:419 (git+0x00000049f57d)
>     #13 cmd_push builtin/push.c:591 (git+0x00000049f57d)
>     #14 run_builtin git.c:330 (git+0x00000040949e)
>     #15 handle_builtin git.c:538 (git+0x00000040949e)
>     #16 run_argv git.c:590 (git+0x000000409a0e)
>     #17 cmd_main git.c:667 (git+0x000000409a0e)
>     #18 main common-main.c:43 (git+0x0000004079d1)
>
>   Location is global 'try_to_free_routine' of size 8 at 0x000000979970 (git+0x000000979970)
>
>   Thread T1 (tid=21405, running) created by main thread at:
>     #0 pthread_create <null> (libtsan.so.0+0x000000027577)
>     #1 start_async run-command.c:1130 (git+0x0000006582e7)
>     #2 send_pack send-pack.c:562 (git+0x00000065b7c8)
>     #3 git_transport_push transport.c:574 (git+0x0000006ab2c1)
>     #4 transport_push transport.c:1068 (git+0x0000006ae5d5)
>     #5 push_with_options builtin/push.c:336 (git+0x00000049d580)
>     #6 do_push builtin/push.c:419 (git+0x00000049f57d)
>     #7 cmd_push builtin/push.c:591 (git+0x00000049f57d)
>     #8 run_builtin git.c:330 (git+0x00000040949e)
>     #9 handle_builtin git.c:538 (git+0x00000040949e)
>     #10 run_argv git.c:590 (git+0x000000409a0e)
>     #11 cmd_main git.c:667 (git+0x000000409a0e)
>     #12 main common-main.c:43 (git+0x0000004079d1)
>
> SUMMARY: ThreadSanitizer: data race wrapper.c:35 set_try_to_free_routine
>

Re: tsan: t5400: set_try_to_free_routine

[Martin Ågren]

On 15 August 2017 at 19:35, Stefan Beller <sbeller@google.com> wrote:
> On Tue, Aug 15, 2017 at 5:53 AM, Martin Ågren <martin.agren@gmail.com> wrote:
>> Using SANITIZE=thread made t5400-send-pack.sh hit the potential race
>> below.
>>
>> This is set_try_to_free_routine in wrapper.c. The race relates to the
>> reading of the "old" value. The caller doesn't care about the "old"
>> value, so this should be harmless right now. But it seems that using
>> this mechanism from multiple threads and restoring the earlier value
>> will probably not work out every time. (Not necessarily because of the
>> race in set_try_to_free_routine, but, e.g., because callers might not
>> restore the function pointer in the reverse order of how they
>> originally set it.)
>>
>> Properly "fixing" this for thread-safety would probably require some
>> redesigning, which at the time might not be warranted. I'm just posting
>> this for completeness.
>
> Maybe related read (also error handling in threads):
> https://public-inbox.org/git/20170619220036.22656-1-avarab@gmail.com/

Thanks for the pointer. Threading is tricky business, indeed. I still
haven't entirely groked all the users of set_try_to_free_routine, i.e.,
what they want to avoid and what they want to achieve. I'm just happy
that the only user which cares about the old value is not threaded, to
the best of my understanding.

Re: tsan: t5400: set_try_to_free_routine

[Jeff King]

On Tue, Aug 15, 2017 at 02:53:07PM +0200, Martin Ågren wrote:

> Using SANITIZE=thread made t5400-send-pack.sh hit the potential race
> below.
> 
> This is set_try_to_free_routine in wrapper.c. The race relates to the
> reading of the "old" value. The caller doesn't care about the "old"
> value, so this should be harmless right now. But it seems that using
> this mechanism from multiple threads and restoring the earlier value
> will probably not work out every time. (Not necessarily because of the
> race in set_try_to_free_routine, but, e.g., because callers might not
> restore the function pointer in the reverse order of how they
> originally set it.)
> 
> Properly "fixing" this for thread-safety would probably require some
> redesigning, which at the time might not be warranted. I'm just posting
> this for completeness.
> 
> Martin
> 
> WARNING: ThreadSanitizer: data race (pid=21382)
>   Read of size 8 at 0x000000979970 by thread T1:
>     #0 set_try_to_free_routine wrapper.c:35 (git+0x0000006cde1c)
>     #1 prepare_trace_line trace.c:105 (git+0x0000006a3bf0)
>     #2 trace_strbuf_fl trace.c:185 (git+0x0000006a3bf0)
>     #3 packet_trace pkt-line.c:80 (git+0x0000005f9f43)
>     #4 packet_read pkt-line.c:309 (git+0x0000005fbe10)
>     #5 recv_sideband sideband.c:37 (git+0x000000684c5e)
>     #6 sideband_demux send-pack.c:216 (git+0x00000065a38c)
>     #7 run_thread run-command.c:933 (git+0x000000655a93)
>     #8 <null> <null> (libtsan.so.0+0x0000000230d9)

I was curious why the trace code would care about the free routine in
the first place. Digging in the mailing list, I didn't find a lot of
discussion. But I think the problem is basically that the trace
infrastructure wants to be thread-safe, but the default free-pack-memory
callback isn't.

It's ironic that we fix the thread-unsafety of the free-pack-memory
function by using the also-thread-unsafe set_try_to_free_routine.

Further irony: the trace routines aren't thread-safe in the first place,
as they do lazy initialization of key->fd using an "initialized" field.
In practice it probably means double-writing key->fd and leaking a
descriptor (though there are no synchronizing operations there, so it's
entirely possible a compiler could reorder the assignments to key->fd
and key->initialized and a simultaneous reader could read a garbage
key->fd value).  We also call getenv(), which isn't thread-safe with
other calls to getenv() or setenv().

I can think of a few possible directions:

  1. Make set_try_to_free_routine() skip the write if it would be a
     noop. This is racy if threads are actually changing the value, but
     in practice they aren't (the first trace of any kind will set it to
     NULL, and it will remain there).

  2. Make the free-packed routine thread-safe by taking a lock. It
     should hardly ever be called, so performance wouldn't matter. The
     big question is: _which_ lock.  pack-objects, which uses threads
     already, has a version which does this. But it knows to take the
     big program-wide "I'm accessing unsafe parts of Git" lock that the
     rest of the program uses during its multi-threaded parts.
     There's no notion in the rest of Git for "now we're going into a
     multi-threaded part, so most calls will need to take a big global
     lock before doing anything interesting".

     For parts of Git that are explicitly multi-threaded (like the
     pack-objects delta search, or index-pack's delta resolution) that's
     not so bad. But the example above is just using a sideband demuxer.
     It would be unfortunate if the entire rest of send-pack had to
     start caring about taking that lock.

  3. Is the free-pack-memory thing actually accomplishing much these
     days? It comes from 97bfeb34df (Release pack windows before
     reporting out of memory., 2006-12-24), and the primary issue is not
     actual allocated memory, but mmap'd packs clogging up the address
     space so that malloc can't find a suitable block.

     On 64-bit systems this is likely doing nothing. We have tons of
     address space. But even on 32-bit systems, the default
     core.packedGitLimit is only 256MiB (which was set around the same
     time). You can certainly come up with a corner case where freeing
     up that address space could matter. But I'd be surprised if this
     has actually helped much in practice over the years. And if you
     have a repo which is running so close to the address space limits
     of your system, the right answer is probably: upgrade to a 64-bit
     system. Even if the try-to-free thing helped in one run, it's
     likely that similar runs are not going to be so lucky, and even
     with it you're going to see sporadic out-of-memory failures.

-Peff

Re: [PATCH/RFC 0/5] Some ThreadSanitizer-results

[Jeff King]

On Tue, Aug 15, 2017 at 02:53:00PM +0200, Martin Ågren wrote:

> I tried running the test suite on Git compiled with ThreadSanitizer
> (SANITIZE=thread). Maybe this series could be useful for someone else
> trying to do the same. I needed the first patch to avoid warnings when
> compiling, although it actually has nothing to do with threads.
> 
> The last four patches are about avoiding some issues where
> ThreadSanitizer complains for reasonable reasons, but which to the best
> of my understanding are not real problems. These patches could be useful
> to make "actual" problems stand out more. Of course, if no-one ever runs
> ThreadSanitizer, they are of little to no (or even negative) value...

I think it's a chicken-and-egg. I'd love to run the test suite with tsan
from time to time, but there's no point if it turns up a bunch of false
positives.

The general direction here looks good to me (and I agree with the
comments made so far, especially that we should stop writing to
strbuf_slopbuf entirely).

>   ThreadSanitizer: add suppressions

This one is the most interesting because it really is just papering over
the issues. I "solved" the transfer_debug one with actual code in:

  https://public-inbox.org/git/20170710133040.yom65mjol3nmf2it@sigill.intra.peff.net/

but it just feels really dirty. I'd be inclined to go with suppressions
for now until somebody can demonstrate or argue for an actual breakage
(just because it makes the tool more useful for finding _real_
problems).

-Peff

Re: [PATCH/RFC 0/5] Some ThreadSanitizer-results

[Martin Ågren]

On 20 August 2017 at 12:06, Jeff King <peff@peff.net> wrote:
> On Tue, Aug 15, 2017 at 02:53:00PM +0200, Martin Ågren wrote:
>
>> I tried running the test suite on Git compiled with ThreadSanitizer
>> (SANITIZE=thread). Maybe this series could be useful for someone else
>> trying to do the same. I needed the first patch to avoid warnings when
>> compiling, although it actually has nothing to do with threads.
>>
>> The last four patches are about avoiding some issues where
>> ThreadSanitizer complains for reasonable reasons, but which to the best
>> of my understanding are not real problems. These patches could be useful
>> to make "actual" problems stand out more. Of course, if no-one ever runs
>> ThreadSanitizer, they are of little to no (or even negative) value...
>
> I think it's a chicken-and-egg. I'd love to run the test suite with tsan
> from time to time, but there's no point if it turns up a bunch of false
> positives.
>
> The general direction here looks good to me (and I agree with the
> comments made so far, especially that we should stop writing to
> strbuf_slopbuf entirely).
>
>>   ThreadSanitizer: add suppressions
>
> This one is the most interesting because it really is just papering over
> the issues. I "solved" the transfer_debug one with actual code in:
>
>   https://public-inbox.org/git/20170710133040.yom65mjol3nmf2it@sigill.intra.peff.net/

Hmm, I did search for related posts, but obviously not good enough.
Sorry that I missed this.

> but it just feels really dirty. I'd be inclined to go with suppressions
> for now until somebody can demonstrate or argue for an actual breakage
> (just because it makes the tool more useful for finding _real_
> problems).

I actually had a more intrusive version of my patch, but which I didn't
send, where I extracted transport_debug_enabled() exactly like that,
except I did it in order to minimize the scope of the suppression. In
the end, I figured the scope was already small enough.

The obvious risk of introducing any kind of "temporary" suppression is
that it remains forever... :-) I think I'll add a couple of NEEDSWORK in
the code to make it a bit more likely that someone stumbles over the
problem and addresses it.

Thanks.

[PATCH v2 0/4] Some ThreadSanitizer-results

[Martin Ågren]

This is the second version of my series to try to address some issues
noted by ThreadSanitizer. Thanks to all who took the time to provide
input on the first version.

The largest change is in the third patch, which moves the "avoid writing
to slopbuf"-logic into strbuf_setlen, and compiles it unconditionally.
Patch 2 hasn't been changed. The others have seen some minor changes.
The patch introducing GIT_THREAD_SANITIZER is gone.

The end result as far as ThreadSanitizer is concerned is the same:

1) set_try_to_free_routine, where Peff outlined some possibilities, and
where I don't feel like I have any idea which of them is better.

2) hashmap_add, which I could try my hands on if Jeff doesn't beat me to
it -- his proposed change should fix it and I doubt I could come up with
anything "better", considering he knows the code.

Martin

Martin Ågren (4):
  convert: always initialize attr_action in convert_attrs
  pack-objects: take lock before accessing `remaining`
  strbuf_setlen: don't write to strbuf_slopbuf
  ThreadSanitizer: add suppressions

 strbuf.h               |  5 ++++-
 builtin/pack-objects.c |  6 ++++++
 color.c                |  7 +++++++
 convert.c              |  5 +++--
 transport-helper.c     |  7 +++++++
 .tsan-suppressions     | 10 ++++++++++
 6 files changed, 37 insertions(+), 3 deletions(-)
 create mode 100644 .tsan-suppressions

-- 
2.14.1.151.gdfeca7a7e

[PATCH v2 1/4] convert: always initialize attr_action in convert_attrs

[Martin Ågren]

convert_attrs contains an "if-else". In the "if", we set attr_action
twice, and the first assignment has no effect. In the "else", we do not
set it at all. Since git_check_attr always returns the same value, we'll
always end up in the "if", so there is no problem right now. But
convert_attrs is obviously trying not to rely on such an
implementation-detail of another component.

Make the initialization of attr_action after the if-else. Remove the
earlier assignments.

Suggested-by: Torsten Bögershausen <tboegi@web.de>
Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
v2: adapted per input from Torsten

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

diff --git a/convert.c b/convert.c
index 1012462e3..1f8116381 100644
--- a/convert.c
+++ b/convert.c
@@ -1040,7 +1040,6 @@ static void convert_attrs(struct conv_attrs *ca, const char *path)
 		ca->crlf_action = git_path_check_crlf(ccheck + 4);
 		if (ca->crlf_action == CRLF_UNDEFINED)
 			ca->crlf_action = git_path_check_crlf(ccheck + 0);
-		ca->attr_action = ca->crlf_action;
 		ca->ident = git_path_check_ident(ccheck + 1);
 		ca->drv = git_path_check_convert(ccheck + 2);
 		if (ca->crlf_action != CRLF_BINARY) {
@@ -1054,12 +1053,14 @@ static void convert_attrs(struct conv_attrs *ca, const char *path)
 			else if (eol_attr == EOL_CRLF)
 				ca->crlf_action = CRLF_TEXT_CRLF;
 		}
-		ca->attr_action = ca->crlf_action;
 	} else {
 		ca->drv = NULL;
 		ca->crlf_action = CRLF_UNDEFINED;
 		ca->ident = 0;
 	}
+
+	/* Save attr and make a decision for action */
+	ca->attr_action = ca->crlf_action;
 	if (ca->crlf_action == CRLF_TEXT)
 		ca->crlf_action = text_eol_is_crlf() ? CRLF_TEXT_CRLF : CRLF_TEXT_INPUT;
 	if (ca->crlf_action == CRLF_UNDEFINED && auto_crlf == AUTO_CRLF_FALSE)
-- 
2.14.1.151.gdfeca7a7e

[PATCH v2 2/4] pack-objects: take lock before accessing `remaining`

[Martin Ågren]

When checking the conditional of "while (me->remaining)", we did not
hold the lock. Calling find_deltas would still be safe, since it checks
"remaining" (after taking the lock) and is able to handle all values. In
fact, this could (currently) not trigger any bug: a bug could happen if
`remaining` transitioning from zero to non-zero races with the evaluation
of the while-condition, but these are always separated by the
data_ready-mechanism.

Make sure we have the lock when we read `remaining`. This does mean we
release it just so that find_deltas can take it immediately again. We
could tweak the contract so that the lock should be taken before calling
find_deltas, but let's defer that until someone can actually show that
"unlock+lock" has a measurable negative impact.

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
v2: unchanged from v1

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

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index c753e9237..bd391e97a 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -2170,7 +2170,10 @@ static void *threaded_find_deltas(void *arg)
 {
 	struct thread_params *me = arg;
 
+	progress_lock();
 	while (me->remaining) {
+		progress_unlock();
+
 		find_deltas(me->list, &me->remaining,
 			    me->window, me->depth, me->processed);
 
@@ -2192,7 +2195,10 @@ static void *threaded_find_deltas(void *arg)
 			pthread_cond_wait(&me->cond, &me->mutex);
 		me->data_ready = 0;
 		pthread_mutex_unlock(&me->mutex);
+
+		progress_lock();
 	}
+	progress_unlock();
 	/* leave ->working 1 so that this doesn't get more work assigned */
 	return NULL;
 }
-- 
2.14.1.151.gdfeca7a7e

[PATCH v2 3/4] strbuf_setlen: don't write to strbuf_slopbuf

[Martin Ågren]

strbuf_setlen(., 0) writes '\0' to sb.buf[0], where buf is either
allocated and unique to sb, or the global slopbuf. The slopbuf is meant
to provide a guarantee that buf is not NULL and that a freshly
initialized buffer contains the empty string, but it is not supposed to
be written to. That strbuf_setlen writes to slopbuf has at least two
implications:

First, it's wrong in principle. Second, it might be hiding misuses which
are just waiting to wreak havoc. Third, ThreadSanitizer detects a race
when multiple threads write to slopbuf at roughly the same time, thus
potentially making any more critical races harder to spot.

Avoid writing to strbuf_slopbuf in strbuf_setlen. Let's instead assert
on the first byte of slopbuf being '\0', since it helps ensure the
promised invariant of buf[len] == '\0'. (We know that "len" was already
0, or someone has messed with "alloc". If someone has fiddled with the
fields that much beyond the correct interface, they're on their own.)

This is a function which is used in many places, possibly also in hot
code paths. There are two branches in strbuf_setlen already, and we are
adding a third and possibly a fourth (in the assert). In hot code paths,
we hopefully reuse the buffer in order to avoid continous reallocations.
Thus, after a start-up phase, we should always take the same path,
which might help branch prediction, and we would never make the assert.
If a hot code path continuously reallocates, we probably have bigger
performance problems than this new safety-check.

Simple measurements do not contradict this reasoning. 100000000 times
resetting a buffer and adding the empty string takes 5.29/5.26 seconds
with/without this patch (best of three). Releasing at every iteration
yields 18.01/17.87. Adding a 30-character string instead of the empty
string yields 5.61/5.58 and 17.28/17.28(!).

This patch causes the git binary emitted by gcc 5.4.0 -O2 on my machine
to grow from 11389848 bytes to 11497184 bytes, an increase of 0.9%.

I also tried to piggy-back on the fact that we already check alloc,
which should already tell us whether we are using the slopbuf:

        if (sb->alloc) {
                if (len > sb->alloc - 1)
                        die("BUG: strbuf_setlen() beyond buffer");
                sb->buf[len] = '\0';
        } else {
                if (len)
                        die("BUG: strbuf_setlen() beyond buffer");
                assert(!strbuf_slopbuf[0]);
        }
        sb->len = len;

That didn't seem to be much slower (5.38, 18.02, 5.70, 17.32 seconds),
but it does introduce some minor code duplication. The resulting git
binary was 11510528 bytes large (another 0.1% increase).

Suggested-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
v2: no "ifdef TSAN"; moved check from strbuf_reset into strbuf_setlen

 strbuf.h | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/strbuf.h b/strbuf.h
index e705b94db..7496cb8ec 100644
--- a/strbuf.h
+++ b/strbuf.h
@@ -147,7 +147,10 @@ static inline void strbuf_setlen(struct strbuf *sb, size_t len)
 	if (len > (sb->alloc ? sb->alloc - 1 : 0))
 		die("BUG: strbuf_setlen() beyond buffer");
 	sb->len = len;
-	sb->buf[len] = '\0';
+	if (sb->buf != strbuf_slopbuf)
+		sb->buf[len] = '\0';
+	else
+		assert(!strbuf_slopbuf[0]);
 }
 
 /**
-- 
2.14.1.151.gdfeca7a7e

Re: [PATCH v2 3/4] strbuf_setlen: don't write to strbuf_slopbuf

[Junio C Hamano]

Martin Ågren <martin.agren@gmail.com> writes:

> strbuf_setlen(., 0) writes '\0' to sb.buf[0], where buf is either
> allocated and unique to sb, or the global slopbuf. The slopbuf is meant
> to provide a guarantee that buf is not NULL and that a freshly
> initialized buffer contains the empty string, but it is not supposed to
> be written to. That strbuf_setlen writes to slopbuf has at least two
> implications:
>
> First, it's wrong in principle. Second, it might be hiding misuses which
> are just waiting to wreak havoc. Third, ThreadSanitizer detects a race
> when multiple threads write to slopbuf at roughly the same time, thus
> potentially making any more critical races harder to spot.

There are two hard things in computer science ;-).

> Suggested-by: Junio C Hamano <gitster@pobox.com>
> Signed-off-by: Martin Ågren <martin.agren@gmail.com>
> ---
> v2: no "ifdef TSAN"; moved check from strbuf_reset into strbuf_setlen

Looks much better.  I have a mild objection to "suggested-by",
though.  It makes it sound as if this were my itch, but it is not.

All the credit for being motivate to fix the issue should go to you.
For what I did during the review of the previous one to lead to this
simpler version, if you want to document it, "helped-by" would be
more appropriate.

>  strbuf.h | 5 ++++-
>  1 file changed, 4 insertions(+), 1 deletion(-)
>
> diff --git a/strbuf.h b/strbuf.h
> index e705b94db..7496cb8ec 100644
> --- a/strbuf.h
> +++ b/strbuf.h
> @@ -147,7 +147,10 @@ static inline void strbuf_setlen(struct strbuf *sb, size_t len)
>  	if (len > (sb->alloc ? sb->alloc - 1 : 0))
>  		die("BUG: strbuf_setlen() beyond buffer");
>  	sb->len = len;
> -	sb->buf[len] = '\0';
> +	if (sb->buf != strbuf_slopbuf)
> +		sb->buf[len] = '\0';
> +	else
> +		assert(!strbuf_slopbuf[0]);
>  }
>  
>  /**

Re: [PATCH v2 3/4] strbuf_setlen: don't write to strbuf_slopbuf

[Martin Ågren]

On 23 August 2017 at 19:24, Junio C Hamano <gitster@pobox.com> wrote:
> Martin Ågren <martin.agren@gmail.com> writes:
>
>> strbuf_setlen(., 0) writes '\0' to sb.buf[0], where buf is either
>> allocated and unique to sb, or the global slopbuf. The slopbuf is meant
>> to provide a guarantee that buf is not NULL and that a freshly
>> initialized buffer contains the empty string, but it is not supposed to
>> be written to. That strbuf_setlen writes to slopbuf has at least two
>> implications:
>>
>> First, it's wrong in principle. Second, it might be hiding misuses which
>> are just waiting to wreak havoc. Third, ThreadSanitizer detects a race
>> when multiple threads write to slopbuf at roughly the same time, thus
>> potentially making any more critical races harder to spot.
>
> There are two hard things in computer science ;-).

Indeed. :-)

>> Suggested-by: Junio C Hamano <gitster@pobox.com>
>> Signed-off-by: Martin Ågren <martin.agren@gmail.com>
>> ---
>> v2: no "ifdef TSAN"; moved check from strbuf_reset into strbuf_setlen
>
> Looks much better.  I have a mild objection to "suggested-by",
> though.  It makes it sound as if this were my itch, but it is not.
>
> All the credit for being motivate to fix the issue should go to you.
> For what I did during the review of the previous one to lead to this
> simpler version, if you want to document it, "helped-by" would be
> more appropriate.

Ok, so that's two things to tweak in the commit message. I'll hold off
on v3 in case I get some more feedback the coming days. Thanks.

Martin

Re: [PATCH v2 3/4] strbuf_setlen: don't write to strbuf_slopbuf

[Junio C Hamano]

Martin Ågren <martin.agren@gmail.com> writes:

> On 23 August 2017 at 19:24, Junio C Hamano <gitster@pobox.com> wrote:
>> Martin Ågren <martin.agren@gmail.com> writes:
>>
>>> strbuf_setlen(., 0) writes '\0' to sb.buf[0], where buf is either
>>> allocated and unique to sb, or the global slopbuf. The slopbuf is meant
>>> to provide a guarantee that buf is not NULL and that a freshly
>>> initialized buffer contains the empty string, but it is not supposed to
>>> be written to. That strbuf_setlen writes to slopbuf has at least two
>>> implications:
>>>
>>> First, it's wrong in principle. Second, it might be hiding misuses which
>>> are just waiting to wreak havoc. Third, ThreadSanitizer detects a race
>>> when multiple threads write to slopbuf at roughly the same time, thus
>>> potentially making any more critical races harder to spot.
>>
>> There are two hard things in computer science ;-).
>
> Indeed. :-)
>
>>> Suggested-by: Junio C Hamano <gitster@pobox.com>
>>> Signed-off-by: Martin Ågren <martin.agren@gmail.com>
>>> ---
>>> v2: no "ifdef TSAN"; moved check from strbuf_reset into strbuf_setlen
>>
>> Looks much better.  I have a mild objection to "suggested-by",
>> though.  It makes it sound as if this were my itch, but it is not.
>>
>> All the credit for being motivate to fix the issue should go to you.
>> For what I did during the review of the previous one to lead to this
>> simpler version, if you want to document it, "helped-by" would be
>> more appropriate.
>
> Ok, so that's two things to tweak in the commit message. I'll hold off
> on v3 in case I get some more feedback the coming days. Thanks.

Well, this one is good enough and your "at least two" is technically
fine ;-)  Let's not reroll this any further.

Re: [PATCH v2 3/4] strbuf_setlen: don't write to strbuf_slopbuf

[Brandon Casey]

On Mon, Aug 21, 2017 at 10:43 AM, Martin Ågren <martin.agren@gmail.com> wrote:
> strbuf_setlen(., 0) writes '\0' to sb.buf[0], where buf is either
> allocated and unique to sb, or the global slopbuf. The slopbuf is meant
> to provide a guarantee that buf is not NULL and that a freshly
> initialized buffer contains the empty string, but it is not supposed to
> be written to. That strbuf_setlen writes to slopbuf has at least two
> implications:
<snip very well written commit message>

> diff --git a/strbuf.h b/strbuf.h
> index e705b94db..7496cb8ec 100644
> --- a/strbuf.h
> +++ b/strbuf.h
> @@ -147,7 +147,10 @@ static inline void strbuf_setlen(struct strbuf *sb, size_t len)
>         if (len > (sb->alloc ? sb->alloc - 1 : 0))
>                 die("BUG: strbuf_setlen() beyond buffer");
>         sb->len = len;
> -       sb->buf[len] = '\0';
> +       if (sb->buf != strbuf_slopbuf)
> +               sb->buf[len] = '\0';
> +       else
> +               assert(!strbuf_slopbuf[0]);
>  }
>
>  /**
> --
> 2.14.1.151.gdfeca7a7e
>

I know this must have been discussed before and/or I'm having a neuron
misfire, but is there any reason why we didn't just make slopbuf a
macro for ""?

i.e.

   #define strbuf_slopbuf ""

That way it should point to readonly memory and any attempt to assign
to it should produce a crash.

One benefit that I can think of for making strbuf_slopbuf be a real
variable is that we can then compare the pointer stored in the strbuf
to the strbuf_slopbuf address to detect whether the strbuf held the
slopbuf.  With the static string macro, each execution unit may get
it's own instance of the empty string.  But, before this patch, we
don't actually seem to be doing that anywhere and instead rely on the
value of alloc being accurate to determine whether the strbuf contains
the slopbuf or not.

So is there any reason why didn't do something like the following in
the first place?

diff --git a/strbuf.h b/strbuf.h
index e705b94..fcca618 100644
--- a/strbuf.h
+++ b/strbuf.h
@@ -67,7 +67,7 @@ struct strbuf {
        char *buf;
 };

-extern char strbuf_slopbuf[];
+#define strbuf_slopbuf ""
 #define STRBUF_INIT  { .alloc = 0, .len = 0, .buf = strbuf_slopbuf }

 /**
@@ -147,7 +147,9 @@ static inline void strbuf_setlen(struct strbuf
*sb, size_t len)
        if (len > (sb->alloc ? sb->alloc - 1 : 0))
                die("BUG: strbuf_setlen() beyond buffer");
        sb->len = len;
-       sb->buf[len] = '\0';
+       if (sb->alloc) {
+               sb->buf[len] = '\0';
+       }
 }

-Brandon

Re: [PATCH v2 3/4] strbuf_setlen: don't write to strbuf_slopbuf

[Junio C Hamano]

Brandon Casey <drafnel@gmail.com> writes:

> So is there any reason why didn't do something like the following in
> the first place?

My guess is that we didn't bother; if we cared, we would have used a
single instance of const char in a read-only segment, instead of
such a macro.

> diff --git a/strbuf.h b/strbuf.h
> index e705b94..fcca618 100644
> --- a/strbuf.h
> +++ b/strbuf.h
> @@ -67,7 +67,7 @@ struct strbuf {
>         char *buf;
>  };
>
> -extern char strbuf_slopbuf[];
> +#define strbuf_slopbuf ""
>  #define STRBUF_INIT  { .alloc = 0, .len = 0, .buf = strbuf_slopbuf }
>
>  /**
> @@ -147,7 +147,9 @@ static inline void strbuf_setlen(struct strbuf
> *sb, size_t len)
>         if (len > (sb->alloc ? sb->alloc - 1 : 0))
>                 die("BUG: strbuf_setlen() beyond buffer");
>         sb->len = len;
> -       sb->buf[len] = '\0';
> +       if (sb->alloc) {
> +               sb->buf[len] = '\0';
> +       }
>  }
>
> -Brandon

Re: [PATCH v2 3/4] strbuf_setlen: don't write to strbuf_slopbuf

[Brandon Casey]

On Wed, Aug 23, 2017 at 2:04 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Brandon Casey <drafnel@gmail.com> writes:
>
>> So is there any reason why didn't do something like the following in
>> the first place?
>
> My guess is that we didn't bother; if we cared, we would have used a
> single instance of const char in a read-only segment, instead of
> such a macro.

I think you mean something like this:

   const char * const strbuf_slopbuf = "";

..with or without "const" at the beginning.  We can't use an actual
variable like that since we also want to be able to do initialization
like:

   struct strbuf b = STRBUF_INIT;

i.e.

   struct strbuf b = { 0, 0, strbuf_slopbuf };

So the compiler needs to be able to determine that everything within
the curly braces is constant and apparently gcc cannot.


On a related note... I was just looking at object.c which also uses a
slopbuf.  We could similarly protect it from inadvertent modification
by doing something like this:

diff --git a/object.c b/object.c
index 321d7e9..4c7a041 100644
--- a/object.c
+++ b/object.c
@@ -303,7 +303,7 @@ int object_list_contains(struct object_list *list, struct ob
ject *obj)
  * A zero-length string to which object_array_entry::name can be
  * initialized without requiring a malloc/free.
  */
-static char object_array_slopbuf[1];
+static const char * const object_array_slopbuf = "";

 void add_object_array_with_path(struct object *obj, const char *name,
                                struct object_array *array,
@@ -326,7 +326,7 @@ void add_object_array_with_path(struct object
*obj, const char *name,
                entry->name = NULL;
        else if (!*name)
                /* Use our own empty string instead of allocating one: */
-               entry->name = object_array_slopbuf;
+               entry->name = (char*) object_array_slopbuf;
        else
                entry->name = xstrdup(name);
        entry->mode = mode;

Re: [PATCH v2 3/4] strbuf_setlen: don't write to strbuf_slopbuf

[Brandon Casey]

On Wed, Aug 23, 2017 at 2:20 PM, Brandon Casey <drafnel@gmail.com> wrote:
> On Wed, Aug 23, 2017 at 2:04 PM, Junio C Hamano <gitster@pobox.com> wrote:
>> Brandon Casey <drafnel@gmail.com> writes:
>>
>>> So is there any reason why didn't do something like the following in
>>> the first place?
>>
>> My guess is that we didn't bother; if we cared, we would have used a
>> single instance of const char in a read-only segment, instead of
>> such a macro.
>
> I think you mean something like this:
>
>    const char * const strbuf_slopbuf = "";

Ah, you probably meant something like this:

   const char strbuf_slopbuf = '\0';

which gcc will apparently place in the read-only segment.  I did not know that.

And assignment and initialization would look like:

   sb->buf = (char*) &strbuf_slopbuf;

and

   #define STRBUF_INIT  { .alloc = 0, .len = 0, .buf = (char*) &strbuf_slopbuf }

respectively.  Yeah, that's definitely preferable to a macro.
Something similar could be done in object.c.

-Brandon

Re: [PATCH v2 3/4] strbuf_setlen: don't write to strbuf_slopbuf

[Brandon Casey]

On Wed, Aug 23, 2017 at 2:54 PM, Brandon Casey <drafnel@gmail.com> wrote:
> On Wed, Aug 23, 2017 at 2:20 PM, Brandon Casey <drafnel@gmail.com> wrote:
>> On Wed, Aug 23, 2017 at 2:04 PM, Junio C Hamano <gitster@pobox.com> wrote:
>>> Brandon Casey <drafnel@gmail.com> writes:
>>>
>>>> So is there any reason why didn't do something like the following in
>>>> the first place?
>>>
>>> My guess is that we didn't bother; if we cared, we would have used a
>>> single instance of const char in a read-only segment, instead of
>>> such a macro.
>>
>> I think you mean something like this:
>>
>>    const char * const strbuf_slopbuf = "";

Hmm, apparently it is sufficient to mark our current strbuf_slopbuf
array as const and initialize it with a static string to trigger its
placement into the read-only section by gcc (and clang).

   const char strbuf_slopbuf[1] = "";

-Brandon

Re: [PATCH v2 3/4] strbuf_setlen: don't write to strbuf_slopbuf

[Junio C Hamano]

Brandon Casey <drafnel@gmail.com> writes:

> Ah, you probably meant something like this:
>
>    const char strbuf_slopbuf = '\0';
>
> which gcc will apparently place in the read-only segment.  I did not know that.

Yes but I highly suspect that it would be very compiler dependent
and not something the language lawyers would recommend us to rely
on.

My response was primarily to answer "why?" with "because we did not
bother".  The above is a mere tangent, i.e. "multiple copies of
empty strings is a horrible implementation (and there would be a way
to do it with a single instance)".

>    #define STRBUF_INIT  { .alloc = 0, .len = 0, .buf = (char*) &strbuf_slopbuf }
>
> respectively.  Yeah, that's definitely preferable to a macro.
> Something similar could be done in object.c.

What is the main objective for doing this change?  The "make sure we
do not write into that slopbuf" assert() bothers you and you want to
replace it with an address in the read-only segment?

Re: [PATCH v2 3/4] strbuf_setlen: don't write to strbuf_slopbuf

[Brandon Casey]

On Thu, Aug 24, 2017 at 9:52 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Brandon Casey <drafnel@gmail.com> writes:
>
>> Ah, you probably meant something like this:
>>
>>    const char strbuf_slopbuf = '\0';
>>
>> which gcc will apparently place in the read-only segment.  I did not know that.
>
> Yes but I highly suspect that it would be very compiler dependent
> and not something the language lawyers would recommend us to rely
> on.

I think compilers may have the option of placing variables that are
explicitly initialized to zero in the bss segment too, in addition to
those that are not explicitly initialized.  So I agree that no one
should write code that depends on their variables being placed in one
segment or the other, but I could see someone using this behavior as
an additional safety check; kind of a free assert, aside from the
additional space in the .rodata segment.

> My response was primarily to answer "why?" with "because we did not
> bother".  The above is a mere tangent, i.e. "multiple copies of
> empty strings is a horrible implementation (and there would be a way
> to do it with a single instance)".

Merely adding const to our current strbuf_slopbuf declaration does not
buy us anything since it will be allocated in r/w memory.  i.e. it
would still be possible to modify it via the buf member of strbuf.  So
you can't just do this:

   const char strbuf_slopbuf[1];

That's pretty much equivalent to what we currently have since it only
restricts modifying the contents of strbuf_slopbuf directly through
the strbuf_slopbuf variable, but it does not restrict modifying it
through a pointer to that object.

Until yesterday, I was under the impression that the only way to
access data in the rodata segment was through a constant literal.  So
my initial thought was that we could do something like:

   const char * const strbuf_slopbuf = "";

..but that variable cannot be used in a static assignment like:

   struct strbuf foo = {0, 0, (char*) strbuf_slopbuf};

So it seemed like our only option was to use a literal "" everywhere
instead of a slopbuf variable _if_ we wanted to have the guarantee
that our "slopbuf" could not be modified.

But what I learned yesterday, is that at least gcc/clang will place
the entire variable in the rodata segment if the variable is both
marked const _and_ initialized.

i.e. this will be allocated in the .rodata segment:

   const char strbuf_slopbuf[1] = "";

>>    #define STRBUF_INIT  { .alloc = 0, .len = 0, .buf = (char*) &strbuf_slopbuf }
>>
>> respectively.  Yeah, that's definitely preferable to a macro.
>> Something similar could be done in object.c.
>
> What is the main objective for doing this change?  The "make sure we
> do not write into that slopbuf" assert() bothers you and you want to
> replace it with an address in the read-only segment?

Actually nothing about the patch bothers me.  The point of that patch
is to make sure we don't accidentally modify the slopbuf.  I was just
looking for a way for the compiler to help out and wondering if there
was a reason we didn't attempt to do so in the first place.

I think the main takeaway here is that I learned something yesterday
:-)  I didn't actually intend to submit a patch for any of this, but
if anything useful came out of the discussion I thought Martin may
incorporate it into his patch if he wanted to.

-Brandon

Re: [PATCH v2 3/4] strbuf_setlen: don't write to strbuf_slopbuf

[Martin Ågren]

On 24 August 2017 at 20:29, Brandon Casey <drafnel@gmail.com> wrote:
> On Thu, Aug 24, 2017 at 9:52 AM, Junio C Hamano <gitster@pobox.com> wrote:
>> Brandon Casey <drafnel@gmail.com> writes:
>>
>>> Ah, you probably meant something like this:
>>>
>>>    const char strbuf_slopbuf = '\0';
>>>
>>> which gcc will apparently place in the read-only segment.  I did not know that.
>>
>> Yes but I highly suspect that it would be very compiler dependent
>> and not something the language lawyers would recommend us to rely
>> on.
>
> I think compilers may have the option of placing variables that are
> explicitly initialized to zero in the bss segment too, in addition to
> those that are not explicitly initialized.  So I agree that no one
> should write code that depends on their variables being placed in one
> segment or the other, but I could see someone using this behavior as
> an additional safety check; kind of a free assert, aside from the
> additional space in the .rodata segment.
>
>> My response was primarily to answer "why?" with "because we did not
>> bother".  The above is a mere tangent, i.e. "multiple copies of
>> empty strings is a horrible implementation (and there would be a way
>> to do it with a single instance)".
>
> Merely adding const to our current strbuf_slopbuf declaration does not
> buy us anything since it will be allocated in r/w memory.  i.e. it
> would still be possible to modify it via the buf member of strbuf.  So
> you can't just do this:
>
>    const char strbuf_slopbuf[1];
>
> That's pretty much equivalent to what we currently have since it only
> restricts modifying the contents of strbuf_slopbuf directly through
> the strbuf_slopbuf variable, but it does not restrict modifying it
> through a pointer to that object.
>
> Until yesterday, I was under the impression that the only way to
> access data in the rodata segment was through a constant literal.  So
> my initial thought was that we could do something like:
>
>    const char * const strbuf_slopbuf = "";
>
> ..but that variable cannot be used in a static assignment like:
>
>    struct strbuf foo = {0, 0, (char*) strbuf_slopbuf};
>
> So it seemed like our only option was to use a literal "" everywhere
> instead of a slopbuf variable _if_ we wanted to have the guarantee
> that our "slopbuf" could not be modified.
>
> But what I learned yesterday, is that at least gcc/clang will place
> the entire variable in the rodata segment if the variable is both
> marked const _and_ initialized.
>
> i.e. this will be allocated in the .rodata segment:
>
>    const char strbuf_slopbuf[1] = "";
>
>>>    #define STRBUF_INIT  { .alloc = 0, .len = 0, .buf = (char*) &strbuf_slopbuf }
>>>
>>> respectively.  Yeah, that's definitely preferable to a macro.
>>> Something similar could be done in object.c.
>>
>> What is the main objective for doing this change?  The "make sure we
>> do not write into that slopbuf" assert() bothers you and you want to
>> replace it with an address in the read-only segment?
>
> Actually nothing about the patch bothers me.  The point of that patch
> is to make sure we don't accidentally modify the slopbuf.  I was just
> looking for a way for the compiler to help out and wondering if there
> was a reason we didn't attempt to do so in the first place.
>
> I think the main takeaway here is that I learned something yesterday
> :-)  I didn't actually intend to submit a patch for any of this, but
> if anything useful came out of the discussion I thought Martin may
> incorporate it into his patch if he wanted to.

Thanks for interesting information. I also learned something new. :-)

My first thought was, well, maybe someone writes '\0' to sb.buf[len].
That should intuitively be a no-op and "ok", but the documentation
actually only says that it's safe to write to positions 0 .. len-1, so
sb.buf[len] is supposedly not safe (no-op or not). Maybe a degenerate
and rarely tested case of otherwise sane code could end up writing '\0'
to slopbuf[0]. (Arguably strbuf_setlen should have been used instead.)

I can see the value of placing the slopbuf in read-only memory, but I
think that would be a follow-up patch with its own pros and cons.

Martin

Re: [PATCH v2 3/4] strbuf_setlen: don't write to strbuf_slopbuf

[Junio C Hamano]

Brandon Casey <drafnel@gmail.com> writes:

> On Wed, Aug 23, 2017 at 2:04 PM, Junio C Hamano <gitster@pobox.com> wrote:
>> Brandon Casey <drafnel@gmail.com> writes:
>>
>>> So is there any reason why didn't do something like the following in
>>> the first place?
>>
>> My guess is that we didn't bother; if we cared, we would have used a
>> single instance of const char in a read-only segment, instead of
>> such a macro.
>
> I think you mean something like this:
>
>    const char * const strbuf_slopbuf = "";

Rather, more like "const char slopbuf[1];"

Re: [PATCH v2 3/4] strbuf_setlen: don't write to strbuf_slopbuf

[Brandon Casey]

On Wed, Aug 23, 2017 at 3:24 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Brandon Casey <drafnel@gmail.com> writes:
>
>> On Wed, Aug 23, 2017 at 2:04 PM, Junio C Hamano <gitster@pobox.com> wrote:
>>> Brandon Casey <drafnel@gmail.com> writes:
>>>
>>>> So is there any reason why didn't do something like the following in
>>>> the first place?
>>>
>>> My guess is that we didn't bother; if we cared, we would have used a
>>> single instance of const char in a read-only segment, instead of
>>> such a macro.
>>
>> I think you mean something like this:
>>
>>    const char * const strbuf_slopbuf = "";
>
> Rather, more like "const char slopbuf[1];"

You'd think that would be sufficient right?  Apparently gcc and clang
will only place a variable marked as const in the read-only section if
you initialize it with a constant too.  (gcc 4.9.2, clang 3.8.1 on
linux, clang 8.1.0 on osx)

I might have to adjust my stance on initializing global variables
moving forward :-)

-Brandon

[PATCH v2 4/4] ThreadSanitizer: add suppressions

[Martin Ågren]

Add a file .tsan-suppressions and list two functions in it: want_color()
and transfer_debug(). Both of these use the pattern

	static int foo = -1;
	if (foo < 0)
		foo = bar();

where bar always returns the same non-negative value. This can cause
ThreadSanitizer to diagnose a race when foo is written from two threads.
That is indeed a race, although it arguably doesn't matter in practice
since it's always the same value that is written.

Add NEEDSWORK-comments to the functions so that this problem is not
forever swept way under the carpet.

The suppressions-file is used by setting the environment variable
TSAN_OPTIONS to, e.g., "suppressions=$(pwd)/.tsan-suppressions". Observe
that relative paths such as ".tsan-suppressions" might not work.

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
v2: added NEEDSWORK; reworded the comments in the new file
 color.c            |  7 +++++++
 transport-helper.c |  7 +++++++
 .tsan-suppressions | 10 ++++++++++
 3 files changed, 24 insertions(+)
 create mode 100644 .tsan-suppressions

diff --git a/color.c b/color.c
index 7aa8b076f..9ccd954d6 100644
--- a/color.c
+++ b/color.c
@@ -338,6 +338,13 @@ static int check_auto_color(void)
 
 int want_color(int var)
 {
+	/*
+	 * NEEDSWORK: This function is sometimes used from multiple threads, and
+	 * we end up using want_auto racily. That "should not matter" since
+	 * we always write the same value, but it's still wrong. This function
+	 * is listed in .tsan-suppressions for the time being.
+	 */
+
 	static int want_auto = -1;
 
 	if (var < 0)
diff --git a/transport-helper.c b/transport-helper.c
index 8f68d69a8..f50b34df2 100644
--- a/transport-helper.c
+++ b/transport-helper.c
@@ -1117,6 +1117,13 @@ int transport_helper_init(struct transport *transport, const char *name)
 __attribute__((format (printf, 1, 2)))
 static void transfer_debug(const char *fmt, ...)
 {
+	/*
+	 * NEEDSWORK: This function is sometimes used from multiple threads, and
+	 * we end up using debug_enabled racily. That "should not matter" since
+	 * we always write the same value, but it's still wrong. This function
+	 * is listed in .tsan-suppressions for the time being.
+	 */
+
 	va_list args;
 	char msgbuf[PBUFFERSIZE];
 	static int debug_enabled = -1;
diff --git a/.tsan-suppressions b/.tsan-suppressions
new file mode 100644
index 000000000..8c85014a0
--- /dev/null
+++ b/.tsan-suppressions
@@ -0,0 +1,10 @@
+# Suppressions for ThreadSanitizer (tsan).
+#
+# This file is used by setting the environment variable TSAN_OPTIONS to, e.g.,
+# "suppressions=$(pwd)/.tsan-suppressions". Observe that relative paths such as
+# ".tsan-suppressions" might not work.
+
+# A static variable is written to racily, but we always write the same value, so
+# in practice it (hopefully!) doesn't matter.
+race:^want_color$
+race:^transfer_debug$
-- 
2.14.1.151.gdfeca7a7e

Re: [PATCH v2 4/4] ThreadSanitizer: add suppressions

[Jeff King]

On Mon, Aug 21, 2017 at 07:43:48PM +0200, Martin Ågren wrote:

> Add a file .tsan-suppressions and list two functions in it: want_color()
> and transfer_debug(). Both of these use the pattern
> 
> 	static int foo = -1;
> 	if (foo < 0)
> 		foo = bar();
> 
> where bar always returns the same non-negative value. This can cause
> ThreadSanitizer to diagnose a race when foo is written from two threads.
> That is indeed a race, although it arguably doesn't matter in practice
> since it's always the same value that is written.
> 
> Add NEEDSWORK-comments to the functions so that this problem is not
> forever swept way under the carpet.
> 
> The suppressions-file is used by setting the environment variable
> TSAN_OPTIONS to, e.g., "suppressions=$(pwd)/.tsan-suppressions". Observe
> that relative paths such as ".tsan-suppressions" might not work.

This looks good to me.

-Peff

Re: [PATCH v2 0/4] Some ThreadSanitizer-results

[Jeff Hostetler]

On 8/21/2017 1:43 PM, Martin Ågren wrote:
> This is the second version of my series to try to address some issues
> ... 
> 2) hashmap_add, which I could try my hands on if Jeff doesn't beat me to
> it -- his proposed change should fix it and I doubt I could come up with
> anything "better", considering he knows the code.

Now that I'm back from vacation, let me take another stab at this.

Jeff