This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: debug mode performance patch


Hi

Here is a new proposition with the deadlock issue fixed. I use auto_ptr to acquire it even if it is deprecated because unique_ptr is only available in gnu++0x mode and the library is not built in this mode, is it fine ? I also created a test to show the problem before the fix. In fact I even had to add a sleep between the 2 locks in debug.cc to reproduce the deadlock temporarily, it shows that the problem existed and that it has been removed now.

Just in case you agree to apply the patch there are new files in it, especially the safe_sequence.tcc one. Has it to be added in some files ? I ask because to run tests I had to manually create a link to this file in x86_64-unknown-linux-gnu/libstdc++-v3/include/debug. Will it be generated automatically once commited ?

François

On 11/11/2010 10:06 PM, François Dumont wrote:
Ok I will integrate a test showing the deadlock issue with current patch based on your code and then will fix the patch.

Thanks for the code !

On 11/10/2010 11:02 PM, Jonathan Wakely wrote:
On 10 November 2010 21:55, François Dumont wrote:
Well, this is not something my change introduce. For the moment the debug
mode is using a single mutex for all synchronizations. To keep binary
compatibility I haven't been able to add a mutex instance to the safe
sequence so I introduce a small mutex pool to limit contention.
Sorry if my review sounded negative, I think the general idea is very
good.  But with a single mutex there is no chance for deadlock, it
just means only one swap can take place at a time.

By introducing multiple mutexes without some checking you make it easy
to deadlock.  Slow and correct is better than fast and deadlock  ;-)

There are two problems with _M_swap in your patch:

1) if two objects are swapped whih share the same mutex then it will
try to lock the same mutex twice.  You should be able to reproduce
this like so (untested):

__gnu_debug::vector<int>    v[17];
swap(v[0], v[16]);

If I'm not mistaken, v[0] and v[16] should get the same mutex from
get_mutex and so should lock it twice. That's bad, even in a
single-threaded program.

Yes, this is why I asked if mutex are guarantied to be reentrant even if I
agree that even if it is so it is still bad practice.
When your mail arrived I had just finished some examples to
demonstrate the problems, maybe these should go in the testsuite.

This deadlocks for me:

#include<mutex>
#include<iostream>

std::mutex& get_mutex(void* p)
{
const uintptr_t mask = 0xf;
static std::mutex mutexes[ mask + 1 ];
uintptr_t index = (reinterpret_cast<uintptr_t>(p) / sizeof(void*))& mask;
std::cerr<< index<< std::endl;
return mutexes[ index ];
}


struct A { void* p; };

void swap(A&  a, A&  b)
{
   std::lock_guard<std::mutex>  l1(get_mutex(&a));
   std::lock_guard<std::mutex>  l2(get_mutex(&b));
}

int main()
{
   A a[17];
   swap(a[0], a[16]);  // distinct objects, but "share" a mutex
}

2) consider four sequences, A, B, C and D. They happen to have
addresses such that:

&A.get_mutex() ==&C.get_mutex()
and
&B.get_mutex() ==&D.get_mutex()

now, in my multithreaded program I do this concurrently:
swap(A, B);   swap(D, C);
I'm not accessing any single object in more than one thread, but it
will deadlock.

Indeed
e.g this deadlocks for me:

// same definition of A, get_mutex and swap:
#include<thread>

A a[32];

void f(int i, int j) { for (int k=0; k<10; ++k) swap(a[i], a[j]); }

int main()
{
   // swap distinct objects in two threads
   std::thread t1(f, 0, 1);
   std::thread t2(f, 17, 16);
   t1.join();
   t2.join();
}


The solution is to ensure that you don't lock the same mutex twice and
you always lock in a consistent order

e.g. this fixes both deadlocks

void swap(A&  a, A&  b)
{
   std::mutex&  m1 = get_mutex(&a);
   std::mutex&  m2 = get_mutex(&b);
   if (&m1< &m2)
     std::lock_guard<std::mutex>  l(m1);
   else
   {
     std::lock_guard<std::mutex>  l1(&m1< &m2 ? m1 : m2);
     std::lock_guard<std::mutex>  l2(&m1< &m2 ? m2 : m1);
   }
}

Ok, so except fixing this lock issue you seem to agree on the modified debug
mode lock model, great. I will fix this issue and submit a new proposition.
Great - thanks for working on this!

Jonathan


Attachment: performance.patch
Description: Text document


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]