Unified re-map and cache-index table with dual write-counters for wear-leveling of non-volatile flash RAM mass storage

• US 6,000,006 A
• Filed: 08/25/1997
• Issued: 12/07/1999
• Est. Priority Date: 08/25/1997
• Status: Expired due to Term

• Current Assignee: BiTMICRO, LLC (BiTMICRO Networks, Inc.)
• Original Assignee: Bit Microsystems, Inc.
• Inventors: Cohen, Earl T., Christie, Allan J., Bruce, Rolando H., Bruce, Ricardo H.
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): Portka, Gary J.
• Application Number:
  US08/918,203
• Time in Patent Office: 834 Days
• Field of Search: 711/103, 711/206, 712/37, 365/230.03, 365/185.33, 365/218
• US Class Current: 711/103
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/7211 Wear leveling

Abstract

A flash-memory system provides solid-state mass storage as a replacement to a hard disk. A unified re-map table in a RAM is used to arbitrarily re-map all logical addresses from a host system to physical addresses of flash-memory devices. Each entry in the unified re-map table contains a physical block address (PBA) of the flash memory allocated to the logical address, and a cache valid bit and a cache index. When the cache valid bit is set, the data is read or written to a line in the cache pointed to by the cache index. A separate cache tag RAM is not needed. When the cache valid bit is cleared, the data is read from the flash memory block pointed to by the PBA. Two write count values are stored with the PBA in the table entry. A total-write count indicates a total number of writes to the flash block since manufacture. An incremental-write count indicates the number of writes since the last wear-leveling operation that moved the block. Wear-leveling is performed on a block being written when both total and incremental counts exceed system-wide total and incremental thresholds. The incremental-write count is cleared after a block is wear-leveled, but the total-write count is never cleared. The incremental-write count prevents moving a block again immediately after wear-leveling. The thresholds are adjusted as the system ages to provide even wear.

Claims

1. A unified re-mapping table for a flash-memory system, the unified re-mapping table comprising:

a plurality of entries, an entry in the plurality of entries selected by a logical address from a host system, each entry in the plurality of entries having;

a physical-block-address field containing a physical block address of a block in an array of flash-memory devices, each flash-memory device containing non-volatile storage cells that retain data when a power supply is no longer applied to the flash-memory device;

a total-write-counter field for indicating a total number of write-erase cycles of the block identified by the physical-block-address field;

an incremental-write-counter field for indicating an incremental number of write-erase cycles since a wear-leveling operation for the block;

wherein both the total number and the incremental number from the entry must exceed thresholds to initiate wear-leveling for the block;

wherein the block is wear-leveled by moving the physical block address and the total number to a different entry in the unified re-mapping table when data is exchanged between blocks,

wherein the flash-memory system further comprises;

a total-threshold resister containing a total-write threshold for the flash-memory system;

an incremental-threshold register containing an incremental-write threshold for the flash-memory system;

total compare means, coupled to the total-threshold register and receiving the total number from the entry selected by a current logical address, for activating a first signal when the total number from the entry in the unified re-mapping table exceeds the total-write threshold;

incremental compare means, coupled to the incremental-threshold register and receiving the incremental number from the entry selected by the current logical address, for activating a second signal when the incremental number from the entry in the unified re-mapping table exceeds the incremental-write threshold;

wear-leveling means, activated by a write to the current logical address when both the first signal and the second signal are activated, for wear-leveling the block by moving the physical block address and the total number to a different entry in the unified re-mapping table, and for replacing the physical block address with a new physical block address for a physical block having a smaller total number of write-erase cycles,

whereby the total number from the entry must exceed the total-write threshold and the incremental number must exceed the incremental-write threshold to initiate wear-leveling and whereby each entry includes the physical block address for address translation to the flash-memory devices and two write-counters for wear-leveling.

2. The unified re-mapping table for a flash-memory system of claim 1 wherein the total-write-counter field is never cleared but continues to increase over a lifetime of the flash-memory system, but wherein the incremental-write-counter field is reset when the block is allocated to a different logical address and moved to a different entry in the plurality of entries,

whereby the total-write-counter field is never reset but the incremental-write-counter field is reset by wear-leveling.

3. The unified re-mapping table for a flash-memory system of claim 2 wherein the block in the array of flash-memory devices is a smallest amount of memory capable of being erased, wherein writes to the block can occur only after an erase, the block comprising a plurality of pages, and each page comprising a plurality of bytes,

whereby individual bytes cannot be erased unless an entire block of pages is erased.

4. The unified re-mapping table for a flash-memory system of claim 3 wherein each page in the flash-memory devices contains a data field and a system field, the system field containing only one byte for mapping, wherein all other bytes in the system field are available for an error-correction code for the data field,

whereby all except one byte of the system field is used for the error-correction code.

5. The unified re-mapping table for a flash-memory system of claim 4 wherein the one byte for mapping for each page in a block of pages is combined with the one byte for mapping for other pages in the block to form a block pointer, the block pointer containing a copy of the total number and the incremental number of writes from the entry in the unified re-mapping table for the block,

whereby the block pointer contains the total number and incremental number for all pages in the block.

6. The unified re-mapping table for a flash-memory system of claim 5 wherein the block pointer further includes the logical address for data in the data field of pages in the block,

whereby the block pointer includes a reverse map with the logical address mapped to the physical block address for the block.

7. The unified re-mapping table for a flash-memory system of claim 1 wherein each entry in the plurality of entries further comprises:

a cache valid field for indicating when data identified by the logical address resides in a cache, the cache comprising volatile memory that loses data when power is lost;

a cache index field containing a cache index when the cache valid field indicates that the data resides in the cache, the cache index identifying a location in the cache of the data for the logical address,

whereby each entry identifies the location in cache for the data or the location in the flash-memory devices.

8. The unified re-mapping table for a flash-memory system of claim 7 wherein the cache contains only data while cache tags containing cache addresses are absent for the cache,

whereby the cache index in the unified re-mapping table eliminates the cache tags.

9. The unified re-mapping table for a flash-memory system of claim 1 wherein each entry contains a physical-block address for an interleave of at least four physical blocks, the at least four physical blocks being in at least four of the flash memory chips,

whereby the unified re-mapping table stores entries for an interleave of physical blocks.

10. A flash-memory system comprising:

a plurality of flash memory chips, each flash memory chip having non-volatile memory cells organized into pages and physical blocks, each physical block comprising a plurality of pages, the non-volatile memory cells retaining data when power is lost;

a cache for storing a copy of some but not all data in the flash memory chips, the cache being a copy-back cache with more recent data than in the flash memory chips, the cache responsive to cache addresses;

a mapping table, receiving logical addresses from a host, for translating the logical addresses to physical addresses or cache addresses, the mapping table having a plurality of entries for the logical addresses, each entry having;

a physical-block address of a physical block in the flash memory chips;

a total-write count of a total number of writes to the physical block address since manufacture of the flash-memory system;

an incremental-write count of an incremental number of writes to the physical block since a last wear-leveling operation on the physical block;

a cache valid bit for indicating when the data is in the cache or only in the flash memory chips;

a cache index for generating a cache address for locating cache data in the cache, the cache data identified by the logical address;

a wear-level indicator, coupled to the mapping table, for comparing the total-write count to a total threshold and for comparing the incremental-write count to an incremental threshold, for generating a wear-leveling signal when both the total threshold and the incremental threshold are met;

a wear-leveler, coupled to begin a wear-leveling operation when the wear-leveling signal is received, for replacing the physical block address for the entry with a less-written physical block address having a lower total-write count;

reset means, responsive to the wear-leveling signal, for resetting the incremental-write count when a block is wear-leveled;

average write calculator, for calculating an average number of writes per physical block in the flash memory chips;

average comparator, for comparing the average number of writes per block to the total threshold;

threshold adjust means, coupled to the average comparator, for increasing the total threshold when the average number of writes exceeds the total threshold,

whereby wear-leveling begins when both the total threshold and the incremental threshold are met by write counts stored in the entry in the mapping table and the total threshold is increased as the average number of writes per block increases and the incremental-write count is reset but the total-write count is not reset by wear-leveling.

11. The flash-memory system of claim 10 further comprising:

access means, responsive to the cache valid bit, for sending the cache address generated from the cache index to the cache when the cache valid bit indicates that the data is in the cache, but otherwise sending the physical block address to the flash memory chips,

whereby an address to the cache or to the flash memory chips is generated from the entry in the mapping table.

12. The flash-memory system of claim 10 wherein the incremental threshold is decreased as the total threshold is increased over a lifetime of the flash-memory system.

13. The flash-memory system of claim 12 wherein the total threshold is set to an initial value of at least half an expected number of writes in a lifetime of the flash-memory system during manufacture,

whereby wear-leveling is not signaled until a block has half of its expected writes.

14. The flash-memory system of claim 12 wherein the total threshold is set to an initial value of at least 500,000 writes during manufacture,

whereby wear-leveling is not signaled until a block has 500,000 writes.

15. The flash-memory system of claim 10 wherein each entry in the mapping table contains a physical-block address for an interleave of at least four physical blocks, the at least four physical blocks being in at least four of the flash memory chips,

whereby the mapping table stores entries for an interleave of physical blocks.

16. The flash-memory system of claim 15 wherein the wear-leveler moves physical blocks of an interleave.

17. The flash-memory system of claim 16 wherein the mapping table receives logical addresses from the host that include interleave bits, the interleave bits for selecting one of the at least four of the flash memory chips in an interleave, the interleave bits not for selecting an entry in the mapping table.

18. The flash-memory system of claim 17 wherein the interleave bits are page-interleaving bits.

19. The flash-memory system of claim 17 wherein the interleave bits are block-interleaving bits.