Re: [Xen-devel] [RFC PATCH 23/49] ARM: new VGIC: Add IRQ sorting

[Christoffer Dall <christoffer.dall@xxxxxxxxxx>]

On Tue, Feb 13, 2018 at 3:56 PM, Andre Przywara
<andre.przywara@xxxxxxxxxx> wrote:
> Hi,
>
> Christoffer, Eric, Marc,
> a question about locking order between multiple IRQs below. Could you
> have a brief look, please?
>
> On 13/02/18 12:30, Julien Grall wrote:
>> Hi Andre,
>>
>> On 09/02/18 14:39, Andre Przywara wrote:
>>> Adds the sorting function to cover the case where you have more IRQs
>>> to consider than you have LRs. We consider their priorities.
>>> This pulls in Linux' list_sort.c , which is a merge sort implementation
>>> for linked lists.
>>>
>>> This is based on Linux commit 8e4447457965, written by Christoffer Dall.
>>>
>>> Signed-off-by: Andre Przywara <andre.przywara@xxxxxxxxxx>
>>> ---
>>>   xen/arch/arm/vgic/vgic.c    |  59 +++++++++++++++
>>>   xen/common/list_sort.c      | 170
>>> ++++++++++++++++++++++++++++++++++++++++++++
>>>   xen/include/xen/list_sort.h |  11 +++
>>
>> You need to CC "THE REST" maintainers for this code. It would also make
>> sense to have a separate patch for adding list_sort.c
>
> Yeah, will do.
>
>>>   3 files changed, 240 insertions(+)
>>>   create mode 100644 xen/common/list_sort.c
>>>   create mode 100644 xen/include/xen/list_sort.h
>>>
>>> diff --git a/xen/arch/arm/vgic/vgic.c b/xen/arch/arm/vgic/vgic.c
>>> index f517df6d00..a4efd1fd03 100644
>>> --- a/xen/arch/arm/vgic/vgic.c
>>> +++ b/xen/arch/arm/vgic/vgic.c
>>> @@ -16,6 +16,7 @@
>>>    */
>>>     #include <asm/bug.h>
>>> +#include <xen/list_sort.h>
>>>   #include <xen/sched.h>
>>>     #include <asm/arm_vgic.h>
>>> @@ -163,6 +164,64 @@ static struct vcpu *vgic_target_oracle(struct
>>> vgic_irq *irq)
>>>       return NULL;
>>>   }
>>>   +/*
>>> + * The order of items in the ap_lists defines how we'll pack things
>>> in LRs as
>>> + * well, the first items in the list being the first things populated
>>> in the
>>> + * LRs.
>>> + *
>>> + * A hard rule is that active interrupts can never be pushed out of
>>> the LRs
>>> + * (and therefore take priority) since we cannot reliably trap on
>>> deactivation
>>> + * of IRQs and therefore they have to be present in the LRs.
>>> + *
>>> + * Otherwise things should be sorted by the priority field and the GIC
>>> + * hardware support will take care of preemption of priority groups etc.
>>> + *
>>> + * Return negative if "a" sorts before "b", 0 to preserve order, and
>>> positive
>>> + * to sort "b" before "a".
>>
>> Finally a good explanation of the return value of a sort function :). I
>> always get confused what the return is supposed to be.
>>
>>> + */
>>> +static int vgic_irq_cmp(void *priv, struct list_head *a, struct
>>> list_head *b)
>>> +{
>>> +    struct vgic_irq *irqa = container_of(a, struct vgic_irq, ap_list);
>>> +    struct vgic_irq *irqb = container_of(b, struct vgic_irq, ap_list);
>>> +    bool penda, pendb;
>>> +    int ret;
>>> +
>>> +    spin_lock(&irqa->irq_lock);
>>> +    spin_lock(&irqb->irq_lock);
>>
>> I guess the locking order does not matter here because this is the only
>> place where two IRQs lock have to be taken?
>
> Mmh, good question. I guess indeed in practice this will not be a problem:
> - As you mentioned this should be the only(?) place where we take
> multiple IRQ locks, but that sounds fragile.
> - A certain IRQ should only be on one VCPU list at a given point in
> time. So there would be no race with two instances of this compare
> function trying to lock the same IRQ.
>
> But that sounds a bit dodgy to rely on. It should be relatively straight
> forward to fix this with a simple comparison, shouldn't it?
> CC:ing Christoffer, Marc and Eric here to see if we should add this (in
> KVM as well).
>

The only concern about holding two locks at the same time is the risk
of another thread attempting to hold a number of locks at the same
time in a different order, leading to a deadlock (either directly or
via a circular dependency).

As you point out, the only place where we take two irq locks at the
same time is in vgic_irq_cmp().  Now, the concern can be reduced to
calling this function more than once in parallel, operating on the
same set of struct irqs.

An IRQ can only be on a single AP list at any time, and we call
vgic_irq_cmp() from exactly one place in the KVM code, which holds the
ap_list_lock, and our locking order defines that the ap_list_lock must
be taken before irq locks.  This means that vgic_irq_cmp() can only
execute in parallel on different AP lists and therefore not operate on
the same set of struct irqs.

There is no need to change anything in the implementation.

Thanks,
-Christoffer

_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/mailman/listinfo/xen-devel