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

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: <20170807091326.5e3iec54ninmeyex@hirez.programming.kicks-ass.net>
Date:   Mon, 7 Aug 2017 11:13:26 +0200
From:   Peter Zijlstra <peterz@...radead.org>
To:     Alexey Budankov <alexey.budankov@...ux.intel.com>
Cc:     Ingo Molnar <mingo@...hat.com>,
        Arnaldo Carvalho de Melo <acme@...nel.org>,
        Alexander Shishkin <alexander.shishkin@...ux.intel.com>,
        Andi Kleen <ak@...ux.intel.com>,
        Kan Liang <kan.liang@...el.com>,
        Dmitri Prokhorov <Dmitry.Prohorov@...el.com>,
        Valery Cherepennikov <valery.cherepennikov@...el.com>,
        Mark Rutland <mark.rutland@....com>,
        Stephane Eranian <eranian@...gle.com>,
        David Carrillo-Cisneros <davidcc@...gle.com>,
        linux-kernel <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups

On Mon, Aug 07, 2017 at 10:39:13AM +0200, Peter Zijlstra wrote:
> On Mon, Aug 07, 2017 at 10:17:46AM +0300, Alexey Budankov wrote:
> > 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.
> 
> Yes, but like said, it allows implementing a better scheduler than RR,
> allowing us to fix rotation artifacts where task runtimes are near the
> rotation window.
> 
> A slightly more complicated, but also interested scheduling problem is
> the per-cpu flexible vs the per-task flexible. Ideally we'd rotate them
> at the same priority based on service, without strictly prioritizing the
> per-cpu events.
> 
> Again, that is something that should be possible once we have a more
> capable event scheduler.
> 
> 
> So yes, cons and pros.. :-)

Also, I think for AVL tree you could do the erase and (re)insert
combined and then rebalance in one go, not sure RB allows the same
thing, but it might be fun looking into.