Re: [Xen-devel] [RFC PATCH 1/1] xen: credit2: rb-tree for runqueues

[Dario Faggioli <dfaggioli@xxxxxxxx>]

On Tue, 2018-04-24 at 14:30 +0530, Praveen Kumar wrote:
> Hi Dario,
> 
Hi!

> On Tuesday 17 April 2018 04:16 PM, Dario Faggioli wrote:
> > On Tue, 2018-04-03 at 22:25 +0530, Praveen Kumar wrote:
> > > 
> > > +        if ( svc->credit < entry->credit )
> > > +            node = &parent->rb_left;
> > > +        else
> > > +            node = &parent->rb_right;
> > > +
> > > +        (*pos)++;
> > > +    }
> > > +    rb_link_node(&svc->runq_elem, parent, node);
> > > +    rb_insert_color(&svc->runq_elem, root);
> > > +}
> > > 
> > Wait, where's the part where we cache which element is the one with
> > the
> > highest credits? (And the same applies to the tree-removal
> > function, of
> > course.)
> > 
> > In fact, we need a field for storing such a cache in the runqueue
> > data
> > structure as well, and we need to keep it updated.
> 
> I thought of caching the left most node as done in rb_tree, but I 
> thought of taking an easy way to have things working and delaying
> the 
> Linux rb_tree caching variant to be ported in next patch or so.
>
That is fine, as soon as the fact that you are not doing it right now,
but planning to do it in another patch is stated somewhere (e.g., cover
letter or a changelog).

> > I would suggest we do not try to use the rb_*_cached() functions,
> > and
> > cache rightmost explicitly in runqueue_data.
> 
> Ok, that sounds better, I will introduce an entry for rightmost
> element 
> to be cached in runqueue_data
> Also, lets port the Linux rb_tree cache variant as well ( probably
> in 
> future we may use that ).
>
I'm not sure about this last part. I mean, I can see other uses of rb-
trees, TBH, and ones where such caching would be useful. Still, I'll do
the port when we actually decide to use the new functionallity (or
when, e.g., we run into issues retro-fitting a Linux fix, etc).

> > Err... is it? Isn't the leftmost element the one with the _least_
> > credits? It looks to me that we want rb_last().
> > 
> > And IAC, we don't want to have to traverse the tree to get the
> > runnable
> > vcpu with the highest credit, we want it available in O(1) time.
> > 
> > That's why we want to cache it.
> 
> Yes, it looks like an error. Will update the patch in v2.
>
Right. So, I think the main problem with this patch was this one, i.e.,
the fact that the runqueue was sorted in the wrong order.

Then there is the lack of caching, for O(1) access to the head of the
runqueue itself. As said, it is ok for that to come in its own patch of
this series. It is also ok if this comes as a later patch, as soon as
that is clearly stated.

> Sure, let me have 3 series, first; Linux porting , second; rb_tree 
> changes which doesn't have caching and third; have rightmost node
> cached.
> 
I'd actually skip doing the porting right now... Although, in this
case, it's not really my call, and others may have different a opinion.

Regards,
Dario
-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Software Engineer @ SUSE https://www.suse.com/

Attachment: signature.asc
Description: This is a digitally signed message part

_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/mailman/listinfo/xen-devel