Image analysis – Image transformation or preprocessing – Image storage or retrieval
Reexamination Certificate
2001-01-08
2004-08-10
Patel, Kanji (Department: 2625)
Image analysis
Image transformation or preprocessing
Image storage or retrieval
C717S168000, C707S793000, C709S246000, C711S100000
Reexamination Certificate
active
06775423
ABSTRACT:
TECHNICAL FIELD
This invention relates to incrementally updating an image in flash memory and, more particularly, to a dial-up bootloader for remotely updating an operating system image in flash memory of an electronic device.
BACKGROUND
Computer electronic devices, such as a set-top box or a hand-held computer, utilize flash memory to store computer programs, e.g., operating systems and applications. Flash memory is semiconductor memory that can operate as ROM (read only memory) but, on an activating signal, can rewrite its contents as though it were random access memory (RAM). Flash memory is the industry standard for non-volatile storage in embedded applications.
Operating systems and applications are stored in flash memory as execute-in-place (XIP) images. Execute-in-place functionality is the ability to run an application directly from flash memory, instead of copying the application into RAM and running it from there. This functionality preserves system resources.
Although the XIP image format is efficient for execution purposes, it is not a file system and was not designed to be modified. Therefore, making a change to an XIP image is an overhead-intensive process that requires constructing a completely new image, downloading the new image to random access memory of the electronic device, and reprogramming the flash memory of the device.
One application that is utilized by electronic devices is a dial-up bootloader. A dial-up bootloader is a mechanism to update an image on a device—including a device operating system—by booting into a dial-up bootloader (DUB) operating system that is smaller than the device operating system. The DUB operating system contains the necessary information to dial into a server, download a latest version of the device operating system, and update the operating system on the device. In the case of a dial-up bootloader, the entire device operating system is downloaded.
The image is usually downloaded over a modem. If the size of the image is significant, i.e., several megabytes, this process can take up to an hour to complete. This is an unacceptably long time for a customer to wait, especially when the change to the image is actually quite minor, such as a minor bug fix.
A compression technique that utilized a differences file may be used to reduce the size of data transmitted to update an image. A differences file represents a new image in terms of an old image, plus new data. Any part of the new image that also exists in the old image is represented as a reference to the original data. This representation is efficient because the reference is much smaller than the original data itself. As a result, the differences file is typically much smaller than the new image. Download time is, therefore, significantly reduced.
The differences file contains a series of copy and data sections. A copy section is a section in the original image that has not changed in the updated image. A copy section indicates that a portion of the new image can be found in the old image at the address given in the copy section. A data section consists of a portion of the new image that is not found in the old image.
As an old image is updated, portions of the old image are overwritten with portions of the new image. Because later copy sections may refer to and use sections in the old image that have already be overwritten, the new image cannot simply be written in sequential order over the old image. Methods using a differences file, therefore, have traditionally created the new image in RAM—drawing data from the old image in flash memory and the new image at the server—before transferring the image from the RAM to the flash memory. When dealing with compact electronic devices, a desirable solution will not utilize such a large amount of RAM, since device RAM is modest so as to conform to the compact, low-cost objective of the compact device.
Therefore, one problem overcome by the implementations described herein is reducing the number of sections transmitted while, at the same time, preserving image sections that are used to construct other image sections.
Another problem arises because flash memory can only be written in a predefined block size (a write to flash memory is defined by a block address and block size). If an entire block of flash memory is written before later sections are written that depend on the overwritten block of memory, then the later sections cannot be constructed. Therefore, the block of flash memory must be written so that it does not overwrite data sections on which later sections depend.
SUMMARY
The implementations described herein create and utilize a differences file to create a new image in flash memory of an electronic device from sections of an old image in the flash memory and sections of a new image, the new image being an updated version of the old image. The new image is created incrementally in flash memory so that an entire image does not have to first be constructed in device RAM, thereby saving significant overhead. A “flash manager” is described which allows the new image to be built incrementally until a memory block is created that is of sufficient size to be written to the flash memory.
For example, if the flash memory has a block size of 64 Kb and the image to be written is 10 Mb, then the flash manager will create one or more memory blocks in RAM as it constructs the new image. Each RAM memory block corresponds to one flash memory block. When at least one-half of the RAM memory block (32 Mb) is filled with data, then the memory block is written to the flash memory. The flash manager continues to create memory blocks of the image in RAM as necessary, and writes a memory block to the flash memory whenever it is at least half full. Because the new image is not constructed sequentially, i.e., the first block of the new image is not necessarily constructed first, the memory blocks are not written sequentially. The writing process continues until the entire 10 Mb image is stored in the flash memory. This procedure requires much less than the 10 Mb of RAM that would normally be required if the entire image was created in RAM before being written to the flash memory.
The size of a block that may be written to flash memory depends upon the particular type of flash memory. Some flash memory has a 32 Kb write block size, while other flash memory may accept write blocks of 64 Kb or more. Therefore, the flash manager is configured so that the block size is variable and can be changed to suit the write block size of any particular type of flash memory.
In addition to the code that runs on the device itself, the incremental dial-up bootloader includes two tools that execute on a personal computer from which the new image is downloaded. A first program is a compression program responsible for generating the differences file. A second program takes the differences file and reorders the sections to allow the flash memory to be reprogrammed without first having to reconstruct the complete new image in RAM before programming it to flash memory.
To accomplish this, the second program must identify dependent sections that require data from other sections and order the sections so that a dependent section is written before the sections from which it requires data. This is because the new image is incrementally written over the old image and, if the sections from which data is taken are written first, the dependent sections will not be able to access the data required to build the dependent sections.
A solution is also described in the case where dependent sections require data from each other (cyclic references) and, therefore, one cannot be written before the other without preventing the other from being constructed. In this case, graph theory analysis is used to determine the most efficient way to eliminate the cyclic references. Cyclic references are eliminated by replacing the smallest amount of references (copy sections) possible with data sections.
REFERENCES:
patent: 5832520 (1998-11-01), Miller
patent: 6269371 (2001-07-01), Ohnishi
patent
Fleming Michael K.
Fuller Jason W.
Kulkarni Harish
Lee & Hayes PLLC
Microsoft Corporation
Patel Kanji
LandOfFree
Systems and methods for incrementally updating an image in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systems and methods for incrementally updating an image in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for incrementally updating an image in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3276592