[Spice-devel] [PATCH 10/11] Make sure link in RedPipeItem can be not the first field

[Frediano Ziglio]

> 
> In general, this is a good idea, but I question why you're doing it now.
> There
> are patches already in the refactory branch which change the PipeItem ring
> into
> a GList (although perhaps GQueue might be more appropriate). That patch would
> also fix the underlying issue you're solving here. So having both patches
> just
> creates more work for no benefit.
> 
> Jonathon
> 

It all started when I found, in a couple of cases that moving/removing
fields from some structures caused no compilation errors but occasional
crashes. I tried to remove any hidden assumption from the code for
structure layout. I don't remember if RedPipeItem was (I don't think so)
one of these cases but it was on the way.
I'll keep the patch to make sure your patch (or any similar) touch
(and avoid) such situations for RedPipeItem.

About your patch. Obviously a GQueue is better than a GList :-) !
The pipe is a structure that implements a queue.

Some O considerations
                ring    GList   GQueue
prepend item    O(1)    O(1)    O(1)
append item     O(1)    O(n)    O(1)
remove item     O(1)    O(n)    O(n)
remove link     O(1)    O(1)    O(1)
getting tail    O(1)    O(n)    O(1)
counting items  O(n)    O(n)    O(n)
check linked    O(1)    O(n)    O(n)

I tried to have a look at your patch and possible "O" consideration
on order of different algorithms used. After moving to a queue
(removing "append item" and "getting tail" difference) and using
some link (to change "remove item" to a "remote link") there are
unfortunately some "check linked" checks in some O(n**2) paths which
could potentially lead to O(n**4). Considering that n could be
in number or 100/1000 are potentially quite slower than before.
More study should be done however the only practical reason for the
change is to support inserting the same item to different queue
and this is currently used only for CharDevice and multiple clients.
I would feel much more comfortable to rollback (or move to a similar
behavior) the patch that introduced the problem with multiple clients.
The paths above are in section of the code we are not really familiar
with (I posted some question on ML and got no answers).
On the same issue does it make sense to support multiple clients for
SpiceVmc/Smartcards? Would an USB device attached to a SpiceVmc work
having multiple clients?

Frediano