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

[Shanker Donthineni <shankerd@xxxxxxxxxxxxxx>]

Hi Julien,

On 07/14/2016 11:46 AM, Julien Grall wrote:
> Hi Shanker,
>
> On 14/07/16 17:18, 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 v3:
> >    Moved the function bsearch() to common file xen/common/bsearch.c.
> >
> > Changes since v2:
> >    Converted mmio lookup code to a critical section.
> >    Copied the function bsreach() from Linux kernel.
> >
> >   xen/arch/arm/io.c | 42 +++++++++++++++++++++++++-----------------
> >   1 file changed, 25 insertions(+), 17 deletions(-)
> >
> > diff --git a/xen/arch/arm/io.c b/xen/arch/arm/io.c
> > index 40330f0..0471ba8 100644
> > --- a/xen/arch/arm/io.c
> > +++ b/xen/arch/arm/io.c
> > @@ -20,6 +20,8 @@
> >   #include <xen/lib.h>
> >   #include <xen/spinlock.h>
> >   #include <xen/sched.h>
> > +#include <xen/sort.h>
> > +#include <xen/bsearch.h>
> >   #include <asm/current.h>
> >   #include <asm/mmio.h>
> >
> > @@ -70,27 +72,29 @@ static int handle_write(const struct mmio_handler 
> > *handler, struct vcpu *v,
> >                                  handler->priv);
> >   }
> >
> > -static const struct mmio_handler *find_mmio_handler(struct domain *d,
> > -                                                    paddr_t gpa)
> > +static int cmp_mmio_handler(const void *key, const void *elem)
> Would it be worth to mention in a comment that we don't support 
> overlapping?
Sure, I'll do.

> >   {
> > -    const struct mmio_handler *handler;
> > -    unsigned int i;
> > -    struct vmmio *vmmio = &d->arch.vmmio;
> > +    const struct mmio_handler *handler0 = key;
> > +    const struct mmio_handler *handler1 = elem;
> >
> > -    read_lock(&vmmio->lock);
> > +    if ( handler0->addr < handler1->addr )
> > +        return -1;
> >
> > -    for ( i = 0; i < vmmio->num_entries; i++ )
> > -    {
> > -        handler = &vmmio->handlers[i];
> > +    if ( handler0->addr > (handler1->addr + handler1->size) )
> > +        return 1;
> >
> > -        if ( (gpa >= handler->addr) &&
> > -             (gpa < (handler->addr + handler->size)) )
> > -            break;
> > -    }
> > +    return 0;
> > +}
> >
> > -    if ( i == vmmio->num_entries )
> > -        handler = NULL;
> > +static const struct mmio_handler *find_mmio_handler(struct vcpu *v, 
> > paddr_t gpa)
> Why have you changed the prototype of find_mmio_handler?
As such there is no reason for this change, I'll revert this change in 
next patchset.
> > +{
> > +    struct vmmio *vmmio = &v->domain->arch.vmmio;
> > +    struct mmio_handler key = {.addr = gpa};
> I know it is not currently the case, but should not we take into 
> account the size of the access?
I agree with you, we definitely need to consider size of the access for 
traps/emulation drivers similar to what Linux KVM code does currently. 
Do you know which emulation drivers are using non aligned accesses?

> > +    const struct mmio_handler *handler;
> >
> > +    read_lock(&vmmio->lock);
> > +    handler = bsearch(&key, vmmio->handlers, vmmio->num_entries,
> > +                      sizeof(*handler), cmp_mmio_handler);
> >       read_unlock(&vmmio->lock);
> >
> >       return handler;
> > @@ -99,9 +103,9 @@ static const struct mmio_handler 
> > *find_mmio_handler(struct domain *d,
> >   int handle_mmio(mmio_info_t *info)
> >   {
> >       struct vcpu *v = current;
> > -    const struct mmio_handler *handler = NULL;
> > +    const struct mmio_handler *handler;
> Why this change?
No need to initialize this local variable because the following line 
always initializes it. I'll revert this change anyway to avoid confusion.
> > -    handler = find_mmio_handler(v->domain, info->gpa);
> > +    handler = find_mmio_handler(v, info->gpa);
> ditto.
>
> >       if ( !handler )
> >           return 0;
> >
> > @@ -131,6 +135,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);
> The indentation looks wrong here.
I don't quite understand what you mean. It has 8 spaces, do I need more 
than 8 spaces or something else?
> > +
> >       write_unlock(&vmmio->lock);
> >   }
--
Shanker Donthineni
Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm 
Technologies, Inc.
Qualcomm Technologies, Inc. is a member of the Code Aurora Forum, a Linux 
Foundation Collaborative Project.


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