[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

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,


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
highest credits? (And the same applies to the tree-removal
function, of

In fact, we need a field for storing such a cache in the runqueue
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
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,
cache rightmost explicitly in runqueue_data.

Ok, that sounds better, I will introduce an entry for rightmost
to be cached in runqueue_data
Also, lets port the Linux rb_tree cache variant as well ( probably
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
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

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.



Xen-devel mailing list



Lists.xenproject.org is hosted with RackSpace, monitoring our
servers 24x7x365 and backed by RackSpace's Fanatical Support®.