Homework 5 Solutions

22C:116, Spring 1999

1. Part A:

   base_plot( w, x, y, r, g, b ) {
      BASE[ x + (y * PIXPERLINE) ] = (r << 20) | (g << 10) | b
   }
   

   Note that the above code makes no provision for error checking!

   Part B: As given in the problem statement, all windows can be represented by a record with the following field:

   • plot -- points to plot routine for this window
   The representation of the base window has plotme point to base_plot, and has no other data. A generic plot routine (for non-object-oriented users) can be written as:

   plot( w, x, y, r, g, b ) {
      (* w->plot)( w, x, y, r, g, b );
   }
   

   Windows contained within the base window could have the following representation, an extension of the representation given above:
   • plot -- points to plot routine for this window
   • base -- points to the window containing this window
   • basex -- the x coordinate of this window in its parent
   • basey -- the y coordinate of this window in its parent
   • width -- the width of this window
   • height -- the height of this window
   Given this, the plot routine for subsidiary windows, pointed to by plot in the representation of such windows, could have the following form:

   sub_plot( w, x, y, r, g, b ) {
      if ((x > 0) and (y > 0) and (x < w->width) and (y < w-> height) {
          plot( base, w->basex + x, w->basey + y, r, g, b )
      }
   }
   

   This code is only a first-hack at solving the problem, its biggest shortcoming is that it does nothing to prevent a plot operation on a window from overwriting windows contained in that window.

2. Gate crossing on the Hawk machine could be done using any instruction that forces a trap. The obvious candidates are unimplemented instructions and privileged instructions. The return from trap mechanism can be used to return control to the user after a supervisor call.

   Simple parameters passed in registers will be easy to handle, but if the user runs with the memory management unit turned on, supervisor calls turn off the MMU and the return from trap mechanism turns the MMU back on. As a result, pointers passed by the user (including the user's stack pointer and program counter) will be difficult for the supervisor routine to interpret.

3. From the point of view of protection mechanisms, the right to manipulate an open file in UNIX is protected by a capability list. Specifically, the list of open files, indexed by UNIX file descriptors, is a capability list. This list is maintained by the kernel on behalf of each process and may be manipulated only by kernel calls. The entries in this list contain the access rights (read or write) allowed for that file, plus a pointer to the data structure (buffers, I-node, etc) for that file.

4. The UNIX access control model for files is not intended to be universal, but it can be pushed much farther than its developers intended. Consider an arbitrary access matrix. Owner access can be used to give one user special access to each file, but this solves few problems, in the general case. Public access can be used to grant the least privilege all users of a file require, but again, this solves few problems in the general case.

   Therefore, the group mechanism must be used to solve the general problem! Consider making one group per file, where that group lists all the users who have special (non-owner and non-public) access to that file. To open a file, the user in question must be a member of the group for that file, and the access requested must correspond to the access allowed by that file for members of that group. This this is short of being universal for two reasons:

   First, there is a system-wide constant, ngroups, limiting the number of groups to which a user may belong. Second, all users in a group share the same access rights.

   The second shortcoming can be solved only by creating multiple groups for each file. For example, for file f, instead of just fgroup, a list of users with access to f, we will need frgroup, a list of users allowed to read f, fwgroup, a list of users allowed to write f, and frwgroup, a list of users allowed to read and write f. This makes the limit set by ngroups more severe!