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