Spin locked stack and memory barriers (C++)

Question

I have a implementation spin lock:

class Spinlock {
public:
    void Lock() {
        while (true) {
            if (!_lock.test_and_set(std::memory_order_acquire)) {
                return;
            }
        }
    }

    void Unlock() {
        _lock.clear(std::memory_order_release);
    }

private:
    std::atomic_flag _lock;
};

I use SpinLock class in:

class SpinlockedStack {
public:
    SpinlockedStack() : _head(nullptr) {
    }

    ~SpinlockedStack() {
        while (_head != nullptr) {
            Node* node = _head->Next;
            delete _head;
            _head = node;
        }
    }

    void Push(int value) {
        _lock.Lock();
        _head = new Node(value, _head);
        _lock.Unlock();
    }

    bool TryPop(int& value) {
        _lock.Lock();

        if (_head == nullptr) {
            value = NULL;
            _lock.Unlock();
            return false;
        }

        Node* node = _head;
        value = node->Value;
        _head = node->Next;

        delete node;

        _lock.Unlock();

        return true;
    }

private:
    struct Node {
        int Value;
        Node* Next;

        Node(int value, Node* next) : Value(value), Next(next) {
        }
    };

    Node* _head;
    Spinlock _lock;
};

I understand that i should put memory barriers. I can use atomic variables:

struct Node {
    int Value;
    std::atomic<Node*> Next;

    Node(int value) : Value(value) {
    }
};

std::atomic<Node*> _head;
Spinlock _lock;
...

void Push(int value) {
    _lock.Lock();

    Node* currentHead = _head.load(std::memory_order_acquire);

    Node* newHead = new Node(value);
    newHead->Next.store(currentHead, std::memory_order_relaxed);

    _head.store(newHead, std::memory_order_release);

    _lock.Unlock();
}

bool TryPop(int& value) {
    _lock.Lock();

    Node* currentHead = _head.load(std::memory_order_acquire);

    if (currentHead == nullptr) {
        value = NULL;
        _lock.Unlock();
        return false;
    }

    value = currentHead->Value;
    _head.store(currentHead->Next.load(std::memory_order_relaxed), std::memory_order_release);

    delete currentHead;

    _lock.Unlock();

    return true;
}

I can also use atomic_thread_fence():

struct Node {
    int Value;
    Node* Next;

    Node(int value) : Value(value) {
    }
};

Node* _head;
Spinlock _lock;

...

void Push(int value) {
    _lock.Lock();

    Node* currentHead = _head;

    std::atomic_thread_fence(std::memory_order_acquire);

    Node* newHead = new Node(value);

    newHead->Next = currentHead;

    std::atomic_thread_fence(std::memory_order_release);

    _head = newHead;

    _lock.Unlock();
}

bool TryPop(int& value) {
    _lock.Lock();

    std::atomic_thread_fence(std::memory_order_acquire);

    Node* currentHead = _head;

    if (currentHead == nullptr) {
        value = NULL;
        _lock.Unlock();
        return false;
    }

    value = currentHead->Value;

    std::atomic_thread_fence(std::memory_order_acquire);

    Node* nextNead = currentHead->Next;

    std::atomic_thread_fence(std::memory_order_release);

    _head = nextNead;

    delete currentHead;

    _lock.Unlock();

    return true;
}

My questions:

1. Do I place the memory barriers?
2. What is better to use in this case (atomic variables or atomic_thread_fence) and why?

Answer 1

The acquiring of the lock already establishes the memory guarantees that you need.

When a thread releases the lock it has to write to the atomic flag. This guarantees that when the next thread acquires the lock and sees the write to the flag, that the acquiring thread is guaranteed to see all writes the releasing thread did before writing to the flag.

On a sidenote you should use something like RAII to make sure your lock is released in all circumstances.

Also you have to initialize your lock with ATOMIC_FLAG_INIT otherwise it is on an undefined state.