SYSTEM, METHOD AND MEMORY DEVICE PROVIDING DATA SCRAMBLING COMPATIBLE WITH ON-CHIP COPY OPERATION

• US 20090204824A1
• Filed: 12/30/2008
• Published: 08/13/2009
• Est. Priority Date: 12/31/2007
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Inventors: Cheng, Steven S., Traister, Shai, Lin, Jason T.
• Granted Patent: US 8,301,912 B2
• Time in Patent Office: Days
• US Class Current: 713/193
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 21/72 in cryptographic circuits
• CPC Class Codes: G06F 21/725 operating on a secure reference time value
• CPC Class Codes: G06F 21/79 in semiconductor storage media, e.g. directly-addressable memories
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G11B 20/0021 involving encryption or decryption of contents recorded on or reproduced from a record carrier
• CPC Class Codes: G11C 11/5628 Programming or writing circuits; Data input circuits
• CPC Class Codes: G11C 16/0483 comprising cells having several storage transistors connected in series
• CPC Class Codes: G11C 16/3418 Disturbance prevention or evaluation; Refreshing of disturbed memory data
• CPC Class Codes: G11C 16/3427 Circuits or methods to prevent or reduce disturbance of the state of a memory cell when neighbouring cells are read or written
• CPC Class Codes: G11C 7/1006 Data managing, e.g. manipulating data before writing or reading out, data bus switches or control circuits therefor

Abstract

Data scrambling techniques implemented externally to a flash memory device are disclosed which can be used in concert with flash memory on-chip copy functionality operating internally to the flash device, thus supporting high performance copying operations. All the data stored in the flash may be scrambled, including headers and control structures. Robust file system operation may be achieved, including the capability to tolerate a power loss at any time, and yet be able to relocate data internally within the flash without having to de-scramble and then re-scramble the data. An exemplary hardware based solution has little or no impact on overall system performance, and may be implemented at very low incremental cost to increase overall system reliability. The data scrambling technique preferably uses a logical address, such as logical block address or logical page address, rather than a physical address, to determine a seed scrambling key.

Claims

1. A method for storing information in a non-volatile memory, said method comprising:

determining a starting key based upon a seed key and a logical page address associated with a group of data;

randomizing the group of data using a deterministic sequence of keys corresponding to the starting key; and

storing the randomized group of data into a physical page of the non-volatile memory.

2. The method as recited in claim 1 further comprising storing, into the physical page of the non-volatile memory, additional information from which the starting key may be determined without knowledge of the logical page address.

3. The method as recited in claim 2 further comprising:

storing the additional information into more than one location within the physical memory page, so that even if one location is corrupted, another can still be read to determine the starting key.

4. The method as recited in claim 2 wherein the determining step comprises:

determining an index for a sequence of scrambling keys based upon a logical page offset value; and

using the index to identify the starting key within a repeating sequence of M-bit scrambling keys corresponding to the seed key.

5. The method as recited in claim 4 wherein:

the additional information comprises the index.

6. The method as recited in claim 2 further comprising:

storing the additional information as randomized information using the deterministic sequence of keys corresponding to the starting key.

7. The method as recited in claim 2 wherein:

the additional information comprises a mapped page offset code having a 1;

1 correspondence with a page offset value.

8. The method as recited in claim 7 wherein:

the mapped page offset code is identical with the logical page offset value, and may be directly read from the physical page of the non-volatile memory without de-randomizing.

9. The method as recited in claim 7 further comprising:

determining a page code associated with the logical page offset value; and

randomizing the page code using the deterministic sequence of keys corresponding to the starting key, to generate the mapped page offset code which is stored in the physical page of the non-volatile memory.

10. The method as recited in claim 9 wherein:

the page code is randomized using only the starting key, and the resulting mapped page offset code is written into a page header of the physical page of the non-volatile memory.

11. The method as recited in claim 9 wherein:

the page code is determined by firmware; and

the page code is randomized by hardware.

12. The method as recited in claim 7 further comprising initializing the non-volatile memory upon power-up, said initializing comprising:

reading a randomized memory page header including a mapped page offset code;

extracting a corresponding page offset value from the mapped page offset code;

then

determining a starting key based upon the page offset value and the seed key; and

reading and de-randomizing the memory page using a deterministic sequence of scrambling keys corresponding to the starting key.

13. The method as recited in claim 12 wherein said extracting a corresponding page offset value comprises using a lookup table.

14. The method as recited in claim 12 wherein said extracting a corresponding page offset value comprises using a reverse mapping calculation.

15. The method as recited in claim 12 wherein said de-randomizing the memory page comprises de-randomizing at least the memory page header using firmware.

16. The method as recited in claim 12 wherein said de-randomizing the memory page is performed using hardware.

17. The method as recited in claim 12 further comprising:

re-constructing mapping of open blocks to identify block types.

18. The method as recited in claim 7 further comprising:

determining a second starting key based upon the seed key and a physical page address associated with a second group of data;

randomizing the second group of data using a deterministic sequence of keys corresponding to the second starting key; and

storing the randomized second group of data into a second physical page of the non-volatile memory.

19. The method as recited in claim 18 wherein said initializing step is performed on blocks whose starting key is based upon its logical page address and on blocks whose starting key is based upon its physical page address.

20. The method as recited in claim 18 wherein:

the second group of data corresponds to a control block of a flash file system.

21. The method as recited in claim 7 further comprising:

determining a third starting key based upon a predetermined default seed key and a physical page address associated with a third group of data;

randomizing the third group of data using a deterministic sequence of keys corresponding to the third starting key; and

storing the randomized third group of data into a third physical page of the non-volatile memory.

22. The method as recited in claim 1 further comprising:

ECC encoding the randomized group of data and storing non-randomized ECC redundancy bytes in the non-volatile memory.

23. The method as recited in claim 1 further comprising:

ECC encoding the non-randomized group of data to generate corresponding ECC bytes;

randomizing the corresponding ECC redundancy bytes; and

storing randomized ECC redundancy bytes in the non-volatile memory.

24. The method as recited in claim 2 further comprising:

randomizing all page header information written into the non-volatile memory.

25. The method as recited in claim 24 further comprising:

randomizing control blocks for a flash file system using a physical page address rather than a logical page address.

26. The method as recited in claim 24 further comprising:

randomizing boot blocks for a flash file system using a predetermined default seed key, and using a physical page address.

27. The method as recited in claim 1 wherein the deterministic sequence of keys comprises:

a number M of separate scrambling keys, each comprising M-bits, wherein each respective scrambling key N (KeyN) corresponds to an N-bit circular rotation of a predetermined seed key (Key0).

28. The method as recited in claim 27 wherein the randomizing comprises a bit-by-bit XOR operation using the deterministic sequence of M-bit scrambling keys.

29. The method as recited in claim 28 wherein each successive scrambling key in the deterministic sequence is a single-bit rotation of the preceding scrambling key.

30. The method as recited in claim 28 wherein each successive scrambling key in the deterministic sequence is a bit-wise rotation of the seed key by a calculated number of bits.

31. The method as recited in claim 30 wherein the calculated number of bits for the successive key depends on the current key.

32. The method as recited in claim 31 wherein the calculated number of bits for the successive key also depends on the page offset value and the D-word offset value of the corresponding successive word.

33. The method as recited in claim 1 wherein the deterministic sequence of keys comprises:

a pseudo-random sequence of keys generated by a linear feedback shift register (LFSR) having a starting value corresponding to the starting key.

34. A method for storing data in a non-volatile memory comprising:

determining a page offset number using a logical block address of a memory page;

determining a starting key based upon a seed key and the page offset number;

scrambling page data using a deterministic sequence of scrambling keys corresponding to the starting key;

storing into a header of a physical page of the non-volatile memory an identifier corresponding to the page offset number; and

storing the scrambled page data into the physical page.

35. The method as recited in claim 34 wherein the identifier comprises an index to identify the starting key within a repeating sequence of M-bit scrambling keys corresponding to the seed key.

36. The method as recited in claim 35 further comprising:

determining a page code associated with the page offset value; and

randomizing the page code using the deterministic sequence of scrambling keys corresponding to the starting key, to generate a mapped page offset code which is stored in the physical page of the non-volatile memory.

37. The method as recited in claim 35 further comprising initializing the non-volatile memory upon power-up, said initializing comprising:

reading a randomized memory page header including a mapped page offset code;

extracting a corresponding page offset value from the mapped page offset code;

then

determining a starting key based upon the page offset value and the seed key; and

reading and de-randomizing the memory page using a deterministic sequence of scrambling keys corresponding to the starting key.

38. The method as recited in claim 34 further comprising:

ECC encoding the randomized page data and storing non-randomized ECC redundancy bytes in the non-volatile memory.

39. The method as recited in claim 34 further comprising:

randomizing all page header information written into the non-volatile memory.

40. The method as recited in claim 34 wherein the deterministic sequence of keys comprises:

a number M of separate scrambling keys, each comprising M-bits, wherein each respective scrambling key N (KeyN) corresponds to an N-bit circular rotation of a predetermined seed key (Key0).

41. The method as recited in claim 40 wherein the randomizing comprises a bit-by-bit XOR operation using the deterministic sequence of M-bit scrambling keys.

42. An apparatus comprising:

a non-volatile memory; and

a memory controller configured to;

determine a starting key based upon a seed key and a logical page address associated with a group of data;

randomize the group of data using a deterministic sequence of keys corresponding to the starting key; and

store the randomized group of data into a physical page of the non-volatile memory.

43. The apparatus as recited in claim 42 wherein the non-volatile memory comprises a distinct integrated circuit separate from the memory controller.

44. The apparatus as recited in claim 42 wherein the memory controller is further configured to store, into the physical page of the non-volatile memory, additional information from which the starting key may be determined without knowledge of the logical page address.

45. The apparatus as recited in claim 44 wherein the memory controller is further configured to:

determine an index for a sequence of scrambling keys based upon a logical page offset value; and

use the index to identify the starting key within a repeating sequence of M-bit scrambling keys corresponding to the seed key.

46. The apparatus as recited in claim 45 wherein:

the additional information comprises the index.

47. The apparatus as recited in claim 44 wherein:

the additional information is stored as randomized information using the deterministic sequence of keys corresponding to the starting key.

48. The apparatus as recited in claim 44 wherein:

the additional information comprises a mapped page offset code having a 1;

1 correspondence with a page offset value.

49. The apparatus as recited in claim 48 wherein the memory controller is further configured to:

determine a page code associated with the logical page offset value; and

randomize the page code using the deterministic sequence of keys corresponding to the starting key, to generate the mapped page offset code which is stored in the physical page of the non-volatile memory.

50. The apparatus as recited in claim 49 wherein:

the page code is randomized using only the starting key, and the resulting mapped page offset code is written into a page header of the physical page of the non-volatile memory.

51. The apparatus as recited in claim 48 wherein the memory controller is further configured for initializing the non-volatile memory upon power-up, said initializing comprising:

reading a randomized memory page header including a mapped page offset code;

extracting a corresponding page offset value from the mapped page offset code;

then

determining a starting key based upon the page offset value and the seed key; and

reading and de-randomizing the memory page using a deterministic sequence of scrambling keys corresponding to the starting key.

52. The apparatus as recited in claim 48 wherein the memory controller is further configured to:

determine a second starting key based upon the seed key and a physical page address associated with a second group of data;

randomize the second group of data using a deterministic sequence of keys corresponding to the second starting key; and

store the randomized second group of data into a second physical page of the non-volatile memory.

53. The apparatus as recited in claim 52 wherein said initializing is performed on blocks whose starting key is based upon its logical page address and on blocks whose starting key is based upon its physical page address.

54. The apparatus as recited in claim 52 wherein:

the second group of data corresponds to a control block of a flash file system.

55. The apparatus as recited in claim 48 wherein the memory controller is further configured to:

determine a third starting key based upon a predetermined default seed key and a physical page address associated with a third group of data;

randomize the third group of data using a deterministic sequence of keys corresponding to the third starting key; and

store the randomized third group of data into a third physical page of the non-volatile memory.

56. The apparatus as recited in claim 42 wherein:

the randomized group of data is ECC encoded and non-randomized ECC redundancy bytes are stored in the non-volatile memory.

57. The apparatus as recited in claim 44 wherein:

all page header information written into the non-volatile memory is randomized.

58. The apparatus as recited in claim 57 wherein:

control blocks for a flash file system are randomized using a physical page address rather than a logical page address.

59. The apparatus as recited in claim 57 wherein:

boot blocks for a flash file system are randomized using a predetermined default seed key, and using a physical page address corresponding to the boot block.

60. The apparatus as recited in claim 42 wherein the deterministic sequence of keys comprises:

a number M of separate scrambling keys, each comprising M-bits, wherein each respective scrambling key N (KeyN) corresponds to an N-bit circular rotation of a predetermined seed key (Key0).

61. The apparatus as recited in claim 60 wherein the randomizing comprises a bit-by-bit XOR operation using the deterministic sequence of M-bit scrambling keys.

62. The apparatus as recited in claim 61 wherein each successive scrambling key in the deterministic sequence is a single-bit rotation of the preceding scrambling key.

63. The apparatus as recited in claim 61 wherein each successive scrambling key in the deterministic sequence is a bit-wise rotation of the seed key by a calculated number of bits.

64. The apparatus as recited in claim 63 wherein the calculated number of bits for the successive key depends on the current key.

65. The apparatus as recited in claim 64 wherein the calculated number of bits for the successive key also depends on the page offset value and the D-word offset value of the corresponding successive word.

66. The apparatus as recited in claim 42 wherein the deterministic sequence of keys comprises:

a pseudo-random sequence of keys generated by a linear feedback shift register (LFSR) having a starting value corresponding to the starting key.