linux-fsdevel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* Bug: lockf returns false-positive EDEADLK in multiprocess multithreaded environment
@ 2022-01-10 10:46 Ivan Zuboff
       [not found] ` <CAL-cVeiHF3+1bq9+RLsdZU-kzfMNYxD0CJBGVeKOrrEpBAyt4Q@mail.gmail.com>
  0 siblings, 1 reply; 5+ messages in thread
From: Ivan Zuboff @ 2022-01-10 10:46 UTC (permalink / raw)
  To: linux-fsdevel

[-- Attachment #1: Type: text/plain, Size: 2266 bytes --]

As an application-level developer, I found a counter-intuitive
behavior in lockf function provided by glibc and Linux kernel that is
likely a bug.

In glibc, lockf function is implemented on top of fcntl system call:
https://github.com/lattera/glibc/blob/master/io/lockf.c
man page says that lockf can sometimes detect deadlock:
http://manpages.ubuntu.com/manpages/xenial/man3/lockf.3.html
Same with fcntl(F_SETLKW), on top of which lockf is implemented:
http://manpages.ubuntu.com/manpages/hirsute/en/man3/fcntl.3posix.html

Deadlock detection algorithm in the Linux kernel
(https://github.com/torvalds/linux/blob/master/fs/locks.c) seems buggy
because it can easily give false positives. Suppose we have two
processes A and B, process A has threads 1 and 2, process B has
threads 3 and 4. When this processes execute concurrently, following
sequence of actions is possible:
1. processA thread1 gets lockI
2. processB thread2 gets lockII
3. processA thread3 tries to get lockII, starts to wait
4. processB thread4 tries to get lockI, kernel detects deadlock,
EDEADLK is returned from lockf function

Steps to reproduce this scenario (see attached file):
1. gcc -o edeadlk ./edeadlk.c -lpthread
2. Launch "./edeadlk a b" in the first terminal window.
3. Launch "./edeadlk a b" in the second terminal window.

What I expected to happen: two instances of the program are steadily working.

What happened instead:
Assertion failed: (lockf(fd, 1, 1)) != -1 file: ./edeadlk.c, line:25,
errno:35 . Error:: Resource deadlock avoided
Aborted (core dumped)

Surely, this behavior is kind of "right". lockf file locks belongs to
process, so on the process level it seems that deadlock is just about
to happen: process A holds lockI and waits for lockII, process B holds
lockII and is going to wait for lockI. However, the algorithm in the
kernel doesn't take threads into account. In fact, a deadlock is not
going to happen here if the thread scheduler will give control to some
thread holding a lock.

I think there's a problem with the deadlock detection algorithm
because it's overly pessimistic, which in turn creates problems --
lockf errors in applications. I had to patch my application to use
flock instead because flock doesn't have this overly-pessimistic
behavior.

[-- Attachment #2: edeadlk.c --]
[-- Type: application/octet-stream, Size: 1051 bytes --]

#include<unistd.h>
#include<stdio.h>
#include<stdlib.h>
#include<fcntl.h>
#include<errno.h>
#include<pthread.h>
#include<stddef.h>
#include<stdint.h>

#define DIE(x)\
{\
	fprintf(stderr, "Assertion failed: " #x " file: %s, line:%d, errno:%d ", __FILE__, __LINE__, errno); \
	perror(". Error:");\
	fflush(stdout);\
	abort();\
}
#define ASS(x) if (!(x)) DIE(x)
#define ASS1(x) ASS((x) != -1)
#define ASS0(x) ASS((x) == 0)

void * deadlocker(void *arg)
{
    int fd = (int)(ptrdiff_t)arg;
    for (;;) {
        ASS1( lockf(fd, F_LOCK, 1) );
        ASS1( lockf(fd, F_ULOCK, 1) );
    }
    return NULL;
}

int main(int argc, char * argv[])
{
    int fd1, fd2;
    ASS( argc >= 3 );
    ASS1( fd1 = creat(argv[1], 0660) );
    ASS1( fd2 = creat(argv[2], 0660) );
    void * thrv;
    pthread_t thr1, thr2;
    ASS0( pthread_create(&thr1, NULL, deadlocker, (void *)(ptrdiff_t)fd2) );
    ASS0( pthread_create(&thr2, NULL, deadlocker, (void *)(ptrdiff_t)fd1) );
    ASS0( pthread_join(thr1, &thrv) );
    ASS0( pthread_join(thr2, &thrv) );
    return 0;
}

^ permalink raw reply	[flat|nested] 5+ messages in thread

end of thread, other threads:[~2022-01-31 13:10 UTC | newest]

Thread overview: 5+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2022-01-10 10:46 Bug: lockf returns false-positive EDEADLK in multiprocess multithreaded environment Ivan Zuboff
     [not found] ` <CAL-cVeiHF3+1bq9+RLsdZU-kzfMNYxD0CJBGVeKOrrEpBAyt4Q@mail.gmail.com>
2022-01-31 11:21   ` Fwd: " Jeff Layton
2022-01-31 12:06     ` Ivan Zuboff
2022-01-31 12:45       ` Jeff Layton
2022-01-31 13:10         ` Ivan Zuboff

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).