Computer-Science

File System

1. Goal

2. Several example file systems

3. EXT2 fs: default file system in Linux 2.4

1) files

2) inode table

3) IBM: Inode Bit Map

The use/free information of each inode. With 4K-byte block, 1 block can show the usage info of 4*1024*8 = 32768 inodes.

4) DBM: Data block Bit Map

The usage info of 32768 blocks.

5) Group descriptors

The location of inode bit map,data block bit map, inode table, etc. for each block group.

6) Super block

Overall information about this file system such as total number of inodes, total number of blocks, block size, etc.

data structures:

typedef struct  // super block
{
    u32 m_inodes_count;  // 0-3
    u32 m_blocks_count;  // 4-7
    u32 m_r_blocks_count; // 8-B
    u32 m_free_blocks_count; // C-F
    u32 m_free_inodes_count;  // 10-13
    u32 m_first_data_block;  // 14-17
                            // block location of superblock.
    u32 m_log_block_size;    // 18-1B. block size=1024*(2^(m_log⁡_block_size))
    u32 m_log_frag_size;     // 1C-1F
    u32 m_blocks_per_group;  // 20-23
    u32 m_frrags_per_group; // 24-27
    u32 m_inodes_per_group;  // 28-2B
    u32 m_mtime;  // 2C-2F
    u32 m_wtime;  // 30-33
    u16 m_mnt_count; // 34-35
    u16 m_max_mnt_count;  // 36-37
    u16 m_magic;  // 38-39
    u16 m_state;  // 3A-3B
    u16 m_errors;  // 3C-3D
    u16 m_minor_rev_level;  // 3E-3F
    u32 m_lastcheck;  // 40-43
    u32 m_checkinterval; // 44-47
    u32 m_creator_os;  // 48-4b
    u32 m_rev_level;  // 4c-4f
    u16 m_def_resuid;  // 50-51
    u16 m_def_resgid;  // 52-53
    u32 m_first_ino;  // 54-57
    u16 m_inode_size;  //58-59
    u16 m_block_group_nr;  //5a-5b
    u32 m_feature_compat;  //5c-5f
    u32 m_feature_incompat;  //60-63
    u32 m_feature_ro_compat;  //64-67
    u08 m_uuid[16]; //68-77
    char m_volume_name[16]; //78-87
    char m_last_mounted[64]; //88-c7
    u32 m_algorithm_usage_bitmap; //c8-cb
    u08 m_prealloc_blocks; //cc
    u08 m_prealloc_dir_blocks; //cd
    u16 m_padding; // ce-cf
    u08 m_journal_uuid[16]; // d0-df
    u32 m_journal_inum; // e0-e3
    u32 m_journal_dev; // e4-e7
    u32 m_last_orphan; // e8-eb
    u32 m_hash_seed[4]; // ec-fb
} SuperBlock;

typedef struct // group descriptor
{
    u32 m_block_bitmap;  // block location of DBM
    u32 m_inode_bitmap;  // block location of IBM
    u32 m_inode_table;   // block location of inode table
    u16 m_free_blocks_count;
    u16 m_free_inodes_count;
    u16 m_used_dir_count;
    u16 m_padding;
    u32 m_reserved[3];
} GroupDescriptor;

typedef struct  // inode
{
    u16 m_mode; // 0-1
    u16 m_uid;  // 2-3
    u32 m_size; // 4-7
    u32 m_atime; // 8-B
    u32 m_ctime; // C-F
    u32 m_mtime;  // 10-13
    u32 m_dtime; // 14-17
    u16 m_gid; // 18-19
    u16 m_links_count; // 1A-1B
    u32 m_blocks; // 1C-1F. shows num of data blocks for this file in units of 512 bytes
    u32 m_flags; // 20-23
    u32 m_reserved1; // 24-27
    u32 m_block[15];   // block location of this file
    u32 m_generation;
    u32 m_file_acl;
    u32 m_dir_acl;
    u32 m_faddr;
    u32 m_reserved2[3];
} Inode;

typedef struct // directory
{
    u32 m_inode;
    u16 m_rec_len;
    u08 m_name_len;
    u08 m_file_type;
    char m_name[255];
} DirectoryEntry;

4. Finding a file’s block location in ext2

5. Creating an ext2 fs in a floppy disk

$ mkfs  –t  ext2  /dev/fd0
# or
$ mke2fs  /dev/fd0

creates an ext2 file system in a floppy disk.

6. (homework) Read the disk and analyze the contents of the meta blocks.

1) Make a virtual floppy disk

$ dd bs=1024 count=1440 if=/dev/zero of=myfd

will make a virtual floppy disk of size 1.44MB with name “myfd”.

1-1) Check the content of myfd. What data do you have in it? Check address 0x400.

$ xxd myfd > x
$ vi x
/400

2) Format

$ mkfs -t ext2 myfd

will format myfd with ext2 file system.

2-1) Now what data do you have in myfd? First 4 byte at address 0x400 must be b8 00 00 00. What is the meaning of them? Who has written that data in myfd?

$ xxd myfd > x
$ vi x
/400

2-2) myfd is actually a simple file with EXT2 file system written in it. However, vi myfd will not show the content. Why is that? How can you see the content of myfd?

2-3) myfd is a virtual disk which means you can store a file in it as if it is a regular disk. You may think following will store two files (f1 and f2) in myfd disk. Explain why it is not working.

$ echo hello > f1
$ echo hello2 > f2
$ cp f1 myfd
$ cp f2 myfd
$ xxd myfd

3) Mount

To store a file in myfd, you have to connect the file tree in myfd to the system file tree via mounting. Regenerate myfd and do followings.

$ mkdir temp

We need an empty directory to mount myfd. If temp is already there, skip this step.

$ mount -o loop myfd temp

will connect myfd to temp directory, which is called mounting. Since myfd is not a physical disk but a file that contains a disk image, we need to use –o loop option. This command will connect myfd disk to /temp directory and you can access “myfd” disk via /temp.

4) Make some files in myfd

$ cd temp             --- go to myfd
$ ls                  --- check myfd is empty
$ echo korea > f1     --- make f1 in it
$ ls                  --- check f1

5) Analyze myfd

$ cd ..
$ umount temp

We need umount temp to write the change in the myfd disk.

$ xxd -g1 myfd > x

-g1 option will display each byte of myfd separately.

$ vi x

(if it doesn’t start at line 0, type :1 to go to line 1)

6) Read superblock. Superblock starts at offset 1024(400h) always. Find the superblock and read the total number of inodes in this disk (m_inodes_count), total number of blocks in this disk (m_blocks_count), the magic number (m_magic), block size (1024*2^(m_log⁡_block_size)), and the first data block number (m_first_data_block). Every multi-byte number is stored in little endian, and you have to reverse the byte order to compute the actual value.

7) Read the group descriptor and find the block number of DBM, IBM, and inode table.

8) Read the DBM, IBM, and find the inode numbers and block numbers in use. Draw the layout of myfd disk that shows the block location of all meta blocks: super block, group descriptor, IBM, DBM, and inode table.

8-1) Create another file f2 in myfd with vi. What changes can you observe in DBM and IBM? Guess what is the inode number for f2 and what is the block number assigned to it.

9) Read the inode table and find the block location of the root directory file. What is the byte size and block size of this file? Who is the owner of this file?

각각의 inode는 inode table에서 0x80(=128)bytes를 차지한다.

0x2800에 첫번째 inode가 위치하고, 0x2880에 두번째 inode가 위치한다.

root directory file은 inode 2번이므로 0x2880~0x28ff에 기록되어있다.

typedef struct  // inode
{
    ... ......
    u16 m_uid;  // 2-3
    u32 m_size; // 4-7
    ... ......
    u32 m_block[15];   // 28-2C block location of this file
    ... ......
} Inode;

inode struct에 따르면 파일의 block 위치를 나타내는 m_block은 [28-2C]에 위치한다.

해당 위치에 0x21이 기록된 것을 확인할 수 있다. 따라서 root directory의 file 위치는 0x21 * 0x400 = 0x8400이다.

또한, m_size를 통해 byte size가 0x400 = 1024 bytes이고, m_blcoks를 통해 block size가 0x2 (512 bytes) = 1024 bytes임을 알 수 있다.

이 파일의 소유자는 uid field에 기록되며 0이다. uid 0은 root 사용자를 의미한다.

10) Read the root directory file. How many member files it has? What are the inode numbers and file names of them? Go to the inode table and find the block location of each member file.

root directory file의 시작 위치는 0x8400이다.

typedef struct // directory
{
    u32 m_inode;
    u16 m_rec_len;
    u08 m_name_len;
    u08 m_file_type;
    char m_name[255];
} DirectoryEntry;

총 4개의 파일이 존재한다.

lost+found의 inode table

lost+found의 block location은 0x22 * 0x400 = 0x8800 이다.

f1의 inode table

f1의 block location은 0x2f * 0x400 = 0xbc00 이다.

11) Read the member files and confirm the contents.

lost+found directory file

lost+found의 directory file 내부에는 .과 ..파일이 있다. .파일은 inode 번호가 11인 자신을 나타내고 ..파일은 2번 root directory file을 의미한다.

f1 directory file

f1은 file type 번호가 1인 regular file로 f1의 data, ‘korea’가 기록되어있다.

12) You can see all files including hidden ones with ls -a. Confirm you can see all files you found in the file system with this command.

$ ls  -a

숨겨진 파일(., ..)을 포함한 현재 디렉터리의 모든 파일이 출력된다.

13) You can see the inode number of a file with ls -i. Confirm the inode numbers of all files.

$ ls  -ai

각 파일명 왼쪽에 inode 번호가 같이 출력된다.

14) Make another file in your virtual disk. Confirm the changes in the file system: IBM, DBM, Inode table, and root directory file. Now delete this file (with rm command). What happens to the file system? How can you recover this file?

$ mkdir temp
$ mount -o loop myfd temp  # virtual disk(myfd)와 temp 디렉토리 연결
$ echo hello > f3
$ ls
f1  f3  lost+found
$ cd ..
$ umount temp              # 연결 해제
$ xxd -g1 myfd > hw14      # 내용 추출
$ vi hw14

14-1) Make a new directory (d7) in the root directory (of myfd) with mkdir command. Show the disk block content of the root directory file and find out the inode number of d7.

14-2) Show the inode content of d7. What is the block location of d7? Show the block content of d7. What files do you have in d7?

14-3) Run mv f1 d7/f2 and show the changes in the root directory file, d7 file, and inode table.

15) Examine the file system in the hard disk (/dev/sda3) and find file names in the root directory.

$ dd bs=1024 count=8000 if=/dev/sda3 of=myhd
$ xxd –g1 myhd > x
$ vi x

16) Write a program that opens a disk device formatted with EXT2 and reads and displays the super block, group descriptor, ibm, dbm, and inode table. Also display the file names in the root directory file, their inode numbers, and their block locations. Use open(), lseek(), read(), etc.

         struct superblock{
             int  total_inode_num;
             int  total_block_num;
             .........
         };
         int x; char buf[1024]; struct superblock *sb;
         x=open("myfd", O_RDONLY, 00777); //open a virtual disk
         lseek(x, 1024, SEEK_SET); // move the file pointer to offset 1024 where the
                                    // superblock starts
         read(x, buf, 1024); // read the superblock into buf
         sb=(struct superblock *)buf; // interpret the data in buf as "struct superblock"
         printf("total inode num:%x, total_block_num:%x, ...",
               sb->total_inode_num, sb->total_block_num, ....);
This site is open source. Improve this page.