Reducing erase cycles in an electronic storage device that uses at least one erase-limited memory device

A solution for reducing erase cycles in an electronic storage device that uses at least one erase-limited memory device is disclosed.

FIELD OF INVENTION

The present invention relates to solutions for reducing erase cycles. More particularly, the present invention pertains to solutions for reducing erase cycles in an electronic storage device that uses at least one erase-limited memory device, such as NAND (Not And) flash memory devices (non-volatile memory devices).

BACKGROUND

Electronic storage devices that respectively employ a memory subsystem that includes memory devices or modules that use non-volatile memory cells are commonly known and are sometimes referred to as solid-state storage devices. The computer device industry has increased the adoption of these solid-state storage devices due to certain advantages offered by these types of storage devices over other forms of storage devices, such as rotational drives. The adoption of solid state storage devices as enhancement or even a replacement to rotational drives is not without some difficulty because many conventional computer devices, sometimes referred to as “hosts”, use host operating systems, file systems, or both that are optimized for use with rotational drives rather than solid state storage devices. For example, unlike rotational drives, solid state storage devices that use NAND flash memory devices, also referred to as “flash drives”, suffer from write limitations because these devices require an erase cycle before a write cycle can be performed on or within a flash block of a flash memory device. Currently, flash block can only support a limited number of erase cycles and after an approximate number of these erase cycles are performed on a flash block, the flash block will eventually be unable to store data in the flash block in a reliable manner. For instance, data stored in a flash block that is at or near its erase cycle limit may start exhibiting bit errors which will progressively increase in size until this data can no longer be reliably read from the flash block.

To reduce erase cycles, one traditional solution is to use wear-leveling but this does not actually reduce or minimize erase cycles. Instead, wear-leveling simply spreads out erase cycles by re-mapping writes from one flash block to another flash block. Another solution is to employ a write-in-place technique but this suffers from the disadvantage of increasing erase-cycles in embodiments that use control blocks.

Consequently, a need exists for reducing erase cycles in electronic storage devices, such as solid-state storage devices, that use erase-limited memory devices.

SUMMARY

A solution for reducing erase cycles in an electronic storage device that uses at least one erase-limited memory device is disclosed.

DETAILED DESCRIPTION OF THE INVENTION

In the following detailed description, for purposes of explanation, numerous specific details are set forth to provide a thorough understanding of the various embodiments of the present invention. Those of ordinary skill in the art will realize that these various embodiments of the present invention are illustrative only and are not intended to be limiting in any way. Other embodiments of the present invention will readily suggest themselves to such skilled persons having the benefit of this disclosure.

In addition, for clarity purposes, not all of the routine features of the embodiments described herein are shown or described. One of ordinary skill in the art would readily appreciate that in the development of any such actual implementation, numerous implementation-specific decisions may be required to achieve specific design objectives. These design objectives will vary from one implementation to another and from one developer to another. Moreover, it will be appreciated that such a development effort might be complex and time-consuming but would nevertheless be a routine engineering undertaking for those of ordinary skill in the art having the benefit of this disclosure.

The various embodiments disclosed herein are not intended to limit the scope and spirit of the herein disclosure. For example, the present invention may be used to enhance the basic architecture of existing storage solutions and devices that use semiconductor memory devices, such as flash memory, including the device disclosed in U.S. Pat. No. 5,822,251, entitled “Expandable Flash-Memory Mass-Storage Using Shared Buddy Lines and Intermediate Flash-Bus Between Device-Specific Buffers and Flash-Intelligent DMA controllers”, issued on Oct. 13, 1998, hereinafter named the “Patent”, and which is hereby incorporated by reference as if fully set forth herein.

With reference toFIG. 1, the present invention reduces erase cycles in an electronic storage device10that uses at least one erase-limited memory device. An erase-limited memory device is any memory device that can only support a limited number of write cycles before exhibiting bit errors. These bit errors will progressively increase in size until data can no longer be reliably read from the memory device. For instance, an erase-limited memory device may be a NAND flash memory device. A NAND flash memory device is a erase-limited memory device because a NAND flash memory device requires an erase-cycle on a flash block before the flash block may be used to receive a write operation, and the number of erase-cycles that a flash block can support is limited. Once the flash block nears or exceeds this erase cycle limit, data may no longer be written or read from the flash block reliably without some sort of intervention, such as data correction. Eventually, even with data correction, the data stored in the flash block may have too many bit errors that can be adequately corrected, rendering the flash block unusable for its intended purpose.

The term “flash memory device” is intended to include any form of non-volatile solid-state memory, including those that use blocks of non-volatile memory cells, named flash blocks. Each memory cell (not shown) may be single or multi-level. Flash memory devices are known by those of ordinary skill in the art. A flash memory device permits memory operations, such as a write or read operation, to be performed on these flash blocks according to a protocol supported by the flash memory device. A flash memory device may be implemented by using a NAND flash memory device that complies with the Open NAND Flash Interface Specification, commonly referred to as ONFI Specification. The term “ONFI Specification” is a known device interface standard created by a consortium of technology companies, called the “ONFI Workgroup”. The ONFI Workgroup develops open standards for NAND flash memory devices and for devices that communicate with these NAND flash memory devices. The ONFI Workgroup is headquartered in Hillsboro, Oreg. Using a flash memory device that complies with the ONFI Specification is not intended to limit the embodiment disclosed. One of ordinary skill in the art having the benefit of this disclosure would readily recognize that other types of flash memory devices employing different device interface protocols may be used, such as protocols compatible with the standards created through the Non-Volatile Memory Host Controller Interface (“NVMHCI”) working group. Members of the NVMHCI working group include Intel Corporation of Santa Clara, Calif., Dell Inc. of Round Rock, Tex. and Microsoft Corporation of Redmond, Wash.

InFIG. 1, electronic storage device10may have any configuration that can perform memory operations on a memory store4, which includes at least one erase-limited memory device, such as flash memory devices14-1,14-2, through14-i; and that reduces erase-cycles according to the present invention. The variable i reflects the maximum number of flash memory devices that form a portion or all of memory store4. Electronic storage device10may be configured to include a storage processing unit16that is coupled to memory store4and an I/O (input/output) interface18. IO interface18may be in the form of a SATA (Serial Advanced Technology Attachment), iSCSI (Internet Small Computer System Interface), Fibre Channel, USB (Universal Serial Bus), eSATA (external SATA) interfaces, a network adapter, a PCI (Peripheral Component Interconnect) or PCI-e (PCI Express) bus bridge, or the like. Storage processing unit18may include subcomponents, such as a CPU (central processing unit), interconnecting pathways, such as busses and control lines, (collectively referred to as “interconnects”), and a working memory, such as DRAM (dynamic random access memory), which are not illustrated to avoid overcomplicating this disclosure. Storage processing system may also include a memory subsystem20, a mapping table22, an embedded operating system, named “OS”24, and a program code26. Memory subsystem20may include DMA (direct memory access) controllers and interconnects that couple memory subsystem20between storage processing system16to memory store4. These device components enable electronic storage device10to execute an embedded operating system, such as OS (operating system)24, that is necessary for processing memory transaction requests, including memory transaction request28, which are initiated by one or more hosts, including host30, through a suitable conduit, such as network32.

Storage processing system16uses at least one logical storage unit, named a “flop”, when minimizing erase cycles, A flop includes a set of at least two flop sections from one or more minimum erasable locations that are from at least one erase-limited memory device, such as flash block44in flash memory device14-1and flash blocks52-1through52-nin flash memory device14-2, respectively. The variable n reflects the maximum number of flash blocks disposed in flash memory device14-2. In addition, storage processing system16maps these flash blocks to a single primary address, such as a LBA (logical block address) address used by host30. For example, flash memory device14-1may be used to include at least two flop sections42-1and42-2, which are created from a single flash block44in flash memory device14-1. Flash block44is mapped to a single primary address62-1, and may thus also be referred to as a flop, such as flop46. Thus in this example, flop sections are formed from a single flash block. When used to form a flop, each of these mapped flash blocks may be also referred as flop blocks. Using this naming convention inFIG. 1, flop sections42-1through42-2collectively belong to flop46.

In another example, flash memory device14-2may be initialized to in include at least two flop sections, such as50-1through50-n, but unlike in the previous example, flop sections50-1through50-nare created from n number of flash blocks, such as flash blocks52-1through52-nin flash memory device14-2. Flash blocks52-1through52-nare mapped to a single primary address, and thus may be also referred to as a flop, such as flop56. In this example, n number of flash sections are formed from n number of flash blocks. These examples are not intended to limit the embodiment shown inFIG. 1. Other variations may be used. In another example (not shown), flop sections may be formed from flash blocks that are from different flash memory devices.

A primary address may be any address, such as an LBA, that is associated by a host to data which is subject to a memory transaction request, such as memory transaction request28inFIG. 1. An LBA represents an address that is part of a logical addressing system (not shown) used by a host30, and this host may use one or more LBAs in a memory transaction request, such as memory transaction request28. Other types of primary addresses may be mapped other than an LBA, including any address that is part of a memory device addressing system used by electronic storage device10but is in logical form. The mapping of a primary address to a set of at least one flop blocks may be performed by using a mapping structure, such as mapping table22. The form of the mapping structure used to provide the association between a single primary address to a set of flop blocks is not intended to limit the present invention in any way, and any form for the mapping structure may be utilized

InFIG. 2, mapping table22is illustrated in accordance with another embodiment of the present invention. Mapping table22includes a set of at least one primary address, such as addresses62-1,62-2, and62-k. Mapping table22associates LBAs used by a host to the memory device addressing system used by an electronic storage device. This primary address to flop block mapping is named “flop mapping”. Flop mapping is used as part of minimizing erase-cycles in selected erase-limited memory devices in memory store4. Mapping table22is not limited to mapping all primary addresses supported by electronic storage device10to a flop or to using all minimum erasable locations available in memory store4.

Primary addresses, such as addresses62-1,62-2, and62-k, that are mapped to a flop block are subject to reduced erase-cycles. For example, address62-1, which is in the form of an LBA, named LBA1, is mapped to a set of at least one flash block addresses respectively corresponding to a set of at least one flash blocks, such as PBA (physical block address)1-1and flash block44. Similarly, address62-2, which is in the form of an LBA, named LBA2, is mapped to a set of at least one flash block addresses respectively corresponding to a set of at least one flash blocks, such as PBA2-1through PBA2-nand flash blocks52-1through52-n, respectively. Further, address62-k, which is in the form of an LBA, named LBAK, is mapped to a set of at least one flash block addresses respectively corresponding to a set of at least one flash blocks68-1through68-M. These flash block addresses are associated with or have physical block addresses PBA M-1, PBA M-2, PBA M-N, and may be also referred to as flopL. Mapping a host address, such as an LBA, to a set of flash blocks that represent a flop is not intended to limit the present in anyway. Variable k, L, M, and N reflect a variable integer number and are not intended to limit the present invention in any way.

In accordance with yet another embodiment of the present invention, the data associated with the primary address associated with a flop, such as primary address62-2and flop56inFIG. 2, respectively, has a data size that is at most equal to the size of the flop section, named “flop section size”, initialized from the flop block of flop56. For instance, if a flop section is initialized using pages from a flash block then the data associated with the primary address is limited to be at most equal to the page size of the flash block.

Minimum Erasable Location

FIG. 3illustrates a generic illustration of a flop70that has been initialized to include a plurality of flop sections72, including a first flop section74, in accordance with another embodiment of the present invention. Flop sections72may be formed from a minimum erasable location76of a memory device. For example, if the memory device used is a flash memory device, such as14-1inFIG. 1, flop sections70would be formed from a flash block from this flash memory device since a flash block is the minimum erasable location of a (NAND) flash memory device. A minimum erasable location, such as76, may also be referred to in the alternative as a “flop block”. Flop70can have more than one flop section that contains data but only one of these flop sections will be considered to hold valid data.

In addition, this minimum erasable location is partitioned into at least one flop section, such as flop sections72. In accordance with one embodiment of the present invention, a flop section, such as first flop section74, represents a minimum writeable area selected for minimum erasable location76for the memory device. For example, if the memory device used is a flash memory device, such as14-1in FIG.1, each flop section from plurality of flop sections72, such as first flop section74, would be formed from a selected minimum writable area of flash block44. A flash block has at least two native minimum writable areas that can be used: a flash block page, named herein as a “page”, or a flash block partial page, named herein as a “partial page”. In the embodiment disclosed inFIG. 3, a minimum writeable area is in the form of a page although this is not intended to limit the present invention in any way. Partial pages can be used as flop sections, or other minimum writable areas can be selected that are not native to the flash block. For instance, using additional program logic, a flop section can be comprised of two pages.

The minimum erasable location may be partitioned to have at minimum one flop section although a flop, such as flop46, flop56, or flop L inFIG. 2, should have at least two flop sections to provide a reduction in erase cycles in the memory device(s) associated with the flop. For instance inFIG. 4, one or more flop blocks, such as flop blocks90-1through90-n, can be grouped together to form a flop92.

Method of Initializing Flop Sections

FIG. 6illustrates a method of initializing a flop for minimizing erase cycles in an electronic storage device that uses at least one erase-limited memory device in accordance with yet another embodiment of the present invention. Initializing a flop may be required when electronic device is used for the first time. The method inFIG. 6is further described below with reference toFIGS. 1,2and5A.

A set of at least one minimum erasable locations that will be used to initialize a flop is selected200. For example, flash blocks52-1through52-n, in flash memory device14-2may be used to provide this set of minimum erasable locations. Flash blocks52-1through52-nare referred to as flop blocks inFIG. 5Ato indicate that a flop has been initialized using these flash blocks.

A primary address is mapped202to these minimum erasable locations. For example, an LBA used by host30is mapped to the addresses of flash blocks52-1through52-nin flash memory device14-2by using mapping table22. The addresses of flash blocks52-1through52-nmay be in the form of physical block addresses, such as PBA2-1, PBA2-2, and PBA2-n.

These minimum erasable locations are erased204by storage processing system16as directed by program code26. Erasing a minimum erasable location in a flop may also be referred to as initializing a flop block.

Initialization parameters are obtained or calculated, and then stored206into non-volatile memory, such as in a flash memory device. These parameters include: the size of a minimum erasable location, the size of the minimum writeable location that will be used as a flop section; the number of flop sections per minimum erasable location; the number of erasable locations mapped to the primary address in step202; a sequence range; and an invalid flop section location.

The size of a minimum erasable location in this example is the size of flash block52-1. In the embodiment shown, flash blocks that are used as minimum erasable locations are of the same size, and flash block52-1may be disposed with a block size of 256 KB.

The size of the minimum writeable location in this example is a flash block page. Although not intended to be limiting in any way, blocks52-1through52-nare each disposed to have the same page size, such as 2 KB, and thus the flop sections initialized in this method each have a flop section size of 2 KB.

The number of flop sections per minimum erasable location may be calculated by dividing the size of the minimum erasable location used by the flop section size. In this example, the number of flop sections is equal to the flash block size of 256 KB divided by the flop section size of 2 KB.

The number of erasable locations mapped to the primary address in step202is equal to the number of flash block addresses mapped to the primary address in step202, which is equal to n in this example.

The sequence range is a range of values, such as ascending numbers, that can be used to identify the relative position of a flop section in a flop according to the section selection sequence used. For instance, if this section selection sequence selects flop sections on per block basis, the beginning sequence value selected for this sequence range can be set to zero (0) and the ending sequence value selected for this sequence range can be set to the number of flop sections per minimum erasable location multiplied by the number of minimum erasable locations in the flop minus one (1). InFIG. 5A, flop block56illustrates a total of (n*z)-1erased flop sections.

A flop section location is used to point to a specific flop section within a flop. A flop section location includes two values, a flop block index and a flop section index. The flop block index reflects the relative position of a minimum erasable location within the set of minimum erasable locations, and is unique to the particular memory device that contains the minimum erasable location referenced by the minimum erasable identifier. A flash block index is unique to a particular erase-cycle memory device within the flop. For example, referringFIG. 5B, flop blocks52-1through52-n, which are implemented in the form of flash blocks having PBA2-1through PBA2-ninFIG. 2, can be described to have the relative positions of0,1, through n-1, respectively. The flop section index reflects the relative position of a flop section within the set of flop sections in a minimum erasable location and is unique to the particular flop section within the minimum erasable location. Flop sections104-1,104-2through104-zcan be described to have a flop section index of0,1, through z-1, respectively. Flop section104-1, therefore, has a flop section location of00. An invalid flop section location is a predefined flop section location value that does not point to a particular flop section within a flop. In the example inFIG. 5B, the value represented by the variables nz is used to represent the invalid flop section location although this value is not intended to limit the present invention in any way.

A section selection sequence is initialized in step208and the first minimum writeable location in an erased minimum erasable location in the section selection sequence is treated as an available flop section by storing the location of this available flop section in working memory. Consequently, if the section selection sequence treats flop section104-1in flop block52-1, as an available flop section, storage processing system stores the values00in working memory as an available flop section location106. Storage processing system16inFIG. 1, also stores the invalid flop section location value in working memory as a valid flop section location108. During succeeding boot-ups of electronics storage device10, the available flop section location and valid section location are initialized to contain the invalid flop section location value. An available flop section location is intended to hold a value that represents the next erased flop section location in the section selection sequence that can receive a write operation to store data associated with the primary address mapped to flop56.

Section Selection Sequence and Offsets

In accordance with another embodiment of the present invention, each flop section is addressable by using an offset from the address of the flop block which has been initialized to include the flop section. For example in fromFIG. 4flop blocks90-1through90-nmay be disposed to be in the form of flop L, and thus, these flop blocks are respectively associated with PBA addresses M-1, M-2, M-N which in turn are associated with flash blocks68-1,68-2through68-M. The means for minimizing erase cycles, such as storage processing system16executing program code26inFIG. 1, uses an offset value that points to the beginning boundary of a flop section within each flop.

For example since inFIG. 4, flop blocks90-1through90-nare in the form of flash blocks, and if the minimum writable area selected is a page, then storage processing system16would use an offset value that when combined with the address of a flop block, named “flop block address”, would point to the beginning page boundary of a page. The flop block address in the example inFIG. 4is equal to the address of the flash block from which a flop block is formed. For example, flop block90-1would have a flop block address equal to the PBA of flash block68-1, which is PBA M-1inFIG. 4. The offset value selected is not limited to point to page boundaries but could be used to point within a page, such as when using partial pages as flop sections.

The use of offset values combined with a flop block address to point to flop sections in a flop block is not intended to limit the present invention in any way but any method may be used to permit a storage processing system, such as storage processing system16inFIG. 1, to access a flop section partitioned within a flop block, such as flop block104-1through104-zinFIG. 5B. For instance, if storage processing system16receives a memory transaction request for data with a primary address that is mapped to a flop through mapping table22, storage processing system16selects a flop section from the flop according to a chosen section selection sequence. If this flop has not been mapped to any minimum erasable locations, storage processing system16initializes the flop as discussed earlier with reference withFIG. 5A. After initialization, storage processing system16selects flop sections sequentially according to this section selection sequence. Each used flop section may then be reused after their flop block is re-initialized, rendering the newly initialized or created flop sections to be selected and used once again.

After flop initialization, storage processing system16under program code22uses this section selection sequence to find certain flop sections. For write operations that involve a flop, storage processing system16searches for an available flop section. An available flop section is a flop section that has been initialized but has not yet been used to store data. Storage processing system16may only use an available flop section once to store data until the flop block for this flop section is initialized again. For read operations that involve a flop, storage processing system16searches for a valid flop section. A valid flop section is a flop section that holds the most current data in the set of flop section in the same flop. Since a flop has more than one flop section, data from the same primary address is written only to an available flop section. There is only one available flop section and only one valid flop section per flop. Storage processing system16keeps a record of the location of the available flop section and the location of valid flop section by storing these locations in working memory as further described herein.

The section selection sequence used may be any sequence suitable for sequentially accessing initialized flop sections, and the following section selection sequence examples below are not intended to limit the present invention in any way. For example, storage processing system16may be disposed to select flop sections only from the same flop block in a flop having more than two flop blocks. Flop sections from another flop block within the same flop are not selected until all erased flop sections from the prior used flop block have been used. With reference toFIGS. 1 and 4, under this example of a section selection sequence, storage processing system16selects the first flop section94-1, named “section1”, in flop block90-1, then the second flop section94-2, named “section2”, in flop block90-1, and so on until the flop section sought by storage processing system16is found. In a write operation, storage processing system16only uses flop sections from another flop block in flop92, such as flop block90-2, if all flop sections in flop block90-1have been used and no flop sections in flop block90-1are available to store data. In effect, flop sections are selected sequentially per flop block under this section selection sequence.

Storage processing system16can obtain the flop block address of flop block90-1from the mapping structure that provides the mapping of primary addresses with flops, such as mapping table22inFIG. 1. Storage processing system16uses successive offsets beginning from the flop block address provided by a primary address to flop mapping table, such as mapping table22inFIG. 4, to sequentially access another available flop section until flop sections have been accessed in the flop block.

After all flop sections in flop block90-1have been used and no other flop sections are available in flop block90-1, storage processing system16selects another flop section, if available, by using the next flop address that is associated with another flop block in flop92in mapping table22. For instance, storage processing system16selects flop section1from flop block90-2by using its flop block address, and then sequences down to each section in flop block90-2by using an offset value. This continues, until all available flop sections in flop block90-2have been used, and if so, storage processing selects sections from flop block90-nby using this selection sequence until all available flop sections in flop92have been used. After all flops sections have been used for each flop block in flop92, storage processing system16re-initializes the flop blocks in flop92again in the same manner.

In another example of a section selection sequence, storage processing system16may instead select an available flop section from a first flop block and in a subsequent selection selects an available flop section only from flop blocks that were not selected in a prior selection of an available flop section and that are from the same flop. Only after storage processing system16has selected one available flop section from each of these flop blocks from the same flop, can storage processing system16again select another available flop section from the same flop block used previously.

With reference again toFIG. 4, under this example of a section selection sequence, storage processing system16selects the first flop section1in flop block90-1, then flop section1in flop block90-2, and so on until there are no other flop blocks available in flop92that were not used in a prior selection of an available flop section. Any subsequent section selection sequence is made from a flop block that is different from the flop block used in the prior section selection sequence until all flop blocks have been used to provide a flop section under the section selection sequence. When each flop block, such as flop blocks90-1through90-n, have been used in the section selection sequence, storage processing system16returns to flop block90-1and selects flop section2, and in another write cycle, selects flop section2from flop block90-2and so on until all flop blocks have been again used to provide a flop section under the section selection sequence. In effect, flop sections are selected under this section selection sequence across flop blocks from the same flop. The algorithm used by storage processing system16under this section selection sequence may include using the first flop block address listed in mapping table22that is mapped to the primary address associated with the data that will be written into an available flop section that is selected under the section selection sequence.

After initializing at least one flop so that the flop can be used to minimize erase cycles in erase-limited memory devices, storage processing system16tracks which flop blocks can be erased and which flop sections are available to receive data. Flop sections available to receive data may herein also be referred to as “available flop sections.” In accordance with one embodiment of the present invention, storage processing system16uses a set of sequence numbers that is comprised of sequential numbers that are unique with respect to each other. Storage processing system16stores one of these sequence numbers with each data that is subject to a write transaction, such as data having primary address62-1inFIG. 2, when storing the data into an available flop section. The amount of sequence numbers in this set of sequence numbers is equal to the number of flop sections initialized in a flop, such as flop56inFIGS. 5A-5D, and no two sequence numbers are the same in the same flop. For example, if flop56has been initialized to include flop sections104-1through104-z, and each flop block contains z number of flop sections, the set of sequence numbers would include n*z numbers that are in sequence, where z represents an arbitrary number. Integer numbers may be used in the set of sequence numbers, in the example set of sequence numbers example immediate above, can range from 0 through ((n*z)-1).

Before a flop can be used to minimize erase cycles, storage processing system16creates a flop by mapping the respective flop block address of flop blocks that will comprise the flop to a primary address. For example, referring again to FIGS.2and5A-5D, storage processing system16maps primary address62-2to the addresses of flash blocks52-1through52-nof flop56. At least one of these flop blocks, such as flop blocks102-1through102-n, that is mapped to the primary address62-2is then erased by storage processing system16to initialize flop sections in flop56.

For the first write operation that is performed after initialization of the flop sections and that pertains to data associated with primary address62-2, storage processing system16selects the first available flop section, such as flop section104-1inFIG. 5B, according to the section selection sequence used. After selecting the first available flop section, storage processing system16writes this data in flop section104-1, and records the location of flop section104-1in the working memory as the valid flop section location108as illustrated inFIG. 5C. Storage processing system16also embeds the first number in a set of sequence numbers with this data in flop section104-1; and updates available flop section location106to reflect the location of the next erased flop section under the section selection sequence used and that can be used to receive data in a subsequent write operation involving primary address62-2. For example inFIG. 5C, the next available flop section that reflects the location of the next flop section under the section selection sequence is flop section104-2and its location of01is stored in available flop section location106in working memory.

FIG. 5Dillustrates the states of flop sections in a flop block, such as flop block102-1, after a storage processing system performs the second write operation on flop block102-1in accordance with yet another embodiment of the present invention. For the second write operation that is performed for data associated with primary address62-2, storage processing system16selects the first available flop section, which is now flop section104-2inFIG. 5C, in flop56according to the section selection sequence used. After selecting the first available flop section, storage processing system16writes this data in flop section104-2, and records the location of flop section104-2in the working memory as the valid flop section location108as illustrated inFIG. 5D. Since104-1is no longer in the erased state and neither the available flop section location nor the valid flop section location point flop section104-1, flop section104-1can be described as “unknown” since cannot be used by storage system processing to read or write data until the flop sections in flop block102-1are initialized again. This “unknown” state is not recorded by storage processing system16in the embodiment shown.

Storage processing system16also embeds the second number in a set of sequence numbers with this data in flop section104-2; and updates available flop section location106to reflect the location of the next erased flop section under the section selection sequence used and that can be used to receive data in a subsequent write operation involving primary address62-2. For example inFIG. 5D, the next available flop section that reflects the location of the next flop section under the section selection sequence is flop section104-3and its location of02is stored in available flop section location106in working memory.

FIG. 7illustrates a method of performing a write operation in an electronic storage device that minimizes erase cycles in at least one erase-limited memory device, named “flop write operation”, in accordance with yet another embodiment of the present invention. The method inFIG. 7is further described below with reference toFIGS. 1 and 2and is performed after a set of flop sections have been initialized, such as by the flop section initialization method disclosed above with reference toFIG. 6above.

Upon receiving a memory transaction28from host30through10interface18, electronic storage device10through storage processing system16will determine whether the memory transaction28pertains to a read or write memory operation involving a primary address, such as a LBA62-2(LBA2). If memory transaction28pertains to a write operation, the method inFIG. 7is performed.

At300, it is determined whether the available flop section location in working memory for flop56is valid. Determining whether the available flop section location is valid may include comparing the available flop section location value stored in working memory to the value stored in working memory that represents the invalid flop section location. If these values are the same then the available flop section location is not valid.

If yes, the process flow proceeds to step312. If no, mapping table22is searched302for LBA62-2. A flop section that has been initialized from one of the flash blocks mapped to LBA62-2is read304according to a section selection sequence. In this example, the section selection sequence sequentially selects flop sections in the same flash block before selecting another flop section in another flash block and keeps track of the number of flop sections read.

It is determined306whether the currently read flop section is erased.

If yes, it is determined308whether all flop sections have been read under the section selection sequence. In this example, storage processing system16determines whether all flop sections have been read in the flop by dividing the maximum erasable location size with the minimum writable location size and multiplying the quotient by the number of flop blocks in the flop. A result that is equal to the current number of flop sections read indicates that storage processing system has reach the end of the flop. If yes, the process flow proceeds to step310.

At step310, the location of the next erased flop section is stored as the available flop section location in working memory. In this example, the next erased flop section location is the erased flop section location that is subsequent to the first erased flop section under the section selection sequence used, such as flop section104-1. In one embodiment of the present invention, the information stored in working memory as a flop section location includes two values, a flop block index and a flop section index. Consequently, the next available flop section location reflects the flop block index and the flop section index of the available flop section location found in step310. In addition, the first sequence number in the sequence range, which can be previously calculated and stored in non-volatile memory during the initialization of the flop, is stored in working memory as the current sequence number. The process flow then leads to step312.

If at step308, it is determined that not all flop section have been read under the section selection sequence, the program flow returns to step304, and the next flop section under the section selection sequence is read.

If at step306, it is determined that the currently read flop section is not erased, the sequence number stored with the data in the currently read flop section and the flop section location of the currently read flop section are stored314as the current sequence number and the valid flop section location respectively in working memory.

At step316, it is determined whether all flop sections have been read under the section selection sequence.

If yes, the location of the next erased flop section in the section selection sequence is stored318in working memory as the available flop section location. This process flow then proceeds to step320, where the current sequence number that is currently stored in working memory is incremented. The process flow then proceeds to step312.

If at step316not all of the flop sections have been read in the flop, the next flop section in the section selection sequence is read322.

At step324, it is determined whether next flop section read in step322is erased, and if so, the location of next flop section in the section selection sequence is stored326as the available flop section location in working memory. The program flow then proceeds to step320.

If at step324, the next flop section read in step is not erased; it is determined328whether the sequence number read from the next flop section read in step322is more recent than the current sequence number stored in working memory.

If no, then the process flow proceeds to step316, and if yes, then the process flow proceeds to step314.

At step312, the data associated with the primary address, such as LBA2, that is subject to the memory write transaction request; is written to the flop section corresponding to the available flop section location stored in working memory. In addition, the current sequence number, such as the current sequence number stored in working memory is also stored in the same flop section as the data. Further, the previous valid flop section location is temporarily stored in working memory, the available flop section location is stored as the valid flop section location in working memory, and the next erased flop section in the section selection sequence is noted by storing the location of this next erased flop section as the available flop section location in working memory.

At step330, the current sequence number is incremented.

At step332, it is determined whether the previous valid flop section location temporarily stored in working memory is valid. A previous valid flop section is valid if the write memory operation is at least the second subsequent write memory operation performed after initialization of the flop. Consequently, in the example inFIG. 2, the only time the previous valid flop section location is not valid occurs immediately after the initialization of flop56.

If a previous valid flop section is not valid, the process flow completes and exits.

If a previous valid flop section is valid, the process flow continues to step334, where it is determined334whether the flop block of the previous valid flop section contains only invalid flop sections. This may be performed by determining whether the valid flop section location contains a value that now points to a flop block that is different than the flop block pointed to by the previous valid flop section location value.

At step344, the flop block of the previous valid flop section is erased and the process flow can then terminate.

FIG. 8illustrates a method of performing a read operation in an electronic storage device that minimizes erase cycles in at least one erase-limited memory device, named “flop read operation”, in accordance with yet another embodiment of the present invention. The method inFIG. 8is further described below with reference toFIGS. 1 and 2and is performed after a set of flop sections have been initialized, such as by the flop section initialization method disclosed above with reference toFIG. 6above.

Upon receiving a memory transaction28from host30through10interface18, electronic storage device10through storage processing system16will determine whether the memory transaction28pertains to a read or write memory operation involving a primary address, such as a LBA62-2. If memory transaction28pertains to a read operation, the method inFIG. 8is performed.

At400, it is determined whether the available flop section location stored in working memory for flop56is valid. Determining whether this flop section location is valid may include comparing the available flop section location value to the stored invalid flop section location value. If these values are not equal then the available flop section location value in working memory is valid.

If yes, the process flows to step312. If no, mapping table22is searched402for LBA62-2. A flop section that has been initialized from one of the flash blocks mapped to LBA62-2is read404according to a section selection sequence. In this example, the section selection sequence sequentially selects all flop sections in the same flash block before selecting another flop section in another flash block.

It is determined406whether currently read flop section is erased.

If yes, it is determined408whether all flop sections have been read under the section selection sequence.

At step410, if all flop sections have been read, the location of the next erased flop section is stored as the available flop section location in working memory. In addition, the first sequence number in the sequence range, which can be previously calculated and stored in non-volatile memory during the initialization of the flop, is stored in working memory as the current sequence number. The process flow then leads to step412.

If at step408, it is determined that not all flop section have been read under the section selection sequence, the program flow returns to step404, and the next flop section under the section selection sequence is read.

If at step406, it is determined that the currently read flop section is not erased, the sequence number stored with the data in the currently read flop section and the flop section location of the currently read flop section are stored414as the current sequence number and the valid flop section location respectively in working memory.

At step416, it is determined whether all flop sections have been read under the section selection sequence.

If yes, the location of the next erased flop section in the section selection sequence is stored418in working memory as the available flop section location. This process flow then proceeds to step420, where the current sequence number that is currently stored in working memory is incremented. The process flow then proceeds to step412.

If at step416not all of the flop sections have been read in the flop, the next flop section in the section selection sequence is read422.

At step424, it is determined whether next flop section read in step422is erased, and if so, the location of next flop section in the section selection sequence is stored426as the available flop section location in working memory. The program flow then proceeds to step420.

If at step424, the next flop section read in step is not erased; it is determined428whether the sequence number read from the next flop section read in step422is more recent than the current sequence number stored in working memory.

If no, then the process flow proceeds to step416, and if yes, then the process flow proceeds to step414.

At step412, data stored in the flop section corresponding to the valid flop section location stored in working memory is read and sent to the host. The process flow can then terminate.

FIG. 9illustrates a multilevel structure500that may be used with the present invention. Multilevel structure500may be written in an erase-limited memory device, such as flash memory device14-1inFIG. 1. Multilevel structure500includes control data501stored at the top level, sometimes referred to as the root node, of the multilevel structure500. The contents of control data501include the physical locations of control data at a level below the top-most level, such as second control data502,503, and504. Control data501may be referred to as the parent of504, and504is a child of control data501. Similarly, control data504is the parent of control data505, and control data505is a child of504. A parent can have multiple children but a child can only have one parent.

When a child changes its physical location, its parent will incur a change in content and will have to be written to the target flash memory device storing the parent. In an implementation where every write to the flash memory device requires a change in physical location, such as in pre-erase memory addressing, a change in any level below the top level in the multilevel structure, such as control data507will cause a change to its parent, such as control data504which will in turn cause a change to its parent, such as501. This domino effect flows from changes incurred from a lower level to a higher level, resulting in a change in control data at the top level any time a change occurs at any of the lower levels of multilevel structure500. When using a flop in a multilevel structure500, the parent mapped to the flop will not incur the domino effect since the parent will only need to store the address of the flop, and thus, the parent will not incur a change if the location of any of its children changes.

For example, referring toFIGS. 1 and 2, if the parent is in the form of control data501and control data501is mapped to flop46, any changes to control data that are children to control data501will be written to flop sections of flop46and erase-cycles will be delayed until a flop block is re-initialized, reducing or minimizing erase cycles in flash block46.

While the present invention has been described in particular embodiments, it should be appreciated that the present invention should not be construed as limited by such embodiments. Rather, the present invention should be construed according to the claims below.