Added description of wait strategies for flat combining
authorkhizmax <libcds.dev@gmail.com>
Sun, 26 Jun 2016 06:27:43 +0000 (09:27 +0300)
committerkhizmax <libcds.dev@gmail.com>
Sun, 26 Jun 2016 06:27:43 +0000 (09:27 +0300)
cds/algo/flat_combining/kernel.h
cds/algo/flat_combining/wait_strategy.h
change.log
thanks

index f984375..1f24cc2 100644 (file)
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #ifndef CDSLIB_ALGO_FLAT_COMBINING_KERNEL_H
@@ -55,10 +55,10 @@ namespace cds { namespace algo {
         of a <i>publication list</i>. The publication list is a list of thread-local records
         of a size proportional to the number of threads that are concurrently accessing the shared object.
 
-        Each thread \p t accessing the structure to perform an invocation of some method \p m
+        Each thread \p t accessing the structure to perform an invocation of some method \p f()
         on the shared object executes the following sequence of steps:
         <ol>
-        <li>Write the invocation opcode and parameters (if any) of the method \p m to be applied
+        <li>Write the invocation opcode and parameters (if any) of the method \p f() to be applied
         sequentially to the shared object in the <i>request</i> field of your thread local publication
         record (there is no need to use a load-store memory barrier). The <i>request</i> field will later
         be used to receive the response. If your thread local publication record is marked as active
@@ -66,15 +66,15 @@ namespace cds { namespace algo {
         <li>Check if the global lock is taken. If so (another thread is an active combiner), spin on the <i>request</i>
         field waiting for a response to the invocation (one can add a yield at this point to allow other threads
         on the same core to run). Once in a while while spinning check if the lock is still taken and that your
-        record is active. If your record is inactive proceed to step 5. Once the response is available,
-        reset the request field to null and return the response.</li>
+        record is active (you may use any of \p wait_strategy instead of spinning). If your record is inactive proceed to step 5.
+        Once the response is available, reset the request field to null and return the response.</li>
         <li>If the lock is not taken, attempt to acquire it and become a combiner. If you fail,
         return to spinning in step 2.</li>
         <li>Otherwise, you hold the lock and are a combiner.
         <ul>
             <li>Increment the combining pass count by one.</li>
             <li>Execute a \p fc_apply() by traversing the publication list from the head,
-            combining all nonnull method call invocations, setting the <i>age</i> of each of these records
+            combining all non-null method call invocations, setting the <i>age</i> of each of these records
             to the current <i>count</i>, applying the combined method calls to the structure D, and returning
             responses to all the invocations. This traversal is guaranteed to be wait-free.</li>
             <li>If the <i>count</i> is such that a cleanup needs to be performed, traverse the publication
index c8ec6f8..f16c6d7 100644 (file)
@@ -56,58 +56,133 @@ namespace cds { namespace opt {
 namespace cds { namespace algo { namespace flat_combining {
 
     /// Wait strategies for \p flat_combining technique
+    /**
+        Wait strategy specifies how a thread waits until its request is performed by the combiner.
+        See \p wait_strategy::empty wait strategy to explain the interface.
+    */
     namespace wait_strategy {
 
         /// Empty wait strategy
+        /**
+            Empty wait strategy is just spinning on request field.
+            All functions are empty.
+        */
         struct empty
         {
-        //@cond
+            /// Metafunction for defining a publication record for flat combining technique
+            /**
+                Any wait strategy may expand the publication record for storing
+                its own private data.
+                \p PublicationRecord is the type specified by \p flat_combining::kernel.
+                - If the strategy has no thread-private data, it should typedef \p PublicationRecord
+                  as a return \p type of metafunction.
+                - Otherwise, if the strategy wants to store anything in thread-local data,
+                  it should expand \p PublicationRecord, for example:
+                  \code
+                  template <typename PublicationRecord>
+                  struct make_publication_record {
+                    struct type: public PublicationRecord
+                    {
+                        int strategy_data;
+                    };
+                  };
+                  \endcode
+            */
             template <typename PublicationRecord>
             struct make_publication_record {
-                typedef PublicationRecord type;
+                typedef PublicationRecord type; ///< Metafunction result
             };
 
+            /// Prepares the strategy
+            /**
+                This function is called before enter to waiting cycle.
+                Some strategies need to prepare its thread-local data in \p rec.
+
+                \p PublicationRecord is thread's publication record of type \p make_publication_record::type
+            */
             template <typename PublicationRecord>
-            void prepare( PublicationRecord& /*rec*/ )
-            {}
+            void prepare( PublicationRecord& rec )
+            {
+                CDS_UNUSED( rec );
+            }
+
+            /// Waits for the combiner
+            /**
+                The thread calls this function to wait for the combiner process
+                the request.
+                The function returns \p true if the thread was waked up by the combiner,
+                otherwise it should return \p false.
 
+                \p FCKernel is a \p flat_combining::kernel object,
+                \p PublicationRecord is thread's publication record of type \p make_publication_record::type
+            */
             template <typename FCKernel, typename PublicationRecord>
-            bool wait( FCKernel& /*fc*/, PublicationRecord& /*rec*/ )
+            bool wait( FCKernel& fc, PublicationRecord& rec )
             {
+                CDS_UNUSED( fc );
+                CDS_UNUSED( rec );
                 return false;
             }
 
+            /// Wakes up the thread
+            /**
+                The combiner calls \p %notify() when it has been processed the request.
+
+                \p FCKernel is a \p flat_combining::kernel object,
+                \p PublicationRecord is thread's publication record of type \p make_publication_record::type
+            */
             template <typename FCKernel, typename PublicationRecord>
-            void notify( FCKernel& /*fc*/, PublicationRecord& /*rec*/ )
-            {}
+            void notify( FCKernel& fc, PublicationRecord& rec )
+            {
+                CDS_UNUSED( fc );
+                CDS_UNUSED( rec );
+            }
 
+            /// Moves control to other thread
+            /**
+                This function is called when the thread becomes the combiner
+                but the request of the thread is already processed.
+                The strategy may call \p fc.wakeup_any() instructs the kernel
+                to wake up any pending thread.
+
+                \p FCKernel is a \p flat_combining::kernel object,
+            */
             template <typename FCKernel>
-            void wakeup( FCKernel& /*fc*/ )
-            {}
-        //@endcond
+            void wakeup( FCKernel& fc )
+            {
+                CDS_UNUSED( fc );
+            }
         };
 
         /// Back-off wait strategy
+        /**
+            Template argument \p Backoff specifies back-off strategy, default is cds::backoff::delay_of<2>
+        */
         template <typename BackOff = cds::backoff::delay_of<2>>
         struct backoff
         {
-        //@cond
-            typedef BackOff back_off;
+            typedef BackOff back_off;   ///< Back-off strategy
 
+            /// Incorporates back-off strategy into publication record
             template <typename PublicationRecord>
-            struct make_publication_record {
+            struct make_publication_record 
+            {
+                //@cond
                 struct type: public PublicationRecord
                 {
                     back_off bkoff;
                 };
+                //@endcond
             };
 
+            /// Resets back-off strategy in \p rec
             template <typename PublicationRecord>
             void prepare( PublicationRecord& rec )
             {
                 rec.bkoff.reset();
             }
 
+            /// Calls back-off strategy
             template <typename FCKernel, typename PublicationRecord>
             bool wait( FCKernel& /*fc*/, PublicationRecord& rec )
             {
@@ -115,14 +190,15 @@ namespace cds { namespace algo { namespace flat_combining {
                 return false;
             }
 
+            /// Does nothing
             template <typename FCKernel, typename PublicationRecord>
             void notify( FCKernel& /*fc*/, PublicationRecord& /*rec*/ )
             {}
 
+            /// Does nothing
             template <typename FCKernel>
             void wakeup( FCKernel& )
             {}
-        //@endcond
         };
 
         /// Wait strategy based on the single mutex and the condition variable
@@ -140,21 +216,25 @@ namespace cds { namespace algo { namespace flat_combining {
             std::condition_variable m_condvar;
 
             typedef std::unique_lock< std::mutex > unique_lock;
+        //@endcond
 
         public:
             enum {
-                c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds
+                c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds ///< Waiting duration
             };
 
+            /// Empty metafunction
             template <typename PublicationRecord>
             struct make_publication_record {
-                typedef PublicationRecord type;
+                typedef PublicationRecord type; ///< publication record type
             };
 
+            /// Does nothing
             template <typename PublicationRecord>
             void prepare( PublicationRecord& /*rec*/ )
             {}
 
+            /// Sleeps on condition variable waiting for notification from combiner
             template <typename FCKernel, typename PublicationRecord>
             bool wait( FCKernel& fc, PublicationRecord& rec )
             {
@@ -166,18 +246,19 @@ namespace cds { namespace algo { namespace flat_combining {
                 return false;
             }
 
+            /// Calls condition variable function \p notify_all()
             template <typename FCKernel, typename PublicationRecord>
             void notify( FCKernel& fc, PublicationRecord& rec )
             {
                 m_condvar.notify_all();
             }
 
+            /// Calls condition variable function \p notify_all()
             template <typename FCKernel>
             void wakeup( FCKernel& /*fc*/ )
             {
                 m_condvar.notify_all();
             }
-        //@endcond
         };
 
         /// Wait strategy based on the single mutex and thread-local condition variables
@@ -194,24 +275,31 @@ namespace cds { namespace algo { namespace flat_combining {
             std::mutex m_mutex;
 
             typedef std::unique_lock< std::mutex > unique_lock;
+        //@endcond
 
         public:
             enum {
-                c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds
+                c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds  ///< Waiting duration
             };
 
+            /// Incorporates a condition variable into \p PublicationRecord
             template <typename PublicationRecord>
             struct make_publication_record {
+                /// Metafunction result
                 struct type: public PublicationRecord
                 {
+                    //@cond
                     std::condition_variable m_condvar;
+                    //@endcond
                 };
             };
 
+            /// Does nothing
             template <typename PublicationRecord>
             void prepare( PublicationRecord& /*rec*/ )
             {}
 
+            /// Sleeps on condition variable waiting for notification from combiner
             template <typename FCKernel, typename PublicationRecord>
             bool wait( FCKernel& fc, PublicationRecord& rec )
             {
@@ -223,18 +311,19 @@ namespace cds { namespace algo { namespace flat_combining {
                 return false;
             }
 
+            /// Calls condition variable function \p notify_one()
             template <typename FCKernel, typename PublicationRecord>
             void notify( FCKernel& fc, PublicationRecord& rec )
             {
                 rec.m_condvar.notify_one();
             }
 
+            /// Calls \p fc.wakeup_any() to wake up any pending thread
             template <typename FCKernel>
             void wakeup( FCKernel& fc )
             {
                 fc.wakeup_any();
             }
-        //@endcond
         };
 
         /// Wait strategy where each thread has a mutex and a condition variable
@@ -247,25 +336,31 @@ namespace cds { namespace algo { namespace flat_combining {
         {
         //@cond
             typedef std::unique_lock< std::mutex > unique_lock;
-
+        //@endcond
         public:
             enum {
-                c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds
+                c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds   ///< Waiting duration
             };
 
+            /// Incorporates a condition variable and a mutex into \p PublicationRecord
             template <typename PublicationRecord>
             struct make_publication_record {
+                /// Metafunction result
                 struct type: public PublicationRecord
                 {
+                    //@cond
                     std::mutex              m_mutex;
                     std::condition_variable m_condvar;
+                    //@endcond
                 };
             };
 
+            /// Does nothing
             template <typename PublicationRecord>
             void prepare( PublicationRecord& /*rec*/ )
             {}
 
+            /// Sleeps on condition variable waiting for notification from combiner
             template <typename FCKernel, typename PublicationRecord>
             bool wait( FCKernel& fc, PublicationRecord& rec )
             {
@@ -277,18 +372,19 @@ namespace cds { namespace algo { namespace flat_combining {
                 return false;
             }
 
+            /// Calls condition variable function \p notify_one()
             template <typename FCKernel, typename PublicationRecord>
             void notify( FCKernel& /*fc*/, PublicationRecord& rec )
             {
                 rec.m_condvar.notify_one();
             }
 
+            /// Calls \p fc.wakeup_any() to wake up any pending thread
             template <typename FCKernel>
             void wakeup( FCKernel& fc )
             {
                 fc.wakeup_any();
             }
-        //@endcond
         };
 
     } // namespace wait_strategy
index fcf866e..fbfb992 100644 (file)
@@ -2,6 +2,8 @@
     General release
     - Changed: CMake is used for build libcds. Ancient build.sh is removed
     - Changed: unit and stress tests are migrated to googletest framework
+    - Added: wait strategies for flat combining technique. Based on
+      research of Marsel Galimullin and Nikolai Rapotkin.
     - Fixed: serious bug in MichaelSet::emplace() function
       New node was created twice from the arguments by move semantics. 
       However, move semantics may change internal state of the argument
diff --git a/thanks b/thanks
index 9747104..6e0d6cd 100644 (file)
--- a/thanks
+++ b/thanks
@@ -9,7 +9,9 @@ Kyle Hegeman (https://github.com/khegeman)
 Lily Tsai (https://github.com/tslilyai)\r
 Lucas Larsch\r
 Markus Elfring\r
+Marsel Galimullin\r
 Mykola Dimura\r
 Mike Krinkin (https://github.com/krinkinmu)\r
+Nikolai Rapotkin\r
 rwf (https://github.com/rfw)\r
 Tamas Lengyel\r