I believe there is a mistake in the 'details/lwm_gcc.hpp' and 
'details/lwm_linux.hpp' (and possibly the other lightweight_mutex 
implementation as well -- I haven't looked at them).
 
In both of these files we have a counter (m_.a_) that is initialized to 1.  
The lock routine is implemented as follows:
 
while( !__exchange_and_add(&m_.a_, -1) ){
  __atomic_add(&m_.a_, 1);
  sched_yield();
}
 
The unlock as:
__atomic_add(&m_.a_, 1);
 
This works if there are only two contenders for the lock.  It can fail if 
there are three or more:
 
1-  Thread one takes the lock, putting the counter at 0.
2-  Thread two does the __exchange_and_add, fails the test, and then its time 
time slice expires before the __atomic_add, leaving the counter at -1.
3-  Thread three also takes the lock (because !-1 is false).
 
A simple solution is to initialize the counter to zero and replace the above 
lock by:
 
while( __exchange_and_add(&m_.a_, 1) ){
  __atomic_add(&m_.a_, -1);
  sched_yield();
}
 
and the unlock by:
__atomic_add(&m_.a_, -1);
 
This would result in:
1-  Thread one takes the lock, putting the counter at 1.
2-  Thread two does the __exchange_and_add, fails the test, and then its time 
slice expires before it can do the __atomic_add, leaving the counter at 2.
3-  Thread cannot take the the lock (because 2 is true).
 
- -T
 
- -- 
 Tyson Whitehead  (-twhitehe@uwo.ca -- WSC-)
 Computer Engineer                        Dept. of Applied Mathematics,
 Graduate Student- Applied Mathematics    University of Western Ontario,
 GnuPG Key ID# 0x8A2AB5D8                 London, Ontario, Canada


---------------------------------------------------------------------------------------------------------------------

Tyson Whitehead wrote:
>  I believe there is a mistake in the 'details/lwm_gcc.hpp' and 
'details/lwm_linux.hpp' (and possibly the other lightweight_mutex 
implementation as well -- I haven't looked at them). 

 
I am not sure what the status of these are.  Are other components
supposed to be using these?  In addition to what you mentioned, they're
broken in other ways:
 
>  In both of these files we have a counter (m_.a_) that is initialized to 1.  
The lock routine is implemented as follows:
while( !__exchange_and_add(&m_.a_, -1) ){
  __atomic_add(&m_.a_, 1);
  sched_yield(); 

 
If a low priority thread is preempted by a high priority thread
immediately before __atomic_add, and the high priority thread is
attempting to grab the spinlock, deadlock is acheived, despite the
sched_yield().
 
I think that spinlocks should not be used in a way other than as an
optimization for the non-contended case in an algorithm with fallback to
a real synchronization primative.  I think it is a bug to do otherwise
on most non-realtime systems.
 
Aaron W. LaFramboise

-------------------------------------------------------------------------------------------------------------------------

Aaron W. LaFramboise wrote:
>  I am not sure what the status of these are.  Are other components
supposed to be using these? 

 
I came upon them when I was checking out the smart pointers implementation.  
Grepping the source seems to indicate 'lightweight_mutex.hpp' is only used by  
the smart pointers (only included by 'quick_allocator.hpp' and 
'shared_count.hpp') under multithreaded conditions.
 
>  In addition to what you mentioned, they're broken in other ways: 
If a low priority thread is preempted by a high priority thread
immediately before __atomic_add, and the high priority thread is
attempting to grab the spinlock, deadlock is acheived, despite the
sched_yield(). 

 
I missed that one.  You're right though, and not only that, but the 
sched_yield manpage states (I'm assuming this applies to threads -- threads 
in Linux are actually processes -- right?):
 
"Note: If the current process is the only process in the highest priority list 
at that time, this process will continue to run after a  call to 
sched_yield."
 
The implementer seemed to be aware there could be priority problems though.  
The relevant comments in 'lightweight_mutex.hpp' are:
 
//  * Used by the smart pointer library
//  * Performance oriented
//  * Header-only implementation
//  * Small memory footprint
//  * Not a general purpose mutex, use boost::mutex, CRITICAL_SECTION or
//    pthread_mutex instead.
//  * Never spin in a tight lock/do-something/unlock loop, since
//    lightweight_mutex does not guarantee fairness.
//  * Never keep a lightweight_mutex locked for long periods.
//
//  The current implementation can use a pthread_mutex, a CRITICAL_SECTION,
//  or a platform-specific spinlock.
//
//  You can force a particular implementation by defining
//  BOOST_LWM_USE_PTHREADS,
//  BOOST_LWM_USE_CRITICAL_SECTION, or 
//  BOOST_LWM_USE_SPINLOCK.
//
//  If neither macro has been defined, the default is to use a spinlock on
//  Win32, and a pthread_mutex otherwise.
//
//  Note that a spinlock is not a general synchronization primitive. In
//  particular, it is not guaranteed to be a memory barrier, and it is
//  possible to "livelock" if a lower-priority thread has acquired the
//  spinlock but a higher-priority thread is spinning trying to acquire the
//  same lock.
//
//  For these reasons, spinlocks have been disabled by default except on
//  Windows, where a spinlock can be several orders of magnitude faster than a
//  CRITICAL_SECTION.
 
The current Win32 doesn't have the counter problems, and claims to be able to 
yield to lower priority threads, so it should be okay.  The relevant lock 
routine is (m_.l_ is initialized to 0):
 
while( InterlockedExchange(&m_.l_, 1) ){
  // Note: changed to Sleep(1) from Sleep(0).
  // According to MSDN, Sleep(0) will never yield
  // to a lower-priority thread, whereas Sleep(1)
  // will. Performance seems not to be affected.
  Sleep(1);
}
 
The unlock routine is:
InterlockedExchange(&m_.l_, 0);
 
- -T
 
- -- 
 Tyson Whitehead  (-twhitehe@uwo.ca -- WSC-)
 Computer Engineer                        Dept. of Applied Mathematics,
 Graduate Student- Applied Mathematics    University of Western Ontario,
 GnuPG Key ID# 0x8A2AB5D8                 London, Ontario, Canada

-------------------------------------------------------------------------------------------

Tyson Whitehead wrote:
>  The current Win32 doesn't have the counter problems, and claims to be able to 
yield to lower priority threads, so it should be okay.  The relevant lock 
routine is (m_.l_ is initialized to 0):
while( InterlockedExchange(&m_.l_, 1) ){
  // Note: changed to Sleep(1) from Sleep(0).
  // According to MSDN, Sleep(0) will never yield
  // to a lower-priority thread, whereas Sleep(1)
  // will. Performance seems not to be affected.
  Sleep(1);
} 

 
For what its worth, while it avoids deadlocking problems, this code is
also wrong.
 
Synchronization code should never sleep.  That code above will actually
sleep for the minimum amount of time Windows allows, which is usually
10ms.  I measured the performance of this spinlock a while back when
improvements to GCC's Windows mutexes were being discussed on the MinGW
lists, and in some cases where there is substanctial contention over
short-lived locks, the performance degradation is quite unacceptable.
Certain naïve benchmarks might not notice, though, because during the
period waiters are sleeping, the lock will be accessable.
 
I think the code above could lead to severe slowdowns in some usage
cases, and could lead to difficult to diagnose intermittant 'blips' of
bad performance in others.
 
In any case, my point is that spinlocks are always going to be wrong in
these sorts of situations unless coupled with some other primative.  In
fact, spinning at all is usually the wrong thing to do.  On single CPU
systems, it is always a waste of precious time.  On multi CPU systems,
it can cause very undesirable memory bus slowdowns.
 
The best general locking strategy I have seen--which is used by Linux
futexes and GCC for Windows' new locks--is where a normal scheduler
locking primative is wrapped by a quick userspace atomic operation to
avoid locking in the noncontended case.  The downside is that, on
Windows for example, this will require 8 bytes of storage.  I'm not sure
how shared_ptr uses mutexes, but this might not be acceptable.
 
These spinlocks need to be fixed.  Is anyone working on this?
 
Aaron W. LaFramboise
-------------------------------------------------------------------------------------

Aaron,
 
Before taking your word for it, I would like to hear more about how your
benchmarks relate to smart pointers.
 
It sounds reasonable that the kind of lock described will perform badly in
high-contention situations. But what evidence do you have that there is any
probability of high contention, especially when, as you say, the locks are
short-lived? These locks aren't taken every time the smart pointer is accessed;
they're only taken when a copy is made. So to get the high contention you speak
of, you would have to have two threads repeatedly making copies of the "same"
smart pointer. From where I stand, this seems sufficiently rare that the extra
performance gain in the common cases is worth it.
 
/Mattias
-------------------------------------------------------------------------------------

flodin@cs.umu.se wrote:
>  It sounds reasonable that the kind of lock described will perform badly in
high-contention situations. But what evidence do you have that there is any
probability of high contention, especially when, as you say, the locks are
short-lived? These locks aren't taken every time the smart pointer is accessed;
they're only taken when a copy is made. So to get the high contention you speak
of, you would have to have two threads repeatedly making copies of the "same"
smart pointer. From where I stand, this seems sufficiently rare that the extra
performance gain in the common cases is worth it. 

 
[these comments are specific to the win32 spinlock discussed]
 
I have two specific concerns.
 
1) Personally, I value predictable performance.  I would prefer slight
performance degradation (Note, however, that I am not examining the
actual numbers.) to the case where I may have an occasional very long
wait.  (Specific example: If a graphically intensive program is aiming
for 30 frames per second, that is only about 30ms per frame.  It would
be very unfortunate if, even occasionally, a single smart pointer copy
accounted for 1/3 of the time it took to render a frame.)
 
2) In "thundering herd" situations, contention is unavoidable, and
performance may be paramount.  The possibility of a single thread
halting many other threads for 10ms on a machine with many processors is
disturbing. (Specific example: In a case where thread is producing work
for many consumer threads on a multiprocessor machine, and obtaining the
work involves copying a smart pointer, it is possible that some amount
of threads will forced to sleep every single time, which might be a
substantial percentage of total job wall clock time.)
 
In any case, I feel fairly strongly that sleeping is not the right thing
to do.  Despite the weakness in appeal to authority, I will note that I
have seen Butenhof make the same assertion on Usenet, surely in a manner
more eloquent than mine.
 
I previously neglected to suggest alternatives.
 
1) A generally sound 8-byte mutex could be used.  I am not sure how bad
this would be in terms of storage efficiency.  It may be possible to
implement it using less storage, but I have no specific information on this.
 
2) I've seen a shared_ptr count implementation that used
InterlockedIncrement instead of the lwm code.  I have not examined this
in detail; however it seems that an approach like this is better in all
respects than trying to manage locks if the only need is to maintain a
count (which is what many mutex primatives are doing anyway).  Is there
some reason this cannot be used?
 
What do you think?
 
Aaron W. LaFramboise
--------------------------------------------------------------------------------

while( __exchange_and_add(&m_.a_, 1) ){
//  если в этот момент другой тред будет пытаться захватить автолок, наверняка будет бяка
  __atomic_add(&m_.a_, -1);
//  и в этот наверняка тоже :)
  sched_yield();
}

while( __exchange_and_add(&m_.a_, 1) ){
  __atomic_add(&m_.a_, -1);
  sched_yield();
}