PB173 - Ovladače jádra - Linux IV. Jiri Slabý ITI, Fakulta Informatiky 10. 10. 2012 J. Slabý (ITI) PB173/06 10. 10. 2012 1 /18 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í int *addr; int a = load (addr) ; a = a + 1 ; store (a, addr) ; Ukázkový kód J. Slabý (ITI) PB173/06 10. 10. 2012 2/ 18 Příklad chyby souběhu int a = load (addr) ; a = a + 1 ; store (a, addr) ; Uvažujme *addr == 0 *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; /*>"!<*/ store (a, addr) ; - J. Slabý (ITI) PB173/06 10. 10. 2012 3/ 18 Ř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 J. Slabý (ITI) PB173/06 10. 10. 2012 4/ 18 Část I Atomické operace, bitmapy J. Slabý (ITI) PB173/06 10. 10. 2012 5/ 18 Atomické operace • asm/atomic. h, Documentation/atomic_ops . txt a atomic.t a = ATOMIC_INIT (5) • Pojme 32 bitů se znaménkem (int) (historicky jen 24) • atomicread, atomicset • atomic_add, atomicinc, atomic.sub, atomic.dec, atomic_*_return a další (LXR) int *addr; atomic.t a; int a = load (addr) ; =4> a = a + 1; store (a, addr) ; atomic.inc(&a) ; /* nebo atomic.add (1 , &a) ; */ Řešení pomocí atomických operací a atomic64_t (drahý na 32-bitu) J. Slabý (ITI) PB173/06 10. 10. 2012 6/ 18 Ú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 0 Přičíst 3 0 Odečíst 1 O Přečíst hodnotu a vrátit jako návratovou J. Slabý (ITI) PB173/06 10. 10. 2012 7/ 18 Atomické bitové operace • Stačí-li 1 bit namísto int a linux/bitops.h, Documentation/atomic_ops . txt • DECLARE_BITMAP (a, 1000) • set_bit, clear_bit, test_bit • test_and_set_bit, test_and_clear_bit Bitmapy lze použít i NEATOMICKY (např. v kritických sekcích) • linux/bitmap.h • __set_bit, __clear_bit a bitmap_zero, bitmap.f ill, bitmap_copy • bitmap.OP, kde OP £ {and, or, xor, andnot, complement} a bitmap_empty, bitmap.full, . . . J. Slabý (ITI) PB173/06 10. 10. 2012 8/ 18 Úkol Práce s bitmapami O Definice bitového pole o 100 bitech Q Výmaz pole (bitmap_zero) O Nastavení 2., 63. a 76. bitu O Výpis longu (%ix) s 63. bitem (bitmapa [bit.word (63) ]) 0 Výpis celé bitmapy (bitmap_scnprintf) O Výpis longů obsahující „1" bity (f or.each.setJoit) O Výpis pozice 1. nastaveného bitu (f ind_f irst_bit) J. Slabý (ITI) PB173/06 10. 10. 2012 9/ 18 Část II Zámky J. Slabý (ITI) PB173/06 10. 10. 2012 10/18 Zámky Vytvoření kritické sekce « Spinlocky • Čekání ve smyčce (požírá strojový čas) • Rychlé, nesmí se uvnitř spát (čekat) • Mutexy • Spící, fronta čekatelů • Pomalejší než spinlock (viz tělo _mutex.iock.common) a Semafory • Podobné mutexům • Počítadlo (jsou rekurzivní) • Dnes se používají výjimečně Zámky lze držet jen v jádře (po dobu vykonávání syscallu) J. Slabý (ITI) PB173/06 10. 10. 2012 11/18 Zámky v jádře - spinlocky • linux/spinlock.h, Documentation/spinlocks.txt • DEFINE.SPINLOCK(lock),spinlock.t lock • spin_lock, spin_unlock • Podobné pthread spinlockům int *addr; int a = load (addr) a = a + 1; store (a, addr) ; DEFINE.SPINLOCK( addr.lock) int *addr; spin.lock(&addr.lock ) ; int a = load (addr) ; a = a + 1 ; store (a, addr) ; spin.unlock(&addr.lock ) ; Řešení pomocí spinlocků J. Slabý (ITI) PB173/06 10. 10. 2012 12/18 Spinlocky a přerušení Vlákno Přerušení spin.lock(&addr.lock ) ; spin Jock(&addr_lock) ; spin.unlock(&addr.lock ) ; // " deadlock spin _unlock(&addrJock) ; _irq* varianty • Zákaz přerušení, poté spinlock Vlákno Přerušení spin.lock.irq(&addr.lock) ; // interrupt cannot trigger spi n.u nlock.irq (&addr.lock ) ; spin.lock(&addr.lock ) ; spin.unlock(&addr.lock ) ; J. Slaby (ITI) PB173/06 10. 10. 2012 13/18 Zámky v jádře - mutexy Mutexy a linux/mutex.h • DEFINEJMUTEX(name) • mutex.lock, mutex.unlock • Podobné pthread mutexům int *addr; DEFINE_MUTEX( addr.lock) ; int *addr; int a = load (addr) ; =4> a = a + 1 ; store (a, addr) ; mutex_lock(&addrJock) ; int a = load (addr) ; a = a + 1 ; store (a, addr) ; mutex.unlock(&addr.lock) ; Řešení pomocí mutexů J. Slabý (ITI) PB173/06 10. 10. 2012 14/18 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) • NEPOUŽÍVAT 9 V nových jádrech už ani není • Hrubozrnný zámek • Pochází z dob počátku Linuxu • lock.kernel, unlock_kernel J. Slabý (ITI) PB173/06 10.10.2012 15/ 18 Úkol Atomické čtení/zápis bufferu o velikosti 128 bytů • Globální buffer « 2 znaková (mise) zařízení • 1 implementuje . read • 1 implementuje .write • Zápis o Umožněn max. po 5 znacích (.write vrací max. 5) • Spí 20 ms po každém zápisu znaku do bufferu (msleep z linux/delay.h) • Č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í pětici) • Vyzkoušejte Pozn. 1: práce soffpv pb173/04 Pozn. 2: odevzdat s domácím J. Slabý (ITI) PB173/06 10. 10. 2012 16/18 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 •L 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 taskiist.iock J. Slabý (ITI) PB173/06 10. 10. 2012 18/18