| blob | bf1acd6204efab7fdde5e265803094180ec29b1a |
1 .. include:: ../disclaimer-ita.rst
3 .. c:namespace:: it_IT
5 :Original: :ref:`Documentation/kernel-hacking/locking.rst <kernel_hacking_lock>`
6 :Translator: Federico Vaga <federico.vaga@vaga.pv.it>
8 .. _it_kernel_hacking_lock:
10 ==========================================
11 L'inaffidabile guida alla sincronizzazione
12 ==========================================
14 :Author: Rusty Russell
16 Introduzione
17 ============
19 Benvenuto, alla notevole ed inaffidabile guida ai problemi di sincronizzazione
20 (locking) nel kernel. Questo documento descrive il sistema di sincronizzazione
21 nel kernel Linux 2.6.
23 Dato il largo utilizzo del multi-threading e della prelazione nel kernel
24 Linux, chiunque voglia dilettarsi col kernel deve conoscere i concetti
25 fondamentali della concorrenza e della sincronizzazione nei sistemi
26 multi-processore.
28 Il problema con la concorrenza
29 ==============================
31 (Saltatelo se sapete già cos'è una corsa critica).
33 In un normale programma, potete incrementare un contatore nel seguente modo:
35 ::
37 contatore++;
39 Questo è quello che vi aspettereste che accada sempre:
42 .. table:: Risultati attesi
44 +------------------------------------+------------------------------------+
45 | Istanza 1 | Istanza 2 |
46 +====================================+====================================+
47 | leggi contatore (5) | |
48 +------------------------------------+------------------------------------+
49 | aggiungi 1 (6) | |
50 +------------------------------------+------------------------------------+
51 | scrivi contatore (6) | |
52 +------------------------------------+------------------------------------+
53 | | leggi contatore (6) |
54 +------------------------------------+------------------------------------+
55 | | aggiungi 1 (7) |
56 +------------------------------------+------------------------------------+
57 | | scrivi contatore (7) |
58 +------------------------------------+------------------------------------+
60 Questo è quello che potrebbe succedere in realtà:
62 .. table:: Possibile risultato
64 +------------------------------------+------------------------------------+
65 | Istanza 1 | Istanza 2 |
66 +====================================+====================================+
67 | leggi contatore (5) | |
68 +------------------------------------+------------------------------------+
69 | | leggi contatore (5) |
70 +------------------------------------+------------------------------------+
71 | aggiungi 1 (6) | |
72 +------------------------------------+------------------------------------+
73 | | aggiungi 1 (6) |
74 +------------------------------------+------------------------------------+
75 | scrivi contatore (6) | |
76 +------------------------------------+------------------------------------+
77 | | scrivi contatore (6) |
78 +------------------------------------+------------------------------------+
81 Corse critiche e sezioni critiche
82 ---------------------------------
84 Questa sovrapposizione, ovvero quando un risultato dipende dal tempo che
85 intercorre fra processi diversi, è chiamata corsa critica. La porzione
86 di codice che contiene questo problema è chiamata sezione critica.
87 In particolar modo da quando Linux ha incominciato a girare su
88 macchine multi-processore, le sezioni critiche sono diventate uno dei
89 maggiori problemi di progettazione ed implementazione del kernel.
91 La prelazione può sortire gli stessi effetti, anche se c'è una sola CPU:
92 interrompendo un processo nella sua sezione critica otterremo comunque
93 la stessa corsa critica. In questo caso, il thread che si avvicenda
94 nell'esecuzione potrebbe eseguire anch'esso la sezione critica.
96 La soluzione è quella di riconoscere quando avvengono questi accessi
97 simultanei, ed utilizzare i *lock* per accertarsi che solo un'istanza
98 per volta possa entrare nella sezione critica. Il kernel offre delle buone
99 funzioni a questo scopo. E poi ci sono quelle meno buone, ma farò finta
100 che non esistano.
102 Sincronizzazione nel kernel Linux
103 =================================
105 Se posso darvi un suggerimento: non dormite mai con qualcuno più pazzo di
106 voi. Ma se dovessi darvi un suggerimento sulla sincronizzazione:
107 **mantenetela semplice**.
109 Siate riluttanti nell'introduzione di nuovi *lock*.
111 Abbastanza strano, quest'ultimo è l'esatto opposto del mio suggerimento
112 su quando **avete** dormito con qualcuno più pazzo di voi. E dovreste
113 pensare a prendervi un cane bello grande.
115 I due principali tipi di *lock* nel kernel: spinlock e mutex
116 ------------------------------------------------------------
118 Ci sono due tipi principali di *lock* nel kernel. Il tipo fondamentale è lo
119 spinlock (``include/asm/spinlock.h``), un semplice *lock* che può essere
120 trattenuto solo da un processo: se non si può trattenere lo spinlock, allora
121 rimane in attesa attiva (in inglese *spinning*) finché non ci riesce.
122 Gli spinlock sono molto piccoli e rapidi, possono essere utilizzati ovunque.
124 Il secondo tipo è il mutex (``include/linux/mutex.h``): è come uno spinlock,
125 ma potreste bloccarvi trattenendolo. Se non potete trattenere un mutex
126 il vostro processo si auto-sospenderà; verrà riattivato quando il mutex
127 verrà rilasciato. Questo significa che il processore potrà occuparsi d'altro
128 mentre il vostro processo è in attesa. Esistono molti casi in cui non potete
129 permettervi di sospendere un processo (vedere
130 :ref:`Quali funzioni possono essere chiamate in modo sicuro dalle interruzioni? <it_sleeping-things>`)
131 e quindi dovrete utilizzare gli spinlock.
133 Nessuno di questi *lock* è ricorsivo: vedere
134 :ref:`Stallo: semplice ed avanzato <it_deadlock>`
136 I *lock* e i kernel per sistemi monoprocessore
137 ----------------------------------------------
139 Per i kernel compilati senza ``CONFIG_SMP`` e senza ``CONFIG_PREEMPT``
140 gli spinlock non esistono. Questa è un'ottima scelta di progettazione:
141 quando nessun altro processo può essere eseguito in simultanea, allora
142 non c'è la necessità di avere un *lock*.
144 Se il kernel è compilato senza ``CONFIG_SMP`` ma con ``CONFIG_PREEMPT``,
145 allora gli spinlock disabilitano la prelazione; questo è sufficiente a
146 prevenire le corse critiche. Nella maggior parte dei casi, possiamo considerare
147 la prelazione equivalente ad un sistema multi-processore senza preoccuparci
148 di trattarla indipendentemente.
150 Dovreste verificare sempre la sincronizzazione con le opzioni ``CONFIG_SMP`` e
151 ``CONFIG_PREEMPT`` abilitate, anche quando non avete un sistema
152 multi-processore, questo vi permetterà di identificare alcuni problemi
153 di sincronizzazione.
155 Come vedremo di seguito, i mutex continuano ad esistere perché sono necessari
156 per la sincronizzazione fra processi in contesto utente.
158 Sincronizzazione in contesto utente
159 -----------------------------------
161 Se avete una struttura dati che verrà utilizzata solo dal contesto utente,
162 allora, per proteggerla, potete utilizzare un semplice mutex
163 (``include/linux/mutex.h``). Questo è il caso più semplice: inizializzate il
164 mutex; invocate mutex_lock_interruptible() per trattenerlo e
165 mutex_unlock() per rilasciarlo. C'è anche mutex_lock()
166 ma questa dovrebbe essere evitata perché non ritorna in caso di segnali.
168 Per esempio: ``net/netfilter/nf_sockopt.c`` permette la registrazione
169 di nuove chiamate per setsockopt() e getsockopt()
170 usando la funzione nf_register_sockopt(). La registrazione e
171 la rimozione vengono eseguite solamente quando il modulo viene caricato
172 o scaricato (e durante l'avvio del sistema, qui non abbiamo concorrenza),
173 e la lista delle funzioni registrate viene consultata solamente quando
174 setsockopt() o getsockopt() sono sconosciute al sistema.
175 In questo caso ``nf_sockopt_mutex`` è perfetto allo scopo, in particolar modo
176 visto che setsockopt e getsockopt potrebbero dormire.
178 Sincronizzazione fra il contesto utente e i softirq
179 ---------------------------------------------------
181 Se un softirq condivide dati col contesto utente, avete due problemi.
182 Primo, il contesto utente corrente potrebbe essere interroto da un softirq,
183 e secondo, la sezione critica potrebbe essere eseguita da un altro
184 processore. Questo è quando spin_lock_bh()
185 (``include/linux/spinlock.h``) viene utilizzato. Questo disabilita i softirq
186 sul processore e trattiene il *lock*. Invece, spin_unlock_bh() fa
187 l'opposto. (Il suffisso '_bh' è un residuo storico che fa riferimento al
188 "Bottom Halves", il vecchio nome delle interruzioni software. In un mondo
189 perfetto questa funzione si chiamerebbe 'spin_lock_softirq()').
191 Da notare che in questo caso potete utilizzare anche spin_lock_irq()
192 o spin_lock_irqsave(), queste fermano anche le interruzioni hardware:
193 vedere :ref:`Contesto di interruzione hardware <it_hardirq-context>`.
195 Questo funziona alla perfezione anche sui sistemi monoprocessore: gli spinlock
196 svaniscono e questa macro diventa semplicemente local_bh_disable()
197 (``include/linux/interrupt.h``), la quale impedisce ai softirq d'essere
198 eseguiti.
200 Sincronizzazione fra contesto utente e i tasklet
201 ------------------------------------------------
203 Questo caso è uguale al precedente, un tasklet viene eseguito da un softirq.
205 Sincronizzazione fra contesto utente e i timer
206 ----------------------------------------------
208 Anche questo caso è uguale al precedente, un timer viene eseguito da un
209 softirq.
210 Dal punto di vista della sincronizzazione, tasklet e timer sono identici.
212 Sincronizzazione fra tasklet e timer
213 ------------------------------------
215 Qualche volta un tasklet od un timer potrebbero condividere i dati con
216 un altro tasklet o timer
218 Lo stesso tasklet/timer
219 ~~~~~~~~~~~~~~~~~~~~~~~
221 Dato che un tasklet non viene mai eseguito contemporaneamente su due
222 processori, non dovete preoccuparvi che sia rientrante (ovvero eseguito
223 più volte in contemporanea), perfino su sistemi multi-processore.
225 Differenti tasklet/timer
226 ~~~~~~~~~~~~~~~~~~~~~~~~
228 Se un altro tasklet/timer vuole condividere dati col vostro tasklet o timer,
229 allora avrete bisogno entrambe di spin_lock() e
230 spin_unlock(). Qui spin_lock_bh() è inutile, siete già
231 in un tasklet ed avete la garanzia che nessun altro verrà eseguito sullo
232 stesso processore.
234 Sincronizzazione fra softirq
235 ----------------------------
237 Spesso un softirq potrebbe condividere dati con se stesso o un tasklet/timer.
239 Lo stesso softirq
240 ~~~~~~~~~~~~~~~~~
242 Lo stesso softirq può essere eseguito su un diverso processore: allo scopo
243 di migliorare le prestazioni potete utilizzare dati riservati ad ogni
244 processore (vedere :ref:`Dati per processore <it_per-cpu>`). Se siete arrivati
245 fino a questo punto nell'uso dei softirq, probabilmente tenete alla scalabilità
246 delle prestazioni abbastanza da giustificarne la complessità aggiuntiva.
248 Dovete utilizzare spin_lock() e spin_unlock() per
249 proteggere i dati condivisi.
251 Diversi Softirqs
252 ~~~~~~~~~~~~~~~~
254 Dovete utilizzare spin_lock() e spin_unlock() per
255 proteggere i dati condivisi, che siano timer, tasklet, diversi softirq o
256 lo stesso o altri softirq: uno qualsiasi di essi potrebbe essere in esecuzione
257 su un diverso processore.
259 .. _`it_hardirq-context`:
261 Contesto di interruzione hardware
262 =================================
264 Solitamente le interruzioni hardware comunicano con un tasklet o un softirq.
265 Spesso questo si traduce nel mettere in coda qualcosa da fare che verrà
266 preso in carico da un softirq.
268 Sincronizzazione fra interruzioni hardware e softirq/tasklet
269 ------------------------------------------------------------
271 Se un gestore di interruzioni hardware condivide dati con un softirq, allora
272 avrete due preoccupazioni. Primo, il softirq può essere interrotto da
273 un'interruzione hardware, e secondo, la sezione critica potrebbe essere
274 eseguita da un'interruzione hardware su un processore diverso. Questo è il caso
275 dove spin_lock_irq() viene utilizzato. Disabilita le interruzioni
276 sul processore che l'esegue, poi trattiene il lock. spin_unlock_irq()
277 fa l'opposto.
279 Il gestore d'interruzione hardware non ha bisogno di usare spin_lock_irq()
280 perché i softirq non possono essere eseguiti quando il gestore d'interruzione
281 hardware è in esecuzione: per questo si può usare spin_lock(), che è un po'
282 più veloce. L'unica eccezione è quando un altro gestore d'interruzioni
283 hardware utilizza lo stesso *lock*: spin_lock_irq() impedirà a questo
284 secondo gestore di interrompere quello in esecuzione.
286 Questo funziona alla perfezione anche sui sistemi monoprocessore: gli spinlock
287 svaniscono e questa macro diventa semplicemente local_irq_disable()
288 (``include/asm/smp.h``), la quale impedisce a softirq/tasklet/BH d'essere
289 eseguiti.
291 spin_lock_irqsave() (``include/linux/spinlock.h``) è una variante che
292 salva lo stato delle interruzioni in una variabile, questa verrà poi passata
293 a spin_unlock_irqrestore(). Questo significa che lo stesso codice
294 potrà essere utilizzato in un'interruzione hardware (dove le interruzioni sono
295 già disabilitate) e in un softirq (dove la disabilitazione delle interruzioni
296 è richiesta).
298 Da notare che i softirq (e quindi tasklet e timer) sono eseguiti al ritorno
299 da un'interruzione hardware, quindi spin_lock_irq() interrompe
300 anche questi. Tenuto conto di questo si può dire che
301 spin_lock_irqsave() è la funzione di sincronizzazione più generica
302 e potente.
304 Sincronizzazione fra due gestori d'interruzioni hardware
305 --------------------------------------------------------
307 Condividere dati fra due gestori di interruzione hardware è molto raro, ma se
308 succede, dovreste usare spin_lock_irqsave(): è una specificità
309 dell'architettura il fatto che tutte le interruzioni vengano interrotte
310 quando si eseguono di gestori di interruzioni.
312 Bigino della sincronizzazione
313 =============================
315 Pete Zaitcev ci offre il seguente riassunto:
317 - Se siete in un contesto utente (una qualsiasi chiamata di sistema)
318 e volete sincronizzarvi con altri processi, usate i mutex. Potete trattenere
319 il mutex e dormire (``copy_from_user*(`` o ``kmalloc(x,GFP_KERNEL)``).
321 - Altrimenti (== i dati possono essere manipolati da un'interruzione) usate
322 spin_lock_irqsave() e spin_unlock_irqrestore().
324 - Evitate di trattenere uno spinlock per più di 5 righe di codice incluse
325 le chiamate a funzione (ad eccezione di quell per l'accesso come
326 readb()).
328 Tabella dei requisiti minimi
329 ----------------------------
331 La tabella seguente illustra i requisiti **minimi** per la sincronizzazione fra
332 diversi contesti. In alcuni casi, lo stesso contesto può essere eseguito solo
333 da un processore per volta, quindi non ci sono requisiti per la
334 sincronizzazione (per esempio, un thread può essere eseguito solo su un
335 processore alla volta, ma se deve condividere dati con un altro thread, allora
336 la sincronizzazione è necessaria).
338 Ricordatevi il suggerimento qui sopra: potete sempre usare
339 spin_lock_irqsave(), che è un sovrainsieme di tutte le altre funzioni
340 per spinlock.
342 ============== ============= ============= ========= ========= ========= ========= ======= ======= ============== ==============
343 . IRQ Handler A IRQ Handler B Softirq A Softirq B Tasklet A Tasklet B Timer A Timer B User Context A User Context B
344 ============== ============= ============= ========= ========= ========= ========= ======= ======= ============== ==============
345 IRQ Handler A None
346 IRQ Handler B SLIS None
347 Softirq A SLI SLI SL
348 Softirq B SLI SLI SL SL
349 Tasklet A SLI SLI SL SL None
350 Tasklet B SLI SLI SL SL SL None
351 Timer A SLI SLI SL SL SL SL None
352 Timer B SLI SLI SL SL SL SL SL None
353 User Context A SLI SLI SLBH SLBH SLBH SLBH SLBH SLBH None
354 User Context B SLI SLI SLBH SLBH SLBH SLBH SLBH SLBH MLI None
355 ============== ============= ============= ========= ========= ========= ========= ======= ======= ============== ==============
357 Table: Tabella dei requisiti per la sincronizzazione
359 +--------+----------------------------+
360 | SLIS | spin_lock_irqsave |
361 +--------+----------------------------+
362 | SLI | spin_lock_irq |
363 +--------+----------------------------+
364 | SL | spin_lock |
365 +--------+----------------------------+
366 | SLBH | spin_lock_bh |
367 +--------+----------------------------+
368 | MLI | mutex_lock_interruptible |
369 +--------+----------------------------+
371 Table: Legenda per la tabella dei requisiti per la sincronizzazione
373 Le funzioni *trylock*
374 =====================
376 Ci sono funzioni che provano a trattenere un *lock* solo una volta e
377 ritornano immediatamente comunicato il successo od il fallimento
378 dell'operazione. Posso essere usate quando non serve accedere ai dati
379 protetti dal *lock* quando qualche altro thread lo sta già facendo
380 trattenendo il *lock*. Potrete acquisire il *lock* più tardi se vi
381 serve accedere ai dati protetti da questo *lock*.
383 La funzione spin_trylock() non ritenta di acquisire il *lock*,
384 se ci riesce al primo colpo ritorna un valore diverso da zero, altrimenti
385 se fallisce ritorna 0. Questa funzione può essere utilizzata in un qualunque
386 contesto, ma come spin_lock(): dovete disabilitare i contesti che
387 potrebbero interrompervi e quindi trattenere lo spinlock.
389 La funzione mutex_trylock() invece di sospendere il vostro processo
390 ritorna un valore diverso da zero se è possibile trattenere il lock al primo
391 colpo, altrimenti se fallisce ritorna 0. Nonostante non dorma, questa funzione
392 non può essere usata in modo sicuro in contesti di interruzione hardware o
393 software.
395 Esempi più comuni
396 =================
398 Guardiamo un semplice esempio: una memoria che associa nomi a numeri.
399 La memoria tiene traccia di quanto spesso viene utilizzato ogni oggetto;
400 quando è piena, l'oggetto meno usato viene eliminato.
402 Tutto in contesto utente
403 ------------------------
405 Nel primo esempio, supponiamo che tutte le operazioni avvengano in contesto
406 utente (in soldoni, da una chiamata di sistema), quindi possiamo dormire.
407 Questo significa che possiamo usare i mutex per proteggere la nostra memoria
408 e tutti gli oggetti che contiene. Ecco il codice::
410 #include <linux/list.h>
411 #include <linux/slab.h>
412 #include <linux/string.h>
413 #include <linux/mutex.h>
414 #include <asm/errno.h>
416 struct object
417 {
418 struct list_head list;
419 int id;
420 char name[32];
421 int popularity;
422 };
424 /* Protects the cache, cache_num, and the objects within it */
425 static DEFINE_MUTEX(cache_lock);
426 static LIST_HEAD(cache);
427 static unsigned int cache_num = 0;
428 #define MAX_CACHE_SIZE 10
430 /* Must be holding cache_lock */
431 static struct object *__cache_find(int id)
432 {
433 struct object *i;
435 list_for_each_entry(i, &cache, list)
436 if (i->id == id) {
437 i->popularity++;
438 return i;
439 }
440 return NULL;
441 }
443 /* Must be holding cache_lock */
444 static void __cache_delete(struct object *obj)
445 {
446 BUG_ON(!obj);
447 list_del(&obj->list);
448 kfree(obj);
449 cache_num--;
450 }
452 /* Must be holding cache_lock */
453 static void __cache_add(struct object *obj)
454 {
455 list_add(&obj->list, &cache);
456 if (++cache_num > MAX_CACHE_SIZE) {
457 struct object *i, *outcast = NULL;
458 list_for_each_entry(i, &cache, list) {
459 if (!outcast || i->popularity < outcast->popularity)
460 outcast = i;
461 }
462 __cache_delete(outcast);
463 }
464 }
466 int cache_add(int id, const char *name)
467 {
468 struct object *obj;
470 if ((obj = kmalloc(sizeof(*obj), GFP_KERNEL)) == NULL)
471 return -ENOMEM;
473 strscpy(obj->name, name, sizeof(obj->name));
474 obj->id = id;
475 obj->popularity = 0;
477 mutex_lock(&cache_lock);
478 __cache_add(obj);
479 mutex_unlock(&cache_lock);
480 return 0;
481 }
483 void cache_delete(int id)
484 {
485 mutex_lock(&cache_lock);
486 __cache_delete(__cache_find(id));
487 mutex_unlock(&cache_lock);
488 }
490 int cache_find(int id, char *name)
491 {
492 struct object *obj;
493 int ret = -ENOENT;
495 mutex_lock(&cache_lock);
496 obj = __cache_find(id);
497 if (obj) {
498 ret = 0;
499 strcpy(name, obj->name);
500 }
501 mutex_unlock(&cache_lock);
502 return ret;
503 }
505 Da notare che ci assicuriamo sempre di trattenere cache_lock quando
506 aggiungiamo, rimuoviamo od ispezioniamo la memoria: sia la struttura
507 della memoria che il suo contenuto sono protetti dal *lock*. Questo
508 caso è semplice dato che copiamo i dati dall'utente e non permettiamo
509 mai loro di accedere direttamente agli oggetti.
511 C'è una piccola ottimizzazione qui: nella funzione cache_add()
512 impostiamo i campi dell'oggetto prima di acquisire il *lock*. Questo è
513 sicuro perché nessun altro potrà accedervi finché non lo inseriremo
514 nella memoria.
516 Accesso dal contesto utente
517 ---------------------------
519 Ora consideriamo il caso in cui cache_find() può essere invocata
520 dal contesto d'interruzione: sia hardware che software. Un esempio potrebbe
521 essere un timer che elimina oggetti dalla memoria.
523 Qui di seguito troverete la modifica nel formato *patch*: le righe ``-``
524 sono quelle rimosse, mentre quelle ``+`` sono quelle aggiunte.
526 ::
528 --- cache.c.usercontext 2003-12-09 13:58:54.000000000 +1100
529 +++ cache.c.interrupt 2003-12-09 14:07:49.000000000 +1100
530 @@ -12,7 +12,7 @@
531 int popularity;
532 };
534 -static DEFINE_MUTEX(cache_lock);
535 +static DEFINE_SPINLOCK(cache_lock);
536 static LIST_HEAD(cache);
537 static unsigned int cache_num = 0;
538 #define MAX_CACHE_SIZE 10
539 @@ -55,6 +55,7 @@
540 int cache_add(int id, const char *name)
541 {
542 struct object *obj;
543 + unsigned long flags;
545 if ((obj = kmalloc(sizeof(*obj), GFP_KERNEL)) == NULL)
546 return -ENOMEM;
547 @@ -63,30 +64,33 @@
548 obj->id = id;
549 obj->popularity = 0;
551 - mutex_lock(&cache_lock);
552 + spin_lock_irqsave(&cache_lock, flags);
553 __cache_add(obj);
554 - mutex_unlock(&cache_lock);
555 + spin_unlock_irqrestore(&cache_lock, flags);
556 return 0;
557 }
559 void cache_delete(int id)
560 {
561 - mutex_lock(&cache_lock);
562 + unsigned long flags;
563 +
564 + spin_lock_irqsave(&cache_lock, flags);
565 __cache_delete(__cache_find(id));
566 - mutex_unlock(&cache_lock);
567 + spin_unlock_irqrestore(&cache_lock, flags);
568 }
570 int cache_find(int id, char *name)
571 {
572 struct object *obj;
573 int ret = -ENOENT;
574 + unsigned long flags;
576 - mutex_lock(&cache_lock);
577 + spin_lock_irqsave(&cache_lock, flags);
578 obj = __cache_find(id);
579 if (obj) {
580 ret = 0;
581 strcpy(name, obj->name);
582 }
583 - mutex_unlock(&cache_lock);
584 + spin_unlock_irqrestore(&cache_lock, flags);
585 return ret;
586 }
588 Da notare che spin_lock_irqsave() disabiliterà le interruzioni
589 se erano attive, altrimenti non farà niente (quando siamo già in un contesto
590 d'interruzione); dunque queste funzioni possono essere chiamante in
591 sicurezza da qualsiasi contesto.
593 Sfortunatamente, cache_add() invoca kmalloc() con
594 l'opzione ``GFP_KERNEL`` che è permessa solo in contesto utente. Ho supposto
595 che cache_add() venga chiamata dal contesto utente, altrimenti
596 questa opzione deve diventare un parametro di cache_add().
598 Esporre gli oggetti al di fuori del file
599 ----------------------------------------
601 Se i vostri oggetti contengono più informazioni, potrebbe non essere
602 sufficiente copiare i dati avanti e indietro: per esempio, altre parti del
603 codice potrebbero avere un puntatore a questi oggetti piuttosto che cercarli
604 ogni volta. Questo introduce due problemi.
606 Il primo problema è che utilizziamo ``cache_lock`` per proteggere gli oggetti:
607 dobbiamo renderlo dinamico così che il resto del codice possa usarlo. Questo
608 rende la sincronizzazione più complicata dato che non avviene più in un unico
609 posto.
611 Il secondo problema è il problema del ciclo di vita: se un'altra struttura
612 mantiene un puntatore ad un oggetto, presumibilmente si aspetta che questo
613 puntatore rimanga valido. Sfortunatamente, questo è garantito solo mentre
614 si trattiene il *lock*, altrimenti qualcuno potrebbe chiamare
615 cache_delete() o peggio, aggiungere un oggetto che riutilizza lo
616 stesso indirizzo.
618 Dato che c'è un solo *lock*, non potete trattenerlo a vita: altrimenti
619 nessun altro potrà eseguire il proprio lavoro.
621 La soluzione a questo problema è l'uso di un contatore di riferimenti:
622 chiunque punti ad un oggetto deve incrementare il contatore, e decrementarlo
623 quando il puntatore non viene più usato. Quando il contatore raggiunge lo zero
624 significa che non è più usato e l'oggetto può essere rimosso.
626 Ecco il codice::
628 --- cache.c.interrupt 2003-12-09 14:25:43.000000000 +1100
629 +++ cache.c.refcnt 2003-12-09 14:33:05.000000000 +1100
630 @@ -7,6 +7,7 @@
631 struct object
632 {
633 struct list_head list;
634 + unsigned int refcnt;
635 int id;
636 char name[32];
637 int popularity;
638 @@ -17,6 +18,35 @@
639 static unsigned int cache_num = 0;
640 #define MAX_CACHE_SIZE 10
642 +static void __object_put(struct object *obj)
643 +{
644 + if (--obj->refcnt == 0)
645 + kfree(obj);
646 +}
647 +
648 +static void __object_get(struct object *obj)
649 +{
650 + obj->refcnt++;
651 +}
652 +
653 +void object_put(struct object *obj)
654 +{
655 + unsigned long flags;
656 +
657 + spin_lock_irqsave(&cache_lock, flags);
658 + __object_put(obj);
659 + spin_unlock_irqrestore(&cache_lock, flags);
660 +}
661 +
662 +void object_get(struct object *obj)
663 +{
664 + unsigned long flags;
665 +
666 + spin_lock_irqsave(&cache_lock, flags);
667 + __object_get(obj);
668 + spin_unlock_irqrestore(&cache_lock, flags);
669 +}
670 +
671 /* Must be holding cache_lock */
672 static struct object *__cache_find(int id)
673 {
674 @@ -35,6 +65,7 @@
675 {
676 BUG_ON(!obj);
677 list_del(&obj->list);
678 + __object_put(obj);
679 cache_num--;
680 }
682 @@ -63,6 +94,7 @@
683 strscpy(obj->name, name, sizeof(obj->name));
684 obj->id = id;
685 obj->popularity = 0;
686 + obj->refcnt = 1; /* The cache holds a reference */
688 spin_lock_irqsave(&cache_lock, flags);
689 __cache_add(obj);
690 @@ -79,18 +111,15 @@
691 spin_unlock_irqrestore(&cache_lock, flags);
692 }
694 -int cache_find(int id, char *name)
695 +struct object *cache_find(int id)
696 {
697 struct object *obj;
698 - int ret = -ENOENT;
699 unsigned long flags;
701 spin_lock_irqsave(&cache_lock, flags);
702 obj = __cache_find(id);
703 - if (obj) {
704 - ret = 0;
705 - strcpy(name, obj->name);
706 - }
707 + if (obj)
708 + __object_get(obj);
709 spin_unlock_irqrestore(&cache_lock, flags);
710 - return ret;
711 + return obj;
712 }
714 Abbiamo incapsulato il contatore di riferimenti nelle tipiche funzioni
715 di 'get' e 'put'. Ora possiamo ritornare l'oggetto da cache_find()
716 col vantaggio che l'utente può dormire trattenendo l'oggetto (per esempio,
717 copy_to_user() per copiare il nome verso lo spazio utente).
719 Un altro punto da notare è che ho detto che il contatore dovrebbe incrementarsi
720 per ogni puntatore ad un oggetto: quindi il contatore di riferimenti è 1
721 quando l'oggetto viene inserito nella memoria. In altre versione il framework
722 non trattiene un riferimento per se, ma diventa più complicato.
724 Usare operazioni atomiche per il contatore di riferimenti
725 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
727 In sostanza, :c:type:`atomic_t` viene usato come contatore di riferimenti.
728 Ci sono un certo numbero di operazioni atomiche definite
729 in ``include/asm/atomic.h``: queste sono garantite come atomiche su qualsiasi
730 processore del sistema, quindi non sono necessari i *lock*. In questo caso è
731 più semplice rispetto all'uso degli spinlock, benché l'uso degli spinlock
732 sia più elegante per casi non banali. Le funzioni atomic_inc() e
733 atomic_dec_and_test() vengono usate al posto dei tipici operatori di
734 incremento e decremento, e i *lock* non sono più necessari per proteggere il
735 contatore stesso.
737 ::
739 --- cache.c.refcnt 2003-12-09 15:00:35.000000000 +1100
740 +++ cache.c.refcnt-atomic 2003-12-11 15:49:42.000000000 +1100
741 @@ -7,7 +7,7 @@
742 struct object
743 {
744 struct list_head list;
745 - unsigned int refcnt;
746 + atomic_t refcnt;
747 int id;
748 char name[32];
749 int popularity;
750 @@ -18,33 +18,15 @@
751 static unsigned int cache_num = 0;
752 #define MAX_CACHE_SIZE 10
754 -static void __object_put(struct object *obj)
755 -{
756 - if (--obj->refcnt == 0)
757 - kfree(obj);
758 -}
759 -
760 -static void __object_get(struct object *obj)
761 -{
762 - obj->refcnt++;
763 -}
764 -
765 void object_put(struct object *obj)
766 {
767 - unsigned long flags;
768 -
769 - spin_lock_irqsave(&cache_lock, flags);
770 - __object_put(obj);
771 - spin_unlock_irqrestore(&cache_lock, flags);
772 + if (atomic_dec_and_test(&obj->refcnt))
773 + kfree(obj);
774 }
776 void object_get(struct object *obj)
777 {
778 - unsigned long flags;
779 -
780 - spin_lock_irqsave(&cache_lock, flags);
781 - __object_get(obj);
782 - spin_unlock_irqrestore(&cache_lock, flags);
783 + atomic_inc(&obj->refcnt);
784 }
786 /* Must be holding cache_lock */
787 @@ -65,7 +47,7 @@
788 {
789 BUG_ON(!obj);
790 list_del(&obj->list);
791 - __object_put(obj);
792 + object_put(obj);
793 cache_num--;
794 }
796 @@ -94,7 +76,7 @@
797 strscpy(obj->name, name, sizeof(obj->name));
798 obj->id = id;
799 obj->popularity = 0;
800 - obj->refcnt = 1; /* The cache holds a reference */
801 + atomic_set(&obj->refcnt, 1); /* The cache holds a reference */
803 spin_lock_irqsave(&cache_lock, flags);
804 __cache_add(obj);
805 @@ -119,7 +101,7 @@
806 spin_lock_irqsave(&cache_lock, flags);
807 obj = __cache_find(id);
808 if (obj)
809 - __object_get(obj);
810 + object_get(obj);
811 spin_unlock_irqrestore(&cache_lock, flags);
812 return obj;
813 }
815 Proteggere l'oggetto stesso
816 ---------------------------
818 In questo esempio, assumiamo che gli oggetti (ad eccezione del contatore
819 di riferimenti) non cambino mai dopo la loro creazione. Se vogliamo permettere
820 al nome di cambiare abbiamo tre possibilità:
822 - Si può togliere static da ``cache_lock`` e dire agli utenti che devono
823 trattenere il *lock* prima di modificare il nome di un oggetto.
825 - Si può fornire una funzione cache_obj_rename() che prende il
826 *lock* e cambia il nome per conto del chiamante; si dirà poi agli utenti
827 di usare questa funzione.
829 - Si può decidere che ``cache_lock`` protegge solo la memoria stessa, ed
830 un altro *lock* è necessario per la protezione del nome.
832 Teoricamente, possiamo avere un *lock* per ogni campo e per ogni oggetto.
833 In pratica, le varianti più comuni sono:
835 - un *lock* che protegge l'infrastruttura (la lista ``cache`` di questo
836 esempio) e gli oggetti. Questo è quello che abbiamo fatto finora.
838 - un *lock* che protegge l'infrastruttura (inclusi i puntatori alla lista
839 negli oggetti), e un *lock* nell'oggetto per proteggere il resto
840 dell'oggetto stesso.
842 - *lock* multipli per proteggere l'infrastruttura (per esempio un *lock*
843 per ogni lista), possibilmente con un *lock* per oggetto.
845 Qui di seguito un'implementazione con "un lock per oggetto":
847 ::
849 --- cache.c.refcnt-atomic 2003-12-11 15:50:54.000000000 +1100
850 +++ cache.c.perobjectlock 2003-12-11 17:15:03.000000000 +1100
851 @@ -6,11 +6,17 @@
853 struct object
854 {
855 + /* These two protected by cache_lock. */
856 struct list_head list;
857 + int popularity;
858 +
859 atomic_t refcnt;
860 +
861 + /* Doesn't change once created. */
862 int id;
863 +
864 + spinlock_t lock; /* Protects the name */
865 char name[32];
866 - int popularity;
867 };
869 static DEFINE_SPINLOCK(cache_lock);
870 @@ -77,6 +84,7 @@
871 obj->id = id;
872 obj->popularity = 0;
873 atomic_set(&obj->refcnt, 1); /* The cache holds a reference */
874 + spin_lock_init(&obj->lock);
876 spin_lock_irqsave(&cache_lock, flags);
877 __cache_add(obj);
879 Da notare che ho deciso che il contatore di popolarità dovesse essere
880 protetto da ``cache_lock`` piuttosto che dal *lock* dell'oggetto; questo
881 perché è logicamente parte dell'infrastruttura (come
882 :c:type:`struct list_head <list_head>` nell'oggetto). In questo modo,
883 in __cache_add(), non ho bisogno di trattenere il *lock* di ogni
884 oggetto mentre si cerca il meno popolare.
886 Ho anche deciso che il campo id è immutabile, quindi non ho bisogno di
887 trattenere il lock dell'oggetto quando si usa __cache_find()
888 per leggere questo campo; il *lock* dell'oggetto è usato solo dal chiamante
889 che vuole leggere o scrivere il campo name.
891 Inoltre, da notare che ho aggiunto un commento che descrive i dati che sono
892 protetti dal *lock*. Questo è estremamente importante in quanto descrive il
893 comportamento del codice, che altrimenti sarebbe di difficile comprensione
894 leggendo solamente il codice. E come dice Alan Cox: “Lock data, not code”.
896 Problemi comuni
897 ===============
899 .. _`it_deadlock`:
901 Stallo: semplice ed avanzato
902 ----------------------------
904 Esiste un tipo di baco dove un pezzo di codice tenta di trattenere uno
905 spinlock due volte: questo rimarrà in attesa attiva per sempre aspettando che
906 il *lock* venga rilasciato (in Linux spinlocks, rwlocks e mutex non sono
907 ricorsivi).
908 Questo è facile da diagnosticare: non è uno di quei problemi che ti tengono
909 sveglio 5 notti a parlare da solo.
911 Un caso un pochino più complesso; immaginate d'avere una spazio condiviso
912 fra un softirq ed il contesto utente. Se usate spin_lock() per
913 proteggerlo, il contesto utente potrebbe essere interrotto da un softirq
914 mentre trattiene il lock, da qui il softirq rimarrà in attesa attiva provando
915 ad acquisire il *lock* già trattenuto nel contesto utente.
917 Questi casi sono chiamati stalli (*deadlock*), e come mostrato qui sopra,
918 può succedere anche con un solo processore (Ma non sui sistemi
919 monoprocessore perché gli spinlock spariscano quando il kernel è compilato
920 con ``CONFIG_SMP``\ =n. Nonostante ciò, nel secondo caso avrete comunque
921 una corruzione dei dati).
923 Questi casi sono facili da diagnosticare; sui sistemi multi-processore
924 il supervisione (*watchdog*) o l'opzione di compilazione ``DEBUG_SPINLOCK``
925 (``include/linux/spinlock.h``) permettono di scovare immediatamente quando
926 succedono.
928 Esiste un caso più complesso che è conosciuto come l'abbraccio della morte;
929 questo coinvolge due o più *lock*. Diciamo che avete un vettore di hash in cui
930 ogni elemento è uno spinlock a cui è associata una lista di elementi con lo
931 stesso hash. In un gestore di interruzioni software, dovete modificare un
932 oggetto e spostarlo su un altro hash; quindi dovrete trattenete lo spinlock
933 del vecchio hash e di quello nuovo, quindi rimuovere l'oggetto dal vecchio ed
934 inserirlo nel nuovo.
936 Qui abbiamo due problemi. Primo, se il vostro codice prova a spostare un
937 oggetto all'interno della stessa lista, otterrete uno stallo visto che
938 tenterà di trattenere lo stesso *lock* due volte. Secondo, se la stessa
939 interruzione software su un altro processore sta tentando di spostare
940 un altro oggetto nella direzione opposta, potrebbe accadere quanto segue:
942 +---------------------------------+---------------------------------+
943 | CPU 1 | CPU 2 |
944 +=================================+=================================+
945 | Trattiene *lock* A -> OK | Trattiene *lock* B -> OK |
946 +---------------------------------+---------------------------------+
947 | Trattiene *lock* B -> attesa | Trattiene *lock* A -> attesa |
948 +---------------------------------+---------------------------------+
950 Table: Conseguenze
952 Entrambe i processori rimarranno in attesa attiva sul *lock* per sempre,
953 aspettando che l'altro lo rilasci. Sembra e puzza come un blocco totale.
955 Prevenire gli stalli
956 --------------------
958 I libri di testo vi diranno che se trattenete i *lock* sempre nello stesso
959 ordine non avrete mai un simile stallo. La pratica vi dirà che questo
960 approccio non funziona all'ingrandirsi del sistema: quando creo un nuovo
961 *lock* non ne capisco abbastanza del kernel per dire in quale dei 5000 *lock*
962 si incastrerà.
964 I *lock* migliori sono quelli incapsulati: non vengono esposti nei file di
965 intestazione, e non vengono mai trattenuti fuori dallo stesso file. Potete
966 rileggere questo codice e vedere che non ci sarà mai uno stallo perché
967 non tenterà mai di trattenere un altro *lock* quando lo ha già.
968 Le persone che usano il vostro codice non devono nemmeno sapere che voi
969 state usando dei *lock*.
971 Un classico problema deriva dall'uso di *callback* e di *hook*: se li
972 chiamate mentre trattenete un *lock*, rischiate uno stallo o un abbraccio
973 della morte (chi lo sa cosa farà una *callback*?).
975 Ossessiva prevenzione degli stalli
976 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
978 Gli stalli sono un problema, ma non così terribile come la corruzione dei dati.
979 Un pezzo di codice trattiene un *lock* di lettura, cerca in una lista,
980 fallisce nel trovare quello che vuole, quindi rilascia il *lock* di lettura,
981 trattiene un *lock* di scrittura ed inserisce un oggetto; questo genere di
982 codice presenta una corsa critica.
984 Se non riuscite a capire il perché, per favore state alla larga dal mio
985 codice.
987 corsa fra temporizzatori: un passatempo del kernel
988 --------------------------------------------------
990 I temporizzatori potrebbero avere dei problemi con le corse critiche.
991 Considerate una collezione di oggetti (liste, hash, eccetera) dove ogni oggetto
992 ha un temporizzatore che sta per distruggerlo.
994 Se volete eliminare l'intera collezione (diciamo quando rimuovete un modulo),
995 potreste fare come segue::
997 /* THIS CODE BAD BAD BAD BAD: IF IT WAS ANY WORSE IT WOULD USE
998 HUNGARIAN NOTATION */
999 spin_lock_bh(&list_lock);
1001 while (list) {
1002 struct foo *next = list->next;
1003 del_timer(&list->timer);
1004 kfree(list);
1005 list = next;
1006 }
1008 spin_unlock_bh(&list_lock);
1010 Primo o poi, questo esploderà su un sistema multiprocessore perché un
1011 temporizzatore potrebbe essere già partiro prima di spin_lock_bh(),
1012 e prenderà il *lock* solo dopo spin_unlock_bh(), e cercherà
1013 di eliminare il suo oggetto (che però è già stato eliminato).
1015 Questo può essere evitato controllando il valore di ritorno di
1016 del_timer(): se ritorna 1, il temporizzatore è stato già
1017 rimosso. Se 0, significa (in questo caso) che il temporizzatore è in
1018 esecuzione, quindi possiamo fare come segue::
1020 retry:
1021 spin_lock_bh(&list_lock);
1023 while (list) {
1024 struct foo *next = list->next;
1025 if (!del_timer(&list->timer)) {
1026 /* Give timer a chance to delete this */
1027 spin_unlock_bh(&list_lock);
1028 goto retry;
1029 }
1030 kfree(list);
1031 list = next;
1032 }
1034 spin_unlock_bh(&list_lock);
1036 Un altro problema è l'eliminazione dei temporizzatori che si riavviano
1037 da soli (chiamando add_timer() alla fine della loro esecuzione).
1038 Dato che questo è un problema abbastanza comune con una propensione
1039 alle corse critiche, dovreste usare del_timer_sync()
1040 (``include/linux/timer.h``) per gestire questo caso. Questa ritorna il
1041 numero di volte che il temporizzatore è stato interrotto prima che
1042 fosse in grado di fermarlo senza che si riavviasse.
1044 Velocità della sincronizzazione
1045 ===============================
1047 Ci sono tre cose importanti da tenere in considerazione quando si valuta
1048 la velocità d'esecuzione di un pezzo di codice che necessita di
1049 sincronizzazione. La prima è la concorrenza: quante cose rimangono in attesa
1050 mentre qualcuno trattiene un *lock*. La seconda è il tempo necessario per
1051 acquisire (senza contese) e rilasciare un *lock*. La terza è di usare meno
1052 *lock* o di più furbi. Immagino che i *lock* vengano usati regolarmente,
1053 altrimenti, non sareste interessati all'efficienza.
1055 La concorrenza dipende da quanto a lungo un *lock* è trattenuto: dovreste
1056 trattenere un *lock* solo il tempo minimo necessario ma non un istante in più.
1057 Nella memoria dell'esempio precedente, creiamo gli oggetti senza trattenere
1058 il *lock*, poi acquisiamo il *lock* quando siamo pronti per inserirlo nella
1059 lista.
1061 Il tempo di acquisizione di un *lock* dipende da quanto danno fa
1062 l'operazione sulla *pipeline* (ovvero stalli della *pipeline*) e quant'è
1063 probabile che il processore corrente sia stato anche l'ultimo ad acquisire
1064 il *lock* (in pratica, il *lock* è nella memoria cache del processore
1065 corrente?): su sistemi multi-processore questa probabilità precipita
1066 rapidamente. Consideriamo un processore Intel Pentium III a 700Mhz: questo
1067 esegue un'istruzione in 0.7ns, un incremento atomico richiede 58ns, acquisire
1068 un *lock* che è nella memoria cache del processore richiede 160ns, e un
1069 trasferimento dalla memoria cache di un altro processore richiede altri
1070 170/360ns (Leggetevi l'articolo di Paul McKenney's `Linux Journal RCU
1071 article <http://www.linuxjournal.com/article.php?sid=6993>`__).
1073 Questi due obiettivi sono in conflitto: trattenere un *lock* per il minor
1074 tempo possibile potrebbe richiedere la divisione in più *lock* per diverse
1075 parti (come nel nostro ultimo esempio con un *lock* per ogni oggetto),
1076 ma questo aumenta il numero di acquisizioni di *lock*, ed il risultato
1077 spesso è che tutto è più lento che con un singolo *lock*. Questo è un altro
1078 argomento in favore della semplicità quando si parla di sincronizzazione.
1080 Il terzo punto è discusso di seguito: ci sono alcune tecniche per ridurre
1081 il numero di sincronizzazioni che devono essere fatte.
1083 Read/Write Lock Variants
1084 ------------------------
1086 Sia gli spinlock che i mutex hanno una variante per la lettura/scrittura
1087 (read/write): ``rwlock_t`` e :c:type:`struct rw_semaphore <rw_semaphore>`.
1088 Queste dividono gli utenti in due categorie: i lettori e gli scrittori.
1089 Se state solo leggendo i dati, potete acquisire il *lock* di lettura, ma
1090 per scrivere avrete bisogno del *lock* di scrittura. Molti possono trattenere
1091 il *lock* di lettura, ma solo uno scrittore alla volta può trattenere
1092 quello di scrittura.
1094 Se il vostro codice si divide chiaramente in codice per lettori e codice
1095 per scrittori (come nel nostro esempio), e il *lock* dei lettori viene
1096 trattenuto per molto tempo, allora l'uso di questo tipo di *lock* può aiutare.
1097 Questi sono leggermente più lenti rispetto alla loro versione normale, quindi
1098 nella pratica l'uso di ``rwlock_t`` non ne vale la pena.
1100 Evitare i *lock*: Read Copy Update
1101 --------------------------------------------
1103 Esiste un metodo di sincronizzazione per letture e scritture detto
1104 Read Copy Update. Con l'uso della tecnica RCU, i lettori possono scordarsi
1105 completamente di trattenere i *lock*; dato che nel nostro esempio ci
1106 aspettiamo d'avere più lettore che scrittori (altrimenti questa memoria
1107 sarebbe uno spreco) possiamo dire che questo meccanismo permette
1108 un'ottimizzazione.
1110 Come facciamo a sbarazzarci dei *lock* di lettura? Sbarazzarsi dei *lock* di
1111 lettura significa che uno scrittore potrebbe cambiare la lista sotto al naso
1112 dei lettori. Questo è abbastanza semplice: possiamo leggere una lista
1113 concatenata se lo scrittore aggiunge elementi alla fine e con certe
1114 precauzioni. Per esempio, aggiungendo ``new`` ad una lista concatenata
1115 chiamata ``list``::
1117 new->next = list->next;
1118 wmb();
1119 list->next = new;
1121 La funzione wmb() è una barriera di sincronizzazione delle
1122 scritture. Questa garantisce che la prima operazione (impostare l'elemento
1123 ``next`` del nuovo elemento) venga completata e vista da tutti i processori
1124 prima che venga eseguita la seconda operazione (che sarebbe quella di mettere
1125 il nuovo elemento nella lista). Questo è importante perché i moderni
1126 compilatori ed i moderni processori possono, entrambe, riordinare le istruzioni
1127 se non vengono istruiti altrimenti: vogliamo che i lettori non vedano
1128 completamente il nuovo elemento; oppure che lo vedano correttamente e quindi
1129 il puntatore ``next`` deve puntare al resto della lista.
1131 Fortunatamente, c'è una funzione che fa questa operazione sulle liste
1132 :c:type:`struct list_head <list_head>`: list_add_rcu()
1133 (``include/linux/list.h``).
1135 Rimuovere un elemento dalla lista è anche più facile: sostituiamo il puntatore
1136 al vecchio elemento con quello del suo successore, e i lettori vedranno
1137 l'elemento o lo salteranno.
1139 ::
1141 list->next = old->next;
1143 La funzione list_del_rcu() (``include/linux/list.h``) fa esattamente
1144 questo (la versione normale corrompe il vecchio oggetto, e non vogliamo che
1145 accada).
1147 Anche i lettori devono stare attenti: alcuni processori potrebbero leggere
1148 attraverso il puntatore ``next`` il contenuto dell'elemento successivo
1149 troppo presto, ma non accorgersi che il contenuto caricato è sbagliato quando
1150 il puntatore ``next`` viene modificato alla loro spalle. Ancora una volta
1151 c'è una funzione che viene in vostro aiuto list_for_each_entry_rcu()
1152 (``include/linux/list.h``). Ovviamente, gli scrittori possono usare
1153 list_for_each_entry() dato che non ci possono essere due scrittori
1154 in contemporanea.
1156 Il nostro ultimo dilemma è il seguente: quando possiamo realmente distruggere
1157 l'elemento rimosso? Ricordate, un lettore potrebbe aver avuto accesso a questo
1158 elemento proprio ora: se eliminiamo questo elemento ed il puntatore ``next``
1159 cambia, il lettore salterà direttamente nella spazzatura e scoppierà. Dobbiamo
1160 aspettare finché tutti i lettori che stanno attraversando la lista abbiano
1161 finito. Utilizziamo call_rcu() per registrare una funzione di
1162 richiamo che distrugga l'oggetto quando tutti i lettori correnti hanno
1163 terminato. In alternative, potrebbe essere usata la funzione
1164 synchronize_rcu() che blocca l'esecuzione finché tutti i lettori
1165 non terminano di ispezionare la lista.
1167 Ma come fa l'RCU a sapere quando i lettori sono finiti? Il meccanismo è
1168 il seguente: innanzi tutto i lettori accedono alla lista solo fra la coppia
1169 rcu_read_lock()/rcu_read_unlock() che disabilita la
1170 prelazione così che i lettori non vengano sospesi mentre stanno leggendo
1171 la lista.
1173 Poi, l'RCU aspetta finché tutti i processori non abbiano dormito almeno
1174 una volta; a questo punto, dato che i lettori non possono dormire, possiamo
1175 dedurre che un qualsiasi lettore che abbia consultato la lista durante la
1176 rimozione abbia già terminato, quindi la *callback* viene eseguita. Il vero
1177 codice RCU è un po' più ottimizzato di così, ma questa è l'idea di fondo.
1179 ::
1181 --- cache.c.perobjectlock 2003-12-11 17:15:03.000000000 +1100
1182 +++ cache.c.rcupdate 2003-12-11 17:55:14.000000000 +1100
1183 @@ -1,15 +1,18 @@
1184 #include <linux/list.h>
1185 #include <linux/slab.h>
1186 #include <linux/string.h>
1187 +#include <linux/rcupdate.h>
1188 #include <linux/mutex.h>
1189 #include <asm/errno.h>
1191 struct object
1192 {
1193 - /* These two protected by cache_lock. */
1194 + /* This is protected by RCU */
1195 struct list_head list;
1196 int popularity;
1198 + struct rcu_head rcu;
1199 +
1200 atomic_t refcnt;
1202 /* Doesn't change once created. */
1203 @@ -40,7 +43,7 @@
1204 {
1205 struct object *i;
1207 - list_for_each_entry(i, &cache, list) {
1208 + list_for_each_entry_rcu(i, &cache, list) {
1209 if (i->id == id) {
1210 i->popularity++;
1211 return i;
1212 @@ -49,19 +52,25 @@
1213 return NULL;
1214 }
1216 +/* Final discard done once we know no readers are looking. */
1217 +static void cache_delete_rcu(void *arg)
1218 +{
1219 + object_put(arg);
1220 +}
1221 +
1222 /* Must be holding cache_lock */
1223 static void __cache_delete(struct object *obj)
1224 {
1225 BUG_ON(!obj);
1226 - list_del(&obj->list);
1227 - object_put(obj);
1228 + list_del_rcu(&obj->list);
1229 cache_num--;
1230 + call_rcu(&obj->rcu, cache_delete_rcu);
1231 }
1233 /* Must be holding cache_lock */
1234 static void __cache_add(struct object *obj)
1235 {
1236 - list_add(&obj->list, &cache);
1237 + list_add_rcu(&obj->list, &cache);
1238 if (++cache_num > MAX_CACHE_SIZE) {
1239 struct object *i, *outcast = NULL;
1240 list_for_each_entry(i, &cache, list) {
1241 @@ -104,12 +114,11 @@
1242 struct object *cache_find(int id)
1243 {
1244 struct object *obj;
1245 - unsigned long flags;
1247 - spin_lock_irqsave(&cache_lock, flags);
1248 + rcu_read_lock();
1249 obj = __cache_find(id);
1250 if (obj)
1251 object_get(obj);
1252 - spin_unlock_irqrestore(&cache_lock, flags);
1253 + rcu_read_unlock();
1254 return obj;
1255 }
1257 Da notare che i lettori modificano il campo popularity nella funzione
1258 __cache_find(), e ora non trattiene alcun *lock*. Una soluzione
1259 potrebbe essere quella di rendere la variabile ``atomic_t``, ma per l'uso
1260 che ne abbiamo fatto qui, non ci interessano queste corse critiche perché un
1261 risultato approssimativo è comunque accettabile, quindi non l'ho cambiato.
1263 Il risultato è che la funzione cache_find() non ha bisogno di alcuna
1264 sincronizzazione con le altre funzioni, quindi è veloce su un sistema
1265 multi-processore tanto quanto lo sarebbe su un sistema mono-processore.
1267 Esiste un'ulteriore ottimizzazione possibile: vi ricordate il codice originale
1268 della nostra memoria dove non c'erano contatori di riferimenti e il chiamante
1269 semplicemente tratteneva il *lock* prima di accedere ad un oggetto? Questo è
1270 ancora possibile: se trattenete un *lock* nessuno potrà cancellare l'oggetto,
1271 quindi non avete bisogno di incrementare e decrementare il contatore di
1272 riferimenti.
1274 Ora, dato che il '*lock* di lettura' di un RCU non fa altro che disabilitare
1275 la prelazione, un chiamante che ha sempre la prelazione disabilitata fra le
1276 chiamate cache_find() e object_put() non necessita
1277 di incrementare e decrementare il contatore di riferimenti. Potremmo
1278 esporre la funzione __cache_find() dichiarandola non-static,
1279 e quel chiamante potrebbe usare direttamente questa funzione.
1281 Il beneficio qui sta nel fatto che il contatore di riferimenti no
1282 viene scritto: l'oggetto non viene alterato in alcun modo e quindi diventa
1283 molto più veloce su sistemi molti-processore grazie alla loro memoria cache.
1285 .. _`it_per-cpu`:
1287 Dati per processore
1288 -------------------
1290 Un'altra tecnica comunemente usata per evitare la sincronizzazione è quella
1291 di duplicare le informazioni per ogni processore. Per esempio, se volete
1292 avere un contatore di qualcosa, potreste utilizzare uno spinlock ed un
1293 singolo contatore. Facile e pulito.
1295 Se questo dovesse essere troppo lento (solitamente non lo è, ma se avete
1296 dimostrato che lo è devvero), potreste usare un contatore per ogni processore
1297 e quindi non sarebbe più necessaria la mutua esclusione. Vedere
1298 DEFINE_PER_CPU(), get_cpu_var() e put_cpu_var()
1299 (``include/linux/percpu.h``).
1301 Il tipo di dato ``local_t``, la funzione cpu_local_inc() e tutte
1302 le altre funzioni associate, sono di particolare utilità per semplici contatori
1303 per-processore; su alcune architetture sono anche più efficienti
1304 (``include/asm/local.h``).
1306 Da notare che non esiste un modo facile ed affidabile per ottenere il valore
1307 di un simile contatore senza introdurre altri *lock*. In alcuni casi questo
1308 non è un problema.
1310 Dati che sono usati prevalentemente dai gestori d'interruzioni
1311 --------------------------------------------------------------
1313 Se i dati vengono utilizzati sempre dallo stesso gestore d'interruzioni,
1314 allora i *lock* non vi servono per niente: il kernel già vi garantisce che
1315 il gestore d'interruzione non verrà eseguito in contemporanea su diversi
1316 processori.
1318 Manfred Spraul fa notare che potreste comunque comportarvi così anche
1319 se i dati vengono occasionalmente utilizzati da un contesto utente o
1320 da un'interruzione software. Il gestore d'interruzione non utilizza alcun
1321 *lock*, e tutti gli altri accessi verranno fatti così::
1323 spin_lock(&lock);
1324 disable_irq(irq);
1325 ...
1326 enable_irq(irq);
1327 spin_unlock(&lock);
1329 La funzione disable_irq() impedisce al gestore d'interruzioni
1330 d'essere eseguito (e aspetta che finisca nel caso fosse in esecuzione su
1331 un altro processore). Lo spinlock, invece, previene accessi simultanei.
1332 Naturalmente, questo è più lento della semplice chiamata
1333 spin_lock_irq(), quindi ha senso solo se questo genere di accesso
1334 è estremamente raro.
1336 .. _`it_sleeping-things`:
1338 Quali funzioni possono essere chiamate in modo sicuro dalle interruzioni?
1339 =========================================================================
1341 Molte funzioni del kernel dormono (in sostanza, chiamano schedule())
1342 direttamente od indirettamente: non potete chiamarle se trattenere uno
1343 spinlock o avete la prelazione disabilitata, mai. Questo significa che
1344 dovete necessariamente essere nel contesto utente: chiamarle da un
1345 contesto d'interruzione è illegale.
1347 Alcune funzioni che dormono
1348 ---------------------------
1350 Le più comuni sono elencate qui di seguito, ma solitamente dovete leggere
1351 il codice per scoprire se altre chiamate sono sicure. Se chiunque altro
1352 le chiami dorme, allora dovreste poter dormire anche voi. In particolar
1353 modo, le funzioni di registrazione e deregistrazione solitamente si
1354 aspettano d'essere chiamante da un contesto utente e quindi che possono
1355 dormire.
1357 - Accessi allo spazio utente:
1359 - copy_from_user()
1361 - copy_to_user()
1363 - get_user()
1365 - put_user()
1367 - kmalloc(GFP_KERNEL) <kmalloc>`
1369 - mutex_lock_interruptible() and
1370 mutex_lock()
1372 C'è anche mutex_trylock() che però non dorme.
1373 Comunque, non deve essere usata in un contesto d'interruzione dato
1374 che la sua implementazione non è sicura in quel contesto.
1375 Anche mutex_unlock() non dorme mai. Non può comunque essere
1376 usata in un contesto d'interruzione perché un mutex deve essere rilasciato
1377 dallo stesso processo che l'ha acquisito.
1379 Alcune funzioni che non dormono
1380 -------------------------------
1382 Alcune funzioni possono essere chiamate tranquillamente da qualsiasi
1383 contesto, o trattenendo un qualsiasi *lock*.
1385 - printk()
1387 - kfree()
1389 - add_timer() e del_timer()
1391 Riferimento per l'API dei Mutex
1392 ===============================
1394 .. kernel-doc:: include/linux/mutex.h
1395 :internal:
1397 .. kernel-doc:: kernel/locking/mutex.c
1398 :export:
1400 Riferimento per l'API dei Futex
1401 ===============================
1403 .. kernel-doc:: kernel/futex.c
1404 :internal:
1406 Approfondimenti
1407 ===============
1409 - ``Documentation/locking/spinlocks.rst``: la guida di Linus Torvalds agli
1410 spinlock del kernel.
1412 - Unix Systems for Modern Architectures: Symmetric Multiprocessing and
1413 Caching for Kernel Programmers.
1415 L'introduzione alla sincronizzazione a livello di kernel di Curt Schimmel
1416 è davvero ottima (non è scritta per Linux, ma approssimativamente si adatta
1417 a tutte le situazioni). Il libro è costoso, ma vale ogni singolo spicciolo
1418 per capire la sincronizzazione nei sistemi multi-processore.
1419 [ISBN: 0201633388]
1421 Ringraziamenti
1422 ==============
1424 Grazie a Telsa Gwynne per aver formattato questa guida in DocBook, averla
1425 pulita e aggiunto un po' di stile.
1427 Grazie a Martin Pool, Philipp Rumpf, Stephen Rothwell, Paul Mackerras,
1428 Ruedi Aschwanden, Alan Cox, Manfred Spraul, Tim Waugh, Pete Zaitcev,
1429 James Morris, Robert Love, Paul McKenney, John Ashby per aver revisionato,
1430 corretto, maledetto e commentato.
1432 Grazie alla congrega per non aver avuto alcuna influenza su questo documento.
1434 Glossario
1435 =========
1437 prelazione
1438 Prima del kernel 2.5, o quando ``CONFIG_PREEMPT`` non è impostato, i processi
1439 in contesto utente non si avvicendano nell'esecuzione (in pratica, il
1440 processo userà il processore fino al proprio termine, a meno che non ci siano
1441 delle interruzioni). Con l'aggiunta di ``CONFIG_PREEMPT`` nella versione
1442 2.5.4 questo è cambiato: quando si è in contesto utente, processi con una
1443 priorità maggiore possono subentrare nell'esecuzione: gli spinlock furono
1444 cambiati per disabilitare la prelazioni, anche su sistemi monoprocessore.
1446 bh
1447 Bottom Half: per ragioni storiche, le funzioni che contengono '_bh' nel
1448 loro nome ora si riferiscono a qualsiasi interruzione software; per esempio,
1449 spin_lock_bh() blocca qualsiasi interuzione software sul processore
1450 corrente. I *Bottom Halves* sono deprecati, e probabilmente verranno
1451 sostituiti dai tasklet. In un dato momento potrà esserci solo un
1452 *bottom half* in esecuzione.
1454 contesto d'interruzione
1455 Non è il contesto utente: qui si processano le interruzioni hardware e
1456 software. La macro in_interrupt() ritorna vero.
1458 contesto utente
1459 Il kernel che esegue qualcosa per conto di un particolare processo (per
1460 esempio una chiamata di sistema) o di un thread del kernel. Potete
1461 identificare il processo con la macro ``current``. Da non confondere
1462 con lo spazio utente. Può essere interrotto sia da interruzioni software
1463 che hardware.
1465 interruzione hardware
1466 Richiesta di interruzione hardware. in_irq() ritorna vero in un
1467 gestore d'interruzioni hardware.
1469 interruzione software / softirq
1470 Gestore di interruzioni software: in_irq() ritorna falso;
1471 in_softirq() ritorna vero. I tasklet e le softirq sono entrambi
1472 considerati 'interruzioni software'.
1474 In soldoni, un softirq è uno delle 32 interruzioni software che possono
1475 essere eseguite su più processori in contemporanea. A volte si usa per
1476 riferirsi anche ai tasklet (in pratica tutte le interruzioni software).
1478 monoprocessore / UP
1479 (Uni-Processor) un solo processore, ovvero non è SMP. (``CONFIG_SMP=n``).
1481 multi-processore / SMP
1482 (Symmetric Multi-Processor) kernel compilati per sistemi multi-processore
1483 (``CONFIG_SMP=y``).
1485 spazio utente
1486 Un processo che esegue il proprio codice fuori dal kernel.
1488 tasklet
1489 Un'interruzione software registrabile dinamicamente che ha la garanzia
1490 d'essere eseguita solo su un processore alla volta.
1492 timer
1493 Un'interruzione software registrabile dinamicamente che viene eseguita
1494 (circa) in un determinato momento. Quando è in esecuzione è come un tasklet
1495 (infatti, sono chiamati da ``TIMER_SOFTIRQ``).