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