Date:   Tue, 3 Jan 2017 16:39:16 -0800
From:   David Carrillo-Cisneros <davidcc@...gle.com>
To:     Mark Rutland <mark.rutland@....com>
Cc:     Peter Zijlstra <peterz@...radead.org>,
        Ingo Molnar <mingo@...hat.com>,
        linux-kernel <linux-kernel@...r.kernel.org>,
        Arnaldo Carvalho de Melo <acme@...nel.org>,
        Thomas Gleixner <tglx@...utronix.de>,
        Alexander Shishkin <alexander.shishkin@...ux.intel.com>,
        vince@...ter.net, Stephane Eranian <eranian@...gle.com>,
        Andi Kleen <andi@...stfloor.org>,
        Kan Liang <kan.liang@...el.com>,
        Vikas Shivappa <vikas.shivappa@...ux.intel.com>
Subject: Re: [PATCH] perf/core: introduce context per CPU event list

On Tue, Jan 3, 2017 at 4:00 AM, Mark Rutland <mark.rutland@....com> wrote:
> On Sun, Jan 01, 2017 at 01:18:27PM -0800, David Carrillo-Cisneros wrote:
>> On Sun, Jan 1, 2017 at 12:20 PM, David Carrillo-Cisneros
>> <davidcc@...gle.com> wrote:
>> > From: Mark Rutland <mark.rutland@....com>
>> >
>> > On Thu, Nov 10, 2016 at 05:26:32PM +0100, Peter Zijlstra wrote:
>> >> On Thu, Nov 10, 2016 at 02:10:37PM +0000, Mark Rutland wrote:
>> >>
>> >> > Sure, that sounds fine for scheduling (including big.LITTLE).
>> >> >
>> >> > I might still be misunderstanding something, but I don't think that
>> >> > helps Kan's case: since INACTIVE events which will fail their filters
>> >> > (including the CPU check) will still be in the tree, they will still
>> >> > have to be iterated over.
>> >> >
>> >> > That is, unless we also sort the tree by event->cpu, or if in those
>> >> > cases we only care about ACTIVE events and can use an active list.
>> >>
>> >> A few emails back up I wrote:
>> >>
>> >> >> If we stick all events in an RB-tree sorted on: {pmu,cpu,runtime} we
>> >
>> > Ah, sorry. Clearly I wouldn't pass a reading comprehension test today.
>> >
>> >> Looking at the code there's also cgroup muck, not entirely sure where in
>> >> the sort order that should go if at all.
>> >>
>> >> But having pmu and cpu in there would cure the big-little and
>> >> per-task-per-cpu event issues.
>> >
>> > Yup, that all makes sense to me now (modulo the cgroup stuff I also
>> > haven't considered yet).
>>
>> cgroup events are stored in each pmu's cpuctx, so they wouldn't benefit
>> from a pmu,cpu sort order. Yet the RB-tree would help if it could use cgroup
>> as key for cpu contexts.
>>
>> Is there a reason to have runtime as part of the RB-tree?
>
> Fairer scheduling of the events, especially where cross-group conflicts
> for PMU resources are non-trivial to solve. IIRC this is the major
> reason Peter wanted the RB tree in the first place.

I see, so we want to be able to reinsert conflicting groups
efficiently. It makes
sense.

>
>> Couldn't a FIFO list work just fine? A node could have an ACTIVE and
>> an INACTIVE FIFO list and just move the events in out the tree in ioctl and
>> to/from ACTIVE from/to INACTIVE on sched in/out.
>> This would speed up both sched in and sched out.
>>
>> The node would be something like this:
>>
>> struct ctx_rbnode {
>>         struct rb_node node;
>>         struct list_head active_events;
>>         struct list_head inactive_events;
>> };
>>
>> And the insertion order would be {pmu, cpu} for task contexts (cpu == -1
>> for events without fixed cpu) and {cgroup} for cpuctxs (CPU events would
>> have NULL cgrp).
>
> The problem with using a list rather than a tree is that we have to
> perform a linear walk of the list every time we want to find the
> relevant sub-list (e.g. scheduling, insertion). Using a tree makes
> finding the relevant portion much cheaper.

Then we could extend the per data that each pmu allocates in perf_pmu_register
to something like:

struct pmu_percpu_data {
        struct perf_cpu_context;         /* what it currently allocates */
        struct list_head active_events_list;
        struct rb_root inactive_events_rbtree;
};

The events in the inactive rbtree can be sorted by the time they've been waiting
to be scheduled.

The closer I can find to a per PMU list of active events are the intel
lists existing
in RAPL and uncore pmus. They use perf_event::active_entry. This could be
moved to generic code and maintain active_event_list for all {pmus,cpus}.

>
>> Am I interested on getting this to work as part of the cgroup context switch
>> optimization that CQM/CMT needs. See discussion in:
>>
>> https://patchwork.kernel.org/patch/9478617/
>>
>> Is anyone actively working on it?
>
> Unfortunately I have too much on my plate at the moment; I'm not
> actively working on this.
>
> I'm happy to review and test patches, though!

I'll be happy to give this a try then!

Thanks,
David
>
> Thanks,
> Mark.

Powered by blists - more mailing lists