decomitting mpmcstack elements

[nwf]

As noted by the comment in ds/mpmcstack.h pop(), it's unsafe to decommit memory used for stack nodes. Presumably this means that snmalloc can't discard large slab headers, even if it discards the rest of the heap? Are there other bits of memory that are pinned as a result? If there's quite a bit, should something like hazard pointers or urcu synchronization be deployed here?

[mjp41]

We don't currently support any form of tear down mid way through an application. We could implement hazards, epochs, or other things to enable this. But currently don't see the need. We do have to keep the first page of a large alloc live, but we are using this as the entry in the large stack, so we never decommit that memory. This is all handled globally, so shared across threads.

I have another project that uses this stack with an epoch layer wrapped on top to handle deallocation. So that could be added if we see a performance issues in memory usage.

[nwf]

Speaking of mpmcstack elements...

I note that LargeAlloc::alloc will alias the LargeSlab, including the MPMCStack's next pointer, and the user's allocation. I think this means that the MPMCStack::pop method will encounter undefined behavior, if two of them race: the loser of the race may read a memory word from an object other than the LargeSlab now resident at this address (it will fail the CAS, thankfully, but nevertheless will have read user memory). In de facto C++, I'm sure this is fine, but the standard may say something else.

[davidchisnall]

Nathaniel Wesley Filardo (@nwf), sounds like a fun example to share with the REMS meeting on Wednesday...

[nwf]

The consensus, I think, of the REMS group is that the design seen for intrusive linked lists which alias with user memory, which may be distilled, ignoring ABA, to two instances of the code below running in parallel, is undefined behavior.

std::atomic<void *> o = h.load(std::memory_order_relaxed);
void *n = o.load(std::memory_order_acquire);
if(h.compare_and_swap(o, n, std::memory_order_relaxed, std::memory_order_relaxed))
  *o = 1;

The user's store (*o = 1) data-races with the other thread's load of n and that's that; the fact that we're "about" to fail the CAS doesn't save us from anything and doesn't bound the badness of the undefined behavior. Architecturally, OTOH, it's probably fine.

[mjp41]

With the redesign in 0.6.0 this is no longer relevant as we don't have type races with MPMCStacks, and are only using the pagemap for this state. So I believe this can be closed.