Swappable sets of partial-mapping tables in a flash-memory system with a command queue for combining flash writes

• US 8,112,574 B2
• Filed: 12/31/2008
• Issued: 02/07/2012
• Est. Priority Date: 02/26/2004
• Status: Expired due to Fees

• Current Assignee: Super Talent Technology, Corporation
• Original Assignee: Super Talent Electronics, Inc.
• Inventors: Lee, Charles C., Yu, Frank, Ma, Abraham C.
• Primary Examiner(s): PATEL, KAUSHIKKUMAR M
• Application Number:
  US12/347,306
• Publication Number:
  US 20090113121A1
• Time in Patent Office: 1,133 Days
• Field of Search: None
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
• CPC Class Codes: G11C 16/102 External programming circuits, e.g. EPROM programmers; In-circuit programming or reprogramming; EPROM emulators
• CPC Class Codes: G11C 2216/30 Reduction of number of input/output pins by using a serial interface to transmit or receive addresses or data, i.e. serial access memory

Abstract

A flash controller has a flash interface accessing physical blocks of multi-level-cell (MLC) flash memory. An Extended Universal-Serial-Bus (EUSB) interface loads host commands into a command queue where writes are re-ordered and combined to reduce flash writes. A partial logical-to-physical L2P mapping table in a RAM has entries for only 1 of N sets of L2P mapping tables. The other N−1 sets are stored in flash memory and fetched into the RAM when a L2P table miss occurs. The RAM required for mapping is greatly reduced. A data buffer stores one page of host write data. Sector writes are merged using the data buffer. The data buffer is flushed to flash when a different page is written, while the partial logical-to-physical mapping table is flushed to flash when a L2P table miss occurs, when the host address is to a different one of the N sets of L2P mapping tables.

Claims

1. A partially-mapped flash-memory controller comprising:

a host interface coupled to a host and configured for receiving host commands and a host logical-sector address (LSA) for host data to be written to flash memory;

a flash interface to a flash memory;

an internal bus coupled to the flash interface;

a host buffer, coupled to the internal bus, configured for buffering data to and from the host interface;

a random-access memory (RAM) coupled to the internal bus;

a processor configured for executing controller routines, the processor coupled to the internal bus;

a page data buffer in the RAM, configured for storing a page of host data;

a command queue in the RAM, configured for storing a plurality of queue entries, each queue entry configured for storing the host command and the host LSA;

a partial logical-to-physical (L2P) mapping table in the RAM, the partial L2P mapping table having entries that each store a physical-block address (PBA) of a physical block in the flash memory;

N sets of partial L2P mapping tables stored in the flash memory;

wherein the partial L2P mapping table stores one set of entries identified by a stored set number, wherein the flash memory requires N sets of entries to map the flash memory, wherein N is a whole number of at least 64;

wherein the host LSA has a set number, an entry number, a page number, and a sector number;

wherein a selected entry in the partial L2P mapping table is usable for mapping to the physical block in the flash memory when the set number matches the stored set number, and the entry number selects the selected entry;

a tracking table in the RAM, the tracking table receiving the set number and outputting a table PBA that locates one of the N sets of partial L2P mapping tables stored in the flash memory;

wear-leveling counters that each indicate a number of erases of a different physical block in the flash memory;

wherein the entries in the partial L2P mapping table each further comprise a plurality of page-resident bits, each page-resident bit identifying when a bit'"'"'s page identified by a bit'"'"'s page number from a bit'"'"'s host LSA has been written to the flash memory;

a table miss routine, executed by the processor when the stored set number mis-matches the set number from the host LSA, configured for copying modified entries in the partial L2P mapping table to the flash memory, and configured for reading a new set from flash memory, the new set being one of the N sets of partial L2P mapping tables in flash memory, and configured for loading the new set to the partial L2P mapping table;

wherein a first stored page number identifies a first page number of a first host LSA of data currently stored in the data buffer;

wherein a first stored entry number identifies a first entry number of the first host LSA of data currently stored in the data buffer;

a buffer miss routine, executed by the processor when the first stored page number mis-matches the page number from the host LSA, or when the first stored entry number mis-matches the entry number from the host LSA, the buffer miss routine moving data stored in the data buffer to an old physical block in the flash memory, the old physical block being identified by an old PBA read from an old entry in the partial L2P mapping table, the old entry being located by the first stored entry number,

whereby the RAM stores one of N sets of mapping entries to partially map the flash memory and whereby page-resident bits are set in entries in the partial L2P mapping table.

2. The partially-mapped flash-memory controller of claim 1 further comprising:

an out-of-order check routine, executed by the processor, for examining the page-resident bits in the old entry in the partial L2P mapping table to determine when the page number from the host LSA is not a maximum of page numbers corresponding to the page-resident bits set for the old entry, and signaling an out-of-page-order flush when page number from the host LSA is not the maximum of page numbers; and

an out-of-order flush routine, activated when the out-of-page-order flush is signaled, comprising;

location means for locating an empty physical block in the flash memory using wear-leveling counters that indicate a number of erasures of a physical block;

first read means for reading an old PBA from the old entry and using the old PBA to read old pages from an old physical block in the flash memory;

first write means for writing in page-number-order the old pages to the empty physical block for pages having a page number that is lower than the stored page number;

second write means for writing data stored in the data buffer to the empty physical block after old pages having the page number that is lower than the stored page number have been written to the empty physical block;

third write means for writing in page-number-order the old pages to the empty physical block for pages having a page number that is greater than the stored page number after the data from the data buffer has been written to the empty physical block;

fourth write means for writing a new PBA that identifies the empty physical block to the old entry in the partial L2P mapping table; and

erase means for erasing the old physical block in the flash memory after the old pages have been read,

whereby old pages are re-ordered with the data stored in the data buffer when the out-of-page-order flush is signaled.

3. A partially-mapped flash-memory controller comprising:

a host interface coupled to a host and configured for receiving host commands and a host logical-sector address (LSA) for host data to be written to flash memory;

a flash interface to a flash memory;

an internal bus coupled to the flash interface;

a host buffer, coupled to the internal bus, configured for buffering data to and from the host interface;

a random-access memory (RAM) coupled to the internal bus;

a processor configured for executing controller routines, the processor coupled to the internal bus;

a page data buffer in the RAM, configured for storing a page of host data;

a command queue in the RAM, configured for storing a plurality of queue entries, each queue entry configured for storing the host command and the host LSA;

a partial logical-to-physical (L2P) mapping table in the RAM, the partial L2P mapping table having entries that each store a physical-block address (PBA) of a physical block in the flash memory;

N sets of partial L2P mapping tables stored in the flash memory;

wherein the partial L2P mapping table stores one set of entries identified by a stored set number, wherein the flash memory requires N sets of entries to map the flash memory, wherein N is a whole number of at least 64;

wherein the host LSA has a set number, an entry number, a page number, and a sector number;

wherein a selected entry in the partial L2P mapping table is usable for mapping to the physical block in the flash memory when the set number matches the stored set number, and the entry number selects the selected entry;

whereby the RAM stores one of N sets of mapping entries to partially map the flash memory;

wherein the host interface further comprises;

a physical layer that de-serializes data from the host received over a receive differential pair of lines, and that serializes data for transmission to the host over a transmit differential pair of lines, the physical layer adding a frame start and a frame end;

a transport layer that adds a header and a checksum to a data payload for transmission to the host;

a data-link layer coupled between the physical layer and the transport layer, the data-link layer adding a sequence number and a link-layer cyclical-redundancy-check (CRC) to transport-layer packets for transmission to the host;

a transmit Phase-Locked Loop (PLL) for generating a clock for synchronizing data sent over the transmit differential pair of lines to the host; and

a receive Phase-Locked Loop (PLL) for generating a clock for synchronizing data received from the host over the receive differential pair of lines.

4. The partially-mapped flash-memory controller of claim 3 wherein the host interface comprises an Extended Universal-Serial-Bus (EUSB) interface, a Serial AT Attachment (SATA) interface, an Integrated Device Electronics (IDE) interface, or a Non-Volatile Memory Host Controller Interface (NVMHCI).

5. A partial-mapping method for writing to a flash memory comprising:

receiving a host command from a host along with a host logical-sector address (LSA) from the host;

dividing the host LSA into a set number, an entry number, a page number, and a sector number;

comparing a stored set number with the set number from the host LSA to determine when a logical-to-physical (L2P) table hit occurs, wherein the stored set number indicates which one of N sets of partial logical-to-physical mapping tables is currently stored in a volatile L2P mapping table, wherein N is a whole number of at least 64;

when the volatile L2P table hit occurs, using the entry number from the host LSA to locate a selected entry in the volatile L2P mapping table;

wherein a data buffer stores one page of data, and has a stored page number and a stored entry number of data last stored into the data buffer;

when the page number from the host LSA matches the stored page number, and the entry number from the host LSA matches the stored entry number, and the volatile L2P table hit occurs, writing host data associated with the host command into the data buffer and completing the host command;

when the volatile L2P table hit occurs and the page number from the host LSA mis-matches the stored page number, or the volatile L2P table hit occurs and the entry number from the host LSA mis-matches the stored entry number, signaling a buffer miss; and

when the buffer miss is signaled, reading the data buffer and writing the buffered host data from the data buffer into a target physical block in the flash memory, the target physical block located by reading a physical-block address (PBA) from an old entry in the volatile L2P mapping table, the old entry identified by the stored entry number, and writing new host data associated with the host command into the data buffer and completing the host command,

whereby one of the N sets of partial logical-to-physical mapping tables from flash memory is currently stored in the volatile L2P mapping table allowing the volatile L2P table hit to write host data to the data buffer.

6. The partial-mapping method of claim 5 further comprising:

setting a page-resident bit in the selected entry in the volatile L2P mapping table;

wherein the page-resident bit that is set identifies the page number from the host LSA, whereby page-resident bits are set in entries in the volatile L2P mapping table.

7. The partial-mapping method of claim 6 further comprising:

when the buffer miss is signaled, examining the page-resident bits in the old entry in the volatile L2P mapping table to determine when the page number from the host LSA is not a maximum of page numbers corresponding to the page-resident bits set for the old entry, and signaling an out-of-page-order flush when page number from the host LSA is not the maximum of page numbers;

when the out-of-page-order flush is signaled;

locating an empty physical block in the flash memory using wear-leveling counters that indicate a number of erasures of a physical block;

reading an old PBA from the old entry and using the old PBA to read old pages from an old physical block in the flash memory;

writing in page-number-order the old pages to the empty physical block for pages having a page number that is lower than the stored page number;

writing the data stored in the data buffer to the empty physical block after old pages having the page number that is lower than the stored page number have been written to the empty physical block;

writing in page-number-order the old pages to the empty physical block for pages having a page number that is greater than the stored page number after the data from the data buffer has been written to the empty physical block;

writing a new PBA that identifies the empty physical block to the old entry in the volatile L2P mapping table; and

erasing the old physical block in the flash memory after the old pages have been read,

whereby old pages are re-ordered with the data stored in the data buffer when the out-of-page-order flush is signaled.

8. The partial-mapping method of claim 5 further comprising:

when the host command is a read command and the volatile L2P table hit occurs;

reading a physical block address (PBA) from the selected entry;

using the PBA to read requested data from the flash memory;

sending the requested data to the host.

9. The partial-mapping method of claim 5 further comprising:

when the volatile L2P table hit does not occur, signaling a volatile L2P table miss;

using the set number to locate a new set in N sets of partial logical-to-physical mapping tables that are stored in flash memory, and reading the new set from flash memory and writing the new set to the volatile L2P mapping table,

whereby the set number locates the new set in flash memory that is copied to the volatile L2P mapping table.

10. The partial-mapping method of claim 9 further comprising:

when the volatile L2P table hit does not occur, signaling a volatile L2P table miss;

examining a L2P modified flag that indicates when entries in the volatile L2P mapping table have been modified;

when the L2P modified flag is set, using the stored set number to locate a physical block of tables in the flash memory, and reading an old set from the volatile L2P mapping table and writing the old set to the physical block of tables in the flash memory,

whereby the old set is flushed to flash memory before over-writing the volatile L2P mapping table.

11. The partial-mapping method of claim 10 further comprising:

when the physical block of tables in the flash memory has no empty pages;

locating an empty physical block of tables in the flash memory using wear-leveling counters that indicate a number of erasures of a physical block;

writing the old set from the volatile L2P mapping table to the empty physical block of tables in flash memory; and

erasing the physical block of tables in the flash memory that had no empty pages.

12. The partial-mapping method of claim 5 further comprising:

wherein when a wear-leveling counter reaches a wear threshold value, performing static wear-leveling by moving static data from a least-worn physical block having a lowest wear-leveling count value to a most-worn empty physical block having the wear-leveling counter reaching the wear threshold value,

whereby static wear-leveling moves static data from the least-worn physical block to the most-worn empty physical block to make the least-worn physical block available for use by dynamic data.

13. The partial-mapping method of claim 12 wherein static data from the least-worn physical block is a master-boot record (MBR) that is not modified.

14. The partial-mapping method of claim 5 further comprising:

storing the host command into a command queue;

combining entries in the command queue for host commands that have overlapping host data to reduce a number of host commands writing to the flash memory,

whereby entries in the command queue are combined when host data is overlapping.