memory-management - 从右开始查找单词中的第一个零位 (LSB)

Question

我正在为我的程序编写一个小型平板分配器，但是在阅读了 IBM 的一篇关于无锁堆的论文之后，我决定实现类似的东西，而不是使用带有锁定机制的列表。但是，哪种 GCC 内在函数（ffs/ffz/ctz 等）最有效，为什么？

我最有可能的目标是带有CLZ硬件指令的 ARMv7 和 ARMv6 处理器。

我想出了类似的东西

uint32_t tmp;
uint32_t new_bits;
uint32_t old_bits;

do {
    old_bits = slab->bitmap;
    tmp = <function>(old_bitmap);
    new_bits = old_bits | (1 << tmp);
} while(cpu_atomic_cmpxchg(&slab->bitmap, old_bits, new_bits) != OS_OKAY);

return ((void *) slab->start + (tmp * slab->blksize))

Answer 1

如果您有 CTZ，则只需反转值并计算尾随零：

if (x == -1ULL)
    return /* failure? */;
int index = __builtin_ctz(~x);

例如

                                      v
 x = 0000 1111 0000 1111 0000 1111 0000 1111
~x = 1111 0000 1111 0000 1111 0000 1111 0000
index = __builtin_ctz(~x) = 4