Egy Rust-ban írt Linux scheduler bizonyos workload-okban lenyomhatja az alapértelmezett scheduler-t

Kernel

Például számítógépes játékoknál FPS-ben. Az overhead-ek (pl. hogy userland-ben fut) ellenére. Videó demó:

 

scx_rustland (https://github.com/sched-ext/scx/tree...) is a Linux scheduler written in Rust that runs in user-space.

The scheduler uses sched-ext (https://github.com/sched-ext/sched_ext): a Linux kernel feature that allows to implement schedulers in BPF and load them dynamically at run-time to replace the default Linux scheduler.

This demo shows that, despite the overhead of running a scheduler in user-space, we can still obtain interesting results and, in this particular case, even outperform the default Linux scheduler in terms of application responsiveness (fps), while a CPU intensive workload (parallel kernel build) is running in the background. Disclaimer: for this demo I'm using an additional patch that adds a "time slice penalty" to new short-lived tasks (that I don't think it's a good idea in general, but in this particular use case it seems quite useful). The point here is just to prove that conducting experiments like this is really easy and safe, given that we are in user-space, and it's all Rust!

Részletek itt.

( Vamp | 2024. 01. 21., v – 12:08 )

Más téma de:

 

A freerdpt (pontosabban az rdp protokollt) is elkezdték újra imlementalni rust alatt. Meg nem próbáltam de videók alapján impressziv a teljesítménye...

 https://github.com/Devolutions/IronRDP

Amúgy ilyenkor elgondolkodok hogy azért lesz jobb mert a nyelv hatékonyabb vagy mert tisztább/rendezettebb a kód a frissessege miatt?

Az IronRDP egy régi, FreeRDP-től független projekt, bár úgy látom mostanában kezdtek újra komolyabban foglalkozni vele. A FreeRDP kódja tiszta, jól szervezett, objektum orientált C kód, nem gondolom hogy a kód rendezettségi szintje komolyabb akadálya lenne annak hogy hatékony legyen. Pusztán a nyelv hatékonyságnak nincs különösebb jelentősége, ami miatt elméletileg lehet gyorsabb a Rust mint a C, az a strict aliasing és a generikus kódok inlineolhatósága, de egyikről sem gondolnám hogy látványos különbséghez vezetne. Ha van látványos különbség, az az implementált algoritmusok miatt lesz. A Rust kifejezőbb típusrendszere segít, hogy egy új algoritmust implementálj. A csomagkezelője pedig segít hogy a mások által implementált algoritmusokat a saját projektedben kipróbálj és használj.

scx-rustland esetében pedig a Rustnak ha bármi relevanciája van azon kívül hogy a fejlesztője Rustban akart dolgozni, az az eBPF támogatás, ami a Rustos ökoszisztémában egy már kitaposott út, tehát amikor van egy új ötleted és a karácsonyi szünetben össze akarsz dobni egy process schedulert, akkor könnyen meg tudod csinálni. Ha bármilyen komoly előnye van, az algoritmikus különbségből fakad, nem azért mert gyorsabb a kód, hiszen a gyári Rustos hashmap-et használja a taskokhoz anélkül hogy kicserélné az alapértelmezetten használt secure hash functiont egy gyors hashre.

objektum orientált C kód

IMHO itt lesz a kutya elasva. Amikor repkednek a ** -ok, minden function ASSERT() -ekkel kezdodik, konnyen a hatekonysag rovasara megy. Nem tudom, itt is ez-e a helyzet, csak roviden kukkantottam meg a kodjat github-on, de lattam mar nagy C kodbazist, ahol szinten probaltak valami OO elveket belevinni, de tragya lett, es a java replacement jocskan ravert. Mert ott a rendes OO es a kapasbol magasabb szintu lib-ek miatt, nomeg a GC miatti szabadsag miatt rendesen ossze tudtuk reszelni a kodot, a funkcionalitasra koncentralva.

Nincs. Valamelyik előadásában mondta is, hogy a virtme-ng-init projektjét azért kezdte, mert meg akarta tanulni a Rust-ot (ezt fél éve láttam kb. egy korábbi előadásában, twitteren és githubon igyekeztem segíteni a virtme-ng projektet) és gondolom ez is egy gyakorló projekt. A scheduler userspace része van egyébként Rust-ban írva, ez tipikusan control plane, a BPF rész C-ben van írva, ami kernel szinten fut. Magyarán a teljesítménynövekménynek semmi köze a Rust-hoz, az ebben megírt rész mindössze felparaméterezi és betölti a C-ben írt és BPF-re fordított részét az ütemezőnek.

nem hinnem en se hogy a rust miatt hatekonyabb. az rdp egy eleg bonyi protokoll, sok opcionalis feature-el, codecekkel stb, ha ezekbol tobbet implementalnak az is sokat segit. a masik a halozat kezeles, mivel eleg nagy az i/o sok kis csomaggal, itt jol johet az async io. nem tudom a freerdp-ben van-e async io hasznalva, regebben nem volt ez annyira divat.

de siman lehet hogy csak a RemoteFX support miatt jobb.

( asch v | 2024. 01. 21., v – 15:49 )

Szerkesztve: 2024. 01. 21., v – 15:50

A scheduling szerintem olyan téma, hogy nincsen egyetlen optimális megoldása, ezért különböző terhelésekre mindig lehet optimalizálni egyet. Szerintem matematikailag ha van egy adott feladat és célfüggvény, akkor ahhoz létezik egy vagy több optimális ütemezés. Például ha a kernelfordítás közben a játék FPS-re optimalizálunk, akkor én úgy ütemezném a szálakat, hogy a kernelfordítás szépen várja meg a játszást :-). De nincsen általánosságban optimális ütemező.

Ez tipikusan egy hülye terhelési profil, mert nem tudnám megmondani mi a célfüggvény. Mennyit szabad a kernelből beáldozni az FPS érdekében? Például a make-et úgy szokás indítani, hogy annyi szálon induljon el, amennyi csak van a proceszorban. De ha játszunk mellette, akkor ezzel lábonlőhetjük magunkat, mert ha több a szál mint a mag, akkor a magoknak folyton szálat kell váltaniuk, és ennek a vége szuboptimális cache használat lesz. Az első tehát, hogy a szálakat érdemes a lehetőségekhez igazítani, úgy használjuk ki legjobban az erőforrásokat. A CS tudjátok, hogy hány szálon fut? Szerintem a legjobb megoldás az lenne, ha fixen leosztanánk a magokat a build és a CS között.

A build szerintem a CPU-t szinte 100%-ban ki tudja használni. Amiért nem, az a háttértárra várakozás. Ha ezen akarnék optimalizálni - és volt már ilyen feladat... - azon gondolkodnék el, hogy a szükséges háttértár műveleteket prediktálnám és előre behúznám azt, ami éppen jönni fog. Vagy ha befér a RAM-ba, akkor az egész kernelfát behúznám, és akkor az ütemezés unalmassá válik, mert minden szál folyton ütemezhető, hiszen mire várnának, ha nem IO-ra?

Hasonló indokok miatt nem került be végül (egyelőre?) a sched_ext mainlineba. Attól félnek, hogy mindenki megírja házon belül az ütemezőjét az adott workloadra, ami lehet tetszőlegesen specifikus és innentől senkit nem érdekel majd, hogy az EEVDF meg a core része amúgy jó-e vagy sem. Nem értek hozzá, szerintem nem lenne tragikus a helyzet de a scheduler karbantartója biztosan alaposan átgondolta ezt a döntést.

Akkor ha jól látom, ez a sched_ext ugyanaz az állatfaj, mint a FUSE. Egy jól indokolhatóan kernel szinten implementált szolgáltatást (fájlok turkálása) kiszervezünk user-space-be. Annak is mi lett az eredménye: boldog-boldogtalan FUSE-alapon implementál fájlrendszernek látszó tárgyat (trágyát?), és a világ megelégedetten használja. Lásd FUSE alapon tömörítvények elérése, titkosítás, fájlok távoli elérése, stb. És ez jó. És akkor sem írják át kernel-space-be, amikor esetleg jó lenne - lásd NTFS. Ez meg nem jó.

tl;dr
Egy-két mondatban leírnátok, hogy lehet ellopni egy bitcoin-t?

Igen, a FUSE az ugyan ez a megközelítés és kiállta az idő próbáját. Engem meglep, mennyire ellenségesen fogadták ezt a sched_ext-et. Ubuntuban egyébként benne van/lesz a sched_ext, az out-of-tree ágat húzzák maguk után. Ha minden disztró hozná magával (nem valami esztétikus) akkor végülis mindegy mainlineban benne-e vagy sem.

( falu v | 2024. 01. 21., v – 15:49 )

Most akkor ez a rust vagy a scheduler algoritmus érdeme? Szerintem minden nyelven lehet jó és rossz kódot is írni.

[Falu.Me]==>[-][□][X]

Még csak az algoritmusnak sem. Belerakott egy szándékos "penalty"-t (gondolom ez prioritáscsökkentést akar jelenteni) a rövid ideig futó folyamatokra. És láss csodát... a kernelfordítás melletti realtime játék hirtelen sokkal jobban fut. Gondolom cserébe a kernelfordítás meg jóval hosszabb lett...

A cikk lényege rosszul van megfogva. Ez az egész egy kb hello world példa arra, hogy lehet eBPF-fel userspace-ben futó ütemezőt írni. Amúgy ez le is van írva az eredeti szövegben világosan, csak mindenki arra koncentrál, hogy "wow gyorsabb lett".

Régóta vágyok én, az androidok mezonkincsére már!

Azért erre koncentrálunk, mert a srác literálisan a legelső tweetjében ezt emelte ki: nemcsak, hogy működik, hanem még gyorsabb is:

I'm pretty shocked to see that it doesn't just work, but it can even outperform the default Linux scheduler (EEVDF) with certain workloads

Ha neki ez a kiemelendő dolog, akkor hadd szedjük már szét ízekre ezt az állítását.

Megfordítom akkor a problémát.

Az hogy valaki random tweetel (vagy X-el? újabban már így kell mondani?) lelkesen valamiről az egy dolog. Bárki megteheti, kb bármiről. Nem kell tudományos folyóiratcikk szintet megütnie, belefér, hogy valamelyest clickbait felütéssel kezd. A mostani még viszonylag jó példa, mert legalább a szövegtörzsben benne van, hogy valójában mi is volt a cél ezzel.

Az hogy utána ebből cikket ír valaki az egy másik dolog. Picit más szerintem az elvárás egy szakmai cikkel szemben a lényeg kiemelése szempontjából. (Btw igazából örülök, hogy egyáltalán szakmai cikk, nem pedig yet another EV fikázás, bulvár vagy celebes hír)

Régóta vágyok én, az androidok mezonkincsére már!

Az hogy valaki random tweetel (vagy X-el? újabban már így kell mondani?) lelkesen valamiről az egy dolog.

Na de ez a valaki pont az volt, aki ezt az ütemezőt megcsinálta. Ha ő az ütemezés jóságát emeli ki, és nem a Rust-eBPF toolchaint, akkor miért is ne lehetne erről beszélni?

Illetve hát, ugye azt mondja ő:

and the whole point of this demo was to prove that, despite the overhead of running a scheduler in user-space, we can still achieve interesting performance, while having the advantages of being in user-space

De ha jól értem, az ütemező NEM userspaceben fut, a userspace feladata csak az eBPF kód betöltése a kernelbe, az ütemező továbbra is a kernelben fut.

 

Most akkor mi is van, valaki el tudná mondani?

+1

Én is úgy értem, hogy az eBPF valami virtuális programozási nyelv, aminek pont az a lényege, hogy kernek kontextusban futtatható "biztonságosan". Az a trükk, hogy az ütemező nem egy konkrét ilyen programot injektál, hanem mindig a következő ütemezési feladatot egy új virtuális program segítségével hajtja végre, tehát ezekből mindig újakat indít el a kernelben?

Szerintem amit ő kiemel, hogy a userspace-ben futó ütemezőnek nincs akkora overheadje, hogy használhatatlanul lassú lenne. Hogy sikerült egy konkrét (még ha nagyon speciálisan tuningolt) példával megvernie a kernelen belüli ütemezőt, az neki azért fontos, mert ezzel támasztja alá, hogy nincs nagy overhead.

A rust cargo library-hez (https://docs.rs/scx_utils/latest/scx_utils/) írt dokumentáció szerint:

"... sched_ext scheduler implementations which use Rust for userspace component. This enables implementing hot paths in BPF while offloading colder and more complex operations to userspace Rust code which can be significantly more convenient and powerful."

Vagyis lehetséges kevert megoldást használni, a sebességkritikusabb részeket BPF-ben (kernel módban, de valamelyest sandboxolva) tudja futtatni, de a bonyolultabb dolgokat ki lehet szervezni userspace-be.

A mostani konkrét példa - ha jól értelmezem a szerző postját, a kódot nem rágtam át - az scx_rustland implementációt használta és teljes egészében userspace-be lett kirakva. Ezért volt annyira "meglepő", hogy még így is használható a sebessége.

De mégegyszer, itt nem azon van a hangsúly, hogy csinált egy "jobb ütemezőt" - mert nem csinált. Egy speciális esetre szélsőségesen elhangolt ütemezőt csinált. A lényeg az, hogy ez egy proof-of-concept volt annak alátámasztására, hogy a teljesen userspace ütemező is működőképes és a teljesítménye is használható marad.

Régóta vágyok én, az androidok mezonkincsére már!

Pontosan. A sched_ext ütemezőt David Vernet és Tejun Heo csinálta ami adja az API-t saját ütemező írásához (eBPF-ben) és ezt az API-t használva írt egy saját, speciális workloadhoz szánt ütemezőt ő. De a sched_ext-nek pont ez a célja, hogy a te saját, speciális workloadodra hatékony ütemezőt írhass anélkül, hogy újrafordítsd a kernelt vagy modulokat töltenél be.

( persicsb | 2024. 01. 21., v – 18:53 )

Szerkesztve: 2024. 01. 22., h – 06:54

Nyilván, a gaming speciális workload, ezért van olyan ütemezési algoritmus, ami jobban teljesít. És ez nem a rust érdeme.

mondjuk az viszont emlitesre melto, hogy miert is nincs olyan a mai desktop distro-kban olyan scheduler, ami a desktop/gui/gaming use pattern-t tamogatna. az, ha egy 'gyuttment rust n00b' jobbat csinal gaming workload-ra, eleg jo markere annak, hogy nagyon nem volt optmalis, ami eddig a kernelben volt.

Érdekes módon a grafikus kárytákba bele tudták tenni a game-re optimalizált kártyaprofilt, jelentsen ez bármit is. Nem hiszem, h sokáig fog tartani egy megfelelő heurisztikát és AI ML DL cuccal felvéttezett "training" mode-al felvértezett daemon olyan ütemező profilt rajzoljon DEFINE-okkal a Arch-osoknak, hogy mindenki körbepisili majd és kiteszik user space-be az idomított ütemezőt :)

Lehet (biztos).offtopic már, de az agy is ezt csinálja. Évmilliók (?) alatt kialakult pár séma , amivel penalty-re tesz megszakításokat adrenalin, melatoin, endorfin, dopamin és egyéb prioritáskezelés , háttérbe rakom és csak "áramot" kap. Alvás, emésztés, menekülés vadászat, szex, maga a koncentráció, pánik :-) Ezt szokás alkohollal és/vagy egyéb dolgokkal befolyásolni, sokszor sajnos ujrafordítva pár séma paramétert. :-)

Hasonlót fogunk majd mi is látni, ha lenne a processzekről valamilyen ujjlenyomat h mit csinál, mire való valójában, és x napnyi mintavételezés után jöhet a személyre/gépre userre szabott microcode a kernellel segítve.

pl csak Rust-ban irt pure notepad nem kell féljen az OOM killertől és a bluethooth se kelljen zizegjen neki.

az intel itune hasonlót ígért, de lehet sokat ittam. :)

Szerintem játékokhoz "ami a csövön kifér" ütemező kell: minden taszknak be kell fejeződni a következő frame rajzolásáig, egyéb taszkok viszont nincsenek, vagy ha vannak (pl a táj hamarosan láthatóvá váló részének betöltése) akkor a többi magon. Én legalábbis így csinálnám, a hozzá való ütemező pedig simán annyi, hogy a játék szálak bazi nagy prioritással fussanak.

Egyébként megmozgatta ez a fantáziámat, mert a játszós gépemen van egy rakás mag, és mégis meg tud akadni a frame. Meg lehet azt csinálni Linuxszal, hogy egy program száljait fixen magokhoz rendelem, és ugyanakkor minden mást kizárok onnét? Tehát mondjuk 8 magos gép esetén minden más osztozzon mondjuk 2 magon, a játék meg kapja meg teljesen a 6 magot? Ráadásul úgy, hogy lássa, hogy 6-ba kell beleférnie, tehát ne is indítson többet, ha olyan játékról van szó, ami képes a szálak számát változtatni.

( hajbazer v | 2024. 01. 22., h – 00:05 )

A marketingasztalra is csak általában bizonyos aspektusok férnek fel, az összkép soha.

Arra talán elég lesz, hogy babzsákfejlesztőék a fél kernelt újra akarják írni Rust-ban, ami a végén sokkal nagyobb bloat lesz, de legalább már van mivel reklámozni.

( SPYFF v | 2024. 06. 13., cs – 07:36 )

Szerkesztve: 2024. 06. 13., cs – 07:38

Linus felülbírálva Peter Zijlstra-t mergeli 6.11-be a sched_ext patchsetet. A BPF-el userspaceből programozható scheduler innentől a mainline része.

 

I honestly see no reason to delay this any more. This whole patchset was the major (private) discussion at last year's kernel maintainer summit, and I don't find any value in having the same discussion (whether off-list or as an actual event) at the upcoming maintainer summit one year later, so to make any kind of sane progress, my current plan is to merge this for 6.11.

At least that way, we're making progress, and the discussion at KS 2024 can be about my mental acuity - or lack thereof - rather than about rehashing the same thing that clearly made no progress last year.

I've never been a huge believer in trying to make everybody happy with code that is out of tree - we're better off working together on it in-tree.

And using the "in order to accept this, some other thing has to be fixed first" argument doesn't really work well either (and _that_ has been discussed for over a decade at various maintainer summits).

Maybe the people who have concerns about this can work on those concerns when it's in-tree.

I'm also not a believer in the argument that has been used (multiple times) that the BPF scheduler would keep people from participating in scheduler development. I personally think the main thing that keeps people from participating is too high barriers to participation.

Anyway, this is the heads-up to Tejun to please just send me a pull request for the next merge window.

And for everybody else as a "It's happening" heads-up.

[ Please just mentally insert the "IT'S HAPPENING" meme gif here - because if I actually were to include it here, lkml would just reject this email. Sometimes the anti-html rules don't work in our favor ].

              Linus