Pp. 65–76 of the Proceedings

Abstract

Techniques for dynamically adding new code to a running program already exist in various operating systems, programming languages and runtime environments. Most of these systems have not found their way into common use, however, since they require programmer retraining and invalidate previous software investments. In addition, many of the systems are too high-level for performance-critical applications. This paper presents an implementation of dynamic classes for the C++ language. Dynamic classes allow run-time updates of an executing C++ program at the class level. Our implementation is a lightweight proxy class that exploits only common C++ features and can be compiled with most modern compilers. The proxy supports version updates of existing classes as well as the introduction of new classes. Our language choice and proxy implementation is targeted towards performance-critical applications such as low-level networking in which the use of C++ is already widespread.

1. Introduction

Every modern organization has software systems that are critical to its mission and must operate continuously. A network provider, for example, loses both revenue and customer goodwill if its switches or service controllers are temporarily unavailable. Because of the need for continuous operation, planned downtime is hard to schedule, and unplanned downtime can have cataclysmic effects. When a new service or security threat makes changes unavoidable, the changes are designed to minimize downtime, reducing system maintenance to repetitious patching. Such patching breaks the program?s data abstractions and encapsulation, reduces modularity and increases coupling. At the same time, ignoring needed maintenance and development leads to an outdated system, one that eventually will become an obstacle to organizational development.

Complicating the situation is that, as network computing has transformed many industries, continuous change has become just as important as continuous operation. Rapid introduction of new functionality and dynamic adaptation to volatile needs is essential. Systems, particularly telecommunications systems, must be customized on a very fine time scale, either due to user demand or to load and usage fluctuations.

An effective way to allow both continuous operation and continuous change is through dynamic code updates. New code is added to a running program without halting the program, thus introducing new functionality but avoiding downtime. The idea of adding new code to a running program dates back to the earliest electronic computers, and dynamic linking [1, 2, 3, 4, 5, 6, 7, 8] is now available for nearly all operating systems and programming languages. However, since languages such as C++ do not directly support the creation of dynamically loadable modules, preserving program-level abstractions across the dynamic-linking interface is difficult. In particular, current dynamic linkers break the type safety of C++ ⁽²⁾, since they are oriented towards functions rather than types and classes.

Recently, new environments and languages have been designed to dynamically download and execute programs [9, 10]. In particular, Java [9, 11] has become extremely popular and is in widespread use. However, although a Java class loader can lazily load the classes that make up an application, it has no knowledge of class versions and can only load each class once. In addition, the relatively poor performance of Java makes it impractical for low-level applications.

Here we propose dynamic classes. Dynamic classes allow new functionality to be introduced into an executing C++ [12] program without sacrificing type safety, performance or the object-oriented paradigm. Replacing an entire class, rather than individual functions, honors the semantic integrity of the program and minimizes interference between the update and the ongoing computation. Although comparable techniques exist in interpreted languages and agent-based environments, our objective is to use these mechanisms in telecommunication (and other) systems where performance is the primary concern. We outline a C++ proxy-based implementation that requires only existing features of the language and is usable with any complete C++ compiler.

Section 2 presents related work. Section 3 introduces dynamic classes=2E Section 4 describes our proxy-based implementation. Section 5 examines system performance. Section 6 presents several applications in which we are using dynamic classes. Sections 7 and 8 consider future work and our overall conclusions. Finally, the appendix contains psuedocode for our proxy class. The psuedocode is discussed in Section 3.

2. Related work

The idea of adding new code to a running program dates back to the earliest electronic computers, but perhaps the first structured approach can be found in the rudimentary dynamic linking of the Multics system [1]. Since then some form of dynamic linking has found its way into a wide range of programming languages, distributed-computing environments and even operating-system kernels. Since we are targeting the C++ language, we first consider various ways to add code to an executing C or C++ program, and then examine a few approaches that have been used in other languages and environments.

2.1. C and C++

Incremental linking, or runtime linking of code that was available to the compile-time linker, achieves lazy loading of the code and avoids resource allocation for code segments that are never used [13, 14]. Conceptually, however, incremental linking is identical to traditional compile-time linking.

Dynamic linking, or runtime linking of code that was not available to the compile-time linker, truly supports the introduction of new functionality into a running program [2, 3, 4, 5, 6, 7]. However, the C++ language does not directly support the creation of dynamically loadable modules, making it difficult to preserve program-level abstractions across the dynamic interface. In particular, current dynamic linkers break the type safety of C++, since they are oriented towards functions rather than classes. For example, to create an instance of a previously unknown derived class, the program must search a shared library for the desired constructor via a tedious C interface (e.g., dlfind on many systems), and then cast the resulting function pointer to the constructor type. In addition, some dynamic linkers do not allow a previously loaded code module to be replaced later unless every call into the module is made via the same tedious C interface. Even when the dynamic linker allows the relinking described in [15], there is no support for replacing a module that is in use or having multiple versions of a module coexist within the same program.

Dorward et al. [8] extend dynamic linking so that it preserves the type safety of C++ and works at the class level. Their solution allows a new derived class of a known base class to be dynamically loaded into a program. First, the shared library that contains the implementation of the new class is dynamically linked into the program. Then, a standard factory mechanism [16] is used to call into the library and create an instance of the new class (a preprocessor automatically generates the necessary factory routines). The instance is cast to the type of the base class and can be used wherever an instance of the base class is expected. Since all calls to the base class are type checked statically, and the base class constrains the derived class to have the same function signatures, type safety is preserved even though the program is actually invoking the operations of the derived class. Our implementation uses much the same mechanism to achieve type safety, but it extends Dorward?s implementation by (1) allowing the replacement of a previously loaded class with a new version and (2) allowing multiple versions of a class to coexist within the same program. In other words, our implementation adds versioning.

The techniques of Hamilton and Radia [17] and Goldstein and Sloan [18] do allow multiple versions of a class to coexist within the same program. In the Hamilton and Radia approach, the program must be recompiled to take advantage of a new version (and hence stopped and restarted). Goldstein and Sloan, on the other hand, allow the new version to be dynamically added to the running program, but their solution is meant for distributed systems in which programs communicate by passing objects to each other. Since the libraries that the programs use might be upgraded at different times, a program might receive an object for which it does not contain the corresponding library version. When this happens, the program dynamically loads the appropriate library version and directs all accesses to the received object into this library. Their solution is intended to be completely transparent and does not provide application-level control over the active version (although it could be extended to provide such control). In addition, their solution requires nontrivial compiler support and does not allow an instance of an old class version to be passed to code that was compiled against a newer class version.

2.2. Other languages and environments

Java is of particular interest due to its widespread popularity and availability. Java is an object-oriented language that is syntactically similar to C++ [9]. A Java program is made up of one or more classes. Rather than load each class into the Java virtual machine at program startup, a class loader dynamically loads each class at the time of first reference. Although the built-in class loader has no knowledge of class versions and will only load each class once, it would be possible to write a custom class loader that took versioning into account. This custom class loader might need help from (1) Java interfaces to cleanly separate interface and implementation, (2) a preprocessor to enforce a version-naming scheme, and (3) some proxy-like class. Java, however, simply does not provide sufficient performance for the low-level applications of interest. It will be worthwhile to reconsider Java once effective just-in-time compilation brings its performance closer to that of C++. If Java becomes an attractive choice for our target applications, the same dynamic-class mechanism presented in this paper could be reimplemented in Java.

The Limbo language, which is part of the Inferno system from Lucent technologies, is intended for the same type of distributed applications as Java [10]. A Limbo program consists of one or more modules. Each module consists of a public interface and a private implementation. The public interface can include functions, variables, data types and constants. These modules can be dynamically loaded, unloaded and reloaded at runtime. Although versioning support would need to be added at a higher level, this dynamic loading capability would play a large role in a dynamic-class implementation for Limbo. Like Java, however, Limbo is not in widespread use for the applications in question and does not yet provide the desired performance.

Many other languages - such as Eiffel, Lisp, Perl, Python [19], Scheme, SmallTalk [20], Standard ML and Tcl [21] - support some form of dynamic linking or loading. Depending on the language, the dynamic update can be as small as a single procedure, a single class or a single compilation unit. Unfortunately, many of these languages are interpreted and are too inefficient for performance-critical systems. None of them directly provide the necessary versioning support. Most importantly, none of them are in widespread use in our application environment.

Most agent-based environments - which include mobile-code systems [22, 23], cooperative processes [24], and intelligent interfaces [25] - allow the dynamic introduction and removal of individual process entities or agents. There is little support, however, for replacing an existing agent while preserving ongoing agent conversations. In addition, many agent systems use interpreted languages that are not efficient enough for low-level processing. Finally, due to the communication overhead in current agent systems, an application is often implemented as a few large agents rather than many small agents. These large agents are too coarse of a replacement unit for many applications. ⁽³⁾

Many distributed programming systems such as CORBA [26] and Argus [27] also allow the dynamic introduction and removal of individual processing entities. In CORBA this entity is a single process. In Argus this entity is a collection of objects and processes called a guardian. Both systems provide limited support for replacement. As in the agent case, however, a process or guardian is too coarse a replacement unit for many applications, particularly since a guardian is unavailable during the replacement process (i.e, all ongoing conversations are blocked). Bloom, however, does make the notable contribution of analyzing when it is safe to replace one implementation of a guardian with another [27], an analysis that could be applied directly to dynamic C++ classes.

Finally, Microsoft's component object model (COM) [28] allows the programmer to define components, which have an interface and a separate implementation. If the implementation changes, existing components will continue with the old implementation, while new components can use the new implementation. This approach is quite close to the approach that we use for our dynamic classes. In addition, COM is efficient enough that components can be used at the "class" level. On the other hand, COM has many additional features that we do not need; it has a longer learning-curve than our simple proxy; and it is not widely used in non-Windows applications. Like Java, however, COM will be worth revisiting as it evolves.

3. Dynamic classes

A dynamic class is a class whose implementation can be dynamically changed during program execution, allowing the introduction of new functionality at the class level. Of course, the main program must be able to communicate with (invoke the methods of) the new implementation. Thus each implementation must have an interface that is known to the main program at compile time. Each new implementation either updates an existing class (a new version) or introduces a new class (a new type) that uses the known interface.

3.1. Version Update Semantics

A basic problem when updating an existing dynamic class is what to do with existing objects. There are at least three approaches as shown in Figure 1. One approach (a) is to raise a "barrier," blocking object creation until all existing objects of older versions have expired. Then the new version takes over and object creation resumes. This approach is conceptually equivalent to halting, modifying and restarting the system. Another approach (b) is to recreate all existing objects using the new version. This approach retains a crucial property of raising a barrier, namely that at any time all objects of a particular class are of the same version. On the other hand, since different class versions can have different internal data structures, copying each object?s state requires an understanding of the object?s semantics.

Figure 1: Three approaches to version updating

The last approach (c) is not to take any action at all. All new objects are created with the new version, and existing objects continue with their current versions. Once the existing objects finish their tasks and are destroyed, only the new version will be in use. We adopt this last solution since it is the most basic, is sufficient in all the cases that we have considered, and can be implemented efficiently. However, we also include a method that an object can use to determine if its version is the most recent version, allowing the programmer to explicitly migrate objects of a particular class. The programmer would need to write state-capture and restoration routines for each class version. These routines would produce and accept version-independent representations of an object?s state.

3.2. The Interface Semantics

To allow "hot" updates, an interface monitor screens every message that passes through the dynamic class interfaces. This monitor is conceptually a class proxy. For each dynamic class, the monitor maintains a map that associates the class name with the current implementation version (and its location on external storage). A dynamic class is invalid if the running program does not contain any implementation version for that class. All dynamic classes start out as invalid. When a message is sent to an invalid class, the monitor locates and loads the current implementation version, updating the internal map as needed. The monitor then passes the message on to the newly loaded version.

The interface monitor provides three methods to manipulate the current version: activate, invalidate and activate-and-invalidate. The activate method registers a new version as the current version. Objects of older versions remain in existence. Once all old objects have expired normally, the older versions are removed from the system. The activate-and-invalidate method registers a new version as the current version but also invalidates (destroys) all objects of older versions. Conversations ⁽⁴⁾ in which these objects were engaged are broken. The surviving participants must recover and retry. The invalidate method invalidates (destroys) all objects of a given version. Invalidating the current version is an error. With these semantics, the three methods maintain the invariant that each dynamic class has a unique current version.

4. Implementation

We had three design goals for our C++ implementation of dynamic classes: (1) efficiently find and invoke the correct version of each method, (2) hide the dynamic class mechanism as much as possible from the end programmer, and (3) use only standard C++ features. The implementation should not require special preprocessor or compiler support, nor depend on compiler-specific details. These design goals led us to proxy classes=2E In this section, we first present our proxy-class implementation, and then discuss the tradeoffs involved.

The core of our implementation is a generic template class. The template, which is shown in the appendix, uses only standard C++ features and can be compiled with any complete C++ compiler. The template serves as a proxy (or smart pointer) for each dynamic class. As with any proxy, a program creates a dynamic class instance by creating a proxy instance instead.

Each dynamic class is written as two separate parts: (1) an abstract interface class that is known to the program at compile time and (2) one or more implementation classes that inherit from the interface class. There is one implementation class for each version of the dynamic class. The abstract interface class specifies the public operations that remain constant across all versions of the dynamic class. These operations are defined as pure virtual functions so that each derived implementation class is forced to provide them. In addition, although each implementation class can have any additional methods and data members that it needs to perform its task, only the operations defined in the interface class can be called from other program modules. This only makes sense since otherwise a program module might become dependent on a particular version of the dynamic class. Each implementation class is compiled into a separate shared library.

To use a dynamic class, the template is instantiated on the interface class. At run-time, the template locates the shared library that contains the most recent implementation class and loads this library into the program?s address space. The template calls into the library to create an instance of the implementation class, and casts the instance to the type of the interface class. Finally, the public interface operations are accessed through the template using standard pointer redirection.

The template also provides static methods that implement active, invalidate and activate-and-invalidate. Most software systems will provide an external interface through which an administrator, developer or automated management tool can invoke these methods.

As an example, consider a dynamic class whose job is to receive packets sent across a network connection. For simplicity, the dynamic class interface provides only a single operation.

class Receiver {

    public:

        virtual Packet receivePacket (void) =3D 0;
}

The programmer might write two implementation classes, the normal production version and later, after the discovery of an unexpected problem, a debugging version that contains new debugging code.

class ReceiverImp: public Receiver {

    public:

        Packet receivePacket (void) { ...?}
}

class ReceiverDebuggingImp: public Receiver {

    public:

        Packet receivePacket (void) {
            logDebuggingInfo(); 
        }
}

Each of these two implementation classes is compiled into its own shared library, say imp.so and debugimp.so respectively. Using the dynamic class is now straightforward (dynamic is the name of our proxy template as shown in the appendix).

// normal program operation --create and use normal packet receivers

dynamic<Receiver>::activate ("imp.so");
dynamic<Receiver> receiver;
Packet packet =3D receiver.receivePacket();
=2E..


// switch to debugging mode in response to some external event (library 
// name would be included in the external event)

dynamic<Receiver>::activate ("debugimp.so");

// now all new packet receivers will contain the debugging code

dynamic<Receiver> otherReceiver;
=2E..

Thus new debugging functionality is introduced without stopping the running program. In addition, once the bug is identified, the developer can create a third version of Receiver, one that contains the necessary fix=2E The fixed version can then be activated, again without stopping the running programming. Of course, we do not intend to suggest that all bugs can be fixed without stopping the program, but at least some bugs can be. For example, our Receiver might simply be mistranslating a particular kind of packet.

4.1. Implementation details

In our approach, the version of each object remains unchanged for the lifetime of the object. Therefore, the version mapping can be resolved during object creation and stored in the instance of the proxy. In fact, once the object is created, the needed mapping is just a single pointer to the new object (namely the object pointer that appears in the template definition in the appendix).

The medium-functionality template requires each dynamic class to have its own interface class (and thus supports version updates only). The template still maintains a version list for each dynamic class, but eliminates the class-name to version-list mapping, avoiding (1) the string lookup in the activate, invalidate, and activate_and_invalidate methods and (2) the handle lookup in the constructor. In this template, the three methods take only the library name as a parameter, and the constructor takes no arguments. The class name, which is needed to invoke the constructor, is obtained from a special function in the shared library (i.e., a static function that returns the class name as a const char *). The medium-functionality template is the most commonly used template. Its performance is discussed in Section 5.

We chose the proxy approach since the ability to use standard C++ development environments was a primary design goal. If we had been willing to sacrifice this goal, we would have had more implementation choices, most notably a custom preprocessor. A sufficiently complex preprocessor could (1) make dynamic classes look more like normal C++ classes (i.e., multiple constructors per dynamic class and method access via selection (.) rather than just deference (->)), and (2) provide better performance. A careful analysis of the tradeoffs, however, indicates that the preprocessor advantages are not as great as they first appear, and do not justify the additional complexity and development time.

class ReceiverWrapper {

     private:

       dynamic<Receiver> *receiver;

     public:

       ReceiverWrapper (void) {
         receiver =3D new dynamic<Receiver>;
       }

       ReceiveWrapper (int packetType) {
         receiver =3D new dynamic<Receiver>;
         receiver -> initialize (packetType);
       }

       Packet receivePacket (void) {
         return (receiver -> receivePacket()); 
       }
   }

typedef list<DynamicVersion*> VersionList;

typedef int Handle;

template<class T> class dynamic {

    // the actual object, its version information and its class handle

    T *object;
    DynamicVersion *dvPtr;
    Handle classHandle;

public:

    // constructors, etc.  

   dynamic(Handle handle);
   dynamic(const dynamic<T>& proxy);
  ~dynamic();

   dynamic<T>& operator=3D (const dynamic<T>& proxy);

   // smart pointer

   T *operator-> (void);

   // activate a version

   static Handle activate (const char *libraryName, const char *className =3D NULL);

   // invalidate a version

   static void invalidate (const char *libraryName, Handle handle);

   // activate and invalidate

   static Handle activate_and_invalidate (const char *libraryName, const char *className =3D NULL);

private:

   // static data (shared by all versions and classes implementing the interface <T>)

   // 1. map: handles to version list
   static VersionList **versionMap;

   // 2. map: handles to active version
   static DynamicVersion **activeMap;

   // ... more ... 
};