Re: [PATCH v5 13/14] locks: skip deadlock detection on FL_FILE_PVT locks

[Richard Hipp <drh@sqlite.org>]

I have no context here.  I'm not sure what you are discussing or what
questions you have or what SQLite has to do with any of it.  Nevertheless,
I have injected a few remarks inline....


On Tue, Jan 14, 2014 at 3:29 PM, Andy Lutomirski <luto@amacapital.net>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@fieldses.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@redhat.com> wrote:
> >> > On Thu, 09 Jan 2014 12:25:25 -0800
> >> > Andy Lutomirski <luto@amacapital.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
>

Technicality:  The lock upgrade is deferred until content must be written
to disk, which in the usual case does not happen until COMMIT.


> >>
> >> Now program 1 is waiting for program 2 to release its lock.  But if
> >> program 2 tries to UPDATE, then it deadlocks.  A friendly ... SQL
> >> implementation (which, sadly, does not include sqlite) will ...
> >> abort the transaction instead.
>

SQLite fails the particular statement that needed the write lock (usually a
COMMIT) which gives the application an opportunity to either retry the
statement after a delay or to abort the transaction, as it sees fit.  The
usually practice is to pause for a few milliseconds and retry, aborting the
transaction only after many repeated failures.  There are convenience
functions (and a PRAGMA) in SQLite that make it easy for applications to
specify whatever behavior they want in this regard.



> >
> > 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, 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.)
>

SQLite uses only F_SETLK, never F_SETLKW.  Doesn't that mean that SQLite
will work the same with or without deadlock detection?  Doesn't deadlock
detection only come into play with F_SETLKW?  Or am I missing something?


>
> >
> > 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.
>
> >
> > 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.
>

See above.  SQLite uses only F_SETLK, never F_SETLKW.



>
> >
> >> The nasty case, though, is if you try to write-lock a
> >> range while holding a read-lock on only part of the range -- you could
> >> end up acquiring part of the range and deadlocking on the rest.  Now
> >> you need to remember enough state to be able to abort.
> >
> > We wait until the entire lock can be applied, and then apply it all
> > atomically (under i_lock).
> >
> >> (Actually, what happens if you receive a signal which waiting on a file
> lock?)
> >
> > Return -EINTR.
>

Huh.  SQLite is not checking for EINTR if fcntl(F_SETLK,...) fails.  Should
it be?  Or does EINTR only come up for F_SETLKW?

We do check for EINTR and retry for other system calls (read(), write(),
fallocate(), ftruncate(), close(), chmod(), open(), maybe others too).


> >
> >> I would personally be okay with removing the existing deadlock
> >> detector entirely.  I wouldn't be surprised if no one relies on it.
> >
> > I'd be in favor.
> >
> > --b.
>
> --Andy
>



-- 
D. Richard Hipp
drh@sqlite.org