0001 .. include:: ../disclaimer-ita.rst
0002
0003 .. c:namespace:: it_IT
0004
0005 :Original: :ref:`Documentation/kernel-hacking/locking.rst <kernel_hacking_lock>`
0006 :Translator: Federico Vaga <federico.vaga@vaga.pv.it>
0007
0008 .. _it_kernel_hacking_lock:
0009
0010 ==========================================
0011 L'inaffidabile guida alla sincronizzazione
0012 ==========================================
0013
0014 :Author: Rusty Russell
0015
0016 Introduzione
0017 ============
0018
0019 Benvenuto, alla notevole ed inaffidabile guida ai problemi di sincronizzazione
0020 (locking) nel kernel. Questo documento descrive il sistema di sincronizzazione
0021 nel kernel Linux 2.6.
0022
0023 Dato il largo utilizzo del multi-threading e della prelazione nel kernel
0024 Linux, chiunque voglia dilettarsi col kernel deve conoscere i concetti
0025 fondamentali della concorrenza e della sincronizzazione nei sistemi
0026 multi-processore.
0027
0028 Il problema con la concorrenza
0029 ==============================
0030
0031 (Saltatelo se sapete già cos'è una corsa critica).
0032
0033 In un normale programma, potete incrementare un contatore nel seguente modo:
0034
0035 ::
0036
0037 contatore++;
0038
0039 Questo è quello che vi aspettereste che accada sempre:
0040
0041
0042 .. table:: Risultati attesi
0043
0044 +------------------------------------+------------------------------------+
0045 | Istanza 1 | Istanza 2 |
0046 +====================================+====================================+
0047 | leggi contatore (5) | |
0048 +------------------------------------+------------------------------------+
0049 | aggiungi 1 (6) | |
0050 +------------------------------------+------------------------------------+
0051 | scrivi contatore (6) | |
0052 +------------------------------------+------------------------------------+
0053 | | leggi contatore (6) |
0054 +------------------------------------+------------------------------------+
0055 | | aggiungi 1 (7) |
0056 +------------------------------------+------------------------------------+
0057 | | scrivi contatore (7) |
0058 +------------------------------------+------------------------------------+
0059
0060 Questo è quello che potrebbe succedere in realtà:
0061
0062 .. table:: Possibile risultato
0063
0064 +------------------------------------+------------------------------------+
0065 | Istanza 1 | Istanza 2 |
0066 +====================================+====================================+
0067 | leggi contatore (5) | |
0068 +------------------------------------+------------------------------------+
0069 | | leggi contatore (5) |
0070 +------------------------------------+------------------------------------+
0071 | aggiungi 1 (6) | |
0072 +------------------------------------+------------------------------------+
0073 | | aggiungi 1 (6) |
0074 +------------------------------------+------------------------------------+
0075 | scrivi contatore (6) | |
0076 +------------------------------------+------------------------------------+
0077 | | scrivi contatore (6) |
0078 +------------------------------------+------------------------------------+
0079
0080
0081 Corse critiche e sezioni critiche
0082 ---------------------------------
0083
0084 Questa sovrapposizione, ovvero quando un risultato dipende dal tempo che
0085 intercorre fra processi diversi, è chiamata corsa critica. La porzione
0086 di codice che contiene questo problema è chiamata sezione critica.
0087 In particolar modo da quando Linux ha incominciato a girare su
0088 macchine multi-processore, le sezioni critiche sono diventate uno dei
0089 maggiori problemi di progettazione ed implementazione del kernel.
0090
0091 La prelazione può sortire gli stessi effetti, anche se c'è una sola CPU:
0092 interrompendo un processo nella sua sezione critica otterremo comunque
0093 la stessa corsa critica. In questo caso, il thread che si avvicenda
0094 nell'esecuzione potrebbe eseguire anch'esso la sezione critica.
0095
0096 La soluzione è quella di riconoscere quando avvengono questi accessi
0097 simultanei, ed utilizzare i *lock* per accertarsi che solo un'istanza
0098 per volta possa entrare nella sezione critica. Il kernel offre delle buone
0099 funzioni a questo scopo. E poi ci sono quelle meno buone, ma farò finta
0100 che non esistano.
0101
0102 Sincronizzazione nel kernel Linux
0103 =================================
0104
0105 Se dovessi darvi un suggerimento sulla sincronizzazione: **mantenetela
0106 semplice**.
0107
0108 Siate riluttanti nell'introduzione di nuovi *lock*.
0109
0110 I due principali tipi di *lock* nel kernel: spinlock e mutex
0111 ------------------------------------------------------------
0112
0113 Ci sono due tipi principali di *lock* nel kernel. Il tipo fondamentale è lo
0114 spinlock (``include/asm/spinlock.h``), un semplice *lock* che può essere
0115 trattenuto solo da un processo: se non si può trattenere lo spinlock, allora
0116 rimane in attesa attiva (in inglese *spinning*) finché non ci riesce.
0117 Gli spinlock sono molto piccoli e rapidi, possono essere utilizzati ovunque.
0118
0119 Il secondo tipo è il mutex (``include/linux/mutex.h``): è come uno spinlock,
0120 ma potreste bloccarvi trattenendolo. Se non potete trattenere un mutex
0121 il vostro processo si auto-sospenderà; verrà riattivato quando il mutex
0122 verrà rilasciato. Questo significa che il processore potrà occuparsi d'altro
0123 mentre il vostro processo è in attesa. Esistono molti casi in cui non potete
0124 permettervi di sospendere un processo (vedere
0125 `Quali funzioni possono essere chiamate in modo sicuro dalle interruzioni?`_)
0126 e quindi dovrete utilizzare gli spinlock.
0127
0128 Nessuno di questi *lock* è ricorsivo: vedere
0129 `Stallo: semplice ed avanzato`_
0130
0131 I *lock* e i kernel per sistemi monoprocessore
0132 ----------------------------------------------
0133
0134 Per i kernel compilati senza ``CONFIG_SMP`` e senza ``CONFIG_PREEMPT``
0135 gli spinlock non esistono. Questa è un'ottima scelta di progettazione:
0136 quando nessun altro processo può essere eseguito in simultanea, allora
0137 non c'è la necessità di avere un *lock*.
0138
0139 Se il kernel è compilato senza ``CONFIG_SMP`` ma con ``CONFIG_PREEMPT``,
0140 allora gli spinlock disabilitano la prelazione; questo è sufficiente a
0141 prevenire le corse critiche. Nella maggior parte dei casi, possiamo considerare
0142 la prelazione equivalente ad un sistema multi-processore senza preoccuparci
0143 di trattarla indipendentemente.
0144
0145 Dovreste verificare sempre la sincronizzazione con le opzioni ``CONFIG_SMP`` e
0146 ``CONFIG_PREEMPT`` abilitate, anche quando non avete un sistema
0147 multi-processore, questo vi permetterà di identificare alcuni problemi
0148 di sincronizzazione.
0149
0150 Come vedremo di seguito, i mutex continuano ad esistere perché sono necessari
0151 per la sincronizzazione fra processi in contesto utente.
0152
0153 Sincronizzazione in contesto utente
0154 -----------------------------------
0155
0156 Se avete una struttura dati che verrà utilizzata solo dal contesto utente,
0157 allora, per proteggerla, potete utilizzare un semplice mutex
0158 (``include/linux/mutex.h``). Questo è il caso più semplice: inizializzate il
0159 mutex; invocate mutex_lock_interruptible() per trattenerlo e
0160 mutex_unlock() per rilasciarlo. C'è anche mutex_lock()
0161 ma questa dovrebbe essere evitata perché non ritorna in caso di segnali.
0162
0163 Per esempio: ``net/netfilter/nf_sockopt.c`` permette la registrazione
0164 di nuove chiamate per setsockopt() e getsockopt()
0165 usando la funzione nf_register_sockopt(). La registrazione e
0166 la rimozione vengono eseguite solamente quando il modulo viene caricato
0167 o scaricato (e durante l'avvio del sistema, qui non abbiamo concorrenza),
0168 e la lista delle funzioni registrate viene consultata solamente quando
0169 setsockopt() o getsockopt() sono sconosciute al sistema.
0170 In questo caso ``nf_sockopt_mutex`` è perfetto allo scopo, in particolar modo
0171 visto che setsockopt e getsockopt potrebbero dormire.
0172
0173 Sincronizzazione fra il contesto utente e i softirq
0174 ---------------------------------------------------
0175
0176 Se un softirq condivide dati col contesto utente, avete due problemi.
0177 Primo, il contesto utente corrente potrebbe essere interroto da un softirq,
0178 e secondo, la sezione critica potrebbe essere eseguita da un altro
0179 processore. Questo è quando spin_lock_bh()
0180 (``include/linux/spinlock.h``) viene utilizzato. Questo disabilita i softirq
0181 sul processore e trattiene il *lock*. Invece, spin_unlock_bh() fa
0182 l'opposto. (Il suffisso '_bh' è un residuo storico che fa riferimento al
0183 "Bottom Halves", il vecchio nome delle interruzioni software. In un mondo
0184 perfetto questa funzione si chiamerebbe 'spin_lock_softirq()').
0185
0186 Da notare che in questo caso potete utilizzare anche spin_lock_irq()
0187 o spin_lock_irqsave(), queste fermano anche le interruzioni hardware:
0188 vedere `Contesto di interruzione hardware`_.
0189
0190 Questo funziona alla perfezione anche sui sistemi monoprocessore: gli spinlock
0191 svaniscono e questa macro diventa semplicemente local_bh_disable()
0192 (``include/linux/interrupt.h``), la quale impedisce ai softirq d'essere
0193 eseguiti.
0194
0195 Sincronizzazione fra contesto utente e i tasklet
0196 ------------------------------------------------
0197
0198 Questo caso è uguale al precedente, un tasklet viene eseguito da un softirq.
0199
0200 Sincronizzazione fra contesto utente e i timer
0201 ----------------------------------------------
0202
0203 Anche questo caso è uguale al precedente, un timer viene eseguito da un
0204 softirq.
0205 Dal punto di vista della sincronizzazione, tasklet e timer sono identici.
0206
0207 Sincronizzazione fra tasklet e timer
0208 ------------------------------------
0209
0210 Qualche volta un tasklet od un timer potrebbero condividere i dati con
0211 un altro tasklet o timer
0212
0213 Lo stesso tasklet/timer
0214 ~~~~~~~~~~~~~~~~~~~~~~~
0215
0216 Dato che un tasklet non viene mai eseguito contemporaneamente su due
0217 processori, non dovete preoccuparvi che sia rientrante (ovvero eseguito
0218 più volte in contemporanea), perfino su sistemi multi-processore.
0219
0220 Differenti tasklet/timer
0221 ~~~~~~~~~~~~~~~~~~~~~~~~
0222
0223 Se un altro tasklet/timer vuole condividere dati col vostro tasklet o timer,
0224 allora avrete bisogno entrambe di spin_lock() e
0225 spin_unlock(). Qui spin_lock_bh() è inutile, siete già
0226 in un tasklet ed avete la garanzia che nessun altro verrà eseguito sullo
0227 stesso processore.
0228
0229 Sincronizzazione fra softirq
0230 ----------------------------
0231
0232 Spesso un softirq potrebbe condividere dati con se stesso o un tasklet/timer.
0233
0234 Lo stesso softirq
0235 ~~~~~~~~~~~~~~~~~
0236
0237 Lo stesso softirq può essere eseguito su un diverso processore: allo scopo
0238 di migliorare le prestazioni potete utilizzare dati riservati ad ogni
0239 processore (vedere `Dati per processore`_). Se siete arrivati
0240 fino a questo punto nell'uso dei softirq, probabilmente tenete alla scalabilità
0241 delle prestazioni abbastanza da giustificarne la complessità aggiuntiva.
0242
0243 Dovete utilizzare spin_lock() e spin_unlock() per
0244 proteggere i dati condivisi.
0245
0246 Diversi Softirqs
0247 ~~~~~~~~~~~~~~~~
0248
0249 Dovete utilizzare spin_lock() e spin_unlock() per
0250 proteggere i dati condivisi, che siano timer, tasklet, diversi softirq o
0251 lo stesso o altri softirq: uno qualsiasi di essi potrebbe essere in esecuzione
0252 su un diverso processore.
0253
0254 .. _`it_hardirq-context`:
0255
0256 Contesto di interruzione hardware
0257 =================================
0258
0259 Solitamente le interruzioni hardware comunicano con un tasklet o un softirq.
0260 Spesso questo si traduce nel mettere in coda qualcosa da fare che verrà
0261 preso in carico da un softirq.
0262
0263 Sincronizzazione fra interruzioni hardware e softirq/tasklet
0264 ------------------------------------------------------------
0265
0266 Se un gestore di interruzioni hardware condivide dati con un softirq, allora
0267 avrete due preoccupazioni. Primo, il softirq può essere interrotto da
0268 un'interruzione hardware, e secondo, la sezione critica potrebbe essere
0269 eseguita da un'interruzione hardware su un processore diverso. Questo è il caso
0270 dove spin_lock_irq() viene utilizzato. Disabilita le interruzioni
0271 sul processore che l'esegue, poi trattiene il lock. spin_unlock_irq()
0272 fa l'opposto.
0273
0274 Il gestore d'interruzione hardware non ha bisogno di usare spin_lock_irq()
0275 perché i softirq non possono essere eseguiti quando il gestore d'interruzione
0276 hardware è in esecuzione: per questo si può usare spin_lock(), che è un po'
0277 più veloce. L'unica eccezione è quando un altro gestore d'interruzioni
0278 hardware utilizza lo stesso *lock*: spin_lock_irq() impedirà a questo
0279 secondo gestore di interrompere quello in esecuzione.
0280
0281 Questo funziona alla perfezione anche sui sistemi monoprocessore: gli spinlock
0282 svaniscono e questa macro diventa semplicemente local_irq_disable()
0283 (``include/asm/smp.h``), la quale impedisce a softirq/tasklet/BH d'essere
0284 eseguiti.
0285
0286 spin_lock_irqsave() (``include/linux/spinlock.h``) è una variante che
0287 salva lo stato delle interruzioni in una variabile, questa verrà poi passata
0288 a spin_unlock_irqrestore(). Questo significa che lo stesso codice
0289 potrà essere utilizzato in un'interruzione hardware (dove le interruzioni sono
0290 già disabilitate) e in un softirq (dove la disabilitazione delle interruzioni
0291 è richiesta).
0292
0293 Da notare che i softirq (e quindi tasklet e timer) sono eseguiti al ritorno
0294 da un'interruzione hardware, quindi spin_lock_irq() interrompe
0295 anche questi. Tenuto conto di questo si può dire che
0296 spin_lock_irqsave() è la funzione di sincronizzazione più generica
0297 e potente.
0298
0299 Sincronizzazione fra due gestori d'interruzioni hardware
0300 --------------------------------------------------------
0301
0302 Condividere dati fra due gestori di interruzione hardware è molto raro, ma se
0303 succede, dovreste usare spin_lock_irqsave(): è una specificità
0304 dell'architettura il fatto che tutte le interruzioni vengano interrotte
0305 quando si eseguono di gestori di interruzioni.
0306
0307 Bigino della sincronizzazione
0308 =============================
0309
0310 Pete Zaitcev ci offre il seguente riassunto:
0311
0312 - Se siete in un contesto utente (una qualsiasi chiamata di sistema)
0313 e volete sincronizzarvi con altri processi, usate i mutex. Potete trattenere
0314 il mutex e dormire (``copy_from_user(`` o ``kmalloc(x,GFP_KERNEL)``).
0315
0316 - Altrimenti (== i dati possono essere manipolati da un'interruzione) usate
0317 spin_lock_irqsave() e spin_unlock_irqrestore().
0318
0319 - Evitate di trattenere uno spinlock per più di 5 righe di codice incluse
0320 le chiamate a funzione (ad eccezione di quell per l'accesso come
0321 readb()).
0322
0323 Tabella dei requisiti minimi
0324 ----------------------------
0325
0326 La tabella seguente illustra i requisiti **minimi** per la sincronizzazione fra
0327 diversi contesti. In alcuni casi, lo stesso contesto può essere eseguito solo
0328 da un processore per volta, quindi non ci sono requisiti per la
0329 sincronizzazione (per esempio, un thread può essere eseguito solo su un
0330 processore alla volta, ma se deve condividere dati con un altro thread, allora
0331 la sincronizzazione è necessaria).
0332
0333 Ricordatevi il suggerimento qui sopra: potete sempre usare
0334 spin_lock_irqsave(), che è un sovrainsieme di tutte le altre funzioni
0335 per spinlock.
0336
0337 ============== ============= ============= ========= ========= ========= ========= ======= ======= ============== ==============
0338 . IRQ Handler A IRQ Handler B Softirq A Softirq B Tasklet A Tasklet B Timer A Timer B User Context A User Context B
0339 ============== ============= ============= ========= ========= ========= ========= ======= ======= ============== ==============
0340 IRQ Handler A None
0341 IRQ Handler B SLIS None
0342 Softirq A SLI SLI SL
0343 Softirq B SLI SLI SL SL
0344 Tasklet A SLI SLI SL SL None
0345 Tasklet B SLI SLI SL SL SL None
0346 Timer A SLI SLI SL SL SL SL None
0347 Timer B SLI SLI SL SL SL SL SL None
0348 User Context A SLI SLI SLBH SLBH SLBH SLBH SLBH SLBH None
0349 User Context B SLI SLI SLBH SLBH SLBH SLBH SLBH SLBH MLI None
0350 ============== ============= ============= ========= ========= ========= ========= ======= ======= ============== ==============
0351
0352 Table: Tabella dei requisiti per la sincronizzazione
0353
0354 +--------+----------------------------+
0355 | SLIS | spin_lock_irqsave |
0356 +--------+----------------------------+
0357 | SLI | spin_lock_irq |
0358 +--------+----------------------------+
0359 | SL | spin_lock |
0360 +--------+----------------------------+
0361 | SLBH | spin_lock_bh |
0362 +--------+----------------------------+
0363 | MLI | mutex_lock_interruptible |
0364 +--------+----------------------------+
0365
0366 Table: Legenda per la tabella dei requisiti per la sincronizzazione
0367
0368 Le funzioni *trylock*
0369 =====================
0370
0371 Ci sono funzioni che provano a trattenere un *lock* solo una volta e
0372 ritornano immediatamente comunicato il successo od il fallimento
0373 dell'operazione. Posso essere usate quando non serve accedere ai dati
0374 protetti dal *lock* quando qualche altro thread lo sta già facendo
0375 trattenendo il *lock*. Potrete acquisire il *lock* più tardi se vi
0376 serve accedere ai dati protetti da questo *lock*.
0377
0378 La funzione spin_trylock() non ritenta di acquisire il *lock*,
0379 se ci riesce al primo colpo ritorna un valore diverso da zero, altrimenti
0380 se fallisce ritorna 0. Questa funzione può essere utilizzata in un qualunque
0381 contesto, ma come spin_lock(): dovete disabilitare i contesti che
0382 potrebbero interrompervi e quindi trattenere lo spinlock.
0383
0384 La funzione mutex_trylock() invece di sospendere il vostro processo
0385 ritorna un valore diverso da zero se è possibile trattenere il lock al primo
0386 colpo, altrimenti se fallisce ritorna 0. Nonostante non dorma, questa funzione
0387 non può essere usata in modo sicuro in contesti di interruzione hardware o
0388 software.
0389
0390 Esempi più comuni
0391 =================
0392
0393 Guardiamo un semplice esempio: una memoria che associa nomi a numeri.
0394 La memoria tiene traccia di quanto spesso viene utilizzato ogni oggetto;
0395 quando è piena, l'oggetto meno usato viene eliminato.
0396
0397 Tutto in contesto utente
0398 ------------------------
0399
0400 Nel primo esempio, supponiamo che tutte le operazioni avvengano in contesto
0401 utente (in soldoni, da una chiamata di sistema), quindi possiamo dormire.
0402 Questo significa che possiamo usare i mutex per proteggere la nostra memoria
0403 e tutti gli oggetti che contiene. Ecco il codice::
0404
0405 #include <linux/list.h>
0406 #include <linux/slab.h>
0407 #include <linux/string.h>
0408 #include <linux/mutex.h>
0409 #include <asm/errno.h>
0410
0411 struct object
0412 {
0413 struct list_head list;
0414 int id;
0415 char name[32];
0416 int popularity;
0417 };
0418
0419 /* Protects the cache, cache_num, and the objects within it */
0420 static DEFINE_MUTEX(cache_lock);
0421 static LIST_HEAD(cache);
0422 static unsigned int cache_num = 0;
0423 #define MAX_CACHE_SIZE 10
0424
0425 /* Must be holding cache_lock */
0426 static struct object *__cache_find(int id)
0427 {
0428 struct object *i;
0429
0430 list_for_each_entry(i, &cache, list)
0431 if (i->id == id) {
0432 i->popularity++;
0433 return i;
0434 }
0435 return NULL;
0436 }
0437
0438 /* Must be holding cache_lock */
0439 static void __cache_delete(struct object *obj)
0440 {
0441 BUG_ON(!obj);
0442 list_del(&obj->list);
0443 kfree(obj);
0444 cache_num--;
0445 }
0446
0447 /* Must be holding cache_lock */
0448 static void __cache_add(struct object *obj)
0449 {
0450 list_add(&obj->list, &cache);
0451 if (++cache_num > MAX_CACHE_SIZE) {
0452 struct object *i, *outcast = NULL;
0453 list_for_each_entry(i, &cache, list) {
0454 if (!outcast || i->popularity < outcast->popularity)
0455 outcast = i;
0456 }
0457 __cache_delete(outcast);
0458 }
0459 }
0460
0461 int cache_add(int id, const char *name)
0462 {
0463 struct object *obj;
0464
0465 if ((obj = kmalloc(sizeof(*obj), GFP_KERNEL)) == NULL)
0466 return -ENOMEM;
0467
0468 strscpy(obj->name, name, sizeof(obj->name));
0469 obj->id = id;
0470 obj->popularity = 0;
0471
0472 mutex_lock(&cache_lock);
0473 __cache_add(obj);
0474 mutex_unlock(&cache_lock);
0475 return 0;
0476 }
0477
0478 void cache_delete(int id)
0479 {
0480 mutex_lock(&cache_lock);
0481 __cache_delete(__cache_find(id));
0482 mutex_unlock(&cache_lock);
0483 }
0484
0485 int cache_find(int id, char *name)
0486 {
0487 struct object *obj;
0488 int ret = -ENOENT;
0489
0490 mutex_lock(&cache_lock);
0491 obj = __cache_find(id);
0492 if (obj) {
0493 ret = 0;
0494 strcpy(name, obj->name);
0495 }
0496 mutex_unlock(&cache_lock);
0497 return ret;
0498 }
0499
0500 Da notare che ci assicuriamo sempre di trattenere cache_lock quando
0501 aggiungiamo, rimuoviamo od ispezioniamo la memoria: sia la struttura
0502 della memoria che il suo contenuto sono protetti dal *lock*. Questo
0503 caso è semplice dato che copiamo i dati dall'utente e non permettiamo
0504 mai loro di accedere direttamente agli oggetti.
0505
0506 C'è una piccola ottimizzazione qui: nella funzione cache_add()
0507 impostiamo i campi dell'oggetto prima di acquisire il *lock*. Questo è
0508 sicuro perché nessun altro potrà accedervi finché non lo inseriremo
0509 nella memoria.
0510
0511 Accesso dal contesto utente
0512 ---------------------------
0513
0514 Ora consideriamo il caso in cui cache_find() può essere invocata
0515 dal contesto d'interruzione: sia hardware che software. Un esempio potrebbe
0516 essere un timer che elimina oggetti dalla memoria.
0517
0518 Qui di seguito troverete la modifica nel formato *patch*: le righe ``-``
0519 sono quelle rimosse, mentre quelle ``+`` sono quelle aggiunte.
0520
0521 ::
0522
0523 --- cache.c.usercontext 2003-12-09 13:58:54.000000000 +1100
0524 +++ cache.c.interrupt 2003-12-09 14:07:49.000000000 +1100
0525 @@ -12,7 +12,7 @@
0526 int popularity;
0527 };
0528
0529 -static DEFINE_MUTEX(cache_lock);
0530 +static DEFINE_SPINLOCK(cache_lock);
0531 static LIST_HEAD(cache);
0532 static unsigned int cache_num = 0;
0533 #define MAX_CACHE_SIZE 10
0534 @@ -55,6 +55,7 @@
0535 int cache_add(int id, const char *name)
0536 {
0537 struct object *obj;
0538 + unsigned long flags;
0539
0540 if ((obj = kmalloc(sizeof(*obj), GFP_KERNEL)) == NULL)
0541 return -ENOMEM;
0542 @@ -63,30 +64,33 @@
0543 obj->id = id;
0544 obj->popularity = 0;
0545
0546 - mutex_lock(&cache_lock);
0547 + spin_lock_irqsave(&cache_lock, flags);
0548 __cache_add(obj);
0549 - mutex_unlock(&cache_lock);
0550 + spin_unlock_irqrestore(&cache_lock, flags);
0551 return 0;
0552 }
0553
0554 void cache_delete(int id)
0555 {
0556 - mutex_lock(&cache_lock);
0557 + unsigned long flags;
0558 +
0559 + spin_lock_irqsave(&cache_lock, flags);
0560 __cache_delete(__cache_find(id));
0561 - mutex_unlock(&cache_lock);
0562 + spin_unlock_irqrestore(&cache_lock, flags);
0563 }
0564
0565 int cache_find(int id, char *name)
0566 {
0567 struct object *obj;
0568 int ret = -ENOENT;
0569 + unsigned long flags;
0570
0571 - mutex_lock(&cache_lock);
0572 + spin_lock_irqsave(&cache_lock, flags);
0573 obj = __cache_find(id);
0574 if (obj) {
0575 ret = 0;
0576 strcpy(name, obj->name);
0577 }
0578 - mutex_unlock(&cache_lock);
0579 + spin_unlock_irqrestore(&cache_lock, flags);
0580 return ret;
0581 }
0582
0583 Da notare che spin_lock_irqsave() disabiliterà le interruzioni
0584 se erano attive, altrimenti non farà niente (quando siamo già in un contesto
0585 d'interruzione); dunque queste funzioni possono essere chiamante in
0586 sicurezza da qualsiasi contesto.
0587
0588 Sfortunatamente, cache_add() invoca kmalloc() con
0589 l'opzione ``GFP_KERNEL`` che è permessa solo in contesto utente. Ho supposto
0590 che cache_add() venga chiamata dal contesto utente, altrimenti
0591 questa opzione deve diventare un parametro di cache_add().
0592
0593 Esporre gli oggetti al di fuori del file
0594 ----------------------------------------
0595
0596 Se i vostri oggetti contengono più informazioni, potrebbe non essere
0597 sufficiente copiare i dati avanti e indietro: per esempio, altre parti del
0598 codice potrebbero avere un puntatore a questi oggetti piuttosto che cercarli
0599 ogni volta. Questo introduce due problemi.
0600
0601 Il primo problema è che utilizziamo ``cache_lock`` per proteggere gli oggetti:
0602 dobbiamo renderlo dinamico così che il resto del codice possa usarlo. Questo
0603 rende la sincronizzazione più complicata dato che non avviene più in un unico
0604 posto.
0605
0606 Il secondo problema è il problema del ciclo di vita: se un'altra struttura
0607 mantiene un puntatore ad un oggetto, presumibilmente si aspetta che questo
0608 puntatore rimanga valido. Sfortunatamente, questo è garantito solo mentre
0609 si trattiene il *lock*, altrimenti qualcuno potrebbe chiamare
0610 cache_delete() o peggio, aggiungere un oggetto che riutilizza lo
0611 stesso indirizzo.
0612
0613 Dato che c'è un solo *lock*, non potete trattenerlo a vita: altrimenti
0614 nessun altro potrà eseguire il proprio lavoro.
0615
0616 La soluzione a questo problema è l'uso di un contatore di riferimenti:
0617 chiunque punti ad un oggetto deve incrementare il contatore, e decrementarlo
0618 quando il puntatore non viene più usato. Quando il contatore raggiunge lo zero
0619 significa che non è più usato e l'oggetto può essere rimosso.
0620
0621 Ecco il codice::
0622
0623 --- cache.c.interrupt 2003-12-09 14:25:43.000000000 +1100
0624 +++ cache.c.refcnt 2003-12-09 14:33:05.000000000 +1100
0625 @@ -7,6 +7,7 @@
0626 struct object
0627 {
0628 struct list_head list;
0629 + unsigned int refcnt;
0630 int id;
0631 char name[32];
0632 int popularity;
0633 @@ -17,6 +18,35 @@
0634 static unsigned int cache_num = 0;
0635 #define MAX_CACHE_SIZE 10
0636
0637 +static void __object_put(struct object *obj)
0638 +{
0639 + if (--obj->refcnt == 0)
0640 + kfree(obj);
0641 +}
0642 +
0643 +static void __object_get(struct object *obj)
0644 +{
0645 + obj->refcnt++;
0646 +}
0647 +
0648 +void object_put(struct object *obj)
0649 +{
0650 + unsigned long flags;
0651 +
0652 + spin_lock_irqsave(&cache_lock, flags);
0653 + __object_put(obj);
0654 + spin_unlock_irqrestore(&cache_lock, flags);
0655 +}
0656 +
0657 +void object_get(struct object *obj)
0658 +{
0659 + unsigned long flags;
0660 +
0661 + spin_lock_irqsave(&cache_lock, flags);
0662 + __object_get(obj);
0663 + spin_unlock_irqrestore(&cache_lock, flags);
0664 +}
0665 +
0666 /* Must be holding cache_lock */
0667 static struct object *__cache_find(int id)
0668 {
0669 @@ -35,6 +65,7 @@
0670 {
0671 BUG_ON(!obj);
0672 list_del(&obj->list);
0673 + __object_put(obj);
0674 cache_num--;
0675 }
0676
0677 @@ -63,6 +94,7 @@
0678 strscpy(obj->name, name, sizeof(obj->name));
0679 obj->id = id;
0680 obj->popularity = 0;
0681 + obj->refcnt = 1; /* The cache holds a reference */
0682
0683 spin_lock_irqsave(&cache_lock, flags);
0684 __cache_add(obj);
0685 @@ -79,18 +111,15 @@
0686 spin_unlock_irqrestore(&cache_lock, flags);
0687 }
0688
0689 -int cache_find(int id, char *name)
0690 +struct object *cache_find(int id)
0691 {
0692 struct object *obj;
0693 - int ret = -ENOENT;
0694 unsigned long flags;
0695
0696 spin_lock_irqsave(&cache_lock, flags);
0697 obj = __cache_find(id);
0698 - if (obj) {
0699 - ret = 0;
0700 - strcpy(name, obj->name);
0701 - }
0702 + if (obj)
0703 + __object_get(obj);
0704 spin_unlock_irqrestore(&cache_lock, flags);
0705 - return ret;
0706 + return obj;
0707 }
0708
0709 Abbiamo incapsulato il contatore di riferimenti nelle tipiche funzioni
0710 di 'get' e 'put'. Ora possiamo ritornare l'oggetto da cache_find()
0711 col vantaggio che l'utente può dormire trattenendo l'oggetto (per esempio,
0712 copy_to_user() per copiare il nome verso lo spazio utente).
0713
0714 Un altro punto da notare è che ho detto che il contatore dovrebbe incrementarsi
0715 per ogni puntatore ad un oggetto: quindi il contatore di riferimenti è 1
0716 quando l'oggetto viene inserito nella memoria. In altre versione il framework
0717 non trattiene un riferimento per se, ma diventa più complicato.
0718
0719 Usare operazioni atomiche per il contatore di riferimenti
0720 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
0721
0722 In sostanza, :c:type:`atomic_t` viene usato come contatore di riferimenti.
0723 Ci sono un certo numbero di operazioni atomiche definite
0724 in ``include/asm/atomic.h``: queste sono garantite come atomiche su qualsiasi
0725 processore del sistema, quindi non sono necessari i *lock*. In questo caso è
0726 più semplice rispetto all'uso degli spinlock, benché l'uso degli spinlock
0727 sia più elegante per casi non banali. Le funzioni atomic_inc() e
0728 atomic_dec_and_test() vengono usate al posto dei tipici operatori di
0729 incremento e decremento, e i *lock* non sono più necessari per proteggere il
0730 contatore stesso.
0731
0732 ::
0733
0734 --- cache.c.refcnt 2003-12-09 15:00:35.000000000 +1100
0735 +++ cache.c.refcnt-atomic 2003-12-11 15:49:42.000000000 +1100
0736 @@ -7,7 +7,7 @@
0737 struct object
0738 {
0739 struct list_head list;
0740 - unsigned int refcnt;
0741 + atomic_t refcnt;
0742 int id;
0743 char name[32];
0744 int popularity;
0745 @@ -18,33 +18,15 @@
0746 static unsigned int cache_num = 0;
0747 #define MAX_CACHE_SIZE 10
0748
0749 -static void __object_put(struct object *obj)
0750 -{
0751 - if (--obj->refcnt == 0)
0752 - kfree(obj);
0753 -}
0754 -
0755 -static void __object_get(struct object *obj)
0756 -{
0757 - obj->refcnt++;
0758 -}
0759 -
0760 void object_put(struct object *obj)
0761 {
0762 - unsigned long flags;
0763 -
0764 - spin_lock_irqsave(&cache_lock, flags);
0765 - __object_put(obj);
0766 - spin_unlock_irqrestore(&cache_lock, flags);
0767 + if (atomic_dec_and_test(&obj->refcnt))
0768 + kfree(obj);
0769 }
0770
0771 void object_get(struct object *obj)
0772 {
0773 - unsigned long flags;
0774 -
0775 - spin_lock_irqsave(&cache_lock, flags);
0776 - __object_get(obj);
0777 - spin_unlock_irqrestore(&cache_lock, flags);
0778 + atomic_inc(&obj->refcnt);
0779 }
0780
0781 /* Must be holding cache_lock */
0782 @@ -65,7 +47,7 @@
0783 {
0784 BUG_ON(!obj);
0785 list_del(&obj->list);
0786 - __object_put(obj);
0787 + object_put(obj);
0788 cache_num--;
0789 }
0790
0791 @@ -94,7 +76,7 @@
0792 strscpy(obj->name, name, sizeof(obj->name));
0793 obj->id = id;
0794 obj->popularity = 0;
0795 - obj->refcnt = 1; /* The cache holds a reference */
0796 + atomic_set(&obj->refcnt, 1); /* The cache holds a reference */
0797
0798 spin_lock_irqsave(&cache_lock, flags);
0799 __cache_add(obj);
0800 @@ -119,7 +101,7 @@
0801 spin_lock_irqsave(&cache_lock, flags);
0802 obj = __cache_find(id);
0803 if (obj)
0804 - __object_get(obj);
0805 + object_get(obj);
0806 spin_unlock_irqrestore(&cache_lock, flags);
0807 return obj;
0808 }
0809
0810 Proteggere l'oggetto stesso
0811 ---------------------------
0812
0813 In questo esempio, assumiamo che gli oggetti (ad eccezione del contatore
0814 di riferimenti) non cambino mai dopo la loro creazione. Se vogliamo permettere
0815 al nome di cambiare abbiamo tre possibilità:
0816
0817 - Si può togliere static da ``cache_lock`` e dire agli utenti che devono
0818 trattenere il *lock* prima di modificare il nome di un oggetto.
0819
0820 - Si può fornire una funzione cache_obj_rename() che prende il
0821 *lock* e cambia il nome per conto del chiamante; si dirà poi agli utenti
0822 di usare questa funzione.
0823
0824 - Si può decidere che ``cache_lock`` protegge solo la memoria stessa, ed
0825 un altro *lock* è necessario per la protezione del nome.
0826
0827 Teoricamente, possiamo avere un *lock* per ogni campo e per ogni oggetto.
0828 In pratica, le varianti più comuni sono:
0829
0830 - un *lock* che protegge l'infrastruttura (la lista ``cache`` di questo
0831 esempio) e gli oggetti. Questo è quello che abbiamo fatto finora.
0832
0833 - un *lock* che protegge l'infrastruttura (inclusi i puntatori alla lista
0834 negli oggetti), e un *lock* nell'oggetto per proteggere il resto
0835 dell'oggetto stesso.
0836
0837 - *lock* multipli per proteggere l'infrastruttura (per esempio un *lock*
0838 per ogni lista), possibilmente con un *lock* per oggetto.
0839
0840 Qui di seguito un'implementazione con "un lock per oggetto":
0841
0842 ::
0843
0844 --- cache.c.refcnt-atomic 2003-12-11 15:50:54.000000000 +1100
0845 +++ cache.c.perobjectlock 2003-12-11 17:15:03.000000000 +1100
0846 @@ -6,11 +6,17 @@
0847
0848 struct object
0849 {
0850 + /* These two protected by cache_lock. */
0851 struct list_head list;
0852 + int popularity;
0853 +
0854 atomic_t refcnt;
0855 +
0856 + /* Doesn't change once created. */
0857 int id;
0858 +
0859 + spinlock_t lock; /* Protects the name */
0860 char name[32];
0861 - int popularity;
0862 };
0863
0864 static DEFINE_SPINLOCK(cache_lock);
0865 @@ -77,6 +84,7 @@
0866 obj->id = id;
0867 obj->popularity = 0;
0868 atomic_set(&obj->refcnt, 1); /* The cache holds a reference */
0869 + spin_lock_init(&obj->lock);
0870
0871 spin_lock_irqsave(&cache_lock, flags);
0872 __cache_add(obj);
0873
0874 Da notare che ho deciso che il contatore di popolarità dovesse essere
0875 protetto da ``cache_lock`` piuttosto che dal *lock* dell'oggetto; questo
0876 perché è logicamente parte dell'infrastruttura (come
0877 :c:type:`struct list_head <list_head>` nell'oggetto). In questo modo,
0878 in __cache_add(), non ho bisogno di trattenere il *lock* di ogni
0879 oggetto mentre si cerca il meno popolare.
0880
0881 Ho anche deciso che il campo id è immutabile, quindi non ho bisogno di
0882 trattenere il lock dell'oggetto quando si usa __cache_find()
0883 per leggere questo campo; il *lock* dell'oggetto è usato solo dal chiamante
0884 che vuole leggere o scrivere il campo name.
0885
0886 Inoltre, da notare che ho aggiunto un commento che descrive i dati che sono
0887 protetti dal *lock*. Questo è estremamente importante in quanto descrive il
0888 comportamento del codice, che altrimenti sarebbe di difficile comprensione
0889 leggendo solamente il codice. E come dice Alan Cox: “Lock data, not code”.
0890
0891 Problemi comuni
0892 ===============
0893
0894 Stallo: semplice ed avanzato
0895 ----------------------------
0896
0897 Esiste un tipo di baco dove un pezzo di codice tenta di trattenere uno
0898 spinlock due volte: questo rimarrà in attesa attiva per sempre aspettando che
0899 il *lock* venga rilasciato (in Linux spinlocks, rwlocks e mutex non sono
0900 ricorsivi).
0901 Questo è facile da diagnosticare: non è uno di quei problemi che ti tengono
0902 sveglio 5 notti a parlare da solo.
0903
0904 Un caso un pochino più complesso; immaginate d'avere una spazio condiviso
0905 fra un softirq ed il contesto utente. Se usate spin_lock() per
0906 proteggerlo, il contesto utente potrebbe essere interrotto da un softirq
0907 mentre trattiene il lock, da qui il softirq rimarrà in attesa attiva provando
0908 ad acquisire il *lock* già trattenuto nel contesto utente.
0909
0910 Questi casi sono chiamati stalli (*deadlock*), e come mostrato qui sopra,
0911 può succedere anche con un solo processore (Ma non sui sistemi
0912 monoprocessore perché gli spinlock spariscano quando il kernel è compilato
0913 con ``CONFIG_SMP``\ =n. Nonostante ciò, nel secondo caso avrete comunque
0914 una corruzione dei dati).
0915
0916 Questi casi sono facili da diagnosticare; sui sistemi multi-processore
0917 il supervisione (*watchdog*) o l'opzione di compilazione ``DEBUG_SPINLOCK``
0918 (``include/linux/spinlock.h``) permettono di scovare immediatamente quando
0919 succedono.
0920
0921 Esiste un caso più complesso che è conosciuto come l'abbraccio della morte;
0922 questo coinvolge due o più *lock*. Diciamo che avete un vettore di hash in cui
0923 ogni elemento è uno spinlock a cui è associata una lista di elementi con lo
0924 stesso hash. In un gestore di interruzioni software, dovete modificare un
0925 oggetto e spostarlo su un altro hash; quindi dovrete trattenete lo spinlock
0926 del vecchio hash e di quello nuovo, quindi rimuovere l'oggetto dal vecchio ed
0927 inserirlo nel nuovo.
0928
0929 Qui abbiamo due problemi. Primo, se il vostro codice prova a spostare un
0930 oggetto all'interno della stessa lista, otterrete uno stallo visto che
0931 tenterà di trattenere lo stesso *lock* due volte. Secondo, se la stessa
0932 interruzione software su un altro processore sta tentando di spostare
0933 un altro oggetto nella direzione opposta, potrebbe accadere quanto segue:
0934
0935 +---------------------------------+---------------------------------+
0936 | CPU 1 | CPU 2 |
0937 +=================================+=================================+
0938 | Trattiene *lock* A -> OK | Trattiene *lock* B -> OK |
0939 +---------------------------------+---------------------------------+
0940 | Trattiene *lock* B -> attesa | Trattiene *lock* A -> attesa |
0941 +---------------------------------+---------------------------------+
0942
0943 Table: Conseguenze
0944
0945 Entrambe i processori rimarranno in attesa attiva sul *lock* per sempre,
0946 aspettando che l'altro lo rilasci. Sembra e puzza come un blocco totale.
0947
0948 Prevenire gli stalli
0949 --------------------
0950
0951 I libri di testo vi diranno che se trattenete i *lock* sempre nello stesso
0952 ordine non avrete mai un simile stallo. La pratica vi dirà che questo
0953 approccio non funziona all'ingrandirsi del sistema: quando creo un nuovo
0954 *lock* non ne capisco abbastanza del kernel per dire in quale dei 5000 *lock*
0955 si incastrerà.
0956
0957 I *lock* migliori sono quelli incapsulati: non vengono esposti nei file di
0958 intestazione, e non vengono mai trattenuti fuori dallo stesso file. Potete
0959 rileggere questo codice e vedere che non ci sarà mai uno stallo perché
0960 non tenterà mai di trattenere un altro *lock* quando lo ha già.
0961 Le persone che usano il vostro codice non devono nemmeno sapere che voi
0962 state usando dei *lock*.
0963
0964 Un classico problema deriva dall'uso di *callback* e di *hook*: se li
0965 chiamate mentre trattenete un *lock*, rischiate uno stallo o un abbraccio
0966 della morte (chi lo sa cosa farà una *callback*?).
0967
0968 Ossessiva prevenzione degli stalli
0969 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
0970
0971 Gli stalli sono un problema, ma non così terribile come la corruzione dei dati.
0972 Un pezzo di codice trattiene un *lock* di lettura, cerca in una lista,
0973 fallisce nel trovare quello che vuole, quindi rilascia il *lock* di lettura,
0974 trattiene un *lock* di scrittura ed inserisce un oggetto; questo genere di
0975 codice presenta una corsa critica.
0976
0977 corsa fra temporizzatori: un passatempo del kernel
0978 --------------------------------------------------
0979
0980 I temporizzatori potrebbero avere dei problemi con le corse critiche.
0981 Considerate una collezione di oggetti (liste, hash, eccetera) dove ogni oggetto
0982 ha un temporizzatore che sta per distruggerlo.
0983
0984 Se volete eliminare l'intera collezione (diciamo quando rimuovete un modulo),
0985 potreste fare come segue::
0986
0987 /* THIS CODE BAD BAD BAD BAD: IF IT WAS ANY WORSE IT WOULD USE
0988 HUNGARIAN NOTATION */
0989 spin_lock_bh(&list_lock);
0990
0991 while (list) {
0992 struct foo *next = list->next;
0993 del_timer(&list->timer);
0994 kfree(list);
0995 list = next;
0996 }
0997
0998 spin_unlock_bh(&list_lock);
0999
1000 Primo o poi, questo esploderà su un sistema multiprocessore perché un
1001 temporizzatore potrebbe essere già partiro prima di spin_lock_bh(),
1002 e prenderà il *lock* solo dopo spin_unlock_bh(), e cercherà
1003 di eliminare il suo oggetto (che però è già stato eliminato).
1004
1005 Questo può essere evitato controllando il valore di ritorno di
1006 del_timer(): se ritorna 1, il temporizzatore è stato già
1007 rimosso. Se 0, significa (in questo caso) che il temporizzatore è in
1008 esecuzione, quindi possiamo fare come segue::
1009
1010 retry:
1011 spin_lock_bh(&list_lock);
1012
1013 while (list) {
1014 struct foo *next = list->next;
1015 if (!del_timer(&list->timer)) {
1016 /* Give timer a chance to delete this */
1017 spin_unlock_bh(&list_lock);
1018 goto retry;
1019 }
1020 kfree(list);
1021 list = next;
1022 }
1023
1024 spin_unlock_bh(&list_lock);
1025
1026 Un altro problema è l'eliminazione dei temporizzatori che si riavviano
1027 da soli (chiamando add_timer() alla fine della loro esecuzione).
1028 Dato che questo è un problema abbastanza comune con una propensione
1029 alle corse critiche, dovreste usare del_timer_sync()
1030 (``include/linux/timer.h``) per gestire questo caso. Questa ritorna il
1031 numero di volte che il temporizzatore è stato interrotto prima che
1032 fosse in grado di fermarlo senza che si riavviasse.
1033
1034 Velocità della sincronizzazione
1035 ===============================
1036
1037 Ci sono tre cose importanti da tenere in considerazione quando si valuta
1038 la velocità d'esecuzione di un pezzo di codice che necessita di
1039 sincronizzazione. La prima è la concorrenza: quante cose rimangono in attesa
1040 mentre qualcuno trattiene un *lock*. La seconda è il tempo necessario per
1041 acquisire (senza contese) e rilasciare un *lock*. La terza è di usare meno
1042 *lock* o di più furbi. Immagino che i *lock* vengano usati regolarmente,
1043 altrimenti, non sareste interessati all'efficienza.
1044
1045 La concorrenza dipende da quanto a lungo un *lock* è trattenuto: dovreste
1046 trattenere un *lock* solo il tempo minimo necessario ma non un istante in più.
1047 Nella memoria dell'esempio precedente, creiamo gli oggetti senza trattenere
1048 il *lock*, poi acquisiamo il *lock* quando siamo pronti per inserirlo nella
1049 lista.
1050
1051 Il tempo di acquisizione di un *lock* dipende da quanto danno fa
1052 l'operazione sulla *pipeline* (ovvero stalli della *pipeline*) e quant'è
1053 probabile che il processore corrente sia stato anche l'ultimo ad acquisire
1054 il *lock* (in pratica, il *lock* è nella memoria cache del processore
1055 corrente?): su sistemi multi-processore questa probabilità precipita
1056 rapidamente. Consideriamo un processore Intel Pentium III a 700Mhz: questo
1057 esegue un'istruzione in 0.7ns, un incremento atomico richiede 58ns, acquisire
1058 un *lock* che è nella memoria cache del processore richiede 160ns, e un
1059 trasferimento dalla memoria cache di un altro processore richiede altri
1060 170/360ns (Leggetevi l'articolo di Paul McKenney's `Linux Journal RCU
1061 article <http://www.linuxjournal.com/article.php?sid=6993>`__).
1062
1063 Questi due obiettivi sono in conflitto: trattenere un *lock* per il minor
1064 tempo possibile potrebbe richiedere la divisione in più *lock* per diverse
1065 parti (come nel nostro ultimo esempio con un *lock* per ogni oggetto),
1066 ma questo aumenta il numero di acquisizioni di *lock*, ed il risultato
1067 spesso è che tutto è più lento che con un singolo *lock*. Questo è un altro
1068 argomento in favore della semplicità quando si parla di sincronizzazione.
1069
1070 Il terzo punto è discusso di seguito: ci sono alcune tecniche per ridurre
1071 il numero di sincronizzazioni che devono essere fatte.
1072
1073 Read/Write Lock Variants
1074 ------------------------
1075
1076 Sia gli spinlock che i mutex hanno una variante per la lettura/scrittura
1077 (read/write): ``rwlock_t`` e :c:type:`struct rw_semaphore <rw_semaphore>`.
1078 Queste dividono gli utenti in due categorie: i lettori e gli scrittori.
1079 Se state solo leggendo i dati, potete acquisire il *lock* di lettura, ma
1080 per scrivere avrete bisogno del *lock* di scrittura. Molti possono trattenere
1081 il *lock* di lettura, ma solo uno scrittore alla volta può trattenere
1082 quello di scrittura.
1083
1084 Se il vostro codice si divide chiaramente in codice per lettori e codice
1085 per scrittori (come nel nostro esempio), e il *lock* dei lettori viene
1086 trattenuto per molto tempo, allora l'uso di questo tipo di *lock* può aiutare.
1087 Questi sono leggermente più lenti rispetto alla loro versione normale, quindi
1088 nella pratica l'uso di ``rwlock_t`` non ne vale la pena.
1089
1090 Evitare i *lock*: Read Copy Update
1091 --------------------------------------------
1092
1093 Esiste un metodo di sincronizzazione per letture e scritture detto
1094 Read Copy Update. Con l'uso della tecnica RCU, i lettori possono scordarsi
1095 completamente di trattenere i *lock*; dato che nel nostro esempio ci
1096 aspettiamo d'avere più lettore che scrittori (altrimenti questa memoria
1097 sarebbe uno spreco) possiamo dire che questo meccanismo permette
1098 un'ottimizzazione.
1099
1100 Come facciamo a sbarazzarci dei *lock* di lettura? Sbarazzarsi dei *lock* di
1101 lettura significa che uno scrittore potrebbe cambiare la lista sotto al naso
1102 dei lettori. Questo è abbastanza semplice: possiamo leggere una lista
1103 concatenata se lo scrittore aggiunge elementi alla fine e con certe
1104 precauzioni. Per esempio, aggiungendo ``new`` ad una lista concatenata
1105 chiamata ``list``::
1106
1107 new->next = list->next;
1108 wmb();
1109 list->next = new;
1110
1111 La funzione wmb() è una barriera di sincronizzazione delle
1112 scritture. Questa garantisce che la prima operazione (impostare l'elemento
1113 ``next`` del nuovo elemento) venga completata e vista da tutti i processori
1114 prima che venga eseguita la seconda operazione (che sarebbe quella di mettere
1115 il nuovo elemento nella lista). Questo è importante perché i moderni
1116 compilatori ed i moderni processori possono, entrambe, riordinare le istruzioni
1117 se non vengono istruiti altrimenti: vogliamo che i lettori non vedano
1118 completamente il nuovo elemento; oppure che lo vedano correttamente e quindi
1119 il puntatore ``next`` deve puntare al resto della lista.
1120
1121 Fortunatamente, c'è una funzione che fa questa operazione sulle liste
1122 :c:type:`struct list_head <list_head>`: list_add_rcu()
1123 (``include/linux/list.h``).
1124
1125 Rimuovere un elemento dalla lista è anche più facile: sostituiamo il puntatore
1126 al vecchio elemento con quello del suo successore, e i lettori vedranno
1127 l'elemento o lo salteranno.
1128
1129 ::
1130
1131 list->next = old->next;
1132
1133 La funzione list_del_rcu() (``include/linux/list.h``) fa esattamente
1134 questo (la versione normale corrompe il vecchio oggetto, e non vogliamo che
1135 accada).
1136
1137 Anche i lettori devono stare attenti: alcuni processori potrebbero leggere
1138 attraverso il puntatore ``next`` il contenuto dell'elemento successivo
1139 troppo presto, ma non accorgersi che il contenuto caricato è sbagliato quando
1140 il puntatore ``next`` viene modificato alla loro spalle. Ancora una volta
1141 c'è una funzione che viene in vostro aiuto list_for_each_entry_rcu()
1142 (``include/linux/list.h``). Ovviamente, gli scrittori possono usare
1143 list_for_each_entry() dato che non ci possono essere due scrittori
1144 in contemporanea.
1145
1146 Il nostro ultimo dilemma è il seguente: quando possiamo realmente distruggere
1147 l'elemento rimosso? Ricordate, un lettore potrebbe aver avuto accesso a questo
1148 elemento proprio ora: se eliminiamo questo elemento ed il puntatore ``next``
1149 cambia, il lettore salterà direttamente nella spazzatura e scoppierà. Dobbiamo
1150 aspettare finché tutti i lettori che stanno attraversando la lista abbiano
1151 finito. Utilizziamo call_rcu() per registrare una funzione di
1152 richiamo che distrugga l'oggetto quando tutti i lettori correnti hanno
1153 terminato. In alternative, potrebbe essere usata la funzione
1154 synchronize_rcu() che blocca l'esecuzione finché tutti i lettori
1155 non terminano di ispezionare la lista.
1156
1157 Ma come fa l'RCU a sapere quando i lettori sono finiti? Il meccanismo è
1158 il seguente: innanzi tutto i lettori accedono alla lista solo fra la coppia
1159 rcu_read_lock()/rcu_read_unlock() che disabilita la
1160 prelazione così che i lettori non vengano sospesi mentre stanno leggendo
1161 la lista.
1162
1163 Poi, l'RCU aspetta finché tutti i processori non abbiano dormito almeno
1164 una volta; a questo punto, dato che i lettori non possono dormire, possiamo
1165 dedurre che un qualsiasi lettore che abbia consultato la lista durante la
1166 rimozione abbia già terminato, quindi la *callback* viene eseguita. Il vero
1167 codice RCU è un po' più ottimizzato di così, ma questa è l'idea di fondo.
1168
1169 ::
1170
1171 --- cache.c.perobjectlock 2003-12-11 17:15:03.000000000 +1100
1172 +++ cache.c.rcupdate 2003-12-11 17:55:14.000000000 +1100
1173 @@ -1,15 +1,18 @@
1174 #include <linux/list.h>
1175 #include <linux/slab.h>
1176 #include <linux/string.h>
1177 +#include <linux/rcupdate.h>
1178 #include <linux/mutex.h>
1179 #include <asm/errno.h>
1180
1181 struct object
1182 {
1183 - /* These two protected by cache_lock. */
1184 + /* This is protected by RCU */
1185 struct list_head list;
1186 int popularity;
1187
1188 + struct rcu_head rcu;
1189 +
1190 atomic_t refcnt;
1191
1192 /* Doesn't change once created. */
1193 @@ -40,7 +43,7 @@
1194 {
1195 struct object *i;
1196
1197 - list_for_each_entry(i, &cache, list) {
1198 + list_for_each_entry_rcu(i, &cache, list) {
1199 if (i->id == id) {
1200 i->popularity++;
1201 return i;
1202 @@ -49,19 +52,25 @@
1203 return NULL;
1204 }
1205
1206 +/* Final discard done once we know no readers are looking. */
1207 +static void cache_delete_rcu(void *arg)
1208 +{
1209 + object_put(arg);
1210 +}
1211 +
1212 /* Must be holding cache_lock */
1213 static void __cache_delete(struct object *obj)
1214 {
1215 BUG_ON(!obj);
1216 - list_del(&obj->list);
1217 - object_put(obj);
1218 + list_del_rcu(&obj->list);
1219 cache_num--;
1220 + call_rcu(&obj->rcu, cache_delete_rcu);
1221 }
1222
1223 /* Must be holding cache_lock */
1224 static void __cache_add(struct object *obj)
1225 {
1226 - list_add(&obj->list, &cache);
1227 + list_add_rcu(&obj->list, &cache);
1228 if (++cache_num > MAX_CACHE_SIZE) {
1229 struct object *i, *outcast = NULL;
1230 list_for_each_entry(i, &cache, list) {
1231 @@ -104,12 +114,11 @@
1232 struct object *cache_find(int id)
1233 {
1234 struct object *obj;
1235 - unsigned long flags;
1236
1237 - spin_lock_irqsave(&cache_lock, flags);
1238 + rcu_read_lock();
1239 obj = __cache_find(id);
1240 if (obj)
1241 object_get(obj);
1242 - spin_unlock_irqrestore(&cache_lock, flags);
1243 + rcu_read_unlock();
1244 return obj;
1245 }
1246
1247 Da notare che i lettori modificano il campo popularity nella funzione
1248 __cache_find(), e ora non trattiene alcun *lock*. Una soluzione
1249 potrebbe essere quella di rendere la variabile ``atomic_t``, ma per l'uso
1250 che ne abbiamo fatto qui, non ci interessano queste corse critiche perché un
1251 risultato approssimativo è comunque accettabile, quindi non l'ho cambiato.
1252
1253 Il risultato è che la funzione cache_find() non ha bisogno di alcuna
1254 sincronizzazione con le altre funzioni, quindi è veloce su un sistema
1255 multi-processore tanto quanto lo sarebbe su un sistema mono-processore.
1256
1257 Esiste un'ulteriore ottimizzazione possibile: vi ricordate il codice originale
1258 della nostra memoria dove non c'erano contatori di riferimenti e il chiamante
1259 semplicemente tratteneva il *lock* prima di accedere ad un oggetto? Questo è
1260 ancora possibile: se trattenete un *lock* nessuno potrà cancellare l'oggetto,
1261 quindi non avete bisogno di incrementare e decrementare il contatore di
1262 riferimenti.
1263
1264 Ora, dato che il '*lock* di lettura' di un RCU non fa altro che disabilitare
1265 la prelazione, un chiamante che ha sempre la prelazione disabilitata fra le
1266 chiamate cache_find() e object_put() non necessita
1267 di incrementare e decrementare il contatore di riferimenti. Potremmo
1268 esporre la funzione __cache_find() dichiarandola non-static,
1269 e quel chiamante potrebbe usare direttamente questa funzione.
1270
1271 Il beneficio qui sta nel fatto che il contatore di riferimenti no
1272 viene scritto: l'oggetto non viene alterato in alcun modo e quindi diventa
1273 molto più veloce su sistemi molti-processore grazie alla loro memoria cache.
1274
1275
1276 Dati per processore
1277 -------------------
1278
1279 Un'altra tecnica comunemente usata per evitare la sincronizzazione è quella
1280 di duplicare le informazioni per ogni processore. Per esempio, se volete
1281 avere un contatore di qualcosa, potreste utilizzare uno spinlock ed un
1282 singolo contatore. Facile e pulito.
1283
1284 Se questo dovesse essere troppo lento (solitamente non lo è, ma se avete
1285 dimostrato che lo è devvero), potreste usare un contatore per ogni processore
1286 e quindi non sarebbe più necessaria la mutua esclusione. Vedere
1287 DEFINE_PER_CPU(), get_cpu_var() e put_cpu_var()
1288 (``include/linux/percpu.h``).
1289
1290 Il tipo di dato ``local_t``, la funzione cpu_local_inc() e tutte
1291 le altre funzioni associate, sono di particolare utilità per semplici contatori
1292 per-processore; su alcune architetture sono anche più efficienti
1293 (``include/asm/local.h``).
1294
1295 Da notare che non esiste un modo facile ed affidabile per ottenere il valore
1296 di un simile contatore senza introdurre altri *lock*. In alcuni casi questo
1297 non è un problema.
1298
1299 Dati che sono usati prevalentemente dai gestori d'interruzioni
1300 --------------------------------------------------------------
1301
1302 Se i dati vengono utilizzati sempre dallo stesso gestore d'interruzioni,
1303 allora i *lock* non vi servono per niente: il kernel già vi garantisce che
1304 il gestore d'interruzione non verrà eseguito in contemporanea su diversi
1305 processori.
1306
1307 Manfred Spraul fa notare che potreste comunque comportarvi così anche
1308 se i dati vengono occasionalmente utilizzati da un contesto utente o
1309 da un'interruzione software. Il gestore d'interruzione non utilizza alcun
1310 *lock*, e tutti gli altri accessi verranno fatti così::
1311
1312 spin_lock(&lock);
1313 disable_irq(irq);
1314 ...
1315 enable_irq(irq);
1316 spin_unlock(&lock);
1317
1318 La funzione disable_irq() impedisce al gestore d'interruzioni
1319 d'essere eseguito (e aspetta che finisca nel caso fosse in esecuzione su
1320 un altro processore). Lo spinlock, invece, previene accessi simultanei.
1321 Naturalmente, questo è più lento della semplice chiamata
1322 spin_lock_irq(), quindi ha senso solo se questo genere di accesso
1323 è estremamente raro.
1324
1325
1326 Quali funzioni possono essere chiamate in modo sicuro dalle interruzioni?
1327 =========================================================================
1328
1329 Molte funzioni del kernel dormono (in sostanza, chiamano schedule())
1330 direttamente od indirettamente: non potete chiamarle se trattenere uno
1331 spinlock o avete la prelazione disabilitata, mai. Questo significa che
1332 dovete necessariamente essere nel contesto utente: chiamarle da un
1333 contesto d'interruzione è illegale.
1334
1335 Alcune funzioni che dormono
1336 ---------------------------
1337
1338 Le più comuni sono elencate qui di seguito, ma solitamente dovete leggere
1339 il codice per scoprire se altre chiamate sono sicure. Se chiunque altro
1340 le chiami dorme, allora dovreste poter dormire anche voi. In particolar
1341 modo, le funzioni di registrazione e deregistrazione solitamente si
1342 aspettano d'essere chiamante da un contesto utente e quindi che possono
1343 dormire.
1344
1345 - Accessi allo spazio utente:
1346
1347 - copy_from_user()
1348
1349 - copy_to_user()
1350
1351 - get_user()
1352
1353 - put_user()
1354
1355 - kmalloc(GFP_KERNEL) <kmalloc>`
1356
1357 - mutex_lock_interruptible() and
1358 mutex_lock()
1359
1360 C'è anche mutex_trylock() che però non dorme.
1361 Comunque, non deve essere usata in un contesto d'interruzione dato
1362 che la sua implementazione non è sicura in quel contesto.
1363 Anche mutex_unlock() non dorme mai. Non può comunque essere
1364 usata in un contesto d'interruzione perché un mutex deve essere rilasciato
1365 dallo stesso processo che l'ha acquisito.
1366
1367 Alcune funzioni che non dormono
1368 -------------------------------
1369
1370 Alcune funzioni possono essere chiamate tranquillamente da qualsiasi
1371 contesto, o trattenendo un qualsiasi *lock*.
1372
1373 - printk()
1374
1375 - kfree()
1376
1377 - add_timer() e del_timer()
1378
1379 Riferimento per l'API dei Mutex
1380 ===============================
1381
1382 .. kernel-doc:: include/linux/mutex.h
1383 :internal:
1384
1385 .. kernel-doc:: kernel/locking/mutex.c
1386 :export:
1387
1388 Riferimento per l'API dei Futex
1389 ===============================
1390
1391 .. kernel-doc:: kernel/futex/core.c
1392 :internal:
1393
1394 .. kernel-doc:: kernel/futex/futex.h
1395 :internal:
1396
1397 .. kernel-doc:: kernel/futex/pi.c
1398 :internal:
1399
1400 .. kernel-doc:: kernel/futex/requeue.c
1401 :internal:
1402
1403 .. kernel-doc:: kernel/futex/waitwake.c
1404 :internal:
1405
1406 Approfondimenti
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
1421 Ringraziamenti
1422 ==============
1423
1424 Grazie a Telsa Gwynne per aver formattato questa guida in DocBook, averla
1425 pulita e aggiunto un po' di stile.
1426
1427 Grazie a Martin Pool, Philipp Rumpf, Stephen Rothwell, Paul Mackerras,
1428 Ruedi Aschwanden, Alan Cox, Manfred Spraul, Tim Waugh, Pete Zaitcev,
1429 James Morris, Robert Love, Paul McKenney, John Ashby per aver revisionato,
1430 corretto, maledetto e commentato.
1431
1432 Grazie alla congrega per non aver avuto alcuna influenza su questo documento.
1433
1434 Glossario
1435 =========
1436
1437 prelazione
1438 Prima del kernel 2.5, o quando ``CONFIG_PREEMPT`` non è impostato, i processi
1439 in contesto utente non si avvicendano nell'esecuzione (in pratica, il
1440 processo userà il processore fino al proprio termine, a meno che non ci siano
1441 delle interruzioni). Con l'aggiunta di ``CONFIG_PREEMPT`` nella versione
1442 2.5.4 questo è cambiato: quando si è in contesto utente, processi con una
1443 priorità maggiore possono subentrare nell'esecuzione: gli spinlock furono
1444 cambiati per disabilitare la prelazioni, anche su sistemi monoprocessore.
1445
1446 bh
1447 Bottom Half: per ragioni storiche, le funzioni che contengono '_bh' nel
1448 loro nome ora si riferiscono a qualsiasi interruzione software; per esempio,
1449 spin_lock_bh() blocca qualsiasi interuzione software sul processore
1450 corrente. I *Bottom Halves* sono deprecati, e probabilmente verranno
1451 sostituiti dai tasklet. In un dato momento potrà esserci solo un
1452 *bottom half* in esecuzione.
1453
1454 contesto d'interruzione
1455 Non è il contesto utente: qui si processano le interruzioni hardware e
1456 software. La macro in_interrupt() ritorna vero.
1457
1458 contesto utente
1459 Il kernel che esegue qualcosa per conto di un particolare processo (per
1460 esempio una chiamata di sistema) o di un thread del kernel. Potete
1461 identificare il processo con la macro ``current``. Da non confondere
1462 con lo spazio utente. Può essere interrotto sia da interruzioni software
1463 che hardware.
1464
1465 interruzione hardware
1466 Richiesta di interruzione hardware. in_hardirq() ritorna vero in un
1467 gestore d'interruzioni hardware.
1468
1469 interruzione software / softirq
1470 Gestore di interruzioni software: in_hardirq() 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
1478 monoprocessore / UP
1479 (Uni-Processor) un solo processore, ovvero non è SMP. (``CONFIG_SMP=n``).
1480
1481 multi-processore / SMP
1482 (Symmetric Multi-Processor) kernel compilati per sistemi multi-processore
1483 (``CONFIG_SMP=y``).
1484
1485 spazio utente
1486 Un processo che esegue il proprio codice fuori dal kernel.
1487
1488 tasklet
1489 Un'interruzione software registrabile dinamicamente che ha la garanzia
1490 d'essere eseguita solo su un processore alla volta.
1491
1492 timer
1493 Un'interruzione software registrabile dinamicamente che viene eseguita
1494 (circa) in un determinato momento. Quando è in esecuzione è come un tasklet
1495 (infatti, sono chiamati da ``TIMER_SOFTIRQ``).
