[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH, v2] Rewrite mmap_find_vma() to work fine on 64-
From: |
Kirill A. Shutemov |
Subject: |
Re: [Qemu-devel] [PATCH, v2] Rewrite mmap_find_vma() to work fine on 64-bit hosts with 32-bit targets |
Date: |
Fri, 14 Nov 2008 14:23:56 +0200 |
User-agent: |
Mutt/1.5.18 (2008-05-29) |
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?
--
Regards, Kirill A. Shutemov
+ Belarus, Minsk
+ ALT Linux Team, http://www.altlinux.org/
signature.asc
Description: Digital signature
- Re: [Qemu-devel] [PATCH, v2] Rewrite mmap_find_vma() to work fine on 64-bit hosts with 32-bit targets, Jamie Lokier, 2008/11/01
- Re: [Qemu-devel] [PATCH, v2] Rewrite mmap_find_vma() to work fine on 64-bit hosts with 32-bit targets, Kirill A. Shutemov, 2008/11/01
- Re: [Qemu-devel] [PATCH, v2] Rewrite mmap_find_vma() to work fine on 64-bit hosts with 32-bit targets, andrzej zaborowski, 2008/11/09
- Re: [Qemu-devel] [PATCH, v2] Rewrite mmap_find_vma() to work fine on 64-bit hosts with 32-bit targets, Kirill A. Shutemov, 2008/11/10
- Re: [Qemu-devel] [PATCH, v2] Rewrite mmap_find_vma() to work fine on 64-bit hosts with 32-bit targets, Jamie Lokier, 2008/11/10
- Re: [Qemu-devel] [PATCH, v2] Rewrite mmap_find_vma() to work fine on 64-bit hosts with 32-bit targets, andrzej zaborowski, 2008/11/10
- Re: [Qemu-devel] [PATCH, v2] Rewrite mmap_find_vma() to work fine on 64-bit hosts with 32-bit targets, Kirill A. Shutemov, 2008/11/10
- Re: [Qemu-devel] [PATCH, v2] Rewrite mmap_find_vma() to work fine on 64-bit hosts with 32-bit targets, Jamie Lokier, 2008/11/10
- Re: [Qemu-devel] [PATCH, v2] Rewrite mmap_find_vma() to work fine on 64-bit hosts with 32-bit targets,
Kirill A. Shutemov <=
- Re: [Qemu-devel] [PATCH, v2] Rewrite mmap_find_vma() to work fine on 64-bit hosts with 32-bit targets, Paul Brook, 2008/11/14
- Re: [Qemu-devel] [PATCH, v2] Rewrite mmap_find_vma() to work fine on 64-bit hosts with 32-bit targets, Jamie Lokier, 2008/11/14
- Re: [Qemu-devel] [PATCH, v2] Rewrite mmap_find_vma() to work fine on 64-bit hosts with 32-bit targets, Kirill A. Shutemov, 2008/11/14