locking.rst

   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``).