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.
git://git.openafs.org / openafs.git / log