linux-kernel - Re: [PATCH] rbtree: introduce three helpers about sort-order iteration

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: <20200309165511.GK12561@hirez.programming.kicks-ass.net>
Date:   Mon, 9 Mar 2020 17:55:11 +0100
From:   Peter Zijlstra <peterz@...radead.org>
To:     qiwuchen55@...il.com
Cc:     akpm@...ux-foundation.org, walken@...gle.com, rfontana@...hat.com,
        dbueso@...e.de, tglx@...utronix.de, linux-kernel@...r.kernel.org,
        chenqiwu <chenqiwu@...omi.com>
Subject: Re: [PATCH] rbtree: introduce three helpers about sort-order
 iteration

On Tue, Mar 10, 2020 at 12:02:14AM +0800, qiwuchen55@...il.com wrote:
> +/**
> + * rbtree_for_each_entry_safe - iterate in sort-order over of given type
> + * allowing the backing memory of @pos to be invalidated.
> + * @pos:	the 'type *' to use as a loop cursor.
> + * @n:		another 'type *' to use as temporary storage.
> + * @root:	'rb_root *' of the rbtree.
> + * @field:	the name of the rb_node field within 'type'.
> + *
> + * rbtree_order_for_each_entry_safe() provides a similar guarantee as
> + * list_for_each_entry_safe() and allows the sort-order iteration to
> + * continue independent of changes to @pos by the body of the loop.
> + *
> + * Note, however, that it cannot handle other modifications that re-order the
> + * rbtree it is iterating over. This includes calling rb_erase() on @pos, as
> + * rb_erase() may rebalance the tree, causing us to miss some nodes.
> + */
> +#define rbtree_for_each_entry_safe(pos, n, root, field) \
> +	for (pos = rb_entry_safe(rb_first(root), typeof(*pos), field); \
> +	     pos && ({ n = rb_entry_safe(rb_next(&pos->field), \
> +			typeof(*pos), field); 1; }); \
> +	     pos = n)

Since this cannot deal with rb_erase(), what exactly is the purpose of
this thing?