1 //////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost
4 // Software License, Version 1.0. (See accompanying file
5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 //
7 // See http://www.boost.org/libs/interprocess for documentation.
8 //
9 //////////////////////////////////////////////////////////////////////////////
10
11 #ifndef BOOST_INTERPROCESS_DETAIL_CONDITION_ALGORITHM_8A_HPP
12 #define BOOST_INTERPROCESS_DETAIL_CONDITION_ALGORITHM_8A_HPP
13
14 #ifndef BOOST_CONFIG_HPP
15 # include <boost/config.hpp>
16 #endif
17 #
18 #if defined(BOOST_HAS_PRAGMA_ONCE)
19 # pragma once
20 #endif
21
22 #include <boost/interprocess/detail/config_begin.hpp>
23 #include <boost/interprocess/detail/workaround.hpp>
24 #include <boost/interprocess/sync/scoped_lock.hpp>
25 #include <boost/interprocess/sync/detail/locks.hpp>
26 #include <limits>
27
28 namespace boost {
29 namespace interprocess {
30 namespace ipcdetail {
31
32 ////////////////////////////////////////////////////////////////////////
33 ////////////////////////////////////////////////////////////////////////
34 ////////////////////////////////////////////////////////////////////////
35 //
36 // Condition variable algorithm taken from pthreads-win32 discussion.
37 //
38 // The algorithm was developed by Alexander Terekhov in colaboration with
39 // Louis Thomas.
40 //
41 // Algorithm 8a / IMPL_SEM,UNBLOCK_STRATEGY == UNBLOCK_ALL
42 //
43 // semBlockLock - bin.semaphore
44 // semBlockQueue - semaphore
45 // mtxExternal - mutex or CS
46 // mtxUnblockLock - mutex or CS
47 // nWaitersGone - int
48 // nWaitersBlocked - int
49 // nWaitersToUnblock - int
50 //
51 // wait( timeout ) {
52 //
53 // [auto: register int result ] // error checking omitted
54 // [auto: register int nSignalsWasLeft ]
55 // [auto: register int nWaitersWasGone ]
56 //
57 // sem_wait( semBlockLock );
58 // nWaitersBlocked++;
59 // sem_post( semBlockLock );
60 //
61 // unlock( mtxExternal );
62 // bTimedOut = sem_wait( semBlockQueue,timeout );
63 //
64 // lock( mtxUnblockLock );
65 // if ( 0 != (nSignalsWasLeft = nWaitersToUnblock) ) {
66 // if ( bTimedOut ) { // timeout (or canceled)
67 // if ( 0 != nWaitersBlocked ) {
68 // nWaitersBlocked--;
69 // }
70 // else {
71 // nWaitersGone++; // count spurious wakeups.
72 // }
73 // }
74 // if ( 0 == --nWaitersToUnblock ) {
75 // if ( 0 != nWaitersBlocked ) {
76 // sem_post( semBlockLock ); // open the gate.
77 // nSignalsWasLeft = 0; // do not open the gate
78 // // below again.
79 // }
80 // else if ( 0 != (nWaitersWasGone = nWaitersGone) ) {
81 // nWaitersGone = 0;
82 // }
83 // }
84 // }
85 // else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or
86 // // spurious semaphore :-)
87 // sem_wait( semBlockLock );
88 // nWaitersBlocked -= nWaitersGone; // something is going on here
89 // // - test of timeouts? :-)
90 // sem_post( semBlockLock );
91 // nWaitersGone = 0;
92 // }
93 // unlock( mtxUnblockLock );
94 //
95 // if ( 1 == nSignalsWasLeft ) {
96 // if ( 0 != nWaitersWasGone ) {
97 // // sem_adjust( semBlockQueue,-nWaitersWasGone );
98 // while ( nWaitersWasGone-- ) {
99 // sem_wait( semBlockQueue ); // better now than spurious later
100 // }
101 // } sem_post( semBlockLock ); // open the gate
102 // }
103 //
104 // lock( mtxExternal );
105 //
106 // return ( bTimedOut ) ? ETIMEOUT : 0;
107 // }
108 //
109 // signal(bAll) {
110 //
111 // [auto: register int result ]
112 // [auto: register int nSignalsToIssue]
113 //
114 // lock( mtxUnblockLock );
115 //
116 // if ( 0 != nWaitersToUnblock ) { // the gate is closed!!!
117 // if ( 0 == nWaitersBlocked ) { // NO-OP
118 // return unlock( mtxUnblockLock );
119 // }
120 // if (bAll) {
121 // nWaitersToUnblock += nSignalsToIssue=nWaitersBlocked;
122 // nWaitersBlocked = 0;
123 // }
124 // else {
125 // nSignalsToIssue = 1;
126 // nWaitersToUnblock++;
127 // nWaitersBlocked--;
128 // }
129 // }
130 // else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION!
131 // sem_wait( semBlockLock ); // close the gate
132 // if ( 0 != nWaitersGone ) {
133 // nWaitersBlocked -= nWaitersGone;
134 // nWaitersGone = 0;
135 // }
136 // if (bAll) {
137 // nSignalsToIssue = nWaitersToUnblock = nWaitersBlocked;
138 // nWaitersBlocked = 0;
139 // }
140 // else {
141 // nSignalsToIssue = nWaitersToUnblock = 1;
142 // nWaitersBlocked--;
143 // }
144 // }
145 // else { // NO-OP
146 // return unlock( mtxUnblockLock );
147 // }
148 //
149 // unlock( mtxUnblockLock );
150 // sem_post( semBlockQueue,nSignalsToIssue );
151 // return result;
152 // }
153 ////////////////////////////////////////////////////////////////////////
154 ////////////////////////////////////////////////////////////////////////
155 ////////////////////////////////////////////////////////////////////////
156
157
158 // Required interface for ConditionMembers
159 // class ConditionMembers
160 // {
161 // typedef implementation_defined semaphore_type;
162 // typedef implementation_defined mutex_type;
163 // typedef implementation_defined integer_type;
164 //
165 // integer_type &get_nwaiters_blocked()
166 // integer_type &get_nwaiters_gone()
167 // integer_type &get_nwaiters_to_unblock()
168 // semaphore_type &get_sem_block_queue()
169 // semaphore_type &get_sem_block_lock()
170 // mutex_type &get_mtx_unblock_lock()
171 // };
172 //
173 // Must be initialized as following
174 //
175 // get_nwaiters_blocked() == 0
176 // get_nwaiters_gone() == 0
177 // get_nwaiters_to_unblock() == 0
178 // get_sem_block_queue() == initial count 0
179 // get_sem_block_lock() == initial count 1
180 // get_mtx_unblock_lock() (unlocked)
181 //
182 template<class ConditionMembers>
183 class condition_algorithm_8a
184 {
185 private:
186 condition_algorithm_8a();
187 ~condition_algorithm_8a();
188 condition_algorithm_8a(const condition_algorithm_8a &);
189 condition_algorithm_8a &operator=(const condition_algorithm_8a &);
190
191 typedef typename ConditionMembers::semaphore_type semaphore_type;
192 typedef typename ConditionMembers::mutex_type mutex_type;
193 typedef typename ConditionMembers::integer_type integer_type;
194
195 public:
196 template<class Lock>
197 static bool wait ( ConditionMembers &data, Lock &lock
198 , bool timeout_enabled, const boost::posix_time::ptime &abs_time);
199 static void signal(ConditionMembers &data, bool broadcast);
200 };
201
202 template<class ConditionMembers>
signal(ConditionMembers & data,bool broadcast)203 inline void condition_algorithm_8a<ConditionMembers>::signal(ConditionMembers &data, bool broadcast)
204 {
205 integer_type nsignals_to_issue;
206
207 {
208 scoped_lock<mutex_type> locker(data.get_mtx_unblock_lock());
209
210 if ( 0 != data.get_nwaiters_to_unblock() ) { // the gate is closed!!!
211 if ( 0 == data.get_nwaiters_blocked() ) { // NO-OP
212 //locker's destructor triggers data.get_mtx_unblock_lock().unlock()
213 return;
214 }
215 if (broadcast) {
216 data.get_nwaiters_to_unblock() += nsignals_to_issue = data.get_nwaiters_blocked();
217 data.get_nwaiters_blocked() = 0;
218 }
219 else {
220 nsignals_to_issue = 1;
221 data.get_nwaiters_to_unblock()++;
222 data.get_nwaiters_blocked()--;
223 }
224 }
225 else if ( data.get_nwaiters_blocked() > data.get_nwaiters_gone() ) { // HARMLESS RACE CONDITION!
226 data.get_sem_block_lock().wait(); // close the gate
227 if ( 0 != data.get_nwaiters_gone() ) {
228 data.get_nwaiters_blocked() -= data.get_nwaiters_gone();
229 data.get_nwaiters_gone() = 0;
230 }
231 if (broadcast) {
232 nsignals_to_issue = data.get_nwaiters_to_unblock() = data.get_nwaiters_blocked();
233 data.get_nwaiters_blocked() = 0;
234 }
235 else {
236 nsignals_to_issue = data.get_nwaiters_to_unblock() = 1;
237 data.get_nwaiters_blocked()--;
238 }
239 }
240 else { // NO-OP
241 //locker's destructor triggers data.get_mtx_unblock_lock().unlock()
242 return;
243 }
244 //locker's destructor triggers data.get_mtx_unblock_lock().unlock()
245 }
246 data.get_sem_block_queue().post(nsignals_to_issue);
247 }
248
249 template<class ConditionMembers>
250 template<class Lock>
wait(ConditionMembers & data,Lock & lock,bool tout_enabled,const boost::posix_time::ptime & abs_time)251 inline bool condition_algorithm_8a<ConditionMembers>::wait
252 ( ConditionMembers &data
253 , Lock &lock
254 , bool tout_enabled
255 , const boost::posix_time::ptime &abs_time
256 )
257 {
258 //Initialize to avoid warnings
259 integer_type nsignals_was_left = 0;
260 integer_type nwaiters_was_gone = 0;
261
262 data.get_sem_block_lock().wait();
263 ++data.get_nwaiters_blocked();
264 data.get_sem_block_lock().post();
265
266 //Unlock external lock and program for relock
267 lock_inverter<Lock> inverted_lock(lock);
268 scoped_lock<lock_inverter<Lock> > external_unlock(inverted_lock);
269
270 bool bTimedOut = tout_enabled
271 ? !data.get_sem_block_queue().timed_wait(abs_time)
272 : (data.get_sem_block_queue().wait(), false);
273
274 {
275 scoped_lock<mutex_type> locker(data.get_mtx_unblock_lock());
276 if ( 0 != (nsignals_was_left = data.get_nwaiters_to_unblock()) ) {
277 if ( bTimedOut ) { // timeout (or canceled)
278 if ( 0 != data.get_nwaiters_blocked() ) {
279 data.get_nwaiters_blocked()--;
280 }
281 else {
282 data.get_nwaiters_gone()++; // count spurious wakeups.
283 }
284 }
285 if ( 0 == --data.get_nwaiters_to_unblock() ) {
286 if ( 0 != data.get_nwaiters_blocked() ) {
287 data.get_sem_block_lock().post(); // open the gate.
288 nsignals_was_left = 0; // do not open the gate below again.
289 }
290 else if ( 0 != (nwaiters_was_gone = data.get_nwaiters_gone()) ) {
291 data.get_nwaiters_gone() = 0;
292 }
293 }
294 }
295 else if ( (std::numeric_limits<integer_type>::max)()/2
296 == ++data.get_nwaiters_gone() ) { // timeout/canceled or spurious semaphore :-)
297 data.get_sem_block_lock().wait();
298 data.get_nwaiters_blocked() -= data.get_nwaiters_gone(); // something is going on here - test of timeouts? :-)
299 data.get_sem_block_lock().post();
300 data.get_nwaiters_gone() = 0;
301 }
302 //locker's destructor triggers data.get_mtx_unblock_lock().unlock()
303 }
304
305 if ( 1 == nsignals_was_left ) {
306 if ( 0 != nwaiters_was_gone ) {
307 // sem_adjust( data.get_sem_block_queue(),-nwaiters_was_gone );
308 while ( nwaiters_was_gone-- ) {
309 data.get_sem_block_queue().wait(); // better now than spurious later
310 }
311 }
312 data.get_sem_block_lock().post(); // open the gate
313 }
314
315 //lock.lock(); called from unlocker destructor
316
317 return ( bTimedOut ) ? false : true;
318 }
319
320
321 template<class ConditionMembers>
322 class condition_8a_wrapper
323 {
324 //Non-copyable
325 condition_8a_wrapper(const condition_8a_wrapper &);
326 condition_8a_wrapper &operator=(const condition_8a_wrapper &);
327
328 ConditionMembers m_data;
329 typedef ipcdetail::condition_algorithm_8a<ConditionMembers> algo_type;
330
331 public:
332
condition_8a_wrapper()333 condition_8a_wrapper(){}
334
335 //Compiler-generated destructor is OK
336 //~condition_8a_wrapper(){}
337
get_members()338 ConditionMembers & get_members()
339 { return m_data; }
340
get_members() const341 const ConditionMembers & get_members() const
342 { return m_data; }
343
notify_one()344 void notify_one()
345 { algo_type::signal(m_data, false); }
346
notify_all()347 void notify_all()
348 { algo_type::signal(m_data, true); }
349
350 template <typename L>
wait(L & lock)351 void wait(L& lock)
352 {
353 if (!lock)
354 throw lock_exception();
355 algo_type::wait(m_data, lock, false, boost::posix_time::ptime());
356 }
357
358 template <typename L, typename Pr>
wait(L & lock,Pr pred)359 void wait(L& lock, Pr pred)
360 {
361 if (!lock)
362 throw lock_exception();
363
364 while (!pred())
365 algo_type::wait(m_data, lock, false, boost::posix_time::ptime());
366 }
367
368 template <typename L>
timed_wait(L & lock,const boost::posix_time::ptime & abs_time)369 bool timed_wait(L& lock, const boost::posix_time::ptime &abs_time)
370 {
371 if (!lock)
372 throw lock_exception();
373 return algo_type::wait(m_data, lock, true, abs_time);
374 }
375
376 template <typename L, typename Pr>
timed_wait(L & lock,const boost::posix_time::ptime & abs_time,Pr pred)377 bool timed_wait(L& lock, const boost::posix_time::ptime &abs_time, Pr pred)
378 {
379 if (!lock)
380 throw lock_exception();
381 while (!pred()){
382 if (!algo_type::wait(m_data, lock, true, abs_time))
383 return pred();
384 }
385 return true;
386 }
387 };
388
389 } //namespace ipcdetail
390 } //namespace interprocess
391 } //namespace boost
392
393 #include <boost/interprocess/detail/config_end.hpp>
394
395 #endif //BOOST_INTERPROCESS_DETAIL_CONDITION_ALGORITHM_8A_HPP
396