如果这不是boost :: lockfree :: detail :: freelist中的错误，我在这里错过了什么? [英] If this is not a bug in boost::lockfree::detail::freelist, what am I missing here?

问题描述

在此文件中， boost :: lockfree :: detail :: freelist 类用于使用

In this file, the boost::lockfree::detail::freelist class is used to manage storage for a lock-free data structure (e.g., a queue), using a free list. The deallocate_impl method is used to free nodes by linking them back into the free list (a freed node becomes the new head of the free list, displacing the old head). This method is supposed to be thread-safe and lock-free. The original source code of one instance is duplicated here with my comments annotated to point out the suspicious code (potential bug?):

void deallocate_impl (index_t index)
{
    freelist_node * new_pool_node =
           reinterpret_cast<freelist_node*>(NodeStorage::nodes() + index);

    // Shouldn't this line be placed inside the loop?
    // The loop continues as long as the compare-and-exchange fails,
    // which happens if the pool head has been concurrently updated.
    // In that case, we MUST reload the new value of "pool_" to
    // reuse its tag, link the new free-list head to it and
    // compare against in the compare_and_exchange call.
    tagged_index old_pool = pool_.load(memory_order_consume);

    for(;;) {
        // The old pool head tag is reused here without causing
        // any ABA problems. However, if "index" is the same as
        // old_pool.get_index(), a self-reference is written.
        tagged_index new_pool (index, old_pool.get_tag());
        new_pool_node->next.set_index(old_pool.get_index());

        if (pool_.compare_exchange_weak(old_pool, new_pool))
            return;
    }
}

我在Boost 1.62.0中也看到了相同的实现

I have seen the same implementation in Boost 1.62.0 too

推荐答案

只要比较和交换失败，循环就会继续，如果池头已同时更新，则会发生这种情况.在这种情况下，我们必须重新加载"pool_"的新值以重用其标记...

The loop continues as long as the compare-and-exchange fails, which happens if the pool head has been concurrently updated. In that case, we MUST reload the new value of "pool_" to reuse its tag...

compare_exchange_weak()在每次调用后将 pool _ 的先前值写入 old_pool . compare_exchange_weak() .

compare_exchange_weak() writes previous value of pool_ into old_pool after each call. Documentation for compare_exchange_weak().

但是，如果索引"与old_pool.get_index()相同...

However, if "index" is the same as old_pool.get_index()...

这可能不会发生，因为具有该索引的节点尚未移至空闲列表.

This probably cannot happen, since node with that index was not moved to free list yet.

这篇关于如果这不是boost :: lockfree :: detail :: freelist中的错误，我在这里错过了什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！