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

[Peter Zijlstra]

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}