原子自增并原子赋值给共享原子变量的高效实现问询

现有全局原子变量：

std::atomic_int next_free_block;

多个线程会访问一个可能被共享的原子变量：

std::atomic_int child_offset;

需要原子执行如下逻辑：

if (child_offset != 0) child_offset = next_free_block++;

直接实现会引发多线程冲突；尝试用CAS实现时，CAS失败会导致next_free_block自增的副作用残留，造成内存分配间隙。已知用mutex可以实现，但希望用原子操作高效完成。

该需求来自并行构建大型树的场景，树结构定义如下：

struct tree_page {
    atomic<uint32_t> allocated;
    uint32_t child_offset[8];
    uint32_t nodes[1015];
};

树按层级构建，每个非叶节点对应一个线程。当当前页无剩余空间时，需要从全局next_free_page分配新页并赋值给child_offset数组元素，对应代码中需要原子执行上述赋值操作。

核心思路是把next_free_block的自增操作延后到CAS成功时执行，避免CAS失败导致的无效自增，具体实现如下：

std::atomic_int child_offset;
std::atomic_int next_free_block;

void atomic_assign_child_offset() {
    int expected = 0;
    // 循环直到CAS成功或child_offset已被其他线程赋值
    while (true) {
        // 读取当前child_offset的值
        expected = child_offset.load(std::memory_order_acquire);
        if (expected != 0) {
            // child_offset已被赋值，直接退出
            break;
        }
        // 先获取待分配的块编号，暂不修改全局变量
        int desired = next_free_block.load(std::memory_order_relaxed);
        // 尝试CAS：若child_offset仍为0，则将其设为desired
        if (child_offset.compare_exchange_strong(expected, desired,
                                                 std::memory_order_release,
                                                 std::memory_order_acquire)) {
            // CAS成功后，再自增next_free_block，确保只有成功分配才消耗块
            next_free_block.fetch_add(1, std::memory_order_relaxed);
            break;
        }
        // CAS失败，说明其他线程修改了child_offset，重新循环检查
    }
}

逻辑细节 #

1. 先检查child_offset是否已被赋值（非0），如果是直接退出，避免无效操作
2. 读取当前next_free_block的值作为分配目标，但此时不修改全局变量
3. CAS尝试替换child_offset：
   • 成功：当前线程获得分配权，此时再自增next_free_block，保证每个成功分配只消耗一个块，无间隙
   • 失败：其他线程已修改child_offset，重新进入循环检查

内存序说明 #

• 使用memory_order_acquire/memory_order_release确保线程间操作的可见性和顺序，避免内存重排问题
• next_free_block的load和fetch_add用memory_order_relaxed即可，它仅用于生成递增编号，无需强同步

适配树场景的扩展 #

针对tree_page中的child_offset[8]数组，需先将数组元素改为原子类型（原结构中是普通uint32_t，多线程访问不安全），再封装成索引化的函数：

// 修改后的tree_page结构
struct tree_page {
    atomic<uint32_t> allocated;
    atomic<uint32_t> child_offset[8];
    uint32_t nodes[1015];
};

std::atomic<uint32_t> next_free_page;

void assign_child_offset(tree_page& page, int idx) {
    uint32_t expected = 0;
    while (true) {
        expected = page.child_offset[idx].load(std::memory_order_acquire);
        if (expected != 0) break;
        uint32_t desired = next_free_page.load(std::memory_order_relaxed);
        if (page.child_offset[idx].compare_exchange_strong(expected, desired,
                                                           std::memory_order_release,
                                                           std::memory_order_acquire)) {
            next_free_page.fetch_add(1, std::memory_order_relaxed);
            break;
        }
    }
}

内容的提问来源于stack exchange，提问作者konsolas