Mechanism: Limited Direct Execution

1 6 Mechanism: Limited Direct ExecutionIn order to virtualize the CPU, the operating system needs to somehowshare the physical CPU among many jobs running seemingly at thesametime. The basic idea is simple: run one process for a little while, thenrun another one, and so forth. Bytime sharingthe CPU in this manner,virtualization is are a few challenges, however, in building such virtualizationmachinery. The first isperformance: how can we implement virtualiza-tion without adding excessive overhead to the system? The secondiscontrol: how can we run processes efficiently while retaining control overthe CPU? Control is particularly important to the OS, as it is in charge ofresources; without control, a process could simply run forever and takeover the machine, or access information that it should not be allowedtoaccess. Obtaining high performance while maintaining controlis thusone of the central challenges in building an operating :HOWTOEFFICIENTLYVIRTUALIZETHECPU WITHCONTROLThe OS must virtualize the CPU in an efficient manner while retainingcontrol over the system.

2 To do so, both hardware and operating-systemsupport will be required. The OS will often use a judicious bit of hard-ware support in order to accomplish its work Basic Technique: Limited Direct ExecutionTo make a program run as fast as one might expect, not surprisinglyOS developers came up with a technique, which we calllimited directexecution. The Direct Execution part of the idea is simple: just run theprogram directly on the CPU. Thus, when the OS wishes to start a pro-gram running, it creates a process entry for it in a process list,allocatessome memory for it, loads the program code into memory (from disk), lo-cates its entry point ( , themain()routine or something similar), jumps12 MECHANISM: LIMITEDDIRECTEXECUTIONOSP rogramCreate entry for process listAllocate memory for programLoad program into memorySet up stack with argc/argvClear registersExecutecallmain()Run main()Executereturnfrom mainFree memory of processRemove from process listFigure : Direct Execution Protocol (Without Limits)to it, and starts running the user s code.

3 Figure shows this basic di-rect Execution protocol (without any limits, yet), using a normal call andreturn to jump to the program smain()and later back into the simple, no? But this approach gives rise to a few problemsin our quest to virtualize the CPU. The first is simple: if we just run aprogram, how can the OS make sure the program doesn t do anythingthat we don t want it to do, while still running it efficiently? The second:when we are running a process, how does the operating system stop itfrom running and switch to another process, thus implementing thetimesharingwe require to virtualize the CPU?In answering these questions below, we ll get a much better sense ofwhat is needed to virtualize the CPU. In developing these techniques,we ll also see where the Limited part of the name arises from; withoutlimits on running programs, the OS wouldn t be in control of anythingand thus would be just a library a very sad state of affairs foranaspiring operating system!

4 Problem #1: Restricted OperationsDirect Execution has the obvious advantage of being fast; the programruns natively on the hardware CPU and thus executes as quicklyas onewould expect. But running on the CPU introduces a problem: what ifthe process wishes to perform some kind of restricted operation, suchas issuing an I/O request to a disk, or gaining access to more systemresources such as CPU or memory?THECRUX: HOWTOPERFORMRESTRICTEDOPERATIONSA process must be able to perform I/O and some other restricted oper-ations, but without giving the process complete control over the can the OS and hardware work together to do so?OPERATINGSYSTEMS[ ] : LIMITEDDIRECTEXECUTION3 ASIDE: WHYSYSTEMCALLSLOOKLIKEPROCEDURECALLSYou may wonder why a call to a system call, such asopen()orread(),looks exactly like a typical procedure call in C; that is, if it looks just likea procedure call, how does the system know it s a system call, and doallthe right stuff?

5 The simple reason: itisa procedure call, but hidden in-side that procedure call is the famous trap instruction. More specifically,when you callopen()(for example), you are executing a procedure callinto the C library. Therein, whether foropen()or any of the other sys-tem calls provided, the library uses an agreed-upon calling conventionwith the kernel to put the arguments toopen()in well-known locations( , on the stack, or in specific registers), puts the system-call numberinto a well-known location as well (again, onto the stack or a register),and then executes the aforementioned trap instruction. The codein thelibrary after the trap unpacks return values and returns control to theprogram that issued the system call. Thus, the parts of the C library thatmake system calls are hand-coded in assembly, as they need to carefullyfollow convention in order to process arguments and return values cor-rectly, as well as execute the hardware-specific trap instruction.

6 And nowyou know why you personally don t have to write assembly code to trapinto an OS; somebody has already written that assembly for approach would simply be to let any process do whatever it wantsin terms of I/O and other related operations. However, doing so wouldprevent the construction of many kinds of systems that are desirable. Forexample, if we wish to build a file system that checks permissions beforegranting access to a file, we can t simply let any user process issue I/Osto the disk; if we did, a process could simply read or write the entire diskand thus all protections would be , the approach we take is to introduce a new processor mode,known asuser mode; code that runs in user mode is restricted in what itcan do. For example, when running in user mode, a process can t issueI/O requests; doing so would result in the processor raising an exception;the OS would then likely kill the contrast to user mode iskernel mode, which the operating system(or kernel) runs in.

7 In this mode, code that runs can do what it likes, in-cluding privileged operations such as issuing I/O requests and executingall types of restricted are still left with a challenge, however: what should a user pro-cess do when it wishes to perform some kind of privileged operation,such as reading from disk? To enable this, virtually all modernhard-ware provides the ability for user programs to perform asystem on ancient machines such as the Atlas [K+61,L78], system callsallow the kernel to carefully expose certain key pieces of functionality touser programs, such as accessing the file system, creating anddestroy-ing processes, communicating with other processes, and allocating morec 2008 19, ARPACI-DUSSEAUTHREEEASYPIECES4 MECHANISM: LIMITEDDIRECTEXECUTIONTIP: USEPROTECTEDCONTROLTRANSFERThe hardware assists the OS by providing different modes of mode, applications do not have full access to hardware mode, the OS has access to the full resources of the instructions totrapinto the kernel andreturn-from-trapback touser-mode programs are also provided, as well as instructions that allowthe OS to tell the hardware where thetrap tableresides in Most operating systems provide a few hundred calls (see thePOSIX standard for details [P10]); early Unix systems exposed amoreconcise subset of around twenty execute a system call, a program must execute a specialtrapinstruc-tion.

8 This instruction simultaneously jumps into the kernel and raises theprivilege level to kernel mode; once in the kernel, the system can now per-form whatever privileged operations are needed (if allowed), and thus dothe required work for the calling process. When finished, the OS calls aspecialreturn-from-trapinstruction, which, as you might expect, returnsinto the calling user program while simultaneously reducing the privi-lege level back to user hardware needs to be a bit careful when executing a trap, in that itmust make sure to save enough of the caller s registers in order tobe ableto return correctly when the OS issues the return-from-trap x86, for example, the processor will push the program counter, flags,and a few other registers onto a per-processkernel stack; the return-from-trap will pop these values off the stack and resume Execution of the user-mode program (see the Intel systems manuals [I11] for details).

9 Otherhardware systems use different conventions, but the basic concepts aresimilar across is one important detail left out of this discussion: how does thetrap know which code to run inside the OS? Clearly, the calling processcan t specify an address to jump to (as you would when making a pro-cedure call); doing so would allow programs to jump anywhere intothekernel which clearly is aVery Bad Idea1. Thus the kernel must carefullycontrol what code executes upon a kernel does so by setting up atrap tableat boot time. When themachine boots up, it does so in privileged (kernel) mode, and thusis freeto configure machine hardware as need be. One of the first things the OSthus does is to tell the hardware what code to run when certain excep-tional events occur. For example, what code should run when a hard-disk interrupt takes place, when a keyboard interrupt occurs,or whena program makes a system call?

10 The OS informs the hardware of the1 Imagine jumping into code to access a file, but just after a permissioncheck; in fact, it islikely such an ability would enable a wily programmer to get the kernel to run arbitrary codesequences [S07]. In general, try to avoid Very Bad Ideas like this [ ] : LIMITEDDIRECTEXECUTION5OS @ bootHardware(kernel mode)initialize trap tableremember address handlerOS @ runHardwareProgram(kernel mode)(user mode)Create entry for process listAllocate memory for programLoad program into memorySetup user stack with argvFill kernel stack with reg/PCreturn-from-traprestore regs(from kernel stack)move to user modejump to mainRun main()..Call system calltrapinto OSsave regs(to kernel stack)move to kernel modejump to trap handlerHandle trapDo work of syscallreturn-from-traprestore regs(from kernel stack)move to user modejump to PC after from maintrap(viaexit())Free memory of processRemove from process listFigure : Limited Direct Execution Protocollocations of thesetrap handlers, usually with some kind of special in-struction.