Um Ressourcenkonflikte parallel laufender Prozesse nicht durch komplizierte Locking-Strategien lösen zu müssen, versuchen es Kernelprogrammierer besser, sie gleich zu vermeiden. Die Kern-Technik zeigt, wie Per-CPU-Variablen ihnen dabei helfen.
Der Schutz kritischer Abschnitte ist eine der höchsten Hürden bei der Programmierung parallel ablaufender Prozesse, vor allem bei echter Parallelität auf Mehrprozessormaschinen (SMP). Entsprechend umfangreich ist das Arsenal der Entwickler: atomare Variablen, Semaphore, Spinlocks und Memory-Barrier, alle vorgestellt in Folge 5 der Kern-Technik [1].
Einfacher ist es allerdings, kritische Abschnitte gleich zu vermeiden. Hierzu bedarf es der Änderung des Datenmodells: Statt den konkurrierenden Zugriff auf Daten durch Semaphor oder Spinlock zu sequenzialisieren, erhält jede parallel zugreifende Instanz (jeder Codeabschnitt) einen eigenen Datenbereich. Dies macht den gleichzeitigen Zugriff möglich und vermeidet den Konflikt.
Sieht das ursprüngliche Datenmodell beispielsweise vor, empfangene Bytes über eine Workqueue in einen einzelnen Buffer abzulegen, vervielfacht – gemäß neuem Datenmodell – der Kernelprogrammierer diesen Buffer entsprechend der Anzahl der parallel zugreifenden Instanzen. Jede dieser Instanzen arbeitet dann auf einem eigenen Datenbereich, der teure Zugriffsschutz entfällt auf Kosten eines etwas erhöhten Speicherbedarfs.
Oder: Wenn es beispielsweise darum geht, statistische Informationen über eine Zugriffshäufigkeit zu protokollieren, speichert im Sinne der Konfliktvermeidung jede Instanz die Anzahl der Zugriffe in einer eigenen Variablen. Erst wenn eine Anwendung sie für die Auswertung anfordert, werden die Daten zusammengeführt. So macht es zum Beispiel das Netzwerk-Subsystem.
Felder bevorzugt
Im Kernel greifen zu einem Zeitpunkt maximal so viele Instanzen zu, wie Prozessoren im System vorhanden sind. Jede CPU benötigt die Variablen damit genau ein Mal. Sie heißen deshalb auch Per-CPU-Variablen. Die Realisierung ist einfach. Anstatt eine Variable genau einmal zu definieren (»static int var«), legt der Programmierer die Variable als Array an (siehe Abbildung 1), und zwar mit so vielen Elementen wie Prozessoren im System vorhanden sind: »static int var[MAX_CPU]«.
Abbildung 1: Konfliktvermeidung: Für jede CPU wird ein eigener Speicher reserviert.
Die maximale Anzahl der Prozessoren ist ein Konfigurationsparameter bei der Kernelgenerierung und somit bekannt. Für den Zugriff auf die Variable verwendet der Entwickler das Variablenfeld mit der ID der jeweiligen CPU als Index: »sum = var[smp_processor_id()]«. Für pfiffige Entwickler ist das ein alter Hut. Neu und wenig bekannt ist allerdings, dass Kernel 2.6 für die Verwendung von Per-CPU-Variablen eine komfortable Infrastruktur zur Verfügung stellt. Diese sorgt unter anderem dafür, dass der Kernel die Variablen so im Speicher ablegt, dass sie möglichst in eine Cacheline des zugehörigen Prozessors passen. Das verhindert häufige Cache-Misses und beschleunigt damit den Zugriff.
CPU-eigene Variablen
Außerdem bietet dieses Interface Funktionen, die die Kernel-Preemption ausschalten. Kernel 2.6 hat nämlich auch die Unterbrechbarkeit von Kernelfunktionen eingeführt. Findet aber während des Zugriffs auf einen Per-CPU-Speicherbereich eine Unterbrechung und möglicherweise damit verbunden sogar eine Prozessmigration statt (der Kernel entscheidet sich den aktiven Rechenprozess auf einer anderen CPU ablaufen zu lassen), liegt doch eine zu schützende Race Condition vor (siehe hierzu Kasten “Kernel-Preemption”). Durch das Ausschalten der Kernel-Preemption lässt sich dieser kritische Abschnitt aber mit wenig Aufwand entschärfen.
|
Kernel-Preemption |
|---|
|
Bis Kernel 2.6 gehorcht Linux einem überschaubaren Unterbrechungsmodell. Es sieht im Kernel drei Ebenen vor: Die eigentliche Kernelebene, die Bottom-Halves-Ebene (BH) und die Hardware-IRQ-Ebene. Dabei können Funktionen der niederen Ebene die der oberen unterbrechen. Sobald der Kernel eine Funktion der niedrigeren Ebene beendet hat, kann er die unterbrochene Funktion weiterbearbeiten. Der Grundsatz lautet also: Funktionen im Kernel werden zwar unterbrochen, jedoch immer abgeschlossen, bevor eine Funktion auf der gleichen Ebene an die Reihe kommt. Dieses Unterbrechungsmodell reduziert auf Einprozessormaschinen die Zahl kritischer Abschnitte gewaltig. Greifen beispielsweise zwei Kernelfunktionen, die im Prozesskontext ablaufen, auf dieselbe Datenstruktur zu, ist überhaupt kein Locking notwendig. Ohne Unterbrechung langsamDiese eigentlich klare Struktur hat aber auch einen Nachteil: Tritt ein Ereignis ein, das eine Aktion mit hoher Priorität erforderlich macht, verzögert sich die Bearbeitung so lange, bis der gerade ablaufende Dienst mit niedriger Priorität abgearbeitet ist. Die Folge: Die Latenzzeiten (Startzeiten für die zugehörigen Aktionen) werden länger.  Abbildung 2: Kernel 2.4 beendet erst einen Dienst, bevor er den nächsten beginnt. Kernel 2.6 schiebt schon mal eine hoch-priore Aufgabe dazwischen. Da der im Artikel beschriebene kritische Abschnitt für Mehrprozessormaschinen ohnehin durch Semaphore oder Spinlocks abgesichert sein muss und damit die Vorteile des übersichtlichen Unterbrechungsmodells zunichte macht, hat Linus Torvalds mit Kernel 2.6 die Kernel-Preemption zugelassen. Kommt es jetzt im Kernel zu einer Unterbrechung (Interrupt), die eine hoch-priore Recheninstanz aktiviert, bearbeitet er diese sofort. Die ursprünglich aktive Kernelfunktion muss warten. Das macht sich für den Anwender in kürzeren Latenzzeiten positiv bemerkbar, verlangt dem Programmierer aber mehr Sorgfalt ab. Denn damit gibt es auch auf Einprozessormaschinen eine Reihe potenziell neuer kritischer Abschnitte, die der Entwickler sichern muss. Die Unterbrechbarkeit im Kernel lässt sich übrigens auf einer Einprozessormaschine sehr einfach demonstrieren (siehe Listing 3). Dazu sind nur zwei Kernel-Threads (siehe [2]) nötig, von denen einer mit Echtzeitpriorität, der andere ohne läuft. Beide werden periodisch aktiv. Während der Thread ohne Echtzeitpriorität seine Aktivität über ein Flag signalisiert und ansonsten nur Rechenzeit verbraucht, überprüft der Echtzeit-Thread, ob er den anderen Thread unterbrochen hat. Das erkennt er anhand des Aktivitäten-Flag. Um die Wahrscheinlichkeit einer Unterbrechung zu erhöhen, lässt das Beispiel beide Threads über unterschiedliche Schlafenszeiten asynchron zueinander arbeiten. Das Schlafenlegen ist auch wichtig, damit das System durch die CPU-hungrigen Kernel-Threads nicht zum Stillstand kommt. Schließlich bringt der Kernel – mit oder ohne Preemption – immer erst eigene Funktionen oder Threads zum Abschluss (Schlaf oder Exit), bevor User-Prozesse an die Reihe kommen. Test mit KernelmodulZum Test der Unterbrechbarkeit dient der Code aus Listing 1. Nach dem Laden des generierten Moduls mit »insmod kthreadrt.ko disable=0« entlädt »rmmod kthreadrt« es wieder. Falls der Kernel für Kernel-Preemption kompiliert ist, taucht im Syslog eine Meldung wie in Abbildung 3 auf. Beim Test wurde der niedrig-priore Kernel-Thread 25-mal unterbrochen und 251-mal nicht unterbrochen.  Abbildung 3: Kernel-Preemption eingeschaltet: Der hoch-priore Kernel-Thread unterbricht den normal-prioren. Nun soll das Modul ein zweites Mal geladen werden, jetzt mit dem Parameter »disable=1«. Nach zwei Sekunden soll es wieder entladen werden. Dazu dient die Befehlssequenz: insmod kthreadrt.ko disable=1; sleep 2; rmmod kthreadrt Der Parameter »disable=1« bewirkt, dass der normal priorisierte Kernel-Thread die Unterbrechbarkeit im Kernel ausschaltet. Eine Zeile im Syslog wie »interrupted: 0« zeigt an, dass keine Unterbrechung stattgefunden hat (siehe Abbildung 1). |
Tabelle 1 listet die Funktionen für Per-CPU-Variablen auf. Der Kernelprogrammierer legt eine Per-CPU-Variable mit Hilfe des Makros »DEFINE_PER_CPU(Datentyp, Variablenname)« an. Das Makro »DECLARE_PER_CPU(Datentyp, Name)« realisiert die Deklaration für den Zugriff eines anderen Moduls auf die Variable. Allerdings muss sie dazu vom definierenden Quellcode per »EXPORT_PER_CPU_SYMBOL_GPL()« beziehungsweise »EXPORT_PER_CPU_SYMBOL()« exportiert werden.
|
Tabelle 1: |
|
|---|---|
|
Name |
Kurzbeschreibung |
|
DEFINE_PER_CPU() |
Legt eine CPU-Variable an |
|
DECLARE_PER_CPU() |
Macht eine CPU-Variable bekannt |
|
get_cpu_var() |
Schaltet Kernel-Preemption aus und gibt die Variable |
|
put_cpu_var() |
Schaltet Kernel-Preemption ein |
|
per_cpu() |
Zugriff auf die Variable ohne Abschaltung der |
|
EXPORT_PER_CPU_SYMBOL() |
Exportiert die Variable |
|
EXPORT_PER_CPU_SYMBOL_GPL() |
Exportiert die Variable und erlaubt nur den Import |
|
alloc_percpu() |
Reserviert im Modul Per-CPU-Speicher |
|
free_percpu() |
Gibt reservierten Speicher wieder frei |
|
per_cpu_ptr() |
Liefert die Adresse einer per »alloc_percpu()« |
Das Makro »get_cpu_var(name)« übernimmt den eigentlichen Zugriff auf die Variable. Seine Handhabung ist etwas gewöhnungsbedürftig. Es schaltet die Kernel-Preemption aus und löst dann den Variablennamen als so genannten Lvalue auf. Will der Programmierer die Per-CPU-Variable zum Beispiel inkrementieren, darf das »++« direkt hinter dem Makro stehen: »get_cpu_var(stat)++«. Wenn es sich um eine Datenstruktur handelt, steht unmittelbar nach der schließenden Klammer die Elementauswahl, also zum Beispiel »get_cpu_var(statstruct).open«.
Um die Kernel-Preemption wieder zu aktivieren, ruft man »put_cpu_var(Name)« auf. Zwischen »get_cpu_var()« und »put_cpu_var()« können beliebig viele Zugriffe auf die Variable erfolgen, allerdings ist es bei Mehrfachzugriffen – wie Listing 2 zeigt – besser, über Pointer zuzugreifen. Ist die Kernel-Preemption ausgeschaltet, ist das Schlafenlegen trotz Prozesskontext tabu und wird vom Kernel mit einer Absturz-Meldung (Ooops-Message) quittiert.
|
Listing 1: |
|---|
01 #include <linux/module.h>
02 #include <asm/delay.h>
03 #include <asm/atomic.h>
04
05 static int thread_id_nort=0, thread_id_rt=0;
06 static DECLARE_COMPLETION( on_exit );
07 static atomic_t active = ATOMIC_INIT(0);
08 static int interrupted = 0, not_interrupted = 0;
09 static int disable=0;
10 module_param( disable, int, 0666 );
11
12 static int thread_nort( void *data )
13 {
14 unsigned long remaining;
15
16 daemonize("normal-kthread");
17 allow_signal( SIGTERM );
18 while( 1 ) {
19 if( disable ) preempt_disable();
20 atomic_set( &active, 1 );
21 udelay( 1000 );
22 set_task_state( current, TASK_INTERRUPTIBLE );
23 atomic_set( &active, 0 );
24 if( disable ) preempt_enable();
25 remaining = schedule_timeout( 10 );
26 if( signal_pending(current) ) {
27 thread_id_nort = 0;
28 break;
29 }
30 }
31 complete_and_exit( &on_exit, 0 );
32 }
33
34 static int thread_rt( void *data )
35 {
36 unsigned long remaining;
37 struct sched_param sched_params;
38
39 daemonize("rt-kthread");
40 allow_signal( SIGTERM );
41
42 sched_params.sched_priority = 50;
43 if( sched_setscheduler(current,SCHED_RR,&sched_params)!=0 ) {
44 printk("can't set realtime priority ...n");
45 complete_and_exit( &on_exit, -1 );
46 }
47
48 while( 1 ) {
49 set_task_state( current, TASK_INTERRUPTIBLE );
50 remaining = schedule_timeout( 7 );
51 if( atomic_add_return(0,&active) )
52 interrupted++;
53 else
54 not_interrupted++;
55 if( signal_pending(current) ) {
56 thread_id_rt = 0;
57 break;
58 }
59 }
60 printk(" interrupted: %dnnot interrupted: %dn",
61 interrupted, not_interrupted );
62 complete_and_exit( &on_exit, 0 );
63 }
64
65 static int __init kthread_init(void)
66 {
67 #ifndef CONFIG_PREEMPT
68 printk("KERNEL DOES NOT SUPPORT KERNEL-PREEMPTION!n");
69 #endif
70 thread_id_nort=kernel_thread(thread_nort,NULL,CLONE_KERNEL);
71 if( thread_id_nort==0 )
72 return -EIO;
73 thread_id_rt=kernel_thread(thread_rt,NULL,CLONE_KERNEL);
74 if( thread_id_rt==0 ) {
75 kill_proc( thread_id_nort, SIGTERM, 1 );
76 wait_for_completion( &on_exit );
77 return -EIO;
78 }
79 if( disable )
80 printk("Kernel-Preemption in kernel-thread disabled...n");
81 else
82 printk("Kernel-Preemption in kernel-thread activated...n");
83 return 0;
84 }
85
86 static void __exit kthread_exit(void)
87 {
88 kill_proc( thread_id_nort, SIGTERM, 1 );
89 kill_proc( thread_id_rt, SIGTERM, 1 );
90 wait_for_completion( &on_exit );
91 wait_for_completion( &on_exit );
92 }
93
94 module_init( kthread_init );
95 module_exit( kthread_exit );
96 MODULE_LICENSE("GPL");
|
|
Listing 2: Kernel-Preemption |
|---|
01 static DEFINE_PER_CPU( unsigned long, readstat ); 02 ... 03 unsigned long *readstatp; 04 .... 05 get_cpu_var(readstat)++; 06 put_cpu_var(readstat); 07 ... 08 readstatp = &get_cpu_var(readstat); 09 *readstatp++; 10 *readstatp++; 11 put_cpu_var(readstat); |
Nur mit GPL
Die bisher beschriebenen Funktionen stehen leider nicht allen Kernelkomponenten zur Verfügung. Dass jene Komponente, die Per-CPU-Funktionen benutzen will, GPL-konform sein muss, ist noch leicht zu bewerkstelligen. Schwierigkeiten bereitet eher, dass Kernelmodule die Funktionen aus technischen Gründen nicht benutzen können. Der Linker legt die Variablen nämlich in einem speziellen Segment an.
Innerhalb eines Moduls weichen die Entwickler daher auf die dynamische Allokation über »void *alloc_percpu(size_t Datentyp)« und »void free_percpu(const void *Referenz)« aus. Die Funktion »alloc_percpu()« nutzt »kmalloc()« und gibt als Referenz die Basisadresse des Variablenfelds zurück. Meist ruft man »alloc_percpu()« während der Modul-Initialisierung auf.
|
Listing 3: |
|---|
01 void *percpu_ref; 02 int cpuid; 03 struct stat *read_stat; // Für die Referenz 04 ... 05 per_cpu_ref = alloc_percpu( struct stat ); 06 ... 07 cpuid = get_cpu(); 08 read_stat = per_cpu_ptr( per_cpu_ref, cpuid ); 09 read_stat->count += 2; // Verwendung der Variablen 10 put_cpu(); 11 ... 12 free_percpu( percpu_ref ); |
Manuell absichern
Mit der Referenz lässt sich die Adresse des zum gerade aktiven Prozessors gehörenden Datenbereichs bestimmen. Dazu dient die Funktion »get_cpu_ptr(Referenz, cpuid«, die die Adresse des zur CPU-Identifikation »cpuid« gehörenden Datenbereichs liefert. Die Parameterliste der Funktion deutet bereits an, dass ein Prozessor durch Angabe der »cpuid« auf jede beliebige Per-CPU-Variable zugreifen kann. Dabei ist aber Vorsicht geboten: Der Zugriff findet konkurrierend zur anderen CPU statt. Es handelt sich also wieder um einen kritischen Abschnitt, der gesichert werden muss.
Üblich ist es daher, die »cpuid« des gerade aktiven Prozessors mit »get_cpu()« zu bestimmen, das zuvor die Kernel-Preemption ausschaltet. Nach erfolgtem Zugriff schaltet »put_cpu()« sie wieder ein. Wird die Per-CPU-Variable nicht mehr benötigt, gibt »free_percpu()« ihren Speicher frei. Listing 3 zeigt, wie sich im Modulcode mehrere Per-CPU-Variablen verwenden lassen.
Nur wenige Kernelprogrammierer benutzen bislang in Modulen den Zugriff auf Per-CPU-Speicher – abgesehen von einigen Anwendungen im Netzwerk-Code. Dagegen finden sich im statischen Teil des Kernels bereits rund 100 Per-CPU-Variablen. Weitere Informationen zu diesen Variablen sind in den beiden Büchern [3] und [4] zu finden. (ofr)
|
Infos |
|---|
|
[1] Eva-Katharina Kunst und Jürgen Quade, “Kern-Technik”, Folge 5: Linux-Magazin 12/03, S. 82 [2] Eva-Katharina Kunst und Jürgen Quade, “Kern-Technik”, Folge 4: Linux-Magazin 11/03, S. 96 [3] Robert Love, “Linux Kernel Development”, 2. Auflage: Novell Press 2005 [4] Corbet, Rubini, Kroah-Hartman, “Linux Device Drivers”, 3. Auflage: O\’Reilly 2005 [5] Listings und Makefile: [https://www.linux-magazin.de/Service/Listings/2006/02/Kern-Technik/] |
