US20090327804A1 - Wear leveling in flash storage devices - Google Patents

Abstract

A method of wear leveling in a flash storage device comprising a plurality of data blocks is provided. The method comprises the steps of detecting a data error in a read of dynamic data from a first data segment of a first data block of the plurality of data blocks, correcting the data error, and moving the dynamic data from the first data segment to a second data segment in a second one of the plurality of data blocks.

Description

CROSS-REFERENCE TO RELATED APPLICATION
• The present application claims the benefit of priority under 35 U.S.C. §119 from U.S. Provisional Patent Application Ser. No. 61/075,709, entitled “SOLID STATE DEVICE,” filed on Jun. 25, 2008, the disclosure of which is hereby incorporated by reference in its entirety for all purposes.
FIELD OF THE INVENTION
• The present invention relates to flash storage devices and, in particular, relates to improved wear leveling in flash storage devices.
BACKGROUND OF THE INVENTION
• Flash memory is an improved form of Electrically-Erasable Programmable Read-Only Memory (EEPROM). Traditional EEPROM devices are only capable of erasing or writing one memory location at a time. In contrast, flash memory allows multiple memory locations to be erased or written in one programming operation. Flash memory can thus operate at higher effective speeds than traditional EEPROM.
• Flash memory enjoys a number of advantages over other storage devices. It generally offers faster read access times and better shock resistance than a hard disk drive (HDD). Unlike dynamic random access memory (DRAM), flash memory is non-volatile, meaning that data stored in a flash storage device is not lost when power to the device is removed. For this reason, a flash memory device is frequently referred to as a flash storage device, to differentiate it from volatile forms of memory. These advantages, and others, may explain the increasing popularity of flash memory for storage applications in devices such as memory cards, USB flash drives, mobile phones, digital cameras, mass storage devices, MP3 players and the like.
• Due to flash memory's unique structure, however, each region of memory can only be rewritten a certain number of times before it can no longer reliably hold data. Accordingly, if some regions of memory are written to and rewritten more frequently than others, the lifetime of a flash storage device may be unacceptably shortened by the early failure of those regions of the memory.
SUMMARY OF THE INVENTION
• Various aspects of the subject disclosure solve the foregoing problem by providing improved wear leveling for flash storage devices. The wear leveling improves the lifespan of flash storage devices and improves the reliability of data access therefrom.
• According to one aspect of the subject disclosure, a method of wear leveling in a flash storage device comprising a plurality of data blocks is provided. The method comprises the steps of detecting a data error in a read of dynamic data from a first data segment of a first data block of the plurality of data blocks, correcting the data error, and moving the dynamic data from the first data segment to a second data segment in a second one of the plurality of data blocks.
• According to another aspect of the subject disclosure, a flash storage device comprises a plurality of data blocks and a controller. The controller is configured to detect a data error in a read of dynamic data from a first data segment of a first data block of the plurality of data blocks, to correct the data error, and to move the dynamic data from the first data segment to a second data segment in a second one of the plurality of data blocks.
• According to yet another aspect of the subject disclosure, a machine readable medium carries one or more sequences of instructions for wear leveling in a flash storage device having a plurality of data blocks. Execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of detecting a data error in a read of dynamic data from a first data segment of a first data block of the plurality of data blocks, correcting the data error, and moving the dynamic data from the first data segment to a second data segment in a second one of the plurality of data blocks.
• It is to be understood that both the foregoing summary of the invention and the following detailed description are exemplary and explanatory and are intended to provide further explanation of the invention as claimed.
BRIEF DESCRIPTION OF THE DRAWINGS
• The accompanying drawings, which are included to provide further understanding of the invention and are incorporated in and constitute a part of this specification, illustrate embodiments of the invention and together with the description serve to explain the principles of the invention. In the drawings:
• FIG. 1 illustrates a flash storage device in accordance with one aspect of the subject disclosure;
• FIG. 2 illustrates a flash storage device in accordance with one aspect of the subject disclosure;
• FIGS. 3aand3billustrate a data structure of a flash storage device in accordance with one aspect of the subject disclosure;
• FIGS. 4aand4billustrate a data structure of a flash storage device in accordance with one aspect of the subject disclosure;
• FIG. 5 is a flow chart illustrating a method of wear leveling in a flash storage device comprising a plurality of data blocks in accordance with one aspect of the subject disclosure; and
• FIG. 6 is a block diagram that illustratesprocessor101 in greater detail, in accordance with one aspect of the subject disclosure
DETAILED DESCRIPTION OF THE INVENTION
• In the following detailed description, numerous specific details are set forth to provide a full understanding of the present invention. It will be apparent, however, to one ordinarily skilled in the art that the present invention may be practiced without some of these specific details. In other instances, well-known structures and techniques have not been shown in detail to avoid unnecessarily obscuring the present invention.
• Referring toFIG. 1, a block diagram of a flash storage device according to one aspect of the subject disclosure is depicted. Flashstorage device100 includes acontroller101 and a number of data blocks110₁,110₂,110₃,110₄. . .110_n. While the term “data block” is used throughout the description, it will be understood by those of skill in the art that the term data block is frequently used interchangeably with the term “memory block” in the art. Each data block has a plurality of data segments for storing data. In the present exemplary flash storage device, each data block is illustrated as including 16 data segments. The scope of the present invention, however, is not limited to such an arrangement. Rather, as will be apparent to one of skill in the art, a data block may be configured with more or less than 16 data segments as desired to provide various levels of storage space. For example, in accordance with one aspect of the subject disclosure, a data block may include 32 data segments of 4 kilobytes (kB) each to provide 128 kB of data storage. While data blocks are usually configured with 2ⁿdata segments (e.g., 16, 32, 64, 128, 256, etc.), the scope of the invention is not so limited. Similarly, while each data block110₁-110_nis illustrated as including the same number of data segments, the scope of the invention is not so limited, as a flash storage device may comprise a number of data blocks with differing capacities and/or numbers of data segments. In accordance with one aspect of the subject disclosure, a data block may span over more than one flash memory chip in a storage array of multiple chips. In accordance with another aspect, a data block is stored on a single flash memory chip in a storage array of multiple flash memory chips.
• Three types of data segments are illustrated with different graphical conventions inFIG. 1. In particular, empty data segments, such asdata segment121, are indicated by a white field surrounded with a black line, data segments containing dynamic data (e.g., data which is frequently updated or rewritten), such asdata segment122, are indicated by a shaded field surrounded by a black line, and data segments containing static data (e.g., data which is infrequently updated or rewritten), such asdata segment123, are indicated by a field with diagonal hatches surrounded by black lines. In addition, a data segment containing data which has become corrupted or is otherwise erroneous, such asdata segment124, is indicated by intersecting diagonal black lines. A data segment may contain erroneous data as a result of the degradation of a data block that has been written to/rewritten so many times that the hardware thereof has become unreliable. Other manners in which the data of a data segment may be corrupted or otherwise rendered erroneous will be readily apparent to those of skill in the art, and are omitted herefrom for brevity's sake.
• Flashstorage device100 further includes a data structure for storing information associated with each data block110₁-110_n. According to one exemplary aspect of the subject disclosure, the data structure may store information about the number of data errors that have occurred in read operations corresponding to each of the data blocks. For example, the data structure may store information indicating that data block110₁has experienced three read errors, that data block110₂has experienced one read error, that data block110₃has experienced two read errors, etc. This information may allowcontroller101 to select a data block from which to move dynamic data in favor of static data, as described in greater detail below.
• According to one exemplary aspect of the subject disclosure, the data structure may include information about the number of data read errors that have occurred in each data block sinceflash storage device100 was last powered on. In accordance with an alternative aspect, the data structure may include information about the total number of data read errors that have occurred in each data block since some time prior to the last timeflash storage device100 was powered on (e.g., sinceflash storage device100 was initialized, formatted, manufactured, first powered on, etc.). In accordance with still another aspect of the subject disclosure, the data structure may include information about the number of data read errors that have occurred in each data block both sinceflash storage device100 was last powered on and since a time previous to the last timeflash storage device100 was powered on (e.g., sinceflash storage device100 was initialized, formatted, manufactured, first powered on, etc.).
• Information regarding the number of data read errors associated with a given data block may be used to determine whether the data stored therein is dynamic or static. For example, if the number of read errors of a certain data block, such as data block110₂, is below a predetermined threshold (e.g., 2), thencontroller101 may be configured to determine that the data segments therein contain “static” data. If the number of read errors of a certain data block, such as data block110₃, meets or exceeds a predetermined threshold (e.g., 2), thencontroller101 may be configured to determine that the data segments therein contain “dynamic” data. In this way, data which is subject to more frequent write or rewrite operations (e.g., operations which may reduce the reliability of the associated data segments and/or data blocks) is determined to be dynamic data, and can be relocated to data blocks with less wear (e.g., as determined by the number of data read errors associated therewith).
• While in the foregoing description, a data block has been described as being determined to contain static or dynamic data based upon a predetermined threshold of two data read errors, the scope of the present invention is not limited to such an arrangement. Rather, as will be apparent to those of skill in the art, any threshold value greater than 0 may be used to determine whether a data block contains static or dynamic data. Moreover, the predetermined threshold may be subject to change as necessary to characterize at least some of the data inflash storage device100 as static, as is described in greater detail below. Accordingly, the terms “dynamic” and “static” are used herein to describe the relative frequency with which data is updated among data blocks in a flash storage device, and do not imply a rigid or unchanging definition. Moreover, data which is at one time determined to be static may later be determined to be dynamic, and vice versa, as is set forth in greater detail below.
• WhileFIG. 1 graphically illustrates the three data read errors that have occurred in data block110₁as occurring in three discrete data segments, it will be readily understood that a data block may experience multiple data read errors arising from multiple reads of data from a single data segment. As can be seen with reference toFIGS. 3aand3bbelow, the information concerning the number of data read errors associated with a given data block need not include information regarding which particular data segments from which the data read errors have arisen. Accordingly, the graphical convention ofFIGS. 1 and 2 is merely intended to provide a simple illustration of data blocks with multiple data read errors, and not to specify that particular data segments are associated with information regarding a number of data read errors occurring therein. According to another exemplary aspect of the subject disclosure, however, the data structures may contain information associating particular data segments with a status indicator which indicates a number of data read errors associated therewith.
• According to one aspect of the subject disclosure, upon a read ofdynamic data segment124,controller101 may detect an error in the read data (e.g., using an error checking algorithm or the like). Upon detecting the error,controller101 may be configured to correct the data error in data segment124 (e.g., by utilizing an error correction code, parity information, or the like). After correcting the data error,controller101 may be configured to move the data from data segment124 (or the entire data block110₁) to one or more data segments of an available data block, such as data block110₄.Controller101 may be further configured to move data (e.g., from a single data segment, or from multiple data segments) which has been determined to be static data from one or more data segments of another data block, such as data block110₂, to one or more data segments of data block110₁. In accordance with one aspect of the subject disclosure,controller101 is configured to move data by first copying the data from the data segment(s) of one data block to the data segment(s) of another data block, and then deleting the first data block.
• The foregoing operation may be more easily understood with reference toFIG. 2, which illustratesflash storage device100 after the foregoing operations have been completed, in accordance with one aspect of the subject disclosure. As can be seen with reference toFIG. 2, the dynamic data previously located in the data segments of data block110₁have been moved to data segments of data block110₄, while the static data previously located in the data segments of data block110₂have been moved to data segments of data block110₁. For the sake of clarity, the crossed diagonal lines used to indicate the data read errors experienced by data blocks110₁and110₂have been omitted fromFIG. 2.
• According to various aspects of the subject disclosure, data in a data block may be determined to be “static” data in any one of a number of ways. As indicated above, if the data block in question is associated in a data structure with a number of data read errors which is below a predetermined threshold, the data in the data block may be determined to be static. Alternatively, a data block may be determined to contain static data based upon the time at which the data block in question was last written to (which information may be stored in a data structure of flash storage device100). For example, if the data block in question has not been written to for a predetermined period of time (e.g., whether one hour, one day, etc.), the data therein may be determined bycontroller101 to be static. Similarly, if the data block in question has not been written to sinceflash storage device100 was last powered on, the data in the data block may be determined to be static. According to another aspect of the subject disclosure, information about the time of the most recent data write operation in a block of data may “follow” that data if it is moved to a different data block, such that data in a data block may be determined to be dynamic based upon the time of a last write operation even after that data is moved from a different data block that has experienced a number of read errors above the threshold for dynamic data. In this regard,controller101 may consider both the number of data read errors associated with a data block as well as the time of a last data write operation thereto in determining whether or not a data block contains static or dynamic data.
• In this regard,flash storage device100 may include a data structure which stores information about a time at which each of the data blocks110₁-110_nwas last written to, in accordance with one aspect of the subject disclosure. The information about a time at which each of the data blocks was last written to may be as simple as a status indicator which indicates whether an associated data block has been written to sinceflash storage device100 was last powered on, according to one exemplary aspect. For example, the data structure may store information indicating that data block110₁has been written to since the last timeflash storage device100 was powered on, that data block110₄has not been written to sinceflash storage device100 was last powered on, etc. According to another exemplary aspect of the subject disclosure, the status indicator may indicate a time of the last write operation in an associated data block (e.g., with reference to a clock signal).
• According to one aspect of the subject disclosure, ifcontroller101 is configured to consider a number of data read errors associated with a data block in determining whether or not that data block contains static data, it may be necessary to revise the threshold number of data errors in making such a determination. For example, if a flash storage device has been in operation for a significant length of time, the foregoing wear-leveling technique may result in every data block in the flash storage device having experienced some number of data read errors. Accordingly, if every data block is determined to have experienced a number of data read errors in excess of thethreshold value controller101 uses to determine whether or not data is static,controller101 may be configured to revise the threshold value upwards, until at least one data block has a number of data read errors below the revised threshold value.
• After moving data from one data block to another,controller101 may be configured to update an address mapping associated with each data block to properly identify the new location of the moved data, according to one aspect of the subject disclosure. For example,controller101 may maintain a list of logical addresses (by which a host device identifies data to flash storage device100) corresponding to the physical address (e.g., of a data block and/or data segment) in which data is stored inflash storage device100. Upon moving data from one data block to another, as described above with reference toFIGS. 1 and 2,controller101 may be configured to update the physical addresses of the relocated data to ensure that the logical address properly identifies the location thereof.
• Controller101 may be further configured to modify the data structures containing information associated with the data blocks affected by the foregoing operations. This may be more easily understood with reference toFIGS. 3aand3b,which illustrate a data structure offlash storage device100 in accordance with one aspect of the subject disclosure.
• As can be seen with reference toFIG. 3a,prior to the foregoing operations,data structure300 includes a linkedlist300athat associates each data block with a number of data read errors experienced thereby (e.g., in the present exemplary embodiment, since the last timeflash storage device100 was powered on). In this regard, data block110₁has experienced three read errors, data block110₂has experienced one read error, data block110₃has experienced two read errors, data block110₄has experienced no read errors, and data block110_nhas experienced no read errors. After the foregoing operations (described with reference toFIGS. 1 and 2) are complete,controller101 may be configured to updatedata structure300 such that updated linkedlist300bshown inFIG. 3breflects the updated values for the number of data read errors experienced by each data block. In this regard, as can be seen with reference toFIG. 3b,the number of data read errors associated with data block110₁has been changed to 0. Moreover, the data that had previously been categorized as dynamic when it was located in data block110₁(having a number of read errors exceeding the threshold) is categorized as static after being moved to data block110₄(as can be seen with reference toFIG. 3b,which indicates that a number of read errors associated with the data now located in data block110₄is 0).
• Turning toFIGS. 4aand4b,a similar updating of the data structure which contains information regarding the last time a data block has been written to (or, more specifically, whether a data block has been written to sinceflash storage device100 was last powered on) is illustrated in accordance with one aspect of the subject disclosure. Prior to the foregoing operations,data structure400 includes a linkedlist400athat indicates whether or not each data block110₁-110_n, has been written to sinceflash storage device100 was last powered on. As can be seen with reference toFIG. 4a,data blocks110₁,110₂and110₃are each associated with a 1 (by whichconvention controller101 indicates that these data blocks have been written to since the last timeflash storage device100 was powered on), and data blocks110₄and110_n, are each associated with a 0 (by whichconvention controller101 indicates that these data blocks have not been written to since the last timeflash storage device100 was powered on). After the foregoing wear-leveling operations (described with reference toFIGS. 1 and 2) are complete,controller101 may be configured to updatedata structure400 such that updated linkedlist400bshown inFIG. 4breflects that data block110₄has been written to since the last timeflash storage device100 was powered on (i.e., by changing the associated 0 to 1).
• The foregoing exemplary data structures may be provided on a flash storage device in any one of a number of manners. For example, in accordance with one exemplary aspect of the subject disclosure, the data structure may be provided in a random access memory (RAM) or dynamic random access memory (DRAM) module offlash storage device100. According to one aspect,controller101 may include DRAM or RAM modules, as illustrated in greater detail below with respect toFIG. 6. Alternatively, the data structure may be provided in one of the plurality of data blocks of flash storage device. Where the data structure is stored may depend upon a power state of the flash storage device. When in an unpowered condition, the data structure may be copied from a volatile storage medium (e.g., DRAM) to a non-volatile storage medium (e.g., a data block) to prevent the information in the data structure from being lost when the reserve power of flash storage device100 (e.g., provided by capacitors, super-capacitors, batteries, etc.) is exhausted.
• While in the foregoing exemplary embodiments, the data structures have been illustrated as including a single linked list, the scope of the present invention is not so limited. Rather, as will be apparent to those of skill in the art, information regarding the number of data read errors corresponding to each data block of a flash storage device and information regarding the last time a data write operation took place in a data block of a flash storage device may be provided in any one of a number of ways. For example, rather than a single linked list, a data structure may comprise multiple linked lists, whereby data blocks with similar numbers of data read errors may be included on a single list (e.g., one list indicating data blocks with between 0 and 7 data read errors, another list indicating data blocks with between 8 and 15 data read errors, etc.). In such an embodiment,controller101 may provide a “rough” sorting feature by organizing data blocks into “bins” of similarly situated data blocks. This allowscontroller101 to simply select one data block from the unordered list representing data blocks with fewer read errors (e.g., data blocks with between 0 and 7 read errors) to designate as “static” data blocks.Controller101 may update the unordered lists when an operation changes the number of data read errors detected in a given data block, moving the data block to the appropriate list that reflects the updated number of data read errors.
• While in the foregoing exemplary embodiments, the data structures have been described as including one or more linked lists for keeping track of the number of data read errors in each data block of a flash storage device and the time of a last data write operation in each data block of a flash storage device, the scope of the present invention is not limited to such an arrangement. Rather, as will be apparent to those of skill in the art, any one of a number of different data structures may be employed to maintain this information, including, for example, tables, pointers, and the like.
• While in the foregoing exemplary embodiments, data moving operations have been described with reference to block-level copying, the scope of the present invention is not limited to this particular arrangement. Rather, according to one aspect of the subject disclosure, only valid data segments are copied from one data block to another before the first data block is erased. Moreover, the valid data segments copied from the first data block to the destination data block may be combined with valid data segments from other data blocks, so that the destination data block is provided with enough valid data segments to fully populate the destination data block with valid data. The valid data segments may be copied from other data blocks that have been identified as containing dynamic or static data (e.g., as a result of a read error count of a time of last write operation), as appropriate, or may be copied from other data blocks based upon any one of a number of other selection criteria (e.g., data blocks containing the number of data segments necessary to fully populate the destination data block). After such an operation, the other data blocks may be erased and labeled as “free” blocks for future use, although the read error count associated with these data blocks may or may not be changed.
• While in the foregoing exemplary embodiments, data moving operations have been described as triggered by a determination that these data blocks contain dynamic or static data, the scope of the present invention is not limited to this particular arrangement. Rather, as will be readily apparent to those of skill in the art, data moving operations may be triggered by any one of a number of other determinations. For example, in accordance with one aspect of the subject disclosure, data moving operations may be triggered by a background operation that combines the valid data segments of various blocks into one data block.
• FIG. 5 is a flow chart illustrating a method of wear leveling in a flash storage device having a plurality of data blocks, in accordance with one aspect of the subject disclosure. The method begins withstep501, in which a data error is detected in a read of dynamic data from a first data segment of a first data block. Instep502, the data error is corrected (e.g., using an error correction code, parity bits, or the like). Instep503, the dynamic data is moved to a second data segment of a second one of the plurality of data blocks. Instep504, a third data block is selected based on an associated status indicator (e.g., identifying a number of data read errors associated with the third data block, or identifying a time at which the third data block was last written to), and instep505, static data is moved from a third data segment of the third data block to an available data segment of the first data block.
• FIG. 6 is a block diagram that illustratescontroller101 in greater detail, in accordance with one aspect of the subject disclosure.Controller101 includes abus602 or other communication mechanism for communicating information, and aprocessor604 coupled withbus602 for processing information.Controller101 also includes a machine-readable media606 for storing a data structure, such as a random access memory (“RAM”) or other dynamic storage device, coupled tobus602 for storing information and instructions to be executed byprocessor604.Media606 may also be used for storing temporary variables or other intermediate information during execution of instructions byprocessor604.Media606 may also comprise non-volatile storage media, such as flash memory, a magnetic disk or an optical disk, coupled tobus602 for storing information and instructions.Controller101 may be coupled via I/O module608 to data blocks110₁-110_n, and to an external system with whichflash storage device100 communicates.
• According to one aspect of the present invention, wear leveling in a flash storage device is performed bycontroller101 in response toprocessor604 executing one or more sequences of one or more instructions contained inmedia606. Such instructions may be read intomedia606 from another machine-readable medium, such as through I/O module608. Execution of the sequences of instructions contained inmedia606 causesprocessor604 to perform the process steps described herein. One or more processors in a multi-processing arrangement may also be employed to execute the sequences of instructions contained inmedia606. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement various embodiments of the present invention. Thus, embodiments of the present invention are not limited to any specific combination of hardware circuitry and software.
• The term “machine-readable medium” as used herein refers to any medium that participates in providing instructions toprocessor604 for execution. Such a medium may take many forms, including, but not limited to, non-volatile media, volatile media, and transmission media. Non-volatile media include, for example, optical or magnetic disks. Volatile media include dynamic memory, such asmemory606. Transmission media include coaxial cables, copper wire, and fiber optics, including the wires that comprisebus602. Transmission media can also take the form of acoustic or light waves, such as those generated during radio frequency and infrared data communications. Common forms of machine-readable media include, for example, floppy disk, a flexible disk, hard disk, magnetic tape, any other magnetic medium, a CD-ROM, DVD, any other optical medium, punch cards, paper tape, any other physical medium with patterns of holes, a RAM, a PROM, an EPROM, a FLASH EPROM, any other memory chip or cartridge, a carrier wave, or any other medium from which a computer can read.
• The description of the invention is provided to enable any person skilled in the art to practice the various embodiments described herein. While the present invention has been particularly described with reference to the various figures and embodiments, it should be understood that these are for illustration purposes only and should not be taken as limiting the scope of the invention.
• There may be many other ways to implement the invention. Various functions and elements described herein may be partitioned differently from those shown without departing from the spirit and scope of the invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and generic principles defined herein may be applied to other embodiments. Thus, many changes and modifications may be made to the invention, by one having ordinary skill in the art, without departing from the spirit and scope of the invention.
• A reference to an element in the singular is not intended to mean “one and only one” unless specifically stated, but rather “one or more.” The term “some” refers to one or more. Underlined and/or italicized headings and subheadings are used for convenience only, do not limit the invention, and are not referred to in connection with the interpretation of the description of the invention. All structural and functional equivalents to the elements of the various embodiments of the invention described throughout this disclosure that are known or later come to be known to those of ordinary skill in the art are expressly incorporated herein by reference and intended to be encompassed by the invention. Moreover, nothing disclosed herein is intended to be dedicated to the public regardless of whether such disclosure is explicitly recited in the above description.

Claims (37)

1. A method of wear leveling in a flash storage device comprising a plurality of data blocks, the method comprising the steps of:

detecting a data error in a read of dynamic data from a first data segment of a first data block of the plurality of data blocks;

correcting the data error; and

moving the dynamic data from the first data segment to a second data segment in a second one of the plurality of data blocks.

2. The method according toclaim 1, wherein the available data segment of the first data block is the first data segment.

3. The method according toclaim 1, wherein the step of correcting the data error is performed using an error correction code.

4. The method according toclaim 1, wherein the step of moving the dynamic data from the first data segment to the second data segment in the second one of the plurality of data blocks comprises:

writing the dynamic data to the second data segment, and

erasing the first data block.

5. The method according toclaim 1, further comprising the step of:

moving static data from a third data segment of a third data block to an available data segment of the first data block.

6. The method according toclaim 5, wherein the step of moving the static data from the third data segment to the available data segment of the first data block comprises:

writing the static data to the available data segment of the first data block, and

erasing the third data block.

7. The method according toclaim 5, wherein the step of moving the static data to the available data segment of the first data block comprises:

changing an address mapping associated with the static data from the third data segment to the available data segment of the first data block.

8. The method according toclaim 1, wherein the step of moving the dynamic data to the second data segment comprises:

changing an address mapping associated with the dynamic data from the first data segment to the second data segment.

9. The method according toclaim 1, wherein each data block of the plurality of data blocks is associated with a first status indicator that indicates a number of data errors that have occurred in reads of data segments of the associated data block.

10. The method according toclaim 9, wherein the first status indicator indicates the number of data errors that have occurred in reads of data segments of the associated data block since the flash storage device was last powered on.

11. The method according toclaim 9, further comprising adjusting the first status indicator associated with the first data block to indicate that the number of data errors that have occurred in reads of data segments of the first data block is 0.

12. The method according toclaim 9, wherein the first data segment is determined to comprise dynamic data based upon the first status indicator associated with the first data block exceeding a predetermined threshold.

13. The method according toclaim 9, further comprising:

selecting a third data block based on the associated first status indicator indicating that a number of data errors that have occurred in reads of data segments of the third data block does not exceed a predetermined threshold; and

moving static data from a third data segment of the third data block to an available data segment of the first data block.

14. The method according toclaim 13, wherein if the first status indicator for each of the plurality of data blocks exceeds the predetermined threshold, the predetermined threshold is modified such that the first status indicator of at least one of the plurality of data blocks does not exceed the predetermined threshold.

15. The method according toclaim 1, wherein each data block of the plurality of data blocks is associated with a second status indicator that indicates a time of the last data write operation to a data segment of the associated data block.

16. The method according toclaim 15, further comprising selecting a third data block based on the associated second status indicator indicating that the time of the last data write operation to a data segment of the third data block was prior to a predetermined time; and

moving static data from a third data segment of the third data block to an available data segment of the first data block.

17. The method according toclaim 15, wherein the second status indicator indicates whether data has been written to a data segment of the associated data block since the flash storage device was last powered on.

18. The method according toclaim 17, further comprising selecting a third data block based on the associated second status indicator indicating that no data has been written to a data segment of the third data block since the flash storage device was last powered on; and

moving static data from a third data segment of a third data block to an available data segment of the first data block.

19. A flash storage device comprising:

a plurality of data blocks; and

a controller configured to:

detect a data error in a read of dynamic data from a first data segment of a first data block of the plurality of data blocks,

correct the data error, and

move the dynamic data from the first data segment to a second data segment in a second one of the plurality of data blocks.

20. The flash storage device according toclaim 19, wherein the available data segment of the first data block is the first data segment.

21. The flash storage device according toclaim 19, wherein the controller is configured to correct the data error with an error correction code.

22. The flash storage device according toclaim 19, wherein the controller is configured to move the dynamic data from the first data segment to the second data segment in the second one of the plurality of data blocks by:

writing the dynamic data to the second data segment, and

erasing the first data block

23. The flash storage device according toclaim 19, wherein the controller is further configured to:

move static data from a third data segment of a third data block to an available data segment of the first data block.

24. The flash storage device according toclaim 23, wherein the controller is configured to move the static data from the third data segment to the first data block by:

writing the static data to the available data segment of the first data block, and

erasing the third data block.

25. The flash storage device according toclaim 23, wherein the controller is further configured to change an address mapping associated with the static data from the third data segment to the first data segment.

26. The flash storage device according toclaim 19, wherein the controller is further configured to change an address mapping associated with the dynamic data from the first data segment to the second data segment.

27. The flash storage device according toclaim 19, wherein each data block of the plurality of data blocks is associated with a first status indicator that indicates a number of data errors that have occurred in reads of data segments of the associated data block.

28. The flash storage device according toclaim 27, wherein the first status indicator indicates the number of data errors that have occurred in reads of data segments of the associated data block since the flash storage device was last powered on.

29. The flash storage device according toclaim 27, wherein the controller is further configured to adjust the first status indicator associated with the first data block.

30. The flash storage device according toclaim 27, wherein the first data segment is determined to comprise dynamic data based upon the first status indicator associated with the first data block exceeding a predetermined threshold.

31. The flash storage device according toclaim 27, wherein the controller is configured to:

select a third data block based on the associated first status indicator indicating that a number of data errors that have occurred in reads of data segments the second data block does not exceed a predetermined threshold; and

move static data from a third data segment of the third data block to an available data segment of the first data block.

32. The flash storage device according toclaim 31, wherein if the first status indicator for each of the plurality of data blocks exceeds the predetermined threshold, the controller is configured to modify the predetermined threshold such that the first status indicator of at least one of the plurality of data blocks does not exceed the predetermined threshold.

33. The flash storage device according toclaim 19, wherein each data block of the plurality of data blocks is associated with a second status indicator that indicates a time of the last data write operation to a data segment of the associated data block.

34. The flash storage device according toclaim 33, wherein the controller is configured to:

select a third data block based on the associated second status indicator indicating that the time of the last data write operation of the second data block was prior to a predetermined time; and

move static data from a third data segment of the third data block to an available data segment of the first data block.

35. The flash storage device according toclaim 33, wherein the second status indicator indicates whether data has been written to a data segment of the associated data block since the flash storage device was last powered on.

36. The flash storage device according toclaim 33, wherein the controller is configured to:

select a third data block based on the associated second status indicator indicating that no data has been written to a data segment of the third data block since the flash storage device was last powered on; and

move static data from a third data segment of the third data block to an available data segment of the first data block.

37. A machine readable medium carrying one or more sequences of instructions for wear leveling in a flash storage device having a plurality of data blocks, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

detecting a data error in a read of dynamic data from a first data segment of a first data block of the plurality of data blocks;

correcting the data error; and

moving the dynamic data from the first data segment to a second data segment in a second one of the plurality of data blocks.

Images