Implementation of a lock-free fixed-sized allocator

This question now has a follow-up:

Implementation of a lock-free fixed-sized allocator - follow-up - with commented code

I've tried implementing a lock-free fixed-size allocator while trying to learn synchronization through atomic variables.

Here are the related classes:

template_utility.h

#ifndef OAG_TEMPLATE_UTLITY_H
#define OAG_TEMPLATE_UTLITY_H
namespace oag
{
    template 
    using Pointer_type = typename C::pointer;

    template 
    using Size_type = typename C::size_type;
}
#endif // !OAG_TEMPLATE_UTLITY_H

Implementation of the lock-free fixed-size allocator with default memory ordering for all atomic operations.

lock_free_memory_chunk.h

```
#ifndef OAG_LOCK_FREE_MEMORY_CHUNK_H
#define OAG_LOCK_FREE_MEMORY_CHUNK_H

#include
#include "template_utility.h"

namespace oag
{
template
class lock_free_memory_chunk
{
public:
using value_type = T;
using pointer = value_type*;
using size_type = SizeT;

private:
using byte = unsigned char;

public:
explicit lock_free_memory_chunk( size_type const );

pointer allocate() noexcept;
void deallocate( pointer ) noexcept;

private:
bool dec_avail_blocks();

private:
static auto constexpr block_sz = sizeof( value_type ) next_alloc_idx_;
std::atomic num_avail_blocks_;
};
}

namespace oag
{
template
lock_free_memory_chunk::lock_free_memory_chunk( size_type const capacity ) :
p_bytes_{ new byte[ sizeof( value_type ) * capacity ] },
next_alloc_idx_{ 0 },
num_avail_blocks_{ capacity }
{
static_assert( sizeof( byte ) == 1, "sizeof(unsigned char) != 1" );

size_type i{ 0 };
for ( byte* p{ p_bytes_ }; i ( p ) = ++i;
}
}

template
inline oag::lock_free_memory_chunk::~lock_free_memory_chunk()
{
delete[] p_bytes_;
}

template
inline oag::Pointer_type>
lock_free_memory_chunk::allocate() noexcept

ABA problem

It looks like your allocator is susceptible to the ABA problem. The allocate() function's compare and exchange is unsafe because the "next" value you are exchanging could be invalid by the time that the exchange happens.

ABA Example

Suppose your free list looks like this:

0 -> 1 -> 2 -> 3

• Thread A enters allocate() and prepares to compare and exchange 0 with 1. But Thread A pauses for an extended period of time.

-
Thread B calls allocate() twice. The free list now looks like this:

2 -> 3

-
Thread B calls deallocate() on item 0. The free list now looks like this:

0 -> 2 -> 3

-
Thread A resumes. It exchanges 0 with 1. Notice item 1 is in use. The free list is now corrupted.

1 -> ?

Deallocate problem

Also I noticed in the deallocate() function that you set the pointers in a bad order:

while ( !next_alloc_idx_.compare_exchange_weak(                             // 2C
        next_alloc_from_p,
        new_next_alloc_idx ) )
    {
    }
    *reinterpret_cast( p ) = next_alloc_from_p;                     // 2D

If you succeed with the compare and exchange, but then pause before you set p to next_alloc_from_p, then your free list is in a bad state. If another thread tries to allocate while this thread is paused before line 2D, it will load an unknown next pointer from p. You need to assign the next pointer before exchanging:

do {
        *reinterpret_cast( p ) = next_alloc_from_p;
    } while ( !next_alloc_idx_.compare_exchange_weak(
            next_alloc_from_p,
            new_next_alloc_idx ) );

StackExchange Code Review Q#105656, answer score: 6