[OpenAFS-win32-devel] New client-side locking implementation

[Asanka Herath]

Hello,

The following is a draft of the new file locking implementation that will
replace the current not-very-functional locks. Discuss.

/* 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.  The logistics of generating
   useful keys are dealt with at the SMB server and IFS layer.

   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).  In the keyed lock
   implementation in the cache manager code, a key is represented as
   an unsigned 32 bit quantity.  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 left upto the
   SMB and IFS layer to figure out.

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

   A client C can read range (O,L) of cm_scache_t S iff:

   1. for all _a_ in (O,L), one of the following is true:

       1.1 There does NOT exist a VALID or LOST lock L in S->fileLocks
         such that _a_ in (L->LOffset,L->LLength) (IOW: byte _a_ of S
         is unowned)

       1.2 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.3 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 under lock L)

   A client C can write range (O,L) of cm_scache_t S iff:

   2. for all _a_ in (O,L), one of the following is true:

       2.1 Byte _a_ of S is unowned (as above)

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

   A client C can lock range (O,L) of cm_scache_t S iff:

   3 for all _a_ in (O,L), the following is true:

       3.1 Byte _a_ is unowned (as above)

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

   Note:

   1. A lock L is VALID if it exists and is not INVALID.  A lock that
      is WAITING is still valid.  A lock will be in a waiting state
      (WAITING) from the time the cache manager accepts the lock until
      the AFS file server acknowledges the lock.

   2. A lock L is ACTIVE if it is VALID is not in a waiting
      state. I.e. the cache manager has asserted the lock with the AFS
      file server.

   3. A lock L is LOST if it was formerly VALID or ACTIVE but the
      cache manager failed to extend the lock.  The cache manager
      rechecks locks once every minute and extends them.  If this is
      not done for 5 minutes, the AFS file server will release the
      lock.  Once release, 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.

   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 VALID 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.  Whether it is VALID or INVALID, and
         if VALID, whether it is in a WAITING state or not.  If the
         lock is VALID and not WAITING, then it's ACTIVE.

   Semantic invariants:

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

       I2. If L1 and L2 are both VALID locks in S->fileLocks, then L1
           and L2 do NOT overlap. (enforced by 3.1 above)

   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.

   --asanka
 */