[PATCH] arm64: Correct virt_addr_valid

[Russell King - ARM Linux]

On Wed, Dec 11, 2013 at 10:44:29AM +0000, Will Deacon wrote:
> Hmm, this is pretty expensive on both arm and arm64, since we end up doing a
> binary search through all of the memblocks.

People say "binary search == expensive" almost as a knee jerk
reaction, because classical thinking is that binary searches are
expensive for systems with caches.  Have you considered how many
memblocks you end up with on a normal system?

How expensive is a binary search across one element?  Two elements?
Four elements?  In the very very rare case (there's only one platform)
eight elements?

For one element, it's the same as a linear search - we only have to
look at one element and confirm whether the pointer is within range.
Same for two - we check one and check the other.  As memblock is array
based, both blocks share the same cache line.

For four, it means we look at most three elements, at least two of
which share a cache line.  In terms of cache line loading, it's no
more expensive than a linear search.  In terms of CPU cycles, it's
a win because we don't need to expend cycles looking at the fourth
element.

For eight (which is starting to get into the "rare" territory, and
three cache lines, four elements vs a linear search which can be up
to four cache lines and obviously eight elements.

Now, bear in mind that the normal case is one, there's a number with
two, four starts to become rare, and eight is almost non-existent...