Introduction to Operating System

Lab5: filesystem ext2

Lab Overview

ext2 was the official filesystem of Linux when it was still in its infancy (the early to mid nineties). Most Linux systems now use ext3 or another advanced filesystem. ext2 was phased out because it had reliability problems (if the power went out) and was inefficient when dealing with massive files or directories. However, ext2 is appropriate for teaching.

In this lab, you'll be asked to extend or implement functions in some provided C files, and have a closer observation with the filesystem concepts.


1. USB working with a Virtual Machine

The first part of this lab will be to create an ext2 filesystem on a USB stick. Hopefully, everyone has a free USB available!

How to make a USB work with your virtual machine can be referenced here: USB work with virutal machine

Usually,when used on windows, USB devices are formatted with one of FAT filesystems. So, you're going to have to format the USB drive as an ext2 device.

To Linux, your USB drive looks like a hard drive. When you insert it, chances are it will automatically be mounted and associated with a SCSI drive device (/dev/sda1, usually). So, you can treat your USB drive as a tiny harddrive. So, you can assume that the sectors on the drive are ordered and can therefore treat it as a sequence of addressable bytes. The two low-level commands you will be using in this lab are seek, which moves the read/write head to a location on the drive, and read which reads in a number of bytes from the location on the drive you just seeked to. Because seek is interested in moving around the read/write head of a drive, it is concerned with offsets. That is, the number of bytes from the beginning of the drive to the desired location. Some of the questions in this lab are all about translating from block number to byte offset, to get you used to this (sometimes tricky) scheme.

2.creating an ext2 filesystem

A USB comes formatted for Windows. That means that it uses the vfat filesystem, which is simpler and less capable than ext2. Our first step will be to replace the vfat format with ext2. (Note: if for some reason the stick came without formatting, we could create a formatted partition on it using fdisk. )

Creating the ext2 file system is simple using the mke2fs command. However, we first have to make sure that the vfat drive is not mounted (connected to the file system directory tree). Modern Linux systems automatically detect insertion of a memory stick and mount it for you. We can see the devices currently mounted using the mount command. The result should look somewhat like the following:

/dev/hda5 on / type ext3 (rw,noatime)
none on /proc type proc (rw)
none on /proc/bus/usb type usbfs (rw)
none on /sys type sysfs (rw)
/dev/hda7 on /boot type ext3 (rw,noatime)
/dev/hda1 on /mnt/windows type ntfs (ro,umask=0022,nls=iso8859-1)
Notice: The above lines can be different from your machine!

The memory stick should be the first (and only) SCSI drive, referred to by Unix as /dev/sda. (Additional SCSI drives would be named /dev/sdb, /dev/sdc, etc. The floppy drive is /dev/fd0.) If you see a reference to /dev/sda1, that means that the memory stick has already been mounted, probably at /media/disk. To unmount it, use umount. You may then proceed with the ext2 format, using mke2fs. Finally, remount the device and change the permissions on it to be writable by anyone.

These steps are summarized below.
[lab3]$ sudo /sbin/mke2fs /dev/sdb1
[sudo] password:
mke2fs 1.41.13 (13-Mar-2008)
Filesystem label=
OS type: Linux
Block size=1024 (log=0)
Fragment size=1024 (log=0)
31360 inodes, 125296 blocks
6264 blocks (5.00%) reserved for the super user
First data block=1
Maximum filesystem blocks=67371008
16 block groups
8192 blocks per group, 8192 fragments per group
1960 inodes per group
Superblock backups stored on blocks:
8193, 24577, 40961, 57345, 73729
Writing inode tables: done
Writing superblocks and filesystem accounting information: done
This filesystem will be automatically checked every 23 mounts or
180 days, whichever comes first. Use tune2fs -c or -i to override.
Notice: The above lines are also different from your machine!

3.ext2 file structure

The following picture illustrates the basic structure of the ext2 filesystem:

ext2 layout

The first 1024 bytes of a volume are the boot block. This area is reserved for partition boot sectors and aren't used by ext2. The rest of the disk is divided into block groups. Small devices, like floppies, contain only 1 block group. But your USB drive should have several (16 or so).All of the structures we¡¯ll be discussing are defined in the linux/ext2.h header file, which is available on your linux boxes under /usr/include/linux/ext2.h.

4. Superblock

The superblock contains all the pertinent global information for the entire drive. Information such as: the total number of blocks on disk, the size of the blocks, the number of free blocks, and so forth. The structure of the superblock is described by struct ext2 super block (which occurs around line 315 of the ext2.h header file). Some of the more pertinent fields have been extracted below:

struct ext2_super_block {
__le32 s_inodes_count; 			/* Inodes count */
__le32 s_blocks_count; 			/* Blocks count */
__le32 s_r_blocks_count;		/* Reserved blocks count */
__le32 s_free_blocks_count; 		/* Free blocks count */
__le32 s_free_inodes_count; 		/* Free inodes count */
__le32 s_first_data_block; 		/* First Data Block */
__le32 s_log_block_size; 		/* Block size */
__le32 s_blocks_per_group; 		/* # Blocks per group */
__le32 s_inodes_per_group; 		/* # Inodes per group */

__le16 s_magic; 			/* Magic signature */
__le32 s_first_ino; 			/* First non-reserved inode */
__le16 s_inode_size; 			/* size of inode structure */

The le32 and le16 datatypes specify little-endian 32-bit and 16-bit integers (unsigned).Because Linux is cross-platform, more expressive type names are used rather than just plain old int. But you can still cast these values to an int and use them like you'd expect. s inodes count and s blocks count contain the total number of inodes and blocks on the disk, respectively.

As stated by mke2fs, the block size is 1024 (can be different) bytes. If you multiply the block size by the number of blocks, you get the total disk capacity.In the superblock, block size is contained in s log block size. This value expresses block size as a power of two and using 1024 as the unit. This means that an s log block size value of 0 means 1024 byte blocks, a value of 1 means 2048 byte blocks, etc. If you need to calculate the block size in bytes from this value, you should use the following code:
unsigned int block_size = 1024 << super.s_log_block_size;

The superblock also tells us how many blocks are in a block group. This value is contained in the s blocks per group field. Going back to the mke2fs output, we see that the block group size is 8192. Now you can see that on a floppy (capacity 1.44 MB), only one block group would fit. But on our memory sticks, there¡¯s room for multiple blocks.

Q:Extend the code in the file opensuper.c to print out the superblock. Implement the print super block function to print out: the inodes count, blocks count, free blocks count, free inodes count, the first data block, block size, blocks per group, inodes per group, and the size of the inode structure. The output should be"<field>\t:<value>\n".

5. Group Descriptor

Group Descriptors The blocks immediately after the superblock contain a list of group descriptors (essentially an array of group descriptors). This list contains a descriptor for each block group. For a disk with multiple block groups, we have to calculate the size of this list from information in the superblock,specifically s blocks count and s blocks per group. We calculate it like so:
/* calculate number of block groups on the disk */
unsigned int group_count =
1 + (super.s_blocks_count-1) / super.s_blocks_per_group;
/* calculate size of the group descriptor list in bytes */
unsigned int descr_list_size =
group_count * sizeof(struct ext2_group_descr);
The group descriptor structure is called ext2 group descr and is located around line 106 of the ext2 header file. To reproduced it as below:
struct ext2_group_desc
__le32 bg_block_bitmap;			 /* Blocks bitmap block */
__le32 bg_inode_bitmap; 		 /* Inodes bitmap block */
__le32 bg_inode_table; 			 /* Inodes table block */
__le16 bg_free_blocks_count; 		 /* Free blocks count */
__le16 bg_free_inodes_count; 		 /* Free inodes count */
__le16 bg_used_dirs_count; 		 /* Directories count */
__le16 bg_pad;
__le32 bg_reserved[3];

To read in the group descriptors, you first have to calculate the offset from the beginning of the disk. The first 1024 bytes are reserved and the first block is occupied by the superblock, so the code to read the first group descriptor off the disk looks like:

struct ext2_group_descr group_descr;
/* position head above the group descriptor block */
lseek(sd, 1024 + block_size, SEEK_SET);
read(sd, &group_descr, sizeof(group_descr));

The group descriptor tells us the location of the block/inode bitmaps and of the inode table (described later) through the bg block bitmap, bg inode bitmap and bg inode table fields. These values indicate the blocks where the bitmaps and the table are located. It is handy to have a function to convert a block number to an offset on disk, which can be easily done by knowing that all blocks on disk have the same size of block size bytes (calculated earlier from the super-block):

/* location of the super-block in the first group */
#define BASE_OFFSET 1024
#define BLOCK_OFFSET(block) (BASE_OFFSET + (block-1)*block_size)
Q:Extend the code contained in opengroup.c by implementing the print group desc.Print out: blocks bitmap block, inodes bitmap block, inodes table block, free blocks count,free inodes count, and the directories count.

Helpful Documents

Student Feedbacks

If you have any advice and sugguestions about the lab or the course design, please let me know.:)