linux-kernel - Re: [PATCH 14/37] perf tools: Convert dead thread list into rbtree

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAM9d7chmWVo0yhwpxhyKo+7k9SMP3tag1f1iq0Mt9oehUJjXEg@mail.gmail.com>
Date:	Sun, 28 Dec 2014 22:24:43 +0900
From:	Namhyung Kim <namhyung@...nel.org>
To:	David Ahern <dsahern@...il.com>
Cc:	Arnaldo Carvalho de Melo <acme@...nel.org>,
	Ingo Molnar <mingo@...nel.org>,
	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	Jiri Olsa <jolsa@...hat.com>,
	LKML <linux-kernel@...r.kernel.org>,
	Stephane Eranian <eranian@...gle.com>,
	Adrian Hunter <adrian.hunter@...el.com>,
	Andi Kleen <andi@...stfloor.org>,
	Frederic Weisbecker <fweisbec@...il.com>
Subject: Re: [PATCH 14/37] perf tools: Convert dead thread list into rbtree

Hi David,

On Sun, Dec 28, 2014 at 12:31 AM, David Ahern <dsahern@...il.com> wrote:
> On 12/24/14 12:15 AM, Namhyung Kim wrote:
>>
>> @@ -106,8 +117,8 @@ void machine__delete_threads(struct machine *machine)
>>         while (nd) {
>>                 struct thread *t = rb_entry(nd, struct thread, rb_node);
>>
>> -               rb_erase(&t->rb_node, &machine->threads);
>>                 nd = rb_next(nd);
>> +               rb_erase(&t->rb_node, &machine->threads);
>>                 thread__delete(t);
>>         }
>>   }
>
>
> unrelated to dead threads. Bug fix? separate patch?

Yes, I'll make it a separate bug-fix patch.


>
>
>> @@ -1236,13 +1247,36 @@ int machine__process_mmap_event(struct machine
>> *machine, union perf_event *event
>>
>>   static void machine__remove_thread(struct machine *machine, struct
>> thread *th)
>>   {
>> +       struct rb_node **p = &machine->dead_threads.rb_node;
>> +       struct rb_node *parent = NULL;
>> +       struct thread *pos;
>> +
>>         machine->last_match = NULL;
>>         rb_erase(&th->rb_node, &machine->threads);
>> +
>> +       th->dead = true;
>> +
>>         /*
>>          * We may have references to this thread, for instance in some
>> hist_entry
>> -        * instances, so just move them to a separate list.
>> +        * instances, so just move them to a separate list in rbtree.
>>          */
>> -       list_add_tail(&th->node, &machine->dead_threads);
>> +       while (*p != NULL) {
>> +               parent = *p;
>> +               pos = rb_entry(parent, struct thread, rb_node);
>> +
>> +               if (pos->tid == th->tid) {
>> +                       list_add_tail(&th->node, &pos->node);
>> +                       return;
>> +               }
>
>
> So you have a linked list for tid collisions (not mentioned in the git log).

Right, will add a description.


>
>> +
>> +               if (th->tid < pos->tid)
>> +                       p = &(*p)->rb_left;
>> +               else
>> +                       p = &(*p)->rb_right;
>> +       }
>> +
>> +       rb_link_node(&th->rb_node, parent, p);
>> +       rb_insert_color(&th->rb_node, &machine->dead_threads);
>>   }
>>
>>   int machine__process_fork_event(struct machine *machine, union
>> perf_event *event,
>> @@ -1649,7 +1683,7 @@ int machine__for_each_thread(struct machine
>> *machine,
>
>
> ---8<---
>
>> diff --git a/tools/perf/util/thread.h b/tools/perf/util/thread.h
>> index 0b6dcd70bc8b..413f28cf689b 100644
>> --- a/tools/perf/util/thread.h
>> +++ b/tools/perf/util/thread.h
>> @@ -11,10 +11,8 @@
>>   struct thread_stack;
>>
>>   struct thread {
>> -       union {
>> -               struct rb_node   rb_node;
>> -               struct list_head node;
>> -       };
>> +       struct rb_node          rb_node;
>> +       struct list_head        node;
>>         struct map_groups       *mg;
>>         pid_t                   pid_; /* Not all tools update this */
>>         pid_t                   tid;
>
>
> could use better names for rb_node and node. rb_node is the entry in the
> dead_threads tree - dead_node?; node is the linked list for tid collisions -
> tid_node?

But the rb_node is used for 3 different purpose depends on its state -
a thread can be in a (normal) threads tree, dead threads tree or
missing threads tree (will be introduced later).

Thanks,
Namhyung
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/