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

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

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

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

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

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

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

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

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

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

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

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)

quoted

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.

On 15 August 2017 at 16:17, Torsten Bögershausen [off-list ref] wrote:

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

quoted

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

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.

On Tue, Aug 15, 2017 at 5:53 AM, Martin Ågren [off-list ref] 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

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

On Tue, Aug 15, 2017 at 10:59 AM, Jeff Hostetler [off-list ref] wrote:

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.

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.

On 15 August 2017 at 20:17, Stefan Beller [off-list ref] wrote:

On Tue, Aug 15, 2017 at 10:59 AM, Jeff Hostetler [off-list ref] wrote:

quoted

On 8/15/2017 8:53 AM, Martin Ågren wrote:

quoted

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.

quoted

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.

quoted

        /* 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..

quoted

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

On 15 August 2017 at 19:35, Stefan Beller [off-list ref] wrote:

On Tue, Aug 15, 2017 at 5:53 AM, Martin Ågren [off-list ref] wrote:

quoted

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.

quoted

quoted

        /* 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.

On 15 August 2017 at 20:48, Stefan Beller [off-list ref] wrote:

quoted

quoted

quoted

        /* 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.

quoted

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.

quoted

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.

quoted

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

Am 15.08.2017 um 14:53 schrieb Martin Ågren:

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

On 8/15/2017 3:21 PM, Martin Ågren wrote:

On 15 August 2017 at 20:48, Stefan Beller [off-list ref] wrote:

quoted

quoted

quoted

quoted

         /* 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.

quoted

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.

quoted

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.

quoted

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

quoted

quoted

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

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

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

On 20 August 2017 at 12:06, Jeff King [off-list ref] wrote:

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

quoted

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

quoted

  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.

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

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 <redacted>
Signed-off-by: Martin Ågren <redacted>
---
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

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

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 <redacted>
Signed-off-by: Martin Ågren <redacted>
---
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

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

On Mon, Aug 21, 2017 at 10:43 AM, Martin Ågren [off-list ref] 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>

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

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

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

From: Jeff Hostetler <redacted>

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

From: Jeff Hostetler <redacted>

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

Hi Jeff,

On Wed, 30 Aug 2017, Jeff Hostetler wrote:

From: Jeff Hostetler <redacted>

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

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

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

Hi,

Johannes Schindelin wrote:

On Wed, 30 Aug 2017, Jeff Hostetler wrote:

quoted

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?

quoted

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

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?

[...]

quoted

+	/* TODO Consider counting them and returning that. */

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

quoted

+	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

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

From: Jeff Hostetler <redacted>

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

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

quoted

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

[...]

quoted

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

quoted

+	/* TODO Consider counting them and returning that. */

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

quoted

+	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()).

quoted

+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

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

Hi Peff,

On Sat, 2 Sep 2017, Jeff King wrote:

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

quoted

quoted

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

[...]

quoted

+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

On 9/1/2017 7:31 PM, Johannes Schindelin wrote:

Hi Jeff,

On Wed, 30 Aug 2017, Jeff Hostetler wrote:

quoted

From: Jeff Hostetler <redacted>

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

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.

quoted

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

quoted

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

quoted

+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

quoted

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

On 9/1/2017 7:50 PM, Jonathan Nieder wrote:

Hi,

Johannes Schindelin wrote:

quoted

On Wed, 30 Aug 2017, Jeff Hostetler wrote:

quoted

quoted

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

On 9/2/2017 4:17 AM, Jeff King wrote:

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

quoted

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.

quoted

quoted

+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

On 9/2/2017 4:05 AM, Jeff King wrote:

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

quoted

From: Jeff Hostetler <redacted>

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

On 5 September 2017 at 18:39, Jeff Hostetler [off-list ref] wrote:

On 9/1/2017 7:50 PM, Jonathan Nieder wrote:

quoted

Hi,

Johannes Schindelin wrote:

quoted

On Wed, 30 Aug 2017, Jeff Hostetler wrote:

quoted

quoted

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

Jeff Hostetler [off-list ref] writes:

From: Jeff Hostetler <redacted>

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

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.

Jeff King [off-list ref] writes:

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

quoted

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

On 9/5/2017 9:24 PM, Junio C Hamano wrote:

Jeff Hostetler [off-list ref] writes:

quoted

From: Jeff Hostetler <redacted>

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

From: Jeff Hostetler <redacted>

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

From: Jeff Hostetler <redacted>

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 <redacted>
---
 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;
 }