1.. SPDX-License-Identifier: GPL-2.0 2 3.. include:: ../disclaimer-ita.rst 4 5Validatore di sincronizzazione durante l'esecuzione 6=================================================== 7 8Classi di blocchi 9----------------- 10 11L'oggetto su cui il validatore lavora è una "classe" di blocchi. 12 13Una classe di blocchi è un gruppo di blocchi che seguono le stesse regole di 14sincronizzazione, anche quando i blocchi potrebbero avere più istanze (anche 15decine di migliaia). Per esempio un blocco nella struttura inode è una classe, 16mentre ogni inode sarà un'istanza di questa classe di blocco. 17 18Il validatore traccia lo "stato d'uso" di una classe di blocchi e le sue 19dipendenze con altre classi. L'uso di un blocco indica come quel blocco viene 20usato rispetto al suo contesto d'interruzione, mentre le dipendenze di un blocco 21possono essere interpretate come il loro ordine; per esempio L1 -> L2 suggerisce 22che un processo cerca di acquisire L2 mentre già trattiene L1. Dal punto di 23vista di lockdep, i due blocchi (L1 ed L2) non sono per forza correlati: quella 24dipendenza indica solamente l'ordine in cui sono successe le cose. Il validatore 25verifica permanentemente la correttezza dell'uso dei blocchi e delle loro 26dipendenze, altrimenti ritornerà un errore. 27 28Il comportamento di una classe di blocchi viene costruito dall'insieme delle sue 29istanze. Una classe di blocco viene registrata alla creazione della sua prima 30istanza, mentre tutte le successive istanze verranno mappate; dunque, il loro 31uso e le loro dipendenze contribuiranno a costruire quello della classe. Una 32classe di blocco non sparisce quando sparisce una sua istanza, ma può essere 33rimossa quando il suo spazio in memoria viene reclamato. Per esempio, questo 34succede quando si rimuove un modulo, o quando una *workqueue* viene eliminata. 35 36Stato 37----- 38 39Il validatore traccia l'uso cronologico delle classi di blocchi e ne divide 40l'uso in categorie (4 USI * n STATI + 1). 41 42I quattro USI possono essere: 43 44- 'sempre trattenuto nel contesto <STATO>' 45- 'sempre trattenuto come blocco di lettura nel contesto <STATO>' 46- 'sempre trattenuto con <STATO> abilitato' 47- 'sempre trattenuto come blocco di lettura con <STATO> abilitato' 48 49gli `n` STATI sono codificati in kernel/locking/lockdep_states.h, ad oggi 50includono: 51 52- hardirq 53- softirq 54 55infine l'ultima categoria è: 56 57- 'sempre trattenuto' [ == !unused ] 58 59Quando vengono violate le regole di sincronizzazione, questi bit di utilizzo 60vengono presentati nei messaggi di errore di sincronizzazione, fra parentesi 61graffe, per un totale di `2 * n` (`n`: bit STATO). Un esempio inventato:: 62 63 modprobe/2287 is trying to acquire lock: 64 (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24 65 66 but task is already holding lock: 67 (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24 68 69Per un dato blocco, da sinistra verso destra, la posizione del bit indica l'uso 70del blocco e di un eventuale blocco di lettura, per ognuno degli `n` STATI elencati 71precedentemente. Il carattere mostrato per ogni bit indica: 72 73 === =========================================================================== 74 '.' acquisito con interruzioni disabilitate fuori da un contesto d'interruzione 75 '-' acquisito in contesto d'interruzione 76 '+' acquisito con interruzioni abilitate 77 '?' acquisito in contesto d'interruzione con interruzioni abilitate 78 === =========================================================================== 79 80Il seguente esempio mostra i bit:: 81 82 (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24 83 |||| 84 ||| \-> softirq disabilitati e fuori da un contesto di softirq 85 || \--> acquisito in un contesto di softirq 86 | \---> hardirq disabilitati e fuori da un contesto di hardirq 87 \----> acquisito in un contesto di hardirq 88 89Per un dato STATO, che il blocco sia mai stato acquisito in quel contesto di 90STATO, o che lo STATO sia abilitato, ci lascia coi quattro possibili scenari 91mostrati nella seguente tabella. Il carattere associato al bit indica con 92esattezza in quale scenario ci si trova al momento del rapporto. 93 94 +---------------+---------------+------------------+ 95 | | irq abilitati | irq disabilitati | 96 +---------------+---------------+------------------+ 97 | sempre in irq | '?' | '-' | 98 +---------------+---------------+------------------+ 99 | mai in irq | '+' | '.' | 100 +---------------+---------------+------------------+ 101 102Il carattere '-' suggerisce che le interruzioni sono disabilitate perché 103altrimenti verrebbe mostrato il carattere '?'. Una deduzione simile può essere 104fatta anche per '+' 105 106I blocchi inutilizzati (ad esempio i mutex) non possono essere fra le cause di 107un errore. 108 109Regole dello stato per un blocco singolo 110---------------------------------------- 111 112Avere un blocco sicuro in interruzioni (*irq-safe*) significa che è sempre stato 113usato in un contesto d'interruzione, mentre un blocco insicuro in interruzioni 114(*irq-unsafe*) significa che è sempre stato acquisito con le interruzioni 115abilitate. 116 117Una classe softirq insicura è automaticamente insicura anche per hardirq. I 118seguenti stati sono mutualmente esclusivi: solo una può essere vero quando viene 119usata una classe di blocco:: 120 121 <hardirq-safe> o <hardirq-unsafe> 122 <softirq-safe> o <softirq-unsafe> 123 124Questo perché se un blocco può essere usato in un contesto di interruzioni 125(sicuro in interruzioni), allora non può mai essere acquisito con le 126interruzioni abilitate (insicuro in interruzioni). Altrimenti potrebbe 127verificarsi uno stallo. Per esempio, questo blocco viene acquisito, ma prima di 128essere rilasciato il contesto d'esecuzione viene interrotto nuovamente, e quindi 129si tenterà di acquisirlo nuovamente. Questo porterà ad uno stallo, in 130particolare uno stallo ricorsivo. 131 132Il validatore rileva e riporta gli usi di blocchi che violano queste regole per 133blocchi singoli. 134 135Regole per le dipendenze di blocchi multipli 136-------------------------------------------- 137 138La stessa classe di blocco non deve essere acquisita due volte, questo perché 139potrebbe portare ad uno blocco ricorsivo e dunque ad uno stallo. 140 141Inoltre, due blocchi non possono essere trattenuti in ordine inverso:: 142 143 <L1> -> <L2> 144 <L2> -> <L1> 145 146perché porterebbe ad uno stallo - chiamato stallo da blocco inverso - in cui si 147cerca di trattenere i due blocchi in un ciclo in cui entrambe i contesti 148aspettano per sempre che l'altro termini. Il validatore è in grado di trovare 149queste dipendenze cicliche di qualsiasi complessità, ovvero nel mezzo ci 150potrebbero essere altre sequenze di blocchi. Il validatore troverà se questi 151blocchi possono essere acquisiti circolarmente. 152 153In aggiunta, le seguenti sequenze di blocco nei contesti indicati non sono 154permesse, indipendentemente da quale che sia la classe di blocco:: 155 156 <hardirq-safe> -> <hardirq-unsafe> 157 <softirq-safe> -> <softirq-unsafe> 158 159La prima regola deriva dal fatto che un blocco sicuro in interruzioni può essere 160trattenuto in un contesto d'interruzione che, per definizione, ha la possibilità 161di interrompere un blocco insicuro in interruzioni; questo porterebbe ad uno 162stallo da blocco inverso. La seconda, analogamente, ci dice che un blocco sicuro 163in interruzioni software potrebbe essere trattenuto in un contesto di 164interruzione software, dunque potrebbe interrompere un blocco insicuro in 165interruzioni software. 166 167Le suddette regole vengono applicate per qualsiasi sequenza di blocchi: quando 168si acquisiscono nuovi blocchi, il validatore verifica se vi è una violazione 169delle regole fra il nuovo blocco e quelli già trattenuti. 170 171Quando una classe di blocco cambia stato, applicheremo le seguenti regole: 172 173- se viene trovato un nuovo blocco sicuro in interruzioni, verificheremo se 174 abbia mai trattenuto dei blocchi insicuri in interruzioni. 175 176- se viene trovato un nuovo blocco sicuro in interruzioni software, 177 verificheremo se abbia trattenuto dei blocchi insicuri in interruzioni 178 software. 179 180- se viene trovato un nuovo blocco insicuro in interruzioni, verificheremo se 181 abbia trattenuto dei blocchi sicuri in interruzioni. 182 183- se viene trovato un nuovo blocco insicuro in interruzioni software, 184 verificheremo se abbia trattenuto dei blocchi sicuri in interruzioni 185 software. 186 187(Di nuovo, questi controlli vengono fatti perché un contesto d'interruzione 188potrebbe interrompere l'esecuzione di qualsiasi blocco insicuro portando ad uno 189stallo; questo anche se lo stallo non si verifica in pratica) 190 191Eccezione: dipendenze annidate sui dati portano a blocchi annidati 192------------------------------------------------------------------ 193 194Ci sono alcuni casi in cui il kernel Linux acquisisce più volte la stessa 195istanza di una classe di blocco. Solitamente, questo succede quando esiste una 196gerarchia fra oggetti dello stesso tipo. In questi casi viene ereditato 197implicitamente l'ordine fra i due oggetti (definito dalle proprietà di questa 198gerarchia), ed il kernel tratterrà i blocchi in questo ordine prefissato per 199ognuno degli oggetti. 200 201Un esempio di questa gerarchia di oggetti che producono "blocchi annidati" sono 202i *block-dev* che rappresentano l'intero disco e quelli che rappresentano una 203sua partizione; la partizione è una parte del disco intero, e l'ordine dei 204blocchi sarà corretto fintantoche uno acquisisce il blocco del disco intero e 205poi quello della partizione. Il validatore non rileva automaticamente questo 206ordine implicito, perché queste regole di sincronizzazione non sono statiche. 207 208Per istruire il validatore riguardo a questo uso corretto dei blocchi sono stati 209introdotte nuove primitive per specificare i "livelli di annidamento". Per 210esempio, per i blocchi a mutua esclusione dei *block-dev* si avrebbe una 211chiamata simile a:: 212 213 enum bdev_bd_mutex_lock_class 214 { 215 BD_MUTEX_NORMAL, 216 BD_MUTEX_WHOLE, 217 BD_MUTEX_PARTITION 218 }; 219 220 mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION); 221 222In questo caso la sincronizzazione viene fatta su un *block-dev* sapendo che si 223tratta di una partizione. 224 225Ai fini della validazione, il validatore lo considererà con una - sotto - classe 226di blocco separata. 227 228Nota: Prestate estrema attenzione che la vostra gerarchia sia corretta quando si 229vogliono usare le primitive _nested(); altrimenti potreste avere sia falsi 230positivi che falsi negativi. 231 232Annotazioni 233----------- 234 235Si possono utilizzare due costrutti per verificare ed annotare se certi blocchi 236devono essere trattenuti: lockdep_assert_held*(&lock) e 237lockdep_*pin_lock(&lock). 238 239Come suggerito dal nome, la famiglia di macro lockdep_assert_held* asseriscono 240che un dato blocco in un dato momento deve essere trattenuto (altrimenti, verrà 241generato un WARN()). Queste vengono usate abbondantemente nel kernel, per 242esempio in kernel/sched/core.c:: 243 244 void update_rq_clock(struct rq *rq) 245 { 246 s64 delta; 247 248 lockdep_assert_held(&rq->lock); 249 [...] 250 } 251 252dove aver trattenuto rq->lock è necessario per aggiornare in sicurezza il clock 253rq. 254 255L'altra famiglia di macro è lockdep_*pin_lock(), che a dire il vero viene usata 256solo per rq->lock ATM. Se per caso un blocco non viene trattenuto, queste 257genereranno un WARN(). Questo si rivela particolarmente utile quando si deve 258verificare la correttezza di codice con *callback*, dove livelli superiori 259potrebbero assumere che un blocco rimanga trattenuto, ma livelli inferiori 260potrebbero invece pensare che il blocco possa essere rilasciato e poi 261riacquisito (involontariamente si apre una sezione critica). lockdep_pin_lock() 262restituisce 'struct pin_cookie' che viene usato da lockdep_unpin_lock() per 263verificare che nessuno abbia manomesso il blocco. Per esempio in 264kernel/sched/sched.h abbiamo:: 265 266 static inline void rq_pin_lock(struct rq *rq, struct rq_flags *rf) 267 { 268 rf->cookie = lockdep_pin_lock(&rq->lock); 269 [...] 270 } 271 272 static inline void rq_unpin_lock(struct rq *rq, struct rq_flags *rf) 273 { 274 [...] 275 lockdep_unpin_lock(&rq->lock, rf->cookie); 276 } 277 278I commenti riguardo alla sincronizzazione possano fornire informazioni utili, 279tuttavia sono le verifiche in esecuzione effettuate da queste macro ad essere 280vitali per scovare problemi di sincronizzazione, ed inoltre forniscono lo stesso 281livello di informazioni quando si ispeziona il codice. Nel dubbio, preferite 282queste annotazioni! 283 284Dimostrazione di correttezza al 100% 285------------------------------------ 286 287Il validatore verifica la proprietà di chiusura in senso matematico. Ovvero, per 288ogni sequenza di sincronizzazione di un singolo processo che si verifichi almeno 289una volta nel kernel, il validatore dimostrerà con una certezza del 100% che 290nessuna combinazione e tempistica di queste sequenze possa causare uno stallo in 291una qualsiasi classe di blocco. [1]_ 292 293In pratica, per dimostrare l'esistenza di uno stallo non servono complessi 294scenari di sincronizzazione multi-processore e multi-processo. Il validatore può 295dimostrare la correttezza basandosi sulla sola sequenza di sincronizzazione 296apparsa almeno una volta (in qualunque momento, in qualunque processo o 297contesto). Uno scenario complesso che avrebbe bisogno di 3 processori e una 298sfortunata presenza di processi, interruzioni, e pessimo tempismo, può essere 299riprodotto su un sistema a singolo processore. 300 301Questo riduce drasticamente la complessità del controllo di qualità della 302sincronizzazione nel kernel: quello che deve essere fatto è di innescare nel 303kernel quante più possibili "semplici" sequenze di sincronizzazione, almeno una 304volta, allo scopo di dimostrarne la correttezza. Questo al posto di innescare 305una verifica per ogni possibile combinazione di sincronizzazione fra processori, 306e differenti scenari con hardirq e softirq e annidamenti vari (nella pratica, 307impossibile da fare) 308 309.. [1] 310 311 assumendo che il validatore sia corretto al 100%, e che nessun altra parte 312 del sistema possa corromperne lo stato. Assumiamo anche che tutti i percorsi 313 MNI/SMM [potrebbero interrompere anche percorsi dove le interruzioni sono 314 disabilitate] sono corretti e non interferiscono con il validatore. Inoltre, 315 assumiamo che un hash a 64-bit sia unico per ogni sequenza di 316 sincronizzazione nel sistema. Infine, la ricorsione dei blocchi non deve 317 essere maggiore di 20. 318 319Prestazione 320----------- 321 322Le regole sopracitate hanno bisogno di una quantità **enorme** di verifiche 323durante l'esecuzione. Il sistema sarebbe diventato praticamente inutilizzabile 324per la sua lentezza se le avessimo fatte davvero per ogni blocco trattenuto e 325per ogni abilitazione delle interruzioni. La complessità della verifica è 326O(N^2), quindi avremmo dovuto fare decine di migliaia di verifiche per ogni 327evento, il tutto per poche centinaia di classi. 328 329Il problema è stato risolto facendo una singola verifica per ogni 'scenario di 330sincronizzazione' (una sequenza unica di blocchi trattenuti uno dopo l'altro). 331Per farlo, viene mantenuta una pila dei blocchi trattenuti, e viene calcolato un 332hash a 64-bit unico per ogni sequenza. Quando la sequenza viene verificata per 333la prima volta, l'hash viene inserito in una tabella hash. La tabella potrà 334essere verificata senza bisogno di blocchi. Se la sequenza dovesse ripetersi, la 335tabella ci dirà che non è necessario verificarla nuovamente. 336 337Risoluzione dei problemi 338------------------------ 339 340Il massimo numero di classi di blocco che il validatore può tracciare è: 341MAX_LOCKDEP_KEYS. Oltrepassare questo limite indurrà lokdep a generare il 342seguente avviso:: 343 344 (DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS)) 345 346Di base questo valore è 8191, e un classico sistema da ufficio ha meno di 1000 347classi, dunque questo avviso è solitamente la conseguenza di un problema di 348perdita delle classi di blocco o d'inizializzazione dei blocchi. Di seguito una 349descrizione dei due problemi: 350 3511. caricare e rimuovere continuamente i moduli mentre il validatore è in 352 esecuzione porterà ad una perdita di classi di blocco. Il problema è che ogni 353 caricamento crea un nuovo insieme di classi di blocco per tutti i blocchi di 354 quel modulo. Tuttavia, la rimozione del modulo non rimuove le vecchie classi 355 (vedi dopo perché non le riusiamo). Dunque, il continuo caricamento e 356 rimozione di un modulo non fa altro che aumentare il contatore di classi fino 357 a raggiungere, eventualmente, il limite. 358 3592. Usare array con un gran numero di blocchi che non vengono esplicitamente 360 inizializzati. Per esempio, una tabella hash con 8192 *bucket* dove ognuno ha 361 il proprio spinlock_t consumerà 8192 classi di blocco a meno che non vengano 362 esplicitamente inizializzati in esecuzione usando spin_lock_init() invece 363 dell'inizializzazione durante la compilazione con __SPIN_LOCK_UNLOCKED(). 364 Sbagliare questa inizializzazione garantisce un esaurimento di classi di 365 blocco. Viceversa, un ciclo che invoca spin_lock_init() su tutti i blocchi li 366 mapperebbe tutti alla stessa classe di blocco. 367 368 La morale della favola è che dovete sempre inizializzare esplicitamente i 369 vostri blocchi. 370 371Qualcuno potrebbe argomentare che il validatore debba permettere il riuso di 372classi di blocco. Tuttavia, se siete tentati dall'argomento, prima revisionate 373il codice e pensate alla modifiche necessarie, e tenendo a mente che le classi 374di blocco da rimuovere probabilmente sono legate al grafo delle dipendenze. Più 375facile a dirsi che a farsi. 376 377Ovviamente, se non esaurite le classi di blocco, la prossima cosa da fare è 378quella di trovare le classi non funzionanti. Per prima cosa, il seguente comando 379ritorna il numero di classi attualmente in uso assieme al valore massimo:: 380 381 grep "lock-classes" /proc/lockdep_stats 382 383Questo comando produce il seguente messaggio:: 384 385 lock-classes: 748 [max: 8191] 386 387Se il numero di assegnazioni (748 qui sopra) aumenta continuamente nel tempo, 388allora c'è probabilmente un problema da qualche parte. Il seguente comando può 389essere utilizzato per identificare le classi di blocchi problematiche:: 390 391 grep "BD" /proc/lockdep 392 393Eseguite il comando e salvatene l'output, quindi confrontatelo con l'output di 394un'esecuzione successiva per identificare eventuali problemi. Questo stesso 395output può anche aiutarti a trovare situazioni in cui l'inizializzazione del 396blocco è stata omessa. 397 398Lettura ricorsiva dei blocchi 399----------------------------- 400 401Il resto di questo documento vuole dimostrare che certi cicli equivalgono ad una 402possibilità di stallo. 403 404Ci sono tre tipi di bloccatori: gli scrittori (bloccatori esclusivi, come 405spin_lock() o write_lock()), lettori non ricorsivi (bloccatori condivisi, come 406down_read()), e lettori ricorsivi (bloccatori condivisi ricorsivi, come 407rcu_read_lock()). D'ora in poi, per questi tipi di bloccatori, useremo la 408seguente notazione: 409 410 W o E: per gli scrittori (bloccatori esclusivi) (W dall'inglese per 411 *Writer*, ed E per *Exclusive*). 412 413 r: per i lettori non ricorsivi (r dall'inglese per *reader*). 414 415 R: per i lettori ricorsivi (R dall'inglese per *Reader*). 416 417 S: per qualsiasi lettore (non ricorsivi + ricorsivi), dato che entrambe 418 sono bloccatori condivisi (S dall'inglese per *Shared*). 419 420 N: per gli scrittori ed i lettori non ricorsivi, dato che entrambe sono 421 non ricorsivi. 422 423Ovviamente, N equivale a "r o W" ed S a "r o R". 424 425Come suggerisce il nome, i lettori ricorsivi sono dei bloccatori a cui è 426permesso di acquisire la stessa istanza di blocco anche all'interno della 427sezione critica di un altro lettore. In altre parole, permette di annidare la 428stessa istanza di blocco nelle sezioni critiche dei lettori. 429 430Dall'altro canto, lo stesso comportamento indurrebbe un lettore non ricorsivo ad 431auto infliggersi uno stallo. 432 433La differenza fra questi due tipi di lettori esiste perché: quelli ricorsivi 434vengono bloccati solo dal trattenimento di un blocco di scrittura, mentre quelli 435non ricorsivi possono essere bloccati dall'attesa di un blocco di scrittura. 436Consideriamo il seguente esempio:: 437 438 TASK A: TASK B: 439 440 read_lock(X); 441 write_lock(X); 442 read_lock_2(X); 443 444L'attività A acquisisce il blocco di lettura X (non importa se di tipo ricorsivo 445o meno) usando read_lock(). Quando l'attività B tenterà di acquisire il blocco 446X, si fermerà e rimarrà in attesa che venga rilasciato. Ora se read_lock_2() è 447un tipo lettore ricorsivo, l'attività A continuerà perché gli scrittori in 448attesa non possono bloccare lettori ricorsivi, e non avremo alcuno stallo. 449Tuttavia, se read_lock_2() è un lettore non ricorsivo, allora verrà bloccato 450dall'attività B e si causerà uno stallo. 451 452Condizioni bloccanti per lettori/scrittori su uno stesso blocco 453--------------------------------------------------------------- 454Essenzialmente ci sono quattro condizioni bloccanti: 455 4561. Uno scrittore blocca un altro scrittore. 4572. Un lettore blocca uno scrittore. 4583. Uno scrittore blocca sia i lettori ricorsivi che non ricorsivi. 4594. Un lettore (ricorsivo o meno) non blocca altri lettori ricorsivi ma potrebbe 460 bloccare quelli non ricorsivi (perché potrebbero esistere degli scrittori in 461 attesa). 462 463Di seguito le tabella delle condizioni bloccanti, Y (*Yes*) significa che il 464tipo in riga blocca quello in colonna, mentre N l'opposto. 465 466 +---+---+---+---+ 467 | | W | r | R | 468 +---+---+---+---+ 469 | W | Y | Y | Y | 470 +---+---+---+---+ 471 | r | Y | Y | N | 472 +---+---+---+---+ 473 | R | Y | Y | N | 474 +---+---+---+---+ 475 476 (W: scrittori, r: lettori non ricorsivi, R: lettori ricorsivi) 477 478Al contrario dei blocchi per lettori non ricorsivi, quelli ricorsivi vengono 479trattenuti da chi trattiene il blocco di scrittura piuttosto che da chi ne 480attende il rilascio. Per esempio:: 481 482 TASK A: TASK B: 483 484 read_lock(X); 485 486 write_lock(X); 487 488 read_lock(X); 489 490non produce uno stallo per i lettori ricorsivi, in quanto il processo B rimane 491in attesta del blocco X, mentre il secondo read_lock() non ha bisogno di 492aspettare perché si tratta di un lettore ricorsivo. Tuttavia, se read_lock() 493fosse un lettore non ricorsivo, questo codice produrrebbe uno stallo. 494 495Da notare che in funzione dell'operazione di blocco usate per l'acquisizione (in 496particolare il valore del parametro 'read' in lock_acquire()), un blocco può 497essere di scrittura (blocco esclusivo), di lettura non ricorsivo (blocco 498condiviso e non ricorsivo), o di lettura ricorsivo (blocco condiviso e 499ricorsivo). In altre parole, per un'istanza di blocco esistono tre tipi di 500acquisizione che dipendono dalla funzione di acquisizione usata: esclusiva, di 501lettura non ricorsiva, e di lettura ricorsiva. 502 503In breve, chiamiamo "non ricorsivi" blocchi di scrittura e quelli di lettura non 504ricorsiva, mentre "ricorsivi" i blocchi di lettura ricorsivi. 505 506I blocchi ricorsivi non si bloccano a vicenda, mentre quelli non ricorsivi sì 507(anche in lettura). Un blocco di lettura non ricorsivi può bloccare uno 508ricorsivo, e viceversa. 509 510Il seguente esempio mostra uno stallo con blocchi ricorsivi:: 511 512 TASK A: TASK B: 513 514 read_lock(X); 515 read_lock(Y); 516 write_lock(Y); 517 write_lock(X); 518 519Il processo A attende che il processo B esegua read_unlock() so Y, mentre il 520processo B attende che A esegua read_unlock() su X. 521 522Tipi di dipendenze e percorsi forti 523----------------------------------- 524Le dipendenze fra blocchi tracciano l'ordine con cui una coppia di blocchi viene 525acquisita, e perché vi sono 3 tipi di bloccatori, allora avremo 9 tipi di 526dipendenze. Tuttavia, vi mostreremo che 4 sono sufficienti per individuare gli 527stalli. 528 529Per ogni dipendenza fra blocchi avremo:: 530 531 L1 -> L2 532 533Questo significa che lockdep ha visto acquisire L1 prima di L2 nello stesso 534contesto di esecuzione. Per quanto riguarda l'individuazione degli stalli, ci 535interessa sapere se possiamo rimanere bloccati da L2 mentre L1 viene trattenuto. 536In altre parole, vogliamo sapere se esiste un bloccatore L3 che viene bloccato 537da L1 e un L2 che viene bloccato da L3. Dunque, siamo interessati a (1) quello 538che L1 blocca e (2) quello che blocca L2. Di conseguenza, possiamo combinare 539lettori ricorsivi e non per L1 (perché bloccano gli stessi tipi) e possiamo 540combinare scrittori e lettori non ricorsivi per L2 (perché vengono bloccati 541dagli stessi tipi). 542 543Con questa semplificazione, possiamo dedurre che ci sono 4 tipi di rami nel 544grafo delle dipendenze di lockdep: 545 5461) -(ER)->: 547 dipendenza da scrittore esclusivo a lettore ricorsivo. "X -(ER)-> Y" 548 significa X -> Y, dove X è uno scrittore e Y un lettore ricorsivo. 549 5502) -(EN)->: 551 dipendenza da scrittore esclusivo a bloccatore non ricorsivo. 552 "X -(EN)->" significa X-> Y, dove X è uno scrittore e Y può essere 553 o uno scrittore o un lettore non ricorsivo. 554 5553) -(SR)->: 556 dipendenza da lettore condiviso a lettore ricorsivo. "X -(SR)->" 557 significa X -> Y, dove X è un lettore (ricorsivo o meno) e Y è un 558 lettore ricorsivo. 559 5604) -(SN)->: 561 dipendenza da lettore condiviso a bloccatore non ricorsivo. 562 "X -(SN)-> Y" significa X -> Y , dove X è un lettore (ricorsivo 563 o meno) e Y può essere o uno scrittore o un lettore non ricorsivo. 564 565Da notare che presi due blocchi, questi potrebbero avere più dipendenza fra di 566loro. Per esempio:: 567 568 TASK A: 569 570 read_lock(X); 571 write_lock(Y); 572 ... 573 574 TASK B: 575 576 write_lock(X); 577 write_lock(Y); 578 579Nel grafo delle dipendenze avremo sia X -(SN)-> Y che X -(EN)-> Y. 580 581Usiamo -(xN)-> per rappresentare i rami sia per -(EN)-> che -(SN)->, allo stesso 582modo -(Ex)->, -(xR)-> e -(Sx)-> 583 584Un "percorso" in un grafo è una serie di nodi e degli archi che li congiungono. 585Definiamo un percorso "forte", come il percorso che non ha archi (dipendenze) di 586tipo -(xR)-> e -(Sx)->. In altre parole, un percorso "forte" è un percorso da un 587blocco ad un altro attraverso le varie dipendenze, e se sul percorso abbiamo X 588-> Y -> Z (dove X, Y, e Z sono blocchi), e da X a Y si ha una dipendenza -(SR)-> 589o -(ER)->, allora fra Y e Z non deve esserci una dipendenza -(SN)-> o -(SR)->. 590 591Nella prossima sezione vedremo perché definiamo questo percorso "forte". 592 593Identificazione di stalli da lettura ricorsiva 594---------------------------------------------- 595Ora vogliamo dimostrare altre due cose: 596 597Lemma 1: 598 599Se esiste un percorso chiuso forte (ciclo forte), allora esiste anche una 600combinazione di sequenze di blocchi che causa uno stallo. In altre parole, 601l'esistenza di un ciclo forte è sufficiente alla scoperta di uno stallo. 602 603Lemma 2: 604 605Se non esiste un percorso chiuso forte (ciclo forte), allora non esiste una 606combinazione di sequenze di blocchi che causino uno stallo. In altre parole, i 607cicli forti sono necessari alla rilevazione degli stallo. 608 609Con questi due lemmi possiamo facilmente affermare che un percorso chiuso forte 610è sia sufficiente che necessario per avere gli stalli, dunque averli equivale 611alla possibilità di imbattersi concretamente in uno stallo. Un percorso chiuso 612forte significa che può causare stalli, per questo lo definiamo "forte", ma ci 613sono anche cicli di dipendenze che non causeranno stalli. 614 615Dimostrazione di sufficienza (lemma 1): 616 617Immaginiamo d'avere un ciclo forte:: 618 619 L1 -> L2 ... -> Ln -> L1 620 621Questo significa che abbiamo le seguenti dipendenze:: 622 623 L1 -> L2 624 L2 -> L3 625 ... 626 Ln-1 -> Ln 627 Ln -> L1 628 629Ora possiamo costruire una combinazione di sequenze di blocchi che causano lo 630stallo. 631 632Per prima cosa facciamo sì che un processo/processore prenda L1 in L1 -> L2, poi 633un altro prende L2 in L2 -> L3, e così via. Alla fine, tutti i Lx in Lx -> Lx+1 634saranno trattenuti da processi/processori diversi. 635 636Poi visto che abbiamo L1 -> L2, chi trattiene L1 vorrà acquisire L2 in L1 -> L2, 637ma prima dovrà attendere che venga rilasciato da chi lo trattiene. Questo perché 638L2 è già trattenuto da un altro processo/processore, ed in più L1 -> L2 e L2 -> 639L3 non sono -(xR)-> né -(Sx)-> (la definizione di forte). Questo significa che L2 640in L1 -> L2 non è un bloccatore non ricorsivo (bloccabile da chiunque), e L2 in 641L2 -> L3 non è uno scrittore (che blocca chiunque). 642 643In aggiunta, possiamo trarre una simile conclusione per chi sta trattenendo L2: 644deve aspettare che L3 venga rilasciato, e così via. Ora possiamo dimostrare che 645chi trattiene Lx deve aspettare che Lx+1 venga rilasciato. Notiamo che Ln+1 è 646L1, dunque si è creato un ciclo dal quale non possiamo uscire, quindi si ha uno 647stallo. 648 649Dimostrazione della necessità (lemma 2): 650 651Questo lemma equivale a dire che: se siamo in uno scenario di stallo, allora 652deve esiste un ciclo forte nel grafo delle dipendenze. 653 654Secondo Wikipedia[1], se c'è uno stallo, allora deve esserci un ciclo di attese, 655ovvero ci sono N processi/processori dove P1 aspetta un blocco trattenuto da P2, 656e P2 ne aspetta uno trattenuto da P3, ... e Pn attende che il blocco P1 venga 657rilasciato. Chiamiamo Lx il blocco che attende Px, quindi P1 aspetta L1 e 658trattiene Ln. Quindi avremo Ln -> L1 nel grafo delle dipendenze. Similarmente, 659nel grafo delle dipendenze avremo L1 -> L2, L2 -> L3, ..., Ln-1 -> Ln, il che 660significa che abbiamo un ciclo:: 661 662 Ln -> L1 -> L2 -> ... -> Ln 663 664, ed ora dimostriamo d'avere un ciclo forte. 665 666Per un blocco Lx, il processo Px contribuisce alla dipendenza Lx-1 -> Lx e Px+1 667contribuisce a quella Lx -> Lx+1. Visto che Px aspetta che Px+1 rilasci Lx, sarà 668impossibile che Lx in Px+1 sia un lettore e che Lx in Px sia un lettore 669ricorsivo. Questo perché i lettori (ricorsivi o meno) non bloccano lettori 670ricorsivi. Dunque, Lx-1 -> Lx e Lx -> Lx+1 non possono essere una coppia di 671-(xR)-> -(Sx)->. Questo è vero per ogni ciclo, dunque, questo è un ciclo forte. 672 673Riferimenti 674----------- 675 676[1]: https://it.wikipedia.org/wiki/Stallo_(informatica) 677 678[2]: Shibu, K. (2009). Intro To Embedded Systems (1st ed.). Tata McGraw-Hill 679