Jaderné noviny - 1. 9. 2016: Pohled do hlavy vývojářky Coccinelle

11. 9. 2016 | Redakce | Jaderné noviny | 3254×

Stav vydání jádra. Pohled do hlavy vývojářky Coccinelle.

Stav vydání jádra

Současný vývojový kernel je 4.8-rc4, vydaný 28. srpna. „Vše vypadá normálně, navíc to bylo klidnější než rc3, takže snad už jsme ve fázi, kdy se vše ‚uklidňuje‘. I když vzhledem k obvyklému časovému kolísání (správci rozkládají své žádosti o začlenění různě) je zatím těžké předvídat nějaký trend.“

Pro informace o známých regresích ve vydání 4.8 viz tento report.

Stabilní aktualizace: tento týden žádné nebyly vydány.

Pohled do hlavy vývojářky Coccinelle

Julia Lawallová, vývojářka Coccinelle, začala svou přednášku na Linux Security Summitu v Torontu konstatováním, že toho o bezpečnosti vlastně moc neví. Ale nástroj, který vyvinula, a patche, které tento nástroj generoval, zřejmě v jádře opravily v kernelu mnoho vzorců chyb, z nichž některé měly bezpečnostní důsledky. Lawallová ve svém příspěvku pro zhruba 90 účastníků vysvětlila, co se používáním nástroje naučila, a představila jeho schopnosti.

Principem Coccinelle je „najít jednou, opravit všude“. Jedná se o statický analyzátor, který hledá vzory v kódu v jazyce C. Takže jakmile někdo narazí na problém ve velkém kusu kódu, jde použít Coccinelle k nalezení dalších případů stejné chyby. Navíc je možné aplikovat transformace kódu k vytvoření patchů pro opravu ostatních výskytů chyby.

Sémantické patche

Coccinelle je uživatelsky skriptovatelná pomocí „sémantických patchů“, které jsou založeny na zápisu, který vývojáři znají. V ideálním případě, řekla Julia, se toho lidé k tomu, aby mohli tento nástroj používat, nebudou muset naučit moc. Od počátku bylo cílem, aby nástroj byl přístupný vývojářům v jazyce C.

Lawallová ukázala klasický případ využití Coccinelle. Commit Al Vira („wmi: (!x & y) znovu v akci“) ukazoval na opakující se problém s testy v podobě

if (!block->flags & ACPI_WMI_METHOD)

Správnou opravou je uzávorkování výrazu:

if (!(block->flags & ACPI_WMI_METHOD))

Problém je v tom, že operátor logické negace (!) se váže mnohem těsněji než bitová konjunkce (&), což vede k chybnému testu. Jak upozorňuje komentář, je jasné, že se tento problém objevuje s určitou frekvencí, ale použít grep k jeho nalezení je obtížné. V jádře se nachází příliš mnoho symbolů ! a & a test se může protáhnout na několik řádek, což může znesnadnit vyhledávání.

Jednoduchý sémantický patch Coccinelle ale najde (a opraví pomocí generovaného patche) problémy tohoto druhu:

@@
expression E;
constant C;
@@
- !E & C
+ !(E & C)

Lawallová poté ukázala příklad stejného problému (přes dva řádky) jinde v jádře a změny kódu vedoucí k opravě této chyby.

Historie

Coccinelle začala vznikat v roce 2004, kdy měla Lawallová volno. Bylo to zrovna v době vydání jádra 2.6, ale většina ovladačů tou dobou stále cílila na jádro 2.4. Lawallová chtěla automatizovat port těchto ovladačů na 2.6, ale ukázalo se, že „je to nereálné.“ Nicméně některé změny, které nazvala „vedlejší evoluce“, mohly být provedeny automaticky, jako například změny volacích funkcí, jako je přidávání nových parametrů.

K vyřešení problému vedlejší evoluce vznikl nástroj Coccinelle, angažovala se v tom čtveřice, v níž figurovala Lawallová, na univerzitě v Kodani mezi roky 2005 a 2007. První patche založené na výstupu Coccinelle byly k začlenění do jádra podány v roce 2007. Týkaly se míst, ve kterých bylo volání kmalloc() následováno memset(), a nahrazovaly tato volání jedním voláním kzalloc(). Následovala publikace dvou článků v letech 2008 a 2011.

V současné době se na vývoji Coccinelle podílí Lawallová společně s dalšími třemi lidmi z Inrie. „Nástroj je kompletně implementován v OCamlu, což může podstatně zmenšit základnu přispěvatelů,“ pokračovala za smíchu části publika. Na druhou stranu to redukuje počet patchů, které je potřeba zkontrolovat.

Nástroj měl na jádro docela velký dopad od roku 2007, kdy byly zveřejněny první patche. Aktuálně Coccinelle zmiňuje přes 4500 patchů v jádře, z toho 3000 pochází od více než 500 vývojářů mimo projekt Coccinelle samotný. V jádře je také 56 sémantických patchů, které se používají jako testy (dostupné skrze make coccicheck). Více sémantických patchů týkajících se Linuxu je možné najít na coccinellery.org.

Sémantické patche jsou v jádře určeny k zachycování různých typů chyb, které mohou proniknout na povrch. Existují testy pro obecné chyby v C (např. testování nezáporných číselných proměnných na hodnoty menší než nula, popř. dereference ukazatele nikam), obecné linuxové problémy (dvojité zámky nebo použití indexu, přes který se iteruje, mimo cyklus), chyby závislé na API (použití free() na oblasti alokované devm), modernizace API (použití kmemdup() namísto kmaloc() a memcpy()). Příspěvky nových sémantických patchů jsou vítány. Přispěvatelé mohou patch vyrobit sami nebo týmu ukázat vzor, na který má patch cílit.

Použití Coccinelle

Poté Lawallová ukázala některá složitější použití Coccinelle v jádře. Jako první to byla snaha převést ovladače k používání frameworku devm ke správě paměti, aby se zabránilo únikům paměti. Při zavedení (probe) ovladače se často alokuje paměť pomocí kzalloc() a potom se při odebrání (remove) uvolní. Přechod k devm_kzalloc() znamená, že paměť bude nově řídit knihovna devm.

Proces tvoří tři kroky. V prvé řadě je to nalezení názvů funkcí probe a remove. K tomu by šlo použít regulární výraz, což se však „jeví neatraktivní," řekla Lawallová. Ukazatele na funkce se vloží do struktury platform_driver atp., takže jejich jména jde extrahovat pomocí pravidel Coccinelle. Druhým krokem je nalezení definice funkce probe a transformace volání kzalloc() na devm_kzalloc(), přičemž volání kfree() jsou odstraněna ze všech větví, kde se ošetřují chyby. Posledním krokem je odstranění volání kfree() z funkce remove.

Lawallová na tomto sémantickém patchi pracovala v roce 2012 a nakonec podala 39 patchů, které vedly k provedení kýžených změn. Její sémantický patch nabízí více než 170 příležitostí k provedení této změny, ale není možné je aplikovat slepě. Je třeba se odpovědně dívat na generované patche, dodává. Celý proces trvá jen 30 sekund (za použití indexování GLIMPSE), takže problém hledání vzorců převádí na problém kontroly oprav.

Jiné použití Coccinelle je detekce volání na uživatelské úrovni, u kterých by mohlo dojít k blokování kvůli výpadku stránky (např. copy_*_user(), get_user()), pokud byla volána z oblasti chráněné zámkem. Blokování není v oblastech chráněných zámky povoleno, takže tato volání by se z nich neměla provádět. Patch jednoduše hlásil nálezy potenciálně inkriminovaných funkcí mezi spin_lock() (nebo variantami) a spin_unlock(). Běžně zpracovává Coccinelle funkce po jedné, ale při hledání vzorů ve funkcích nebo v souborech se dá použít i iterativně.

Jedna potvrzená chyba byla nalezena v copy_from_user(). Kontrola copy_to_user() našla problém, ale byl u něj komentář „FIXME“, což by mohlo naznačovat, že se k ní vývojář plánoval někdy v budoucnu vrátit. Když se tomu obecenstvo na přednášce zasmálo, řekla Lawallová: „Chápu vaši nedůvěru.“ Tato kontrola našla i falešně pozitivní nález. Poznamenala, že se sémantickými patchi nehodlá dosáhnout dokonalosti, jen se snaží najít něco zajímavého, takže nemá zájem komplikovat sémantické patche do té míry, aby eliminovala falešně pozitivní nálezy. Kontrola get_user() a put_user() našla od každého jeden případ, ale ještě nebyl čas je vyhodnotit.

Další práce spočívala v sémantickém patchi pro přidávání klíčového slova const k některým jaderným strukturám. Lawallová použila postup o čtyřech krocích, z nichž dva jsou manuální. Prvním z nich je identifikace struktur, které obsahují pouze ukazatele na funkce, pomocí Coccinelle. To jsou vhodní, ale ne jediní kandidáti na přidání const. Kromě toho je ochrana těchto struktur před přepsáním důležitá z toho důvodu, aby se zabránilo spuštění kódu v jádře. Ze seznamu takových struktur se některá vybere ručně a pomocí Coccinelle se pak ke každému jejímu použití přidá const. Posledním krokem je sestavit jádro pomocí GCC a ujistit se, že všechno funguje.

Tento proces vyústil v 115 patchů předložených v roce 2015. Lawallové nejde o to, zda dojde k jejich začlenění. Co si pamatuje, tak žádný z nich nebyl zamítnut, ale možná některé nebyly naopak přijaty. Detekce struktur se samými ukazateli na funkce je pomalá – spouští je přes noc – ale přidání const je okamžité.

Ponaučení

Lawallová se za tu dobu naučila některé věci, o které se chtěla podělit. Nejdůležitější je začít s něčím jednoduchým. Sémantické patche v jaderném stromu jsou komplexnější a ne zrovna reprezentativní – nejsou dobré pro první kroky s tímto nástrojem. Začněte s běžným případem, který může skončit falešně pozitivními chybami. Možná dostanete 100 výsledků, které povedou k nalezení dvou chyb. Samozřejmě je možné mít složitější systém, ale je to něco za něco.

Během procesu přechodu na devm bylo například těžké přijít na to, jak se ve funkci remove zbavit toho správného kfree(). Zvolila jednoduché řešení. Prostě předpokládala, že jaderní vývojáři by pro uvolňovanou proměnnou použili stejné jméno, jako pro tu, která se nachází ve funkci probe. Je to „zcela nebezpečné, ale funguje to docela dobře.“ Nejhorší případ by byla falešná negativa – neodstranění kfree(), které by mělo být odstraněno. Takže udělala test, ve kterém použila Coccinelle k odstranění všech volání kfree() ve funkci remove. Ukázalo se, že se jedná o stejnou sadu souborů jako v jejím pravidle, takže „pravděpodobně je pravidlo OK“ a „přímočará metoda byla dostatečně dobrá.“

Sémantické patche by se měly tvořit postupně. Pravidla pro přechod na devm vyústila v 171 souborů, jejichž analýza nějaký čas zabere. Kromě toho devm uvolňuje paměť, kterou spravuje v pořadí LIFO (last in first out), což může způsobit rozdíly. Takže Lawallová přepsala svůj sémantický patch, aby se předešlo jakýmkoli voláním funkcí, které vracejí hodnotu, před kzalloc() ve funkci probe nebo libovolným funkcím remove, kde se cokoliv volá po kfree(). To zmenšilo vzorek na 51 souborů.

Podobně kontrola na blokující funkce v oblasti chráněné zámky produkovala spoustu falešně pozitivních nálezů. Podmínky v kódu mohou způsobit, že status zámku bude při analýze zaznamenán nepřesně. Aby se tomu vyhnula, změnila test, aby vyhledával v místech, kde se blokující volání objevují po uvolnění zámku, a potom se podrobněji podívala na místa, kde se to nedělo.

Poslední rada, kterou předala, se týkala využití informací z jiných nástrojů. Proces přidávání const využíval GCC ke zjištění, zda se po změně dá jádro sestavit. Ale v ideálním případě by existoval způsob, jak uživatele varovat o potenciálně problematických případech. Za tímto účelem možná budete chtít získat informace o strukturách (jsou už některé z nich const, což by mohlo naznačit, že když budou všechny const, mohlo by to fungovat?) a o sestavení jádra s ohledem na příslušnou strukturu (jsou všechny instance struktur v souborech, které jsou obsaženy v sestavení ve stávající konfiguraci?). Tak by mohly být vybrány struktury, které by bylo snazší, nebo naopak složitější změnit a ověřit, aby bylo jasné, čím se zabývat dřív. Tento typ informací se dá shromáždit pomocí programů v Pythonu nebo OCamlu, což může uživatelům pomoci zaměřit se na vhodné kandidáty.

Na závěr Lawallová prohlásila, že tento nástroj je vhodný pro celou řadu různých problémů. Coccinelle je „kompromis mezi správností a úplností, ale v praxi je to užitečný nástroj.“ Vývojáři by udělali jedině dobře, pokud jej přidají do svého arzenálu.

       

Komentáře

[Michal Kubeček]

Docela mne překvapuje, že někdo opravdu napíše

  !x & y

s tímhle mezerováním, pokud tím chce říct, že se negace vztahuje na výsledek &.

V tomto případě bych byl navíc s automatickým opravováním hodně opatrný, protože jakkoli je "!x & y" logický nesmysl, nedivil bych se, kdyby některé výskyty byly ve skutečnosti překlepem v

  !x && y

[chrono]

Hľadajú sa tam ale prípady, keď je y konštanta (takže áno, môže to nájsť aj nevhodný kód, ale takých chybne nájdených miest nebude až tak veľa, aby to pri kontrole spôsobovalo príliš veľa problémov).

[Michal Kubeček]

Aha, jasně, s konstantou to "&&" moc časté nebude, nanejvýš nějaké CONFIG_* IS_ENABLED(). Na druhou stranu tak ale nechytne případy, kdy druhý operand konstatní není.

[Josef Kufner]

Spíš jde o to, že grep to neumí najít, takže seznam pro ruční kontrolu je moc dlouhý.

[Bedňa]

Ideálne by bolo impementovať "no idiot syntax", pretože v Cečku ide napísať nezmyselných konštrukcií kopec a upozorňovať na ich výskyt.

[Josef Kufner]

gcc má nějaká varování, že chce třeba extra závorky kolem přiřazení v ifu.

[Bystroushaak]

Ideálne by bolo impementovať "no idiot syntax", pretože v Cečku ide napísať nezmyselných konštrukcií kopec a upozorňovať na ich výskyt.

Jen jestli by ti pak z C něco zbylo :>

[pc2005]

Tak současný nejmenší turing univerzální "jazyk" je tuším Wolfram (2,3) .

[Bedňa]

Keď som koment odoslal, tak mi tiež dopalo, že nad nadstavbou asembleru je ťažko písať nejakú kontrolu. Takže súhlas.

[Bystroushaak]

Tak kontrola by se určitě dala. Co by bylo ale lepší je třeba nějaká ne-tak-dementně parsovatelná syntaxe a strojově parsovatelné a pochopitelné chybové hlášky. Dneska třeba když chceš generovat z nějakého svého jazyka / projektu C kód, tak to sice funguje, ale nedosahuje to toho potenciálu třeba co do různých transformací a úprav, protože ten jazyk je prostě místama zbytečně komplexní.

[tom]

jakkoli je "!x & y" logický nesmysl

A to jako proc? Co treba todle:

for (i = 30; i > 0; i--) {
  x = function_returning_error_code();
  printf("%s; ", !x << i & report_pass_mask ? "pass" : "----");
}
x = function_returning_error_code();
printf("%s\n", !x & report_pass_mask ? "pass" : "----");

[Michal Kubeček]

1. Bez toho, abyste té funkci aspoň předal číslo testu, to moc smyslu nedává.

2. Abyste tam dostal tu konstrukci, musíte úplně zbytečně vytáhnout jednu iteraci mimo smyčku. Zhoršení čitelnosti, riziko zavlečení chyby, …

3. Stejně křečovité a samoúčelné je použití "!x << i & mask" místo přirozenějšího a čitelnějšího "!x && (mask & BIT(i))"

4. A to nás přivádí k otázce, zda ty testy, na jejichž výsledku nezáleží, vlastně vůbec chceme spouštět. )

[tom]

1. Bez toho, abyste té funkci aspoň předal číslo testu, to moc smyslu nedává.

Treba ta funcke pouziva globalni promenou, jedna se o priklad, nechapu, proc to resite.

2. Abyste tam dostal tu konstrukci, musíte úplně zbytečně vytáhnout jednu iteraci mimo smyčku. Zhoršení čitelnosti, riziko zavlečení chyby, …

Prvni a nebo posledni iterace se vytahuje celkem bezne, protoze byva jina. V existujicim kodu jich najdete spousty, ilustroval jsem to na prikladu odlisneho formatovani posledni hodnoty.

3. Stejně křečovité a samoúčelné je použití "!x << i & mask" místo přirozenějšího a čitelnějšího "!x && (mask & BIT(i))"

Syntakticky i semanticky je to spravne, tudiz to nemuze byt logicky nesmysl a to tu jde. Krecovitost je subjektivni.

4. A to nás přivádí k otázce, zda ty testy, na jejichž výsledku nezáleží, vlastně vůbec chceme spouštět. )

Jedna se o priklad, chtel jsem ho ponechat co nejjednodussi, abych vam usnadnil jeho pochopeni. Bohuzel se mi to nepovedlo.

[Michal Kubeček]

Pokud chcete ukázat příklad, měl by to být takový, u kterého jsem schopen uvěřit, že to někdo příčetný takto opravdu napíše (a bude k tomu mít jiný důvod, než že chce za každou cenu ukázat, že tu konstrukci použít lze). Pokud bude šance, že někdo příčetný takový kód akceptuje, tím lépe. Při nejlepší vůli vaši ukázku za takový příklad považovat nemůžu.

[tom]

Tvrdil jste, ze dana konstrukce je logicky nesmysl, poslal jsem vam priklad, ktery je jak semanticky tak syntakticky spravne, na ilustraci toho, ze nemate pravdu. A clovek to psat ani nemusi, kod generuji i stroje a to je presne misto, kde jsem se s tim setkal.

[lubo]

Nemam prehlad v programovani v jazyku C, tak ma prosim ospravedlnte za krepu otazku, ale to neexistuje IDE (devcpp, eclipse, intelij, visualstudio,...), ktore by zvladlo napriklad ten prechod na nove api a preklopilo by to i drajvre? Osobne si bez funkcii ako premenovat, pridat parameter, prehodit poradie parametrov a podobne moc neviem predstavit spravovat nejaky kod (java/scala) po dlhsiu dobu...

[mimi.vx]

ano .. rika se mu programator, developer nebo vyvojar

 

a ano, tady se nepise o takove samzrejmosti jako je refactoring ..

[Sid]

No tento komentar vyssie by bol zjavne "ozdobou" LKML . Tusim nastal cas aby sa IDE niekomu spustalo iba po predlozeni dokladu o sposobilosti rozmyslat.

[smazáno]

to "java/scala" si uz psal nemusel, to nam bylo jasne po precteni prvni vety :-P

[Pavel Stárek]

Problém je, že u kernelu se velice rychle mění jeho vlastní API a to bohužel i v setinkových verzích. Pamatuji případ, že například Nvidia ovladače šly v pohodě zkompilovat na kernelech 3.0 až 3.18 a pak vyšel kernel 3.19 a už najednou nešly, protože se změnil název jakési funkce v kernelu. Ano, souhlasím s tím, že toto by si měli hlídat hlavně vývojáři Nvidie, ale prostě minimálně u longterm kernelů by API mělo být zachováno po celou dobu životnosti (možná dokonce je, věci okolo jádra moc nesleduji).

[Michal Kubeček]

u kernelu se velice rychle mění jeho vlastní API a to bohužel i v setinkových verzích

To je hlavně hluboké nepochopení toho, co ty verze (ne)znamenají. Přechod mezi 3.19 a 4.0 nebyl (až na rozbití pár neprozíravých skriptů) o nic významnější než třeba právě mezi 3.18 a 3.19.

Ano, souhlasím s tím, že toto by si měli hlídat hlavně vývojáři Nvidie

Každý svého štěstí strůjcem. Když se někdo rozhodne poskytovat closed source out of tree driver a někdo jiný na něj spoléhat, je to jejich volba, ale musejí počítat s následky.

ale prostě minimálně u longterm kernelů by API mělo být zachováno po celou dobu životnosti

Jak to souvisí s tím, jestli se změnilo mezi 3.18 a 3.19?

[Pavel Stárek]

Souvisí to s tím, že by se u lt kernelu nemělo rozbít API například mezi verzí 4.4.18 a 4.4.19, ale jak píšu, nejsem v jádře zase tak kovaný, takže tomu tak třeba je již dnes.

[trekker.dk]

Souvisí to s tím, že by se u lt kernelu nemělo rozbít API například mezi verzí 4.4.18 a 4.4.19

Proč by ne? LT jádro znamená, že aktualizace přinášejí téměř výhradně opravy chyb a že by se jeho nasazením nemělo nic rozbít. "Nic rozbít" se ale - jako vždy - vztahuje pouze na in-tree kód. Pokud někdo používá out-of-tree ovladače, to už je napsáno o dva příspěvky výš...

[Jendа]

ale prostě minimálně u longterm kernelů by API mělo být zachováno po celou dobu životnosti (možná dokonce je, věci okolo jádra moc nesleduji)

No to je. Longterm je třeba 3.14.x. 3.x je normální další verze a 4.0 se od 3.19 neliší nijak víc než 3.19 od 3.18. Už 10 let se na major a minor verze nehraje.

[Ondrej Santiago Zajicek]

No, je trochu matouci pouzivat 'API' pro oznaceni ciste interniho rozhrani. Interni rozhrani se v Linux kernelu obecne meni, (Vnejsi) API zustava stabilni.

[Ladislav Hagara]

Jaderné noviny jsou z 1. 9. O týden později byl zveřejněn Videozáznam přednášky Pohled do hlavy vývojářky Coccinelle.