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

[Julien Grall <julien.grall@xxxxxxx>]

On 28/06/16 14:19, Shanker Donthineni wrote:
> On 06/28/2016 05:49 AM, Julien Grall wrote:
> > 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?
To xen/common/

[...]

> > 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.
I don't think this will be an issue to compare the range for both and it 
will avoid to duplicate the code.
Regards,

--
Julien Grall

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