Fw: Spam: [Bugme-new] [Bug 2829] New: posix_locks_deadlock() loops infinitely

Fw: Spam: [Bugme-new] [Bug 2829] New: posix_locks_deadlock() loops infinitely

[Andrew Morton]

Begin forwarded message:

Date: Thu, 3 Jun 2004 22:45:56 -0700
From: bugme-daemon@osdl.org
To: bugme-new@lists.osdl.org
Subject: Spam: [Bugme-new] [Bug 2829] New: posix_locks_deadlock() loops infinitely


http://bugme.osdl.org/show_bug.cgi?id=2829

           Summary: posix_locks_deadlock() loops infinitely
    Kernel Version: 2.6.6
            Status: NEW
          Severity: normal
             Owner: fs_vfs@kernel-bugs.osdl.org
         Submitter: i-sakamoto@pb.jp.nec.com


Distribution: debian
Hardware Environment:
Software Environment:
Problem Description: Using POSIX threads makes posix_locks_deadlock() loop
infinitely.

Steps to reproduce:

There are 3 processes; "A", "B" and "C".
Each process opens "file1", "file2" and "file3".

"A" creates 3 POSIX threads; "A1", "A2" and "A3". (These threads' PIDs are the
same.)
"B" creates 2 POSIX threads; "B1" and "B2". (These threads' PIDs are the same.)
"C" creates 1 POSIX thread; "C1".


1. "A1" locks "file1" exclusively.
2. "B1" locks "file2" exclusively.
3. "C1" locks "file3" exclusively.
4. "A2" trys to lock "file2" and sleeps (blocked by "B1").
5. "A3" trys to lock "file3" and sleeps (blocked by "C1").
6. "B2" trys to lock "file1".
   Here, posix_locks_deadlock() must detect deadlock, but
   it does not. Then "B2" sleeps (blocked "A1").

  "A"                                    "B"
   |                                      |
   +--A1(LOCK)---->(file1)<-B2(*deadlock)-+
   |                                      |
   |                                      |
   +--A2(BLOCK)--->(file2)<---B1(LOCK)----+
   |
   |
   +--A3(BLOCK)--->(file3)<---C1(LOCK)----"C"

    block_list -> A3(BLOCK) -> A2(BLOCK)


7. "C1" unlocks "file3". ("A3" wakes up and locks "file3".)
8. "A3" unlocks "file3".
9. Another process locks "file1".
   This makes posix_locks_deadlock() loop infinitely.

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

Re: [Bug 2829] New: posix_locks_deadlock() loops infinitely

[Andrew Morton]

Andrew Morton <akpm@osdl.org> wrote:
>
> 
> 
> Begin forwarded message:
> 
> Date: Thu, 3 Jun 2004 22:45:56 -0700
> From: bugme-daemon@osdl.org
> To: bugme-new@lists.osdl.org
> Subject: Spam: [Bugme-new] [Bug 2829] New: posix_locks_deadlock() loops infinitely
> 

Do you have a test app which demonstrates the bug?


> http://bugme.osdl.org/show_bug.cgi?id=2829
> 
>            Summary: posix_locks_deadlock() loops infinitely
>     Kernel Version: 2.6.6
>             Status: NEW
>           Severity: normal
>              Owner: fs_vfs@kernel-bugs.osdl.org
>          Submitter: i-sakamoto@pb.jp.nec.com
> 
> 
> Distribution: debian
> Hardware Environment:
> Software Environment:
> Problem Description: Using POSIX threads makes posix_locks_deadlock() loop
> infinitely.
> 
> Steps to reproduce:
> 
> There are 3 processes; "A", "B" and "C".
> Each process opens "file1", "file2" and "file3".
> 
> "A" creates 3 POSIX threads; "A1", "A2" and "A3". (These threads' PIDs are the
> same.)
> "B" creates 2 POSIX threads; "B1" and "B2". (These threads' PIDs are the same.)
> "C" creates 1 POSIX thread; "C1".
> 
> 
> 1. "A1" locks "file1" exclusively.
> 2. "B1" locks "file2" exclusively.
> 3. "C1" locks "file3" exclusively.
> 4. "A2" trys to lock "file2" and sleeps (blocked by "B1").
> 5. "A3" trys to lock "file3" and sleeps (blocked by "C1").
> 6. "B2" trys to lock "file1".
>    Here, posix_locks_deadlock() must detect deadlock, but
>    it does not. Then "B2" sleeps (blocked "A1").
> 
>   "A"                                    "B"
>    |                                      |
>    +--A1(LOCK)---->(file1)<-B2(*deadlock)-+
>    |                                      |
>    |                                      |
>    +--A2(BLOCK)--->(file2)<---B1(LOCK)----+
>    |
>    |
>    +--A3(BLOCK)--->(file3)<---C1(LOCK)----"C"
> 
>     block_list -> A3(BLOCK) -> A2(BLOCK)
> 
> 
> 7. "C1" unlocks "file3". ("A3" wakes up and locks "file3".)
> 8. "A3" unlocks "file3".
> 9. Another process locks "file1".
>    This makes posix_locks_deadlock() loop infinitely.
> 
> ------- You are receiving this mail because: -------
> You are on the CC list for the bug, or are watching someone who is.

Re: [Bug 2829] New: posix_locks_deadlock() loops infinitely

[Ichiko Sakamoto]

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

Andrew Morton wrote:

> Andrew Morton <akpm@osdl.org> wrote:
> 
>>
>>
>>Begin forwarded message:
>>
>>Date: Thu, 3 Jun 2004 22:45:56 -0700
>>From: bugme-daemon@osdl.org
>>To: bugme-new@lists.osdl.org
>>Subject: Spam: [Bugme-new] [Bug 2829] New: posix_locks_deadlock() loops infinitely
>>
> 
> 
> Do you have a test app which demonstrates the bug?



Please compile attached source files.
$ gcc -o proc_A proc_A.c -lpthread
$ gcc -o proc_B proc_B.c -lpthread
$ gcc -o proc_C proc_C.c -lpthread

Then create 3 files.
$ touch ./file1
$ touch ./file2
$ touch ./file3

Run 3 procs.
$ ./proc_A & ./proc_B & ./proc_C &

Create file named "1", then "A1" thread will lock "file1".
$ touch 1

Create file named "2", then "B1" will lock "file2".
$ touch 2

Create file named "3", then "C1" will lock "file3".
$ touch 3

Create file named "4", then "A2" will try to lock "file2".
$ touch 4

Create file named "5", then "A3" will try to lock "file3".
$ touch 5

Create file named "6", then "B2" will try to lock "file1".
$ touch 6
Here, deadlock detection fails.

Create file named "7", then "C1" will unlock "file3".
$ touch 7

Create file named "8", then "A3" will unlock "file3".
$ touch 8

Create file named "9", then "C2" trys to lock "file1".
$ touch 9
Here, posix_locks_deadlock() hangs.




-- 
Ichiko Sakamoto

[-- Attachment #2: demo.tgz --]
[-- Type: application/x-compressed, Size: 971 bytes --]

Re: Fw: Spam: [Bugme-new] [Bug 2829] New: posix_locks_deadlock() loops infinitely

[Matthew Wilcox]

On Thu, Jun 03, 2004 at 10:50:12PM -0700, Andrew Morton wrote:
> Subject: Spam: [Bugme-new] [Bug 2829] New: posix_locks_deadlock() loops infinitely

We should just rip out posix_locks_deadlock().  It gives false positives
and false negatives, thanks to NPTL.  POSIX doesn't require us to detect
deadlocks -- it's a "may".

-- 
"Next the statesmen will invent cheap lies, putting the blame upon 
the nation that is attacked, and every man will be glad of those
conscience-soothing falsities, and will diligently study them, and refuse
to examine any refutations of them; and thus he will by and by convince 
himself that the war is just, and will thank God for the better sleep 
he enjoys after this process of grotesque self-deception." -- Mark Twain

Re: Fw: Spam: [Bugme-new] [Bug 2829] New: posix_locks_deadlock() loops infinitely

[Andrew Morton]

Matthew Wilcox <willy@debian.org> wrote:
>
> On Thu, Jun 03, 2004 at 10:50:12PM -0700, Andrew Morton wrote:
> > Subject: Spam: [Bugme-new] [Bug 2829] New: posix_locks_deadlock() loops infinitely
> 
> We should just rip out posix_locks_deadlock().  It gives false positives
> and false negatives, thanks to NPTL.  POSIX doesn't require us to detect
> deadlocks -- it's a "may".

Could you please scoot a patch over sometime?

(How can we simply rip it?  Isn't it trying to do something useful?)

Re: Fw: Spam: [Bugme-new] [Bug 2829] New: posix_locks_deadlock() loops infinitely

[Trond Myklebust]

På fr , 04/06/2004 klokka 22:18, skreiv Andrew Morton:

> > We should just rip out posix_locks_deadlock().  It gives false positives
> > and false negatives, thanks to NPTL.

The standards state that your pid is the criterion for whether or not
you own a lock. (see
http://www.opengroup.org/onlinepubs/009695399/functions/fcntl.html)

This whole messy idea of adding a link to the (totally unrelated)
filetable in fl_owner is what is causing these false positives and
negatives.
That and the fact that the choice of whether to use fl_owner, fl_pid, or
both as an indication of lock ownership appears to be completely random
at various places in locks.c.

> Could you please scoot a patch over sometime?
> 
> (How can we simply rip it?  Isn't it trying to do something useful?)

Could we instead concentrate on fixing the fscking fl_owner? That would
also get rid of crap like "steal_locks".
The only process that needs to be setting fl_owner is lockd, since that
takes locks on behalf of processes that are running on the client
machines.

Deadlock detection *is* useful, particularly so when you are in a
multi-threaded environment. Most other OSes manage to implement it,
exactly why are we more stupid than they are?

Trond
-
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Fw: Spam: [Bugme-new] [Bug 2829] New: posix_locks_deadlock() loops infinitely

[Trond Myklebust]

På fr , 04/06/2004 klokka 22:45, skreiv Trond Myklebust:
> Could we instead concentrate on fixing the fscking fl_owner? That would
> also get rid of crap like "steal_locks".
> The only process that needs to be setting fl_owner is lockd, since that
> takes locks on behalf of processes that are running on the client
> machines.

Something like the appended patch (untested).

Trond

diff -u --recursive --new-file --show-c-function linux-2.6.7-rc1/fs/locks.c linux-2.6.7-lock_nfsv4/fs/locks.c
--- linux-2.6.7-rc1/fs/locks.c	2004-05-29 09:06:52.000000000 -0400
+++ linux-2.6.7-lock_nfsv4/fs/locks.c	2004-06-04 23:13:00.000000000 -0400
@@ -317,7 +317,7 @@ static int flock_to_posix_lock(struct fi
 	if (l->l_len == 0)
 		fl->fl_end = OFFSET_MAX;
 	
-	fl->fl_owner = current->files;
+	fl->fl_owner = 0;
 	fl->fl_pid = current->tgid;
 	fl->fl_file = filp;
 	fl->fl_flags = FL_POSIX;
@@ -357,7 +357,7 @@ static int flock64_to_posix_lock(struct 
 	if (l->l_len == 0)
 		fl->fl_end = OFFSET_MAX;
 	
-	fl->fl_owner = current->files;
+	fl->fl_owner = 0;
 	fl->fl_pid = current->tgid;
 	fl->fl_file = filp;
 	fl->fl_flags = FL_POSIX;
@@ -920,7 +920,7 @@ int posix_lock_file(struct file *filp, s
  */
 int locks_mandatory_locked(struct inode *inode)
 {
-	fl_owner_t owner = current->files;
+	unsigned int pid = current->tgid;
 	struct file_lock *fl;
 
 	/*
@@ -930,7 +930,9 @@ int locks_mandatory_locked(struct inode 
 	for (fl = inode->i_flock; fl != NULL; fl = fl->fl_next) {
 		if (!IS_POSIX(fl))
 			continue;
-		if (fl->fl_owner != owner)
+		if (fl->fl_owner != 0)
+			break;
+		if (fl->fl_pid != pid)
 			break;
 	}
 	unlock_kernel();
@@ -958,7 +960,7 @@ int locks_mandatory_area(int read_write,
 	int error;
 
 	locks_init_lock(&fl);
-	fl.fl_owner = current->files;
+	fl.fl_owner = 0;
 	fl.fl_pid = current->tgid;
 	fl.fl_file = filp;
 	fl.fl_flags = FL_POSIX | FL_ACCESS;
@@ -1684,7 +1686,7 @@ void locks_remove_posix(struct file *fil
 	lock_kernel();
 	while (*before != NULL) {
 		struct file_lock *fl = *before;
-		if (IS_POSIX(fl) && (fl->fl_owner == owner)) {
+		if (IS_POSIX(fl) && posix_same_owner(fl, &lock)) {
 			locks_delete_lock(before);
 			continue;
 		}
@@ -1982,18 +1984,6 @@ int lock_may_write(struct inode *inode, 
 
 EXPORT_SYMBOL(lock_may_write);
 
-static inline void __steal_locks(struct file *file, fl_owner_t from)
-{
-	struct inode *inode = file->f_dentry->d_inode;
-	struct file_lock *fl = inode->i_flock;
-
-	while (fl) {
-		if (fl->fl_file == file && fl->fl_owner == from)
-			fl->fl_owner = current->files;
-		fl = fl->fl_next;
-	}
-}
-
 /* When getting ready for executing a binary, we make sure that current
  * has a files_struct on its own. Before dropping the old files_struct,
  * we take over ownership of all locks for all file descriptors we own.
@@ -2002,31 +1992,6 @@ static inline void __steal_locks(struct 
  */
 void steal_locks(fl_owner_t from)
 {
-	struct files_struct *files = current->files;
-	int i, j;
-
-	if (from == files)
-		return;
-
-	lock_kernel();
-	j = 0;
-	for (;;) {
-		unsigned long set;
-		i = j * __NFDBITS;
-		if (i >= files->max_fdset || i >= files->max_fds)
-			break;
-		set = files->open_fds->fds_bits[j++];
-		while (set) {
-			if (set & 1) {
-				struct file *file = files->fd[i];
-				if (file)
-					__steal_locks(file, from);
-			}
-			i++;
-			set >>= 1;
-		}
-	}
-	unlock_kernel();
 }
 EXPORT_SYMBOL(steal_locks);
 
diff -u --recursive --new-file --show-c-function linux-2.6.7-rc1/fs/nfs/file.c linux-2.6.7-lock_nfsv4/fs/nfs/file.c
--- linux-2.6.7-rc1/fs/nfs/file.c	2004-05-29 09:06:36.000000000 -0400
+++ linux-2.6.7-lock_nfsv4/fs/nfs/file.c	2004-06-04 22:58:49.000000000 -0400
@@ -340,7 +340,7 @@ nfs_lock(struct file *filp, int cmd, str
 	 * Not sure whether that would be unique, though, or whether
 	 * that would break in other places.
 	 */
-	if (!fl->fl_owner || !(fl->fl_flags & FL_POSIX))
+	if (!(fl->fl_flags & FL_POSIX))
 		return -ENOLCK;
 
 	/*
diff -u --recursive --new-file --show-c-function linux-2.6.7-rc1/fs/nfs/nfs4state.c linux-2.6.7-lock_nfsv4/fs/nfs/nfs4state.c
--- linux-2.6.7-rc1/fs/nfs/nfs4state.c	2004-05-29 09:06:20.000000000 -0400
+++ linux-2.6.7-lock_nfsv4/fs/nfs/nfs4state.c	2004-06-04 23:09:10.000000000 -0400
@@ -496,11 +496,11 @@ nfs4_close_state(struct nfs4_state *stat
  * that is compatible with current->files
  */
 static struct nfs4_lock_state *
-__nfs4_find_lock_state(struct nfs4_state *state, fl_owner_t fl_owner)
+__nfs4_find_lock_state(struct nfs4_state *state, unsigned int pid)
 {
 	struct nfs4_lock_state *pos;
 	list_for_each_entry(pos, &state->lock_states, ls_locks) {
-		if (pos->ls_owner != fl_owner)
+		if (pos->ls_pid != pid)
 			continue;
 		atomic_inc(&pos->ls_count);
 		return pos;
@@ -509,11 +509,11 @@ __nfs4_find_lock_state(struct nfs4_state
 }
 
 struct nfs4_lock_state *
-nfs4_find_lock_state(struct nfs4_state *state, fl_owner_t fl_owner)
+nfs4_find_lock_state(struct nfs4_state *state, unsigned int pid)
 {
 	struct nfs4_lock_state *lsp;
 	read_lock(&state->state_lock);
-	lsp = __nfs4_find_lock_state(state, fl_owner);
+	lsp = __nfs4_find_lock_state(state, pid);
 	read_unlock(&state->state_lock);
 	return lsp;
 }
@@ -525,7 +525,7 @@ nfs4_find_lock_state(struct nfs4_state *
  * The caller must be holding state->lock_sema
  */
 struct nfs4_lock_state *
-nfs4_alloc_lock_state(struct nfs4_state *state, fl_owner_t fl_owner)
+nfs4_alloc_lock_state(struct nfs4_state *state, unsigned int pid)
 {
 	struct nfs4_lock_state *lsp;
 	struct nfs4_client *clp = state->owner->so_client;
@@ -537,7 +537,7 @@ nfs4_alloc_lock_state(struct nfs4_state 
 	lsp->ls_id = -1; 
 	memset(lsp->ls_stateid.data, 0, sizeof(lsp->ls_stateid.data));
 	atomic_set(&lsp->ls_count, 1);
-	lsp->ls_owner = fl_owner;
+	lsp->ls_pid = pid;
 	lsp->ls_parent = state;
 	INIT_LIST_HEAD(&lsp->ls_locks);
 	spin_lock(&clp->cl_lock);
@@ -551,12 +551,12 @@ nfs4_alloc_lock_state(struct nfs4_state 
  * requests.
  */
 void
-nfs4_copy_stateid(nfs4_stateid *dst, struct nfs4_state *state, fl_owner_t fl_owner)
+nfs4_copy_stateid(nfs4_stateid *dst, struct nfs4_state *state, unsigned int pid)
 {
 	if (test_bit(LK_STATE_IN_USE, &state->flags)) {
 		struct nfs4_lock_state *lsp;
 
-		lsp = nfs4_find_lock_state(state, fl_owner);
+		lsp = nfs4_find_lock_state(state, pid);
 		if (lsp) {
 			memcpy(dst, &lsp->ls_stateid, sizeof(*dst));
 			nfs4_put_lock_state(lsp);
@@ -628,7 +628,7 @@ nfs4_notify_unlck(struct inode *inode, s
 	for (fl = inode->i_flock; fl != NULL; fl = fl->fl_next) {
 		if (!(fl->fl_flags & FL_POSIX))
 			continue;
-		if (fl->fl_owner != lsp->ls_owner)
+		if (fl->fl_pid != lsp->ls_pid)
 			continue;
 		/* Exit if we find at least one lock which is not consumed */
 		if (nfs4_check_unlock(fl,request) == 0)
diff -u --recursive --new-file --show-c-function linux-2.6.7-rc1/fs/open.c linux-2.6.7-lock_nfsv4/fs/open.c
--- linux-2.6.7-rc1/fs/open.c	2004-05-29 09:06:20.000000000 -0400
+++ linux-2.6.7-lock_nfsv4/fs/open.c	2004-06-04 22:54:32.000000000 -0400
@@ -1007,7 +1007,7 @@ int filp_close(struct file *filp, fl_own
 	}
 
 	dnotify_flush(filp, id);
-	locks_remove_posix(filp, id);
+	locks_remove_posix(filp, 0);
 	fput(filp);
 	return retval;
 }
diff -u --recursive --new-file --show-c-function linux-2.6.7-rc1/include/linux/fs.h linux-2.6.7-lock_nfsv4/include/linux/fs.h
--- linux-2.6.7-rc1/include/linux/fs.h	2004-05-29 09:06:23.000000000 -0400
+++ linux-2.6.7-lock_nfsv4/include/linux/fs.h	2004-06-04 23:03:52.000000000 -0400
@@ -625,7 +625,7 @@ struct file_lock {
 	struct file_lock *fl_next;	/* singly linked list for this inode  */
 	struct list_head fl_link;	/* doubly linked list of all locks */
 	struct list_head fl_block;	/* circular list of blocked processes */
-	fl_owner_t fl_owner;
+	fl_owner_t fl_owner;		/* 0 if lock owned by a local process */
 	unsigned int fl_pid;
 	wait_queue_head_t fl_wait;
 	struct file *fl_file;
diff -u --recursive --new-file --show-c-function linux-2.6.7-rc1/include/linux/nfs_fs.h linux-2.6.7-lock_nfsv4/include/linux/nfs_fs.h
--- linux-2.6.7-rc1/include/linux/nfs_fs.h	2004-05-29 09:06:25.000000000 -0400
+++ linux-2.6.7-lock_nfsv4/include/linux/nfs_fs.h	2004-06-04 23:09:26.000000000 -0400
@@ -595,7 +595,7 @@ struct nfs4_state_owner {
 
 struct nfs4_lock_state {
 	struct list_head	ls_locks;	/* Other lock stateids */
-	fl_owner_t		ls_owner;	/* POSIX lock owner */
+	unsigned int		ls_pid;		/* pid of owner process */
 	struct nfs4_state *	ls_parent;	/* Parent nfs4_state */
 	u32			ls_seqid;
 	u32			ls_id;
@@ -665,13 +665,13 @@ extern struct nfs4_state *nfs4_find_stat
 extern void nfs4_increment_seqid(int status, struct nfs4_state_owner *sp);
 extern int nfs4_handle_error(struct nfs_server *, int);
 extern void nfs4_schedule_state_recovery(struct nfs4_client *);
-extern struct nfs4_lock_state *nfs4_find_lock_state(struct nfs4_state *state, fl_owner_t);
-extern struct nfs4_lock_state *nfs4_alloc_lock_state(struct nfs4_state *state, fl_owner_t);
+extern struct nfs4_lock_state *nfs4_find_lock_state(struct nfs4_state *state, unsigned int pid);
+extern struct nfs4_lock_state *nfs4_alloc_lock_state(struct nfs4_state *state, unsigned int pid);
 extern void nfs4_put_lock_state(struct nfs4_lock_state *state);
 extern void nfs4_increment_lock_seqid(int status, struct nfs4_lock_state *ls);
 extern void nfs4_notify_setlk(struct inode *, struct file_lock *, struct nfs4_lock_state *);
 extern void nfs4_notify_unlck(struct inode *, struct file_lock *, struct nfs4_lock_state *);
-extern void nfs4_copy_stateid(nfs4_stateid *, struct nfs4_state *, fl_owner_t);
+extern void nfs4_copy_stateid(nfs4_stateid *, struct nfs4_state *, unsigned int pid);
 
 
 

-
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html