lockfree/test/freelist_test.cpp

//  Copyright (C) 2011 Tim Blechmann
//
//  Distributed under the Boost Software License, Version 1.0. (See
//  accompanying file LICENSE_1_0.txt or copy at
//  http://www.boost.org/LICENSE_1_0.txt)

// enables error checks via dummy::~dtor
#define BOOST_LOCKFREE_FREELIST_INIT_RUNS_DTOR

#include <boost/lockfree/detail/freelist.hpp>
#include <boost/lockfree/queue.hpp>

#include <boost/thread/thread.hpp>

#define BOOST_TEST_MAIN
#ifdef BOOST_LOCKFREE_INCLUDE_TESTS
#    include <boost/test/included/unit_test.hpp>
#else
#    include <boost/test/unit_test.hpp>
#endif

#include <set>

#include "test_helpers.hpp"

using boost::lockfree::detail::atomic;

atomic< bool > test_running( false );

struct dummy
{
    dummy( void )
    {
        if ( test_running.load( boost::lockfree::detail::memory_order_relaxed ) )
            assert( allocated == 0 );
        allocated = 1;
    }

    ~dummy( void )
    {
        if ( test_running.load( boost::lockfree::detail::memory_order_relaxed ) )
            assert( allocated == 1 );
        allocated = 0;
    }

    size_t padding[ 2 ]; // for used for the freelist node
    int    allocated;
};

template < typename freelist_type, bool threadsafe, bool bounded >
void run_test( void )
{
    freelist_type fl( std::allocator< int >(), 8 );

    std::set< dummy* > nodes;

    dummy d;
    if ( bounded )
        test_running.store( true );

    for ( int i = 0; i != 4; ++i ) {
        dummy* allocated = fl.template construct< threadsafe, bounded >();
        BOOST_TEST_REQUIRE( ( nodes.find( allocated ) == nodes.end() ) );
        nodes.insert( allocated );
    }

    for ( dummy* d : nodes )
        fl.template destruct< threadsafe >( d );

    nodes.clear();
    for ( int i = 0; i != 4; ++i )
        nodes.insert( fl.template construct< threadsafe, bounded >() );

    for ( dummy* d : nodes )
        fl.template destruct< threadsafe >( d );

    for ( int i = 0; i != 4; ++i )
        nodes.insert( fl.template construct< threadsafe, bounded >() );

    if ( bounded )
        test_running.store( false );
}

template < bool bounded >
void run_tests( void )
{
    run_test< boost::lockfree::detail::freelist_stack< dummy >, true, bounded >();
    run_test< boost::lockfree::detail::freelist_stack< dummy >, false, bounded >();
    run_test< boost::lockfree::detail::fixed_size_freelist< dummy >, true, bounded >();
}

BOOST_AUTO_TEST_CASE( freelist_tests )
{
    run_tests< false >();
    run_tests< true >();
}

template < typename freelist_type, bool threadsafe >
void oom_test( void )
{
    const bool    bounded = true;
    freelist_type fl( std::allocator< int >(), 8 );

    for ( int i = 0; i != 8; ++i )
        fl.template construct< threadsafe, bounded >();

    dummy* allocated = fl.template construct< threadsafe, bounded >();
    BOOST_TEST_REQUIRE( allocated == (dummy*)NULL );
}

BOOST_AUTO_TEST_CASE( oom_tests )
{
    oom_test< boost::lockfree::detail::freelist_stack< dummy >, true >();
    oom_test< boost::lockfree::detail::freelist_stack< dummy >, false >();
    oom_test< boost::lockfree::detail::fixed_size_freelist< dummy >, true >();
    oom_test< boost::lockfree::detail::fixed_size_freelist< dummy >, false >();
}


template < typename freelist_type, bool bounded >
struct freelist_tester
{
    static const int size         = 128;
    static const int thread_count = 4;
#ifndef BOOST_LOCKFREE_STRESS_TEST
    static const int operations_per_thread = 1000;
#else
    static const int operations_per_thread = 100000;
#endif

    freelist_type                    fl;
    boost::lockfree::queue< dummy* > allocated_nodes;

    atomic< bool >                       running;
    static_hashed_set< dummy*, 1 << 16 > working_set;


    freelist_tester( void ) :
        fl( std::allocator< int >(), size ),
        allocated_nodes( 256 )
    {}

    void run()
    {
        running = true;

        if ( bounded )
            test_running.store( true );
        boost::thread_group alloc_threads;
        boost::thread_group dealloc_threads;

        for ( int i = 0; i != thread_count; ++i )
            dealloc_threads.create_thread( [ this ] {
                deallocate();
            } );

        for ( int i = 0; i != thread_count; ++i )
            alloc_threads.create_thread( [ this ] {
                allocate();
            } );
        alloc_threads.join_all();
        test_running.store( false );
        running = false;
        dealloc_threads.join_all();
    }

    void allocate( void )
    {
        for ( long i = 0; i != operations_per_thread; ++i ) {
            for ( ;; ) {
                dummy* node = fl.template construct< true, bounded >();
                if ( node ) {
                    bool success = working_set.insert( node );
                    (void)success;
                    assert( success );
                    allocated_nodes.push( node );
                    break;
                }
            }
        }
    }

    void deallocate( void )
    {
        for ( ;; ) {
            dummy* node;
            if ( allocated_nodes.pop( node ) ) {
                bool success = working_set.erase( node );
                (void)success;
                assert( success );
                fl.template destruct< true >( node );
            }

            if ( running.load() == false )
                break;

#ifdef __VXWORKS__
            std::this_thread::yield();
#endif
        }

        dummy* node;
        while ( allocated_nodes.pop( node ) ) {
            bool success = working_set.erase( node );
            (void)success;
            assert( success );
            fl.template destruct< true >( node );
        }
    }
};

template < typename Tester >
void run_tester()
{
    std::unique_ptr< Tester > tester( new Tester );
    tester->run();
}


BOOST_AUTO_TEST_CASE( unbounded_freelist_test )
{
    typedef freelist_tester< boost::lockfree::detail::freelist_stack< dummy >, false > test_type;
    run_tester< test_type >();
}


BOOST_AUTO_TEST_CASE( bounded_freelist_test )
{
    typedef freelist_tester< boost::lockfree::detail::freelist_stack< dummy >, true > test_type;
    run_tester< test_type >();
}

BOOST_AUTO_TEST_CASE( fixed_size_freelist_test )
{
    typedef freelist_tester< boost::lockfree::detail::fixed_size_freelist< dummy >, true > test_type;
    run_tester< test_type >();
}