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