Self-describing software image update components

CROSS-REFERENCE TO RELATED APPLICATIONS

0001The present invention claims priority to United States provisional patent application serial no. 60/530,129 filed December 16, 2003, and incorporated herein in its entirety.

0002The present invention is related to the following United States patent applications, filed concurrently herewith and incorporated herein in their entireties: <ul id="ul0001" list-style="none" compact="compact"><li>Docket no. 4271/307,649 "Applying Custom Software Image Updates To Non-Volatile Storage in a Failsafe Manner;"</li><li>Docket no. 4281/307,650 "Determining the Maximal Set of Dependent Software Updates Valid for Installation"</li><li>Docket no. 4291/307,651 "Ensuring that a Software Update may be Installed or Run only on a Specific Device or Class of Devices" and</li><li>Docket no. 4311/307,663 "Creating File Systems Within a File In a Storage Technology-Abstracted Manner."</li></ul>

FIELD OF THE INVENTION

0003The invention relates generally to computing devices, and more particularly to updating non-volatile storage of computing devices.

BACKGROUND

0004Mobile computing devices such as personal digital assistants, contemporary mobile telephones, and hand-held and pocket-sized computers are becoming important and popular user tools. In general, they have become small enough to be extremely convenient, while consuming less battery power, and at the same time have become capable of running more powerful applications.

0005During the process of manufacturing such devices, embedded operating system images are typically built into a monolithic image file and stored in non-volatile storage (e.g., NAND or NOR flash memory, a hard disk and so forth) of each device. As a result, updating such a device is necessary or desirable from time-to-time.

0006However, a monolithic operating system has a number of disadvantages, including that to install an update, a large amount of resources (e.g., temporary storage and bandwidth) are needed to replace the entire monolithic image. At the same time, installing some subset components of the operating system is a difficult task, for various reasons. What is needed are mechanisms that facilitate the updating of some subset of an operating system image.

SUMMARY OF THE INVENTION

0007Briefly, the present invention is directed towards a system and method that provide installation and update packages, wherein each package comprises an encapsulation of a set of files that which are treated the same for the purposes of installation, and wherein the format of the package is self-describing, thereby facilitating the replacement of only component parts of an image. To this end, the system and method maps operating system features (comprising files, metadata, configuration information and so forth) into packages as part of a software build process.

0008In one implementation, packaging logic handles cases where specific files and/or settings are shared between related features, which the user in turn chooses to map to differing packages. The logic generally ensures that individual files/settings are mapped to the correct package, given a number of possible higher level package mapping requests. Further, packages optionally convey dependency information, and thus a mechanism is provided (via feature-level dependency specifications) by which packages acquire the dependency information. Logic resolves conflicts and dependencies below the feature level.

0009During the build process, a build manifest file is created by taking a binary image builder file for the operating system image and a component to package mapping file as inputs. The build manifest file specifies the file contents for a particular package. These file contents are reviewed, and any executable code is processed prior to insertion into the package to enable executable code relocation/fix-up on the device at install time. A package generation process creates the device manifest based on information in the build manifest and a package definition file.

0010The registry for the operating system image is broken up and assigned to packages based on a similar algorithm, and XML files may be similarly broken up and assigned to specific packages. The result is a number of files for each package that is to be constructed, possibly including a package definition file, a component mapping file, a component relations file, a build manifest file; registry file and an XML settings file. From these files a package generation process constructs a final package file by creating a package collection from the packages, including mapping each package to the package definition, reading the build manifest file for that package and generating the package from that data.

0011For a package to be self-describing, a device manifest file is created during the packaging process and stored in the package itself. The device manifest file is used during the installation process. Package dependency and shadow (package settings priority) data is also part of the data accompanying a package, e.g., by writing it into the device manifest file.

0012Other advantages will become apparent from the following detailed description when taken in conjunction with the drawings, in which:

BRIEF DESCRIPTION OF THE DRAWINGS

0013<ul id="ul0002" list-style="none" compact="compact"><li>FIGURE 1 is a block diagram generally representing a computer system into which the present invention may be incorporated;</li><li>FIG. 2 is a block diagram representing various components for constructing self-describing update packages, in accordance with an aspect of the present invention;</li><li>FIG. 3 is a flow diagram representing logic for creating a build manifest file from a binary image file in accordance with an aspect of the present invention;</li><li>FIG. 4 is a flow diagram representing logic for creating a registry settings-related file from registry settings in accordance with an aspect of the present invention;</li><li>FIG. 5 is a flow diagram representing logic for processing an XML-formatted file for writing data therefrom into a package, in accordance with an aspect of the present invention;</li><li>FIG. 6 is a flow diagram representing logic for generating a package, in accordance with an aspect of the present invention;</li><li>FIGS. 7A and 7B comprise a flow diagram representing logic for creating a device manifest file to describe a package, in accordance with an aspect of the present invention;</li><li>FIG. 8 is a flow diagram representing logic performed by a tool (relmerge) to insert relocation information for executable files, in accordance with an aspect of the present invention;</li><li>FIG. 9 is a block diagram representing the format of a device manifest file that describes a package, in accordance with an aspect of the present invention;</li><li>FIGS. 10A and 10B comprise flow diagrams for building a device manifest file to describe a package, in accordance with an aspect of the present invention; and</li><li>FIG. 11 is a flow diagram representing the creation of a package, in accordance with an aspect of the present invention;</li></ul>

DETAILED DESCRIPTION

<u>EXEMPLARY OPERATING ENVIRONMENT</u>

0014FIG. 1 shows functional components of one such handheld computing device 120, including a processor 122, a memory 124, a display 126, and a keyboard 128 (which may be a physical or virtual keyboard, or may represent both). A microphone 129 may be present to receive audio input. The memory 124 generally includes both volatile memory (e.g., RAM) and non-volatile memory (e.g., ROM, PCMCIA cards, and so forth). An operating system 130 is resident in the memory 124 and executes on the processor 122, such as the Windows® operating system from Microsoft Corporation, or another operating system.

0015One or more application programs 132 are loaded into memory 124 (or execute in place in ROM) and run on the operating system 130. Examples of applications include email programs, scheduling programs, PIM (personal information management) programs, word processing programs, spreadsheet programs, Internet browser programs, and so forth. The handheld personal computer 120 may also include a notification manager 134 loaded in the memory 124, which executes on the processor 122. The notification manager 134 handles notification requests, e.g., from the application programs 132. Also, as described below, the handheld personal computer 120 includes networking software 136 (e.g., hardware drivers and the like) and network components 138 (e.g., a radio and antenna) suitable for connecting the handheld personal computer 120 to a network, which may include making a telephone call.

0016The handheld personal computer 120 has a power supply 140, which is implemented as one or more batteries. The power supply 140 may further include an external power source that overrides or recharges the built-in batteries, such as an AC adapter or a powered docking cradle.

0017The exemplary handheld personal computer 120 represented in FIG. 1 is shown with three types of external notification mechanisms: one or more light emitting diodes (LEDs) 142 and an audio generator 144. These devices may be directly coupled to the power supply 140 so that when activated, they remain on for a duration dictated by a notification mechanism even though the handheld personal computer processor 122 and other components might shut down to conserve battery power. The LED 142 preferably remains on indefinitely until the user takes action. Note that contemporary versions of the audio generator 144 use too much power for today's handheld personal computer batteries, and so it is configured to turn off when the rest of the system does or at some finite duration after activation.

0018Note that although a basic handheld personal computer has been shown, virtually any device capable of receiving data communications and processing the data in some way for use by a program, such as a mobile telephone, is equivalent for purposes of implementing the present invention.

<u>SELF-DESCRIBING SOFTWARE IMAGE UPDATE COMPONENTS</u>

0019The present invention is generally directed towards installing and/or updating software that is stored on small mobile computing devices, such as Microsoft Windows® CE-based portable devices, including those in which the initial software or software update is written to the embedded device's non-volatile memory, e.g., flash memory. Notwithstanding, the present invention provides benefits to computing in general, and thus may apply to other computing devices and other types of storage, including various types of memory and/or other types of storage media such as hard disk drives. For purposes of simplicity, the term "flash" hereinafter may be used with reference to the updatable storage of a device, although it is understood that any storage mechanism is equivalent. Further, the term "image" will generally include the concept of the initial software installation image as well as subsequent software updates to an image, even when only part of an existing image is updated.

0020By way of background, contemporary operating systems such as the Windows® CE operating system are modular (componentized). However, the resultant image that contains the correct files and settings is a monolithic operating system image. To this end, at build time, feature variables are mapped to specific files and settings to determine what is contained in the resultant monolithic operating system image. The ability to perform this mapping makes use of two types of build-time configuration files: binary image builder (.bib) and registry (.reg) files. The .bib file contains a list of files which are to be included in the resultant image, and the .reg file contains a list of registry (setting) information to be included in the image. The contents of these files are grouped into collections by feature and wrapped in conditional variables which can optionally be set at build time. When a conditional feature variable is set at build time, the associated contents of the .bib and .reg files are included in the image, and as such the user of the system has the ability to select, at a granular feature level, what the resultant image should contain.

0021Higher-level logic is also applied to the selection of conditional variables, such that feature-level dependencies are self-satisfying. In other words, selecting one feature will also cause other features, on which the selected feature is dependent, to be selected. The build system thus ensures that a self-consistent monolithic operating system image results from any random selection of features on the part of the user. However, as described above, a monolithic operating system image has disadvantages relative to an image comprised in which subparts of the image can be individually updated.

0022In accordance with an aspect of the present invention, images including software updates are built from self-contained, secure entities. A fundamental update primitive is referred to as a package, wherein in general, a package is an encapsulation of a set of files that are versioned the same and are updated as a unit. The present invention provides a package format as one which is self-describing, a significant improvement when updating images, and one that facilitates replacing only a component part of an image.

0023Images are built from packages and contain both executable code and data that may be applied to storage. Note that executable code is customized to the virtual address space environment of the embedded device at install time; for example, depending on the underlying flash memory technology, some devices allow executable code to be run directly from the flash (execute-in-place, which means that the code cannot be stored in a compressed format) while other devices require that the code be copied (including decompressing the code as necessary) into RAM in order to run. In keeping with an aspect of the present invention, image update technology uses packages to break the operating system image into updateable components that can be updated in isolation, while maintaining any cross-component dependencies.

0024In accordance with an aspect of the present invention, there is provided a system and method that maps operating system features (comprising files, metadata, configuration information and so forth) into packages as part of a software build process. The packages can be used for initial device installation, and also for updates. As described below, software update packages may be in various forms, for example some may contain only the changes (deltas) to a previous update, while others may contain files that entirely replace other files. One other type of package can contain other packages.

0025The package concept described herein is a component part of the updating process. The process by which operating system features (generally an abstract concept that maps to specific files, metadata, configuration information, and so forth) are mapped into packages provides an ease-of-use advantage for the user (e.g., the provider of the image), including that instead of having to identify the lowest level components of an operating system image, the user is able to refer to higher level handles that describe a full set of associated files, metadata, configuration information and so forth for a particular aspect of the operating system image. Note that as used herein, the terms "feature" and "component" ordinarily may be used interchangeably. By referring to a feature handle, the user is able to gain an advantage in terms of managing packaging complexity through abstraction. For example, rather than specifically mapping the executable module, dynamically-linked libraries (DLLs), resource/data files, registry information, and the like for browsing component software (e.g., Internet Explorer) and individually mapping each part into a package, the present invention enables the user to refer to this associated information with a single "Internet Explorer" handle and thus map it at the feature level to a package.

0026The present invention also provides packaging logic to handle cases where specific files/settings are shared between related features, which the user in turn chooses to map to differing packages. The logic in various algorithms (described below) generally ensures that individual files/settings are mapped to the correct package, given a number of possible higher level package mapping requests. In situations in which the logic cannot determine a correct course of action, messaging is provided to the user to indicate any issues that require user intervention to resolve.

0027Further, packages optionally convey dependency information. For example, when the contents of a package rely on the contents of another package, the relationship is captured during the build process and encoded into the package for later analysis during the installation process. The present invention also provides a mechanism (via feature-level dependency specifications) by which packages acquire the dependency information.

0028In accordance with an aspect of the present invention, feature selections can be mapped to an array (one or more) of packages, resulting in specific files and settings being mapped to an appropriate package. To accomplish this correctly, logic resolves conflicts and dependencies below the feature level. For example, if two features logically refer to the same specific file and the features are mapped to different packages, the logic determines into which package the shared file is to be placed.

0029In one implementation, package files are defined at build time by three different files: a package definition file (pkd), a component mapping file (cpm), and a component relations file (crf). The pkd file defines the global attributes of the contents of a package. The pkd file is an XML file that is validated during the build process against the following XSD:<img file="EP1548587A2_D0001.tif" />

0030One example of a .pkd file is set forth below:<img file="EP1548587A2_D0002.tif" />

0031Note the presence in this definition file of the globally-unique ID (GUID) and the package name. The GUID provides a unique name for the package that can be referenced to differentiate the package from another. The package name serves to provide a handle that is used when mapping an operating system feature / component to the package.

0032In an example implementation, the cpm file is a comma-separated value file that contains component-to-package mapping information. It is of the form: <ul id="ul0003" list-style="none" compact="compact"><li><component variable>, <package name></li></ul>    or <ul id="ul0004" list-style="none" compact="compact"><li><component filename>, <package name>.</li></ul>

0033The following provides some component-to-package mapping information examples:<img file="EP1548587A2_D0003.tif" />

0034The component relations file (crf) denotes dependency and shadow relations (shadow refers to a precedence ordering for settings) between components. The component relations file is of the form: <ul id="ul0005" list-style="none" compact="compact"><li><component variable> DEPENDSON <component variable></li></ul>    Or <ul id="ul0006" list-style="none" compact="compact"><li><component variable> SHADOWS <component variable></li></ul>

0035An example of this is: <ul id="ul0007" list-style="none" compact="compact"><li>APPS_MODULES_OMADMCLIENT SHADOWS APPS_MODULES_MMS</li></ul>

0036The following tables summarize general, non-limiting definitions for some of the terms and file types described herein: <tables id="tabl0001" num="0001"><table frame="all"><tgroup cols="2" colsep="1" rowsep="1"><colspec colnum="1" colname="col1" colwidth="78.75mm" /><colspec colnum="2" colname="col2" colwidth="78.75mm" /><thead valign="top"><row><entry namest="col1" nameend="col2" align="left"><b>Terms</b></entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left">Term</entry><entry namest="col2" nameend="col2" align="left">General Definition</entry></row><row><entry namest="col1" nameend="col1" align="left">Module</entry><entry namest="col2" nameend="col2" align="left">A single executable file (.EXE, .DLL, etc.)</entry></row><row><entry namest="col1" nameend="col1" align="left">Settings</entry><entry namest="col2" nameend="col2" align="left">A collection of configuration information that may contain Registry settings, file system initialization instructions (.DAT file), Database initializations, and Provisioning XML.</entry></row><row><entry namest="col1" nameend="col1" align="left">Component</entry><entry namest="col2" nameend="col2" align="left">A collection of modules, files (non-module files including templates, fonts, etc.), and settings that make up a feature unit. Components are typically associated with sysgen MODULES tags.</entry></row><row><entry namest="col1" nameend="col1" align="left">Package</entry><entry namest="col2" nameend="col2" align="left">A collection of components that is signed and packaged for distribution</entry></row><row><entry namest="col1" nameend="col1" align="left">Manifest (package, build and device)</entry><entry namest="col2" nameend="col2" align="left">A file which describes the contents of a package. Note that in the build environment, there is a package manifest file (with a .BIB extension) that contains entries which describe the names of each file in the package; and a different manifest file, a device side manifest (with a .DSM extension), is a binary file that describes the complete set of information about a package (described below with reference to FIG. 9). As described with reference to FIG. 3, a build manifest file is created from the package manifest file, and used by a package generation process that generates the device manifest file (and the rest of the package).</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left">Shadow Order Tool</entry><entry namest="col2" nameend="col2" align="left">Build tool which processes the Component Relationships File and generates the Package Shadow Files.</entry></row></tbody></tgroup></table></tables><tables id="tabl0002" num="0002"><table frame="all"><tgroup cols="3" colsep="1" rowsep="1"><colspec colnum="1" colname="col1" colwidth="52.50mm" /><colspec colnum="2" colname="col2" colwidth="52.50mm" /><colspec colnum="3" colname="col3" colwidth="52.50mm" /><thead valign="top"><row><entry namest="col1" nameend="col3" align="left"><b>File Types</b></entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left">Exten.</entry><entry namest="col2" nameend="col2" align="left">File Type</entry><entry namest="col3" nameend="col3" align="left">General Description</entry></row><row><entry namest="col1" nameend="col1" align="left">.bib</entry><entry namest="col2" nameend="col2" align="left">Binary image builder</entry><entry namest="col3" nameend="col3" align="left">Contains a list of files which should be included in the resultant image</entry></row><row><entry namest="col1" nameend="col1" align="left">.reg</entry><entry namest="col2" nameend="col2" align="left">registry file</entry><entry namest="col3" nameend="col3" align="left">file contains a list of registry (setting) information to be included in the image</entry></row><row><entry namest="col1" nameend="col1" align="left">.pkd.xml</entry><entry namest="col2" nameend="col2" align="left">Package Definition File</entry><entry namest="col3" nameend="col3" align="left">XML file in the build tree which defines what packages exist (package name, guid, version, loc buddy)</entry></row><row><entry namest="col1" nameend="col1" align="left">.cpm.csv</entry><entry namest="col2" nameend="col2" align="left">Component to Package Mapping file</entry><entry namest="col3" nameend="col3" align="left">CSV file in the build tree which maps MODULES tags and files to packages</entry></row><row><entry namest="col1" nameend="col1" align="left">.crf.csv</entry><entry namest="col2" nameend="col2" align="left">Component Relationships File</entry><entry namest="col3" nameend="col3" align="left">Text file in the build tree which defines the relationships (shadow and dependency) between MODULES tags</entry></row><row><entry namest="col1" nameend="col1" align="left">.bsm.xml</entry><entry namest="col2" nameend="col2" align="left">Build Side Manifest File</entry><entry namest="col3" nameend="col3" align="left">an XML file translation of the .bib (binary image builder) file</entry></row><row><entry namest="col1" nameend="col1" align="left">.psf</entry><entry namest="col2" nameend="col2" align="left">Package Shadow File</entry><entry namest="col3" nameend="col3" align="left">Intermediate file in the build environment (one per package, as in <packagename>.psf) which lists the packages that need to be shadowed by the named package.</entry></row><row><entry namest="col1" nameend="col1" align="left">.dsm</entry><entry namest="col2" nameend="col2" align="left">Device Side Manifest file</entry><entry namest="col3" nameend="col3" align="left">File on the device (one per package) which describes the package (files in the package, name, guid, signature, version, shadows, dependencies, CRC, root certs, etc.)</entry></row><row><entry namest="col1" nameend="col1" align="left">.pkg.cab</entry><entry namest="col2" nameend="col2" align="left">Canonical Package file</entry><entry namest="col3" nameend="col3" align="left">Full version of a package which contains the complete file for all files in the package.</entry></row><row><entry namest="col1" nameend="col1" align="left">.pku.cab</entry><entry namest="col2" nameend="col2" align="left">Update Package file</entry><entry namest="col3" nameend="col3" align="left">A file which facilitates the update of a device from a specific version of a single package to a different version of the same package. This file may contain binary diffs of individual files, or complete files, whichever minimizes the size of the update package.</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left">.pks.cab</entry><entry namest="col2" nameend="col2" align="left">Super Package file</entry><entry namest="col3" nameend="col3" align="left">A file which contains a collection of Update Packages and/or Canonical Packages.</entry></row></tbody></tgroup></table></tables>

0037Turning to FIG. 2 of the drawings, as part of the overall package generation process, during the build process a build manifest file 202 is created by taking a binary image builder file 204 (the .bib file, also referred to as a package manifest file) for the operating system image and a component to package mapping file 206 as inputs. As described above, the build manifest file 202 specifies the file contents for a particular package.

0038FIG. 3 generally shows an example build manifest file creation process 208 by which the build manifest file 202 is created from the binary image builder file 204. As can be seen from FIG. 3, in general, each line in the binary image builder file 204 is parsed; lines that parse as a .bib file entry having valid tags (looked up in an execute-in-place table (steps 310 and 312) may be compressed as desired (step 318), and written to the build manifest file 202 (step 320).

0039The resultant build manifest file 202 is an XML file that is validated with the following XSD:<img file="EP1548587A2_D0004.tif" /><img file="EP1548587A2_D0005.tif" />

0040Similar to the way in which the build manifest file 202 was created, the registry for the operating system image is broken up (into what is sometimes referred to as an RGU file) and assigned to packages based on a similar algorithm. An example of such a process 210 (FIG. 2) is depicted in FIG. 4, wherein the registry settings 212 (FIG. 2) associated with valid tags (step 414), including their registry key names as appropriate, are written into the package RGU file (step 422). Note that the registry key names are written to that package's RGU file whenever a package being processed changes (steps 418 and 420).

0041Further, XML files 218 (FIG. 2, e.g., containing other settings) may be broken up and assigned to specific packages. An example process 220 for doing this is depicted in FIG. 5, wherein valid tags for the children nodes (evaluated at step 508) are assigned to a node of the package (step 514).

0042The result of this intermediate step of the package-creation process is a number of files, shown in FIG. 2, for each package that is to be constructed, including:<img file="EP1548587A2_D0006.tif" />

0043From these files, (including validation, e.g., via XSD 203 and XSD 225) a package generation process 230 constructs a final package file 232, generally in accordance with the flowchart shown in FIG. 6. As generally represented in FIG. 6, after some checks and validations (steps 600-610), a package collection is created from the packages (step 612), including mapping each package to the package definition, reading the build manifest file 208 for that package and generating the package from that data (steps 618-622).

0044The process of converting the build manifest file into a final package file list form and processing each executable with a relmerge tool 250 (the tool that inserts relocation information into an executable as described below with reference to FIG. 8) is generally depicted in FIGS. 7A and 7B. As generally represented in FIGS. 7A and 7B via steps 700-714, a directive file is created and the build manifest file is located and parsed, (assuming no errors occurred). If the parsing is successful (step 716), a device manifest object is created at step 720, and the process continues to step 726 of FIG. 7B, which ensures that the device manifest object was properly created.

0045Via steps 732 and 756, each file listed in the build manifest file is processed. To this end, at step 734 the file is found and determined whether to be executable at step 738. If not, the file is copied as is to a temporary build directory, otherwise the file needs to be processed by a tool 250 (FIG. 2, e.g., named relmerge.exe) that enables executable code relocation/fix-up on the device at install time (if not already processed, as tested via step 740). If the file needs relmerge processing, described below with reference to FIGS. 8A and 8B, the tool is called at step 744, and if it executes successfully, the filename is added to the device manifest.

0046Thus, as described above with reference to FIG. 7A and 7B, the file contents for a package, listed in the build manifest file 208, are reviewed and any executable code is processed prior to insertion into the package to enable executable code relocation/fix-up on the device at install time. To convert the build manifest file into a final package file list form, each executable is processed with the relmerge tool 250 that compresses the relocation information that is already in the file, and optionally (if a .REL file is provided) provides more detailed relocation information that allows the operating system to separate the code and data sections into discontiguous memory regions.

0047The relmerge tool operations are generally depicted in the flow diagram of FIG. 8. As represented by step 802, a copy of the input file is made, because the input file will be modified by running this too. The relmerge tool 250 makes a thus copy of the input file and works from that copy, which is deleted when the program exits.

0048At step 804, the signature is removed, because the signature would otherwise cause a later portion of the process (a space accounting check, described below) to fail. Note that since the tool 250 will be outputting a completely different file, the signature would have no relevance to the output file in any event. Note that in a portable executable file, (the file format for .EXE and .DLL files), the signature is stored at the end of the file outside of any section in the file, wherein each section corresponds to a unit with which data is loaded into memory by the loader. Each section has a header, called an 032 header, or identified with the IMAGE_SECTION_HEADER structure. As generally represented by step 806, to facilitate manipulating the file, the tool 250 parses the PE file headers for the PE file and its sections into suitable internal data structures. The IMAGE_SECTION_HEADER structure represents the image section header format (additional details about the IMAGE_SECTION_HEADER may be found at msdn.microsoft.com):<img file="EP1548587A2_D0007.tif" />

0049Because the file will be re-layed out with new headers and with padding removed, a space accounting check (step 808) is performed to verify that there is no information in the file that is not included in the sections of the file. Note that there are some situations where data is stored in an .EXE or .DLL file outside of the Sections, including file signatures and Codeview debug directory entries, (which are handled by the tool 250). There are other applications that may store data outside of a section, such as a self-extracting executable file which stores the data to be extracted after the .EXE itself. The compressed data is not stored in a section, otherwise the loader would attempt to load the compressed data into memory, which is not how a self-extracting executable should operate. The tool does not support these instances.

0050Space Accounting is implemented by an instance of the CSpaceAccounting class, which maintains an array of SpaceBlock structures, each of which accounts for block of data in the file. To implement Space Accounting, the areas in the file that can be accounted for are added to the SpaceAccounting as individual blocks. This is done for the file headers (including the E32 and 032 headers), and for each of the sections in the file. To accommodate CodeView debug entries, each of those are also added as a separate block. The blocks are then sorted by their offset within the file. Blocks which are adjacent in the new ordering (e.g., Block 2 begins on the byte immediately after the last byte of Block 1) are merged. At the end of the process, if all of the space in the file can be accounted for, then the list should contain one and only one block, which starts at offset 0 and has a length which is the length of the entire file. If that condition is true, then the test passes. If not, an error is reported and the tool exits.

0051If the space accounting check passes, the tool 250 searches for the .REL file in the same directory where the input file is specified, as represented by step 810. If so, it is processed via step 812, otherwise the relocation section of the PE file is processed via step 814. More particularly, the relocation parsing tool can parse two different types of relocation information, namely the relocation information in a .REL file, which contains destination section information, and the relocation information in the .reloc section of a PE file, which does not contain destination section information. To this end, relocation parsing has two entry points corresponding to parsing either a .REL file or the internal relocations in a PE file; in a current implementation, it is legal to call either one or the other, but not both.

0052In order to store the relocations, a two dimensional array of CRelocData classes is maintained, wherein the two dimensions of this array are the source section and the destination section for the relocation in question. The source section for a relocation is the section where the relocation is located, wherein a relocation is an instruction to update a particular piece of data in the file when the file is fixed up to load at a particular address; the source section identifies in which section that piece of data occurs. The source section is inferred by looking at the relative virtual address of the relocation and comparing that with the relative virtual address ranges of the sections in the file.

0053The destination section for a relocation identifies which section contains the piece of data to which the relocation is pointing. An inspection technique does not always work, because optimizers have been known to optimize the code in such a way that the relocations appear to point to other sections, e.g., it will optimize out an addition or subtraction and place it in the reference instead of in the code. For this reason, the destination section is not inferred from the data. The difference between the two relocation formats (.REL or .reloc) is whether the destination section for the relocation is known. The .REL file explicitly identifies the destination section, while the .reloc section does not.

0054As a result, for files which only have the relocation information in the .reloc section, the entire file needs to be relocated together. Without destination section information, it is not possible to separate two sections and relocate them by different amounts. Thus, this tool needs to keep track of both the source and destination section for each relocation, and keep track of whether the destination sections are valid.

0055To do this, the process maintains a two dimensional array of CRelocData classes, and each CRelocData class builds its own stream of relocation data. This array is fixed size in both dimensions, meaning that the tool can only handle PE files with some maximum (e.g., sixteen) sections. With that limitation, the data format for persisting the relocations stores eight bits for each of the source and destination sections, leaving the possibility in the data format for 256 sections. Two other functions (CalculateRelocSize and WriteRelocationsToFile) then combine these individual streams by writing out a block header for each combination of source and destination section which has at least one relocation.

0056Relocation encoding is implemented in the CRelocData class. This class takes a stream of relocation addresses (as individual calls to the CRelocData::AddReloc method), and creates a byte stream which represents the commands necessary to encode those relocations. That byte stream can be retrieved later. To implement this, the class effectively stays one command behind, always starting out with a "Single" command, representing a single relocation. Then as new relocations arrive (at the AddReloc method), they are analyzed to see if a pattern can be formed using the previous command and the new location. If the previous command is a "Single" command, the previous command can only be extended by transforming it from a "Single" command to a "Pattern" command if the new relocation address is DWORD aligned, and is within the maximum skip range of the pattern command (which is 3 DWORDs). If the previous command is a pattern command, then that pattern already has an established form, and the next element in the pattern can be deduced. If the new address happens to match the next element in that pattern, the pattern is extended by one cycle. Otherwise, a new Single command is started.

0057Returning to the overall flow of FIG. 8, because the sections of the file occur linearly in the file following the headers, the entire file needs to be re-layed out to accommodate the new header format and the removal of all of the padding between the sections. To this end, as represented by step 818, the old .RELOC section (if one existed) is removed, and the new .CRELOC section is added at the end, if there are any relocations to add. Using the file layout completed in step 818, the output file is finally created at step 820, writing the headers then the data for each section to the output file.

0058At step 822, relmerge.exe now tests to see if the target output file is nk.exe. If the output file is nk.exe, then the relmerge tool 250 processes the contents of two files, to write out the pTOC information and RomExt information, (described below). The relmerge tool 250 looks at the output file because nk.exe is created by copying different files based on debug settings. The first file processed is config.bsm.xml. This file is produced by MakePkg.exe during Image Update processing. It contains a textual representation of the names and desired values for the FIXUPVARS in the system kernel. The contents of this file are parsed and stored for later use. The second file is the map file for the input file. This file is processed by ProcessFixupVars. It takes the source file path, copies it and replaces the .exe with .map and attempts to open the map file (map files are text files containing a large amount of information about the physical and virtual addresses of functions and variables within the PE file). If the map file is successfully opened, the first line is parsed to retrieve the timestamp of the map file. The timestamp is then compared against the timestamp in the PE file. If they are different, a warning is produced and map file processing stops. If the timestamps match, each line of the file is read and a regular expression string is used to look for each FIXUPVAR. If a match is found, the address information is taken from the map file and is used to write the new variable value (from config.bsm.xml) into the source file at the correct location. At the same time, ProcessFixupVars also looks for the pTOC (where TOC represents table of contents) and RomExt variables for later processing. When pTOC is found, a new .creloc header is created with the bSrcSection set to the section retrieved from the map file (adjusted from 1 based to 0 based), the bDstSection set to 254 and a length of four. This header is written to the target file followed by the 4 byte RVA+Base address information. For RomExt, the header is the same except that bSrcSection is set to 253.

0059The pTOC/RomExt parsing operation is used because the operating system kernel requires information about the files in the ROMs, which is provided through the pTOC variable. This variable needs to be updated by the DiskImage tool and the update application running on the device. The information about this variable can only be retrieved through the .MAP file created during the compile and link phase of a system build. This file is parsed to retrieve this information.

0060Certain runtime tools need access to a variable declared within the kernel data structures. This variable is named RomExt. This variable needs to be updated by the DiskImage tool and the Update Application running on the device. The information about this variable can only be retrieved through the .MAP file created during the compile and link phase of a system build, and thus this file is parsed to retrieve this information.

0061In accordance with an aspect of the present invention, for a package to be self-describing, a device manifest file 260 (FIG. 2, shown in more detail in FIG. 9) is created during the packaging process and stored in the package itself. The device manifest file 260 is used during the installation process. The format and information contained in the device manifest file is shown in FIG. 9 and is also described with this structure definition:<img file="EP1548587A2_D0008.tif" /><img file="EP1548587A2_D0009.tif" />

0062In one implementation, as described above, the contents of a device manifest file are derived from the pkd and processed crf file (called a psf file 280 once processed) information, as well as from the build manifest file (e.g., for the file list and attribute information). The crf file describes component-level dependencies, and is processed into a form that describes package-level dependencies.

0063Further, component settings (configuration information) can shadow one-another (in other words, there is a precedence ordering in events where two related settings exist on the system such that only one will win). Dependency and shadowing information at the component level are converted into package-level relations by way of a shadow order tool.

0064The shadow order tool produces a package shadow file (packagename.psf) for each package which shadows other packages according to the component relationships file 226 (FIG. 2). The .psf file for a package lists (one per line) the GUIDs of shadowed packages. The shadow order tool's inputs are the merged component to package mapping file (.cpm), the merged component relationships file (.crf) and the merged package definition file (.pkd). The output is a text file, including formatted text lines of the form: <ul id="ul0008" list-style="none" compact="compact"><li><shadowed pkg GUID>, <shadowed pkg name>, <rule> (where rule = SHADOWS or DEPENDSON).</li></ul>

0065An example line is shown below: <ul id="ul0009" list-style="none" compact="compact"><li>273ce4bf-d4ef-4771-b2ce-6fe2fa2b2666,SMARTFON, SHADOWS</li></ul>

0066From this information, the package generator creates a device manifest file, as shown in FIG. 2 by a Device Manifest File Creation Process 262 and as generally described in FIGS. 10A and 10B. To this end, each GUID in the .psf file is added to the device manifest file, as generally represented via step 1010 of FIG. 10A. Note that in one implemetation, this includes determining if the GUID is a dependency GUID or a shadow GUID, and calling the appropriate add function on the device manifest object. When the GUIDS have been added, the device manifest object writes the device manifest file to the temporary directory, as generally represented via step 1030 of FIG. 10B.

0067As described in FIG. 11, the package file 232 is created, including the processed files described in the directive file, the rgu file(s) 214, the xml file(s) 218, and the device manifest file 260, along with other package contents 282, using a package file creation process such as a CAB file API (CABAPI). The CABAPI is intended to provide access to the contents of Cabinet files that are used as the transport mechanism for the files involved in an image update as part of the image update process.

0068To create the package, a PackageDefinition class is responsible for managing the overall creation of a Package. As part of the creation process, the PackageDefinition object creates a new subdirectory under the directory specified by the '_FLATRELEASEDIR' environment variable. The directory name is the package name, with the string "_PACKAGE_FILES" appended thereto, e.g., given a package named -- "LANG" --, a directory named "LANG_PACKAGE_FILES" would be created. This directory is created when the method SetDirectoryBase is called on the object. When the PackageDefinition object creates a package, the name of the resulting package file is the friendly name of the package with a ".PKG" extension. The package file conforms to the Microsoft CAB file specification for CAB version 1.3.

0069The PackagDefinition class provides the following public methods: <ul id="ul0010" list-style="bullet" compact="compact"><li>PackageDefinition( XipPackage pkg) - Constructor to create a package based on an XipPackage object.</li><li>SetDirectoryBase( string path ) - Creates a new subdirectory under the specified directory.</li><li>Validate() - Determines if the package has the two required fields, a name and a GUID.</li><li>ReadManifest() - Causes the BuildManifest associated with this package to parse the appropriate build manifest file.</li><li>MakePackage() - Creates the actual package file for this package definition.</li></ul>

0070Further, when working with the various files for inclusion in the packages, it should be noted that executable code and data may be arranged in separate files. One significant advantage of is to facilitate a multi-language system, where the language-specific parts of a feature are placed into separate packages that are language specific. This creates a system where the packages that contain the executable code of the system are separate from the packages that contain language-specific components of the system. As a result, a patch for the executable code of a feature may be applied to any device, independent of any combination of languages that are installed on a that device.

0071More particularly, by construction, when a feature is built, the executable code (and language-independent data) are separated into one set of files, and the language-dependent data (and potentially code) into another set of files. These files are tagged as being part of the feature, but the language-dependent data files are further tagged being as language dependent. The system then moves those files into a separate package (e.g., described by a LocBuddy tag in the pkd file).

0072By way of example, a telephone-based feature may be in a library (e.g., tpcutil.dll) that is language-independent. The language-dependent resources for the phone feature are built into another resource dll, e.g., named tapres.dll, which is further localized for each language, e.g., it becomes tapres.dll.0409.mui (for US English), tapres.dll.0407.mui (for German), and so forth. These files are tagged as being part of the phone feature, but the language-specific files are further tagged as being language-specific, with suitable filenames. For example, filenames may be constructed by substituting suitable language tags into a location-based variable in the name, such as represented by tapres.dll.%LOCID%.mui. Then the file is processed for each language that is supported, and multiple LANGPHONE (the locbuddy) packages are generated, e.g., LANGPHONE_0409 (for US English), LANGPHONE_0407 (for German), and so forth. As a result, the system can later update the LANGPHONE region such as to fix bugs in tpcutil.dll, independent of which languages are installed on the phone (via different LANGPHONE_xxxx packages).

0073Additionally, the flexibility of the system is such that language-specific executable code is allowed where necessary. For example, different languages and locales have different Input Method Editors (IMEs) which are used for capturing text in that language. These IMEs require special code for each language, and thus are placed inside one of the LANG regions.

0074Lastly, note that cabinet verification may be performed. The cabinet verification module extracts the device manifest file 260 from the final package file 232 (a cabinet file) and verifying the cabinet file against the contents of the device manifest 260.

0075As can be seen from the foregoing detailed description, there is provided various mechanisms that that facilitate the updating of some subset of an operating system image. A self-describing package file is provided, including dependency, shadow and other features that make updating of an image straightforward and correct.

0076While the invention is susceptible to various modifications and alternative constructions, certain illustrated embodiments thereof are shown in the drawings and have been described above in detail. It should be understood, however, that there is no intention to limit the invention to the specific forms disclosed, but on the contrary, the intention is to cover all modifications, alternative constructions, and equivalents falling within the spirit and scope of the invention.