Lines Matching +full:un +full:-
1 .. SPDX-License-Identifier: GPL-2.0
3 .. include:: ../disclaimer-ita.rst
9 -----------------
13 Una classe di blocchi è un gruppo di blocchi che seguono le stesse regole di
15 decine di migliaia). Per esempio un blocco nella struttura inode è una classe,
16 mentre ogni inode sarà un'istanza di questa classe di blocco.
19 dipendenze con altre classi. L'uso di un blocco indica come quel blocco viene
20 usato rispetto al suo contesto d'interruzione, mentre le dipendenze di un blocco
21 possono essere interpretate come il loro ordine; per esempio L1 -> L2 suggerisce
22 che un processo cerca di acquisire L2 mentre già trattiene L1. Dal punto di
26 dipendenze, altrimenti ritornerà un errore.
34 succede quando si rimuove un modulo, o quando una *workqueue* viene eliminata.
37 -----
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'
52 - hardirq
53 - softirq
57 - 'sempre trattenuto' [ == !unused ]
61 graffe, per un totale di `2 * n` (`n`: bit STATO). Un esempio inventato::
64 (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
67 (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
69 Per un dato blocco, da sinistra verso destra, la posizione del bit indica l'uso
70 del blocco e di un eventuale blocco di lettura, per ognuno degli `n` STATI elencati
74 '.' acquisito con interruzioni disabilitate fuori da un contesto d'interruzione
75 '-' acquisito in contesto d'interruzione
82 (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
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
89 Per un dato STATO, che il blocco sia mai stato acquisito in quel contesto di
94 +---------------+---------------+------------------+
96 +---------------+---------------+------------------+
97 | sempre in irq | '?' | '-' |
98 +---------------+---------------+------------------+
100 +---------------+---------------+------------------+
102 Il carattere '-' suggerisce che le interruzioni sono disabilitate perché
107 un errore.
109 Regole dello stato per un blocco singolo
110 ----------------------------------------
112 Avere un blocco sicuro in interruzioni (*irq-safe*) significa che è sempre stato
113 usato in un contesto d'interruzione, mentre un blocco insicuro in interruzioni
114 (*irq-unsafe*) significa che è sempre stato acquisito con le interruzioni
121 <hardirq-safe> o <hardirq-unsafe>
122 <softirq-safe> o <softirq-unsafe>
124 Questo perché se un blocco può essere usato in un contesto di interruzioni
136 --------------------------------------------
143 <L1> -> <L2>
144 <L2> -> <L1>
146 perché porterebbe ad uno stallo - chiamato stallo da blocco inverso - in cui si
147 cerca di trattenere i due blocchi in un ciclo in cui entrambe i contesti
156 <hardirq-safe> -> <hardirq-unsafe>
157 <softirq-safe> -> <softirq-unsafe>
159 La prima regola deriva dal fatto che un blocco sicuro in interruzioni può essere
160 trattenuto in un contesto d'interruzione che, per definizione, ha la possibilità
161 di interrompere un blocco insicuro in interruzioni; questo porterebbe ad uno
162 stallo da blocco inverso. La seconda, analogamente, ci dice che un blocco sicuro
163 in interruzioni software potrebbe essere trattenuto in un contesto di
164 interruzione software, dunque potrebbe interrompere un blocco insicuro in
173 - se viene trovato un nuovo blocco sicuro in interruzioni, verificheremo se
176 - se viene trovato un nuovo blocco sicuro in interruzioni software,
180 - se viene trovato un nuovo blocco insicuro in interruzioni, verificheremo se
183 - se viene trovato un nuovo blocco insicuro in interruzioni software,
187 (Di nuovo, questi controlli vengono fatti perché un contesto d'interruzione
192 ------------------------------------------------------------------
201 Un esempio di questa gerarchia di oggetti che producono "blocchi annidati" sono
202 i *block-dev* che rappresentano l'intero disco e quelli che rappresentano una
210 esempio, per i blocchi a mutua esclusione dei *block-dev* si avrebbe una
220 mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION);
222 In questo caso la sincronizzazione viene fatta su un *block-dev* sapendo che si
225 Ai fini della validazione, il validatore lo considererà con una - sotto - classe
233 -----------
240 che un dato blocco in un dato momento deve essere trattenuto (altrimenti, verrà
241 generato un WARN()). Queste vengono usate abbondantemente nel kernel, per
248 lockdep_assert_held(&rq->lock);
252 dove aver trattenuto rq->lock è necessario per aggiornare in sicurezza il clock
256 solo per rq->lock ATM. Se per caso un blocco non viene trattenuto, queste
257 genereranno un WARN(). Questo si rivela particolarmente utile quando si deve
259 potrebbero assumere che un blocco rimanga trattenuto, ma livelli inferiori
268 rf->cookie = lockdep_pin_lock(&rq->lock);
275 lockdep_unpin_lock(&rq->lock, rf->cookie);
285 ------------------------------------
288 ogni sequenza di sincronizzazione di un singolo processo che si verifichi almeno
294 scenari di sincronizzazione multi-processore e multi-processo. Il validatore può
299 riprodotto su un sistema a singolo processore.
315 assumiamo che un hash a 64-bit sia unico per ogni sequenza di
320 -----------
331 Per farlo, viene mantenuta una pila dei blocchi trattenuti, e viene calcolato un
332 hash a 64-bit unico per ogni sequenza. Quando la sequenza viene verificata per
338 ------------------------
346 Di base questo valore è 8191, e un classico sistema da ufficio ha meno di 1000
347 classi, dunque questo avviso è solitamente la conseguenza di un problema di
353 caricamento crea un nuovo insieme di classi di blocco per tutti i blocchi di
356 rimozione di un modulo non fa altro che aumentare il contatore di classi fino
359 2. Usare array con un gran numero di blocchi che non vengono esplicitamente
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
381 grep "lock-classes" /proc/lockdep_stats
385 lock-classes: 748 [max: 8191]
388 allora c'è probabilmente un problema da qualche parte. Il seguente comando può
394 un'esecuzione successiva per identificare eventuali problemi. Questo stesso
399 -----------------------------
427 sezione critica di un altro lettore. In altre parole, permette di annidare la
430 Dall'altro canto, lo stesso comportamento indurrebbe un lettore non ricorsivo ad
434 vengono bloccati solo dal trattenimento di un blocco di scrittura, mentre quelli
435 non ricorsivi possono essere bloccati dall'attesa di un blocco di scrittura.
447 un tipo lettore ricorsivo, l'attività A continuerà perché gli scrittori in
449 Tuttavia, se read_lock_2() è un lettore non ricorsivo, allora verrà bloccato
453 ---------------------------------------------------------------
456 1. Uno scrittore blocca un altro scrittore.
457 2. Un lettore blocca uno scrittore.
459 4. Un lettore (ricorsivo o meno) non blocca altri lettori ricorsivi ma potrebbe
466 +---+---+---+---+
468 +---+---+---+---+
470 +---+---+---+---+
472 +---+---+---+---+
474 +---+---+---+---+
492 aspettare perché si tratta di un lettore ricorsivo. Tuttavia, se read_lock()
493 fosse un lettore non ricorsivo, questo codice produrrebbe uno stallo.
496 particolare il valore del parametro 'read' in lock_acquire()), un blocco può
499 ricorsivo). In altre parole, per un'istanza di blocco esistono tre tipi di
507 (anche in lettura). Un blocco di lettura non ricorsivi può bloccare uno
523 -----------------------------------
531 L1 -> L2
536 In altre parole, vogliamo sapere se esiste un bloccatore L3 che viene bloccato
537 da L1 e un L2 che viene bloccato da L3. Dunque, siamo interessati a (1) quello
546 1) -(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.
550 2) -(EN)->:
552 "X -(EN)->" significa X-> Y, dove X è uno scrittore e Y può essere
553 o uno scrittore o un lettore non ricorsivo.
555 3) -(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
560 4) -(SN)->:
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.
579 Nel grafo delle dipendenze avremo sia X -(SN)-> Y che X -(EN)-> Y.
581 Usiamo -(xN)-> per rappresentare i rami sia per -(EN)-> che -(SN)->, allo stesso
582 modo -(Ex)->, -(xR)-> e -(Sx)->
584 Un "percorso" in un grafo è una serie di nodi e degli archi che li congiungono.
585 Definiamo un percorso "forte", come il percorso che non ha archi (dipendenze) di
586 tipo -(xR)-> e -(Sx)->. In altre parole, un percorso "forte" è un percorso da un
587 blocco 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)->
589 o -(ER)->, allora fra Y e Z non deve esserci una dipendenza -(SN)-> o -(SR)->.
594 ----------------------------------------------
599 Se esiste un percorso chiuso forte (ciclo forte), allora esiste anche una
601 l'esistenza di un ciclo forte è sufficiente alla scoperta di uno stallo.
605 Se non esiste un percorso chiuso forte (ciclo forte), allora non esiste una
609 Con questi due lemmi possiamo facilmente affermare che un percorso chiuso forte
611 alla possibilità di imbattersi concretamente in uno stallo. Un percorso chiuso
617 Immaginiamo d'avere un ciclo forte::
619 L1 -> L2 ... -> Ln -> L1
623 L1 -> L2
624 L2 -> L3
626 Ln-1 -> Ln
627 Ln -> L1
632 Per prima cosa facciamo sì che un processo/processore prenda L1 in L1 -> L2, poi
633 un altro prende L2 in L2 -> L3, e così via. Alla fine, tutti i Lx in Lx -> Lx+1
636 Poi visto che abbiamo L1 -> L2, chi trattiene L1 vorrà acquisire L2 in L1 -> L2,
638 L2 è già trattenuto da un altro processo/processore, ed in più L1 -> L2 e L2 ->
639 L3 non sono -(xR)-> né -(Sx)-> (la definizione di forte). Questo significa che L2
640 in L1 -> L2 non è un bloccatore non ricorsivo (bloccabile da chiunque), e L2 in
641 L2 -> L3 non è uno scrittore (che blocca chiunque).
646 L1, dunque si è creato un ciclo dal quale non possiamo uscire, quindi si ha uno
652 deve esiste un ciclo forte nel grafo delle dipendenze.
654 Secondo Wikipedia[1], se c'è uno stallo, allora deve esserci un ciclo di attese,
655 ovvero ci sono N processi/processori dove P1 aspetta un blocco trattenuto da P2,
658 trattiene Ln. Quindi avremo Ln -> L1 nel grafo delle dipendenze. Similarmente,
659 nel grafo delle dipendenze avremo L1 -> L2, L2 -> L3, ..., Ln-1 -> Ln, il che
660 significa che abbiamo un ciclo::
662 Ln -> L1 -> L2 -> ... -> Ln
664 , ed ora dimostriamo d'avere un ciclo forte.
666 Per un blocco Lx, il processo Px contribuisce alla dipendenza Lx-1 -> Lx e Px+1
667 contribuisce a quella Lx -> Lx+1. Visto che Px aspetta che Px+1 rilasci Lx, sarà
668 impossibile che Lx in Px+1 sia un lettore e che Lx in Px sia un lettore
670 ricorsivi. 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.
674 -----------
678 [2]: Shibu, K. (2009). Intro To Embedded Systems (1st ed.). Tata McGraw-Hill