linux-kernel - Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert

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: <50406F60.5040707@intel.com>
Date:	Fri, 31 Aug 2012 11:01:36 +0300
From:	Adrian Hunter <adrian.hunter@...el.com>
To:	akpm@...ux-foundation.org
CC:	Michel Lespinasse <walken@...gle.com>, linux-mm@...ck.org,
	linux-kernel@...r.kernel.org, acme@...hat.com
Subject: Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color()
 only when necessary

On 13/07/12 03:31, Michel Lespinasse wrote:
> The root node of an rbtree must always be black. However, rb_insert_color()
> only needs to maintain this invariant when it has been broken - that is,
> when it exits the loop due to the current (red) node being the root.
> In all other cases (exiting after tree rotations, or exiting due to
> an existing black parent) the invariant is already satisfied, so there
> is no need to adjust the root node color.
> 
> Signed-off-by: Michel Lespinasse <walken@...gle.com>
> ---
>  lib/rbtree.c |   19 +++++++++++++++----
>  1 files changed, 15 insertions(+), 4 deletions(-)
> 
> diff --git a/lib/rbtree.c b/lib/rbtree.c
> index 12abb8a..d0be5fc 100644
> --- a/lib/rbtree.c
> +++ b/lib/rbtree.c
> @@ -91,8 +91,21 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
>  {
>  	struct rb_node *parent, *gparent;
>  
> -	while ((parent = rb_parent(node)) && rb_is_red(parent))
> -	{
> +	while (true) {

This breaks tools/perf build in linux-next:

../../lib/rbtree.c: In function 'rb_insert_color':
../../lib/rbtree.c:95:9: error: 'true' undeclared (first use in this function)
../../lib/rbtree.c:95:9: note: each undeclared identifier is reported only once for each function it appears in
../../lib/rbtree.c: In function '__rb_erase_color':
../../lib/rbtree.c:216:9: error: 'true' undeclared (first use in this function)
../../lib/rbtree.c: In function 'rb_erase':
../../lib/rbtree.c:368:2: error: unknown type name 'bool'
make: *** [util/rbtree.o] Error 1

How about:

From: Adrian Hunter <adrian.hunter@...el.com>
Date: Fri, 31 Aug 2012 10:49:27 +0300
Subject: [PATCH] perf tools: fix build for another rbtree.c change

Fixes:

../../lib/rbtree.c: In function 'rb_insert_color':
../../lib/rbtree.c:95:9: error: 'true' undeclared (first use in this function)
../../lib/rbtree.c:95:9: note: each undeclared identifier is reported only once for each function it appears in
../../lib/rbtree.c: In function '__rb_erase_color':
../../lib/rbtree.c:216:9: error: 'true' undeclared (first use in this function)
../../lib/rbtree.c: In function 'rb_erase':
../../lib/rbtree.c:368:2: error: unknown type name 'bool'
make: *** [util/rbtree.o] Error 1

Signed-off-by: Adrian Hunter <adrian.hunter@...el.com>
---
 tools/perf/util/include/linux/rbtree.h | 1 +
 1 file changed, 1 insertion(+)

diff --git a/tools/perf/util/include/linux/rbtree.h b/tools/perf/util/include/linux/rbtree.h
index 7a243a1..2a030c5 100644
--- a/tools/perf/util/include/linux/rbtree.h
+++ b/tools/perf/util/include/linux/rbtree.h
@@ -1 +1,2 @@
+#include <stdbool.h>
 #include "../../../../include/linux/rbtree.h"
-- 
1.7.11.4

--
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/