Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
MIME-Version: 1.0
References: <20210429152656.4118460-1-qperret@google.com> <CAKfTPtAfgVnMYkY_M+SDmNQDb_EsxSctQw-fkt2WJhczZakOjQ@mail.gmail.com>
 <YIu/EjZ8QsEl9sum@google.com>
In-Reply-To: <YIu/EjZ8QsEl9sum@google.com>
From:   Vincent Guittot <vincent.guittot@linaro.org>
Date:   Fri, 30 Apr 2021 10:49:50 +0200
Message-ID: <CAKfTPtDOuB0UzZM5OtNzCUABftz_A40Z4W1z9OAORzFitfPDEQ@mail.gmail.com>
Subject: Re: [PATCH v2] sched: Fix out-of-bound access in uclamp
To:     Quentin Perret <qperret@google.com>
Cc:     Ingo Molnar <mingo@redhat.com>,
        Peter Zijlstra <peterz@infradead.org>,
        Juri Lelli <juri.lelli@redhat.com>,
        Dietmar Eggemann <dietmar.eggemann@arm.com>,
        Steven Rostedt <rostedt@goodmis.org>,
        Ben Segall <bsegall@google.com>, Mel Gorman <mgorman@suse.de>,
        Daniel Bristot de Oliveira <bristot@redhat.com>,
        Qais Yousef <qais.yousef@arm.com>,
        Android Kernel Team <kernel-team@android.com>,
        linux-kernel <linux-kernel@vger.kernel.org>,
        Patrick Bellasi <patrick.bellasi@matbug.net>
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

On Fri, 30 Apr 2021 at 10:25, Quentin Perret <qperret@google.com> wrote:
>
> On Friday 30 Apr 2021 at 09:45:32 (+0200), Vincent Guittot wrote:
> > On Thu, 29 Apr 2021 at 17:27, Quentin Perret <qperret@google.com> wrote:
> > >
> > > Util-clamp places tasks in different buckets based on their clamp values
> > > for performance reasons. However, the size of buckets is currently
> > > computed using a rounding division, which can lead to an off-by-one
> > > error in some configurations.
> > >
> > > For instance, with 20 buckets, the bucket size will be 1024/20=51. A
> > > task with a clamp of 1024 will be mapped to bucket id 1024/51=20. Sadly,
> > > correct indexes are in range [0,19], hence leading to an out of bound
> > > memory access.
> > >
> > > Fix the math to compute the bucket size.
> > >
> > > Fixes: 69842cba9ace ("sched/uclamp: Add CPU's clamp buckets refcounting")
> > > Suggested-by: Qais Yousef <qais.yousef@arm.com>
> > > Signed-off-by: Quentin Perret <qperret@google.com>
> > >
> > > ---
> > >
> > > Changes in v2:
> > >  - replaced the DIV_ROUND_UP(a,b) with a/b+1 (Dietmar)
> >
> > Doesn't this create unfairness between buckets ?
> >
> > If we take your example above of 20 buckets, delta is now 52. Then we
> > expect the last bucket to get the range [972-1024] but values lower
> > than 988 will go in the idx 18.
>
> Well, that's just the limitation of integer arithmetics isn't it?
>
> > And the more bucket you will have, the
> > worse it will be
>
> Sure, but 20 is a hard limit, and if we ever need more than that then
> maybe we should think about getting rid of the buckets altogether.
>
> > Your problem comes from the fact that we use 1025 values instead of
> > 1024.
>
> I don't understand what you mean here. Right now we'll assign bucket id
> 20 for any clamp in the range [1020-1024], so I don't think we can
> special case 1024.

20 buckets is probably not the best example because of the rounding of
the division. With 16 buckets, each bucket should be exactly 64 steps
large except the last one which will have 65 steps because of the
value 1024. With your change, buckets will be 65 large and the last
one will be only 49 large

>
> > Wouldn't it be easier to have a special condition for
> > SCHED_CAPACITY_SCALE value
>
> As per the above, I don't see how that'll work.
>
> Thanks,
> Quentin