Poznámky k jádru Linux 2.4

Copyright (C) 14. srpna 2001, verze dokumentu 0.9.3

Kamil Toman <ktoman@email.cz>,
Martin Mačok <martin.macok@underground.cz>

linux logo Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.1
or any later version published by the Free Software Foundation;
with the Invariant Sections being LIST THEIR TITLES, with the
Front-Cover Texts being LIST, and with the Back-Cover Texts being LIST.
A copy of the license is included in the section entitled "GNU
Free Documentation License".

Aktuálně se informace vztahují k standardnímu jádru Linuxu verze 2.4.7. Co se týče architekturově závislých částí, zabývali jsme se jen architekturou x86 (IA32) a x86 SMP.

Obsah

Vytvoření jádra

Pokud si chceme vyzkoušet nové linuxové jádro, zkonfigurované nebo upravené podle našich představ, budeme jej napřed muset vytvořit. Podívejme se, co se děje, když napíšeme make bzImage.

Poznámka: Kromě jádra bzImage je možné vytvořit i (až na zavaděč) stejné linuxové jádro, zImage, Tuto metodu používal linux dříve a zřejmě jediný důvod, proč ještě zůstává součátstí standardního vývojového stromu, je, že jádra bzImage není možné na některých počítačích kvůli chybám BIOSu vůbec zavést. Bohužel je to za cenu ještě větší komplikovanosti už tak ne zrovna přehledného zavaděče.

Standardním překladačem jazyka C a assembleru cc(1) respektive as(1) jsou všechny relevantní soubory .c a .S přeloženy modulů .o binárního formátu ELF, případně jsou jednotlivé moduly dále sdruženy do knihovních archivů .a s pomocí ar(1) .

  1. Proběhne normální statické slinkování všech potřebných souborů .o a .a do souboru vmlinux (na architektuře x86 je to 32-bitový LSB ELF).
  2. Příkazem nm vmlinux, je (po nezbytné redukci) vytvořena mapa systémových symbolu jádra System.map .
  3. Ze souboru arch/i386/boot/bootsect.S se vytvoří assemblerový zdroj zavaděče pro bzImage, ten se přeloží a výsledný modul je po zkrácení o hlavičky ELF formátu uložen jako binární zavaděč bbootsect .
  4. Podobně, překladem a následným zkrácením o hlavičky, je ze souborů setup.S a video.S vytvořen soubor bsetup.
  5. Do adresáře adresáři arch/i386/boot/compressed se překopíruje soubor vmlinux, který se zbaví sekcí .note a .comment z ELF hlavičky, upravený soubor je pak zkomprimován pomocí gzip(1) a převeden na relokovatelný ELF piggy.o.
  6. Soubor piggy.o je slinkován s dekompresními rutinami v head.o a misc.o do souboru bvmlinux .
  7. Soubor bvmlinux je opět zbaven sekcí .note a .comment z ELF hlavičky a uložen do bvmlinux.out.
  8. S pomocí tools/build jsou (za sebou) spojeny bbootsect, bsetup a compressed/bvmlinux.out do výsledného bzImage. Do bootsektoru jsou také zapsány některé informace zavaděče, nicméně je možné je později změnit pomocí příkazu rdev(8).

Bootování

Zavedení operačního systému nebývá příliš náročný úkol. Na architektuře x86 je to, s postupem času, stále komplikovanější sled úkonů, které je potřeba udělat. Samozřejmě, je to především dáno požadavky na co největší zpětnou kompatibilitu.

BIOS POST

Bootsektor

Většina dnešních PC používá nějaký bootloader , pokud na nich běží Linux, pak nejčastěji LILO (LInux Loader), anebo modernější Grub. Linux lze ale zavést i bez asistence takových programů - například tak, že linuxové jádro nakopírujeme na disketu tak, aby se část bbootsect jádra bzImage dostala na nultou stopu, první sektor bootovacího zařízení,(např. příkazem cat bzImage > /dev/fd0).

Co se pak stane? Na fyzické adrese 0x7C00:0000 se začne provádět programový kód zavaděče Linuxu, popsaný v souboru arch/i386/boot/bootsect.S (pozor, CPU je pořád v reálném 16tibitovém režimu):

  movw    $BOOTSEG, %ax
  movw    %ax, %ds
  movw    $INITSEG, %ax
  movw    %ax, %es
  movw    $256, %cx
  subw    %si, %si
  subw    %di, %di
  cld
  rep
  movsw
  ljmp    $INITSEG, $go
  
  go:     movw    $0x4000-12, %di         # 0x4000 is an arbitrary value >=
                                          # length of bootsect + length of
                                          # setup + room for stack
                                          # 12 is disk parm size.
  movw    %ax, %ds                        # ax and es already contain INITSEG
  movw    %ax, %ss
  movw    %di, %sp                        # put stack at INITSEG:0x4000-12.
kde příslušné konstanty definované arch/i386/boot/bootsect.S resp. include/asm/boot.h jsou
  SETUPSECTS      = 4                     /* default nr of setup-sectors */
  BOOTSEG         = 0x07C0                /* original address of boot-sector */
  INITSEG         = DEF_INITSEG           /* we move boot here - out of the way */
  SETUPSEG        = DEF_SETUPSEG          /* setup starts here */
  SYSSEG          = DEF_SYSSEG            /* system loaded at 0x10000 (65536) */
  SYSSIZE         = DEF_SYSSIZE           /* system size: # of 16-byte clicks */
  /* to be loaded */
  #define DEF_INITSEG     0x9000
  #define DEF_SYSSEG      0x1000
  #define DEF_SETUPSEG    0x9020
  #define DEF_SYSSIZE     0x7F00

Tedy, první část programového kódu zkopíruje sebe sama do vyšší paměti a pokračuje v provádění na nové adrese, jak ukazuje obrázek:

Kopírování bootsektoru

Zbytek instrukcí za $go připravuje dostatečný zásobník pro rutiny, které nahrají a spustí programový kód setup.S (proto je potřeba při změnách kódu setupu dávat pozor, aby jeho programový kód + zásobník potřebný pro jeho běh nebyl mimo meze stanovené konstantami v bootsektoru). Další část kódu zavaděče je spíš technická záležitost - upravuje tabulky BIOSu, aby čtení dat pomocí jeho standardních služeb nemuselo probíhat po jednom sektoru a načte na fyzickou adresu $INITSEG:0x0200 programový kód setup.S :

load_setup:
  xorb    %ah, %ah                # reset FDC
  xorb    %dl, %dl
  int     $0x13
  xorw    %dx, %dx                # drive 0, head 0
  movb    $0x02, %cl              # sector 2, track 0
  movw    $0x0200, %bx            # address = 512, in INITSEG
  movb    $0x02, %ah              # service 2, "read sector(s)"
  movb    setup_sects, %al        # (assume all on head 0, track 0)
  int     $0x13                   # read it
  jnc     ok_load_setup           # ok - continue
  
  pushw   %ax                     # dump error code
  call    print_nl
  movw    %sp, %bp
  call    print_hex
  popw    %ax
  jmp     load_setup

Pokud se čtení sektoru nepovede, například kvůli vadné disketě, vypíše rutina chybový kód a zkusí sektor načítat znovu (to je skoro zbytečné, vadný disk zkrátka zůstane vadný). Zavaděč tak skončí v nekonečném cyklu a jediná cesta ven je reboot počítače. Počítadlo neúspěšných pokusů chybí patrně proto, že autoři v uvedeném cyklu vyčerpali registry procesoru.

Zbytek programového kódu bootsektoru se postará o nahrátí komprimovaného bzImage na fyzickou adresu 0x10000 (64kB od začátku paměti mívá obsazené firmware).

Poznámka: Protože se stále ještě naházíme v 16tibitovém reálném režimu, je nutné využít, eufemisticky řečeno, několika dalších "fíglů". Rutina, která to zařídí, je definována jako bootsect_helper v setup.S. Odkaz na ni je v bootsect.S jako bootsect_kludge (název hovoří za sebe :-)). Důvod, proč je rutina definovaná v setup.S a ne v bootsect.S , kam logicky patří, je ten, že v zavaděči už není dost místa, přičemž programový kód setup.S je už v paměti (byť jinde a musí se kvůli tomu používat mezisegmentový skok).

Setup

Po nahrátí komprimovaného kernelu se dlouhým skokem přeneseme na adresu $SETUPSEG, kde začíná programový kód setup.S. Komplexnost setupu je do značné míry dána tím, že musí zvládnout i další různé případy, jak lze zavést linuxový kernel (bootování ze sítě, loadlin, LILO, starší jádro zImage apod.).

setup.S pak provede zjištění velikosti paměti (pro jistotu jsou implementovány hned tři metody), provede základní nastavení klávesnice, zavolá runtiny definované ve video.S pro detekci a výběr textových videorežimů, zjistí, zda je zapojena PS/2 myš, připojen hardisk a několik další drobností, jako je detekce MCA a základní inicializace APM.

Následuje menší "rošáda": poté, co již nejsou potřeba další služby BIOSu, je celé komprimované jádro bzImage přemístěno z adresy $INITSEG (=0x10000) do dolní části paměti na $SYSSEG (=0x1000). setup.S pak zařídí všechny náležitosti potřebné k přepnutí do chráněného 80386 režimu (zakázání přerušení, zrušení NMI, smysluplné nastavení globální deskriptorové tabulky GDT a podobně). Když je všechno hotovo, setup.S přepne CPU do chráněného režimu, vyprázdní instrukční cache a provede odskok na fyzickou adresu 0x1000, což je programový kód arch/i386/boot/compressed/head.S.

head.S už samozřejmě obsahuje 32bitový assembler. Je potřeba si uvědomit, že fyzická adresa 0x1000 je zároveň adresou, kde bude tabulka stránkování - tedy, že startovací programový kód jádra bude touto tabulkou přepsán.

Poznámka: ve zbytku jádra se mlčky předpokládá, že tabulky stránkování končí na fyzické adrese 0x1000 + 1Mb. Stránka číslo 0 se navíc nechává volná kvůli system managementu některých notebooků, který v této části paměti přistupuje k datům BIOSu.

Takže co dál? Kromě několika nutných úkonů head.S především zavolá C rutinu decompress_kernel() definovanou v arch/i386/boot/compressed/misc.c, která má za úkol rozbalit programový kód vlastního kernelu.

Dekomprese

Tady se nacházíme v dost těžké situaci, v tomto bodě totiž nejsou k dispozici žádné podpůrné funkce. Nezbývá než si nadefinovat alespoň několik základních funkcí jako memcpy(), memset(). Upravená verze dekompresního algoritmu, převzatého z programu gzip(1), navíc potřebuje i malloc() a free() (s tím si ostatně aktuální implementace příliš hlavu neláme, funkce malloc() pouze posunuje (a zarovnává) ukazatel na začátek volného místa, funkce free() nedělá pro jistotu vůbec nic). Potíže ale vyvstávají i s tak primitivními věcmi, jako je vypsání textu na obrazovku - funkce BIOSu už nejsou k dispozici, tak nezbývá než psát přímo do videopaměti.

Poznámka: to je mimochodem zajímavá informace pro všechny, kterým tak vadí úvodní textová hlášení, které Linux vypisuje. Aby se zbavili i takových skvostů jako "Uncompressing Linux..." a "OK, booting the kernel.". Budou muset modifikovat i tuto rutinu, přímo v zavaděči.

Základní informace o zobrazovacím systému už víme z video.S. Pokud byl detekován videorežim č.7, máme k dispozici jen monochromatický režim 80x25 (jedná se o historické adaptéry CGA/MDA/HGA nebo Mono VGA), je zvolena adresa videopaměti 0xB0000 a příslušný port 0x3B4, v opačném případě se předpokládá adaptér kompatibilní s barevnou IBM VGA a nastavena je adresa textové videopaměti 0xB8000 a port 0x3D4. Počet řádků a sloupců na obrazovce se nastaví podle čísla videomódu. Organizace videopamětí je naštěstí pro všechny textové režimy i adaptéry stejná.

Je-li k dispozici dostatek paměti, už nic nestojí v cestě a může se spustit dekompresní algoritmus, tj. funkce makecrc() a gunzip, překládané jako součást arch/i386/boot/compressed/misc.c, ale skutečně definované v lib/inflate.c

Pokud je dekomprese úspěšně dokončena, řízení se vrací do arch/i386/boot/compressed/head.S, kde programový kód už definitivně opustí zavaděč a provede odskok na adresu "opravdového kódu" kernelu, tedy na fyzickou adresu 0x100000.

Základní inicializace jádra

Zavádění máme za sebou, je na čase "nahodit" vlastní jádro. Stále ještě nemáme tolik prostředků, kolik bychom potřebovali, takže ještě chvíli zůstaneme v assembleru a trochu si věci připravíme. Začínáme na fyzické adrese 0x100000, tedy programovém kódu arch/i386/kernel/head.S.

Segmentové registry nastavíme na adresu jádra, inicializujeme stránkovací tabulky (prozatím jen úvodních 8MB pro účely startu jádra, zbytek se vyplní později, podle velikosti fyzické paměti). Pak zapneme stránkování. Bezprostředně potom musíme vyprázdnit celou instrukční frontu nepodmíněným skokem (kdybychom to neudělali, změna adresování by úplně změnila smysl instrukcí v procesorové cache).

Poznámka: modul head.S kernelu je zjevně koncipován tak, že umí provést i (odlišnou) dodatečnou inicializaci pro multiprocesorové systémy. Nicméně na x86 SMP máme zaručeno, že zavádění, dekompresi i následující inicializaci provádí jen boot processor. Proč je tedy head.S udělán, jak je, uvidíme za chvíli.

Boot procesor pak snuluje kompletní BSS (tj. paměť mezi symboly __bss_start a __bss_end, tím je takové chování dáno explicitně, aby zbytečně nedocházelo k nepříjemným překvapením). Protože jsme už v 32bitové inicializaci, je potřeba nastavit znovu tabulků vektoru přerušení. Všech 256 položek se prozatím nastaví obslužnou rutinu ignore_int a, skutečně se přerušení povolí až o něco později. Procesor pak překopíruje 2kB dat z příkazové řádky do nulté stránky (zbylé 2kB ponecháme zatím volné pro přímé boot parametry).

Poznámka: Data pro příkazovou řádku uživatel dává zavaděči ještě v reálném režimu, ale protože jsme si v jednom registru ponechali jejich původní adresu, tak je odtud s stále ještě můžeme dostat.

Po základní detekci typu procesoru a koprocesoru (jen 386, 486 nebo lepší), zbývá jenom správně nastavit EFLAGS, a nahrát deskriptorové tabulky (GDT resp. IDT nahrávají obsah definovaný pod gdt_descr resp. idt_descr, LDT je o něco později nastavena na 0. Pak už můžeme pokračovat inicializacemi v C, konkrétně funkcí start_kernel() definovanou v init/main.c. start_kernel() je architekturově nezávislá, konkrétní kroky jednotlivých akcí jsou samozřejmě pro každou architekturu definovány zvlášť (opět podrobněji rozebíráme jen věci týkající se x86/x86 MP (IA32)).

Startování jádra

Funkce start_kernel() provede následující akce:

  1. Uzamkne kernel globálním zámkem.

    FIXME: Proč nastavuje globální zámek? Do funkce start_kernel by neměl vstoupit jiný než boot procesor (na architektuře x86 se to určitě nestane). Interrupty by měly být také vypnuté. Navíc nedává smysl, aby touto rutinou procházel další procesor.

  2. Vypíše typický linuxový "banner".

    Neboli, vypíše konstantu linux_banner z init/version.c. Ta udává verzi jádra, kdo, kde a kterým kompilerem jádro přeložil. Stejnou informaci lze kdykoliv získat z /proc/version.

    Poznámka: pokud chceme být přesní: jádro sice zavolá pomocnou funkci printk() (jaderný ekvivalent printf()), ale ve skutečnosti se hned na obrazovku nic nevypisuje. printk() pouze naformátuje daný řetězec do statického bufferu log_buf velikosti LOG_BUF_LEN definovaného v linux/kernel/printk.c. Standardní velikost bufferu je 16kB. Zprávy z bufferu log_buf se na obrazovku vypíší až v okamžiku, kdy se standardním způsobem zaregistruje nějaká konzole (console device). To je také důvod, proč lze funkci printk() užít v jádře téměř na libovolném místě, včetně rutiny pro obsluhu přerušení, jak to můžeme vidět i v případě ignore_int. Jen je pak třeba opět obnovit obsahy registrů, které implementace printk() využívá.

  3. Základní architekturově závislá nastavení.

    Téměř všechny funkce pro základní nastavení architektury x86 jsou definovány přímo v souboru arch/i386/kernel/setup.c. A většina z nich má co do činění s inicializací paměti (je dobré si připomenout, že zatím ještě fungujeme jen v 8MB provizoriu). setup_arch() napřed ještě nastaví některé proměnné nutné pro případné bootování z ramdisku, root device a několik dalších. Důležitá je ale především funkce setup_memory_region(), podle které se Linux snaží nastavit kompletní mapu paměti. Následně, ve funkci parse_mem_cmdline(), pak upraví případná přenastavení velikosti nebo oblastí paměti podle parametru mem= příkazové řádky jádra.

    Poznámka: BIOS vrací velmi často zcela nesmyslné hodnoty, co se velikosti fyzické paměti týče. Linux proto hodnotu udávanou BIOSem ignoruje a místo toho nastaví jako velikost fyzické RAM jako maximum všech hodnot, které se mu podařilo zdetekovat. Podobně je tomu i s mapou paměti. Jádro se napřed pokusí "opravit" (sanitize_e820_map()) mapu udanou BIOSem tak, aby se jednotlivé paměťové oblasti nepřekrývaly. Pokud to nejde, používá maximálně zjednodušené schéma - jeden blok 0-640kB dolní paměti, další sekce od 1Mb výše.

    Podle výsledné mapy paměti, nastaví volné rámce stránek dolní paměti pro alokátor (stránky, které jsou využité jen zčásti nechá nedotčené) a nastaví také počáteční a koncové ("brk") body pro data a kód jádra. Nultou stránku ponechá vždy volnou - ta na mnoha počítačích slouží jako speciální stránka BIOSu v nízké paměti. Zpravidla bývá využívána pro operace se SMP, pro System management u laptopů, pro funkce APM (ACPI) a podobně.

    Pokud máme systém konfigurován pro SMP, jádro se pokusí zjistit a inicializovat struktury APIC, tj. provede funkci find_smp_config().

    Poznámka: Z historických důvodů specifikace x86 MP neříká přesně, kde přesně leží konfigurační tabulky pro SMP, pouze udává několik adresových lokací, kde by se mohly nacházet. Zřejmě tak činí ze snahy, co nejvíce zachovat kompatibilitu s dřívějšími systému x86. Každá z uváděných lokací totiž může obsahovat programový kód pro zařízení od jiného výrobce (např. pro inicializační kód pro některé SCSI řadiče) nebo dokonce téměř libovolný kód, pokud uvedenou adresu náhodou použije např. bootloader. Je na jádře, aby takové tabulky dokázalo rozpoznat (funkce smp_scan_config()).

    paging_init() pak už může dokončit mapování paměti (prvních 8MB už mapováno máme). Nultou stránku z mapování vyjme, aby bylo možné v jádře odchytit případně NULL-dereference. Konfiguraci SMP pak překopíruje do normální paměti jádra a inicializuje APIC.

    Pokud je systém konfigurován pro bootování z ramdisku, vyhradí pro něj jádro dostatek místa pomocnou funkcí reserve_bootmem(). Dále vyhradí adresový prostor všem prostředkům ROM (pro video, základní desku a další možná zařízení), oblasti videopaměti (vram_resource) a všem IO prostředkům (standard_io_resources[0..STANDARD_IO_RESOURCES]). Na závěr upraví odkaz na začátek paměti pro správu prostředků PCI a ostatních zařízení mapovaných do paměti (mmaped IO) tak, aby byl na co možná nejnižších adresách (a tedy nevznikaly problémy s přetečením do běžné RAM).

  4. Vypíše a zpracuje parametry předané jádru z příkazové řádky při zavádění.

    Funkce parse_options() jednoduše zpracuje parametry z příkazové řádky, kterými naplní argumenty a evironment (budoucího) threadu init (jako proměnné environmentu se berou všechny předané parametry, které obsahují znak '=').

    Poznámka: výjimku tvoří parametr 'mem=', kde se zjišťuje velikost, případně konkrétní mapa paměti, který je už předem zpracován a interpretován funkcí setup_arch().

    Každý předaný parametr je navíc zároveň subrutinou checksetup() otestován proti symbolům deklarovaným pomocí __setup(). Tj., například __setup("foo", foo_bar) asociuje parametr příkazové řádky jádra "foo" s funkcí jádra foo_bar(). Tomu odpovídají jen parametry používané pro interní účely a threadu init se už dál nepředávají. Podrobnější popis je v souboru linux/Documentation/kernel-parameters.txt

    Normální (default) seznam argumentů a environmentu init je definován následovně:

      static char * argv_init[MAX_INIT_ARGS+2] = { "init", NULL, };
      static char * envp_init[MAX_INIT_ENVS+2] = { "HOME=/", "TERM=linux", NULL, };

    přičemž normální hodnota MAX_INIT_ARGS i MAX_INIT_ENVS je 8.

    Poznámka: zpracovávání příkazové řádky obsahuje ještě jeden workaround. Pokud totiž uživatel používá program LILO jako bootloader a ponechá normální (default) příkazovou řádku, LILO před jádru předsune ještě slovíčko "auto". Při standardním zpracování by pak došlo k nedorozumění, že se má pustit program takového jména. Linux to řeší jednoduše tím, že všechny argumenty, které předcházejí init=, jednoduše ignoruje.

    FIXME: takové chování není zrovna korektní, i když jde především o chybu zavaděče. Každopádně by mělo být daleko lépe zaneseno do dokumentace.

  5. Provede inicializaci traps a IRQ.

    Tyto esenciální inicializace základních výjimek, které dovede procesor poskytnout, provádí funkce trap_init() resp. init_IRQ() definované v arch/i386/kernel/traps.c resp. arch/i386/kernel/i8259.c. Z našeho pohledu jsou zajímavé především dvě volání:

      set_system_gate(SYSCALL_VECTOR,&system_call);

    kde (definováno v include/asm-i386/hw_irq.h)

      #define SYSCALL_VECTOR		0x80

    a system_call je vlastní implementace systémového volání (definovaná v arch/i386/kernel/entry.S, ještě se k ní podrobněji vrátíme). Do tabulky vektorů přerušení je pod číslem 0x80 tedy instalujeme instanci uživatelsky klíčového prvku - systémové volání. Vlastní implementace je samozřejmě kvůli rychlosti v assembleru, stejně jako ostatní handlery, které v této funkci nastavujeme. Druhé slíbené zajímavé volání je:

      cpu_init();

    Ačkoliv jsou už některá data v tomto okamžiku inicializována (připomeňme například inicializaci tabulky vektorů přerušení IDT obslužnou rutinou ignore_int a globální deskriptorové tabulky GDT už v arch/i386/kernel/head.S), funkce cpu_init() tvoří bariéru, při které je úplně reinicializován stav CPU. Konkrétně cpu_init() dělá následující akce:

    1. inicializuje stav CPU,
    2. nahraje tabulky GDT a IDT,
    3. shodí NT (Nested Task) bit,
    4. nastaví a nahraje TSS (Task State Segment) a LDT,
    5. vynuluje ladící registry CPU,
    6. nastaví TS (Task Switched) bit, tj. povolí lazy ukládání registrů při přepnutí kontextu.

    Druhou část inicializací (převážně pro SMP) provádí funkce init_IRQ(). Napřed nastaví oba 8259A řadiče ISA IRQ, pak instaluje obsluhy přerušení pro:

    • všechny nepoužité vektory (implicitní obsluha, většina vektorů pak dostane skutečné obslužné rutiny)
    • IRQ 0 (je potřeba pro inicializaci IO APIC)
    • CPU-to-CPU IPI (Inter-Processor Interrupt) - je potřeba pro reschedule_helper,
    • invalidaci TLB,
    • lokální APIC IPI časovač,
    • IPI vektory výjimek APIC.

    Na závěr nastaví systémové hodiny, aby každých HZ (normálně 100) Hz generovaly přerušení a pokud má procesor externí FPU, nastaví standardní obsluhu IRQ 13 (na SMP je dvojice IRQ 13 resp. IRQ 16 používána pro fast resp. slow IPI).

  6. Inicializuje data potřebná pro plánovač a správu procesů.

    Inicializační funkce sched_init() (definovaná v kernel/sched.c) nejprve určí aktuální CPU, tj. boot procesor, jako výkonný procesor threadu init. Pak vynuluje hashovací tabulku pidhash.

    FIXME: Tabulka pidhash není dynamická, její definice a definice hashovací funkce je následovná:

      #define PIDHASH_SZ (4096 >> 2)
      extern struct task_struct *pidhash[PIDHASH_SZ];
    
      #define pid_hashfn(x)	((((x) >> 8) ^ (x)) & (PIDHASH_SZ - 1))

    což pro při běžném provozu, kdy jsou spuštěny desítky nebo maximálně několik set procesů současně nevadí, problém s rychlostí může ale vznikat, pokud na serveru běží aplikace, která vytváří velký počet threadů (webservery, transakční systémy,...).

    FIXME: pidhash je poměrně velká statická tabulka, proč není umístěna přímo explicitně nulované BSS, nebo proč alespoň není místo cyklu použita funkce memset()?

    Funkce dále inicializuje struktury vektorů pro časovače, nastaví obsluhy třech speciálních bottom halves (viz níže) timer_bh, tqueue_bh, immediate_bh a pro boot idle thread se nastaví lazy přepínání MMU.

  7. Inicializuje mechanismus softirq.

    Inicializace všech mechanizmů softirq je zajištěna funkcí softirq_init() (definice je v souboru kernel/softirq.c).

    Co v Linuxu mechanizmus softirq představuje? Především jde o to, odlehčit standardní obsluze přerušení. V určitých případech je rozumné rozdělit obsluhu přerušení na část, kterou je nutné vykonat hned (přijetí přerušení, update statistik a podobně), a na část práce, kterou lze odložit na později, kdy už jsou přerušení opět povolena (například nějaké další zpracování dat nebo probuzení procesů, které na data z přerušení čekají). Původně, v Linuxu 1.x, byl pro tento účel vyhrazen mechanizmus tzv. bottom halves. Ten měl nicméně poměrně dost nepříjemných omezení, proto byl v průběhu času rozšířen a dále doplněn na dnešní mechanizmy softirq. V Linuxu 2.4 najdeme následující části:

    • bottom halves,
    • task queues,
    • tasklets,
    • softirqs.

    Bottom halves představují dnes už zastaralý způsob, jak danou problematiku v jádře řešit. Přesto na několika místech v jádře dosud přetrvává - patrně se nikomu nechce dál předělávat, co zatím celkem stačí a alespoň bez problémů funguje (i když by to bylo čistší řešení). V systému může být celkem zaregistrováno maximálně 32 bottom halves. Největší omezení ale plyne ze způsobu synchronizace. Bottom halves jsou serializovány globálním spinlockem global_bh_spinlock, tj. i na SMP systému může běžet v jednom okamžiku pouze jedna bottom half. Zamykání global_bh_lock se přesto od zamykání klasického spinlocku, kde CPU čeká v aktivním cyklu, výrazně liší. Pokud global_bh_lock není k dispozici, je provádění příslušné bottom half přeplánováno, takže systém není zbytečně blokován.

    Task queues jsou konzervativním rozšířením bottom halves (někdy se jim také říká "nové bottom halves"). Řeší především menší technické omezení bottom halves, totiž nemožnost zaregistrovat více než jednu obslužnou funkci. Task queues dovolují s pomocí makra queue_task() zaregistrovat libovolný počet obslužných funkcí, které jsou pak jedna po druhé vyvolávány. V linuxovém jádře jsou předdefinovány čtyři základní task queues:

    • tq_timer: obslužné rutiny jsou vyvolávány při každém přerušení časovače a při zavření terminálu. Obsluha přerušení časovače běží v rámci interrupt kontextu, takže úkoly v této frontě nemůžou používat blokující operace.
    • tq_scheduler: obslužné rutiny jsou vyvolávány plánovačem a při zavření terminálu. Neběží v rámci interrupt kontextu, takže mohou používat prakticky libovolné prostředky.
    • tq_immediate: je třída fronty obslužných rutin, které odpovídají původní třídě bottom halves. Vyvolání obslužných rutin je možné řídit makrem mark_bh().
    • tq_disk: je třída specifických obslužných rutin, které mají za úkol vyřizovat požadavky blokových a RAID zařízení. Tato task queue je exportována i pro potřeby dynamických modulů jádra.

    Poznámka: Důvod, proč jsou úkoly zařazené v task queues tq_timer a tq_scheduler vyvolávány i při zavření terminálu (případně podobných příležitostech), je celkem zjevný. Totiž, že provádění určitých akcí je potřeba jen tehdy, pokud ovladač stále ještě může pracovat s konkrétní instancí používaného zařízení, odkládat to na později nemá žádný smysl. Krom toho už nemusejí být k dispozici příslušné datové struktury. Při vyvolání obslužných rutin i v takovémto případě, lze v ovladači takovou situaci včas "podchytit".

    Krom předdefinovaných task queues je možné vyvořit i úplně novou frontu s pomocí makra DECLARE_TASK_QUEUE(). Vyvolání obslužných rutin pak proběhne pokaždé při volání funkce run_task_queue().

    Tasklets jsou multithreadovou analogií bottom halves. Jejich hlavní výhodou je, různé tasklets můžou současně běžet na různých CPU. Po zavolání tasklet_schedule() je garantováno, že tasklet na tomtéž CPU alespoň jednou proběhne, přičemž pokud je už tasklet naplánován, ale provádění jeho kódu ještě nezačalo, je garantováno, že proběhne právě jednou. Pokud už tasklet běží na jiném procesoru (nebo pokud tasklet sám zavolá funkci schedule()), je přeplánován na později. Dobrou vlastností je, že každý tasklet je serializován pro zápis ve všech svých instancích. Pro instance různých taskletů to samozřejmě neplatí. Pokud je taková serializovatelnost potřeba, je nutné použít spinlocky. Většina původních bottom halves byla převedena právě na tasklets.

    Softirqs jsou celkově nejobecnější, používá se přímá hardwarová podpora. Žádná serializace se nedělá, v případě nutnosti si ji musí klientská funkce zajistit sama. Nepoužívají se sdílené proměnné, všechna data jsou lokální danému CPU. Pokud není nutné, aby byla obslužná rutina vyvolávána opravdu velmi často, není potřeba používat softirq. Pro většinu věcí naprosto postačují tasklets.

  8. Zkalibruje a nastaví funkce potřebné pro správu času.

    Funkce time_init() (definovaná v souboru arch/i386/kernel/time.c) napřed z CMOS RTC (Real Time Clock) zjistí aktuální čas. V případě, že CPU disponuje TSC (time stamp counter), máme štěstí, stačí nakalibrovat TSC a můžeme bez problémů počítat čas velmi přesně (většinou dokonce lépe než na mikrosekundy). V případě, že TSC k dispozici není, musíme použít méně přesné (a navíc výrazně pomalejší) řešení.

    Poznámka: Pokud jste šťastným majitelem víceprocesorového systému s procesory i486, z nichž některé procesory TSC mají a jiné ne, máte smůlu - nebude to fungovat. Ostatně, podle autorů jste patrně jediný majitel takového systému, tak si to máte opravit sám.

    CMOS RTC má sice poměrně dobrou přesnost času za delší období, kámen úrazu je rychlost odezvy. RTC zvládne generovat přerušení v rozsahu přibližně 8192Hz - 2Hz, což je ale pro některá zařízení příliš dlouhý interval. Například jenom audio driver pro PC speaker potřebuje přerušení generované přibližně každých 120 mikrosekund. Situace se musí obcházet přes časovač 8253, s pomocí kterého lze dosáhnout lepší přesnosti.

    Na závěr funkce instaluje standardní obsluhu timer_interrupt() (definovanou v souboru arch/i386/kernel/time.c) časovače na IRQ 0 a zaregistruje tuto informaci v procfs. Krom jiného, timer_interrupt() resp. jeho výkonná funkce do_timer_interrupt() volá rutinu do_timer(), která inkrementuje hodnotu časového počítadla jiffies a naplánuje obslužné rutiny zaregistrované v task queue tq_timer. do_timer_interrupt() také přibližně každých 11 minut updatuje hodnotu v RTC.

  9. Předběžně inicializuje konzoli.

    Na inicializace konzole je vlastně příliš brzy, ještě neproběhla nastavení PCI sběrnice, většiny portů a podobně. Je ale vhodné mít alespoň nějaký chybový výstup pro případ, že se stane něco špatně. console_init() (definováno v drivers/char/tty_io.c) proto příliš nespoléhá na pomocné funkce jádra a provede jen základní inicializaci.

    Poznámka: volání console_init() musí následovat až za nastaveními funkcí pro správu času a softirq, protože si registruje vlastní časovač (pomocí funkce init_timer() definované v include/linux/timer.h) a také vlastní tasklet. Kompletní inicializace konzole proběhne až později.

  10. Zapne podporu dynamického nahrávání modulů.

    Pokud je v konfiguraci jádra nastaveno CONFIG_MODULES, zavolá se inicializační funkce init_modules(), která především naplní příslušné tabulky symbolů jádra. Podrobnosti o modulech jádra lze najít v souborech kernel/module.c a kernel/kmod.c.

  11. Zapne podporu profilingu.

    Pokud byla při startu požadována podpora profilování (např. parametrem "profile=" příkazové řádky při zavádění), vyhradí se místo pro příslušné buffery.

  12. Inicializuje se většina subsystému pro cacheování.

    Funkce kmem_cache_init() (definovaná v souboru mm/slab.c) provede inicializaci dat a paměťový odhad pro velikost cache.

  13. Příkazem sti() se povolí harwarová přerušení.

    Tedy se rozběhne i generování přerušení od časovače a v následujícím kroku bude možné provést funkci calibrate_delay().

  14. Nakalibruje, spočte a vypíše hodnotu BogoMIPS.

    Hodnota BogoMIPS přitom určuje, kolik prázdných cyklů za jiffy je boot procesor schopen vykonat.

  15. Provede úplnou inicializaci paměti.

    Funkce mem_init() (definovaná v souboru mm/slab.c) především vynuluje nultou stránku a veškerou volnou paměť z dolní oblasti paměti přidá do totalram_pages. Spočte a vytiskne statistiky o celkové/volné paměti, velikosti programového kódu jádra, paměti, kterou jádro potřebuje pro data jádra atd. Protože SMP jádro bootuje ostatní CPU poměrně pozdě, je potřeba ještě prozatím zachovat některé oblasti nízké paměti kvůli detekcím. Od tohoto okamžiku je možné už normálně používat funkci jádra get_free_pages().

  16. Nastaví softwarové limity pro fork().

    Maximální (softwarový) limit pro maximální počet threadů je nastaven na bezpečnou hodnotu: celkový objem paměti pro všechny datové struktury potřebné v kernelu pro běh threadů nesmí přesáhnout 1/2.

  17. Dokončí inicializaci subsystému cacheování.

    Pomocné jsou funkce opět definovány v mm/slab.c. Od tohoto okamžiku je možné používat i funkci jádra kmalloc().

  18. Inicializuje proc filesystem.

    Inicializuje základní datové struktury, zaregistruje souborový systém procfs. V profs vytvoří soubory obsahující základní informace o systému.

  19. Inicializuje podporu IPC System V.

    Inicializuje standardní prostředky IPC (InterProcess Communication) známé ze Systému V (semafory, zprávy, sdílená paměť) a zaregistruje je v procfs. Zajistí (interní) mount souborového systému shmfs.

  20. Pokusí se detekovat některé hardwarové chyby.

    Zjistí typ a verzi procesoru, případně se pokusí zapnout nějaký workaround, pokud narazí na výraznější chybu hardwarovou chybu procesoru, jako například neošetřený stav při zpracování nekorektních instrukcí začínajících F00F u dřívějších verzí procesoru Pentium.

  21. Ohlásí, že Linux je POSIX kompatibilní.

    Kompatibilitu se standardem POSIX musí vždy testovat certifikovaná firma, v případě Linuxu je jí UNIFIX.

  22. Inicializuje SMP.

    Inicializace x86 SMP je poměrně složitá záležitost. V jádře Linuxu se o většinu akcí stará funkce smp_boot_cpus(). Ta (krom jiného) provede následující:

    • Inicializuje mtrr registry boot procesoru. Překontroluje inicializace APIC a tabulky BIOSu pro obsluhu přerušení. Uloží a vypíše informace dostupné o boot procesoru.

    • Pokud bylo cokoliv špatně, inicializace končí a SMP se vypne. Systém pak pokračuje stejně jako na uniprocesorovém systému.

    • Přepne systém hardwarové obsluhy přerušení z (emulace) PIC do symetrického módu I/O přerušení.

    • V cyklu přes všechny procesory (0 <= apicid <= NR_CPUS, kromě absentujících a boot procesoru) volá funkci do_boot_cpu(). Ta, s pomocí funkce fork_by_hand() pro každý nově bootovaný (cílový) procesor vytvoří idle task a každému procesoru taky "naplánuje" budoucí první úkol:

      	idle->processor = cpu;
      	x86_cpu_to_apicid[cpu] = apicid;
      	x86_apicid_to_cpu[apicid] = cpu;
      	idle->has_cpu = 1; /* we schedule the first task manually */
      	idle->thread.eip = (unsigned long) start_secondary;

      Poznámka: všechny idle tasks mají číslo 0, číslo 1 musí patřit initu. Všechny takto vytvořené projekty jsou ihned vyjmuty z tabulky pidhash a z fronty běžících procesů (plánovač sice zatím neběží, ale datové struktury už připravené máme).

      Do konfiguračních paměťových lokací je zapíše fyzickou adresu rutiny trampoline_base, což je kopie programového kódu trampoline_data definovaného v arch/i386/kernel/trampoline.S. Boot procesor pak vyšle sérii synchronizačních IPI a STARTUP IPI cílovému CPU, což znamená pokyn k nastartování a následnému provedení kódu trampoline_base (rutina se musí kopírovat do nízké paměti, vyžaduje to MP specifikace Intelu):

      	mov	%cs, %ax	# Code and data in the same place
      	mov	%ax, %ds
      
      	mov	$1, %bx		# Flag an SMP trampoline
      	cli			# We should be safe anyway
      
      	movl	$0xA5A5A5A5, trampoline_data - r_base
      				# write marker for master knows we're running
      
      	lidt	idt_48 - r_base	# load idt with 0, 0
      	lgdt	gdt_48 - r_base	# load gdt with whatever is appropriate
      
      	xor	%ax, %ax
      	inc	%ax		# protected mode (PE) bit
      	lmsw	%ax		# into protected mode
      	jmp	flush_instr
      flush_instr:
      	ljmpl	$__KERNEL_CS, $0x00100000
      			# jump to startup_32 in arch/i386/kernel/head.S
      
      idt_48:
      	.word	0			# idt limit = 0
      	.word	0, 0			# idt base = 0L
      
      gdt_48:
      	.word	0x0800			# gdt limit = 2048, 256 GDT entries
      	.long	gdt_table-__PAGE_OFFSET	# gdt base = gdt (first SMP CPU)

      Po nastartování cílového procesoru se na daném CPU opět ocitáme v 16tibitovém reálném módu, tomu samozřejmě musí odpovídat i programový kód trampoline_base(). Cílový procesor po překrytí datového a kódového segmentu zapíše do vlastního programového kódu identifikační konstantu 0xA5A5A5A5, nahraje si provizorní lokální i globální deskriptorovou tabulku a po přepnutí do chráněného režimu provede odskok do již známého programového kódu arch/i386/kernel/head.S. Na rozdíl od boot procesoru, kde byl před skokem ze zavaděče arch/i386/boot/compressed/head.S do arch/i386/kernel/head.S registr %bx explicitně vynulován, cílový procesor jej nastavuje na hodnotu 1. Díky tomu lze pak cílový a boot procesor snadno rozlišit a tedy i zajistit, aby cílový procesor neprováděl všechen inicializační kód v head.S, ale jen potřebné části (neprovádí tedy např. znovu inicializace BSS, která v tomto okamžiku zničila většinu pracně vyrobených programových struktur). Podobně, místo start_kernel() zavolá cílový procesor rutinu inicialize_secondary() definovanou v kernel/smpboot.c,

      	asm volatile(
      		"movl %0,%%esp\n\t"
      		"jmp *%1"
      		:
      		:"r" (current->thread.esp),"r" (current->thread.eip));

      která jednoduše skočí na "další naplánovaný" úkol - tedy na rutinu start_secondary():

             	cpu_init();
      	smp_callin();
      	while (!atomic_read(&smp_commenced))
      		rep_nop();
      	/*
      	 * low-memory mappings have been cleared, flush them from
      	 * the local TLBs too.
      	 */
      	local_flush_tlb();
      
      	return cpu_idle();

      Cílový procesor tedy znovu úplně reinicializujeme pomocí cpu_init() (viz výše) a zavoláme smp_callin(), která provede finální inicializace procesoru a čeká na spinlocku dokud boot procesor nevyrobí všechny idle threads i pro ostatní CPU (plánovač totiž předpokládá, že je na každém CPU vždy co spustit, přinejhorším právě alespoň idle thread).

      Mezitím boot procesor čeká (maximálně však 5 sekund) než cílový procesor nabootuje. Pokud programový kód na adrese trampoline_data - r_base obsahuje něco jiného než konstantu 0xA5A5A5A5, předpokládá neúspěch, vypíše příslušnou chybovou hlášku a procesor v tabulkách vyřadí. V opačném případě pokračuje startováním dalšího procesoru (starty procesorů jsou tedy serializované).

    • Vypíše souhrnnou hodnotu BogoMIPS všech procesorů. Ta je sice k ničemu, protože jediné, co by nás mohlo zajímat jsou individuální hodnoty BogoMIPS pro každý procesor, ale co by to bylo za operační systém, kdybyste svým přátelům nemohli hned po startu ukázat, jak úžasně rychlý počítač mají tu čest vidět.

    • Nastaví a zkalibruje všechny lokální časovače APIC. Pak provede synchronizaci TSC všech nově nastartovaných procesorů s boot procesorem.

    • Uvolní paměť pro inicializační rutiny potřebné k nastartování SMP a vyprázdní TLB všech procesorů.

    V tomto okamžiku jediný procesor, který opět provádí nějaký další programový kód, je boot procesor. Konkrétně je právě za funkcí smp_boot_cpus() v smp_init(). Ostatní, plně inicializované CPU čekají na spinlocku ve funkci smp_callin(). Voláním smp_commence() definitivně odstartujeme víceprocesorový režim běhu systému. Procesory, které čekaly v smp_callin(), budou pokračovat ve svých programech - po opětovném vyprázdnění svých lokálních TLB cache skočí do rutiny cpu_idle(), kde pak už normálně provádějí funkci idle() dokud jim schedule() nepřidělí něco lepšího.

  23. Boot procesor dokončí inicializaci a spustí init thread.

    Funkce rest_init() vytvoří nový kernelový thread init, odemkne globální zámek a nastaví flag, že má být aktuální thread uvnitř volání schedule() přeplánován.

    Poznámka: na SMP nutně potřebujeme napřed dokončit provádění funkcí vně threadu init, protože v opačném případě by mohla nastat i situace, že by v důsledku volání funkce free_initmem() z init threadu mohlo dojít přepsání dat, které ještě potřebuje start_kernel() k úspěšnému dokončení.

    Funkce cpu_idle() pak zůstane jako proces číslo 0 (tzv. idle thread). Pokud je kernel konfigurován pro APM nebo ACPI, provádí kód podle daných specifikací podpory power-saving. V opačném případě provádí instrukci "hlt" a pouští přeplánování procesů schedule().

Init thread

Systém je už v podstatě inicializovaný, všechna CPU už nabootovala a provádějí svoje idle threads, paměť i správa procesů funguje normálně. Kromě konzole, časovačů a několika řadičů nezbytných pro počáteční nastartování systému, jsme ale dosud opomíjeli inicializaci prakticky všech zařízení. Právě teď už dozrál čas to napravit.

Init thread, proces číslo 1, (poté co je naplánován pro některé z CPU) začne provádět funkci init() ze souboru init/main.c. Zamkne jádro globálním zámkem a provede do_basic_setup(), tedy především

Když je základní nastavení systému dokončeno, pokračujeme už rovnou k cíli. Funkce prepare_namespace(), přimontuje filesystem a devfs (pomocí mount_root() resp. mount_devfs_fs()), případně nastartuje kernel thread linuxrc, který umožní zavést root filesystem na ramdisk (mechanismus je podrobně rozebírán v souboru linux/Documentation/initrd.txt).

Jádro pak funkcí free_initmem() uvolní veškerou paměť, která byla označena jako kód/data jen pro inicializace. Na typickém systému je to několik desítek až stovek kilobytů.

Poznámka: k označení takové paměti se používá podpory kompilátoru. Makra __init, __initdata, __init_call a init_setup (pro moduly také __exit a exit_data) expandují na příkazy pro assembler .section ".text.init" resp. .section ".data.init", které zaručí umístění označených dat/kódu do příslušných sekcé ELF souboru vmlinux. Kompletní mapu generuje linker při kompilaci do souboru arch/i386/vmlinux.lds. Funkci free_initmem() pak stačí uvolní všechny stránky mezi adresami __init_begin a __init_end určující hranice obrazu inicializační sekce ve fyzické paměti.

Init thread pak odemkne globální zámek, otevře iniciální konzoli /dev/console a příslušný filedeskriptor dvakrát zduplikuje (dup(2)) tak, aby sloužil jako stdin, stdout a stderr pro program init a jeho potomky. Na závěr spustí program init:

	/*
	 * We try each of these until one succeeds.
	 *
	 * The Bourne shell can be used instead of init if we are 
	 * trying to recover a really broken machine.
	 */

	if (execute_command)   /* user supplied init program */
		execve(execute_command,argv_init,envp_init);
	execve("/sbin/init",argv_init,envp_init);
	execve("/etc/init",argv_init,envp_init);
	execve("/bin/init",argv_init,envp_init);
	execve("/bin/sh",argv_init,envp_init);
	panic("No init found.  Try passing init= option to kernel.");

Voila, máme běžící jádro Linuxu.

Systémová volání

Systémová volání v Linuxu ošetřují dva základní mechanizmy:

Normální (native) linuxové programy používají mechanizmus softwarového přerušení, zatímco mechanismus call gates je především určen pro emulaci chování ostatních unixů (Solaris x86, UnixWare 7 atd.). Call gates jsou navíc úzce spjaty i s dalšími mechanizmy, které mohou určovat (mírně odlišné) chování konkrétních systémových volání. Tím lze prakticky dosáhnout možnosti přímého spuštění x86 programového kódu programů určeného pro jiný unixový systém souběžně s normálními linuxovými aplikacemi. Příslušné definice takových podpůrných funkcí se nacházejí v souboru kernel/exec_domain.c.

Nás ale bude zajímat hlavně první možnost. Z předchozího textu už víme, že po startu systému boot procesor zavolá funkci trap_init(), která (mimo jiné) nastaví tabulku IDT tak, že vektor přerušení odkazuje na adresu vstupního bodu rutiny system_call souboru arch/i386/kernel/entry.S:

ENTRY(system_call)
        pushl %eax			# save orig_eax
        SAVE_ALL
        GET_CURRENT(%ebx)
        cmpl $(NR_syscalls),%eax
        jae badsys
        testb $0x02,tsk_ptrace(%ebx)	# PT_TRACESYS
        jne tracesys
        call *SYMBOL_NAME(sys_call_table)(,%eax,4)
        movl %eax,EAX(%esp)		# save the return value
ENTRY(ret_from_sys_call)
        cli				# need_resched and signals atomic test
        cmpl $0,need_resched(%ebx)
        jne reschedule
        cmpl $0,sigpending(%ebx)
        jne signal_return
restore_all:
      RESTORE_ALL

tracesys:
	movl $-ENOSYS,EAX(%esp)
	call SYMBOL_NAME(syscall_trace)
	movl ORIG_EAX(%esp),%eax
	cmpl $(NR_syscalls),%eax
	jae tracesys_exit
	call *SYMBOL_NAME(sys_call_table)(,%eax,4)
	movl %eax,EAX(%esp)		# save the return value
tracesys_exit:
	call SYMBOL_NAME(syscall_trace)
	jmp ret_from_sys_call
        
reschedule:
	call SYMBOL_NAME(schedule)    # test
	jmp ret_from_sys_call

badsys:
	movl $-ENOSYS,EAX(%esp)
	jmp ret_from_sys_call

Uživatelská aplikace, která chce provést nějaké systémové volání, nastaví do registru %eax příslušné číslo služby, případně předá až dalších 6 argumentů systémového volání v registrech %ebx, %ecx, %edx, %esi, %edi až %ebp (detaily viz například v souboru include/asm-i386/unistd.h) a zavolá softwarové přerušení int 0x80. Návratovou hodnotu očekává v %eax. Pokud potřebujeme předat nebo dostat od systémového volání nějaká větší data, musíme předat ukazatel. Systémové volání pak musí provést obvyklý kolotoč, tj. překopírovat si nejprve všechna potřebná data "k sobě" do adresového prostoru jádra a když pak končí, tak zase uložit do adresového prostoru aplikace. Všechny samozřejmě normálně skrývá standardní C knihovna libc, která všechna systémová volání obalí potřebným kódem tak, aby normální aplikace vůbec nepoznala rozdíl mezi voláním klasické a systémové funkce.

Příprava ani návrat ze systémového volání nejsou tak složité jak se může na první pohled zdát (i když svoji roli hraje také optimalizace kódu). system_call provede následující:

  1. Uloží registry procesoru a segmentové registry %ds a %es pak nastaví na adresový prostor jádra KERNEL_DS.
  2. Zkontroluje, zda je číslo požadované systémové služby platné, tj. zda je menší než počet systémových služeb NR_syscalls. Pokud ne, obsluha systémového volání končí s chybou ENOSYS.
  3. Zjistí, zda je daný task ve stavu trasování (viz ptrace(2)). Pokud ano, pokračuje speciálním zpracováním arch/i386/kernel/ptrace.c ve funkci sycall_trace(). Ta proces pozastaví, pošle rodiči SIGCHLD, vzbudí všechny thready v rodičovské skupině a přeplánuje. Po návratu pošle procesu signál SIGTRAP a pokračuje volání systémové služby.
  4. Zavolá obslužnou rutinu určenou adresou syscall_table + 4 * %eax. Tabulka systémových volání sycall_table je opět definována ve stejném souboru arch/i386/kernel/entry.S. Příslušné obslužné rutiny jsou na Linuxu typicky prefixovány sys_ (případně old_ pro některá systémová volání, která zůstávají pro zachování zpětné kompatibility). Odlišný způsob předání parametrů u systémových volání je umožněn speciální direktivou překladače gcc(1) (viz include/linux/linkage.h).
  5. Po návratu ze systémového volání aplikace atomicky zjistí, zda je potřeba přeplánovat, případně obslouží signály čekající na vyřízení. Tato část je také spojena s obsluhou tasklets a bottom halves.
  6. Nakonec obnoví registry a vrátí řízení aplikaci.

A to už je všechno, víc toho od systémového volání nepotřebujeme,

Synchronizace - synchronizační primitiva a zamykání

Kernelové semafory (MUTEXy)

Semafory

Řeč je o interních kernelových semaforech (tedy semaforech, které se používají v rámci kernelu), ne o semaforech, které jsou k dispozici uživatelským aplikacím prostřednictvím syscallů (ty se liší implementací a sémantikou).

include/asm-i386/semaphore.h:
struct semaphore {
	atomic_t count;
	int sleepers;
	wait_queue_head_t wait;
};

Semafor se deklaruje a zároveň inicializuje makrem DECLARE_MUTEX() anebo DECLARE_MUTEX_LOCKED(). Jako argument je jméno semaforu (jméno proměnné). První makro inicializuje odemknutý semafor (count=1) a druhé zamčený semafor (count=0). Na takto nainicializovaný semafor lze rovnou používat funkce down(), up() apod. - viz dále.

Pokud je potřeba zvlášť semafor deklarovat (např. jako část jiné struktury), potom se semafor deklaruje jako struct semaphore name; a inicializuje pomocí sema_init(name, count);, kde count je iniciální hodnota semaforu. Pokud chcete inicializovat semafor s hodnotou 1 (tedy klasický odemčený mutex), můžete použít pro přehlednost init_MUTEX(); či init_MUTEX_LOCKED() pro hodnotu 0.

include/asm-i386/semaphore.h
static inline void sema_init (struct semaphore *sem, int val)
{
	atomic_set(&sem->count, val);
	sem->sleepers = 0;
	init_waitqueue_head(&sem->wait);
}

static inline void init_MUTEX (struct semaphore *sem)
{
	sema_init(sem, 1);
}

Semafory jsou implementovány dvousměrným počítadlem - count. Proměnná count je dekrementována (její hodnota snižována) pro každý pokus o získání semaforu (hned na začátku funkce down()), proměnná sleepers je počítadlo těchto pokusů resp. indikátor čekajících procesů - viz __down() níže).

Funkce down() je inline assembler funkce, která je optimalizována na průběh (fall trough), při kterém se down() hned povede (provede pouze instrukce decl, js, ret) - tedy případ, kdy je hodnota semaforu větší než nula a proces je puštěn do své kritické sekce. Pokud je výsledkem operace nad semaforem záporná hodnota counteru, proces je nutno zablokovat - to udělá funkce __down() (která je volána prostřednictvím asm handleru __down_failed()).

include/asm-i386/semaphore.h
static inline void down(struct semaphore * sem)
{
	__asm__ __volatile__(
		"# atomic down operation\n\t"
		LOCK "decl %0\n\t"     /* --sem->count */
		"js 2f\n"
		"1:\n"
		".section .text.lock,\"ax\"\n"
		"2:\tcall __down_failed\n\t"
		"jmp 1b\n"
		".previous"
		:"=m" (sem->count)
		:"c" (sem)
		:"memory");
}

funkce __down() přidá proces mezi čekající procesy na semaforu a to na konec fronty (je obsluhována FIFO - viz waitqueues dále). (*) Zjistí, zda aktuální stav semaforu count a sleepers (atomicky zároveň připočte k hodnotě count všechny sleepery mimo sebe) odpovídá situaci, kdy mohou být nějací čekající uspokojeni - pokud ano, odstraní se ze seznamu čekajících a nastaví se jako TASK_RUNNING a spustí i ostatní pomocí wake_up() (ti se dostanou do stavu (*) označeného výše.) Pokud ne, nastaví sleepers na 1 a zavolá schedule() (což má za následek uspání procesu, protože je TASK_UNINTERRUPTIBLE).

funkce up() je o něco jednodušší. zavolá prostě rutinu, která probudí (eventuální) čekatele na semaforu. Probouzení provádí funkce __wake_up_common(), v tomto případě volána s nr_exclusive=1, tedy z fronty čekajících jsou postupně probouzeni (funkcí try_to_wake_up()) všichni (všichni jenž mají nastaveny flagy TASK_UNINTERRUPTIBLE nebo TASK_INTERRUPTIBLE) a buzení skončí, pokud se povedlo probudit někoho s nastaveným WQ_FLAG_EXCLUSIVE flagem, anebo pokud již byli probuzeni všichni z fronty wait. Ve frontě čekajících by měli být nejprve všichni neexkluzivní a až teprve potom ostatní s flagy WQ_FLAG_EXCLUSIVE. Ve skutečnosti by v této frontě měly být pouze procesy s flagem WQ_FLAG_EXCLUSIVE, které se tam dostaly pomocí operací add_wait_queue_exclusive() (viz __down() a __down_interruptible()), takže operace up() probudí právě jeden čekající proces na down(), což je kupodivu i celkem logické :)

(Mechanismus z WQ_FLAG_EXCLUSIVE byl do linuxu přidán proto, aby nevznikal problém typu "thundering herd". Například pokud na počítači běží webserver a na událost čeká 100 instancí httpd, událost přijde a je probuzeno všech 100 procesů, ti se poperou o zámek, jeden proces uspěje a ostatní jdou zase spát. Je to neefektivní a velice to snižuje výkonnost serveru při rostoucí zátěži a množství httpd procesů. Proto byl do řady 2.3/2.4 přidán mechanismus EXCLUSIVE (nejrpve pomocí TASK_EXCLUSIVE, později efektivněji a jednodušeji úpravou waitqueues), kdy lze tento problém řešit buzením pouze jednoho příslušného procesu.)

Přerušitelné semafory

pokud to jde, používejte spíše přerušitelné semafory, tedy místo obyčejných operací up()/down() používejte down_interruptible()/up(), u které down_interruptible() vrací hodnotu výsledku operace: pokud je návratová hodnota nenulová, operace byla přerušena. ostatní sémantika je stejná. implemtace těchto semaforů se de facto liší jen v testování podmínky if (signal_pending(current)) v cyklu před testováním rovnováhy mezi čekajícími procesy a hodnotou semaforu. operace tedy může navíc skončit, pokud čeká signál k obsloužení - tento případ je nutno ošetřit testováním návratové hodnoty - semafor v této situaci nevlastníme!

Neblokující semafory

často jsou potřeba semaforové operace, které neblokují. například uvnitř interruptu (interrupt context) nesmíte volat rutiny, které mohou proces uspat. fuknce down() a down_interruptible() samozřejmě blokovat můžou a proto je k dispozici down_trylock(). podle její návratové hodnoty poznáme, zda se operace down() povedla nebo ne. úspěch je indikován nulovou návratovou hodnotou a neúspěch nenulovou. (v každém případě je nejprve hodnota semaforu snížena, což se v případě neúspěchu napraví ve funkci __down_trylock(), ale to je jen implementační detail.)

Read/Write semafory

Linux kernel obsahuje i read/write semafory, tedy semafory, kterými lze implementovat problém přístupu čtenářů a písařů. K datům můžeme pustit několik čtenářů zároveň, anebo jednoho písaře.

include/asm-i386/rwsem.h:
struct rw_semaphore {
	signed long		count;
	spinlock_t		wait_lock;
	struct list_head	wait_list;
};

Kritické sekce čtenářů se potom ohraničují pomocí down_read() a up_read(). Kritické sekce písařů obdobně down_write() a up_read(). Obsluhování je plně FIFO - když na zámek čeká jeden zapisovatel, další čtenáře už k zámku nepouští (teoreticky tak snižuje výkon a stupeň paralelizace systému, na druhou stranu se nemusí řešit problém s vyhladověním písařů). V operacích up(): pokud je zámek volný, tak se podívá na prvního čekajícího ve frontě - pokud je to písař, probudí jen jeho; pokud je to čtenář, probudí všechny čtenáře ze začátku fronty až po prvního písaře. (teoreticky by se dali probudit všichni čtenáři i za písaři, ale i zde by potom mohl nastat problém s hladovějícími písaři, a proto se to takto v linuxu nedělá).

Read/write semafory nemají své neblokující a přerušitelné verze.

Spinlocky

Spinlocky jsou tradičním zamykacím mechanismem v kernelu. Na rozdíl od semaforů implementují aktivní čekání (busy waiting), tedy jejich smysl je především na multiprocesorových architekturách (na jednoprocesorovém stroji nemá většinou aktivní čekání velký smysl, vyjma komunikace s drivery apod., což ovšem není v linuxovém kernelu řešeno pomocí spinlocků). Díky tomu, že během čekání se neprovádí na daném procesoru scheduling, pokud nastane očekávaná událost v krátké době, ušetří se tak mnoho instrukcí. Spinlocky mají tedy smysl, pokud se dá vpuštění do kritické sekce očekávat během velice krátké d oby (cca 2 context switche).

Pokud je kernel zkompilován bez podpory CONFIG_SMP (podpora symetrického multiprocessingu), spinlocky prostě neexistují - nedávaly by smysl. Následující část se tedy týká multiprocesorové synchronizace pomocí spinlocků.

Základní (vanilla) spinlocky

není zde moc co řešit:

include/asm-i386/spinlock.h
typedef struct {
	volatile unsigned int lock;
} spinlock_t;

#define spin_lock_init(x)	do { *(x) = SPIN_LOCK_UNLOCKED; } while(0)
(Tento trik s #define ... do { ... } while(0) se mimochodem používá proto, aby delší makra šly použít i jako samotné větve if-then-else, jinak by programátor musel vždy řešit, zda makro uzavírat do složených závorek a měnit tento zápis, pokud makro změní... viz Why do a lot of #defines in the kernel use do { ... } while(0)?)
static inline void spin_lock(spinlock_t *lock)
{
	__asm__ __volatile__(
		spin_lock_string
		:"=m" (lock->lock) : : "memory");
}

static inline void spin_unlock(spinlock_t *lock)
{
	__asm__ __volatile__(
		spin_unlock_string
		:"=m" (lock->lock) : : "memory");
}

Dále ještě existuje funkce spin_trylock(), na které program aktivně nečeká - podle návratové hodnoty se pozná, zda se zamknutí podařilo - 0 znamená neúspěch, ostatní hodnoty úspěch.

Funkce spin_lock() a spin_unlock() se smí používat jen v situacích, kdy je jisté, že nenastanou interrupty (tedy kde interrupty jsou disabled), anebo pokud je jisté, že nevznikne časově závislá chyba s obsluhou přerušení. jednoduše řečeno, pokud se přistupuje k datům přes spinlocky a interrupt handlery také skrze stejné spinlocky, tyto funkce se nesmí používat - pokud by v kritické sekci nastal interrupt, handler by čekal na spin_lock() donekonečna. Funkce spin_lock() a spin_unlock() se smí používat také v taskletech a bottom halves.

IRQ verze spinlocků

spin_lock_irq() a spin_unlock_irq(): tyto funkce při zakážou po dobu kritické sekce interrupty a při unlock je zase povolí. Požívají se tedy jen v situacích/kontextech, kdy je jistota, že interrupty jsou povoleny - například uvnitř syscallů, tedy v uživatelském kontextu, pokud by s námi o data mohly zápasit interrupty.

silnější variantou jsou spin_lock_irqsave() a spin_unlock_irqrestore(): použijí se tam, kde není předem zřejmé, zda budou interrupty povoleny či zakázany, ale kde víme, že interrupty přistupují k našim datům a je nutno je zakázat, aby neporušily konzistenci dat.

IRQ spinlocky se používají především v případě, kdy sdílíte data mezi hardwareouvým a softwareovým interruptem (softirq, tasklet, bottom halves), aby v době vykonávání softirq/bh/taskletu nemohl přijít hardwareový interrupt a data uvést do nekonzistentní podoby. Samotný hardwareový interrupt je rovněž třeba chránit IRQ spinlockem, aby se zaručilo, že stejný interrupt nebude vyvolán na jiném procesoru.

BH verze spinlocků

spin_lock_bh() a spin_unlock_bh(): tyto funkce se postarají o zakázání běhu bottom halves a taskletů, slouží proto k použití, pokud uživatelský kontext závodí s bh nebo tasklety o přístup na stejná data.

Implementace je prozaická:
include/linux/spinlock.h
#define spin_lock_irqsave(lock, flags)		do { local_irq_save(flags);       spin_lock(lock); } while (0)
#define spin_lock_irq(lock)			do { local_irq_disable();         spin_lock(lock); } while (0)
#define spin_lock_bh(lock)			do { local_bh_disable();          spin_lock(lock); } while (0)

#define spin_unlock_irqrestore(lock, flags)	do { spin_unlock(lock);  local_irq_restore(flags); } while (0)
#define spin_unlock_irq(lock)			do { spin_unlock(lock);  local_irq_enable();       } while (0)
#define spin_unlock_bh(lock)			do { spin_unlock(lock);  local_bh_enable();        } while (0)

Read/Write spinlocky

include/asm-i386/spinlock.h
typedef struct {
	volatile unsigned int lock;
} rwlock_t;

Read/write spinlocky jsou určeny pro použití v případech, kdy chcete umožnit přístup několika čtenářům simultánně najednou. Čtenáři potom kritickou sekci ohraničí funkcí read_lock() a read_unlock() - písaři obdobně write_lock() a write_unlock() (existuje i nečekající verze write_trylock(), výsledek opět dle návratové hodnoty).

Vše řečené výše o spinlock platí i o r/w spinlocích. S tím rozdílem, že je běžné mít čtenáře v obsluze interruptů, ale ne žádné zapisovatele. Potom je bezpečné používat irq-save write-locky (write_lock_irq()) a proti nim libovolné read locky. Jinak zde opět existují BH i IRQ verze obou r/w operací, platí zde stejná pravidla, jako pro normální spinlocky.

Momentální implementace read/write spinlocků nemá FIFO sémantiku jako r/w semafory. Pokud na spinlocku čeká proces z požadavkem na zápis, zámek je přidělován i dalším zájemcům o čtení - teprve až když se všichni staří i noví čtenáři zámku vzdají, dostane ho písař. Jedním z důvodů je i ten, že čtenáři si obvykle spinlock je na velice krátkou dobu a že by bylo neefektivní, kdyby museli čekat. Riziko, že dojde k vyhladovění čtenáře neustávajícím množstvím příchozích čtenářů je v praxi (vzhledem k povaze využití r/w spinlocků rámci kernelu) velmi nepravděpodobné.

Big Reader spinlocky

Tyto r/w spinlocky jsou silně optimalizovány na rychlost. Optimalizovány jsou především read locky, které jsou zvýhodněny tím, že nepotřebují k získání zámku spolupracovat s ostatními procesory. To musí dělat až write lock, což ho značně zpomalí. Z toho vyplývá, že tyto locky se používají jen tam, kde je převaha read locků na write locky zdrcující a zoptimalizování read locku na úkor write locku se vyplatí. (jejich paměťové nároky jsou také větší oproti ostatním typům spinlocků.) Sémanticky jsou shodné s předchozími r/w spinlocky.

lib/brlock.c
brlock_read_lock_t __brlock_array[NR_CPUS][__BR_IDX_MAX] =
   { [0 ... NR_CPUS-1] = { [0 ... __BR_IDX_MAX-1] = RW_LOCK_UNLOCKED } };

void __br_write_lock (enum brlock_indices idx)
{
	int i;

	for (i = 0; i < smp_num_cpus; i++)
		write_lock(&__brlock_array[cpu_logical_map(i)][idx]);
}

void __br_write_unlock (enum brlock_indices idx)
{
	int i;

	for (i = 0; i < smp_num_cpus; i++)
		write_unlock(&__brlock_array[cpu_logical_map(i)][idx]);
}

Počet Big Reader spinlocků v systému je omezený - momentálně jsou tam pouze dva. Jeden slouží k implementaci global irq na procesoru sparc64 a druhý je použit pro networking. V ostatních oblastech kernelu je doporučeno se BR lockům vyhýbat a do systému je nepřidávat/nepoužívat.

V kritické sekci ohraničené spinlocky se nesmí volat operace, které mohou blokovat:
copy_from_user(), copy_to_user(), get_user(), put_user(), kmalloc(GFP_KERNEL), down_interruptible(), down().
Oproti tomu funkce down_trylock(), printk() používat lze.

Typický příklad použití spinlocku

Spinlocky se běžně používají pro synchronizaci přístupu k datům sdíleným mezi uživatelským kontextem a obsluhou přerušení:

spinlock_t my_lock = SPIN_LOCK_UNLOCKED;

my_ioctl()
{
	spin_lock_irq(&my_lock);
	/* critical section */
	spin_unlock_irq(&my_lock);
}

my_irq_handler()
{
	spin_lock(&my_lock);
	/* critical section */
	spin_unlock(&my_lock);
}

Zdroje

Valid HTML 4.01!