cds/details/defs.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_DEFS_H
   4 #define __CDS_DEFS_H
   5
   6 #include <assert.h>
   7 #include <cstdint>
   8 #include <exception>
   9 #include <string>
  10 #include <memory>
  11
  12 #include <cds/version.h>
  13
  14 /** \mainpage CDS: Concurrent Data Structures library
  15
  16    This library is a collection of lock-free and lock-based fine-grained algorithms of data structures
  17    like maps, queues, list etc. The library contains implementation of well-known data structures
  18    and memory reclamation schemas for modern processor architectures.
  19
  20    Supported processor architectures and operating systems (OS) are:
  21       - x86 [32bit] Linux, Windows, FreeBSD, MinGW
  22       - amd64 (x86-64) [64bit] Linux, Windows, FreeBSD, MinGW
  23       - ia64 (itanium) [64bit] Linux, HP-UX 11.23, HP-UX 11.31
  24       - sparc [64bit] Sun Solaris
  25       - Mac OS X amd64
  26
  27    Supported compilers:
  28       - GCC 4.3+ - for the UNIX-like OSes
  29       - Clang 3.0+ - for Linux
  30       - MS Visual C++ 2008 and above - for MS Windows
  31
  32    For each lock-free data structure the \p CDS library presents several implementation based on published papers. For
  33    example, there are several implementations of queue, each of them is divided by memory reclamation
  34    schema used. However, any implementation supports common interface for the type of data structure.
  35
  36    To implement any lock-free data structure, two things are needed:
  37    - atomic operation library conforming with C++11 memory model. The <b>libcds</b> has such feature, see cds::cxx11_atomic namespace for
  38      details and compiler-specific information.
  39    - safe memory reclamation (SMR) or garbage collecting (GC) algorithm. The <b>libcds</b> has an implementation of several
  40      well-known SMR algos, see below.
  41
  42    The main part of lock-free data structs is garbage collecting. The garbage collector (GC) solves the problem of safe
  43    memory reclamation that is one of the main problems for lock-free programming.
  44    The library contains the implementations of several light-weight \ref cds_garbage_collector "memory reclamation schemes":
  45    - M.Michael's Hazard Pointer - see cds::gc::HP for more explanation
  46    - Gidenstam's memory reclamation schema based on Hazard Pointer and reference counting - see cds::gc::HRC
  47    - M.Herlihy and M.Moir's Pass The Buck algorithm - see cds::gc::PTB
  48    - User-space Read-Copy Update (RCU) - see cds::urcu namespace
  49    - there is cds::gc::nogc "GC" for containers that do not support item reclamation.
  50
  51    Many GC requires a support from the thread. The library does not define the threading model you must use,
  52    it is developed to support various ones; about incorporating <b>cds</b> library to your threading model see cds::threading.
  53
  54    The main namespace for the library is \ref cds.
  55    To see the full list of container's class go to <a href="modules.html">modules</a> tab.
  56
  57    \par How to build
  58
  59    The <b>cds</b> is mostly header-only library. Only small part of library related to GC core functionality
  60    must be compiled. The test projects depends on the following static library from \p boost:
  61    - <tt>boost_thread</tt>
  62    - <tt>boost_date_time</tt>
  63
  64    \par Windows build
  65
  66    Prerequisites: for building <b>cds</b> library and test suite you need:
  67     - <a href="http://www.activestate.com/activeperl/downloads">perl</a> installed; \p PATH environment variable
  68         should contain full path to Perl binary. Perl is used to generate large dictionary for testing purpose;
  69     - <a href="http://www.boost.org/">boost library</a> 1.51 and above. You should create environment variable
  70         \p BOOST_PATH containing full path to \p boost root directory (for example, <tt>C:\\libs\\boost_1_47_0</tt>).
  71
  72    Open solution file <tt>cds\projects\vcX\cds.sln</tt> where vcX - version of
  73    Microsoft Visual C++ you use: vc9 for MS VC 2008, vc10 for MS VC 2010 and so on. The solution
  74    contains <tt>cds</tt> project and several test projects. Just build the library using solution.
  75
  76    <b>Warning</b>: the solution depends on \p BOOST_PATH environment variable that specifies full path
  77    to \p boost library root directory. The test projects search \p boost libraries in:
  78    - for 32bit: \$(BOOST_PATH)/stage/lib, \$(BOOST_PATH)/stage32/lib, and \$(BOOST_PATH)/bin.
  79    - for 64bit: \$(BOOST_PATH)/stage64/lib and \$(BOOST_PATH)/bin.
  80
  81    \par *NIX build
  82
  83    For Unix-like systems GCC and Clang compilers are supported.
  84    Use GCC 4.3 (or above) compiler or Clang 3.0 or above to build <b>cds</b> library. The distributive contains
  85    makefile and <tt>build.sh</tt> script in <tt>build</tt> directory.
  86    The <tt>build/sample</tt> directory contains sample scripts for different operating systems and
  87    processor architectures.
  88    The <tt>build.sh</tt> script supports the following options:
  89    - <tt>-c toolset</tt> - Toolset name, possible values: <tt>gcc</tt> (default), <tt>clang</tt>
  90    - <tt>-x compiler</tt> - C++ compiler name (e.g. g++, g++-4.5 and so on)
  91    - <tt>-p arch</tt> - processor architecture; possible values for arch are: x86, amd64 (x86_64), sparc, ia64
  92    - <tt>-o OStype</tt> - OS family; possible values for OStype are: linux, sunos (solaris), hpux
  93    - <tt>-D define</tt> additional defines
  94    - <tt>-b bits</tt> - bits to build, accepts '64', '32'
  95    - <tt>-l "options"</tt> - extra linker options (in quotes)
  96    - <tt>-z "options"</tt> - extra compiler options (in quotes)
  97    - <tt>--with-boost path</tt> - path to boost include
  98    - <tt>--debug-cxx-options "options"</tt> - extra compiler options for debug target
  99    - <tt>--debug-ld-options "options"</tt> - extra linker options for debug target
 100    - <tt>--release-cxx-options "options"</tt> - extra compiler options for release target
 101    - <tt>--release-ld-options "optons"</tt> - extra linker options for release target
 102    - <tt>--clean</tt> - clean all before building
 103    - <tt>--debug-test</tt> - make unit test in debug mode; by defalt release unit test generated
 104    - <tt>--amd64-use-128bit</tt> - compile with supporting 128bit (16byte) CAS on amd64 (for am64 only)
 105
 106     <b>Important for GCC compiler</b>: all your projects that use <b>libcds</b> must be compiled with <b>-fno-strict-aliasing</b>
 107     compiler flag. Also, the compiler option <tt>-std=c++0x</tt> is very useful.
 108
 109    \anchor cds_how_to_use
 110    \par How to use
 111
 112    To use \p cds lock-free containers based on garbage collectors (GC) provided by library
 113    your application must be linked with \p libcds.
 114
 115    The main part of lock-free programming is garbage collecting for safe memory reclamation.
 116    The library provides several types of GC schemes. One of widely used and well-tested one is Hazard Pointer
 117    memory reclamation schema discovered by M. Micheal and implemented in the library as cds::gc::HP class.
 118    Usually, the application is based on only one type of GC.
 119
 120    In the next example we mean that your application uses Hazard Pointer (cds::gc::HP) - based containers.
 121    Other GCs (cds::gc::HRC, cds::gc::PTB) are applied analogously.
 122
 123     First, in your code you should initialize \p cds library and a garbage collector in \p main function:
 124     \code
 125     #include <cds/init.h>       // for cds::Initialize and cds::Terminate
 126     #include <cds/gc/hp.h>      // for cds::HP (Hazard Pointer) garbage collector
 127
 128     int main(int argc, char** argv)
 129     {
 130         // Initialize libcds
 131         cds::Initialize();
 132
 133         {
 134             // Initialize Hazard Pointer singleton
 135             cds::gc::HP hpGC;
 136
 137             // If main thread uses lock-free containers
 138             // the main thread should be attached to libcds infrastructure
 139             cds::threading::Manager::attachThread();
 140
 141             // Now you can use HP-based containers in the main thread
 142             //...
 143         }
 144
 145         // Terminate libcds
 146         cds::Terminate();
 147     }
 148     \endcode
 149
 150     Second, any of your thread should be attached to \p cds infrastructure.
 151     \code
 152     #include <cds/gc/hp.h>
 153
 154     int myThreadEntryPoint(void *)
 155     {
 156         // Attach the thread to libcds infrastructure
 157         cds::threading::Manager::attachThread();
 158
 159         // Now you can use HP-based containers in the thread
 160         //...
 161
 162         // Detach thread when terminating
 163         cds::threading::Manager::detachThread();
 164     }
 165     \endcode
 166
 167     After that, you can use \p cds lock-free containers safely without any external synchronization.
 168
 169     In some cases, you should work in an external thread. For example, your application
 170     is a plug-in for a server that calls your code in a thread that has been created by the server.
 171     In this case, you should use persistent mode of garbage collecting. In this mode, the thread attaches
 172     to the GC singleton only if it is not attached yet and never call detaching:
 173     \code
 174     #include <cds/gc/hp.h>
 175
 176     int plugin_entry_point()
 177     {
 178         // Attach the thread if it is not attached yet
 179         if ( !cds::threading::Manager::isThreadAttached() )
 180             cds::threading::Manager::attachThread();
 181
 182         // Do some work with HP-related containers
 183         ...
 184     }
 185     \endcode
 186
 187 */
 188
 189
 190 /// The main library namespace
 191 namespace cds {}
 192
 193 /*
 194     \brief Basic typedefs and defines
 195
 196     You do not need include this header directly. All library header files depends on defs.h and include it.
 197
 198     Defines macros:
 199
 200     CDS_COMPILER        Compiler:
 201                     - CDS_COMPILER_MSVC     Microsoft Visual C++
 202                     - CDS_COMPILER_GCC      GNU C++
 203                     - CDS_COMPILER_CLANG    clang
 204                     - CDS_COMPILER_UNKNOWN  unknown compiler
 205
 206     CDS_COMPILER__NAME    Character compiler name
 207
 208     CDS_COMPILER_VERSION    Compliler version (number)
 209
 210     CDS_BUILD_BITS    Resulting binary code:
 211                     - 32        32bit
 212                     - 64        64bit
 213                     - -1        undefined
 214
 215     CDS_POW2_BITS    CDS_BUILD_BITS == 2**CDS_POW2_BITS
 216
 217     CDS_PROCESSOR_ARCH    The processor architecture:
 218                     - CDS_PROCESSOR_X86     Intel x86 (32bit)
 219                     - CDS_PROCESSOR_AMD64   Amd64, Intel x86-64 (64bit)
 220                     - CDS_PROCESSOR_IA64    Intel IA64 (Itanium)
 221                     - CDS_PROCESSOR_SPARC   Sparc
 222                     - CDS_PROCESSOR_PPC64   PowerPC64
 223                     - CDS_PROCESSOR_ARM7    ARM v7
 224                     - CDS_PROCESSOR_UNKNOWN undefined processor architecture
 225
 226     CDS_PROCESSOR__NAME    The name (string) of processor architecture
 227
 228     CDS_OS_TYPE        Operating system type:
 229                     - CDS_OS_UNKNOWN        unknown OS
 230                     - CDS_OS_PTHREAD        unknown OS with pthread
 231                     - CDS_OS_WIN32          Windows 32bit
 232                     - CDS_OS_WIN64          Windows 64bit
 233                     - CDS_OS_LINUX          Linux
 234                     - CDS_OS_SUN_SOLARIS    Sun Solaris
 235                     - CDS_OS_HPUX           HP-UX
 236                     - CDS_OS_AIX            IBM AIX
 237                     - CDS_OS_BSD            FreeBSD, OpenBSD, NetBSD - common flag
 238                     - CDS_OS_FREE_BSD       FreeBSD
 239                     - CDS_OS_OPEN_BSD       OpenBSD
 240                     - CSD_OS_NET_BSD        NetBSD
 241                     - CDS_OS_MINGW          MinGW
 242                     - CDS_OS_OSX            Apple OS X
 243
 244     CDS_OS__NAME        The name (string) of operating system type
 245
 246     CDS_OS_INTERFACE OS interface:
 247                     - CDS_OSI_UNIX             Unix (POSIX)
 248                     - CDS_OSI_WINDOWS          Windows
 249
 250
 251     CDS_BUILD_TYPE    Build type: 'RELEASE' or 'DEBUG' string
 252
 253 */
 254
 255 #if defined(_DEBUG) || !defined(NDEBUG)
 256 #    define    CDS_DEBUG
 257 #    define    CDS_BUILD_TYPE    "DEBUG"
 258 #else
 259 #    define    CDS_BUILD_TYPE    "RELEASE"
 260 #endif
 261
 262 /// Unused function argument
 263 #define CDS_UNUSED(x)   (void)(x)
 264
 265 // Supported compilers:
 266 #define CDS_COMPILER_MSVC        1
 267 #define CDS_COMPILER_GCC         2
 268 #define CDS_COMPILER_INTEL       3
 269 #define CDS_COMPILER_CLANG       4
 270 #define CDS_COMPILER_UNKNOWN    -1
 271
 272 // Supported processor architectures:
 273 #define CDS_PROCESSOR_X86       1
 274 #define CDS_PROCESSOR_IA64      2
 275 #define CDS_PROCESSOR_SPARC     3
 276 #define CDS_PROCESSOR_AMD64     4
 277 #define CDS_PROCESSOR_PPC64     5   // PowerPC 64bit
 278 #define CDS_PROCESSOR_ARM7      7
 279 #define CDS_PROCESSOR_UNKNOWN   -1
 280
 281 // Supported OS interfaces
 282 #define CDS_OSI_UNKNOWN          0
 283 #define CDS_OSI_UNIX             1
 284 #define CDS_OSI_WINDOWS          2
 285
 286 // Supported operating systems (value of CDS_OS_TYPE):
 287 #define CDS_OS_UNKNOWN          -1
 288 #define CDS_OS_WIN32            1
 289 #define CDS_OS_WIN64            5
 290 #define CDS_OS_LINUX            10
 291 #define CDS_OS_SUN_SOLARIS      20
 292 #define CDS_OS_HPUX             30
 293 #define CDS_OS_AIX              50  // IBM AIX
 294 #define CDS_OS_FREE_BSD         61
 295 #define CDS_OS_OPEN_BSD         62
 296 #define CDS_OS_NET_BSD          63
 297 #define CDS_OS_MINGW            70
 298 #define CDS_OS_OSX              80
 299 #define CDS_OS_PTHREAD          100
 300
 301 #if defined(_MSC_VER)
 302 #   if defined(__ICL) || defined(__INTEL_COMPILER)
 303 #       define CDS_COMPILER CDS_COMPILER_INTEL
 304 #   else
 305 #       define CDS_COMPILER CDS_COMPILER_MSVC
 306 #   endif
 307 #elif defined(__clang__)    // Clang checking must be before GCC since Clang defines __GCC__ too
 308 #   define CDS_COMPILER CDS_COMPILER_CLANG
 309 #elif defined( __GCC__ ) || defined(__GNUC__)
 310 #   if defined(__ICL) || defined(__INTEL_COMPILER)
 311 #       define CDS_COMPILER CDS_COMPILER_INTEL
 312 #   else
 313 #       define CDS_COMPILER CDS_COMPILER_GCC
 314 #   endif
 315 #else
 316 #    define CDS_COMPILER CDS_COMPILER_UNKNOWN
 317 #endif  // Compiler choice
 318
 319
 320 // CDS_VERIFY: Debug - assert(_expr); Release - _expr
 321 #ifdef CDS_DEBUG
 322 #   define CDS_VERIFY( _expr )    assert( _expr )
 323 #   define CDS_DEBUG_DO( _expr )        _expr
 324 #else
 325 #   define CDS_VERIFY( _expr )    _expr
 326 #   define CDS_DEBUG_DO( _expr )
 327 #endif
 328
 329 #ifdef CDS_STRICT
 330 #   define CDS_STRICT_DO(_expr)         _expr
 331 #else
 332 #   define CDS_STRICT_DO( _expr )
 333 #endif
 334
 335
 336 // Compiler-specific defines
 337 #include <cds/compiler/defs.h>
 338 // New C++11 features
 339 #include <cds/details/cxx11_features.h>
 340
 341 #define CDS_NOEXCEPT            CDS_NOEXCEPT_SUPPORT
 342 #define CDS_NOEXCEPT_( expr )   CDS_NOEXCEPT_SUPPORT_( expr )
 343 #ifndef CDS_NOEXCEPT_DEFAULTED
 344     // Some compilers do not allow noexcept specification in defaulted function
 345     // For example, GCC 4.6.x raise following error:
 346     //  void foo() noexcept = default
 347     //  error: function \91foo\92 defaulted on its first declaration must not have an exception-specification
 348     // For such compiler empty CDS_NOEXCEPT_DEFAULTED must be defined
 349 #   define CDS_NOEXCEPT_DEFAULTED         CDS_NOEXCEPT
 350 #   define CDS_NOEXCEPT_DEFAULTED_(expr)  CDS_NOEXCEPT_( expr )
 351 #endif
 352
 353 #if defined(CDS_MOVE_SEMANTICS_SUPPORT)
 354 #   define CDS_EMPLACE_SUPPORT
 355 #endif
 356
 357 #ifdef CDS_CXX11_INLINE_NAMESPACE_SUPPORT
 358 #   define CDS_CXX11_INLINE_NAMESPACE   inline
 359 #else
 360 #   define CDS_CXX11_INLINE_NAMESPACE
 361 #endif
 362
 363 //@cond
 364 // typedefs for back compatibility
 365 namespace cds {
 366     /// Atomic pointer
 367     typedef void *            pointer_t;
 368
 369     /// 64bit unaligned int
 370     typedef int64_t     atomic64_unaligned;
 371
 372     /// 64bit unaligned unsigned int
 373     typedef uint64_t  atomic64u_unaligned;
 374
 375     /// 64bit aligned int
 376     typedef atomic64_unaligned CDS_TYPE_ALIGNMENT(8)    atomic64_aligned;
 377
 378     /// 64bit aligned unsigned int
 379     typedef atomic64u_unaligned CDS_TYPE_ALIGNMENT(8)   atomic64u_aligned;
 380
 381     /// 64bit atomic int (aligned)
 382     typedef atomic64_aligned    atomic64_t;
 383
 384     /// 64bit atomic unsigned int (aligned)
 385     typedef atomic64u_aligned   atomic64u_t;
 386
 387     /// 32bit atomic int
 388     typedef int32_t     atomic32_t;
 389
 390     /// 32bit atomic unsigned int
 391     typedef uint32_t    atomic32u_t;
 392
 393     /// atomic int
 394     typedef atomic32_t          atomic_t;
 395
 396     /// atomic unsigned int
 397     typedef atomic32u_t         unsigned_atomic_t;
 398
 399     /// atomic int sized as pointer
 400     typedef intptr_t ptr_atomic_t;
 401
 402     /// atomic unsigned int sized as pointer
 403     typedef uintptr_t uptr_atomic_t;
 404 } // namespace cds
 405 //@endcond
 406
 407 /*************************************************************************
 408  Common things
 409 **************************************************************************/
 410
 411 #include <cds/details/numtraits.h>
 412
 413 namespace cds {
 414
 415     /// Base of all exceptions in the library
 416     class Exception: public std::exception
 417     {
 418     protected:
 419         std::string    m_strMsg    ;    ///< Exception message
 420     public:
 421         /// Create empty exception
 422         Exception()
 423         {}
 424         /// Create exception with message
 425         explicit Exception( const char * pszMsg )
 426             : m_strMsg( pszMsg )
 427         {}
 428         /// Create exception with message
 429         explicit Exception( const std::string& strMsg )
 430             :m_strMsg( strMsg )
 431         {}
 432
 433         /// Destructor
 434         virtual ~Exception() throw()
 435         {}
 436
 437         /// Return exception message
 438         virtual const char * what( ) const throw()
 439         {
 440             return m_strMsg.c_str();
 441         }
 442     };
 443
 444 //@cond
 445 #   define CDS_PURE_VIRTUAL_FUNCTION_CALLED    { assert(false); throw Exception("Pure virtual function called"); }
 446 #   define CDS_PURE_VIRTUAL_FUNCTION_CALLED_(method_name)    { assert(false); throw Exception("Pure virtual function called " method_name ); }
 447 //@endcond
 448
 449     /// any_type is used as a placeholder for auto-calculated type (usually in \p rebind templates)
 450     struct any_type {};
 451
 452     /** \def CDS_DECLARE_EXCEPTION( _class, _msg )
 453         Simplifying declaration of specific exception (usual within classes)
 454         - @p _class - the class name of exception
 455         - @p _msg - exception message (const char *)
 456     */
 457 #define CDS_DECLARE_EXCEPTION( _class, _msg )       \
 458     struct _class: public std::exception {          \
 459     public:                                         \
 460     _class(): std::exception() {}                   \
 461     virtual const char * what( ) const throw() { return _msg; } \
 462     }
 463
 464 } // namespace cds
 465
 466
 467 //@cond
 468 #ifdef _DEBUG
 469 #   define cds_assert(X)    assert(X)
 470 #else
 471 #   include <stdio.h>   // snprintf
 472     static inline void cds_assert_( bool bCond, char const * pszMsg, char const * pszFile, int nLine )
 473     {
 474         if ( !bCond ) {
 475             char buf[4096];
 476 #   if CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL
 477             _snprintf_s( buf, sizeof(buf)/sizeof(buf[0]), _TRUNCATE, pszMsg, pszFile, nLine );
 478 #   else
 479             snprintf( buf, sizeof(buf)/sizeof(buf[0]), pszMsg, pszFile, nLine );
 480 #   endif
 481             throw cds::Exception( buf );
 482         }
 483     }
 484 #   define cds_assert(X)    cds_assert_( X, "%s (%d): Assert failed: " #X, __FILE__, __LINE__ );
 485 #endif
 486 //@endcond
 487
 488 #endif // #ifndef __CDS_DEFS_H