Cluster Coherent NFS and Byte Range Locking

From Linux NFS

Cluster Coherent NFS and Byte Range Locking

Background

For some time, exporting byte-range locks to NFS has been a challenge in Linux. Support for file system locks was designed with a process model and a local file system in mind. This suggested a synchronous interface in which a process that requests a lock is either granted the lock or suspended and placed on a queue. When the lock becomes available, a suspended process is granted the lock and allowed to proceed.

This synchronous approach breaks down when the request is made by a server, e.g., LOCKD or NFSD, where threads are a scarce resource. The synchronous approach threatens to block the server process, which constitutes a disaster.

Hence an asynchronous lock request interface has emerged.

One of the complexities in making that transformation is a mechanism for queueing contending requests. The queue should be fair, not giving preference to one source of lock requests over another. Ideally, contending lock requests should be granted in the order in which they are issued. This argues for a single queue of pending requests, no matter their source of issue.

Cluster file systems exported with NFS introduce another layer of complexity: often they need to coordinate their locks with a lock manager in the back end. But back end coordination can be delayed, e.g., by inter-node communication, which poses another threat to a threaded server.

Finally, NFSv4 introduces one more layer of complexity: unlike NLM locks, which block, NFSv4 byte-range locks are non-blocking, so clients contending for a lock must poll. This raises the stakes for fair queueing, as a local process waiting for a lock will almost always acquire the contended lock before an NFSv4 client can.

NFSv4 Blocking Locks

Addressing fair queueing, the NFSv4 spec suggests that the server should maintain an ordered list of pending blocking locks. More broadly, queue fairness suggests that all lock requestors (local processes, LOCKD, and the NFSv4 server) should share such an ordered list.

Tasks

   * Implement a shared blocking lock fair queue
   * Implement the NFSv4 server fl_notify and use the fair queue

Progress

We have written patches that change the semantics of the existing file_lock->fl_block queue to integrate it with the NFSv4 server and to make it more 'fair.' This queue holds all blocking locks in the order in which they were requested. New blockers are added to the tail.

These patches have not been reviewed by the wider kernel community. However, the effort exposed a number of spec and implementation problems for which fixes were incorporated into the Linux kernel and the new NFSv4.1 draft.

The existing fl_block semantics:

When a lock becomes available, local blocked processes are awakened and contending NLM clients are issued a "grant" callback. Contending NFSv4 clients, on the other hand, do not block in anticipate of a server callback -- they repeatedly poll the server to discover whether the blocked lock is available.

In more detail, when a lock is released, the kernel traverses the lock's fl_block list and wakes each blocker, resulting in a 'scrum' to get the lock. The winner then places all losers on its fl_block list.

This queue is fair to contending processes in that that blockers wake in order, and it is likely that a process awakened late will find the lock already claimed. But it's not especially fair to LOCKD, which has to perform some bookeeping tasks before requesting the lock, which gives local processes an unfair advantage. And it is especially unfair to the NFSv4 server, which must wait for a contending client question to poll again before it can attempt to acquire the lock.

The new 'fair' fl_block semantics:

We tried modifying the VFS lock code so that it grants locks to queued contenders, wakes the lucky ones whose locks succeed, and returns the others to the fl_block list. We used a kernel lock to protect the fl_block list during processing. We immediately ran into a few problems:

   * Claiming the lock means calling posix_lock_file which calls kmalloc which can sleep, 
     not possible when under a spinlock; so we'd have to use a semaphore or mutex; but
   * For the purposes of mandatory lock checking, this new lock must be obtained in the
     read/write path to check for lock compliance, and adding a semaphore or mutex to
     the performance-critical read/write path is thought to be inefficient.

We investigated alternative locking schemes, however we soon identified a critical problem: an NFSv4 client that has been polling for a lock may stop polling at any time without notice. (For example, a user might grow weary of waiting for an application polling for a lock to make progress and issue an interrupt.)

Granting a lock to a client that does not want it is incorrect behavior, but benign if the lock grant can be revoked. However, in some cases it may be difficult for the server to revoke the errantly granted lock, e.g., if the lock (?) has been downgraded or coalesced with other locks. In these cases, the incorrect behavior can not be reversed with a simple unlock.

This suggests the ability to apply a new kind of byte-range lock to (?) the back end file system that allows us to temporarily block other lock requests, but that does not downgrade or coalesce existing posix locks. This allows us to remove the lock safely if the client does not return (?).

Our patches add such a lock type to the VFS lock code. After these patches, the VFS lock code again walks through the fl_block list, applying those locks it can, and waking queued contenders for newly acquired locks. This time, though, we apply the (new) non-coalescing byte-range lock. We do not upgrade the lock to a real posix byte-range lock until the contender wakes up and requests (or, optionally, cancels) the lock.

This approach sidesteps the kernel spinlock problems of the earlier scheme, since the new lock type is simple enough to be applied without requiring memory allocations.

Along the way, we identified and fixed some problems with the NFSv4 protocol:

   * The NFSv4 protocol has no equivalent to the NLM "cancel" call.  This means
     that when a client process stops blocking on a lock, the server may wait up to a
     lease period (typically about a minute) before giving up and allowing another
     waiting client to take the lock.  We found a solution that is backwards
     compatible (and thus implementable by current NFSv4.0 clients and servers), and
     also added language describing this solution to the new NFSv4.1 draft
   * The NFSv4 protocol has no equivalent to the "grant" call; clients must thus poll
     very frequently if they wish to acquire contended locks in a timely manner.
     The traditional NLM grant call is, however, has a number of known races, and is
     known to be problematic.  We therefore have proposed an alternative mechanism
     which allows a server to notify a client that a lock is available without
     committing the server to granting the lock to the client.  Speicific language
     for NFSv4.1 has been proposed and met with interest, but is awaiting working
     group concensus.

Cluster Filesystem ->lock() Interface

There is currently a filesystem ->lock() method, but it is defined only by a few filesystems that are not exported via NFS. So none of the lock routines that are used by LOCKD or the NFSv4 server bother to call those methods. Cluster filesystems would like to NFS to call their own lock methods which keep a consistant view of a lock across cluster filesystem nodes. But the current ->lock() interface is not suitable for cluster filesystems in a couple of ways.

   * We'd rather not block the NFSv4 server or LOCKD threads for longer than necessary,
     so it'd be nice to have a way to make lock requests asynchronously. This is
     particularly helpful for non-blocking locks, which do not have the option of
     returning a temporary "blocked" response and then responding with a granted callback
     later.
   * Given that in the blocking case we want the filesystem to be able to return from ->lock() 
     without having necessarily acquired the lock, we need to be able to handle the case where 
     a process on the client is interrupted and the client cancels the lock.

Tasks

   * Design and implement an asynchronous ->lock() interface
   * Have LOCKD and the NFSv4 server test for and call the new ->lock()

Progress

Since acquiring a filesystem lock may require comminication with remote hosts, and to avoid blocking lock manager threads during such communication, we allow the results to be returned asynchronously.

When a filesystem ->lock() call needs to block due to a delay in satisfying a non-blocking lock request, the file system will return -EINPROGRESS, and then later return the results with a callback registered via the lock_manager_operations struct.

An FL_CANCEL flag is added to the struct file_lock to indicate to the file system that the caller wants to cancel the provided lock.

New routines vfs_lock_file, vfs_test_lock, and vfs_cancel_lock replace posix_lock_file, posix_test_file, and posix_cancel_lock in LOCKD and the NFSv4 server. They call the new filesystem ->lock() method if it exists, else call the posix conterparts.

Status

Our solution has been tested with the GPFS file system. The relevant patches have been submitted to the Linux community, and we are responding to comments.

A major issue for acceptance is the lack of a consumer in the Linux kernel - e.g. a cluster file system with byte-range locking.