CMSC 412 Project #6

ACL and Message Passing

Due Tuesday, May 11th, 2004 (9:00 AM)

  • Updated (05/18)Grading Criteria
  • Submission Instructions
  • Slides used in recitation
  • New project files


  • Updated (05/03) syscall.c.add
  • elf.c - replace current version
  • syscallnos.h.add
  • gosfs.h.add, gosfs.c.add
  • fileio.h.add - add to respective files in the project directory
  • vfs.h.add, vfs.c.add - add to respective files in the project directory
  • syscall.h.add - add to respective files in the project directory


  • Updated (05/05)ls.c
  • setacl.c, wc.c, cat.c, - add to userProgs directory; add corresponding .exe files to the PROGS variable in the Makefile in userProgs directory
  • libuser.h.add, libuser.c.add - add to respective files in userProgs directory


    The purpose of this project is to add the notion of users and access control lists to the Geek OS kernel.  You will also add input and output redirection as well as add interprocess communication via message buffers.

    Message Passing

    Message passing allows processes to communicate by sending messages.   In this project, those messages will be sent via message queues.  You can think of the message queues as mailboxes.   A send to a mailbox will insert the message to the queue of messages corresponding to that mailbox. A receive reads from the queue and returns it to the receiver.  The queues will be FIFO so a send should append message to the end of a queue.  Correspondingly, a receive should read from the front of a queue. Messages have arbitrary sizes: the sender uses Write() for sending and the receiver uses Read() for receiving; so the receiver has no idea how many bytes has the sender actually written; the FIFO mechanism will assure bytes are read in exactly the order they were received. The kernel must allocate space to hold the message and copy it from the process sending the message.   On a receive, the kernel will read from the queue and copy the message into the buffer passed by the receiver.   If the message is longer that the buffer size of the receiver, part of the message (up to the buffer size) is given to the receiver, while the rest is left in the message queue.   

    All message queues will have a fixed size of 4KB.  An attempt to write to a full message queue should block the process and an attempt to read from an empty message queue will block the process (as you might have noticed, this is the UNIX semantics for pipes).  The operations of message queues are defined for the case of one process reading from a message queue and a second process writing to it.  You do not need to handle the case of more than one process reading from (or writing to) the same message queue.

    The key new system call to allow message passing is: int MessageQueueCreate.This call will create a message queue to be used to send messages. If this is the first call to MessageQueueCreate with the given name, it creates a new entry in the MQ array. You need to support at least 20 mailboxes whose names may be up to 25 characters long. If all mailboxes are currently used (i.e., all mailboxes have at least one user), -1 should be returned.

    If there is already a mailbox with this given name, then find an unused file descriptor from the process’s file descriptor table (declared in user context) and assign the mailbox to this file descriptor. Return the file descriptor number as the result of this system call. 

    In order to make it easier for processes to use the message queue, you will extend the functionality of the VSF. You will use the read, write, and close system calls from project #5 to implement sending data to and from message queues and closing a message queue. To implement this functionality, you will need to modify vfs.c to create a new "filesystem" (FS_TYPE_IPC) that represents the message-passing interface.  The read,write, and close calls in vsf.c will forward the calls to your message queue functions (similarly to the way in which it forwarded GOSFS calls to functions in gosfs.c in project 5).

    Input/Output Redirection

    You will also modify your spawn code to allow input and output redirection. To do this, you will need to modify the Spawn_Program system call to take two additional parameters (stdin and stdout).  The resulting call will look like Spawn_Program(char *program, int stdin, int stdout) These extra parameters should be the file descriptors that an application process will read from or write to. These file descriptors must be valid open file descriptors in the parent process that is spawning the child process. Every process will have two pre-defined file descriptors (0 and 1) that will refer to the standard input and standard output of that process (as passed by the spawn system call). There will also be another file system defined called FS_TYPE_CONSOLE. This is the screen and keyboard.  The initial process (started in main.c) should have its file descriptors 0 and 1 set to read and write (respectively) from this special file system type.  You should modify the vfs.c code to handle read and write to the console device (basically clone the code from Print_String and GetKey). 

    Finally, you should modify the Print_String system call to be simply a call the write system call to the stdout (1) file descriptor.  This will allow the output of one process to be either redirected to a file (if the open file descriptor passed to the spawn system call is a file) or piped into another process (if the open file descriptor passed into the process is a message queue). You may want to define Debug_Print_String to be the old Print_String system calls to allow debugging output while you debug this call.

    You can use the files located in testing to test the additional spawn functionality.

    Users and I/O Protection

    This project will also introduce the idea of user's and I/O protection to the OS.  Adding the system calls SetAcl, SetSetUid, and SetEffectiveUid will do this.  The key idea to adding users is simply to have a field in the user context data structure that identifies the current user that is running this process. The user will be represented by an integer called the uid.  There is a special user (uid 0) that is the super user. The super user (and only the super user) may change the user id of a running process via the SetEffectiveUid system call.  If the uid of a process is 0 (superuser) when this system call is made, the uid is changed to the passed uid. The GetUid call returns the current uid of the process. When the shell starts, it runs with uid 0, i.e. super-user privileges. When a process is spawned, it normally will inherit the uid of the parent process.  There may be instances where a process may need more rights than its parent (think of the passwd command in unix). In order to allow this, there is a special bit, setUid stored in the GOSFSFileNode. If this bit is enabled (set to 1) for the executable, the process should inherit the uid of executable file rather than the parent process. The function SetSetUid is used to set this bit for a file.

    The uid is also used by the file system to check if a particular user is able to perform a particular operation on a given file.  A process running with the uid of the superuser can open any file regardless of the ACLs. If the uid is any other value, the I/O operation will only succeed if the uid has appropriate privilege based on the ACL of the file (or directory).  For the Open system call, if the file exists the current uid must have the requested access level (i.e. Read privilege if the file is being opened with read access).  If the file does not exist, then the user must have write access to the parent directory. The read, write, seek, stat, and close system calls do not require checking the ACL since the check is made on the Open call. The createDirectory call requires write access to the parent directory. The delete and setAcl calls require write access to the named file.

    The SetAcl system call sets the file permissions for the passed uid on the named file.  If the permissions are 0, this should delete any access that uid had to the passed file.  If the request is for a new uid to have some privilege for a file , and the ACL table for that file is full, you should return -1 as an error code.  This code should also be used for invalid permissions or for non-existent files.

    New System Calls

    The following system calls will need to be added to your operating system.

    Call User Function Return on success Return on failure Reasons for failure Comment
    SYS_SET_ACL SetAcl(char *name, int uid, int permissions) 0 -1
  • name does not exist
  • illlegal value for uid (it must be greater than 0)
  • illegal value for permissions
  • the ACL table for name is full
  • The permissions values are flags and may be OR'ed together in a call. For example:
    • O_READ
    • O_WRITE
    • 0 (zero)
  • SYS_SET_SET_UID SetSetUid(char *name, int setUid) 0 -1
  • name does not exist
  • illegal value for setUid (it can only be 0 or 1)
  • This call will set the setUid bit in the GOSFSFileNode structure for the file corresponding to name
  • SYS_SET_EFFECTIVE_UID SetEffectiveUid(int uid) 0 -1
  • current Uid is not superuser
  • Set the user id for the current process
    SYS_GET_UID GetUid() uid of the current process -1   Return the user id of the current process
    SYS_MQ_CREATE MessageQueueCreate(char *name) new file descriptor number -1
  • there is no available file descriptor index for the process
  • all mailboxes are currently in use
  • This call should create a new message queue if it does not exist. Otherwise, it should open it in the current process.



    The message queue implementation for interprocess communication can be done using a using a circular queue.


    Below are several files you can use for testing. They require the modified Spawn call to compile.
  • shell.c
  • pipe.c