From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752000AbdEPVRb (ORCPT ); Tue, 16 May 2017 17:17:31 -0400 Received: from mx2.suse.de ([195.135.220.15]:57115 "EHLO mx1.suse.de" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1750799AbdEPVR1 (ORCPT ); Tue, 16 May 2017 17:17:27 -0400 Date: Tue, 16 May 2017 14:17:14 -0700 From: Davidlohr Bueso To: Peter Zijlstra Cc: mingo@kernel.org, akpm@linux-foundation.org, jack@suse.cz, kirill.shutemov@linux.intel.com, ldufour@linux.vnet.ibm.com, mhocko@suse.com, mgorman@techsingularity.net, linux-kernel@vger.kernel.org, Davidlohr Bueso Subject: Re: [PATCH 2/6] locking: Introduce range reader/writer lock Message-ID: <20170516211714.GD2966@linux-80c1.suse> References: <20170515090725.27055-1-dave@stgolabs.net> <20170515090725.27055-3-dave@stgolabs.net> <20170515134459.sl3jfewo7uj62cqs@hirez.programming.kicks-ass.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Disposition: inline In-Reply-To: <20170515134459.sl3jfewo7uj62cqs@hirez.programming.kicks-ass.net> User-Agent: Mutt/1.5.24 (2015-08-30) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, 15 May 2017, Peter Zijlstra wrote: >Nearly every range_interval_tree_foreach() usage has a >__range_intersects_intree() in front, suggesting our >range_interval_tree_foreach() is 'broken'. > >I suppose the only question is if we should fix >range_interval_tree_foreach() or interval_tree_iter_first(). I'm tempted >to suggest the latter. Yes this functionality would be helpful to all interval tree users, but for that we have to cache the leftmost node, and given the way interval trees are setup via templates, the latter gets icky _fast_: - For one we could add extra parameters to INTERVAL_TREE_DEFINE and pass an arbitrary structure that contains a ptr to the node type as well as the rb_root. This of course busts the generic flavor. Or, - Add a second leftmost rb_node to struct rb_root and (at least) only use it for interval trees; while there are rbtree users that do this caching explicitly, I doubt folks would like for the general case. So it would seem that we ought to tuck __range_intersects_intree() in the range_interval_tree_foreach() helper. Thanks, Davidlohr