Description
Purpose
This project has you build a timeout -queue facility, based on the classic Unix callout table, and using the timer library that you built in Project Zero. A timeout queue is a simple and elegant way to keep track of deadlines and to create periodic jobs. Your implementation will make use of doubly-linked lists, which will be provided to you … the doubly-linked list is a technique used to keep track of things, and it is very flexible in that you can walk the list in either direction, and deleting an item from the list only requires a pointer to the item to delete (as opposed to a singly- linked list, which requires a pointer to the item as well as a pointer to the preceding item in the list) . As will be the case in most of the semester’s projects, this is programmed in C and does not interact with the ARM peripherals, so you can first build and test it on your laptop, before trying to run it on the Raspberry Pi board.
On Timers and Access to System Registers
There is a very powerful facility in the latest instantiations of the ARM instruction set. The following comes from toe document ARMv8 Instruction Set Overview:
What this means is that, for all of the I/O registers that are part of the core (as opposed to those that are defined at the SoC level), you need not know the addresses where they live; you need only know their names. So, for example, here is a write-up of some of the system registers available in ARMv8 cores (64-bit cores), taken from the document ARM® Architecture Reference Manual—ARMv8, for ARMv8-A architecture profile:
ENEE 447: Operating Systems — Project 2Let’s focus for the moment just on the timer registers, in particular, CNTPCT_EL0. Here is the documentation write-up for that register (from the same doc):
How can you use this? The document itself tells you under the heading “Accessing the CNTPCT_EL0” toward the end of the section. For example, let’s say you type the following assembly code into a text file called time.s:
.globl get_time
get_time:
mrs x0, cntpct_el0
ret
This will give you the get_time() function, which reads the 64-bit time counter into the register x0 and returns it (in ARMv8, function return values are passed through the x0 register).
ENEE 447: Operating Systems — Project 2
If you really don’t want to mess with assembly code, you can type the following in a C-language file:
unsigned long get_time(){
register unsigned long t;
// read the current counter
asm volatile (“mrs %0, cntpct_el0” : “=r”(t));
return t;
}
We can argue about which of the two is easier. The main point is that these two representations are equivalent — they end up producing exactly the same binary executable code. With a 64- bit architecture, there is no need to use separate 32-bit reads to access the timer, and there is no need to check to make sure the top 32 bits are the same before and after reading the bottom 32 bits, and there is no need for a special time_diff() function—to tell the difference between two times, just subtract the earlier from the later (perhaps checking for negative values as a possible error scenario).
Build a Timeout Queue
You should implement the following functions for handling a timeout queue facility. They have the following definitions and behaviors:
int bring_timeoutq_current( void );
This function calculates the time difference between now and when the timeout queue was last updated, and it subtracts that difference from the head of the list. It returns the amount of time to wait, which can be the value of the next-to-fire event, or perhaps some MAX_WAIT value if you choose that the kernel should never go to sleep for too long.
void create_timeoutq_event( int start, int repeat, pfv_t function, namenum_t data );
This function takes a pointer to a function (which returns void, i.e., a pfv_t) as well as a piece of generic 8-byte data (in general, this could be more sophisticated, like a pointer to a dynamically allocated data structure), and it inserts the function into the timeout queue with the specified timeout. This is done by taking an event structure off the free list, initializing its values, and inserting it into the timeout queue with the appropriate timing. The function is intended to run at time start microseconds from now. The function assumes that the calling function has already brought the timeout queue’s internal notion of time to be current [through the function bring_timeoutq_current()…] If the repeat value is non- zero, then when the event is handled (by the function handle_timeoutq_event()), it will be re-inserted into the timeout queue instead of being put back onto the free list.
int handle_timeoutq_event( void );
This function looks at the front of the timeout queue and, if the timeout has expired, or is about to expire within the next microsecond or so, then the event’s function is executed, and the corresponding data value is passed to it. If this happens, then the corresponding event structure is removed from the list. It is either placed back onto the free list, or it is re-inserted into the timeout queue, depending on the value of the event’s repeat variable, which was initialized in the create_timeoutq_event() function. The function returns a Boolean value representing whether or not an event was handled. The outer loop will use this to decide whether or not to keep checking the queue for expired events. We will return control to the outer loop in this example (as opposed to having the
ENEE 447: Operating Systems — Project 2
handle_timeoutq_event() function walk the list, handling every single event that has reached its timeout, and only stopping once it reaches the end of the list or an event with a still-positive timeout value), because we want to handle not only timed events but asynchronous events, and we do not want to have to write reentrant list-handling code.
Your functions should work together in the following code (this is taken from kernel.c):
init_timeoutq(); // given to you
-
create some timeout events namenum_t data;
data.num = 3;
bring_timeoutq_current();
create_timeoutq_event( 2 * ONE_SEC, 4 * ONE_SEC, do_hex, data );
data.num = 10;
bring_timeoutq_current();
create_timeoutq_event( 3 * ONE_SEC, 4 * ONE_SEC, do_blink, data );
data.num = 0xabcde0123456789;
bring_timeoutq_current();
create_timeoutq_event( 4 * ONE_SEC, 4 * ONE_SEC, do_hex, data );
data.name[0] = ‘H’;
data.name[1] = ‘e’;
data.name[2] = ‘l’;
data.name[3] = ‘l’;
data.name[4] = ‘o’;
data.name[5] = ‘.’;
data.name[6] = 0;
data.name[7] = 0;
bring_timeoutq_current();
create_timeoutq_event( 5 * ONE_SEC, 4 * ONE_SEC, do_string, data); while (1) {
if (handle_timeoutq_event()) {
continue;
}
timeout = bring_timeoutq_current();
wait(timeout);
}
As with a number of the projects to come, the timeout queue is programmed in C and does not interact with the ARM peripherals directly, so you can first build and test the facility on your laptop, before trying to run it on the Raspberry Pi board. If you do so, you will have to “fake” the time-related facilities such as wait() and get_time() … but it will allow you to debug your code.
Optional Extra Credit
When you look at the code, you may notice that the blink_led() function has been renamed to
ENEE 447: Operating Systems — Project 2
blink_led_stall() to indicate that it performs its operation by stalling between turning the LED on and off. Through this implementation, which is simple but effective, it also effectively blocks the CPU from doing anything useful in the mean time until it’s done blinking the LED—which is important because it means that it also blocks the kernel from doing anything useful in the mean time until it’s done. Therefore there are two versions of the do_blink() function called in the code above. The first version looks like one would expect:
void do_blink( namenum_t data ) {
blink_led_stall(data.num);
}
The second version is quite a bit more involved:
void do_blink( namenum_t data ) {
int i;
namenum_t foo;
foo.num = 0;
bring_timeoutq_current();
for (i=0; i<(data.num*2); i++) {
if (i & 0x1) {
create_timeoutq_event( 50 * i * ONE_MSEC, 0, led_off, foo );
} else {
create_timeoutq_event( 50 * i * ONE_MSEC, 0, led_on, foo );
}
}
}
The two versions of the code are enabled/disabled by setting the #if statement in the code to either 0 or 1.
Among other things, the second example shows why the function create_timeoutq_event() does not need to bring the time current itself—if it is desired to create a string of events, all relative to now(), then you should only update the time once at the beginning. If instead you bring the timeout queue current each time, you are effectively compacting time for those events.
What this second version accomplishes is a way to do a string of events that will not block the kernel from doing other things. By using the timeout queue instead of just spin-waiting, the kernel is free to interleave various things together to achieve a globally consistent timing of events. For example, what do you think would happen if the do_blink() function were given an input value of more than 10? Note that it works by blinking on and off every 10th of a second.
Getting your timeout queue implementation working with the first version is a bit easier than getting it to work with the second version, which is running things at 0.05sec (50ms) time granularities instead of time granularities of 1 second. Also, the blinking should be regular, and the on/off time periods should be the same—if not, it will be noticeable. And, lastly, using the timeout queue implementation would allow you to have blinking times in excess of one second, without weirdness happening.
So, the Extra Credit Part?
To get extra credit, run your code with the more complex version of do_blink(), which turns the LED on and off through your timeout queue, and set the number of blinks in the kernel to be 20 instead of 10 (replace data.num = 10; with data.num = 20; in the kernel.c code above). If you successfully make this attempt, you’ll get an additional 25% for this project.
ENEE 447: Operating Systems — Project 2
Build It, Load It, Run It
