From mboxrd@z Thu Jan 1 00:00:00 1970 Received: with ECARTIS (v1.0.0; list linux-mips); Tue, 06 Nov 2012 23:11:48 +0100 (CET) Received: from mail.linuxfoundation.org ([140.211.169.12]:51322 "EHLO mail.linuxfoundation.org" rhost-flags-OK-OK-OK-OK) by eddie.linux-mips.org with ESMTP id S6826032Ab2KFWLrAge5w (ORCPT ); Tue, 6 Nov 2012 23:11:47 +0100 Received: from akpm.mtv.corp.google.com (216-239-45-4.google.com [216.239.45.4]) by mail.linuxfoundation.org (Postfix) with ESMTPSA id BA95326; Tue, 6 Nov 2012 22:11:38 +0000 (UTC) Date: Tue, 6 Nov 2012 14:11:37 -0800 From: Andrew Morton To: Michel Lespinasse Cc: Rik van Riel , Hugh Dickins , linux-kernel@vger.kernel.org, Russell King , Ralf Baechle , Paul Mundt , "David S. Miller" , Chris Metcalf , x86@kernel.org, William Irwin , linux-mm@kvack.org, linux-arm-kernel@lists.infradead.org, linux-mips@linux-mips.org, linux-sh@vger.kernel.org, sparclinux@vger.kernel.org Subject: Re: [PATCH 00/16] mm: use augmented rbtrees for finding unmapped areas Message-Id: <20121106141137.68bbd4ea.akpm@linux-foundation.org> In-Reply-To: <1352155633-8648-1-git-send-email-walken@google.com> References: <1352155633-8648-1-git-send-email-walken@google.com> X-Mailer: Sylpheed 3.0.2 (GTK+ 2.20.1; x86_64-pc-linux-gnu) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-archive-position: 34907 X-ecartis-version: Ecartis v1.0.0 Sender: linux-mips-bounce@linux-mips.org Errors-to: linux-mips-bounce@linux-mips.org X-original-sender: akpm@linux-foundation.org Precedence: bulk List-help: List-unsubscribe: List-software: Ecartis version 1.0.0 List-Id: linux-mips X-List-ID: linux-mips List-subscribe: List-owner: List-post: List-archive: X-list: linux-mips Return-Path: On Mon, 5 Nov 2012 14:46:57 -0800 Michel Lespinasse wrote: > Earlier this year, Rik proposed using augmented rbtrees to optimize > our search for a suitable unmapped area during mmap(). This prompted > my work on improving the augmented rbtree code. Rik doesn't seem to > have time to follow up on his idea at this time, so I'm sending this > series to revive the idea. Well, the key word here is "optimize". Some quantitative testing results would be nice, please! People do occasionally see nasty meltdowns in the get_unmapped_area() vicinity. There was one case 2-3 years ago which was just ghastly, but I can't find the email (it's on linux-mm somewhere). This one might be another case: http://lkml.indiana.edu/hypermail/linux/kernel/1101.1/00896.html If you can demonstrate that this patchset fixes some of all of the bad search complexity scenarios then that's quite a win? > These changes are against v3.7-rc4. I have not converted all applicable > architectuers yet, but we don't necessarily need to get them all onboard > at once - the series is fully bisectable and additional architectures > can be added later on. I am confident enough in my tests for patches 1-8; > however the second half of the series basically didn't get tested as > I don't have access to all the relevant architectures. Yes, I'll try to get these into -next so that the thousand monkeys at least give us some compilation coverage testing. Hopefully the relevant arch maintainers will find time to perform a runtime test. > Patch 1 is the validate_mm() fix from Bob Liu (+ fixed-the-fix from me :) I grabbed this one separately, as a post-3.6 fix.