\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.

