Memory management unit(MMU)

Memory Management

This is quite possibly the most important part of any Kernel. And rightfully so--all programs and data require it. As you know, in the Kernel, because we are still in Supervisor Mode (Ring 0), We have direct access to every byte in memory. This is very powerful, but also produces problems, espically in a multitasking evirement, where multiple programs and data require memory.

One of the primary problems we have to solve is: What do we do when we run out of memory?

Another problem is fragmentation. It is not always possible to load a file or program into a sequencal area of memory. For an example, lets say we have 2 programs loaded. One at 0x0, the other at 0x900. Both of these programs requested to load files, so we load the data files:

Notice what is happening here. There is alot of unused memory between all of these programs and files. Okay...What happens if we add a bigger file that is unable to fit in the above? This is when big problems arise with the current scheme. We cannot directly manipulate memory in any specific way, as it will currupt the currently executing programs and loaded files.

Then there is the problems of where each program is loaded at. Each program will be required to be Position Indipendent or provide relocation Tables. Without this, we will not know what base address the program is supposed to be loaded at.

Lets look at these deeper. Remember the ORG directive? This directive sets the location where your program is expected to load from. By loading the program at a different location, the program will refrence incorrect addresses, and will crash. We can easily test this theory. Right now, Stage2 expects to be loaded at 0x500. However, if we load it at 0x400 within Stage1 (While keeping the ORG 0x500 within Stage2), a triple fault will accure.

This adds on two new problems. How do we know where to load a program at? Coinsidering all we have is a binary image, we cannot know. However, if we make it standard that all programs begin at the same address--lets say, 0x0, then we can know. This would work--but is impossible to impliment if we plan to support multitasking. However, if we give each program there own memory space, that virtually begins at 0x0, this will work. After all, from each programs' perspective, they are all loaded at the same base address--even if they are different in the real (physical) memory.

What we need is some way to abstract the physical memory. Lets look closer.

Virtual Address Space (VAS)

A Virtual Address Space is a Program's Address Space. One needs to take note that this does not have to do with System Memory. The idea is so that each program has their own independent address space. This insures one program cannot access another program, because they are using a different address space.

Because VAS is Virtual and not directly used with the physical memory, it allows the use of other sources, such as disk drives, as if it was memory. That is, It allows us to use more memory then what is physically installed in the system.

This fixes the "Not enough memory" problem.

Also, as each program uses its own VAS, we can have each program always begin at base 0x0000:0000. This solves the relocation problems discussed ealier, as well as memory fragmentation--as we no longer need to worry about allocating continous physical blocks of memory for each program.

Virtual Addresses are mapped by the Kernel trough the MMU. More on this a little later.

Virtual Memory: Abstract

Virtual Memory is a special Memory Addressing Scheme implimented by both the hardware and software. It allows non contigous memory to act as if it was contigius memory.

Virtual Memory is based off the Virtual Address Space concepts. It provides every program its own Virtual Address Space, allowing memory protection, and decreasing memory fragmentation.

Virtual Memory also provides a way to indirectly use more memory then we actually have within the system. One common way of approching this is by using Page files, stored on a hard drive.

Virtual Memory needs to be mapped through a hardware device controller in order to work, as it is handled at the hardware level. This is normally done through the MMU, which we will look at later.

For an example of seeing virtual memory in use, lets look at it in action:

Notice what is going on here. Each memory block within the Virtual Addresses are linear. Each Memory Block is mapped to either it's location within the real physical RAM, or another device, such as a hard disk. The blocks are swapped between these devices as an as needed bases. This might seem slow, but it is very fast thanks to the MMU.

Remember: Each program will have its own Virtual Address Space--shown above. Because each address space is linear, and begins from 0x0000:00000, this immiedately fixes alot of the problems relating to memory fragmentation and program relocation issues.

Also, because Virtual Memory uses different devices in using memory blocks, it can easily manage more then the amount of memory within the system. i.e., If there is no more system memory, we can allocate blocks on the hard drive instead. If we run out of memory, we can either increase this page file on an as needed bases, or display a warning/error message,

Each memory "Block" is known as a Page, which is useually 4096 bytes in size.

Once again, we will cover everything in much detail later.

Memory Management Unit (MMU): Abstract

The MMU, Also known as Paged Memory Management Unit (PMMU) is a component inside the microprocessor responsible for the management of the memory requested by the CPU. It has a number of responsibilities, includingTranslating Virtual Addresses to Physical Addresses, Memory Protection, Cache Control, and more.

Segmentation: Abstract

Segmentation is a method of Memory Protection. In Segmentation, we only allocate a certain address space from the currently running program. This is done through the hardware registers.

Segmentation is one of the most widly used memory protection scheme. On the x86, it is useually handled by the segment registers: CS, SS, DS, and ES.

We have seen the use of this through Real Mode.

Paging: Abstract

THIS will be important to us. Paging is the process of managing program access to the virtual memory pages that are not in RAM. We will cover this alot more later.

Linux basics kernel and bootloader

What is a bootloader

Bootloader is a piece of code that runs before any operating system is running.
Bootloader are used to boot other operating systems, usually each operating system has a set of bootloaders specific for it.
Bootloaders usually contain several ways to boot the OS kernel and also contain commands for debugging and/or modifying the kernel environment.
In this talk we will concentrate on Linux bootloaders.

Since it is usually the first software to run after powerup or reset, it is highly processor and board specific.

Processor and Board specific

• Bootloader starts before any other software starts therefore it is highly processor specific and board specific.
• The bootloader performs the necessary initializations to prepare the system for the Operating system.
• The operating System is more general and usually contains minimum board or processor specific code.

Usually starts from ROM (Flash)

When a CPU starts, it has certain preset values in its registers, it usually knows nothing about on board memory. It expetcs to find program code at a specific address, this address usually points to ROM or Flash, this is the beginning of bootloader code. First task of boot loader is usually map the RAM to predefined addresses. After RAM is mapped Stack pointer is setup.
This is the minimal setup required, after that the bootloader starts it's work.

Moves itself to RAM for actual work

We now have RAM and Stack pointer and ready to do the real work. First of all since Flash memory is usually scarce resource and much slower then RAM, we move the actual bootloader code to RAM for actual execution. In many cases Flash memory is located in an address space that is not executable, for example serial flash that you can access by reading repeatativly from one address. Also in many cases, the actual bootloader code is compressed so it must first be uncompressed and then written to RAM.

Minimum peripheral initialization

The bootloader needs to initialize peripherals needed for its operation, usually we need the screen the keyboard and optionaly the mouse. In embedded systems we need a terminal. Sometimes when we boot from network we need network connection so we have to initialize ethernet card.

These initializations are usually just for the bootloader.
The Operating System usually overrides them or not using them at all.

Decide which OS image to start

Bootloaders can usually load one of few kernel images that are known to the bootloader This can be done in embedded systems to make sure we can upgrade a kernel without fear of power loss during upgrade, since we always have a backup kernel that will load. In PC environments this is done to let the user choose among several OS's or give the user a chance to try another kernel without losing his/her current kernel.

Get the kernel

Bootloaders must load the kernel image from a known location
most bootloaders provide several ways to loade the kernel:

• Load kernel image from memory
• Load kernel image from file (If the system has a disk)
• Load kernel image from network using bootp
• Load kernel image to memory using TFTP

Allow manual intervention

In some cases we need manual intervention to specify parameters for the OS,
bootloaders usually have a way to interrupt automatic loading and insert parameters. This is done by waiting a certain default time before autoloading, during this time the user has to press a specific key (Esc in case of LILO) or any key in case of UBOOT. When a key is pressed, a prompt is displayed and the user has a chance to change certain environment variable or maybe load a different kernel from memory, disk, network etc.

PC boot sequence

PC's have a different boot sequence, first a ROM BIOS starts that give minimal configuration to peripherals, usually just configuring the screen and keyboard. It then looks in its tables (CMOS RAM) for a boot device.
From the specified boot device it loads to RAM the first stage (from MBR)
control is transferred to first stage.
First stage bootloader loads the second stage that usually displays the boot menu. The user selects the OS to boot or a default OS is booted after a speficied time. In this stage the user have the option to add boot parameters to kernel. In several cases, the bootloader does not know how to load the OS and transfers the control to another bootloader, this is called chain loading, this is usually done when LILO or GRUB needs to load windows.

Prepare parameters for OS loading

The OS is usually generic and is not specificly tied to one board implementation, so in order for the OS to work as expected, it needs some information about the memory map, clocks etc. These parameters can be compiled into the kernel but this make the kernel very board specific and makes it difficult to replace kernels in the future. Most kernels allow passing information by means of command line and/or in memory structure.

Loads OS Image

After the bootloadr knows what OS Image (Kernel) to load, it loads the Image to RAM This usually must be done to a specific address the specific address is either hard coded into the bootloader or is read from the kernel image file.
The bootloader needs to be able to read and understand the object format of the OS kernel. It will extract the actual memory image from the object file and place it to memory according to the header of the object format and then jump to the entry point (also given in the object header).

In case of Linux which uses MMU the base address is usually virtual address and the bootloader needs to translate it to physical address, this is why we usually can't load linux using a bootloader written for other OS's that don't use MMU such as vxWorks.

Load optional RAM file system (initrd)

In Linux the kernel needs a root file system to work, this root file system can be on a disk or in RAM disk. RAM disk (initrd) is frequently used in linux distributions to keep the kernel small and to load only a required set of modules to work with the hardware. The initial RAM disk is used as a root file system, the init process of the RAM disk, loads the needed modules and then mounts the other filesystems from disk. In embedded system, many times there is no disk at all so the RAM file system is used.

Transfer control to OS kernel in RAM

After all images are loaded into RAM, we can start the OS itself. Starting the OS usually means copying it to a certain location in RAM, filling a memory structure and then transfer control to the OS code. In this stage the bootloader role is done and thus the OS can use the RAM area where the bootloader is.

Starting Linux

Until now we concentrated on the bootloader itself and what we discussed in general for all operating system, now we will discuss specific features needed to boot linux. Linux was created as an operating system for desktop or server, it was later adopted for embedded system environments and is thus different from other Embedded operating systems.

Linux must have a file system, this makes programming an embedded linux application easier as it is similar to programming a desktop application, you simply compile your program to a file linked with the appropriate libraries and then run this file. In other embedded operating system you link your application with the kernel itself and thus you actually write a kernel application. However since Linux must have a file system and embedded systems usually does not even have a disk, we use a RAM disk image of the file system. This RAM disk image can be included in the Kernel image as another section in the object file or used as a seperate file. The bootloader must know how to handle it. It must extract the file system image and put it in a certain known RAM location before it trasfers control to the kernel.