Message-ID: <039101cf116e$56c2de80$04489b80$@mindspring.com>
Date:	Tue, 14 Jan 2014 13:19:39 -0800
From:	"Frank Filz" <ffilzlnx@...dspring.com>
To:	"'J. Bruce Fields'" <bfields@...ldses.org>,
	"'Andy Lutomirski'" <luto@...capital.net>
Cc:	"'Jeff Layton'" <jlayton@...hat.com>,
	"'Linux FS Devel'" <linux-fsdevel@...r.kernel.org>,
	<nfs-ganesha-devel@...ts.sourceforge.net>,
	<samba-technical@...ts.samba.org>, <linux-kernel@...r.kernel.org>,
	<drh@...ci.com>
Subject: RE: [PATCH v5 13/14] locks: skip deadlock detection on FL_FILE_PVT locks

> On Tue, Jan 14, 2014 at 12:29:17PM -0800, Andy Lutomirski wrote:
> > [cc: drh, who I suspect is responsible for the most widespread
> > userspace software that uses this stuff]
> >
> > On Tue, Jan 14, 2014 at 11:27 AM, J. Bruce Fields <bfields@...ldses.org>
> wrote:
> > > On Thu, Jan 09, 2014 at 04:58:59PM -0800, Andy Lutomirski wrote:
> > >> On Thu, Jan 9, 2014 at 4:49 PM, Jeff Layton <jlayton@...hat.com>
> wrote:
> > >> > On Thu, 09 Jan 2014 12:25:25 -0800 Andy Lutomirski
> > >> > <luto@...capital.net> wrote:
> > >> >> When I think of deadlocks caused by r/w locks (which these are),
> > >> >> I think of two kinds.  First is what the current code tries to
> > >> >> detect: two processes that are each waiting for each other.  I
> > >> >> don't know whether POSIX enshrines the idea of detecting that,
> > >> >> but I wouldn't be surprised, considering how awful the old POSIX
> locks are.
> > > ...
> > >> >> The sensible kind of detectable deadlock involves just one lock,
> > >> >> and it happens when two processes both hold read locks and try
> > >> >> to upgrade to write locks.  This should be efficiently
> > >> >> detectable and makes upgrading locks safe(r).
> > >
> > > This also involves two processes waiting on each other, and the
> > > current code should detect either case equally well.
> > >
> > > ...
> > >> For this kind of deadlock detection, nothing global is needed --
> > >> I'm only talking about detecting deadlocks due to two tasks
> > >> upgrading locks on the same file (with overlapping ranges) at the
same
> time.
> > >>
> > >> This is actually useful for SQL-like things.  Imagine this scenario:
> > >>
> > >> Program 1:
> > >>
> > >> Open a file
> > >> BEGIN;
> > >> SELECT whatever;  -- acquires a read lock
> > >>
> > >> Program 2:
> > >>
> > >> Open the same file
> > >> BEGIN;
> > >> SELECT whatever;  -- acquires a read lock
> > >>
> > >> Program 1:
> > >> UPDATE something;  -- upgrades to write
> > >>
> > >> Now program 1 is waiting for program 2 to release its lock.  But if
> > >> program 2 tries to UPDATE, then it deadlocks.  A friendly MySQL
> > >> implementation (which, sadly, does not include sqlite) will fail
> > >> the abort the transaction instead.
> > >
> > > And then I suppose you'd need to get an exclusive lock when you
> > > retry, to guarantee forward progress in the face of multiple
> > > processes retrying at once.
> >
> > I don't think so -- as long as deadlock detection is 100% reliable and
> > if you have writer priority,
> 
> We don't have writer priority.  Depending on how it worked I'm not
> convinced it would help.  E.g. consider the above but with 3 processes:
> 
> 	processes 1, 2, and 3 each get a whole-file read lock.
> 
> 	process 1 requests a write lock, blocks because it conflicts
> 	with read locks held by 2 and 3.
> 
> 	process 2 requests a write lock, gets -EDEADLK, unlocks and
> 	requests a new read lock.  That request succeeds because there
> 	is no conflicting lock.  (Note the lock manager had no
> 	opportunity to upgrade 1's lock here thanks to the conflict with
> 	3's lock.)

As I understand write lock priority, process 2 requesting a new read lock
would block, once there is a write lock waiter, no further read locks would
be granted that would conflict with that waiting write lock.

> 	process 3 requests a write lock, gets -EDEADLOCK, unlocks and
> 	requests a new read lock.

And then at this point, all read locks have been dropped, and there are
pending read locks blocking. The blocked write lock can now be granted. When
that lock is done, the read locks are again granted, and then we go through
the cycle again, this time with just two processes. And then one of those
processes wins the write lock race and blocks while the other gets EDEADLK
and drops it's read lock at which point of course the blocked write lock is
immediately granted. And then finally process 3 is granted it's read lock
and is able to upgrade to a write lock.

Frank

> 	Etc.
> 
> > then all that readers need to do is to drop and re-acquire the read
> > lock.  (This property is critical to avoid livelocks in SQL.  I rely
> > on it here: a deadlocked UPDATE just retries the entire transaction
> > without any special exclusive locks.)
> >
> > >
> > > I don't know, is this so useful?
> > >
> > >> It would be nice if the kernel
> > >> supported this.
> > >>
> > >> Note that unlocking and then re-locking for write is incorrect --
> > >> it would allow program 2 to write inconsistent data.
> > >>
> > >> I think that implementing this could be as simple as having some
> > >> way to check if a struct file_lock is currently trying to upgrade
> > >> from read to write and, if you try to upgrade and end up waiting
> > >> for such a lock, aborting.
> > >
> > > You have to be clear what you mean by "such a lock".  What you
> > > really want to know is whether you'd be waiting on a lock that might
> > > be waiting on a lock you hold.
> >
> > By "such a lock" I mean a read lock on the same file that's trying to
> > upgrade to write.  I think that's the main (only?) interesting case.
> > Checking for this has the nice property that you don't need to iterate
> > and you don't care whom the holder of that lock is waiting for -- if
> > it's upgrading and you overlap with it, you are certainly in the
> > deadlock case.
> 
> OK, I think.
> 
> > > To a first approximation, the current works with a graph with tasks
> > > as nodes and an arrow from node X to node Y if X is waiting on a
> > > lock held by node Y.  And it follows arrows in that graph looking for
cycles.
> > >
> > > And sure I guess it would be a bit nicer if you only bothered
> > > checking for cycles that touch this one file.
> > >
> > > But I'd really rather avoid the complication of deadlock detection
> > > unless somebody can make a really strong case that they need it.
> >
> > TBH, I suspect that the person you really want to ask is drh, who
> > writes/maintains sqlite (cc'd).  sqlite has fancy locks built on top
> > of fcntl locks.
> 
> A quick check of the sqlite source shows some complaints about posix locks
> in src/os.c.
> 
> Looks like all he's asking for his for the lock owner to be the file
descriptor not
> the pid, and for locks not to be thrown away on first close.  Those are
the two
> things jlayton addresses.
> 
> So yes I think it would be interesting to know whether some of the extra
> layer of internal sqlite locking could have been chucked if it could have
been
> based on jlayton's locks.
> 
> --b.
> --
> To unsubscribe from this list: send the line "unsubscribe linux-fsdevel"
in the
> body of a message to majordomo@...r.kernel.org More majordomo info at
> http://vger.kernel.org/majordomo-info.html

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists