Two-level RAM lookup table for block and page allocation and wear-leveling in limited-write flash-memories

• US 7,660,941 B2
• Filed: 04/30/2007
• Issued: 02/09/2010
• Est. Priority Date: 09/10/2003
• Status: Expired due to Fees

• Current Assignee: Super Talent Technology, Corporation
• Original Assignee: Super Talent Electronics, Inc.
• Inventors: Yu, Frank I-Kang, Lee, Charles C., Chow, David Q.
• Primary Examiner(s): Chace; Christian P
• Assistant Examiner(s): Parikh; Kalpit
• Application Number:
  US11/742,270
• Publication Number:
  US 20070204128A1
• Time in Patent Office: 1,016 Days
• Field of Search: 711/103
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7211 Wear leveling

Abstract

A restrictive multi-level-cell (MLC) flash memory prohibits regressive page-writes. When a regressive page-write is requested, an empty block having a low wear-level count is found, and data from the regressive page-write and data from pages stored in the old block are written to the empty block in page order. The old block is erased and recycled. A two-level look-up table is stored in volatile random-access memory (RAM). A logical page address from a host is divided by a modulo divider to generate a quotient and a remainder. The quotient is a logical block address that indexes a first-level look-up table to find a mapping entry with a physical block address that selects a row in a second-level look-up table. The remainder locates a column in the row in the second-level look-up table. If any page-valid bits above the column pointed to by the remainder are set, the write is regressive.

Claims

1. A flash-memory sub-system comprising:

a flash-memory array of physical blocks of flash memory identified by a physical-block address (PBA), a physical block in the flash-memory array of physical blocks having a plurality of pages, a page in the plurality of pages having a data sector that can be written with arbitrary data only once before requiring an erase of the physical block;

wherein the data sector is block-addressable and not randomly-addressable, wherein all bytes of the data sector are accessible together as a block and not accessible as individual bytes;

a data area formed from physical blocks of flash memory in the flash-memory array;

wherein each page in the plurality of pages in the physical blocks stores host data from a host in the data sector for the page;

a logical-sector address (LSA) received from the host, the LSA from the host being a host address for the host data from the host;

a first-level volatile lookup table having a plurality of mapping entries, wherein each mapping entry in the plurality of mapping entries is for storing a PBA mapping to a physical block in the flash-memory array of physical blocks for a logical block address (LBA);

a second-level volatile lookup table having a plurality of rows, wherein each row in the plurality of entries is for storing a plurality of page-valid bits that indicate when pages in the plurality of pages in a physical block in the flash-memory array of physical blocks contain valid host data; and

a modulo generator, receiving the LSA from the host, for performing a modulo operation on the LSA to generate a modulo remainder that identifies a selected page-valid bit in a selected row of the second-level volatile lookup table, the modulo generator also generating a quotient that is the LBA that is applied to the first-level volatile lookup table to select a selected mapping entry;

the selected mapping entry for storing a PBA mapping indicating a selected physical block in the flash-memory array of physical blocks for storing host data identified by the LSA;

wherein the PBA mapping from the selected mapping entry of the first-level volatile lookup table is applied to the second-level volatile lookup table to select the selected row in the plurality of rows;

wherein the flash-memory array is restrictive, allowing writes to pages in the plurality of pages in an ascending page order within a physical block in the flash-memory array of physical blocks, wherein regressive page-writes to a page in the plurality of pages in a descending order is prohibited;

regressive page-write detector means, receiving a subset of the page-valid bits from the selected row, the subset comprising page-valid bits that are for pages in the plurality of pages after a page in the plurality of pages for the selected page-valid bit, for signaling a regressive page-write when any page-valid bit in the subset of the page-valid bits indicates valid host data;

whereby regressive page-writes are detected from the page-valid bits from the second-level volatile lookup table and whereby the first-level volatile lookup table stores the PBA mapping that selects a row of the page-valid bits in the second-level volatile lookup table.

2. The flash-memory sub-system of claim 1 further comprising:

block relocator means, activated by the regressive page-write detector means when the regressive page-write is signaled, for copying valid pages of host data from the selected physical block to a new physical block in the flash-memory array of physical blocks; and

write ordering means for writing the host data to a selected page in the plurality of pages in the new physical block when the regressive page-write is signaled, wherein the host data is written into the new physical block in an ascending page order when the block relocator means copies valid pages in the plurality of pages,

whereby pages in the plurality of pages are written into the new physical block in ascending page order.

3. The flash-memory sub-system of claim 2 further comprising:

mapping entry update means for replacing a PBA mapping for the selected physical block with a PBA mapping the new physical block in the selected mapping entry in the first-level volatile lookup table when the regressive page-write is signaled;

row copy means for copying the page-valid bits from the selected row to a new selected row in the second-level volatile lookup table when the regressive page-write is signaled,

whereby mapping entries and rows are updated when the regressive page-write is signaled.

4. The flash-memory sub-system of claim 1 further comprising:

a wear-leveling-counter pool formed from wear-leveling counter physical blocks of flash memory in the flash-memory array;

a current wear-leveling counter physical block in the flash-memory array of physical blocks;

a plurality of wear-leveling counters stored in the current wear-leveling counter physical block, wherein the plurality of wear-leveling counters includes a wear-leveling counter for each physical block, and for each wear-leveling counter physical block,

whereby wear-leveling counters track wear of physical blocks of flash memory.

5. The flash-memory sub-system of claim 4 further comprising:

wear-level selector means for selecting a new physical block by examining the plurality of wear-leveling counters stored in the current wear-leveling counter physical block,

whereby the new physical block is selected by examining wear-leveling counters.

6. The flash-memory sub-system of claim 5 further comprising:

a history counter stored in each wear-leveling counter physical block, the history counter indicating a youngest wear-leveling counter physical block in the wear-leveling-counter pool, wherein the youngest wear-leveling counter physical block is the current wear-leveling counter physical block.

7. The flash-memory sub-system of claim 5 further comprising:

replacement means for replacing the current wear-leveling counter physical block with a new current wear-leveling counter physical block in the wear-leveling-counter pool when the selected physical block is erased and its wear-leveling counter needs to be updated,

whereby the current wear-leveling counter physical block is replaced.

8. The flash-memory sub-system of claim 1 further comprising:

a Secure Digital (SD) interface to a SD bus, wherein host requests with the LSA and the host data are received over the SD bus;

whereby flash-memory sub-system connects to the host through the SD interface.

9. The flash-memory sub-system of claim 1 further comprising:

a Serial AT-Attachment (SATA) interface to a SATA bus, wherein host requests with the LSA and the host data are received over the SATA bus;

whereby flash-memory sub-system connects to the host through the SATA interface.

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

a Universal-Serial-Bus (USB) interface to a USB bus, wherein host requests with the LSA and the host data are received over the USB bus;

whereby flash-memory sub-system connects to the host through the USB interface.

11. A method for writing pages of data to a restrictive flash memory that does not allow regressive page writes comprising:

receiving a logical page number (LPN) from a host computer;

dividing the LPN by a number of pages per block to generate a quotient and a remainder;

using the quotient as an index into a first-level look-up table to locate a mapping entry;

reading a physical-block address (PBA) from the mapping entry in the first-level look-up table;

using the PBA read from the mapping entry of the first-level look-up table as an index into a second-level look-up table to locate a selected row for the PBA;

reading page-valid bits from the selected row of the second-level look-up table;

determining when the host computer is requesting a regressive page-write;

when the host computer is not requesting the regressive page-write, writing page data from the host computer to a selected page in a selected block of the restrictive flash memory, wherein the selected block is identified by the PBA, and wherein the selected page in the selected block is identified by the remainder, and setting a selected page-valid bit in the selected row of the second-level look-up table, wherein the selected page-valid bit is located within the selected row by the remainder;

when the host computer is requesting the regressive page-write,

identifying a new block that is empty of valid data;

copying valid pages of data from an old block identified by the PBA to the new block;

writing the page data from the host computer to a selected page in the new block, wherein the selected page in the new block is identified by the remainder;

wherein copying the valid pages of data from the old block and writing the page data from the host computer are performed together in ascending page order wherein regressive page-writes are prohibited;

over-writing the PBA in the mapping entry with a new PBA that identifies the new block;

copying the page-valid bits read from the selected row to a new selected row in the second-level look-up table, wherein the new selected row is located by the new PBA; and

setting a selected page-valid bit in the new selected row of the second-level look-up table, wherein the selected page-valid bit is located within the new selected row by the remainder,

whereby the regressive page-write forces copying of the valid pages of page-data from the old block to the new block.

12. The method of claim 11 wherein determining when the host computer is requesting the regressive page-write comprises:

using the remainder to select a subset of the page-valid bits above the selected page-valid bit within the selected row;

wherein the subset of the page-valid bits are for pages later than the selected page in a page-writing sequence that is not regressive;

indicating the regressive page-write when any page-valid bits in the subset are set,

whereby the subset of the page-valid bits from the second-level look-up table detects when the regressive page-write occurs.

13. The method of claim 12 further comprising:

combining the page-valid bits in the subset using a logical-OR function to generate a detect signal that indicates that the regressive page-write is requested.

14. The method of claim 13 wherein the subset of the page-valid bits further comprise the selected page-valid bit,

whereby over-writing the selected page triggers detection of the regressive page-write.

15. The method of claim 12 further comprising:

when the host computer is requesting the regressive page-write;

reading a sequential count for the old block;

incrementing the sequential count to generate a new sequential count,

whereby the sequential count is incremented when the regressive page-write forces copying of the valid pages of data from the old block to the new block.

16. The method of claim 15 further comprising:

when the host computer is requesting the regressive page-write;

over writing the sequential count with the new sequential count in the mapping entry in the first-level look-up table,

whereby the sequential count is stored in the first-level look-up table.

17. The method of claim 11 wherein identifying a new block that is empty of valid data further comprises:

reading a plurality of wear counters from a wear-level-counter physical block;

finding a lowest wear counter in the plurality of wear counters;

wherein the lowest wear counter in the wear-level-counter physical block corresponds to the new block.

18. The method of claim 11 further comprising:

locating a wear-level-counter physical block by reading block identifiers for blocks in the restrictive flash memory to find a wear block identifier that indicates the wear-level-counter physical block;

reading a plurality of wear counters from the wear-level-counter physical block;

finding a first lowest wear counter in the plurality of wear counters;

wherein the first lowest wear counter in the wear-level-counter physical block corresponds to the new block;

finding a second lowest wear counter in the plurality of wear counters;

wherein the second lowest wear counter in the wear-level-counter physical block corresponds to a second new block;

incrementing the first lowest wear counter to generate a first incremented wear counter;

incrementing the second lowest wear counter to generate a second incremented wear counter;

copying unchanged wear counters in the plurality of wear counters from the wear-level-counter physical block to the second new block;

wherein the unchanged wear counters in the plurality of wear counters exclude the first lowest wear counter and the second lowest wear counter;

writing the first incremented wear counter to the second new block;

writing the second incremented wear counter to the second new block;

writing the wear block identifier to the second new block to identify the second new block as a second wear-level-counter physical block; and

erasing the wear-level-counter physical block,

whereby the plurality of wear counters in the wear-level-counter physical block are relocated when wear counters are incremented.