Non-regular parity distribution detection via metadata tag

• US 8,726,126 B2
• Filed: 03/23/2010
• Issued: 05/13/2014
• Est. Priority Date: 03/23/2010
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Post, Daniel J.
• Primary Examiner(s): Bhatia, Ajay
• Assistant Examiner(s): Nguyen, Thien D
• Application Number:
  US12/729,564
• Publication Number:
  US 20110239088A1
• Time in Patent Office: 1,512 Days
• Field of Search: 714/763, 714/805, 714/746, 714/E11.032, 714/E11.034
• US Class Current: 714/763
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence

Abstract

This can relate to non-regular parity distribution of a non-volatile memory (“NVM”), such as flash memory, and detection of the non-regular parity via a metadata tag. For example, each codeword of the NVM can include one or more parity pages that may be distributed at random through the NVM. To identify the page as a parity page, a parity page marker can be included in the metadata of that page. During power-up of the NVM, an address table including the logical-to-physical address mapping of the pages can be created. Pages including a parity page marker, however, can be skipped during the creation of this address table. Additionally, by having two or more parity pages associated with a codeword, an additional layer of protection can be provided for repairing errors in that codeword.

Claims

1. A method of storing user data in a non-volatile memory (“

NVM”

), wherein the NVM comprises a plurality of pages, the method comprising;

selecting an encoding technique to employ on the user data, wherein the size of the user data is larger than the size of one of the plurality of pages;

applying the encoding technique to the user data to generate at least one page worth of parity data;

programming the user data in a first portion of the plurality of pages;

storing the parity data in a second portion of the plurality of pages, wherein the storing comprises marking a metadata field in each page of the second portion to indicate the second portion stores the parity data; and

based on the metadata field, not including the second portion of the plurality of pages in a mapping address table of the NVM.

2. The method of claim 1, wherein the second portion comprises at least two pages.

3. The method of claim 1, further comprising:

redundantly storing the metadata field indicating the second portion stores the parity data in a second memory location of the NVM.

4. The method of claim 1, wherein the second portion comprises a non-regular distribution across the NVM.

5. The method of claim 1, further comprising:

determining the first portion comprises at least one uncorrectable page; and

using the parity data to repair the at least one uncorrectable page.

6. The method of claim 1, wherein the non-volatile memory comprises flash memory.

7. A method for building a logical-to-physical mapping address table of a non-volatile memory (“

NVM”

), wherein the NVM comprises a plurality of pages and wherein each page is associated with a unique physical address, the method comprising;

processing a first page of the plurality of pages by;

reading a first metadata tag of the first page, wherein the first metadata tag indicates whether or not the first page is a parity page;

in response to determining the first metadata tag indicates the first page is not a parity page;

determining a first logical address of the first page;

storing the first logical address with the first page'"'"'s unique physical address in the logical-to-physical mapping address table; and

in response to determining the first metadata tag indicates the first page is a parity page, skipping the first page such that the first logical address is not stored in the address table.

8. The method of claim 7, further comprising:

determining the NVM has powered on; and

wherein the reading of the first metadata tag occurs in response to determining the NVM has powered on.

9. The method of claim 7, further comprising:

sequentially processing each page of the plurality of pages by proceeding to a next page of the plurality of pages and performing the processing on the next page until a final page of the plurality has been processed.

10. The method of claim 7, wherein determining a first logical address comprises:

reading the first logical address from metadata of the first page.

11. An electronic device comprising:

a non-volatile memory (“

NVM”

) comprising a plurality of pages wherein;

a subset of the plurality of pages are parity pages; and

the plurality of pages are grouped into a plurality of codewords, each codeword of the plurality of codewords comprising at least two contiguous pages of the plurality of pages and comprising at least one parity page, and wherein each codeword of at least a first subset of the plurality of codewords comprise at least two parity pages; and

a processor for controlling access to the plurality of pages of the NVM, wherein the processor is configured to;

mark a metadata field in each parity page to indicate the page is a parity page; and

based on the metadata field, not include any parity page in a mapping address table of the NVM.

12. The electronic device of claim 11, further comprising:

an error correcting code module configured to;

apply an encoding technique to user data of a particular codeword of the plurality of codewords to generate parity data associated with the particular codeword; and

wherein the processor is further configured to;

store the parity data in at least one parity page of the particular codeword.

13. The electronic device of claim 11, wherein the processor is further configured to:

retrieve each page of a particular codeword;

identify, during the retrieving, an uncorrectable page of the particular codeword;

scan left, in response to the encountering, to buffer data of each page in the particular codeword previous to the uncorrectable page;

scan right, in response to the encountering, to determine an end of the particular codeword; and

buffer data of the uncorrectable page and data of each page in the codeword after the uncorrectable page as each page after the uncorrectable page is retrieved.

14. The electronic device of claim 13, wherein the processor is further configured to:

determine a beginning of the particular codeword by scanning left until a parity page marker is encountered.

15. The electronic device of claim 13, wherein the processor is further configured to:

determine a beginning of the particular codeword by scanning left until a first page metadata tag is encountered.

16. The electronic device of claim 13, wherein the processor is further configured to:

determine the end of the particular codeword by scanning right until a non-parity page marker following a parity page marker is encountered.

17. The electronic device of claim 13, wherein the processor is further configured to:

determine the end of the particular codeword by scanning right until a first page metadata tag is encountered.

18. The electronic device of claim 13, wherein the processor is further configured to:

repair the uncorrectable page based on the buffered data and at least one parity page comprised in the particular codeword.

19. The electronic device of claim 11, wherein the processor is further configured to:

generate at least two parity equations based on a preliminary assumption that a particular codeword comprises a first number of assumed parity pages;

retrieve the particular codeword; and

update calculations of the at least two parity equations with data of each page of the particular codeword as each page is retrieved.

20. The electronic device of claim 19, wherein the processor is further configured to:

determine, upon retrieving the end of the particular codeword, a second number of actual parity pages associated with the particular codeword by reading a metadata tag of each actual parity page;

determine the second number is less than the first number; and

discard all but a second number of the updated calculations of the at least two parity equations.

21. The electronic device of claim 19, wherein the processor is further configured to:

determine, upon retrieving the end of the particular codeword, a second number of actual parity pages associated with the particular codeword by reading a metadata tag of each actual parity page;

determine the second number is equal to the first number; and

use the updated calculations of the at least two parity equations to repair at least one uncorrectable page of the particular codeword.

22. The electronic device of claim 11, further comprising:

an integrated circuit package, wherein the NVM and the processor are included in the integrated circuit package.

23. The electronic device of claim 11, further comprising:

an integrated circuit package, wherein the NVM is included in the integrated circuit package, and wherein the processor is implemented in a system-on-a-chip external to the integrated circuit package.

24. The electronic device of claim 11, wherein the non-volatile memory comprises flash memory.

25. An electronic device comprising:

a non-volatile memory (“

NVM”

) comprising a plurality of pages wherein;

a subset of the plurality of pages are parity pages; and

the plurality of pages are grouped into a plurality of codewords, each codeword of the plurality of codewords comprising at least two contiguous pages of the plurality of pages and comprising at least one parity page, and wherein each codeword of at least a first subset of the plurality of codewords comprise at least two parity pages; and

a processor for controlling access to the plurality of pages of the NVM, wherein the processor is configured to;

mark a metadata field in each parity page to indicate the page is a parity page;

generate at least two parity equations based on a preliminary assumption that a particular codeword comprises a first number of assumed parity pages;

retrieve the particular codeword; and

update calculations of the at least two parity equations with data of each page of the particular codeword as each page is retrieved.

26. The electronic device of claim 25, wherein the processor is further configured to:

determine, upon retrieving the end of the particular codeword, a second number of actual parity pages associated with the particular codeword by reading a metadata tag of each actual parity page;

determine the second number is less than the first number; and

discard all but a second number of the updated calculations of the at least two parity equations.

27. The electronic device of claim 25, wherein the processor is further configured to:

determine, upon retrieving the end of the particular codeword, a second number of actual parity pages associated with the particular codeword by reading a metadata tag of each actual parity page;

determine the second number is equal to the first number; and

use the updated calculations of the at least two parity equations to repair at least one uncorrectable page of the particular codeword.