Method for storing data in a write-once memory array using a write-many file system

• US 7,051,251 B2
• Filed: 12/20/2002
• Issued: 05/23/2006
• Est. Priority Date: 12/20/2002
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Matrix Semiconductor, Inc. (Western Digital Corporation)
• Inventors: Yang, Chia, Moore, Christopher S., Fruin, Richard M., Loudon, Kyle
• Primary Examiner(s): DILDINE JR, R STEPHEN
• Application Number:
  US10/327,680
• Publication Number:
  US 20040123064A1
• Time in Patent Office: 1,250 Days
• Field of Search: 714/710
• US Class Current: 714/710
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

The preferred embodiments described herein provide various data allocation and error recovery methods that allow data to be written to a write-once memory array using a write-many file system. Other preferred embodiments described herein relate to methods for generating a set of valid file system structures. The various preferred embodiments can be used alone or in combination with one another.

Claims

1. A method for writing data to a write-once memory array, the method comprising:

(a) providing a write-once memory array comprising a file allocation table and a main memory, wherein a line is a minimum amount of data that can be written to the write-once memory array, and a line of clusters comprises an amount of clusters in the main memory represented by one line of entries written in the file allocation table;

(b) for a first set of X lines of clusters, wherein X≧

2;

(b1) writing entries in the file allocation table for all but the last line of clusters in the first set of X lines of clusters; and

(b2) writing data in the first set of X lines of clusters in the main memory; and

(c) if no error occurs in writing data in the first set of X lines of clusters;

(c1) writing entries in the file allocation table for all but the last line of clusters in a second set of X lines of clusters;

(c2) writing data in the second set of X lines of clusters in the main memory; and

(c3) if no error occurs in writing data in the second set of X lines of clusters, writing an entry in the file allocation table for the last line of clusters in the first set of X lines of clusters.

2. The invention of claim 1 further comprising:

(d) if an error occurs in writing data in a first line of clusters in the first set, writing the data in available clusters in the main memory and creating a directory entry pointing to a first cluster in said available clusters.

3. The invention of claim 1 further comprising:

(d) if an error occurs in writing data in a first cluster of a second line of clusters in the first set, writing the data that would have been written in the first cluster in an available cluster in main memory, generating a new file allocation table, and ensuring that the new file allocation table is read instead of the first-mentioned file allocation table.

4. The invention of claim 1 further comprising:

(d) if an error occurs in writing data in a cluster, other than the first cluster, of a second line of clusters in the first set, writing the data that would have been written in said cluster in an available cluster and writing an entry in the file allocation table for the available cluster.

5. The invention of claim 1 further comprising:

(d) if an error occurs in writing data in a cluster of a first line of clusters in the second set, writing the data that would have been written in said cluster in an available cluster and writing an entry in the file allocation table for the available cluster.

6. The invention of claim 1 further comprising:

(d) if an error occurs in writing an entry in the file allocation table, generating a new file allocation table, and ensuring that the new file allocation table is read instead of the first-mentioned file allocation table.

7. The invention of claim 1, wherein the data being written into the main memory comprises a file of unknown size.

8. The invention of claim 1, wherein X is fixed.

9. The invention of claim 1, wherein X is variable.

10. The invention of claim 1, wherein X=2.

11. The invention of claim 1, wherein the memory array comprises a plurality of memory cells arranged in a plurality of layers stacked vertically above one another in a single integrated circuit.

12. The invention of claim 1 further comprising:

(d) if an error occurs in writing data in a first cluster of a second line of clusters in the first set, writing data intended to be stored in the first and second lines of clusters in available clusters in main memory and creating a file allocation table entry pointing to a first cluster in said available clusters.

13. The invention of claim 1 further comprising:

(d) if an error occurs in writing data in a first cluster of a second line of clusters in the first set, determining which of the following acts requires less memory overhead and performing that act;

(d1) writing the data that would have been written in the first cluster in an available cluster in main memory, generating a new file allocation table, and ensuring that the new file allocation table is read instead of the first-mentioned file allocation table; and

(d2) writing data intended to be stored in the first and second lines of clusters in available clusters in main memory and creating a file allocation table entry pointing to a first cluster in said available clusters.

14. A method for writing data to a write-once memory array, the method comprising:

(a) providing a write-once memory array comprising a file allocation table and a main memory, wherein a line is a minimum amount of data that can be written to the write-once memory array, and a line of clusters comprises an amount of clusters in the main memory represented by one line of entries written in the file allocation table;

(b) writing data in a line of clusters in the main memory; and

(c) if no error occurs in writing data in the line of clusters, writing a line of entries in the file allocation table for the line of clusters.

15. The invention of claim 14 further comprising:

(d) if an error occurs in writing data in a first cluster in the line of clusters and the line of clusters is the first line of clusters in a file, writing the data in an available line of clusters in the main memory and creating a directory entry pointing to a first cluster in said available line of clusters.

16. The invention of claim 14 further comprising:

(d) if an error occurs in writing data in a first cluster in the line of clusters and the line of clusters is not the first line of clusters in a file, writing the data that would have been written in the first cluster in an available cluster in main memory, generating a new file allocation table, and ensuring that the new file allocation table is read instead of the first-mentioned file allocation table.

17. The invention of claim 14 further comprising:

(d) if an error occurs in writing data in a cluster other than the first cluster in the line of clusters, writing the data that would have been written in said cluster in an available cluster and writing an entry in the file allocation table for the available cluster.

18. The invention of claim 14 further comprising:

(d) if an error occurs in writing an entry in the file allocation table, generating a new file allocation table, and ensuring that the new file allocation table is read instead of the first-mentioned file allocation table.

19. The invention of claim 14, wherein the data being written into the main memory comprises a file of known size.

20. The invention of claim 14, wherein the memory array comprises a plurality of memory cells arranged in a plurality of layers stacked vertically above one another in a single integrated circuit.

21. The invention of claim 14 further comprising:

(d) if an error occurs in writing data in a first cluster in the line of clusters and the line of clusters is not the first line of clusters in a file, writing data intended to be stored in the line of clusters and in a previously-written line of clusters in available clusters in main memory and creating a file allocation table entry pointing to a first cluster in said available clusters.

22. The invention of claim 14 further comprising:

(d) if an error occurs in writing data in a first cluster in the line of clusters and the line of clusters is not the first line of clusters in a file, determining which of the following acts requires less memory overhead and performing that act;

(d1) writing the data that would have been written in the first cluster in an available cluster in main memory, generating a new file allocation table, and ensuring that the new file allocation table is read instead of the first-mentioned file allocation table; and

(d2) writing data intended to be stored in the line of clusters and in a previously-written line of clusters in available clusters in main memory and creating a file allocation table entry pointing to a first cluster in said available clusters.

23. A method for writing data to a write-once memory array, the method comprising:

(a) providing a write-once memory array comprising a file allocation table and a main memory, wherein a line is a minimum amount of data that can be written to the write-once memory array, and a line of clusters comprises an amount of clusters in the main memory represented by one line of entries written in the file allocation table;

(b) writing a line of entries in the file allocation table; and

(c) writing data in a line of clusters represented by the line of entries.

24. The invention of claim 23 further comprising:

(d) if an error occurs in writing data in the line of clusters, writing a second line of entries in the file allocation table and writing data in a second line of clusters represented by the second line of entries.

25. The invention of claim 23 further comprising:

(d) if an error occurs in writing an entry in the file allocation table, generating a new file allocation table, and ensuring that the new file allocation table is read instead of the first-mentioned file allocation table.

26. The invention of claim 23, wherein the data being written into the main memory comprises a file of known size.

27. The invention of claim 23, wherein the memory array comprises a plurality of memory cells arranged in a plurality of layers stacked vertically above one another in a single integrated circuit.

28. A method for generating a set of valid file system structures, the method comprising:

(a) providing a write-once memory array storing a set of file system structures;

(b) invalidating at least some of the set of file system structures; and

(c) re-writing the set of file system structures in a different part of the write-once memory array;

wherein the at least some of the set of file system structures invalidated in (b) are not re-written in (c).

29. The invention of claim 28, wherein each file system structure comprises a respective attribute field, and wherein (b) comprises storing an invalid bit in the respective attribute fields of the at least some of the set of file system structures.

30. The invention of claim 28, wherein a line is a minimum amount of data that can be written to the write-once memory array, wherein each file system structure comprises a plurality of lines, and wherein (b) comprises storing a line of invalid bits only in the line of the file system structure that comprises the attribute field.

31. The invention of claim 28, wherein (b)–

(c) are performed in response to a rename operation.

32. The invention of claim 28, wherein (b)–

(c) are performed in response to a move operation.

33. The invention of claim 28, wherein (b)–

(c) are performed in response to a delete operation.

34. The invention of claim 28, wherein the set of file system structures comprises a directory.

35. The invention of claim 28, wherein the set of file system structures comprises a sub-directory.

36. The invention of claim 28, wherein (b)–

(c) are performed in response to a change in an attribute field of a file.

37. The invention of claim 28, wherein (b)–

(c) are performed in response to a change to any information about a file.