Race in PyThread_release_lock - can lead to memory corruption and deadlock

Create issue
Issue #3072 resolved
Kirill Smelkov created an issue

Hello up there. I recently found concurency bug that applies to CPython2.7, PyPy2 and PyPy3. Basically PyThread_release_lock, on systems where it is implemented via mutex + condition variable, has a race condition since pthread_cond_signal is called outside of mutex-protected region. This race condition can lead to memory corruption and deadlock. I’ve hit this bug for real while testing Pygolang on macOS. Original bug report is here: https://bugs.python.org/issue38106.

Copy of original bug report follows:

----8<----

Bug history

( Please see attached pylock_bug.pyx for the program that triggers the bug for real. )

On Darwin, even though this is considered as POSIX, Python uses
mutex+condition variable to implement its lock, and, as of 20190828, Py2.7
implementation, even though similar issue was fixed for Py3 in 2012, contains
synchronization bug: the condition is signalled after mutex unlock while the
correct protocol is to signal condition from under mutex:

https://github.com/python/cpython/blob/v2.7.16-127-g0229b56d8c0/Python/thread_pthread.h#L486-L506
https://github.com/python/cpython/commit/187aa545165d (py3 fix)

PyPy has the same bug for both pypy2 and pypy3:

https://bitbucket.org/pypy/pypy/src/578667b3fef9/rpython/translator/c/src/thread_pthread.c#lines-443:465
https://bitbucket.org/pypy/pypy/src/5b42890d48c3/rpython/translator/c/src/thread_pthread.c#lines-443:465

Signalling condition outside of corresponding mutex is considered OK by
POSIX, but in Python context it can lead to at least memory corruption if we
consider the whole lifetime of python level lock. For example the following
logical scenario:

      T1                                          T2

  sema = Lock()
  sema.acquire()

                                              sema.release()

  sema.acquire()
  free(sema)

  ...

can translate to the next C-level calls:

      T1                                          T2

  # sema = Lock()
  sema = malloc(...)
  sema.locked = 0
  pthread_mutex_init(&sema.mut)
  pthread_cond_init (&sema.lock_released)

  # sema.acquire()
  pthread_mutex_lock(&sema.mut)
  # sees sema.locked == 0
  sema.locked = 1
  pthread_mutex_unlock(&sema.mut)


                                              # sema.release()
                                              pthread_mutex_lock(&sema.mut)
                                              sema.locked = 0
                                              pthread_mutex_unlock(&sema.mut)

                      # OS scheduler gets in and relinquishes control from T2
                      # to another process
                                              ...

  # second sema.acquire()
  pthread_mutex_lock(&sema.mut)
  # sees sema.locked == 0
  sema.locked = 1
  pthread_mutex_unlock(&sema.mut)

  # free(sema)
  pthread_mutex_destroy(&sema.mut)
  pthread_cond_destroy (&sema.lock_released)
  free(sema)


  # ...
  e.g. malloc() which returns memory where sema was

                                              ...
                      # OS scheduler returns control to T2
                      # sema.release() continues
                      #
                      # BUT sema was already freed and writing to anywhere
                      # inside sema block CORRUPTS MEMORY. In particular if
                      # _another_ python-level lock was allocated where sema
                      # block was, writing into the memory can have effect on
                      # further synchronization correctness and in particular
                      # lead to deadlock on lock that was next allocated.
                                              pthread_cond_signal(&sema.lock_released)

Note that T2.pthread_cond_signal(&sema.lock_released) CORRUPTS MEMORY as it
is called when sema memory was already freed and is potentially
reallocated for another object.

The fix is to move pthread_cond_signal to be done under corresponding mutex:

  # sema.release()
  pthread_mutex_lock(&sema.mut)
  sema.locked = 0
  pthread_cond_signal(&sema.lock_released)
  pthread_mutex_unlock(&sema.mut)

by cherry-picking commit 187aa545165d ("Signal condition variables with the
mutex held. Destroy condition variables before their mutexes").

Bug history

The bug was there since 1994 - since at least [1]. It was discussed in 2001
with original code author[2], but the code was still considered to be
race-free. In 2010 the place where pthread_cond_signal should be - before or
after pthread_mutex_unlock - was discussed with the rationale to avoid
threads bouncing[3,4,5], and in 2012 pthread_cond_signal was moved to be
called from under mutex, but only for CPython3[6,7].

In 2019 the bug was (re-)discovered while testing Pygolang[8] on macOS with
CPython2 and PyPy2 and PyPy3.

[1] https://github.com/python/cpython/commit/2c8cb9f3d240
[2] https://bugs.python.org/issue433625
[3] https://bugs.python.org/issue8299#msg103224
[4] https://bugs.python.org/issue8410#msg103313
[5] https://bugs.python.org/issue8411#msg113301
[6] https://bugs.python.org/issue15038#msg163187
[7] https://github.com/python/cpython/commit/187aa545165d
[8] https://pypi.org/project/pygolang

Comments (7)

  1. Kirill Smelkov reporter

    @Armin Rigo thanks again for the fix. I’m not sure (just had not digged on this topic), but my intuition says that it is better to also destroy the condition variable before destryoing the mutex. CPython did this in the commit I mentioned, but on PyPy side only pthread_cond_signal was moved before pthread_mutex_unlock, whereas pthread_cond_destroy still comes after pthread_mutex_destroy. Condition builds on top of a mutex, and pthread library implementations often glue condition to associated mutex internally. This way it should be more safe to first destroy the condition variable becuase it is another mutex user.

    Once again I’m not 100% sure and had not investigated this topic. I suggest to be on the safe side though, since debugging concurrency issues is expensive and it would be a pity to spend a lot of effort to prove it has to be done this way after hitting the issue for real again, given that the fix is simple and aligns with what CPython already does and what pthread tutorials recommend.

  2. Armin Rigo

    I'm not sure it makes any difference. If there is any concurrent user of either the mutex or the condition variable here, then we're going to get random memory corruption, independently of the order in which they are freed. But I also don't see any reason not to follow your sensible-sounding advice. Checked in a9d36d6af872.

  3. Log in to comment