Assignment 3, Solutions

Part of the homework for 22C:169, Spring 2011
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. Background: Different systems have performed system calls in many different ways. On one historic system, the address space was divided in half. The low half of the address space was the operating system, the high half was for applications code. All memory references (loads, stores, jumps and calls) to the low half of memory from the high half were forbidden -- any attempt to perform such an operation forced a trap to the operating system.

    In general, when a trap occurs, the registers of the program causing the trap are saved, including the program counter. The exact details of how this is done vary from system to system and are irrelevant for our purposes. What matters is that the trap service routine in the operating system has full access to everything about the program that caused the trap. The system can inspect the user's registers, the system can determine what instruction was executed to cause the trap, and the system can determine what memory address was referenced, if a memory reference caused the trap.

    To simplify linking to operating system services, the system designers have opted to use normal call instructions, and to call system services by calls to the actual address of the code for those services. Thus, if the protection mechanism is disabled, well-behaved programs will execute normally, but there will be no defense against malicious or erroneous programs.

    Under this architecture, a return from a system service is done with a simple return instruction. When this instruction assigns a value to the PC with its high bit set, the system is back in user mode.

    a) Outline the logic of a trap handler for this machine that recognizes system calls and dispatches control to the appropriate system service routines. Don't forget to arrange things so that the system service can return properly when it is done, and don't forget that a malicious application could attempt to directly call a system routine that was not supposed to be called directly by users. (1.0 points)

    1. like all trap handlers, begin by saving all the registers.
    2. using the saved PC, find what instruction caused the trap.
    3. if the instruction was a call instruction go on
    4. using the saved registers and instruction, get the destination address.
    5. if the address was the entry point of a system call, go on.
    6. working with the saved registers, simulate a call to the destination address.
    7. Finally, like all trap handlers, restore the registers and return.

    The return from trap at the end of the trap handler will be a return to the entry point of the system call, with the registers restored to the values the caller provided, and with the return address set so that the system call can return directly to the user.

    If the above trap handler finds a violation (not a call instruction, not a call to a permitted address), it should raise an exception in the user program.

    Note that there is an inferior solution in which the trap handler calls the system call. In this case, the return from trap happens at the end of the handler. and all of the code is more difficult to get correct, particularly under the rule that the code should work identically, for well behaved programs, if the memory protection mechanism is turned off.

    b) Where does parameter validity checking belong in this architecture? Is it something that you can reasonably expect the trap service routine to perform, or is it something that must be incorporated into the code for each system service routine? Justify your answer with an example. (1.0 points)

    It belongs in the entry code of each system call, since the constraints that must be tested depend on which system call is being used. An attempt to design a centralized parameter checking mechanism would require some kind of table, for each system call listing what parameter checks to perform. The net result would be some kind of interpreter that would interpret the table entry and try to figure out what checks to perform. It would be simpler to simply perform the correct checks in the prologue code of each system call.

  2. Background: On another historic system, there were two separate virtual memory maps in the memory management unit, one for user programs and one for the system. The machine had a reserved instruction TRAP that forced a trap. This was used for system calls. The TRAP instruction had an unused 8-bit field that was available to encode which system call was intended -- so the field was called the trap-code field.

    The privilege bit in the processor status word indicated which memory map was currently being used, and there was a second bit in the PSW that indicated the previous map. A trap first saved the old PC and PSW and then copied the privilige bit to the previous bit before setting the privilege bit to zero and setting the PC to the entry point of the trap service routine. The trap service routine, after making sure all the registers are saved properly, looks at the trap-code field and uses it to select one of 256 system call entry points.

    There were two special instructions, LOADP and STOREP that allowed a program to load data from the previous address space or to store data in the previous address space.

    a) Suppose parameters are passed on the stack, so the way a program called a system service routine is to first push each of the parameters and then use the appropriate trap. Outline how the code for a particular system call would go about getting the its parameters. (1.0 points)

    First, get the saved stack pointer from the trap handler, and then compute the addresses of the parameters by adding the appropriate displacements to the stack pointer. Finally, load the parameters using LOADP.

    b) Suppose an application needs to pass a pointer, for example, a pointer to an input/output buffer. How does the system code access this buffer? What parameter validity checking must it do? (1.0 points)

    Having gotten the pointer using LOADP, use There were two special instructions, LOADP relative to the pointer to get what it points to, and use STOREP relative to the pointer to change what it points to.

  3. Background: Suppose you had hardware such as was described in problem 2) above, but you wanted to write your operating system using the approach described in problem 1) above. Step 1 is easy: Set up the user's memory address map to contain only user pages. If the address space is just 4 pages, for example, and if the user needed pages up, the user program, and ud, the user data, the user's address map would be [x,x,up,ud] where x indicates an inaccessible page. Given that pagex sp and sd contain the system code and system data, the system address map would be [sp,sd,up,ud] so the system has access to all user data but the user has no access to system data.

    A Problem: Describe how a system call would work in this context, with specific attention to how the trap handler would detect that the instruction causing a trap was a system call, how it would transfer control to the called routine, and how the called routine would return. You may need to review the nature of traps from whatever text you used to study assembly language and computer architecture. (1.0 points)

    The trap handler would operate as outlined in Problem 1 in order to determine if the call was allowed, but before returning, it would fill in the bottom pages of the memory map with the appropriate entries to make the system accessible.

    Unfortunately, it would no longer work to simulate a call and then return from trap, because we need to edit the address map again on return, taking the system pages out of the map. Therefore, we have to do things the hard way, calling the system service from within the trap handler and then fixing the address map before the return from trap that is used to return to the user code.