[RFC] oplock with a guarantee of progress (description of the primitive) - take 2

Edward Shishkin edward at redhat.com
Thu Jun 2 20:39:13 UTC 2011


On 05/31/2011 05:33 PM, Jeff Darcy wrote:
> On 05/30/2011 10:04 AM, Edward Shishkin wrote:
>> On 05/27/2011 11:52 PM, Edward Shishkin wrote:
>>> fixed bad tabs/whitespaces stuff
>>>
>>> /*
>>>     * Oplock translator:
>>>     *
>>>     * Serialize rmw requests submission with a quarantee
>>>     * of progress.
>>>     * Maintain per-inode queues of submission requests;
>>>     *
>>>     *
>>>     * Glossary:
>>>     *
>>>     * Read-modify-write request (rmw-request)
>>>     *
>>>     * is a write request, which contains extra-data
>>>     * to write. Such requests are specific to atoimic
>>>     * cipher modes.
>>>     * Submitting an rmw request can make other pending
>>>     * rmw-requests out-of-date, and it will lead to loss
>>>     * of operations. In order to prevent this we serialize
>>>     * rmw-requests submission and make sure that every
>>>     * request which is going to be submitted contains
>>>     * uptodate information.
>
> I don't think there's any reasonable way, without wire-protocol changes,
> to pass a serial number along with a write.


It's a pity: I kept a hope that there are "legal" means of
inter-translator communication..


  The server needs to be able
> to associate a write request which consumes a lease with an earlier
> request that established the lease based only on the write request's
> "normal" characteristics such as fd/start/end.


Our initial goal is to serialize writes to the same atoms, i.e.
writes with the same (fd, start, end). So making associations
based on those parameters would be a logical mistake. Since per-atom 
serialization is not easy to implement, I suggest to consider
per-file serialization for now.

Thus, any rmw-request should have a unique id on the server. Yes,
we can obligate clients to generate such ids, so that server won't
need to pass it to the client. I think we need a simple generator,
which increments the last used value. No collisions are possible.

So you suggest to pass a generated id to the server as an xattr value
for some "magic" xattr name via ->fgetxattr(). Seems to be interesting
idea.  Oplock will need to terminate such calls to not involve IO
operations though. I'll try to develop such approach.

Thanks,
Edward.


  Another way of looking at
> it is that those normal characteristics can be combined/encoded into an
> ID for the write which ends a lease, and that same ID can be used in the
> request that begins a lease. Since the "read" part of a
> read-modify-write needs to transfer at most 2*(atom_size-1) bytes, it
> need not be an actual readv but a "magic" fgetxattr containing the ID as
> part of the xattr name. Thus, we end up with the following sequence.
>
> * client generates the ID as encode(fd,offset,length)
>
> * client generates the xattr name as "trusted.oplock." + ID
>
> * client issues an fgetxattr using the generated name
>
> * server checks for conflicts, either grants a lease or queues the
>    fgetxattr behind one that's already granted
>
> * (assuming grant) client regains control, along with head/tail pieces
>    for the read-modify-write
>
> * client encrypts and issues writev
>
> * server processes writev, ends lease, unblocks any conflicting fgetxattr
>
> The only case where this seems to fall down is when the server receives
> two requests with the same ID on the same connection (i.e. from the same
> client). Is that a retry/renewal or a separate request? Only the client
> knows, but the server doesn't actually need to care. The only reason a
> client should be retrying is after a connection timeout, so the sequence
> of events would be as follows:
>
> * client issues a lease-acquire fgetxattr, which for some reason doesn't
>    complete for a long time
>
> * client's connection times out and it establishes a new one
>
> * client retries its lease-acquire, which the server sees on a different
>    connection than the original
>
> * server detects conflict, queues the second lease-acquire
>
> * first lease-acquire times out, server throws it away
>
> * . . . progress is made . . .
>
> * second lease-acquire reached the front of the queue, is granted *with
>    current head/tail data*
>
> * client completes read-modify-write normally and correctly
>
> I think a lot of the logic below still applies; mostly the change is to
> how we communicate information between client and server.
>
> 	
>>>     *
>>>     * Request for submission (sub-request)
>>>     *
>>>     * An element in inode's rmw_queue. A sub-request is
>>>     * issued for every new rmw-request in the case when
>>>     * the file is "busy" (i.e. the rmw_queue is not empty).
>>>     * In this case a sub-request with a unique serial number
>>>     * is issued and put to the rmw-queue. With this number
>>>     * the process will uptodate and try to re-submit the
>>>     * rmw request later.
>>>     *
>>>     *
>>>     *
>>>     * struct _inode {
>>>     * ...
>>>     *
>>>     * gf_lock_t rmwq_lock;   /* protects the rmw-queue */
>>>     * rmw_queue_head_t head; /* queue of submission requests */
>>>     * uint64_t generation;   /* last allocated serial number */
>>>     * }
>
> Extending an existing structure like this would require a patch to code
> that's part of another project/package.  That means we'd have to
> overcome any resistance upstream to have the patch accepted, then wait
> for it to work its way through both Gluster's release process and the
> distro-specific (e.g. Fedora) packaging on a version that includes it.
> That could mean months before we even get back glusterfs-devel headers
> that we can compile against, let alone executables we can run against.
> Therefore it's *highly* preferable to use the inode_ctx functions to
> associate our own private data with an inode, instead of patching.
>
>>>     * lock_queue(inode) is LOCK(&inode->rmwq_lock)
>>>     * unlock_queue(inode) is UNLOCK(&inode->rmwq_lock)
>>>     */
>>>
>>> /*
>>>     * oplock_witev():
>>>     *
>>>     * Pre-condition: a read-modify-write request rmw_req
>>>     * has been received.
>>>     *
>>>     * Check if we can proceed with this.
>>>     *
>>>     * If we can not, then allocate a serial number and issue
>>>     * a sub-request if the rmw-req is new (i.e. it doesn't
>>>     * have a serial number and we didn't try to submit this
>>>     * request before). Than return error to re-submit this
>>>     * later.
>>>     */
>>>
>>> oplock_witev()
>>> {
>>> 	lock_queue(inode);
>>>
>>> 	if (the inode's rmw_queue is empty) {
>>>
>>> 	empty:
>>> 		/*
>>> 		 * submit this rmw_req, but first
>>> 		 * we need to "occupy the queue
>>> 		 */
>>> 		allocate a serial number;
>>> 		create a sub-request and insert it to the queue";
>>> 		goto submit;
>>> 	}
>>> 	else {
>>> 		if (is_new_request(rmw_req)) {
>>> 			/*
>>> 			 * queue is not empty, so we are not
>>> 			 * allowed to proceed (there are
>>> 			 * requests with higher priorities
>>> 			 */
>>>
>>> 			allocate a serial number,
>>> 			create a sub-request and insert it to the queue;
>>>
>>> 			/*
>>> 			 * refuse to proceed, will be
>>> 			 * restarted with this serial
>>> 			 * number later
>>> 			 */
>>> 			goto refuse;
>>> 		}
>>> 		/*
>>> 		 * queue is not empty and rmw_req is
>>> 		 * not new (has serial number)
>>> 		 */
>>> 	next:
>>> 		find the next sub_req in the queue;
>>> 		if (sub_req is too old, timeout is over) {
>>> 			/* the owner has died */
>>> 			remove sub_req;
>>> 			if (rmw_queue is empty)
>>> 				goto empty;
>>> 			else
>>> 				goto next;
>>> 		}
>>> 		if (serial_number_of(rmw_req) != serial_number_of(next_sub_req){
>>> 			/*
>>> 			 * this is not our turn to submit
>>> 			 */
>>> 	refuse:
>>> 			unlock_queue(inode);
>>> 			/*
>>> 			 * refuse to proceed,
>>> 			 * will be re-submitted
>>> 			 */
>>> 			op_errno = EBUSY;
>>> 			STACK_UNWIND();
>>> 			return;
>>> 	}
>>> 	submit:
>>> 		/*
>>> 		 * our turn to submit,
>>> 		 * allow to proceed
>>> 		 */
>
> The above might be a bit clearer this way:
>
> 	/* Called from fgetxattr, writev, writev_cbk, "cleaner" thread. */
> 	drain_queue (queue)
> 	{
> 		while (!is_empty(queue)&&  is_timed_out(queue->head)) {
> 			/* Client's request is waiting, must reply */
> 			STACK_UNWIND(queue->head);
> 			dequeue_and_discard(queue);
> 		}
> 	}
>
> 	...		
>
> 	lock_queue();
> 	if (!is_empty(queue)&&  id_match(queue->head,new_req)) {
> 		status = OK;
> 	}
> 	else {
> 		status = LEASE_EXPIRED;
> 	}
> 	unlock_queue();
> 	if (status == OK) {
> 		STACK_WIND(...);
> 	}
> 	return status;
>
> Note that things become more complex if we allow a fully aligned write
> to be processed as a single writev without a preceding lease-acquire
> read/getxattr.  In that case we do want to check for conflicting leases,
> but create a lease "on the fly" and let the write progress if it's fully
> aligned, so the middle part of the snippet above becomes:
>
> 	if (is_fully_aligned(new_req)) {
> 		if (is_empty(queue)) {
> 			status = OK;
> 		}
> 		else {
> 			status = BLOCKED;
> 		}
> 		create_and_enqueue_request(new_req);
> 	}
> 	else {
> 		/* empty/id_match checks as above */
> 	}
>
>> Hmm, bad...
>> this is out turn to submit, but rmw-request can be not
>> uptodate. So we'll need to visit server at least 2 times.
>> The common scenario is:
>>
>> 1) go to the server side and put a sub-request to the
>>      queue, return EBUSY to the client.
>> 2) check the queue. If this is our turn to submit, then
>>      update a rmw-request on the client side and go back
>>      to the server to submit (our sub-request is waiting
>>      for us in the queue). Otherwise repeat step (2).
>>
>>
>>> 		unlock_queue(inode);
>>> 		STACK_WIND();
>>> 		return;
>>> 	}
>>> }
>>>
>>> /*
>>>     * this is called only if we
>>>     * were allowed to submit.
>>>     */
>>> oplock_writew_cbk()
>>> {
>>> 	if (op_ret>   = 0) {
>>> 		/*
>>> 		 * it was our turn to submit, and our
>>> 		 * rmw-request has been successfully
>>> 		 * submitted
>>> 		 */
>>> 		lock_queue(inode);
>>> 		remove the sub-request from the queue;
>>> 		unlock_queue(inode);
>>> 	}
>>> 	else {
>>> 		/*
>>> 		 * it was our turn to submit, but error
>>> 		 * happened in other layers, so don't remove
>>> 		 * sub-request, will retry.
>>> 		 */
>>> 		STACK_UNWIND();
>>> 	}
>>> }
>
> I think we want to dequeue and STACK_UNWIND regardless, and *also*
> STACK_WIND if another request was blocked behind us.  For example:
>
> 	lock_queue();
> 	old_req = dequeue_request(queue); /* this one must be ours */
> 	drain_queue();
> 	need_wind = !is_empty(queue);
> 	unlock_queue();
> 	if (need_wind) {
> 		STACK_WIND(queue->head);
> 	}
> 	STACK_UNWIND(old_req);
> 		
> This depends on the STACK_WIND working regardless of whether the request
> we're unblocking is an fgetxattr (for an unaligned read-modify-write) or
> a writev (for an aligned write).  I think we can ensure that by using
> the "stub" mechanism developed for the dht translator; if not, we'll
> have to store flags etc. and deal with it ourselves.
> _______________________________________________
> cloudfs-devel mailing list
> cloudfs-devel at lists.fedorahosted.org
> https://fedorahosted.org/mailman/listinfo/cloudfs-devel



More information about the cloudfs-devel mailing list