possible divide by 0 in kernel/sched/cputime.c scale_stime()
Since upgrading from v3.8 to v3.12 I see random crashes in function scale_stime() in kernel/sched/cputime.c:
divide error: 0000 [#1] SMP
Modules linked in: parport_pc(F) ppdev(F) bnep rfcomm bluetooth binfmt_misc(F)
zl10353 cx88_dvb cx88_vp3054_i2c videobuf_dvb dvb_core intel_powerclamp coretemp
kvm_intel(F) tuner_xc2028 kvm(F) i915 snd_hda_codec_hdmi snd_hda_codec_realtek
cx8800 cx8802 tuner snd_hda_intel snd_hda_codec cx88_alsa crct10dif_pclmul(F)
crc32_pclmul(F) snd_hwdep(F) snd_pcm(F) snd_page_alloc(F) ghash_clmulni_intel(F)
aesni_intel(F) snd_seq_midi(F) snd_seq_midi_event(F) snd_rawmidi(F) snd_seq(F)
joydev(F) cx88xx snd_seq_device(F) snd_timer(F) aes_x86_64(F) lrw(F) gf128mul(F)
glue_helper(F) video(F) btcx_risc drm_kms_helper ablk_helper(F) tveeprom cryptd(F)
lp(F) videobuf_dma_sg rc_core drm v4l2_common videobuf_core mei_me parport(F)
snd(F) mei soundcore(F) videodev i2c_algo_bit serio_raw(F) microcode(F) mac_hid
lpc_ich asus_atk0110 hid_generic usbhid hid usb_storage(F) firewire_ohci ahci(F)
libahci(F) firewire_core r8169 crc_itu_t(F) mii(F)
CPU: 3 PID: 15367 Comm: htop Tainted: GF 3.12.0-031200-generic #201311031935
Hardware name: System manufacturer System Product Name/P7H55-M PRO, BIOS 1709 01/04/2011
task: ffff8800cc09e000 ti: ffff8800af620000 task.ti: ffff8800af620000
RIP: 0010:[<ffffffff81099de0>] [<ffffffff81099de0>] cputime_adjust+0xf0/0x110
RSP: 0018:ffff8800af621cc8 EFLAGS: 00010847
RAX: 85fdc1fef4047c00 RBX: 0000000000000000 RCX: ffff8800af621df8
RDX: 0000000000000000 RSI: ffff8800cc0634d0 RDI: 0000000000000000
RBP: ffff8800af621cd8 R08: 00000000fffffffe R09: 0000000000000000
R10: 0000000000000000 R11: fffffffe03427acc R12: ffff8800af621df0
R13: ffff8800af621df8 R14: 0000000000000000 R15: ffff8800cc063300
FS: 00007f22a387d740(0000) GS:ffff880117c60000(0000) knlGS:0000000000000000
CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
CR2: 00007f22a3892000 CR3: 0000000097023000 CR4: 00000000000007e0
Stack:
ffff8800c37f0000 ffff8800af621df0 ffff8800af621d18 ffffffff8109aa51
000000000a7d8c00 0000000042fee100 fffffffe03427acc ffff8800bf112a80
ffff8800c37f0000 ffff8800c307c280 ffff8800af621e50 ffffffff8121f74b
Call Trace:
[<ffffffff8109aa51>] thread_group_cputime_adjusted+0x41/0x50
[<ffffffff8121f74b>] do_task_stat+0x8eb/0xb60
[<ffffffff81176400>] ? vma_compute_subtree_gap+0x50/0x50
[<ffffffff81220314>] proc_tgid_stat+0x14/0x20
[<ffffffff8121b16d>] proc_single_show+0x4d/0x90
[<ffffffff811d6eee>] seq_read+0x14e/0x390
[<ffffffff811b3725>] vfs_read+0x95/0x160
[<ffffffff811b4239>] SyS_read+0x49/0xa0
[<ffffffff81723ced>] system_call_fastpath+0x1a/0x1f
Code: 89 fa 49 c1 ea 20 4d 85 d2 74 ca 4c 89 c2 48 d1 ef 49 89 c0 48 d1 ea 48
89 d0 eb 9f 0f 1f 80 00 00 00 00 89 c0 31 d2 49 0f af c0 <48> f7 f7 4c
89 df 48 29 c7 49 89 c3 e9 31 ff ff ff 66 66 66 66
RIP [<ffffffff81099de0>] cputime_adjust+0xf0/0x110
RSP <ffff8800af621cc8>
---[ end trace dbafd2159a385dd6 ]---The affected LOC performing the division by 0 was introduced in commit
commit 55eaa7c1f511af5fb6ef808b5328804f4d4e5243
Author: Stanislaw Gruszka <[email protected]>
Date: Tue Apr 30 17:14:42 2013 +0200
sched: Avoid cputime scaling overflow
For the problem to occur the function is called eg. with the following input parameters
stime: 0x3567e00
rtime: 0xffffffffbf1abfdb
total: 0x3938700
which leads to 'total' being shifted to 0 during the adaption of the precision and is then used without further check in
scaled = div_u64((u64) (u32) stime * (u64) (u32) rtime, (u32)total);
The root cause triggering this issue seems to be an overflowed value of
rtime = nsecs_to_cputime(curr->sum_exec_runtime);
On the affected machine the problem can be triggered by loading the previously idle system by starting a full kernel build. The problem occurs within a minute after the ondemand frequency scaling governor adjusts the frequency from the minimum to the maximum.
The x86 init check whether all booted CPUs have their TSC's synchronized, never failed so far, however, the tsc clocksource is sporadically marked unstable.
Clocksource tsc unstable (delta = -74994678 ns)
The used CPU provides an Intel Invariant TSC as stated by CPUID.80000007H:EDX[8]:
eax in eax ebx ecx edx
00000000 0000000b 756e6547 6c65746e 49656e69
00000001 00020652 04100800 0298e3ff bfebfbff
00000002 55035a01 00f0b2e3 00000000 09ca212c
00000003 00000000 00000000 00000000 00000000
00000004 00000000 00000000 00000000 00000000
00000005 00000040 00000040 00000003 00001120
00000006 00000005 00000002 00000001 00000000
00000007 00000000 00000000 00000000 00000000
00000008 00000000 00000000 00000000 00000000
00000009 00000000 00000000 00000000 00000000
0000000a 07300403 00000004 00000000 00000603
0000000b 00000000 00000000 0000002c 00000004
80000000 80000008 00000000 00000000 00000000
80000001 00000000 00000000 00000001 28100800
80000002 65746e49 2952286c 726f4320 4d542865
80000003 35692029 55504320 20202020 20202020
80000004 30353620 20402020 30322e33 007a4847
80000005 00000000 00000000 00000000 00000000
80000006 00000000 00000000 01006040 00000000
80000007 00000000 00000000 00000000 00000100
80000008 00003024 00000000 00000000 00000000
Vendor ID: "GenuineIntel"; CPUID level 11
Intel-specific functions:
Version 00020652:
Type 0 - Original OEM
Family 6 - Pentium Pro
Model 5 - Pentium II Model 5/Xeon/Celeron
Stepping 2
Reserved 8
Extended brand string: "Intel(R) Core(TM) i5 CPU 650 @ 3.20GHz"
CLFLUSH instruction cache line size: 8
Initial APIC ID: 4
Hyper threading siblings: 16
Feature flags bfebfbff:
FPU Floating Point Unit VME Virtual 8086 Mode Enhancements DE Debugging Extensions PSE Page Size Extensions TSC Time Stamp Counter MSR Model Specific Registers PAE Physical Address Extension MCE Machine Check Exception CX8 COMPXCHG8B Instruction APIC On-chip Advanced Programmable Interrupt Controller present and enabled SEP Fast System Call MTRR Memory Type Range Registers PGE PTE Global Flag MCA Machine Check Architecture CMOV Conditional Move and Compare Instructions FGPAT Page Attribute Table PSE-36 36-bit Page Size Extension CLFSH CFLUSH instruction DS Debug store ACPI Thermal Monitor and Clock Ctrl MMX MMX instruction set FXSR Fast FP/MMX Streaming SIMD Extensions save/restore SSE Streaming SIMD Extensions instruction set SSE2 SSE2 extensions SS Self Snoop HT Hyper Threading TM Thermal monitor 31 reserved
Nevertheless, when looking into the issue I saw occurences of sched_clock going backwards as if the TSCs were read out of sync. Accordingly the problem does not occur when either booting with option 'nosmp' or when forcing the TSC to be marked as unstable for sched_clock. Booting with 'acpi=off' and no frequency scaling works too.
Having a look at the scheduler code I see the following pattern that would also catch a time warp, eg. kernel/sched/rt.c update_curr_rt():
u64 delta_exec;
delta_exec = rq_clock_task(rq) - curr->se.exec_start;
if (unlikely((s64)delta_exec <= 0))
return;However, there are still vulnerable places, eg. kernel/sched/fair.c update_curr():
/*
* Get the amount of time the current task was running
* since the last time we changed load (this cannot
* overflow on 32 bits):
*/
delta_exec = (unsigned long)(now - curr->exec_start); if (!delta_exec)
return;
Regards,
Christian
Hi Christian
Quoted 169 lines · Christian Engelmayer
Since upgrading from v3.8 to v3.12 I see random crashes in function
scale_stime()inkernel/sched/cputime.c:divide error: 0000 [#1] SMP Modules linked in: parport_pc(F) ppdev(F) bnep rfcomm bluetooth binfmt_misc(F) zl10353 cx88_dvb cx88_vp3054_i2c videobuf_dvb dvb_core intel_powerclamp coretemp kvm_intel(F) tuner_xc2028 kvm(F) i915 snd_hda_codec_hdmi snd_hda_codec_realtek cx8800 cx8802 tuner snd_hda_intel snd_hda_codec cx88_alsa crct10dif_pclmul(F) crc32_pclmul(F) snd_hwdep(F) snd_pcm(F) snd_page_alloc(F) ghash_clmulni_intel(F) aesni_intel(F) snd_seq_midi(F) snd_seq_midi_event(F) snd_rawmidi(F) snd_seq(F) joydev(F) cx88xx snd_seq_device(F) snd_timer(F) aes_x86_64(F) lrw(F) gf128mul(F) glue_helper(F) video(F) btcx_risc drm_kms_helper ablk_helper(F) tveeprom cryptd(F) lp(F) videobuf_dma_sg rc_core drm v4l2_common videobuf_core mei_me parport(F) snd(F) mei soundcore(F) videodev i2c_algo_bit serio_raw(F) microcode(F) mac_hid lpc_ich asus_atk0110 hid_generic usbhid hid usb_storage(F) firewire_ohci ahci(F) libahci(F) firewire_core r8169 crc_itu_t(F) mii(F) CPU: 3 PID: 15367 Comm: htop Tainted: GF 3.12.0-031200-generic #201311031935 Hardware name: System manufacturer System Product Name/P7H55-M PRO, BIOS 1709 01/04/2011 task: ffff8800cc09e000 ti: ffff8800af620000 task.ti: ffff8800af620000 RIP: 0010:[<ffffffff81099de0>] [<ffffffff81099de0>] cputime_adjust+0xf0/0x110 RSP: 0018:ffff8800af621cc8 EFLAGS: 00010847 RAX: 85fdc1fef4047c00 RBX: 0000000000000000 RCX: ffff8800af621df8 RDX: 0000000000000000 RSI: ffff8800cc0634d0 RDI: 0000000000000000 RBP: ffff8800af621cd8 R08: 00000000fffffffe R09: 0000000000000000 R10: 0000000000000000 R11: fffffffe03427acc R12: ffff8800af621df0 R13: ffff8800af621df8 R14: 0000000000000000 R15: ffff8800cc063300 FS: 00007f22a387d740(0000) GS:ffff880117c60000(0000) knlGS:0000000000000000 CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 CR2: 00007f22a3892000 CR3: 0000000097023000 CR4: 00000000000007e0 Stack: ffff8800c37f0000 ffff8800af621df0 ffff8800af621d18 ffffffff8109aa51 000000000a7d8c00 0000000042fee100 fffffffe03427acc ffff8800bf112a80 ffff8800c37f0000 ffff8800c307c280 ffff8800af621e50 ffffffff8121f74b Call Trace: [<ffffffff8109aa51>] thread_group_cputime_adjusted+0x41/0x50 [<ffffffff8121f74b>] do_task_stat+0x8eb/0xb60 [<ffffffff81176400>] ? vma_compute_subtree_gap+0x50/0x50 [<ffffffff81220314>] proc_tgid_stat+0x14/0x20 [<ffffffff8121b16d>] proc_single_show+0x4d/0x90 [<ffffffff811d6eee>] seq_read+0x14e/0x390 [<ffffffff811b3725>] vfs_read+0x95/0x160 [<ffffffff811b4239>] SyS_read+0x49/0xa0 [<ffffffff81723ced>] system_call_fastpath+0x1a/0x1f Code: 89 fa 49 c1 ea 20 4d 85 d2 74 ca 4c 89 c2 48 d1 ef 49 89 c0 48 d1 ea 48 89 d0 eb 9f 0f 1f 80 00 00 00 00 89 c0 31 d2 49 0f af c0 <48> f7 f7 4c 89 df 48 29 c7 49 89 c3 e9 31 ff ff ff 66 66 66 66 RIP [<ffffffff81099de0>] cputime_adjust+0xf0/0x110 RSP <ffff8800af621cc8> ---[ end trace dbafd2159a385dd6 ]---The affected LOC performing the division by 0 was introduced in commit
commit
55eaa7c1f511af5fb6ef808b5328804f4d4e5243
Author: Stanislaw Gruszka <[email protected]>
Date: Tue Apr 30 17:14:42 2013 +0200
sched: Avoid cputime scaling overflowFor the problem to occur the function is called eg. with the following input parameters
stime: 0x3567e00 rtime: 0xffffffffbf1abfdb total: 0x3938700which leads to 'total' being shifted to 0 during the adaption of the precision and is then used without further check in
scaled = div_u64((u64) (u32) stime * (u64) (u32) rtime, (u32)total);The root cause triggering this issue seems to be an overflowed value of
rtime = nsecs_to_cputime(curr->sum_exec_runtime);On the affected machine the problem can be triggered by loading the previously idle system by starting a full kernel build. The problem occurs within a minute after the ondemand frequency scaling governor adjusts the frequency from the minimum to the maximum.
The x86 init check whether all booted CPUs have their TSC's synchronized, never failed so far, however, the tsc clocksource is sporadically marked unstable.
Clocksource tsc unstable (delta = -74994678 ns)
The used CPU provides an Intel Invariant TSC as stated by CPUID.80000007H:EDX[8]:
eax in eax ebx ecx edx
000000000000000b756e65476c65746e49656e69
00000001 00020652 041008000298e3ffbfebfbff
0000000255035a0100f0b2e30000000009ca212c
00000003 00000000 00000000 00000000 00000000
00000004 00000000 00000000 00000000 00000000
00000005 00000040 00000040 00000003 00001120
00000006 00000005 00000002 00000001 00000000
00000007 00000000 00000000 00000000 00000000
00000008 00000000 00000000 00000000 00000000
00000009 00000000 00000000 00000000 00000000
0000000a07300403 00000004 00000000 00000603
0000000b00000000 000000000000002c00000004
80000000 80000008 00000000 00000000 00000000
80000001 00000000 00000000 00000001 28100800
8000000265746e492952286c726f43204d542865
80000003 35692029 55504320 20202020 20202020
80000004 30353620 2040202030322e33007a4847
80000005 00000000 00000000 00000000 00000000
80000006 00000000 00000000 01006040 00000000
80000007 00000000 00000000 00000000 00000100
80000008 00003024 00000000 00000000 00000000Vendor ID: "GenuineIntel"; CPUID level 11
Intel-specific functions:
Version 00020652:
Type 0 - Original OEM
Family 6 - Pentium Pro
Model 5 - Pentium II Model 5/Xeon/Celeron
Stepping 2
Reserved 8Extended brand string: "Intel(R) Core(TM) i5 CPU 650 @ 3.20GHz"
CLFLUSH instruction cache line size: 8
Initial APIC ID: 4
Hyper threading siblings: 16Feature flags bfebfbff:
FPU Floating Point Unit VME Virtual 8086 Mode Enhancements DE Debugging Extensions PSE Page Size Extensions TSC Time Stamp Counter MSR Model Specific Registers PAE Physical Address Extension MCE Machine Check Exception CX8 COMPXCHG8B Instruction APIC On-chip Advanced Programmable Interrupt Controller present and enabled SEP Fast System Call MTRR Memory Type Range Registers PGE PTE Global Flag MCA Machine Check Architecture CMOV Conditional Move and Compare Instructions FGPAT Page Attribute Table PSE-36 36-bit Page Size Extension CLFSH CFLUSH instruction DS Debug store ACPI Thermal Monitor and Clock Ctrl MMX MMX instruction set FXSR Fast FP/MMX Streaming SIMD Extensions save/restore SSE Streaming SIMD Extensions instruction set SSE2 SSE2 extensions SS Self Snoop HT Hyper Threading TM Thermal monitor 31 reservedNevertheless, when looking into the issue I saw occurences of
sched_clockgoing backwards as if the TSCs were read out of sync. Accordingly the problem does not occur when either booting with option 'nosmp' or when forcing the TSC to be marked as unstable forsched_clock. Booting with 'acpi=off' and no frequency scaling works too.Having a look at the scheduler code I see the following pattern that would also catch a time warp, eg.
kernel/sched/rt.cupdate_curr_rt():u64 delta_exec; delta_exec = rq_clock_task(rq) - curr->se.exec_start; if (unlikely((s64)delta_exec <= 0)) return;However, there are still vulnerable places, eg.
kernel/sched/fair.cupdate_curr():
Quoted 8 lines
/*
* Get the amount of time the current task was running
* since the last time we changed load (this cannot
* overflow on 32 bits):
*/
delta_exec = (unsigned long)(now - curr->exec_start);
if (!delta_exec)
return;Thanks for great analyse. I'm not sure where this problem should be fixed (in TSC clocksource or sched/fair.c or sched/cputime.c), however since RT scheduler is protected for sched_clock going backward, we probably can protect fair scheduler as well (also do_task_delta_exec() has similar check).
Does the below patch fixes the issue on affected machine?
Stanislaw
kernel/sched/fair.c +1 -3
@@ -727,7 +727,7 @@ static void update_curr(struct cfs_rq *cfs_rq)u64 now =rq_clock_task (rq_of (cfs_rq));unsigned long delta_exec; -if (unlikely (!curr)) +if (unlikely (!curr || now <= curr->exec_start))return ;/*
@@ -736,8 +736,6 @@ static void update_curr(struct cfs_rq *cfs_rq)* overflow on 32 bits): */ delta_exec = (unsigned long )(now - curr->exec_start); -if (!delta_exec) -return ;__update_curr (cfs_rq, curr, delta_exec); curr->exec_start = now;
Peter Zijlstra
maintainerQuoted 10 lines · Stanislaw Gruszka
Quoted 10 lines
The x86 init check whether all booted CPUs have their TSC's synchronized, never failed so far, however, the tsc clocksource is sporadically marked unstable.
Clocksource tsc unstable (delta = -74994678 ns)
Version 00020652:
Type 0 - Original OEM
Family 6 - Pentium Pro
Model 5 - Pentium II Model 5/Xeon/Celeron
Extended brand string: "Intel(R) Core(TM) i5 CPU 650 @ 3.20GHz"
I'm not sure what tool you used to generate that, but its broken, that's model 0x25 (37), it somehow truncates the upper model bits.
That said, its a westmere core and I've seen wsm-ep (dual socket) machines loose their TSC sync quite regularly, but this would be the first case a single socket wsm would loose its TSC sync.
That leads me to believe your BIOS is screwing you over with SMIs or the like.
I would be tempted to say you should simply mark the tsc unstable on boot and live with that -- we fully assume the sched_clock stuff is not going backwards in an 'observable' way.
That said, it might be nice to not crash either..
Quoted 3 lines · Peter Zijlstra
I would be tempted to say you should simply mark the tsc unstable on boot and live with that -- we fully assume the
sched_clockstuff is not going backwards in an 'observable' way.
BIOS crap and actual hardware bugs do happen - so kernel code needs to consider TSC input with a pinch of salt, assuming that it's untrusted external data.
Quoted 1 line
That said, it might be nice to not crash either..
Indeed, not crashing on weird TSC input is absolutely required!
Thanks,
Ingo
Peter Zijlstra
maintainerkernel/sched/fair.c static void update_curr(struct cfs_rq *cfs_rq) · line 731
Quoted 11 lines · Stanislaw Gruszka
kernel/sched/fair.c +1
-1@@ -727,7 +727,7 @@ static void update_curr(struct cfs_rq *cfs_rq)u64 now =rq_clock_task (rq_of (cfs_rq));unsigned long delta_exec; -if (unlikely (!curr)) +if (unlikely (!curr || now <= curr->exec_start))return ;
That is not actually correct in the case time wraps.
There's a further problem with this code though -- ever since Frederic added NO_HZ_FULL a CPU can in fact aggregate a runtime delta larger than 4 seconds, due to running without a tick.
Therefore we need to be able to deal with u64 deltas.
The below is a compile tested only attempt to deal with both these problems. Comments?
--- arch/x86/Kconfig | 1 + include/linux/math64.h | 32 +++++++++++ init/Kconfig | 6 +++ kernel/sched/fair.c | 144 ++++++++++++++++++++++--------------------------- 4 files changed, 102 insertions(+), 81 deletions(-)
arch/x86/Kconfig +1 -0
@@ -26,6 +26,7 @@ config X86 select HAVE_AOUT if X86_32 select HAVE_UNSTABLE_SCHED_CLOCK select ARCH_SUPPORTS_NUMA_BALANCING + select ARCH_SUPPORTS_INT128 select ARCH_WANTS_PROT_NUMA_PROT_NONE select HAVE_IDE select HAVE_OPROFILE
include/linux/math64.h +32 -0
@@ -133,4 +133,36 @@ __iter_div_u64_rem(u64 dividend, u32 divisor, u64 *remainder)return ret; } +#if defined(CONFIG_ARCH_SUPPORTS_INT128 ) && defined(__SIZEOF_INT128__) + +#ifndef mul_u64_u32_shr +static inline u64 mul_u64_u32_shr (u64 a,u32 mul,unsigned int shift) +{ +return (u64)(((unsigned __int128 )a * mul) >> shift); +} +#endif /* mul_u64_u32_shr */ + +#else + +#ifndef mul_u64_u32_shr +static inline u64 mul_u64_u32_shr (u64 a,u32 mul,unsigned int shift) +{ +u32 ah, al; +u64 t1, t2; + + al = a; + ah = a >>32 ; + + t1 = ((u64 )al * mul) >> shift; +if (ah) { + t2 = ((u64 )ah * mul) << (32 - shift); + t1 += t2; + } + +return t1; +} +#endif /* mul_u64_u32_shr */ + +#endif +#endif /* _LINUX_MATH64_H */
init/Kconfig +6 -0
@@ -823,6 +823,12 @@ config GENERIC_SCHED_CLOCK config ARCH_SUPPORTS_NUMA_BALANCING bool +# +# For architectures that know their GCC __int128 support is sound +# +config ARCH_SUPPORTS_INT128 + bool + # For architectures that (ab)use NUMA to represent different memory regions # all cpu-local but of different latencies, such as SuperH. #
kernel/sched/fair.c +63 -81
217 lines not on this page · raw message
Quoted 2 lines · Peter Zijlstra
The below is a compile tested only attempt to deal with both these problems. Comments?
Just two nits as I don't understand vast of the patch.
kernel/sched/fair.c void init_task_runnable_average(struct task_struct *p) · line 718
Quoted 3 lines
kernel/sched/fair.c +2
-0+ delta_exec = now - curr->exec_start; +if ((s64 )delta_exec <0 )return ;
Check here should probably use <= and also unlikely() would be reasonable.
kernel/sched/fair.c void init_task_runnable_average(struct task_struct *p) · line 723
Quoted 2 lines
kernel/sched/fair.c +2
-0+schedstat_set (curr->statistics.exec_max, +max ((u64 )delta_exec, curr->statistics.exec_max));
(u64) cast not needed.
Stanislaw
Quoted 10 lines · Peter Zijlstra
That is not actually correct in the case time wraps.
There's a further problem with this code though -- ever since Frederic added
NO_HZ_FULLa CPU can in fact aggregate a runtime delta larger than 4 seconds, due to running without a tick.Therefore we need to be able to deal with u64 deltas.
The below is a compile tested only attempt to deal with both these problems. Comments?
I had this patch applied during daily use. No systematic testing, but no user perceived regressions either. The originally reported divide by 0 scenario could no longer be reproduced with this change.
Quoted 4 lines
kernel/sched/fair.c +4
-0+/* +* delta_exec * weight / lw.weight +* OR +* (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT
kernel/sched/fair.c void sched_init_granularity(void) · line 214
Quoted 10 lines
kernel/sched/fair.c +10
-0+* +* Either weight := NICE_0_LOAD and lw \e prio_to_wmult[], in which case +* we're guaranteed shift stays positive because inv_weight is guaranteed to +* fit 32 bits, and NICE_0_LOAD gives another 10 bits; therefore shift >= 22. +* +* Or, weight =< lw.weight (because lw.weight is the runqueue weight), thus +* XXX mind got twisted, but I'm fairly sure shift will stay positive. +* +*/ +static u64 __calc_delta (u64 delta_exec,unsigned long weight,struct load_weight *lw)
The patch itself seems comprehensible to me, although I have to admit that I would have to read into the code more deeply in order to understand why the changed __calc_delta() will always prove correct.
Quoted 2 lines · Peter Zijlstra
I'm not sure what tool you used to generate that, but its broken, that's model
0x25(37), it somehow truncates the upper model bits.
Correct, that was the fairly outdated cpuid (http://www.ka9q.net/code/cpuid)
currently shipped with Ubuntu 13.10. Debian already switched to packaging a maintained version (http://www.etallen.com/cpuid.html).
Quoted 6 lines
That said, its a westmere core and I've seen wsm-ep (dual socket) machines loose their TSC sync quite regularly, but this would be the first case a single socket wsm would loose its TSC sync.
That leads me to believe your BIOS is screwing you over with SMIs or the like.
Having rechecked the running microcode as hinted by Henrique de Moraes Holschuh off-list and running the Intel BIOS Implementation Test Suite (http://biosbits.org)
that seems to be an educated guess.
Regards,
Christian
Peter Zijlstra
maintainerPATCH 1/1 sched, fair: Rework sched_fair time accounting
Quoted 3 lines · Christian Engelmayer
I had this patch applied during daily use. No systematic testing, but no user perceived regressions either. The originally reported divide by 0 scenario could no longer be reproduced with this change.
Thanks! slightly updated version below.
I took some care to make sure the patch compiles into two 32x32->64 multiplications in the common case for 32bit.
Sadly GCC is too smart and completely fails to get the hint; the line:
fact = (u64)(u32)fact * lw->inv_weight;
Is converted into a double imul+mul monster for -O2. The only way to get the proper single mul is by forcing it into a noinline function, but that adds call/stack overhead.
That said, given a sensible compiler (ha!) the common case for 32bit should be equal or better than before.
---
Subject: sched, fair: Rework sched_fair time accounting
From: Peter Zijlstra <[email protected]>
Date: Mon, 18 Nov 2013 18:27:06 +0100
Christian suffers from a bad BIOS that wrecks his i5's TSC sync. This results in him occasionally seeing time going backwards.
Most of our time accounting can actually handle that except the most common one; the tick time update of sched_fair.
There is a further problem with that code; previously we assumed that because we get a tick every TICK_NSEC our time delta could never exceed 32bits and math was simpler.
However, ever since Frederic managed to get NO_HZ_FULL merged; this is no longer the case since now a task can run for a long time indeed without getting a tick. It only takes about ~4.2 seconds to overflow our u32 in nanoseconds.
This means we not only need to better deal with time going backwards; but also means we need to be able to deal with large deltas.
This patch reworks the entire code and introduces mul_u64_u32_shr() as proposed by Andy a long while ago.
We express our virtual time scale factor in a u32 multiplier and shift right and the 32bit mul_u64_u32_shr() implementation reduces to a single 32x32->64 multiply if the time delta is still short (common case).
For 64bit a 64x64->128 multiply can be used if ARCH_SUPPORTS_INT128; I didn't want to write fallback code for now, but we could.
--- arch/x86/Kconfig | 1 include/linux/math64.h | 30 ++++++++++ include/linux/sched.h | 3 - init/Kconfig | 6 ++ kernel/sched/fair.c | 144 +++++++++++++++++++++---------------------------- 5 files changed, 103 insertions(+), 81 deletions(-)
arch/x86/Kconfig +1 -0
@@ -26,6 +26,7 @@ config X86 select HAVE_AOUT if X86_32 select HAVE_UNSTABLE_SCHED_CLOCK select ARCH_SUPPORTS_NUMA_BALANCING + select ARCH_SUPPORTS_INT128 if X86_64 select ARCH_WANTS_PROT_NUMA_PROT_NONE select HAVE_IDE select HAVE_OPROFILE
include/linux/math64.h +30 -0
@@ -133,4 +133,34 @@ __iter_div_u64_rem(u64 dividend, u32 div return ret; } +#if defined(CONFIG_ARCH_SUPPORTS_INT128 ) && defined(__SIZEOF_INT128__) + +#ifndef mul_u64_u32_shr +static inline u64 mul_u64_u32_shr (u64 a,u32 mul,unsigned int shift) +{ +return (u64)(((unsigned __int128 )a * mul) >> shift); +} +#endif /* mul_u64_u32_shr */ + +#else + +#ifndef mul_u64_u32_shr +static inline u64 mul_u64_u32_shr (u64 a,u32 mul,unsigned int shift) +{ +u32 ah, al; +u64 ret; + + al = a; + ah = a >>32 ; + + ret = ((u64 )al * mul) >> shift; +if (ah) + ret += ((u64 )ah * mul) << (32 - shift); + +return ret; +} +#endif /* mul_u64_u32_shr */ + +#endif +#endif /* _LINUX_MATH64_H */
include/linux/sched.h +2 -1
@@ -932,7 +932,8 @@ struct pipe_inode_info;struct uts_namespace ;struct load_weight { -unsigned long weight, inv_weight; +unsigned long weight; +u32 inv_weight; };struct sched_avg {
init/Kconfig +6 -0
@@ -809,6 +809,12 @@ config GENERIC_SCHED_CLOCK config ARCH_SUPPORTS_NUMA_BALANCING bool +# +# For architectures that know their GCC __int128 support is sound +# +config ARCH_SUPPORTS_INT128 + bool + # For architectures that (ab)use NUMA to represent different memory regions # all cpu-local but of different latencies, such as SuperH. #
kernel/sched/fair.c +64 -80
218 lines not on this page · raw message
tip-bot for Peter Zijlstra
merge bot[tip:sched/urgent] sched/fair: Rework sched_fair time accounting
In reply to Peter Zijlstrasched/fair: Rework sched_fair time accounting
Commit-ID: 9dbdb155532395ba000c5d5d187658b0e17e529f Gitweb: http://git.kernel.org/tip/9dbdb155532395ba000c5d5d187658b0e17e529f Author: Peter Zijlstra <[email protected]> AuthorDate: Mon, 18 Nov 2013 18:27:06 +0100 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 11 Dec 2013 15:52:35 +0100
sched/fair: Rework sched_fair time accounting
Christian suffers from a bad BIOS that wrecks his i5's TSC sync. This results in him occasionally seeing time going backwards - which crashes the scheduler ...
Most of our time accounting can actually handle that except the most common one; the tick time update of sched_fair.
There is a further problem with that code; previously we assumed that because we get a tick every TICK_NSEC our time delta could never exceed 32bits and math was simpler.
However, ever since Frederic managed to get NO_HZ_FULL merged; this is no longer the case since now a task can run for a long time indeed without getting a tick. It only takes about ~4.2 seconds to overflow our u32 in nanoseconds.
This means we not only need to better deal with time going backwards; but also means we need to be able to deal with large deltas.
This patch reworks the entire code and uses mul_u64_u32_shr() as proposed by Andy a long while ago.
We express our virtual time scale factor in a u32 multiplier and shift right and the 32bit mul_u64_u32_shr() implementation reduces to a single 32x32->64 multiply if the time delta is still short (common case).
For 64bit a 64x64->128 multiply can be used if ARCH_SUPPORTS_INT128.
--- include/linux/sched.h | 3 +- kernel/sched/fair.c | 144 ++++++++++++++++++++++---------------------------- 2 files changed, 66 insertions(+), 81 deletions(-)
include/linux/sched.h +2 -1
@@ -930,7 +930,8 @@ struct pipe_inode_info;struct uts_namespace ;struct load_weight { -unsigned long weight, inv_weight; +unsigned long weight; +u32 inv_weight; };struct sched_avg {
kernel/sched/fair.c +64 -80
218 lines not on this page · raw message