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

[Julien Grall <julien.grall@arm.com>]

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@codeaurora.org>
>>> ---
>>> 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@lists.xen.org
http://lists.xen.org/xen-devel