Skip to contentSkip to conversation

pahole: avoid adding same struct structure to two rb trees

PATCH In review Eduard Zingerman 2 participants 10 messages May 26, 2023 – Jul 10, 2023 BPF

lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

PATCH 1/1 pahole: avoid adding same struct structure to two rb trees

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.

---
 pahole.c | 41 ++++++++++++++++++++++++++++-------------
 1 file changed, 28 insertions(+), 13 deletions(-)
pahole.c +28 -13
index 6fc4ed6..576733f 100644
@@ -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();
 }
 
 
Signature · 1 line
2.40.1
#1 lore raw

Em Fri, May 26, 2023 at 02:59:49AM +0300, Eduard Zingerman escreveu:

Quoted 90 lines

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.

---
 pahole.c | 41 ++++++++++++++++++++++++++++-------------
 1 file changed, 28 insertions(+), 13 deletions(-)
pahole.c +11 -5
index 6fc4ed6..576733f 100644
@@ -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()

pahole.c static void resort_add(struct rb_root *resorted, struct structure *str) · line 684

Quoted 10 lines
pahole.c +10 -0
+	 *         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?

pahole.c static void resort_add(struct rb_root *resorted, struct structure *str) · line 685

Quoted 1 line
pahole.c +1 -0
+		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

Quoted 24 lines
pahole.c +6 -8
+	}
+
+	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();
 }
 
 
Signature · 1 line
2.40.1
Signature · 1 line
- Arnaldo
author maintainer
#2 lore raw
Quoted 129 lines · Arnaldo Carvalho de Melo

Em Fri, May 26, 2023 at 02:59:49AM +0300, Eduard Zingerman escreveu:

Quoted 90 lines

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.

---
 pahole.c | 41 ++++++++++++++++++++++++++++-------------
 1 file changed, 28 insertions(+), 13 deletions(-)
pahole.c +11 -5
index 6fc4ed6..576733f 100644
@@ -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()

pahole.c static void resort_add(struct rb_root *resorted, struct structure *str) · line 684

Quoted 10 lines
pahole.c +10 -0
+	 *         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?

pahole.c static void resort_add(struct rb_root *resorted, struct structure *str) · line 685

Quoted 1 line
pahole.c +1 -0
+		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))))
Quoted 2 lines

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().

Quoted 28 lines

- Arnaldo

Quoted 24 lines
pahole.c +6 -8
+	}
+
+	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();
 }
 
 
Signature · 1 line
2.40.1
#3 lore raw

Em Fri, Jun 02, 2023 at 04:52:40PM +0300, Eduard Zingerman escreveu:

Quoted 130 lines · Arnaldo Carvalho de Melo
Quoted 129 lines

Em Fri, May 26, 2023 at 02:59:49AM +0300, Eduard Zingerman escreveu:

Quoted 90 lines

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.

---
 pahole.c | 41 ++++++++++++++++++++++++++++-------------
 1 file changed, 28 insertions(+), 13 deletions(-)
pahole.c +11 -5
index 6fc4ed6..576733f 100644
@@ -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()

pahole.c static void resort_add(struct rb_root *resorted, struct structure *str) · line 684

Quoted 10 lines
pahole.c +10 -0
+	 *         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?

pahole.c static void resort_add(struct rb_root *resorted, struct structure *str) · line 685

Quoted 1 line
pahole.c +1 -0
+		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))))
Quoted 6 lines
Quoted 2 lines

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

pahole.c +6 -1
index 6fc4ed6a721b97ab..7f7aa0a5db05837d 100644
@@ -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);
 	}
author maintainer
#4 lore raw
Quoted 147 lines · Arnaldo Carvalho de Melo

Em Fri, Jun 02, 2023 at 04:52:40PM +0300, Eduard Zingerman escreveu:

Quoted 130 lines · Arnaldo Carvalho de Melo
Quoted 129 lines

Em Fri, May 26, 2023 at 02:59:49AM +0300, Eduard Zingerman escreveu:

Quoted 90 lines

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.

---
 pahole.c | 41 ++++++++++++++++++++++++++++-------------
 1 file changed, 28 insertions(+), 13 deletions(-)
pahole.c +11 -5
index 6fc4ed6..576733f 100644
@@ -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()

pahole.c static void resort_add(struct rb_root *resorted, struct structure *str) · line 684

Quoted 10 lines
pahole.c +10 -0
+	 *         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?

pahole.c static void resort_add(struct rb_root *resorted, struct structure *str) · line 685

Quoted 1 line
pahole.c +1 -0
+		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))))
Quoted 6 lines
Quoted 2 lines

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

pahole.c +0 -0
index 6fc4ed6a721b97ab..7f7aa0a5db05837d 100644

pahole.c static void print_ordered_classes(void) · line 682

Quoted 10 lines
pahole.c +6 -1
@@ -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?

Quoted 3 lines
pahole.c +0 -0
 		resort_classes(&resorted, &structures__list);
 		__print_ordered_classes(&resorted);
 	}
#5 lore raw

Em Fri, Jun 02, 2023 at 09:08:51PM +0300, Eduard Zingerman escreveu:

Quoted 8 lines · Arnaldo Carvalho de Melo
Quoted 6 lines

Em Fri, Jun 02, 2023 at 04:52:40PM +0300, Eduard Zingerman escreveu:

Quoted 3 lines

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?

Quoted 19 lines

Review static void print_ordered_classes(void) · line 682

Quoted 12 lines

+++ b/pahole.c

(quoted diff) +6 -1
@@ -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?

Quoted 3 lines
(quoted diff) +0 -0
 		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:

pahole.c +3 -3
index 6fc4ed6a721b97ab..e843999fde2a8a37 100644
@@ -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);
 	}
 }
 
author maintainer
#6 lore raw
Quoted 42 lines · Arnaldo Carvalho de Melo

Em Fri, Jun 02, 2023 at 09:08:51PM +0300, Eduard Zingerman escreveu:

Quoted 8 lines · Arnaldo Carvalho de Melo
Quoted 6 lines

Em Fri, Jun 02, 2023 at 04:52:40PM +0300, Eduard Zingerman escreveu:

Quoted 3 lines

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?

Quoted 19 lines

Review static void print_ordered_classes(void) · line 682

Quoted 12 lines

+++ b/pahole.c

(quoted diff) +6 -1
@@ -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?

Quoted 3 lines
(quoted diff) +0 -0
 		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:

pahole.c +0 -0
index 6fc4ed6a721b97ab..e843999fde2a8a37 100644
@@ -673,10 +673,10 @@ static void print_ordered_classes(void)
 	if (!need_resort) {
 		__print_ordered_classes(&structures__tree);
 	} else {

pahole.c static void print_ordered_classes(void) · line 682

Quoted 10 lines
pahole.c +3 -3
-		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);
}

#7 lore raw

Em Mon, Jun 05, 2023 at 05:39:19PM +0300, Eduard Zingerman escreveu:

Quoted 65 lines · Arnaldo Carvalho de Melo
Quoted 42 lines

Em Fri, Jun 02, 2023 at 09:08:51PM +0300, Eduard Zingerman escreveu:

Quoted 8 lines · Arnaldo Carvalho de Melo
Quoted 6 lines

Em Fri, Jun 02, 2023 at 04:52:40PM +0300, Eduard Zingerman escreveu:

Quoted 3 lines

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?

Quoted 19 lines

Review static void print_ordered_classes(void) · line 682

Quoted 12 lines

+++ b/pahole.c

(quoted diff) +6 -1
@@ -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?

Quoted 3 lines
(quoted diff) +0 -0
 		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:

pahole.c +0 -0
index 6fc4ed6a721b97ab..e843999fde2a8a37 100644
@@ -673,10 +673,10 @@ static void print_ordered_classes(void)
 	if (!need_resort) {
 		__print_ordered_classes(&structures__tree);
 	} else {

pahole.c static void print_ordered_classes(void) · line 682

Quoted 10 lines
pahole.c +3 -3
-		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.:

(quoted diff) +0 -3
@@ -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 {

Review static void resort_classes(struct rb_root *resorted, struct list_head *head) · line 679

Quoted 10 lines
(quoted diff) +4 -4
-               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

#8 lore raw

Em Mon, Jun 05, 2023 at 03:54:30PM -0300, Arnaldo Carvalho de Melo escreveu:

Quoted 56 lines

Em Mon, Jun 05, 2023 at 05:39:19PM +0300, Eduard Zingerman escreveu:

Quoted 55 lines · Arnaldo Carvalho de Melo
Quoted 42 lines

Em Fri, Jun 02, 2023 at 09:08:51PM +0300, Eduard Zingerman escreveu:

Quoted 8 lines · Arnaldo Carvalho de Melo
Quoted 6 lines

Em Fri, Jun 02, 2023 at 04:52:40PM +0300, Eduard Zingerman escreveu:

Quoted 3 lines

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?

Quoted 19 lines

Review static void print_ordered_classes(void) · line 682

Quoted 12 lines

+++ b/pahole.c

(quoted diff) +6 -1
@@ -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?

Quoted 3 lines
(quoted diff) +0 -0
 		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:

pahole.c +0 -0
index 6fc4ed6a721b97ab..e843999fde2a8a37 100644
@@ -673,10 +673,10 @@ static void print_ordered_classes(void)
 	if (!need_resort) {
 		__print_ordered_classes(&structures__tree);
 	} else {

pahole.c static void print_ordered_classes(void) · line 682

Quoted 10 lines
pahole.c +3 -3
-		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

Quoted 25 lines
Quoted 10 lines

to __print_ordered_classes, as long as the same list is passed as an argument, e.g.:

(quoted diff) +0 -3
@@ -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 {

Review static void resort_classes(struct rb_root *resorted, struct list_head *head) · line 679

Quoted 10 lines
(quoted diff) +4 -4
-               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.

author maintainer
#9 lore raw
Quoted 58 lines · Arnaldo Carvalho de Melo

Em Mon, Jun 05, 2023 at 03:54:30PM -0300, Arnaldo Carvalho de Melo escreveu:

Quoted 56 lines

Em Mon, Jun 05, 2023 at 05:39:19PM +0300, Eduard Zingerman escreveu:

Quoted 55 lines · Arnaldo Carvalho de Melo
Quoted 42 lines

Em Fri, Jun 02, 2023 at 09:08:51PM +0300, Eduard Zingerman escreveu:

Quoted 8 lines · Arnaldo Carvalho de Melo
Quoted 6 lines

Em Fri, Jun 02, 2023 at 04:52:40PM +0300, Eduard Zingerman escreveu:

Quoted 3 lines

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?

Quoted 19 lines

Review static void print_ordered_classes(void) · line 682

Quoted 12 lines

+++ b/pahole.c

(quoted diff) +6 -1
@@ -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?

Quoted 3 lines
(quoted diff) +0 -0
 		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:

pahole.c +0 -0
index 6fc4ed6a721b97ab..e843999fde2a8a37 100644
@@ -673,10 +673,10 @@ static void print_ordered_classes(void)
 	if (!need_resort) {
 		__print_ordered_classes(&structures__tree);
 	} else {

pahole.c static void print_ordered_classes(void) · line 682

Quoted 10 lines
pahole.c +3 -3
-		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

Quoted 2 lines

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.

Quoted 28 lines

- Arnaldo

Quoted 25 lines
Quoted 10 lines

to __print_ordered_classes, as long as the same list is passed as an argument, e.g.:

(quoted diff) +0 -3
@@ -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 {

Review static void resort_classes(struct rb_root *resorted, struct list_head *head) · line 679

Quoted 10 lines
(quoted diff) +4 -4
-               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.