使用 64 位指针进行无锁内存回收

StackOverflow https://stackoverflow.com/questions/1061889

  •  21-08-2019
  •  | 
  •  

题

赫利希和沙维特的书（多处理器编程的艺术）内存回收的解决方案使用Java的 AtomicStampedReference<T>;.

我想，要用 C++ 为 x86_64 编写一个交换操作，至少需要 12 字节交换操作 - 8 个字节用于 64 位指针，4 个字节用于 int。

是否有 x86 硬件支持，如果没有，是否有任何关于如何在没有它的情况下进行无等待内存回收的指示？

有帮助吗？

解决方案

是的，有硬件的支持，虽然我不知道它是由C ++库曝光。无论如何，如果你不介意做一些低级别的不可移植的汇编语言挂羊头卖狗肉 - 仰望CMPXCHG16B指令英特尔手册

。

其他提示

好吧，希望我有这本书，

对于其他可能提供答案的人来说，重点是实现此类： 

class AtomicReference<T>{
  public:
    void set(T *ref, int stamp){ ... }
    T *get(int *stamp){ ... }
  private:  
    T *_ref; 
    int _stamp;

};

以无锁的方式，以便：

  • set() 以原子方式更新引用和标记。
  • get() 返回引用并将 *stamp 设置为与引用对应的标记。

如果我错了，JDonner 请纠正我。

现在我的回答是：我不认为你可以在某个地方没有锁的情况下做到这一点（锁可以是 while(test_and_set() != ..)）。因此，没有可用的无锁算法。这意味着可以为任何 N 以无锁方式构建 N 个寄存器。

如果您查看书 pragma 9.8.1，AtomicMarkableReference 与整数标记中的单个位相同。作者建议从指针中“窃取”一点，以从单个单词中提取标记和指针（几乎被引用），这显然意味着他们想要使用单个原子寄存器来完成此操作。

然而，可能有一种方法可以在没有它的情况下消除无等待内存回收。我不知道。

是，64支持此;你需要使用CMPXCHG16B。

可以通过依赖于一个事实，即指针将使用小于64位节省存储器的位。首先，定义一个函数compare&set（此ASM工作在GCC＆ICC）：

inline bool CAS_ (volatile uint64_t* mem, uint64_t old_val, uint64_t new_val)
{
  unsigned long old_high = old_val >> 32, old_low = old_val;
  unsigned long new_high = new_val >> 32, new_low = new_val;

  char res = 0;
  asm volatile("lock; cmpxchg8b (%6);"
               "setz %7; "
               : "=a" (old_low),  // 0
                 "=d" (old_high)  // 1
               : "0" (old_low),   // 2
                 "1" (old_high),  // 3
                 "b" (new_low),   // 4
                 "c" (new_high),  // 5
                 "r" (mem),       // 6
                 "m" (res)        // 7
               : "cc", "memory");
  return res;
}

然后您就需要构建一个标记指针类型。我假设具有128字节（像的Nehalem）高速缓存行宽度为40位的指针。对准高速缓存线将通过减少假共享，竞争等给予极大的速度提升;这具有使用的很多更多存储器，在某些情况下的明显的折衷。

template <typename pointer_type, typename tag_type, int PtrAlign=7, int PtrWidth=40>
struct tagged_pointer
{
  static const unsigned int PtrMask = (1 << (PtrWidth - PtrAlign)) - 1;
  static const unsigned int TagMask = ~ PtrMask;

  typedef unsigned long raw_value_type;

  raw_value_type raw_m_;

  tagged_pointer () : raw_m_(0) {}
  tagged_pointer (pointer_type ptr) { this->pack(ptr, 0); }
  tagged_pointer (pointer_type ptr, tag_type tag) { this->pack(ptr, tag); }

  void pack (pointer_type ptr, tag_type tag)
  {
    this->raw_m_ = 0;
    this->raw_m_ |= ((ptr >> PtrAlign) & PtrMask);
    this->raw_m_ |= ((tag << (PtrWidth - PtrAlign)) & TagMask);
  }

  pointer_type ptr () const
  {
    raw_value_type p = (this->raw_m_ & PtrMask) << PtrAlign;
    return *reinterpret_cast<pointer_type*>(&p);
  }

  tag_type tag () const
  {
    raw_value_type t = (this->raw_m_ & TagMask) >> (PtrWidth - PtrAlign_;
    return *reinterpret_cast<tag_type*>(&t);
  }
};

我还没有机会调试代码，所以你需要做的，但这是一般的想法。

请注意，x86_64体系和gcc可以启用128位CAS。它可与-mcx16 GCC选项被启用。

int main()
{
   __int128_t x = 0;
   __sync_bool_compare_and_swap(&x,0,10);
   return 0;
}

与编译：

gcc -mcx16 file.c

cmpxchg16b 操作提供了预期的操作，但请注意一些较旧的 x86-64 处理器没有此指令。

然后，您只需要使用计数器和指针以及 asm 内联代码构建一个实体。我在这里写了一篇关于该主题的博客文章：实现通用双字比较和交换

不过，如果您只是想防止早期释放和 ABA 问题，则不需要此操作。危险指针更简单，不需要特定的 asm 代码（只要使用 C++11 原子值。）我在 bitbucket 上有一个存储库，其中包含各种无锁算法的实验实现： 无锁实验 （请注意，所有这些实现都是实验玩具，而不是可靠且经过测试的生产代码。）

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top