Re: [lttng-dev] [PATCH 00/11] Add support for TSAN to liburcu

[Olivier Dion via lttng-dev <lttng-dev@lists.lttng.org>]

[-- Attachment #1: Type: text/plain, Size: 209 bytes --]

Hi Dmitry,

We do have a new issue and we think it might be a limitation from TSAN.

Find attached a test program that we believe is correct.  You can
compile it with `gcc -fsanitize=thread test.c -pthread'.


[-- Attachment #2: test.c --]
[-- Type: application/octet-stream, Size: 2035 bytes --]

#include <stdlib.h>
#include <stdint.h>

#include <pthread.h>

#define LOOP 1000

struct node {
	struct node *next;
};

static pthread_barrier_t barrier;
static struct node the_terminal_node = { .next = &the_terminal_node };
static struct node pending_stack = { &the_terminal_node };

extern void __tsan_acquire(void*);
extern void __tsan_release(void*);

extern void __tsan_ignore_thread_begin();
extern void __tsan_ignore_thread_end();

static void *push_worker(void *nil)
{
	(void) nil;

	pthread_barrier_wait(&barrier);

	for (size_t k=0; k<LOOP; ++k){
		struct node *new_node, *old_node;

		new_node = calloc(1, sizeof(struct node));
		old_node = __atomic_exchange_n(&pending_stack.next,
					       new_node,
					       __ATOMIC_SEQ_CST);
		/* Works if RELEASE. */
		__atomic_store_n(&new_node->next, old_node, __ATOMIC_RELAXED);

		/* Also works if: */
#if 0
		__tsan_ignore_thread_begin();
		__atomic_store_n(&new_node->next, old_node, __ATOMIC_RELAXED);
		__tsan_ignore_thread_end();
#endif
		/* Why is this not working? */
#if 0
		__tsan_release(&new_node->next);
		__atomic_store_n(&new_node->next, old_node, __ATOMIC_RELAXED);
#endif

	}

	return NULL;
}

static void *pop_worker(void *nil)
{
	(void) nil;

	size_t k = 0;

	pthread_barrier_wait(&barrier);

	while (k < LOOP) {
		struct node *current_stack;
		struct node *next_node;

		current_stack = __atomic_exchange_n(&pending_stack.next,
						    &the_terminal_node,
						    __ATOMIC_SEQ_CST);

		while (current_stack != &the_terminal_node) {

		retry_load:
			next_node = __atomic_load_n(&current_stack->next,
						    __ATOMIC_CONSUME);

			if (!next_node) {
				goto retry_load;
			}

			free(current_stack);
			current_stack = next_node;
			++k;
		}
	}

	return NULL;
}

int main(void)
{
	pthread_t ths[2];

	pthread_barrier_init(&barrier, NULL, 3);

	pthread_create(&ths[0], NULL, push_worker, NULL);
	pthread_create(&ths[1], NULL, pop_worker, NULL);

	pthread_barrier_wait(&barrier);

	pthread_join(ths[0], NULL);
	pthread_join(ths[1], NULL);

	return 0;
}

[-- Attachment #3: Type: text/plain, Size: 821 bytes --]


TSAN flags a race condition between the atomic store relaxed at line 36
and the free at line 81.

We can solve the issue by replacing the atomic store relaxed with a
atomic store release.  However, the preceding atomic exchange with
sequential consistency already acts as an implicit release (in term of
memory barrier) for the following store, making the release semantic
redundant.

We've found an alternative to fix this by ignoring the thread during the
relaxed store (line 39).  However, what we would like is to annotate the
memory stored (line 45).

My theory (I don't know the internal of TSAN much) is that TSAN thinks
for some reason that the atomic store relaxed happen at the same epoch
as the free, resulting in a false positive.  If so, m

Thought?

-- 
Olivier Dion
EfficiOS Inc.
https://www.efficios.com

[-- Attachment #4: Type: text/plain, Size: 156 bytes --]

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev