fix race condition in file locking

Submitted by Kaarle Ritvanen on Sept. 17, 2018, 10:53 p.m.

Details

Message ID 20180917225336.1953-1-kaarle.ritvanen@datakunkku.fi
State New
Series "fix race condition in file locking"
Headers show

Commit Message

Kaarle Ritvanen Sept. 17, 2018, 10:53 p.m.
The condition occurs when
- thread #1 is holding the lock
- thread #2 is waiting for it on __futexwait
- thread #1 is about to release the lock and performs a_swap
- thread #3 enters the __lockfile function and manages to grab the lock
  before thread #1 calls __wake, resetting the MAYBE_WAITERS flag
- thread #1 calls __wake
- thread #2 wakes up but goes again to __futexwait as the lock is
  held by thread #3
- thread #3 releases the lock but does not call __wake as the
  MAYBE_WAITERS flag is not set

This condition results in thread #2 not being woken up. This patch fixes
the problem by making the woken up thread ensure that the flag is properly set
before going to sleep again.
---
 src/stdio/__lockfile.c | 11 +++++------
 1 file changed, 5 insertions(+), 6 deletions(-)

Patch hide | download patch | download mbox

diff --git a/src/stdio/__lockfile.c b/src/stdio/__lockfile.c
index 2ff75d8a..f6adefb6 100644
--- a/src/stdio/__lockfile.c
+++ b/src/stdio/__lockfile.c
@@ -8,13 +8,12 @@  int __lockfile(FILE *f)
 	int owner = f->lock, tid = __pthread_self()->tid;
 	if ((owner & ~MAYBE_WAITERS) == tid)
 		return 0;
-	for (;;) {
-		owner = a_cas(&f->lock, 0, tid);
-		if (!owner) return 1;
-		if (a_cas(&f->lock, owner, owner|MAYBE_WAITERS)==owner) break;
+	owner = a_cas(&f->lock, 0, tid);
+	if (!owner) return 1;
+	while ((owner = a_cas(&f->lock, 0, tid|MAYBE_WAITERS))) {
+		if (a_cas(&f->lock, owner, owner|MAYBE_WAITERS)==owner)
+			__futexwait(&f->lock, owner, 1);
 	}
-	while ((owner = a_cas(&f->lock, 0, tid|MAYBE_WAITERS)))
-		__futexwait(&f->lock, owner, 1);
 	return 1;
 }
 

Comments

Rich Felker Sept. 17, 2018, 11:19 p.m.
On Tue, Sep 18, 2018 at 01:53:36AM +0300, Kaarle Ritvanen wrote:
> The condition occurs when
> - thread #1 is holding the lock
> - thread #2 is waiting for it on __futexwait
> - thread #1 is about to release the lock and performs a_swap
> - thread #3 enters the __lockfile function and manages to grab the lock
>   before thread #1 calls __wake, resetting the MAYBE_WAITERS flag
> - thread #1 calls __wake
> - thread #2 wakes up but goes again to __futexwait as the lock is
>   held by thread #3
> - thread #3 releases the lock but does not call __wake as the
>   MAYBE_WAITERS flag is not set
> 
> This condition results in thread #2 not being woken up. This patch fixes
> the problem by making the woken up thread ensure that the flag is properly set
> before going to sleep again.
> ---
>  src/stdio/__lockfile.c | 11 +++++------
>  1 file changed, 5 insertions(+), 6 deletions(-)
> 
> diff --git a/src/stdio/__lockfile.c b/src/stdio/__lockfile.c
> index 2ff75d8a..f6adefb6 100644
> --- a/src/stdio/__lockfile.c
> +++ b/src/stdio/__lockfile.c
> @@ -8,13 +8,12 @@ int __lockfile(FILE *f)
>  	int owner = f->lock, tid = __pthread_self()->tid;
>  	if ((owner & ~MAYBE_WAITERS) == tid)
>  		return 0;
> -	for (;;) {
> -		owner = a_cas(&f->lock, 0, tid);
> -		if (!owner) return 1;
> -		if (a_cas(&f->lock, owner, owner|MAYBE_WAITERS)==owner) break;
> +	owner = a_cas(&f->lock, 0, tid);
> +	if (!owner) return 1;
> +	while ((owner = a_cas(&f->lock, 0, tid|MAYBE_WAITERS))) {
> +		if (a_cas(&f->lock, owner, owner|MAYBE_WAITERS)==owner)
> +			__futexwait(&f->lock, owner, 1);
>  	}

Overall I think the concept is right, but I don't understand the logic
in this loop. When adding the MAYBE_WAITERS flag with a_cas succeeds,
it will try to __futexwait with the old value that doesn't have
MAYBE_WAITERS set, which will fail and spin again, adding a spurious
cas and a spurious syscall.

I think the right logic would be something like:

	while ((owner = a_cas(&f->lock, 0, tid|MAYBE_WAITERS))) {
		if (!(owner & MAYBE_WAITERS))
			a_cas(&f->lock, owner, owner|MAYBE_WAITERS);
		__futexwait(&f->lock, owner|MAYBE_WAITERS, 1);
	}

Does that look better to you? The if is not actually necessary (the
a_cas could be done unconditionally) but skipping it puts less
pressure on the hardware's cache coherency.

Alternatively it could be:

	while ((owner = a_cas(&f->lock, 0, tid|MAYBE_WAITERS))) {
		if ((owner & MAYBE_WAITERS) ||
		    a_cas(&f->lock, owner, owner|MAYBE_WAITERS)==owner)
			__futexwait(&f->lock, owner|MAYBE_WAITERS, 1);
	}

This form does what you were trying to do, I think, and avoids making
the syscall when the owner changed in a race (the syscall would fail,
but avoiding it saves time).

Rich