Make your own free website on Tripod.com

Linux - a journey

by C Hanish Menon (www.hanishkvc.com)
date: Jun 2001
license: GPL for documents


Table of Contents

  1. THE INTRODUCTION
    1. LINUX
    2. GUI SYSTEM
    3. APPLICATIONS
    4. THE SYSTEM
  2. THE LINUX SYSTEM
    1. THE LINUX KERNEL
    2. LINUX BOOT PROCESS
    3. CONTEXT SWITCH LOGIC
    4. MMU SUBSYSTEM
    5. IO SUBSYSTEM
    6. INTERRUPT SUBSYSTEM
    7. MISC. HAL
      1. TIMER
      2. DMA
      3. Keyboard Controller
    8. CHAR DEVICES
    9. BLOCK DEVICES
    10. NETWORK DEVICES
    11. THE APPLICATIONS

Table of Figures/Tables

  1. The System
  2. The Linux kernel
  3. The Linux Boot process
  4. The Applications

Chapter 1

The Introduction

The integrated future.

Technology is taking us to a future made of Integrated multi function devices which are compact, convenient and economical from the end user perspective. Linux makes a lot of sense for such devices, what with the currently available Processing power and Memory in these devices. With internet being as popular as it is, and with the integration of Internet access capabilities into most of these devices the Network stacks in the kernel, the free and flexible GUI and InternetAccessClients available with Linux help a lot.

KEY MODULES
Linux
GUI System
Applications

Linux

An Embeddable Linux System basicaly consists of a Linux kernel along with a mini Linux distribution. This in turn provides the system environment in which the other modules/applications run. It takes care of managing the resources available in the system and providing it to the other modules as found necessary. It also takes care of abstracting the hardware features in friendly manner for the other modules, so that they are portable to a great extent.

GUI System

The GUI system helps abstract the User Interface devices of the system from the applications that interact with the user. It includes drivers for the Graphics Chipset and the Input devices like Keyboard or Mouse or IR-Gadgets. It also takes care of providing a standard Application Programming Interface for the GUI functionality, thus allowing developers to produce GUI applications. Also the look and feel of the applications will be standardised.

Applications

Applications allow the end user to utilize the system in a useful manner. Depending on the kind of system it could consist of Personal Information Management kind of applications (in a PDA) like Address book, Calendar, Notes, Calculator, Convertor and so on. Or in case of a Internet Access Devices it would be the Internet access clients namely the Browser and Messaging services like the Email client and Chat. The Browser will allow the end user to access the World Wide Web. This will allow the user to access the rich set of Information and Services available on the net. Where as the email client will allow the user to communicate with others on the net. Chatting will allow people to interact with one another on the net in realtime.

The SYSTEM

 
                       |------------------------|
                       |      Applications      |     
                       |-----------||-----------|
                                   ||
                                   ||
  |-----------|     |--------------WW---------------|   
  |          C-------D         Libraries            |
  |  GUI      |     |-------------MM----------------|
  |           |                   ||                         User level
__|  System   |___________________||___________________________________
  |           |                   ||
  |------M----|                   ||
         .             |----------WW------------|
         .             | System Call Interface  |
         .    |----------------------------------------|  
         .    |                                        |
         .    |       Linux Kernel with SubSystems     |   
         .    |                                        |
         .    |----------------|                       |
         .    | Device Drivers |                       |
         .    |                |                       |
         .    |    |------------------------------|    |  
         .    |    |   Hardware Abstraction Layer |    |   
         .    |-------------------MM-------------------|
         .                        ||                        Kernel level
_________.________________________||____________________________________
         .                        ||
         .                        ||                        Hardware level 
       |-W------------------------WW--------------------------|  
       |                    Hardware                          |   
       |------------------------------------------------------|

Figure 1: The System

A well-designed computer system is made up of a layered architecture of software modules running on top of the underlying hardware providing different levels of abstractions to different entities of the system.

The typical layers in such a system consist of

  1. Hardware Abstraction Layer
    This layer allows the rest of the system to work in a portable manner with out worrying about the differences that can exist in different Computer systems.
  2. Kernel
    It manages the resources available in the system and allows effective and efficient utilization of it across competing processes. This abstracts the resources of the system as far as the User processes are concerned. Kernel exports its services to the user processes through some standard programming interface mechanism.
  3. Library
    Commonly used or required functionality is packaged into modules called the Libraries. It allows for efficient conservation of the storage available. It also simplifies the process of bug fixing and enhancing the services provided by the library across versions without affecting the applications that use it.
  4. Applications
    These are the entities in the system, which interact with the users and allow them to get some specific and or useful job done from the system. They in turn could be background daemons or foreground console or GUI applications.

Chapter 2

The LINUX System

Posix compliant Unix like OS.

Linux is a open source Unix like OS, which strives to be Posix compliant. Its simple, modular and configurable nature makes it suitable for Embedded Systems at one end to Servers at the other.

Linux is also portable and extensible, thus people have already ported it to different boards belonging to different architectures like x86, ppc, arm, mips, alpha, sparc,..

KEY MODULES
HAL and Subsystems
Drivers
System library

Here we will be looking into the Linux system in terms of its Kernel core, the subsystems, drivers and the system interface library.

When programming for Linux, one has to look at it from two different aspects. One is that of the Kernel space programming this is where the Kernel Core, the subsystems and drivers come into picture. The other is the User land programming and this is where the System Interface library comes into picture.

The Linux kernel



         |---------------------------------------------------|
         |                L i b r a r i e s                  |
         |--------------------------M------------------------|
                                    |                         User Level
 ...................................|....................................
                                    |
                                    |
         |--------------------------W------------------------|
         |              System Call Interface                |
         |--------M--------------------------------M---------|
                  |                                |
                  |                                |
                  |                                |
      |-----------W--------------|     |-----------W-------------|
      |        V  F  S           |     |                         |
      |                          |     |  Process Management     |
      |        |---------------| |     |       System            |
      |        |File Sub system| |     |         ................|
      |        |---------------| |     |         . Inter Process |
      |                          |     |         . Communication |
      |--------------------------C-----D         ................|
      |           |    BLOCK     |     |         . Memory        |
      | CHARACTER |--------------|     |         .    Management |
      |           | Buffer Cache |     |         ................|
      |           |--------------|     |         .               |
      |           |  Low Level   |     |         .   Schedular   |
      |           |       Logic  |     |         .               |
      |--------------------------|     |-----M-------------M-----|
                  |                          |             |
                  |                          |             |
                  |                          |             |
          |-------W--------------------------W----------|  |
          |      Subsystems                             |  |
          |                |-------------------------------W--|
          |                |    Hardware Abstraction Layer    |
          |                |                                  |
          |------M---------|------------------MM--------------|
                 |                            ||            Kernel Level
 ................|............................||.........................
                 |                            ||          Hardware Level
        |--------W----------------------------WW---------|
        |                Hardware                        |
        |------------------------------------------------|

Figure 2: The Linux kernel

The Linux kernel is what I would like to call a Macro kernel. The kernel image consists of the kernel-core, subsystems and the drivers as a single entity from hardware perspective during runtime as in a Monolithic kernel. However it's a Modular kernel in that these subsystems and drivers can be written as modules, which can be loaded and unloaded dynamically in a running system. Also its contents and functionality can be selectively exported to other modules or the system. These features give it most of the advantages of a Micro kernel at the same time not having the overhead of Message passing across different Context levels as found in the tasks forming the Micro kernel, as the Modules act as a Monolith entity once they are loaded into the kernel.

This in turn means that the conventions specified for accessing or managing resources should be followed properly or else the stability of the system can be compromised by flaky kernel space code.

The Linux kernel is non pre-emptive in the kernel space. Well how ever this is not a problem as

  1. Interrupts and their handlers still work.
  2. All well behaving kernel code are co-operative, in that when ever they have to wait for anything, they give back control so that the system can continue with other things in the mean while.

The Modular nature of Linux allows one to add or remove drivers in a running system without rebooting. It also allows new drivers or subsystems to be added to a running system.

The drivers in Linux can be categorized into 3 main groups namely Char, Block and Network drivers. Based on the functionality provided by Kernel, the functioning of the device and ones requirements one has to write driver for the corresponding subsystem in the kernel. There are also other models for programming drivers related to specific devices like say sound.

When porting Linux to a new system/target we will be mainly dealing with the HAL layer of Linux and also adding some new drivers for Linux. Next we will be creating a new mini linux distribution consisting of the required libraries, applications and their resources.

The HAL of Linux takes care of issues like

  1. Task Context and switching
  2. Memory management unit
  3. I/O subsystem
  4. Interrupt subsystem
  5. Inter process communication
  6. Timer, DMA, UI devices, ...

A lot of these areas will be touched upon when the system boots. So we shall look into the typical Linux boot process first. Later we will be looking into some of these other areas like Task switching, MMU logic, I/O, Interrupts, drivers and so on.

Linux Boot process


                                    |-------------------------------------|
                                    | Compressed/Relocatable Kernel Image |
                                    |-------|||---------------------------|
                                            |||
  |-----------------------------------------WWW------|
  |      Kernel Boot Strap (assembly) start          |
  |--------------------------------------------------|
  |               [arch/boot/xyz..]                  |
  |  1 Setup and Clear BSS                           |
  |  2 Minimal Page Table and Cache initialization   |
  |  3 Inflate and Relocate the kernel if required   |
  |  4 Clean, Flush and Switch off cache             |
  |  5 Jump to kernel (_stext)                       |
  |                                                  |  
  |-----------------||-------------------------------|
                    ||
                    ||              |---------------------|
                    ||              | Normal Kernel Image |
                    ||              |-------|||-----------|
                    ||                      |||
  |-----------------WW----------------------WWW------|
  |  Pre Kernel Initialization (assembly) _stext     |
  |--------------------------------------------------|
  |            [arch/kernel/head.s ++]               |
  |  1 Verify Processor and Architecture types       |
  |  2 Initialize arcitecture if any                 |
  |  3 Setup Initial Page-Table                      |
  |  4 Setup/initialize any debug related minimal    |
  |    device                                        |
  |  5 Clear BSS and setup Stack                     |
  |  6 Jump to start_kernel                          |
  |                                                  |  
  |-----------------||-------------------------------|
                    ||
                    ||                         
  |-----------------WW-------------------------------|
  |   In Kernel Initialization (C) start_kernel      |
  |--------------------------------------------------|
  |            [init/main.c]                         |
  |  1 Announce Linux                                |
  |  2 Architecture specific setup and               |
  |    Process command-line                          |
  |  3 CPU Subsystem setup                           |
  |  4 Memory management setup                       |
  |  5 Process management setup                      |
  |  6 Allocate Buffers/Memory                       |
  |  7 Start Init - the kernel thread                |
  |  8 Do CPU Idle                                   |
  |                                                  |  
  |-----------------||-------------------------------|
                    ||
                    ||                         
  |-----------------WW-------------------------------|
  | In Kernel Initialization (C) Init - KernelThread |
  |--------------------------------------------------|
  |            [init/main.c]                         |
  |  1 Architecture specific Fixups                  |
  |  2 Bus and Device setup                          |
  |  3 Make initcall s (for all subsystems)          |
  |  4 Multistage Root file-system mounting          |
  |  5 Free initialization related memory            |
  |  6 Transform to user_space_Init process          |
  |                                                  |  
  |--------------------------------------------------|

Figure 3: The Linux Boot process

The Linux boot process can be roughly broken down into 3 parts they are the

  1. Kernel bootstrapping
  2. Pre Kernel Initialization
  3. In Kernel Initialization

Depending on the Architecture and the available firmware support and working environment the kernel bootstrapping process could be almost non-existent to consist of kernel and initrd (initial ramdisk) inflating and relocation. Next it passes control to the Pre Kernel initialization part which is mainly written in assembly language of the given processor architecture.

Once the control has been passed to the Pre Kernel initialization part of the kernel. It starts by doing any minimal architecture specific initialization (interrupts are disabled for one) and maybe even setup minimal exception handlers, followed by setting up of the initial page table. Next it initializes any available debugging aids and jumps to the architecture independent start_kernel routine, which is in C language.

The Kernel proper starts by asking an architecture specific routine to do any setup specifically required for that architecture, as well as asking it to get the command line and other parameters passed to it by the boot strap loader logic if any. Next the Command line arguments are put into proper environment variables for other parts of the kernel to access it. Next Exception or Trap handlers are setup, followed by setup of the Interrupt subsystem. The Scheduler is setup and the System timer is initialized. Also the console logic is initialized so that the kernel can communicate to the user. The Module mechanism of the kernel gets setup next. Setting up of the Cache and Memory Management logic follows this. The proc filesystem, which allows kernel to communicate with the user space in a structured manner, is activated. Also any of the modern day kernels use lot of buffering strategies for different mechanisms to increase the efficiency in the system, so does the Linux kernel, so any buffers or caches required are setup and allocated next. Signals and Inter-process Communication is setup to allow processes to communicate and synchronize with one another. The init kernel thread is started and the kernel goes to the cpu_idle loop.

The init kernel thread gets scheduled next. At this moment in time the system is in a stable state and the basic systems like CPU, Memory and Process management are up and running. The thread starts by doing any architecture specific fix-ups. Setting up the Bus systems if any and then the Devices, which are attached to these busses, is achieved. One of the key advantages of the Linux kernel is a standards compliant Networking stack. The next job of the Init kernel thread is to start the Networking subsystem. The different systems within the kernel are initialized next by going thro the list of initialization routines in the initialization specific section of the kernel image. The code is setup; using linker related commands, such that the initialization routines of the different systems within the kernel fall into this Initialization specific section. This also takes care of loading the Initial ram disk (initrd) (or is it or maybe some part of this is occuring as part of the setup_arch call in start_kernel). This is a very important file-system in embedded systems, where secondary storage based file-systems are usually lacking. The linuxrc script/executable within the root directory of the initrd system is executed next. In a embedded system this in itself could be the end of the boot process. However if organized differently (or also in a normal system), the actual root file-system is mounted next and the system designer is given a chance to retain the already mounted initrd file-system. All the initialization related memory (both data and function) is freed up to conserve the precious little memory. This is easily achieved as all initialization related contents are bundled into special sections in the kernel image. An interesting part of the code runs next in that the init kernel thread Starts up the console and then transforms itself into a User space process by execve-ing the init application, which should be located in a suitable place in the real root file-system.

Context Switch logic

Context switching is a key and frequently utilized feature of any Multiprogramming OS. It allows the kernel to save the context of the currently running process and replace it with the previously saved context of the next process to run. This logic in turn is usually triggered by the Scheduler, which in turn decides the scheduling algorithms to use in order to provide the required process running behavior. In Linux the context switching logic is part of HAL and Scheduler is part of the Platform independent code.

The context switch logic in the HAL is implemented using the switch_to macro. Its job is to save general-purpose and special-purpose registers. In case of special-purpose registers they are saved and restored only if required, this is especially true for registers like the fpu registers and the debug registers.

MMU subsystem

The MMU is a very essential part of any OS today. It provides many advantages like

  1. Protection of code and data belonging to one application from another applications. Thus even if one program / process misbehaves only it will be killed and other processes can continue executing.
  2. Allow multiple processes to run even if the total available memory in the system is not able to satisfy the memory requirements of all the processes in the system at any given point of time. This is achieved by maintaining only the currently accessed part of the processes in Memory. And the other parts of the system are swapped in and out as required to utilize the available main memory efficiently.
  3. As the processes will be able to access memory only through the virtual address space, a process can be provided a large contiguous virtual memory space even thou internally it could be non-contiguous in the physical memory chips.
  4. Code can be transparently relocated to different areas in the physical memory space by updating the virtual to physical mapping suitably.

Linux being a multiprogramming/multi-user OS, utilizes the MMU to achieve the above stated goals. As Linux is designed to be portable in the newer versions, the hardware dependant parts of the MMU logic are isolated into the HAL of Linux. The following are some of the key requirements to be satisfied by the MMU module of HAL in Linux.

IO subsystem

The I/O subsystem which is part of the HAL of Linux allows device drivers to access control and data space of the devices in a architecture neutral form, without having to worry about whether its i/o mapped or memory mapped, or whether caching issues have to be taken care or not and so.

First of all one is required to get the address space of the device recognized by the system this is where the routines ioremap[_nocache] and iounmap come into picture.

Once the required address space has been mapped one is normally required to read and write on this space. This is where routines like read[byte/word/long] and write[byte/word/long] are used. Also functions like memset_io, memcp_toio, memcp_fromio are used when working on a chunk of address space at a time.

If working on I/O mapped devices

Also issues like Cache coherency and DMA, I/O operations on certain busses like ISA and other quirks require to be handled here.

Interrupt Subsystem

Linux has a controller-independent x86 interrupt architecture. Every controller has a 'controller- template' that is used by the main code to do the right thing. Each driver-visible interrupt source is transparently wired to the appropriate controller. Thus drivers need not be aware of the interrupt-controller.

The code and the controller-template are designed to be easily extended with new/different interrupt controllers, without having to do assembly magic. This controller-template forms part of the HAL in Linux.

The controller-template is specified by struct hw_interrupt_type. It consists of

HAL (Misc.)

Timer

Timer is an important component as it is the heart beat of the system. It gives a mechanism for all modern day OS's to periodically get control from the user process and see if any new process requires to be scheduled into the system, thus achieving Preemption. It also helps keep the time_of_day up to date.

The Timer Chip related functions belong to the HAL of Linux. As part of this one is required to implement time_init function, which is called during booting. It is supposed to initialize the timer chip to a known state and setup the system timer appropriately and associate the timer_interrupt-handler for it. In many cases the default timer_interrupt logic could be enough. However if some additional work is required related to the target then a new-timer_interrupt-handler should be defined which in turn calls the default-timer_interrupt-handler.

The other key functions that one may require to implement are do_gettimeofday and do_settimeofday. These are used by the system when one requires querying or setting of the wall or calender-time.

DMA

DMA is required to allow data transfer between the device and memory without the intervention of the CPU. Thus the available resources in the system can be utilized efficiently by doing things in parallel.

The DMA functionality is abstracted as part of the HAL in Linux. So the module, which uses DMA, doesn't have to worry about the differences in the DMA Controller.

The functions that require to be implemented as part of the HAL are

Keyboard Controller

Setup Interrupt_Handler or Polling mechanism (using Timers) as part of the keyboard controller initialization routine so that any keypress or keyrelease event can be recoginized by the kernel. Routines triggered by them inturn look into the got row and column status or other code and convert it suitably as required to the kernel specified scancode using tables. This scancode is inturn along with the key Up/Down status is passed to the Platform independant handle_scancode routine.

Char devices

Char devices is one of the most flexible driver related interface available in Linux. It allows for arbitrary length of data transfer during I/O. Also kernel doesn't provide any buffering for this class of drivers, thus whatever I/O that occurs in these drivers directly affects the underlying hardware immediately.

The char driver interface allows the hardware device to be abstracted as a File as far as the user applications are concerned. This in turn would mean that one can use common functions like open, read, write, close on these devices.

Common Device interface functions for this class of devices are

BLOCK devices

Block device class of drivers in Linux is usually used for storage kind of devices. The kernel provides support for Buffered I/O on this class of devices. Also the driver doesn't have to worry about varying I/O data sizes, as the kernel translates them to a series of fixed block size transfers.

Even block devices are available to the user space through the usual file abstraction. However most of the file related I/O logic is implemented by the kernel so as to provide for Buffered I/O, Clustering of I/O requests for better efficiency when working with such devices. So the driver is only required to provide implementation for certain low-level device I/O operations.

Thus looking into the structure of a Block Device driver

Network Devices

Network devices are a class of device drivers, which don't use the device special file based user space naming/addressing of the devices. They use the concept of sockets to abstract the networking logic. However the Network device driver doesn't have to worry about all these issues, they work on packets - independent of protocol contained in these packets.

To implement a network device driver one is got to fill the net_device structure first. It mainly contains things like

Init, which is called when the driver is loaded, make calls to init_etherdev or ether_setup as required to initialise the net_device structure with suitable defaults. Next it calls register_netdev to register its services with the kernel. Finally when the driver is no longer required Un-Init is called to unregister_netdev.

Hard-Header & Rebuild-Header are called before packets are sent out, if one requires to set-up the headers in any special way or get destination mac address using any proprietary mechanism or so. Normally this job is left to the default handlers provided by the kernel.

hardware_start_transmit, tx_timeout

do_ioctl, set_multicast_list, get_stats

Interrupt-Handler as usual is a important entity of the driver. It is required to identify and process the Reasons associated with the current interrupt. If the interrupt is related to a receive event it normally triggers the NET_BH related bottom-half handler.

Bottom-Half (part of interrupt-handler if no BH) is required to trigger DMA operation if there is Data in the Device-Receive-Buffer. However if the BH was triggered related to the Receive-DMA-Over event then it is required to pass the just received packet to the higher layers of the network stack by calling netif_rx.

The User layer













Figure 4: The Applications