Re: [Xen-devel] [PATCH V3 09/10] xen/arm: io: Use binary search for mmio handler lookup

[Shanker Donthineni <shankerd@xxxxxxxxxxxxxx>]

Hi Julien,

On 06/28/2016 05:49 AM, Julien Grall wrote:
> Hi Shanker,
>
> On 27/06/16 21:33, Shanker Donthineni wrote:
> > As the number of I/O handlers increase, the overhead associated with
> > linear lookup also increases. The system might have maximum of 144
> > (assuming CONFIG_NR_CPUS=128) mmio handlers. In worst case scenario,
> > it would require 144 iterations for finding a matching handler. Now
> > it is time for us to change from linear (complexity O(n)) to a binary
> > search (complexity O(log n) for reducing mmio handler lookup overhead.
> >
> > Signed-off-by: Shanker Donthineni <shankerd@xxxxxxxxxxxxxx>
> > ---
> > Changes since v2:
> >    Converted mmio lookup code to a critical section.
> >    Copied the function bsreach() from Linux kernel.
> >
> >   xen/arch/arm/io.c | 97
> +++++++++++++++++++++++++++++++++++++++++++++++--------
> >   1 file changed, 84 insertions(+), 13 deletions(-)
> >
> > diff --git a/xen/arch/arm/io.c b/xen/arch/arm/io.c
> > index a5b2c2d..c31fdf3 100644
> > --- a/xen/arch/arm/io.c
> > +++ b/xen/arch/arm/io.c
> > @@ -20,9 +20,50 @@
> >   #include <xen/lib.h>
> >   #include <xen/spinlock.h>
> >   #include <xen/sched.h>
> > +#include <xen/sort.h>
> >   #include <asm/current.h>
> >   #include <asm/mmio.h>
> >
> > +/*
> > + * bsearch - binary search an array of elements
> > + * @key: pointer to item being searched for
> > + * @base: pointer to first element to search
> > + * @num: number of elements
> > + * @size: size of each element
> > + * @cmp: pointer to comparison function
> > + *
> > + * This function does a binary search on the given array.  The
> > + * contents of the array should already be in ascending sorted order
> > + * under the provided comparison function.
> > + *
> > + * Note that the key need not have the same type as the elements in
> > + * the array, e.g. key could be a string and the comparison function
> > + * could compare the string with the struct's name field. However, if
> > + * the key and elements in the array are of the same type, you can use
> > + * the same comparison function for both sort() and bsearch().
> > + */
> > +static void *bsearch(const void *key, const void *base, size_t num,
> size_t size,
> > +                     int (*cmp)(const void *key, const void *elt))
> This function is not specific to I/O handlers. So this should be moved 
> to common code. Also please mention in the commit message where the 
> code came from.
Should I move to xen/arch/arm folder?

> > +{
> > +    size_t start = 0, end = num;
> > +    int result;
> > +
> > +    while ( start < end )
> > +    {
> > +        size_t mid = start + (end - start) / 2;
> > +
> > +        result = cmp(key, base + mid * size);
> > +        if ( result < 0 )
> > +            end = mid;
> > +        else if ( result > 0 )
> > +            start = mid + 1;
> > +        else
> > +            return (void *)base + mid * size;
> > +    }
> > +
> > +    return NULL;
> > +}
> > +
> >   static int handle_read(const struct mmio_handler *handler, struct vcpu
> *v,
> >                          mmio_info_t *info)
> >   {
> > @@ -70,23 +111,41 @@ static int handle_write(const struct mmio_handler
> *handler, struct vcpu *v,
> > handler->priv);
> >   }
> >
> > -int handle_mmio(mmio_info_t *info)
> > +static int match_mmio_handler(const void *key, const void *elem)
> >   {
> > -    struct vcpu *v = current;
> > -    int i;
> > -    const struct mmio_handler *handler = NULL;
> > -    const struct vmmio *vmmio = &v->domain->arch.vmmio;
> > +    const struct mmio_handler *handler = elem;
> > +    paddr_t addr = (paddr_t)key;
> >
> > -    for ( i = 0; i < vmmio->num_entries; i++ )
> > -    {
> > -        handler = &vmmio->handlers[i];
> > +    if ( addr < handler->addr )
> > +        return -1;
> >
> > -        if ( (info->gpa >= handler->addr) &&
> > -             (info->gpa < (handler->addr + handler->size)) )
> > -            break;
> > -    }
> > +    if ( addr > (handler->addr + handler->size) )
> > +        return 1;
> > +
> > +    return 0;
> > +}
> >
> > -    if ( i == vmmio->num_entries )
> > +static const struct mmio_handler *
> > +find_mmio_handler(struct vcpu *v, paddr_t addr)
> > +{
> > +    struct vmmio *vmmio = &v->domain->arch.vmmio;
> > +    const struct mmio_handler *handler;
> > +
> > +    spin_lock(&vmmio->lock);
> > +    handler = bsearch((const void *)addr, vmmio->handlers,
> vmmio->num_entries,
>
> paddr_t is always 64-bit regardless the architecture (ARM64 vs ARM32). 
> So the cast will lead to a compilation error on ARM32.
I'll fix.

> Please try to at least compile test your patch with ARM64, ARM32 and 
> x86 (when you touch common code).
Thanks, I'll follow next time.

> Anyway, I would try to merge the two compare functions 
> (match_mmio_handler, cmp_mmio_handler) which have very similar behavior.
Yes, they are not exactly same. One compares only start address and 
other one compares the range.
> > +                      sizeof(*handler), match_mmio_handler);
> > +    spin_unlock(&vmmio->lock);
> > +
> > +    return handler;
> > +}
> > +
> > +int handle_mmio(mmio_info_t *info)
> > +{
> > +    const struct mmio_handler *handler;
> > +    struct vcpu *v = current;
> > +
> > +    handler = find_mmio_handler(v, info->gpa);
> > +    if ( !handler )
> >           return 0;
> >
> >       if ( info->dabt.write )
> > @@ -95,6 +154,14 @@ int handle_mmio(mmio_info_t *info)
> >           return handle_read(handler, v, info);
> >   }
> >
> > +static int cmp_mmio_handler(const void *key, const void *elem)
> > +{
> > +    const struct mmio_handler *handler0 = key;
> > +    const struct mmio_handler *handler1 = elem;
> > +
> > +    return (handler0->addr < handler1->addr) ? -1 : 0;
> > +}
> > +
> >   void register_mmio_handler(struct domain *d,
> >                              const struct mmio_handler_ops *ops,
> >                              paddr_t addr, paddr_t size, void *priv)
> > @@ -122,6 +189,10 @@ void register_mmio_handler(struct domain *d,
> >
> >       vmmio->num_entries++;
> >
> > +    /* Sort mmio handlers in ascending order based on base address */
> > +    sort(vmmio->handlers, vmmio->num_entries, sizeof(struct
> mmio_handler),
> > +         cmp_mmio_handler, NULL);
> > +
> >       spin_unlock(&vmmio->lock);
> >   }
> Regards,
--
Shanker Donthineni
Qualcomm Technologies, Inc. on behalf of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux 
Foundation Collaborative Project


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