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

[Ian Campbell <Ian.Campbell@xxxxxxxxxx>]

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?

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

>          /* HW interrupts cannot be ACTIVE and PENDING */
>          if ( p->desc == NULL &&
>               test_bit(GIC_IRQ_GUEST_ENABLED, &p->status) &&


> @@ -735,6 +736,7 @@ static void gic_clear_one_lr(struct vcpu *v, int i)
>          if ( p->desc != NULL )
>              p->desc->status &= ~IRQ_INPROGRESS;
>          clear_bit(GIC_IRQ_GUEST_VISIBLE, &p->status);
> +        clear_bit(GIC_IRQ_GUEST_ACTIVE, &p->status);

Same as above I guess?

>          p->lr = GIC_INVALID_LR;
>          if ( test_bit(GIC_IRQ_GUEST_PENDING, &p->status) &&
>                  test_bit(GIC_IRQ_GUEST_ENABLED, &p->status))
> @@ -763,22 +765,51 @@ void gic_clear_lrs(struct vcpu *v)
>  
>  static void gic_restore_pending_irqs(struct vcpu *v)
>  {
> -    int i;
> -    struct pending_irq *p, *t;
> +    int i = 0, lrs = nr_lrs;
> +    struct pending_irq *p, *t, *p_r;
>      unsigned long flags;
>  
> +    if ( list_empty(&v->arch.vgic.lr_pending) )
> +        return;

This is unlocked, according to the previous patch access to lr_pending
is supposed to be protected by vgic.lock.

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

Also a comment explaining that we are looking to evict a lower priority
interrupt would be useful. Do we not need to check for LRs which can
simply be cleared? I suppose that must happen elsewhere.

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

Is this nested loop O(n^2) in the number of inflight interrupts?

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.

I'm also unsure why this function both uses find_first_zero_bit and
counts the lrs it has unassigned in the "lrs" variable. Is one or the
other not sufficient?

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

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,

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

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

Ian.



_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel