Re: [Xen-devel] [RFC PATCH 2/2] xen: credit2: cached attribute for next runqueue entry

[Dario Faggioli <dfaggioli@xxxxxxxx>]

On Sun, 2018-12-23 at 19:51 +0530, Praveen Kumar wrote:
> --- a/xen/common/sched_credit2.c
> +++ b/xen/common/sched_credit2.c
> @@ -473,6 +473,7 @@ struct csched2_runqueue_data {
>      spinlock_t lock;           /* Lock for this
> runqueue                     */
>  
>      struct rb_root runq;       /* Runqueue is an
> rbtree                      */
> +    struct rb_node *next_elem; /* Cached entry to run
> next                   */
>
I don't like the name much. IIRC, in Linux, the field was called
'rb_leftmost'. So we can call it rb_rightmost.

Or maybe something like rq_rightmost, or rq_first (or runq_first).

And in the comment, I'd say something like, "vcpu with highest credits
in the runq"

> @@ -1301,6 +1302,7 @@ runq_insert(const struct scheduler *ops, struct
> csched2_vcpu *svc)
>  {
>      unsigned int cpu = svc->vcpu->processor;
>      struct rb_root *runq = &c2rqd(ops, cpu)->runq;
> +    struct csched2_runqueue_data *rqd = svc->rqd;
>      int pos = 0;
>  
>      ASSERT(spin_is_locked(per_cpu(schedule_data,
> cpu).schedule_lock));
> @@ -1314,6 +1316,7 @@ runq_insert(const struct scheduler *ops, struct
> csched2_vcpu *svc)
>      ASSERT(!(svc->flags & CSFLAG_scheduled));
>  
>      rb_runq_insert(runq, svc, &pos);
> +    rqd->next_elem = rb_last(runq);
>  
Ah, ok, yes, using rb_last() here (and in runq_remove()) is indeed
better than doing it int runq_candidate().

Still not what I had in mind, though.

In fact, the whole point of this "let's cache the rightmost element"
would be to avoid having to call rb_last() pretty much at all.

How? Well, basically, inside the while() that you're adding here in
runq_insert(), you make a note about whether the new vcpu has been
inserted in the righmost spot of the tree. And if it was, you update
the cache.

Similarly, when removing a vcpu, you check whether you are removing the
rightmost element of the tree. And if you are, you update the cache.


For instance, see how they've been doing this in CFS (before the rb-
tree cached helpers were introduced), when inserting a task in the
runqueue:

https://elixir.bootlin.com/linux/v3.15/source/kernel/sched/fair.c#L490

and when removing it:

https://elixir.bootlin.com/linux/v3.15/source/kernel/sched/fair.c#L526

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