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