From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1KzhVe-0006Ae-Ri for qemu-devel@nongnu.org; Mon, 10 Nov 2008 19:53:34 -0500 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1KzhVb-00069b-7c for qemu-devel@nongnu.org; Mon, 10 Nov 2008 19:53:34 -0500 Received: from [199.232.76.173] (port=40104 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1KzhVb-00069Y-30 for qemu-devel@nongnu.org; Mon, 10 Nov 2008 19:53:31 -0500 Received: from mail2.shareable.org ([80.68.89.115]:41116) by monty-python.gnu.org with esmtps (TLS-1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1KzhVa-0002IO-KU for qemu-devel@nongnu.org; Mon, 10 Nov 2008 19:53:31 -0500 Date: Tue, 11 Nov 2008 00:53:17 +0000 From: Jamie Lokier Subject: Re: [Qemu-devel] [PATCH, v2] Rewrite mmap_find_vma() to work fine on 64-bit hosts with 32-bit targets Message-ID: <20081111005317.GA1215@shareable.org> References: <1223892640-15545-11-git-send-email-kirill@shutemov.name> <1225129768-11603-1-git-send-email-kirill@shutemov.name> <20081101165110.GA6991@shareable.org> <20081101165543.GA5076@localhost.localdomain> <20081110080234.GA18267@shareable.org> <20081110143810.GB17947@localhost.localdomain> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20081110143810.GB17947@localhost.localdomain> Reply-To: qemu-devel@nongnu.org List-Id: qemu-devel.nongnu.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: "Kirill A. Shutemov" Cc: qemu-devel@nongnu.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