Highly componentized system architecture with object mutation Number:7,159,222 from the United States Patent and Trademark Office (PTO) owispatent In accordance with another aspect, the invention is embodied in a computer operating system capable of supporting plural objects running in a computer having a working memory, the computer operating system including a kernel resident in the working memory at link time, and a loadable mutation object resident at link time outside of the working memory and dynamically loadable into the working memory at run time upon demand of one of the application programs, the mutation object including an interface with methods for mutating any one of the plural objects. The kernel includes a loader for loading the mutation object into the working memory in response to a demand from one of the plural objects. The computer further includes a storage memory separate from the working memory, the loadable mutation object residing at link time in the storage memory. The loader loads the mutation object from the storage memory to the working memory, and the loadable mutation object is terminable from the working memory upon lack of demand therefor by the plural objects. Preferably, the kernel of the operating system includes a Namespace for registering the mutation object upon the mutation object being loaded into the working memory, whereby the mutation object becomes available to each of the plural objects through the Namespace.<H componentized, architecture, Highly, componen, 7159222.html, Patent, pto, 7159222

Title: Highly componentized system architecture with object mutation

Abstract: In accordance with another aspect, the invention is embodied in a computer operating system capable of supporting plural objects running in a computer having a working memory, the computer operating system including a kernel resident in the working memory at link time, and a loadable mutation object resident at link time outside of the working memory and dynamically loadable into the working memory at run time upon demand of one of the application programs, the mutation object including an interface with methods for mutating any one of the plural objects. The kernel includes a loader for loading the mutation object into the working memory in response to a demand from one of the plural objects. The computer further includes a storage memory separate from the working memory, the loadable mutation object residing at link time in the storage memory. The loader loads the mutation object from the storage memory to the working memory, and the loadable mutation object is terminable from the working memory upon lack of demand therefor by the plural objects. Preferably, the kernel of the operating system includes a Namespace for registering the mutation object upon the mutation object being loaded into the working memory, whereby the mutation object becomes available to each of the plural objects through the Namespace.

Patent Number: 7,159,222 Issued on 01/02/2007 to Forin, et al.

Inventors: Forin; Alessandro (Redmond, WA), Helander; Johannes V. (Bellevue, WA)
Assignee: Microsoft Corporation (Redmond, WA)

Appl. No.: 09/282,229

Filed: March 31, 1999

Current U.S. Class: 719/310 ; 718/100; 719/316; 719/331; 719/332

Current International Class: G06F 9/00 (20060101)

Field of Search: 709/310,321 719/310,321,316,331,332 718/100,108

References Cited [Referenced By]

U.S. Patent Documents


5339430	August 1994	Lundin et al.
5761670	June 1998	Joy
6092079	July 2000	Gerard et al.
6339841	January 2002	Merrick et al.
6510437	January 2003	Bak et al.
6560626	May 2003	Hogle et al.
6678880	January 2004	Roddy

Other References

B Bershad, et al., "Extensibility, Safety and Performance in the Spin Operating System," 15th ACM Symposium on Operating System Principles, Copper Mountain Resort, Colorado, Dec. 1995, pp. 267-284. cited by other .
D. Black, et al., "Microkernel Operating System Architecture and Mach," 1st Usenix Workshop on Micro-Kernels and Other Kernel Architectures, Seattle, Apr. 1992, pp. 11-30. cited by other .
D. Cheriton, et al., "A Caching Model of Operating System Kernel Functionality," Proceedings of the First Symposium on Operating Systems Design and Implementation, Seattle, 1994, 15 pages. cited by other .
D. Cheriton, "The V Distributed System", Communications of the ACM, Mar. 1998, vol. 31, No. 3, pp. 314-333. cited by other .
R. Draves, et al., "Unifying the User and Kernel Environments," Microsoft Research Technical Report MSR-TR-97-10, Mar. 1997, 16 pages. cited by oth- er .
D. Engler, et al., "Exokernel: An Operating System Architecture for Application-Level Resource Management," 15th ACM Symposium on Operating System Principles ACM SIGOPS, Copper Mountain Resort, Colorado, Dec. 1995, pp. 251-266. cited by other .
B. Ford, et al., "The Flux OSKit: A Substrate for Kernel and Language Research," Proceedings of the 16th ACM Symposium on Operating Systems Principles, ACM SIGOPS, Saint-Malo, France, Oct. 1997, pp. 38-51. cited by other .
D. Golub, et al., "UNIX as an application program," USENIX 1990 Summer Conference, Anaheim, CA, Jun. 1990, pp. 87-95. cited by other .
J. Helander, "Unix Under Mach: The Lites Server," Master's Thesis, Helsinki University of Technology, 1994, 71 pages. cited by other .
D. Hildebrand, "An Architectural Overview of QNX," 1st USENIX Workshop on Micro-kernels and Other Kernel Architectures, Seattle, Apr. 1992, pp. 113-126. cited by other .
M. Jones, et al., "An Overveiw of the Rialto Real-Time Architecture," Proceedings of the Seventh ACM SIGOPS European Workshop, SIGOPS, Sep. 1996, pp. 249-256. cited by other .
M. Jones, et al., "CPU Reservations and Time Constraints: Efficient, Predictable Scheduling of Independent Activities," Proceedings of the 16th ACM Symposium on Operating System Principles, ACM SIGOPS, Saint-Malo, France, Oct. 1997, pp. 198-211. cited by other .
M. Jones, The Microsoft Interactive TV System: An Experience Report, Microsoft Research Technical Report MSR-TR-97-18 [online], Jul. 1997, 24 pages, Retrieved Jan. 26, 2000 from the Internet at .research.microsoft.com/research/os/mbj/papers/mitv/tr-97-18.html. cited by other .
D. Julin, et al., "Generalized Emulation Services for Mach 3.0 Overview, Experiences and Current Status," Proceedings of the Usenix Mach Symposium USENIX Association, 1991, pp. 13-26. cited by other .
D. Lee, et al., "Execution Characteristics of Desktop Applications on Windows NT," Proceedings of the 25th International Symposium on Computer Architecture,, IEEE, Barcelona, Spain, Jun. 1998, pp. 27-38. cited by oth- er .
J. Liedtke, "On .mu.-Kernel Construction," 15th ACM Symposium on Operating System Principles, ACM, Copper Mountain Resort, Colorado, Dec. 1995, pp. 237-250. cited by other .
J. Mogul, et al., "The Packet Filter: An Efficient Mechanism for User-level Network Code," 11th ACM Symposium on Operating System Principles, ACM, Nov. 1987, 34 pages. cited by other .
R. Rashid, "From RIG to Accent to Mach: The Evolution of a Network Operating System," Carnegie-Mellon University Technical Report, Aug. 1987, pp. 1128-1137. cited by other .
M. Rozier, et al., "CHORUS Distributed Operating System," Computing Systems, Fall 1998, vol. 1, No. 4, pp. 305-370. cited by other .
Torborg, Jay, et al., "Talisman: Commodity Realtime 3D Graphics for the PC," Proceeding of SIGGRAPH96, ACM, Aug. 1996, pp. 353-363. cited by othe- r .
M. Young, "Exporting a User Interface to Memory Management from a Communication-Oriented Operating System," Ph.D. Thesis CMU-CS-89-202, Carnegie-Mellon University, Nov. 1989, 206 pages. cited by other .
U.S. Appl. No. 09/282,238, filed Mar. 31, 1999, Forin et al. cited by othe- r .
U.S. Appl. No. 09/283,227, filed Mar. 31, 1999, Forin et al. cited by othe- r .
U.S. Appl. No. 09/283,818, filed Mar. 31, 1999, Forin et al. cited by othe- r .
U.S. Appl. No. 09/392,405, filed Sep. 9, 1999, Forin et al. cited by other .
U.S. Appl. No. 09/282,656, filed Mar. 31, 1999, Forin et al. cited by othe- r.

Primary Examiner: Thomson; William
Assistant Examiner: Ho; Andy
Attorney, Agent or Firm: Microsoft Corporation

Parent Case Text

CROSS-REFERENCE TO RELATED APPLICATION

This application is a utility application filing of provisional patent Ser. No. 60/099,562, filed on Sep. 9, 1998 and entitled "A Highly Componentized System Architecture With Dynamically Loadable Operating Features" (now abandoned).

Claims

What is claimed is:

1. A computer having a memory storing computer-executable instructions supporting plural objects and a mutation object, said mutation object comprising: a method for mutating at least one object of said plural objects dynamically during run-time to provide a new implementation within the one object, wherein the one object includes a first method and a second method and an interface with a pointer, and wherein the method of mutating includes changing the pointer from identification of the first method to identification of the second method.

2. The computer of claim 1 wherein each one of said plural objects comprises: a V-table; a V-table pointer pointing to said interface.

3. The computer of claim 2 wherein said interface comprises a Mutate_Object method.

4. The computer of claim 2 wherein said mutation object mutates said V-table pointer so as to change the interface of the one object to a new interface corresponding to a new set of methods.

5. The computer of claim 4 wherein said method of said mutation object is a Mutate_VTable method.

6. The computer of claim 2 wherein said method of said mutation object is a Mutate_Object method.

7. The computer of claim 1 wherein each one of said plural objects comprises a state register storing a state of said one object, and wherein said method of said mutation object changes the contents of said state register so as to mutate the state of said one object.

8. The computer of claim 7 wherein said state register stores the value of a pointer of said one object.

9. The computer of claim 8 wherein said pointer of said one object comprises a VTable pointer.

10. The computer of claim 8 wherein said mutation object comprises a Mutate_Object method.

11. The computer of claim 1 wherein said mutation object further comprises a synchronization of the mutation of one of said plural objects with threads running in said one object.

12. The computer of claim 11 wherein said synchronization comprises mutual exclusion.

13. The computer of claim 12 wherein said mutual exclusion prevents new threads from accessing said one object while other threads running in said object are permitted to finish.

14. The computer of claim 11 wherein said synchronization comprises transactional synchronization.

15. The computer of claim 14 wherein said transactional synchronization rolls back the threads currently running in the one object and then permits mutation of the object.

16. The computer of claim 11 wherein said synchronization comprises swizzling.

17. The computer of claim 16 wherein said swizzling comprises suspending threads running in said one object, mutating the one object and modifying states of the suspended threads in accordance with the mutation of the one object, and thereafter reactivating the suspended threads.

18. The computer of claim 17 wherein thread states are swizzled between clean points in the thread execution, whereby the threads are suspended at a clean point.

19. The computer of claim 1 wherein one of said plural objects comprises an interposition object formed by said mutation object mutating a particular one of said plural objects and a copied object at least nearly identical to said one particular object, said interposition object differing from said one particular object in that said one particular object has a pointer to said copied object and a method of interposition between threads seeking said one particular object and said copied object.

20. The computer of claim 19 wherein said interposition method comprises a filter.

21. The computer of claim 20 wherein said filter is a read-only filter.

22. The computer of claim 20 wherein said filter provides access based upon the identity of the requesting thread.

23. The computer of claim 19 wherein said copied object is a copy of the one particular object.

24. The computer of claim 23 wherein said interposition object is formed by copying said one particular object and mutating the resulting copy while said copied object is said one particular object.

25. The computer of claim 5 wherein said new implementation corresponds to a software upgrade.

26. The computer of claim 5 wherein said new implementation is a higher speed I/O driver.

27. The computer of claim 5 wherein said new implementation comprises recently loaded code.

28. The computer of claim 1 wherein said new implementation comprises a different arithmetic algorithm.

29. The computer of claim 1 where said new implementation is a version of an algorithm where specific conditions are assumed to be true, where the version is mutated back to a version when the conditions are no longer true.

30. The computer of claim 29 wherein some of the parameters of the method are assumed to be constant.

31. The computer of claim 30 where the version is generated by a compiler through constant folding.

32. The computer of claim 29 where specific assumptions are made of the objects the method accesses.

33. The computer of claim 32 where the assumption is the location of an object.

34. The computer of claim 32 where the assumption is the value of a field of the state of the object.

35. The computer of claim 32 where the said version is generated through constant folding.

36. The computer of claim 32 where the said version is generated through inlining.

Description

BACKGROUND OF THE INVENTION

1. Technical Field

The invention is related to computer operating systems and in particular to a computer operating system which is highly componentized and has dynamically loadable operating features which may be loaded and unloaded during system run time.

2. Background Art

The progressive computerization of society involves a number of diverse computing platforms beside the general-purpose computer:

Embedded control systems, including consumer devices, intelligent sensors and smart home controls.

Communication-oriented devices such as digital cell phones and networking infrastructure.

Programmable peripherals and microcontrollers.

In all these cases, the general-purpose platform approach is either not applicable, or it is prohibitively expensive.

The microprocessor might be a DSP, a VLIW, or a micro-controller; the memory budget is severely restricted; there might be no MMU; the network connection might be sporadic; and Real-Time support is essential.

Current operating systems are either inflexible, big, lack Real-Time support, have complex hardware requirements, or are so special purpose that good development tools are unavailable and code reusability is low.

Microkernels [Black92, Engler95] attempt to modularize the operating system. But they confuse modularity with security by mandating that system services be in separate address spaces. Many of the services moved into separate server processes are still necessary for these systems to function and often the services have to trust each other.

C++ and Java provide objects at a very fine granularity level, and they are extremely successful with application programmers. Unfortunately, both languages confine their objects to a single address space. Object Linking and Embedding (OLE) [Brockschmidt95] and other similar systems extend objects across address spaces and across machine boundaries. OLE seamlessly integrates independently developed components. When editing an Excel spreadsheet inside a Word document it is in fact the Excel process that operates on objects inside of Word's address space. Unfortunately, it only works for user mode applications.

Modularity has always been an important paradigm in software design. By breaking a complex system into pieces, the complexity becomes more manageable. Address spaces provide security by installing virtual-memory based firewalls between applications. These two issues are orthogonal, but the distinction has been lost in systems research that has been concentrating on so-called microkernels. These issues have been discussed in the following publications: [Bershad95] Brian Bershad, S. Savage, P. Pardyak, E. G. Sirer, M. Fiuczynski, D. Becker, S. Eggers, C. Chambers. Extensibility, safety and performance in the Spin operating system. In 15.sup.th ACM Symposium on Operating System Principles, pages 267 284, Copper Mountain Resort, Colo., December 1995. [Black92] David Black, David Golub, Daniel Julin, Richard Rashid, Richard Draves, Randall Dean, Alessandro Forin, Joseph Barrera, Hideyuki Tokuda, Gerald Malan, David Bohman. Microkernel Operating System Architecture and Mach. In 1.sup.st USENIX Workshop on Micro-kernels and Other Kernel Architectures, pages 11 30, Seattle, April 1992. [Brockschmidt95] K. Brockshmidt. Inside OLE, Second ed. Microsoft Press, Redmond Wash., 1995. [Cheriton94] David Cheriton, Kenneth Duda. A Caching Model of Operating System Kernel Functionality. In 1.sup.st Symposium on Operating Systems Design and Implementation, Seattle, 1994. [Cheriton88] David Cheriton. The V distributed system. In Communications of the ACM, pages 314 333, March 1988. [Draves97] Richard Draves, Scott Cutshall. Unifying the User and Kernel Environments. Microsoft Research Technical Report MSR-TR-97-10, 16 pages, March 1997 [Engler95] D. R. Engler, M. F. Kaashoek, J. O'Toole Jr. Exokernel: an operating system architecture for application-specific resource management. In 15.sup.th ACM Symposium on Operating System Principles, pages 251 266, Copper Mountain Resort, Colo., December 1995. [Ford97] Bryan Ford, Godmar Back, Greg Benson, Jay Lepreau, Albert Lin, Olin Shivers. The Flux OSKit: A Substrate for Kernel and Language Research. In Proceedings of the 16th ACM Symposium on Operating Systems Principles, pages 38 51. ACM SIGOPS, Saint-Malo, France, October 1997. [Golub90] David Golub, Randall Dean, Alessandro Forin, Richard Rashid. UNIX as an application program. In USENIX 1990 Summer Conference, pages 87 95, June 1990. [Helander94] Johannes Helander. Unix under Mach: The Lites Server. Master's thesis, 71 pages, Helsinki University of Technology, 1994. [Hildebrand92] D. Hildebrand. An architectural overview of QNX. In 1.sup.st USENIX Workshop on Micro-kernels and Other Kernel Architectures, pages 113 126, Seattle, April 1992. [ISI95] Integrated Systems Inc. pSOSystem System Concepts. Part No. COL0011, May 1995, ISI, Sunnyvale Calif. [Jones96] Michael B. Jones, Joseph S. Barrera, III, Richard P. Draves, Alessandro Forin, Paul J. Leach, Gilad Odinak. An Overview of the Rialto Real Time Architecture. In Proceedings of the 7.sup.th ACM SIGOPS European Workshop, pagg. 249 256, September 1996. [Jones97] Michael B. Jones et al. CPU Reservations and Time Constraints: Efficient, Predictable Scheduling of Independent Activities. In Proceedings of the 16th ACM Symposium on Operating Systems Principles, pages 198 211. ACM SIGOPS, Saint-Malo, France, October 1997. [Jones 97b] Michael B. Jones. The Microsoft Interactive TV System: An Experience Report. Microsoft Research Technical Report MSR-TR-97-18, July, 1997. [Julin91] Daniel Julin, Jonathan Chew, Mark Stevenson, Paulo Guedes, Paul Neves, Paul Roy. Generalized Emulation Services for Mach 3.0: Overview, Experiences and Current Status. In Proceedings of the Usenix Mach Symposium, 1991. [Lee98] Dennis Lee, Patrick Crowley, Jean-Loup Baer, Tom Anderson, Brian Bershad. Execution characteristics of desktop applications on Windows NT. In Proceedings of the 25.sup.th International Symposium on Computer Architecture, Barcelona, Spain, June 1998. [Liedtke95] Jochen Liedtke. On .quadrature.-kernel construction. In 15.sup.th ACM Symposium on Operating System Principles, pages 237 250, Copper Mountain Resort, Colo., December 1995. [Mogul87] Jeffrey Mogul, Richard Rashid, Michael Accetta. The Packet Filter: an Efficient Mechanism for User-level Network Code. In 11.sup.th ACM Symposium on Operating System Principles, November 1987. [Rashid87] Richard Rashid. From RIG to Accent to Mach: The evolution of a network operating system. Carnegie Mellon University Technical Report, August 1987. [Rozier88] M. Rozier, A. Abrassimov, F. Armand, I. Boule, M. Gien, M. Guillemont, F. Hermann, C. Kaiser, S. Langlois, P. Leonard, W. Neuhauser. CHORUS distributed operating system. In Computing Systems, pages 305 370, Vol. 1 4, 1988. [Young89] Michael Wayne Young. Exporting a User Interface to Memory Management from a Communication-Oriented Operating System. Ph.D. Thesis CMU-CS-89-202, Carnegie Mellon University, November 1989.

Mach [Black92] defined an interface for external memory managers [Young89] and was able to split virtual memory into functionally distinct parts, allowing part of the functionality to reside outside the privilege-level component (the "kernel"). Mach also separated part of the Unix operating system services out of the kernel [Golub90, Helander94], achieving modularity but limited additional functionality. The multiserver project [Julin91] went further in the modularization by splitting the Unix services into multiple independent servers. The componentization added structure and generality to the services. However, keeping the services in multiple address spaces did not add any security or robustness since components had to be available and trusted in any case. The most interesting new functionality was in the ability to emulate multiple OS interfaces, at the same time.

Contemporary research systems take the minimization of the "kernel" concept even further by defining even lower level abstractions and demonstrating the ability to split states across address space boundaries. None of these systems defines a new application programming interface (API) different from the Unix they emulate. The API that their predecessors [Rashid87, Cheriton88, Rozier88] did define, based on RPC and message exchanges, were not very successful with programmers.

The Cache Kernel [Cheriton94] uses Mach's external memory manager metaphor uniformly for the management of all kernel objects. Threads, Address Spaces and User Kernels are all handled through this pagein-pageout logical interface. An actual application is statically linked with a number of libraries, which provide default implementations of the required User Kernel components (VM, scheduling, IPC). This offers some flexibility by letting untrusted applications have their custom application kernel. Overall complexity is not decreased; it seems an application kernel would have to be as complicated as any other operating system. The ability to write your own application kernel would seem useful for a limited number of users, in teaching operating systems for instance.

Exokernel [Engler95] goes along the same lines demonstrating further ability to run operating system code in user mode. While it is highly successful in this and offers some added flexibility, it is questionable whether the premises differ from that of microkernels. The main contribution is in the mechanisms for application-specific resource management.

[Liedtke95] argues that microkernels have failed exclusively on performance grounds, and that poor performance is their only cause for inflexibility. Our argument is the opposite: inflexibility is inherent in the design, and leads to unavoidable inefficiencies that can only be mitigated by good implementations, never eliminated.

Spin [Bershad95] addresses the issue of expensive address space crossings by letting user code compiled by a trusted compiler run inside the kernel. This can be viewed as smart proxies that can do a lot of the work locally that otherwise would require communication. It is similar to loading packet filters into network drivers [Mogul87], to running database application query language inside database engines [reference], or to sandboxing Java applets. Applying these techniques to operating systems is beneficial when a trust boundary must be crossed and the cost would otherwise be high. It does not address the issue of whether or not a trust boundary is necessary. Spin uses an object-based language (Modula3) to provide extensibility. The pointer-safety property of the language is what permits execution of untrusted code in privileged mode. Trust relationships, as in the user-versus-kernel separation, should not dominate system decomposition. It is important to return to a global system view. The present invention addresses the issue of how to minimize the set of base services, and how to dynamically extend them on demand.

[Ford97] shows how a base set of system components can be composed in different ways to build an operating system kernel. The granularity is fairly coarse, and the techniques are limited to static linking. Components that should be of interest to OS researchers (VM, IPC, scheduling, etc.) cannot be replaced or removed, neither statically nor dynamically. The decomposition is otherwise limited to the "OS" component; it is not meant as a whole-system approach. This does not go far enough in the componentization. It provides a few convenient components, such as bootstrap loader and filesystems, but is mostly concerned with reusing existing device drivers and Unix code. It fails to componentize the core kernel services or extend the paradigm to applications.

Componentization and location independence has also been studied in the context of filesystems and network protocols [Maeda93] and in a number of existing embedded systems, such as pSOS [ISI95]. In a typical embedded system there is no loader, and components can only be chosen at static link time when the load image is built. Services are extremely limited, sometimes exclusively to the scheduling component. The number and priority of threads might have to be specified statically as well.

Chorus [Rozier88] can be configured to use either a page-based or a segment-based VM system.

SUMMARY OF THE INVENTION

A preferred embodiment of the invention is directed to a flexible system architecture that is suitable for a wide range of applications. The system is built out of minimal but flexible components, which can be deployed as needed. Instead of mandating a fixed set of operating system services and hardware requirements, the system preferably provides a menu of well-defined components that can be chosen to compose a complete system depending on hardware capabilities, security needs, and application requirements.

Dynamic loading and unloading of components provides the flexibility that lets the system adapt to changing requirements.

The componentization makes it possible to change the implementation of a component without affecting the rest of the system. Minimalism makes it possible to use the system with severely restricted hardware budgets. It also forces the system to be understandable and flexible. Software components, when possible, are not tied to a particular layer of the system, but can be reused. For example, the same code that implements the system physical memory heap is used to provide application heaps over virtual memory. The key system building blocks are componentized. This includes the virtual memory system, IPC, and the scheduler in addition to filesystems, networking, drivers, and protection policies. Preferred embodiments of the present invention extend object-orientation both across address spaces and across protection levels.

In a preferred embodiment, components are located in separate address spaces only when there is a real reason for it, such as security or specific address space requirements. Thus, the price of multiple address spaces (and transitions thereof) is paid only where needed.

The present invention is directed to objects which are mutable by other objects and to a method for mutating objects. In general, the invention is directed to a computer having a memory storing computer-executable instructions supporting plural objects and a mutation object, the mutation object including a method for mutating any one of the plural objects. Preferably, each one of the plural objects includes a V-table, an interface corresponding to plural methods and an implementation of the methods, a V-table pointer pointing to the interface, and an interface pointer for each of the methods to a corresponding one of the implementations.

Preferably, the mutation object includes a mutation interface including a method for changing a selected one of the pointers of the selected object, a V-table pointer to the mutation interface, and a pointer from the mutation interface to an implementation of the method for mutating. The the mutation object mutates the V-table pointer so as to change the interface of the one object to a new interface corresponding to a new set of methods. The mutation object mutates the interface pointer to point to a new implementation, so as to change the implementation of a given one of the methods of the one object. Preferably, each one of the plural objects includes a state register storing a state of the one object, and the method of the mutation object changes the contents of the state register so as to mutate the state of the one object. Generally, the state register stores the value of a pointer of the one object. The pointer of the one object includes a VTable pointer and points to an implementation of a method of the one object.

The mutation object further includes a synchronization of the mutation of one of the plural objects with threads running in the one object. In one embodiment, the synchronization includes mutual exclusion, which prevents new threads from accessing the one object while other threads running in the object are permitted to finish. In another embodiment, the synchronization includes transactional synchronization, which rolls back the threads currently running in the one object and then permits mutation of the object. In yet another embodiment, the synchronization includes swizzling which suspends threads running in the one object, mutates the one object and modifies the states of the suspended in accordance with the mutation of the one object, and thereafter reactivates the suspended threads. In this latter embodiment, thread states are swizzled between clean points in the thread execution, whereby the thread becomes suspended at a clean point.

In another aspect, one of the plural objects includes an interposition object formed by the mutation object mutating a particular one of the plural objects and a copied object at least nearly identical to the one particular object, the interposition object differing from the one particular object in that the one particular object has a pointer to the copied object and a method of interposition between threads seeking the one particular object and the copied object. The interposition method may include a filter such as a read-only filter. The filter may provide access based upon the identity of the requesting thread. The copied object is a copy of the one particular object. The interposition object is formed by copying the one particular object and mutating the resulting copy while the copied object is the one particular object.

In accordance with another aspect, the invention is embodied in a computer operating system capable of supporting plural objects running in a computer having a working memory, the computer operating system including a kernel resident in the working memory at link time, and a loadable mutation object resident at link time outside of the working memory and dynamically loadable into the working memory at run time upon demand of one of the application programs, the mutation object including an interface with methods for mutating any one of the plural objects. The kernel includes a loader for loading the mutation object into the working memory in response to a demand from one of the plural objects. The computer further includes a storage memory separate from the working memory, the loadable mutation object residing at link time in the storage memory. The loader loads the mutation object from the storage memory to the working memory, and the loadable mutation object is terminable from the working memory upon lack of demand therefor by the plural objects. Preferably, the kernel of the operating system includes a Namespace for registering the mutation object upon the mutation object being loaded into the working memory, whereby the mutation object becomes available to each of the plural objects through the Namespace.

In accordance with a further aspect, the invention is embodied in a computerized system including at least one computer and having a memory storing computer-executable instructions supporting plural objects, a first address space and a second address space wherein respective ones of the plural objects reside, a mutation object, the mutation object including a method for mutating any one of the plural objects. One of the plural objects in the first address space includes a proxy object having a pointer to a destination one of the plural objects in the second address space, so that other objects in the first address space can invoke the destination object in the second address space through the proxy object in the first address space. The proxy object is formed by mutating a destination object in the first address space, and the destination object is formed by mutating a proxy object in the second address space.

In accordance with a yet further aspect, the invention is embodied in a method of providing object mobility in a computer having a memory storing computer-executable instructions supporting plural objects and having a first address space and a second address space wherein respective ones of the plural objects reside, one of the plural objects in the first address space including a proxy object having a pointer to a destination one of the plural objects in the second address space, whereby other objects in the first address space can invoke the destination object in the second address space through the proxy object in the first address space. The method includes mutating the proxy object in the first address space to become the destination object and mutating the destination object in the second address space to become the proxy object, whereby the proxy and destination objects are mobile between the first and second address spaces.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1A is a block diagram of an exemplary operating environment of the invention.

FIG. 1B is a block diagram of an operating system embodying the present invention in the computer illustrated in FIG. 1A.

FIG. 1C illustrates one application of the invention to form stacked virtual memories with a local virtual memory.

FIG. 2 illustrates a page table registry structure of a virtual memory manager of the operating system of FIG. 1B.

FIG. 3 illustrates the objects in the virtual memory manager.

FIG. 4 illustrates the virtual memory manager of FIG. 3 with a set of interfaces.

FIG. 5 illustrates the structure of an object in the operating system of FIG. 1B.

FIG. 6 illustrates the structure of the virtual memory view object of the operating system of FIG. 1B.

FIG. 7 illustrates the objects in a preferred implementation of the virtual memory manager.

FIG. 8 illustrates the Load VMM process in the operating system of FIG. 1B.

FIG. 9 illustrates the method of handling a virtual memory (VMM) fault in the operating system of FIG. 1B.

FIG. 10 illustrates the operation of the VMM fault handler in the operating system of FIG. 1B.

FIG. 11 illustrates the method for taking a VMM fault in the operating system of FIG. 1B.

FIG. 12 illustrates the operation of the context switch process in the operating system of FIG. 1B.

FIG. 13 illustrates the SwitchTo process in the operating system of FIG. 1B.

FIG. 14 illustrates the operation for unloading the virtual memory manager in the system of FIG. 1B.

FIG. 15 illustrates the process for handling a page fault in the system of FIG. 1B.

FIG. 16 illustrates a process by which a constructor creates a thread in the operating system of FIG. 1B.

FIG. 17 illustrates multiple views of memory provided by the VMView object of the operating system of FIG. 1B.

FIG. 18 illustrates multiple views of memory that can be obtained in accordance with FIG. 17.

FIG. 19 illustrates the basic features of a loadable interprocess communication (IPC) manager in the operating system of FIG. 1B.

FIG. 20 illustrates the process of loading of the IPC manager of FIG. 19.

FIG. 21 illustrates an interface between the IPC manager and other threads.

FIG. 22 illustrates intercommunication provided by the IPC manager between different address spaces.

FIG. 23 illustrates how an IPC trap is handled in the operating system of FIG. 1B.

FIG. 24A illustrates the operation of the IPC trap handler in the operating system of FIG. 1B.

FIG. 24B illustrates objects inside the loadable IPC system of a preferred embodiment of the present invention.

FIG. 24C illustrates objects in different address spaces connected by the loadable IPC system of FIG. 24B.

FIG. 25 illustrates the interface Imutate which provides object mutation in the operating system of FIG. 1B.

FIG. 26 illustrates one application of object mutation in the operating system of FIG. 1B.

FIG. 27 illustrates another application of object mutation applied to a Vtable.

FIG. 28 illustrates synchronization of object mutation by mutual exclusion.

FIG. 29 illustrates synchronization of object mutation by transactional synchronization.

FIG. 30A illustrates the process of object mutation by swizzling in accordance with a preferred embodiment of the invention.

FIG. 30B illustrates the structure of a thread relative to external objects prior to swizzling.

FIG. 30C illustrates the structure of the thread relative to the external objects corresponding to FIG. 30B after swizzling.

FIG. 31 illustrates an application of object mutation to achieve object interposition.

FIG. 32 illustrates an application of object mutation to carry out dynamic software upgrading.

FIG. 33 illustrates an application of object mutation to carry out run-time code generation.

FIG. 34 illustrates how to achieve object mobility using object mutation.

FIG. 35 illustrates how proxies may be used with object mutation to communicate across address spaces.

FIG. 36 illustrates a mutatable structure of the virtual memory manager.

FIG. 37 illustrates a method embodying the programming model of the invention.

FIG. 38 illustrates operations carried out with the demand-loading NameSpace in accordance with the programming model of FIG. 37.

FIG. 39 illustrates the loading of an object in accordance with the programming model of FIG. 37.

FIG. 40 illustrates an application of the programming model of FIG. 37 to plug-and-play technology.

FIGS. 41 and 42 illustrate an example of a conventional process for linking an executable image.

FIG. 43 illustrates an example of a conventional process for linking with shared libraries.

FIG. 44 illustrates a process in accordance with the present invention for linking an executable image using shared libraries.

FIG. 45 illustrates a process in accordance with the present invention for forming a dynamically linked library.

FIGS. 46A and 46B illustrate an example of a jump shortcutting process of the present invention.

FIGS. 47A and 47B illustrate an example of a jump shortcutting process as applied to data references in accordance with the present invention.

FIG. 48 illustrates an example of a post-link time compaction process of the present invention.

FIG. 49 illustrates a load time code synthesis process for virtual memory in accordance with the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Exemplary Operating Environment:

FIG. 1A and the following discussion are intended to provide a brief, general description of a suitable computing environment in which the invention may be implemented. Although not required, the invention will be described in the general context of computer-executable instructions, such as program modules, being executed by a personal computer. Generally, program modules include processes, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. Moreover, those skilled in the art will appreciate that the invention may be practiced with other computer system configurations, including inside various programmable peripheral interface cards such as 126, 128, 130, 144, 158, 148 in FIG. 1A, inside programmable peripherals such as disks, game controllers and accessories, speakers, modems, printers and the like, in hand-held devices, multiprocessor systems, microprocessor-based or programmable consumer electronics, network PCs, minicomputers, mainframe computers, and the like. Thus, for example, the present invention can be an operating system of an optimally minimized configuration, as described below, running inside a network interface card of the network interface 158 of FIG. 1A or in an embedded control system or in a communication-oriented device. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located both in local and in remote memory storage devices.

With reference to FIG. 1A, an exemplary system for implementing the invention includes a general purpose computing device in the form of a conventional personal computer 120, including a processing unit 121, a system memory 122, and a system bus 123 that couples various system components including the system memory to the processing unit 121. The system bus 123 may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. The system memory includes read only memory (ROM) 124 and random access memory (RAM) 125. A basic input/output system 126 (BIOS), containing the basic process that helps to transfer information between elements within the personal computer 120, such as during start-up, is stored in ROM 124. The personal computer 120 further includes a hard disk drive 127 for reading from and writing to a hard disk, not shown, a magnetic disk drive 128 for reading from or writing to a removable magnetic disk 129, and an optical disk drive 130 for reading from or writing to a removable optical disk 131 such as a CD ROM or other optical media. The hard disk drive 127, magnetic disk drive 128, and optical disk drive 130 are connected to the system bus 123 by a hard disk drive interface 132, a magnetic disk drive interface 133, and an optical drive interface 134, respectively. The drives and their associated computer-readable media provide nonvolatile storage of computer readable instructions, data structures, program modules and other data for the personal computer 120. Although the exemplary environment described herein employs a hard disk, a removable magnetic disk 129 and a removable optical disk 131, it should be appreciated by those skilled in the art that other types of computer readable media which can store data that is accessible by a computer, such as magnetic cassettes, flash memory cards, digital video disks, Bernoulli cartridges, random access memories (RAMs), read only memories (ROM), and the like, may also be used in the exemplary operating environment.

A number of program modules may be stored on the hard disk, magnetic disk 129, optical disk 131, ROM 124 or RAM 125, including an operating system 135, one or more application programs 136, other program modules 137, and program data 138. A user may enter commands and information into the personal computer 120 through input devices such as a keyboard 140 and pointing device 142. Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, scanner, or the like. These and other input devices are often connected to the processing unit 121 through a serial port interface 146 that is coupled to the system bus, but may be connected by other interfaces, such as a parallel port, game port or a universal serial bus (USB). A monitor 147 or other type of display device is also connected to the system bus 123 via an interface, such as a video adapter 148. In addition to the monitor, personal computers typically include other peripheral output devices (not shown), such as speakers and printers.

The personal computer 120 may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer 149. The remote computer 149 may be another personal computer, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the personal computer 120, although only a memory storage device 150 has been illustrated in FIG. 1A. The logical connections depicted in FIG. 1A include a local area network (LAN) 151 and a wide area network (WAN) 152. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and Internet.

When used in a LAN networking environment, the personal computer 120 is connected to the local network 151 through a network interface or adapter 153. When used in a WAN networking environment, the personal computer 120 typically includes a modem 154 or other means for establishing communications over the wide area network 152, such as the Internet. The modem 154, which may be internal or external, is connected to the system bus 123 via the serial port interface 146. In a networked environment, program modules depicted relative to the personal computer 120, or portions thereof, may be stored in the remote memory storage device. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used.

Introduction to the Architecture

In a preferred embodiment of the invention, the operating system components contain code and other metadata for classes of objects. When a component is loaded into an address space it is instantiated. The instantiated component creates object instances that communicate with other objects, potentially in other components. The objects expose their methods through Component Object Model (COM) [Brockschmidt95] interfaces. Threads execute code and synchronize through Mutexes and Condition variables. System components are typically written in C or C++ but there is no fundamental bias towards any particular language.

COM enables late binding, version compatibility and checking, transparency through proxies, cross language support, and is reasonably lightweight and efficient. Each object needs a method table pointer and a reference count. Each call adds one indirection for fetching the actual method pointer.

Component implementations in the preferred embodiment of the invention are rarely aware of their intended system layer. The same code can be used in different address spaces or contexts and can be nested. A filesystem can be applied to a file provided by another filesystem as well as to one provided by a disk driver. A heap can be applied to any memory: physical memory, memory allocated from another heap, or memory provided by a virtual memory manager. The loader loads modules into any address space.

Selection of System Components

What components should be part of a deployed system depends upon the application itself and its interface requirements, application memory requirements, security requirements, and the target hardware capabilities. Flexible loading of modules was an important design goal for the operating system described herein. The loading of components can be deferred until they are actually used by an application. Device drivers and runtime services typically fall into this category. Others can be loaded just prior to running an application, such as virtual memory for untrusted applications. Most services will terminate themselves when they are no longer needed.

Drivers and virtual memory can not be used when the hardware to support them is not present. An application that tries to use them will look them up in the demand-loading namespace. The lookup operation fails, either because the driver is absent or it returns a NULL pointer.

Execution Model

Components have code, static data, a stack and a number of dynamic objects. A heap object allows dynamic memory allocations. The stack is pointed to by the stack pointer register; it is allocated from the heap. In a physical memory system the initial size of the stack is also the maximum size of the stack; every byte has to be paid for by real memory. Thus in an embedded application the stack size must be chosen carefully. Most compilers can generate stack checks at function entry, to guard against stack overflows. In a virtual memory system, the stack does not have to be backed by real memory, which can be allocated on demand. The stack only consumes virtual address range and can thus be allocated liberally. A Real-Time application might still want to pre-allocate all memory in order to avoid run time fluctuations. In this case the existence of virtual memory does not affect the stack.

Memory for code and static data is also allocated from the heap. Code can be placed anywhere in memory if it is either position-independent (pc-relative) or relocatable. The Microsoft Visual C++ compiler, for instance, creates a compressed relocation table that the runtime loader uses to fix any references if the executable was placed in a different place in memory than it was linked for. All compilers for embedded use provide similar functionality, although the specific image formats and relocation schemes differ.

On the other hand, it is often found that most compilers do not support reentrancy. If the code in an image is not reentrant, it is still possible to execute multiple instances of the same image in the same address space. The code and data are simply loaded multiple times, each time relocated differently.

If the relocation information is not present, and a component virtually overlaps with another component it cannot be executed in the same address space. In this case a new address space is required, which in turn requires virtual memory.

System Components

An exemplary base set of system components in a preferred embodiment of the invention is now described.

Referring to FIG. 1B, an exemplary operating system in accordance with an embodiment of the invention has a kernel or link-time component 202 and a set of run-time loadable resources 204. The kernel 202 includes a set of software resources including, preferably, a HEAP (physical memory manager) 302, a loader 304, a support library 306, a timer 310, an interrupt control unit 312, a scheduler 314, thread support 316 including synchronization primitives 318, NameSpace 320, filesystem 322 and a startup program 324. The set of run-time loadable resources 204 are available to the system through the loader 304. The resources 204 include, preferably, a virtual memory manager (VMM) 362, inter-process communication 364, drivers 366, applications 368 and a network program 370. A minimal multi-threaded kernel may be provided in accordance with the present invention having only the thread support 316, the scheduler 314, the library 306, the timer 310 and the startup 324. If multi-threading is not desired, the kernel may be further minimized to include only the library 306, the timer 310 and the startup 324.

As illustrated in FIG. 1B, the ICU (interrupt control unit) 312 preferably includes the following software methods at link time: install VMM (virtual memory manager) trap handler 372, install IPC (inter-process communication) trap handler 374. These resources are preferably included in the interrupt control unit 312 because it is possible for such a system to take a VMM trap or an IPC trap or a page fault whether or not a VMM or IPC has been loaded.

Any one of the components contained in the set of loadable resources 202 may be fetched by the loader 304 and loaded into the operating system on a demand or as-needed basis during run time. The loader 304 registers the name of any such component that has been so loaded in NameSpace 320 so that all users in the system can find the component by querying NameSpace 320.

In particular, the VMM 372 is loadable upon demand into the operating system and may be unloaded when all demand for it disappears.

Different implementations of a virtual memory manager may be selected for different purposes during run time from a VMM library 380 storing a set of VMMs, as shown in FIG. 1B.

Heap

The Heap 302 implements (physical) memory management, allowing dynamic memory allocations with specifiable alignments. The constructor allows creating nested heaps or heaps over virtual memory.

Loader

The Loader 304 is used to load additional components into a running system. Most embedded systems do not provide a loader, and if not needed it can be eliminated at link time from this system as well. Multiple image formats are supported. The loader loads images into the same address space, or given a flag and a virtual memory system, it creates a new address space and loads the image in there.

No particular distinction is made herein between executables and DLLs (shared libraries). An executable is simply a DLL that exports no entry points besides main( ).

Support Library, Machine Initialization

The library 306 is a shared support library and includes common base utilities like memcpy and other compiler support routines, AtomicAdd, CurrentThread, etc. It is used by many system components and is available to applications.

Basic machine initialization code is used at startup and system reset. Most of the machine dependent code of the componentized operating system of the invention resides here.

Timer and Interrupt Drivers

A driver for the timer 310 is used by the scheduler 314 to keep track of time and for thread pre-emption. A driver for the Interrupt Control Unit (ICU) 312 dispatches interrupts and keeps a registry of interrupt routines, which can be installed and removed by other components. The system has no particular notion of a "device driver" per se.

It does enforce strict limits as to what an interrupt routine can do: wakeup a thread.

Scheduler

The scheduler 314 is a policy module that determines which thread should run at any given time. Low-level management of blocking and switching between threads is handled by the thread and synchronization components 316, 318.

The timer interrupt and thread and synchronization modules call into the scheduler 314, possibly passing callback functions as arguments.

Three example schedulers have been implemented: the null scheduler, a round robin scheduler, and a constraint based Real-Time scheduler. The null scheduler is for systems that use only one thread. The round robin scheduler provides time-sharing, it can easily be extended to handle dynamically changing priorities. Constraint scheduling is for consumer Real-Time applications and is described in [Jones97]. The existence of these schedulers proves that the scheduling interface is necessary and sufficient to implement all of the prior art scheduling policies.

Threads and Synchronization

The thread support and synchronization components 316, 318 provide basic thread support and synchronization primitives. Each thread is run in one address space. A thread is usually created in the address space of the component in which it is started. If there is no virtual memory, the address space is always the physical address space. Threads can be created in remote components as well as in local components that are part of the same address space. Threads can block on mutexes and conditions. They can inform the scheduler of their time constraints, but these calls will fail if the scheduler is not a constraint scheduler. The constraint scheduler performs priority inheritance when threads block on mutexes. Preferably, the thread support 316 and scheduler 314 are separated so that the scheduler 314 and be changed while maintaining thread support. So, a third party could change the scheduler 314 without affecting applications, so that the applications and the scheduler are isolated.

NamespacesA simple boot namespace where applications register objects may be provided. The Namespace 320 is a namespace that cooperates with the loader 304 in demand-loading and caching of components. A namespace may be used for displaying the status (e.g. running threads) and performance parameters (e.g. execution times) of a system during development. Filesystems are also namespaces.

Filesystem

Filesystem 322 is used to load additional components during runtime, and as permanent data repository. RomFS is a filesystem for read-only in-memory images (arbitrary files and the system can be merged into one image) and FatFS is for reading/writing disks. NetFile is a network filesystem client built on top of sockets.

Startup Program

Startup 324 is a program that is started once the system has been initialized. It can be a simple command interpreter that configures the system and launches applications, or the (only) application itself.

Network

The Network Program 370 provides the entire BSD4.4Lite network protocol code, with minor adaptations. The interface is a COM interface that provides sockets. The protocols operate the network drivers through another interface.

Other Components

A small Win32 compatibility library may be provided to make it easier to use WindowsNT code in some of the drivers and applications.

How Namespace is Used to Manage the Loading of Objects

Namespaces are used to let applications gain access to objects provided by other components. A namespace is like a filesystem directory tree, except it can hold any kind of objects, not just files. Namespaces can themselves be implemented by different components, including a filesystem that exports its directories as sub-namespaces, and files as registered objects. Namespaces can be registered into other namespaces, extending the directory tree. Location transparency of all objects automatically makes namespaces distributed. Therefore it is easily possible to view some other machine's NameSpace as a sub-Namespace of one's own machine. Namespaces can be filtered for access control or for providing different views for different applications. There is no limit as to the number of namespaces. A component can gain access to its namespace through a call to CurrentNamespace( ). In a minimal system, all applications share the same boot namespace.

When an application looks up a name in the namespace, it obtains a reference to the object: a local direct reference in case the object is local, or an automatically created proxy if the object is remote. (For remote objects, the interprocess communication (IPC) system described below in this specification is responsible for creating proxies, handling the delegation to remote objects, and reference counting.) A namespace is free to only give access to previously registered objects or to create objects on demand, as it sees fit. The namespace only handles the IUnknown interface. It is up to the application to obtain the proper interface from the object, using the QueryInterface method.

The interface of Namespace includes a method called Bind. The Bind method is used to request an object. The Bind method finds whether the requested object has already been loaded and, if not, Bind obtains the IUnknown interface of the requested object and returns it as an argument. Bind returns a pointer to the IUnknown's pointer to the requested object. Bind is the method that looks up the requested object in Namespace while Register is the method for registering the object in Namespace. After the object has been loaded, the Query Interface method may be used to query the object.

Objects can be made available to other components by registering them in a namespace. Every COM object has a virtual method table and at least the three methods derived from the base interface (the IUnknown) used with Namespace: QueryInterface for agreeing on the interface protocols, and AddRef and Release for reference counting. Specific interfaces have additional methods to do the actual work. In addition, a constructor is usually provided.

Garbage collection is done through reference counting. When Release has called for the last reference, the implementation can finalize and deallocate the object. Even if reference counting has limitations, it is convenient in a system environment due to its simplicity.

Interaction with objects using other garbage collection models can be achieved through proxies that intercept the IUnknown methods to update their root sets.

Loadable Virtual Memory Manager

Virtual memory provides virtual address spaces. Threads run in either a virtual address space or in the physical memory space. Components can be loaded into any address space. Component code may be shared between various address spaces like shared libraries. For instance, any code loaded into the physical memory space is made visible to applications regardless of their address space. There is nothing secret in the system's code, so there is no security problem. Virtual memory can be used to protect sensitive application code, for instance to defend it against disassembly and theft of intellectu