windows-byte-range-locks-20050816
authorAsanka Herath <asanka@secure-endpoints.com>
Tue, 16 Aug 2005 17:17:13 +0000 (17:17 +0000)
committerJeffrey Altman <jaltman@secure-endpoints.com>
Tue, 16 Aug 2005 17:17:13 +0000 (17:17 +0000)
commit14408c7e88c198d80ce89e90e209f48685da89da
tree5191ed9c6c97fee7c8ad358dda10c6314876c8c4
parenta09b27d0a0bdb9d967220388f76379ece4c7b5cb
windows-byte-range-locks-20050816

 Byte range locks:

   The OpenAFS Windows client has to fake byte range locks given no
   server side support for such locks.  This is implemented as keyed
   byte range locks on the cache manager.

   Keyed byte range locks:

   Each cm_scache_t structure keeps track of a list of keyed locks.
   The key for a lock is essentially a token which identifies an owner
   of a set of locks (referred to as a client).  The set of keys used
   within a specific cm_scache_t structure form a namespace that has a
   scope of just that cm_scache_t structure.  The same key value can
   be used with another cm_scache_t structure and correspond to a
   completely different client.  However it is advantageous for the
   SMB or IFS layer to make sure that there is a 1-1 mapping between
   client and keys irrespective of the cm_scache_t.

   Assume a client C has key Key(C) (although, since the scope of the
   key is a cm_scache_t, the key can be Key(C,S), where S is the
   cm_scache_t.  But assume a 1-1 relation between keys and clients).
   A byte range (O,+L) denotes byte addresses (O) through (O+L-1)
   inclusive (a.k.a. [O,O+L-1]).  The function Key(x) is implemented
   through cm_generateKey() function for both SMB and IFS.

   The cache manager will set a lock on the AFS file server in order
   to assert the locks in S->fileLocks.  If only shared locks are in
   place for S, then the cache manager will obtain a LockRead lock,
   while if there are any exclusive locks, it will obtain a LockWrite
   lock.  If the exclusive locks are all released while the shared
   locks remain, then the cache manager will downgrade the lock from
   LockWrite to LockRead.

   Lock states:

   A lock exists iff it is in S->fileLocks for some cm_scache_t
   S. Existing locks are in one of the following states: ACTIVE,
   WAITLOCK, WAITUNLOCK, LOST, DELETED.

   The following sections describe each lock and the associated
   transitions.

   1. ACTIVE: A lock L is ACTIVE iff the cache manager has asserted
      the lock with the AFS file server.  This type of lock can be
      exercised by a client to read or write to the locked region (as
      the lock allows).

      1.1 ACTIVE->LOST: When the AFS file server fails to extend a
        server lock that was required to assert the lock.

      1.2 ACTIVE->DELETED: Lock is released.

   2. WAITLOCK: A lock is in a WAITLOCK state if the cache manager
      grants the lock but the lock is yet to be asserted with the AFS
      file server.  Once the file server grants the lock, the state
      will transition to an ACTIVE lock.

      2.1 WAITLOCK->ACTIVE: The server granted the lock.

      2.2 WAITLOCK->DELETED: Lock is abandoned, or timed out during
        waiting.

      2.3 WAITLOCK->LOST: One or more locks from this client were
        marked as LOST.  No further locks will be granted to this
        client until al lost locks are removed.

   3. WAITUNLOCK: A lock is in a WAITUNLOCK state if the cache manager
      receives a request for a lock that conflicts with an existing
      ACTIVE or WAITLOCK lock.  The lock will be placed in the queue
      and will be granted at such time the conflicting locks are
      removed, at which point the state will transition to either
      WAITLOCK or ACTIVE.

      3.1 WAITUNLOCK->ACTIVE: The conflicting lock was removed.  The
        current serverLock is sufficient to assert this lock, or a
        sufficient serverLock is obtained.

      3.2 WAITUNLOCK->WAITLOCK: The conflicting lock was removed,
        however the required serverLock is yet to be asserted with the
        server.

      3.3 WAITUNLOCK->DELETED: The lock is abandoned or timed out.

      3.5 WAITUNLOCK->LOST: One or more locks from this client were
        marked as LOST.  No further locks will be granted to this
        client until all lost locks are removed.

   4. LOST: A lock L is LOST if the server lock that was required to
      assert the lock could not be obtained or if it could not be
      extended, or if other locks by the same client were LOST.
      Effectively, once a lock is LOST, the contract between the cache
      manager and that specific client is no longer valid.

      The cache manager rechecks the server lock once every minute and
      extends it as appropriate.  If this is not done for 5 minutes,
      the AFS file server will release the lock.  Once released, the
      lock cannot be re-obtained without verifying that the contents
      of the file hasn't been modified since the time the lock was
      released.  Doing so may cause data corruption.

      4.1 LOST->DELETED: The lock is released.

      4.2 LOST->ACTIVE: The lock is reassertd.  This requires
        verifying that the file was not modified in between.

      4.3 LOST->WAITLOCK: All LOST ACTIVE locks from this client were
        reasserted.  The cache manager can reinstate this waiting
        lock.

      4.4 LOST->WAITUNLOCK: All LOST ACTIVE locks from this client
        were reasserted.  The cache manager can reinstate this waiting
        lock.

   5. DELETED: The lock is no longer relevant.  Eventually, it will
      get removed from the cm_scache_t. In the meantime, it will be
      treated as if it does not exist.

      5.1 DELETED->not exist: The lock is removed from the
        cm_scache_t.

   6* A lock L is ACCEPTED if it is ACTIVE or WAITLOCK.
      These locks have been accepted by the cache manager, but may or
      may not have been granted back to the client.

   7* A lock L is QUEUED if it is ACTIVE, WAITLOCK or WAITUNLOCK.

   8* A lock L is EFFECTIVE if it is ACTIVE or LOST.

   9* A lock L is WAITING if it is WAITLOCK or WAITUNLOCK.

   Lock operation:

   A client C can READ range (Offset,+Length) of cm_scache_t S iff:

   1. for all _a_ in (Offset,+Length), one of the following is true:

       1.1 There does NOT exist an ACTIVE lock L in S->fileLocks such
         that _a_ in (L->LOffset,+L->LLength) (IOW: byte _a_ of S is
         unowned)

         AND

         For each LOST lock M in S->fileLocks such that
         _a_ in (M->LOffset,+M->LLength), M->LockType is shared AND
         M->key != Key(C).

         (Note: If this is a different client from one whose shared
         lock was LOST, then the contract between this client and the
         cache manager is indistinguishable from that where no lock
         was lost.  If an exclusive lock was lost, then the range is
         considered unsafe for consumption.)

       1.3 There is an ACTIVE lock L in S->fileLocks such that: L->key
         == Key(C) && _a_ in (L->LOffset,+L->LLength) (IOW: byte _a_
         of S is owned by C under lock L)

       1.4 There is an ACTIVE lock L in S->fileLocks such that _a_ in
         (L->LOffset,L->+LLength) && L->LockType is shared (IOW: byte
         _a_ of S is shared) AND there is no LOST lock M such that _a_
         in (M->LOffset,+M->LLength) and M->key == Key(C)

   A client C can WRITE range (Offset,+Length) of cm_scache_t S iff:

   2. for all _a_ in (Offset,+Length), one of the following is true:

       2.1 Byte _a_ of S is unowned (as above) AND for each LOST lock
         L in S->fileLocks _a_ NOT in (L->LOffset,+L->LLength).

       2.2 Byte _a_ of S is owned by C under lock L (as above) AND
         L->LockType is exclusive.

   A client C can OBTAIN a lock L on cm_scache_t S iff:

   3. for all _a_ in (L->LOffset,+L->LLength), ALL of the following is
      true:

       3.1 L->LockType is exclusive IMPLIES there does NOT exist a QUEUED lock
         M in S->fileLocks such that _a_ in (M->LOffset,+M->LLength).

         (Note: If we count all QUEUED locks then we hit cases such as
         cascading waiting locks where the locks later on in the queue
         can be granted without compromising file integrity.  On the
         other hand if only ACCEPTED locks are considered, then locks
         that were received earlier may end up waiting for locks that
         were received later to be unlocked. The choice of QUEUED
         locks were made so that large locks don't consistently get
         trumped by smaller locks which were requested later.)

       3.2 L->LockType is shared IMPLIES for each QUEUED lock M in
         S->fileLocks, if _a_ in (M->LOffset,+M->LLength) then
         M->LockType is shared.

   4. For each LOST lock M in S->fileLocks, M->key != Key(C)

         (Note: If a client loses a lock, it loses all locks.
         Subsequently, it will not be allowed to obtain any more locks
         until all existing LOST locks that belong to the client are
         released.  Once all locks are released by a single client,
         there exists no further contract between the client and AFS
         about the contents of the file, hence the client can then
         proceed to obtain new locks and establish a new contract.)

   A client C can only unlock locks L in S->fileLocks which have
   L->key == Key(C).

   The representation and invariants are as follows:

   - Each cm_scache_t structure keeps:

       - A queue of byte-range locks (cm_scache_t::fileLocks) which
         are of type cm_file_lock_t.

       - A record of the highest server-side lock that has been
         obtained for this object (cm_scache_t::serverLock), which is
         one of (-1), LockRead, LockWrite.

       - A count of ACCEPTED exclusive and shared locks that are in the
         queue (cm_scache_t::sharedLocks and
         cm_scache_t::exclusiveLocks)

   - Each cm_file_lock_t structure keeps:

       - The type of lock (cm_file_lock_t::LockType)

       - The key associated with the lock (cm_file_lock_t::key)

       - The offset and length of the lock (cm_file_lock_t::LOffset
         and cm_file_lock_t::LLength)

       - The state of the lock.

       - Time of issuance or last successful extension

   Semantic invariants:

       I1. The number of ACCEPTED locks in S->fileLocks are
           (S->sharedLocks + S->exclusiveLocks)

   External invariants:

       I3. S->serverLock is the lock that we have asserted with the
           AFS file server for this cm_scache_t.

       I4. S->serverLock == LockRead iff there is at least one ACTIVE
           shared lock, but no ACTIVE exclusive locks.

       I5. S->serverLock == LockWrite iff there is at least one ACTIVE
           exclusive lock.

       I6. If a WAITUNLOCK lock L exists in S->fileLocks, then all
           locks that L is waiting on are ahead of L in S->fileLocks.

       I7. If L is a LOST lock, then for each lock M in S->fileLocks,
           M->key == L->key IMPLIES M is LOST or DELETED.

   --asanka

====================
This delta was composed from multiple commits as part of the CVS->Git migration.
The checkin message with each commit was inconsistent.
The following are the additional commit messages.
====================

Byte range locks added to change list

====================

should improve error codes, and allow lock promotions and demotions
by releasing locks.

====================

More improvements to the byte range locking.  Handle errors caused
by a failure to have locking privs; report sharing violations when
opening files; lie about locks on read-only volumes; implement
shared read/write file creation in the smb layer.

====================

remove assertion

====================

must reference count local references to objects if the lock
is being released

====================

Do not use a variable until you assign it a value

====================

remove an unwanted assertion and move the resetting of scp->serverLock
to -1 into cm_LockMarkSCacheLost() so that others do not forget to set
it.  cm_LockMarkSCacheLost() is always called when the scp->mx is held
so it is ok to do so.
doc/txt/winnotes/afs-changes-since-1.2.txt
src/WINNT/afsd/cm.h
src/WINNT/afsd/cm_conn.c
src/WINNT/afsd/cm_scache.c
src/WINNT/afsd/cm_scache.h
src/WINNT/afsd/cm_utils.c
src/WINNT/afsd/cm_vnodeops.c
src/WINNT/afsd/cm_vnodeops.h
src/WINNT/afsd/smb.c
src/WINNT/afsd/smb.h
src/WINNT/afsd/smb3.c