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==========================================
11L'inaffidabile guida alla sincronizzazione
12==========================================
13
14:Author: Rusty Russell
15
16Introduzione
17============
18
19Benvenuto, alla notevole ed inaffidabile guida ai problemi di sincronizzazione
20(locking) nel kernel. Questo documento descrive il sistema di sincronizzazione
21nel kernel Linux 2.6.
22
23Dato il largo utilizzo del multi-threading e della prelazione nel kernel
24Linux, chiunque voglia dilettarsi col kernel deve conoscere i concetti
25fondamentali della concorrenza e della sincronizzazione nei sistemi
26multi-processore.
27
28Il problema con la concorrenza
29==============================
30
31(Saltatelo se sapete già cos'è una corsa critica).
32
33In un normale programma, potete incrementare un contatore nel seguente modo:
34
35::
36
37          contatore++;
38
39Questo è 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
60Questo è 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
81Corse critiche e sezioni critiche
82---------------------------------
83
84Questa sovrapposizione, ovvero quando un risultato dipende dal tempo che
85intercorre fra processi diversi, è chiamata corsa critica. La porzione
86di codice che contiene questo problema è chiamata sezione critica.
87In particolar modo da quando Linux ha incominciato a girare su
88macchine multi-processore, le sezioni critiche sono diventate uno dei
89maggiori problemi di progettazione ed implementazione del kernel.
90
91La prelazione può sortire gli stessi effetti, anche se c'è una sola CPU:
92interrompendo un processo nella sua sezione critica otterremo comunque
93la stessa corsa critica. In questo caso, il thread che si avvicenda
94nell'esecuzione potrebbe eseguire anch'esso la sezione critica.
95
96La soluzione è quella di riconoscere quando avvengono questi accessi
97simultanei, ed utilizzare i *lock* per accertarsi che solo un'istanza
98per volta possa entrare nella sezione critica. Il kernel offre delle buone
99funzioni a questo scopo. E poi ci sono quelle meno buone, ma farò finta
100che non esistano.
101
102Sincronizzazione nel kernel Linux
103=================================
104
105Se posso darvi un suggerimento: non dormite mai con qualcuno più pazzo di
106voi. Ma se dovessi darvi un suggerimento sulla sincronizzazione:
107**mantenetela semplice**.
108
109Siate riluttanti nell'introduzione di nuovi *lock*.
110
111Abbastanza strano, quest'ultimo è l'esatto opposto del mio suggerimento
112su quando **avete** dormito con qualcuno più pazzo di voi. E dovreste
113pensare a prendervi un cane bello grande.
114
115I due principali tipi di *lock* nel kernel: spinlock e mutex
116------------------------------------------------------------
117
118Ci sono due tipi principali di *lock* nel kernel. Il tipo fondamentale è lo
119spinlock (``include/asm/spinlock.h``), un semplice *lock* che può essere
120trattenuto solo da un processo: se non si può trattenere lo spinlock, allora
121rimane in attesa attiva (in inglese *spinning*) finché non ci riesce.
122Gli spinlock sono molto piccoli e rapidi, possono essere utilizzati ovunque.
123
124Il secondo tipo è il mutex (``include/linux/mutex.h``): è come uno spinlock,
125ma potreste bloccarvi trattenendolo. Se non potete trattenere un mutex
126il vostro processo si auto-sospenderà; verrà riattivato quando il mutex
127verrà rilasciato. Questo significa che il processore potrà occuparsi d'altro
128mentre il vostro processo è in attesa. Esistono molti casi in cui non potete
129permettervi di sospendere un processo (vedere
130:ref:`Quali funzioni possono essere chiamate in modo sicuro dalle interruzioni? <it_sleeping-things>`)
131e quindi dovrete utilizzare gli spinlock.
132
133Nessuno di questi *lock* è ricorsivo: vedere
134:ref:`Stallo: semplice ed avanzato <it_deadlock>`
135
136I *lock* e i kernel per sistemi monoprocessore
137----------------------------------------------
138
139Per i kernel compilati senza ``CONFIG_SMP`` e senza ``CONFIG_PREEMPT``
140gli spinlock non esistono. Questa è un'ottima scelta di progettazione:
141quando nessun altro processo può essere eseguito in simultanea, allora
142non c'è la necessità di avere un *lock*.
143
144Se il kernel è compilato senza ``CONFIG_SMP`` ma con ``CONFIG_PREEMPT``,
145allora gli spinlock disabilitano la prelazione; questo è sufficiente a
146prevenire le corse critiche. Nella maggior parte dei casi, possiamo considerare
147la prelazione equivalente ad un sistema multi-processore senza preoccuparci
148di trattarla indipendentemente.
149
150Dovreste verificare sempre la sincronizzazione con le opzioni ``CONFIG_SMP`` e
151``CONFIG_PREEMPT`` abilitate, anche quando non avete un sistema
152multi-processore, questo vi permetterà di identificare alcuni problemi
153di sincronizzazione.
154
155Come vedremo di seguito, i mutex continuano ad esistere perché sono necessari
156per la sincronizzazione fra processi in contesto utente.
157
158Sincronizzazione in contesto utente
159-----------------------------------
160
161Se avete una struttura dati che verrà utilizzata solo dal contesto utente,
162allora, per proteggerla, potete utilizzare un semplice mutex
163(``include/linux/mutex.h``). Questo è il caso più semplice: inizializzate il
164mutex; invocate mutex_lock_interruptible() per trattenerlo e
165mutex_unlock() per rilasciarlo. C'è anche mutex_lock()
166ma questa dovrebbe essere evitata perché non ritorna in caso di segnali.
167
168Per esempio: ``net/netfilter/nf_sockopt.c`` permette la registrazione
169di nuove chiamate per setsockopt() e getsockopt()
170usando la funzione nf_register_sockopt(). La registrazione e
171la rimozione vengono eseguite solamente quando il modulo viene caricato
172o scaricato (e durante l'avvio del sistema, qui non abbiamo concorrenza),
173e la lista delle funzioni registrate viene consultata solamente quando
174setsockopt() o getsockopt() sono sconosciute al sistema.
175In questo caso ``nf_sockopt_mutex`` è perfetto allo scopo, in particolar modo
176visto che setsockopt e getsockopt potrebbero dormire.
177
178Sincronizzazione fra il contesto utente e i softirq
179---------------------------------------------------
180
181Se un softirq condivide dati col contesto utente, avete due problemi.
182Primo, il contesto utente corrente potrebbe essere interroto da un softirq,
183e secondo, la sezione critica potrebbe essere eseguita da un altro
184processore. Questo è quando spin_lock_bh()
185(``include/linux/spinlock.h``) viene utilizzato. Questo disabilita i softirq
186sul processore e trattiene il *lock*. Invece, spin_unlock_bh() fa
187l'opposto. (Il suffisso '_bh' è un residuo storico che fa riferimento al
188"Bottom Halves", il vecchio nome delle interruzioni software. In un mondo
189perfetto questa funzione si chiamerebbe 'spin_lock_softirq()').
190
191Da notare che in questo caso potete utilizzare anche spin_lock_irq()
192o spin_lock_irqsave(), queste fermano anche le interruzioni hardware:
193vedere :ref:`Contesto di interruzione hardware <it_hardirq-context>`.
194
195Questo funziona alla perfezione anche sui sistemi monoprocessore: gli spinlock
196svaniscono e questa macro diventa semplicemente local_bh_disable()
197(``include/linux/interrupt.h``), la quale impedisce ai softirq d'essere
198eseguiti.
199
200Sincronizzazione fra contesto utente e i tasklet
201------------------------------------------------
202
203Questo caso è uguale al precedente, un tasklet viene eseguito da un softirq.
204
205Sincronizzazione fra contesto utente e i timer
206----------------------------------------------
207
208Anche questo caso è uguale al precedente, un timer viene eseguito da un
209softirq.
210Dal punto di vista della sincronizzazione, tasklet e timer sono identici.
211
212Sincronizzazione fra tasklet e timer
213------------------------------------
214
215Qualche volta un tasklet od un timer potrebbero condividere i dati con
216un altro tasklet o timer
217
218Lo stesso tasklet/timer
219~~~~~~~~~~~~~~~~~~~~~~~
220
221Dato che un tasklet non viene mai eseguito contemporaneamente su due
222processori, non dovete preoccuparvi che sia rientrante (ovvero eseguito
223più volte in contemporanea), perfino su sistemi multi-processore.
224
225Differenti tasklet/timer
226~~~~~~~~~~~~~~~~~~~~~~~~
227
228Se un altro tasklet/timer vuole condividere dati col vostro tasklet o timer,
229allora avrete bisogno entrambe di spin_lock() e
230spin_unlock(). Qui spin_lock_bh() è inutile, siete già
231in un tasklet ed avete la garanzia che nessun altro verrà eseguito sullo
232stesso processore.
233
234Sincronizzazione fra softirq
235----------------------------
236
237Spesso un softirq potrebbe condividere dati con se stesso o un tasklet/timer.
238
239Lo stesso softirq
240~~~~~~~~~~~~~~~~~
241
242Lo stesso softirq può essere eseguito su un diverso processore: allo scopo
243di migliorare le prestazioni potete utilizzare dati riservati ad ogni
244processore (vedere :ref:`Dati per processore <it_per-cpu>`). Se siete arrivati
245fino a questo punto nell'uso dei softirq, probabilmente tenete alla scalabilità
246delle prestazioni abbastanza da giustificarne la complessità aggiuntiva.
247
248Dovete utilizzare spin_lock() e spin_unlock() per
249proteggere i dati condivisi.
250
251Diversi Softirqs
252~~~~~~~~~~~~~~~~
253
254Dovete utilizzare spin_lock() e spin_unlock() per
255proteggere i dati condivisi, che siano timer, tasklet, diversi softirq o
256lo stesso o altri softirq: uno qualsiasi di essi potrebbe essere in esecuzione
257su un diverso processore.
258
259.. _`it_hardirq-context`:
260
261Contesto di interruzione hardware
262=================================
263
264Solitamente le interruzioni hardware comunicano con un tasklet o un softirq.
265Spesso questo si traduce nel mettere in coda qualcosa da fare che verrà
266preso in carico da un softirq.
267
268Sincronizzazione fra interruzioni hardware e softirq/tasklet
269------------------------------------------------------------
270
271Se un gestore di interruzioni hardware condivide dati con un softirq, allora
272avrete due preoccupazioni. Primo, il softirq può essere interrotto da
273un'interruzione hardware, e secondo, la sezione critica potrebbe essere
274eseguita da un'interruzione hardware su un processore diverso. Questo è il caso
275dove spin_lock_irq() viene utilizzato. Disabilita le interruzioni
276sul processore che l'esegue, poi trattiene il lock. spin_unlock_irq()
277fa l'opposto.
278
279Il gestore d'interruzione hardware non ha bisogno di usare spin_lock_irq()
280perché i softirq non possono essere eseguiti quando il gestore d'interruzione
281hardware è in esecuzione: per questo si può usare spin_lock(), che è un po'
282più veloce. L'unica eccezione è quando un altro gestore d'interruzioni
283hardware utilizza lo stesso *lock*: spin_lock_irq() impedirà a questo
284secondo gestore di interrompere quello in esecuzione.
285
286Questo funziona alla perfezione anche sui sistemi monoprocessore: gli spinlock
287svaniscono e questa macro diventa semplicemente local_irq_disable()
288(``include/asm/smp.h``), la quale impedisce a softirq/tasklet/BH d'essere
289eseguiti.
290
291spin_lock_irqsave() (``include/linux/spinlock.h``) è una variante che
292salva lo stato delle interruzioni in una variabile, questa verrà poi passata
293a spin_unlock_irqrestore(). Questo significa che lo stesso codice
294potrà essere utilizzato in un'interruzione hardware (dove le interruzioni sono
295già disabilitate) e in un softirq (dove la disabilitazione delle interruzioni
296è richiesta).
297
298Da notare che i softirq (e quindi tasklet e timer) sono eseguiti al ritorno
299da un'interruzione hardware, quindi spin_lock_irq() interrompe
300anche questi. Tenuto conto di questo si può dire che
301spin_lock_irqsave() è la funzione di sincronizzazione più generica
302e potente.
303
304Sincronizzazione fra due gestori d'interruzioni hardware
305--------------------------------------------------------
306
307Condividere dati fra due gestori di interruzione hardware è molto raro, ma se
308succede, dovreste usare spin_lock_irqsave(): è una specificità
309dell'architettura il fatto che tutte le interruzioni vengano interrotte
310quando si eseguono di gestori di interruzioni.
311
312Bigino della sincronizzazione
313=============================
314
315Pete Zaitcev ci offre il seguente riassunto:
316
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)``).
320
321-  Altrimenti (== i dati possono essere manipolati da un'interruzione) usate
322   spin_lock_irqsave() e spin_unlock_irqrestore().
323
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()).
327
328Tabella dei requisiti minimi
329----------------------------
330
331La tabella seguente illustra i requisiti **minimi** per la sincronizzazione fra
332diversi contesti. In alcuni casi, lo stesso contesto può essere eseguito solo
333da un processore per volta, quindi non ci sono requisiti per la
334sincronizzazione (per esempio, un thread può essere eseguito solo su un
335processore alla volta, ma se deve condividere dati con un altro thread, allora
336la sincronizzazione è necessaria).
337
338Ricordatevi il suggerimento qui sopra: potete sempre usare
339spin_lock_irqsave(), che è un sovrainsieme di tutte le altre funzioni
340per spinlock.
341
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============== ============= ============= ========= ========= ========= ========= ======= ======= ============== ==============
345IRQ Handler A  None
346IRQ Handler B  SLIS          None
347Softirq A      SLI           SLI           SL
348Softirq B      SLI           SLI           SL        SL
349Tasklet A      SLI           SLI           SL        SL        None
350Tasklet B      SLI           SLI           SL        SL        SL        None
351Timer A        SLI           SLI           SL        SL        SL        SL        None
352Timer B        SLI           SLI           SL        SL        SL        SL        SL      None
353User Context A SLI           SLI           SLBH      SLBH      SLBH      SLBH      SLBH    SLBH    None
354User Context B SLI           SLI           SLBH      SLBH      SLBH      SLBH      SLBH    SLBH    MLI            None
355============== ============= ============= ========= ========= ========= ========= ======= ======= ============== ==============
356
357Table: Tabella dei requisiti per la sincronizzazione
358
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+--------+----------------------------+
370
371Table: Legenda per la tabella dei requisiti per la sincronizzazione
372
373Le funzioni *trylock*
374=====================
375
376Ci sono funzioni che provano a trattenere un *lock* solo una volta e
377ritornano immediatamente comunicato il successo od il fallimento
378dell'operazione. Posso essere usate quando non serve accedere ai dati
379protetti dal *lock* quando qualche altro thread lo sta già facendo
380trattenendo il *lock*. Potrete acquisire il *lock* più tardi se vi
381serve accedere ai dati protetti da questo *lock*.
382
383La funzione spin_trylock() non ritenta di acquisire il *lock*,
384se ci riesce al primo colpo ritorna un valore diverso da zero, altrimenti
385se fallisce ritorna 0. Questa funzione può essere utilizzata in un qualunque
386contesto, ma come spin_lock(): dovete disabilitare i contesti che
387potrebbero interrompervi e quindi trattenere lo spinlock.
388
389La funzione mutex_trylock() invece di sospendere il vostro processo
390ritorna un valore diverso da zero se è possibile trattenere il lock al primo
391colpo, altrimenti se fallisce ritorna 0. Nonostante non dorma, questa funzione
392non può essere usata in modo sicuro in contesti di interruzione hardware o
393software.
394
395Esempi più comuni
396=================
397
398Guardiamo un semplice esempio: una memoria che associa nomi a numeri.
399La memoria tiene traccia di quanto spesso viene utilizzato ogni oggetto;
400quando è piena, l'oggetto meno usato viene eliminato.
401
402Tutto in contesto utente
403------------------------
404
405Nel primo esempio, supponiamo che tutte le operazioni avvengano in contesto
406utente (in soldoni, da una chiamata di sistema), quindi possiamo dormire.
407Questo significa che possiamo usare i mutex per proteggere la nostra memoria
408e tutti gli oggetti che contiene. Ecco il codice::
409
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>
415
416    struct object
417    {
418            struct list_head list;
419            int id;
420            char name[32];
421            int popularity;
422    };
423
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
429
430    /* Must be holding cache_lock */
431    static struct object *__cache_find(int id)
432    {
433            struct object *i;
434
435            list_for_each_entry(i, &cache, list)
436                    if (i->id == id) {
437                            i->popularity++;
438                            return i;
439                    }
440            return NULL;
441    }
442
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    }
451
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    }
465
466    int cache_add(int id, const char *name)
467    {
468            struct object *obj;
469
470            if ((obj = kmalloc(sizeof(*obj), GFP_KERNEL)) == NULL)
471                    return -ENOMEM;
472
473            strscpy(obj->name, name, sizeof(obj->name));
474            obj->id = id;
475            obj->popularity = 0;
476
477            mutex_lock(&cache_lock);
478            __cache_add(obj);
479            mutex_unlock(&cache_lock);
480            return 0;
481    }
482
483    void cache_delete(int id)
484    {
485            mutex_lock(&cache_lock);
486            __cache_delete(__cache_find(id));
487            mutex_unlock(&cache_lock);
488    }
489
490    int cache_find(int id, char *name)
491    {
492            struct object *obj;
493            int ret = -ENOENT;
494
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    }
504
505Da notare che ci assicuriamo sempre di trattenere cache_lock quando
506aggiungiamo, rimuoviamo od ispezioniamo la memoria: sia la struttura
507della memoria che il suo contenuto sono protetti dal *lock*. Questo
508caso è semplice dato che copiamo i dati dall'utente e non permettiamo
509mai loro di accedere direttamente agli oggetti.
510
511C'è una piccola ottimizzazione qui: nella funzione cache_add()
512impostiamo i campi dell'oggetto prima di acquisire il *lock*. Questo è
513sicuro perché nessun altro potrà accedervi finché non lo inseriremo
514nella memoria.
515
516Accesso dal contesto utente
517---------------------------
518
519Ora consideriamo il caso in cui cache_find() può essere invocata
520dal contesto d'interruzione: sia hardware che software. Un esempio potrebbe
521essere un timer che elimina oggetti dalla memoria.
522
523Qui di seguito troverete la modifica nel formato *patch*: le righe ``-``
524sono quelle rimosse, mentre quelle ``+`` sono quelle aggiunte.
525
526::
527
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     };
533
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;
544
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;
550
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     }
558
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     }
569
570     int cache_find(int id, char *name)
571     {
572             struct object *obj;
573             int ret = -ENOENT;
574    +        unsigned long flags;
575
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     }
587
588Da notare che spin_lock_irqsave() disabiliterà le interruzioni
589se erano attive, altrimenti non farà niente (quando siamo già in un contesto
590d'interruzione); dunque queste funzioni possono essere chiamante in
591sicurezza da qualsiasi contesto.
592
593Sfortunatamente, cache_add() invoca kmalloc() con
594l'opzione ``GFP_KERNEL`` che è permessa solo in contesto utente. Ho supposto
595che cache_add() venga chiamata dal contesto utente, altrimenti
596questa opzione deve diventare un parametro di cache_add().
597
598Esporre gli oggetti al di fuori del file
599----------------------------------------
600
601Se i vostri oggetti contengono più informazioni, potrebbe non essere
602sufficiente copiare i dati avanti e indietro: per esempio, altre parti del
603codice potrebbero avere un puntatore a questi oggetti piuttosto che cercarli
604ogni volta. Questo introduce due problemi.
605
606Il primo problema è che utilizziamo ``cache_lock`` per proteggere gli oggetti:
607dobbiamo renderlo dinamico così che il resto del codice possa usarlo. Questo
608rende la sincronizzazione più complicata dato che non avviene più in un unico
609posto.
610
611Il secondo problema è il problema del ciclo di vita: se un'altra struttura
612mantiene un puntatore ad un oggetto, presumibilmente si aspetta che questo
613puntatore rimanga valido. Sfortunatamente, questo è garantito solo mentre
614si trattiene il *lock*, altrimenti qualcuno potrebbe chiamare
615cache_delete() o peggio, aggiungere un oggetto che riutilizza lo
616stesso indirizzo.
617
618Dato che c'è un solo *lock*, non potete trattenerlo a vita: altrimenti
619nessun altro potrà eseguire il proprio lavoro.
620
621La soluzione a questo problema è l'uso di un contatore di riferimenti:
622chiunque punti ad un oggetto deve incrementare il contatore, e decrementarlo
623quando il puntatore non viene più usato. Quando il contatore raggiunge lo zero
624significa che non è più usato e l'oggetto può essere rimosso.
625
626Ecco il codice::
627
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
641
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     }
681
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 */
687
688             spin_lock_irqsave(&cache_lock, flags);
689             __cache_add(obj);
690    @@ -79,18 +111,15 @@
691             spin_unlock_irqrestore(&cache_lock, flags);
692     }
693
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;
700
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     }
713
714Abbiamo incapsulato il contatore di riferimenti nelle tipiche funzioni
715di 'get' e 'put'. Ora possiamo ritornare l'oggetto da cache_find()
716col vantaggio che l'utente può dormire trattenendo l'oggetto (per esempio,
717copy_to_user() per copiare il nome verso lo spazio utente).
718
719Un altro punto da notare è che ho detto che il contatore dovrebbe incrementarsi
720per ogni puntatore ad un oggetto: quindi il contatore di riferimenti è 1
721quando l'oggetto viene inserito nella memoria. In altre versione il framework
722non trattiene un riferimento per se, ma diventa più complicato.
723
724Usare operazioni atomiche per il contatore di riferimenti
725~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
726
727In sostanza, :c:type:`atomic_t` viene usato come contatore di riferimenti.
728Ci sono un certo numbero di operazioni atomiche definite
729in ``include/asm/atomic.h``: queste sono garantite come atomiche su qualsiasi
730processore del sistema, quindi non sono necessari i *lock*. In questo caso è
731più semplice rispetto all'uso degli spinlock, benché l'uso degli spinlock
732sia più elegante per casi non banali. Le funzioni atomic_inc() e
733atomic_dec_and_test() vengono usate al posto dei tipici operatori di
734incremento e decremento, e i *lock* non sono più necessari per proteggere il
735contatore stesso.
736
737::
738
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
753
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     }
775
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     }
785
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     }
795
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 */
802
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     }
814
815Proteggere l'oggetto stesso
816---------------------------
817
818In questo esempio, assumiamo che gli oggetti (ad eccezione del contatore
819di riferimenti) non cambino mai dopo la loro creazione. Se vogliamo permettere
820al nome di cambiare abbiamo tre possibilità:
821
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.
824
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.
828
829-  Si può decidere che ``cache_lock`` protegge solo la memoria stessa, ed
830   un altro *lock* è necessario per la protezione del nome.
831
832Teoricamente, possiamo avere un *lock* per ogni campo e per ogni oggetto.
833In pratica, le varianti più comuni sono:
834
835-  un *lock* che protegge l'infrastruttura (la lista ``cache`` di questo
836   esempio) e gli oggetti. Questo è quello che abbiamo fatto finora.
837
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.
841
842-  *lock* multipli per proteggere l'infrastruttura (per esempio un *lock*
843   per ogni lista), possibilmente con un *lock* per oggetto.
844
845Qui di seguito un'implementazione con "un lock per oggetto":
846
847::
848
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 @@
852
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     };
868
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);
875
876             spin_lock_irqsave(&cache_lock, flags);
877             __cache_add(obj);
878
879Da notare che ho deciso che il contatore di popolarità dovesse essere
880protetto da ``cache_lock`` piuttosto che dal *lock* dell'oggetto; questo
881perché è logicamente parte dell'infrastruttura (come
882:c:type:`struct list_head <list_head>` nell'oggetto). In questo modo,
883in __cache_add(), non ho bisogno di trattenere il *lock* di ogni
884oggetto mentre si cerca il meno popolare.
885
886Ho anche deciso che il campo id è immutabile, quindi non ho bisogno di
887trattenere il lock dell'oggetto quando si usa __cache_find()
888per leggere questo campo; il *lock* dell'oggetto è usato solo dal chiamante
889che vuole leggere o scrivere il campo name.
890
891Inoltre, da notare che ho aggiunto un commento che descrive i dati che sono
892protetti dal *lock*. Questo è estremamente importante in quanto descrive il
893comportamento del codice, che altrimenti sarebbe di difficile comprensione
894leggendo solamente il codice. E come dice Alan Cox: “Lock data, not code”.
895
896Problemi comuni
897===============
898
899.. _`it_deadlock`:
900
901Stallo: semplice ed avanzato
902----------------------------
903
904Esiste un tipo di  baco dove un pezzo di codice tenta di trattenere uno
905spinlock due volte: questo rimarrà in attesa attiva per sempre aspettando che
906il *lock* venga rilasciato (in Linux spinlocks, rwlocks e mutex non sono
907ricorsivi).
908Questo è facile da diagnosticare: non è uno di quei problemi che ti tengono
909sveglio 5 notti a parlare da solo.
910
911Un caso un pochino più complesso; immaginate d'avere una spazio condiviso
912fra un softirq ed il contesto utente. Se usate spin_lock() per
913proteggerlo, il contesto utente potrebbe essere interrotto da un softirq
914mentre trattiene il lock, da qui il softirq rimarrà in attesa attiva provando
915ad acquisire il *lock* già trattenuto nel contesto utente.
916
917Questi casi sono chiamati stalli (*deadlock*), e come mostrato qui sopra,
918può succedere anche con un solo processore (Ma non sui sistemi
919monoprocessore perché gli spinlock spariscano quando il kernel è compilato
920con ``CONFIG_SMP``\ =n. Nonostante ciò, nel secondo caso avrete comunque
921una corruzione dei dati).
922
923Questi casi sono facili da diagnosticare; sui sistemi multi-processore
924il supervisione (*watchdog*) o l'opzione di compilazione ``DEBUG_SPINLOCK``
925(``include/linux/spinlock.h``) permettono di scovare immediatamente quando
926succedono.
927
928Esiste un caso più complesso che è conosciuto come l'abbraccio della morte;
929questo coinvolge due o più *lock*. Diciamo che avete un vettore di hash in cui
930ogni elemento è uno spinlock a cui è associata una lista di elementi con lo
931stesso hash. In un gestore di interruzioni software, dovete modificare un
932oggetto e spostarlo su un altro hash; quindi dovrete trattenete lo spinlock
933del vecchio hash e di quello nuovo, quindi rimuovere l'oggetto dal vecchio ed
934inserirlo nel nuovo.
935
936Qui abbiamo due problemi. Primo, se il vostro codice prova a spostare un
937oggetto all'interno della stessa lista, otterrete uno stallo visto che
938tenterà di trattenere lo stesso *lock* due volte. Secondo, se la stessa
939interruzione software su un altro processore sta tentando di spostare
940un altro oggetto nella direzione opposta, potrebbe accadere quanto segue:
941
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+---------------------------------+---------------------------------+
949
950Table: Conseguenze
951
952Entrambe i processori rimarranno in attesa attiva sul *lock* per sempre,
953aspettando che l'altro lo rilasci. Sembra e puzza come un blocco totale.
954
955Prevenire gli stalli
956--------------------
957
958I libri di testo vi diranno che se trattenete i *lock* sempre nello stesso
959ordine non avrete mai un simile stallo. La pratica vi dirà che questo
960approccio 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*
962si incastrerà.
963
964I *lock* migliori sono quelli incapsulati: non vengono esposti nei file di
965intestazione, e non vengono mai trattenuti fuori dallo stesso file. Potete
966rileggere questo codice e vedere che non ci sarà mai uno stallo perché
967non tenterà mai di trattenere un altro *lock* quando lo ha già.
968Le persone che usano il vostro codice non devono nemmeno sapere che voi
969state usando dei *lock*.
970
971Un classico problema deriva dall'uso di *callback* e di *hook*: se li
972chiamate mentre trattenete un *lock*, rischiate uno stallo o un abbraccio
973della morte (chi lo sa cosa farà una *callback*?).
974
975Ossessiva prevenzione degli stalli
976~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
977
978Gli stalli sono un problema, ma non così terribile come la corruzione dei dati.
979Un pezzo di codice trattiene un *lock* di lettura, cerca in una lista,
980fallisce nel trovare quello che vuole, quindi rilascia il *lock* di lettura,
981trattiene un *lock* di scrittura ed inserisce un oggetto; questo genere di
982codice presenta una corsa critica.
983
984Se non riuscite a capire il perché, per favore state alla larga dal mio
985codice.
986
987corsa fra temporizzatori: un passatempo del kernel
988--------------------------------------------------
989
990I temporizzatori potrebbero avere dei problemi con le corse critiche.
991Considerate una collezione di oggetti (liste, hash, eccetera) dove ogni oggetto
992ha un temporizzatore che sta per distruggerlo.
993
994Se volete eliminare l'intera collezione (diciamo quando rimuovete un modulo),
995potreste fare come segue::
996
997            /* THIS CODE BAD BAD BAD BAD: IF IT WAS ANY WORSE IT WOULD USE
998               HUNGARIAN NOTATION */
999            spin_lock_bh(&list_lock);
1000
1001            while (list) {
1002                    struct foo *next = list->next;
1003                    del_timer(&list->timer);
1004                    kfree(list);
1005                    list = next;
1006            }
1007
1008            spin_unlock_bh(&list_lock);
1009
1010Primo o poi, questo esploderà su un sistema multiprocessore perché un
1011temporizzatore potrebbe essere già partiro prima di spin_lock_bh(),
1012e prenderà il *lock* solo dopo spin_unlock_bh(), e cercherà
1013di eliminare il suo oggetto (che però è già stato eliminato).
1014
1015Questo può essere evitato controllando il valore di ritorno di
1016del_timer(): se ritorna 1, il temporizzatore è stato già
1017rimosso. Se 0, significa (in questo caso) che il temporizzatore è in
1018esecuzione, quindi possiamo fare come segue::
1019
1020            retry:
1021                    spin_lock_bh(&list_lock);
1022
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                    }
1033
1034                    spin_unlock_bh(&list_lock);
1035
1036Un altro problema è l'eliminazione dei temporizzatori che si riavviano
1037da soli (chiamando add_timer() alla fine della loro esecuzione).
1038Dato che questo è un problema abbastanza comune con una propensione
1039alle corse critiche, dovreste usare del_timer_sync()
1040(``include/linux/timer.h``) per gestire questo caso. Questa ritorna il
1041numero di volte che il temporizzatore è stato interrotto prima che
1042fosse in grado di fermarlo senza che si riavviasse.
1043
1044Velocità della sincronizzazione
1045===============================
1046
1047Ci sono tre cose importanti da tenere in considerazione quando si valuta
1048la velocità d'esecuzione di un pezzo di codice che necessita di
1049sincronizzazione. La prima è la concorrenza: quante cose rimangono in attesa
1050mentre qualcuno trattiene un *lock*. La seconda è il tempo necessario per
1051acquisire (senza contese) e rilasciare un *lock*. La terza è di usare meno
1052*lock* o di più furbi. Immagino che i *lock* vengano usati regolarmente,
1053altrimenti, non sareste interessati all'efficienza.
1054
1055La concorrenza dipende da quanto a lungo un *lock* è trattenuto: dovreste
1056trattenere un *lock* solo il tempo minimo necessario ma non un istante in più.
1057Nella memoria dell'esempio precedente, creiamo gli oggetti senza trattenere
1058il *lock*, poi acquisiamo il *lock* quando siamo pronti per inserirlo nella
1059lista.
1060
1061Il tempo di acquisizione di un *lock* dipende da quanto danno fa
1062l'operazione sulla *pipeline* (ovvero stalli della *pipeline*) e quant'è
1063probabile che il processore corrente sia stato anche l'ultimo ad acquisire
1064il *lock* (in pratica, il *lock* è nella memoria cache del processore
1065corrente?): su sistemi multi-processore questa probabilità precipita
1066rapidamente. Consideriamo un processore Intel Pentium III a 700Mhz: questo
1067esegue un'istruzione in 0.7ns, un incremento atomico richiede 58ns, acquisire
1068un *lock* che è nella memoria cache del processore richiede 160ns, e un
1069trasferimento dalla memoria cache di un altro processore richiede altri
1070170/360ns (Leggetevi l'articolo di Paul McKenney's `Linux Journal RCU
1071article <http://www.linuxjournal.com/article.php?sid=6993>`__).
1072
1073Questi due obiettivi sono in conflitto: trattenere un *lock* per il minor
1074tempo possibile potrebbe richiedere la divisione in più *lock* per diverse
1075parti (come nel nostro ultimo esempio con un *lock* per ogni oggetto),
1076ma questo aumenta il numero di acquisizioni di *lock*, ed il risultato
1077spesso è che tutto è più lento che con un singolo *lock*. Questo è un altro
1078argomento in favore della semplicità quando si parla di sincronizzazione.
1079
1080Il terzo punto è discusso di seguito: ci sono alcune tecniche per ridurre
1081il numero di sincronizzazioni che devono essere fatte.
1082
1083Read/Write Lock Variants
1084------------------------
1085
1086Sia 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>`.
1088Queste dividono gli utenti in due categorie: i lettori e gli scrittori.
1089Se state solo leggendo i dati, potete acquisire il *lock* di lettura, ma
1090per scrivere avrete bisogno del *lock* di scrittura. Molti possono trattenere
1091il *lock* di lettura, ma solo uno scrittore alla volta può trattenere
1092quello di scrittura.
1093
1094Se il vostro codice si divide chiaramente in codice per lettori e codice
1095per scrittori (come nel nostro esempio), e il *lock* dei lettori viene
1096trattenuto per molto tempo, allora l'uso di questo tipo di *lock* può aiutare.
1097Questi sono leggermente più lenti rispetto alla loro versione normale, quindi
1098nella pratica l'uso di ``rwlock_t`` non ne vale la pena.
1099
1100Evitare i *lock*: Read Copy Update
1101--------------------------------------------
1102
1103Esiste un metodo di sincronizzazione per letture e scritture detto
1104Read Copy Update. Con l'uso della tecnica RCU, i lettori possono scordarsi
1105completamente di trattenere i *lock*; dato che nel nostro esempio ci
1106aspettiamo d'avere più lettore che scrittori (altrimenti questa memoria
1107sarebbe uno spreco) possiamo dire che questo meccanismo permette
1108un'ottimizzazione.
1109
1110Come facciamo a sbarazzarci dei *lock* di lettura? Sbarazzarsi dei *lock* di
1111lettura significa che uno scrittore potrebbe cambiare la lista sotto al naso
1112dei lettori. Questo è abbastanza semplice: possiamo leggere una lista
1113concatenata se lo scrittore aggiunge elementi alla fine e con certe
1114precauzioni. Per esempio, aggiungendo ``new`` ad una lista concatenata
1115chiamata ``list``::
1116
1117            new->next = list->next;
1118            wmb();
1119            list->next = new;
1120
1121La funzione wmb() è una barriera di sincronizzazione delle
1122scritture. Questa garantisce che la prima operazione (impostare l'elemento
1123``next`` del nuovo elemento) venga completata e vista da tutti i processori
1124prima che venga eseguita la seconda operazione (che sarebbe quella di mettere
1125il nuovo elemento nella lista). Questo è importante perché i moderni
1126compilatori ed i moderni processori possono, entrambe, riordinare le istruzioni
1127se non vengono istruiti altrimenti: vogliamo che i lettori non vedano
1128completamente il nuovo elemento; oppure che lo vedano correttamente e quindi
1129il puntatore ``next`` deve puntare al resto della lista.
1130
1131Fortunatamente, 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``).
1134
1135Rimuovere un elemento dalla lista è anche più facile: sostituiamo il puntatore
1136al vecchio elemento con quello del suo successore, e i lettori vedranno
1137l'elemento o lo salteranno.
1138
1139::
1140
1141            list->next = old->next;
1142
1143La funzione list_del_rcu() (``include/linux/list.h``) fa esattamente
1144questo (la versione normale corrompe il vecchio oggetto, e non vogliamo che
1145accada).
1146
1147Anche i lettori devono stare attenti: alcuni processori potrebbero leggere
1148attraverso il puntatore ``next`` il contenuto dell'elemento successivo
1149troppo presto, ma non accorgersi che il contenuto caricato è sbagliato quando
1150il puntatore ``next`` viene modificato alla loro spalle. Ancora una volta
1151c'è una funzione che viene in vostro aiuto list_for_each_entry_rcu()
1152(``include/linux/list.h``). Ovviamente, gli scrittori possono usare
1153list_for_each_entry() dato che non ci possono essere due scrittori
1154in contemporanea.
1155
1156Il nostro ultimo dilemma è il seguente: quando possiamo realmente distruggere
1157l'elemento rimosso? Ricordate, un lettore potrebbe aver avuto accesso a questo
1158elemento proprio ora: se eliminiamo questo elemento ed il puntatore ``next``
1159cambia, il lettore salterà direttamente nella spazzatura e scoppierà. Dobbiamo
1160aspettare finché tutti i lettori che stanno attraversando la lista abbiano
1161finito. Utilizziamo call_rcu() per registrare una funzione di
1162richiamo che distrugga l'oggetto quando tutti i lettori correnti hanno
1163terminato. In alternative, potrebbe essere usata la funzione
1164synchronize_rcu() che blocca l'esecuzione finché tutti i lettori
1165non terminano di ispezionare la lista.
1166
1167Ma come fa l'RCU a sapere quando i lettori sono finiti? Il meccanismo è
1168il seguente: innanzi tutto i lettori accedono alla lista solo fra la coppia
1169rcu_read_lock()/rcu_read_unlock() che disabilita la
1170prelazione così che i lettori non vengano sospesi mentre stanno leggendo
1171la lista.
1172
1173Poi, l'RCU aspetta finché tutti i processori non abbiano dormito almeno
1174una volta; a questo punto, dato che i lettori non possono dormire, possiamo
1175dedurre che un qualsiasi lettore che abbia consultato la lista durante la
1176rimozione abbia già terminato, quindi la *callback* viene eseguita. Il vero
1177codice RCU è un po' più ottimizzato di così, ma questa è l'idea di fondo.
1178
1179::
1180
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>
1190
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;
1197
1198    +        struct rcu_head rcu;
1199    +
1200             atomic_t refcnt;
1201
1202             /* Doesn't change once created. */
1203    @@ -40,7 +43,7 @@
1204     {
1205             struct object *i;
1206
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     }
1215
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     }
1232
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;
1246
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     }
1256
1257Da notare che i lettori modificano il campo popularity nella funzione
1258__cache_find(), e ora non trattiene alcun *lock*. Una soluzione
1259potrebbe essere quella di rendere la variabile ``atomic_t``, ma per l'uso
1260che ne abbiamo fatto qui, non ci interessano queste corse critiche perché un
1261risultato approssimativo è comunque accettabile, quindi non l'ho cambiato.
1262
1263Il risultato è che la funzione cache_find() non ha bisogno di alcuna
1264sincronizzazione con le altre funzioni, quindi è veloce su un sistema
1265multi-processore tanto quanto lo sarebbe su un sistema mono-processore.
1266
1267Esiste un'ulteriore ottimizzazione possibile: vi ricordate il codice originale
1268della nostra memoria dove non c'erano contatori di riferimenti e il chiamante
1269semplicemente tratteneva il *lock* prima di accedere ad un oggetto? Questo è
1270ancora possibile: se trattenete un *lock* nessuno potrà cancellare l'oggetto,
1271quindi non avete bisogno di incrementare e decrementare il contatore di
1272riferimenti.
1273
1274Ora, dato che il '*lock* di lettura' di un RCU non fa altro che disabilitare
1275la prelazione, un chiamante che ha sempre la prelazione disabilitata fra le
1276chiamate cache_find() e object_put() non necessita
1277di incrementare e decrementare il contatore di riferimenti. Potremmo
1278esporre la funzione __cache_find() dichiarandola non-static,
1279e quel chiamante potrebbe usare direttamente questa funzione.
1280
1281Il beneficio qui sta nel fatto che il contatore di riferimenti no
1282viene scritto: l'oggetto non viene alterato in alcun modo e quindi diventa
1283molto più veloce su sistemi molti-processore grazie alla loro memoria cache.
1284
1285.. _`it_per-cpu`:
1286
1287Dati per processore
1288-------------------
1289
1290Un'altra tecnica comunemente usata per evitare la sincronizzazione è quella
1291di duplicare le informazioni per ogni processore. Per esempio, se volete
1292avere un contatore di qualcosa, potreste utilizzare uno spinlock ed un
1293singolo contatore. Facile e pulito.
1294
1295Se questo dovesse essere troppo lento (solitamente non lo è, ma se avete
1296dimostrato che lo è devvero), potreste usare un contatore per ogni processore
1297e quindi non sarebbe più necessaria la mutua esclusione. Vedere
1298DEFINE_PER_CPU(), get_cpu_var() e put_cpu_var()
1299(``include/linux/percpu.h``).
1300
1301Il tipo di dato ``local_t``, la funzione cpu_local_inc() e tutte
1302le altre funzioni associate, sono di particolare utilità per semplici contatori
1303per-processore; su alcune architetture sono anche più efficienti
1304(``include/asm/local.h``).
1305
1306Da notare che non esiste un modo facile ed affidabile per ottenere il valore
1307di un simile contatore senza introdurre altri *lock*. In alcuni casi questo
1308non è un problema.
1309
1310Dati che sono usati prevalentemente dai gestori d'interruzioni
1311--------------------------------------------------------------
1312
1313Se i dati vengono utilizzati sempre dallo stesso gestore d'interruzioni,
1314allora i *lock* non vi servono per niente: il kernel già vi garantisce che
1315il gestore d'interruzione non verrà eseguito in contemporanea su diversi
1316processori.
1317
1318Manfred Spraul fa notare che potreste comunque comportarvi così anche
1319se i dati vengono occasionalmente utilizzati da un contesto utente o
1320da un'interruzione software. Il gestore d'interruzione non utilizza alcun
1321*lock*, e tutti gli altri accessi verranno fatti così::
1322
1323        spin_lock(&lock);
1324        disable_irq(irq);
1325        ...
1326        enable_irq(irq);
1327        spin_unlock(&lock);
1328
1329La funzione disable_irq() impedisce al gestore d'interruzioni
1330d'essere eseguito (e aspetta che finisca nel caso fosse in esecuzione su
1331un altro processore). Lo spinlock, invece, previene accessi simultanei.
1332Naturalmente, questo è più lento della semplice chiamata
1333spin_lock_irq(), quindi ha senso solo se questo genere di accesso
1334è estremamente raro.
1335
1336.. _`it_sleeping-things`:
1337
1338Quali funzioni possono essere chiamate in modo sicuro dalle interruzioni?
1339=========================================================================
1340
1341Molte funzioni del kernel dormono (in sostanza, chiamano schedule())
1342direttamente od indirettamente: non potete chiamarle se trattenere uno
1343spinlock o avete la prelazione disabilitata, mai. Questo significa che
1344dovete necessariamente essere nel contesto utente: chiamarle da un
1345contesto d'interruzione è illegale.
1346
1347Alcune funzioni che dormono
1348---------------------------
1349
1350Le più comuni sono elencate qui di seguito, ma solitamente dovete leggere
1351il codice per scoprire se altre chiamate sono sicure. Se chiunque altro
1352le chiami dorme, allora dovreste poter dormire anche voi. In particolar
1353modo, le funzioni di registrazione e deregistrazione solitamente si
1354aspettano d'essere chiamante da un contesto utente e quindi che possono
1355dormire.
1356
1357-  Accessi allo spazio utente:
1358
1359   -  copy_from_user()
1360
1361   -  copy_to_user()
1362
1363   -  get_user()
1364
1365   -  put_user()
1366
1367-  kmalloc(GFP_KERNEL) <kmalloc>`
1368
1369-  mutex_lock_interruptible() and
1370   mutex_lock()
1371
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.
1378
1379Alcune funzioni che non dormono
1380-------------------------------
1381
1382Alcune funzioni possono essere chiamate tranquillamente da qualsiasi
1383contesto, o trattenendo un qualsiasi *lock*.
1384
1385-  printk()
1386
1387-  kfree()
1388
1389-  add_timer() e del_timer()
1390
1391Riferimento per l'API dei Mutex
1392===============================
1393
1394.. kernel-doc:: include/linux/mutex.h
1395   :internal:
1396
1397.. kernel-doc:: kernel/locking/mutex.c
1398   :export:
1399
1400Riferimento per l'API dei Futex
1401===============================
1402
1403.. kernel-doc:: kernel/futex.c
1404   :internal:
1405
1406Approfondimenti
1407===============
1408
1409-  ``Documentation/locking/spinlocks.rst``: la guida di Linus Torvalds agli
1410   spinlock del kernel.
1411
1412-  Unix Systems for Modern Architectures: Symmetric Multiprocessing and
1413   Caching for Kernel Programmers.
1414
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]
1420
1421Ringraziamenti
1422==============
1423
1424Grazie a Telsa Gwynne per aver formattato questa guida in DocBook, averla
1425pulita e aggiunto un po' di stile.
1426
1427Grazie a Martin Pool, Philipp Rumpf, Stephen Rothwell, Paul Mackerras,
1428Ruedi Aschwanden, Alan Cox, Manfred Spraul, Tim Waugh, Pete Zaitcev,
1429James Morris, Robert Love, Paul McKenney, John Ashby per aver revisionato,
1430corretto, maledetto e commentato.
1431
1432Grazie alla congrega per non aver avuto alcuna influenza su questo documento.
1433
1434Glossario
1435=========
1436
1437prelazione
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.
1445
1446bh
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.
1453
1454contesto d'interruzione
1455  Non è il contesto utente: qui si processano le interruzioni hardware e
1456  software. La macro in_interrupt() ritorna vero.
1457
1458contesto 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.
1464
1465interruzione hardware
1466  Richiesta di interruzione hardware. in_irq() ritorna vero in un
1467  gestore d'interruzioni hardware.
1468
1469interruzione 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'.
1473
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).
1477
1478monoprocessore / UP
1479  (Uni-Processor) un solo processore, ovvero non è SMP. (``CONFIG_SMP=n``).
1480
1481multi-processore / SMP
1482  (Symmetric Multi-Processor) kernel compilati per sistemi multi-processore
1483  (``CONFIG_SMP=y``).
1484
1485spazio utente
1486  Un processo che esegue il proprio codice fuori dal kernel.
1487
1488tasklet
1489  Un'interruzione software registrabile dinamicamente che ha la garanzia
1490  d'essere eseguita solo su un processore alla volta.
1491
1492timer
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``).
1496