Questo HOWTO cerca di descrivere come le componenti del Kernel di Linux funzionano, quali sono le funzioni principali e le strutture dati utilizzate e come ''gira il tutto''. Puoi trovare l'ultima versione di questo documento su http://www.bertolinux.com Se hai dei suggerimento per migliorare questo documento, manda un'email all'indirizzo: berto@bertolinux.com. Il codice descritto nel documento si riferisce al Kernel Linux versione 2.4.x, l'ultima versione stabile al momento della compilazione dell'HOWTO.
Copyright (C) 2000,2001,2002 Roberto Arcomano. This document is free; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This document is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You can get a copy of the GNU GPL here
Sei libero di tradurre questo documento, devi soltanto rispettare 2 regole:
Attenzione! Non bisogna tradurre il file TXT o HTML, bensi' il file LYX, cosicche' sia possibile convertirlo negli altri formati (TXT, HTML, RIFF, ecc.): puoi utilizzare l'applicativo LyX scaricabile da http://www.lyx.org.
Non c'e' bisogno di chiedermi l'autorizzazione! E' sufficiente comunicarmelo.
Grazie per la tua traduzione!
Ringraziamenti a Fatamorgana Computers per i mezzi hardware offerti e la possibilita' di sperimentazione.
Quando descriviamo una funzione, scriviamo:
"nome_funzione [ percorso . estensione ]"
Ad esempio:
"schedule [kernel/sched.c]"
ci dice che stiamo parlando della funzione
"schedule" definita nel file
[ kernel/sched.c ]
Nota: Il percorso di riferimento e' la directory dei sorgenti del Kernel ''/usr/src/linux''.
L'indendazione nel codice sorgente del documento e' di 3 caratteri.
Nel documento verranno utilizzate le "InterCallings Analysis "(ICA) (analisi delle reciproche chiamate) per vedere (utilizzando anche l'indentazione) come le funzioni del Kernel si chiamano l'un l'altra.
Ad esempio, la funzione ''sleep_on'' e' descritto di seguito:
|sleep_on
|init_waitqueue_entry --
|__add_wait_queue | Accodamento della richiesta
|list_add |
|__list_add --
|schedule --- In attesa di esecuzione
|__remove_wait_queue --
|list_del | Disaccodamento richiesta
|__list_del --
sleep_on ICA
L'ICA indentata e' seguita dal percorso delle funzioni descritte:
Nota: Se il percorso non cambia non verra' piu' specificato nelle righe seguenti.
In una ICA una linea come la seguente
funzione1 -> funzione2
significa che la < funzione1 > e' un generico puntatore a funzione che, in questo caso, punta a < function2 >.
Quando scriviamo:
funzione:
significa che < funzione > non e' una vera funzione, bensi' un'etichetta assembler.
A volte verra' riportato del codice ''C'' o pseudo codice al posto di linee ''assembler'' o di codice '' non strutturato'' per poter chiarire l'esposizione.
I vantaggi nell'utilizzo delle ICA (InterCallings Analysis) sono molti:
Come tutti i modelli teorici, viene semplificata la realta' sorvolando alcuni dettagli, come il vero codice sorgente e i casi eccezionali.
Il Kernel e' il cuore di ogni sistema operativo: e' quel software che permette agli utenti di condividere ed utilizzare al meglio le risorse del sistema di elaborazione.
Il Kernel puo' essere visto come il principale software del Sistema Operativo che potrebbe anche includere la gestione grafica: ad esempio sotto Linux (come nella maggiorparte dei sistemi Unix-like), l'ambiente XWindow non fa parte del Kernel di Linux perche' gestisce soltanto operazioni grafiche (grazie ad istruzioni I/O eseguite in User Mode e accesso diretto alla scheda video). Com'e' noto, invece, gli ambienti Windows (Win9x, WinME, WinNT, Win2K, WinXP, e cosi' via) sono un mix tra ambiente grafico e kernel.
Molti anni fa, quando i computers erano grandi come stanze, gli utenti lanciavano le loro applicazioni con molta difficolta' e, a volte, il sistema di elaborazione andava in crash.
Per evitare tale crash si e' pensato di introdurre 2 modi di funzionamento (ancora presenti nei nuovi microprocessori):
| Applicazioni /|\
| ______________ |
| | User Mode | |
| ______________ |
| | |
Dettaglio | _______ _______ | Astrazione
Implementazione| | Kernel Mode | |
| _______________ |
| | |
| | |
| | |
\|/ Hardware |
Kernel Mode impedisce alle applicazioni User Mode di danneggiare il sistema o le sue caratteristiche.
I moderni microprocessori implementano in hardware almeno 2 stati differenti. Ad esempio l'architettura Intel possiede 4 stati che determinano il PL (Privilege Level) permettendo quindi di avere gli stati 0,1,2,3 , con 0 usato in modo Kernel.
I sistemi Unix-like richiedono soltanto 2 livelli di privilegio e utilizzeremo questo come punto di riferimento.
Una volta capito che ci sono 2 modi operativi differenti, dobbiamo vedere quando avviene il ''salto'' tra uno e l'altro:
Le System Calls sono come delle normali funzioni, soltanto che operano in Kernel Mode per eseguire operazioni sull'OS (in effetti le System Calls sono parte integrante dell'OS).
Una System Call puo' essere chiamata quando:
| |
------->| System Call i | (Accesso ai Devices)
| | | | [sys_read()] |
| ... | | | |
| system_call(i) |-------- | |
| [read()] | | |
| ... | | |
| system_call(j) |-------- | |
| [get_pid()] | | | |
| ... | ------->| System Call j | (Accesso alle strutture dati del kernel)
| | | [sys_getpid()]|
| |
USER MODE KERNEL MODE
Funzionamento System Calls Unix
Le System Calls teoricamente sono l'unica interfaccia disponibile in User Mode per accedere alle risorse hardware. In realta' esiste la SC ''ioperm'' che permette ad un Task di accedere direttamente ad un device (benche' senza IRQs).
NOTA: Non tutte le funzioni di libreria ''C'' sono delle system call, solo un piccolo sottoinsieme di esse.
Segue una lista delle System Calls presenti nel Linux Kernel 2.4.17, ricavabili dal file [ arch/i386/kernel/entry.S ]
.long SYMBOL_NAME(sys_ni_syscall) /* 0 - old "setup()" system call*/
.long SYMBOL_NAME(sys_exit)
.long SYMBOL_NAME(sys_fork)
.long SYMBOL_NAME(sys_read)
.long SYMBOL_NAME(sys_write)
.long SYMBOL_NAME(sys_open) /* 5 */
.long SYMBOL_NAME(sys_close)
.long SYMBOL_NAME(sys_waitpid)
.long SYMBOL_NAME(sys_creat)
.long SYMBOL_NAME(sys_link)
.long SYMBOL_NAME(sys_unlink) /* 10 */
.long SYMBOL_NAME(sys_execve)
.long SYMBOL_NAME(sys_chdir)
.long SYMBOL_NAME(sys_time)
.long SYMBOL_NAME(sys_mknod)
.long SYMBOL_NAME(sys_chmod) /* 15 */
.long SYMBOL_NAME(sys_lchown16)
.long SYMBOL_NAME(sys_ni_syscall) /* old break syscall holder */
.long SYMBOL_NAME(sys_stat)
.long SYMBOL_NAME(sys_lseek)
.long SYMBOL_NAME(sys_getpid) /* 20 */
.long SYMBOL_NAME(sys_mount)
.long SYMBOL_NAME(sys_oldumount)
.long SYMBOL_NAME(sys_setuid16)
.long SYMBOL_NAME(sys_getuid16)
.long SYMBOL_NAME(sys_stime) /* 25 */
.long SYMBOL_NAME(sys_ptrace)
.long SYMBOL_NAME(sys_alarm)
.long SYMBOL_NAME(sys_fstat)
.long SYMBOL_NAME(sys_pause)
.long SYMBOL_NAME(sys_utime) /* 30 */
.long SYMBOL_NAME(sys_ni_syscall) /* old stty syscall holder */
.long SYMBOL_NAME(sys_ni_syscall) /* old gtty syscall holder */
.long SYMBOL_NAME(sys_access)
.long SYMBOL_NAME(sys_nice)
.long SYMBOL_NAME(sys_ni_syscall) /* 35 */ /* old ftime syscall holder */
.long SYMBOL_NAME(sys_sync)
.long SYMBOL_NAME(sys_kill)
.long SYMBOL_NAME(sys_rename)
.long SYMBOL_NAME(sys_mkdir)
.long SYMBOL_NAME(sys_rmdir) /* 40 */
.long SYMBOL_NAME(sys_dup)
.long SYMBOL_NAME(sys_pipe)
.long SYMBOL_NAME(sys_times)
.long SYMBOL_NAME(sys_ni_syscall) /* old prof syscall holder */
.long SYMBOL_NAME(sys_brk) /* 45 */
.long SYMBOL_NAME(sys_setgid16)
.long SYMBOL_NAME(sys_getgid16)
.long SYMBOL_NAME(sys_signal)
.long SYMBOL_NAME(sys_geteuid16)
.long SYMBOL_NAME(sys_getegid16) /* 50 */
.long SYMBOL_NAME(sys_acct)
.long SYMBOL_NAME(sys_umount) /* recycled never used phys() */
.long SYMBOL_NAME(sys_ni_syscall) /* old lock syscall holder */
.long SYMBOL_NAME(sys_ioctl)
.long SYMBOL_NAME(sys_fcntl) /* 55 */
.long SYMBOL_NAME(sys_ni_syscall) /* old mpx syscall holder */
.long SYMBOL_NAME(sys_setpgid)
.long SYMBOL_NAME(sys_ni_syscall) /* old ulimit syscall holder */
.long SYMBOL_NAME(sys_olduname)
.long SYMBOL_NAME(sys_umask) /* 60 */
.long SYMBOL_NAME(sys_chroot)
.long SYMBOL_NAME(sys_ustat)
.long SYMBOL_NAME(sys_dup2)
.long SYMBOL_NAME(sys_getppid)
.long SYMBOL_NAME(sys_getpgrp) /* 65 */
.long SYMBOL_NAME(sys_setsid)
.long SYMBOL_NAME(sys_sigaction)
.long SYMBOL_NAME(sys_sgetmask)
.long SYMBOL_NAME(sys_ssetmask)
.long SYMBOL_NAME(sys_setreuid16) /* 70 */
.long SYMBOL_NAME(sys_setregid16)
.long SYMBOL_NAME(sys_sigsuspend)
.long SYMBOL_NAME(sys_sigpending)
.long SYMBOL_NAME(sys_sethostname)
.long SYMBOL_NAME(sys_setrlimit) /* 75 */
.long SYMBOL_NAME(sys_old_getrlimit)
.long SYMBOL_NAME(sys_getrusage)
.long SYMBOL_NAME(sys_gettimeofday)
.long SYMBOL_NAME(sys_settimeofday)
.long SYMBOL_NAME(sys_getgroups16) /* 80 */
.long SYMBOL_NAME(sys_setgroups16)
.long SYMBOL_NAME(old_select)
.long SYMBOL_NAME(sys_symlink)
.long SYMBOL_NAME(sys_lstat)
.long SYMBOL_NAME(sys_readlink) /* 85 */
.long SYMBOL_NAME(sys_uselib)
.long SYMBOL_NAME(sys_swapon)
.long SYMBOL_NAME(sys_reboot)
.long SYMBOL_NAME(old_readdir)
.long SYMBOL_NAME(old_mmap) /* 90 */
.long SYMBOL_NAME(sys_munmap)
.long SYMBOL_NAME(sys_truncate)
.long SYMBOL_NAME(sys_ftruncate)
.long SYMBOL_NAME(sys_fchmod)
.long SYMBOL_NAME(sys_fchown16) /* 95 */
.long SYMBOL_NAME(sys_getpriority)
.long SYMBOL_NAME(sys_setpriority)
.long SYMBOL_NAME(sys_ni_syscall) /* old profil syscall holder */
.long SYMBOL_NAME(sys_statfs)
.long SYMBOL_NAME(sys_fstatfs) /* 100 */
.long SYMBOL_NAME(sys_ioperm)
.long SYMBOL_NAME(sys_socketcall)
.long SYMBOL_NAME(sys_syslog)
.long SYMBOL_NAME(sys_setitimer)
.long SYMBOL_NAME(sys_getitimer) /* 105 */
.long SYMBOL_NAME(sys_newstat)
.long SYMBOL_NAME(sys_newlstat)
.long SYMBOL_NAME(sys_newfstat)
.long SYMBOL_NAME(sys_uname)
.long SYMBOL_NAME(sys_iopl) /* 110 */
.long SYMBOL_NAME(sys_vhangup)
.long SYMBOL_NAME(sys_ni_syscall) /* old "idle" system call */
.long SYMBOL_NAME(sys_vm86old)
.long SYMBOL_NAME(sys_wait4)
.long SYMBOL_NAME(sys_swapoff) /* 115 */
.long SYMBOL_NAME(sys_sysinfo)
.long SYMBOL_NAME(sys_ipc)
.long SYMBOL_NAME(sys_fsync)
.long SYMBOL_NAME(sys_sigreturn)
.long SYMBOL_NAME(sys_clone) /* 120 */
.long SYMBOL_NAME(sys_setdomainname)
.long SYMBOL_NAME(sys_newuname)
.long SYMBOL_NAME(sys_modify_ldt)
.long SYMBOL_NAME(sys_adjtimex)
.long SYMBOL_NAME(sys_mprotect) /* 125 */
.long SYMBOL_NAME(sys_sigprocmask)
.long SYMBOL_NAME(sys_create_module)
.long SYMBOL_NAME(sys_init_module)
.long SYMBOL_NAME(sys_delete_module)
.long SYMBOL_NAME(sys_get_kernel_syms) /* 130 */
.long SYMBOL_NAME(sys_quotactl)
.long SYMBOL_NAME(sys_getpgid)
.long SYMBOL_NAME(sys_fchdir)
.long SYMBOL_NAME(sys_bdflush)
.long SYMBOL_NAME(sys_sysfs) /* 135 */
.long SYMBOL_NAME(sys_personality)
.long SYMBOL_NAME(sys_ni_syscall) /* for afs_syscall */
.long SYMBOL_NAME(sys_setfsuid16)
.long SYMBOL_NAME(sys_setfsgid16)
.long SYMBOL_NAME(sys_llseek) /* 140 */
.long SYMBOL_NAME(sys_getdents)
.long SYMBOL_NAME(sys_select)
.long SYMBOL_NAME(sys_flock)
.long SYMBOL_NAME(sys_msync)
.long SYMBOL_NAME(sys_readv) /* 145 */
.long SYMBOL_NAME(sys_writev)
.long SYMBOL_NAME(sys_getsid)
.long SYMBOL_NAME(sys_fdatasync)
.long SYMBOL_NAME(sys_sysctl)
.long SYMBOL_NAME(sys_mlock) /* 150 */
.long SYMBOL_NAME(sys_munlock)
.long SYMBOL_NAME(sys_mlockall)
.long SYMBOL_NAME(sys_munlockall)
.long SYMBOL_NAME(sys_sched_setparam)
.long SYMBOL_NAME(sys_sched_getparam) /* 155 */
.long SYMBOL_NAME(sys_sched_setscheduler)
.long SYMBOL_NAME(sys_sched_getscheduler)
.long SYMBOL_NAME(sys_sched_yield)
.long SYMBOL_NAME(sys_sched_get_priority_max)
.long SYMBOL_NAME(sys_sched_get_priority_min) /* 160 */
.long SYMBOL_NAME(sys_sched_rr_get_interval)
.long SYMBOL_NAME(sys_nanosleep)
.long SYMBOL_NAME(sys_mremap)
.long SYMBOL_NAME(sys_setresuid16)
.long SYMBOL_NAME(sys_getresuid16) /* 165 */
.long SYMBOL_NAME(sys_vm86)
.long SYMBOL_NAME(sys_query_module)
.long SYMBOL_NAME(sys_poll)
.long SYMBOL_NAME(sys_nfsservctl)
.long SYMBOL_NAME(sys_setresgid16) /* 170 */
.long SYMBOL_NAME(sys_getresgid16)
.long SYMBOL_NAME(sys_prctl)
.long SYMBOL_NAME(sys_rt_sigreturn)
.long SYMBOL_NAME(sys_rt_sigaction)
.long SYMBOL_NAME(sys_rt_sigprocmask) /* 175 */
.long SYMBOL_NAME(sys_rt_sigpending)
.long SYMBOL_NAME(sys_rt_sigtimedwait)
.long SYMBOL_NAME(sys_rt_sigqueueinfo)
.long SYMBOL_NAME(sys_rt_sigsuspend)
.long SYMBOL_NAME(sys_pread) /* 180 */
.long SYMBOL_NAME(sys_pwrite)
.long SYMBOL_NAME(sys_chown16)
.long SYMBOL_NAME(sys_getcwd)
.long SYMBOL_NAME(sys_capget)
.long SYMBOL_NAME(sys_capset) /* 185 */
.long SYMBOL_NAME(sys_sigaltstack)
.long SYMBOL_NAME(sys_sendfile)
.long SYMBOL_NAME(sys_ni_syscall) /* streams1 */
.long SYMBOL_NAME(sys_ni_syscall) /* streams2 */
.long SYMBOL_NAME(sys_vfork) /* 190 */
.long SYMBOL_NAME(sys_getrlimit)
.long SYMBOL_NAME(sys_mmap2)
.long SYMBOL_NAME(sys_truncate64)
.long SYMBOL_NAME(sys_ftruncate64)
.long SYMBOL_NAME(sys_stat64) /* 195 */
.long SYMBOL_NAME(sys_lstat64)
.long SYMBOL_NAME(sys_fstat64)
.long SYMBOL_NAME(sys_lchown)
.long SYMBOL_NAME(sys_getuid)
.long SYMBOL_NAME(sys_getgid) /* 200 */
.long SYMBOL_NAME(sys_geteuid)
.long SYMBOL_NAME(sys_getegid)
.long SYMBOL_NAME(sys_setreuid)
.long SYMBOL_NAME(sys_setregid)
.long SYMBOL_NAME(sys_getgroups) /* 205 */
.long SYMBOL_NAME(sys_setgroups)
.long SYMBOL_NAME(sys_fchown)
.long SYMBOL_NAME(sys_setresuid)
.long SYMBOL_NAME(sys_getresuid)
.long SYMBOL_NAME(sys_setresgid) /* 210 */
.long SYMBOL_NAME(sys_getresgid)
.long SYMBOL_NAME(sys_chown)
.long SYMBOL_NAME(sys_setuid)
.long SYMBOL_NAME(sys_setgid)
.long SYMBOL_NAME(sys_setfsuid) /* 215 */
.long SYMBOL_NAME(sys_setfsgid)
.long SYMBOL_NAME(sys_pivot_root)
.long SYMBOL_NAME(sys_mincore)
.long SYMBOL_NAME(sys_madvise)
.long SYMBOL_NAME(sys_getdents64) /* 220 */
.long SYMBOL_NAME(sys_fcntl64)
.long SYMBOL_NAME(sys_ni_syscall) /* reserved for TUX */
.long SYMBOL_NAME(sys_ni_syscall) /* Reserved for Security */
.long SYMBOL_NAME(sys_gettid)
.long SYMBOL_NAME(sys_readahead) /* 225 */
Quando arriva un IRQ, il task in esecuzione viene interrotto per far eseguire un gestore IRQ.
Dopo l'esecuzione di tale gestore il controllo ritorna tranquillamente al processo che non si accorge di nulla.
Task in esecuzione
|-----------| (3)
ESECUZIONE | | | [stop esecuzione] IRQ Handler
NORMALE (1) | | | ------------->|---------|
| \|/ | | |gestisce |
IRQ (2)---->| .. |-----> | alcuni |
| | |<----- | dati |
RITORNO (6) | | | | | ..(4). |
ALLA NORMALE | \|/ | <-------------|_________|
ESECUZIONE |___________| [ritorno al codice]
(5)
USER MODE KERNEL MODE
Transizione User->Kernel Mode causata da evento IRQ
I seguenti passi si riferiscono al diagramma precedente:
Un IRQ di particolare interesse e' quello relativo al Timer che arriva ogni tot millisecondi per gestire
La punto chiave di ogni moderno sistema operativo e' il ''Task''. Il Task e' un'applicazione che ''gira'' in memoria e codivide tutte le risorse del sistema (inclusi CPU e Memoria) con gli altri Tasks.
Questa ''condivisione di risorse'' viene gestita dal meccanismo di MultiTasking. Ogni tot (''timeslice'') millisecondi avviene il cambiamento di contesto (Task Switching'') grazie al quale gli utenti hanno l'illusione di possedere tutte le risorse; se consideriamo un solo utente si avra' invece l'illusione di poter eseguire piu' Tasks nello stesso istante.
Per implementare il Multitasking i Task utilizzano una variabile ''state'' che puo' assumere i valori:
Lo stato del Task viene gestito dalla presenza o meno dello stesso nella lista relativa:
La commutazione da un Task ad un altro si chiama ''Task Switching''. Molti elaboratori hanno una istruzione hardware che esegue automaticamente questa operazione. Il Task Switching avviene nei seguenti casi:
In entrambi i casi abbiamo bisogno di schedulare un nuovo processo pronto per l'esecuzione (dalla ''Ready List'') ed eseguirlo.
* Questo serve ad evitare la ''Busy Form Waiting'', cioe' l'esecuzione inutile di un loop del processo in attesa della risorsa.
Il Task Switching viene gestito dall'entita' ''Schedule''.
Timer | |
IRQ | | Schedule
| | | ________________________
|----->| Task 1 |<------------------>|(1)Scegli un nuovo Task |
| | | |(2)Task Switching |
| |___________| |________________________|
| | | /|\
| | | |
| | | |
| | | |
| | | |
|----->| Task 2 |<-------------------------------|
| | | |
| |___________| |
. . . . .
. . . . .
. . . . .
| | | |
| | | |
------>| Task N |<--------------------------------
| |
|___________|
Task Switching basato sul TimeSlice
Un tipico Timeslice per Linux e' di circa 10 ms (in alcune architetture 1 ms).
| |
| | Accesso _____________________________
| Task 1 |----------->|(1) Accoda richiesta risorsa |
| | Risorsa |(2) Marca Task come bloccato |
| | |(3) Scegli un Task Pronto |
|___________| |(4) Task Switching |
|_____________________________|
|
|
| | |
| | |
| Task 2 |<-------------------------
| |
| |
|___________|
Task Switching basato sull'attesa di una risorsa
Fino adesso abbiamo visto i cosiddetti OS Monolitici, ma esiste anche un'altra famiglia di OS, quella basata sui ''Microkernel''.
Un OS basato su Microkernel utilizza i Tasks, non solo per i processi in User Mode, ma anche come gestori del Kernel, come il Floppy-Task, l'HDD-Task, il Net-Task e cosi' via. Alcuni esempi sono Amoeba e Mach.
PRO:
CONTRO:
La mia opinione personale e' che gli OS Microkernel sono un buon esempio didattico (come Minix) ma non sono ''ottimali'' (cioe' partono gia' male come prestazioni) quindi non sono da considerarsi come buoni OS.
Linux utilizza alcuni Tasks, chiamati "Kernel Threads" per implementare un mini struttura microkernel, laddove e' evidente che le il tempo di accesso di un Task Switching sia notevolmente trascurabile (come ''kswapd'', che serve per recuperare pagine dalla memoria di massa).
Lo Standard ISO-OSI descrive un'architettura di rete con i seguenti livelli:
I primi 2 livelli sono di solito implementati in hardware mentre i livelli successivi in software (o in firmware per i routers).
Un OS e0 capace di gestire molti protocolli: uno di questi e' il TCP/IP (il piu' importante sui livelli 3-4).
Il Kernel non conosce nulla dei primi 2 livelli
In RX l'OS:
frames pacchetti sockets
NIC ---------> Kernel ----------> Applicazione
| pacchetti
--------------> Instradamento
- RX -
Nello stadio di TX l'OS:
sockets packets frames
Application ---------> Kernel ----------> NIC
packets /|\
Forward -------------------
- TX -
La Segmentazione e' il primo metodo per risolvere i problemi di allocazione di memoria: questa tecnica permette di compilare il codice sorgente senza preoccuparsi di dove i dati verranno eseguiti o memorizzati. In effetti questa feature e' di grande aiuto nello sviluppare di applicazioni in modo indipendente dall'OS e dall'Hardware.
| Stack |
| | |
| \|/ |
| Spazio Libero |
| /|\ | Segmento <---> Processo
| | |
| Heap |
|Dati non inizializzati|
| Dati inizializzati |
| Codice |
|______________________|
Segmento
Possiamo dire che un segmento e' la trasposizione logica di un'applicazione in memoria, o anche l'immagine dell'applicazione.
Quando si programmiamo non ci interessiamo di dove esattamente i dati vadano a finire in memoria, ci preoccupiamo soltanto dell'offset all'interno del segmento (quindi dell'applicazione).
Siamo soliti attribuire quindi, un Segment ad ogni Processo e viceversa. In Linux questo non e' vero fino in fondo, in quanto vengono usati soltanto 4 segmenti per il Kernel e tutti i Processi.
____________________
----->| |----->
| IN | Segmento A | OUT
____________________ | |____________________|
| |____| | |
| Segmento B | | Segmento B |
| |____ | |
|____________________| | |____________________|
| | Segmento C |
| |____________________|
----->| Segmento D |----->
IN |____________________| OUT
Problema della Segmentazione
Nel diagramma vogliamo disallocare i processi A e D ad allocare il processo B.
Come si puo' vedere ci sarebbe abbastanza spazio per B, ma in pratica non possiamo splittarlo in 2 pezzi e quindi NON POSSIAMO caricarlo (manca memoria!).
La ragione di fondo di cio' e che i segmenti puri sono aree contigue proprio perche' sono aree logiche (di processo) e quindi non possono essere divise.
____________________
| Pagina 1 |
|____________________|
| Pagina 2 |
|____________________|
| .. | Segmento <---> Processo
|____________________|
| Pagina n |
|____________________|
| |
|____________________|
| |
|____________________|
Segmento
La Paginazione divide la memoria in "N" pezzi, tutti a lunghezza fissa.
Un processo puo' essere caricato in una o piu' pagine. Quando un processo viene disallocato, tutte le sue pagine vengono liberate (vedi Problema della Segmentazione, prima).
La Paginazione viene sfruttata anche per un altro importante scopo: lo "Swapping": se una pagina infatti non e' presente in memoria fisica viene generata un'ECCEZIONE , che fara' cercare al Kernel una pagina in memoria di massa. Questo meccanismo permette all'OS di caricare piu' applicazioni rispetto a quelle realmente caricabili soltanto in memoria fisica.
____________________
Pagina X | Processo Y |
|____________________|
| |
| SPAZIO |
| INUTILIZZATO |
|____________________|
Problema della Paginazione
Nel diagramma possiamo notare qual e' il problema della Paginazione: quando un Processo Y viene caricato nella Pagina X, TUTTO la spazio di memoria viene allocato, cosicche' il rimanente spazio in fondo alla pagina rimanga inutilizzato.
Come possiamo risolvere i problemi di segmentazione e paginazione? Utilizzando entrambe le politiche.
| .. |
|____________________|
----->| Pagina 1 |
| |____________________|
| | .. |
____________________ | |____________________|
| | |---->| Pagina 2 |
| Segmento X | ----| |____________________|
| | | | .. |
|____________________| | |____________________|
| | .. |
| |____________________|
|---->| Pagina 3 |
|____________________|
| .. |
Il Processo X, identificato dal Segmento X, viene diviso in 3 pezzi ognino poi caricato in una pagina.
Non abbiamo:
| | | |
| | Offset2 | Valore |
| | /|\| |
Offset1 | |----- | | |
/|\ | | | | | |
| | | | \|/| |
| | | ------>| |
\|/ | | | |
Indirizzo Base --------->| | | |
Paginazione | ....... | | ....... |
| | | |
Paginazione Gerarchica
Il Kernel di Linux inizia dal codice C eseguito a partire dall'etichetta assember ''startup_32:'':
|startup_32:
|start_kernel
|lock_kernel
|trap_init
|init_IRQ
|sched_init
|softirq_init
|time_init
|console_init
|#ifdef CONFIG_MODULES
|init_modules
|#endif
|kmem_cache_init
|sti
|calibrate_delay
|mem_init
|kmem_cache_sizes_init
|pgtable_cache_init
|fork_init
|proc_caches_init
|vfs_caches_init
|buffer_init
|page_cache_init
|signals_init
|#ifdef CONFIG_PROC_FS
|proc_root_init
|#endif
|#if defined(CONFIG_SYSVIPC)
|ipc_init
|#endif
|check_bugs
|smp_init
|rest_init
|kernel_thread
|unlock_kernel
|cpu_idle
L'ultima funzione ''rest_init'':
In effetti la funzione ''start_kernel'' non finisce mai.
Segue la descrizione di init che e' il primo kernel_thread in esecuzione (che lanciera' poi tutti gli altri)
|init
|lock_kernel
|do_basic_setup
|mtrr_init
|sysctl_init
|pci_init
|sock_init
|start_context_thread
|do_init_calls
|(*call())-> kswapd_init
|prepare_namespace
|free_initmem
|unlock_kernel
|execve
Linux possiede alcune caratteristiche pressoche' uniche rispetto agli altri OSs. These peculiarities include:
I punti 4 e 5 danno agli ammistratori un'enorme flessibilita' sulla configurazione del sistema in User Mode permettendo loro di risolvere anche problemi critici (come kernel bugs) senza dover riavviare la macchina
Ad esempio se si vuol cambiare qualcosa nel Kernel di un grosso server non e' necessario riavviarlo, bastera' preparare la prima volta il kernel ad accogliere un modulo e, in seguito, creare il modulo per effettuare le modifiche volute.
Linux non utilizza la Segmentazione per distinguere i Tasks l'uno dall'altro, usa soltanto la Paginazione (solo 2 segmenti vengono utilizzati in tutti i Tasks, CODE e DATA/STACK).
Possiamo anche dire che una ''Page Fault'' tra Task non puo' mai avvenire (cioe' quell'evento scatenato quando un Task vuole scrivere sull'area di memoria di un altro Task), poiche' ogni Task utilizza un set di Page Tables (Tabelle di Paginazione) differenti per ogni Processo: queste tabelle non possono mai puntare allo stesso indirizzo fisico (per costruzione).
Sotto Linux vengono utilizzati soltanto 4 segmenti:
[La sintassi e' ''Utilizzo [Segmento]'']
Nell'architettura Intel, i registri di segmenti usati sono:
Quindi ogni Task utilizza il segmenti 0x23 per il codice e il segmenti 0x2b per data/stack.
Linux utilizza uno schema con 3 levelli di paginazione, a seconda dell'architecture.
Intel permette di sfruttare solo 2 levelli. Per ottimizzare l'utilizzo della memoria viene anche utilizzato il meccanismo della ''Copy on Write'' (si veda il Cap.10 per ulteriori informazioni).
La risposta e' molto molto semplice: i conflitti tra indirizzi sono impossibili.
La mappatura tra indirizzi Lineari-> Fisici viene gestita dalla Paginazione, quindi e' sufficiente assegnare le pagine fisiche in modo univoco.
No. L'assegnazione delle Pagine e' un processo dinamico: abbiamo bisogno di allocare una pagina soltanto quando un Task lo richiede e quindi possiamo sceglierlo tra le pagine di memoria libere in modo ordinato. Quando vogliamo rilasciare una pagina dobbiamo soltanto aggiungerla nella ''free page list''.
Lo spazio del Kernel ha una caratteristica: lo spazio Lineare coincide con quello Fisico (questo per semplificare la vita!). Questa peculiarita' comporta che sia necessario allocare una volta per tutte un blocco di memoria senza poi possibilita' alcuna di aggiungere un altro blocco in modo CONTIGUO (non lo si puo' garantire perche' vi possono essere altre pagine in User Mode in mezzo!).
Tutto cio' non porta a grossi problemi per quanto riguarda il CODICE in quanto esso non modifica a Run-Time la propria dimensione (si intende la dimensione in maniera CONTIGUA), bastera' quindi allocare la prima volta uno spazio di memoria sufficiente e non si avranno problemi.
Il problema vero si ha nel caso dello STACK, in quanto ogni processo (in Kernel Mode) utilizza 1 pagina di Kernel Stack: com'e' noto lo Stack e' una struttura dati che richiede di essere CONTIGUA, quindi, una volta stabilito il limite massimo per lo stack (come detto 1 pagina) non lo si potra' piu' aumentare.
Se si dovesse utilizzare lo Stack oltre lo spazio consentito vi sarebbe una scrittura sulle strutture dati relative al processo in questione (in Kernel Mode).
Fortunatamente la struttura del Kernel ci aiuta, in quanto le funzioni del sistema:
Una volta noto N, e una volta noto il massimo utilizzo di stack da parte delle funzioni del Kernel chiamate si potra' avere la giusta stima per lo Stack.
Per verificare il problema e' sufficiente creare un modulo che abbiam una funzione ricorsiva che si richiami un certo numero di volte. Dopo un certo numero di volte il Kernel si blocchera' generando una eccezione di page fault.
Quando arriva un IRQ, il ''Task Switching'' viene posticipato per non intaccare le prestazioni del sistema.
Alcuni lavori (che possono essere eseguiti tranquillamente anche dopo l'IRQ e che consumano molta CPU, come la costruzione di un pacchetto TCP/IP) vengono accodati per essere poi eseguiti durante lo scheduling (una volta cioe' che il TimeSlice dell'attuale processo e' terminato).
Nei Kernels recenti (2.4.x) il meccanismo "SoftIrq'' viene gestito da un Kernel Thread: ''ksoftirqd_CPUn'', dove n sta' per il numero di CPU che sta eseguendo il tale Thread (in un sistema monoprocessore il nome e' ''ksoftirqd_CPU0'' avente PID 3).
''cpu_raise_softirq'' e' la routine che sveglia il Kernel Thread ''ksoftirqd_CPU0'' che gestira' poi il lavoro accodato:
|cpu_raise_softirq
|__cpu_raise_softirq
|wakeup_softirqd
|wake_up_process
La routine ''__cpu_raise_softirq'' attiva il bit giusto relativo a lavoro in questione sul vettore della coda SoftIrq.
''wakeup_softirq'' usa ''wakeup_process'' per svegliare il Kernel Thread ''ksoftirqd_CPU0''.
DAFARE: descrivere la struttura dati del meccanismo SoftIrq.
Quando ''ksoftirqd_CPU0'' si sveglia, andra' ad eseguire i lavori accodati.
Il codice di ''ksoftirqd_CPU0'' (ciclo principale) e':
for (;;) {
if (!softirq_pending(cpu))
schedule();
__set_current_state(TASK_RUNNING);
while (softirq_pending(cpu)) {
do_softirq();
if (current->need_resched)
schedule
}
__set_current_state(TASK_INTERRUPTIBLE)
}
Sebbene Linux sia un OS Monolitico, esistono alcuni ''Kernel Threads'' per eseguire del lavoro di manutenzione del sistema.
Questi Tasks non utilizzano memoria UTENTE, ma condividono quella del KERNEL; operano al piu' alto privilegio (RING 0 su architettura 386+) come ogni altro codice del Kernel.
I Kernel Threads vengono creati dalla funzione ''kernel_thread [arch/i386/kernel/process]'', che va poi a chiamare la System Call ''clone'' [arch/i386/kernel/process.c] in assembler (che praticamente e' come la ''fork''):
int kernel_thread(int (*fn)(void *), void * arg, unsigned long flags)
{
long retval, d0;
__asm__ __volatile__(
"movl %%esp,%%esi\n\t"
"int $0x80\n\t" /* Linux/i386 system call */
"cmpl %%esp,%%esi\n\t" /* child or parent? */
"je 1f\n\t" /* parent - jump */
/* Load the argument into eax, and push it. That way, it does
* not matter whether the called function is compiled with
* -mregparm or not. */
"movl %4,%%eax\n\t"
"pushl %%eax\n\t"
"call *%5\n\t" /* call fn */
"movl %3,%0\n\t" /* exit */
"int $0x80\n"
"1:\t"
:"=&a" (retval), "=&S" (d0)
:"0" (__NR_clone), "i" (__NR_exit),
"r" (arg), "r" (fn),
"b" (flags | CLONE_VM)
: "memory");
return retval;
}
Una volta chiamata, avremo un nuovo Task (di solito con PID molto basso, come 2,3, ecc.) all'interno di un ciclo infinito in attesa di una risorsa molto lenta, come lo swap o un evento usb (soltanto risorse lente altrimenti il tempo di Task Switching potrebbe influenzare negativamente le prestazioni del sistema)
Segue una lista dei piu' comuni Kernel Threads (dal comando ''ps x''):
PID COMMAND 1 init 2 keventd 3 kswapd 4 kreclaimd 5 bdflush 6 kupdated 7 kacpid 67 khubd
'init' e' il primo processo creato, che chiamera' tutti gli altri Tasks in User Modes (dal file /etc/inittab) come i demoni di console, di tty, di rete e cosi' via (''rc'' scripts).
''kswapd'' viene creato dalla ''clone() [arch/i386/kernel/process.c]''
Routines di inzializzazione:
|do_initcalls
|kswapd_init
|kernel_thread
|syscall fork (in assembler)
do_initcalls [init/main.c]
kswapd_init [mm/vmscan.c]
kernel_thread [arch/i386/kernel/process.c]
I Moduli del Kernel sono pezzi di codice (che gestiscono ad esempio fs, net, e hw driver) che girano in Modo Kernel e che possono essere caricati in qualunque momento.
Quasi tutto il codice puo' essere modularizzato, tranne il core piu' interno del Kernel, quello che gestisce scheduling, interrupt, core della rete, e cosi' via.
Nella directory "/lib/modules/KERNEL_VERSION/" si trovano tutti i moduli installati nel sistema.
Per caricare un module, basta digitare:
insmod NOME_MODULO parametri esempio: insmod ne io=0x300 irq=9
NOTA: Si puo' utilizzare ''modprobe'' al posto di ''insmod'' per far caricare alcuni parametri in automatico (come per le periferiche PCI, oppure quando si specificano i parametri nel file /etc/conf.modules o nel nuovo /etc/modules.conf).
Per rimuovere un modulo, digitare:
rmmod NOME_MODULO
Un Module contiene sempre le funzioni
In alternativa si possono specificare altre funzioni di inizializzazione e chiusura tramite le macro:
NOTA: un modulo puo' ''vedere'' le variabili del Kernel solo se queste sono state precedentemente esportate (nella loro dichiarazione (con la macro EXPORT_SYMBOL).
// Parte kernel
void (*foo_function_pointer)(void *);
if (foo_function_pointer)
(foo_function_pointer)(parameter);
// Parte modulo
extern void (*foo_function_pointer)(void *);
void my_function(void *parameter) {
//My code
}
int init_module() {
foo_function_pointer = &my_function;
}
int cleanup_module() {
foo_function_pointer = NULL;
}
Questo artifizio permette di rendere il Kernel piu' flessibile, perche' soltanto quando si carica il modulo, la funzione ''my_function'' verra' effettivamente eseguita: questa routine potra' fare qualunque cosa vogliamo, ad esempio il modulo ''rshaper'' (per limitare il traffico in entrata dalla rete) funziona in questo modo.
Si noti come l'intero meccanismo dei moduli sia possibile grazie ad alcune variabili globali nel kernel che vengono esportate ai moduli, come puntatori a liste (permettendo di estendere tali liste quanto si vuole): esempi tipici sono i fs e i devices (char, block, net, telephony).
In definitiva, per caricare un modulo, bisogna in qualche modo ''preparare il kernel'' perche' lo accetti (se si vuole fargli fare qualcosa di interessante): in alcuni casi e' necessario creare una nuova infrastruttura che sia poi il piu' standard possibile (come quella ''telephony'' creata di recente).
Nella directory /proc e' presente il FS proc, che e' un sistema speciale per consentire il dialogo diretto con il Kernel in user mode.
Linux utilizza tale directory, ad esempio per dialogare con le strutture dati dei processi, per gestire le opzioni di rete delle interfacce come il ''proxy-arp'', il massimo numero di Threads, o per controllare lo state dei bus ISA o PCI, per sapere quali schede sono installate nel sistema e con quali indirizzi di I/O e IRQs
Segue l'elenco delle sottodirectory piu' importanti della directory proc:
|-- bus | |-- pci | | |-- 00 | | | |-- 00.0 | | | |-- 01.0 | | | |-- 07.0 | | | |-- 07.1 | | | |-- 07.2 | | | |-- 07.3 | | | |-- 07.4 | | | |-- 07.5 | | | |-- 09.0 | | | |-- 0a.0 | | | `-- 0f.0 | | |-- 01 | | | `-- 00.0 | | `-- devices | `-- usb |-- cmdline |-- cpuinfo |-- devices |-- dma |-- dri | `-- 0 | |-- bufs | |-- clients | |-- mem | |-- name | |-- queues | |-- vm | `-- vma |-- driver |-- execdomains |-- filesystems |-- fs |-- ide | |-- drivers | |-- hda -> ide0/hda | |-- hdc -> ide1/hdc | |-- ide0 | | |-- channel | | |-- config | | |-- hda | | | |-- cache | | | |-- capacity | | | |-- driver | | | |-- geometry | | | |-- identify | | | |-- media | | | |-- model | | | |-- settings | | | |-- smart_thresholds | | | `-- smart_values | | |-- mate | | `-- model | |-- ide1 | | |-- channel | | |-- config | | |-- hdc | | | |-- capacity | | | |-- driver | | | |-- identify | | | |-- media | | | |-- model | | | `-- settings | | |-- mate | | `-- model | `-- via |-- interrupts |-- iomem |-- ioports |-- irq | |-- 0 | |-- 1 | |-- 10 | |-- 11 | |-- 12 | |-- 13 | |-- 14 | |-- 15 | |-- 2 | |-- 3 | |-- 4 | |-- 5 | |-- 6 | |-- 7 | |-- 8 | |-- 9 | `-- prof_cpu_mask |-- kcore |-- kmsg |-- ksyms |-- loadavg |-- locks |-- meminfo |-- misc |-- modules |-- mounts |-- mtrr |-- net | |-- arp | |-- dev | |-- dev_mcast | |-- ip_fwchains | |-- ip_fwnames | |-- ip_masquerade | |-- netlink | |-- netstat | |-- packet | |-- psched | |-- raw | |-- route | |-- rt_acct | |-- rt_cache | |-- rt_cache_stat | |-- snmp | |-- sockstat | |-- softnet_stat | |-- tcp | |-- udp | |-- unix | `-- wireless |-- partitions |-- pci |-- scsi | |-- ide-scsi | | `-- 0 | `-- scsi |-- self -> 2069 |-- slabinfo |-- stat |-- swaps |-- sys | |-- abi | | |-- defhandler_coff | | |-- defhandler_elf | | |-- defhandler_lcall7 | | |-- defhandler_libcso | | |-- fake_utsname | | `-- trace | |-- debug | |-- dev | | |-- cdrom | | | |-- autoclose | | | |-- autoeject | | | |-- check_media | | | |-- debug | | | |-- info | | | `-- lock | | `-- parport | | |-- default | | | |-- spintime | | | `-- timeslice | | `-- parport0 | | |-- autoprobe | | |-- autoprobe0 | | |-- autoprobe1 | | |-- autoprobe2 | | |-- autoprobe3 | | |-- base-addr | | |-- devices | | | |-- active | | | `-- lp | | | `-- timeslice | | |-- dma | | |-- irq | | |-- modes | | `-- spintime | |-- fs | | |-- binfmt_misc | | |-- dentry-state | | |-- dir-notify-enable | | |-- dquot-nr | | |-- file-max | | |-- file-nr | | |-- inode-nr | | |-- inode-state | | |-- jbd-debug | | |-- lease-break-time | | |-- leases-enable | | |-- overflowgid | | `-- overflowuid | |-- kernel | | |-- acct | | |-- cad_pid | | |-- cap-bound | | |-- core_uses_pid | | |-- ctrl-alt-del | | |-- domainname | | |-- hostname | | |-- modprobe | | |-- msgmax | | |-- msgmnb | | |-- msgmni | | |-- osrelease | | |-- ostype | | |-- overflowgid | | |-- overflowuid | | |-- panic | | |-- printk | | |-- random | | | |-- boot_id | | | |-- entropy_avail | | | |-- poolsize | | | |-- read_wakeup_threshold | | | |-- uuid | | | `-- write_wakeup_threshold | | |-- rtsig-max | | |-- rtsig-nr | | |-- sem | | |-- shmall | | |-- shmmax | | |-- shmmni | | |-- sysrq | | |-- tainted | | |-- threads-max | | `-- version | |-- net | | |-- 802 | | |-- core | | | |-- hot_list_length | | | |-- lo_cong | | | |-- message_burst | | | |-- message_cost | | | |-- mod_cong | | | |-- netdev_max_backlog | | | |-- no_cong | | | |-- no_cong_thresh | | | |-- optmem_max | | | |-- rmem_default | | | |-- rmem_max | | | |-- wmem_default | | | `-- wmem_max | | |-- ethernet | | |-- ipv4 | | | |-- conf | | | | |-- all | | | | | |-- accept_redirects | | | | | |-- accept_source_route | | | | | |-- arp_filter | | | | | |-- bootp_relay | | | | | |-- forwarding | | | | | |-- log_martians | | | | | |-- mc_forwarding | | | | | |-- proxy_arp | | | | | |-- rp_filter | | | | | |-- secure_redirects | | | | | |-- send_redirects | | | | | |-- shared_media | | | | | `-- tag | | | | |-- default | | | | | |-- accept_redirects | | | | | |-- accept_source_route | | | | | |-- arp_filter | | | | | |-- bootp_relay | | | | | |-- forwarding | | | | | |-- log_martians | | | | | |-- mc_forwarding | | | | | |-- proxy_arp | | | | | |-- rp_filter | | | | | |-- secure_redirects | | | | | |-- send_redirects | | | | | |-- shared_media | | | | | `-- tag | | | | |-- eth0 | | | | | |-- accept_redirects | | | | | |-- accept_source_route | | | | | |-- arp_filter | | | | | |-- bootp_relay | | | | | |-- forwarding | | | | | |-- log_martians | | | | | |-- mc_forwarding | | | | | |-- proxy_arp | | | | | |-- rp_filter | | | | | |-- secure_redirects | | | | | |-- send_redirects | | | | | |-- shared_media | | | | | `-- tag | | | | |-- eth1 | | | | | |-- accept_redirects | | | | | |-- accept_source_route | | | | | |-- arp_filter | | | | | |-- bootp_relay | | | | | |-- forwarding | | | | | |-- log_martians | | | | | |-- mc_forwarding | | | | | |-- proxy_arp | | | | | |-- rp_filter | | | | | |-- secure_redirects | | | | | |-- send_redirects | | | | | |-- shared_media | | | | | `-- tag | | | | `-- lo | | | | |-- accept_redirects | | | | |-- accept_source_route | | | | |-- arp_filter | | | | |-- bootp_relay | | | | |-- forwarding | | | | |-- log_martians | | | | |-- mc_forwarding | | | | |-- proxy_arp | | | | |-- rp_filter | | | | |-- secure_redirects | | | | |-- send_redirects | | | | |-- shared_media | | | | `-- tag | | | |-- icmp_echo_ignore_all | | | |-- icmp_echo_ignore_broadcasts | | | |-- icmp_ignore_bogus_error_responses | | | |-- icmp_ratelimit | | | |-- icmp_ratemask | | | |-- inet_peer_gc_maxtime | | | |-- inet_peer_gc_mintime | | | |-- inet_peer_maxttl | | | |-- inet_peer_minttl | | | |-- inet_peer_threshold | | | |-- ip_autoconfig | | | |-- ip_conntrack_max | | | |-- ip_default_ttl | | | |-- ip_dynaddr | | | |-- ip_forward | | | |-- ip_local_port_range | | | |-- ip_no_pmtu_disc | | | |-- ip_nonlocal_bind | | | |-- ipfrag_high_thresh | | | |-- ipfrag_low_thresh | | | |-- ipfrag_time | | | |-- neigh | | | | |-- default | | | | | |-- anycast_delay | | | | | |-- app_solicit | | | | | |-- base_reachable_time | | | | | |-- delay_first_probe_time | | | | | |-- gc_interval | | | | | |-- gc_stale_time | | | | | |-- gc_thresh1 | | | | | |-- gc_thresh2 | | | | | |-- gc_thresh3 | | | | | |-- locktime | | | | | |-- mcast_solicit | | | | | |-- proxy_delay | | | | | |-- proxy_qlen | | | | | |-- retrans_time | | | | | |-- ucast_solicit | | | | | `-- unres_qlen | | | | |-- eth0 | | | | | |-- anycast_delay | | | | | |-- app_solicit | | | | | |-- base_reachable_time | | | | | |-- delay_first_probe_time | | | | | |-- gc_stale_time | | | | | |-- locktime | | | | | |-- mcast_solicit | | | | | |-- proxy_delay | | | | | |-- proxy_qlen | | | | | |-- retrans_time | | | | | |-- ucast_solicit | | | | | `-- unres_qlen | | | | |-- eth1 | | | | | |-- anycast_delay | | | | | |-- app_solicit | | | | | |-- base_reachable_time | | | | | |-- delay_first_probe_time | | | | | |-- gc_stale_time | | | | | |-- locktime | | | | | |-- mcast_solicit | | | | | |-- proxy_delay | | | | | |-- proxy_qlen | | | | | |-- retrans_time | | | | | |-- ucast_solicit | | | | | `-- unres_qlen | | | | `-- lo | | | | |-- anycast_delay | | | | |-- app_solicit | | | | |-- base_reachable_time | | | | |-- delay_first_probe_time | | | | |-- gc_stale_time | | | | |-- locktime | | | | |-- mcast_solicit | | | | |-- proxy_delay | | | | |-- proxy_qlen | | | | |-- retrans_time | | | | |-- ucast_solicit | | | | `-- unres_qlen | | | |-- route | | | | |-- error_burst | | | | |-- error_cost | | | | |-- flush | | | | |-- gc_elasticity | | | | |-- gc_interval | | | | |-- gc_min_interval | | | | |-- gc_thresh | | | | |-- gc_timeout | | | | |-- max_delay | | | | |-- max_size | | | | |-- min_adv_mss | | | | |-- min_delay | | | | |-- min_pmtu | | | | |-- mtu_expires | | | | |-- redirect_load | | | | |-- redirect_number | | | | `-- redirect_silence | | | |-- tcp_abort_on_overflow | | | |-- tcp_adv_win_scale | | | |-- tcp_app_win | | | |-- tcp_dsack | | | |-- tcp_ecn | | | |-- tcp_fack | | | |-- tcp_fin_timeout | | | |-- tcp_keepalive_intvl | | | |-- tcp_keepalive_probes | | | |-- tcp_keepalive_time | | | |-- tcp_max_orphans | | | |-- tcp_max_syn_backlog | | | |-- tcp_max_tw_buckets | | | |-- tcp_mem | | | |-- tcp_orphan_retries | | | |-- tcp_reordering | | | |-- tcp_retrans_collapse | | | |-- tcp_retries1 | | | |-- tcp_retries2 | | | |-- tcp_rfc1337 | | | |-- tcp_rmem | | | |-- tcp_sack | | | |-- tcp_stdurg | | | |-- tcp_syn_retries | | | |-- tcp_synack_retries | | | |-- tcp_syncookies | | | |-- tcp_timestamps | | | |-- tcp_tw_recycle | | | |-- tcp_window_scaling | | | `-- tcp_wmem | | `-- unix | | `-- max_dgram_qlen | |-- proc | `-- vm | |-- bdflush | |-- kswapd | |-- max-readahead | |-- min-readahead | |-- overcommit_memory | |-- page-cluster | `-- pagetable_cache |-- sysvipc | |-- msg | |-- sem | `-- shm |-- tty | |-- driver | | `-- serial | |-- drivers | |-- ldisc | `-- ldiscs |-- uptime `-- version
Nella directory sono presenti anche tutti i Tasks attivi tramite il PID (che funge da nome della directory) tramite cui si puo' avere accesso alle informazioni relative ai Tasks, come percorso del file binario, memoria usata e cosi' via).
Il punto piu' interessante e' che non e' soltanto possibile ''vedere'' alcuni valori, ma anche modificarli, come quelli nella sottodirectory /proc/sys:
/proc/sys/
acpi
dev
debug
fs
proc
net
vm
kernel
Sotto seguono alcuni file utili per modificare dei settaggi del kernel:
overflowgid overflowuid random threads-max // Massimo numero dei Threads, tipicamente 16384 sysrq // kernel hack: per consultare istantaneamente i valori dei registri del processore sem msgmnb msgmni msgmax shmmni shmall shmmax rtsig-max rtsig-nr modprobe // percorso di modprobe printk ctrl-alt-del cap-bound panic domainname // domain name del Linux box hostname // host name del Linux box version // data del Kernel osrelease // versione del kernel (i.e. 2.4.5) ostype // Linux!
Questa puo' essere cosiderate la piu' utile sottodirectory del kernel: permette di cambiare alcuni importanti settaggi della rete del Kernel:
core ipv4 ipv6 unix ethernet 802
Sotto sono elencati alcuni settaggi di rete generali come "netdev_max_backlog" (tipicamente) che indica la lunghezza massima della coda di tutti i pacchetti di rete. Questo valore puo' limitare la banda della rete quando si ricevono i pacchetti, perche' Linux deve attendere fino al successivo tempo di schedulazione (1000/HZ ms) per poter svuotare tale buffer di pacchetti (per il meccanismo del bottom half).
300 * 100 = 30 000 pacchetti HZ(freq Timeslice) pacchetti/s 30 000 * 1000 = 30 M pacchetti Media(Bytes/packet) throughput Bytes/s
Per aumentare le prestazioni bisogna aumentare necessariamente il valore di netdev_max_backlog, digitando:
echo 4000 > /proc/sys/net/core/netdev_max_backlog
Nota: Attenzione ai valori di HZ: alcune architetture (come alpha o arm-tbox) utilizzano 1000, che permettono quindi di arrivare a 300 MBytes/s di banda media.
"ip_forward", abilita o disabilita l'ip forwarding nel Linux box: questo e' un settaggio generale, ma e' possibile specificare per ogni interfaccia un valore diverso.
Ritengo questo sia la directory /proc piu' utile, in quanto permette di cambiare molti settaggi di rete utili soprattutto in caso di reti wireless (si veda il Wireless-HOWTO per maggiori informazioni).
Ecco alcuni esempi di utilizzo:
Questa capitolo analizza le strutture dati e funzionamento del Multitasking di Linux
Un Task Linux puo' esssere in uno dei seguenti stati (come da file [include/linux.h]):
______________ CPU Disponibile _______________
| | ----------------> | |
| TASK_RUNNING | |Vera esecuzione|
|______________| <---------------- |_______________|
CPU Occupata
| /|\
In attesa di| | Risorsa
una Risorsa | | Disponibile
\|/ |
______________________
| |
| TASK_INTERRUPTIBLE / |
| TASK-UNINTERRUPTIBLE |
|______________________|
Flusso Principale Multitasking
Ogni 10 ms (a seconda del valore di HZ) arriva un IRQ0, che permmette di gestire il multitasking: questo segnale arriva dal PIC 8259 (nell'architettura 386+) connesso a sua volta con il PIT 8253 avente clock di 1.19318 MHz.
_____ ______ ______
| CPU |<------| 8259 |------| 8253 |
|_____| IRQ0 |______| |___/|\|
|_____ CLK 1.193.180 MHz
// From include/asm/param.h
#ifndef HZ
#define HZ 100
#endif
// From include/asm/timex.h
#define CLOCK_TICK_RATE 1193180 /* Underlying HZ */
// From include/linux/timex.h
#define LATCH ((CLOCK_TICK_RATE + HZ/2) / HZ) /* For divider */
// From arch/i386/kernel/i8259.c
outb_p(0x34,0x43); /* binary, mode 2, LSB/MSB, ch 0 */
outb_p(LATCH & 0xff , 0x40); /* LSB */
outb(LATCH >> 8 , 0x40); /* MSB */
Quindi quello che si fa e' programmare l'8253 (PIT, Programmable Interval Timer) con LATCH = (1193180/HZ) = 11931.8, dove HZ=100 (default). LATCH indica il fattore di divisione frequenza per il clock.
LATCH = 11931.8 fornisce all'8253 (in output) una frequenza di 1193180 / 11931.8 = 100 Hz, quindi il periodo tra 2 IRQ0 e' di 10ms
Quindi il Timeslice si misura come 1/HZ.
Ogni TimeSlice viene sospeso il processo attualmente di esecuzione (senza Task Switching), e viene fatto del lavoro di ''manutenzione'', dopo di che il controllo ritorna al processo precedentemente interrotto.
Linux Timer IRQ
IRQ 0 [Timer]
|
\|/
|IRQ0x00_interrupt // wrapper IRQ handler
|SAVE_ALL ---
|do_IRQ | wrapper routines
|handle_IRQ_event ---
|handler() -> timer_interrupt // registered IRQ 0 handler
|do_timer_interrupt
|do_timer
|jiffies++;
|update_process_times
|if (--counter <= 0) { // if time slice ended then
|counter = 0; // reset counter
|need_resched = 1; // prepare to reschedule
|}
|do_softirq
|while (need_resched) { // if necessary
|schedule // reschedule
|handle_softirq
|}
|RESTORE_ALL
Le Funzioni si trovano:
Note:
Descrizione:
Per gestire il Multitasking quindi, Linux (come ogni sistema Unix-like) utilizza un ''contatore'' per tenere traccia di quanto e' stata utilizzata la CPU dal Task.
Quindi, ad ogni IRQ 0, il contatore viene decrementato (punto 4) e, quando raggiunge 0, siamo dobbiamo effettuare un Task Switching (punto 4, la variabile "need_resched" viene settata ad 1, cosicche' nel punto 5 tale valore porta a chiamare la "schedule" [kernel/sched.c]).
Lo scheduler e' quella parte di codice che sceglie QUALE Task deve venir eseguito di volta in volta.
Ogni volta che si deve cambiare Task viene scelto un candidato.
Segue la funzione ''schedule [kernel/sched.c]''.
|schedule
|do_softirq // manages post-IRQ work
|for each task
|calculate counter
|prepare_to__switch // does anything
|switch_mm // change Memory context (change CR3 value)
|switch_to (assembler)
|SAVE ESP
|RESTORE future_ESP
|SAVE EIP
|push future_EIP *** push parametro come se facessimo una call
|jmp __switch_to (funzione per gestire alcuni registri)
|__switch_to() (si veda dopo per la spiegazione del funzionamento del Task Switching
..
|ret *** ret dalla call usando il nuovo EIP
new_task
Nei classici Unix, quando arriva un IRQ (da un device), il sistema effettua il Task Switching per interrogare il Task che ha fatto accesso al Device.
Per migliorare le performance, Linux posticipa il lavoro non urgente.
Questa funzionalita' e' stata gestita fin dalle prime versioni (kernel 1.x in poi) dai cosiddetti "bottom halves" (BH). In sostanza l'IRQ handler ''marca'' un bottom half (flag), per essere eseguito piu' tardi, e durante la schedulazione vengono poi eseguiti tutti i BH attivi.
Negli ultimi Kernels compare il meccanismo del "Task Queue" piu' dinamico del BH e nascono anche i "Tasklet" per gestire i sistemi multiprocessore.
Lo schema e':
#define DECLARE_TASK_QUEUE(q) LIST_HEAD(q)
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
struct list_head {
struct list_head *next, *prev;
};
#define LIST_HEAD_INIT(name) { &(name), &(name) }
''DECLARE_TASK_QUEUE'' [include/linux/tqueue.h, include/linux/list.h]
La macro "DECLARE_TASK_QUEUE(q)" viene usata per dichiarare una struttura chiamata "q" per gestire i Task Queue.
Segue lo schema ICA per la "mark_bh" [include/linux/interrupt.h]:
|mark_bh(NUMBER)
|tasklet_hi_schedule(bh_task_vec + NUMBER)
|insert into tasklet_hi_vec
|__cpu_raise_softirq(HI_SOFTIRQ)
|soft_active |= (1 << HI_SOFTIRQ)
''mark_bh''[include/linux/interrupt.h]
Quindi, ad esempio, quando un IRQ handler vuole posticipare del lavoro, basta che esegua una marcatura con la mark_bh(NUMBER)", dove NUMBER e' un BH precedentemente dichiarato (si veda sezione precedente).
Vediamo l'esecuzione a partire dalla funzione "do_IRQ" [arch/i386/kernel/irq.c]:
if (softirq_pending(cpu)) do_softirq();
quindi la ''do_softirq.c" [kernel/softirq.c]:
asmlinkage void do_softirq() {
int cpu = smp_processor_id();
__u32 pending;
long flags;
__u32 mask;
debug_function(DO_SOFTIRQ,NULL);
if (in_interrupt())
return;
local_irq_save(flags);
pending = softirq_pending(cpu);
if (pending) {
struct softirq_action *h;
mask = ~pending;
local_bh_disable();
restart:
/* Reset the pending bitmask before enabling irqs */
softirq_pending(cpu) = 0;
local_irq_enable();
h = softirq_vec;
do {
if (pending & 1)
h->action(h);
h++;
pending >>= 1;
} while (pending);
local_irq_disable();
pending = softirq_pending(cpu);
if (pending & mask) {
mask &= ~pending;
goto restart;
}
__local_bh_enable();
if (pending)
wakeup_softirqd(cpu);
}
local_irq_restore(flags);
}
"h->action(h);" rappresenta la funzione precedentemente accodata.
set_intr_gate
set_trap_gate
set_task_gate (non used).
(*interrupt)[NR_IRQS](void) = { IRQ0x00_interrupt, IRQ0x01_interrupt, ..}
NR_IRQS = 224 [kernel 2.4.2]
DAFARE: Descrizione
Il Task Switching e' necessario in molti casi:
TRUCCO DEL TASK SWITCHING
#define switch_to(prev,next,last) do { \
asm volatile("pushl %%esi\n\t" \
"pushl %%edi\n\t" \
"pushl %%ebp\n\t" \
"movl %%esp,%0\n\t" /* save ESP */ \
"movl %3,%%esp\n\t" /* restore ESP */ \
"movl $1f,%1\n\t" /* save EIP */ \
"pushl %4\n\t" /* restore EIP */ \
"jmp __switch_to\n" \
"1:\t" \
"popl %%ebp\n\t" \
"popl %%edi\n\t" \
"popl %%esi\n\t" \
:"=m" (prev->thread.esp),"=m" (prev->thread.eip), \
"=b" (last) \
:"m" (next->thread.esp),"m" (next->thread.eip), \
"a" (prev), "d" (next), \
"b" (prev)); \
} while (0)
Come si puo' notare il trucco sta' nel
Il trucco sta' qui:
U S E R M O D E K E R N E L M O D E
| | | | | | | |
| | | | Timer | | | |
| | | Normal | IRQ | | | |
| | | Exec |------>|Timer_Int.| | |
| | | | | | .. | | |
| | | \|/ | |schedule()| | Task1 Ret|
| | | | |_switch_to|<-- | Address |
|__________| |__________| | | | | |
| | |S | |
Task1 Data/Stack Task1 Code | | |w | |
| | T|i | |
| | a|t | |
| | | | | | s|c | |
| | | | Timer | | k|h | |
| | | Normal | IRQ | | |i | |
| | | Exec |------>|Timer_Int.| |n | |
| | | | | | .. | |g | |
| | | \|/ | |schedule()| | | Task2 Ret|
| | | | |_switch_to|<-- | Address |
|__________| |__________| |__________| |__________|
Task2 Data/Stack Task2 Code Kernel Code Kernel Data/Stack
La Fork e' usata per creare un nuovo Task.
Si parte dal Task padre, e si copiano le strutture dati al Task figlio.
| |
| .. |
Task Parent | |
| | | |
| fork |---------->| CREATE |
| | /| NEW |
|_________| / | TASK |
/ | |
--- / | |
--- / | .. |
/ | |
Task Child /
| | /
| fork |<-/
| |
|_________|
Fork SysCall
Il Task appena creato (''Task figlio'') e' quasi identico al padre (''Task padre''), as eccezione di:
|sys_fork
|do_fork
|alloc_task_struct
|__get_free_pages
|p->state = TASK_UNINTERRUPTIBLE
|copy_flags
|p->pid = get_pid
|copy_files
|copy_fs
|copy_sighand
|copy_mm // gestisce la CopyOnWrite (I parte)
|allocate_mm
|mm_init
|pgd_alloc -> get_pgd_fast
|get_pgd_slow
|dup_mmap
|copy_page_range
|ptep_set_wrprotect
|clear_bit // marca la pagina read-only
|copy_segments // per LDT
|copy_thread
|childregs->eax = 0
|p->thread.esp = childregs // figlio ritorna 0
|p->thread.eip = ret_from_fork // figlio ricomincia fall'uscita della fork
|retval = p->pid // la fork del padre ritorna il pid del figlio
|SET_LINKS // Il Task viene inserito nella lista dei processi
|nr_threads++ // variabile globale
|wake_up_process(p) // Adesso possiamo svegliare il Task figlio
|return retval
fork ICA
Per implementare la Copy on Write Linux:
| Page
| Fault
| Exception
|
|
-----------> |do_page_fault
|handle_mm_fault
|handle_pte_fault
|do_wp_page
|alloc_page // Allocata una nuova pagina
|break_cow
|copy_cow_page // Copia la vecchia pagina su quella nuova
|establish_pte // riconfigura i puntatori della Page Table
|set_pte
Page Fault ICA
Linux usa la segmentazione paginata che semplifica molto la notazione.
Vengono utilizzati soltanto 4 segmenti:
__
4 GB--->| | |
| Kernel | | Kernel Mode (Codice + Dati/Stack)
| | __|
3 GB--->|----------------| __
| | |
| | |
2 GB--->| | |
| Tasks | | User Mode (Codice + Dati/Stack)
| | |
1 GB--->| | |
| | |
|________________| __|
0x00000000
Indirizzi Lineari Kernel/User
Linux implementa la Paginazione usando 3 Levelli di Pagine, ma su architettura 386+ solo 2 sono effettivamente utilizzati:
-----------------------------------------------------------------
I N D I R I Z Z I L I N E A R I
-----------------------------------------------------------------
\___/ \___/ \_____/
PD offset PF offset Frame offset
[10 bits] [10 bits] [12 bits]
| | |
| | ----------- |
| | | Valore |----------|---------
| | | | |---------| /|\ | |
| | | | | | | | |
| | | | | | | Frame offset |
| | | | | | \|/ |
| | | | |---------|<------ |
| | | | | | | |
| | | | | | | x 4096 |
| | | PF offset|_________|------- |
| | | /|\ | | |
PD offset |_________|----- | | | _________|
/|\ | | | | | | |
| | | | \|/ | | \|/
_____ | | | ------>|_________| INDIRIZZO FISICO
| | \|/ | | x 4096 | |
| CR3 |-------->| | | |
|_____| | ....... | | ....... |
| | | |
Page Directory Page File
Paginazione su 386+
Linux gestisce il Controllo di Accesso soltanto sulla Paginazione, quindi Tasks differenti possono condividere lo stesso indirizzo di Segmento ma, avendo differenti valori nel registro CR3 (usato per puntare alla Page Directory), puntano effettivamente a differenti Pagine.
In User mode un Task non puo' superare il limite di 3 GB (0 x C0 00 00 00), quindi soltanto le prime 768 page directories hanno senso (768*4MB = 3GB, perche' ogni page directory e' grande 4MB).
Quando un Task entra in Kernel Mode (tramite System call o IRQ) le altre 256 pages directories sono effettivamente utilizzate e sono in comune rispetto a tutti gli altri Tasks (quindi sempre le stesse aree di memoria).
Si noti che lo Spazio Lineare del Kernel (e soltanto del Kernel) e' uguale allo Spazio Fisico, cosicche':
________________ _____
|Altri Dati Kernel|___ | | |
|-----------------| | |__| |
| Kernel |\ |____| Spazio Reale |
3 GB --->|-----------------| \ | Altri Dati Kernel |
| |\ \ | |
| ___|_\_\____|__ Spazio |
| Tasks | \ \ | Reale |
| ___|___\_\__|__ Tasks |
| | \ \ | |
| | \ \|-------------------|
| | \ |Spazio Reale Kernel|
|_________________| \|___________________|
Indirizzi Logici Indirizzi Fisici
Lo Spazio Lineare del Kernel corrisponde allo Spazio Fisico traslato di 3 GB in basso (infatti le page tables sono del tipo { "00000000", "00000001" }, di modo che possano lavorare senza virtualizzazione, riportando semplicemente il valore lineare su quello fisico).
Si noti come non esista neanche conflitto tra gli indirizzi fisici Kernel e quelli User perche' il Kernel ha un'allocazione di tipo statica (quindi conosciamo subito dove piazzare i dati): per quanto riguarda i moduli o i dati aggiuntivi, basta scegliere i valori in modo tale che non vadano in conflitto con le Page Tables gia' presenti dello User Mode.
Si parte dalla funzione ''kmem_cache_init'' (lanciata da start_kernel [init/main.c] all'avvio):
|kmem_cache_init |kmem_cache_estimate
Continuiamo con ''mem_init'' (anch'essa lanciata da start_kernel[init/main.c])
|mem_init
|free_all_bootmem
|free_all_bootmem_core
Su Linux, quando vogliamo allocate memoria, ad esempio durante la "copy_on_write" (si veda il Cap.10), chiamiamo:
|copy_mm
|allocate_mm = kmem_cache_alloc
|__kmem_cache_alloc
|kmem_cache_alloc_one
|alloc_new_slab
|kmem_cache_grow
|kmem_getpages
|__get_free_pages
|alloc_pages
|alloc_pages_pgdat
|__alloc_pages
|rmqueue
|reclaim_pages
DAFARE: Capire le Zone
Lo Swapping viene gestito dal demone ''kswapd'' (Kernel Thread).
Come tutti i Kernel Threads, ''kswapd'' ha un ciclo principale in attesa di essere svegliato.
|kswapd
|// routines di inizializzazione
|for (;;) { // Ciclo principale
|do_try_to_free_pages
|recalculate_vm_stats
|refill_inactive_scan
|run_task_queue
|interruptible_sleep_on_timeout // In attesa di essere svegliati
|}
Lo Swapping e' necessario quando dobbiamo accedere ad una pagina che non e' presente in memoria fisica: il tutto viene scatenato da un'eccezione (generata dall'accesso non autorizzato):
| Page Fault Exception
| cause by all these conditions:
| a-) User page
| b-) Read or write access
| c-) Page not present
|
|
-----------> |do_page_fault
|handle_mm_fault
|pte_alloc
|pte_alloc_one
|__get_free_page = __get_free_pages
|alloc_pages
|alloc_pages_pgdat
|__alloc_pages
|wakeup_kswapd // Svegliamo kswapd
Page Fault ICA
Per ogni tipo di NIC vi e' un device driver che lo gestisce (ad esempio per la il device NE2000 compatibile oppure per la periferica 3COM 3C59X, ecc.).
Dopo il device a basso livello, Linux chiama SEMPRE la routine di routing ad alto livello "netif_rx [net/core/dev.c]", che controlla:
Vedremo un esempio di quello che accade quando mandamo dobbiamo ricevere un pacchetto TCP, partendo dalla ''netif_rx [net/core/dev.c]'' (in sostanza analizziamo ''a grandi linee'' lo stack TCP/IP di Linux).
|netif_rx
|__skb_queue_tail
|qlen++
|* Inserimento tramite puntatori nella coda pacchetti*
|cpu_raise_softirq
|softirq_active(cpu) |= (1 << NET_RX_SOFTIRQ) // settiamo il bit NET_RX_SOFTIRQ nel vettore BH
Una volta che l'interazione IRQ e' terminata, seguiamo cosa accade in fase di scheduling quando si esegue il BH relativo alla rete che abbiamo attivato tramite NET_RX_SOFTIRQ: in pratica andiamo a chiamare la ''net_rx_action [net/core/dev.c]'' come specificato da "net_dev_init [net/core/dev.c]".
|net_rx_action
|skb = __skb_dequeue (operazione inversa della __skb_queue_tail)
|for (ptype = first_protocol; ptype < max_protocol; ptype++) // Determiniamo
|if (skb->protocol == ptype) // qual'e' il protocollo di rete
|ptype->func -> ip_rcv // come specificato sulla ''struct ip_packet_type [net/ipv4/ip_output.c]''
**** ADESSO SAPPIAMO CHE IL PACCHETTO E' DI TIPO IP ****
|ip_rcv
|NF_HOOK (ip_rcv_finish)
|ip_route_input // accediamo alla tabella di routing per capire qual e' la funzione da chiamare (qual e' cioe' l'interfaccia)
|skb->dst->input -> ip_local_deliver // come da controllo della tabella di routing la destinazione e' la macchina locale
|ip_defrag // riassembliamo i frammenti IP
|NF_HOOK (ip_local_deliver_finish)
|ipprot->handler -> tcp_v4_rcv // come da ''tcp_protocol [include/net/protocol.c]''
**** ADESSO SAPPIAMO CHE IL PACCHETTO E' TCP ****
|tcp_v4_rcv
|sk = __tcp_v4_lookup
|tcp_v4_do_rcv
|switch(sk->state)
*** Il pacchetto puo' essere mandato al Task tramite il socket aperto ***
|case TCP_ESTABLISHED:
|tcp_rcv_established
|__skb_queue_tail // accoda il pacchetto sul socket
|sk->data_ready -> sock_def_readable
|wake_up_interruptible
*** Dobbiamo gestire il 3-way TCP handshake ***
|case TCP_LISTEN:
|tcp_v4_hnd_req
|tcp_v4_search_req
|tcp_check_req
|syn_recv_sock -> tcp_v4_syn_recv_sock
|__tcp_v4_lookup_established
|tcp_rcv_state_process
*** 3-Way TCP Handshake ***
|switch(sk->state)
|case TCP_LISTEN: // Riceviamo il SYN
|conn_request -> tcp_v4_conn_request
|tcp_v4_send_synack // Mandiamo SYN + ACK
|tcp_v4_synq_add // settiamo lo stato SYN
|case TCP_SYN_SENT: // riceviamo SYN + ACK
|tcp_rcv_synsent_state_process
tcp_set_state(TCP_ESTABLISHED)
|tcp_send_ack
|tcp_transmit_skb
|queue_xmit -> ip_queue_xmit
|ip_queue_xmit2
|skb->dst->output
|case TCP_SYN_RECV: // Riceviamo ACK
|if (ACK)
|tcp_set_state(TCP_ESTABLISHED)
Descrizione:
SERVER (LISTENING) CLIENT (CONNECTING)
SYN
<-------------------
SYN + ACK
------------------->
ACK
<-------------------
3-Way TCP handshake
DAFARE
Qui vediamo come vengono allocati in memoria "stack" ed "heap".
FF.. | | <-- inizio dello stack
/|\ | | |
valori | | | | stack
piu'alti| | | \|/ crescente
di memoria | |
XX.. | | <-- attuale puntatore stack
| |
| |
| |
00.. |_________________| <-- fine dello stack [Stack Segment]
Stack
Gli indirizzi di memoria partono da 00.. (che e' il dove il Segmento dello Stack comincia) e aumentano verso il valore FF.., mentre lo stack cresce all'opposto, cioe' dal valore FF.. al valoce 00.. verso valori bassi di memoria
XX.. e' il valore attuale dello Stack Pointer.
Lo Stack viene solitamente usato per:
Ad esempio una classica funzione
|int funzione (parametro_1, parametro_2, ..., parametro_N) {
|dichiarazione variabile_1;
|dichiarazione variabile_2;
..
|dichiarazione variabile_N;
|// Corpo della funzione
|dichiarazione variabile_dinamica_1;
|dichiarazione variabile_dinamica_2;
..
|dichiarazione variabile_dinamica_N;
|// Il Codice e' all'interno del Segmento di Codice, non nel Segmento Dati/Stack!
|return (ret-type) valore; // Spesso finisce in qualche registro, per 386+: registro ''eax''
|}
utilizza uno stack del tipo
| |
| 1. parametro_1 pushato| \
S | 2. parameter_2 pushato| | Prima della
T | ................... | | chiamata
A | N. parameter_N pushato| /
C | *Indirizzo di Ritorno*| -- Chiamata
K | 1. variabile_1 locale | \
| 2. variabile_2 locale | | Dopo la
| ................. | | chiamata
| N. variabile_N locale | /
| |
... ... Stack
... ... Libero
| |
H | N.variabile_N dinamica| \
E | ................... | | Allocato dalle
A | 2.variabile_2 dinamica| | malloc & kmalloc
P | 1.variabile_1 dinamica| /
|_______________________|
Utilizzo tipico dello Stack
Nota: L'ordine delle variabile puo' essere differente a seconda dell'architettura hardware (come sempre qui si ipotizza l'utilizzo del 386+).
Distinguiamo 2 2 concetti:
Spesso i Processi vengono chiamati Task o Thread.
2 tipi di locks:
Il meccanismo della Copy_on_write consente di ridurre l'utilizzo di memoria, postponendo l'allocazione per un nuovo Thread fino a quando non e' strettamente necessario.
Ad esempio, quando un Task esegue la "fork()" per creare un nuovo Processo, le pagine del vecchio processo non vengono copiate, ma vengono soltanto "referenziate" in modalita' READ ONLY (sia per il padre che per il figlio) in modo che, quando qualcuno andra' a scrivervi sopra, l'eccezione generata si occupera' di creare una nuova copia della pagina marcandola, questa volta READ + WRITE.
Ecco uno schema riassuntivo:
1-) La Pagina X e' condivisa tra Il Task Padre e quello figlio
Task Padre
| | Accesso RO ________
| |---------->|Pagina X|
|_________| |________|
/|\
|
Task Figlio |
| | Accesso RO |
| |----------------
|_________|
2-) Richiesta di Scrittura
Task Figlio
| | Accesso RO ________
| |---------->|Pagina X| (tentativo di scrittura)
|_________| |________| |
/|\ |
| \|/
Task Figlio | ECCEZIONE
| | Accesso RO |
| |----------------
|_________|
3-) Configurazione Finale: il Task Padre e quello Figlio hanno ognuno una copia indipendente della Pagina, X e Y
Task Padre
| | Accesso RW ________
| |---------->|Pagina X|
|_________| |________|
Task Figlio
| | Accesso RW ________
| |---------->|Pagina Y|
|_________| |________|
bbootsect.s [arch/i386/boot] setup.S (+video.S) head.S (+misc.c) [arch/i386/boot/compressed] start_kernel [init/main.c]
I Descrittori sono delle strutture dati usate nell'architettura i386+ per utilizzare la memoria virtuale.
L'IRQ e' un segnale asincrono mandato al microprocessore per avvertirlo che un lavoro e' stato completato o che si e' verificato un errore.
|<--> IRQ(0) [Timer]
|<--> IRQ(1) [Device 1]
| ..
|<--> IRQ(n) [Device n]
_____________________________|
/|\ /|\ /|\
| | |
\|/ \|/ \|/
Task(1) Task(2) .. Task(N)
Schema di interazione Tasks-IRQ
Un O.S. tipico utilizza molti segnali IRQ per interrompere la normale esecuzione di un processo e gestire del lavoro relativo ad un device. Lo schema e' il seguente:
In particolare Linux, quando arriva un IRQ esegue prima di tutto la funzione di incapsulazione IRQ (chiamata "interrupt0x??"), e soltanto dopo l'IRQ(i)_handler ufficile. Questo permette di eseguire alcune operazioni comuni a tutti gli IRQ come la gestione del TimeSlice.
Definizione
#define list_entry(ptr, type, member) \ ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
Significato:
La macro "list_entry" viene usata per ricavare il puntatore ad una struttura utilizzando soltanto un elemento interno alla struttura.
Esempio
struct __wait_queue {
unsigned int flags;
struct task_struct * task;
struct list_head task_list;
};
struct list_head {
struct list_head *next, *prev;
};
// e con la definizione del tipo:
typedef struct __wait_queue wait_queue_t;
// avremo:
wait_queue_t *out list_entry(tmp, wait_queue_t, task_list);
// dove tmp punta a list_head
Quindi, in questo caso, usando il puntatore *tmp [list_head] troviamo il puntatore *out [wait_queue_t].
____________ <---- *out [abbiamo calcolato questo] |flags | /|\ |task *--> | | |task_list |<---- list_entry | prev * -->| | | | next * -->| | | |____________| ----- *tmp [partendo da questo]
Files:
Funzioni:
Funzioni chiamate:
InterCallings Analysis:
|sleep_on
|init_waitqueue_entry --
|__add_wait_queue | Accodamento della richiesta sulla lista della risorsa
|list_add |
|__list_add --
|schedule --- Attesa che la richiesta venga eseguita
|__remove_wait_queue --
|list_del | Disaccodamento richiesta dalla lista della risorsa
|__list_del --
Descrizione:
Ogni risorsa (in teoria ogni oggetto condiviso tra piu' utenti e piu' processi), ha una cosa per gestire TUTTI i Tasks che la richiedono.
Questo metodo di accodamento viene chiamato "wait queue" e consiste di molti elementi chiamati"wait queue element":
*** struttura wait queue [include/linux/wait.h] ***
struct __wait_queue {
unsigned int flags;
struct task_struct * task;
struct list_head task_list;
}
struct list_head {
struct list_head *next, *prev;
};
Rappresentazione grafica:
*** elemento wait queue ***
/|\
|
<--[prev *, flags, task *, next *]-->
*** Lista wait queue ***
/|\ /|\ /|\ /|\
| | | |
--> <--[task1]--> <--[task2]--> <--[task3]--> .... <--[taskN]--> <--
| |
|__________________________________________________________________|
*** Testa wait queue ***
task1 <--[prev *, lock, next *]--> taskN
La Testa "wait queue" punta al primo (con next *) e last (com prev *) all'ultimo della lista "wait queue".
Quando deve venire inserito un nuovo elemento viene chiamata la "__add_wait_queue" [include/linux/wait.h], dopo di che verra' eseguita la generica routine "list_add" [include/linux/wait.h]:
*** funzione list_add [include/linux/list.h] ***
// classico inserimento doppio linkato
static __inline__ void __list_add (struct list_head * new, \
struct list_head * prev, \
struct list_head * next) {
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
Per completare la descrizione vediamo anche la "__list_del" [include/linux/list.h] chiamata da "list_del" [include/linux/list.h] all'interno di "remove_wait_queue" [include/linux/wait.h]:
*** funzione list_del [include/linux/list.h] ***
// classica cancellazione doppio linkato
static __inline__ void __list_del (struct list_head * prev, struct list_head * next) {
next->prev = prev;
prev->next = next;
}
Una lista tipica (o coda) viene normalmente gestita allocandola nello Heap (si veda il Cap.10 per definizioni e gestione delle variabili nello Heap e nello Stack).
Qui invece, allochiamo ''Wait Queue'' in una variabile locale (quindi nello Stack), dopo di che la funzione viene interrotta dalla schedulazione e, al risveglio, la variabile locale verra' cancellata
new task <----| task1 <------| task2 <------|
| | |
| | |
|..........| | |..........| | |..........| |
|wait.flags| | |wait.flags| | |wait.flags| |
|wait.task_|____| |wait.task_|____| |wait.task_|____|
|wait.prev |--> |wait.prev |--> |wait.prev |-->
|wait.next |--> |wait.next |--> |wait.next |-->
|.. | |.. | |.. |
|schedule()| |schedule()| |schedule()|
|..........| |..........| |..........|
|__________| |__________| |__________|
Stack Stack Stack
Linux e' scritto in linguaggio ''C'', e come ogni applicazione usa:
Quando una variabile Statica viene modificata da un modulo, tutti gli altri moduli potranno avere a disposizione il nuovo valore.
Le variabili Statiche sotto Linux sono molto importanti, perche' rappresentano l'unico metodo per aggiungere nuove funzionalita' al Kernel: tipicamente puntano alla testa di liste dove sono memorizzati elementi ''registrati'', che possono essere:
_______ _______ _______
Variabile Globale ------> |Item(1)| -> |Item(2)| -> |Item(3)| ..
|_______| |_______| |_______|
__________________
Current ----------------> | Processo attuale |
|__________________|
Current punta alla struttura ''task_struct'', che contiene tutte le informazioni relative ad un Processo:
Current non e' una vera variabile, piuttosto una macro:
static inline struct task_struct * get_current(void) {
struct task_struct *current;
__asm__("andl %%esp,%0; ":"=r" (current) : "0" (~8191UL));
return current;
}
#define current get_current()
Le linee sopra prendono il valore di ''ESP'' (stack pointer) e lo rendono disponibile come una variabile, che poi verra' usata per puntare ad una struttura task_struct.
Dall'elemento ''current'' possiamo accedere quindi direttamente ad ogni struttura dati Kernel del processo (ready, stopped o in qualunque altro stato), ad esempio possiamo cambiargli lo stato (come fa ad esempio un driver di I/O), il PID, la presenza o meno nella Ready List o nella Blocked List, ecc.
______ _______ ______
file_systems ------> | ext2 | -> | msdos | -> | ntfs |
[fs/super.c] |______| |_______| |______|
Quando digitiamo il comando ''modprobe some_fs'' verra' aggiunta una nuova entry alla lista dei file systems, mentre con il comando ''rmmod'' la andremo a rimuovere.
______ _______ ______
mount_hash_table ---->| / | -> | /usr | -> | /var |
[fs/namespace.c] |______| |_______| |______|
Il comando ''mount'' permette di aggiungere un file system alla lista dei fs gia' montati nel sistema, mentre la umount cancella la relativa voce.
______ _______ ______
ptype_all ------>| ip | -> | x25 | -> | ipv6 |
[net/core/dev.c] |______| |_______| |______|
Ad esempio, se si vuole aggiungere l'IPv6 (caricando il modulo relativo) sara' necessario inserire la voce del Network Packet Type nella lista.
______ _______ _______
inet_protocol_base ----->| icmp | -> | tcp | -> | udp |
[net/ipv4/protocol.c] |______| |_______| |_______|
Ogni Network Packet Type puo' avere all'interno una serie di protocolli che si possono aggiungere alla lista (come IPv6 che ha i protocolli TCPv6).
______ _______ _______
inet6_protos ----------->|icmpv6| -> | tcpv6 | -> | udpv6 |
[net/ipv6/protocol.c] |______| |_______| |_______|
______ _______ _______
dev_base --------------->| lo | -> | eth0 | -> | ppp0 |
[drivers/core/Space.c] |______| |_______| |_______|
______ _______ ________
chrdevs ---------------->| lp | -> | keyb | -> | serial |
[fs/devices.c] |______| |_______| |________|
''chrdevs'' non e' in realta' un vero puntatore ad una lista, piuttosto un vettore standard.
______ ______ ________
bdev_hashtable --------->| fd | -> | hd | -> | scsi |
[fs/block_dev.c] |______| |______| |________|
''bdev_hashtable'' e' un vettore di hash
Sorgenti Ufficiali del Kernel e Patches
Ottima documentazione sul Kernel