Grundlegende Kernelstrukturen und Funktionen

Page OFFSET

Dieses Modell wurde eingeführt, da mache Prozessoren die Adressierung von nur 1 Segment erlauben (Dec, Alpha)

ê Umschaltung der Adressräume muss ausdrücklich veranlasst werden. (internes Koroutinen-Modell)

ê Schutz: Zugriff auf Kernelsegment ist im User-Modus verboten (sonst könnte sich jeder User zum
Admin machen!), „harte Grenze“.

è Trennung User-Stack und Kernel-Stack

Implementierungstrick

pseudo-variable current:

(Zeiger auf) à Prozess der gerade läuft

Mit 2 Maschinenbefehlen

MOV SP à ACCU

AND ACCU, ~ ((1 << 11) –1) ß (ACCU DIV 2048)* 2048

(2¹¹ –1) invertiert

Jeder Prozess hat SU-Stack (mind. für jede CPU)

ê Rekursionen im Kernelmodus sehr problematisch, Stack ist beschränkt. (512 Prozesse * 2k = 1 MB)

ê Bei SMP hat jeder Prozessor seinen eigenen Supervisor-Stackpointer, aber trotzdem den gemeinsamen Kernel-Adressraum à SMP- Synchronisationsproblem.

ê Kernel-Pointer und User-Pointer sind unterschiedlich!

ê Beide sind virtuell: Physikalische Adresse = virtuelle Kerneladresse + page_OFFSET

Zugriff auf User-Segment:

Der Zugriff der Daten im User-Segment kann nie direkt, sondern nur über Makros oder Funktionen erfolgen.

int access_ok (type, addr, size);

type {VARIFY_READ, VARIFY_WRITE}

überprüft, ob lesend bzw. schreibend auf einen Useradressbereich zugegriffen werden kann.

varify_area ();

Makro:

get_user (result, addr)

Lesen eines skalaren Wertes aus dem Usersegment, wobei der result-Typ automatisch vom Typ von addr bestimmt wird.

analog:

put_usr (x, ptr)

Schreiben eines skalaren Wertes aus dem Usersegment.

unsignedlong copy_to_user (to, from, n)

unsignedlong copy_from_user (to, from, n)

Kopieren von Daten in/aus dem Usersegment.

Pointertypen:

Pointer auf Userdaten

Pointer in Kernel

auf physikalische Adresse

ê Aufpassen, welche Art von Pointer übergeben wird!

Synchronisationsmittel auf Task-Ebene

Unterste Ebene: void schedule (void)

Sucht einen (anderen) lauffähigen Prozess, schaltet Koroutine auf diesen Prozess um.
ê Prozess wird einfach durch Setzen / Löschen von current à state = <state>
state:
TASK_RUNNING

Der Prozess wartet auf seine Zuteilung oder läuft gerade.

TASK_INTERUPTIBLE
TASK_UNINTERUPTIPLE

Der Prozess wartet auf bestimmte externe Ereignisse. Der Unterschied zwischen diesen beiden Werten besteht darin, dass im Zustand TASK_INTERUPTIBLE ein Prozess durch Signale wieder aktiviert werden kann, während er im Zustand TASK_UNINTERUPTIPLE in der Regel direkt oder indirekt auf eine Hardwarebedingung wartet und damit keine Signale akzeptiert.

TASK_STOPPED

Beschreibt einen Prozess dessen Ausführung angehalten worden ist.

TASK_ZOMBIE

Beschriebt einen Prozess, der beendet worden ist, dessen Taskstruktur sich aber noch in der Prozesstabelle befinden muss.

Der Scheduler ist für die Zuteilung der Ressource „Prozessor“ (also Rechenzeit) an die einzelnen Prozesse verantwortlich. Es ist möglich, dass ein Prozess der Klase SCHED_FIFO so lange laufen kann wie er möchte bis er die Steuerung freiwillig abgibt. Nur ein Prozess mit höhere Echtzeitpriorität kann diesen Prozess unterbrechen.

Die Funktion schedule() besteht aus drei Teilen. Zuerst werden Routinen die regelmäßig aufgerufen werden müssen, gestartet. Danach wird der Prozess mit der höchsten Priorität bestimmt. Als drittes wird der neue Prozess zum aktuellen Prozess und der Scheduler hat seine Arbeit erledigt.

Ein Prozess kann folgende Zustände annehmen:

Bei der Wahl des nächsten Prozesses überprüft der Scheduler ob das Attribut state der task_struct Struktur auf TASK_RUNNING (Warten) gesetzt ist, denn nur dann ist der Prozess auch bereit. Unter besonderen Umständen (warten auf ein bestimmtes Ereignis z.B. I/O-Operationen) kann es passieren, dass ein laufender Prozess in den blockierenden Zustand wechselt wobei das state Attribut hierbei auf TASK_INTERUPTIBLE oder TASK_UNINTERUPTIPLE gesetzt wird. In diesem Fall wird der Scheduler diesen Prozess bei der nächsten Wahl nicht mehr berücksichtigen. Wenn das bestimmte Ereignis eingetreten ist, wird das state Attribut wieder auf TASK_RUNNING gesetzt und beim nächsten Durchlauf des Schedulers berücksichtigt.

Mittlerer Ebene: ADT wait_queue

Oftmals ist ein Prozess vom Eintreten bestimmter Bedingungen abhängig. Sei es, dass der Systemaufruf read() darauf warten muss, dass die Daten von der Festplatte in den Speicherbereich des Prozesses geladen werden, oder dass ein Elternprozess mit wait() auf das Ende eines Kindprozesses wartet. In jedem dieser Fälle ist nicht bekannt, wie lange ein Prozess warten muss.

Dieses „Warten bis eine Bedingung erfüllt ist“ wird in Linux mit Hilfe der Warteschlange (Waitques) realisiert. Ein Warteschlange ist nichts anderes als eine zyklische Liste, welche als Element Zeiger in die Prozesstabelle enthält.

void add_wait_queue (struct wait_queue **queue,
struct wait_queue *entry);

void remove_wait_queue (struct wait_queue **queue,
struct wait_queue *entry);

Ein Prozess, der auf ein bestimmtes Ereignis warten will, trägt sich nun in eine solche Warteschlange ein und gibt die Steuerung ab (Koroutinen-Modell). Zu jedem möglichen Ereignis gibt es eine Warteschlange. Wenn das entsprechende Ereignis eintritt, werden alle Prozesse in dieser Warteschlange wieder aktiviert und können weiterarbeiten. queue enthält jeweils die zu modifizierende Warteschlange (das entsprechende Ereignis).

Diese Semantik wird durch die Funktion

void [interruptible_] sleep_on (struct wait_queue ** q)

realisiert. Sie setzt den Status des Prozesses (current-> state) auf den Wert TASK_UNINTERUPTIPLE bzw. TASK_INTERUPTIBLE, tragen den aktuellen Prozess (current) in die Warteschlange ein und rufen den Scheduler auf. Damit gibt der Prozess die Steuerung freiwillig ab.

Der Prozess wird erst wieder aktiviert, wenn der Prozessstatus auf TASK_RUNNING gesetzt wurde. Das geschieht in der Regel dadurch, dass ein anderer Prozess das Makro

void wake_up (struct wait_queue **q);

aufruft, um alle in der Warteschlange eingetragenen Prozesse zu wecken.

High-Level-Ebene: Semaphore

Mit Hilfe von Warteschlangen stellt Linux auch Semaphore bereit. Diese dienen der Synchronisation verschiedener Routinen des Kerns auf gemeinsam benutze Datenstrukturen. Diese Semaphore sind nicht mit dem für Anwendungsprogramme bereitgestellten Semaphoren von Unix System V zu verwechseln.

struct semaphore {

int count;

struct wait_queue *wait;

unsigned long owner, owner_depth;

int waking;

}

Ein Semaphor gilt als belegt, wenn count einen Wert kleiner oder gleich 0 hat. In die Warteschlange tragen sich alle Prozesse ein, die den Semaphor belegen wollen. Sie werden dann benachrichtet, wenn er von einem anderen Prozess freigegeben wird. owner enthält einen Verweis auf die Task, die den Semaphor gerade belegt hat, owner_depth gibt an, wie oft diese Task den Semaphor belegt hält. Zum Belegen oder Freigeben von Semaphoren gibt es zwei Hilfsfunktionen:

void down (struct semaphore* sem); /* P-Operation */
void up (struct semaphore* sem); /* V-Operation */

Weiteres

Weitere High-Level-Funktionen insbesondere 2 verschiedene Timer-Implementierungen

Interrupts

Zur Kommunikation der Hardware mit dem Betriebsystem werden Interrupts verwendet. Beim Entwurf einer Interruptroutine steht der Programmierer vor einem Problem. Zum einen muss die eigentliche Interruptroutine die Hardware so schnell wie möglich bedienen und dann den Prozessor für andere Aufgaben so schnell wie möglich für die Bearbeitung weiterer Interrupts, wieder freigeben. Zum anderen kann so ein Interrupt aber auch die Verarbeitung einer größeren Datenmenge auslösen.

Um dieses Problem zu lösen, erfolgt die Interruptbehandlung unter Linux in zwei Phasen. Zuerst wird die zeitkritische Kommunikation mit der Hardware durchgeführt, hierbei sind eventuell andere Interrupts gesperrt. Die eigentliche Verarbeitung der Daten erfolgt asynchron zum eigentlichen Interrupt in den sogenannten „Bottom Halfs“ der Interrupthandler. Dies sind Funktionen, die zu einem späteren Zeitpunkt aufgerufen werden. Sie können ihrerseits auch wieder von anderen Interrupts unterbrochen werden.

ê Können „jederzeit“ auftreten à liegen quer zum Koroutinen-Modell

à besondere Sorgfalt notwendig, z.B. darf in Interrupts kein Schedule() aufgerufen werden!
(Zerstörung des Koroutinen-Modells, schedule() könnte rekursiv unterbrochen werden) Re-Entranz-Problem (Wiedereintrittsproblem)

è Interrupts müssen gesperrt werden können, bei allen Prozessortypen über das Statusregister.

Makros: __cli() /* Interrupts sperren */ (lokal)

__sti() /* Interrupts wieder zulässig*/ (lokal)

save_flags (flags) à Interrupts merken

restore_flags (flags) à Interrupts wiederherstellen

cli() und sti() für alle Interrupts auf allen Prozessoren (bei SMP-Kernel)

ê Interrupt-Programmierer müssen aufpassen, keine Kernelfunktionen aufzurufen, die blockieren können!

ê In Interrupts darf man nicht warten!

Beispiel Interruptbetrieb:

Im Interruptbetrieb benachrichtigt das Gerät die CPU über einen Interruptkanal (IRQ), wenn es eine Operation beendet hat. Die CPU unterbricht den laufenden Betrieb und führt eine Interruptserviceroutine (ISR) aus. Innerhalb der ISR erfolgt dann die weitere Kommunikation mit dem Gerät. So wird ein Prozess, der auf die parallele Schnittstelle im Interruptbetrieb schreiben will, vom Gerätetreiber im Interruptbetrieb nach dem Schreiben eines Zeichens angehalten. Kann die parallele Schnittstelle weitere Zeichen entgegennehmen, löst sie einen IRQ aus. Die behandelnde ISR weckt den Prozess daraufhin wieder (current->sate = TASK_RUNNING) und der Vorgang wiederholt sich.

Zuerst wird die Schnittstelle ermittelt, die den Interrupt auslöste, und danach der wartende Prozess mit wake_up() „wachgeküsst“ .

Synchronisationsmittel auf CPU-Ebene (SMP)

Bei Symmetric Multi Processing (SMP) können mehrere Prozessoren in kritischen Abschnitten um die selbe Ressource konkurrieren. Um dieses Problem zu lösen, wurden in den Linux-Kernel Spin Locks eingeführt. Sie realisieren den gegenseitigen Ausschluss von Prozessoren im Kernel. Der kritische Abschnitt kann nur von dem Prozessor ausgeführt werden, der sich gerade im Besitz des Spin Locks befindet.

ê liegt nochmals „quer“, sowohl zum Koroutinen-Modell als auch zu den Interrupts!

à Spinnlocks

ADT spinlock_t; („bringe und lösche“)

void spin_lock_init (lock);

void spin_lock (lock);

void spin_unlock (lock);

int spin_trylock (lock);

Wegen Problemen mit Interrupts:

spin_[un]lock_irq (lock)

verhindert Interrupts für die Dauer des gehaltenen Locks.

ê Bei Schachtelung mehrerer Locks geht das schief!

Lösung:

spin_[un]lock_irq_save (lock);

Um einen kritischen Bereich zu betreten, muss spin_lock() aufgerufen werden. Falls sich ein Prozessor bereits in diesem Bereich befindet, bleibt der aktuelle Prozessor so lange im Spinlock² gefangen, bis der andere Prozessor den kritischen Bereich verlassen hat.

Verlässt ein Prozessor einen kritischen Bereich, muss spin_unlock() aufgerufen werden. Vergisst man diesen Aufruf, kann schnell der Rechner einfreieren, da danach kein Prozessor mehr diesen Bereich betreten kann.

Mit Hilfe von spin_trylock() kann abgefragt werden, ob ein Bereich betreten werden kann. Liefert diese den Wert 0, ist der Bereich momentan belegt. Ansonsten ist er frei. Ein weiteres spin_lock() ist nicht mehr erforderlich, da spin_trylock() den Spinlock belegt.

Weitere Möglichkeiten in <asm/atomic.h> atomare Operation für Zähler:

z.B. atomic_inc()

atomic_dec()

atomic_add()

atomic_sub()

Diese Funktionen erlauben es, den Wert einer atomaren Variable durch Addition oder Subtraktion eines Werts zu ändern.

Allgemeine Hilfsroutinen

Meldungen an Systemkonsole. Funktion um Kontroll- und Debugmeldungen ausgeben zu können. Es werden nur Mitteilungen die wichtig genug sind auf der Konsole ausgegeben (d.h. in der Priorität höher als das Loglevel liegen). Das Loglevel kann durch den Systemruf syslog eingestellt werden.

int printk (char* fmt, ...) eingeschränkte Version von printf

void panic (char* str);

Diese Funktion ist ein printk() mit der festen Priorität KERN_EMERG. Zusätzlich wird die Kernfunktion sys_sync() aufgerufen.

<linux/string.h>

char* strcpy ( char* ziel,

const char* quelle);

kopiert den String quelle einschließlich Nullbyte.

char* strncpy ( char* ziel,

const char* quelle,

size_t count );

nur die ersten count-Zeichen werden kopiert.

size_t strlen (char* str);

liefert sie Anzahl der Zeichen in str, ohne das Nullbyte.

Folgende Funktionen bearbeiten Speicherbereiche. Normalerweise handelt es sich um Speicher in Form von Zeichenketten, die nicht durch ein Nullbyte abgeschlossen sind.

void* memset (void* addr,

int inival,

size_t len);

füllt den mit addr adressierten Bereich der Größe len mit inival

void* memcpy (void* ziel,

void* quelle,

size_t len);

der Bereich ziel wird mit den ersten len Zeichen aus quelle gefüllt.

Folgende Funktion setzt das Bit nr an der Adresse addr.

<asm/bitops.h>

void set_bit (int nr,

void* addr);

Speicherallokation im Kernel

Der physische Speicher wird in Pages strukturiert. Die Größe der Pages ist durch das Makro PAGE_SIZE definiert. Für 32-Bit-Architekturen wie x86 beträgt die Größe meist 4 KB.

Low-Level

unsigned long __get_free_page (int gfp_mask)

à Pointer à Typecast notwendig!

GFP_KERNEL

(GFP_USER à der laufende Prozess darf zum Auslagern von Speicherseiten unterbrochen werden)

GFP_ATOMIC

(Die Funktion __get_free_page darf den laufenden Prozess nicht unterbrechen, aber sollte nach Möglichkeit eine Speicherseite zurückliefern) à garantiert kein schedule().

GFP_KERNEL | GFP_DMA oder

GFP_ATOMIC | GFP_DMA à liegt unter 16 MB-Grenze (braucht man nur bei Intel)

Eigenschaften:

• Speicherbereich hat Größe PAGE_SIZE

• beginnt an einer PAGE_SIZE-Grenze

unsigned long __get_free_pages (int gfp_mask,

unsigned long gfp_order);

è Größe ist (PAGE_SIZE << gfp_order). Ein Block mit der Ordnung x ist 2^x Speicherseiten groß.

Weiterer Versionen ohne __ löschen den allokiertern Speicher

ê Allokierter Speicher beginnt an der Größen-Grenze

Objekt-Caches

<linux/slab.h>

<linux/simp.h>

ADT:

kmem_cache_t* kmem_cache_create (const char* name,

size_t size,

size_t offset,

unsigned long flags,

void(x)(void*, kmem_cache_t* unsigned long),

... );

Mit kmem_cache_create wird ein neuer Cache für Objekte der Größe size angelegt. Mit offset kann ein Alignment für die Objekte, kleiner als die Objekte selber angefordert werden.

Die Allokation und Freigabe einzelner Objekte ist mit

void* kmem_cache_alloc (kmem_cache_t *,

int gfp_mask);

void kmem_cache_free (kmem_cache_t *,

void* obgp);

möglich. Bei kmem_cache_alloc() können in den Flags die Priorität für das Allokieren einer Speicherseite angegeben werden.

Idee:

Objekt muss nur einmal konstruiert werden, kmem_cache_free() gibt Objekte zurück, die noch (teilweise) sinnvolle Informationen enthalten.

Heterogener Heap im Kernel Speicher

void* kmalloc (size_t size,

int gfp_mask);

versucht Speicher mit der Größe size zu reservieren. Es ist die Reservierung von Speicher bis zu 128kByte möglich. Der Speicher ist aus dem physikalischen Speicherbereich allokiert.

void kfree (const void *obj);

so kann der reservierte Speicher wieder freigegeben werden.

Virtueller Adreßraum

void* vmalloc (size_t size);

void vfree (void* addr);

Blendet vielfaches von Speicherseiten in den virtuellen Adressraum des Kernels ein, lässt Lücken von mind. 1 Seite im virtuellen Adressraum.

à allokierter Speicher beginnt an Page-Grenzen

Wichtige grundlegende ADT’S im Kernel

struct task_struct

(sehr umfangreich) beinhaltet sowohl User- als auch Kerneldaten für Prozesse.

Dazu globales Array

struct task_struct *task[NR_TASK];

Das Array ist auf max. 512 Prozesse beschränkt!

struct mm_struct

Beschreibt Layout eines virtuellen Adreßraumes.

à neu 1 Instanz pro task_struct-Instanz notwendig.

struct vm_area_struct

Beschreibt Segment eines virtuellen Adressraumes.

ê Eine vm_area_struct-Instanz kann Mitglied in mehreren mm_struct-Instanzen sein.

à Inoffizieller clone()- Systemaufruf

struct vm_operations_struct

Enthält Methoden zur Verwaltung eines Segments.

struct page

Beschreibt physikalische Speicherseite

(1:1 Zuordnung zwischen mem[] und der Speicherseite)

struct inode

Beschreibt genau ein (passives) Dateiobjekt

ê bei Hardlinks ist nur 1 Instanz vorhanden

ê Objekt muss keinen Namen haben, z.B. anonyme Pipes

struct dentry

Beschreibt Namen für ein Dateiobjekt.

struct file

Beschreibt Kanal für ein Dateiobjekt (es kann mehrere Kanäle zu einer Datei geben)

ê Es können mehrere (unabhängige) Kanäle für dasselbe Dateiobjekt existieren!

struct super_block

Beschreibt Dateisystem-Typ, z.B. ext2, iso9660, nfs, ...

struct {inode, super, dentry, file}_operations

ê theoretisch sollten hier die zur jeweiligen Struktur gehörenden Methoden stehen, es herrscht aber Chaos!

struct buffer_head

Beschreibt Platten-Datenblöcke, zur Verwendung in Dateisystem-Implementierungen

ê Ursprünglicher Zweck war Buffer-Cache, dessen Funktion inzwischen teilweise durch einen Page-Cache realisiert ist!