Il Kernel del Sistema Operativo Thix Design e Architettura Edizione 1.0, Thix versione 0.2 Giugno 1995 Tudor Hulubei Supervisore: Prof. Serban Petrescu Department of Computer Science and Engineering "Politehcnica" University of Bucharest - Romania -------------------------------------------------------------------------------- INDICE DEI CONTENUTI: -------------------------------------------------------------------------------- INTRODUZIONE Questo documento presenta il kernel UNIX che ho scritto nel 1994-1995, E' un'implementazione pressoché completa dello standard POSIX.1(IEEE Std 1003.1-1988). Il mio scopo principale è stato quello di imparare l'architettura e il design dei sistemi operativi, algoritmi del kernel, allocazione di risorse, schedulazione dei processi, regole di memory management ecc. Il risultato è stato un nuovo kernel UNIX, POSIX compliant, con molte caratteristiche di un sistema operativo reale, come ad esempio la memoria virtuale, il paging su richiesta, la protezione della memoria, lo swapping etc. Non è certo perfetto e probabilmente è pieno di bug, ma con il tempo verranno fixati e il kernel diverrà sempre più stabile. Poiché su internet sono disponibili molti programmi di qualità con codice sorgente completamente FREE, per primo lo GNU project, ho eseguito il porting di molti di questi sul mio sistema, con l'idea di raggiungere un vero stato di funzionalità. Copyright (c) 1999,2000 Tudor Hulubei mailto:tudor@cs.unh.edu Questo documento è inteso come una descrizione generale del kernel, non come una dettagliata descrizione del codice sorgente. Naturalmente contiene esempi di strutture dati del kernel e algoritmi, ma solo per rendere l'idea dell'attuale implementazione. Alcuni esempi sono abbastanza corposi, specialmente la struttura del TSS, la routine del page fault e il loop principale dello swapper. Ho provato a stringarli al massimo, rimovendo tutte le cose che nel contesto non sono importanti, ma c'è un limite a quanto un algoritmo possa essere ridotto, e in qualche caso sono stato costretto a lasciarlo com'era, per essere sicuro che tutti i passi importanti fossero descritti. Comunque, per una migliore comprensione generale del design del kernel, sono inclusi in appendice i sorgenti completi del kernel (inclusi tutti i file header e delle utility addizionali come fsck e mkfs). Per cortesia consultate i sorgenti quando gli esempi in questa sede esposti risultino confusi o incompleti. KERNEL DESIGN Thix è un kernel monolitico. Questi tipi di kernel sono di solito meno modulari rispetto ai microkernel, questo perché parti totalmente indipendenti di codice come il filesystem e la gestione della memoria e dei processi, sono compilati insieme dentro una grossa immagine chiamata appunto "il kernel" e l'interfaccia tra di loro non è molto ben definita. Questi diversi moduli del kernel comunicano tra di loro usando delle normali istruzioni di "call", mentre i moduli basati su di un microkernel usano il meccanismo dell'IPC per svolgere le stesse chiamate. Questa lacuna della "reale" modularità, fa la progettazione dei kernel monolitici un poco più complicata, ma questa documentazione è strutturata in modo che non dovreste avere problemi nel capire quale parte del kernel svolge il tale compito. Per iniziare, descriverò l'implementazione dello scheduling dei processi, i segnali, le chiamate di sistema, interrupts ed eccezioni, ecc. Dopo presenterò il meccanismo della memoria virtuale, il file system e i device driver. Infine ci sarà una breve descrizione della startup-sequence del sistema. Processi: Gestione dei processi. Scheduling: Scheduling dei processi. Sleep and Wakeup: Primitive di Sleep e Wakeup. Segnali: Handling dei Segnali. Timers: Timers del Kernel. Chiamate di sistema: Interfaccia delle chiamate di sistema. Interrupts e Eccezioni: Handling degli Interrupts e delle Eccezioni. I/O: I/O a basso livello -------------------------------------------------------------------------------- PROCESSI -------------------------------------------------------------------------------- Il compito principale di un sistema operativo è quello di far girare i processi. Un sistema operativo decente deve essere anche in grado di far girare più processi allo stesso tempo. Questo è chiamato "multitasking". I processi devono essere protetti da tutti gli altri, in questo modo il loro ambiente di esecuzione non sarà corrotto dagli eventuali errori degli altri processi. Thix è un kernel multitasking, così, come spiegato in precedenza, è capace di far girare più processi contemporaneamente. Fornisce anche la protezione della memoria ed è fault tolerant. E' pesantemente basato sull'architettura dei processori Intel 80386/486, sfruttandone al massimo le potenzialità. Il kernel fornisce ad ogni processo il suo spazio di indirizzamento (vedi la sezione: Gestione della memoria virtuale) e tiene traccia di tutte le informazioni circa le strutture dati dei processi, statistiche, descrittori dei file aperti, ecc, in una struttura separata chiamata TSS. la tabella `u_area[]' contiene un numero di strutture TSS uguale alla costante SYSTEM_PROCESS_MAX. SYSTEM_OPEN_MAX è il massimo numero di processi cui è permesso di girare contemporaneamente, e può essere configurato asseconda del bisogno al momento della compilazione del kernel. Ogni struttura contenuta nella tabella `u_area[]', è mappata con il Task State Segment (Intel 80386+), una struttura specifica del processore che contiene tutti i registri del processore (sia generali che di segmento), flags, la page directory e i puntatori alla descriptor table locale. In aggiunta ai campi richiesti da Intel, la tabella 'u_area[]' contiene anche informazioni specifiche del processo, come il PID (Process IDentifyer), statistiche, timers, ID di gruppo e di utente, maschere dei segnali, controlli dei terminali ecc. Internamente il kernel identifica un processo attraverso il proprio ID di processo (che altro non è che l'indice del processo dentro la tabella `u_area[]'). Di seguito riporto la struttura completa di una entry di `u_area[]' (una struttura TSS). Dovrebbe dare un'idea del tipo di informazioni mantenute dal kernel per ogni processo che gira. typedef struct { /* i80386 TSS */ unsigned BackLink; unsigned ESP0; unsigned SS0; unsigned ESP1; unsigned SS1; unsigned ESP2; unsigned SS2; PGTBL **PGDIR; unsigned EIP; unsigned EFLAGS; unsigned EAX; unsigned ECX; unsigned EDX; unsigned EBX; unsigned ESP; unsigned EBP; unsigned ESI; unsigned EDI; unsigned ES; unsigned CS; unsigned SS; unsigned DS; unsigned FS; unsigned GS; unsigned LDT; unsigned IO_bitmap_offset; /* End of i80386 TSS. */ /* i80386 TSS auxiliary data (process data). */ __pid_t pid; /* Process id. */ __pid_t ppid; /* Parent process id. */ __pid_t session; /* Session id. */ __pid_t pgrp; /* Process group id. */ int pkpid; /* Parent kernel process id. */ unsigned istack; /* Process internal stack (kernel mode stack). */ int text_pages; /* Number of text pages in the executable. */ int data_pages; /* Number of data pages in the executable. */ int bss_pages; /* Number of bss pages in the executable . */ unsigned brk; /* Break value. */ unsigned stk; /* Stack value. */ int max_brk; /* Maximum break value in number of pages. */ int max_stack; /* Maximum stack value in number of pages. */ void *sleep_address; /* Process current sleeping address. */ int wakeup_priority; /* Process current wakeup priority. */ int old_cpu_usage; /* CPU usage before going to sleep. */ _itimerval real; /* Real interval timer. */ _itimerval virtual; /* Virtual interval timer. */ _itimerval prof; /* Profile interval timer. */ rlimits limits; /* Resource limits. */ struct rusage usage; /* Resource usage. */ struct rusage cusage; /* Dead children resource usage. */ int cwd_inode; /* Current directory inode. */ unsigned short ufdt[256];/* User file descriptors table. */ unsigned close_on_exec[8]; /* Close on exec bits. */ int a_out_inode; /* Executable inode. */ int ff_ufd; /* First free user file descriptor. */ int umask; /* Process umask. */ __uid_t ruid, euid, suid; /* Real, effective and saved user ids. */ __gid_t rgid, egid, sgid; /* Real, effective and saved group ids. */ char access_flag; /* Flag used by sys_access() to force namei() to use ruid/rgid instead of euid/egid. */ char kwreq; /* Kernel write request flag. Set when a system call tries to write data in the user address space because page protection faults don't occur when running in kernel mode. The page protection fault routine is called "by hand" from the page fault routine. This is only useful when running on i386. */ char children; /* Number of children. */ char swapable; /* Swapable flag. Used by swapper to determine if the process is currently swapable. */ char status; /* Process status. */ char exec_flag; /* The process has executed an 'exec' system call since it was forked. It will be used by the setpgid() system call. */ char leader; /* The process is a session leader. */ unsigned short exit_code;/* Process exit code. */ __sigset_t sigpending; /* Mask of pending signals. */ __sigset_t sigblocked; /* Mask of blocked signals. */ struct sigaction sigactions[_NSIG]; /* Sigaction structures. */ __time_t start_time; /* Process start time. */ __dev_t ctty; /* Controlling terminal major/minor numbers. */ char **argv; /* Command line arguments pointer. */ char **envp; /* Environment pointer. */ char args[132]; /* Command line string. I hope I will get rid of this one day... */ } TSS; -------------------------------------------------------------------------------- SCHEDULING DEI PROCESSI -------------------------------------------------------------------------------- I sistemi operativi multitasking necessitano di un algoritmo per eseguire processi differenti simultaneamente. Lo scheduler dei processi deciderà quale processo riceverà l'uso della CPU in un dato momento, in dipendenza dalla priorità di ogni processo pronto ad essere eseguito. Lo scheduler di Thix è piccolo e veloce. Esso mantiene una lista di puntatori alle liste di processo, una per ogni livello di priorità. La priorità a livello user è un intero compreso tra -19 e 19, dove un livello più alto significa priorità maggiore, mentre il kernel lavora con livelli di priorità compresi tra 1 e 55, anche qui il livello alto corrisponde ad una priorità maggiore. Il kernel divide le priorità in tre categorie: 1. Priorità a livello utente (user level). Questi livelli di priorità sono usati dai processi utente e mappate sui livelli di priorità del kernel compresi tra 1 e 39. 2. Livelli di priorità "Interruptible". Questi sono i livelli di priorità usati dai processi del kernel che necessitano di aspettare per un evento "non sicuro" (per esempio eventi che non sappiamo se avverranno, vedi la sezione Sleep and Wakeup. 3. Livelli di priorità "Uninterruptible".Questi sono i livelli di priorità usati dai processi del kernel che aspettano un evento "sicuro". Ogni volta che lo scheduler è chiamato, prenderà un processo dalla lista di priorità più alta che ne ha uno, lo muove nella lista di priorità più bassa e lo esegue. Quando tutti i processi che si trovano nello stato "ready to run" (pronto all'esecuzione) hanno raggiunto il livello di priorità più bassa, sono spostati indietro nella lista corrispondente al proprio livello di priorità base. Lo scheduler immagazzinerà l'ultimo livello di priorità usato, ed inizierà a controllare dalla lista libera di priorità più alta solo quando un processo cessa. Nel caso standard, il controllo per i processi "ready to run" inizia dal livello di priorità immagazzinato e cercherà un processo eseguibile al suo primo passo. A causa di questo e del fatto che il codice assembly generato dal compilatore GNU C per il loop principale esattamente lungo quattro istruzioni di codice macchina, lo scheduler è realmente molto veloce. I processori Intel resettano la loro cache interna ad ogni cambio di contesto. Questa è una cosa normale, poiché dopo un cambio di contesto, il nuovo processo schedulato userà un'altra gerarchia di tabelle di pagine, e i riferimenti presenti nella cache sarebbero comunque invalidi. Comunque, quando il nuovo processo schedulato è lo stesso del precedente, non sarà fatto nessun cambio di contesto, per non consumare inutilmente del tempo della CPU e preservare il contenuto della cache. In questo caso particolare, se lo scheduler accede a locazioni di memoria molto sparpagliate quando tenta di cercare un nuovo processo da eseguire, molte delle entrate nelle pagina della cache saranno perse. Questo è il motivo per cui lo scheduler non mantiene le sue strutture dati all'interno della struttura 'u_area[]', una grossa struttura relativa ad ogni singolo processo usata per memorizzare informazioni circa tutti i processi del sistema, ma in strutture dati separate, per provare a ridurre il più possibile i cambiamenti all'interno della cache. ogni Entry di questa struttura dati è così composta: typedef struct { unsigned char prev; unsigned char next; unsigned char priority; /* The process's base priority. */ unsigned char cpu_usage; /* Current process's ticks left. */ } sched_struct; Questo è il loop principale dello schedulatore di processi di Thix. current_kpid e current_pid sono due variabili globali che contengono l'indice del processo corrente dentro la tabella dei processi e il suo ID. int scheduler(void) { int priority; int first_priority_level; int kpid, old_kpid = current_kpid; /* current_kpid == IDLE when the process calling scheduler() has just exited. */ if (current_kpid != IDLE) { first_priority_level = sched_touched ? MAX_PRIORITY_LEVEL : sched_data[current_kpid].cpu_usage; /* If the process is asleep, don't try to delete it from the scheduler list. */ if (this->status != PROCESS_ASLEEP) { delete_schedulable_process(current_kpid); new_schedulable_process(current_kpid, --sched_data[current_kpid].cpu_usage); } } else first_priority_level = MAX_PRIORITY_LEVEL; sched_touched = 0; /* Loop through the priority lists, trying to find an eligible process in their heads. In most cases, we will find one at the very first loop. However, when a new process has been waked up, we have to start searching from the highest priority list. The process waked up is normally inserted in the head of a high priority list so even in this situation there is a *big* chance to find it quickly. */ for (priority = first_priority_level; priority; priority--) if (sched_head[priority]) { kpid = sched_head[priority]; goto found; } /* No process has been found yet. All the processes have exceeded their time quota. So we have to reinsert them into their base priority list. */ while ((kpid = sched_head[0])) { delete_schedulable_process(kpid); new_schedulable_process(kpid, sched_data[kpid].priority); } /* Rescan the priority lists. Maybe we can find a process ready to run this time. */ for (priority = MAX_PRIORITY_LEVEL; priority; priority--) if (sched_head[priority]) { kpid = sched_head[priority]; goto found; } /* Bad luck. Invoke IDLE. */ old_kpid = -1; kpid = IDLE; found: /* Ok, we have found an eligible process. */ this = &u_area[current_kpid = kpid]; tss_descr[current_kpid].low_flags = VALID_TSS_ARB; /* Don't perform a context switch if the new selected process is the same as the old one. */ if (current_kpid == old_kpid) return -1; /* Returns the kernel process id of the process to switch to. */ return current_kpid; } La funzione new_schedulable_process() aggiunge un processo alla lista dei processi schedulabili corrispondente ad un data priorità. La funzione delete_schedulable_priority() rimuove un processo dalla lista dello scheduler corrispondente alla sua priorità e ritorna il suo uso della cpu. Per la natura di quest'implementazione, il processo è sempre trovato in cima alla lista e, come risultato, aggiungere o rimuovere i processi dalla lista dello scheduler corrisponde semplicemente a settare qualche campo della struttura sched_data[]. inline void new_schedulable_process(int kpid, int priority) { sched_data[kpid].cpu_usage = priority; sched_data[kpid].next = 0; if (sched_head[priority]) sched_data[sched_tail[priority]].next = kpid; else sched_head[priority] = kpid; sched_tail[priority] = kpid; } -------------------------------------------------------------------------------- SLEEP e WAKEUP -------------------------------------------------------------------------------- Tra le routine del kernel più usate ci sono sleep() e wakeup(). Ogni volta che un processo deve aspettare perché una risorsa diventi disponibile, o accada un determinato evento, sarà mandato in sleep finché il processo che usa quella risorsa non la lascia libera. Questo significa che il processo cambia i suo stato da "ready to run" a "asleep" e ancora a "ready to run" quando la risorsa diventa disponibile o accade l'evento atteso. Quando il processo è risvegliato, deve controllare se la risorsa è realmente disponibile ed eventualmente tornare in sleep() se un'altro processo è stato schedulato prima di lui ed ha nuovamente bloccato la risorsa. Ci sono molti tipi di eventi per i quali un processo rimane in stato di attesa: completamento dell'I/O, risorse bloccate che devono sbloccarsi, pagine di memoria libera, segnali, I/O dai terminali ecc. Poiché qualche evento, come il completamento dell'I/O, avverranno sicuramente ed alcuni altri, come l'input da terminale, non è detto che avverranno, il kernel usa differenti priorità di sleep per processi che aspettano diversi tipi di eventi ("sicuri" oppure no). I processi che aspettano il verificarsi di un evento "sicuro" andranno in sleeping con priorità alta e non possono essere interrotti, i processi che aspettano un evento "incerto" andranno in sleeping con priorità più basse e potranno essere interrotti tramite dei segnali. Dobbiamo differenziare le priorità usate per gli eventi "sicuri" perché è più importante far girare un processo che si risveglia per il completamente di una richiesta di I/O rispetto ad un processo che si risveglia perché il superblock è diventato disponibile. Il completamente di un I/O potrebbe liberare dei buffer che potrebbero servire al secondo processo, quindi non possiamo fare altrimenti, per non inficiare le prestazioni del sistema. Come risultato di questa filosofia, saranno usati otto diversi livelli di priorità per processi in sleeping ad un livello di priorità "interruptible" e otto per processi in sleeping ad un livello di priorità "non interruptible": /* Interruptible priority levels (40-47): */ #define WAIT_PIPE 40 #define WAIT_SIGNAL 42 #define WAIT_CHILD_EXIT 43 #define WAIT_TTY_OUTPUT 45 #define WAIT_TTY_INPUT 47 /* Uninterruptible priority levels (48-55): */ #define WAIT_PAGE 48 #define WAIT_INODE 49 #define WAIT_SUPERBLOCK 50 #define WAIT_SYNC 51 #define WAIT_BUFFER 52 #define WAIT_DEVICE_BUSY 53 #define WAIT_DEVICE_IO 54 #define WAIT_SWAPPER 55 -------------------------------------------------------------------------------- SEGNALI -------------------------------------------------------------------------------- Thix fornisce un'implementazione POSIX.1 dei segnali. I segnali possono essere bloccati o sbloccati, un processo può specificare un maschera per i segnali, oppure può leggere la maschera dei segnali pendenti. Il kernel fondamentalmente implementa queste chiamate di sistema: `sigprocmask'(), `sigpending'(), `sigsuspend'() e `sigaction'(). Le chiamate di sistema di vecchio stile come `signal'() sono tutte emulate nella libreria C usando le funzioni POSIX. L'handling dei segnali è stato implementato usando tre campi della struttura u_area[] per tenere traccia dei segnali pending, blocked e action. I campi `sigpending' e `sigblocked' contengono un bit per ogni segnale (i segnali sono numerati da uno a 31), mentre l'array `sigactions' contiene una struttura del tipo `struct sigaction' per ogni segnale. { .... __sigset_t sigpending; /* mask of pending signals. */ __sigset_t sigblocked; /* mask of blocked signals. */ struct sigaction sigactions[_NSIG]; /* sigaction structures */ .... } Il kernel controlla i segnali ad ogni transizione da livello kernel a livello utente, mediante la chiamata alla funzione `__issig'() prima di ritornare in user mode. Se il processo riceve un segnale, il suo stack corrente è modificato per permettere un salto al corrispondente handler del segnale (se presente) prima di ritornare al codice dove il processo è entrato in kernel mode in seguito ad un interrupt, un'eccezione o una chiamata di sistema. I segnali sono anche controllati prima di entrare in sleeping, altrimenti i processi potrebbero ignorare n segnale recente e andare in sleep per sempre. Ogni volta che un processo vuole mandare un segnali ad un'altro processo, esso setta il bit corrispondente nel campo `sigpending' del processo di destinazione. Dato un ID di processo del kernel e un numero di segnale, la routine kill_kpid() invia questo segnale al processo target. L'ID di processo del kernel non è accessibile a livello utente, ma quando è invocata la chiamata di sistema kill(), l'ID di processo è convertita nell'ID di processo del kernel e quindi passata alla routine. void kill_kpid(int kpid, int signum) { /* The swapper can't receive signals. It it does, something really bad happened, so just PANIC! */ if (kpid == SWAPPER) PANIC("Swapper received signal %d\n", signum); /* Don't send ignored signals to processes, unless we are dealing with SIGCHLD. */ if (u_area[kpid].sigactions[signum].sa_handler == SIG_IGN && signum != SIGCHLD) return; /* Send the signal. */ u_area[kpid].sigpending |= 1 << signum; /* If the process is asleep, wake it up. */ if (status(kpid) == PROCESS_ASLEEP && wakeup_priority(kpid) < U_THRESHOLD_PRIORITY) wakeup_process(kpid); } La prima volta il kernel controlla i segnali settati del processo target (durante `__issig'() o in `sleep'(), come spiegato in precedenza) rileva i segnali pendenti (semplicemente controllando se u_area[].sigpending == 0) e intraprende le azioni del caso. Questi sono i segnali definiti nel file thix/signals.h #define SIGHUP 1 /* Hangup (POSIX). */ #define SIGINT 2 /* Interrupt (ANSI). */ #define SIGQUIT 3 /* Quit (POSIX). */ #define SIGILL 4 /* Illegal instruction (ANSI). */ #define SIGABRT SIGIOT /* Abort (ANSI). */ #define SIGTRAP 5 /* Trace trap (POSIX). */ #define SIGIOT 6 /* IOT trap. */ #define SIGEMT 7 /* EMT trap. */ #define SIGFPE 8 /* Floating-point exception (ANSI). */ #define SIGKILL 9 /* Kill, unblockable (POSIX). */ #define SIGBUS 10 /* Bus error. */ #define SIGSEGV 11 /* Segmentation violation (ANSI). */ #define SIGSYS 12 /* Bad argument to system call*/ #define SIGPIPE 13 /* Broken pipe (POSIX). */ #define SIGALRM 14 /* Alarm clock (POSIX). */ #define SIGTERM 15 /* Termination (ANSI). */ #define SIGUSR1 16 /* User-defined signal 1 (POSIX). */ #define SIGUSR2 17 /* User-defined signal 2 (POSIX). */ #define SIGCHLD 18 /* Child status has changed (POSIX). */ #define SIGCLD SIGCHLD /* Same as SIGCHLD (System V). */ #define SIGPWR 19 /* Power going down. */ #define SIGWINCH 20 /* Window size change. */ #define SIGURG 21 /* Urgent condition on socket.*/ #define SIGIO SIGPOLL /* I/O now possible. */ #define SIGPOLL 22 /* Same as SIGIO? (SVID). */ #define SIGSTOP 23 /* Stop, unblockable (POSIX). */ #define SIGTSTP 24 /* Keyboard stop (POSIX). */ #define SIGCONT 25 /* Continue (POSIX). */ #define SIGTTIN 26 /* Background read from tty (POSIX). */ #define SIGTTOU 27 /* Background write to tty (POSIX). */ #define SIGVTALRM 28 /* Virtual alarm clock. */ #define SIGPROF 29 /* Profiling alarm clock. */ #define SIGXCPU 30 /* CPU limit exceeded. */ #define SIGXFSZ 31 /* File size limit exceeded. */ Notare che alcuni di loro sono definiti solo per compatibilià con altri tipi di sistemi UNIX, ma non correntemente usati da Thix. L'attuale implementazione del kernel non effettua il dump del "core" dei processi quando riceve dei segnali che normalmente dovrebbero sortire tal effetto. Allo stato attuale al kernel manca anche la possibilità di debugging e profiling del codice. -------------------------------------------------------------------------------- TIMERS del KERNEL -------------------------------------------------------------------------------- Il clock del sistema viaggia a 100Hz. Così 100 volte al secondo l'hardware genera un interrupt e la funzione 'timer'() è chiamata. Sfortunatamente, deve anche fare un sacco di cose. Prima di tutto il kernel deve tener traccia del passare del tempo.Quindi dovrebbe calcolare delle statistiche tipo il tempo speso in user mode o in kernel mode, in base a quale livello è stato eseguito il processo corrente al momento dell'interrupt. Dovrebbe anche controllare se l'intervallo del timer è scaduto, reale, virtuale o di profiling che sia. Se così fosse, il kernel invia un segnale al processo che ha schedulato quell'intervallo del timer. Fortunatamente gli intervalli dei timer sono stati implementati con liste concatenate di intervalli di tempo ordinati, per cui il prossimo timer che scadrà è sempre in testa alla lista. Il kernel usa questo metodo per spendere il minor tempo possibile nella routine di interrupt. Molti device drivers, come il driver del floppy o dell'hard disk necessitano di un modo per tener traccia del tempo per rilevare i timeouts. Così ognuno di questi drivers registra una routine timer all'avvio del sistema, e questa routine è chiamata ad ogni interrupt del timer. Il driver del floppy usa questo sistema per rilevare i timeouts e fermare il motore dopo pochi secondi se non sussistono richieste al floppy stesso. Il driver dell'hard disk usa il timer solo per rilevare i timeouts. request occured. Il meccanismo dei timer probabilmente potrebbe essere migliorato per gestire una sorta di intervallo di tempo, perché potrebbe essere una buona idea usare un timer invece di chiamare il driver del timer ad ogni interrupt hardware, solo per controllare se sono avvenuti dei timeouts. un esempio migliore è quello del driver dei terminali virtuali che voglia implementare uno screen saver. Usando per questo compito un normale timer di sistema potrebbe non essere appropriato. -------------------------------------------------------------------------------- CHIAMATE di SISTEMA -------------------------------------------------------------------------------- Le chiamate di sistema sono implementate come interrupt software (int 0x30). I parametri sono passati sullo stack e il numero della chiamata di sistema nel registro %eax. Il sistema rileva chiamate invalide ed esegue un controllo sui parametri passati. non c'è modo per un processo di danneggiare il kernel passando parametri invalidi o puntatori a chiamate di sistema. Passando un puntatore invalido a una chiamata di sistema è molto pericoloso, perché girare in kernel mode significa avere accesso all'intero spazio di memoria virtuale (inclusa l'area dati e codice del kernel), così scrivendo ad un dato puntatore senza prima controllare si potrebbe corrompere la memoria occupata dal kernel. Non controllare un descrittore di file passato come parametro alla funzione di sistema write(), per esempio, potrebbe significare scrivere a un indirizzo invalido che potrebbe essere fatale. Le chiamate di sistema sono strettamente legate alla libreria C. Dopo essere entrati nel kernel mode usando un'istruzione 'int 0x30', il kernel controlla il numero della chiamata e , se tutto è andato bene, setta i registri di segmento (%ds e %es dovrebbero puntare al segmento dati del kernel) e quindi invoca la corrispondente funzione del kernel. Alla fine della chiamata, il kernel controlla la presenza di segnali, rischedula se un'altro processo con priorità più alta si è risvegliato o semplicemente ripristina l'esecuzione del processo corrente in user mode. Il risultato della chiamata di sistema è ritornato nel registro %eax, un valore negativo indica un errore. In questo caso la libreria C setta la variabile globale errno a tale valore e ritorna -1. L'unica chiamata di sistema che non rispetta questa regola è 'getpriority' () perché -10, per esempio, è un perfettamente valido numero di priorità (vedi la sezione 'Scheduling dei processi'). per questo la libreria C tratta questa funzione di sistema in maniera differente. Di seguito un esempio di una normale chiamata di sistema. Prima descriverò l'interfaccia della libreria C per le chiamate di sistema, dopo presenterò la gestione delle chiamate di sistema del kernel. Notare che lo stub dell'invocazione delle chiamate di sistema è una macro che è espansa in linea dalla libreria C. Lo stub della libreria C: .text .globl syscall_error ....... movl $SYS_##syscall_name, %eax /* Store in %eax the system call number. */ int $0x30 /* Kernel trap. */ test %eax, %eax jl syscall_error ....... syscall_error: negl %eax /* Make it positive. */ movl %eax, _errno /* Store it in `errno'. */ movl $-1, %eax /* Return -1. */ ret The kernel: ....... # Code to check the system call number # and set up registers jmp %eax # Call the appropriate routine ...... # Resume the system call. Check for # signals, etc .align 4 __sys_fcntl: pushl 12(%esi) pushl 8(%esi) pushl 4(%esi) movw %bx, %ds call _sys_fcntl # Call the kernel C function addl $0xc, %esp ret Al momento il kernel di Thix implementa le seguenti chiamate di sistema: fork exec ustat utime getpid brk getppid exit umask fcntl kill pause uname stime time sync chmod open close link unlink mkdir chdir readdir rmdir reboot lseek read write dup stat fstat dup2 mknod pipe setuid setgid getuid geteuid getgid getegid sigpending sigprocmask sigsuspend sigaction chown access ioctl tcsendbreak tcdrain tcflush tcflow tcgetattr tcsetattr getitimer setitimer getrlimit setrlimit getrusage getpriority setpriority mount umount waitpid setsid setpgid getpgrp swapon swapoff readlink truncate lstat symlink sethostname setdomainname ftruncate fchown fchmod Alcune di loro ancora non sono ancora terminate. Il kernel mette a disposizione due chiamate di sistema addizionali (getprocinfo and getsysinfo) per ottenere informazioni sul sistema e sui processi. Usare le chiamate di sistema invece di leggere da /dev/kmem per ottenere informazioni è un metodo più pulito. Quando il kernel avrà il supporto per il file system virtuale, un entrata /proc del filesystem renderà obsolete queste due chiamate, ma adesso questa è la maniera di ottenere informazioni sul sistema. -------------------------------------------------------------------------------- INTERRUPTS e ECCEZIONI -------------------------------------------------------------------------------- l'hardware di solito genera molti differenti tipi di interrupt e eccezioni. Molti sono legati al completamento dell 'I/O, alla sincronizzazione hardware, alla violazione delle protezioni, ai page faults, ai timers o agli eventi inusuali. Il kernel dovrebbe gestirli tutti, giusto per essere sicuri che sia in grado di filtrare e processare ogni evento. Il kernel di thix tiene traccia di tutti gli interrupt e le eccezioni conosciute dei processori 386/486, chiamando l'handler appropriato. Tutti i processi condividono la stessa tabella degli interrupt (che contiene gli entry point per gli interrupt hardware e le eccezioni software, più gli entry point delle chiamate di sistema) ed ogni tentativo di usare un numero di interrupt invalido (per esempio generando un interrupt software) sarà rilevato e un appropriato segnale sarà inviato al processo che ha generato il problema. Alla fine di un interrupt o di un'eccezione, sarà effettuata una transizione dallo stato kernel mode allo stato user mode.Il kernel per primo controllerà se un processo a priorità più alta si è risvegliato come conseguenza dell'esecuzione di un handler di un interrupt. Questo perché solitamente il completamento di una richiesta di I/O Pensiamo un attimo a cosa succederebbe se alla fine di una routine di interrupt il kernel continuasse semplicemente ad eseguire lo stesso processo, senza controllare se ci sono processi a priorità maggiore da eseguire. Supponiamo che il kernel esegua due processi: il processo A e il processo B. Il processo A vuole effettuare un'operazione di I/O (per leggere alcuni blocchi su disco). Esso normalmente chiama il device driver del disco per farlo, invia la richiesta appropriata al controller del disco e si mette in stato di sleep aspettando che l'I/O sia completato. Lo scheduler a questo punto sceglie di eseguire il processo B e l'I/O è terminato quando il processo B è ancora in esecuzione. Il kernel chiama allora la routine di interrupt del disco, e quando la routine ritorna il processo B ritorna ad essere eseguito. Il processo A sarà schedulato per l'esecuzione quando il processo B "mangia" il suo tempo. Allora il processo A sarà risvegliato per l'esecuzione nel device driver del disco, ed eventualmente, effettua un'altra operazione di I/O sul disco. Il problema qui è che le performance del disco scadranno molto a causa del ritardo artificiale tra due richieste di I/O consecutive. Supponiamo che il processo B sia quello in stato idle. Sia la CPU sia il controller I/O sprecheranno il loro tempo. Se il processo A è schedulato per l'esecuzione prima che l'interrupt sia avvenuto, esso effettuerà un'altra richiesta di I/O ed andrà in stato sleep usando la CPU solo per un breve periodo di tempo. Quindi il processo B sarà schedulato ancora ed userà la CPU mentre il controller del disk sta facendo il proprio lavoro. Ecco un esempio di come gli interrupts sono gestiti all'interno del kernel, Prima di chiamare il gestore dell'interrupt, i registri di segmento sono settati e il livello corrente di interrupt mascherato. .align 4 int26: # IRQ 6 -> the floppy disk pushl %ebp movl %esp, %ebp pushal pushl %ds pushl %es movw $0x10, %ax movw %ax, %ds movw %ax, %es movb $(1 << 6), %bl # 6 is the irq no. call mask_i8259A_irq # mask the current irq level call _fdc_interrupt # call the appropriate # interrupt handler movb $~(1 << 6), %bl # 6 is the irq no. call unmask_i8259A_irq # unmask the current irq level cmpl $0, _sched_touched # if a process with a higher jne do_sched # priority waked up, # reschedule jmp end_IRQ # check for signals, # restore registers and iret -------------------------------------------------------------------------------- I/O A BASSO LIVELLO -------------------------------------------------------------------------------- L'I/O a basso livello è effettuato attraverso una serie di funzioni "inline" che contengono istruzioni i386 di input e output, oppure tramite una serie di tali istruzioni quando l'I/O lo richieda: static inline void outb(unsigned short __port, unsigned char __value) { __asm__ __volatile__("outb %0,%1" : /* no output */ : "a" (__value), "d" (__port) : "eax","edx"); } static inline void outb_delay(unsigned short __port, unsigned char __value) { __asm__ __volatile__("outb %0,%1 outb %%al,$0xE0" : /* no output */ : "a" (__value), "d" (__port) : "eax","edx"); } A causa del fatto che i dispositivi di I/O sono solitamente lenti, possono essere richiesti dei ritardi tra le operazioni di I/O, in molti casi due istruzioni 'jump' ... /* I/O instruction. */ jmp $+2 jmp $+2 ... /* I/O instruction. */ sono sufficienti a sincronizzarsi con i dispositivi di I/O. Le istruzioni di salto rallentano il processore resettando la sua coda delle istruzioni, ma ad esempio il BIOS AT usa istruzioni 'out' nella porta inutilizzata 0xE0 per questo compito, perché danno migliore temporizzazione su macchine veloci. Tale metodo è lo stesso con cui Thix implementa dei ritardi per la sincronizzazione con l'I/O, in tutte le funzioni _delay. -------------------------------------------------------------------------------- GESTIONE DELLA MEMORIA VIRTUALE -------------------------------------------------------------------------------- VM Mapping: La mappatura della memoria virtuale Demand Paging: Implementazione del paging su richiesta Fork: La chiamata di sistema fork() Exec: La chiamata di sistema exec() Page Cache: La cache delle pagine fisiche Shared Pages: Pagine condivise VM Device Numbers: I numeri di dispositivo specifici della Memoria Virtuale Swapper: Il processo swapper Sub-allocation: Il sub-allocatore di memoria Checking User Params: Come sono controllati i parametri forniti dall'utente -------------------------------------------------------------------------------- MAPPARE LA MEMORIA VIRTUALE NELLA MEMORIA FISICA -------------------------------------------------------------------------------- Dai processori Intel (TM) 80386 DX, tutti i processori x86 supportano la memoria virtuale. Come breve descrizione posso affermare che ogni processo può avere il suo spazio di indirizzamento virtuale, rendendo così impossibile conflitti di memoria con gli altri processi in esecuzione, e che ognuno di questi spazi virtuali è costruito usando un piccolo albero consistente di una directory di pagine con più di 1024 entry di tabelle di pagine, ognuna delle quali punta ad una tabella con 1024 entry di pagine fisiche. Poiché ogni pagina è di 4Kb, un processo può usare 4Gb di memoria virtuale. Per facilitare le cose al kernel e prevenire la mappatura di pagine inutilizzate, (che implicano un reset della cache del processore), il kernel mappa l'inizio dello spazio degli indirizzi virtuali dentro lo spazio degli indirizzi fisici. In questo modo, ogni volta che il kernel necessita di accedere alla memoria fisica del computer, semplicemente esegue tale accesso, perché la memoria fisica può essere trovata allo stesso indirizzo all'interno dello spazio degli indirizzi virtuali. I processori x86 prevedono anche un meccanismo di segmentazione del codice. Il kernel lo usa per nascondere il suo codice, dati e stack dai processi che girano a livello utente. Il kernel inizia all'indirizzo 0 e riserva una quantità di memoria virtuale uguale all'ammontare di memoria fisica del computer più 4Mb. Quando un processo gira in modo kernel, può avere accesso ad ogni locazione di memoria virtuale (anche inesistente se necessario), mentre i processi che girano a livello utente usano un segmento per codice/dati/stack che inizia dopo lo spazio riservato dal kernel. -------------------------------------------------------------------------------- L'IMPLEMENTAZIONE DEL PAGING SU RICHIESTA (demand paging) -------------------------------------------------------------------------------- i programmi diventano sempre più grandi ogni giorno. Se un computer ha 4Mb di RAM e qualche utente lancia un compilatore C (che occupa circa 1.3 Mb) ed un'altro utente lancia l'editore Emacs (che occupa circa la stessa quantità di memoria), la memoria di sistema si riempirà. E richiesto un breve algoritmo che semplicemente carica l'intero eseguibile in memoria. Sono usato due tecniche per diminuire al massimo la quantità di memoria che un programma necessita in un determinato momento. Il primo è chiamato 'demand paging, e fondamentalmente, dice che il sistema operativo dovrebbe intercettare i 'page faults' e caricare una pagina da un eseguibile solo quando il processo ne abbia bisogno ( è avvenuta una 'page fault' per un dato indirizzo). La seconda tecnica è chiamata swapping' e sarà discussa più avanti, al momento della presentazione dell'implementazione dello 'Swapper'. Ogni volta che avviene un 'page fault', è chiamata la routine i386_page_fault(). In base alla natura di questo page fault', questa funzione chiama in ordine il gestore di `page not present' oppure quello di`page protection'. Una descrizione semplificata del gestore di `page not present' darà un'idea migliore di come lavora il sistema del paging su richiesta. void i386_page_not_present_fault(VMADDR address) { int kpid; int page; PGDATA *pgd; unsigned pgtbl_addr; PGTBL *pgtbl, **pgdir; int vmdev, block, type; unsigned new_page, new_page_addr; pgdir = this->PGDIR + address.pgdir_index; if (((PGTBL *)pgdir)->present) { /* La pagina è persa */ pgtbl_addr = (unsigned)*pgdir & 0xFFFFF000; restart: pgtbl = (PGTBL *)pgtbl_addr + address.pgtbl_index; /* Trova il tipo di pagina e la locazione (se presente). */ vmdev = ((extPGTBL *)pgtbl)->vmdev; block = ((extPGTBL *)pgtbl)->block; type = ((extPGTBL *)pgtbl)->type; if (block) for(;;) if ((page = pg_hash_search(vmdev, block))) { /* E' stata trovata una pagina con il dato numero di vmdev/block nella tabella hash. Se nessun altro processo la sta usando, dobbiamo prelevarla dal pool di memoria libera. */ pgd = &pgdata[page]; if (pgd->lnext != 0xFFFF) reuse_page(pgd - pgdata); pgd->count++; if (type == PAGE_SWAP) release_swap_block(vmdev_aux(vmdev), block); /* Marca la pagina come read-only. Potremmo voleral condividere. */ *(unsigned *)pgtbl = ((pgd - pgdata) << PAGE_SHIFT) | PAGE_URP; return; } else if ((kpid = block_is_loading(vmdev, block))) { sleep(&busy_blocks[kpid], WAIT_PAGE); /* C'è la possibilità che la pagina sia stata 'swappata' da qualche altro processo, ma lo swapper l'ha 'swappata' prima che avessimo la possibilità di risvegliare il processo. Facciamo ripartire il fault handler dal punto in cui ha controllato l'entry nella tabella delle pagine. */ goto restart; } else { /* Notifica altre istanze dello stesso processo che stiamo per caricare questo blocco. */ busy_blocks[current_kpid].vmdev = vmdev; busy_blocks[current_kpid].block = block; break; } pgtbl->busy = 1; reserve_pages(1); /* Prende una nuova pagina dal pool di memoria libera. */ new_page_addr = (new_page = get_page()) << PAGE_SHIFT; *(unsigned *)pgtbl = new_page_addr | PAGE_URP; pgtbl->busy = 1; /* Inizializzo la struttura PGDATA. */ pgd = &pgdata[new_page]; pgd->vmdev = vmdev; pgd->block = block; pgd->type = type; switch (type) { case PAGE_DZ: lmemset((void *)new_page_addr, 0, PAGE_SIZE >> 2); break; case PAGE_FILE: /* Carico la pagina dall'immagine binaria. */ a_out_read(this->a_out_inode, (char *)new_page_addr, A_OUT_HEADER + ((*(unsigned *)&address - KERNEL_RESERVED_SPACE) & ~(PAGE_SIZE - 1)), PAGE_SIZE); goto common; case PAGE_SWAP: /* carico la pagina dal disco. */ load_page(pgd); common: /* Inserisco la pagina nella tabella hash. */ pg_hash_insert(new_page); /* If the page have a swap block, release it, we no longer need it. */ if (type == PAGE_SWAP) release_swap_block(vmdev_aux(vmdev), block); /* Wake up all the processes waiting for this block to be loaded. */ busy_blocks[current_kpid].vmdev = 0; busy_blocks[current_kpid].block = 0; wakeup(&busy_blocks[current_kpid]); break; default: PANIC("invalid extended page table entry %x !", type); break; } pgtbl->rw = 0; pgtbl->busy = 0; } else { /* The page table is missing. Allocate & initialize one. */ reserve_pages(1); new_page_addr = get_page() << PAGE_SHIFT; *(unsigned *)pgdir = new_page_addr | PAGE_UWP; lmemset((void *)new_page_addr, 0, PAGE_SIZE >> 2); } } Implementare il 'demand paging' nel kernel, non solo aumenta le prestazioni globali del sistema operativo, ma semplifica anche il codice. Le funzioni di sistema fork() e exec() (descritte nella prossima sezione) sono molto più veloci rispetto a quelle di un kernel senza paging su richiesta, perché non è più necessario copiare lo spazio degli indirizzi del processo padre (vedi la sezione 'la chiamata di sistema fork()') o caricare la nuova immagine dall'eseguibile (vedi la sezione 'la chiamata di sistema exec()). La quantità di memoria usato da un processo è dinamicamente configurata e se il carico del sistema è mediamente alto, il sistema manterrà nella memoria principale solo quelle pagine che sono correntemente in uso. Vedi la sezione 'Il processo swapper' per capire come le pagine di memoria inutilizzata sono rimosse dalla memoria principale. -------------------------------------------------------------------------------- La routine di sistema FORK() -------------------------------------------------------------------------------- La routine fork() è molto semplice e veloce, perché non c'è necessita di copiare lo spazio degli indirizzi dal processo padre a quello figlio. Il kernel prima protegge in scrittura tutte le pagine di memoria virtuale del padre, e dopo copia la tabella delle pagine del padre dentro quella del figlio. Esso copia anche la struttura 'u_area[]' del padre nella struttura 'u-area[]' del figlio, modificando solo i campi che sono differenti. La fork() incrementa anche i contatori della pagina per le pagine virtuali che sono correntemente allocate in memoria, o il contatore dello swap block per le pagine virtuali che sono sul dispositivo di swap. Di seguito è presente il loop principale della routine fork(), che clona lo spazio degli indirizzi del padre, solo settando la tabella delle pagine e i contatori dello swap block. La routine reale è un poco più complicata, essa copia la struttura 'u_area[]' del padre dentro quella del figlio, inizializzando alcuni campi, ma questo non è rilevante in questo contesto. Ho incluso qui il listato giusto per puntualizzare sulla semplicità della routine fork() in un sistema che implementa il 'demand paging'. Per amor di chiarezza e leggibilità, tutte le ottimizzazioni sono state rimosse. extern PGDATA *pgdata; /* One entry for each physical page. */ int sys_fork(void) { ..... /* Loop through the parent page tables in order to initialize the corresponding child data structures. This is the child VM setup code. */ for (page_table = KERNEL_PAGE_TABLES + 1; page_table < 1024; page_table++) { if (pgdir[page_table] == 0) continue; pgtbl_addr = get_page() << PAGE_SHIFT; cpgdir[page_table] = (PGTBL *)(pgtbl_addr | PAGE_UWP); pgtbl = (PGTBL *)((unsigned)pgdir[page_table] & ~0xFFF); extpgtbl = (extPGTBL *)pgtbl; for (page = 0; page < 1024; page++) if (pgtbl[page].present) { pgtbl[page].rw = 0; pgdata[pgtbl[page].high_address].count++; } else { if (extpgtbl[page].type == PAGE_SWAP && extpgtbl[page].block) sdt[vmdev_aux(extpgtbl[page].vmdev)]. bitmap[extpgtbl[page].block]++; } /* Clone the parent page table. */ memcpy((void *)pgtbl_addr, pgtbl, PAGE_SIZE); } ..... } Vedi al sezione Page Cache per una dettagliata descrizione della struttura PGDATA. -------------------------------------------------------------------------------- La funzione di sistema EXEC() -------------------------------------------------------------------------------- Anche la routine di sistema exec() è molto semplice, perché il suo solo compito (per quanto concerne la gestione della memoria virtuale) è allocare una directory di pagine e un numero di tabelle di apgine per la nuova immagine del processo, riempiendole con le informazioni appropriate. Questo significa che tutte le pagine corrispondenti alle sezioni codice,dati e bss dovrebbero essere tutte inizializzate per puntare ai corrispondenti block del file system, o marcate come 'demand zero' (solo per le pagine bss). Ogni volta che il processo prova ad accedere a pagine codice, dati o bss, il kernel avraà tutte le informazioni necessarie per caricare la pagina (o semplicemente allocarne una nuova per le pagine bss). Lo farà e dopo ripristinerà l'esecuzione del processo. Poiché tutte le istruzioni che causano un 'page faults' (istruzioni che effettuano accessi in memoria) sono ripristinabili, il processo proverà nuovamente ad accedere l'indirizzo virtuale perso e continuerà con successo la sua esecuzione. -------------------------------------------------------------------------------- Il CACHING DELLE PAGINE -------------------------------------------------------------------------------- Il kernel tiene traccia delle pagine di memoria fisica usando una lista a doppio concatenamento. per ogni pagina fisica, esso mantiene una struttura PGDATA contenente il tipo della pagina, le informazioni della locazione corrente, il conto dei processi che stanno usando la pagina, i flag 'dedicati', etc. typedef struct { unsigned reserved : 1, type : 2, vmdev : 5, block : 24; unsigned char busy; unsigned char dedicated; unsigned char count; union { unsigned age; /* Used when the page is part of the address space to keep track of its age. */ unsigned map; /* Used for dynamic data allocation. */ } aux; unsigned short hprev; unsigned short hnext; unsigned short lprev; unsigned short lnext; } PGDATA; Se una pagina virtuale non ha la sua copia nella memoria fisica (può essere caricata da un block del file system, da un device di swap o semplicemente riempita di zero se è una pagina bss), l'informazione circa tale pagine è mantenuta dentro la tabella delle pagine. Se una pagina ha la sua copia dentro la memoria principale, ma ha anche una copia sul device di swap (come risultato di essere 'swappata' in un momento precedente), il kernel mantiene le informazioni circa la sua ubicazione (il device di swap e il numero di block) dentro la struttura PGDATA, perché tale pagina potrebbe diventare vecchia e non c'è motivo di scriverla ancora sul device di swap se vi è già presente. Ogni volta che avviene un page faults, il kernel rileva la locazione (device è block) della pagina 'persa' dagli entry della tabella delle pagine ed inizia a cercare tale pagina. Cercare attraverso tutte le strutture PGDATA per una pagina con lo stesso numero di device/block è un processo veramente lento, specialmente su sistemi con molta memoria, così il kernel inserisce le pagine che hanno una copia sul device di swap o sul file system in un a tabella hash, usando una funzione hash basata sul numero di device/block. Se è stata trovata una pagina, il kernel prima controlla se altri processi la condividono, (vedi la sezione 'Implementazione della condivisione delle pagine) perché se non ci sono altri processi che la usano, la pagina dovrebbe essere anche rimossa dalla lista delle pagine libere, per prevenire una reallocazione. Altrimenti, il contatore delle pagine è incrementato e l'entry della tabella della pagina settato. Ci sono alcuni problemi circa l'interazione tra cache delle pagine e cache del buffer del file system. Poiché entrambi i meccanismi di cache stanno provando a fare il caching di binari, (il page cache preserva la connessione tra pagina fisica e file system o block del device o block del device di swap spesso anche dopo che il programma esce, la cache del buffer del file system, semplicemente tiene in memoria i block del file system più usati), il kernel si trova a fronteggiare strane situazioni. Quando una pagina è inserita dentro la lista libera, la connessione tra lei e il suo block di swap o block del file system (se presente) non è rimossa, con l'idea di poter ritrovare la pagina molto velocemente se è richiesta ancora dopo essere stata deallocata. Se il kernel interrompe questa connessione (cancellando la pagina dalla tabella hash e resettando i campi 'vmdev' e 'block' nella relativa struttura PGDATA) e un processo necessita della pagina, esso proverà a trovarla usando i suoi 'vmdev' e 'block', ma senza successo perché la pagina doveva ancora contenere l'informazione nello swap o nel file system block. C'è un'altra situazione in cui la connessione swap/fs block può tornare utile. Supponiamo che un programma termini e sia lanciato di nuovo. Se il tempo trascorso è breve, o quelle pagine non sono state richieste da qualche altro programma, saremo in grado di trovarle nella lista delle pagine libere, e non avremo bisogno di caricarle da disco. senza cercare nel buffer cache. Comunque, questo porta ad una strana situazione. Supponiamo di far partire un programma chiamato 'A'. Questo caricherà le sue pagine, usando il meccanismo del demand paging fornito dal kernel, andrà in esecuzione e poi terminerà. Le sue pagine sono adesso presenti sia nella cache della pagine sia nella buffer cache (le pagine di 'A' possono apparire nella lista delle pagine libere anche mentre 'A' è in esecuzione, come risultato di un ridimensionamento dell'area dati o dello stack, oppure di un'azione dello swapper). Se qualcuno modifica l'immagine binaria dell'eseguibile (per esempio come risultato di una compilazione di una nuova versione di 'A'), c'è la possibilità che la nuova immagine binaria usi alcuni e tutti i blocchi del file system usati dalla versione precedente. Se 'A' è rilanciato, il kernel cercherà le pagine con lo stesso numero di 'vmdev' e 'block' nella lista delle pagine libere (la cache) e le caricherà, agendo in maniera errata, perché quelle pagine contengono il vecchio eseguibile. Per aggirare il problema, il kernel resetta la cache delle pagine ogni volta che è lanciato un eseguibile con una data di creazione più recente dell'ultimo volta in cui la cache è stata cancellata. poiché non possiamo far fede al campo 'mtime' dell'inode (l'utente può modificarlo mediante la chiamata di sistema 'utimes'), ho aggiunto un nuovo campo all'inode, 'ktime' ,usato per tener traccia della data di creazione del file. Una soluzione migliore potrebbe essere semplicemente quella di resettare la cache delle pagine ogni volta che un eseguibile è lanciato, perché il metodo del 'ktime' funziona solamente con il filesystem TFS (Thix File System). Fondamentalmente l'implementazione della cache delle pagine consiste di poche routine che mantengono la lista a doppio concatenamento delle pagine libere. Queste routine sono pg_list_insert() e pg_list_delete() per le liste concatenate e pg_hash_insert(), pg_hash_delete() e pg_hash_search() per la tabella hash. -------------------------------------------------------------------------------- Implementazione delle pagine condivise -------------------------------------------------------------------------------- Le pagine condivise sono un altro metodo per diminuire la quantità di memoria usata dai programmi. Poiché non c'è motivo nell'avere pagine multiple contenenti la stessa cosa, il kernel prova ad usare la stessa pagina per quanti più processi è possibile. La cache delle pagine effettua il primo passo in questa direzione cercando le pagine nella tabella hash che usando i numeri di device e di block. Se un'altra istanza del processo in esecuzione è attiva, ci sono molte probabilità di trovare la pagina richiesta nella tabella hash. La pagina restituita dalla ricerca nella tabella hash è esattamente la stessa di quella usata dall'altra istanza, così sarà condivisa da entrambe. Questa la descrizione di come le pagine di codice sono condivise. Alcune volte la stessa regola può essere usata per condividere anche le pagine di dati. una pagina di dati può essere condivisa fino a quando il programma che la usa non cerca di cambiarne il contenuto. Quando un processo cerca di cambiare il contenuto di una pagina condivisa, è generato un 'page protection fault' ed il kernel crea una copia separata della pagina per quel processo, resettando il flag 'write protect' nel corrispondente entry della tabella delle pagine. Gli altri processi continueranno a condividere la vecchia pagina, non modificata. Se non ci sono altri processi che condividono la pagina, il kernel interrompe la connessione tra la pagina e il file system o il device di swap (se presente) poiché la pagina sarà modificata esattamente dopo il ritorno dalla routine che gestisce il 'page protection fault', rimovendo la pagina dalla tabella hash e marcandola come 'read/write' nella relativa entry della tabella delle pagine. Ecco una versione semplificata della routine di `page protection fault'. void i386_page_protection_fault(VMADDR address) { PGDATA *pgd; PGTBL *pgtbl, **pgdir; unsigned new_page, old_page_addr, new_page_addr; if (*(unsigned *)&address - KERNEL_RESERVED_SPACE < (this->text_pages << PAGE_SHIFT)) { kill_kpid(current_kpid, SIGSEGV); return; } else { pgdir = this->PGDIR + address.pgdir_index; pgtbl = (PGTBL *)((unsigned)*pgdir & 0xFFFFF000) + address.pgtbl_index; pgd = &pgdata[pgtbl->high_address]; if (pgd->count == 1) { not_shared: pgtbl->rw = 1; if (pgd->block) { pg_hash_delete(pgd - pgdata); pgd->block = 0; } pgd->type = PAGE_SWAP; return; } pgtbl->busy = 1; reserve_pages(1); if (pgd->count == 1) { pgtbl->busy = 0; goto not_shared; } pgd->count--; old_page_addr = (pgd - pgdata) << PAGE_SHIFT; new_page_addr = (new_page = get_page()) << PAGE_SHIFT; *(unsigned *)pgtbl = new_page_addr | PAGE_UWP; pgdata[new_page].type = PAGE_SWAP; pgdata[new_page].block = 0; memcpy((void *)new_page_addr, (void *)old_page_addr, PAGE_SIZE); } } Sfortunatamente i processori 80386 DX (TM) hanno un difetto di progettazione che rende l'implementazione dell'algoritmo appena descritto molto più difficoltosa di quello che dovrebbe essere.Ecco in breve il problema: Per implementare la protezione, i processori della famiglia Intel 80x86 forniscono quattro differenti livelli in cui i programmi possono girare. Il livello 0 è quello a privilegi più alti, ed è usato per far girare il kernel. Il livello a privilegi più bassi è il 3 ed è usato per far girare programmi utente. In un hardware ben progettato, ogni tentativo di scrittura su una pagina a sola lettura dovrebbe generare un 'page fault' (l'errore passato al gestore dei 'page fault' specifica la ragione del page fault, che potrebbe essere la richiesta di una pagina non presente oppure una violazione d'accesso). Sfortunatamente questo non accade nel processore 80386 quando gira nei livelli di protezione 0, 1 e 2. Succede solo a livello utente, ma non è sufficiente. Supponete che un programma effettui una chiamata di sistema a read() per leggere qualcosa da un file. Se la pagina corrisponde al buffer passato come argomento a read() è condivisa con qualche altro processo (come conseguenza di qualche precedente chiamata alla routine di sistema fork()) la pagina sarà ovviamente in stato read-only per rilevare ogni tentativo di modifica, come spiegato in precedenza. quando il kernel proverà a scrivere i dati richiesti nel buffer, dovrebbe essere generato un 'page protection fault', che notifica al kernel che la pagina è read-nly (condivisa) e dovrebbe essere duplicata prima di essere modificata. Bene, tale segnale di 'page protection fault' non è generato nei sistemi basati su processori 80386. Così il kernel attualmente scrive i dati nella pagina senza accorgersi che la pagina è a sola lettura. Questo problema è stato eliminato nei processori 80486, ma il kernel suppone di funzionar anche sui 386, così sono stati aggiunti alcuni controlli addizionali per scavalcare tale problema. Possiamo distinguere due situazioni. Quando la pagina non è presente, sarà prima generato un 'page not present fault', il kernel caricherà la pagina (eventualmente condividendola con un'altra istanza dello stesso processo), settandola come read-only e quindi riprovando l'operazione di scrittura. Ma non la farà. Il kernel risolverà il problema settando un flag nella struttura u_area del processo corrente all'inizio di ogni chiamata di sistema che si suppone effettui un accesso alla memoria (read(), stat(), fstat(), waitpid(), sigpending(), etc.) e resetterà il flag alla fine della chiamata. Se è generato un 'page not present fault' quando il processo corrente gira in modo kernel,il fatto che questo flag sia settato (kwreq) determinerà la chiamata "manuale" della routine di 'page protection' da parte della routine di 'page not present fault' (poiché tale 'fault' sarà normalmente generato alla fine del primo) e la pagina duplicata o marcata come non condivisa. Nel secondo caso, le cose sono un poco più complicate. Questo perché la pagina è a sola lettura ma presente, quindi il kernel non è informato che è successo qualcosa di sbagliato dalla combinazione flag kwreq settato / page not present. Risolvere questo problema è più complicato che nel primo caso, perché il kernel deve guardare nelle tabelle delle pagine e chiamare "a mano" la routine di page protection fault, per ogni pagina a sola lettura che fa parte del buffer. Ovviamente questo si fa solamente nelle chiamate di sistema che si suppone accedano in scrittura nella memoria del kernel, e solo se il kernel è compilato per macchine 80386. Come già spiegato, il 486 non necessita di nessuno di questi noiosi rimedi. -------------------------------------------------------------------------------- Numeri di device della memoria virtuale -------------------------------------------------------------------------------- Il kernel usa numeri di device a 16bit: 8bit per il major e 8 bit per il minor number. Sfortunatamente il numero di bit disponibili in un entry della tabella delle pagine è limitato a 5. Per ovviare all'inconveniente, il kernel alloca dinamicamente un numero di device più piccolo (vmdev) giusto per l'uso da parte delle routine di gestione della memoria ogni volta che è eseguita un'operazione di mount() o di swapon(). Le routine della memoria virtuale usano questo numero quando 'swappano' pagine di memoria. Prima di effettuare operazioni di I/O, il numero vmdev è convertito nel numero di device reale. Quando il device è inutilizzato da molto tempo (come conseguenza di una chiamata a umount() oppure a swapoff()), il numero vmdev è rilasciato e può essere riutilizzato. Con questo metodo siamo limitati a 2^5 = 32 dispositivi montati allo stesso tempo più il device di swap. -------------------------------------------------------------------------------- Il processo Swapper -------------------------------------------------------------------------------- Lo swapper è il solo reale processo del kernel, il solo processo che gira in modo kernel per tutto il tempo, facendo un lavoro molto utile. Ovviamente c'è anche un processo nascosto, ma questo processo è attivo quando non ci sono altri processi 'ready to run'. Se nel sistema c'è abbastanza memoria libera, lo swapper è in modo 'sleep'. Quando il numero di pagine disponibili scende al di sotto del limite imposto da LOW_PAGES_LIMIT (0x20), lo swapper è risvegliato e inizia a cercare pagine sufficientemente vecchie da essere 'swappate'. Quando sono state 'swappate' pagine a sufficienza (o semplicemente il numero di pagine libere è cresciuto entro il limite imposto da HIGH_PAGES_LIMIT (0x40), lo swapper torna in modo 'sleep'. Ma scendiamo in dettaglio: prima di tutto, perché necessitiamo di due limiti (LOW_PAGES_LIMIT and HIGH_PAGES_LIMIT) ? Supponiamo di avere solo un limite (chiamiamolo, PAGES_LIMIT). La prima volta che il numero delle pagine libere nel sistema diminuisce sotto questo limite, lo swapper è risvegliato ed inizia a fare lo 'swapping' delle pagine. Dopo aver svolto il suo compito lo swapper torna in stato 'sleep', perché le pagine libere nel sistema sono state riportate a PAGES_LIMIT. Se un processo richiede immediatamente una nuova pagina, il numero di pagine libere nel sistema scenderà ancora sotto PAGES_LIMIT, lo swapper sarà risvegliato e così via. L'idea di avere due limiti differenti invece di uno solo e quella di diminuire il sovraccarico computazionale dovuto proprio al continuo avvio/arresto del processo swapper. In più, se il sistema è a corto di pagine, è una buona cosa liberare un numero maggiore possibile di pagine, così si allontana per quanto più è possibile il momento in cui il sistema sarà in deficit di memoria. Come lavora lo swapper? Lo swapper è un processo del kernel, per cui ha accesso a tutte le strutture del kernel, inclusa la page directories e la page table. Per prima cosa lo swapper prova ad ottenere qualche pagina libera comprimendo il buffer cache. Dopo inizia a cercare nella tabella dei processi del kernel quei processi che hanno pagine che possono essere swappate. Alcuni processi, come gli zombie o i processi che eseguono del codice kernel critico (ad esempio fork()) non possono essere swappati. Una volta che un processo è stato selezionato, lo swapper inizia a cercare nella tabella delle pagine in uso. Sarà certamente saltata la tabella delle pagine che puntano al kernel, perché l'area di memoria virtuale usata dal kernel è condivisa da tutti i processi nel kernel e non è soggetta a swapping. Quando lo swapper trova una tabella di pagine in uso, la controlla cercando le pagine. Se un data pagina e trovata e il bit di accesso è settato (significa che la pagina è stata usata di recente), lo swapper semplicemente resetta tale bit e continua la sua ricerca tra le pagine della tabella. Se il bit di accesso non è settato, significa che la pagina è vecchia, ma lo swapper non la rimuove fino a che la sua età (mantenuta nella struttura pgdata[]) non diventa MAX_PAGE_AGE (7). Questa strategia è più flessibile di quella di usare solo il bit di accesso fornito dall'hardware, poiché il fatto che non ci sia stato accesso alla pagina dall'ultima volta che lo swapper l'ha controllata, non significa necessariamente che la pagina sia vecchia.. Potrebbe darsi che il processo abbia un livello di priorità basso, e non abbia mai la possibilità di essere eseguito ed accedervi. O potrebbe darsi che il processo abbia usato la pagina pochi secondi prima e proverà ad accedervi presto, così non ci sarebbe ragione di "swappare via" la pagina. Se la pagina risulta inutilizzata per un lungo periodo di tempo, allora ad ogni iterazione lo swapper incrementerà la sua età, e quando sarà raggiunto il massimo, la pagina sarà swappata. Se la pagina è sufficientemente "vecchia", lo swapper assumerà che non ce ne sia correntemente bisogno, e proverà a scartarla. Ci sono 3 tipi di queste pagine. Discutiamo ognuna di loro in ordine. Per prime ci sono le pagine che fanno parte del bss del processo (il segmento dati non inizializzati) e non saranno mai modificate. Supponiamo che un processo legga il contenuto di una di queste variabili non inizializzate (che è permesso da quando sotto UNIX il kernel garantisce che tale bss è riempito con zeri prima della partenza del programma; in effetti questo è vero solo sotto il punto di vista del processore, il kernel attualmente riempie la pagina bss di zeri soltanto quando il processo prova ad accedervi). La lettura della variabile non cambia il contenuto della pagina a lei associata, così se la pagina deve essere swappata, lo swapper semplicemente la scarta. Le pagine che sono state caricate in memoria ma che non sono mai state modificate, come quelle appartenenti al segmento 'text' oppure al segmento 'data' sono trattate nello stesso modo. Queste pagine possono essere ricaricate più tardi dalla loro corrispondente immagine binaria, così lo swapper si limita semplicemente a scartarle. (per esempio marcandole come non presenti nella 'page table', memorizzando nella page table la locazione dove queste pagine possono essere recuperate (VM device number + file offset). Notate che per queste pagine non possiamo memorizzare il numero di blocco del filesystem,perché esso ci fornisce solo informazioni circa la locazione della prima parte della pagina. Una pagina è composta da 4 blocchi (1blocco = 1Kbyte) e per capire dove siano gli altri blocchi del filesystem, il kernel deve analizzare i blocchi indiretti del file. Questa funzione è svolta attraverso a_out_read() che è una versione semplificata della chiamata di sistema read() usata per i file normali. In ultimo, ci sono della pagine che saranno modificata successivamente al momento del loro caricamento in memoria. Possiamo qui distinguere due situazioni: la pagina che deve essere swappata può anche essere trovata sul device di swap. In questo caso lo swapper aggiusta il contatore del blocco in cui tale pagina si trova e quindi la scarta. Se la pagina da swappare non ha una copia sul device di swap, allora non può essere scartata (bene, sarebbe divertente scartarle tutte, ma....). Lo swapper la inserirà sul device di swap. Per fare ciò deve controllare che sia presente tale device e che abbia abbastanza spazio. E' un compito facile, poiché il kernel tiene un contatore per il numero di blocchi liberi per lo swap su ogni device di swap presente nel sistema. ed anche un contatore globale di blocchi liberi per lo swap. Un semplice controllo su quest'ultimo ci fornisce l'informazione richiesta. Se non ci sono blocchi liberi per lo swap, lo swapper rinuncia e la pagina rimane in memoria. Se un device di swap non è stato specificato attraverso la chiamata di sistema swapon(), la pagina non sarà mai swappata. Se lo swapper trova un blocco libero, ci scrive sopra la pagina, la marca come 'non presente' ed aggiorna la corrispondente entry point della page table con i relativi valori di VM device/blocco di swap. Una nota finale sullo swapper: poiché lo swapper attiva gli interrupts ad ogni iterazione, il processo correntemente controllato potrebbe morire, ed il kernel id riusato per un'altro processo, Questa situazione dovrebbe essere evitata e questa è la ragione per cui ad ogni iterazione lo swapper controlla che l'id del processo non sia cambiata. Se così fosse, lo swapper molla ed inizia lo swapping per il processo successivo. Di seguito una versione semplificata del loop principale dello swapper. Molte cose sono state omesse perché le ho considerate irrilevanti: ottimizzazioni, codice per abilitare/disabilitare gli interrupt, statistiche, etc. ma dovrebbe ancora rendere bene l'idea di come lavora lo swapper. Tenete presente che gli interrupt sono tutti abilitati/disabilitati sul posto e un processo "swappabile" potrebbe terminare e/o essere rimpiazzato da un nuovo processo. Le condizioni Race possono essere eliminate facendo in modo di esser sicuri che ad ogni loop non stiamo "mixando" pagine e page table fra processi differenti. for (kpid = INIT; kpid; kpid = NEXT(kpid)) { pid = pid(kpid); for (page_table = KERNEL_PAGE_TABLES; page_table < 1024; page_table++) { /*Controlliamo se stiamo maneggiando lo stesso processo e se è ancora swappabile*/ if (pid(kpid) != pid || !u_area[kpid].swapable) break; /* Questa page table è in uso ? */ if (pgdir[page_table] == 0) continue; for (page = 0; page < 1024; page++) { /*Controlliamo se stiamo maneggiando lo stesso processo e se è ancora swappabile*/ if (pid(kpid) != pid || !u_area[kpid].swapable) break; /* Se la pagina corrente non è presente o e' occupata, continua */ if (!pgtbl[page].present || pgtbl[page].busy) continue; /* Abbiamo raggiunto il limite massimo superiore? Allora basta swapping*/ if (free_pages > HIGH_PAGES_LIMIT) goto main_loop; /* Se c'è stato accesso alla pagina significa che fa parte di quelle su cui si sta' correntemente lavorando. Non swappiamola allora! */ if (pgtbl[page].accessed) { pgtbl[page].accessed = 0; pgdata[pgtbl[page].high_address].aux.age = 0; continue; } /* Se la pagina e' sufficientemente vecchia, swappiamola. */ if (pgdata[pgtbl[page].high_address].aux.age == MAX_PAGE_AGE) { /* Ok, andiamo a swappare via la pagina. */ pgd = &pgdata[pgtbl[page].high_address]; switch (pgd->type) { case PAGE_DZ: case PAGE_FILE: /* Teniamo traccia della sua locazione e del tipo. */ extpgtbl[page].vmdev = pgd->vmdev; extpgtbl[page].block = pgd->block; extpgtbl[page].type = pgd->type; /* Marchiamola come "non presente". */ pgtbl[page].present = 0; /* Rilasciamo la pagina. */ if (release_page(pgd - pgdata)) wakeup(&get_page); break; case PAGE_SWAP: if (pgd->block) { /* Questa pagina è già presente sul device di swap quindi dobbiamo solo aggiustare i contatori */ get_swap_block(vmdev_aux(pgd->vmdev), pgd->block); /* Teniamo traccia della sua locazione e del tipo. */ extpgtbl[page].vmdev = pgd->vmdev; extpgtbl[page].block = pgd->block; extpgtbl[page].type = pgd->type; /* Marchiamola come "non presente". */ pgtbl[page].present = 0; if (release_page(pgd - pgdata)) wakeup(&get_page); break; } /* Abbiamo bisogno di un blocco di swap, ma non ci sono blocchi liberi sullo swap device. Proseguiamo. */ if (total_free_swap_blocks == 0) continue; /* Inizializziamo pgd con i valori vmdev/block . */ swap_page(pgd); pg_hash_insert(pgd - pgdata); /* Marchiamola come "non presente". */ pgtbl[page].present = 0; /* Teniamo traccia della sua locazione e del tipo. */ extpgtbl[page].vmdev = pgd->vmdev; extpgtbl[page].block = pgd->block; extpgtbl[page].type = PAGE_SWAP; /* Scriviamo la pagina sul disco. */ save_page(pgd); break; default: PANIC("BAD PAGE TYPE ... "); } } else pgdata[pgtbl[page].high_address].aux.age++; } } } } Il Sub-allocatore di memoria ---------------------------- Ci sono alcuni algoritmi nel kernel che richiedono chunks di memoria allocati dinamicamente di dimensioni più piccole della taglia della pagina (4096 bytes). L'esempio tipico è il meccanismo del buffer cache, che usa buffer di lunghezza 512, 1024 o 2048 bytes. Il kernel fornisce un metodo molto veloce per fare internamente malloc()/free() , usando chunks (pezzi) di taglia fissa. Il Sub-allocatore usa una lista concatenata di pagine per ogni possibile grandezza dei chunks. Esso prende le pagine dalla lista di quelle libere, le inserisce nella lista concatenata in corrispondenza della relativa dimensione e le divide se necessario. Quando le dealloca, se tutti i chunks della pagina sono liberi, la pagina ritorna nel pool di memoria libera. Col crescere della complessità e della dimensione del kernel, probabilmente questo algoritmo dovrà essere migliorato per gestire l'allocazione dinamica di chunk di memoria più piccoli, ottimizzando l'uso della memoria dei moduli del kernel. *Controllo dei parametri forniti dall'utente Il kernel deve controllare tutti i parametri forniti alle chiamate di sistema da parte dei programmi che girano a livello utente. Questo è fatto perché tali parametri potrebbero essere settati con dei valori illegali che potrebbero compromettere il funzionamento interno del kernel.Ogni chiamata di sistema controlla i propri argomenti di chiamata, poiché essi differiscono di chiamata in chiamata. Ad esempio, read() e write() controllano la validità del descrittore del file per essere sicure che punti ad un file aperto valido. Ma una cosa comune a tutte le chiamate di sistema è il controllo per la validità dei puntatori. Di questo si occupano alcune routine che fanno parte del gestore di memoria. Nel caso più semplice sono sufficienti le routines ok_to_read_area() e ok_to_write_area(). Queste routines ricevono come argomento un puntatore e una grandezza (size), controllando che l'area di memoria compresa tra il puntatore e il puntatore+size possa essere adoperata nella maniera richiesta (read/write). ok_to_write_area() emula anche il fault del page protection perle pagine in sola lettura, per aggirare il famoso e conosciuto inconveniente della memoria virtuale nei processori i386. Ecco un esempio di una chiamata di sistema che controlla la validità dei parametri: int sys_sigprocmask(int how, __sigset_t *set, __sigset_t *old_set) { if (old_set != (__sigset_t *)USER_NULL) if (ok_to_write_area(old_set, sizeof(__sigset_t))) { SYSCALL_PROLOG(); *old_set = this->sigblocked; SYSCALL_EPILOG(); } else return -EFAULT; if (set == (__sigset_t *)USER_NULL) return 0; if (!ok_to_read_area(set, sizeof(__sigset_t))) return -EFAULT; switch (how) { case SIG_BLOCK : this->sigblocked &= *set & SIG_BLOCKABLE; break; case SIG_UNBLOCK: this->sigblocked &= ~(*set & SIG_BLOCKABLE); break; case SIG_SETMASK: this->sigblocked = *set & SIG_BLOCKABLE; break; default : return -EINVAL; } return 0; } SYSCALL_PROLOG() e SYSCALL_EPILOG() sono delle macro che settano e resettano il flag kwreq nella u_area del processo corrente, per bypassare il problema della memoria virtuale nei processori i386. In caso di processori i486 tali macro sono nulle. #ifdef __i386k__ #define SYSCALL_PROLOG() { this->kwreq = 1; } #define SYSCALL_EPILOG() { this->kwreq = 0; } #else #define SYSCALL_PROLOG() #define SYSCALL_EPILOG() #endif Le funzioni ok_to_read_area() e ok_to_write_area() sono il più semplice possibile, così non costituiranno un collo di bottiglia nella gestione delle chiamate di sistema. Per avere un'idea di come possano essere, riporto di seguito il codice per la ok_to_read_area(). ok_to_write_area() è più complessa, perché deve aver a che fare col problema della VM dei processori i386, come spiegato prima, ma fondamentalmente fa' le stesse cose. int ok_to_read_area(void *pointer, unsigned size) { unsigned end = (unsigned)pointer + size; unsigned brk = this->brk + KERNEL_RESERVED_SPACE; unsigned stk = user_level_ESP[current_kpid] + KERNEL_RESERVED_SPACE; if ((unsigned)pointer < KERNEL_RESERVED_SPACE) return 0; if ((unsigned)pointer >= stk && end >= stk && (unsigned)pointer <= end) return 1; if ((unsigned)pointer <= brk && end <= brk && (unsigned)pointer <= end) return 1; return 0; } Controllare i puntatori invalidi può essere complicato, perché non tutti i puntatori forniti come argomento alle chiamate di sistema puntano ad una zona fissa di memoria. Un buon esempio di una chiamata di sistema che riceve tali puntatori è la exec(). I suoi argomenti sono puntatori a liste di puntatori a stringhe. Queste stringhe contengono la nuova immagine degli argomenti della linea di comando e dell'environment, e devono essere controllate e copiate sulla nuova immagine dello stack. Ci sono due differenti tipi di puntatori nella chiamata di sistema exec().Per prima il kernel deve controllare che le liste di puntatori siano valide. Questo comporta una ricerca per il puntatore NULL terminating. Il problema qui è che il kernel non conosce quanto siano lunga le liste dei puntatori, quindi deve cercare fino a quando non trova il puntatore a NULL. Supponiamo che un processo usi circa 2Mb di spazio 'data', riempiamolo con un pattern non nullo e quindi passiamolo come argomento alla exec(). Il kernel cercherà in tutti i 2 Mb di memoria, eventualmente generando dei faults quando accede a pagine non presenti, consumando un considerevole quantitativo di tempo CPU. La soluzione è stata quella di cercare il puntatore a NULL solo nei primi ARG_MAX bytes, la massima lunghezza non variabile combinata tra linea di comando e argomenti dell'environment che possa essere passata alla funzione di sistema exec(). Il secondo caso è simile, la sola differenza è che il kernel cerca per i caratteri null di fine stringa nella nuova immagine della linea di comando e dell'environment. Il File System Nella prima versione del kernel di Thix implementai il file system descritto nel libro di Maurice Bach `The design of the UNIX system'. Il file system li descritto tiene traccia dei blocchi liberi usando una lista concatenata e pensai che le implementazioni basate su una bitmap dovrebbero essere più veloci e stabile per due motivi principali. a. La frammentazione del filesystem non può essere controllata, Quando il kernel necessita di un nuovo blocco, non ha altra scelta che usare il blocco situato in testa alla lista concatenata. Poiche' dopo un determinato periodo di tempo la lista conterrà numeri di blocchi casuali, i nuovi files saranno sparpagliati in giro per il disco. b.il tempo di seek non può essere minimizzato. Per la stessa ragione descritta prima. Le testine del disco devono spostarsi in posti casuali del disco per leggere i blocchi richiesti dal file. c. Quando il cache superblock dei numeri di inode diventa vuoto, il kernel deve leggere molti inode dal disco e controllare il loro stato per ottenerne uno libero. d. L'impossibilità di leggere un singolo blocco nella lista concatenata può facilmente portare alla perdita dell'intera lista di blocchi liberi. Il filesystem può diventare instabile e deve essere riparato con l'utility fsck. I moderni kernel UNIX dividono il filesystem in gruppi di cilindri, allocando nuovi blocchi e inode da un gruppo di cilindri alla volta, nel tentativo di ridurre la frammentazione e il tempo di seek della testina. Per ogni gruppo di cilindri c'è una bitmap che tiene traccia dei blocchi liberi e un'altra che tiene traccia degli inode liberi. La nuova versione del kernel di Thix implementa una struttura similare di filesystem, basata su bitmap, che ha migliori performance rispetto alla precedente, ed è anche più stabile. Ogni volta che il kernel switcha su un nuovo cluster (questo è il nome che ho dato ai gruppi di cilindri) poichè non ci sono più risorse libere disponibili di un certo tipo (inodes o block liberi), esso prova ad allocare gli altri tipi di risorsa dallo stesso cluster o da uno a lui vicino, per poter ottimizzare il tempo di seek. Al momento non è stato fatto niente per controllare la frammentazione e tenerla a livelli bassi, tale ottimizzazione sarà aggiunta in futuro. Buffer cache: The buffer cache Layout: The file system layout Inodes: Inodes management Blocks: Blocks management File Tables: File tables Regular Files: Regular files Directories: Directories Pipes: Pipes Mount Points: Mount Points fsck: The fsck utility La buffer cache Ogni moderno sistema UNIX ha un meccanismo built-in di buffer cache, usato per incrementare le performance del file system, tenendo in memoria i blocchi del fs usati più di frequente. Solitamente è dinamico, il che significa che il buffer cache può usare l'intera memoria libera se necessario. L'algoritmo che ho usato nell'implementazione del buffer cache dinamico è un'estensione dell'algoritmo descritto nel libro di Maurice Bach `The design of the UNIX system'. Tale algoritmo usa un'area di memoria di dimensione fissa per il buffer cache, ed un singola lista a doppio concatenamento di strutture buffer, perdendo la possibilità di usare l'eccesso di memoria libera per il buffer cache. Per ogni buffer nel sistema, c'è una struttura contenente informazioni su di lui. Queste strutture sono collegate tra loro in due liste a doppio concatenamento. La prima contiene le strutture non usate. la seconda le strutture che puntano a buffer contenenti dati validi: typedef struct { unsigned block : 24, busy : 1, in_demand : 1, delayed_write : 1, valid : 1, dedicated : 1; __dev_t device; unsigned short size; unsigned char *address; unsigned short hprev; unsigned short hnext; unsigned short lprev; unsigned short lnext; unsigned short next; unsigned short __fill; } buffer; L'idea di base è di avere un numero di strutture buffer grosso abbastanza da coprire l'intero ammontare di buffer necessari in un dato momento, o di allocarle dinamicamente. Una lista a concatenamento semplice non è abbastanza per un'efficiente gestione del buffer cache, perché se il sistema deve restringere lo spazio usato dal buffer cache, l'operazione di parsing della lista per di alcuni buffer e scrivere sul disco ......sarebbe rallentata dal grosso quantitativo di strutture non usate che devono essere comunque saltate. Questa è la ragione principale per cui ho usato le due liste a concatenamento doppio. Se abbiamo più memoria libera e la possiamo usare come buffer cache, le strutture necessarie per i nuovi buffer sono prese dalla prima lista (che contiene le strutture buffer non utilizzate). Queste strutture saranno cancellate dal tale lista e inserite nell'altra. Quando dovremo liberare memoria usata dal buffer cache, sarà analizzata la lista usata per i buffer validi, liberando la memoria usata, rimovendo le strutture da qui e reinserendole nella lista delle strutture non usate, fino a quando non sarà stata liberata sufficiente memoria. Il file system non può lavorare senza la buffer cache. Nello speciale caso in cui tutti i buffer validi sono stati scartati e non c'è memoria sufficiente per dei nuovi, il sistema diverrà inutilizzabile. The basic idea is to have a number of buffer structures big enough to cover the entire amount of buffers needed at a given moment or to dynamically allocate buffer structures. A single linked list is not enough for an efficient buffer cache management, because if the system has to shrink the space used by the buffer cache, the operation of parsing the linked list in order to get rid of some buffers and to write to the disk the delayed write ones will be slowed down by a large amount of unused structures that need to be skipped. The file system can't work without the buffer cache. In the special case when all the valid buffers have been discarded and there is not enough memory for new ones, the system would be unusable. This leads to the idea of having a dedicated pool of free pages, big enough to keep the system going. The dynamic kernel memory allocation routines can receive a pointer to a local allocator function, specific to each kernel algorithm, used to get memory for the dedicated free pages pool. If such a pointer is specified, the kernel will try to allocate memory from the dedicated free pages pool before trying to use the global one. Layout This section will describe the layout of the Thix File System (TFS). A file system block is 1024 bytes long. The first file system block contains the boot block. It can be used to boot the system, but in the current implementation this block is unused because the kernel boots from a separate partition. However, future versions of the kernel might use it in order to reduce the number of partitions needed. The second file system block contains the superblock. Since the superblock contains a big amount of vital file system information, this block is replicated in several other places on the disk, as we will see. Here it is the superblock description: typedef struct { unsigned s_fsize; /* Total number of blocks in the fs. */ unsigned s_bblsz; /* Bad blocks list size (in blocks). */ unsigned s_clusters; /* Clusters in the file system. */ unsigned s_icluster; /* Inodes in a cluster. */ unsigned s_bcluster; /* Data blocks in a cluster. (R) */ unsigned s_lcflag; /* Last cluster status flag. */ unsigned s_blcluster; /* Blocks in the last cluster. */ unsigned s_bpcluster; /* Blocks per cluster. (R) */ unsigned s_ublocks; /* Unused blocks. */ unsigned s_ifree; /* Total free inodes. */ unsigned s_bfree; /* Total free blocks. */ unsigned s_flock; /* Lock used during file manip. */ unsigned s_ilock; /* Lock used during inodes manip. */ unsigned s_fmod; /* Superblock modified flag. */ unsigned s_ronly; /* Mounted read only flag. */ unsigned s_time; /* Last superblock update. */ unsigned s_state; /* File system state. */ unsigned s_magic; /* File system magic number. */ unsigned s_blksz; /* File system block size. */ unsigned s_direntsz; /* Directory entry size (power of 2). */ unsigned char s_ftype[64]; /* File system type. */ unsigned char s_fname[64]; /* File system name. */ unsigned s_f_in_demand; /* Block access required. */ unsigned s_i_in_demand; /* Inode access required. */ unsigned s_ssbldsz; /* Second stage boot loader size. */ unsigned char s_fill[288]; /* Adjust this to reach 512 bytes. */ unsigned s_checksum; /* Superblock checksum (0-507). */ } superblock; Note that some fields are currently unused and some other are redundant. They are provided for future use and for additional consistency checkings. After the superblock, a number of blocks are reserved for the list of bad file system blocks. The information about the number of blocks reserved for this list is kept in the superblock. The amount of blocks reserved is decided when creating the file system with mkfs and cannot be changed afterwards. As explained before, the file system is divided into smaller pieces called clusters (cylinder groups). The first cluster is located at the end of the bad blocks list. Each cluster contains a superblock copy as its first block and two bitmaps (1 Kb each) to keep track of inodes and blocks. For each inode and block in that cluster there is a bit in the corresponding bitmap keeps its status: 0 means the inode/block is allocated, 1 means it is free. We can keep track of 8*1024=8192 blocks and 8192 inodes in such a bitmap, but since such a huge number of inodes per cluster would be inappropriate, only the blocks bitmap is completely used. After the superblock copy and the two bitmaps a cluster contains a number of blocks for the actual inodes (the number of inodes can be specified when creating the file system) and 8192 blocks. Inodes An inode is a small structure that keeps information about a file. The inode structures are kept on disk, as explained in the Layout section. Here it is the inode layout. It is 128 bytes long, and contains enough information to allow the kernel to access the file. Inode operations are subject of caching through the buffer cache. For even faster access, the kernel keeps a hash table of in core inodes, in order to figure out quickly if a given inode should be loaded from disk or it can be located into the main memory. Here it is the disk inode layout: typedef struct { __mode_t di_mode; /* File mode. */ __nlink_t di_nlinks; /* Inode number of links. */ __uid_t di_uid; /* File owner id. */ __gid_t di_gid; /* File owner group. */ size_t di_size; /* File size. */ size_t di_blocks; /* Real number of blocks. */ unsigned char di_addr[70]; /* Direct & indirect blocks map. */ unsigned short di_pipesize; /* Pipe size. */ __time_t di_atime; /* Last access time. */ __time_t di_mtime; /* Last modification time. */ __time_t di_ctime; /* Last status change time. */ __dev_t di_rdev; /* Special file major/minor numbers. */ unsigned short di_pipercnt; /* Pipe readers count. */ unsigned short di_pipewcnt; /* Pipe writers count. */ unsigned short di_piperoff; /* Pipe read offset. */ unsigned short di_pipewoff; /* Pipe write offset. */ unsigned long di_atime_usec; /* Fractional part of di_atime. */ unsigned long di_mtime_usec; /* Fractional part of di_mtime. */ unsigned long di_ctime_usec; /* Fractional part of di_ctime. */ __time_t di_ktime; /* Unmodifiable last modified time. */ } dinode; Each time a file is opened, an in core inode is allocated and the disk inode is loaded into it. An in core inode is an inode that contains all the information provided by a disk inode plus some other information related to the in core inode state: the reference count, hash table pointers, several flags, etc. typedef struct { /* Disk inode. Not included again for the sake of brevity. */ ..... unsigned char busy : 1, /* Busy flag. */ in_demand : 1, /* Access to the inode requested. */ modified : 1, /* Modified flag. */ mount_point : 1, /* The file is a mount point. */ write_denied : 1, /* Set when the file is currently being executed. */ exec_denied : 1; /* Set when the file is currently open for writing. */ unsigned char __fill; __dev_t device; __ino_t dinode; /* Disk inode number. */ __nlink_t nref; /* Inode reference count. */ unsigned short hprev; unsigned short hnext; unsigned short lprev; unsigned short lnext; } inode; In order to prevent possible races while allocating/deallocating disk inodes (by setting/resetting bits in the inode bitmaps), the kernel locks the superblock for inode operations. That is, the s_ilock flag is set into the in core copy of the superblock and any other process that will try to allocate or deallocate an inode will sleep until the lock is released. Here there are the two routines locking and unlocking the superblock: void sb_i_lock(superblock *sb) { while (sb->s_ilock) { sb->s_i_in_demand = 1; sleep(&sb->s_ilock, WAIT_SUPERBLOCK); } sb->s_ilock = 1; } void sb_i_unlock(superblock *sb) { sb->s_ilock = 0; if (sb->s_i_in_demand) { wakeup(&sb->s_ilock); sb->s_i_in_demand = 0; } } Given a disk inode, the kernel will allocate an in core inode for it. Then, the in core inode is filled with the contents of the disk inode. This is done by the i_get() routine which returns the in core inode number. When a disk inode is no longer needed, its corresponding in core inode is deallocated using the i_release() routine. Allocation and deallocation of disk inodes is handled by i_alloc() and i_free(). Basically, i_alloc() searches a free inode in the current cluster and, if it fails to find one, keeps switching to another cluster until a free disk inode is found. Of course, it first checks if there is at least one free disk inode in the file system before starting the actual search. i_free() simply sets the disk inode bit into the corresponding bitmap. During many file related operations the kernel has to guarantee to a process that it has exclusive access to a given inode. This is done by locking the inode before entering the critical region and releasing it afterwards. The implementation of the locking mechanism is similar with the superblock locking mechanism described before. The functions actually locking the inode are i_lock() and i_unlock(). When a file becomes bigger than about 20 Kb, the disk inode will not be able to keep track of all the blocks used by that file. As a result, block numbers will be kept into special blocks, called indirect blocks, and each time a read or write request will specify a file offset bigger than 20 Kb, a search through such indirect blocks will be initiated. Unfortunately, doing so for each block over 20 Kb will be expensive. The current version of the Thix File System reads all the contiguous blocks found in the last level indirect block and sends them to the corresponding device driver. This will reduce the time needed for indirect block parsing and will also improve the device driver performance because contiguous blocks are read/written faster. Blocks File system blocks are handled in a similar way. If a process needs a new file system block, it will pick up one from the current cluster, if possible. Otherwise, it will start searching for free blocks in other clusters. Note also that the superblock is locked during the search so that different processes searching for a new file system block will not interfere. File Tables The kernel keeps track of files using a global file descriptors table. Each structure in this table looks like this: typedef struct { unsigned short inode; unsigned short flags; unsigned count; unsigned offset; } fd_struct; Also the kernel keeps in u_area[] a per process table called `user file descriptor table' (ufd) that contains pointers to global descriptor table entries. Each process opening a file will receive a file handle (if the operation was successful) that is an index into the user file descriptor table. The kernel will use this ufd to get the file descriptor when accessing the file. Regular Files Since regular files are the most used type of files in the file system and the global system performance depends very much on their implementation, a brief discussion will help understanding how they are handled. The read() and write() system calls are entry points for access to all file types. They detect the actual file type and call the appropriate routine. If a regular file is detected, regular_read() or regular_write() is called. Due to the limited number of direct block entries in the inode structure, only the first 20 direct block numbers can be obtained from the inode. In order to be able to read the other blocks, the kernel will start searching through indirect blocks, as explained before. Based on the low level support provided by the inode implementation for getting sets of contiguous block numbers from the last indirect blocks, the read() and write() system calls provide a mechanism to optimize regular file operations by feeding the corresponding device driver with optimized requests. Such requests contain sets of contiguous blocks and can be usually handled in only one step. The kernel has to take care not to allow write operations on binaries that are currently executed or to try to execute a binary that is currently opened for write. Otherwise, if the system's load average is high and the swapper decides that a code page should be discarded, when the process will reload it from the file system, that page will contain something else and the process might die trying to execute random code. Directories Directories are in fact regular files that contain file entry points. Each directory entry contains an inode number and a file name. The size of the file name can be specified when creating the file system with the mkfs utility. The default is 30 bytes. The inode number is a 16 bit number, but in the future it will be a full 32 bit number, allowing the creation of file systems with huge number of files. Directories can be read in the same way normal files are. This is not recommended, though, because the kernel also provides a readdir() system call that fills a dirent structure. This structure will provide the user with the directory entry contents in a implementation independent way. The possibility of directly reading the directory contents is provided only for compatibility with older implementations of the UNIX system. The C library reads the directory contents using the readdir() system call. Writing to a directory is not permitted, a directory can be modified only by creating or deleting files. Here it is the dirent structure: struct dirent { __ino_t d_fileno; /* File inode number. */ size_t d_namlen; /* Length of the file name. */ /* Only this member is in the POSIX standard. */ char d_name[NAME_MAX + 1]; /* File name. */ }; Pipes The implementation of pipes provides all the features UNIX pipes need. This includes blocking, sending SIGPIPE, named and unnamed pipes, etc. Users can create pipes with the pipe() or mknod() system calls and access them through read() and write(). Because the kernel implements pipes in the file system and because a pipe does not exist before its use, the kernel must assign an inode for it on creation. It also allocates a pair of user file descriptors and corresponding file table entries for the pipe: one file descriptor for reading from the pipe and the other for writing to the pipe. It uses the file table so that the interface for the read, write and other system calls is consistent with the interface for regular files. Information about the number of pipe readers and writers and the current offsets is kept in the inode structure. Maintaining the pipe offsets in the inode allows convenient FIFO access to the pipe data and differs from regular files where the offset is maintained in the file table. Processes cannot adjust them via the lseek() system call so random access I/O to a pipe is not possible. Punti di mount In order to be able to access several file systems at the same time, UNIX systems usually mount a file system into an empty directory of an already mounted file system. When parsing a path (the historical namei() algorithm), the kernel detects directories (in fact inodes) that are mount points and continues to parse the path in the mounted file system in a transparent way. Once the mounted file system is no longer needed, the previously mounted file system can be unmounted (using the umount() system call) and the directory where the file system was mounted becomes accessible again. The kernel keeps track of mount points using structures like this: typedef struct { __dev_t device; /* Device (major/minor). */ int fd; /* mp file descriptor. */ int vmdev; /* VM device number. */ superblock *sb; /* Device superblock. */ int dir_i_no; /* Mount point parent directory inode. */ int mp_i_no; /* Mount point directory inode. */ int root_i_no; /* Root inode of the mounted fs. */ int icluster; /* Cluster used for op. on inodes. */ int bcluster; /* Cluster used for op. on blocks. */ int icount; /* Free inodes in ibitmap. */ int bcount; /* Free blocks in bbitmap. */ unsigned *ibitmap; /* Current inodes bitmap. */ unsigned *bbitmap; /* Current blocks bitmap. */ } mp_struct; When a new file system is mounted, the superblock is checked for consistency (including magic numbers, etc) and if the file system to be mounted is not valid, the mount operation will fail. ---------------- L'utility fsck ---------------- I file systems di tanto in tanto hanno bisogno di essere riparati, a causa dei crash di sistema o delle interruzioni dell'alimentazione. Quando succede qualcosa del genere, solitamente il sistema va giù senza avere possibilità di sincronizzare il file system. I buffer di scrittura ritardati non saranno svuotati e, come risultato, la struttura del file system diverrà inconsistente. Il più delle volte le inconsistenze rendono il file system instabile. Con un po' d'attenzione in ogni caso, parte o tutti i dati possono essere recuperati, e il file system può essere riutilizzato. I sistemi Unix di solito forniscono un'utility chiamata 'fsck' (file system check) che puo' essere usata per riparare un file system danneggiato. Per prevenire problemi, l'utility fsck dovrebbe essere eseguita in modo 'singolo utente'. Eseguire un'utility di riparazione del file system mentre altri programmi stanno leggendo o scrivendo è generalmente una cattiva idea, perché tale utility accede al file system a basso livello e potrebbe interferire con le altre operazioni ad alto livello, Come ogni altro sistema Unix, Thix fornisce l'utility fsck. Durante lo sviluppo, questa utility si è dimostrata veramente utile e capace di riparare dei file system pesantemente danneggiati con una percentuale molto bassa di dati persi. Discuterò qui l'implementazione di fsck com'è stata applicata all'ultima versione del Thix File System. Passo 1- Controllare il Superblock -------------------------------------------------------------------- Prima di tutto, l'utility fsck prova ad aprire il device specificato e controlla la consistenza del superblock. E' usato un algoritmo similare a quello della chiamata di sistema "mount", eccetto per il fatto che fsck si rifiuta di continuare solo se è incontrato un errore irrecuperabile. Questo è il primo passo dell'utility fsck. Passo 2 - Controllo Inodes e Blocchi -------------------------------------------------------------------- Nel secondo passo, è controllato ogni cluster degli inode e dei blocchi della bitmap. Ogni inode che è marcato come libero nella bitmap, dovrebbe avere il proprio bit di_mode settato a zero, e non dovrebbe avere links. Ogni inode che è marcato come in uso nella bitmap dovrebbe contenere un campo "file type" valido. Altrimenti all'utente sarà chiesto di inserire un "file type" valido. Il default è S_IFREG (file regolare). Anche gli inode in uso dovrebbero avere un numero di link diverso da zero. Una volta che un inode in uso ha passato questo test, è calcolato il suo numero di blocchi dati, e confrontato con il campo di_blocks. Se il numero di blocchi è inesatto, il suo valore è settato con quello corretto. Durante questo passo l'intera mappa dei blocchi in uso è registrata e la bitmap dei blocchi è aggiustata. Passo 3 - Controllo di files e directory -------------------------------------------------------------------- Se gli errori incontrati nei primi due stadi sono troppo grossi e non possono essere risolti "al volo", fsck si rifiuterà di continuare. Eseguendo di nuovo fsck si dovrebbero risolvere ulteriori problemi (solitamente tutti i precedenti) e questo permette di proseguire negli stadi successivi del programma. Notare che questo non succede quando fsck è in grado di correggere tutti gli errori. Quando si incontra un errore, è incrementato il contatore globale degli errori, ma solo quando l'errore è stato corretto è decrementato e l'esecuzione continua normalmente. Nel terzo stadio, è controllato l'intero albero del file system e tutte le directory. Ogni Entry dovrebbe puntare ad un numero d'inode valido, altrimenti l'entry è cancellata (il numero dell'inode è settato a zero) poiché non c'e' modo di recuperare il file cui punta (se mai ci fosse). Durante questo stadio, ogni numero di inode dei link è controllato. Passo 4 - Ricontrollare gli Inode per numeri di links invalidi -------------------------------------------------------------------- Nell'ultimo passo il numero di links calcolati nel terzo stadio sono comparati con il numero di links attualmente trovati negli inode. Se sono riscontrate differenze, i campi di_nlinks sono settati col valore calcolato. fsck alle volte fallisce nel suo tentativo di riparare il filesystem in un solo passo. Questo è normale, poichè gli errori incontrati nei primi stadi possono affliggere i risultati degli stadi successivi. fsck ritorna zero solo se non sono stati riscontrati errori durante l'esecuzione dei quattro stadi prima descritti. L'utility fsck sarà migliorata man mano che il file system diverrà più complesso. Gli utenti hanno chiesto quali cose dovrebbero essere gestite di solito, perciò l'azione di default è solitamente "correggere". fsck dovrebbe essere migliorato per permettergli di gestire alcune condizioni che si presentano quando è eseguito su di un file system montato. ---------------------------------- Implementazione dei Device Drivers ---------------------------------- Floppy Disk:Il device driver dei floppy disk Hard Disk: Il device driver dell'hard disk Virtual Terminals: Il device driver dei terminali virtuali Physical Memory: Il device driver della memoria fisica Kernel Memory: Il device driver della memoria del kernel Null: Il null device driver *Device Driver dei floppy disk Sui PC, il trasferimento dei dati tra floppy disk e memoria principale è effettuato il secondo canale DMA (direct memory access).. Per leggere i dati dal dischetto, il driver invierà i parametri posizionali al controller del lettore floppy, programmerà il canale DMA per leggere la quantità richiesta di dai e quindi entrerà in sleep, aspettando il verificarsi dell'apposito interrupt. Quando il controller finisce di trasferire i dati, viene inviato un interrupt e il processo entrato precedentemente in sleep viene risvegliato e procede nella sua esecuzione. Questo è principalmente cosa avviene all'interno del driver floppy, anche se l'attuale implementazione è più complicata, a causa del fatto che devono essere passati al controller e al canale DMA molti parametri per far funzionare tutto correttamente. Per cortesia consultate i sorgenti del driver o le specifiche tecniche dei controller per maggior dettagli. *Device Driver dell'Hard Disk In contrasto al driver dei floppy, quello del controller IDE degli HD non usa il canale DMA. Questo porterebbe ad un eccessivo rallentamento, così il trasferimento dati da/per l'hard disk e' effettuato tramite le porte. Quando si scrivono dati sul disco, accadono cose quasi uguali a quelle del driver del floppy (eccetto il fatto che non stiamo usando il canale DMA). Il driver invia i parametri posizionali al controller, quindi scrive i dati nella porta 0x1F0 e entra in modalità sleep, aspettando l'interrupt. Quando si leggono i dati invece, tutte le operazioni devono essere effettuate all'interno dell'interrupt, così l'interrupt lascia il controller in uno stato "pulito", pronto ad accettare nuovi comandi. Questo implica che non possiamo lasciare il task di lettura dati dal controller al processo che ha iniziato la richiesta, ma al processo in esecuzione quando è avvenuto l'interrupt. Brevemente, l'interrupt handler aspetterà fino a quando il controller non è pronto, e quindi leggerà i dati. *Device Driver dei terminali virtuali Il kernel implementa 12 terminali virtuali. Cambiare da uno all'altro con i tasti funzione e' semplice, e finché il kernel sta girando, ogni singolo utente può avere sessioni differenti (eventualmente con diversi nomi di login) senza per questo dover eseguire il programma 'screen'. Certamente questo induce un sovraccarico in più del kernel in termini di memoria, ma rimane comunque un'utile caratteristica messa a disposizione da molti sistemi UNIX. Ogni terminale virtuale e' trattato come un terminale indipendente, con i suoi propri contenuti dello schermi, posizione del cursore, modalità corrente etc. Ogni terminale è provvisto di una coda di ingresso di 256 caratteri, il che permette sufficiente spazio per digitare ogni carattere. per essere il più efficiente possibile, i terminali virtuali implementano lo scrolling hardware, traendo vantaggio dalla caratteristica dei chip CGA/EGA/VGA di cambiare l'indirizzo di partenza della modalità testo. Al momento sono implementate le seguenti "termcap capabilities": ho ll le nd up do vb vs vi ve cl cd ce al dl AL DL dc sf sr so md mb me cm I terminali virtuali forniscono un'implementazione pressoché totale delle specifiche POSIX. Supportano i modi terminale canonici e non canonici, posizionamento assoluto del cursore, caratteri di interrupt e di kill, input bufferizzato, timeouts, etc. Il supporto per i colori standard ANSI e' stato implementato di recente. Un entry completa delle termcap per i terminali vtty (terminali virtuali) è fornita col sistema. E' stato effettuato il porting della libreria GNU termcap e i programmi interattivi come editor e file manager sembra non abbiano problemi ad usarla. Di seguito l'entri standard dei terminali vtty: vt|vtty|Thix virtual terminal:\ :co#80:li#25:am:km:bl=^G:\ :ku=\EA:kd=\EB:kr=\EC:kl=\ED:kb=^H:\ :k1=\E@a:k2=\E@b:k3=\E@c:k4=\E@d:k5=\E@e:\ :k6=\E@f:k7=\E@g:k8=\E@h:k9=\E@i:k;=\E@j:\ :F1=\E@k:F2=\E@l:\ :kP=\EI:kN=\EJ:kI=\EE:kD=\EF:kh=\EG:kH=\EH:\ :cm=\E]%i%d;%dH:cr=^M:\ :ho=\EMH:ll=\EML:le=\EME:nd=\EMN:do=\EMD:\ :vb=\EB:vs=\EVS:vi=\EVI:ve=\EVE:\ :cl=\ECS:cd=\ECD:ce=\ECE:\ :al=\ELA:dl=\ELD:\ :dc=\EDC:\ :sf=\ESF:sr=\ESR:\ :ms:so=\EAS:se=\EAE:mr=\EAS:md=\EAD:mb=\EAB:me=\EAE: *Device Driver della memoria fisica Il driver della memoria fisica (/dev/mem) fornisce l'accesso alla memoria del computer. Leggere o scrivere ad indirizzi al di fuori dello spazio di indirizzi fisici non produrrà un'eccezione di pagina, ma il sistema delle chiamate di lettura/scrittura ritornerà il numero di caratteri letti/scritti (probabilmente 0, dipende dall'argomento della chiamata di sistema). *Device Driver della memoria kernel. Il driver della memoria kernel (/dev/kmem) fornisce accesso alla memoria virtuale del kernel. Puo' essere usato per esaminare o patchare il kernel. Usando lo speciale file kmem, un processo puo'accedere fino a 4Gb di memoria virtuale. *Il Null Device Driver Il null device driver (/dev/null) e' il più semplice driver del kernel, fornisce una funzione di lettura che ritorna sempre zero e una funzione di scrittura che ritorna sempre il numero di caratteri specificati nella richiesta stessa di scrittura. PARTENZA DEL SISTEMA (Startup) Solitamente ci sono un sacco di inizializzazioni che devono essere fatte per avere un sistema attivo e funzionante. Molte di loro sono relative all'hardware, ed includono il controller degli interrupt (PIC), la tastiera, etc. C'è anche bisogno del rilevamento del tipo e/o taglia del floppy e dell'hard disk. e altri componenti hardware, e di inizializzare lo stack del processore e le tabelle IDT e GDT. Come secondo passo, devono essere inizializzate diverse parti del kernel: device drivers, gestore della memoria virtuale, lo schedulatore e il file system sono solo alcune di loro. Interrupt Controllers: Inizializzazione del controller degli interrupt Tastiera: Inizializzazione tastiera Floppy Drives: Rilevazione Floppy Drives Hard Drives: Rilevazione Hard Drives Terminali: Inizializzazione Terminali Virtuali -------------------------------------------------------------------------------- Inizializzazione del controller degli interrupt -------------------------------------------------------------------------------- Le piastre madri dei PC usano due controller di interrupt Intel8259. Solitamente sono chiamati I8259A e I8259B. Tutti gli interrupt dell'I8259B sono mappati sul secondo livello di interrupt del primo controller (I8259A - interrupt in cascata). Per inizializzare i due controller, il kernel invia ad entrambi la sequenza di inizializzazione, quindi invia i numeri di avvio degli interrupt hardware (0x20 per l'I8259A e 0x28 per l'I8259B, per permettere la mappatura sugli interrupt riservati Intel (0x00-0x1F)). Il primo controller è settato come master ed il secondo come slave, entrambi in modalità 8086. Poichè la versione corrente del kernel gestisce solo gli interrupt hardware del controller dei floppy e dell'hard disk (IRQ 0x06 e IRQ 0x0E), del clock di sistema (IRQ 0x00) e della tastiera (IRQ 0x01), tutti gli altri interrupts hardware sono mascherati (ignorati). La sola eccezione e' l'IRQ 0x02 che e' rilevato per permettere la ricezione degli interrupt provenienti dal secondo controller degli interrupt (solitamente IRQ 0x0E), che è mappato su questo IRQ. -------------------------------------------------------------------------------- Inizializzazione della Tastiera -------------------------------------------------------------------------------- Alcuni PC necessitano di una sequenza di inizializzazione della tastiera al momento dell'accensione. E' strano, perchè molte macchine funzionano bene anche senza, principalmente perchè se ne occupa il BIOS al momento del boot. La sequenza di inizializzazione prima legge un tasto (?!) e dopo setta l'indirizzo di linee della tastiera. Senza questa sequenza, qualche PC semplicemente carica il kernel ma non riceve nessun interrupt hardware dalla tastiera. -------------------------------------------------------------------------------- Rilevamento dei lettori floppy -------------------------------------------------------------------------------- I tipi di lettore floppy sono rilevati al momento dell'inizializzazione del device driver. I tipi sono memorizzati nella memoria CMOS all'indirizzo 0x10 (4 bits per ogni floppy). Al momento il kernel supporta solo i floppy da 1.2Mb e 1.44mb, ma aggiungere nuovi tipi di floppy è solo questione di aggiungere nuove tabelle con i parametri da passare al controller per i nuovi tipi e creare per loro devices con minor number differente. -------------------------------------------------------------------------------- Rilevamento dei dischi rigidi (Hard Disk) -------------------------------------------------------------------------------- Anche gli HD sono rilevati dalla memoria CMOS (indirizzi 0x12, 0x19 e 0x1a). La geometria attuale degli HD è ottenuta al momento del boot dalla area dei dati del BIOS ed il driver la usa al momento in cui è inizializzato. L'inizializzazione del driver dell'hard disk è più complicata di quella del floppy, perchè gli hard disk sono solitamente partizionati e il kernel deve essere in grado di trattare ogni partizione come un device logico differente. Così, dopo che sono stati rilevati geometria e tipo dell'hard disk, viene letta la tabella delle partizioni e inizializzata la corrispondente tabella di dati del device. -------------------------------------------------------------------------------- Inizializzazione dei Terminali Virtuali -------------------------------------------------------------------------------- Il device driver dei terminali virtuali è il primo driver registrato dal kernel. Questo è fatto per avere la possibilità di visualizzare messaggi sullo schermo al momento del boot del sistema. Il driver dei terminali virtuali prima rileva il tipo di display (colore o monocromatico), quindi inizializza tutti i terminali virtuali e setta il focus sul primo di loro, correntemente usato per visualizzare informazioni di debug del kernel. -------------------------------------------------------------------------------- Stato Attuale -------------------------------------------------------------------------------- Molti pacchetti software free sono stati portati sul sistema Thix. Il kernel sembra essere abbastanza stabile, e capace di far girare molti programmi disponibili su internet, ma che non necessitano di networking. Sono state portate anche alcune librerie che svolgono compito un pò per tutti i gusti, come la libreria readline, la regex etc, nel tentativo di fornire più strumenti UNIX possibile. Il porting del compilatore GNU C e delle utility relative è stato il primo passo nella costruzione di un ambiente di sviluppo completo. I file header sono un mix tra i file header dello standard ANSI C presi dalla libreria C dello GNU e i file include di Thix, anch'essi sempre compatibili ANSI C. Sono disponibili anche file header per le librerie aggiuntive. A breve sarà disponibili il porting di Emacs, in modo che questo potente ambiente aiuti ulteriormente lo sviluppo. Di seguito una lista di utilities portate con successo sotto Thix. Molte di esse sono compilate sotto Thix, usando il compilatore GNU C versione 2.5.8. Eseguibili: ar as banner basename bash bc c++filt cal cat chgrp chmod chown cksum clear cmp comm compress cp cpp csplit cut date dhrystone dirname dosdir dosread echo egrep env expand expr false fgrep fold fsck g++ gasp gcc git grep gunzip gzip head hostname id init joe join kill ld ln login logname ls mail make man mesg mkdir mkfs mknod more mount mv nice nl nm nohup objcopy objdump od passwd paste pathchk pr printenv printf protoize ps pwd ranlib reboot renice rgrep rm rmdir sed sh size sleep sort split strings strip stty su sum swapon sync tac tail tar tee test tfsck time touch tr true tty umount uname unexpand uniq unprotoize update users vi vmstat wc which who whoami yes Librerie: libc.a libreadline.a libtermcap.a libregex.a libtilde.a libm.a libmcheck.a libhistory.a libposix.a libglob.a libbsd-compat.a Molti di questi programmi e librerie provengono dai pacchetti GNU liberamente disponibili. Alcuni di essi provengono invece da Minix. Ho scritto ex-novo le utility relative al file system (fsck, mkfs, mount e umount) e il programma init poichè sono specifici del sistema. -------------------------------------------------------------------------------- LAVORI DA FARE -------------------------------------------------------------------------------- Prima di tutto, intendo testare nel miglior modo possibile il codice scritto fino ad adesso. nessuno può dire che un sistema operativo è esente da errori, poichè eseguirne il debug è solitamente molto difficile. Una delle migliori maniere per farlo sembra essere quella di eseguire il porting del software esistente ed eseguirlo sul sistema. Il kernel ha bisogno di essere completato sotto molte aspetti, specialmente nella gestione della memoria virtuale e nel file system. Cose come mappare i files e i device nella memoria, gruppi supplementari, lock dei file, IPC etc, dovrebbero essere implementati, poichè necessitano al funzionamento di molti programmi. Dovrebbe essere aggiunto anche il supporto per la FPU, per macchine che ne posseggono una (i387/i487), per le macchine senza FPU il compilatore GNU C fornisce una libreria di emulazione software. Devono essere scritti molti driver, i driver delle seriali e della parallela sono molto importanti. Anche il driver del mouse è importante per iniziare il porting del sistema X11R6. Tale porting richiede anche una chiamata a ioctl() per mettere la tastiera in modalità raw, un meccanismo di memoria virtuale per mappare la memoria video dentro lo spazio virtuale di indirizzi dell' X server, supporto per la chiamata di sistema BSD select() e un canale di comunicazione full duplex. L'ottimizzazione del file system è un'altra cosa che andrebbe fatta. Il nucleo degli inodes dovrebbe essere allocato dinamicamente e l'algoritmo dello switching dei cluster migliorato. Dovrebbe essere aggiunto anche il supporto per il file system virtuale, per montare altri tipi di fs ed usarli come se fossero nativi del sistema. Intendo anche migliorare lo scheduler dei processi, per renderlo capace di differenziare i processi in base alla classe degli utenti. Molti sistemi UNIX su cui ho lavorato, mancano di questa capacità ed iniziano a piantarsi se qualche utente malizioso avvia una marea di processi che consumano tempo macchina. Il kernel deve essere capace di controllare la quantità di tempo della CPU che i processi di un dato utente possono ottenere, Limitare il numero dei processi che un utente può lanciare (CHILD_MAX) non sembra un metodo sufficientemente valido. References [1] Maurice J. Bach "The Design of the UNIX Operating System" [2] Andrew S. Tanenbaum "Operating Systems: Design and Implementation" [3] Andrew S. Tanenbaum "Modern Operating Systems" [4] IEEE Standard 1003.1 "Portable Operating System Interface for Computer environments" -------------------------------------------------------------------------------- This document was generated on 10 June 1999 using the texi2html translator version 1.51a.