On 11/15/2011 03:57 PM, Jeff Darcy wrote:
On Mon, 14 Nov 2011 20:09:53 +0100
Edward Shishkin<edward(a)redhat.com> wrote:
> For every arrived APPTRUNC request oplock xlator updates FSOF
> by the following way:
>
> . FSOF = off + count (in the case of appending writes);
> . FSOF = off (in the case of truncates).
It's very important to specify *when* this FSOF update takes place. If
it's done too early - when a request is received rather than when it's
"issued" (allowed to proceed) - then we run the risk of
mischaracterizing later-received requests as OVWR even though they're
APPTRUNC at the time they're issued.
FSOF is an attribute of the CSL. FSOF precisely means a size that
the file will have after all requests (including the last one which
updated the FSOF) in the CSL are completed.
So we update FSOF, NEXT, NR_APPTRUNC, and other CSL attributes under
a special lock for CSL protection. I don't see any problems here.
> ESL is a queue. Every element of this queue represents a pending
> request, which waits for an exclusive access to the file. This
> element contains a record - unique (for the whole CSL!) request-id.
>
> SSL is an rb-tree of extents. Every such extent (off, count) points
> to a queue of pending requests which want to write to this interval
> (off, count). Every such request contains a unique (for the whole
> CSL!) request-id.
What about the case where an incoming request needs to go on more than
one queue?
we'll jump to (**) below
Consider the following sequence of requests.
A: offset 0, length 10
B: offset 10, length 10
C: offset 0, length 20
When A and B are received, this will result in two queues, but C needs
to follow both.
So in accordance with (**) extents (0, 10), (10, 10) will be replaced
with a single one (0, 20) and instead of 2 queues we'll have a single
one (A->B->C)
An rb-tree of non-overlapping extents is both
insufficient for this case and too complex for common ones. In the
several systems I've worked on that had to deal with the same problem
of overlapping byte ranges, it has always been sufficient to maintain a
single queue and let the dispatch code handle overlaps by checking the
queue head against *already issued* requests (guaranteed to be few
because it's under control of the dispatcher) instead of other enqueued
requests (probably still few in practice but not guaranteed to be so).
We don't even need a separate ESL and SSL (bad names BTW) because the
conflict-detecting function can serve the same purpose.
We allow different processes to write to non-overlapping regions of a
file in parallel. So instead of locking the whole filer we need to lock
respective non-overlapping regions. That said we need to maintain a
data-base of _non-overlapping_ extents, so that every such extent has a
queue of pending requests which want to write to this extent.
We can not allow processes to write to overlapping regions in parallel:
it will be a conflict with the following data corruption. Respectively
overlapping extents won't help us.
> If a primary arrived request is APPTRUNC, then oplock xlator assigns
> him a unique id as the next non-busy serial number and puts the
> request to ESL queue.
>
> If a primary arrived request (off, len) is OVRWR, then oplock xlator
> assigns him a unique id as the next non-busy serial number and puts
> this request to SSL by the following steps:
>
(**)
> . find all extents in SSL overlapped with (off, len);
> . replace all those extents and (off, len) with a single one and
> merge all their queues properly (in the resulted queue requests
> must be ordered by request-id).
>
> All requests are sent to oplock xlator by clients via ->fgetxattr().
> Offset, count, request-id, etc. are encoded to the "name" of
> extended attribute prefixed with a special magic string.
>
>
> Checking global priorities
>
>
> For every file oplock xlator maintains NEXT, an id of request which
> must get an access (exclusive, or shared) next time. The value of NEXT
> is initialized with zero value, as the first request-id is always
> zero. NEXT is incremented by oplock xlator with every access is
> granted to a secondary request.
>
> Also for every file oplock xlator maintains NR_WRITEBACK, a number
> of requests, which have been provided an access and which are
> currently in progress. NR_WRITEBACK is incremented every time when
> an access is granted to some request. ->writev_cbk() decrements
> NR_WRITEBACK counter and drops CSL_WRITEBACK flag, if it has become 0.
>
> For every arrived secondary request oplock checks its global priority:
> if its id coincides with NEXT, then arrived request has the highest
> global priority. Otherwise, if it is larger then NEXT, it has low
> global priority.
>
> Arrived secondary request can not have id smaller then NEXT.
>
> For every set of locks (ESL and SSL) oplock xlator maintains a number
> of their elements (NR_ESL and NR_SSL).
>
>
> Handling primary requests by oplock xlator
>
>
> If a primary APPTRUNC request has arrived and the common set of lock
> (CSL) is empty (NR_ESL + NR_SSL == 0) and the flag CSL_WRITEBACK is
> not set, then oplock
> . updates FSOF
> . sets a CSL_WRITEBACK flag and
> . grants an exclusive access to the client.
> In this case no requests are put to CSL (a kind of optimization).
>
> If a primary OVRWR request has arrived, or a primary APPTRUNC request
> has arrived and CSL_WRITEBACK is set, or the common set of lock (CSL)
> is not empty, then oplock xlator
> . updates FSOF (for APPTRUNC request);
> . assigns a request-id;
> . put the request to respective set (ESL or SSL).
>
>
> Handling repeated requests by oplock xlator
>
>
> For any arrived secondary request oplock xlator checks its global
> priority (see above).
>
> If the request has low global priority, then EBUSY is returned.
...and the client has to keep polling until it gets some other result?
NO.
Another approach is that fgetxattr (which asks for access) sleeps
on the server while the request has low priority. I am not sure if
it will work: we can not control the number of requests in CSL, so
client will receive en error (time out is over).
There is no way this should be our first choice, especially since
we *already have a proposal on the table* for a mechanism that uses
leases instead of polling.
Could you please say more? Leases are what? At least I can not
find such concept related to computer science in wikipedia..
There is no need to consider polling unless
and until we conclusively determine that the alternative is
insufficient.