Some ThreadSanitizer-results

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 <[email protected]>

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

convert.c +0 -0

index 1012462e3..943d957b4 100644

convert.c +0 -0

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

Signature · 1 line

2.14.1.151.gdfeca7a7e

convert.c static void convert_attrs(struct conv_attrs *ca, const char *path) · line 1043

Quoted 10 lines

convert.c +0 -1

index 1012462e3..943d957b4 100644
@@ -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.

Quoted 23 lines · Martin Ågren

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

Initialize attr_action to CRLF_UNDEFINED in the dead code path.

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

Signed-off-by Martin Ågren <[email protected]>

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

convert.c static void convert_attrs(struct conv_attrs *ca, const char *path) · line 1043

Quoted 9 lines

convert.c +0 -1

index 1012462e3..943d957b4 100644
@@ -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.

convert.c static void convert_attrs(struct conv_attrs *ca, const char *path) · line 1060

Quoted 9 lines

convert.c +1 -0

              ca->ident = git_path_check_ident(ccheck + 1);
              ca->drv = git_path_check_convert(ccheck + 2);
              if (ca->crlf_action != CRLF_BINARY) {

@@ -1058,6 +1057,7 @@ static void convert_attrs(struct conv_attrs *ca, const char *path)
      } else {
              ca->drv = NULL;
              ca->crlf_action = CRLF_UNDEFINED;
+             ca->attr_action = CRLF_UNDEFINED;

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

Quoted 6 lines

convert.c +0 -1

              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:

convert.c +0 -1

index 1012462e3c..fd91b91ada 100644
@@ -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) {

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 <[email protected]>

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

builtin/pack-objects.c +3 -0

index c753e9237..bd391e97a 100644
@@ -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);
 

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.

Quoted 13 lines · Martin Ågren

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

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

Quoted 4 lines

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

hashmap.c +3 -0

index 9b6a12859b..be97642daa 100644
@@ -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)

hashmap.c +0 -0

        /* fix size and rehash if appropriate */
        map->size--;

        if (map->size < map->shrink_at)

hashmap.h +0 -0

index 7a8fa7fa3d..ec9541b981 100644

hashmap.h +9 -0

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

Quoted 53 lines · Jeff Hostetler

Quoted 13 lines · Martin Ågren

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

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

Quoted 4 lines

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

hashmap.c +3 -0

index 9b6a12859b..be97642daa 100644
@@ -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)

hashmap.c void *hashmap_remove(struct hashmap *map, const void · line 232

Quoted 7 lines

hashmap.c +3 -0

@@ -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 10 lines

hashmap.c +0 -0

        /* fix size and rehash if appropriate */
        map->size--;

        if (map->size < map->shrink_at)

hashmap.h +0 -0

index 7a8fa7fa3d..ec9541b981 100644
@@ -183,7 +183,8 @@ struct hashmap {
        const void *cmpfn_data;
 

hashmap.h struct hashmap { · line 187

Quoted 4 lines

hashmap.h +2 -1

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

Quoted 25 lines

hashmap.h +9 -0

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

Quoted 5 lines

hashmap.h struct hashmap { · line 187

Quoted 4 lines

        /* total number of entries (0 means the hashmap is empty) */

hashmap.h +2 -1

-       unsigned int size;
+       /* -1 means size is unknown for threading reasons */
+       int size;

Quoted 7 lines

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

Quoted 5 lines

hashmap.h struct hashmap { · line 187

Quoted 4 lines

        /* total number of entries (0 means the hashmap is empty) */

hashmap.h +2 -1

-       unsigned int size;
+       /* -1 means size is unknown for threading reasons */
+       int size;

Quoted 7 lines

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.

Quoted 1 line

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

yes, I do.

Quoted 4 lines

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

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.

Quoted 3 lines

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.

Quoted 30 lines · Stefan Beller

Quoted 13 lines

Quoted 5 lines

hashmap.h struct hashmap { · line 187

Quoted 4 lines

         /* total number of entries (0 means the hashmap is empty) */

hashmap.h +2 -1

-       unsigned int size;
+       /* -1 means size is unknown for threading reasons */
+       int size;

Quoted 7 lines

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.

Quoted 1 line

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

yes, I do.

Quoted 4 lines

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

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

Quoted 7 lines

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

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

Quoted 3 lines

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

From: Jeff Hostetler <[email protected]>

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 <[email protected]>

---

name-hash.c +0 -0

index 0e10f3e..829ff59 100644

Quoted 3 lines · Jeff Hostetler

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

Quoted 13 lines

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.

Quoted 2 lines

Signed-off-by Jeff Hostetler <[email protected]>

---

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.

hashmap.h static inline void hashmap_entry_init(void *entry, unsigned int hash) · line 263

Quoted 1 line

hashmap.h +1 -0

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

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

hashmap.h static inline void hashmap_entry_init(void *entry, unsigned int hash) · line 264

Quoted 1 line

hashmap.h +1 -0

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

Hi,

Quoted 5 lines · Johannes Schindelin

Quoted 3 lines · Jeff Hostetler

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 13 lines · Jonathan Nieder

Hi,

Quoted 7 lines · Johannes Schindelin

Quoted 3 lines · Jeff Hostetler

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

Quoted 5 lines

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.

Quoted 1 line

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

[...]

Quoted 3 lines

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.

hashmap.h static inline void hashmap_entry_init(void *entry, unsigned int hash) · line 263

Quoted 1 line

hashmap.h +1 -0

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

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

hashmap.h static inline void hashmap_entry_init(void *entry, unsigned int hash) · line 264

Quoted 1 line

hashmap.h +1 -0

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

Quoted 12 lines

hashmap.h +12 -0

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

Quoted 1 line

+}

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.

Quoted 14 lines · Johannes Schindelin

Quoted 1 line

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

[...]

Quoted 12 lines

hashmap.h +12 -0

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

Quoted 8 lines

Quoted 1 line

+}

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

Quoted 2 lines · Johannes Schindelin

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

Quoted 13 lines

hashmap.h +12 -0

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

Quoted 8 lines

Quoted 1 line

+}

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

Quoted 6 lines · Johannes Schindelin

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

Hi Jeff,

Quoted 18 lines · Jeff Hostetler

From: Jeff Hostetler <[email protected]>

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.

Quoted 2 lines

Signed-off-by Jeff Hostetler <[email protected]>

---

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.

hashmap.h static inline void hashmap_entry_init(void *entry, unsigned int hash) · line 263

Quoted 13 lines

hashmap.h +8 -0

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

hashmap.h static inline void hashmap_entry_init(void *entry, unsigned int hash) · line 264

Quoted 1 line

hashmap.h +1 -0

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

Quoted 4 lines

hashmap.h +3 -0

+static inline void hashmap_enable_item_counting(struct hashmap *map)
+{
+	void *item;

hashmap.h static inline void *hashmap_iter_first(struct hashmap *map, · line 420

Quoted 10 lines

hashmap.h +10 -0

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

Quoted 6 lines

name-hash.c +0 -0

index 0e10f3e..829ff59 100644

name-hash.c static void lazy_init_name_hash(struct index_state *istate) · line 587

Quoted 10 lines

name-hash.c +4 -2

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

From: Jeff Hostetler <[email protected]>

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.

Quoted 9 lines · Jeff Hostetler

From: Jeff Hostetler <[email protected]>

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.

[snip]
+/*
+ * 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.
+ */

hashmap.h +3 -0

+static inline void hashmap_enable_item_counting(struct hashmap *map)
+{
+	void *item;

From: Jeff Hostetler <[email protected]>

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 <[email protected]>

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

Quoted 2 lines · Jeff Hostetler

From: Jeff Hostetler <[email protected]>

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

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

Quoted 12 lines · Martin Ågren

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

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

Quoted 3 lines

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/[email protected]/

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)

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 <[email protected]>

---
 strbuf.h | 12 ++++++++++++
 1 file changed, 12 insertions(+)

strbuf.h +6 -0

index e705b94db..295654d39 100644
@@ -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)				\

Quoted 31 lines · Martin Ågren

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

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

Signed-off-by Martin Ågren <[email protected]>

---
 strbuf.h | 12 ++++++++++++
 1 file changed, 12 insertions(+)

strbuf.h +6 -0

index e705b94db..295654d39 100644
@@ -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)                         \

strbuf.h static inline void strbuf_setlen(struct strbuf *sb, size_t len) · line 171

Quoted 10 lines

strbuf.h +6 -0

+                     assert(!strbuf_slopbuf[0]);                     \
+             else                                                    \
+                     _sb->buf[0] = '\0';                             \
+     } while (0)
+#else
 #define strbuf_reset(sb)  strbuf_setlen(sb, 0)
+#endif
 
 
 /**

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

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

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

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

strbuf.h +0 -0

index 2075384e0b..1a77fe146a 100644
@@ -147,7 +147,10 @@ static inline void strbuf_setlen(struct strbuf *sb, size_t len)
        if (len > (sb->alloc ? sb->alloc - 1 : 0))

Quoted 15 lines

strbuf.h +4 -1

index 2075384e0b..1a77fe146a 100644
@@ -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]);
 }
 

strbuf.h static inline void strbuf_setlen(struct strbuf *sb, size_t len) · line 156

Quoted 1 line

strbuf.h +0 -0

 /**

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

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

ThreadSanitizer: add suppressions

Quoted 10 lines · Martin Ågren

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

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

I 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 1 line

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/[email protected]/

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

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.

Suggested-by Junio C Hamano <[email protected]>

Signed-off-by Martin Ågren <[email protected]>

---
v2: no "ifdef TSAN"; moved check from strbuf_reset into strbuf_setlen

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

strbuf.h +4 -1

index e705b94db..7496cb8ec 100644
@@ -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]);
 }
 
 /**

Quoted 7 lines · Martin Ågren

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

Quoted 4 lines

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

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

Quoted 4 lines

Suggested-by Junio C Hamano <[email protected]>

Signed-off-by Martin Ågren <[email protected]>

---
v2: no "ifdef TSAN"; moved check from strbuf_reset into strbuf_setlen

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

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

Quoted 9 lines · Junio C Hamano

Quoted 7 lines · Martin Ågren

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

Quoted 6 lines

Quoted 4 lines

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

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

Indeed. :-)

Quoted 8 lines

Quoted 4 lines

Suggested-by Junio C Hamano <[email protected]>

Signed-off-by Martin Ågren <[email protected]>

---
v2: no "ifdef TSAN"; moved check from strbuf_reset into strbuf_setlen

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

Quoted 4 lines

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

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

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:

strbuf.h +4 -2

index e705b94db..7496cb8ec 100644
@@ -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

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

strbuf.h +4 -3

index e705b94..fcca618 100644
@@ -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

Quoted 2 lines · Brandon Casey

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

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

Quoted 5 lines · Junio C Hamano

Quoted 2 lines · Brandon Casey

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

Quoted 3 lines

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

I think you mean something like this:

   const char * const strbuf_slopbuf = "";

Quoted 6 lines · Brandon Casey

Quoted 5 lines · Junio C Hamano

Quoted 2 lines · Brandon Casey

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

Quoted 7 lines

Quoted 3 lines

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

I think you mean something like this:

   const char * const strbuf_slopbuf = "";

Ah, you probably meant something like this:

   const char strbuf_slopbuf = '\0';

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

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

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

Quoted 5 lines · Brandon Casey

Ah, you probably meant something like this:

   const char strbuf_slopbuf = '\0';

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

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

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

Quoted 4 lines

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

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

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

Quoted 11 lines · Junio C Hamano

Quoted 5 lines · Brandon Casey

Ah, you probably meant something like this:

   const char strbuf_slopbuf = '\0';

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

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

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

Quoted 4 lines

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

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

   const char strbuf_slopbuf[1];

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

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

   const char * const strbuf_slopbuf = "";

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

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

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

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

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

   const char strbuf_slopbuf[1] = "";

Quoted 8 lines

Quoted 4 lines

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

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

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

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

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

Quoted 5 lines · Junio C Hamano

Quoted 2 lines · Brandon Casey

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

Quoted 3 lines

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

I think you mean something like this:

   const char * const strbuf_slopbuf = "";

Quoted 10 lines · Brandon Casey

Quoted 8 lines · Junio C Hamano

Quoted 2 lines · Brandon Casey

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

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

Quoted 3 lines

I think you mean something like this:

   const char * const strbuf_slopbuf = "";

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

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