linux-kernel - 答复: 答复: 答复: [PATCH] rbtree: stop iteration early in rb_find

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 for Android: free password hash cracker in your pocket

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

Message-ID: <770bfd98d67e4c6cbfbb341d70ecf448@baidu.com>
Date:   Thu, 26 Aug 2021 05:03:54 +0000
From:   "Li,Rongqing" <lirongqing@...du.com>
To:     Peter Zijlstra <peterz@...radead.org>
CC:     Michel Lespinasse <michel@...pinasse.org>,
        "dbueso@...e.de" <dbueso@...e.de>,
        "mingo@...nel.org" <mingo@...nel.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>
Subject: 答复: 答复: 答复: [PATCH] rbtree: stop iteration early in rb_find_first

> You're right that rb_add() does a tail-add for elements it considers equal -- there
> is actually code in the tree that relies on this.
> 
> But that doesn't mean rb_find_first() should go right, it *must*not*, because
> then it wouldn't find the 'first' aka 'leftmost' instance of the equal elements.
> 
> Also, you're only considering building the tree in-order with rb_add(), trees get
> modified all the time and the pattern Michel gave is perfectly valid (also see
> rb_prev()).
> 
> Sure the snippet is not a balanced tree, but you can construct the pattern as
> part of a larger tree just fine, just add some elements:
> 
> 
> 	 10(b)
> 	/  \
>        5   10(c)
>         \
> 	10(a)
> 
> is a tree that is balanced (remember, RB trees only require the left and right
> depths to no more than double -- as opposed to AVL trees, which have a tighter
> constraint). This tree has order: 5, 10(a), 10(b), 10(c).
> Also note that the tree rotations are stable -- they must be since they do not
> refence the order function.
> 
> As such, if we rb_find_first() for 10, we must find 10(a), the leftmost
> 10 in the tree.

I see, Thanks for the explanation. Sorry for the noise.

-Li