Systems and methods for incrementally updating an image in flash memory

• US 20020034105A1
• Filed: 01/08/2001
• Published: 03/21/2002
• Est. Priority Date: 05/03/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kulkarni, Harish, Fleming, Michael K., Fuller, Jason W.
• Granted Patent: US 6,775,423 B2
• Time in Patent Office: Days
• US Class Current: 365/200
• 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: G11C 16/102 External programming circuits, e.g. EPROM programmers; In-circuit programming or reprogramming; EPROM emulators
• CPC Class Codes: G11C 16/105 Circuits or methods for updating contents of nonvolatile memory, especially with 'security' features to ensure reliable replacement, i.e. preventing that old data is lost before new data is reliably written
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

Systems and methods for incrementally updating a first image in flash memory of a device by downloading a differences file that identifies differences between the first image and a second image and applying the differences file to the first image to create the second image in the flash memory. The updating is performed incrementally by writing portions of the second image to the flash memory, each portion being of a standard block size acceptable for writing to the flash memory.

Claims

1. A method, comprising:

creating a differences file from a first image and a second image, the second image including data sections from the first image and new data sections, the differences file including pointers to the data sections of the first image that are included in the second image and the new data sections from the second image;

identifying dependent data sections that require data from one or more referenced data sections; and

reordering the data sections and pointers so that no dependent data section requires data from a referenced data section that precedes it in the order.

2. The method as recited in claim 1, further comprising creating a modified differences file that contains the ordered data sections and pointers.

3. The method as recited in claim 1, further comprising writing the referenced data sections and the new data sections to memory according to the reordering to produce the second image in memory from the first image and the differences file.

4. The method as recited in claim 3, wherein the data sections are written to memory in blocks of a predefined size of memory.

5. The method as recited in claim 3, the second image overwriting the first image in the memory.

6. The method as recited in claim 1, the reordering further comprising:

identifying cyclic references between referenced data sections; and

breaking one or more references in the cyclic references so that there are no cyclic references between referenced data sections.

7. The method as recited in claim 6, wherein the breaking one or more references further comprises breaking one or more references that reference the smallest amounts of data to remove the cyclic references.

8. The method as recited in claim 1, the reordering further comprising:

creating a directed graph of nodes and edges wherein each node corresponds to a referenced data section in the first image and each edge being indicative of a section taking data from another section;

assigning a weight to each edge to create a weighted directed graph, the weight of an edge being the amount of data taken by one node connected to the edge from the other node connected to the edge;

determining the smallest set of edges that, when deleted, results in a weighted directed acyclic graph;

deleting at least one edge in the determined smallest set of edges; and

topologically sorting the weighted directed acyclic graph.

9. The method as recited in claim 8, wherein deleting an edge comprises replacing a reference to a data section in the differences file with the data section.

10. A method for overwriting an old image in flash memory with a new image, the new image containing data sections from the old image and new data sections, the method comprising:

accessing a differences file that contains references to data sections from the old image that are included in the new image, and the new data sections from the new image;

identifying dependent data sections as being data sections that require data from one or more referenced data sections;

ordering the references to data sections from the old image and the new data sections so that a dependent data section precedes the one or more referenced data sections from which it requires data; and

writing the new image in flash memory according to the ordering, the new data sections being copied from the differences file and the referenced data sections being copied from the old image.

11. The method as recited in claim 10, further comprising creating a modified differences file that contains the ordered references and data sections.

12. The method as recited in claim 10, the ordering further comprising:

creating directed graph of nodes and edges wherein each node corresponds to a referenced data section in the old image, and each edge indicating that a first node connected to a first end of an edge takes data from a second node connected to a second end of the edge;

creating a weighted directed graph from the directed graph by assigning a weight to each edge, the weight of an edge being an amount of data taken by the first node from the second node;

determining a smallest set of edges that can be deleted to derive a weighted directed acyclic graph;

deleting the set of edges; and

performing a topological sort on the weighted directed acyclic graph.

13. The method as recited in claim 10, the ordering further comprising:

identifying cyclic references between referenced data sections; and

converting the cyclic references to acyclic references by breaking one or more references within each cyclic reference.

14. The method as recited in claim 13, wherein the breaking one or more references further comprises breaking one or more references that reference the smallest amounts of data possible to remove the cyclic references.

15. The method as recited in claim 10, further comprising creating the difference file.

16. The method as recited in claim 10, further comprising receiving the difference file from a computing device.

18. The computer readable medium as recited in claim 17, further comprising computer-executable instructions that, when executed on a computer, perform the step of creating a modified differences file containing the data sections and references of the differences file in the order derived by the reordering.

19. The computer readable medium as recited in claim 17, further comprising computer-executable instructions that, when executed on a computer, perform the step of writing the referenced data sections and the new data sections to memory in the order derived by the reordering to store the second image in the memory.

20. The computer readable medium as recited in claim 19, wherein the new data sections are copied into the memory from the differences file, and the data sections in the first image that are referenced by the differences file are copied into the memory from the first image.

21. The computer readable medium as recited in claim 19, wherein the memory is flash memory that accepts write data in blocks having a minimum size, and the computer readable medium further comprises computer-executable instructions that, when executed on a computer, perform the following:

incrementally constructing the second image in random access memory until there is a portion of the second image that is the minimum size to be written to the flash memory;

writing the portion of the second image to the flash memory; and

writing a remainder of the second image to the flash memory when data sections remaining to be written are insufficient to make up a block of the minimum size.

22. The computer readable medium as recited in claim 19, wherein the referenced data sections and the new data sections are written to a memory location where the first image is stored, overwriting the first image.

23. The computer readable medium as recited in claim 17, further comprising computer-executable instructions that, when executed on a computer, perform the step of creating a modified differences file to store the reordered new data sections and references to data sections from the old image.

24. The computer readable medium as recited in claim 17, further comprising computer-executable instructions that, when executed on a computer, perform the steps of:

identifying cyclic references between referenced data sections; and

breaking one or more references in the cyclic references so that there are no cyclic references between referenced data sections.

25. The method as recited in claim 24, wherein the breaking one or more references further comprises breaking one or more references that reference the smallest amounts of data to remove the cyclic references.

26. The computer readable medium as recited in claim 17, further comprising computer-executable instructions that, when executed on a computer, perform the steps of:

creating a representation of a directed graph of nodes and edges wherein each node corresponds to a referenced data section in the first image and each edge being indicative of a section taking data from another section;

assigning a weight to each edge to create a representation of a weighted directed graph, the weight of an edge being the amount of data taken by a receiving node connected to a receiving end of the edge from a taking node connected to a taking end of the edge;

determining the smallest set of edges that, when deleted, results in a representation of a weighted directed acyclic graph; and

topologically sorting the representation of the weighted directed acyclic graph.

28. A system as recited in claim 27, further comprising a reference substitution module that is configured to:

identify cyclic references between referenced data sections;

remove one or more references in each cyclic reference to eliminate the cyclic references; and

wherein a reference is removed by substituting a data section for a reference to the data section in the differences file.

17. A computer readable medium containing computer-executable instructions that, when executed by a computer, perform the following:

accessing a differences file that contains references to data sections from a first image that are included in a second image, and new data sections that are included in the second image;

identifying dependent data sections that require data from one or more referenced data sections in the first image; and

reordering the references to data sections from the first image and the new data sections so that each dependent data section precedes the one or more referenced data sections from which it requires data.

27. A system, comprising:

a processor;

memory;

an image stored in the memory and containing data sections;

an updated image stored in the memory, containing one or more data sections from the image and new data sections;

a compression module configured to create a differences file, the differences file including the new data sections of the updated image and references to the data sections in the image that are also contained in the updated image; and

an ordering module configured to reorder the references and new data sections in the differences file and store the reordered references and new data sections in a modified differences file so that any data section requiring data from one or more referenced data sections comes before the one or more referenced data sections.

29. An incremental dial-up bootloader, comprising:

a dial-up bootloader operating system, configure to download a differences file;

an incremental module configured to apply the differences file to a first image to produce a second image that is an updated version of the first image; and

a flash manager to create the second image incrementally until a portion of the second image is of a standard size to write to the flash memory and to write portions of the second image to the flash memory until the second image is stored in the flash memory.