Abstract:
A method and apparatus for achieving a non-disruptive code load in a digital electronic device utilizes a copier that modifies itself as it executes. A fixed data section might be left unmodified to preserve a trusted system state. The copier has two parts, a bootstrapper and a dynamic part. As a minimum, the bootstrapper copies the new dynamic part into the runtime area and initiates execution of the new dynamic part. Through the dynamic part, the desired new runtime area configuration for data and code modules is achieved. The bootstrapper is typically static through upgrades, but instruction cache associated with the processor can make self-modification of even the bootstrapper more convenient.

Description:
CROSS-REFERENCES TO RELATED APPLICATIONS  
       [0001]     The present application is a continuation-in-part of, and claims benefit from, U.S. patent application Ser. No. 10/228,044, filed Aug. 27, 2002, and incorporated herein by reference in its entirety. 
     
    
     FIELD OF THE INVENTION  
       [0002]     The present invention relates to logic adapted to execution on an electronic digital device for a self-modifying copier. More particularly, it relates to a self-modifying copier used to nondisruptively load code and data into a runtime area of an active digital electronic device.  
       BACKGROUND OF THE INVENTION  
       [0003]     The field of computing technology advances at almost a lightening pace. Equipment rarely has more than a five year life. In most instances, the life is only two to three years. In some instances, it is possible to replace various pieces of the equipment. In other instances, all that is required is a modification to existing code.  
         [0004]     “Smart” devices operating under control of a digital processor today include not just traditional computer systems, but also include, for example, telephones; personal digital assistants; routers, switches, and other networking devices; media presentation, recording, and distribution systems; storage systems, databases, and data warehouses; kiosks; security monitoring equipment, devices supporting web services; space shuttles, and tractors. It is easy to imagine situations in which any of these kinds of equipment might benefit from being able to update information, including running code, on the fly nondisruptively; i.e., without interruption to active operation. We will refer to such a device operating under the control of a processor as a “system.” 
         [0005]     It is desirable to provide an apparatus and method that enables running code on such systems to be upgraded to add functionality or fix bugs without any system down time. The device would run or operate in real time and continue to process requests. A process that updates a system without requiring it to shut down is often referred to as a nondisruptive code load (NDCL).  
         [0006]     A variety of approaches to NDCL have been implemented. Christeson et al. (U.S. Pat. No. 5,579,522) teach a computer system having two update modes, normal and recovery, selectable from outside the computer&#39;s enclosure using a hardware jumper. In a normal update mode, an operating system is transferred to and caused to execute in volatile random access memory. The system&#39;s BIOS and flash memory may be used in this initialization. An update program is then executed within the operating system, providing a user with update selections to save, verify or update nonvolatile memory areas, including the system BIOS or flash memory. A recovery update mode causes a special recovery BIOS to be executed in the event that the normal BIOS has been corrupted, thereby overwriting the normal BIOS of a computer system. The normal mode of Christeson is a variety of NDCL that Gabel (U.S. Pat. No. 5,930,504) characterizes as teaching that procedures for updating a logical area within a system may reside within that same logical area; in order to avoid change or corruption during an update process if they were to remain in the affected logical area, however, those procedures are protected by copying them to a safe system memory area from which they execute the update. The recovery mode of Christeson is clearly disruptive, requiring a reboot of the system after a manual change in a hardware jumper setting. In the context of a telecommunications switching system, Nilsson et al. (U.S. Pat. No. 5,410,703) teach maintaining an old software version effectively in parallel with a new version, gradually switching traffic over to the new version. Ishii et al. (U.S. Pat. No. 5,835,761) discuss performance improvements during NDCL that can be achieved by first copying the new code version into a shadow area of fast memory.  
         [0007]     The parameters and variables required to keep the system operational must be preserved through a nondisruptive code load. The patent of O&#39;Brien et al. (U.S. Pat. No. 6,141,771) teaches copying a trusted machine state to a second portion of memory, reinitializing some portion of memory that does not include the trusted machine state, and then restoring the trusted machine state to either the original memory area or to a new memory area. O&#39;Brien et al. also allude to an alternative method of preserving a trusted machine state, one that avoids initializing the portion of memory that contains that state; no specific structure or process for reinitializing the system is described, however, for this alternative method, which is not the focus of their invention.  
       SUMMARY OF THE INVENTION  
       [0008]     The central concept of the present invention is an executable self-modifying copier, resident in runtime memory. Runtime memory is an area of a digital device from which a processor reads instructions. The word “memory” is being used generically here to include a medium to which instructions can be written and then later written over, such as random access memory or disk storage. Runtime memory might be volatile random access memory, or it could be nonvolatile firmware so that its contents will not be erased when the system is shut down and restarted. The invention applies equally to either alternative. Henceforth without loss of generality this document will describe a single area of runtime memory, while in fact a given system may have a plurality of areas of runtime memory that exploit the benefits of the invention.  
         [0009]     The runtime memory has some structure or format that the executing code requires to function properly. For example, the executing code might access within memory certain parameters or variables about the state of the system. For example, within a digital camera, a typical state variable is an aperture setting. The logic requires these variables to be found in portions of runtime memory whose locations are usually known and constant. Another example of a required format within runtime memory is the start of the code that executes when the system is initialized (i.e., rebooted). The structure of runtime memory, therefore, typically consists of a plurality of segments. Both the old version and the new version of what occupies that memory, namely the old runtime version before the update and the new runtime version afterwards, will be some combination taken from code modules, data modules, and modules that combine both code and data. The data might consist of system parameters, but in general it can be virtually anything that can be represented digitally, such as statistical data, transactional data, images, or music.  
         [0010]     In one embodiment of the invention, the new version is first loaded into a shadow area of memory. It will often be the case that the memory in the shadow area will have faster and more robust performance than some external medium, such as slow disk, containing the new code version. Thus, the preliminary shadowing operation will both shorten the process of upgrading and reduce the risk of errors. We will refer to the area from which the new version is transferred as the source area, which might be shadow memory or any other medium.  
         [0011]     If the arrangement of the segments in the runtime area is unchanging through every upgrade, then the process of copying the new version is fairly straightforward, consisting essentially of copier instructions in the runtime memory superposing segments of the new version into corresponding segments containing the old version. In other words, the copier could be static, and would typically itself occupy a code segment. The copying process in this case is not entirely trivial, however, because consideration must be given to currently executing processes, system interrupts occurring while the transfer is occurring, and so forth.  
         [0012]     If, on the other hand, the structure of the runtime area must be changed with the new version, then the upgrade process can be significantly more complicated if it is done in place, that is, by directly overwriting the runtime area. Such a structural modification might include, for example, one or more of the following: a change in the starting address of a segment; a change in the ending address of a segment; the addition of a new code or data segment; and the deletion of an existing code or data segment. The structural modification could obviously leave some segments intact, although the content (i.e., code or data) of such segments might change with the upgrade.  
         [0013]     In general, a static copier within the runtime area would not contain logic to anticipate how the segments might be rearranged in the next upgrade iteration, nor, indeed, all succeeding ones. Consequently, there is a puzzle regarding how the processor can execute code in the runtime area that effects the structural change, when the nature of the desired change is embodied only in the new version, residing in the typically nonexecutable source area.  
         [0014]     The solution employed by the present invention is for a runtime area copier module to consist of two parts: a bootstrapper and a dynamic copier part. The content of the bootstrapper will typically, but not necessarily, be static through upgrades, while the dynamic copier part has the opportunity to change from one runtime version to the next. Two essential functions of the bootstrapper are to copy the new version of the dynamic copier part into runtime memory and to cause the new dynamic copier part to begin execution. In one embodiment of the invention, the bootstrapper will have fixed start and ending addresses in the runtime area, while the dynamic part (which will be replaced and typically overwritten during the NDCL) will have a fixed start address. In some embodiments, the entire copier will reside within a runtime memory segment having fixed starting and ending addresses, with enough space available for the dynamic part of the copier to expand within the segment over a number of anticipated upgrade cycles. Instructions within the new dynamic part of the copier, once loaded into runtime memory and executed, will produce the intended runtime area structural change and load in the remainder of the new version of code and data.  
         [0015]     The content of the bootstrapper can remain static in either of two ways. One alternative is for instructions in the static copier part of runtime memory to be overwritten with identical instructions from the source region as the copier executes. This approach has an advantage of simplicity, in that the entire runtime version is overwritten. The second alternative is for the copier to only overwrite its dynamic part, which will be faster, although usually only slightly faster, than a complete overwrite. Performance of the copier can be improved by the utilization of a processor instruction cache, when available. The processor instruction cache can also facilitate changes to the bootstrapper part of the copier.  
         [0016]     In some embodiments of the invention, state information about the system is stored in a trusted system state segment that is left untouched during upgrades of the executable code. The trusted system segment will have fixed start and end addresses. In some embodiments, the copying process involves decompression, decryption, or other similar operations being applied to some or all of the information being copied. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0017]      FIG. 1  is a conceptual block diagram illustrating several elements of an embodiment of the present invention.  
         [0018]      FIG. 2  is a diagram of an exemplary structuring of memory in the runtime area and a shadow (source) area.  
         [0019]      FIG. 3  is a flowchart illustrating an embodiment of the runtime area upgrade process.  
         [0020]      FIG. 4  is a conceptual block diagram illustrating a processor having an instruction cache and a data cache.  
         [0021]      FIG. 5  is a flowchart illustrating an embodiment of the runtime area upgrade process utilizing a processor instruction cache. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0022]     The present invention provides an apparatus and method for installing executable code or data in a manner that is non-disruptive to the system, so that the system is able to continue operating without the need to sacrifice any system down time.  FIG. 1  is a conceptual block diagram showing one embodiment of the invention. The system  105  is an electronic digital device that contains a processor  108  and a runtime area  110 . The processor  108  can be a microcontroller on an integrated circuit board, a central processor of a supercomputer, or anything in between. The system  105  could be, for example, a computer, a digital camera, a portable media player, or a mobile phone. The runtime area  110  is an area of memory from within which the processor  108  can execute instructions represented in digital form (i.e., software code). The runtime area  110  is represented on a medium that is both readable and writable. The arrow labeled  190  indicates that the processor  108  has access to data and code for execution, both located in this area. This medium will be referred to as memory, although it need not be conventional volatile memory. The runtime area  110  contains at least two modules, one of which is a copier  120 . The other module could be an old code module  160 , a old data module  170 , or some combination of code and data. More typically, in addition to the copier  120 , the runtime area  110  will contain at least an old code module  160 , an old data module  170 , and a fixed content module  115 , whose content remains the same through all upgrades. The runtime area  110  might, in fact, contain a plurality of some or all of these module types. A particular example of a fixed content module  115  is a trusted system state  116 , which contains system state information and other parameters that are located in fixed, well-known locations, to ensure reliability of processing and continuity through upgrades of the system  105 .  
         [0023]     The upgrade process includes copying a new version  101  of runtime area content (hereinafter, “new version”) from a source area  111  into the runtime area  110 , replacing portions of the old version  100 , but not any fixed content modules  115 . It is well-known in the art that other steps and other components will typically be involved for a code upgrade to be done nondisruptively. The scope of the invention encompasses any such ancillary steps and components when used in combination with core concepts of the present invention.  
         [0024]     The source area  111  could be located internally within the system  105 , or it might be external. The large outer rectangle in the  FIG. 1  suggests an internal source area  111 , while a dashed line  106  suggests the alternative of an external source area  111 .  
         [0025]     The new version  101  might have a collection of modules that are in correspondence with the original modules. For example, every old code module could have a corresponding new code module, and conversely. This need not be the case, however.  FIG. 1 , for example, shows that the source area  111  has a new second code module  181 . The figure is also suggestive of some other kinds of restructuring of the content of the runtime area  110  that an upgrade might accomplish. For example, the new data module  171  has a different size from the old data module  170  (namely, larger), while the new code module  161  is smaller than its counterpart old code module  160 . The modules in the source area  111  are also arranged differently from those in the runtime area  110 , suggesting that the same might be true after the new modules have been installed into the runtime area  110 . In general, the upgrade process can result in a restructuring of the content within runtime area  110  that can qualitatively be simple or complex. Additions and deletions of modules, rearrangements of locations, and changes in module sizes are among the possible restructuring possibilities.  
         [0026]     The invention accomplishes the upgrade, including any concomitant runtime area  110  restructuring, using a self-modifying copier  120 . At the start of the upgrade process, there are two versions of the copier  120 , an old copier module  130  within the runtime area  110 , and a new copier module  131 , within the source area  111 .  
         [0027]     In the embodiment of the invention illustrated in  FIG. 1 , the old copier module  130  includes two parts, an old bootstrapper  140  and an old copier dynamic part  150 . The new copier module  131  includes a new copier dynamic part  151 . (Each “part” is actually code, so, for example, “new copier dynamic code” is an alternative term for that part.) The old bootstrapper  140  causes the new copier dynamic part  151  to be copied into the runtime area  110 , and thereafter causes the processor  108  to execute the new copier dynamic part  151 . The adaptation of logic within the old bootstrapper  140  to copying the new copier module  131 , at least the new copier dynamic part  151  but possibly also, as discussed below, the new bootstrapper  141 , is indicated by the arrow labeled  195  in  FIG. 1 .  
         [0028]     The new copier dynamic part  151  contains logic for loading the new runtime content version  101  into the runtime area  110 , including any restructuring required within the runtime area  110  to accommodate the various modules of the new version  101 . For convenience, we will exclude the new version of the copier  120  from the term new runtime content version  101 . Logic in the modules in the runtime area  110  can consequently be ignorant about how the runtime area  110  might be reconfigured during an upgrade. In effect, the old copier module  130  knows how to kick off the upgrade process and the new copier module  131 , specifically the new copier dynamic part  151 , takes over from there. In  FIG. 1 , logic in the new copier dynamic part  151  to copy and arrange the various modules of the new runtime content version  101  is suggested by arrows labeled  196 . The copying process might also accomplish one or more incidental tasks on portions of the new runtime content version  101 , including decompression, decoding, decryption, or even code assembly or compilation.  
         [0029]     The new copier module  131  might also include a new bootstrapper  141 . The fact that a new bootstrapper  141  is optional is suggested in  FIG. 1  by its enclosure within a dashed line. If it exists at all, the new bootstrapper  141  is typically identical to the old bootstrapper  140 . While overwriting the old bootstrapper  140  with an identical version of itself might seem redundant, in some situations there might be good motivation to do so stemming from hardware or software considerations. It is also conceivable that the designers of the system  105  might want to leave open the possibility of improving or fixing bugs within the old bootstrapper  140 , in which case the new bootstrapper  141  could have some differences from the old bootstrapper  140 .  
         [0030]     Referring now to  FIG. 2 , we see a simple embodiment of the concepts that were illustrated in  FIG. 1  in which the runtime area  110  and the source area  111  each consist of a respective block of memory. Here, the source area  111  is actually a shadow area into which the new runtime content version  101  has been staged (i.e., preloaded) to reduce the time required for the upgrade process. The runtime area  110  includes a runtime area copier section  210 , a runtime area code section  220 , a runtime area data section  230 . The source area  111  includes corresponding sections, specifically a source area copier section  211 , a source area code section  221 , a source area data section  231 . As their names suggest, these sections contain a copier, code, and data, respectively. The runtime area  110  contains an additional section, a fixed content section  200 . The fixed content section  200 , which can contain any kind of digital content such as code or data, remains untouched during the upgrade process. In the embodiment of  FIG. 2 , the fixed content section  200  contains a trusted system state  116 .  
         [0031]     In the embodiment illustrated by  FIG. 2 , the starting and ending memory addresses within the runtime area  110  are fixed and the sections are contiguous. Thus, for example, the runtime area code section  220  extends up to the start of the runtime area data section  230 . The old code module  160 , however, does not fully occupy the runtime area code section  220 . A code expansion area  260  remains vacant, providing limited room for the code module in the runtime area  110  to grow from one upgrade iteration to the next. Similarly, the fixed content section  200  includes a fixed content section expansion area  240 , the runtime area copier section  210  includes a copier expansion area  250 , and the runtime area data section  230  includes a data expansion area  270 . A runtime area  110  structure including segments with fixed starting and ending addresses, while not essential to the invention, is often convenient so that system  105  logic can anticipate where to find particular information regardless of upgrades.  
         [0032]     In the exemplary embodiment, the old copier module  130  is divided into an old bootstrapper  140  and an old copier dynamic part  150 . The old bootstrapper  140  has static start and end addresses, contained in memory extending up to the start of the old copier dynamic part  150 . Because, in this embodiment of the invention, the bootstrapper remains unchanged through the upgrade, the copier expansion area  250  is exclusively dedicated to potential expansion of the copier dynamic part.  
         [0033]     A few things are worthy of notice in the source area  111 . The sizes of the new copier dynamic part  151 , the new code module  161 , and the new data module  171  differ from their respective counterparts in the old runtime content version  100 . On the other hand, the new bootstrapper  141  is identical in size to the old bootstrapper  140  because it is identical in content. Each content module in the source area  111  would be copied into the runtime area  110 , beginning at the start address of the corresponding memory section there. In this configuration, the old copier module  130  would entirely overwrite itself with the new copier module  131  during the upgrade process.  
         [0034]     Even in the relatively simple embodiment shown in  FIG. 2 , the new copier dynamic part  151  might have several tasks effecting the restructuring of the runtime area  110 . As a minimum, the logic of the new copier dynamic part  151  must be aware of the format of the new version  101 , such as the starting and ending addresses of the new data module  171  within the source area  111 , so that the segments of the runtime area  110  can be appropriately populated. Another possibility is that logic executing on the processor  108  might rely upon knowledge of the ending addresses of the portions of the memory sections actually in use (or equivalently the starting addresses of the expansion areas). This information might be stored by the new copier dynamic part  151  during NDCL at previously specified locations within the trusted system state  116 .  
         [0035]      FIG. 3  is a flowchart illustrating an embodiment of the invention in which at the start  300  of the process, the new runtime content version  101  is staged  310  into a source area  111  that is a shadow area containing fast memory. In other embodiments, the source area  111  might be external to the system  105 , or might consist of a read-only medium, such as a compact disk. The processor  108  (or, more precisely, code executing on the processor) initiates  320  execution of the old copier module  130 , specifically the old bootstrapper  140 . Whether the next step, in which the old bootstrapper  140  overwrites  330  itself with a new bootstrapper  141  from the source area  111  is included depends upon embodiment, as previously discussed. In the next step  340 , the copier  120  copies the new copier dynamic part  151  into the runtime area  110  as a replacement for the old copier dynamic part  150 . Some responsibility for this task must fall on the old bootstrapper  140 , although the new copier dynamic part  151  might also participate in copying itself after it has begun executing  350 .  
         [0036]     In step  360 , which is an optional step that has been included in this particular embodiment, the copier  120  decompresses some or all of the modules of the new runtime content version  101 . Note that this step might be done at alternative locations in the flowchart. For example, the new copier module  131  might be decompressed by the old bootstrapper  140  between steps  320  and  330 . Decompression might be done all at once, or it might be done in smaller bits; for example, code might be decompressed on the fly, one instruction at a time. In fact, steps that are presented for convenience of illustration as sequential in the flowchart might actually occur together in a single step; for example, steps  360  and  370  might be carried out in combination or in parallel. In certain embodiments, some modules within the new runtime content version  101  will need decompression but not others. Analogously to decompression  360 , steps (not shown) might be added to the process for decoding or decrypting various modules of the new runtime content version  101 , with similar configuration flexibility. Of course, such secondary processes as decompression, decoding, and decryption might not be required at all in some embodiments. In step  370 , the new copier dynamic part  151 , now resident itself within the runtime area  110 , copies the remainder of the new runtime content version  101  modules from the source area  111  to the runtime area  110 , reconfiguring the runtime area  110  appropriately.  
         [0037]     The discussion so far has not addressed details regarding treatment of cache  400  that might be available to the processor  108 . A processor  108  might have instruction cache  410 , data cache  420 , or, as illustrated by  FIG. 4 , both. Physically, the cache  400  might be housed within the processor  108  itself, but could be separate. Within the conceptual framework illustrated by  FIG. 1 , the cache  400  will be within the system  105  but outside both the runtime area  110  and the source area  111 . Either cache  400  type might be implemented in one or more separate units, so when we refer to “the data cache,” we mean as many individual units of data cache as are involved within the particular context.  
         [0038]     Despite some perils for the unwary described below, the availability of instruction cache  410  offers advantages in terms of processor  108  performance and a safe area where a small piece of code such as the old bootstrapper  140  can execute. This approach allows the old bootstrapper  140  to conveniently overwrite and even modify itself during the upgrade.  
         [0039]      FIG. 5  is a flowchart illustrating the interplay between the instruction cache  410 , the data cache  420 , and the runtime area  110  during copying of the new bootstrapper  141  and the new copier dynamic part  151 .  FIG. 5  in effect adds cache-specific implementation details to  FIG. 3 , which also pertains to configurations in which cache is either not present or has been disabled.  
         [0040]     The availability, types, and implementation of cache  400  tend to be specific to a family of processors  108 , or even to a single processor  108  model.  FIG. 5  assumes that the processor  108  has both instruction cache  410  and data cache  420  enabled, but variants of  FIG. 5  for which either type is not present are straightforward and within the scope of the invention.  
         [0041]     The process starts  500  with the new version being staged  510  into a source area  111 , which in this embodiment is a shadow area within fast memory to improve performance. In step  515 , the old bootstrapper  140  is placed within instruction cache  410 . This can be done manually by loading and locking the instruction cache  410 , or automatically if the system  105  provides a command to cause the processor  108  to do so according to algorithms of the processor  108 . The old bootstrapper  140  within the instruction cache  410  will typically be an instruction loop adapted to copying the new bootstrapper  141  and the new copier dynamic part  151  from the source area  111  into the runtime area  110 . Execution of the old bootstrapper  140  is initiated in step  520 . In addition to better processor  108  performance, having the old bootstrapper  140  within the instruction cache  410  in effect allows the bootstrapper to be conveniently modified as it overwrites  530  the runtime area  110  copy of itself. Next, the old copier dynamic part  150  is replaced  540  by the new copier dynamic part  151  by being partly or wholly overwritten.  
         [0042]     Because the copier  120  is self-modifying code, the distinction between “data” and “instructions” is obscured. Because processors  108  are often configured under the assumption that they will not be overwriting their own instruction set, many processors  108  will behave as if the new version  101  being copied from the source area  111  is data, not instructions. Unless the data cache  420  has been disabled (which may be preferable), the processor  108  might copy at least some portion of the new version  101  into its data cache  420  for faster availability of the “data”. Code in the data cache  420  is not in the runtime area  110 , where it is needed for completion of the upgrade. Flushing  545  the data cache  420  fixes this problem, returning the instructions contained therein to the memory of the runtime area  110 .  
         [0043]     Because the instruction cache  410  still contains the old bootstrapper  140 , a command is issued to invalidate  547  the contents of the instruction cache  410 , which forces the processor  108  to fetch its instructions from runtime area  110  memory, hence refreshing itself and initiating execution of the new copier dynamic part  151 . The system  105  typically provides specific assembly level instructions for operations such as loading and invalidating the instruction cache  410  and for disabling and flushing the data cache  420 . As in  FIG. 3  the step  560  of decompressing some or all of the information being transferred from the source area  111  to the runtime area  110  is optional. Other similar operations, such as decryption, decoding, compression, encryption, or encoding can also be done optionally. Finally, the new copier dynamic part  151  completes the copying and rearrangement of the runtime area  110 , while keeping the fixed content section  200  intact.  
         [0044]     The present invention is not limited to all the above details, as modifications and variations may be made without departing from the intent or scope of the invention. For example, the functionality of the tracking camera could be split between two cameras, one dedicated to viewing presets and the other to tracking movement of a presenter, without departing from the central concept of integrating preset sensing zones with tracking away from those zones. As another example, other forms of devices might be used to configure a controller. Consequently, the invention should be limited only by the following claims and equivalent constructions.