We’re rewarding the question askers & reputations are being recalculated! Read more.
3 deleted 49 characters in body
source | link

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
  1. Thread A enters allocate() and prepares to compare and exchange 0 with 1. But Thread A pauses for an extended period of time.
  2. Thread B calls allocate() twice. The free list now looks like this:

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

    0 -> 2 -> 3
    
  4. 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<size_type*>( 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 should move line 2D above line 2Cneed to avoid thisassign the next pointer before exchanging:

    *reinterpret_cast<size_type*>( p ) = next_alloc_from_p;         do {
        *reinterpret_cast<size_type*>( p ) //= 2Dnext_alloc_from_p;
    } while ( !next_alloc_idx_.compare_exchange_weak(                   
           // 2Cnext_alloc_from_p,
        next_alloc_from_p,
        new_next_alloc_idx ) )
    {
    };

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
  1. Thread A enters allocate() and prepares to compare and exchange 0 with 1. But Thread A pauses for an extended period of time.
  2. Thread B calls allocate() twice. The free list now looks like this:

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

    0 -> 2 -> 3
    
  4. 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<size_type*>( 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 should move line 2D above line 2C to avoid this:

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

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
  1. Thread A enters allocate() and prepares to compare and exchange 0 with 1. But Thread A pauses for an extended period of time.
  2. Thread B calls allocate() twice. The free list now looks like this:

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

    0 -> 2 -> 3
    
  4. 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<size_type*>( 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<size_type*>( p ) = next_alloc_from_p;
    } while ( !next_alloc_idx_.compare_exchange_weak( 
            next_alloc_from_p,
            new_next_alloc_idx ) );
2 added 1413 characters in body
source | link

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
  1. Thread A enters allocate() and prepares to compare and exchange 0 with 1. But Thread A pauses for an extended period of time.
  2. Thread B calls allocate() twice. The free list now looks like this:

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

    0 -> 2 -> 3
    
  4. 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<size_type*>( 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 should move line 2D above line 2C to avoid this:

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

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 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
  1. Thread A enters allocate() and prepares to compare and exchange 0 with 1. But Thread A pauses for an extended period of time.
  2. Thread B calls allocate() twice. The free list now looks like this:

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

    0 -> 2 -> 3
    
  4. 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<size_type*>( 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 should move line 2D above line 2C to avoid this:

    *reinterpret_cast<size_type*>( p ) = next_alloc_from_p;                     // 2D
    while ( !next_alloc_idx_.compare_exchange_weak(                             // 2C
        next_alloc_from_p,
        new_next_alloc_idx ) )
    {
    }
1
source | link

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.