Construction and Improvement of YAFFS File System in Embedded Linux System

In the development of embedded Linux, the commonly used storage devices are NorFlash and NandFlash. Among them, NandFlash is more widely used because it is inexpensive and suitable for high-density and large-capacity storage [1]. The YAFFS (Yet Another Flash File System) file system is designed specifically for the special structure of NandFlash. It is a log-structured file system with performance that exceeds the original JFFS series file system. However, with the development of embedded technology, when constructing YAFFS in embedded Linux on NandFlash media, YAFFS has two disadvantages: long mounting time and insufficient wear leveling, which need further improvement and optimization.

1 YAFFS file system

In the embedded NandFlash, the basic read and write unit is page. The storage bit of YAFFS is also page (generally called Chunk), which is divided into the overlay area (OOB) and the data area. The 32-page block is the basic erase unit [2]. Since the file offset address of YAFFS is inconsistent with the physical address of the flash memory, a mapping table between files and physical pages is established. The page number of the flash memory is used as the table content, and the file offset described by each page is used as the table index. This large mapping table is divided into several small tables and organized into a tree structure to improve the search speed of file data blocks. This hierarchical index directory established in the memory is called the node tree (TnodeTree), which is the core model of YAFFS, as shown in Figure 1. In the node tree, the physical address index (Physical chunk index) is found according to the logical index (Logical chunk index). When the file becomes larger, the required leaf nodes will also increase. At this time, the node tree will be "elevated" and "fatten". When the file is deleted, the recursive method is used to shrink from the leaf node upward to release the physical page corresponding to the deleted node. 2. Building the YAFFS file system 2.1 The cross-compilation mode of the target board and the host machine is used in the development process of the experimental platform. The host machine is a PC, which uses a virtual machine + Linux RedHat9.0 system; the hardware of the target board is an ARM board, which uses an S3C2440 ARM9 microprocessor with a 256 MB NandFlash and 64 MB SDRAM memory. The development software used by the target board is embedded Linux2.6.28+cross-compilation tool arm-Linux-gcc4.3.1. The development process of the YAFFS file system is shown in Figure 2. The boot program Boot-Loader is generally fixed in the Flash of the board (not explained in detail here). 2.2 Kernel transplantation (1) Modify the cross-compilation environment to make it suitable for this experimental platform. Modify the ARM compiler defined in the top-level Makefile to correspond to the platform processor used. Modify as follows: ARCH = arm CROSS_COMPILE = /usr/local/3.4.1/arm-linux- At the same time, in order to support the 12 MHz crystal frequency of the experimental platform processor, modify the input clock provided by Linux, define s3c24xx_init_clocks (12 000 000) in the file arch/arm/mach-s3c2440/mach-smdk2440.c; and change the machine name supported by Linux to MACHINE_START(S3C2440, "Study-S3C2440" in this file; finally, modify the default machine number in Linux to make it consistent with the machine parameter 782 passed by BootLoarder. In arch/arm/tools/math-types, the machine model statement is modified to: S3C2440 ARCH_S3C2440 S3C2440 782 (2) The kernel supports MTD. MTD is the interface between flash memory and file system. The connection between NandFlash, YAFFS file system and MTD is shown in Figure 3. [page] The old version of MTD is not very compatible with NandFlash, so the latest MTD needs to be installed. To implement Linux support for MTD, the NandFlash hardware device driver must first be added to the MTD subsystem. The driver information of the Flash hardware platform is defined in the file common-smdk.c in the arch/arm/plat-s3c2440 directory. The structure static struct mtd-partition partition-info[] is defined in the file to represent the MTD partition information of the flash memory. Here, NandFlash is divided into 5 MTD partitions. The partition contents are as follows: [0] = { .name = "Boot", .size = 0x00100000, .offset = 0 }, //mtd0 partition, size is 1 MB, relative offset address is 0x0 [1] = { .name = "MyApp", .size = 0x003c0000, .offset = 0x00140000, }, //mtd1 partition, stores application programs [2] = { .name = "Kernel", .size = 0x00300000, .offset = 0x00500000, }, //mtd1 partition, used to store the kernel [3] = { .name = "filesystem", .size = 0x03c00000, .offset = 0x00800000, }, //mtd3 partition, size is 30 MB, used to store the file system [4]…… } In this file, the Flash bus width, basic read and write operations, and hardware-related control pins are also defined, which can be modified according to the corresponding requirements. (3) Add kernel support for YAFFS. First, put the latest YAFFS source code package into the /fs directory of the Linux kernel and perform the decompression operation. The source code of the YAFFS file system is added to the /fs directory; then configure YAFFS in the kernel and modify it accordingly: add obj-$(CONFIG_YAFFS_FS)+=yaffs/ in /fs/Makefile; add source "fs/yaffs/Kconfig" in /fs/Kconfig. (4) Compile the kernel. Execute the make menuconfig operation in the Linux2.6.28 kernel directory, and select the options that support MTD, NandFlash, and YAFFS file systems in the kernel configuration menu. Note that you must select the option Let yaffs do its own ECC, because the data in the additional area of ​​the produced YAFFS file system image contains the ECC verification algorithm. This algorithm is different from the verification algorithm in NandFlash's MTD, which will cause MTD to think that the page verification is wrong; then run make zImage to form a compressed kernel image zImage in /linux2.6.28/arch/arm/boot, and use the S3C2440 dedicated serial port tool DWN to burn the image to the kernel partition. 2.3 YAFFS root file system production (1) Production of the file system. First, create the file system root directory rootfs, and create subdirectories bin and sbin (to store built-in commands), etc (system configuration files), proc, lib (dynamic link libraries for program operation), user, dev (device files supported by the system) under the root directory; then, install the common command set Busybox of Linux, install its source code to the Linux root directory, and modify the makefile in it to achieve cross compilation: ARCH = arm
























































CROSS_COMPILE = /usr/arm-linux-

Execute make menuconfig in the Busybox directory to enter the configuration menu and add options as needed. After compiling, copy the files in the install directory to /rootfs; secondly, install the interactive program Bash so that the system can enter the interactive interface. After the source code package is unzipped, modify the link path to: export PATH =/usr/local/arm/3.4.1/bin; after compiling, copy the obtained bash static link program to the /rootfs/bin directory; finally, create the system configuration file and write the startup script. The first script accessed by the system startup is etc/inittab. Edit the etc/init.d/rcS script and execute the command to mount the file system Ramfs and sysfs. You can also configure the system IP address in etc/rc.local.

(2) Make a YAFFS file system image. There is a util tool package in the YAFFS source code file package. Modify the cross-compilation path of the makefile in the tool package and compile to get the mkyaffsimage tool. Execute in the root directory: ./mkyaffsimage/rootfs rootfs.yaffs.

(3) Burn the YAFFS root file system. Modify the kernel configuration parameter rootsystem=YAFFS, and burn the rootfs.yaffs image file to the filesystem partition through DWN. When the system is started, the startup information will be displayed: VFS: Mounted root (yaffs filesystem).

3 YAFFS improvement strategy

(1) In order to solve the problem that all used blocks on the Flash need to be scanned when mounting YAFFS, which slows down the startup speed, a space-for-time strategy is adopted during the loading process of the file system. An index area is added to store file attribute information nodes [3]. However, this is not very meaningful for embedded systems with small flash memory. YAFFS defines and records the data Objectpoint_data and file_data in the NandFlash page, and also adds the index_data data type, which records the data and node information required when mounting the system, and allocates blocks (i.e., index blocks) specifically for recording these data. In YAFFS, a data structure of index_data type yaffs_monut_index is created to organize the structure of the initialization data of file attributes, such as yaffs_object and some related yaffs_Device, yafffs_BlockInfo and yaffs_Tnode. The storage structure of each page in the index block is shown in Figure 4. inode_num, check and other useful data are all mark bits stored in the additional space of each page of the index block. inode_num is used to record the number of pages used to store startup control information. When mounting, the system only needs to scan the pages used by the index block; check records whether the control information is normally written to the flash memory when the system is uninstalled. If the check passes during startup, the system is mounted using the improved strategy. Otherwise, the original mechanism is run to scan all blocks [4]. When YAFFS is mounted, the system scans the additional area of ​​the first page of each block. If it is not an index block, it skips checking the next block; if it is, it reads the block, obtains the information recording the leaf node data in the node tree, and rebuilds the node tree [5]. The YAFFS file system is successfully mounted, which means that a certain amount of storage space is exchanged for a lot of mounting time. After adopting this strategy, the system will run the original startup mechanism when mounted for the first time, write the file attribute data into the index block when unmounted, and directly read the startup data according to the default settings when mounted for the second time [6]. It also avoids the problem of slow startup as the file system grows. The difference between the space-for-time strategy and the original YAFFS loading process is shown in Flowchart 5. [page] (2) When the YAFFS system performs a write operation and the unallocated space in NandFlash is less than the preset threshold, the garbage collection mechanism is started and the dirtiest block is selected for erasure. The garbage collection strategy of the YAFFS file system combines the balance of the random strategy and the efficiency of the greedy strategy. The recycling mechanism includes: recycling dirty blocks that are no longer used and processing bad blocks with valid data. However, the recycling algorithm is random. The system may always select the same block, determine it as the dirtiest block, and continuously erase and recycle it, resulting in malicious use. The number of erases of NandFlash is limited (about 10 times). Malicious use will cause some blocks in the flash memory to be damaged, while other blocks are rarely used, shortening the life of the flash memory. (3) In view of the poor wear balance of YAFFS, an erase count mechanism is adopted[7]: in yaffs.guts.h, a data structure yaffs_tags is defined and stored in the additional area of ​​NandFlash to mark the status of each page; chunkID, objectID and valid word count are defined. Two bits of space are not used, and 7 bits are allocated from chunkID and objectID. The 9 bits of space are defined as erase_count to record the number of times the page is erased. The initial value is zero. When it is erased, it is marked as "1", indicating that the maximum count value that can be reached after one erase is 511. The flowchart of system garbage collection is shown in Figure 6. When the number of erases of a block reaches 511, the block exchanges the data stored in each block with the block with the smallest number of erases, so that the frequently erased block stores rarely used data, while the block with the least number of erases stores frequently updated data[8] (such as file attribute information data). When the erase count reaches more than 70% of the largest block, all erase count values ​​are reset to zero, and the above operations are repeated to achieve a basic balance of NandFlash wear, extend service life, and improve file system reliability. 4 Performance Test According to the above strategy, the source code of the relevant part of the YAFFS file system is modified, and according to the basic steps of building the YAFFS root file system, the improved file system is burned into the target board as the root file system. On the experimental platform, the performance tests and research of YAFFS and the improved file system are carried out respectively. The main contents of the performance test are: the number of erases of each block and the time of file system mounting. A large number of read, write and delete operations are performed on the experimental platform, and the erase count is also added to the source code (only for counting). After the two file systems have the same number of read, write and delete operations, the number of erases of each block is read. The data analysis shows that there are blocks with zero erase counts in the original YAFFS, but not in the improved one; the ratio of the maximum erase count to the minimum erase count of the original YAFFS is infinite, while the ratio of the maximum erase count to the minimum erase count of the improved one fluctuates around the average value, with little fluctuation. The main method of file system loading test is to add interrupt mechanism and clock in kernel source code and file system source code, install PrintkTimes patch, a tool for evaluating system time, and use printk to output required data. The test results are shown in Table 1. As can be seen from Table 1, since the file attribute information has not been written into the index area at the first startup, the system startup time is roughly the same as before the improvement, but the index area mechanism starts to work at the second startup, and the file information is read directly from the index block. The startup time of the modified YAFFS has been significantly improved, indicating that the improvement strategy has achieved the purpose of shortening the loading time. The YAFFS file system was built on an embedded Linux platform with NandFlash as the medium, and the startup time and loss balance of YAFFS were optimized based on the original YAFFS file system. The test shows that the startup time is shortened by more than half compared with the original file system, and the friction loss of NandFlash is basically balanced, which is better than the file system before the improvement.