From 4f670845ff9ab6c48bcb5f7bf4d4ef6dc3c3064b Mon Sep 17 00:00:00 2001 From: manuel Date: Tue, 27 Mar 2012 11:51:08 +0200 Subject: reorganize file structure to match the upstream requirements --- devices/timer.c | 297 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 297 insertions(+) create mode 100644 devices/timer.c (limited to 'devices/timer.c') diff --git a/devices/timer.c b/devices/timer.c new file mode 100644 index 0000000..3533fe7 --- /dev/null +++ b/devices/timer.c @@ -0,0 +1,297 @@ +#include "devices/timer.h" +#include +#include +#include +#include +#include "devices/pit.h" +#include "threads/interrupt.h" +#include "threads/synch.h" +#include "threads/thread.h" + +/* See [8254] for hardware details of the 8254 timer chip. */ + +#if TIMER_FREQ < 19 +#error 8254 timer requires TIMER_FREQ >= 19 +#endif +#if TIMER_FREQ > 1000 +#error TIMER_FREQ <= 1000 recommended +#endif + +/* Number of timer ticks since OS booted. */ +static int64_t ticks; + +/* Number of loops per timer tick. + Initialized by timer_calibrate(). */ +static unsigned loops_per_tick; + +static intr_handler_func timer_interrupt; +static bool too_many_loops (unsigned loops); +static void busy_wait (int64_t loops); +static void real_time_sleep (int64_t num, int32_t denom); +static void real_time_delay (int64_t num, int32_t denom); + +/* list of processes waiting for an wakeup event + * and currently put to sleep */ +static struct list wakeup_list; + +/* Sets up the timer to interrupt TIMER_FREQ times per second, + and registers the corresponding interrupt. */ +void +timer_init (void) +{ + list_init (&wakeup_list); + pit_configure_channel (0, 2, TIMER_FREQ); + intr_register_ext (0x20, timer_interrupt, "8254 Timer"); +} + +/* Calibrates loops_per_tick, used to implement brief delays. */ +void +timer_calibrate (void) +{ + unsigned high_bit, test_bit; + + ASSERT (intr_get_level () == INTR_ON); + printf ("Calibrating timer... "); + + /* Approximate loops_per_tick as the largest power-of-two + still less than one timer tick. */ + loops_per_tick = 1u << 10; + while (!too_many_loops (loops_per_tick << 1)) + { + loops_per_tick <<= 1; + ASSERT (loops_per_tick != 0); + } + + /* Refine the next 8 bits of loops_per_tick. */ + high_bit = loops_per_tick; + for (test_bit = high_bit >> 1; test_bit != high_bit >> 10; test_bit >>= 1) + if (!too_many_loops (high_bit | test_bit)) + loops_per_tick |= test_bit; + + printf ("%'"PRIu64" loops/s.\n", (uint64_t) loops_per_tick * TIMER_FREQ); +} + +/* Returns the number of timer ticks since the OS booted. */ +int64_t +timer_ticks (void) +{ + enum intr_level old_level = intr_disable (); + int64_t t = ticks; + intr_set_level (old_level); + return t; +} + +/* Returns the number of timer ticks elapsed since THEN, which + should be a value once returned by timer_ticks(). */ +int64_t +timer_elapsed (int64_t then) +{ + return timer_ticks () - then; +} + +/* Comparison function for our ascending ordered wakeup list. */ +static bool +wakeup_list_cmp_less(const struct list_elem *a, const struct list_elem *b, + void *AUX UNUSED) +{ + struct thread *t1 = list_entry (a, struct thread, elem); + struct thread *t2 = list_entry (b, struct thread, elem); + return (t1->wakeup_tick < t2->wakeup_tick); +} + +/* Sleeps for approximately TICKS timer ticks. Interrupts must + be turned on. */ +void +timer_sleep (int64_t ticks) +{ + struct thread *t = thread_current (); + enum intr_level old_level; + + ASSERT (intr_get_level () == INTR_ON); + + /* nothing to sleep here */ + if (ticks <= 0) + return; + + t->wakeup_tick = timer_ticks () + ticks; + + /* add thread to sorted wakeup list + * disable interrupts as this is critical */ + old_level = intr_disable (); + ASSERT (t->status == THREAD_RUNNING); + list_insert_ordered (&wakeup_list, &t->elem, &wakeup_list_cmp_less, NULL); + + /* block the thread */ + thread_block (); + + /* restore interrupt */ + intr_set_level (old_level); +} + +/* Sleeps for approximately MS milliseconds. Interrupts must be + turned on. */ +void +timer_msleep (int64_t ms) +{ + real_time_sleep (ms, 1000); +} + +/* Sleeps for approximately US microseconds. Interrupts must be + turned on. */ +void +timer_usleep (int64_t us) +{ + real_time_sleep (us, 1000 * 1000); +} + +/* Sleeps for approximately NS nanoseconds. Interrupts must be + turned on. */ +void +timer_nsleep (int64_t ns) +{ + real_time_sleep (ns, 1000 * 1000 * 1000); +} + +/* Busy-waits for approximately MS milliseconds. Interrupts need + not be turned on. + + Busy waiting wastes CPU cycles, and busy waiting with + interrupts off for the interval between timer ticks or longer + will cause timer ticks to be lost. Thus, use timer_msleep() + instead if interrupts are enabled. */ +void +timer_mdelay (int64_t ms) +{ + real_time_delay (ms, 1000); +} + +/* Sleeps for approximately US microseconds. Interrupts need not + be turned on. + + Busy waiting wastes CPU cycles, and busy waiting with + interrupts off for the interval between timer ticks or longer + will cause timer ticks to be lost. Thus, use timer_usleep() + instead if interrupts are enabled. */ +void +timer_udelay (int64_t us) +{ + real_time_delay (us, 1000 * 1000); +} + +/* Sleeps execution for approximately NS nanoseconds. Interrupts + need not be turned on. + + Busy waiting wastes CPU cycles, and busy waiting with + interrupts off for the interval between timer ticks or longer + will cause timer ticks to be lost. Thus, use timer_nsleep() + instead if interrupts are enabled.*/ +void +timer_ndelay (int64_t ns) +{ + real_time_delay (ns, 1000 * 1000 * 1000); +} + +/* Prints timer statistics. */ +void +timer_print_stats (void) +{ + printf ("Timer: %"PRId64" ticks\n", timer_ticks ()); +} + +/* Timer interrupt handler. */ +static void +timer_interrupt (struct intr_frame *args UNUSED) +{ + struct list_elem *el, *next; + + ticks++; + thread_tick (); + + /* Check threads waiting to get woken up/unblocked. + * Since this is an ordered list we can bail out as soon + * as the first element doesn't need to get unblocked. */ + for (el = list_begin (&wakeup_list); el != list_end (&wakeup_list); el = next) + { + struct thread *t = list_entry (el, struct thread, elem); + if (t->wakeup_tick == timer_ticks ()) + { + next = list_remove (el); + /* unblock must be called AFTER removing, + * as thread_unblock() will reuse t.elem */ + thread_unblock (t); + continue; + } + break; + } +} + +/* Returns true if LOOPS iterations waits for more than one timer + tick, otherwise false. */ +static bool +too_many_loops (unsigned loops) +{ + /* Wait for a timer tick. */ + int64_t start = ticks; + while (ticks == start) + barrier (); + + /* Run LOOPS loops. */ + start = ticks; + busy_wait (loops); + + /* If the tick count changed, we iterated too long. */ + barrier (); + return start != ticks; +} + +/* Iterates through a simple loop LOOPS times, for implementing + brief delays. + + Marked NO_INLINE because code alignment can significantly + affect timings, so that if this function was inlined + differently in different places the results would be difficult + to predict. */ +static void NO_INLINE +busy_wait (int64_t loops) +{ + while (loops-- > 0) + barrier (); +} + +/* Sleep for approximately NUM/DENOM seconds. */ +static void +real_time_sleep (int64_t num, int32_t denom) +{ + /* Convert NUM/DENOM seconds into timer ticks, rounding down. + + (NUM / DENOM) s + ---------------------- = NUM * TIMER_FREQ / DENOM ticks. + 1 s / TIMER_FREQ ticks + */ + int64_t ticks = num * TIMER_FREQ / denom; + + ASSERT (intr_get_level () == INTR_ON); + if (ticks > 0) + { + /* We're waiting for at least one full timer tick. Use + timer_sleep() because it will yield the CPU to other + processes. */ + timer_sleep (ticks); + } + else + { + /* Otherwise, use a busy-wait loop for more accurate + sub-tick timing. */ + real_time_delay (num, denom); + } +} + +/* Busy-wait for approximately NUM/DENOM seconds. */ +static void +real_time_delay (int64_t num, int32_t denom) +{ + /* Scale the numerator and denominator down by 1000 to avoid + the possibility of overflow. */ + ASSERT (denom % 1000 == 0); + busy_wait (loops_per_tick * num / 1000 * TIMER_FREQ / (denom / 1000)); +} -- cgit v1.2.3