CN101488153A - Method for implementing high-capacity flash memory file system in embedded type Linux - Google Patents

Abstract

The invention discloses a realizing method of an embedded Linux large capacity flash file system. The method comprises sectionalized storage, data page distribution, refuse collection, logic structure zoning, file system initialization, directory searching, file displacement location, data reading and data writing. The method realizes the embedded Linux large capacity Nand flash file system and is beneficial for the management of embedded Linux large capacity Nand flash. The realized large capacity Nand flash file system can be applied to the large capacity Nand flash management and is beneficial to the utilization of embedded storing.

Description

Implementation method of large-capacity flash memory file system under embedded Linux

technical field

The invention relates to the field of embedded file systems, in particular to a method for realizing a large-capacity flash memory file system under embedded Linux.

Background technique

Embedded Linux is a small operating system designed according to the requirements of embedded operating systems. It consists of a Kernel (kernel) and some system modules customized according to requirements [6]. Its Kernel is very small, generally only about a few hundred KB in size. Even with other necessary modules and applications, the memory space occupied is very small.

The main features of the embedded Linux operating system are: streamlining the standard Linux kernel, adapting to a variety of CPU and hardware platforms, stable performance, good tailorability, easy development and use, and applications on Unix or Linux can also be used. Now, embedded Linux can also be used for multimedia applications under Windows. The embedded Linux operating system has a high degree of flexibility, and developers can easily customize it or develop it appropriately to meet the actual application needs.

Under embedded Linux, an effective way to manage the operating system and user data is to use the file system. Embedded Linux supports various types of file systems, which can be selected according to the type of system storage medium and the purpose of system application.

In order to provide effective support for various types of file systems, embedded Linux provides a virtual file system layer, which abstracts the user's file read and write operations. For users, all file system system calls have a unified interface. Implementation details are hidden in the virtual file system's calls to the concrete file system. The virtual file system layer facilitates the transplantation of embedded Linux.

With the continuous improvement of the manufacturing process of Nand flash memory and the continuous decline of manufacturing costs, Nand flash memory has replaced other non-volatile memories and become the mainstream storage medium in the mobile storage market, with unlimited prospects. In recent years, many scientific research institutions in the computer science circle at home and abroad have begun or imposed research on Nand flash memory management technology. The research directions can be roughly divided into the following categories:

1. Nand flash memory block mapping technology: use an intermediate layer driver to simulate Nand flash memory as a traditional block device that can be read and written at will, and use the traditional disk file system for management. The FTL technology and NFTL technology proposed by American Ban in 1995 and 1997 respectively are the precursors of this technology. Current research hotspots include: hotspot discovery and processing of massive data storage in Nand flash memory, scalable block mapping technology, etc.;

2. Research on the realization of application-related complex data on Nand flash memory. Such as implementing B-tree or R-tree on Nand flash memory, mobile communication and Nand flash memory application on sensor network, etc.

Other aspects of research include Nand flash boot XIP technology and flash real-time research.

3. Research on special file system for Nand flash memory. A Nand flash file system must fully consider the physical characteristics of Nand flash, and manage the service life of Nand flash on the basis of effective storage. There are many research fields on Nand flash file system, including: fast initialization of file system, log management of file system, system crash recovery, garbage collection and page allocation technology, etc.

The current research on Nand flash file system focuses on how to fully exploit the storage characteristics of Nand flash memory, support erasure and write balance, ensure the service life of Nand flash memory, and improve access performance through reasonable design of file system, but for large-capacity Nand flash memory and file The system lacks sufficient consideration, especially the lack of effective support for random access to large files.

A typical feature of large-capacity flash memory is that the number of pages in the memory is greatly increased compared with ordinary flash memory. Therefore, in addition to considering the problems of designing a common flash file system, the design of a large-capacity flash file system also needs to consider and solve new problems brought about by the increase in flash memory capacity, such as: the subsequent file system initialization time becomes longer , a large number of page management methods, page allocation algorithms, storage and access of large-size files, etc. The flash memory in the present invention refers to large-capacity Nand flash memory. ssss

Contents of the invention

The purpose of the present invention is to provide a method for realizing a large-capacity flash memory file system under embedded Linux.

The technical scheme that the present invention solves its technical problem adopts is as follows:

A method for realizing a large-capacity flash memory file system under embedded Linux, the steps of the method are as follows:

1) Segmented storage:

Storage points are organized in sections, file data is stored in a continuous page, and data addition and deletion are also performed in units of sections; sections are scalable and have the functions of adding, deleting, merging, and splitting ;All segments are stored in a B-tree;

2) Data page allocation:

When allocating blank pages, the pages of the directory and the data pages are placed in different blocks, which avoids "all copying", thereby reducing the number of page copies and improving efficiency;

Each type of block has one and only one block in the "current allocation" state. New pages are allocated sequentially from the currently allocated block, and if the current block is full, the next free block is sequentially searched for;

3) Garbage collection:

For dirty data, garbage collection is performed using a mixture of multiple existing recycling methods, and the greedy method and random selection method are mixed in proportion: when a specific small probability condition is met, the specific small probability condition is implemented in the specific implementation According to different application environment settings, the garbage collector will try to randomly select a recyclable page; in other cases, use the greedy method to reclaim the most "dirty" block;

4) Partition logical structure:

The first section of the partition indicates that the flash memory block stores the inode segment of the file system, and the data stored in the page in the block represents the block number of some blocks in the partition; these blocks store the header element information of the storage object, and each storage The object header element allocates a page; this segment is allocated from the beginning of the partition and has a fixed length. The specific length depends on the size of the partition; the last part is the data segment, which includes valid data pages, dirty data pages, and blank pages;

5) File system initialization:

1. First, initialize the file system related variables;

2. Initialize Nand flash memory and create memory device objects for management.

3. Scan the Nand flash partition, and read each block containing file and directory index nodes in sequence from the index node segment at the beginning of the partition;

4. Use the header object page to create the initialization information of the object;

6) Directory lookup:

Starting from the root directory or the current directory, analyze the file name layer by layer until the file is finally found;

7) File displacement positioning:

Displacement positioning is a process starting from the root node and finally finding a leaf node. First, obtain the parameters and perform integrity check; if qualified, start from the root node and find the corresponding child node according to the given displacement. If the child node And if the number of bytes of the previous child nodes is insufficient for the file displacement, it is necessary to search for the next child node until the corresponding child node is found; after determining the child node, search in turn from the leaf nodes of the child node until the corresponding section is found , and determine the local displacement in the section, and return; if there is no next child node or the corresponding leaf node, and determine the displacement on the section determined by the leaf node;

8) Data reading:

The process of reading data from the HNFS file system:

1. First obtain the read offset and the number of bytes read;

2. Determine the section and the displacement within the section;

3. Start the reading cycle, and set the cycle condition as there is still data to be read;

4. Read each page sequentially from this section, copy the data to the buffer, and modify the buffer pointer offset, remaining data amount and read offset at the same time;

5. To read a page, first check whether there is a corresponding cache in the system page cache, if not, read the page cache from the Nand flash memory;

6. If the data of a section is read, select the next adjacent section to read until enough bytes are read, if the file does not have enough bytes;

7. Return the buffer and the total number of bytes read after completion;

9) Data writing:

The process of writing data to the HNFS file system:

1. First obtain the file offset and the number of bytes written;

2. Determine the section and the displacement within the section;

3. Start the write cycle, and set the cycle condition as there is still data to be written;

4. Read a page first, first check whether there is a corresponding cache in the system page cache, if not, read the page cache from the Nand flash memory;

5. Copy the data sequentially from the buffer to the beginning of the internal displacement of this segment, and modify the buffer pointer offset, remaining data amount and read offset at the same time;

6. If the write-through method is adopted, a free page is directly selected to write the cache page, and the corresponding storage section of the object header is correspondingly modified after the writing is successful. If an error occurs during the writing process, an error is reported;

7. If the written data has not been written yet, the next adjacent segment is sequentially determined to be written until all of them are written. When there are not enough free pages in the system, the garbage collector is called to reclaim the dirty pages in the system;

8. Return the number of bytes written after completion.

Compared with the background technology, the present invention has the beneficial effects that:

The present invention is a method for realizing a large-capacity flash memory file system under embedded Linux. Its main function is aimed at the storage characteristics of large-capacity Nand flash memory, and proposes the idea of data segment storage, and realizes the method of large-capacity Nand flash memory file system. method, and described in detail the process of system initialization, directory search, displacement positioning, and data reading and writing of the large-capacity Nand flash file system HNFS. The method realizes the large-capacity Nand flash memory file system under the embedded Linux, and is beneficial to the management of the large-capacity Nand flash memory under the embedded Linux.

(1) Efficiency. The method realizes the large-capacity Nand flash memory file system under the embedded Linux, and can efficiently manage the large-capacity Nand flash memory.

(2) Practicality. The realization of the file system of large-capacity Nand flash memory is conducive to the utilization of embedded storage.

Description of drawings

Fig. 1 is a schematic diagram of the implementation process of the present invention;

Fig. 2 is the file system initialization flowchart of the present invention;

Fig. 3 is a flow chart of file displacement positioning in the file system of the present invention;

Fig. 4 is the flow chart of file system data reading of the present invention;

Fig. 5 is a flow chart of file system data writing in the present invention.

Detailed ways

The present invention is an implementation method of a large-capacity flash memory file system under embedded Linux, and its specific implementation process will be described below in conjunction with FIG. 1 .

1) Segmented storage:

The biggest feature of large-capacity Nand flash memory is that there are many data pages and large storage capacity. Therefore, when designing storage, it is necessary to design to support the storage and access of large-size files, and at the same time, consider the situation that there are many small files in the file system. Storage space savings and file compression are not primary storage goals.

Segmented storage management is different from blocks that are often seen in disk file systems. Segmented storage management All storage points are organized in segments. File data is stored in a continuous page as much as possible. Data The addition and deletion of segments is also performed in units of segments; segments are scalable and have the functions of adding, deleting, merging, and splitting. All segments are stored in a B-tree. For small files that are frequently modified, you only need to update the object header element and data page accordingly when writing data. For large and very large files with high frequency random reads, segment management can perform displacement calculations at a faster speed than file systems such as YAFFS. Segmentation management can effectively meet the file system usage characteristics mentioned above, reduce the additional loss caused by indirect indexing, and improve random access speed.

In the present invention, files, hard links, and directories are abstracted into storage objects, each object has an object header, and stores information on aspects such as object control and access, and each object header is specially assigned an object header page. The file system realized according to the method of the present invention is called the high-capacity Nand flash memory file system HNFS, hereinafter referred to as HNFS.

Directories are accessed more frequently than files. If the object header is placed on a separate page, and the update frequency of the object header is high, then this page can be used multiple times to store multiple versions of the stored object elements, which not only helps to reduce the loss of Nand flash memory, but also facilitates possible recover from a system crash. And if 2 or more object header elements share a page, then the modification of any file will inevitably lead to the modification of the header element page, so that the update frequency of this page is too high, which violates the saving space and reduces the loss of Nand flash memory The original intention; if the data and header elements are placed in one page, because the access frequency of directory and ordinary file data is usually different, this also brings about the problem of frequent data transfer without reason and faster page update.

According to the storage characteristics of Nand flash memory, the loading speed of the file system is also improved. A number of blocks are reserved at the beginning of the flash partition to be used as file inode block indexes. When loading a large-capacity flash file system, the position of the inode block is read from these pages, and then the inode information is read from the inode block, thereby constructing the entire file system in memory.

2) Data page allocation:

Unlike magnetic disks, Nand flash memory has no tracking delay, so it has a higher access speed when reading data. However, since Nand flash memory can only write data to blank pages, the writing speed and blank page allocation method, storage space status, and garbage collector performance are closely related to the overall performance of the file system. The allocation method is as follows: in a certain block, blank pages are allocated in increasing order, and after the pages in a block are allocated, another blank block is selected to participate in the allocation. Also, reserve 2-3 blocks for garbage collection, for "copy all". When there is no blank page in the system, select a dirty block to be erased and used as a blank block.

From the perspective of the file system, pages that store system metadata, such as directory pages, have a higher update rate than ordinary data pages. Therefore, when allocating blank pages, the pages of the directory and the data pages are placed in different blocks (Block), which avoids "full copy", thereby reducing the number of page copies and improving efficiency. In the present invention, each type of block has one and only one block in the "current allocation" state. New pages are allocated sequentially from the currently allocated block, and if the current block is full, the next free block is sequentially searched for.

3) Garbage collection:

When the blank page in the storage space is lower than a predetermined value, it is necessary to use the garbage collector to reclaim the buried data page and return it to the system.

For dirty data, use a variety of existing recycling methods mixed algorithms for garbage collection, and use a mixture of greedy methods and random selection methods in a certain proportion: when a specific small probability condition is met (the specific small probability condition is in the specific According to different application environment settings during implementation), the garbage collector will try to randomly select a recyclable page; in other cases, use the greedy method to reclaim the most "dirty" block.

When reclaiming dirty data blocks, different methods are used to treat different types of dirty data blocks. If the recovered dirty block is used to store directories, then copy the valid pages in the block to other blocks that store directories; if the recovered dirty blocks store ordinary file data, then copy the valid pages in the block to Other blocks that store ordinary file data.

4) Partition logical structure:

The first section of the partition represents the index node segment (Inode-StoredBlock of Segment) of the flash memory block storage file system, and the data stored in the page in the block represents the block number of some blocks in the partition. These blocks store the storage object header element information, and each storage object header element is allocated a page. This segment is allocated from the beginning of the partition and has a fixed length. The specific length is set according to the size of the partition. The last part is the data segment, which includes valid data pages, dirty data pages, and blank pages.

When the system is initialized, the file system loading is completed by reading the header page information from the inode segment.

5) File system initialization:

The file system initialization process is shown in Figure 2:

1. First, initialize file system-related variables, such as superb, directory tree, object cache, and so on.

2. Initialize Nand flash memory and create memory device objects for management.

3. Scan the Nand flash memory partition, read each block containing file and directory index nodes in turn from the index node segment at the beginning of the partition, and read the block number of the head page block in each page of the block. A block number points to some blocks in the partition, expressed as a two-byte unsigned 16-bit binary number. Each page in these data blocks holds header information for directory and file objects.

4. Use the header object page to establish the initialization information of the object, which includes access control information, status information, and storage information. Each storage object manages storage through a B-tree-like structure. Each object is also added to the directory tree.

As inodes are read continuously, the file system is gradually initialized. In HNFS, all sub-objects under a directory are linked together through pointers, and file data is managed through B-trees. Finally, a search tree is established from the root directory as the root node to each file as the leaf node in the system.

6) Directory lookup:

The path of a Linux file name is a series of directory names separated by "/", ending with the name of the file. For example, a file name is /home/ruby/.cshrc, where /home and /ruby are directory names, and the file name is .cshrc. Like all other Unix systems, Linux does not pay special attention to the format of the file name itself. The maximum length it supports is 1024 characters, consisting of printable characters. In order to find the memory object corresponding to a certain file, the file system implemented by the method of the present invention must analyze the file name layer by layer starting from the root directory or the current directory until the file is finally found.

The first object required is the object for the root of the file system. Its value can be obtained in the superblock of the file system. In order to read an HNFS object, it must be found in the linked list of its parent directories. For example, for ruby, you must first find home, and then find ruby from the linked list of sub-objects of home.

home is just one of the sub-object lists in "/". From its entry in "/", a pointer to the object can be obtained. Ruby must be discovered through this directory object (first obtain a pointer to this object, and then obtain a pointer to ruby from the object's sub-object linked list). From the obtained data, the entry of the number of the memory object of the /home/ruby directory is obtained. Finally, read in the memory object data pointing to the description directory /home/ruby. And find the memory object value of .csshrc from the data block it points to. From this memory object, the data block containing the data for the file can be located.

7) File displacement positioning:

In HNFS, the purpose of file displacement positioning is to determine the storage data segment of the data and the displacement in the data segment according to the displacement given by the user.

As mentioned earlier, in HNFS, memory file data is organized in a B-tree structure. A branch node in a B-tree stores a pointer to a leaf node and the number of bytes stored by that node. And each leaf node stores a pointer to the storage section and the number of bytes stored in the section. B-trees are created when the file system is initialized.

As shown in Figure 3, displacement positioning is a process starting from the root node and finally finding a leaf node. The parameters are first obtained and sanity checked. If it is qualified, start from the root node and find the corresponding child node according to the given displacement. If the number of bytes of this child node and the previous child nodes is not enough for the file displacement, you need to find the next child node until you find the corresponding child node. node. After the child node is determined, it is searched sequentially from the leaf nodes of the child node until the corresponding segment is found, and the local displacement in the segment is determined and returned. If there is no next child node or corresponding leaf node, and determine the displacement on the section determined by the leaf node.

8) Data reading:

The process of reading data from the HNFS file system is shown in Figure 4:

1. First obtain the read offset and the number of bytes read;

2. Determine the section and the displacement within the section;

3. Start the reading cycle, and set the cycle condition as there is still data to be read;

4. Read each page sequentially from this section, copy the data to the buffer, and modify the buffer pointer offset, remaining data amount and read offset at the same time;

5. To read a page, first check whether there is a corresponding cache in the system page cache, if not, read the page cache from the Nand flash memory;

6. If the data of a section is read, select the next adjacent section to read until enough bytes are read, if the file does not have enough bytes;

7. After completion, return the buffer and the total number of bytes read.

9) Data writing:

The process of writing data to the HNFS file system is shown in Figure 5:

1. First obtain the file offset and the number of bytes written;

2. Determine the section and the displacement within the section;

3. Start the write cycle, and set the cycle condition as there is still data to be written;

4. Read a page first, first check whether there is a corresponding cache in the system page cache, if not, read the page cache from the Nand flash memory;

5. Copy the data sequentially from the buffer to the beginning of the internal displacement of this segment, and modify the buffer pointer offset, remaining data amount and read offset at the same time;

6. If the write-through method is adopted, a free page is directly selected to write the cache page, and the corresponding storage section of the object header is correspondingly modified after the writing is successful. Report an error if an error occurs during the write.

7. If the written data has not been written yet, the next adjacent segment is sequentially determined to be written until all of them are written. When there are not enough free pages in the system, the garbage collector is called to reclaim the dirty pages in the system;

8. Return the number of bytes written after completion.

Claims (1)

1. an implementation method of large-capacity flash file system under embedded Linux, it is characterized in that the steps of the method are as follows: 1) Segmented storage: Storage points are organized in sections, file data is stored in a continuous page, and data addition and deletion are also performed in units of sections; sections are scalable and have the functions of adding, deleting, merging, and splitting ;All segments are stored in a B-tree; 2) Data page allocation: When allocating blank pages, the pages of the directory and the data pages are placed in different blocks, which avoids "all copying", thereby reducing the number of page copies and improving efficiency; Each type of block has one and only one block in the "current allocation" state. New pages are allocated sequentially from the currently allocated block, and if the current block is full, the next free block is sequentially searched for; 3) Garbage collection: For dirty data, garbage collection is performed using a mixture of multiple existing recycling methods, and the greedy method and random selection method are mixed in proportion: when a specific small probability condition is met, the specific small probability condition is implemented in the specific implementation According to different application environment settings, the garbage collector will try to randomly select a recyclable page; in other cases, use the greedy method to reclaim the most "dirty" block; 4) Partition logical structure: The first section of the partition indicates that the flash memory block stores the inode segment of the file system, and the data stored in the page in the block represents the block number of some blocks in the partition; these blocks store the header element information of the storage object, and each storage The object header element allocates a page; this segment is allocated from the beginning of the partition and has a fixed length. The specific length depends on the size of the partition; the last part is the data segment, which includes valid data pages, dirty data pages, and blank pages; 5) File system initialization: 1. First, initialize the file system related variables; 2. Initialize Nand flash memory and create memory device objects for management. 3. Scan the Nand flash partition, and read each block containing file and directory index nodes in sequence from the index node segment at the beginning of the partition; 4. Use the header object page to create the initialization information of the object; 6) Directory lookup: Starting from the root directory or the current directory, analyze the file name layer by layer until the file is finally found; 7) File displacement positioning: Displacement positioning is a process starting from the root node and finally finding a leaf node. First, obtain the parameters and perform integrity check; if qualified, start from the root node and find the corresponding child node according to the given displacement. If the child node And if the number of bytes of the previous child nodes is insufficient for the file displacement, it is necessary to search for the next child node until the corresponding child node is found; after determining the child node, search in turn from the leaf nodes of the child node until the corresponding section is found , and determine the local displacement in the section, and return; if there is no next child node or the corresponding leaf node, and determine the displacement on the section determined by the leaf node; 8) Data reading: The process of reading data from the HNFS file system: 1. First obtain the read offset and the number of bytes read; 2. Determine the section and the displacement within the section; 3. Start the reading cycle, and set the cycle condition as there is still data to be read; 4. Read each page sequentially from this section, copy the data to the buffer, and modify the buffer pointer offset, remaining data amount and read offset at the same time; 5. To read a page, first check whether there is a corresponding cache in the system page cache, if not, read the page cache from the Nand flash memory; 6. If the data of a section is read, select the next adjacent section to read until enough bytes are read, if the file does not have enough bytes; 7. Return the buffer and the total number of bytes read after completion; 9) Data writing: The process of writing data to the HNFS file system: 1. First obtain the file offset and the number of bytes written; 2. Determine the section and the displacement within the section; 3. Start the write cycle, and set the cycle condition as there is still data to be written; 4. Read a page first, first check whether there is a corresponding cache in the system page cache, if not, read the page cache from the Nand flash memory; 5. Copy the data sequentially from the buffer to the beginning of the internal displacement of this segment, and modify the buffer pointer offset, remaining data amount and read offset at the same time; 6. If the write-through method is adopted, a free page is directly selected to write the cache page, and the corresponding storage section of the object header is correspondingly modified after the writing is successful. If an error occurs during the writing process, an error is reported; 7. If the written data has not been written yet, the next adjacent segment is sequentially determined to be written until all of them are written. When there are not enough free pages in the system, the garbage collector is called to reclaim the dirty pages in the system; 8. Return the number of bytes written after completion.

Images