c - 取消引用指针时的竞争条件

Question

我们正在一个非常简单的内存池中工作，我们发现了一个非常有趣的错误，但我们无法解决。

该算法的思想如下:有一个“可用”内存块的堆栈，因此每个 block 都有一个指向下一个可用 block 的指针。为了避免出现辅助数据结构，我们决定使用相同的内存块来存储指针。因此，通过取消引用该 block 来获得下一个可用 block : void *nextChunk = *((void **)chunk)

该代码最初是使用 C++ 原子实现的，但我们可以简化它并使用 C 原子内在函数重现问题:

void *_topChunk;

void *getChunk()
{
    void *chunk;

    // Try to reserve a chunk (for these tests, it has been forced that _topChunk can never be null)
    do {
        chunk = _topChunk;
    } while(!__sync_bool_compare_and_swap(&_topChunk, chunk, *((void **)chunk)));

    return chunk;
}

void returnChunk(void *chunk)
{
    do {
        *((void **)chunk) = _topChunk;
    } while (!__sync_bool_compare_and_swap(&_topChunk, *((void **)chunk), chunk));
}

对于我们为调试此问题而运行的测试，我们生成了多个执行此操作的线程:

while (1) {
    void *ptr = getChunk();
    *((void **)ptr) = (void *)~0ULL;
    returnChunk(ptr);
}

在执行过程中的某个时刻，getChunk() 会出现段错误，因为它试图取消引用 0xfff... 指针。但从 returnChunk() 中写入的内容来看，*((void **)chunk) 永远不应该是 0xfff...，它应该是来自堆栈的有效指针。为什么不起作用？

我们也尝试过使用中间的void *，而不是直接取消引用，结果是完全一样的。

Answer 1

我认为问题出在函数 getChunk 中。 __sync_bool_compare_and_swap 的第三个参数可能已过时。让我们看一下 getChunk 的稍微修改版本:

void *getChunk()
{
    void *chunk;
    void *chunkNext;

    // Try to reserve a chunk (for these tests, it has been forced that _topChunk can never be null)
    do {
        chunk = _topChunk;
        chunkNext = *(void **)chunk;
        //chunkNext might have been changed meanwhile, but chunk is the same!! 
    } while(!__sync_bool_compare_and_swap(&_topChunk, chunk, chunkNext));
    return chunk;
}

假设我们有一个由三个 block 组成的简单链，位于地址 0x100、0x200 和 0x300。我们需要三个线程(A、B 和 C)来打破链条:

//The Chain: TOP -> 0x100 -> 0x200 -> 0x300 -> NIL
 Thread   
 A      chnk     = top;         //is 0x100
 A      chnkNext = *chnk;       //is 0x200
   B       chnk = top           //is 0x100
   B       chnkNext = *chnk;    //is 0x200
   B       syncSwap();          //okay, swap takes place
   B       return chnk;         //is 0x100
   /*** The Chain Now: TOP -> 0x200 -> 0x300 -> NIL ***/
     C        chnk = top;      //is 0x200
     C        chnkNext = *chnk //is 0x300
     C        syncSwap         //okay, swap takes place
     C        return chnk;     //is 0x200
   /*** The Chain Now: TOP -> 0x300 -> NIL ***/
   B       returnChunk(0x100); 
   /*** The Chain Now: TOP -> 0x100 -> 0x300 -> NIL ***/
 A      syncSwap(&Top, 0x100, 0x200 /*WRONG, *chnk IS NOW 0x300!!!!*/  );
 A      return chnk;