linux-kernel - Re: [PATCH 1/5] [RFC] Add volatile range management code

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <5024107D.8070109@linaro.org>
Date:	Thu, 09 Aug 2012 12:33:17 -0700
From:	John Stultz <john.stultz@...aro.org>
To:	Andrea Righi <andrea@...terlinux.com>
CC:	Michel Lespinasse <walken@...gle.com>,
	LKML <linux-kernel@...r.kernel.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Android Kernel Team <kernel-team@...roid.com>,
	Robert Love <rlove@...gle.com>, Mel Gorman <mel@....ul.ie>,
	Hugh Dickins <hughd@...gle.com>,
	Dave Hansen <dave@...ux.vnet.ibm.com>,
	Rik van Riel <riel@...hat.com>,
	Dmitry Adamushko <dmitry.adamushko@...il.com>,
	Dave Chinner <david@...morbit.com>, Neil Brown <neilb@...e.de>,
	"Aneesh Kumar K.V" <aneesh.kumar@...ux.vnet.ibm.com>,
	Mike Hommey <mh@...ndium.org>, Jan Kara <jack@...e.cz>,
	KOSAKI Motohiro <kosaki.motohiro@...il.com>,
	Minchan Kim <minchan@...nel.org>,
	"linux-mm@...ck.org" <linux-mm@...ck.org>
Subject: Re: [PATCH 1/5] [RFC] Add volatile range management code

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 <john.stultz@...aro.org> 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.

thanks
-john

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/