xen/arm: io: Use binary search for mmio handler lookup
authorShanker Donthineni <shankerd@codeaurora.org>
Wed, 20 Jul 2016 14:00:55 +0000 (09:00 -0500)
committerStefano Stabellini <sstabellini@kernel.org>
Tue, 26 Jul 2016 22:12:27 +0000 (15:12 -0700)
commit8047e090f42a39bda911f6b2e81fdab12603b64a
treee60266fb0fc812af05f82d71bf6cfa71bc0a00ba
parente3eb84e33c365ce0af1a75ef25ec36cf646c958b
xen/arm: io: Use binary search for mmio handler lookup

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>
Acked-by: Julien Grall <julien.grall@arm.com>
Acked-by: Stefano Stabellini <sstabellini@kernel.org>
xen/arch/arm/io.c