[patch] avoid kmemcheck warning in epoll

[patch] avoid kmemcheck warning in epoll

[Davide Libenzi]

Epoll calls rb_set_parent(n, n) to initialize the rb-tree node, but 
rb_set_parent() accesses node's pointer in its code. This creates a 
warning in kmemcheck (reported by Vegard Nossum) about an uninitialized 
memory access. The warning is harmless since the following rb-tree node 
insert is going to overwrite the node data. In any case I think it's 
better to not have that happening at all, and fix it by properly 
initializing the data.


Signed-off-by: Davide Libenzi <davidel@xmailserver.org>


- Davide


---
 fs/eventpoll.c         |    2 +-
 include/linux/rbtree.h |   12 ++++++++++++
 2 files changed, 13 insertions(+), 1 deletion(-)

Index: linux-2.6.mod/fs/eventpoll.c
===================================================================
--- linux-2.6.mod.orig/fs/eventpoll.c	2008-02-10 12:36:20.000000000 -0800
+++ linux-2.6.mod/fs/eventpoll.c	2008-02-10 12:50:41.000000000 -0800
@@ -260,7 +260,7 @@
 /* Special initialization for the RB tree node to detect linkage */
 static inline void ep_rb_initnode(struct rb_node *n)
 {
-	rb_set_parent(n, n);
+	rb_init_node(n, n);
 }
 
 /* Removes a node from the RB tree and marks it for a fast is-linked check */
Index: linux-2.6.mod/include/linux/rbtree.h
===================================================================
--- linux-2.6.mod.orig/include/linux/rbtree.h	2008-02-10 12:36:13.000000000 -0800
+++ linux-2.6.mod/include/linux/rbtree.h	2008-02-10 12:51:57.000000000 -0800
@@ -112,6 +112,18 @@
 	struct rb_node *rb_node;
 };
 
+/**
+ * rb_init_node - Initializes the node internal data
+ *
+ * @node: Pointer to the RB-Tree node
+ * @parent: Pointer to the parent node, or NULL
+ *
+ */
+static inline void rb_init_node(struct rb_node *node, struct rb_node *parent)
+{
+	node->rb_parent_color = (unsigned long) parent;
+	node->rb_left = node->rb_right = NULL;
+}
 
 #define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
 #define rb_color(r)   ((r)->rb_parent_color & 1)

Re: [patch] avoid kmemcheck warning in epoll

[Andrew Morton]

On Sun, 10 Feb 2008 13:32:01 -0800 (PST)
Davide Libenzi <davidel@xmailserver.org> wrote:

> Epoll calls rb_set_parent(n, n) to initialize the rb-tree node, but 
> rb_set_parent() accesses node's pointer in its code. This creates a 
> warning in kmemcheck (reported by Vegard Nossum) about an uninitialized 
> memory access. The warning is harmless since the following rb-tree node 
> insert is going to overwrite the node data. In any case I think it's 
> better to not have that happening at all, and fix it by properly 
> initializing the data.
> 
> 
> Signed-off-by: Davide Libenzi <davidel@xmailserver.org>
> 
> 
> - Davide
> 
> 
> ---
>  fs/eventpoll.c         |    2 +-
>  include/linux/rbtree.h |   12 ++++++++++++
>  2 files changed, 13 insertions(+), 1 deletion(-)
> 
> Index: linux-2.6.mod/fs/eventpoll.c
> ===================================================================
> --- linux-2.6.mod.orig/fs/eventpoll.c	2008-02-10 12:36:20.000000000 -0800
> +++ linux-2.6.mod/fs/eventpoll.c	2008-02-10 12:50:41.000000000 -0800
> @@ -260,7 +260,7 @@
>  /* Special initialization for the RB tree node to detect linkage */
>  static inline void ep_rb_initnode(struct rb_node *n)
>  {
> -	rb_set_parent(n, n);
> +	rb_init_node(n, n);
>  }
>  
>  /* Removes a node from the RB tree and marks it for a fast is-linked check */
> Index: linux-2.6.mod/include/linux/rbtree.h
> ===================================================================
> --- linux-2.6.mod.orig/include/linux/rbtree.h	2008-02-10 12:36:13.000000000 -0800
> +++ linux-2.6.mod/include/linux/rbtree.h	2008-02-10 12:51:57.000000000 -0800
> @@ -112,6 +112,18 @@
>  	struct rb_node *rb_node;
>  };
>  
> +/**
> + * rb_init_node - Initializes the node internal data
> + *
> + * @node: Pointer to the RB-Tree node
> + * @parent: Pointer to the parent node, or NULL
> + *
> + */
> +static inline void rb_init_node(struct rb_node *node, struct rb_node *parent)
> +{
> +	node->rb_parent_color = (unsigned long) parent;
> +	node->rb_left = node->rb_right = NULL;
> +}

Is epoll the only rbtree-using code which exhibits this problem?  If so,
what is epoll doing differently from all the others?

Re: [patch] avoid kmemcheck warning in epoll

[Davide Libenzi]

On Mon, 11 Feb 2008, Andrew Morton wrote:

> On Sun, 10 Feb 2008 13:32:01 -0800 (PST)
> Davide Libenzi <davidel@xmailserver.org> wrote:
> 
> > Epoll calls rb_set_parent(n, n) to initialize the rb-tree node, but 
> > rb_set_parent() accesses node's pointer in its code. This creates a 
> > warning in kmemcheck (reported by Vegard Nossum) about an uninitialized 
> > memory access. The warning is harmless since the following rb-tree node 
> > insert is going to overwrite the node data. In any case I think it's 
> > better to not have that happening at all, and fix it by properly 
> > initializing the data.
> > 
> > 
> > Signed-off-by: Davide Libenzi <davidel@xmailserver.org>
> > 
> > 
> > - Davide
> > 
> > 
> > ---
> >  fs/eventpoll.c         |    2 +-
> >  include/linux/rbtree.h |   12 ++++++++++++
> >  2 files changed, 13 insertions(+), 1 deletion(-)
> > 
> > Index: linux-2.6.mod/fs/eventpoll.c
> > ===================================================================
> > --- linux-2.6.mod.orig/fs/eventpoll.c	2008-02-10 12:36:20.000000000 -0800
> > +++ linux-2.6.mod/fs/eventpoll.c	2008-02-10 12:50:41.000000000 -0800
> > @@ -260,7 +260,7 @@
> >  /* Special initialization for the RB tree node to detect linkage */
> >  static inline void ep_rb_initnode(struct rb_node *n)
> >  {
> > -	rb_set_parent(n, n);
> > +	rb_init_node(n, n);
> >  }
> >  
> >  /* Removes a node from the RB tree and marks it for a fast is-linked check */
> > Index: linux-2.6.mod/include/linux/rbtree.h
> > ===================================================================
> > --- linux-2.6.mod.orig/include/linux/rbtree.h	2008-02-10 12:36:13.000000000 -0800
> > +++ linux-2.6.mod/include/linux/rbtree.h	2008-02-10 12:51:57.000000000 -0800
> > @@ -112,6 +112,18 @@
> >  	struct rb_node *rb_node;
> >  };
> >  
> > +/**
> > + * rb_init_node - Initializes the node internal data
> > + *
> > + * @node: Pointer to the RB-Tree node
> > + * @parent: Pointer to the parent node, or NULL
> > + *
> > + */
> > +static inline void rb_init_node(struct rb_node *node, struct rb_node *parent)
> > +{
> > +	node->rb_parent_color = (unsigned long) parent;
> > +	node->rb_left = node->rb_right = NULL;
> > +}
> 
> Is epoll the only rbtree-using code which exhibits this problem?  If so,
> what is epoll doing differently from all the others?

Dunno, but I don't think so. Epoll initializes the node to a state so that 
later on can check if the file-fd item is inserted or not. And it uses the 
"parent" information for that. But rb_set_parent() (that is used in the 
current initialization code) uses the data in the node, and this triggers 
the uninitialized memory access.
Taking a better look at it, the code (after the latest changes) has no 
more point-of-failures after the rb-tree insert, so I can probably avoid 
doing the node's parent-initialization and check altogether.
Yeah, let's that ;)

 eventpoll.c |   27 +++------------------------
 1 file changed, 3 insertions(+), 24 deletions(-)

Andrew, drop that one. I'm gonna send the new one after some test...



- Davide

[patch] avoid kmemcheck warning in epoll

[Davide Libenzi]

Epoll calls rb_set_parent(n, n) to initialize the rb-tree node, but 
rb_set_parent() accesses node's pointer in its code. This creates a 
warning in kmemcheck (reported by Vegard Nossum) about an uninitialized 
memory access. The warning is harmless since the following rb-tree node 
insert is going to overwrite the node data. In any case I think it's 
better to not have that happening at all, and fix it by simplifying the 
code to get rid of a few lines that became superfluous after the previous 
epoll changes.



Signed-off-by: Davide Libenzi <davidel@xmailserver.org>


- Davide


---
 fs/eventpoll.c |   27 +++------------------------
 1 file changed, 3 insertions(+), 24 deletions(-)

Index: linux-2.6.mod/fs/eventpoll.c
===================================================================
--- linux-2.6.mod.orig/fs/eventpoll.c	2008-02-11 15:31:02.000000000 -0800
+++ linux-2.6.mod/fs/eventpoll.c	2008-02-11 15:32:46.000000000 -0800
@@ -257,25 +257,6 @@
 	        (p1->file < p2->file ? -1 : p1->fd - p2->fd));
 }
 
-/* Special initialization for the RB tree node to detect linkage */
-static inline void ep_rb_initnode(struct rb_node *n)
-{
-	rb_set_parent(n, n);
-}
-
-/* Removes a node from the RB tree and marks it for a fast is-linked check */
-static inline void ep_rb_erase(struct rb_node *n, struct rb_root *r)
-{
-	rb_erase(n, r);
-	rb_set_parent(n, n);
-}
-
-/* Fast check to verify that the item is linked to the main RB tree */
-static inline int ep_rb_linked(struct rb_node *n)
-{
-	return rb_parent(n) != n;
-}
-
 /* Tells us if the item is currently linked */
 static inline int ep_is_linked(struct list_head *p)
 {
@@ -283,13 +264,13 @@
 }
 
 /* Get the "struct epitem" from a wait queue pointer */
-static inline struct epitem * ep_item_from_wait(wait_queue_t *p)
+static inline struct epitem *ep_item_from_wait(wait_queue_t *p)
 {
 	return container_of(p, struct eppoll_entry, wait)->base;
 }
 
 /* Get the "struct epitem" from an epoll queue wrapper */
-static inline struct epitem * ep_item_from_epqueue(poll_table *p)
+static inline struct epitem *ep_item_from_epqueue(poll_table *p)
 {
 	return container_of(p, struct ep_pqueue, pt)->epi;
 }
@@ -411,8 +392,7 @@
 		list_del_init(&epi->fllink);
 	spin_unlock(&file->f_ep_lock);
 
-	if (ep_rb_linked(&epi->rbn))
-		ep_rb_erase(&epi->rbn, &ep->rbr);
+	rb_erase(&epi->rbn, &ep->rbr);
 
 	spin_lock_irqsave(&ep->lock, flags);
 	if (ep_is_linked(&epi->rdllink))
@@ -728,7 +708,6 @@
 		goto error_return;
 
 	/* Item initialization follow here ... */
-	ep_rb_initnode(&epi->rbn);
 	INIT_LIST_HEAD(&epi->rdllink);
 	INIT_LIST_HEAD(&epi->fllink);
 	INIT_LIST_HEAD(&epi->pwqlist);

Re: [patch] avoid kmemcheck warning in epoll

[Andrew Morton]

On Mon, 11 Feb 2008 22:03:21 -0800 (PST) Davide Libenzi <davidel@xmailserver.org> wrote:
>

Thanks.

> Subject: [patch] avoid kmemcheck warning in epoll

I converted this to "epoll: avoid kmemcheck warning", as per
SubmittingPatches's section 14.