linux-kernel - Re: [PATCH 02/13] rbtree: empty nodes have no color

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, 10 Jul 2012 16:10:28 -0700
From:	Michel Lespinasse <walken@...gle.com>
To:	Daniel Santos <daniel.santos@...ox.com>
Cc:	aarcange@...hat.com, dwmw2@...radead.org, riel@...hat.com,
	peterz@...radead.org, 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 02/13] rbtree: empty nodes have no color

On Tue, Jul 10, 2012 at 3:59 AM, Daniel Santos <danielfsantos@....net> wrote:
>> One final rb_init_node() caller was recently added in sysctl code
>> to implement faster sysctl name lookups. This code doesn't make use
>> of RB_EMPTY_NODE at all, and from what I could see it only called
>> rb_init_node() under the mistaken assumption that such initialization
>> was required before node insertion.
> That was one of the problems with rb_init_node().  Not being documented,
> one would assume it's needed unless you study the code more closely.

Agree, the name made it sound like it was required, while it wasn't.

Looking at the code history, it's pretty clear that the function was
introduced for the wrong reasons...

> BTW, the current revision of my patches adds some doc comments to struct
> rb_node since the actual function of rb_parent_color isn't very clear
> without a lot of study.
>
> /**
>  * struct rb_node
>  * @rb_parent_color: Contains the color in the lower 2 bits (although
> only bit
>  *              zero is currently used) and the address of the parent in
>  *              the rest (lower 2 bits of address should always be zero on
>  *              any arch supported).  If the node is initialized and not a
>  *              member of any tree, the parent point to its self.  If the
>  *              node belongs to a tree, but is the root element, the
>  *              parent will be NULL.  Otherwise, parent will always
>  *              point to the parent node in the tree.
>  * @rb_right:        Pointer to the right element.
>  * @rb_left:         Pointer to the left element.
>  */
>
> That said, there's an extra bit in the rb_parent_color that can be used
> for some future purpose.

My preference would be for such comments to go into lib/rbtree.c, NOT
include/lib/rbtree.h . The reason being that we really don't want
rbtree users to start depending on rbtree internals - it's best if
they just stick to using the documented APIs :)

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