[PATCH dwarves] pahole: avoid adding same struct structure to two rb trees

[PATCH dwarves] pahole: avoid adding same struct structure to two rb trees

[Eduard Zingerman]

When pahole is executed in '-F dwarf --sort' mode there are two places
where 'struct structure' instance could be added to the rb_tree:

The first is triggered from the following call stack:

  print_classes()
    structures__add()
      __structures__add()
        (adds to global pahole.c:structures__tree)

The second is triggered from the following call stack:

  print_ordered_classes()
    resort_classes()
      resort_add()
        (adds to local rb_tree instance)

Both places use the same 'struct structure::rb_node' field, so if both
code pathes are executed the final state of the 'structures__tree'
might be inconsistent.

For example, this could be observed when DEBUG_CHECK_LEAKS build flag
is set. Here is the command line snippet that eventually leads to a
segfault:

  $ for i in $(seq 1 100); do \
      echo $i; \
      pahole -F dwarf --flat_arrays --sort --jobs vmlinux > /dev/null \
             || break; \
    done

GDB shows the following stack trace:

  Thread 1 "pahole" received signal SIGSEGV, Segmentation fault.
  0x00007ffff7f819ad in __rb_erase_color (node=0x7fffd4045830, parent=0x0, root=0x5555555672d8 <structures.tree>) at /home/eddy/work/dwarves-fork/rbtree.c:134
  134			if (parent->rb_left == node)
  (gdb) bt
  #0  0x00007ffff7f819ad in __rb_erase_color (node=0x7fffd4045830, parent=0x0, root=0x5555555672d8 <structures.tree>) at /home/eddy/work/dwarves-fork/rbtree.c:134
  #1  0x00007ffff7f82014 in rb_erase (node=0x7fff21ae5b80, root=0x5555555672d8 <structures.tree>) at /home/eddy/work/dwarves-fork/rbtree.c:275
  #2  0x0000555555559c3d in __structures__delete () at /home/eddy/work/dwarves-fork/pahole.c:440
  #3  0x0000555555559c70 in structures__delete () at /home/eddy/work/dwarves-fork/pahole.c:448
  #4  0x0000555555560bb6 in main (argc=13, argv=0x7fffffffdcd8) at /home/eddy/work/dwarves-fork/pahole.c:3584

This commit modifies resort_classes() to re-use 'structures__tree' and
to reset 'rb_node' fields before adding structure instances to the
tree for a second time.

Lock/unlock structures_lock to be consistent with structures_add() and
structures__delete() code.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 pahole.c | 41 ++++++++++++++++++++++++++++-------------
 1 file changed, 28 insertions(+), 13 deletions(-)

diff --git a/pahole.c b/pahole.c
index 6fc4ed6..576733f 100644
--- a/pahole.c
+++ b/pahole.c
@@ -621,9 +621,9 @@ static void print_classes(struct cu *cu)
 	}
 }
 
-static void __print_ordered_classes(struct rb_root *root)
+static void __print_ordered_classes(void)
 {
-	struct rb_node *next = rb_first(root);
+	struct rb_node *next = rb_first(&structures__tree);
 
 	while (next) {
 		struct structure *st = rb_entry(next, struct structure, rb_node);
@@ -660,24 +660,39 @@ static void resort_add(struct rb_root *resorted, struct structure *str)
 	rb_insert_color(&str->rb_node, resorted);
 }
 
-static void resort_classes(struct rb_root *resorted, struct list_head *head)
+static void resort_classes(void)
 {
 	struct structure *str;
 
-	list_for_each_entry(str, head, node)
-		resort_add(resorted, str);
+	pthread_mutex_lock(&structures_lock);
+
+	/* The need_resort flag is set by type__compare_members()
+	 * within the following call stack:
+	 *
+	 *   print_classes()
+	 *     structures__add()
+	 *       __structures__add()
+	 *         type__compare()
+	 *
+	 * The call to structures__add() registers 'struct structures'
+	 * instances in both 'structures__tree' and 'structures__list'.
+	 * In order to avoid adding same node to the tree twice reset
+	 * both the 'structures__tree' and 'str->rb_node'.
+	 */
+	structures__tree = RB_ROOT;
+	list_for_each_entry(str, &structures__list, node) {
+		bzero(&str->rb_node, sizeof(str->rb_node));
+		resort_add(&structures__tree, str);
+	}
+
+	pthread_mutex_unlock(&structures_lock);
 }
 
 static void print_ordered_classes(void)
 {
-	if (!need_resort) {
-		__print_ordered_classes(&structures__tree);
-	} else {
-		struct rb_root resorted = RB_ROOT;
-
-		resort_classes(&resorted, &structures__list);
-		__print_ordered_classes(&resorted);
-	}
+	if (need_resort)
+		resort_classes();
+	__print_ordered_classes();
 }
 
 
-- 
2.40.1

Re: [PATCH dwarves] pahole: avoid adding same struct structure to two rb trees

[Arnaldo Carvalho de Melo]

Em Fri, May 26, 2023 at 02:59:49AM +0300, Eduard Zingerman escreveu:
> When pahole is executed in '-F dwarf --sort' mode there are two places
> where 'struct structure' instance could be added to the rb_tree:
> 
> The first is triggered from the following call stack:
> 
>   print_classes()
>     structures__add()
>       __structures__add()
>         (adds to global pahole.c:structures__tree)
> 
> The second is triggered from the following call stack:
> 
>   print_ordered_classes()
>     resort_classes()
>       resort_add()
>         (adds to local rb_tree instance)
> 
> Both places use the same 'struct structure::rb_node' field, so if both
> code pathes are executed the final state of the 'structures__tree'
> might be inconsistent.
> 
> For example, this could be observed when DEBUG_CHECK_LEAKS build flag
> is set. Here is the command line snippet that eventually leads to a
> segfault:
> 
>   $ for i in $(seq 1 100); do \
>       echo $i; \
>       pahole -F dwarf --flat_arrays --sort --jobs vmlinux > /dev/null \
>              || break; \
>     done
> 
> GDB shows the following stack trace:
> 
>   Thread 1 "pahole" received signal SIGSEGV, Segmentation fault.
>   0x00007ffff7f819ad in __rb_erase_color (node=0x7fffd4045830, parent=0x0, root=0x5555555672d8 <structures.tree>) at /home/eddy/work/dwarves-fork/rbtree.c:134
>   134			if (parent->rb_left == node)
>   (gdb) bt
>   #0  0x00007ffff7f819ad in __rb_erase_color (node=0x7fffd4045830, parent=0x0, root=0x5555555672d8 <structures.tree>) at /home/eddy/work/dwarves-fork/rbtree.c:134
>   #1  0x00007ffff7f82014 in rb_erase (node=0x7fff21ae5b80, root=0x5555555672d8 <structures.tree>) at /home/eddy/work/dwarves-fork/rbtree.c:275
>   #2  0x0000555555559c3d in __structures__delete () at /home/eddy/work/dwarves-fork/pahole.c:440
>   #3  0x0000555555559c70 in structures__delete () at /home/eddy/work/dwarves-fork/pahole.c:448
>   #4  0x0000555555560bb6 in main (argc=13, argv=0x7fffffffdcd8) at /home/eddy/work/dwarves-fork/pahole.c:3584
> 
> This commit modifies resort_classes() to re-use 'structures__tree' and
> to reset 'rb_node' fields before adding structure instances to the
> tree for a second time.
> 
> Lock/unlock structures_lock to be consistent with structures_add() and
> structures__delete() code.
> 
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  pahole.c | 41 ++++++++++++++++++++++++++++-------------
>  1 file changed, 28 insertions(+), 13 deletions(-)
> 
> diff --git a/pahole.c b/pahole.c
> index 6fc4ed6..576733f 100644
> --- a/pahole.c
> +++ b/pahole.c
> @@ -621,9 +621,9 @@ static void print_classes(struct cu *cu)
>  	}
>  }
>  
> -static void __print_ordered_classes(struct rb_root *root)
> +static void __print_ordered_classes(void)
>  {
> -	struct rb_node *next = rb_first(root);
> +	struct rb_node *next = rb_first(&structures__tree);
>  
>  	while (next) {
>  		struct structure *st = rb_entry(next, struct structure, rb_node);
> @@ -660,24 +660,39 @@ static void resort_add(struct rb_root *resorted, struct structure *str)
>  	rb_insert_color(&str->rb_node, resorted);
>  }
>  
> -static void resort_classes(struct rb_root *resorted, struct list_head *head)
> +static void resort_classes(void)
>  {
>  	struct structure *str;
>  
> -	list_for_each_entry(str, head, node)
> -		resort_add(resorted, str);
> +	pthread_mutex_lock(&structures_lock);
> +
> +	/* The need_resort flag is set by type__compare_members()
> +	 * within the following call stack:
> +	 *
> +	 *   print_classes()
> +	 *     structures__add()
> +	 *       __structures__add()
> +	 *         type__compare()
> +	 *
> +	 * The call to structures__add() registers 'struct structures'
> +	 * instances in both 'structures__tree' and 'structures__list'.
> +	 * In order to avoid adding same node to the tree twice reset
> +	 * both the 'structures__tree' and 'str->rb_node'.
> +	 */
> +	structures__tree = RB_ROOT;
> +	list_for_each_entry(str, &structures__list, node) {
> +		bzero(&str->rb_node, sizeof(str->rb_node));

Why is this bzero needed?

> +		resort_add(&structures__tree, str);

resort_add will call rb_link_node(&str->rb_node, parent, p); and it, in
turn:

static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
                                struct rb_node ** rb_link)
{
        node->rb_parent_color = (unsigned long )parent;
        node->rb_left = node->rb_right = NULL;

        *rb_link = node;
}

And:

struct rb_node
{
        unsigned long  rb_parent_color;
#define RB_RED          0
#define RB_BLACK        1
        struct rb_node *rb_right;
        struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))))

So all the fields are being initialized in the operation right after the
bzero(), no?

- Arnaldo

> +	}
> +
> +	pthread_mutex_unlock(&structures_lock);
>  }
>  
>  static void print_ordered_classes(void)
>  {
> -	if (!need_resort) {
> -		__print_ordered_classes(&structures__tree);
> -	} else {
> -		struct rb_root resorted = RB_ROOT;
> -
> -		resort_classes(&resorted, &structures__list);
> -		__print_ordered_classes(&resorted);
> -	}
> +	if (need_resort)
> +		resort_classes();
> +	__print_ordered_classes();
>  }
>  
>  
> -- 
> 2.40.1
> 

-- 

- Arnaldo

Re: [PATCH dwarves] pahole: avoid adding same struct structure to two rb trees

[Eduard Zingerman]

On Fri, 2023-06-02 at 10:42 -0300, Arnaldo Carvalho de Melo wrote:
> Em Fri, May 26, 2023 at 02:59:49AM +0300, Eduard Zingerman escreveu:
> > When pahole is executed in '-F dwarf --sort' mode there are two places
> > where 'struct structure' instance could be added to the rb_tree:
> > 
> > The first is triggered from the following call stack:
> > 
> >   print_classes()
> >     structures__add()
> >       __structures__add()
> >         (adds to global pahole.c:structures__tree)
> > 
> > The second is triggered from the following call stack:
> > 
> >   print_ordered_classes()
> >     resort_classes()
> >       resort_add()
> >         (adds to local rb_tree instance)
> > 
> > Both places use the same 'struct structure::rb_node' field, so if both
> > code pathes are executed the final state of the 'structures__tree'
> > might be inconsistent.
> > 
> > For example, this could be observed when DEBUG_CHECK_LEAKS build flag
> > is set. Here is the command line snippet that eventually leads to a
> > segfault:
> > 
> >   $ for i in $(seq 1 100); do \
> >       echo $i; \
> >       pahole -F dwarf --flat_arrays --sort --jobs vmlinux > /dev/null \
> >              || break; \
> >     done
> > 
> > GDB shows the following stack trace:
> > 
> >   Thread 1 "pahole" received signal SIGSEGV, Segmentation fault.
> >   0x00007ffff7f819ad in __rb_erase_color (node=0x7fffd4045830, parent=0x0, root=0x5555555672d8 <structures.tree>) at /home/eddy/work/dwarves-fork/rbtree.c:134
> >   134			if (parent->rb_left == node)
> >   (gdb) bt
> >   #0  0x00007ffff7f819ad in __rb_erase_color (node=0x7fffd4045830, parent=0x0, root=0x5555555672d8 <structures.tree>) at /home/eddy/work/dwarves-fork/rbtree.c:134
> >   #1  0x00007ffff7f82014 in rb_erase (node=0x7fff21ae5b80, root=0x5555555672d8 <structures.tree>) at /home/eddy/work/dwarves-fork/rbtree.c:275
> >   #2  0x0000555555559c3d in __structures__delete () at /home/eddy/work/dwarves-fork/pahole.c:440
> >   #3  0x0000555555559c70 in structures__delete () at /home/eddy/work/dwarves-fork/pahole.c:448
> >   #4  0x0000555555560bb6 in main (argc=13, argv=0x7fffffffdcd8) at /home/eddy/work/dwarves-fork/pahole.c:3584
> > 
> > This commit modifies resort_classes() to re-use 'structures__tree' and
> > to reset 'rb_node' fields before adding structure instances to the
> > tree for a second time.
> > 
> > Lock/unlock structures_lock to be consistent with structures_add() and
> > structures__delete() code.
> > 
> > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > ---
> >  pahole.c | 41 ++++++++++++++++++++++++++++-------------
> >  1 file changed, 28 insertions(+), 13 deletions(-)
> > 
> > diff --git a/pahole.c b/pahole.c
> > index 6fc4ed6..576733f 100644
> > --- a/pahole.c
> > +++ b/pahole.c
> > @@ -621,9 +621,9 @@ static void print_classes(struct cu *cu)
> >  	}
> >  }
> >  
> > -static void __print_ordered_classes(struct rb_root *root)
> > +static void __print_ordered_classes(void)
> >  {
> > -	struct rb_node *next = rb_first(root);
> > +	struct rb_node *next = rb_first(&structures__tree);
> >  
> >  	while (next) {
> >  		struct structure *st = rb_entry(next, struct structure, rb_node);
> > @@ -660,24 +660,39 @@ static void resort_add(struct rb_root *resorted, struct structure *str)
> >  	rb_insert_color(&str->rb_node, resorted);
> >  }
> >  
> > -static void resort_classes(struct rb_root *resorted, struct list_head *head)
> > +static void resort_classes(void)
> >  {
> >  	struct structure *str;
> >  
> > -	list_for_each_entry(str, head, node)
> > -		resort_add(resorted, str);
> > +	pthread_mutex_lock(&structures_lock);
> > +
> > +	/* The need_resort flag is set by type__compare_members()
> > +	 * within the following call stack:
> > +	 *
> > +	 *   print_classes()
> > +	 *     structures__add()
> > +	 *       __structures__add()
> > +	 *         type__compare()
> > +	 *
> > +	 * The call to structures__add() registers 'struct structures'
> > +	 * instances in both 'structures__tree' and 'structures__list'.
> > +	 * In order to avoid adding same node to the tree twice reset
> > +	 * both the 'structures__tree' and 'str->rb_node'.
> > +	 */
> > +	structures__tree = RB_ROOT;
> > +	list_for_each_entry(str, &structures__list, node) {
> > +		bzero(&str->rb_node, sizeof(str->rb_node));
> 
> Why is this bzero needed?
> 
> > +		resort_add(&structures__tree, str);
> 
> resort_add will call rb_link_node(&str->rb_node, parent, p); and it, in
> turn:
> 
> static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
>                                 struct rb_node ** rb_link)
> {
>         node->rb_parent_color = (unsigned long )parent;
>         node->rb_left = node->rb_right = NULL;
> 
>         *rb_link = node;
> }
> 
> And:
> 
> struct rb_node
> {
>         unsigned long  rb_parent_color;
> #define RB_RED          0
> #define RB_BLACK        1
>         struct rb_node *rb_right;
>         struct rb_node *rb_left;
> } __attribute__((aligned(sizeof(long))))
> 
> So all the fields are being initialized in the operation right after the
> bzero(), no?

Right, you are correct.
The 'structures__tree = RB_ROOT' part is still necessary, though.
If you are ok with overall structure of the patch I can resend it w/o bzero().

> 
> - Arnaldo
> 
> > +	}
> > +
> > +	pthread_mutex_unlock(&structures_lock);
> >  }
> >  
> >  static void print_ordered_classes(void)
> >  {
> > -	if (!need_resort) {
> > -		__print_ordered_classes(&structures__tree);
> > -	} else {
> > -		struct rb_root resorted = RB_ROOT;
> > -
> > -		resort_classes(&resorted, &structures__list);
> > -		__print_ordered_classes(&resorted);
> > -	}
> > +	if (need_resort)
> > +		resort_classes();
> > +	__print_ordered_classes();
> >  }
> >  
> >  
> > -- 
> > 2.40.1
> > 
> 

Re: [PATCH dwarves] pahole: avoid adding same struct structure to two rb trees

[Arnaldo Carvalho de Melo]

Em Fri, Jun 02, 2023 at 04:52:40PM +0300, Eduard Zingerman escreveu:
> On Fri, 2023-06-02 at 10:42 -0300, Arnaldo Carvalho de Melo wrote:
> > Em Fri, May 26, 2023 at 02:59:49AM +0300, Eduard Zingerman escreveu:
> > > When pahole is executed in '-F dwarf --sort' mode there are two places
> > > where 'struct structure' instance could be added to the rb_tree:
> > > 
> > > The first is triggered from the following call stack:
> > > 
> > >   print_classes()
> > >     structures__add()
> > >       __structures__add()
> > >         (adds to global pahole.c:structures__tree)
> > > 
> > > The second is triggered from the following call stack:
> > > 
> > >   print_ordered_classes()
> > >     resort_classes()
> > >       resort_add()
> > >         (adds to local rb_tree instance)
> > > 
> > > Both places use the same 'struct structure::rb_node' field, so if both
> > > code pathes are executed the final state of the 'structures__tree'
> > > might be inconsistent.
> > > 
> > > For example, this could be observed when DEBUG_CHECK_LEAKS build flag
> > > is set. Here is the command line snippet that eventually leads to a
> > > segfault:
> > > 
> > >   $ for i in $(seq 1 100); do \
> > >       echo $i; \
> > >       pahole -F dwarf --flat_arrays --sort --jobs vmlinux > /dev/null \
> > >              || break; \
> > >     done
> > > 
> > > GDB shows the following stack trace:
> > > 
> > >   Thread 1 "pahole" received signal SIGSEGV, Segmentation fault.
> > >   0x00007ffff7f819ad in __rb_erase_color (node=0x7fffd4045830, parent=0x0, root=0x5555555672d8 <structures.tree>) at /home/eddy/work/dwarves-fork/rbtree.c:134
> > >   134			if (parent->rb_left == node)
> > >   (gdb) bt
> > >   #0  0x00007ffff7f819ad in __rb_erase_color (node=0x7fffd4045830, parent=0x0, root=0x5555555672d8 <structures.tree>) at /home/eddy/work/dwarves-fork/rbtree.c:134
> > >   #1  0x00007ffff7f82014 in rb_erase (node=0x7fff21ae5b80, root=0x5555555672d8 <structures.tree>) at /home/eddy/work/dwarves-fork/rbtree.c:275
> > >   #2  0x0000555555559c3d in __structures__delete () at /home/eddy/work/dwarves-fork/pahole.c:440
> > >   #3  0x0000555555559c70 in structures__delete () at /home/eddy/work/dwarves-fork/pahole.c:448
> > >   #4  0x0000555555560bb6 in main (argc=13, argv=0x7fffffffdcd8) at /home/eddy/work/dwarves-fork/pahole.c:3584
> > > 
> > > This commit modifies resort_classes() to re-use 'structures__tree' and
> > > to reset 'rb_node' fields before adding structure instances to the
> > > tree for a second time.
> > > 
> > > Lock/unlock structures_lock to be consistent with structures_add() and
> > > structures__delete() code.
> > > 
> > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > > ---
> > >  pahole.c | 41 ++++++++++++++++++++++++++++-------------
> > >  1 file changed, 28 insertions(+), 13 deletions(-)
> > > 
> > > diff --git a/pahole.c b/pahole.c
> > > index 6fc4ed6..576733f 100644
> > > --- a/pahole.c
> > > +++ b/pahole.c
> > > @@ -621,9 +621,9 @@ static void print_classes(struct cu *cu)
> > >  	}
> > >  }
> > >  
> > > -static void __print_ordered_classes(struct rb_root *root)
> > > +static void __print_ordered_classes(void)
> > >  {
> > > -	struct rb_node *next = rb_first(root);
> > > +	struct rb_node *next = rb_first(&structures__tree);
> > >  
> > >  	while (next) {
> > >  		struct structure *st = rb_entry(next, struct structure, rb_node);
> > > @@ -660,24 +660,39 @@ static void resort_add(struct rb_root *resorted, struct structure *str)
> > >  	rb_insert_color(&str->rb_node, resorted);
> > >  }
> > >  
> > > -static void resort_classes(struct rb_root *resorted, struct list_head *head)
> > > +static void resort_classes(void)
> > >  {
> > >  	struct structure *str;
> > >  
> > > -	list_for_each_entry(str, head, node)
> > > -		resort_add(resorted, str);
> > > +	pthread_mutex_lock(&structures_lock);
> > > +
> > > +	/* The need_resort flag is set by type__compare_members()
> > > +	 * within the following call stack:
> > > +	 *
> > > +	 *   print_classes()
> > > +	 *     structures__add()
> > > +	 *       __structures__add()
> > > +	 *         type__compare()
> > > +	 *
> > > +	 * The call to structures__add() registers 'struct structures'
> > > +	 * instances in both 'structures__tree' and 'structures__list'.
> > > +	 * In order to avoid adding same node to the tree twice reset
> > > +	 * both the 'structures__tree' and 'str->rb_node'.
> > > +	 */
> > > +	structures__tree = RB_ROOT;
> > > +	list_for_each_entry(str, &structures__list, node) {
> > > +		bzero(&str->rb_node, sizeof(str->rb_node));
> > 
> > Why is this bzero needed?
> > 
> > > +		resort_add(&structures__tree, str);
> > 
> > resort_add will call rb_link_node(&str->rb_node, parent, p); and it, in
> > turn:
> > 
> > static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
> >                                 struct rb_node ** rb_link)
> > {
> >         node->rb_parent_color = (unsigned long )parent;
> >         node->rb_left = node->rb_right = NULL;
> > 
> >         *rb_link = node;
> > }
> > 
> > And:
> > 
> > struct rb_node
> > {
> >         unsigned long  rb_parent_color;
> > #define RB_RED          0
> > #define RB_BLACK        1
> >         struct rb_node *rb_right;
> >         struct rb_node *rb_left;
> > } __attribute__((aligned(sizeof(long))))
> > 
> > So all the fields are being initialized in the operation right after the
> > bzero(), no?
> 
> Right, you are correct.
> The 'structures__tree = RB_ROOT' part is still necessary, though.
> If you are ok with overall structure of the patch I can resend it w/o bzero().

Humm, so basically this boils down to the following patch?

- Arnaldo

diff --git a/pahole.c b/pahole.c
index 6fc4ed6a721b97ab..7f7aa0a5db05837d 100644
--- a/pahole.c
+++ b/pahole.c
@@ -674,7 +674,12 @@ static void print_ordered_classes(void)
 		__print_ordered_classes(&structures__tree);
 	} else {
 		struct rb_root resorted = RB_ROOT;
-
+#ifdef DEBUG_CHECK_LEAKS
+		// We'll delete structures from structures__tree, since we're
+		// adding them to ther resorted list, better not keep
+		// references there.
+		structures__tree = RB_ROOT;
+#endif
 		resort_classes(&resorted, &structures__list);
 		__print_ordered_classes(&resorted);
 	}

Re: [PATCH dwarves] pahole: avoid adding same struct structure to two rb trees

[Eduard Zingerman]

On Fri, 2023-06-02 at 15:04 -0300, Arnaldo Carvalho de Melo wrote:
> Em Fri, Jun 02, 2023 at 04:52:40PM +0300, Eduard Zingerman escreveu:
> > On Fri, 2023-06-02 at 10:42 -0300, Arnaldo Carvalho de Melo wrote:
> > > Em Fri, May 26, 2023 at 02:59:49AM +0300, Eduard Zingerman escreveu:
> > > > When pahole is executed in '-F dwarf --sort' mode there are two places
> > > > where 'struct structure' instance could be added to the rb_tree:
> > > > 
> > > > The first is triggered from the following call stack:
> > > > 
> > > >   print_classes()
> > > >     structures__add()
> > > >       __structures__add()
> > > >         (adds to global pahole.c:structures__tree)
> > > > 
> > > > The second is triggered from the following call stack:
> > > > 
> > > >   print_ordered_classes()
> > > >     resort_classes()
> > > >       resort_add()
> > > >         (adds to local rb_tree instance)
> > > > 
> > > > Both places use the same 'struct structure::rb_node' field, so if both
> > > > code pathes are executed the final state of the 'structures__tree'
> > > > might be inconsistent.
> > > > 
> > > > For example, this could be observed when DEBUG_CHECK_LEAKS build flag
> > > > is set. Here is the command line snippet that eventually leads to a
> > > > segfault:
> > > > 
> > > >   $ for i in $(seq 1 100); do \
> > > >       echo $i; \
> > > >       pahole -F dwarf --flat_arrays --sort --jobs vmlinux > /dev/null \
> > > >              || break; \
> > > >     done
> > > > 
> > > > GDB shows the following stack trace:
> > > > 
> > > >   Thread 1 "pahole" received signal SIGSEGV, Segmentation fault.
> > > >   0x00007ffff7f819ad in __rb_erase_color (node=0x7fffd4045830, parent=0x0, root=0x5555555672d8 <structures.tree>) at /home/eddy/work/dwarves-fork/rbtree.c:134
> > > >   134			if (parent->rb_left == node)
> > > >   (gdb) bt
> > > >   #0  0x00007ffff7f819ad in __rb_erase_color (node=0x7fffd4045830, parent=0x0, root=0x5555555672d8 <structures.tree>) at /home/eddy/work/dwarves-fork/rbtree.c:134
> > > >   #1  0x00007ffff7f82014 in rb_erase (node=0x7fff21ae5b80, root=0x5555555672d8 <structures.tree>) at /home/eddy/work/dwarves-fork/rbtree.c:275
> > > >   #2  0x0000555555559c3d in __structures__delete () at /home/eddy/work/dwarves-fork/pahole.c:440
> > > >   #3  0x0000555555559c70 in structures__delete () at /home/eddy/work/dwarves-fork/pahole.c:448
> > > >   #4  0x0000555555560bb6 in main (argc=13, argv=0x7fffffffdcd8) at /home/eddy/work/dwarves-fork/pahole.c:3584
> > > > 
> > > > This commit modifies resort_classes() to re-use 'structures__tree' and
> > > > to reset 'rb_node' fields before adding structure instances to the
> > > > tree for a second time.
> > > > 
> > > > Lock/unlock structures_lock to be consistent with structures_add() and
> > > > structures__delete() code.
> > > > 
> > > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > > > ---
> > > >  pahole.c | 41 ++++++++++++++++++++++++++++-------------
> > > >  1 file changed, 28 insertions(+), 13 deletions(-)
> > > > 
> > > > diff --git a/pahole.c b/pahole.c
> > > > index 6fc4ed6..576733f 100644
> > > > --- a/pahole.c
> > > > +++ b/pahole.c
> > > > @@ -621,9 +621,9 @@ static void print_classes(struct cu *cu)
> > > >  	}
> > > >  }
> > > >  
> > > > -static void __print_ordered_classes(struct rb_root *root)
> > > > +static void __print_ordered_classes(void)
> > > >  {
> > > > -	struct rb_node *next = rb_first(root);
> > > > +	struct rb_node *next = rb_first(&structures__tree);
> > > >  
> > > >  	while (next) {
> > > >  		struct structure *st = rb_entry(next, struct structure, rb_node);
> > > > @@ -660,24 +660,39 @@ static void resort_add(struct rb_root *resorted, struct structure *str)
> > > >  	rb_insert_color(&str->rb_node, resorted);
> > > >  }
> > > >  
> > > > -static void resort_classes(struct rb_root *resorted, struct list_head *head)
> > > > +static void resort_classes(void)
> > > >  {
> > > >  	struct structure *str;
> > > >  
> > > > -	list_for_each_entry(str, head, node)
> > > > -		resort_add(resorted, str);
> > > > +	pthread_mutex_lock(&structures_lock);
> > > > +
> > > > +	/* The need_resort flag is set by type__compare_members()
> > > > +	 * within the following call stack:
> > > > +	 *
> > > > +	 *   print_classes()
> > > > +	 *     structures__add()
> > > > +	 *       __structures__add()
> > > > +	 *         type__compare()
> > > > +	 *
> > > > +	 * The call to structures__add() registers 'struct structures'
> > > > +	 * instances in both 'structures__tree' and 'structures__list'.
> > > > +	 * In order to avoid adding same node to the tree twice reset
> > > > +	 * both the 'structures__tree' and 'str->rb_node'.
> > > > +	 */
> > > > +	structures__tree = RB_ROOT;
> > > > +	list_for_each_entry(str, &structures__list, node) {
> > > > +		bzero(&str->rb_node, sizeof(str->rb_node));
> > > 
> > > Why is this bzero needed?
> > > 
> > > > +		resort_add(&structures__tree, str);
> > > 
> > > resort_add will call rb_link_node(&str->rb_node, parent, p); and it, in
> > > turn:
> > > 
> > > static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
> > >                                 struct rb_node ** rb_link)
> > > {
> > >         node->rb_parent_color = (unsigned long )parent;
> > >         node->rb_left = node->rb_right = NULL;
> > > 
> > >         *rb_link = node;
> > > }
> > > 
> > > And:
> > > 
> > > struct rb_node
> > > {
> > >         unsigned long  rb_parent_color;
> > > #define RB_RED          0
> > > #define RB_BLACK        1
> > >         struct rb_node *rb_right;
> > >         struct rb_node *rb_left;
> > > } __attribute__((aligned(sizeof(long))))
> > > 
> > > So all the fields are being initialized in the operation right after the
> > > bzero(), no?
> > 
> > Right, you are correct.
> > The 'structures__tree = RB_ROOT' part is still necessary, though.
> > If you are ok with overall structure of the patch I can resend it w/o bzero().
> 
> Humm, so basically this boils down to the following patch?
> 
> - Arnaldo
> 
> diff --git a/pahole.c b/pahole.c
> index 6fc4ed6a721b97ab..7f7aa0a5db05837d 100644
> --- a/pahole.c
> +++ b/pahole.c
> @@ -674,7 +674,12 @@ static void print_ordered_classes(void)
>  		__print_ordered_classes(&structures__tree);
>  	} else {
>  		struct rb_root resorted = RB_ROOT;
> -
> +#ifdef DEBUG_CHECK_LEAKS
> +		// We'll delete structures from structures__tree, since we're
> +		// adding them to ther resorted list, better not keep
> +		// references there.
> +		structures__tree = RB_ROOT;
> +#endif

But __structures__delete iterates over structures__tree,
so it won't delete anything if code like this, right?

>  		resort_classes(&resorted, &structures__list);
>  		__print_ordered_classes(&resorted);
>  	}

Re: [PATCH dwarves] pahole: avoid adding same struct structure to two rb trees

[Arnaldo Carvalho de Melo]

Em Fri, Jun 02, 2023 at 09:08:51PM +0300, Eduard Zingerman escreveu:
> On Fri, 2023-06-02 at 15:04 -0300, Arnaldo Carvalho de Melo wrote:
> > Em Fri, Jun 02, 2023 at 04:52:40PM +0300, Eduard Zingerman escreveu:
> > > Right, you are correct.
> > > The 'structures__tree = RB_ROOT' part is still necessary, though.
> > > If you are ok with overall structure of the patch I can resend it w/o bzero().

> > Humm, so basically this boils down to the following patch?

> > +++ b/pahole.c
> > @@ -674,7 +674,12 @@ static void print_ordered_classes(void)
> >  		__print_ordered_classes(&structures__tree);
> >  	} else {
> >  		struct rb_root resorted = RB_ROOT;
> > -
> > +#ifdef DEBUG_CHECK_LEAKS
> > +		// We'll delete structures from structures__tree, since we're
> > +		// adding them to ther resorted list, better not keep
> > +		// references there.
> > +		structures__tree = RB_ROOT;
> > +#endif
 
> But __structures__delete iterates over structures__tree,
> so it won't delete anything if code like this, right?
 
> >  		resort_classes(&resorted, &structures__list);
> >  		__print_ordered_classes(&resorted);
> >  	}

Yeah, I tried to be minimalistic, my version avoids the crash, but
defeats the DEBUG_CHECK_LEAKS purpose :-\

How about:

diff --git a/pahole.c b/pahole.c
index 6fc4ed6a721b97ab..e843999fde2a8a37 100644
--- a/pahole.c
+++ b/pahole.c
@@ -673,10 +673,10 @@ static void print_ordered_classes(void)
 	if (!need_resort) {
 		__print_ordered_classes(&structures__tree);
 	} else {
-		struct rb_root resorted = RB_ROOT;
+		structures__tree = RB_ROOT;
 
-		resort_classes(&resorted, &structures__list);
-		__print_ordered_classes(&resorted);
+		resort_classes(&structures__tree, &structures__list);
+		__print_ordered_classes(&structures__tree);
 	}
 }
 

Re: [PATCH dwarves] pahole: avoid adding same struct structure to two rb trees

[Eduard Zingerman]

On Mon, 2023-06-05 at 10:47 -0300, Arnaldo Carvalho de Melo wrote:
> Em Fri, Jun 02, 2023 at 09:08:51PM +0300, Eduard Zingerman escreveu:
> > On Fri, 2023-06-02 at 15:04 -0300, Arnaldo Carvalho de Melo wrote:
> > > Em Fri, Jun 02, 2023 at 04:52:40PM +0300, Eduard Zingerman escreveu:
> > > > Right, you are correct.
> > > > The 'structures__tree = RB_ROOT' part is still necessary, though.
> > > > If you are ok with overall structure of the patch I can resend it w/o bzero().
> 
> > > Humm, so basically this boils down to the following patch?
> 
> > > +++ b/pahole.c
> > > @@ -674,7 +674,12 @@ static void print_ordered_classes(void)
> > >  		__print_ordered_classes(&structures__tree);
> > >  	} else {
> > >  		struct rb_root resorted = RB_ROOT;
> > > -
> > > +#ifdef DEBUG_CHECK_LEAKS
> > > +		// We'll delete structures from structures__tree, since we're
> > > +		// adding them to ther resorted list, better not keep
> > > +		// references there.
> > > +		structures__tree = RB_ROOT;
> > > +#endif
>  
> > But __structures__delete iterates over structures__tree,
> > so it won't delete anything if code like this, right?
>  
> > >  		resort_classes(&resorted, &structures__list);
> > >  		__print_ordered_classes(&resorted);
> > >  	}
> 
> Yeah, I tried to be minimalistic, my version avoids the crash, but
> defeats the DEBUG_CHECK_LEAKS purpose :-\
> 
> How about:
> 
> diff --git a/pahole.c b/pahole.c
> index 6fc4ed6a721b97ab..e843999fde2a8a37 100644
> --- a/pahole.c
> +++ b/pahole.c
> @@ -673,10 +673,10 @@ static void print_ordered_classes(void)
>  	if (!need_resort) {
>  		__print_ordered_classes(&structures__tree);
>  	} else {
> -		struct rb_root resorted = RB_ROOT;
> +		structures__tree = RB_ROOT;
>  
> -		resort_classes(&resorted, &structures__list);
> -		__print_ordered_classes(&resorted);
> +		resort_classes(&structures__tree, &structures__list);
> +		__print_ordered_classes(&structures__tree);
>  	}
>  }
>  

That would work, but I still think that there is no need to replicate call
to __print_ordered_classes, as long as the same list is passed as an argument,
e.g.:

@@ -670,14 +671,11 @@ static void resort_classes(struct rb_root *resorted, struct list_head *head)
 
 static void print_ordered_classes(void)
 {
-       if (!need_resort) {
-               __print_ordered_classes(&structures__tree);
-       } else {
-               struct rb_root resorted = RB_ROOT;
-
-               resort_classes(&resorted, &structures__list);
-               __print_ordered_classes(&resorted);
+       if (need_resort) {
+               structures__tree = RB_ROOT;
+               resort_classes(&structures__tree, &structures__list);
        }
+       __print_ordered_classes(&structures__tree);
 }

Re: [PATCH dwarves] pahole: avoid adding same struct structure to two rb trees

[Arnaldo Carvalho de Melo]

Em Mon, Jun 05, 2023 at 05:39:19PM +0300, Eduard Zingerman escreveu:
> On Mon, 2023-06-05 at 10:47 -0300, Arnaldo Carvalho de Melo wrote:
> > Em Fri, Jun 02, 2023 at 09:08:51PM +0300, Eduard Zingerman escreveu:
> > > On Fri, 2023-06-02 at 15:04 -0300, Arnaldo Carvalho de Melo wrote:
> > > > Em Fri, Jun 02, 2023 at 04:52:40PM +0300, Eduard Zingerman escreveu:
> > > > > Right, you are correct.
> > > > > The 'structures__tree = RB_ROOT' part is still necessary, though.
> > > > > If you are ok with overall structure of the patch I can resend it w/o bzero().
> > 
> > > > Humm, so basically this boils down to the following patch?
> > 
> > > > +++ b/pahole.c
> > > > @@ -674,7 +674,12 @@ static void print_ordered_classes(void)
> > > >  		__print_ordered_classes(&structures__tree);
> > > >  	} else {
> > > >  		struct rb_root resorted = RB_ROOT;
> > > > -
> > > > +#ifdef DEBUG_CHECK_LEAKS
> > > > +		// We'll delete structures from structures__tree, since we're
> > > > +		// adding them to ther resorted list, better not keep
> > > > +		// references there.
> > > > +		structures__tree = RB_ROOT;
> > > > +#endif
> >  
> > > But __structures__delete iterates over structures__tree,
> > > so it won't delete anything if code like this, right?
> >  
> > > >  		resort_classes(&resorted, &structures__list);
> > > >  		__print_ordered_classes(&resorted);
> > > >  	}
> > 
> > Yeah, I tried to be minimalistic, my version avoids the crash, but
> > defeats the DEBUG_CHECK_LEAKS purpose :-\
> > 
> > How about:
> > 
> > diff --git a/pahole.c b/pahole.c
> > index 6fc4ed6a721b97ab..e843999fde2a8a37 100644
> > --- a/pahole.c
> > +++ b/pahole.c
> > @@ -673,10 +673,10 @@ static void print_ordered_classes(void)
> >  	if (!need_resort) {
> >  		__print_ordered_classes(&structures__tree);
> >  	} else {
> > -		struct rb_root resorted = RB_ROOT;
> > +		structures__tree = RB_ROOT;
> >  
> > -		resort_classes(&resorted, &structures__list);
> > -		__print_ordered_classes(&resorted);
> > +		resort_classes(&structures__tree, &structures__list);
> > +		__print_ordered_classes(&structures__tree);
> >  	}
> >  }
> >  
> 
> That would work, but I still think that there is no need to replicate call
> to __print_ordered_classes, as long as the same list is passed as an argument,
> e.g.:
> 
> @@ -670,14 +671,11 @@ static void resort_classes(struct rb_root *resorted, struct list_head *head)
>  
>  static void print_ordered_classes(void)
>  {
> -       if (!need_resort) {
> -               __print_ordered_classes(&structures__tree);
> -       } else {
> -               struct rb_root resorted = RB_ROOT;
> -
> -               resort_classes(&resorted, &structures__list);
> -               __print_ordered_classes(&resorted);
> +       if (need_resort) {
> +               structures__tree = RB_ROOT;
> +               resort_classes(&structures__tree, &structures__list);
>         }
> +       __print_ordered_classes(&structures__tree);
>  }

Right, that can be done as a follow up patch, further simplifying the
code.

I'm just trying to have each patch as small as possible.

- Arnaldo

Re: [PATCH dwarves] pahole: avoid adding same struct structure to two rb trees

[Arnaldo Carvalho de Melo]

Em Mon, Jun 05, 2023 at 03:54:30PM -0300, Arnaldo Carvalho de Melo escreveu:
> Em Mon, Jun 05, 2023 at 05:39:19PM +0300, Eduard Zingerman escreveu:
> > On Mon, 2023-06-05 at 10:47 -0300, Arnaldo Carvalho de Melo wrote:
> > > Em Fri, Jun 02, 2023 at 09:08:51PM +0300, Eduard Zingerman escreveu:
> > > > On Fri, 2023-06-02 at 15:04 -0300, Arnaldo Carvalho de Melo wrote:
> > > > > Em Fri, Jun 02, 2023 at 04:52:40PM +0300, Eduard Zingerman escreveu:
> > > > > > Right, you are correct.
> > > > > > The 'structures__tree = RB_ROOT' part is still necessary, though.
> > > > > > If you are ok with overall structure of the patch I can resend it w/o bzero().
> > > 
> > > > > Humm, so basically this boils down to the following patch?
> > > 
> > > > > +++ b/pahole.c
> > > > > @@ -674,7 +674,12 @@ static void print_ordered_classes(void)
> > > > >  		__print_ordered_classes(&structures__tree);
> > > > >  	} else {
> > > > >  		struct rb_root resorted = RB_ROOT;
> > > > > -
> > > > > +#ifdef DEBUG_CHECK_LEAKS
> > > > > +		// We'll delete structures from structures__tree, since we're
> > > > > +		// adding them to ther resorted list, better not keep
> > > > > +		// references there.
> > > > > +		structures__tree = RB_ROOT;
> > > > > +#endif
> > >  
> > > > But __structures__delete iterates over structures__tree,
> > > > so it won't delete anything if code like this, right?
> > >  
> > > > >  		resort_classes(&resorted, &structures__list);
> > > > >  		__print_ordered_classes(&resorted);
> > > > >  	}
> > > 
> > > Yeah, I tried to be minimalistic, my version avoids the crash, but
> > > defeats the DEBUG_CHECK_LEAKS purpose :-\
> > > 
> > > How about:
> > > 
> > > diff --git a/pahole.c b/pahole.c
> > > index 6fc4ed6a721b97ab..e843999fde2a8a37 100644
> > > --- a/pahole.c
> > > +++ b/pahole.c
> > > @@ -673,10 +673,10 @@ static void print_ordered_classes(void)
> > >  	if (!need_resort) {
> > >  		__print_ordered_classes(&structures__tree);
> > >  	} else {
> > > -		struct rb_root resorted = RB_ROOT;
> > > +		structures__tree = RB_ROOT;
> > >  
> > > -		resort_classes(&resorted, &structures__list);
> > > -		__print_ordered_classes(&resorted);
> > > +		resort_classes(&structures__tree, &structures__list);
> > > +		__print_ordered_classes(&structures__tree);
> > >  	}
> > >  }
> > >  
> > 
> > That would work, but I still think that there is no need to replicate call

I'm going thru the pile of stuff from before my vacations, can I take
the above as an Acked-by in addition to your Reported-by?

- Arnaldo

> > to __print_ordered_classes, as long as the same list is passed as an argument,
> > e.g.:
> > 
> > @@ -670,14 +671,11 @@ static void resort_classes(struct rb_root *resorted, struct list_head *head)
> >  
> >  static void print_ordered_classes(void)
> >  {
> > -       if (!need_resort) {
> > -               __print_ordered_classes(&structures__tree);
> > -       } else {
> > -               struct rb_root resorted = RB_ROOT;
> > -
> > -               resort_classes(&resorted, &structures__list);
> > -               __print_ordered_classes(&resorted);
> > +       if (need_resort) {
> > +               structures__tree = RB_ROOT;
> > +               resort_classes(&structures__tree, &structures__list);
> >         }
> > +       __print_ordered_classes(&structures__tree);
> >  }
> 
> Right, that can be done as a follow up patch, further simplifying the
> code.
> 
> I'm just trying to have each patch as small as possible.

Re: [PATCH dwarves] pahole: avoid adding same struct structure to two rb trees

[Eduard Zingerman]

On Mon, 2023-07-10 at 10:13 -0300, Arnaldo Carvalho de Melo wrote:
> Em Mon, Jun 05, 2023 at 03:54:30PM -0300, Arnaldo Carvalho de Melo escreveu:
> > Em Mon, Jun 05, 2023 at 05:39:19PM +0300, Eduard Zingerman escreveu:
> > > On Mon, 2023-06-05 at 10:47 -0300, Arnaldo Carvalho de Melo wrote:
> > > > Em Fri, Jun 02, 2023 at 09:08:51PM +0300, Eduard Zingerman escreveu:
> > > > > On Fri, 2023-06-02 at 15:04 -0300, Arnaldo Carvalho de Melo wrote:
> > > > > > Em Fri, Jun 02, 2023 at 04:52:40PM +0300, Eduard Zingerman escreveu:
> > > > > > > Right, you are correct.
> > > > > > > The 'structures__tree = RB_ROOT' part is still necessary, though.
> > > > > > > If you are ok with overall structure of the patch I can resend it w/o bzero().
> > > > 
> > > > > > Humm, so basically this boils down to the following patch?
> > > > 
> > > > > > +++ b/pahole.c
> > > > > > @@ -674,7 +674,12 @@ static void print_ordered_classes(void)
> > > > > >  		__print_ordered_classes(&structures__tree);
> > > > > >  	} else {
> > > > > >  		struct rb_root resorted = RB_ROOT;
> > > > > > -
> > > > > > +#ifdef DEBUG_CHECK_LEAKS
> > > > > > +		// We'll delete structures from structures__tree, since we're
> > > > > > +		// adding them to ther resorted list, better not keep
> > > > > > +		// references there.
> > > > > > +		structures__tree = RB_ROOT;
> > > > > > +#endif
> > > >  
> > > > > But __structures__delete iterates over structures__tree,
> > > > > so it won't delete anything if code like this, right?
> > > >  
> > > > > >  		resort_classes(&resorted, &structures__list);
> > > > > >  		__print_ordered_classes(&resorted);
> > > > > >  	}
> > > > 
> > > > Yeah, I tried to be minimalistic, my version avoids the crash, but
> > > > defeats the DEBUG_CHECK_LEAKS purpose :-\
> > > > 
> > > > How about:
> > > > 
> > > > diff --git a/pahole.c b/pahole.c
> > > > index 6fc4ed6a721b97ab..e843999fde2a8a37 100644
> > > > --- a/pahole.c
> > > > +++ b/pahole.c
> > > > @@ -673,10 +673,10 @@ static void print_ordered_classes(void)
> > > >  	if (!need_resort) {
> > > >  		__print_ordered_classes(&structures__tree);
> > > >  	} else {
> > > > -		struct rb_root resorted = RB_ROOT;
> > > > +		structures__tree = RB_ROOT;
> > > >  
> > > > -		resort_classes(&resorted, &structures__list);
> > > > -		__print_ordered_classes(&resorted);
> > > > +		resort_classes(&structures__tree, &structures__list);
> > > > +		__print_ordered_classes(&structures__tree);
> > > >  	}
> > > >  }
> > > >  
> > > 
> > > That would work, but I still think that there is no need to replicate call
> 
> I'm going thru the pile of stuff from before my vacations, can I take
> the above as an Acked-by in addition to your Reported-by?

Hi Arnaldo,

Sure, no problem.

> 
> - Arnaldo
> 
> > > to __print_ordered_classes, as long as the same list is passed as an argument,
> > > e.g.:
> > > 
> > > @@ -670,14 +671,11 @@ static void resort_classes(struct rb_root *resorted, struct list_head *head)
> > >  
> > >  static void print_ordered_classes(void)
> > >  {
> > > -       if (!need_resort) {
> > > -               __print_ordered_classes(&structures__tree);
> > > -       } else {
> > > -               struct rb_root resorted = RB_ROOT;
> > > -
> > > -               resort_classes(&resorted, &structures__list);
> > > -               __print_ordered_classes(&resorted);
> > > +       if (need_resort) {
> > > +               structures__tree = RB_ROOT;
> > > +               resort_classes(&structures__tree, &structures__list);
> > >         }
> > > +       __print_ordered_classes(&structures__tree);
> > >  }
> > 
> > Right, that can be done as a follow up patch, further simplifying the
> > code.
> > 
> > I'm just trying to have each patch as small as possible.