khizmax/libcds

A C++ library of Concurrent Data Structures

!!! STOP WAR !!!

CDS C++ library

The Concurrent Data Structures (CDS) library is a collection of concurrent containers that don't require external (manual) synchronization for shared access, and safe memory reclamation (SMR) algorithms like Hazard Pointer and user-space RCU that is used as an epoch-based SMR.

CDS is mostly header-only template library. Only SMR core implementation is segregated to .so/.dll file.

The library contains the implementations of the following containers:

• lock-free stack with optional elimination support
• several algo for lock-free queue, including classic Michael & Scott algorithm and its derivatives, the flat combining queue, the segmented queue.
• several implementation of unordered set/map - lock-free and fine-grained lock-based
• flat-combining technique
• lock-free skip-list
• lock-free FeldmanHashMap/Set Multi-Level Array Hash with thread-safe bidirectional iterator support
• Bronson's et al algorithm for fine-grained lock-based AVL tree

Generally, each container has an intrusive and non-intrusive (STL-like) version belonging to cds::intrusive and cds::container namespace respectively.

Version 2.x of the library is written on C++11 and can be compiled by GCC 4.8+, clang 3.6+, Intel C++ 15+, and MS VC++ 14 (2015) and above

Download the latest release from http://sourceforge.net/projects/libcds/files/

See online doxygen-generated doc here: http://libcds.sourceforge.net/doc/cds-api/index.html

How to build

• *nix: use CMake
• Windows: use MS Visual C++ 2017 project

Some parts of libcds may depend on DCAS (double-width compare-and-swap) atomic primitive if the target architecture supports it. For x86, cmake build script enables -mcx16 compiler flag that switches DCAS support on. You may manually disable DCAS support with the following command line flags in GCC/clang (for MS VC++ compiler DCAS is not supported):

• -DCDS_DISABLE_128BIT_ATOMIC - for 64bit build
• -DCDS_DISABLE_64BIT_ATOMIC - for 32bit build

All your projects AND libcds MUST be compiled with the same flags - either with DCAS support or without it.

**Building libcds -use vcpkg

You can download and install libcds using the vcpkg dependency manager:

git clone https://github.com/Microsoft/vcpkg.git
cd vcpkg
./bootstrap-vcpkg.sh
./vcpkg integrate install
vcpkg install libcds

The libcds port in vcpkg is kept up to date by Microsoft team members and community contributors. If the version is out of date, please create an issue or pull request on the vcpkg repository.

Pull request requirements

• Pull-request to master branch will be unconditionally rejected
• integration branch is intended for pull-request. Usually, integration branch is the same as master
• dev branch is intended for main developing. Usually, it contains unstable code

References

Stack

• TreiberStack: [1986] R. K. Treiber. Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center, April 1986.
• Elimination back-off implementation is based on idea from [2004] Danny Hendler, Nir Shavit, Lena Yerushalmi "A Scalable Lock-free Stack Algorithm" pdf
• FCStack - flat-combining wrapper for std::stack

Queue

• BasketQueue: [2007] Moshe Hoffman, Ori Shalev, Nir Shavit "The Baskets Queue" pdf
• MSQueue:
  • [1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms" pdf
  • [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-free objects using atomic reads and writes" pdf
  • [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects" pdf
• RWQueue: [1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms" pdf
• MoirQueue: [2000] Simon Doherty, Lindsay Groves, Victor Luchangco, Mark Moir "Formal Verification of a practical lock-free queue algorithm" pdf
• OptimisticQueue: [2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues" pdf
• SegmentedQueue: [2010] Afek, Korland, Yanovsky "Quasi-Linearizability: relaxed consistency for improved concurrency" pdf
• FCQueue - flat-combining wrapper for std::queue
• VyukovMPMCCycleQueue Dmitry Vyukov (see http://www.1024cores.net)

Deque

• flat-combining deque based on stl::deque

Map, set

• MichaelHashMap: [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets" pdf
• SplitOrderedList: [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables" pdf
• StripedMap, StripedSet: [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
• CuckooMap, CuckooSet: [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
• SkipListMap, SkipListSet: [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
• FeldmanHashMap, FeldmanHashSet: [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays: Wait-free Extensible Hash Maps". Supports thread-safe bidirectional iterators pdf

Ordered single-linked list

• LazyList: [2005] Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit "A Lazy Concurrent List-Based Set Algorithm" pdf
• MichaelList: [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets" pdf

Priority queue

• MSPriorityQueue: [1996] G.Hunt, M.Michael, S. Parthasarathy, M.Scott "An efficient algorithm for concurrent priority queue heaps" pdf

Tree

• EllenBinTree: [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree" pdf
• BronsonAVLTreeMap - lock-based fine-grained AVL-tree implementation: [2010] Nathan Bronson, Jared Casper, Hassan Chafi, Kunle Olukotun "A Practical Concurrent Binary Search Tree" pdf

SMR

• Hazard Pointers
  • [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-free objects using atomic reads and writes" pdf
  • [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects" pdf
  • [2004] Andrei Alexandrescu, Maged Michael "Lock-free Data Structures with Hazard Pointers" pdf
• User-space RCU
  • [2009] M.Desnoyers "Low-Impact Operating System Tracing" PhD Thesis, Chapter 6 "User-Level Implementations of Read-Copy Update" pdf
  • [2011] M.Desnoyers, P.McKenney, A.Stern, M.Dagenias, J.Walpole "User-Level Implementations of Read-Copy Update" pdf

Flat Combining technique

• [2010] Hendler, Incze, Shavit and Tzafrir "Flat Combining and the Synchronization-Parallelism Tradeoff" pdf

libcds's Issues

Consider installing CMake Config files

If libcds provided a LibCDSConfig.cmake file with its installation, it would be easier to use it from a CMake-based project.

Remove cds::gc::HRC

Remove cds::gc::HRC SMR, reason:

1. It is complex and unstable GC
2. It is inefficient GC - no performance benefit

Remove all container's specialization for gc::HRC

Mix of allocate and construct in vyukov_queue_pool

In the documentation, it is stated that the pool should be used the following way :

Foo * p = pool_allocator().allocate( 1 );
new(p) Foo;

But when creating the pool, the preallocate_pool function call cxx_allocator().NewArray that does allocate and construct (so if i'm not wrong it calls the constructor ?) and the same goes for vyukov_queue_pool::allocate when the queue is empty when fallbacking to cxx_allocator().New().

Is it by design? Do i miss something ?

(Btw, i also posted it on https://sourceforge.net/p/libcds/bugs/20/ which tracker should be used ? )

Move semantics for cds::urcu::exempt_ptr

urcu::exempt_ptr must be move-constructible and move-assignable.
Copy semantics should not be supported.

Supporting stateful allocators through stateful disposers

Hi,

I'm trying to use LibCDS in a context where I have custom allocators that may contain state. I'm struggling to make this work, and I think the reason is that only stateless disposers are supported. Here's a toy example to express the problem I'm running into:

template <typename T, typename Allocator, typename GC>
class MyList {
    Allocator allocator_;

    struct rcu_disposer {
        void operator()(Node<T>* node) const {
            allocator_.deallocate(node);
        //  ^^^^^^^^^^ Can't have access to the allocator because the
        //             disposer can't be stateful!
        }
    };

public:
    explicit MyList(Allocator const& alloc)
        : allocator_{alloc} // important: the allocator is stateful
    { }

    void erase(int i) {
        Node<T>* removed_node = remove_node_from_list(i);
        GC::template retire_ptr<rcu_disposer>(removed_node);
    }
};

Here, my allocator may contain state. Hence, I want my disposer, who is going to call deallocate(), to hold a reference to that allocator. If I understand correctly, this is impossible to achieve with LibCDS because only the type of the disposer can be passed to retire_ptr, but no instance of that type. Instead, I think being able to do the following would solve my problem:

template <typename T, typename Allocator, typename GC>
class MyList {
    Allocator allocator_;

    struct rcu_disposer {
        Allocator& alloc_;
        void operator()(Node<T>* node) const {
            alloc_.deallocate(node);
        }
    };

public:
    explicit MyList(Allocator const& alloc)
        : allocator_{alloc} // important: the allocator is stateful
    { }

    void erase(int i) {
        Node<T>* removed_node = remove_node_from_list(i);
        rcu_disposer disposer{allocator_};
        GC::template retire_ptr<rcu_disposer>(removed_node, disposer);
    }
};

Hence, I have the following questions:

• Is my use case of stateful allocators supported by LibCDS today, and if so, how can I do it?
• If this is not supported, is there desire to add support for it?

Thanks!

Is ellen_bintree::update_desc needed?

In EllenBinTree implementation we do not use helping.
Analyze whether update_desc is needed in such case.

Skip List Map Usage

In the container cds::container::SkipListMap<cds::gc::nogc, KeyType, ValueType, skip_list_map_traits> skip_list_map_t, is it possible for insert to fail even when the key does not exist ?

I ran a multi-threaded insert workload (4 threads), and it looks like some of the insert operations fail even when the key does not exist (~30%).

Rename cds::gc::PTB to cds::gc::DHP

The current Pass-the-Buck GC (cds::gc::PTB) implementation is not original pass-the-buck algo but it is nearly to Unbounded Hazard Pointer schema.
So, it should be renamed to cds::gc::DHP (dynamic hazard pointer) in all code and tests.

Unification of container declaration

Now, there are two types of container declarations:

1. template <class GC, typename T, typename... Options> class type1;
2. template <class GC, typename T, typename Traits = container_ns::traits > class type2;

The first type of declaration is used mostly for simple containers like stacks and queues. That type of declaration leads to very long mangling names and to giant complicated debugging output.
It is necessary to rewrite type1 declaration to type2 for all libcds containers.

URCU implementation has extra unnecessary locked instructions

The read side of the URCU implementation currently results in locked incl/decl instructions, which is not necessary for correctness.

Per the URCU paper https://www.computer.org/cms/dl/trans/td/2012/02/extras/ttd2012020375s.pdf figure 6, it's sufficient to just have "release" barriers in the case that you are recursively locking, and in all "unlock" cases. Although the code previously used 'fetch_sub' and 'fetch_add' with memory_order_relaxed and memory_order_released, these translated to fully locked atomic instructions.

Fixing the barriers sped up a micro-benchmark (16 threads accessing an RCU-protected split-list set) by 30-40%.

Move *.so link into "devel" package

Accorging to the linux standard *.so should be installed with only "devel" package in order to have a possibility to install multiple versions of library without "devel" package.

P.S. Possible tune install directory on x64 systems from lib to lib64

name space cds::urcu::gc not exist

hi, I want to use the skip_list_set_rcu, but there is no gc files behind the cds/urcu directory. Where can I find it?

Apple clang build issue

Building with

Apple LLVM version 9.0.0 (clang-900.0.38)
Target: x86_64-apple-darwin16.7.0
Thread model: posix
InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin

causes the following:

In file included from libcds/cds/init.h:35:
In file included from libcds/cds/os/topology.h:49:
In file included from libcds/cds/os/osx/topology.h:38:
In file included from libcds/cds/os/details/fake_topology.h:35:
In file included from libcds/cds/threading/model.h:34:
In file included from libcds/cds/threading/details/_common.h:34:
In file included from libcds/cds/urcu/details/gp_decl.h:34:
In file included from libcds/cds/urcu/details/base.h:37:
In file included from libcds/cds/os/thread.h:34:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/thread:97:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/__mutex_base:17:
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/__threading_support:156:1: error: unknown type name 'mach_port_t'
mach_port_t __libcpp_thread_get_port();
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/__threading_support:300:1: error: unknown type name 'mach_port_t'
mach_port_t __libcpp_thread_get_port() {
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/__threading_support:301:12: error: use of undeclared identifier 'pthread_mach_thread_np'
    return pthread_mach_thread_np(pthread_self());```

tests build script fails. CMake usage proposal

And when it fails, it makes no output for libcds.so.
So my proposition is to use CMake instead (can generate Makefile for *NIX and .sln for MS Visual).
I'll make a pull-request within some reasonable time. This file successfully builds libcds and few tests(not all, got no good PC to compile them all at the moment):

cmake_minimum_required (VERSION 2.8.10)
project (libCDS-proj)
set(libCDS_VERSION "2.1.0")

# options:
option(WITH_AMD_USE_128BIT "Use AMD use 128bit (16byte) CAS on amd64" OFF)
option(WITH_TESTS "Build libCDS unit tests" OFF)
option(WITH_BOOST "Set this flag to ON to use non system-wide Boost installation path" OFF)

if(WITH_BOOST)
        set(BOOST_ROOT /usr CACHE PATH "Path to Boost libraries and includes(libboost_system, libbosst_thread)")
        include_directories(BEFORE ${BOOST_ROOT}/include)
        link_directories(BEFORE ${BOOST_ROOT}/include)
endif(WITH_BOOST)

# compiler options and CXX flags:
add_definitions("-D_REENTRANT -D_POSIX_PTHREAD_SEMANTICS -D_FILE_OFFSET_BITS=64")
add_definitions("-DOS_FAMILY=linux ")
set(CMAKE_CXX_FLAGS "-std=c++11 -m64 -fPIC -mtune=native")

set(COMMON_LD_LIBS "-lpthread -ldl -lstdc++")

# libCDS .cpp sources:
include_directories(${CMAKE_SOURCE_DIR})
include_directories(${CMAKE_SOURCE_DIR}/tests/test-hdr/)
include_directories(${CMAKE_SOURCE_DIR}/tests/unit)
file(GLOB CDS_LIB_SRC src/*.cpp)

# link libcds.a
add_library(cds STATIC ${CDS_LIB_SRC})
target_link_libraries(cds ${COMMON_LD_LIBS} -lboost_system -lboost_thread)

# build an link tests(if WITH_TESTS):
if(WITH_TESTS)
        # common library for tests(libcds_test_common):
        include_directories(tests)
        set(CDS_TESTCOMMON_SOURCES
            tests/cppunit/test_main.cpp
            tests/cppunit/thread.cpp
            tests/unit/michael_alloc.cpp
            tests/unit/ellen_bintree_update_desc_pool.cpp)

        add_library(cds_test_common STATIC ${CDS_TESTCOMMON_SOURCES})
        target_link_libraries(cds_test_common cds)

        # lists of tests executable files sources:

        set(CDS_TESTHDR_OFFSETOF_MAP tests/test-hdr/map/hdr_cuckoo_map.cpp)

    file(GLOB CDS_TESTHDR_OFFSETOF_SET tests/test-hdr/set/*.cpp)
    file(GLOB CDS_TESTHDR_OFFSETOF_ORDLIST tests/test-hdr/ordered_list/*.cpp)
    file(GLOB CDS_TESTHDR_OFFSETOF_QUEUE tests/test-hdr/queue/*.cpp)
    file(GLOB CDS_TESTHDR_OFFSETOF_STACK tests/test-hdr/stack/*.cpp)
    file(GLOB CDS_TESTHDR_OFFSETOF_TREE tests/test-hdr/tree/*.cpp)

    file(GLOB CDS_TESTHDR_MAP tests/test-hdr/map/*.cpp tests/test-hdr/map/*.h)

    set(CDS_TESTHDR_DEQUE tests/test-hdr/deque/hdr_fcdeque.cpp)
    file(GLOB CDS_TESTHDR_ORDLIST tests/test-hdr/ordered_list/*.cpp)
    file(GLOB CDS_TESTHDR_PQUEUE  tests/test-hdr/priority_queue/*.cpp)
    file(GLOB CDS_TESTHDR_QUEUE tests/test-hdr/queue/*.cpp)


    file(GLOB CDS_TESTHDR_MISC tests/test-hdr/misc/*.cpp)

    file(GLOB CDSUNIT_SET_SOURCES tests/unit/set2/*.cpp )
    file(GLOB CDSUNIT_QUEUE_SOURCES tests/unit/queue/*.cpp )
    file(GLOB CDSUNIT_STACK_SOURCES tests/unit/stack/*.cpp )
    file(GLOB CDSUNIT_MAP_SOURCES tests/unit/map2/*.cpp )
    file(GLOB CDSUNIT_MISC_SOURCES tests/unit/alloc/*.cpp tests/unit/lock/*.cpp)

    file(GLOB CDSUNIT_PQUEUE_SOURCES tests/unit/pqueue/*.cpp )

    set(CDS_TESTHDR_OFFSETOF_SOURCES 
        ${CDS_TESTHDR_OFFSETOF_QUEUE} 
        ${CDS_TESTHDR_OFFSETOF_STACK} 
        ${CDS_TESTHDR_OFFSETOF_DEQUE} 
        ${CDS_TESTHDR_OFFSETOF_MAP} 
        ${CDS_TESTHDR_OFFSETOF_SET} 
        ${CDS_TESTHDR_OFFSETOF_ORDLIST} 
        ${CDS_TESTHDR_OFFSETOF_TREE})


    set(CDS_TESTHDR_SOURCES 
        ${CDS_TESTHDR_QUEUE} 
        ${CDS_TESTHDR_PQUEUE} 
        ${CDS_TESTHDR_STACK} 
        ${CDS_TESTHDR_MAP} 
        ${CDS_TESTHDR_DEQUE} 
        ${CDS_TESTHDR_ORDLIST} 
        ${CDS_TESTHDR_SET} 
        ${CDS_TESTHDR_TREE} 
        ${CDS_TESTHDR_MISC})

        # build and link tests executables:
    add_executable(test_map     ${CDS_TESTHDR_MAP}) 
    target_link_libraries(test_map cds_test_common cds)

    add_executable(test_off_map     ${CDS_TESTHDR_OFFSETOF_MAP})
    target_link_libraries(test_off_map cds_test_common cds)

    add_executable(test_alloc     ${CDSUNIT_MISC_SOURCES})
    target_link_libraries(test_alloc cds_test_common cds)

endif(WITH_TESTS)

Can't build on Mac OS X

Hello!

Please take look at this:

cd build
bash build.sh 
compiler version=g++ 4.2.1
Building with the following options ...
Processor: x86
Platform: darwin
C Compiler: gcc
C++ Compiler: g++
C++ Compiler version: 4.2.1
Bits to build: 0
Compile options:  -m32 -fPIC -march=native -I 
Link options:  -m32 -fPIC 
Link options (for test cds-unit app):  -m32 -fPIC 
PATH=/opt/local/bin:/opt/local/sbin:/usr/local/bin:/usr/bin:/bin:/usr/sbin:/sbin:/usr/local/go/bin
LD_LIBRARY_PATH=
BIN_PATH=../bin/gcc-x86-darwin-0
OBJ_PATH=../obj/gcc-x86-darwin-0
Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/usr/include/c++/4.2.1
Apple LLVM version 6.0 (clang-600.0.57) (based on LLVM 3.5svn)
Build started
---------------------------------
Make debug library
g++ -std=c++11 -c  -D_DEBUG -O0 -g  -m32 -fPIC -march=native -I  -D_REENTRANT -D_POSIX_PTHREAD_SEMANTICS -D_FILE_OFFSET_BITS=64 -I..  -o ../obj/gcc-x86-darwin-0/debug/hp_gc.o ../src/hp_gc.cpp
g++ -std=c++11 -c  -D_DEBUG -O0 -g  -m32 -fPIC -march=native -I  -D_REENTRANT -D_POSIX_PTHREAD_SEMANTICS -D_FILE_OFFSET_BITS=64 -I..  -o ../obj/gcc-x86-darwin-0/debug/init.o ../src/init.cpp
In file included from ../src/init.cpp:19:
../cds/threading/details/cxx11_manager.h:18:16: error: thread-local storage is unsupported for the current target
        static thread_local ThreadDataPlaceholder CDS_DATA_ALIGNMENT(8) s_threadData;
               ^
../cds/threading/details/cxx11_manager.h:19:16: error: thread-local storage is unsupported for the current target
        static thread_local ThreadData * s_pThreadData;
               ^
../src/init.cpp:43:5: error: thread-local storage is unsupported for the current target
    thread_local threading::cxx11_internal::ThreadDataPlaceholder CDS_DATA_ALIGNMENT(8) threading::cxx11_internal::s_threadData;
    ^
../src/init.cpp:44:5: error: thread-local storage is unsupported for the current target
    thread_local threading::ThreadData * threading::cxx11_internal::s_pThreadData = nullptr;
    ^
4 errors generated.
make: *** [../obj/gcc-x86-darwin-0/debug/init.o] Error 1
```bash

clang:
```bash
clang --version
Apple LLVM version 6.0 (clang-600.0.57) (based on LLVM 3.5svn)
Target: x86_64-apple-darwin14.1.0
Thread model: posix

OS: Mac OS X Yosemite

-mxc16 compiler Flag

Hi,

I found out that it is crucial that the project including libcds is compiled using -mxc16 flag. Otherwise datastructures are compiled with a different size. I propose to add static asserts:

E.g. add cds/gc/dhp.h line 267:
static_assert (sizeof(retired_block) == 16, "Size is not correct");

and document the requirement in the readme.

HP::Guard::Guard

Здравствуйте, подключил вашу билиотеку к проэкту, перевел std::list на IterableList и при тестах получил падение на
cds/cds/gc/impl/hp_impl.h:73
73 : m_guard( hp::get_thread_gc().allocGuard())
как я понимаю идет переполнение количества гуардов на поток. Хотя обращения к итератору листа идет из потока циклически, суть работы примерно такая

обьявление
typedef cds::container::IterableList< cds::gc::HP, Effect*,
typename cds::container::iterable_list::make_traits<
cds::container::opt::compare< ComparatorEffect >
>::type

EffectList;

EffectList modTypes[MAX_TYPE];

использование
uint Object::GetEffectMod(uint type)
{
int sameData = 0;
EffectList const& typeList = modTypes[type];
if (!typeList.empty())
{
for (EffectList::const_iterator iter = typeList.begin(); iter != typeList.end(); ++iter)
sameData += (*iter)->mod;
}
return sameData;
}

вызов GetEffectMod идет из списка обьктов.

Подскажите что я сделал не так и возможны ли варианты переделать.

test-hdr Assertion `m_nTop > 0' failed

assertion happens on linux with both g++ 4.8 and clang 3.5

test-hdr: libcds/cds/gc/details/hp_alloc.h:236: cds::gc::hp::details::hp_allocator<Allocator>::atomic_hazard_ptr& cds::gc::hp::details::hp_allocator<Allocator>::alloc() [with Allocator = std::allocator<int>; cds::gc::hp::details::hp_allocator<Allocator>::atomic_hazard_ptr = cds::gc::hp::details::hp_guard]: Assertion `m_nTop > 0' failed.

It happens during this test

CPPUNIT_TEST(split_dyn_HP_base_cmp)

CMAKE_BUILD_TYPE=DEBUG

with clang, I used libc++. CMAKE_CXX_FLAGS=-stdlib=libc++

OS X clang can't link against library

My steps:

> cmake .
> make

got libcds.dylib in bin/

> file libcds.dylib
libcds.dylib: Mach-O 64-bit dynamically linked shared library x86_64

trying to compile my project that is using

#include "cds/container/michael_list_hp.h"
#include "cds/container/split_list_map.h"

ld fails with the following error:

Undefined symbols for architecture x86_64:
  "cds::gc::dhp::GuardArray<3ul>::GuardArray()", referenced from:
      cds::gc::DHP::GuardArray<3ul>::GuardArray() in main.o
  "cds::gc::dhp::GuardArray<3ul>::~GuardArray()", referenced from:
      cds::gc::DHP::GuardArray<3ul>::~GuardArray() in main.o
  "cds::gc::dhp::Guard::Guard()", referenced from:
      cds::gc::DHP::Guard::Guard() in main.o
  "cds::gc::dhp::Guard::~Guard()", referenced from:
      cds::gc::DHP::Guard::~Guard() in main.o
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)

cds::intrusive::single_link::node - remove base class

Remove base class GC::container_node from cds::intrusive::single_link::node.
Remove GC::contauner_node (GC = HP, DHP) - it is a hangover of gc::HRC

Replace std::random_shuffle with std::shuffle in tests

std::random_shuffle is deprecated in C++11.
http://en.cppreference.com/w/cpp/algorithm/random_shuffle

Conan package

Hello,
Do you know about Conan?
Conan is modern dependency manager for C++. And will be great if your library will be available via package manager for other developers.

Here you can find example, how you can create package for the library.

If you have any questions, just ask :-)

thread_local is not available on Visual Studio 12 2013 Update 4

I've been trying to compile for visual studio 12 2013 with Update 5, and have run into a few errors. Problems with noexcept and constexpr can be worked around with the CDS_XXX macros. thread_local seems to be the remaining compile issue. I'm wondering if a CDS_THREAD_LOCAL could be created which defaults to declspec(thread) on vc120? Are there cases where thread_local is used on non-POD types in libcds?

Support icc/icpc

icc and icpc are the required compilers on several clusters including TACC Stampede, and I've had to make some adjustments every time I've tried to get it to compile.

Basic changes:
cds/cxx11_atomic.h needs to detect that icpc has the atomic header
icpc is missing certain features of the atomic header. This is a shortlist:

• std::atomic_ typedefs
• atomic_memory_fence and similar functions are not in std::

If you think this is a worthy feature I may have time to do it properly the week after next.

assert on exit

Hello, i init and deinit cds on the same thread, i attach my other threads to cds with attach method, by i still get assert on exit here:
CDS_EXPORT_API void smr::help_scan( thread_data* pThis ) { assert( static_cast<thread_record*>( pThis )->m_idOwner.load( atomics::memory_order_relaxed ) == cds::OS::get_current_thread_id() );
in DHP.cpp on line 460 in ~DHP()

I use various moirqueue and stacks on different threads and i make sure to attach to them, why do i get that assert?(i validated that get_current_thread_id() is the same when i init and deinit)

version: latest git build
ide: visual studio 2015

Can't build on FreeBSD 10

Hello, again!

There we have multiple issues with original FreeBSD's make.

bash build.sh -c clang -x clang
compiler version=clang 4.2.1
Building with the following options ...
Processor: amd64
Platform: freebsd
C Compiler: clang
C++ Compiler: clang
C++ Compiler version: 4.2.1
Bits to build: 0
Compile options:  -m64 -fPIC -march=native  -I 
Link options:  -m64 -fPIC 
Link options (for test cds-unit app):  -m64 -fPIC 
PATH=/sbin:/bin:/usr/sbin:/usr/bin:/usr/games:/usr/local/sbin:/usr/local/bin:/root/bin
LD_LIBRARY_PATH=
BIN_PATH=../bin/clang-amd64-freebsd-0
OBJ_PATH=../obj/clang-amd64-freebsd-0
FreeBSD clang version 3.4.1 (tags/RELEASE_34/dot1-final 208032) 20140512
Build started
---------------------------------
Make debug library
make: "/usr/local/src/libcds/build/Makefile" line 14: Missing dependency operator
make: "/usr/local/src/libcds/build/Makefile" line 20: Need an operator
make: "/usr/local/src/libcds/build/Makefile" line 21: Missing dependency operator
make: "/usr/local/src/libcds/build/Makefile" line 24: Need an operator
make: "/usr/local/src/libcds/build/Makefile" line 27: Need an operator
make: "/usr/local/src/libcds/build/Makefile" line 30: Need an operator
make: "../projects/../projects/source.libcds.mk" line 2: Need an operator
make: "../projects/../projects/source.libcds.mk" line 3: Need an operator
make: "../projects/../projects/source.libcds.mk" line 4: Need an operator
make: "../projects/../projects/source.libcds.mk" line 5: Need an operator
make: "../projects/../projects/source.libcds.mk" line 6: Need an operator
make: "../projects/../projects/source.libcds.mk" line 7: Need an operator
make: "../projects/../projects/source.libcds.mk" line 8: Need an operator
make: "../projects/../projects/source.libcds.mk" line 9: Need an operator
make: "../projects/../projects/source.libcds.mk" line 10: Need an operator
make: "../projects/../projects/source.libcds.mk" line 11: Need an operator
make: "/usr/local/src/libcds/build/Makefile" line 49: Missing dependency operator
make: "/usr/local/src/libcds/build/Makefile" line 52: Need an operator
make: "/usr/local/src/libcds/build/Makefile" line 53: Missing dependency operator
make: "/usr/local/src/libcds/build/Makefile" line 56: Need an operator
make: "/usr/local/src/libcds/build/Makefile" line 59: Need an operator
make: "/usr/local/src/libcds/build/Makefile" line 60: Need an operator
make: "/usr/local/src/libcds/build/Makefile" line 65: Missing dependency operator
make: "/usr/local/src/libcds/build/Makefile" line 78: Need an operator
make: "/usr/local/src/libcds/build/Makefile" line 92: Need an operator
make: "/usr/local/src/libcds/build/Makefile" line 175: Missing dependency operator
make: "/usr/local/src/libcds/build/Makefile" line 179: Need an operator
make: "/usr/local/src/libcds/build/Makefile" line 181: warning: duplicate script for target "make_test" ignored
make: "/usr/local/src/libcds/build/Makefile" line 178: warning: using previous script for "make_test" defined here
make: "/usr/local/src/libcds/build/Makefile" line 182: warning: duplicate script for target "make_test" ignored
make: "/usr/local/src/libcds/build/Makefile" line 178: warning: using previous script for "make_test" defined here
make: "/usr/local/src/libcds/build/Makefile" line 183: Need an operator
make: "/usr/local/src/libcds/build/Makefile" line 224: Missing dependency operator
make: "/usr/local/src/libcds/build/Makefile" line 228: Need an operator
make: "/usr/local/src/libcds/build/Makefile" line 230: warning: duplicate script for target "make_debug_test" ignored
make: "/usr/local/src/libcds/build/Makefile" line 227: warning: using previous script for "make_debug_test" defined here
make: "/usr/local/src/libcds/build/Makefile" line 231: warning: duplicate script for target "make_debug_test" ignored
make: "/usr/local/src/libcds/build/Makefile" line 227: warning: using previous script for "make_debug_test" defined here
make: "/usr/local/src/libcds/build/Makefile" line 232: Need an operator
make: Fatal errors encountered -- cannot continue
make: stopped in /usr/local/src/libcds/build

reserved identifier violation

Created by Markus Elfring https://sourceforge.net/p/libcds/bugs/17/
I would like to point out that identifiers like "__CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H" and "__CDS_OPT_ITEM_DISPOSER_H" do not fit to the expected naming convention of the C++ language standard.
Would you like to adjust your selection for unique names?

SplitListMap iterator reliability or alternative

khizmax,

This is an incredible library! Thank-you for your work!

Quick question: are SplitListMap iterators guaranteed despite concurrent erasures?

I've seen that warning in all other maps with iterators, so is this the only one with that capability, or was the warning simply omitted?

If SplitListMap iterators aren't guaranteed, is there an alternative lockfree map with guaranteed iterators?

Most specifically, I'd like avoid early terminations. Imperfect consistency across iteration is irrelevant to my implementation.

most queue implementations don't move the value when popping an element.

See title. Most queue implementations copy the value to the destination, instead of moving it.
See for example https://github.com/khizmax/libcds/blob/dev/cds/container/fcqueue.h#L318:
Instead of *(pRec->pValDeq) = m_Queue.front();
it could be *(pRec->pValDeq) = std::move(m_Queue.front());, since the element is immediately popped anyways. This improves the performance when using element types that implement the move assignment, such as std::function<T>.

Double free error with FCPriority queue

[from http://sourceforge.net/p/libcds/mailman/message/34753436/]

Hello,

I am having an issue with FCPriority queue.

In my code I need to allocate memory for FCPriority queue in a thread in
heap. Then in the destructor, I delete the allocated pointer. The
destructor is called in the main thread. During destructor call of my class
object, I get a double free error. The -fsanitize=address output is given
in [1]. I tested with both 1.6.0 and 2.1 and encountered the same error.

Please advise me how to resolve the issue.

[1] http://pastebin.com/FH7wSTCQ

Thank you
Regards
-Thejaka

FC Deque and iteration interface.

Why all flat combining deque's missing iterate interface?
Like iterate(closure) or begin()/end(), or whatever.

It is understandable why there is no per index/iterator access/insert/ersae.
But why no iteration?

Move semantics for cds::gc::guarded_ptr

gc::guarded_ptr must be move-constructible and move-assignable.
Copy semantics must be prohibited.
That implies the big changes in GC guard code: guards should support the move semantics too.

Segmented Queue: exhausted and populated boolean functions only exist if _DEBUG is defined

Suggested patch below!

diff --git a/cds/intrusive/segmented_queue.h b/cds/intrusive/segmented_queue.h
index fcd4064..83cfb1d 100644
--- a/cds/intrusive/segmented_queue.h
+++ b/cds/intrusive/segmented_queue.h
@@ -374,9 +374,7 @@ namespace cds { namespace intrusive {
                     return guard.assign( &m_List.back() );
                 }

-#       ifdef _DEBUG
                 assert( m_List.empty() || populated( m_List.back() ));
-#       endif 

                 segment * pNew = allocate_segment();
                 m_Stat.onSegmentCreated();
@@ -408,9 +406,7 @@ namespace cds { namespace intrusive {
                         return guard.assign( &m_List.front() );
                     }

-#       ifdef _DEBUG
                     assert( exhausted(m_List.front()) );
-#       endif 

                     m_List.pop_front();
                     if ( m_List.empty() ) {

ABA in Michael's linked list?

I have been playing around with libcds implementation of Michael Maged's linked list. It's likely that I'm doing something wrong but I'm running into erroneous behavior with a simple test written to try to trigger the ABA problem on cds::intrusive::MichaelList.

The test inserts 10 nodes (ordered 0, 1, 2 ... 9) into the list in the main thread, and then runs 2 very simple threads, where thread A erases item 0, thread B erases item 0, erases item 1 and re-inserts item 0 back. These threads are both started and joined.

After joining, around 1-5 out of 1000 times I'm left with an empty list. Much rarer, the list is not empty, but item 2 is not present (and it is possible the list is messed up further).

Expected behavior: the list is not empty; item 1 is not present in the list, item 0 is or is not present depending on run order, items 2-9 are present)

Is there something I'm missing? I tried to check that I'm initializing the library correctly. (BTW, the doxygen could use some code examples involving actual use of the structures - not just setup/initialization)

Platform: x86-64 (Haswell i7-4790 non-K), Linux 4.4, GCC 5.4.0

Source for reproduction (be sure to edit the path in the build script if you want to run it):

#include <cds/init.h>
#include <cds/gc/hp.h>
#include <cds/intrusive/michael_list_hp.h>

#include <cstdio>

struct test_item: public cds::intrusive::michael_list::node< cds::gc::HP >
{
    uint32_t data;
};

struct test_cmp
{
    int operator()( const test_item& a, const test_item& b ) const
    {
        return a.data - b.data;
    }
};

struct test_traits: public cds::intrusive::michael_list::traits
{
    typedef cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > hook;
    typedef test_cmp compare;
};

typedef cds::intrusive::MichaelList< cds::gc::HP, test_item, test_traits > TestList;

int main( int argc, const char *argv[] )
{
    constexpr uint32_t ITER_COUNT = 1000;
    cds::Initialize();
    for( uint32_t j = 0; j < ITER_COUNT; ++j )
    {
        cds::gc::HP hpGC;
        cds::threading::Manager::attachThread();

        constexpr uint32_t ITEM_COUNT = 10;
        // previously used a static array of item values, not pointers - same issue
        test_item* items [ITEM_COUNT];
        for( uint32_t i = 0; i < ITEM_COUNT; ++i )
        {
            items[i] = new test_item;
            // also tried explicitly initializing this
            // items[i]->m_pNext = cds::intrusive::michael_list::node< cds::gc::HP >::marked_ptr();
            items[i]->data = i;
        }

        // items are only read, not written from here on
        {
            TestList list;
            for( uint32_t i = 0; i < ITEM_COUNT; ++i )
            {
                bool inserted = list.insert( *(items[i]) );
                assert( inserted );
            }

            assert( !list.empty() );
            assert( !list.get(*(items[1])).empty() );
            assert( !list.get(*(items[2])).empty() );

            // used check success of erase/insert
            bool e1, e2a, e2b, i2;
            e1 = e2a = e2b = i2 = false;
                
            std::thread t1( [&](){
                cds::threading::Manager::attachThread();
                e1 = list.erase(*(items[0]));
                cds::threading::Manager::detachThread();
            } );
            std::thread t2( [&](){
		cds::threading::Manager::attachThread();
                e2a = list.erase(*(items[0]));
                e2b = list.erase(*(items[1]));
                i2 = list.insert(*(items[0]));
                cds::threading::Manager::detachThread();
            } );
            t1.join();
            t2.join();

            if( list.empty() )
            {
                printf( "ABA: empty list: iteration %u: e1: %d, e2a: %d, e2b: %u, i2: %u\n", j, e1, e2a, e2b, i2 );
            }
            else if( !list.get(*(items[2])) )
            {
                printf( "ABA: missing item 2: iteration %u: e1: %d, e2a: %d, e2b: %u, i2: %u\n", j, e1, e2a, e2b, i2 );
            }

            list.clear();
        }
        cds::threading::Manager::detachThread();
        for( uint32_t i = 0; i < ITEM_COUNT; ++i )
        {
            delete items[i];
        }
    }
    cds::Terminate();
    return 0;
}

Compiled with:

#!/bin/sh
g++ -g -I/PATH/TO/libcds/ -O3 -Wall -Wextra -std=c++14 -o michael_aba michael_aba.cpp /PATH/TO/libcds/build/bin/libcds-s_d.a -lpthread

Wait-free structures

Wait-freedom is the strongest non-blocking guarantee of progress, under which any thread must make progress when given enough CPU steps. Kogan and Petrank in their paper suggested an efficient algorithm of wait-free data structures, with subsequent papers probably suggesting some improvements (I haven't checked all of them yet).
So I suggest to add the implementations of wait free structures to the library

Release/Debug build incompatibility

Hi,
We want to use this library in our project, but we have a problem (concrete signal 11 crashes) when we use libcds release build, and our executable as debug build.
It seams that header-only part is not compatible with compiled part of libcds if NDEBUG is set differently.

At the moment the only solution for us is to patch libcds (concreate to remove #define CDS_DEBUG statement), so that we can work without crashes.

This is also a huge problem for linux distributors because they have to build libcds in both versions, debug and release, and you have to link against first or second dependent on your build profile. This is not usual behaviour. I can for example use boost library provided by my distributor (which is built with release profile), and link them to my project which i have built in debug profile. Of course, it is not possible then to debug in boost library, but usualy you don't want to do that, you want to debug only your code. Executable will work without crashes.

Do you have a better solution for this problem? Is it possible to make CDS_DEBUG definition dependent on a different condition then #if !defined(NDEBUG)? In our Makefiles we do not set NDEBUG for debug build, and this activates CDS_DEBUG macro too, but compiled part of libcds was build without CDS_DEBUG?

Thanks in advance

Intrusive MSQueue: Re-queuing dequeued element results in deadlock

Sample code here will never return despite having just queued a (previously dequeued) node.

using QueueTraits = cds::intrusive::msqueue::make_traits<
    // Use base_hook type (inherit from node)
    cds::intrusive::opt::hook<
        cds::intrusive::msqueue::base_hook<cds::opt::gc<cds::gc::HP>>>,
    // Call 'delete' on node when time to free
    cds::intrusive::opt::disposer<cds::intrusive::opt::v::delete_disposer<>>,
    // Enable item counting in queue (enable .size())
    cds::opt::item_counter<cds::atomicity::item_counter>>::type;

struct MessageQueueNode : public cds::intrusive::msqueue::node<cds::gc::HP>
{
};

using MessageQueue =
    cds::intrusive::MSQueue<cds::gc::HP, MessageQueueNode, QueueTraits>;

MessageQueue testQueue;
MessageQueueNode *onlyNode = new MessageQueueNode;
testQueue.enqueue(*onlyNode);
onlyNode = testQueue.dequeue();
testQueue.enqueue(*onlyNode);
onlyNode = testQueue.dequeue(); // never returns!

Test coverage support

It'll be convenient for continious integration to have a possibility to build the project with gcc code coverage compiler keys

краш на деструкторе

при вызове деструктора класса в котором распологается контейнер типа cds::container::FeldmanHashMap

идёт краш в feldman_hashset_base.h указывающий на это

        static void free_array_node( array_node * parr, size_t nSize )
           {
               cxx_array_node_allocator().Delete( parr, nSize );
           }

при сборке проектна vs13 - всё работает отлично, а вот при сборке на vs 15 - уже получается вот такая вот ошибка

с чем может быть такое связанно?

Is there some benchmark ?

lock-free is not always the best way to solve the problem.
Is there some benchmark between libcds and intel tbb containers?
I think many users are confused on choosing the different kinds of same containers.

test hdr_intrusive_ellen_bintree_hp_member.cpp compile error

In release mode on both clang and g++. swap is requiring a movable type and the basic_node in ellen_bintree contains an atomic member, so it is not generating default move operations.

[90/350] Building CXX object tests/test-hdr/CMakeFiles/test-hdr-offsetof.dir/tree/hdr_intrusive_ellen_bintree_hp_member.cpp.o
FAILED: /usr/bin/clang++    -stdlib=libc++ -std=c++11 -O3 -DNDEBUG -Itests/test-hdr -I/dev/libcds/tests/test-hdr -I/dev/libcds -I/dev/libcds/tests    -Wno-invalid-offsetof -MMD -MT tests/test-hdr/CMakeFiles/test-hdr-offsetof.dir/tree/hdr_intrusive_ellen_bintree_hp_member.cpp.o -MF tests/test-hdr/CMakeFiles/test-hdr-offsetof.dir/tree/hdr_intrusive_ellen_bintree_hp_member.cpp.o.d -o tests/test-hdr/CMakeFiles/test-hdr-offsetof.dir/tree/hdr_intrusive_ellen_bintree_hp_member.cpp.o -c /dev/libcds/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_hp_member.cpp
In file included from /dev/libcds/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_hp_member.cpp:3:
In file included from /dev/libcds/tests/test-hdr/tree/hdr_intrusive_bintree.h:6:
In file included from /dev/libcds/tests/cppunit/cppunit_proxy.h:31:
In file included from /dev/libcds/tests/cppunit/cppunit_mini.h:28:
In file included from /usr/include/c++/v1/sstream:174:
In file included from /usr/include/c++/v1/ostream:131:
In file included from /usr/include/c++/v1/ios:216:
In file included from /usr/include/c++/v1/__locale:15:
In file included from /usr/include/c++/v1/string:439:
/usr/include/c++/v1/algorithm:3127:17: error: no matching function for call to 'swap'
                swap(*__first, *(__first + __i));
                ^~~~
/dev/libcds/tests/cppunit/cppunit_mini.h:201:14: note: in instantiation of function template specialization 'std::__1::shuffle<tree::IntrusiveBinTreeHdrTest::member_hook_value<cds::intrusive::ellen_bintree::node<cds::gc::HP, cds::opt::none> > *, std::__1::mersenne_twister_engine<unsigned long, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253> &>' requested here
        std::shuffle( first, last, m_RandomGen );
             ^
/dev/libcds/tests/test-hdr/tree/hdr_intrusive_bintree.h:264:17: note: in instantiation of function template specialization 'CppUnitMini::TestCase::shuffle<tree::IntrusiveBinTreeHdrTest::member_hook_value<cds::intrusive::ellen_bintree::node<cds::gc::HP, cds::opt::none> > *>' requested here
                shuffle( pFirst, pLast );
                ^
/dev/libcds/tests/test-hdr/tree/hdr_intrusive_bintree.h:793:41: note: in instantiation of member function 'tree::IntrusiveBinTreeHdrTest::data_array<tree::IntrusiveBinTreeHdrTest::member_hook_value<cds::intrusive::ellen_bintree::node<cds::gc::HP, cds::opt::none> > >::data_array' requested here
                data_array< value_type> arr;
                                        ^
/dev/libcds/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_hp_member.cpp:48:9: note: in instantiation of function template specialization 'tree::IntrusiveBinTreeHdrTest::test<cds::intrusive::EllenBinTree<cds::gc::HP, int, tree::IntrusiveBinTreeHdrTest::member_hook_value<cds::intrusive::ellen_bintree::node<cds::gc::HP, cds::opt::none> >, cds::intrusive::opt::disposer<tree::IntrusiveBinTreeHdrTest::disposer<tree::IntrusiveBinTreeHdrTest::member_hook_value<cds::intrusive::ellen_bintree::node<cds::gc::HP, cds::opt::none> > > >::pack<cds::opt::less<tree::IntrusiveBinTreeHdrTest::less<tree::IntrusiveBinTreeHdrTest::member_hook_value<cds::intrusive::ellen_bintree::node<cds::gc::HP, cds::opt::none> > > >::pack<cds::intrusive::ellen_bintree::key_extractor<tree::IntrusiveBinTreeHdrTest::key_extractor<tree::IntrusiveBinTreeHdrTest::member_hook_value<cds::intrusive::ellen_bintree::node<cds::gc::HP, cds::opt::none> > > >::pack<cds::intrusive::opt::hook<cds::intrusive::ellen_bintree::member_hook<8, cds::opt::gc<cds::gc::HP> > >::pack<cds::intrusive::ellen_bintree::traits> > > > >, tree::(anonymous namespace)::print_stat>' requested here
        test<tree_type, print_stat>();
        ^
/usr/include/c++/v1/type_traits:3287:5: note: candidate template ignored: disabled by 'enable_if' [with _Tp = tree::IntrusiveBinTreeHdrTest::member_hook_value<cds::intrusive::ellen_bintree::node<cds::gc::HP, cds::opt::none> >]
    is_move_constructible<_Tp>::value &&
    ^
/usr/include/c++/v1/utility:218:1: note: candidate template ignored: could not match '_Tp [_Np]' against 'tree::IntrusiveBinTreeHdrTest::member_hook_value<cds::intrusive::ellen_bintree::node<cds::gc::HP, cds::opt::none> >'
swap(_Tp (&__a)[_Np], _Tp (&__b)[_Np]) _NOEXCEPT_(__is_nothrow_swappable<_Tp>::value)
^

crash TestIntrusiveStack::Elimination_DHP_member_disposer_relaxed . clang 3.5/libc++

In release mode, this test crashes. In debug mode, it deadlocks. I have attached the call stacks of both.

RELEASE

./test-hdr 
libcds version 2.1.0
Test started 2015-May-12 20:58:34
Using test config file: test.conf
System topology:
    Logical processor count: 8

Use in-place scan strategy for Hazard Pointer memory reclamation algorithm
     Hazard Pointer count: 72
  Max thread count for HP: 100
Retired HP array capacity: 1600

TestIntrusiveStack::Elimination_DHP_member_disposer_relaxed
thread_init_fini::init_fini
        Thread init/fini test,
    thread count=8 pass count=100000...
           Duration=1.13611Segmentation fault (core dumped)


Core was generated by `./test-hdr'.
Program terminated with signal 11, Segmentation fault.
#0  0x00007f4d245f57e0 in boost::detail::thread_data_base::~thread_data_base() () from /usr/lib/x86_64-linux-gnu/libboost_thread.so.1.53.0
(gdb) where
#0  0x00007f4d245f57e0 in boost::detail::thread_data_base::~thread_data_base() () from /usr/lib/x86_64-linux-gnu/libboost_thread.so.1.53.0
#1  0x000000000991fa69 in boost::detail::thread_data<boost::_bi::bind_t<void, void (*)(CppUnitMini::TestThread*), boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> > > >::~thread_data() ()
#2  0x00007f4d245f778e in boost::detail::sp_counted_base::release() () from /usr/lib/x86_64-linux-gnu/libboost_thread.so.1.53.0
#3  0x00000000079ec7dc in boost::thread::~thread() ()
#4  0x00000000079ebf5f in thread_init_fini::Thread::~Thread() ()
#5  0x000000000991ed42 in CppUnitMini::ThreadPool::~ThreadPool() ()
#6  0x00000000079ebd61 in thread_init_fini::init_fini() ()
#7  0x00000000079eb772 in thread_init_fini::myRun(char const*, bool) ()
#8  0x000000000990b228 in CppUnitMini::TestCase::run(CppUnitMini::Reporter*, char const*, bool) ()
#9  0x000000000990d0a9 in main ()
(gdb) thread apply all backtrace

Thread 3 (Thread 0x7f4d228ec700 (LWP 7728)):
#0  pthread_cond_wait@@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
#1  0x00007f4d23f4ebc6 in std::__1::condition_variable::wait(std::__1::unique_lock<std::__1::mutex>&) () from /usr/lib/x86_64-linux-gnu/libc++.so.1
#2  0x000000000990eb4b in cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >::execute() ()
#3  0x000000000990ea9e in void* std::__1::__thread_proxy<std::__1::tuple<void (*)(cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*), cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*> >(void*) ()
#4  0x00007f4d241cff6e in start_thread (arg=0x7f4d228ec700) at pthread_create.c:311
#5  0x00007f4d236f49cd in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:113

Thread 2 (Thread 0x7f4d230ed700 (LWP 7727)):
#0  pthread_cond_wait@@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
#1  0x00007f4d23f4ebc6 in std::__1::condition_variable::wait(std::__1::unique_lock<std::__1::mutex>&) () from /usr/lib/x86_64-linux-gnu/libc++.so.1
#2  0x000000000990eb4b in cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >::execute() ()
#3  0x000000000990ea9e in void* std::__1::__thread_proxy<std::__1::tuple<void (*)(cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*), cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*> >(void*) ()
#4  0x00007f4d241cff6e in start_thread (arg=0x7f4d230ed700) at pthread_create.c:311
#5  0x00007f4d236f49cd in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:113

Thread 1 (Thread 0x7f4d24bf5840 (LWP 7726)):
#0  0x00007f4d245f57e0 in boost::detail::thread_data_base::~thread_data_base() () from /usr/lib/x86_64-linux-gnu/libboost_thread.so.1.53.0
#1  0x000000000991fa69 in boost::detail::thread_data<boost::_bi::bind_t<void, void (*)(CppUnitMini::TestThread*), boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> > > >::~thread_data() ()
#2  0x00007f4d245f778e in boost::detail::sp_counted_base::release() () from /usr/lib/x86_64-linux-gnu/libboost_thread.so.1.53.0
#3  0x00000000079ec7dc in boost::thread::~thread() ()
#4  0x00000000079ebf5f in thread_init_fini::Thread::~Thread() ()
#5  0x000000000991ed42 in CppUnitMini::ThreadPool::~ThreadPool() ()
#6  0x00000000079ebd61 in thread_init_fini::init_fini() ()
#7  0x00000000079eb772 in thread_init_fini::myRun(char const*, bool) ()
#8  0x000000000990b228 in CppUnitMini::TestCase::run(CppUnitMini::Reporter*, char const*, bool) ()
#9  0x000000000990d0a9 in main ()

DEBUG.

clang 3.5 DEBUG build. -stdlib=libc++

bin ❯ ./test-hdr 
libcds version 2.1.0
Test started 2015-May-12 05:33:55
Using test config file: test-debug.conf
System topology:
    Logical processor count: 8

Use in-place scan strategy for Hazard Pointer memory reclamation algorithm
     Hazard Pointer count: 72
  Max thread count for HP: 100
Retired HP array capacity: 1600


TestIntrusiveStack::Elimination_DHP_member_disposer_relaxed
thread_init_fini::init_fini
        Thread init/fini test,
    thread count=4 pass count=100000...

(gdb) info threads
  Id   Target Id         Frame 
  6    Thread 0x7f43aa373700 (LWP 4014) "test-hdr" pthread_cond_wait@@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
  5    Thread 0x7f43a9b72700 (LWP 4015) "test-hdr" pthread_cond_wait@@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
  4    Thread 0x7f43a9371700 (LWP 4016) "test-hdr" pthread_cond_wait@@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
  3    Thread 0x7f43a3fff700 (LWP 4018) "test-hdr" pthread_cond_wait@@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
  2    Thread 0x7f43a37fe700 (LWP 4019) "test-hdr" pthread_cond_wait@@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
* 1    Thread 0x7f43abe97840 (LWP 4013) "test-hdr" pthread_cond_wait@@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185


(gdb) thread apply all backtrace

Thread 6 (Thread 0x7f43aa373700 (LWP 4014)):
#0  pthread_cond_wait@@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
#1  0x00007f43ab1d4bc6 in std::__1::condition_variable::wait(std::__1::unique_lock<std::__1::mutex>&) () from /usr/lib/x86_64-linux-gnu/libc++.so.1
#2  0x0000000017d71e8a in cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >::execute (this=0x3173ebd8)
    at /home/khegeman/dev/libcds/cds/urcu/dispose_thread.h:85
#3  0x0000000017d71475 in cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >::dispose_thread_starter::thread_func (pThis=0x3173ebd8)
    at /home/khegeman/dev/libcds/cds/urcu/dispose_thread.h:38
#4  0x0000000017d71b25 in __invoke<void (*)(cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*), cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*> (__f=<unknown type in /home/khegeman/build/libcds_clangdebuglibc/bin/test-hdr, CU 0x87b9d58, DIE 0x87dddcc>, 
    __args=<unknown type in /home/khegeman/build/libcds_clangdebuglibc/bin/test-hdr, CU 0x87b9d58, DIE 0x87dddd4>) at /usr/include/c++/v1/__functional_base:413
#5  __thread_execute<void (*)(cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*), cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*, 1> (__t=...) at /usr/include/c++/v1/thread:332
#6  std::__1::__thread_proxy<std::__1::tuple<void (*)(cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*), cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*> > (__vp=0x3173d5e0) at /usr/include/c++/v1/thread:342
#7  0x00007f43ab455f6e in start_thread (arg=0x7f43aa373700) at pthread_create.c:311
#8  0x00007f43aa97a9cd in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:113

Thread 5 (Thread 0x7f43a9b72700 (LWP 4015)):
#0  pthread_cond_wait@@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
#1  0x00007f43ab1d4bc6 in std::__1::condition_variable::wait(std::__1::unique_lock<std::__1::mutex>&) () from /usr/lib/x86_64-linux-gnu/libc++.so.1
#2  0x0000000017d71e8a in cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >::execute (this=0x3173f078)
    at /home/khegeman/dev/libcds/cds/urcu/dispose_thread.h:85
#3  0x0000000017d71475 in cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >::dispose_thread_starter::thread_func (pThis=0x3173f078)
    at /home/khegeman/dev/libcds/cds/urcu/dispose_thread.h:38
#4  0x0000000017d71b25 in __invoke<void (*)(cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*), cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*> (__f=<unknown type in /home/khegeman/build/libcds_clangdebuglibc/bin/test-hdr, CU 0x87b9d58, DIE 0x87dddcc>, 
    __args=<unknown type in /home/khegeman/build/libcds_clangdebuglibc/bin/test-hdr, CU 0x87b9d58, DIE 0x87dddd4>) at /usr/include/c++/v1/__functional_base:413
#5  __thread_execute<void (*)(cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*), cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*, 1> (__t=...) at /usr/include/c++/v1/thread:332
#6  std::__1::__thread_proxy<std::__1::tuple<void (*)(cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*), cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*> > (__vp=0x3173f150) at /usr/include/c++/v1/thread:342
#7  0x00007f43ab455f6e in start_thread (arg=0x7f43a9b72700) at pthread_create.c:311
#8  0x00007f43aa97a9cd in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:113

Thread 4 (Thread 0x7f43a9371700 (LWP 4016)):
#0  pthread_cond_wait@@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
#1  0x0000000017da9ce0 in boost::condition_variable::wait (this=0x31780ff8, m=...) at /usr/include/boost/thread/pthread/condition_variable.hpp:73
#2  0x0000000017da634a in boost::barrier::wait (this=0x31780fd0) at /usr/include/boost/thread/barrier.hpp:233
#3  0x0000000017da4b60 in CppUnitMini::ThreadPool::onThreadFiniDone (this=0x7ffff4bc89f0) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:127
#4  0x0000000017da4995 in CppUnitMini::TestThread::run (this=0x3177e410) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:29
#5  0x0000000017da4905 in CppUnitMini::TestThread::threadEntryPoint (pInst=0x3177e410) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:11
#6  0x0000000017da9845 in boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> >::operator()<void (*)(CppUnitMini::TestThread*), boost::_bi::list0> (this=0x317819d8, 
    f=@0x317819d0: 0x17da48f0 <CppUnitMini::TestThread::threadEntryPoint(CppUnitMini::TestThread*)>, a=...) at /usr/include/boost/bind/bind.hpp:253
#7  0x0000000017da97cf in boost::_bi::bind_t<void, void (*)(CppUnitMini::TestThread*), boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> > >::operator() (this=0x317819d0)
    at /usr/include/boost/bind/bind_template.hpp:20
#8  0x0000000017da85cc in boost::detail::thread_data<boost::_bi::bind_t<void, void (*)(CppUnitMini::TestThread*), boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> > > >::run (this=0x31781830)
    at /usr/include/boost/thread/detail/thread.hpp:116
#9  0x00007f43ab87a94a in ?? () from /usr/lib/x86_64-linux-gnu/libboost_thread.so.1.53.0
#10 0x00007f43ab455f6e in start_thread (arg=0x7f43a9371700) at pthread_create.c:311
#11 0x00007f43aa97a9cd in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:113

Thread 3 (Thread 0x7f43a3fff700 (LWP 4018)):
#0  pthread_cond_wait@@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
#1  0x0000000017da9ce0 in boost::condition_variable::wait (this=0x31780ff8, m=...) at /usr/include/boost/thread/pthread/condition_variable.hpp:73
#2  0x0000000017da634a in boost::barrier::wait (this=0x31780fd0) at /usr/include/boost/thread/barrier.hpp:233
#3  0x0000000017da4b60 in CppUnitMini::ThreadPool::onThreadFiniDone (this=0x7ffff4bc89f0) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:127
#4  0x0000000017da4995 in CppUnitMini::TestThread::run (this=0x3177af20) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:29
#5  0x0000000017da4905 in CppUnitMini::TestThread::threadEntryPoint (pInst=0x3177af20) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:11
#6  0x0000000017da9845 in boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> >::operator()<void (*)(CppUnitMini::TestThread*), boost::_bi::list0> (this=0x31783318, 
    f=@0x31783310: 0x17da48f0 <CppUnitMini::TestThread::threadEntryPoint(CppUnitMini::TestThread*)>, a=...) at /usr/include/boost/bind/bind.hpp:253
#7  0x0000000017da97cf in boost::_bi::bind_t<void, void (*)(CppUnitMini::TestThread*), boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> > >::operator() (this=0x31783310)
    at /usr/include/boost/bind/bind_template.hpp:20
#8  0x0000000017da85cc in boost::detail::thread_data<boost::_bi::bind_t<void, void (*)(CppUnitMini::TestThread*), boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> > > >::run (this=0x31783170)
    at /usr/include/boost/thread/detail/thread.hpp:116
#9  0x00007f43ab87a94a in ?? () from /usr/lib/x86_64-linux-gnu/libboost_thread.so.1.53.0
#10 0x00007f43ab455f6e in start_thread (arg=0x7f43a3fff700) at pthread_create.c:311
#11 0x00007f43aa97a9cd in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:113

Thread 2 (Thread 0x7f43a37fe700 (LWP 4019)):
#0  pthread_cond_wait@@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
#1  0x0000000017da9ce0 in boost::condition_variable::wait (this=0x31780ff8, m=...) at /usr/include/boost/thread/pthread/condition_variable.hpp:73
#2  0x0000000017da634a in boost::barrier::wait (this=0x31780fd0) at /usr/include/boost/thread/barrier.hpp:233
#3  0x0000000017da4b60 in CppUnitMini::ThreadPool::onThreadFiniDone (this=0x7ffff4bc89f0) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:127
#4  0x0000000017da4995 in CppUnitMini::TestThread::run (this=0x31781d20) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:29
#5  0x0000000017da4905 in CppUnitMini::TestThread::threadEntryPoint (pInst=0x31781d20) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:11
#6  0x0000000017da9845 in boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> >::operator()<void (*)(CppUnitMini::TestThread*), boost::_bi::list0> (this=0x31769db8, 
    f=@0x31769db0: 0x17da48f0 <CppUnitMini::TestThread::threadEntryPoint(CppUnitMini::TestThread*)>, a=...) at /usr/include/boost/bind/bind.hpp:253
#7  0x0000000017da97cf in boost::_bi::bind_t<void, void (*)(CppUnitMini::TestThread*), boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> > >::operator() (this=0x31769db0)
    at /usr/include/boost/bind/bind_template.hpp:20
#8  0x0000000017da85cc in boost::detail::thread_data<boost::_bi::bind_t<void, void (*)(CppUnitMini::TestThread*), boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> > > >::run (this=0x31769c10)
    at /usr/include/boost/thread/detail/thread.hpp:116
#9  0x00007f43ab87a94a in ?? () from /usr/lib/x86_64-linux-gnu/libboost_thread.so.1.53.0
#10 0x00007f43ab455f6e in start_thread (arg=0x7f43a37fe700) at pthread_create.c:311
#11 0x00007f43aa97a9cd in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:113

Thread 1 (Thread 0x7f43abe97840 (LWP 4013)):
#0  pthread_cond_wait@@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
#1  0x0000000017da9ce0 in boost::condition_variable::wait (this=0x31780ff8, m=...) at /usr/include/boost/thread/pthread/condition_variable.hpp:73
#2  0x0000000017da634a in boost::barrier::wait (this=0x31780fd0) at /usr/include/boost/thread/barrier.hpp:233
#3  0x0000000017da5310 in CppUnitMini::ThreadPool::run (this=0x7ffff4bc89f0) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:82
#4  0x0000000014ef2261 in thread_init_fini::init_fini (this=0x3154e338 <_ZL5local>) at /home/khegeman/dev/libcds/tests/test-hdr/misc/thread_init_fini.cpp:62
#5  0x0000000014ef190a in thread_init_fini::myRun (this=0x3154e338 <_ZL5local>, in_name=0x181b8f10 "", invert=false) at /home/khegeman/dev/libcds/tests/test-hdr/misc/thread_init_fini.cpp:73
#6  0x0000000017d68c99 in CppUnitMini::TestCase::run (in_reporter=0x3173d600, in_testName=0x181b8f10 "", invert=false) at /home/khegeman/dev/libcds/tests/cppunit/test_main.cpp:111
#7  0x0000000017d6b9d1 in main (argc=1, argv=0x7ffff4bc97e8) at /home/khegeman/dev/libcds/tests/cppunit/test_main.cpp:447

split tests/unit/map2/map_delodd.cpp and tests/unit/map2/map_insdelfind.cpp

Compilation of this files with g++ 4.9 with -O3 flag takes over 3 GB of memory on my ubuntu 14.04 notebook 8GB, so if -j 2 option is specified and this files are compiled simultaneously (and it happens quite often) it causes out of memory error in best case, but ussualy it just freezes my pc. It would be very nice to split these files, if possible.

Remove unnecessary null pointer checks

Created by Markus Elfring https://sourceforge.net/p/libcds/bugs/18/

An extra null pointer check is not needed in functions like the following.

• GarbageCollector::Destruct
• ThreadPool

MichaelHashSet item counter causes false sharing

In a multi-threaded workload, I found that the item counter in MichaelHashSet caused a lot of contention in the read path, where the atomic increments of the item count were causing 'HITM' loads for threads that were only performing read operations.

Padding this out seems like an easy win.

Also, it seems overly restrictive to not allow empty_item_counter. If the user of the hashset doesn't care about .empty() and .size() working correctly, the empty item counter should be sufficient.

CDS_ENABLE_HPSTAT

Library fails if i didn't define CDS_ENABLE_HPSTAT.

False sharing between thread-local data records in URCU implementation

I noticed using perf c2c that there was a lot of cacheline bouncing while accessing thread-local records in a URCU-protected workload. This is due to lack of padding causing false sharing when the TSD records get allocated in adjacent memory.

toddlipcon@4b8d5a8 fixes the issue

Unclear statements about iterators

It is probably not a code issue, but I don't understand if container(s) (say, skip list) have iterators which
are used to update value(s) from different threads.

Absent EllenBinTree< cds::gc::nogc > specialization

Should be implemented

BronsonAVLTreeMap Usage

I am having trouble with setting up the BronsonAVLTreeMap. In particular, I observe this assertion failure:

map_test: /home/parallels/git/peloton/third_party/libcds/cds/urcu/details/gp.h:94: static bool cds::urcu::details::gp_thread_gc<GPRCUtag>::is_locked() [with GPRCUtag = cds::urcu::general_buffered_tag]: Assertion `pRec != nullptr' failed.

Relevant code snippets:

// HEADER FILE

#include "libcds/cds/init.h"
#include "libcds/cds/urcu/general_buffered.h"
#include "libcds/cds/sync/pool_monitor.h"
#include "libcds/cds/memory/vyukov_queue_pool.h"
#include "libcds/cds/container/bronson_avltree_map_rcu.h"

  // rcu implementation
  typedef cds::urcu::general_buffered<> RCUImpl;

  // rcu type
  typedef cds::urcu::gc<RCUImpl> RCUType;

  typedef cds::container::BronsonAVLTreeMap<RCUType, KeyType, MappedType> avl_tree_t;

// SOURCE FILE

MAP_TEMPLATE_ARGUMENTS
MAP_TYPE::Map(){

  // Create URCU general_buffered singleton
  RCUImpl::Construct();

}

MAP_TEMPLATE_ARGUMENTS
MAP_TYPE::~Map(){

  // Destroy URCU general_buffered singleton
  RCUImpl::Destruct();

}

// TEST FILE

TEST_F(MapTest, BasicTest) {
  size_t const element_count = 3;

  // Initialize CDS library
  cds::Initialize();

  typedef uint32_t  key_type;
  typedef uint32_t  value_type;
  typedef uint32_t* value_ptr_type;

  {
    // Attach thread
    cds::threading::Manager::attachThread();

    Map<key_type, value_type> map;

    for (size_t element = 0; element < element_count; ++element ) {
      value_ptr_type val = new value_type(element);
      auto status = map.Insert(element, val);
    }

    EXPECT_EQ(map.GetSize(), element_count);

    // Detach thread
    cds::threading::Manager::detachThread();
  }

  // Terminate CDS library
  cds::Terminate();

}

Any pointers would be helpful. Thanks.