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

[Julien Grall <julien.grall@xxxxxxx>]

Hi Shanker,

On 26/06/16 18:48, 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>
> ---
>   xen/arch/arm/io.c | 50 +++++++++++++++++++++++++++++++++++++++-----------
>   1 file changed, 39 insertions(+), 11 deletions(-)
>
> diff --git a/xen/arch/arm/io.c b/xen/arch/arm/io.c
> index a5b2c2d..abf49fb 100644
> --- a/xen/arch/arm/io.c
> +++ b/xen/arch/arm/io.c
> @@ -20,6 +20,7 @@
>   #include <xen/lib.h>
>   #include <xen/spinlock.h>
>   #include <xen/sched.h>
> +#include <xen/sort.h>
>   #include <asm/current.h>
>   #include <asm/mmio.h>
>
> @@ -70,23 +71,38 @@ static int handle_write(const struct mmio_handler *handler, 
> struct vcpu *v,
>                                  handler->priv);
>   }
>
> -int handle_mmio(mmio_info_t *info)
> +const struct mmio_handler *find_mmio_handler(struct vcpu *v, paddr_t addr)
>   {
> -    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 = vmmio->handlers;
> +    unsigned int eidx = vmmio->num_entries;
> +    unsigned int midx = eidx / 2;
> +    unsigned int sidx = 0;
>
> -    for ( i = 0; i < vmmio->num_entries; i++ )
> +    /* Do binary search for matching mmio handler */
> +    while ( sidx != midx )
>       {
> -        handler = &vmmio->handlers[i];
> -
> -        if ( (info->gpa >= handler->addr) &&
> -             (info->gpa < (handler->addr + handler->size)) )
> -            break;
> +        if ( addr < handler[midx].addr )
> +            eidx = midx;
> +        else
> +            sidx = midx;
> +        midx = sidx + (eidx - sidx) / 2;
This binary search can be simplified. For instance, why do you want to 
compute midx at the end rather than at the beginning. This would avoid 
to have "unsigned int midx = eidx / 2" at the beginning.
>       }
>
> -    if ( i == vmmio->num_entries )
> +    if ( (addr >= handler[sidx].addr) &&
> +         (addr < (handler[sidx].addr + handler[sidx].size)) )
> +        return handler + sidx;
Please use a temporary variable for handler[sidx]. So it will be easier 
to read the code.
> +
> +    return NULL;
> +}
> +
> +int handle_mmio(mmio_info_t *info)
> +{
> +    const struct mmio_handler *handler;
> +    struct vcpu *v = current;
> +
> +    handler = find_mmio_handler(v, info->gpa);
I would have expected some locking here. Could you explain why it is 
safe to looking find the handler with your solution?
For what is worth, there was no locking before because 
register_mmio_handler was always adding the handler at the end of the 
array. This is not true anymore because you are sorting the array.
> +    if ( !handler )
>           return 0;
>
>       if ( info->dabt.write )
> @@ -95,6 +111,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 +146,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,

--
Julien Grall

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