Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups

From: Alexey Budankov
Date: Mon Aug 07 2017 - 03:18:00 EST


On 04.08.2017 17:36, Peter Zijlstra wrote:
> On Thu, Aug 03, 2017 at 11:30:09PM +0300, Alexey Budankov wrote:
>> On 03.08.2017 16:00, Peter Zijlstra wrote:
>>> On Wed, Aug 02, 2017 at 11:13:54AM +0300, Alexey Budankov wrote:
>
>>>> +/*
>>>> + * Find group list by a cpu key and rotate it.
>>>> + */
>>>> +static void
>>>> +perf_event_groups_rotate(struct rb_root *groups, int cpu)
>>>> +{
>>>> + struct rb_node *node;
>>>> + struct perf_event *node_event;
>>>> +
>>>> + node = groups->rb_node;
>>>> +
>>>> + while (node) {
>>>> + node_event = container_of(node,
>>>> + struct perf_event, group_node);
>>>> +
>>>> + if (cpu < node_event->cpu) {
>>>> + node = node->rb_left;
>>>> + } else if (cpu > node_event->cpu) {
>>>> + node = node->rb_right;
>>>> + } else {
>>>> + list_rotate_left(&node_event->group_list);
>>>> + break;
>>>> + }
>>>> + }
>>>> +}
>>>
>>> Ah, you worry about how to rotate inside a tree?
>>
>> Exactly.
>>
>>>
>>> You can do that by adding (run)time based ordering, and you'll end up
>>> with a runtime based scheduler.
>>
>> Do you mean replacing a CPU indexed rb_tree of lists with
>> an CPU indexed rb_tree of counter indexed rb_trees?
>
> No, single tree, just more complicated ordering rules.
>
>>> A trivial variant keeps a simple counter per tree that is incremented
>>> for each rotation. That should end up with the events ordered exactly
>>> like the list. And if you have that comparator like above, expressing
>>> that additional ordering becomes simple ;-)
>>>
>>> Something like:
>>>
>>> struct group {
>>> u64 vtime;
>>> rb_tree tree;
>>> };
>>>
>>> bool event_less(left, right)
>>> {
>>> if (left->cpu < right->cpu)
>>> return true;
>>>
>>> if (left->cpu > right_cpu)
>>> return false;
>>>
>>> if (left->vtime < right->vtime)
>>> return true;
>>>
>>> return false;
>>> }
>>>
>>> insert_group(group, event, tail)
>>> {
>>> if (tail)
>>> event->vtime = ++group->vtime;
>>>
>>> tree_insert(&group->root, event);
>>> }
>>>
>>> Then every time you use insert_group(.tail=1) it goes to the end of that
>>> CPU's 'list'.
>>>
>>
>> Could you elaborate more on how to implement rotation?
>
> Its almost all there, but let me write a complete replacement for your
> perf_event_group_rotate() above.
>
> /* find the leftmost event matching @cpu */
> /* XXX not sure how to best parametrise a subtree search, */
> /* again, C sucks... */
> struct perf_event *__group_find_cpu(group, cpu)
> {
> struct rb_node *node = group->tree.rb_node;
> struct perf_event *event, *match = NULL;
>
> while (node) {
> event = container_of(node, struct perf_event, group_node);
>
> if (cpu > event->cpu) {
> node = node->rb_right;
> } else if (cpu < event->cpu) {
> node = node->rb_left;
> } else {
> /*
> * subtree match, try left subtree for a
> * 'smaller' match.
> */
> match = event;
> node = node->rb_left;
> }
> }
>
> return match;
> }
>
> void perf_event_group_rotate(group, int cpu)
> {
> struct perf_event *event = __group_find_cpu(cpu);
>
> if (!event)
> return;
>
> tree_delete(&group->tree, event);
> insert_group(group, event, 1);
> }
>
> So we have a tree ordered by {cpu,vtime} and what we do is find the
> leftmost {cpu} entry, that is the smallest vtime entry for that cpu. We
> then take it out and re-insert it with a vtime number larger than any
> other, which places it as the rightmost entry for that cpu.
>
>
> So given:
>
> {1,1}
> / \
> {0,5} {1,2}
> / \ \
> {0,1} {0,6} {1,4}
>
>
> __group_find_cpu(.cpu=1) will return {1,1} as being the leftmost entry
> with cpu=1. We'll then remove it, update its vtime to 7 and re-insert.
> resulting in something like:
>
> {1,2}
> / \
> {0,5} {1,4}
> / \ \
> {0,1} {0,6} {1,7}
>

Makes sense. The implementation becomes a bit simpler. The drawbacks
may be several rotations of potentially big tree on the critical path,
instead of updating four pointers in case of the tree of lists.

>
>
>
>