Discussion :

[Pyramidev]

Bonjour,

Pour rappel, std::lock sert à bloquer plusieurs mutex en évitant les deadlocks.
Prérequis : documentation : http://en.cppreference.com/w/cpp/thread/lock

Hier, par curiosité, j'ai regardé l'implémentation de std::lock de GCC 4.9.2, mais j'ai été déçu.
La voici, accompagnée de l'implémentation de std::try_lock :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
  template<typename _Lock>
    unique_lock<_Lock>
    __try_to_lock(_Lock& __l)
    { return unique_lock<_Lock>(__l, try_to_lock); }
 
  template<int _Idx, bool _Continue = true>
    struct __try_lock_impl
    {
      template<typename... _Lock>
	static void
	__do_try_lock(tuple<_Lock&...>& __locks, int& __idx)
	{
          __idx = _Idx;
          auto __lock = __try_to_lock(std::get<_Idx>(__locks));
          if (__lock.owns_lock())
            {
              __try_lock_impl<_Idx + 1, _Idx + 2 < sizeof...(_Lock)>::
                __do_try_lock(__locks, __idx);
              if (__idx == -1)
                __lock.release();
            }
	}
    };
 
  template<int _Idx>
    struct __try_lock_impl<_Idx, false>
    {
      template<typename... _Lock>
	static void
	__do_try_lock(tuple<_Lock&...>& __locks, int& __idx)
	{
          __idx = _Idx;
          auto __lock = __try_to_lock(std::get<_Idx>(__locks));
          if (__lock.owns_lock())
            {
              __idx = -1;
              __lock.release();
            }
	}
    };
 
  /** @brief Generic try_lock.
   *  @param __l1 Meets Mutex requirements (try_lock() may throw).
   *  @param __l2 Meets Mutex requirements (try_lock() may throw).
   *  @param __l3 Meets Mutex requirements (try_lock() may throw).
   *  @return Returns -1 if all try_lock() calls return true. Otherwise returns
   *          a 0-based index corresponding to the argument that returned false.
   *  @post Either all arguments are locked, or none will be.
   *
   *  Sequentially calls try_lock() on each argument.
   */
  template<typename _Lock1, typename _Lock2, typename... _Lock3>
    int
    try_lock(_Lock1& __l1, _Lock2& __l2, _Lock3&... __l3)
    {
      int __idx;
      auto __locks = std::tie(__l1, __l2, __l3...);
      __try_lock_impl<0>::__do_try_lock(__locks, __idx);
      return __idx;
    }
 
  /** @brief Generic lock.
   *  @param __l1 Meets Mutex requirements (try_lock() may throw).
   *  @param __l2 Meets Mutex requirements (try_lock() may throw).
   *  @param __l3 Meets Mutex requirements (try_lock() may throw).
   *  @throw An exception thrown by an argument's lock() or try_lock() member.
   *  @post All arguments are locked.
   *
   *  All arguments are locked via a sequence of calls to lock(), try_lock()
   *  and unlock().  If the call exits via an exception any locks that were
   *  obtained will be released.
   */
  template<typename _L1, typename _L2, typename ..._L3>
    void
    lock(_L1& __l1, _L2& __l2, _L3&... __l3)
    {
      while (true)
        {
          unique_lock<_L1> __first(__l1);
          int __idx;
          auto __locks = std::tie(__l2, __l3...);
          __try_lock_impl<0, sizeof...(_L3)>::__do_try_lock(__locks, __idx);
          if (__idx == -1)
            {
              __first.release();
              return;
            }
        }
    }

Pour que ce soit plus facile à suivre, voici le code équivalent dans le cas où std::lock a 3 paramètres :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
template<class Lockable1, class Lockable2>
int try_lock(Lockable1& lock1, Lockable2& lock2);
 
template<class Lockable1, class Lockable2, class Lockable3>
void lock(Lockable1& lock1, Lockable2& lock2, Lockable3& lock3)
{
	while(true) {
		unique_lock<Lockable1> u1(lock1); // can throw
		int idx = try_lock(lock2, lock3); // can throw
		if(idx == -1) {
			u1.release();
			return;
		}
	}
}
 
template<class Lockable1, class Lockable2>
int try_lock(Lockable1& lock1, Lockable2& lock2)
{
	int result = 0;
	unique_lock<Lockable1> u1(lock1, try_to_lock); // can throw
	if(u1.owns_lock()) {
		result = 1;
		unique_lock<Lockable2> u2(lock2, try_to_lock); // can throw
		if(u2.owns_lock()) {
			result = -1;
			u2.release();
		}
		if(result == -1)
			u1.release();
	}
	return result;
}

Le problème de cette implémentation est que le premier mutex que la fonction essaie de bloquer est toujours le même, à savoir celui qui est en 1er paramètre.
Admettons que, par exemple, le 3e mutex soit déjà bloqué et que la fonction essaie de bloquer les 3 mutex. La fonction ne va jamais s'arrêter et va continuellement bloquer et débloquer les deux premiers mutex. Il aurait été préférable qu'elle se rappelle que c'est le 3e mutex qu'elle n'a pas réussi à bloquer puis qu'elle décide, après avoir débloquer les deux premiers mutex, de bloquer le 3e en premier.

Boost 1.61.0, lui, possèdes des lock non variadics implémentés correctement (je n'ai pas regardé les autres versions de Boost). Voici l'implémentation du boost::lock à 3 paramètres :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
namespace boost
{
  namespace detail
  {
    // ...
 
    template <typename MutexType1, typename MutexType2, typename MutexType3>
    unsigned lock_helper(MutexType1& m1, MutexType2& m2, MutexType3& m3)
    {
      boost::unique_lock<MutexType1> l1(m1);
      if (unsigned const failed_lock=try_lock_internal(m2,m3))
      {
        return failed_lock;
      }
      l1.release();
      return 0;
    }
 
    // ...
 
  }
 
  // ...
 
  template <typename MutexType1, typename MutexType2, typename MutexType3>
  void lock(MutexType1& m1, MutexType2& m2, MutexType3& m3)
  {
    unsigned const lock_count = 3;
    unsigned lock_first = 0;
    for (;;)
    {
      switch (lock_first)
      {
      case 0:
        lock_first = detail::lock_helper(m1, m2, m3);
        if (!lock_first) return;
        break;
      case 1:
        lock_first = detail::lock_helper(m2, m3, m1);
        if (!lock_first) return;
        lock_first = (lock_first + 1) % lock_count;
        break;
      case 2:
        lock_first = detail::lock_helper(m3, m1, m2);
        if (!lock_first) return;
        lock_first = (lock_first + 2) % lock_count;
        break;
      }
    }
  }
 
  // ...
 
}

Mais comment faire une implémentation correcte avec des variadic templates ?
Aujourd'hui, je viens d'en faire une avec du type erasure :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class LockableBase
{
public:
	virtual ~LockableBase() {}
	virtual void lock()     = 0;
	virtual bool try_lock() = 0;
	virtual void unlock()   = 0;
};
 
template<class Lockable>
class LockableWrapper : public LockableBase
{
private:
	Lockable& m_lock;
public:
	explicit LockableWrapper(Lockable& lock) : m_lock(lock) {}
	~LockableWrapper() override {}
	void lock()        override { m_lock.lock();            }
	bool try_lock()    override { return m_lock.try_lock(); }
	void unlock()      override { m_lock.unlock();          }
};
 
class LockableAny
{
private:
	std::unique_ptr<LockableBase> m_lockBase;
 
public:
	LockableAny() {}
 
	template<class Lockable>
	LockableAny(Lockable& lock) :
		m_lockBase(new LockableWrapper<Lockable>(lock))
	{
	}
 
	void lock()     { assert(m_lockBase); m_lockBase->lock();            }
	bool try_lock() { assert(m_lockBase); return m_lockBase->try_lock(); }
	void unlock()   { assert(m_lockBase); m_lockBase->unlock();          }
};
 
template<size_t CurrentIndex, class LockableAnyArrayType, class Lockable>
void fillLockableAnyArray(LockableAnyArrayType& arrayLocks, Lockable& lock)
{
	arrayLocks[CurrentIndex] = LockableAny(lock);
}
 
template<size_t CurrentIndex, class LockableAnyArrayType, class Lockable1, class ...LockableTypes>
void fillLockableAnyArray(LockableAnyArrayType& arrayLocks, Lockable1& lock1, LockableTypes&... lockN)
{
	arrayLocks[CurrentIndex] = LockableAny(lock1);
	fillLockableAnyArray<CurrentIndex + 1>(arrayLocks, lockN...);
}
 
template<class Lockable1, class Lockable2, class... LockableN>
void lock(Lockable1& lock1, Lockable2& lock2, LockableN&... lockN)
{
	constexpr size_t nbArgs = 2 + sizeof...(LockableN);
 
	std::array<LockableAny, nbArgs> arrayLocks;
	fillLockableAnyArray<0>(arrayLocks, lock1, lock2, lockN...);
 
//	std::array<unique_lock<LockableAny>, nbArgs> arrayUniqueLocks;
		// EDIT 18/09/2016 vers 2h34 : bogue corrigé : ligne déplacée vers l'intérieur de la boucle while
 
	size_t firstLock = 0;
 
	while(true)	{
		std::array<unique_lock<LockableAny>, nbArgs> arrayUniqueLocks;
		arrayUniqueLocks[firstLock] = unique_lock<LockableAny>(arrayLocks[firstLock]);
		size_t lockIndex = (firstLock + 1) % nbArgs;
		bool lockSuccess = true;
		for(; lockIndex != firstLock && lockSuccess; lockIndex = (lockIndex+1)%nbArgs) {
			arrayUniqueLocks[lockIndex] = unique_lock<LockableAny>(arrayLocks[lockIndex], try_to_lock);
			lockSuccess = arrayUniqueLocks[lockIndex].owns_lock();
		}
		if(lockSuccess) {
			for(auto& uLock : arrayUniqueLocks)
				uLock.release();
			return;
		} else {
			firstLock = (lockIndex + nbArgs - 1) % nbArgs;
		}
	}
}

Mais ma première implémentation a un inconvénient :
Je stocke les objets LockableWrapper dans la mémoire dynamique, ce qui n'est pas performant.

J'ai voulu les mettre dans un std::tuple, mais je n'ai pas réussi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class Lockable1, class Lockable2, class... LockableN>
void lock(Lockable1& lock1, Lockable2& lock2, LockableN&... lockN)
{
	std::tuple<
		LockableWrapper<Lockable1>,
		LockableWrapper<Lockable2>,
		LockableWrapper<LockableN>
	> locks(
		LockableWrapper<Lockable1>(lock1),
		LockableWrapper<Lockable2>(lock2),
		LockableWrapper<LockableN>(lockN...) // Ne compile pas.
	);
	// ...
}

Finalement, dans ma deuxième implémentation, j'ai triché en sauvegardant le LockableWrapper directement dans LockableAny. Seule la classe LockableAny a changé :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class LockableAny
{
private:
	std::aligned_storage<sizeof (LockableWrapper<std::mutex>),
	                     alignof(LockableWrapper<std::mutex>)>::type m_data;
 
	LockableBase& getLockBaseRef()
	{
		return reinterpret_cast<LockableBase&>(m_data);
	}
 
public:
	LockableAny() {}
 
	template<class Lockable>
	LockableAny(Lockable& lock)
	{
		static_assert(   sizeof (LockableWrapper<Lockable>) == sizeof (LockableWrapper<std::mutex>)
		              && alignof(LockableWrapper<Lockable>) == alignof(LockableWrapper<std::mutex>),
		              "Hack échoué. Tous les LockableWrapper doivent avoir la même taille et le même alignement."
		              " Sinon, changer le type de m_data en std::unique_ptr<LockableBase> et adapter le code.");
 
		new(&m_data) LockableWrapper<Lockable>(lock);
	}
 
	void lock()     { getLockBaseRef().lock();            }
	bool try_lock() { return getLockBaseRef().try_lock(); }
	void unlock()   { getLockBaseRef().unlock();          }
};

Les LockableWrapper ont tous la même taille et le même alignement, car ils contiennent tous la même chose : un pointeur vers une table virtuelle et une référence.
Le destructeur de LockableWrapper n'est pas appelé, mais ce n'est pas grave : il ne fait rien.
Cependant, c'est assez moche et je crains que ce ne soit pas portable à cause du reinterpret_cast.

En tout cas, je n'ai pas trouvé comment implémenter correctement std::lock sans passer par des fonctions virtuelles ou des pointeurs de fonction.
Est-ce possible ? Si oui, est-ce que l'un d'entre vous y arriverait ? Le défi est lancé !