Understanding Linux

Disk I/O Basics

2012-09-05T21:50:00.001+05:30

Seek Time:
Generally speaking, when the I/O request comes in for a particular piece of data, the head will not be above the correct track on the disk. The arm will need to move so that the head is directed over the correct track where it must then wait for the platter spin to present the target data beneath it. As the data could potentially be anywhere on the platter, the average seek time is time taken for the head to travel half way across the disk.

Latency (Rotational Latency):
Latency is the average time for the sector being accessed to rotate into position under a head, after a completed seek. It is easily calculated from the spindle speed, being the time for half a rotation.

Response Time = (Average Latency) + (Average Seek Time)

Disk Transfer Rates (Aka Sequential Read) :
how much data the drive could potentially deliver on a sequential read. Mainly dominated by the latency (ie rotational delay).

Let's assume the OS has directed the disk to perform a large sequential read operation. After the initial average overhead (seek + latency delay) to locate the start of the data, the actuator arm need now move only fractionally with each disk rotation to continue the read (assuming the data is contigious). The rate at which we can read data off the disk is now limited by the platter RPM and how much data the manufacturer can pack into each track.

Data per track on a 2.5 inch drive is ~1.43MB
Now a disk spinning at 7200RPM is actually spinning 120 times per second. Which means that the total amount of data which can pass under the head in 1 second is a massive 173MB (120 * 1.43MB).

Taking into account that perhaps about 87% of a track is data, this gives a maximum disk throughput of about 150MB/s.

Note that this calculation is best case -it assumes the data is being sequentially read from the outermost tracks of the disk and that there are no other delays between the head reading the data and the operating system which requested it. As we start populating the drive with data, the tracks get smaller and smaller as we work inwards (don't worry -we'll cover this in Zone Bit Recording below). This means less data per track as you work towards the centre of the platter, and therefore the less data passing under the head in any given time frame.

To see how bad the sequential read rate can get, let's perform the same calculation for the smallest track which has a 1 inch diameter. This gives a worst case sequential read rate of 60MB/s! So when your users report that their computers get progressively slower with time, they might not actually be imagining it. As the disk fills up, retrieving the data from the end of a 2.5inch drive will be 2.5 times slower than retrieving it from the start. For a 3.5 inch desktop harddisk the difference is 3.5 times.

Disk Operations per Second - IOP:

The problem with databases is that database I/O is unlikely to be sequential in nature. One query could ask for some data at the top of a table, and the next query could request data from 100,000 rows down. In fact, consecutive queries might even be for different databases.

If we were to look at the disk level whilst such queries are in action, what we'd see is the head zipping back and forth like mad -apparently moving at random as it tries ro read and write data in response to the incoming I/O requests.

In the database scenario, the time it takes for each small I/O request to be serviced is dominated by the time it takes the disk heads to travel to the target location and pick up the data. That is to say, the disk's reponse time will now dominate our performance. The response time now reflects the time our storage takes to service an I/O request when the request is random and small.

For seagate drive with RPM of 7200, seek time = 11ms. Avg latency = 4.17ms.
Response time = 11 + 4.17 = 15.17ms.
So, for the specific case of our Seagate Drive with a 15.17ms response time, it will take at least on average 15.17ms to service each I/O. Turning this on it's head to give us our IOPS yeilds (1/ 0.01517) which is 66 IOPS.

Typical IOPS values are:
Drive RPM       Avg Rotational Latency (ms)    Seek Time (ms)         IOPS                TransferRate
5400                       5.5                                     7 - 14.4                50 - 80                ~100MB/s
7200                       4.2                                    5.9 - 9.1                75 - 100              ~150MB/s
10,000                       3                                       3.6 - 5                  125 - 150             ~200MB/s
15,000                       2                                       2.7 - 3.7                175 - 200            ~300MB/s

Typical disk speeds are:
5400 RPM is standard for laptops
7200 RPM is the standard for PCs.
10000 RPM is a mid-range server.
15000 RPM is a high-end server.

Log Structured File System : An Introduction

2011-01-16T21:53:00.002+05:30

I am writing this post after a long gap. In this post I am trying to give a basic idea about the log structured file systems. I have oversimplified some of the stuff so as not to confuse you and keep the things as straight forward as possible.
In traditional file systems the data stored on the disk may not be contiguous and so the seek time is poor which degrades the performance. It is the seek time between various IO requests that dominates the performance. Also, buffer caches are sufficiently large these days and most of the reads can be served by the buffer cache. So, disk traffic is mostly dominated by writes and disk seek time is the major reason that impacts the performance.
Log structured try to solve this problem by writing all modifications contiguously on the disk in a log-like structure.
LFS first buffers all updates in memory into a segment (typically MB in size). When the segment is full, it is written to the disk in one long sequential write to the unused part of disk.
LFS never overwrites the data. The modified data blocks and inodes are written to the new segment. So, we have the old and new copies of the inodes and data blocks spread in different logs and we need to keep track of the latest inodes/data-blocks.
Lets take a simple example to see what happens when a block is added to a file
Here we need to allocate a new block and modify the inode to point to the newly allocated block. Initially the modification are done to the segment which is still in memory. Later, when the segment is full of such modifications it is written to the disk. Note, here there is no problem of finding free disk blocks. The free space in the log implies free blocks and can be allocated to a file. Both the modified inode and the new block are written on to the log.

Wait, we have a problem here. How do you find the location of new inode ?
How to find the location of new modified inode ?
On a traditions unix file system it is quite easy to find the location of an inode. The inode table lies at a fixed address on the disk. So, if we know the inode number and its size we can easily determine its location.
In LFS, the inodes are spread everywhere on the disk in various segments. Moreover there are multiple copies of the inodes (as we never overwrite in place). So, how to find which one is latest and its location in the segment ? The answer is inode map which keeps the disk address of all inodes.
inode map is an array that keeps the disk addresses of all the inodes. Imagine if there are one hundres thousand inodes what is the size of inode-map.
inode map size = 100000 * 4 = 400000 bytes = 390 KB.
So, inode maps are small enough and can be cached completely in memory. Every segment on disk has a copy of the inode map.
Now the question is where to put the inode map on disk?
inode map can be put on a fixed part of the disk. But, it is changed frequently and so whenever a segment is updated we would need to update the inode map. So there would be more disk seeks and performance may be impacted. Please note that we do not wait for the entire segment to be filled with modified inodes/data before the segment is synced to disk. In fact, the segments are updated partially and so for each partial write updating inode map may impact the performance. So, we keep the inode-map also on each segment.

Now how to find the inode-map ?
LFS keeps a fixed place on disk called checkpoint region (CR) that contains the address of the latest inode-map. The CR needs to be updated whenever we write a new segment. So, CR is required to be updated quite infrequently.

Note that each segment has pointer to the next segment and that is why the overall name of the file system is log structured file system.
By starting from the CR we can find the first segment written to the disk and traverse the chain to see what changes were made to the filesystem finally reaching the latest segment.
Reading files from a Log Structured File System
Lets assume that the system is just booted and there is nothing related to LFS in memory. The first thing that is read from the disk is CR (check point region) as this is the only region whose position is fixed. CR contains the pointer to the inode map. LFS then reads the entire inode map into the memory. To get the inode, LFS simply looks the cached copy of inode map and finds the inode number to inode disk address and thus reads the most recent version of inode. To find blocks of a file, rest of the operations are exactly the same like a traditional file system. Once LFS had read the latest copy of inode it can find out the disk addresses of the blocks that belong to this file and read them.
Garbage collection
Garbage collection is very important in LFS. As we have seen that LFS never overwrites any inode/disk-block. So, there are older versions of a file/blocks scattered all over the disk in various segments. LFS must periodically find out these old versions and clean/free them.
Periodically LFS reads the old segments and determine which blocks are live in this segment. Please note that any segment may contain few old and few latest versions of inodes/data-blocks. We will see how to determine if a particular inod/data-block is latest. Lets assume that we somehow know which inodes/blocks are latest. The cleaner process then writes only the latest/live blocks to a new segment and frees the old segment. So cleaner will read M old segments and compact them to N new segments (where M > N). This results in freeing of (M – N) segments and thereby creating more free space.
How to determine which inodes/data blocks in a segment are live/latest-version ?
How to find if a inode is live or not?
Fisrt determine the inode number. For this every segment has a segment summary that also keeps information about which inodes are stored in this segment. Looking at the segment summary we can find the inode number and its disk address (say D)
Now, we have the latest inode map cached in the memory. So, we can always find out the disk address of the latest version (L) of an inode. Then we can compare if the inode address in the segment (D) matches with the address of the latest version (L) in inode-map. If they both are equal that means the inode is live.
How to find if a data block is live ?
For this the segment summary block in the segment keeps some information for each data block. LFS includes the inode number and its offset in the file.
Given this information it is easy to determine if the block is live or not. LFS notes the inode number of block D and offset O from the segment summary and then looks in the latest inode map (cached in memory) to find the disk address of the corresponding inode and reads the inode from the disk. It then finds the disk address of the block at offset O in the file. If the disk address in the inode matches with the disk address of block in the segment, the block is live.
LFS also keeps the version number of a file. Whenever a new file is created LFS increases its version number. Thus looking at the version number LFS can save the longer checks to determine the liveliness of an inode/disk-block.
More on this later. Lots of things have been oversimplified for the sake of clarity. I will go into more details in later posts. Till then Have Fun !!!
And yes if you have any comments positive/negative please feel free to post.

Exceptions and Interrupts on x86 family of processors (Part 1)

2010-06-02T21:38:00.013+05:30

Interrupts and exceptions are special kinds of control transfer; they alter the normal program flow to handle external events or to report errors or exceptional conditions.

The difference between interrupts and exceptions is that interrupts are used to handle events external to the processor, but exceptions handle conditions detected by the processor itself while executing instructions (like divide by 0, invalid opcode, floating point exception etc).

Identifying an interrupt/exception
Intel processor associates an identifying number (ranging from 0 to 255) with each different type of interrupt or exception. Intel calls this identifying number a vector.

Interrupt and Exception numbers on x86 processors

Vector Number Description

0 Divide by Zero

1 Debug exceptions

2 Nonmaskable interrupt

3 Breakpoint (one-byte INT 3 instruction)

4 Overflow (INTO instruction)

5 Bounds check (BOUND instruction)

6 Invalid opcode

7 Coprocessor not available

8 Double fault

9 Reserved

10 Invalid TSS

11 Segment not present

12 Stack exception

13 General protection

14 Page fault

15 Reserved

16 Coprocessor error

17-31 Reserved

32-255 Available for external interrupts via

INTR pin

The vectors of nonmaskable interrupt and exceptions are fixed.

IRQs and external interrupts
The external devices like scsi disks, sound cards, network cards etc may be assigned any vector in the range 32 – 228.

Linux uses vector 28 (0x80) to implement system calls.

The IBM compatible PC architecture requires that some devices should be allocated particular fixed vector number as shown in following table.

IRQ	INT	Hardware device
0	32	Timer
1	33	Keyboard
2	34	PIC cascading
3	35	Second serial port
4	36	First serial port
6	38	Floppy disk
8	40	System clock
10	42	Network card
11	43	USB port, sound card
12	44	PS/2 mouse
13	45	Mathematical coprocessor
14	46	EIDE disk controller's first chain
15	47	EIDE disk controller's second chain

Interrupt vectors as used by Linux on an x86 processor

Vector Range	Use
0 – 16	Nonmaskable interrupts and exceptions
17 - 31	Intel-reserved
32 - 127	Maskable External interrupts (IRQs)
128 (0x80)	Software interrupt for system calls (int 0x80)
129 - 238	External interrupts (IRQs)
239	Local APIC timer interrupt
240	Local APIC thermal interrupt
241 - 250	Reserved by Linux for future use
251 – 253	Interprocessor interrupts
254 (0xfe)	Local APIC error interrupt (generated when the local APIC detects an erroneous condition)
255 (0xff)	Local APIC spurious interrupt (generated if the CPU masks an interrupt while the hardware device raises it)

Enabling and Disabling Interrupts on intel x86 processor
The external interrupts that are signaled via the INTR pin of the processor can be enabled/disabled by the IF bit of flag register.

When IF=0, INTR interrupts are inhibited.

When IF=1, INTR interrupts are enabled.

The instructions CLI and STI alter the setting of IF.

CLI (Clear Interrupt-Enable Flag) and STI (Set Interrupt-Enable Flag) explicitly alter IF (bit 9 in the flag register).

These instructions may be executed only by the linux kernel code that runs at a higher privilege level as compared to the user program. The user process cannot enable/disable the interrupts.

Programmable Interrupt Controller (PIC 82596)Each hardware device (like keyboard, sound card, hard disk etc) capable of issuing an interrupt request has an output line known as IRQ line. These IRQ lines are connected to the input pins of programmable interrupt controller (PIC 82596).

The IRQ lines are sequentially numbered from 0. The vector numbers for external interrupts start from 32. So, the PIC should be programmed in a way that it generates the vector number 32 when the hardware device connected to IRQ0 generates an interrupt.

So, IRQ0 is associated with vector number 32.

IRQN is associated with vector number 32 + N

Each IRQ can be selectively disabled. The PIC can be programmed to disable IRQ. The disabled interrupts are not lost and are issued to the CPU as soon as they are enabled again.

Typically on a PC, the PICs are implemented by connecting them in cascade as shown in figure above. Each 82596 chip can handle up to 8 IRQ input lines.

The INT output of slave PIC is connected to the IRQ 2 of the master PIC as is used for cascading. So, only 15 IRQ lines are available to the external devices.

The 8 IRQ lines are first passed through the IMR (Interrupt Mask Register) to see if they are masked or not. If a particular interrupt is masked then it is not processed further. If it is not masked it will register its request with the Interrupt Request Register (IRR) by setting the corresponding bit in it. The priority resolver then selects the highest priority interrupt and set the corresponding bit in the ISR register.

Sequence of events in handling an interrupt request
1) One or more IRQ lines (IRQ0 to IRQ15) are raised high by the external device connected to these lines. This results in setting the corresponding bits in IRR (Interrupt Request Register).

2) The chip 82596 sends INT to CPU (ie INT line on the processor is asserted)

3) CPU acknowledges the INT and responds with INTA pulse

4) Upon receiving INTA from CPU, the highest priority bit from IRR is selected and the corresponding bit in ISR (Interrupt Service Register) is set. The selected bit in IRR is reset.

The ISR bit shows which IRQ is being currently served.

The corresponding bit in IRR is reset as it is no longer requesting service but actually getting service.

5) CPU then initiates a second INTA pulse to tell the PIC to place the 8 bit IRQ number on the the data bus (corresponding the vector number of IRQ being serviced).

6) CPU then reads the data bus to find out the interrupt vector number to call the associated Interrupt handler code.

7) Once the interrupt handler (ISR) is done, it sends an EOI (End of Interrupt) to the PIC. The PIC will then determine the next highest priority interrupt and repeat the same process.

This is all for today. In the next article we will see how interrupts are handled by linux kernel and discuss in more details about them.

Till then, Have Fun !!!

Data Structure Alignment and Padding

2010-05-31T23:47:00.008+05:30

You must have heard that the fundamental data types must be aligned to a specific byte boundary. Most of you must have seen your programs being killed due to alignment exception generated by the processor. For any C programmer it is very important to understand the reasons behind the alignment restrictions.
In this article we will see why the compiler align certain data types to a certain boundary.

Why alignment restrictions ?
Typically a 32 bit processor reads or writes from the memory in chunks of 4 bytes (32 bits). The reads and writes can be performed at addresses that are divisible by 4.
Even if you want to read a single byte, 4 bytes are read from the memory and then the processor hardware circuitry will copy the requested byte to the specific position in the register.
For example, on m68K processor, a multiplexer sits in between an internal register and the external bus. The multiplexer selects the specified byte and routes it to the appropriate byte position in the register.

Lets try to see why processor restricts the data to be aligned to a specific byte boundary. Suppose the processor needs to read an integer (4 bytes in size).

Case 1: Integer is stored at address that is 4 byte aligned (say 0x100)

As the processor can read/write only at addresses that are divisible by 4, all four bytes can be read in a single bus cycle. Note that the address 0x100 is divisible by 4.

Address	Byte 0	Byte 1	Byte 2	Byte 3
0x100	X0	X1	X2	X3

Case 2: Integer is stored at an unaligned address (say 0x101)

This read cannot be performed in a single 32 bit bus cycle. The processor will have to issue two different reads at addresses 0x100 and 0x104.

Thus, it takes twice the time to read a misaligned data.

Address	Byte 0	Byte 1	Byte 2	Byte 3
0x100		X0	X1	X2
0x104	X3

It is important to note that

· Some processors allow unaligned access but at a performance penalty as we saw above. Total time to read a misaligned data is more/double as compared to the aligned data Intel processor allow reading/writing data which is unaligned but at the cost of reduced performance.

· Some processors generate an alignment exception on accessing a misaligned data. Then it is up to the exception handler either to report an error (kill the user process) or perform two read cycles to read the misaligned data (user process will run normally in this case but at reduced performance).

C compiler allocates addresses such that the data types are properly aligned. This helps in speeding up the read/write operation without causing any exception.
Typically on a 32 bit processor (like 32 bit x86, m68k, PowerPC, ARM etc)

· A char (one byte) will be 1-byte aligned.

· A short (two bytes) will be 2-byte aligned.

· An int (four bytes) will be 4-byte aligned.

· Any pointer (four bytes) will be 4-byte aligned (e.g.: char *, int *)

Structure alignment and padding

Compiler add pad bytes in the user defined structures so that the various fields of a structure are properly aligned.

There are certain rules that can be kept in mind to understand padding in a structure.

1) No padding before the first element

The first element of a struct must come first, and must be preceded by no padding. This allows a struct pointer to be converted to a pointer to the struct's first element and vice versa, which is a useful property.

2) Pad bytes at the end of structure

It is obvious to add bytes in between the elements of a structure to keep the elements aligned. But why the compiler will put pad bytes at the end of a structure ?

This is because if an array of structure is declared, start of each structure should be properly aligned.

For an array of structure, struct A array[10],

ð array[1] should be equivalent to *(array + 1).

ð difference between array + 1 and array + 0, should exactly equal to the size of struct A

To satisfy above constraints, compiler may have to put padding bytes at the end of structure. The rule is that the last member inside a structure should be padded with the number of bytes to make the structure aligned to the size of largest member of structure.

Lets see few examples for structure alignment and padding

struct exampleStruct {

char data1;

short data2;

int data 3;

char data 4;

};

On a typical 32 bit processor (say m68k or PowerPC), the compiler will insert padding in between various members so that they are properly aligned.

struct exampleStruct {

char data1;

char padding[1]; // pad of 1 byte to keep short to be 2

// byte aligned

short data2;

int data3; // already aligned to 4 byte boundary,

// so no padding before this

char data4;

char padding[3]; // padding at the end of structure so

// that if an array of such structures is

// declared, the start of each structure

// in the array is properly aligned.

// Padding should be done such that

// start of structure address is aligned

// to the size of largest data member of

// structure. In this case, the size of

// largest data type (int data3) is 4.

// So, 3 pad bytes are added to the end.

};

How to arrange members so as to minimize padding?

By changing the ordering of members in a structure, it is possible to minimize the amount of padding. If members are sorted by ascending or descending aligment requirements, minimal amount of padding is required.

So, if you have a structure with multiple integer, short and char members, then keep all integer members at the beginning, keep all short members after interger members and all chars at the end.

How to prevent compiler from putting pad bytes in between or at the end of structure?

Compiler provides #pragma directives to specify the alignment of members inside a structure.

#pragma pack(push) // save original alignment on stack

#pragma pack(1) // set alignment to 1 byte boundary

struct packedStruct {

char data1;

int data2; // no padding is inserted,

// as alignment specified is 1 byte.

char data3;

};

#pragma pack(pop) // restore original alignment

Here, we tell the compiler that each element should be aligned to 1 byte boundary. So, no padding is inserted in between elements. The size of this structure aftre compilation will be 6 bytes.

Thats all for today.
Have Fun !!!

Dissecting FAT 16 File System

2010-05-19T19:39:00.007+05:30

In this article I will discuss about the internals of FAT16 file system, its layout and how the files and directories are stored in it. We will dissect the FAT file system by reading the important blocks and analyze their contents to get an understanding of how the fat16 file system works.

Sectors Vs Clusters
Data is written on disks in terms of sectors which are typically 512 bytes in size. You cannot read/write data less than sector size.
Cluster is a fixed number of contiguous sectors on disk. FAT file system allocate space to a file in terms of clusters and not sectors. If the cluster size is 8, it means that even if you write a single byte to a file, 8 contiguous sectors (ie 8 * 512 = 4096 bytes) will be allocated to the file.

Why FAT uses clusters instead of sectors ?
Like any file system FAT also needs to keep information about which sectors on disk are free and which are allocated to a file. FAT keeps a table, where it uses two bytes for each sector.
For efficiently reading/writing to a file, this table should be kept in memory. Smaller the size of table, more part of the table can be kept in memory. If instead of sector, cluster is used as a minimum allocation unit, the size of table will be reduced. If we use 8 sectors / cluster, the size of table will be reduces 8 times.

Larger File System
Also, larger disks can be handled using a larger cluster size. As FAT uses 2 bytes per cluster, total number of clusters that can be addressed are 0xFFFF (65535). Bigger the size of cluster, bigger the size of FAT file system that can be created.

Cluster size (Bytes) FAT16 File System Size

1024 (1K) 67MB = (65536 * 1024) Bytes

4096 (4K) 268 MB

8192 (8K) 536 MB

32768 (32K 2.14 GB

Better Performance
Another advantage of using a cluster is that if we have more contiguous blocks of sectors allocated to a file. This reduces the disk seek time and therefore improves file system performance.

Drawbacks (Internal Fragmentation)
The drawback of using a cluster is the internal fragmentation. If we need to write a single byte, the file system will allocate a cluster. If size of cluster is 8 sectors, we will end up allocating (8 * 512) = 4096 bytes, which means a lot of wastage of disk space. Since, most of the files are larger than sector size, the cluster concept works great.

FAT File System Layout on disk
A filesystem is created on a partition on the disk. A partition can be created using “fdisk” command.

As you see in the above diagram, essentially a FAT File System comprise of three sections.

· Boot Sector
· Primary And Secondary FAT Tables
· Data Clusters that contain the root directory and other files and directories.

Lets discuss FAT Table first
FAT table keeps information about which clusters in the data area are allocated to a file/directory and which are free.
It uses 2 bytes for each cluster.

FAT TABLE VALUE MEANING

0x0000 Cluster is free and not allocated to any

file/directory
0x0002 – 0xFFEF Used, Next cluster in file

0xFFF7 Bad Cluster

0xFFF8 – 0xFFFF Used, Last Cluster in file

The first two entries in the FAT Table are the special entries that are used to indicate the type of media and the dirty status of the file system.
The first entry stores the type of storage medium (0xF0 means removable and 0xF8 means non removable)
The second entry in the table indicates if the file system is dirty or not.
Suppose the file (Hello.txt) is allocated cluster number 3, then to find the next cluster allocated to this file go to third entry in the table which will have the next cluster number (which is 7) allocated. Then go to entry number 7 which has 0xFFFF as the next cluster number. 0xFFFF indicates end of file.
So, find all the clusters allocated to a file, we need to traverse the FAT table. That is why it will be more efficient to keep the entire FAT Table in the memory.

FAT 16 BOOT SECTOR
It is the first sector in the FAT file system
Contains information about the file system like Sectors per cluster, Number of FAT Tables, file system type (FAT 16/12/32) etc.

Bytes	Purpose
0-2	Assembly code instructions to jump to boot code (present in bootable partition)
3-10	OEM name in ASCII
11-12	Bytes per sector (512, 1024, 2048, or 4096)
13	Sectors per cluster (Must be a power of 2 and cluster size must be <=32 KB)
14-15	Size of reserved area, in sectors
16	Number of FAT Tables (usually 2, one primary and other backup)
17-18	Maximum number of files in the root directory
19-20	Number of sectors in the file system; if 2 Bytes are not large enough, set to 0 and use 4 Byte value in bytes 32-35 below
21	Media type (0xF0 = removable disk, 0xF8 = fixed disk)
22-23	Size of each FAT in sectors
24-25	Sectors per track in storage device
26-27	Number of heads in storage device
28-31	Number of sectors before the start partition
32-35	Number of sectors in the file system; this field will be 0 if the 2Byte field above (bytes 19-20) is non-zero
36	BIOS INT 13h (low level disk services) drive number
37	Not used
38	Extended boot signature to validate next three fields (0x29)
39-42	Volume serial number
43-53	Volume label, in ASCII
54-61	File system type level, in ASCII. (Generally "FAT", "FAT12", or "FAT16")
62-509	Not used
510-511	Signature value (0xaa55)

Lets print the BOOT SECTOR of FAT16 File System.
I created this FAT16 File System on 1GB disk. I used “dd” command to read the sectors from the partition.

Bytes Value Meaning

00-02: eb 3c 90 Instructions to jump to boot code

03-0a: 4d 53 44 4f 53 35 2e 30 Name string (MSDOS5.0)

0b-0c: 00 02 Bytes/sector (0x0200 = 512)

0d : 20 Sectors/cluster (0x20 = 32)

0e-0f: 02 00 Size of reserved area (2 sectors)

10 : 02 Number of FAT Tables (2) primary and secondary

11-12: 00 02 Max. number of root directory entries

(0x0200 = 512)

13-14: 00 00 Total number of sectors (0x0000)

2 Bytes are not large enough to

store the size of this fileSystem

15 : f8 Media type (non removable)

16-17: ff 00 FAT size (0x00ff = 255 sectors)

18-19: 20 00 Sectors/track (0x0020 = 32)

1a-1b: 80 00 Number of heads (0x0080 = 128)

1c-1f: 20 00 00 00 Number of sector before partition (0x20 = 32)

20-23: c3 dd 1f 00 Total number of sectors (0x001fddc3 ~ 1MB)

24 : 80 Drive number (80)

25 : 00 Unused

26 : 29 Extended boot signature

27-2a: fa 1e e7 34 Volume serial number

2b-35: 4e 4f 20 4e 41 4d 45 20 20 20 20 Volume label ("NO NAME ")

36-3d: 46 41 54 31 36 20 20 20 File system type label ("FAT16 ")

3e-1fd : [snip] Not used

1fe-1ff: 55 aa Signature value (0xaa55)

DATA AREA
Data area contains the root directoy and all other files and sub directories.
Root Directory store the directory entries for each file in the root directory. The most important data in each directory entry is the name of the file and the first cluster number of the file. If you the first cluster number then all other clusters that belong to this file can be found.
After the root directory, data belonging to all the files and the subdirectories is stored.

First lets have a look at the various fields of DIRECTORY ENTRY

VARIOUS FIELDS OF DIRECTORY ENTRY

Bytes Purpose

0 First character of file name Or allocation status

(0x00 = unallocated, 0xe5 = deleted)

1-10 Characters 2-11 of the file name

11 File Attributes

0x01 => Read Only

0x02 => Hidden File

0x04 => System File

0x08 => Volume Label

0x0f => Long File Name

0x10 => Directory

0x20 => Archive

12 Reserved

13 File Creation Time (in tenths of seconds)

14-15 Creation Time (Hours, minutes, seconds)

16-17 Creation date

18-19 Access Date

20-21 High order 2 Bytes of address of first cluster

(0 for FAT16)

22-23 Modified Time (hours, minutes, seconds)

24-25 Modified Date

26-27 Low order two bytes of address of first cluster

28-31 File size (0 for directories)

Lets do the dissection of a real FAT16 File System

I printed the boot sector of the FAT file system above that has the overall information about the entire file system. We will use this information to create the layout of the file system

No of sectors per cluster = 32
No of reserved sectors = 2
Number of FAT tables = 2 (one primary and one secondary)
Size of each FAT Table = 255 sectors
Size of single directory entry = 32 bytes
Max number of Root Directory Entries = 512
Size of root directory = 512 * 32 = 32 sectors = 1 cluster

So the LAYOUT of the file system is

Now lets analyze the contents of Root Directory and other files.
In my filesystem, I created following folders and files.

/folder1

/folder1/test3.txt

/folder2

/folder2/test4.txt

/test1.txt

/test2.txt

Lets print the root directory contents of my file system

Byte

Offset Directory Entry (32 Bytes)

-------------------------------------------------------

1000000 T E S T F A T 1 6 20 08 00 00 00 00

1000020 00 00 00 00 00 00 fd 00 b1 3c 00 00 00 00 00 00

First directory entry (32 bytes)

Volume Name = TEST FAT16

File Attribute = 08 = Volume Label
-------------------------------------------------------

1000040 e5 4e 00 65 00 77 00 20 00 46 00 0f 00 dd 6f 00

1000060 6c 00 64 00 65 00 72 00 00 00 00 00 ff ff ff ff

Second directory entry (32 bytes)

e5 = Deleted
-------------------------------------------------------

1000140 F O L D E R 1 10 00 4c 02 01

1000160 b1 3c b1 3c 00 00 03 01 b1 3c 02 00 00 00 00 00

Fourth Directory Entry

Directory Name = FOLDER1

Attribute = 10 = Directory

First Cluster Address = 0002
-------------------------------------------------------

(removed deleted/unallocated directory entries>

1000300 F O L D E R 2 10 00 91 07 01

1000320 b1 3c b1 3c 00 00 08 01 b1 3c 03 00 00 00 00 00

Directory Name = FOLDER2

Attribute = 10 = Directory

First cluster address = 0003
--------------------------------------------------------

1000500 T E S T 1 T X T 20 00 7e 0b 01

1000520 b1 3c b1 3c 00 00 22 01 b1 3c 04 00 b8 01 00 00

File Name = TEST1.TXT

Attributes = 20 = Archive

First Cluster address = 0004

--------------------------------------------------------

1000700 T E S T 2 T X T 20 00 7e 0b 01

1000720 b1 3c b1 3c 00 00 3a 01 b1 3c 05 00 2b 01 00 00

File Name = TEST2.TXT

Attribute = 20 = Archive

First cluster address = 0005

So, we saw that the root directory contains the directory entries of all folders and files that are created inside it. The directory entry contains the first sector containing the directory or file, so we can find all subdirectories and files inside it.
Lest look at FOLDER1. I created the file test3.txt inside FOLDER1
As per the directory entry of FOLDER1 (printed above) the first cluster number that contains the contents of FOLDER1 is 0x02.
We will print the contents of cluster no 2. Note that cluster numbering starts from 2. Cluster 2 lies just after the end of root directory.
Sector number corresponding to cluster 2 = 2 + 255 *2 + 32 = 544

CONTENTS OF FOLDER1 (cluster 2) Sector #544

1040000 2e 20 20 20 20 20 20 20 20 20 20 10 00 4c 02 01

1040020 b1 3c b1 3c 00 00 03 01 b1 3c 02 00 00 00 00 00

<snip>

1040240 T E S T 3 T X T 20 00 59 45 01

1040260 b1 3c b1 3c 00 00 54 01 b1 3c 06 00 f2 00 00 00

File Name = TEST3.TXT

Attributes = 0x20 (Archive)

First Cluster address = 0006

The first cluster that contains the file TEST3.TXT is 0x06.
I stored following contents in TEST3.TXT

# cat /folder1/test3.txt

CONTENTS oF TEST3.TXT CONTENTS oF TEST3.TXT CONTENTS oF TEST3.TXT CONTENTS oF TEST3.TXT CONTENTS oF TEST3.TXT CONTENTS oF TEST3.TXT CONTENTS oF TEST3.TXT CONTENTS oF TEST3.TXT CONTENTS oF TEST3.TXT CONTENTS oF TEST3.TXT CONTENTS oF TEST3.TX

Lets print the contents of cluster 6 to see if the contents match with the contents of file test3.txt

Cluster 6 correspond to sector number 2 + 255 * 2 + 32 + 32 * 4 = 672

1240000 C O N T E N T S o F T E S T

1240020 3 . T X T C O N T E N T S o

1240040 F T E S T 3 . T X T C O N T

1240060 E N T S o F T E S T 3 . T X

1240100 T C O N T E N T S o F T E

1240120 S T 3 . T X T C O N T E N T S

1240140 o F T E S T 3 . T X T C O

1240160 N T E N T S o F T E S T 3 .

1240200 T X T C O N T E N T S o F

1240220 T E S T 3 . T X T C O N T E N

1240240 T S o F T E S T 3 . T X T

1240260 C O N T E N T S o F T E S T

1240300 3 . T X T C O N T E N T S o

1240320 F T E S T 3 . T X T C O N T

1240340 E N T S o F T E S T 3 . T X

1240360 T \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0

1240400 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0

So, we saw that the contents matches with what we stored in test3.txt.
You can follow the same approach to traverse the directory hierarchy to print the contents of other files.
Lets print the primary FAT Table as well

0002000 f8 ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff

0002020 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Entry 0 = 0xf8 (media type non removable)

Entry 1 = 0xff

Entry 2 = 0xff

Entry 6 = 0xff which indicates the end of file for test3.txt

(ie test3.txt has only one cluster allocated)

Thats all for today. I hope you find this article useful. If you have any questions or find something missing or incorrect please post your comments.
Have Fun !!!

Executable File Formats (ELF)

2010-04-17T18:19:00.025+05:30

What happens when you compile your C code ?

Answer is simple, the compiler generates the executable. On a linux/unix system, by deafult the name of the executable generated is “a.out”.

What’s there inside an executable file (a.out) ?

Have you ever tried dissecting an a.out file ? Its not a plain binary file of machine codes. It is much more than that and has lot of other information that helps Operating System to load it in memory. The executable files have various formats like COFF, ELF etc.

Now a day, most of the unix like operating systems (linux, BSD, Solaris, IRIX) etc use ELF (Executable and Linkable Format) format for their executables.

Typically an elf executable includes

ELF Header
Program Headers
Section Headers
Data referred by program or section headers

Dissecting an ELF File
We will take a simple C Program, compile it and see what all is there in the generated a.out (ELF) file.

/************************* test.c ************************/

int global1 = 100;

int global2;

int main (void)

{

global2 = 200;

global1 = 300;

printf(“global1 = %d global2 = %d\n”, global1, global2);

return 0;

}

On compiling it on a linux system, a.out is generated with elf file format.

You can determine the file format using the file command.

# file a.out

a.out ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), for GNU/Linux 2.6.9, dynamically linked (user shared libs), for GNU/Linux 2.6.9, not stripped

“file” command determines this information by reading the Elf Header which lies at the start of file.

ELF Header

Always lie at the start of the executable file. ELF header has an overall information about the entire elf file. It describes the target architecture (Intel 80386 in this case), version of elf, location and number of program and section headers. It also contains the location of the first executable instruction (called entry point).

Lets print the contents of ELF header for our “a.out” elf executable. You can use the tool “readelf” to dissect the elf executable.

ELF HEADER

-----------

#define EI_NIDENT 16

typedef struct {

unsigned char e_ident[EI_NIDENT]; // elf magic

Elf32_Half e_type;

Elf32_Half e_machine; // target machine architecture

Elf32_Word e_version;

Elf32_Addr e_entry; // entry point address

Elf32_Off e_phoff; // program hdr table’s file offset

Elf32_Off e_shoff; // section hgr table’s file offset

Elf32_Word e_flags;

Elf32_Half e_ehsize; // elf header size in bytes

Elf32_Half e_phentsize; // size of one entry in program

// header table in bytes. All

// Entries are of equal size

Elf32_Half e_phnum; // number of entries in programm header table

Elf32_Half e_shentsize; // size of section header in bytes

Elf32_Half e_shnum; // number of section headers in section header table

Elf32_Half e_shstrndx; // index of .shstrtab section in section header table.

} Elf32_Ehdr;

# readelf -h a.out

ELF Header:

Magic: 7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00

Class: ELF32

Data: 2's complement, little endian

Version: 1 (current)

OS/ABI: UNIX - System V

ABI Version: 0

Type: EXEC (Executable file)

Machine: Intel 80386

Version: 0x1

Entry point address: 0x80482b0

Start of program headers: 52 (bytes into file)

Start of section headers: 1980 (bytes into file)

Flags: 0x0

Size of this header: 52 (bytes)

Size of program headers: 32 (bytes)

Number of program headers: 7

Size of section headers: 40 (bytes)

Number of section headers: 28

Section header string table index: 25

The first four bytes hold a magic number identifying the file as ELF executable.

The second (0x45), third (0x4c) and fourth (0x46) characters are in fact the ASCII values for ‘E’, ‘L’, ‘F’. The “file” command reads this magic number to determine if this is an ELF file or not.

Note the entry point address. This is the address of first instruction where the control is transferred after loading the executable in memory.

Elf Header also contains the offset at which the program header table and section header table are placed in the a.out file.

ELF Section Headers

The elf executable contains various sections and each section has a corresponding section header that contains the section name, the virtual address at which this should be loaded, the type of section, offset from the beginning file at which the first byte of the section resides, the size of section etc.

Few important sections are:

.text : This section hold the executable instructions of the program.
.bss : This holds the uninitialized global data. In our example code, the variable global2 will go to the .bss section. All data in this section is initialized with 0, when program is loaded into memory. This section occupies no space in elf file. We only have a header for .bss section in the elf file. There is no need to allocate any space in the a.out (elf file) as we know that the initial value of the variables inside .bss is 0.
.data : Global initialized data goes here.
.strtab : It holds the names of various symbols.
.symtab : It holds a symbol entry for each symbol.
.shstrtab : This section holds sections names.

There are various other sections as well. But we will concentrate only on the above sections.

Lets print the section header for above sections. Again, readelf can be used to print the section headers.

ELF SECTION HEADER

------------------

typedef struct {

Elf32_Word sh_name; // offset into .shstrtab section

Elf32_Word sh_type;

Elf32_Word sh_flags;

Elf32_Addr sh_addr;

Elf32_Off sh_offset;

Elf32_Word sh_size;

Elf32_Word sh_link;

Elf32_Word sh_info;

Elf32_Word sh_addralign;

Elf32_Word sh_entsize;

} Elf32_Shdr;

# readelf –S a.out

(only important fields are shown below)

Section Headers:

[Nr] Name Type Addr Off Size Flg

[12] .text PROGBITS 080482b0 0002b0 0001d8 AX

[22] .data PROGBITS 080495c4 0005c4 000008 WA

[23] .bss NOBITS 080495cc 0005cc 00000c WA

[25] .shstrtab STRTAB 00000000 0006e0 0000db

[26] .symtab SYMTAB 00000000 000c1c 000460

[27] .strtab STRTAB 00000000 00107c 00026a

The sections flags have following meanings:

A (ALLOC) The space should be allocated in memory to load this section. See that symbol and string table are not loaded in memory
X (EXEC INSTRUCTIONS) The section contians executable machine instructions. See that .text section has this flag set.
W (WRITE) The section has data that can be modified during program execution.

Note the section type (NOBITS) of .bss section. NOBITS indicates that section does not occupy any space in th executable file.

Also, note that the virtual address of sections .symtab, .strtab is 0, which means that they are not loaded in memory. They are only used during debugging of the program.

The offset specifies where the actual bytes for that section reside in the elf file.

For eg. offset for .text section is 0x2b0, which means that the machine instructions for this program lie at an offset of 0x2b0 from the start of a.out file.

offset for .text section is 0x2b0, which means that the machine instructions for this program lie at an offset of 0x2b0 from the start of a.out file.

The name is not the actual name of the section. We cannot store the name of section in section header as want all section headers to be of equal size. Its easier to parse the sections if all of them are of equal size. So, instead of keeping the name an offset is stored. The offset is actually an index into the “.shstrtab” section, giving the location of null terminated string.

You can also print the symbol table of elf file.

SYMBOL TABLE ENTRY

-------------------

typedef struct {

Elf32_Word st_name; // offset into .strtab section

Elf32_Addr st_value;

Elf32_Word st_size;

unsigned char st_info;

unsigned char st_other;

Elf32_Half st_shndx;

} Elf32_Sym;

# readelf -s a.out

Symbol table '.symtab' contains 70 entries:

Num: Value Size Type Bind Vis Ndx Name

…

62: 080495d4 4 OBJECT GLOBAL DEFAULT 23 global2

63: 080495c8 4 OBJECT GLOBAL DEFAULT 22 global1

…

68: 08048384 82 FUNC GLOBAL DEFAULT 12 main

69: 08048250 0 FUNC GLOBAL DEFAULT 10 _init

…

Symbol table has a symbol table entry for each symbol. Each entry is of fixed size. As each entry is of fixed size, we cannot keep “symbol” name in the entry. Here also an offset is stored. The offset is an index into the “.strtab” section, giving the location of null terminated symbol name.

Note the virtual address (0x080495c8) of symbol “global1”. It is an initialized global symbol, so it must go to .data section. The start address of section .data = 0x080495c4 and its size is 0x8 bytes. Hence, we can see that “global1” resides in .data section.

# objdump –S a.out

08048384

8048384: 8d 4c 24 04 lea 0x4(%esp),%ecx

8048388: 83 e4 f0 and $0xfffffff0,%esp

804838b: ff 71 fc pushl 0xfffffffc(%ecx)

804838e: 55 push %ebp

804838f: 89 e5 mov %esp,%ebp

8048391: 51 push %ecx

8048392: 83 ec 14 sub $0x14,%esp

8048395: c7 05 d4 95 04 08 c8 movl $0xc8,0x80495d4

804839c: 00 00 00

804839f: c7 05 c8 95 04 08 2c movl $0x12c,0x80495c8

Note: we are storing 300 (0x12c) at address 0x80495c8 which is the address of variable global1.

Simlilarly, 200 (0xc8) is stored at 0x80495d4 which is the address of variable global2. Also, see that global2 is uninitialized global variable so it must reside in .bss section. The start virtual address of .bss = 0x080495cc and its size is 0xc bytes. So, we can clearly see that global2 resides in .bss section.

Program Header Table

Program Header Table are used meaningful only for executable files and shared object files. Or you can say, that any object file that needs to be loaded into memory for execution needs a program header table.

Each entry in the program header table describes a segment in the process address space. It has the information needed to create an executable process image in memory. The operating system copies the loadable segment (PT_LOAD) into the memory according to the location and size information.

So, various sections having common attributes/types are combined together to form a single segment.

The sections like .text, .init, .fini, .plt etc all have machine executable code and have same attributes. So, they all can be combined together to form a single entry in program header table or single segment.

Similarly, sections like .bss, .data, .got etc all have data corresponding to various variables that can be modified during program execution. So, all these sections are combined together to form a single segment.

Lets print the program header table for our a.out file

PROGRAM HEADER

--------------

typedef struct {

Elf32_Word p_type;

Elf32_Off p_offset;

Elf32_Addr p_vaddr;

Elf32_Addr p_paddr;

Elf32_Word p_filesz;

Elf32_Word p_memsz;

Elf32_Word p_flags;

Elf32_Word p_align;

} Elf32_Phdr;

# readelf -l .a.out

Elf file type is EXEC (Executable file)

Entry point 0x80482b0

There are 7 program headers, starting at offset 52

Program Headers:

Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align

…

LOAD 0x000000 0x08048000 0x08048000 0x004cc 0x004cc R E 0x1000

LOAD 0x0004cc 0x080494cc 0x080494cc 0x00100 0x0010c RW 0x1000

…

GNU_STACK 0x000000 0x00000000 0x00000000 0x00000 0x00000 RW 0x4

Section to Segment mapping:

Segment Sections...

01 .interp

02 .interp .note.ABI-tag .gnu.hash .dynsym .dynstr

.gnu.version .gnu.version_r .rel.dyn .rel.plt .init

.plt.text .fini .rodata .eh_frame

03 .ctors .dtors .jcr .dynamic .got .got.plt .data .bss

…

If type of segment is PT_LOAD, it indicates that the Operating System should load this segment in memory.

The type GNU_STACK indicates that program needs a stack segment. Its virtual address and size is 0. It is upto the operating system to decide on size and where to create the stack segment.

The command output also displays the section to segment mapping to tell which all sections are combined together to form a particular segment.

That’s all for today. Hope you find it useful. In case you have any suggestions or you find any errors please provide your comments below.

Till then, Have Fun !!!

Process Address Space

2010-04-10T14:47:00.020+05:30

What is Process Address Space ?

In simple words, address space is a range of addresses that a process can access. If a process tries to access any address which does not lie in its address space, the operating
system kills the process. The process dies with the following prints “Segmentation Fault: core dumped”.

Lets take a simple example

test.c

int globalx = 100;

int globaly;

int main (void)

{

If (globalx == 100) {

globaly = 200;

}

return 0;

}

When you compile this program, you get an executable. The executable files have various formats like elf, coff etc. On a linux system the executable generated has elf file format. There are various tools available that can be used to read the elf executable file. One of such tools is readelf. This can display all the sections generated and the virtual addresses assigned to them.

# gcc test.c

Executable a.out is created. Use readelf to read the various sections of a.out

# readelf -e a.out

a.out has lots of other sections, but lets concentrate only on the following important sections and fields

Section Headers:

Name Addr Size

[ 0 ] .text 0x08048280 0x1b8

[ 1 ] .data 0x08049558 0x8

[ 2 ] .bss 0x08049560 0xc

All the machine instructions corresponding to your code go to .text sections. All initialized global variables go to .data section. In this case, globalx will go to .data section. All uninitialized global variables (globaly) will go to .bss sections.

So, what is the address space for this process ?

All .text/.data/.bss addresses consitute the address space of this process.

.text address range (0x08048280 to 0x08048437)

Note: size of .text section is 0x1b8

.data address range (0x08049558 to 0x0804955F)

.bss address range (0x08049560 to 0x0804956B)

Access to any address outside the above address ranges will cause segmentation fault and your process will be killed by the Operating System.

Apart from this there are other sections (like .stack etc) as well but we will not discuss them at this time.

Virtual to physical address translation

The above addresses are all virtual addresses and not the actual addresses of physical RAM. The MMU (memory management unit) translates these virtual addresses to physical addresses using page tables.

Page table for a process is created by the Operating System at the time when the process is created. OS reads the executable file and finds various sections and their addresses. The page table mapping is created on demand ie when the process accesses any virtual address, OS checks in the page table if the mapping already exists for this address. If no mapping exists, it finds a free page in memory and creates a mapping for that page.

The size of page depends on the processor architecture. Typically it is 4K on various processors. On such processors, address space is divided into pages of 4K and each entry in the page table maps 4K of virtual addresses to a physical page.

An entry (page table entry or PTE) in the page table typically has the following fields.

Page Frame Address |User /Kernel| Read/Write | Present |

Page Frame Address is the physical address of the page in memory.
User bit (User = 0, Kernel = 1) specifies whether the page can be accessed in user mode or not. If this is 1, it cannot be accessed by a user process. Only kernel can access such a page. If any user tries to access such a page, the processor will generate an exception. OS will find that the user is trying to access a kernel page and so it will kill the process.
Read/Write (Read = 0, Write = 1) indicates if the process can read or write on this page. The text section pages are all mapped Read only.
Present bit indicates if the mapping is valid or not. If this bit is not set, it indicates there is no mapping for this virtual address and OS should create it.

Process Segments

Apart from page tables, OS also keeps the information about each process sections. It creates a segment for each section and keeps the information like start virtual address of this section, protections for entire section (like read only for text sectioon), size of the section in the segment. This information is used to determine if process is accessing any address outside its address space.

So, for our example, OS will create three segments for .text, .bss and .data section. There’s one more for stack as well.

Accessing a valid address for the first time

Kernel creates the mapping on demand. When the virtual address is first accessed, the MMU (harware) first finds out its mapping in the page table. As this is the first time this address is accessed, MMU will not find any mapping in the page table. So, it will generate an exception and the control will be given to the exception handler code of kernel. The handler first checks if the virtual address is a valid address or not. It checks all the segments of that process one by one and validates that the address should lie in one of the segments. If the address lie in one of the segment , it will find a free page in memory and create a mapping for that page in the page table. It will also set various bits in the PTE. For eg. Present = 1, User = 0, Read = 1 or 0 (depending on type of section).

Accessing an address outside the address space

Suppose due to some bug, your process try to access some random address, the MMU first tries to find the physical address in the page table. In this case, it will not find any translation for this address. So, a page fault will be generated by the processor. The control will be transferred to the kernel. The page fault handler inspects all the segments of this process to determine if this is a valid address. In this case, the address will not lie in any of the segments. So, the kernel will not create any mapping for this and kill the process. You will see the prints “Segmentation Fault: core dumped”.

Writing to a read only section

If the process try to write to a read only page, there are two cases.

Case 1: The page table entry is already created earlier when the address was accessed for read. The PTE has Read bit = 0. ie page is read only. In this case, the MMU will find the PTE in the page table. As the process is trying to write on this page, MMU will generate an access fault exception. The exception handler will then kill the process.
Case 2: The page table doesn't have an entry for this address. Page fault is generated and the exception handler will find out if the address is a valid address. As the address is valid, it will find the corresponding section in which the address lie. Next it will check the permissions on the section. Here the section is Read Only, so the handler will kill the process.

How to prevent any process from accessing/corrupting the pages of another page

One process should not be allowed to access the data of another page for security reasons. How this is done?

Note that the access to the physical page is controlled by the page table of that process. The page tables are created by the kernel. Kernel will never create a mapping so as to allow one process to access another process pages. For eg. the data pages for a process A will be mapped only by its page table. No other page table will have a mapping for the data pages of process A.

How to prevent any process from accessing kernel pages

In Linux, user and kernel both share the same address space. On a 32 bit system out of 4GB, first 3GB is reserved for user and last 1 GB is used by kernel.All kernel pages will have User Bit = 1 in their PTEs (ie only kernel can access these pages).

If the user tries to access any kernel page (any address greater that or equal to 3GB), MMU during converting the virtual to physical address will find that the User Bit = 1 in the PTE. So, it will generate an exception and the process will be killed by the kernel.

That’s all for today.

Have Fun !!!

VMWare Player 3.0 (A boon to Linux Hackers/Newbies)

2010-04-09T10:21:00.024+05:30

In my previous post, I discussed about VMWare Workstation, on how it can be used to create virtual machines and run various operating systems on them. However, it doesn’t come for free. It has lots of advanced features (like taking a snapshot of the virtual machine, cloning a virtual machine etc), but they may not be so important for newbies/students.

VMWare Player 3.0 is a nice alternative to Workstation for the linux beginners/learners/students. It comes for free and is very user friendly.You can create new virtual machines in few simple steps and connect an ISO image to the virtual CD drive to install your operating system. Not only that, you can also connect the physical drive of your Desktop PC to the virtual machine; And then the physical drive can be used to load OS from a boot CD.

You can also edit the settings of your virtual machine (like adding/removing a new virtual hard disk, increasing/decreasing the size of memory available to the virtual machine etc etc).

The user interface is quite similar to that of Workstation. See my previous post on how to create a linux virtual machine. The Player itself comes up with a very nicely written User guide.

So, what are you waiting for ? Go get it and

Have Fun !!!

Enjoy this video while you download your player

Hacking Linux using Virtual Machine (Vmware Workstation)

2010-04-02T09:29:00.113+05:30

Best way to learn linux is to modify it and see how it bahaves. The biggest problem the newbies/students find is the unavailability of a Test Machine to do their experiments.

But, you don’t need a separate physical machine to load/test your linux OS. If you have a desktop PC, you can create as many virtual machines as you want out of it and run as many Operating Systems (Linux/BSD/Solaris etc) on it. The solution is VMWare Workstation.
In this post we will see how to create a Virtual Machine using VMware Workstation and load Linux on it.

You can get the trial verison of VMWare Workstation from VMWare Website.

Step 1
Start VMWare Workstation. You will get the following screen.

Step 2
On the left panel, Right Click and Select New > Virtual Machine
Or Chose File > New > Virtual Machine

Step 3
Chose the type of Configuration. Select Typical

Step 4
Guest Operating System Installation. Chose “I will install Operating System Later”.

Step 5
Select a Guest Operating System. You may chose whatevere OS you would like to install. I chose Linux

Step 6
Chose the Version of OS. For eg. I want to install Red Hat Enterperise 5, So from the dropdown menu I select that.

Step 7
Name the Virtual Machine. Here you chose a name for your virtual machine. By default, workstation will assign some meaningful name to your virtual machine. In this case, it assigns “Red Hat Enterprise Linux 5”.
You also need to chose a location on your hard disk where you want to store the files related to your virtual machine being created. You may go ahead with the deafult location that Vmware Workstation choses for you by default

Step 8
Chose the number of processors for your virtual machine

Step 9
Memory for your virtual machine. Chose how much memory (RAM) you would like to give to your virtual machine, Minimum recommended is 512 MB.

Step 10
Chose the network type. Select Bridged Netwroking

Step 11
Select I/O Adapte types. Chose SCSI Adpater > LSI Logic

Step 12
Add a hard disk to your Virtual Machine. Chose “Create a new virtual disk”.

Step 13
Select Disk Type. Chose SCSI

Step 14
Specify the size of your disk. Chose 8GB and select “store virtual disk as a single file”.

Step 15
Specify the location where you would like to keep your disk file

Step 16
Congrats. Your virtual machine is ready. Click Finish to download some OS on it.

Step 17
After you successfully create a virtual machine you will see the following screen
I already had one Virtual machine created (Red Hat Enterprise 3) and below you see the new virtual machine (Red Hat Enterprise Linux 5) that we created just now

Step 18
Now, we need to load the OS on our virtual machine. We will use the virtual CD to load the OS on it. We can attach an ISO image of the Red Hat Enterpise CD to our virtual CD. There are software available that may be used to convert your bootable CD to an ISO image file.
To do this, click “Edit virtual machine settings”

Step 19
Chose ISO image file and specify the location of the ISO image file of your OS.
Chose "Connect at power on"

Step 20
Now, lets Power On the virtual machine. Click the green button "Power On this virtual machine"

Step 21
As you have already attached the ISO image of your bootable CD to the virtual CD drive, the virtual machine starts booting from it. You will see the following screen.

From here you need to follow the same steps as you do for any normal installation.

So, you have a complete virtual machine with hard disk, network card, CD Drive, USB Controller, floppy, CPU and a dislay.
You may create as many virtual machines as you want and load whatever OS you want to load on it.
Isn't this amazing.

Have Fun !!!

System Calls (Linux/Unix Kernel)

2010-03-30T19:25:00.006+05:30

System Calls

In simple words, it is a call from the user application to the Operating System to do some work for it.

Why do we need a System Call?

A very common example is reading a document from the hard disk.

To read the document from the scsi disk, you must know about the hardware details of disk. You need to program its controller so that you can pass scsi read command to it and tell the controller that you want to read a specific block. You must know the device specific protocol (like scsi) so that you can talk to the disk. Overall it will be a nightmare for the user to do a simple read/write from the disk.

Solution is let the operating system (linux/unix/windows) do it for you. All operating systems have a driver code for any hardware device (disk, mouse, keyboard, memory, ethernet card etc) attached to the system. The driver code knows how to talk to the hardware devices.

So, application/user can simply make a call to the system saying “Hey ! can you please do this for me”.

How to make a System Call ?

Unix/Linux systems include various standard libraries that provide various APIs to the users. These APIs are defined by the POSIX standard. The advantage of using these standard APIs is that these are available on all unix systems which makes the application portable.

These APIs in turn call the platform specific system calls. These systems calls are generally a part of standard C library libc and are typically written in Assembly language. These are highly system dependent (both OS and processor specific).

A user program can make a system-call directly but it is not advisable to do so as these system calls may vary from system to system. There’s no guarantee that a system call present on one system (say HP-UX) will also be present on a different system (say Solaris). But, the APIs defined by POSIX are guaranteed to be present on all POSIX compliant systems.

Typically the flow is as follows:

Application ----> POSIX library APIs (fread) ----> System Call (read)

How System Call works

The purpose of system call is to transfer control from user application to operating system. User application cannot directly call kernel functions as the kernel has protected address space which is essential for system stability and security.

A processor provides certain instructions (like “int 0x80” on i386, “sc” on PowerpC) which are used to tarnsfer the control from user to kernel. When a user program execute these instructions, an exception is taken which changes the processor mode from user to kernel. The Program counter is changed so as to execute the exception handler at a specific location. The exception handler is nothing but the system call handler in kernel. This can then invoke appropriate driver code to interact with hardware.

System Call Number and Arguments

Typically there are 100s of different system calls to do different kinds of tasks. All of them execute the same instruction (“int 0x80” on i386, “sc” on PowerPC). So, user must tell the kernel that which system call is being made. This is done by assigning a unique number to each system call.

Every processor specify an Appilication Binary Interface (ABI) that describes the low level interface between and application and operating system. The ABI describes how the system call number and arguments etc should be passed to OS. They also define how the OS will tell the user if the system call was executed successfully or not. This is done typicallly by passing the error number in a specific register.

Lets see how it happens on i386

As per the System V ABI for x86 (Linux, NetBSD follow System V ABI)

System call number is passed into eax register.
Arguments are passed in registers ebx, ecx, edx, esi and edi in order (the first five arguments). In case, the number of arguments are more than 5, then a single register is used to pass a pointer to user space address where the parameters are stored.
The return value is passed to the user via eax register. If return value is between -1 and -125 (value of eax), it means system call finished with an error. The actual error code (-eax) is then copied to “errno” variable and -1 is returned in eax.

read system call library function for i386

// read (fd, buf, numBytes)

read:

pushl %ebx // save ebx on stack

mov1 8(%esp), %ebx // pass first argument in ebx

movl 12(%esp), %ecx // pass second parameter in ecx

movl 16(%esp), %edx // pass third parameter in edx

movl $3, %eax // pass system call no in eax

int $0x80 // invoke system call

cmpl $-126, %eax // check return value

jbe out // if no error goto out

negl %eax // negate the value of eax

mov %eax, errno // save the error code in errno

mov, $-1, %eax // pass –1 to eax

out:

pop %ebx

ret // return

System call interface on PowerPC

As per System V PowerPC ABI (linux also follows System V ABI),

System call number is passed in register r0
The arguments are passed in registers r3 to r10 (total 8 argumenst in order).
The error code from OS to system call is passed in r3. The summary overflow bit (CR0_SO) in the condition register CR0 indicates if error occurred. A unix system checks if there is an error, it copies error code to “errno” and return -1 to user application.
The return value(s) from system call to user application are passed in r3 and r4.

read system call library function for PowerPC

// read (fd, buf, numBytes)

read:

li r0, 3 // pass system call number to r0

// arguments have already been passed

// in r3, r4, r5 by the caller.

sc // invoke system call

bnslr // if no error return (Summary

// Overflow bit not set)

lis r4, errno@ha // copy error code to errno variable

stw r3, errno@l(r4)

li r3, -1 // return -1 to user application

blr

Accessing/Copying user data from kernel

User is not allowed to access kernel pages which is essential for system security and stablity. However, kernel can read/write data from/to user space. Linux kernel provides two functions for this:

copy_to_user() is used to copy data from kernel address space to user address space.

copy_from_user() is used to read the data from user buffer to kernel page.

I will discuss more about these in some other post.

Kernel must verify all the arguments passed by user. The most important is the validity of the pointer provided by the user. Kernel must ensure that

address should lie with in user address space. It should not lie in kernel region else user may corrupt the kernel data.
user has valid permissions to read/write data for that address.

This is all for today. We will discuss more on how kernel handles the system call later.

Till then, Have Fun !!!

Synchronization in Linux/Unix Kernel - Part 4 (Reader-Writer Lock)

2010-03-28T21:29:00.004+05:30

Till now we saw how we can atomically read-modify-write global variables using special instructions provided by the processor. We also saw the use and implementation of Spin Locks and Semaphores. In this post we will discuss about a new locking mechanism called Reader-Writer Lock.

Consider a case where we have a file shared across various processes with the following constraints.

Multiple processes can read the file simultaneously.
Only one process can write to the file at a time. No other process should be allowed to read/write the file while one of the process is writing to the file.

We can’t use Spin Lock here as it allows only one process to access the file. Spin Lock can’t distinguish between readers and writers. Also, read/write to file on disk is time consuming operation and spin lock is not suitable here.

Semaphores or Counting Semaphores are also not suitable here as they can’t distinguish between reader and writer.

We need a separate type of lock here called Reader Writer Lock.

It keeps track of number of readers/writers reading/writing to the file. It also keep track of number of readers/writers that are waiting to take the lock.

Reader Write Lock

If there are only readers it allows all of them to take the lock.
If a new writer comes it blocks the writer until all readers are done. But, if new readers keep coming and we allow them to take the lock, it will cause writers to starve.
Similarly, if a writer is active, all new readers and writers will be blocked.

Question is whom to wake up after the writer is done ? Should it wake up another writer or all other readers ? If writers are given preference, readers could starve.

To solve the problem of starvation

All new readers are blocked if there is any writer already waiting so that we don’t starve writers.
If a reader releases the lock, it takes no action if some readers are already active. When the last reader releases the lock, it issues wakeup to the waiting writer.
If a writer realease the lock, it issues wakeup to all the blocked readers. If there are no blocked readers, it issues wakeup to the single blocked writer.

With this scheme we can alternate access to the resource between a writer and bunch of readers.

Implementation of reader writer lock

typedef struct rwLock {

spinLock sl; // spin lock to synchronize access

// to following members of lock

// by multiple threads.

int nActive; // number of active readers.

// if -1, a writer is active

int nReadPending; // number of blocked readers

int nWritePending; // number of blocked writers

queue readers; // queue to put blocked readers

queue writers; // queue to put blocked writers

} rwLock;

void LockRead (rwLock *lock)

{

acquire the spin lock // acquire the spin lock

lock->nReadPending++;

if (nWritePending) { // if any writer already blocked

add itself to readers wait queue

release the spin lock

sleep

acquire the spin lock

}

while (lock->nActive == -1) { // if any writer already

//acquired the lock

add itself to reader wait queue

release the spin lock

sleep

acquire the spin lock

}

lock->nActive++;

lock->nReadPending--;

release the spin lock

}

void LockWrite (rwLock *lock)

{

spinLock(&lock->sl); // acquire the spin lock

lock->nWritePending++;

while (lock->nActive) { // any reader/writer active

add itself to writer queue

release spin lock

sleep

acquire the spin lock

}

lock->nWritePending--;

lock->nActive = -1;

release the spin lock

}

void UnlockRead (rwLock *lock)

{

acquire the spin lock

lock->nActive--;

if (lock->nActive == 0) { // no readers/writers active

issue wakeup to writers

release spin lock

} else {

release the spin lock // if any reader writer

// active, don’t do anything

}

void UnlockWrite (rwLock *lock)

{

Acquire the spin lock

lock->nActive = 0;

if (nReadPending) { // if any readers blocked

wake all readers

release the spin lock

} else {

wake the single writer

release the spin lock

}

Note that the structure rwLock lock has several members. All these members can be accessed by various processes concurrently. So, to synchronize access to all these members a single spin lock is used. This spin lock should be taken before accessing any member of the rwLock.

Reader Writer lock is used by filesystem code while doing any read/write to a file in a filesystem. The lock is acquired at the start of read/write system call and released as soon as the system call is done. It allows multiple readers to read the file but allows only a single writer to write the file.

Synchronization in linux/unix kernel - Part 3 (Semaphores)

2010-03-27T12:53:00.156+05:30

In my previous post we discussed how Spin Locks can be useful when we need to update multiple global variables atomically. We saw that Spin Locks should be acquired only for a short duration of time as the blocking threads spin in a loop and not doing any thing useful. In this post we will discuss the scenarios where we need to grab a lock for long duration and the ways to solve such problems.

Single Printer and Multiple Users Problem

Lets consider a common example where there is a single printer and multiple threads (thread1, thread2, thread3) that want to print their files (say file1, file2, file3 respectively) As there is only one printer, while one of the threads is printing its file, the others should wait. Also, we are not sure about how much time a single job will take to finish. It may take from few seconds to few hours depending on the size of the file. So, the waiting threads cannot spin in a loop as they will waste lot of cpu cycles. The better option for them is to sleep so that some other thread can run. When the printing job is done the thread at the front of queue should be awakened so that it can start printing its file.

This kind of problem is solved by using a synchronization mechanism called Semaphore.

To implement a semaphore we need a flag to indicate if printer is in use and a queue to keep info about waiting threads.

struct semaphore {

int flag; // flag = 0, means resource BUSY,

// flag = 1, means resource is FREE

queue q; // queue to store pids of all waiting threads

// pid can be later used to issue wakeup to the

// sleeping threads

};

The thread that needs to print the file will first check if the flag is equal to 0 (printer is available). If flag == 0, it will set flag to 1 (to indicate printer is in use) and start printing its file. The test-and-set should be done atomically else two or more threads may feel that they all have acquired the lock. See my previous posts to find out the problems if test-and-set is not done atomically.

If any thread finds that the flag is already set, (printer is busy), it will put itself on the queue and will sleep.

When the printing job is done, flag is again set to 0 to indicate that the printer is free And wakeup is issued to the threads waiting for the printer to become free. No need to issue wakeup to all waiting threads. Wakeup the thread which is waiting for the longest time (ie the thread at the front of queue). The woken-up thread again sets the flag = 1 and starts printing its file.

Semaphores are also called SLEEPING LOCKS as the waiting threads don’t spin but sleep.

Semaphore and related operations.

typedef struct semaphore {

int flag;

queue q;

} semaphore;

semaphore sem; // Create a semaphore for printer

void initSem(semaphore *sem)

{

sem->flag = 0; // Mark resource as free. Printer is available

initialize the queue with all 0s. // No thread is waiting initially

}

void acquireSem(semaphore *sem)

{

while (test_and_set(sem->flag)) { // atomically test-and-set the flag

add itself to the end of queue // if flag is set, add itself to queue

sleep;

}

void releaseSem(semaphore *sem)

{

atomic_set(sem->flag, 0); // Mark the resource free. Set flag to 0

if threads are waiting on queue,

issue wakeup to the first thread on queue

}

Note: Care must be taken while adding/removing threads from the queue. As multiple threads may be adding/removing themselves to the queue, a spin lock should be used to prevent queue from corruption. Spin lock will ensure that only a single thread is being added/removed from the queue. In fact, a single spin lock can be used to synchronize access to both flag and queue. The spin lock should be released before going to sleep.

See the example at the end of this post to see how spin lock can be used to implement a semaphore.

This is not the actual implementation but gives you a basic idea on how semaphores work.

The semaphore discussed above can be used to implement a mutex as it allows only a single thread to access the shared resource. These are also called Binary Semaphore.

Multiple Printers and Multiple Users Problem

We saw how a semaphore can be used to synchronize the access to a shared resource. Think of a case where there are multiple resources of same type eg multiple printers. If we have 10 printers then we should allow 10 users to print their files simultaneously.

Solution is Counting Semaphore

This problem is solved by using Counting Semaphores. Here a counter is used to keep track of the threads that are using the shared resources.

struct semaphore {

int count; // initial value of count is equal to the number of shared

// resources.

queue q;

};

Implementing a Counting Semaphore

To implement a Counting Semaphore, the initial value of the count is set to the number of available resources. So, if we have 10 printers initial value of count = 10.

To aquire a semaphore, thread first decrements the value of count by 1. And then tests if count >= 0, which means some printers are available and the thread can start printing his job. So, atmost 10 threads can be printing their files simultaneously.

If the value of count after decrement becomes negative, it means no printer is free and the incoming thread will put itself on the sleep queue. After any printing job is done, count is inceremented by 1 and wakeup is issued to the first thread on the queue.

There are three cases

Case 1: count is > 0. This mean that resource is available. For our 10 printer example, if value of count is 4, it means 4 printers are free.

Case 2: count = 0. No resource available. For our 10 printer case, 0 means no printer is available and no one is waiting on the queue.

Case 3: count < 0. No resource is available. For our 10 printer case, if value of count is -3, it means all printers are busy and 3 threads are waiting in the queue.

So, the value of count may be used to determine if any thread is waiting in the queue. If value of lock < 0, it means some threads are waiting in the queue.

Implementing a Counting Semaphore

typedef struct semaphore {

int count;

queue q

} semaphore;

semaphore sem;

void initSem(semaphore *sem)

{

sem->count = 10; // Initialize the count to 10, to indicate

// 10 resources (printers) are available

initialize the queue with all 0s // No thread is waiting initially

}

void acquireSem(semaphore *sem)

{

decrement sem->count

if (sem->count < 0) {

add itself to the end of queue.

sleep; // Sleep if no resource is available

}

void releaseSem(semaphore *sem)

{

increment sem->count

if (sem->count <= 0) {

remove thread from the fron of waiting queue and

issue wakeup to it

}

Again, this is not the actual implementation. The count should be modified/checked atomically. Similarly, a thread may be added only if the resource is not available. While acquiring the semaphore, all the operations like decrementing the count, testing its value and then putting the thread on sleep queue should be done atomically. So, a single spin lock should be used to prevent access to both count and queue.

Sempahore using a spin lock to prevent access to its data

typedef struct semaphore {

int spinLock; // spin lock to prevent access to count and queue.

int count;

queue q

}

Spin lock is accessed only for short time, while modifying/testing count value and while adding thread to the queue. The spin lock should be released before going to sleep.

Semaphore operations using a spin lock

void acquireSem(semaphore *sem)

{

acquire spin lock

decrement sem->count

if (sem->count < 0) {

add itself to the end of queue.

release spin lock

sleep; // Sleep if no resource is available

}

void releaseSem(semaphore *sem)

{

Acquire spin lock

increment sem->count

if (sem->count <= 0) {

remove thread from the front of waiting queue

release spin lock

issue wake up to removed thread

}

Note: Counting semaphores can be used to implement Mutex or Binary Semaphores by initializaing the count to 1.

Hope you find this article useful. If you have any comments/suggestions please post them below.

Have Fun !!!

Synchronization in Linux Kernel - Part 2 (Spin Locks)

2010-03-21T18:37:00.293+05:30

In continuation to my previous post, lets discuss other concurrency
related problems and their solutions. Earlier, we saw how concurrent
access to a shared variable may result in loss of information or data
corruption. In this article, we will explore more such problems and
ways to solve them.

Consider a scenario where there is a need to update multiple shared
global variables atomically. No other thread should be allowed to
acess the global variables until the thread that is updating them is done.

For eg. take the case of multiple threads adding/removing/reading
elements from a linked list concurrently. This may result in linked list
corruption if done without using appropriate synchronization mechanism
as shown in following example.

Consider a linked list

Head -----> Element1 -----> Element2 -----> Element3 -----> Element4 -----> Null

To add a new element (say NewElement) in this list after a specific element (say Element3) following operations need to be performed.

Step 1) First update NewElement to point to Element4

Head ----> Element1 ----> Element2 -----> Element3 -----> Element4 -----> Null
|
NewElement -------+

Step 2) Update Element3 to point to NewElement

Head ----> Element1 ----> Element2 ----> Element3 Element4 ----> Null
| |

+--- NewElement --+

Now, suppose thread-1 needs to add NewElement1 after Element3 and

thread-2 wants to add NewElement2 after Element3.

thread-1 is running on cpu-1 and thread-2 is running on cpu-2 concurrently.

1) thread-1 executes Step-1 to make NewElement1 point to Element4. Just after that thread-2 executes and updates NewElement2 to point to Element4 as shown below.

NewElement1 -----+
|

Head ----> Element1 ----> Element2 -----> Element3 -----> Element4 ----> Null
|
NewElement2 -----+

2) thread-1 then updates Element3 to point to NewElement1.

+--- NewElement1 ---+
| |
Head ----> Element1 ----> Element2 -----> Element3 Element4 ----> Null

|
NewElement2---+

3) And then thread2 also updates Element3 to point to the NewElement2

NewElement1 ---+
|

Head ----> Element1 ----> Element2 ------> Element3 Element4 ----> Null
| |

+--- NewElement2 ---+

So, finally we have NewElement2 successfully inserted into the linked list. But, NewElement1 is not a part of the linked list, So we lost Element1.

How to solve the problem where multiple global shared variables need to be updated atomically ?

Answer is simple. We need to prevent all threads from accessing the linked list while one of the thread is manipulating the list.

To achieve this, use one global variable as a lock. Any thread that needs to access the list must acquire the lock by setting its value to 1. This thread will first test if the value of lock variable is 0, then set it to1 to acquire the lock. This test-and-set should be done atomically. If any thread is already holding a lock, all others threads should wait. The thread holding the lock will release the lock (by setting the lock to 0) after it is done with the list.

This locking variable is called Spin Lock.

A Spin Lock can be implemented as a single bit in an integer variable. The most important thing here is that the testing and setting of the lock bit should be done atomically. Performing read-modify-write operation atomically is one of the prime requirement of implementing a spin lock.

If test-and-set is not done atomically then multiple threads may erroneously come under the impression that they all hold the lock simultaneouly which will lead to data corruption. See the example below how this may happen.

Problem if test-and-set is not done atomically

thread-1 thread-2

Lock Variable = 0

1) Reads the value of lock variable (=0)

to its register.

2) Reads the value of lock variable (=0)
to its register.

(Both of them find the value of Lock variable to be 0, So they assume that the lock is free.)

3) Checks the value of local register.

Value is 0, So try to acquire the

lock by writing 1 to lock variable

   in memory.
   4) thread-2 also finds that the value of
    global variable read in its register
   = 0, which means lock is free. So,

writes 1 to the lock variable to
acquire the lock.

(Both of them now feel that have acquired the lock which is wrong)

So, test and set should be done atomically.

Lets first see a simple implementation of test_and_set()

int test_and_set (int *lock)
{

int temp = *lock; // save the original value of lock

*x = 1; // always set lock to 1

return temp; // return the original value

}

Note: this is not atomic.

test_and_set() saves the original value of lock, sets the lock to 1 and returns the old value of lock. Of course, this should be done atomically.

The return value indicates whether it was already locked or not.

If return value is 0, it means that lock was free and by writing 1, the caller has acquired the lock.

If return value is 1, it means that the lock was already acquired by someone else. So, the caller needs to call this function again. The caller will keep calling this in a loop until this function returns 0.

Why it always set lock to 1 ?

You may be the thinking why this function always sets the value of lock to 1 ? What if the value is already 1? Why don’t we first check the value of lock? We should set it to 1 only if the initial value of lock is 0.

Well, answer is that there is nothing wrong in testing the value before setting it to 1. But, to test we need an extra instruction which can be avoided by always setting it to 1.

How to make test_and_set atomic ?

As I discussed my previous post, we need support from processor to achieve this. For eg i386 provides an “xchg” instruction that can atomically exchange the value of memory location with its internal register.

int atomic_test_and_set (int *lock)

.text

.globl atomic_test_and_set

atomic_test_and_set:
pushl %ebx // Preserve ebx. We will save original

                        // value of lock in ebx.

   movl    8(%esp), %ebx // save original value of lock to

                          // ebx
   movl    $1, %eax       // 1 (true) to eax

   xchg    %eax, (%ebx)   // Atomically exchange eax with

// lock. Sets lock = 1.

popl %ebx // Restor ebx

ret // return old value of lock

// which is already in eax.

Lets see how PowerPC does it.

int atomic_test_and_set (int *lock)

atomic_test_and_set: loop:

lwarx r4, 0, r3 // Save the initial value of lock.

// r3 = address of lock variable

li r5, 1 // 1 (true) to r5

stwcx r5, 0, r3 // store 1 to lock

bne- loop // go back to loop if store is not

// done atomically

mr r3, r4 // move original value of lock saved

// in r4 to r3.

blr // return valus is in r3

Lets come back to our original discussion on Spin Locks. We will see how we can implement a Spin Lock on i386 and PowerPC shortly.

Why the word “spin” is used before lock ?

The reason is that while one of the thread has acquired the lock, all other threads spin in a loop repeatedly checking until the lock becomes available.

Spin Locks should be acquired for a short time
As the threads spinning in loop are not doing any useful work they are wasting costly cpu cycles. So, spinlocks should be held only for a short duration of time.

Why not deschedule the thread instead of spinning ?

Descheduling a thread means two context switches which are far more costlier than to spin in a loop for a short duration.

Thread should never sleep/descheduled after acquiring the spin lock

If a thread goes to sleep or descheduled after acquiring the spin lock all other threads that need the same lock will be blocked spinning in a loop wasting cpu cycles.

Disabling interrupts

If a shared variable is also accessed by an interrupt handler then local interrupts should also be disabled. Otherwise it is possible that the thread after acquiring the lock is preempted by the interrupt which tries to acquire the same lock as well. The interrupt handler will stuck in the busy-wait loop as the thread which is holding the lock never gets the chance to run to release the lock. So, both of them deadlock.

Uniprocessor systems don’t need spin locks.

Disabling interrupts is sufficient on a single cpu system.

Spin Lock implementation

atomic_test_and_set() discussed above is the buliding block of implementing a spin lock.

void SpinLock(boolean *lock)

{

while (atomic_test_and_set(lock) == 1) /* If already locked spin */

;

}

The caller obtains the lock if the old value of lock is 0, else it spins calling atomic_test_and_set() in a while loop, until it return 0.

Spin Lock is implementation on i386

SpinLock:

mov eax, 0x1 // Set the register eax = 1

loop:

xchg eax, [lock] // Atomically exchange the values of lock and register eax

   test eax, eax // Check the old value of lock which is now in eax
   jnz loop // If old value of lock is not 0 (lock not free), spin in
   // loop

ret

SpinUnlock:

mov eax, 0x0 // Set eax register = 0

xchg eax, [lock] // Exchange the values of lock and eax register.
// This will set the value of lock to 0.

ret

Spin Lock implmentation on PowerPC

SpinLock:

loop:

lwarx r4, 0, r3 // register r3 has the address of lock variable
// Load the initial value of lock variable to register r4

// and place a reservation on lock address

cmpwi r4, 0 // compare value of lock with 0

bne- loop // if value of lock is 1, go to loop

li r5, 1 // Set r5 = 1

stwcx r5, 0, r3 // Store 1 to lock, if reservation exists

bne- loop // If reservation lost, try again

// lock acquired successfully

blr // return

Synchronization in Linux Kernel

2010-03-14T16:44:00.002+05:30

Linux Synchronization

We need synchronization mechanisms when two or more threads try to access a shared resource simultaneously. By using synchronization mechanisms kernel allows only one thread to execute while the other threads wait.

Concurrency in Uniprocessor systems

You may be thinking that how multiple threads may execute concurrently when there is only one CPU. In a single cpu system, although multiple threads can not run simultaneously but a thread may be preempted by an interrupt Or it may be descheduled to run another thread on the cpu.

The preemption can lead to same problems of concurrency like data corruption, deadlock etc.

Masking an interrupt is a simple technique used on single cpu systems to solve concurrency related problems. If a global variable is shared by both an interrupt handler and a kernel thread, that interrupt should be masked by the thread while reading/modifying the shared variable.

Concurrency on SMP systems

On an SMP system, two or more processors are connected to a single shared main memory. Multiple threads can run concurrently on different processors and can access the data on main memory simultaneously. Here, masking the interrupts on a single cpu or on all cpus does not solve the problem as we still have threads on other cpus running.

We need more complex mechanisms here which we will discuss later.

Problems due to concurrent access of shared resource

It is very important to understand the problems or the undesirable effects due to concurrent access of a shared resource by multiple threads. Lets try to understand this using a simple example.

Suppose there is a global variable called “state” (8 bits wide). Consider two threads where thread-1 wants to set bit number one whereas thread-2 wants to set bit number two in the shared variable "state". If any bit is already set, it should remain set.

To set a bit, a processor needs to do following three operations

1) Read the current value from memory in its internal register.

2) Set the bit in register.

3) Store the modified value of register to memory.

In fact, these are the common steps to perform any read-modify-write operations.

Let the initial value of global variable "state" be 0xF0 (11110000b). The final value after both threads finished execution should be 0xF3 (11110011b).

However this is not the case. It may happen that the final value of "state" is either 0xF1or 0xF2 or 0xF3. This may happen when both the threads execute simultaneously. See the following example.

Thread 1 Thread 2

Loads the value (0xF0) of global variable "state"
to its register.

Loads the value (0xF0) of global variable "state"
to its register.
(As only one processor can access the memory at a time, lets assume that thread-1 loads the value first and
then the thread-2)

Sets bit number 1 in its register (0xF0 -> 0xF1) Sets bit number 2 in its register (0xF0 -> 0xF2)
(Both the processors can do this at the same time as they are using their internal registers.)

Stores the updated value (0xF1) in its register

to memory.

Stores the updated value (0xF2) in its register

to memory
(Again lets assume thread-1 stores first)

So, the final value is 0xF2 whereas it should have been 0xF3. We lost the bit number 1 set by thread-1.
If thread-2 would have stored its value first, the final value will be 0xF1. In that case, the bit set by thread-2 would have been lost.
So, concurrency access may lead to data corruption.

How to solve the above problem

The above problem can be solved if all the three operations are performed in single step (ie all other cpus are prevented from accessing the shared variable while one of the cpu is read-modify-writing to it.)

For this we need support from the processor hardware. Most of the modern day processors provide instructions to perform above operations atomically.

Lets take an example of 80386 processor

80386 provides an instruction “btsl” to set a bit in memory. The format is as follows

btsl memAddr, bitNum // This will set bitNum at memAddr

But there is no guarantee that the above operation is atomic. To solve this, 80386 provides a mechanism where the memory bus may be locked until read-modify-write instruction has finished its execution. This is done by prefixing the instruction opcode by “lock”. When the contol unit detects the “lock” prefix, it locks the memory bus until that instruction is finished. No other processor can access the memory bus until the locked instruction has finished execution.

lock; btsl memAddr, bitNum // Atomically sets biNum at memAddr

Similarly, “lock" prefix may be used to atomically increment a number.

lock; incl memAddr // Atomically increments the number stored at
// memAddr

Lets see how this happens on PowerPC
PowerPC provides two instructions to make read-modify-write instructions atomic. It doesn’t lock the memory bus but informs the programmer if the read-modify-write was atomic (by setting a bit in one of its conditional registers). The programmer can then retry the operation if the opertaion was not atomic.

The two instructions to provide atomicity are “lwarx” and “stwcx”.

lwarx: Reads the word from memory and places a reservation on the loaded address.
Think reservation as a kind of register that keeps the address of reserved memory.

If the processor detects that another processor writes to the reserved address (using any store instruction), it clears the reservation.

stwcx : Stores only if the reservation exists on that address else no store will be done. It also informs the programmer if the store was done or not.
The stwcx. instruction sets the CR0[EQ] bit if the store was successful and clears it if it failed. If the store is perfomed successfully, the reservation is cleared.

Atomically incrementing an integer

retry:    
    lwarx  r4, 0, r5   // Read integer from memory (whose address is stored in
                       // register r4) into r5, placing reservation on that 
                       // address                                         

    addi   r4, r4, 1   // Add 1 to r4.
    stwcx. r4, 0, r5   // Attempt to store incremented value back to memory.
    bne-   retry       // If the store failed (some other processor wrote at the 
                       // same address  
                       // in between due to which reservation was lost), retry.
                       // Reservation is cleared if the store is performed 
                       // successfully.

Similarly, any read-modify-write operation may be perfomed using lwarx/stwcx.

We will discuss on other concurrency problems and techniques to solve them later in the second part.

Till then enjoy and have fun ...