From: khizmax Date: Fri, 24 Oct 2014 09:10:37 +0000 (+0400) Subject: add "insert item troubleshooting" to docs X-Git-Tag: v2.0.0~173 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=commitdiff_plain;h=1c4e300439ce894a5a861c6db8ac04d6b1a90318 add "insert item troubleshooting" to docs --- diff --git a/cds/container/impl/lazy_kvlist.h b/cds/container/impl/lazy_kvlist.h index d736e620..e593b827 100644 --- a/cds/container/impl/lazy_kvlist.h +++ b/cds/container/impl/lazy_kvlist.h @@ -427,6 +427,8 @@ namespace cds { namespace container { This can be useful if complete initialization of object of \p mapped_type is heavyweight and it is preferable that the initialization should be completed only if inserting is successful. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template bool insert_key( const K& key, Func func ) @@ -471,11 +473,11 @@ namespace cds { namespace container { however, \p func must guarantee that during changing no any other modifications could be made on this item by concurrent threads. - You may pass \p func argument by reference using \p std::ref. - Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key already is in the list. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template std::pair ensure( const K& key, Func f ) diff --git a/cds/container/impl/lazy_list.h b/cds/container/impl/lazy_list.h index 427dcaf2..dfed21d8 100644 --- a/cds/container/impl/lazy_list.h +++ b/cds/container/impl/lazy_list.h @@ -389,6 +389,8 @@ namespace cds { namespace container { This can be useful if complete initialization of object of \p value_type is heavyweight and it is preferable that the initialization should be completed only if inserting is successful. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template bool insert( Q const& key, Func func ) @@ -431,11 +433,11 @@ namespace cds { namespace container { The functor may change non-key fields of the \p item; however, \p func must guarantee that during changing no any other modifications could be made on this item by concurrent threads. - You may pass \p func argument by reference using \p std::ref - Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key already is in the list. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template std::pair ensure( Q const& key, Func f ) diff --git a/cds/container/impl/michael_kvlist.h b/cds/container/impl/michael_kvlist.h index 09623b03..7dce75f5 100644 --- a/cds/container/impl/michael_kvlist.h +++ b/cds/container/impl/michael_kvlist.h @@ -395,6 +395,8 @@ namespace cds { namespace container { This can be useful if complete initialization of object of \p mapped_type is heavyweight and it is preferable that the initialization should be completed only if inserting is successful. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template bool insert_key( const K& key, Func func ) @@ -432,6 +434,8 @@ namespace cds { namespace container { Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key already is in the list. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template std::pair ensure( const K& key, Func f ) diff --git a/cds/container/impl/michael_list.h b/cds/container/impl/michael_list.h index d600a9e1..17224e31 100644 --- a/cds/container/impl/michael_list.h +++ b/cds/container/impl/michael_list.h @@ -352,6 +352,8 @@ namespace cds { namespace container { The method can be useful if complete initialization of object of \p value_type is heavyweight and it is preferable that the initialization should be completed only if inserting is successful. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template bool insert( Q const& key, Func func ) @@ -387,6 +389,8 @@ namespace cds { namespace container { Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key already is in the list. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template std::pair ensure( Q const& key, Func func ) diff --git a/cds/container/lazy_kvlist_rcu.h b/cds/container/lazy_kvlist_rcu.h index f1b9afe8..3456a29c 100644 --- a/cds/container/lazy_kvlist_rcu.h +++ b/cds/container/lazy_kvlist_rcu.h @@ -411,6 +411,8 @@ namespace cds { namespace container { it is preferable that the initialization should be completed only if inserting is successful. The function makes RCU lock internally. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template bool insert_key( const K& key, Func func ) @@ -457,13 +459,13 @@ namespace cds { namespace container { however, \p func must guarantee that during changing no any other modifications could be made on this item by concurrent threads. - You may pass \p func argument by reference using \p std::ref - The function makes RCU lock internally. Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key already is in the list. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template std::pair ensure( const K& key, Func f ) diff --git a/cds/container/lazy_list_rcu.h b/cds/container/lazy_list_rcu.h index 6b2ac2f2..5e694a7b 100644 --- a/cds/container/lazy_list_rcu.h +++ b/cds/container/lazy_list_rcu.h @@ -385,6 +385,8 @@ namespace cds { namespace container { it is preferable that the initialization should be completed only if inserting is successful. The function makes RCU lock internally. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template bool insert( Q const& key, Func func ) @@ -436,6 +438,8 @@ namespace cds { namespace container { Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key already is in the list. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template std::pair ensure( Q const& key, Func f ) diff --git a/cds/container/michael_kvlist_rcu.h b/cds/container/michael_kvlist_rcu.h index 04bc71a7..b7fc1ad2 100644 --- a/cds/container/michael_kvlist_rcu.h +++ b/cds/container/michael_kvlist_rcu.h @@ -382,6 +382,8 @@ namespace cds { namespace container { it is preferable that the initialization should be completed only if inserting is successful. The function makes RCU lock internally. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template bool insert_key( const K& key, Func func ) @@ -423,6 +425,8 @@ namespace cds { namespace container { Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key already is in the list. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template std::pair ensure( const K& key, Func f ) diff --git a/cds/container/michael_list_rcu.h b/cds/container/michael_list_rcu.h index 071b976b..65a8351e 100644 --- a/cds/container/michael_list_rcu.h +++ b/cds/container/michael_list_rcu.h @@ -356,6 +356,8 @@ namespace cds { namespace container { it is preferable that the initialization should be completed only if inserting is successful. The function makes RCU lock internally. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template bool insert( Q const& key, Func func ) @@ -393,6 +395,8 @@ namespace cds { namespace container { Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key already is in the list. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template std::pair ensure( Q const& key, Func f ) diff --git a/cds/intrusive/details/base.h b/cds/intrusive/details/base.h index 73c653de..5bf0b389 100644 --- a/cds/intrusive/details/base.h +++ b/cds/intrusive/details/base.h @@ -31,7 +31,138 @@ namespace cds { struct tag1; cds::intrusive::treiber_stack::node< cds::gc::HP, tag > \endcode - If no tag is specified åðó default \p cds::opt::none will be used. + If no tag is specified the default \p cds::opt::none will be used. + + \anchor cds_intrusive_item_creating + \par Inserting items + Many intrusive and non-intrusive (standard-like) containers in the library have the member functions + that take an functor argument to initialize the inserted item after it has been successfully inserted, + for example: + \code + template + bool insert( Q& key, Func f ); + + template + std::pair ensure( Q& key, Func f ); + \endcode + The first member function calls \p f functor iif an new item has been inserted. The functor takes two parameter: a reference to inserted item and + \p key. + + The second member function, \p ensure, allows to insert a new item to the container if \p key is not found, or to find the item with \p key and + to perform some action with it. The \p f signature is: + \code + void f( bool bNew, item_type& item, Q& key ); + \endcode + where \p bNew is a flag to indicate whether \p item is a new created node or not. + + Such functions should be used with caution in multi-threaded environment + since they can cause races. The library does not synchronize access + to container's items, so many threads can access to one item simultaneously. + For example, for \p insert member function the following race is possible: + \code + // Suppose, Foo is a complex structure with int key field + SomeContainer q; + + Thread 1 Thread 2 + + q.insert( Foo(5), q.find( 5, []( Foo& item ) { + []( Foo& item ){ // access to item fields + // complex initialization ... + item.f1 = ...; }); + ... + }); + \endcode + Execute sequence: + \code + Find 5 in the container. + Key 5 is not found + Create a new item Find key 5 + with calling Foo(5) ctor + Insert the new item + The key 5 is found - + call the functor (!) + Perform complex + initialization - + call the functor + \endcode + (!): Thread 2 found the key and call its functor on incomplete initialized item. + Simultaneous access to the item also is possible. In this case Thread 1 is + initializing the item, thread 2 is reading (or writing) the item's fields. + In any case, Thread 2 can read uninitialized or incomplete initialized fields. + + \p ensure member function race. Suppose, thread 1 and thread 2 perform + the + following code: + \code + q.ensure( 5, []( bool bNew, Foo& item, int arg ) + { + // bNew: true if the new element has been created + // false otherwise + if ( bNew ) { + // initialize item + item.f1=...; + //... + } + else { + // do some work + if ( !item.f1 ) + item.f1 = ...; + else { + //... + } + //... + } + } + ); + \endcode + Execute sequence: + \code + Thread 1 Thread 2 + key 5 not found + insert new item Foo(5) Find 5 + Key 5 found + call the functor with + bNew = false (!) + call the functor with + bNew = true + \endcode + (!): Thread 2 executes its functor on incomplete initialized item. + + To protect your code from such races you can use some item-level synchronization, + for example: + \code + struct Foo { + spinlock lock; // item-level lock + bool initialized = false; // initialization flag + // other fields + // .... + }; + + q.ensure( 5, []( bool bNew, Foo& item, int arg ) + { + // Lock access to the item + std::unique_lock( item.lock ); + + if ( !item.initialized ) { + // initialize item + item.f1=...; + //... + item.initialized = true; // mark the item as initialized + } + else { + // do some work + if ( !item.f1 ) + item.f1 = ...; + else { + //... + } + //... + } + } + ); + \endcode + If the item-level synchronization is not suitable, you should not use any inserting member function + with post-insert functor argument. \anchor cds_intrusive_item_destroying \par Destroying items diff --git a/cds/intrusive/impl/lazy_list.h b/cds/intrusive/impl/lazy_list.h index 273a14c8..4e29b4cc 100644 --- a/cds/intrusive/impl/lazy_list.h +++ b/cds/intrusive/impl/lazy_list.h @@ -537,8 +537,9 @@ namespace cds { namespace intrusive { \endcode where \p val is the item inserted. While the functor \p f is working the item \p val is locked. - The user-defined functor is called only if the inserting is success and may be passed by reference - using \p std::ref + The user-defined functor is called only if the inserting is success. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template bool insert( value_type& val, Func f ) @@ -566,11 +567,11 @@ namespace cds { namespace intrusive { The functor may change non-key fields of the \p item. While the functor \p f is working the item \p item is locked. - You may pass \p func argument by reference using \p std::ref. - Returns std::pair where \p first is \p true if operation is successfull, \p second is \p true if new item has been added or \p false if the item with \p key already is in the list. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template std::pair ensure( value_type& val, Func func ) diff --git a/cds/intrusive/impl/michael_list.h b/cds/intrusive/impl/michael_list.h index 8c2980ba..2922cb6a 100644 --- a/cds/intrusive/impl/michael_list.h +++ b/cds/intrusive/impl/michael_list.h @@ -517,6 +517,8 @@ namespace cds { namespace intrusive { where \p val is the item inserted. User-defined functor \p f should guarantee that during changing \p val no any other changes could be made on this list's item by concurrent threads. The user-defined functor is called only if the inserting is success. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template bool insert( value_type& val, Func f ) @@ -547,6 +549,8 @@ namespace cds { namespace intrusive { Returns std::pair where \p first is \p true if operation is successfull, \p second is \p true if new item has been added or \p false if the item with \p key already is in the list. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template std::pair ensure( value_type& val, Func func ) diff --git a/cds/intrusive/lazy_list_rcu.h b/cds/intrusive/lazy_list_rcu.h index 48dbd604..4ac0a863 100644 --- a/cds/intrusive/lazy_list_rcu.h +++ b/cds/intrusive/lazy_list_rcu.h @@ -444,8 +444,9 @@ namespace cds { namespace intrusive { \endcode where \p val is the item inserted. While the functor \p f is working the item \p val is locked. - The user-defined functor is called only if the inserting is success and may be passed by reference - using \p std::ref. + The user-defined functor is called only if the inserting is success. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template bool insert( value_type& val, Func f ) @@ -475,11 +476,11 @@ namespace cds { namespace intrusive { The functor may change non-key fields of the \p item. While the functor \p f is calling the item \p item is locked. - You may pass \p func argument by reference using \p std::ref. - Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key already is in the list. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template diff --git a/cds/intrusive/michael_list_rcu.h b/cds/intrusive/michael_list_rcu.h index 4ff82b57..1cd4b662 100644 --- a/cds/intrusive/michael_list_rcu.h +++ b/cds/intrusive/michael_list_rcu.h @@ -340,6 +340,8 @@ namespace cds { namespace intrusive { The user-defined functor is called only if the inserting is success. The function makes RCU lock internally. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template bool insert( value_type& val, Func f ) @@ -374,6 +376,8 @@ namespace cds { namespace intrusive { already is in the list. The function makes RCU lock internally. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template std::pair ensure( value_type& val, Func func )