JP2008059228A - File system - Google Patents

Abstract

A file system capable of performing initialization processing at high speed is provided.
A file system on a flash memory, block information including a file ID unique to the file system assigned to the file and a block number indicating the connection order of the blocks in the file is stored in the block. Block information adding means for adding the file structure information, and file structure information reconstructing means for reconstructing the file structure information representing the file structure based on the block information.
[Selection] Figure 7

Description

  The present invention relates to a file system technique, and more particularly to a NAND flash memory file system technique.

  In recent years, with the development of information equipment, flash memory has attracted attention as an information recording medium. The reason is that it is possible to reduce the size, and the reliability is increased because the driving device is unnecessary. In particular, NAND flash memories that can be easily increased in capacity are rapidly spreading as information recording media. A NAND flash memory is a kind of flash memory, and is characterized by high-speed erasing and writing.

  In general, in order to write to a flash memory, it is necessary to erase before writing. The NAND flash memory is composed of a plurality of blocks, and the blocks are composed of a plurality of pages. Erasing is performed in units of blocks, and writing is performed in units of pages. In general, a page is divided into a part for storing data and a part for storing redundant data such as an error correction code.

  FIG. 22 is a diagram showing an image of the file system of the magnetic storage device. In the magnetic storage device, physical read / write is performed in units of sectors. The logical read / write unit is a cluster unit (a cluster of a plurality of sectors).

  A cluster is divided into a system area and a data area, and a file is divided into a plurality of clusters assigned to the data area and stored. Information on the cluster assigned to the file and information on the file itself (file configuration information) are stored in the system area. Therefore, when the file is updated, this area is also rewritten. Information about which clusters are in use and which are free is also stored in the system area. Therefore, when the file is updated, this area is also rewritten.

  However, because of the electrical characteristics of flash memory, there are limits on the number of times data can be erased and written, and it is not possible to apply the file system method for a magnetic storage device that has no substantial limit on the number of times of writing. This is because the file configuration information represented by, for example, FAT (File Allocation Table) is stored in a specific location in the storage device, and the configuration information is written by writing the file or the like. If is changed, the contents of this location will be updated accordingly. That is, when a file is written, not only the location where the file is actually written but also the file configuration information is rewritten.

  FIG. 23 is a diagram showing an image of the file system of the flash memory. In the flash memory, physical erasure is in units of blocks and writing is in units of pages. The logical read / write unit is a block unit (a block is composed of a plurality of pages), and all the blocks are used as a data area. The file is divided into a plurality of blocks and stored. At this time, header information is added to the head of the block and saved. Block information assigned to the file and information of the file itself (file configuration information) are not stored in the flash memory. In other words, by analyzing the header information of the block, it can be reconfigured when the file system is initialized, and the information itself is stored in another memory such as a RAM of the electronic device to be used. Also, block usage information indicating which blocks are in use and which blocks are free (reusable blocks) is not stored in the flash memory. Instead, it can be detected at the time of initialization of the file system by analyzing the header information of the block, and the information itself is stored in the RAM.

  This is because when a file system method similar to that of a magnetic storage device is applied to flash memory, only a specific block is frequently rewritten, so that the block immediately exceeds the limit of the number of writes and becomes unusable. This is because the entire memory becomes unavailable.

  In order to avoid such a problem, a file system called jffs2 (Journaling FlashFile System version 2) has been developed by Red Hat Corporation in the Linux OS (Operating System). This is intended to extend the life of the entire flash memory by distributing the restriction on the number of times of writing to the flash memory over the entire area by preventing data writing from depending on a specific block.

http: // sources. redhat. com / jffs2 /

  However, in the initialization process, the jffs2 needs to scan the written area of the file and analyze the written data for the file consistency check and the free area check. take time. In particular, when there are a large number of files, there is a problem that the influence appears remarkably when the power of the apparatus is interrupted when the file is written.

  For example, it is not suitable when it is necessary for the user to feed back the reaction to the operation as soon as possible after the power-on operation, such as a home electronic device (liquid crystal television, recorder, etc.).

  An object of the present invention is to provide a file system capable of performing initialization processing at high speed.

  According to one aspect of the present invention, a memory area is divided into a plurality of blocks, data written in the memory area is erased in units of blocks, and the blocks are divided into a plurality of pages. The writing of the data is a file system on the flash memory that is performed in units of pages, and at least a file ID that is unique to the file system assigned to the file and a block number that indicates the connection order of the blocks in the file. A file comprising block information adding means for adding block information to a block, and file structure information reconstructing means for reconstructing file structure information representing a file structure based on the block information A system is provided. Based on the block information, the file can be correctly reconstructed.

  Magic number adding means to add magic numbers to the first page and non-first page of each block when data is written to the block, and data is written in order from the first page and verified each time data is written to the page. You may make it have the page verification means to perform, and the block check means which checks the validity of a block based on whether the magic number is added to the head page of each block, and a page other than the head.

  At least first and second magic number areas for writing the magic number in the block may be provided across a data area for writing data. An area for writing block information may be provided in a portion before the first magic number area.

  According to another aspect of the present invention, there is provided a method for reconstructing file configuration information using the above file system, the step of taking out a block and reading out the block information of a valid block, and a file ID in the block information And a step of linking blocks having the same file ID in the order of the block numbers based on the difference between the file numbers. A method for determining the validity of a block using the file system, wherein the first and second magic numbers are read, and the validity of the data in the block is determined by the validity / invalidity of the magic number based on the read contents. A method for determining the validity of a block is provided.

  According to the present invention, a file system capable of performing initialization processing and the like at high speed can be provided.

  Hereinafter, a file system of a flash memory according to an embodiment of the present invention will be described with reference to the drawings. FIG. 1 is a functional block diagram showing a configuration example of an electronic device shown as an example of a device to which the file system according to the first embodiment of the present invention can be applied. As shown in FIG. 1, an electronic device A according to the present embodiment includes a control device (CPU) 1 that controls the whole, a non-volatile flash memory 3 that stores programs and data files for controlling the device, and the like. A volatile memory 5 such as a RAM, a data input / output means 15 for inputting / outputting data, an input means 7 for inputting by a user, and an output obtained by processing input data Display means 11 for displaying information.

  In the file system in the electronic device, the file configuration information indicating where the file is used in the flash memory area is not stored in a specific area of the flash memory, but mounted (file system initialization process). In some cases, the file configuration information is reconfigured on the memory 5 and applied to a NAND flash memory. FIG. 2 is a diagram showing an example of the area configuration of the NAND flash memory. As shown in FIG. 2, the file X is composed of one or more blocks Y, and the blocks Y are composed of pages Z. Thus, the NAND flash memory is composed of a plurality of blocks, and the block is composed of a plurality of pages. FIG. 3 is a diagram illustrating variations of block information. For example, assuming that the file X is composed of blocks A, B, and C (Y), the block information 25, 27, 31, and 33 added to the data 23 are the blocks A, B as shown in FIG. , C may hold the same one, or may hold different ones depending on the block as shown in FIG. In the case of FIG. 3B, block information including the file name and file size only in the first block constituting the file (block A ′: the block existing at the beginning of the arrow, the arrow indicates the access order). 21 to have.

  When writing data, it is necessary to erase it before that. Erasing is performed in units of blocks, and writing is performed in units of pages. Further, the page is generally divided into a data area for writing normal data and an OOB (Out Of Band) area for writing redundant data. The OOB area includes an area for storing an error correction code for correcting an error in data written in the data area, an area indicating whether or not the block is a bad block, and the like.

  This is because, due to the characteristics of NAND flash memory, incorrect data may be written at the time of writing, and if it is read as it is, the incorrect data will be read out next time, so the error is corrected. This is because there is an area for storing a correction code. When an error that cannot be corrected with just the correction code occurs, the block including the page in which the error occurs is treated as a bad block. The bad block is marked as a bad block in the OOB area of the first page. Some bad blocks are initially bad blocks depending on the manufacturing process, and some bad blocks are deteriorated by repeating erasing and writing, and later become bad blocks.

The definitions of terms used in the present specification are shown below.
1) Free block: An erased block. In this state, the data can be written.
2) Valid block: A block holding data written by this file system. It can be a block that constitutes a file.
3) Invalid block: A block that is neither a free block nor a valid block. It is a block that needs to be erased. Either the power was cut off during writing to the block, or in this file system, it was determined that erasure was necessary and the block was explicitly invalidated.
4) Bad block: This block is physically unusable. There is an initial bad block that exists from the time of shipment, and an acquired bad block that occurs while writing is repeated. In any case, the information is marked in a portion where the OOB is present, so that it can be distinguished from a normal block. The above three blocks relate to normal blocks.
5) Free block list: a list storing free blocks, which is a list existing on the RAM.
6) Check block list: A list that stores valid blocks and is a list that exists on the RAM.
7) Erase block list: a list that stores invalid blocks and erasable blocks among valid blocks, and is a list that exists on the RAM.
8) Bad block list: A list storing bad blocks, which is a list existing in the RAM.
9) Valid file / Valid file candidate: A file that is composed of necessary and sufficient valid blocks and is determined to be a file according to the data structure of the file system. There is also a file with the same name. A valid file candidate is a file that has blocks but may have some data missing. Valid files are a subset of valid file candidates.
10) Incomplete file: A file that is determined to be an abnormal file that does not conform to the data structure of this file system. This includes files with missing building blocks, files that do not contain necessary data, and so on.
11) Valid file: One of valid files. When a file with the same name exists in a valid file, it indicates the file that was normally written last. If a file with the same name does not exist, it is the file itself. However, it is not a “file indicating deletion”.
12) Invalid file: A file that is not a valid file among valid files. There is a newer file with the same name, or “file indicating deletion”.
13) File ID: A unique ID in the file system assigned to the file when the file is written. Not reused. For example, the file ID to be assigned next = the maximum file ID assigned in the past + 1.
14) Block ID: A serial number for identifying a block.
15) Block number: A serial number of a block in the file.
Next, the mounting process will be described with reference to the drawings.

  The file system according to the present embodiment does not record file configuration information in a specific block, but adds block information to each block by block information adding means, and records this block information to mount the block. The file structure information is sometimes constructed from the block information by the file structure information reconstruction means. That is, in the mount process, block information of all valid blocks is read, and blocks having the same file ID are collected. Then, file configuration information is generated from a block in which the file can be correctly reconstructed.

  The block information adding means is means for adding information related to the block to the corresponding block at the time of generating the write data to the block. The hardware may be added. The block configuration example shown in FIG. 3 shows a state after block information has already been added.

  The file configuration information reconstruction means is means for reconstructing the file configuration information based on the block information at the time of mounting, and is generally performed by a control device by a program, but is reconfigured by dedicated hardware. You may make it do. The flowchart shown in FIG. 7 shows a program from the extraction of a block to the end of reconstruction. This process corresponds to the process by the file reconstruction unit.

  The file ID is assigned by file ID assigning means. The file ID assigning means is a means for assigning a unique file ID in the system for identifying the file when writing the file. The file ID is written into the block as one piece of block information by the block information adding means.

  In the first stage of mounting, all blocks in the area are scanned, free blocks, valid blocks, invalid blocks, and bad blocks are determined, and the blocks are connected to the respective lists.

  More specifically, if a bad block is recorded in the OOB area of the first page of each block, or if it is not recorded, a determination is made based on whether a predetermined magic number is written in the block. The magic number can be written in either the data area or the OOB area. However, since it is necessary to read the OOB area to determine whether the block is a bad block, the magic number can also be written to the OOB area. Can be judged at the same time. Therefore, the determination is made based on whether or not the magic number is written in the OOB area of the first page and the last used page of each block. The block check means is a means for making such a determination in order to determine the validity of the block, and is generally performed by the control device by a program, but it is to be checked by dedicated hardware. Also good. In order to make such a determination, when writing data to a block, the magic number adding means writes the magic number and the number of used pages of the block in the OOB area. The magic number adding means is generally performed by the control device by a program, but may be added by dedicated hardware. In addition, an erased block usually has all 1 bits (the magic number is 0xffff if it is 16 bits). At this time, the judgment criteria are as shown in Table 1 below.

  Here, by performing the following, it is possible to speed up the determination of the validity of the block at the time of mounting. This will be described with reference to FIG. One method of speeding up can be achieved by providing magic number areas for writing the above-described magic number at two or more locations in the block. That is, in order to determine the validity of a block, it is only necessary to confirm whether data has been written correctly. Since it takes time to read the entire block and check the data consistency, if the data is written sequentially from the beginning of the block, check that the correct data is written near the beginning and near the end. Just be good. Therefore, an area for describing the magic number is provided near the beginning and end of the block. By reading only this magic number, the validity of the block can be determined at high speed. Furthermore, it becomes easy to determine whether or not the power is cut off during block writing.

  FIG. 8A is a diagram illustrating a block configuration example for realizing the above technique. As shown in FIG. 8A, the block Y is configured in the page order of the data 1 area 73a, the magic number 1 area 71a, the data 2 area 73b, the magic number 2 area 71b, and the data 3 area 73c. Has been. Since the magic number may be in the data area or the OOB area, the data area and the OOB area are not distinguished in the figure. However, since the magic number is preferably in the OOB area, it is assumed that the magic number is written in the OOB area. Further, it is assumed that the magic number 1 area 71a exists on the first page of the block and the magic number 2 area 71b exists on a page other than the top of the block. Based on the criteria described in Table 1 above, if the bad block is recorded in the OOB area of the first page of each block, or if it is not recorded, the first page of each block and the OOB area of the last used page The validity of the block is checked based on whether or not the magic number is written.

  FIG. 8B is a diagram illustrating a configuration example of four types of blocks 1 to 4. As shown in FIG. 8A, the blocks 1 to 4 are provided with magic number areas for writing the above-described magic numbers at two or more locations in the block. Here, description will be made assuming that the effective magic number is 0x1234. In block 1, magic numbers indicating validity are described in magic number 1 area 71a and magic number 2 area 71b. Therefore, block 1 can be determined as a valid block. In block 2, a magic number indicating validity is described in the magic number 1 area 71a, but 0xffff is described in the magic number 2 area 71b. This block is considered to have lost power during the writing of the block. Therefore, block 2 can be determined as an invalid block. In block 3, 0xffff is written in both the magic number 1 area 71a and the magic number 2 area 71b, and it can be determined that the block is a free block. In block 4, a magic number indicating validity is described in the magic number 2 area 71b, but 0x0000 is described in the magic number 1 area 71a. This block is considered that the file system explicitly invalidated the block. Therefore, the block 4 can be determined as an invalid block.

  It should be noted that the reason for making a decision at two locations, the first page and the last used page, is that writing to the block is performed on a page-by-page basis, so simply checking the magic number at one location will detect a power failure during block writing It is not possible. For blocks in which data is written only on the first page of the block, the first page and the last used page are the same, so the magic number is written on pages other than the first page, and the last used page Judging by using instead of the magic number.

  In addition, by determining the magic numbers of the two pages in this way, it is ensured that at least the data of the first page is correct data. The reason for this is that when writing multiple pages in a block in succession, if the data written is written in order from the first page and the written data is verified each time the page is written, the first page can be written correctly. This is because there is no going to write to the following pages unless it is. That is, even if the power is cut off when writing data 2 or data 3, if it can be determined that magic number area 71a and magic number area 71b are valid, data 1 in front of magic number area 71a is valid. Guaranteed to be. If important information is stored in the area of data 1, at least this information can be used as normal data. Note that page verification is performed by page verification means. The page verify means is means for verifying whether the written data is correctly written at the time of writing data to the page. Generally, the control apparatus performs it by a program, but it is verified by dedicated hardware. You may make it do.

  In the second stage of mounting, valid blocks in the check block list are analyzed, and valid file candidates or incomplete files are reconstructed. Basically, a valid block should be a component of either a valid file candidate or an incomplete file.

  To reconstruct the file specifically, data is written by adding block information as shown in Table 2 below to the first page of each block. As described above, since the data of the first page of the valid block is guaranteed to be correct, the check of whether the block information is correct may be omitted.

  The file name and file size are not essential in the block information and need not be included. In that case, these may be added to the head of the data (see the block information variation in FIG. 3).

  A more specific example of generating file configuration information will be described with reference to the drawings. FIG. 4 is a diagram showing a configuration example of a block in the file system according to the present embodiment. As shown in FIG. 4, the block Y includes a block information area surrounded by a bold line and a data area 53 other than that. The block information 41 includes a file name 43, a file size 45, a unique file ID 47 assigned by the file system, and a block number 51 indicating the connection order of blocks in the file. Of these, the essential items 41a of the block information 41 are a file ID and a block number, so that the configuration of where the block belongs can be known.

  FIG. 5 is a diagram illustrating a block configuration example related to blocks 1 to 6 shown as examples. In the block 1, the file ID 47 is “456” and the block number 51 is 2/2. 2/2 indicates the second of two blocks. In the block 2, the file ID 47 is “123” and the block number 51 is 1/3. In the block 3, the file ID 47 is “789”, and the block number 51 is 2/4. In the block 4, the file ID 47 is “123”, and the block number 51 is 3/3. In the block 5, the file ID 47 is “123”, and the block number 51 is 2/3. In the block 6, the file ID 47 is “456” and the block number 51 is ½.

  FIG. 6 is a diagram illustrating a configuration example of file configuration information and a configuration example of a file that can be regenerated from the file configuration information. As shown in FIG. 6A, the file configuration information 61 has a file ID 45 and a block list 57. As shown in FIG. 6B, the block list of file 1 with file ID = 123 is composed of block 2, block 5 and block 4 connected in the order of arrows AR1, 2, and 3. Recognize. On the other hand, it can be seen that the file 2 with the file ID = 456 is composed of the blocks 6 and 1 connected in the order of the arrows AR11 and AR12.

  Next, the flow of processing for reconstructing file configuration information will be described with reference to FIGS. 7 (A) and 7 (B). In step S1, file reconstruction is started. In step S2, the block is extracted, and in step S3, it is determined using the block check means whether or not the extracted block is a valid block. If it is not a valid block (N), the process proceeds to step S8. If it is a valid block (Y), the process proceeds to step S4 to read block information. It is determined whether or not the file ID described in the block information read in step S5 is a new file ID. If it is a new file ID (Y), the file ID is registered in step S6, and the process proceeds to step S7. Even if it is not a new file ID (N), the process proceeds to step S7, and this block is added to the corresponding file ID. Next, in step S8, it is determined whether or not all blocks have been processed. If all the blocks have not been processed (N), the process returns to step S2. If all blocks have been processed (Y), the file configuration information generation process is terminated. These pieces of information are registered in the RAM file configuration information storage area. The file registered at this time is an incomplete file or a valid file candidate.

  Next, processing for extracting valid file candidates from these files based on the file configuration information will be described. In step S9, the information registered in the file configuration information storage area of the RAM is read to extract the file ID, and it is determined whether or not all blocks exist in the file having this file ID (step S10). If all the blocks exist (Y), the process proceeds to step S11, and the file configuration information of the corresponding file ID is validated. If all the blocks do not exist (N), the process proceeds to step S12, and all file IDs Whether or not the process is completed is determined. If NO, the process returns to step S9 to repeat the same process. If the processing is completed for all the file IDs (Y), the file reconstruction is completed in step S13. Note that the processing from step S1 to step S8 and the processing from step S9 to step S13 may be parallel processing. As described above, creation and reconfiguration of file configuration information can be easily performed. Since the file configuration information is not stored in the flash memory, writing and reading in the same area can be avoided when the file is reconstructed based only on the block information.

  A file that is not a valid file candidate is an incomplete file. In the third stage of mounting, a valid file is selected from the reconstructed valid file candidates. A valid file is a valid file candidate to be a valid file. If there is no file with the same name in the valid file, the valid file is assumed to be that file, and if there is a file with the same name, the last file is written. Further, it is also a condition that the valid file is not a “file indicating erasure”. The existence of a file with the same name, determination of the file written at the end of the same name, and “file indicating erasure” will be described later.

  When verification is necessary for writing to a block, there is a problem that if the power is cut off during verification, it is not known whether or not the block has been written correctly. If the file is composed of a plurality of blocks and the power is cut off in the final block, the write validity of the final block cannot be determined and the file contents may become abnormal. Therefore, the file system according to this embodiment is characterized in that the file writing is completed by writing a write completion flag in any block in the file. If an area for writing a flag indicating completion of writing of the entire file is provided in some block in the file, it can be easily determined whether or not the file has been written normally only by checking the flag. Therefore, it is possible to easily detect an incomplete file due to a power interruption when writing a file. FIG. 9A shows an example of such a block configuration. As shown in the figure, the block Y has a data area 81 and a write completion flag area 83. FIG. 9B is a diagram illustrating a configuration example of six blocks from block A to block F. Blocks A to C are blocks included in the file 1, and blocks D to F are blocks included in the file 2. Here, the last page of the first block of each file 1 and 2 is provided with a write completion flag area 83a for writing a write completion flag indicating the completion of writing. The write completion flag area may be provided anywhere, but is preferably in the first block. As shown in FIG. 10A, the file 1 composed of the blocks A, B, and C is normally written up to the block C, which is the last block, and the write completion flag area 83a exists in the last page of the block A. Since it is described, it can be seen that the file was written normally. On the other hand, as shown in FIG. 10B, the file 2 is composed of blocks D, E, and F, but no flag is described in the write completion flag area 83b provided on the last page of the block D. With this, it can be determined that the writing of the file is incomplete. That is, in order to determine whether a valid file candidate is a valid file, with respect to the first block of the file among the blocks constituting the file, data indicating that the writing of the entire block of the file has been completed (write complete) A feature is that an area 83 for writing a flag is separately provided.

  As an example of implementation, the last page of the first block is not used for writing file data, but is used for writing this write completion flag. By doing this, by checking whether the write completion flag is written in the first block of a certain file, it is possible to check whether all the blocks of the file having that block as the first block have been written normally. Judgment can be made. The valid candidate file in which the write completion flag is written is regarded as a valid file. The write completion flag is written after the file writing is completed by the completion flag writing means. Further, at the time of mounting, it is read by a completion flag reading means and used to determine whether or not the writing of the file is completed. These writing, reading, and determination are generally performed by the control device by a program, but these may be performed by dedicated hardware.

  The blocks that make up the valid file are removed from the check block list. Blocks that have not become blocks constituting the valid file are removed from the check block list and connected to the erase block list. That is, it is a block constituting an invalid file and an incomplete file. These blocks will be reused. When connecting to the erase block list, the blocks are connected in order from the oldest.

  According to the above-described series of processing, after completion of mounting, free blocks are connected to the free block list, and blocks that need to be erased or are erasable are connected to the erase block list.

  Next, a file writing process will be described with reference to FIG. First, in step S101, a writing process is started. Next, in step S102, the file ID is obtained using the file ID assigning means. In step S103, it is determined whether or not the free block list is empty. If the free block list is empty (YES), the process proceeds to step S104, a block is extracted from the erase block list instead of the free block list, the block is deleted in step S106, and block information is generated in step S107. If NO in step S103, the process proceeds to step S105, a block is extracted from the free block list, and the process proceeds to step S107 to generate block information.

  Next, in step S108, block information and data are written to the block, and in step S109, it is determined whether or not write data remains. Next, in step S110, the completion flag writing means is used to write the write completion flag to the first block, and in step S111, the file ID is updated (indicating that the file ID has been consumed is indicated to the file ID giving means), and in step S112. To add a new file to the file structure information. In step S113, it is determined whether or not the old file exists. If yes (YES), the process proceeds to step S114, where the old file configuration block is added to the erase block list, and in step S115, the old file is deleted from the file configuration information. The writing is terminated (step S116). If the old file does not exist, the process is terminated as it is (step S116). Here, step S110 to step S115 show the procedure of the file update means described later. In other words, if there is an old file with the same name as the file that has been written, the file is invalidated and the new file is validated. If there is no old file, only the new file is valid. The processing from step S110 to step S115 is generally performed by the control device by a program, but may be performed by dedicated hardware.

  As described above, the block used for writing the file is extracted from the free block list. If there is no block in the free block list, the block is taken out from the erase block list, erased, put in the free block list, and taken out from the free block list. If this procedure is used, the blocks in the erase block list will be reused after the free block list is exhausted. Therefore, writing to the blocks in all areas is performed after all areas have been initialized. In the meantime, the block is not reused. Further, the blocks connected to the erase block list are connected in the order in which they were written, and when connecting, they are connected in the order in which they were written. Therefore, a specific block in the erase block list is not reused many times.

  In step S110, when the write completion flag is written in the first block of the file, the file is normally written. That is, if a power failure occurs before step S110, the written block is either an incomplete file or an invalid block, and in the next mounting process, You will be linked to the erase block list. At this time, since the file ID is also assigned to the incomplete file, this file is connected to the end of the erase block list. An invalid block is linked to the top of the erase block list. In this case, it is equivalent to no writing.

  If the power is turned off after step S110, the processing in step 114 and step 115 is always performed in the next mounting process if necessary, so there is no need to consider it in particular.

Next, file update processing will be described.
In a general file system, when a file is updated, a method of directly rewriting a portion where the file is recorded or changing a file name after creating a file with an alias is taken. However, in these methods, there is a risk of data inconsistency or file loss when a power interruption occurs during rewriting or when a power interruption occurs while changing a file name. On the other hand, in order to rewrite a flash memory, it is necessary to erase the entire block, and rewriting only a part is wasteful and the number of times of rewriting is limited, so the above method is suitable. Not.

  Therefore, in the file system according to the present embodiment, it is allowed that a file with the same name exists in the file system, the valid file is the last written file, and waiting for the completion of writing the new file. It is characterized by invalidating old files. As a result, it is possible to eliminate the above-described danger caused by the power interruption at the time of file update. These processes are performed by the file update means.

  Next, description will be made in more detail with reference to the drawings. FIG. 11 is a diagram illustrating an example of file configuration information before file writing. As shown in FIG. 11, the configuration information before writing the file in the file 1 has the file name “AA”, and the file 1 with the file name AA is blocked as indicated by the arrow AR1 and the arrow AR2 following it. It consists of A and block B. The configuration information (1) during the file writing shown in FIG. 12 creates a file 2 having the same name as the file 1 in addition to the file 1 when the file is written to update the file 1 as shown. In the block C included in the file 2, since the file writing has not yet been completed, the flag is not set in the flag area 83b (none). The configuration information (2) during file writing shown in FIG. 13 connects the block C and the block D with respect to the file 2 as shown in the figure. In this state, since the file writing has not been completed yet, no flag is set in the flag area 83b.

  FIG. 14 is a diagram illustrating an example of configuration information immediately after file writing is completed. As shown in FIG. 14, after the blocks D are connected in the file 2, a flag is set in the flag writing area 83a as shown by an arrow AR31 (present). After this, since the flag is present, the file 2 exists even when the power is cut off. Therefore, as shown in FIG. 15, even if the file 1 is invalidated, the file 1 can be updated from the file 2 by using the file 2 continuously. In this state, file configuration information is written to the RAM.

  In this way, by allowing the existence of the same name file and updating with the same name file, there is no risk of losing both the file before update and the file after update even if the power is interrupted in the middle, and it is safe You can update the file.

  Next, the file erasing process will be described. In the file system according to the present embodiment, the file is erased by writing “file indicating that the file has been erased”. To delete a file, it is only necessary to remove the file configuration information from the file configuration information. However, since the file configuration information exists in the RAM, if the power is cut off in that state, it will be deleted in the next mount process. The file should have been restored. Therefore, it is necessary not only to erase the file configuration information but also to erase the blocks constituting the file. However, such a process takes time for erasing a file composed of a plurality of blocks or for a device that takes a long time to erase. Therefore, instead of erasing the blocks constituting the file, a file indicating that the file has been erased is written, and the file and the file erased by the file are not shown to the user. By doing so, even if the power is cut off, the file erased by the next mounting process will not be restored. Here, for example, if a file with the same name having a size of 0 is written as a file indicating that the file has been erased, it is only necessary to write for one block, so that erasure can be performed at high speed. .

  FIG. 16A is a diagram illustrating an example of configuration information before file writing indicating erasure. As shown in FIG. 16A, before the file writing indicating erasure, the file 1 having the file name “AA” 45 is connected to the blocks A, B, It can be seen that it is composed of C. Here, as shown in FIG. 16B, when erasing the file 1 composed of a plurality of blocks, the file 2 including only the block D is generated. This file 2 is a file erasure file and a file of size 0. A flag indicating completion of writing is attached to the flag writing area 83a of the file 2. Then, by overwriting the file 1 with the file 2 of size 0, the file 1 can be deleted in a form that is not visible to the user. In this case, if there is a file with the same name 'AA', the file 2 written last is valid. That is, as shown in FIG. 16C, it becomes possible to easily delete the file 1 by invalidating the file 1 and the file 2. In other words, file erasing can be speeded up.

  As described above, the erasure of the file can be realized by writing “file indicating erasure”. For example, in the above description, the role is assigned to a file having the same file size of 0, but there is no particular limitation. However, it is preferable not to show the “file indicating deletion” to the user. The writing procedure is almost the same as the normal file writing, but after the file writing, a process of connecting the blocks constituting the “file indicating erasure” to the erase block list is added.

  FIG. 25 shows a flowchart of the process. First, in step S121, an erasing process is started. Next, a file ID is acquired in step S122. In step S123, it is determined whether or not the free block list is empty. If the free block list is empty (YES), the process proceeds to step S124, a block is extracted from the erase block list instead of the free block list, the block is erased in step S126, and block information is generated in step S127. At this time, the file size is set to zero. If NO in step S123, the process proceeds to step S125, a block is extracted from the free block list, and the process proceeds to step S127 to generate block information. At this time, the file size is set to zero. In step S128, block information and data are written to the block. In step S129, it is determined whether or not write data remains. Next, in step S130, the write completion flag is written in the first block, the file ID is updated in step S131, the file configuration block is added to the erase block list in step S132, and the old file configuration block is erased in step S133. In step S134, the old file is deleted from the file configuration information, and writing is terminated (step S135).

  In step S130, when the write completion flag is written in the first block of the file, the file is normally written. That is, if a power interruption occurs before step S130, the written block is either an incomplete file or an invalid block, and in the next mounting process, You will be linked to the erase block list. At this time, since the file ID is also assigned to the incomplete file, this file is connected to the end of the erase block list. An invalid block is linked to the top of the erase block list. In this case, it is equivalent to no erasure.

  Even if the power is turned off after step S130, as long as the valid file is determined to be the last written file, the processing from step 132 to step 134 is always performed in the next mounting process if necessary. There is no particular need to consider.

Next, a file ID assigning method and a block reusing method will be described.
The method for reconstructing a file and extracting a valid file based on the file ID assigned to the block at the time of mounting has already been described. In addition, when there is a file with the same name, the last written file is assumed to be a valid file, so that a problem does not occur even if the power is cut off when writing or erasing the file. Furthermore, regarding the blocks that make up a file that is not valid, a method of reusing the file in the order in which the file was written was described.

  These methods are independent of each other. However, if the file writing order can be determined based on the unique file ID, all of them can be satisfied at once. In particular, it is preferable that a new file ID is assigned each time a file is written without reusing the file ID, and that the file ID monotonously increase or monotonously decrease.

  Therefore, in the file system according to the present embodiment, the file ID assigned by the file ID assigning unit is set to the maximum file ID + 1 assigned in the past, and the order in which the files are written is determined based on the size of the file ID. A file writing order determining means is provided.

  When a block that constitutes an invalid file that was generated due to a power interruption during file writing, or no longer needed due to file update or deletion, is left as it is, and a block is required for new writing In addition, in the method of reusing such a block, it is desirable that a specific block is not reused many times. If a file ID is assigned to a file (block), it can be reused from an unnecessary old block. Follow it when mounting. Thereby, there is an advantage that appropriate block allocation can be performed at the time of block reuse. That is, wear leveling is possible.

  FIG. 17 is a diagram showing an example of block connection when writing a file corresponding to wear leveling in the file system according to the present embodiment. FIG. 17A is a diagram illustrating an example of configuration information before file writing. As shown in FIG. 17A, the erase block list is a list connected to block A (AR1), block B (AR2), block C (AR3), block D (AR4), and block G (AR4). It has become. On the other hand, the file 1 is a file having the file name “BB” and is connected to the block E (AR5) and the block F (AR6). Here, the file ID increases from block A to block G.

  FIG. 17B is a diagram illustrating an example of file configuration information immediately after file writing is completed. Of the blocks connected to the erase block list in FIG. 17A, the block is reused from the block with the smaller file ID (the file ID is larger from block A to G). The file 1 has the same configuration as that shown in FIG. 17A, the file 2 has the same name 'BB' as the file 1, and uses the block A and the block B from the erase block list in ascending order of block numbers.

  Next, as shown in FIG. 17C, the file configuration information is updated. That is, the file 1 deletes (invalidates) the file information, and inserts the block included up to that point into the erase block list. In the erase block list, the block E and the block F are inserted between the block D and the block G based on the order of the size of the file ID determined by the file writing order determining means. File 2 is composed of block A and block B.

  If the file 2 is further updated, the file ID of the block A and the block B becomes larger than that of the block G, so that the block A is connected after the block G in the erase block list.

  The writing process will be described again with reference to FIG. First, in step S101, a writing process is started. In step S102, a unique file ID is acquired. Here, the newly acquired file ID is assumed to be the maximum file ID + 1 previously assigned by the file system. In step S103, it is determined whether or not the free block list is empty. If the free block list is empty (YES), the process proceeds to step S104, a block is extracted from the erase block list instead of the free block list, the block is deleted in step S106, and block information is generated in step S107. If NO in step S103, the process proceeds to step S105, a block is extracted from the free block list, and the process proceeds to step S107 to generate block information.

  Next, in step S108, block information and data are written to the block, and in step S109, it is determined whether or not write data remains. Next, in step S110, a write completion flag is written in the first block, and in step S111, the file ID is updated, and the file system is informed that the file ID has been consumed. In step S112, a new file is added to the file configuration information. In step S113, it is determined whether or not the old file exists. If yes (YES), the process proceeds to step S114, where the old file configuration block is added to the erase block list, and in step S115, the old file is deleted from the file configuration information. The writing is terminated (step S116). If the old file does not exist, the process is terminated as it is (step S116). As described in the file writing process, the block used for writing the file is obtained from the free block list. If there is no block in the free block list, the block is extracted from the erase block list, erased, and connected to the free block list to obtain from the free block list.

  This means that in the state where the entire area of the NAND flash memory is initialized, all the blocks are connected to the free block list, and the blocks in the erase block list are not reused until they are used up. That is. Further, the blocks in the erase block list are connected in the order of file ID. Blocks having the same file ID are connected in the order of block numbers. In other words, the block to be reused is the block that has been written most recently among the erasable blocks.

  Next, the flow of the mounting process will be described with reference to FIG. In step S61, a file reconstruction process is started. Next, a block is extracted in step S62, and in step S63, it is determined whether or not the extracted block is a valid block. If not valid (NO), the process proceeds to step S69. If it is valid (YES), block information is read in step S64, and it is determined whether the file ID is a new file ID in step S65. If it is not a new file ID (NO), the process proceeds to step S68. If it is a new file ID (YES), the file ID is registered in step S66, the file ID is updated in step S67, and the process proceeds to step S68. In step S68, the extracted block is added to the corresponding file ID.

  In step S69, it is determined whether or not all blocks have been processed. If NO, the process returns to step S62. If YES, the process proceeds to step S70, and registered file IDs are extracted in descending order. That is, in step S70, the file writing order determination unit is used to sequentially extract the last written file, and the subsequent processing is continued. In step S71, it is determined whether all blocks exist. If YES, the process proceeds to step S72 to determine whether a file with the same name exists. Next, in step S73, the file configuration information of the corresponding file ID is validated, and the process proceeds to step S75. If NO, the process proceeds to step S74, the file configuration blocks are inserted into the erase block list in the order of file IDs, and the process proceeds to step S75. In step S75, it is determined whether or not the processing of all file IDs has been completed. If NO, the process returns to step S70, and if YES, the reconstruction is terminated in step S76.

  In this way, if a power interruption occurs while writing a file, the block consumed by the writing is connected to the end of the erase block list at the next mount processing. This is because the blocks in the erase block list are connected in the order of the file IDs, and the file ID used in the last writing when the power interruption occurred is the maximum at that time. This is because the blocks are reused after the blocks in the erase block list at the time of file writing are used up. That is, it is possible to prevent only a specific block from being reused many times.

  Up to this point, no particular mention has been made regarding the handling of bad blocks, so a brief description will be given here.

  The NAND flash memory includes an initial bad block that exists from the time of shipment and an acquired bad block that occurs due to wear during repeated erasing and writing. These are blocks that may not be able to read data correctly, and should not be used. Such a block records that it is a bad block in the OOB area. Since such bad blocks can be detected during the mounting process, these should be put in the bad block list and not used thereafter.

  Although the initial bad block is recorded as a bad block at the time of shipment, the acquired bad block must be detected and recorded at the time of writing. That is, after data is written to a block, the same block is read again and verified. At this time, although the writing and reading are performed normally, an error occurred in the verification becomes an acquired bad block. Such a block may be recorded as a bad block in the OOB area of the first page, put in the bad block list, and not used thereafter. Once it is recorded in the OOB area that it is a bad block, it can be detected that the block is a bad block even in the mounting process after the power is turned off, so that it is not used.

  As described above, the file system according to the present embodiment can perform high-speed file processing. Also, wear leveling becomes possible. Furthermore, there is an advantage that the file information can be reconfigured even if the power is cut off during the file writing, and the file is not lost or destroyed.

  Next, a file system according to the second embodiment of the present invention will be described. In the first embodiment, file erasure is realized by writing “file indicating erasure”, but there is also a demand for physically erasing data in terms of security. Can be considered.

  In this case, at the time of erasing the file, there is a method of erasing a block actually used by the file instead of writing “file indicating erasure”. However, if the power is cut off after the blocks are erased, these blocks are regarded as free blocks when the file system is mounted next time the power is turned on, and these blocks are immediately reused. In addition, if a power failure occurs after the files constituting these reused blocks are erased, these blocks are reused immediately again.

  That is, if you repeat the cycle of writing a file, erasing the file, turning off the power, turning on the power, a specific block will be used over and over again, which is convenient for flash memory with a limited number of writes. bad.

  Therefore, in the file system according to the second embodiment of the present invention, the file is erased by writing “file indicating that the file has been erased”, and the block is erased for the past file. At this time, the block ID of the block to be erased is also added to the file. In other words, the file is erased by writing “file indicating erasure”, actually erasing the block used by the file to be erased, and “file indicating erasure”. This is realized by adding a block ID of the block. Further, the erased block and the block constituting the “file indicating erasure” are sequentially connected to the erase block list. In this way, even if the power is cut off before the erased block is reused, the erased block is not located in the free block list at the appropriate position in the erase block list during the next mounting process. Can be connected. Because the blocks that make up the “file indicating erasure” are connected to the erase block list during the mount process, if there is such a block, the information of the erased block added to the file is extracted and immediately before that This is because the erase block list when the power is turned off can be reconfigured by inserting the data into. Specifically, as shown in FIG. 19A, as configuration information before erasing the file, blocks A, B, C, D, and G are included in the erase block list as AR1 to AR4. Suppose that Further, it is assumed that the file 1 whose file name 45 is “BB” is composed of a block E and a block F.

  Here, as shown in FIG. 19B, when the file 1 is deleted as the configuration information during the file deletion, the block E and the block F constituting the file 1 are connected to the erase block list. The file 2 that is the “file indicating erasure” is newly generated. At this time, the block A is obtained by extracting the head block of the erase block list. Further, information indicating that the block E and the block F are erased is added to the block A. Thereafter, the block E and the block F are actually erased.

  Finally, as shown in FIG. 19C, the erase block list is added with the block A in FIG. 19B as the configuration information after erasing the file.

  The block A stores information indicating that the block E and the block F have been erased, so that the erase block list can be reconstructed even when the power is cut off.

  The flow of the erasure process will be described using FIG. First, in step S141, an erasing process is started. Next, a file ID is acquired in step S142. In step S143, it is determined whether or not the free block list is empty. If the free block list is empty (YES), the process proceeds to step S144, a block is extracted from the erase block list instead of the free block list, the block is deleted in step S146, and block information is generated in step S147. At this time, the file size is set to zero. If NO in step S143, the process proceeds to step S145, a block is extracted from the free block list, and the process proceeds to step S147 to generate block information. At this time, the file size is set to zero. Next, in step S148, block information and data are written to the block. At this time, the block ID of the block to be actually erased is added as data. Next, in step S149, it is determined whether write data remains. Next, in step S150, the write completion flag is written to the first block, the file ID is updated in step S151, the old file configuration block is added to the erase block list in step S152, and the same name in the erase block list is added in step S153. The blocks constituting the file are erased, the block erased in step S154 is reconnected to the end of the erase block list, the file configuration block is added to the erase block list in step S155, and the old file is added from the file configuration information in step S156. The data is deleted and the writing is terminated (step S157).

  In step S154, the erased block is reconnected to the erase block list (added to the end), so that the erased block is erased until the first block in the erase block list is used up unless the power is cut off. Blocks are never used. On the other hand, if the power is cut off halfway, during the mounting process, these blocks can be reconnected from the free block list to the erase block list according to the procedure described below. It can be returned to the state. As a result, even when a block is erased when a file is erased, only the same block can be prevented from being reused many times.

  Next, the flow of the mounting process will be described with reference to FIG. First, reconstruction is started in step S81, and a block is taken out in step S82. In step S83, it is determined whether the block is a free block. If it is a free block (YES), the process proceeds to step S92, added to the free block list, and proceeds to step S90. If it is not a free block (NO), it is determined in step S84 whether it is a valid block. If it is a valid block (YES), the process proceeds to step S85. If it is not a valid block (NO), it is added to the erase block list in step S91, and the process proceeds to step S90. In step S85, block information is read. In step S86, it is determined whether the file ID is a new file ID. If it is a new file ID, the file ID is registered in step S87, and a block is added to the corresponding file ID in step S88. Next, in step S90, it is determined whether or not the processing of all blocks has been completed. If NO, the process returns to step S82, and if YES, the process proceeds to the step in FIG.

  FIG. 21 is a flowchart showing the flow of processing following FIG. If “YES” in the step S90, the process proceeds to a step S91, and the registered file IDs are extracted in a descending order (a newly created order). In step S92, it is determined whether or not all blocks exist. If NO, the process proceeds to step S100, the file configuration block is added to the erase block list, and the process proceeds to step S96. In the case of YES in step S92, it is determined whether or not the same name file has been registered in step S93. If NO, the process proceeds to step S94 to validate the file configuration information of the corresponding file ID. In step S95, It is determined whether the file is an erasure file. If NO, the process proceeds to step S96. If “YES” in the step S93, the process proceeds to a step S98 to determine whether or not the file is an erased file. If NO, the process proceeds to step S100. If YES, the process proceeds to step S99, the block recorded in this file is taken out from the free block list and added to the erase block list, and the process proceeds to step S100. In step S96, it is determined whether or not all ID processes have been completed. If not completed (NO), the process returns to step S91. If completed (YES), the reconstruction process is terminated in step S97.

  In step S100, the block added to the erase block list is a block that constitutes a file that does not have all the blocks that come from step S92, and a new file that has the same name but that is a valid file that comes from step S98. The block that constitutes the file if it exists, the block that constitutes the newest erased file coming from step S95, that is, the block that constitutes a file that is a valid file in which all blocks exist and is not an erased file Other blocks are linked to the erase block list.

  If the above-mentioned is a basic form, as an extension of the above, in step S148, not only the block ID of the block to be erased but also the file ID and block number of the block to be erased are added to the “file indicating erase”. In the above step S152, when connecting to the erase block, the block is connected to the erase block list in the order of the file ID and the block number. Further, in step S154, after the block is erased, the block is not reconnected. Conceivable. In this case, when remounting the erased block from the free block list to the erase block list at the time of mounting after the power failure occurs, reconnect using the file ID and block number stored together with the block number. Thus, the erase block list can be returned to the state where the power is cut off. This method has the advantage that the order of block reuse is completely the same as the case of not erasing blocks when erasing files and is easy to understand, but has the disadvantage that implementation is a little complicated.

  In both the basic form and the advanced form, only the same block is never reused many times, so either method may be selected to suit the purpose.

  As described above, the file system according to the present embodiment can perform high-speed file processing. Also, wear leveling becomes possible. Furthermore, even if the power is cut off during file writing, the file information can be reconfigured, and the file is not lost or destroyed. Also, erasing a file has the advantage that it can be relieved in terms of security because data is actually erased.

  The present invention can be used for a file system of a flash memory used in an electronic device.

It is a functional block diagram which shows the example of 1 structure of the electronic device shown as an example of the apparatus which can apply the file system by the 1st Embodiment of this invention. It is a figure which shows the area structural example of a NAND type flash memory. It is a figure which shows the variation of header information. It is a figure which shows one structural example of the block in the file system by this Embodiment. It is a figure which shows the block structural example regarding the block 1-6 shown as an example. It is a figure which shows the structural example of a file structure information, and the structural example of the file which can be regenerated from file structure information. It is a flowchart figure which shows the flow of a process of file structure information reconstruction. FIG. 8A is a diagram illustrating a block configuration example for realizing the above technique. FIG. 8B is a diagram illustrating a configuration example of four types of blocks 1 to 4. FIG. 9A shows an example of such a block configuration. FIG. 9B is a diagram illustrating a configuration example of six blocks from block A to block F. 10A is a diagram illustrating a configuration example of the file 1 including the blocks A, B, and C, and FIG. 10B is a diagram illustrating a configuration example of the file 2 including the blocks D, E, and F. is there. It is a figure which shows the example of the file structure information before file writing. It is a figure which shows the structure information (1) during file writing. It is a figure which shows the structure information (2) in writing. It is a figure which shows the example of structure information immediately after file writing completion It is a figure which shows a mode that the update from the file 1 is performed by invalidating the file 1 and using the file 2 continuously. It is a figure which shows the example of the structure information at the time of a file write process. It is a figure which shows the example of a block connection at the time of the file writing corresponding to wear leveling in the file system by this Embodiment. It is a flowchart figure which shows the flow of a process of file structure information reconstruction in consideration of the update of a file. It is a figure which shows the structural example of the file in a file deletion process. It is a flowchart figure which shows the flow of a process of file structure information reconstruction in consideration of the deletion of a file. It is a flowchart figure which shows the flow of the process following FIG. It is a figure which shows the image of the file system of a magnetic storage apparatus. It is a figure which shows the image of the file system of flash memory. It is a flowchart figure which shows the flow of a file writing process. It is a flowchart figure which shows the flow of a file deletion process. It is a flowchart figure which shows the flow of the file deletion process accompanied by deletion of a block.

Explanation of symbols

DESCRIPTION OF SYMBOLS A ... Electronic device, 1 ... Control apparatus (CPU), 3 ... Flash memory, 5 ... RAM (memory), 7 ... Input means, 11 ... Display means, 15 ... Data input / output means.

Claims (6)

The memory area is divided into a plurality of blocks, the data written in the memory area is erased in units of blocks, the block is divided into a plurality of pages, and data is written in the memory area in units of pages. A file system on flash memory,
Block information adding means for adding to the block block information including at least a file ID unique to the file system assigned to the file and a block number indicating the connection order of the blocks in the file;
A file system comprising: file structure information reconstructing means for reconstructing file structure information representing a file structure based on the block information. Magic number adding means for adding a magic number to the first page of each block and pages other than the top when writing data to the block;
A page verifying unit that sequentially writes data from the first page and verifies the data each time data is written to the page;
2. The file system according to claim 1, further comprising block check means for checking the validity of the block based on whether or not a magic number is added to the first page and each page other than the first page of each block.   2. The file system according to claim 1, wherein at least first and second magic number areas for writing the magic number in a block are provided across a data area for writing data.   4. The file system according to claim 3, wherein an area for writing block information is provided in a portion before the first magic number area. A method for reconstructing file configuration information using the file system according to claim 1,
Retrieving a block and reading the block information of a valid block;
And reconnecting blocks having the same file ID in the order of the block numbers based on the file IDs in the block information. A block validity determination method using the file system according to claim 3,
A block validity determination method comprising the steps of: reading the first and second magic numbers, and determining the validity of data in the block based on the validity / invalidity of the magic number based on the read contents.

Images