PB173 - Ovladače jádra - Linux IV. Chyby souběhu Jiri Slabý Fakulta informatiky Masarykova univerzita 15. 10. 2015 Jiri Slabý (Fakulta informatiky, MU) PB173/04 15. 10. 2015 1 /19 Obsah cvičení Q Chyby souběhu Q Atomické operace, bitmapy Q Zámky • Spinlocky • Mutexy Jiri Slabý (Fakulta informatiky, MU) PB173/04 15.10.2015 2/ 19 Chyby souběhu, zámky LDD3 kap. 5 (zastaralá) Co je chyba souběhu • Chyba závislá na načasování/prokládání operací Ukázkový kód i int *addr = &some_int; int a = load(addr); a = a + 1; store(a, addr); Jiri Slabý (Fakulta informatiky, MU) PB173/04 15. 10. 2015 3/ 19 Příklad chyby souběhu int a = load(addr); a = a + 1; store(a, addr); Uvažujme při startu *addr == o *addr Vlákno A Vlákno B 0 int a = load(addr); 0 a = a + 1; 0 *addr Vlákno A Vlákno B 0 int a = load(addr); int a = load(addr); 0 a = a + 1; a = a + 1; 1 store(a, addr); *addr Vlákno A Vlákno B 0 int a = load(addr); 0 a = a + 1; /*>1 <*/ store(a, addr); Jiri Slabý (Fakulta informatiky, MU) PB173/04 15. 10. 2015 4/ 19 Řešení chyb souběhu • Atomickou operací ve stylu ioad_inc_store • Nutná podpora CPU • Ne na všechno jsou operace (vesměs jen +, load, store) • Kritickou sekcí • Kus kódu vykonávaný max. jedním procesem • Zámky • Read-copy-update (RCU) • Podrobnosti v LDD Jiri Slabý (Fakulta informatiky MU) PB173/04 15. 10. 2015 5/ 19 Sekce 2 Atomické operace, bitmapy Jiri Slabý (Fakulta informatiky, MU) PB173/04 15. 10. 2015 6/ 19 Atomické operace • linux/atomic.h, Documentation/atomic_ops.txt • atomic.t a = AT0MIC_INIT(5) • Pojme 32 bitů se znaménkem (int) (historicky jen 24) • atomic_read, atomic_set • atomic_add, atomic_inc, atomic_sub5 atomic_dec, atomic_*_return a další (LXR) int *addr = &some_int; atomicj a; int a = load(addr); a = a + 1; store(a, addr); atomic_inc(&a); /* nebo atomic_add(1, &a); */ • atomic64_t (drahý na 32-bitu) Jiri Slabý (Fakulta informatiky, MU) PB173/04 15. 10. 2015 7/19 Úkol Práce s atomickými typy O Definice jednoho atomic.t V module.init O Nastavit hodnotu na -3 (nejlépe staticky) O Atomicky jednou operací „přičíst 1 a přečíst hodnotu" O Přečtenou hodnotu vypsat do logu Q Přičíst 3 O Odečíst 1 O Přečíst hodnotu a vrátit jako návratovou Pozn.: tento kód nemažte, budeme s ním nadále pracovat Jiri Slabý (Fakulta informatiky, MU) PB173/04 15. 10. 2015 8/ 19 Atomické bitové operace • Stačí-li 1 bit namísto int • linux/bitops.h, Documentation/atomic_ops.txt • DECLARE_BITMAP(a, 1000) • set_bit, clear_bit5 test_bit • test_and_set_bit5 test_and_clear_bit Bitmapy lze použít i NEATOMICKY (např. v kritických sekcích) • linux/bitmap.h •__set_bit,__clear_bit • bitmap_zero, bitmap_f ill, bitmap_copy • bitmap_0P, kde OP G {and,or,xor,andnot,complement} • bitmap_empty, bitmap_full, .. . Jiri Slabý (Fakulta informatiky, MU) PB173/04 15. 10. 2015 9/ 19 Úkol Práce s bitmapami O Definice bitového pole o 100 bitech O Výmaz pole • bitmap_zero O Nastavení 2., 63. a 76. bitu (čísla považujte za indexy v C) O Výpis longu (°/0ix) s 63. bitem • bitmapa[BIT_W0RD(63)] 0 Výpis celé bitmapy jako řetězce • bitmap.scnprintf (do 4.0), °/0*bp (od 4.0) O Výpis longů obsahující bity nastavené na 1 • for_each_set_bit O Výpis pozice 1. nastaveného bitu • find first bit Jiri Slabý (Fakulta informatiky, MU) PB173/04 15. 10. 2015 10/19 Sekce 3 Zámky Jiri Slabý (Fakulta informatiky, MU) PB173/04 15. 10. 2015 11/19 Zámky Vytvoření kritické sekce • Spinlocky • Čekání ve smyčce (požírá strojový čas) • Rychlé, ale POZOR: nesmí se uvnitř spát (čekat) • Mutexy • Spící, fronta čekatelů • Pomalejší než spinlock (viz tělo__mutex_lock_common) • Semafory • Podobné mutexům • Počítadlo (jsou rekurzivní) • Dnes se používají výjimečně POZOR Zámky lze držet jen v jádře (po dobu vykonávání syscallu) Jiri Slabý (Fakulta informatiky MU) PB173/04 15. 10. 2015 12/19 Zámky v jádře - spinlocky • Cekání ve smyčce • linux/spinlock.h, Documentation/spinlocks.txt • DEFINE_SPINLOCK(lock)5 spinlock.t lock • spin_lock, spin_unlock • Podobné pthread spinlockům int *addr = &some_int; D E FIN E_S PIN LOC K(add r_l ock); int *addr = &some_int; int a = load(addr); a = a + 1; store(a, addr); spin_lock(&addr_lock); int a = load(addr); a = a + 1; store(a, addr); s pi n_u n I ock(&add rj ock); Jiri Slabý (Fakulta informatiky, MU) PB173/04 15. 10. 2015 13/19 Úkol Práce se spinlocky Úkol s atomickými operacemi prepíšte Q atomic.t změňte na obyčejný int Q A celý kód obalte spinlockem O Vyzkoušejte Jiri Slabý (Fakulta informatiky, MU) PB173/04 15. 10. 2015 14/19 Zámky v jádře - mutexy Mutexy • Spící, fronta čekatelů • linux/mutex.h • DEFINE_MUTEX(name) • mutex_lock, mutex_unlock • Podobné pthread mutexům Řešení pomocí mutexů int *addr = &some_int; D E FIN E_M UT EX(add rjock); int *addr = &some_int; int a = load(addr); a = a + 1; store(a, addr); mutex_lock(&addr_lock); int a = load(addr); a = a + 1; store(a, addr); mutex_unlock(&addr_lock); Jiri Slabý (Fakulta informatiky, MU) PB173/04 15. 10. 2015 15/19 Zámky v jádře - ostatní Semafory • linux/semaphore.h • Víceméně nepoužívat • Pozor: DECLARE_MUTEX(lock) • down, up Big Kernel Lock (BKL) • Historický • Dnes už v jádře nenajdeme (commit 4ba8216cd905 v 2.6.39) • Jen jeho relikty • Hrubozrnný • Pochází z dob počátku Linuxu • lock_kernel, unlock_kernel Jiri Slabý (Fakulta informatiky, MU) PB173/04 15. 10. 2015 16/19 Ukol Součást domácího Atomické čtení/zápis bufferu o velikosti 128 bytů O Globální buffer 128 B O 2 znaková (mise) zařízení • 1 implementuje .read • 1 implementuje .write O Zápis • Umožněn max. po 5 znacích (.write vrací max. 5) • Spí 20 ms po každém zápisu znaku do bufferu (get.user a msleep Zlinux/delay.h) O Čtení • Vrátí naráz celých 128 B (je-li count dostatečně velký) • Musí vidět změny pouze po 5 znacích (až na poslední kousek) O Vyzkoušejte Pozn.: inspirace v pb173/04 Jiri Slabý (Fakulta informatiky, MU) PB173/04 15. 10. 2015 17/19 Deadlock • 4 podmínky uváznutí • Jádro spoléhá na programátora, že k němu nikdy nedojde • LockDep • Dynamický mechanismus hledání chyb v zámcích • Obvyklé typy chyb: ABBA, AA • Obvyklé chyby: lock + if + return (POZOR) Jiri Slabý (Fakulta informatiky, MU) PB173/04 15. 10. 2015 18/19 Další problémy zámků • Zpomalují kritický kód • Řešení: odstranit zámky • Např. kruhovými buffery • Nevhodná granularita • Jeden zámek na všechno vs. jeden zámek na jednu činnost • Např. BKL, nebo naopak zámky každého registru • Zahlcení • Příliš mnoho procesů čeká na zámek • Lze řešit přechodem na COW, RCU, RW zámky, ... • Např. všechny procesy čekají na tasklist.iock Jiri Slabý (Fakulta informatiky, MU) PB173/04 15. 10. 2015 19/19