Initial commit

14 files changed, 1673 insertions, 0 deletions

diff --git a/src/devices/disk.c b/src/devices/disk.c
new file mode 100644
index 0000000..14fc631
--- /dev/null
+++ b/src/devices/disk.c
@@ -0,0 +1,571 @@
+#include "devices/disk.h"
+#include <ctype.h>
+#include <debug.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include "devices/timer.h"
+#include "threads/io.h"
+#include "threads/interrupt.h"
+#include "threads/synch.h"
+
+/* The code in this file is an interface to an ATA (IDE)
+   controller.  It attempts to comply to [ATA-3]. */
+
+/* ATA command block port addresses. */
+#define reg_data(CHANNEL) ((CHANNEL)->reg_base + 0)     /* Data. */
+#define reg_error(CHANNEL) ((CHANNEL)->reg_base + 1)    /* Error. */
+#define reg_nsect(CHANNEL) ((CHANNEL)->reg_base + 2)    /* Sector Count. */
+#define reg_lbal(CHANNEL) ((CHANNEL)->reg_base + 3)     /* LBA 0:7. */
+#define reg_lbam(CHANNEL) ((CHANNEL)->reg_base + 4)     /* LBA 15:8. */
+#define reg_lbah(CHANNEL) ((CHANNEL)->reg_base + 5)     /* LBA 23:16. */
+#define reg_device(CHANNEL) ((CHANNEL)->reg_base + 6)   /* Device/LBA 27:24. */
+#define reg_status(CHANNEL) ((CHANNEL)->reg_base + 7)   /* Status (r/o). */
+#define reg_command(CHANNEL) reg_status (CHANNEL)       /* Command (w/o). */
+
+/* ATA control block port addresses.
+   (If we supported non-legacy ATA controllers this would not be
+   flexible enough, but it's fine for what we do.) */
+#define reg_ctl(CHANNEL) ((CHANNEL)->reg_base + 0x206)  /* Control (w/o). */
+#define reg_alt_status(CHANNEL) reg_ctl (CHANNEL)       /* Alt Status (r/o). */
+
+/* Alternate Status Register bits. */
+#define STA_BSY 0x80            /* Busy. */
+#define STA_DRDY 0x40           /* Device Ready. */
+#define STA_DRQ 0x08            /* Data Request. */
+
+/* Control Register bits. */
+#define CTL_SRST 0x04           /* Software Reset. */
+
+/* Device Register bits. */
+#define DEV_MBS 0xa0            /* Must be set. */
+#define DEV_LBA 0x40            /* Linear based addressing. */
+#define DEV_DEV 0x10            /* Select device: 0=master, 1=slave. */
+
+/* Commands.
+   Many more are defined but this is the small subset that we
+   use. */
+#define CMD_IDENTIFY_DEVICE 0xec        /* IDENTIFY DEVICE. */
+#define CMD_READ_SECTOR_RETRY 0x20      /* READ SECTOR with retries. */
+#define CMD_WRITE_SECTOR_RETRY 0x30     /* WRITE SECTOR with retries. */
+
+/* An ATA device. */
+struct disk 
+  {
+    char name[8];               /* Name, e.g. "hd0:1". */
+    struct channel *channel;    /* Channel disk is on. */
+    int dev_no;                 /* Device 0 or 1 for master or slave. */
+
+    bool is_ata;                /* 1=This device is an ATA disk. */
+    disk_sector_t capacity;     /* Capacity in sectors (if is_ata). */
+
+    long long read_cnt;         /* Number of sectors read. */
+    long long write_cnt;        /* Number of sectors written. */
+  };
+
+/* An ATA channel (aka controller).
+   Each channel can control up to two disks. */
+struct channel 
+  {
+    char name[8];               /* Name, e.g. "hd0". */
+    uint16_t reg_base;          /* Base I/O port. */
+    uint8_t irq;                /* Interrupt in use. */
+
+    struct lock lock;           /* Must acquire to access the controller. */
+    bool expecting_interrupt;   /* True if an interrupt is expected, false if
+                                   any interrupt would be spurious. */
+    struct semaphore completion_wait;   /* Up'd by interrupt handler. */
+
+    struct disk devices[2];     /* The devices on this channel. */
+  };
+
+/* We support the two "legacy" ATA channels found in a standard PC. */
+#define CHANNEL_CNT 2
+static struct channel channels[CHANNEL_CNT];
+
+static void reset_channel (struct channel *);
+static bool check_device_type (struct disk *);
+static void identify_ata_device (struct disk *);
+
+static void select_sector (struct disk *, disk_sector_t);
+static void issue_pio_command (struct channel *, uint8_t command);
+static void input_sector (struct channel *, void *);
+static void output_sector (struct channel *, const void *);
+
+static void wait_until_idle (const struct disk *);
+static bool wait_while_busy (const struct disk *);
+static void select_device (const struct disk *);
+static void select_device_wait (const struct disk *);
+
+static void interrupt_handler (struct intr_frame *);
+
+/* Initialize the disk subsystem and detect disks. */
+void
+disk_init (void) 
+{
+  size_t chan_no;
+
+  for (chan_no = 0; chan_no < CHANNEL_CNT; chan_no++)
+    {
+      struct channel *c = &channels[chan_no];
+      int dev_no;
+
+      /* Initialize channel. */
+      snprintf (c->name, sizeof c->name, "hd%zu", chan_no);
+      switch (chan_no) 
+        {
+        case 0:
+          c->reg_base = 0x1f0;
+          c->irq = 14 + 0x20;
+          break;
+        case 1:
+          c->reg_base = 0x170;
+          c->irq = 15 + 0x20;
+          break;
+        default:
+          NOT_REACHED ();
+        }
+      lock_init (&c->lock);
+      c->expecting_interrupt = false;
+      sema_init (&c->completion_wait, 0);
+ 
+      /* Initialize devices. */
+      for (dev_no = 0; dev_no < 2; dev_no++)
+        {
+          struct disk *d = &c->devices[dev_no];
+          snprintf (d->name, sizeof d->name, "%s:%d", c->name, dev_no);
+          d->channel = c;
+          d->dev_no = dev_no;
+
+          d->is_ata = false;
+          d->capacity = 0;
+
+          d->read_cnt = d->write_cnt = 0;
+        }
+
+      /* Register interrupt handler. */
+      intr_register_ext (c->irq, interrupt_handler, c->name);
+
+      /* Reset hardware. */
+      reset_channel (c);
+
+      /* Distinguish ATA hard disks from other devices. */
+      if (check_device_type (&c->devices[0]))
+        check_device_type (&c->devices[1]);
+
+      /* Read hard disk identity information. */
+      for (dev_no = 0; dev_no < 2; dev_no++)
+        if (c->devices[dev_no].is_ata)
+          identify_ata_device (&c->devices[dev_no]);
+    }
+}
+
+/* Prints disk statistics. */
+void
+disk_print_stats (void) 
+{
+  int chan_no;
+
+  for (chan_no = 0; chan_no < CHANNEL_CNT; chan_no++) 
+    {
+      int dev_no;
+
+      for (dev_no = 0; dev_no < 2; dev_no++) 
+        {
+          struct disk *d = disk_get (chan_no, dev_no);
+          if (d != NULL && d->is_ata) 
+            printf ("%s: %lld reads, %lld writes\n",
+                    d->name, d->read_cnt, d->write_cnt);
+        }
+    }
+}
+
+/* Returns the disk numbered DEV_NO--either 0 or 1 for master or
+   slave, respectively--within the channel numbered CHAN_NO.
+
+   Pintos uses disks this way:
+        0:0 - boot loader, command line args, and operating system kernel
+        0:1 - file system
+        1:0 - scratch
+        1:1 - swap
+*/
+struct disk *
+disk_get (int chan_no, int dev_no) 
+{
+  ASSERT (dev_no == 0 || dev_no == 1);
+
+  if (chan_no < (int) CHANNEL_CNT) 
+    {
+      struct disk *d = &channels[chan_no].devices[dev_no];
+      if (d->is_ata)
+        return d; 
+    }
+  return NULL;
+}
+
+/* Returns the size of disk D, measured in DISK_SECTOR_SIZE-byte
+   sectors. */
+disk_sector_t
+disk_size (struct disk *d) 
+{
+  ASSERT (d != NULL);
+  
+  return d->capacity;
+}
+
+/* Reads sector SEC_NO from disk D into BUFFER, which must have
+   room for DISK_SECTOR_SIZE bytes.
+   Internally synchronizes accesses to disks, so external
+   per-disk locking is unneeded. */
+void
+disk_read (struct disk *d, disk_sector_t sec_no, void *buffer) 
+{
+  struct channel *c;
+  
+  ASSERT (d != NULL);
+  ASSERT (buffer != NULL);
+
+  c = d->channel;
+  lock_acquire (&c->lock);
+  select_sector (d, sec_no);
+  issue_pio_command (c, CMD_READ_SECTOR_RETRY);
+  sema_down (&c->completion_wait);
+  if (!wait_while_busy (d))
+    PANIC ("%s: disk read failed, sector=%"PRDSNu, d->name, sec_no);
+  input_sector (c, buffer);
+  d->read_cnt++;
+  lock_release (&c->lock);
+}
+
+/* Write sector SEC_NO to disk D from BUFFER, which must contain
+   DISK_SECTOR_SIZE bytes.  Returns after the disk has
+   acknowledged receiving the data.
+   Internally synchronizes accesses to disks, so external
+   per-disk locking is unneeded. */
+void
+disk_write (struct disk *d, disk_sector_t sec_no, const void *buffer)
+{
+  struct channel *c;
+  
+  ASSERT (d != NULL);
+  ASSERT (buffer != NULL);
+
+  c = d->channel;
+  lock_acquire (&c->lock);
+  select_sector (d, sec_no);
+  issue_pio_command (c, CMD_WRITE_SECTOR_RETRY);
+  if (!wait_while_busy (d))
+    PANIC ("%s: disk write failed, sector=%"PRDSNu, d->name, sec_no);
+  output_sector (c, buffer);
+  sema_down (&c->completion_wait);
+  d->write_cnt++;
+  lock_release (&c->lock);
+}
+
+/* Disk detection and identification. */
+
+static void print_ata_string (char *string, size_t size);
+
+/* Resets an ATA channel and waits for any devices present on it
+   to finish the reset. */
+static void
+reset_channel (struct channel *c) 
+{
+  bool present[2];
+  int dev_no;
+
+  /* The ATA reset sequence depends on which devices are present,
+     so we start by detecting device presence. */
+  for (dev_no = 0; dev_no < 2; dev_no++)
+    {
+      struct disk *d = &c->devices[dev_no];
+
+      select_device (d);
+
+      outb (reg_nsect (c), 0x55);
+      outb (reg_lbal (c), 0xaa);
+
+      outb (reg_nsect (c), 0xaa);
+      outb (reg_lbal (c), 0x55);
+
+      outb (reg_nsect (c), 0x55);
+      outb (reg_lbal (c), 0xaa);
+
+      present[dev_no] = (inb (reg_nsect (c)) == 0x55
+                         && inb (reg_lbal (c)) == 0xaa);
+    }
+
+  /* Issue soft reset sequence, which selects device 0 as a side effect.
+     Also enable interrupts. */
+  outb (reg_ctl (c), 0);
+  timer_usleep (10);
+  outb (reg_ctl (c), CTL_SRST);
+  timer_usleep (10);
+  outb (reg_ctl (c), 0);
+
+  timer_msleep (150);
+
+  /* Wait for device 0 to clear BSY. */
+  if (present[0]) 
+    {
+      select_device (&c->devices[0]);
+      wait_while_busy (&c->devices[0]); 
+    }
+
+  /* Wait for device 1 to clear BSY. */
+  if (present[1])
+    {
+      int i;
+
+      select_device (&c->devices[1]);
+      for (i = 0; i < 3000; i++) 
+        {
+          if (inb (reg_nsect (c)) == 1 && inb (reg_lbal (c)) == 1)
+            break;
+          timer_msleep (10);
+        }
+      wait_while_busy (&c->devices[1]);
+    }
+}
+
+/* Checks whether device D is an ATA disk and sets D's is_ata
+   member appropriately.  If D is device 0 (master), returns true
+   if it's possible that a slave (device 1) exists on this
+   channel.  If D is device 1 (slave), the return value is not
+   meaningful. */
+static bool
+check_device_type (struct disk *d) 
+{
+  struct channel *c = d->channel;
+  uint8_t error, lbam, lbah, status;
+
+  select_device (d);
+
+  error = inb (reg_error (c));
+  lbam = inb (reg_lbam (c));
+  lbah = inb (reg_lbah (c));
+  status = inb (reg_status (c));
+
+  if ((error != 1 && (error != 0x81 || d->dev_no == 1))
+      || (status & STA_DRDY) == 0
+      || (status & STA_BSY) != 0)
+    {
+      d->is_ata = false;
+      return error != 0x81;      
+    }
+  else 
+    {
+      d->is_ata = (lbam == 0 && lbah == 0) || (lbam == 0x3c && lbah == 0xc3);
+      return true; 
+    }
+}
+
+/* Sends an IDENTIFY DEVICE command to disk D and reads the
+   response.  Initializes D's capacity member based on the result
+   and prints a message describing the disk to the console. */
+static void
+identify_ata_device (struct disk *d) 
+{
+  struct channel *c = d->channel;
+  uint16_t id[DISK_SECTOR_SIZE / 2];
+
+  ASSERT (d->is_ata);
+
+  /* Send the IDENTIFY DEVICE command, wait for an interrupt
+     indicating the device's response is ready, and read the data
+     into our buffer. */
+  select_device_wait (d);
+  issue_pio_command (c, CMD_IDENTIFY_DEVICE);
+  sema_down (&c->completion_wait);
+  if (!wait_while_busy (d))
+    {
+      d->is_ata = false;
+      return;
+    }
+  input_sector (c, id);
+
+  /* Calculate capacity. */
+  d->capacity = id[60] | ((uint32_t) id[61] << 16);
+
+  /* Print identification message. */
+  printf ("%s: detected %'"PRDSNu" sector (", d->name, d->capacity);
+  if (d->capacity > 1024 / DISK_SECTOR_SIZE * 1024 * 1024)
+    printf ("%"PRDSNu" GB",
+            d->capacity / (1024 / DISK_SECTOR_SIZE * 1024 * 1024));
+  else if (d->capacity > 1024 / DISK_SECTOR_SIZE * 1024)
+    printf ("%"PRDSNu" MB", d->capacity / (1024 / DISK_SECTOR_SIZE * 1024));
+  else if (d->capacity > 1024 / DISK_SECTOR_SIZE)
+    printf ("%"PRDSNu" kB", d->capacity / (1024 / DISK_SECTOR_SIZE));
+  else
+    printf ("%"PRDSNu" byte", d->capacity * DISK_SECTOR_SIZE);
+  printf (") disk, model \"");
+  print_ata_string ((char *) &id[27], 40);
+  printf ("\", serial \"");
+  print_ata_string ((char *) &id[10], 20);
+  printf ("\"\n");
+}
+
+/* Prints STRING, which consists of SIZE bytes in a funky format:
+   each pair of bytes is in reverse order.  Does not print
+   trailing whitespace and/or nulls. */
+static void
+print_ata_string (char *string, size_t size) 
+{
+  size_t i;
+
+  /* Find the last non-white, non-null character. */
+  for (; size > 0; size--)
+    {
+      int c = string[(size - 1) ^ 1];
+      if (c != '\0' && !isspace (c))
+        break; 
+    }
+
+  /* Print. */
+  for (i = 0; i < size; i++)
+    printf ("%c", string[i ^ 1]);
+}
+
+/* Selects device D, waiting for it to become ready, and then
+   writes SEC_NO to the disk's sector selection registers.  (We
+   use LBA mode.) */
+static void
+select_sector (struct disk *d, disk_sector_t sec_no) 
+{
+  struct channel *c = d->channel;
+
+  ASSERT (sec_no < d->capacity);
+  ASSERT (sec_no < (1UL << 28));
+  
+  select_device_wait (d);
+  outb (reg_nsect (c), 1);
+  outb (reg_lbal (c), sec_no);
+  outb (reg_lbam (c), sec_no >> 8);
+  outb (reg_lbah (c), (sec_no >> 16));
+  outb (reg_device (c),
+        DEV_MBS | DEV_LBA | (d->dev_no == 1 ? DEV_DEV : 0) | (sec_no >> 24));
+}
+
+/* Writes COMMAND to channel C and prepares for receiving a
+   completion interrupt. */
+static void
+issue_pio_command (struct channel *c, uint8_t command) 
+{
+  /* Interrupts must be enabled or our semaphore will never be
+     up'd by the completion handler. */
+  ASSERT (intr_get_level () == INTR_ON);
+
+  c->expecting_interrupt = true;
+  outb (reg_command (c), command);
+}
+
+/* Reads a sector from channel C's data register in PIO mode into
+   SECTOR, which must have room for DISK_SECTOR_SIZE bytes. */
+static void
+input_sector (struct channel *c, void *sector) 
+{
+  insw (reg_data (c), sector, DISK_SECTOR_SIZE / 2);
+}
+
+/* Writes SECTOR to channel C's data register in PIO mode.
+   SECTOR must contain DISK_SECTOR_SIZE bytes. */
+static void
+output_sector (struct channel *c, const void *sector) 
+{
+  outsw (reg_data (c), sector, DISK_SECTOR_SIZE / 2);
+}
+
+/* Low-level ATA primitives. */
+
+/* Wait up to 10 seconds for the controller to become idle, that
+   is, for the BSY and DRQ bits to clear in the status register.
+
+   As a side effect, reading the status register clears any
+   pending interrupt. */
+static void
+wait_until_idle (const struct disk *d) 
+{
+  int i;
+
+  for (i = 0; i < 1000; i++) 
+    {
+      if ((inb (reg_status (d->channel)) & (STA_BSY | STA_DRQ)) == 0)
+        return;
+      timer_usleep (10);
+    }
+
+  printf ("%s: idle timeout\n", d->name);
+}
+
+/* Wait up to 30 seconds for disk D to clear BSY,
+   and then return the status of the DRQ bit.
+   The ATA standards say that a disk may take as long as that to
+   complete its reset. */
+static bool
+wait_while_busy (const struct disk *d) 
+{
+  struct channel *c = d->channel;
+  int i;
+  
+  for (i = 0; i < 3000; i++)
+    {
+      if (i == 700)
+        printf ("%s: busy, waiting...", d->name);
+      if (!(inb (reg_alt_status (c)) & STA_BSY)) 
+        {
+          if (i >= 700)
+            printf ("ok\n");
+          return (inb (reg_alt_status (c)) & STA_DRQ) != 0;
+        }
+      timer_msleep (10);
+    }
+
+  printf ("failed\n");
+  return false;
+}
+
+/* Program D's channel so that D is now the selected disk. */
+static void
+select_device (const struct disk *d)
+{
+  struct channel *c = d->channel;
+  uint8_t dev = DEV_MBS;
+  if (d->dev_no == 1)
+    dev |= DEV_DEV;
+  outb (reg_device (c), dev);
+  inb (reg_alt_status (c));
+  timer_nsleep (400);
+}
+
+/* Select disk D in its channel, as select_device(), but wait for
+   the channel to become idle before and after. */
+static void
+select_device_wait (const struct disk *d) 
+{
+  wait_until_idle (d);
+  select_device (d);
+  wait_until_idle (d);
+}
+
+/* ATA interrupt handler. */
+static void
+interrupt_handler (struct intr_frame *f) 
+{
+  struct channel *c;
+
+  for (c = channels; c < channels + CHANNEL_CNT; c++)
+    if (f->vec_no == c->irq)
+      {
+        if (c->expecting_interrupt) 
+          {
+            inb (reg_status (c));               /* Acknowledge interrupt. */
+            sema_up (&c->completion_wait);      /* Wake up waiter. */
+          }
+        else
+          printf ("%s: unexpected interrupt\n", c->name);
+        return;
+      }
+
+  NOT_REACHED ();
+}
+
+
diff --git a/src/devices/disk.h b/src/devices/disk.h
new file mode 100644
index 0000000..3bcbb9a
--- /dev/null
+++ b/src/devices/disk.h
@@ -0,0 +1,26 @@
+#ifndef DEVICES_DISK_H
+#define DEVICES_DISK_H
+
+#include <inttypes.h>
+#include <stdint.h>
+
+/* Size of a disk sector in bytes. */
+#define DISK_SECTOR_SIZE 512
+
+/* Index of a disk sector within a disk.
+   Good enough for disks up to 2 TB. */
+typedef uint32_t disk_sector_t;
+
+/* Format specifier for printf(), e.g.:
+   printf ("sector=%"PRDSNu"\n", sector); */
+#define PRDSNu PRIu32
+
+void disk_init (void);
+void disk_print_stats (void);
+
+struct disk *disk_get (int chan_no, int dev_no);
+disk_sector_t disk_size (struct disk *);
+void disk_read (struct disk *, disk_sector_t, void *);
+void disk_write (struct disk *, disk_sector_t, const void *);
+
+#endif /* devices/disk.h */
diff --git a/src/devices/input.c b/src/devices/input.c
new file mode 100644
index 0000000..4a12160
--- /dev/null
+++ b/src/devices/input.c
@@ -0,0 +1,52 @@
+#include "devices/input.h"
+#include <debug.h>
+#include "devices/intq.h"
+#include "devices/serial.h"
+
+/* Stores keys from the keyboard and serial port. */
+static struct intq buffer;
+
+/* Initializes the input buffer. */
+void
+input_init (void) 
+{
+  intq_init (&buffer);
+}
+
+/* Adds a key to the input buffer.
+   Interrupts must be off and the buffer must not be full. */
+void
+input_putc (uint8_t key) 
+{
+  ASSERT (intr_get_level () == INTR_OFF);
+  ASSERT (!intq_full (&buffer));
+
+  intq_putc (&buffer, key);
+  serial_notify ();
+}
+
+/* Retrieves a key from the input buffer.
+   If the buffer is empty, waits for a key to be pressed. */
+uint8_t
+input_getc (void) 
+{
+  enum intr_level old_level;
+  uint8_t key;
+
+  old_level = intr_disable ();
+  key = intq_getc (&buffer);
+  serial_notify ();
+  intr_set_level (old_level);
+  
+  return key;
+}
+
+/* Returns true if the input buffer is full,
+   false otherwise.
+   Interrupts must be off. */
+bool
+input_full (void) 
+{
+  ASSERT (intr_get_level () == INTR_OFF);
+  return intq_full (&buffer);
+}
diff --git a/src/devices/input.h b/src/devices/input.h
new file mode 100644
index 0000000..a2f50e9
--- /dev/null
+++ b/src/devices/input.h
@@ -0,0 +1,12 @@
+#ifndef DEVICES_INPUT_H
+#define DEVICES_INPUT_H
+
+#include <stdbool.h>
+#include <stdint.h>
+
+void input_init (void);
+void input_putc (uint8_t);
+uint8_t input_getc (void);
+bool input_full (void);
+
+#endif /* devices/input.h */
diff --git a/src/devices/intq.c b/src/devices/intq.c
new file mode 100644
index 0000000..028dca4
--- /dev/null
+++ b/src/devices/intq.c
@@ -0,0 +1,116 @@
+#include "devices/intq.h"
+#include <debug.h>
+#include "threads/thread.h"
+
+static int next (int pos);
+static void wait (struct intq *q, struct thread **waiter);
+static void signal (struct intq *q, struct thread **waiter);
+
+/* Initializes interrupt queue Q. */
+void
+intq_init (struct intq *q) 
+{
+  lock_init (&q->lock);
+  q->not_full = q->not_empty = NULL;
+  q->head = q->tail = 0;
+}
+
+/* Returns true if Q is empty, false otherwise. */
+bool
+intq_empty (const struct intq *q) 
+{
+  ASSERT (intr_get_level () == INTR_OFF);
+  return q->head == q->tail;
+}
+
+/* Returns true if Q is full, false otherwise. */
+bool
+intq_full (const struct intq *q) 
+{
+  ASSERT (intr_get_level () == INTR_OFF);
+  return next (q->head) == q->tail;
+}
+
+/* Removes a byte from Q and returns it.
+   Q must not be empty if called from an interrupt handler.
+   Otherwise, if Q is empty, first sleeps until a byte is
+   added. */
+uint8_t
+intq_getc (struct intq *q) 
+{
+  uint8_t byte;
+  
+  ASSERT (intr_get_level () == INTR_OFF);
+  while (intq_empty (q)) 
+    {
+      ASSERT (!intr_context ());
+      lock_acquire (&q->lock);
+      wait (q, &q->not_empty);
+      lock_release (&q->lock);
+    }
+  
+  byte = q->buf[q->tail];
+  q->tail = next (q->tail);
+  signal (q, &q->not_full);
+  return byte;
+}
+
+/* Adds BYTE to the end of Q.
+   Q must not be full if called from an interrupt handler.
+   Otherwise, if Q is full, first sleeps until a byte is
+   removed. */
+void
+intq_putc (struct intq *q, uint8_t byte) 
+{
+  ASSERT (intr_get_level () == INTR_OFF);
+  while (intq_full (q))
+    {
+      ASSERT (!intr_context ());
+      lock_acquire (&q->lock);
+      wait (q, &q->not_full);
+      lock_release (&q->lock);
+    }
+
+  q->buf[q->head] = byte;
+  q->head = next (q->head);
+  signal (q, &q->not_empty);
+}
+
+/* Returns the position after POS within an intq. */
+static int
+next (int pos) 
+{
+  return (pos + 1) % INTQ_BUFSIZE;
+}
+
+/* WAITER must be the address of Q's not_empty or not_full
+   member.  Waits until the given condition is true. */
+static void
+wait (struct intq *q UNUSED, struct thread **waiter) 
+{
+  ASSERT (!intr_context ());
+  ASSERT (intr_get_level () == INTR_OFF);
+  ASSERT ((waiter == &q->not_empty && intq_empty (q))
+          || (waiter == &q->not_full && intq_full (q)));
+
+  *waiter = thread_current ();
+  thread_block ();
+}
+
+/* WAITER must be the address of Q's not_empty or not_full
+   member, and the associated condition must be true.  If a
+   thread is waiting for the condition, wakes it up and resets
+   the waiting thread. */
+static void
+signal (struct intq *q UNUSED, struct thread **waiter) 
+{
+  ASSERT (intr_get_level () == INTR_OFF);
+  ASSERT ((waiter == &q->not_empty && !intq_empty (q))
+          || (waiter == &q->not_full && !intq_full (q)));
+
+  if (*waiter != NULL) 
+    {
+      thread_unblock (*waiter);
+      *waiter = NULL;
+    }
+}
diff --git a/src/devices/intq.h b/src/devices/intq.h
new file mode 100644
index 0000000..2312b12
--- /dev/null
+++ b/src/devices/intq.h
@@ -0,0 +1,43 @@
+#ifndef DEVICES_INTQ_H
+#define DEVICES_INTQ_H
+
+#include "threads/interrupt.h"
+#include "threads/synch.h"
+
+/* An "interrupt queue", a circular buffer shared between
+   kernel threads and external interrupt handlers.
+
+   Interrupt queue functions can be called from kernel threads or
+   from external interrupt handlers.  Except for intq_init(),
+   interrupts must be off in either case.
+
+   The interrupt queue has the structure of a "monitor".  Locks
+   and condition variables from threads/synch.h cannot be used in
+   this case, as they normally would, because they can only
+   protect kernel threads from one another, not from interrupt
+   handlers. */
+
+/* Queue buffer size, in bytes. */
+#define INTQ_BUFSIZE 64
+
+/* A circular queue of bytes. */
+struct intq
+  {
+    /* Waiting threads. */
+    struct lock lock;           /* Only one thread may wait at once. */
+    struct thread *not_full;    /* Thread waiting for not-full condition. */
+    struct thread *not_empty;   /* Thread waiting for not-empty condition. */
+
+    /* Queue. */
+    uint8_t buf[INTQ_BUFSIZE];  /* Buffer. */
+    int head;                   /* New data is written here. */
+    int tail;                   /* Old data is read here. */
+  };
+
+void intq_init (struct intq *);
+bool intq_empty (const struct intq *);
+bool intq_full (const struct intq *);
+uint8_t intq_getc (struct intq *);
+void intq_putc (struct intq *, uint8_t);
+
+#endif /* devices/intq.h */
diff --git a/src/devices/kbd.c b/src/devices/kbd.c
new file mode 100644
index 0000000..4d7dfdf
--- /dev/null
+++ b/src/devices/kbd.c
@@ -0,0 +1,207 @@
+#include "devices/kbd.h"
+#include <ctype.h>
+#include <debug.h>
+#include <stdio.h>
+#include <string.h>
+#include "devices/input.h"
+#include "threads/interrupt.h"
+#include "threads/io.h"
+
+/* Keyboard data register port. */
+#define DATA_REG 0x60
+
+/* Current state of shift keys.
+   True if depressed, false otherwise. */
+static bool left_shift, right_shift;    /* Left and right Shift keys. */
+static bool left_alt, right_alt;        /* Left and right Alt keys. */
+static bool left_ctrl, right_ctrl;      /* Left and right Ctl keys. */
+
+/* Status of Caps Lock.
+   True when on, false when off. */
+static bool caps_lock;
+
+/* Number of keys pressed. */
+static int64_t key_cnt;
+
+static intr_handler_func keyboard_interrupt;
+
+/* Initializes the keyboard. */
+void
+kbd_init (void) 
+{
+  intr_register_ext (0x21, keyboard_interrupt, "8042 Keyboard");
+}
+
+/* Prints keyboard statistics. */
+void
+kbd_print_stats (void) 
+{
+  printf ("Keyboard: %lld keys pressed\n", key_cnt);
+}
+
+/* Maps a set of contiguous scancodes into characters. */
+struct keymap
+  {
+    uint8_t first_scancode;     /* First scancode. */
+    const char *chars;          /* chars[0] has scancode first_scancode,
+                                   chars[1] has scancode first_scancode + 1,
+                                   and so on to the end of the string. */
+  };
+  
+/* Keys that produce the same characters regardless of whether
+   the Shift keys are down.  Case of letters is an exception
+   that we handle elsewhere.  */
+static const struct keymap invariant_keymap[] = 
+  {
+    {0x01, "\033"},
+    {0x0e, "\b"},
+    {0x0f, "\tQWERTYUIOP"},
+    {0x1c, "\r"},
+    {0x1e, "ASDFGHJKL"},
+    {0x2c, "ZXCVBNM"},
+    {0x37, "*"},
+    {0x39, " "},
+    {0, NULL},
+  };
+
+/* Characters for keys pressed without Shift, for those keys
+   where it matters. */
+static const struct keymap unshifted_keymap[] = 
+  {
+    {0x02, "1234567890-="},
+    {0x1a, "[]"},
+    {0x27, ";'`"},
+    {0x2b, "\\"},
+    {0x33, ",./"},
+    {0, NULL},
+  };
+  
+/* Characters for keys pressed with Shift, for those keys where
+   it matters. */
+static const struct keymap shifted_keymap[] = 
+  {
+    {0x02, "!@#$%^&*()_+"},
+    {0x1a, "{}"},
+    {0x27, ":\"~"},
+    {0x2b, "|"},
+    {0x33, "<>?"},
+    {0, NULL},
+  };
+
+static bool map_key (const struct keymap[], unsigned scancode, uint8_t *);
+
+static void
+keyboard_interrupt (struct intr_frame *args UNUSED) 
+{
+  /* Status of shift keys. */
+  bool shift = left_shift || right_shift;
+  bool alt = left_alt || right_alt;
+  bool ctrl = left_ctrl || right_ctrl;
+
+  /* Keyboard scancode. */
+  unsigned code;
+
+  /* False if key pressed, true if key released. */
+  bool release;
+
+  /* Character that corresponds to `code'. */
+  uint8_t c;
+
+  /* Read scancode, including second byte if prefix code. */
+  code = inb (DATA_REG);
+  if (code == 0xe0)
+    code = (code << 8) | inb (DATA_REG);
+
+  /* Bit 0x80 distinguishes key press from key release
+     (even if there's a prefix). */
+  release = (code & 0x80) != 0;
+  code &= ~0x80u;
+
+  /* Interpret key. */
+  if (code == 0x3a) 
+    {
+      /* Caps Lock. */
+      if (!release)
+        caps_lock = !caps_lock;
+    }
+  else if (map_key (invariant_keymap, code, &c)
+           || (!shift && map_key (unshifted_keymap, code, &c))
+           || (shift && map_key (shifted_keymap, code, &c)))
+    {
+      /* Ordinary character. */
+      if (!release) 
+        {
+          /* Handle Ctrl, Shift.
+             Note that Ctrl overrides Shift. */
+          if (ctrl && c >= 0x40 && c < 0x60) 
+            {
+              /* A is 0x41, Ctrl+A is 0x01, etc. */
+              c -= 0x40; 
+            }
+          else if (shift == caps_lock)
+            c = tolower (c);
+
+          /* Handle Alt by setting the high bit.
+             This 0x80 is unrelated to the one used to
+             distinguish key press from key release. */
+          if (alt)
+            c += 0x80;
+
+          /* Append to keyboard buffer. */
+          if (!input_full ())
+            {
+              key_cnt++;
+              input_putc (c);
+            }
+        }
+    }
+  else
+    {
+      /* Maps a keycode into a shift state variable. */
+      struct shift_key 
+        {
+          unsigned scancode;
+          bool *state_var;
+        };
+
+      /* Table of shift keys. */
+      static const struct shift_key shift_keys[] = 
+        {
+          {  0x2a, &left_shift},
+          {  0x36, &right_shift},
+          {  0x38, &left_alt},
+          {0xe038, &right_alt},
+          {  0x1d, &left_ctrl},
+          {0xe01d, &right_ctrl},
+          {0,      NULL},
+        };
+  
+      const struct shift_key *key;
+
+      /* Scan the table. */
+      for (key = shift_keys; key->scancode != 0; key++) 
+        if (key->scancode == code)
+          {
+            *key->state_var = !release;
+            break;
+          }
+    }
+}
+
+/* Scans the array of keymaps K for SCANCODE.
+   If found, sets *C to the corresponding character and returns
+   true.
+   If not found, returns false and C is ignored. */
+static bool
+map_key (const struct keymap k[], unsigned scancode, uint8_t *c) 
+{
+  for (; k->first_scancode != 0; k++)
+    if (scancode >= k->first_scancode
+        && scancode < k->first_scancode + strlen (k->chars)) 
+      {
+        *c = k->chars[scancode - k->first_scancode];
+        return true; 
+      }
+
+  return false;
+}
diff --git a/src/devices/kbd.h b/src/devices/kbd.h
new file mode 100644
index 0000000..ed9c06b
--- /dev/null
+++ b/src/devices/kbd.h
@@ -0,0 +1,9 @@
+#ifndef DEVICES_KBD_H
+#define DEVICES_KBD_H
+
+#include <stdint.h>
+
+void kbd_init (void);
+void kbd_print_stats (void);
+
+#endif /* devices/kbd.h */
diff --git a/src/devices/serial.c b/src/devices/serial.c
new file mode 100644
index 0000000..f64074a
--- /dev/null
+++ b/src/devices/serial.c
@@ -0,0 +1,228 @@
+#include "devices/serial.h"
+#include <debug.h>
+#include "devices/input.h"
+#include "devices/intq.h"
+#include "devices/timer.h"
+#include "threads/io.h"
+#include "threads/interrupt.h"
+#include "threads/synch.h"
+#include "threads/thread.h"
+
+/* Register definitions for the 16550A UART used in PCs.
+   The 16550A has a lot more going on than shown here, but this
+   is all we need.
+
+   Refer to [PC16650D] for hardware information. */
+
+/* I/O port base address for the first serial port. */
+#define IO_BASE 0x3f8
+
+/* DLAB=0 registers. */
+#define RBR_REG (IO_BASE + 0)   /* Receiver Buffer Reg. (read-only). */
+#define THR_REG (IO_BASE + 0)   /* Transmitter Holding Reg. (write-only). */
+#define IER_REG (IO_BASE + 1)   /* Interrupt Enable Reg.. */
+
+/* DLAB=1 registers. */
+#define LS_REG (IO_BASE + 0)    /* Divisor Latch (LSB). */
+#define MS_REG (IO_BASE + 1)    /* Divisor Latch (MSB). */
+
+/* DLAB-insensitive registers. */
+#define IIR_REG (IO_BASE + 2)   /* Interrupt Identification Reg. (read-only) */
+#define FCR_REG (IO_BASE + 2)   /* FIFO Control Reg. (write-only). */
+#define LCR_REG (IO_BASE + 3)   /* Line Control Register. */
+#define MCR_REG (IO_BASE + 4)   /* MODEM Control Register. */
+#define LSR_REG (IO_BASE + 5)   /* Line Status Register (read-only). */
+
+/* Interrupt Enable Register bits. */
+#define IER_RECV 0x01           /* Interrupt when data received. */
+#define IER_XMIT 0x02           /* Interrupt when transmit finishes. */
+
+/* Line Control Register bits. */
+#define LCR_N81 0x03            /* No parity, 8 data bits, 1 stop bit. */
+#define LCR_DLAB 0x80           /* Divisor Latch Access Bit (DLAB). */
+
+/* MODEM Control Register. */
+#define MCR_OUT2 0x08           /* Output line 2. */
+
+/* Line Status Register. */
+#define LSR_DR 0x01             /* Data Ready: received data byte is in RBR. */
+#define LSR_THRE 0x20           /* THR Empty. */
+
+/* Transmission mode. */
+static enum { UNINIT, POLL, QUEUE } mode;
+
+/* Data to be transmitted. */
+static struct intq txq;
+
+static void set_serial (int bps);
+static void putc_poll (uint8_t);
+static void write_ier (void);
+static intr_handler_func serial_interrupt;
+
+/* Initializes the serial port device for polling mode.
+   Polling mode busy-waits for the serial port to become free
+   before writing to it.  It's slow, but until interrupts have
+   been initialized it's all we can do. */
+static void
+init_poll (void) 
+{
+  ASSERT (mode == UNINIT);
+  outb (IER_REG, 0);                    /* Turn off all interrupts. */
+  outb (FCR_REG, 0);                    /* Disable FIFO. */
+  set_serial (115200);                  /* 115.2 kbps, N-8-1. */
+  outb (MCR_REG, MCR_OUT2);             /* Required to enable interrupts. */
+  intq_init (&txq);
+  mode = POLL;
+} 
+
+/* Initializes the serial port device for queued interrupt-driven
+   I/O.  With interrupt-driven I/O we don't waste CPU time
+   waiting for the serial device to become ready. */
+void
+serial_init_queue (void) 
+{
+  enum intr_level old_level;
+
+  if (mode == UNINIT)
+    init_poll ();
+  ASSERT (mode == POLL);
+
+  intr_register_ext (0x20 + 4, serial_interrupt, "serial");
+  mode = QUEUE;
+  old_level = intr_disable ();
+  write_ier ();
+  intr_set_level (old_level);
+}
+
+/* Sends BYTE to the serial port. */
+void
+serial_putc (uint8_t byte) 
+{
+  enum intr_level old_level = intr_disable ();
+
+  if (mode != QUEUE)
+    {
+      /* If we're not set up for interrupt-driven I/O yet,
+         use dumb polling to transmit a byte. */
+      if (mode == UNINIT)
+        init_poll ();
+      putc_poll (byte); 
+    }
+  else 
+    {
+      /* Otherwise, queue a byte and update the interrupt enable
+         register. */
+      if (old_level == INTR_OFF && intq_full (&txq)) 
+        {
+          /* Interrupts are off and the transmit queue is full.
+             If we wanted to wait for the queue to empty,
+             we'd have to reenable interrupts.
+             That's impolite, so we'll send a character via
+             polling instead. */
+          putc_poll (intq_getc (&txq)); 
+        }
+
+      intq_putc (&txq, byte); 
+      write_ier ();
+    }
+  
+  intr_set_level (old_level);
+}
+
+/* Flushes anything in the serial buffer out the port in polling
+   mode. */
+void
+serial_flush (void) 
+{
+  enum intr_level old_level = intr_disable ();
+  while (!intq_empty (&txq))
+    putc_poll (intq_getc (&txq));
+  intr_set_level (old_level);
+}
+
+/* The fullness of the input buffer may have changed.  Reassess
+   whether we should block receive interrupts.
+   Called by the input buffer routines when characters are added
+   to or removed from the buffer. */
+void
+serial_notify (void) 
+{
+  ASSERT (intr_get_level () == INTR_OFF);
+  if (mode == QUEUE)
+    write_ier ();
+}
+
+/* Configures the serial port for BPS bits per second. */
+static void
+set_serial (int bps)
+{
+  int base_rate = 1843200 / 16;         /* Base rate of 16550A, in Hz. */
+  uint16_t divisor = base_rate / bps;   /* Clock rate divisor. */
+
+  ASSERT (bps >= 300 && bps <= 115200);
+
+  /* Enable DLAB. */
+  outb (LCR_REG, LCR_N81 | LCR_DLAB);
+
+  /* Set data rate. */
+  outb (LS_REG, divisor & 0xff);
+  outb (MS_REG, divisor >> 8);
+  
+  /* Reset DLAB. */
+  outb (LCR_REG, LCR_N81);
+}
+
+/* Update interrupt enable register. */
+static void
+write_ier (void) 
+{
+  uint8_t ier = 0;
+
+  ASSERT (intr_get_level () == INTR_OFF);
+
+  /* Enable transmit interrupt if we have any characters to
+     transmit. */
+  if (!intq_empty (&txq))
+    ier |= IER_XMIT;
+
+  /* Enable receive interrupt if we have room to store any
+     characters we receive. */
+  if (!input_full ())
+    ier |= IER_RECV;
+  
+  outb (IER_REG, ier);
+}
+
+/* Polls the serial port until it's ready,
+   and then transmits BYTE. */
+static void
+putc_poll (uint8_t byte) 
+{
+  ASSERT (intr_get_level () == INTR_OFF);
+
+  while ((inb (LSR_REG) & LSR_THRE) == 0)
+    continue;
+  outb (THR_REG, byte);
+}
+
+/* Serial interrupt handler. */
+static void
+serial_interrupt (struct intr_frame *f UNUSED) 
+{
+  /* Inquire about interrupt in UART.  Without this, we can
+     occasionally miss an interrupt running under QEMU. */
+  inb (IIR_REG);
+
+  /* As long as we have room to receive a byte, and the hardware
+     has a byte for us, receive a byte.  */
+  while (!input_full () && (inb (LSR_REG) & LSR_DR) != 0)
+    input_putc (inb (RBR_REG));
+
+  /* As long as we have a byte to transmit, and the hardware is
+     ready to accept a byte for transmission, transmit a byte. */
+  while (!intq_empty (&txq) && (inb (LSR_REG) & LSR_THRE) != 0) 
+    outb (THR_REG, intq_getc (&txq));
+
+  /* Update interrupt enable register based on queue status. */
+  write_ier ();
+}
diff --git a/src/devices/serial.h b/src/devices/serial.h
new file mode 100644
index 0000000..6e04778
--- /dev/null
+++ b/src/devices/serial.h
@@ -0,0 +1,11 @@
+#ifndef DEVICES_SERIAL_H
+#define DEVICES_SERIAL_H
+
+#include <stdint.h>
+
+void serial_init_queue (void);
+void serial_putc (uint8_t);
+void serial_flush (void);
+void serial_notify (void);
+
+#endif /* devices/serial.h */
diff --git a/src/devices/timer.c b/src/devices/timer.c
new file mode 100644
index 0000000..a4521de
--- /dev/null
+++ b/src/devices/timer.c
@@ -0,0 +1,204 @@
+#include "devices/timer.h"
+#include <debug.h>
+#include <inttypes.h>
+#include <round.h>
+#include <stdio.h>
+#include "threads/interrupt.h"
+#include "threads/io.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);
+
+/* Sets up the 8254 Programmable Interval Timer (PIT) to
+   interrupt PIT_FREQ times per second, and registers the
+   corresponding interrupt. */
+void
+timer_init (void) 
+{
+  /* 8254 input frequency divided by TIMER_FREQ, rounded to
+     nearest. */
+  uint16_t count = (1193180 + TIMER_FREQ / 2) / TIMER_FREQ;
+
+  outb (0x43, 0x34);    /* CW: counter 0, LSB then MSB, mode 2, binary. */
+  outb (0x40, count & 0xff);
+  outb (0x40, count >> 8);
+
+  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);
+  barrier ();
+  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;
+}
+
+/* Suspends execution for approximately TICKS timer ticks. */
+void
+timer_sleep (int64_t ticks) 
+{
+  int64_t start = timer_ticks ();
+
+  ASSERT (intr_get_level () == INTR_ON);
+  while (timer_elapsed (start) < ticks) 
+    thread_yield ();
+}
+
+/* Suspends execution for approximately MS milliseconds. */
+void
+timer_msleep (int64_t ms) 
+{
+  real_time_sleep (ms, 1000);
+}
+
+/* Suspends execution for approximately US microseconds. */
+void
+timer_usleep (int64_t us) 
+{
+  real_time_sleep (us, 1000 * 1000);
+}
+
+/* Suspends execution for approximately NS nanoseconds. */
+void
+timer_nsleep (int64_t ns) 
+{
+  real_time_sleep (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)
+{
+  ticks++;
+  thread_tick ();
+}
+
+/* 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.  We 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)); 
+    }
+}
+
diff --git a/src/devices/timer.h b/src/devices/timer.h
new file mode 100644
index 0000000..45a3f72
--- /dev/null
+++ b/src/devices/timer.h
@@ -0,0 +1,23 @@
+#ifndef DEVICES_TIMER_H
+#define DEVICES_TIMER_H
+
+#include <round.h>
+#include <stdint.h>
+
+/* Number of timer interrupts per second. */
+#define TIMER_FREQ 100
+
+void timer_init (void);
+void timer_calibrate (void);
+
+int64_t timer_ticks (void);
+int64_t timer_elapsed (int64_t);
+
+void timer_sleep (int64_t ticks);
+void timer_msleep (int64_t milliseconds);
+void timer_usleep (int64_t microseconds);
+void timer_nsleep (int64_t nanoseconds);
+
+void timer_print_stats (void);
+
+#endif /* devices/timer.h */
diff --git a/src/devices/vga.c b/src/devices/vga.c
new file mode 100644
index 0000000..8255747
--- /dev/null
+++ b/src/devices/vga.c
@@ -0,0 +1,165 @@
+#include "devices/vga.h"
+#include <round.h>
+#include <stdint.h>
+#include <stddef.h>
+#include <string.h>
+#include "threads/io.h"
+#include "threads/interrupt.h"
+#include "threads/vaddr.h"
+
+/* VGA text screen support.  See [FREEVGA] for more information. */
+
+/* Number of columns and rows on the text display. */
+#define COL_CNT 80
+#define ROW_CNT 25
+
+/* Current cursor position.  (0,0) is in the upper left corner of
+   the display. */
+static size_t cx, cy;
+
+/* Attribute value for gray text on a black background. */
+#define GRAY_ON_BLACK 0x07
+
+/* Framebuffer.  See [FREEVGA] under "VGA Text Mode Operation".
+   The character at (x,y) is fb[y][x][0].
+   The attribute at (x,y) is fb[y][x][1]. */
+static uint8_t (*fb)[COL_CNT][2];
+
+static void clear_row (size_t y);
+static void cls (void);
+static void newline (void);
+static void move_cursor (void);
+static void find_cursor (size_t *x, size_t *y);
+
+/* Initializes the VGA text display. */
+static void
+init (void)
+{
+  /* Already initialized? */
+  static bool inited;
+  if (!inited)
+    {
+      fb = ptov (0xb8000);
+      find_cursor (&cx, &cy);
+      inited = true; 
+    }
+}
+
+/* Writes C to the VGA text display, interpreting control
+   characters in the conventional ways.  */
+void
+vga_putc (int c)
+{
+  /* Disable interrupts to lock out interrupt handlers
+     that might write to the console. */
+  enum intr_level old_level = intr_disable ();
+
+  init ();
+  
+  switch (c) 
+    {
+    case '\n':
+      newline ();
+      break;
+
+    case '\f':
+      cls ();
+      break;
+
+    case '\b':
+      if (cx > 0)
+        cx--;
+      break;
+      
+    case '\r':
+      cx = 0;
+      break;
+
+    case '\t':
+      cx = ROUND_UP (cx + 1, 8);
+      if (cx >= COL_CNT)
+        newline ();
+      break;
+      
+    default:
+      fb[cy][cx][0] = c;
+      fb[cy][cx][1] = GRAY_ON_BLACK;
+      if (++cx >= COL_CNT)
+        newline ();
+      break;
+    }
+
+  /* Update cursor position. */
+  move_cursor ();
+
+  intr_set_level (old_level);
+}
+
+/* Clears the screen and moves the cursor to the upper left. */
+static void
+cls (void)
+{
+  size_t y;
+
+  for (y = 0; y < ROW_CNT; y++)
+    clear_row (y);
+
+  cx = cy = 0;
+  move_cursor ();
+}
+
+/* Clears row Y to spaces. */
+static void
+clear_row (size_t y) 
+{
+  size_t x;
+
+  for (x = 0; x < COL_CNT; x++)
+    {
+      fb[y][x][0] = ' ';
+      fb[y][x][1] = GRAY_ON_BLACK;
+    }
+}
+
+/* Advances the cursor to the first column in the next line on
+   the screen.  If the cursor is already on the last line on the
+   screen, scrolls the screen upward one line. */
+static void
+newline (void)
+{
+  cx = 0;
+  cy++;
+  if (cy >= ROW_CNT)
+    {
+      cy = ROW_CNT - 1;
+      memmove (&fb[0], &fb[1], sizeof fb[0] * (ROW_CNT - 1));
+      clear_row (ROW_CNT - 1);
+    }
+}
+
+/* Moves the hardware cursor to (cx,cy). */
+static void
+move_cursor (void) 
+{
+  /* See [FREEVGA] under "Manipulating the Text-mode Cursor". */
+  uint16_t cp = cx + COL_CNT * cy;
+  outw (0x3d4, 0x0e | (cp & 0xff00));
+  outw (0x3d4, 0x0f | (cp << 8));
+}
+
+/* Reads the current hardware cursor position into (*X,*Y). */
+static void
+find_cursor (size_t *x, size_t *y) 
+{
+  /* See [FREEVGA] under "Manipulating the Text-mode Cursor". */
+  uint16_t cp;
+
+  outb (0x3d4, 0x0e);
+  cp = inb (0x3d5) << 8;
+
+  outb (0x3d4, 0x0f);
+  cp |= inb (0x3d5);
+
+  *x = cp % COL_CNT;
+  *y = cp / COL_CNT;
+}
diff --git a/src/devices/vga.h b/src/devices/vga.h
new file mode 100644
index 0000000..59690fb
--- /dev/null
+++ b/src/devices/vga.h
@@ -0,0 +1,6 @@
+#ifndef DEVICES_VGA_H
+#define DEVICES_VGA_H
+
+void vga_putc (int);
+
+#endif /* devices/vga.h */