atomic_queue - thread-safe and lock-free implementation of the FIFO data structure pattern

please review my implementation of a FIFO data structure that guarantees thread-safe access without locking.

I removed the license header block and all Doxygen comments. The original version (along with some tests) is available from here:
https://github.com/fat-lobyte/atomic_queue

It should compile with

• Clang >= 3.1, with -stdlib=libc++

• GCC => 4.7, with -D_GLIBCXX_USE_SCHED_YIELD

• Visual Studio >= 2012 (_MSC_VER >= 1700), without emplace_back() member function

I would ask you to check if

• It actually is thread safe (this is the main concern)

• It is compliant with the C++11 standard

• It performs reasonably and no resources are wasted

• If its possible to implement it more simple without losing performance or flexibility

Additionally, if someone is a real pro in lock-free programming, they can help me answer the following question: Can I relax some of the load/store/exchange operations memory ordering constraints (pass an std::memory_order constant)?
I do not understand the memory model properly, and quite frankly I find it is a really difficult to grasp.

Help would be very appreciated. Thanks in advance!

```
#ifndef ATOMIC_QUEUE_HPP_INCLUDED
#define ATOMIC_QUEUE_HPP_INCLUDED

#include
#include
#include
#include

// At the time of writing, MSVC didn't know noexcept
#if defined(_MSC_VER) && _MSC_VER
struct node
{
T t /*> next / >
class atomic_queue_base
{
public:

atomic_queue_base(const Allocator& alc = Allocator()) noexcept
: size_(0u), front_(nullptr), back_(nullptr),
alc_(alc)
{ }

~atomic_queue_base() noexcept
{
node* fr = front_;

while(fr)
{
node* next = fr->next;
NodeAllocatorTraits::destroy(alc_, fr);
NodeAllocatorTraits::deallocate(alc_, fr, 1);
fr = next;
}

}

void push_back(const T& t)
{
auto new_node = NodeAllocatorTraits::allocate(alc_, 1);

try {
ValueAllocator alc(alc_)

Pretty sure this is broken in multi-threaded code:

do
    {
        // Point A.
        if (!old_front) return nullptr;
        new_front = old_front->next;  
    }
    while(!front_.compare_exchange_weak(old_front, new_front));

What happens if:

• Thread A. Reaches point A

• Thread A is de-scheduled and is not currently running.

• Thread B. runs through the above code and works

• Thread B. destroyes the node it poped off the front.

• Thread A. Is re-scheduled to run.

• Thread A. Any use of old_front is invalid as it points at a node that was deleted by Thread B

• Thread A. Even if the node was not destroyed it is no longer the head of the list.

Thus any usage of next is suspect.

StackExchange Code Review Q#15768, answer score: 4