为什么ThreadSanitizer报告这个无锁示例存在竞态条件?

27

我将其简化为一个简单的自包含示例。主线程排队1000个项目,工作线程尝试并发出队。即使有一个获取-释放内存屏障序列保护它们,ThreadSanitizer也会抱怨其中一个元素的读取和写入之间存在竞争。

#include <atomic>
#include <thread>
#include <cassert>

struct FakeQueue
{
    int items[1000];
    std::atomic<int> m_enqueueIndex;
    int m_dequeueIndex;

    FakeQueue() : m_enqueueIndex(0), m_dequeueIndex(0) { }

    void enqueue(int x)
    {
        auto tail = m_enqueueIndex.load(std::memory_order_relaxed);
        items[tail] = x;              // <- element written
        m_enqueueIndex.store(tail + 1, std::memory_order_release);
    }

    bool try_dequeue(int& x)
    {
        auto tail = m_enqueueIndex.load(std::memory_order_acquire);
        assert(tail >= m_dequeueIndex);
        if (tail == m_dequeueIndex)
            return false;
        x = items[m_dequeueIndex];    // <- element read -- tsan says race!
        ++m_dequeueIndex;
        return true;
    }
};


FakeQueue q;

int main()
{
    std::thread th([&]() {
        int x;
        for (int i = 0; i != 1000; ++i)
            q.try_dequeue(x);
    });

    for (int i = 0; i != 1000; ++i)
        q.enqueue(i);

    th.join();
}

线程安全检测器输出:

==================
WARNING: ThreadSanitizer: data race (pid=17220)
  Read of size 4 at 0x0000006051c0 by thread T1:
    #0 FakeQueue::try_dequeue(int&) /home/cameron/projects/concurrentqueue/tests/tsan/issue49.cpp:26 (issue49+0x000000402bcd)
    #1 main::{lambda()#1}::operator()() const <null> (issue49+0x000000401132)
    #2 _M_invoke<> /usr/include/c++/5.3.1/functional:1531 (issue49+0x0000004025e3)
    #3 operator() /usr/include/c++/5.3.1/functional:1520 (issue49+0x0000004024ed)
    #4 _M_run /usr/include/c++/5.3.1/thread:115 (issue49+0x00000040244d)
    #5 <null> <null> (libstdc++.so.6+0x0000000b8f2f)

  Previous write of size 4 at 0x0000006051c0 by main thread:
    #0 FakeQueue::enqueue(int) /home/cameron/projects/concurrentqueue/tests/tsan/issue49.cpp:16 (issue49+0x000000402a90)
    #1 main /home/cameron/projects/concurrentqueue/tests/tsan/issue49.cpp:44 (issue49+0x000000401187)

  Location is global 'q' of size 4008 at 0x0000006051c0 (issue49+0x0000006051c0)

  Thread T1 (tid=17222, running) created by main thread at:
    #0 pthread_create <null> (libtsan.so.0+0x000000027a67)
    #1 std::thread::_M_start_thread(std::shared_ptr<std::thread::_Impl_base>, void (*)()) <null> (libstdc++.so.6+0x0000000b9072)
    #2 main /home/cameron/projects/concurrentqueue/tests/tsan/issue49.cpp:41 (issue49+0x000000401168)

SUMMARY: ThreadSanitizer: data race /home/cameron/projects/concurrentqueue/tests/tsan/issue49.cpp:26 FakeQueue::try_dequeue(int&)
==================
ThreadSanitizer: reported 1 warnings

命令行:

g++ -std=c++11 -O0 -g -fsanitize=thread issue49.cpp -o issue49 -pthread

g++版本: 5.3.1

有人能解释一下为什么tsan认为这是数据竞争吗?


更新

看起来这是一个误报。为了让ThreadSanitizer满意,我已经添加了注释(参见此处支持的内容和此处的示例)。请注意,通过宏检测GCC中是否启用tsan只是最近才添加的功能,因此目前我必须手动传递-D__SANITIZE_THREAD__给g++。

#if defined(__SANITIZE_THREAD__)
#define TSAN_ENABLED
#elif defined(__has_feature)
#if __has_feature(thread_sanitizer)
#define TSAN_ENABLED
#endif
#endif

#ifdef TSAN_ENABLED
#define TSAN_ANNOTATE_HAPPENS_BEFORE(addr) \
    AnnotateHappensBefore(__FILE__, __LINE__, (void*)(addr))
#define TSAN_ANNOTATE_HAPPENS_AFTER(addr) \
    AnnotateHappensAfter(__FILE__, __LINE__, (void*)(addr))
extern "C" void AnnotateHappensBefore(const char* f, int l, void* addr);
extern "C" void AnnotateHappensAfter(const char* f, int l, void* addr);
#else
#define TSAN_ANNOTATE_HAPPENS_BEFORE(addr)
#define TSAN_ANNOTATE_HAPPENS_AFTER(addr)
#endif

struct FakeQueue
{
    int items[1000];
    std::atomic<int> m_enqueueIndex;
    int m_dequeueIndex;

    FakeQueue() : m_enqueueIndex(0), m_dequeueIndex(0) { }

    void enqueue(int x)
    {
        auto tail = m_enqueueIndex.load(std::memory_order_relaxed);
        items[tail] = x;
        TSAN_ANNOTATE_HAPPENS_BEFORE(&items[tail]);
        m_enqueueIndex.store(tail + 1, std::memory_order_release);
    }

    bool try_dequeue(int& x)
    {
        auto tail = m_enqueueIndex.load(std::memory_order_acquire);
        assert(tail >= m_dequeueIndex);
        if (tail == m_dequeueIndex)
            return false;
        TSAN_ANNOTATE_HAPPENS_AFTER(&items[m_dequeueIndex]);
        x = items[m_dequeueIndex];
        ++m_dequeueIndex;
        return true;
    }
};

// main() is as before

现在ThreadSanitizer在运行时很高兴。


1
如果您在原子访问中使用顺序一致性,是否会有所不同? - MikeMB
不,tsan 仍然报告了一个竞争。 - Cameron
2
我认为你的“UPDATE”实际上是一个答案 - 而且是一个很好的答案!考虑将其从问题中移出并放入答案中。 - Toby Speight
1
@Toby:谢谢,但实际上这只是一个详细的例子,展示如何消除我的特定示例代码中的误报警告。user1887915提供了真正的答案(即tsan首先并不支持此类代码)。就像番茄/西红柿一样;-) - Cameron
2个回答

15

这看起来像是 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78158。通过反汇编GCC生成的二进制代码,可以看出它没有在O0级别上仪器化原子操作。

作为解决方法,您可以使用带有-O1/-O2选项的GCC来构建代码,或者获取一个最新的Clang版本并使用它来运行ThreadSanitizer(这是推荐的方式,因为TSan是作为Clang的一部分开发的,并且只被后移植到了GCC)。

上面的评论是无效的:TSan可以轻松理解您代码中原子操作之间的happens-before关系(可以通过在Clang下运行上面的重现程序来检查)。

我也不建议使用AnnotateHappensBefore()/AnnotateHappensAfter() 有两个原因:

  • 在大多数情况下,您不应该需要它们;它们表示代码正在执行非常复杂的操作(在这种情况下,您可能需要仔细检查是否正确执行);

  • 如果您在无锁代码中犯了错误,那么注释会掩盖该错误,导致TSan无法发现它。


2

ThreadSanitizer 不擅长计数,它不能理解在读取之前写入项目始终发生。

ThreadSanitizer 可以发现 m_enqueueIndex 的存储发生在加载之前,但它不理解当 tail > m_dequeueIndex 时,对 items[m_dequeueIndex] 的存储必须在加载之前发生。


2
您IP地址为143.198.54.68,由于运营成本限制,当前对于免费用户的使用频率限制为每个IP每72小时10次对话,如需解除限制,请点击左下角设置图标按钮(手机用户先点击左上角菜单按钮)。 - Vittorio Romeo
@VittorioRomeo 这是一个缺陷,但是是有意为之的。它会保持当前的行为,直到有人找到一种能够高效处理这种情况的_新_算法。 - user1887915
2
啊,我没意识到 ThreadSanitizer 可能会产生假阳性。在我找到的文档中完全没有明确说明 :-) 你链接的论文描述了最初的 ThreadSanitizer;据我理解,它已经被重写为编译器/运行时集成工具,而不是基于 valgrind 的工具。我不确定哪些部分仍然适用。我会尝试注释我的代码以使 tsan 满意。 - Cameron
4
ThreadSanitizer确实可能会产生误报,但这不是这里的情况(请参见我的下面评论)。不幸的是,关于基于Valgrind的ThreadSanitizer的论文已不再适用,也没有覆盖实际情况的“新”论文。您可以在YouTube上搜索“ThreadSanitizer”以获得对该工具现在如何运作的简要描述。 - Glider

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接