summaryrefslogtreecommitdiffstats
path: root/Documentation/translations/it_IT/locking/lockdep-design.rst
diff options
context:
space:
mode:
Diffstat (limited to 'Documentation/translations/it_IT/locking/lockdep-design.rst')
-rw-r--r--Documentation/translations/it_IT/locking/lockdep-design.rst678
1 files changed, 678 insertions, 0 deletions
diff --git a/Documentation/translations/it_IT/locking/lockdep-design.rst b/Documentation/translations/it_IT/locking/lockdep-design.rst
new file mode 100644
index 0000000000..9ed00d8cf2
--- /dev/null
+++ b/Documentation/translations/it_IT/locking/lockdep-design.rst
@@ -0,0 +1,678 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+.. include:: ../disclaimer-ita.rst
+
+Validatore di sincronizzazione durante l'esecuzione
+===================================================
+
+Classi di blocchi
+-----------------
+
+L'oggetto su cui il validatore lavora è una "classe" di blocchi.
+
+Una classe di blocchi è un gruppo di blocchi che seguono le stesse regole di
+sincronizzazione, anche quando i blocchi potrebbero avere più istanze (anche
+decine di migliaia). Per esempio un blocco nella struttura inode è una classe,
+mentre ogni inode sarà un'istanza di questa classe di blocco.
+
+Il validatore traccia lo "stato d'uso" di una classe di blocchi e le sue
+dipendenze con altre classi. L'uso di un blocco indica come quel blocco viene
+usato rispetto al suo contesto d'interruzione, mentre le dipendenze di un blocco
+possono essere interpretate come il loro ordine; per esempio L1 -> L2 suggerisce
+che un processo cerca di acquisire L2 mentre già trattiene L1. Dal punto di
+vista di lockdep, i due blocchi (L1 ed L2) non sono per forza correlati: quella
+dipendenza indica solamente l'ordine in cui sono successe le cose. Il validatore
+verifica permanentemente la correttezza dell'uso dei blocchi e delle loro
+dipendenze, altrimenti ritornerà un errore.
+
+Il comportamento di una classe di blocchi viene costruito dall'insieme delle sue
+istanze. Una classe di blocco viene registrata alla creazione della sua prima
+istanza, mentre tutte le successive istanze verranno mappate; dunque, il loro
+uso e le loro dipendenze contribuiranno a costruire quello della classe. Una
+classe di blocco non sparisce quando sparisce una sua istanza, ma può essere
+rimossa quando il suo spazio in memoria viene reclamato. Per esempio, questo
+succede quando si rimuove un modulo, o quando una *workqueue* viene eliminata.
+
+Stato
+-----
+
+Il validatore traccia l'uso cronologico delle classi di blocchi e ne divide
+l'uso in categorie (4 USI * n STATI + 1).
+
+I quattro USI possono essere:
+
+- 'sempre trattenuto nel contesto <STATO>'
+- 'sempre trattenuto come blocco di lettura nel contesto <STATO>'
+- 'sempre trattenuto con <STATO> abilitato'
+- 'sempre trattenuto come blocco di lettura con <STATO> abilitato'
+
+gli `n` STATI sono codificati in kernel/locking/lockdep_states.h, ad oggi
+includono:
+
+- hardirq
+- softirq
+
+infine l'ultima categoria è:
+
+- 'sempre trattenuto' [ == !unused ]
+
+Quando vengono violate le regole di sincronizzazione, questi bit di utilizzo
+vengono presentati nei messaggi di errore di sincronizzazione, fra parentesi
+graffe, per un totale di `2 * n` (`n`: bit STATO). Un esempio inventato::
+
+ modprobe/2287 is trying to acquire lock:
+ (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
+
+ but task is already holding lock:
+ (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
+
+Per un dato blocco, da sinistra verso destra, la posizione del bit indica l'uso
+del blocco e di un eventuale blocco di lettura, per ognuno degli `n` STATI elencati
+precedentemente. Il carattere mostrato per ogni bit indica:
+
+ === ===========================================================================
+ '.' acquisito con interruzioni disabilitate fuori da un contesto d'interruzione
+ '-' acquisito in contesto d'interruzione
+ '+' acquisito con interruzioni abilitate
+ '?' acquisito in contesto d'interruzione con interruzioni abilitate
+ === ===========================================================================
+
+Il seguente esempio mostra i bit::
+
+ (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
+ ||||
+ ||| \-> softirq disabilitati e fuori da un contesto di softirq
+ || \--> acquisito in un contesto di softirq
+ | \---> hardirq disabilitati e fuori da un contesto di hardirq
+ \----> acquisito in un contesto di hardirq
+
+Per un dato STATO, che il blocco sia mai stato acquisito in quel contesto di
+STATO, o che lo STATO sia abilitato, ci lascia coi quattro possibili scenari
+mostrati nella seguente tabella. Il carattere associato al bit indica con
+esattezza in quale scenario ci si trova al momento del rapporto.
+
+ +---------------+---------------+------------------+
+ | | irq abilitati | irq disabilitati |
+ +---------------+---------------+------------------+
+ | sempre in irq | '?' | '-' |
+ +---------------+---------------+------------------+
+ | mai in irq | '+' | '.' |
+ +---------------+---------------+------------------+
+
+Il carattere '-' suggerisce che le interruzioni sono disabilitate perché
+altrimenti verrebbe mostrato il carattere '?'. Una deduzione simile può essere
+fatta anche per '+'
+
+I blocchi inutilizzati (ad esempio i mutex) non possono essere fra le cause di
+un errore.
+
+Regole dello stato per un blocco singolo
+----------------------------------------
+
+Avere un blocco sicuro in interruzioni (*irq-safe*) significa che è sempre stato
+usato in un contesto d'interruzione, mentre un blocco insicuro in interruzioni
+(*irq-unsafe*) significa che è sempre stato acquisito con le interruzioni
+abilitate.
+
+Una classe softirq insicura è automaticamente insicura anche per hardirq. I
+seguenti stati sono mutualmente esclusivi: solo una può essere vero quando viene
+usata una classe di blocco::
+
+ <hardirq-safe> o <hardirq-unsafe>
+ <softirq-safe> o <softirq-unsafe>
+
+Questo perché se un blocco può essere usato in un contesto di interruzioni
+(sicuro in interruzioni), allora non può mai essere acquisito con le
+interruzioni abilitate (insicuro in interruzioni). Altrimenti potrebbe
+verificarsi uno stallo. Per esempio, questo blocco viene acquisito, ma prima di
+essere rilasciato il contesto d'esecuzione viene interrotto nuovamente, e quindi
+si tenterà di acquisirlo nuovamente. Questo porterà ad uno stallo, in
+particolare uno stallo ricorsivo.
+
+Il validatore rileva e riporta gli usi di blocchi che violano queste regole per
+blocchi singoli.
+
+Regole per le dipendenze di blocchi multipli
+--------------------------------------------
+
+La stessa classe di blocco non deve essere acquisita due volte, questo perché
+potrebbe portare ad uno blocco ricorsivo e dunque ad uno stallo.
+
+Inoltre, due blocchi non possono essere trattenuti in ordine inverso::
+
+ <L1> -> <L2>
+ <L2> -> <L1>
+
+perché porterebbe ad uno stallo - chiamato stallo da blocco inverso - in cui si
+cerca di trattenere i due blocchi in un ciclo in cui entrambe i contesti
+aspettano per sempre che l'altro termini. Il validatore è in grado di trovare
+queste dipendenze cicliche di qualsiasi complessità, ovvero nel mezzo ci
+potrebbero essere altre sequenze di blocchi. Il validatore troverà se questi
+blocchi possono essere acquisiti circolarmente.
+
+In aggiunta, le seguenti sequenze di blocco nei contesti indicati non sono
+permesse, indipendentemente da quale che sia la classe di blocco::
+
+ <hardirq-safe> -> <hardirq-unsafe>
+ <softirq-safe> -> <softirq-unsafe>
+
+La prima regola deriva dal fatto che un blocco sicuro in interruzioni può essere
+trattenuto in un contesto d'interruzione che, per definizione, ha la possibilità
+di interrompere un blocco insicuro in interruzioni; questo porterebbe ad uno
+stallo da blocco inverso. La seconda, analogamente, ci dice che un blocco sicuro
+in interruzioni software potrebbe essere trattenuto in un contesto di
+interruzione software, dunque potrebbe interrompere un blocco insicuro in
+interruzioni software.
+
+Le suddette regole vengono applicate per qualsiasi sequenza di blocchi: quando
+si acquisiscono nuovi blocchi, il validatore verifica se vi è una violazione
+delle regole fra il nuovo blocco e quelli già trattenuti.
+
+Quando una classe di blocco cambia stato, applicheremo le seguenti regole:
+
+- se viene trovato un nuovo blocco sicuro in interruzioni, verificheremo se
+ abbia mai trattenuto dei blocchi insicuri in interruzioni.
+
+- se viene trovato un nuovo blocco sicuro in interruzioni software,
+ verificheremo se abbia trattenuto dei blocchi insicuri in interruzioni
+ software.
+
+- se viene trovato un nuovo blocco insicuro in interruzioni, verificheremo se
+ abbia trattenuto dei blocchi sicuri in interruzioni.
+
+- se viene trovato un nuovo blocco insicuro in interruzioni software,
+ verificheremo se abbia trattenuto dei blocchi sicuri in interruzioni
+ software.
+
+(Di nuovo, questi controlli vengono fatti perché un contesto d'interruzione
+potrebbe interrompere l'esecuzione di qualsiasi blocco insicuro portando ad uno
+stallo; questo anche se lo stallo non si verifica in pratica)
+
+Eccezione: dipendenze annidate sui dati portano a blocchi annidati
+------------------------------------------------------------------
+
+Ci sono alcuni casi in cui il kernel Linux acquisisce più volte la stessa
+istanza di una classe di blocco. Solitamente, questo succede quando esiste una
+gerarchia fra oggetti dello stesso tipo. In questi casi viene ereditato
+implicitamente l'ordine fra i due oggetti (definito dalle proprietà di questa
+gerarchia), ed il kernel tratterrà i blocchi in questo ordine prefissato per
+ognuno degli oggetti.
+
+Un esempio di questa gerarchia di oggetti che producono "blocchi annidati" sono
+i *block-dev* che rappresentano l'intero disco e quelli che rappresentano una
+sua partizione; la partizione è una parte del disco intero, e l'ordine dei
+blocchi sarà corretto fintantoche uno acquisisce il blocco del disco intero e
+poi quello della partizione. Il validatore non rileva automaticamente questo
+ordine implicito, perché queste regole di sincronizzazione non sono statiche.
+
+Per istruire il validatore riguardo a questo uso corretto dei blocchi sono stati
+introdotte nuove primitive per specificare i "livelli di annidamento". Per
+esempio, per i blocchi a mutua esclusione dei *block-dev* si avrebbe una
+chiamata simile a::
+
+ enum bdev_bd_mutex_lock_class
+ {
+ BD_MUTEX_NORMAL,
+ BD_MUTEX_WHOLE,
+ BD_MUTEX_PARTITION
+ };
+
+ mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION);
+
+In questo caso la sincronizzazione viene fatta su un *block-dev* sapendo che si
+tratta di una partizione.
+
+Ai fini della validazione, il validatore lo considererà con una - sotto - classe
+di blocco separata.
+
+Nota: Prestate estrema attenzione che la vostra gerarchia sia corretta quando si
+vogliono usare le primitive _nested(); altrimenti potreste avere sia falsi
+positivi che falsi negativi.
+
+Annotazioni
+-----------
+
+Si possono utilizzare due costrutti per verificare ed annotare se certi blocchi
+devono essere trattenuti: lockdep_assert_held*(&lock) e
+lockdep_*pin_lock(&lock).
+
+Come suggerito dal nome, la famiglia di macro lockdep_assert_held* asseriscono
+che un dato blocco in un dato momento deve essere trattenuto (altrimenti, verrà
+generato un WARN()). Queste vengono usate abbondantemente nel kernel, per
+esempio in kernel/sched/core.c::
+
+ void update_rq_clock(struct rq *rq)
+ {
+ s64 delta;
+
+ lockdep_assert_held(&rq->lock);
+ [...]
+ }
+
+dove aver trattenuto rq->lock è necessario per aggiornare in sicurezza il clock
+rq.
+
+L'altra famiglia di macro è lockdep_*pin_lock(), che a dire il vero viene usata
+solo per rq->lock ATM. Se per caso un blocco non viene trattenuto, queste
+genereranno un WARN(). Questo si rivela particolarmente utile quando si deve
+verificare la correttezza di codice con *callback*, dove livelli superiori
+potrebbero assumere che un blocco rimanga trattenuto, ma livelli inferiori
+potrebbero invece pensare che il blocco possa essere rilasciato e poi
+riacquisito (involontariamente si apre una sezione critica). lockdep_pin_lock()
+restituisce 'struct pin_cookie' che viene usato da lockdep_unpin_lock() per
+verificare che nessuno abbia manomesso il blocco. Per esempio in
+kernel/sched/sched.h abbiamo::
+
+ static inline void rq_pin_lock(struct rq *rq, struct rq_flags *rf)
+ {
+ rf->cookie = lockdep_pin_lock(&rq->lock);
+ [...]
+ }
+
+ static inline void rq_unpin_lock(struct rq *rq, struct rq_flags *rf)
+ {
+ [...]
+ lockdep_unpin_lock(&rq->lock, rf->cookie);
+ }
+
+I commenti riguardo alla sincronizzazione possano fornire informazioni utili,
+tuttavia sono le verifiche in esecuzione effettuate da queste macro ad essere
+vitali per scovare problemi di sincronizzazione, ed inoltre forniscono lo stesso
+livello di informazioni quando si ispeziona il codice. Nel dubbio, preferite
+queste annotazioni!
+
+Dimostrazione di correttezza al 100%
+------------------------------------
+
+Il validatore verifica la proprietà di chiusura in senso matematico. Ovvero, per
+ogni sequenza di sincronizzazione di un singolo processo che si verifichi almeno
+una volta nel kernel, il validatore dimostrerà con una certezza del 100% che
+nessuna combinazione e tempistica di queste sequenze possa causare uno stallo in
+una qualsiasi classe di blocco. [1]_
+
+In pratica, per dimostrare l'esistenza di uno stallo non servono complessi
+scenari di sincronizzazione multi-processore e multi-processo. Il validatore può
+dimostrare la correttezza basandosi sulla sola sequenza di sincronizzazione
+apparsa almeno una volta (in qualunque momento, in qualunque processo o
+contesto). Uno scenario complesso che avrebbe bisogno di 3 processori e una
+sfortunata presenza di processi, interruzioni, e pessimo tempismo, può essere
+riprodotto su un sistema a singolo processore.
+
+Questo riduce drasticamente la complessità del controllo di qualità della
+sincronizzazione nel kernel: quello che deve essere fatto è di innescare nel
+kernel quante più possibili "semplici" sequenze di sincronizzazione, almeno una
+volta, allo scopo di dimostrarne la correttezza. Questo al posto di innescare
+una verifica per ogni possibile combinazione di sincronizzazione fra processori,
+e differenti scenari con hardirq e softirq e annidamenti vari (nella pratica,
+impossibile da fare)
+
+.. [1]
+
+ assumendo che il validatore sia corretto al 100%, e che nessun altra parte
+ del sistema possa corromperne lo stato. Assumiamo anche che tutti i percorsi
+ MNI/SMM [potrebbero interrompere anche percorsi dove le interruzioni sono
+ disabilitate] sono corretti e non interferiscono con il validatore. Inoltre,
+ assumiamo che un hash a 64-bit sia unico per ogni sequenza di
+ sincronizzazione nel sistema. Infine, la ricorsione dei blocchi non deve
+ essere maggiore di 20.
+
+Prestazione
+-----------
+
+Le regole sopracitate hanno bisogno di una quantità **enorme** di verifiche
+durante l'esecuzione. Il sistema sarebbe diventato praticamente inutilizzabile
+per la sua lentezza se le avessimo fatte davvero per ogni blocco trattenuto e
+per ogni abilitazione delle interruzioni. La complessità della verifica è
+O(N^2), quindi avremmo dovuto fare decine di migliaia di verifiche per ogni
+evento, il tutto per poche centinaia di classi.
+
+Il problema è stato risolto facendo una singola verifica per ogni 'scenario di
+sincronizzazione' (una sequenza unica di blocchi trattenuti uno dopo l'altro).
+Per farlo, viene mantenuta una pila dei blocchi trattenuti, e viene calcolato un
+hash a 64-bit unico per ogni sequenza. Quando la sequenza viene verificata per
+la prima volta, l'hash viene inserito in una tabella hash. La tabella potrà
+essere verificata senza bisogno di blocchi. Se la sequenza dovesse ripetersi, la
+tabella ci dirà che non è necessario verificarla nuovamente.
+
+Risoluzione dei problemi
+------------------------
+
+Il massimo numero di classi di blocco che il validatore può tracciare è:
+MAX_LOCKDEP_KEYS. Oltrepassare questo limite indurrà lokdep a generare il
+seguente avviso::
+
+ (DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))
+
+Di base questo valore è 8191, e un classico sistema da ufficio ha meno di 1000
+classi, dunque questo avviso è solitamente la conseguenza di un problema di
+perdita delle classi di blocco o d'inizializzazione dei blocchi. Di seguito una
+descrizione dei due problemi:
+
+1. caricare e rimuovere continuamente i moduli mentre il validatore è in
+ esecuzione porterà ad una perdita di classi di blocco. Il problema è che ogni
+ caricamento crea un nuovo insieme di classi di blocco per tutti i blocchi di
+ quel modulo. Tuttavia, la rimozione del modulo non rimuove le vecchie classi
+ (vedi dopo perché non le riusiamo). Dunque, il continuo caricamento e
+ rimozione di un modulo non fa altro che aumentare il contatore di classi fino
+ a raggiungere, eventualmente, il limite.
+
+2. Usare array con un gran numero di blocchi che non vengono esplicitamente
+ inizializzati. Per esempio, una tabella hash con 8192 *bucket* dove ognuno ha
+ il proprio spinlock_t consumerà 8192 classi di blocco a meno che non vengano
+ esplicitamente inizializzati in esecuzione usando spin_lock_init() invece
+ dell'inizializzazione durante la compilazione con __SPIN_LOCK_UNLOCKED().
+ Sbagliare questa inizializzazione garantisce un esaurimento di classi di
+ blocco. Viceversa, un ciclo che invoca spin_lock_init() su tutti i blocchi li
+ mapperebbe tutti alla stessa classe di blocco.
+
+ La morale della favola è che dovete sempre inizializzare esplicitamente i
+ vostri blocchi.
+
+Qualcuno potrebbe argomentare che il validatore debba permettere il riuso di
+classi di blocco. Tuttavia, se siete tentati dall'argomento, prima revisionate
+il codice e pensate alla modifiche necessarie, e tenendo a mente che le classi
+di blocco da rimuovere probabilmente sono legate al grafo delle dipendenze. Più
+facile a dirsi che a farsi.
+
+Ovviamente, se non esaurite le classi di blocco, la prossima cosa da fare è
+quella di trovare le classi non funzionanti. Per prima cosa, il seguente comando
+ritorna il numero di classi attualmente in uso assieme al valore massimo::
+
+ grep "lock-classes" /proc/lockdep_stats
+
+Questo comando produce il seguente messaggio::
+
+ lock-classes: 748 [max: 8191]
+
+Se il numero di assegnazioni (748 qui sopra) aumenta continuamente nel tempo,
+allora c'è probabilmente un problema da qualche parte. Il seguente comando può
+essere utilizzato per identificare le classi di blocchi problematiche::
+
+ grep "BD" /proc/lockdep
+
+Eseguite il comando e salvatene l'output, quindi confrontatelo con l'output di
+un'esecuzione successiva per identificare eventuali problemi. Questo stesso
+output può anche aiutarti a trovare situazioni in cui l'inizializzazione del
+blocco è stata omessa.
+
+Lettura ricorsiva dei blocchi
+-----------------------------
+
+Il resto di questo documento vuole dimostrare che certi cicli equivalgono ad una
+possibilità di stallo.
+
+Ci sono tre tipi di bloccatori: gli scrittori (bloccatori esclusivi, come
+spin_lock() o write_lock()), lettori non ricorsivi (bloccatori condivisi, come
+down_read()), e lettori ricorsivi (bloccatori condivisi ricorsivi, come
+rcu_read_lock()). D'ora in poi, per questi tipi di bloccatori, useremo la
+seguente notazione:
+
+ W o E: per gli scrittori (bloccatori esclusivi) (W dall'inglese per
+ *Writer*, ed E per *Exclusive*).
+
+ r: per i lettori non ricorsivi (r dall'inglese per *reader*).
+
+ R: per i lettori ricorsivi (R dall'inglese per *Reader*).
+
+ S: per qualsiasi lettore (non ricorsivi + ricorsivi), dato che entrambe
+ sono bloccatori condivisi (S dall'inglese per *Shared*).
+
+ N: per gli scrittori ed i lettori non ricorsivi, dato che entrambe sono
+ non ricorsivi.
+
+Ovviamente, N equivale a "r o W" ed S a "r o R".
+
+Come suggerisce il nome, i lettori ricorsivi sono dei bloccatori a cui è
+permesso di acquisire la stessa istanza di blocco anche all'interno della
+sezione critica di un altro lettore. In altre parole, permette di annidare la
+stessa istanza di blocco nelle sezioni critiche dei lettori.
+
+Dall'altro canto, lo stesso comportamento indurrebbe un lettore non ricorsivo ad
+auto infliggersi uno stallo.
+
+La differenza fra questi due tipi di lettori esiste perché: quelli ricorsivi
+vengono bloccati solo dal trattenimento di un blocco di scrittura, mentre quelli
+non ricorsivi possono essere bloccati dall'attesa di un blocco di scrittura.
+Consideriamo il seguente esempio::
+
+ TASK A: TASK B:
+
+ read_lock(X);
+ write_lock(X);
+ read_lock_2(X);
+
+L'attività A acquisisce il blocco di lettura X (non importa se di tipo ricorsivo
+o meno) usando read_lock(). Quando l'attività B tenterà di acquisire il blocco
+X, si fermerà e rimarrà in attesa che venga rilasciato. Ora se read_lock_2() è
+un tipo lettore ricorsivo, l'attività A continuerà perché gli scrittori in
+attesa non possono bloccare lettori ricorsivi, e non avremo alcuno stallo.
+Tuttavia, se read_lock_2() è un lettore non ricorsivo, allora verrà bloccato
+dall'attività B e si causerà uno stallo.
+
+Condizioni bloccanti per lettori/scrittori su uno stesso blocco
+---------------------------------------------------------------
+Essenzialmente ci sono quattro condizioni bloccanti:
+
+1. Uno scrittore blocca un altro scrittore.
+2. Un lettore blocca uno scrittore.
+3. Uno scrittore blocca sia i lettori ricorsivi che non ricorsivi.
+4. Un lettore (ricorsivo o meno) non blocca altri lettori ricorsivi ma potrebbe
+ bloccare quelli non ricorsivi (perché potrebbero esistere degli scrittori in
+ attesa).
+
+Di seguito le tabella delle condizioni bloccanti, Y (*Yes*) significa che il
+tipo in riga blocca quello in colonna, mentre N l'opposto.
+
+ +---+---+---+---+
+ | | W | r | R |
+ +---+---+---+---+
+ | W | Y | Y | Y |
+ +---+---+---+---+
+ | r | Y | Y | N |
+ +---+---+---+---+
+ | R | Y | Y | N |
+ +---+---+---+---+
+
+ (W: scrittori, r: lettori non ricorsivi, R: lettori ricorsivi)
+
+Al contrario dei blocchi per lettori non ricorsivi, quelli ricorsivi vengono
+trattenuti da chi trattiene il blocco di scrittura piuttosto che da chi ne
+attende il rilascio. Per esempio::
+
+ TASK A: TASK B:
+
+ read_lock(X);
+
+ write_lock(X);
+
+ read_lock(X);
+
+non produce uno stallo per i lettori ricorsivi, in quanto il processo B rimane
+in attesta del blocco X, mentre il secondo read_lock() non ha bisogno di
+aspettare perché si tratta di un lettore ricorsivo. Tuttavia, se read_lock()
+fosse un lettore non ricorsivo, questo codice produrrebbe uno stallo.
+
+Da notare che in funzione dell'operazione di blocco usate per l'acquisizione (in
+particolare il valore del parametro 'read' in lock_acquire()), un blocco può
+essere di scrittura (blocco esclusivo), di lettura non ricorsivo (blocco
+condiviso e non ricorsivo), o di lettura ricorsivo (blocco condiviso e
+ricorsivo). In altre parole, per un'istanza di blocco esistono tre tipi di
+acquisizione che dipendono dalla funzione di acquisizione usata: esclusiva, di
+lettura non ricorsiva, e di lettura ricorsiva.
+
+In breve, chiamiamo "non ricorsivi" blocchi di scrittura e quelli di lettura non
+ricorsiva, mentre "ricorsivi" i blocchi di lettura ricorsivi.
+
+I blocchi ricorsivi non si bloccano a vicenda, mentre quelli non ricorsivi sì
+(anche in lettura). Un blocco di lettura non ricorsivi può bloccare uno
+ricorsivo, e viceversa.
+
+Il seguente esempio mostra uno stallo con blocchi ricorsivi::
+
+ TASK A: TASK B:
+
+ read_lock(X);
+ read_lock(Y);
+ write_lock(Y);
+ write_lock(X);
+
+Il processo A attende che il processo B esegua read_unlock() so Y, mentre il
+processo B attende che A esegua read_unlock() su X.
+
+Tipi di dipendenze e percorsi forti
+-----------------------------------
+Le dipendenze fra blocchi tracciano l'ordine con cui una coppia di blocchi viene
+acquisita, e perché vi sono 3 tipi di bloccatori, allora avremo 9 tipi di
+dipendenze. Tuttavia, vi mostreremo che 4 sono sufficienti per individuare gli
+stalli.
+
+Per ogni dipendenza fra blocchi avremo::
+
+ L1 -> L2
+
+Questo significa che lockdep ha visto acquisire L1 prima di L2 nello stesso
+contesto di esecuzione. Per quanto riguarda l'individuazione degli stalli, ci
+interessa sapere se possiamo rimanere bloccati da L2 mentre L1 viene trattenuto.
+In altre parole, vogliamo sapere se esiste un bloccatore L3 che viene bloccato
+da L1 e un L2 che viene bloccato da L3. Dunque, siamo interessati a (1) quello
+che L1 blocca e (2) quello che blocca L2. Di conseguenza, possiamo combinare
+lettori ricorsivi e non per L1 (perché bloccano gli stessi tipi) e possiamo
+combinare scrittori e lettori non ricorsivi per L2 (perché vengono bloccati
+dagli stessi tipi).
+
+Con questa semplificazione, possiamo dedurre che ci sono 4 tipi di rami nel
+grafo delle dipendenze di lockdep:
+
+1) -(ER)->:
+ dipendenza da scrittore esclusivo a lettore ricorsivo. "X -(ER)-> Y"
+ significa X -> Y, dove X è uno scrittore e Y un lettore ricorsivo.
+
+2) -(EN)->:
+ dipendenza da scrittore esclusivo a bloccatore non ricorsivo.
+ "X -(EN)->" significa X-> Y, dove X è uno scrittore e Y può essere
+ o uno scrittore o un lettore non ricorsivo.
+
+3) -(SR)->:
+ dipendenza da lettore condiviso a lettore ricorsivo. "X -(SR)->"
+ significa X -> Y, dove X è un lettore (ricorsivo o meno) e Y è un
+ lettore ricorsivo.
+
+4) -(SN)->:
+ dipendenza da lettore condiviso a bloccatore non ricorsivo.
+ "X -(SN)-> Y" significa X -> Y , dove X è un lettore (ricorsivo
+ o meno) e Y può essere o uno scrittore o un lettore non ricorsivo.
+
+Da notare che presi due blocchi, questi potrebbero avere più dipendenza fra di
+loro. Per esempio::
+
+ TASK A:
+
+ read_lock(X);
+ write_lock(Y);
+ ...
+
+ TASK B:
+
+ write_lock(X);
+ write_lock(Y);
+
+Nel grafo delle dipendenze avremo sia X -(SN)-> Y che X -(EN)-> Y.
+
+Usiamo -(xN)-> per rappresentare i rami sia per -(EN)-> che -(SN)->, allo stesso
+modo -(Ex)->, -(xR)-> e -(Sx)->
+
+Un "percorso" in un grafo è una serie di nodi e degli archi che li congiungono.
+Definiamo un percorso "forte", come il percorso che non ha archi (dipendenze) di
+tipo -(xR)-> e -(Sx)->. In altre parole, un percorso "forte" è un percorso da un
+blocco ad un altro attraverso le varie dipendenze, e se sul percorso abbiamo X
+-> Y -> Z (dove X, Y, e Z sono blocchi), e da X a Y si ha una dipendenza -(SR)->
+o -(ER)->, allora fra Y e Z non deve esserci una dipendenza -(SN)-> o -(SR)->.
+
+Nella prossima sezione vedremo perché definiamo questo percorso "forte".
+
+Identificazione di stalli da lettura ricorsiva
+----------------------------------------------
+Ora vogliamo dimostrare altre due cose:
+
+Lemma 1:
+
+Se esiste un percorso chiuso forte (ciclo forte), allora esiste anche una
+combinazione di sequenze di blocchi che causa uno stallo. In altre parole,
+l'esistenza di un ciclo forte è sufficiente alla scoperta di uno stallo.
+
+Lemma 2:
+
+Se non esiste un percorso chiuso forte (ciclo forte), allora non esiste una
+combinazione di sequenze di blocchi che causino uno stallo. In altre parole, i
+cicli forti sono necessari alla rilevazione degli stallo.
+
+Con questi due lemmi possiamo facilmente affermare che un percorso chiuso forte
+è sia sufficiente che necessario per avere gli stalli, dunque averli equivale
+alla possibilità di imbattersi concretamente in uno stallo. Un percorso chiuso
+forte significa che può causare stalli, per questo lo definiamo "forte", ma ci
+sono anche cicli di dipendenze che non causeranno stalli.
+
+Dimostrazione di sufficienza (lemma 1):
+
+Immaginiamo d'avere un ciclo forte::
+
+ L1 -> L2 ... -> Ln -> L1
+
+Questo significa che abbiamo le seguenti dipendenze::
+
+ L1 -> L2
+ L2 -> L3
+ ...
+ Ln-1 -> Ln
+ Ln -> L1
+
+Ora possiamo costruire una combinazione di sequenze di blocchi che causano lo
+stallo.
+
+Per prima cosa facciamo sì che un processo/processore prenda L1 in L1 -> L2, poi
+un altro prende L2 in L2 -> L3, e così via. Alla fine, tutti i Lx in Lx -> Lx+1
+saranno trattenuti da processi/processori diversi.
+
+Poi visto che abbiamo L1 -> L2, chi trattiene L1 vorrà acquisire L2 in L1 -> L2,
+ma prima dovrà attendere che venga rilasciato da chi lo trattiene. Questo perché
+L2 è già trattenuto da un altro processo/processore, ed in più L1 -> L2 e L2 ->
+L3 non sono -(xR)-> né -(Sx)-> (la definizione di forte). Questo significa che L2
+in L1 -> L2 non è un bloccatore non ricorsivo (bloccabile da chiunque), e L2 in
+L2 -> L3 non è uno scrittore (che blocca chiunque).
+
+In aggiunta, possiamo trarre una simile conclusione per chi sta trattenendo L2:
+deve aspettare che L3 venga rilasciato, e così via. Ora possiamo dimostrare che
+chi trattiene Lx deve aspettare che Lx+1 venga rilasciato. Notiamo che Ln+1 è
+L1, dunque si è creato un ciclo dal quale non possiamo uscire, quindi si ha uno
+stallo.
+
+Dimostrazione della necessità (lemma 2):
+
+Questo lemma equivale a dire che: se siamo in uno scenario di stallo, allora
+deve esiste un ciclo forte nel grafo delle dipendenze.
+
+Secondo Wikipedia[1], se c'è uno stallo, allora deve esserci un ciclo di attese,
+ovvero ci sono N processi/processori dove P1 aspetta un blocco trattenuto da P2,
+e P2 ne aspetta uno trattenuto da P3, ... e Pn attende che il blocco P1 venga
+rilasciato. Chiamiamo Lx il blocco che attende Px, quindi P1 aspetta L1 e
+trattiene Ln. Quindi avremo Ln -> L1 nel grafo delle dipendenze. Similarmente,
+nel grafo delle dipendenze avremo L1 -> L2, L2 -> L3, ..., Ln-1 -> Ln, il che
+significa che abbiamo un ciclo::
+
+ Ln -> L1 -> L2 -> ... -> Ln
+
+, ed ora dimostriamo d'avere un ciclo forte.
+
+Per un blocco Lx, il processo Px contribuisce alla dipendenza Lx-1 -> Lx e Px+1
+contribuisce a quella Lx -> Lx+1. Visto che Px aspetta che Px+1 rilasci Lx, sarà
+impossibile che Lx in Px+1 sia un lettore e che Lx in Px sia un lettore
+ricorsivo. Questo perché i lettori (ricorsivi o meno) non bloccano lettori
+ricorsivi. Dunque, Lx-1 -> Lx e Lx -> Lx+1 non possono essere una coppia di
+-(xR)-> -(Sx)->. Questo è vero per ogni ciclo, dunque, questo è un ciclo forte.
+
+Riferimenti
+-----------
+
+[1]: https://it.wikipedia.org/wiki/Stallo_(informatica)
+
+[2]: Shibu, K. (2009). Intro To Embedded Systems (1st ed.). Tata McGraw-Hill