\chapter{Tour of the \linux\ kernel source}\label{tour} {\bf [The ``I'' in this chapter is Dan Miner. This chapter needs to be significantly re-worked before I consider taking it out of the appendix and making it a chapter.]} I wrote this for one simple reason: The source to \linux\ is getting rather large and navigating the source tree is becoming increasingly harder. This is only a guide for the programmer wishing to add or modify functions and services in the kernel. I will give an overview of the \linux\ sources, describing the contents of each of the files. The source for the \linux\ kernel assumes that it has been installed in /usr/src/linux. It is possible to change this, but since it is the default, we will refer to the root of the \linux\ source directory as /usr/src/linux, and assume that if you have changed this, that you are savvy enough to understand. This means that we will base all our file references from the /usr/src/linux/ directory. This was developed in reference to \linux\ version 0.99.8. \section{boot directory} This contains the default bootstrap and initialization code for the kernel. All of this is placed in a file, which is attached to the very beginning of the ``Image'' file to create a bootable disk. The ``boot'' code is only used if you are booting from a floppy disk, whereas the setup and initialization code is used no matter what your booting method is. LILO replaces the ``boot'' code with a much more sophisticated booting method, and then transfers control to the setup code. For more information on this, get the LILO package. It includes an excellent document on the boot process on PC's, and of the partitioning system as well. It is available for anonymous ftp as {\tt tsx-11.mit.edu:/pub/linux/packages/lilo/lilo.{\em n}.ps.Z} where {\em n} is the version number. \subsection*{boot/bootsect.S} This is the source to the bootstrap code that is responsible for loading \linux\ from a floppy disk. It is capable of handling low and high density disks. A major bug with this code is that it will lockup the computer should anything go wrong. So, no warnings here; it's a cross fingers and pray ritual. \subsection*{boot/setup.S} This fetchs all the information about the computer (ie. Memory availible, video card detection, etc.) from BIOS and initializes the gdt tables, page directory(s), idt tables, etc. These activities happen here: \begin{itemize} \item Moving kernel to 0x00000000 \item Reprogramming the interrupt handler to map interrupts to 0x20 - 0x2f (instead of 0x08 - 0x10 by BIOS) \item gdt table and register initialized for overlaping segments (base = 0, length = 8 meg). One segment is for data and the other is for code (execution in protected mode). \item idt table and register initialized. Basically, it is setup for NO interrupts. \item A20 is turn on. (Method for addressing more than 1 meg of memory) \item Finally, we actually switch to protected mode. \end{itemize} Most of these preparations will be modified later for the paging system and interrupts. Read a book on the 386 for more details, such as {\em Advanced 80386 Programming Techniques\/} by James L. Turley. See the Anotated Bibliography for details, Appendix~\ref{bibliography} \subsection*{boot/head.S} Here we find the actually beginning stages of ``setup'' for the kernel itself. First, the idt table (256 entries) is initialized for the {\tt ignore\_int()} interrupt gate. Interrupts are still disabled here. Next, it checks to see if the A20 line is {\bf really} set. It will lock the computer if it isn't. It then tests for 386 or 486 along with math coprocessor. The next important detail is paging. The page tables are created and ``Identity-mapped'', meaning location 1034 actually equals location 1034. Of course, paging is enabled. The gdt and idt registers are reloaded and the pre-fetch queue is flushed. Next to last, parameters are passed to kernel, which are hardcored to be none. Finally, we jump into the actual kernel. There are many data areas here. Two worth mentioning is the {\tt \_tmp\_floppy\_area} and {\tt \_floppy\_track\_buffer}. The first is used when DMA (Direct Memory Access) cannot reach an allocated buffer block in the kernel. The other holds a whole track on a floppy, used to speed reading. \section{fs directory} The VFS (virtual filesystem) ``layer'' is contained here along with all the specific filesystems. The VFS allows applications to access files on different filesystems in a unified interface. Most importantly, it allows the kernel programmer to ignore which filesystem to reference for a file operation. This directory also contains the sources for the following filesystems, ext, ext2, isofs, minix, msdos, nfs, proc, and xiafs. Also, the routines for loading and executing programs are here. \subsection*{fs/ext directory} This was Linux's second filesystem to be added. It boasted a 255 character file name with filesystems of up to 4 GB in size. This was a welcome relief from the 14 character file name limit and the 64 MB size limit in the old minix filesystem. This filesystem supported as the usual files; regular, device, symlinks, etc. One of the major problems with the extended filesystem was the fact it used linked lists to keep track of free space. This means, among other things, that once the filesystem is corrupt, it is very hard to recover. {\bf [Is this true?]} It was also very slow, much slower than the minix filesystem, again due to the use of linked lists to keep track of free space. \subsection*{fs/ext2 directory} Basically, this was added because of the major changes to extended filesystem were incompatibile with the previous filesystems that people had already installed. This filesystem looked a lot like the extended filesystem, except it now supported a bitmap, like the minix filesystem. Bitmaps are faster than linked lists, because they are smaller and therefore much more of a bitmap can be kept in memory at once, and because indirection is limited. This made correction in corrupted filesystems much easier. {\bf [Again, is this true?]} Also, a feature was the this system did bookkeeping on fragmented space and employed a caching system. This file system has gone under two major revisions. \subsection*{fs/iso directory} This is the standardize filesystem used on CD-ROM media. The group responsible for the standard is ISO (International Standards Organization)\footnote{Or {\bf Interminble Systems Opressors,} take your pick\dots} This is a very flexible system. With the invention of WORM (write once, read many) drives, the filesystem had to be 'changed' when the media was unable to change after been written to. There is not much I can tell about. It has 255 character file name limit. I don't believe many people are using it and I'm unfarmilar with the system. {\bf [Cop-out. I need to contact the author about this one. :) -dm] } {\bf [Actually, this is what is used on CD-ROMs, with very few exceptions. This version of the filesystem supports several different versions of CD-ROM filesystems, including all the major ones. -mkj]} \subsection*{fs/minix directory} \linux\ was first developed under Minix by Linus Torvalds. Naturally, he made his first filesystem compatible with Minix to make development easier. There are two minix filesystems availible (with a third forthcoming someday- V2.00). {\bf [Huh? Are you talking about for minix, or what?]} The first one has a 14 character file name limit and a 64 MB reach. It was the defacto filesystem because the root filesystem couldn't be any but this one for a long time. The second version supports 30 character file names. \subsection*{fs/msdos directory} The directory name says it all. You can mount MS-DOS disks and access the data without mtools anymore. It employs a cache system to speed things up. With dosemu you can even run many DOS programs, and support is being added to run those programs directly from \linux\ filesystems, including the DOS filesystem. \section{init directory} This directory contains one file, main.c. This is where the kernel initializes itself and all the device drivers. Also, multitasking is started and the program `/etc/init' is executed to bring up the rest of the system by interpreting the shell script /etc/rc. We start in the function {\tt start\_kernel()}. Here are the details. \begin{itemize} \item Save the information from BIOS and the boot/startup procedures. \item Calculate the total memory availible and round {\bf down} to the nearest 4k granularity (imposed by the gdt entries). (Not that you are likely to have an ammount of memory not a multiple of 4K anyway\dots) \item Set the size of the RAMDisk. \item A conditional compile for 16 Meg maxmium is possible. If in effect, the total memory is lowered to 16 megs if greater. \item You can mount the root filesystem as read-only. The flags for the root fs are set appropriately. \end{itemize} \section{lib directory} This contain library-like routines for parts for the kernel to to do the equivalent of a syscall, for the most part. It also includes {\tt kmalloc()} and {\tt kfree()}, which are a little different from their standard library {\tt malloc()} and {\tt free()} counterparts, and are documented in malloc.c, as well as in this manual. See section~\ref{how-device} and the appropriate section 9 man pages for more information on this. \section{kernel directory} \subsection*{kernel/dma.c} This is where DMA channel management is located. This note of usage is taken from it (0.98.5): \begin{quote} All drivers needing DMA channels, should allocate and release them through the public routines {\tt request\_dma()} and {\tt free\_dma()}. In order to avoid problems, all processes should allocate resources in the same sequence and release them in the reverse order. So, when allocating DMA channels and IRQ's, first allocate the IRQ, then the DMA. When releasing them, first release the DMA, then release the IRQ. If you don't, you may cause allocation requests to fail unnecessarily. This doesn't really matter now, but it will once we get real semaphores in the kernel. \end{quote} \subsection*{kernel/exit.c} This is where all the routines for managing the `exit' of a process. (i.e.. called exit() in a program, segmentation fault) It also is the home for the following system calls: (Note: syscalls always have the prefix sys\_) \begin{screen}\begin{verbatim} int sys_kill (int pid, int sig) int sys_exit (int error_code) int sys_wait4(pid_t pid, unsigned long *stat_addr, int options, struct rusage *ru) \end{verbatim}\end{screen} {\tt sys\_waitpid()} remains for compatibility. {\tt waitpid()} should be implemented by calling {\tt sys\_wait4()} from libc.a \subsection*{kernel/fork.c} Home of the system call {\tt sys\_fork()} and its helpers. \subsection*{kernel/ioport.c} The 386 (and up) support what is called an I/O permission bitmap. These routines allow you to modify the map for a task. Each bit in this bit array corresponds to an I/O port. If a bit in this array is false (0) then any refence to that port address will be denied. An example, say you wanted to do graphics without Xwindows. You would need to get permission to read/write to the video ports. Note, you must be super user (effective uid of 0) to do this. \noindent Home of: \begin{screen}\begin{verbatim} int sys_ioperm (unsigned long from, unsigned long num, int turn_on) \end{verbatim}\end{screen} (for ports 0x0000 - 0x03ff) \begin{screen}\begin{verbatim} int sys_iopl() \end{verbatim}\end{screen} (for ports beyond 0x03ff; requires 8 kb I/O bitmap) \subsection*{kernel/irq.c} Source for the IRQ handling and requests. \subsection*{kernel/itimer.c} Code for Interval timers. \noindent Home of: \begin{screen}\begin{verbatim} int sys_getitimer (int which, struct itimerval *value) int sys_setitimer (int which, struct itimerval *value, struct itimerval *ovalue) \end{verbatim}\end{screen} \subsection*{kernel/mktime.c} Source to convert a time structure into its coded long value. \subsection*{kernel/panic.c} This nifty little routine is used throughout the kernel. If called, you have a {\bf major} problem. \subsection*{kernel/printk.c} Central print routine in the kernel, replacing {\tt printf()} in normal C programs. Note that this routine prints to the {\bf console}, i.e. /dev/console. Messages are also logged through the {\tt syslog()} system call and can also be read from /proc/kmsg if the proc filesystem is mounted. \subsection*{kernel/ptrace.c} Source for process tracing. \noindent Home of: \begin{screen}\begin{verbatim} int sys_ptrace (long request, long pid, long addr, long data) \end{verbatim}\end{screen} \subsection*{kernel/sched.c} Main kernel routine, the scheduler. \noindent Home of: \begin{screen}\begin{verbatim} int sys_pause (void) int sys_alarm (long seconds) int sys_getpid (void) int sys_getppid (void) int sys_getuid (void) int sys_geteuid (void) int sys_getgid (void) int sys_getegid (void) int sys_nice (long increment) \end{verbatim}\end{screen} \subsection*{kernel/signal.c} Code of the signal mechanism and handling routines. \noindent Home of: \begin{screen}\begin{verbatim} int sys_sgetmask () int sys_ssetmask (int newmask) int sys_sigpending (sigset_t *set) int sys_sigsuspend (int restart, unsigned long old_mask, unsigned long set) int sys_signal (int signum, long handler, long restorer) int sys_sigaction (int signum, const struct sigaction *action, struct sigaction *oldaction) \end{verbatim}\end{screen} \subsection*{kernel/sys.c} Heart of the kernel. Note, there are a few that are not implemented. \noindent Home of: \begin{screen}\begin{verbatim} int sys_setpriority (int which, int who, int niceval) int sys_getpriority (int which, int who) int sys_profil () int sys_ftime () int sys_break () int sys_stty () int sys_gtty () int sys_prof () int sys_vm86 (struct vm86_struct *v86) int sys_reboot (int magic, int magic_too, int flag) int sys_setregid (gid_t rgid, gid_t egid) int sys_setgid (gid_t gid) int sys_acct () int sys_phys () int sys_lock () int sys_mpx () int sys_ulimit () int sys_time (long *tloc) int sys_setreuid (uid_t ruid, uid_t euid) int sys_setuid (uid_t uid) int sys_stime (long *tptr) int sys_times (struct tms *tbuf) int sys_brk (unsigned long end_data_seg) int sys_setpgid (pid_t pid, pid_t pgid) int sys_getpgrp (void) int sys_setsid (void) int sys_getgroups (int gidsetsize, gid_t *grouplist) int sys_setgroups (int gidsetsize, gid_t *grouplist) int sys_newuname (struct new_utsname *name) int sys_uname (struct old_utsname *name) int sys_sethostname (char *name, int len) int sys_getrlimit (unsigned int resource, struct rlimit *rlim) int sys_setrlimit (unsigned int resource, struct rlimit *rlim) int sys_getrusage (int who, struct rusage *ru) int sys_gettimeofday (struct timeval *tv, struct timezone *tz) int sys_settimeofday (struct timeval *tv, struct timezone *tz) int sys_umask (int mask) \end{verbatim}\end{screen} \subsection*{kernel/traps.c} Handles hardware traps and faults. \subsection*{kernel/vsprintf.c} Implements vsprintf for the kernel because the kernel can't use the standard library. \subsection*{kernel/sys\_call.S} This contains the system-call and fault low-level handling routines, the timer-interrupt handler, as well as all interrupts and faults that can result in a task-switch. {\bf NOTE:} This code handles signal-recognition, which happens every time after a timer-interrupt and after each system call. \subsection*{kernel/FPU-emu directory} This contains the floating point math emulator code. This is highly technical code, so paraphrasing from the README: This emulator is based on the FPU in the 80486. Unfortunatly, it isn't a full implementation (don't blame the author). It covers the basic arithmatic and many of the trigonometric functions. The author hopes that all functions C or Fortran uses are covered. Most of the control bits are implemented, as are partial load/store operations. The main aim was to provide good accuracy in a ``reasonable'' time. It uses classic algorthms found in Numerical Analysis for many of its more complex functions (trig, exp(), etc...) Possible problems can happen when the emulator is interrupted (for example, by swapping) and another task requires floating-point operations. Due to static data, some control ``registers'' can be overwriten {\bf [Right?]} See the README for more details and limitations. \subsection*{kernel/blk\_drv directory} This is the directory for the block devices; in here is the floppy, generic hard drive, ram disk, and SCSI drivers. \subsection*{kernel/blk\_drv/scsi directory} This handles hard drive that use SCSI to communicate with the computer. The SCSI I/O controls are include here. The following adaptors are supported: \begin{itemize} \item Seagate ST-01 and -02 \item Future Domain 850, 950, 1440, and others \item Adaptec 1542B, 1542C, and 1740 \item WD 7000Fasst \item Ultrastor 14F, 24F, and 34F \end{itemize} \subsection*{kernel/chr\_drv} This directory contains the character devices.