cds/sync/monitor.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_SYNC_MONITOR_H
  32 #define CDSLIB_SYNC_MONITOR_H
  33
  34 #include <cds/details/defs.h>
  35
  36 namespace cds { namespace sync {
  37     /**
  38         @page cds_sync_monitor Synchronization monitor
  39         A <a href="http://en.wikipedia.org/wiki/Monitor_%28synchronization%29">monitor</a> is synchronization construct
  40         that allows threads to have both mutual exclusion and the ability to wait (block) for a certain condition to become true.
  41         Some blocking data structure algoritms like the trees require per-node locking.
  42         For huge trees containing millions of nodes it can be very inefficient to inject
  43         the lock object into each node. Moreover, some operating systems may not support
  44         the millions of system objects like mutexes per user process.
  45         The monitor strategy is intended to solve that problem.
  46         When the node should be locked, the monitor is called to allocate appropriate
  47         lock object for the node if needed, and to lock the node.
  48         The monitor strategy can significantly reduce the number of system objects
  49         required for data structure.
  50
  51         <b>Implemetations</b>
  52
  53         \p libcds contains several monitor implementations:
  54         - \p sync::injecting_monitor injects the lock object into each node.
  55             That mock monitor is designed for user-space locking primitive like
  56             \ref sync::spin_lock "spin-lock".
  57         - \p sync::pool_monitor is the monitor that allocates a lock object
  58             for a node from the pool when needed. When the node is unlocked
  59             the lock assigned to it is given back to the pool if no thread
  60             references to that node.
  61
  62         <b>How to use</b>
  63
  64         If you use a container from \p libcds that requires a monitor, you should just
  65         specify required monitor type in container's traits. Usually, the monitor
  66         is specified by \p traits::sync_monitor typedef, or by \p cds::opt::sync_monitor
  67         option for container's \p make_traits metafunction.
  68
  69         If you're developing a new container algorithm, you should know internal monitor
  70         interface:
  71         \code
  72         class Monitor {
  73         public:
  74             // Monitor's injection into the Node class
  75             template <typename Node>
  76             struct node_injection: public Node
  77             {
  78                 // Monitor data injecting into container's node
  79                 // ...
  80             };
  81             // Locks the node
  82             template <typename Node>
  83             void lock( Node& node );
  84             // Unlocks the node
  85             template <typename Node>
  86             void unlock( Node& node );
  87             // Scoped lock applyes RAII to Monitor
  88             template <typename Node>
  89             using scoped_lock = monitor_scoped_lock< pool_monitor, Node >;
  90         };
  91         \endcode
  92         Monitor's data must be injected into container's node as \p m_SyncMonitorInjection data member:
  93         \code
  94         template <typename SyncMonitor>
  95         struct my_node
  96         {
  97             // ...
  98             typename SyncMonitor::node_injection m_SyncMonitorInjection;
  99         };
 100         \endcode
 101         The monitor must be a member of your container:
 102         \code
 103         template <typename GC, typename T, typename Traits>
 104         class my_container {
 105             // ...
 106             typedef typename Traits::sync_monitor   sync_monitor;
 107             typedef my_node<sync_monitor> node_type;
 108             sync_monitor m_Monitor;
 109             //...
 110         };
 111         \endcode
 112     */
 113     /// Monitor scoped lock (RAII)
 114     /**
 115         Template arguments:
 116         - \p Monitor - monitor type
 117         - \p Node - node type
 118     */
 119     template <typename Monitor, typename Node>
 120     struct monitor_scoped_lock
 121     {
 122     public:
 123         typedef Monitor monitor_type;   ///< Monitor type
 124         typedef Node    node_type;      ///< Node type
 125     private:
 126         //@cond
 127         monitor_type&    m_Monitor; ///< Monitor
 128         node_type const& m_Node;    ///< Our locked node
 129         //@endcond
 130     public:
 131         /// Makes exclusive access to the node \p p by \p monitor
 132         monitor_scoped_lock( monitor_type& monitor, node_type const& p )
 133             : m_Monitor( monitor )
 134             , m_Node( p )
 135         {
 136             monitor.lock( p );
 137         }
 138         /// Unlocks the node
 139         ~monitor_scoped_lock()
 140         {
 141             m_Monitor.unlock( m_Node );
 142         }
 143     };
 144 }} // namespace cds::sync
 145 #endif // #ifndef CDSLIB_SYNC_MONITOR_H
 146