| 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
| ||
|
Message-ID: <20120712011208.GA1152@google.com>
Date: Wed, 11 Jul 2012 18:12:08 -0700
From: Michel Lespinasse <walken@...gle.com>
To: Peter Zijlstra <peterz@...radead.org>
Cc: aarcange@...hat.com, dwmw2@...radead.org, riel@...hat.com,
daniel.santos@...ox.com, axboe@...nel.dk, ebiederm@...ssion.com,
linux-mm@...ck.org, akpm@...ux-foundation.org,
linux-kernel@...r.kernel.org, torvalds@...ux-foundation.org
Subject: Re: [PATCH 00/13] rbtree updates
On Wed, Jul 11, 2012 at 6:23 AM, Peter Zijlstra <peterz@...radead.org> wrote:
> Looks nice.. How about something like the below on top.. I couldn't
> immediately find a sane reason for the grand-parent to always be red in
> the insertion case.
Do you mean the case you marked XXX ? it is actually parent that is
red, which we know because we tested that a few lines earlier.
> @@ -85,12 +104,27 @@ void rb_insert_color(struct rb_node *nod
> } else if (rb_is_black(parent))
> break;
>
> + /*
> + * XXX
> + */
> gparent = rb_red_parent(parent);
See :)
> if (parent == gparent->rb_left) {
> tmp = gparent->rb_right;
> if (tmp && rb_is_red(tmp)) {
> - /* Case 1 - color flips */
> + /*
> + * Case 1 - color flips
> + *
> + * G g
> + * / \ / \
> + * p u --> P U
> + * / /
> + * n N
> + *
> + * However, since g's parent might be red, and
> + * 4) does not allow this, we need to recurse
> + * at g.
> + */
I like these diagrams - I initially didn't think they'd work well, given the need for colors etc, but I now see that it's workable.
In __rb_erase_color(), some of the cases are more complicated than you drew however, because some node colors aren't known.
This is what I ended up with:
* 5), then the longest possible path due to 4 is 2B.
*
* We shall indicate color with case, where black nodes are uppercase and red
- * nodes will be lowercase.
+ * nodes will be lowercase. Unknown color nodes shall be drawn as red with
+ * some accompanying text comment.
*/
+ /*
+ * Case 2 - sibling color flip
+ * (p could be either color here)
+ *
+ * p p
+ * / \ / \
+ * N S --> N s
+ * / \ / \
+ * Sl Sr Sl Sr
+ *
+ * This leaves us violating 5), so
+ * recurse at p. If p is red, the
+ * recursion will just flip it to black
+ * and exit. If coming from Case 1,
+ * p is known to be red.
+ */
+ /*
+ * Case 3 - right rotate at sibling
+ * (p could be either color here)
+ *
+ * p p
+ * / \ / \
+ * N S --> N Sl
+ * / \ \
+ * sl Sr s
+ * \
+ * Sr
+ */
+ /*
+ * Case 4 - left rotate at parent + color flips
+ * (p and sl could be either color here.
+ * After rotation, p becomes black, s acquires
+ * p's color, and sl keeps its color)
+ *
+ * p s
+ * / \ / \
+ * N S --> P Sr
+ * / \ / \
+ * sl sr N sl
+ */
--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
--
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/
Powered by blists - more mailing lists