From: Peter Zijlstra <peterz@infradead.org>
To: Tommaso Cucinotta <tommaso.cucinotta@sssup.it>
Cc: Juri Lelli <juri.lelli@gmail.com>,
tglx@linutronix.de, mingo@redhat.com, rostedt@goodmis.org,
cfriesen@nortel.com, oleg@redhat.com, fweisbec@gmail.com,
darren@dvhart.com, johan.eker@ericsson.com, p.faure@akatech.ch,
linux-kernel@vger.kernel.org, claudio@evidence.eu.com,
michael@amarulasolutions.com, fchecconi@gmail.com,
nicola.manica@disi.unitn.it, luca.abeni@unitn.it,
dhaval.giani@gmail.com, hgu1972@gmail.com,
paulmck@linux.vnet.ibm.com, raistlin@linux.it,
insop.song@ericsson.com, liming.wang@windriver.com
Subject: Re: [PATCH 05/16] sched: SCHED_DEADLINE policy implementation.
Date: Tue, 24 Apr 2012 11:50:27 +0200 [thread overview]
Message-ID: <1335261027.28150.189.camel@twins> (raw)
In-Reply-To: <4F95E3F1.3030407@sssup.it>
On Tue, 2012-04-24 at 00:21 +0100, Tommaso Cucinotta wrote:
> > Yes I can do it for x86_64, but people tend to get mighty upset if you
> > break the compile for all other arches...
>
> rather than breaking compile, I was thinking more of using the
> optimization for a more accurate comparison on archs that have 64-bit
> mul and 128-bit cmp, and leaving the overflow on other archs. Though,
> that would imply a difference in behavior on those borderline cases
> (very big periods I guess).
>
> However, I'm also puzzled from what would happen by compiling the
> current code on mostly 16-bit micros which have very limited 32-bit
> operations...
We don't support 16bit archs, 32bit is almost useless as it is :-)
Anyway, how about something like this, I guess archs can go wild and add
asm/math128.h if they want etc..
Completely untested, hasn't even seen a compiler..
---
Subject: math128: Add {add,mult,cmp}_u128
From: Peter Zijlstra <a.p.zijlstra@chello.nl>
Date: Tue Apr 24 11:47:12 CEST 2012
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
---
include/linux/math128.h | 75 ++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 75 insertions(+)
--- /dev/null
+++ b/include/linux/math128.h
@@ -0,0 +1,75 @@
+#ifndef _LINUX_MATH128_H
+#define _LINUX_MATH128_H
+
+#include <linux/types.h>
+
+typedef struct {
+ u64 hi, lo;
+} u128;
+
+u128 add_u128(u128 a, u128 b)
+{
+ u128 res;
+
+ res.hi = a.hi + b.hi;
+ res.lo = a.lo + b.lo;
+
+ if (res.lo < a.lo || res.lo < b.lo)
+ res.hi++;
+
+ return res;
+}
+
+/*
+ * a * b = (ah * 2^32 + al) * (bh * 2^32 + bl) =
+ * ah*bh * 2^64 + (ah*bl + bh*al) * 2^32 + al*bl
+ */
+u128 mult_u128(u64 a, u64 b)
+{
+ u128 res;
+ u64 ah, al;
+ u64 bh, bl;
+ u128 t1, t2, t3, t4;
+
+ ah = a >> 32;
+ al = a & ((1ULL << 32) - 1);
+
+ bh = b >> 32;
+ bl = b & ((1ULL << 32) - 1);
+
+ t1.lo = 0;
+ t1.hi = ah * bh;
+
+ t2.lo = ah * bl;
+ t2.hi = t2.lo >> 32;
+ t2.lo <<= 32;
+
+ t3.lo = al * bh;
+ t3.hi = t3.lo >> 32;
+ t3.lo <<= 32;
+
+ t4.lo = al * bl;
+ t4.hi = 0;
+
+ res = add_u128(t1, t2);
+ res = add_u128(res, t3);
+ res = add_u128(res, t4);
+
+ return res;
+}
+
+int cmp_u128(u128 a, u128 b)
+{
+ if (a.hi > b.hi)
+ return 1;
+ if (a.hi < b.hi)
+ return -1;
+ if (a.lo > b.lo)
+ return 1;
+ if (a.lo < b.lo)
+ return -1;
+
+ return 0;
+}
+
+#endif /* _LINUX_MATH128_H */
next prev parent reply other threads:[~2012-04-24 9:50 UTC|newest]
Thread overview: 129+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-04-06 7:14 [RFC][PATCH 00/16] sched: SCHED_DEADLINE v4 Juri Lelli
2012-04-06 7:14 ` [PATCH 01/16] sched: add sched_class->task_dead Juri Lelli
2012-04-08 17:49 ` Oleg Nesterov
2012-04-08 18:09 ` Juri Lelli
2012-04-06 7:14 ` [PATCH 02/16] sched: add extended scheduling interface Juri Lelli
2012-04-06 7:14 ` [PATCH 03/16] sched: SCHED_DEADLINE data structures Juri Lelli
2012-04-23 9:08 ` Peter Zijlstra
2012-04-23 9:47 ` Juri Lelli
2012-04-23 9:49 ` Peter Zijlstra
2012-04-23 9:55 ` Juri Lelli
2012-04-23 10:12 ` Peter Zijlstra
2012-04-23 9:13 ` Peter Zijlstra
2012-04-23 9:28 ` Juri Lelli
2012-04-23 9:30 ` Peter Zijlstra
2012-04-23 9:36 ` Juri Lelli
2012-04-23 9:39 ` Peter Zijlstra
2012-04-23 9:34 ` Peter Zijlstra
2012-04-23 10:16 ` Juri Lelli
2012-04-23 10:28 ` Peter Zijlstra
2012-04-23 10:33 ` Juri Lelli
2012-04-06 7:14 ` [PATCH 04/16] sched: SCHED_DEADLINE SMP-related " Juri Lelli
2012-04-06 7:14 ` [PATCH 05/16] sched: SCHED_DEADLINE policy implementation Juri Lelli
2012-04-11 3:06 ` Steven Rostedt
2012-04-11 6:54 ` Juri Lelli
2012-04-11 13:41 ` Steven Rostedt
2012-04-11 13:55 ` Juri Lelli
2012-04-23 10:15 ` Peter Zijlstra
2012-04-23 10:18 ` Juri Lelli
2012-04-23 10:31 ` Peter Zijlstra
2012-04-23 10:37 ` Juri Lelli
2012-04-23 21:25 ` Tommaso Cucinotta
2012-04-23 21:45 ` Peter Zijlstra
2012-04-23 23:25 ` Tommaso Cucinotta
2012-04-24 6:29 ` Dario Faggioli
2012-04-24 6:52 ` Juri Lelli
2012-04-23 11:32 ` Peter Zijlstra
2012-04-23 12:13 ` Juri Lelli
2012-04-23 12:22 ` Peter Zijlstra
2012-04-23 13:37 ` Juri Lelli
2012-04-23 14:01 ` Peter Zijlstra
2012-04-23 11:34 ` Peter Zijlstra
2012-04-23 11:57 ` Juri Lelli
2012-04-23 11:55 ` Peter Zijlstra
2012-04-23 14:43 ` Juri Lelli
2012-04-23 15:11 ` Peter Zijlstra
2012-04-23 21:55 ` Tommaso Cucinotta
2012-04-23 21:58 ` Peter Zijlstra
2012-04-23 23:21 ` Tommaso Cucinotta
2012-04-24 9:50 ` Peter Zijlstra [this message]
2012-04-24 1:03 ` Steven Rostedt
2012-04-23 14:11 ` Peter Zijlstra
2012-04-23 14:25 ` Peter Zijlstra
2012-04-23 15:34 ` Juri Lelli
2012-04-23 14:35 ` Peter Zijlstra
2012-04-23 15:39 ` Juri Lelli
2012-04-23 15:43 ` Peter Zijlstra
2012-04-23 16:41 ` Juri Lelli
[not found] ` <4F95D41F.5060700@sssup.it>
2012-04-24 7:21 ` Juri Lelli
2012-04-24 9:00 ` Peter Zijlstra
2012-05-15 10:10 ` Juri Lelli
2012-04-23 15:15 ` Peter Zijlstra
2012-04-23 15:37 ` Juri Lelli
2012-04-06 7:14 ` [PATCH 06/16] sched: SCHED_DEADLINE push and pull logic Juri Lelli
2012-04-06 13:39 ` Hillf Danton
2012-04-06 17:31 ` Juri Lelli
2012-04-07 2:32 ` Hillf Danton
2012-04-07 7:46 ` Dario Faggioli
2012-04-08 20:20 ` Juri Lelli
2012-04-09 12:28 ` Hillf Danton
2012-04-10 8:11 ` Juri Lelli
2012-04-11 15:57 ` Steven Rostedt
2012-04-11 16:00 ` Steven Rostedt
2012-04-11 16:09 ` Juri Lelli
2012-04-11 14:10 ` Steven Rostedt
2012-04-12 12:28 ` Hillf Danton
2012-04-12 12:51 ` Steven Rostedt
2012-04-12 12:56 ` Hillf Danton
2012-04-12 13:35 ` Steven Rostedt
2012-04-12 13:41 ` Hillf Danton
2012-04-11 16:07 ` Steven Rostedt
2012-04-11 16:11 ` Juri Lelli
2012-04-11 16:14 ` Steven Rostedt
2012-04-19 13:44 ` Juri Lelli
2012-04-11 16:21 ` Steven Rostedt
2012-04-11 16:24 ` Juri Lelli
2012-04-11 16:33 ` Steven Rostedt
2012-04-24 13:15 ` Peter Zijlstra
2012-04-24 18:50 ` Steven Rostedt
2012-04-24 18:53 ` Peter Zijlstra
2012-04-24 19:01 ` Steven Rostedt
2012-04-11 17:25 ` Steven Rostedt
2012-04-11 17:48 ` Juri Lelli
2012-04-06 7:14 ` [PATCH 07/16] sched: SCHED_DEADLINE avg_update accounting Juri Lelli
2012-04-06 7:14 ` [PATCH 08/16] sched: add period support for -deadline tasks Juri Lelli
2012-04-11 20:32 ` Steven Rostedt
2012-04-11 21:56 ` Juri Lelli
2012-04-11 22:13 ` Tommaso Cucinotta
2012-04-12 0:19 ` Steven Rostedt
2012-04-12 6:39 ` Luca Abeni
2012-04-06 7:14 ` [PATCH 09/16] sched: add schedstats " Juri Lelli
2012-04-06 7:14 ` [PATCH 10/16] sched: add resource limits " Juri Lelli
2012-04-24 15:07 ` Peter Zijlstra
2012-04-24 15:22 ` Juri Lelli
2012-04-24 16:27 ` Peter Zijlstra
2012-04-24 17:14 ` Juri Lelli
2012-04-06 7:14 ` [PATCH 11/16] sched: add latency tracing " Juri Lelli
2012-04-11 21:03 ` Steven Rostedt
2012-04-12 7:16 ` Juri Lelli
2012-04-16 15:51 ` Daniel Vacek
2012-04-16 19:56 ` Steven Rostedt
2012-04-16 21:31 ` Daniel Vacek
2012-04-06 7:14 ` [PATCH 12/16] rtmutex: turn the plist into an rb-tree Juri Lelli
2012-04-11 21:11 ` Steven Rostedt
2012-04-22 14:28 ` Juri Lelli
2012-04-23 8:33 ` Peter Zijlstra
2012-04-23 11:37 ` Steven Rostedt
2012-04-06 7:14 ` [PATCH 13/16] sched: drafted deadline inheritance logic Juri Lelli
2012-04-12 2:42 ` Steven Rostedt
2012-04-22 14:04 ` Juri Lelli
2012-04-23 8:39 ` Peter Zijlstra
2012-04-06 7:14 ` [PATCH 14/16] sched: add bandwidth management for sched_dl Juri Lelli
2012-04-06 7:14 ` [PATCH 15/16] sched: speed up -dl pushes with a push-heap Juri Lelli
2012-04-06 7:14 ` [PATCH 16/16] sched: add sched_dl documentation Juri Lelli
2012-04-06 8:25 ` [RFC][PATCH 00/16] sched: SCHED_DEADLINE v4 Luca Abeni
2012-04-07 9:25 ` Tadeus Prastowo
2012-04-06 11:07 ` Dario Faggioli
2012-04-11 14:17 ` Steven Rostedt
2012-04-11 14:28 ` Juri Lelli
2012-04-23 12:31 [PATCH 05/16] sched: SCHED_DEADLINE policy implementation cucinotta
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=1335261027.28150.189.camel@twins \
--to=peterz@infradead.org \
--cc=cfriesen@nortel.com \
--cc=claudio@evidence.eu.com \
--cc=darren@dvhart.com \
--cc=dhaval.giani@gmail.com \
--cc=fchecconi@gmail.com \
--cc=fweisbec@gmail.com \
--cc=hgu1972@gmail.com \
--cc=insop.song@ericsson.com \
--cc=johan.eker@ericsson.com \
--cc=juri.lelli@gmail.com \
--cc=liming.wang@windriver.com \
--cc=linux-kernel@vger.kernel.org \
--cc=luca.abeni@unitn.it \
--cc=michael@amarulasolutions.com \
--cc=mingo@redhat.com \
--cc=nicola.manica@disi.unitn.it \
--cc=oleg@redhat.com \
--cc=p.faure@akatech.ch \
--cc=paulmck@linux.vnet.ibm.com \
--cc=raistlin@linux.it \
--cc=rostedt@goodmis.org \
--cc=tglx@linutronix.de \
--cc=tommaso.cucinotta@sssup.it \
/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).