cds/memory/michael/options.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_MEMORY_MICHAEL_OPTIONS_H
  32 #define CDSLIB_MEMORY_MICHAEL_OPTIONS_H
  33
  34 /*
  35     Options for Michael allocator
  36     Source:
  37         [2004] Maged Michael "Scalable Lock-Free Dynamic Memory Allocation"
  38
  39     Editions:
  40         2011.01.23 khizmax  Created
  41 */
  42
  43 #include <cds/opt/options.h>
  44
  45 namespace cds { namespace memory { namespace michael {
  46
  47     /// Options related for Michael's allocator \ref Heap
  48     namespace opt {
  49         using namespace cds::opt;
  50
  51         /// Option setter specifies system topology
  52         /**
  53             See cds::OS::Win32::topology for interface example.
  54
  55             Default type: \p cds::OS::topology selects appropriate implementation for target system.
  56         */
  57         template <typename TOPOLOGY>
  58         struct sys_topology {
  59             //@cond
  60             template<class BASE> struct pack: public BASE
  61             {
  62                 typedef TOPOLOGY sys_topology;
  63             };
  64             //@endcond
  65         };
  66
  67         /// Option setter specifies system heap for large blocks
  68         /**
  69             If the block size requested is more that Michael's allocator upper limit
  70             then an allocator provided by \p system_heap option is called.
  71             By default, Michael's allocator can maintain blocks up to 64K bytes length;
  72             for blocks larger than 64K the allocator defined by this option is used.
  73
  74             Available \p HEAP implementations:
  75                 - malloc_heap
  76         */
  77         template <typename HEAP>
  78         struct system_heap
  79         {
  80             //@cond
  81             template<class BASE> struct pack: public BASE
  82             {
  83                 typedef HEAP system_heap;
  84             };
  85             //@endcond
  86         };
  87
  88         /// Option setter specifies internal aligned heap
  89         /**
  90             This heap is used by Michael's allocator for obtaining aligned memory.
  91
  92             Available \p HEAP implementations:
  93                 - aligned_malloc_heap
  94         */
  95         template <typename HEAP>
  96         struct aligned_heap {
  97             //@cond
  98             template<class BASE> struct pack: public BASE
  99             {
 100                 typedef HEAP aligned_heap;
 101             };
 102             //@endcond
 103         };
 104
 105         /// Option setter specifies page heap
 106         /**
 107             This heap is used by Michael's allocator for superblock allocation.
 108             The size of superblock is:
 109                 - 64K - for small blocks
 110                 - 1M - for other blocks
 111
 112             Available \p HEAP implementations:
 113                 - page_allocator
 114                 - page_cached_allocator
 115         */
 116         template <typename HEAP>
 117         struct page_heap {
 118             //@cond
 119             template<class BASE> struct pack: public BASE
 120             {
 121                 typedef HEAP page_heap;
 122             };
 123             //@endcond
 124         };
 125
 126         /// Option setter specifies size-class selector
 127         /**
 128             The size-class selector determines the best size-class for requested block size,
 129             i.e. it specifies allocation granularity.
 130             In fact, it selects superblock descriptor within processor heap.
 131
 132             Available \p Type implementation:
 133                 - default_sizeclass_selector
 134         */
 135         template <typename Type>
 136         struct sizeclass_selector {
 137             //@cond
 138             template<class BASE> struct pack: public BASE
 139             {
 140                 typedef Type sizeclass_selector;
 141             };
 142             //@endcond
 143         };
 144
 145         /// Option setter specifies free-list of superblock descriptor
 146         /**
 147             Available \p Type implementations:
 148                 - free_list_locked
 149         */
 150         template <typename Type>
 151         struct free_list {
 152             //@cond
 153             template<class BASE> struct pack: public BASE
 154             {
 155                 typedef Type free_list;
 156             };
 157             //@endcond
 158         };
 159
 160         /// Option setter specifies partial list of superblocks
 161         /**
 162             Available \p Type implementations:
 163                 - partial_list_locked
 164         */
 165         template <typename Type>
 166         struct partial_list {
 167             //@cond
 168             template<class BASE> struct pack: public BASE
 169             {
 170                 typedef Type partial_list;
 171             };
 172             //@endcond
 173         };
 174
 175         /// Option setter for processor heap statistics
 176         /**
 177             The option specifies a type for gathering internal processor heap statistics.
 178             The processor heap statistics is gathered on per processor basis.
 179             Large memory block (more than 64K) allocated directly from OS does not fall into these statistics.
 180             For OS-allocated memory block see \ref os_allocated_stat option.
 181
 182             Available \p Type implementations:
 183                 - \ref procheap_atomic_stat
 184                 - \ref procheap_empty_stat
 185
 186             For interface of type \p Type see \ref procheap_atomic_stat.
 187         */
 188         template <typename Type>
 189         struct procheap_stat {
 190             //@cond
 191             template <class BASE> struct pack: public BASE
 192             {
 193                 typedef Type procheap_stat;
 194             };
 195             //@endcond
 196         };
 197
 198         /// Option setter for OS-allocated memory
 199         /**
 200             The option specifies a type for gathering internal statistics of
 201             large (OS-allocated) memory blocks that is too big to maintain by Michael's heap
 202             (with default \ref sizeclass_selector, the block that large than 64K is not
 203             maintained by Michael's heap and passed directly to system allocator).
 204
 205             Note that OS-allocated memory statistics does not include memory allocation
 206             for heap's internal purposes. Only direct call of \p alloc or \p alloc_aligned
 207             for large memory block is counted.
 208
 209             Available \p Type implementations:
 210                 - \ref os_allocated_atomic
 211                 - \ref os_allocated_empty
 212         */
 213         template <typename Type>
 214         struct os_allocated_stat {
 215             //@cond
 216             template <class BASE> struct pack: public BASE
 217             {
 218                 typedef Type os_allocated_stat;
 219             };
 220             //@endcond
 221         };
 222
 223         /// Option setter for bounds checking
 224         /**
 225             This option defines a strategy to check upper memory boundary of allocated blocks.
 226             \p Type defines a class for bound checking with following interface:
 227
 228             \code
 229             class bound_checker
 230             {
 231             public:
 232                 enum {
 233                     trailer_size = numeric_const
 234                 };
 235
 236                 void make_trailer( void * pStartArea, void * pEndBlock, size_t nAllocSize );
 237                 bool check_bounds( void * pStartArea, void * pEndBlock, size_t nBlockSize );
 238             }
 239             \endcode
 240
 241             Before allocating a memory block of size N, the heap adds the \p trailer_size to N and really it
 242             allocates N + trailer_size bytes. Then, the heap calls \p make_trailer function of bound checker with arguments:
 243                 - \p pStartArea - start of allocated block
 244                 - \p pEndBlock - the first byte after really allocated block; \code pEndBlock - pStartArea >= N + trailer_size \endcode
 245                 - \p nAllocSize -  requested size in bytes (i.e. N)
 246             So, \p make_trailer function can place some predefined value called bound mark of any type, for example, int64,
 247             on address pStartArea + nAllocSize, and store real allocated block size N to pEndBlock - sizeof(size_t).
 248             In this example, \p trailer_size constant is equal sizeof(int64) + sizeof(size_t).
 249
 250             Before the memory block previously allocated is deallocating, the \p check_bounds function is called.
 251             The function has similar signature:
 252                 - \p pStartArea - start of allocated block (like \p make_trailer fist argument)
 253                 - \p pEndBlock - the first byte after allocated block (like \p make_trailer second argument)
 254                 - \p nBlockSize - real allocated block size, not equal to \p nAllocSize argument of \p make_trailer
 255
 256             The function can:
 257                 - calculate real allocated block size: \code N = *reinterpret_cast<size_t>(pEndBlock - sizeof(size_t)) \endcode
 258                 - check whether the bound mark is unchanged: \code *reinterpret_cast<int64>(pStartArea + N) == bound_mark \endcode
 259                 - if it is not equal - make assertion
 260
 261             The library provides the following predefined bound checkers, i.e they are possible values of \p Type
 262             template argument:
 263                 \li cds::opt::none - no bound checking is performed (default)
 264                 \li michael::debug_bound_checking - an assertion is thrown when memory bound violation is detected.
 265                     This option is acceptable only in debug mode. For release mode it is equal to cds::opt::none.
 266                 \li michael::strong_bound_checking - an assertion is thrown in debug mode if memory bound violation is detected;
 267                     an exception is thrown in release mode.
 268         */
 269         template <typename Type>
 270         struct check_bounds {
 271             //@cond
 272             template <class BASE> struct pack: public BASE
 273             {
 274                 typedef Type check_bounds;
 275             };
 276             //@endcond
 277         };
 278     }
 279
 280 }}} // namespace cds::memory::michael
 281
 282 #endif // #ifndef CDSLIB_MEMORY_MICHAEL_OPTIONS_H