Operating System代写：CPSC415 Device Driver

代写操作系统作业，练习设备驱动(Device Driver)的三层交互方式，通过事件(Event)的方式驱动应用程序。

Motivation

The purpose of this assignment is to develop an understanding of the how the three layers of the device driver interact and how the kernel can signal events to an application. In this assignment you will extend the kernel from the second assignment to implement signal handling and a keyboard device. In doing this you will learn how a device driver is constructed and how the kernel can asynchronously signal events to an application.

Also, since this is the last assignment not as much guidance is provided on what to do and which files need to modified. By this point you should be able to determine that on your own.

To Start

Your starting point is the kernel resulting from the second assignment. If you did not complete the assignment, or don’t wish to use your kernel, you may use someone else’s kernel or the partial solution kernel available through Stash. (You could also start with an assignment 1 solution to avoid time slicing problems, but in the end it needs to run on the assignment 2 kernel.) You will modify the code in several modules and add additional modules to extend the kernel. Note: If you use the supplied solution, as with the A1 solution, the kfree() function is not fully implemented and does not actually free memory. Consequently, don’t get too exuberant with kmalloc() and expect kfree() to help you out. Additionally none of the IPC primitives from assignment 2 are supplied nor is priority scheduling since none of that functionality is needed for this assignment.

If you are going to use your own kernel you need to clone the repo that is created when you register for this assignment and then replace all the .h and .c files from your A2.

Note: The solution kernel, using the supplied makefile, compiles without any compiler warnings except for routines in the libx directory. Your code, regardless of the kernel you start with, must also compile without warnings except for files in the libx directory. You are not allowed to change the command line options to the compiler to achieve this.

Assignment 3 - GIT Usage

NOTE: You are expected to regularly check-in the work you have done throughout the assignment. To encourage this part of the grade for this assignment will be based on a regular and reasonable check-ins of your code. If working in pairs it is expected that both partners will contribute to the assignment and check-in code. It is accepted that the checking in of code may not be 50/50, but if only one person is checking in code then questions might be raised about who is doing the work.

A new function

int sysgetcputimes(processStatuses *)

This system call is provided for you in the sample code. Each element in the structure corresponds to a process in the system. For each process the pid, current process state and the number of milliseconds (yes milliseconds and not ticks) that have been charged to the process are recorded. Process 0 is always reported and it is the NULL/idle process. The code in user.c shows how to call it and how to print the information out. Note when you print the information out you should print column headings and a meaningful state name as opposed to just a number.

The function fills the table starting with table element 0. The value returned, if it is positive is the last slot used. -1 is returned if the address is in the hole, and -2 is returned if the structure being pointed to goes beyond the end of main memory. If you are using your own kernel you will need to either implement this functionality from scratch or move the provided code into your code base and make the appropriate adjustments.

Signal

The task for this part of the assignment is to implement a mechanism that allows the kernel to asynchronously signal an application. The signalling system will support 32 signals, numbered 0 to 31. Signal 31 is a special signal that has as its handler sysstop(). In addition signal 31 cannot be overridden or ignored. Signals are to be delivered in priority order, with signals of a higher number having a higher priority being delivered first and they also are allowed to interrupt the execution of lower priority signal handlers. For example, if signal 23 is being handled by a process, that signal’s processing can be interrupted by signals numbered 24 to 31 while signals 0 to 23 would be held in abeyance until the handling of signal 23 finished.

In order to keep things simple, the only way a signal can be posted (signalled) is via the syskill() call which is being repurposed from assignment 2.

Signal system calls

To syscall.c add the following system calls:

int syssighandler(int signal, void (*newhandler)(void *), void (** oldHandler)(void *))

This call registers the provided function as the handler for the indicated signal. If signal is invalid then 1 is returned. Since signal 31 cannot have its handler changed an attempt to change the handler for signal 31 will also return 1. If it can be determined that the handler resides at an invalid address then -2 is returned. If the handler is successfully installed a 0 is returned. The function being registered as the handler takes a single argument. The third argument, oldHandler, is a pointer to a variable that points to a handler. When this call successfully installs a new handler it copies the address of the old handler to the location pointed to by oldHandler. By doing this it is possible for the application code to remember a previously installed handler in case it needs/wants to restore that handler. If he address pointed to be oldHandler is an invalid address (e.g. the hole, past the end of main memory etc.) then 3 is to be returned.

When the handler is called, the trampoline code will set up things so that the handler’s parameter will point to the start of the context at the time the kernel decides to deliver a signal to the process. (Note this means actually delivering the signal, not marking it for delivery.) Essentially, this is a pointer to the start of the context that would have been activated if a signal was not being delivered. If a null pointer is passed in as the handler then signal delivery for the identified signal is disabled, which means the signal is ignored. The default action for all signals is to ignore the signal.

void syssigreturn(void *old sp)

This call is to be used only by the signal trampoline code. It takes as an argument the location, in the application stack, of the context frame to switch this process to. This is just the value that was passed to the trampoline code. (A discussion of the trampoline code occurs in the next section.) On the kernel side, the action performed by this call is to replace the stack pointer in this process’s PCB with the pointer passed as the parameter to this system call. In addition this call needs to retrieve any saved return value and indicate what signals can again be delivered. This call does not return.

int syskill(int PID, int signalNumber)

This system call requests that a signal be delivered to a process. The PID argument is the process ID of the process to deliver the signal to. The signalNumber is the number of the signal to be delivered (i.e. 0 to 31). On success this call returns 0, if the target process does not exist then -514 is returned and if the signal number is invalid -583 is returned. From syskill()’s perspective if a signal is marked for delivery, or if the signal to be delivered and is marked “to be ignored,” that is considered success.

int syswait(int PID)

This system call causes the calling process to wait for the process with the ID PID to terminate. If the call terminates normally it returns 0. If the process to be waited for does not exist then -1 is returned. (Process 0 is considered to not exist for the purposes of this call.) If a signal is targeted at the process while it is waiting the signal is delivered and handler run, if the signal isn’t being ignored, and the call returns the value that indicates a system call was interrupted (see below).

Signal processing Code

In the file signal.c implements the function

sigtramp(void (*handler)(void *), void *cntx)

When the kernel decides to deliver a signal to a process, the kernel modifies the application’s stack so that sigtramp() is executed when this process is switched to. The sigtramp() code runs in user space as part of the application and is used to control the signal processing in the application. It is the responsibility of sigtramp() to call the provided handler with the argument cntx When the handler returns, sigtramp() then calls syssigreturn() with cntx to complete the signal processing. The syssigreturn() call never returns.

int signal(...)

This function, implemented in signal.c, is internal to the kernel, and is called when a signal is to be registered for delivery to a process. It is your responsibility to decided what appropriate arguments should be and the meaning of the return values. Regardless of what you decide, it must be possible for a process to signal itself.

If a process is blocked on a system call when it is targeted to receive a signal, then the target process is unblocked and the return value for the system call, which is being unblocked, is -666, unless otherwise specified and means that the system call was interrupted by a signal. The unblocked process does not return from this “interrupted” system call until after the signal processing finishes. Consequently you will need to remember the value that needs to be returned for the system call as any context switches from the trampoline/handler to the kernel could result in register eax being improperly set upon return.

If, before a process gets a chance to process a specific signal, the same signal is signalled (posted) again the signal handler for that signal is run only once. However, if that same signal is posted while the signal handler (or trampoline code) for it is being run, that same signal handler will be run, depending on the priority of any other signals that might have occurred, once the current handler is complete.

Interrupting syssleep()

In assignment 2 the description of syssleep() says that the value returned is 0 if the timer expires or the time left to sleep if the call is interrupted. Since the call can’t be interrupted in assignment 2 it always returned 0 so there was no question as to whether the time retured should be in ticks or milliseconds. For this assignment the units of the return value are to be milliseconds, just like the parameter.

Signal handling implementation suggestions

To deal with the signal prioritization issue you might want to maintain several sets of bit masks. The first could be bit mask that records all of the signals currently targeted to the process. The second could be a mask with 1s in the locations of all the bits of the signals we are willing to accept (i.e. a handler is installed for that signal). You will probably also want to keep some indication of the range of signals the process will respond to taking priorities into account. For example if the only signals with a priority greater than 10 are to be processes then that needs to be remembered and adjusted as signal handlers are run.

As part of delivering a signal the kernel will need to save the current value of the current signal processing level so that the signalling level can be raised and subsequently restored. Depending upon your implementation approach there may be other values that need to be stored and recovered later.

One problem is where to store all these old values. You might want to consider putting the old values on the application stack, just before the context for the trampoline code is added. (i.e. Put it on the stack as if sigtramp() had additional parameter. Sigtramp won’t use them, but when syssigreturn() is called the kernel can compute where these values are stored and retrieve them. (Suggestion: Consider defining a struct that can be used to setup the stack for the switch to sigtramp and then having the appropriately defined fields in it such as the new context, return address, arguments to sigtramp() and then any extra fields.)

It is strongly suggested that you focus your initial implementation on getting the signal handling code to work before permiting and excuting signal handler to be interrupted by a higher priority signal.

Device Driver

You are to implement the keyboard device using the standard design pattern discussed in class consisting of the DII and upper and lower half driver code.

System Calls

To syscall.c and disp.c add the following system calls:

extern int sysopen(int device no)

This call will be used to open a device. The argument passed in is the major device number and can be used to index, perhaps after some adjustment, into the device table. The call returns -1 if the open fails, and a file descriptor in the range 0 to 3 (inclusive) if it succeeds.

extern int sysclose(int fd)

This call takes as an argument, the file descriptor (fd) from a previously successful open call, and closes that descriptor. Subsequent system calls that make use of the file descriptor return a failure. The call returns 0 for success and -1 for a failure.

extern int syswrite(int fd, void *buff, int bufflen)

This call performs a write operation to the device associated with the provided file descriptor, fd. Up to bufflen bytes are written from buff. The call returns -1 if there is an error, otherwise it returns the number of bytes written. Depending upon the device, the number of bytes written may be less than bufflen.

extern int sysread(int fd, void *buff, int bufflen)

This call reads up to bufflen bytes from the previously opened device associated with fd into the buffer area pointed to by buff. The call returns -1 if there is an error, otherwise it returns the number of bytes read. Depending upon the device, the number of bytes read may be less than bufflen. A 0 is returned to indicate end-of-file (EOF). If a sysread() call is interrupted by a signal that isn’t being ignored, the signal handler is run and then sysread() returns and the return value is number of bytes in its buffer. If that value would be 0 then the value indicating an interrupted system call is returned.

extern int sysioctl(int fd, unsigned long command, ...)

This call takes a file descriptor and executes the specified control command. The action taken is device specific and depends upon the control command. Additional parameters are device specific. The call returns -1 if there is an error and 0 otherwise.

Device Independent Calls

Each application level system call requires a corresponding call to be invoked by the dispatcher. The calls that you will need to implement are: di_open(), di_close(), di_write(), di_read() and di_ioctl(). The parameters to these calls are just the parameters of the corresponding system call along with any additional parameters, if any, required by your design. The return values of these calls and their meaning are dependent upon your design. (Recall that the return values are only used by the dispatcher and do not have to represent the value that the system call returns to the application.) These calls are to be implemented in the file called di_calls.c

Except for the di_open() call, the remaining calls all follow the same implementation pattern. Roughly each DII call does the following:

• Verifies that the passed in file descriptor is in the valid range and corresponds to an opened device.
• Using the information stored in the file descriptor table of the process determines the index of the appropriate device in the device table from the there determines the function to call.
• Calls the function.
• You will need to determine the meaning of the return value of the DII call.

We discussed in class the types of things that di_open() needs to perform. However, we don’t have a file system to perform the name to major device number mapping. To get around this problem have the di_open() call take the actual major device number as the argument to identify the device being opened. The di_open() call will need to verify that the major number is in the valid range before calling the device specific open() function pointed to by the device block and adding the entry to the file descriptor table in the PCB.

PCB Changes

You will need to add a file descriptor table to your PCB. The file descriptor table must allow 4 devices to be opened at once. Each entry in the file descriptor table must somehow (this is up to you) identify the device associated with the descriptor.

Device Table and Device Structure

The kernel’s device table will not be very interesting in that it will have only 2 devices in it. Both entries are for the keyboard. The device 0 version of the keyboard will not, by default, echo the characters. as they arrive. This means that if the characters need to be displayed the application will have to do it. Device 1 will, by default, echo the characters. This means that the character could be displayed before the application has actually read the character. Even though these are separate devices, only one of them is allowed to be open at a time.

Each table entry has a device structure similar to that described in class. (i.e. It need not be exactly as described in class.) The structure proposed in class serves only as a guide. Keep in mind that the structure you choose must be capable of supporting a wide range of both physical and virtual devices. Also note that the keyboard devices have basically the same functionality except for one routine so do not duplicate code.

The required tables and structures are to be defined in xeroskernel.h and initialized in init.c

Keyboard

For each of the device independent calls you will need to implement a corresponding device specific device driver call. The implementation is to be in the files named kbd.c and kbd.h.

Since writes are not supported to the keyboard, all calls to syswrite() will result in an error indication (-1) being returned.

The behaviour of the sysread() system call is somewhat simpler and less flexible than might be found on a typical Unix system.

If the echo version of the keyboard is opened, then each typed character is echoed to the screen as soon as it arrives. If the non-echo version of the keyboard is being used the responsibility for printing characters, if required, is the application’s.

The keyboard implementation is to internally buffer up to 4 characters. If a control-d is typed the underlying driver will take that to mean that no more input follows and return, at the appropriate time, an end-of-file (EOF) indication. (i.e. a 0 on a sysread() call.) The control-d is never returned to the application nor are any characters typed after a control-d. In fact it makes sense to disable the keyboard hardware at this point. Subsequent sysread() operations on this descriptor will continue to return the EOF indication. If the buffer fills up subsequent character arrivals are discarded and not displayed until buffer space becomes available. If a control-d is received while the buffer is full it is discarded like any other character.

When a sysread call is made it blocks until one or more of the following conditions occurs while copying data from the kernel to the application buffer passed as the parameter to sysread():

• The buffer passed in to the sysread system call is full as specified by the size parameter to the read call. Any unread bytes in the kernel buffer are returned on subsequent sysreads.
• While copying bytes to the application buffer the “Enter key” (i.e. the carriage return character) is encountered. in this case the ASCII character for a new line (“\n”) is put into the buffer and the call returns. The “\n” character is included in the count of the number of characters returned. Characters after the “Enter Key” are returned in subsequent read operations. Note that “\n” takes up two characters when entered as code, it actually is a single character since the \ is acting as an escape character and provides a way to represent a non-printable character.
• An EOF was detected by the kernel and all unread data has been copied.
• A signal is targeted at the process and the signal is not being ignored. In this case the process is unblocked and the handler run. Once the handler has completed execution the sysread call returns the number of characters that, up to this point have been placed in the buffer supplied by the application. If that value is zero then the value defined earlier that indicates an interrupted system call is returned.

Observe that when filling the application’s read buffer, characters are always consumed first from the kernel’s read buffer followed by new characters from the keyboard if there are insufficient characters in the kernel’s buffer. When sysread operations succeed the bytes returned in the buffer must correspond to the legal ASCII characters as defined by man ASCII on the undergraduate Linux machines.

The sysioctl() command supported by the keyboard device has three operations. O is to change the character typed at the keyboard that indicates an EOF. The command number to request this operation is 53, (see http://www.random.org for how this number was selected.) and the third parameter is the integer value of the character that is to become the new EOF indicator. The other two commands are 55 and 56. Command 55 turns echoing off, and command 56 turns echoing on. There are no other parameters for command 55 and 56.

Interacting with the keyboard hardware

The chip that communicates with the keyboard is the Intel 8042 and it occupies ports 0x60 to 0x6F, although we won’t use all the ports. Port 0x60 is where data is read from. Commands and control information are read/written to port 0x64. To see if there is data present read a byte from port 0x64. If the low order bit is 1 then there is data ready to be read from port 0x60. Do not assume that because an interrupt went off that there is actually data to read. Most of the time there will be, but there are things known as spurious interrupts that occur when there is in fact no data. Links to documents to help you understand the 8042 and how to program it are available in this assignment’s area on Canvas. The keyboard is the 2nd device connected to the PIC/APIC. Since devices are numbered starting with 0, the IRQ for the keyboard controller is 1. Consequently, interrupts for the keyboard controller are enabled with the following call: enable irq(1, 0). To avoid unneeded processing, the kernel should enable the keyboard interrupts through the APIC only upon an open and disable them again on a close. You will need to read the code to determine how to disable the keyboard. I’d suggest starting with enable irq(). Also, don’t forget to install your ISR.

When a character is read from the 8042 you actually get back a scan code representing which key was pressed or released. (You get an event when the key is pressed and another event when the key is released.) This means that you will need to convert the scan codes to ASCII and you will also need to keep track of whether the control and shift keys are still being held when subsequent scan codes arrive. Note: keys outside the standard part of the keyboard (e.g. the function keys, keypad, arrow keys etc, can be ignored. The escape key is considered a standard key.) Before getting too involved in this code, you should experiment a bit by having the keyboard interrupt routine simply print the byte read from port 0x60. This will allow you to determine just what happens when a key is pressed/released and how the control and shift keys fit into this. Some code to convert scan codes to ASCII has been put in the file scancodesToAscii.txt in the C directory. You may find this code, which doesn’t have a lot of comments, to be of some help. Feel free to use the code and modify it for your own purposes. If you choose to use this code, and make changes to it, be sure to clearly identify and document the changes you make.

A test Program

To demonstrate your new kernel you will write the program that controls access to the console, a simple shell, and a couple of test programs.

The init program

The root process is going to provide the functionality similar to the init program on Unix. The program does the following:

1. Prints a banner that says Welcome to Xeros - a not so experimental OS
2. Opens the keyboard.
3. Prints Username:
4. Reads the username - the only username you need to support is cs415 5. Turns keyboard echoing off
5. Prints Password:
6. Reads the password
7. Closes the keyboard
8. Verifies the username and password
9. If the verification fails goes back to step 1 (The password is to be EveryonegetsanA)
10. Create the shell program.
11. Wait for the shell program to exit
12. Go back to step 1

The shell

Roughly the shell behaves as follows after opening the keyboard.

1. Print the prompt
2. Reads the command - each command ends when the enter key is pressed.
3. The first word on the line is the command.
4. If the command does not exist print “Command not found” and go to step 1
5. If the command exists then create the process corresponding to that command and remember the process ID until the process exits.
6. If the command line ended with “&” go back to 1.
7. Otherwise wait for the command to finish with syswait().

Determining if a program has exited if the shell hasn’t done a syswait() is a bit problematic and will be dealt with in the commands section.

The commands

Commands designated as builtin are run by the shell directly and if the command line ends with & the & is ignored. The commands you are to support are:

• ps - builtin - lists all the current living/active processes one per line. Each line consists of 3 nicely spaced columns. The columns, which are to have headings, are the process id, the current state of the process, and the amount of time the process has run in milliseconds. Note that the state of the process running the ps command is to be reported as RUNNING. You will probably need to introduce some additional states to represent things like processes blocked for I/O or waiting for another process as these states are different from each other and from sleeping.
• ex or current EOF character - builtin - causes the shell to exit
• the current EOF character - builtin - causes the shell to exit. If a line is is terminated with the current EOF character as opposed to the enter key, then the the command line is not interpreted and the shell exits.
• k - builtin - Takes a parameter, the pid of the process to terminate, and kills that process. If the process does not exist it prints “No such process” (Note you will have to implement syskill() as it isn’t supplied.)
• a - partially builtin, This commands takes a parameter that is the number of milliseconds before signal 18 is to be sent. The shell first installs a hander that prints ALARM ALARM ALARM and then disables signal 18 once the alarm has been delivered. If the command line ends with “&”. The shell will run the alarm() process in the background otherwise it waits for the alarm process to terminate. The alarm process will sleep for the required number of ticks and then send the signal 18 to the shell. To get the time and shell pid you can “cheat” and use global variables, but if you want more of a challenge you can figure out how to pass these values as parameters to the process (No marks will be deducted if you don’t do this.)
• t - this starts the t() process which simply prints, on a new line a T every 10 seconds or so. You might have to experiment a bit to get the right sleep value.

Feel free to add new commands to help with testing. Since the tests can be command line driven leave them in so that we can try them.

Hints to Successfully Completing the Assignment

Here are some hints on how to successfully complete this assignment.

1. Implement the parts you understand first. Do not assume that the best way to implement this assignment is to start at the beginning of the assignment and working your way through.
2. To develop some expertise in interacting with the 8042 just try reading from it and printing something out before writing other parts of the code.
3. Write small bits of code and test it right away. Do not write the whole assignment and then try to get it working.

Testing

You are to produce a plain ASCII testing document, called testdoc.txt, organized into sections. Each section will cover one of the testing scenario described below, have a title, and be clearly delineated with an obvious separator from adjacent sections. The sections are to appear in the order as listed below. For each test case explain what is being tested, how the test is structured, and how the output demonstrates what is being tested. You may want to annotate the output but be very careful to distinguish between annotations and actual output. It is acceptable to remove output that is superfluous as long as that is indicated. The tests must be unique and different from any of the scenarios required to implement the shell and its commands.

1. Test showing prioritization and signals interrupting each other.
2. syssighandler() test case
3. syskill() test case
4. syssigwait() test case
5. sysopen() with invalid arguments
6. syswrite() with invalid file descriptor
7. sysioctl() test for invalid commands
8. sysread() when there are more characters buffered in kernel than the read requests 9. Two test cases for scenarios not covered here or in the test program.

How the TA’s will Test Your Code

To test your code, the TA’s will compile and run your code as is, and verify that the test program works. Secondly they may provide their own user land code to test the signal handling and devices.

How to hand in things

As in the previous assignments to hand in you need to commit your changes and push the commits to stash.

1. Make sure your c, h, and compile directories from the xeros distribution are committed. Do not add any .a or .o files to the repo.
2. Make sure you have pushed all your final code to the stash server.
3. If you have anything you want the TA to know about your assignment put in a file named README.txt in the c directory.
4. Make sure your testing documentation is included.