From 750d21936d284127e265d050ccbce76fca1ece1a Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Mon, 16 Aug 2004 21:45:04 +0000 Subject: [PATCH] Initial revision --- src/Makefile | 10 + src/Makefile.inc | 61 ++++ src/devices/16550a.h | 123 ++++++++ src/devices/kbd.c | 18 ++ src/devices/kbd.h | 6 + src/devices/serial.c | 39 +++ src/devices/serial.h | 9 + src/devices/timer.c | 53 ++++ src/devices/timer.h | 14 + src/devices/vga.c | 90 ++++++ src/devices/vga.h | 8 + src/lib/bitmap.c | 228 +++++++++++++++ src/lib/bitmap.h | 33 +++ src/lib/debug.c | 19 ++ src/lib/debug.h | 32 +++ src/lib/lib.c | 574 +++++++++++++++++++++++++++++++++++++ src/lib/lib.h | 29 ++ src/lib/list.c | 271 +++++++++++++++++ src/lib/list.h | 58 ++++ src/lib/random.c | 64 +++++ src/lib/random.h | 10 + src/threads/Makefile | 3 + src/threads/build/Makefile | 6 + src/threads/init.c | 223 ++++++++++++++ src/threads/interrupt.c | 266 +++++++++++++++++ src/threads/interrupt.h | 42 +++ src/threads/intr-stubs.pl | 50 ++++ src/threads/io.h | 94 ++++++ src/threads/kernel.lds | 34 +++ src/threads/loader.S | 169 +++++++++++ src/threads/malloc.c | 109 +++++++ src/threads/malloc.h | 12 + src/threads/mmu.h | 363 +++++++++++++++++++++++ src/threads/palloc.c | 61 ++++ src/threads/palloc.h | 20 ++ src/threads/start.S | 9 + src/threads/switch.S | 36 +++ src/threads/synch.c | 304 ++++++++++++++++++++ src/threads/synch.h | 45 +++ src/threads/thread.c | 159 ++++++++++ src/threads/thread.h | 38 +++ src/vmware/bootdisk.pln | 8 + src/vmware/nachos.vmx | 23 ++ src/vmware/nvram | Bin 0 -> 8664 bytes 44 files changed, 3823 insertions(+) create mode 100644 src/Makefile create mode 100644 src/Makefile.inc create mode 100644 src/devices/16550a.h create mode 100644 src/devices/kbd.c create mode 100644 src/devices/kbd.h create mode 100644 src/devices/serial.c create mode 100644 src/devices/serial.h create mode 100644 src/devices/timer.c create mode 100644 src/devices/timer.h create mode 100644 src/devices/vga.c create mode 100644 src/devices/vga.h create mode 100644 src/lib/bitmap.c create mode 100644 src/lib/bitmap.h create mode 100644 src/lib/debug.c create mode 100644 src/lib/debug.h create mode 100644 src/lib/lib.c create mode 100644 src/lib/lib.h create mode 100644 src/lib/list.c create mode 100644 src/lib/list.h create mode 100644 src/lib/random.c create mode 100644 src/lib/random.h create mode 100644 src/threads/Makefile create mode 100644 src/threads/build/Makefile create mode 100644 src/threads/init.c create mode 100644 src/threads/interrupt.c create mode 100644 src/threads/interrupt.h create mode 100755 src/threads/intr-stubs.pl create mode 100644 src/threads/io.h create mode 100644 src/threads/kernel.lds create mode 100644 src/threads/loader.S create mode 100644 src/threads/malloc.c create mode 100644 src/threads/malloc.h create mode 100644 src/threads/mmu.h create mode 100644 src/threads/palloc.c create mode 100644 src/threads/palloc.h create mode 100644 src/threads/start.S create mode 100644 src/threads/switch.S create mode 100644 src/threads/synch.c create mode 100644 src/threads/synch.h create mode 100644 src/threads/thread.c create mode 100644 src/threads/thread.h create mode 100644 src/vmware/bootdisk.pln create mode 100755 src/vmware/nachos.vmx create mode 100644 src/vmware/nvram diff --git a/src/Makefile b/src/Makefile new file mode 100644 index 0000000..72b234a --- /dev/null +++ b/src/Makefile @@ -0,0 +1,10 @@ +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 '{}' \; diff --git a/src/Makefile.inc b/src/Makefile.inc new file mode 100644 index 0000000..20e96d7 --- /dev/null +++ b/src/Makefile.inc @@ -0,0 +1,61 @@ +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 + + diff --git a/src/devices/16550a.h b/src/devices/16550a.h new file mode 100644 index 0000000..bce26f3 --- /dev/null +++ b/src/devices/16550a.h @@ -0,0 +1,123 @@ +#ifndef HEADER_16550A_H +#define HEADER_16550A_H 1 + +#include +#include +#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 */ diff --git a/src/devices/kbd.c b/src/devices/kbd.c new file mode 100644 index 0000000..21c98a5 --- /dev/null +++ b/src/devices/kbd.c @@ -0,0 +1,18 @@ +#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); +} diff --git a/src/devices/kbd.h b/src/devices/kbd.h new file mode 100644 index 0000000..f08ef74 --- /dev/null +++ b/src/devices/kbd.h @@ -0,0 +1,6 @@ +#ifndef HEADER_KBD_H +#define HEADER_KBD_H 1 + +void kbd_init (void); + +#endif /* kbd.h */ diff --git a/src/devices/serial.c b/src/devices/serial.c new file mode 100644 index 0000000..8d1633f --- /dev/null +++ b/src/devices/serial.c @@ -0,0 +1,39 @@ +#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); +} diff --git a/src/devices/serial.h b/src/devices/serial.h new file mode 100644 index 0000000..2b63800 --- /dev/null +++ b/src/devices/serial.h @@ -0,0 +1,9 @@ +#ifndef HEADER_SERIAL_H +#define HEADER_SERIAL_H 1 + +#include + +void serial_init (void); +void serial_outb (uint8_t); + +#endif /* serial.h */ diff --git a/src/devices/timer.c b/src/devices/timer.c new file mode 100644 index 0000000..67fe567 --- /dev/null +++ b/src/devices/timer.c @@ -0,0 +1,53 @@ +#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 */ +} diff --git a/src/devices/timer.h b/src/devices/timer.h new file mode 100644 index 0000000..4be2f48 --- /dev/null +++ b/src/devices/timer.h @@ -0,0 +1,14 @@ +#ifndef HEADER_TIMER_H +#define HEADER_TIMER_H 1 + +#include + +#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 */ diff --git a/src/devices/vga.c b/src/devices/vga.c new file mode 100644 index 0000000..7261fc4 --- /dev/null +++ b/src/devices/vga.c @@ -0,0 +1,90 @@ +#include "vga.h" +#include +#include +#include +#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 (); +} diff --git a/src/devices/vga.h b/src/devices/vga.h new file mode 100644 index 0000000..a859dea --- /dev/null +++ b/src/devices/vga.h @@ -0,0 +1,8 @@ +#ifndef HEADER_VGA_H +#define HEADER_VGA_H 1 + +void vga_init (void); +void vga_cls (void); +void vga_putc (int); + +#endif /* vga.h */ diff --git a/src/lib/bitmap.c b/src/lib/bitmap.c new file mode 100644 index 0000000..84a6ae4 --- /dev/null +++ b/src/lib/bitmap.c @@ -0,0 +1,228 @@ +#define NDEBUG +#include "bitmap.h" +#include +#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; +} diff --git a/src/lib/bitmap.h b/src/lib/bitmap.h new file mode 100644 index 0000000..50d8db6 --- /dev/null +++ b/src/lib/bitmap.h @@ -0,0 +1,33 @@ +#ifndef HEADER_BITMAP_H +#define HEADER_BITMAP_H 1 + +#include +#include + +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 */ diff --git a/src/lib/debug.c b/src/lib/debug.c new file mode 100644 index 0000000..577ab67 --- /dev/null +++ b/src/lib/debug.c @@ -0,0 +1,19 @@ +#include "debug.h" +#include +#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 (;;); +} diff --git a/src/lib/debug.h b/src/lib/debug.h new file mode 100644 index 0000000..1382473 --- /dev/null +++ b/src/lib/debug.h @@ -0,0 +1,32 @@ +#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 */ diff --git a/src/lib/lib.c b/src/lib/lib.c new file mode 100644 index 0000000..d439f5d --- /dev/null +++ b/src/lib/lib.c @@ -0,0 +1,574 @@ +#include +#include +#include +#include +#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); +} + +/* 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 ("<>", output, aux, *format); + break; + + default: + printf_core ("<>", output, aux, *format); + break; + } + } +} diff --git a/src/lib/lib.h b/src/lib/lib.h new file mode 100644 index 0000000..29dc17c --- /dev/null +++ b/src/lib/lib.h @@ -0,0 +1,29 @@ +#ifndef HEADER_LIB_H +#define HEADER_LIB_H 1 + +#include +#include + +#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 */ diff --git a/src/lib/list.c b/src/lib/list.c new file mode 100644 index 0000000..fbdbca7 --- /dev/null +++ b/src/lib/list.c @@ -0,0 +1,271 @@ +#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; +} diff --git a/src/lib/list.h b/src/lib/list.h new file mode 100644 index 0000000..e5f86f9 --- /dev/null +++ b/src/lib/list.h @@ -0,0 +1,58 @@ +#ifndef HEADER_LIST_H +#define HEADER_LIST_H 1 + +#include +#include +#include + +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 */ diff --git a/src/lib/random.c b/src/lib/random.c new file mode 100644 index 0000000..39452a9 --- /dev/null +++ b/src/lib/random.c @@ -0,0 +1,64 @@ +#include "random.h" +#include + +/* 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; +} diff --git a/src/lib/random.h b/src/lib/random.h new file mode 100644 index 0000000..d2f3706 --- /dev/null +++ b/src/lib/random.h @@ -0,0 +1,10 @@ +#ifndef HEADER_RANDOM_H +#define HEADER_RANDOM_H 1 + +#include + +void random_init (void); +void random_bytes (void *, size_t); +unsigned long random_ulong (void); + +#endif /* random.h */ diff --git a/src/threads/Makefile b/src/threads/Makefile new file mode 100644 index 0000000..495615d --- /dev/null +++ b/src/threads/Makefile @@ -0,0 +1,3 @@ +all: +%: + $(MAKE) -C build $@ diff --git a/src/threads/build/Makefile b/src/threads/build/Makefile new file mode 100644 index 0000000..293a2df --- /dev/null +++ b/src/threads/build/Makefile @@ -0,0 +1,6 @@ +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 + diff --git a/src/threads/init.c b/src/threads/init.c new file mode 100644 index 0000000..453543f --- /dev/null +++ b/src/threads/init.c @@ -0,0 +1,223 @@ +#include +#include +#include +#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)); +} + +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 (;;); +} diff --git a/src/threads/interrupt.c b/src/threads/interrupt.c new file mode 100644 index 0000000..f368385 --- /dev/null +++ b/src/threads/interrupt.c @@ -0,0 +1,266 @@ +#include "interrupt.h" +#include +#include "debug.h" +#include "io.h" +#include "lib.h" +#include "mmu.h" +#include "thread.h" +#include "timer.h" + +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; +} + +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); +} + +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 (;;); +} diff --git a/src/threads/interrupt.h b/src/threads/interrupt.h new file mode 100644 index 0000000..834d796 --- /dev/null +++ b/src/threads/interrupt.h @@ -0,0 +1,42 @@ +#ifndef HEADER_INTERRUPT_H +#define HEADER_INTERRUPT_H 1 + +#include +#include + +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); + +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 */ diff --git a/src/threads/intr-stubs.pl b/src/threads/intr-stubs.pl new file mode 100755 index 0000000..45f4fa3 --- /dev/null +++ b/src/threads/intr-stubs.pl @@ -0,0 +1,50 @@ +#! /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 diff --git a/src/threads/io.h b/src/threads/io.h new file mode 100644 index 0000000..f59c79e --- /dev/null +++ b/src/threads/io.h @@ -0,0 +1,94 @@ +#ifndef PORTIO_H +#define PORTIO_H 1 + +#include +#include + +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 */ diff --git a/src/threads/kernel.lds b/src/threads/kernel.lds new file mode 100644 index 0000000..d60fe0a --- /dev/null +++ b/src/threads/kernel.lds @@ -0,0 +1,34 @@ +/* ld script to make i386 Linux kernel + * Written by Martin Mares ; + */ +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 = . ; +} diff --git a/src/threads/loader.S b/src/threads/loader.S new file mode 100644 index 0000000..f2563bb --- /dev/null +++ b/src/threads/loader.S @@ -0,0 +1,169 @@ +#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 diff --git a/src/threads/malloc.c b/src/threads/malloc.c new file mode 100644 index 0000000..afa487c --- /dev/null +++ b/src/threads/malloc.c @@ -0,0 +1,109 @@ +#include "malloc.h" +#include +#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; +} diff --git a/src/threads/malloc.h b/src/threads/malloc.h new file mode 100644 index 0000000..2315312 --- /dev/null +++ b/src/threads/malloc.h @@ -0,0 +1,12 @@ +#ifndef HEADER_MALLOC_H +#define HEADER_MALLOC_H + +#include "debug.h" +#include + +void malloc_init (void); +void *malloc (size_t) + ATTRIBUTE ((malloc)); +void free (void *); + +#endif /* malloc.h */ diff --git a/src/threads/mmu.h b/src/threads/mmu.h new file mode 100644 index 0000000..4010964 --- /dev/null +++ b/src/threads/mmu.h @@ -0,0 +1,363 @@ +/* + * 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 +#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_ */ diff --git a/src/threads/palloc.c b/src/threads/palloc.c new file mode 100644 index 0000000..0fe5f94 --- /dev/null +++ b/src/threads/palloc.c @@ -0,0 +1,61 @@ +#include "palloc.h" +#include +#include +#include +#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; +} diff --git a/src/threads/palloc.h b/src/threads/palloc.h new file mode 100644 index 0000000..9bd076f --- /dev/null +++ b/src/threads/palloc.h @@ -0,0 +1,20 @@ +#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 + +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 */ diff --git a/src/threads/start.S b/src/threads/start.S new file mode 100644 index 0000000..351b5e1 --- /dev/null +++ b/src/threads/start.S @@ -0,0 +1,9 @@ +# 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 diff --git a/src/threads/switch.S b/src/threads/switch.S new file mode 100644 index 0000000..a7c27fb --- /dev/null +++ b/src/threads/switch.S @@ -0,0 +1,36 @@ +#### 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 diff --git a/src/threads/synch.c b/src/threads/synch.c new file mode 100644 index 0000000..39e43c3 --- /dev/null +++ b/src/threads/synch.c @@ -0,0 +1,304 @@ +#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]); + } +} + +/* 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; +} + +/* 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; +} diff --git a/src/threads/synch.h b/src/threads/synch.h new file mode 100644 index 0000000..e64bc6d --- /dev/null +++ b/src/threads/synch.h @@ -0,0 +1,45 @@ +#ifndef HEADER_SYNCH_H +#define HEADER_SYNCH_H 1 + +#include +#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 */ diff --git a/src/threads/thread.c b/src/threads/thread.c new file mode 100644 index 0000000..6793bb3 --- /dev/null +++ b/src/threads/thread.c @@ -0,0 +1,159 @@ +#include "thread.h" +#include +#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 (); +} diff --git a/src/threads/thread.h b/src/threads/thread.h new file mode 100644 index 0000000..b72c372 --- /dev/null +++ b/src/threads/thread.h @@ -0,0 +1,38 @@ +#ifndef HEADER_THREAD_H +#define HEADER_THREAD_H 1 + +#include +#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 */ diff --git a/src/vmware/bootdisk.pln b/src/vmware/bootdisk.pln new file mode 100644 index 0000000..f938675 --- /dev/null +++ b/src/vmware/bootdisk.pln @@ -0,0 +1,8 @@ +DRIVETYPE ide +#vm|VERSION 2 +#vm|TOOLSVERSION 0 +CYLINDERS 8 +HEADS 16 +SECTORS 63 +#vm|CAPACITY 8064 +ACCESS "bootdisk.bin" 0 8064 diff --git a/src/vmware/nachos.vmx b/src/vmware/nachos.vmx new file mode 100755 index 0000000..2ad2f05 --- /dev/null +++ b/src/vmware/nachos.vmx @@ -0,0 +1,23 @@ +#!/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" diff --git a/src/vmware/nvram b/src/vmware/nvram new file mode 100644 index 0000000000000000000000000000000000000000..1f393a4c544e5ae64d49a2f92ce2739032f12e68 GIT binary patch literal 8664 zcmeHNOH30%82P) z1wxEM6iqyMz(g-z?M32|cw%yjBXeARcfu4BsdNsCNTKY*nRYdB&vZQwRU%xr1>uBrh z?HJPGgX)~{FC60gKqOj~^B3x37cX6|Z-}=fTH6x)3jTL@rE^J*C)zs{)ki};CuW=^ zX#s^$P=X+~Z3Zwz$W?iel1ybms|X{YqydZ;Q6{2?GQb0liY$(ie?kQ}p*%xCIDlrk z7P%vCfdZBS2HkKW!Z{RBseu7k`!_<(!sn~{5{xC&$XLd-0agKi2D}Em7CZ_b1Fr{f z!dMa$caWI@e*yjyd>MtWQA`a8E3(^`z`C}rL!%IL4nDHZBn=27zG~Z+4iELZ=8VF>u7<^_K5+PvF;yk%CB$dp z;l`}jAVt6gee*?NKeVZw5>6W8>hr^>NEtg|_gP(3lI;}J29++ImxkiolZ>1zC9ZBf z?&>D5;HsyudAixtr22>~Ap%epb)Q=ZB1CikI7q}XEYiGh!YU)R1uM*qa)BW78-lb? ze|6Gngm$`lgoutYQ5|)w$@OH;MVBNlGcKQ-wry|G+s>EZ%YvD=Q_6je(i>1ji4@6z zWI!@-6d1@q0;QG=NCqSWk^#wpWI!@-00VMa<^W<2PgpL?(6W(SmXXUcN8#t49HV4F zGI019aK28+W$D8=aT2j)Kr-;h48+BM1H?m+IZwj;;jAhG)=Vy@F_pILu$&oM4(lXp zL9S7^X^)u&$}nnXS7w2YHCCH7^XE>7a~-iy)p?h8p(#bLwKp?v?9u7oo#bvyV2Q<| zyRhh#cClbQSGpgIuD|6fReXoPPGEUQu#n!}agRMv1$+(!U~3c}Iz{`M(W)`0Lfxz^ u{kpiP*u#=$6s=*=2*wpQHSpZ68Od(hy_M$2$!{M-ufHuGmV1H?G2UN56!xhA literal 0 HcmV?d00001 -- 2.30.2