From 4f670845ff9ab6c48bcb5f7bf4d4ef6dc3c3064b Mon Sep 17 00:00:00 2001 From: manuel Date: Tue, 27 Mar 2012 11:51:08 +0200 Subject: reorganize file structure to match the upstream requirements --- pintos-progos/lib/arithmetic.c | 189 ----------- pintos-progos/lib/ctype.h | 28 -- pintos-progos/lib/debug.c | 32 -- pintos-progos/lib/debug.h | 39 --- pintos-progos/lib/inttypes.h | 48 --- pintos-progos/lib/kernel/bitmap.c | 371 --------------------- pintos-progos/lib/kernel/bitmap.h | 51 --- pintos-progos/lib/kernel/console.c | 191 ----------- pintos-progos/lib/kernel/console.h | 8 - pintos-progos/lib/kernel/debug.c | 123 ------- pintos-progos/lib/kernel/hash.c | 430 ------------------------ pintos-progos/lib/kernel/hash.h | 103 ------ pintos-progos/lib/kernel/list.c | 524 ----------------------------- pintos-progos/lib/kernel/list.h | 181 ---------- pintos-progos/lib/kernel/stdio.h | 6 - pintos-progos/lib/limits.h | 34 -- pintos-progos/lib/packed.h | 10 - pintos-progos/lib/random.c | 83 ----- pintos-progos/lib/random.h | 10 - pintos-progos/lib/round.h | 18 - pintos-progos/lib/stdarg.h | 14 - pintos-progos/lib/stdbool.h | 9 - pintos-progos/lib/stddef.h | 12 - pintos-progos/lib/stdint.h | 51 --- pintos-progos/lib/stdio.c | 655 ------------------------------------- pintos-progos/lib/stdio.h | 40 --- pintos-progos/lib/stdlib.c | 208 ------------ pintos-progos/lib/stdlib.h | 22 -- pintos-progos/lib/string.c | 375 --------------------- pintos-progos/lib/string.h | 35 -- pintos-progos/lib/syscall-nr.h | 34 -- pintos-progos/lib/user/console.c | 94 ------ pintos-progos/lib/user/debug.c | 25 -- pintos-progos/lib/user/entry.c | 10 - pintos-progos/lib/user/stdio.h | 7 - pintos-progos/lib/user/syscall.c | 184 ----------- pintos-progos/lib/user/syscall.h | 48 --- pintos-progos/lib/user/user.lds | 57 ---- pintos-progos/lib/ustar.c | 228 ------------- pintos-progos/lib/ustar.h | 29 -- 40 files changed, 4616 deletions(-) delete mode 100644 pintos-progos/lib/arithmetic.c delete mode 100644 pintos-progos/lib/ctype.h delete mode 100644 pintos-progos/lib/debug.c delete mode 100644 pintos-progos/lib/debug.h delete mode 100644 pintos-progos/lib/inttypes.h delete mode 100644 pintos-progos/lib/kernel/bitmap.c delete mode 100644 pintos-progos/lib/kernel/bitmap.h delete mode 100644 pintos-progos/lib/kernel/console.c delete mode 100644 pintos-progos/lib/kernel/console.h delete mode 100644 pintos-progos/lib/kernel/debug.c delete mode 100644 pintos-progos/lib/kernel/hash.c delete mode 100644 pintos-progos/lib/kernel/hash.h delete mode 100644 pintos-progos/lib/kernel/list.c delete mode 100644 pintos-progos/lib/kernel/list.h delete mode 100644 pintos-progos/lib/kernel/stdio.h delete mode 100644 pintos-progos/lib/limits.h delete mode 100644 pintos-progos/lib/packed.h delete mode 100644 pintos-progos/lib/random.c delete mode 100644 pintos-progos/lib/random.h delete mode 100644 pintos-progos/lib/round.h delete mode 100644 pintos-progos/lib/stdarg.h delete mode 100644 pintos-progos/lib/stdbool.h delete mode 100644 pintos-progos/lib/stddef.h delete mode 100644 pintos-progos/lib/stdint.h delete mode 100644 pintos-progos/lib/stdio.c delete mode 100644 pintos-progos/lib/stdio.h delete mode 100644 pintos-progos/lib/stdlib.c delete mode 100644 pintos-progos/lib/stdlib.h delete mode 100644 pintos-progos/lib/string.c delete mode 100644 pintos-progos/lib/string.h delete mode 100644 pintos-progos/lib/syscall-nr.h delete mode 100644 pintos-progos/lib/user/console.c delete mode 100644 pintos-progos/lib/user/debug.c delete mode 100644 pintos-progos/lib/user/entry.c delete mode 100644 pintos-progos/lib/user/stdio.h delete mode 100644 pintos-progos/lib/user/syscall.c delete mode 100644 pintos-progos/lib/user/syscall.h delete mode 100644 pintos-progos/lib/user/user.lds delete mode 100644 pintos-progos/lib/ustar.c delete mode 100644 pintos-progos/lib/ustar.h (limited to 'pintos-progos/lib') diff --git a/pintos-progos/lib/arithmetic.c b/pintos-progos/lib/arithmetic.c deleted file mode 100644 index bfc9b5a..0000000 --- a/pintos-progos/lib/arithmetic.c +++ /dev/null @@ -1,189 +0,0 @@ -#include - -/* On x86, division of one 64-bit integer by another cannot be - done with a single instruction or a short sequence. Thus, GCC - implements 64-bit division and remainder operations through - function calls. These functions are normally obtained from - libgcc, which is automatically included by GCC in any link - that it does. - - Some x86-64 machines, however, have a compiler and utilities - that can generate 32-bit x86 code without having any of the - necessary libraries, including libgcc. Thus, we can make - Pintos work on these machines by simply implementing our own - 64-bit division routines, which are the only routines from - libgcc that Pintos requires. - - Completeness is another reason to include these routines. If - Pintos is completely self-contained, then that makes it that - much less mysterious. */ - -/* Uses x86 DIVL instruction to divide 64-bit N by 32-bit D to - yield a 32-bit quotient. Returns the quotient. - Traps with a divide error (#DE) if the quotient does not fit - in 32 bits. */ -static inline uint32_t -divl (uint64_t n, uint32_t d) -{ - uint32_t n1 = n >> 32; - uint32_t n0 = n; - uint32_t q, r; - - asm ("divl %4" - : "=d" (r), "=a" (q) - : "0" (n1), "1" (n0), "rm" (d)); - - return q; -} - -/* Returns the number of leading zero bits in X, - which must be nonzero. */ -static int -nlz (uint32_t x) -{ - /* This technique is portable, but there are better ways to do - it on particular systems. With sufficiently new enough GCC, - you can use __builtin_clz() to take advantage of GCC's - knowledge of how to do it. Or you can use the x86 BSR - instruction directly. */ - int n = 0; - if (x <= 0x0000FFFF) - { - n += 16; - x <<= 16; - } - if (x <= 0x00FFFFFF) - { - n += 8; - x <<= 8; - } - if (x <= 0x0FFFFFFF) - { - n += 4; - x <<= 4; - } - if (x <= 0x3FFFFFFF) - { - n += 2; - x <<= 2; - } - if (x <= 0x7FFFFFFF) - n++; - return n; -} - -/* Divides unsigned 64-bit N by unsigned 64-bit D and returns the - quotient. */ -static uint64_t -udiv64 (uint64_t n, uint64_t d) -{ - if ((d >> 32) == 0) - { - /* Proof of correctness: - - Let n, d, b, n1, and n0 be defined as in this function. - Let [x] be the "floor" of x. Let T = b[n1/d]. Assume d - nonzero. Then: - [n/d] = [n/d] - T + T - = [n/d - T] + T by (1) below - = [(b*n1 + n0)/d - T] + T by definition of n - = [(b*n1 + n0)/d - dT/d] + T - = [(b(n1 - d[n1/d]) + n0)/d] + T - = [(b[n1 % d] + n0)/d] + T, by definition of % - which is the expression calculated below. - - (1) Note that for any real x, integer i: [x] + i = [x + i]. - - To prevent divl() from trapping, [(b[n1 % d] + n0)/d] must - be less than b. Assume that [n1 % d] and n0 take their - respective maximum values of d - 1 and b - 1: - [(b(d - 1) + (b - 1))/d] < b - <=> [(bd - 1)/d] < b - <=> [b - 1/d] < b - which is a tautology. - - Therefore, this code is correct and will not trap. */ - uint64_t b = 1ULL << 32; - uint32_t n1 = n >> 32; - uint32_t n0 = n; - uint32_t d0 = d; - - return divl (b * (n1 % d0) + n0, d0) + b * (n1 / d0); - } - else - { - /* Based on the algorithm and proof available from - http://www.hackersdelight.org/revisions.pdf. */ - if (n < d) - return 0; - else - { - uint32_t d1 = d >> 32; - int s = nlz (d1); - uint64_t q = divl (n >> 1, (d << s) >> 32) >> (31 - s); - return n - (q - 1) * d < d ? q - 1 : q; - } - } -} - -/* Divides unsigned 64-bit N by unsigned 64-bit D and returns the - remainder. */ -static uint32_t -umod64 (uint64_t n, uint64_t d) -{ - return n - d * udiv64 (n, d); -} - -/* Divides signed 64-bit N by signed 64-bit D and returns the - quotient. */ -static int64_t -sdiv64 (int64_t n, int64_t d) -{ - uint64_t n_abs = n >= 0 ? (uint64_t) n : -(uint64_t) n; - uint64_t d_abs = d >= 0 ? (uint64_t) d : -(uint64_t) d; - uint64_t q_abs = udiv64 (n_abs, d_abs); - return (n < 0) == (d < 0) ? (int64_t) q_abs : -(int64_t) q_abs; -} - -/* Divides signed 64-bit N by signed 64-bit D and returns the - remainder. */ -static int32_t -smod64 (int64_t n, int64_t d) -{ - return n - d * sdiv64 (n, d); -} - -/* These are the routines that GCC calls. */ - -long long __divdi3 (long long n, long long d); -long long __moddi3 (long long n, long long d); -unsigned long long __udivdi3 (unsigned long long n, unsigned long long d); -unsigned long long __umoddi3 (unsigned long long n, unsigned long long d); - -/* Signed 64-bit division. */ -long long -__divdi3 (long long n, long long d) -{ - return sdiv64 (n, d); -} - -/* Signed 64-bit remainder. */ -long long -__moddi3 (long long n, long long d) -{ - return smod64 (n, d); -} - -/* Unsigned 64-bit division. */ -unsigned long long -__udivdi3 (unsigned long long n, unsigned long long d) -{ - return udiv64 (n, d); -} - -/* Unsigned 64-bit remainder. */ -unsigned long long -__umoddi3 (unsigned long long n, unsigned long long d) -{ - return umod64 (n, d); -} diff --git a/pintos-progos/lib/ctype.h b/pintos-progos/lib/ctype.h deleted file mode 100644 index 9096aca..0000000 --- a/pintos-progos/lib/ctype.h +++ /dev/null @@ -1,28 +0,0 @@ -#ifndef __LIB_CTYPE_H -#define __LIB_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 (c == ' ' || c == '\f' || c == '\n' - || c == '\r' || c == '\t' || c == '\v'); -} -static inline int isblank (int c) { return c == ' ' || c == '\t'; } -static inline int isgraph (int c) { return c > 32 && c < 127; } -static inline int isprint (int c) { return c >= 32 && c < 127; } -static inline int iscntrl (int c) { return (c >= 0 && c < 32) || c == 127; } -static inline int isascii (int c) { return c >= 0 && c < 128; } -static inline int ispunct (int c) { - return isprint (c) && !isalnum (c) && !isspace (c); -} - -static inline int tolower (int c) { return isupper (c) ? c - 'A' + 'a' : c; } -static inline int toupper (int c) { return islower (c) ? c - 'a' + 'A' : c; } - -#endif /* lib/ctype.h */ diff --git a/pintos-progos/lib/debug.c b/pintos-progos/lib/debug.c deleted file mode 100644 index b4f8c2d..0000000 --- a/pintos-progos/lib/debug.c +++ /dev/null @@ -1,32 +0,0 @@ -#include -#include -#include -#include -#include -#include - -/* 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) -{ - static bool explained; - void **frame; - - printf ("Call stack: %p", __builtin_return_address (0)); - for (frame = __builtin_frame_address (1); - (uintptr_t) frame >= 0x1000 && frame[0] != NULL; - frame = frame[0]) - printf (" %p", frame[1]); - printf (".\n"); - - if (!explained) - { - explained = true; - printf ("The `backtrace' program can make call stacks useful.\n" - "Read \"Backtraces\" in the \"Debugging Tools\" chapter\n" - "of the Pintos documentation for more information.\n"); - } -} diff --git a/pintos-progos/lib/debug.h b/pintos-progos/lib/debug.h deleted file mode 100644 index 888ab7b..0000000 --- a/pintos-progos/lib/debug.h +++ /dev/null @@ -1,39 +0,0 @@ -#ifndef __LIB_DEBUG_H -#define __LIB_DEBUG_H - -/* GCC lets us add "attributes" to functions, function - parameters, etc. to indicate their properties. - See the GCC manual for details. */ -#define UNUSED __attribute__ ((unused)) -#define NO_RETURN __attribute__ ((noreturn)) -#define NO_INLINE __attribute__ ((noinline)) -#define PRINTF_FORMAT(FMT, FIRST) __attribute__ ((format (printf, FMT, FIRST))) - -/* Halts the OS, printing the source file name, line number, and - function name, plus a user-specific message. */ -#define PANIC(...) debug_panic (__FILE__, __LINE__, __func__, __VA_ARGS__) - -void debug_panic (const char *file, int line, const char *function, - const char *message, ...) PRINTF_FORMAT (4, 5) NO_RETURN; -void debug_backtrace (void); -void debug_backtrace_all (void); - -#endif - - - -/* This is outside the header guard so that debug.h may be - included multiple times with different settings of NDEBUG. */ -#undef ASSERT -#undef NOT_REACHED - -#ifndef NDEBUG -#define ASSERT(CONDITION) \ - if (CONDITION) { } else { \ - PANIC ("assertion `%s' failed.", #CONDITION); \ - } -#define NOT_REACHED() PANIC ("executed an unreachable statement"); -#else -#define ASSERT(CONDITION) ((void) 0) -#define NOT_REACHED() for (;;) -#endif /* lib/debug.h */ diff --git a/pintos-progos/lib/inttypes.h b/pintos-progos/lib/inttypes.h deleted file mode 100644 index f703725..0000000 --- a/pintos-progos/lib/inttypes.h +++ /dev/null @@ -1,48 +0,0 @@ -#ifndef __LIB_INTTYPES_H -#define __LIB_INTTYPES_H - -#include - -#define PRId8 "hhd" -#define PRIi8 "hhi" -#define PRIo8 "hho" -#define PRIu8 "hhu" -#define PRIx8 "hhx" -#define PRIX8 "hhX" - -#define PRId16 "hd" -#define PRIi16 "hi" -#define PRIo16 "ho" -#define PRIu16 "hu" -#define PRIx16 "hx" -#define PRIX16 "hX" - -#define PRId32 "d" -#define PRIi32 "i" -#define PRIo32 "o" -#define PRIu32 "u" -#define PRIx32 "x" -#define PRIX32 "X" - -#define PRId64 "lld" -#define PRIi64 "lli" -#define PRIo64 "llo" -#define PRIu64 "llu" -#define PRIx64 "llx" -#define PRIX64 "llX" - -#define PRIdMAX "jd" -#define PRIiMAX "ji" -#define PRIoMAX "jo" -#define PRIuMAX "ju" -#define PRIxMAX "jx" -#define PRIXMAX "jX" - -#define PRIdPTR "td" -#define PRIiPTR "ti" -#define PRIoPTR "to" -#define PRIuPTR "tu" -#define PRIxPTR "tx" -#define PRIXPTR "tX" - -#endif /* lib/inttypes.h */ diff --git a/pintos-progos/lib/kernel/bitmap.c b/pintos-progos/lib/kernel/bitmap.c deleted file mode 100644 index d14a98c..0000000 --- a/pintos-progos/lib/kernel/bitmap.c +++ /dev/null @@ -1,371 +0,0 @@ -#include "bitmap.h" -#include -#include -#include -#include -#include "threads/malloc.h" -#ifdef FILESYS -#include "filesys/file.h" -#endif - -/* 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; - -/* Number of bits in an element. */ -#define ELEM_BITS (sizeof (elem_type) * CHAR_BIT) - -/* 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. */ - }; - -/* 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 BIT_CNT bits. */ -static inline size_t -elem_cnt (size_t bit_cnt) -{ - return DIV_ROUND_UP (bit_cnt, ELEM_BITS); -} - -/* Returns the number of bytes required for BIT_CNT bits. */ -static inline size_t -byte_cnt (size_t bit_cnt) -{ - return sizeof (elem_type) * elem_cnt (bit_cnt); -} - -/* 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; -} - -/* Creation and destruction. */ - -/* Creates and returns a pointer to a newly allocated bitmap with room for - BIT_CNT (or more) bits. Returns a null pointer if memory allocation fails. - The caller is responsible for freeing the bitmap, with bitmap_destroy(), - when it is no longer needed. */ -struct bitmap * -bitmap_create (size_t bit_cnt) -{ - struct bitmap *b = malloc (sizeof *b); - if (b != NULL) - { - b->bit_cnt = bit_cnt; - b->bits = malloc (byte_cnt (bit_cnt)); - if (b->bits != NULL || bit_cnt == 0) - { - bitmap_set_all (b, false); - return b; - } - free (b); - } - return NULL; -} - -/* Creates and returns a bitmap with BIT_CNT bits in the - BLOCK_SIZE bytes of storage preallocated at BLOCK. - BLOCK_SIZE must be at least bitmap_needed_bytes(BIT_CNT). */ -struct bitmap * -bitmap_create_in_buf (size_t bit_cnt, void *block, size_t block_size UNUSED) -{ - struct bitmap *b = block; - - ASSERT (block_size >= bitmap_buf_size (bit_cnt)); - - b->bit_cnt = bit_cnt; - b->bits = (elem_type *) (b + 1); - bitmap_set_all (b, false); - return b; -} - -/* Returns the number of bytes required to accomodate a bitmap - with BIT_CNT bits (for use with bitmap_create_in_buf()). */ -size_t -bitmap_buf_size (size_t bit_cnt) -{ - return sizeof (struct bitmap) + byte_cnt (bit_cnt); -} - -/* Destroys bitmap B, freeing its storage. - Not for use on bitmaps created by bitmap_create_in_buf(). */ -void -bitmap_destroy (struct bitmap *b) -{ - if (b != NULL) - { - free (b->bits); - free (b); - } -} - -/* Bitmap size. */ - -/* Returns the number of bits in B. */ -size_t -bitmap_size (const struct bitmap *b) -{ - return b->bit_cnt; -} - -/* Setting and testing single bits. */ - -/* Atomically 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) - bitmap_mark (b, idx); - else - bitmap_reset (b, idx); -} - -/* Atomically sets the bit numbered BIT_IDX in B to true. */ -void -bitmap_mark (struct bitmap *b, size_t bit_idx) -{ - size_t idx = elem_idx (bit_idx); - elem_type mask = bit_mask (bit_idx); - - /* This is equivalent to `b->bits[idx] |= mask' except that it - is guaranteed to be atomic on a uniprocessor machine. See - the description of the OR instruction in [IA32-v2b]. */ - asm ("orl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc"); -} - -/* Atomically sets the bit numbered BIT_IDX in B to false. */ -void -bitmap_reset (struct bitmap *b, size_t bit_idx) -{ - size_t idx = elem_idx (bit_idx); - elem_type mask = bit_mask (bit_idx); - - /* This is equivalent to `b->bits[idx] &= ~mask' except that it - is guaranteed to be atomic on a uniprocessor machine. See - the description of the AND instruction in [IA32-v2a]. */ - asm ("andl %1, %0" : "=m" (b->bits[idx]) : "r" (~mask) : "cc"); -} - -/* Atomically 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 bit_idx) -{ - size_t idx = elem_idx (bit_idx); - elem_type mask = bit_mask (bit_idx); - - /* This is equivalent to `b->bits[idx] ^= mask' except that it - is guaranteed to be atomic on a uniprocessor machine. See - the description of the XOR instruction in [IA32-v2b]. */ - asm ("xorl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc"); -} - -/* 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; -} - -/* Setting and testing multiple bits. */ - -/* Sets all bits in B to VALUE. */ -void -bitmap_set_all (struct bitmap *b, bool value) -{ - ASSERT (b != NULL); - - bitmap_set_multiple (b, 0, bitmap_size (b), value); -} - -/* Sets the CNT bits starting at START in B to VALUE. */ -void -bitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value) -{ - size_t i; - - ASSERT (b != NULL); - ASSERT (start <= b->bit_cnt); - ASSERT (start + cnt <= b->bit_cnt); - - for (i = 0; i < cnt; i++) - bitmap_set (b, start + i, value); -} - -/* Returns the number of bits in B between START and START + CNT, - exclusive, that are set to VALUE. */ -size_t -bitmap_count (const struct bitmap *b, size_t start, size_t cnt, bool value) -{ - size_t i, value_cnt; - - ASSERT (b != NULL); - ASSERT (start <= b->bit_cnt); - ASSERT (start + cnt <= b->bit_cnt); - - value_cnt = 0; - for (i = 0; i < cnt; i++) - if (bitmap_test (b, start + i) == value) - value_cnt++; - return value_cnt; -} - -/* Returns true if any bits in B between START and START + CNT, - exclusive, are set to VALUE, and false otherwise. */ -bool -bitmap_contains (const struct bitmap *b, size_t start, size_t cnt, bool value) -{ - size_t i; - - ASSERT (b != NULL); - ASSERT (start <= b->bit_cnt); - ASSERT (start + cnt <= b->bit_cnt); - - for (i = 0; i < cnt; i++) - if (bitmap_test (b, start + i) == value) - return true; - return false; -} - -/* Returns true if any bits in B between START and START + CNT, - exclusive, are set to true, and false otherwise.*/ -bool -bitmap_any (const struct bitmap *b, size_t start, size_t cnt) -{ - return bitmap_contains (b, start, cnt, true); -} - -/* Returns true if no bits in B between START and START + CNT, - exclusive, are set to true, and false otherwise.*/ -bool -bitmap_none (const struct bitmap *b, size_t start, size_t cnt) -{ - return !bitmap_contains (b, start, cnt, true); -} - -/* Returns true if every bit in B between START and START + CNT, - exclusive, is set to true, and false otherwise. */ -bool -bitmap_all (const struct bitmap *b, size_t start, size_t cnt) -{ - return !bitmap_contains (b, start, cnt, false); -} - -/* Finding set or unset bits. */ - -/* Finds and returns the starting index of the first group of CNT - consecutive bits in B at or after START that are all set to - VALUE. - If there is no such group, returns BITMAP_ERROR. */ -size_t -bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value) -{ - ASSERT (b != NULL); - ASSERT (start <= b->bit_cnt); - - if (cnt <= b->bit_cnt) - { - size_t last = b->bit_cnt - cnt; - size_t i; - for (i = start; i <= last; i++) - if (!bitmap_contains (b, i, cnt, !value)) - return i; - } - return BITMAP_ERROR; -} - -/* Finds the first group of CNT consecutive bits in B at or after - START that are all set to VALUE, flips them all to !VALUE, - and returns the index of the first bit in the group. - If there is no such group, returns BITMAP_ERROR. - If CNT is zero, returns 0. - Bits are set atomically, but testing bits is not atomic with - setting them. */ -size_t -bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value) -{ - size_t idx = bitmap_scan (b, start, cnt, value); - if (idx != BITMAP_ERROR) - bitmap_set_multiple (b, idx, cnt, !value); - return idx; -} - -/* File input and output. */ - -#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->bit_cnt); -} - -/* Reads B from FILE. Returns true if successful, false - otherwise. */ -bool -bitmap_read (struct bitmap *b, struct file *file) -{ - bool success = true; - if (b->bit_cnt > 0) - { - off_t size = byte_cnt (b->bit_cnt); - success = file_read_at (file, b->bits, size, 0) == size; - b->bits[elem_cnt (b->bit_cnt) - 1] &= last_mask (b); - } - return success; -} - -/* Writes B to FILE. Return true if successful, false - otherwise. */ -bool -bitmap_write (const struct bitmap *b, struct file *file) -{ - off_t size = byte_cnt (b->bit_cnt); - return file_write_at (file, b->bits, size, 0) == size; -} -#endif /* FILESYS */ - -/* Debugging. */ - -/* Dumps the contents of B to the console as hexadecimal. */ -void -bitmap_dump (const struct bitmap *b) -{ - hex_dump (0, b->bits, byte_cnt (b->bit_cnt), false); -} - diff --git a/pintos-progos/lib/kernel/bitmap.h b/pintos-progos/lib/kernel/bitmap.h deleted file mode 100644 index a50593c..0000000 --- a/pintos-progos/lib/kernel/bitmap.h +++ /dev/null @@ -1,51 +0,0 @@ -#ifndef __LIB_KERNEL_BITMAP_H -#define __LIB_KERNEL_BITMAP_H - -#include -#include -#include - -/* Bitmap abstract data type. */ - -/* Creation and destruction. */ -struct bitmap *bitmap_create (size_t bit_cnt); -struct bitmap *bitmap_create_in_buf (size_t bit_cnt, void *, size_t byte_cnt); -size_t bitmap_buf_size (size_t bit_cnt); -void bitmap_destroy (struct bitmap *); - -/* Bitmap size. */ -size_t bitmap_size (const struct bitmap *); - -/* Setting and testing single bits. */ -void bitmap_set (struct bitmap *, size_t idx, 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); - -/* Setting and testing multiple bits. */ -void bitmap_set_all (struct bitmap *, bool); -void bitmap_set_multiple (struct bitmap *, size_t start, size_t cnt, bool); -size_t bitmap_count (const struct bitmap *, size_t start, size_t cnt, bool); -bool bitmap_contains (const struct bitmap *, size_t start, size_t cnt, bool); -bool bitmap_any (const struct bitmap *, size_t start, size_t cnt); -bool bitmap_none (const struct bitmap *, size_t start, size_t cnt); -bool bitmap_all (const struct bitmap *, size_t start, size_t cnt); - -/* Finding set or unset bits. */ -#define BITMAP_ERROR SIZE_MAX -size_t bitmap_scan (const struct bitmap *, size_t start, size_t cnt, bool); -size_t bitmap_scan_and_flip (struct bitmap *, size_t start, size_t cnt, bool); - -/* File input and output. */ -#ifdef FILESYS -struct file; -size_t bitmap_file_size (const struct bitmap *); -bool bitmap_read (struct bitmap *, struct file *); -bool bitmap_write (const struct bitmap *, struct file *); -#endif - -/* Debugging. */ -void bitmap_dump (const struct bitmap *); - -#endif /* lib/kernel/bitmap.h */ diff --git a/pintos-progos/lib/kernel/console.c b/pintos-progos/lib/kernel/console.c deleted file mode 100644 index 844b184..0000000 --- a/pintos-progos/lib/kernel/console.c +++ /dev/null @@ -1,191 +0,0 @@ -#include -#include -#include -#include "devices/serial.h" -#include "devices/vga.h" -#include "threads/init.h" -#include "threads/interrupt.h" -#include "threads/synch.h" - -static void vprintf_helper (char, void *); -static void putchar_have_lock (uint8_t c); - -/* The console lock. - Both the vga and serial layers do their own locking, so it's - safe to call them at any time. - But this lock is useful to prevent simultaneous printf() calls - from mixing their output, which looks confusing. */ -static struct lock console_lock; - -/* True in ordinary circumstances: we want to use the console - lock to avoid mixing output between threads, as explained - above. - - False in early boot before the point that locks are functional - or the console lock has been initialized, or after a kernel - panics. In the former case, taking the lock would cause an - assertion failure, which in turn would cause a panic, turning - it into the latter case. In the latter case, if it is a buggy - lock_acquire() implementation that caused the panic, we'll - likely just recurse. */ -static bool use_console_lock; - -/* It's possible, if you add enough debug output to Pintos, to - try to recursively grab console_lock from a single thread. As - a real example, I added a printf() call to palloc_free(). - Here's a real backtrace that resulted: - - lock_console() - vprintf() - printf() - palloc() tries to grab the lock again - palloc_free() - thread_schedule_tail() - another thread dying as we switch threads - schedule() - thread_yield() - intr_handler() - timer interrupt - intr_set_level() - serial_putc() - putchar_have_lock() - putbuf() - sys_write() - one process writing to the console - syscall_handler() - intr_handler() - - This kind of thing is very difficult to debug, so we avoid the - problem by simulating a recursive lock with a depth - counter. */ -static int console_lock_depth; - -/* Number of characters written to console. */ -static int64_t write_cnt; - -/* Enable console locking. */ -void -console_init (void) -{ - lock_init (&console_lock); - use_console_lock = true; -} - -/* Notifies the console that a kernel panic is underway, - which warns it to avoid trying to take the console lock from - now on. */ -void -console_panic (void) -{ - use_console_lock = false; -} - -/* Prints console statistics. */ -void -console_print_stats (void) -{ - printf ("Console: %lld characters output\n", write_cnt); -} - -/* Acquires the console lock. */ -static void -acquire_console (void) -{ - if (!intr_context () && use_console_lock) - { - if (lock_held_by_current_thread (&console_lock)) - console_lock_depth++; - else - lock_acquire (&console_lock); - } -} - -/* Releases the console lock. */ -static void -release_console (void) -{ - if (!intr_context () && use_console_lock) - { - if (console_lock_depth > 0) - console_lock_depth--; - else - lock_release (&console_lock); - } -} - -/* Returns true if the current thread has the console lock, - false otherwise. */ -static bool -console_locked_by_current_thread (void) -{ - return (intr_context () - || !use_console_lock - || lock_held_by_current_thread (&console_lock)); -} - -/* The standard vprintf() function, - which is like printf() but uses a va_list. - Writes its output to both vga display and serial port. */ -int -vprintf (const char *format, va_list args) -{ - int char_cnt = 0; - - acquire_console (); - __vprintf (format, args, vprintf_helper, &char_cnt); - release_console (); - - return char_cnt; -} - -/* Writes string S to the console, followed by a new-line - character. */ -int -puts (const char *s) -{ - acquire_console (); - while (*s != '\0') - putchar_have_lock (*s++); - putchar_have_lock ('\n'); - release_console (); - - return 0; -} - -/* Writes the N characters in BUFFER to the console. */ -void -putbuf (const char *buffer, size_t n) -{ - acquire_console (); - while (n-- > 0) - putchar_have_lock (*buffer++); - release_console (); -} - -/* Writes C to the vga display and serial port. */ -int -putchar (int c) -{ - acquire_console (); - putchar_have_lock (c); - release_console (); - - return c; -} - -/* Helper function for vprintf(). */ -static void -vprintf_helper (char c, void *char_cnt_) -{ - int *char_cnt = char_cnt_; - (*char_cnt)++; - putchar_have_lock (c); -} - -/* Writes C to the vga display and serial port. - The caller has already acquired the console lock if - appropriate. */ -static void -putchar_have_lock (uint8_t c) -{ - ASSERT (console_locked_by_current_thread ()); - write_cnt++; - serial_putc (c); - vga_putc (c); -} diff --git a/pintos-progos/lib/kernel/console.h b/pintos-progos/lib/kernel/console.h deleted file mode 100644 index ab99249..0000000 --- a/pintos-progos/lib/kernel/console.h +++ /dev/null @@ -1,8 +0,0 @@ -#ifndef __LIB_KERNEL_CONSOLE_H -#define __LIB_KERNEL_CONSOLE_H - -void console_init (void); -void console_panic (void); -void console_print_stats (void); - -#endif /* lib/kernel/console.h */ diff --git a/pintos-progos/lib/kernel/debug.c b/pintos-progos/lib/kernel/debug.c deleted file mode 100644 index b12f4f9..0000000 --- a/pintos-progos/lib/kernel/debug.c +++ /dev/null @@ -1,123 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include "threads/init.h" -#include "threads/interrupt.h" -#include "threads/thread.h" -#include "threads/switch.h" -#include "threads/vaddr.h" -#include "devices/serial.h" -#include "devices/shutdown.h" - -/* Halts the OS, printing the source file name, line number, and - function name, plus a user-specific message. */ -void -debug_panic (const char *file, int line, const char *function, - const char *message, ...) -{ - static int level; - va_list args; - - intr_disable (); - console_panic (); - - level++; - if (level == 1) - { - printf ("Kernel PANIC at %s:%d in %s(): ", file, line, function); - - va_start (args, message); - vprintf (message, args); - printf ("\n"); - va_end (args); - - debug_backtrace (); - } - else if (level == 2) - printf ("Kernel PANIC recursion at %s:%d in %s().\n", - file, line, function); - else - { - /* Don't print anything: that's probably why we recursed. */ - } - - serial_flush (); - shutdown (); - for (;;); -} - -/* Print call stack of a thread. - The thread may be running, ready, or blocked. */ -static void -print_stacktrace(struct thread *t, void *aux UNUSED) -{ - void *retaddr = NULL, **frame = NULL; - const char *status = "UNKNOWN"; - - switch (t->status) { - case THREAD_RUNNING: - status = "RUNNING"; - break; - - case THREAD_READY: - status = "READY"; - break; - - case THREAD_BLOCKED: - status = "BLOCKED"; - break; - - default: - break; - } - - printf ("Call stack of thread `%s' (status %s):", t->name, status); - - if (t == thread_current()) - { - frame = __builtin_frame_address (1); - retaddr = __builtin_return_address (0); - } - else - { - /* Retrieve the values of the base and instruction pointers - as they were saved when this thread called switch_threads. */ - struct switch_threads_frame * saved_frame; - - saved_frame = (struct switch_threads_frame *)t->stack; - - /* Skip threads if they have been added to the all threads - list, but have never been scheduled. - We can identify because their `stack' member either points - at the top of their kernel stack page, or the - switch_threads_frame's 'eip' member points at switch_entry. - See also threads.c. */ - if (t->stack == (uint8_t *)t + PGSIZE || saved_frame->eip == switch_entry) - { - printf (" thread was never scheduled.\n"); - return; - } - - frame = (void **) saved_frame->ebp; - retaddr = (void *) saved_frame->eip; - } - - printf (" %p", retaddr); - for (; (uintptr_t) frame >= 0x1000 && frame[0] != NULL; frame = frame[0]) - printf (" %p", frame[1]); - printf (".\n"); -} - -/* Prints call stack of all threads. */ -void -debug_backtrace_all (void) -{ - enum intr_level oldlevel = intr_disable (); - - thread_foreach (print_stacktrace, 0); - intr_set_level (oldlevel); -} diff --git a/pintos-progos/lib/kernel/hash.c b/pintos-progos/lib/kernel/hash.c deleted file mode 100644 index 57eed45..0000000 --- a/pintos-progos/lib/kernel/hash.c +++ /dev/null @@ -1,430 +0,0 @@ -/* Hash table. - - This data structure is thoroughly documented in the Tour of - Pintos for Project 3. - - See hash.h for basic information. */ - -#include "hash.h" -#include "../debug.h" -#include "threads/malloc.h" - -#define list_elem_to_hash_elem(LIST_ELEM) \ - list_entry(LIST_ELEM, struct hash_elem, list_elem) - -static struct list *find_bucket (struct hash *, struct hash_elem *); -static struct hash_elem *find_elem (struct hash *, struct list *, - struct hash_elem *); -static void insert_elem (struct hash *, struct list *, struct hash_elem *); -static void remove_elem (struct hash *, struct 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, NULL); - return true; - } - else - return false; -} - -/* Removes all the elements from H. - - If DESTRUCTOR is non-null, then it is called for each element - in the hash. DESTRUCTOR may, if appropriate, deallocate the - memory used by the hash element. However, modifying hash - table H while hash_clear() is running, using any of the - functions hash_clear(), hash_destroy(), hash_insert(), - hash_replace(), or hash_delete(), yields undefined behavior, - whether done in DESTRUCTOR or elsewhere. */ -void -hash_clear (struct hash *h, hash_action_func *destructor) -{ - size_t i; - - for (i = 0; i < h->bucket_cnt; i++) - { - struct list *bucket = &h->buckets[i]; - - if (destructor != NULL) - while (!list_empty (bucket)) - { - struct list_elem *list_elem = list_pop_front (bucket); - struct hash_elem *hash_elem = list_elem_to_hash_elem (list_elem); - destructor (hash_elem, h->aux); - } - - list_init (bucket); - } - - h->elem_cnt = 0; -} - -/* Destroys hash table H. - - If DESTRUCTOR is non-null, then it is first called for each - element in the hash. DESTRUCTOR may, if appropriate, - deallocate the memory used by the hash element. However, - modifying hash table H while hash_clear() is running, using - any of the functions hash_clear(), hash_destroy(), - hash_insert(), hash_replace(), or hash_delete(), yields - undefined behavior, whether done in DESTRUCTOR or - elsewhere. */ -void -hash_destroy (struct hash *h, hash_action_func *destructor) -{ - if (destructor != NULL) - hash_clear (h, destructor); - 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. */ -struct hash_elem * -hash_insert (struct hash *h, struct hash_elem *new) -{ - struct list *bucket = find_bucket (h, new); - struct hash_elem *old = find_elem (h, bucket, new); - - if (old == NULL) - insert_elem (h, bucket, new); - - rehash (h); - - return old; -} - -/* Inserts NEW into hash table H, replacing any equal element - already in the table, which is returned. */ -struct hash_elem * -hash_replace (struct hash *h, struct hash_elem *new) -{ - struct list *bucket = find_bucket (h, new); - struct hash_elem *old = find_elem (h, bucket, new); - - if (old != NULL) - remove_elem (h, old); - insert_elem (h, bucket, new); - - rehash (h); - - 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. */ -struct hash_elem * -hash_find (struct hash *h, struct 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. - - If the elements of the hash table are dynamically allocated, - or own resources that are, then it is the caller's - responsibility to deallocate them. */ -struct hash_elem * -hash_delete (struct hash *h, struct hash_elem *e) -{ - struct hash_elem *found = find_elem (h, find_bucket (h, e), e); - if (found != NULL) - { - remove_elem (h, found); - rehash (h); - } - return found; -} - -/* Calls ACTION for each element in hash table H in arbitrary - order. - Modifying hash table H while hash_apply() is running, using - any of the functions hash_clear(), hash_destroy(), - hash_insert(), hash_replace(), or hash_delete(), yields - undefined behavior, whether done from ACTION or elsewhere. */ -void -hash_apply (struct hash *h, hash_action_func *action) -{ - size_t i; - - ASSERT (action != NULL); - - for (i = 0; i < h->bucket_cnt; i++) - { - struct list *bucket = &h->buckets[i]; - struct list_elem *elem, *next; - - for (elem = list_begin (bucket); elem != list_end (bucket); elem = next) - { - next = list_next (elem); - action (list_elem_to_hash_elem (elem), h->aux); - } - } -} - -/* Initializes I for iterating hash table H. - - Iteration idiom: - - struct hash_iterator i; - - hash_first (&i, h); - while (hash_next (&i)) - { - struct foo *f = hash_entry (hash_cur (&i), struct foo, elem); - ...do something with f... - } - - Modifying hash table H during iteration, using any of the - functions hash_clear(), hash_destroy(), hash_insert(), - hash_replace(), or hash_delete(), 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_elem_to_hash_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. - - Modifying a hash table H during iteration, using any of the - functions hash_clear(), hash_destroy(), hash_insert(), - hash_replace(), or hash_delete(), invalidates all - iterators. */ -struct hash_elem * -hash_next (struct hash_iterator *i) -{ - ASSERT (i != NULL); - - i->elem = list_elem_to_hash_elem (list_next (&i->elem->list_elem)); - while (i->elem == list_elem_to_hash_elem (list_end (i->bucket))) - { - if (++i->bucket >= i->hash->buckets + i->hash->bucket_cnt) - { - i->elem = NULL; - break; - } - i->elem = list_elem_to_hash_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(). */ -struct 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 = (const unsigned char *) s_; - unsigned hash; - - ASSERT (s != NULL); - - hash = FNV_32_BASIS; - while (*s != '\0') - hash = (hash * FNV_32_PRIME) ^ *s++; - - return hash; -} - -/* Returns a hash of integer I. */ -unsigned -hash_int (int i) -{ - return hash_bytes (&i, sizeof i); -} - -/* Returns the bucket in H that E belongs in. */ -static struct list * -find_bucket (struct hash *h, struct 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 hash_elem * -find_elem (struct hash *h, struct list *bucket, struct hash_elem *e) -{ - struct list_elem *i; - - for (i = list_begin (bucket); i != list_end (bucket); i = list_next (i)) - { - struct hash_elem *hi = list_elem_to_hash_elem (i); - if (!h->less (hi, e, h->aux) && !h->less (e, hi, h->aux)) - return hi; - } - 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, list_elem_to_hash_elem (elem)); - next = list_next (elem); - list_remove (elem); - list_push_front (new_bucket, elem); - } - } - - free (old_buckets); -} - -/* Inserts E into BUCKET (in hash table H). */ -static void -insert_elem (struct hash *h, struct list *bucket, struct hash_elem *e) -{ - h->elem_cnt++; - list_push_front (bucket, &e->list_elem); -} - -/* Removes E from hash table H. */ -static void -remove_elem (struct hash *h, struct hash_elem *e) -{ - h->elem_cnt--; - list_remove (&e->list_elem); -} - diff --git a/pintos-progos/lib/kernel/hash.h b/pintos-progos/lib/kernel/hash.h deleted file mode 100644 index db9f674..0000000 --- a/pintos-progos/lib/kernel/hash.h +++ /dev/null @@ -1,103 +0,0 @@ -#ifndef __LIB_KERNEL_HASH_H -#define __LIB_KERNEL_HASH_H - -/* Hash table. - - This data structure is thoroughly documented in the Tour of - Pintos for Project 3. - - 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 - struct hash_elem member. All of the hash functions operate on - these `struct hash_elem's. The hash_entry macro allows - conversion from a struct hash_elem back to a structure object - that contains it. This is the same technique used in the - linked list implementation. Refer to lib/kernel/list.h for a - detailed explanation. */ - -#include -#include -#include -#include "list.h" - -/* Hash element. */ -struct hash_elem - { - struct list_elem list_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)->list_elem \ - - offsetof (STRUCT, MEMBER.list_elem))) - -/* Computes and returns the hash value for hash element E, given - auxiliary data AUX. */ -typedef unsigned hash_hash_func (const struct 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 struct hash_elem *a, - const struct hash_elem *b, - void *aux); - -/* Performs some operation on hash element E, given auxiliary - data AUX. */ -typedef void hash_action_func (struct hash_elem *e, 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. */ - struct 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 *, hash_action_func *); -void hash_destroy (struct hash *, hash_action_func *); - -/* Search, insertion, deletion. */ -struct hash_elem *hash_insert (struct hash *, struct hash_elem *); -struct hash_elem *hash_replace (struct hash *, struct hash_elem *); -struct hash_elem *hash_find (struct hash *, struct hash_elem *); -struct hash_elem *hash_delete (struct hash *, struct hash_elem *); - -/* Iteration. */ -void hash_apply (struct hash *, hash_action_func *); -void hash_first (struct hash_iterator *, struct hash *); -struct hash_elem *hash_next (struct hash_iterator *); -struct 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 /* lib/kernel/hash.h */ diff --git a/pintos-progos/lib/kernel/list.c b/pintos-progos/lib/kernel/list.c deleted file mode 100644 index 316d9ef..0000000 --- a/pintos-progos/lib/kernel/list.c +++ /dev/null @@ -1,524 +0,0 @@ -#include "list.h" -#include "../debug.h" - -/* Our doubly linked lists have two header elements: the "head" - just before the first element and the "tail" just after the - last element. The `prev' link of the front header is null, as - is the `next' link of the back header. Their other two links - point toward each other via the interior elements of the list. - - An empty list looks like this: - - +------+ +------+ - <---| head |<--->| tail |---> - +------+ +------+ - - A list with two elements in it looks like this: - - +------+ +-------+ +-------+ +------+ - <---| head |<--->| 1 |<--->| 2 |<--->| tail |<---> - +------+ +-------+ +-------+ +------+ - - The symmetry of this arrangement eliminates lots of special - cases in list processing. For example, take a look at - list_remove(): it takes only two pointer assignments and no - conditionals. That's a lot simpler than the code would be - without header elements. - - (Because only one of the pointers in each header element is used, - we could in fact combine them into a single header element - without sacrificing this simplicity. But using two separate - elements allows us to do a little bit of checking on some - operations, which can be valuable.) */ - -static bool is_sorted (struct list_elem *a, struct list_elem *b, - list_less_func *less, void *aux) UNUSED; - -/* Returns true if ELEM is a head, false otherwise. */ -static inline bool -is_head (struct 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 (struct 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 (struct 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. */ -struct 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. */ -struct list_elem * -list_next (struct list_elem *elem) -{ - ASSERT (is_head (elem) || 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. */ -struct 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. */ -struct 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. */ -struct list_elem * -list_prev (struct 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... - } -*/ -struct 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)) - { - ... - } -*/ -struct list_elem * -list_head (struct list *list) -{ - ASSERT (list != NULL); - return &list->head; -} - -/* Return's LIST's tail. */ -struct 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 (struct list_elem *before, struct 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 (struct list_elem *before, - struct list_elem *first, struct 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, struct 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, struct list_elem *elem) -{ - list_insert (list_end (list), elem); -} - -/* Removes ELEM from its list and returns the element that - followed it. Undefined behavior if ELEM is not in a list. - - A list element must be treated very carefully after removing - it from its list. Calling list_next() or list_prev() on ELEM - will return the item that was previously before or after ELEM, - but, e.g., list_prev(list_next(ELEM)) is no longer ELEM! - - The list_remove() return value provides a convenient way to - iterate and remove elements from a list: - - for (e = list_begin (&list); e != list_end (&list); e = list_remove (e)) - { - ...do something with e... - } - - If you need to free() elements of the list then you need to be - more conservative. Here's an alternate strategy that works - even in that case: - - while (!list_empty (&list)) - { - struct list_elem *e = list_pop_front (&list); - ...do something with e... - } -*/ -struct list_elem * -list_remove (struct list_elem *elem) -{ - ASSERT (is_interior (elem)); - elem->prev->next = elem->next; - elem->next->prev = elem->prev; - return elem->next; -} - -/* Removes the front element from LIST and returns it. - Undefined behavior if LIST is empty before removal. */ -struct list_elem * -list_pop_front (struct list *list) -{ - struct list_elem *front = list_front (list); - list_remove (front); - return front; -} - -/* Removes the back element from LIST and returns it. - Undefined behavior if LIST is empty before removal. */ -struct list_elem * -list_pop_back (struct list *list) -{ - struct list_elem *back = list_back (list); - list_remove (back); - return back; -} - -/* Returns the front element in LIST. - Undefined behavior if LIST is empty. */ -struct 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. */ -struct 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) -{ - struct 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); -} - -/* Swaps the `struct list_elem *'s that A and B point to. */ -static void -swap (struct list_elem **a, struct list_elem **b) -{ - struct list_elem *t = *a; - *a = *b; - *b = t; -} - -/* Reverses the order of LIST. */ -void -list_reverse (struct list *list) -{ - if (!list_empty (list)) - { - struct list_elem *e; - - for (e = list_begin (list); e != list_end (list); e = e->prev) - swap (&e->prev, &e->next); - swap (&list->head.next, &list->tail.prev); - swap (&list->head.next->prev, &list->tail.prev->next); - } -} - -/* Returns true only if the list elements A through B (exclusive) - are in order according to LESS given auxiliary data AUX. */ -static bool -is_sorted (struct list_elem *a, struct list_elem *b, - list_less_func *less, void *aux) -{ - if (a != b) - while ((a = list_next (a)) != b) - if (less (a, list_prev (a), aux)) - return false; - return true; -} - -/* Finds a run, starting at A and ending not after B, of list - elements that are in nondecreasing order according to LESS - given auxiliary data AUX. Returns the (exclusive) end of the - run. - A through B (exclusive) must form a non-empty range. */ -static struct list_elem * -find_end_of_run (struct list_elem *a, struct list_elem *b, - list_less_func *less, void *aux) -{ - ASSERT (a != NULL); - ASSERT (b != NULL); - ASSERT (less != NULL); - ASSERT (a != b); - - do - { - a = list_next (a); - } - while (a != b && !less (a, list_prev (a), aux)); - return a; -} - -/* Merges A0 through A1B0 (exclusive) with A1B0 through B1 - (exclusive) to form a combined range also ending at B1 - (exclusive). Both input ranges must be nonempty and sorted in - nondecreasing order according to LESS given auxiliary data - AUX. The output range will be sorted the same way. */ -static void -inplace_merge (struct list_elem *a0, struct list_elem *a1b0, - struct list_elem *b1, - list_less_func *less, void *aux) -{ - ASSERT (a0 != NULL); - ASSERT (a1b0 != NULL); - ASSERT (b1 != NULL); - ASSERT (less != NULL); - ASSERT (is_sorted (a0, a1b0, less, aux)); - ASSERT (is_sorted (a1b0, b1, less, aux)); - - while (a0 != a1b0 && a1b0 != b1) - if (!less (a1b0, a0, aux)) - a0 = list_next (a0); - else - { - a1b0 = list_next (a1b0); - list_splice (a0, list_prev (a1b0), a1b0); - } -} - -/* Sorts LIST according to LESS given auxiliary data AUX, using a - natural iterative merge sort that runs in O(n lg n) time and - O(1) space in the number of elements in LIST. */ -void -list_sort (struct list *list, list_less_func *less, void *aux) -{ - size_t output_run_cnt; /* Number of runs output in current pass. */ - - ASSERT (list != NULL); - ASSERT (less != NULL); - - /* Pass over the list repeatedly, merging adjacent runs of - nondecreasing elements, until only one run is left. */ - do - { - struct list_elem *a0; /* Start of first run. */ - struct list_elem *a1b0; /* End of first run, start of second. */ - struct list_elem *b1; /* End of second run. */ - - output_run_cnt = 0; - for (a0 = list_begin (list); a0 != list_end (list); a0 = b1) - { - /* Each iteration produces one output run. */ - output_run_cnt++; - - /* Locate two adjacent runs of nondecreasing elements - A0...A1B0 and A1B0...B1. */ - a1b0 = find_end_of_run (a0, list_end (list), less, aux); - if (a1b0 == list_end (list)) - break; - b1 = find_end_of_run (a1b0, list_end (list), less, aux); - - /* Merge the runs. */ - inplace_merge (a0, a1b0, b1, less, aux); - } - } - while (output_run_cnt > 1); - - ASSERT (is_sorted (list_begin (list), list_end (list), 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, struct list_elem *elem, - list_less_func *less, void *aux) -{ - struct list_elem *e; - - ASSERT (list != NULL); - ASSERT (elem != NULL); - ASSERT (less != NULL); - - for (e = list_begin (list); e != list_end (list); e = list_next (e)) - if (less (elem, e, aux)) - break; - return list_insert (e, elem); -} - -/* 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) -{ - struct list_elem *elem, *next; - - ASSERT (list != NULL); - ASSERT (less != NULL); - if (list_empty (list)) - return; - - elem = list_begin (list); - while ((next = list_next (elem)) != list_end (list)) - if (!less (elem, next, aux) && !less (next, elem, aux)) - { - list_remove (next); - if (duplicates != NULL) - list_push_back (duplicates, next); - } - else - elem = next; -} - -/* Returns the element in LIST with the largest value according - to LESS given auxiliary data AUX. If there is more than one - maximum, returns the one that appears earlier in the list. If - the list is empty, returns its tail. */ -struct list_elem * -list_max (struct list *list, list_less_func *less, void *aux) -{ - struct list_elem *max = list_begin (list); - if (max != list_end (list)) - { - struct list_elem *e; - - for (e = list_next (max); e != list_end (list); e = list_next (e)) - if (less (max, e, aux)) - max = e; - } - return max; -} - -/* Returns the element in LIST with the smallest value according - to LESS given auxiliary data AUX. If there is more than one - minimum, returns the one that appears earlier in the list. If - the list is empty, returns its tail. */ -struct list_elem * -list_min (struct list *list, list_less_func *less, void *aux) -{ - struct list_elem *min = list_begin (list); - if (min != list_end (list)) - { - struct list_elem *e; - - for (e = list_next (min); e != list_end (list); e = list_next (e)) - if (less (e, min, aux)) - min = e; - } - return min; -} diff --git a/pintos-progos/lib/kernel/list.h b/pintos-progos/lib/kernel/list.h deleted file mode 100644 index 82efbb5..0000000 --- a/pintos-progos/lib/kernel/list.h +++ /dev/null @@ -1,181 +0,0 @@ -#ifndef __LIB_KERNEL_LIST_H -#define __LIB_KERNEL_LIST_H - -/* 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 struct list_elem - member. All of the list functions operate on these `struct - list_elem's. The list_entry macro allows conversion from a - struct 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 `struct list_elem' - member, like so: - - struct foo - { - struct 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 struct list_elem back to its enclosing - structure. Here's an example using foo_list: - - struct list_elem *e; - - for (e = list_begin (&foo_list); e != list_end (&foo_list); - e = list_next (e)) - { - struct foo *f = list_entry (e, struct foo, elem); - ...do something with f... - } - - You can find real examples of list usage throughout the - source; for example, malloc.c, palloc.c, and thread.c in the - threads directory all use lists. - - The interface for this list is inspired by the list<> template - in the C++ STL. If you're familiar with list<>, you should - find this easy to use. However, it should be emphasized that - these lists do *no* type checking and can't do much other - correctness checking. If you screw up, it will bite you. - - Glossary of list terms: - - - "front": The first element in a list. Undefined in an - empty list. Returned by list_front(). - - - "back": The last element in a list. Undefined in an empty - list. Returned by list_back(). - - - "tail": The element figuratively just after the last - element of a list. Well defined even in an empty list. - Returned by list_end(). Used as the end sentinel for an - iteration from front to back. - - - "beginning": In a non-empty list, the front. In an empty - list, the tail. Returned by list_begin(). Used as the - starting point for an iteration from front to back. - - - "head": The element figuratively just before the first - element of a list. Well defined even in an empty list. - Returned by list_rend(). Used as the end sentinel for an - iteration from back to front. - - - "reverse beginning": In a non-empty list, the back. In an - empty list, the head. Returned by list_rbegin(). Used as - the starting point for an iteration from back to front. - - - "interior element": An element that is not the head or - tail, that is, a real list element. An empty list does - not have any interior elements. -*/ - -#include -#include -#include - -/* List element. */ -struct list_elem - { - struct list_elem *prev; /* Previous list element. */ - struct list_elem *next; /* Next list element. */ - }; - -/* List. */ -struct list - { - struct list_elem head; /* List head. */ - struct 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)->next \ - - offsetof (STRUCT, MEMBER.next))) - -/* List initialization. - - A list may be initialized by calling list_init(): - - struct list my_list; - list_init (&my_list); - - or with an initializer using LIST_INITIALIZER: - - struct list my_list = LIST_INITIALIZER (my_list); */ -#define LIST_INITIALIZER(NAME) { { NULL, &(NAME).tail }, \ - { &(NAME).head, NULL } } - -void list_init (struct list *); - -/* List traversal. */ -struct list_elem *list_begin (struct list *); -struct list_elem *list_next (struct list_elem *); -struct list_elem *list_end (struct list *); - -struct list_elem *list_rbegin (struct list *); -struct list_elem *list_prev (struct list_elem *); -struct list_elem *list_rend (struct list *); - -struct list_elem *list_head (struct list *); -struct list_elem *list_tail (struct list *); - -/* List insertion. */ -void list_insert (struct list_elem *, struct list_elem *); -void list_splice (struct list_elem *before, - struct list_elem *first, struct list_elem *last); -void list_push_front (struct list *, struct list_elem *); -void list_push_back (struct list *, struct list_elem *); - -/* List removal. */ -struct list_elem *list_remove (struct list_elem *); -struct list_elem *list_pop_front (struct list *); -struct list_elem *list_pop_back (struct list *); - -/* List elements. */ -struct list_elem *list_front (struct list *); -struct list_elem *list_back (struct list *); - -/* List properties. */ -size_t list_size (struct list *); -bool list_empty (struct list *); - -/* Miscellaneous. */ -void list_reverse (struct list *); - -/* 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 struct list_elem *a, - const struct list_elem *b, - void *aux); - -/* Operations on lists with ordered elements. */ -void list_sort (struct list *, - list_less_func *, void *aux); -void list_insert_ordered (struct list *, struct list_elem *, - list_less_func *, void *aux); -void list_unique (struct list *, struct list *duplicates, - list_less_func *, void *aux); - -/* Max and min. */ -struct list_elem *list_max (struct list *, list_less_func *, void *aux); -struct list_elem *list_min (struct list *, list_less_func *, void *aux); - -#endif /* lib/kernel/list.h */ diff --git a/pintos-progos/lib/kernel/stdio.h b/pintos-progos/lib/kernel/stdio.h deleted file mode 100644 index 3e5bae9..0000000 --- a/pintos-progos/lib/kernel/stdio.h +++ /dev/null @@ -1,6 +0,0 @@ -#ifndef __LIB_KERNEL_STDIO_H -#define __LIB_KERNEL_STDIO_H - -void putbuf (const char *, size_t); - -#endif /* lib/kernel/stdio.h */ diff --git a/pintos-progos/lib/limits.h b/pintos-progos/lib/limits.h deleted file mode 100644 index c957ec4..0000000 --- a/pintos-progos/lib/limits.h +++ /dev/null @@ -1,34 +0,0 @@ -#ifndef __LIB_LIMITS_H -#define __LIB_LIMITS_H - -#define CHAR_BIT 8 - -#define SCHAR_MAX 127 -#define SCHAR_MIN (-SCHAR_MAX - 1) -#define UCHAR_MAX 255 - -#ifdef __CHAR_UNSIGNED__ -#define CHAR_MIN 0 -#define CHAR_MAX UCHAR_MAX -#else -#define CHAR_MIN SCHAR_MIN -#define CHAR_MAX SCHAR_MAX -#endif - -#define SHRT_MAX 32767 -#define SHRT_MIN (-SHRT_MAX - 1) -#define USHRT_MAX 65535 - -#define INT_MAX 2147483647 -#define INT_MIN (-INT_MAX - 1) -#define UINT_MAX 4294967295U - -#define LONG_MAX 2147483647L -#define LONG_MIN (-LONG_MAX - 1) -#define ULONG_MAX 4294967295UL - -#define LLONG_MAX 9223372036854775807LL -#define LLONG_MIN (-LLONG_MAX - 1) -#define ULLONG_MAX 18446744073709551615ULL - -#endif /* lib/limits.h */ diff --git a/pintos-progos/lib/packed.h b/pintos-progos/lib/packed.h deleted file mode 100644 index 9a9b6e2..0000000 --- a/pintos-progos/lib/packed.h +++ /dev/null @@ -1,10 +0,0 @@ -#ifndef __LIB_PACKED_H -#define __LIB_PACKED_H - -/* The "packed" attribute, when applied to a structure, prevents - GCC from inserting padding bytes between or after structure - members. It must be specified at the time of the structure's - definition, normally just after the closing brace. */ -#define PACKED __attribute__ ((packed)) - -#endif /* lib/packed.h */ diff --git a/pintos-progos/lib/random.c b/pintos-progos/lib/random.c deleted file mode 100644 index a4761b6..0000000 --- a/pintos-progos/lib/random.c +++ /dev/null @@ -1,83 +0,0 @@ -#include "random.h" -#include -#include -#include "debug.h" - -/* RC4-based pseudo-random number generator (PRNG). - - RC4 is a stream cipher. We're not using it here for its - cryptographic properties, but because it is easy to implement - and its output is plenty random for non-cryptographic - purposes. - - See http://en.wikipedia.org/wiki/RC4_(cipher) for information - on RC4.*/ - -/* RC4 state. */ -static uint8_t s[256]; /* S[]. */ -static uint8_t s_i, s_j; /* i, j. */ - -/* Already initialized? */ -static bool inited; - -/* Swaps the bytes pointed to by A and B. */ -static inline void -swap_byte (uint8_t *a, uint8_t *b) -{ - uint8_t t = *a; - *a = *b; - *b = t; -} - -/* Initializes or reinitializes the PRNG with the given SEED. */ -void -random_init (unsigned seed) -{ - uint8_t *seedp = (uint8_t *) &seed; - int i; - uint8_t j; - - for (i = 0; i < 256; i++) - s[i] = i; - for (i = j = 0; i < 256; i++) - { - j += s[i] + seedp[i % sizeof seed]; - swap_byte (s + i, s + j); - } - - s_i = s_j = 0; - inited = true; -} - -/* Writes SIZE random bytes into BUF. */ -void -random_bytes (void *buf_, size_t size) -{ - uint8_t *buf; - - if (!inited) - random_init (0); - - for (buf = buf_; size-- > 0; buf++) - { - uint8_t s_k; - - s_i++; - s_j += s[s_i]; - swap_byte (s + s_i, s + s_j); - - s_k = s[s_i] + s[s_j]; - *buf = s[s_k]; - } -} - -/* Returns a pseudo-random unsigned long. - Use random_ulong() % n to obtain a random number in the range - 0...n (exclusive). */ -unsigned long -random_ulong (void) -{ - unsigned long ul; - random_bytes (&ul, sizeof ul); - return ul; -} diff --git a/pintos-progos/lib/random.h b/pintos-progos/lib/random.h deleted file mode 100644 index 0950ae2..0000000 --- a/pintos-progos/lib/random.h +++ /dev/null @@ -1,10 +0,0 @@ -#ifndef __LIB_RANDOM_H -#define __LIB_RANDOM_H - -#include - -void random_init (unsigned seed); -void random_bytes (void *, size_t); -unsigned long random_ulong (void); - -#endif /* lib/random.h */ diff --git a/pintos-progos/lib/round.h b/pintos-progos/lib/round.h deleted file mode 100644 index 3aa6642..0000000 --- a/pintos-progos/lib/round.h +++ /dev/null @@ -1,18 +0,0 @@ -#ifndef __LIB_ROUND_H -#define __LIB_ROUND_H - -/* Yields X rounded up to the nearest multiple of STEP. - For X >= 0, STEP >= 1 only. */ -#define ROUND_UP(X, STEP) (((X) + (STEP) - 1) / (STEP) * (STEP)) - -/* Yields X divided by STEP, rounded up. - For X >= 0, STEP >= 1 only. */ -#define DIV_ROUND_UP(X, STEP) (((X) + (STEP) - 1) / (STEP)) - -/* Yields X rounded down to the nearest multiple of STEP. - For X >= 0, STEP >= 1 only. */ -#define ROUND_DOWN(X, STEP) ((X) / (STEP) * (STEP)) - -/* There is no DIV_ROUND_DOWN. It would be simply X / STEP. */ - -#endif /* lib/round.h */ diff --git a/pintos-progos/lib/stdarg.h b/pintos-progos/lib/stdarg.h deleted file mode 100644 index 32622b5..0000000 --- a/pintos-progos/lib/stdarg.h +++ /dev/null @@ -1,14 +0,0 @@ -#ifndef __LIB_STDARG_H -#define __LIB_STDARG_H - -/* GCC has functionality as built-ins, - so all we need is to use it. */ - -typedef __builtin_va_list va_list; - -#define va_start(LIST, ARG) __builtin_va_start (LIST, ARG) -#define va_end(LIST) __builtin_va_end (LIST) -#define va_arg(LIST, TYPE) __builtin_va_arg (LIST, TYPE) -#define va_copy(DST, SRC) __builtin_va_copy (DST, SRC) - -#endif /* lib/stdarg.h */ diff --git a/pintos-progos/lib/stdbool.h b/pintos-progos/lib/stdbool.h deleted file mode 100644 index f173a91..0000000 --- a/pintos-progos/lib/stdbool.h +++ /dev/null @@ -1,9 +0,0 @@ -#ifndef __LIB_STDBOOL_H -#define __LIB_STDBOOL_H - -#define bool _Bool -#define true 1 -#define false 0 -#define __bool_true_false_are_defined 1 - -#endif /* lib/stdbool.h */ diff --git a/pintos-progos/lib/stddef.h b/pintos-progos/lib/stddef.h deleted file mode 100644 index 4e74fa6..0000000 --- a/pintos-progos/lib/stddef.h +++ /dev/null @@ -1,12 +0,0 @@ -#ifndef __LIB_STDDEF_H -#define __LIB_STDDEF_H - -#define NULL ((void *) 0) -#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *) 0)->MEMBER) - -/* GCC predefines the types we need for ptrdiff_t and size_t, - so that we don't have to guess. */ -typedef __PTRDIFF_TYPE__ ptrdiff_t; -typedef __SIZE_TYPE__ size_t; - -#endif /* lib/stddef.h */ diff --git a/pintos-progos/lib/stdint.h b/pintos-progos/lib/stdint.h deleted file mode 100644 index ef5f214..0000000 --- a/pintos-progos/lib/stdint.h +++ /dev/null @@ -1,51 +0,0 @@ -#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 4294967295U - -typedef unsigned long long int uint64_t; -#define UINT64_MAX 18446744073709551615ULL - -typedef int32_t intptr_t; -#define INTPTR_MIN INT32_MIN -#define INTPTR_MAX INT32_MAX - -typedef uint32_t uintptr_t; -#define UINTPTR_MAX UINT32_MAX - -typedef int64_t intmax_t; -#define INTMAX_MIN INT64_MIN -#define INTMAX_MAX INT64_MAX - -typedef uint64_t uintmax_t; -#define UINTMAX_MAX UINT64_MAX - -#define PTRDIFF_MIN INT32_MIN -#define PTRDIFF_MAX INT32_MAX - -#define SIZE_MAX UINT32_MAX - -#endif /* lib/stdint.h */ diff --git a/pintos-progos/lib/stdio.c b/pintos-progos/lib/stdio.c deleted file mode 100644 index 8927c50..0000000 --- a/pintos-progos/lib/stdio.c +++ /dev/null @@ -1,655 +0,0 @@ -#include -#include -#include -#include -#include -#include - -/* Auxiliary data for vsnprintf_helper(). */ -struct vsnprintf_aux - { - char *p; /* Current output position. */ - int length; /* Length of output string. */ - int max_length; /* Max length of output string. */ - }; - -static void vsnprintf_helper (char, void *); - -/* Like vprintf(), except that output is stored into BUFFER, - which must have space for BUF_SIZE characters. Writes at most - BUF_SIZE - 1 characters to BUFFER, followed by a null - terminator. BUFFER will always be null-terminated unless - BUF_SIZE is zero. Returns the number of characters that would - have been written to BUFFER, not including a null terminator, - had there been enough room. */ -int -vsnprintf (char *buffer, size_t buf_size, const char *format, va_list args) -{ - /* Set up aux data for vsnprintf_helper(). */ - struct vsnprintf_aux aux; - aux.p = buffer; - aux.length = 0; - aux.max_length = buf_size > 0 ? buf_size - 1 : 0; - - /* Do most of the work. */ - __vprintf (format, args, vsnprintf_helper, &aux); - - /* Add null terminator. */ - if (buf_size > 0) - *aux.p = '\0'; - - return aux.length; -} - -/* Helper function for vsnprintf(). */ -static void -vsnprintf_helper (char ch, void *aux_) -{ - struct vsnprintf_aux *aux = aux_; - - if (aux->length++ < aux->max_length) - *aux->p++ = ch; -} - -/* Like printf(), except that output is stored into BUFFER, - which must have space for BUF_SIZE characters. Writes at most - BUF_SIZE - 1 characters to BUFFER, followed by a null - terminator. BUFFER will always be null-terminated unless - BUF_SIZE is zero. Returns the number of characters that would - have been written to BUFFER, not including a null terminator, - had there been enough room. */ -int -snprintf (char *buffer, size_t buf_size, const char *format, ...) -{ - va_list args; - int retval; - - va_start (args, format); - retval = vsnprintf (buffer, buf_size, format, args); - va_end (args); - - return retval; -} - -/* Writes formatted output to the console. - In the kernel, the console is both the video display and first - serial port. - In userspace, the console is file descriptor 1. */ -int -printf (const char *format, ...) -{ - va_list args; - int retval; - - va_start (args, format); - retval = vprintf (format, args); - va_end (args); - - return retval; -} - -/* printf() formatting internals. */ - -/* A printf() conversion. */ -struct printf_conversion - { - /* Flags. */ - enum - { - MINUS = 1 << 0, /* '-' */ - PLUS = 1 << 1, /* '+' */ - SPACE = 1 << 2, /* ' ' */ - POUND = 1 << 3, /* '#' */ - ZERO = 1 << 4, /* '0' */ - GROUP = 1 << 5 /* '\'' */ - } - flags; - - /* Minimum field width. */ - int width; - - /* Numeric precision. - -1 indicates no precision was specified. */ - int precision; - - /* Type of argument to format. */ - enum - { - CHAR = 1, /* hh */ - SHORT = 2, /* h */ - INT = 3, /* (none) */ - INTMAX = 4, /* j */ - LONG = 5, /* l */ - LONGLONG = 6, /* ll */ - PTRDIFFT = 7, /* t */ - SIZET = 8 /* z */ - } - type; - }; - -struct integer_base - { - int base; /* Base. */ - const char *digits; /* Collection of digits. */ - int x; /* `x' character to use, for base 16 only. */ - int group; /* Number of digits to group with ' flag. */ - }; - -static const struct integer_base base_d = {10, "0123456789", 0, 3}; -static const struct integer_base base_o = {8, "01234567", 0, 3}; -static const struct integer_base base_x = {16, "0123456789abcdef", 'x', 4}; -static const struct integer_base base_X = {16, "0123456789ABCDEF", 'X', 4}; - -static const char *parse_conversion (const char *format, - struct printf_conversion *, - va_list *); -static void format_integer (uintmax_t value, bool is_signed, 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, int 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 INTMAX: - value = va_arg (args, intmax_t); - 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); - if (value > SIZE_MAX / 2) - value = value - SIZE_MAX - 1; - break; - default: - NOT_REACHED (); - } - - format_integer (value < 0 ? -value : value, - true, 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 INTMAX: - value = va_arg (args, uintmax_t); - 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); -#if UINTMAX_MAX != PTRDIFF_MAX - value &= ((uintmax_t) PTRDIFF_MAX << 1) | 1; -#endif - 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, 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 pointers as %#x. */ - void *p = va_arg (args, void *); - - c.flags = POUND; - format_integer ((uintptr_t) p, false, false, - &base_x, &c, output, aux); - } - break; - - case 'f': - case 'e': - case 'E': - case 'g': - case 'G': - case 'n': - /* We don't support floating-point arithmetic, - and %n can be part of a security hole. */ - __printf ("<>", output, aux, *format); - break; - - default: - __printf ("<>", output, aux, *format); - break; - } - } -} - -/* Parses conversion option characters starting at FORMAT and - initializes C appropriately. Returns the character in FORMAT - that indicates the conversion (e.g. the `d' in `%d'). Uses - *ARGS for `*' field widths and precisions. */ -static const char * -parse_conversion (const char *format, struct printf_conversion *c, - va_list *args) -{ - /* Parse flag characters. */ - c->flags = 0; - for (;;) - { - switch (*format++) - { - case '-': - c->flags |= MINUS; - break; - case '+': - c->flags |= PLUS; - break; - case ' ': - c->flags |= SPACE; - break; - case '#': - c->flags |= POUND; - break; - case '0': - c->flags |= ZERO; - break; - case '\'': - c->flags |= GROUP; - break; - default: - format--; - goto not_a_flag; - } - } - not_a_flag: - if (c->flags & MINUS) - c->flags &= ~ZERO; - if (c->flags & PLUS) - c->flags &= ~SPACE; - - /* Parse field width. */ - c->width = 0; - if (*format == '*') - { - format++; - c->width = va_arg (*args, int); - } - else - { - for (; isdigit (*format); format++) - c->width = c->width * 10 + *format - '0'; - } - if (c->width < 0) - { - c->width = -c->width; - c->flags |= MINUS; - } - - /* Parse precision. */ - c->precision = -1; - if (*format == '.') - { - format++; - if (*format == '*') - { - format++; - c->precision = va_arg (*args, int); - } - else - { - c->precision = 0; - for (; isdigit (*format); format++) - c->precision = c->precision * 10 + *format - '0'; - } - if (c->precision < 0) - c->precision = -1; - } - if (c->precision >= 0) - c->flags &= ~ZERO; - - /* Parse type. */ - c->type = INT; - switch (*format++) - { - case 'h': - if (*format == 'h') - { - format++; - c->type = CHAR; - } - else - c->type = SHORT; - break; - - case 'j': - c->type = INTMAX; - break; - - case 'l': - if (*format == 'l') - { - format++; - c->type = LONGLONG; - } - else - c->type = LONG; - break; - - case 't': - c->type = PTRDIFFT; - break; - - case 'z': - c->type = SIZET; - break; - - default: - format--; - break; - } - - return format; -} - -/* Performs an integer conversion, writing output to OUTPUT with - auxiliary data AUX. The integer converted has absolute value - VALUE. If IS_SIGNED is true, does a signed conversion with - NEGATIVE indicating a negative value; otherwise does an - unsigned conversion and ignores NEGATIVE. The output is done - according to the provided base B. Details of the conversion - are in C. */ -static void -format_integer (uintmax_t value, bool is_signed, 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. */ - int x; /* `x' character to use or 0 if none. */ - int sign; /* Sign character or 0 if none. */ - int precision; /* Rendered precision. */ - int pad_cnt; /* # of pad characters to fill field width. */ - int digit_cnt; /* # of digits output so far. */ - - /* Determine sign character, if any. - An unsigned conversion will never have a sign character, - even if one of the flags requests one. */ - sign = 0; - if (is_signed) - { - if (c->flags & PLUS) - sign = negative ? '-' : '+'; - else if (c->flags & SPACE) - sign = negative ? '-' : ' '; - else if (negative) - sign = '-'; - } - - /* Determine whether to include `0x' or `0X'. - It will only be included with a hexadecimal conversion of a - nonzero value with the # flag. */ - x = (c->flags & POUND) && value ? b->x : 0; - - /* Accumulate digits into buffer. - This algorithm produces digits in reverse order, so later we - will output the buffer's content in reverse. */ - cp = buf; - digit_cnt = 0; - while (value > 0) - { - if ((c->flags & GROUP) && digit_cnt > 0 && digit_cnt % b->group == 0) - *cp++ = ','; - *cp++ = b->digits[value % b->base]; - value /= b->base; - digit_cnt++; - } - - /* 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". - If the # flag is used with base 8, the result must always - begin with a zero. */ - precision = c->precision < 0 ? 1 : c->precision; - while (cp - buf < precision && cp < buf + sizeof buf - 1) - *cp++ = '0'; - if ((c->flags & POUND) && b->base == 8 && (cp == buf || cp[-1] != '0')) - *cp++ = '0'; - - /* Calculate number of pad characters to fill field width. */ - pad_cnt = c->width - (cp - buf) - (x ? 2 : 0) - (sign != 0); - if (pad_cnt < 0) - pad_cnt = 0; - - /* Do output. */ - if ((c->flags & (MINUS | ZERO)) == 0) - output_dup (' ', pad_cnt, output, aux); - if (sign) - output (sign, aux); - if (x) - { - output ('0', aux); - output (x, 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, int length, - struct printf_conversion *c, - void (*output) (char, void *), void *aux) -{ - int i; - if (c->width > length && (c->flags & MINUS) == 0) - output_dup (' ', c->width - length, output, aux); - for (i = 0; i < length; i++) - output (string[i], aux); - if (c->width > length && (c->flags & MINUS) != 0) - output_dup (' ', c->width - length, 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); -} - -/* Dumps the SIZE bytes in BUF to the console as hex bytes - arranged 16 per line. Numeric offsets are also included, - starting at OFS for the first byte in BUF. If ASCII is true - then the corresponding ASCII characters are also rendered - alongside. */ -void -hex_dump (uintptr_t ofs, const void *buf_, size_t size, bool ascii) -{ - const uint8_t *buf = buf_; - const size_t per_line = 16; /* Maximum bytes per line. */ - - while (size > 0) - { - size_t start, end, n; - size_t i; - - /* Number of bytes on this line. */ - start = ofs % per_line; - end = per_line; - if (end - start > size) - end = start + size; - n = end - start; - - /* Print line. */ - printf ("%08jx ", (uintmax_t) ROUND_DOWN (ofs, per_line)); - for (i = 0; i < start; i++) - printf (" "); - for (; i < end; i++) - printf ("%02hhx%c", - buf[i - start], i == per_line / 2 - 1? '-' : ' '); - if (ascii) - { - for (; i < per_line; i++) - printf (" "); - printf ("|"); - for (i = 0; i < start; i++) - printf (" "); - for (; i < end; i++) - printf ("%c", - isprint (buf[i - start]) ? buf[i - start] : '.'); - for (; i < per_line; i++) - printf (" "); - printf ("|"); - } - printf ("\n"); - - ofs += n; - buf += n; - size -= n; - } -} - -/* Prints SIZE, which represents a number of bytes, in a - human-readable format, e.g. "256 kB". */ -void -print_human_readable_size (uint64_t size) -{ - if (size == 1) - printf ("1 byte"); - else - { - static const char *factors[] = {"bytes", "kB", "MB", "GB", "TB", NULL}; - const char **fp; - - for (fp = factors; size >= 1024 && fp[1] != NULL; fp++) - size /= 1024; - printf ("%"PRIu64" %s", size, *fp); - } -} diff --git a/pintos-progos/lib/stdio.h b/pintos-progos/lib/stdio.h deleted file mode 100644 index 2739c0a..0000000 --- a/pintos-progos/lib/stdio.h +++ /dev/null @@ -1,40 +0,0 @@ -#ifndef __LIB_STDIO_H -#define __LIB_STDIO_H - -#include -#include -#include -#include -#include - -/* Include lib/user/stdio.h or lib/kernel/stdio.h, as - appropriate. */ -#include_next - -/* Predefined file handles. */ -#define STDIN_FILENO 0 -#define STDOUT_FILENO 1 - -/* Standard functions. */ -int printf (const char *, ...) PRINTF_FORMAT (1, 2); -int snprintf (char *, size_t, const char *, ...) PRINTF_FORMAT (3, 4); -int vprintf (const char *, va_list) PRINTF_FORMAT (1, 0); -int vsnprintf (char *, size_t, const char *, va_list) PRINTF_FORMAT (3, 0); -int putchar (int); -int puts (const char *); - -/* Nonstandard functions. */ -void hex_dump (uintptr_t ofs, const void *, size_t size, bool ascii); -void print_human_readable_size (uint64_t sz); - -/* Internal functions. */ -void __vprintf (const char *format, va_list args, - void (*output) (char, void *), void *aux); -void __printf (const char *format, - void (*output) (char, void *), void *aux, ...); - -/* Try to be helpful. */ -#define sprintf dont_use_sprintf_use_snprintf -#define vsprintf dont_use_vsprintf_use_vsnprintf - -#endif /* lib/stdio.h */ diff --git a/pintos-progos/lib/stdlib.c b/pintos-progos/lib/stdlib.c deleted file mode 100644 index 84c7f61..0000000 --- a/pintos-progos/lib/stdlib.c +++ /dev/null @@ -1,208 +0,0 @@ -#include -#include -#include -#include -#include - -/* Converts a string representation of a signed decimal integer - in S into an `int', which is returned. */ -int -atoi (const char *s) -{ - bool negative; - int value; - - ASSERT (s != NULL); - - /* Skip white space. */ - while (isspace ((unsigned char) *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; -} - -/* Compares A and B by calling the AUX function. */ -static int -compare_thunk (const void *a, const void *b, void *aux) -{ - int (**compare) (const void *, const void *) = aux; - return (*compare) (a, b); -} - -/* Sorts ARRAY, which contains CNT elements of SIZE bytes each, - using COMPARE. When COMPARE is passed a pair of elements A - and B, respectively, it must return a strcmp()-type result, - i.e. less than zero if A < B, zero if A == B, greater than - zero if A > B. Runs in O(n lg n) time and O(1) space in - CNT. */ -void -qsort (void *array, size_t cnt, size_t size, - int (*compare) (const void *, const void *)) -{ - sort (array, cnt, size, compare_thunk, &compare); -} - -/* Swaps elements with 1-based indexes A_IDX and B_IDX in ARRAY - with elements of SIZE bytes each. */ -static void -do_swap (unsigned char *array, size_t a_idx, size_t b_idx, size_t size) -{ - unsigned char *a = array + (a_idx - 1) * size; - unsigned char *b = array + (b_idx - 1) * size; - size_t i; - - for (i = 0; i < size; i++) - { - unsigned char t = a[i]; - a[i] = b[i]; - b[i] = t; - } -} - -/* Compares elements with 1-based indexes A_IDX and B_IDX in - ARRAY with elements of SIZE bytes each, using COMPARE to - compare elements, passing AUX as auxiliary data, and returns a - strcmp()-type result. */ -static int -do_compare (unsigned char *array, size_t a_idx, size_t b_idx, size_t size, - int (*compare) (const void *, const void *, void *aux), - void *aux) -{ - return compare (array + (a_idx - 1) * size, array + (b_idx - 1) * size, aux); -} - -/* "Float down" the element with 1-based index I in ARRAY of CNT - elements of SIZE bytes each, using COMPARE to compare - elements, passing AUX as auxiliary data. */ -static void -heapify (unsigned char *array, size_t i, size_t cnt, size_t size, - int (*compare) (const void *, const void *, void *aux), - void *aux) -{ - for (;;) - { - /* Set `max' to the index of the largest element among I - and its children (if any). */ - size_t left = 2 * i; - size_t right = 2 * i + 1; - size_t max = i; - if (left <= cnt && do_compare (array, left, max, size, compare, aux) > 0) - max = left; - if (right <= cnt - && do_compare (array, right, max, size, compare, aux) > 0) - max = right; - - /* If the maximum value is already in element I, we're - done. */ - if (max == i) - break; - - /* Swap and continue down the heap. */ - do_swap (array, i, max, size); - i = max; - } -} - -/* Sorts ARRAY, which contains CNT elements of SIZE bytes each, - using COMPARE to compare elements, passing AUX as auxiliary - data. When COMPARE is passed a pair of elements A and B, - respectively, it must return a strcmp()-type result, i.e. less - than zero if A < B, zero if A == B, greater than zero if A > - B. Runs in O(n lg n) time and O(1) space in CNT. */ -void -sort (void *array, size_t cnt, size_t size, - int (*compare) (const void *, const void *, void *aux), - void *aux) -{ - size_t i; - - ASSERT (array != NULL || cnt == 0); - ASSERT (compare != NULL); - ASSERT (size > 0); - - /* Build a heap. */ - for (i = cnt / 2; i > 0; i--) - heapify (array, i, cnt, size, compare, aux); - - /* Sort the heap. */ - for (i = cnt; i > 1; i--) - { - do_swap (array, 1, i, size); - heapify (array, 1, i - 1, size, compare, aux); - } -} - -/* Searches ARRAY, which contains CNT elements of SIZE bytes - each, for the given KEY. Returns a match is found, otherwise - a null pointer. If there are multiple matches, returns an - arbitrary one of them. - - ARRAY must be sorted in order according to COMPARE. - - Uses COMPARE to compare elements. When COMPARE is passed a - pair of elements A and B, respectively, it must return a - strcmp()-type result, i.e. less than zero if A < B, zero if A - == B, greater than zero if A > B. */ -void * -bsearch (const void *key, const void *array, size_t cnt, - size_t size, int (*compare) (const void *, const void *)) -{ - return binary_search (key, array, cnt, size, compare_thunk, &compare); -} - -/* Searches ARRAY, which contains CNT elements of SIZE bytes - each, for the given KEY. Returns a match is found, otherwise - a null pointer. If there are multiple matches, returns an - arbitrary one of them. - - ARRAY must be sorted in order according to COMPARE. - - Uses COMPARE to compare elements, passing AUX as auxiliary - data. When COMPARE is passed a pair of elements A and B, - respectively, it must return a strcmp()-type result, i.e. less - than zero if A < B, zero if A == B, greater than zero if A > - B. */ -void * -binary_search (const void *key, const void *array, size_t cnt, size_t size, - int (*compare) (const void *, const void *, void *aux), - void *aux) -{ - const unsigned char *first = array; - const unsigned char *last = array + size * cnt; - - while (first < last) - { - size_t range = (last - first) / size; - const unsigned char *middle = first + (range / 2) * size; - int cmp = compare (key, middle, aux); - - if (cmp < 0) - last = middle; - else if (cmp > 0) - first = middle + size; - else - return (void *) middle; - } - - return NULL; -} - diff --git a/pintos-progos/lib/stdlib.h b/pintos-progos/lib/stdlib.h deleted file mode 100644 index d14afa3..0000000 --- a/pintos-progos/lib/stdlib.h +++ /dev/null @@ -1,22 +0,0 @@ -#ifndef __LIB_STDLIB_H -#define __LIB_STDLIB_H - -#include - -/* Standard functions. */ -int atoi (const char *); -void qsort (void *array, size_t cnt, size_t size, - int (*compare) (const void *, const void *)); -void *bsearch (const void *key, const void *array, size_t cnt, - size_t size, int (*compare) (const void *, const void *)); - -/* Nonstandard functions. */ -void sort (void *array, size_t cnt, size_t size, - int (*compare) (const void *, const void *, void *aux), - void *aux); -void *binary_search (const void *key, const void *array, size_t cnt, - size_t size, - int (*compare) (const void *, const void *, void *aux), - void *aux); - -#endif /* lib/stdlib.h */ diff --git a/pintos-progos/lib/string.c b/pintos-progos/lib/string.c deleted file mode 100644 index d223c89..0000000 --- a/pintos-progos/lib/string.c +++ /dev/null @@ -1,375 +0,0 @@ -#include -#include - -/* Copies SIZE bytes from SRC to DST, which must not overlap. - Returns DST. */ -void * -memcpy (void *dst_, const void *src_, size_t size) -{ - unsigned char *dst = dst_; - const unsigned char *src = src_; - - ASSERT (dst != NULL || size == 0); - ASSERT (src != NULL || size == 0); - - while (size-- > 0) - *dst++ = *src++; - - return dst_; -} - -/* Copies SIZE bytes from SRC to DST, which are allowed to - overlap. Returns DST. */ -void * -memmove (void *dst_, const void *src_, size_t size) -{ - unsigned char *dst = dst_; - const unsigned char *src = src_; - - ASSERT (dst != NULL || size == 0); - ASSERT (src != NULL || size == 0); - - if (dst < src) - { - while (size-- > 0) - *dst++ = *src++; - } - else - { - dst += size; - src += size; - while (size-- > 0) - *--dst = *--src; - } - - return dst; -} - -/* Find the first differing byte in the two blocks of SIZE bytes - at A and B. Returns a positive value if the byte in A is - greater, a negative value if the byte in B is greater, or zero - if blocks A and B are equal. */ -int -memcmp (const void *a_, const void *b_, size_t size) -{ - const unsigned char *a = a_; - const unsigned char *b = b_; - - ASSERT (a != NULL || size == 0); - ASSERT (b != NULL || size == 0); - - for (; size-- > 0; a++, b++) - if (*a != *b) - return *a > *b ? +1 : -1; - return 0; -} - -/* Finds the first differing characters in strings A and B. - Returns a positive value if the character in A (as an unsigned - char) is greater, a negative value if the character in B (as - an unsigned char) is greater, or zero if strings A and B are - equal. */ -int -strcmp (const char *a_, const char *b_) -{ - const unsigned char *a = (const unsigned char *) a_; - const unsigned char *b = (const unsigned char *) b_; - - ASSERT (a != NULL); - ASSERT (b != NULL); - - while (*a != '\0' && *a == *b) - { - a++; - b++; - } - - return *a < *b ? -1 : *a > *b; -} - -/* Returns a pointer to the first occurrence of CH in the first - SIZE bytes starting at BLOCK. Returns a null pointer if CH - does not occur in BLOCK. */ -void * -memchr (const void *block_, int ch_, size_t size) -{ - const unsigned char *block = block_; - unsigned char ch = ch_; - - ASSERT (block != NULL || size == 0); - - for (; size-- > 0; block++) - if (*block == ch) - return (void *) block; - - return NULL; -} - -/* Finds and returns the first occurrence of C in STRING, or a - null pointer if C does not appear in STRING. If C == '\0' - then returns a pointer to the null terminator at the end of - STRING. */ -char * -strchr (const char *string, int c_) -{ - char c = c_; - - ASSERT (string != NULL); - - for (;;) - if (*string == c) - return (char *) string; - else if (*string == '\0') - return NULL; - else - string++; -} - -/* Returns the length of the initial substring of STRING that - consists of characters that are not in STOP. */ -size_t -strcspn (const char *string, const char *stop) -{ - size_t length; - - for (length = 0; string[length] != '\0'; length++) - if (strchr (stop, string[length]) != NULL) - break; - return length; -} - -/* Returns a pointer to the first character in STRING that is - also in STOP. If no character in STRING is in STOP, returns a - null pointer. */ -char * -strpbrk (const char *string, const char *stop) -{ - for (; *string != '\0'; string++) - if (strchr (stop, *string) != NULL) - return (char *) string; - return NULL; -} - -/* Returns a pointer to the last occurrence of C in STRING. - Returns a null pointer if C does not occur in STRING. */ -char * -strrchr (const char *string, int c_) -{ - char c = c_; - const char *p = NULL; - - for (; *string != '\0'; string++) - if (*string == c) - p = string; - return (char *) p; -} - -/* Returns the length of the initial substring of STRING that - consists of characters in SKIP. */ -size_t -strspn (const char *string, const char *skip) -{ - size_t length; - - for (length = 0; string[length] != '\0'; length++) - if (strchr (skip, string[length]) == NULL) - break; - return length; -} - -/* Returns a pointer to the first occurrence of NEEDLE within - HAYSTACK. Returns a null pointer if NEEDLE does not exist - within HAYSTACK. */ -char * -strstr (const char *haystack, const char *needle) -{ - size_t haystack_len = strlen (haystack); - size_t needle_len = strlen (needle); - - if (haystack_len >= needle_len) - { - size_t i; - - for (i = 0; i <= haystack_len - needle_len; i++) - if (!memcmp (haystack + i, needle, needle_len)) - return (char *) haystack + i; - } - - return NULL; -} - -/* Breaks a string into tokens separated by DELIMITERS. The - first time this function is called, S should be the string to - tokenize, and in subsequent calls it must be a null pointer. - SAVE_PTR is the address of a `char *' variable used to keep - track of the tokenizer's position. The return value each time - is the next token in the string, or a null pointer if no - tokens remain. - - This function treats multiple adjacent delimiters as a single - delimiter. The returned tokens will never be length 0. - DELIMITERS may change from one call to the next within a - single string. - - strtok_r() modifies the string S, changing delimiters to null - bytes. Thus, S must be a modifiable string. String literals, - in particular, are *not* modifiable in C, even though for - backward compatibility they are not `const'. - - 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) - dst_len = src_len; - memcpy (dst, src, dst_len); - dst[dst_len] = '\0'; - } - return src_len; -} - -/* Concatenates string SRC to DST. The concatenated string is - limited to SIZE - 1 characters. A null terminator is always - written to DST, unless SIZE is 0. Returns the length that the - concatenated string would have assuming that there was - sufficient space, not including a null terminator. - - strlcat() is not in the standard C library, but it is an - increasingly popular extension. See - http://www.courtesan.com/todd/papers/strlcpy.html for - information on strlcpy(). */ -size_t -strlcat (char *dst, const char *src, size_t size) -{ - size_t src_len, dst_len; - - ASSERT (dst != NULL); - ASSERT (src != NULL); - - src_len = strlen (src); - dst_len = strlen (dst); - if (size > 0 && dst_len < size) - { - size_t copy_cnt = size - dst_len - 1; - if (src_len < copy_cnt) - copy_cnt = src_len; - memcpy (dst + dst_len, src, copy_cnt); - dst[dst_len + copy_cnt] = '\0'; - } - return src_len + dst_len; -} - diff --git a/pintos-progos/lib/string.h b/pintos-progos/lib/string.h deleted file mode 100644 index 1fff82a..0000000 --- a/pintos-progos/lib/string.h +++ /dev/null @@ -1,35 +0,0 @@ -#ifndef __LIB_STRING_H -#define __LIB_STRING_H - -#include - -/* Standard. */ -void *memcpy (void *, const void *, size_t); -void *memmove (void *, const void *, size_t); -char *strncat (char *, const char *, size_t); -int memcmp (const void *, const void *, size_t); -int strcmp (const char *, const char *); -void *memchr (const void *, int, size_t); -char *strchr (const char *, int); -size_t strcspn (const char *, const char *); -char *strpbrk (const char *, const char *); -char *strrchr (const char *, int); -size_t strspn (const char *, const char *); -char *strstr (const char *, const char *); -void *memset (void *, int, size_t); -size_t strlen (const char *); - -/* Extensions. */ -size_t strlcpy (char *, const char *, size_t); -size_t strlcat (char *, const char *, size_t); -char *strtok_r (char *, const char *, char **); -size_t strnlen (const char *, size_t); - -/* Try to be helpful. */ -#define strcpy dont_use_strcpy_use_strlcpy -#define strncpy dont_use_strncpy_use_strlcpy -#define strcat dont_use_strcat_use_strlcat -#define strncat dont_use_strncat_use_strlcat -#define strtok dont_use_strtok_use_strtok_r - -#endif /* lib/string.h */ diff --git a/pintos-progos/lib/syscall-nr.h b/pintos-progos/lib/syscall-nr.h deleted file mode 100644 index 21a7af9..0000000 --- a/pintos-progos/lib/syscall-nr.h +++ /dev/null @@ -1,34 +0,0 @@ -#ifndef __LIB_SYSCALL_NR_H -#define __LIB_SYSCALL_NR_H - -/* System call numbers. */ -enum - { - /* Projects 2 and later. */ - SYS_HALT, /* Halt the operating system. */ - SYS_EXIT, /* Terminate this process. */ - SYS_EXEC, /* Start another process. */ - SYS_WAIT, /* Wait for a child process to die. */ - SYS_CREATE, /* Create a file. */ - SYS_REMOVE, /* Delete a file. */ - SYS_OPEN, /* Open a file. */ - SYS_FILESIZE, /* Obtain a file's size. */ - SYS_READ, /* Read from a file. */ - SYS_WRITE, /* Write to a file. */ - SYS_SEEK, /* Change position in a file. */ - SYS_TELL, /* Report current position in a file. */ - SYS_CLOSE, /* Close a file. */ - - /* Project 3 and optionally project 4. */ - SYS_MMAP, /* Map a file into memory. */ - SYS_MUNMAP, /* Remove a memory mapping. */ - - /* Project 4 only. */ - SYS_CHDIR, /* Change the current directory. */ - SYS_MKDIR, /* Create a directory. */ - SYS_READDIR, /* Reads a directory entry. */ - SYS_ISDIR, /* Tests if a fd represents a directory. */ - SYS_INUMBER /* Returns the inode number for a fd. */ - }; - -#endif /* lib/syscall-nr.h */ diff --git a/pintos-progos/lib/user/console.c b/pintos-progos/lib/user/console.c deleted file mode 100644 index 22bdc8c..0000000 --- a/pintos-progos/lib/user/console.c +++ /dev/null @@ -1,94 +0,0 @@ -#include -#include -#include -#include - -/* The standard vprintf() function, - which is like printf() but uses a va_list. */ -int -vprintf (const char *format, va_list args) -{ - return vhprintf (STDOUT_FILENO, format, args); -} - -/* Like printf(), but writes output to the given HANDLE. */ -int -hprintf (int handle, const char *format, ...) -{ - va_list args; - int retval; - - va_start (args, format); - retval = vhprintf (handle, format, args); - va_end (args); - - return retval; -} - -/* Writes string S to the console, followed by a new-line - character. */ -int -puts (const char *s) -{ - write (STDOUT_FILENO, s, strlen (s)); - putchar ('\n'); - - return 0; -} - -/* Writes C to the console. */ -int -putchar (int c) -{ - char c2 = c; - write (STDOUT_FILENO, &c2, 1); - return c; -} - -/* Auxiliary data for vhprintf_helper(). */ -struct vhprintf_aux - { - char buf[64]; /* Character buffer. */ - char *p; /* Current position in buffer. */ - int char_cnt; /* Total characters written so far. */ - int handle; /* Output file handle. */ - }; - -static void add_char (char, void *); -static void flush (struct vhprintf_aux *); - -/* Formats the printf() format specification FORMAT with - arguments given in ARGS and writes the output to the given - HANDLE. */ -int -vhprintf (int handle, const char *format, va_list args) -{ - struct vhprintf_aux aux; - aux.p = aux.buf; - aux.char_cnt = 0; - aux.handle = handle; - __vprintf (format, args, add_char, &aux); - flush (&aux); - return aux.char_cnt; -} - -/* Adds C to the buffer in AUX, flushing it if the buffer fills - up. */ -static void -add_char (char c, void *aux_) -{ - struct vhprintf_aux *aux = aux_; - *aux->p++ = c; - if (aux->p >= aux->buf + sizeof aux->buf) - flush (aux); - aux->char_cnt++; -} - -/* Flushes the buffer in AUX. */ -static void -flush (struct vhprintf_aux *aux) -{ - if (aux->p > aux->buf) - write (aux->handle, aux->buf, aux->p - aux->buf); - aux->p = aux->buf; -} diff --git a/pintos-progos/lib/user/debug.c b/pintos-progos/lib/user/debug.c deleted file mode 100644 index f49b874..0000000 --- a/pintos-progos/lib/user/debug.c +++ /dev/null @@ -1,25 +0,0 @@ -#include -#include -#include -#include -#include - -/* Aborts the user program, printing the source file name, line - number, and function name, plus a user-specific message. */ -void -debug_panic (const char *file, int line, const char *function, - const char *message, ...) -{ - va_list args; - - printf ("User process ABORT at %s:%d in %s(): ", file, line, function); - - va_start (args, message); - vprintf (message, args); - printf ("\n"); - va_end (args); - - debug_backtrace (); - - exit (1); -} diff --git a/pintos-progos/lib/user/entry.c b/pintos-progos/lib/user/entry.c deleted file mode 100644 index a707c70..0000000 --- a/pintos-progos/lib/user/entry.c +++ /dev/null @@ -1,10 +0,0 @@ -#include - -int main (int, char *[]); -void _start (int argc, char *argv[]); - -void -_start (int argc, char *argv[]) -{ - exit (main (argc, argv)); -} diff --git a/pintos-progos/lib/user/stdio.h b/pintos-progos/lib/user/stdio.h deleted file mode 100644 index b9f3cc6..0000000 --- a/pintos-progos/lib/user/stdio.h +++ /dev/null @@ -1,7 +0,0 @@ -#ifndef __LIB_USER_STDIO_H -#define __LIB_USER_STDIO_H - -int hprintf (int, const char *, ...) PRINTF_FORMAT (2, 3); -int vhprintf (int, const char *, va_list) PRINTF_FORMAT (2, 0); - -#endif /* lib/user/stdio.h */ diff --git a/pintos-progos/lib/user/syscall.c b/pintos-progos/lib/user/syscall.c deleted file mode 100644 index 0a467f8..0000000 --- a/pintos-progos/lib/user/syscall.c +++ /dev/null @@ -1,184 +0,0 @@ -#include -#include "../syscall-nr.h" - -/* Invokes syscall NUMBER, passing no arguments, and returns the - return value as an `int'. */ -#define syscall0(NUMBER) \ - ({ \ - int retval; \ - asm volatile \ - ("pushl %[number]; int $0x30; addl $4, %%esp" \ - : "=a" (retval) \ - : [number] "i" (NUMBER) \ - : "memory"); \ - retval; \ - }) - -/* Invokes syscall NUMBER, passing argument ARG0, and returns the - return value as an `int'. */ -#define syscall1(NUMBER, ARG0) \ - ({ \ - int retval; \ - asm volatile \ - ("pushl %[arg0]; pushl %[number]; int $0x30; addl $8, %%esp" \ - : "=a" (retval) \ - : [number] "i" (NUMBER), \ - [arg0] "g" (ARG0) \ - : "memory"); \ - retval; \ - }) - -/* Invokes syscall NUMBER, passing arguments ARG0 and ARG1, and - returns the return value as an `int'. */ -#define syscall2(NUMBER, ARG0, ARG1) \ - ({ \ - int retval; \ - asm volatile \ - ("pushl %[arg1]; pushl %[arg0]; " \ - "pushl %[number]; int $0x30; addl $12, %%esp" \ - : "=a" (retval) \ - : [number] "i" (NUMBER), \ - [arg0] "r" (ARG0), \ - [arg1] "r" (ARG1) \ - : "memory"); \ - retval; \ - }) - -/* Invokes syscall NUMBER, passing arguments ARG0, ARG1, and - ARG2, and returns the return value as an `int'. */ -#define syscall3(NUMBER, ARG0, ARG1, ARG2) \ - ({ \ - int retval; \ - asm volatile \ - ("pushl %[arg2]; pushl %[arg1]; pushl %[arg0]; " \ - "pushl %[number]; int $0x30; addl $16, %%esp" \ - : "=a" (retval) \ - : [number] "i" (NUMBER), \ - [arg0] "r" (ARG0), \ - [arg1] "r" (ARG1), \ - [arg2] "r" (ARG2) \ - : "memory"); \ - retval; \ - }) - -void -halt (void) -{ - syscall0 (SYS_HALT); - NOT_REACHED (); -} - -void -exit (int status) -{ - syscall1 (SYS_EXIT, status); - NOT_REACHED (); -} - -pid_t -exec (const char *cmd_line) -{ - return (pid_t) syscall1 (SYS_EXEC, cmd_line); -} - -int -wait (pid_t pid) -{ - return syscall1 (SYS_WAIT, pid); -} - -bool -create (const char *file, unsigned initial_size) -{ - return syscall2 (SYS_CREATE, file, initial_size); -} - -bool -remove (const char *file) -{ - return syscall1 (SYS_REMOVE, file); -} - -int -open (const char *file) -{ - return syscall1 (SYS_OPEN, file); -} - -int -filesize (int fd) -{ - return syscall1 (SYS_FILESIZE, fd); -} - -int -read (int fd, void *buffer, unsigned size) -{ - return syscall3 (SYS_READ, fd, buffer, size); -} - -int -write (int fd, const void *buffer, unsigned size) -{ - return syscall3 (SYS_WRITE, fd, buffer, size); -} - -void -seek (int fd, unsigned position) -{ - syscall2 (SYS_SEEK, fd, position); -} - -unsigned -tell (int fd) -{ - return syscall1 (SYS_TELL, fd); -} - -void -close (int fd) -{ - syscall1 (SYS_CLOSE, fd); -} - -mapid_t -mmap (int fd, void *addr) -{ - return syscall2 (SYS_MMAP, fd, addr); -} - -void -munmap (mapid_t mapid) -{ - syscall1 (SYS_MUNMAP, mapid); -} - -bool -chdir (const char *dir) -{ - return syscall1 (SYS_CHDIR, dir); -} - -bool -mkdir (const char *dir) -{ - return syscall1 (SYS_MKDIR, dir); -} - -bool -readdir (int fd, char name[READDIR_MAX_LEN + 1]) -{ - return syscall2 (SYS_READDIR, fd, name); -} - -bool -isdir (int fd) -{ - return syscall1 (SYS_ISDIR, fd); -} - -int -inumber (int fd) -{ - return syscall1 (SYS_INUMBER, fd); -} diff --git a/pintos-progos/lib/user/syscall.h b/pintos-progos/lib/user/syscall.h deleted file mode 100644 index a1bcf0b..0000000 --- a/pintos-progos/lib/user/syscall.h +++ /dev/null @@ -1,48 +0,0 @@ -#ifndef __LIB_USER_SYSCALL_H -#define __LIB_USER_SYSCALL_H - -#include -#include - -/* Process identifier. */ -typedef int pid_t; -#define PID_ERROR ((pid_t) -1) - -/* Map region identifier. */ -typedef int mapid_t; -#define MAP_FAILED ((mapid_t) -1) - -/* Maximum characters in a filename written by readdir(). */ -#define READDIR_MAX_LEN 14 - -/* Typical return values from main() and arguments to exit(). */ -#define EXIT_SUCCESS 0 /* Successful execution. */ -#define EXIT_FAILURE 1 /* Unsuccessful execution. */ - -/* Projects 2 and later. */ -void halt (void) NO_RETURN; -void exit (int status) NO_RETURN; -pid_t exec (const char *cmd_line); -int wait (pid_t); -bool create (const char *file, unsigned initial_size); -bool remove (const char *file); -int open (const char *file); -int filesize (int fd); -int read (int fd, void *buffer, unsigned length); -int write (int fd, const void *buffer, unsigned length); -void seek (int fd, unsigned position); -unsigned tell (int fd); -void close (int fd); - -/* Project 3 and optionally project 4. */ -mapid_t mmap (int fd, void *addr); -void munmap (mapid_t); - -/* Project 4 only. */ -bool chdir (const char *dir); -bool mkdir (const char *dir); -bool readdir (int fd, char name[READDIR_MAX_LEN + 1]); -bool isdir (int fd); -int inumber (int fd); - -#endif /* lib/user/syscall.h */ diff --git a/pintos-progos/lib/user/user.lds b/pintos-progos/lib/user/user.lds deleted file mode 100644 index cc6d6c0..0000000 --- a/pintos-progos/lib/user/user.lds +++ /dev/null @@ -1,57 +0,0 @@ -OUTPUT_FORMAT("elf32-i386") -OUTPUT_ARCH(i386) -ENTRY(_start) - -SECTIONS -{ - /* Read-only sections, merged into text segment: */ - __executable_start = 0x08048000 + SIZEOF_HEADERS; - . = 0x08048000 + SIZEOF_HEADERS; - .text : { *(.text) } = 0x90 - .rodata : { *(.rodata) } - - /* Adjust the address for the data segment. We want to adjust up to - the same address within the page on the next page up. */ - . = ALIGN (0x1000) - ((0x1000 - .) & (0x1000 - 1)); - . = DATA_SEGMENT_ALIGN (0x1000, 0x1000); - - .data : { *(.data) } - .bss : { *(.bss) } - - /* Stabs debugging sections. */ - .stab 0 : { *(.stab) } - .stabstr 0 : { *(.stabstr) } - .stab.excl 0 : { *(.stab.excl) } - .stab.exclstr 0 : { *(.stab.exclstr) } - .stab.index 0 : { *(.stab.index) } - .stab.indexstr 0 : { *(.stab.indexstr) } - .comment 0 : { *(.comment) } - - /* DWARF debug sections. - Symbols in the DWARF debugging sections are relative to the beginning - of the section so we begin them at 0. */ - /* DWARF 1 */ - .debug 0 : { *(.debug) } - .line 0 : { *(.line) } - /* GNU DWARF 1 extensions */ - .debug_srcinfo 0 : { *(.debug_srcinfo) } - .debug_sfnames 0 : { *(.debug_sfnames) } - /* DWARF 1.1 and DWARF 2 */ - .debug_aranges 0 : { *(.debug_aranges) } - .debug_pubnames 0 : { *(.debug_pubnames) } - /* DWARF 2 */ - .debug_info 0 : { *(.debug_info .gnu.linkonce.wi.*) } - .debug_abbrev 0 : { *(.debug_abbrev) } - .debug_line 0 : { *(.debug_line) } - .debug_frame 0 : { *(.debug_frame) } - .debug_str 0 : { *(.debug_str) } - .debug_loc 0 : { *(.debug_loc) } - .debug_macinfo 0 : { *(.debug_macinfo) } - /* SGI/MIPS DWARF 2 extensions */ - .debug_weaknames 0 : { *(.debug_weaknames) } - .debug_funcnames 0 : { *(.debug_funcnames) } - .debug_typenames 0 : { *(.debug_typenames) } - .debug_varnames 0 : { *(.debug_varnames) } - /DISCARD/ : { *(.note.GNU-stack) } - /DISCARD/ : { *(.eh_frame) } -} diff --git a/pintos-progos/lib/ustar.c b/pintos-progos/lib/ustar.c deleted file mode 100644 index 49af69a..0000000 --- a/pintos-progos/lib/ustar.c +++ /dev/null @@ -1,228 +0,0 @@ -#include -#include -#include -#include -#include - -/* Header for ustar-format tar archive. See the documentation of - the "pax" utility in [SUSv3] for the the "ustar" format - specification. */ -struct ustar_header - { - char name[100]; /* File name. Null-terminated if room. */ - char mode[8]; /* Permissions as octal string. */ - char uid[8]; /* User ID as octal string. */ - char gid[8]; /* Group ID as octal string. */ - char size[12]; /* File size in bytes as octal string. */ - char mtime[12]; /* Modification time in seconds - from Jan 1, 1970, as octal string. */ - char chksum[8]; /* Sum of octets in header as octal string. */ - char typeflag; /* An enum ustar_type value. */ - char linkname[100]; /* Name of link target. - Null-terminated if room. */ - char magic[6]; /* "ustar\0" */ - char version[2]; /* "00" */ - char uname[32]; /* User name, always null-terminated. */ - char gname[32]; /* Group name, always null-terminated. */ - char devmajor[8]; /* Device major number as octal string. */ - char devminor[8]; /* Device minor number as octal string. */ - char prefix[155]; /* Prefix to file name. - Null-terminated if room. */ - char padding[12]; /* Pad to 512 bytes. */ - } -PACKED; - -/* Returns the checksum for the given ustar format HEADER. */ -static unsigned int -calculate_chksum (const struct ustar_header *h) -{ - const uint8_t *header = (const uint8_t *) h; - unsigned int chksum; - size_t i; - - chksum = 0; - for (i = 0; i < USTAR_HEADER_SIZE; i++) - { - /* The ustar checksum is calculated as if the chksum field - were all spaces. */ - const size_t chksum_start = offsetof (struct ustar_header, chksum); - const size_t chksum_end = chksum_start + sizeof h->chksum; - bool in_chksum_field = i >= chksum_start && i < chksum_end; - chksum += in_chksum_field ? ' ' : header[i]; - } - return chksum; -} - -/* Drop possibly dangerous prefixes from FILE_NAME and return the - stripped name. An archive with file names that start with "/" - or "../" could cause a naive tar extractor to write to - arbitrary parts of the file system, not just the destination - directory. We don't want to create such archives or be such a - naive extractor. - - The return value can be a suffix of FILE_NAME or a string - literal. */ -static const char * -strip_antisocial_prefixes (const char *file_name) -{ - while (*file_name == '/' - || !memcmp (file_name, "./", 2) - || !memcmp (file_name, "../", 3)) - file_name = strchr (file_name, '/') + 1; - return *file_name == '\0' || !strcmp (file_name, "..") ? "." : file_name; -} - -/* Composes HEADER as a USTAR_HEADER_SIZE (512)-byte archive - header in ustar format for a SIZE-byte file named FILE_NAME of - the given TYPE. The caller is responsible for writing the - header to a file or device. - - If successful, returns true. On failure (due to an - excessively long file name), returns false. */ -bool -ustar_make_header (const char *file_name, enum ustar_type type, - int size, char header[USTAR_HEADER_SIZE]) -{ - struct ustar_header *h = (struct ustar_header *) header; - - ASSERT (sizeof (struct ustar_header) == USTAR_HEADER_SIZE); - ASSERT (type == USTAR_REGULAR || type == USTAR_DIRECTORY); - - /* Check file name. */ - file_name = strip_antisocial_prefixes (file_name); - if (strlen (file_name) > 99) - { - printf ("%s: file name too long\n", file_name); - return false; - } - - /* Fill in header except for final checksum. */ - memset (h, 0, sizeof *h); - strlcpy (h->name, file_name, sizeof h->name); - snprintf (h->mode, sizeof h->mode, "%07o", - type == USTAR_REGULAR ? 0644 : 0755); - strlcpy (h->uid, "0000000", sizeof h->uid); - strlcpy (h->gid, "0000000", sizeof h->gid); - snprintf (h->size, sizeof h->size, "%011o", size); - snprintf (h->mtime, sizeof h->size, "%011o", 1136102400); - h->typeflag = type; - strlcpy (h->magic, "ustar", sizeof h->magic); - h->version[0] = h->version[1] = '0'; - strlcpy (h->gname, "root", sizeof h->gname); - strlcpy (h->uname, "root", sizeof h->uname); - - /* Compute and fill in final checksum. */ - snprintf (h->chksum, sizeof h->chksum, "%07o", calculate_chksum (h)); - - return true; -} - -/* Parses a SIZE-byte octal field in S in the format used by - ustar format. If successful, stores the field's value in - *VALUE and returns true; on failure, returns false. - - ustar octal fields consist of a sequence of octal digits - terminated by a space or a null byte. The ustar specification - seems ambiguous as to whether these fields must be padded on - the left with '0's, so we accept any field that fits in the - available space, regardless of whether it fills the space. */ -static bool -parse_octal_field (const char *s, size_t size, unsigned long int *value) -{ - size_t ofs; - - *value = 0; - for (ofs = 0; ofs < size; ofs++) - { - char c = s[ofs]; - if (c >= '0' && c <= '7') - { - if (*value > ULONG_MAX / 8) - { - /* Overflow. */ - return false; - } - *value = c - '0' + *value * 8; - } - else if (c == ' ' || c == '\0') - { - /* End of field, but disallow completely empty - fields. */ - return ofs > 0; - } - else - { - /* Bad character. */ - return false; - } - } - - /* Field did not end in space or null byte. */ - return false; -} - -/* Returns true if the CNT bytes starting at BLOCK are all zero, - false otherwise. */ -static bool -is_all_zeros (const char *block, size_t cnt) -{ - while (cnt-- > 0) - if (*block++ != 0) - return false; - return true; -} - -/* Parses HEADER as a ustar-format archive header for a regular - file or directory. If successful, stores the archived file's - name in *FILE_NAME (as a pointer into HEADER or a string - literal), its type in *TYPE, and its size in bytes in *SIZE, - and returns a null pointer. On failure, returns a - human-readable error message. */ -const char * -ustar_parse_header (const char header[USTAR_HEADER_SIZE], - const char **file_name, enum ustar_type *type, int *size) -{ - const struct ustar_header *h = (const struct ustar_header *) header; - unsigned long int chksum, size_ul; - - ASSERT (sizeof (struct ustar_header) == USTAR_HEADER_SIZE); - - /* Detect end of archive. */ - if (is_all_zeros (header, USTAR_HEADER_SIZE)) - { - *file_name = NULL; - *type = USTAR_EOF; - *size = 0; - return NULL; - } - - /* Validate ustar header. */ - if (memcmp (h->magic, "ustar", 6)) - return "not a ustar archive"; - else if (h->version[0] != '0' || h->version[1] != '0') - return "invalid ustar version"; - else if (!parse_octal_field (h->chksum, sizeof h->chksum, &chksum)) - return "corrupt chksum field"; - else if (chksum != calculate_chksum (h)) - return "checksum mismatch"; - else if (h->name[sizeof h->name - 1] != '\0' || h->prefix[0] != '\0') - return "file name too long"; - else if (h->typeflag != USTAR_REGULAR && h->typeflag != USTAR_DIRECTORY) - return "unimplemented file type"; - if (h->typeflag == USTAR_REGULAR) - { - if (!parse_octal_field (h->size, sizeof h->size, &size_ul)) - return "corrupt file size field"; - else if (size_ul > INT_MAX) - return "file too large"; - } - else - size_ul = 0; - - /* Success. */ - *file_name = strip_antisocial_prefixes (h->name); - *type = h->typeflag; - *size = size_ul; - return NULL; -} - diff --git a/pintos-progos/lib/ustar.h b/pintos-progos/lib/ustar.h deleted file mode 100644 index 43a5513..0000000 --- a/pintos-progos/lib/ustar.h +++ /dev/null @@ -1,29 +0,0 @@ -#ifndef __LIB_USTAR_H -#define __LIB_USTAR_H - -/* Support for the standard Posix "ustar" format. See the - documentation of the "pax" utility in [SUSv3] for the the - "ustar" format specification. */ - -#include - -/* Type of a file entry in an archive. - The values here are the bytes that appear in the file format. - Only types of interest to Pintos are listed here. */ -enum ustar_type - { - USTAR_REGULAR = '0', /* Ordinary file. */ - USTAR_DIRECTORY = '5', /* Directory. */ - USTAR_EOF = -1 /* End of archive (not an official value). */ - }; - -/* Size of a ustar archive header, in bytes. */ -#define USTAR_HEADER_SIZE 512 - -bool ustar_make_header (const char *file_name, enum ustar_type, - int size, char header[USTAR_HEADER_SIZE]); -const char *ustar_parse_header (const char header[USTAR_HEADER_SIZE], - const char **file_name, - enum ustar_type *, int *size); - -#endif /* lib/ustar.h */ -- cgit v1.2.3