Method and system for in-place updating content stored in a storage device

• US 9,043,680 B2
• Filed: 01/13/2008
• Issued: 05/26/2015
• 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
• Primary Examiner(s): Knapp, Justin R
• Application Number:
  US11/997,134
• Publication Number:
  US 20100185921A1
• Time in Patent Office: 2,690 Days
• Field of Search: None
• US Class Current: 714/769
• 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 of an original version stored in storage blocks of a non-volatile storage to yield updated content of an updated version, according to an update sequence for updating content in said blocks, wherein the non-volatile storage does not store the updated version in addition to the original version, 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 in-place updating the original content, wherein a part of said data is recoverable 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, in-place updating the original content by writing the updated content to the non-volatile storage in place of the original content,

wherein the data includes a single version of content.

2. The method of claim 1, wherein the single version of content includes one of original content, updated content, original content requiring protection and updated content requiring protection.

3. The method of claim 2, wherein at least one operand of said first error recovery function is the data.

4. The method of claim 2, wherein at least one operand of said first error recovery function is the data, and wherein when the data includes content that requires protection, said content is stored in one or more storage blocks.

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 functions.

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.

8. The method of claim 1, wherein obtaining includes one of (i) receiving the error recovery result from an external source and (ii) calculating the error recovery result by applying the first error recovery function.

9. The method of claim 1, further comprising writing said error recovery result into non-volatile memory, wherein at least one operand of said first function includes one of (i) original content, (ii) updated content and (iii) content that requires protection.

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

11. The method of claim 1, wherein (i) the recoverable data includes non-reliable content that is a result of an interrupted in-place update of content stored in the storage blocks of the non-volatile storage, and (ii) one of the blocks stores the non-reliable content and each one of the other blocks stores one of original content and updated content, and

wherein said non-reliable content of said recoverable data is recoverable by applying the second error recovery function to said error recovery result and to the other part of said data, said other part of said data including one of (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.

12. The method of claim 1, further comprising storing said error recovery result in the non-volatile storage prior to writing the updated content to the non-volatile storage in place of the original content.

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

14. The method of claim 1 further comprising:

protecting, according to the update sequence, 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.

15. The method of claim 14, further comprising:

providing a predetermined number of blocks in non-volatile storage for storing said error recovery result

wherein each protection buffer instance is equivalent in size to said predetermined number of blocks and corresponding to at least one sequential block in an update sequence,

wherein no two instances correspond to the same block in the update sequence,

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, and

wherein at least one operand in each said first and second error recovery functions includes at least part of a protection buffer instance; and

writing said error recovery result to said predetermined number of blocks prior to writing updated content to the non-volatile storage in place of original content.

16. The method of claim 1, further comprising:

protecting original content in at least one instance of a protection buffer in volatile memory, wherein said data includes at least one protection buffer instance; and

storing said error recovery result in a number of blocks in said non-volatile storage equivalent to a number of blocks in one protection buffer instance.

17. The method of claim 16, further comprising:

retrieving said stored error 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 at least one protection buffer instances using original or updated content from non-volatile storage except for one protection buffer instance which cannot be rebuilt based on said original or updated content,

wherein said recoverable part of said data includes said protection buffer instance which cannot be rebuilt, and

wherein said another part of said data includes at least one rebuilt protection buffer instance; and

wherein said updating of content includes using said recovered protection buffer instance.

18. The method of claim 1, wherein said recoverable part of said data includes updated content corresponding to a block in said non-volatile storage and wherein another part of said data includes updated content associated with at least one other block.

19. The method of claim 1, wherein said recoverable part of said data includes original content corresponding to a block in said storage and wherein another part of said data includes original content original associated with at least one other block.

20. The method according to claim 1, further comprising protecting, in a protection buffer in volatile memory, any part of said data that is related to a storage block and which is required for updating said storage block or for updating any storage block later in said update sequence.

21. The method of claim 20, wherein said any part of 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 at least one of original content from a corresponding storage block and data to facilitate locating the original content in the protection buffer.

22. An apparatus for reliably in-place updating original content of an original version stored in storage blocks of a non-volatile storage to yield updated content of an updated version, wherein the non-volatile storage does not store the updated version in addition to the original version, the apparatus 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 in-place updating the original content, wherein a part of said data is recoverable 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 in-place updating the original content by storing the updated content to the non-volatile storage in place of the original content,

wherein the data includes a single version of content.

23. The apparatus of claim 22, wherein the error recovery result obtaining unit is coupled to a calculator configured to calculate the error recovery result, by performing the first error recovery function.

24. The apparatus of claim 22, wherein (i) the recoverable data includes non-reliable content stored in at least one of the storage blocks and is a result of an interrupted in-place update of content stored in the storage blocks of the non-volatile storage, (ii) and one of the blocks stores the non-reliable content and each one of other blocks stores one of the original content and (ii) the updated content, the apparatus further comprising:

a recovery processor responsive to said error recovery result for recovering said non-reliable content of said recoverable data by applying the second error recovery function to said error recovery result and to the other part of said data, wherein the other part of said data includes one of (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.

25. 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, according to an update sequence, wherein the non-volatile storage does not store the updated version in addition to the original version, the method comprising:

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

prior to in-place updating or simulating in-place updating of content stored in a storage block, for each segment of said storage block that (i) relates to a corresponding storage block and (ii) is required for updating said corresponding storage block or for updating any storage block later in said update sequence, when there is space available in said protection buffer, protecting or simulating protecting of said each segment, and when there is no available space, inserting said each segment in said update package,

wherein after each of said protected or simulated to be protected segments has been used to update or simulate update of content of said corresponding storage block or to update content of said any storage block later in said update sequence, each of said used segments is marked as available for erasure and reuse in said protection buffer by other data,

wherein said each segment includes a single version of content.

26. A non-transitory computer readable storage medium that stores a program of instructions that causes a computer to perform steps for reliably in-place updating original content of an original version stored in storage blocks of a non-volatile storage to yield updated content of an updated version, wherein the non-volatile storage does not store the updated version in addition to the original version, the steps comprising:

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

after obtaining the error recovery result, in-place updating the original content by writing the updated content to the non-volatile storage in place of the original content,

wherein the data includes a single version of content.

27. The non-transitory computer readable storage medium of claim 26,

wherein the obtaining includes calculating the error recovery result by applying the first error recovery function to data which is used in updating the original content,

wherein at least one operand of said first error recovery function includes one of the following:

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

wherein said program of instructions stored on the non-transitory computer readable storage medium further causes the computer to write said error recovery result into the non-volatile storage.

28. The non-transitory computer readable storage medium of claim 26, wherein (i) the recoverable data includes non-reliable content that is a result of an interrupted in-place update of content stored in storage blocks of the non-volatile storage and (ii) one of the blocks stores the non-reliable content and each one of the other blocks stores one of original content and updated content, and

wherein said non-reliable content of said recoverable data is recoverable by applying the second error recovery function to said error recovery result and to the other part of said data, the other part of said data including one of (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.

29. The non-transitory computer readable storage medium of claim 26, wherein:

said program of instructions stored on the non-transitory computer readable storage medium further causes the computer to store said error recovery result in the non-volatile storage prior to writing the updated content to the non-volatile storage in place of the original content.

30. A method for reliably in-place updating original content of an original version stored in a non-volatile storage to yield updated content of an updated version, wherein the non-volatile storage does not store the updated version in addition to the original version, the method comprising:

a. prior to the in-place updating original content, obtaining an error recovery result achievable by applying at least one first error recovery function to data which is designated to be used in updating the original content,

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

wherein said error recovery result is usable for recovering a part of said data which becomes non-reliable resulting an interrupted in-place update, said recovery to be provided by applying at least one second error recovery function to (i) said error recovery result and (ii) to a reliable part of said data and/or derivatives thereof,

wherein the data includes a single version of content.

31. The method of claim 30, the updated version being stored in 1 storage blocks, where content stored in n out of the 1 storage blocks is updated, where n≦

1, comprising;

(a) obtaining an update package;

(b) reliably in-place updating the original content while performing no more than n+k storage operations, where k is a selectable predetermined number and k<

n.

32. The method of claim 31 applied for recovering non-reliable content that is a result of an interrupted in-place update of content stored in storage blocks of the non-volatile storage, wherein

(a) one of the blocks stores non-reliable content and each one of the other blocks stores original content or updated content, and

(b) recovering said non-reliable content is provided by applying said second error recovery function to said error recovery result and to data and/or deviations thereof corresponding to the content stored in the other blocks.

33. The method of claim 30, wherein said single version of content corresponds to the original content or part thereof.

34. The method of claim 30, wherein said single version of content corresponds to the updated content or part thereof.

35. The method of claim 30, wherein said single version of content corresponds to one of an original content desired to be protected and an updated content desired to be protected.

36. The method of claim 30 wherein the first error recovery function and the second error recovery function are identical.

37. The method of claim 30 wherein the first error recovery function and the second error recovery function are XOR functions.

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

39. The method of claim 30, wherein obtaining includes receiving the error recovery result from an external source.

40. The method of claim 39, wherein the error recovery result is generated during generation of an update package which is usable for reliably in-place updating the original content to yield the updated content.

41. The method of claim 30, wherein obtaining includes writing said error recovery result into the non-volatile storage.

42. An apparatus for reliably in-place updating original content of an original version stored in storage blocks of a non-volatile storage to yield updated content of an updated version, wherein the non-volatile storage does not store the updated version in addition to the original version, the apparatus comprising:

a) an error recovery result obtaining unit for obtaining an error recovery result achievable by applying at least one first error recovery function to data which are designated to be used in in-place updating the original content, wherein said error recovery result is usable for recovering a part of said data which become non-reliable resulting an interrupted in-place update, said recovery to be provided by applying at least one second error recovery function to (i) said error recovery result and (ii) a reliable part of said data and/or derivatives thereof; and

wherein said unit is configured to obtain said error recovery result prior to a start of the updating process; and

b) an updating processor responsive to said error recovery result for in-place updating the original content by storing the updated content to the non-volatile storage in place of the original content,

wherein the data includes a single version of content.

43. The apparatus of claim 42, wherein the error recovery result obtaining unit is coupled to a calculator configured to calculate the error recovery result, by performing the first error recovery function.

44. The apparatus of claim 42, wherein the error recovery function is an XOR function.

45. The apparatus of claim 42 configured for recovering non-reliable content that is a result of an interrupted in-place update of content stored in the storage blocks of the non-volatile storage, wherein one of the blocks stores the non-reliable content and each one of other blocks stores original content or updated content, the apparatus further comprising:

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 data and/or derivatives thereof corresponding to said content stored in the other blocks.

46. A non-transitory computer-readable medium in which a computer program is recorded, said computer program comprising computer program code means able to be executed by a computer to perform steps for reliably in-place updating original content of an original version stored in a non-volatile storage to yield updated content of an updated version, wherein the non-volatile storage does not store the updated version in addition to the original version, the computer program causing the computer to execute the steps of:

(a) prior to an in-place updating of original content stored in the non-volatile storage, obtaining an error recovery result achievable by applying at least one first error recovery function to data, which includes a single version of content and which is designated to be used in updating the original content,

(b) after obtaining the error recovery result, in-place updating the original content by storing updated content to the non-volatile storage in place of the original content,

wherein said error recovery result is usable for recovering a part of said data which becomes non-reliable resulting an interrupted in-place update, said recovery to be provided by applying at least one second error recovery function to (i) said error recovery result and (ii) to a reliable part of said data and/or derivatives thereof, and

wherein the updated version is stored in 1 storage blocks, where content stored in n out of the 1 storage blocks is updated, where n≦

1, and the method further comprises

(c) obtaining an update package; and

(d) reliably in-place updating the original content while performing no more than n+k storage operations, where k is a selectable predetermined number and k<

n.