Split write bug with shared memory neighbor lists #1445

Thanks to @jtramm for pointing out this issue. It's been taking me a little time to fully understand it and find the right fix so I just wanted to call it out here on the repo page.

With #1140, neighbor lists are implemented as a shared-memory linked list. Threads are allowed to read a list while another thread is concurrently writing to the same list. I thought this would be fine due to some guarantees in the standard that list iterators are not invalidated by write operations. But in hindsight, I don't think they protect us from concurrent read/write on the same list node.

We generally expect linked lists to be implemented with nodes like this:

struct NeighborListNode
{
  NeighborListNode* next;
  int32_t value;
};

And we might run into trouble with split-reads on that next pointer. If writing to that pointer takes two CPU operations, then we could have the case where thread 1 modifies the first half of next, thread 2 reads the halfway-modified and invalid next, then thread 1 finishes modifying next.

In practice this bug is tough to run into on CPUs. On a 64-bit machine that pointer should be a quadword, and reading or writing an aligned quadword is guaranteed atomic on an Intel CPU. (I assume it's the same for AMD and IBM CPUs.) So I think you need to force an unaligned next in order to see this on a typical CPU, e.g.:

struct NeighborListNode
{
  int32_t value;
  NeighborListNode* next;
} __attribute__((packed));

I'm hoping that packed struct will allow me to test potential fixes on a CPU, but I haven't confirmed yet that it picks up the split-write bug. I don't know anything about GPUs so maybe they are much more likely to hit this bug.

I've done a little testing with

struct NeighborListNode
{
  std::atomic<NeighborListNode*> next;
  int32_t value;
};

that's accessed with operations like next.load(std::memory_order_relaxed). The performance results look promising. No measurable change in runtime for some multiphysics calcs I'm running. But I need to run some more tests to be sure. If it does prove to be slow that are some other options that rely on just one atomic per list instead of one atomic per list node.