From: Peter Zijlstra <peterz@infradead.org>
To: Stanislaw Gruszka <sgruszka@redhat.com>
Cc: linux-kernel@vger.kernel.org, mingo@kernel.org, hpa@zytor.com,
fweisbec@gmail.com, rostedt@goodmis.org,
akpm@linux-foundation.org, tglx@linutronix.de,
linux-tip-commits@vger.kernel.org,
Linus Torvalds <torvalds@linux-foundation.org>
Subject: Re: [tip:sched/core] sched: Lower chances of cputime scaling overflow
Date: Thu, 11 Apr 2013 19:31:09 +0200 [thread overview]
Message-ID: <1365701469.10217.6.camel@laptop> (raw)
In-Reply-To: <20130411145052.GA31644@redhat.com>
On Thu, 2013-04-11 at 16:50 +0200, Stanislaw Gruszka wrote:
> > + /*
> > + * Since the stime:utime ratio is already an approximation through
> > + * the sampling, reducing its resolution isn't too big a deal.
> > + * And since total = stime+utime; the total_fls will be the biggest
> > + * of the two;
> > + */
> > + if (total_fls > 32) {
> > + shift = total_fls - 32; /* a = 2^shift */
> > + stime >>= shift;
> > + total >>= shift;
> > + stime_fls -= shift;
> > + total_fls -= shift;
> > + }
> > +
> > + /*
> > + * Since we limited stime to 32bits the multiplication reduced to 96bit.
> > + * stime * rtime = stime * (rl + rh * 2^32) =
> > + * stime * rl + stime * rh * 2^32
> > + */
> > + lo = stime * rtime_lo;
> > + hi = stime * rtime_hi;
> > + t = hi << 32;
> > + lo += t;
> > + if (lo < t) /* overflow */
> > + hi += 0x100000000L;
> > + hi >>= 32;
>
> I do not understand why we shift hi value here, is that correct?
Yes.. remember that we have:
stime * rl + stime * rh * 2^32
How we get this 96bit value but our two 64bit values overlap:
| w3 | w2 | w1 | w0 |
+----+----+----+----+
| lo |
| hi |
So what I do is I add the low word of hi to lo and shift the high word
of hi to get:
| hi | lo |
Two non-overlapping 64bit values where the high word of hi is always 0.
> > + /*
> > + * Pick the 64 most significant bits for division into @lo.
> > + *
> > + * NOTE: res_fls is an approximation (upper-bound) do we want to
> > + * properly calculate?
> > + */
> > + shift = 0;
> > + res_fls = stime_fls + rtime_fls;
> > + if (res_fls > 64) {
> > + shift = res_fls - 64; /* b = 2^shift */
> > + lo >>= shift;
> > + hi <<= 64 - shift;
> > + lo |= hi;
> > }
> > - return (__force cputime_t) scaled;
> > + /*
> > + * So here we do:
> > + *
> > + * ((stime / a) * rtime / b)
> > + * --------------------------- / b
> > + * (total / a)
> > + */
> > + return div_u64(lo, total) >> shift;
>
> I think it should be:
>
> ((stime / a) * rtime / b)
> --------------------------- * b
> (total / a)
>
> return div_u64(lo, total) << shift;
I think you're very right about that.. got my head twisted by staring
at this stuff too long.
next prev parent reply other threads:[~2013-04-11 17:31 UTC|newest]
Thread overview: 21+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <tip-d9a3c9823a2e6a543eb7807fb3d15d8233817ec5@git.kernel.org>
2013-03-26 14:01 ` [tip:sched/core] sched: Lower chances of cputime scaling overflow Stanislaw Gruszka
2013-03-26 14:19 ` Frederic Weisbecker
2013-03-26 16:54 ` Stanislaw Gruszka
2013-04-10 12:51 ` Ingo Molnar
2013-04-10 15:28 ` Frederic Weisbecker
2013-04-10 17:32 ` Ingo Molnar
2013-04-11 8:04 ` Stanislaw Gruszka
2013-04-11 13:45 ` Peter Zijlstra
2013-04-11 14:50 ` Stanislaw Gruszka
2013-04-11 17:31 ` Peter Zijlstra [this message]
2013-04-11 15:38 ` Linus Torvalds
2013-04-11 18:07 ` Peter Zijlstra
2013-04-11 18:22 ` Frederic Weisbecker
2013-04-11 18:26 ` Frederic Weisbecker
2013-04-11 18:22 ` Linus Torvalds
2013-04-12 7:55 ` Peter Zijlstra
2013-04-13 14:49 ` Stanislaw Gruszka
2013-04-13 18:44 ` Linus Torvalds
2013-04-16 10:40 ` Stanislaw Gruszka
2013-04-30 14:03 ` Stanislaw Gruszka
2013-04-13 14:55 ` Stanislaw Gruszka
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1365701469.10217.6.camel@laptop \
--to=peterz@infradead.org \
--cc=akpm@linux-foundation.org \
--cc=fweisbec@gmail.com \
--cc=hpa@zytor.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-tip-commits@vger.kernel.org \
--cc=mingo@kernel.org \
--cc=rostedt@goodmis.org \
--cc=sgruszka@redhat.com \
--cc=tglx@linutronix.de \
--cc=torvalds@linux-foundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).