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

[Paul Brook <paul@codesourcery.com>]

On Friday 14 November 2008, Kirill A. Shutemov wrote:
> On Tue, Nov 11, 2008 at 12:53:17AM +0000, Jamie Lokier wrote:
> > 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.
>
> Sorry, but I can't understand your algorithm. Can you provide pseudo-code?

It's a basic binary search. The problem with it being that as with any other 
binary search it relies on being able to do "probes".  In this case that 
involves mapping and unmapping the region, which I'd expect to be fairly high 
overhead.

Paul