CENG Take Home Exam 3 Filesystems Solution

    • Objectives

The goal of the assignment is to familiarize you with lesystem structures. Towards this end, you will write a program that can read a regular le and copy its content as a new le into an ext2 image (a le containing the contents and structure of a disk volume or an entire data storage device), without mounting it.


    • ext2  lesystem

The structure of the ext2 lesystem, shown in Figure 1, is as follows; The rst 1024 bytes of the disk is reserved as a boot block. This block is followed by a number of block/block groups. Each block group starts with its super block, followed by group descriptors. The blocks bitmap and inodes bitmap structures store information about free/allocated blocks and free/allocated inodes in the group. Each bitmap structure takes 1 block and hence the block and inode bitmaps occupy 2 blocks. The inode table, size of which depends on the number of inodes created during the formatting process, is stored in subsequent blocks. The remaining blocks within the group are used as data blocks.












Figure 1: ext2    lesystem structure.







1

Here we provide some conventions about the ext2    lesystem, to ease your introduction:

Block numbering starts from 1 (not zero!).

Block numbering starts at the beginning of the disk.

The super block of the rst group (namely Block/block group 0 in Figure 1) resides in block 1. inode numbering starts from 1 (not zero!).

The root directory inode always resides in inode number 2. The rst 11 inodes are reserved.

There is always a lost+ nd directory in the root directory.

The total number of data and inode blocks and number of inode and data blocks in each block group are de ned in superblock.

The super block structure is de ned as follows in the Linux kernel:

s t r u c t  ext2_super_block
f
/
I n o d e s  count   /





__le32
s_inodes_count ;







__le32
s_blocks_count ;
/
B l o c k s  count   /


/


__le32
s_r_blocks_count ;
/
Reserved
b l o c k s
count



__le32
s_free_blocks_count ;

/
Free
b l o c k s
count
/


__le32
s_free_inodes_count ;

/
Free
i n o d e s  count   /


__le32
s_first_data_block ;
/
F i r s t

Data
Block   /



__le32
s_log_block_size ;
/
Block

s i z e
/





__le32
s_log_frag_size ;
/
Fragment
s i z e   /




__le32
s_blocks_per_group ;
/  # B l o c k s
p e r  group   /
/


__le32
s_frags_per_group ;
/  # Fragments
p e r
group



__le32
s_inodes_per_group ;
/  # I n o d e s  p e r  group   /



__le32
s_mtime ;
/
Mount
time
/






__le32
s_wtime ;
/
Write
time
/






__le16
s_mnt_count ;

/  Mount  count   /





__le16
s_max_mnt_count ;
/   Maximal mount  count   /


__le16
s_magic ;
/
Magic
s i g n a t u r e
/





__le16
s_state ;
/
F i l e

system
s t a t e   /

e r r o r s   /

__le16
s_errors ;
/
Behaviour

when
d e t e c t i n g


__le16
s_minor_rev_level ;
/
minor

r e v i s i o n
l e v e l
/


__le32
s_lastcheck ;

/
time

o f
l a s t  check
/

/

__le32
s_checkinterval ;
/
max .

time  between
c h e c k s


__le32
s_creator_os ;
/OS/




/




__le32
s_rev_level ;

/
R e v i s i o n
l e v e l




/
__le16
s_def_resuid ;
/
D e f a u l t
u i d
f o r
r e s e r v e d
b l o c k s

__le16
s_def_resgid ;
/
D e f a u l t
g i d
f o r
r e s e r v e d
b l o c k s
/
__le32
s_first_ino ;

/
F i r s t

non  r e s e r v e d
i n o d e
/

__le16
s_inode_size ;
/
s i z e

o f
i n o d e  s t r u c t u r e
/

/    t h e r e    a r e    o t h e r    i r r e l e v a n t    f i e l d s    /

    • ;

where    le32 is 32 bit unsigned integer and    le16 is 16 bit unsigned integer.


Note that;

s blocks count is the total number of blocks in the image s inodes count is the total number of inodes in the image 2s log block size+10 is the block size. A typical value is 1024.


2

s inode size is the size of an inode structure. A typical value is 128.



The number of block groups can be calculated as ceiling of
s blocks count


s blocks per group


inode’s are numbered globally across the whole volume (or image) as opposed to within the block group.


The block group in which an inode resides can be computed using the j

(inode  1)
k formula.


s inodes per group


Within the inode table of a block group (table address is given in group descriptor table entry), a modulo operation determines the index of the inode.

The size of an inode is smaller than the size of a block, hence the lookup process should take the inode size into account.

Data block addresses in inode structure are absolute block addresses of the  lesystem image.

j
The block group containing a data block can be calculated as

blockaddr

s blocks per group

k
. Remainder of this

division gives index of the data block within the block group, which is used in locating its index in block allocation table.

Each block group may contain a superblock backup copy, group descriptor table backup copy. Groups 0, 1 and groups that are powers of 3, 5, or 7 contains these copies. The others directly start with the bitmap data. As a result, the o set of inode and data block bitmaps are not xed. You need to read group descriptor table for o set of bitmap blocks and inode table.


The group descriptor table blocks, which comes after each super block copy, describes the structure of each block group:

s t r u c t  group_descriptor  f

/

b l o c k   /
__le32
bg_block_bitmap ;


B l o c k s  bitmap

__le32
bg_inode_bitmap ;
/
/
I n o d e s  bitmap
b l o c k   /
__le32
bg_inode_table ;

I n o d e s  t a b l e  b l o c k
/
/
__le16
bg_free_blocks_count ;
/
Free  b l o c k s  count

__le16
bg_free_inodes_count ;
/
Free  i n o d e s  count
/
__le16
bg_used_dirs_count ;  /
D i r e c t o r i e s  count
/

__le16   bg_pad ;





__le32
bg_reserved [ 3 ] ;






    • group_descriptors [ NGROUPS ] ;

In the table, there is an entry for each group, which contains the absolute block addresses of data blocks bitmap, inodes bitmap, and inodes table. The number of blocks that the blocks/inodes bitmap occupy can be computed by dividing the number of blocks/inodes by 8 (i.e number of bits in a byte) rounded up to the block size. For instance, one 1024 byte block is su cient for the blocks bitmap to store the free/allocated information about 8192 blocks.

An inode table has the following structure:

s t r u c t  ext2_inode  f
/

mode  /


__le16   i_mode ;

F i l e


Owner Uid   /
__le16   i_uid ;
/
Low
16  b i t s
o f

__le32   i_size ;
/
S i z e
i n  b y t e s
/
__le32   i_atime ;
/
A c c e s s  time   /

__le32   i_ctime ;
/
C r e a t i o n  time   /
__le32   i_mtime ;
/
M o d i f i c a t i o n
time   /
__le32   i_dtime ;
/
D e l e t i o n  Time
/

3

__le16
i_gid ;
/
Low
16  b i t s
o f
Group  Id
/
__le16
i_links_count ;
/
L i n k s  count   /


__le32
i_blocks ;
/
B l o c k s  count   /


__le32
i_flags ;
/
F i l e
f l a g s
/


/
__le32
i_reserved ;
/
OS
dependent
r e s e r v e d

__le32
i_block [ 1 2 ] ; /
P o i n t e r s
t o
b l o c k s
/

__le32   i_ind_block ;








__le32   i_dind_block ;







__le32
i_tind_block ;





/

/   r e s t
i s  i r r e l e v a n t ,
pad
i t  t o
128
b y t e s


    • inode_table [ N_INODES_PER_BLOCK ] ;

A directory is represented as a le and hence has a corresponding inode which contains direct/indirect pointers to its data blocks. The data blocks of a directory stores directory entry structures as follows:

struct  ext2_dir_entry  f
/

number   /
__le32
inode ;

Inode

__le16
rec_len ;
/
Directory  entry  l e n g t h   /
__le16   name_len ;
/
Name
l e n g t h
/
char
name [ ] ;
/
File
name ,
up  to  EXT2_NAME_LEN   /
g;





where rec len is the length of the whole entry and name len is the length of the le name string. rec len is usually rounded up to 4 bytes word.


The data blocks of a directory contains all les (note that directories are also les) under this directory as sequence of these directory entries. A new le entry can be created after the last directory entry, which can be found after a sequential search.

More information about the ext2    le system can be found in the following links:

http://www.nongnu.org/ext2-doc/ext2.html: ext2 documentation.

https://wiki.osdev.org/Ext2: The OSDev wiki page on ext2

Also http://web.mit.edu/tytso/www/linux/ext2intro.html: A page by Dave Poirer containing more details.

2.1    Details

You can create a disk image with 128 blocks of size 1024 with the following command:

$  dd    i f =/dev /zero  of=image . img  bs=1024  count=128

The disk image can then be formatted with mke2fs. The following commands format the disk and force the creation of 32 inodes.

        ◦ mke2fs   N  32  image . img

You can mount the image (for veri cation purposes only) by creating a loopback device by:

$  mkdir  mnt
$  sudo  mount    o  loop  image . img  mnt

and unmount with:

        ◦ umount  mnt

On computers where you do not have administrative privileges (such as the ones in the lab), you can use FUSE based fuseext2 to mount your image to a folder you own as:


4

$  fuseext2    o  rw + image . img  mnt

and unmount with:

        ◦ fusermount   u  mnt

dumpe2fs tool can be used to inspect structure of  lesystem.

You are expected to copy only regular les into the ext2 image. Your implementation should support di erent block sizes, di erent number of inodes and di erent number of blocks in the image. Copying of les other than regular les is not required.

You can inspect di erences between two image les using a xxd hex dump and diff. For instance, you can use the following command to inspect the di erences between two images:

$  diff  <(xxd  image1 . img )  <(xxd  image2 . img ) > images . diff

2.2    Implementation, Compilation & Execution Details

Any standard library can be used in your code. However, the use of libraries with ext2 implemen-tation is forbidden!

You have to provide a make le with your implementation which creates an executable named filecopy.

Your code will be tested using the command:

$  . / filecopy  imagefile  sourcefile  targetdirpath j targetdirinode

which should result in copying the regular le sourcefile into the ext2 image le imagefile. The le should be created with same name under the targetdirpath directory of the ext2 image. targetdirpath will be an absolute path. If it does not start with ‘/’, it should be assumed relative to ‘/’, root of the ext2 image. Instead of a directory path, the target can be given as location of an inode block, which is the inode for a directory.

The steps of your task are:

Open the ext2 image  le.

If targetdirpath is given, traverse the path and get the directory data blocks. If targetdirinode is given get the inode and get the directory data blocks.

Allocate a new inode,  ll in metadata from metadata of sourcefile (see man 2 stat).

Allocate data blocks for the new le. For simplicity, assume that the le data will t only in direct blocks of the inode. if it is larger, it is truncated to direct data block addressing.

Set data blocks of the inode of the created  le.

Insert an entry in data blocks of the directory for the le mapping le name into le inode. Close the image le.

After these steps, the copied    le should be visible in the given path of the ext2 image.

You will be given a valid and non corrupted ext2 image le. However note that it does not have to be empty and may already contain les in it. Your code will be tested multiple times with di erent les and images successively. When copying a le, you are expected to print the inode number of the le that you created and its corresponding data blocks, such as:


5

    • . / filecopy imagefile file targetdirectory 12 8 ,9 ,10 ,11



    • Restrictions, Grading and Warnings

Your implementation should be in C/C++. The submissions should be done via COW.

Create a tar.gz le named hw3.tar.gz that contains all your source code les and a make le. The executable should be named filecopy.
The following sequence of commands should compile and execute your code.

    • tar   xf  hw3 . tar . gz

    • make  all

$ . / filecopy imagefile sourcefile targetdirectory $ . / filecopy imagefile sourcefile targetinode

Your codes will be evaluated through a black-box approach and have to compile and run on lab. machines.

After your code runs, the target image lesystem check should not produce any integrity errors. The minimal implementation for getting partial points from this homework is the correct imple-

mentation of:

filecopy imagefile sourcefile targetinode. which is worth 60 points.

If sourcefile is directory, and recursive copy of the directory is implemented, a 15 point bonus will be granted.

If les larger than 12 direct blocks is supported (up to triple indirect) a 15 point bonus will be granted.

Please ask your questions related to the homework on piazza only so that the discussions become public and would bene t you all.

Cheating: We have zero tolerance policy for cheating. Sharing part or whole of your code with other students, or copying code from other sources on the internet will be considered as cheating, and disciplinary action will be taken against.


















6