Hi Everyone

Consider this as an open thread to discuss and talk about Cachy/CacULE

I would post some patches for testing too.

We could talk about how to enhance the scheduler.

Thank you.

Hi @hamadmarri

Since CacULE scheduler might work better on some machine/load, and Cachy might work better for the others, it probably makes sense to have a single patch and use kconfig menu to select between Cachy/CacULE, similar to how PDS/BMQ schedulers did. The source codes between Cachy/CacULE are also quite similar in my opinion, as the most noticeable difference is the scheduling policy.

#21 (comment)

GRQ shows mm bug when CONFIG_PREEMPT=y.
So far it seems working fine with CONFIG_PREEMPT_VOLUNTARY = y

When playing something with Cemu emulator, it will start locking up for couple seconds at the time then will lock whole the system, tested with few others, it seems to occur when CPU is particularly strained, GPU just locks up

[ AMD Raven, 4 core APU ]

Would be really nice. :)

Hi @hamadmarri

It would be nice to have the latest RDB support the schedutil CPU frequency governor, which would be helpful on battery-powered devices. Since the autogroup-testing RDB patch on 5.12 can already support schedutil, I am wondering if it could be possible to port necessary changes to 5.13. To avoid those re-enabled statistics messing up the performance when schedutil is disabled in Kconfig, maybe we can add something like #if defined(CONFIG_CPU_FREQ_GOV_SCHEDUTIL) on those statistics.

Currently I am using the latest autogroup-testing RDB patch synced to 5.13 and schedutil works fine on my laptop.
rdb-autogroup-testing_5.13.zip

Hi Hamad ... you're doing a great job, but there are problems with nvidia modules - it says exec is invalid and won't load the module:

soryy my fault - bad name of kernel - working great ;)

WOW ... Man, your work is brilliant - see equal - optimized kernel for Kabylake - first movie on your scheduler, second CFS - hope you can see the difference - nice load on all cores/threads - our NeteXt`73

https://www.dropbox.com/sh/0utb407a7j23aek/AAAJEWjL9kboC_sodX26HNJBa?dl=0

Best regards

Tomek

Hi with 5.8.6 Kernel, i get around 4700~ score with PDS scheduler but only get 4200 with cachy, i think that 500 points come from numa=y option in the kernel, is there way cachy to be modified to work with numa=y ?

Update: I've patched 5.7.19 with the 5.7.10 patch from the repository and i dont see a geekbench score reduction with numa=n. I get 4700~. But im not sure if cachy is really active right now. I dont see a cachy option in the kernel configuration menu. And the patch file was too small comparing the 5.8.3 patch. Can you explain why my score dropped that much with 5.8.3?

kernel/sysctl.c:1696:13: error: ‘sysctl_sched_migration_cost’ undeclared here (not in a function); did you mean ‘sysctl_timer_migration’? 1696 | .data = &sysctl_sched_migration_cost, | ^~~~~~~~~~~~~~~~~~~~~~~~~~~ | sysctl_timer_migration

kernel 5.10.27

Hi Hamad
I try to build with latest kernel 5.8.3 but have a small problem
please see log:

CC kernel/bpf/tnum.o
In file included from ./arch/x86/include/asm/current.h:5,
from ./include/linux/sched.h:12,
from kernel/sched/sched.h:5,
from kernel/sched/fair.c:23:
kernel/sched/fair.c: In function 'pick_next_task_fair':
kernel/sched/fair.c:6218:17: error: implicit declaration of function 'check_cfs_rq_runtime'; did you mean 'init_cfs_rq_runtime'? [-Werror=implicit-function-declaration]
6218 | if (unlikely(check_cfs_rq_runtime(cfs_rq))) {
| ^~~~~~~~~~~~~~~~~~~~
./include/linux/compiler.h:78:42: note: in definition of macro 'unlikely'
78 | # define unlikely(x) __builtin_expect(!!(x), 0)
| ^
kernel/sched/fair.c:6228:8: error: implicit declaration of function 'pick_next_entity'; did you mean 'set_next_entity'? [-Werror=implicit-function-declaration]
6228 | se = pick_next_entity(cfs_rq, curr);
| ^~~~~~~~~~~~~~~~
| set_next_entity
kernel/sched/fair.c:6228:6: warning: assignment to 'struct sched_entity *' from 'int' makes pointer from integer without a cast [-Wint-conversion]
6228 | se = pick_next_entity(cfs_rq, curr);
| ^
CC kernel/sched/wait_bit.o
At top level:
kernel/sched/fair.c:2844:13: warning: 'update_scan_period' defined but not used [-Wunused-function]
2844 | static void update_scan_period(struct task_struct *p, int new_cpu)
| ^~~~~~~~~~~~~~~~~~

first start nothing, but stopping and starting VM gets you

Aug 26 09:54:39 Tower kernel: SVM: kvm [21606]: vcpu0, guest rIP: 0xfffff853d6ef22f4 unimplemented wrmsr: 0xc0010115 data 0x0
Aug 26 09:54:39 Tower kernel: SVM: kvm [21606]: vcpu1, guest rIP: 0xfffff853d6ef22f4 unimplemented wrmsr: 0xc0010115 data 0x0
Aug 26 09:54:39 Tower kernel: SVM: kvm [21606]: vcpu2, guest rIP: 0xfffff853d6ef22f4 unimplemented wrmsr: 0xc0010115 data 0x0
Aug 26 09:54:39 Tower kernel: SVM: kvm [21606]: vcpu3, guest rIP: 0xfffff853d6ef22f4 unimplemented wrmsr: 0xc0010115 data 0x0
Aug 26 09:54:39 Tower kernel: SVM: kvm [21606]: vcpu4, guest rIP: 0xfffff853d6ef22f4 unimplemented wrmsr: 0xc0010115 data 0x0
Aug 26 09:54:39 Tower kernel: SVM: kvm [21606]: vcpu5, guest rIP: 0xfffff853d6ef22f4 unimplemented wrmsr: 0xc0010115 data 0x0
Aug 26 09:54:39 Tower kernel: SVM: kvm [21606]: vcpu6, guest rIP: 0xfffff853d6ef22f4 unimplemented wrmsr: 0xc0010115 data 0x0
Aug 26 09:54:39 Tower kernel: SVM: kvm [21606]: vcpu7, guest rIP: 0xfffff853d6ef22f4 unimplemented wrmsr: 0xc0010115 data 0x0
Aug 26 09:54:39 Tower kernel: SVM: kvm [21606]: vcpu8, guest rIP: 0xfffff853d6ef22f4 unimplemented wrmsr: 0xc0010115 data 0x0
Aug 26 09:54:39 Tower kernel: SVM: kvm [21606]: vcpu9, guest rIP: 0xfffff853d6ef22f4 unimplemented wrmsr: 0xc0010115 data 0x0

Hi.

On both of my laptop and desktop machine, the cachy-5.8-r7 causes system freeze under heavy load e.g. compiling. Reverting the change of reset_lifetime at hamadmarri/linux@d459869 seems to fix the problem on my system.

Not sure whether it is relevant, I am using the voluntary preemption with the autogroup enabled.

Regards,
Raymond

Hi @hamadmarri

I just saw your new CacULE scheduler. There is a small bug in the patch that it is still using #ifdef CONFIG_CACHY_SCHED in the sysctl.c file and therefore the interactivity factor is not tunable via sysctl.

Hello Hamad, could you patch cachy-sched for Kernel 5.6 ?

I've been experiencing these hangs (where everything freezes for like 5 secs) when playing some games on wine that usually uses a lot of the CPU, sometimes when watching some videos.

To be sure that was cacule patch and nothing else I tested with the mainline arch kernel (no hangs). As I have some patches applied at my kernel I tried compiling it without the cacule patch (also no hangs). And then tried applying the cacule again and the hangs comes back.

I'm not quite sure. But I think that the commit that introduced it is the 06cb3974.

I didn't tried reverting the commit to test, only tested with these:

cacule-patch-with-hangs.txt - patch where hangs happens

cacule-without-hangs.txt - and without the hangs

But if needed I can try bisecting later to see exactly which commit causes it.

Hi @hamadmarri

I got the following error with the latest CacULE patch when compiling with CONFIG_SCHED_DEBUG enabled:

kernel/sched/fair.c:748:9: error: incompatible pointer types returning 'struct cacule_node *' from a function with result type 'struct sched_entity *'

Should line 748 be return se_of(cfs_rq->head);?

Hello! Not sure if it was problem of cacule. Using 5.10.1 xanmod with cacule.
So I had running Itellij Idea, Java project, Firefox with hundreds of tabs and a youtube playing. All ram and swap were occupied, but it was all great until it wasn't. Suddenly everything just freezed. earlyoom did not not work, even magic button did not responce.
Can i do smth to figure out was it cacule problem or not?
Thank you.

Hi.

When I tried to compile the source code on my 32-bit Raspberry Pi with clang compiler, I got the error that the symbol __aeabi_uldivmod was undefined. By a quick Google search it seems to be due to the divisions (https://stackoverflow.com/questions/25623956/aeabi-ldivmod-undefined-when-compiling-kernel-module). I am not sure whether compiling with gcc would return the same error.

By the way, the performance of your scheduler is really impressive on my desktop machines. Thank you for your great work!

Regards,
Raymond

Hello @hamadmarri

with the latest patches, following compile error happens.

kernel/sched/fair.c:7225:15: error: implicit declaration of function 'wake_affine' [-Werror,-Wimplicit-function-declaration]
                                new_cpu = wake_affine(tmp, p, cpu, prev_cpu, sync);

edit:
seems to happen only with the rdb patch on top of cacule

Hi, if running this program can it damage my CPU?

I observe the following warning happening shortly after booting linux 5.12.11 with CacULE v5.12-r2 (NO_HZ_FULL) :

WARNING: CPU: 0 PID: 227 at kernel/sched/core.c:4637 sched_tick_remote+0x123/0x180
Modules linked in: uas usb_storage iwlmvm nls_iso8859_1 vfat fat mac80211 intel_rapl_msr intel_rapl_common kvm_amd kvm libarc4 snd_hda_codec_realtek iwlwifi snd_hda_codec_generic ledtrig_audio snd_usb_audio crct10dif_pclmul crc32_pclmul snd_hda_intel ghash_clmulni_intel aesni_intel cfg80211 snd_intel_dspcfg snd_hda_codec crypto_simd cryptd igb rapl snd_usbmidi_lib snd_rawmidi snd_seq_device i2c_piix4 snd_hwdep snd_hda_core pcspkr ccp dca zenpower(OE) rfkill rng_core gpio_amdpt gpio_generic pinctrl_amd acpi_cpufreq mac_hid wmi_bmof mxm_wmi vendor_reset(OE) pkcs8_key_parser i2c_dev ledtrig_timer it87(OE) hwmon_vid ee1004 snd_aloop snd_pcm snd_timer snd soundcore v4l2loopback_dc(OE) videodev mc sg crypto_user asus_wmi_sensors(OE) wmi fuse ip_tables x_tables ext4 crc32c_generic crc16 mbcache jbd2 amdgpu crc32c_intel xhci_pci xhci_pci_renesas drm_ttm_helper ttm gpu_sched i2c_algo_bit drm_kms_helper syscopyarea sysfillrect sysimgblt fb_sys_fops cec drm agpgart vfio_pci irqbypass
 vfio_virqfd vfio_iommu_type1 vfio
CPU: 0 PID: 227 Comm: kworker/u64:12 Tainted: G           OE     5.12.11-168-tkg-cacule #1
Hardware name: System manufacturer System Product Name/CROSSHAIR VI HERO, BIOS 7901 07/31/2020
Workqueue: events_unbound sched_tick_remote
RIP: 0010:sched_tick_remote+0x123/0x180
Code: 00 00 41 5d e9 4e b1 fe ff 83 bd 18 0a 00 00 01 76 46 48 8b 85 40 0a 00 00 49 2b 85 20 01 00 00 ba 00 5e d0 b2 48 39 d0 76 90 <0f> 0b eb 8c 0f 0b 5b 5d 41 5c 41 5d c3 89 c2 e9 fd fe ff ff 48 c7
RSP: 0018:ffffac6b80947e68 EFLAGS: 00010082
RAX: fffffffffd9fac54 RBX: 0000000000000008 RCX: ffff8fc28ea00000
RDX: 00000000b2d05e00 RSI: 00000000239f5376 RDI: 0000000000000008
RBP: ffff8fc28ea2c640 R08: 00000000c127f591 R09: 000000000000000f
R10: 000000000000000f R11: fefefefefefefeff R12: ffff8fc28ea31688
R13: ffff8fbf8fc68000 R14: 0000000000000000 R15: 0000000000000000
FS:  0000000000000000(0000) GS:ffff8fc28e800000(0000) knlGS:0000000000000000
CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
CR2: 00007fb1a6874000 CR3: 00000001061b2000 CR4: 0000000000350ef0
Call Trace:
 process_one_work+0x217/0x3e0
 worker_thread+0x4d/0x3d0
 ? process_one_work+0x3e0/0x3e0
 kthread+0x134/0x160
 ? kthread_associate_blkcg+0xc0/0xc0
 ret_from_fork+0x22/0x30

Hello Hamad
I noticed that _pick_last_entity returns cfs_rq->head. Is this intentional or it should be "cfs_rq->last"?

https://github.com/hamadmarri/cachy-sched/blob/9f0070f36db1bbbf8bdfd83534ef070ccc1135bb/patches/cachy-5.8.patch#L229

Hi,

I copy the 5.8 patch in my kernel 5.8.3 root folder and run patch -p1
everything ok but one chunk rejected. here it is:

-- Makefile 2020-08-04 01:04:51.327366223 +1000
+++ linux-5.8-cachy/Makefile 2020-08-04 00:13:59.710682597 +1000
@@ -2,8 +2,8 @@
VERSION = 5
PATCHLEVEL = 8
SUBLEVEL = 0
-EXTRAVERSION =
-NAME = Kleptomaniac Octopus
+EXTRAVERSION = -cachy
+NAME = Cachy

DOCUMENTATION

To see a list of typical targets execute "make help"

Thanks

I tried few latest version (5.4-r7 and and 5.8-r8). They both worked well until I started kernel compilation.5.8-r8 is probably better but I still have sound skips on Youtube music (poorly optimized web app to be honest). With CFS UI slows down but rarely has "xruns". With Cachy UI responsiveness seem better but at this point it's not suitable for "realtime" applications.
It's not necesseraly has to be compilation, sound may interrupt during more generic user tasks such as system updates.

Todo:

1. Full support for cgroups, fair groups, autogroup
2. Variable time slice instead of preempt every tick
   Any suggestions are appreciated

Some alternative schedulers have " yield_type" tunable
From MuQSS description:

This determines what type of yield calls to sched_yield will perform.
 0: No yield.
 1: Yield only to better priority/deadline tasks. (default)
 2: Expire timeslice and recalculate deadline.

From "Project C" (BMQ/PDS) description:

0 - No yield.
1 - Deboost and requeue task. (default)
2 - Set run queue skip task.

I guess "0" is a questionable value (especially with BMQ where my system with a single core and lowest frequency could stuck) but "1" is fine.

So the question is how to implement it with CFS.

In kernel/sched/core.c there's such part
static void do_sched_yield(void)

{
	struct rq_flags rf;
	struct rq *rq;

	rq = this_rq_lock_irq(&rf);

	schedstat_inc(rq->yld_count);
	current->sched_class->yield_task(rq);

	preempt_disable();
	rq_unlock_irq(rq, &rf);
	sched_preempt_enable_no_resched();

	schedule();
}

With "yield_type=0" MuQSS and PrjC put "return" before "rq = this_rq_lock_irq(&rf);"

static void do_sched_yield(void)
{
	struct rq *rq;
	struct rq_flags rf;

	if (!sched_yield_type)
		return;

	rq = this_rq_lock_irq(&rf);

But for "current->sched_class->yield_task(rq);" they have their own code which they use for "yield_type=2"
So is it it safe to just comment
current->sched_class->yield_task(rq);
to get something similar to "yield_type=1" for CFS?

Issue when applying rdb-5.13.patch with cacule-5.13.patch.

kevin@archlinux-portable ~/D/linux-5.13.7> patch -Np1 < ../cacule-5.13.patch
patching file Documentation/admin-guide/sysctl/kernel.rst
patching file Documentation/scheduler/sched-CacULE.rst
patching file include/linux/sched.h
patching file include/linux/sched/sysctl.h
patching file init/Kconfig
patching file kernel/Kconfig.hz
patching file kernel/sched/core.c
patching file kernel/sched/debug.c
patching file kernel/sched/fair.c
patching file kernel/sched/sched.h
patching file kernel/sysctl.c
kevin@archlinux-portable ~/D/linux-5.13.7> patch -Np1 < ../rdb-5.13.patch
patching file init/Kconfig
patching file kernel/sched/core.c
patching file kernel/sched/fair.c
Hunk #8 FAILED at 4936.
Hunk #9 succeeded at 5171 (offset -4 lines).
Hunk #10 succeeded at 5251 (offset -4 lines).
Hunk #11 succeeded at 5338 (offset -4 lines).
Hunk #12 succeeded at 5791 (offset -4 lines).
Hunk #13 succeeded at 6039 (offset -4 lines).
Hunk #14 succeeded at 6092 (offset -4 lines).
Hunk #15 succeeded at 7621 with fuzz 2 (offset -4 lines).
Hunk #16 succeeded at 7663 (offset 1 line).
Hunk #17 succeeded at 7973 (offset 1 line).
Hunk #18 succeeded at 8395 (offset 1 line).
Hunk #19 succeeded at 8445 (offset 1 line).
Hunk #20 succeeded at 8471 (offset 1 line).
Hunk #21 succeeded at 8562 (offset 1 line).
Hunk #22 succeeded at 8574 (offset 1 line).
Hunk #23 succeeded at 8582 (offset 1 line).
Hunk #24 succeeded at 8601 (offset 1 line).
Hunk #25 succeeded at 9705 (offset 1 line).
Hunk #26 succeeded at 9974 (offset 1 line).
Hunk #27 succeeded at 10011 (offset 1 line).
Hunk #28 succeeded at 10344 (offset 1 line).
Hunk #29 succeeded at 10383 (offset 1 line).
Hunk #30 succeeded at 10469 (offset 1 line).
Hunk #31 succeeded at 10480 (offset 1 line).
Hunk #32 succeeded at 10573 (offset 1 line).
Hunk #33 succeeded at 10607 (offset 1 line).
Hunk #34 succeeded at 10758 (offset 1 line).
Hunk #35 succeeded at 10879 (offset 1 line).
Hunk #36 succeeded at 10959 (offset 1 line).
Hunk #37 succeeded at 10989 (offset 1 line).
Hunk #38 succeeded at 11010 (offset 1 line).
Hunk #39 succeeded at 11060 (offset 1 line).
Hunk #40 succeeded at 11069 (offset 1 line).
Hunk #41 succeeded at 11203 (offset 1 line).
Hunk #42 succeeded at 11460 (offset 1 line).
Hunk #43 succeeded at 12308 (offset 1 line).
1 out of 43 hunks FAILED -- saving rejects to file kernel/sched/fair.c.rej
patching file kernel/sched/idle.c
patching file kernel/sched/sched.h

here the .rej file
fair.c.rej.txt

docker : mountpoint for cpu not found.

Hello @hamadmarri
First of all, thanks for your work!
I believe it's very important that Cachy is built on top of mainline scheduler. CFS shows comparable performance with MuQSS and BMQ, usable with RT application etc. The main problem is multitasking under heavy load. MuQSS really shined in this aspect but seems like it's dying. Also, just like BMQ it misses support for modern mainline features (schedutil/uclamp, nohz_full, cgroups). So if it's possible to achieve similar results with CFS, it looks like the best choice.
So I have a few questions:

1. Cachy looks like a lighter copy of CFS. Is it possible to have some lighter patch for CFS which adds HRRN policy? I'm personally fine with CFS "bloat". More important for me is if patch would survive until the kernel lifecycle ends.
2. I'm trying to stick with Ubuntu kernels and luckily this time for LTS we have good LTS kernel version 5.4. Next Ubuntu version will probably have kernel 5.8 but sadly it has major regression in Intel graphics performance. As Cachy now is more stable and feature-complete, do you plan to extend support to LTS kernel versions?

Thanks!

Maintainers of tweaked kernels change a lot of settings in config. The most noticeable tweak is CONFIG_HZ (upstream x86 values: 1000, 300, 250, 100; addition upstream ARM values: 500, 200). And Cachy-ies description even mentions

A task gets preempted in every tick if any task has higher HRRN. If the clock ticks in 250HZ (i.e. CONFIG_HZ_250=y) then a task runs for 4 milliseconds and then got preempted if there are other tasks in the runqueue and if any task has higher HRRN.

That makes some values questionable (like 300HZ (because with 1000/300 we can't get exact value); 1000HZ or even 500HZ because timer for preemption seem too low). Can we consider 250HZ as the recommended tick rate for Cachy?

Also I'd like to see opinion about CONFIG_PREEMPT and NO_HZ_FULL. The first one is popular among tweaked kernels. NO_HZ is already adopted by some distros but it's not recommended for MuQSS.

Thanks,

Can I use the 5.9-r8 patch with any 5.9.x kernel release?

After doing patch -p1 < rdb.patch to 5.13.13-xanmod1-cacule, and trying to compile with make -j7 bindeb-pkg like I normally do to make .debs, I get these errors:

kernel/sched/fair.c: At top level:
kernel/sched/fair.c:11591:2: error: #else after #else
11591 | #else
      |  ^~~~
kernel/sched/fair.c:11255: error: the conditional began here
11255 | #ifdef CONFIG_CACULE_RDB
      |
kernel/sched/fair.c:12760:16: error: ‘rq_online_fair’ undeclared here (not in a function)
12760 |  .rq_online  = rq_online_fair,
      |                ^~~~~~~~~~~~~~
  CC      fs/verity/hash_algs.o
kernel/sched/fair.c:12761:17: error: ‘rq_offline_fair’ undeclared here (not in a function)
12761 |  .rq_offline  = rq_offline_fair,
      |                 ^~~~~~~~~~~~~~~

is it possible for sysctl variables to be calculated dynamically based on current context (e.g. cpu load, num of running threads, priority distribution, etc accounting)? For

• squeeze the max perf out
• user (non-geek) friendly