(12) United States Patent
`Devine et al.
`
`I 1111111111111111 11111 lllll 111111111111111 lllll lllll 111111111111111 11111111
`US006397242Bl
`US 6,397,242 Bl
`May 28, 2002
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) VIRTUALIZATION SYSTEM INCLUDING A
`VIRTUAL MACHINE MONITOR FOR A
`COMPUTER WITH A SEGMENTED
`ARCHITECTURE
`
`(75)
`
`Inventors: Scott W. Devine, Palo Alto; Edouard
`Bugnion, Menlo Park; Mendel
`Rosenblum, Stanford, all of CA (US)
`
`(73) Assignee: VMWare, Inc., Palo Alto, CA (US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by O days.
`
`(21) Appl. No.: 09/179,137
`
`(22) Filed:
`
`Oct. 26, 1998
`
`Related U.S. Application Data
`(60) Provisional application No. 60/085,685, filed on May 15,
`1998.
`
`(51)
`(52)
`
`(58)
`
`(56)
`
`Int. CI.7 . ... ... .. ... ... ... ... .. ... ... ... ... ... .. ... ... ... . G06F 9/00
`U.S. Cl. ........................... 709/1; 709/214; 709/321;
`703/27; 710/23; 711/148; 711/153
`Field of Search ............................ 709/100, 1, 200,
`709/224, 316,320,328,330,223; 717/131,
`138, 140; 703/26, 27; 714/1, 2, 47
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,747,040 A
`4,787,031 A
`4,792,895 A
`4,926,322 A
`4,974,159 A
`5,134,580 A
`5,167,023 A
`5,255,379 A
`5,307,504 A
`5,440,710 A
`5,488,716 A
`5,522,075 A
`5,560,013 A *
`5,652,869 A
`5,652,872 A
`5,721,922 A
`
`5/1988
`11/1988
`12/1988
`5/1990
`11/1990
`7/1992
`11/1992
`10/1993
`4/1994
`8/1995
`1/1996
`5/1996
`9/1996
`7/1997
`7/1997
`2/1998
`
`Blanset et al.
`Karger et al.
`Tallman
`Stimac et al.
`Hargrove et al.
`Bertram et al.
`de Nicolas et al.
`Melo
`Robinson et al.
`Richter et al.
`Schneider et al.
`Robinson et al.
`Scalzi et al. ................ 717 /138
`Herdeg et al.
`Richter et al.
`Dingwall
`
`VM
`
`5,761,477 A * 6/1998 Wahbe et al. .................. 709/1
`5,832,205 A
`11/1998 Kelly et al.
`
`OTHER PUBLICATIONS
`
`Goldberg, "Survey of Virtual Machine Research," Com(cid:173)
`puter, Jun. 1974, pp. 34-45.
`Ebciglu et al., "IBM Research Report-Daisy: Dynamic
`Compilation for 100% Architectural Compatibility", RC
`20538, Aug. 5, 1996.
`Bugnion, "Disco: Running Commodity Operating Systems
`on Scalable Multiprocessors," ACM Trans. on Computer
`Systems, vol. 15, No. 4, Nov. 1997, pp. 412-447.
`Bressoud, "Hypervisor-based Fault-tolerance," SIGOPS
`'95, Dec. 1995, pp. 1-11.
`Rosenblum et al., "Using the SimOS Machine Simulator to
`Study Complex Computer Systems," ACM Trans. on Mod(cid:173)
`eling and Computer Simulation, vol 7, No. 1, Jan. 1997, pp.
`78-103.
`Creasy, "The Origin of the VM/370 Time-Sharing System,"
`IBM J. Res. Develop., vol. 25, No. 5, Sep. 1981.
`Intel Architecture Software Developer's Manual, vol. 3,
`1997.
`* cited by examiner
`
`Primary Examiner-Majid Banankhah
`(74) Attorney, Agent, or Firm-Jeffrey Slusher
`
`(57)
`
`ABSTRACT
`
`In a computer that has hardware processor, and a memory,
`the invention provides a virtual machine monitor (VMM)
`and a virtual machine (VM) that has at least one virtual
`processor and is operatively connected to the VMM for
`running a sequence of VM instructions, which are either
`directly executable or non-directly executable. The VMM
`includes both a binary translation sub-system and a direct
`execution sub-system, as well as a sub-system that deter(cid:173)
`mines if VM instructions must be executed using binary
`translation, or if they can be executed using direct execution.
`Shadow descriptor tables in the VMM, corresponding to VM
`descriptor tables, segment tracking and memory tracing are
`used as factors in the decision of which execution mode to
`activate. The invention is particularly well-adapted for vir(cid:173)
`tualizing computers in which the hardware processor has an
`Intel x86 architecture.
`
`28 Claims, 6 Drawing Sheets
`
`100
`
`244
`
`200
`
`120 ~ ~ ~130
`
`R
`
`T
`
`170
`
`240
`
`204
`
`(□ECl~N>
`
`250
`
`202
`
`DIRECT
`EXECUTION
`
`TRACES
`
`Microsoft Ex. 1014, p. 1
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`I■-
`~
`N
`,I;;..
`'N
`'° -...,l
`~
`O'I
`rJ'J.
`e
`
`O'I
`
`'"""' 0 ....,
`~ ....
`'JJ. =(cid:173)~
`
`N
`0
`0
`N
`~CIO
`N
`'-<
`~
`~
`
`~ = ......
`~ ......
`~
`•
`r:JJ.
`d •
`
`TRACING
`MEMORY
`
`...
`
`COHERENCY
`
`CACHE
`
`TRANSLATION
`
`,.
`
`.. ,.
`
`FIG. 1
`
`REAL?
`
`NOT REVERSIBLE?
`
`REVERSIBLE?
`
`I
`
`SEGMENT TRACKING:
`
`VIRTUALIZATION I◄
`
`SEGMENT
`
`..
`
`►I TRANSLATION
`
`BINARY
`
`I
`
`MODE DECISION
`
`EXECUTION
`
`.....---------,/
`
`INSTRUCTIONS
`
`I NON-VIRTUALIZEABLE SEGMENTED
`
`ARCHITECTURE AND/OR
`
`VIRTUALIZATION OF
`
`_J ...
`
`INSTRUCTIONS
`
`SPECIFIC
`
`NON-VIRT. OF
`
`◄
`I
`
`EXECUTION
`
`DIRECT
`
`..
`
`SYSTEM
`
`_J ...
`
`USE OF HOS
`
`Microsoft Ex. 1014, p. 2
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`U.S. Patent
`
`May 28, 2002
`
`Sheet 2 of 6
`
`US 6,397,242 Bl
`
`-.::t
`0
`N
`
`0
`-.::t
`N
`
`Z
`0
`Cf)
`u
`w
`0
`
`z
`0
`I- w
`:'.:JI
`Cf) u
`z <(
`c2 u
`I-
`
`N
`0
`N
`
`\
`
`z
`I- 0
`u I-w::::,
`0::: u
`-w
`0 ><
`w
`
`0
`LO
`N
`
`>-u z
`w
`0:::
`w I
`0 u
`u
`I-
`
`~ Cf) ---z
`
`0:::
`0
`
`z
`<(
`0:::
`I-
`
`c..
`<(
`~
`u
`>(cid:173)Cf)
`u
`I-
`
`0
`('I)
`..-
`
`0
`0
`
`0
`t--
`..-
`
`Cf)
`0
`>
`
`I-
`o
`(9
`
`l(cid:173)
`0
`....J
`
`[!ill
`
`0
`N ..-
`
`0
`0 ..-
`
`I
`Cf)
`<(
`I
`
`u I-
`
`N
`-.::t
`N
`
`CX)
`-.::t
`N
`
`w
`~
`::::,
`Cf)
`w
`0:::
`
`Cf)
`
`w u
`
`<(
`0:::
`I-
`
`N .
`(!)
`LL
`
`I-
`o
`(9
`
`l(cid:173)
`0
`....J
`
`co
`-.::t
`N
`
`u z
`>(cid:173)Cf)
`
`[!ill
`
`0
`0
`N
`
`Microsoft Ex. 1014, p. 3
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`U.S. Patent
`
`May 28, 2002
`
`Sheet 3 of 6
`
`US 6,397,242 Bl
`
`VIRTUAL ADDRESS
`
`-1◄---0FFSET---..-i
`
`t
`
`BASE
`
`._ __ _.__....,___....____,, ____ ......... _...._---1....._____._
`
`I} PHYSICAL
`
`ADDRESS
`
`FIG. 3
`
`"304
`
`VISIBLE
`.J.,
`
`r
`
`HIDDEN
`
`OS:
`
`SELECTOR
`n
`
`TYPE
`(DATA)
`
`BASE
`
`LIMIT
`(OS LIM)
`
`PROT./
`ACCESS
`
`t
`DS:n
`I
`I
`LINEAR
`ADDRESS 1------------t..__ _ __ ---J
`SPACE
`-◄------ OS LIM - - - - - - - - -
`
`I
`
`FIG. 4
`
`Microsoft Ex. 1014, p. 4
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`U.S. Patent
`
`May 28, 2002
`
`Sheet 4 of 6
`
`US 6,397,242 Bl
`
`GDTR
`
`LDTR
`
`I INDEX(= 40) I
`
`I BASE I LIMIT I
`I - !
`
`I~
`
`,,.
`GOT
`TYPE CODE DATA TYPE TYPE DATA
`BASE
`BASE BASE BASE BASE BASE (LDT)
`LIMIT
`LIMIT
`LIMIT
`LIMIT
`PROT. PROT. PROT. PROT. PROT. PROTECTION
`L-y---JL-y---J
`
`LIMIT LIMIT (LDT) ~-
`•••
`
`~
`
`-
`
`IND EX:
`
`'"
`0
`
`ac&;~4
`
`CS:8
`
`DS:16
`
`32
`
`40
`
`_I
`, I
`
`TYPE
`BASE
`LIMIT
`PROT.
`
`i
`
`• I -
`
`-
`
`LDT:
`
`INDEX:
`
`4
`
`L
`12
`
`DATA
`BASE
`LIMIT
`PROT.
`y
`
`J
`20
`
`~
`
`'If"
`
`_I
`
`~
`
`•••
`
`28
`
`36
`
`44
`
`FIG. 5
`
`Microsoft Ex. 1014, p. 5
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`U.S. Patent
`
`May 28, 2002
`
`Sheet 5 of 6
`
`US 6,397,242 Bl
`
`r
`0
`....I
`
`I ~ - ~ ,.
`
`-
`
`r
`0
`....I
`
`-....
`-....
`
`r
`0
`(.!)
`
`U)
`
`0: ~o or
`
`oa...
`<C 0:
`IO
`U)U) w
`0
`
`U)
`0:
`0
`~r
`~a.. >5
`U) w
`0
`
`U)
`0:
`
`00 Wr
`I a..
`Oo:
`<C 0
`OU) w
`0
`
`.
`(!)
`LL
`
`I
`,.
`~ ~ ~
`I
`
`I
`I
`I
`I
`I
`I
`I
`I
`
`r
`0
`(.!)
`
`U)
`
`0: ~o or
`
`oa...
`<(0:
`I 0
`U)U) w
`0
`
`Microsoft Ex. 1014, p. 6
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`U.S. Patent
`
`May 28, 2002
`
`Sheet 6 of 6
`
`US 6,397,242 Bl
`
`1ooor120
`
`VM
`
`700
`
`120
`
`100
`
`750
`
`HOS
`
`VMM
`
`DRIVERS
`
`740
`
`t
`
`(204
`
`<DECISION)
`
`I
`
`~200 202~
`r 710
`
`HARDWARE
`
`FIG. 7
`
`VM
`
`120
`
`VMM
`
`100
`
`750
`
`710
`
`HARDWARE
`
`FIG. 8
`
`Microsoft Ex. 1014, p. 7
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`US 6,397,242 Bl
`
`1
`VIRTUALIZATION SYSTEM INCLUDING A
`VIRTUAL MACHINE MONITOR FOR A
`COMPUTER WITH A SEGMENTED
`ARCHITECTURE
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application claims priority from U.S. Provisional
`Patent Application No. 60/085,685, "Virtual Machine
`Monitor", filed May 15, 1998.
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`This invention relates to a computer architecture, includ- 15
`ing a virtual machine monitor, and a related operating
`method that allow virtualization of the resources of a mod-
`em computer system.
`2. Description of the Related Art
`The operating system plays a special role in today's
`personal computers and engineering work stations. Indeed,
`it is the only piece of software that is typically ordered at the
`same time the hardware itself is purchased. Of course, the
`customer can later change operating systems, upgrade to a
`newer version of the operating system, or even re-partition
`the hard drive to support multiple boots. In all cases,
`however, a single operating system runs at any given time on
`the computer. As a result, applications written for different
`operating systems cannot run concurrently on the system.
`Various solutions have been proposed to solve this prob(cid:173)
`lem and eliminate this restriction. These include virtual
`machine monitors, machine simulators, application
`emulators, operating system emulators, embedded operating
`systems, legacy virtual machine monitors, and boot manag(cid:173)
`ers.
`Virtual Machine Monitors
`One solution that was the subject of intense research in the
`late 1960's and 1970's came to be known as the "virtual
`machine monitor" (VMM). See, for example, R. P.
`Goldberg, "Survey of virtual machine research," IEEE 40
`Computer, Vol. 7, No. 6, 1974. During that time, moreover,
`IBM Corp. adopted a virtual machine monitor for use in its
`VM/370 system.
`A virtual machine monitor is a thin piece of software that
`runs directly on top of the hardware and virtualizes all the 45
`resources of the machine. Since the exported interface is the
`same as the hardware interface of the machine, the operating
`system cannot determine the presence of the VMM.
`Consequently, when the hardware interface is compatible
`with the underlying hardware, the same operating system 50
`can run either on top of the virtual machine monitor or on top
`of the raw hardware.
`Virtual machine monitors were popular at a time where
`hardware was scarce and operating systems were primitive.
`By virtualizing all the resources of the system, multiple
`independent operating systems could coexist on the same
`machine. For example, each user could have her own virtual
`machine running a single-user operating system.
`The research in virtual machine monitors also led to the
`design of processor architectures that were particularly 60
`suitable for virtualization. It allowed virtual machine moni-
`tors to use a technique known as "direct execution," which
`simplifies the implementation of the monitor and improves
`performance. With direct execution, the VMM sets up the
`processor in a mode with reduced privileges so that the 65
`operating system cannot directly execute its privileged
`instructions. The execution with reduced privileges gener-
`
`5
`
`2
`ates traps, for example when the operating system attempts
`to issue a privileged instruction. The VMM thus needs only
`to correctly emulate the traps to allow the correct execution
`of the operating system in the virtual machine.
`As hardware became cheaper and operating systems more
`sophisticated, VMM's based on direct execution began to
`lose their appeal. Recently, however, they have been pro(cid:173)
`posed to solve specific problems. For example, the Hyper(cid:173)
`visor system provides fault-tolerance, as is described by T.
`10 C. Bressoud and F. B. Schneider, in "Hypervisor-based fault
`tolerance," ACM Transactions on Computer Systems
`(TOCS),Vol. 14. (1), February 1996; and in U.S. Pat. No.
`5,488,716 "Fault tolerant computer system with shadow
`virtual processor," (Schneider, et al.). As another example,
`the Disco system runs commodity operating systems on
`scalable multiprocessors. See "Disco: Running Commodity
`Operating Systems on Scalable Multiprocessors," E.
`Bugnion, S. Devine, K. Govil and M. Rosenblum, ACM
`Transactions on Computer Systems (TOCS), Vol. 15, No. 4,
`20 November 1997, pp. 412-447.
`Virtual machine monitors can also provide architectural
`compatibility between different processor architectures by
`using a technique known as either "binary emulation" or
`"binary translation." In these systems, the VMM cannot use
`25 direct execution since the virtual and underlying architec(cid:173)
`tures mismatch; rather, they must emulate the virtual archi(cid:173)
`tecture on top of the underlying one. This allows entire
`virtual machines (operating systems and applications) writ(cid:173)
`ten for a particular processor architecture to run on top of
`30 one another. For example, the IBM DAISY system has
`recently been proposed to run PowerPC and x86 systems on
`top of a VLIW architecture. See, for example, K. Ebcioglu
`and E. R. Altman, "DAISY: Compilation for 100% Archi(cid:173)
`tectural Compatibility," Proceedings of the 24th Interna-
`35 tional Symposium on Computer Architecture, 1997.
`Machine Simulators/Emulators
`Machine simulators, also known as machine emulators,
`run as application programs on top of an existing operating
`system. They emulate all the components of a given com(cid:173)
`puter system with enough accuracy to run an operating
`system and its applications. Machine simulators are often
`used in research to study the performance of multiproces(cid:173)
`sors. See, for example, M. Rosenblum, et al., "Using the
`SimOS machine simulator to study complex computer
`systems," ACM Transactions on Modeling and Computer
`Simulation, Vol. 7, No. 1, January 1997. They have also been
`used to simulate an Intel x86 machine as the "VirtualPC" or
`"RealPC" products on a PowerPC-based Apple Macintosh
`system.
`Machine simulators share binary emulation techniques
`with some VMM's such as DAISY. They differentiate them(cid:173)
`selves from VMM's, however, in that they run on top of a
`host operating system. This has a number of advantages as
`they can use the services provided by the operating system.
`55 On the other hand, these systems can also be somewhat
`constrained by the host operating system. For example, an
`operating system that provides protection never allows
`application programs to issue privileged instructions or to
`change its address space directly. These constraints typically
`lead to significant overheads, especially when running on
`top of operating systems that are protected from applica-
`tions.
`Application Emulators
`Like machine simulators, application emulators also run
`as an application program in order to provide compatibility
`across different processor architectures. Unlike machine
`simulators, however, they emulate application-level soft-
`
`Microsoft Ex. 1014, p. 8
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`US 6,397,242 Bl
`
`3
`ware and convert the application's system calls into direct
`calls into the host operating system. These systems have
`been used in research for architectural studies, as well as to
`run legacy binaries written for the 68000 architecture on
`newer PowerPC-based Macintosh systems. They have also
`been also been used to run x86 applications written for
`Microsoft NT on Alpha work stations running Microsoft NT.
`In all cases, the expected operating system matches the
`underlying one, which simplifies the implementation. Other
`systems such as the known Insigna's SoftWindows use
`binary emulation to run Windows applications and a modi(cid:173)
`fied version of the Windows operating system on platforms
`other than PCS. At least two known systems allow Macin(cid:173)
`tosh applications to run on other systems: the Executer runs
`them on Intel processors running Linux or Next and MAE
`runs them on top of the Unix operating system.
`Operating System Emulators
`Operating system (OS) emulators allow applications writ(cid:173)
`ten for one given operating system application binary inter(cid:173)
`face (ABI) to run on another operating system. They trans(cid:173)
`late all system calls made by the application for the original
`operating system into a sequence of system calls to the
`underlying operating system. ABI emulators are currently
`used to allow Unix applications to run on Window NT (the
`Softway OpenNT emulator) and to run applications written
`for Microsoft's operating systems on public-domain oper(cid:173)
`ating systems (the Linux WINE project).
`Unlike virtual machine monitors and machine simulators,
`which are essentially independent of the operating system,
`ABI emulators are intimately tied with the operating system
`that they are emulating. Operating system emulators differ
`from application emulators in that the applications are
`already compiled for the instruction set architecture of the
`target processor. The OS emulator does not need to worry
`about the execution of the applications, but rather only of the
`calls that it makes to the underlying operating system.
`Embedded Operating Systems
`Emulating an ABI at the user level is not an option if the
`goal is to provide additional guarantees to the applications
`that are not provided by the host operating system. For
`example, the VenturCom RTX Real-Time subsystem
`embeds a real-time kernel within the Microsoft NT operat(cid:173)
`ing system. This effectively allows real-time processes to
`co-exist with traditional NT processes within the same
`system.
`This co-existence requires the modification of the lowest
`levels of the operating system, that is, its Hardware Abstrac(cid:173)
`tion Layer (HAL). This allows the RTX system to first
`handle all 1/0 interrupts. This solution is tightly coupled
`with WindowsNT, since both environments share the same
`address space and interrupts entry points.
`Legacy Virtual Machine Monitors
`Certain processors, most notably those with the Intel
`architecture, contain special execution modes that are spe(cid:173)
`cifically designed to virtualize a given legacy architecture. 55
`This mode is designed to support the strict virtualization of
`the legacy architecture, but not of the existing architecture.
`A legacy virtual machine monitor consists of the appro(cid:173)
`priate software support that allows running the legacy oper(cid:173)
`ating system using the special mode of the processor.
`Specifically, Microsoft's DOS virtual machine runs DOS in
`a virtual machine on top of Microsoft Windows and NT. As
`another example, the freeware DOSEMU system runs DOS
`on top of Linux.
`Although these systems are commonly referred to as a
`form of virtual machine monitor, they run either on top of an
`existing operating system, such as DOSEMU, or as part of
`
`4
`an existing operating system such as Microsoft Windows
`and Microsoft NT. In this respect, they are quite different
`from the true virtual machine monitors described above, and
`from the definition of the term "virtual machine monitor"
`5 applied to the invention described below.
`Boot Managers
`Finally, boot managers such as the public-domain LILO
`and the commercial System Commander facilitate changing
`operating systems by managing multiple partitions on the
`10 hard drive. The user must, however, reboot the computer to
`change perating systems. Boot managers therefore do not
`allow applications written for different operating systems to
`coexist. Rather, they simply allow the user to reboot another
`operating system without having to reinstall it, that is,
`15 without having to remove the previous operating system.
`General Shortcomings of the Prior Art
`All of the systems described above are designed to allow
`applications designed for one version or type of operating
`system to run on systems with a different version or type of
`20 operating system. As usual, the designer of such a system
`must try to meet different requirements, which are often
`competing, and sometimes apparently mutually exclusive.
`Virtual machine monitors (VMM) have many attractive
`properties. For example, conventional VMMs outperform
`25 machine emulators since they run at system level without the
`overhead and constraint of an existing operating system.
`They are, moreover, more general than application and
`operating system emulators since they can run any applica(cid:173)
`tion and any operating system written for the virtual
`30 machine architecture. Furthermore, they allow modern oper(cid:173)
`ating systems to coexist, not just the legacy operating
`systems that legacy virtual machine monitors allow. Finally,
`they allow application written for different operating sys(cid:173)
`tems to time-share the processor; in this respect they differ
`35 from boot managers, which require a complete "re-boot,"
`that is, system restart, between applications.
`As is the typical case in the engineering world, the
`attractive properties of VMMs come with corresponding
`drawbacks. A major drawback is the lack of portability of the
`40 VMM itself-conventional VMMs are intimately tied to the
`hardware that they run on, and to the hardware they emulate.
`Also, the virtualization of all the resources of the system
`generally leads to diminished performance.
`As is mentioned above, certain architectures (so-called
`45 "strictly virtualizeable" architectures), allow VMMs to use a
`technique known as "direct execution" to run the virtual
`machines. This technique maximizes performance by letting
`the virtual machine run directly on the hardware in all cases
`where it is safe to do so. Specifically, it runs the operating
`50 system in the virtual machine with reduced privileges so that
`the effect of any instruction sequence is guaranteed to be
`contained in the virtual machine. Because of this, the VMM
`must handle only the traps that result from attempts by the
`virtual machine to issue privileged instructions.
`Unfortunately, many current architectures are not strictly
`virtualizeable. This may be because either their instructions
`are non-virtualizeable, or they have segmented architectures
`that are non-virtualizeable, or both. Unfortunately, the all(cid:173)
`but-ubiquitous Intel x86 processor family has both of these
`60 problematic properties, that is, both non-virtualizeable
`instructions and non-reversible segmentation. Consequently,
`no VMM based exclusively on direct execution can com(cid:173)
`pletely virtualize the x86 architecture.
`Complete virtualization of even the Intel x86 architecture
`65 using binary translation is of course possible, but the loss of
`performance would be significant. Note that, unlike cross(cid:173)
`architectural systems such as DAISY, in which the processor
`
`Microsoft Ex. 1014, p. 9
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`US 6,397,242 Bl
`
`5
`contains specific support for emulation, the Intel x86 was not
`designed to run a binary translator. Consequently, no con(cid:173)
`ventional x86-based system has been able to successfully
`virtualize the Intel x86 processor itself.
`What is needed is therefore a VMM that is able to function
`with both the speed of a direct-execution system and the
`flexibility of a binary-translation system. The VMM should
`also have an efficient switch between the two execution
`modes. This invention provides such a system.
`
`SUMMARY OF THE INVENTION
`
`The invention provides a system for virtualizing a com(cid:173)
`puter. The invention comprises a hardware processor; a
`memory; a virtual machine monitor (VMM); and a virtual
`machine (VM). The VM has at least one virtual processor
`and is operatively connected to the VMM for running a
`sequence of VM instructions. The VM instruction include
`directly executable VM instructions and non-directly
`executable instructions.
`The VMM according to the invention includes: a binary
`translation sub-system; a direct execution sub-system; and
`an execution decision module/sub-system that implements a
`decision function for discriminating between the directly
`executable and non-directly executable VM instructions,
`and for selectively directing the VMM to activate the direct
`execution subsystem for execution by the hardware proces(cid:173)
`sor of the directly executable VM instructions and to activate
`the binary translation subsystem for execution on the hard(cid:173)
`ware processor of the non-directly executable VM instruc-
`tions.
`In a preferred embodiment of the invention, the hardware
`processor has a plurality of privilege levels, as well as
`virtualizeable instructions and non-virtualizeable instruc(cid:173)
`tions. The non-virtualizeable instructions have predefined 35
`semantics that depend on the privilege level, and the seman(cid:173)
`tics of at least two of the privilege levels are mutually
`different and non-trapping. In this embodiment, the VM has
`a privileged operation mode and a non-privileged operation
`mode and the decision sub-system is further provided for 40
`directing the VMM to activate the binary translation sub(cid:173)
`system when the VM is in the privileged operation mode.
`According to another aspect of the invention, the hard(cid:173)
`ware processor has a plurality of hardware segments and at
`least one hardware segment descriptor table that is stored in 45
`the memory and that has, as entries, hardware segment
`descriptors. The VM has VM descriptor tables that in turn
`have, as entries, VM segment descriptors. Furthermore, the
`virtual processor has virtual segments. In this preferred
`embodiment, the VMM includes VMM descriptor tables,
`including shadow descriptors, that correspond to predeter(cid:173)
`mined ones of the VM descriptors tables. The VMM also
`includes a segment tracking sub-system/module that com(cid:173)
`pares the shadow descriptors with their corresponding VM
`segment descriptors, and indicates any lack of correspon(cid:173)
`dence between shadow descriptor tables with their corre(cid:173)
`sponding VM descriptor tables, and updates the shadow
`descriptors so that they correspond to their respective cor(cid:173)
`responding VM segment descriptors.
`The VMM in the preferred embodiment of the invention
`additionally includes one cached entry in the VMM descrip(cid:173)
`tor tables for each segment of the processor, the binary
`translation sub-system selectively accessing each cached
`entry instead of the corresponding shadow entry.
`Furthermore, the hardware processor includes a detection
`sub-system that detects attempts by the VM to load VMM
`descriptors other than shadow descriptors, and updates the
`
`25
`
`30
`
`6
`VMM descriptor table so that the cached entry correspond(cid:173)
`ing to the processor segment also corresponds to the VM
`segment descriptor. The VMM thereby also uses binary
`translation using this cached entry until the processor seg-
`s ment is subsequently loaded with a VMM descriptor that is
`a shadow descriptor.
`In another aspect of the invention, the hardware processor
`has predetermined caching semantics and includes non(cid:173)
`reversible state information. The segment tracking sub-
`10 system is further provided for detecting attempts by the VM
`to modify any VM segment descriptor that leads to a
`non-reversible processor segment. The VMM then also
`updates the VMM descriptor table so that the cached entry
`corresponding to the processor segment also corresponds to
`15 the VM segment descriptor, before any modification of the
`VM segment descriptor. The decision sub-system is further
`provided for directing the VMM to activate the binary
`translation sub-system when the segment-tracking sub(cid:173)
`system has detected creation of a non-reversible segment,
`20 and the binary translation sub-system uses the cached entry
`until the processor segment is subsequently loaded with a
`VMM descriptor that is a shadow descriptor.
`According to yet another aspect of the invention, the
`hardware processor has a native mode; and the virtual
`processor in the VM has native and non-native execution
`modes, in which the non-native execution modes are inde(cid:173)
`pendent of the VM segment descriptor tables for accessing
`segments. The decision sub-system is then further provided
`for directing the VMM to operate using the cached descrip(cid:173)
`tors and to activate the binary translation sub-system when
`the hardware processor is in the non-native execution mode.
`The binary translation sub-system thereby uses the cached
`entry in the native mode when at least one of the following
`conditions is present: the virtual processor is in one of the
`non-native execution modes; and at least one virtual pro(cid:173)
`cessor segment has been most recently loaded in one of the
`non-native execution modes.
`According to still another aspect of the invention, the
`hardware processor and the virtual processor each has native
`and non-native execution modes, in which at least one of the
`non-native execution modes is strictly virtualizeable. The
`decision sub-system then directs the VMM to run in the
`same execution mode as the virtual processor.
`In implementations of the invention in which the hard-
`ware processor has a memory management unit (MMU), the
`invention further comprises a memory tracing mechanism,
`included in the VMM, for detecting, via the MMU, accesses
`to selectable memory portions. The segment tracking sub-
`so system is then operatively connected to the memory tracing
`mechanism for detecting accesses to selected memory por(cid:173)
`tions.
`The invention is particularly well-suited for virtualizing
`computer systems in which the hardware processor has an
`ss Intel x86 architecture that is compatible with at least the
`Intel 80386 processor. Where the hardware processor has an
`Intel x86 architecture with at least one non-virtualizeable
`instruction, and the virtual processor in the VM also has the
`Intel x86 architecture, the virtual processor has a plurality of
`60 processing states at a plurality of current privilege levels
`(CPL), an input/output privilege level, and means for dis(cid:173)
`abling interrupts. In such a system, the decision sub-system
`is further provided for directing the VMM to activate the
`binary translation sub-system whenever at least one of the
`65 following conditions occur: a) the CPL of the virtual pro(cid:173)
`cessor is set to a most privileged level; b) the inpuvoutput
`privilege level of the virtual processor is greater than zero;
`
`Microsoft Ex. 1014, p. 10
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`US 6,397,242 Bl
`
`7
`and c) interrupts are disabled in the virtual processor. The
`VMM, by means of the binary translation sub-system,
`thereby virtualizes all non-virtualizeable instructions of the
`virtual processor as a predetermined function of the pro(cid:173)
`cessing state of the virtual processor.
`In the preferred embodiment of the invention, the hard(cid:173)
`ware processor has an Intel x86 architecture with a protected
`operation mode, a real operation mode, and a system man(cid:173)
`agement operation mode. The VMM then operates within
`the protected operation mode and uses binary translation to 10
`execute VM instructions whenever the real and system
`management operation modes of the processor are to be
`virtualized. On the other hand, where the hardware proces(cid:173)
`sor has an Intel x86 architecture with a strictly virtualizeable
`virtual 8086 mode, the VMM uses direct execution when- 15
`ever the virtual 8086 mode of the processor is to be
`virtualized.
`The invention can also be used for virtualizing systems in
`which the computer has a plurality of hardware processors.
`In such cases, the invention further comprises a plurality of
`virtual processors included in the virtual machine; and, in
`the VMM, VMM descriptor tables for each virtual processor.
`The segment tracking sub-system then includes means for
`indicating to the VMM, on selected ones of the plurality of
`hardware processors, any lack of correspondence between
`the shadow descriptor tables and their corresponding VM
`descriptor tables. Additionally, for each hardware processor
`on which the VMM is running, the decision sub-system
`discriminates between the directly executable and the non(cid:173)
`directly executable VM instructions independent of the 30
`remaining hardware processors.
`
`5
`
`8
`concepts of the invention is discussed. Third, particular
`features of the virtual machine monitor (VMM) according to
`the invention that enable dual execution mode operation are
`described.
`In connection with the description of the preferred VMM,
`the structure of a preferred binary translation execution
`engine is described. Note that binary translation is a tech(cid:173)
`nique that allows the efficient emulation of binary instruc(cid:173)
`tion sequences. In the discussion of the invention below,
`binary translation is referred to instead of binary emulation
`since this is the correct term for the technique used in the
`preferred embodiment of the invention.
`Fourth, a system that has an existing operating system and
`that includes the VMM according to the invention is
`described. Finally, a system in which the invention directly
`controls hardware devices with no assistance from a host
`operating system is illustrated and described.
`Architectural Concepts and Issues
`Before attempting to unders