ポインタの逆参照時の競合条件

Question

非常に単純なメモリプールで作業しており、解決できなかった非常に興味深いバグを発見しました。

アルゴリズムの考え方は次のとおりです。「利用可能な」メモリチャンクのスタックがあるため、各チャンクは次の利用可能なチャンクへのポインタを持ちます。二次的なデータ構造を避けるために、この同じメモリチャンクを使用してポインタを格納することにしました。したがって、次の利用可能なチャンクは、このチャンクを逆参照することによって得られます。void * nextChunk = *（（void **）チャンク）

このコードは元々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の3番目のパラメータが古くなっている可能性があります。のは、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; 
} 

たちはアドレス0x100のに配置された3つのチャンク、0x200からと0x300というのシンプルなチェーンを持っていると仮定します。そして、我々はチェーン破るために3つのスレッド（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;