From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1759500Ab2HITj3 (ORCPT ); Thu, 9 Aug 2012 15:39:29 -0400 Received: from mail.betterlinux.com ([199.58.199.50]:53529 "EHLO mail.betterlinux.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1759376Ab2HITj1 (ORCPT ); Thu, 9 Aug 2012 15:39:27 -0400 X-DKIM: OpenDKIM Filter v2.4.1 mail.betterlinux.com 4DD808210C Date: Thu, 9 Aug 2012 21:39:21 +0200 From: Andrea Righi To: John Stultz Cc: Michel Lespinasse , LKML , Andrew Morton , Android Kernel Team , Robert Love , Mel Gorman , Hugh Dickins , Dave Hansen , Rik van Riel , Dmitry Adamushko , Dave Chinner , Neil Brown , "Aneesh Kumar K.V" , Mike Hommey , Jan Kara , KOSAKI Motohiro , Minchan Kim , "linux-mm@kvack.org" Subject: Re: [PATCH 1/5] [RFC] Add volatile range management code Message-ID: <20120809193921.GA1999@thinkpad> References: <1343447832-7182-1-git-send-email-john.stultz@linaro.org> <1343447832-7182-2-git-send-email-john.stultz@linaro.org> <20120809133544.GA2086@thinkpad> <5024107D.8070109@linaro.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <5024107D.8070109@linaro.org> User-Agent: Mutt/1.5.21 (2010-09-15) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Thu, Aug 09, 2012 at 12:33:17PM -0700, John Stultz wrote: > On 08/09/2012 06:35 AM, Andrea Righi wrote: > >On Thu, Aug 09, 2012 at 02:46:37AM -0700, Michel Lespinasse wrote: > >>On Fri, Jul 27, 2012 at 8:57 PM, John Stultz wrote: > >>>v5: > >>>* Drop intervaltree for prio_tree usage per Michel & > >>> Dmitry's suggestions. > >>Actually, I believe the ranges you need to track are non-overlapping, correct ? > >> > >>If that is the case, a simple rbtree, sorted by start-of-range > >>address, would work best. > >>(I am trying to remove prio_tree users... :) > >> > >John, > > > >JFYI, if you want to try a possible rbtree-based implementation, as > >suggested by Michel you could try this one: > >https://github.com/arighi/kinterval > > > >This implementation supports insertion, deletion and transparent merging > >of adjacent ranges, as well as splitting ranges when chunks removed or > >different chunk types are added in the middle of an existing range; so > >if I'm not wrong probably you should be able to use this code as is, > >without any modification. > I do appreciate the suggestion, and considered this earlier when you > posted this before. > > Unfotunately the transparent merging/splitting/etc is actually not > useful for me, since I manage other data per-range. The earlier > generic rangetree/intervaltree implementations I tried limiting the > interface to basically add(), remove(), search(), and search_next(), > since when we coalesce intervals, we need to free the data in the > structure referencing the interval being deleted (and similarly > create new structures to reference new intervals created when we > remove an interval). So the coalescing/splitting logic can't be > pushed into the interval management code cleanly. > > So while I might be able to make use of your kinterval in a fairly > simple manner (only using add/del/lookup), I'm not sure it wins > anything over just using an rbtree. Especially since I'd have to do > my own coalesce/splitting logic anyway, it would actually be more > expensive as on add() it would still scan to check for overlapping > ranges to merge. > > I ended up dropping my generic intervaltree implementation because > folks objected that it was so trivial (basically just wrapping an > rbtree) and didn't handle some of the more complex intervaltree use > cases (ie: allowing for overlapping intervals). The priotree seemed > to match fairly closely the interface I was using, but apparently > its on its way out as well, so unless anyone further objects, I > think I'll just fall back to a simple rbtree implementation. OK, everything makes sense now, thanks for the clarifications, and sorry for suggesting yet another range/interval tree implementation. :) I'll look at your patch set more in details and try to test/review it closely. -Andrea From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx151.postini.com [74.125.245.151]) by kanga.kvack.org (Postfix) with SMTP id 2EEE46B0044 for ; Thu, 9 Aug 2012 15:39:28 -0400 (EDT) Date: Thu, 9 Aug 2012 21:39:21 +0200 From: Andrea Righi Subject: Re: [PATCH 1/5] [RFC] Add volatile range management code Message-ID: <20120809193921.GA1999@thinkpad> References: <1343447832-7182-1-git-send-email-john.stultz@linaro.org> <1343447832-7182-2-git-send-email-john.stultz@linaro.org> <20120809133544.GA2086@thinkpad> <5024107D.8070109@linaro.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <5024107D.8070109@linaro.org> Sender: owner-linux-mm@kvack.org List-ID: To: John Stultz Cc: Michel Lespinasse , LKML , Andrew Morton , Android Kernel Team , Robert Love , Mel Gorman , Hugh Dickins , Dave Hansen , Rik van Riel , Dmitry Adamushko , Dave Chinner , Neil Brown , "Aneesh Kumar K.V" , Mike Hommey , Jan Kara , KOSAKI Motohiro , Minchan Kim , "linux-mm@kvack.org" On Thu, Aug 09, 2012 at 12:33:17PM -0700, John Stultz wrote: > On 08/09/2012 06:35 AM, Andrea Righi wrote: > >On Thu, Aug 09, 2012 at 02:46:37AM -0700, Michel Lespinasse wrote: > >>On Fri, Jul 27, 2012 at 8:57 PM, John Stultz wrote: > >>>v5: > >>>* Drop intervaltree for prio_tree usage per Michel & > >>> Dmitry's suggestions. > >>Actually, I believe the ranges you need to track are non-overlapping, correct ? > >> > >>If that is the case, a simple rbtree, sorted by start-of-range > >>address, would work best. > >>(I am trying to remove prio_tree users... :) > >> > >John, > > > >JFYI, if you want to try a possible rbtree-based implementation, as > >suggested by Michel you could try this one: > >https://github.com/arighi/kinterval > > > >This implementation supports insertion, deletion and transparent merging > >of adjacent ranges, as well as splitting ranges when chunks removed or > >different chunk types are added in the middle of an existing range; so > >if I'm not wrong probably you should be able to use this code as is, > >without any modification. > I do appreciate the suggestion, and considered this earlier when you > posted this before. > > Unfotunately the transparent merging/splitting/etc is actually not > useful for me, since I manage other data per-range. The earlier > generic rangetree/intervaltree implementations I tried limiting the > interface to basically add(), remove(), search(), and search_next(), > since when we coalesce intervals, we need to free the data in the > structure referencing the interval being deleted (and similarly > create new structures to reference new intervals created when we > remove an interval). So the coalescing/splitting logic can't be > pushed into the interval management code cleanly. > > So while I might be able to make use of your kinterval in a fairly > simple manner (only using add/del/lookup), I'm not sure it wins > anything over just using an rbtree. Especially since I'd have to do > my own coalesce/splitting logic anyway, it would actually be more > expensive as on add() it would still scan to check for overlapping > ranges to merge. > > I ended up dropping my generic intervaltree implementation because > folks objected that it was so trivial (basically just wrapping an > rbtree) and didn't handle some of the more complex intervaltree use > cases (ie: allowing for overlapping intervals). The priotree seemed > to match fairly closely the interface I was using, but apparently > its on its way out as well, so unless anyone further objects, I > think I'll just fall back to a simple rbtree implementation. OK, everything makes sense now, thanks for the clarifications, and sorry for suggesting yet another range/interval tree implementation. :) I'll look at your patch set more in details and try to test/review it closely. -Andrea -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org