Sémantické patchování pomocí nástroje Coccinelle

25. 2. 2009 | Jirka Bourek | Programování | 3334×

Všichni jsme to zažili: hledáte nějakou ošklivou chybu a najednou s hrůzou zjistíte, že musíte úplně změnit enormní kus kódu, abyste ji mohli opravit. Spustíte rychlý grep nad základnou kódu a orosíte se: stovky řádků kódu, které je potřeba změnit! A změna je příliš složitá na to, aby se dala udělat skriptem, protože závisí na kontextu, ve kterém je volána, nebo vyžaduje do každého volajícího přidat novou proměnnou.

Originál tohoto článku napsala Valerie Aurora (dříve Henson), vyšel na LWN.net.

To se mi stalo minulý měsíc, když jsem přidávala podporu pro 64bitové souborové systémy do e2fsprogs. Myslela jsem si, že jsem skoro hotová, když jsem zjistila, že potřebuji napsat (další) nové rozhraní a konvertovat podle něj (dalších) několik set řádek kódu. Změny byly dostatečně komplexní na to, aby je nebylo možné provést skriptem, ale dostatečně jednoduché, že jsem si chtěla vydrápat oči kvůli té duši ubíjející nudě při ručních úpravách. V tu chvíli správce, Theodore Ts'o, navrhl, abych se podívala na Coccinelle (též známé jako spatch).

Coccinelle

Coccinelle (vyslovováno kok'-si:-nel) je nástroj pro automatickou analýzu a přepis C kódu, ve francouzštině toto slovo znamená "slunéčko sedmitečné"; jméno je zvoleno proto, že slunéčko požírá jiné brouky [bug]. Nejde pouze o další skriptovací jazyk; Coccinelle si je vědom struktury jazyka C a je schopno provádět komplexnější změny, než je možné čistým zpracováním řetězců. Například může danou změnu provést jenom u funkcí, které jsou spojeny s ukazatelem na funkci v konkrétním typu pole - řekněme člena create struktury struct inode_operations.

Vstupem pro tento nástroj je soubor(y), který se má měnit, a "sémantický patch" napsaný v SmPL [Semantic Patch Language, jazyk pro sémantické patche]. SmPL vypadá jako unifikovaný [unified] diff (patch), do kterého jsou zamíchány nějaké céčkové deklarace. Zde je příklad:

@@
expression E;
identifier fld;
@@

- !E && !E->fld
+ !E || !E->fld

Tento sémantický patch opravuje chybu, kde je ukazatel testován na nulovost - a dereferencován, pokud je nulový. Příklad chyby, kterou tento sémantický patch našel v linuxovém jádře (a automaticky vygeneroval opravu):

 --- a/drivers/pci/hotplug/cpqphp_ctrl.c
 +++ b/drivers/pci/hotplug/cpqphp_ctrl.c
 @@ -1139,7 +1139,7 @@ static u8 set_controller_speed(struct controller
 *ctrl, u8 adapter_speed, u8 hp_
         for(slot = ctrl->slot; slot; slot = slot->next) {
                 if (slot->device == (hp_slot + ctrl->slot_device_offset))
                            continue;
 -               if (!slot->hotplug_slot && !slot->hotplug_slot->info)
 +               if (!slot->hotplug_slot || !slot->hotplug_slot->info)
                         continue;
                 if (slot->hotplug_slot->info->adapter_status == 0)
                         continue;

(Více o formátu sémantického patche je popsáno později.)

Coccinelle navrhli, napsali a spravují Julie Lawall z Katedry počítačových věd Univerzity v Kodani, Gilles Muller a Yoann Padioleau z Ecole des Mines de Nantes a René Rydhof Hansen z Katedry počítačových věd Univerzity v Aalborg. Je distribuován pod licencí GPL, nicméně je napsán v OCamlu, takže potenciální základna vývojářů je poněkud omezená.

Původním cílem Coccinelle bylo co nejvíce automatizovat úkol udržovat ovladače aktuální s nejnovějšími rozhraními v jádře. Konečný výsledek nicméně umí mnohem více než to, včetně vyhledávání a opravování chyb a nepravidelností ve stylu psaní kódu. Do linuxového jádra bylo dosud akceptováno přes 180 patchů vytvořených pomocí Coccinelle.

Rychlý úvod do Coccinelle

Jako mnoho jazyků, i SmPL se lze nejlépe naučit pomocí příkladů. Pro začátek si projdeme jeden jednoduchý, poté můžeme na webové stránce Coccinelle najít nějakou dokumentaci a přehršel příkladů.

Nejprve Coccinelle stáhněte a nainstalujte. Já jsem místo kterékoliv předkompilované volby použila verzi ze zdrojových kódů. Binárka Coccinelle se nazývá spatch.

V našem příkladu řekněme, že máme program, který často volá alloca(), a my bychom tato volání chtěli nahradit malloc(). Funkce alloca() alokuje prostor na zásobníku a může být efektivnější a vhodnější než malloc(), ale je také závislá na překladači, nestandardní, snadno se použije nesprávně a při selhání má nedefinované chování. (Nahrazení alloca() malloc() není dostatečné, také musíme testovat návratovou hodnotu - ale o tom později.)

Zde je C soubor, se kterým pracujeme:

#include <alloca.h>

int
main(int argc, char *argv[])
{
        unsigned int bytes = 1024 * 1024;
        char *buf;

        /* allocate memory */
        buf = alloca(bytes);

        return 0;
}

Mohli bychom nahrazení zařídit skriptovacím jazykem jako je sed:

$ sed -i 's/alloca/malloc/g' test.c

To ale nahradí řetězec "alloca", kdekoliv se objeví. Výsledný diff:

--- test.c
+++ /tmp/test.c
@@ -1,4 +1,4 @@
-#include <alloca.h>
+#include <malloc.h>

 int
 main(int argc, char *argv[])
@@ -6,8 +6,8 @@
         unsigned int bytes = 1024 * 1024;
         char *buf;

-        /* allocate memory */
-        buf = alloca(bytes);
+        /* mallocte memory */
+        buf = malloc(bytes);

         return 0;
 }

Tento skript můžeme vyladit tak, aby řešil 90 % případů:

$ sed -i 's/alloca(/malloc(/g' test.c

Úprava ale neřeší případ, kdy má jméno druhé funkce jako příponu jméno první, závisí na stylu psaní kódu, kde mezi otevírající závorkou a jménem funkce není žádný bílý znak, atd., atd. Touhle dobou už je náš jednoduchý skript pro sed stoznakové monstrum. Lze ho vytvořit, ale je to problematické.

V Coccinelle bychom použili následující sémantický patch:

@@ expression E; @@

-alloca(E)
+malloc(E)

C soubor nechť je test.c, sémantický patch uložíme do test.cocci a spustíme patchování:

$ spatch -sp_file test.cocci test.c

Měl by být vytvořen takovýto diff:

--- test.c
+++ /tmp/cocci-output-17416-b5450d-test.c
@@ -7,7 +7,7 @@ main(int argc, char *argv[])
         char *buf;
 
         /* allocate memory */
-        buf = alloca(bytes);
+        buf = malloc(bytes);
 
         return 0;
 }

Nyní se podívejme na sémantický patch řádek po řádku.

@@ expression E; @@

Tento řádek deklaruje "metaproměnnou" E jako proměnnou, která může odpovídat kterémukoliv výrazu - například 1 + 2, sizeof(x), strlen(name) + sizeof(x) * 72. Když spatch zpracovává vstup, nastaví hodnotu E na argument alloca(). Syntaxe @@ @@ je zvolena tak, aby připomínala řádek v unifikovaném diffu popisující řádky, které se budou patchovat. Osobně tuto podobnost nepovažuji za příliš užitečnou, ale záměr je zvolen dobře.

-alloca(E)

Tento řádek říká, že se má odstranit jakékoliv volání funkce alloca() a jeho argument uložit do metaproměnné E.

+malloc(E)

A tento řádek říká, že se volání alloca() má nahradit voláním malloc() a použít hodnotu metaproměnné E jako argument.

Nyní bychom také chtěli testovat návratovou hodnotu malloc() a vrátit chybu, pokud selhalo. To můžeme udělat také:

@@
expression E;
identifier ptr;
@@

-ptr = alloca(E);
+ptr = malloc(E);
+if (ptr == NULL)
+        return 1;

Výsledný diff:

--- test.c
+++ /tmp/cocci-output-17494-22a573-test.c
@@ -7,7 +7,8 @@ main(int argc, char *argv[])
         char *buf;
 
         /* allocate memory */
-        buf = alloca(bytes);
+        buf = malloc(bytes);
+        if (buf == NULL)
+                return 1;
 
         return 0;
 }

Sémantické patche mohou být mnohem komplexnější. Jedním z mých oblíbených příkladů je přesun počítání referencí struktury Scsi_Host mimo ovladače. Tato změna vyžadovala přidání argumentu signatuře funkce a odstranění deklarace a několika dalších řádek z funkce proc_info každého SCSI ovladače. Sémantický patch, který je detailně popsán ve slidech OLS 2007 [PPT] [ODP], toto všechno udělá automaticky. Doporučuji přečíst si tento příklad několikrát, dokud si ho neosvojíte.

Zkušenosti

Moje první zkušenost s Coccinelle byla smíšená. Teoreticky Coccinelle dělá přesně to, co chci - automatizuje komplexní změny v kódu - ale praktická implementace má kvalitu betaverze. Úspěšně jsem použila Coccinelle ke změnám v rozsahu několika stovek řádků s méně než sto řádky sémantických patchů, ale až po přímé spolupráci s vývojáři na opravování chyb a zjišťování vlastností SmPL. Coccinelle je jeden z těch schizofrenních projektů umístěných na hranici mezi akademickým výzkumem a vývojem softwaru.

První překážku, kterou jsem musela překonat, bylo poučit Coccinelle o makrech ve svém kódu. Coccinelle si sám musí zajistit veškeré parsování a preprocessing - není možné prostě prohnat C kód přes cpp, protože pak by bylo potřeba mapovat výstup preprocesoru zpět na původní kód. Makro je občas natolik matoucí, že Coccinelle vzdá procházení funkce do místa, kde narazí na další bezpečný gramatický počáteční bod (tj. na další funkci) - což může znamenat, že nezpracuje většinu souboru. Abyste toto obešli, můžete vytvořit seznam maker a vložit je do spatch s volbou -macro_file. (Ano, to je jedna pomlčka - jedna z věcí, která mě na Coccinelle štve, je nestandardní styl voleb příkazové řádky.) Zde je například několik řádek z makro souboru, který jsem použila pro e2fsprogs:

#define EXT2FS_ATTR(a)
#define _INLINE_ inline
#define ATTR(a)

Seznam maker lze vytvořit ručně, ale spatch má volbu, která je vyhledává automaticky. Volba -parse_c způsobí, že spatch vypíše deset nejčastějších chyb, které budou zahrnovat jméno makra. Zde je například část výstupu z spatch -parse_c na e2fsprogs:

EXT2FS_ATTR: present in 85 parsing errors
example:

      static int check_and_change_inodes(ext2_ino_t dir,
                                  int entry EXT2FS_ATTR((unused)),
                                  struct ext2_dir_entry *dirent, int
                                  offset,
                                  int  blocksize EXT2FS_ATTR((unused)),

V těchto několika týdnech bylo Coccinelle významně vylepšen. Vydání 0.1.2 mělo mnoho chyb, kvůli kterým byl pro mě spatch nepoužitelný. Další vydání (0.1.3) tyto chyby opravilo a s ním jsem byla schopna vytvořit praktické patche pro skutečný svět. Vydání 0.1.4 přijde brzy. Vývojáři napsali a uvolnili více dokumentace, včetně popisu všech voleb pro příkazovou řádku [PDF] a gramatiky SmPL. K dispozici je mnohem více příkladových skriptů pro spatch. Nejlepším zdrojem pro výuku Coccinelle jsou stále slidy z OLS 2007 a s nimi spojené pojednání [PDF]. Práce s bílými znaky se zlepšuje; Coccinelle se původně příliš o bílé znaky nestaral a často poškodil transformace, které je obsahovaly; což je problém, když se pokoušíte o automatizaci editace, která se dříve dělala pouze ručně. Jeden z mých sémantických patchů zanechal uprostřed kódu středník; vývojáři mi poslali opravu během několika dní.

Jednou věcí jsem si naprosto jistá: naučit se Coccinelle a psaní sémantických patchů bylo mnohem zábavnější než dělat změny ručně nebo s použitím regulárních výrazů. Také mám větší důvěru v to, že moje změny byly správné; je pozoruhodně příjemné, když změníte několik set řádků kódu a výsledek se na první pokus zkompiluje a projde testy na regrese.

Příbuzná práce

Jestliže opravdu chcete, můžete dělat všechno, co umí Coccinelee, pomocí vlastních skriptů - koneckonců kód je kód. Musíte se ale vypořádat se všemi okrajovými případy - pro C jsou například všechny bílé znaky obecně stejné, ale regulární výrazy považují mezeru, tabulátor a nový řádek za různé věci. Pro úkol použijte správný nástroj - jestliže jenom měníte jméno proměnné a váš první skript funguje, skvěle. Jestliže měníte konvenci volání nebo přesouváte alokaci a uvolňování objektu do jiného kontextu, zkuste Coccinelle nebo podobný nástroj.

Co se výkonu a flexibility týče, Coccinelle je podobný nástroji Stanford compiler checker [PDF] (komericializován firmou Coverity). I když je tento nástroj dospělejší a průběh analýzy a procházení kódu je lepší, Coccinele umí generovat kód, který opravuje nalezení chyby. A co je nejdůležitější, Coccinelle je open source, takže vývojáři mohou hledat a opravovat chyby sami.

Některé IDE obsahují nástroje pro automatické přepisování kódu (refactor), což je jeden aspekt toho, co dělá Coccinelle. Osobně jsem nikdy žádný z těchto nástrojů nevyzkoušela a s Coccinelle je porovnat nemůžu, ale mí přátelé, kteří ano, hlásili, že jejich stabilita má své rezervy. Xrefactory je přepisovací nástroj pro *NIX platformy, který je plně integrován s Emacsem a XEmacsem. Není open source a vyžaduje zakoupení licence, i když k dispozici je jedna verze zdarma.

Závěr

Coccinelle je nástroj s otevřeným zdrojovým kódem, který umí analyzovat a měnit zdrojový kód v C podle specifikovaných pravidel či sémantických patchů. Sémantické patche jsou mnohem mocnější než běžné patche nebo regulární výrazy. Momentálně má kvalitu betaverze, ale je použitelný pro praktické účely a vývojáři reagují poměrně rychle. Pro každého vývojáře, který provádí netriviální změny rozhraní, stojí za to naučit se ho používat.

       

Komentáře

[jos]

nějak se vám sem vloudil celej další článek ))

[Robert Krátký]

Oops... opraveno, dík.

[dayvee]

wow tak tohle vypada zajimave. diky :)

[digri]

Zajímavej článek, akorát v tom vzorovým případě s náhradou alloca lze použít úplně jednoduchej regexp.

sed 's/\<alloca\>/malloc/g' test.c

[Pavel Vymetálek]

Ale už tam takhle jednoduše nepřïdáte ten test na výsledek volání funkce.

[Miloslav Ponkrác]

Já myslím, že Coccinelle je ukázka kam až může zajít opovrhování různými IDE.

Každé dobré IDE (než začnete argumentovat různými IDE ve stylu hračky pro děti přečtěte si ještě jednou to slovo dobré) má slušné nástroje refaktorizaci, což je v zásadě to, co programátor při změnách na 99,999% potřebuje.

Ale jinak dobře pojatý článek, autor má talent.

[b*d]

Refactoring je ale věcí OOP. Toto je pokus překonat jeden z problémů, které odstraňuje OO jazyk.

Jinak se nedá než nesouhlasit - dokonce bych založil hnutí osvěty na školách, kde studenty nutí psát v obyčejném textovém editoru. Výsledek je jenom ten, že jsou znechucení chybami jako jsou překlepy a složitostí vývoje. Člověk se totiž neučí celkovým počtem pokusů nýbrž jenom počtem těch, které jsou správně.

[Ladicek]

Refactoring je ale věcí OOP.

Proč? Nebo jsem zaspal, když se měnil význam slova refaktoring (automatizované zlepšování existujícího kódu)?

[b*d]

Můžete mi prosím uvést nějaký nástroj stejných nebo lepších kvalit, než Eclipse nebo RR pro ne OO jazyk a se 100% úspěšností pro "automatizované zlepšování existujícího kódu"?

[Ladicek]

Nemůžu, protože žádný takový jazyk nepoužívám a ty nástroje neznám. Nicméně přítomný článek dokazuje, že i pro Céčko se ty nástroje dají napsat. Jeho gramatika je sice odporný hnus, což je výrazná komplikace, ale lze to. Mimochodem pokud jde o Javu, nejlepší refaktoring má jednoznačně IDEA

[deda.jabko]

gramatika Cecka zase neni takovy hnus... resp. nevidim tam zadnou vetsi krpu.... horsi je to se semantikou...

prvni vec, ktera rapidne komplikuje refaktorizaci je preprocesor. dalsi veci, ktera refaktorizaci moc nepomaha je ,,mnohoznacnost'' hodnot... z toho, ze neco muze byt napr. soucasne pointer, cislo, pole... musi mit takovy nastroj urcite ohromnou radost...

[Ladicek]

No, to je právě to. Gramatika je tak hnusná, že pro parsování jsou potřeba sémantické informace. Klasický příklad s a*b A navíc ten preprocesor, to je pravda. Ale před pár dny jsem trochu četl něco o Clangu a tam si udržují informace o původní podobě zdrojáku až do hodně pozdních fází překladu, takže něco takového asi taky jde.

[Ivan]

Ten priklad a*b je jeste brnkacka. V C++ muzete videt i tohle:

v1 = a.b();


v2 = a->c();

A co ted? Je "a" instance tridy anebo pointer? Navic trida "a" nema zadnou metodu "c". Po tom co jsem prisel o nekolik hodin zivota jsem prisel na to, ze "a" ma vnorenou tridu "x", ktera je potomkem "y" a "y" ma metodu "c". Navic trida "a" ma pretizeny operator "->" ktery umoznuje "pretypovani" na y.

 

[9x0]

Java refactoring v Eclipse rozhodne nefunguje na 100 %. Eclipse som sice len skusal, ale uz pri operacii Extract method nastali problemy a bola zmenena semantiku kodu (ale aspon ma IDE o tom informovalo). Mozno sa to uz zmenilo, no nie je to az tak davno, co som to skusal.

[Gilhad]

IMHO je Refaktoring zlepsovani existujiciho kodu (aspon to tak tvrdi Martin Fowler ve sve knize), takze refaktorovat lze v podstate jakykoli kod v tarka jakemkoli jazyce. Samozrejme nektere veci se daji refaktorizovat snaz, nektere hur. Pro nektere jazyky existuji klikaci udelatka, pro jine nikoli. Ale rict ze refaktorovani = automatizovana oprava ciste OO jazyka je podle me naproste nepochopeni podstaty :)

[Filip Jirsák]

Myslím, že v této debatě se refaktoringem myslí refaktorign s výraznou podporou nějakého nástroje. Upravit existující kód ručně je samozřejmě možné vždy a v jakémkoli jazyce, ale důvodů, proč se tomu chce každý programátor vyhnout, je v samotném článku popsáno dost.

PS: ostřílení programátoři by refaktoring asi popsali spíš jako nahrazování starých chyb novými chybami.

[Gilhad]

To zni jako z praxe :)

Spravne by refaktoring mel zachovat vsechny stavajici chyby, nepridat zadne nove a jenom zmenit vzhled zapisu zdrojaku na neco, co se bude udrzovat ponekud snaz a v cem ty chyby budou opravitelnejsi :)

[Ivan]

Rozhodne nechci hajit Javu, napsal jsem v ni vsehovsudy pouze jeden program, ale prave refactioring v Eclipse me utvrdil v tom, ze gcc zaostava. Eclipse ma integrovany kompilator a ten do prostredi dodava vsechny potrebne informace pro pochopeni kodu a nasledny refactoring. Takovy refactoring je uspesny ve 100% pripadu. Vubec se to neda srovnat s nastroji jako cscope nebo ctags. Nikde nenarazite na milion maker, ktera jsou do sebe zanorena do sebe takovym zpusobem ze nikdo nedokaze odhadnout co z nich vlastne vypadne - viz treba mozilla nebo alokace pameti v openldapu.

 

[Filip Jirsák]

Jenom doplním, že k refaktoringu nepotřebujete celý kompilátor, stačí analyzátor kódu. V tomhle má Java velkou výhodu, protože je to tak jednoduchý jazyk. Není problém analyzovat k, zjistit co se kde jak volá atd., ale pořád si pamatovat, kde přesně je to ve zdrojovém kódu. U těch 100 % bych také nějakou tu setinku ubral -- on ten eclipsí kompilátor taky není úplně v pořádku (resp. třeba nepřeloží kód, který Sunovský kompilátor přeloží nebo opačně -- a podle mne správně bylo chování Sunovského kompilátoru).