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.
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.
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))
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 $@ $<
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
#ifndef HEADER_16550A_H
#define HEADER_16550A_H 1
+#include <debug.h>
#include <stdbool.h>
#include <stdint.h>
-#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
-#include "disk.h"
+#include "devices/disk.h"
+#include <ctype.h>
+#include <debug.h>
#include <stdbool.h>
-#include "timer.h"
-#include "lib/debug.h"
-#include "lib/lib.h"
+#include <stdio.h>
+#include "devices/timer.h"
#include "threads/io.h"
#include "threads/interrupt.h"
#include "threads/synch.h"
\f
/* 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. */
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;
/* Print. */
for (i = 0; i < size; i++)
- printk ("%c", string[i ^ 1]);
+ printf ("%c", string[i ^ 1]);
}
\f
/* Selects device D, waiting for it to become ready, and then
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,
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;
}
sema_up (&c->completion_wait); /* Wake up waiter. */
}
else
- printk ("%s: unexpected interrupt\n", c->name);
+ printf ("%s: unexpected interrupt\n", c->name);
return;
}
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);
-#include "kbd.h"
-#include "lib/debug.h"
-#include "lib/lib.h"
+#include "devices/kbd.h"
+#include <debug.h>
+#include <stdio.h>
#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);
}
-#include "serial.h"
-#include "16550a.h"
-#include "timer.h"
-#include "lib/debug.h"
+#include "devices/serial.h"
+#include <debug.h>
+#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);
-#include "timer.h"
-#include "lib/debug.h"
+#include "devices/timer.h"
+#include <debug.h>
#include "threads/interrupt.h"
#include "threads/io.h"
-#include "vga.h"
+#include "devices/vga.h"
+#include <round.h>
#include <stdint.h>
#include <stddef.h>
-#include "lib/lib.h"
+#include <string.h>
#include "threads/io.h"
#include "threads/mmu.h"
DEFINES = -DUSERPROG -DFILESYS
-SUBDIRS = threads devices lib userprog filesys
+SUBDIRS = threads devices lib lib/kernel userprog filesys
-#include "directory.h"
-#include "file.h"
-#include "fsutil.h"
-#include "lib/lib.h"
+#include "filesys/directory.h"
+#include <stdio.h>
+#include <string.h>
+#include "filesys/file.h"
+#include "filesys/fsutil.h"
#include "threads/malloc.h"
/* Initializes D as a directory that holds ENTRY_CNT entries. */
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
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");
}
}
-#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 <debug.h>
+#include <string.h>
+#include "filesys/directory.h"
+#include "filesys/filehdr.h"
+#include "filesys/filesys.h"
#include "threads/malloc.h"
bool
#include <stdint.h>
#include <stddef.h>
#include "devices/disk.h"
-#include "off_t.h"
+#include "filesys/off_t.h"
struct file
{
-#include "filehdr.h"
-#include "filesys.h"
-#include "lib/bitmap.h"
-#include "lib/debug.h"
-#include "lib/lib.h"
+#include "filesys/filehdr.h"
+#include <bitmap.h>
+#include <debug.h>
+#include <stdio.h>
+#include "filesys/filesys.h"
#include "threads/malloc.h"
/* Allocates sectors from bitmap B for the content of a file
{
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
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");
}
#include <stdbool.h>
#include <stddef.h>
-#include "off_t.h"
+#include "filesys/off_t.h"
#include "devices/disk.h"
/* Number of direct sector pointers in a file header. */
MODIFICATIONS.
*/
-#include "filesys.h"
-#include "file.h"
-#include "filehdr.h"
-#include "directory.h"
+#include "filesys/filesys.h"
+#include <bitmap.h>
+#include <debug.h>
+#include <stdio.h>
+#include <string.h>
+#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.
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;
MUST_SUCCEED (filesys_remove ("foo"));
- printk ("filesys: self test ok\n");
+ printf ("filesys: self test ok\n");
}
\f
/* Formats the filesystem. */
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. */
dir_destroy (&dir);
file_close (&free_map_file);
- printk ("done.\n");
+ printf ("done.\n");
}
/* If SUCCESS is false, panics with an error complaining about
#include <stdbool.h>
#include <stdint.h>
-#include "off_t.h"
+#include "filesys/off_t.h"
/* Disk used for filesystem. */
extern struct disk *filesys_disk;
-#include "fsutil.h"
+#include "filesys/fsutil.h"
+#include <debug.h>
#include <stdbool.h>
-#include "file.h"
-#include "filesys.h"
-#include "lib/debug.h"
-#include "lib/lib.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "filesys/file.h"
+#include "filesys/filesys.h"
#include "threads/mmu.h"
#include "threads/palloc.h"
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);
}
+++ /dev/null
-#include "bitmap.h"
-#include <limits.h>
-#include "debug.h"
-#include "lib.h"
-#include "threads/malloc.h"
-#ifdef FILESYS
-#include "filesys/file.h"
-#endif
-\f
-/* 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;
-}
-\f
-/* 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);
-}
+++ /dev/null
-#ifndef HEADER_BITMAP_H
-#define HEADER_BITMAP_H 1
-
-#include <stdbool.h>
-#include <stddef.h>
-
-/* 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 */
--- /dev/null
+#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 */
-#include "debug.h"
+#include <debug.h>
#include <stdarg.h>
-#include "lib.h"
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <string.h>
+#ifdef KERNEL
#include "threads/interrupt.h"
+#else
+#include <syscall.h>
+#endif
#define MAX_CLASSES 16
static bool all_enabled;
{
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
}
}
{
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");
}
\f
+++ /dev/null
-#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);
-}
-\f
-/* 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);
-}
-
+++ /dev/null
-#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 <stdbool.h>
-#include <stddef.h>
-#include <stdint.h>
-#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 */
--- /dev/null
+#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 */
--- /dev/null
+#include "bitmap.h"
+#include <debug.h>
+#include <limits.h>
+#include <round.h>
+#include <stdio.h>
+#include "threads/malloc.h"
+#ifdef FILESYS
+#include "filesys/file.h"
+#endif
+\f
+/* 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;
+}
+\f
+/* 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);
+}
--- /dev/null
+#ifndef HEADER_BITMAP_H
+#define HEADER_BITMAP_H 1
+
+#include <stdbool.h>
+#include <stddef.h>
+
+/* 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 */
--- /dev/null
+#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);
+}
+\f
+/* 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);
+}
+
--- /dev/null
+#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 <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+#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 */
--- /dev/null
+#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;
+}
--- /dev/null
+#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 <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+
+/* 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 *);
+\f
+/* 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 */
--- /dev/null
+#include <stdarg.h>
+#include <stdio.h>
+
+#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;
+}
+++ /dev/null
-#include "lib.h"
-#include <stdint.h>
-#include <stdarg.h>
-#include <stdbool.h>
-#include <stddef.h>
-#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);
-\f
-/* <string.h> */
-
-/* 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;
-}
-\f
-/* <stdlib.h> */
-
-/* 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;
-}
-\f
-/* <stdio.h> */
-
-/* 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;
-}
-\f
-/* 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);
-}
-\f
-/* 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 ("<<no %%%c in kernel>>", output, aux, *format);
- break;
-
- default:
- printf_core ("<<no %%%c conversion>>", 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);
-}
-\f
-/* 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");
- }
-}
+++ /dev/null
-#ifndef HEADER_LIB_H
-#define HEADER_LIB_H 1
-
-#include <stdarg.h>
-#include <stdbool.h>
-#include <stddef.h>
-#include "debug.h"
-
-/* <string.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 **);
-
-/* <stdlib.h> */
-int atoi (const char *);
-
-/* <stdio.h> */
-int vsnprintf (char *, size_t, const char *, va_list) PRINTF_FORMAT (3, 0);
-int snprintf (char *, size_t, const char *, ...) PRINTF_FORMAT (3, 4);
-
-/* <ctype.h> */
-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);
-}
-\f
-/* 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 */
--- /dev/null
+#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 */
+++ /dev/null
-#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;
-}
+++ /dev/null
-#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 <stdbool.h>
-#include <stddef.h>
-#include <stdint.h>
-
-/* 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 *);
-\f
-/* 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 */
--- /dev/null
+#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 */
--- /dev/null
+#ifndef LIB_STDARG_H
+#define LIB_STDARG_H
+
+/* GCC has <stdarg.h> 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 */
--- /dev/null
+#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 */
--- /dev/null
+#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 */
--- /dev/null
+#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 */
--- /dev/null
+#include <ctype.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <string.h>
+
+/* 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;
+}
+\f
+/* 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 ("<<no %%%c in kernel>>", output, aux, *format);
+ break;
+
+ default:
+ __printf ("<<no %%%c conversion>>", 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;
+}
+\f
+/* 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");
+ }
+}
--- /dev/null
+#ifndef LIB_STDIO_H
+#define LIB_STDIO_H
+
+#include <debug.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdarg.h>
+
+/* 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 */
--- /dev/null
+#include <ctype.h>
+#include <stdlib.h>
+#include <stdbool.h>
+
+/* 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;
+}
--- /dev/null
+#ifndef LIB_STDLIB_H
+#define LIB_STDLIB_H
+
+#include "stddef.h"
+
+int atoi (const char *);
+
+#endif /* lib/stdlib.h */
--- /dev/null
+#include <string.h>
+#include <debug.h>
+
+/* 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;
+}
+
--- /dev/null
+#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 */
--- /dev/null
+#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 */
--- /dev/null
+#include <syscall.h>
+
+int main (int, char *[]);
+void _start (int argc, char *argv[]);
+
+void
+_start (int argc, char *argv[])
+{
+ main (argc, argv);
+ exit (0);
+}
--- /dev/null
+#include <stdio.h>
+#include <syscall.h>
+#include <syscall-nr.h>
+
+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;
+}
--- /dev/null
+.globl syscall
+syscall:
+ int $0x30
+ retl
--- /dev/null
+#ifndef LIB_USER_SYSCALL_STUB_H
+#define LIB_USER_SYSCALL_STUB_H 1
+
+int syscall (int nr, ...);
+
+#endif /* lib/user/syscall-stub.h */
--- /dev/null
+#include <syscall.h>
+#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);
+}
--- /dev/null
+#ifndef LIB_USER_SYSCALL_H
+#define LIB_USER_SYSCALL_H 1
+
+#include <stdbool.h>
+#include <debug.h>
+
+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 */
--- /dev/null
+#ifndef LIB_USER_H
+#define LIB_USER_H 1
+
+#ifdef KERNEL
+#error This header is user-only.
+#endif
+
+/* <stdlib.h> */
+#define EXIT_SUCCESS 0
+#define EXIT_FAILURE 1
+void exit (int);
+void abort (void);
+
+#endif /* lib/user.h */
DEFINES =
-SUBDIRS = threads devices lib
+SUBDIRS = threads devices lib lib/kernel
-#include "init.h"
-#include <stdint.h>
-#include <stddef.h>
+#include "threads/init.h"
+#include <debug.h>
#include <limits.h>
-#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 <random.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
#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"
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 ();
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
#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"
-#include "interrupt.h"
+#include "threads/interrupt.h"
+#include <debug.h>
#include <inttypes.h>
#include <stdint.h>
-#include "intr-stubs.h"
-#include "io.h"
-#include "mmu.h"
-#include "thread.h"
+#include <stdio.h>
+#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
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);
}
* the copyright notices, if any, listed below.
*/
-#include "loader.h"
-#include "mmu.h"
+#include "threads/loader.h"
+#include "threads/mmu.h"
##############################################################################
# Kernel loader.
-#include "malloc.h"
+#include "threads/malloc.h"
+#include <debug.h>
+#include <list.h>
#include <stdint.h>
-#include "mmu.h"
-#include "palloc.h"
-#include "synch.h"
-#include "lib/debug.h"
-#include "lib/lib.h"
-#include "lib/list.h"
+#include <stdio.h>
+#include <string.h>
+#include "threads/mmu.h"
+#include "threads/palloc.h"
+#include "threads/synch.h"
/* A simple implementation of malloc().
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;
}
#ifndef HEADER_MALLOC_H
#define HEADER_MALLOC_H
-#include "lib/debug.h"
+#include <debug.h>
#include <stddef.h>
void malloc_init (void);
#define HEADER_MMU_H 1
#ifndef __ASSEMBLER__
+#include <debug.h>
#include <stdint.h>
-#include "lib/debug.h"
#endif
-#include "loader.h"
+#include "threads/loader.h"
#define MASK(SHIFT, CNT) (((1ul << (CNT)) - 1) << (SHIFT))
-#include "paging.h"
+#include "threads/paging.h"
#include <stdbool.h>
#include <stddef.h>
-#include "init.h"
-#include "mmu.h"
-#include "palloc.h"
-#include "lib/lib.h"
+#include <string.h>
+#include "threads/init.h"
+#include "threads/mmu.h"
+#include "threads/palloc.h"
static uint32_t *base_page_dir;
-#include "palloc.h"
+#include "threads/palloc.h"
+#include <debug.h>
+#include <list.h>
#include <stddef.h>
#include <stdint.h>
-#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 <string.h>
+#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
-#include "switch.h"
+#include "threads/switch.h"
#### struct thread *switch_threads (struct thread *cur, struct thread *next);
####
MODIFICATIONS.
*/
-#include "synch.h"
-#include "interrupt.h"
-#include "thread.h"
-#include "lib/lib.h"
+#include "threads/synch.h"
+#include <stdio.h>
+#include <string.h>
+#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
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)
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);
sema_up (&sema[0]);
sema_down (&sema[1]);
}
- printk ("done.\n");
+ printf ("done.\n");
}
/* Thread function used by sema_self_test(). */
#ifndef HEADER_SYNCH_H
#define HEADER_SYNCH_H 1
+#include <list.h>
#include <stdbool.h>
-#include "lib/list.h"
/* A counting semaphore. */
struct semaphore
-#include "thread.h"
+#include "threads/thread.h"
+#include <debug.h>
#include <stddef.h>
-#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 <random.h>
+#include <string.h>
+#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
#ifndef HEADER_THREAD_H
#define HEADER_THREAD_H 1
+#include <debug.h>
+#include <list.h>
#include <stdint.h>
-#include "lib/debug.h"
-#include "lib/list.h"
#ifdef USERPROG
#include "userprog/addrspace.h"
DEFINES = -DUSERPROG -DFILESYS
-SUBDIRS = threads devices lib userprog filesys
+SUBDIRS = threads devices lib lib/kernel userprog filesys
-#include "addrspace.h"
+#include "userprog/addrspace.h"
+#include <debug.h>
#include <inttypes.h>
-#include "tss.h"
+#include <round.h>
+#include <stdio.h>
+#include <string.h>
+#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"
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. */
/* 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)
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))
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;
}
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;
}
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;
}
palloc_free (kpage);
}
else
- printk ("failed to allocate process stack\n");
+ printf ("failed to allocate process stack\n");
return success;
}
-#include "exception.h"
+#include "userprog/exception.h"
#include <inttypes.h>
-#include "gdt.h"
-#include "lib/lib.h"
+#include <stdio.h>
+#include "userprog/gdt.h"
#include "threads/interrupt.h"
#include "threads/thread.h"
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);
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 ();
}
/* 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",
-#include "gdt.h"
-#include "tss.h"
-#include "lib/debug.h"
+#include "userprog/gdt.h"
+#include <debug.h>
+#include "userprog/tss.h"
#include "threads/mmu.h"
#include "threads/palloc.h"
-#include "syscall.h"
-#include "lib/lib.h"
+#include "userprog/syscall.h"
+#include <stdio.h>
+#include <syscall-nr.h>
#include "threads/interrupt.h"
#include "threads/thread.h"
static void
syscall_handler (struct intr_frame *f)
{
- printk ("system call!\n");
+ printf ("system call!\n");
thread_exit ();
}
-#include "tss.h"
+#include "userprog/tss.h"
+#include <debug.h>
#include <stddef.h>
-#include "gdt.h"
-#include "lib/debug.h"
+#include "userprog/gdt.h"
#include "threads/mmu.h"
#include "threads/palloc.h"
projects / pintos-anon / commitdiff