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

• US 20080172584A1
• Filed: 01/11/2007
• Published: 07/17/2008
• Est. Priority Date: 01/11/2007
• Status: Abandoned Application

• Current Assignee: Red Bend Limited (Samsung Electronics Co. Ltd.)
• Original Assignee: Red Bend Limited (Samsung Electronics Co. Ltd.)
• Inventors: Meller, Evyatar, Peleg, Sharon
• Application Number:
  US11/652,147
• Publication Number:
  US 20080172584A1
• Time in Patent Office: Days
• US Class Current: 714/702
• 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 of an original version stored in a non-volatile storage device and for yielding updated content of an updated version. 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 storage 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 buffer protecting content which is required in the update process.

Claims

1. 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:

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.

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

3. The method of claim 1, 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.

4. The method of claim 1, wherein said data includes at least some of said original content.

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

6. The method of claim 5, wherein said predetermined number is 1.

7. The method of claim 1, 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.

8. The method of claim 1, 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.

9. The method of claim 8, 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.

10. The method of claim 1, 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.

11. The method of claim 10, 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.

12. The method of claim 10, 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.

13. The method of claim 10, 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.

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

15. The method of claim 14, 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.

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

17. The method of claim 16, 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.

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

19. The method of claim 18, 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.

20. The method of claim 19, 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.

21. The method of claim 18, 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.

22. The method of claim 21, wherein said subgroup is a XOR function.

23. The method of claim 21, 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.

24. The method of claim 18, 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.

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

26. 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 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;

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. 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 provide a predetermined number of blocks in non-volatile storage for storing a XOR result;

computer readable program code for causing the computer to protect 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 write 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.

28. 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 provide 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 write said XOR result to said provided block prior to writing updated content from volatile memory to non-volatile storage in place of original content.

29. 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 protect in a protection buffer in volatile memory data related to a storage block which is required for updating said storage block or for updating any storage block later in said update sequence, prior to updating said storage block in non-volatile storage;

computer readable program code for causing the computer to write 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, prior to updating said storage block in non-volatile storage; and

computer readable program code for causing the computer, 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, to replace in said protection buffer said used data by other data.

30. 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 provide a protection buffer of equivalent size to a predetermined number of blocks;

computer readable program code for causing the computer to perform the following;

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

computer readable program code for causing the computer, 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, to replace or simulate replacement in said protection buffer of said used piece of data by other data.