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


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


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