|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] Re: [Xen-devel] [PATCH v6 10/10] xen/arm: gic_events_need_delivery and irq priorities
On Sun, 2014-04-06 at 20:27 +0100, Stefano Stabellini wrote:
> On Thu, 3 Apr 2014, Ian Campbell wrote:
> > On Wed, 2014-04-02 at 16:01 +0100, Stefano Stabellini wrote:
> > > gic_events_need_delivery should only return positive if an outstanding
> > > pending irq has an higher priority than the currently active irq and the
> > > priority mask.
> > > Rewrite the function by going through the priority ordered inflight and
> > > lr_queue lists.
> > >
> > > In gic_restore_pending_irqs replace lower priority pending (and not
> > > active) irqs in GICH_LRs with higher priority irqs if no more GICH_LRs
> > > are available.
> > >
> > > Signed-off-by: Stefano Stabellini <stefano.stabellini@xxxxxxxxxxxxx>
> > >
> > > ---
> > > Changes in v5:
> > > - improve in code comments;
> > > - use list_for_each_entry_reverse instead of writing my own list walker.
> > >
> > > Changes in v4:
> > > - in gic_events_need_delivery go through inflight_irqs and only consider
> > > enabled irqs.
> > > ---
> > > xen/arch/arm/gic.c | 77
> > > ++++++++++++++++++++++++++++++++++++++----
> > > xen/include/asm-arm/domain.h | 5 +--
> > > xen/include/asm-arm/gic.h | 3 ++
> > > 3 files changed, 76 insertions(+), 9 deletions(-)
> > >
> > > diff --git a/xen/arch/arm/gic.c b/xen/arch/arm/gic.c
> > > index 611990d..7faa0e9 100644
> > > --- a/xen/arch/arm/gic.c
> > > +++ b/xen/arch/arm/gic.c
> > > @@ -721,6 +721,7 @@ static void gic_clear_one_lr(struct vcpu *v, int i)
> >
> > Looking at the complete function, a better name would include "try"
> > somewhere, since it doesn't unconditionally clear things. In fact it's
> > almost more of a "sync the h/w and s/w state" function, is it?
>
> Yes, that is true. I'll rename it to gic_update_one_lr.
Thanks, I think that'll help clarify the stuff I asked about in patch #8
too.
> > > p = irq_to_pending(v, irq);
> > > if ( lr & GICH_LR_ACTIVE )
> > > {
> > > + set_bit(GIC_IRQ_GUEST_ACTIVE, &p->status);
> >
> > This appears to be unmotivated by the commit message. Is this just a
> > case of needing to more carefully manage the software ACTIVE state to
> > match the h/w?
>
> The new GIC_IRQ_GUEST_ACTIVE bit is needed to track which one (if any)
> is the currenly active irq. We need the information to calculate
> priorities in gic_events_need_delivery.
>
> I'll add a note to the commit message to clarify why we are introducing
> it.
OK, hopefully I'll understand the comment ;-)
> > If this lock free check is safe for some reason then please add a
> > comment.
> >
> > > +
> > > + spin_lock_irqsave(&v->arch.vgic.lock, flags);
> > > +
> > > list_for_each_entry_safe ( p, t, &v->arch.vgic.lr_pending, lr_queue )
> > > {
> > > i = find_first_zero_bit(&this_cpu(lr_mask), nr_lrs);
> > > - if ( i >= nr_lrs ) return;
> > > + if ( i >= nr_lrs )
> >
> > This where we find the LRs are full and we look for a lower priority
> > interrupt to evict from the LRs?
>
> Yep.
>
>
> > Isn't this check ~= lr_all_full, which
> > would be more obvious, and avoid a find_first_zero_bit in the case where
> > things are full.
>
> Consider that we are inside a list_for_each_entry_safe loop, adding
> lr_pending irqs to GICH_LR registers one by one: we need the
> find_first_zero_bit.
Shouldn't/couldn't you remember the answer from last time and start the
search from there. Currently it seems to search the whole bitmask every
time. (I think what I'm suggesting is roughly equivalent too passing i
instead of nr_lrs, with suitable initialisation and ++ of i at the
appropriate points)
> > > + {
> > > + list_for_each_entry_reverse( p_r,
> > > + &v->arch.vgic.inflight_irqs,
> > > + inflight )
> > > + {
> > > + if ( test_bit(GIC_IRQ_GUEST_VISIBLE, &p_r->status) &&
> > > + !test_bit(GIC_IRQ_GUEST_ACTIVE, &p_r->status) )
> > > + goto found;
> > > + if ( &p_r->inflight == p->inflight.next )
> > > + goto out;
> >
> > Can't we stop the search as soon as we find a higher priority interrupt
> > than the one we are trying to inject?
>
> Actually we are already doing that. Currently we stop when we find a
> suitable lower priority irq, or when the next irq in inflight_irqs is
> the same that we are already processing from lr_pending. Given that both
> lr_pending and inflight_irqs are ordered by priority (a new irq is
> inserted between the last irq with the same priority and the first with
> lower priority) and that we are walking inflight_irqs in reverse, it is
> the same as you are suggesting. We are stopping when the next in line
> is the irq we are already evaluating from lr_pending, therefore we know
> for sure that all the following irqs in inflight_irqs have the same or
> higher priority.
>
>
> > Is this nested loop O(n^2) in the number of inflight interrupts?
>
> We only run the outer loop nr_lrs times (see the lrs == 0 check).
The important thing here is how many times we run the inner loop for
each of those nr_lrs times.
> Also:
>
> - the lists are ordered by priority and we exploit that
> - lr_pending is a subset of inflight
> - we stop as soon as we exaust the lower priority irqs that we can evict
> - nr_lrs is very limited and we can at most do nr_lrs substitutions
>
> In my tests thanks to the list ordering it actually takes only one step
> of the inner loop to find an irq to evict and the case when we need to
> do any evicting at all is very rare.
>
>
> > Is there a possible algorithm which involves picking the head from
> > whichever of inflight_irqs or pending_irqs has the highest priority,
> > until the LRs are full (or the lists are empty) and then putting the
> > remainder of pending back into the inflight list?
> >
> > Or perhaps because we know that the two lists are sorted we can avoid a
> > complete search of inflight_irqs on every outer loop by remembering how
> > far we got last time and restarting there? i.e. if you gave up on an
> > interrupt with priority N+1 last time then there isn't much point in
> > checking for an interrupt with priority N this time around.
>
> This is exactly what my previous version of the patch did:
>
> http://marc.info/?l=xen-devel&m=139523245301114
>
> but you asked me to change it :-)
You mean by my asking to use the macros I ruled this approach out?
Oops ;-)
> > > + }
> > > + goto out;
> > > +
> > > +found:
> > > + i = p_r->lr;
> > > + p_r->lr = GIC_INVALID_LR;
> > > + set_bit(GIC_IRQ_GUEST_PENDING, &p_r->status);
> > > + clear_bit(GIC_IRQ_GUEST_VISIBLE, &p_r->status);
> > > + gic_add_to_lr_pending(v, p_r);
> > > + }
> > >
> > > - spin_lock_irqsave(&v->arch.vgic.lock, flags);
> > > gic_set_lr(i, p, GICH_LR_PENDING);
> > > list_del_init(&p->lr_queue);
> > > set_bit(i, &this_cpu(lr_mask));
> > > - spin_unlock_irqrestore(&v->arch.vgic.lock, flags);
> > > +
> > > + lrs--;
> > > + if ( lrs == 0 )
> > > + break;
> > > }
> > >
> > > +out:
> > > + spin_unlock_irqrestore(&v->arch.vgic.lock, flags);
> > > }
> > >
> > > void gic_clear_pending_irqs(struct vcpu *v)
> > > @@ -794,8 +825,40 @@ void gic_clear_pending_irqs(struct vcpu *v)
> > >
> > > int gic_events_need_delivery(void)
> > > {
> > > - return (!list_empty(¤t->arch.vgic.lr_pending) ||
> > > - this_cpu(lr_mask));
> > > + int mask_priority, lrs = nr_lrs;
> > > + int max_priority = 0xff, active_priority = 0xff;
> > > + struct vcpu *v = current;
> > > + struct pending_irq *p;
> > > + unsigned long flags;
> > > +
> > > + mask_priority = (GICH[GICH_VMCR] >> GICH_VMCR_PRIORITY_SHIFT) &
> > > GICH_VMCR_PRIORITY_MASK;
> > > +
> > > + spin_lock_irqsave(&v->arch.vgic.lock, flags);
> > > +
> > > + /* TODO: We order the guest irqs by priority, but we don't change
> > > + * the priority of host irqs. */
> > > + list_for_each_entry( p, &v->arch.vgic.inflight_irqs, inflight )
> > > + {
> > > + if ( test_bit(GIC_IRQ_GUEST_ACTIVE, &p->status) )
> > > + {
> > > + if ( p->priority < active_priority )
> > > + active_priority = p->priority;
> > > + } else if ( test_bit(GIC_IRQ_GUEST_ENABLED, &p->status) ) {
> > > + if ( p->priority < max_priority )
> > > + max_priority = p->priority;
> > > + }
> >
> > Can't you do the comparison against mask_priority in this loop and
> > simply return true as soon as you find an interrupt which needs an
> > upcall?
>
> We need to know the active_priority before we can return. Only if an
> outstanding irq exists with priority higher than active_priority (and
> mask_priority) we can return true.
"active_priority" here is the priority of the highest priority active
interrupt I think? You don't actually need to know what the highest is,
just that one exists which is higher than the threshold, don't you?
Likewise max_priority is the priority of highest priority interrupt
which the guest hasn't masked? Again don't you just need an existence
proof of one which exceeds the required threshold rather than the strict
highest?
> > Can't you also stop searching when p->priority > mask_priority, since
> > inflight_irqs is order you know all the rest of the list has lower
> > (numerically higher) priority,
>
> This is a good point. We can also stop as soon as we find the irq with
> GIC_IRQ_GUEST_ACTIVE, because we know than going forward all the others
> are going to have a lower priority.
> I'll make the changes.
>
>
> > > + lrs--;
> > > + if ( lrs == 0 )
> > > + break;
> > > + }
> > > +
> > > + spin_unlock_irqrestore(&v->arch.vgic.lock, flags);
> > > +
> > > + if ( max_priority < active_priority &&
> > > + (max_priority >> 3) < mask_priority )
> >
> > Why >> 3? Something to do with our emulation or the BPR?
>
> Only 5 bits are implemented for the guest irq priority, both in GICH_LRs
> and in GICH_VMCR. See gic_set_lr.
Looking at the docs it seems like the LRs have lower precision than
GICD_IPRIORITYRn, how odd. So this is a hardware limit rather an
artefact of our implementation? (I notice there are 3 reserved bits in
the LR right where the missing priority bits would sit... /me strokes
beard). I guess this ties in with GICH_APR only being 32 bits.
I'd like to see the >>3 replaced by a #define both here and gic_set_lr
please.
>
>
> > > + return 1;
> > > + else
> > > + return 0;
> > > }
> >
> > Ian.
> >
> >
_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |