Methods and apparatus for file management using partitioned file metadata

Management of files in a memory, such as a flash memory, includes storing in the memory a first node including a first type of metadata of the file, a second node including data of the file and a third node including a second type of metadata of the file including file status and memory location information for the first and second nodes. The third node may include a node including memory location information for the second node and a node including an index table that cross-references a memory location for the memory location information for the second node to a memory location of the first node. Methods and devices may be provided.

CROSS-REFERENCE TO RELATED APPLICATION

This application claims priority under 35 U.S.C. §119 from Korean Patent Application No. 10-2007-0103183, filed Oct. 12, 2007, the disclosure of which is hereby incorporated by reference herein in its entirety.

FIELD OF THE INVENTION

The present invention relates to memory systems and methods and, more particularly, to file management systems and methods.

BACKGROUND OF THE INVENTION

Flash memory devices typically are electrically erasable and/or programmable and are often used for data storage in relatively large units. Flash memory is widely used, for example, for storage of operating system and other computer programs for computers and computer-controlled devices, and for storage of video, audio and/or other media files for consumer devices, such as digital cameras and music players.

FIG. 1illustrates a conventional use of flash memory. A CPU11and random access memory (RAM)14communicate over a bus15, which may include data and control signal lines. The RAM14may be used to temporarily store program code, such as operating system and applications programs, and data upon which the CPU11operates. A flash memory controller12is also coupled to the bus15, and controls data transfer between the bus15and a flash memory13, which may be used for non-volatile storage of information used by the CPU11and RAM14. For example, in some applications, a boot program may be stored in the flash memory13, and the CPU11may load the boot program via the flash controller12. In further applications, data, such as audio and video files, may be transferred between the flash memory13and the bus15via the flash controller12.

In some applications, the RAM14may be used to support management of a file system for the flash memory13. Referring toFIG. 2, an application21may read and write data through a file system manager22that interfaces with a flash memory24via flash translation logic (FTL)23that converts disk-oriented address information, i.e., sector addresses, to flash address information, e.g., block and page address information. The FTL24may be implemented, for example, in a flash controller, such as the flash controller12described above with reference toFIG. 1.

A variety of different file systems may be used with flash memory.FIG. 3illustrates a conventional FAT (file allocation table) file system, including a BIOS Parameter Block BPB region, a FAT table region, a directory entry region, and a data region. Flash translation logic FTL converts sector numbers in the FAT file system to block and page numbers, such that the FAT table, directory entries and data are stored in at particular block and page locations in the flash memory.

FIGS. 4 and 5illustrate an example of operations that may occur when using FAT file system in a NAND flash memory application. Referring toFIG. 4, information from a sector6of a FAT system is mapped by a flash translation layer FTL to block0, page2of a flash memory. Referring toFIG. 5, if data in block0, page2is modified, the sector6is remapped to a new page3in block0. In particular, the flash translation layer FTL may search the flash memory for a free page and write the modified data to the free page. The prior page is then marked as invalid until a “garbage collection” process is executed to erase invalid pages so that they may be freed for future writes.

As FAT file systems were originally developed for use with disk drives with different characteristics than flash memory, other types of file systems have been developed that are more tailored to the characteristics of flash memory. Examples of such file systems include JFFS and JFFS2, described in an article “JFFS: The Journalling Flash File System,” by David Woodhouse, presented at the Ottawa Linux Symposium in 2001.

SUMMARY OF THE INVENTION

Some embodiments of the present invention provide methods of managing files in a memory which include storing in the memory a first node including a first type of metadata of the file, a second node including data of the file and a third node including a second type of metadata of the file including file status and memory location information for the first and second nodes. In some embodiments, the methods may further include reading the third node to retrieve memory location information for the first node and/or the second node and accessing the first node and/or the second node based on the retrieved memory location information. The first type of metadata may include information less likely to change than the second type of metadata. For example, the first type of metadata may include file identification information and/or file creation information, and the second type of metadata may include file status information.

According to further embodiments, the third node includes a node including memory location information for the second node and a node including an index table that cross-references a memory location for the memory location information for the second node to a memory location of the first node. The methods may further include retrieving memory locations for nodes including the first type of metadata based on the index table, reading nodes including the first type of metadata responsive to the retrieved memory locations, identifying the first node from among the read nodes including the first type of metadata, retrieving a memory location of the node including memory location information for the second node corresponding to the identified first node and accessing the second node responsive to the retrieved memory location of the node including memory location information for the second node corresponding to the identified first node.

The methods may further include performing a file write operation wherein data of the file and the second type of metadata of the file are written as new nodes in the memory without writing the first type metadata in a new node in the memory. In further embodiments, new nodes including respective portions of the data of the file and new nodes including the second type of metadata including memory location information for nodes including the portions of the data are intermittently written in a periodic or aperiodic fashion.

Further embodiments of the present invention provide methods of managing files in memory including managing a first class of metadata of the file including file identification information and a second class of metadata of the file including file state information and memory location information of the file as respective first and second types of nodes in the memory. Over a series of write operations for the file, the second type of node may be written to the memory more frequently than the first type of node. In a file write operation for the file, writing a new node of the second type to a new memory location without writing a new node of the first type.

According to additional embodiments of the present invention, an apparatus includes a memory control circuit configured to communicate with a memory and a file system manager circuit operatively coupled to the memory control circuit and configured to cause the memory control circuit to store in the memory a first node including a first type of metadata of a file, a second node including data of the file and a third node including a second type of metadata of the file including file status and memory location metadata for the first and second nodes. Further embodiments of the present invention provide computer program products including computer program code embodied in a computer-readable storage medium, the computer program code including program code configured to cause storage in the memory of a first node including a first type of metadata of a file, a second node including data of the file in the memory and a third node including a second type of metadata of the file including file status and memory location information for the first and second nodes. Still further embodiments provide a memory device including a nonvolatile storage medium wherein a file is stored as a first node including a first type of metadata of the file, a second node including data of the file and a third node including a second type of metadata of the file including file status information and memory location information for the first and second nodes.

DETAILED DESCRIPTION OF EMBODIMENT OF THE INVENTION

In the drawings, the sizes or configurations of elements may be idealized or exaggerated for clarity. It will be understood that when an element is referred to as being “connected to” or “coupled to” another element, it may be directly connected or coupled to the other element or intervening elements may be present. In contrast, when an element is referred to as being “directly connected to” or “directly coupled to” another element, there are no intervening elements present. Like numbers refer to like elements throughout. As used herein, the term “and/or” includes any and all combinations of one or more of the associated listed items.

It will be understood that, although the terms first, second, third etc. may be used herein to describe various elements, components and/or sections, these elements, components and/or sections should not be limited by these terms. These terms are only used to distinguish one element, component, or section from another element, region or section. Thus, a first element, component or section discussed below could be termed a second element, component or section without departing from the teachings of the present invention.

Certain embodiments of the present invention are described below in application to flash memory devices. It will be appreciated, however, that the present invention applicable to other types of memory systems including, but not limited to, other types of solid state memory devices, magnetic memory systems and optical memory systems.

Some embodiments of the present invention arise from a realization that more efficient storage of files in devices, particularly devices having characteristics such as those of a flash memory, e.g., block erase and similar constraints, may be achieved by distinguishing between file metadata that is relatively “static,” such as filename, creation date and the like, and metadata that is more “dynamic,” such as file size, last edit date and the like. These different types of information may be stored in memory in two different types of memory “nodes”, i.e., independent memory storage units, such that the “static” metadata need not be rewritten each time the file is updated with new data. This may reduce the amount of memory space that is consumed over a series of updates, and thus can reduce the overhead attributable to memory management functions, such as garbage collection.

FIG. 6illustrates a file system610implemented in a flash memory600according to some embodiments of the present invention. According to the file system610, a file is stored in the flash memory600using three different types of nodes. A first type of node611includes dynamic file metadata, e.g., metadata of the file that tends to change frequently, such as file size, last modified time, file allocation information, and the like. A second type of node612includes static file metadata, e.g., metadata of the file that tends to change less frequently, such as file ID, created date, file name, and the like. A third type of node613includes data of the file, e.g., data other than metadata, such as numeric, graphic, textual, audio and/or video data. The first type of node611, i.e., the dynamic metadata node, includes flash memory location information (e.g., memory addresses) for the second and third types of nodes612,613, such that the dynamic metadata node611may be accessed to find the static metadata node612and the data node(s)613. As will be described in detail below, the use of such an arrangement may allow reduced rewrites of data to flash memory as the file is modified, as the static metadata node612may be left unchanged over several file modifications, such that this metadata need not be rewritten with each file write operation to the flash memory.

FIG. 7illustrates apparatus and methods for implementing a file system including dynamic metadata nodes721, static metadata nodes722and data nodes723in a flash memory720according to some embodiments of the present invention. An application712executing on a processor710(the processor710may include, for example, a computing device, such as microprocessor, and associated memory) provides data to a file system manager713executing on the processor710. The file system manager713is configured to store and retrieve data from a flash memory720. As illustrated, the file system manager713may include a flash space manager714configured to provide space management functions for file management in the flash memory720, such as identification and selection of free memory locations and garbage collection for invalidated memory locations. The file system manager713may further include a file metadata manager715configured to maintain the dynamic metadata node721and the static metadata node722.

It will be appreciated that the nodes721,722,723may be arranged in the flash memory in a number of different ways. For example, the data nodes723may be stored along block/page boundaries, e.g., each data node723may correspond to a page. The nodes721,722,723may also be arranged to make use of partitions defined in the memory space of the flash memory720. For example, as shown inFIG. 7, the static metadata node722and the data node(s)723may be stored in order in “data blocks” of the flash memory device720, while the dynamic metadata node721is stored in a “meta block” of the memory device720. This may facilitate retrieval of the dynamic metadata node721when attempting to access memory location information for the static metadata and data nodes722,723during read operations along the lines described below with reference toFIG. 9, as the file metadata manager715can limit retrieval of file dynamic metadata to the “meta blocks” of the device720without having to read through the data blocks of the memory device720. It will be appreciated that other types of partitioning may be used.

FIG. 8illustrates exemplary operations for writing a file to flash memory using a file system along the lines discussed above according to some embodiments of the present invention. If new static metadata is present, for example, if the file is being newly created and/or if static metadata, such as filename, is being changed, the static metadata is stored in a static metadata node in flash memory (blocks810,820). If the static metadata is not new, for example, if the file is already stored in the flash memory and only changes in dynamic metadata or data are to be made, static metadata of the file already stored remains unchanged. If new data is present, the data is stored in one or more data nodes (blocks830,840). If new data is not present, for example, if the file is being created and includes no data, storage of data may be bypassed. The file write operation may conclude with storage of dynamic metadata in a dynamic metadata node in the flash memory, the dynamic metadata including flash memory location information for the static metadata node and any data node(s) created (block850).

FIG. 9illustrates exemplary operations for reading a file from flash memory using a file system along the lines described above according to further embodiments of the present invention. To read a file, one or more dynamic metadata nodes stored in the flash memory are read to obtain flash memory location information for static metadata nodes associated therewith (block910). One or more static metadata nodes are accessed using this location information to obtain file identification information for files stored in the flash memory (block920). If a static metadata node corresponding to the requested file is located, data nodes containing data of the file are accessed using the flash memory location information in the dynamic metadata node associated with the static metadata node (blocks930,940). If the file is not located in the search of static metadata nodes, an error message (e.g., “file not found”) may be generated (blocks930,950).

According to further embodiments of the present invention, the above-described file system may be further modified by adding a fourth type of file storage node that cross-references static file metadata nodes and dynamic file metadata nodes, such that locating a file need not involve retrieval of all dynamic metadata nodes stored in flash memory. Such an arrangement may help reduce the amount of system memory (e.g., RAM) needed to support the file system.

FIG. 10illustrates flash memory1000arranged using a file system1010according to further embodiments of the present invention. In the file system1010, a file is stored in the flash memory1000using a first type of node1011including an index table that cross-references flash memory location information for a file dynamic metadata node1012with flash memory location information for a static metadata node1013. Similar to the embodiments described above with reference toFIGS. 6-9, the dynamic metadata node1012includes dynamic file metadata, e.g., metadata of the file that tends to change frequently, such as file size, last modified time, file allocation information, and the like. The static metadata node1013includes static file metadata, e.g., metadata of the file that tends to change less frequently, such as file ID, created date, file name, and the like. Similar to the above-described embodiments, one or more data nodes1014include data from the file. The dynamic metadata node1012includes flash memory location information for the static metadata node1013and data node(s)1014, such that the dynamic metadata node1012may be accessed to find the static metadata node1013and the data node(s)1014.

FIG. 11illustrates apparatus and methods for implementing a file system including an index table node1121, a dynamic metadata node1122, a static metadata node1123and one or more data node1124for a file in a flash memory1120according to some embodiments of the present invention. An application1112executing on a processor1110provides data to a file system manager1113executing on the processor1110. The file system manager1113is configured to store and retrieve data from the flash memory1120. As illustrated, the file system manager1113may include a flash space manager1114configured to provide space management functions for file management in the flash memory1120, such as identification and selection of free memory locations and garbage collection for invalidated memory locations. The file system manager1113also includes include a file metadata manager1115configured to manage the dynamic metadata node1122and the static metadata node1123. The file system manager1113further includes a file index manager1116that is configured maintain the file index table node1121, which cross-references flash memory location information for the dynamic metadata node1122and the static metadata node1123.

FIG. 12illustrates exemplary operations for writing a file to flash memory using a file system along the lines discussed above with reference toFIGS. 10 and 11according to some embodiments of the present invention. If new static metadata is present, for example, if the file is being created, the static metadata is stored in a static metadata node in flash memory (blocks1210,1220). If the static metadata is not new, for example, if the file is already stored in the flash memory and only changes in data and dynamic metadata are to be made, static metadata of the file already stored remains unchanged. If new data is present, the data is stored in one or more data nodes (blocks1230,1240). If new data is not present, for example, if the file is newly created and includes no data, storage of data may be bypassed. Dynamic metadata is subsequently stored in a dynamic metadata node in the flash memory, the dynamic metadata including flash memory location information for the static metadata node and any data node(s) created (block1250). Information cross-referencing flash memory location information for the static metadata node and the dynamic metadata node is stored in the flash memory in a file index table node (block1260).

FIG. 13illustrates exemplary operations for reading a file from flash memory using a file system along the lines described above with reference toFIGS. 10 and 11according to further embodiments of the present invention. To read a file, a file index table node stored in the flash memory is accessed (block1310). Using location information from the file index table node, one or more static metadata nodes stored in the flash memory are read to attempt to find the requested file (block1320). If an appropriate static metadata node is found, a corresponding dynamic metadata node is accessed using location information obtained from the index table (blocks1330,1340). If no corresponding static metadata node is found, an error message may be generated (block1360). If a static metadata node corresponding to the requested file is located, data nodes containing data of the file may be accessed using the flash memory location information in the dynamic metadata node associated with the static metadata node (block1350).

According to further embodiments of the present invention, a file system along the lines described above with reference toFIG. 6-9or10-13may be modified to allow files to be stored in a flash memory in a piecewise fashion. Such an approach may be advantageous, for example, in reducing the risk of data corruption occurring while writing a file to flash memory, particularly for files, such as media files, in which small amounts of data can be lost without completely destroying the value of the file.

FIG. 14illustrates apparatus and methods for implementing such a system in flash memory according to some embodiments of the present invention. An application1412executing on a processor1410(the processor1410may include, for example, a computing device, such as microprocessor, and associated memory) provides data to a file system manager1413executing on the processor1410. The file system manager1413is configured to store and retrieve data from a flash memory1420. As illustrated, the file system manager1413may include a flash space manager1414configured to provide space management functions for file management in the flash memory1420, such as identification and selection of free memory locations and garbage collection for invalidated memory locations. The file system manager1413also includes a file metadata manager1415configured to cause storage of a file using a static metadata node1423and dynamic metadata nodes1422a-c, which are created concurrent with creation of respective data nodes1424a-cin intermittent incremental file write operations discussed below with reference toFIG. 15. The file system manager1413further includes a file index manager1416that is configured to manage a file index table node1421that cross-references flash memory location information for the dynamic metadata nodes1422a-cand the static metadata node1423.

In contrast the embodiments described above with reference toFIGS. 10-13, in the file system shown inFIG. 14, files are stored in the flash memory in an intermittent incremental fashion. For example, in some embodiments, portions of the data of a file may be written periodically, with a new, updated dynamic metadata node1422a-cbeing written in each of successive write cycles. Referring toFIG. 14, for example, in a first cycle, upon writing data node1424a, dynamic metadata node1422ais written, including flash memory location information for the data node1424aand the static metadata node1423. In a succeeding cycle, a second data node1424bis written, along with a new dynamic metadata node1422bthat includes flash memory location information for the first data node1424a, the second data node1424band the static metadata node1423, such that the new dynamic metadata node1422bsupersedes the first dynamic metadata node1422a. Similar operations may be performed in the next write cycle for the file for the third data node1424cand the third dynamic metadata node1422c.

FIG. 15illustrates exemplary operations for writing a file to flash memory in a piecewise manner along the lines described above with reference toFIG. 14in accordance with some embodiments of the present invention. If new static metadata is present, for example, if the file is being newly created, the static metadata is stored in a static metadata node in flash memory (blocks1510,1520). If the static metadata is not new, for example, if the file already exists and its static metadata is to be unchanged, static metadata of the file already stored in the flash memory remains unchanged. If new data is present, the data is stored in one or more data nodes (blocks1530,1540). In a recursive loop, portions of the data of the file are incrementally written to the flash memory (block1540), along with storage of dynamic metadata in dynamic metadata nodes (block1550) and storage of an index table in an index table node (block1560). Recursive writing of data nodes, dynamic metadata nodes and index table nodes occurs until no more data remains to be stored for the file (block1570). If new data is not present, for example, if the file is newly created and includes no data, storage of data may be bypassed. It will be appreciated that a file stored in the manner described above with reference toFIGS. 14 and 15may be read using substantially the same operations described above with reference toFIG. 13, except that the operation of accessing a dynamic metadata node corresponding to a static node corresponding to the desired file (block1340) may involve accessing the last written dynamic metadata node, which includes flash memory location information for data nodes written over a series of intermittent write cycles, e.g., the write cycles described with reference toFIG. 14.

It will be understood that, in some embodiments, the intermittent write cycles may be aperiodic and/or differing amounts of data may be written in each cycle. In further embodiments, periodic and aperiodic write operations may be selectively performed based on file type and/or other factors, and that intermittent operations and write operations along the lines ofFIGS. 6-9and10-13may be selectively applied based on file type and/or other factors. For example, relatively short files and/or files for which data integrity is important may be written using operations along the lines described above with reference toFIGS. 10-13, while longer files and/or less important files may be stored using operations along the lines discussed with reference toFIGS. 14 and 15.