US20020016891A1 - Method and apparatus for reconfiguring memory in a multiprcessor system with shared memory - Google Patents

Abstract

Multiple instances of operating systems execute cooperatively in a single multiprocessor computer wherein all processors and resources are electrically connected together. The single physical machine with multiple physical processors and resources is subdivided by software into multiple partitions, each with the ability to run a distinct copy, or instance, of an operating system. At different times, different operating system instances may be loaded on a given partition. Resources, such as CPUs and memory, can be dynamically assigned to different partitions and used by instances of operating systems running within the machine by modifying the configuration. The partitions themselves can also be changed without rebooting the system by modifying the configuration tree. Memory may be reconfigured into or out of a partition or community under software control. In general, memory may be in one of three states: private, shared, or unowned. Memory is private if it is “owned” by a single system partition. Memory is shared if it is owned by partitions which are members of a community. Otherwise, it is unowned. Memory is placed in an “unowned” state by an operating system instance and console software, reflected in the system configuration tree, before the memory can be reconfigured into or out of a system.

Description

FIELD OF THE INVENTION
• This invention relates to multiprocessor computer architectures in which processors and other computer hardware resources are grouped in partitions, each of which has an operating system instance and, more specifically, to methods and apparatus for allocating computer hardware resources to partitions.[0001]
BACKGROUND OF THE INVENTION
• The efficient operation of many applications in present computing environments depends upon fast, powerful and flexible computing systems. The configuration and design of such systems has become very complicated when such systems are to be used in an “enterprise” commercial environment where there may be many separate departments, many different problem types and continually changing computing needs. Users in such environments generally want to be able to quickly and easily change the capacity of the system, its speed and its configuration. They may also want to expand the system work capacity and change configurations to achieve better utilization of resources without stopping execution of application programs on the system. In addition they may want be able to configure the system in order to maximize resource availability so that each application will have an optimum computing configuration.[0002]
• Traditionally, computing speed has been addressed by using a “shared nothing” computing architecture where data, business logic, and graphic user interfaces are distinct tiers and have specific computing resources dedicated to each tier. Initially, a single central processing unit was used and the power and speed of such a computing system was increased by increasing the clock rate of the single central processing unit. More recently, computing systems have been developed which use several processors working as a team instead one massive processor working alone. In this manner, a complex application can be distributed among many processors instead of waiting to be executed by a single processor. Such systems typically consist of several central processing units (CPUs) which are controlled by a single operating system. In a variant of a multiple processor system called “symmetric multiprocessing” or SMP, the applications are distributed equally across all processors. The processors also share memory. In another variant called “asymmetric multiprocessing” or AMP, one processor acts as a “master” and all of the other processors act as “slaves.” Therefore, all operations, including the operating system, must pass through the master before being passed onto the slave processors. These multiprocessing architectures have the advantage that performance can be increased by adding additional processors, but suffer from the disadvantage that the software running on such systems must be carefully written to take advantage of the multiple processors and it is difficult to scale the software as the number of processors increases. Current commercial workloads do not scale well beyond 8-24 CPUs as a single SMP system, the exact number depending upon platform, operating system and application mix.[0003]
• For increased performance, another typical answer has been to dedicate computer resources (machines) to an application in order to optimally tune the machine resources to the application. However, this approach has not been adopted by the majority of users because most sites have many applications and separate databases developed by different vendors. Therefore, it is difficult, and expensive, to dedicate resources among all of the applications especially in environments where the application mix is constantly changing.[0004]
• Alternatively, a computing system can be partitioned with hardware to make a subset of the resources on a computer available to a specific application. This approach avoids dedicating the resources permanently since the partitions can be changed, but still leaves issues concerning performance improvements by means of load balancing of resources among partitions and resource availability.[0005]
• The availability and maintainability issues were addressed by a “shared everything” model in which a large centralized robust server that contains most of the resources is networked with and services many small, uncomplicated client network computers. Alternatively, “clusters” are used in which each system or “node” has its own memory and is controlled by its own operating system. The systems interact by sharing disks and passing messages among themselves via some type of communications network. A cluster system has the advantage that additional systems can easily be added to a cluster. However, networks and clusters suffer from a lack of shared memory and from limited interconnect bandwidth which places limitations on performance.[0006]
• In many enterprise computing environments, it is clear that the two separate computing models must be simultaneously accommodated and each model optimized. Several prior art approaches have been used to attempt this accommodation. For example, a design called a “virtual machine” or VM developed and marketed by International Business Machines Corporation, Armonk, N.Y., uses a single physical machine, with one or more physical processors, in combination with software which simulates multiple virtual machines. Each of those virtual machines has, in principle, access to all the physical resources of the underlying real computer. The assignment of resources to each virtual machine is controlled by a program called a “hypervisor”. There is only one hypervisor in the system and it is responsible for all the physical resources. Consequently, the hypervisor, not the other operating systems, deals with the allocation of physical hardware. The hypervisor intercepts requests for resources from the other operating systems and deals with the requests in a globally-correct way.[0007]
• The VM architecture supports the concept of a “logical partition” or LPAR. Each LPAR contains some of the available physical CPUs and resources which are logically assigned to the partition. The same resources can be assigned to more than one partition. LPARs are set up by an administrator statically, but can respond to changes in load dynamically, and without rebooting, in several ways. For example, if two logical partitions, each containing ten CPUs, are shared on a physical system containing ten physical CPUs, and, if the logical ten CPU partitions have complementary peak loads, each partition can take over the entire physical ten CPU system as the workload shifts without a re-boot or operator intervention.[0008]
• In addition, the CPUs logically assigned to each partition can be turned “on” and “off” dynamically via normal operating system operator commands without re-boot. The only limitation is that the number of CPUs active at system initialization is the maximum number of CPUs that can be turned “on” in any partition.[0009]
• Finally, in cases where the aggregate workload demand of all partitions is more than can be delivered by the physical system, LPAR weights can be used to define how much of the total CPU resources is given to each partition. These weights can be changed by operators on-the-fly with no disruption.[0010]
• Another prior art system is called a “Parallel Sysplex” and is also marketed and developed by the International Business Machines Corporation. This architecture consists of a set of computers that are clustered via a hardware entity called a “coupling facility” attached to each CPU. The coupling facilities on each node are connected via a fiber-optic link and each node operates as a traditional SMP machine, with a maximum of 10 CPUs. Certain CPU instructions directly invoke the coupling facility. For example, a node registers a data structure with the coupling facility, then the coupling facility takes care of keeping the data structures coherent within the local memory of each node.[0011]
• The Enterprise 10000 Unix server developed and marketed by Sun Microsystems, Mountain View, Calif., uses a partitioning arrangement called “Dynamic System Domains” to logically divide the resources of a single physical server into multiple partitions, or domains, each of which operates as a stand-alone server. Each of the partitions has CPUs, memory and I/O hardware. Dynamic reconfiguration allows a system administrator to create, resize, or delete domains on the fly and without rebooting. Every domain remains logically isolated from any other domain in the system, isolating it completely from any software error or CPU, memory, or I/O error generated by any other domain. There is no sharing of resources between any of the domains.[0012]
• The Hive Project conducted at Stanford University uses an architecture which is structured as a set of cells. When the system boots, each cell is assigned a range of nodes that it owns throughout execution. Each cell manages the processors, memory and I/O devices on those nodes as if it were an independent operating system. The cells cooperate to present the illusion of a single system to user-level processes.[0013]
• Hive cells are not responsible for deciding how to divide their resources between local and remote requests. Each cell is responsible only for maintaining its internal resources and for optimizing performance within the resources it has been allocated. Global resource allocation is carried out by a user-level process called “wax.” The Hive system attempts to prevent data corruption by using certain fault containment boundaries between the cells. In order to implement the tight sharing expected from a multiprocessor system despite the fault containment boundaries between cells, resource sharing is implemented through the cooperation of the various cell kernels, but the policy is implemented outside the kernels in the wax process. Both memory and processors can be shared.[0014]
• A system called “Cellular IRIX” developed and marketed by Silicon Graphics Inc. Mountain View, Calif., supports modular computing by extending traditional symmetric multiprocessing systems. The Cellular IRIX architecture distributes global kernel text and data into optimized SMP-sized chunks or “cells”. Cells represent a control domain consisting of one or more machine modules, where each module consists of processors, memory, and I/O. Applications running on these cells rely extensively on a full set of local operating system services, including local copies of operating system text and kernel data structures. Only one instance of the operating system exists on the entire system. Inter-cell coordination allows application images to directly and transparently utilize processing, memory and I/O resources from other cells without incurring the overhead of data copies or extra context switches.[0015]
• Another existing architecture called NUMA-Q developed and marketed by Sequent Computer Systems, Inc., Beaverton, Oreg. uses “quads”, or a group of four processors per portion of memory, as the basic building block for NUMA-Q SMP nodes. Adding I/O to each quad further improves performance. Therefore, the NUMA-Q architecture not only distributes physical memory but puts a predetermined number of processors and PCI slots next to each part. The memory in each quad is not local memory in the traditional sense. Rather, it is one third of the physical memory address space and has a specific address range. The address map is divided evenly over memory, with each quad containing a contiguous portion of address space. Only one copy of the operating system is running and, as in any SMP system, it resides in memory and runs processes without distinction and simultaneously on one or more processors.[0016]
• Accordingly, while many attempts have been made at providing a flexible computer system having maximum resource availability and scalability, existing systems each have significant shortcomings. Therefore, it would be desirable to have a new computer system design which provides improved flexibility, resource availability and scalability.[0017]
SUMMARY OF THE INVENTION
• In accordance with the principles of the present invention, multiple instances of operating systems execute cooperatively in a single multiprocessor computer wherein all processors and resources are electrically connected together. The single physical machine with multiple physical processors and resources is adaptively subdivided by software into multiple partitions, each with the ability to run a distinct copy, or instance, of an operating system. Each of the partitions has access to its own physical resources plus resources designated as shared. In accordance with one embodiment, the partitioning of resources is performed by assigning resources within a configuration.[0018]
• More particularly, software logically, and adaptively, partitions CPUs, memory, and I/O ports by assigning them together. An instance of an operating system may then be loaded on a partition. At different times, different operating system instances may be loaded on a given partition. This partitioning, which a system manager directs, is a software function; no hardware boundaries are required. Each individual instance has the resources it needs to execute independently. Resources, such as CPUs and memory, can be dynamically assigned to different partitions and used by instances of operating systems running within the machine by modifying the configuration. The partitions themselves can also be changed without rebooting the system by modifying the configuration tree. The resulting adaptively-partitioned, multi-processing (APMP) system exhibits scalability, flexibility, and high performance.[0019]
• Memory may be reconfigured into or out of a partition or community under software control and hardware hot in-swapping or out-swapping are supported. In general, memory may be in one of three states: private, shared, or unowned. Memory is private if it is “owned” by a single system partition. Memory is shared if it is owned by a community. A community is a collection of one or more partitions which may share resources. Otherwise, it is unowned. Memory may be reconfigured between any of three states directly. For example, memory may be reconfigured from private in one partition to private in another partition, or from shared in a community to private in a partition. Memory is placed in the unowned state by an operating system instance and console software, reflected in the system configuration tree, before the memory can be out-swapped or in-swapped. A page fram number database is sized to include all possible memory that can be in-swapped and added memory pages may be employed as page frame number database entry pages. Consequently, new memory can be readily accommodated. As noted above, to out-swap memory, the memory must be in the unowned state. If the memory to be out-swapped is in either the shared or private state, it is placed in the unowned state to permit out-swapping.[0020]
BRIEF DESCRIPTION OF THE DRAWINGS
• The above and further advantages of the invention may be better understood by referring to the following description in conjunction with the accompanying drawings and which:[0021]
• FIG. 1 is a schematic block diagram of a hardware platform illustrating several system building blocks.[0022]
• FIG. 2 is a schematic diagram of an APMP computer system constructed in accordance with the principles of the present invention illustrating several partitions.[0023]
• FIG. 3 is a schematic diagram of a configuration tree which represents hardware resource configurations and software configurations and their component parts with child and sibling pointers.[0024]
• FIG. 4 is a schematic diagram of the configuration tree shown in FIG. 3 and rearranged to illustrate the assignment of hardware to software instances by ownership pointers.[0025]
• FIG. 5 is a flowchart outlining steps in an illustrative routine for creating an APMP computer system in accordance with the principles of the present invention.[0026]
• FIG. 6 is a flowchart illustrating the steps in an illustrative routine for creating entries in an APMP system management database which maintains information concerning the APMP system and its configuration.[0027]
• FIGS. 7A and 7B, when placed together, form a flowchart illustrating in detail the steps in an illustrative routine for creating an APMP computer system in accordance with the principles of the present invention.[0028]
• FIGS. 8A and 8B, when placed together, form a flowchart illustrating the steps in an illustrative routine followed by an operating system instance to join an APMP computer system which is already created[0029]
• FIG. 9 is a flowchart illustrating the steps in an illustrative routine followed by an operating system instance as it removes private memory from a system.[0030]
• FIG. 10 is a flowchart illustrating the steps in an illustrative routine followed by an operating system instance as it removes shared memory from a system.[0031]
• FIG. 11 is a memory map of a PFN database in accordance with the invention.[0032]
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
• A computer platform constructed in accordance with the principles of the present invention is a multi-processor system capable of being partitioned to allow the concurrent execution of multiple instances of operating system software. The system does not require hardware support for the partitioning of its memory, CPUs and I/O subsystems, but some hardware may be used to provide additional hardware assistance for isolating faults, and minimizing the cost of software engineering. The following specification describes the interfaces and data structures required to support the inventive software architecture. The interfaces and data structures described are not meant to imply a specific operating system must be used, or that only a single type of operating system will execute concurrently. Any operating system which implements the software requirements discussed below can participate in the inventive system operation.[0033]
• System Building Blocks[0034]
• The inventive software architecture operates on a hardware platform which incorporates multiple CPUs, memory and I/O hardware. Preferably, a modular architecture such as that shown in FIG. 1 is used, although those skilled in the art will understand that other architectures can also be used, which architectures need not be modular. FIG. 1 illustrates a computing system constructed of four basic system building blocks (SBBs)[0035]100-106. In the illustrative embodiment, each building block, such asblock100, is identical and comprises several CPUs108-114, several memory slots (illustrated collectively as memory120), an I/O processor118, and aport116 which contains a switch (not shown) that can connect the system to another such system. However, in other embodiments, the building blocks need not be identical. Large multiprocessor systems can be constructed by connecting the desired number of system building blocks by means of their ports. Switch technology, rather than bus technology, is employed to connect building block components in order to both achieve the improved bandwidth and to allow for non-uniform memory architectures (NUMA).
• In accordance with the principles of the invention, the hardware switches are arranged so that each CPU can address all available memory and I/O ports regardless of the number of building blocks configured as schematically illustrated by[0036]line122. In addition, all CPUs may communicate to any or all other CPUs in all SBBs with conventional mechanisms, such as inter-processor interrupts. Consequently, the CPUs and other hardware resources can be associated solely with software. Such a platform architecture is inherently scalable so that large amounts of processing power, memory and I/O will be available in a single computer.
• An[0037]APMP computer system200 constructed in accordance with the principles of the present invention from a software view is illustrated in FIG. 2. In this system, the hardware components have been allocated to allow concurrent execution of multipleoperating system instances208,210,212.
• In a preferred embodiment, this allocation is performed by a software program called a “console” program, which, as will hereinafter be described in detail, is loaded into memory at power up. Console programs are shown schematically in FIG. 2 as[0038]programs213,215 and217. The console program may be a modification of an existing administrative program or a separate program which interacts with an operating system to control the operation of the preferred embodiment. The console program does not virtualize the system resources, that is, it does not create any software layers between the runningoperating systems208,210 and212 and the physical hardware, such as memory and I/O units (not shown in FIG. 2.) Nor is the state of the runningoperating systems208,210 and212 swapped to provide access to the same hardware. Instead, the inventive system logically divides the hardware into partitions. It is the responsibility ofoperating system instance208,210, and212 to use the resources appropriately and provide coordination of resource allocation and sharing. The hardware platform may optionally provide hardware assistance for the division of resources, and may provide fault barriers to minimize the ability of an operating system to corrupt memory, or affect devices controlled by another operating system copy.
• The execution environment for a single copy of an operating system, such as[0039]copy208 is called a “partition”202, and the executingoperating system208 inpartition202 is called “instance”208. Each operating system instance is capable of booting and running independently of all other operating system instances in the computer system, and can cooperatively take part in sharing resources between operating system instances as described below.
• In order to run an operating system instance, a partition must include a hardware restart parameter block (HWRPB), a copy of a console program, some amount of memory, one or more CPUs, and at least one I/O bus which must have a dedicated physical port for the console. The HWRPB is a configuration block which is passed between the console program and the operating system.[0040]
• Each of[0041]console programs213,215 and217, is connected to a console port, shown asports214,216 and218, respectively. Console ports, such asports214,216 and218, generally come in the form of a serial line port, or attached graphics, keyboard and mouse options. For the purposes of the inventive computer system, the capability of supporting a dedicated graphics port and associated input devices is not required, although a specific operating system may require it. The base assumption is that a serial port is sufficient for each partition. While a separate terminal, or independent graphics console, could be used to display information generated by each console, preferably theserial lines220,222 and224, can all be connected to asingle multiplexer226 attached to a workstation, PC, orLAT228 for display of console information.
• It is important to note that partitions are not synonymous with system building blocks. For example,[0042]partition202 may comprise the hardware inbuilding blocks100 and106 in FIG. 1 whereaspartitions204 and206 might comprise the hardware inbuilding blocks102 and104, respectively. Partitions may also include part of the hardware in a building block.
• Partitions can be “initialized” or “uninitialized.” An initialized partition has sufficient resources to execute an operating system instance, has a console program image loaded, and a primary CPU available and executing. An initialized partition may be under control of a console program, or may be executing an operating system instance. In an initialized state, a partition has full ownership and control of hardware components assigned to it and only the partition itself may release its components.[0043]
• In accordance with the principles of the invention, resources can be reassigned from one initialized partition to another. Reassignment of resources can only be performed by the initialized partition to which the resource is currently assigned. When a partition is in an uninitialized state, other partitions may reassign its hardware components and may delete it.[0044]
• An uninitialized partition is a partition which has no primary CPU executing either under control of a console program or an operating system. For example, a partition may be uninitialized due to a lack of sufficient resources at power up to run a primary CPU, or when a system administrator is reconfiguring the computer system. When in an uninitialized state, a partition may reassign its hardware components and may be deleted by another partition. Unassigned resources may be assigned by any partition.[0045]
• Partitions may be organized into “communities” which provide the basis for grouping separate execution contexts to allow cooperative resource sharing. Partitions in the same community can share resources. Partitions that are not within the same community cannot share resources. Resources may only be manually moved between partitions that are not in the same community by the system administrator by de-assigning the resource (and stopping usage), and manually reconfiguring the resource. Communities can be used to create independent operating system domains, or to implement user policy for hardware usage. In FIG. 2,[0046]partitions202 and204 have been organized intocommunity230.Partition206 may be in itsown community205. Communities can be constructed using the configuration tree described below and may be enforced by hardware.
• The Console Program[0047]
• When a computer system constructed in accordance with the principles of the present invention is enabled on a platform, multiple HWRPB's must be created, multiple console program copies must be loaded, and system resources must be assigned in such a way that each HWRPB is associated with specific components of the system. To do this, the first console program to run will create a configuration tree structure in memory which represents all of the hardware in the system. The tree will also contain the software partitioning information, and the assignments of hardware to partitions and is discussed in detail below.[0048]
• More specifically, when the APMP system is powered up, a CPU will be selected as a primary CPU in a conventional manner by hardware which is specific to the platform on which the system is running. The primary CPU then loads a copy of a console program into memory. This console copy is called a “master console” program. The primary CPU initially operates under control of the master console program to perform testing and checking assuming that there is a single system which owns the entire machine. Subsequently, a set of environment variables are loaded which define the system partitions. Finally, the master console creates and initializes the partitions based on the environment variables. In this latter process the master console operates to create the configuration tree, to create additional HWRPB data blocks, to load the additional console program copies, and to start the CPUs on the alternate HWRPBs. Each partition then has an operating system instance running on it, which instance cooperates with a console program copy also running in that partition. In an unconfigured APMP system, the master console program will initially create a single partition containing the primary CPU, a minimum amount of memory, and a physical system administrator's console selected in a platform-specific way. Console program commands will then allow the system administrator to create additional partitions, and configure I/O buses, memory, and CPUs for each partition.[0049]
• After associations of resources to partitions have been made by the console program, the associations are stored in non-volatile RAM to allow for an automatic configuration of the system during subsequent boots. During subsequent boots, the master console program must validate the current configuration with the stored configuration to handle the removal and addition of new components. Newly-added components are placed into an unassigned state, until they are assigned by the system administrator. If the removal of a hardware component results in a partition with insufficient resources to run an operating system, resources will continue to be assigned to the partition, but it will be incapable of running an operating system instance until additional new resources are allocated to it.[0050]
• As previously mentioned, the console program communicates with an operating system instance by means of an HWRPB which is passed to the operating system during operating system boot up. The fundamental requirements for a console program are that it should be able to create multiple copies of HWRPBs and itself. Each HWRPB copy created by the console program will be capable of booting an independent operating system instance into a private section of memory and each operating system instance booted in this manner can be identified by a unique value placed into the HWRPB. The value indicates the partition, and is also used as the operating system instance ID.[0051]
• In addition, the console program is configured to provide a mechanism to remove a CPU from the available CPUs within a partition in response to a request by an operating system running in that partition. Each operating system instance must be able to shutdown, halt, or otherwise crash in a manner that control is passed to the console program. Conversely, each operating system instance must be able to reboot into an operational mode, independently of any other operating system instance.[0052]
• Each HWRPB which is created by a console program will contain a CPU slot-specific database for each CPU that is in the system, or that can be added to the system without powering the entire system down. Each CPU that is physically present will be marked “present”, but only CPUs that will initially execute in a specific partition will be marked “available” in the HWRPB for the partition. The operating system instance running on a partition will be capable of recognizing that a CPU may be available at some future time by a present (PP) bit in a per-CPU state flag fields of the HWRPB, and can build data structures to reflect this. When set, the available (PA) bit in the per-CPU state flag fields indicates that the associated CPU is currently associated with the partition, and can be invited to join SMP operation.[0053]
• The Configuration Tree[0054]
• As previously mentioned, the master console program creates a configuration tree which represents the hardware configuration, and the assignment of each component in the system to each partition. Each console program then identifies the configuration tree to its associated operating system instance by placing a pointer to the tree in the HWRPB.[0055]
• Referring to FIG. 3, the[0056]configuration tree300 represents the hardware components in the system, the platform constraints and minimums, and the software configuration. The master console program builds the tree using information discovered by probing the hardware, and from information stored in non-volatile RAM which contains configuration information generated during previous initializations.
• The master console may generate a single copy of the tree which copy is shared by all operating system instances, or it may replicate the tree for each instance. A single copy of the tree has the disadvantage that it can create a single point of failure in systems with independent memories. However, platforms that generate multiple tree copies require the console programs to be capable of keeping changes to the tree synchronized.[0057]
• The configuration tree comprises multiple nodes including root nodes, child nodes and sibling nodes. Each node is formed of a fixed header and a variable length extension for overlaid data structures. The tree starts with a[0058]tree root node302 representing the entire system box, followed by branches that describe the hardware configuration (hardware root node304), the software configuration (software root node306), and the minimum partition requirements (template root node308.) In FIG. 3, the arrows represent child and sibling relationships. The children of a node represent component parts of the hardware or software configuration. Siblings represent peers of a component that may not be related except by having the same parent. Nodes in thetree300 contain information on the software communities and operating system instances, hardware configuration, configuration constraints, performance boundaries and hot-swap capabilities. The nodes also provide the relationship of hardware to software ownership, or the sharing of a hardware component.
• The nodes are stored contiguously in memory and the address offset from the[0059]tree root node302 of thetree300 to a specific node forms a “handle” which may be used from any operating system instance to unambiguously identify the same component on any operating system instance. In addition, each component in the inventive computer system has a separate ID. This may illustratively be a 64-bit unsigned value. The ID must specify a unique component when combined with the type and subtype values of the component. That is, for a given type of component, the ID must identify a specific component. The ID may be a simple number, for example the CPU ID, it may be some other unique encoding, or a physical address. The component ID and handle allow any member of the computer system to identify a specific piece of hardware or software. That is, any partition using either method of specification must be able to use the same specification, and obtain the same result.
• As described above, the inventive computer system is composed of one or more communities which, in turn, are composed of one or more partitions. By dividing the partitions across the independent communities, the inventive computer system can be placed into a configuration in which sharing of devices and memory can be limited. Communities and partitions will have IDs which are densely packed. The hardware platform will determine the maximum number of partitions based on the hardware that is present in the system, as well as having a platform maximum limit. Partition and community IDs will never exceed this value during runtime. IDs will be reused for deleted partitions and communities. The maximum number of communities is the same as the maximum number of partitions. In addition, each operating system instance is identified by a unique instance identifier, for example a combination of the partition ID plus an incarnation number.[0060]
• The communities and partitions are represented by a[0061]software root node306, which has community node children (of whichcommunity node310 is shown), and partition node grandchildren (of which two nodes,312 and314, are shown.) The hardware components are represented by ahardware root node304 which contains children that represent a hierarchical representation of all of the hardware currently present in the computer system. “Ownership” of a hardware component is represented by a handle in the associated hardware node which points to the appropriate software node (310,312 or314.) These handles are illustrated in FIG. 4 which will be discussed in more detail below. Components that are owned by a specific partition will have handles that point to the node representing the partition. Hardware which is shared by multiple partitions (for example, memory) will have handles that point to the community to which sharing is confined. Un-owned hardware will have a handle of zero (representing the tree root node302).
• Hardware components place configuration constraints on how ownership may be divided. A “config” handle in the configuration tree node associated with each component determines if the component is free to be associated anywhere in the computer system by pointing to the[0062]hardware root node304. However, some hardware components may be bound to an ancestor node and must be configured as part of this node. Examples of this are CPUs, which may have no constraints on where they execute, but which are a component part of a system building block (SBB), such asSBBs322 or324. In this case, even though the CPU is a child of the SBB, its config handle will point to thehardware root node304. An I/O bus, however, may not be able to be owned by a partition other than the partition that owns its I/O processor. In this case, the configuration tree node representing the I/O bus would have a config handle pointing to the I/O processor. Because the rules governing hardware configuration are platform specific, this information is provided to the operating system instances by the config handle.
• Each hardware component also has an “affinity” handle. The affinity handle is identical to the config handle, except that it represents a configuration which will obtain the best performance of the component. For example, a CPU or memory may have a config handle which allows it to be configured anywhere in the computer system (it points to the hardware root node[0063]304), however, for optimal performance, the CPU or memory should be configured to use the System Building Block of which they are a part. The result is that the config pointer points to thehardware root node304, but the affinity pointer points to an SBB node such asnode322 ornode324. The affinity of any component is platform specific, and determined by the firmware. Firmware may use this information when asked to form “optimal” automatic configurations.
• Each node also contains several flags which indicate the type and state of the node. These flags include a node_hotswap flag which indicates that the component represented is a “hot swappable” component and can be powered down independently of its parent and siblings. However, all children of this node must power down if this component powers down. If the children can power down independently of this component, they must also have this bit set in their corresponding nodes. Another flag is a node_unavailable flag which, when set, indicates that the component represented by the node is not currently available for use. When a component is powered down (or is never powered up) it is flagged as unavailable.[0064]
• Two flags, node_hardware and node_template, indicate the type of node. Further flags, such as node_initialized and node_cpu_primary may also be provided to indicate whether the node represents a partition which has been initialized or a CPU that is currently a primary CPU.[0065]
• The[0066]configuration tree300 may extend to the level of device controllers, which will allow the operating system to build bus and device configuration tables without probing the buses. However, the tree may also end at any level, if all components below it cannot be configured independently. System software will still be required to probe for bus and device information not provided by the tree.
• The console program implements and enforces configuration constraints, if any, on each component of the system. In general, components are either assignable without constraints (for example, CPUs may have no constraints), or are configurable only as a part of another component (a device adapter, for example, may be configurable only as a part of its bus). A partition which is, as explained above, a grouping of CPUs, memory, and I/O devices into a unique software entity also has minimum requirements. For example, the minimum hardware requirements for a partition are at least one CPU, some private memory (platform dependent minimum, including console memory) and an I/O bus, including a physical, non-shared, console port.[0067]
• The minimal component requirements for a partition are provided by the information contained in the[0068]template root node308. Thetemplate root node308 contains nodes,316,318 and320, representing the hardware components that must be provided to create a partition capable of execution of a console program and an operating system instance. Configuration editors can use this information as the basis to determine what types, and how many resources must be available to form a new partition.
• During the construction of a new partition, the template subtree will be “walked”, and, for each node in the template subtree, there must be a node with the same type and subtype owned by the new partition so that it will be capable of loading a console program and booting an operating system instance. If there are more than one node of the same type and subtype in the template tree, there must also be multiple nodes in the new partition. The console program will use the template to validate that a new partition has the minimum requirements prior to attempting to load a console program and initialize operation.[0069]
• The following is a detailed example of a particular implementation of configuration tree nodes. It is intended for descriptive purposes only and is not intended to be limiting. Each HWRPB must point to a configuration tree which provides the current configuration, and the assignments of components to partitions. A configuration pointer (in the CONFIG field) in the HWRPB is used to point to the configuration tree. The CONFIG field points to a 64-byte header containing the size of the memory pool for the tree, and the initial checksum of the memory. Immediately following the header is the root node of the tree. The header and root node of the tree will be page aligned.[0070]
• The total size in bytes of the memory allocated for the configuration tree is located in the first quadword of the header. The size is guaranteed to be in multiples of the hardware page size. The second quadword of the header is reserved for a checksum. In order to examine the configuration tree, an operating system instance maps the tree into its local address space. Because an operating system instance may map this memory with read access allowed for all applications, some provision must be made to prevent a non-privileged application from gaining access to console data to which it should not have access. Access may be restricted by appropriately allocating memory. For example, the memory may be page aligned and allocated in whole pages. Normally, an operating system instance will map the first page of the configuration tree, obtain the tree size, and then remap the memory allocated for configuration tree usage. The total size may include additional memory used by the console for dynamic changes to the tree.[0071]
• Preferably, configuration tree nodes are formed with fixed headers, and may optionally contain type-specific information following the fixed portion. The size field contains the full length of the node, nodes are illustratively allocated in multiples of 64-bytes and padded as needed. The following description defines illustrative fields in the fixed header for a node:[0072]

  	typedef struct_gct_node {

  	unsigned char	type;
  	unsigned char	subtype;
  	uint16	size;
  	GCT_HANDLE	owner
  	GCT_HANDLE	current_owner;
  	GCT_ID	id;
  	union {
  	uint64	node_flags;
  	struct {
  	unsigned	node_hardware	: 1;
  	unsigned	node_hotswap	: 1;
  	unsigned	node_unavailable	: 1;
  	unsigned	node_hw_template	: 1;
  	unsigned	node_initialized	: 1;
  	unsigned	node_cpu_primary	: 1;

  	#define NODE_HARDWARE	0x001
  	#define NODE_HOTSWAP	0x002
  	#define NODE_UNAVAILABLE	0x004
  	#define NODE_HW_TEMPLATE	0x008
  	#define NODE_INITIALIZED	0x010
  	#define NODE_PRIMARY	0x020

  	} flag_bits;
  	} flag_union;
  	GCT_HANDLE	config;
  	GCT_HANDLE	affinity;
  	GCT_HANDLE	parent;
  	GCT_HANDLE	next_sib
  	GCT_HANDLE	prey_sib
  	GCT_HANDLE	child;
  	GCT_HANDLE	reserved;
  	uint32	magic
  	} GCT_NODE;

• In the above definition the type definitions “uint” are unsigned integers with the appropriate bit lengths. As previously mentioned, nodes are located and identified by a handle (identified by the typedef GCT_HANDLE in the definition above). An illustrative handle is a signed 32-bit offset from the base of the configuration tree to the node. The value is unique across all partitions in the computer system. That is, a handle obtained on one partition must be valid to lookup a node, or as an input to a console callback, on all partitions. The magic field contains a predetermined bit pattern which indicates that the node is actually a valid node.[0073]
• The tree root node represents the entire system. Its handle is always zero. That is, it is always located at the first physical location in the memory allocated for the configuration tree following the config header. It has the following definition:[0074]

  	typedef struct_gct root_node {

  	GCT_NODE	hd;
  	uint64	lock;
  	uint64	transient_level;
  	uint64	current_level
  	uint64	console_req;
  	uint64	min_alloc
  	uint64	min_align;
  	uint64	base_alloc
  	uint64	base_align;
  	uint64	max_phys_address;
  	uint64	mem_size;
  	uint64	platform_type;
  	int32	platform_name;
  	GCT_HANDLE	primary_instance;
  	GCT HANDLE	first_free;
  	GCT_HANDLE	high_limit
  	GCT_HANDLE	lookaside;
  	GCT_HANDLE	available;
  	uint32	max_partition;
  	int32	partitions;
  	int32	communities;
  	uint32	max_platform_partition;
  	uint32	max_fragments;
  	uint32	max_desc
  	char	APMP_id[16];
  	char	APMP_id_pad[4];
  	int32	bindings;

  	}	GCT_ROOT_NODE;

• The fields in the root node are defined as follows:[0075]
• lock[0076]
• This field is used as a simple lock by software wishing to inhibit changes to the structure of the tree, and the software configuration. When this value is −1 (all bits on) the tree is unlocked; when the value is >=0 the tree is locked. This field is modified using atomic operations. The caller of the lock routine passes a partition ID which is written to the lock field. This can be used to assist in fault tracing, and recovery during crashes.[0077]
• transient_level[0078]
• This field is incremented at the start of a tree update.[0079]
• current_level[0080]
• This field is updated at the completion of a tree update.[0081]
• console_req[0082]
• This field specifies the memory required in bytes for the console in the base memory segment of a partition.[0083]
• min_alloc[0084]
• This field holds the minimum size of a memory fragment, and the allocation unit (fragments size must be a multiple of the allocation). It must be a power of 2.[0085]
• min_align[0086]
• This field holds the alignment requirements for a memory fragment. It must be a power of 2.[0087]
• base_alloc[0088]
• This field specifies the minimum memory in bytes (including console_req) needed for the base memory segment for a partition. This is where the console, console structures, and operating system will be loaded for a partition. It must be greater or equal to minAlloc and a multiple of minAlloc.[0089]
• base_align[0090]
• This field holds the alignment requirement for the base memory segment of a partition. It must be a power of 2, and have an alignment of at least min_align.[0091]
• max_phys_address[0092]
• The field holds the calculated largest physical address that could exist on the system, including memory subsystems that are not currently powered on and available.[0093]
• mem_size[0094]
• This field holds the total memory currently in system.[0095]
• platform_type[0096]
• This field stores the type of platform taken from a field in the HWRPB.[0097]
• plafform_name[0098]
• This field holds an integer offset from the base of the tree root node to a string representing the name of the platform.[0099]
• primary_instance[0100]
• This field stores the partition ID of the first operating system instance.[0101]
• first_free[0102]
• This field holds the offset from the tree root node to the first free byte of memory pool used for new nodes.[0103]
• high_limit[0104]
• This field holds the highest address at which a valid node can be located within the configuration tree. It is used by callbacks to validate that a handle is legal.[0105]
• lookaside[0106]
• This field is the handle of a linked list of nodes that have been deleted, and that may be reclaimed. When a community or partition are deleted, the node is linked into this list, and creation of a new partition or community will look at this list before allocating from free pool.[0107]
• available[0108]
• This field holds the number of bytes remaining in the free pool pointed to by the first_free field.[0109]
• max_partitions[0110]
• This field holds the maximum number of partitions computed by the platform based on the amount of hardware resources currently available.[0111]
• partitions[0112]
• This field holds an offset from the base of the root node to an array of handles.[0113]
• Each partition ID is used as an index into this array, and the partition node handle is stored at the indexed location. When a new partition is created, this array is examined to find the first partition ID which does not have a corresponding partition node handle and this partition ID is used as the ID for the new partition.[0114]
• communities[0115]
• This field also holds an offset from the base of the root node to an array of handles. Each community ID is used an index into this array, and a community node handle is stored in the array. When a new community is created, this array is examined to find the first community ID which does not have a corresponding community node handle and this community ID is used as the ID for the new community. There cannot be more communities than partitions, so the array is sized based on the maximum number of partitions.[0116]
• max_platform_partition[0117]
• This field holds the maximum number of partitions that can simultaneously exist on the platform, even if additional hardware is added (potentially inswapped).[0118]
• max_fragments[0119]
• This field holds a platform defined maximum number of fragments into which a memory descriptor can be divided. It is used to size the array of fragments in the memory descriptor node.[0120]
• max_desc[0121]
• This field holds the maximum number of memory descriptors for the platform.[0122]
• APMP_id[0123]
• This field holds a system ID set by system software and saved in non-volatile RAM.[0124]
• APMP_id_pad[0125]
• This field holds padding bytes for the APMP ID.[0126]
• bindings[0127]
• This field holds an offset to an array of “bindings” Each binding entry describes a type of hardware node, the type of node the parent must be, the configuration binding, and the affinity binding for a node type. Bindings are used by software to determine how node types are related and configuration and affinity rules.[0128]
• A community provides the basis for the sharing of resources between partitions. While a hardware component may be assigned to any partition in a community, the actual sharing of a device, such as memory, occurs only within a community. The[0129]community node310 contains a pointer to a control section, called an APMP database, which allows the operating system instances to control access and membership in the community for the purpose of sharing memory and communications between instances. The APMP database and the creation of communities are discussed in detail below. The configuration ID for the community is a signed 16-bit integer value assigned by the console program. The ID value will never be greater than the maximum number of partitions that can be created on the platform.
• A partition node, such as[0130]node312 or314, represents a collection of hardware that is capable of running an independent copy of the console program, and an independent copy of an operating system. The configuration ID for this node is a signed 16-bit integer value assigned by the console. The ID will never be greater than the maximum number of partitions that can be created on the platform. The node has the definition:

  	typedef struct_gct_partition_node {

  	GCT_NODE	hd;
  	uint64	hwrpb;
  	uint64	incarnation;
  	uint64	priority;
  	int32	os_type;
  	uint32	partition_reserved_1;
  	uint64	instance_name_format;
  	char	instance_name[128];

  	} GCT_PARTITION_NODE;

• The defined fields have the definitions:[0131]
• hwrpb[0132]
• This field holds the physical address of the hardware restart parameter block for this partition. To minimize changes to the HWRPB, the HWRPB does not contain a pointer to the partition, or the partition ID. Instead, the partition nodes contain a pointer to the HWRPB. System software can then determine the partition ID of the partition in which it is running by searching the partition nodes for the partition which contains the physical address of its HWRPB.[0133]
• incarnation[0134]
• This field holds a value which is incremented each time the primary CPU of the partition executes a boot or restart operation on the partition.[0135]
• priority[0136]
• This field holds a partition priority.[0137]
• Os_type[0138]
• This field holds a value which indicates the type of operating system that will be loaded in the partition.[0139]
• partition_reserved[0140]_—1
• This field is reserved for future use.[0141]
• instance_name_format[0142]
• This field holds a value that describes the format of the instance name string.[0143]
• instance_name[0144]
• This field holds a formatted string which is interpreted using the instance_name_format field. The value in this field provides a high-level path name to the operating system instance executing in the partition. This field is loaded by system software and is not saved across power cycles. The field is cleared at power up and at partition creation and deletion.[0145]
• A System Building Block node, such as[0146]node322 or324, represents an arbitrary piece of hardware, or conceptual grouping used by system platforms with modular designs such as that illustrated in FIG. 2. A QBB (Quad Building Block) is a specific example of an SBB and corresponds to units such asunits100,102,104 and106 in FIG. 1. Children of theSBB nodes322 and324 includeinpuvoutput processor nodes326 and340.
• CPU nodes, such as nodes[0147]328-332 and342-346, are assumed to be capable of operation as a primary CPU for SMP operation. In the rare case where a CPU is not primary capable, it will have a SUBTYPE code indicating that it cannot be used as a primary CPU in SMP operation. This information is critical when configuring resources to create a new partition. The CPU node will also carry information on where the CPU is currently executing. The primary for a partition will have the NODE_CPU_PRIMARY flag set in the NODE_FLAGS field. The CPU node has the following definition:

  	typedef struct_gct_cpu_node {

  GCT_NODE

  hd;

  	} GCT_CPU_NODE;

• A memory subsystem node, such as[0148]node334 or348, is a “pseudo” node that groups together nodes representing the physical memory controllers and the assignments of the memory that the controllers provide. The children of this node consist of one or more memory controller nodes (such asnodes336 and350) which the console has configured to operate together (interleaved), and one or more memory descriptor nodes (such asnodes338 and352) which describe physically contiguous ranges of memory.
• A memory controller node (such as[0149]nodes336 or350) is used to express a physical hardware component, and its owner is typically the partition which will handle errors, and initialization. Memory controllers cannot be assigned to communities, as they require a specific operating system instance for initialization, testing and errors. However, a memory description, defined by a memory descriptor node, may be split into “fragments” to allow different partitions or communities to own specific memory ranges within the memory descriptor. Memory is unlike other hardware resources in that it may be shared concurrently, or broken into “private” areas. Each memory descriptor node contains a list of subset ranges that allow the memory to be divided among partitions, as well as shared between partitions (owned by a community). A memory descriptor node (such asnodes338 or352) is defined as:

  	typedef struct_gct mem_desc_node {

  	GCT_NODE	hd;
  	GCT_MEM_INFO	mem_info
  	int32	mem_frag;

  }GCT_MEM_DESC_NODE;

  The mem_info structure has the following definition:

  typedef struct_gct_mem_info {

  	uint64	base_pa;
  	uint64	base_size;
  	uint32	desc_count
  	uint32	info_fill;

  	}GCT_MEM_INFO:

• The mem-frag field holds an offset from the base of the memory descriptor node to an array of GCT_MEM_DESC structures which have the definition:[0150]

  	typedef struct_gct_mem_desc {

  	uint64	pa;
  	unit64	size;
  	GCT_HANDLE	mem_owner;
  	GCT_HANDLE	mem_current_owner;
  	union {

  uint32

  mem_flags;

  struct {

  	unsigned	mem_console	: 1;
  	unsigned	mem_private	: 1;
  	unsigned	mem_shared	: 1;
  	unsigned	base	: 1;

  	#define CGT_MEM_CONSOLE	0x1
  	#define CGT_MEM_PRIVATE	0x2
  	#define CGT_MEM_SHARED	0x4
  	#define CGT_MEM_CONSOLE	0x8

  } flag_bits;

  }

  flag_union;

  uint32

  mem_fill

  	} GCT_MEM_DESC;

• The number of fragments in a memory description node ([0151]nodes338 or352) is limited by platform firmware. This creates an upper bound on memory division, and limits unbounded growth of the configuration tree. Software can determine the maximum number of fragments from the max_fragments field in the tree root node302 (discussed above), or by calling an appropriate console callback function to return the value. Each fragment can be assigned to any partition, provided that the config binding, and the ownership of the memory descriptor and memory subsystem nodes allow it. Each fragment contains a base physical address, size, and owner field, as well as flags indicating the type of usage.
• To allow shared memory access, the memory subsystem parent node, and the memory descriptor node must be owned by a community. The fragments within the memory descriptor may then be owned by the community (shared) or by any partition within the community.[0152]
• Fragments can have minimum allocation sizes and alignments provided in the[0153]tree root node302. The base memory for a partition (the fragments where the console and operating system will be loaded) may have a greater allocation and alignment than other fragments (see the tree root node definition above). If the owner field of the memory descriptor node is a partition, then the fragments can only be owned by that partition.
• FIG. 4 illustrates the configuration tree shown in FIG. 3 when it is viewed from a perspective of ownership. The console program for a partition relinquishes ownership and control of the partition resources to the operating system instance running in that partition when the primary CPU for that partition starts execution. The concept of “ownership” determines how the hardware resources and CPUs are assigned to software partitions and communities. The configuration tree has ownership pointers illustrated in FIG. 4 which determine the mapping of hardware devices to software such as partitions (exclusive access) and communities (shared access). An operating system instance uses the information in the configuration tree to determine to which hardware resources it has access and reconfiguration control.[0154]
• Passive hardware resources which have no owner are unavailable for use until ownership is established. Once ownership is established by altering the configuration tree, the operating system instances may begin using the resources. When an instance makes an initial request, ownership can be changed by causing the owning operating system to stop using a resource or by a console program taking action to stop using a resource in a partition where no operating system instance is executing. The configuration tree is then altered to transfer ownership of the resource to another operating system instance. The action required to cause an operating system to stop using a hardware resource is operating system specific, and may require a reboot of the operating system instances affected by the change.[0155]
• To manage the transition of a resource from an owned and active state, to a unowned and inactive state, two fields are provided in each node of the tree. The owner field represents the owner of a resource and is loaded with the handle of the owning software partition or community. At power up of an APMP system, the owner fields of the hardware nodes are loaded from the contents of non-volatile RAM to establish an initial configuration.[0156]
• To change the owner of a resource, the handle value is modified in the owner field of the hardware component, and in the owner fields of any descendants of the hardware component which are bound to the component by their config handles. The current_owner field represents the current user of the resource. When the owner and current_owner fields hold the same non-zero value, the resource is owned and active. Only the owner of a resource can de-assign the resource (set the owner field to zero). A resource that has null owner and current_owner fields is unowned, and inactive. Only resources which have null owner and current_owner fields may be assigned to a new partition or community.[0157]
• When a resource is de-assigned, the owner may decide to deassign the owner field, or both the owner and current_owner fields. The decision is based on the ability of the owning operating system instance running in the partition to discontinue the use of the resource prior to de-assigning ownership. In the case where a reboot is required to relinquish ownership, the owner field is cleared, but the current_owner field is not changed. When the owning operating system instance reboots, the console program can clear any current_owner fields for resources that have no owner during initialization.[0158]
• During initialization, the console program will modify the current_owner field to match the owner field for any node of which it is the owner, and for which the current_owner field is null. System software should only use hardware of which it is the current owner. In the case of a de-assignment of a resource which is owned by a community, it is the responsibility of system software to manage the transition between states. In some embodiments, a resource may be loaned to another partition. In this condition, the owner and current_owner fields are both valid, but not equal. The following table summarizes the possible resource states and the values of the owner and current_owner fields:[0159]

  TABLE 1
  owner field value	current_owner field value	Resource State
  none	none	unowned, and inactive
  none	valid	unowned, but still active
  valid	none	owned, not yet active
  valid	equal to owner	owned and active
  valid	is not equal to owner	loaned

• Because CPUs are active devices, and sharing of CPUs means that a CPU could be executing in the context of a partition which may not be its “owner”, ownership of a CPU is different from ownership of a passive resource. The CPU node in the configuration tree provides two fields that indicate which partition a CPU is nominally “owned” by, and in which partition the CPU is currently executing. The owner field contains a value which indicates the nominal ownership of the CPU, or more specifically, the partition in which the CPU will initially execute at system power up.[0160]
• Until an initial ownership is established (that is, if the owner field is unassigned), CPUs are placed into a HWRPB context decided by the master console, but the HWRPB available bit for the CPU will not be set in any HWRPB. This combination prevents the CPU from joining any operating system instance in SMP operation. When ownership of a CPU is established (the owner field is filled in with a valid partition handle), the CPU will migrate, if necessary, to the owning partition, set the available bit in the HWRPB associated with that partition, and request to join SMP operation of the instance running in that partition, or join the console program in SMP mode. The combination of the present and available bits in the HWRPB tell the operating system instance that the CPU is available for use in SMP operation, and the operating system instance may use these bits to build appropriate per-CPU data structures, and to send a message to the CPU to request it to join SMP operation.[0161]
• When a CPU sets the available bit in an HWRPB, it also enters a value into the current_owner field in its corresponding CPU node in the configuration tree. The current_owner field value is the handle of the partition in which the CPU has set the active HWRPB bit and is capable of joining SMP operation. The current_owner field for a CPU is only set by the console program. When a CPU migrates from one partition to another partition, or is halted into an unassigned state, the current_owner field is cleared (or changed to the new partition handle value) at the same time that the available bit is cleared in the HWRPB. The current_owner field should not be written to directly by system software, and only reflects which HWRPB has the available bit set for the CPU.[0162]
• During runtime, an operating system instance can temporarily “loan” a CPU to another partition without changing the nominal ownership of the CPU. The traditional SMP concept of ownership using the HWRPB present and available bits is used to reflect the current execution context of the CPU by modifying the HWRPB and the configuration tree in atomic operations. The current_owner field can further be used by system software in one of the partitions to determine in which partition the CPU is currently executing (other instances can determine the location of a particular CPU by examining the configuration tree.)[0163]
• It is also possible to de-assign a CPU and return it into a state in which the available bit is not set in any HWRPB, and the current_owner field in the configuration tree node for the CPU is cleared. This is accomplished by halting the execution of the CPU and causing the console program to clear the owner field in the configuration tree node, as well as the current_owner field and the available HWRPB bit. The CPU will then execute in console mode and poll the owner field waiting for a valid partition handle to be written to it. System software can then establish a new owner, and the CPU begin execution in the new partition.[0164]
• Illustrative ownership pointers are illustrated in FIG. 4 by arrows. Each of the nodes in FIG. 4 that corresponds to a similar node in FIG. 3 is given a corresponding number. For example, the software root node denoted in FIG. 3 as[0165]node306 is denoted asnode406 in FIG. 4. As shown in FIG. 4, thecommunity410 is “owned” by thesoftware root406. Likewise, thesystem building blocks 1 and 2 (422 and425) are owned by thecommunity410. Similarly,partitions412 and414 are also owned by thecommunity410.
• [0166]Partition412 owns CPUs428-432 and the I/O processor426. Thememory controller436 is also a part of partition 1 (412). In a like manner, partition 2 (414) owns CPUs442-446, I/O processor440 andmemory controller450.
• The common or shared memory in the system is comprised of[0167]memory subsystems434 and448 andmemory descriptors438 and452. These are owned by thecommunity410. Thus, FIG. 4 describes the layout of the system as it would appear to the operating system instances.
• Operating System Characteristics[0168]
• As previously mentioned, the illustrative computer system can operate with several different operating systems in different partitions. However, conventional operating systems may need to be modified in some aspects in order to make them compatible with the inventive system, depending on how the system is configured. Some sample modifications for the illustrative embodiment are listed below:[0169]
• 1. Instances may need to be modified to include a mechanism for choosing a “primary” CPU in the partition to run the console and be a target for communication from other instances. The selection of a primary CPU can be done in a conventional manner using arbitration mechanisms or other conventional devices.[0170]
• 2. Each instance may need modifications that allow it to communicate and cooperate with the console program which is responsible for creating a configuration data block that describes the resources available to the partition in which the instance is running. For example, the instance should not probe the underlying hardware to determine what resources are available for usage by the instance. Instead, if it is passed a configuration data block that describes what resources that instance is allowed to access, it will need to work with the specified resources.[0171]
• 3. An instance may need to be capable of starting at an arbitrary physical address and may not be able to reserve any specific physical address in order to avoid conflicting with other operating systems running at that particular address.[0172]
• 4. An instance may need to be capable of supporting multiple arbitrary physical holes in its address space, if it is part of a system configuration in which memory is shared between partitions. In addition, an instance may need to deal with physical holes in its address space in order to support “hot inswap” of memory.[0173]
• 5. An instance may need to pass messages and receive notifications that new resources are available to partitions and instances. More particularly, a protocol is needed to inform an instance to search for a new resource. Otherwise, the instance may never realize that the resource has arrived and is ready for use.[0174]
• 6. An instance may need to be capable of running entirely within its “private memory” if it is used in a system where instances do not share memory. Alternatively, an instance may need to be capable of using physical “shared memory” for communicating or sharing data with other instances running within the computer if the instance is part of a system in which memory is shared. In such a shared memory system, an instance may need to be capable of mapping physical “shared memory” as identified in the configuration tree into its virtual address space, and the virtual address spaces of the “processes” running within that operating system instance.[0175]
• 7. Each instance may need some mechanism to contact another CPU in the computer system in order to communicate with it.[0176]
• 8. An instance may also need to be able to recognize other CPUs that are compatible with its operations, even if the CPUs are not currently assigned to its partition. For example, the instance may need to be able to ascertain CPU parameters, such as console revision number and clock speed, to determine whether it could run with that CPU, if the CPU was re-assigned to the partition in which the instance is running.[0177]
• Changing the Configuration Tree[0178]
• Each console program provides a number of callback functions to allow the associated operating system instance to change the configuration of the APMP system, for example, by creating a new community or partition, or altering the ownership of memory fragments. In addition, other callback functions provide the ability to remove a community, or partition, or to start operation on a newly-created partition.[0179]
• However, callback functions do not cause any changes to take place on the running operating system instances. Any changes made to the configuration tree must be acted upon by each instance affected by the change. The type of action that must take place in an instance when the configuration tree is altered is a function of the type of change, and the operating system instance capabilities. For example, moving an input/output processor from one partition to another may require both partitions to reboot. Changing the memory allocation of fragments, on the other hand, might be handled by an operating system instance without the need for a reboot.[0180]
• Configuration of an APMP system entails the creation of communities and partitions, and the assignment of unassigned components. When a component is moved from one partition to another, the current owner removes itself as owner of the resource and then indicates the new owner of the resource. The new owner can then use the resource. When an instance running in a partition releases a component, the instance must no longer access the component. This simple procedure eliminates the complex synchronization needed to allow blind stealing of a component from an instance, and possible race conditions in booting an instance during a reconfiguration.[0181]
• Once initialized, configuration tree nodes will never be deleted or moved, that is, their handles will always be valid. Thus, hardware node addresses may be cached by software. Callback functions which purport to delete a partition or a community do not actually delete the associated node, or remove it from the tree, but instead flag the node as UNAVAILABLE, and clear the ownership fields of any hardware resource that was owned by the software component.[0182]
• In order to synchronize changes to the configuration tree, the root node of the tree maintains two counters (transient_level and current_level). The transient_level counter is incremented at the start of an update to the tree, and the current_level counter is incremented when the update is complete. Software may use these counters to determine when a change has occurred, or is occurring to the tree. When an update is completed by a console, an interrupt can be generated to all CPUs in the APMP system. This interrupt can be used to cause system software to update its state based on changes to the tree.[0183]
• Creation of an APMP Computer System[0184]
• FIG. 5 is a flowchart that illustrates an overview of the formation of the illustrative adaptively-partitioned, multi-processor (APMP) computer system. The routine starts in[0185]step500 and proceeds to step502 where a master console program is started. If the APMP computer system is being created on power up, the CPU on which the master console runs is chosen by a predetermined mechanism, such as arbitration, or another hardware mechanism. If the APMP computer system is being created on hardware that is already running, a CPU in the first partition that tries to join the (non-existent) system runs the master console program, as discussed below.
• Next, in[0186]step504, the master console program probes the hardware and creates the configuration tree instep506 as discussed above. If there is more than one partition in the APMP system on power up, each partition is initialized and its console program is started (step508).
• Finally, an operating system instance is booted in at least one of the partitions as indicated in[0187]step510. The first operating system instance to boot creates an APMP database and fills in the entries as described below. APMP databases store information relating to the state of active operating system instances in the system. The routine then finishes instep512. It should be noted that an instance is not required to participate in an APMP system. The instance can choose not to participate or to participate at a time that occurs well after boot. Those instances which do participate form a “sharing set.” The first instance which decides to join a sharing set must create it. There can be multiple sharing sets operating on a single APMP system and each sharing set has its own APMP database.
• Deciding to Create a New APMP System or to Join an Existing APMP System[0188]
• An operating system instance running on a platform which is also running the APMP computer system does not necessarily have to be a member of the APMP computer system. The instance can attempt to become a member of the APMP system at any time after booting. This may occur either automatically at boot, or after an operator-command explicitly initiates joining. After the operating system is loaded at boot time, the operating system initialization routine is invoked and examines a stored parameter to see whether it specifies immediate joining and, if so, the system executes a joining routine which is part of the APMP computer system. An operator command would result in an execution of the same routine.[0189]
• APMP Database[0190]
• An important data structure supporting the inventive software allocation of resources is the APMP database which keeps track of operating system instances which are members of a sharing set. The first operating system instance attempting to set up the APMP computer system initializes an APMP database, thus creating, or instantiating, the inventive software resource allocations for the initial sharing set. Later instances wishing to become part of the sharing set join by registering in the APMP database associated with that sharing set. The APMP database is a shared data structure containing the centralized information required for the management of shared resources of the sharing set. An APMP database is also initialized when the APMP computer system is re-formed in response to an unrecoverable error.[0191]
• More specifically, each APMP database is a three-part structure. The first part is a fixed-size header portion including basic synchronization structures for creation of the APMP computer system, address-mapping information for the database and offsets to the service-specific segments that make up the second portion. The second portion is an array of data blocks with one block assigned to each potential instance. The data blocks are called “node blocks.” The third portion is divided into segments used by each of the computer system sub-facilities. Each sub-facility is responsible for the content of, and synchronizing access to, its own segment.[0192]
• The initial, header portion of an APMP database is the first part of the APMP database mapped by a joining operating system instance. Portions of the header are accessed before the instance has joined the sharing set, and, in fact, before the instance knows that the APMP computer system exists.[0193]
• The header section contains:[0194]
• 1. a membership and creation synchronization quadword[0195]
• 2. a computer system software version[0196]
• 3. state information, creation time, incarnation count, etc.[0197]
• 4. a pointer (offset) to a membership mask[0198]
• 5. crashing instance, crash acknowledge bits, etc.[0199]
• 6. validation masks, including a bit for each service[0200]
• 7. memory mapping information (page frame number information) for the entire APMP database[0201]
• 8. offset/length pairs describing each of the service segments (lengths in bytes rounded to pages and offsets full pages) including:[0202]
• shared memory services[0203]
• cpu communications services[0204]
• membership services (if required)[0205]
• locking services[0206]
• The array of node blocks is indexed by a system partition id (one per instance possible on the current platform) and each block contains:[0207]
• instance software version[0208]
• interrupt reason mask[0209]
• instance state[0210]
• instance incarnation[0211]
• instance heartbeat[0212]
• instance membership timestamp[0213]
• little brother instance id and inactive-time; big brother instance id[0214]
• instance validation done bit.[0215]
• An APMP database is stored in shared memory. The initial fixed portion of N physically contiguous pages occupies the first N pages of one of two memory ranges allocated by the first instance to join during initial partitioning of the hardware. The instance directs the console to store the starting physical addresses of these ranges in the configuration tree. The purpose of allocating two ranges is to permit failover in case of hardware memory failure. Memory management is responsible for mapping the physical memory into virtual address space for the APMP database.[0216]
• The detailed actions taken by an operating system instance are illustrated in FIG. 6. More specifically, when an operating system instance wishes to become a member of a sharing set, it must be prepared to create the APMP computer system if it is the first instance attempting to “join” a non-existent system. In order for the instance to determine whether an APMP system already exists, the instance must be able to examine the state of shared memory as described above. Further, it must be able to synchronize with other instances which may be attempting to join the APMP system and the sharing set at the same time to prevent conflicting creation attempts. The master console creates the configuration tree as discussed above. Subsequently, a region of memory is initialized by the first, or primary, operating system instance to boot, and this memory region can be used for an APMP database.[0217]
• Mapping the APMP Database Header[0218]
• The goal of the initial actions taken by all operating system instances is to map the header portion of the APMP database and initialize primitive inter-instance interrupt handling to lay the groundwork for a create or join decision. The routine used is illustrated in FIG. 6 which begins in[0219]step600. The first action taken by each instance (step602) is to engage memory management to map the initial segment of the APMP database as described above. At this time, the array of node blocks in the second database section is also mapped. Memory management maps the initial and second segments of the APMP database into the primary operating system address space and returns the start address and length. The instance then informs the console to store the location and size of the segments in the configuration tree.
• Next, in[0220]step604, the initial virtual address of the APMP database is used to allow the initialization routine to zero interrupt reason masks in the node block assigned to the current instance.
• A zero initial value is then stored to the heartbeat field for the instance in the node block, and other node block fields. In some cases, the instance attempting to create a new APMP computer system was previously a member of an APMP system and did not withdraw from the APMP system. If this instance is rebooting before the other instances have removed it, then its bit will still be “on” in the system membership mask. Other unusual or error cases can also lead to “garbage” being stored in the system membership mask.[0221]
• Next, in[0222]step608, the virtual address (VA) of the APMP database is stored in a private cell which is examined by an inter-processor interrupt handler. The handler examines this cell to determine whether to test the per-instance interrupt reason mask in the APMP database header for work to do. If this cell is zero, the APMP database is not mapped and nothing further is done by the handler. As previously discussed, the entire APMP database, including this mask, is initialized so that the handler does nothing before the address is stored. In addition, a clock interrupt handler can examine the same private cell to determine whether to increment the instance-specific heartbeat field for this instance in the appropriate node block. If the private cell is zero, the interrupt handler does not increment the heartbeat field.
• At this point, the routine is finished (step[0223]610) and the APMP database header is accessible and the joining instance is able to examine the header and decide whether the APMP computer system does not exist and, therefore, the instance must create it, or whether the instance will be joining an already-existing APMP system.
• Once the APMP header is mapped, the header is examined to determine whether an APMP computer system is up and functioning, and, if not, whether the current instance should initialize the APMP database and create the APMP computer system. The problem of joining an existing APMP system becomes more difficult, for example, if the APMP computer system was created at one time, but now has no members, or if the APMP system is being reformed after an error. In this case, the state of the APMP database memory is not known in advance, and a simple memory test is not sufficient. An instance that is attempting to join a possibly existing APMP system must be able to determine whether an APMP system exists or not and, if it does not, the instance must be able to create a new APMP system without interference from other instances. This interference could arise from threads running either on the same instance or on another instance.[0224]
• In order to prevent such interference, the create/join decision is made by first locking the APMP database and then examining the APMP header to determine whether there is a functioning APMP computer system. If there is a properly functioning APMP system, then the instance joins the system and releases the lock on the APMP database. Alternatively, if there is no APMP system, or if the there is an APMP system, but it is non-functioning, then the instance creates a new APMP system, with itself as a member and releases the lock on the APMP database.[0225]
• If there appears to be an APMP system in transition, then the instance waits until the APMP system is again operational or dead, and then proceeds as above. If a system cannot be created, then joining fails.[0226]
• Creating a new APMP Computer System[0227]
• Assuming that a new APMP system must be created, the creator instance is responsible for allocating the rest of the APMP database, initializing the header and invoking system services. Assuming the APMP database is locked as described above, the following steps are taken by the creator instance to initialize the APMP system (these steps are shown in FIGS.[0228]7A and7B):
• [0229]Step702 the creator instance sets the APMP system state and its node block state to “initializing.”
• [0230]Step704 the creator instance calls a size routine for each system service with the address of its length field in the header.
• [0231]Step706 the resulting length fields are summed and the creator instance calls memory management to allocate space for the entire APMP database by creating a new mapping and deleting the old mapping.
• [0232]Step708 the creator instance fills in the offsets to the beginnings of each system service segment.
• [0233]Step710 the initialization routine for each service is called with the virtual addresses of the APMP database, the service segment and the segment length.
• [0234]Step712 the creator instance initializes a membership mask to make itself the sole member and increments an incarnation count. It then sets creation time, software version, and other creation parameters.
• [0235]Step714 the instance then sets itself as its own big and little brother (for heartbeat monitoring purposes as described below).
• [0236]Step716 the instance then fills in its instance state as “member” and the APMP system state as “operational.”
• [0237]Step718 finally, the instance releases the APMP database lock.
• The routine then ends in[0238]step720.
• Joining an Existing APMP Computer System[0239]
• Assuming an instance has the APMP database locked, the following steps are taken by the instance to become a member of an existing APMP system (shown in FIGS.[0240]8A and8B):
• [0241]Step802 the instance checks to make sure that its instance name is unique. If another current member has the instance's proposed name, joining is aborted.
• [0242]Step804 the instance sets the APMP system state and its node block state to “instance joining”Step806 the instance calls a memory management routine to map the variable portion of the APMP database into its local address space. Step808 the instance calls system joining routines for each system service with the virtual addresses of the APMP database and its segment and its segment length.
• [0243]Step810 if all system service joining routines report success, then the instance joining routine continues. If any system service join routine fails, the instance joining process must start over and possibly create a new APMP computer system.
• [0244]Step812 assuming that success was achieved instep810, the instance adds itself to the system membership mask.
• [0245]Step814 the instance selects a big brother to monitor its instance health as set forth below.
• [0246]Step816 the instance fills in its instance state as “member” and sets a local membership flag. Step818 the instance releases the configuration database lock.
• The routine then ends in[0247]step820.
• The loss of an instance, either through inactivity timeout or a crash, is detected by means of a “heartbeat” mechanism implemented in the APMP database. Instances will attempt to do minimal checking and cleanup and notify the rest of the APMP system during an instance crash. When this is not possible, system services will detect the disappearance of an instance via a software heartbeat mechanism. In particular, a “heartbeat” field is allocated in the APMP database for each active instance. This field is written to by the corresponding instance at time intervals that are less than a predetermined value, for example, every two milliseconds.[0248]
• Any instance may examine the heartbeat field of any other instance to make a direct determination for some specific purpose. An instance reads the heartbeat field of another instance by reading its heartbeat field twice separated by a two millisecond time duration. If the heartbeat is not incremented between the two reads, the instance is considered inactive (gone, halted at control-P, or hung at or above clock interrupt priority level.) If the instance remains inactive for a predetermined time, then the instance is considered dead or disinterested.[0249]
• In addition, a special arrangement is used to monitor all instances because it is not feasible for every instance to watch every other instance, especially as the APMP system becomes large. This arrangement uses a “big brother—little brother” scheme. More particularly, when an instance joins the APMP system, before releasing the lock on the APMP database, it picks one of the current members to be its big brother and watch over the joining instance. The joining instance first assumes big brother duties for its chosen big brother's current little brother, and then assigns itself as the new little brother of the chosen instance. Conversely, when an instance exits the APMP computer system while still in operation so that it is able to perform exit processing, and while it is holding the lock on the APMP database, it assigns its big brother duties to its current big brother before it stops incrementing its heartbeat.[0250]
• Every clock tick, after incrementing its own heartbeat, each instance reads its little brother's heartbeat and compares it to the value read at the last clock tick. If the new value is greater, or the little brother's ID has changed, the little brother is considered active. However, if the little brother ID and its heartbeat value are the same, the little brother is considered inactive, and the current instance begins watching its little brother's little brother as well. This accumulation of responsibility continues to a predetermined maximum and insures that the failure of one instance does not result in missing the failure of its little brother. If the little brother begins incrementing its heartbeat again, all additional responsibilities are dropped.[0251]
• If a member instance is judged dead, or disinterested, and it has not notified the APMP computer system of its intent to shut down or crash, the instance is removed from the APMP system. This may be done, for example, by setting the “bugcheck” bit in the instance primitive interrupt mask and sending an IP interrupt to all CPU's of the instance. As a rule, shared memory may only be accessed below the hardware priority of the IP interrupt. This insures that if the CPUs in the instance should attempt to execute at a priority below that of the IP interrupt, the IP interrupt will occur first and thus the CPU will see the “bugcheck” bit before any lower priority threads can execute. This insures the operating system instance will crash and not touch shared resources such as memory which may have been reallocated for other purposes when the instances were judged dead. As an additional or alternative mechanism, a console callback (should one exist) can be invoked to remove the instance. In addition, in accordance with a preferred embodiment, whenever an instance disappears or drops out of the APMP computer system without warning, the remaining instances perform some sanity checks to determine whether they can continue. These checks include verifying that all pages in the APMP database are still accessible, i.e. that there was not a memory failure.[0252]
• Assignment of Resources After Joining[0253]
• A CPU can have at most one owner partition at any given time in the power-up life of an APMP system. However, the reflection of that ownership and the entity responsible for controlling it can change as a result of configuration and state transitions undergone by the resource itself, the partition it resides within, and the instance running in that partition.[0254]
• CPU ownership is indicated in a number of ways, in a number of structures dictated by the entity that is managing the resource at the time. In the most basic case, the CPU can be in an unassigned state, available to all partitions that reside in the same sharing set as the CPU. Eventually that CPU is assigned to a specific partition, which may or may not be running an operating system instance. In either case, the partition reflects its ownership to all other partitions through the configuration tree structure, and to all operating system instances that may run in that partition through the AVAILABLE bit in the HWRPB per-CPU flags field.[0255]
• If the owning partition has no operating system instance running on it, its console is responsible for responding to, and initiating, transition events on the resources within it. The console decides if the resource is in a state that allows it to migrate to another partition or to revert back to the unassigned state.[0256]
• If, however, there is an instance currently running in the partition, the console relinquishes responsibility for initiating resource transitions and is responsible for notifying the running primary of the instance when a configuration change has taken place. It is still the facilitator of the underlying hardware transition, but control of resource transitions is elevated one level up to the operating system instance. The transfer of responsibility takes place when the primary CPU executes its first instruction outside of console mode in a system boot.[0257]
• Operating system instances can maintain ownership state information in any number of ways that promote the most efficient usage of the information internally. For example, a hierarchy of state bit vectors can be used which reflect the instance-specific information both internally and globally (to other members sharing an APMP database).[0258]
• The internal representations are strictly for the use of the instance. They are built up at boot time from the underlying configuration tree and HWRPB information, but are maintained as strict software constructs for the life of the operating system instance. They represent the software view of the partition resources available to the instance, and may—through software rule sets—further restrict the configuration to a subset of that indicated by the physical constructs. Nevertheless, all resources in the partition are owned and managed by the instance—using the console mechanisms to direct state transitions—until that operating system invocation is no longer a viable entity. That state is indicated by halting the primary CPU once again back into console mode with no possibility of returning without a reboot.[0259]
• Ownership of CPU resources never extends beyond the instance. The state information of each individual instance is duplicated in an APMP database for read-only decision-making purposes, but no other instance can force a state transition event for another's CPU resource. Each instance is responsible for understanding and controlling its own resource set; it may receive external requests for its resources, but only it can make the decision to allow the resources to be transferred.[0260]
• When each such CPU becomes operational, it does not set its AVAILABLE bit in the per-CPU flags. When the AVAILABLE bit is not set, no instance will attempt to start, nor expect the CPU to join in SMP operation. Instead, the CPU, in console mode, polls the owner field in the configuration tree waiting for a valid partition to be assigned. Once a valid partition is assigned as the owner by the primary console, the CPU will begin operation in that partition.[0261]
• During runtime, the current_owner field reflects the partition where a CPU is executing. The AVAILABLE bit in the per-CPU flags field in the HWRPB remains the ultimate indicator of whether a CPU is actually available, or executing, for SMP operation with an operating system instance, and has the same meaning as in conventional SMP systems.[0262]
• It should be noted that an instance need not be a member of a sharing set to participate in many of the reconfiguration features of an APMP computer system. An instance can transfer its resources to another instance in the APMP system so that an instance which is not a part of a sharing set can transfer a resource to an instance which is part of the sharing set. Similarly, the instance which is not a part of the sharing set can receive a resource from an instance which is part of the sharing set.[0263]
• Shared Memory[0264]
• Through software configuration, recorded in the console configuration tree, some memory is marked as shared among all instances in a community. Some memory is marked as private to a partition which can be running an instance of an operating system. All other memory is marked as unowned. Since the configuration is defined by software, it is possible to dynamically change partitions and the relative sizes of partitions.[0265]
• All memory within the physical hardware system is associated with an owner field within the configuration tree. Memory can be owned by a partition, in which case the memory is used as private memory by the operating system or console software running within the partition. This is referred to as “private” memory. Alternatively, memory may be owned by a community, in which case, the memory is shared for all instances within the community and such memory is referred to as “shared” memory. Memory can also be configured to be owned by no partition or community. Such “unowned” memory may be powered down and out-swapped while the remainder of the system continues to operate, if hardware allows such “hot out-swapping”.[0266]
• Memory can be shared among instances in a community through the use of shared memory regions. A shared memory region can be created by any instance. A tag is specified to coordinate access to the same region by multiple instances. A virtual size is specified as well as a physical size. The virtual size may be the same size or larger than the physical size. Shared memory is initialized by a call-back routine. A lock is held during initialization to block out other instances from mapping to the region while the region is being initialized. Once the shared memory region is created by one instance, other instances can be mapped and attached to the region. A zero page table entry is used to indicate pages that are part of the region virtually but do not have physical memory associated with them. The memory region data structure records which instances have attached to the region. An instance must specify a call-back routine when attaching to a shared memory region. This routine is called for a variety of reasons: during initialization or shutdown of the system, or whenever another instance is attaching to or detaching from the region, or whenever an instance that was attached has crashed (detached in an unorderly fashion). Depending upon the call-back reason, during shutdown, for example, the call-back routine is expected to block access to the shared memory region.[0267]
• An instance can request that more physical memory be added to a region. Only the instance that makes this request initially maps these new pages. When another instance attempts to access these pages, an access violation handler gains control (because that instance will have a zero page table entry (PTE) associated with that memory region), and the access violation handler updates the mapping region with any new pages. When an instance unmaps the region, the detachment is recorded in the APMP database. When all instances have detached from a region, it can be deleted and all pages released to a shared memory free page list. The shared memory region data structure also records which instances have outstanding I/O on any page within the region. The operating system instances record their individual reference counters such that they know when to set and clear their I/O bit in the region. An instance cannot unmap and detach from a shared memory region if it has outstanding I/O to any page within the region.[0268]
• A shared memory API is a set of routines that can be called by user mode applications and maps shared memory into the application's address space. When a shared memory region is created, as described above, the associated creating instance keeps track of how the operating system's data structures relate to the shared memory region. When the instance has created data structures for the shared memory region, the instance is attached to the region. Then, when the shared memory mapping API routine is called, normal operating system mechanisms are used to map the application address space to the shared memory. When the local operating system data structures are cleaned up, the instance is detached from the region. A global section may be associated with a shared memory region in a one-to-one fashion.[0269]
• An instance may specify a “context variable” which is to be associated with a region. If another instance attempts to attach to a region and does not specify the same context, an error is returned. This specification of a context variable may be used, for example, to associate a version number with the application. Additionally, an instance may specify a private context variable to be associated with the instance private data stored for a region. When the call-back routine is called, the instance can gather additional information about the region by obtaining the private context variable. The private context may be used, for example, to store a port number.[0270]
• Shared memory can be borrowed by an operating system instance for use as instance private memory. Shared memory can be borrowed through the use of the shared memory API. Shared memory can be created, then used by only the local instance. This technique is useful if not all memory marked as shared is being used by the community member instances. The extra shared memory can be a pooled source of free memory. In other words, shared memory can be borrowed by the creation of a shared memory region. The pages in the shared memory region can be used by the local operating system for various purposes.[0271]
• Private memory can be configured to be owned by the instance whose CPU(s) have fastest access to the memory. Nonuniform memory access is accommodated in the design's shared memory by organizing internal data structures for shared memory in groups according to the hardware characteristics of the memory. These internal data structures are called common property partitions. The shared memory API allows for memory characteristics to be specified by the caller. These characteristics can be expressed as nonuniform memory access properties such as “near” or “far”.[0272]
• The PFN database accommodates private memory and shared memory and reconfigured memory using a large array of page frame number (PFN) database entries. There is no physical memory behind a virtual array that describes pages that are private to another instance, nor corresponding to memory locations supported by memory boards that are missing from the system, nor corresponding to physical memory addressing holes. The layout of the PFN database suggests a particular granularity of physical memory. That is, in order to allocate and consume an integral number of physical pages for the PFN database that is to reside within each block of memory, physical memory should have a granularity as described below. The granularity of physical memory is chosen as the smallest amount of memory that contains an integral number of pages and an integral number of PFN database entries. This is given by the least common multiple of the memory page size and the page frame number database entries, in quad words.[0273]
• As described above, a creating instance, more specifically, the APMP computer system's initialization program, walks the configuration tree and builds management structures for its associated community's shared memory. In general, four hierarchical access modes provide memory access control. The access modes are, from the most to least privileged: kernel, executive, supervisor and user. Additionally, memory protection is specified at individual page level, where a page may be inaccessible, read only, or read/write for each of the four access modes. Accessible pages can be restricted to have only data or instruction access. Memory management software maintains tables of mapping information (page tables) that keep track of where each virtual page is located in physical memory. A process, through a memory management unit, utilizes this mapping information when it translates virtual addresses to physical addresses. The virtual address space is broken into units of relocation, sharing, and protection pages, which are referred to as pages. An operating system instance controls the virtual-to-physical mapping tables and saves the inactive parts of the virtual memory address space on external storage media.[0274]
• Memory management employs, illustratively, a quad word page table entry to translate virtual addresses to physical addresses. Each page table entry (PTE) includes a page frame number (PFN) which points to a page boundary and may be concatenated with a byte-within-page indicator of a virtual address to yield a physical address.[0275]
• Physical address translation is performed by accessing entries in a multi-level page structure. A page table base register (PTBR) contains the physical PFN of the highest level page table. Bits of the virtual address are used to index into the higher level page tables to obtain the physical PFNs of the base lower level page tables and, at the lowest level, to obtain the physical PFN of the page being referenced. This PFN is concatenated with the virtual address byte-within-page indicator to obtain the physical address of the location being accessed.[0276]
• As noted above, an instance may decide to join the operation of a community at any time, not necessarily at system boot time. When an instance decides to join the APMP system, it calls a routine DB_MAP_initial, which obtains the APMP data base pages from the configuration tree community node and maps the initial piece of the APMP database. If the configuration tree does not contain APMP database pages yet, the instance chooses shared memory pages to be used for the APMP database. The instance calls console code to write to the configuration tree in an asynchronous manner. After mapping the initial piece of the APMP database, it is determined as described above whether the instance is creating or joining the APMP system. If the instance is the creator of the APMP system, the instance calls a routine, DB_allocate, to allocate the pages for the APMP database and to initialize the mapping information within a MMAP data structure. The MMAP data structure, which is discussed in greater detail below, is used to describe a mapping of shared memory. The routine DB_allocate does not unmap the initial piece of the APMP database. If the instance is a joiner of a APMP system, the instance calls a routine DB_Map_continue to map the APMP database. The routine DB_Map_continue does not unmap the initial piece of the APMP database. Once the APMP database is mapped and the joining instance's code has switched to referencing the newly mapped APMP database, rather than the initial APMP database, the initial APMP database is unmapped by calling a routine, DB_unmap. This routine can also be called to unmap the APMP database when an instance is leaving the APMP system.[0277]
• The APMP database need not be located at the same virtual location for all instances, as this would prevent instances from joining the APMP system if a given range of virtual addresses were unavailable. This flexibility permits different operating systems having different virtual address space layouts to readily coexist in the new APMP system.[0278]
• The DB_Map_initial routine maps the initial piece of the APMP database, accepts the length of the initial APMP database and returns the virtual address of the initial APMP database. Additionally, DB_Map_initial will test the mapped pages to ensure that the pages are from shared memory and to mark any bad pages.[0279]
• The DB_allocate routine accepts the full address of the initial APMP database, the length of the initial APMP database, and the length of the entire APMP database. The routine returns the virtual address of the entire APMP database. The routine allocates sufficient instance address space to map the entire APMP database and remaps the initial piece of the APMP database in the beginning of this space. More APMP database pages are mapped from shared memory, as necessary. These pages may be tested and if a bad page is encountered, it is marked as used. The rest of the APMP database pages are mapped in the appropriate page table entries. Contiguous pages are allocated for the APMP database PFN list. The APMP database PFNs are stored in the PFN list pages, with any unused entries zeroed out. If enough contiguous pages are available for the entire APMP database, no PFN list pages are used. Shared pages are allocated directly from configuration tree and are taken from the page directly after the initial APMP database pages.[0280]
• The DB_Map_continue routine maps the entire APMP database if a caller is not the creator of the APMP system. The routine accepts the virtual address of the initial APMP database and the length of the initial APMP database. The routine returns the starting virtual address of the entire APMP database and the length of the entire APMP database.[0281]
• Each operating system instance includes memory configuration information functions which focus on the memory aspects of the configuration tree. A MEM-CONFIG_INFO routine returns basic memory configuration information by reading the configuration tree fields MAX_DESC and MAX_FRAGMENTS and returning the maximum number of memory descriptor nodes and the maximum number of memory fragments per descriptor node. A MEM_CONFIG_PFN routine determines which partition owns a given PFN. This routine accepts a page frame number and returns an indication of what type of page it is, that is, whether the page is shared or private to a particular partition, an input/output (I/O) page, or unowned memory. Additionally, if the page is private or used to access I/O devices, the routine returns an indication of which partition owns this PFN and, if the page is shared, which community owns the PFN. The SHMEM_CONFIG_DESC routine returns shared memory information about a memory descriptor in the configuration tree. Once a memory descriptor node is found, the routine searches the memory fragments for those fragments that are marked shared and fills in a return buffer with the PFN and page count for each fragment. If there are no memory fragments marked shared, a fragment count is set to zero.[0282]
• The SHMEM_CONFIG_ALL routine returns information about all memory descriptor nodes that contain shared memory. The routine calls SHMEM_CONFIG_DESC in a loop to obtain all shared memory page ranges. Input arguments include the maximum number of memory descriptor nodes and the maximum number of memory fragments per descriptor node. The routine returns the total number of shared memory fragments from an array of structures that describe the shared memory ranges.[0283]
• A routine SHMEM_CONFIG_APMP sets up the APMP PFN range in the configuration tree. If the APMP PFN range has already been set up, it returns the information. The routine returns the first PFN to use for the APMP database and number of APMP pages. This routine reads a value within a community node and if the value is zero, it obtains the first contiguous range of shared memory, eight megabytes in the illustrative embodiment, by calling the SHMEM_CONFIG_DESC routine. Then it calls the console dispatch routine to set this range in the community node. If there was a race to set the APMP page range, the range set in the configuration tree will be read and returned to the caller.[0284]
• A shared memory management data structure in the APMP database SHMEM includes version number, the size of the fixed part of the SHMEM structure, flags that indicate whether the shared memory is valid, whether initialization is in progress, whether debug structure formats are being used, whether all pages within all shared memory common property partitions have been tested, and the maximum number of shared memory common property partitions. Additionally, the data structure includes the total number of valid shared memory common property partitions, the size of one shared memory common property partition structure, offsets from the beginning of the shared memory data structure to the shared memory common property partition array, an offset from the beginning of the shared memory data structure to the shared memory lock structure, a shared memory lock handle, and the maximum number of shared memory regions supported within the APMP system. The data structure also includes the total number of valid shared memory regions and an offset from the beginning of the shared memory data structure to the shared memory region tag array. The size of a shared memory region structure, and the offset from the beginning of the shared memory management data structure to the shared memory region array is also included.[0285]
• Instance private memory data cells contain information about the shared memory management area in the APMP database. This information includes a pointer to the beginning of the shared memory data structure and the same descriptors as were described in relation to the shared memory data structure: the maximum number of shared memory common property partitions, maximum number of memory fragments in each shared memory common property partition, the size of one shared memory common property partition structure, a pointer to a shared memory common property partition array within the APMP database, a pointer to a shared memory list and a pointer to a shared memory region tag array within the APMP database. Additionally, the maximum number of shared memory regions, the size of one shared memory region structure, a pointer to a shared memory region array within the APMP database, and a pointer to the shared memory descriptor array in private memory are included.[0286]
• When a shared memory common property partition (CPP) configuration area is initialized, the APMP database pages are excluded. Shared memory common property partitions support hot-swapping and non-uniform memory access by partitioning shared memory into partitions having common properties. Flags and routines are employed to indicate, for example, which non-uniform memory access unit a CPP is in, or which hot swappable unit a CPP is in, along with the range and location of memory pages within the unit. Each instance that is a member of an APMP system maintains data within its own private memory regarding each shared memory CPP that it is connected to. A lock structure is employed to synchronize access to the shared memory common property partition data structure. The lock is held when a partition is connecting to the shared memory CPP, when a partition is disconnecting from a shared memory CPP, when pages are being allocated from the shared memory CPP, or when pages are being deallocated to the shared memory CPP. Each shared memory CPP has a free page list, a bad page list, and an untested page list. Pages can be allocated from the free page and untested page lists and deallocated into the free page list and bad page list. The shared memory CPP page list links are maintained within the PFN database entries for the pages.[0287]
• The shared memory lock is employed to synchronize the SHM_TAG array and an associated list of valid SHM_REG structures and to synchronize access to the list of free SHM_REG structures. The SHMEM lock must be held while reading or writing the SHM_TAG array, while manipulating a list of valid SHM_REG structures, or while manipulating the free SHM_REG list. Shared memory locks are ranked as follows: the highest order lock is an IPL 8 SMP spinlock, followed by the SHM_CPP lock, the SHM_REG lock and, finally, the SHMEM lock. For example, while holding the SHMEM lock, one can acquire a SHM_REG lock, a SHM_CPP lock and/or a SMP spinlock, in that order. Shared memory management functions can be called from kernel mode to get information about shared memory. The SHMEM lock has a ranking relative to other locks such that no deadlocks occur.[0288]
• Reconfiguring Memory[0289]
• The Page Frame Number (PFN) database design allows for memory to be reconfigured into or out of the operating system instance under software control. Private memory may be reconfigured to be shared, shared memory may be reconfigured to be private, and memory which is private to one partition may be reconfigured to be private to another partition. Memory which is private or shared may also be reconfigured to be unowned. Memory reconfiguration can support hardware hot in-swapping, or hot out-swapping. When memory is in an “unowned” state in a configuration tree, it can be reconfigured into an instance's private memory, or as part of shared memory in a community. When new memory is in-swapped into a system, the memory is initially placed in the unowned state. Additionally, before memory can be out-swapped from a system it must be in the unowned state. Therefore, to support memory hot-swapping, the operating system instance and console software must reconfigure memory into and out of the unowned state. When reconfiguring memory, the range of pages is, illustratively, 8 megabyte (MB) aligned (system page size squared divided 8 bytes). The range of pages is a multiple of 8 MB in size and, if pages within the range to be reconfigured out of the system are in use, other restrictions may apply, as described below.[0290]
• New memory may be added to the system at any time since the PFN database is sized to include all possible memory that can be in-swapped and the new pages can always be used to make up the PFN database entry pages. To remove memory from a system, it is first determined if the range of pages is private, shared, or unowned. If the memory is already marked unowned, it is considered to be removed.[0291]
• For the removal of private memory, a removed page list of page frame numbers, similar to a free page list, is established to support the removal of memory. If it is determined at any time that the pages cannot be removed on line, the system can be shut-down, the pages configured as unowned with console software, and the operating system instance restarted. If the console is using some or all of the pages in the range, the console relocates itself to a different set of pages. This relocation may be accomplished in a variety of ways. For example, the console may copy its pages to another sort of pages owned by the partition, then start executing on the other set of pages. Alternatively, another console within another partition can dissolve the partition, reassign the range of pages to “unowned”, then reform the partition without the memory. Additionally, the entire system could be shut down, the memory removed, and the system restarted. The removal operation can be abandoned at anytime by moving the pages from the removed page list to the free, zeroed, or bad page lists.[0292]
• If the range of pages to be removed is in private memory, the following steps are repeated until all pages can be removed or the removal operation is abandoned. The process is illustrated in the flowchart of FIG. 9. Before entering the process illustrated in the flowchart of FIG. 9, it is determined whether there is sufficient memory to allow the removal of the memory. A system parameter, fluid page count, is typically employed to indicate the amount of spare memory readily available. If this fluid page count is too low, that is if there are insufficient fluid pages in the system to accommodate the removal, an error is returned to the user, otherwise, each page in the range to be removed is examined as described in the steps illustrated in FIG. 9.[0293]
• The process begins in step[0294]900 and proceeds from there to step902 where the first unremoved page within a page range to be removed is located. Fromstep902, the process proceeds to step904, where it is determined whether the page or pages to be removed have outstanding input/output operations and these pages are skipped; once their I/O operations are completed, the pages can be reconsidered for removal. If the pages have outstanding I/O, the operation returns to step902 where the first unremoved page is located and from there to step904 as described previously. To allow the system to perform other work, a system may want to stall at this point waiting for I/O to complete.
• If the current unremoved page has no I/O pending, the process proceeds from[0295]step904 to step906, where it is determined whether the page is on the free, zeroed, untested, or bad page lists. If any of the memory pages are on any of these lists, the page is removed from the list instep908 and placed on the removed page list. Free pages are handled first so that copied pages are not copied onto free pages that are also part of the reconfigured range. Fromstep908, the process proceeds to step926 where it is determined whether all pages have been placed in the removed page list and, if they have, the process proceeds to finish instep928. On the other hand, if all pages have not been placed on the removed page list, the process returns to step902 and from there as previously described. If desired, an implementation may choose to limit the number of iterations and execute an error recovery mechanism to avoid looping forever.
• If there are no pages on the free, zeroed, untested, or bad page lists, the process proceeds from step[0296]906 to step910 where it is determined whether there are any pages on the modified page list. If there are no pages on the modified page list, the process proceeds to step914. On the other hand, if there are pages on the modified page list, the process proceeds to step912 where the pages are written to backing storage such as a system page file. Fromstep912 the process proceeds to step926 and from there as previously described. On the other hand, if the process had proceeded to step914 fromstep910, instep914, it is determined whether any pages are process pages, i.e, pages where an application runs. Since each process may have multiple threads, each process has its own page table apart from other processes. If any pages are process pages, an AST which provides a mechanism for executing within the process' context to gain access to the process page tables, is sent to the process and the AST sets the process single threaded if necessary to synchronize access to the page tables. New page frame numbers are allocated for the pages and the contents of the pages are copied to the new page frame numbers. The old page frame numbers are placed on the instance's removed page list instep916. Fromstep916, the process proceeds to step926 and from there as described previously.
• If it is determined in[0297]step914 that none of the pages are process pages, the process proceeds to step918 where it is determined whether any of the pages are part of a global section i.e., a set of private pages acesssed by several processes simultaneously. If any of the pages are part of global section, the process proceeds fromstep918 to step920. Instep920, the name of the global section may be displayed to a user so the user can determine which application to shut down in order to free memory. Alternatively, an operating system which can track where pages are mapped, could suspend all processes mapped to the section, copy all pages, modify all process page table entries, and place the old page frame numbers on the removed page list. Fromstep920, the process would then proceed to step926 and from there as described previously. If instep918 it is determined that there are no pages which are part of the global section, the process proceeds to step922 where it is determined whether any page is mapped into system address space. If none of the pages is mapped into the system address space, the process proceeds fromstep922 to step926 and from there as previously described.
• On the other hand, if there are pages mapped into the system address space, the process proceeds to step[0298]924, where those pages that are read only are copied. Once copied, the page is placed on the removed page list. Read/write pages are copied only while all CPUs within the instance are temporarily blocked from execution such that they do not change the contents of the page. One page is copied at a time and copied pages are placed on the remove page list. After migration instep924, the process proceeds to926 and from there as previously described.
• In order to remove shared memory, a new list of page frame numbers is established within each shared memory common property partition data structure, i.e., within each SHM CPP structure within the APMP data base. The list is called the common property partition removed page list. These lists are temporary holding places for all pages that are ready to be removed. Only when all pages within the 8 MB range are located on the appropriate remove page list, can the pages be removed. At any point in time, if it is determined that the pages cannot be removed while the sharing set (the set of instances which share resources, such as memory) is operational, the sharing set can be dissolved, the pages marked unowned, and the sharing set reformed. The removal operation can be abandoned at any time by moving the pages from the common property partition removed page list to the free page or bad page lists depending on the previous state of the page, i.e., to the free page list if it had been on the free page list and to the bad page list if it had been on the bad page list.[0299]
• The process of removing shared memory is illustrated in the flowchart of FIG. 1000 with the process beginning in[0300]step1000 and proceeding from there to step1002 whereby the first unremoved page in the range of pages to be removed is located. Fromstep1002 the process proceeds to step1004 where it is determined whether any pages within the page range to be removed have outstanding I/O. Those pages that have outstanding I/O are skipped and the process returns to step1002 to locate the first unremoved page, as previously described. To allow the system to perform other work, a system may want to stall at this point waiting for I/O to complete.
• If no pages have outstanding I/O, the process proceeds from[0301]step1004 to step1006 where it is determined whether any pages are part of the APMP database. If any of the pages are a part of the APMP database, an error is returned to the user instep1008. In such a case, the sharing set must be reformed with the APMP database on different pages. This can be accomplished by dissolving the sharing set, marking the old APMP database pages as unowned, choosing a new set of APMP database pages, then recreating the sharing set. The process proceeds fromstep1008 to finish instep1030.
• The page frame number database entry pages describing those pages are unmapped and freed to the common property partition free page list, the PMAP arrays that describe shared memory are updated to reflect the change and the console is called to mark the page unowned. From[0302]step1028, the process then proceeds to finish instep1030. If, instep1026, the process had determined that all pages were not on the shared memory common property partition removed page list, the process returns fromstep1026 to step1002 and proceeds from there as described previously. If instep1006, the process determines that none of the pages are part of the APMP database, the process proceeds to step1010 where it is determined whether any of the pages are on the free, bad, or untested page lists, and, if so the pages are removed and placed on the common property partition removed page list instep1012. Fromstep1012, the process proceeds to step1026 and from there as previously described.
• If it is determined in step[0303]1010 that none of the pages are on the free, bad or untested page lists, the process proceeds to step1014, where it is determined whether any pages are shared memory page frame number database pages and if so, the process proceeds to step1016. Instep1016, assuming the range of pages comprise the only pages left within the shared memory common property partition that are not on the common property partition removed page list, the shared memory common property partition is removed from the community. Instep1016, the shared memory common property partition is marked as invalid so no attempts are made to allocate pages from it. The PMAP arrays that describe shared memory are updated to reflect the removal of the memory. Other shared memory APMP database structures are updated to reflect the removal of the shared memory common property partition and the console is called to mark the pages unowned. Alternatively, if the PFN database pages are not the only pages left within the shared memory common property partition not on the removed page list, an error may be returned to the user, in which case, the user could dissolve the sharing set, mark the pages unowned, and recreate the sharing set. To copy these pages, the shared memory common property partition which contains the pages could be marked as temporarily invalid and the mapping of the PFN database pages marked read only. One instance could then copy the pages to a new set of pages allocated from the common property partition. All instances would then modify their mappings from the old page to the new pages and the old pages could then be placed on the common property partition removed page list. The process would then proceed fromstep1016 to step1026 and from there as previously described.
• If it is determined in[0304]step1014 that some pages are not shared memory page frame number database pages, the process would proceed to step1018 where it is determined whether any of the pages are part of a shared memory region that is mapped into systems space and if so the process would proceed to step1020 where shared memory region callback routines may be called and retain the memory used to be removed. The callback routines can either shut down the application or create a new shared memory region and start using the new region. Alternatively, or in conjunction with the callback routines, the tag of the shared memory region can be displayed through the console. This would allow a user to assist in shutting down the application which is using the shared memory. Fromstep1020, the process would then proceed to step1026 and from there as previously described.
• If, in[0305]step1018, it is determined that none of the pages are part of a shared memory region that is mapped into system space, the process proceeds to step1022 where it is determined whether any pages are part of a shared memory global section, i.e., a set of shared page mappings into one or more process' address space so all the processes can have access to the same pages. If there are some pages that are part of a shared memory global section, the process proceeds to step1024, where a callback routine is called on all instances that have this global section mapped. All processes that are mapped to the global section can be suspended, the code can then copy all data from one set of pages to another, modify all process page table entries, modify the global section data structures and place the old page frame numbers on the common property partition removed page list. Alternatively, each process that maps to the global section can be notified to shut down, or, the names of the global sections can be displayed so the user can determine which application should be shut down to assist in the removal operation. From step1024, the process would then proceed to step1026 and from there as previously described.
• To ensure, if I/O has been initiated to shared memory, that the memory is not reused for another purpose before we are sure that all I/O in shared memory is completed, an I/O device may interrupt the instance when I/O has completed, the system would then record that the I/O is complete. Alternatively, when all I/O buses within the instance's partition have been reset, I/O has been completed. In the SHM_DESC structure in private memory, there is a field called I/O refcnt, which stands for I/O reference count. There is one SHM_DESC structure per shared memory region.[0306]
• In the SHM_REG structure in the APMP database, there is a bitmask called the “attached bitmask.” There is one SHM_REG structure per shared memory region. The attached bitmask contains one bit for each instance in the APMP system. If a bit in the attached bitmask is set, the corresponding instance is attached to the region.[0307]
• In the configuration tree structure, maintained by the console, there is an ID field in the partition node that can be set or cleared by calling a console callback routine. During system boot after the partition's I/O buses have been reset this field in the instance's partition node is cleared.[0308]
• When a sharing set is being created:[0309]
• 1) Loop through all other instance's partition nodes in this community.[0310]
• 2) If the ID field is non-zero and there is no instance running on the partition as indicated within the configuration tree, reset all I/O buses connected to the partition.[0311]
• 3) Set the ID field in this instance's partition node to the ID (a number that increases each time the APMP database is recreated).[0312]
• When an instance is joining a sharing set:[0313]
• 1) Set the ID field in the instance's partition node to the current ID.[0314]
• During a sharing set exit:[0315]
• 1) Call a routine which detaches from all shared memory regions.[0316]
• 2) Clear the ID field in the instance's partition node in the config tree.[0317]
• When an I/O is initiated, the routine shm_reg_incref is called for each page on which I/O will be performed. When the I/O is completed, the routine shm_reg_decref is called for each page.[0318]
• Routine shm_reg_incref:[0319]
• Input: Address of PFN database entry for page[0320]
• Read the shared memory region id from the PFN database entry.[0321]
• Obtain the SHM_DESC address in private memory for this region.[0322]
• Increment I/O refcnt.[0323]
• Routine shm_reg_decref:[0324]
• Input: Address of PFN database entry for page[0325]
• Read the shared memory region id from the PFN database entry.[0326]
• Obtain the SHM_DESC address in private memory for this region.[0327]
• Decrement I/O refcnt[0328]
• Routine shm_reg_create:[0329]
• Inputs: tag[0330]
• virtual length[0331]
• physical length[0332]
• virtual mapping information[0333]
• plus additional information[0334]
• Output: shared memory region id[0335]
• Search for a SHM_REG structure in shared memory whose tag matches the tag supplied.[0336]
• If no such SHM_REG structure is found:[0337]
• Allocate a new SHM_REG structure[0338]
• Acquire the SHM_REG lock[0339]
• Set the “init in progress” bit in the SHM_REG structure[0340]
• Allocate shared memory pages for the region[0341]
• Clear the “init in progress” bit in the SHM_REG structure[0342]
• Release the SHM_REG lock[0343]
• Set the bit in the SHM_REG attached bitmask for this instance.[0344]
• Map to the shared memory region using the virtual mapping information supplied.[0345]
• Routine shm_reg_delete:[0346]
• Input: shared memory region id[0347]
• Obtain the SHM_DESC address in private memory for this region.[0348]
• If the I/O refcnt field is non-zero, return an error.[0349]
• Unmap the shared memory region.[0350]
• Obtain the SHM_REG address in shared memory for this region.[0351]
• Clear the bit in the SHM_REG attached bitmask for this instance.[0352]
• If the attached bitmask has more bits set, return.[0353]
• If the SHM_REG attached bitmask has no bits set:[0354]
• Acquire the SHM_REG lock[0355]
• Set the “delete in progress” bit in the SHM_REG structure[0356]
• Deallocate all shared memory pages to the appropriate shared memory free page lists.[0357]
• Clear the “delete in progress” bit[0358]
• Release the SHM_REG lock[0359]
• Clean up the SHM_REG data structure[0360]
• During system crash:[0361]
• Reset all I/O buses.[0362]
• Clear the ID field in the instance's partition node.[0363]
• Call system code to interrupt another instance to indicate that the instance has crashed. (The interrupt handler on the other instance calls shmem_APMPDB_recover.)[0364]
• Initiate crash dump.[0365]
• During heartbeat monitoring:[0366]
• If an instance's heart does not beat for an amount of time, the instance is declared dead and is removed from the sharing set.[0367]
• Acquire the SHM_REG synchronization lock, breaking the lock if necessary. If the lock was held by the dead instance:[0368]
• If the SHM_REG structure indicates that initialization was in progress or that the region was in the process of being deleted, call shm_reg_delete.[0369]
• The routine shmem_APMPDB_recover is called on at least one of the other instances. In this case, the ID Field in the instance's partition node is not cleared.[0370]
• Routine shmem_APMPDB_recover:[0371]
• Input: Instance ID of the dead node[0372]
• Loop through all SHM_REG structures in the APMP database.[0373]
• If the crashing instance was attached to the region:[0374]
• 1) If the ID field in the instance's partition node is non-zero, this might indicate that the instance was halted, not crashed. I/O devices may still be writing to shared memory.[0375]
• Loop to the next SHM_REG structure leaving this instance attached and the shared memory region in place. When the instance joins the sharing set again, it will clear the attached bit after having reset the I/O buses. It will delete the shared memory region if it was the last instance attached to the region.[0376]
• 2) If the ID field in the instance's partition node is clear:[0377]
• clear the bit for the instance in the attached bitmask[0378]
• If the attached bitmask has no bits set:[0379]
• Call shm_reg_delete[0380]
• Loop to the next SHM_REG structure[0381]
• After all SHM_REG structures have been processed, execute more shared memory recovery code.[0382]
• Routine shmem_sharing _set_join:[0383]
• Input: Instance ID of this instance.[0384]
• Map to the APMP database in shared memory.[0385]
• Execute other shared memory community join code.[0386]
• Loop through all SHM_REG structures in the APMP database.[0387]
• If this instance was attached to the region:[0388]
• Clear the bit for this instance in the attached bitmask[0389]
• If the attached bitmask has no more bits set[0390]
• Call shm_reg_delete[0391]
• Loop to the next SHM_REG structure[0392]
• After all SHM_REG structures have been processed, return.[0393]
• To choose the initial APMP database pages, the routine shmem_config_APMPDB is called by APMPDB_map_initial to choose the intial set of APMPDB pages.[0394]
• Data structures:[0395]
• The community node in the config tree contains a 64-bit field, called APMPDB_INFO, which is used to store APMPDB page information. The first 32-bits, APMPDB_INFO[31:0], is the low PFN of the APMPDB pages. The second 32-bits, APMPDB_INFO[63:32], is the page count of APMPDB pages.[0396]
• Each instance keeps an array in private memory called the “shared memory array.” Each element in the array contains a shared memory PFN and a page count. The entire array describes all shared memory owned by the community that this instance is a part of.[0397]
• The configuration tree may contain tested memory bitmaps for shared memory. If the configuration tree does not contain a bitmap for a range of memory, the memory has been tested and it is good. If a bitmap exists for a range of memory, each bit in the bitmap indicates whether a page of shared memory is good or bad.[0398]
• A value, MAX_APMPDB_PAGES, is set to the maximum number of pages required to initialize a system. This number should be smaller than the granularity of shared memory. MAX_APMPDB_PAGES should be a small number to increase the chances that contiguous good memory can be found for the initialization of the APMP database.[0399]
• Console callback routine set_APMPDB_info:[0400]
• Inputs: new_APMPDB_info Bits[31:0]=first APMPDB page frame number[0401]
• Bits[63:32]=number of pages specified for the APMP database[0402]
• old_APMPDB_info—value read from the GDMB_INFO field in the community node.[0403]
• Outputs: None.[0404]
• Status: Error=Value in APMPDB_INFO does not match old_APMPDB_info[0405]
• Success=APMPDB_INFO has been updated with new_APMPDB_info[0406]
• This routine may be more complex if multiple copies of the configuration tree are maintained by a console.[0407]
• 1. Read APMPDB INFO from the community node[0408]
• 2. If APMPDB_INFO does not equal old_APMPDB_info, return an error[0409]
• 3. Store new_APMPDB_INFO into APMPDB_INFO with an atomic instruction[0410]
• A routine, SHMEM_config_APMPDB, is used to configure the APMP database. The routine provides the first APMP database page frame number and the number of pages specified for the APMP database. The routine proceeds as follows:[0411]
• (1) Obtain a pointer to the community node within the configuration tree.[0412]
• (2)Traverse the configuration tree creating the shared memory array. If there is no shared memory, return an error.[0413]
• (3) Read the APMPDB_INFO field[0414]
• (4) If APMPDB_INFO field is non-zero[0415]
• Set PAGES to APMPDB_INFO[0416]
• Search the shared memory array to ensure that pages PFN through[0417]
• PFN+PAGES-1 are in shared memory[0418]
• If these pages are in the shared memory array:[0419]
• if a tested memory bitmap exists, check the bitmap to ensure that these pages are not marked bad[0420]
• if all the pages are good, cal set_APMPDB_INFO to write the PFN and PAGES into the APMPDB_INFO field[0421]
• if SET_APMPDB_INFO returns an error, return to (2)[0422]
• If SET_APMPDB_INFO returns a success, return PFN and PAGES to the caller[0423]
• If any of the pages are not in shared memory or are bad[0424]
• Call SET_APMPDB_INFO to clear the APMPDB_INFO field[0425]
• If SET_APMPDB_INFO returns an error, return to (2)[0426]
• If SET_APMPDB_INFO returns success, go to (5) to choose new APMPDB pages[0427]
• (5) Set PAGES to MAX_APMPDB_PAGES[0428]
• (6) Loop through the shared memory array. For each element in the array:[0429]
• (6.1) Set PFN to the lowest shared memory PFN in the range.[0430]
• (6.2) If a tested memory bitmap exists, check the bitmap to ensure that these pages are not marked bad[0431]
• (6.3) If all the pages are good[0432]
• Call SET_APMPDB_INFO to write PFN pages intothe APMPDB field[0433]
• If SET_APMPDB_INFO returns an error, return to (2)[0434]
• If SET_APMPDB_INFO returns success, return PFN and PAGES to the caller[0435]
• (6.4) If a bad page is encountered within the range[0436]
• Set PFN to the highest numbered[0437]bad PFN+1
• If PFN+PAGES-1 is still within the shared memory array element return to (6.2)[0438]
• If PFN+PAGES-1 is greater than the range described by this shared memory array element, move to the next shared memory array element[0439]
• (6.5) If there are no shared memory array elements left, return an error.[0440]
• An illustrative page frame number database layout is illustrated by the memory map of FIG. 11. In this illustrative example the system includes two instances, A and B, each with 64 megabytes of private memory and 64 megabytes of shared memory. The memory is arranged as eight kilobyte pages, with private memory for instance A extending from page frame number (PFN) 0 through PFN 1BFF (hexadecimal). Sixty four megabytes of shared memory extends from PFN 2000- to PFN 3FFF. Private memory for instance B extends from PFN 800000 through PFN 801FFF. The memory used to hold the PFN database for instance A comes from instance A's private memory (0-1FFF), the memory used to hold the PFN database for instance B comes from instance B's private memory (2000-3FFF), and the memory used to hold the PFN database for shared memory comes from the shared memory (800000-801FFF). Instance A cannot access the PFN database entries for Instance B's memory because, as illustrated, that memory region is not mapped into the system space for instance A. Similarly, Instance B cannot access the PFN database entries for Instance A's memory because that memory region is not mapped into the system space for instance B. Both Instances A and B map the shared pages into the PFN database entries for shared memory. Instances map to the shared pages with private memory page tables because private memory and shared memory PFN database entries may be mapped by the same page table pages. As noted above, the granularity of physical memory may be chosen as the least common multiple of PFN database entry size and memory pages size. In the illustrative example the memory page size is 8 kilobytes and the granularity of physical memory is equal to the page size squared divided by eight (bytes), or 8 MB. Page sizes of 16, 32, and 64 KB yield physical memory granularity of 32, 128, and 512 MB, respectively.[0441]
• A software implementation of the above-described embodiment may comprise a series of computer instructions either fixed on a tangible medium, such as a computer readable media, e.g. diskette[0442]142, CD-ROM147, ROM115, or fixed disk152 of FIG. 1, or transmissible to a computer system, via a modem or other interface device, such as communications adapter190 connected to the network195 over a medium191. Medium191 can be either a tangible medium, including but not limited to optical or analog communications lines, or may be implemented with wireless techniques, including but not limited to microwave, infrared or other transmission techniques. It may also be the Internet. The series of computer instructions embodies all or part of the functionality previously described herein with respect to the invention. Those skilled in the art will appreciate that such computer instructions can be written in a number of programming languages for use with many computer architectures or operating systems. Further, such instructions may be stored using any memory technology, present or future, including, but not limited to, semiconductor, magnetic, optical or other memory devices, or transmitted using any communications technology, present or future, including but not limited to optical, infrared, microwave, or other transmission technologies. It is contemplated that such a computer program product may be distributed as a removable media with accompanying printed or electronic documentation, e.g., shrink wrapped software, pre-loaded with a computer system, e.g., on system ROM or fixed disk, or distributed from a server or electronic bulletin board over a network, e.g., the Internet or World Wide Web.
• Although an exemplary embodiment of the invention has been disclosed, it will be apparent to those skilled in the art that various changes and modifications can be made which will achieve some of the advantages of the invention without departing from the spirit and scope of the invention. For example, it will be obvious to those reasonably skilled in the art that, although the description was directed to a particular hardware system and operating system, other hardware and operating system software could be used in the same manner as that described. Other aspects, such as the specific instructions utilized to achieve a particular function, as well as other modifications to the inventive concept are intended to be covered by the appended claims.[0443]

Claims (20)

What is claimed is:

1. A computer system having a plurality of system resources including processors, memory and I/O circuitry, the computer system comprising:

an interconnection mechanism for electrically interconnecting the processors, memory and I/O circuitry so that each processor has electrical access to all of the memory and at least some of the I/O circuitry; and

a software mechanism for dividing the system resources into a plurality of partitions and for dividing the memory into private and shared memory segments, wherein the software mechanism allows only a single partition to have access to each private memory segment and allows a plurality of partitions which form a community to have access to each shared memory segment.

2. The computer system ofclaim 1 wherein the software mechanism blocks access by any partition to any memory segment that the software system designates as unowned by any partition.

3. A computer system according toclaim 2 wherein said memory may be reconfigured into or out of the system when in the unowned state.

4. A computer system according toclaim 3 wherein memory pages are placed in the unowned state only if they have no pending input/output operations.

5. A computer system according toclaim 1 wherein the software mechanism maintains free, zeroed, untested, and bad memory page lists.

6. A computer system according toclaim 5 wherein memory pages to be removed are modified to an unowned status, if they are on any of the memory page lists.

7. A computer system according toclaim 5 wherein the system maintains a modified page list that indicates those memory pages which have been modified, but not written to a system paging file.

8. A computer system according toclaim 6 wherein the system maintains a shared memory database within shared memory.

9. A computer system according toclaim 8 wherein the shared memory database indicates whether an operating system instance associated with a partition within the community is active.

10. A computer system according toclaim 9 wherein the system is responsive to a request to remove a page of memory associated with an operating system instance that is active by returning an error.

11. A method for constructing a computer system having a plurality of system resources including processors, memory and I/O circuitry, and for adding memory to or deleting memory from the system, the method comprising the steps of:

(a) electrically interconnecting the processors, memory and I/O circuitry so that each processor has electrical access to all of the memory and at least some of the I/O circuitry;

(b) dividing the system resources into a plurality of partitions;

(c) forming a community of partitions by sharing memory among a group of partitions; and

(d) placing memory into an unowned state, whereby the memory is unowned by any partition, whenever the memory is to be added to or deleted from the system.

12. A method according toclaim 11 wherein step (d) further comprises the steps of

(d1) determing whether any pending input/output operations will affect the memory; and

(d2) placing memory that is to be reconfigured into or out of the system in the unowned state only if there are no input/output operations which will affect the memory.

13. The method ofclaim 12 further comprising the step of

(e) maintaining free, zeroed, untested, and bad memory page lists.

14. The method ofclaim 13 further comprising the step of:

(f) placing memory that is to be removed and is on a free, zeroed, untested, or bad memory page list on a removed list.

15. The method ofclaim 14 further comprising the step of:

(g) writing to backing storage memory that is to be removed that is not on the free, zeroed, untested, or bad memory page list.

16. A computer program product for constructing a computer system having a plurality of system resources including processors, memory and I/O circuitry and hardware for electrically interconnecting the processors, memory, and I/O circuitry so that each processor has electrical access to all of the memory and at least some of the I/O circuitry, the computer program product comprising a computer usable medium having computer readable program code thereon including:

(a) program code for dividing the system resources into a plurality of partitions;

(b) program code for forming a community of partitions which shares memory; and

(c) program code for adding memory to or removing memory from the system.

17. A computer program product according toclaim 16 wherein the program code for adding memory to or removing memory from the system includes:

(c1) program code for placing memory into an unowned state, whereby the memory is unowned by any partition, whenever the memory is to be added to or deleted from the system.

18. A computer program product according toclaim 17 wherein the program code for adding memory to or removing memory from the system includes:

(c2) program code for determing whether any pending input/output operations will affect the memory; and

(c3) program code for placing memory that is to be reconfigured into or out of the system in the unowned state only if there are no input/output operations which will affect the memory.

19. The computer program product of method ofclaim 18 wherein the program code for adding memory to or removing memory from the system includes:

(c4) program code for maintaining free, zeroed, untested, and bad memory page lists.

20. The computer program product of method ofclaim 19 wherein the program code for adding memory to or removing memory from the system includes:

(c5) program code for placing memory that is to be removed and is on a free, zeroed, untested, or bad memory page list on a removed list.

Images