确定对安装有效的最大依赖软件更新组

摘要

所描述的是一种系统和方法，其中，审阅用于安装(如，到嵌入式计算设备上)的软件包集合的依赖关系，由此能够选择最大安装可能性组，以允许以最少的可能更新步骤对任一给定包的最高版本更新，同时遵从依赖性约束。更新确认过程组织并确认下载到设备的更新包，并为每一组构建图。处理包括更新之间的路径的图数据，以确认更新并确定当有一个以上路径可用于到达同一版本时，可用最小加权(成本)来应用到设备上的现有映象来产生期望更新的最小且最优包组。

说明书

相关申请的参照

本发明要求2003年12月16日提交的美国临时专利申请序列号60/530,126的优先权，该申请整体结合于此。

本申请涉及与其同时提交的以下美国专利申请，这些申请整体结合于此：

摘要号4271/307,649，“以故障保险方式向非易失存储应用自定义软件映象更新(Applying Custom Software Image Updates To Non-Volatile Storage in a FailsafeManner)”；

摘要号4291/307,651，“确保软件更新仅在特定的设备或设备类上安装或运行(Ensuring that a Software Update may be Installed or Run only on a Specific Deviceor Class of Devices)”；

摘要号4301/307,652，“自描述软件映象更新组件(Self-Describing SoftwareImage Update Components)”以及

摘要号4311/307,663，“以存储技术抽象方式在文件内创建文件系统(CreatingFile Systems Within a File In a Storage Technology-Abstracted Manner)”。

技术领域

本发明一般涉及诸如具有嵌入式操作系统的计算设备，尤其涉及更新计算设备的非易失存储。

背景技术

诸如个人数字助理、当代移动电话和手持式及袖珍计算机等移动计算设备正在变为重要且流行的用户工具。一般而言，它们变得足够小，使得它们极度方便，而消耗较少的电池功率，且在同时变得能够运行更强大的应用程序。

在制造这类设备的过程中，嵌入式操作系统映象通常被内建到每一设备的单块映象文件中，并储存在非易失存储中(如，NAND或NOR闪存、硬盘等等)。作为结果，更新这一设备有时是必需或期望的。

然而，单块操作系统具有众多缺点，包括为安装更新，需要大量的资源(如，临时存储和带宽)来替换整个单块映象。同时，安装操作系统的某些子集组件是一项困难的任务，因为设备上现有包安装状态是可变的，并且可存在任意数量的有版本的包排队等候安装。目前，没有一种已知的可查询设备上已安装的映象来找出要安装什么的智能映象更新服务器架构。然而，即使可开发这一服务器架构，会存在关于与服务器共享设备的安装状态信息的私密性问题。需要一种能够处理许多更新版本以及那些版本之间的冲突和依赖性的在设备侧处理设备更新的有效方法。

发明内容

简单而言，本发明针对一种系统和方法，通过该系统和方法可审阅用于安装(如，在嵌入式设备上)的包集合的依赖关系，由此能选择最大安装可能性组以允许以可能的最少更新步骤对任意给定包的最高版本更新，而遵从包依赖约束。这通过知道设备上的现有包安装状态以及被排队等候安装的有版本的包来实现。

首先确认要安装的任一包，这涉及一个过程，其中，审阅排队等候安装的包的完整性、确认内容、确定更新权限(根据签名机制)并确定依赖关系。在一个实现中，确认过程的结果包括两个列表：由于通过确认要求而可被安装的包列表、及由于无法满足确认要求的一个或多个而无法被安装的包列表。列表可被排序成安装顺序。

提供了一种更新确认器/确认过程，一般而言，它确认下载到设备上的一组更新包并基于要更新的目标包将它们组织成组。处理每一组以确定可应用到设备的现有映象来生成更新的最小且最优包组。为确定最小且最优包组，将包组织成具有从基节点(表示目标包)到每一叶节点的多个路径的图。该图方便了确定通过该包组的最优路径，由此，可以最低的成本(加权)更新将现有设备包更新到更新组内指定的每一包的可能的最高版本。为此，在构建了图之后，为各种确认目的步查(walk)这些图，同时试图找出当有一个以上路径可用于到达同一版本时，可用最少的权值(成本)将该设备更新到的最高版本。

在一个实现中，确认过程可作为例如由更新应用程序所调用的应用编程接口来访问。确认过程查找每一包的设备清单文件(设备清单文件描述该包)，当找到时，将该包添加(如，作为该包的代表性节点)到包图。当处理了每一清单文件时，图处理查找证书信息，包括检查父节点的证书链，并在无效时从父节点延伸出的树中剪除任一对应的分支。当处理了图的分支和节点之后，包括签名核实，确定最低加权分支，并将该分支添加到要返回到调用实体的更新列表。

当结合附图阅读以下详细描述时，可以清楚其它优点，附图中：

附图说明

图1是一般表示可结合本发明的计算机系统的框图；

图2是依照本发明的一个方面用于获取包依赖信息的清单文件的表示；

图3A和3B包括依照本发明的一个方面用于执行更新确认过程，包括处理依赖信息的流程图；

图4所示是依照本发明的一个方面执行更新确认过程的各种机制的框图；

图5A和5B包括依照本发明的一个方面用于执行下令更新过程，包括处理依赖信息的流程图；

图6是依照本发明的一个方面用于构造图来评估包依赖性的流程图；

图7A和7B包括依照本发明的一个方面用于执行包更新图的遍历的流程图。

具体实施方式

示例性操作环境

图1示出了一个这样的手持式计算设备120的功能组件，包括处理器122、存储器124、显示屏126和键盘128(可以是物理或虚拟键盘，或表示两者)。可存在麦克风129以接收音频输入。存储器124一般包括易失存储器(如，RAM)和非易失存储器(如，ROM、PCMCIA卡等等)。操作系统130驻留在存储器124中，并在处理器122上执行，如微软公司的Windows^操作系统或另一操作系统。

一个或多个应用程序132被加载到存储器124中，并在操作系统130上运行。应用程序的示例包括电子邮件程序、调度程序、PIM(个人信息管理)程序、文字处理程序、电子表格程序、因特网浏览器程序等等。手持式个人计算机120也可包括加载到存储器124中的通知管理器134，它在处理器122上执行。通知管理器134处理如来自应用程序132的通知请求。同样，如下所述，手持式个人计算机120包括适用于将手持式个人计算机120连接到网络(包括作出电话呼叫)的网络软件136(如，硬件驱动程序等)和网络组件138(如，无线电和天线)。

手持式个人计算机120具有电源140，它被实现为一个或多个电池。电源140还可包括忽略内置电池或对其重新充电的外部电源，如AC适配器或加电对接托架。

图1所示的示例性手持式个人计算机120被示出为具有三种类型的外部通知机制：一个或多个发光二极管(LED)142和音频生成器144。这些设备可直接耦合至电源140，使得当被激活时，即使手持式个人计算机处理器122或其它组件被关闭以保存电池能量时，它们也保留一段由通知机制指示的持续时间。LED 142较佳地不确定地保留，直到用户采取行动。注意，音频生成器144的当代版本使用当今手持式个人计算机电池的太多能量，因此它被配置成当系统的剩余部分被关闭时，或者在激活后的一段确定持续时间之后被关闭。

注意，尽管示出了基本手持式个人计算机，然而，为实现本发明的目的，实际上能够以可由程序使用的某一方式接收数据通信和处理数据的任何设备都是等效的。

确定对安装有效的软件更新

本发明一般针对更新储存在诸如基于微软Windows^CE.NET的便携式设备等小型移动计算设备上的软件，这些设备包括在其中将初始软件或软件更新写入诸如闪存等嵌入式设备的非易失存储器的那些设备。尽管如此，本发明提供了在总体上计算的益处，并由此可应用到其它计算设备和其它类型的存储，包括各种类型的存储器和/或其它类型的存储媒质，如硬盘驱动器。为简化目的，术语“闪存”在后文参考设备的可更新存储来使用，尽管可以理解，任一存储机制都是等效的。此外，术语“映象”一般包括初始软件安装映象以及对该映象的随后的软件更新的概念，即使仅更新现有映象的一部分。

依照本发明的一个方面，以有效、智能(且故障保险)的方式向嵌入式设备的非易失存储应用自包含、安全实体形式的可用软件更新的一个适当的子集。可应用各种类型的软件更新，包括全替换更新以及仅包含对前一更新的改变的更新。这些软件更新可包含可执行代码和数据两者，在安装时刻将可执行代码定制到嵌入式设备的虚拟地址空间环境。

与单块更新不同，一旦在设备上安装了初始制造映象，可通过按本发明更新该映象的离散部分来执行对该映象的更新。在一个实现中，这些离散部分被封装成包，其中，包是映象文件(代码、数据、脚本等等)的自描述集合，并可包括被签署并被包装用于分发的组件的集合。在这一实现中，整个操作系统映象根据一个或多个包来构建，其每一个都被个别地或与其它包组合来更新，取决于每一包的要求。

包可以各种方式来配置，包括“规范”、“增量/差”和“超级”形式，其每一个都服务关于软件更新的各种目的。例如，规范包包含包内每一文件的完整副本，而增量/差包包含仅包含基于该文件的较早修订版本的二进制差的一个或多个文件。增量/差包应用到已安装的前一版本，由此，通常相对于其它包较小，并且在试图减少下载成本和下载时间时使用。超级包包含其它包，并在需要下载一个以上包时，如，更新互相依赖的包时用作一种方便。

规范包在构建过程中通过将操作系统特征和元数据(如，特定应用程序的可执行代码和关联的数据和配置信息)与包定义相关联来生成。增量/差包通过向两个规范包的内容应用二进制差算法，并依照本发明如后文所描述的捕捉增量/差包在基线规范包版本上具有的依赖关系，从规范包生成。

依照本发明的一个方面，提供了一种组织并确认被下载到设备的一组更新包的更新确认器/确认过程。该过程中的第一步基于要更新的目标包将包组织成一致的组。在包被组织成组之后，处理每一组以确定可应用到设备上的现有映象来产生更新的最小且最优包组。一致组的每一个包括以设备上同一现有包为目标的一组包。新包的每一个具有不同的基础版本，并可应用到不同的目标版本。

为确定最小且最优包组，将包组织成具有从基节点(表示目标包)到每一叶节点的多个路径的图。这方便了确定通过构成该图的包组的最优路径。处理每一组以确定要安装的组内的最优包组，由此，将现有设备包更新到更新组内所指定的每一包的最高可能版本。

各种因素影响这一处理的结果。例如，如果无法确认依赖性或签名，则从图中移除该更新的分支，并尝试不同的分支，如果有可用的分支的话。对于需要更新多少数据，一个分支可以比另一分支更有效；注意，规范包被认为具有无穷的权值，因为不使用规范包来获取更新的任一方式(即，通过至少某些增量，可能在多个包中)可能比将每一文件写(如，闪存)入规范包中更有效。可选地，规范包具有实际的权值也是可行的。

由此，对每一包构架一个图，无论该包是在NK(内核)分区还是在系统分区中，其中，分区本质上是不同的文件系统，它们可具有不同的属性，可在分区中储存包内容，如由上述名为“以存储技术抽象方式在文件内创建文件系统”的相关专利申请中所描述的。注意，具有到NK分区的内容的包是与其内容到IMGFS分区中的包是相同种类的包。然而，对于IMGFS分区的NK和系统更新，加载/启动操作系统的序列是不同的，因为NK分区被首先加载，并且NK分区中的驱动程序被用于定位并加载IMGFS分区文件。

向该包的对应图添加每一更新包的节点。然后使用包清单中清楚说明的版本依赖关系连接图中的节点，如包的版本二可升级包的版本一，版本三可升级版本二(但不是版本一)，由此，在版本一和二之间以及版本二和三之间可存在边连接，但是在版本一和三之间不存在。应当理解，上述版本关系仅为示例，关系实际上依赖于构建更新的方式。例如，可构建从版本1包更新的版本3包。一般而言，每一更新包具有特定的源版本和特定的目标(最终)版本，并仅可从该源版本更新(不必要是目标版本减一)。注意，规范更新包可更新任一较早的版本。

在构建了图之后，为各种确认目的步查这些图，如，如下所述地检查签名。一般而言，图步查过程遍历每一图中的路径，试图找出当有一个以上路径可用于到达同一版本时，可以用最小的权值(成本)将设备更新到的最高版本。在步查时，如果节点未被确认，则本质上将该节点及其路径从该图中移除。

对于包清单，如上述名为“自描述软件映象更新组件”的相关专利申请中所描述的，每一包类型包含一完整地描述包内容以及通用包特征(包括依赖信息)的设备侧清单文件(如，具有.dsm扩展名)。图2表示了该清单文件的布局。

如下表中所见的，该设备清单头部包含唯一地涉及该特定包的直系的全局唯一标识符(GUID)以及涉及该特定包文件的版本：

typedef struct_DeviceManifestHeader{    const DWORD dwStructSize；//用于指定版本的该结构的大小(以字节表示)    const DWORD dwPackageVersion；//该包的版本    const DWORD dwPrevPkgVersion；//该包所更新的包的版本，(0)代表规范    const DWORD dwPackageFlags；//包专用标识符    const DWORD dwProcessorID；//什么处理器(匹配winnt.h中的定义)    const DWORD dwOSVersion；//构建到操作系统的什么版本    const DWORD dwPlatformID；//目标平台是什么    const DWORD dwNameLength；//以字节表示的文件名长度    const DWORD dwNameOffset；//对包的友好名的偏移    const DWORD dwDependentCount；//依赖GUID列表中有多少条目    const DWORD dwDependentOffset；//从文件的前端开始有多少字节是依赖                                   //GUID结构    const DWORD dwShadowCount；//阴影GUID列表中有多少条目    const DWORD dwShadowOffset；//从文件的前端开始有多少字节是附有                                //阴影包GUID的数组    const DWORD dwFileCount；   //该清单中列出了多少文件    const DWORD dwFileListOffset；//从文件的前端开始到第一个文件条目                                  //有多少字节    const DWORD cbCERTData；//数字证书数据的字节数    const DWORD dwCERTDataOffset；//从文件的前端开始到证书数据                                 //有多少字节    const GUID guidPackage；    //该包的GUID}DeviceManifestHeader*PDeviceManifestHeader；typedef struct_DependentEntry{    const DWORD size；    const DWORD version；    const GUID guid；}DependentEntry，*PDependentEntry；typedef struct_FileEntry{    const DWORD dwNameLength；    const DWORD dwFlags；    const DWORD dwOffset；    const DWORD dwBase；//该文件最初与其链接的基地址    const DWORD dwFileSize；//整个文件的大小，对更新包不准确。}FILEENTRY，*PFILEENTRY；

在设备清单头部中还可见到当前包所依赖的包的列表，其每一个由以下结构来描述：

typedef struct_DependentEntry{     const DWORD size；     const DWORD version；     const GUID guid；}DependentEntry，*pDependentEntry；

可存在多个包，其每一个都由一GUID唯一地描述；包的所有版本共享同一GUID。包的依赖规则要求该包或该包所依赖的包为依赖列表中所标识的版本号或高于该版本号。如果这样一个版本已安装在设备上，或安装待决但其依赖性已满足(由此确保其安装)，则包为指定的版本或高于此版本。

为提供对设备侧清单文件(在一个实现中为具有所有者格式的二进制文件)中的信息的访问，提供了一种公用包信息API(PackageInfoAPI)。本发明使用该包信息API来确定设备上的包以及排队等候可能安装的包的现有安装状态。该API作为构建系统API以及嵌入式设备API存在，并服务以有效地分析包文件的集合的设备清单文件。一般而言，包信息API提供枚举设备上预先存在的包、枚举特定包的阴影顺序信息(后文描述)、枚举特定包的依赖信息、以及枚举属于特定包的文件的文件名列表的能力。包信息API也提供打开作为设备侧清单储存在文件系统中的文件、从指定的包内打开设备侧清单文件、以及检索特定包的包信息(如，_PACKAGEINFO)的能力。包信息API也提供当给定到特定文件的路径时为该文件计算CRC32值、以及给定到特定包的路径时为该包计算CRC32值的接口。PackageInfoAPI组件包含下文描述的API的一个实现。

以下API组定义了对PackageInfoAPI的外部接口。数据类型描述如下：

·HPKGENUM-这是用于标识特定包枚举组的不透明数据类型。

·HPKG-这是用于表示唯一包的不透明数据类型。

·HRESULT-这是标准COM返回类型。

·REFGUID-这是到GUID结构的引用。

·LPTSTR-这是到TCHAR串的指针。

·HFILEENTRY-这是用于向调用程序传递FILEENTRY信息的不透明数据类型。

以下API找出第一个有效(有效＝＝不是恶意的“模仿者”)包并提供检索包信息所需的句柄：

HRESULT Pkg_FindFirstPackage(

  /*[out]*/HPKGENUM*phPkgEnum，

  /*[out]*/HPKG*phPkg)；

以下API找出下一个有效的包并提供检索包信息所需的句柄(S_FALSE指示枚举的结束)：

HRESULT Pkg_FindNextPackage(

  /*[in]*/HPKGENUM hPkgEnum，

  /*[out]*/HPKG*phPkg)；

以下API关闭包枚举器：

HRESULT Pkg_FindClose(/*[in]*/HPKGENUM hPkgEnum)；

以下API将“打开”具有指定GUID的设备侧清单文件，提供检索包信息所需的句柄。这是FindFirstPackage/FindNextPackage API的替换使用：

HRESULT Pkg_OpenPackageByGUID(

  REFGUID guidPkg，

  /*[out]*/HPKG*phPkg)；

以下API将“打开”具有指定名字的设备侧清单文件，提供检索包信息所需的句柄。这是FindFirstPackage/FindNextPackage API的替换使用：

　　HRESULT Pkg_OpenPackageByName(<!-- SIPO <DP n="9"> --><dp n="d9"/>　　LPCTSTR szFileName，　　/*[out]*/HPKG*phPkg)；　　//“关闭”包(先前用Pkg_FindFirstPackage、Pkg_FindNextPackage　　//或Pkg_OpenPackageByGUID打开的包)　　HRESULT Pkg_Close(HPKG hPkg)；　　//枚举附有阴影的包。S_FALSE指示枚举的结束　　HRESULT Pkg_GetNextShadowedPackage(HPKG hPkg，　　/*[out]*/GUID*pguidShadowedPkg)；　　//开始指定包的GUID依赖性的枚举。　　HRESULT Pkg_GetFirstDependentPackage(　　HPKG hPkg，　　/*[out]*/GUID pguidDependentPkg，　　/*[out]*/DWORD*pdwDependentPackageVersion)；　　//继续对给定包的GUID依赖性的枚举。S_FALSE指示枚举的结束。　　HRESULT Pkg_GetNextDependentPackage(HPKG hPkg，　　/*[out]*/GUID*pguidDependentPkg，/*[out]*/DWORD　　*pdwDependentPackageVersion)；　　//开始包中列出的文件的枚举。如果缓冲器不够大(或为空)，则将cbSize　　//设为需要的缓冲器大小，包括末端的NUL字符。　　HRESULT Pkg_GetFirstFile(　　HPKG hPkg，　　/*[out]*/LPTSTR pszFileName，　　/*[in/out]*/DWORD*cbSize)；　　//枚举包中的文件。S_FALSE指示枚举的结束。　　HRESULT Pkg_GetNextFile(HPKG hPkg，/*[out]*/<!-- SIPO <DP n="10"> --><dp n="d10"/>　　LPTSTR pszFilename，DOWRD cbSize)；　　//获取包的单次出现的信息　　HRESULT Pkg_GetPkgInfo(HPKG hPkg，/*[out]*/　　PPACKAGEINFO pPackageInfo)；　　//将指定的文件映射为DSM文件。如果它不是DSM，返回E_FAIL。　　HRESULT PkgInfo_OpenByName(LPCTSTR szFullName)；　　//确定特定的文件是否包含在指定的包内。　　//如果命名的文件是包的一部分，则HFILEENTRY为非空。　　HRESULT Pkg_ContainsFile(　　HPKG hPkg，　　LPTSTR szFileName，　　/*[out]*/HFILEENTRY**pFileEntry)；　　//确认指定包的头部。　　HRESULT Pkg_ValidateHeader(　　HPKG hPkg，　　DWORD DWFileSize)；　　//将CERT(证书)数据从指定的包复制到传入的缓冲器中。　　//如果缓冲器不够大或者为空，则将pcbBufferSize设为需要的大小。　　HRESULT Pkg_GetCERTData(　　HPKG hPkg，　　LPVOID lpBuffer，　　DWORD*pcbBufferSize)；　　//以及CRC计算API(这用于测试，例如，　　//对照储存在设备上的CRC进行核实<!-- SIPO <DP n="11"> --><dp n="d11"/>　　HRESULT Pkg_CalculateFileCRC(　　LPCTSTR pszFilename，　　/*[out]*/DWORD*pdwCRC)；　　HRESULT Pkg_CalculatePackageCRC(　　LPCTSTR pszPackageName，　　/*[out]*/DWORD*pdwCRC)；　　//打开CAB，提取DSM并映射。　　//如果文件不存在或不是DSM，则返回E_FAIL。　　HRESULT PkgInfo_ExtractFrom(LPCTSTR szCABFile)；　　//给定由CABAPI返回的HCAB，找出DSM、提取它并映射它。如果文件　　//不存在或不是DSM，则返回E FAIL。　　HRESULT Pkg_Info_ExtractFromHCAB(HCAB hCab)；

依照本发明的一个方面，首先确认要安装的任一包。包确认涉及审阅排队等候安装的包的完整性、确认其内容、确定更新权限(根据签名机制)以及确定依赖关系的过程。在一个实现中，确认过程的结果包括两个列表：由于通过确认要求可被安装的一个或多个包的列表、及由于无法满足一个或多个确认要求不能被安装的一个或多个包的列表，以及其每一个的失败原因。列表可被排序成安装顺序，除确保如果应用增量则所需的文件存在以外，它可依赖于大小考虑事项来减少碎片并确保有足够的空间来更新。图3A和3B包括描述总体确认过程的流程图。

在一个实现中，确认过程可作为调用的应用编程接口，例如由更新应用程序来访问。有两个函数，一个函数用更新的文件名来调用，以确认并返回其安装数据，在另一个函数中调用程序提供到可储存更新包的目录的路径。为简化的目的，一般在此将更新认为是在目录中。

在图3A和3B中，例如，当给定包含要安装的一个或多个包的目录时，执行若干测试来确定包是否可被安装。步骤300获得包目录，并测试以确定该目录是否存在(步骤302)以及该目录是否包含文件(步骤304)。如果不是，则通过步骤306返回错误消息，确认过程结束。

如果目录存在，且包含至少一个文件，则步骤308和322循环以重复通过每一文件，在每一个上执行测试。步骤310测试该文件是否为合适类型的包文件；如果是，则步骤312试图从该包中提取设备侧清单文件(DSM)。更具体地，在一个实现中，使用CABAPI来试图作为CAB文件打开文件。如果成功，则作出提取DSM的试图。如果文件无法作为CAB文件被加载，则将名字记录到坏包的列表中，用HRESULT错误代码指示指定的文件名不能作为CAB文件被加载。如果DSM不能被提取，则将该文件名记录到坏包的列表中，用HRESULT错误代码指示CAB中没有DSM。如果不是CAB文件或如果如在步骤314所评估的无法找到设备侧清单文件，则选择下一包文件并测试，直到没有文件剩余为止。

当找到设备侧文件时，通过步骤316将包添加(如，作为该包的代表性节点)到包图。如果在由步骤318测试时不成功，则确认过程结束(在步骤320)，作为无法创建节点的结果。

当处理了每一文件之后，如果目录中至少一个文件是具有设备侧清单文件的包文件，则图应当不为空。如果图为空(步骤324)，则没有一个文件是有效的包，过程在步骤326结束。否则，过程继续到图3B的步骤328。

图3B的步骤328(以及步骤348)表示用于处理图中的每一分支的循环，而步骤330(以及步骤344)表示用于处理当前被处理的分支中的每一节点的嵌套循环。一般而言，处理查找证书信息，包括通过步骤332和334检查父节点的证书链、当未找到时通过步骤336从父节点延伸出的树中剪除对应的分支。

如果找到，则通过步骤338和340核实签名。如果找到，则在步骤342将加权数据(用于在决定当一个以上包可用于提供同一结果时相对其它包使用哪一包时来评估效率)添加到基于该节点的分支，并且通过步骤344选择下一节点，直到没有剩余。当包被加载时计算加权信息，并且当构建路径时将加权信息添加到路径的权值。初始图构造排除了包有效的假定，由此，仅需要过程希望使用的包核实签名信息，而非在更新组中的每一包上执行核实，这有希望地减少了执行的签名检查次数。如果在步骤340签名无效，则在步骤346从当前节点剪除该分支。

在以这一方式处理了图的分支和节点之后，如由步骤350所示的步查该图，以找出最低权值的分支，并且将该分支添加到要返回的更新列表。

依照本发明的一个方面，确认过程提供能够确定对安装有效的最大依赖软件更新的版本依赖性计算要求。如由图4的框图所表示的，确认过程402与各种组件相关联(或可被认为是包括各种组件)来作出决定，包括下令更新组件404。下令更新组件404构造作为更新组408被下载到设备的包组的图406、从包清单410提取依赖信息并核实其它包412以正确的版本在设备上存在(或在排队等候安装的包414中)。另外，下令更新组件404负责分析现有和新的设备清单文件410和412，并基于依赖要求为包生成安装顺序。

图5A和5B包括描述确认过程的下令更新过程的流程图。一般而言，在某一初始化和确认检查(步骤500、502和504)之后，对于设备上对应于先前安装的包的每一现有的设备清单文件，由下令更新过程创建包图以表示该包，如由在设备上维护的包设备清单文件所定义的。注意，确认过程可使用包信息API来枚举现有的设备清单。在步骤506更新目录中的包被添加到该包的适当的基线图中；如果没有找到现有的图，则为新包创建图，但是将其标记为非基线图。节点包含基于清单和包的信息，并且当被添加时，查找图中的其它节点的版本信息以基于包可更新到哪一或哪些版本来确定连接到哪一或哪些节点。注意，在图中可存在能够更新被添加到图的包的孤立节点。图构造过程步查构成该图的节点，并且如果在图中有可更新新节点的现有节点，添加适当的链接。

一旦添加了要安装的包，步查每一图，包括为评估路径和执行文件确认的目的。注意，在节点被添加到图的实时构造通过图的路径。如后文参考图6所描述的，一旦加载了包，更新确认器步查每一图，查找对图可用的路径组中的最优路径。一旦为图选择了一个路径，则确认该路径中的节点的签名。如果不能确认特定节点的签名，则从失败节点开始剪除该路径，然后为该图重新运行路径选择过程。重复该过程，直到确定了路径中的节点具有有效签名，或者对给定的图没有更多的路径来处理。

如果在步骤514处理成功，则下令更新过程在图5B的步骤518继续，其中，对于每一所得的包路径，如果该包是NK分区的一部分，则通过步骤522将包信息添加到NK列表416(图4)。如果包不是NK分区的一部分，则将该包添加到另一列表418(图4)。一旦处理了所有的包图，则通过步骤532将其它列表418追加到NK列表416，如果如步骤534所评估的追加成功，则以追加的NK列表416和无效列表420返回NOERROR状态。

确认过程402的另一部分针对构造更新图，并由更新图组件422实现，它负责为包括设备上的更新的包构建图。设备上每一预先存在的包将被用于为独立的图创建基节点。在一个实现中，每一包由包节点对象表示；注意，在该实现中，每一节点对象包含在一个且仅一个包图对象中。

图构造过程在图6中表示。一般而言，更新图424(图4)包括两个数组，包括节点对象数组436和边对象数组428。边对象将节点彼此链接。当新包被添加到图时，为该包创建节点对象，并将其添加到节点数组426，如由步骤600所表示的。如果如由步骤602所评估的未创建节点，则过程失败。

步骤606和608试图找出对应于该包的现有图；如果没有找到，则该包为新包，并在步骤610为其创建图，(并通过步骤612确保它被正确地创建)。如果成功地创建，则在步骤616返回新图，否则返回失败。

如果节点创建成功，且为该包找到图，则步骤608分支到步骤618，其中，通过步骤618-630，对节点数组中的每一节点，如果新节点的基础版本与现有节点的版本号相匹配，则在更新图424(图4)中创建边对象并将其添加到数组428。在这一条件下，边对象将现有节点指定为源，而将新节点指定为宿。如果相反，现有节点的基础版本与新节点的版本号相匹配，则创建将新节点指定为源而将现有节点指定为宿的边对象。

注意，对于要添加的包，可能在添加时没有到任何现有节点的链接。这一条件可通过两个结果之一来矫正，即(a)没有可通过该包节点到达的节点，并且没有通过更新中的其它包节点到达该包节点的路径；在这一情况下，将节点标记为坏，并以无效更新列表结束，以及(b)稍后将要添加的包将连接到该节点。在这一情况下，在图步查阶段处理该节点，这在下文参考图7A和7B描述。

此外，注意，如果两个包具有同一目标版本，则比较这两个设备侧清单文件。如果它们不相等，则将两个节点都标记为无效，因为对于任一给定的包，特定版本的设备侧清单文件应当跨将该给定包更新到特定版本的所有包都是相同的。

作为确认过程的另一部分，更新图步查器组件430遍历每一包图，以基于通过该图的可能多个路径确定该包的最高最终版本号。在步查时，更新图步查器组件430确认图中的包上的数字签名。如果签名检查失败，则在该点上剪除该图，并移除连接到失败的节点的任何边。

一旦确定了最高版本号，确认对该节点的依赖性。这通过向更新图424查询匹配依赖GUID的包图来实现。如果新更新图尚未被确认，则更新图步查器在新包图上开始步查过程。如果无法满足依赖性，则放弃该分支并尝试新分支。移除连接分支中的节点的边。如果穷尽了所有可能的边并且仍无法满足依赖性要求，则将由图中的节点表示的图移至无效更新列表。

图7A和7B表示遍历过程的逻辑，从图的基节点开始。如由步骤702-706所示的，对于图中的每一边，确定该边是否具有该节点作为源(步骤704)。如果没有与该节点关联的边，则检测到终端节点，并由步骤708-718处理。一般而言，这些步骤将节点的版本号与图版本号相比较(步骤714)，如果节点版本高于图版本，则在步骤716将图版本更新到节点版本，过程结束(不返回错误)。

如果相反，在步骤704，存在边，则过程分支到图7B的步骤724，检查该节点来看它是否具有CERT链。如果在步骤724没有CERT链，则从对应于该节点的设备侧清单文件获取CERT块。注意，如果在设备侧清单文件中没有CERT块，则在步骤730将该节点标记为坏，过程返回。

如果在步骤724或步骤728存在CERT数据，则过程前进到步骤734来解码该数据。如果解码失败，则在步骤730将该节点标记为坏，过程返回。

否则，在步骤738执行找出边的末端的宿节点的尝试，在步骤740作出关于是否不存在宿节点的测试；如果不是，则将图完整性错误记入日志，过程通过步骤742返回。

如果找到宿节点，则使用CERT数据来确认宿节点(步骤744)。如果宿节点通过签名确认，则递归地调用该函数，在步骤748传递宿节点，返回到图7A的步骤720。如果宿节点失败，则将该边标记为坏。

以这一方式，确定最大更新组，并返回排序的更新列表，以及任何无效更新的列表。这可对应于将设备包版本最大化的包的最小数量。

如可从上文的详细描述中所见到的，提供了一种在设备侧处理设备更新的机制。该机制处理许多更新版本以及那些版本之间的冲突和依赖性，以提供当应用时可将设备包版本最大化的最小数量的有效包。

尽管本发明易受各种修改和替换构造的影响，然而在附图中示出了某些说明的实施例并在上文详细描述了它们。然而应当理解，这并非将本发明限于所揭示的具体形式，而是相反，本发明覆盖落入本发明的精神和范围之内的所有修改、替换构造和等效技术方案。