Zen and the Art of Dynamic Linking

Dennis L. Mumaugh

Context:

This paper was originally written as a tutorial for engineers interested in building a "plug and play" system on a Real Time Embedded system.  It is a summary of the state of the art. (as of 1995)

Forces:

We assume a large system board with adequate memory. We also assume a CPU such as a Motorola 68060 or a Power PC. In the general context there is a Real Time Operating System (RTOS) such as VXworks or Chorus.

Solutions:

1. List the places (phases) in its life that a "component" can be "constructed." (This is linking and binding).
• Images: Some time before, an "off line" image for each processor/board is built and made ready to down load. [This is the usual method for most embedded systems].
• Load time: The binding (collection of modules and linking of them together) is done at the time the "component" is down-loaded to the processor/board. This is a lot like the way UNIX for the 3B2 Systems did its auto configuration boot].
• Run-time: The "component" is linked after it is loaded into the processor/board. [This is the shared library concept of SVR3].
• Execution time: The "component" is loaded onto the board, execution of the [task] is started and the binding is done as the task makes references to "external" areas. [This is the shared object concept of SVR4 also know as Dynamic Run Time Linking.]
• Demand loading: The "system" needs a module/component. Some how it tells the external system that it needs it, and it is "loaded" in and executed. [This the standard UNIX application concept. Or Java dynamic loading of class libraries.] Linking can either be at down load, or after loading.
2. What is run-time linking vs. dynamic run-time linking?
• In run-time linking, the component is loaded into memory and the other [external] shared library components are connected before execution.
• In Dynamic Run-time Linking no binding is done for external references to the shared object until the component tries to access the reference. [Lazy binding]. [ The excellent Description of the SGI (and SVR4) version of dynamic run-time linking was provided by Mary Fernandez of Bell Labs].
• A related form of linking at run-time is the system for making changes in running systems variously called "software update" or "quick fix".  This is usually initiated by an external agent and can be located on another system.
3. List the various methods that have been used over the years to accomplish "plug and play". (Generally task loading, driver loading, 5ESS software update, etc.)
• Overlay both Basic and Unix 7th version had the ability to overlay an application. Both replaced the text of the process and left the data segment untouched. For Unix it was called 405 executables as executables with this property were tagged with the value of 0405 as the first 16-bit word of the file.
  
• Loadable drivers Used by RT-11/DOS-11/RSX-11 for the PDP-11. The driver was a self-contained Position Independent Module with a special header called a Driver Control Block . All references to the driver were through DCB entries that were relative addresses to entry points in the driver. Similarly all external references were indirect through a pointer in the DCB. The O/S patched the necessary information into the DCB which was the first part of the driver.
• UNIX Auto-config (AT&T System V) Used by the AT&T 3B2/15 UNIX. In this version a boot loader was loaded. It looked at the Equipped Device Table (EDT) and the System Configuration file (/etc/system). Together this lists the desired configuration of the system. The boot loader looked in a well known place for the objects. They were linked together into the main memory. The relocatable objects were selected from those in the directory and those not mentioned in the configuration information were ignored. After the link was done the boot loader transferred control to the program it had build. A second program looks at the internal configuration of a running system and builds an absolute image for subsequent boot (to save the linking time).
• UNIX Auto-config (4.3 BSD) The boot loader probes the I/O page of the address space. The DEC computers have well known addresses for device registers and well known and consistent layouts. One register provides the type of peripheral (Tape, Disk, etc.), the abilities (Fixed or removable) and an ID type. The loader can then load and bind the appropriate drivers.
• Shared libraries A SVR3 feature for allowing programs to have common libraries. In SVR3 for shared libraries the component [a program] was already link edited with "references" to areas of the shared library. After the component was loaded, the O/S [UNIX] mapped into the component's address space the shared library(s). It used the same mechanism that was used for shared text. Both the component and the shared library(s) were previously linked and the addresses of both the component and the library were assigned and bound previous to load time. All the O/S did was to load the library (if needed) and adjust the address space to map the library in. Only two or three shared libraries were supported and had specific segment addresses. This feature depends on contiguous memory segments and swapping. It was supplanted by the more generic Shared Object and virtual memory systems.
• Shared objects A SVR4 and Sun feature for allowing programs to link to common libraries only if they need to use the functions. It is used to implement Dynamic Run-time Linking. The external references to the shared object are intercepted by a part of the component [although it could have been an O/S service] and the library mapped into memory using mmap(2). Since the memory addresses are not previously assigned, the Run Time linker needs to map into memory the library/object, locate and link the references. This is deferred until the component attempts to access the reference. Function calls are intercepted through a transfer vector and routed to the appropriate entry point. In some version, the component reference is "back patched" to avoid the transfer vector the next time. This feature is used by all Sun O/S systems and also System V Release 4. It needs compiler support as the shared object must be a Position Independent Code object, and a global object table (GOT) must be maintained to track references to external data (vs. functions). [The excellent Description of the SGI (and SVR4) version of dynamic run-time linking was provided by Mary Fernandez of Bell Labs.]
• Debugger and patches Many debuggers allow patching of the code. A scratch area is made available. The debugger removes the "offending" instructions and replaces them with jump instructions into the patch area where the new code is placed. This can be used extensively. Some modules are built with space allocated for patches. Patches can and are made in the patches. In some debuggers, an new image of the program can be created with the patches in place. After time, the term spaghetti code takes on a new meaning.
• 5ESS® Software Update This is the fun one. I need to provide details {do not look at the man behind the curtain!} A Transfer Vector is used to provide all references between modules. The module is loaded into some free memory. The transfer vector is changed to point to the new module. After some time the old module is removed from memory and the space re-used. [Note AT&T/Lucent has a patent on Software Update].
• Quick fix The software module to be changed is loaded into patch space using a CORBA routine. The entry point of the old function is overlaid (using an atomic write) with a unconditional jump to the patched code. This requires special software to compare the software patched image with the image of the running system and extract differences. The patch then must be linked with the symbol table of the running image. A small CORBA skeleton in the running system is able to load the data into the previously defined patch space and make the change to cause the patch routine to be used.
4. List the technical constraints needed to accomplish the goal of "plug and play". (Position independent code, external references, transfer vectors, restricted symbol tables).
• Absolute Code All references in the code module are "absolute". This works if the O/S and computer architecture can use a "virtual" address space.
• Position Independent Code This is code that is independent of where in memory it is loaded. All data and program references are some how relative to the start of the code module. In most modern computer architectures the PIC is "program counter" relative. In older systems the addressing is on a Base/Offset model and the base register is some how loaded at the same time as the model [IBM 360/370 did this]. The only problem with PIC is how to access addresses outside of the module.
• Transfer Vectors All addresses outside of the module are indirect through a Transfer Vector (TV). The O/S (or somebody) loads the TV with the addresses of data and functions. The TV offsets must be cast in stone.
• Restricted Symbol Tables One can build a object module with only a symbol table. The component is linked with this module thus producing either PIC or absolute modules. These can then be loaded as desired. The hazard is that the fake module must contain addresses that are cast in stone.
• Equipped Device Table (EDT) Used by the 3B2 to specify hardware the computer was equipped with. At boot time (or with a standalone utility) the back plane was probed and the boards installed identified and the equipage was loaded into NVRAM as the EDT
• Global Object Table (GOT) In Dynamic Run Time linking, a table containing all external references to data. The compiler/assemble made all data references through this table. During run-time linking this table was initialized by the Run-time linker to the values of externals.
• Driver Control Block (DCB) A block of data is prepended to the driver code. It contains the offset from the beginning of the driver for each [mandatory] entry point, other O/S nonsense and words that the O/S fills with pointers to system tables and control blocks. All communication between the driver and the O/S goes through this DCB.
• Contiguous Text and Data Space A major code section usually references literals and strings in addition to local variables. These must be located and referenced at use time. The safest way to accomplish this is to include literals and strings into the .text segment of the object file. Similarly there is need to reference static data and also global static data. While static data is not a major problem, global static data is because the remainder of the code has no knowledge of the new data.
5. Look at possible areas where research is needed before we can think about proposing solutions.
• C++ Issues C++ supports virtual functions, overloading, templates, and dynamic (run-time) initialization of objects. Will these impact the problem?

---

©2006 Dennis L. Mumaugh
Author: Dennis L. Mumaugh
Document: http://condor.depaul.edu/~dmumaugh/zen-dynamic-linking.html
Last Updated: 21 May 2006.