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

[Praveen Kumar <kpraveen.lkml@xxxxxxxxx>]

On Tuesday 24 April 2018 04:33 PM, Dario Faggioli wrote:
> 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).
Sure, I am fine with that too.

> > > 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.
Ok. Working on the same.

> > 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.
Sure, I am fine with not including the porting work as part of this 
patch. Probably, we may take this as a different activity as you 
mentioned above.
Regards,

~Praveen.

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