linux-kernel - Re: [PATCH 2/6] locking: Introduce range reader/writer lock

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]

Date:   Tue, 16 May 2017 14:17:14 -0700
From:   Davidlohr Bueso <dave@...olabs.net>
To:     Peter Zijlstra <peterz@...radead.org>
Cc:     mingo@...nel.org, akpm@...ux-foundation.org, jack@...e.cz,
        kirill.shutemov@...ux.intel.com, ldufour@...ux.vnet.ibm.com,
        mhocko@...e.com, mgorman@...hsingularity.net,
        linux-kernel@...r.kernel.org, Davidlohr Bueso <dbueso@...e.de>
Subject: Re: [PATCH 2/6] locking: Introduce range reader/writer lock

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