linux-kernel - Re: [PATCH 1/3] Range tree implementation

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: <4F9AF4A8.40901@linaro.org>
Date:	Fri, 27 Apr 2012 12:34:00 -0700
From:	John Stultz <john.stultz@...aro.org>
To:	Dmitry Adamushko <dmitry.adamushko@...il.com>
CC:	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>,
	Dave Chinner <david@...morbit.com>, Neil Brown <neilb@...e.de>,
	Andrea Righi <andrea@...terlinux.com>,
	"Aneesh Kumar K.V" <aneesh.kumar@...ux.vnet.ibm.com>
Subject: Re: [PATCH 1/3] Range tree implementation

On 04/26/2012 03:00 AM, Dmitry Adamushko wrote:
>>> [ ... ]
>>>
>>> Almost everything is common rb_tree-handling code that can be found in
>>> any place where rb-trees are used (hard-coded for flexibility,
>>> performance or whatever other reasons). So my feeling is that it
>>> should not be different here.
>>>
>> Sorry, not sure I quite understand what you're suggesting. Are you saying it
>> doesn't make sense to have a generic range tree implementation, since really
>> its just a small shim over the rbtree code?  So instead range-tree users
>> should just implment them themselves?
> Exactly. It's not much different from other rbtree
> search-insert-delete implementations out there.
>
> What are the generic use cases that we want to support with this interface?

Well, Andrew really wants to see posix file locking to reuse something 
like this (which is the whole reason I split it out separately). And 
Aneesh has similar range management needs for his hugetlb region tracking.

> Is the current notion of the 'overlapping range' as taken by
> range_tree_in_range() common enough? What if another use-case requires
> _only_ the ranges that are strictly inside the [ start, end ] range?
> In this case, we might be better off sticking to the same
> 'implement-your-own-search' approach taken by the generic rbtree
> interface.
Or we could extend the interface for more specific requests?

So its true that the range-tree construct is a pretty thin layer over 
the rbtree code, but even so, we've had a few places in the kernel where 
folks basically are duplicating the same logic over and over again, so 
it might make sense to consolidate the obvious use cases, even just to 
avoid some of the simpler bugs that can happen with rbtree logic (for 
instance, I sent a simple fix to an rbtree related thinko in Rafael's 
recent userspace wakelock api earlier this week).

Anther example is the timerqueue structure I added earlier, which again 
is a thin shim over the rbtree, but allows a few different users to 
share code for quick insert ordered list behavior.

So yea, even though its fairly thin, I think it still has value for reuse.

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/