--- /dev/null
+all::
+ @echo "Run 'make' in the threads, userprog, filesys, or vm directory."
+ @echo "This top-level make has only 'clean' targets."
+
+clean::
+ for d in threads; do $(MAKE) -C $$d $@; done
+
+distclean::
+ $(MAKE) clean
+ find . -name '*~' -exec rm '{}' \;
--- /dev/null
+SHELL = /bin/sh
+VPATH = $(TOP_SRCDIR)/threads:$(TOP_SRCDIR)/devices:$(TOP_SRCDIR)/lib
+
+-include *.d
+
+DEFINES =
+WARNINGS = -Wall -W -Wstrict-prototypes -Wmissing-prototypes
+CFLAGS = -g -O3 -MMD $(WARNINGS) $(INCLUDES) $(DEFINES)
+ASFLAGS = $(INCLUDES) $(DEFINES)
+
+# Core kernel.
+THREADS_SRC = start.S # Must be first.
+THREADS_SRC += init.c # Start-up code.
+THREADS_SRC += thread.c # Thread management core.
+THREADS_SRC += switch.S # Thread switch routine.
+THREADS_SRC += interrupt.c # Interrupt core.
+THREADS_SRC += intr-stubs.S # Interrupt stubs.
+THREADS_SRC += synch.c # Synchronization.
+THREADS_SRC += palloc.c # Page allocator.
+THREADS_SRC += malloc.c # Subpage allocator.
+
+# Device driver code.
+DEVICES_SRC = timer.c # Timer device.
+DEVICES_SRC += kbd.c # Keyboard device.
+DEVICES_SRC += vga.c # Video device.
+DEVICES_SRC += serial.c # Serial port device.
+
+# Library code.
+LIB_SRC = debug.c # Debug helpers.
+LIB_SRC += lib.c # Standard C library.
+LIB_SRC += random.c # Pseudo-random numbers.
+LIB_SRC += list.c # Doubly-linked lists.
+LIB_SRC += bitmap.c # Bitmaps.
+
+# Objects.
+OBJECTS = $(patsubst %.c,%.o,$(patsubst %.S,%.o,$(SOURCES)))
+
+all: diskimage.bin
+
+intr-stubs.S: $(TOP_SRCDIR)/threads/intr-stubs.pl
+ $< > $@.tmp && mv $@.tmp $@
+
+kernel.o: $(OBJECTS)
+ echo $(OBJECTS)
+ ld -T $(TOP_SRCDIR)/threads/kernel.lds -o $@ $^ \
+ `$(CC) -print-libgcc-file-name`
+
+kernel.bin: kernel.o
+ objcopy -O binary -R .note -R .comment -S $< $@
+
+loader.bin: loader.S kernel.bin
+ gcc -c $< -DKERNEL_LOAD_PAGES=`perl -e 'print int (((-s "kernel.bin") + 4095) / 4096);'`
+ ld -N -e start -Ttext 0x7c00 --oformat binary -o $@ loader.o
+
+diskimage.bin: loader.bin kernel.bin
+ cat loader.bin kernel.bin > diskimage.bin
+
+clean:
+ rm -f *.o *.d *.bin intr-stubs.S
+
+
--- /dev/null
+#ifndef HEADER_16550A_H
+#define HEADER_16550A_H 1
+
+#include <stdbool.h>
+#include <stdint.h>
+#include "debug.h"
+
+/* Register definitions for the 16550A UART used in PCs. This is
+ a full definition of all the registers and their bits. We
+ only use a few of them, however. */
+
+/* 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. (read-only). */
+#define IIR_REG (IO_BASE + 2) /* Interrupt Ident. 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). */
+#define MSR_REG (IO_BASE + 6) /* MODEM Status Register. */
+#define SCR_REG (IO_BASE + 7) /* Scratch Register. */
+
+/* DLAB=1 registers. */
+#define LS_REG (IO_BASE + 0) /* Divisor Latch (LSB). */
+#define MS_REG (IO_BASE + 1) /* Divisor Latch (MSB). */
+
+/* Interrupt Enable Register bits. */
+#define IER_RECV 0x01 /* Enable interrupt when data received. */
+#define IER_XMIT 0x02 /* Interrupt when transmit finishes. */
+#define IER_LSR 0x04 /* Interrupt when LSR changes. */
+#define IER_MSR 0x08 /* Interrupt when MSR changes. */
+
+/* Interrupt Identification Register bits. */
+#define IIR_PENDING 0x01 /* 0=interrupt pending. */
+#define IIR_ID(IIR) (((IIR) >> 1) & 7) /* Interrupt ID. */
+#define IIR_FIFO 0xc0 /* Set when FIFO is enabled. */
+
+/* FIFO Control Register bits. */
+#define FCR_FIFO 0x01 /* 1=Enable FIFOs. */
+#define FCR_RECV_RESET 0x02 /* 1=Reset receive FIFO. */
+#define FCR_XMIT_RESET 0x04 /* 1=Reset transmit FIFO. */
+#define FCR_DMA_MODE 0x08 /* 0=DMA mode 0, 1=DMA mode 1. */
+#define FCR_FIFO_TRIGGER 0xc0 /* Mask for FIFO trigger level. */
+
+/* Line Control Register bits. */
+enum parity_type
+ {
+ NONE, /* No parity bit. */
+ ODD, /* Odd parity. */
+ EVEN, /* Even parity. */
+ MARK, /* Parity bit set to 1. */
+ SPACE /* Parity bit set to 0. */
+ };
+
+static inline uint8_t
+make_lcr (int bits, enum parity_type parity, int stop, bool send_break,
+ bool dlab)
+{
+ uint8_t lcr = 0;
+
+ ASSERT (bits >= 5 && bits <= 8);
+ switch (bits)
+ {
+ case 5: lcr |= 0x00; break;
+ case 6: lcr |= 0x01; break;
+ case 7: lcr |= 0x02; break;
+ case 8: lcr |= 0x03; break;
+ }
+
+ switch (parity)
+ {
+ case NONE: lcr |= 0x00; break;
+ case ODD: lcr |= 0x08; break;
+ case EVEN: lcr |= 0x18; break;
+ case MARK: lcr |= 0x28; break;
+ case SPACE: lcr |= 0x38; break;
+ default: panic ("bad parity %d", (int) parity);
+ }
+
+ ASSERT (stop == 1 || stop == 2);
+ if (stop > 1)
+ lcr |= 0x04;
+
+ if (send_break)
+ lcr |= 0x40;
+ if (dlab)
+ lcr |= 0x80;
+
+ return lcr;
+}
+
+/* MODEM Control Register. */
+#define MCR_DTR 0x01 /* Data Terminal Ready. */
+#define MCR_RTS 0x02 /* Request to Send. */
+#define MCR_OUT1 0x04 /* Output line 1. */
+#define MCR_OUT2 0x08 /* Output line 2. */
+#define MCR_LOOP 0x10 /* Loopback enable. */
+
+/* Line Status Register. */
+#define LSR_DR 0x01 /* Data Ready. */
+#define LSR_OE 0x02 /* Overrun Error. */
+#define LSR_PE 0x04 /* Parity Error. */
+#define LSR_FE 0x08 /* Framing Error. */
+#define LSR_BI 0x10 /* Break Interrupt. */
+#define LSR_THRE 0x20 /* THR Empty. */
+#define LSR_TEMT 0x40 /* Transmitter Empty. */
+#define LSR_ERF 0x80 /* Error in Receiver FIFO. */
+
+/* MODEM Status Register. */
+#define MSR_DCTS 0x01 /* Delta Clear to Send. */
+#define MSR_DDSR 0x02 /* Delta Data Set Ready. */
+#define MSR_TERI 0x04 /* Trailing Edge Ring Indicator. */
+#define MSR_DDCD 0x08 /* Delta Data Carrier Detect. */
+#define MSR_CTS 0x10 /* Clear To Send. */
+#define MSR_DSR 0x20 /* Data Set Ready. */
+#define MSR_RI 0x40 /* Ring Indicator. */
+#define MSR_DCD 0x80 /* Data Carrier Detect. */
+
+#endif /* 16550a.h */
--- /dev/null
+#include "kbd.h"
+#include "debug.h"
+#include "interrupt.h"
+#include "io.h"
+#include "lib.h"
+
+static void
+irq21_keyboard (struct intr_args *args UNUSED)
+{
+ printk ("Keyboard!\n");
+ inb (0x60);
+}
+
+void
+kbd_init (void)
+{
+ intr_register (0x21, 0, IF_OFF, irq21_keyboard);
+}
--- /dev/null
+#ifndef HEADER_KBD_H
+#define HEADER_KBD_H 1
+
+void kbd_init (void);
+
+#endif /* kbd.h */
--- /dev/null
+#include "serial.h"
+#include "16550a.h"
+#include "debug.h"
+#include "io.h"
+#include "timer.h"
+
+static void
+set_serial (int bps, int bits, enum parity_type parity, int stop)
+{
+ int baud_base = 1843200 / 16; /* Base rate of 16550A. */
+ uint16_t divisor = baud_base / bps; /* Clock rate divisor. */
+
+ /* Enable DLAB. */
+ outb (LCR_REG, make_lcr (bits, parity, stop, false, true));
+
+ /* Set baud rate. */
+ outb (LS_REG, divisor & 0xff);
+ outb (MS_REG, divisor >> 8);
+
+ /* Reset DLAB. */
+ outb (LCR_REG, make_lcr (bits, parity, stop, false, false));
+}
+
+void
+serial_init (void)
+{
+ outb (IER_REG, 0); /* Turn off all interrupts. */
+ outb (FCR_REG, 0); /* Disable FIFO. */
+ set_serial (9600, 8, NONE, 1);
+ outb (MCR_REG, 0); /* Turn off output lines. */
+}
+
+void
+serial_outb (uint8_t byte)
+{
+ while ((inb (LSR_REG) & LSR_THRE) == 0)
+ continue;
+ outb (THR_REG, byte);
+}
--- /dev/null
+#ifndef HEADER_SERIAL_H
+#define HEADER_SERIAL_H 1
+
+#include <stdint.h>
+
+void serial_init (void);
+void serial_outb (uint8_t);
+
+#endif /* serial.h */
--- /dev/null
+#include "timer.h"
+#include "debug.h"
+#include "interrupt.h"
+#include "io.h"
+
+static volatile uint64_t ticks;
+
+static void
+irq20_timer (struct intr_args *args UNUSED)
+{
+ ticks++;
+ intr_yield_on_return ();
+}
+
+/* Sets up the 8254 Programmable Interrupt 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 (0x20, 0, IF_OFF, irq20_timer);
+}
+
+uint64_t
+timer_ticks (void)
+{
+ enum if_level old_level = intr_disable ();
+ uint64_t t = ticks;
+ intr_set_level (old_level);
+ return t;
+}
+
+uint64_t
+timer_elapsed (uint64_t then)
+{
+ uint64_t now = timer_ticks ();
+ return now > then ? now - then : ((uint64_t) -1 - then) + now + 1;
+}
+
+/* Suspends execution for at least DURATION ticks. */
+void
+timer_wait_until (uint64_t duration)
+{
+ /* FIXME */
+}
--- /dev/null
+#ifndef HEADER_TIMER_H
+#define HEADER_TIMER_H 1
+
+#include <stdint.h>
+
+#define TIMER_FREQ 100
+
+void timer_init (void);
+uint64_t timer_ticks (void);
+uint64_t timer_elapsed (uint64_t);
+
+void timer_wait_until (uint64_t);
+
+#endif /* timer.h */
--- /dev/null
+#include "vga.h"
+#include <stdint.h>
+#include <stddef.h>
+#include <string.h>
+#include "io.h"
+#include "mmu.h"
+
+static size_t vga_cols, vga_rows;
+static size_t vga_x, vga_y;
+static uint16_t *vga_base;
+
+void
+vga_init (void)
+{
+ vga_cols = 80;
+ vga_rows = 25;
+ vga_base = (uint16_t *) ptov (0xb8000);
+ vga_cls ();
+}
+
+void
+vga_cls (void)
+{
+ size_t i;
+ for (i = 0; i < vga_cols * vga_rows; i++)
+ vga_base[i] = 0x0700;
+ vga_x = vga_y = 0;
+}
+
+static void
+vga_newline (void)
+{
+ vga_x = 0;
+ vga_y++;
+ if (vga_y >= vga_rows)
+ {
+ vga_y = vga_rows - 1;
+ memmove (vga_base, vga_base + vga_cols,
+ vga_cols * (vga_rows - 1) * 2);
+ memset (vga_base + vga_cols * (vga_rows - 1),
+ 0, vga_cols * 2);
+ }
+}
+
+static void
+move_cursor (void)
+{
+ uint16_t cp = (vga_x + vga_cols * vga_y);
+ outw (0x3d4, 0x0e | (cp & 0xff00));
+ outw (0x3d4, 0x0f | (cp << 8));
+}
+
+void
+vga_putc (int c)
+{
+ switch (c)
+ {
+ case '\n':
+ vga_newline ();
+ break;
+
+ case '\f':
+ vga_cls ();
+ break;
+
+ case '\b':
+ if (vga_x > 0)
+ vga_x--;
+ break;
+
+ case '\r':
+ vga_x = 0;
+ break;
+
+ case '\t':
+ vga_x = (vga_x + 8) / 8 * 8;
+ if (vga_x >= vga_cols)
+ vga_newline ();
+ break;
+
+ default:
+ vga_base[vga_x + vga_y * vga_cols] = 0x0700 | c;
+ vga_x++;
+ if (vga_x >= vga_cols)
+ vga_newline ();
+ break;
+ }
+
+ move_cursor ();
+}
--- /dev/null
+#ifndef HEADER_VGA_H
+#define HEADER_VGA_H 1
+
+void vga_init (void);
+void vga_cls (void);
+void vga_putc (int);
+
+#endif /* vga.h */
--- /dev/null
+#define NDEBUG
+#include "bitmap.h"
+#include <limits.h>
+#include "debug.h"
+#include "lib.h"
+#include "malloc.h"
+
+typedef unsigned long elem_type;
+#define ELEM_BITS (sizeof (elem_type) * CHAR_BIT)
+#define ELEM_IDX(BIT_IDX) ((BIT_IDX) / ELEM_BITS)
+#define BIT_MASK(BIT_IDX) ((elem_type) 1 << ((BIT_IDX) % ELEM_BITS))
+
+struct bitmap
+ {
+ size_t bit_cnt;
+ elem_type *bits;
+ };
+
+static inline size_t
+elem_cnt (const struct bitmap *b)
+{
+ return DIV_ROUND_UP (b->bit_cnt, ELEM_BITS);
+}
+
+static inline size_t
+byte_cnt (const struct bitmap *b)
+{
+ return sizeof (elem_type) * elem_cnt (b);
+}
+
+struct bitmap *
+bitmap_create (size_t bit_cnt)
+{
+ struct bitmap *b = malloc (sizeof *b);
+ if (b == NULL)
+ return NULL;
+
+ b->bit_cnt = bit_cnt;
+ b->bits = malloc (byte_cnt (b));
+ if (b->bits == NULL && bit_cnt > 0)
+ {
+ free (b);
+ return NULL;
+ }
+ bitmap_set_all (b, false);
+ return b;
+}
+
+void
+bitmap_destroy (struct bitmap *b)
+{
+ ASSERT (b);
+
+ free (b->bits);
+ free (b);
+}
+
+size_t
+bitmap_size (const struct bitmap *b)
+{
+ return b->bit_cnt;
+}
+
+void
+bitmap_set (struct bitmap *b, size_t idx, bool value)
+{
+ ASSERT (b != NULL);
+ ASSERT (idx < b->bit_cnt);
+ if (value)
+ b->bits[ELEM_IDX (idx)] |= BIT_MASK (idx);
+ else
+ b->bits[ELEM_IDX (idx)] &= ~BIT_MASK (idx);
+}
+
+void
+bitmap_set_all (struct bitmap *b, bool value)
+{
+ size_t i;
+ size_t leftover_bits;
+
+ ASSERT (b != NULL);
+
+ for (i = 0; i < elem_cnt (b); i++)
+ b->bits[i] = value ? (elem_type) -1 : 0;
+
+ leftover_bits = b->bit_cnt % ELEM_BITS;
+ if (leftover_bits != 0)
+ b->bits[i - 1] = ((elem_type) 1 << leftover_bits) - 1;
+}
+
+void
+bitmap_mark (struct bitmap *b, size_t idx)
+{
+ bitmap_set (b, idx, true);
+}
+
+void
+bitmap_reset (struct bitmap *b, size_t idx)
+{
+ bitmap_set (b, idx, false);
+}
+
+void
+bitmap_flip (struct bitmap *b, size_t idx)
+{
+ ASSERT (b != NULL);
+ ASSERT (idx < b->bit_cnt);
+ b->bits[ELEM_IDX (idx)] ^= BIT_MASK (idx);
+}
+
+bool
+bitmap_test (const struct bitmap *b, size_t idx)
+{
+ ASSERT (b != NULL);
+ ASSERT (idx < b->bit_cnt);
+ return (b->bits[ELEM_IDX (idx)] & BIT_MASK (idx)) != 0;
+}
+
+size_t
+bitmap_scan (const struct bitmap *b, bool value)
+{
+ elem_type ignore;
+ size_t idx;
+
+ ASSERT (b != NULL);
+ ignore = value ? 0 : (elem_type) -1;
+ for (idx = 0; idx < elem_cnt (b); idx++)
+ {
+ elem_type e = b->bits[idx];
+ if (e != (elem_type) -1)
+ {
+ idx *= ELEM_BITS;
+
+ while ((e & 1) == 1)
+ {
+ e >>= 1;
+ idx++;
+ }
+
+ return idx;
+ }
+ }
+ return BITMAP_ERROR;
+}
+
+size_t
+bitmap_find_and_set (struct bitmap *b)
+{
+ size_t idx = bitmap_scan (b, false);
+ if (idx != BITMAP_ERROR)
+ bitmap_mark (b, idx);
+ return idx;
+}
+
+size_t
+bitmap_find_and_clear (struct bitmap *b)
+{
+ size_t idx = bitmap_scan (b, true);
+ if (idx != BITMAP_ERROR)
+ bitmap_reset (b, idx);
+ return idx;
+}
+
+size_t
+bitmap_set_cnt (const struct bitmap *b)
+{
+ size_t cnt;
+ size_t i;
+
+ ASSERT (b != NULL);
+ cnt = 0;
+ for (i = 0; i < elem_cnt (b); i++)
+ {
+ elem_type e = b->bits[i];
+ while (e != 0)
+ {
+ cnt++;
+ e &= e - 1;
+ }
+ }
+ return cnt;
+}
+
+bool
+bitmap_any (const struct bitmap *b)
+{
+ size_t i;
+
+ ASSERT (b != NULL);
+ for (i = 0; i < elem_cnt (b); i++)
+ if (b->bits[i])
+ return true;
+ return false;
+}
+
+bool
+bitmap_clear_cnt (const struct bitmap *b)
+{
+ return b->bit_cnt - bitmap_set_cnt (b);
+}
+
+bool
+bitmap_none (const struct bitmap *b)
+{
+ return !bitmap_any (b);
+}
+
+bool
+bitmap_all (const struct bitmap *b)
+{
+ size_t leftover_bits;
+ size_t i;
+
+ ASSERT (b != NULL);
+
+ if (b->bit_cnt == 0)
+ return true;
+
+ for (i = 0; i < elem_cnt (b) - 1; i++)
+ if (b->bits[i] != (elem_type) -1)
+ return true;
+
+ leftover_bits = b->bit_cnt % ELEM_BITS;
+ if (leftover_bits == 0)
+ return b->bits[i] == (elem_type) -1;
+ else
+ return b->bits[i] == ((elem_type) 1 << leftover_bits) - 1;
+}
--- /dev/null
+#ifndef HEADER_BITMAP_H
+#define HEADER_BITMAP_H 1
+
+#include <stdbool.h>
+#include <stddef.h>
+
+struct bitmap *bitmap_create (size_t bit_cnt);
+void bitmap_destroy (struct bitmap *);
+
+size_t bitmap_size (const struct bitmap *);
+
+void bitmap_set (struct bitmap *, size_t idx, bool);
+void bitmap_set_all (struct bitmap *, bool);
+
+void bitmap_mark (struct bitmap *, size_t idx);
+void bitmap_reset (struct bitmap *, size_t idx);
+void bitmap_flip (struct bitmap *, size_t idx);
+
+bool bitmap_test (const struct bitmap *, size_t idx);
+
+#define BITMAP_ERROR ((size_t) -1)
+size_t bitmap_scan (const struct bitmap *, bool);
+size_t bitmap_find_and_set (struct bitmap *);
+size_t bitmap_find_and_clear (struct bitmap *);
+
+size_t bitmap_set_cnt (const struct bitmap *);
+bool bitmap_clear_cnt (const struct bitmap *);
+
+bool bitmap_any (const struct bitmap *);
+bool bitmap_none (const struct bitmap *);
+bool bitmap_all (const struct bitmap *);
+
+#endif /* bitmap.h */
--- /dev/null
+#include "debug.h"
+#include <stdarg.h>
+#include "interrupt.h"
+#include "lib.h"
+
+void
+panic (const char *format, ...)
+{
+ va_list args;
+
+ intr_disable ();
+
+ va_start (args, format);
+ vprintk (format, args);
+ printk ("\n");
+ va_end (args);
+
+ for (;;);
+}
--- /dev/null
+#ifndef HEADER_DEBUG_H
+#define HEADER_DEBUG_H 1
+
+#ifndef NDEBUG
+#define ASSERT(CONDITION) \
+ if (CONDITION) { \
+ /* Nothing. */ \
+ } else { \
+ panic ("%s:%d: %s(): assertion `%s' failed.", \
+ __FILE__, __LINE__, __func__, #CONDITION); \
+ }
+#define NOT_REACHED() ASSERT (0)
+#else
+#define ASSERT(CONDITION) ((void) 0)
+#define NOT_REACHED() for (;;)
+#endif
+
+void panic (const char *, ...)
+ __attribute__ ((format (printf, 1, 2), noreturn));
+
+#if __GNUC__ > 1
+#define ATTRIBUTE(X) __attribute__ (X)
+#else
+#define ATTRIBUTE(X)
+#endif
+
+#define UNUSED ATTRIBUTE ((unused))
+#define NO_RETURN ATTRIBUTE ((noreturn))
+#define PRINTF_FORMAT(FMT, FIRST) ATTRIBUTE ((format (printf, FMT, FIRST)))
+#define SCANF_FORMAT(FMT, FIRST) ATTRIBUTE ((format (scanf, FMT, FIRST)))
+
+#endif /* debug.h */
--- /dev/null
+#include <stdint.h>
+#include <stdarg.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include "debug.h"
+#include "lib.h"
+#include "serial.h"
+#include "vga.h"
+
+void *
+memset (void *dst_, int value, size_t cnt)
+{
+ uint8_t *dst = dst_;
+
+ while (cnt-- > 0)
+ *dst++ = value;
+
+ return dst_;
+}
+
+void *
+memcpy (void *dst_, const void *src_, size_t cnt)
+{
+ uint8_t *dst = dst_;
+ const uint8_t *src = src_;
+
+ while (cnt-- > 0)
+ *dst++ = *src++;
+
+ return dst_;
+}
+
+void *
+memmove (void *dst_, const void *src_, size_t cnt)
+{
+ uint8_t *dst = dst_;
+ const uint8_t *src = src_;
+
+ if (dst < src)
+ {
+ while (cnt-- > 0)
+ *dst++ = *src++;
+ }
+ else
+ {
+ dst += cnt;
+ src += cnt;
+ while (cnt-- > 0)
+ *--dst = *--src;
+ }
+
+ return dst;
+}
+
+void *
+memchr (const void *block_, int ch_, size_t size)
+{
+ const uint8_t *block = block_;
+ uint8_t ch = ch_;
+
+ for (; size-- > 0; block++)
+ if (*block == ch)
+ return (void *) block;
+
+ return NULL;
+}
+
+size_t
+strlcpy (char *dst, const char *src, size_t size)
+{
+ size_t src_len = strlen (src);
+ if (size > 0)
+ {
+ size_t dst_len_max = size - 1;
+ size_t dst_len = src_len < dst_len_max ? src_len : dst_len_max;
+ memcpy (dst, src, dst_len);
+ dst[dst_len] = '\0';
+ }
+ return src_len;
+}
+
+size_t
+strlen (const char *string)
+{
+ const char *p;
+
+ for (p = string; *p != '\0'; p++)
+ continue;
+ return p - string;
+}
+
+char *
+strchr (const char *string, int c_)
+{
+ char c = c_;
+
+ for (;;)
+ if (*string == c)
+ return (char *) string;
+ else if (*string == '\0')
+ return NULL;
+ else string++;
+}
+
+static void
+vprintf_core (const char *format, va_list args,
+ void (*output) (char, void *), void *aux);
+
+static void
+output_console (char ch, void *aux __attribute__ ((unused)))
+{
+ vga_putc (ch);
+ serial_outb (ch);
+}
+
+void
+vprintk (const char *format, va_list args)
+{
+ vprintf_core (format, args, output_console, NULL);
+}
+
+void
+printk (const char *format, ...)
+{
+ va_list args;
+
+ va_start (args, format);
+ vprintk (format, args);
+ va_end (args);
+}
+\f
+/* printf() and friends internals. You do not need to understand
+ this code. */
+
+struct printf_conversion
+ {
+ enum
+ {
+ MINUS = 1 << 0,
+ PLUS = 1 << 1,
+ SPACE = 1 << 2,
+ POUND = 1 << 3,
+ ZERO = 1 << 4
+ }
+ flags;
+
+ int width;
+ int precision;
+
+ enum
+ {
+ CHAR = 1,
+ SHORT = 2,
+ INT = 3,
+ INTMAX = 4,
+ LONG = 5,
+ LONGLONG = 6,
+ PTRDIFFT = 7,
+ SIZET = 8
+ }
+ type;
+ };
+
+static const char *
+parse_conversion (const char *format, struct printf_conversion *c, va_list *args)
+{
+ /* Parse flag characters. */
+ c->flags = 0;
+ for (;;)
+ {
+ switch (*format++)
+ {
+ case '-':
+ c->flags |= MINUS;
+ break;
+ case '+':
+ c->flags |= PLUS;
+ break;
+ case ' ':
+ c->flags |= SPACE;
+ break;
+ case '#':
+ c->flags |= POUND;
+ break;
+ case '0':
+ c->flags |= ZERO;
+ break;
+ default:
+ format--;
+ goto not_a_flag;
+ }
+ }
+ not_a_flag:
+ if (c->flags & MINUS)
+ c->flags &= ~ZERO;
+ if (c->flags & PLUS)
+ c->flags &= ~SPACE;
+
+ /* Parse field width. */
+ c->width = 0;
+ if (*format == '*')
+ {
+ format++;
+ c->width = va_arg (*args, int);
+ }
+ else
+ {
+ for (; isdigit (*format); format++)
+ c->width = c->width * 10 + *format - '0';
+ }
+ if (c->width < 0)
+ {
+ c->width = -c->width;
+ c->flags |= MINUS;
+ }
+
+ /* Parse precision. */
+ c->precision = -1;
+ if (*format == '.')
+ {
+ format++;
+ if (*format == '*')
+ {
+ format++;
+ c->precision = va_arg (*args, int);
+ }
+ else
+ {
+ c->precision = 0;
+ for (; isdigit (*format); format++)
+ c->precision = c->precision * 10 + *format - '0';
+ }
+ if (c->precision < 0)
+ c->precision = -1;
+ }
+ if (c->precision >= 0)
+ c->flags &= ~ZERO;
+
+ /* Parse type. */
+ c->type = INT;
+ switch (*format++)
+ {
+ case 'h':
+ if (*format == 'h')
+ {
+ format++;
+ c->type = CHAR;
+ }
+ else
+ c->type = SHORT;
+ break;
+
+ case 'j':
+ c->type = INTMAX;
+ break;
+
+ case 'l':
+ if (*format == 'l')
+ {
+ format++;
+ c->type = LONGLONG;
+ }
+ else
+ c->type = LONG;
+ break;
+
+ case 'L':
+ case 'q':
+ c->type = LONGLONG;
+ break;
+
+ case 't':
+ c->type = PTRDIFFT;
+ break;
+
+ case 'z':
+ case 'Z':
+ c->type = SIZET;
+ break;
+
+ default:
+ format--;
+ break;
+ }
+
+ return format;
+}
+
+static void
+output_dup (char ch, size_t cnt, void (*output) (char, void *), void *aux)
+{
+ while (cnt-- > 0)
+ output (ch, aux);
+}
+
+static void
+printf_integer (uintmax_t value, bool negative, const char *digits,
+ struct printf_conversion *c,
+ void (*output) (char, void *), void *aux)
+
+{
+ int base = strlen (digits);
+
+ char buf[64];
+ char *const buf_end = buf + sizeof buf;
+ char *bp;
+
+ int pad;
+
+ /* Accumulate digits into buffer.
+ This algorithm produces digits in reverse order, so we count
+ backward from the end of the array. */
+ bp = buf_end;
+ while (value > 0)
+ {
+ *--bp = digits[value % base];
+ value /= base;
+ }
+
+ /* Prepend enough zeros to match precision.
+ If precision is 0, then a value of zero is rendered as a
+ null string. Otherwise at least one digit is presented. */
+ if (c->precision < 0)
+ c->precision = 1;
+ while (buf_end - bp < c->precision && bp > buf + 3)
+ *--bp = '0';
+
+ /* Prepend sign. */
+ if (c->flags & PLUS)
+ *--bp = negative ? '-' : '+';
+ else if (c->flags & SPACE)
+ *--bp = negative ? '-' : ' ';
+ else if (negative)
+ *--bp = '-';
+
+ /* Prepend base. */
+ if ((c->flags & POUND) && base != 10)
+ {
+ *--bp = digits[0xa] == 'a' ? 'x' : 'X';
+ *--bp = '0';
+ }
+
+ /* Calculate number of pad characters to fill field width. */
+ pad = c->width - (buf_end - bp);
+ if (pad < 0)
+ pad = 0;
+
+ /* Do output. */
+ if ((c->flags & (MINUS | ZERO)) == 0)
+ output_dup (' ', pad, output, aux);
+ if (bp < buf_end && strchr (digits, *bp) == NULL)
+ output (*bp++, aux);
+ if (c->flags & ZERO)
+ output_dup ('0', pad, output, aux);
+ while (bp < buf_end)
+ output (*bp++, aux);
+ if (c->flags & MINUS)
+ output_dup (' ', pad, output, aux);
+}
+
+static void
+printf_string (const char *string, size_t length,
+ struct printf_conversion *c,
+ void (*output) (char, void *), void *aux)
+{
+ if (c->width > 1 && (c->flags & MINUS) == 0)
+ output_dup (' ', c->width - 1, output, aux);
+ while (length-- > 0)
+ output (*string++, aux);
+ if (c->width > 1 && (c->flags & MINUS) != 0)
+ output_dup (' ', c->width - 1, output, aux);
+}
+
+static void
+printf_core (const char *format,
+ void (*output) (char, void *), void *aux, ...)
+{
+ va_list args;
+
+ va_start (args, aux);
+ vprintf_core (format, args, output, aux);
+ va_end (args);
+}
+
+static void
+vprintf_core (const char *format, va_list args,
+ void (*output) (char, void *), void *aux)
+{
+ for (; *format != '\0'; format++)
+ {
+ struct printf_conversion c;
+
+ /* Literally copy non-conversions to output. */
+ if (*format != '%')
+ {
+ output (*format, aux);
+ continue;
+ }
+ format++;
+
+ /* %% => %. */
+ if (*format == '%')
+ {
+ output ('%', aux);
+ continue;
+ }
+
+ format = parse_conversion (format, &c, &args);
+ switch (*format)
+ {
+ case 'd':
+ case 'i':
+ {
+ intmax_t value;
+ uintmax_t abs_value;
+ bool negative = false;
+
+ switch (c.type)
+ {
+ case CHAR:
+ value = (signed char) va_arg (args, int);
+ break;
+ case SHORT:
+ value = (short) va_arg (args, int);
+ break;
+ case INT:
+ value = va_arg (args, int);
+ break;
+ case LONG:
+ value = va_arg (args, long);
+ break;
+ case LONGLONG:
+ value = va_arg (args, long long);
+ break;
+ case PTRDIFFT:
+ value = va_arg (args, ptrdiff_t);
+ break;
+ case SIZET:
+ value = va_arg (args, size_t);
+ break;
+ default:
+ NOT_REACHED ();
+ }
+
+ if (value < 0)
+ {
+ negative = true;
+ abs_value = -value;
+ }
+ else
+ abs_value = value;
+
+ printf_integer (abs_value, negative, "0123456789",
+ &c, output, aux);
+ }
+ break;
+
+ case 'o':
+ case 'u':
+ case 'x':
+ case 'X':
+ {
+ uintmax_t value;
+ const char *digits;
+
+ switch (c.type)
+ {
+ case CHAR:
+ value = (unsigned char) va_arg (args, unsigned);
+ break;
+ case SHORT:
+ value = (unsigned short) va_arg (args, unsigned);
+ break;
+ case INT:
+ value = va_arg (args, unsigned);
+ break;
+ case LONG:
+ value = va_arg (args, unsigned long);
+ break;
+ case LONGLONG:
+ value = va_arg (args, unsigned long long);
+ break;
+ case PTRDIFFT:
+ value = va_arg (args, ptrdiff_t);
+ break;
+ case SIZET:
+ value = va_arg (args, size_t);
+ break;
+ default:
+ NOT_REACHED ();
+ }
+
+ switch (*format)
+ {
+ case 'o':
+ digits = "01234567";
+ break;
+ case 'u':
+ digits = "0123456789";
+ break;
+ case 'x':
+ digits = "0123456789abcdef";
+ break;
+ case 'X':
+ digits = "0123456789ABCDEF";
+ break;
+ default:
+ NOT_REACHED ();
+ }
+
+ printf_integer (value, false, digits, &c, output, aux);
+ }
+ break;
+
+ case 'c':
+ {
+ char ch = va_arg (args, int);
+ printf_string (&ch, 1, &c, output, aux);
+ }
+ break;
+
+ case 's':
+ {
+ const char *s;
+ size_t length;
+
+ s = va_arg (args, char *);
+ if (s == NULL)
+ s = "(null)";
+
+ if (c.precision >= 0)
+ {
+ const char *zero = memchr (s, '\0', c.precision);
+ if (zero != NULL)
+ length = zero - s;
+ else
+ length = c.precision;
+ }
+ else
+ length = strlen (s);
+
+ printf_string (s, length, &c, output, aux);
+ }
+ break;
+
+ case 'p':
+ {
+ void *p = va_arg (args, void *);
+
+ c.flags = POUND;
+ if (p != NULL)
+ printf_integer ((uintptr_t) p,
+ false, "0123456789abcdef", &c,
+ output, aux);
+ else
+ printf_string ("(nil)", 5, &c, output, aux);
+ }
+ break;
+
+ case 'f':
+ case 'e':
+ case 'E':
+ case 'g':
+ case 'G':
+ case 'n':
+ printf_core ("<<no %%%c in kernel>>", output, aux, *format);
+ break;
+
+ default:
+ printf_core ("<<no %%%c conversion>>", output, aux, *format);
+ break;
+ }
+ }
+}
--- /dev/null
+#ifndef HEADER_LIB_H
+#define HEADER_LIB_H 1
+
+#include <stdarg.h>
+#include <stddef.h>
+
+#define ROUND_UP(X, STEP) (((X) + (STEP) - 1) / (STEP) * (STEP))
+#define DIV_ROUND_UP(X, STEP) (((X) + (STEP) - 1) / (STEP))
+
+void *memset (void *, int, size_t);
+void *memcpy (void *, const void *, size_t);
+void *memmove (void *, const void *, size_t);
+void *memchr (const void *, int, size_t);
+
+char *strchr (const char *, int);
+size_t strlcpy (char *, const char *, size_t);
+size_t strlen (const char *);
+
+void vprintk (const char *, va_list);
+void printk (const char *, ...)
+ __attribute__ ((format (printf, 1, 2)));
+
+static inline int
+isdigit (int c)
+{
+ return c >= '0' && c <= '9';
+}
+
+#endif /* lib.h */
--- /dev/null
+#include "list.h"
+#include "debug.h"
+
+void
+list_init (struct list *list)
+{
+ list->head.prev = NULL;
+ list->head.next = &list->tail;
+ list->tail.prev = &list->head;
+ list->tail.next = NULL;
+}
+
+struct list_elem *
+list_begin (struct list *list)
+{
+ return list->head.next;
+}
+
+struct list_elem *
+list_end (struct list *list)
+{
+ return &list->tail;
+}
+
+static inline bool
+is_head (struct list_elem *elem)
+{
+ return elem != NULL && elem->prev == NULL && elem->next != NULL;
+}
+
+static inline bool
+is_real (struct list_elem *elem)
+{
+ return elem != NULL && elem->prev != NULL && elem->next != NULL;
+}
+
+static inline bool
+is_tail (struct list_elem *elem)
+{
+ return elem != NULL && elem->prev != NULL && elem->next == NULL;
+}
+
+struct list_elem *
+list_next (struct list_elem *elem)
+{
+ ASSERT (is_real (elem));
+ return elem->next;
+}
+
+struct list_elem *
+list_prev (struct list_elem *elem)
+{
+ ASSERT (is_real (elem) || is_tail (elem));
+ return elem->prev;
+}
+
+void
+list_insert (struct list_elem *before, struct list_elem *elem)
+{
+ ASSERT (is_real (before) || is_tail (before));
+ ASSERT (elem != NULL);
+
+ elem->prev = before->prev;
+ elem->next = before;
+ before->prev->next = elem;
+ before->prev = elem;
+}
+
+void
+list_splice (struct list_elem *target,
+ struct list_elem *first, struct list_elem *last)
+{
+ ASSERT (is_real (target) || is_tail (target));
+ if (first == last)
+ return;
+ last = list_prev (last);
+
+ ASSERT (is_real (first));
+ ASSERT (is_real (last));
+
+ /* Cleanly remove FIRST...LAST from its current list. */
+ first->prev->next = last->next;
+ last->next->prev = first->prev;
+
+ /* Splice FIRST...LAST into new list. */
+ first->prev = target->prev;
+ last->next = target;
+ target->prev->next = first;
+ target->prev = last;
+}
+
+void
+list_push_front (struct list *list, struct list_elem *elem)
+{
+ list_insert (list_begin (list), elem);
+}
+
+void
+list_push_back (struct list *list, struct list_elem *elem)
+{
+ list_insert (list_end (list), elem);
+}
+
+static struct list_elem *
+remove_item (struct list_elem *elem)
+{
+ ASSERT (is_real (elem));
+ elem->prev->next = elem->next;
+ elem->next->prev = elem->prev;
+ return elem;
+}
+
+void
+list_remove (struct list_elem *elem)
+{
+ remove_item (elem);
+}
+
+struct list_elem *
+list_pop_front (struct list *list)
+{
+ return remove_item (list_front (list));
+}
+
+struct list_elem *
+list_pop_back (struct list *list)
+{
+ return remove_item (list_back (list));
+}
+
+struct list_elem *
+list_front (struct list *list)
+{
+ return list_begin (list);
+}
+
+struct list_elem *
+list_back (struct list *list)
+{
+ return list_prev (list_end (list));
+}
+
+size_t
+list_size (struct list *list)
+{
+ struct list_elem *elem;
+ size_t cnt = 0;
+
+ for (elem = list_begin (list); elem != list_end (list); elem = elem->next)
+ cnt++;
+ return cnt;
+}
+
+bool
+list_empty (struct list *list)
+{
+ return list_begin (list) == list_end (list);
+}
+
+void
+list_reverse (struct list *list)
+{
+ struct list_elem *e;
+ struct list_elem te;
+
+ for (e = &list->head; e != NULL; e = e->prev)
+ {
+ struct list_elem *tep = e->prev;
+ e->prev = e->next;
+ e->next = tep;
+ }
+
+ te = list->head;
+ list->head = list->tail;
+ list->tail = te;
+}
+
+void
+list_merge (struct list *al, struct list *bl,
+ list_less_func *less, void *aux)
+{
+ struct list_elem *a;
+
+ ASSERT (al != NULL);
+ ASSERT (bl != NULL);
+ ASSERT (less != NULL);
+
+ a = list_begin (al);
+ while (a != list_end (al))
+ {
+ struct list_elem *b = list_begin (bl);
+ if (less (b, a, aux))
+ {
+ list_splice (a, b, list_next (b));
+ if (list_empty (bl))
+ break;
+ }
+ else
+ a = list_next (a);
+ }
+ list_splice (list_end (al), list_begin (bl), list_end (bl));
+}
+
+void
+list_sort (struct list *list,
+ list_less_func *less, void *aux)
+{
+ struct list tmp;
+ struct list_elem *middle, *last;
+
+ ASSERT (list != NULL);
+ ASSERT (less != NULL);
+
+ /* Empty and 1-element lists are already sorted. */
+ if (list_empty (list) || list_next (list_begin (list)) == list_end (list))
+ return;
+
+ /* Find middle of LIST. (We're not interested in the end of
+ the list but it's incidentally needed.) */
+ middle = list_begin (list);
+ last = list_next (middle);
+ while (last != list_end (list) && list_next (last) != list_end (list))
+ {
+ middle = list_next (middle);
+ last = list_next (list_next (last));
+ }
+
+ /* Extract first half of LIST into a temporary list. */
+ list_init (&tmp);
+ list_splice (list_begin (&tmp), list_begin (list), middle);
+
+ /* Sort each half-list and merge the result. */
+ list_sort (&tmp, less, aux);
+ list_sort (list, less, aux);
+ list_merge (list, &tmp, less, aux);
+}
+
+void
+list_insert_ordered (struct list *list, struct list_elem *elem,
+ list_less_func *less, void *aux)
+{
+ struct list_elem *e;
+
+ ASSERT (list != NULL);
+ ASSERT (elem != NULL);
+ ASSERT (less != NULL);
+
+ for (e = list_begin (list); e != list_end (list); e = list_next (e))
+ if (less (elem, e, aux))
+ break;
+ return list_insert (e, elem);
+}
+
+void
+list_unique (struct list *list,
+ list_less_func *less, void *aux)
+{
+ struct list_elem *elem, *next;
+
+ ASSERT (list != NULL);
+ ASSERT (less != NULL);
+ if (list_empty (list))
+ return;
+
+ elem = list_begin (list);
+ while ((next = list_next (elem)) != list_end (list))
+ if (!less (elem, next, aux) && !less (next, elem, aux))
+ list_remove (next);
+ else
+ elem = next;
+}
--- /dev/null
+#ifndef HEADER_LIST_H
+#define HEADER_LIST_H 1
+
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+
+struct list_elem
+ {
+ struct list_elem *prev, *next;
+ };
+
+struct list
+ {
+ struct list_elem head, tail;
+ };
+
+#define list_entry(LIST_ELEM, STRUCT, MEMBER) \
+ ((STRUCT *) ((uint8_t *) (LIST_ELEM) - offsetof (STRUCT, MEMBER)))
+
+void list_init (struct list *);
+
+struct list_elem *list_begin (struct list *);
+struct list_elem *list_end (struct list *);
+struct list_elem *list_next (struct list_elem *);
+struct list_elem *list_prev (struct list_elem *);
+
+void list_insert (struct list_elem *, struct list_elem *);
+void list_splice (struct list_elem *before,
+ struct list_elem *first, struct list_elem *last);
+void list_push_front (struct list *, struct list_elem *);
+void list_push_back (struct list *, struct list_elem *);
+
+void list_remove (struct list_elem *);
+struct list_elem *list_pop_front (struct list *);
+struct list_elem *list_pop_back (struct list *);
+
+struct list_elem *list_front (struct list *);
+struct list_elem *list_back (struct list *);
+
+size_t list_size (struct list *);
+bool list_empty (struct list *);
+
+void list_reverse (struct list *);
+
+typedef bool list_less_func (const struct list_elem *a,
+ const struct list_elem *b, void *aux);
+
+void list_merge (struct list *, struct list *,
+ list_less_func *, void *aux);
+void list_sort (struct list *,
+ list_less_func *, void *aux);
+void list_insert_ordered (struct list *, struct list_elem *,
+ list_less_func *, void *aux);
+void list_unique (struct list *,
+ list_less_func *, void *aux);
+
+#endif /* list.h */
--- /dev/null
+#include "random.h"
+#include <stdint.h>
+
+/* RC4-based pseudo-random state. */
+static uint8_t s[256];
+static uint8_t s_i, s_j;
+
+static inline void
+swap_byte (uint8_t *a, uint8_t *b)
+{
+ uint8_t t = *a;
+ *a = *b;
+ *b = t;
+}
+
+static uint8_t
+key_byte (int idx)
+{
+ return idx ^ 0xff;
+}
+
+void
+random_init (void)
+{
+ int i;
+ uint8_t j;
+
+ for (i = 0; i < 256; i++)
+ s[i] = i;
+ for (i = j = 0; i < 256; i++)
+ {
+ j += s[i] + key_byte (i);
+ swap_byte (s + i, s + j);
+ }
+
+ s_i = s_j = 0;
+}
+
+void
+random_bytes (void *buf_, size_t size)
+{
+ uint8_t *buf;
+
+ for (buf = buf_; size-- > 0; buf++)
+ {
+ uint8_t s_k;
+
+ s_i++;
+ s_j += s[s_i];
+ swap_byte (s + s_i, s + s_j);
+
+ s_k = s[s_i] + s[s_j];
+ *buf = s[s_k];
+ }
+}
+
+/* Returns a pseudo-random unsigned long. */
+unsigned long
+random_ulong (void)
+{
+ unsigned long ul;
+ random_bytes (&ul, sizeof ul);
+ return ul;
+}
--- /dev/null
+#ifndef HEADER_RANDOM_H
+#define HEADER_RANDOM_H 1
+
+#include <stddef.h>
+
+void random_init (void);
+void random_bytes (void *, size_t);
+unsigned long random_ulong (void);
+
+#endif /* random.h */
--- /dev/null
+all:
+%:
+ $(MAKE) -C build $@
--- /dev/null
+TOP_SRCDIR = ../..
+SOURCES = $(THREADS_SRC) $(DEVICES_SRC) $(LIB_SRC)
+INCLUDES = -I$(TOP_SRCDIR)/threads -I$(TOP_SRCDIR)/devices -I$(TOP_SRCDIR)/lib
+
+include ../../Makefile.inc
+
--- /dev/null
+#include <stdint.h>
+#include <stddef.h>
+#include <limits.h>
+#include "debug.h"
+#include "interrupt.h"
+#include "io.h"
+#include "kbd.h"
+#include "lib.h"
+#include "malloc.h"
+#include "mmu.h"
+#include "palloc.h"
+#include "random.h"
+#include "serial.h"
+#include "thread.h"
+#include "timer.h"
+#include "vga.h"
+
+/* Size of kernel static code and data, in 4 kB pages. */
+size_t kernel_pages;
+
+/* Amount of physical memory, in 4 kB pages. */
+size_t ram_pages;
+
+static void init_page_table (void);
+static void setup_gdt (void);
+void power_off (void);
+
+struct thread *a, *b;
+
+static void
+tfunc (void *aux UNUSED)
+{
+ for (;;)
+ {
+ size_t count, i;
+ if (random_ulong () % 5 == 0)
+ {
+ printk ("%s exiting\n", thread_current ()->name);
+ break;
+ }
+ count = random_ulong () % 25 * 1000000;
+ printk ("%s waiting %zu: ", thread_current ()->name, count);
+ for (i = 0; i < count; i++);
+ printk ("%s\n", thread_current ()->name);
+ }
+}
+
+int
+main (void)
+{
+ extern char _text, _end, __bss_start;
+
+ /* Clear out the BSS segment. */
+ memset (&__bss_start, 0, &_end - &__bss_start);
+
+ vga_init ();
+ serial_init ();
+
+ /* Calculate how much RAM the kernel uses, and find out from
+ the bootloader how much RAM this machine has. */
+ kernel_pages = (&_end - &_text + 4095) / 4096;
+ ram_pages = *(uint32_t *) (0x7e00 - 8);
+
+ printk ("Initializing nachos-x86, %d kB RAM detected.\n",
+ ram_pages * 4);
+
+ /* Memory from the end of the kernel through the end of memory
+ is free. Give it to the page allocator. */
+ palloc_init ((void *) (KERN_BASE + kernel_pages * NBPG),
+ (void *) (PHYS_BASE + ram_pages * NBPG));
+
+ init_page_table ();
+ setup_gdt ();
+
+ malloc_init ();
+ random_init ();
+
+ intr_init ();
+ timer_init ();
+ kbd_init ();
+ intr_enable ();
+
+ thread_init ();
+
+#if 0
+ printk ("running semaphore test... ");
+ sema_self_test ();
+ printk (" done.\n");
+#endif
+
+ {
+ struct thread *t;
+ int i;
+
+ for (i = 0; i < 4; i++)
+ {
+ char name[2];
+ name[0] = 'a' + i;
+ name[1] = 0;
+ t = thread_create (name, tfunc, NULL);
+ }
+ thread_start (t);
+ }
+
+ printk ("Done!\n");
+ return 0;
+}
+
+/* Populates the page directory and page table with the kernel
+ virtual mapping. */
+static void
+init_page_table (void)
+{
+ uint32_t *pd, *pt;
+ uint32_t paddr;
+
+ pd = palloc_get (PAL_ASSERT | PAL_ZERO);
+ pt = NULL;
+ for (paddr = 0; paddr < NBPG * ram_pages; paddr += NBPG)
+ {
+ uint32_t vaddr = paddr + PHYS_BASE;
+ size_t pde_idx = PDENO(vaddr);
+ size_t pte_idx = PTENO(vaddr);
+
+ if (pd[pde_idx] == 0)
+ {
+ pt = palloc_get (PAL_ASSERT | PAL_ZERO);
+ pd[pde_idx] = (uint32_t) vtop (pt) | PG_U | PG_W | PG_P;
+ }
+
+ pt[pte_idx] = paddr | PG_U | PG_W | PG_P;
+ }
+
+ /* Set the page table. */
+ asm volatile ("movl %0,%%cr3" :: "r" (vtop (pd)));
+}
+
+static uint64_t
+make_seg_desc (uint32_t base,
+ uint32_t limit,
+ enum seg_system system,
+ enum seg_type type,
+ int dpl,
+ enum seg_granularity granularity)
+{
+ uint32_t e0 = ((limit & 0xffff) /* Limit 15:0. */
+ | (base << 16)); /* Base 15:0. */
+ uint32_t e1 = (((base >> 16) & 0xff) /* Base 23:16. */
+ | ( system << 12) /* 0=system, 1=code/data. */
+ | ( type << 8) /* Segment type. */
+ | (dpl << 13) /* Descriptor privilege. */
+ | (1 << 15) /* Present. */
+ | (limit & 0xf0000) /* Limit 16:19. */
+ | (1 << 22) /* 32-bit segment. */
+ | ( granularity << 23) /* Byte/page granularity. */
+ | (base & 0xff000000)); /* Base 31:24. */
+ return e0 | ((uint64_t) e1 << 32);
+}
+
+static uint64_t
+make_code_desc (int dpl)
+{
+ return make_seg_desc (0, 0xfffff, SYS_CODE_DATA, TYPE_CODE | TYPE_READABLE,
+ dpl, GRAN_PAGE);
+}
+
+static uint64_t
+make_data_desc (int dpl)
+{
+ return make_seg_desc (0, 0xfffff, SYS_CODE_DATA, TYPE_WRITABLE,
+ dpl, GRAN_PAGE);
+}
+
+static uint64_t
+make_tss_desc (uint32_t base)
+{
+ return make_seg_desc (base, 0x67, SYS_SYSTEM, TYPE_TSS_32_A, 0, GRAN_BYTE);
+}
+
+uint64_t gdt[SEL_CNT];
+
+struct tss *tss;
+
+/* Sets up a proper GDT. The bootstrap loader's GDT didn't
+ include user-mode selectors or a TSS. */
+static void
+setup_gdt (void)
+{
+ uint64_t gdtr_operand;
+
+ /* Our TSS is never used in a call gate or task gate, so only a
+ few fields of it are ever referenced, and those are the only
+ ones we initialize. */
+ tss = palloc_get (PAL_ASSERT | PAL_ZERO);
+ tss->esp0 = (uint32_t) ptov(0xc0020000);
+ tss->ss0 = SEL_KDSEG;
+ tss->bitmap = 0xdfff;
+
+ /* Initialize GDT. */
+ gdt[SEL_NULL / sizeof *gdt] = 0;
+ gdt[SEL_KCSEG / sizeof *gdt] = make_code_desc (0);
+ gdt[SEL_KDSEG / sizeof *gdt] = make_data_desc (0);
+ gdt[SEL_UCSEG / sizeof *gdt] = make_code_desc (3);
+ gdt[SEL_UDSEG / sizeof *gdt] = make_data_desc (3);
+ gdt[SEL_TSS / sizeof *gdt] = make_tss_desc (vtop (tss));
+
+ /* Load GDTR, TR. */
+ gdtr_operand = make_dtr_operand (sizeof gdt - 1, gdt);
+ asm volatile ("lgdt %0" :: "m" (gdtr_operand));
+ asm volatile ("ltr %w0" :: "r" (SEL_TSS));
+}
+\f
+void
+power_off (void)
+{
+ const char s[] = "Shutdown";
+ const char *p;
+
+ printk ("Powering off...\n");
+ for (p = s; *p != '\0'; p++)
+ outb (0x8900, *p);
+ for (;;);
+}
--- /dev/null
+#include "interrupt.h"
+#include <stdint.h>
+#include "debug.h"
+#include "io.h"
+#include "lib.h"
+#include "mmu.h"
+#include "thread.h"
+#include "timer.h"
+\f
+enum if_level
+intr_get_level (void)
+{
+ uint32_t flags;
+
+ asm ("pushfl; popl %0" : "=g" (flags));
+
+ return flags & (1 << 9) ? IF_ON : IF_OFF;
+}
+
+enum if_level
+intr_set_level (enum if_level level)
+{
+ enum if_level old_level = intr_get_level ();
+ if (level == IF_ON)
+ intr_enable ();
+ else
+ intr_disable ();
+ return old_level;
+}
+
+enum if_level
+intr_enable (void)
+{
+ enum if_level old_level = intr_get_level ();
+ asm volatile ("sti");
+ return old_level;
+}
+
+enum if_level
+intr_disable (void)
+{
+ enum if_level old_level = intr_get_level ();
+ asm volatile ("cli");
+ return old_level;
+}
+\f
+static void
+pic_init (void)
+{
+ /* Every PC has two 8259A Programmable Interrupt Controller
+ (PIC) chips. One is a "master" accessible at ports 0x20 and
+ 0x21. The other is a "slave" cascaded onto the master's IRQ
+ 2 line and accessible at ports 0xa0 and 0xa1. Accesses to
+ port 0x20 set the A0 line to 0 and accesses to 0x21 set the
+ A1 line to 1. The situation is similar for the slave PIC.
+ Refer to the 8259A datasheet for details.
+
+ By default, interrupts 0...15 delivered by the PICs will go
+ to interrupt vectors 0...15. Unfortunately, those vectors
+ are also used for CPU traps and exceptions. We reprogram
+ the PICs so that interrupts 0...15 are delivered to
+ interrupt vectors 32...47 instead. */
+
+ /* Mask all interrupts on both PICs. */
+ outb (0x21, 0xff);
+ outb (0xa1, 0xff);
+
+ /* Initialize master. */
+ outb (0x20, 0x11); /* ICW1: single mode, edge triggered, expect ICW4. */
+ outb (0x21, 0x20); /* ICW2: line IR0...7 -> irq 0x20...0x27. */
+ outb (0x21, 0x04); /* ICW3: slave PIC on line IR2. */
+ outb (0x21, 0x01); /* ICW4: 8086 mode, normal EOI, non-buffered. */
+
+ /* Initialize slave. */
+ outb (0xa0, 0x11); /* ICW1: single mode, edge triggered, expect ICW4. */
+ outb (0xa1, 0x28); /* ICW2: line IR0...7 -> irq 0x28...0x2f. */
+ outb (0xa1, 0x02); /* ICW3: slave ID is 2. */
+ outb (0xa1, 0x01); /* ICW4: 8086 mode, normal EOI, non-buffered. */
+
+ /* Unmask all interrupts. */
+ outb (0x21, 0x00);
+ outb (0xa1, 0x00);
+}
+
+/* Sends an end-of-interrupt signal to the PIC for the given IRQ.
+ If we don't acknowledge the IRQ, we'll never get it again, so
+ this is important. */
+static void
+pic_eoi (void)
+{
+ /* FIXME? The Linux code is much more complicated. */
+ outb (0x20, 0x20);
+}
+\f
+uint64_t idt[256];
+
+extern void (*intr_stubs[256]) (void);
+
+intr_handler_func *intr_handlers[256];
+
+void intr_handler (struct intr_args *args);
+
+bool intr_in_progress;
+bool yield_on_return;
+
+void
+intr_handler (struct intr_args *args)
+{
+ bool external;
+
+ yield_on_return = false;
+
+ external = args->vec_no >= 0x20 && args->vec_no < 0x30;
+ if (external)
+ {
+ ASSERT (intr_get_level () == IF_OFF);
+ ASSERT (!intr_context ());
+ intr_in_progress = true;
+ }
+
+ intr_handlers[args->vec_no] (args);
+
+ if (external)
+ {
+ ASSERT (intr_get_level () == IF_OFF);
+ ASSERT (intr_context ());
+ intr_in_progress = false;
+ pic_eoi ();
+ }
+
+ if (yield_on_return)
+ {
+ printk (".");
+ thread_yield ();
+ }
+}
+
+bool
+intr_context (void)
+{
+ return intr_in_progress;
+}
+
+void
+intr_yield_on_return (void)
+{
+ yield_on_return = true;
+}
+
+/* Handles interrupts we don't know about. */
+intr_handler_func intr_unexpected;
+
+/* Handlers for CPU exceptions. */
+intr_handler_func excp00_divide_error;
+intr_handler_func excp01_debug;
+intr_handler_func excp02_nmi;
+intr_handler_func excp03_breakpoint;
+intr_handler_func excp04_overflow;
+intr_handler_func excp05_bound;
+intr_handler_func excp06_invalid_opcode;
+intr_handler_func excp07_device_not_available;
+intr_handler_func excp08_double_fault;
+intr_handler_func excp09_coprocessor_overrun;
+intr_handler_func excp0a_invalid_tss;
+intr_handler_func excp0b_segment_not_present;
+intr_handler_func excp0c_stack_fault;
+intr_handler_func excp0d_general_protection;
+intr_handler_func excp0e_page_fault;
+intr_handler_func excp10_fp_error;
+intr_handler_func excp11_alignment;
+intr_handler_func excp12_machine_check;
+intr_handler_func excp13_simd_error;
+
+static uint64_t
+make_intr_gate (void (*target) (void),
+ int dpl)
+{
+ uint32_t offset = (uint32_t) target;
+ uint32_t e0 = ((offset & 0xffff) /* Offset 15:0. */
+ | (SEL_KCSEG << 16)); /* Target code segment. */
+ uint32_t e1 = ((offset & 0xffff0000) /* Offset 31:16. */
+ | (1 << 15) /* Present. */
+ | (dpl << 13) /* Descriptor privilege. */
+ | (SYS_SYSTEM << 12) /* System. */
+ | (TYPE_INT_32 << 8)); /* 32-bit interrupt gate. */
+ return e0 | ((uint64_t) e1 << 32);
+}
+
+static uint64_t
+make_trap_gate (void (*target) (void),
+ int dpl)
+{
+ return make_intr_gate (target, dpl) | (1 << 8);
+}
+
+/* We don't support nested interrupts generated by external
+ hardware, so these interrupts (vec_no 0x20...0x2f) should
+ specify IF_OFF for LEVEL. Otherwise a timer interrupt could
+ cause a task switch during interrupt handling. Most other
+ interrupts can and should be handled with interrupts
+ enabled. */
+void
+intr_register (uint8_t vec_no, int dpl, enum if_level level,
+ intr_handler_func *handler)
+{
+ if (level == IF_ON)
+ idt[vec_no] = make_trap_gate (intr_stubs[vec_no], dpl);
+ else
+ idt[vec_no] = make_intr_gate (intr_stubs[vec_no], dpl);
+ intr_handlers[vec_no] = handler;
+}
+
+void
+intr_init (void)
+{
+ uint64_t idtr_operand;
+ int i;
+
+ pic_init ();
+
+ /* Install default handlers. */
+ for (i = 0; i < 256; i++)
+ intr_register (i, 0, IF_OFF, intr_unexpected);
+
+ /* Most exceptions require ring 0.
+ Exceptions 3, 4, and 5 can be caused by ring 3 directly.
+
+ Most exceptions can be handled with interrupts turned on.
+ We need to disable interrupts for page faults because the
+ fault address is stored in CR2 and needs to be preserved.
+ */
+#if 0
+ intr_register (0x00, 0, IF_ON, excp00_divide_error);
+ intr_register (0x01, 0, IF_ON, excp01_debug);
+ intr_register (0x02, 0, IF_ON, excp02_nmi);
+ intr_register (0x03, 3, IF_ON, excp03_breakpoint);
+ intr_register (0x04, 3, IF_ON, excp04_overflow);
+ intr_register (0x05, 3, IF_ON, excp05_bound);
+ intr_register (0x06, 0, IF_ON, excp06_invalid_opcode);
+ intr_register (0x07, 0, IF_ON, excp07_device_not_available);
+ intr_register (0x08, 0, IF_ON, excp08_double_fault);
+ intr_register (0x09, 0, IF_ON, excp09_coprocessor_overrun);
+ intr_register (0x0a, 0, IF_ON, excp0a_invalid_tss);
+ intr_register (0x0b, 0, IF_ON, excp0b_segment_not_present);
+ intr_register (0x0c, 0, IF_ON, excp0c_stack_fault);
+ intr_register (0x0d, 0, IF_ON, excp0d_general_protection);
+ intr_register (0x0e, 0, IF_OFF, excp0e_page_fault);
+ intr_register (0x10, 0, IF_ON, excp10_fp_error);
+ intr_register (0x11, 0, IF_ON, excp11_alignment);
+ intr_register (0x12, 0, IF_ON, excp12_machine_check);
+ intr_register (0x13, 0, IF_ON, excp13_simd_error);
+#endif
+
+ idtr_operand = make_dtr_operand (sizeof idt - 1, idt);
+ asm volatile ("lidt %0" :: "m" (idtr_operand));
+}
+
+void
+intr_unexpected (struct intr_args *regs)
+{
+ uint32_t cr2;
+ asm ("movl %%cr2, %0" : "=r" (cr2));
+ printk ("Unexpected interrupt 0x%02x, error code %08x, cr2=%08x, eip=%08x\n",
+ regs->vec_no, regs->error_code, cr2, regs->eip);
+ for (;;);
+}
--- /dev/null
+#ifndef HEADER_INTERRUPT_H
+#define HEADER_INTERRUPT_H 1
+
+#include <stdbool.h>
+#include <stdint.h>
+
+enum if_level
+ {
+ IF_OFF, /* Interrupts disabled. */
+ IF_ON /* Interrupts enabled. */
+ };
+
+enum if_level intr_get_level (void);
+enum if_level intr_set_level (enum if_level);
+enum if_level intr_enable (void);
+enum if_level intr_disable (void);
+\f
+struct intr_args
+ {
+ uint32_t edi;
+ uint32_t esi;
+ uint32_t ebp;
+ uint32_t esp;
+ uint32_t ebx;
+ uint32_t edx;
+ uint32_t ecx;
+ uint32_t eax;
+ uint16_t es, :16;
+ uint16_t ds, :16;
+ uint32_t vec_no;
+ uint32_t error_code;
+ uint32_t eip;
+ };
+
+typedef void intr_handler_func (struct intr_args *);
+
+void intr_init (void);
+void intr_register (uint8_t vec, int dpl, enum if_level, intr_handler_func *);
+bool intr_context (void);
+void intr_yield_on_return (void);
+
+#endif /* interrupt.h */
--- /dev/null
+#! /usr/bin/perl
+
+print <<'EOF';
+#include "mmu.h"
+
+ .globl intr_stubs
+intr_stubs:
+EOF
+
+for $i (0...255) {
+ $x = sprintf ("%02x", $i);
+ print "\t.long intr${x}_stub\n";
+}
+print "\n";
+
+for $i (0...255) {
+ $x = sprintf ("%02x", $i);
+ print "\t.globl intr${x}_stub\n";
+ print "intr${x}_stub:\n";
+ print "\tpushl \$0\n" if $i != 8 && $i != 10 && $i != 11 && $i != 13 && $i != 14 && $i != 17;
+ print "\tpushl \$0x$x\n";
+ print "\tjmp intr_entry\n";
+}
+
+print <<'EOF';
+intr_entry:
+ # Save caller's registers.
+ pushl %ds
+ pushl %es
+ pushal
+
+ # Set up kernel environment.
+ cld
+ movl $SEL_KDSEG, %eax
+ movl %eax, %ds
+ movl %eax, %es
+
+ # Call handler.
+ pushl %esp
+ .globl intr_handler
+ call intr_handler
+ addl $4, %esp
+
+ # Restore caller's registers.
+ popal
+ popl %es
+ popl %ds
+ addl $8, %esp
+ iret
+EOF
--- /dev/null
+#ifndef PORTIO_H
+#define PORTIO_H 1
+
+#include <stddef.h>
+#include <stdint.h>
+
+static inline uint8_t
+inb(uint16_t port)
+{
+ uint8_t data;
+ asm volatile ("inb %w1,%0" : "=a" (data) : "d" (port));
+ return data;
+}
+
+static inline void
+insb(uint16_t port, void *addr, size_t cnt)
+{
+ asm volatile ("cld\n\trepne\n\tinsb" :
+ "=D" (addr), "=c" (cnt) :
+ "d" (port), "0" (addr), "1" (cnt) :
+ "memory", "cc");
+}
+
+static inline uint16_t
+inw(uint16_t port)
+{
+ uint16_t data;
+ asm volatile ("inw %w1,%0" : "=a" (data) : "d" (port));
+ return data;
+}
+
+static inline void
+insw(uint16_t port, void *addr, size_t cnt)
+{
+ asm volatile ("cld\n\trepne\n\tinsw" :
+ "=D" (addr), "=c" (cnt) :
+ "d" (port), "0" (addr), "1" (cnt) :
+ "memory", "cc");
+}
+
+static inline uint32_t
+inl(uint16_t port)
+{
+ uint32_t data;
+ asm volatile ("inl %w1,%0" : "=a" (data) : "d" (port));
+ return data;
+}
+
+static inline void
+insl(uint16_t port, void *addr, size_t cnt)
+{
+ asm volatile ("cld\n\trepne\n\tinsl" :
+ "=D" (addr), "=c" (cnt) :
+ "d" (port), "0" (addr), "1" (cnt) :
+ "memory", "cc");
+}
+
+static inline void
+outb(uint16_t port, uint8_t data)
+{
+ asm volatile ("outb %0,%w1" : : "a" (data), "d" (port));
+}
+
+static inline void
+outsb(uint16_t port, const void *addr, size_t cnt)
+{
+ asm volatile ("cld\n\trepne\n\toutsb" :
+ "=S" (addr), "=c" (cnt) :
+ "d" (port), "0" (addr), "1" (cnt) :
+ "cc");
+}
+
+static inline void
+outw(uint16_t port, uint16_t data)
+{
+ asm volatile ("outw %0,%w1" : : "a" (data), "d" (port));
+}
+
+static inline void
+outsw(uint16_t port, const void *addr, size_t cnt)
+{
+ asm volatile ("cld\n\trepne\n\toutsw" :
+ "=S" (addr), "=c" (cnt) :
+ "d" (port), "0" (addr), "1" (cnt) :
+ "cc");
+}
+
+static inline void
+outl(uint16_t port, uint32_t data)
+{
+ asm volatile ("outl %0,%w1" : : "a" (data), "d" (port));
+}
+
+#endif /* io.h */
--- /dev/null
+/* ld script to make i386 Linux kernel
+ * Written by Martin Mares <mj@atrey.karlin.mff.cuni.cz>;
+ */
+OUTPUT_FORMAT("elf32-i386", "elf32-i386", "elf32-i386")
+OUTPUT_ARCH(i386)
+ENTRY(start)
+SECTIONS
+{
+ . = 0xC0100000;
+ _text = .; /* Text and read-only data */
+ .text : {
+ *(.text)
+ *(.fixup)
+ *(.gnu.warning)
+ } = 0x9090
+
+ _etext = .; /* End of text section */
+
+ .rodata : { *(.rodata) *(.rodata.*) }
+ .kstrtab : { *(.kstrtab) }
+
+ .data : { /* Data */
+ *(.data)
+ CONSTRUCTORS
+ }
+
+ _edata = .; /* End of data section */
+
+ __bss_start = .; /* BSS */
+ .bss : {
+ *(.bss)
+ }
+ _end = . ;
+}
--- /dev/null
+#include "mmu.h"
+
+###################################################################################
+# ENTRY POINT
+# This code should be stored in the first sector of the hard disk. When the
+# BIOS runs, it loads this code at physical address 0x7c00 - 0x7e00 (512 bytes).
+# Then jumps to the beginning of it, in real-mode (BIOS runs in real mode).
+#
+# This code switches into protected mode (32-bit mode) so that all of
+# memory can accessed, then calls into C.
+###################################################################################
+
+.globl start # Entry point
+start: .code16 # This runs in real mode
+ cli # Disable interrupts
+ cld # String ops inc
+ xorw %ax,%ax # Zero
+ movw %ax,%es # Address
+ movw %ax,%ds # data
+ movw %ax,%ss # Set up
+ movw $start,%sp # stack (grows down)
+
+#### Enable A20:
+#### Address line 20 is tied to low when the machine boots,
+#### obviously this a bit of a drag, such as when trying to
+#### address memory above 1MB. This code undoes this.
+
+1: inb $0x64,%al # Get status
+ testb $0x2,%al # Busy?
+ jnz 1b # Yes
+ movb $0xd1,%al # Command: Write
+ outb %al,$0x64 # output port
+2: inb $0x64,%al # Get status
+ testb $0x2,%al # Busy?
+ jnz 2b # Yes
+ movb $0xdf,%al # Enable
+ outb %al,$0x60 # A20
+
+#### Get memory size, via interrupt 15h function 88h.
+#### Returns CF clear if successful, with AX = (kB of physical memory) - 1024.
+#### This only works for memory sizes <= 65 MB, which should be fine for our purposes.
+
+ movb $0x88,%ah
+ int $0x15
+ jc panic # Carry flag set on error
+ addl $1024,%eax # Total kB
+ shrl $2,%eax # Total 4 kB pages
+ movl %eax, ram_pages
+
+#### switch from real to protected mode
+#### The segments in GDT allow all of physical memory to be accessed.
+#### Furthermore, the segments have base addresses of 0, so that the
+#### segment translation is a NOP, ie. virtual addresses are identical to
+#### their physical addresses. With this setup, it appears to this code
+#### that it is running directly on physical memory.
+
+ cli # Mandatory since we dont set up an IDT
+ lgdt gdtdesc # load GDT -- mandatory in protected mode
+ movl %cr0, %eax # turn on protected mode
+ orl $CR0_PE, %eax #
+ movl %eax, %cr0 #
+ ### CPU magic: jump to relocation, flush prefetch queue, and reload %cs
+ ### Has the effect of just jmp to the next instruction, but simultaneous
+ ### loads CS with $PROT_MODE_CSEG.
+ ljmp $SEL_KCSEG, $protcseg
+
+#### We are in protected mode in a 32-bit segment (hence the .code32)
+protcseg:
+ .code32
+ movw $SEL_KDSEG, %ax # set up data segment registers
+ movw %ax, %ds
+ movw %ax, %es
+ movw %ax, %fs
+ movw %ax, %gs
+ movw %ax, %ss
+
+#### Load kernel at 1 MB by frobbing the IDE controller directly.
+
+ movl $1, %ebx
+ movl $0x100000, %edi
+read_sector:
+ movl $0x1f7, %edx
+1: inb %dx, %al
+ testb $0x80, %al
+ jnz 1b
+
+ movl $0x1f2, %edx
+ movb $1, %al
+ outb %al, %dx
+
+ movl %ebx, %eax
+ andl $0x0fffffff, %eax
+ orl $0xe0000000, %eax
+
+ movl $4, %ecx
+2: incl %edx
+ outb %al, %dx
+ shrl $8, %eax
+ loop 2b
+
+ incw %dx
+ movb $0x20, %al
+ outb %al, %dx
+
+1: inb %dx, %al
+ testb $0x80, %al
+ jnz 1b
+
+ movl $512 / 4, %ecx
+ movl $0x1f0, %edx
+ rep insl
+
+ incl %ebx
+ cmpl $KERNEL_LOAD_PAGES*8 + 1, %ebx
+ jnz read_sector
+
+##### Create temporary PDE and PTE and set page directory pointer
+##### FIXME? We could use a single 4 MB page instead of 1024 4 kB pages.
+
+ movl $0x10000, %edi
+ movl %edi, %cr3
+ subl %eax, %eax
+ movl $0x400, %ecx
+ rep stosl
+ movl $0x11000 | PG_U | PG_W | PG_P, %eax
+ movl %eax, 0x10000
+ movl %eax, 0x10c00
+ movl $PG_U | PG_W | PG_P, %eax
+ movl $0x400, %ecx
+1: stosl
+ addl $0x1000, %eax
+ loop 1b
+
+##### Enable paging.
+
+ movl %cr0, %eax
+ orl $CR0_PG, %eax
+ movl %eax, %cr0
+ jmp 1f
+1:
+
+##### Jump to kernel entry point.
+
+ movl $0xc0007c00, %esp
+ movl $0xc0100000, %eax
+ jmp *%eax
+
+##### GDT
+
+gdt:
+ .quad 0x0000000000000000 # null seg
+ .quad 0x00cf9a000000ffff # code seg
+ .quad 0x00cf92000000ffff # data seg
+
+gdtdesc:
+ .word 0x17 # sizeof (gdt) - 1
+ .long gdt # address gdt
+
+##### Arrive here on error
+panic: jmp panic
+
+##### Memory size in 4 kB pages.
+ .org 0x200 - 8
+ram_pages:
+ .long 0
+
+##### Boot-sector signature for BIOS inspection.
+ .org 0x200 - 2
+ .word 0xaa55
--- /dev/null
+#include "malloc.h"
+#include <stdint.h>
+#include "debug.h"
+#include "lib.h"
+#include "mmu.h"
+#include "palloc.h"
+
+struct desc
+ {
+ size_t slot_size; /* Size of each element in bytes. */
+ struct slot *free_list; /* Unused slots. */
+ struct arena *arenas; /* Arenas. */
+ };
+
+struct arena
+ {
+ struct desc *desc; /* Owning descriptor. */
+ struct arena *prev, *next; /* Doubly linked list of arenas. */
+ };
+
+struct slot
+ {
+ struct slot *next; /* Singly linked list of slots. */
+ };
+
+struct desc descs[16];
+size_t desc_cnt;
+
+void
+malloc_init (void)
+{
+ size_t slot_size;
+
+ for (slot_size = 16; slot_size < NBPG; slot_size *= 2)
+ {
+ struct desc *d = &descs[desc_cnt++];
+ ASSERT (desc_cnt <= sizeof descs / sizeof *descs);
+ d->slot_size = slot_size;
+ d->free_list = NULL;
+ d->arenas = NULL;
+ }
+}
+
+static struct arena *
+slot_to_arena (struct slot *s)
+{
+ return (struct arena *) ((uint32_t) s & (NBPG - 1));
+}
+
+static void *
+get_free_slot (struct desc *d)
+{
+ void *block = d->free_list;
+ ASSERT (block != NULL);
+ d->free_list = d->free_list->next;
+ return block;
+}
+
+void *
+malloc (size_t size)
+{
+ struct desc *d;
+ struct arena *a;
+ size_t ofs;
+
+ if (size == 0)
+ return NULL;
+
+ for (d = descs; d < descs + desc_cnt; d++)
+ if (size < d->slot_size)
+ break;
+ if (d == descs + desc_cnt)
+ {
+ printk ("can't malloc %zu byte object\n", size);
+ return NULL;
+ }
+
+ if (d->free_list != NULL)
+ return get_free_slot (d);
+
+ a = palloc_get (0);
+ if (a == NULL)
+ return NULL;
+
+ a->desc = d;
+ a->prev = NULL;
+ a->next = d->arenas;
+ if (d->arenas != NULL)
+ d->arenas->prev = a;
+ for (ofs = sizeof *a; ofs + d->slot_size <= NBPG; ofs += d->slot_size)
+ {
+ struct slot *s = (struct slot *) ((uint8_t *) a + ofs);
+ s->next = d->free_list;
+ d->free_list = s;
+ }
+
+ return get_free_slot (d);
+}
+
+void
+free (void *p)
+{
+ struct slot *s = p;
+ struct arena *a = slot_to_arena (s);
+ struct desc *d = a->desc;
+
+ s->next = d->free_list;
+ d->free_list = s;
+}
--- /dev/null
+#ifndef HEADER_MALLOC_H
+#define HEADER_MALLOC_H
+
+#include "debug.h"
+#include <stddef.h>
+
+void malloc_init (void);
+void *malloc (size_t)
+ ATTRIBUTE ((malloc));
+void free (void *);
+
+#endif /* malloc.h */
--- /dev/null
+/*
+ * Copyright (C) 1997 Massachusetts Institute of Technology
+ *
+ * This software is being provided by the copyright holders under the
+ * following license. By obtaining, using and/or copying this software,
+ * you agree that you have read, understood, and will comply with the
+ * following terms and conditions:
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose and without fee or royalty is
+ * hereby granted, provided that the full text of this NOTICE appears on
+ * ALL copies of the software and documentation or portions thereof,
+ * including modifications, that you make.
+ *
+ * THIS SOFTWARE IS PROVIDED "AS IS," AND COPYRIGHT HOLDERS MAKE NO
+ * REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED. BY WAY OF EXAMPLE,
+ * BUT NOT LIMITATION, COPYRIGHT HOLDERS MAKE NO REPRESENTATIONS OR
+ * WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY PARTICULAR PURPOSE OR
+ * THAT THE USE OF THE SOFTWARE OR DOCUMENTATION WILL NOT INFRINGE ANY
+ * THIRD PARTY PATENTS, COPYRIGHTS, TRADEMARKS OR OTHER RIGHTS. COPYRIGHT
+ * HOLDERS WILL BEAR NO LIABILITY FOR ANY USE OF THIS SOFTWARE OR
+ * DOCUMENTATION.
+ *
+ * The name and trademarks of copyright holders may NOT be used in
+ * advertising or publicity pertaining to the software without specific,
+ * written prior permission. Title to copyright in this software and any
+ * associated documentation will at all times remain with copyright
+ * holders. See the file AUTHORS which should have accompanied this software
+ * for a list of all copyright holders.
+ *
+ * This file may be derived from previously copyrighted software. This
+ * copyright applies only to those changes made by the copyright
+ * holders listed in the AUTHORS file. The rest of this file is covered by
+ * the copyright notices, if any, listed below.
+ */
+
+
+#ifndef _MMU_H_
+#define _MMU_H_
+
+#ifndef __ASSEMBLER__
+#include <stdint.h>
+#endif
+
+// An Address:
+// +--------10------+-------10-------+---------12----------+
+// | Page Directory | Page Table | Offset within Page |
+// +----------------+----------------+---------------------+
+
+#define PGSHIFT 12 /* LOG2(NBPG) */
+#define NBPG (1 << PGSHIFT) /* bytes/page */
+
+/* Page tables (selected by VA[31:22] and indexed by VA[21:12]) */
+#define NLPG (1<<(PGSHIFT-2)) /* Number of 32-bit longwords per page */
+#define PGMASK (NBPG - 1) /* Mask for page offset. Terrible name! */
+/* Page number of virtual page in the virtual page table. */
+#define PGNO(va) ((uint32_t) (va) >> PGSHIFT)
+/* Index of PTE for VA within the corresponding page table */
+#define PTENO(va) (((uint32_t) (va) >> PGSHIFT) & 0x3ff)
+/* Round up to a page */
+#define PGROUNDUP(va) (((va) + PGMASK) & ~PGMASK)
+/* Round down to a page */
+#define PGROUNDDOWN(va) ((va) & ~PGMASK)
+/* Page directories (indexed by VA[31:22]) */
+#define PDSHIFT 22 /* LOG2(NBPD) */
+#define NBPD (1 << PDSHIFT) /* bytes/page dir */
+#define PDMASK (NBPD-1) /* byte offset into region mapped by
+ a page table */
+#define PDENO(va) ((uint32_t) (va) >> PDSHIFT)
+/* Round up */
+#define PDROUNDUP(va) (((va) + PDMASK) & ~PDMASK)
+/* Round down */
+#define PDROUNDDOWN(va) ((va) & ~PDMASK)
+
+/* At IOPHYSMEM (640K) there is a 384K hole for I/O. From the kernel,
+ * IOPHYSMEM can be addressed at KERNBASE + IOPHYSMEM. The hole ends
+ * at physical address EXTPHYSMEM. */
+#define IOPHYSMEM 0xa0000
+#define EXTPHYSMEM 0x100000
+
+
+/*
+ * Virtual memory map: Permissions
+ * kernel/user
+ *
+ * 4 Gig --------> +------------------------------+
+ * | | RW/--
+ * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ * : . :
+ * : . :
+ * : . :
+ * |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| RW/--
+ * | | RW/--
+ * | Physical Memory | RW/--
+ * | | RW/--
+ * KERNBASE -----> +------------------------------+
+ * | Kernel Virtual Page Table | RW/-- NBPD
+ * VPT,KSTACKTOP--> +------------------------------+ --+
+ * | Kernel Stack | RW/-- KSTKSIZE |
+ * | - - - - - - - - - - - - - - -| NBPD
+ * | Invalid memory | --/-- |
+ * ULIM ------> +------------------------------+ --+
+ * | R/O User VPT | R-/R- NBPD
+ * UVPT ----> +------------------------------+
+ * | R/O PPAGE | R-/R- NBPD
+ * UPPAGES ----> +------------------------------+
+ * | R/O UENVS | R-/R- NBPD
+ * UTOP,UENVS -------> +------------------------------+
+ * UXSTACKTOP -/ | user exception stack | RW/RW NBPG
+ * +------------------------------+
+ * | Invalid memory | --/-- NBPG
+ * USTACKTOP ----> +------------------------------+
+ * | normal user stack | RW/RW NBPG
+ * +------------------------------+
+ * | |
+ * | |
+ * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ * . .
+ * . .
+ * . .
+ * |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|
+ * | |
+ * UTEXT -------> +------------------------------+
+ * | | 2 * NBPD
+ * 0 ------------> +------------------------------+
+ */
+
+
+#define PHYS_BASE 0xc0000000 /* All physical memory mapped here. */
+#define KERN_BASE 0xc0100000 /* Kernel loaded here. */
+
+/* Virtual page table. Last entry of all PDEs contains a pointer to
+ * the PD itself, thereby turning the PD into a page table which
+ * maps all PTEs over the last 4 Megs of the virtual address space */
+#define VPT (KERNBASE - NBPD)
+#define KSTACKTOP VPT
+#define KSTKSIZE (8 * NBPG) /* size of a kernel stack */
+#define ULIM (KSTACKTOP - NBPD)
+
+/*
+ * User read-only mappings! Anything below here til UTOP are readonly to user.
+ * They are global pages mapped in at env allocation time.
+ */
+
+/* Same as VPT but read-only for users */
+#define UVPT (ULIM - NBPD)
+/* Read-only copies of all ppage structures */
+#define UPPAGES (UVPT - NBPD)
+/* Read only copy of the global env structures */
+#define UENVS (UPPAGES - NBPD)
+
+
+
+/*
+ * Top of user VM. User can manipulate VA from UTOP-1 and down!
+ */
+#define UTOP UENVS
+#define UXSTACKTOP (UTOP) /* one page user exception stack */
+/* leave top page invalid to guard against exception stack overflow */
+#define USTACKTOP (UTOP - 2*NBPG) /* top of the normal user stack */
+#define UTEXT (2*NBPD)
+
+/* Number of page tables for mapping physical memory at KERNBASE.
+ * (each PT contains 1K PTE's, for a total of 128 Megabytes mapped) */
+#define NPPT ((-KERNBASE)>>PDSHIFT)
+
+#ifndef __ASSEMBLER__
+/* Kernel virtual address at which physical address PADDR is
+ mapped. */
+static inline void *
+ptov (uint32_t paddr)
+{
+ return (void *) (paddr + PHYS_BASE);
+}
+
+/* Physical address at which kernel virtual address VADDR is
+ mapped. */
+static inline uint32_t
+vtop (void *vaddr)
+{
+ return (uint32_t) vaddr - PHYS_BASE;
+}
+#endif
+
+#define PFM_NONE 0x0 /* No page faults expected. Must be a kernel bug */
+#define PFM_KILL 0x1 /* On fault kill user process. */
+
+
+/*
+ * Macros to build GDT entries in assembly.
+ */
+#define SEG_NULL \
+ .word 0, 0; \
+ .byte 0, 0, 0, 0
+#define SEG(type,base,lim) \
+ .word ((lim)&0xffff), ((base)&0xffff); \
+ .byte (((base)>>16)&0xff), (0x90|(type)), \
+ (0xc0|(((lim)>>16)&0xf)), (((base)>>24)&0xff)
+
+
+
+/* Page Table/Directory Entry flags
+ * these are defined by the hardware
+ */
+#define PG_P 0x1 /* Present */
+#define PG_W 0x2 /* Writeable */
+#define PG_U 0x4 /* User */
+#define PG_PWT 0x8 /* Write-Through */
+#define PG_PCD 0x10 /* Cache-Disable */
+#define PG_A 0x20 /* Accessed */
+#define PG_D 0x40 /* Dirty */
+#define PG_PS 0x80 /* Page Size */
+#define PG_MBZ 0x180 /* Bits must be zero */
+#define PG_USER 0xe00 /* Bits for user processes */
+/*
+ * The PG_USER bits are not used by the kernel and they are
+ * not interpreted by the hardware. The kernel allows
+ * user processes to set them arbitrarily.
+ */
+
+
+
+/* Control Register flags */
+#define CR0_PE 0x1 /* Protection Enable */
+#define CR0_MP 0x2 /* Monitor coProcessor */
+#define CR0_EM 0x4 /* Emulation */
+#define CR0_TS 0x8 /* Task Switched */
+#define CR0_ET 0x10 /* Extension Type */
+#define CR0_NE 0x20 /* Numeric Errror */
+#define CR0_WP 0x10000 /* Write Protect */
+#define CR0_AM 0x40000 /* Alignment Mask */
+#define CR0_NW 0x20000000 /* Not Writethrough */
+#define CR0_CD 0x40000000 /* Cache Disable */
+#define CR0_PG 0x80000000 /* Paging */
+
+#define CR4_PCE 0x100 /* Performance counter enable */
+#define CR4_MCE 0x40 /* Machine Check Enable */
+#define CR4_PSE 0x10 /* Page Size Extensions */
+#define CR4_DE 0x08 /* Debugging Extensions */
+#define CR4_TSD 0x04 /* Time Stamp Disable */
+#define CR4_PVI 0x02 /* Protected-Mode Virtual Interrupts */
+#define CR4_VME 0x01 /* V86 Mode Extensions */
+
+/* EFLAGS Register. */
+#define FLAG_CF 0x00000001 /* Carry Flag. */
+#define FLAG_PF 0x00000004 /* Parity Flag. */
+#define FLAG_AF 0x00000010 /* Auxiliary Carry Flag. */
+#define FLAG_ZF 0x00000040 /* Zero Flag. */
+#define FLAG_SF 0x00000080 /* Sign Flag. */
+#define FLAG_TF 0x00000100 /* Trap Flag. */
+#define FLAG_IF 0x00000200 /* Interrupt Flag. */
+#define FLAG_DF 0x00000400 /* Direction Flag. */
+#define FLAG_OF 0x00000800 /* Overflow Flag. */
+#define FLAG_IOPL 0x00003000 /* I/O Privilege Level (2 bits). */
+#define FLAG_IOPL_SHIFT 12
+#define FLAG_NT 0x00004000 /* Nested Task. */
+#define FLAG_RF 0x00010000 /* Resume Flag. */
+#define FLAG_VM 0x00020000 /* Virtual 8086 Mode. */
+#define FLAG_AC 0x00040000 /* Alignment Check. */
+#define FLAG_VIF 0x00080000 /* Virtual Interrupt Flag. */
+#define FLAG_VIP 0x00100000 /* Virtual Interrupt Pending. */
+#define FLAG_ID 0x00200000 /* ID Flag. */
+
+/* Page fault error codes */
+#define FEC_PR 0x1 /* Page fault caused by protection violation */
+#define FEC_WR 0x2 /* Page fault caused by a write */
+#define FEC_U 0x4 /* Page fault occured while in user mode */
+
+
+/* Application segment type bits */
+#define STA_X 0x8 /* Executable segment */
+#define STA_A 0x1 /* Accessed */
+
+#define STA_C 0x4 /* Conforming code segment (executable only) */
+#define STA_R 0x2 /* Readable (executable segments) */
+
+#define STA_E 0x4 /* Expand down (non-executable segments) */
+#define STA_W 0x2 /* Writeable (non-executable segments) */
+
+
+/* Segment selectors. */
+#define SEL_NULL 0x00 /* Null selector. */
+#define SEL_KCSEG 0x08 /* Kernel code selector. */
+#define SEL_KDSEG 0x10 /* Kernel data selector. */
+#define SEL_UCSEG 0x18 /* Kernel code selector. */
+#define SEL_UDSEG 0x20 /* Kernel data selector. */
+#define SEL_TSS 0x28 /* Task-state segment. */
+#define SEL_CNT 6 /* Number of segments. */
+
+#ifndef __ASSEMBLER__
+struct tss
+ {
+ uint16_t back_link, :16;
+ uint32_t esp0;
+ uint16_t ss0, :16;
+ uint32_t esp1;
+ uint16_t ss1, :16;
+ uint32_t esp2;
+ uint16_t ss2, :16;
+ uint32_t cr3;
+ uint32_t eip;
+ uint32_t eflags;
+ uint32_t eax, ecx, edx, ebx;
+ uint32_t esp, ebp, esi, edi;
+ uint16_t es, :16;
+ uint16_t cs, :16;
+ uint16_t ss, :16;
+ uint16_t ds, :16;
+ uint16_t fs, :16;
+ uint16_t gs, :16;
+ uint16_t ldt, :16;
+ uint16_t trace, bitmap;
+ };
+
+enum seg_system
+ {
+ SYS_SYSTEM = 0, /* System segment. */
+ SYS_CODE_DATA = 1 /* Code or data segment. */
+ };
+
+enum seg_granularity
+ {
+ GRAN_BYTE = 0, /* Limit has 1-byte granularity. */
+ GRAN_PAGE = 1 /* Limit has 4 kB granularity. */
+ };
+
+enum seg_type
+ {
+ /* System segment types. */
+ TYPE_TSS_16_A = 1, /* 16-bit TSS (available). */
+ TYPE_LDT = 2, /* LDT. */
+ TYPE_TSS_16_B = 3, /* 16-bit TSS (busy). */
+ TYPE_CALL_16 = 4, /* 16-bit call gate. */
+ TYPE_TASK = 5, /* Task gate. */
+ TYPE_INT_16 = 6, /* 16-bit interrupt gate. */
+ TYPE_TRAP_16 = 7, /* 16-bit trap gate. */
+ TYPE_TSS_32_A = 9, /* 32-bit TSS (available). */
+ TYPE_TSS_32_B = 11, /* 32-bit TSS (busy). */
+ TYPE_CALL_32 = 12, /* 32-bit call gate. */
+ TYPE_INT_32 = 14, /* 32-bit interrupt gate. */
+ TYPE_TRAP_32 = 15, /* 32-bit trap gate. */
+
+ /* Code/data segment types. */
+ TYPE_CODE = 8, /* 1=Code segment, 0=data segment. */
+ TYPE_ACCESSED = 1, /* Set if accessed. */
+
+ /* Data segment types. */
+ TYPE_EXPAND_DOWN = 4, /* 1=Expands up, 0=expands down. */
+ TYPE_WRITABLE = 2, /* 1=Read/write, 0=read-only. */
+
+ /* Code segment types. */
+ TYPE_CONFORMING = 4, /* 1=Conforming, 0=nonconforming. */
+ TYPE_READABLE = 2 /* 1=Exec/read, 0=exec-only. */
+ };
+
+static inline uint64_t
+make_dtr_operand (uint16_t limit, void *base)
+{
+ return limit | ((uint64_t) (uint32_t) base << 16);
+}
+#endif
+
+#endif /* !_MMU_H_ */
--- /dev/null
+#include "palloc.h"
+#include <stddef.h>
+#include <stdint.h>
+#include <string.h>
+#include "debug.h"
+#include "mmu.h"
+
+/* A free page owned by the page allocator. */
+struct page
+ {
+ struct page *next; /* Next free page, or null at end of chain. */
+ };
+
+static struct page *free_pages;
+static uint8_t *uninit_start, *uninit_end;
+
+void
+palloc_init (uint8_t *start, uint8_t *end)
+{
+ uninit_start = start;
+ uninit_end = end;
+}
+
+void *
+palloc_get (enum palloc_flags flags)
+{
+ struct page *page;
+
+ if (free_pages == NULL && uninit_start < uninit_end)
+ {
+ palloc_free (uninit_start);
+ uninit_start += NBPG;
+ }
+
+ page = free_pages;
+ if (page != NULL)
+ {
+ free_pages = page->next;
+ if (flags & PAL_ZERO)
+ memset (page, 0, NBPG);
+ }
+ else
+ {
+ if (flags & PAL_ASSERT)
+ panic ("palloc_get: out of pages");
+ }
+
+ return page;
+}
+
+void
+palloc_free (void *page_)
+{
+ struct page *page = page_;
+ ASSERT((uintptr_t) page % NBPG == 0);
+#ifndef NDEBUG
+ memset (page, 0xcc, NBPG);
+#endif
+ page->next = free_pages;
+ free_pages = page;
+}
--- /dev/null
+#ifndef HEADER_PALLOC_H
+#define HEADER_PALLOC_H 1
+
+/* Page allocator. Hands out memory in page-size chunks.
+ See malloc.h for an allocator that hands out smaller
+ chunks. */
+
+#include <stdint.h>
+
+enum palloc_flags
+ {
+ PAL_ASSERT = 001, /* Panic on failure. */
+ PAL_ZERO = 002 /* Zero page contents. */
+ };
+
+void palloc_init (uint8_t *start, uint8_t *end);
+void *palloc_get (enum palloc_flags);
+void palloc_free (void *);
+
+#endif /* palloc.h */
--- /dev/null
+# This module gets linked first, so that the kernel entry point
+# is the very beginning of its binary image. All we need to do is
+# jump to the real entry point.
+
+ .globl start
+start: call main
+
+ # If main returns, spin.
+1: jmp 1b
--- /dev/null
+#### 0(%esp) - old registers
+#### 16(%esp) - return address
+#### 20(%esp) - current thread
+#### 24(%esp) - new thread
+
+ .globl thread_switch
+thread_switch:
+ # Save caller's register state.
+ # Note that the SVR4 ABI allows us to destroy %eax, %ecx, %edx.
+ # This stack frame must match the one set up by thread_create().
+ pushl %ebx
+ pushl %ebp
+ pushl %esi
+ pushl %edi
+
+ # Get offsetof (struct thread, stack).
+ .globl thread_stack_ofs
+ mov thread_stack_ofs, %edx
+
+ # Save current stack pointer to old thread's stack, if any.
+ movl 20(%esp), %eax
+ test %eax, %eax
+ jz 1f
+ movl %esp, (%eax,%edx,1)
+1:
+
+ # Restore stack pointer from new thread's stack.
+ movl 24(%esp), %ecx
+ movl (%ecx,%edx,1), %esp
+
+ # Restore caller's register state.
+ popl %edi
+ popl %esi
+ popl %ebp
+ popl %ebx
+ ret
--- /dev/null
+#include "synch.h"
+#include "interrupt.h"
+#include "lib.h"
+#include "malloc.h"
+#include "thread.h"
+
+/* One thread in a list. */
+struct thread_elem
+ {
+ struct list_elem elem;
+ struct thread *thread;
+ };
+
+/* Initializes semaphore SEMA to VALUE and names it NAME (for
+ debugging purposes only). A semaphore is a nonnegative
+ integer along with two atomic operators for manipulating it:
+
+ - down or "P": wait for the value to become positive, then
+ decrement it.
+
+ - up or "V": increment the value (and wake up one waiting
+ thread, if any). */
+void
+sema_init (struct semaphore *sema, unsigned value, const char *name)
+{
+ ASSERT (sema != NULL);
+ ASSERT (name != NULL);
+
+ strlcpy (sema->name, name, sizeof sema->name);
+ sema->value = value;
+ list_init (&sema->waiters);
+}
+
+/* Waits for SEMA's value to become positive and then
+ atomically decrements it.
+
+ This function may sleep, so it must not be called within an
+ interrupt handler. */
+void
+sema_down (struct semaphore *sema)
+{
+ enum if_level old_level;
+
+ ASSERT (sema != NULL);
+ ASSERT (!intr_context ());
+
+ old_level = intr_disable ();
+ while (sema->value == 0)
+ {
+ struct thread_elem te;
+ te.thread = thread_current ();
+ list_push_back (&sema->waiters, &te.elem);
+ thread_sleep ();
+ }
+ sema->value--;
+ intr_set_level (old_level);
+}
+
+/* Increments SEMA's value. Wakes up one thread of those waiting
+ for SEMA, if any.
+
+ This function may be called from an interrupt handler. */
+void
+sema_up (struct semaphore *sema)
+{
+ enum if_level old_level;
+
+ ASSERT (sema != NULL);
+
+ old_level = intr_disable ();
+ if (!list_empty (&sema->waiters))
+ thread_ready (list_entry (list_pop_front (&sema->waiters),
+ struct thread_elem, elem)->thread);
+ sema->value++;
+ intr_set_level (old_level);
+}
+
+/* Return SEMA's name (for debugging purposes). */
+const char *
+sema_name (const struct semaphore *sema)
+{
+ return sema->name;
+}
+
+static void
+sema_test_helper (void *sema_)
+{
+ struct semaphore *sema = sema_;
+ int i;
+
+ for (i = 0; i < 10; i++)
+ {
+ sema_down (&sema[0]);
+ sema_up (&sema[1]);
+ }
+}
+
+/* Self-test for semaphores that makes control "ping-pong"
+ between a pair of threads. Insert calls to printk() to see
+ what's going on. */
+void
+sema_self_test (void)
+{
+ struct thread *thread;
+ struct semaphore sema[2];
+ int i;
+
+ sema_init (&sema[0], 0, "ping");
+ sema_init (&sema[1], 0, "pong");
+ thread = thread_create ("sema-test", sema_test_helper, &sema);
+ for (i = 0; i < 10; i++)
+ {
+ sema_up (&sema[0]);
+ sema_down (&sema[1]);
+ }
+}
+\f
+/* Initializes LOCK and names it NAME (for debugging purposes).
+ A lock can be held by at most a single thread at any given
+ time. Our locks are not "recursive", meaning that it is an
+ error for a thread that holds a lock to attempt to reacquire
+ it.
+
+ A lock is a specialization of a semaphore with an initial
+ value of 1. The difference between a lock and such a
+ semaphore is twofold. First, a semaphore can have a value
+ greater than 1, but a lock can only be owned by a single
+ thread at a time. Second, a semaphore does not have an owner,
+ meaning that one thread can "down" the semaphore and then
+ another one "up" it, but with a lock the same thread must both
+ acquire and release it. When these restrictions prove
+ onerous, it's a good sign that a semaphore should be used,
+ instead of a lock. */
+void
+lock_init (struct lock *lock, const char *name)
+{
+ ASSERT (lock != NULL);
+ ASSERT (name != NULL);
+
+ strlcpy (lock->name, name, sizeof lock->name);
+ lock->holder = NULL;
+ sema_init (&lock->semaphore, 1, name);
+}
+
+/* Acquires LOCK, sleeping until it becomes available if
+ necessary. The lock must not already be held by the current
+ thread.
+
+ This function may sleep, so it must not be called within an
+ interrupt handler. */
+void
+lock_acquire (struct lock *lock)
+{
+ enum if_level old_level;
+
+ ASSERT (lock != NULL);
+ ASSERT (!intr_context ());
+ ASSERT (!lock_held_by_current_thread (lock));
+
+ old_level = intr_disable ();
+ sema_down (&lock->semaphore);
+ lock->holder = thread_current ();
+ intr_set_level (old_level);
+}
+
+/* Releases LOCK, which must be owned by the current thread.
+
+ An interrupt handler cannot acquire a lock, so it does not
+ make sense to try to signal a condition variable within an
+ interrupt handler. */
+void
+lock_release (struct lock *lock)
+{
+ enum if_level old_level;
+
+ ASSERT (lock != NULL);
+ ASSERT (lock_held_by_current_thread (lock));
+
+ old_level = intr_disable ();
+ lock->holder = NULL;
+ sema_up (&lock->semaphore);
+ intr_set_level (old_level);
+}
+
+/* Returns true if the current thread holds LOCK, false
+ otherwise. (Note that testing whether some other thread holds
+ a lock would be racy.) */
+bool
+lock_held_by_current_thread (const struct lock *lock)
+{
+ ASSERT (lock != NULL);
+
+ return lock->holder == thread_current ();
+}
+
+/* Returns the name of LOCK (for debugging purposes). */
+const char *
+lock_name (const struct lock *lock)
+{
+ ASSERT (lock != NULL);
+
+ return lock->name;
+}
+\f
+/* One semaphore in a list. */
+struct semaphore_elem
+ {
+ struct list_elem elem;
+ struct semaphore semaphore;
+ };
+
+/* Initializes condition variable COND and names it NAME. A
+ condition variable allows one piece of code to signal a
+ condition and cooperating code to receive the signal and act
+ upon it. */
+void
+cond_init (struct condition *cond, const char *name)
+{
+ ASSERT (cond != NULL);
+ ASSERT (name != NULL);
+
+ strlcpy (cond->name, name, sizeof cond->name);
+ list_init (&cond->waiters);
+}
+
+/* Atomically releases LOCK and waits for COND to be signaled by
+ some other piece of code. After COND is signalled, LOCK is
+ reacquired before returning. LOCK must be held before calling
+ this function.
+
+ The monitor implemented by this function is "Mesa" style, not
+ "Hoare" style. That is, sending a signal is not atomic with
+ delivering it. Thus, typically the caller must recheck the
+ condition after the wait completes and, if necessary, wait
+ again.
+
+ A given condition variable is associated with only a single
+ lock, but one lock may be be associated with any number of
+ condition variables. That is, there is a one-to-many mapping
+ from locks to condition variables.
+
+ This function may sleep, so it must not be called within an
+ interrupt handler. */
+void
+cond_wait (struct condition *cond, struct lock *lock)
+{
+ struct semaphore_elem waiter;
+
+ ASSERT (cond != NULL);
+ ASSERT (lock != NULL);
+ ASSERT (!intr_context ());
+ ASSERT (lock_held_by_current_thread (lock));
+
+ sema_init (&waiter.semaphore, 0, "condition");
+ list_push_back (&cond->waiters, &waiter.elem);
+ lock_release (lock);
+ sema_down (&waiter.semaphore);
+ lock_acquire (lock);
+}
+
+/* If any threads are waiting on COND (protected by LOCK), then
+ this function signals one of them to wake up from its wait.
+ LOCK must be held before calling this function.
+
+ An interrupt handler cannot acquire a lock, so it does not
+ make sense to try to signal a condition variable within an
+ interrupt handler. */
+void
+cond_signal (struct condition *cond, struct lock *lock)
+{
+ ASSERT (cond != NULL);
+ ASSERT (lock != NULL);
+ ASSERT (!intr_context ());
+ ASSERT (lock_held_by_current_thread (lock));
+
+ if (!list_empty (&cond->waiters))
+ sema_up (&list_entry (list_pop_front (&cond->waiters),
+ struct semaphore_elem, elem)->semaphore);
+}
+
+/* Wakes up all threads, if any, waiting on COND (protected by
+ LOCK). LOCK must be held before calling this function.
+
+ An interrupt handler cannot acquire a lock, so it does not
+ make sense to try to signal a condition variable within an
+ interrupt handler. */
+void
+cond_broadcast (struct condition *cond, struct lock *lock)
+{
+ ASSERT (cond != NULL);
+ ASSERT (lock != NULL);
+
+ while (!list_empty (&cond->waiters))
+ cond_signal (cond, lock);
+}
+
+/* Returns COND's name (for debugging purposes). */
+const char *
+cond_name (const struct condition *cond)
+{
+ ASSERT (cond != NULL);
+
+ return cond->name;
+}
--- /dev/null
+#ifndef HEADER_SYNCH_H
+#define HEADER_SYNCH_H 1
+
+#include <stdbool.h>
+#include "list.h"
+
+struct semaphore
+ {
+ char name[16];
+ unsigned value;
+ struct list waiters;
+ };
+
+void sema_init (struct semaphore *, unsigned value, const char *);
+void sema_down (struct semaphore *);
+void sema_up (struct semaphore *);
+const char *sema_name (const struct semaphore *);
+void sema_self_test (void);
+
+struct lock
+ {
+ char name[16];
+ struct thread *holder;
+ struct semaphore semaphore;
+ };
+
+void lock_init (struct lock *, const char *);
+void lock_acquire (struct lock *);
+void lock_release (struct lock *);
+bool lock_held_by_current_thread (const struct lock *);
+const char *lock_name (const struct lock *);
+
+struct condition
+ {
+ char name[16];
+ struct list waiters;
+ };
+
+void cond_init (struct condition *, const char *);
+void cond_wait (struct condition *, struct lock *);
+void cond_signal (struct condition *, struct lock *);
+void cond_broadcast (struct condition *, struct lock *);
+const char *cond_name (const struct condition *);
+
+#endif /* synch.h */
--- /dev/null
+#include "thread.h"
+#include <stddef.h>
+#include "debug.h"
+#include "interrupt.h"
+#include "lib.h"
+#include "mmu.h"
+#include "palloc.h"
+
+uint32_t thread_stack_ofs = offsetof (struct thread, stack);
+
+static struct list run_queue;
+
+struct thread *thread_switch (struct thread *cur, struct thread *next);
+
+void
+thread_init (void)
+{
+ list_init (&run_queue);
+}
+
+static void
+thread_root (void (*function) (void *aux), void *aux)
+{
+ ASSERT (function != NULL);
+
+ function (aux);
+ thread_exit ();
+}
+
+struct thread *
+thread_create (const char *name, void (*function) (void *aux), void *aux)
+{
+ struct thread *t;
+
+ ASSERT (name != NULL);
+ ASSERT (function != NULL);
+
+ t = palloc_get (0);
+ if (t == NULL)
+ return NULL;
+
+ memset (t, 0, NBPG);
+ strlcpy (t->name, name, sizeof t->name);
+
+ /* Set up stack. */
+ t->stack = (uint32_t *) ((uint8_t *) t + NBPG);
+ *--t->stack = (uint32_t) aux;
+ *--t->stack = (uint32_t) function;
+ --t->stack;
+ *--t->stack = (uint32_t) thread_root;
+ t->stack -= 4;
+
+ /* Add to run_queue. */
+ t->status = THREAD_BLOCKED;
+ thread_ready (t);
+
+ return t;
+}
+
+static struct thread *
+stack_to_thread (uint32_t *stack)
+{
+ return (struct thread *) ((uint32_t) (stack - 1) & ~((uint32_t) NBPG - 1));
+}
+
+struct thread *
+thread_current (void)
+{
+ uint32_t *esp;
+ asm ("movl %%esp, %0\n" : "=g" (esp));
+ return stack_to_thread (esp);
+}
+
+void
+thread_ready (struct thread *t)
+{
+ if (t->status != THREAD_READY)
+ {
+ list_push_back (&run_queue, &t->rq_elem);
+ t->status = THREAD_READY;
+ }
+}
+
+static struct thread *
+find_next_to_run (void)
+{
+ if (list_empty (&run_queue))
+ return NULL;
+ else
+ return list_entry (list_pop_front (&run_queue), struct thread, rq_elem);
+}
+
+static void
+idle (void)
+{
+ static int idle = 0;
+ if (idle++ == 0)
+ printk ("idle\n");
+}
+
+void
+thread_destroy (struct thread *t)
+{
+ ASSERT (t->status == THREAD_DYING);
+ ASSERT (t != thread_current ());
+
+ palloc_free (t);
+}
+
+void
+thread_schedule (void)
+{
+ struct thread *cur, *next, *prev;
+
+ cur = thread_current ();
+ ASSERT (cur->status != THREAD_RUNNING);
+
+ while ((next = find_next_to_run ()) == NULL)
+ idle ();
+
+ next->status = THREAD_RUNNING;
+ prev = thread_switch (cur, next);
+ if (prev != NULL && prev->status == THREAD_DYING)
+ thread_destroy (prev);
+}
+
+void
+thread_yield (void)
+{
+ ASSERT (!intr_context ());
+ thread_ready (thread_current ());
+ thread_schedule ();
+}
+
+void
+thread_start (struct thread *t)
+{
+ if (t->status == THREAD_READY)
+ list_remove (&t->rq_elem);
+ t->status = THREAD_RUNNING;
+ thread_switch (NULL, t);
+}
+
+void
+thread_exit (void)
+{
+ struct thread *t = thread_current ();
+ t->status = THREAD_DYING;
+ thread_schedule ();
+}
+
+void
+thread_sleep (void)
+{
+ ASSERT (intr_get_level () == IF_OFF);
+
+ thread_current ()->status = THREAD_BLOCKED;
+ thread_schedule ();
+}
--- /dev/null
+#ifndef HEADER_THREAD_H
+#define HEADER_THREAD_H 1
+
+#include <stdint.h>
+#include "list.h"
+
+enum thread_status
+ {
+ THREAD_RUNNING,
+ THREAD_READY,
+ THREAD_BLOCKED,
+ THREAD_DYING
+ };
+
+struct thread
+ {
+ enum thread_status status;
+ char name[16];
+ uint32_t *stack;
+ struct list_elem rq_elem;
+ };
+
+void thread_init (void);
+
+struct thread *thread_create (const char *name,
+ void (*function) (void *aux), void *aux);
+void thread_destroy (struct thread *);
+struct thread *thread_current (void);
+
+void thread_start (struct thread *);
+void thread_ready (struct thread *);
+void thread_exit (void);
+
+void thread_yield (void);
+void thread_sleep (void);
+void thread_schedule (void);
+
+#endif /* thread.h */
--- /dev/null
+DRIVETYPE ide
+#vm|VERSION 2
+#vm|TOOLSVERSION 0
+CYLINDERS 8
+HEADS 16
+SECTORS 63
+#vm|CAPACITY 8064
+ACCESS "bootdisk.bin" 0 8064
--- /dev/null
+#!/usr/bin/vmware
+config.version = "6"
+virtualHW.version = 2
+displayName = ""
+gui.powerOnAtStartUp = FALSE
+apmSuspend = FALSE
+suspendToDisk = TRUE
+gui.exitAtPowerOff = FALSE
+hard-disk.enableIBR = FALSE
+gui.fullScreenResize = TRUE
+resume.repeatable = FALSE
+disable_acceleration = FALSE
+guestOS = "linux"
+ide0:0.present = TRUE
+ide0:0.deviceType = "plainDisk"
+ide0:0.fileName = "bootdisk.pln"
+gui.fullScreenAtPowerOn = FALSE
+redoLogDir = ""
+logging = TRUE
+debug = FALSE
+uuid.location = "56 4d 89 06 87 3f cf 97-13 c7 37 a8 10 ca e8 69"
+
+floppy0.present = "false"
projects / pintos-anon / commitdiff