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

[Julien Grall <julien.grall@xxxxxxx>]

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
>   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?
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.
> +
> +    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?
> + *
> + * 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,

--
Julien Grall

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