FAULT-TOLERANT METHOD AND APPARATUS FOR UPDATING COMPRESSED READ-ONLY FILE SYSTEMS

• US 20100325523A1
• Filed: 07/24/2009
• Published: 12/23/2010
• Est. Priority Date: 06/19/2009
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Wu, Zhao-Ming, McGhee, LaShawn, Slyz, Marko, Wen, Li
• Granted Patent: US 8,201,054 B2
• Time in Patent Office: Days
• US Class Current: 714/773
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 11/1433 during software upgrading
• CPC Class Codes: G06F 8/65 Updates security arrangements therefor G06F21/57

Abstract

A fault-tolerant approach for updating a compressed read-only file system in embedded devices using a two-step approach. In the first phase an update package creates an intermediate memory image where the data blocks are independently compressed so that, if needed, the data therein can be decompressed and read without access to any other surrounding data blocks. Then in the second phase the intermediate memory image is decompressed in a buffer so that it can be reimaged into its final form and order before being recompressed and written back to non-volatile memory over-writing the intermediate memory image.

Claims

1. A fault-tolerant method of updating an original data image having both compressed and raw data arranged into data sub-blocks and stored in a programmable non-volatile flash memory, wherein the flash memory is divided into discrete flash blocks with flash block boundaries, the method comprising:

a) decompressing each compressed data sub-block identified by predetermined updating instructions;

b) generating the decompression state for each decompressed data sub-block that crosses a flash block boundary, and copying to flash memory the generated decompression states for use in recovering data after a system failure;

c) creating an intermediate memory image in buffer memory by

i. applying predetermined updating instructions while retrieving and decompressing flash blocks of data identified by the predetermined updating instructions and creating an intermediate memory image consisting of a sequence of uncompressed data blocks, each corresponding to a single flash block;

ii. compressing the intermediate memory image so that the data in each flash block is compressed independently of the data in any other compressed flash block;

iii. over-writing the flash blocks in the original data image with the intermediate memory image;

d) creating an updated memory image that includes the desired update information by

i. copying portions of the intermediate memory image to a buffer and decompressing the data in each compressed flash block in the intermediate memory image;

ii. sequentially recompressing the decompressed intermediate memory image into discrete flash blocks thereby generating the updated compressed memory image; and

iii. overwriting the intermediate memory image in the flash memory with the updated compressed memory image.

2. The updating method according to claim 1, wherein step (c)(ii) further comprises:

limiting the amount of data associated with each discrete flash block in the intermediate memory image so that each independently compressed data flash block is no larger than the size of the corresponding data flash block in the original data image thereby creating overlap data for each compressed flash block; and

storing in flash memory the overlap data generated from the above step.

3. The updating method according to claim 2, where step (d)(i) further comprises:

selectively combining the overlap data with the decompressed intermediate memory image data to generate the updated memory image in uncompressed format.

4. The updating method according to claim 3 further comprising:

after step (c)(ii), calculating the parity block for all of the independently compressed data blocks and copying the parity block to the flash memory for use in recovering data after a system failure.

5. The method according to claim 3, wherein steps (c)(i), (c)(ii), and (c)(iii) further comprise:

e) applying predetermined updating instructions while retrieving and decompressing a first group of flash blocks of data identified by the predetermined updating instructions and creating a partial intermediate memory image in uncompressed format;

f) compressing the partial intermediate memory image so that the data for each flash block is compressed independently of the data in any other flash block;

g) over-writing the data flash blocks in the original data image with the partial intermediate memory image; and

h) repeating steps (e), (f), and (g) sequentially until all of the flash blocks of data identified by the predetermined updating instructions have been processed thereby creating the intermediate memory image.

6. The updating method according to claim 4 wherein the original data image comprises a read-only file system.

7. The updating method according to claim 4 wherein in the event of a power failure occurring while creating the intermediate memory image, upon restoration of power, performing the steps of:

locating the point of failure in the update process by comparing the checksums of each data flash block in the intermediate memory image stored in the flash memory to the checksums stored in the update package for each data flash block;

if all of the data flash blocks are in an unmodified state, continuing with all the remaining steps in the updating process beginning at step (c) (i);

if all of the data flash blocks in the original data image have been over-written with the intermediate memory image, continuing with all the remaining steps in the updating process beginning at step (d) (i);

if neither of the above steps is valid, performing the following steps to recover corrupted data and continue the updating process;

for that portion of the original data image that had not been updated before the power failure, applying the updating instructions while retrieving and decompressing flash blocks of data identified by the predetermined updating instructions and creating a portion of the intermediate memory image in uncompressed format;

recompressing that portion of the intermediate memory image from the prior step so that each data flash block is compressed independently of any other compressed data flash block;

copying to the buffer memory the remaining portion of the intermediate memory image from the flash memory that had been updated;

calculating the exclusive-OR of the parity block and all of the compressed data blocks from the prior two steps thereby generating the original data in the corrupted data block; and

continuing with each of the remaining steps in the updating process beginning at (c) (iii).

8. A mobile electronic device having an operating software system configured to have a completely fault-tolerant process for updating the operating system software, said electronic device comprising:

a buffer memory;

a computer-readable flash memory having stored therein said operating system software configured as a first memory image consisting of compressed and incompressible blocks of data, and divided into discrete flash blocks of data;

a processor programmed for updating the first memory image in accordance with predetermined updating instructions by;

decompressing each compressed data sub-block identified by the predetermined updating instructions;

generating the decompression state of each decompressed data sub-block which crosses a flash block boundary and copying to flash memory the generated decompression states for use in recovering data after a system failure;

creating an intermediate memory image in buffer memory by

applying the predetermined updating instructions while retrieving and decompressing flash blocks of data from the flash memory identified by the predetermined updating instructions and creating an intermediate memory image consisting of a sequence of uncompressed data blocks, each corresponding to a single flash block;

compressing the intermediate memory image so that the data corresponding to each flash block is compressed independently of the data in any other flash block, and limiting the amount of data in each discrete flash block in the intermediate memory image so that each independently compressed flash block fits within the corresponding flash block, and if it does not, saving the overlap data to flash memory;

over-writing the data in each flash block in the original data image with the intermediate memory image;

creating an updated memory image that includes the desired update information by

copying the intermediate memory image to the buffer and decompressing each compressed data sub-block in the intermediate memory image while using the overlap data stored in flash memory;

sequentially recompressing the decompressed intermediate memory image into a different sequence of data sub-blocks thereby generating the updated compressed memory image; and

overwriting the intermediate memory image in the flash memory with the updated compressed memory image.

9. The mobile electronic device according to claim 8, wherein said device further comprises a cellular phone.