[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 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(¤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? 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. > > > > > > > > _______________________________________________ Xen-devel mailing list Xen-devel@xxxxxxxxxxxxx http://lists.xen.org/xen-devel
|
Lists.xenproject.org is hosted with RackSpace, monitoring our |