METHOD AND SYSTEM FOR IN-PLACE UPDATING CONTENT STORED IN A STORAGE DEVICE

• US 20100185921A1
• Filed: 01/13/2008
• Published: 07/22/2010
• Est. Priority Date: 01/11/2007
• Status: Active Grant

• Current Assignee: Red Bend Limited (Samsung Electronics Co. Ltd.)
• Original Assignee: Red Bend Limited (Samsung Electronics Co. Ltd.)
• Inventors: Meller, Evyatar, Peleg, Sharon
• Granted Patent: US 9,043,680 B2
• Time in Patent Office: Days
• US Class Current: 714/763
• CPC Class Codes: G06F 11/1433 during software upgrading
• CPC Class Codes: G06F 8/654 using techniques specially adapted for alterable solid state memories, e.g. for EEPROM or flash memories

Abstract

Methods and systems for in-place updating original content stored in a non-volatile storage device and for yielding updated content. Some of the described embodiments illustrate the possibilities for reduction in storage operations, storage blocks, and/or update package size. Some of the described embodiments include the writing of error recovery result(s) such as XOR result(s) which enable the recovery of data in case of an interruption of the update process. In some of the described embodiments, there is re-usage of a protection buffer containing content which is required in the update process.

Claims

1. A method for reliably in-place updating original content stored in storage blocks of a non-volatile storage to yield updated content, the method comprising:

obtaining an error recovery result indicative of a result achievable by applying a first error recovery function to data which is used in updating the original content, wherein a part of said data can be recovered by applying a second error recovery function to (i) said error recovery result and (ii) another part of said data;

after obtaining the error recovery result, updating the original content while storing the updated content to the non-volatile storage in place of the original content.

5. The method of claim 1, wherein the first error recovery function and the second error recovery function are identical.

6. The method of claim 1, wherein the first error recovery function and the second error recovery function are XOR.

7. The method of claim 1, wherein one of the first error recovery function and the second error recovery function is addition and the other is subtraction.

2. The method of claim Error! Reference source not found, wherein the data include original content.

3. The method of claim Error! Reference source not found, wherein the data include updated content.

4. The method of claim Error! Reference source not found, wherein the data include content that requires protection.

8. The method of claim Error! Reference source not found, wherein obtaining includes receiving the error recovery result from an external source.

9. The method of claim Error! Reference source not found, wherein obtaining includes calculating the error recovery result by applying the first error recovery function.

10. The method of claim 0, wherein the data include original content and at least one operand of said first error recovery function is the data.

11. The method of claim 0, wherein the data include updated content and at least one operand of said first error recovery function is the data.

12. The method of claim 0, wherein the data include content that requires protection, which is stored in one or more storage blocks, and at least one operand of said first error recovery function is the data.

13. An apparatus for reliably in-place updating original content stored in storage blocks of a non-volatile storage to yield updated content, the method comprising:

an error recovery result obtaining unit for obtaining an error recovery result indicative of a result achievable by applying a first error recovery function to data which is used in updating the original content, wherein a part of said data can be recovered by applying a second error recovery function to (i) said error recovery result and (ii) another part of said data; and

an updating processor responsive to said error recovery result for updating the original content while storing the updated content to the non-volatile storage in place of the original content.

14. The apparatus of claim 0, wherein the error recovery result obtaining unit is coupled to a calculator configured to calculating the error recovery result, by performing the first error recovery function.

15. A method for generating an update package that is configured for reliably in-place updating original content to yield updated content stored in n storage blocks of a non-volatile storage device, the method comprising:

obtaining a number (k);

generating the update package, wherein the update package is configured to instruct an update process to perform n+x storage operations, x is a function of k wherein x<

n.

16. A method for reliably in-place updating original content stored in storage blocks of a non-volatile storage to yield updated content, the method comprising:

obtaining an update package;

reliably in-place updating the original content while performing no backup storage operations.

17. A method for protecting data used for reliably in-place updating original content stored in storage blocks of a non-volatile storage device to yield updated content, the method comprising:

calculating an error recovery result, by performing an error recovery function, wherein at least one operand of said function includes one of the following;

(i) original content, (ii) updated content, and (iii) content that requires protection; and

writing said error recovery result into non-volatile memory.

20. The method of claim 17, wherein the error recovery function is XOR.

18. The method of claim 0, wherein said calculating is performed prior to storing updated content into the non-volatile storage device in place of original content.

19. The method of claim 0, wherein said calculating is performed during generation of an update package that is usable for reliably in-place updating the original content to yield the updated content.

21. An apparatus for protecting data, the data is used for reliably in-place updating original content stored in storage blocks of a non-volatile storage device to yield updated content, the apparatus comprising:

a calculator for calculating an error recovery result by performing an error recovery function, wherein at least one operand of said function includes one of the following;

(i) original content, (ii) updated content, and (iii) content that requires protection; and

an error recovery result writing unit responsive to said calculator for writing the error recovery result into a non-volatile memory.

22. The apparatus of claim 0, wherein the error recovery function is XOR.

23. A method for recovering non-reliable content that is a result of an interrupted in-place update of content stored in storage blocks of a non-volatile storage device, wherein one of the blocks stores non-reliable content and each one of the other blocks stores one of the following:

(i) original content, and (ii) updated content, the method comprising;

obtaining an error recovery result indicative of data, said data includes one of the following;

(i) original content, (ii) updated content, and (iii) content that requires protection;

recovering said non-reliable content by applying an error recovery function to said error recovery result and to one of the following;

(a) content stored in the other blocks, (b) content calculated based on content stored in the other blocks, and (c) content requiring protection calculated based on the content stored in the other blocks.

24. The method of claim 0, wherein said error recovery function is XOR.

25. An apparatus for recovering non-reliable content that is a result of an interrupted in-place update of content stored in storage blocks of a non-volatile storage device, wherein one of the blocks stores the non-reliable content and each one of other blocks stores one of the following:

(i) original content, and (ii) updated content, the apparatus comprising;

an error recovery result obtaining unit for obtaining an error recovery result indicative of data, said data includes one of the following;

(i) original content, (ii) updated content, and (iii) content that requires protection;

a recovery processor responsive to said error recovery result for recovering said non-reliable content by applying an error recovery function to said error recovery result and to one of the following (a) content stored in the other blocks or (b) content calculated based on content stored in the other blocks or (c) content requiring protection calculated based on the content stored in the other blocks.

26. A method for reliably in-place updating original content of an original version stored in non-volatile storage including blocks to yield updated content of an updated version, comprising:

applying a first subgroup of an error recovery group of functions to data which is used in achieving an updated version in non-volatile storage, thereby generating an error recovery result; and

storing said error recovery result in non-volatile storage prior to writing updated content from volatile memory to non-volatile storage in place of original content;

wherein a part of said data can be recovered by applying another subgroup of said error recovery group of functions to said error recovery result and a result of said first subgroup applied to another part of said data.

27. The method of claim 0, wherein said group of error recovery functions includes a pair of XOR functions.

28. The method of claim 0, further comprising:

updating original content to updated content in volatile memory;

wherein said data includes at least some of said updated content in volatile memory.

29. The method of claim 0, wherein said data includes at least some of said original content.

30. The method of claim 0, wherein said error recovery result is stored in a predetermined number of blocks in non-volatile storage.

31. The method of claim 0, wherein said predetermined number is 1.

32. The method of claim 0, wherein said group of functions is a pair of error recovery functions, said subgroup is one error recovery function from said pair, and said another subgroup is another error recovery function from said pair.

33. The method of claim 0, wherein there is an update sequence for updating content in blocks in said non volatile storage, the method further comprising:

protecting original content in at least one instance of a protection buffer in volatile memory,

wherein said data includes said at least one protection buffer instances.

34. The method of claim 0, wherein said error recovery result is stored in a number of blocks in said non-volatile storage equivalent to a number of blocks in one protection buffer instance.

35. The method of claim 0, further comprising:

after an interruption which erases volatile memory, retrieving said stored error recovery result from non volatile storage to volatile memory;

recovering a part of said data by applying said another subgroup of said recovery group of functions to said error recovery result and a result of said first subgroup applied to another part of said data; and

utilizing said recovered part of data to write content to non-volatile storage.

36. The method of claim 0, wherein said recovered part of said data includes updated content corresponding to a block in said non-volatile storage;

and wherein said another part of said data includes updated content associated with at least one other block which is not said block corresponding to said recovered updated content, and wherein said utilizing includes writing said recovered updated content to said corresponding storage block.

37. The method of claim 0, wherein said recovered part of said data includes original content corresponding to a block in said storage;

and wherein said another part of said data includes original content original associated with at least one other block which is not said block corresponding to said recovered original content;

said method further comprising;

updating said recovered original content, wherein said utilizing includes;

writing said updated recovered original content to said corresponding storage block.

38. The method of claim 0, further comprising:

rebuilding each at least one protection buffer instances using original or updated content from non-volatile storage except for one protection buffer instance which can not be rebuilt based on said original or updated content;

wherein said recovered part of said data includes said protection buffer instance which can not be rebuilt, and wherein said another part of said data includes at least one rebuilt protection buffer instance; and

updating content using said recovered protection buffer instance, wherein said utilizing includes writing said updated content to said non-volatile storage.

39. A method for in-place updating original content of an original version stored in non-volatile storage including blocks to yield updated content of an updated version, wherein there is an update sequence for updating content in said blocks in said non-volatile storage, the method comprising:

providing a predetermined number of blocks in non-volatile storage for storing a XOR result;

protecting original content in at least one instance of a protection buffer in volatile memory, each instance equivalent in size to said predetermined number of blocks and corresponding to at least one sequential block in said update sequence, wherein no two instances correspond to the same block in the update sequence and wherein for each instance, all original content protected in said instance originates from said at least one corresponding sequential blocks and is used to update said at least one corresponding sequential blocks;

performing at least one XOR operation, thereby generating a XOR result, wherein at least one operand in each said at least one XOR operation includes at least part of a protection buffer instance; and

writing said XOR result to said predetermined number of blocks prior to writing updated content from volatile memory to non-volatile storage in place of original content.

40. The method of claim 0, further comprising:

retrieving said stored XOR result from non volatile storage to volatile memory after an interruption which erases volatile memory and precludes rebuilding of a protection buffer instance from any of original or updated content in said non-volatile storage;

rebuilding each of said at least one protection buffer instances using original or updated content from non-volatile storage except for said protection buffer instance which can not be rebuilt based on said original or updated content;

executing at least one XOR operation, thereby recovering said protection buffer instance which can not be rebuilt, wherein at least one operand in each said at least one XOR operation includes said retrieved XOR result or at least part of a rebuilt protection buffer instance; and

updating content using said recovered protection buffer instance, and writing said updated content to said non-volatile storage.

41. A method for in-place updating original content of an original version stored in non-volatile storage including blocks to yield updated content of an updated version, comprising:

providing one block in non-volatile storage for storing a XOR result;

performing at least one XOR operation, thereby generating said XOR result, wherein at least one operand in each said at least one XOR operation includes original content corresponding to at least part of a storage block or wherein at least one operand in each said at least one XOR operation includes updated content corresponding to at least part of a storage block; and

writing said XOR result to said provided block prior to writing updated content from volatile memory to non-volatile storage in place of original content.

42. The method of claim 0, further comprising:

retrieving said stored XOR result from non volatile storage to volatile memory after an interruption which erases volatile memory and precludes restoration from non-volatile storage of some content corresponding to a block;

performing at least one XOR operation, thereby recovering said some content which could not be restored from non-volatile storage, wherein at least one operand in each said at least one XOR operation includes original content associated with at least part of a block which is not said block corresponding to said recovered content, or wherein at least one operand in each said at least one XOR operation includes updated content associated with at least part of a block which is not said block corresponding to said recovered content;

updating said recovered content if said recovered content is original content; and

writing said recovered updated content to said corresponding block in said non-volatile storage.

43. A method for in-place updating original content of an original version stored in non-volatile storage including blocks to yield updated content of an updated version, wherein there is an update sequence for updating content in said blocks in said non-volatile storage, the method comprising:

prior to updating a storage block in non-volatile storage;

(i) protecting in a protection buffer in volatile memory data related to said storage block which is required for updating said storage block or for updating any storage block later in said update sequence; and

(ii) and writing said data related to said storage block which is required for updating said corresponding storage block or for updating any storage block later in said update sequence, or writing a function thereof, to non-volatile storage;

wherein after using any of said data to update in volatile memory content corresponding to said storage block or corresponding to said any storage block later in said update sequence, said used data is replaced in said protection buffer by other data.

44. The method of claim 0, wherein said data related to said storage block which is required for updating said storage block or for updating said any storage block later in said update sequence includes original content from said storage block.

45. The method of claim 0, wherein said data related to said storage block which is required for updating said storage block or for updating said any storage block later in said update sequence also includes data to facilitate the locating of original content in the protection buffer.

46. The method of claim 0, wherein said function is a subgroup of an error recovery group of functions which encodes said data related to said storage block which is required for updating said storage block or for updating said any storage block later in said update sequence along with other data required for updating storage blocks.

47. The method of claim 0, wherein said subgroup is a XOR function.

48. The method of claim 0, further comprising:

after an interruption which erases volatile memory, retrieving said stored error recovery result from non volatile storage to volatile memory; and

recovering said data related to said storage block which is required for updating said storage block or for updating said storage any block later in said update sequence by applying another subgroup of said error recovery group of functions to said error recovery result and a result of said subgroup applied to said other data required for updating storage blocks.

49. The method of claim 0, further comprising:

after an interruption which erases volatile memory, retrieving said data related to said storage block which is required for updating said storage block or for updating said any storage block later in said update sequence from non volatile storage to volatile memory; and

utilizing said retrieved data to update said corresponding storage block in non-volatile storage.

50. A method for generating an update package for in place updating original content of an original version stored in non-volatile storage with blocks to yield updated content of an updated version, the method comprising:

providing a protection buffer of equivalent size to a predetermined number of blocks; and

prior to updating or simulating updating of content corresponding to a storage block, for each piece of data related to said corresponding storage block which is required for updating said corresponding storage block or for updating any storage block later in said update sequence performing the following;

if there is space available in said protection buffer, protecting or simulating protecting of said piece of data, but if there is no available space inserting said piece of data in said update package;

wherein after said protected or simulated to be protected piece of data has been used to update or simulate update of content corresponding to said storage block or corresponding to said any storage block later in said update sequence, said used piece of data is replaced or simulated to be replaced in said protection buffer by other data.

51-62. -62. (canceled)

63. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method for reliably in-place updating original content stored in storage blocks of a non-volatile storage to yield updated content, the method comprising:

obtaining an error recovery result indicative of a result achievable by applying a first error recovery function to data which is used in updating the original content, wherein a part of said data can be recovered by applying a second error recovery function to (i) said error recovery result and (ii) another part of said data;

after obtaining the error recovery result, updating the original content while storing the updated content to the non-volatile storage in place of the original content.

64. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for generating an update package that is configured for reliably in-place updating original content to yield updated content stored in n storage blocks of a non-volatile storage device, the method comprising:

obtaining a number (k);

generating the update package, wherein the update package is configured to instruct an update process to perform n+x storage operations, x is a function of k wherein x<

n.

65. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for reliably in-place updating original content stored in storage blocks of a non-volatile storage to yield updated content, the method comprising:

obtaining an update package;

reliably in-place updating the original content while performing no backup storage operations.

66. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for protecting data used for reliably in-place updating original content stored in storage blocks of a non-volatile storage device to yield updated content, the method comprising:

calculating an error recovery result, by performing an error recovery function, wherein at least one operand of said function includes one of the following;

(i) original content, (ii) updated content, and (iii) content that requires protection; and

writing said error recovery result into non-volatile memory.

67. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for recovering non-reliable content that is a result of an interrupted in-place update of content stored in storage blocks of a non-volatile storage device, wherein one of the blocks stores non-reliable content and each one of the other blocks stores one of the following:

(i) original content, and (ii) updated content, the method comprising;

obtaining an error recovery result indicative of data, said data includes one of the following;

(i) original content, (ii) updated content, and (iii) content that requires protection;

recovering said non-reliable content by applying an error recovery function to said error recovery result and to one of the following;

(a) content stored in the other blocks, (b) content calculated based on content stored in the other blocks, and (c) content requiring protection calculated based on the content stored in the other blocks.

68. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for reliably in-place updating original content of an original version stored in non-volatile storage including blocks to yield updated content of an updated version, comprising:

69. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform a method for reliably in-place updating original content stored in storage blocks of a non-volatile storage to yield updated content, the method comprising:

obtaining an error recovery result indicative of a result achievable by applying a first error recovery function to data which is used in updating the original content, wherein a part of said data can be recovered by applying a second error recovery function to (i) said error recovery result and (ii) another part of said data;

after obtaining the error recovery result, updating the original content while storing the updated content to the non-volatile storage in place of the original content.

70. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform a method for generating an update package that is configured for reliably in-place updating original content to yield updated content stored in n storage blocks of a non-volatile storage device, the method comprising:

obtaining a number (k);

generating the update package, wherein the update package is configured to instruct an update process to perform n+x storage operations, x is a function of k wherein x<

n.

71. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform a method for reliably in-place updating original content stored in storage blocks of a non-volatile storage to yield updated content, the method comprising:

obtaining an update package;

reliably in-place updating the original content while performing no backup storage operations.

72. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform a method for protecting data used for reliably in-place updating original content stored in storage blocks of a non-volatile storage device to yield updated content, the method comprising:

calculating an error recovery result, by performing an error recovery function, wherein at least one operand of said function includes one of the following;

(i) original content, (ii) updated content, and (iii) content that requires protection; and

writing said error recovery result into non-volatile memory.

73. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform a method for recovering non-reliable content that is a result of an interrupted in-place update of content stored in storage blocks of a non-volatile storage device, wherein one of the blocks stores non-reliable content and each one of the other blocks stores one of the following:

(i) original content, and (ii) updated content, the method comprising;

obtaining an error recovery result indicative of data, said data includes one of the following;

(i) original content, (ii) updated content, and (iii) content that requires protection;

recovering said non-reliable content by applying an error recovery function to said error recovery result and to one of the following;

(a) content stored in the other blocks, (b) content calculated based on content stored in the other blocks, and (c) content requiring protection calculated based on the content stored in the other blocks.

74. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform a method for reliably in-place updating original content of an original version stored in non-volatile storage including blocks to yield updated content of an updated version, comprising:

applying a first subgroup of an error recovery group of functions to data which is used in achieving an updated version in non-volatile storage, thereby generating an error recovery result; and

storing said error recovery result in non-volatile storage prior to writing updated content from volatile memory to non-volatile storage in place of original content;

wherein a part of said data can be recovered by applying another subgroup of said error recovery group of functions to said error recovery result and a result of said first subgroup applied to another part of said data.

75. A computer program product comprising a computer useable medium having computer readable program code embodied therein for reliably in-place updating original content of an original version stored in non-volatile storage including blocks to yield updated content of an updated version, the computer program product comprising:

computer readable program code for causing the computer to apply a first subgroup of an error recovery group of functions to data which is used in achieving an updated version in non-volatile storage, thereby generating an error recovery result; and

computer readable program code for causing the computer to store said error recovery result in non-volatile storage prior to writing updated content from volatile memory to non-volatile storage in place of original content;

computer readable program code for causing the computer to wherein a part of said data can be recovered by applying another subgroup of said error recovery group of functions to said error recovery result and a result of said first subgroup applied to another part of said data.

76. A computer program product comprising a computer useable medium having computer readable program code embodied therein for in-place updating original content of an original version stored in non-volatile storage including blocks to yield updated content of an updated version, wherein there is an update sequence for updating content in said blocks in said non-volatile storage, the computer program product comprising:

computer readable program code for causing the computer to providing a predetermined number of blocks in non-volatile storage for storing a XOR result;

computer readable program code for causing the computer to protecting original content in at least one instance of a protection buffer in volatile memory, each instance equivalent in size to said predetermined number of blocks and corresponding to at least one sequential block in said update sequence, wherein no two instances correspond to the same block in the update sequence and wherein for each instance, all original content protected in said instance originates from said at least one corresponding sequential blocks and is used to update said at least one corresponding sequential blocks;

computer readable program code for causing the computer to perform at least one XOR operation, thereby generating a XOR result, wherein at least one operand in each said at least one XOR operation includes at least part of a protection buffer instance; and

computer readable program code for causing the computer to writ said XOR result to said predetermined number of blocks prior to writing updated content from volatile memory to non-volatile storage in place of original content.

77. A computer program product comprising a computer useable medium having computer readable program code embodied therein for in-place updating original content of an original version stored in non-volatile storage including blocks to yield updated content of an updated version, the computer program product comprising:

computer readable program code for causing the computer to providing one block in non-volatile storage for storing a XOR result;

computer readable program code for causing the computer to perform at least one XOR operation, thereby generating said XOR result, wherein at least one operand in each said at least one XOR operation includes original content corresponding to at least part of a storage block or wherein at least one operand in each said at least one XOR operation includes updated content corresponding to at least part of a storage block; and

computer readable program code for causing the computer to writ said XOR result to said provided block prior to writing updated content from volatile memory to non-volatile storage in place of original content.

78. A computer program product comprising a computer useable medium having computer readable program code embodied therein for in-place updating original content of an original version stored in non-volatile storage including blocks to yield updated content of an updated version, wherein there is an update sequence for updating content in said blocks in said non-volatile storage, the computer program product comprising:

computer readable program code for causing the computer to prior to updating a storage block in non-volatile storage;

computer readable program code for causing the computer to

(i) protecting in a protection buffer in volatile memory data related to said storage block which is required for updating said storage block or for updating any storage block later in said update sequence; and

computer readable program code for causing the computer to (ii) and writing said data related to said storage block which is required for updating said corresponding storage block or for updating any storage block later in said update sequence, or writing a function thereof, to non-volatile storage;

computer readable program code for causing the computer to wherein after using any of said data to update in volatile memory content corresponding to said storage block or corresponding to said any storage block later in said update sequence, said used data is replaced in said protection buffer by other data.

79. A computer program product comprising a computer useable medium having computer readable program code embodied therein for generating an update package for in place updating original content of an original version stored in non-volatile storage with blocks to yield updated content of an updated version, the computer program product comprising:

computer readable program code for causing the computer to providing a protection buffer of equivalent size to a predetermined number of blocks; and

computer readable program code for causing the computer to prior to updating or simulating updating of content corresponding to a storage block, for each piece of data related to said corresponding storage block which is required for updating said corresponding storage block or for updating any storage block later in said update sequence performing the following;

if there is space available in said protection buffer, protecting or simulating protecting of said piece of data, but if there is no available space inserting said piece of data in said update package.