Pojďte na lov: GCC 4.3.0 vs. verse

20.4.2008 12:18 | Přečteno: 1397× | Programování | poslední úprava: 23.4.2008 17:30

UPDATE: Vyřešeno

Tři hodiny po odeslání bug reportu do gcc bugzilly problém vyřešen jedním z vývojářů. Jelikož tomu nerozumím až tak dobře, tak v zájmu nešíření FUDu napíšu pouze odkaz s řešením.

Pojďte se mnou na lov. Co nás čeká? Spousta nebezpečí, temná zákoutí kódu a hmyzáci všude okolo.

Pomozte mi najít chybu v kombinaci GCC 4.x a Verse.

Q: O co jde?

A: Scháním někoho, kdo by mi pomohl otestovat zda bug #8959 je bugem GCC nebo verse a případně i s popisem problému. Update: Už jsem to reportoval do gcc bugzilly, mrkněte na bug #36026.

Q: Potřebný software?

A: GCC, ideálně více verzí, chyba se projevuje přinejmenším v 4.3.0 a 4.1.2 , verse a případně verse-tests (pokud chcete vyzkoušet i nějakého klienta), které jsou ke stažení přes subversion:

svn co https://svn.blender.org/svnroot/verse/trunk/verse
svn co https://svn.blender.org/svnroot/verse/trunk/verse-tests

Q: Co je třeba udělat atd.?

A: Problém je v tom, že když verse zkompiluji s gcc 4.x (v gcc 3.4.6 se chyba neprojeví) s flagem -O2 nebo vyšším tak generování klíče skončí v nekonečné smyčce. U klientů se to projevuje vždy (klíč se generuje při každém přihlášení), u serveru jen pokud v adresáři ze kterého je spouštěn není vygenerovaný host_id.rsa (např. z testu bez optimalizací).

Podle všeho za to nejspíš může nějaká kombinace flagů, protože když jsem zkoušel verse zkompilovat nejprve s jednou polovinou flagů, které -O2 zapíná a potom s druhou, ani jednou se problém neprojevil.

Q: Kde hledat chybu?

A: Hlavně díky Ketlingově pomoci byla jako původce chyby odhalena funkce miller_rabin() v souboru v_prime.c, která nerozpozná prvočíslo a tedy vrací vždy 0 což způsobí zacyklení smyčky v v_prime_set_random() v témže souboru.
Tady se naše výsledky rozchází – podle mých testů problém nastává při druhém průchodu smyčkou v miller_rabin(), kde v_bignum_square_half(d) vrací jiné výsledky v optimalizované verzi a v neoptimalizované verzi. Podle Ketlinga problém nastává také při druhém průchodu, ale ve funkci v_bignum_mul().

Q: Jak testovat?

A: Styl testování nechám na Vás. Pokud ale v adresáři, ze kterého spouštíte verse máte vygenerovaný host_id.rsa, vždy ho před dalším spuštěním vymažte, protože jinak se nespustí generovaní klíče.

---

Q: Co je to verse?

A: Verse je jednoduchý a nenáročný síťový protokol určený pro komunikaci grafických aplikací licencovaný pod GNU FDL. Linuxáky bude nejvíce zajímat jeho implementace ve verse gimp pluginu a Blenderu. Díky tomu je například možné propojit Blender a Gimp díky čemuž je možné kreslit v Gimpu texturu, která se v (takřka) reálném čase zobrazuje v Blenderu. Více viz domovská stránka verse.

Q: verse-tests nejdou zkompilovat!

A: V Makefile schází u arx flag -lalut        

Komentáře

[kozzi]

No z popisu bych to spíš vyděl na BUG v GCC, ale ještě se na to kouknu blíže.

[stativ]

Díky, tím by jsi mi moc pomohl.

Nejde kvůli tomu připojení na verse z Blenderu, které se sice dá nevím proč obejít zapnutím debug buildu (což kazí veškeré snahy o debugování), ale pak je Blender pomalý. U jiných klientů (třeba verse gimp), kteří se nelinkují s vlastní verzí verse to jde obejít tím, že verze zkompiluji bez optimalizací a nastavím ho system-wide.

[kozzi]

Jo a jakýho klienta zkoušíš, verse neznám takže nevím, co přesně mám spsutit z toho verse-test

[stativ]

To je jedno, nefunguje pak žádný. Já bežně používám render, protože na tom je to pěkně vidět, viz. další poznámky.

[kozzi]

Je to zvláštní pokud použiju k sestaveni scons tak to jede ok, ale pokud spustim standartne make tak to nejede. Nechapu proc, jelikoz scons by vlastne mel jen vygenerovat Makefile alspon myslim. V obou pripadech jsem pouzil -O2

[kozzi]

Aha tak scons nejak zahadne ten parametr -O2 vynechava tak jako vsechny dalsi.

[stativ]

scons je, pokud vím, případ sám pro sebe. Je to samostatný build systém, který Makefile negeneruje (narozdíl třeba od cmake a podobných), a rovnou spouští gcc s potřebnými flagy. Prakticky vůbec ho nechápu, jelikož python je pro mě španěská vesnice.

[Ketling]

Tak to vyzerá, že sa to zasekne v tej funkcii

miller_rabin

. Môj odhad je, že

k = v_bignum_bit_msb(nmo);

vráti záporné číslo a potom sa to v nasledujúcom fore cyklí. Navrhujem podávať na každý riadok printf a potom sa uvidí.

[stativ]

To právě že ne, právě jsem to zkusil a k je 255. Už předtím jsem pomocí gdb zkoušel step a zjistil jsem, že se neustále volá právě funkce miller_rabin().

[Ketling]

No dobre. Bola to len prvá vec čo ma napadla. Práve som dal emerge gcc, takže za takú hodinku to vyskúšam.

[Ketling]

No podľa mňa je problém v tom, že tá miller_rabin() funkcia volaná z v_prime_test() vracia vždy 0. Ale zistiť prečo asi bude nad moje sily.

[stativ]

Na něco jsem narazil, odpovídalo by to i tomu strace blenderu v odkazovaném bugreportu.

Problém nastává nejspíš už v v_randgen.c ve funkci VRandGen * v_randgen_new(void). Měl by se tam otevřít /dev/urandom, ale nic to nedělá. Když dám za gen->fd = open(SOURCE, O_RDONLY); nějaký printf, tak ho to ani nevypíše ale až po delší době to přeskočí do fce v_randgen_get() v témže souboru.

[stativ]

Dokonce pokud vymažete host_id.rsa tak se zacyklí i server což zjednodušuje práci.

[stativ]

Možná už to začínám chápat.

V souboru v_randgen.c fce VRandGen * v_randgen_new(void) otevře deskriptor na /dev/urandom a ten vrátí – to ještě funguje tak jak má.

Pak v souboru v_bignum.c funkce void v_bignum_set_random(VBigDig *x, VRandGen *gen) zavolá fci void v_randgen_get(VRandGen *gen, void *bytes, size_t num) z v_randgen.c. Tahle funkce vezme deskriptor na /dev/urandom a ten se pokusí přečíst. Pomocí ukazatale by se měly přečtená data vrátit volané funkci. A tady je průser: /dev/urandom se začne číst, ale už neskončí.

[stativ]

Tak ne, sice to tak vypadá, ale jde jenom o jeho neustálé volání. Takže je to jako původně.

[Ketling]

Tak som si to spustil a zistil som, že sa to zacyklí v súbore v_randgen.c, ako už bolo spomínané vyššie. Stále sa opakuje while cyklus s hodnotami *x=16 a gen->fd=8.

void v_prime_set_random(VBigDig *x)
{
	int		bits = v_bignum_bit_size(x);
	VRandGen	*gen;

	gen = v_randgen_new();
	do
	{
		/* Create candidate, making sure it's both odd and non-zero. */
		v_bignum_set_random(x, gen);
		/* Set topmost two bits, makes sure products are big. */
		v_bignum_bit_set(x, bits - 1);
		v_bignum_bit_set(x, bits - 2);
		/* Set lowermost bit, makes sure it is odd (better prime candidate that way). */
		v_bignum_bit_set(x, 0);
	} while(!v_prime_test(x, gen)); 
/*	printf("Prime found after %d iterations: ", count);
	v_bignum_print_hex_lf(x);
*/
	v_randgen_destroy(gen);
}

[Ketling]

Práve som to vyskúšal s gcc-4.1.2 a rovnaký problém.

Tip na debugovanie: na výpis premennej typu VBigDig je možné použiť funkciu v_bignum_print_hex_lf(x)

[stativ]

Bezva, tohle mi (nejspíš) hodně pomůže. Jinak hodnotu x jsem totiž nějak doposud nedokázal dostat. Leda že by byla pokaždé 16 . Ještě vymyslet jak získat obsah gen, ale to asi nebude třeba, podle zběžného kouknutí na kód to vypadá, že ukládá jenom deskriptor na /dev/urandom.

[stativ]

Takže to vypadá na případ, že v_prime_test() nepozná, že jde o prvočíslo.

[Ketling]

Áno je to tak. Vytvoril som si náhodný súbor dd if=/dev/urandom of=../verse-tests/rand count=1000 bs=32. Potom som prepísal 64. riadok v_randgen.c na #define SOURCE "rand". Touto úpravou mi začal program po každom spustení generovať tú istú sekvenciu čísel, takže sa dá pekne porovnať dobrý a zlý výstup.

Dobrý program označil 0xC4FD1FB7720D4DF2C15DBD9A0FF4C9454399401720757DAB7DDBD68F909D3BC1 ako prvočíslo. Zlý si myslí, že 0xC4FD1FB7720D4DF2C15DBD9A0FF4C9454399401720757DAB7DDBD68F909D3BC1 nie je prvočíslo a pokračuje drzo ďalej.

[stativ]

Já to zase zkoušel tak, že jsem před otestováním pomocí v_bignum_set_string_hex(), popř. pomocí v_bignum_set_string() x nastavil na nějaké zaručené prvočíslo (některá jsou v v_prime_set_table(), ale zkoušel jsem i jiná).

[Ketling]

Tak ďalší pokrok: v_bignum_reduce(d, n, mu); pri druhom prechode for cyklom vracia nesprávny výsledok.

[Ketling]

Ešte jeden update: chyba je vo funkcii v_bignum_bit_shift_right() volanej z v_bignum_reduce()

[Ketling]

Nie v_bignum_bit_shift_right() ale v_bignum_mul(), nejak som to splietol

[Jirka P]

Můžu hádat? hází to ty cifry o 1 větší (tedy 0x10001 * 0x10001 -> 0x200030002 místo 0x100020001)?

[stativ]

Já došel k jinému výsledku – že problém je v druhém průběhu smyčkou v miller_rabin() ve funkci v_bignum_square_half(d);

[stativ]

Nějak se mi toho nedaří dosáhnout. Pokaždé mi to vygeneruje jinou hodnotu druhého parametru.

[stativ]

Už nic, našel jsem to.

[Ketling]

Příloha:

• main.c (4912 bytů)

Tak som dal tie inkriminované funkcie do testovacieho zdrojáku (v prílohe) a nejako sa mi stále nedarí zreprodukovať tú chybu.

[stativ]

Příloha:

• test_simple.c (2570 bytů)

Mně jo, viz příloha.

[Ketling]

Skvelé! Vyzerá to tak, že sa treba asi presne trafiť do dĺžky toho čísla. Ja som experimentoval s rôznymi hodnotami aj s rôznym počtom úvodných núl a stále nič.

[stativ]

Řekl bych, že délka je dána pocí BITS (která je 512, původně definována je v v_encryption.h jako V_ENCRYPTION_LOGIN_KEY_BITS).

[Ketling]

Příloha:

• results.diff (31566 bytů)

Tak som odkomentoval zopár zakomentovaných printf() vo funkcii v_bignum_square_half() a tu je výsledok.

Prvá kompilácia: ./a.out > out1

Druhá kompilácia: ./a.out > out2

diff -u out1 out2 > priloha.diff

[Ketling]

high = (uv & 0x80000000) != 0; je vždy 0. Predpokladám, že to bude chyba kompilátora.

[stativ]

Díky moc! Před chvílí jsem odeslal bug report do gcc bugzilly (#36026). Tohle tam doplním.

[stativ]

Tak na tohle nejde říct nic jiného než: „Wow!“

[Ketling]

Tak to by ma nikdy nenapadlo. Škoda, že kompilátor nevyhodí ten warning pri -Wall alebo aspoň -Wextra.