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