Libguestfs - May 2019 - Re: [libnbd PATCH 1/3] commands: Preserve FIFO ordering

On 5/21/19 10:09 AM, Eric Blake wrote:
> A generic client exploiting multiple in-flight commands should be
> prepared for out-of-order responses (and should probably ensure that
> there are no overlaps between parallel in-flight commands to avoid
> unspecified disk contents if the server acts on commands in an
> arbitrary order or even exposing non-atomic splicing effects).  But a
> specific client aware of a specific server's behavior of being fully
> serialized may depend on commands being processed in strict FIFO
> order, and we should not get in the way of that.  When adding commands
> to be issued, and when moving a server's reply into commands to inform
> the client about, we need to insert at the end rather than the head of
> the appropriate list.  Only the cmds_in_flight list does not have to
> care about maintaining FIFO ordering.
> ---
>  generator/states-reply.c | 13 ++++++++++---
>  lib/rw.c                 | 13 ++++++++++---
>  2 files changed, 20 insertions(+), 6 deletions(-)
If O(n) traversal through the list is painful, we could instead tweak
our storage to also store an end pointer (more bookkeeping to keep head
and tail pointers up-to-date, but then we always have O(1) insertion at
tail and removal at head).  But typically a client won't have huge
amounts of in-flight messages (qemu-nbd defaults to 16 coroutines, and
nbdkit defaults to 16 threads, at which point any further attempts to
send more requests batch up until existing in-flight commands are
drained), so I'm not sure if the algorithmic complexity reaches the
point where it will matter.

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3226
Virtualization:  qemu.org | libvirt.org

On Tue, May 21, 2019 at 10:25:49AM -0500, Eric Blake
wrote:
> On 5/21/19 10:09 AM, Eric Blake wrote:
> > A generic client exploiting multiple in-flight commands should be
> > prepared for out-of-order responses (and should probably ensure that
> > there are no overlaps between parallel in-flight commands to avoid
> > unspecified disk contents if the server acts on commands in an
> > arbitrary order or even exposing non-atomic splicing effects).  But a
> > specific client aware of a specific server's behavior of being
fully
> > serialized may depend on commands being processed in strict FIFO
> > order, and we should not get in the way of that.  When adding commands
> > to be issued, and when moving a server's reply into commands to
inform
> > the client about, we need to insert at the end rather than the head of
> > the appropriate list.  Only the cmds_in_flight list does not have to
> > care about maintaining FIFO ordering.
> > ---
> >  generator/states-reply.c | 13 ++++++++++---
> >  lib/rw.c                 | 13 ++++++++++---
> >  2 files changed, 20 insertions(+), 6 deletions(-)
> 
> If O(n) traversal through the list is painful, we could instead tweak
> our storage to also store an end pointer (more bookkeeping to keep head
> and tail pointers up-to-date, but then we always have O(1) insertion at
> tail and removal at head).  But typically a client won't have huge
> amounts of in-flight messages (qemu-nbd defaults to 16 coroutines, and
> nbdkit defaults to 16 threads, at which point any further attempts to
> send more requests batch up until existing in-flight commands are
> drained), so I'm not sure if the algorithmic complexity reaches the
> point where it will matter.
Actually commands _are_ issued in order.  The reason is not obvious
though!  It's because cmds_to_issue shouldn't be a list at all.  The
handle lock is held while we move straight into ISSUE_COMMAND.START
which moves the command to the in-flight list without blocking.

Note also: The READY state has a permitted external transition
CmdIssue -> ISSUE_COMMAND.START.  Furthermore no other state has a
CmdIssue external transition, and the generated code in the state
machine will ensure that we can never CmdIssue in any other state.

If my reasoning there is correct, we could simplify this patch by
changing cmds_to_issue to be a single command pointer.

Rich.

-- 
Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones
Read my programming and virtualization blog: http://rwmj.wordpress.com
virt-top is 'top' for virtual machines.  Tiny program with many
powerful monitoring features, net stats, disk stats, logging, etc.
http://people.redhat.com/~rjones/virt-top

On Tue, May 21, 2019 at 05:57:14PM +0100, Richard W.M. Jones
wrote:
> On Tue, May 21, 2019 at 10:25:49AM -0500, Eric Blake wrote:
> > On 5/21/19 10:09 AM, Eric Blake wrote:
> > > A generic client exploiting multiple in-flight commands should be
> > > prepared for out-of-order responses (and should probably ensure
that
> > > there are no overlaps between parallel in-flight commands to
avoid
> > > unspecified disk contents if the server acts on commands in an
> > > arbitrary order or even exposing non-atomic splicing effects). 
But a
> > > specific client aware of a specific server's behavior of
being fully
> > > serialized may depend on commands being processed in strict FIFO
> > > order, and we should not get in the way of that.  When adding
commands
> > > to be issued, and when moving a server's reply into commands
to inform
> > > the client about, we need to insert at the end rather than the
head of
> > > the appropriate list.  Only the cmds_in_flight list does not have
to
> > > care about maintaining FIFO ordering.
> > > ---
> > >  generator/states-reply.c | 13 ++++++++++---
> > >  lib/rw.c                 | 13 ++++++++++---
> > >  2 files changed, 20 insertions(+), 6 deletions(-)
> > 
> > If O(n) traversal through the list is painful, we could instead tweak
> > our storage to also store an end pointer (more bookkeeping to keep
head
> > and tail pointers up-to-date, but then we always have O(1) insertion
at
> > tail and removal at head).  But typically a client won't have huge
> > amounts of in-flight messages (qemu-nbd defaults to 16 coroutines, and
> > nbdkit defaults to 16 threads, at which point any further attempts to
> > send more requests batch up until existing in-flight commands are
> > drained), so I'm not sure if the algorithmic complexity reaches
the
> > point where it will matter.
> 
> Actually commands _are_ issued in order.  The reason is not obvious
> though!  It's because cmds_to_issue shouldn't be a list at all. 
The
> handle lock is held while we move straight into ISSUE_COMMAND.START
> which moves the command to the in-flight list without blocking.
> 
> Note also: The READY state has a permitted external transition
> CmdIssue -> ISSUE_COMMAND.START.  Furthermore no other state has a
> CmdIssue external transition, and the generated code in the state
> machine will ensure that we can never CmdIssue in any other state.
> 
> If my reasoning there is correct, we could simplify this patch by
> changing cmds_to_issue to be a single command pointer.
I've now looked at the second patch.  The reasoning above is still
correct, but I see that the second patch would require cmds_to_issue
to stay as a list because you want it to contain multiple "pre-flight"
commands, so let's not change this.

Rich.

-- 
Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones
Read my programming and virtualization blog: http://rwmj.wordpress.com
virt-df lists disk usage of guests without needing to install any
software inside the virtual machine.  Supports Linux and Windows.
http://people.redhat.com/~rjones/virt-df/