SUBMISSION DUE: Friday, November 11th 2016 by 11:59 PM

By the end of this lab, students will be able to:

• Understand how to design and implement low-level device drivers
• Understand how to design and build an interface for users to meaningfully use the underlying device

For this lab, you will need to read certain sections in the Intel Quark SoC datasheet. The document can be downloaded here

One of the most important tasks of an Operating System is to provide users a way to interact with the devices connected to a computer. Today's PCs and mobile computing devices have a wide variety of devices connected to them. An OS is responsible to “talk” with the devices on a user's behalf. A piece of code that directly communicates with a device is called a device driver; each device connected to a computer has a separate device driver. Device drivers hide the complexity of the underlying hardware and provide an interface to interact with the device. An OS typically builds on top the interface provided by the device driver and exposes a system-wide standard interface to the users. For example, in Unix, the interface is provided through the file system - each device connected to the computer is given a name in the file system (e.g., /dev/console may refer to the console device). To initiate use of the device, an application opens the named entry and receives a file descriptor. The application then uses read and write system calls to communicate with the device, passing the file descriptor as an argument. When communication is complete, the application calls close to terminate communication.

Few applications deal directly with devices. An OS library module or an application code uses the standard device interface, but adds a layer of abstraction that makes device interaction convenient and meaningful. For example, a typical smartphone has sensors in them to know what the orientation of the device is in 3D space. The device driver, in this case, will read the orientation and return the coordinates as raw numbers. A smartphone OS display module will request the device driver to read the numbers and take the decision of rotating the screen when the device is physically rotated.

In this lab, you will design a low-level device driver to interact with a device and write a high-level interface for a user to use the device meaningfully. We will use a High Precision Event Timer (HPET) as a device and build an alarm system on top of the HPET which the users can use to set alarms to be triggered after a stipulated amount of time.

In /homes/cs503/xinu there is a file called xinu-fall2016-lab6.tar.gz that contains a start to the code. Unpack:

tar zxvf /u/u3/cs503/xinu/xinu-fall2016-lab6.tar.gz

This will create a directory called xinu-fall2016-lab6.

Xinu provides a standard interface to interact with the devices connected to the computer. Xinu defines all the devices in a table called the device switch table. This table contains an entry for each device that can be used in Xinu. Each entry in the table contains the following:

• Device Number (it's index in the device table)
• Device Name
• Control and Status registers address
• Function pointers for the following device functions:
  • init
  • open
  • close
  • read
  • write
  • seek
  • getc
  • putc
  • control

A device may not use all the above mentioned functions in which case the device table entry contains a stub function (ioerr or ionull, depending on whether the particular function should simply return OK or SYSERR).

The standard device interface in Xinu uses system calls to interact with devices using the device switch table. Let us take an example of the read system call.

read system call prototype in Xinu is defined as:
devcall  read (
           did32    descrp, /* This is the index in device table */
           char     *buffer,/* User provided buffer address      */
           uint32   count   /* No. of bytes to read from device  */
           );

...and performs the following:
1. Checks if the device number is valid
2. Uses the device index to go into the device table and then calls the device specific read function.

You will find a similar definition of other device related system calls like open, close, write, getc, etc.

We saw earlier how Xinu stores device information in device table and how system calls use the table to call device specific functions. The key data structure in all of this is the device table. The device table is populated at compile time using the config program in the config/ sub-directory in the Xinu code. All devices that you want to compile into Xinu, are defined in the file called Configuration. This file is divided into two sections:

• Device type definitions: This section defines device types by providing the device specific functions
• Device declarations: This sections declares the actual devices that will be part of the device table. Each declaration provides a name, a type, and some more information. An entry is then added to the device switch table for this device.

In this lab, you will design and implement a device driver for the High Precision Event Timer (HPET) in Xinu. HPET is a device that can be used to measure time at a very high precision. The HPET in the galileo boards consists of three timers. Timer0 in Xinu is used for a periodic interrupt (clock tick) which generates an interrupt every millisecond. Timer1 and Timer2 are currently not used. For this lab, you will be using Timer1 only. (Note: be careful not to change Timer0 or system functions such as sleep that depend on the clock will not work correctly.)

Here, we will only concentrate on the non-periodic mode of the HPET. An HPET consists of a main counter (64-bit) which keeps running forever once the device is enabled. The frequency at which it increments is fixed as per the specific platform. In case of galileo boards, the main counter increments its value by 1 every 69.841279 ns (nanoseconds). This main counter is common to all the three counters in the HPET. When the main counter value reaches the maximum value, it wraps around and starts counting from zero.

Timer1 consists of a configuration register and a comparator value. After every tick, the main counter value is matched against the comparator value. If they are equal, then an interrupt is generated (if interrupts for the timer are enabled). So, if you want the Timer1 to generate an interrupt 10 ms from now, you will have to do the following:

 1. Read the main counter value; let this be mcv
 2. Set the comparator value to mcv + ((ticks_for_1ms)*10)
 3. Enable interrupt for Timer1

ticks_for_1ms is main counter ticks required for passage of 1 ms. Remember that 1 tick in the main counter happens every 69.841279 ns, so, how many ticks until it is 1ms?

In this lab, you will have to program the HPET to generate interrupts. How do you go about programming a device? On most of the modern computer architectures, software interacts with hardware devices by using memory-mapped registers. This is achieved by reserving a portion of the memory address space for devices (i.e. the RAM is not mapped in that portion). Let us take an example:

   * Let's assume, a 4K block starting from address 0xfab00000 is reserved for a device 'D'
   * Now, the CPU wants to read a 4-byte integer at address 0xfab00040 (a load instruction)
   * This memory read operation is directed to the device 'D' (since it is mapped at that address)
   * The device 'D' gets the request, and returns the data from the corresponding device register
   * The data returned by the device is then loaded in the CPU register

In the 4K block assigned to the device, the device decides how to map the addresses on specific device registers.

HPET on the galileo boards is a memory-mapped device which is mapped starting at address 0xFED00000. The register map for the HPET device is provided in the Intel Quark SoC Datasheet which you can download from here. Section 21.9 gives information on the HPET device and section 21.9.3 gives the register map for the HPET device. This register map is already defined in the file include/hpet.h in Xinu.

For memory-mapped devices, the device driver accesses device registers like it accesses normal memory (RAM). Thus, a device driver controls a device by reading and writing data from/to memory-mapped device registers. How to control the device by manipulating the device registers is typically provided in a document (datasheet, technical reference manual, etc.) by the manufacturer of the device. In the Intel Quark SoC datasheet, you will find description of how to control the HPET device by manipulating the HPET memory-mapped registers.

For the curious bunch, the same Quark datasheet contains details about the Ethernet device. You can go through the datasheet and then check out the ethernet driver code in Xinu to see how Xinu controls the Ethernet device.

In the Xinu code for this lab, to program the HPET device you will use the following files:

device/hpet/hpetinit.c - This file contains the HPET Timer1 initialization code. This code is partially complete. You will need to do the following:

• Initialize the data structure that you have defined as part of your implementation
• Set the interrupt function for this timer using the function set_evec. Look at the device/tty/ttyinit.c or device/eth/ethinit.c file to see how set_evec is used.

device/hpet/hpetcontrol.c - This is the main function used to interact with the HPET Timer1 device. In Xinu, a device control function is used to control the functionality of a device. For example, if there are multiple modes in which a device can be used, you can use the device control function to choose a specific mode. A device control function works in the following way:

devcall  hpetcontrol (
                struct dentry *devptr,
                int32  func,
                int32  arg1,
                int32  arg2
                );

The argument func decides what control action must be performed on the device. For this lab, the HPET device must support the following control functions:

• HPET_CTRL_INTR_SET - This function takes the amount of milliseconds in the argument arg1 and programs the Timer1 to generate an interrupt after the stipulated amount of time. The argument arg2 is ignored. You will perform the following steps:
  • Read the value of the Main Counter (mcv_l register)
  • Compute the counter value at which interrupt must occur (mcv_l + (ticks_for_1ms * arg1))
  • Set the computed counter value in the Timer1 Comparator Value register (t1cv register)
  • Enable interrupts for Timer1 (by setting IE bit in t1cc_l register)

• HPET_CTRL_INTR_DEL - This function disables the interrupt for Timer1 (by clearing IE bit in t1cc_l). The arguments arg1 and arg2 are ignored.

• HPET_CTRL_HOOK_SET - This function accepts a function pointer of the type (void (*)(void)) in the argument arg1. When an interrupt happens, this hook function is called in the interrupt handler. You will need to store this function pointer somewhere in order to call the function from the interrupt handler. If there is a hook already registered and this control function is called with a new hook, the old hook MUST BE REPLACED by the new hook.

• HPET_CTRL_TTI - TTI stands for Time to Interrupt. This function returns (through the provided pointer) the number of milliseconds until next interrupt (or -1 if interrupt is not enabled). This function is already implemented and you DO NOT need to implement it.
  • arg1 takes a pointer to location where time_to_interrupt must be stored
  • arg2 is ignored

device/hpet/hpetdispatch.S - This is the low-level interrupt dispatch function used for the HPET device. This code is already complete, DO NOT modify it.

device/hpet/hpethandler.c - This is the high-level interrupt handler for the HPET device. You will have to perform the following in this function:

• Acknowledge the Timer1 interrupt (by writing 1 in the Timer1 bit of the General Interrupt Status (gis) register)
• Disable the HPET Timer1 interrupt (by clearing the IE bit in the t1cc_l register)
• If a hook was registered with the device using the control function HPET_CTRL_HOOK_SET, call the registered function

config/Configuration - In this file, you will see that a type is already defined called hpet but all the device functions specified are ioerr. It is your task to modify the init, control and intr entries of the type with the appropritate hpet device functions. In addition to that, in the device declaration section you will see a device named HPET is already declared. You DO NOT need to modify this declaration.

Imagine a scenario where a process in Xinu wants to perform a certain action after a stipulated amount of time. A solution to this is to use the sleepms/sleep system calls to delay for that time and then perform the action. But what if the process does not want to stop execution in the delay period? This is where an alarm system comes in picture. An alarm system in Xinu allows a process to register a callback function to the OS to be called after a stipulated amount of time. As a part of this lab, you will design and implement such an alarm system which uses the HPET device to trigger interrupts after specified amount of time.

To build the alarm system in Xinu, you will complete the following functions:

void alarm_init(void)
   -in file system/alarm_init.c

This function should do the following:

• Initialize the data structures used in your implementation
• Register a hook function - alarm_trigger (described below) with the HPET device using the device control function - control(HPET, HPET_CTRL_HOOK_SET, …)

As part of the system initialization, this function is already called from the startup process. You do not need to explicitly call this function anywhere else.

int32  alarm_register (
               int32 delay,
               void (*callbackfn)(int32),
               int32 cbarg
               )
  -in file system/alarm_register.c

This function takes as arguments, the amount of time in milliseconds, a callback function and an argument to the callback function. An example usage of this function:

void callbackfn(int32 arg) {
    kprintf("Callback with argument %d\n", arg);
}

int  main (void) {

    int32  ret;
    ret = alarm_register(3000, callbackfn, 4);
    ....
}

In the example above, the callback function will be called with the argument 4 after 3000ms.

• If the alarm registration is unsuccessful, alarm_register must return SYSERR
• If you are NOT going to implement extra credit:
  • On a successful alarm registration, please return OK
• If you ARE going to implement extra credit:
  • On a successful alarm registration, return a non-negative value which will uniquely identify this alarm registration. The return value will then be used to cancel the alarm registration (extra credit)

void  alarm_trigger (void)
  -in file system/alarm_trigger.c

This function should be registered as a hook function to the HPET device as part of the alarm system initialization (alarm_init). Upon registering this function with HPET device, whenever an HPET Timer1 interrupt occurs, this function will be called. This function will then trigger alarms whose times have expired by calling the registered callback functions directly. Once an alarm is triggered it must be removed from the system.

Note that: as per requirements stated above, the callback functions are called at interrupt time. This is not typically how things happen. Also, since the callback is called at interrupt time, it MUST NOT change the state of the current process to non-eligible (PR_WAIT, PR_SLEEP, etc.). In short, do not call functions like wait, sleep, receive in the callback function. Same applies for the alarm_trigger function itself.

Ideally, one should be able to register as many alarms as needed, but as we have seen in previous labs, this is not practical. For this lab, assume that a maximum of 20 alarms can be registered at a time. This limit is defined in the file include/alarm.h as the macro NALARMS.

At this point, we must ask a few questions regarding the design - how to keep track of multiple alarms? in the HPET timer, we can only set one interrupt at a time, so which of the multiple alarms should we use to set the interrupt? In Xinu, we have seen a very useful data structure called a delta list which is used to hold sleeping processes on the sleepq. You will use a similar approach of storing the alarms on a delta list. The head item of the delta list will be used to set interrupt on the HPET device (e.g. if the head item says trigger an alarm after 1500 ms, then set an interrupt to be triggered after 1500ms). NOTE: This delta-list will be separate from the delta-list that holds sleeping processes. You will have to design your own delta-list that holds alarms instead of processes.

However, there are certain differences between sleepq and delta list in the alarm system. The key of the head item in the sleepq is decremented in the clkhandler which happens every 1 ms. This ensures that the key of the head item on the sleepq correctly represents the remaining sleep time of that process at all times. But, in case of the HPET, an interrupt does not occur every 1 ms, consequently, we cannot decrement key of the head item every 1 ms. This can generate problems; consider the following example:

   * A1, A2, A3 are registered alarms such that:
   * at time=0, delta-list looks like:  [A1, 5000]->[A2, 8000]->[A3, 6000]
   * at time=4000, we register an alarm using alarm_register(3000, ...) (alarm A4)
   * the new delta list will be: [A4, 3000]->[A1, 2000]->[A2, 8000]->[A3, 6000]

Here, we failed to consider that 4000ms have passed since the last delta list
and that the head key does not indicate the correct delay time.

The correct delta list must look like: [A1, 1000]->[A4, 2000]->[A2, 6000]->[A3, 6000]

To solve this problem, whenever we register a new alarm, before inserting the new alarm in the delta list, we must update the head item of the delta list. This can be done by using the HPET_CTRL_TTI control function of the device. This function can be used as follows:

int32 tti;
control(HPET, HPET_CTRL_TTI, (int32)&tti, 0);
//use tti to update the head of the delta list

This function returns the time in milliseconds (through the passed pointer) until the next interrupt will happen (or -1 if Timer1 interrupt is disabled). Using this function we can maintain the delta list correctly.

• While inserting in the delta list, if the head of the list changes, the interrupt time must be changed accordingly in the HPET device.
• If there are no alarms registered, HPET Timer1 interrupt must be disabled.
• Maximum number of alarms to be registered at a time is 20 (NALARMS defined in include/alarm.h). If register_alarm is called and the no. of alarms registered is already 20 then it must return SYSERR.
• Consider defining all data structures needed for the Alarm System in include/alarm.h.
• Think about the information about an alarm you will need to track (callback function pointer, callback argument, etc.).
• Provide a set of test cases to ensure your code works as required in system/main.c, including tests for extra credit if you have implemented it.
• Remove all debug output from your code before submission. Failure to do so will NOT earn you full credit even if your code passes all TA tests.
• The TAs will be replacing main.c with their own test cases after running your submitted test cases. Make sure you do not define any dependent variables in main.c. You are free to modify any other file(s) to implement the lab requirements.
  • Make sure that there are no dependent declarations in main.c.
• If your submitted code does not compile (either the exact submitted code or the code after the TA's replace any test case files), you will receive zero (0) points for code execution. If this happens, you will be allowed to resubmit for half credit only.
• Please run “make clean” prior to submission so that you don't submit object files
• NOTE: When you make xinu for this lab the make file will generate a binary file in the compile directory called xinu. This is the file you will need to download to your backend.

As extra credit for this lab you are required to implement the following function:

int32   alarm_deregister(
                   int32 alarm_id
                   )

The argument alarm_id is the alarm identification that was returned as part of alarm registration using alarm_register. As per requirements of alarm_register when you implement extra credit, the alarm_register function must return a non-negative value that uniquely identifies the registered alarm. The choice of how you implement the unique id per alarm is yours to make.

When provided a valid alarm_id, alarm_deregister will cancel an existing registered alarm. Make sure you consider ALL the cases when you implement this function some of which are mentioned below:

• The alarm to be canceled is the head of delta-list
• The alarm to be canceled is at the end of delta-list
• The alarm to be canceled is somewhere in the middle of the delta-list

Note that there MAY be more cases to consider

• If the alarm was successfully canceled, return OK
• If the alarm was not canceled successfully (including when the alarm_id was invalid), return SYSERR

Submit using the turnin command (see below) your complete source code (all of XINU) including the any files you added to complete the lab. In the system directory include a PDF file called lab6_analysis.pdf with a report discussing:

• The details behind your implementation including extra credit if attempted.
• Very briefly explain your test cases and how they ensure the correct working of HPET device and alarm system.
• Answers to the following questions:
  • Explain how you computed the value of ticks_for_1ms i.e. the HPET main counter ticks needed for passage of 1 ms.
  • Go through the HPET_CTRL_TTI control function for the HPET device that is implemented for you and explain how it correctly computes the value of “time to interrupt” in ms.

NOTE: Make sure you put your name on your report, that the file is named exactly as specified, and the file is located in the directory specified. Also, make sure your report does NOT exceed 10 pages

To turn in your lab use the following command

turnin -c cs503 -p lab6 xinu-fall2016-lab6

assuming xinu-fall2016-lab6 is the name of the directory containing your code.

If you wish to, you can verify your submission by typing the following command:

turnin -v -c cs503 -p lab6

Do not forget the -v above, as otherwise your earlier submission will be erased (it is overwritten by a blank submission).

Note that resubmitting overwrites any earlier submission and erases any record of the date/time of any such earlier submission.

We will check that the submission time stamp is before the due date; Any submission past the due date will be deducted the appropriate number of grace days. If submission is beyond your remaining number of grace days, your work will not be accepted.