Single reader - multiple writer waitable lock-free unreliably ordered stack

The main body of code is located here. In the code linted_error is a platform specific type for error codes. As well, as an optimization the code can use Linux futexes.

• linted/mem.h is just a tiny wrapper around malloc.

• linted/sched.h does a bunch of stuff but is only used in this code to wrap platform specific pause instructions for spinlocks.

Otherwise, there are no other unportabilities.

I think the main problem with this implementation is that it doesn't use memory fences correctly. Am I right that I only need to use memory fences with memory_order_relaxed memory ordering. If so, then it should be possible to convert to usage of memory_order_relaxed easily and possibly obtain a small speedup right?

I also think it may be possible to use memory_order_relaxed without memory fences for the trigger code as triggers are supposed to be unreliable anyway.

Note that for my use case it doesn't matter what order things are inserted onto the stack.

The stack:

```
/*
* Copyright 2015 Steven Stewart-Gallus
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
* implied. See the License for the specific language governing
* permissions and limitations under the License.
*/
#include "config.h"

#include "linted/stack.h"

#include "linted/error.h"
#include "linted/mem.h"
#include "linted/node.h"
#include "linted/sched.h"
#include "linted/trigger.h"

#include
#include
#include

typedef _Atomic(struct linted_node *) atomic_node;

struct linted_stack {
atomic_node inbox;
struct linted_node *outbox;
struct linted_trigger inbox_f

Order of pops is strange

If I am reading your code correctly, your pop ordering will be different from the push ordering. Suppose we push 1 2 3 4 5 in that order. Your inbox will look like:

5 -> 4 -> 3 -> 2 -> 1

So far so good. But then when we pop for the first time, this is what happens:

ret = 5
outbox = 1 -> 2 -> 3 -> 4

Then the next time we pop:

ret = 1
outbox = 2 -> 3 -> 4

So the full sequence of pops becomes: 5 1 2 3 4 when it should be 5 4 3 2 1. Thus, I don't think you can call this a stack because it doesn't behave like one. Note that this is all with only only thread, so it isn't a multithreading issue.

Furthermore, if additional pushes arrive while there are still items in the outbox, the outbox will be emptied before any new items will be popped. I'm not sure if you intended to do this (because you called your stack "unreliably ordered"). I would think that a stack should always pop the newest item off first, though.
Potential fix

For the first problem, you could simply change the put_on_outbox code from this:

put_on_outbox:
    atomic_thread_fence(memory_order_acquire);

    for (struct linted_node *node = ret->next;;) {
        if (0 == node)
            break;

        struct linted_node *next = node->next;

        node->next = stack->outbox;
        stack->outbox = node;

        node = next;
    }

to this:

put_on_outbox:
    atomic_thread_fence(memory_order_acquire);
    stack->outbox = ret->next;

Note that when arriving at put_on_outbox:, stack->outbox is guaranteed to be NULL and ret is guaranteed to be non-NULL.

StackExchange Code Review Q#112061, answer score: 3