From 91dbaa8005237a46dc5993083833df1e7f4fc047 Mon Sep 17 00:00:00 2001 From: khizmax Date: Sun, 5 Jun 2016 09:03:44 +0300 Subject: [PATCH] Fixed use-after-free bug in VyukovMPMCCycleQueue internal buffer. To prevent this bug the queue uses an uninitialized buffer now. cds::opt::buffer option is divided to initialized (cds::opt::v::initialized_dynamic_buffer, cds::opt::v::initialized_static_buffer) and uninitialized (cds::opt::v::uninitialized_dynamic_buffer, cds::opt::v::uninitialized_static_buffer) ones. The old cds::opt::v::dynamic_buffer and cds::opt::v::static_buffer classes are removed. --- cds/container/mspriority_queue.h | 6 +- cds/container/treiber_stack.h | 30 +- cds/container/tsigas_cycle_queue.h | 14 +- cds/container/vyukov_mpmc_cycle_queue.h | 16 +- cds/intrusive/mspriority_queue.h | 18 +- cds/intrusive/striped_set.h | 7 +- .../striped_set/boost_unordered_set.h | 6 +- cds/intrusive/treiber_stack.h | 34 +-- cds/intrusive/tsigas_cycle_queue.h | 14 +- cds/intrusive/vyukov_mpmc_cycle_queue.h | 16 +- cds/memory/michael/allocator.h | 2 +- cds/memory/vyukov_queue_pool.h | 4 +- cds/opt/buffer.h | 257 ++++++++++++++++-- change.log | 7 + .../ellen_bintree_update_desc_pool.h | 4 +- test/stress/pqueue/pqueue_type.h | 16 +- test/stress/queue/intrusive_queue_type.h | 10 +- test/stress/queue/queue_type.h | 16 +- test/stress/stack/intrusive_stack_type.h | 4 +- test/stress/stack/stack_type.h | 4 +- test/unit/pqueue/intrusive_mspqueue.cpp | 4 +- test/unit/pqueue/mspqueue.cpp | 4 +- test/unit/queue/intrusive_tsigas_queue.cpp | 6 +- test/unit/queue/intrusive_vyukov_queue.cpp | 6 +- test/unit/queue/tsigas_queue.cpp | 10 +- test/unit/queue/vyukov_mpmc_queue.cpp | 10 +- .../stack/intrusive_treiber_stack_dhp.cpp | 6 +- .../unit/stack/intrusive_treiber_stack_hp.cpp | 6 +- test/unit/stack/treiber_stack_dhp.cpp | 4 +- test/unit/stack/treiber_stack_hp.cpp | 4 +- .../intrusive_boost_unordered_set.cpp | 12 +- .../test_ellen_bintree_update_desc_pool.h | 2 +- 32 files changed, 395 insertions(+), 164 deletions(-) diff --git a/cds/container/mspriority_queue.h b/cds/container/mspriority_queue.h index 23b2324b..3ebcb3c7 100644 --- a/cds/container/mspriority_queue.h +++ b/cds/container/mspriority_queue.h @@ -76,8 +76,8 @@ namespace cds { namespace container { /// Metafunction converting option list to traits /** \p Options are: - - \p opt::buffer - the buffer type for heap array. Possible type are: \p opt::v::static_buffer, \p opt::v::dynamic_buffer. - Default is \p %opt::v::dynamic_buffer. + - \p opt::buffer - the buffer type for heap array. Possible type are: \p opt::v::initiaized_static_buffer, \p opt::v::initialized_dynamic_buffer. + Default is \p %opt::v::initialized_dynamic_buffer. You may specify any type of values for the buffer since at instantiation time the \p buffer::rebind member metafunction is called to change the type of values stored in the buffer. - \p opt::compare - priority compare functor. No default functor is provided. @@ -164,7 +164,7 @@ namespace cds { namespace container { public: /// Constructs empty priority queue /** - For \p cds::opt::v::static_buffer the \p nCapacity parameter is ignored. + For \p cds::opt::v::initialized_static_buffer the \p nCapacity parameter is ignored. */ MSPriorityQueue( size_t nCapacity ) : base_class( nCapacity ) diff --git a/cds/container/treiber_stack.h b/cds/container/treiber_stack.h index 3de43631..48cc2699 100644 --- a/cds/container/treiber_stack.h +++ b/cds/container/treiber_stack.h @@ -87,12 +87,12 @@ namespace cds { namespace container { /// Buffer type for elimination array /** - Possible types are \p opt::v::static_buffer, \p opt::v::dynamic_buffer. + Possible types are \p opt::v::initialized_static_buffer, \p opt::v::initialized_dynamic_buffer. The buffer can be any size: \p Exp2 template parameter of those classes can be \p false. The size should be selected empirically for your application and hardware, there are no common rules for that. - Default is %opt::v::static_buffer< any_type, 4 > . + Default is %opt::v::initialized_static_buffer< any_type, 4 > . */ - typedef opt::v::static_buffer< int, 4 > buffer; + typedef opt::v::initialized_static_buffer< int, 4 > buffer; /// Random engine to generate a random position in elimination array typedef opt::v::c_rand random_engine; @@ -106,26 +106,26 @@ namespace cds { namespace container { /// Metafunction converting option list to \p TreiberStack traits /** Supported \p Options are: - - opt::allocator - allocator (like \p std::allocator) used for allocating stack nodes. Default is \ref CDS_DEFAULT_ALLOCATOR - - opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used. - - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) + - \p opt::allocator - allocator (like \p std::allocator) used for allocating stack nodes. Default is \ref CDS_DEFAULT_ALLOCATOR + - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used. + - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) or \p opt::v::sequential_consistent (sequentially consisnent memory model). - - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter, i.e. + - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter, i.e. no item counting. Use \p cds::atomicity::item_counter to enable item counting. - - opt::stat - the type to gather internal statistics. + - \p opt::stat - the type to gather internal statistics. Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default), user-provided class that supports \p %treiber_stack::stat interface. - - opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false. + - \p opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false. If elimination back-off is enabled, additional options can be specified: - - opt::buffer - a buffer type for elimination array, see \p opt::v::static_buffer, \p opt::v::dynamic_buffer. + - \p opt::buffer - an initialized buffer type for elimination array, see \p opt::v::initialized_static_buffer, \p opt::v::initialized_dynamic_buffer. The buffer can be any size: \p Exp2 template parameter of those classes can be \p false. The size should be selected empirically for your application and hardware, there are no common rules for that. - Default is %opt::v::static_buffer< any_type, 4 > . - - opt::random_engine - a random engine to generate a random position in elimination array. + Default is %opt::v::initialized_static_buffer< any_type, 4 > . + - \p opt::random_engine - a random engine to generate a random position in elimination array. Default is \p opt::v::c_rand. - - opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<> - - opt::lock_type - a lock type used in elimination back-off, default is \p cds::sync::spin. + - \p opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<> + - \p opt::lock_type - a lock type used in elimination back-off, default is \p cds::sync::spin. Example: declare %TreiberStack with item counting and internal statistics using \p %make_traits \code @@ -302,7 +302,7 @@ namespace cds { namespace container { /// Constructs empty stack and initializes elimination back-off data /** This form should be used if you use elimination back-off with dynamically allocated collision array, i.e - \p Options... contains cds::opt::buffer< cds::opt::v::dynamic_buffer >. + \p Options... contains cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer >. \p nCollisionCapacity parameter specifies the capacity of collision array. */ TreiberStack( size_t nCollisionCapacity ) diff --git a/cds/container/tsigas_cycle_queue.h b/cds/container/tsigas_cycle_queue.h index 7f7f88f1..ad835b33 100644 --- a/cds/container/tsigas_cycle_queue.h +++ b/cds/container/tsigas_cycle_queue.h @@ -51,8 +51,10 @@ namespace cds { namespace container { buffer for required type via \p rebind metafunction. For \p TsigasCycleQueue queue the buffer size should have power-of-2 size. + + You should use any initialized buffer type, see \p opt::buffer. */ - typedef cds::opt::v::dynamic_buffer< void * > buffer; + typedef cds::opt::v::initialized_dynamic_buffer< void * > buffer; /// Node allocator typedef CDS_DEFAULT_ALLOCATOR allocator; @@ -78,7 +80,7 @@ namespace cds { namespace container { /** Supported \p Options are: - \p opt::buffer - the buffer type for internal cyclic array. Possible types are: - \p opt::v::dynamic_buffer (the default), \p opt::v::static_buffer. The type of + \p opt::v::initialized_dynamic_buffer (the default), \p opt::v::initialized_static_buffer. The type of element in the buffer is not important: it will be changed via \p rebind metafunction. - \p opt::allocator - allocator (like \p std::allocator) used for allocating queue items. Default is \ref CDS_DEFAULT_ALLOCATOR - \p opt::back_off - back-off strategy used, default is \p cds::backoff::empty. @@ -92,7 +94,7 @@ namespace cds { namespace container { \code typedef cds::container::TsigasCycleQueue< Foo, typename cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::static_buffer< void *, 1024 >, + cds::opt::buffer< cds::opt::v::initialized_static_buffer< void *, 1024 >, cds::opt::item_counter< cds::atomicity::item_counter > >::type > myQueue; @@ -179,7 +181,7 @@ namespace cds { namespace container { // Queue of Foo, capacity is 1024, statically allocated buffer: typedef cds::container::TsigasCycleQueue< Foo, typename cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::static_buffer< Foo, 1024 > > + cds::opt::buffer< cds::opt::v::initialized_static_buffer< Foo, 1024 > > >::type > static_queue; static_queue stQueue; @@ -187,7 +189,7 @@ namespace cds { namespace container { // Queue of Foo, capacity is 1024, dynamically allocated buffer: typedef cds::container::TsigasCycleQueue< Foo typename cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::dynamic_buffer< Foo > > + cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< Foo > > >::type > dynamic_queue; dynamic_queue dynQueue( 1024 ); @@ -259,7 +261,7 @@ namespace cds { namespace container { public: /// Initialize empty queue of capacity \p nCapacity /** - If internal buffer type is \p cds::opt::v::static_buffer, the \p nCapacity parameter is ignored. + If internal buffer type is \p cds::opt::v::initialized_static_buffer, the \p nCapacity parameter is ignored. Note, the real capacity of queue is \p nCapacity - 2. */ diff --git a/cds/container/vyukov_mpmc_cycle_queue.h b/cds/container/vyukov_mpmc_cycle_queue.h index 5263fee4..50b787c8 100644 --- a/cds/container/vyukov_mpmc_cycle_queue.h +++ b/cds/container/vyukov_mpmc_cycle_queue.h @@ -49,11 +49,15 @@ namespace cds { namespace container { /// Buffer type for internal array /* The type of element for the buffer is not important: the queue rebinds - buffer for required type via \p rebind metafunction. + the buffer for required type via \p rebind metafunction. For \p VyukovMPMCCycleQueue queue the buffer size should have power-of-2 size. + + You should use only uninitialized buffer for the queue - + \p cds::opt::v::uninitialized_dynamic_buffer (the default), + \p cds::opt::v::uninitialized_static_buffer. */ - typedef cds::opt::v::dynamic_buffer< void * > buffer; + typedef cds::opt::v::uninitialized_dynamic_buffer< void * > buffer; /// A functor to clean item dequeued. /** @@ -94,8 +98,8 @@ namespace cds { namespace container { /// Metafunction converting option list to \p vyukov_queue::traits /** Supported \p Options are: - - \p opt::buffer - the buffer type for internal cyclic array. Possible types are: - \p opt::v::dynamic_buffer (the default), \p opt::v::static_buffer. The type of + - \p opt::buffer - an uninitialized buffer type for internal cyclic array. Possible types are: + \p opt::v::uninitialized_dynamic_buffer (the default), \p opt::v::uninitialized_static_buffer. The type of element in the buffer is not important: it will be changed via \p rebind metafunction. - \p opt::value_cleaner - a functor to clean item dequeued. The functor calls the destructor for queue item. @@ -113,7 +117,7 @@ namespace cds { namespace container { \code typedef cds::container::VyukovMPMCCycleQueue< Foo, typename cds::container::vyukov_queue::make_traits< - cds::opt::buffer< cds::opt::v::static_buffer< void *, 1024 >, + cds::opt::buffer< cds::opt::v::uninitialized_static_buffer< void *, 1024 >, cds::opt::item_counte< cds::atomicity::item_counter > >::type > myQueue; @@ -221,7 +225,7 @@ namespace cds { namespace container { public: /// Constructs the queue of capacity \p nCapacity /** - For \p cds::opt::v::static_buffer the \p nCapacity parameter is ignored. + For \p cds::opt::v::uninitialized_static_buffer the \p nCapacity parameter is ignored. The buffer capacity must be the power of two. */ diff --git a/cds/intrusive/mspriority_queue.h b/cds/intrusive/mspriority_queue.h index 8dfbad07..f0e04dc1 100644 --- a/cds/intrusive/mspriority_queue.h +++ b/cds/intrusive/mspriority_queue.h @@ -86,13 +86,13 @@ namespace cds { namespace intrusive { struct traits { /// Storage type /** - The storage type for the heap array. Default is \p cds::opt::v::dynamic_buffer. + The storage type for the heap array. Default is \p cds::opt::v::initialized_dynamic_buffer. You may specify any type of buffer's value since at instantiation time the \p buffer::rebind member metafunction is called to change type of values stored in the buffer. */ - typedef opt::v::dynamic_buffer buffer; + typedef opt::v::initialized_dynamic_buffer buffer; /// Priority compare functor /** @@ -123,9 +123,9 @@ namespace cds { namespace intrusive { /// Metafunction converting option list to traits /** \p Options: - - \p opt::buffer - the buffer type for heap array. Possible type are: \p opt::v::static_buffer, \p opt::v::dynamic_buffer. - Default is \p %opt::v::dynamic_buffer. - You may specify any type of values for the buffer since at instantiation time + - \p opt::buffer - the buffer type for heap array. Possible type are: \p opt::v::initialized_static_buffer, \p opt::v::initialized_dynamic_buffer. + Default is \p %opt::v::initialized_dynamic_buffer. + You may specify any type of value for the buffer since at instantiation time the \p buffer::rebind member metafunction is called to change the type of values stored in the buffer. - \p opt::compare - priority compare functor. No default functor is provided. If the option is not specified, the \p opt::less is used. @@ -187,9 +187,9 @@ namespace cds { namespace intrusive { typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator; # endif - typedef typename traits::lock_type lock_type ; ///< heap's size lock type - typedef typename traits::back_off back_off ; ///< Back-off strategy - typedef typename traits::stat stat ; ///< internal statistics type + typedef typename traits::lock_type lock_type; ///< heap's size lock type + typedef typename traits::back_off back_off; ///< Back-off strategy + typedef typename traits::stat stat; ///< internal statistics type protected: //@cond @@ -245,7 +245,7 @@ namespace cds { namespace intrusive { public: /// Constructs empty priority queue /** - For \p cds::opt::v::static_buffer the \p nCapacity parameter is ignored. + For \p cds::opt::v::initialized_static_buffer the \p nCapacity parameter is ignored. */ MSPriorityQueue( size_t nCapacity ) : m_Heap( nCapacity ) diff --git a/cds/intrusive/striped_set.h b/cds/intrusive/striped_set.h index 328dbafe..8aea0cb6 100644 --- a/cds/intrusive/striped_set.h +++ b/cds/intrusive/striped_set.h @@ -92,8 +92,8 @@ namespace cds { namespace intrusive { Note that the choose of resizing policy depends of \p Container type: for sequential containers like \p boost::intrusive::list the right policy can significantly improve performance. For other, non-sequential types of \p Container (like a \p boost::intrusive::set) the resizing policy is not so important. - - \p cds::opt::buffer - a buffer type used only for \p boost::intrusive::unordered_set. - Default is cds::opt::v::static_buffer< cds::any_type, 256 > . + - \p cds::opt::buffer - an initialized buffer type used only for \p boost::intrusive::unordered_set. + Default is cds::opt::v::initialized_static_buffer< cds::any_type, 256 > . \p opt::compare or \p opt::less options are used in some \p Container class for ordering. \p %opt::compare option has the highest priority: if \p %opt::compare is specified, \p %opt::less is not used. @@ -195,7 +195,8 @@ namespace cds { namespace intrusive { You should provide two different hash function \p h1 and \p h2 - one for \p boost::intrusive::unordered_set and other for \p %StripedSet. For the best result, \p h1 and \p h2 must be orthogonal i.e. h1(X) != h2(X) for any value \p X - The option \p opt::buffer is used for \p boost::intrusive::bucket_traits. Default is cds::opt::v::static_buffer< cds::any_type, 256 > . + The option \p opt::buffer is used for \p boost::intrusive::bucket_traits. + Default is cds::opt::v::initialized_static_buffer< cds::any_type, 256 > . The resizing policy should correlate with the buffer capacity. The default resizing policy is cds::container::striped_set::load_factor_resizing<256> what gives load factor 1 for default bucket buffer that is the best for \p boost::intrusive::unordered_set. diff --git a/cds/intrusive/striped_set/boost_unordered_set.h b/cds/intrusive/striped_set/boost_unordered_set.h index fe61e01e..af738db9 100644 --- a/cds/intrusive/striped_set/boost_unordered_set.h +++ b/cds/intrusive/striped_set/boost_unordered_set.h @@ -55,11 +55,11 @@ namespace cds { namespace intrusive { namespace striped_set { typedef typename opt::value < typename opt::find_option < - opt::buffer< opt::v::static_buffer< cds::any_type, 256 > >, - Options... + opt::buffer< opt::v::initialized_static_buffer< cds::any_type, 256 > >, + Options... > ::type > ::buffer initial_buffer_type; - typedef typename initial_buffer_type::template rebind< typename container_type::bucket_type >::other buffer_type; + typedef typename initial_buffer_type::template rebind< typename container_type::bucket_type >::other buffer_type; typedef cds::intrusive::striped_set::load_factor_resizing<256> default_resizing_policy; private: diff --git a/cds/intrusive/treiber_stack.h b/cds/intrusive/treiber_stack.h index aa4147e0..dff18f4d 100644 --- a/cds/intrusive/treiber_stack.h +++ b/cds/intrusive/treiber_stack.h @@ -218,12 +218,12 @@ namespace cds { namespace intrusive { /// Buffer type for elimination array /** - Possible types are \p opt::v::static_buffer, \p opt::v::dynamic_buffer. + Possible types are \p opt::v::initialized_static_buffer, \p opt::v::initialized_dynamic_buffer. The buffer can be any size: \p Exp2 template parameter of those classes can be \p false. The size should be selected empirically for your application and hardware, there are no common rules for that. - Default is %opt::v::static_buffer< any_type, 4 > . + Default is %opt::v::initialized_static_buffer< any_type, 4 > . */ - typedef opt::v::static_buffer< int, 4 > buffer; + typedef opt::v::initialized_static_buffer< int, 4 > buffer; /// Random engine to generate a random position in elimination array typedef opt::v::c_rand random_engine; @@ -237,30 +237,30 @@ namespace cds { namespace intrusive { /// Metafunction converting option list to \p treiber_stack::traits /** Supported \p Options are: - - opt::hook - hook used. Possible hooks are: \p treiber_stack::base_hook, \p treiber_stack::member_hook, \p treiber_stack::traits_hook. + - \p opt::hook - hook used. Possible hooks are: \p treiber_stack::base_hook, \p treiber_stack::member_hook, \p treiber_stack::traits_hook. If the option is not specified, \p %treiber_stack::base_hook<> is used. - - opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used. - - opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only + - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used. + - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only in \p TreiberStack::clear function. - - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link. - - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) + - \p opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link. + - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) or \p opt::v::sequential_consistent (sequentially consisnent memory model). - - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter, i.e. + - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter, i.e. no item counting. Use \p cds::atomicity::item_counter to enable item counting. - - opt::stat - the type to gather internal statistics. + - \p opt::stat - the type to gather internal statistics. Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default), user-provided class that supports \p treiber_stack::stat interface. - - opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false. + - \p opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false. If elimination back-off is enabled, additional options can be specified: - - opt::buffer - a buffer type for elimination array, see \p opt::v::static_buffer, \p opt::v::dynamic_buffer. + - \p opt::buffer - a buffer type for elimination array, see \p opt::v::initialized_static_buffer, \p opt::v::initialized_dynamic_buffer. The buffer can be any size: \p Exp2 template parameter of those classes can be \p false. The size should be selected empirically for your application and hardware, there are no common rules for that. - Default is %opt::v::static_buffer< any_type, 4 > . - - opt::random_engine - a random engine to generate a random position in elimination array. + Default is %opt::v::initialized_static_buffer< any_type, 4 > . + - \p opt::random_engine - a random engine to generate a random position in elimination array. Default is \p opt::v::c_rand. - - opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<> - - opt::lock_type - a lock type used in elimination back-off, default is \p cds::sync::spin + - \p opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<> + - \p opt::lock_type - a lock type used in elimination back-off, default is \p cds::sync::spin Example: declare \p %TreiberStack with elimination enabled and internal statistics \code @@ -710,7 +710,7 @@ namespace cds { namespace intrusive { /// Constructs empty stack and initializes elimination back-off data /** This form should be used if you use elimination back-off with dynamically allocated collision array, i.e - \p Traits contains typedef cds::opt::v::dynamic_buffer buffer. + \p Traits contains typedef cds::opt::v::initialized_dynamic_buffer buffer. \p nCollisionCapacity parameter specifies the capacity of collision array. */ TreiberStack( size_t nCollisionCapacity ) diff --git a/cds/intrusive/tsigas_cycle_queue.h b/cds/intrusive/tsigas_cycle_queue.h index 1d1f5788..b667f39c 100644 --- a/cds/intrusive/tsigas_cycle_queue.h +++ b/cds/intrusive/tsigas_cycle_queue.h @@ -52,8 +52,10 @@ namespace cds { namespace intrusive { buffer for required type via \p rebind metafunction. For \p TsigasCycleQueue queue the buffer size should have power-of-2 size. + + You should use any initialized buffer type, see \p opt::buffer. */ - typedef cds::opt::v::dynamic_buffer< void * > buffer; + typedef cds::opt::v::initialized_dynamic_buffer< void * > buffer; /// Back-off strategy typedef cds::backoff::empty back_off; @@ -79,7 +81,7 @@ namespace cds { namespace intrusive { /** Supported \p Options are: - \p opt::buffer - the buffer type for internal cyclic array. Possible types are: - \p opt::v::dynamic_buffer (the default), \p opt::v::static_buffer. The type of + \p opt::v::initialized_dynamic_buffer (the default), \p opt::v::initialized_static_buffer. The type of element in the buffer is not important: it will be changed via \p rebind metafunction. - \p opt::back_off - back-off strategy used, default is \p cds::backoff::empty. - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used @@ -94,7 +96,7 @@ namespace cds { namespace intrusive { \code typedef cds::intrusive::TsigasCycleQueue< Foo, typename cds::intrusive::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::static_buffer< void *, 1024 >, + cds::opt::buffer< cds::opt::v::initialized_static_buffer< void *, 1024 >, cds::opt::item_counte< cds::atomicity::item_counter > >::type > myQueue; @@ -156,7 +158,7 @@ namespace cds { namespace intrusive { // Queue of Foo pointers, capacity is 1024, statically allocated buffer: struct queue_traits: public cds::intrusive::tsigas_queue::traits { - typedef cds::opt::v::static_buffer< Foo, 1024 > buffer; + typedef cds::opt::v::initialized_static_buffer< Foo, 1024 > buffer; }; typedef cds::intrusive::TsigasCycleQueue< Foo, queue_traits > static_queue; static_queue stQueue; @@ -164,7 +166,7 @@ namespace cds { namespace intrusive { // Queue of Foo pointers, capacity is 1024, dynamically allocated buffer, with item counting: typedef cds::intrusive::TsigasCycleQueue< Foo, typename cds::intrusive::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::dynamic_buffer< Foo > >, + cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< Foo > >, cds::opt::item_counter< cds::atomicity::item_counter > >::type > dynamic_queue; @@ -230,7 +232,7 @@ namespace cds { namespace intrusive { public: /// Initialize empty queue of capacity \p nCapacity /** - If internal buffer type is \p cds::opt::v::static_buffer, the \p nCapacity parameter is ignored. + If internal buffer type is \p cds::opt::v::initialized_static_buffer, the \p nCapacity parameter is ignored. Note that the real capacity of queue is \p nCapacity - 2. */ diff --git a/cds/intrusive/vyukov_mpmc_cycle_queue.h b/cds/intrusive/vyukov_mpmc_cycle_queue.h index e773636f..709d69b2 100644 --- a/cds/intrusive/vyukov_mpmc_cycle_queue.h +++ b/cds/intrusive/vyukov_mpmc_cycle_queue.h @@ -51,8 +51,8 @@ namespace cds { namespace intrusive { /// Metafunction converting option list to \p vyukov_queue::traits /** Supported \p Options are: - - \p opt::buffer - the buffer type for internal cyclic array. Possible types are: - \p opt::v::dynamic_buffer (the default), \p opt::v::static_buffer. The type of + - \p opt::buffer - an uninitialized buffer type for internal cyclic array. Possible types are: + \p opt::v::uninitialized_dynamic_buffer (the default), \p opt::v::uninitialized_static_buffer. The type of element in the buffer is not important: it will be changed via \p rebind metafunction. - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only in \p clear() member function. @@ -61,13 +61,13 @@ namespace cds { namespace intrusive { - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used. - \p opt::padding - padding for internal critical atomic data. Default is \p opt::cache_line_padding - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) - or \p opt::v::sequential_consistent (sequentially consisnent memory model). + or \p opt::v::sequential_consistent (sequentially consistent memory model). - Example: declare \p %VyukovMPMCCycleQueue with item counting and static iternal buffer of size 1024: + Example: declare \p %VyukovMPMCCycleQueue with item counting and static internal buffer of size 1024: \code typedef cds::intrusive::VyukovMPMCCycleQueue< Foo, typename cds::intrusive::vyukov_queue::make_traits< - cds::opt::buffer< cds::opt::v::static_buffer< void *, 1024 >, + cds::opt::buffer< cds::opt::v::uninitialized_static_buffer< void *, 1024 >, cds::opt::item_counter< cds::atomicity::item_counter > >::type > myQueue; @@ -124,7 +124,7 @@ namespace cds { namespace intrusive { // Queue of Foo pointers, capacity is 1024, statically allocated buffer: typedef cds::intrusive::VyukovMPMCCycleQueue< Foo, typename cds::intrusive::vyukov_queue::make_traits< - cds::opt::buffer< cds::opt::v::static_buffer< Foo, 1024 > > + cds::opt::buffer< cds::opt::v::uninitialized_static_buffer< Foo, 1024 > > >::type > static_queue; static_queue stQueue; @@ -132,7 +132,7 @@ namespace cds { namespace intrusive { // Queue of Foo pointers, capacity is 1024, dynamically allocated buffer: struct queue_traits: public cds::intrusive::vyukov_queue::traits { - typedef cds::opt::v::dynamic_buffer< Foo > buffer; + typedef cds::opt::v::uninitialized_dynamic_buffer< Foo > buffer; }; typedef cds::intrusive::VyukovMPMCCycleQueue< Foo, queue_traits > dynamic_queue; dynamic_queue dynQueue( 1024 ); @@ -163,7 +163,7 @@ namespace cds { namespace intrusive { public: /// Constructs the queue of capacity \p nCapacity /** - For \p cds::opt::v::static_buffer the \p nCapacity parameter is ignored. + For \p cds::opt::v::uninitialized_static_buffer the \p nCapacity parameter is ignored. */ VyukovMPMCCycleQueue( size_t nCapacity = 0 ) : base_class( nCapacity ) diff --git a/cds/memory/michael/allocator.h b/cds/memory/michael/allocator.h index 5d843f3d..678631e4 100644 --- a/cds/memory/michael/allocator.h +++ b/cds/memory/michael/allocator.h @@ -176,7 +176,7 @@ namespace michael { #endif struct free_list_traits : public cds::container::vyukov_queue::traits { - typedef opt::v::static_buffer buffer; + typedef opt::v::initialized_static_buffer buffer; #ifdef _DEBUG typedef make_null_ptr value_cleaner; #endif diff --git a/cds/memory/vyukov_queue_pool.h b/cds/memory/vyukov_queue_pool.h index 4c578097..ab692ccd 100644 --- a/cds/memory/vyukov_queue_pool.h +++ b/cds/memory/vyukov_queue_pool.h @@ -76,7 +76,7 @@ namespace cds { namespace memory { // Pool of Foo object of size 1024. struct pool_traits: public cds::memory::vyukov_queue_pool_traits { - typedef cds::opt::v::static_buffer< Foo, 1024 > buffer; + typedef cds::opt::v::uninitialized_static_buffer< Foo, 1024 > buffer; }; typedef cds::memory::vyukov_queue_pool< Foo, pool_traits > pool_type; static pool_type thePool; @@ -387,7 +387,7 @@ namespace cds { namespace memory { // Pool of Foo object of size 1024. struct pool_traits: public cds::memory::vyukov_queue_pool_traits { - typedef cds::opt::v::static_buffer< Foo, 1024 > buffer; + typedef cds::opt::v::uninitialized_static_buffer< Foo, 1024 > buffer; }; typedef cds::memory::bounded_vyukov_queue_pool< Foo, pool_traits > pool_type; static pool_type thePool; diff --git a/cds/opt/buffer.h b/cds/opt/buffer.h index 93c1e47e..9ded909e 100644 --- a/cds/opt/buffer.h +++ b/cds/opt/buffer.h @@ -48,8 +48,19 @@ namespace cds { namespace opt { The template parameter \p Type should be rebindable. Implementations: - - \p opt::v::static_buffer - - \p opt::v::dynamic_buffer + - \p opt::v::initialized_static_buffer + - \p opt::v::uninitialized_static_buffer + - \p opt::v::initialized_dynamic_buffer + - \p opt::v::uninitialized_dynamic_buffer + + Uninitialized buffer is just an array of uninitialized elements. + Each element should be manually constructed, for example with a placement new operator. + When the uninitialized buffer is destroyed the destructor of its element is not called. + + Initialized buffer contains default-constructed elements. Element destructor is called automatically + when the buffer is destroyed. + + Initialized and uninitialized buffers are not */ template struct buffer { @@ -63,11 +74,113 @@ namespace cds { namespace opt { namespace v { - /// Static buffer + /// Static uninitialized buffer + /** + One of available type for \p opt::buffer option. + + This buffer maintains static array of uninitialized elements. + You should manually construct each element when needed. + No dynamic memory allocation performed. + + \par Template parameters: + - \p T - item type the buffer stores + - \p Capacity - the capacity of buffer. The value must be power of two if \p Exp2 is \p true + - \p Exp2 - a boolean flag. If it is \p true the buffer capacity must be power of two. + Otherwise it can be any positive number. Usually, it is required that the buffer has + size of a power of two. + */ + template + class uninitialized_static_buffer + { + public: + typedef T value_type; ///< value type + static CDS_CONSTEXPR const size_t c_nCapacity = Capacity; ///< Capacity + static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag + + /// Rebind buffer for other template parameters + template + struct rebind { + typedef uninitialized_static_buffer other; ///< Rebind result type + }; + + // Capacity must be power of 2 + static_assert(!c_bExp2 || (c_nCapacity & (c_nCapacity - 1)) == 0, "Capacity must be power of two"); + + private: + //@cond + union element { + value_type v; + char c; + + element() + {} + }; + + element m_buffer[c_nCapacity]; + //@endcond + public: + /// Construct static buffer + uninitialized_static_buffer() CDS_NOEXCEPT + {} + + /// Construct buffer of given capacity + /** + This ctor ignores \p nCapacity argument. The capacity of static buffer + is defined by template argument \p Capacity + */ + uninitialized_static_buffer( size_t nCapacity ) CDS_NOEXCEPT + { + CDS_UNUSED( nCapacity ); + } + + uninitialized_static_buffer( const uninitialized_static_buffer& ) = delete; + uninitialized_static_buffer& operator =( const uninitialized_static_buffer& ) = delete; + + /// Get item \p i + value_type& operator []( size_t i ) + { + assert( i < capacity() ); + return m_buffer[i].v; + } + + /// Get item \p i, const version + const value_type& operator []( size_t i ) const + { + assert( i < capacity() ); + return m_buffer[i].v; + } + + /// Returns buffer capacity + CDS_CONSTEXPR size_t capacity() const CDS_NOEXCEPT + { + return c_nCapacity; + } + + /// Zeroize the buffer + void zeroize() + { + memset( m_buffer, 0, capacity() * sizeof(m_buffer[0]) ); + } + + /// Returns pointer to buffer array + value_type * buffer() CDS_NOEXCEPT + { + return &( m_buffer[0].v ); + } + + /// Returns pointer to buffer array + value_type * buffer() const CDS_NOEXCEPT + { + return &( m_buffer[0].v ); + } + }; + + /// Static initialized buffer /** One of available type for \p opt::buffer option. - This buffer maintains static array. No dynamic memory allocation performed. + This buffer maintains static array of default-constructed elements. + No dynamic memory allocation performed. \par Template parameters: - \p T - item type the buffer stores @@ -77,17 +190,17 @@ namespace cds { namespace opt { size of a power of two. */ template - class static_buffer + class initialized_static_buffer { public: - typedef T value_type ; ///< value type - static CDS_CONSTEXPR const size_t c_nCapacity = Capacity ; ///< Capacity + typedef T value_type; ///< value type + static CDS_CONSTEXPR const size_t c_nCapacity = Capacity; ///< Capacity static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag /// Rebind buffer for other template parameters template struct rebind { - typedef static_buffer other ; ///< Rebind result type + typedef initialized_static_buffer other; ///< Rebind result type }; // Capacity must be power of 2 @@ -99,20 +212,21 @@ namespace cds { namespace opt { //@endcond public: /// Construct static buffer - static_buffer() CDS_NOEXCEPT + initialized_static_buffer() CDS_NOEXCEPT {} + /// Construct buffer of given capacity /** This ctor ignores \p nCapacity argument. The capacity of static buffer is defined by template argument \p Capacity */ - static_buffer( size_t nCapacity ) CDS_NOEXCEPT + initialized_static_buffer( size_t nCapacity ) CDS_NOEXCEPT { CDS_UNUSED( nCapacity ); } - static_buffer( const static_buffer& ) = delete; - static_buffer& operator =( const static_buffer& ) = delete; + initialized_static_buffer( const initialized_static_buffer& ) = delete; + initialized_static_buffer& operator =( const initialized_static_buffer& ) = delete; /// Get item \p i value_type& operator []( size_t i ) @@ -153,12 +267,113 @@ namespace cds { namespace opt { } }; + /// Dynamically allocated uninitialized buffer + /** + One of available type for \p opt::buffer option. + + This buffer maintains dynamically allocated array of uninitialized elements. + You should manually construct each element when needed. + Allocation is performed at construction time. + + \par Template parameters: + - \p T - item type storing in the buffer + - \p Alloc - an allocator used for allocating internal buffer (\p std::allocator interface) + - \p Exp2 - a boolean flag. If it is \p true the buffer capacity must be power of two. + Otherwise it can be any positive number. Usually, it is required that the buffer has + size of a power of two. + */ + template + class uninitialized_dynamic_buffer + { + public: + typedef T value_type; ///< Value type + static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag + + /// Rebind buffer for other template parameters + template + struct rebind { + typedef uninitialized_dynamic_buffer other; ///< Rebinding result type + }; + + //@cond + typedef typename Alloc::template rebind::other allocator_type; + //@endcond + + private: + //@cond + value_type * m_buffer; + size_t const m_nCapacity; + //@endcond + public: + /// Allocates dynamic buffer of given \p nCapacity + /** + If \p Exp2 class template parameter is \p true then actual capacity + of allocating buffer is nearest upper to \p nCapacity power of two. + */ + uninitialized_dynamic_buffer( size_t nCapacity ) + : m_nCapacity( c_bExp2 ? beans::ceil2(nCapacity) : nCapacity ) + { + assert( m_nCapacity >= 2 ); + // Capacity must be power of 2 + assert( !c_bExp2 || (m_nCapacity & (m_nCapacity - 1)) == 0 ); + + m_buffer = allocator_type().allocate( m_nCapacity ); + } + + /// Destroys dynamically allocated buffer + ~uninitialized_dynamic_buffer() + { + allocator_type().deallocate( m_buffer, m_nCapacity ); + } + + uninitialized_dynamic_buffer( const uninitialized_dynamic_buffer& ) = delete; + uninitialized_dynamic_buffer& operator =( const uninitialized_dynamic_buffer& ) = delete; + + /// Get item \p i + value_type& operator []( size_t i ) + { + assert( i < capacity() ); + return m_buffer[i]; + } + + /// Get item \p i, const version + const value_type& operator []( size_t i ) const + { + assert( i < capacity() ); + return m_buffer[i]; + } + + /// Returns buffer capacity + size_t capacity() const CDS_NOEXCEPT + { + return m_nCapacity; + } + + /// Zeroize the buffer + void zeroize() + { + memset( m_buffer, 0, capacity() * sizeof(m_buffer[0]) ); + } + + /// Returns pointer to buffer array + value_type * buffer() CDS_NOEXCEPT + { + return m_buffer; + } + + /// Returns pointer to buffer array + value_type * buffer() const CDS_NOEXCEPT + { + return m_buffer; + } + }; + - /// Dynamically allocated buffer + /// Dynamically allocated initialized buffer /** One of available type for \p opt::buffer option. - This buffer maintains dynamically allocated array. + This buffer maintains dynamically allocated array of initialized default-constructed elements. Allocation is performed at construction time. \par Template parameters: @@ -169,16 +384,16 @@ namespace cds { namespace opt { size of a power of two. */ template - class dynamic_buffer + class initialized_dynamic_buffer { public: - typedef T value_type ; ///< Value type + typedef T value_type; ///< Value type static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag /// Rebind buffer for other template parameters template struct rebind { - typedef dynamic_buffer other ; ///< Rebinding result type + typedef initialized_dynamic_buffer other; ///< Rebinding result type }; //@cond @@ -196,7 +411,7 @@ namespace cds { namespace opt { If \p Exp2 class template parameter is \p true then actual capacity of allocating buffer is nearest upper to \p nCapacity power of two. */ - dynamic_buffer( size_t nCapacity ) + initialized_dynamic_buffer( size_t nCapacity ) : m_nCapacity( c_bExp2 ? beans::ceil2(nCapacity) : nCapacity ) { assert( m_nCapacity >= 2 ); @@ -208,14 +423,14 @@ namespace cds { namespace opt { } /// Destroys dynamically allocated buffer - ~dynamic_buffer() + ~initialized_dynamic_buffer() { allocator_type a; a.Delete( m_buffer, m_nCapacity ); } - dynamic_buffer( const dynamic_buffer& ) = delete; - dynamic_buffer& operator =( const dynamic_buffer& ) = delete; + initialized_dynamic_buffer( const initialized_dynamic_buffer& ) = delete; + initialized_dynamic_buffer& operator =( const initialized_dynamic_buffer& ) = delete; /// Get item \p i value_type& operator []( size_t i ) diff --git a/change.log b/change.log index 44c45445..47ce92cd 100644 --- a/change.log +++ b/change.log @@ -11,6 +11,13 @@ in precondition checking the function can incorrectly return false. - Fixed: possible double-free case in flat combining algorithm. Thanks to Amila Jayasekara who points me to this problem + - Changed: cds::opt::buffer option is divided to initialized + (cds::opt::v::initialized_dynamic_buffer, cds::opt::v::initialized_static_buffer) + and uninitialized (cds::opt::v::uninitialized_dynamic_buffer, cds::opt::v::uninitialized_static_buffer) + ones. The old cds::opt::v::dynamic_buffer and cds::opt::v::static_buffer classes + are removed. + - Fixed: use-after-free bug in VyukovMPMCCycleQueue internal buffer. + To prevent this bug the queue uses an uninitialized buffer now. 2.1.0 06.01.2016 General release diff --git a/test/stress/framework/ellen_bintree_update_desc_pool.h b/test/stress/framework/ellen_bintree_update_desc_pool.h index bd199c94..cb7fddb2 100644 --- a/test/stress/framework/ellen_bintree_update_desc_pool.h +++ b/test/stress/framework/ellen_bintree_update_desc_pool.h @@ -45,7 +45,7 @@ namespace ellen_bintree_pool { // Update descriptor pool based on Vyukov's queue struct update_desc_pool_traits : public cds::memory::vyukov_queue_pool_traits { - typedef cds::opt::v::static_buffer< cds::any_type, 4096 > buffer; + typedef cds::opt::v::initialized_static_buffer< cds::any_type, 4096 > buffer; }; typedef cds::memory::vyukov_queue_pool< update_desc, update_desc_pool_traits > update_desc_pool_type; @@ -63,7 +63,7 @@ namespace ellen_bintree_pool { // Update descriptor pool based on bounded Vyukov's queue struct bounded_update_desc_pool_traits : public cds::memory::vyukov_queue_pool_traits { - typedef cds::opt::v::static_buffer< cds::any_type, 4096 > buffer; + typedef cds::opt::v::initialized_static_buffer< cds::any_type, 4096 > buffer; }; typedef cds::memory::bounded_vyukov_queue_pool< update_desc, bounded_update_desc_pool_traits > bounded_update_desc_pool_type; extern bounded_update_desc_pool_type s_BoundedUpdateDescPool; diff --git a/test/stress/pqueue/pqueue_type.h b/test/stress/pqueue/pqueue_type.h index 288132f8..b776a601 100644 --- a/test/stress/pqueue/pqueue_type.h +++ b/test/stress/pqueue/pqueue_type.h @@ -363,21 +363,21 @@ namespace pqueue { // MSPriorityQueue struct traits_MSPriorityQueue_static_less : public cc::mspriority_queue::make_traits < - co::buffer < co::v::static_buffer< char, c_nBoundedCapacity > > + co::buffer < co::v::initialized_static_buffer< char, c_nBoundedCapacity > > > ::type {}; typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_less > MSPriorityQueue_static_less; struct traits_MSPriorityQueue_static_less_stat : public cc::mspriority_queue::traits { - typedef co::v::static_buffer< char, c_nBoundedCapacity > buffer; + typedef co::v::initialized_static_buffer< char, c_nBoundedCapacity > buffer; typedef cc::mspriority_queue::stat<> stat; }; typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_less_stat > MSPriorityQueue_static_less_stat; struct traits_MSPriorityQueue_static_cmp : public cc::mspriority_queue::make_traits < - co::buffer< co::v::static_buffer< char, c_nBoundedCapacity > > + co::buffer< co::v::initialized_static_buffer< char, c_nBoundedCapacity > > , co::compare < cmp > > ::type {}; @@ -385,7 +385,7 @@ namespace pqueue { struct traits_MSPriorityQueue_static_mutex : public cc::mspriority_queue::make_traits< - co::buffer< co::v::static_buffer< char, c_nBoundedCapacity > > + co::buffer< co::v::initialized_static_buffer< char, c_nBoundedCapacity > > , co::lock_type >::type {}; @@ -393,14 +393,14 @@ namespace pqueue { struct traits_MSPriorityQueue_dyn_less : public cc::mspriority_queue::make_traits< - co::buffer< co::v::dynamic_buffer< char > > + co::buffer< co::v::initialized_dynamic_buffer< char > > >::type {}; typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_less > MSPriorityQueue_dyn_less; struct traits_MSPriorityQueue_dyn_less_stat : public cc::mspriority_queue::make_traits < - co::buffer< co::v::dynamic_buffer< char > > + co::buffer< co::v::initialized_dynamic_buffer< char > > , co::stat < cc::mspriority_queue::stat<> > > ::type {}; @@ -408,7 +408,7 @@ namespace pqueue { struct traits_MSPriorityQueue_dyn_cmp : public cc::mspriority_queue::make_traits < - co::buffer< co::v::dynamic_buffer< char > > + co::buffer< co::v::initialized_dynamic_buffer< char > > , co::compare < cmp > > ::type {}; @@ -416,7 +416,7 @@ namespace pqueue { struct traits_MSPriorityQueue_dyn_mutex : public cc::mspriority_queue::make_traits < - co::buffer< co::v::dynamic_buffer< char > > + co::buffer< co::v::initialized_dynamic_buffer< char > > , co::lock_type < std::mutex > > ::type {}; diff --git a/test/stress/queue/intrusive_queue_type.h b/test/stress/queue/intrusive_queue_type.h index d6f48368..fd380311 100644 --- a/test/stress/queue/intrusive_queue_type.h +++ b/test/stress/queue/intrusive_queue_type.h @@ -247,13 +247,13 @@ namespace queue { class TsigasCycleQueue_dyn : public cds::intrusive::TsigasCycleQueue< T, typename cds::intrusive::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::dynamic_buffer< int > > + cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > >::type > { typedef cds::intrusive::TsigasCycleQueue< T, typename cds::intrusive::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::dynamic_buffer< int > > + cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > >::type > base_class; public: @@ -274,14 +274,14 @@ namespace queue { class TsigasCycleQueue_dyn_ic : public cds::intrusive::TsigasCycleQueue< T, typename cds::intrusive::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::dynamic_buffer< int > > + cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > ,cds::opt::item_counter< cds::atomicity::item_counter > >::type > { typedef cds::intrusive::TsigasCycleQueue< T, typename cds::intrusive::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::dynamic_buffer< int > > + cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > ,cds::opt::item_counter< cds::atomicity::item_counter > >::type > base_class; @@ -302,7 +302,7 @@ namespace queue { // VyukovMPMCCycleQueue struct traits_VyukovMPMCCycleQueue_dyn : public cds::intrusive::vyukov_queue::traits { - typedef cds::opt::v::dynamic_buffer< int > buffer; + typedef cds::opt::v::uninitialized_dynamic_buffer< int > buffer; }; class VyukovMPMCCycleQueue_dyn : public cds::intrusive::VyukovMPMCCycleQueue< T, traits_VyukovMPMCCycleQueue_dyn > diff --git a/test/stress/queue/queue_type.h b/test/stress/queue/queue_type.h index af76bc59..0db165ec 100644 --- a/test/stress/queue/queue_type.h +++ b/test/stress/queue/queue_type.h @@ -217,13 +217,13 @@ namespace queue { class TsigasCycleQueue_dyn : public cds::container::TsigasCycleQueue< Value, typename cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::dynamic_buffer< int > > + cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > >::type > { typedef cds::container::TsigasCycleQueue< Value, typename cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::dynamic_buffer< int > > + cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > >::type > base_class; public: @@ -244,14 +244,14 @@ namespace queue { class TsigasCycleQueue_dyn_michaelAlloc : public cds::container::TsigasCycleQueue< Value, typename cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::dynamic_buffer< int > > + cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > ,cds::opt::allocator< memory::MichaelAllocator > >::type > { typedef cds::container::TsigasCycleQueue< Value, typename cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::dynamic_buffer< int > > + cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > , cds::opt::allocator< memory::MichaelAllocator > >::type > base_class; @@ -273,14 +273,14 @@ namespace queue { class TsigasCycleQueue_dyn_ic : public cds::container::TsigasCycleQueue< Value, typename cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::dynamic_buffer< int > > + cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > ,cds::opt::item_counter< cds::atomicity::item_counter > >::type > { typedef cds::container::TsigasCycleQueue< Value, typename cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::dynamic_buffer< int > > + cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > ,cds::opt::item_counter< cds::atomicity::item_counter > >::type > base_class; @@ -301,7 +301,7 @@ namespace queue { // VyukovMPMCCycleQueue struct traits_VyukovMPMCCycleQueue_dyn : public cds::container::vyukov_queue::traits { - typedef cds::opt::v::dynamic_buffer< int > buffer; + typedef cds::opt::v::uninitialized_dynamic_buffer< int > buffer; }; class VyukovMPMCCycleQueue_dyn : public cds::container::VyukovMPMCCycleQueue< Value, traits_VyukovMPMCCycleQueue_dyn > @@ -323,7 +323,7 @@ namespace queue { struct traits_VyukovMPMCCycleQueue_dyn_michaelAlloc : public cds::container::vyukov_queue::traits { - typedef cds::opt::v::dynamic_buffer< int, memory::MichaelAllocator > buffer; + typedef cds::opt::v::uninitialized_dynamic_buffer< int, memory::MichaelAllocator > buffer; }; class VyukovMPMCCycleQueue_dyn_michaelAlloc : public cds::container::VyukovMPMCCycleQueue< Value, traits_VyukovMPMCCycleQueue_dyn_michaelAlloc > diff --git a/test/stress/stack/intrusive_stack_type.h b/test/stress/stack/intrusive_stack_type.h index 570116d9..ffcb3931 100644 --- a/test/stress/stack/intrusive_stack_type.h +++ b/test/stress/stack/intrusive_stack_type.h @@ -248,7 +248,7 @@ namespace istack { cds::intrusive::treiber_stack::make_traits < cds::intrusive::opt::hook< base_hook > , cds::opt::enable_elimination - , cds::opt::buffer< cds::opt::v::dynamic_buffer > + , cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer > > ::type {}; typedef cds::intrusive::TreiberStack< cds::gc::HP, T, traits_Elimination_dyn > Elimination_HP_dyn; @@ -268,7 +268,7 @@ namespace istack { cds::intrusive::treiber_stack::make_traits < cds::intrusive::opt::hook< base_hook > , cds::opt::enable_elimination - , cds::opt::buffer< cds::opt::v::dynamic_buffer > + , cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer > , cds::opt::stat > > ::type {}; diff --git a/test/stress/stack/stack_type.h b/test/stress/stack/stack_type.h index 43aee442..39d476d4 100644 --- a/test/stress/stack/stack_type.h +++ b/test/stress/stack/stack_type.h @@ -275,7 +275,7 @@ namespace stack { struct traits_Elimination_dyn: public cds::container::treiber_stack::make_traits < cds::opt::enable_elimination - , cds::opt::buffer< cds::opt::v::dynamic_buffer > + , cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer > > ::type {}; typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Elimination_dyn > Elimination_HP_dyn; @@ -294,7 +294,7 @@ namespace stack { cds::container::treiber_stack::make_traits < cds::opt::enable_elimination , cds::opt::stat > - , cds::opt::buffer< cds::opt::v::dynamic_buffer > + , cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer > > ::type {}; typedef cds::container::TreiberStack< cds::gc::HP, T, traits_Elimination_dyn_stat > Elimination_HP_dyn_stat; diff --git a/test/unit/pqueue/intrusive_mspqueue.cpp b/test/unit/pqueue/intrusive_mspqueue.cpp index 1c019943..c5e29c07 100644 --- a/test/unit/pqueue/intrusive_mspqueue.cpp +++ b/test/unit/pqueue/intrusive_mspqueue.cpp @@ -146,8 +146,8 @@ namespace { } }; - typedef cds::opt::v::dynamic_buffer< char > dyn_buffer_type; - typedef cds::opt::v::static_buffer< char, IntrusiveMSPQueue::c_nCapacity > static_buffer_type; + typedef cds::opt::v::initialized_dynamic_buffer< char > dyn_buffer_type; + typedef cds::opt::v::initialized_static_buffer< char, IntrusiveMSPQueue::c_nCapacity > static_buffer_type; TEST_F( IntrusiveMSPQueue, dynamic ) { diff --git a/test/unit/pqueue/mspqueue.cpp b/test/unit/pqueue/mspqueue.cpp index 1966883d..88ce0373 100644 --- a/test/unit/pqueue/mspqueue.cpp +++ b/test/unit/pqueue/mspqueue.cpp @@ -162,8 +162,8 @@ namespace { } }; - typedef cds::opt::v::dynamic_buffer< char > dyn_buffer_type; - typedef cds::opt::v::static_buffer< char, MSPQueue::c_nCapacity > static_buffer_type; + typedef cds::opt::v::initialized_dynamic_buffer< char > dyn_buffer_type; + typedef cds::opt::v::initialized_static_buffer< char, MSPQueue::c_nCapacity > static_buffer_type; TEST_F( MSPQueue, dynamic ) { diff --git a/test/unit/queue/intrusive_tsigas_queue.cpp b/test/unit/queue/intrusive_tsigas_queue.cpp index 2c261bca..e53e8ae1 100644 --- a/test/unit/queue/intrusive_tsigas_queue.cpp +++ b/test/unit/queue/intrusive_tsigas_queue.cpp @@ -71,7 +71,7 @@ namespace { { struct traits : public cds::intrusive::tsigas_queue::traits { - typedef cds::opt::v::static_buffer< int, c_Capacity > buffer; + typedef cds::opt::v::initialized_static_buffer< int, c_Capacity > buffer; typedef IntrusiveTsigasQueue::disposer disposer; }; @@ -83,7 +83,7 @@ namespace { TEST_F( IntrusiveTsigasQueue, dynamic_buffer ) { typedef typename cds::intrusive::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::dynamic_buffer< int >> + cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int >> ,cds::opt::item_counter< cds::atomicity::item_counter > ,cds::opt::back_off< cds::backoff::pause > ,cds::intrusive::opt::disposer< disposer > @@ -98,7 +98,7 @@ namespace { { struct traits : public cds::intrusive::tsigas_queue::traits { - typedef cds::opt::v::static_buffer< int, c_Capacity > buffer; + typedef cds::opt::v::initialized_static_buffer< int, c_Capacity > buffer; typedef IntrusiveTsigasQueue::disposer disposer; enum { padding = 16 | cds::opt::padding_tiny_data_only }; }; diff --git a/test/unit/queue/intrusive_vyukov_queue.cpp b/test/unit/queue/intrusive_vyukov_queue.cpp index 71d48da2..c1147fd9 100644 --- a/test/unit/queue/intrusive_vyukov_queue.cpp +++ b/test/unit/queue/intrusive_vyukov_queue.cpp @@ -71,7 +71,7 @@ namespace { { struct traits : public cds::intrusive::vyukov_queue::traits { - typedef cds::opt::v::static_buffer< int, c_Capacity > buffer; + typedef cds::opt::v::uninitialized_static_buffer< int, c_Capacity > buffer; typedef IntrusiveVyukovQueue::disposer disposer; }; @@ -83,7 +83,7 @@ namespace { TEST_F( IntrusiveVyukovQueue, dynamic_buffer ) { typedef typename cds::intrusive::vyukov_queue::make_traits< - cds::opt::buffer< cds::opt::v::dynamic_buffer< int >> + cds::opt::buffer< cds::opt::v::uninitialized_dynamic_buffer< int >> ,cds::opt::item_counter< cds::atomicity::item_counter > ,cds::opt::back_off< cds::backoff::pause > ,cds::intrusive::opt::disposer< disposer > @@ -98,7 +98,7 @@ namespace { { struct traits : public cds::intrusive::vyukov_queue::traits { - typedef cds::opt::v::static_buffer< int, c_Capacity > buffer; + typedef cds::opt::v::uninitialized_static_buffer< int, c_Capacity > buffer; typedef IntrusiveVyukovQueue::disposer disposer; enum { padding = 16 | cds::opt::padding_tiny_data_only }; }; diff --git a/test/unit/queue/tsigas_queue.cpp b/test/unit/queue/tsigas_queue.cpp index 6ab9b689..dcfe3682 100644 --- a/test/unit/queue/tsigas_queue.cpp +++ b/test/unit/queue/tsigas_queue.cpp @@ -50,7 +50,7 @@ namespace { { struct traits: public cds::container::tsigas_queue::traits { - typedef cds::opt::v::static_buffer buffer; + typedef cds::opt::v::initialized_static_buffer buffer; }; typedef cds::container::TsigasCycleQueue< int, traits > test_queue; @@ -63,7 +63,7 @@ namespace { typedef cds::container::TsigasCycleQueue< int, cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::static_buffer> + cds::opt::buffer< cds::opt::v::initialized_static_buffer> , cds::opt::item_counter< cds::atomicity::item_counter> >::type > test_queue; @@ -76,7 +76,7 @@ namespace { { struct traits : public cds::container::tsigas_queue::traits { - typedef cds::opt::v::dynamic_buffer buffer; + typedef cds::opt::v::initialized_dynamic_buffer buffer; }; typedef cds::container::TsigasCycleQueue< int, traits > test_queue; @@ -88,7 +88,7 @@ namespace { { typedef cds::container::TsigasCycleQueue< int, cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::dynamic_buffer> + cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer> , cds::opt::item_counter< cds::atomicity::item_counter> >::type > test_queue; @@ -101,7 +101,7 @@ namespace { { struct traits : public cds::container::tsigas_queue::traits { - typedef cds::opt::v::dynamic_buffer buffer; + typedef cds::opt::v::initialized_dynamic_buffer buffer; enum { padding = 16 }; }; typedef cds::container::TsigasCycleQueue< int, traits > test_queue; diff --git a/test/unit/queue/vyukov_mpmc_queue.cpp b/test/unit/queue/vyukov_mpmc_queue.cpp index c9aa9c17..f4476a03 100644 --- a/test/unit/queue/vyukov_mpmc_queue.cpp +++ b/test/unit/queue/vyukov_mpmc_queue.cpp @@ -50,7 +50,7 @@ namespace { { struct traits: public cds::container::vyukov_queue::traits { - typedef cds::opt::v::static_buffer buffer; + typedef cds::opt::v::uninitialized_static_buffer buffer; }; typedef cds::container::VyukovMPMCCycleQueue< int, traits > test_queue; @@ -63,7 +63,7 @@ namespace { typedef cds::container::VyukovMPMCCycleQueue< int, cds::container::vyukov_queue::make_traits< - cds::opt::buffer< cds::opt::v::static_buffer> + cds::opt::buffer< cds::opt::v::uninitialized_static_buffer> , cds::opt::item_counter< cds::atomicity::item_counter> >::type > test_queue; @@ -76,7 +76,7 @@ namespace { { struct traits : public cds::container::vyukov_queue::traits { - typedef cds::opt::v::dynamic_buffer buffer; + typedef cds::opt::v::uninitialized_dynamic_buffer buffer; }; typedef cds::container::VyukovMPMCCycleQueue< int, traits > test_queue; @@ -88,7 +88,7 @@ namespace { { typedef cds::container::VyukovMPMCCycleQueue< int, cds::container::vyukov_queue::make_traits< - cds::opt::buffer< cds::opt::v::dynamic_buffer> + cds::opt::buffer< cds::opt::v::uninitialized_dynamic_buffer> , cds::opt::item_counter< cds::atomicity::item_counter> >::type > test_queue; @@ -101,7 +101,7 @@ namespace { { struct traits : public cds::container::vyukov_queue::traits { - typedef cds::opt::v::dynamic_buffer buffer; + typedef cds::opt::v::uninitialized_dynamic_buffer buffer; enum { padding = 64 }; }; typedef cds::container::VyukovMPMCCycleQueue< int, traits > test_queue; diff --git a/test/unit/stack/intrusive_treiber_stack_dhp.cpp b/test/unit/stack/intrusive_treiber_stack_dhp.cpp index 7fe331de..57518166 100644 --- a/test/unit/stack/intrusive_treiber_stack_dhp.cpp +++ b/test/unit/stack/intrusive_treiber_stack_dhp.cpp @@ -204,7 +204,7 @@ namespace { ci::opt::gc > > - ,ci::opt::buffer< ci::opt::v::dynamic_buffer > + ,ci::opt::buffer< ci::opt::v::initialized_dynamic_buffer > >::type > stack_type; @@ -257,7 +257,7 @@ namespace { ci::opt::gc > > - ,ci::opt::buffer< ci::opt::v::dynamic_buffer > + ,ci::opt::buffer< ci::opt::v::initialized_dynamic_buffer > >::type > stack_type; @@ -276,7 +276,7 @@ namespace { ci::opt::gc > > - ,ci::opt::buffer< ci::opt::v::dynamic_buffer > + ,ci::opt::buffer< ci::opt::v::initialized_dynamic_buffer > , ci::opt::disposer< mock_disposer > >::type > stack_type; diff --git a/test/unit/stack/intrusive_treiber_stack_hp.cpp b/test/unit/stack/intrusive_treiber_stack_hp.cpp index 64e9859b..f01fda2b 100644 --- a/test/unit/stack/intrusive_treiber_stack_hp.cpp +++ b/test/unit/stack/intrusive_treiber_stack_hp.cpp @@ -211,7 +211,7 @@ namespace { ci::opt::gc > > - ,ci::opt::buffer< ci::opt::v::dynamic_buffer > + ,ci::opt::buffer< ci::opt::v::initialized_dynamic_buffer > >::type > stack_type; @@ -264,7 +264,7 @@ namespace { ci::opt::gc > > - ,ci::opt::buffer< ci::opt::v::dynamic_buffer > + ,ci::opt::buffer< ci::opt::v::initialized_dynamic_buffer > >::type > stack_type; @@ -283,7 +283,7 @@ namespace { ci::opt::gc > > - ,ci::opt::buffer< ci::opt::v::dynamic_buffer > + ,ci::opt::buffer< ci::opt::v::initialized_dynamic_buffer > , ci::opt::disposer< mock_disposer > >::type > stack_type; diff --git a/test/unit/stack/treiber_stack_dhp.cpp b/test/unit/stack/treiber_stack_dhp.cpp index a2abb8c8..d396fb2e 100644 --- a/test/unit/stack/treiber_stack_dhp.cpp +++ b/test/unit/stack/treiber_stack_dhp.cpp @@ -142,7 +142,7 @@ namespace { typedef cc::TreiberStack< gc_type, int , typename cc::treiber_stack::make_traits< cds::opt::enable_elimination - , cds::opt::buffer< cds::opt::v::dynamic_buffer > + , cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer > >::type > stack_type; @@ -168,7 +168,7 @@ namespace { enum { enable_elimination = true }; - typedef cds::opt::v::dynamic_buffer buffer; + typedef cds::opt::v::initialized_dynamic_buffer buffer; typedef cds::backoff::yield back_off; }; typedef cc::TreiberStack< gc_type, int, traits > stack_type; diff --git a/test/unit/stack/treiber_stack_hp.cpp b/test/unit/stack/treiber_stack_hp.cpp index 1ebba3f2..176caead 100644 --- a/test/unit/stack/treiber_stack_hp.cpp +++ b/test/unit/stack/treiber_stack_hp.cpp @@ -136,7 +136,7 @@ namespace { typedef cc::TreiberStack< gc_type, int , typename cc::treiber_stack::make_traits< cds::opt::enable_elimination - , cds::opt::buffer< cds::opt::v::dynamic_buffer > + , cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer > >::type > stack_type; @@ -162,7 +162,7 @@ namespace { enum { enable_elimination = true }; - typedef cds::opt::v::dynamic_buffer buffer; + typedef cds::opt::v::initialized_dynamic_buffer buffer; typedef cds::backoff::yield back_off; }; typedef cc::TreiberStack< gc_type, int, traits > stack_type; diff --git a/test/unit/striped-set/intrusive_boost_unordered_set.cpp b/test/unit/striped-set/intrusive_boost_unordered_set.cpp index 84d4ca4e..fd535e1e 100644 --- a/test/unit/striped-set/intrusive_boost_unordered_set.cpp +++ b/test/unit/striped-set/intrusive_boost_unordered_set.cpp @@ -50,9 +50,9 @@ namespace { }; template - struct dyn_buffer: public ci::opt::v::dynamic_buffer< T, Alloc > + struct dyn_buffer: public ci::opt::v::initialized_dynamic_buffer< T, Alloc > { - typedef ci::opt::v::dynamic_buffer< T, Alloc > base_class; + typedef ci::opt::v::initialized_dynamic_buffer< T, Alloc > base_class; public: template struct rebind { @@ -93,7 +93,7 @@ namespace { , bi::incremental > ,cds::intrusive::opt::hash< hash2 > - ,cds::intrusive::opt::buffer< cds::intrusive::opt::v::static_buffer< cds::any_type, 64 > > + ,cds::intrusive::opt::buffer< cds::intrusive::opt::v::initialized_static_buffer< cds::any_type, 64 > > ,cds::intrusive::opt::resizing_policy< ci::striped_set::single_bucket_size_threshold<256> > > set_type; @@ -156,7 +156,7 @@ namespace { , bi::incremental > ,cds::intrusive::opt::hash< hash2 > - ,cds::intrusive::opt::buffer< cds::intrusive::opt::v::static_buffer< cds::any_type, 64 > > + ,cds::intrusive::opt::buffer< cds::intrusive::opt::v::initialized_static_buffer< cds::any_type, 64 > > ,cds::intrusive::opt::resizing_policy< ci::striped_set::single_bucket_size_threshold<256> > > set_type; @@ -220,7 +220,7 @@ namespace { > ,ci::opt::mutex_policy< ci::striped_set::refinable<> > ,cds::intrusive::opt::hash< hash2 > - ,cds::intrusive::opt::buffer< cds::intrusive::opt::v::static_buffer< cds::any_type, 64 > > + ,cds::intrusive::opt::buffer< cds::intrusive::opt::v::initialized_static_buffer< cds::any_type, 64 > > ,cds::intrusive::opt::resizing_policy< ci::striped_set::single_bucket_size_threshold<256> > > set_type; @@ -286,7 +286,7 @@ namespace { > ,cds::intrusive::opt::hash< hash2 > ,ci::opt::mutex_policy< ci::striped_set::refinable<> > - ,cds::intrusive::opt::buffer< cds::intrusive::opt::v::static_buffer< cds::any_type, 64 > > + ,cds::intrusive::opt::buffer< cds::intrusive::opt::v::initialized_static_buffer< cds::any_type, 64 > > ,cds::intrusive::opt::resizing_policy< ci::striped_set::single_bucket_size_threshold<256> > > set_type; diff --git a/test/unit/tree/test_ellen_bintree_update_desc_pool.h b/test/unit/tree/test_ellen_bintree_update_desc_pool.h index 89edde7b..fafd2486 100644 --- a/test/unit/tree/test_ellen_bintree_update_desc_pool.h +++ b/test/unit/tree/test_ellen_bintree_update_desc_pool.h @@ -41,7 +41,7 @@ namespace cds_test { // update_desc pools struct pool_traits: public cds::memory::vyukov_queue_pool_traits { - typedef cds::opt::v::static_buffer< update_desc, 256 > buffer; + typedef cds::opt::v::uninitialized_static_buffer< update_desc, 256 > buffer; }; typedef cds::memory::vyukov_queue_pool< update_desc, pool_traits > pool_type; typedef cds::memory::lazy_vyukov_queue_pool< update_desc, pool_traits > lazy_pool_type; -- 2.34.1