OPERATING SYSTEM AUTO-UPDATE PROCEDURE

• US 20110173601A1
• Filed: 01/11/2011
• Published: 07/14/2011
• Est. Priority Date: 01/12/2010
• Status: Abandoned Application

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: de los Reyes, Andrew
• Application Number:
  US13/004,426
• Publication Number:
  US 20110173601A1
• Time in Patent Office: Days
• US Class Current: 717/169
• CPC Class Codes: G06F 8/65 Updates security arrangements therefor G06F21/57
• 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

Abstract

The present invention pertains to differential updating of an operating system in a client device. A delta update file includes an ordered list of operations to be performed on the new install partition in memory that will port from the old install partition. A binary differential compression algorithm may be used to determine differences for the update and to compress the data being transmitted to the client device. Blocks in the partition may cyclically depend from one another. Edges are cut to break cycles. During system operation, disk images are scanned. File operations are created and a blocks vector is developed. A graph is created where the edge weights are set equal to the number of blocks. Given this, cycles are then broken and a final order resulting from a topological sort is produced.

Claims

1. A method of generating an update for a computer readable operating system, the method comprising:

identifying a version number of a current version of the operating system;

creating, with a processor, an ordered list of operations for updating the current version of the operating system to a new version of the operating system, the processor performing iterations over each regular file on the new version of the operating system to obtain the ordered list for all data blocks associated with the new version; and

assembling, with the processor, a differential update file including a magic number indicator showing the differential update file is an actual update file, a new version number identifying the new version of the operating system, and a protocol buffer including the ordered list of operations.

2. The method of claim 1, wherein one or more operations in the ordered list are each associated with a respective data blob indicating a chunk of data, and wherein the differential update file is assembled to include the respective data blobs.

3. The method of claim 1, wherein each operation in the ordered list is applicable to one or more specific data blocks of a partition of a client device, the operations including one or more of:

a copy operation where at least one of the data blocks in the partition is to be copied to another block in a new partition of the client device for the new version of the operating system;

a difference operation where at least a given one of the data blocks is read into memory and a difference routine is performing on the at least one given data block using a data blob of the differential update file;

a replace operation where a selected data blob of the differential update file is configured to be written to specified blocks in the new partition; and

a replace with uncompression operation where a compressed data blob is included in the differential update file and is configured to be written to selected specified blocks in the new partition for the new version of the operating system.

4. The method of claim 1, wherein each operation in the ordered list is associated with a file object, and the method further comprises:

creating a vertex in a graph for each file object; and

creating a vector representing each block.

5. The method of claim 4, further comprising:

setting reader and writer parameters for the vector of each block; and

for each block with a different reader and writer, creating an edge in the graph from the writer to the reader, the edge pointing to a file operation to be completed before a source file operation associated with the edge starts.

6. The method of claim 5, wherein each edge has a weight, and the weight identifies a number of blocks in the graph associated with that edge.

7. The method of claim 5, wherein if the graph includes cycles, the method further comprises breaking each of the cycles.

8. The method of claim 7, wherein breaking a given one of the cycles includes:

finding a lowest-weight edge associated with the given cycle; and

cutting the lowest-weight edge.

9. The method of claim 8, wherein cutting the lowest-weight edge comprises:

creating a new node representing an operation of copying an extent to a scratch space; and

making the lowest-weight edge'"'"'s source node point to the new node.

10. The method of claim 9, wherein a new edge is made from a destination node of the lowest-weight edge in order to ensure that a new copy operation occurs before a consumer of the new copy operation.

11. A device for generating an update for a computer readable operating system, the device comprising:

memory for storing differential update information associated with the operating system; and

a processor coupled to the memory, the processor being configured to;

identify a version number of a current version of the operating system;

create, using the differential update information, an ordered list of operations for updating the current version of the operating system to a new version of the operating system, including performing iterations over each regular file on the new version of the operating system to obtain the ordered list for all data blocks associated with the new version;

assemble a differential update file including a magic number indicator showing the differential update file is an actual update file, a new version number identifying the new version of the operating system, and a protocol buffer including the ordered list of operations; and

store the differential update file in the memory.

12. The device of claim 11, wherein each operation in the ordered list is associated with a file object, and the processor is further configured to:

create a vertex in a graph for each file object; and

create a vector representing each block.

13. The device of claim 12, wherein the processor is further configured to:

set reader and writer parameters for the vector of each block; and

for each block with a different reader and writer, create an edge in the graph from the writer to the reader, the edge pointing to a file operation to be completed before a source file operation associated with the edge starts.

14. The device of claim 13, wherein if the graph includes cycles, the processor is further operable to break each of the cycles.

15. The device of claim 14, wherein breaking a given one of the cycles includes:

finding a lowest-weight edge associated with the given cycle; and

cutting the lowest-weight edge.

16. The device of claim 15, wherein the processor is operable to cut the lowest-weight edge by:

creating a new node representing an operation of copying an extent to a scratch space; and

making the lowest-weight edge'"'"'s source node point to the new node.

17. The device of claim 16, wherein a new edge is made from a destination node of the lowest-weight edge in order to ensure that a new copy operation occurs before a consumer of the new copy operation.

18. A tangible computer-readable storage medium on which computer readable instructions of a computer program are stored, the instructions, when executed by a computer, cause the computer to perform a method of generating an update for a computer readable operating system, the method comprising:

identifying a version number of a current version of the operating system;

creating, with a processor, an ordered list of operations for updating the current version of the operating system to a new version of the operating system, the processor performing iterations over each regular file on the new version of the operating system to obtain the ordered list for all data blocks associated with the new version; and

assembling, with the processor, a differential update file including a magic number indicator showing the differential update file is an actual update file, a new version number identifying the new version of the operating system, and a protocol buffer including the ordered list of operations.

19. The storage medium of claim 18, wherein each operation in the ordered list is associated with a file object, and the method further comprises:

creating a vertex in a graph for each file object; and

creating a vector representing each block.

20. The storage medium of claim 19, wherein the method further comprises:

setting reader and writer parameters for the vector of each block; and

for each block with a different reader and writer, creating an edge in the graph from the writer to the reader, the edge pointing to a file operation to be completed before a source file operation associated with the edge starts.

21. The storage medium of claim 20, wherein if the graph includes cycles, the method further comprises breaking each of the cycles by:

finding a lowest-weight edge associated with each given cycle; and

cutting the lowest-weight edge for each cycle.

22. The storage medium of claim 21, wherein cutting the lowest-weight edge comprises:

creating a new node representing an operation of copying an extent to a scratch space; and

making the lowest-weight edge'"'"'s source node point to the new node.

23. The storage medium of claim 22, wherein a new edge is made from a destination node of the lowest-weight edge in order to ensure that a new copy operation occurs before a consumer of the new copy operation.

24. A client device, comprising:

memory for storing a current version of an operating system; and

a processor coupled to the memory, the processor being configured to;

transmit a request to a remote device regarding an update for the current version of the operating system, the request including a version number identifying the current version of the operating system;

receive a differential update file from the remote device, the differential update file including a magic number indicator showing the differential update file is an actual update file, a new version number identifying the new version of the operating system, and a protocol buffer including an ordered list of operations;

verify the magic number;

extract the ordered list of operations from the protocol buffer; and

perform a differential update by executing the ordered list of operations in order to update the current version of the operating system to the new version of the operating system.

25. The client device of claim 24, wherein the processor is operable to perform the differential update of the operating system to the new version of the operating system without saving the differential update file in the memory while the differential update file is being streamed to the client device.