locking.txt

SIP 1.5.0源代码

	 UNIX Advisory File Locking Implications on c-client
		    Mark Crispin, 28 November 1995


	THIS DOCUMENT HAS BEEN UPDATED TO REFLECT THE CODE IN THE
	IMAP-4 TOOLKIT AS OF NOVEMBER 28, 1995.  SOME STATEMENTS
	IN THIS DOCUMENT DO NOT APPLY TO EARLIER VERSIONS OF THE
	IMAP TOOLKIT.

INTRODUCTION

     Advisory locking is a mechanism by which cooperating processes
can signal to each other their usage of a resource and whether or not
that usage is critical.  It is not a mechanism to protect against
processes which do not cooperate in the locking.

     The most basic form of locking involves a counter.  This counter
is -1 when the resource is available.  If a process wants the lock, it
executes an atomic increment-and-test-if-zero.  If the value is zero,
the process has the lock and can execute the critical code that needs
exclusive usage of a resource.  When it is finished, it sets the lock
back to -1.  In C terms:

  while (++lock)		/* try to get lock */
    invoke_other_threads ();	/* failed, try again */
   .
   .	/* critical code  here */
   .
  lock = -1;			/* release lock */

     This particular form of locking appears most commonly in
multi-threaded applications such as operating system kernels.  It
makes several presumptions:
 (1) it is alright to keep testing the lock (no overflow)
 (2) the critical resource is single-access only
 (3) there is shared writeable memory between the two threads
 (4) the threads can be trusted to release the lock when finished

     In applications programming on multi-user systems, most commonly
the other threads are in an entirely different process, which may even
be logged in as a different user.  Few operating systems offer shared
writeable memory between such processes.

     A means of communicating this is by use of a file with a mutually
agreed upon name.  A binary semaphore can be passed by means of the
existance or non-existance of that file, provided that there is an
atomic means to create a file if and only if that file does not exist.
In C terms:

				/* try to get lock */
  while ((fd = open ("lockfile",O_WRONLY|O_CREAT|O_EXCL,0666)) < 0)
    sleep (1);			/* failed, try again */
  close (fd);			/* got the lock */
   .
   .	/* critical code  here */
   .
  unlink ("lockfile"); 		/* release lock */

     This form of locking makes fewer presumptions, but it still is
guilty of presumptions (2) and (4) above.  Presumption (2) limits the
ability to have processes sharing a resource in a non-conflicting
fashion (e.g. reading from a file).  Presumption (4) leads to
deadlocks should the process crash while it has a resource locked.

     Most modern operating systems provide a resource locking system
call that has none of these presumptions.  In particular, a mechanism
is provided for identifying shared locks as opposed to exclusive
locks.  A shared lock permits other processes to obtain a shared lock,
but denies exclusive locks.  In other words:

	current state		want shared	want exclusive
	-------------		-----------	--------------
	 unlocked		 YES		 YES
	 locked shared		 YES		 NO
	 locked exclusive	 NO		 NO

     Furthermore, the operating system automatically relinquishes all
locks held by that process when it terminates.

     A useful operation is the ability to upgrade a shared lock to
exclusive (provided there are no other shared users of the lock) and
to downgrade an exclusive lock to shared.  It is important that at no
time is the lock ever removed; a process upgrading to exclusive must
not relenquish its shared lock.

     Most commonly, the resources being locked are files.  Shared
locks are particularly important with files; multiple simultaneous
processes can read from a file, but only one can safely write at a
time.  Some writes may be safer than others; an append to the end of
the file is safer than changing existing file data.  In turn, changing
a file record in place is safer than rewriting the file with an
entirely different structure.


FILE LOCKING ON UNIX

     In the oldest versions of UNIX, the use of a semaphore lockfile
was the only available form of locking.  Advisory locking system calls
were not added to UNIX until after the BSD vs. System V split.  Both
of these system calls deal with file resources only.

     Most systems only have one or the other form of locking.  AIX
emulates the BSD form of locking as a jacket into the System V form.
Ultrix and OSF/1 implement both forms.

BSD

     BSD added the flock() system call.  It offers capabilities to
acquire shared lock, acquire exclusive lock, and unlock.  Optionally,
the process can request an immediate error return instead of blocking
when the lock is unavailable.


FLOCK() BUGS

     flock() advertises that it permits upgrading of shared locks to
exclusive and downgrading of exclusive locks to shared, but it does so
by releasing the former lock and then trying to acquire the new lock.
This creates a window of vulnerability in which another process can
grab the exclusive lock.  Therefore, this capability is not useful,
although many programmers have been deluded by incautious reading of
the flock() man page to believe otherwise.  This problem can be
programmed around, once the programmer is aware of it.

     flock() always returns as if it succeeded on NFS files, when in
fact it is a no-op.  There is no way around this.

     Leaving aside these two problems, flock() works remarkably well,
and has shown itself to be robust and trustworthy.

SYSTEM V/POSIX

     System V added new functions to the fnctl() system call, and a
simple interface through the lockf() subroutine.  This was
subsequently included in POSIX.  Both offer the facility to apply the
lock to a particular region of the file instead of to the entire file.
lockf() only supports exclusive locks, and calls fcntl() internally;
hence it won't be discussed further.

     Functionally, fcntl() locking is a superset of flock(); it is
possible to implement a flock() emulator using fcntl(), with one minor
exception: it is not possible to acquire an exclusive lock if the file
is not open for write.

     The fcntl() locking functions are: query lock station of a file
region, lock/unlock a region, and lock/unlock a region and block until
have the lock.  The locks may be shared or exclusive.  By means of the
statd and lockd daemons, fcntl() locking is available on NFS files.

     When statd is started at system boot, it reads its /etc/state
file (which contains the number of times it has been invoked) and
/etc/sm directory (which contains a list of all remote sites which are
client or server locking with this site), and notifies the statd on
each of these systems that it has been restarted.  Each statd then
notifies the local lockd of the restart of that system.

     lockd receives fcntl() requests for NFS files.  It communicates
with the lockd at the server and requests it to apply the lock, and
with the statd to request it for notification when the server goes
down.  It blocks until all these requests are completed.

     There is quite a mythos about fcntl() locking.

     One religion holds that fcntl() locking is the best thing since
sliced bread, and that programs which use flock() should be converted
to fcntl() so that NFS locking will work.  However, as noted above,
very few systems support both calls, so such an exercise is pointless
except on Ultrix and OSF/1.

     Another religion, which I adhere to, has the opposite viewpoint.


FCNTL() BUGS

     For all of the hairy code to do individual section locking of a
file, it's clear that the designers of fcntl() locking never
considered some very basic locking operations.  It's as if all they
knew about locking they got out of some CS textbook with not
investigation of real-world needs.

     It is not possible to acquire an exclusive lock unless the file
is open for write.  You could have append with shared read, and thus
you could have a case in which a read-only access may need to go
exclusive.  This problem can be programmed around once the programmer
is aware of it.

     If the file is opened on another file designator in the same
process, the file is unlocked even if no attempt is made to do any
form of locking on the second designator.  This is a very bad bug.  It
means that an application must keep track of all the files that it has
opened and locked.

     If there is no statd/lockd on the NFS server, fcntl() will hang
forever waiting for them to appear.  This is a bad bug.  It means that
any attempt to lock on a server that doesn't run these daemons will
hang.  There is no way for an application to request flock() style
``try to lock, but no-op if the mechanism ain't there''.

     There is a rumor to the effect that fcntl() will hang forever on
local files too if there is no local statd/lockd.  These daemons are
running on mailer.u, although they appear not to have much CPU time.