Re: [PATCH v6 10/10] xen/arm: gic_events_need_delivery and irq priorities

[Stefano Stabellini <stefano.stabellini@eu.citrix.com>]

On Mon, 7 Apr 2014, Ian Campbell wrote:
> > > 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)

Yeah, I could use find_next_zero_bit instead of find_first_zero_bit.


> > > > +        {
> > > > +            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 ;-)

I think I can find a way to do both.


> > > > +            }
> > > > +            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(&current->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?

No, we need to know the highest because only if max_priority is higher
than active_priority then the function should return true.


> 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?

We need to know that exceeds the required threshold AND that it is
higher than active_priority.


> > > 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.

OK, I'll add a new patch at the end of the series.


> > 
> > 
> > > > +        return 1;
> > > > +    else
> > > > +        return 0;
> > > >  }
> > > 
> > > Ian.
> > > 
> > > 
> 
>