Efficient system and method for updating a memory device

• US 8,200,886 B2
• Filed: 01/16/2007
• Issued: 06/12/2012
• Est. Priority Date: 09/30/2002
• Status: Active Grant

• Current Assignee: Smith Micro Software Incorporated
• Original Assignee: Smith Micro Software Incorporated
• Inventors: Ogle, Andrew J.
• Primary Examiner(s): KROFCHECK, MICHAEL C
• Application Number:
  US11/654,221
• Publication Number:
  US 20070192532A1
• Time in Patent Office: 1,974 Days
• Field of Search: 711/161, 711/162, 711/154, 711/156, 717/168
• US Class Current: 711/103
• CPC Class Codes: G06F 8/654 using techniques specially adapted for alterable solid state memories, e.g. for EEPROM or flash memories
• CPC Class Codes: G06F 8/658 Incremental updates; Differential updates
• CPC Class Codes: G06F 9/3001 Arithmetic instructions
• CPC Class Codes: G06F 9/30032 Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

A system and method for updating a binary image stored across a block-structured memory device, such as a flash memory device. From comparison of original and new images, an update package is generated which includes an encoded instruction set comprising COPY and ADD operations instructing the copying of source data from locations in the memory device and adding other data provided in the update package. The instruction set comprises SETBLOCK operations that direct updating of the memory blocks in an order that optimizes the COPY and ADD operations required and resulting update package size. The instruction set further comprises SETCOPYOFFSET operations to toggle between copy-offset modes thereby allowing for improved efficient encoding of COPY operations. The update package further includes an array of status bits corresponding to the memory blocks to be updated, thereby allowing for reliable restarting of the update process following power loss or other interruption.

Claims

1. A method for providing an update package configured to update a first data image of a memory device to a second image, comprising:

creating an instruction set using a plurality of addition, copying, and SETBLOCK operations representing changes between the first data image and the second data image, said instruction set forming the update package, wherein creating the instruction set comprises;

splitting each addition operation and each copying operation into two operations whenever a destination region for an addition operation or a copying operation in the second data image would otherwise span a block boundary in the second data image, wherein said splitting divides each addition operation and each copying operation at an appropriate block boundary in the second data image;

using the second data image as a copying operation source for each copying operation seeking to copy data from a block processed before each currently processed memory block; and

employing a hashtable set comprising a first data image hashtable and a second data image hashtable, the hashtable set searchable to find a memory block update match in the first data image or second data image based on whether a location in the second image to be updated occurs before or after a start address of each currently processed memory block; and

communicating said update package to a client device containing said memory device.

2. The method of claim 1, wherein the update package contains a plurality of SETBLOCK, COPY and ADD operations and a status array for each of the memory blocks.

3. The method of claim 2, wherein the instruction set contains at least one SETBLOCK operation for each of the memory blocks to be updated.

4. The method of claim 2, wherein the instruction set is applied in an order specified by the SETBLOCK operation to non-sequentially update the memory blocks in said client device.

5. The method of claim 2, wherein said status array stores at least two switchable status identifiers associated with each memory block to be updated as instructed by the instruction set contained in the update package.

6. The method of claim 2, wherein the instruction set further comprises a plurality of COPYADD operations in lieu of at least a portion of the plurality of COPY operations.

7. The method of claim 1, further comprising:

maintaining a first copy-offset value and a second copy-offset value in scratch memory on said client device; and

setting the copy-offset value according to a plurality of COPYOFFSET values provided in the update package.

8. A system for updating a first data image on a client device, comprising:

an update generator that creates an instruction set using a plurality of addition, copying, and SETBLOCK operations for multiple memory blocks based on comparing the first data image and a second data image to create an update package, wherein a SETBLOCK operation identifies a next block to be updated using specified addition and copying operations;

wherein said update generator is configured to;

split each addition and each copying operation into two operations whenever a destination region for an addition operation or a copying operation in the second data image would otherwise span a block boundary in the second data image, wherein splitting divides each addition operation and each copying operation at an appropriate block boundary in the second data image;

use the second data image as a copying operation source for each copying operation seeking to copy data from a block processed before each currently processed memory block; and

employ a hashtable set comprising a first data image hashtable and a second data image hashtable, the hashtable set searchable to find a memory block update match in the first data image or second data image based on whether a location in the second image to be updated occurs before or after a start address of each currently processed memory block; and

provide the instruction set to an update decoder resident on the client device.

9. The system of claim 8, wherein the update package contains a plurality of SETBLOCK, COPY and ADD operations for each of the memory blocks.

10. The system of claim 8, further comprising a communications network and a host server that comprises the update generator, whereby the update package is delivered from the host server to the client device via the communications network.

11. The system of claim 8, wherein the instruction set contains at least one SETBLOCK operation for each of the memory blocks to be updated.

12. The system of claim 9, wherein the instruction set further comprises a plurality of COPYADD operations in lieu of at least a portion of the plurality of COPY operations.

13. The system of claim 8, further comprising:

maintaining a first copy-offset value and a second copy-offset value in scratch memory on said client device; and

setting the copy-offset value according to a plurality of COPYOFFSET values provided in the update package.

14. The system of claim 8, wherein the instruction set direct applying the update package to toggle a copy-offset value maintained in the client device between a current value and a non-current value.

15. A method for providing an update package for modifying functionality in a client device, comprising:

creating an instruction set in an update package using a plurality of addition, copying, and SETBLOCK operations for multiple memory blocks based on comparing a first data image and a second data image, wherein a SETBLOCK operation identifies a next block to be updated using specified addition and copying operations, wherein creating the instruction set comprises;

splitting each addition operation and each copying operation into two operations whenever a destination region for an addition operation or a copying operation in the second data image would otherwise span a block boundary in the second data image, wherein said splitting divides each addition operation and each copying operation at an appropriate block boundary in the second data image;

using the second data image as a copying operation source for each copying operation seeking to copy data from a block processed before each currently processed memory block; and

employing a hashtable set comprising a first data image hashtable and a second data image hashtable, the hashtable set searchable to find a memory block update match in the first data image or second data image based on whether a location in the second image to be updated occurs before or after a start address of each currently processed memory block; and

communicating said update package over-the-air to the client device.

16. The method of claim 15, wherein the instruction set contains at least one SETBLOCK operation for each of the memory blocks to be updated.

17. The method of claim 16, wherein the instruction set is applied in an order specified by the SETBLOCK operation to non-sequentially update the memory blocks in said client device.

18. The method of claim 15, wherein said specific memory blocks involve each memory block in a client device first data image.

19. The method of claim 15, wherein said status array stores at least two switchable status identifiers associated with each memory block to be updated as instructed by the instruction set contained in the update package.

20. The method of claim 15, wherein the instruction set further comprises a plurality of COPYADD operations in lieu of at least a portion of a plurality of COPY operations.