From: Ben Pfaff Date: Mon, 6 Sep 2004 05:19:18 +0000 (+0000) Subject: Rename printk() to printf(). X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?p=pintos-anon;a=commitdiff_plain;h=f2f8875638593bd5365cfd6a5ba7c9578e52322f Rename printk() to printf(). Create user library by separating kernel library into kernel-specific and kernel-independent bits. Break up lib.c by standard header. Break up lib.h by standard header. Write our own standard headers for , etc., and stop using compiler include path. --- diff --git a/src/Makefile.build b/src/Makefile.build index 0a25309..8fe960a 100644 --- a/src/Makefile.build +++ b/src/Makefile.build @@ -6,13 +6,13 @@ SHELL = /bin/sh CC = gcc -SRC_ROOT = ../.. -VPATH = $(SRC_ROOT) +VPATH = ../.. +DEFINES += -DKERNEL WARNINGS = -Wall -W -Wstrict-prototypes -Wmissing-prototypes -INCLUDES = -I$(SRC_ROOT) +INCLUDES = -nostdinc -I../.. -I- -I../../lib -I../../lib/kernel CFLAGS = -g -O3 -MMD -msoft-float $(INCLUDES) $(WARNINGS) $(DEFINES) -ASFLAGS = -Wa,--gstabs $(INCLUDES) $(DEFINES) +ASFLAGS = -Wa,--gstabs -MMD $(INCLUDES) $(DEFINES) # Core kernel. threads_SRC = threads/init.c # Main program. @@ -33,13 +33,18 @@ devices_SRC += devices/vga.c # Video device. devices_SRC += devices/serial.c # Serial port device. devices_SRC += devices/disk.c # IDE disk device. -# Library code. +# Library code shared between kernel and user programs. lib_SRC = lib/debug.c # Debug helpers. -lib_SRC += lib/lib.c # Standard C library. lib_SRC += lib/random.c # Pseudo-random numbers. -lib_SRC += lib/list.c # Doubly-linked lists. -lib_SRC += lib/bitmap.c # Bitmaps. -lib_SRC += lib/hash.c # Hash tables. +lib_SRC += lib/stdio.c # I/O library. +lib_SRC += lib/stdlib.c # Utility functions. +lib_SRC += lib/string.c # String functions. + +# Kernel-specific library code. +lib_kernel_SRC += lib/kernel/list.c # Doubly-linked lists. +lib_kernel_SRC += lib/kernel/bitmap.c # Bitmaps. +lib_kernel_SRC += lib/kernel/hash.c # Hash tables. +lib_kernel_SRC += lib/kernel/printf.c # Kernel printf(). # Filesystem code. filesys_SRC = filesys/filesys.c # Filesystem core. @@ -55,7 +60,7 @@ userprog_SRC += userprog/syscall.c # System call handler. userprog_SRC += userprog/gdt.c # GDT initialization. userprog_SRC += userprog/tss.c # TSS management. -SOURCES = $(foreach dir,$(SUBDIRS),$($(dir)_SRC)) +SOURCES = $(foreach dir,$(SUBDIRS),$($(subst /,_,$(dir))_SRC)) OBJECTS = $(patsubst %.c,%.o,$(patsubst %.S,%.o,$(SOURCES))) DEPENDS = $(patsubst %.o,%.d,$(OBJECTS)) @@ -72,11 +77,11 @@ kernel.o: threads/kernel.lds.s $(OBJECTS) kernel.bin: kernel.o objcopy -O binary -R .note -R .comment -S $< $@.tmp - $(SRC_ROOT)/pad 4096 < $@.tmp > $@ + ../../pad 4096 < $@.tmp > $@ rm $@.tmp -threads/loader.o: threads/loader.S threads/loader.h kernel.bin - gcc -c $< -o $@ -DKERNEL_LOAD_PAGES=`perl -e 'print +(-s "kernel.bin") / 4096;'` +threads/loader.o: kernel.bin +threads/loader.o: DEFINES += -DKERNEL_LOAD_PAGES=`perl -e 'print +(-s "kernel.bin") / 4096;'` loader.bin: threads/loader.o ld -N -e start -Ttext 0x7c00 --oformat binary -o $@ $< diff --git a/src/Makefile.kernel b/src/Makefile.kernel index 9337203..92522fa 100644 --- a/src/Makefile.kernel +++ b/src/Makefile.kernel @@ -1,15 +1,17 @@ include Makefile.vars BUILD_SUBDIRS = $(addprefix build/, $(SUBDIRS)) +LN = ln +MKDIR = mkdir all: build build/Makefile $(BUILD_SUBDIRS) $(MAKE) -C build $(BUILD_SUBDIRS): - mkdir $@ + $(MKDIR) $@ build: - mkdir $@ + $(MKDIR) $@ build/Makefile: ../Makefile.build - cp $< $@ + $(LN) $< $@ clean: rm -rf build diff --git a/src/devices/16550a.h b/src/devices/16550a.h index 9a1e37d..b3cb37a 100644 --- a/src/devices/16550a.h +++ b/src/devices/16550a.h @@ -1,9 +1,9 @@ #ifndef HEADER_16550A_H #define HEADER_16550A_H 1 +#include #include #include -#include "lib/debug.h" /* Register definitions for the 16550A UART used in PCs. This is a full definition of all the registers and their bits. We diff --git a/src/devices/disk.c b/src/devices/disk.c index 9e4b9f5..d8bed65 100644 --- a/src/devices/disk.c +++ b/src/devices/disk.c @@ -1,8 +1,9 @@ -#include "disk.h" +#include "devices/disk.h" +#include +#include #include -#include "timer.h" -#include "lib/debug.h" -#include "lib/lib.h" +#include +#include "devices/timer.h" #include "threads/io.h" #include "threads/interrupt.h" #include "threads/synch.h" @@ -220,7 +221,7 @@ disk_write (struct disk *d, disk_sector_t sec_no, const void *buffer) /* Disk detection and identification. */ -static void printk_ata_string (char *string, size_t size); +static void print_ata_string (char *string, size_t size); /* Resets an ATA channel and waits for any devices present on it to finish the reset. */ @@ -341,28 +342,28 @@ identify_ata_device (struct disk *d) d->capacity = id[60] | ((uint32_t) id[61] << 16); /* Print identification message. */ - printk ("%s: detected %'"PRDSNu" sector (", d->name, d->capacity); + printf ("%s: detected %'"PRDSNu" sector (", d->name, d->capacity); if (d->capacity > 1024 / DISK_SECTOR_SIZE * 1024 * 1024) - printk ("%"PRDSNu" GB", + printf ("%"PRDSNu" GB", d->capacity / (1024 / DISK_SECTOR_SIZE * 1024 * 1024)); else if (d->capacity > 1024 / DISK_SECTOR_SIZE * 1024) - printk ("%"PRDSNu" MB", d->capacity / (1024 / DISK_SECTOR_SIZE * 1024)); + printf ("%"PRDSNu" MB", d->capacity / (1024 / DISK_SECTOR_SIZE * 1024)); else if (d->capacity > 1024 / DISK_SECTOR_SIZE) - printk ("%"PRDSNu" kB", d->capacity / (1024 / DISK_SECTOR_SIZE)); + printf ("%"PRDSNu" kB", d->capacity / (1024 / DISK_SECTOR_SIZE)); else - printk ("%"PRDSNu" byte", d->capacity * DISK_SECTOR_SIZE); - printk (") disk, model \""); - printk_ata_string ((char *) &id[27], 40); - printk ("\", serial \""); - printk_ata_string ((char *) &id[10], 20); - printk ("\"\n"); + printf ("%"PRDSNu" byte", d->capacity * DISK_SECTOR_SIZE); + printf (") disk, model \""); + print_ata_string ((char *) &id[27], 40); + printf ("\", serial \""); + print_ata_string ((char *) &id[10], 20); + printf ("\"\n"); } /* Prints STRING, which consists of SIZE bytes in a funky format: each pair of bytes is in reverse order. Does not print trailing whitespace and/or nulls. */ static void -printk_ata_string (char *string, size_t size) +print_ata_string (char *string, size_t size) { size_t i; @@ -376,7 +377,7 @@ printk_ata_string (char *string, size_t size) /* Print. */ for (i = 0; i < size; i++) - printk ("%c", string[i ^ 1]); + printf ("%c", string[i ^ 1]); } /* Selects device D, waiting for it to become ready, and then @@ -447,7 +448,7 @@ wait_until_idle (const struct disk *d) timer_usleep (10); } - printk ("%s: idle timeout\n", d->name); + printf ("%s: idle timeout\n", d->name); } /* Wait up to 30 seconds for disk D to clear BSY, @@ -463,17 +464,17 @@ wait_while_busy (const struct disk *d) for (i = 0; i < 3000; i++) { if (i == 700) - printk ("%s: busy, waiting...", d->name); + printf ("%s: busy, waiting...", d->name); if (!(inb (reg_alt_status (c)) & STA_BSY)) { if (i >= 700) - printk ("ok\n"); + printf ("ok\n"); return (inb (reg_alt_status (c)) & STA_DRQ) != 0; } timer_msleep (10); } - printk ("failed\n"); + printf ("failed\n"); return false; } @@ -515,7 +516,7 @@ interrupt_handler (struct intr_frame *f) sema_up (&c->completion_wait); /* Wake up waiter. */ } else - printk ("%s: unexpected interrupt\n", c->name); + printf ("%s: unexpected interrupt\n", c->name); return; } diff --git a/src/devices/disk.h b/src/devices/disk.h index d149682..9e785e5 100644 --- a/src/devices/disk.h +++ b/src/devices/disk.h @@ -11,8 +11,8 @@ Good enough for disks up to 2 TB. */ typedef uint32_t disk_sector_t; -/* Format specifier for printk(), e.g.: - printk ("sector=%"PRDSNu"\n", sector); */ +/* Format specifier for printf(), e.g.: + printf ("sector=%"PRDSNu"\n", sector); */ #define PRDSNu PRIu32 void disk_init (void); diff --git a/src/devices/kbd.c b/src/devices/kbd.c index 867c64a..bcfe2c8 100644 --- a/src/devices/kbd.c +++ b/src/devices/kbd.c @@ -1,13 +1,13 @@ -#include "kbd.h" -#include "lib/debug.h" -#include "lib/lib.h" +#include "devices/kbd.h" +#include +#include #include "threads/interrupt.h" #include "threads/io.h" static void irq21_keyboard (struct intr_frame *args UNUSED) { - printk ("Keyboard!\n"); + printf ("Keyboard!\n"); inb (0x60); } diff --git a/src/devices/serial.c b/src/devices/serial.c index eeac40a..41b52f6 100644 --- a/src/devices/serial.c +++ b/src/devices/serial.c @@ -1,7 +1,7 @@ -#include "serial.h" -#include "16550a.h" -#include "timer.h" -#include "lib/debug.h" +#include "devices/serial.h" +#include +#include "devices/16550a.h" +#include "devices/timer.h" #include "threads/io.h" static void set_serial (int bps, int bits, enum parity_type parity, int stop); diff --git a/src/devices/timer.c b/src/devices/timer.c index 85bc3ee..1706201 100644 --- a/src/devices/timer.c +++ b/src/devices/timer.c @@ -1,5 +1,5 @@ -#include "timer.h" -#include "lib/debug.h" +#include "devices/timer.h" +#include #include "threads/interrupt.h" #include "threads/io.h" diff --git a/src/devices/vga.c b/src/devices/vga.c index fcdc689..bc2d6b7 100644 --- a/src/devices/vga.c +++ b/src/devices/vga.c @@ -1,7 +1,8 @@ -#include "vga.h" +#include "devices/vga.h" +#include #include #include -#include "lib/lib.h" +#include #include "threads/io.h" #include "threads/mmu.h" diff --git a/src/filesys/Makefile.vars b/src/filesys/Makefile.vars index db29a74..03e8f08 100644 --- a/src/filesys/Makefile.vars +++ b/src/filesys/Makefile.vars @@ -1,2 +1,2 @@ DEFINES = -DUSERPROG -DFILESYS -SUBDIRS = threads devices lib userprog filesys +SUBDIRS = threads devices lib lib/kernel userprog filesys diff --git a/src/filesys/directory.c b/src/filesys/directory.c index 32911b8..fba32f0 100644 --- a/src/filesys/directory.c +++ b/src/filesys/directory.c @@ -1,7 +1,8 @@ -#include "directory.h" -#include "file.h" -#include "fsutil.h" -#include "lib/lib.h" +#include "filesys/directory.h" +#include +#include +#include "filesys/file.h" +#include "filesys/fsutil.h" #include "threads/malloc.h" /* Initializes D as a directory that holds ENTRY_CNT entries. */ @@ -160,7 +161,7 @@ dir_list (const struct dir *d) for (e = d->entries; e < d->entries + d->entry_cnt; e++) if (e->in_use) - printk ("%s\n", e->name); + printf ("%s\n", e->name); } /* Dumps the contents of D, including its files' names and their @@ -173,8 +174,8 @@ dir_dump (const struct dir *d) for (e = d->entries; e < d->entries + d->entry_cnt; e++) if (e->in_use) { - printk ("Contents of %s:\n", e->name); + printf ("Contents of %s:\n", e->name); fsutil_print (e->name); - printk ("\n"); + printf ("\n"); } } diff --git a/src/filesys/file.c b/src/filesys/file.c index a40c073..e1a70f3 100644 --- a/src/filesys/file.c +++ b/src/filesys/file.c @@ -1,9 +1,9 @@ -#include "file.h" -#include "directory.h" -#include "filehdr.h" -#include "filesys.h" -#include "lib/debug.h" -#include "lib/lib.h" +#include "filesys/file.h" +#include +#include +#include "filesys/directory.h" +#include "filesys/filehdr.h" +#include "filesys/filesys.h" #include "threads/malloc.h" bool diff --git a/src/filesys/file.h b/src/filesys/file.h index afa1990..28495c2 100644 --- a/src/filesys/file.h +++ b/src/filesys/file.h @@ -5,7 +5,7 @@ #include #include #include "devices/disk.h" -#include "off_t.h" +#include "filesys/off_t.h" struct file { diff --git a/src/filesys/filehdr.c b/src/filesys/filehdr.c index eafe211..5817912 100644 --- a/src/filesys/filehdr.c +++ b/src/filesys/filehdr.c @@ -1,8 +1,8 @@ -#include "filehdr.h" -#include "filesys.h" -#include "lib/bitmap.h" -#include "lib/debug.h" -#include "lib/lib.h" +#include "filesys/filehdr.h" +#include +#include +#include +#include "filesys/filesys.h" #include "threads/malloc.h" /* Allocates sectors from bitmap B for the content of a file @@ -122,7 +122,7 @@ filehdr_print (const struct filehdr *h) { size_t i; - printk ("File header: %jd bytes, %zd sectors (", + printf ("File header: %jd bytes, %zd sectors (", (intmax_t) h->length, h->sector_cnt); /* This loop could be unsafe for large h->sector_cnt, can you @@ -130,8 +130,8 @@ filehdr_print (const struct filehdr *h) for (i = 0; i < h->sector_cnt; i++) { if (i != 0) - printk (", "); - printk ("%jd", (intmax_t) h->sectors[i]); + printf (", "); + printf ("%jd", (intmax_t) h->sectors[i]); } - printk (")\n"); + printf (")\n"); } diff --git a/src/filesys/filehdr.h b/src/filesys/filehdr.h index cb28416..7c9f37f 100644 --- a/src/filesys/filehdr.h +++ b/src/filesys/filehdr.h @@ -3,7 +3,7 @@ #include #include -#include "off_t.h" +#include "filesys/off_t.h" #include "devices/disk.h" /* Number of direct sector pointers in a file header. */ diff --git a/src/filesys/filesys.c b/src/filesys/filesys.c index 77284ad..c0e3938 100644 --- a/src/filesys/filesys.c +++ b/src/filesys/filesys.c @@ -26,14 +26,15 @@ MODIFICATIONS. */ -#include "filesys.h" -#include "file.h" -#include "filehdr.h" -#include "directory.h" +#include "filesys/filesys.h" +#include +#include +#include +#include +#include "filesys/file.h" +#include "filesys/filehdr.h" +#include "filesys/directory.h" #include "devices/disk.h" -#include "lib/bitmap.h" -#include "lib/debug.h" -#include "lib/lib.h" /* Filesystem. @@ -276,13 +277,13 @@ filesys_dump (void) struct bitmap free_map; struct dir dir; - printk ("Free map:\n"); + printf ("Free map:\n"); if (!bitmap_init (&free_map, disk_size (filesys_disk))) return false; bitmap_read (&free_map, &free_map_file); bitmap_dump (&free_map); bitmap_destroy (&free_map); - printk ("\n"); + printf ("\n"); if (!dir_init (&dir, NUM_DIR_ENTRIES)) return false; @@ -322,7 +323,7 @@ filesys_self_test (void) MUST_SUCCEED (filesys_remove ("foo")); - printk ("filesys: self test ok\n"); + printf ("filesys: self test ok\n"); } /* Formats the filesystem. */ @@ -333,7 +334,7 @@ do_format (void) struct filehdr *map_hdr, *dir_hdr; struct dir dir; - printk ("Formatting filesystem..."); + printf ("Formatting filesystem..."); /* Create the initial bitmap and reserve sectors for the free map and root directory file headers. */ @@ -375,7 +376,7 @@ do_format (void) dir_destroy (&dir); file_close (&free_map_file); - printk ("done.\n"); + printf ("done.\n"); } /* If SUCCESS is false, panics with an error complaining about diff --git a/src/filesys/filesys.h b/src/filesys/filesys.h index 1f06c34..6e6c136 100644 --- a/src/filesys/filesys.h +++ b/src/filesys/filesys.h @@ -3,7 +3,7 @@ #include #include -#include "off_t.h" +#include "filesys/off_t.h" /* Disk used for filesystem. */ extern struct disk *filesys_disk; diff --git a/src/filesys/fsutil.c b/src/filesys/fsutil.c index 6598785..a51fac6 100644 --- a/src/filesys/fsutil.c +++ b/src/filesys/fsutil.c @@ -1,9 +1,11 @@ -#include "fsutil.h" +#include "filesys/fsutil.h" +#include #include -#include "file.h" -#include "filesys.h" -#include "lib/debug.h" -#include "lib/lib.h" +#include +#include +#include +#include "filesys/file.h" +#include "filesys/filesys.h" #include "threads/mmu.h" #include "threads/palloc.h" @@ -88,7 +90,7 @@ fsutil_run (void) if (fsutil_remove_file != NULL) { if (filesys_remove (fsutil_remove_file)) - printk ("%s: removed\n", fsutil_remove_file); + printf ("%s: removed\n", fsutil_remove_file); else PANIC ("%s: remove failed\n", fsutil_remove_file); } diff --git a/src/lib/bitmap.c b/src/lib/bitmap.c deleted file mode 100644 index 0be0379..0000000 --- a/src/lib/bitmap.c +++ /dev/null @@ -1,299 +0,0 @@ -#include "bitmap.h" -#include -#include "debug.h" -#include "lib.h" -#include "threads/malloc.h" -#ifdef FILESYS -#include "filesys/file.h" -#endif - -/* Number of bits in an element. */ -#define ELEM_BITS (sizeof (elem_type) * CHAR_BIT) - -/* Returns the index of the element that contains the bit - numbered BIT_IDX. */ -static inline size_t -elem_idx (size_t bit_idx) -{ - return bit_idx / ELEM_BITS; -} - -/* Returns an elem_type where only the bit corresponding to - BIT_IDX is turned on. */ -static inline elem_type -bit_mask (size_t bit_idx) -{ - return (elem_type) 1 << (bit_idx % ELEM_BITS); -} - -/* Returns the number of elements required for B's bits. */ -static inline size_t -elem_cnt (const struct bitmap *b) -{ - return DIV_ROUND_UP (b->bit_cnt, ELEM_BITS); -} - -/* Returns the number of bytes required by B's elements. */ -static inline size_t -byte_cnt (const struct bitmap *b) -{ - return sizeof (elem_type) * elem_cnt (b); -} - -/* Returns a bit mask in which the bits actually used in the last - element of B's bits are set to 1 and the rest are set to 0. */ -static inline elem_type -last_mask (const struct bitmap *b) -{ - int last_bits = b->bit_cnt % ELEM_BITS; - return last_bits ? ((elem_type) 1 << last_bits) - 1 : (elem_type) -1; -} - -/* Initializes B to be a bitmap of BIT_CNT bits. - Returns true if successfalse, false if memory allocation - failed. */ -bool -bitmap_init (struct bitmap *b, size_t bit_cnt) -{ - b->bit_cnt = bit_cnt; - b->bits = malloc (byte_cnt (b)); - if (b->bits == NULL && bit_cnt > 0) - return false; - - bitmap_set_all (b, false); - return true; -} - -/* Destroys bitmap B, freeing its storage. */ -void -bitmap_destroy (struct bitmap *b) -{ - ASSERT (b); - - free (b->bits); -} - -/* Returns the number of bits in B. */ -size_t -bitmap_size (const struct bitmap *b) -{ - return b->bit_cnt; -} - -/* Sets the bit numbered IDX in B to VALUE. */ -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); -} - -/* Sets all bits in B to VALUE. */ -void -bitmap_set_all (struct bitmap *b, bool value) -{ - size_t i; - - ASSERT (b != NULL); - - if (b->bit_cnt > 0) - { - for (i = 0; i < elem_cnt (b); i++) - b->bits[i] = value ? (elem_type) -1 : 0; - b->bits[elem_cnt (b) - 1] &= last_mask (b); - } -} - -/* Sets the bit numbered IDX in B to true. */ -void -bitmap_mark (struct bitmap *b, size_t idx) -{ - bitmap_set (b, idx, true); -} - -/* Sets the bit numbered IDX in B to false. */ -void -bitmap_reset (struct bitmap *b, size_t idx) -{ - bitmap_set (b, idx, false); -} - -/* Toggles the bit numbered IDX in B; - that is, if it is true, makes it false, - and if it is false, makes it true. */ -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); -} - -/* Returns the value of the bit numbered IDX in B. */ -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; -} - -/* Returns the smallest index of a bit set to VALUE in B. - If no bits in B are set to VALUE, returns BITMAP_ERROR. */ -size_t -bitmap_scan (const struct bitmap *b, bool value) -{ - elem_type ignore = value ? 0 : (elem_type) -1; - size_t idx; - - ASSERT (b != NULL); - for (idx = 0; idx < elem_cnt (b); idx++) - { - elem_type e = b->bits[idx]; - if (e != ignore) - { - idx *= ELEM_BITS; - - while ((e & 1) != value) - { - e >>= 1; - idx++; - } - - return idx < b->bit_cnt ? idx : BITMAP_ERROR; - } - } - return BITMAP_ERROR; -} - -/* Finds the smallest index of a bit set to false in B, - sets it to true, and returns the index. - If no bits in B are set to false, changes no bits and - returns 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; -} - -/* Finds the smallest index of a bit set to true in B, - sets it to false, and returns the index. - If no bits in B are set to true, changes no bits and - returns BITMAP_ERROR. */ -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; -} - -/* Returns the number of bits in B set to true. */ -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; -} - -/* Returns true if any bits in B are set to true, - and false otherwise.*/ -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; -} - -/* Returns the number of bits in B set to false. */ -bool -bitmap_clear_cnt (const struct bitmap *b) -{ - return b->bit_cnt - bitmap_set_cnt (b); -} - -/* Returns true if no bits in B are set to true, - and false otherwise.*/ -bool -bitmap_none (const struct bitmap *b) -{ - return !bitmap_any (b); -} - -/* Returns true if every bit in B is set to true, - and false otherwise. */ -bool -bitmap_all (const struct bitmap *b) -{ - 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 false; - return b->bits[i] == last_mask (b); -} - -#ifdef FILESYS -/* Returns the number of bytes needed to store B in a file. */ -size_t -bitmap_file_size (const struct bitmap *b) -{ - return byte_cnt (b); -} - -/* Reads FILE into B, ignoring errors. */ -void -bitmap_read (struct bitmap *b, struct file *file) -{ - if (b->bit_cnt > 0) - { - file_read_at (file, b->bits, byte_cnt (b), 0); - b->bits[elem_cnt (b) - 1] &= last_mask (b); - } -} - -/* Writes FILE to B, ignoring errors. */ -void -bitmap_write (const struct bitmap *b, struct file *file) -{ - file_write_at (file, b->bits, byte_cnt (b), 0); -} -#endif /* FILESYS */ - -/* Dumps the contents of B to the console as hexadecimal. */ -void -bitmap_dump (const struct bitmap *b) -{ - hex_dump (b->bits, byte_cnt (b), false); -} diff --git a/src/lib/bitmap.h b/src/lib/bitmap.h deleted file mode 100644 index ada1354..0000000 --- a/src/lib/bitmap.h +++ /dev/null @@ -1,63 +0,0 @@ -#ifndef HEADER_BITMAP_H -#define HEADER_BITMAP_H 1 - -#include -#include - -/* Bitmap abstract data type. */ - -/* Element type. - - This must be an unsigned integer type at least as wide as int. - - Each bit represents one bit in the bitmap. - If bit 0 in an element represents bit K in the bitmap, - then bit 1 in the element represents bit K+1 in the bitmap, - and so on. */ -typedef unsigned long elem_type; - -/* From the outside, a bitmap is an array of bits. From the - inside, it's an array of elem_type (defined above) that - simulates an array of bits. */ -struct bitmap - { - size_t bit_cnt; /* Number of bits. */ - elem_type *bits; /* Elements that represent bits. */ - }; - -bool bitmap_init (struct bitmap *, 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 *); - -#ifdef FILESYS -struct file; -size_t bitmap_file_size (const struct bitmap *); -void bitmap_read (struct bitmap *, struct file *); -void bitmap_write (const struct bitmap *, struct file *); -#endif - -void bitmap_dump (const struct bitmap *); - -#endif /* bitmap.h */ diff --git a/src/lib/ctype.h b/src/lib/ctype.h new file mode 100644 index 0000000..fafa51f --- /dev/null +++ b/src/lib/ctype.h @@ -0,0 +1,24 @@ +#ifndef LIB_CTYPE_H +#define LIB_CTYPE_H 1 + +static inline int islower (int c) { return c >= 'a' && c <= 'z'; } +static inline int isupper (int c) { return c >= 'A' && c <= 'Z'; } +static inline int isalpha (int c) { return islower (c) || isupper (c); } +static inline int isdigit (int c) { return c >= '0' && c <= '9'; } +static inline int isalnum (int c) { return isalpha (c) || isdigit (c); } +static inline int isxdigit (int c) { + return isdigit (c) || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F'); +} +static inline int isspace (int c) { + return (c == ' ' || c == '\f' || c == '\n' + || c == '\r' || c == '\t' || c == '\v'); +} +static inline int isgraph (int c) { return c >= 33 && c < 127; } +static inline int isprint (int c) { return c >= 32 && c < 127; } +static inline int iscntrl (int c) { return c >= 0 && c < 32; } +static inline int isascii (int c) { return c >= 0 && c < 128; } +static inline int ispunct (int c) { + return isprint (c) && !isalnum (c) && !isspace (c); +} + +#endif /* lib/ctype.h */ diff --git a/src/lib/debug.c b/src/lib/debug.c index babf229..2082eed 100644 --- a/src/lib/debug.c +++ b/src/lib/debug.c @@ -1,7 +1,14 @@ -#include "debug.h" +#include #include -#include "lib.h" +#include +#include +#include +#include +#ifdef KERNEL #include "threads/interrupt.h" +#else +#include +#endif #define MAX_CLASSES 16 static bool all_enabled; @@ -39,13 +46,17 @@ debug_message (const char *file, int line, const char *function, { va_list args; +#ifdef KERNEL enum intr_level old_level = intr_disable (); - printk ("%s:%d: %s(): ", file, line, function); +#endif + printf ("%s:%d: %s(): ", file, line, function); va_start (args, message); - vprintk (message, args); - printk ("\n"); + vprintf (message, args); + printf ("\n"); va_end (args); +#ifdef KERNEL intr_set_level (old_level); +#endif } } @@ -57,34 +68,40 @@ debug_panic (const char *file, int line, const char *function, { va_list args; +#ifdef KERNEL intr_disable (); +#endif - printk ("PANIC at %s:%d in %s(): ", file, line, function); + printf ("PANIC at %s:%d in %s(): ", file, line, function); va_start (args, message); - vprintk (message, args); - printk ("\n"); + vprintf (message, args); + printf ("\n"); va_end (args); debug_backtrace (); +#ifdef KERNEL for (;;); +#else + exit (1); +#endif } -/* Prints the call stack, that is, a list of addresses in each of - the functions we are nested within. gdb or addr2line may be - applied to kernel.o to translate these into file names, line - numbers, and function names. */ +/* Prints the call stack, that is, a list of addresses, one in + each of the functions we are nested within. gdb or addr2line + may be applied to kernel.o to translate these into file names, + line numbers, and function names. */ void debug_backtrace (void) { void **frame; - printk ("Call stack:"); + printf ("Call stack:"); for (frame = __builtin_frame_address (0); frame != NULL && frame[0] != NULL; frame = frame[0]) - printk (" %p", frame[1]); - printk (".\n"); + printf (" %p", frame[1]); + printf (".\n"); } diff --git a/src/lib/hash.c b/src/lib/hash.c deleted file mode 100644 index a6b18a9..0000000 --- a/src/lib/hash.c +++ /dev/null @@ -1,347 +0,0 @@ -#include "hash.h" -#include "debug.h" -#include "threads/malloc.h" - -static struct list *find_bucket (struct hash *, hash_elem *); -static struct list_elem *find_elem (struct hash *, struct list *, hash_elem *); -static void insert_elem (struct hash *, struct list *, hash_elem *); -static void remove_elem (struct hash *, hash_elem *); -static void rehash (struct hash *); - -/* Initializes hash table H to compute hash values using HASH and - compare hash elements using LESS, given auxiliary data AUX. */ -bool -hash_init (struct hash *h, - hash_hash_func *hash, hash_less_func *less, void *aux) -{ - h->elem_cnt = 0; - h->bucket_cnt = 4; - h->buckets = malloc (sizeof *h->buckets * h->bucket_cnt); - h->hash = hash; - h->less = less; - h->aux = aux; - - if (h->buckets != NULL) - { - hash_clear (h); - return true; - } - else - return false; -} - -/* Removes all the elements from H. */ -void -hash_clear (struct hash *h) -{ - size_t i; - - for (i = 0; i < h->bucket_cnt; h++) - list_init (&h->buckets[i]); - h->elem_cnt = 0; -} - -/* Destroys hash table H. */ -void -hash_destroy (struct hash *h) -{ - free (h->buckets); -} - -/* Inserts NEW into hash table H and returns a null pointer, if - no equal element is already in the table. - If an equal element is already in the table, returns it - without inserting NEW. */ -hash_elem * -hash_insert (struct hash *h, hash_elem *new) -{ - struct list *bucket = find_bucket (h, new); - struct list_elem *old = find_elem (h, bucket, new); - - if (old == NULL) - insert_elem (h, bucket, new); - return old; -} - -/* Inserts NEW into hash table H, replacing any equal element - already in the table, which is returned. */ -hash_elem * -hash_replace (struct hash *h, hash_elem *new) -{ - struct list *bucket = find_bucket (h, new); - struct list_elem *old = find_elem (h, bucket, new); - - if (old != NULL) - remove_elem (h, old); - - insert_elem (h, bucket, new); - return old; -} - -/* Finds and returns an element equal to E in hash table H, or a - null pointer if no equal element exists in the table. */ -hash_elem * -hash_find (struct hash *h, hash_elem *e) -{ - return find_elem (h, find_bucket (h, e), e); -} - -/* Finds, removes, and returns an element equal to E in hash - table H. Returns a null pointer if no equal element existed - in the table. */ -hash_elem * -hash_delete (struct hash *h, hash_elem *e) -{ - struct list_elem *found = find_elem (h, find_bucket (h, e), e); - if (found != NULL) - remove_elem (h, found); - return found; -} - -/* Initializes I for iterating hash table H. - - Iteration idiom: - - struct hash_iterator i; - - hash_first (&i, h); - while (hash_next (&i, h)) - { - struct foo *f = list_entry (hash_cur (&i), struct foo, elem); - ...do something with f... - } - - NOTE: Modifying a hash table during iteration invalidates all - iterators. -*/ -void -hash_first (struct hash_iterator *i, struct hash *h) -{ - ASSERT (i != NULL); - ASSERT (h != NULL); - - i->hash = h; - i->bucket = i->hash->buckets; - i->elem = list_head (i->bucket); -} - -/* Advances I to the next element in the hash table and returns - it. Returns a null pointer if no elements are left. Elements - are returned in arbitrary order. - - NOTE: Modifying a hash table during iteration invalidates all - iterators. */ -hash_elem * -hash_next (struct hash_iterator *i) -{ - ASSERT (i != NULL); - - i->elem = list_next (i->elem); - while (i->elem == list_end (i->bucket)) - { - if (++i->bucket >= i->hash->buckets + i->hash->bucket_cnt) - { - i->elem = NULL; - break; - } - i->elem = list_begin (i->bucket); - } - - return i->elem; -} - -/* Returns the current element in the hash table iteration, or a - null pointer at the end of the table. Undefined behavior - after calling hash_first() but before hash_next(). */ -hash_elem * -hash_cur (struct hash_iterator *i) -{ - return i->elem; -} - -/* Returns the number of elements in H. */ -size_t -hash_size (struct hash *h) -{ - return h->elem_cnt; -} - -/* Returns true if H contains no elements, false otherwise. */ -bool -hash_empty (struct hash *h) -{ - return h->elem_cnt == 0; -} - -/* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */ -#define FNV_32_PRIME 16777619u -#define FNV_32_BASIS 2166136261u - -/* Returns a hash of the SIZE bytes in BUF. */ -unsigned -hash_bytes (const void *buf_, size_t size) -{ - /* Fowler-Noll-Vo 32-bit hash, for bytes. */ - const unsigned char *buf = buf_; - unsigned hash; - - ASSERT (buf != NULL); - - hash = FNV_32_BASIS; - while (size-- > 0) - hash = (hash * FNV_32_PRIME) ^ *buf++; - - return hash; -} - -/* Returns a hash of string S. */ -unsigned -hash_string (const char *s_) -{ - const unsigned char *s = s_; - unsigned hash; - - ASSERT (s != NULL); - - hash = FNV_32_BASIS; - while (*s != '\0') - hash = (hash * FNV_32_PRIME) ^ *s++; - - return hash; -} - -/* Returns a hash of integer I. */ -unsigned -hash_int (int i) -{ - return hash_bytes (&i, sizeof i); -} - -/* Returns the bucket in H that E belongs in. */ -static struct list * -find_bucket (struct hash *h, hash_elem *e) -{ - size_t bucket_idx = h->hash (e, h->aux) & (h->bucket_cnt - 1); - return &h->buckets[bucket_idx]; -} - -/* Searches BUCKET in H for a hash element equal to E. Returns - it if found or a null pointer otherwise. */ -static struct list_elem * -find_elem (struct hash *h, struct list *bucket, hash_elem *e) -{ - struct list_elem *i; - - for (i = list_begin (bucket); i != list_end (bucket); i = list_next (i)) - if (!h->less (i, e, h->aux) && !h->less (e, i, h->aux)) - return i; - return NULL; -} - -/* Returns X with its lowest-order bit set to 1 turned off. */ -static inline size_t -turn_off_least_1bit (size_t x) -{ - return x & (x - 1); -} - -/* Returns true if X is a power of 2, otherwise false. */ -static inline size_t -is_power_of_2 (size_t x) -{ - return x != 0 && turn_off_least_1bit (x) == 0; -} - -/* Element per bucket ratios. */ -#define MIN_ELEMS_PER_BUCKET 1 /* Elems/bucket < 1: reduce # of buckets. */ -#define BEST_ELEMS_PER_BUCKET 2 /* Ideal elems/bucket. */ -#define MAX_ELEMS_PER_BUCKET 4 /* Elems/bucket > 4: increase # of buckets. */ - -/* Changes the number of buckets in hash table H to match the - ideal. This function can fail because of an out-of-memory - condition, but that'll just make hash accesses less efficient; - we can still continue. */ -static void -rehash (struct hash *h) -{ - size_t old_bucket_cnt, new_bucket_cnt; - struct list *new_buckets, *old_buckets; - size_t i; - - ASSERT (h != NULL); - - /* Save old bucket info for later use. */ - old_buckets = h->buckets; - old_bucket_cnt = h->bucket_cnt; - - /* Calculate the number of buckets to use now. - We want one bucket for about every BEST_ELEMS_PER_BUCKET. - We must have at least four buckets, and the number of - buckets must be a power of 2. */ - new_bucket_cnt = h->elem_cnt / BEST_ELEMS_PER_BUCKET; - if (new_bucket_cnt < 4) - new_bucket_cnt = 4; - while (!is_power_of_2 (new_bucket_cnt)) - new_bucket_cnt = turn_off_least_1bit (new_bucket_cnt); - - /* Don't do anything if the bucket count wouldn't change. */ - if (new_bucket_cnt == old_bucket_cnt) - return; - - /* Allocate new buckets and initialize them as empty. */ - new_buckets = malloc (sizeof *new_buckets * new_bucket_cnt); - if (new_buckets == NULL) - { - /* Allocation failed. This means that use of the hash table will - be less efficient. However, it is still usable, so - there's no reason for it to be an error. */ - return; - } - for (i = 0; i < new_bucket_cnt; i++) - list_init (&new_buckets[i]); - - /* Install new bucket info. */ - h->buckets = new_buckets; - h->bucket_cnt = new_bucket_cnt; - - /* Move each old element into the appropriate new bucket. */ - for (i = 0; i < old_bucket_cnt; i++) - { - struct list *old_bucket; - struct list_elem *elem, *next; - - old_bucket = &old_buckets[i]; - for (elem = list_begin (old_bucket); - elem != list_end (old_bucket); elem = next) - { - struct list *new_bucket = find_bucket (h, elem); - next = list_next (elem); - list_push_front (new_bucket, elem); - } - } -} - -/* Inserts E into BUCKET (in hash table H). - Rehashes if this increases elems/bucket above - MAX_ELEMS_PER_BUCKET. */ -static void -insert_elem (struct hash *h, struct list *bucket, hash_elem *e) -{ - h->elem_cnt++; - if (h->elem_cnt > h->bucket_cnt * MAX_ELEMS_PER_BUCKET) - rehash (h); - list_push_front (bucket, e); -} - -/* Removes E from hash table H. - Rehashes if this decreases elems/bucket below - MIN_ELEMS_PER_BUCKET. */ -static void -remove_elem (struct hash *h, hash_elem *e) -{ - h->elem_cnt--; - if (h->elem_cnt < h->bucket_cnt * MIN_ELEMS_PER_BUCKET) - rehash (h); - list_remove (e); -} - diff --git a/src/lib/hash.h b/src/lib/hash.h deleted file mode 100644 index e37592b..0000000 --- a/src/lib/hash.h +++ /dev/null @@ -1,91 +0,0 @@ -#ifndef HEADER_HASH_H -#define HEADER_HASH_H 1 - -/* Hash table. - - This is a standard hash table with chaining. To locate an - element in the table, we compute a hash function over the - element's data and use that as an index into an array of - doubly linked lists, then linearly search the list. - - The chain lists do not use dynamic allocation. Instead, each - structure that can potentially be in a hash must embed a - hash_elem member. All of the hash functions operate on these - `hash_elem's. The hash_entry macro allows conversion from a - hash_elem back to a structure object that contains it. - - - -*/ - -#include -#include -#include -#include "list.h" - -/* Hash element. */ -typedef list_elem hash_elem; - -/* Converts pointer to hash element HASH_ELEM into a pointer to - the structure that HASH_ELEM is embedded inside. Supply the - name of the outer structure STRUCT and the member name MEMBER - of the hash element. See the big comment at the top of the - file for an example. */ -#define hash_entry(HASH_ELEM, STRUCT, MEMBER) \ - ((STRUCT *) ((uint8_t *) (HASH_ELEM) - offsetof (STRUCT, MEMBER))) - -/* Computes and returns the hash value for hash element E, given - auxiliary data AUX. */ -typedef unsigned hash_hash_func (const hash_elem *e, void *aux); - -/* Compares the value of two hash elements A and B, given - auxiliary data AUX. Returns true if A is less than B, or - false if A is greater than or equal to B. */ -typedef bool hash_less_func (const hash_elem *a, const hash_elem *b, - void *aux); - -/* Hash table. */ -struct hash - { - size_t elem_cnt; /* Number of elements in table. */ - size_t bucket_cnt; /* Number of buckets, a power of 2. */ - struct list *buckets; /* Array of `bucket_cnt' lists. */ - hash_hash_func *hash; /* Hash function. */ - hash_less_func *less; /* Comparison function. */ - void *aux; /* Auxiliary data for `hash' and `less'. */ - }; - -/* A hash table iterator. */ -struct hash_iterator - { - struct hash *hash; /* The hash table. */ - struct list *bucket; /* Current bucket. */ - hash_elem *elem; /* Current hash element in current bucket. */ - }; - -/* Basic life cycle. */ -bool hash_init (struct hash *, hash_hash_func *, hash_less_func *, void *aux); -void hash_clear (struct hash *); -void hash_destroy (struct hash *); - -/* Search, insertion, deletion. */ -hash_elem *hash_insert (struct hash *, hash_elem *); -hash_elem *hash_replace (struct hash *, hash_elem *); -hash_elem *hash_find (struct hash *, hash_elem *); -hash_elem *hash_delete (struct hash *, hash_elem *); - -/* Iteration. */ -void hash_first (struct hash_iterator *, struct hash *); -hash_elem *hash_next (struct hash_iterator *); -hash_elem *hash_cur (struct hash_iterator *); - -/* Information. */ -size_t hash_size (struct hash *); -bool hash_empty (struct hash *); - -/* Sample hash functions. */ -unsigned hash_bytes (const void *, size_t); -unsigned hash_string (const char *); -unsigned hash_int (int); - -#endif /* hash.h */ diff --git a/src/lib/inttypes.h b/src/lib/inttypes.h new file mode 100644 index 0000000..70bb898 --- /dev/null +++ b/src/lib/inttypes.h @@ -0,0 +1,48 @@ +#ifndef LIB_INTTYPES_H +#define LIB_INTTYPES_H + +#define PRId8 "hhd" +#define PRId16 "hd" +#define PRId32 "d" +#define PRId64 "lld" + +#define PRIi8 "hhi" +#define PRIi16 "hi" +#define PRIi32 "i" +#define PRIi64 "lli" + +#define PRIo8 "hho" +#define PRIo16 "ho" +#define PRIo32 "o" +#define PRIo64 "llo" + +#define PRIu8 "hhu" +#define PRIu16 "hu" +#define PRIu32 "u" +#define PRIu64 "llu" + +#define PRIx8 "hhx" +#define PRIx16 "hx" +#define PRIx32 "x" +#define PRIx64 "llx" + +#define PRIX8 "hhX" +#define PRIX16 "hX" +#define PRIX32 "X" +#define PRIX64 "llX" + +#define PRIdMAX "lld" +#define PRIiMAX "lli" +#define PRIoMAX "llo" +#define PRIuMAX "llu" +#define PRIxMAX "llx" +#define PRIXMAX "llX" + +#define PRIdPTR "d" +#define PRIiPTR "i" +#define PRIoPTR "o" +#define PRIuPTR "u" +#define PRIxPTR "x" +#define PRIXPTR "X" + +#endif /* lib/inttypes.h */ diff --git a/src/lib/kernel/bitmap.c b/src/lib/kernel/bitmap.c new file mode 100644 index 0000000..7bbc928 --- /dev/null +++ b/src/lib/kernel/bitmap.c @@ -0,0 +1,300 @@ +#include "bitmap.h" +#include +#include +#include +#include +#include "threads/malloc.h" +#ifdef FILESYS +#include "filesys/file.h" +#endif + +/* Number of bits in an element. */ +#define ELEM_BITS (sizeof (elem_type) * CHAR_BIT) + +/* Returns the index of the element that contains the bit + numbered BIT_IDX. */ +static inline size_t +elem_idx (size_t bit_idx) +{ + return bit_idx / ELEM_BITS; +} + +/* Returns an elem_type where only the bit corresponding to + BIT_IDX is turned on. */ +static inline elem_type +bit_mask (size_t bit_idx) +{ + return (elem_type) 1 << (bit_idx % ELEM_BITS); +} + +/* Returns the number of elements required for B's bits. */ +static inline size_t +elem_cnt (const struct bitmap *b) +{ + return DIV_ROUND_UP (b->bit_cnt, ELEM_BITS); +} + +/* Returns the number of bytes required by B's elements. */ +static inline size_t +byte_cnt (const struct bitmap *b) +{ + return sizeof (elem_type) * elem_cnt (b); +} + +/* Returns a bit mask in which the bits actually used in the last + element of B's bits are set to 1 and the rest are set to 0. */ +static inline elem_type +last_mask (const struct bitmap *b) +{ + int last_bits = b->bit_cnt % ELEM_BITS; + return last_bits ? ((elem_type) 1 << last_bits) - 1 : (elem_type) -1; +} + +/* Initializes B to be a bitmap of BIT_CNT bits. + Returns true if successfalse, false if memory allocation + failed. */ +bool +bitmap_init (struct bitmap *b, size_t bit_cnt) +{ + b->bit_cnt = bit_cnt; + b->bits = malloc (byte_cnt (b)); + if (b->bits == NULL && bit_cnt > 0) + return false; + + bitmap_set_all (b, false); + return true; +} + +/* Destroys bitmap B, freeing its storage. */ +void +bitmap_destroy (struct bitmap *b) +{ + ASSERT (b); + + free (b->bits); +} + +/* Returns the number of bits in B. */ +size_t +bitmap_size (const struct bitmap *b) +{ + return b->bit_cnt; +} + +/* Sets the bit numbered IDX in B to VALUE. */ +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); +} + +/* Sets all bits in B to VALUE. */ +void +bitmap_set_all (struct bitmap *b, bool value) +{ + size_t i; + + ASSERT (b != NULL); + + if (b->bit_cnt > 0) + { + for (i = 0; i < elem_cnt (b); i++) + b->bits[i] = value ? (elem_type) -1 : 0; + b->bits[elem_cnt (b) - 1] &= last_mask (b); + } +} + +/* Sets the bit numbered IDX in B to true. */ +void +bitmap_mark (struct bitmap *b, size_t idx) +{ + bitmap_set (b, idx, true); +} + +/* Sets the bit numbered IDX in B to false. */ +void +bitmap_reset (struct bitmap *b, size_t idx) +{ + bitmap_set (b, idx, false); +} + +/* Toggles the bit numbered IDX in B; + that is, if it is true, makes it false, + and if it is false, makes it true. */ +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); +} + +/* Returns the value of the bit numbered IDX in B. */ +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; +} + +/* Returns the smallest index of a bit set to VALUE in B. + If no bits in B are set to VALUE, returns BITMAP_ERROR. */ +size_t +bitmap_scan (const struct bitmap *b, bool value) +{ + elem_type ignore = value ? 0 : (elem_type) -1; + size_t idx; + + ASSERT (b != NULL); + for (idx = 0; idx < elem_cnt (b); idx++) + { + elem_type e = b->bits[idx]; + if (e != ignore) + { + idx *= ELEM_BITS; + + while ((e & 1) != value) + { + e >>= 1; + idx++; + } + + return idx < b->bit_cnt ? idx : BITMAP_ERROR; + } + } + return BITMAP_ERROR; +} + +/* Finds the smallest index of a bit set to false in B, + sets it to true, and returns the index. + If no bits in B are set to false, changes no bits and + returns 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; +} + +/* Finds the smallest index of a bit set to true in B, + sets it to false, and returns the index. + If no bits in B are set to true, changes no bits and + returns BITMAP_ERROR. */ +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; +} + +/* Returns the number of bits in B set to true. */ +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; +} + +/* Returns true if any bits in B are set to true, + and false otherwise.*/ +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; +} + +/* Returns the number of bits in B set to false. */ +bool +bitmap_clear_cnt (const struct bitmap *b) +{ + return b->bit_cnt - bitmap_set_cnt (b); +} + +/* Returns true if no bits in B are set to true, + and false otherwise.*/ +bool +bitmap_none (const struct bitmap *b) +{ + return !bitmap_any (b); +} + +/* Returns true if every bit in B is set to true, + and false otherwise. */ +bool +bitmap_all (const struct bitmap *b) +{ + 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 false; + return b->bits[i] == last_mask (b); +} + +#ifdef FILESYS +/* Returns the number of bytes needed to store B in a file. */ +size_t +bitmap_file_size (const struct bitmap *b) +{ + return byte_cnt (b); +} + +/* Reads FILE into B, ignoring errors. */ +void +bitmap_read (struct bitmap *b, struct file *file) +{ + if (b->bit_cnt > 0) + { + file_read_at (file, b->bits, byte_cnt (b), 0); + b->bits[elem_cnt (b) - 1] &= last_mask (b); + } +} + +/* Writes FILE to B, ignoring errors. */ +void +bitmap_write (const struct bitmap *b, struct file *file) +{ + file_write_at (file, b->bits, byte_cnt (b), 0); +} +#endif /* FILESYS */ + +/* Dumps the contents of B to the console as hexadecimal. */ +void +bitmap_dump (const struct bitmap *b) +{ + hex_dump (b->bits, byte_cnt (b), false); +} diff --git a/src/lib/kernel/bitmap.h b/src/lib/kernel/bitmap.h new file mode 100644 index 0000000..ada1354 --- /dev/null +++ b/src/lib/kernel/bitmap.h @@ -0,0 +1,63 @@ +#ifndef HEADER_BITMAP_H +#define HEADER_BITMAP_H 1 + +#include +#include + +/* Bitmap abstract data type. */ + +/* Element type. + + This must be an unsigned integer type at least as wide as int. + + Each bit represents one bit in the bitmap. + If bit 0 in an element represents bit K in the bitmap, + then bit 1 in the element represents bit K+1 in the bitmap, + and so on. */ +typedef unsigned long elem_type; + +/* From the outside, a bitmap is an array of bits. From the + inside, it's an array of elem_type (defined above) that + simulates an array of bits. */ +struct bitmap + { + size_t bit_cnt; /* Number of bits. */ + elem_type *bits; /* Elements that represent bits. */ + }; + +bool bitmap_init (struct bitmap *, 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 *); + +#ifdef FILESYS +struct file; +size_t bitmap_file_size (const struct bitmap *); +void bitmap_read (struct bitmap *, struct file *); +void bitmap_write (const struct bitmap *, struct file *); +#endif + +void bitmap_dump (const struct bitmap *); + +#endif /* bitmap.h */ diff --git a/src/lib/kernel/hash.c b/src/lib/kernel/hash.c new file mode 100644 index 0000000..3c0243b --- /dev/null +++ b/src/lib/kernel/hash.c @@ -0,0 +1,347 @@ +#include "hash.h" +#include "../debug.h" +#include "threads/malloc.h" + +static struct list *find_bucket (struct hash *, hash_elem *); +static struct list_elem *find_elem (struct hash *, struct list *, hash_elem *); +static void insert_elem (struct hash *, struct list *, hash_elem *); +static void remove_elem (struct hash *, hash_elem *); +static void rehash (struct hash *); + +/* Initializes hash table H to compute hash values using HASH and + compare hash elements using LESS, given auxiliary data AUX. */ +bool +hash_init (struct hash *h, + hash_hash_func *hash, hash_less_func *less, void *aux) +{ + h->elem_cnt = 0; + h->bucket_cnt = 4; + h->buckets = malloc (sizeof *h->buckets * h->bucket_cnt); + h->hash = hash; + h->less = less; + h->aux = aux; + + if (h->buckets != NULL) + { + hash_clear (h); + return true; + } + else + return false; +} + +/* Removes all the elements from H. */ +void +hash_clear (struct hash *h) +{ + size_t i; + + for (i = 0; i < h->bucket_cnt; h++) + list_init (&h->buckets[i]); + h->elem_cnt = 0; +} + +/* Destroys hash table H. */ +void +hash_destroy (struct hash *h) +{ + free (h->buckets); +} + +/* Inserts NEW into hash table H and returns a null pointer, if + no equal element is already in the table. + If an equal element is already in the table, returns it + without inserting NEW. */ +hash_elem * +hash_insert (struct hash *h, hash_elem *new) +{ + struct list *bucket = find_bucket (h, new); + struct list_elem *old = find_elem (h, bucket, new); + + if (old == NULL) + insert_elem (h, bucket, new); + return old; +} + +/* Inserts NEW into hash table H, replacing any equal element + already in the table, which is returned. */ +hash_elem * +hash_replace (struct hash *h, hash_elem *new) +{ + struct list *bucket = find_bucket (h, new); + struct list_elem *old = find_elem (h, bucket, new); + + if (old != NULL) + remove_elem (h, old); + + insert_elem (h, bucket, new); + return old; +} + +/* Finds and returns an element equal to E in hash table H, or a + null pointer if no equal element exists in the table. */ +hash_elem * +hash_find (struct hash *h, hash_elem *e) +{ + return find_elem (h, find_bucket (h, e), e); +} + +/* Finds, removes, and returns an element equal to E in hash + table H. Returns a null pointer if no equal element existed + in the table. */ +hash_elem * +hash_delete (struct hash *h, hash_elem *e) +{ + struct list_elem *found = find_elem (h, find_bucket (h, e), e); + if (found != NULL) + remove_elem (h, found); + return found; +} + +/* Initializes I for iterating hash table H. + + Iteration idiom: + + struct hash_iterator i; + + hash_first (&i, h); + while (hash_next (&i, h)) + { + struct foo *f = list_entry (hash_cur (&i), struct foo, elem); + ...do something with f... + } + + NOTE: Modifying a hash table during iteration invalidates all + iterators. +*/ +void +hash_first (struct hash_iterator *i, struct hash *h) +{ + ASSERT (i != NULL); + ASSERT (h != NULL); + + i->hash = h; + i->bucket = i->hash->buckets; + i->elem = list_head (i->bucket); +} + +/* Advances I to the next element in the hash table and returns + it. Returns a null pointer if no elements are left. Elements + are returned in arbitrary order. + + NOTE: Modifying a hash table during iteration invalidates all + iterators. */ +hash_elem * +hash_next (struct hash_iterator *i) +{ + ASSERT (i != NULL); + + i->elem = list_next (i->elem); + while (i->elem == list_end (i->bucket)) + { + if (++i->bucket >= i->hash->buckets + i->hash->bucket_cnt) + { + i->elem = NULL; + break; + } + i->elem = list_begin (i->bucket); + } + + return i->elem; +} + +/* Returns the current element in the hash table iteration, or a + null pointer at the end of the table. Undefined behavior + after calling hash_first() but before hash_next(). */ +hash_elem * +hash_cur (struct hash_iterator *i) +{ + return i->elem; +} + +/* Returns the number of elements in H. */ +size_t +hash_size (struct hash *h) +{ + return h->elem_cnt; +} + +/* Returns true if H contains no elements, false otherwise. */ +bool +hash_empty (struct hash *h) +{ + return h->elem_cnt == 0; +} + +/* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */ +#define FNV_32_PRIME 16777619u +#define FNV_32_BASIS 2166136261u + +/* Returns a hash of the SIZE bytes in BUF. */ +unsigned +hash_bytes (const void *buf_, size_t size) +{ + /* Fowler-Noll-Vo 32-bit hash, for bytes. */ + const unsigned char *buf = buf_; + unsigned hash; + + ASSERT (buf != NULL); + + hash = FNV_32_BASIS; + while (size-- > 0) + hash = (hash * FNV_32_PRIME) ^ *buf++; + + return hash; +} + +/* Returns a hash of string S. */ +unsigned +hash_string (const char *s_) +{ + const unsigned char *s = s_; + unsigned hash; + + ASSERT (s != NULL); + + hash = FNV_32_BASIS; + while (*s != '\0') + hash = (hash * FNV_32_PRIME) ^ *s++; + + return hash; +} + +/* Returns a hash of integer I. */ +unsigned +hash_int (int i) +{ + return hash_bytes (&i, sizeof i); +} + +/* Returns the bucket in H that E belongs in. */ +static struct list * +find_bucket (struct hash *h, hash_elem *e) +{ + size_t bucket_idx = h->hash (e, h->aux) & (h->bucket_cnt - 1); + return &h->buckets[bucket_idx]; +} + +/* Searches BUCKET in H for a hash element equal to E. Returns + it if found or a null pointer otherwise. */ +static struct list_elem * +find_elem (struct hash *h, struct list *bucket, hash_elem *e) +{ + struct list_elem *i; + + for (i = list_begin (bucket); i != list_end (bucket); i = list_next (i)) + if (!h->less (i, e, h->aux) && !h->less (e, i, h->aux)) + return i; + return NULL; +} + +/* Returns X with its lowest-order bit set to 1 turned off. */ +static inline size_t +turn_off_least_1bit (size_t x) +{ + return x & (x - 1); +} + +/* Returns true if X is a power of 2, otherwise false. */ +static inline size_t +is_power_of_2 (size_t x) +{ + return x != 0 && turn_off_least_1bit (x) == 0; +} + +/* Element per bucket ratios. */ +#define MIN_ELEMS_PER_BUCKET 1 /* Elems/bucket < 1: reduce # of buckets. */ +#define BEST_ELEMS_PER_BUCKET 2 /* Ideal elems/bucket. */ +#define MAX_ELEMS_PER_BUCKET 4 /* Elems/bucket > 4: increase # of buckets. */ + +/* Changes the number of buckets in hash table H to match the + ideal. This function can fail because of an out-of-memory + condition, but that'll just make hash accesses less efficient; + we can still continue. */ +static void +rehash (struct hash *h) +{ + size_t old_bucket_cnt, new_bucket_cnt; + struct list *new_buckets, *old_buckets; + size_t i; + + ASSERT (h != NULL); + + /* Save old bucket info for later use. */ + old_buckets = h->buckets; + old_bucket_cnt = h->bucket_cnt; + + /* Calculate the number of buckets to use now. + We want one bucket for about every BEST_ELEMS_PER_BUCKET. + We must have at least four buckets, and the number of + buckets must be a power of 2. */ + new_bucket_cnt = h->elem_cnt / BEST_ELEMS_PER_BUCKET; + if (new_bucket_cnt < 4) + new_bucket_cnt = 4; + while (!is_power_of_2 (new_bucket_cnt)) + new_bucket_cnt = turn_off_least_1bit (new_bucket_cnt); + + /* Don't do anything if the bucket count wouldn't change. */ + if (new_bucket_cnt == old_bucket_cnt) + return; + + /* Allocate new buckets and initialize them as empty. */ + new_buckets = malloc (sizeof *new_buckets * new_bucket_cnt); + if (new_buckets == NULL) + { + /* Allocation failed. This means that use of the hash table will + be less efficient. However, it is still usable, so + there's no reason for it to be an error. */ + return; + } + for (i = 0; i < new_bucket_cnt; i++) + list_init (&new_buckets[i]); + + /* Install new bucket info. */ + h->buckets = new_buckets; + h->bucket_cnt = new_bucket_cnt; + + /* Move each old element into the appropriate new bucket. */ + for (i = 0; i < old_bucket_cnt; i++) + { + struct list *old_bucket; + struct list_elem *elem, *next; + + old_bucket = &old_buckets[i]; + for (elem = list_begin (old_bucket); + elem != list_end (old_bucket); elem = next) + { + struct list *new_bucket = find_bucket (h, elem); + next = list_next (elem); + list_push_front (new_bucket, elem); + } + } +} + +/* Inserts E into BUCKET (in hash table H). + Rehashes if this increases elems/bucket above + MAX_ELEMS_PER_BUCKET. */ +static void +insert_elem (struct hash *h, struct list *bucket, hash_elem *e) +{ + h->elem_cnt++; + if (h->elem_cnt > h->bucket_cnt * MAX_ELEMS_PER_BUCKET) + rehash (h); + list_push_front (bucket, e); +} + +/* Removes E from hash table H. + Rehashes if this decreases elems/bucket below + MIN_ELEMS_PER_BUCKET. */ +static void +remove_elem (struct hash *h, hash_elem *e) +{ + h->elem_cnt--; + if (h->elem_cnt < h->bucket_cnt * MIN_ELEMS_PER_BUCKET) + rehash (h); + list_remove (e); +} + diff --git a/src/lib/kernel/hash.h b/src/lib/kernel/hash.h new file mode 100644 index 0000000..e37592b --- /dev/null +++ b/src/lib/kernel/hash.h @@ -0,0 +1,91 @@ +#ifndef HEADER_HASH_H +#define HEADER_HASH_H 1 + +/* Hash table. + + This is a standard hash table with chaining. To locate an + element in the table, we compute a hash function over the + element's data and use that as an index into an array of + doubly linked lists, then linearly search the list. + + The chain lists do not use dynamic allocation. Instead, each + structure that can potentially be in a hash must embed a + hash_elem member. All of the hash functions operate on these + `hash_elem's. The hash_entry macro allows conversion from a + hash_elem back to a structure object that contains it. + + + +*/ + +#include +#include +#include +#include "list.h" + +/* Hash element. */ +typedef list_elem hash_elem; + +/* Converts pointer to hash element HASH_ELEM into a pointer to + the structure that HASH_ELEM is embedded inside. Supply the + name of the outer structure STRUCT and the member name MEMBER + of the hash element. See the big comment at the top of the + file for an example. */ +#define hash_entry(HASH_ELEM, STRUCT, MEMBER) \ + ((STRUCT *) ((uint8_t *) (HASH_ELEM) - offsetof (STRUCT, MEMBER))) + +/* Computes and returns the hash value for hash element E, given + auxiliary data AUX. */ +typedef unsigned hash_hash_func (const hash_elem *e, void *aux); + +/* Compares the value of two hash elements A and B, given + auxiliary data AUX. Returns true if A is less than B, or + false if A is greater than or equal to B. */ +typedef bool hash_less_func (const hash_elem *a, const hash_elem *b, + void *aux); + +/* Hash table. */ +struct hash + { + size_t elem_cnt; /* Number of elements in table. */ + size_t bucket_cnt; /* Number of buckets, a power of 2. */ + struct list *buckets; /* Array of `bucket_cnt' lists. */ + hash_hash_func *hash; /* Hash function. */ + hash_less_func *less; /* Comparison function. */ + void *aux; /* Auxiliary data for `hash' and `less'. */ + }; + +/* A hash table iterator. */ +struct hash_iterator + { + struct hash *hash; /* The hash table. */ + struct list *bucket; /* Current bucket. */ + hash_elem *elem; /* Current hash element in current bucket. */ + }; + +/* Basic life cycle. */ +bool hash_init (struct hash *, hash_hash_func *, hash_less_func *, void *aux); +void hash_clear (struct hash *); +void hash_destroy (struct hash *); + +/* Search, insertion, deletion. */ +hash_elem *hash_insert (struct hash *, hash_elem *); +hash_elem *hash_replace (struct hash *, hash_elem *); +hash_elem *hash_find (struct hash *, hash_elem *); +hash_elem *hash_delete (struct hash *, hash_elem *); + +/* Iteration. */ +void hash_first (struct hash_iterator *, struct hash *); +hash_elem *hash_next (struct hash_iterator *); +hash_elem *hash_cur (struct hash_iterator *); + +/* Information. */ +size_t hash_size (struct hash *); +bool hash_empty (struct hash *); + +/* Sample hash functions. */ +unsigned hash_bytes (const void *, size_t); +unsigned hash_string (const char *); +unsigned hash_int (int); + +#endif /* hash.h */ diff --git a/src/lib/kernel/list.c b/src/lib/kernel/list.c new file mode 100644 index 0000000..3631b2e --- /dev/null +++ b/src/lib/kernel/list.c @@ -0,0 +1,416 @@ +#include "list.h" +#include "../debug.h" + +/* Our doubly linked lists have two header elements: the "head" + just before the first element and the "tail" just after the + last element. The `prev' link of the front header is null, as + is the `next' link of the back header. Their other two links + point toward each other via the interior elements of the list. + + An empty list looks like this: + + +------+ +------+ + <---| head |<--->| tail |---> + +------+ +------+ + + A list with two elements in it looks like this: + + +------+ +-------+ +-------+ +------+ + <---| head |<--->| 1 |<--->| 2 |<--->| tail |<---> + +------+ +-------+ +-------+ +------+ + + The symmetry of this arrangement eliminates lots of special + cases in list processing. For example, take a look at + list_remove(): it takes only two pointer assignments and no + conditionals. That's a lot simpler than the code would be + without header elements. + + (Because only one of the pointers in each header element is used, + we could in fact combine them into a single header element + without sacrificing this simplicity. But using two separate + elements allows us to do a little bit of checking on some + operations, which can be valuable.) */ + +/* Returns true if ELEM is a head, false otherwise. */ +static inline bool +is_head (list_elem *elem) +{ + return elem != NULL && elem->prev == NULL && elem->next != NULL; +} + +/* Returns true if ELEM is an interior element, + false otherwise. */ +static inline bool +is_interior (list_elem *elem) +{ + return elem != NULL && elem->prev != NULL && elem->next != NULL; +} + +/* Returns true if ELEM is a tail, false otherwise. */ +static inline bool +is_tail (list_elem *elem) +{ + return elem != NULL && elem->prev != NULL && elem->next == NULL; +} + +/* Initializes LIST as an empty list. */ +void +list_init (struct list *list) +{ + ASSERT (list != NULL); + list->head.prev = NULL; + list->head.next = &list->tail; + list->tail.prev = &list->head; + list->tail.next = NULL; +} + +/* Returns the beginning of LIST. */ +list_elem * +list_begin (struct list *list) +{ + ASSERT (list != NULL); + return list->head.next; +} + +/* Returns the element after ELEM in its list. If ELEM is the + last element in its list, returns the list tail. Results are + undefined if ELEM is itself a list tail. */ +list_elem * +list_next (list_elem *elem) +{ + ASSERT (is_interior (elem)); + return elem->next; +} + +/* Returns LIST's tail. + + list_end() is often used in iterating through a list from + front to back. See the big comment at the top of list.h for + an example. */ +list_elem * +list_end (struct list *list) +{ + ASSERT (list != NULL); + return &list->tail; +} + +/* Returns the LIST's reverse beginning, for iterating through + LIST in reverse order, from back to front. */ +list_elem * +list_rbegin (struct list *list) +{ + ASSERT (list != NULL); + return list->tail.prev; +} + +/* Returns the element before ELEM in its list. If ELEM is the + first element in its list, returns the list head. Results are + undefined if ELEM is itself a list head. */ +list_elem * +list_prev (list_elem *elem) +{ + ASSERT (is_interior (elem) || is_tail (elem)); + return elem->prev; +} + +/* Returns LIST's head. + + list_rend() is often used in iterating through a list in + reverse order, from back to front. Here's typical usage, + following the example from the top of list.h: + + for (e = list_rbegin (&foo_list); e != list_rend (&foo_list); + e = list_prev (e)) + { + struct foo *f = list_entry (e, struct foo, elem); + ...do something with f... + } +*/ +list_elem * +list_rend (struct list *list) +{ + ASSERT (list != NULL); + return &list->head; +} + +/* Return's LIST's head. + + list_head() can be used for an alternate style of iterating + through a list, e.g.: + + e = list_head (&list); + while ((e = list_next (e)) != list_end (&list)) + { + ... + } +*/ +list_elem * +list_head (struct list *list) +{ + ASSERT (list != NULL); + return &list->head; +} + +/* Return's LIST's tail. */ +list_elem * +list_tail (struct list *list) +{ + ASSERT (list != NULL); + return &list->tail; +} + +/* Inserts ELEM just before BEFORE, which may be either an + interior element or a tail. The latter case is equivalent to + list_push_back(). */ +void +list_insert (list_elem *before, list_elem *elem) +{ + ASSERT (is_interior (before) || is_tail (before)); + ASSERT (elem != NULL); + + elem->prev = before->prev; + elem->next = before; + before->prev->next = elem; + before->prev = elem; +} + +/* Removes elements FIRST though LAST (exclusive) from their + current list, then inserts them just before BEFORE, which may + be either an interior element or a tail. */ +void +list_splice (list_elem *before, + list_elem *first, list_elem *last) +{ + ASSERT (is_interior (before) || is_tail (before)); + if (first == last) + return; + last = list_prev (last); + + ASSERT (is_interior (first)); + ASSERT (is_interior (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 = before->prev; + last->next = before; + before->prev->next = first; + before->prev = last; +} + +/* Inserts ELEM at the beginning of LIST, so that it becomes the + front in LIST. */ +void +list_push_front (struct list *list, list_elem *elem) +{ + list_insert (list_begin (list), elem); +} + +/* Inserts ELEM at the end of LIST, so that it becomes the + back in LIST. */ +void +list_push_back (struct list *list, list_elem *elem) +{ + list_insert (list_end (list), elem); +} + +/* Removes ELEM from its list. Undefined behavior if ELEM is not + in a list. */ +list_elem * +list_remove (list_elem *elem) +{ + ASSERT (is_interior (elem)); + elem->prev->next = elem->next; + elem->next->prev = elem->prev; + return elem; +} + +/* Removes the front element from LIST and returns it. + Undefined behavior if LIST is empty before removal. */ +list_elem * +list_pop_front (struct list *list) +{ + ASSERT (list != NULL); + return list_remove (list_front (list)); +} + +/* Removes the back element from LIST and returns it. + Undefined behavior if LIST is empty before removal. */ +list_elem * +list_pop_back (struct list *list) +{ + ASSERT (list != NULL); + return list_remove (list_back (list)); +} + +/* Returns the front element in LIST. + Undefined behavior if LIST is empty. */ +list_elem * +list_front (struct list *list) +{ + ASSERT (!list_empty (list)); + return list->head.next; +} + +/* Returns the back element in LIST. + Undefined behavior if LIST is empty. */ +list_elem * +list_back (struct list *list) +{ + ASSERT (!list_empty (list)); + return list->tail.prev; +} + +/* Returns the number of elements in LIST. + Runs in O(n) in the number of elements. */ +size_t +list_size (struct list *list) +{ + list_elem *e; + size_t cnt = 0; + + for (e = list_begin (list); e != list_end (list); e = list_next (e)) + cnt++; + return cnt; +} + +/* Returns true if LIST is empty, false otherwise. */ +bool +list_empty (struct list *list) +{ + return list_begin (list) == list_end (list); +} + +/* Reverses the order of LIST. */ +void +list_reverse (struct list *list) +{ + list_elem te, *e; + + /* Swap the prev and next pointers in each element of LIST. */ + for (e = &list->head; e != NULL; e = e->prev) + { + list_elem *tep = e->prev; + e->prev = e->next; + e->next = tep; + } + + /* Swap the head and tail. */ + te = list->head; + list->head = list->tail; + list->tail = te; +} + +/* Merges lists AL and BL, which must each be sorted according to + LESS given auxiliary data AUX, by inserting each element of BL + at the proper place in AL to preserve the ordering. + Runs in O(n) in the combined length of AL and BL. */ +void +list_merge (struct list *al, struct list *bl, + list_less_func *less, void *aux) +{ + list_elem *a; + + ASSERT (al != NULL); + ASSERT (bl != NULL); + ASSERT (less != NULL); + + a = list_begin (al); + while (a != list_end (al)) + { + 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)); +} + +/* Sorts LIST according to LESS given auxiliary data AUX. + Runs in O(n lg n) in the number of elements in LIST. */ +void +list_sort (struct list *list, + list_less_func *less, void *aux) +{ + struct list tmp; + 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); +} + +/* Inserts ELEM in the proper position in LIST, which must be + sorted according to LESS given auxiliary data AUX. + Runs in O(n) average case in the number of elements in LIST. */ +void +list_insert_ordered (struct list *list, list_elem *elem, + list_less_func *less, void *aux) +{ + 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); +} + +/* Iterates through LIST and removes all but the first in each + set of adjacent elements that are equal according to LESS + given auxiliary data AUX. If DUPLICATES is non-null, then the + elements from LIST are appended to DUPLICATES. */ +void +list_unique (struct list *list, struct list *duplicates, + list_less_func *less, void *aux) +{ + 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); + if (duplicates != NULL) + list_push_back (duplicates, next); + } + else + elem = next; +} diff --git a/src/lib/kernel/list.h b/src/lib/kernel/list.h new file mode 100644 index 0000000..1bf6631 --- /dev/null +++ b/src/lib/kernel/list.h @@ -0,0 +1,165 @@ +#ifndef HEADER_LIST_H +#define HEADER_LIST_H 1 + +/* Doubly linked list. + + This implementation of a doubly linked list does not require + use of dynamically allocated memory. Instead, each structure + that is a potential list element must embed a list_elem + member. All of the list functions operate on these + `list_elem's. The list_entry macro allows conversion from a + list_elem back to a structure object that contains it. + + For example, suppose there is a needed for a list of `struct + foo'. `struct foo' should contain a `list_elem' member, like + so: + + struct foo + { + list_elem elem; + int bar; + ...other members... + }; + + Then a list of `struct foo' can be be declared and initialized + like so: + + struct list foo_list; + + list_init (&foo_list); + + Iteration is a typical situation where it is necessary to + convert from a list_elem back to its enclosing structure. + Here's an example using foo_list: + + list_elem *e; + + for (e = list_begin (&foo_list); e != list_end (&foo_list); + e = list_next (e)) + { + struct foo *f = list_entry (e, struct foo, elem); + ...do something with f... + } + + You can find real examples of list usage throughout the + source; for example, malloc.c, palloc.c, and thread.c in the + threads directory all use lists. + + The interface for this list is inspired by the list<> template + in the C++ STL. If you're familiar with list<>, you should + find this easy to use. However, it should be emphasized that + these lists do *no* type checking and can't do much other + correctness checking. If you screw up, it will bite you. + + Glossary of list terms: + + - "front": The first element in a list. Undefined in an + empty list. Returned by list_front(). + + - "back": The last element in a list. Undefined in an empty + list. Returned by list_back(). + + - "tail": The element figuratively just after the last + element of a list. Well defined even in an empty list. + Returned by list_end(). Used as the end sentinel for an + iteration from front to back. + + - "beginning": In a non-empty list, the front. In an empty + list, the tail. Returned by list_begin(). Used as the + starting point for an iteration from front to back. + + - "head": The element figuratively just before the first + element of a list. Well defined even in an empty list. + Returned by list_rend(). Used as the end sentinel for an + iteration from back to front. + + - "reverse beginning": In a non-empty list, the back. In an + empty list, the head. Returned by list_rbegin(). Used as + the starting point for an iteration from back to front. + + - "interior element": An element that is not the head or + tail, that is, a real list element. An empty list does + not have any interior elements. +*/ + +#include +#include +#include + +/* List element. */ +typedef struct list_elem + { + struct list_elem *prev; /* Previous list element. */ + struct list_elem *next; /* Next list element. */ + } +list_elem; + +/* List. */ +struct list + { + list_elem head; /* List head. */ + list_elem tail; /* List tail. */ + }; + +/* Converts pointer to list element LIST_ELEM into a pointer to + the structure that LIST_ELEM is embedded inside. Supply the + name of the outer structure STRUCT and the member name MEMBER + of the list element. See the big comment at the top of the + file for an example. */ +#define list_entry(LIST_ELEM, STRUCT, MEMBER) \ + ((STRUCT *) ((uint8_t *) (LIST_ELEM) - offsetof (STRUCT, MEMBER))) + +void list_init (struct list *); + +/* List traversal. */ +list_elem *list_begin (struct list *); +list_elem *list_next (list_elem *); +list_elem *list_end (struct list *); + +list_elem *list_rbegin (struct list *); +list_elem *list_prev (list_elem *); +list_elem *list_rend (struct list *); + +list_elem *list_head (struct list *); +list_elem *list_tail (struct list *); + +/* List insertion. */ +void list_insert (list_elem *, list_elem *); +void list_splice (list_elem *before, + list_elem *first, list_elem *last); +void list_push_front (struct list *, list_elem *); +void list_push_back (struct list *, list_elem *); + +/* List removal. */ +list_elem *list_remove (list_elem *); +list_elem *list_pop_front (struct list *); +list_elem *list_pop_back (struct list *); + +/* List elements. */ +list_elem *list_front (struct list *); +list_elem *list_back (struct list *); + +/* List properties. */ +size_t list_size (struct list *); +bool list_empty (struct list *); + +/* Weirdness. */ +void list_reverse (struct list *); + +/* Operations on lists with ordered elements. */ + +/* Compares the value of two list elements A and B, given + auxiliary data AUX. Returns true if A is less than B, or + false if A is greater than or equal to B. */ +typedef bool list_less_func (const list_elem *a, const 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 *, list_elem *, + list_less_func *, void *aux); +void list_unique (struct list *, struct list *duplicates, + list_less_func *, void *aux); + +#endif /* list.h */ diff --git a/src/lib/kernel/printf.c b/src/lib/kernel/printf.c new file mode 100644 index 0000000..886706c --- /dev/null +++ b/src/lib/kernel/printf.c @@ -0,0 +1,39 @@ +#include +#include + +#include "devices/serial.h" +#include "devices/vga.h" +#include "threads/interrupt.h" + +static void vprintf_helper (char, void *); + +int +vprintf (const char *format, va_list args) +{ + enum intr_level old_level; + int char_cnt = 0; + + old_level = intr_disable (); + __vprintf (format, args, vprintf_helper, &char_cnt); + intr_set_level (old_level); + + return char_cnt; +} + +/* Helper function for vprintf(). */ +static void +vprintf_helper (char c, void *char_cnt_) +{ + int *char_cnt = char_cnt_; + (*char_cnt)++; + putchar (c); +} + +/* Writes C to the console. */ +int +putchar (int c) +{ + serial_outb (c); + vga_putc (c); + return c; +} diff --git a/src/lib/lib.c b/src/lib/lib.c deleted file mode 100644 index 91fb318..0000000 --- a/src/lib/lib.c +++ /dev/null @@ -1,929 +0,0 @@ -#include "lib.h" -#include -#include -#include -#include -#include "debug.h" -#include "devices/serial.h" -#include "devices/vga.h" -#include "threads/interrupt.h" - -static void -vprintf_core (const char *format, va_list args, - void (*output) (char, void *), void *aux); - -/* */ - -/* Sets the SIZE bytes in DST to VALUE. */ -void * -memset (void *dst_, int value, size_t size) -{ - unsigned char *dst = dst_; - - ASSERT (dst != NULL || size == 0); - - while (size-- > 0) - *dst++ = value; - - return dst_; -} - -/* Copies SIZE bytes from SRC to DST, which must not overlap. - Returns DST. */ -void * -memcpy (void *dst_, const void *src_, size_t size) -{ - unsigned char *dst = dst_; - const unsigned char *src = src_; - - ASSERT (dst != NULL || size == 0); - ASSERT (src != NULL || size == 0); - - while (size-- > 0) - *dst++ = *src++; - - return dst_; -} - -/* Copies SIZE bytes from SRC to DST, which are allowed to - overlap. Returns DST. */ -void * -memmove (void *dst_, const void *src_, size_t size) -{ - unsigned char *dst = dst_; - const unsigned char *src = src_; - - ASSERT (dst != NULL || size == 0); - ASSERT (src != NULL || size == 0); - - if (dst < src) - { - while (size-- > 0) - *dst++ = *src++; - } - else - { - dst += size; - src += size; - while (size-- > 0) - *--dst = *--src; - } - - return dst; -} - -/* Returns a pointer to the first occurrence of CH in the first - SIZE bytes starting at BLOCK. Returns a null pointer if CH - does not occur in BLOCK. */ -void * -memchr (const void *block_, int ch_, size_t size) -{ - const unsigned char *block = block_; - unsigned char ch = ch_; - - ASSERT (block != NULL || size == 0); - - for (; size-- > 0; block++) - if (*block == ch) - return (void *) block; - - return NULL; -} - -/* Find the first differing byte in the two blocks of SIZE bytes - at A and B. Returns a positive value if the byte in A is - greater, a negative value if the byte in B is greater, or zero - if blocks A and B are equal. */ -int -memcmp (const void *a_, const void *b_, size_t size) -{ - const unsigned char *a = a_; - const unsigned char *b = b_; - - ASSERT (a != NULL || size == 0); - ASSERT (b != NULL || size == 0); - - for (; size-- > 0; a++, b++) - if (*a != *b) - return *a > *b ? +1 : -1; - return 0; -} - -/* Finds and returns the first occurrence of C in STRING, or a - null pointer if C does not appear in STRING. If C == '\0' - then returns a pointer to the null terminator at the end of - STRING. */ -char * -strchr (const char *string, int c_) -{ - char c = c_; - - ASSERT (string != NULL); - - for (;;) - if (*string == c) - return (char *) string; - else if (*string == '\0') - return NULL; - else - string++; -} - -/* Copies string SRC to DST. If SRC is longer than SIZE - 1 - characters, only SIZE - 1 characters are copied. A null - terminator is always written to DST, unless SIZE is 0. - Returns the length of SRC. - - strlcpy() is not in the standard C library, but it is an - increasingly popular extension. See - http://www.courtesan.com/todd/papers/strlcpy.html for - information on strlcpy(). */ -size_t -strlcpy (char *dst, const char *src, size_t size) -{ - size_t src_len; - - ASSERT (dst != NULL); - ASSERT (src != NULL); - - src_len = strlen (src); - if (size > 0) - { - size_t dst_len = size - 1; - if (src_len < dst_len) - src_len = dst_len; - memcpy (dst, src, dst_len); - dst[dst_len] = '\0'; - } - return src_len; -} - -/* Returns the length of STRING. */ -size_t -strlen (const char *string) -{ - const char *p; - - ASSERT (string != NULL); - - for (p = string; *p != '\0'; p++) - continue; - return p - string; -} - -/* If STRING is less than MAXLEN characters in length, returns - its actual length. Otherwise, returns MAXLEN. */ -size_t -strnlen (const char *string, size_t maxlen) -{ - size_t length; - - for (length = 0; string[length] != '\0' && length < maxlen; length++) - continue; - return length; -} - -/* Finds the first differing characters in strings A and B. - Returns a positive value if the character in A (as an unsigned - char) is greater, a negative value if the character in B (as - an unsigned char) is greater, or zero if strings A and B are - equal. */ -int -strcmp (const char *a_, const char *b_) -{ - const unsigned char *a = (const unsigned char *) a_; - const unsigned char *b = (const unsigned char *) b_; - - ASSERT (a != NULL); - ASSERT (b != NULL); - - while (*a != '\0' && *a == *b) - { - a++; - b++; - } - - return *a < *b ? -1 : *a > *b; -} - -/* Breaks a string into tokens separated by DELIMITERS. The - first time this function is called, S should be the string to - tokenize, and in subsequent calls it must be a null pointer. - SAVE_PTR is the address of a `char *' variable used to keep - track of the tokenizer's position. The return value each time - is the next token in the string, or a null pointer if no - tokens remain. - - This function treats multiple adjacent delimiters as a single - delimiter. The returned tokens will never be length 0. - DELIMITERS may change from one call to the next within a - single string. - - strtok_r() modifies the string S, changing delimiters to null - bytes. Thus, S must be a modifiable string. - - Example usage: - - char s[] = " String to tokenize. "; - char *token, *save_ptr; - - for (token = strtok_r (s, " ", &save_ptr); token != NULL; - token = strtok_r (NULL, " ", &save_ptr)) - printf ("'%s'\n", token); - - outputs: - - 'String' - 'to' - 'tokenize.' -*/ -char * -strtok_r (char *s, const char *delimiters, char **save_ptr) -{ - char *token; - - ASSERT (delimiters != NULL); - ASSERT (save_ptr != NULL); - - /* If S is nonnull, start from it. - If S is null, start from saved position. */ - if (s == NULL) - s = *save_ptr; - ASSERT (s != NULL); - - /* Skip any DELIMITERS at our current position. */ - while (strchr (delimiters, *s) != NULL) - { - /* strchr() will always return nonnull if we're searching - for a null byte, because every string contains a null - byte (at the end). */ - if (*s == '\0') - { - *save_ptr = s; - return NULL; - } - - s++; - } - - /* Skip any non-DELIMITERS up to the end of the string. */ - token = s; - while (strchr (delimiters, *s) == NULL) - s++; - if (*s != '\0') - { - *s = '\0'; - *save_ptr = s + 1; - } - else - *save_ptr = s; - return token; -} - -/* */ - -/* Converts a string representation of a signed decimal integer - in S into an `int', which is returned. */ -int -atoi (const char *s) -{ - bool negative; - int value; - - /* Skip white space. */ - while (isspace (*s)) - s++; - - /* Parse sign. */ - negative = false; - if (*s == '+') - s++; - else if (*s == '-') - { - negative = true; - s++; - } - - /* Parse digits. We always initially parse the value as - negative, and then make it positive later, because the - negative range of an int is bigger than the positive range - on a 2's complement system. */ - for (value = 0; isdigit (*s); s++) - value = value * 10 - (*s - '0'); - if (!negative) - value = -value; - - return value; -} - -/* */ - -/* Auxiliary data for vsnprintf_helper(). */ -struct vsnprintf_aux - { - char *p; /* Current output position. */ - int length; /* Length of output string. */ - int max_length; /* Max length of output string. */ - }; - -static void vsnprintf_helper (char, void *); - -/* Like vprintf(), except that output is stored into BUFFER, - which must have space for BUF_SIZE characters. Writes at most - BUF_SIZE - 1 characters to BUFFER, followed by a null - terminator. BUFFER will always be null-terminated unless - BUF_SIZE is zero. Returns the number of characters that would - have been written to BUFFER, not including a null terminator, - had there been enough room. */ -int -vsnprintf (char *buffer, size_t buf_size, const char *format, va_list args) -{ - /* Set up aux data for vsnprintf_helper(). */ - struct vsnprintf_aux aux; - aux.p = buffer; - aux.length = 0; - aux.max_length = buf_size > 0 ? buf_size - 1 : 0; - - /* Do most of the work. */ - vprintf_core (format, args, vsnprintf_helper, &aux); - - /* Add null terminator. */ - if (buf_size > 0) - *aux.p = '\0'; - - return aux.length; -} - -/* Helper function for vsnprintf(). */ -static void -vsnprintf_helper (char ch, void *aux_) -{ - struct vsnprintf_aux *aux = aux_; - - if (aux->length++ < aux->max_length) - *aux->p++ = ch; -} - -/* Like printf(), except that output is stored into BUFFER, - which must have space for BUF_SIZE characters. Writes at most - BUF_SIZE - 1 characters to BUFFER, followed by a null - terminator. BUFFER will always be null-terminated unless - BUF_SIZE is zero. Returns the number of characters that would - have been written to BUFFER, not including a null terminator, - had there been enough room. */ -int -snprintf (char *buffer, size_t buf_size, const char *format, ...) -{ - va_list args; - int retval; - - va_start (args, format); - retval = vsnprintf (buffer, buf_size, format, args); - va_end (args); - - return retval; -} - -/* Nonstandard functions. */ - -static void vprintk_helper (char, void *); - -/* Like vprintf(), except that output is written to the system - console, which is defined as the video display and the first - serial port (at the same time). */ -void -vprintk (const char *format, va_list args) -{ - enum intr_level old_level = intr_disable (); - vprintf_core (format, args, vprintk_helper, NULL); - intr_set_level (old_level); -} - -/* Helper function for vprintk(). */ -static void -vprintk_helper (char ch, void *aux UNUSED) -{ - vga_putc (ch); - serial_outb (ch); -} - -/* Like printf(), except that output is written to the system - console, which is defined as the video display and the first - serial port (at the same time). */ -void -printk (const char *format, ...) -{ - va_list args; - - va_start (args, format); - vprintk (format, args); - va_end (args); -} - -/* printf() formatting internals. */ - -/* A printf() conversion. */ -struct printf_conversion - { - /* Flags. */ - enum - { - MINUS = 1 << 0, /* '-' */ - PLUS = 1 << 1, /* '+' */ - SPACE = 1 << 2, /* ' ' */ - POUND = 1 << 3, /* '#' */ - ZERO = 1 << 4, /* '0' */ - GROUP = 1 << 5 /* '\'' */ - } - flags; - - /* Minimum field width. */ - int width; - - /* Numeric precision. - -1 indicates no precision was specified. */ - int precision; - - /* Type of argument to format. */ - enum - { - CHAR = 1, /* hh */ - SHORT = 2, /* h */ - INT = 3, /* (none) */ - INTMAX = 4, /* j */ - LONG = 5, /* l */ - LONGLONG = 6, /* ll */ - PTRDIFFT = 7, /* t */ - SIZET = 8 /* z */ - } - type; - }; - -struct integer_base - { - int base; /* Base. */ - const char *digits; /* Collection of digits. */ - const char *signifier; /* Prefix used with # flag. */ - int group; /* Number of digits to group with ' flag. */ - }; - -static const struct integer_base base_d = {10, "0123456789", "", 3}; -static const struct integer_base base_o = {8, "01234567", "0", 3}; -static const struct integer_base base_x = {16, "0123456789abcdef", "0x", 4}; -static const struct integer_base base_X = {16, "0123456789ABCDEF", "0X", 4}; - -static const char *parse_conversion (const char *format, - struct printf_conversion *, - va_list *); -static void format_integer (uintmax_t value, bool negative, - const struct integer_base *, - const struct printf_conversion *, - void (*output) (char, void *), void *aux); -static void output_dup (char ch, size_t cnt, - void (*output) (char, void *), void *aux); -static void format_string (const char *string, size_t length, - struct printf_conversion *, - void (*output) (char, void *), void *aux); -static void printf_core (const char *format, - void (*output) (char, void *), void *aux, ...); - -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; - } - - /* Parse conversion specifiers. */ - format = parse_conversion (format, &c, &args); - - /* Do conversion. */ - switch (*format) - { - case 'd': - case 'i': - { - /* Signed integer conversions. */ - intmax_t value; - - 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 (); - } - - format_integer (value < 0 ? -value : value, - value < 0, &base_d, &c, output, aux); - } - break; - - case 'o': - case 'u': - case 'x': - case 'X': - { - /* Unsigned integer conversions. */ - uintmax_t value; - const struct integer_base *b; - - 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': b = &base_o; break; - case 'u': b = &base_d; break; - case 'x': b = &base_x; break; - case 'X': b = &base_X; break; - default: NOT_REACHED (); - } - - format_integer (value, false, b, &c, output, aux); - } - break; - - case 'c': - { - /* Treat character as single-character string. */ - char ch = va_arg (args, int); - format_string (&ch, 1, &c, output, aux); - } - break; - - case 's': - { - /* String conversion. */ - const char *s = va_arg (args, char *); - if (s == NULL) - s = "(null)"; - - /* Limit string length according to precision. - Note: if c.precision == -1 then strnlen() will get - SIZE_MAX for MAXLEN, which is just what we want. */ - format_string (s, strnlen (s, c.precision), &c, output, aux); - } - break; - - case 'p': - { - /* Pointer conversion. - Format non-null pointers as %#x. */ - void *p = va_arg (args, void *); - - c.flags = POUND; - if (p != NULL) - format_integer ((uintptr_t) p, false, &base_x, &c, output, aux); - else - format_string ("(nil)", 5, &c, output, aux); - } - break; - - case 'f': - case 'e': - case 'E': - case 'g': - case 'G': - case 'n': - /* We don't support floating-point arithmetic, - and %n can be part of a security hole. */ - printf_core ("<>", output, aux, *format); - break; - - default: - printf_core ("<>", output, aux, *format); - break; - } - } -} - -/* Parses conversion option characters starting at FORMAT and - initializes C appropriately. Returns the character in FORMAT - that indicates the conversion (e.g. the `d' in `%d'). Uses - *ARGS for `*' field widths and precisions. */ -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; - case '\'': - c->flags |= GROUP; - 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 't': - c->type = PTRDIFFT; - break; - - case 'z': - c->type = SIZET; - break; - - default: - format--; - break; - } - - return format; -} - -/* Performs an integer conversion, writing output to OUTPUT with - auxiliary data AUX. The integer converted has absolute value - VALUE. If NEGATIVE is true the value is negative, otherwise - positive. The output will use the given DIGITS, with - strlen(DIGITS) indicating the output base. Details of the - conversion are in C. */ -static void -format_integer (uintmax_t value, bool negative, const struct integer_base *b, - const struct printf_conversion *c, - void (*output) (char, void *), void *aux) -{ - char buf[64], *cp; /* Buffer and current position. */ - const char *signifier; /* b->signifier or "". */ - int precision; /* Rendered precision. */ - int pad_cnt; /* # of pad characters to fill field width. */ - int group_cnt; /* # of digits grouped so far. */ - - /* Accumulate digits into buffer. - This algorithm produces digits in reverse order, so later we - will output the buffer's content in reverse. This is also - the reason that later we append zeros and the sign. */ - cp = buf; - group_cnt = 0; - while (value > 0) - { - if ((c->flags & GROUP) && group_cnt++ == b->group) - { - *cp++ = ','; - group_cnt = 0; - } - *cp++ = b->digits[value % b->base]; - value /= b->base; - } - - /* Append enough zeros to match precision. - If requested precision is 0, then a value of zero is - rendered as a null string, otherwise as "0". */ - precision = c->precision < 0 ? 1 : c->precision; - if (precision < 0) - precision = 1; - while (cp - buf < precision && cp - buf < (int) sizeof buf - 8) - *cp++ = '0'; - - /* Append sign. */ - if (c->flags & PLUS) - *cp++ = negative ? '-' : '+'; - else if (c->flags & SPACE) - *cp++ = negative ? '-' : ' '; - else if (negative) - *cp++ = '-'; - - /* Calculate number of pad characters to fill field width. */ - signifier = c->flags & POUND ? b->signifier : ""; - pad_cnt = c->width - (cp - buf) - strlen (signifier); - if (pad_cnt < 0) - pad_cnt = 0; - - /* Do output. */ - if ((c->flags & (MINUS | ZERO)) == 0) - output_dup (' ', pad_cnt, output, aux); - while (*signifier != '\0') - output (*signifier++, aux); - if (c->flags & ZERO) - output_dup ('0', pad_cnt, output, aux); - while (cp > buf) - output (*--cp, aux); - if (c->flags & MINUS) - output_dup (' ', pad_cnt, output, aux); -} - -/* Writes CH to OUTPUT with auxiliary data AUX, CNT times. */ -static void -output_dup (char ch, size_t cnt, void (*output) (char, void *), void *aux) -{ - while (cnt-- > 0) - output (ch, aux); -} - -/* Formats the LENGTH characters starting at STRING according to - the conversion specified in C. Writes output to OUTPUT with - auxiliary data AUX. */ -static void -format_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); -} - -/* Wrapper for vprintf_core() that converts varargs into a - va_list. */ -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); -} - -/* Dumps the SIZE bytes in BUFFER to the console as hex bytes - arranged 16 per line. If ASCII is true then the corresponding - ASCII characters are also rendered alongside. */ -void -hex_dump (const void *buffer, size_t size, bool ascii) -{ - const size_t n_per_line = 16; /* Maximum bytes per line. */ - size_t n; /* Number of bytes in this line. */ - const uint8_t *p; /* Start of current line in buffer. */ - - for (p = buffer; p < (uint8_t *) buffer + size; p += n) - { - size_t i; - - /* Number of bytes on this line. */ - n = (uint8_t *) (buffer + size) - p; - if (n > n_per_line) - n = n_per_line; - - /* Print line. */ - for (i = 0; i < n; i++) - printk ("%c%02x", i == n_per_line / 2 ? '-' : ' ', (unsigned) p[i]); - if (ascii) - { - for (; i < n_per_line; i++) - printk (" "); - printk (" |"); - for (i = 0; i < n; i++) - printk ("%c", isprint (p[i]) ? p[i] : '.'); - for (; i < n_per_line; i++) - printk (" "); - printk ("|"); - } - printk ("\n"); - } -} diff --git a/src/lib/lib.h b/src/lib/lib.h deleted file mode 100644 index 8883cf7..0000000 --- a/src/lib/lib.h +++ /dev/null @@ -1,68 +0,0 @@ -#ifndef HEADER_LIB_H -#define HEADER_LIB_H 1 - -#include -#include -#include -#include "debug.h" - -/* */ -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); -int memcmp (const void *, const void *, size_t); - -char *strchr (const char *, int); -size_t strlcpy (char *, const char *, size_t); -size_t strlen (const char *); -size_t strnlen (const char *, size_t); -int strcmp (const char *, const char *); -char *strtok_r (char *, const char *, char **); - -/* */ -int atoi (const char *); - -/* */ -int vsnprintf (char *, size_t, const char *, va_list) PRINTF_FORMAT (3, 0); -int snprintf (char *, size_t, const char *, ...) PRINTF_FORMAT (3, 4); - -/* */ -static inline int islower (int c) { return c >= 'a' && c <= 'z'; } -static inline int isupper (int c) { return c >= 'A' && c <= 'Z'; } -static inline int isalpha (int c) { return islower (c) || isupper (c); } -static inline int isdigit (int c) { return c >= '0' && c <= '9'; } -static inline int isalnum (int c) { return isalpha (c) || isdigit (c); } -static inline int isxdigit (int c) { - return isdigit (c) || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F'); -} -static inline int isspace (int c) { return strchr (" \f\n\r\t\v", c) != NULL; } -static inline int isgraph (int c) { return c >= 33 && c < 127; } -static inline int isprint (int c) { return c >= 32 && c < 127; } -static inline int iscntrl (int c) { return c >= 0 && c < 32; } -static inline int isascii (int c) { return c >= 0 && c < 128; } -static inline int ispunct (int c) { - return isprint (c) && !isalnum (c) && !isspace (c); -} - -/* Nonstandard. */ - -/* Yields X rounded up to the nearest multiple of STEP. - For X >= 0, STEP >= 1 only. */ -#define ROUND_UP(X, STEP) (((X) + (STEP) - 1) / (STEP) * (STEP)) - -/* Yields X divided by STEP, rounded up. - For X >= 0, STEP >= 1 only. */ -#define DIV_ROUND_UP(X, STEP) (((X) + (STEP) - 1) / (STEP)) - -/* Yields X rounded down to the nearest multiple of STEP. - For X >= 0, STEP >= 1 only. */ -#define ROUND_DOWN(X, STEP) ((X) / (STEP) * (STEP)) - -/* There is no DIV_ROUND_DOWN. It would be simply X / STEP. */ - -void vprintk (const char *, va_list) PRINTF_FORMAT (1, 0); -void printk (const char *, ...) PRINTF_FORMAT (1, 2); -void hex_dump (const void *, size_t size, bool ascii); - -#endif /* lib.h */ diff --git a/src/lib/limits.h b/src/lib/limits.h new file mode 100644 index 0000000..930a97b --- /dev/null +++ b/src/lib/limits.h @@ -0,0 +1,34 @@ +#ifndef LIB_LIMITS_H +#define LIB_LIMITS_H + +#define CHAR_BIT 8 + +#define SCHAR_MAX 127 +#define SCHAR_MIN (-SCHAR_MAX - 1) +#define UCHAR_MAX 255 + +#ifdef __CHAR_UNSIGNED__ +#define CHAR_MIN 0 +#define CHAR_MAX UCHAR_MAX +#else +#define CHAR_MIN SCHAR_MIN +#define CHAR_MAX SCHAR_MAX +#endif + +#define SHRT_MAX 32767 +#define SHRT_MIN (-SHRT_MAX - 1) +#define USHRT_MAX 65535 + +#define INT_MAX 2147483647 +#define INT_MIN (-INT_MAX - 1) +#define UINT_MAX 4294967295U + +#define LONG_MAX 2147483647L +#define LONG_MIN (-LONG_MAX - 1) +#define ULONG_MAX 4294967295UL + +#define LLONG_MAX 9223372036854775807LL +#define LLONG_MIN (-LLONG_MAX - 1) +#define ULLONG_MAX 18446744073709551615ULL + +#endif /* lib/limits.h */ diff --git a/src/lib/list.c b/src/lib/list.c deleted file mode 100644 index a5f7c1a..0000000 --- a/src/lib/list.c +++ /dev/null @@ -1,416 +0,0 @@ -#include "list.h" -#include "debug.h" - -/* Our doubly linked lists have two header elements: the "head" - just before the first element and the "tail" just after the - last element. The `prev' link of the front header is null, as - is the `next' link of the back header. Their other two links - point toward each other via the interior elements of the list. - - An empty list looks like this: - - +------+ +------+ - <---| head |<--->| tail |---> - +------+ +------+ - - A list with two elements in it looks like this: - - +------+ +-------+ +-------+ +------+ - <---| head |<--->| 1 |<--->| 2 |<--->| tail |<---> - +------+ +-------+ +-------+ +------+ - - The symmetry of this arrangement eliminates lots of special - cases in list processing. For example, take a look at - list_remove(): it takes only two pointer assignments and no - conditionals. That's a lot simpler than the code would be - without header elements. - - (Because only one of the pointers in each header element is used, - we could in fact combine them into a single header element - without sacrificing this simplicity. But using two separate - elements allows us to do a little bit of checking on some - operations, which can be valuable.) */ - -/* Returns true if ELEM is a head, false otherwise. */ -static inline bool -is_head (list_elem *elem) -{ - return elem != NULL && elem->prev == NULL && elem->next != NULL; -} - -/* Returns true if ELEM is an interior element, - false otherwise. */ -static inline bool -is_interior (list_elem *elem) -{ - return elem != NULL && elem->prev != NULL && elem->next != NULL; -} - -/* Returns true if ELEM is a tail, false otherwise. */ -static inline bool -is_tail (list_elem *elem) -{ - return elem != NULL && elem->prev != NULL && elem->next == NULL; -} - -/* Initializes LIST as an empty list. */ -void -list_init (struct list *list) -{ - ASSERT (list != NULL); - list->head.prev = NULL; - list->head.next = &list->tail; - list->tail.prev = &list->head; - list->tail.next = NULL; -} - -/* Returns the beginning of LIST. */ -list_elem * -list_begin (struct list *list) -{ - ASSERT (list != NULL); - return list->head.next; -} - -/* Returns the element after ELEM in its list. If ELEM is the - last element in its list, returns the list tail. Results are - undefined if ELEM is itself a list tail. */ -list_elem * -list_next (list_elem *elem) -{ - ASSERT (is_interior (elem)); - return elem->next; -} - -/* Returns LIST's tail. - - list_end() is often used in iterating through a list from - front to back. See the big comment at the top of list.h for - an example. */ -list_elem * -list_end (struct list *list) -{ - ASSERT (list != NULL); - return &list->tail; -} - -/* Returns the LIST's reverse beginning, for iterating through - LIST in reverse order, from back to front. */ -list_elem * -list_rbegin (struct list *list) -{ - ASSERT (list != NULL); - return list->tail.prev; -} - -/* Returns the element before ELEM in its list. If ELEM is the - first element in its list, returns the list head. Results are - undefined if ELEM is itself a list head. */ -list_elem * -list_prev (list_elem *elem) -{ - ASSERT (is_interior (elem) || is_tail (elem)); - return elem->prev; -} - -/* Returns LIST's head. - - list_rend() is often used in iterating through a list in - reverse order, from back to front. Here's typical usage, - following the example from the top of list.h: - - for (e = list_rbegin (&foo_list); e != list_rend (&foo_list); - e = list_prev (e)) - { - struct foo *f = list_entry (e, struct foo, elem); - ...do something with f... - } -*/ -list_elem * -list_rend (struct list *list) -{ - ASSERT (list != NULL); - return &list->head; -} - -/* Return's LIST's head. - - list_head() can be used for an alternate style of iterating - through a list, e.g.: - - e = list_head (&list); - while ((e = list_next (e)) != list_end (&list)) - { - ... - } -*/ -list_elem * -list_head (struct list *list) -{ - ASSERT (list != NULL); - return &list->head; -} - -/* Return's LIST's tail. */ -list_elem * -list_tail (struct list *list) -{ - ASSERT (list != NULL); - return &list->tail; -} - -/* Inserts ELEM just before BEFORE, which may be either an - interior element or a tail. The latter case is equivalent to - list_push_back(). */ -void -list_insert (list_elem *before, list_elem *elem) -{ - ASSERT (is_interior (before) || is_tail (before)); - ASSERT (elem != NULL); - - elem->prev = before->prev; - elem->next = before; - before->prev->next = elem; - before->prev = elem; -} - -/* Removes elements FIRST though LAST (exclusive) from their - current list, then inserts them just before BEFORE, which may - be either an interior element or a tail. */ -void -list_splice (list_elem *before, - list_elem *first, list_elem *last) -{ - ASSERT (is_interior (before) || is_tail (before)); - if (first == last) - return; - last = list_prev (last); - - ASSERT (is_interior (first)); - ASSERT (is_interior (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 = before->prev; - last->next = before; - before->prev->next = first; - before->prev = last; -} - -/* Inserts ELEM at the beginning of LIST, so that it becomes the - front in LIST. */ -void -list_push_front (struct list *list, list_elem *elem) -{ - list_insert (list_begin (list), elem); -} - -/* Inserts ELEM at the end of LIST, so that it becomes the - back in LIST. */ -void -list_push_back (struct list *list, list_elem *elem) -{ - list_insert (list_end (list), elem); -} - -/* Removes ELEM from its list. Undefined behavior if ELEM is not - in a list. */ -list_elem * -list_remove (list_elem *elem) -{ - ASSERT (is_interior (elem)); - elem->prev->next = elem->next; - elem->next->prev = elem->prev; - return elem; -} - -/* Removes the front element from LIST and returns it. - Undefined behavior if LIST is empty before removal. */ -list_elem * -list_pop_front (struct list *list) -{ - ASSERT (list != NULL); - return list_remove (list_front (list)); -} - -/* Removes the back element from LIST and returns it. - Undefined behavior if LIST is empty before removal. */ -list_elem * -list_pop_back (struct list *list) -{ - ASSERT (list != NULL); - return list_remove (list_back (list)); -} - -/* Returns the front element in LIST. - Undefined behavior if LIST is empty. */ -list_elem * -list_front (struct list *list) -{ - ASSERT (!list_empty (list)); - return list->head.next; -} - -/* Returns the back element in LIST. - Undefined behavior if LIST is empty. */ -list_elem * -list_back (struct list *list) -{ - ASSERT (!list_empty (list)); - return list->tail.prev; -} - -/* Returns the number of elements in LIST. - Runs in O(n) in the number of elements. */ -size_t -list_size (struct list *list) -{ - list_elem *e; - size_t cnt = 0; - - for (e = list_begin (list); e != list_end (list); e = list_next (e)) - cnt++; - return cnt; -} - -/* Returns true if LIST is empty, false otherwise. */ -bool -list_empty (struct list *list) -{ - return list_begin (list) == list_end (list); -} - -/* Reverses the order of LIST. */ -void -list_reverse (struct list *list) -{ - list_elem te, *e; - - /* Swap the prev and next pointers in each element of LIST. */ - for (e = &list->head; e != NULL; e = e->prev) - { - list_elem *tep = e->prev; - e->prev = e->next; - e->next = tep; - } - - /* Swap the head and tail. */ - te = list->head; - list->head = list->tail; - list->tail = te; -} - -/* Merges lists AL and BL, which must each be sorted according to - LESS given auxiliary data AUX, by inserting each element of BL - at the proper place in AL to preserve the ordering. - Runs in O(n) in the combined length of AL and BL. */ -void -list_merge (struct list *al, struct list *bl, - list_less_func *less, void *aux) -{ - list_elem *a; - - ASSERT (al != NULL); - ASSERT (bl != NULL); - ASSERT (less != NULL); - - a = list_begin (al); - while (a != list_end (al)) - { - 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)); -} - -/* Sorts LIST according to LESS given auxiliary data AUX. - Runs in O(n lg n) in the number of elements in LIST. */ -void -list_sort (struct list *list, - list_less_func *less, void *aux) -{ - struct list tmp; - 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); -} - -/* Inserts ELEM in the proper position in LIST, which must be - sorted according to LESS given auxiliary data AUX. - Runs in O(n) average case in the number of elements in LIST. */ -void -list_insert_ordered (struct list *list, list_elem *elem, - list_less_func *less, void *aux) -{ - 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); -} - -/* Iterates through LIST and removes all but the first in each - set of adjacent elements that are equal according to LESS - given auxiliary data AUX. If DUPLICATES is non-null, then the - elements from LIST are appended to DUPLICATES. */ -void -list_unique (struct list *list, struct list *duplicates, - list_less_func *less, void *aux) -{ - 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); - if (duplicates != NULL) - list_push_back (duplicates, next); - } - else - elem = next; -} diff --git a/src/lib/list.h b/src/lib/list.h deleted file mode 100644 index 1bf6631..0000000 --- a/src/lib/list.h +++ /dev/null @@ -1,165 +0,0 @@ -#ifndef HEADER_LIST_H -#define HEADER_LIST_H 1 - -/* Doubly linked list. - - This implementation of a doubly linked list does not require - use of dynamically allocated memory. Instead, each structure - that is a potential list element must embed a list_elem - member. All of the list functions operate on these - `list_elem's. The list_entry macro allows conversion from a - list_elem back to a structure object that contains it. - - For example, suppose there is a needed for a list of `struct - foo'. `struct foo' should contain a `list_elem' member, like - so: - - struct foo - { - list_elem elem; - int bar; - ...other members... - }; - - Then a list of `struct foo' can be be declared and initialized - like so: - - struct list foo_list; - - list_init (&foo_list); - - Iteration is a typical situation where it is necessary to - convert from a list_elem back to its enclosing structure. - Here's an example using foo_list: - - list_elem *e; - - for (e = list_begin (&foo_list); e != list_end (&foo_list); - e = list_next (e)) - { - struct foo *f = list_entry (e, struct foo, elem); - ...do something with f... - } - - You can find real examples of list usage throughout the - source; for example, malloc.c, palloc.c, and thread.c in the - threads directory all use lists. - - The interface for this list is inspired by the list<> template - in the C++ STL. If you're familiar with list<>, you should - find this easy to use. However, it should be emphasized that - these lists do *no* type checking and can't do much other - correctness checking. If you screw up, it will bite you. - - Glossary of list terms: - - - "front": The first element in a list. Undefined in an - empty list. Returned by list_front(). - - - "back": The last element in a list. Undefined in an empty - list. Returned by list_back(). - - - "tail": The element figuratively just after the last - element of a list. Well defined even in an empty list. - Returned by list_end(). Used as the end sentinel for an - iteration from front to back. - - - "beginning": In a non-empty list, the front. In an empty - list, the tail. Returned by list_begin(). Used as the - starting point for an iteration from front to back. - - - "head": The element figuratively just before the first - element of a list. Well defined even in an empty list. - Returned by list_rend(). Used as the end sentinel for an - iteration from back to front. - - - "reverse beginning": In a non-empty list, the back. In an - empty list, the head. Returned by list_rbegin(). Used as - the starting point for an iteration from back to front. - - - "interior element": An element that is not the head or - tail, that is, a real list element. An empty list does - not have any interior elements. -*/ - -#include -#include -#include - -/* List element. */ -typedef struct list_elem - { - struct list_elem *prev; /* Previous list element. */ - struct list_elem *next; /* Next list element. */ - } -list_elem; - -/* List. */ -struct list - { - list_elem head; /* List head. */ - list_elem tail; /* List tail. */ - }; - -/* Converts pointer to list element LIST_ELEM into a pointer to - the structure that LIST_ELEM is embedded inside. Supply the - name of the outer structure STRUCT and the member name MEMBER - of the list element. See the big comment at the top of the - file for an example. */ -#define list_entry(LIST_ELEM, STRUCT, MEMBER) \ - ((STRUCT *) ((uint8_t *) (LIST_ELEM) - offsetof (STRUCT, MEMBER))) - -void list_init (struct list *); - -/* List traversal. */ -list_elem *list_begin (struct list *); -list_elem *list_next (list_elem *); -list_elem *list_end (struct list *); - -list_elem *list_rbegin (struct list *); -list_elem *list_prev (list_elem *); -list_elem *list_rend (struct list *); - -list_elem *list_head (struct list *); -list_elem *list_tail (struct list *); - -/* List insertion. */ -void list_insert (list_elem *, list_elem *); -void list_splice (list_elem *before, - list_elem *first, list_elem *last); -void list_push_front (struct list *, list_elem *); -void list_push_back (struct list *, list_elem *); - -/* List removal. */ -list_elem *list_remove (list_elem *); -list_elem *list_pop_front (struct list *); -list_elem *list_pop_back (struct list *); - -/* List elements. */ -list_elem *list_front (struct list *); -list_elem *list_back (struct list *); - -/* List properties. */ -size_t list_size (struct list *); -bool list_empty (struct list *); - -/* Weirdness. */ -void list_reverse (struct list *); - -/* Operations on lists with ordered elements. */ - -/* Compares the value of two list elements A and B, given - auxiliary data AUX. Returns true if A is less than B, or - false if A is greater than or equal to B. */ -typedef bool list_less_func (const list_elem *a, const 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 *, list_elem *, - list_less_func *, void *aux); -void list_unique (struct list *, struct list *duplicates, - list_less_func *, void *aux); - -#endif /* list.h */ diff --git a/src/lib/round.h b/src/lib/round.h new file mode 100644 index 0000000..df0fb4a --- /dev/null +++ b/src/lib/round.h @@ -0,0 +1,18 @@ +#ifndef LIB_ROUND_H +#define LIB_ROUND_H + +/* Yields X rounded up to the nearest multiple of STEP. + For X >= 0, STEP >= 1 only. */ +#define ROUND_UP(X, STEP) (((X) + (STEP) - 1) / (STEP) * (STEP)) + +/* Yields X divided by STEP, rounded up. + For X >= 0, STEP >= 1 only. */ +#define DIV_ROUND_UP(X, STEP) (((X) + (STEP) - 1) / (STEP)) + +/* Yields X rounded down to the nearest multiple of STEP. + For X >= 0, STEP >= 1 only. */ +#define ROUND_DOWN(X, STEP) ((X) / (STEP) * (STEP)) + +/* There is no DIV_ROUND_DOWN. It would be simply X / STEP. */ + +#endif /* lib/round.h */ diff --git a/src/lib/stdarg.h b/src/lib/stdarg.h new file mode 100644 index 0000000..690bb28 --- /dev/null +++ b/src/lib/stdarg.h @@ -0,0 +1,14 @@ +#ifndef LIB_STDARG_H +#define LIB_STDARG_H + +/* GCC has functionality as built-ins, + so all we need is to use it. */ + +typedef __builtin_va_list va_list; + +#define va_start(LIST, ARG) __builtin_va_start (LIST, ARG) +#define va_end(LIST) __builtin_va_end (LIST) +#define va_arg(LIST, TYPE) __builtin_va_arg (LIST, TYPE) +#define va_copy(DST, SRC) __builtin_va_copy (DST, SRC) + +#endif /* lib/stdarg.h */ diff --git a/src/lib/stdbool.h b/src/lib/stdbool.h new file mode 100644 index 0000000..45fc515 --- /dev/null +++ b/src/lib/stdbool.h @@ -0,0 +1,9 @@ +#ifndef LIB_STDBOOL_H +#define LIB_STDBOOL_H + +#define bool _Bool +#define true 1 +#define false 0 +#define __bool_true_false_are_defined 1 + +#endif /* lib/stdbool.h */ diff --git a/src/lib/stddef.h b/src/lib/stddef.h new file mode 100644 index 0000000..836b8f2 --- /dev/null +++ b/src/lib/stddef.h @@ -0,0 +1,9 @@ +#ifndef LIB_STDDEF_H +#define LIB_STDDEF_H + +#define NULL ((void *) 0) +#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *) 0)->MEMBER) +typedef int ptrdiff_t; +typedef unsigned int size_t; + +#endif /* lib/stddef.h */ diff --git a/src/lib/stdint.h b/src/lib/stdint.h new file mode 100644 index 0000000..2f0218f --- /dev/null +++ b/src/lib/stdint.h @@ -0,0 +1,51 @@ +#ifndef LIB_STDINT_H +#define LIB_STDINT_H + +typedef signed char int8_t; +#define INT8_MAX 127 +#define INT8_MIN (-INT8_MAX - 1) + +typedef signed short int int16_t; +#define INT16_MAX 32767 +#define INT16_MIN (-INT16_MAX - 1) + +typedef signed int int32_t; +#define INT32_MAX 2147483647 +#define INT32_MIN (-INT32_MAX - 1) + +typedef signed long long int int64_t; +#define INT64_MAX 9223372036854775807LL +#define INT64_MIN (-INT64_MAX - 1) + +typedef unsigned char uint8_t; +#define UINT8_MAX 255 + +typedef unsigned short int uint16_t; +#define UINT16_MAX 65535 + +typedef unsigned int uint32_t; +#define UINT32_MAX 4294967295 + +typedef unsigned long long int uint64_t; +#define UINT64_MAX 18446744073709551615ULL + +typedef int32_t intptr_t; +#define INTPTR_MIN INT32_MIN +#define INTPTR_MAX INT32_MAX + +typedef uint32_t uintptr_t; +#define UINTPTR_MAX UINT32_MAX + +typedef int64_t intmax_t; +#define INTMAX_MIN INT64_MIN +#define INTMAX_MAX INT64_MAX + +typedef uint64_t uintmax_t; +#define UINTMAX_MAX UINT64_MAX + +#define PTRDIFF_MIN INT32_MIN +#define PTRDIFF_MAX INT32_MAX + +#define SIZE_MAX UINT32_MAX + +#endif /* lib/stdint.h */ diff --git a/src/lib/stdio.c b/src/lib/stdio.c new file mode 100644 index 0000000..6a03f53 --- /dev/null +++ b/src/lib/stdio.c @@ -0,0 +1,605 @@ +#include +#include +#include +#include + +/* Auxiliary data for vsnprintf_helper(). */ +struct vsnprintf_aux + { + char *p; /* Current output position. */ + int length; /* Length of output string. */ + int max_length; /* Max length of output string. */ + }; + +static void vsnprintf_helper (char, void *); + +/* Like vprintf(), except that output is stored into BUFFER, + which must have space for BUF_SIZE characters. Writes at most + BUF_SIZE - 1 characters to BUFFER, followed by a null + terminator. BUFFER will always be null-terminated unless + BUF_SIZE is zero. Returns the number of characters that would + have been written to BUFFER, not including a null terminator, + had there been enough room. */ +int +vsnprintf (char *buffer, size_t buf_size, const char *format, va_list args) +{ + /* Set up aux data for vsnprintf_helper(). */ + struct vsnprintf_aux aux; + aux.p = buffer; + aux.length = 0; + aux.max_length = buf_size > 0 ? buf_size - 1 : 0; + + /* Do most of the work. */ + __vprintf (format, args, vsnprintf_helper, &aux); + + /* Add null terminator. */ + if (buf_size > 0) + *aux.p = '\0'; + + return aux.length; +} + +/* Helper function for vsnprintf(). */ +static void +vsnprintf_helper (char ch, void *aux_) +{ + struct vsnprintf_aux *aux = aux_; + + if (aux->length++ < aux->max_length) + *aux->p++ = ch; +} + +/* Like printf(), except that output is stored into BUFFER, + which must have space for BUF_SIZE characters. Writes at most + BUF_SIZE - 1 characters to BUFFER, followed by a null + terminator. BUFFER will always be null-terminated unless + BUF_SIZE is zero. Returns the number of characters that would + have been written to BUFFER, not including a null terminator, + had there been enough room. */ +int +snprintf (char *buffer, size_t buf_size, const char *format, ...) +{ + va_list args; + int retval; + + va_start (args, format); + retval = vsnprintf (buffer, buf_size, format, args); + va_end (args); + + return retval; +} + +/* Writes formatted output to the console. + In the kernel, the console is both the video display and first + serial port. + In userspace, the console is file descriptor 1. +*/ +int +printf (const char *format, ...) +{ + va_list args; + int retval; + + va_start (args, format); + retval = vprintf (format, args); + va_end (args); + + return retval; +} + +/* printf() formatting internals. */ + +/* A printf() conversion. */ +struct printf_conversion + { + /* Flags. */ + enum + { + MINUS = 1 << 0, /* '-' */ + PLUS = 1 << 1, /* '+' */ + SPACE = 1 << 2, /* ' ' */ + POUND = 1 << 3, /* '#' */ + ZERO = 1 << 4, /* '0' */ + GROUP = 1 << 5 /* '\'' */ + } + flags; + + /* Minimum field width. */ + int width; + + /* Numeric precision. + -1 indicates no precision was specified. */ + int precision; + + /* Type of argument to format. */ + enum + { + CHAR = 1, /* hh */ + SHORT = 2, /* h */ + INT = 3, /* (none) */ + INTMAX = 4, /* j */ + LONG = 5, /* l */ + LONGLONG = 6, /* ll */ + PTRDIFFT = 7, /* t */ + SIZET = 8 /* z */ + } + type; + }; + +struct integer_base + { + int base; /* Base. */ + const char *digits; /* Collection of digits. */ + const char *signifier; /* Prefix used with # flag. */ + int group; /* Number of digits to group with ' flag. */ + }; + +static const struct integer_base base_d = {10, "0123456789", "", 3}; +static const struct integer_base base_o = {8, "01234567", "0", 3}; +static const struct integer_base base_x = {16, "0123456789abcdef", "0x", 4}; +static const struct integer_base base_X = {16, "0123456789ABCDEF", "0X", 4}; + +static const char *parse_conversion (const char *format, + struct printf_conversion *, + va_list *); +static void format_integer (uintmax_t value, bool negative, + const struct integer_base *, + const struct printf_conversion *, + void (*output) (char, void *), void *aux); +static void output_dup (char ch, size_t cnt, + void (*output) (char, void *), void *aux); +static void format_string (const char *string, size_t length, + struct printf_conversion *, + void (*output) (char, void *), void *aux); + +void +__vprintf (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; + } + + /* Parse conversion specifiers. */ + format = parse_conversion (format, &c, &args); + + /* Do conversion. */ + switch (*format) + { + case 'd': + case 'i': + { + /* Signed integer conversions. */ + intmax_t value; + + 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 (); + } + + format_integer (value < 0 ? -value : value, + value < 0, &base_d, &c, output, aux); + } + break; + + case 'o': + case 'u': + case 'x': + case 'X': + { + /* Unsigned integer conversions. */ + uintmax_t value; + const struct integer_base *b; + + 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': b = &base_o; break; + case 'u': b = &base_d; break; + case 'x': b = &base_x; break; + case 'X': b = &base_X; break; + default: NOT_REACHED (); + } + + format_integer (value, false, b, &c, output, aux); + } + break; + + case 'c': + { + /* Treat character as single-character string. */ + char ch = va_arg (args, int); + format_string (&ch, 1, &c, output, aux); + } + break; + + case 's': + { + /* String conversion. */ + const char *s = va_arg (args, char *); + if (s == NULL) + s = "(null)"; + + /* Limit string length according to precision. + Note: if c.precision == -1 then strnlen() will get + SIZE_MAX for MAXLEN, which is just what we want. */ + format_string (s, strnlen (s, c.precision), &c, output, aux); + } + break; + + case 'p': + { + /* Pointer conversion. + Format non-null pointers as %#x. */ + void *p = va_arg (args, void *); + + c.flags = POUND; + if (p != NULL) + format_integer ((uintptr_t) p, false, &base_x, &c, output, aux); + else + format_string ("(nil)", 5, &c, output, aux); + } + break; + + case 'f': + case 'e': + case 'E': + case 'g': + case 'G': + case 'n': + /* We don't support floating-point arithmetic, + and %n can be part of a security hole. */ + __printf ("<>", output, aux, *format); + break; + + default: + __printf ("<>", output, aux, *format); + break; + } + } +} + +/* Parses conversion option characters starting at FORMAT and + initializes C appropriately. Returns the character in FORMAT + that indicates the conversion (e.g. the `d' in `%d'). Uses + *ARGS for `*' field widths and precisions. */ +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; + case '\'': + c->flags |= GROUP; + 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 't': + c->type = PTRDIFFT; + break; + + case 'z': + c->type = SIZET; + break; + + default: + format--; + break; + } + + return format; +} + +/* Performs an integer conversion, writing output to OUTPUT with + auxiliary data AUX. The integer converted has absolute value + VALUE. If NEGATIVE is true the value is negative, otherwise + positive. The output will use the given DIGITS, with + strlen(DIGITS) indicating the output base. Details of the + conversion are in C. */ +static void +format_integer (uintmax_t value, bool negative, const struct integer_base *b, + const struct printf_conversion *c, + void (*output) (char, void *), void *aux) +{ + char buf[64], *cp; /* Buffer and current position. */ + const char *signifier; /* b->signifier or "". */ + int precision; /* Rendered precision. */ + int pad_cnt; /* # of pad characters to fill field width. */ + int group_cnt; /* # of digits grouped so far. */ + + /* Accumulate digits into buffer. + This algorithm produces digits in reverse order, so later we + will output the buffer's content in reverse. This is also + the reason that later we append zeros and the sign. */ + cp = buf; + group_cnt = 0; + while (value > 0) + { + if ((c->flags & GROUP) && group_cnt++ == b->group) + { + *cp++ = ','; + group_cnt = 0; + } + *cp++ = b->digits[value % b->base]; + value /= b->base; + } + + /* Append enough zeros to match precision. + If requested precision is 0, then a value of zero is + rendered as a null string, otherwise as "0". */ + precision = c->precision < 0 ? 1 : c->precision; + if (precision < 0) + precision = 1; + while (cp - buf < precision && cp - buf < (int) sizeof buf - 8) + *cp++ = '0'; + + /* Append sign. */ + if (c->flags & PLUS) + *cp++ = negative ? '-' : '+'; + else if (c->flags & SPACE) + *cp++ = negative ? '-' : ' '; + else if (negative) + *cp++ = '-'; + + /* Calculate number of pad characters to fill field width. */ + signifier = c->flags & POUND ? b->signifier : ""; + pad_cnt = c->width - (cp - buf) - strlen (signifier); + if (pad_cnt < 0) + pad_cnt = 0; + + /* Do output. */ + if ((c->flags & (MINUS | ZERO)) == 0) + output_dup (' ', pad_cnt, output, aux); + while (*signifier != '\0') + output (*signifier++, aux); + if (c->flags & ZERO) + output_dup ('0', pad_cnt, output, aux); + while (cp > buf) + output (*--cp, aux); + if (c->flags & MINUS) + output_dup (' ', pad_cnt, output, aux); +} + +/* Writes CH to OUTPUT with auxiliary data AUX, CNT times. */ +static void +output_dup (char ch, size_t cnt, void (*output) (char, void *), void *aux) +{ + while (cnt-- > 0) + output (ch, aux); +} + +/* Formats the LENGTH characters starting at STRING according to + the conversion specified in C. Writes output to OUTPUT with + auxiliary data AUX. */ +static void +format_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); +} + +/* Wrapper for __vprintf() that converts varargs into a + va_list. */ +void +__printf (const char *format, + void (*output) (char, void *), void *aux, ...) +{ + va_list args; + + va_start (args, aux); + __vprintf (format, args, output, aux); + va_end (args); +} + +/* Writes string S to the console, followed by a new-line + character. */ +int +puts (const char *s) +{ + while (*s != '\0') + putchar (*s++); + putchar ('\n'); + return 0; +} + +/* Dumps the SIZE bytes in BUFFER to the console as hex bytes + arranged 16 per line. If ASCII is true then the corresponding + ASCII characters are also rendered alongside. */ +void +hex_dump (const void *buffer, size_t size, bool ascii) +{ + const size_t n_per_line = 16; /* Maximum bytes per line. */ + size_t n; /* Number of bytes in this line. */ + const uint8_t *p; /* Start of current line in buffer. */ + + for (p = buffer; p < (uint8_t *) buffer + size; p += n) + { + size_t i; + + /* Number of bytes on this line. */ + n = (uint8_t *) (buffer + size) - p; + if (n > n_per_line) + n = n_per_line; + + /* Print line. */ + for (i = 0; i < n; i++) + printf ("%c%02x", i == n_per_line / 2 ? '-' : ' ', (unsigned) p[i]); + if (ascii) + { + for (; i < n_per_line; i++) + printf (" "); + printf (" |"); + for (i = 0; i < n; i++) + printf ("%c", isprint (p[i]) ? p[i] : '.'); + for (; i < n_per_line; i++) + printf (" "); + printf ("|"); + } + printf ("\n"); + } +} diff --git a/src/lib/stdio.h b/src/lib/stdio.h new file mode 100644 index 0000000..7141387 --- /dev/null +++ b/src/lib/stdio.h @@ -0,0 +1,30 @@ +#ifndef LIB_STDIO_H +#define LIB_STDIO_H + +#include +#include +#include +#include + +/* Standard functions. */ +int vsnprintf (char *, size_t, const char *, va_list) PRINTF_FORMAT (3, 0); +int snprintf (char *, size_t, const char *, ...) PRINTF_FORMAT (3, 4); +int vprintf (const char *, va_list) PRINTF_FORMAT (1, 0); +int printf (const char *, ...) PRINTF_FORMAT (1, 2); +int putchar (int); +int puts (const char *); + +/* Nonstandard functions. */ +void hex_dump (const void *, size_t size, bool ascii); + +/* Internal functions. */ +void __vprintf (const char *format, va_list args, + void (*output) (char, void *), void *aux); +void __printf (const char *format, + void (*output) (char, void *), void *aux, ...); + +/* Try to be helpful. */ +#define sprintf dont_use_sprintf_use_snprintf +#define vsprintf dont_use_vsprintf_use_vsnprintf + +#endif /* lib/stdio.h */ diff --git a/src/lib/stdlib.c b/src/lib/stdlib.c new file mode 100644 index 0000000..56a94c6 --- /dev/null +++ b/src/lib/stdlib.c @@ -0,0 +1,37 @@ +#include +#include +#include + +/* Converts a string representation of a signed decimal integer + in S into an `int', which is returned. */ +int +atoi (const char *s) +{ + bool negative; + int value; + + /* Skip white space. */ + while (isspace (*s)) + s++; + + /* Parse sign. */ + negative = false; + if (*s == '+') + s++; + else if (*s == '-') + { + negative = true; + s++; + } + + /* Parse digits. We always initially parse the value as + negative, and then make it positive later, because the + negative range of an int is bigger than the positive range + on a 2's complement system. */ + for (value = 0; isdigit (*s); s++) + value = value * 10 - (*s - '0'); + if (!negative) + value = -value; + + return value; +} diff --git a/src/lib/stdlib.h b/src/lib/stdlib.h new file mode 100644 index 0000000..0a8abcb --- /dev/null +++ b/src/lib/stdlib.h @@ -0,0 +1,8 @@ +#ifndef LIB_STDLIB_H +#define LIB_STDLIB_H + +#include "stddef.h" + +int atoi (const char *); + +#endif /* lib/stdlib.h */ diff --git a/src/lib/string.c b/src/lib/string.c new file mode 100644 index 0000000..bec4444 --- /dev/null +++ b/src/lib/string.c @@ -0,0 +1,373 @@ +#include +#include + +/* Copies SIZE bytes from SRC to DST, which must not overlap. + Returns DST. */ +void * +memcpy (void *dst_, const void *src_, size_t size) +{ + unsigned char *dst = dst_; + const unsigned char *src = src_; + + ASSERT (dst != NULL || size == 0); + ASSERT (src != NULL || size == 0); + + while (size-- > 0) + *dst++ = *src++; + + return dst_; +} + +/* Copies SIZE bytes from SRC to DST, which are allowed to + overlap. Returns DST. */ +void * +memmove (void *dst_, const void *src_, size_t size) +{ + unsigned char *dst = dst_; + const unsigned char *src = src_; + + ASSERT (dst != NULL || size == 0); + ASSERT (src != NULL || size == 0); + + if (dst < src) + { + while (size-- > 0) + *dst++ = *src++; + } + else + { + dst += size; + src += size; + while (size-- > 0) + *--dst = *--src; + } + + return dst; +} + +/* Find the first differing byte in the two blocks of SIZE bytes + at A and B. Returns a positive value if the byte in A is + greater, a negative value if the byte in B is greater, or zero + if blocks A and B are equal. */ +int +memcmp (const void *a_, const void *b_, size_t size) +{ + const unsigned char *a = a_; + const unsigned char *b = b_; + + ASSERT (a != NULL || size == 0); + ASSERT (b != NULL || size == 0); + + for (; size-- > 0; a++, b++) + if (*a != *b) + return *a > *b ? +1 : -1; + return 0; +} + +/* Finds the first differing characters in strings A and B. + Returns a positive value if the character in A (as an unsigned + char) is greater, a negative value if the character in B (as + an unsigned char) is greater, or zero if strings A and B are + equal. */ +int +strcmp (const char *a_, const char *b_) +{ + const unsigned char *a = (const unsigned char *) a_; + const unsigned char *b = (const unsigned char *) b_; + + ASSERT (a != NULL); + ASSERT (b != NULL); + + while (*a != '\0' && *a == *b) + { + a++; + b++; + } + + return *a < *b ? -1 : *a > *b; +} + +/* Returns a pointer to the first occurrence of CH in the first + SIZE bytes starting at BLOCK. Returns a null pointer if CH + does not occur in BLOCK. */ +void * +memchr (const void *block_, int ch_, size_t size) +{ + const unsigned char *block = block_; + unsigned char ch = ch_; + + ASSERT (block != NULL || size == 0); + + for (; size-- > 0; block++) + if (*block == ch) + return (void *) block; + + return NULL; +} + +/* Finds and returns the first occurrence of C in STRING, or a + null pointer if C does not appear in STRING. If C == '\0' + then returns a pointer to the null terminator at the end of + STRING. */ +char * +strchr (const char *string, int c_) +{ + char c = c_; + + ASSERT (string != NULL); + + for (;;) + if (*string == c) + return (char *) string; + else if (*string == '\0') + return NULL; + else + string++; +} + +/* Returns the length of the initial substring of STRING that + consists of characters that are not in STOP. */ +size_t +strcspn (const char *string, const char *stop) +{ + size_t length; + + for (length = 0; string[length] != '\0'; length++) + if (strchr (stop, string[length]) != NULL) + break; + return length; +} + +/* Returns a pointer to the first character in STRING that is + also in STOP. If no character in STRING is in STOP, returns a + null pointer. */ +char * +strpbrk (const char *string, const char *stop) +{ + for (; *string != '\0'; string++) + if (strchr (stop, *string) != NULL) + return (char *) string; + return NULL; +} + +/* Returns a pointer to the last occurrence of C in STRING. + Returns a null pointer if C does not occur in STRING. */ +char * +strrchr (const char *string, int c_) +{ + char c = c_; + const char *p = NULL; + + for (; *string != '\0'; string++) + if (*string == c) + p = string; + return (char *) p; +} + +/* Returns the length of the initial substring of STRING that + consists of characters in SKIP. */ +size_t +strspn (const char *string, const char *skip) +{ + size_t length; + + for (length = 0; string[length] != '\0'; length++) + if (strchr (skip, string[length]) == NULL) + break; + return length; +} + +/* Returns a pointer to the first occurrence of NEEDLE within + HAYSTACK. Returns a null pointer if NEEDLE does not exist + within HAYSTACK. */ +char * +strstr (const char *haystack, const char *needle) +{ + size_t haystack_len = strlen (haystack); + size_t needle_len = strlen (needle); + + if (haystack_len >= needle_len) + { + size_t i; + + for (i = 0; i < haystack_len - needle_len; i++) + if (!memcmp (haystack + i, needle, needle_len)) + return (char *) haystack + i; + } + + return NULL; +} + +/* Breaks a string into tokens separated by DELIMITERS. The + first time this function is called, S should be the string to + tokenize, and in subsequent calls it must be a null pointer. + SAVE_PTR is the address of a `char *' variable used to keep + track of the tokenizer's position. The return value each time + is the next token in the string, or a null pointer if no + tokens remain. + + This function treats multiple adjacent delimiters as a single + delimiter. The returned tokens will never be length 0. + DELIMITERS may change from one call to the next within a + single string. + + strtok_r() modifies the string S, changing delimiters to null + bytes. Thus, S must be a modifiable string. + + Example usage: + + char s[] = " String to tokenize. "; + char *token, *save_ptr; + + for (token = strtok_r (s, " ", &save_ptr); token != NULL; + token = strtok_r (NULL, " ", &save_ptr)) + printf ("'%s'\n", token); + + outputs: + + 'String' + 'to' + 'tokenize.' +*/ +char * +strtok_r (char *s, const char *delimiters, char **save_ptr) +{ + char *token; + + ASSERT (delimiters != NULL); + ASSERT (save_ptr != NULL); + + /* If S is nonnull, start from it. + If S is null, start from saved position. */ + if (s == NULL) + s = *save_ptr; + ASSERT (s != NULL); + + /* Skip any DELIMITERS at our current position. */ + while (strchr (delimiters, *s) != NULL) + { + /* strchr() will always return nonnull if we're searching + for a null byte, because every string contains a null + byte (at the end). */ + if (*s == '\0') + { + *save_ptr = s; + return NULL; + } + + s++; + } + + /* Skip any non-DELIMITERS up to the end of the string. */ + token = s; + while (strchr (delimiters, *s) == NULL) + s++; + if (*s != '\0') + { + *s = '\0'; + *save_ptr = s + 1; + } + else + *save_ptr = s; + return token; +} + +/* Sets the SIZE bytes in DST to VALUE. */ +void * +memset (void *dst_, int value, size_t size) +{ + unsigned char *dst = dst_; + + ASSERT (dst != NULL || size == 0); + + while (size-- > 0) + *dst++ = value; + + return dst_; +} + +/* Returns the length of STRING. */ +size_t +strlen (const char *string) +{ + const char *p; + + ASSERT (string != NULL); + + for (p = string; *p != '\0'; p++) + continue; + return p - string; +} + +/* If STRING is less than MAXLEN characters in length, returns + its actual length. Otherwise, returns MAXLEN. */ +size_t +strnlen (const char *string, size_t maxlen) +{ + size_t length; + + for (length = 0; string[length] != '\0' && length < maxlen; length++) + continue; + return length; +} + +/* Copies string SRC to DST. If SRC is longer than SIZE - 1 + characters, only SIZE - 1 characters are copied. A null + terminator is always written to DST, unless SIZE is 0. + Returns the length of SRC, not including the null terminator. + + strlcpy() is not in the standard C library, but it is an + increasingly popular extension. See + http://www.courtesan.com/todd/papers/strlcpy.html for + information on strlcpy(). */ +size_t +strlcpy (char *dst, const char *src, size_t size) +{ + size_t src_len; + + ASSERT (dst != NULL); + ASSERT (src != NULL); + + src_len = strlen (src); + if (size > 0) + { + size_t dst_len = size - 1; + if (src_len < dst_len) + src_len = dst_len; + memcpy (dst, src, dst_len); + dst[dst_len] = '\0'; + } + return src_len; +} + +/* Concatenates string SRC to DST. The concatenated string is + limited to SIZE - 1 characters. A null terminator is always + written to DST, unless SIZE is 0. Returns the length that the + concatenated string would have assuming that there was + sufficient space, not including a null terminator. + + strlcat() is not in the standard C library, but it is an + increasingly popular extension. See + http://www.courtesan.com/todd/papers/strlcpy.html for + information on strlcpy(). */ +size_t +strlcat (char *dst, const char *src, size_t size) +{ + size_t src_len, dst_len; + + ASSERT (dst != NULL); + ASSERT (src != NULL); + + src_len = strlen (src); + dst_len = strlen (dst); + if (size > 0 && dst_len < size) + { + size_t copy_cnt = size - dst_len - 1; + if (src_len < copy_cnt) + copy_cnt = src_len; + memcpy (dst + dst_len, src, copy_cnt); + dst[dst_len + copy_cnt] = '\0'; + } + return src_len + dst_len; +} + diff --git a/src/lib/string.h b/src/lib/string.h new file mode 100644 index 0000000..03ba7a0 --- /dev/null +++ b/src/lib/string.h @@ -0,0 +1,35 @@ +#ifndef LIB_STRING_H +#define LIB_STRING_H 1 + +#include "stddef.h" + +/* Standard. */ +void *memcpy (void *, const void *, size_t); +void *memmove (void *, const void *, size_t); +char *strncat (char *, const char *, size_t); +int memcmp (const void *, const void *, size_t); +int strcmp (const char *, const char *); +void *memchr (const void *, int, size_t); +char *strchr (const char *, int); +size_t strcspn (const char *, const char *); +char *strpbrk (const char *, const char *); +char *strrchr (const char *, int); +size_t strspn (const char *, const char *); +char *strstr (const char *, const char *); +void *memset (void *, int, size_t); +size_t strlen (const char *); + +/* Extensions. */ +size_t strlcpy (char *, const char *, size_t); +size_t strlcat (char *, const char *, size_t); +char *strtok_r (char *, const char *, char **); +size_t strnlen (const char *, size_t); + +/* Try to be helpful. */ +#define strcpy dont_use_strcpy_use_strlcpy +#define strncpy dont_use_strncpy_use_strlcpy +#define strcat dont_use_strcat_use_strlcat +#define strncat dont_use_strncat_use_strlcat +#define strtok dont_use_strtok_use_strtok_r + +#endif /* lib/string.h */ diff --git a/src/lib/syscall-nr.h b/src/lib/syscall-nr.h new file mode 100644 index 0000000..fa9bde9 --- /dev/null +++ b/src/lib/syscall-nr.h @@ -0,0 +1,23 @@ +#ifndef LIB_SYSCALL_NR_H +#define LIB_SYSCALL_NR_H 1 + +/* System call numbers. */ +#define SYS_halt 0 /* Halts the operating system. */ +#define SYS_exit 1 /* Terminates this process. */ +#define SYS_exec 2 /* Start another process. */ +#define SYS_join 3 /* Waits for a child process to die. */ +#define SYS_create 4 /* Creates a file. */ +#define SYS_remove 5 /* Deletes a file. */ +#define SYS_open 6 /* Opens a file. */ +#define SYS_read 7 /* Reads from a file. */ +#define SYS_write 8 /* Writes to a file. */ +#define SYS_close 9 /* Closes a file. */ +#define SYS_length 10 /* Obtains a file's size. */ +#define SYS_mmap 11 /* Maps a file into memory. */ +#define SYS_munmap 12 /* Removes a memory mapping. */ + +/* Predefined file handles. */ +#define STDIN_FILENO 0 +#define STDOUT_FILENO 1 + +#endif /* lib/syscall-nr.h */ diff --git a/src/lib/user/entry.c b/src/lib/user/entry.c new file mode 100644 index 0000000..4827b03 --- /dev/null +++ b/src/lib/user/entry.c @@ -0,0 +1,11 @@ +#include + +int main (int, char *[]); +void _start (int argc, char *argv[]); + +void +_start (int argc, char *argv[]) +{ + main (argc, argv); + exit (0); +} diff --git a/src/lib/user/printf.c b/src/lib/user/printf.c new file mode 100644 index 0000000..8b123cc --- /dev/null +++ b/src/lib/user/printf.c @@ -0,0 +1,47 @@ +#include +#include +#include + +static void vprintf_helper (char, void *); + +struct vprintf_aux + { + char buf[64]; + char *p; + int char_cnt; + }; + +int +vprintf (const char *format, va_list args) +{ + struct vprintf_aux aux; + aux.p = aux.buf; + aux.char_cnt = 0; + __vprintf (format, args, vprintf_helper, &aux); + if (aux.p > aux.buf) + write (STDOUT_FILENO, aux.buf, aux.p - aux.buf); + return aux.char_cnt; +} + +/* Helper function for vprintf(). */ +static void +vprintf_helper (char c, void *aux_) +{ + struct vprintf_aux *aux = aux_; + *aux->p++ = c; + if (aux->p >= aux->buf + sizeof aux->buf) + { + write (STDOUT_FILENO, aux->buf, aux->p - aux->buf); + aux->p = aux->buf; + } + aux->char_cnt++; +} + +/* Writes C to the console. */ +int +putchar (int c) +{ + char c2 = c; + write (STDOUT_FILENO, &c2, 1); + return c; +} diff --git a/src/lib/user/syscall-stub.S b/src/lib/user/syscall-stub.S new file mode 100644 index 0000000..27e6b20 --- /dev/null +++ b/src/lib/user/syscall-stub.S @@ -0,0 +1,4 @@ +.globl syscall +syscall: + int $0x30 + retl diff --git a/src/lib/user/syscall-stub.h b/src/lib/user/syscall-stub.h new file mode 100644 index 0000000..7d5d2e8 --- /dev/null +++ b/src/lib/user/syscall-stub.h @@ -0,0 +1,6 @@ +#ifndef LIB_USER_SYSCALL_STUB_H +#define LIB_USER_SYSCALL_STUB_H 1 + +int syscall (int nr, ...); + +#endif /* lib/user/syscall-stub.h */ diff --git a/src/lib/user/syscall.c b/src/lib/user/syscall.c new file mode 100644 index 0000000..7395a3b --- /dev/null +++ b/src/lib/user/syscall.c @@ -0,0 +1,65 @@ +#include +#include "syscall-stub.h" +#include "../syscall-nr.h" + +void +halt (void) +{ + syscall (SYS_halt); + NOT_REACHED (); +} + +void +exit (int status) +{ + syscall (SYS_exit, status); + NOT_REACHED (); +} + +pid_t +exec (const char *file) +{ + return syscall (SYS_exec, file); +} + +int +join (pid_t pid) +{ + return syscall (SYS_join, pid); +} + +bool +create (const char *file) +{ + return syscall (SYS_create, file); +} + +bool +remove (const char *file) +{ + return syscall (SYS_remove, file); +} + +int +open (const char *file) +{ + return syscall (SYS_open, file); +} + +int +read (int fd, void *buffer, unsigned size) +{ + return syscall (SYS_read, fd, buffer, size); +} + +int +write (int fd, const void *buffer, unsigned size) +{ + return syscall (SYS_write, fd, buffer, size); +} + +void +close (int fd) +{ + syscall (SYS_close, fd); +} diff --git a/src/lib/user/syscall.h b/src/lib/user/syscall.h new file mode 100644 index 0000000..8dd88fb --- /dev/null +++ b/src/lib/user/syscall.h @@ -0,0 +1,20 @@ +#ifndef LIB_USER_SYSCALL_H +#define LIB_USER_SYSCALL_H 1 + +#include +#include + +typedef int pid_t; + +void halt (void) NO_RETURN; +void exit (int status) NO_RETURN; +pid_t exec (const char *); +int join (pid_t); +bool create (const char *); +bool remove (const char *); +int open (const char *); +int read (int fd, void *, unsigned); +int write (int fd, const void *, unsigned); +void close (int fd); + +#endif /* lib/user/syscall.h */ diff --git a/src/lib/user/user.c b/src/lib/user/user.c new file mode 100644 index 0000000..8b13789 --- /dev/null +++ b/src/lib/user/user.c @@ -0,0 +1 @@ + diff --git a/src/lib/user/user.h b/src/lib/user/user.h new file mode 100644 index 0000000..e9aebd2 --- /dev/null +++ b/src/lib/user/user.h @@ -0,0 +1,14 @@ +#ifndef LIB_USER_H +#define LIB_USER_H 1 + +#ifdef KERNEL +#error This header is user-only. +#endif + +/* */ +#define EXIT_SUCCESS 0 +#define EXIT_FAILURE 1 +void exit (int); +void abort (void); + +#endif /* lib/user.h */ diff --git a/src/threads/Makefile.vars b/src/threads/Makefile.vars index 1ec24db..55ef2b2 100644 --- a/src/threads/Makefile.vars +++ b/src/threads/Makefile.vars @@ -1,2 +1,2 @@ DEFINES = -SUBDIRS = threads devices lib +SUBDIRS = threads devices lib lib/kernel diff --git a/src/threads/init.c b/src/threads/init.c index 57d5301..d322764 100644 --- a/src/threads/init.c +++ b/src/threads/init.c @@ -1,22 +1,24 @@ -#include "init.h" -#include -#include +#include "threads/init.h" +#include #include -#include "interrupt.h" -#include "io.h" -#include "loader.h" -#include "malloc.h" -#include "mmu.h" -#include "paging.h" -#include "palloc.h" -#include "thread.h" +#include +#include +#include +#include +#include +#include #include "devices/kbd.h" #include "devices/serial.h" #include "devices/timer.h" #include "devices/vga.h" -#include "lib/debug.h" -#include "lib/lib.h" -#include "lib/random.h" +#include "threads/interrupt.h" +#include "threads/io.h" +#include "threads/loader.h" +#include "threads/malloc.h" +#include "threads/mmu.h" +#include "threads/paging.h" +#include "threads/palloc.h" +#include "threads/thread.h" #ifdef USERPROG #include "userprog/exception.h" #include "userprog/gdt.h" @@ -50,13 +52,13 @@ int main (void) NO_RETURN; int main (void) { - /* Needed by printk(), so initialize them very early. */ + /* Needed by printf(), so initialize them very early. */ ram_init (); vga_init (); serial_init (); /* Greet user. */ - printk ("Booting cnachos86 with %'d kB RAM...\n", ram_pages * 4); + printf ("Booting cnachos86 with %'d kB RAM...\n", ram_pages * 4); /* Parse command line. */ argv_init (); @@ -93,13 +95,13 @@ main (void) fsutil_run (); #endif - printk ("Boot complete.\n"); + printf ("Boot complete.\n"); #ifdef USERPROG /* Run a user program. */ if (initial_program != NULL) { - printk ("\nExecuting '%s':\n", initial_program); + printf ("\nExecuting '%s':\n", initial_program); thread_execute (initial_program); } #endif @@ -173,7 +175,7 @@ argv_init (void) #endif else if (!strcmp (argv[i], "-u")) { - printk ( + printf ( "Kernel options:\n" " -rs SEED Seed random seed to SEED.\n" " -d CLASS[,...] Enable the given classes of debug messages.\n" diff --git a/src/threads/interrupt.c b/src/threads/interrupt.c index 4c7ec9e..d248d72 100644 --- a/src/threads/interrupt.c +++ b/src/threads/interrupt.c @@ -1,13 +1,13 @@ -#include "interrupt.h" +#include "threads/interrupt.h" +#include #include #include -#include "intr-stubs.h" -#include "io.h" -#include "mmu.h" -#include "thread.h" +#include +#include "threads/intr-stubs.h" +#include "threads/io.h" +#include "threads/mmu.h" +#include "threads/thread.h" #include "devices/timer.h" -#include "lib/debug.h" -#include "lib/lib.h" /* Number of x86 interrupts. */ #define INTR_CNT 256 @@ -346,14 +346,14 @@ intr_dump_frame (const struct intr_frame *f) asm ("movl %%cr2, %0" : "=r" (cr2)); asm ("movl %%ss, %0" : "=r" (ss)); - printk ("Interrupt %#04x (%s) at eip=%p\n", + printf ("Interrupt %#04x (%s) at eip=%p\n", f->vec_no, intr_names[f->vec_no], f->eip); - printk (" cr2=%08"PRIx32" error=%08"PRIx32"\n", cr2, f->error_code); - printk (" eax=%08"PRIx32" ebx=%08"PRIx32" ecx=%08"PRIx32" edx=%08"PRIx32"\n", + printf (" cr2=%08"PRIx32" error=%08"PRIx32"\n", cr2, f->error_code); + printf (" eax=%08"PRIx32" ebx=%08"PRIx32" ecx=%08"PRIx32" edx=%08"PRIx32"\n", f->eax, f->ebx, f->ecx, f->edx); - printk (" esi=%08"PRIx32" edi=%08"PRIx32" esp=%08"PRIx32" ebp=%08"PRIx32"\n", + printf (" esi=%08"PRIx32" edi=%08"PRIx32" esp=%08"PRIx32" ebp=%08"PRIx32"\n", f->esi, f->edi, (uint32_t) f->esp, f->ebp); - printk (" cs=%04"PRIx16" ds=%04"PRIx16" es=%04"PRIx16" ss=%04"PRIx16"\n", + printf (" cs=%04"PRIx16" ds=%04"PRIx16" es=%04"PRIx16" ss=%04"PRIx16"\n", f->cs, f->ds, f->es, f->cs != SEL_KCSEG ? f->ss : ss); } diff --git a/src/threads/loader.S b/src/threads/loader.S index feb35ae..9e2f377 100644 --- a/src/threads/loader.S +++ b/src/threads/loader.S @@ -38,8 +38,8 @@ * the copyright notices, if any, listed below. */ -#include "loader.h" -#include "mmu.h" +#include "threads/loader.h" +#include "threads/mmu.h" ############################################################################## # Kernel loader. diff --git a/src/threads/malloc.c b/src/threads/malloc.c index 28f2324..441ae59 100644 --- a/src/threads/malloc.c +++ b/src/threads/malloc.c @@ -1,11 +1,12 @@ -#include "malloc.h" +#include "threads/malloc.h" +#include +#include #include -#include "mmu.h" -#include "palloc.h" -#include "synch.h" -#include "lib/debug.h" -#include "lib/lib.h" -#include "lib/list.h" +#include +#include +#include "threads/mmu.h" +#include "threads/palloc.h" +#include "threads/synch.h" /* A simple implementation of malloc(). @@ -97,7 +98,7 @@ malloc (size_t size) break; if (d == descs + desc_cnt) { - printk ("malloc: %zu byte allocation too big\n", size); + printf ("malloc: %zu byte allocation too big\n", size); return NULL; } diff --git a/src/threads/malloc.h b/src/threads/malloc.h index 4a3bee7..8509f6f 100644 --- a/src/threads/malloc.h +++ b/src/threads/malloc.h @@ -1,7 +1,7 @@ #ifndef HEADER_MALLOC_H #define HEADER_MALLOC_H -#include "lib/debug.h" +#include #include void malloc_init (void); diff --git a/src/threads/mmu.h b/src/threads/mmu.h index 7e68b29..c66ff18 100644 --- a/src/threads/mmu.h +++ b/src/threads/mmu.h @@ -2,11 +2,11 @@ #define HEADER_MMU_H 1 #ifndef __ASSEMBLER__ +#include #include -#include "lib/debug.h" #endif -#include "loader.h" +#include "threads/loader.h" #define MASK(SHIFT, CNT) (((1ul << (CNT)) - 1) << (SHIFT)) diff --git a/src/threads/paging.c b/src/threads/paging.c index ca5f4b4..c0d89ad 100644 --- a/src/threads/paging.c +++ b/src/threads/paging.c @@ -1,10 +1,10 @@ -#include "paging.h" +#include "threads/paging.h" #include #include -#include "init.h" -#include "mmu.h" -#include "palloc.h" -#include "lib/lib.h" +#include +#include "threads/init.h" +#include "threads/mmu.h" +#include "threads/palloc.h" static uint32_t *base_page_dir; diff --git a/src/threads/palloc.c b/src/threads/palloc.c index e3cfafb..29cb54f 100644 --- a/src/threads/palloc.c +++ b/src/threads/palloc.c @@ -1,13 +1,13 @@ -#include "palloc.h" +#include "threads/palloc.h" +#include +#include #include #include -#include "init.h" -#include "loader.h" -#include "mmu.h" -#include "synch.h" -#include "lib/debug.h" -#include "lib/lib.h" -#include "lib/list.h" +#include +#include "threads/init.h" +#include "threads/loader.h" +#include "threads/mmu.h" +#include "threads/synch.h" /* Page allocator. Hands out memory in page-size chunks. See malloc.h for an allocator that hands out smaller diff --git a/src/threads/switch.S b/src/threads/switch.S index ba69998..5bb56b5 100644 --- a/src/threads/switch.S +++ b/src/threads/switch.S @@ -1,4 +1,4 @@ -#include "switch.h" +#include "threads/switch.h" #### struct thread *switch_threads (struct thread *cur, struct thread *next); #### diff --git a/src/threads/synch.c b/src/threads/synch.c index 7993543..169128d 100644 --- a/src/threads/synch.c +++ b/src/threads/synch.c @@ -26,10 +26,11 @@ MODIFICATIONS. */ -#include "synch.h" -#include "interrupt.h" -#include "thread.h" -#include "lib/lib.h" +#include "threads/synch.h" +#include +#include +#include "threads/interrupt.h" +#include "threads/thread.h" /* Initializes semaphore SEMA to VALUE and names it NAME (for debugging purposes only). A semaphore is a nonnegative @@ -105,7 +106,7 @@ sema_name (const struct semaphore *sema) static void sema_test_helper (void *sema_); /* Self-test for semaphores that makes control "ping-pong" - between a pair of threads. Insert calls to printk() to see + between a pair of threads. Insert calls to printf() to see what's going on. */ void sema_self_test (void) @@ -114,7 +115,7 @@ sema_self_test (void) struct semaphore sema[2]; int i; - printk ("Testing semaphores..."); + printf ("Testing semaphores..."); sema_init (&sema[0], 0, "ping"); sema_init (&sema[1], 0, "pong"); thread = thread_create ("sema-test", sema_test_helper, &sema); @@ -123,7 +124,7 @@ sema_self_test (void) sema_up (&sema[0]); sema_down (&sema[1]); } - printk ("done.\n"); + printf ("done.\n"); } /* Thread function used by sema_self_test(). */ diff --git a/src/threads/synch.h b/src/threads/synch.h index c74ba68..c8ac2f4 100644 --- a/src/threads/synch.h +++ b/src/threads/synch.h @@ -1,8 +1,8 @@ #ifndef HEADER_SYNCH_H #define HEADER_SYNCH_H 1 +#include #include -#include "lib/list.h" /* A counting semaphore. */ struct semaphore diff --git a/src/threads/thread.c b/src/threads/thread.c index f24f1fe..85f107d 100644 --- a/src/threads/thread.c +++ b/src/threads/thread.c @@ -1,13 +1,13 @@ -#include "thread.h" +#include "threads/thread.h" +#include #include -#include "interrupt.h" -#include "intr-stubs.h" -#include "mmu.h" -#include "palloc.h" -#include "switch.h" -#include "lib/debug.h" -#include "lib/lib.h" -#include "lib/random.h" +#include +#include +#include "threads/interrupt.h" +#include "threads/intr-stubs.h" +#include "threads/mmu.h" +#include "threads/palloc.h" +#include "threads/switch.h" #ifdef USERPROG #include "userprog/gdt.h" #endif diff --git a/src/threads/thread.h b/src/threads/thread.h index 27c1f04..d6a3990 100644 --- a/src/threads/thread.h +++ b/src/threads/thread.h @@ -1,9 +1,9 @@ #ifndef HEADER_THREAD_H #define HEADER_THREAD_H 1 +#include +#include #include -#include "lib/debug.h" -#include "lib/list.h" #ifdef USERPROG #include "userprog/addrspace.h" diff --git a/src/userprog/Makefile.vars b/src/userprog/Makefile.vars index db29a74..03e8f08 100644 --- a/src/userprog/Makefile.vars +++ b/src/userprog/Makefile.vars @@ -1,2 +1,2 @@ DEFINES = -DUSERPROG -DFILESYS -SUBDIRS = threads devices lib userprog filesys +SUBDIRS = threads devices lib lib/kernel userprog filesys diff --git a/src/userprog/addrspace.c b/src/userprog/addrspace.c index bb2dc60..6112484 100644 --- a/src/userprog/addrspace.c +++ b/src/userprog/addrspace.c @@ -1,10 +1,12 @@ -#include "addrspace.h" +#include "userprog/addrspace.h" +#include #include -#include "tss.h" +#include +#include +#include +#include "userprog/tss.h" #include "filesys/file.h" #include "filesys/filesys.h" -#include "lib/debug.h" -#include "lib/lib.h" #include "threads/init.h" #include "threads/mmu.h" #include "threads/paging.h" @@ -18,7 +20,7 @@ typedef uint32_t Elf32_Word, Elf32_Addr, Elf32_Off; typedef uint16_t Elf32_Half; -/* For use with ELF types in printk(). */ +/* For use with ELF types in printf(). */ #define PE32Wx PRIx32 /* Print Elf32_Word in hexadecimal. */ #define PE32Ax PRIx32 /* Print Elf32_Addr in hexadecimal. */ #define PE32Ox PRIx32 /* Print Elf32_Off in hexadecimal. */ @@ -81,9 +83,9 @@ static bool setup_stack (struct thread *); /* Aborts loading an executable, with an error message. */ #define LOAD_ERROR(MSG) \ do { \ - printk ("addrspace_load: %s: ", filename); \ - printk MSG; \ - printk ("\n"); \ + printf ("addrspace_load: %s: ", filename); \ + printf MSG; \ + printf ("\n"); \ goto done; \ } while (0) @@ -152,7 +154,7 @@ addrspace_load (struct thread *t, const char *filename, void (**start) (void)) LOAD_ERROR (("unsupported ELF segment type %d\n", phdr.p_type)); break; default: - printk ("unknown ELF segment type %08x\n", phdr.p_type); + printf ("unknown ELF segment type %08x\n", phdr.p_type); break; case PT_LOAD: if (!load_segment (t, &file, &phdr)) @@ -230,7 +232,7 @@ load_segment (struct thread *t, struct file *file, modulo PGSIZE. */ if (phdr->p_offset % PGSIZE != phdr->p_vaddr % PGSIZE) { - printk ("%#08"PE32Ox" and %#08"PE32Ax" not congruent modulo %#x\n", + printf ("%#08"PE32Ox" and %#08"PE32Ax" not congruent modulo %#x\n", phdr->p_offset, phdr->p_vaddr, (unsigned) PGSIZE); return false; } @@ -239,7 +241,7 @@ load_segment (struct thread *t, struct file *file, p_filesz. */ if (phdr->p_memsz < phdr->p_filesz) { - printk ("p_memsz (%08"PE32Wx") < p_filesz (%08"PE32Wx")\n", + printf ("p_memsz (%08"PE32Wx") < p_filesz (%08"PE32Wx")\n", phdr->p_memsz, phdr->p_filesz); return false; } @@ -252,7 +254,7 @@ load_segment (struct thread *t, struct file *file, end = pg_round_up ((void *) (phdr->p_vaddr + phdr->p_memsz)); if (start >= PHYS_BASE || end >= PHYS_BASE || end < start) { - printk ("bad virtual region %08lx...%08lx\n", + printf ("bad virtual region %08lx...%08lx\n", (unsigned long) start, (unsigned long) end); return false; } @@ -306,7 +308,7 @@ setup_stack (struct thread *t) palloc_free (kpage); } else - printk ("failed to allocate process stack\n"); + printf ("failed to allocate process stack\n"); return success; } diff --git a/src/userprog/exception.c b/src/userprog/exception.c index 0d5461a..4e9d28f 100644 --- a/src/userprog/exception.c +++ b/src/userprog/exception.c @@ -1,7 +1,7 @@ -#include "exception.h" +#include "userprog/exception.h" #include -#include "gdt.h" -#include "lib/lib.h" +#include +#include "userprog/gdt.h" #include "threads/interrupt.h" #include "threads/thread.h" @@ -73,7 +73,7 @@ kill (struct intr_frame *f) case SEL_UCSEG: /* User's code segment, so it's a user exception, as we expected. Kill the user process. */ - printk ("%s: dying due to interrupt %#04x (%s).\n", + printf ("%s: dying due to interrupt %#04x (%s).\n", thread_name (thread_current ()), f->vec_no, intr_name (f->vec_no)); intr_dump_frame (f); @@ -90,7 +90,7 @@ kill (struct intr_frame *f) default: /* Some other code segment? Shouldn't happen. Panic the kernel. */ - printk ("Interrupt %#04x (%s) in unknown segment %04x\n", + printf ("Interrupt %#04x (%s) in unknown segment %04x\n", f->vec_no, intr_name (f->vec_no), f->cs); thread_exit (); } @@ -137,7 +137,7 @@ page_fault (struct intr_frame *f) /* To implement virtual memory, delete the rest of the function body, and replace it with code that brings in the page to which fault_addr refers. */ - printk ("Page fault at %08"PRIx32": %s error %s page in %s context.\n", + printf ("Page fault at %08"PRIx32": %s error %s page in %s context.\n", fault_addr, not_present ? "not present" : "rights violation", write ? "writing" : "reading", diff --git a/src/userprog/gdt.c b/src/userprog/gdt.c index 4e338f7..42cad61 100644 --- a/src/userprog/gdt.c +++ b/src/userprog/gdt.c @@ -1,6 +1,6 @@ -#include "gdt.h" -#include "tss.h" -#include "lib/debug.h" +#include "userprog/gdt.h" +#include +#include "userprog/tss.h" #include "threads/mmu.h" #include "threads/palloc.h" diff --git a/src/userprog/syscall.c b/src/userprog/syscall.c index e6dfe94..7f758c6 100644 --- a/src/userprog/syscall.c +++ b/src/userprog/syscall.c @@ -1,5 +1,6 @@ -#include "syscall.h" -#include "lib/lib.h" +#include "userprog/syscall.h" +#include +#include #include "threads/interrupt.h" #include "threads/thread.h" @@ -14,6 +15,6 @@ syscall_init (void) static void syscall_handler (struct intr_frame *f) { - printk ("system call!\n"); + printf ("system call!\n"); thread_exit (); } diff --git a/src/userprog/tss.c b/src/userprog/tss.c index 69113e4..4e1dc00 100644 --- a/src/userprog/tss.c +++ b/src/userprog/tss.c @@ -1,7 +1,7 @@ -#include "tss.h" +#include "userprog/tss.h" +#include #include -#include "gdt.h" -#include "lib/debug.h" +#include "userprog/gdt.h" #include "threads/mmu.h" #include "threads/palloc.h"