|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] Re: [Xen-devel] [RFC PATCH v2 1/2] xen: credit2: rb-tree for runqueues
On Sun, 2018-12-23 at 19:51 +0530, Praveen Kumar wrote:
> diff --git a/xen/common/sched_credit2.c b/xen/common/sched_credit2.c
> index 623a325ceb..2463a25f87 100644
> --- a/xen/common/sched_credit2.c
> +++ b/xen/common/sched_credit2.c
> @@ -471,7 +472,7 @@ custom_param("credit2_runqueue",
> parse_credit2_runqueue);
> struct csched2_runqueue_data {
> spinlock_t lock; /* Lock for this
> runqueue */
>
> - struct list_head runq; /* Ordered list of runnable
> vms */
> + struct rb_root runq; /* Runqueue is an
> rbtree */
>
I wouldn't change the comment. It's useful to know that the idea is to
use this field to keep a list of runnable vcpus, and that we want it to
be ordered, which is what the comment currently says.
It's pointless to state that we're using an rb-tree, because once can
tell that, by just looking at the data type.
Actually, the comment says "Ordered list of runnable vms", while I
think it would be better if it said "Ordered list of runnable vcpus".
Changing "vms" to "vcpus" does not belong in this patch, strictly
speaking, but if you want to do that, I could live with that. If you
don't want to do it, then don't, and just leave the comment alone.
> @@ -604,6 +605,28 @@ static inline bool has_cap(const struct
> csched2_vcpu *svc)
> return svc->budget != STIME_MAX;
> }
>
> +static void rb_runq_insert(struct rb_root *root,
> + struct csched2_vcpu *svc,
> + int *pos)
> +{
> + struct csched2_vcpu *entry = NULL;
>
I'd call this (something like) 'parent_svc'.
It makes it easier to understand what's actually happening in the loop
below.
> + struct rb_node **node = &root->rb_node;
> + struct rb_node *parent = NULL;
> +
> + while (*node) {
> + parent = *node;
> + entry = rb_entry(parent, struct csched2_vcpu, runq_elem);
> + if ( svc->credit < entry->credit )
> + node = &parent->rb_left;
> + else
> + node = &parent->rb_right;
> +
> + (*pos)++;
> + }
> @@ -1789,6 +1803,7 @@ static void park_vcpu(struct csched2_vcpu *svc)
> * In both cases, we also add it to the list of parked vCPUs of
> the domain.
> */
> __set_bit(_VPF_parked, &v->pause_flags);
> +
> if ( vcpu_on_runq(svc) )
> {
> runq_remove(svc);
>
Unrelated change. Don't do it. :-)
> @@ -2087,6 +2102,8 @@ csched2_vcpu_sleep(const struct scheduler *ops,
> struct vcpu *vc)
> }
> else if ( vcpu_on_runq(svc) )
> {
> + printk(XENLOG_WARNING "%s : %d : vcpu on runq rb !\n",
> __func__, __LINE__);
> +
>
So, this, and all the various other lines similar to this are/have been
useful for debugging, I guess?
That is ok, but I don't think they should land upstream. If you think
they (or maybe some of them) should, then make it/them proper debugging
output.
And, probably, do that in its own patch, as it would not be related to
what the data structure used for the runqueues is.
But again, IMO, you can get rid of all of them.
> ASSERT(svc->rqd == c2rqd(ops, vc->processor));
> update_load(ops, svc->rqd, svc, -1, NOW());
> runq_remove(svc);
> @@ -2764,8 +2783,10 @@ csched2_vcpu_migrate(
> if ( unlikely(!cpumask_test_cpu(new_cpu,
> cpupool_domain_cpumask(d))) )
> {
> ASSERT(system_state == SYS_STATE_suspend);
> +
> if ( vcpu_on_runq(svc) )
> {
>
Stray new-line again.
> @@ -3206,17 +3227,18 @@ csched2_runtime(const struct scheduler *ops,
> int cpu,
> * 2) If there's someone waiting whose credit is positive,
> * run until your credit ~= his.
> */
> - if ( ! list_empty(runq) )
> + if ( ! RB_EMPTY_ROOT(runq) )
> {
> - struct csched2_vcpu *swait = runq_elem(runq->next);
> + // Find the left most element, which is the most probable
> candidate
> + struct rb_node *node = rb_last(runq);
>
Comment style. And I think I'd say "Check the rightmost element in the
tree, which is the one with the highest credits"
> + struct csched2_vcpu *swait = runq_elem(node);
>
I think we can do:
struct csched2_vcpu *swait = runq_elem(rb_last(runq));
Yeah, matter of taste, mostly. Still...
Anyway, if you keep the code like this, no blanks in-between
definitions. And you instead want one between the last definition and
the if below.
> if ( ! is_idle_vcpu(swait->vcpu)
> && swait->credit > 0 )
> {
> rt_credit = snext->credit - swait->credit;
> }
> }
> -
> /*
> * The next guy on the runqueue may actually have a higher
> credit,
>
Spurious change.
> * if we've tried to avoid migrating him from a different cpu.
> @@ -3350,9 +3372,8 @@ runq_candidate(struct csched2_runqueue_data
> *rqd,
> snext = csched2_vcpu(idle_vcpu[cpu]);
>
> check_runq:
> - list_for_each_safe( iter, temp, &rqd->runq )
> - {
> - struct csched2_vcpu * svc = list_entry(iter, struct
> csched2_vcpu, runq_elem);
> + for (iter = rb_last(&rqd->runq); iter != NULL; iter =
> rb_prev(iter)) {
> + struct csched2_vcpu * svc = rb_entry(iter, struct
> csched2_vcpu, runq_elem);
>
I was about to comment about the fact that doing a for() is not the
same as doing the list_for_each_safe() (because of the *_safe() part).
However, looking better, I don't think I see why list_for_each_safe()
(I mean, as opposed to just list_for_each()) was used in the first
place.
So, yes, I think this is actually ok. Anyone, if there's something I'm
missing, please, point it out. :-D
> @@ -3762,8 +3784,8 @@ csched2_dump(const struct scheduler *ops)
> dump_pcpu(ops, j);
>
> printk("RUNQ:\n");
> - list_for_each( iter, runq )
> - {
> +
> + for (iter = rb_last(runq); iter != NULL; iter =
> rb_prev(iter)) {
> struct csched2_vcpu *svc = runq_elem(iter);
>
> if ( svc )
>
Ok, this makes sense. Have you verified that the runqueue is printed in
credits order in the dump?
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 _______________________________________________ Xen-devel mailing list Xen-devel@xxxxxxxxxxxxxxxxxxxx https://lists.xenproject.org/mailman/listinfo/xen-devel
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |