Shulou(Shulou.com)06/01 Report--

What are the basic knowledge points of ext3 file system? I believe many inexperienced people are at a loss about this. Therefore, this paper summarizes the causes and solutions of the problem. Through this article, I hope you can solve this problem.

The composition of the file system

Boot blocks: storing boot cod

Super block: single block size / total number of blocks; number of blocks per group; number of I nodes / number of I nodes per group; volume name; last write time / mount time / mount path; idle I node / block information (used when allocating new I nodes / blocks)

Group descriptor table: 32 bytes each, describing each block bitmap / I node bitmap / I node table starting block number, number of free blocks and directories in the block group; all blocks in the file system are equally divided into several block groups, and the last one may be slightly smaller

Block bitmap: occupies 1 data block

I-node bitmap: occupies 1 data block and is usually inexhaustible

I node table: stores each 128byte under inode,ext3, including 12 direct block pointers / 1 level 1 indirect fast pointer / 1 level 2 indirect block pointer / 1 level 3 block pointer

Data area: storing file data

For file systems with sparse superblock characteristics, only the super block and block group descriptors are backed up in the block group whose group number is the power of 3-5-7, otherwise each block group has a backup

Catalogue

Directory is also a kind of file. Except for inode, each directory owns at least 1 data block and stores the list of files under it in the form of directory entries.

The storage contents include: ASCII code of file name / name length / item length of this directory / I node number / file type

Directory entry length = max ((8-byte fixed + file name), 4roomn), for file file.txt, its length is 16

Hard connection: essentially a different directory entry pointing to the same inode

-- assume that the number of inode per block group is 2008

Create a file

To create the file.txt file under / dir1, follow these steps:

1 read the super block (fixed location) to get the basic information of the file system (block size / number of inode per group); read the group descriptor table (fixed location) to learn about the layout of each block group

2 read the root directory and find dir1 and its inode from its directory entry

-its inode is 2 (fixed, located in block 0 group), while the inode table starts with block 5, and reads block 5 to access the second inode. Its block pointer shows that the directory block number of the root directory is 256.

-- read block 256and traverse its directory entry until it finds the directory entry of dir1 and shows that its inode number is 4724. Update the last access time of the root directory

3 create a directory entry for file.txt

-- the integer division operation int of dir1's inode number determines that it is located in block 2, and the rest is the inode item number. according to the table item of group 2 descriptor, it is known that the I node table starts at 16387.

-- read the block, get its table item No. 708, and show that the dir1 directory block number is 17216.

-- read 17216 blocks to find free space. The new file file.txt name is 7 characters long and requires 16 bytes of space.

Create a directory entry, update the last modification time and the last change time of the directory, and record the changes in the log

4 create inode

-- give priority to creating the same block group in the parent directory, that is, group 2

-- read the I-node bitmap of block 2 at block 16386, get the unassigned I-node number 4850, set its corresponding bit to 1, and subtract 1 from the number of free inode in the super block / group descriptor table.

-- add the inode address to the directory entry created in the previous step

-- initialize inode 4850

5 allocate data blocks

File.txt needs 6 data blocks. Look at the block bitmap of block group 2, find out 6 free blocks in this block group and set the corresponding bit to 1, and assign these blocks to the direct block pointer of inode 4850.

Update the number of free blocks in the super block / group descriptor, update the last modification time and change time of the inode

6 write data

Write file.txt content to the newly allocated block

Delete a file

1 read the super block & group descriptor table

2 get the inode of dir1

-- the root directory inode number is 2 (in block 0), and the I node table starts at block 5 (group descriptor table). Read the I node table from block 5 and access the second table item.

Learn from the direct block pointer of inode that the directory block of the root directory is the 256th block.

Read block 256and traverse the directory entry until you find the dir1 record, whose I node number is 4724

-- update the last access time of the root directory

3 obtain the inode of file.txt and recycle the catalog entry

-- the I node number of dir1 is 4724, the rounding operation int (4724) = 2, which is located in block 2, while the I node descriptor of group 2 starts with block 16387 (group descriptor table).

If you read item 708 from 16387 block, inode,inode shows that the dir1 directory block number is 17216.

Read the traversal catalog entry in block 17216 until you find the file.txt match and get its I node number 4850

Cancel the directory entry, and the length value of the previous item points directly to the beginning of the next item

4 reclaim the data blocks of file.txt

-- get the 4850 I node item from the I node table of group 2, subtract the number of links by 1, and reclaim the inode if the number of links is 0 (the corresponding bit is set to 0)

-- the block bitmap bit of the corresponding 6 blocks is set to 0

Note: please refer to "data Reproduction" edited by Ma Lin.

Frequently asked questions:

1 Why does df show that the disk is full but du shows that there is free space?

A process was opening when the file was deleted, so the actual space was not released.

When deleting or truncate an inode, first add the inode to the orphan inode one-way chain header. The super block structure has the corresponding field s_last_orphan pointing to the linked list.

If the system crashes during execution, the next time the file system is loaded, the linked list is checked and the delete or truncate operation continues.

The following is the normal procedure for ext4 to delete inode

-> do_unlinkat

-> vfs_unlink

-> ext4_unlink

-- > ext4_delete_entry deletes the file from the directory where the file is located

-> ext4_orphan_add

-> iput

-> iput_final

-> generic_drop_inode

-- > generic_delete_inode (inode)

-> ext4_delete_inode

-- > ext4_truncate clears index information on disk

-> ext4_orphan_del

-- > ext4_free_inode removes the inode from memory and disk, respectively

Http://blogimg.chinaunix.net/blog/upfile2/101008204403.pdf

Ext3 uses indirect block mapping. When the file is large, the mapping table will be very expensive, and the block pointer in the inode will be cleared when the file is deleted.

When extent is introduced into Ext4, the number of metadata blocks is reduced, and the overhead of unlink/truncate is greatly reduced. Each extent structure is 12 bytes, and each inode can store up to 4.

Most files only need some extent to describe logical-to-physical block mapping, but extent map is not so efficient for files that are sparse or fragmented.

To solve this problem, it is necessary to use the improved block allocator of ext4 to store small files next to each other and allocate contiguous areas for large files as far as possible.

Http://ols.fedoraproject.org/OLS/Reprints-2008/kumar-reprint.pdf

2 how to allocate block / inode/ directory entries

Allocation block

Priority is given to the block group to which the inode belongs.

Assign inode

File: first created in the group of its parent directory; directory: first created in the group with more free space

Assign a directory entry

Traverse the directory entries in the directory from front to back, calculate the required length of each directory entry according to the length of the file name, and compare it with the actual length value. If it is inconsistent, it means that it is either the last item or spans several deleted directory entries, then try to assign a new directory entry here; if there is not enough space in the current block, suspend the file name and assign a new block. Linux does not allow directory entries to span blocks.

After reading the above, have you mastered the basic knowledge of ext3 file system? If you want to learn more skills or want to know more about it, you are welcome to follow the industry information channel, thank you for reading!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.