×

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
First Claim
Patent Images

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.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×