Data storage management for flash memory devices

Logical units of allocation may be designated as overhead and unallocated and made unavailable for use. During one or more write operations, when one or more logical unit is invalidated, one or more of the unallocated overhead logical units may be designated as available for use and one or more of the invalidated logical units may be designated as overhead.

TECHNICAL FIELD

Embodiments of the invention relate to data storage management techniques for flash memory devices. More particularly, embodiments of the invention relate to management of the reclamation of dirty units of storage space within a flash memory device.

BACKGROUND

In a flash memory system, memory locations are grouped together as blocks. Memory locations within the blocks are consumed as data is written to memory locations within the blocks. A data storage system may be used to map logical memory locations to physical memory locations within the blocks.

As data is deleted the storage space previously allocated for this data is flagged as “dirty” or invalid. When data is overwritten, or appended to, additional unallocated space is consumed and the space previously used may be flagged as dirty. Before the dirty space can be reused the entire block in which the dirty space resides must be erased. If there is still valid data within an erase block that data must first be moved to another block and all references to its location must be updated before an erase can be preformed.

Once this process has been completed the previously unusable dirty space is reclaimed as unallocated space available for reuse. This process of reclaiming dirty space within a block may be, depending upon the type of flash device employed, NOR/NAND, and the dynamics of the storage system itself, relatively time consuming, and has a negative effect on sustained write throughput performance especially as the data within a flash data storage system volume nears capacity such that dirtied space must be reclaimed before a write operation can be completed.

DETAILED DESCRIPTION

In the following description, numerous specific details are set forth. However, embodiments of the invention may be practiced without these specific details. In other instances, well-known circuits, structures and techniques have not been shown in detail in order not to obscure the understanding of this description.

Described herein is a technique that may reduce the frequency of erase block reclaims, which may improve sustained data storage system throughput. In one embodiment, one or more logical units (e.g., blocks) may be logically designated as overhead and unallocated during one or more write operations. In one embodiment, logical units are the smallest block of memory that may be allocated for use. For example, if a logical unit includes 1 Kbytes of memory and 100 bytes of data are to be written, a full logical unit is allocated to store the 100 bytes of data.

When one or more logical units are invalidated, one or more of the unallocated overhead logical units may be logically designated as available for use and one or more of the invalidated logical units may be logically designated as overhead. This use of overhead logical units may postpone reclamation operations, which may improve the sustained write throughput of the system.

FIG. 1is a block diagram of a portion of a memory having multiple logical units. The logical units ofFIG. 1may correspond to any logical grouping of memory locations (e.g., one byte, 4 bytes, 8 bytes, 16 bytes). In one embodiment, the logical units may all be the same size.

FIG. 1includes an initial designation for the portion of memory as well as a subsequent designation after which data may have been written to memory and marked invalid or dirty. In the example ofFIG. 1, logical units of allocation105through140may be initially designated as available and unallocated (labeled “available/unallocated”). According to the initial designation logical units105through140are available for storage of data.

Logical units145through160may be initially designated as unallocated overhead units (labeled “overhead/unallocated”). In one embodiment, the overhead units may be reserved for later allocation. Reserving the overhead units for later allocation may allow reclamation of logical units to be postponed, which may allow memory throughput to be increased.

After a period of time data may be written to one or more of the available logical units. In the example ofFIG. 1, valid data may have been written to logical units105,110,115125and130. The data written to logical units120and135may have been invalidated for any number of reasons. Logical unit140may remain with the available/unallocated designation pending access by an application.

In response to the invalidation of logical units120and135, the designation of logical units120and135may be changed to invalid/overhead and the designation of logical units145and150may be changed to available/unallocated to replace logical units120and135in the operation of the erase block. One result of the use of overhead logical units as described with respect toFIG. 1is that reclamation operations may be postponed, which may result in an improvement to overall sustained data storage system throughput.

FIG. 2is a block diagram of one embodiment of a system hierarchy that may allow management of multiple logical units including overhead logical units. Memory device200may be, for example, a flash memory device. In one embodiment, memory device200may be a NOR flash memory device; however, other types of memory devices (e.g., NAND flash memory) may also be applicable. In one embodiment, memory device200includes one or more erase blocks (230,232,238) that operate as described above. The erase blocks may be coupled with memory control agent205.

In one embodiment, memory control agent205performs addressing operations and/or ECC operations, if necessary. In one embodiment, memory control agent205is implemented as hardware circuitry within memory device200. In alternate embodiments, some or all of the functionality of memory control agent205may be implemented as firmware and/or software.

In one embodiment, memory control agent is communicatively coupled with file system driver220. In general, file system driver220provides the ability for a host system to interact with a specific hardware component (i.e., memory system200). File system driver220may be a combination of software and/or firmware that is executed by a processor of the host system that interacts with memory device200. In one embodiment, the address translation operations described herein are performed by file system driver220. In alternate embodiments, other components, for example, memory control agent205may perform some or all of the address translation and related operations described herein.

In one embodiment, file system driver220may determine timing for a reclamation operation on one or more of the erase blocks. In one embodiment, file system driver220causes the number of dirty logical units in one or more of the erase blocks to be counted and based, at least in part, on the number of dirty logical units in the erase block may cause a reclamation operation to be initiated.

In one embodiment, operating system application program interface (API)240is communicatively coupled with file system driver220. In general operating system API provides a software interface between an operating system executed by the host system and file system driver220. The general functionality of operating system drivers is known in the art and therefore not described in greater detail.

In one embodiment, application260is communicatively coupled with operating system API240to generate requests for access to memory system200. Application260may be any type of application known in the art that may interact with memory system200.

FIG. 3is a flow diagram of one embodiment of a technique for determining a number of dirty logical units in a memory system erase block. The example technique described with respect toFIG. 3may result in an indication of the number of dirty or invalid logical units in an erase block (or other grouping of logical units) to be different than the actual number of dirty or invalid logical units in the erase block, which may result in a delay in initiation of a reclamation operation, as discussed above.

The number of dirty (or invalid) logical units in the erase block may be determined,310. This may be performed by, for example, a memory controller, a state machine or any other component having access to the storage device. The actual number of dirty logical units may be compared with a pre-selected threshold value to determine whether the number of dirty logical units equals or exceeds the threshold value,320. In one embodiment, the threshold value is determined based, at least in part, on the number of initially designated overhead logical units that may be subsequently designated for use.

If the number of dirty logical units exceeds the threshold value, an indication of a number of logical units is generated,340. In one embodiment, the indication of the number of logical units is the number of actual dirty logical units minus the threshold value. By artificially decreasing the number of dirty logical units as interpreted by a control unit external to the erase block, reclamation operations may be delayed to increase sustained system write throughput.

If the number of dirty logical units is less than, or equal to, the threshold value,320, an indication of zero dirty logical units may be generated,330. By generating an external indication of zero logical units until the actual number of logical units is equal to or greater than the threshold value, the reclamation operation may be delayed. That is, the overhead logical units may be used for data storage purposes before the reclamation operation is initiated.

FIG. 4is a block diagram of one embodiment of an electronic system. The electronic system illustrated inFIG. 4is intended to represent a range of electronic systems including, for example, desktop computer systems, laptop computer systems, cellular telephones, personal digital assistants (PDAs) including cellular-enabled PDAs, set top boxes. Alternative computer systems can include more, fewer and/or different components.

Electronic system400includes bus401or other communication device to communicate information, and processor402coupled to bus401that may process information. While electronic system400is illustrated with a single processor, electronic system400may include multiple processors and/or co-processors. Electronic system400further may include random access memory (RAM) or other dynamic storage device404(referred to as main memory), coupled to bus401and may store information and instructions that may be executed by processor402. Main memory404may also be used to store temporary variables or other intermediate information during execution of instructions by processor402.

Electronic system400may also include read only memory (ROM) and/or other static storage device406coupled to bus401that may store static information and instructions for processor402. Data storage device407may be coupled to bus401to store information and instructions. Data storage device407such as a magnetic disk or optical disc and corresponding drive may be coupled to electronic system400.

Electronic system400may also be coupled via bus401to display device421, such as a cathode ray tube (CRT) or liquid crystal display (LCD), to display information to a user. Alphanumeric input device422, including alphanumeric and other keys, may be coupled to bus401to communicate information and command selections to processor402. Another type of user input device is cursor control423, such as a mouse, a trackball, or cursor direction keys to communicate direction information and command selections to processor402and to control cursor movement on display421. Electronic system400further may include network interface(s)430to provide access to a network, such as a local area network. Network interface(s)430may include, for example, a wireless network interface having antenna455, which may represent one or more antenna(e). Antenna455may be a deployable antenna that is part of a removable card as described herein.

In one embodiment, network interface(s)430may provide access to a local area network, for example, by conforming to IEEE 802.11b and/or IEEE 802.11g standards, and/or the wireless network interface may provide access to a personal area network, for example, by conforming to Bluetooth standards. Other wireless network interfaces and/or protocols can also be supported.

IEEE 802.11b corresponds to IEEE Std. 802.11b-1999 entitled “Local and Metropolitan Area Networks, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: Higher-Speed Physical Layer Extension in the 2.4 GHz Band,” approved Sep. 16, 1999 as well as related documents. IEEE 802.11g corresponds to IEEE Std. 802.11g-2003 entitled “Local and Metropolitan Area Networks, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, Amendment 4: Further Higher Rate Extension in the 2.4 GHz Band,” approved Jun. 27, 2003 as well as related documents. Bluetooth protocols are described in “Specification of the Bluetooth System: Core, Version 1.1,” published Feb. 22, 2001 by the Bluetooth Special Interest Group, Inc. Associated as well as previous or subsequent versions of the Bluetooth standard may also be supported.