HongMeng kernel source code analysis (file system) | | said in books management file system best blog analysis OpenHarmony source | v63.01

Sima Niu was worried, saying, “Every man has his brother. I die alone.” Zi Xia said, “It is true that death and life have life, and wealth and honour are in heaven. A gentleman respects without loss, and is courteous and courteous to others. Within the four seas, all are brothers. Why does a gentleman have no brothers?” The Analects of Confucius: Yan Yuan

A hundred blog series. This is:

V63. Xx HongMeng kernel source code analysis (file system) | said in books management file system

File system related sections are as follows:

• V62. Xx HongMeng kernel source code analysis concept (file) | why everything is the file
• V63. Xx HongMeng kernel source code analysis (file system) | said in books management file system
• V64. Xx HongMeng kernel source code analysis (inode) | who is the most important concept of file system
• V65. Xx HongMeng kernel source code analysis (mount directory) | why need to mount the file system
• V66. Xx HongMeng kernel source code analysis (the root file system) | on first/File system on
• V67. Xx HongMeng kernel source code analysis (character device) | bytes read/write device for the unit
• V68. Xx HongMeng kernel source code analysis file system (VFS) | the foundation of the harmonious coexistence
• V69. Xx HongMeng kernel source code analysis (file handle) | why do you call a handle?
• V70. Xx HongMeng kernel source code analysis (pipe file) | how to reduce the data flow cost

This paper describes the management scheme of a large library and explains how the computer file system is managed. If you understand this scenario, you have a basic understanding of how the lowest level of the file system works.

How to Build a Library

Suppose you are given a site of 100*100 meters and 10 meters high to build a library and place the world’s book archives, there are the following operating requirements:

• Books range from large to small, from the Encyclopaedia Britannica, estimated to be millions of pages long, to a single thin page of a telegram.
• Books were not given all at once, but were added, revised and deleted. For example, the first 24 books were not only 12, but they were gradually replaced.
• The scale of the book is in the tens of millions. Books must be found in the shortest possible time, and new ones must be found somewhere to put them.
• Keep a record of every action taken on the book, such as when it was put in storage, when it was modified, and when it was borrowed.
• Permission verification, different people have different permission to the book, for example, some people can doodle in the book, but some people can only read.
• The library must be safe. The whole library cannot operate normally because of a partial fire.
• You can store catalog information, and everyone can create their own catalog of books, requiring that catalog information be saved as well.
• Make it easy to check out books, return books, and get catalog information, and everyone just uses the bar code.

How would you design this library? And make it run safely and efficiently.

Small easy’s solution

A young man named Yi came up with a solution:

• The whole warehouse to build the same size of the grid, this grid unified called cell. Whatever it is, it ends up in a grid. What if each grid pressed0.25 * 0.25 * 0.25Meters, the entire site can be built into 6.4 million units. Cells have unique and uniform numbers. from0Has been in the6.4 million - 1.
• Because there are too many cells and management is very complicated, the site is divided into big A area, big B area and big C area,….. N-block, for example, divided into 8 blocks, each allocated 800,000 cells. Large A area code [0-799999],… And so on.
• Each area is divided into statistical area, directory area, book area.
  • The statistics area is the information data that describes the entire library and each partition, occupying 1000 cells
  • The catalogue area is the information generated to manage the book area, comprising 19,000 cells and divided into three blocks:
    • Index table block (18900 cells): Xiaoyi stipulates that a page will be used to record the index information of the book, and this page is called the index page, and the index page is bound into an index table book, which has a continuous uniform page number (also called the bar code). A book with millions of pages, such as the Encyclopaedia Britannica, no matter how many subsequent cells it occupies in the library area, is a piece of paper in the index table book, which has a fixed format and records the title of the book, permissions, revision dates and so on.
    • Index page bitmap block (10 cells): Record the use of index pages,0 | 1On behalf ofUnused | have been used.
    • Book area cell bitmap block (: 90 cells): record the use of book area cells,0 | 1On behalf ofUnused | have been used.
  • The book area is really to manage the books, according to the capacity of cells to put, larger books will be divided into multiple cells to store. That’s 780,000 cells.

  The above information can be simplified into a tree diagram as follows:

  └ ─ library = > 6.4 million cells, the average is divided into eight big theater ├ ─ big area A = > 800000 cell │ ├ ─ e-book exchange = > 780000 cell │ ├ ─ directory = > 19000 cell │ │ ├ ─ the e-book exchange unit cells for the tiles = > 90 cell │ │ ├ ─ index table block = > 18900 cell │ │ │ ├ ─ A file index pages = > information registration, account for A sheet of paper, describe the name of A book, authority, time = = │ │ │ ├ ─... │ │ │ └ ─ directory index page B │ │ └ ─ bitmap index page block = > 10 cell │ └ ─ statistical area (1000) = > record library and global information of each partition using high frequency └ ─ big B area ├ ─ e-book exchange ├ ─ directory │ ├ ─ the e-book exchange unit cells for the tiles │ ├ ─ │ index table block │ ├─A File Index page │ ├─... │ ├ ─ ├ ─ ├ ─ ├ ─ ├ ─ ├ ─ ├ ─ ├ ─ └...Copy the code

It is important to understand these conceptual relationships and form a brain map in your mind, which is the most critical underlying logic for understanding how the entire file system works and is managed. These concepts are explained in detail below.

The cell

Because the demand is that there is no limit to the size of books, there are huge differences, some books to tens of millions of pages, some small to only one page. It’s an open question. It’s a choice between space and time. If you don’t want to waste time, you have to waste space. Without boundaries, it is not convenient to do special treatment, which requires standardized unified management. How to standardize? The answer is: the same grid can be large or small, but it must be the same size. Small easy to build 0.25*0.25*0.25 meters of standard grid, can put 1000 pages (1K pages) of the book, all books are unified according to the number of pages, put 1000 pages on the remaining grid. The relation between a grid and a book is (N:1), that is, a book can be divided into multiple grids, but two different books cannot be placed in one grid. Yes, there is waste, but waste is waste. The performance is as follows:

• If a book has only one page, it will take up one grid, which is equivalent to wasting 999 pages of space. Be careful not to put other books in it, otherwise management will be very troublesome.
• The 99,999 pages of Encyclopaedia Britannica will be divided into 100 sections, with the last 999 pages taking up space, equivalent to a page wasted.
• Of course, if it is known that the library will basically place books of 10K pages, it can be built according to the grid of 10K pages, so that the grid is less, saving the time of searching. But if you have a book that’s basically 10 pages, you can use 10 pages, saving space but getting more boxes. In short, we need to strike a balance between time and space. If you think about it, if putting 10,000 pages in a 10-page cell library means cutting the book into 1,000 copies, maintenance is very time consuming.

Statistical area

The statistical area is used to collect the overall information of the whole library and each region. This information is very important and is used very frequently. It is like asking how many people live in our country, and it needs to be answered immediately, rather than being reported by each province.

The total information of the library includes: Number of zones: 8 Zone name: Zone A, Zone B... Total number of cells: 640W used cells: 330W remaining cells: 310W war zone cell range: zone A (0 to 799999), zone B (800000 to...) . Index page Number: Zone A (0~99999), Zone B (100000 ~...) The founding of the library :1921 xx name of the library: world Library history event: 1949.... In 1956... Table Description Basic information about each partition A Basic information about each partition... B Basic Partition information... C Partition Information...Copy the code

• Why not keep a copy of the entire library’s global information in each section rather than in its own section? The reason is to prevent the data from being damaged. There is only one copy of such important data. If one day the library catches fire and that part of the cell that is placed is burned, then the whole library can not operate normally. Burning the east side and the west side will sacrifice space, but the safety and robustness of the library will be improved. The basic information of each partition is also stored globally.
• More detailed information about partitions is described in the partition’s global information block. This equates to the total population of Guangdong province being registered under the central government, but the population data of specific subordinate cities, districts and street offices are maintained by Guangdong itself.

Zone name: zone A range: (0 to 799999) total number of cells: 80W used cells: 20W remaining cells: 60W total number of data blocks :78W total number of index blocks :19000....Copy the code

The statistics area will have a lot of information, which can be understood as a series of books, with a fixed format, also placed in the cells. Again, it’s important to understand that any information in this article ends up in a cell!

directory

This section, like the statistics section, is a spin-off from the efficient management of the books section. Directory and e-book exchange assigned cell number is open in the library that is settled, fill the e-book exchange cell’s real books, and who also don’t know what will be a little to come in and out of books, book size determines the usage of the cell, each book takes up an index page, so finally will appear two situations:

• The index page is used up, but there are still Spaces left in the book section. This is the case with a large number of small, multiple books, because more index pages are occupied, and fewer book area cells are occupied.
• On the other hand, the index page is not running out, but there are no cells in the book section. This is the case with a large number of large but small books, because large books take up more cells in the library area, and small books have fewer index pages.
• That’s why sometimes it looks like there’s plenty of space on the disk, but that’s why it’s stored. Because the partition has too many small files, try deleting files that are too small to use.

The index table

The index table can be regarded as a book, the content of the book is a page of index pages, each page records the index information of a book,1000 pages can record the index information of 1000 books, this book is also to be installed in the grid. The cell that holds the book is called an index block. If you do 10 million books you’re going to get 10 million index pages, 1,000 pages per grid, so 10 million per 1,000 is 10,000, so the index table, the book, is going to need 10,000 cells. The index page also has a globally unique and uniform number. Note that this number and cell number are different things, which is the key to many people’s confusion about the file system. Both number ranges are saved in the statistics area.

The three partitions of a large partition (statistics, table of contents, and book) are arranged in a fixed format, so it is easy to calculate the starting and ending positions of the index blocks under a partition. It is assumed that the index table block starts on the 3,000th cell relative to the partition.

How to borrow books

Outsiders can pick up the book by bar code. The process is as follows:

• Dick Wang from tech has it5300This number (bar code) to get the book.
• The administrator needs to first lock the large partition in which the barcode is located. After checking in the statistical area, it is found in the large A area.Index Page No. : Area A (0~99999)
• The administrator immediately calculated the grid position of the index page (3000+5300/1000)=3006 grid, and moved the ladder to the phone to take photos of the first300The contents of this page are as follows:

  Name: Programming Abas Size: 14284 Pages Occupied Book Area Total Number of cells: 15 Cell size: 1000 pages Belong to common file Bar Code: 5300 Bundle Number: 2 people Permission: (0644/ -RW-r -----) User ID: (10/ small sheet) Group ID: (2/ Technical Department) Access time: 2021-07-24 02:07:21.683190622-0700 Modify book time: 2021-07-21 00:17:34.733766830-0700 Modify index time: 2021-07-21 00:17:34.733766830-0700 2021-07-29 01:20:14.314343117-0700 library location :12,32,45,.... 980Copy the code

  • The prior authority and ownership of the administrator have been clearly stated on the table. The owner of this book is Xiao Zhang from the technology department.
  • Zhang himselfrw-This book can be read and modified.
  • Student of Technology Departmentr--You can only read this book, diaosi Xiao Wang belongs to the technical department, so you can borrow it, but you can’t doodle on it.
  • Non-technical students---Note Does not have any permission.
  • The index clearly records the book’s name, total page count, grid size, bar code.
  • Data block number: 15 indicates that programming pearls are placed in 15 grids of the large A area library area,12,32,45...The serial number of grid is given, programming abecas are stored in serial order.
  • With the storage location of the book area, the administrator will copy the book in turn, stack it in order, form a complete programming pearl to Diaosi Xiao Wang, and change the number of borrowing: 2 people to 3 people, change the visit time to the current time.

Two bitmap blocks

What if Wang, a diaosi, wanted to donate his book-loving programmer’s self-cultivation to the library like Zhang did?

It is clear that two parts need to be added:

• Index page,On self-cultivation of programmerThere will be a separate index page in the index table to record information, which requires a clean index page.
• Library area cell, actual storageOn self-cultivation of programmerThe number of cells of content, depending on the size of the book. This requires a clean batch of cells.

Note that although the index pages are numbered sequentially, one after the other in the index table book. However, some books will be destroyed after the library has been in operation for a long time. For example, the Delphi program with bar code 200 was too old and too old for anyone to borrow the standing position and was destroyed, but the erasers are the records on index page 200, which still exists, always between pages 199 and 201. Scrubbed clean who cares what you used to do, and used for indexing new books. So how do you quickly know which index pages and library cells are not being used? The answer is: index page bitmap block and book area cell bitmap block

The index page bitmap can be regarded as a book, the content of the book is a page of bitmap page, the cell of the book is called the index page bitmap block. Draw the bitmap page as 100 x 100 as shown below

010101011010110101010101110101010101101011, 101011010101010110101101011010101010101010, 110101010101101011010110101010110101101011, 010110101101010101011001110101101011010110, 101011010101010110101101011010101010101010, 110101010101101011010110101010110101101011, 011110101101010101010101110101101011010110, 010110101101010101011001110101101011010110, 101011010101010110101101011010101010101010...Copy the code

Each bit represents the usage of an index page. It says that there are 10 million index pages for 10 million books, and a bitmap page can identify the usage of 100100= 10 thousand index pages. The total calculation formula is: 10 million index pages /(100100)=1 thousand bitmap pages /1000=1 index page bitmap block, that is to say, only one grid can hold 10 million index usage.

The same applies to the bitmap block of the book area cells, which records the usage of the book area cells. Bitmaps are the simplest and most efficient way to record whether two states have changed or not.

How to donate books

With the above foundation, the process of donating books is simple.

• Find a bitmap from the index page that is not in use0Index page, while marking the page as1For example, the bar code is9527The available
• Calculate how many blocks of data are needed to store the book according to its sizeOn self-cultivation of programmer“, because the program’s books are very thick, for example, 9888 pages, a cell for 1000 pages, you need 10 cells.
• The block bitmap is not used0Is marked in the page as1, such as the block number3,89,765,...Because of constant change, there is a high probability of not finding consecutive cells.
• At this point, you can create belongOn self-cultivation of programmerThe index page of this book. The following

  Name: On self-cultivation of programmers Size: 9888 pages Data Block Number: 10 Cells Size: 1000 pages Belong to common file Bar Code: 9527 Hard Link Number: 1 Person Permission: (0644/ -RW-r -----) User ID: (4/ diaosi Xiaowang) Group ID: (2/ Technical Department) Access time: 2021-08-04 03:07:21.683190622-0700 Modify book time: 2021-08-04 00:45:34.733766830-0700 Modify index time: 2021-08-04 00:45:34.733766830-0700 2021-08-04 01:20:14.314343117-0700 Block Location :3,89,765,...Copy the code

Directory entry

Can we use xiaoyi’s scheme to record the following information relationships?

├── Jin Yong novels (Bar Code :322) │ ├─ The Legend of the Eagle Heroes (Bar Code :1245) │ ├─ The Hero of the Gods (Bar Code :23456) │ ├─ Deer and the Lion (Bar Code :34567)Copy the code

Although the complete works of Jin Yong look like a catalogue, there is not much difference between them in the index area. The catalogue of The complete Works of Jin Yong also has an index page, which is as follows:

Name: Complete Novel of Jin Yong/Size: 1 page Data Block No. : 1 Cell Size: 1000 Pages Directory Bar Code: 322 Bundle Number: 17 Permission: (0755/ drWxR-XR-x) User ID: (10/ small zhang) Group ID: (2/ technical department) Access: 2021-08-03 22:11:49.021942010-0700 Modify: 2021-07-23 18:53:38.656550199-0700 Change: 2021-07-23 18:53:38.656550199-0700 Location of the data block :15Copy the code

• The only difference is that the index page states that it is a table of contents. This tells the administrator how to fetch the data block. Contents such as the index information of the Condor Heroes are not included in the index page of Jin Yong’s complete novels. Because index pages are limited in size and cannot carry much content, uncertainty is moved to the data block.
• Data block location:15The deposit isThe Legend of The Condor HeroesBar code, etc.,1245,23456,34567, have a bar code to find the index page, find the index page to find everything

The mapping relationship

Xiaoyi’s scheme is basically a low-level implementation of the file system. Understanding this scheme will make it easy to understand the implementation of hongmeng file system based on source code. The mapping between library system and computer file system concepts is as follows

Small Easy solution - > Ext file system grid partition process - > Formate Library Business - > Mount Large A - > Group Statistics - > Super Block Partition Description List - > GDT index table block - > Index table index page - > Inode bar code - > inode.id Book location map block - > Blocks bitmap Index page bitmap block - > Inode bitmap - > Logical Blocks - > Inode Blocks - > Date BlocksCopy the code

The problem

Think about a problem

• If there are several libraries in this city, and they have adopted different management schemes, how should they be managed uniformly? For example, how to move A book from library A to library B?

Intensive reading of the kernel source code

Four code stores synchronous annotation kernel source code, >> view the Gitee repository

Analysis of 100 blogs. Dig deep into the core

Add comments to hongmeng kernel source code process, sort out the following article. Content based on the source code, often in life scene analogy as much as possible into the kernel knowledge of a scene, with a pictorial sense, easy to understand memory. It’s important to speak in a way that others can understand! The 100 blogs are by no means a bunch of ridiculously difficult concepts being put forward by Baidu. That’s not interesting. More hope to make the kernel become lifelike, feel more intimate. It’s hard, it’s hard, but there’s no turning back. 😛 and code bugs need to be constantly debug, there will be many mistakes and omissions in the article and annotation content, please forgive, but will be repeatedly amended, continuous update. Xx represents the number of modifications, refined, concise and comprehensive, and strive to create high-quality content.

HongMeng station | into a little bit every day, the original is not easy, welcome to reprint, please indicate the source.