|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] Re: [Xen-devel] [RFC PATCH 23/49] ARM: new VGIC: Add IRQ sorting
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).
> Also, this will be done with irq disabled right? In that case, may I ask
> for an ASSERT(!local_irq_is_enabled())? Or maybe in vgic_sort_ap_list.
OK.
>> +
>> + if ( irqa->active || irqb->active )
>> + {
>> + ret = (int)irqb->active - (int)irqa->active;
>> + goto out;
>> + }
>> +
>> + penda = irqa->enabled && irq_is_pending(irqa);
>> + pendb = irqb->enabled && irq_is_pending(irqb);
>> +
>> + if ( !penda || !pendb )
>> + {
>> + ret = (int)pendb - (int)penda;
>> + goto out;
>> + }
>> +
>> + /* Both pending and enabled, sort by priority */
>> + ret = irqa->priority - irqb->priority;
>> +out:
>> + spin_unlock(&irqb->irq_lock);
>> + spin_unlock(&irqa->irq_lock);
>> + return ret;
>> +}
>> +
>> +/* Must be called with the ap_list_lock held */
>> +static void vgic_sort_ap_list(struct vcpu *vcpu)
>> +{
>> + struct vgic_cpu *vgic_cpu = &vcpu->arch.vgic_cpu;
>> +
>> + ASSERT(spin_is_locked(&vgic_cpu->ap_list_lock));
>> +
>> + list_sort(NULL, &vgic_cpu->ap_list_head, vgic_irq_cmp);
>> +}
>> +
>> /*
>> * Only valid injection if changing level for level-triggered IRQs
>> or for a
>> * rising edge.
>> diff --git a/xen/common/list_sort.c b/xen/common/list_sort.c
>> new file mode 100644
>> index 0000000000..9c5cc58e43
>> --- /dev/null
>> +++ b/xen/common/list_sort.c
>> @@ -0,0 +1,170 @@
>> +/*
>> + * list_sort.c: merge sort implementation for linked lists
>> + * Copied from the Linux kernel (lib/list_sort.c)
>> + * (without specific copyright notice there)
>
> I can see you moved from Linux to Xen coding style. Is there any other
> changes made?
Just the list of include files, but I didn't touch any actual code.
Will mention this in the commit message for this separate patch.
Cheers,
Andre.
>
>> + *
>> + * This program is free software; you can redistribute it and/or
>> modify it
>> + * under the terms and conditions of the GNU General Public License,
>> + * version 2, as published by the Free Software Foundation.
>> + *
>> + * This program is distributed in the hope it will be useful, but
>> WITHOUT
>> + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
>> + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
>> License for
>> + * more details.
>> + *
>> + * You should have received a copy of the GNU General Public License
>> along with
>> + * this program; If not, see <http://www.gnu.org/licenses/>.
>> + */
>> +#include <xen/lib.h>
>> +#include <xen/list.h>
>> +
>> +#define MAX_LIST_LENGTH_BITS 20
>> +
>> +/*
>> + * Returns a list organized in an intermediate format suited
>> + * to chaining of merge() calls: null-terminated, no reserved or
>> + * sentinel head node, "prev" links not maintained.
>> + */
>> +static struct list_head *merge(void *priv,
>> + int (*cmp)(void *priv, struct
>> list_head *a,
>> + struct list_head *b),
>> + struct list_head *a, struct list_head *b)
>> +{
>> + struct list_head head, *tail = &head;
>> +
>> + while ( a && b )
>> + {
>> + /* if equal, take 'a' -- important for sort stability */
>> + if ( (*cmp)(priv, a, b) <= 0 )
>> + {
>> + tail->next = a;
>> + a = a->next;
>> + }
>> + else
>> + {
>> + tail->next = b;
>> + b = b->next;
>> + }
>> + tail = tail->next;
>> + }
>> + tail->next = a?:b;
>> + return head.next;
>> +}
>> +
>> +/*
>> + * Combine final list merge with restoration of standard doubly-linked
>> + * list structure. This approach duplicates code from merge(), but
>> + * runs faster than the tidier alternatives of either a separate final
>> + * prev-link restoration pass, or maintaining the prev links
>> + * throughout.
>> + */
>> +static void merge_and_restore_back_links(void *priv,
>> + int (*cmp)(void *priv,
>> + struct list_head *a,
>> + struct list_head
>> *b),
>> + struct list_head *head,
>> + struct list_head *a,
>> + struct list_head *b)
>> +{
>> + struct list_head *tail = head;
>> + u8 count = 0;
>> +
>> + while ( a && b )
>> + {
>> + /* if equal, take 'a' -- important for sort stability */
>> + if ( (*cmp)(priv, a, b) <= 0 )
>> + {
>> + tail->next = a;
>> + a->prev = tail;
>> + a = a->next;
>> + }
>> + else
>> + {
>> + tail->next = b;
>> + b->prev = tail;
>> + b = b->next;
>> + }
>> + tail = tail->next;
>> + }
>> + tail->next = a ? : b;
>> +
>> + do
>> + {
>> + /*
>> + * In worst cases this loop may run many iterations.
>> + * Continue callbacks to the client even though no
>> + * element comparison is needed, so the client's cmp()
>> + * routine can invoke cond_resched() periodically.
>> + */
>> + if ( unlikely(!(++count)) )
>> + (*cmp)(priv, tail->next, tail->next);
>> +
>> + tail->next->prev = tail;
>> + tail = tail->next;
>> + } while ( tail->next );
>> +
>> + tail->next = head;
>> + head->prev = tail;
>> +}
>> +
>> +/**
>> + * list_sort - sort a list
>> + * @priv: private data, opaque to list_sort(), passed to @cmp
>> + * @head: the list to sort
>> + * @cmp: the elements comparison function
>> + *
>> + * This function implements "merge sort", which has O(nlog(n))
>> + * complexity.
>> + *
>> + * The comparison function @cmp must return a negative value if @a
>> + * should sort before @b, and a positive value if @a should sort after
>> + * @b. If @a and @b are equivalent, and their original relative
>> + * ordering is to be preserved, @cmp must return 0.
>> + */
>> +void list_sort(void *priv, struct list_head *head,
>> + int (*cmp)(void *priv, struct list_head *a, struct
>> list_head *b))
>> +{
>> + struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial
>> lists
>> + -- last slot is a sentinel */
>> + int lev; /* index into part[] */
>> + int max_lev = 0;
>> + struct list_head *list;
>> +
>> + if ( list_empty(head) )
>> + return;
>> +
>> + memset(part, 0, sizeof(part));
>> +
>> + head->prev->next = NULL;
>> + list = head->next;
>> +
>> + while ( list )
>> + {
>> + struct list_head *cur = list;
>> + list = list->next;
>> + cur->next = NULL;
>> +
>> + for ( lev = 0; part[lev]; lev++ )
>> + {
>> + cur = merge(priv, cmp, part[lev], cur);
>> + part[lev] = NULL;
>> + }
>> + if ( lev > max_lev )
>> + {
>> + if ( unlikely(lev >= ARRAY_SIZE(part)-1) )
>> + {
>> + dprintk(XENLOG_DEBUG, "list too long for efficiency\n");
>> + lev--;
>> + }
>> + max_lev = lev;
>> + }
>> + part[lev] = cur;
>> + }
>> +
>> + for ( lev = 0; lev < max_lev; lev++ )
>> + if ( part[lev] )
>> + list = merge(priv, cmp, part[lev], list);
>> +
>> + merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
>> +}
>> +EXPORT_SYMBOL(list_sort);
>> diff --git a/xen/include/xen/list_sort.h b/xen/include/xen/list_sort.h
>> new file mode 100644
>> index 0000000000..a60c589d4b
>> --- /dev/null
>> +++ b/xen/include/xen/list_sort.h
>> @@ -0,0 +1,11 @@
>> +#ifndef _LINUX_LIST_SORT_H
>> +#define _LINUX_LIST_SORT_H
>> +
>> +#include <xen/types.h>
>> +
>> +struct list_head;
>> +
>> +void list_sort(void *priv, struct list_head *head,
>> + int (*cmp)(void *priv, struct list_head *a,
>> + struct list_head *b));
>> +#endif
>>
>
> Cheers,
>
_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/mailman/listinfo/xen-devel
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |