Re: [Qemu-devel] [PATCH, v2] Rewrite mmap_find_vma() to work fine on 64-bit hosts with 32-bit targets

[Jamie Lokier <jamie@shareable.org>]

Kirill A. Shutemov wrote:
> > > Just briefly to mention that binary search using shorter
> > > probe-mappings can eliminate the page-by-page iteration in this case,
> > > but alas I don't have time in this email to explain how :-)
> > 
> > I was wondering the same, but I think binary search won't work:
> > whenever you make a step greater than page size you risk having missed
> > a free page closer to you.  In the end you need to check all of them.
> > 
> > The in-kernel allocator probably is in a better position to have a
> > smart algorithm.
> 
> To have smarter algorithm we must know about every mapping in self address
> space. But it's impossible without /proc/self/maps. Unfortunately it isn't
> always available.

You're both wrong :-)

Assume you're looking for a hole of size N without missing any free
pages.  You can search forwards in N/2-size steps with N/2-size probe
mappings (actually ceiling(N/2)), then when you find an N/2-size hole,
search _backwards_ from that address to confirm the larger N-size
hole.  You are guaranteed that if there exists an N-size hole at any
address in range, then the probe mappings will find a hole within the
larger hole, even though they skip N/2 pages at a time.  For the
backward search you can do binary search, i.e. use the remaining
search range / 2 for _its_ probe, repeat, rinse, recurse, so that
large N is fast.

-- Jamie