Using Prolog in Windows NT Network Configuration

David Hovel

Microsoft Research
Microsoft Corporation

Abstract

Microsoft's Windows NT operating system uses an embedded Prolog interpreter to configure its local and wide-area network systems. Interdependent software and hardware components are abstracted into a simplified object-oriented framework using declarative information provided by each component's installation script. This information, along with the Prolog algorithm, is consulted into the embedded interpreter, which is then queried to construct the most usable configuration. The algorithm which solves the plumbing problem is described, including its positive and negative constraints, Prolog database and efficiency considerations. The results of the query, stored into NT's configuration database, inform each component of its load order and binding targets. A description of theC++ wrapper class is given and portation considerations are discussed. The Small Prolog interpreter is briefly described.

1. Overview

1.1 Windows NT

Microsoft Windows NT is a completely new software architecture which corrects many of the limitations of past operating systems. It is a fully 32-bit virtual memory operating system which supports multiprogramming and symmetric multiprocessing. It has a built-in graphical subsystem which is compatible with Windows 3.1.

Windows NT was built from the start as a highly extensible platform for both client and server networking. Fully two years before its initial release, developers at Microsoft were developing NT on NT systems which supported multiple network cards and protocol stacks.

1.2 Problems in Network Configuration

Although many systems support networking, there is no standard approach or tool set. Network configuration information on most systems is stored in a set text files with different syntaxes and relationships. Many systems still require relinking or regeneration of operating system binaries in order to change the network software ensemble.

Historically, networking systems have commonly suffered from three wide-spread problems. First, there was no system-pervasive configuration managementsoftware which could be used as a foundation. In MS-DOS, for example, every installer was required to have its own parsers for CONFIG.SYS and AUTOEXEC.BAT. This often meant that trivial formatting changes or unusual data could cause product installations to fail in catastrophic ways. Even simple changes in the order of component installation could result in situations which the vendors software was not designed to handle.

Second, there was no standard repository for network configuration information. Even experienced systems administrators were often uncertain as to which text files were required by the network and which components utilized them.

Third, the network components themselves were interconnected through proprietary software interfaces. Hence, components built by separate vendors could not generally be connected or bound even if their roles in the network software ensemble were inherently compatible.

1.3 Configuring Networks on Windows NT

1.3.1 Network Enhancements in Windows NT

Many of the main stumbling blocks to intelligent network configuration systems in the past are absent in Windows NT, at least in principle:

By comparison with other networking platforms, NT presents a highly normalized and well-behaved interface centered around its configuration database called the Registry. Given a correct Registry, the system runs correctly.

1.3.2 The Centralized Approach

In Windows NT, we decided that there could only be one central algorithm for network configuration. This led to the formulation of a declarative approach, in which vendors had a rich set of declarative information which could be added to the configuration database by their products. However, the final configuration was always generated and stored by the NT network configuration software.

In this architecture, the user would have the opportunity to rescind decisions made by the network configuration software, but neither the user nor vendor software could coerce the system into invalid configurations.

1.3.3 The Goals of Network Configuration

The overall goals of network configuration were:

To achieve a high degree of user acceptance, the planned implementation approach was all-encompassing. In one pass, the network configuration software would be required to:

Equally importantly, the system was supposed to do as little interaction with the user as possible. To the best of my knowledge, no previous networking system has ever been installed in this fashion before.

2. Plumbing the Network Lattice

2.1 The Network Lattice

An ensemble of active networking software components in a computer is best understood as a lattice. The vertices or nodes of the lattice are the components themselves; the edges or arcs are dataflow paths between the components. The arcs are considered to be directed from the service requester to the service provider. In a well-behaved system, there are no dataflow cycles, and all communications between two components is considered to travel along the same edge or arc. Similarly, if component A is connected to B and B is connected to C, any communications between A and C is considered to flow through B.

Figure 1: An Example Network Lattice

The lattice is considered to be oriented from the user downwards; the uppermost nodes are the originators of network traffic and the lowest nodes are those connecting directly to the hardware.

2.2 Plumbing and the NT Namespace

Setting up this lattice is often referred to as plumbing. The basic result of a plumbing algorithm is a set of ordered pairs of component tokens; each such pair indicates the existence of an arc from the first component to the second. Data flow along this arc is considered to be bi-directional.

In Windows NT, as in the members of the Unixi family, the concept of a file has been extended to include any data source or sink. As in Unix, NT maintains names for all such files in a global namespace organized as a tree, and they are accessed using the system openfunction in the same manner as disk files.

Therefore, each ordered pair previously mentioned is really a triple: the final element is the name of the file or port to be created and opened. This triple constitutes an instruction to the higher component to open a connection to the lower component using the given name, as well as an instruction to the lower component to provide an access port of the name required.

2.3 Load Ordering and Grouping

The NT Registry also contains information about load ordering and grouping of components; this allows diverse and unrelated elements of the system to initiate and stabilize their operations in the correct sequence.

The solution to the plumbing problem is used to determine the loading sequence of the network modules. If component A must open a file or port created by component B, then B must complete its loading and initialization operations before A is loaded.

2.4 Decorating the Paths Through the Lattice

From the point of view of a system component, the results of a lattice construction algorithm is a set of device names and relationships for each component. The constructed lattice can be viewed as having been labeled or decorated with generated names which enable the necessary dataflow paths.

In this context, a path is defined as a complete routing from an initiating component downward through the lattice to a network adapter card or other end-point. Product loading requirements and ordering are determined by the topological relationships inherent in the complete set of all constructed paths.

2.5 Object-Oriented Configuration Design

NT was intended from the outset to be a scaleable architecture. Older PC-based networking systems were predicated on simplistic assumptions about the number of network cards or protocol stacks which any one machine might employ. Such restrictions were not viable for NT.

In systems employing several protocol stacks, network cards and serial ports, components of a similar type are treated virtually identically. While the exact details of their addressing might vary, their participation in the network lattice is determined solely by the component type.

Elements of object-oriented design were adopted to exploit this type-versus-instance analogy. In this scheme, there is a global space of named interface classes. A class may be basic(that is, have no parent class), or it may inherit from one or more parent classes. A component type is defined by the class names describing its upper and lower boundaries. In addition, a class may be marked as a logical end-point, which means it acts as a terminal point for interconnections in the lattice. A network adapter card is always considered a logical end-point.

Instances of classes can be bound to one another in the sense that an interconnection can legitimately be made between them. There is a close analogy between this approach and class compatibility in common object-oriented programming languages. For example, if two classes aClass and bClass are declared in Prolog as bindable(aClass,bClass), then instances of aClass can be bound to instances of bClass, but not the reverse. In addition, instances of their subclasses can also be bound together, but not instances of their superclasses. In the case of multiple inheritance, instances of such classes inherit the bindablity of every superclass.

2.6 Object Model

At a deeper level, the object-oriented class descriptions do not describe networking components themselves; instead, they describe the interfaces they offer to other components.

In the configuration model, each network component is abstracted as a black box with an upper and a lower boundary or interface. Most types of objects have the same class interface at both boundaries. However, there are occasions on which it is necessary to consider the upper and lower layers of an object as having distinct properties.

Figure 2: Basic Component Object Model

The definition of a network component type, then, requires the declaration of the interface classes to which its upper and lower layers belong. It is important to remember that these semantic or behavioral interface classes are defined on top of the NDIS and TDI syntactic or general interface standards.

2.7 Overview of the Algorithm

The lattice plumbing algorithm must first determine all possible hierarchical relationships between pairs of components. Then it has to eliminate those pairs which do not eventually connect to a network adapter card or other end-point. To accomplish this, the algorithm has to be given the following information.

Given these rules, all dataflow paths can be determined, and the lattice can be constructed and decorated.

3.Choosing Prolog

To solve the lattice construction problem, I decided to use a public domain Prolog interpreter called Small Prolog (SProlog). This section attempts to recapitulate my decision-making process.

3.1 Viewing the Problem as Declarative

Under the assumption that there needed to be a central lattice generation algorithm, the problem could be viewed as declarative. In such an approach, each individual component is responsible for declaring the classes, types and products it adds to the ensemble. During network configuration, the Prolog interpreter is given these declarations in the form of base clauses. Base clauses are clauses with no unbound variables or functors; clauses of this kind are referred to as factsi n this document. The interpreter is then asked to produce a correctly plumbed or connected lattice.

3.2 Experience with Small Prolog

Before joining Microsoft I was involved in a project to build intelligent applications for the legal profession. The primary prototype for this project was developed in the Think C object-oriented graphical applications framework on the Macintosh; at its core was a ported version of SProlog. Running SProlog in such an environment gave clear experiential evidence of its stability and behavior.

Another issue clearly in its favor is that the interpreteruses a simplified syntax similar to that of LISP; this format made SProlog clauses very easy to generate and process using recursive descent.

3.3 Prototyping

A primary advantage to using Prolog was that a console or character-mode version of the interpreter could immediately be used to experiment with lattice generation algorithms. Tests could start using simple, hand-written clauses and work outward, validating concepts and justifying assumptions.

During the course of the project there were several occasions when the Prolog algorithm had to be enhanced. On each of these occasions, changes were developed and tested in console mode; when completed, the network configuration dynamic-link library was simply relinked with an updated Prolog text program. This ability to perform continual prototyping within a stable application was greatly beneficial.

3.4 Search Space Management

The design for solving the bindings problem was strongly influenced by previous experience with Prolog. It seemed to decompose readily into a series of backtrack operations across a bounded search space. Solving such a problem in a procedural language like C++ seemed unnatural, since it would require numerous new classes and functions for database management, backtracking and unification.

3.5 Introduction to SProlog

3.5.1 Origin

The Small Prolog interpreter was written by Henri de Feraudy and placed into the public domain. It is written in standard (K&R) C and was ported to several platforms by M. de Feraudy during development.

3.5.2 Syntax

SProlog uses a simplified LISP-like syntax for efficiency reasons. For example, here is the standard member/2 predicate:

/* membership in a list */
((member X (X|Y))
)
((member X (A|B))
(member X B)
)

3.5.3 Advantages

3.5.3.1 Size and Portability

SProlog is very small and quite portable. Virtually all machine-specific coding was isolated to a single source module, and makefilesfor several compilers and platforms were included with the source.

Since M. de Feraudy had already considered some of the issues involved in embedding the interpreter, the outer query loop was structured so that it could be readily replaced.

3.5.3.2 Memory Usage

In SProlog, all memory allocation is performed in one module. The various different dynamic areas (heap, stack, trail, etc.) are given zones in which to grow; the size, behavior and placement of these zones are controlled through a single, platform-specific source module. Memory within each zone has to be contiguous. This simplistic approach prevents backtracking from entailing extensive run-time heap manipulation.

3.5.3.3 List and String Handling

The lattice generation algorithm was necessarily going to require the maintenance of many lists and would perform extensive string manipulation to generate the final Registry results. The flexibility of Prologs built-in list handling simplified lattice path management. SProlog also has a useful set of string manipulation primitives, to which were added several built-in predicates to facilitate case shifting and string parsing.

3.5.4 Limitations

The version of SProlog which was used does not support tail recursion elimination or garbage collection.

The absence of garbage collection was not a primary concern since the lattice generation algorithm ran only once during network reconfiguration. Being a virtual memory operating system, NT had no problems supporting the full contingent of memory required for the worst-case scenarios. Similarly, the absence of tail recursion elimination, while a minor performance consideration, did not affect run-time memory use or performance significantly.

4. The Lattice Generation Algorithm

4.1 Background

4.1.1 The Configuration Registry

The NT Configuration Registry is a hierarchical database similar to a directory tree. In the Registry, each key or named location can contain values or deeper keys. Each value entry has a name, a data type and a data block. Most Registry information is either character strings or integers. All persistent configuration information is recorded in the Configuration Registry.

4.1.2 Network Configuration Information

Information related to the network configuration is stored entirely in the configuration Registry. This information can be divided into two broad categories:

The latter type of information governs the behavior of the lattice construction algorithm. As will be explained later, much of it is converted to SProlog declarative facts or base clauses.

4.1.3 Steps in the Installation Process

The large-scale operations performed by the network installation software are:

  1. Detect or choose a network card and run its installation script.
  2. Run the installation scripts for the default software components
  3. Allow the user to pick additional products to install (scripts to run)
  4. Gather the network-related Registry information and convert it to SProlog format.
  5. Run the binding algorithm to generate a correct lattice.
  6. Convert the query results to Registry format.
  7. Update the Registry to reflect the new lattice.
  8. Allow the user to rescind any bindings which are inappropriate or unnecessary.
  9. Perform a topological sort based upon the revised (active) lattice and update the Registry with the load order information.
  10. Start the network by loading the network redirector.

The steps 4, 5 and 6 above are those which involve the embedded Prolog engine and its interfaces. Given a correct lattice and software loading order, the last step suffices to cause the entire network ensemble to be loaded and initiated correctly.

4.2 Basic Algorithm

The fundamental Prolog algorithm is straightforward. First, the lattice construction program is consulted. Then the Registrys network configuration information is converted into a textual block of Prolog facts and consulted.

The algorithm then backtracks across every possible pair of device interfaces and determines if they are bindable. Those which succeed are asserted as facts into the interpreters database. The discovered set of possible bindings is then examined, and any bindings which violate constraints are retracted. (See the appendix Basic Binding Backtrack Algorithmfor more information.)

Finally, the set is converted into usable binding information; that is, the actual device names to be used in the NT namespace are constructed and topological information about the exact path through the network lattice is generated.

(Note: The full details of the generation of binding names is beyond the scope of this document.)

4.3 Constraints

There are several ways in which the construction of the lattice can be constrained.

Binding information which is found to violate a constraint or which loses a contention resolution arbitration is retracted.

4.4 Binding Names and Paths

Once a correct lattice is generated, a corresponding set of device or file names is generated. These names are based upon strings declared in the component configuration information.

Along with these names, the exact path of each binding down through the network lattice is preserved in a list of component tokens stored with each individual binding fact. This information is used by the calling program to perform a topological sort as part of the process of generating the correct network component loading sequence.

4.5 Converted Fact Predicates

This section documents the Prolog predicates into which the information in the Configuration Registry is converted. All of these predicates are base clauses, since no uninstantiated variables are allowed into or generated by the Registry conversion process.

4.5.1 devClass/3

devClass(className,parentClassName,logicalEndPoint).

This fact declares that a class exists, and declares its parent class or uses the token basic to indicate that it has no parent. A final token of yes or no indicates whether the class is a logical end-point or terminus for the binding search. Multiple devClass facts are used to indicate multiple inheritance..

4.5.2 devType/4

devType(productName,productGenericType,upperClass,lowerClass).

This fact declares that a product type exists, but may not necessarily be present or active. Each boundary (upper and lower) of the product can be declared to be of a different class. The Registry fact conversion software defaults both boundaries to be the same if only one is specified.

4.5.3 present/4

present(productId,productName,"objectName","Registry Key Name").

This fact declares that an instance of a product type exists and tells where it is located in the Registry.

4.5.4 bindable/5

bindable(fromClass,toClass,exclusive,exclusive,bindValue).

This fact declares that instances of fromClass can bind to instances of toClass. The Boolean exclusive tokens are used to indicate whether the upper or lower layer can only be bound multiply or only once.

The bindValue token is a number from 0 to 100. Multiple applicable binding rules are resolved as follows. The rule with the highest binding value is used in preference to all others. Then, the rule closest to the binder's true class is used in preference to rules based on parent classes. Finally, multiple specific rules are order-dependent; the first found is the one used.

4.5.5 devBind/5

devBind(productName,objectName,getsBindings,appearsInBindings, namingMethod).

This fact is used to control the generation of names in the NT namespace. The arguments indicate the following:

objectName: This is a string value used as the basis for names generated for this product (contrasted to the tokenized name used inside the interpreter).

getsBindings: This Boolean value determines whether or not a product's Registry area is actually updated with binding information.

appearsInBindings: This Boolean value determines whether or not a product's name is inserted into the generated name. Some layers of a protocol ensemble can be "invisible".

namingMethod: The NT driver architecture allows drivers to create containers (or directories) in the NT name space; if a driver supports this, backslashes are used to separate product level names; otherwise, they are simply concatenated using underscores to create unique names.

4.5.6 block/2

block(fromClass,toClass).

This fact indicates a constraint which prevents any path from being created which connects, however distantly, an instance of fromClass to an instance of toClass. Normal rules of inheritance apply. Note that this is an ordered pair and therefore would not in and of itself prevent a binding in the opposite direction.

4.6 Using the Facts: A Simple Binding Example

The following figure represents two components, one called redir and the other called proto1. They are defined by their devType facts (shown) and their present facts (not shown).

Figure 3: Binding Two Components

The arc connecting redir to proto1 would be instantiated by the binding algorithm because backtracking across all possible component pairs would present the list [redir proto1], and backtracking across all bindable facts would yield the rule which directly permitted binding between the lower interface of redir and the upper interface of proto1.

The search for applicable bindable facts also entails searching the set of classes since interface classes inherit bindability from their parents.

4.7 Gathering and Converting the Facts

The configuration information for each networking product is stored under two distinct keys in the Registry.

The conversion software enumerates the software and hardware products stored under the product registration keys. Components which are part of the network ensemble are identified by a subkey named NetRules. A typical set of entries under a NetRules key is:

type = srv lmNetService lanmanServer class = "lanmanServer lmNetService" use = service yes yes bindform = "LanmanServer" yes yes container

The generated SProlog facts from these values are:

(devType srv service lmNetService lanmanServer) (devBind srv "LanmanServer" yes yes container) (devClass lanmanServer lmNetService no) (present srv srv "LanmanServer" "Machine\SOFTWARE\Microsoft\LanmanServer")

The NetRules values are thus converted into SProlog facts. This conversion is performed in C++, and the tokens are coerced into valid Prolog tokens. The declarations are then reorganized for the convenience of the Prolog algorithm. (A complete listing of the facts for a standard machine is given in the appendix Sample Fact Set.)

It is important to note that the space of declarative facts is global. It is the responsibility of each vendor to guarantee the uniqueness of tokens used in the facts. In addition, each component can, if desired, add any number of uninspected Prolog predicates to extend the fact set.

4.8 Consultation and Querying

After the Registry information is converted to SProlog form, the memory areas for the interpreter are allocated and it is initialized. The textual Prolog algorithm is extracted from the executable file and consulted. Finally, the block of strings of converted Registry facts is consulted.

When SProlog has all the necessary clauses in its database, a single predicate makebindstrings/1 is queried. This predicate uses failure-driven loops to backtrack across every ordered pair of installed components to find all possible component bindings.

As each pair is retrieved, the classes to which the lower layer of the first object and the upper layer of the second belong are backtracked over in an attempt to discover a direct or inherited bindable rule.

After that, the query bindstring/6 is issued by the calling program once for each product in the ensemble of network components. This predicate is defined as:

    bindstring(Owner,Interface,ObjectName,AtomList,
                    BindString,ExportString).

This query may result in zero or more replies, all of which are stored into the output query result string. The Owner variable is the token name of the device instance. The AtomList variable is bound to a list of tokens representing the complete path of the binding down to the hardware adapter or logical end-point. This information is used by the outer-level C++ code to perform a topological sort to derive the loading sequence. The other arguments are bound to strings which are used to update the Registry.

4.9 Handling Identical Instances

There are many configurations where several devices are present with exactly the same declaration, differing only in the specific instance name. The most obvious case of this in Windows NT is theRemote Access Services, which can support hundreds of serial interface connections. Since the lattice generation algorithm will always generate the same results for these identical instances, backtracking is used to create sets of such indistinguishable objects. When found, the actual instances are hidden (by retraction and storage into ancillary clauses) and replaced by one pseudo-instance for each set.

When the binding discovery and constraint satisfaction phases are complete, the results involving the pseudo-instances are used as templates to generate the actual results for all the identical instances. All information pertaining to the pseudo-instances is then discarded.

In spite of the additional complexity, this approach yields a significant performance improvement for the overall algorithm. Instead of being O(n**2) in the number of components, the algorithm becomes O(n**2) in the number of distinct types of components. The final additional phase of generating information from the templates is linear in the number of actual instances.

4.10 Constraints

After all the potentially allowable bindings are discovered, the constraints must be considered. The first of these is the exclusivity constraint. This is a point-to-point constraint which disallows more than one binding between certain interfaces. Although there is a simple contention resolution scheme (a number from 0 to 100), it is rarely used since it does not allow the user to override it.

The other significant constraint is represented by the block clause, which disallows instances of two classes or their subclasses from occurring anywhere along a binding path, regardless of separation. This is quite a flexible and powerful rule, but causes a significant efficiency problem, since each element in a dataflow path must be checked against every other subsequent element in the path.

4.11 Generating the Results

After all the constrained bindings are retracted, the information is prepared for use by the calling program. This involves two basic steps. The namespace names are used by the calling program to update the Registry. Here is an example which uses the Microsoft NETBEUI protocol component Nbf and the file server component LanmanServer in an ensemble with three network cards, two Etherlink IIs and an IBM Token Ring card.
KEY = Services\LanmanServer\Linkage
    Bind   = "\Device\Nbf_ElnkII1"
             "\Device\Nbf_ElnkII2"
             "\Device\Nbf_IbmTok1"
    Export = "\Device\LanmanServer\Nbf_ElnkII1"
             "\Device\LanmanServer\Nbf_ElnkII2"
             "\Device\LanmanServer\Nbf_IbmTok1"
    Route  = "Nbf ElnkIISys ElnkII1"
             "Nbf ElnkIISys ElnkII2"
             "Nbf IbmtokSys IbmTok1"
KEY = Services\Nbf\Linkage
    Bind   = "\Device\ElnkII1"
             "\Device\ElnkII2"
             "\Device\IbmTok1"
    Export = "\Device\Nbf_ElnkII1"
             "\Device\Nbf_ElnkII2"
             "\Device\Nbf_IbmTok1"
    Route  = "ElnkIISys ElnkII1"
             "ElnkIISys ElnkII2"
             "IbmtokSys IbmTok1"

The Bind subkey contains an array of names to which the network component services are to connect; the Export subkey contains names which the services are to create as access points for higher level software.

The Route information enumerates the component tokens which constitute the exact path through the network lattice. These lists are used by the calling program to topologically sort the network objects to determine correct load ordering.

4.12 User Review

Once the lattice generation algorithm has been run, the Registry is updated accordingly. At this point, the user has the option of calling up a dialog and reviewing all the generated binding information. The Registry is updated again afterwards if the user has rescinded or reordered any bindings. The load order is also checked again, since the user may have rescinded all the bindings to a particular component and hence rendered it unnecessary.

4.13 Additional Issues

4.13.1 Non-Determinism

Although the fundamental algorithm was non-deterministic in the Prolog sense, care had to be taken that subordinate backtracking clauses did not unexpectedly yield multiple solutions. This issue demanded a testing discipline in which all new clauses were unit-tested for proper behavior using full-blown configuration scenarios.

4.13.2 Backtrack Ordering

When the sub-clauses in a clause must backtrack across several different segments of the database, ordering them properly can result in significant overall performance improvement. The operations should typically be ordered according to likelihood or frequency of success, from least to most.

5. Embedding Small Prolog

5.1 The Network Configuration Executable

The actual network configuration program is a Win32 dynamic-link library called NCPA.CPL. The extension CPL indicates that it is a Windows NT Control Panel extension (or applet). It is represented in the Control Panels main window by an icon representing a netcard cable.

The source code for the NCPA is written in C++. The SProlog interpreter is written in standard C and is encapsulated in a C++ class called SPROLOG.

This executable file controls the invocation of the Windows NT SETUP utility, which interprets and executes installation and configuration scripts provided by Microsoft and other vendors.

Figure 4: Components of Network Configuration

In the preceding figure, the block labeled SPROLOG represents the Small Prolog interpreter residing within its C++ class (described later).

5.2 Portation

5.2.1 Memory Allocation

Due to the support for virtual memory in the Win32 API, the simplistic approach taken toward memory allocation in SProlog actually suited the Windows NT environment well. In the NT version of the memory allocation module, the initialization routine creates a temporary virtual 16MB region. This region is then divided into smaller 2MB zones to support SPrologs heap, trail, stack and so on. However, no actual memory is allocated or committed into the region. Instead, each new memory allocation request probes the desired zone to see if memory is available at the next logical location. This probe operation consists of attempting to store a word, and it is enclosed in a Win32 exception handling block. If memory is not present at the probed location, an access violation exception occurs. The handler for this exception then attempts to commit memory into the zone, and the probe is reattempted. This method dedicates a very small amount of memory to the interpreter, and the use of exception handling requires very little checking during allocation.

5.2.2 STDIO and Friends

Since normal Windows DLLs have no standard I/O streams (e.g., stdout, stdin), it was necessary to segregate all use of the C run-time librarys stdio functions into a single module. Different versions of this stdio aliasing module were written for different environments.

5.2.3 Query and Consulting

Both consulting and querying were extended to operate within string buffers instead of using standard file handles. The DLL-based version of the stdio aliasing module stores query results into a buffer donated to the interpreter by the calling program. If this string is exhausted by the query, an error is returned. The complete results of non-deterministic queries are concatenated into this buffer.

5.3 Tools and Techniques

5.3.1 The Console Application

The SProlog source code is also compiled into a standard TTY-style console application. This is the main environment for testing changes to the lattice generation algorithm.

5.3.2 The Windows Test Application

Using a separate makefile, the entire C++ code ensemble can be linked into a simple Windows application. The menu bar of this test application presents an interface to the large-scale actions of the code base, such as converting the network-related Registry entries to SProlog format. This environment is used for unit-testing the macroscopic functions of the code set.

5.3.3 Use of Resource Fork

Since the lattice generation algorithm is contained in a standard text file, releasing it in this form would have rendered it susceptible to accidental modification, deletion or path location problems. Since it should ideally be bound directly into the DLL, the Windows NT SDK Resource Compiler was used to add the Prolog text file as a UNICODE text resource. At run-time, the C++ code loads this resource, converts it from the UNICODE character set back to ANSI and passes it to interpreter.

5.4 The C++ WrapperClass

All run-time interface to the SProlog interpreter is through an encapsulating C++ class called SPROLOG. The constructor of this class initializes interpreter memory regions and prepares for file handling. The destructor releases all memory and file resources back to the system.

Figure 5: Small Prolog C++ Wrapper Class

In addition to member functions for querying or consulting text files, the SPROLOG class provides similar functions for accessing string buffers.

All queries are nested within an exception handler which catches such errors as

With the exception handler, the SPROLOG class is able to intercept any form of aberrant behavior on the part of the interpreter except serious corruption of the machine stack.

5.5 New Built-In Predicates

5.5.1 Debugging Predicates

A set of debugging predicates were created to match the standard Prolog write predicates; their output is directed to the Windows API OutputDebugString(). This provided the ability to monitor the behavior of the lattice generation algorithm at any level of detail desired while preserving the results on disk via the system debugger.

5.5.2 Registry Querying

A complete set of predicates was added to query the NT Configuration Registry.

5.5.3 The fault/0 Predicate

To test the robustness of exception handling, a predicate called fault/0 was written which generated a protection violation by dereferencing the address 0xFFFFFFFF.

6. Conclusion

6.1 User and Press Evaluation

The overall results of using a Prolog interpreter to solve the network configuration problem have been very positive. Of the network server platforms available on the market, the Windows NT Advanced Server is consistently judged to be the simplest and most reliable to install and re-configure.

6.2 Software Development Considerations

The configuration system has shown itself to be very extensible, and the primary Prolog algorithm has needed no almost no changes in the past year. Much of this stability is due to the ease with which new changes can be tested using the console version of the interpreter.

The centralized configuration approach has resulted in very short lead-times for the development of new component installers. The installation script for a new network product can typically be written in a matter of minutes, and many scripts are minor variations on existing scripts of similar component classes.

6.3 Future Considerations

Using the proper tool is important in any development effort, and Prolog is clearly a superior tool for rule-based construction algorithms. Several Prolog vendors have recently begun to take seriously the issue of truly embeddable Prolog engines. Space does not permit a full exposition of the issues involved, but experience has shown the viability of encapsulating a Prolog interpreter into a Windows dynamic-link library.>

Bibliography

de Feraudy, Henri. Small Prolog, C User's Group diskette # 297. The C Users' Group, P.O. Box 97, McPherson, KS 67460. This is the public domain version of the Small Prolog interpreter, including complete source, documentation and examples.

Microsoft Corporation. Windows NT Resource Guide, Volume 1. Redmond, Washington: Microsoft Press, 1993. This volume of the three volume set describes the Windows NT network architecture, documents all Configuration Registry entries and describes the functions of the SETUP program in detail.

Microsoft Corporation. Win32 Programmer's Reference, Volume 2. Redmond, Washington: Microsoft Press, 1993. This volume describes Win32 structured exception handling. Other volumes in the series describe the architecture of Win32 Dynamic Link Libraries and all other areas of the Win32 programming standard.

Clocksin, W.F. and Mellish, C.S. Programming in Prolog. New York: Springer-Verlag, 1981. This is the standard reference for the Prolog programming language.

Stroustrop, B. The C++ Programming Language 2nd ed. New York: Addison-Wesley, 1994. This is the standard reference for the C++ programming language.

Appendix A. Basic Binding Backtrack Algorithm

/* Return a list of ordered pairs of bindable components */ ( (getbindings List) (findall L (bindpair X Y L) List)) /* Succeed once for each bindable pair: lower -> upper */ ( (bindpair Dev1 Dev2 (Dev1 Dev2 Excl1 Excl2 Value)) (ifpresent lower Dev1 Type1 _ _) (ifpresent upper Dev2 Type2 _ _) (not (eq Dev1 Dev2)) (canbind Type1 Type2 Excl1 Excl2 Value))

/* Succeed if a common "bindable" rule is inherited by the lower layer of X and the upper layer of Y. */ ( (canbind X Y Xexcl Yexcl Value) (iflower X Lower) (ifupper Y Upper) (bindable Blower Bupper Xexcl Yexcl Value) (devDerived Lower Blower) (devDerived Upper Bupper))

// Determine if a device class is a sub-class of another // (devDerived SubClass BaseClass) ( (devDerived X basic) (cut)) ( (devDerived X X) (cut)) ( (devDerived X Y) (devClass X Y _) (cut)) ( (devDerived X Y) (devClass X Z _) (devDerived Z Y)) // ifupper/2: return the class of a device's upper interface // (ifupper Devname Classname) ( (ifupper Ifname Ifclass) (devType Ifname _ Ifclass _)) // iflower/2: return the class of a device's lower interface // (iflower Devname Classname) ( (iflower Ifname Ifclass) (devType Ifname Usage _ Ifclass) // Adapters cannot connect to anything (not (eq Usage adapter))) // ifpresent/5: validate the presence of an interface. // devTypes have upper and lower interface; devIfs only // have an upper interface. // (ifpresent Layer Device Type Owner Objectname) ( (ifpresent _ Dev Type Type Objname) (present Dev Type Objname _)) ( (ifpresent upper Dev Dev Owner Objname) (devIf Owner Dev _ Objname _) (present Owner _ _ _))

Appendix B. Sample Fact Set

The SProlog clauses in this section were extracted from a standard PC development machine at Microsoft.

(devClass ndisDriver basic no) (devClass ndisTransport basic no) (devClass netBiosTransport ndisTransport no) (devClass lmNetService basic no) (bindable ndisTransport ndisDriver non non 100) (bindable lmNetService netBiosTransport non non 100) (devType decetherworksturbo adapter decetherworksturboAdapter decetherworksturboAdapter) (devBind decetherworksturbo "Lance1" yes yes container) (devClass decetherworksturboAdapter basic no) (present decetherworksturbo decetherworksturbo "Lance1" "Machine\SOFTWARE\Microsoft\Windows NT\NetworkCards\1") (devType lanceSys driver ndisDriver lanceDriver) (devBind lanceSys "LanceSys" yes no container) (devClass lanceDriver basic no) (bindable lanceDriver dec100Adapter non exclusive 100) (bindable lanceDriver dec101Adapter non exclusive 100) (bindable lanceDriver decetherworksturboAdapter non exclusive 100) (bindable lanceDriver dec422Adapter non exclusive 100) (bindable lanceDriver decpcAdapter non exclusive 100) (bindable lanceDriver decstatAdapter non exclusive 100) (present lanceSys lanceSys "LanceSys" "Machine\SOFTWARE\Microsoft\Lance") (devType ubnb transport ubnbNbTransport streamsStack) (devBind ubnb "Ubnb" yes yes container) (devClass ubnbNbTransport netBiosTransport yes) (present ubnb ubnb "Ubnb" "Machine\SOFTWARE\Microsoft\Ubnb") (devType mcsxns transport mcsxnsTransport streamsStack) (devBind mcsxns "McsXns" yes yes container) (devClass mcsxnsTransport basic yes) (present mcsxns mcsxns "McsXns" "Machine\SOFTWARE\Microsoft\McsXns") (devType nbf transport netBiosTransport rasCapableTransport) (devBind nbf "Nbf" yes yes simple) (devClass rasCapableTransport netBiosTransport no) (present nbf nbf "Nbf" "Machine\SOFTWARE\Microsoft\Nbf") (devType netbios service lmNetService lmNetService) (devBind netbios "Netbios" yes yes container) (present netbios netbios "Netbios" "Machine\SOFTWARE\Microsoft\NetBIOS") (devType srv service lmNetService lanmanServer) (devBind srv "LanmanServer" yes yes container) (devClass lanmanServer lmNetService no) (present srv srv "LanmanServer" "Machine\SOFTWARE\Microsoft\LanmanServer") (devType streams transport streamsEnvironment streamsEnvironment) (devBind streams "Streams" yes yes streams) (devClass streamsEnvironment basic no) (devClass streamsStack basic no) (bindable streamsEnvironment ndisDriver non non 100) (bindable streamsStack streamsEnvironment exclusive non 100) (present streams streams "Streams" "Machine\SOFTWARE\Microsoft\Streams") (devType wksta service lmNetService lanmanWorkstation) (devBind wksta "LanmanWorkstation" yes yes container) (devClass lanmanWorkstation lmNetService no) (present wksta wksta "LanmanWorkstation" "Machine\SOFTWARE\Microsoft\LanmanWorkstation")