linux-kernel - Re: [PATCH 1/4] sched/fair: Introduce primitives for CFS bandwidth burst

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]

Date:   Tue, 12 Jan 2021 17:21:08 +0800
From:   changhuaixin <changhuaixin@...ux.alibaba.com>
To:     Peter Zijlstra <peterz@...radead.org>
Cc:     changhuaixin <changhuaixin@...ux.alibaba.com>,
        linux-kernel@...r.kernel.org, bsegall@...gle.com,
        dietmar.eggemann@....com, juri.lelli@...hat.com, mgorman@...e.de,
        mingo@...hat.com, pauld@...head.com, pjt@...gle.com,
        rostedt@...dmis.org, vincent.guittot@...aro.org,
        khlebnikov@...dex-team.ru, xiyou.wangcong@...il.com,
        shanpeic@...ux.alibaba.com
Subject: Re: [PATCH 1/4] sched/fair: Introduce primitives for CFS bandwidth
 burst



> On Dec 21, 2020, at 9:53 PM, changhuaixin <changhuaixin@...ux.alibaba.com> wrote:
> 
> 
> 
>> On Dec 17, 2020, at 9:36 PM, Peter Zijlstra <peterz@...radead.org> wrote:
>> 
>> On Thu, Dec 17, 2020 at 03:46:17PM +0800, Huaixin Chang wrote:
>>> In this patch, we introduce the notion of CFS bandwidth burst. Unused
>>> "quota" from pervious "periods" might be accumulated and used in the
>>> following "periods". The maximum amount of accumulated bandwidth is
>>> bounded by "burst". And the maximun amount of CPU a group can consume in
>>> a given period is "buffer" which is equivalent to "quota" + "burst in
>>> case that this group has done enough accumulation.
>> 
>> Oh man, Juri, wasn't there a paper about statistical bandwidth
>> accounting somewhere? Where, if you replace every utilization by a
>> statistical variable, the end result is still useful?
>> 
>> That is, instead of something like; \Sum u_i <= 1, you get something
>> like: \Sum {avg(u),var(u)}_i <= {1, sqrt(\Sum var_i^2)} and you can
>> still proof bounded tardiness etc.. (assuming a gaussian distribution).
>> 
>> The proposed seems close to that, but not quite, and I'm afraid it's not
>> quite strong enough to still provide any guarantees.
> 
> After reading some papers on statistical bandwidth sharing, it occurs to me that statistical bandwidth sharing is about the way bandwidth is shared between competitors. I wonder if the paper you mentioned was "Insensitivity results in statistical bandwidth sharing" or some paper referenced, which showed the end result is insensitive to maybe the distribution or the arrival pattern.
> 
> I am sorry that I cannot prove using statistical bandwidth sharing theory now. However, I wonder if it is more acceptable to put rate-based cfsb after share fairness, because the input stream of cfsb account is the output stream of fairness. And that is in contrast with what statistical bandwidth sharing does, in which fairness is used to share bandwidth upon the output stream of rate-based control. In this way, maybe guarantees can be provided by share fairness, and cfsb may use a larger buffer to allow more jitters.
> 
> A buffer, which is several times of quota, is able to handle large bursts, and throttle threads soon when overloaded. The present cfsb, however, has to be configured several times larger to handle jitters, which is ineffective and does not provide the designed rate-based control.

Hi, peter.

Will you please have a look at my earlier reply.

The guarantee provided by cfsb is max-min fairness with strict upper bound, I think. And after this modification, it is still roughly that. As for longer periods, each cfsb group is still limited to their quota on average.

When users configure a huge burst buffer, cfsb doesn't really throttle threads and upper bound is exceeded. In that case, guarantees are provided by share, which provides proportional fairness.

Thanks,
Huaixin