summaryrefslogtreecommitdiffstats
path: root/pintos-progos/lib
diff options
context:
space:
mode:
Diffstat (limited to 'pintos-progos/lib')
-rw-r--r--pintos-progos/lib/arithmetic.c189
-rw-r--r--pintos-progos/lib/ctype.h28
-rw-r--r--pintos-progos/lib/debug.c32
-rw-r--r--pintos-progos/lib/debug.h39
-rw-r--r--pintos-progos/lib/inttypes.h48
-rw-r--r--pintos-progos/lib/kernel/bitmap.c371
-rw-r--r--pintos-progos/lib/kernel/bitmap.h51
-rw-r--r--pintos-progos/lib/kernel/console.c191
-rw-r--r--pintos-progos/lib/kernel/console.h8
-rw-r--r--pintos-progos/lib/kernel/debug.c123
-rw-r--r--pintos-progos/lib/kernel/hash.c430
-rw-r--r--pintos-progos/lib/kernel/hash.h103
-rw-r--r--pintos-progos/lib/kernel/list.c524
-rw-r--r--pintos-progos/lib/kernel/list.h181
-rw-r--r--pintos-progos/lib/kernel/stdio.h6
-rw-r--r--pintos-progos/lib/limits.h34
-rw-r--r--pintos-progos/lib/packed.h10
-rw-r--r--pintos-progos/lib/random.c83
-rw-r--r--pintos-progos/lib/random.h10
-rw-r--r--pintos-progos/lib/round.h18
-rw-r--r--pintos-progos/lib/stdarg.h14
-rw-r--r--pintos-progos/lib/stdbool.h9
-rw-r--r--pintos-progos/lib/stddef.h12
-rw-r--r--pintos-progos/lib/stdint.h51
-rw-r--r--pintos-progos/lib/stdio.c655
-rw-r--r--pintos-progos/lib/stdio.h40
-rw-r--r--pintos-progos/lib/stdlib.c208
-rw-r--r--pintos-progos/lib/stdlib.h22
-rw-r--r--pintos-progos/lib/string.c375
-rw-r--r--pintos-progos/lib/string.h35
-rw-r--r--pintos-progos/lib/syscall-nr.h34
-rw-r--r--pintos-progos/lib/user/console.c94
-rw-r--r--pintos-progos/lib/user/debug.c25
-rw-r--r--pintos-progos/lib/user/entry.c10
-rw-r--r--pintos-progos/lib/user/stdio.h7
-rw-r--r--pintos-progos/lib/user/syscall.c184
-rw-r--r--pintos-progos/lib/user/syscall.h48
-rw-r--r--pintos-progos/lib/user/user.lds57
-rw-r--r--pintos-progos/lib/ustar.c228
-rw-r--r--pintos-progos/lib/ustar.h29
40 files changed, 4616 insertions, 0 deletions
diff --git a/pintos-progos/lib/arithmetic.c b/pintos-progos/lib/arithmetic.c
new file mode 100644
index 0000000..bfc9b5a
--- /dev/null
+++ b/pintos-progos/lib/arithmetic.c
@@ -0,0 +1,189 @@
1#include <stdint.h>
2
3/* On x86, division of one 64-bit integer by another cannot be
4 done with a single instruction or a short sequence. Thus, GCC
5 implements 64-bit division and remainder operations through
6 function calls. These functions are normally obtained from
7 libgcc, which is automatically included by GCC in any link
8 that it does.
9
10 Some x86-64 machines, however, have a compiler and utilities
11 that can generate 32-bit x86 code without having any of the
12 necessary libraries, including libgcc. Thus, we can make
13 Pintos work on these machines by simply implementing our own
14 64-bit division routines, which are the only routines from
15 libgcc that Pintos requires.
16
17 Completeness is another reason to include these routines. If
18 Pintos is completely self-contained, then that makes it that
19 much less mysterious. */
20
21/* Uses x86 DIVL instruction to divide 64-bit N by 32-bit D to
22 yield a 32-bit quotient. Returns the quotient.
23 Traps with a divide error (#DE) if the quotient does not fit
24 in 32 bits. */
25static inline uint32_t
26divl (uint64_t n, uint32_t d)
27{
28 uint32_t n1 = n >> 32;
29 uint32_t n0 = n;
30 uint32_t q, r;
31
32 asm ("divl %4"
33 : "=d" (r), "=a" (q)
34 : "0" (n1), "1" (n0), "rm" (d));
35
36 return q;
37}
38
39/* Returns the number of leading zero bits in X,
40 which must be nonzero. */
41static int
42nlz (uint32_t x)
43{
44 /* This technique is portable, but there are better ways to do
45 it on particular systems. With sufficiently new enough GCC,
46 you can use __builtin_clz() to take advantage of GCC's
47 knowledge of how to do it. Or you can use the x86 BSR
48 instruction directly. */
49 int n = 0;
50 if (x <= 0x0000FFFF)
51 {
52 n += 16;
53 x <<= 16;
54 }
55 if (x <= 0x00FFFFFF)
56 {
57 n += 8;
58 x <<= 8;
59 }
60 if (x <= 0x0FFFFFFF)
61 {
62 n += 4;
63 x <<= 4;
64 }
65 if (x <= 0x3FFFFFFF)
66 {
67 n += 2;
68 x <<= 2;
69 }
70 if (x <= 0x7FFFFFFF)
71 n++;
72 return n;
73}
74
75/* Divides unsigned 64-bit N by unsigned 64-bit D and returns the
76 quotient. */
77static uint64_t
78udiv64 (uint64_t n, uint64_t d)
79{
80 if ((d >> 32) == 0)
81 {
82 /* Proof of correctness:
83
84 Let n, d, b, n1, and n0 be defined as in this function.
85 Let [x] be the "floor" of x. Let T = b[n1/d]. Assume d
86 nonzero. Then:
87 [n/d] = [n/d] - T + T
88 = [n/d - T] + T by (1) below
89 = [(b*n1 + n0)/d - T] + T by definition of n
90 = [(b*n1 + n0)/d - dT/d] + T
91 = [(b(n1 - d[n1/d]) + n0)/d] + T
92 = [(b[n1 % d] + n0)/d] + T, by definition of %
93 which is the expression calculated below.
94
95 (1) Note that for any real x, integer i: [x] + i = [x + i].
96
97 To prevent divl() from trapping, [(b[n1 % d] + n0)/d] must
98 be less than b. Assume that [n1 % d] and n0 take their
99 respective maximum values of d - 1 and b - 1:
100 [(b(d - 1) + (b - 1))/d] < b
101 <=> [(bd - 1)/d] < b
102 <=> [b - 1/d] < b
103 which is a tautology.
104
105 Therefore, this code is correct and will not trap. */
106 uint64_t b = 1ULL << 32;
107 uint32_t n1 = n >> 32;
108 uint32_t n0 = n;
109 uint32_t d0 = d;
110
111 return divl (b * (n1 % d0) + n0, d0) + b * (n1 / d0);
112 }
113 else
114 {
115 /* Based on the algorithm and proof available from
116 http://www.hackersdelight.org/revisions.pdf. */
117 if (n < d)
118 return 0;
119 else
120 {
121 uint32_t d1 = d >> 32;
122 int s = nlz (d1);
123 uint64_t q = divl (n >> 1, (d << s) >> 32) >> (31 - s);
124 return n - (q - 1) * d < d ? q - 1 : q;
125 }
126 }
127}
128
129/* Divides unsigned 64-bit N by unsigned 64-bit D and returns the
130 remainder. */
131static uint32_t
132umod64 (uint64_t n, uint64_t d)
133{
134 return n - d * udiv64 (n, d);
135}
136
137/* Divides signed 64-bit N by signed 64-bit D and returns the
138 quotient. */
139static int64_t
140sdiv64 (int64_t n, int64_t d)
141{
142 uint64_t n_abs = n >= 0 ? (uint64_t) n : -(uint64_t) n;
143 uint64_t d_abs = d >= 0 ? (uint64_t) d : -(uint64_t) d;
144 uint64_t q_abs = udiv64 (n_abs, d_abs);
145 return (n < 0) == (d < 0) ? (int64_t) q_abs : -(int64_t) q_abs;
146}
147
148/* Divides signed 64-bit N by signed 64-bit D and returns the
149 remainder. */
150static int32_t
151smod64 (int64_t n, int64_t d)
152{
153 return n - d * sdiv64 (n, d);
154}
155
156/* These are the routines that GCC calls. */
157
158long long __divdi3 (long long n, long long d);
159long long __moddi3 (long long n, long long d);
160unsigned long long __udivdi3 (unsigned long long n, unsigned long long d);
161unsigned long long __umoddi3 (unsigned long long n, unsigned long long d);
162
163/* Signed 64-bit division. */
164long long
165__divdi3 (long long n, long long d)
166{
167 return sdiv64 (n, d);
168}
169
170/* Signed 64-bit remainder. */
171long long
172__moddi3 (long long n, long long d)
173{
174 return smod64 (n, d);
175}
176
177/* Unsigned 64-bit division. */
178unsigned long long
179__udivdi3 (unsigned long long n, unsigned long long d)
180{
181 return udiv64 (n, d);
182}
183
184/* Unsigned 64-bit remainder. */
185unsigned long long
186__umoddi3 (unsigned long long n, unsigned long long d)
187{
188 return umod64 (n, d);
189}
diff --git a/pintos-progos/lib/ctype.h b/pintos-progos/lib/ctype.h
new file mode 100644
index 0000000..9096aca
--- /dev/null
+++ b/pintos-progos/lib/ctype.h
@@ -0,0 +1,28 @@
1#ifndef __LIB_CTYPE_H
2#define __LIB_CTYPE_H
3
4static inline int islower (int c) { return c >= 'a' && c <= 'z'; }
5static inline int isupper (int c) { return c >= 'A' && c <= 'Z'; }
6static inline int isalpha (int c) { return islower (c) || isupper (c); }
7static inline int isdigit (int c) { return c >= '0' && c <= '9'; }
8static inline int isalnum (int c) { return isalpha (c) || isdigit (c); }
9static inline int isxdigit (int c) {
10 return isdigit (c) || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F');
11}
12static inline int isspace (int c) {
13 return (c == ' ' || c == '\f' || c == '\n'
14 || c == '\r' || c == '\t' || c == '\v');
15}
16static inline int isblank (int c) { return c == ' ' || c == '\t'; }
17static inline int isgraph (int c) { return c > 32 && c < 127; }
18static inline int isprint (int c) { return c >= 32 && c < 127; }
19static inline int iscntrl (int c) { return (c >= 0 && c < 32) || c == 127; }
20static inline int isascii (int c) { return c >= 0 && c < 128; }
21static inline int ispunct (int c) {
22 return isprint (c) && !isalnum (c) && !isspace (c);
23}
24
25static inline int tolower (int c) { return isupper (c) ? c - 'A' + 'a' : c; }
26static inline int toupper (int c) { return islower (c) ? c - 'a' + 'A' : c; }
27
28#endif /* lib/ctype.h */
diff --git a/pintos-progos/lib/debug.c b/pintos-progos/lib/debug.c
new file mode 100644
index 0000000..b4f8c2d
--- /dev/null
+++ b/pintos-progos/lib/debug.c
@@ -0,0 +1,32 @@
1#include <debug.h>
2#include <stdarg.h>
3#include <stdbool.h>
4#include <stddef.h>
5#include <stdio.h>
6#include <string.h>
7
8/* Prints the call stack, that is, a list of addresses, one in
9 each of the functions we are nested within. gdb or addr2line
10 may be applied to kernel.o to translate these into file names,
11 line numbers, and function names. */
12void
13debug_backtrace (void)
14{
15 static bool explained;
16 void **frame;
17
18 printf ("Call stack: %p", __builtin_return_address (0));
19 for (frame = __builtin_frame_address (1);
20 (uintptr_t) frame >= 0x1000 && frame[0] != NULL;
21 frame = frame[0])
22 printf (" %p", frame[1]);
23 printf (".\n");
24
25 if (!explained)
26 {
27 explained = true;
28 printf ("The `backtrace' program can make call stacks useful.\n"
29 "Read \"Backtraces\" in the \"Debugging Tools\" chapter\n"
30 "of the Pintos documentation for more information.\n");
31 }
32}
diff --git a/pintos-progos/lib/debug.h b/pintos-progos/lib/debug.h
new file mode 100644
index 0000000..888ab7b
--- /dev/null
+++ b/pintos-progos/lib/debug.h
@@ -0,0 +1,39 @@
1#ifndef __LIB_DEBUG_H
2#define __LIB_DEBUG_H
3
4/* GCC lets us add "attributes" to functions, function
5 parameters, etc. to indicate their properties.
6 See the GCC manual for details. */
7#define UNUSED __attribute__ ((unused))
8#define NO_RETURN __attribute__ ((noreturn))
9#define NO_INLINE __attribute__ ((noinline))
10#define PRINTF_FORMAT(FMT, FIRST) __attribute__ ((format (printf, FMT, FIRST)))
11
12/* Halts the OS, printing the source file name, line number, and
13 function name, plus a user-specific message. */
14#define PANIC(...) debug_panic (__FILE__, __LINE__, __func__, __VA_ARGS__)
15
16void debug_panic (const char *file, int line, const char *function,
17 const char *message, ...) PRINTF_FORMAT (4, 5) NO_RETURN;
18void debug_backtrace (void);
19void debug_backtrace_all (void);
20
21#endif
22
23
24
25/* This is outside the header guard so that debug.h may be
26 included multiple times with different settings of NDEBUG. */
27#undef ASSERT
28#undef NOT_REACHED
29
30#ifndef NDEBUG
31#define ASSERT(CONDITION) \
32 if (CONDITION) { } else { \
33 PANIC ("assertion `%s' failed.", #CONDITION); \
34 }
35#define NOT_REACHED() PANIC ("executed an unreachable statement");
36#else
37#define ASSERT(CONDITION) ((void) 0)
38#define NOT_REACHED() for (;;)
39#endif /* lib/debug.h */
diff --git a/pintos-progos/lib/inttypes.h b/pintos-progos/lib/inttypes.h
new file mode 100644
index 0000000..f703725
--- /dev/null
+++ b/pintos-progos/lib/inttypes.h
@@ -0,0 +1,48 @@
1#ifndef __LIB_INTTYPES_H
2#define __LIB_INTTYPES_H
3
4#include <stdint.h>
5
6#define PRId8 "hhd"
7#define PRIi8 "hhi"
8#define PRIo8 "hho"
9#define PRIu8 "hhu"
10#define PRIx8 "hhx"
11#define PRIX8 "hhX"
12
13#define PRId16 "hd"
14#define PRIi16 "hi"
15#define PRIo16 "ho"
16#define PRIu16 "hu"
17#define PRIx16 "hx"
18#define PRIX16 "hX"
19
20#define PRId32 "d"
21#define PRIi32 "i"
22#define PRIo32 "o"
23#define PRIu32 "u"
24#define PRIx32 "x"
25#define PRIX32 "X"
26
27#define PRId64 "lld"
28#define PRIi64 "lli"
29#define PRIo64 "llo"
30#define PRIu64 "llu"
31#define PRIx64 "llx"
32#define PRIX64 "llX"
33
34#define PRIdMAX "jd"
35#define PRIiMAX "ji"
36#define PRIoMAX "jo"
37#define PRIuMAX "ju"
38#define PRIxMAX "jx"
39#define PRIXMAX "jX"
40
41#define PRIdPTR "td"
42#define PRIiPTR "ti"
43#define PRIoPTR "to"
44#define PRIuPTR "tu"
45#define PRIxPTR "tx"
46#define PRIXPTR "tX"
47
48#endif /* lib/inttypes.h */
diff --git a/pintos-progos/lib/kernel/bitmap.c b/pintos-progos/lib/kernel/bitmap.c
new file mode 100644
index 0000000..d14a98c
--- /dev/null
+++ b/pintos-progos/lib/kernel/bitmap.c
@@ -0,0 +1,371 @@
1#include "bitmap.h"
2#include <debug.h>
3#include <limits.h>
4#include <round.h>
5#include <stdio.h>
6#include "threads/malloc.h"
7#ifdef FILESYS
8#include "filesys/file.h"
9#endif
10
11/* Element type.
12
13 This must be an unsigned integer type at least as wide as int.
14
15 Each bit represents one bit in the bitmap.
16 If bit 0 in an element represents bit K in the bitmap,
17 then bit 1 in the element represents bit K+1 in the bitmap,
18 and so on. */
19typedef unsigned long elem_type;
20
21/* Number of bits in an element. */
22#define ELEM_BITS (sizeof (elem_type) * CHAR_BIT)
23
24/* From the outside, a bitmap is an array of bits. From the
25 inside, it's an array of elem_type (defined above) that
26 simulates an array of bits. */
27struct bitmap
28 {
29 size_t bit_cnt; /* Number of bits. */
30 elem_type *bits; /* Elements that represent bits. */
31 };
32
33/* Returns the index of the element that contains the bit
34 numbered BIT_IDX. */
35static inline size_t
36elem_idx (size_t bit_idx)
37{
38 return bit_idx / ELEM_BITS;
39}
40
41/* Returns an elem_type where only the bit corresponding to
42 BIT_IDX is turned on. */
43static inline elem_type
44bit_mask (size_t bit_idx)
45{
46 return (elem_type) 1 << (bit_idx % ELEM_BITS);
47}
48
49/* Returns the number of elements required for BIT_CNT bits. */
50static inline size_t
51elem_cnt (size_t bit_cnt)
52{
53 return DIV_ROUND_UP (bit_cnt, ELEM_BITS);
54}
55
56/* Returns the number of bytes required for BIT_CNT bits. */
57static inline size_t
58byte_cnt (size_t bit_cnt)
59{
60 return sizeof (elem_type) * elem_cnt (bit_cnt);
61}
62
63/* Returns a bit mask in which the bits actually used in the last
64 element of B's bits are set to 1 and the rest are set to 0. */
65static inline elem_type
66last_mask (const struct bitmap *b)
67{
68 int last_bits = b->bit_cnt % ELEM_BITS;
69 return last_bits ? ((elem_type) 1 << last_bits) - 1 : (elem_type) -1;
70}
71
72/* Creation and destruction. */
73
74/* Creates and returns a pointer to a newly allocated bitmap with room for
75 BIT_CNT (or more) bits. Returns a null pointer if memory allocation fails.
76 The caller is responsible for freeing the bitmap, with bitmap_destroy(),
77 when it is no longer needed. */
78struct bitmap *
79bitmap_create (size_t bit_cnt)
80{
81 struct bitmap *b = malloc (sizeof *b);
82 if (b != NULL)
83 {
84 b->bit_cnt = bit_cnt;
85 b->bits = malloc (byte_cnt (bit_cnt));
86 if (b->bits != NULL || bit_cnt == 0)
87 {
88 bitmap_set_all (b, false);
89 return b;
90 }
91 free (b);
92 }
93 return NULL;
94}
95
96/* Creates and returns a bitmap with BIT_CNT bits in the
97 BLOCK_SIZE bytes of storage preallocated at BLOCK.
98 BLOCK_SIZE must be at least bitmap_needed_bytes(BIT_CNT). */
99struct bitmap *
100bitmap_create_in_buf (size_t bit_cnt, void *block, size_t block_size UNUSED)
101{
102 struct bitmap *b = block;
103
104 ASSERT (block_size >= bitmap_buf_size (bit_cnt));
105
106 b->bit_cnt = bit_cnt;
107 b->bits = (elem_type *) (b + 1);
108 bitmap_set_all (b, false);
109 return b;
110}
111
112/* Returns the number of bytes required to accomodate a bitmap
113 with BIT_CNT bits (for use with bitmap_create_in_buf()). */
114size_t
115bitmap_buf_size (size_t bit_cnt)
116{
117 return sizeof (struct bitmap) + byte_cnt (bit_cnt);
118}
119
120/* Destroys bitmap B, freeing its storage.
121 Not for use on bitmaps created by bitmap_create_in_buf(). */
122void
123bitmap_destroy (struct bitmap *b)
124{
125 if (b != NULL)
126 {
127 free (b->bits);
128 free (b);
129 }
130}
131
132/* Bitmap size. */
133
134/* Returns the number of bits in B. */
135size_t
136bitmap_size (const struct bitmap *b)
137{
138 return b->bit_cnt;
139}
140
141/* Setting and testing single bits. */
142
143/* Atomically sets the bit numbered IDX in B to VALUE. */
144void
145bitmap_set (struct bitmap *b, size_t idx, bool value)
146{
147 ASSERT (b != NULL);
148 ASSERT (idx < b->bit_cnt);
149 if (value)
150 bitmap_mark (b, idx);
151 else
152 bitmap_reset (b, idx);
153}
154
155/* Atomically sets the bit numbered BIT_IDX in B to true. */
156void
157bitmap_mark (struct bitmap *b, size_t bit_idx)
158{
159 size_t idx = elem_idx (bit_idx);
160 elem_type mask = bit_mask (bit_idx);
161
162 /* This is equivalent to `b->bits[idx] |= mask' except that it
163 is guaranteed to be atomic on a uniprocessor machine. See
164 the description of the OR instruction in [IA32-v2b]. */
165 asm ("orl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
166}
167
168/* Atomically sets the bit numbered BIT_IDX in B to false. */
169void
170bitmap_reset (struct bitmap *b, size_t bit_idx)
171{
172 size_t idx = elem_idx (bit_idx);
173 elem_type mask = bit_mask (bit_idx);
174
175 /* This is equivalent to `b->bits[idx] &= ~mask' except that it
176 is guaranteed to be atomic on a uniprocessor machine. See
177 the description of the AND instruction in [IA32-v2a]. */
178 asm ("andl %1, %0" : "=m" (b->bits[idx]) : "r" (~mask) : "cc");
179}
180
181/* Atomically toggles the bit numbered IDX in B;
182 that is, if it is true, makes it false,
183 and if it is false, makes it true. */
184void
185bitmap_flip (struct bitmap *b, size_t bit_idx)
186{
187 size_t idx = elem_idx (bit_idx);
188 elem_type mask = bit_mask (bit_idx);
189
190 /* This is equivalent to `b->bits[idx] ^= mask' except that it
191 is guaranteed to be atomic on a uniprocessor machine. See
192 the description of the XOR instruction in [IA32-v2b]. */
193 asm ("xorl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
194}
195
196/* Returns the value of the bit numbered IDX in B. */
197bool
198bitmap_test (const struct bitmap *b, size_t idx)
199{
200 ASSERT (b != NULL);
201 ASSERT (idx < b->bit_cnt);
202 return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
203}
204
205/* Setting and testing multiple bits. */
206
207/* Sets all bits in B to VALUE. */
208void
209bitmap_set_all (struct bitmap *b, bool value)
210{
211 ASSERT (b != NULL);
212
213 bitmap_set_multiple (b, 0, bitmap_size (b), value);
214}
215
216/* Sets the CNT bits starting at START in B to VALUE. */
217void
218bitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value)
219{
220 size_t i;
221
222 ASSERT (b != NULL);
223 ASSERT (start <= b->bit_cnt);
224 ASSERT (start + cnt <= b->bit_cnt);
225
226 for (i = 0; i < cnt; i++)
227 bitmap_set (b, start + i, value);
228}
229
230/* Returns the number of bits in B between START and START + CNT,
231 exclusive, that are set to VALUE. */
232size_t
233bitmap_count (const struct bitmap *b, size_t start, size_t cnt, bool value)
234{
235 size_t i, value_cnt;
236
237 ASSERT (b != NULL);
238 ASSERT (start <= b->bit_cnt);
239 ASSERT (start + cnt <= b->bit_cnt);
240
241 value_cnt = 0;
242 for (i = 0; i < cnt; i++)
243 if (bitmap_test (b, start + i) == value)
244 value_cnt++;
245 return value_cnt;
246}
247
248/* Returns true if any bits in B between START and START + CNT,
249 exclusive, are set to VALUE, and false otherwise. */
250bool
251bitmap_contains (const struct bitmap *b, size_t start, size_t cnt, bool value)
252{
253 size_t i;
254
255 ASSERT (b != NULL);
256 ASSERT (start <= b->bit_cnt);
257 ASSERT (start + cnt <= b->bit_cnt);
258
259 for (i = 0; i < cnt; i++)
260 if (bitmap_test (b, start + i) == value)
261 return true;
262 return false;
263}
264
265/* Returns true if any bits in B between START and START + CNT,
266 exclusive, are set to true, and false otherwise.*/
267bool
268bitmap_any (const struct bitmap *b, size_t start, size_t cnt)
269{
270 return bitmap_contains (b, start, cnt, true);
271}
272
273/* Returns true if no bits in B between START and START + CNT,
274 exclusive, are set to true, and false otherwise.*/
275bool
276bitmap_none (const struct bitmap *b, size_t start, size_t cnt)
277{
278 return !bitmap_contains (b, start, cnt, true);
279}
280
281/* Returns true if every bit in B between START and START + CNT,
282 exclusive, is set to true, and false otherwise. */
283bool
284bitmap_all (const struct bitmap *b, size_t start, size_t cnt)
285{
286 return !bitmap_contains (b, start, cnt, false);
287}
288
289/* Finding set or unset bits. */
290
291/* Finds and returns the starting index of the first group of CNT
292 consecutive bits in B at or after START that are all set to
293 VALUE.
294 If there is no such group, returns BITMAP_ERROR. */
295size_t
296bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
297{
298 ASSERT (b != NULL);
299 ASSERT (start <= b->bit_cnt);
300
301 if (cnt <= b->bit_cnt)
302 {
303 size_t last = b->bit_cnt - cnt;
304 size_t i;
305 for (i = start; i <= last; i++)
306 if (!bitmap_contains (b, i, cnt, !value))
307 return i;
308 }
309 return BITMAP_ERROR;
310}
311
312/* Finds the first group of CNT consecutive bits in B at or after
313 START that are all set to VALUE, flips them all to !VALUE,
314 and returns the index of the first bit in the group.
315 If there is no such group, returns BITMAP_ERROR.
316 If CNT is zero, returns 0.
317 Bits are set atomically, but testing bits is not atomic with
318 setting them. */
319size_t
320bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)
321{
322 size_t idx = bitmap_scan (b, start, cnt, value);
323 if (idx != BITMAP_ERROR)
324 bitmap_set_multiple (b, idx, cnt, !value);
325 return idx;
326}
327
328/* File input and output. */
329
330#ifdef FILESYS
331/* Returns the number of bytes needed to store B in a file. */
332size_t
333bitmap_file_size (const struct bitmap *b)
334{
335 return byte_cnt (b->bit_cnt);
336}
337
338/* Reads B from FILE. Returns true if successful, false
339 otherwise. */
340bool
341bitmap_read (struct bitmap *b, struct file *file)
342{
343 bool success = true;
344 if (b->bit_cnt > 0)
345 {
346 off_t size = byte_cnt (b->bit_cnt);
347 success = file_read_at (file, b->bits, size, 0) == size;
348 b->bits[elem_cnt (b->bit_cnt) - 1] &= last_mask (b);
349 }
350 return success;
351}
352
353/* Writes B to FILE. Return true if successful, false
354 otherwise. */
355bool
356bitmap_write (const struct bitmap *b, struct file *file)
357{
358 off_t size = byte_cnt (b->bit_cnt);
359 return file_write_at (file, b->bits, size, 0) == size;
360}
361#endif /* FILESYS */
362
363/* Debugging. */
364
365/* Dumps the contents of B to the console as hexadecimal. */
366void
367bitmap_dump (const struct bitmap *b)
368{
369 hex_dump (0, b->bits, byte_cnt (b->bit_cnt), false);
370}
371
diff --git a/pintos-progos/lib/kernel/bitmap.h b/pintos-progos/lib/kernel/bitmap.h
new file mode 100644
index 0000000..a50593c
--- /dev/null
+++ b/pintos-progos/lib/kernel/bitmap.h
@@ -0,0 +1,51 @@
1#ifndef __LIB_KERNEL_BITMAP_H
2#define __LIB_KERNEL_BITMAP_H
3
4#include <stdbool.h>
5#include <stddef.h>
6#include <inttypes.h>
7
8/* Bitmap abstract data type. */
9
10/* Creation and destruction. */
11struct bitmap *bitmap_create (size_t bit_cnt);
12struct bitmap *bitmap_create_in_buf (size_t bit_cnt, void *, size_t byte_cnt);
13size_t bitmap_buf_size (size_t bit_cnt);
14void bitmap_destroy (struct bitmap *);
15
16/* Bitmap size. */
17size_t bitmap_size (const struct bitmap *);
18
19/* Setting and testing single bits. */
20void bitmap_set (struct bitmap *, size_t idx, bool);
21void bitmap_mark (struct bitmap *, size_t idx);
22void bitmap_reset (struct bitmap *, size_t idx);
23void bitmap_flip (struct bitmap *, size_t idx);
24bool bitmap_test (const struct bitmap *, size_t idx);
25
26/* Setting and testing multiple bits. */
27void bitmap_set_all (struct bitmap *, bool);
28void bitmap_set_multiple (struct bitmap *, size_t start, size_t cnt, bool);
29size_t bitmap_count (const struct bitmap *, size_t start, size_t cnt, bool);
30bool bitmap_contains (const struct bitmap *, size_t start, size_t cnt, bool);
31bool bitmap_any (const struct bitmap *, size_t start, size_t cnt);
32bool bitmap_none (const struct bitmap *, size_t start, size_t cnt);
33bool bitmap_all (const struct bitmap *, size_t start, size_t cnt);
34
35/* Finding set or unset bits. */
36#define BITMAP_ERROR SIZE_MAX
37size_t bitmap_scan (const struct bitmap *, size_t start, size_t cnt, bool);
38size_t bitmap_scan_and_flip (struct bitmap *, size_t start, size_t cnt, bool);
39
40/* File input and output. */
41#ifdef FILESYS
42struct file;
43size_t bitmap_file_size (const struct bitmap *);
44bool bitmap_read (struct bitmap *, struct file *);
45bool bitmap_write (const struct bitmap *, struct file *);
46#endif
47
48/* Debugging. */
49void bitmap_dump (const struct bitmap *);
50
51#endif /* lib/kernel/bitmap.h */
diff --git a/pintos-progos/lib/kernel/console.c b/pintos-progos/lib/kernel/console.c
new file mode 100644
index 0000000..844b184
--- /dev/null
+++ b/pintos-progos/lib/kernel/console.c
@@ -0,0 +1,191 @@
1#include <console.h>
2#include <stdarg.h>
3#include <stdio.h>
4#include "devices/serial.h"
5#include "devices/vga.h"
6#include "threads/init.h"
7#include "threads/interrupt.h"
8#include "threads/synch.h"
9
10static void vprintf_helper (char, void *);
11static void putchar_have_lock (uint8_t c);
12
13/* The console lock.
14 Both the vga and serial layers do their own locking, so it's
15 safe to call them at any time.
16 But this lock is useful to prevent simultaneous printf() calls
17 from mixing their output, which looks confusing. */
18static struct lock console_lock;
19
20/* True in ordinary circumstances: we want to use the console
21 lock to avoid mixing output between threads, as explained
22 above.
23
24 False in early boot before the point that locks are functional
25 or the console lock has been initialized, or after a kernel
26 panics. In the former case, taking the lock would cause an
27 assertion failure, which in turn would cause a panic, turning
28 it into the latter case. In the latter case, if it is a buggy
29 lock_acquire() implementation that caused the panic, we'll
30 likely just recurse. */
31static bool use_console_lock;
32
33/* It's possible, if you add enough debug output to Pintos, to
34 try to recursively grab console_lock from a single thread. As
35 a real example, I added a printf() call to palloc_free().
36 Here's a real backtrace that resulted:
37
38 lock_console()
39 vprintf()
40 printf() - palloc() tries to grab the lock again
41 palloc_free()
42 thread_schedule_tail() - another thread dying as we switch threads
43 schedule()
44 thread_yield()
45 intr_handler() - timer interrupt
46 intr_set_level()
47 serial_putc()
48 putchar_have_lock()
49 putbuf()
50 sys_write() - one process writing to the console
51 syscall_handler()
52 intr_handler()
53
54 This kind of thing is very difficult to debug, so we avoid the
55 problem by simulating a recursive lock with a depth
56 counter. */
57static int console_lock_depth;
58
59/* Number of characters written to console. */
60static int64_t write_cnt;
61
62/* Enable console locking. */
63void
64console_init (void)
65{
66 lock_init (&console_lock);
67 use_console_lock = true;
68}
69
70/* Notifies the console that a kernel panic is underway,
71 which warns it to avoid trying to take the console lock from
72 now on. */
73void
74console_panic (void)
75{
76 use_console_lock = false;
77}
78
79/* Prints console statistics. */
80void
81console_print_stats (void)
82{
83 printf ("Console: %lld characters output\n", write_cnt);
84}
85
86/* Acquires the console lock. */
87static void
88acquire_console (void)
89{
90 if (!intr_context () && use_console_lock)
91 {
92 if (lock_held_by_current_thread (&console_lock))
93 console_lock_depth++;
94 else
95 lock_acquire (&console_lock);
96 }
97}
98
99/* Releases the console lock. */
100static void
101release_console (void)
102{
103 if (!intr_context () && use_console_lock)
104 {
105 if (console_lock_depth > 0)
106 console_lock_depth--;
107 else
108 lock_release (&console_lock);
109 }
110}
111
112/* Returns true if the current thread has the console lock,
113 false otherwise. */
114static bool
115console_locked_by_current_thread (void)
116{
117 return (intr_context ()
118 || !use_console_lock
119 || lock_held_by_current_thread (&console_lock));
120}
121
122/* The standard vprintf() function,
123 which is like printf() but uses a va_list.
124 Writes its output to both vga display and serial port. */
125int
126vprintf (const char *format, va_list args)
127{
128 int char_cnt = 0;
129
130 acquire_console ();
131 __vprintf (format, args, vprintf_helper, &char_cnt);
132 release_console ();
133
134 return char_cnt;
135}
136
137/* Writes string S to the console, followed by a new-line
138 character. */
139int
140puts (const char *s)
141{
142 acquire_console ();
143 while (*s != '\0')
144 putchar_have_lock (*s++);
145 putchar_have_lock ('\n');
146 release_console ();
147
148 return 0;
149}
150
151/* Writes the N characters in BUFFER to the console. */
152void
153putbuf (const char *buffer, size_t n)
154{
155 acquire_console ();
156 while (n-- > 0)
157 putchar_have_lock (*buffer++);
158 release_console ();
159}
160
161/* Writes C to the vga display and serial port. */
162int
163putchar (int c)
164{
165 acquire_console ();
166 putchar_have_lock (c);
167 release_console ();
168
169 return c;
170}
171
172/* Helper function for vprintf(). */
173static void
174vprintf_helper (char c, void *char_cnt_)
175{
176 int *char_cnt = char_cnt_;
177 (*char_cnt)++;
178 putchar_have_lock (c);
179}
180
181/* Writes C to the vga display and serial port.
182 The caller has already acquired the console lock if
183 appropriate. */
184static void
185putchar_have_lock (uint8_t c)
186{
187 ASSERT (console_locked_by_current_thread ());
188 write_cnt++;
189 serial_putc (c);
190 vga_putc (c);
191}
diff --git a/pintos-progos/lib/kernel/console.h b/pintos-progos/lib/kernel/console.h
new file mode 100644
index 0000000..ab99249
--- /dev/null
+++ b/pintos-progos/lib/kernel/console.h
@@ -0,0 +1,8 @@
1#ifndef __LIB_KERNEL_CONSOLE_H
2#define __LIB_KERNEL_CONSOLE_H
3
4void console_init (void);
5void console_panic (void);
6void console_print_stats (void);
7
8#endif /* lib/kernel/console.h */
diff --git a/pintos-progos/lib/kernel/debug.c b/pintos-progos/lib/kernel/debug.c
new file mode 100644
index 0000000..b12f4f9
--- /dev/null
+++ b/pintos-progos/lib/kernel/debug.c
@@ -0,0 +1,123 @@
1#include <debug.h>
2#include <console.h>
3#include <stdarg.h>
4#include <stdbool.h>
5#include <stddef.h>
6#include <stdio.h>
7#include <string.h>
8#include "threads/init.h"
9#include "threads/interrupt.h"
10#include "threads/thread.h"
11#include "threads/switch.h"
12#include "threads/vaddr.h"
13#include "devices/serial.h"
14#include "devices/shutdown.h"
15
16/* Halts the OS, printing the source file name, line number, and
17 function name, plus a user-specific message. */
18void
19debug_panic (const char *file, int line, const char *function,
20 const char *message, ...)
21{
22 static int level;
23 va_list args;
24
25 intr_disable ();
26 console_panic ();
27
28 level++;
29 if (level == 1)
30 {
31 printf ("Kernel PANIC at %s:%d in %s(): ", file, line, function);
32
33 va_start (args, message);
34 vprintf (message, args);
35 printf ("\n");
36 va_end (args);
37
38 debug_backtrace ();
39 }
40 else if (level == 2)
41 printf ("Kernel PANIC recursion at %s:%d in %s().\n",
42 file, line, function);
43 else
44 {
45 /* Don't print anything: that's probably why we recursed. */
46 }
47
48 serial_flush ();
49 shutdown ();
50 for (;;);
51}
52
53/* Print call stack of a thread.
54 The thread may be running, ready, or blocked. */
55static void
56print_stacktrace(struct thread *t, void *aux UNUSED)
57{
58 void *retaddr = NULL, **frame = NULL;
59 const char *status = "UNKNOWN";
60
61 switch (t->status) {
62 case THREAD_RUNNING:
63 status = "RUNNING";
64 break;
65
66 case THREAD_READY:
67 status = "READY";
68 break;
69
70 case THREAD_BLOCKED:
71 status = "BLOCKED";
72 break;
73
74 default:
75 break;
76 }
77
78 printf ("Call stack of thread `%s' (status %s):", t->name, status);
79
80 if (t == thread_current())
81 {
82 frame = __builtin_frame_address (1);
83 retaddr = __builtin_return_address (0);
84 }
85 else
86 {
87 /* Retrieve the values of the base and instruction pointers
88 as they were saved when this thread called switch_threads. */
89 struct switch_threads_frame * saved_frame;
90
91 saved_frame = (struct switch_threads_frame *)t->stack;
92
93 /* Skip threads if they have been added to the all threads
94 list, but have never been scheduled.
95 We can identify because their `stack' member either points
96 at the top of their kernel stack page, or the
97 switch_threads_frame's 'eip' member points at switch_entry.
98 See also threads.c. */
99 if (t->stack == (uint8_t *)t + PGSIZE || saved_frame->eip == switch_entry)
100 {
101 printf (" thread was never scheduled.\n");
102 return;
103 }
104
105 frame = (void **) saved_frame->ebp;
106 retaddr = (void *) saved_frame->eip;
107 }
108
109 printf (" %p", retaddr);
110 for (; (uintptr_t) frame >= 0x1000 && frame[0] != NULL; frame = frame[0])
111 printf (" %p", frame[1]);
112 printf (".\n");
113}
114
115/* Prints call stack of all threads. */
116void
117debug_backtrace_all (void)
118{
119 enum intr_level oldlevel = intr_disable ();
120
121 thread_foreach (print_stacktrace, 0);
122 intr_set_level (oldlevel);
123}
diff --git a/pintos-progos/lib/kernel/hash.c b/pintos-progos/lib/kernel/hash.c
new file mode 100644
index 0000000..57eed45
--- /dev/null
+++ b/pintos-progos/lib/kernel/hash.c
@@ -0,0 +1,430 @@
1/* Hash table.
2
3 This data structure is thoroughly documented in the Tour of
4 Pintos for Project 3.
5
6 See hash.h for basic information. */
7
8#include "hash.h"
9#include "../debug.h"
10#include "threads/malloc.h"
11
12#define list_elem_to_hash_elem(LIST_ELEM) \
13 list_entry(LIST_ELEM, struct hash_elem, list_elem)
14
15static struct list *find_bucket (struct hash *, struct hash_elem *);
16static struct hash_elem *find_elem (struct hash *, struct list *,
17 struct hash_elem *);
18static void insert_elem (struct hash *, struct list *, struct hash_elem *);
19static void remove_elem (struct hash *, struct hash_elem *);
20static void rehash (struct hash *);
21
22/* Initializes hash table H to compute hash values using HASH and
23 compare hash elements using LESS, given auxiliary data AUX. */
24bool
25hash_init (struct hash *h,
26 hash_hash_func *hash, hash_less_func *less, void *aux)
27{
28 h->elem_cnt = 0;
29 h->bucket_cnt = 4;
30 h->buckets = malloc (sizeof *h->buckets * h->bucket_cnt);
31 h->hash = hash;
32 h->less = less;
33 h->aux = aux;
34
35 if (h->buckets != NULL)
36 {
37 hash_clear (h, NULL);
38 return true;
39 }
40 else
41 return false;
42}
43
44/* Removes all the elements from H.
45
46 If DESTRUCTOR is non-null, then it is called for each element
47 in the hash. DESTRUCTOR may, if appropriate, deallocate the
48 memory used by the hash element. However, modifying hash
49 table H while hash_clear() is running, using any of the
50 functions hash_clear(), hash_destroy(), hash_insert(),
51 hash_replace(), or hash_delete(), yields undefined behavior,
52 whether done in DESTRUCTOR or elsewhere. */
53void
54hash_clear (struct hash *h, hash_action_func *destructor)
55{
56 size_t i;
57
58 for (i = 0; i < h->bucket_cnt; i++)
59 {
60 struct list *bucket = &h->buckets[i];
61
62 if (destructor != NULL)
63 while (!list_empty (bucket))
64 {
65 struct list_elem *list_elem = list_pop_front (bucket);
66 struct hash_elem *hash_elem = list_elem_to_hash_elem (list_elem);
67 destructor (hash_elem, h->aux);
68 }
69
70 list_init (bucket);
71 }
72
73 h->elem_cnt = 0;
74}
75
76/* Destroys hash table H.
77
78 If DESTRUCTOR is non-null, then it is first called for each
79 element in the hash. DESTRUCTOR may, if appropriate,
80 deallocate the memory used by the hash element. However,
81 modifying hash table H while hash_clear() is running, using
82 any of the functions hash_clear(), hash_destroy(),
83 hash_insert(), hash_replace(), or hash_delete(), yields
84 undefined behavior, whether done in DESTRUCTOR or
85 elsewhere. */
86void
87hash_destroy (struct hash *h, hash_action_func *destructor)
88{
89 if (destructor != NULL)
90 hash_clear (h, destructor);
91 free (h->buckets);
92}
93
94/* Inserts NEW into hash table H and returns a null pointer, if
95 no equal element is already in the table.
96 If an equal element is already in the table, returns it
97 without inserting NEW. */
98struct hash_elem *
99hash_insert (struct hash *h, struct hash_elem *new)
100{
101 struct list *bucket = find_bucket (h, new);
102 struct hash_elem *old = find_elem (h, bucket, new);
103
104 if (old == NULL)
105 insert_elem (h, bucket, new);
106
107 rehash (h);
108
109 return old;
110}
111
112/* Inserts NEW into hash table H, replacing any equal element
113 already in the table, which is returned. */
114struct hash_elem *
115hash_replace (struct hash *h, struct hash_elem *new)
116{
117 struct list *bucket = find_bucket (h, new);
118 struct hash_elem *old = find_elem (h, bucket, new);
119
120 if (old != NULL)
121 remove_elem (h, old);
122 insert_elem (h, bucket, new);
123
124 rehash (h);
125
126 return old;
127}
128
129/* Finds and returns an element equal to E in hash table H, or a
130 null pointer if no equal element exists in the table. */
131struct hash_elem *
132hash_find (struct hash *h, struct hash_elem *e)
133{
134 return find_elem (h, find_bucket (h, e), e);
135}
136
137/* Finds, removes, and returns an element equal to E in hash
138 table H. Returns a null pointer if no equal element existed
139 in the table.
140
141 If the elements of the hash table are dynamically allocated,
142 or own resources that are, then it is the caller's
143 responsibility to deallocate them. */
144struct hash_elem *
145hash_delete (struct hash *h, struct hash_elem *e)
146{
147 struct hash_elem *found = find_elem (h, find_bucket (h, e), e);
148 if (found != NULL)
149 {
150 remove_elem (h, found);
151 rehash (h);
152 }
153 return found;
154}
155
156/* Calls ACTION for each element in hash table H in arbitrary
157 order.
158 Modifying hash table H while hash_apply() is running, using
159 any of the functions hash_clear(), hash_destroy(),
160 hash_insert(), hash_replace(), or hash_delete(), yields
161 undefined behavior, whether done from ACTION or elsewhere. */
162void
163hash_apply (struct hash *h, hash_action_func *action)
164{
165 size_t i;
166
167 ASSERT (action != NULL);
168
169 for (i = 0; i < h->bucket_cnt; i++)
170 {
171 struct list *bucket = &h->buckets[i];
172 struct list_elem *elem, *next;
173
174 for (elem = list_begin (bucket); elem != list_end (bucket); elem = next)
175 {
176 next = list_next (elem);
177 action (list_elem_to_hash_elem (elem), h->aux);
178 }
179 }
180}
181
182/* Initializes I for iterating hash table H.
183
184 Iteration idiom:
185
186 struct hash_iterator i;
187
188 hash_first (&i, h);
189 while (hash_next (&i))
190 {
191 struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
192 ...do something with f...
193 }
194
195 Modifying hash table H during iteration, using any of the
196 functions hash_clear(), hash_destroy(), hash_insert(),
197 hash_replace(), or hash_delete(), invalidates all
198 iterators. */
199void
200hash_first (struct hash_iterator *i, struct hash *h)
201{
202 ASSERT (i != NULL);
203 ASSERT (h != NULL);
204
205 i->hash = h;
206 i->bucket = i->hash->buckets;
207 i->elem = list_elem_to_hash_elem (list_head (i->bucket));
208}
209
210/* Advances I to the next element in the hash table and returns
211 it. Returns a null pointer if no elements are left. Elements
212 are returned in arbitrary order.
213
214 Modifying a hash table H during iteration, using any of the
215 functions hash_clear(), hash_destroy(), hash_insert(),
216 hash_replace(), or hash_delete(), invalidates all
217 iterators. */
218struct hash_elem *
219hash_next (struct hash_iterator *i)
220{
221 ASSERT (i != NULL);
222
223 i->elem = list_elem_to_hash_elem (list_next (&i->elem->list_elem));
224 while (i->elem == list_elem_to_hash_elem (list_end (i->bucket)))
225 {
226 if (++i->bucket >= i->hash->buckets + i->hash->bucket_cnt)
227 {
228 i->elem = NULL;
229 break;
230 }
231 i->elem = list_elem_to_hash_elem (list_begin (i->bucket));
232 }
233
234 return i->elem;
235}
236
237/* Returns the current element in the hash table iteration, or a
238 null pointer at the end of the table. Undefined behavior
239 after calling hash_first() but before hash_next(). */
240struct hash_elem *
241hash_cur (struct hash_iterator *i)
242{
243 return i->elem;
244}
245
246/* Returns the number of elements in H. */
247size_t
248hash_size (struct hash *h)
249{
250 return h->elem_cnt;
251}
252
253/* Returns true if H contains no elements, false otherwise. */
254bool
255hash_empty (struct hash *h)
256{
257 return h->elem_cnt == 0;
258}
259
260/* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
261#define FNV_32_PRIME 16777619u
262#define FNV_32_BASIS 2166136261u
263
264/* Returns a hash of the SIZE bytes in BUF. */
265unsigned
266hash_bytes (const void *buf_, size_t size)
267{
268 /* Fowler-Noll-Vo 32-bit hash, for bytes. */
269 const unsigned char *buf = buf_;
270 unsigned hash;
271
272 ASSERT (buf != NULL);
273
274 hash = FNV_32_BASIS;
275 while (size-- > 0)
276 hash = (hash * FNV_32_PRIME) ^ *buf++;
277
278 return hash;
279}
280
281/* Returns a hash of string S. */
282unsigned
283hash_string (const char *s_)
284{
285 const unsigned char *s = (const unsigned char *) s_;
286 unsigned hash;
287
288 ASSERT (s != NULL);
289
290 hash = FNV_32_BASIS;
291 while (*s != '\0')
292 hash = (hash * FNV_32_PRIME) ^ *s++;
293
294 return hash;
295}
296
297/* Returns a hash of integer I. */
298unsigned
299hash_int (int i)
300{
301 return hash_bytes (&i, sizeof i);
302}
303
304/* Returns the bucket in H that E belongs in. */
305static struct list *
306find_bucket (struct hash *h, struct hash_elem *e)
307{
308 size_t bucket_idx = h->hash (e, h->aux) & (h->bucket_cnt - 1);
309 return &h->buckets[bucket_idx];
310}
311
312/* Searches BUCKET in H for a hash element equal to E. Returns
313 it if found or a null pointer otherwise. */
314static struct hash_elem *
315find_elem (struct hash *h, struct list *bucket, struct hash_elem *e)
316{
317 struct list_elem *i;
318
319 for (i = list_begin (bucket); i != list_end (bucket); i = list_next (i))
320 {
321 struct hash_elem *hi = list_elem_to_hash_elem (i);
322 if (!h->less (hi, e, h->aux) && !h->less (e, hi, h->aux))
323 return hi;
324 }
325 return NULL;
326}
327
328/* Returns X with its lowest-order bit set to 1 turned off. */
329static inline size_t
330turn_off_least_1bit (size_t x)
331{
332 return x & (x - 1);
333}
334
335/* Returns true if X is a power of 2, otherwise false. */
336static inline size_t
337is_power_of_2 (size_t x)
338{
339 return x != 0 && turn_off_least_1bit (x) == 0;
340}
341
342/* Element per bucket ratios. */
343#define MIN_ELEMS_PER_BUCKET 1 /* Elems/bucket < 1: reduce # of buckets. */
344#define BEST_ELEMS_PER_BUCKET 2 /* Ideal elems/bucket. */
345#define MAX_ELEMS_PER_BUCKET 4 /* Elems/bucket > 4: increase # of buckets. */
346
347/* Changes the number of buckets in hash table H to match the
348 ideal. This function can fail because of an out-of-memory
349 condition, but that'll just make hash accesses less efficient;
350 we can still continue. */
351static void
352rehash (struct hash *h)
353{
354 size_t old_bucket_cnt, new_bucket_cnt;
355 struct list *new_buckets, *old_buckets;
356 size_t i;
357
358 ASSERT (h != NULL);
359
360 /* Save old bucket info for later use. */
361 old_buckets = h->buckets;
362 old_bucket_cnt = h->bucket_cnt;
363
364 /* Calculate the number of buckets to use now.
365 We want one bucket for about every BEST_ELEMS_PER_BUCKET.
366 We must have at least four buckets, and the number of
367 buckets must be a power of 2. */
368 new_bucket_cnt = h->elem_cnt / BEST_ELEMS_PER_BUCKET;
369 if (new_bucket_cnt < 4)
370 new_bucket_cnt = 4;
371 while (!is_power_of_2 (new_bucket_cnt))
372 new_bucket_cnt = turn_off_least_1bit (new_bucket_cnt);
373
374 /* Don't do anything if the bucket count wouldn't change. */
375 if (new_bucket_cnt == old_bucket_cnt)
376 return;
377
378 /* Allocate new buckets and initialize them as empty. */
379 new_buckets = malloc (sizeof *new_buckets * new_bucket_cnt);
380 if (new_buckets == NULL)
381 {
382 /* Allocation failed. This means that use of the hash table will
383 be less efficient. However, it is still usable, so
384 there's no reason for it to be an error. */
385 return;
386 }
387 for (i = 0; i < new_bucket_cnt; i++)
388 list_init (&new_buckets[i]);
389
390 /* Install new bucket info. */
391 h->buckets = new_buckets;
392 h->bucket_cnt = new_bucket_cnt;
393
394 /* Move each old element into the appropriate new bucket. */
395 for (i = 0; i < old_bucket_cnt; i++)
396 {
397 struct list *old_bucket;
398 struct list_elem *elem, *next;
399
400 old_bucket = &old_buckets[i];
401 for (elem = list_begin (old_bucket);
402 elem != list_end (old_bucket); elem = next)
403 {
404 struct list *new_bucket
405 = find_bucket (h, list_elem_to_hash_elem (elem));
406 next = list_next (elem);
407 list_remove (elem);
408 list_push_front (new_bucket, elem);
409 }
410 }
411
412 free (old_buckets);
413}
414
415/* Inserts E into BUCKET (in hash table H). */
416static void
417insert_elem (struct hash *h, struct list *bucket, struct hash_elem *e)
418{
419 h->elem_cnt++;
420 list_push_front (bucket, &e->list_elem);
421}
422
423/* Removes E from hash table H. */
424static void
425remove_elem (struct hash *h, struct hash_elem *e)
426{
427 h->elem_cnt--;
428 list_remove (&e->list_elem);
429}
430
diff --git a/pintos-progos/lib/kernel/hash.h b/pintos-progos/lib/kernel/hash.h
new file mode 100644
index 0000000..db9f674
--- /dev/null
+++ b/pintos-progos/lib/kernel/hash.h
@@ -0,0 +1,103 @@
1#ifndef __LIB_KERNEL_HASH_H
2#define __LIB_KERNEL_HASH_H
3
4/* Hash table.
5
6 This data structure is thoroughly documented in the Tour of
7 Pintos for Project 3.
8
9 This is a standard hash table with chaining. To locate an
10 element in the table, we compute a hash function over the
11 element's data and use that as an index into an array of
12 doubly linked lists, then linearly search the list.
13
14 The chain lists do not use dynamic allocation. Instead, each
15 structure that can potentially be in a hash must embed a
16 struct hash_elem member. All of the hash functions operate on
17 these `struct hash_elem's. The hash_entry macro allows
18 conversion from a struct hash_elem back to a structure object
19 that contains it. This is the same technique used in the
20 linked list implementation. Refer to lib/kernel/list.h for a
21 detailed explanation. */
22
23#include <stdbool.h>
24#include <stddef.h>
25#include <stdint.h>
26#include "list.h"
27
28/* Hash element. */
29struct hash_elem
30 {
31 struct list_elem list_elem;
32 };
33
34/* Converts pointer to hash element HASH_ELEM into a pointer to
35 the structure that HASH_ELEM is embedded inside. Supply the
36 name of the outer structure STRUCT and the member name MEMBER
37 of the hash element. See the big comment at the top of the
38 file for an example. */
39#define hash_entry(HASH_ELEM, STRUCT, MEMBER) \
40 ((STRUCT *) ((uint8_t *) &(HASH_ELEM)->list_elem \
41 - offsetof (STRUCT, MEMBER.list_elem)))
42
43/* Computes and returns the hash value for hash element E, given
44 auxiliary data AUX. */
45typedef unsigned hash_hash_func (const struct hash_elem *e, void *aux);
46
47/* Compares the value of two hash elements A and B, given
48 auxiliary data AUX. Returns true if A is less than B, or
49 false if A is greater than or equal to B. */
50typedef bool hash_less_func (const struct hash_elem *a,
51 const struct hash_elem *b,
52 void *aux);
53
54/* Performs some operation on hash element E, given auxiliary
55 data AUX. */
56typedef void hash_action_func (struct hash_elem *e, void *aux);
57
58/* Hash table. */
59struct hash
60 {
61 size_t elem_cnt; /* Number of elements in table. */
62 size_t bucket_cnt; /* Number of buckets, a power of 2. */
63 struct list *buckets; /* Array of `bucket_cnt' lists. */
64 hash_hash_func *hash; /* Hash function. */
65 hash_less_func *less; /* Comparison function. */
66 void *aux; /* Auxiliary data for `hash' and `less'. */
67 };
68
69/* A hash table iterator. */
70struct hash_iterator
71 {
72 struct hash *hash; /* The hash table. */
73 struct list *bucket; /* Current bucket. */
74 struct hash_elem *elem; /* Current hash element in current bucket. */
75 };
76
77/* Basic life cycle. */
78bool hash_init (struct hash *, hash_hash_func *, hash_less_func *, void *aux);
79void hash_clear (struct hash *, hash_action_func *);
80void hash_destroy (struct hash *, hash_action_func *);
81
82/* Search, insertion, deletion. */
83struct hash_elem *hash_insert (struct hash *, struct hash_elem *);
84struct hash_elem *hash_replace (struct hash *, struct hash_elem *);
85struct hash_elem *hash_find (struct hash *, struct hash_elem *);
86struct hash_elem *hash_delete (struct hash *, struct hash_elem *);
87
88/* Iteration. */
89void hash_apply (struct hash *, hash_action_func *);
90void hash_first (struct hash_iterator *, struct hash *);
91struct hash_elem *hash_next (struct hash_iterator *);
92struct hash_elem *hash_cur (struct hash_iterator *);
93
94/* Information. */
95size_t hash_size (struct hash *);
96bool hash_empty (struct hash *);
97
98/* Sample hash functions. */
99unsigned hash_bytes (const void *, size_t);
100unsigned hash_string (const char *);
101unsigned hash_int (int);
102
103#endif /* lib/kernel/hash.h */
diff --git a/pintos-progos/lib/kernel/list.c b/pintos-progos/lib/kernel/list.c
new file mode 100644
index 0000000..316d9ef
--- /dev/null
+++ b/pintos-progos/lib/kernel/list.c
@@ -0,0 +1,524 @@
1#include "list.h"
2#include "../debug.h"
3
4/* Our doubly linked lists have two header elements: the "head"
5 just before the first element and the "tail" just after the
6 last element. The `prev' link of the front header is null, as
7 is the `next' link of the back header. Their other two links
8 point toward each other via the interior elements of the list.
9
10 An empty list looks like this:
11
12 +------+ +------+
13 <---| head |<--->| tail |--->
14 +------+ +------+
15
16 A list with two elements in it looks like this:
17
18 +------+ +-------+ +-------+ +------+
19 <---| head |<--->| 1 |<--->| 2 |<--->| tail |<--->
20 +------+ +-------+ +-------+ +------+
21
22 The symmetry of this arrangement eliminates lots of special
23 cases in list processing. For example, take a look at
24 list_remove(): it takes only two pointer assignments and no
25 conditionals. That's a lot simpler than the code would be
26 without header elements.
27
28 (Because only one of the pointers in each header element is used,
29 we could in fact combine them into a single header element
30 without sacrificing this simplicity. But using two separate
31 elements allows us to do a little bit of checking on some
32 operations, which can be valuable.) */
33
34static bool is_sorted (struct list_elem *a, struct list_elem *b,
35 list_less_func *less, void *aux) UNUSED;
36
37/* Returns true if ELEM is a head, false otherwise. */
38static inline bool
39is_head (struct list_elem *elem)
40{
41 return elem != NULL && elem->prev == NULL && elem->next != NULL;
42}
43
44/* Returns true if ELEM is an interior element,
45 false otherwise. */
46static inline bool
47is_interior (struct list_elem *elem)
48{
49 return elem != NULL && elem->prev != NULL && elem->next != NULL;
50}
51
52/* Returns true if ELEM is a tail, false otherwise. */
53static inline bool
54is_tail (struct list_elem *elem)
55{
56 return elem != NULL && elem->prev != NULL && elem->next == NULL;
57}
58
59/* Initializes LIST as an empty list. */
60void
61list_init (struct list *list)
62{
63 ASSERT (list != NULL);
64 list->head.prev = NULL;
65 list->head.next = &list->tail;
66 list->tail.prev = &list->head;
67 list->tail.next = NULL;
68}
69
70/* Returns the beginning of LIST. */
71struct list_elem *
72list_begin (struct list *list)
73{
74 ASSERT (list != NULL);
75 return list->head.next;
76}
77
78/* Returns the element after ELEM in its list. If ELEM is the
79 last element in its list, returns the list tail. Results are
80 undefined if ELEM is itself a list tail. */
81struct list_elem *
82list_next (struct list_elem *elem)
83{
84 ASSERT (is_head (elem) || is_interior (elem));
85 return elem->next;
86}
87
88/* Returns LIST's tail.
89
90 list_end() is often used in iterating through a list from
91 front to back. See the big comment at the top of list.h for
92 an example. */
93struct list_elem *
94list_end (struct list *list)
95{
96 ASSERT (list != NULL);
97 return &list->tail;
98}
99
100/* Returns the LIST's reverse beginning, for iterating through
101 LIST in reverse order, from back to front. */
102struct list_elem *
103list_rbegin (struct list *list)
104{
105 ASSERT (list != NULL);
106 return list->tail.prev;
107}
108
109/* Returns the element before ELEM in its list. If ELEM is the
110 first element in its list, returns the list head. Results are
111 undefined if ELEM is itself a list head. */
112struct list_elem *
113list_prev (struct list_elem *elem)
114{
115 ASSERT (is_interior (elem) || is_tail (elem));
116 return elem->prev;
117}
118
119/* Returns LIST's head.
120
121 list_rend() is often used in iterating through a list in
122 reverse order, from back to front. Here's typical usage,
123 following the example from the top of list.h:
124
125 for (e = list_rbegin (&foo_list); e != list_rend (&foo_list);
126 e = list_prev (e))
127 {
128 struct foo *f = list_entry (e, struct foo, elem);
129 ...do something with f...
130 }
131*/
132struct list_elem *
133list_rend (struct list *list)
134{
135 ASSERT (list != NULL);
136 return &list->head;
137}
138
139/* Return's LIST's head.
140
141 list_head() can be used for an alternate style of iterating
142 through a list, e.g.:
143
144 e = list_head (&list);
145 while ((e = list_next (e)) != list_end (&list))
146 {
147 ...
148 }
149*/
150struct list_elem *
151list_head (struct list *list)
152{
153 ASSERT (list != NULL);
154 return &list->head;
155}
156
157/* Return's LIST's tail. */
158struct list_elem *
159list_tail (struct list *list)
160{
161 ASSERT (list != NULL);
162 return &list->tail;
163}
164
165/* Inserts ELEM just before BEFORE, which may be either an
166 interior element or a tail. The latter case is equivalent to
167 list_push_back(). */
168void
169list_insert (struct list_elem *before, struct list_elem *elem)
170{
171 ASSERT (is_interior (before) || is_tail (before));
172 ASSERT (elem != NULL);
173
174 elem->prev = before->prev;
175 elem->next = before;
176 before->prev->next = elem;
177 before->prev = elem;
178}
179
180/* Removes elements FIRST though LAST (exclusive) from their
181 current list, then inserts them just before BEFORE, which may
182 be either an interior element or a tail. */
183void
184list_splice (struct list_elem *before,
185 struct list_elem *first, struct list_elem *last)
186{
187 ASSERT (is_interior (before) || is_tail (before));
188 if (first == last)
189 return;
190 last = list_prev (last);
191
192 ASSERT (is_interior (first));
193 ASSERT (is_interior (last));
194
195 /* Cleanly remove FIRST...LAST from its current list. */
196 first->prev->next = last->next;
197 last->next->prev = first->prev;
198
199 /* Splice FIRST...LAST into new list. */
200 first->prev = before->prev;
201 last->next = before;
202 before->prev->next = first;
203 before->prev = last;
204}
205
206/* Inserts ELEM at the beginning of LIST, so that it becomes the
207 front in LIST. */
208void
209list_push_front (struct list *list, struct list_elem *elem)
210{
211 list_insert (list_begin (list), elem);
212}
213
214/* Inserts ELEM at the end of LIST, so that it becomes the
215 back in LIST. */
216void
217list_push_back (struct list *list, struct list_elem *elem)
218{
219 list_insert (list_end (list), elem);
220}
221
222/* Removes ELEM from its list and returns the element that
223 followed it. Undefined behavior if ELEM is not in a list.
224
225 A list element must be treated very carefully after removing
226 it from its list. Calling list_next() or list_prev() on ELEM
227 will return the item that was previously before or after ELEM,
228 but, e.g., list_prev(list_next(ELEM)) is no longer ELEM!
229
230 The list_remove() return value provides a convenient way to
231 iterate and remove elements from a list:
232
233 for (e = list_begin (&list); e != list_end (&list); e = list_remove (e))
234 {
235 ...do something with e...
236 }
237
238 If you need to free() elements of the list then you need to be
239 more conservative. Here's an alternate strategy that works
240 even in that case:
241
242 while (!list_empty (&list))
243 {
244 struct list_elem *e = list_pop_front (&list);
245 ...do something with e...
246 }
247*/
248struct list_elem *
249list_remove (struct list_elem *elem)
250{
251 ASSERT (is_interior (elem));
252 elem->prev->next = elem->next;
253 elem->next->prev = elem->prev;
254 return elem->next;
255}
256
257/* Removes the front element from LIST and returns it.
258 Undefined behavior if LIST is empty before removal. */
259struct list_elem *
260list_pop_front (struct list *list)
261{
262 struct list_elem *front = list_front (list);
263 list_remove (front);
264 return front;
265}
266
267/* Removes the back element from LIST and returns it.
268 Undefined behavior if LIST is empty before removal. */
269struct list_elem *
270list_pop_back (struct list *list)
271{
272 struct list_elem *back = list_back (list);
273 list_remove (back);
274 return back;
275}
276
277/* Returns the front element in LIST.
278 Undefined behavior if LIST is empty. */
279struct list_elem *
280list_front (struct list *list)
281{
282 ASSERT (!list_empty (list));
283 return list->head.next;
284}
285
286/* Returns the back element in LIST.
287 Undefined behavior if LIST is empty. */
288struct list_elem *
289list_back (struct list *list)
290{
291 ASSERT (!list_empty (list));
292 return list->tail.prev;
293}
294
295/* Returns the number of elements in LIST.
296 Runs in O(n) in the number of elements. */
297size_t
298list_size (struct list *list)
299{
300 struct list_elem *e;
301 size_t cnt = 0;
302
303 for (e = list_begin (list); e != list_end (list); e = list_next (e))
304 cnt++;
305 return cnt;
306}
307
308/* Returns true if LIST is empty, false otherwise. */
309bool
310list_empty (struct list *list)
311{
312 return list_begin (list) == list_end (list);
313}
314
315/* Swaps the `struct list_elem *'s that A and B point to. */
316static void
317swap (struct list_elem **a, struct list_elem **b)
318{
319 struct list_elem *t = *a;
320 *a = *b;
321 *b = t;
322}
323
324/* Reverses the order of LIST. */
325void
326list_reverse (struct list *list)
327{
328 if (!list_empty (list))
329 {
330 struct list_elem *e;
331
332 for (e = list_begin (list); e != list_end (list); e = e->prev)
333 swap (&e->prev, &e->next);
334 swap (&list->head.next, &list->tail.prev);
335 swap (&list->head.next->prev, &list->tail.prev->next);
336 }
337}
338
339/* Returns true only if the list elements A through B (exclusive)
340 are in order according to LESS given auxiliary data AUX. */
341static bool
342is_sorted (struct list_elem *a, struct list_elem *b,
343 list_less_func *less, void *aux)
344{
345 if (a != b)
346 while ((a = list_next (a)) != b)
347 if (less (a, list_prev (a), aux))
348 return false;
349 return true;
350}
351
352/* Finds a run, starting at A and ending not after B, of list
353 elements that are in nondecreasing order according to LESS
354 given auxiliary data AUX. Returns the (exclusive) end of the
355 run.
356 A through B (exclusive) must form a non-empty range. */
357static struct list_elem *
358find_end_of_run (struct list_elem *a, struct list_elem *b,
359 list_less_func *less, void *aux)
360{
361 ASSERT (a != NULL);
362 ASSERT (b != NULL);
363 ASSERT (less != NULL);
364 ASSERT (a != b);
365
366 do
367 {
368 a = list_next (a);
369 }
370 while (a != b && !less (a, list_prev (a), aux));
371 return a;
372}
373
374/* Merges A0 through A1B0 (exclusive) with A1B0 through B1
375 (exclusive) to form a combined range also ending at B1
376 (exclusive). Both input ranges must be nonempty and sorted in
377 nondecreasing order according to LESS given auxiliary data
378 AUX. The output range will be sorted the same way. */
379static void
380inplace_merge (struct list_elem *a0, struct list_elem *a1b0,
381 struct list_elem *b1,
382 list_less_func *less, void *aux)
383{
384 ASSERT (a0 != NULL);
385 ASSERT (a1b0 != NULL);
386 ASSERT (b1 != NULL);
387 ASSERT (less != NULL);
388 ASSERT (is_sorted (a0, a1b0, less, aux));
389 ASSERT (is_sorted (a1b0, b1, less, aux));
390
391 while (a0 != a1b0 && a1b0 != b1)
392 if (!less (a1b0, a0, aux))
393 a0 = list_next (a0);
394 else
395 {
396 a1b0 = list_next (a1b0);
397 list_splice (a0, list_prev (a1b0), a1b0);
398 }
399}
400
401/* Sorts LIST according to LESS given auxiliary data AUX, using a
402 natural iterative merge sort that runs in O(n lg n) time and
403 O(1) space in the number of elements in LIST. */
404void
405list_sort (struct list *list, list_less_func *less, void *aux)
406{
407 size_t output_run_cnt; /* Number of runs output in current pass. */
408
409 ASSERT (list != NULL);
410 ASSERT (less != NULL);
411
412 /* Pass over the list repeatedly, merging adjacent runs of
413 nondecreasing elements, until only one run is left. */
414 do
415 {
416 struct list_elem *a0; /* Start of first run. */
417 struct list_elem *a1b0; /* End of first run, start of second. */
418 struct list_elem *b1; /* End of second run. */
419
420 output_run_cnt = 0;
421 for (a0 = list_begin (list); a0 != list_end (list); a0 = b1)
422 {
423 /* Each iteration produces one output run. */
424 output_run_cnt++;
425
426 /* Locate two adjacent runs of nondecreasing elements
427 A0...A1B0 and A1B0...B1. */
428 a1b0 = find_end_of_run (a0, list_end (list), less, aux);
429 if (a1b0 == list_end (list))
430 break;
431 b1 = find_end_of_run (a1b0, list_end (list), less, aux);
432
433 /* Merge the runs. */
434 inplace_merge (a0, a1b0, b1, less, aux);
435 }
436 }
437 while (output_run_cnt > 1);
438
439 ASSERT (is_sorted (list_begin (list), list_end (list), less, aux));
440}
441
442/* Inserts ELEM in the proper position in LIST, which must be
443 sorted according to LESS given auxiliary data AUX.
444 Runs in O(n) average case in the number of elements in LIST. */
445void
446list_insert_ordered (struct list *list, struct list_elem *elem,
447 list_less_func *less, void *aux)
448{
449 struct list_elem *e;
450
451 ASSERT (list != NULL);
452 ASSERT (elem != NULL);
453 ASSERT (less != NULL);
454
455 for (e = list_begin (list); e != list_end (list); e = list_next (e))
456 if (less (elem, e, aux))
457 break;
458 return list_insert (e, elem);
459}
460
461/* Iterates through LIST and removes all but the first in each
462 set of adjacent elements that are equal according to LESS
463 given auxiliary data AUX. If DUPLICATES is non-null, then the
464 elements from LIST are appended to DUPLICATES. */
465void
466list_unique (struct list *list, struct list *duplicates,
467 list_less_func *less, void *aux)
468{
469 struct list_elem *elem, *next;
470
471 ASSERT (list != NULL);
472 ASSERT (less != NULL);
473 if (list_empty (list))
474 return;
475
476 elem = list_begin (list);
477 while ((next = list_next (elem)) != list_end (list))
478 if (!less (elem, next, aux) && !less (next, elem, aux))
479 {
480 list_remove (next);
481 if (duplicates != NULL)
482 list_push_back (duplicates, next);
483 }
484 else
485 elem = next;
486}
487
488/* Returns the element in LIST with the largest value according
489 to LESS given auxiliary data AUX. If there is more than one
490 maximum, returns the one that appears earlier in the list. If
491 the list is empty, returns its tail. */
492struct list_elem *
493list_max (struct list *list, list_less_func *less, void *aux)
494{
495 struct list_elem *max = list_begin (list);
496 if (max != list_end (list))
497 {
498 struct list_elem *e;
499
500 for (e = list_next (max); e != list_end (list); e = list_next (e))
501 if (less (max, e, aux))
502 max = e;
503 }
504 return max;
505}
506
507/* Returns the element in LIST with the smallest value according
508 to LESS given auxiliary data AUX. If there is more than one
509 minimum, returns the one that appears earlier in the list. If
510 the list is empty, returns its tail. */
511struct list_elem *
512list_min (struct list *list, list_less_func *less, void *aux)
513{
514 struct list_elem *min = list_begin (list);
515 if (min != list_end (list))
516 {
517 struct list_elem *e;
518
519 for (e = list_next (min); e != list_end (list); e = list_next (e))
520 if (less (e, min, aux))
521 min = e;
522 }
523 return min;
524}
diff --git a/pintos-progos/lib/kernel/list.h b/pintos-progos/lib/kernel/list.h
new file mode 100644
index 0000000..82efbb5
--- /dev/null
+++ b/pintos-progos/lib/kernel/list.h
@@ -0,0 +1,181 @@
1#ifndef __LIB_KERNEL_LIST_H
2#define __LIB_KERNEL_LIST_H
3
4/* Doubly linked list.
5
6 This implementation of a doubly linked list does not require
7 use of dynamically allocated memory. Instead, each structure
8 that is a potential list element must embed a struct list_elem
9 member. All of the list functions operate on these `struct
10 list_elem's. The list_entry macro allows conversion from a
11 struct list_elem back to a structure object that contains it.
12
13 For example, suppose there is a needed for a list of `struct
14 foo'. `struct foo' should contain a `struct list_elem'
15 member, like so:
16
17 struct foo
18 {
19 struct list_elem elem;
20 int bar;
21 ...other members...
22 };
23
24 Then a list of `struct foo' can be be declared and initialized
25 like so:
26
27 struct list foo_list;
28
29 list_init (&foo_list);
30
31 Iteration is a typical situation where it is necessary to
32 convert from a struct list_elem back to its enclosing
33 structure. Here's an example using foo_list:
34
35 struct list_elem *e;
36
37 for (e = list_begin (&foo_list); e != list_end (&foo_list);
38 e = list_next (e))
39 {
40 struct foo *f = list_entry (e, struct foo, elem);
41 ...do something with f...
42 }
43
44 You can find real examples of list usage throughout the
45 source; for example, malloc.c, palloc.c, and thread.c in the
46 threads directory all use lists.
47
48 The interface for this list is inspired by the list<> template
49 in the C++ STL. If you're familiar with list<>, you should
50 find this easy to use. However, it should be emphasized that
51 these lists do *no* type checking and can't do much other
52 correctness checking. If you screw up, it will bite you.
53
54 Glossary of list terms:
55
56 - "front": The first element in a list. Undefined in an
57 empty list. Returned by list_front().
58
59 - "back": The last element in a list. Undefined in an empty
60 list. Returned by list_back().
61
62 - "tail": The element figuratively just after the last
63 element of a list. Well defined even in an empty list.
64 Returned by list_end(). Used as the end sentinel for an
65 iteration from front to back.
66
67 - "beginning": In a non-empty list, the front. In an empty
68 list, the tail. Returned by list_begin(). Used as the
69 starting point for an iteration from front to back.
70
71 - "head": The element figuratively just before the first
72 element of a list. Well defined even in an empty list.
73 Returned by list_rend(). Used as the end sentinel for an
74 iteration from back to front.
75
76 - "reverse beginning": In a non-empty list, the back. In an
77 empty list, the head. Returned by list_rbegin(). Used as
78 the starting point for an iteration from back to front.
79
80 - "interior element": An element that is not the head or
81 tail, that is, a real list element. An empty list does
82 not have any interior elements.
83*/
84
85#include <stdbool.h>
86#include <stddef.h>
87#include <stdint.h>
88
89/* List element. */
90struct list_elem
91 {
92 struct list_elem *prev; /* Previous list element. */
93 struct list_elem *next; /* Next list element. */
94 };
95
96/* List. */
97struct list
98 {
99 struct list_elem head; /* List head. */
100 struct list_elem tail; /* List tail. */
101 };
102
103/* Converts pointer to list element LIST_ELEM into a pointer to
104 the structure that LIST_ELEM is embedded inside. Supply the
105 name of the outer structure STRUCT and the member name MEMBER
106 of the list element. See the big comment at the top of the
107 file for an example. */
108#define list_entry(LIST_ELEM, STRUCT, MEMBER) \
109 ((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next \
110 - offsetof (STRUCT, MEMBER.next)))
111
112/* List initialization.
113
114 A list may be initialized by calling list_init():
115
116 struct list my_list;
117 list_init (&my_list);
118
119 or with an initializer using LIST_INITIALIZER:
120
121 struct list my_list = LIST_INITIALIZER (my_list); */
122#define LIST_INITIALIZER(NAME) { { NULL, &(NAME).tail }, \
123 { &(NAME).head, NULL } }
124
125void list_init (struct list *);
126
127/* List traversal. */
128struct list_elem *list_begin (struct list *);
129struct list_elem *list_next (struct list_elem *);
130struct list_elem *list_end (struct list *);
131
132struct list_elem *list_rbegin (struct list *);
133struct list_elem *list_prev (struct list_elem *);
134struct list_elem *list_rend (struct list *);
135
136struct list_elem *list_head (struct list *);
137struct list_elem *list_tail (struct list *);
138
139/* List insertion. */
140void list_insert (struct list_elem *, struct list_elem *);
141void list_splice (struct list_elem *before,
142 struct list_elem *first, struct list_elem *last);
143void list_push_front (struct list *, struct list_elem *);
144void list_push_back (struct list *, struct list_elem *);
145
146/* List removal. */
147struct list_elem *list_remove (struct list_elem *);
148struct list_elem *list_pop_front (struct list *);
149struct list_elem *list_pop_back (struct list *);
150
151/* List elements. */
152struct list_elem *list_front (struct list *);
153struct list_elem *list_back (struct list *);
154
155/* List properties. */
156size_t list_size (struct list *);
157bool list_empty (struct list *);
158
159/* Miscellaneous. */
160void list_reverse (struct list *);
161
162/* Compares the value of two list elements A and B, given
163 auxiliary data AUX. Returns true if A is less than B, or
164 false if A is greater than or equal to B. */
165typedef bool list_less_func (const struct list_elem *a,
166 const struct list_elem *b,
167 void *aux);
168
169/* Operations on lists with ordered elements. */
170void list_sort (struct list *,
171 list_less_func *, void *aux);
172void list_insert_ordered (struct list *, struct list_elem *,
173 list_less_func *, void *aux);
174void list_unique (struct list *, struct list *duplicates,
175 list_less_func *, void *aux);
176
177/* Max and min. */
178struct list_elem *list_max (struct list *, list_less_func *, void *aux);
179struct list_elem *list_min (struct list *, list_less_func *, void *aux);
180
181#endif /* lib/kernel/list.h */
diff --git a/pintos-progos/lib/kernel/stdio.h b/pintos-progos/lib/kernel/stdio.h
new file mode 100644
index 0000000..3e5bae9
--- /dev/null
+++ b/pintos-progos/lib/kernel/stdio.h
@@ -0,0 +1,6 @@
1#ifndef __LIB_KERNEL_STDIO_H
2#define __LIB_KERNEL_STDIO_H
3
4void putbuf (const char *, size_t);
5
6#endif /* lib/kernel/stdio.h */
diff --git a/pintos-progos/lib/limits.h b/pintos-progos/lib/limits.h
new file mode 100644
index 0000000..c957ec4
--- /dev/null
+++ b/pintos-progos/lib/limits.h
@@ -0,0 +1,34 @@
1#ifndef __LIB_LIMITS_H
2#define __LIB_LIMITS_H
3
4#define CHAR_BIT 8
5
6#define SCHAR_MAX 127
7#define SCHAR_MIN (-SCHAR_MAX - 1)
8#define UCHAR_MAX 255
9
10#ifdef __CHAR_UNSIGNED__
11#define CHAR_MIN 0
12#define CHAR_MAX UCHAR_MAX
13#else
14#define CHAR_MIN SCHAR_MIN
15#define CHAR_MAX SCHAR_MAX
16#endif
17
18#define SHRT_MAX 32767
19#define SHRT_MIN (-SHRT_MAX - 1)
20#define USHRT_MAX 65535
21
22#define INT_MAX 2147483647
23#define INT_MIN (-INT_MAX - 1)
24#define UINT_MAX 4294967295U
25
26#define LONG_MAX 2147483647L
27#define LONG_MIN (-LONG_MAX - 1)
28#define ULONG_MAX 4294967295UL
29
30#define LLONG_MAX 9223372036854775807LL
31#define LLONG_MIN (-LLONG_MAX - 1)
32#define ULLONG_MAX 18446744073709551615ULL
33
34#endif /* lib/limits.h */
diff --git a/pintos-progos/lib/packed.h b/pintos-progos/lib/packed.h
new file mode 100644
index 0000000..9a9b6e2
--- /dev/null
+++ b/pintos-progos/lib/packed.h
@@ -0,0 +1,10 @@
1#ifndef __LIB_PACKED_H
2#define __LIB_PACKED_H
3
4/* The "packed" attribute, when applied to a structure, prevents
5 GCC from inserting padding bytes between or after structure
6 members. It must be specified at the time of the structure's
7 definition, normally just after the closing brace. */
8#define PACKED __attribute__ ((packed))
9
10#endif /* lib/packed.h */
diff --git a/pintos-progos/lib/random.c b/pintos-progos/lib/random.c
new file mode 100644
index 0000000..a4761b6
--- /dev/null
+++ b/pintos-progos/lib/random.c
@@ -0,0 +1,83 @@
1#include "random.h"
2#include <stdbool.h>
3#include <stdint.h>
4#include "debug.h"
5
6/* RC4-based pseudo-random number generator (PRNG).
7
8 RC4 is a stream cipher. We're not using it here for its
9 cryptographic properties, but because it is easy to implement
10 and its output is plenty random for non-cryptographic
11 purposes.
12
13 See http://en.wikipedia.org/wiki/RC4_(cipher) for information
14 on RC4.*/
15
16/* RC4 state. */
17static uint8_t s[256]; /* S[]. */
18static uint8_t s_i, s_j; /* i, j. */
19
20/* Already initialized? */
21static bool inited;
22
23/* Swaps the bytes pointed to by A and B. */
24static inline void
25swap_byte (uint8_t *a, uint8_t *b)
26{
27 uint8_t t = *a;
28 *a = *b;
29 *b = t;
30}
31
32/* Initializes or reinitializes the PRNG with the given SEED. */
33void
34random_init (unsigned seed)
35{
36 uint8_t *seedp = (uint8_t *) &seed;
37 int i;
38 uint8_t j;
39
40 for (i = 0; i < 256; i++)
41 s[i] = i;
42 for (i = j = 0; i < 256; i++)
43 {
44 j += s[i] + seedp[i % sizeof seed];
45 swap_byte (s + i, s + j);
46 }
47
48 s_i = s_j = 0;
49 inited = true;
50}
51
52/* Writes SIZE random bytes into BUF. */
53void
54random_bytes (void *buf_, size_t size)
55{
56 uint8_t *buf;
57
58 if (!inited)
59 random_init (0);
60
61 for (buf = buf_; size-- > 0; buf++)
62 {
63 uint8_t s_k;
64
65 s_i++;
66 s_j += s[s_i];
67 swap_byte (s + s_i, s + s_j);
68
69 s_k = s[s_i] + s[s_j];
70 *buf = s[s_k];
71 }
72}
73
74/* Returns a pseudo-random unsigned long.
75 Use random_ulong() % n to obtain a random number in the range
76 0...n (exclusive). */
77unsigned long
78random_ulong (void)
79{
80 unsigned long ul;
81 random_bytes (&ul, sizeof ul);
82 return ul;
83}
diff --git a/pintos-progos/lib/random.h b/pintos-progos/lib/random.h
new file mode 100644
index 0000000..0950ae2
--- /dev/null
+++ b/pintos-progos/lib/random.h
@@ -0,0 +1,10 @@
1#ifndef __LIB_RANDOM_H
2#define __LIB_RANDOM_H
3
4#include <stddef.h>
5
6void random_init (unsigned seed);
7void random_bytes (void *, size_t);
8unsigned long random_ulong (void);
9
10#endif /* lib/random.h */
diff --git a/pintos-progos/lib/round.h b/pintos-progos/lib/round.h
new file mode 100644
index 0000000..3aa6642
--- /dev/null
+++ b/pintos-progos/lib/round.h
@@ -0,0 +1,18 @@
1#ifndef __LIB_ROUND_H
2#define __LIB_ROUND_H
3
4/* Yields X rounded up to the nearest multiple of STEP.
5 For X >= 0, STEP >= 1 only. */
6#define ROUND_UP(X, STEP) (((X) + (STEP) - 1) / (STEP) * (STEP))
7
8/* Yields X divided by STEP, rounded up.
9 For X >= 0, STEP >= 1 only. */
10#define DIV_ROUND_UP(X, STEP) (((X) + (STEP) - 1) / (STEP))
11
12/* Yields X rounded down to the nearest multiple of STEP.
13 For X >= 0, STEP >= 1 only. */
14#define ROUND_DOWN(X, STEP) ((X) / (STEP) * (STEP))
15
16/* There is no DIV_ROUND_DOWN. It would be simply X / STEP. */
17
18#endif /* lib/round.h */
diff --git a/pintos-progos/lib/stdarg.h b/pintos-progos/lib/stdarg.h
new file mode 100644
index 0000000..32622b5
--- /dev/null
+++ b/pintos-progos/lib/stdarg.h
@@ -0,0 +1,14 @@
1#ifndef __LIB_STDARG_H
2#define __LIB_STDARG_H
3
4/* GCC has <stdarg.h> functionality as built-ins,
5 so all we need is to use it. */
6
7typedef __builtin_va_list va_list;
8
9#define va_start(LIST, ARG) __builtin_va_start (LIST, ARG)
10#define va_end(LIST) __builtin_va_end (LIST)
11#define va_arg(LIST, TYPE) __builtin_va_arg (LIST, TYPE)
12#define va_copy(DST, SRC) __builtin_va_copy (DST, SRC)
13
14#endif /* lib/stdarg.h */
diff --git a/pintos-progos/lib/stdbool.h b/pintos-progos/lib/stdbool.h
new file mode 100644
index 0000000..f173a91
--- /dev/null
+++ b/pintos-progos/lib/stdbool.h
@@ -0,0 +1,9 @@
1#ifndef __LIB_STDBOOL_H
2#define __LIB_STDBOOL_H
3
4#define bool _Bool
5#define true 1
6#define false 0
7#define __bool_true_false_are_defined 1
8
9#endif /* lib/stdbool.h */
diff --git a/pintos-progos/lib/stddef.h b/pintos-progos/lib/stddef.h
new file mode 100644
index 0000000..4e74fa6
--- /dev/null
+++ b/pintos-progos/lib/stddef.h
@@ -0,0 +1,12 @@
1#ifndef __LIB_STDDEF_H
2#define __LIB_STDDEF_H
3
4#define NULL ((void *) 0)
5#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *) 0)->MEMBER)
6
7/* GCC predefines the types we need for ptrdiff_t and size_t,
8 so that we don't have to guess. */
9typedef __PTRDIFF_TYPE__ ptrdiff_t;
10typedef __SIZE_TYPE__ size_t;
11
12#endif /* lib/stddef.h */
diff --git a/pintos-progos/lib/stdint.h b/pintos-progos/lib/stdint.h
new file mode 100644
index 0000000..ef5f214
--- /dev/null
+++ b/pintos-progos/lib/stdint.h
@@ -0,0 +1,51 @@
1#ifndef __LIB_STDINT_H
2#define __LIB_STDINT_H
3
4typedef signed char int8_t;
5#define INT8_MAX 127
6#define INT8_MIN (-INT8_MAX - 1)
7
8typedef signed short int int16_t;
9#define INT16_MAX 32767
10#define INT16_MIN (-INT16_MAX - 1)
11
12typedef signed int int32_t;
13#define INT32_MAX 2147483647
14#define INT32_MIN (-INT32_MAX - 1)
15
16typedef signed long long int int64_t;
17#define INT64_MAX 9223372036854775807LL
18#define INT64_MIN (-INT64_MAX - 1)
19
20typedef unsigned char uint8_t;
21#define UINT8_MAX 255
22
23typedef unsigned short int uint16_t;
24#define UINT16_MAX 65535
25
26typedef unsigned int uint32_t;
27#define UINT32_MAX 4294967295U
28
29typedef unsigned long long int uint64_t;
30#define UINT64_MAX 18446744073709551615ULL
31
32typedef int32_t intptr_t;
33#define INTPTR_MIN INT32_MIN
34#define INTPTR_MAX INT32_MAX
35
36typedef uint32_t uintptr_t;
37#define UINTPTR_MAX UINT32_MAX
38
39typedef int64_t intmax_t;
40#define INTMAX_MIN INT64_MIN
41#define INTMAX_MAX INT64_MAX
42
43typedef uint64_t uintmax_t;
44#define UINTMAX_MAX UINT64_MAX
45
46#define PTRDIFF_MIN INT32_MIN
47#define PTRDIFF_MAX INT32_MAX
48
49#define SIZE_MAX UINT32_MAX
50
51#endif /* lib/stdint.h */
diff --git a/pintos-progos/lib/stdio.c b/pintos-progos/lib/stdio.c
new file mode 100644
index 0000000..8927c50
--- /dev/null
+++ b/pintos-progos/lib/stdio.c
@@ -0,0 +1,655 @@
1#include <stdio.h>
2#include <ctype.h>
3#include <inttypes.h>
4#include <round.h>
5#include <stdint.h>
6#include <string.h>
7
8/* Auxiliary data for vsnprintf_helper(). */
9struct vsnprintf_aux
10 {
11 char *p; /* Current output position. */
12 int length; /* Length of output string. */
13 int max_length; /* Max length of output string. */
14 };
15
16static void vsnprintf_helper (char, void *);
17
18/* Like vprintf(), except that output is stored into BUFFER,
19 which must have space for BUF_SIZE characters. Writes at most
20 BUF_SIZE - 1 characters to BUFFER, followed by a null
21 terminator. BUFFER will always be null-terminated unless
22 BUF_SIZE is zero. Returns the number of characters that would
23 have been written to BUFFER, not including a null terminator,
24 had there been enough room. */
25int
26vsnprintf (char *buffer, size_t buf_size, const char *format, va_list args)
27{
28 /* Set up aux data for vsnprintf_helper(). */
29 struct vsnprintf_aux aux;
30 aux.p = buffer;
31 aux.length = 0;
32 aux.max_length = buf_size > 0 ? buf_size - 1 : 0;
33
34 /* Do most of the work. */
35 __vprintf (format, args, vsnprintf_helper, &aux);
36
37 /* Add null terminator. */
38 if (buf_size > 0)
39 *aux.p = '\0';
40
41 return aux.length;
42}
43
44/* Helper function for vsnprintf(). */
45static void
46vsnprintf_helper (char ch, void *aux_)
47{
48 struct vsnprintf_aux *aux = aux_;
49
50 if (aux->length++ < aux->max_length)
51 *aux->p++ = ch;
52}
53
54/* Like printf(), except that output is stored into BUFFER,
55 which must have space for BUF_SIZE characters. Writes at most
56 BUF_SIZE - 1 characters to BUFFER, followed by a null
57 terminator. BUFFER will always be null-terminated unless
58 BUF_SIZE is zero. Returns the number of characters that would
59 have been written to BUFFER, not including a null terminator,
60 had there been enough room. */
61int
62snprintf (char *buffer, size_t buf_size, const char *format, ...)
63{
64 va_list args;
65 int retval;
66
67 va_start (args, format);
68 retval = vsnprintf (buffer, buf_size, format, args);
69 va_end (args);
70
71 return retval;
72}
73
74/* Writes formatted output to the console.
75 In the kernel, the console is both the video display and first
76 serial port.
77 In userspace, the console is file descriptor 1. */
78int
79printf (const char *format, ...)
80{
81 va_list args;
82 int retval;
83
84 va_start (args, format);
85 retval = vprintf (format, args);
86 va_end (args);
87
88 return retval;
89}
90
91/* printf() formatting internals. */
92
93/* A printf() conversion. */
94struct printf_conversion
95 {
96 /* Flags. */
97 enum
98 {
99 MINUS = 1 << 0, /* '-' */
100 PLUS = 1 << 1, /* '+' */
101 SPACE = 1 << 2, /* ' ' */
102 POUND = 1 << 3, /* '#' */
103 ZERO = 1 << 4, /* '0' */
104 GROUP = 1 << 5 /* '\'' */
105 }
106 flags;
107
108 /* Minimum field width. */
109 int width;
110
111 /* Numeric precision.
112 -1 indicates no precision was specified. */
113 int precision;
114
115 /* Type of argument to format. */
116 enum
117 {
118 CHAR = 1, /* hh */
119 SHORT = 2, /* h */
120 INT = 3, /* (none) */
121 INTMAX = 4, /* j */
122 LONG = 5, /* l */
123 LONGLONG = 6, /* ll */
124 PTRDIFFT = 7, /* t */
125 SIZET = 8 /* z */
126 }
127 type;
128 };
129
130struct integer_base
131 {
132 int base; /* Base. */
133 const char *digits; /* Collection of digits. */
134 int x; /* `x' character to use, for base 16 only. */
135 int group; /* Number of digits to group with ' flag. */
136 };
137
138static const struct integer_base base_d = {10, "0123456789", 0, 3};
139static const struct integer_base base_o = {8, "01234567", 0, 3};
140static const struct integer_base base_x = {16, "0123456789abcdef", 'x', 4};
141static const struct integer_base base_X = {16, "0123456789ABCDEF", 'X', 4};
142
143static const char *parse_conversion (const char *format,
144 struct printf_conversion *,
145 va_list *);
146static void format_integer (uintmax_t value, bool is_signed, bool negative,
147 const struct integer_base *,
148 const struct printf_conversion *,
149 void (*output) (char, void *), void *aux);
150static void output_dup (char ch, size_t cnt,
151 void (*output) (char, void *), void *aux);
152static void format_string (const char *string, int length,
153 struct printf_conversion *,
154 void (*output) (char, void *), void *aux);
155
156void
157__vprintf (const char *format, va_list args,
158 void (*output) (char, void *), void *aux)
159{
160 for (; *format != '\0'; format++)
161 {
162 struct printf_conversion c;
163
164 /* Literally copy non-conversions to output. */
165 if (*format != '%')
166 {
167 output (*format, aux);
168 continue;
169 }
170 format++;
171
172 /* %% => %. */
173 if (*format == '%')
174 {
175 output ('%', aux);
176 continue;
177 }
178
179 /* Parse conversion specifiers. */
180 format = parse_conversion (format, &c, &args);
181
182 /* Do conversion. */
183 switch (*format)
184 {
185 case 'd':
186 case 'i':
187 {
188 /* Signed integer conversions. */
189 intmax_t value;
190
191 switch (c.type)
192 {
193 case CHAR:
194 value = (signed char) va_arg (args, int);
195 break;
196 case SHORT:
197 value = (short) va_arg (args, int);
198 break;
199 case INT:
200 value = va_arg (args, int);
201 break;
202 case INTMAX:
203 value = va_arg (args, intmax_t);
204 break;
205 case LONG:
206 value = va_arg (args, long);
207 break;
208 case LONGLONG:
209 value = va_arg (args, long long);
210 break;
211 case PTRDIFFT:
212 value = va_arg (args, ptrdiff_t);
213 break;
214 case SIZET:
215 value = va_arg (args, size_t);
216 if (value > SIZE_MAX / 2)
217 value = value - SIZE_MAX - 1;
218 break;
219 default:
220 NOT_REACHED ();
221 }
222
223 format_integer (value < 0 ? -value : value,
224 true, value < 0, &base_d, &c, output, aux);
225 }
226 break;
227
228 case 'o':
229 case 'u':
230 case 'x':
231 case 'X':
232 {
233 /* Unsigned integer conversions. */
234 uintmax_t value;
235 const struct integer_base *b;
236
237 switch (c.type)
238 {
239 case CHAR:
240 value = (unsigned char) va_arg (args, unsigned);
241 break;
242 case SHORT:
243 value = (unsigned short) va_arg (args, unsigned);
244 break;
245 case INT:
246 value = va_arg (args, unsigned);
247 break;
248 case INTMAX:
249 value = va_arg (args, uintmax_t);
250 break;
251 case LONG:
252 value = va_arg (args, unsigned long);
253 break;
254 case LONGLONG:
255 value = va_arg (args, unsigned long long);
256 break;
257 case PTRDIFFT:
258 value = va_arg (args, ptrdiff_t);
259#if UINTMAX_MAX != PTRDIFF_MAX
260 value &= ((uintmax_t) PTRDIFF_MAX << 1) | 1;
261#endif
262 break;
263 case SIZET:
264 value = va_arg (args, size_t);
265 break;
266 default:
267 NOT_REACHED ();
268 }
269
270 switch (*format)
271 {
272 case 'o': b = &base_o; break;
273 case 'u': b = &base_d; break;
274 case 'x': b = &base_x; break;
275 case 'X': b = &base_X; break;
276 default: NOT_REACHED ();
277 }
278
279 format_integer (value, false, false, b, &c, output, aux);
280 }
281 break;
282
283 case 'c':
284 {
285 /* Treat character as single-character string. */
286 char ch = va_arg (args, int);
287 format_string (&ch, 1, &c, output, aux);
288 }
289 break;
290
291 case 's':
292 {
293 /* String conversion. */
294 const char *s = va_arg (args, char *);
295 if (s == NULL)
296 s = "(null)";
297
298 /* Limit string length according to precision.
299 Note: if c.precision == -1 then strnlen() will get
300 SIZE_MAX for MAXLEN, which is just what we want. */
301 format_string (s, strnlen (s, c.precision), &c, output, aux);
302 }
303 break;
304
305 case 'p':
306 {
307 /* Pointer conversion.
308 Format pointers as %#x. */
309 void *p = va_arg (args, void *);
310
311 c.flags = POUND;
312 format_integer ((uintptr_t) p, false, false,
313 &base_x, &c, output, aux);
314 }
315 break;
316
317 case 'f':
318 case 'e':
319 case 'E':
320 case 'g':
321 case 'G':
322 case 'n':
323 /* We don't support floating-point arithmetic,
324 and %n can be part of a security hole. */
325 __printf ("<<no %%%c in kernel>>", output, aux, *format);
326 break;
327
328 default:
329 __printf ("<<no %%%c conversion>>", output, aux, *format);
330 break;
331 }
332 }
333}
334
335/* Parses conversion option characters starting at FORMAT and
336 initializes C appropriately. Returns the character in FORMAT
337 that indicates the conversion (e.g. the `d' in `%d'). Uses
338 *ARGS for `*' field widths and precisions. */
339static const char *
340parse_conversion (const char *format, struct printf_conversion *c,
341 va_list *args)
342{
343 /* Parse flag characters. */
344 c->flags = 0;
345 for (;;)
346 {
347 switch (*format++)
348 {
349 case '-':
350 c->flags |= MINUS;
351 break;
352 case '+':
353 c->flags |= PLUS;
354 break;
355 case ' ':
356 c->flags |= SPACE;
357 break;
358 case '#':
359 c->flags |= POUND;
360 break;
361 case '0':
362 c->flags |= ZERO;
363 break;
364 case '\'':
365 c->flags |= GROUP;
366 break;
367 default:
368 format--;
369 goto not_a_flag;
370 }
371 }
372 not_a_flag:
373 if (c->flags & MINUS)
374 c->flags &= ~ZERO;
375 if (c->flags & PLUS)
376 c->flags &= ~SPACE;
377
378 /* Parse field width. */
379 c->width = 0;
380 if (*format == '*')
381 {
382 format++;
383 c->width = va_arg (*args, int);
384 }
385 else
386 {
387 for (; isdigit (*format); format++)
388 c->width = c->width * 10 + *format - '0';
389 }
390 if (c->width < 0)
391 {
392 c->width = -c->width;
393 c->flags |= MINUS;
394 }
395
396 /* Parse precision. */
397 c->precision = -1;
398 if (*format == '.')
399 {
400 format++;
401 if (*format == '*')
402 {
403 format++;
404 c->precision = va_arg (*args, int);
405 }
406 else
407 {
408 c->precision = 0;
409 for (; isdigit (*format); format++)
410 c->precision = c->precision * 10 + *format - '0';
411 }
412 if (c->precision < 0)
413 c->precision = -1;
414 }
415 if (c->precision >= 0)
416 c->flags &= ~ZERO;
417
418 /* Parse type. */
419 c->type = INT;
420 switch (*format++)
421 {
422 case 'h':
423 if (*format == 'h')
424 {
425 format++;
426 c->type = CHAR;
427 }
428 else
429 c->type = SHORT;
430 break;
431
432 case 'j':
433 c->type = INTMAX;
434 break;
435
436 case 'l':
437 if (*format == 'l')
438 {
439 format++;
440 c->type = LONGLONG;
441 }
442 else
443 c->type = LONG;
444 break;
445
446 case 't':
447 c->type = PTRDIFFT;
448 break;
449
450 case 'z':
451 c->type = SIZET;
452 break;
453
454 default:
455 format--;
456 break;
457 }
458
459 return format;
460}
461
462/* Performs an integer conversion, writing output to OUTPUT with
463 auxiliary data AUX. The integer converted has absolute value
464 VALUE. If IS_SIGNED is true, does a signed conversion with
465 NEGATIVE indicating a negative value; otherwise does an
466 unsigned conversion and ignores NEGATIVE. The output is done
467 according to the provided base B. Details of the conversion
468 are in C. */
469static void
470format_integer (uintmax_t value, bool is_signed, bool negative,
471 const struct integer_base *b,
472 const struct printf_conversion *c,
473 void (*output) (char, void *), void *aux)
474{
475 char buf[64], *cp; /* Buffer and current position. */
476 int x; /* `x' character to use or 0 if none. */
477 int sign; /* Sign character or 0 if none. */
478 int precision; /* Rendered precision. */
479 int pad_cnt; /* # of pad characters to fill field width. */
480 int digit_cnt; /* # of digits output so far. */
481
482 /* Determine sign character, if any.
483 An unsigned conversion will never have a sign character,
484 even if one of the flags requests one. */
485 sign = 0;
486 if (is_signed)
487 {
488 if (c->flags & PLUS)
489 sign = negative ? '-' : '+';
490 else if (c->flags & SPACE)
491 sign = negative ? '-' : ' ';
492 else if (negative)
493 sign = '-';
494 }
495
496 /* Determine whether to include `0x' or `0X'.
497 It will only be included with a hexadecimal conversion of a
498 nonzero value with the # flag. */
499 x = (c->flags & POUND) && value ? b->x : 0;
500
501 /* Accumulate digits into buffer.
502 This algorithm produces digits in reverse order, so later we
503 will output the buffer's content in reverse. */
504 cp = buf;
505 digit_cnt = 0;
506 while (value > 0)
507 {
508 if ((c->flags & GROUP) && digit_cnt > 0 && digit_cnt % b->group == 0)
509 *cp++ = ',';
510 *cp++ = b->digits[value % b->base];
511 value /= b->base;
512 digit_cnt++;
513 }
514
515 /* Append enough zeros to match precision.
516 If requested precision is 0, then a value of zero is
517 rendered as a null string, otherwise as "0".
518 If the # flag is used with base 8, the result must always
519 begin with a zero. */
520 precision = c->precision < 0 ? 1 : c->precision;
521 while (cp - buf < precision && cp < buf + sizeof buf - 1)
522 *cp++ = '0';
523 if ((c->flags & POUND) && b->base == 8 && (cp == buf || cp[-1] != '0'))
524 *cp++ = '0';
525
526 /* Calculate number of pad characters to fill field width. */
527 pad_cnt = c->width - (cp - buf) - (x ? 2 : 0) - (sign != 0);
528 if (pad_cnt < 0)
529 pad_cnt = 0;
530
531 /* Do output. */
532 if ((c->flags & (MINUS | ZERO)) == 0)
533 output_dup (' ', pad_cnt, output, aux);
534 if (sign)
535 output (sign, aux);
536 if (x)
537 {
538 output ('0', aux);
539 output (x, aux);
540 }
541 if (c->flags & ZERO)
542 output_dup ('0', pad_cnt, output, aux);
543 while (cp > buf)
544 output (*--cp, aux);
545 if (c->flags & MINUS)
546 output_dup (' ', pad_cnt, output, aux);
547}
548
549/* Writes CH to OUTPUT with auxiliary data AUX, CNT times. */
550static void
551output_dup (char ch, size_t cnt, void (*output) (char, void *), void *aux)
552{
553 while (cnt-- > 0)
554 output (ch, aux);
555}
556
557/* Formats the LENGTH characters starting at STRING according to
558 the conversion specified in C. Writes output to OUTPUT with
559 auxiliary data AUX. */
560static void
561format_string (const char *string, int length,
562 struct printf_conversion *c,
563 void (*output) (char, void *), void *aux)
564{
565 int i;
566 if (c->width > length && (c->flags & MINUS) == 0)
567 output_dup (' ', c->width - length, output, aux);
568 for (i = 0; i < length; i++)
569 output (string[i], aux);
570 if (c->width > length && (c->flags & MINUS) != 0)
571 output_dup (' ', c->width - length, output, aux);
572}
573
574/* Wrapper for __vprintf() that converts varargs into a
575 va_list. */
576void
577__printf (const char *format,
578 void (*output) (char, void *), void *aux, ...)
579{
580 va_list args;
581
582 va_start (args, aux);
583 __vprintf (format, args, output, aux);
584 va_end (args);
585}
586
587/* Dumps the SIZE bytes in BUF to the console as hex bytes
588 arranged 16 per line. Numeric offsets are also included,
589 starting at OFS for the first byte in BUF. If ASCII is true
590 then the corresponding ASCII characters are also rendered
591 alongside. */
592void
593hex_dump (uintptr_t ofs, const void *buf_, size_t size, bool ascii)
594{
595 const uint8_t *buf = buf_;
596 const size_t per_line = 16; /* Maximum bytes per line. */
597
598 while (size > 0)
599 {
600 size_t start, end, n;
601 size_t i;
602
603 /* Number of bytes on this line. */
604 start = ofs % per_line;
605 end = per_line;
606 if (end - start > size)
607 end = start + size;
608 n = end - start;
609
610 /* Print line. */
611 printf ("%08jx ", (uintmax_t) ROUND_DOWN (ofs, per_line));
612 for (i = 0; i < start; i++)
613 printf (" ");
614 for (; i < end; i++)
615 printf ("%02hhx%c",
616 buf[i - start], i == per_line / 2 - 1? '-' : ' ');
617 if (ascii)
618 {
619 for (; i < per_line; i++)
620 printf (" ");
621 printf ("|");
622 for (i = 0; i < start; i++)
623 printf (" ");
624 for (; i < end; i++)
625 printf ("%c",
626 isprint (buf[i - start]) ? buf[i - start] : '.');
627 for (; i < per_line; i++)
628 printf (" ");
629 printf ("|");
630 }
631 printf ("\n");
632
633 ofs += n;
634 buf += n;
635 size -= n;
636 }
637}
638
639/* Prints SIZE, which represents a number of bytes, in a
640 human-readable format, e.g. "256 kB". */
641void
642print_human_readable_size (uint64_t size)
643{
644 if (size == 1)
645 printf ("1 byte");
646 else
647 {
648 static const char *factors[] = {"bytes", "kB", "MB", "GB", "TB", NULL};
649 const char **fp;
650
651 for (fp = factors; size >= 1024 && fp[1] != NULL; fp++)
652 size /= 1024;
653 printf ("%"PRIu64" %s", size, *fp);
654 }
655}
diff --git a/pintos-progos/lib/stdio.h b/pintos-progos/lib/stdio.h
new file mode 100644
index 0000000..2739c0a
--- /dev/null
+++ b/pintos-progos/lib/stdio.h
@@ -0,0 +1,40 @@
1#ifndef __LIB_STDIO_H
2#define __LIB_STDIO_H
3
4#include <debug.h>
5#include <stdarg.h>
6#include <stdbool.h>
7#include <stddef.h>
8#include <stdint.h>
9
10/* Include lib/user/stdio.h or lib/kernel/stdio.h, as
11 appropriate. */
12#include_next <stdio.h>
13
14/* Predefined file handles. */
15#define STDIN_FILENO 0
16#define STDOUT_FILENO 1
17
18/* Standard functions. */
19int printf (const char *, ...) PRINTF_FORMAT (1, 2);
20int snprintf (char *, size_t, const char *, ...) PRINTF_FORMAT (3, 4);
21int vprintf (const char *, va_list) PRINTF_FORMAT (1, 0);
22int vsnprintf (char *, size_t, const char *, va_list) PRINTF_FORMAT (3, 0);
23int putchar (int);
24int puts (const char *);
25
26/* Nonstandard functions. */
27void hex_dump (uintptr_t ofs, const void *, size_t size, bool ascii);
28void print_human_readable_size (uint64_t sz);
29
30/* Internal functions. */
31void __vprintf (const char *format, va_list args,
32 void (*output) (char, void *), void *aux);
33void __printf (const char *format,
34 void (*output) (char, void *), void *aux, ...);
35
36/* Try to be helpful. */
37#define sprintf dont_use_sprintf_use_snprintf
38#define vsprintf dont_use_vsprintf_use_vsnprintf
39
40#endif /* lib/stdio.h */
diff --git a/pintos-progos/lib/stdlib.c b/pintos-progos/lib/stdlib.c
new file mode 100644
index 0000000..84c7f61
--- /dev/null
+++ b/pintos-progos/lib/stdlib.c
@@ -0,0 +1,208 @@
1#include <ctype.h>
2#include <debug.h>
3#include <random.h>
4#include <stdlib.h>
5#include <stdbool.h>
6
7/* Converts a string representation of a signed decimal integer
8 in S into an `int', which is returned. */
9int
10atoi (const char *s)
11{
12 bool negative;
13 int value;
14
15 ASSERT (s != NULL);
16
17 /* Skip white space. */
18 while (isspace ((unsigned char) *s))
19 s++;
20
21 /* Parse sign. */
22 negative = false;
23 if (*s == '+')
24 s++;
25 else if (*s == '-')
26 {
27 negative = true;
28 s++;
29 }
30
31 /* Parse digits. We always initially parse the value as
32 negative, and then make it positive later, because the
33 negative range of an int is bigger than the positive range
34 on a 2's complement system. */
35 for (value = 0; isdigit (*s); s++)
36 value = value * 10 - (*s - '0');
37 if (!negative)
38 value = -value;
39
40 return value;
41}
42
43/* Compares A and B by calling the AUX function. */
44static int
45compare_thunk (const void *a, const void *b, void *aux)
46{
47 int (**compare) (const void *, const void *) = aux;
48 return (*compare) (a, b);
49}
50
51/* Sorts ARRAY, which contains CNT elements of SIZE bytes each,
52 using COMPARE. When COMPARE is passed a pair of elements A
53 and B, respectively, it must return a strcmp()-type result,
54 i.e. less than zero if A < B, zero if A == B, greater than
55 zero if A > B. Runs in O(n lg n) time and O(1) space in
56 CNT. */
57void
58qsort (void *array, size_t cnt, size_t size,
59 int (*compare) (const void *, const void *))
60{
61 sort (array, cnt, size, compare_thunk, &compare);
62}
63
64/* Swaps elements with 1-based indexes A_IDX and B_IDX in ARRAY
65 with elements of SIZE bytes each. */
66static void
67do_swap (unsigned char *array, size_t a_idx, size_t b_idx, size_t size)
68{
69 unsigned char *a = array + (a_idx - 1) * size;
70 unsigned char *b = array + (b_idx - 1) * size;
71 size_t i;
72
73 for (i = 0; i < size; i++)
74 {
75 unsigned char t = a[i];
76 a[i] = b[i];
77 b[i] = t;
78 }
79}
80
81/* Compares elements with 1-based indexes A_IDX and B_IDX in
82 ARRAY with elements of SIZE bytes each, using COMPARE to
83 compare elements, passing AUX as auxiliary data, and returns a
84 strcmp()-type result. */
85static int
86do_compare (unsigned char *array, size_t a_idx, size_t b_idx, size_t size,
87 int (*compare) (const void *, const void *, void *aux),
88 void *aux)
89{
90 return compare (array + (a_idx - 1) * size, array + (b_idx - 1) * size, aux);
91}
92
93/* "Float down" the element with 1-based index I in ARRAY of CNT
94 elements of SIZE bytes each, using COMPARE to compare
95 elements, passing AUX as auxiliary data. */
96static void
97heapify (unsigned char *array, size_t i, size_t cnt, size_t size,
98 int (*compare) (const void *, const void *, void *aux),
99 void *aux)
100{
101 for (;;)
102 {
103 /* Set `max' to the index of the largest element among I
104 and its children (if any). */
105 size_t left = 2 * i;
106 size_t right = 2 * i + 1;
107 size_t max = i;
108 if (left <= cnt && do_compare (array, left, max, size, compare, aux) > 0)
109 max = left;
110 if (right <= cnt
111 && do_compare (array, right, max, size, compare, aux) > 0)
112 max = right;
113
114 /* If the maximum value is already in element I, we're
115 done. */
116 if (max == i)
117 break;
118
119 /* Swap and continue down the heap. */
120 do_swap (array, i, max, size);
121 i = max;
122 }
123}
124
125/* Sorts ARRAY, which contains CNT elements of SIZE bytes each,
126 using COMPARE to compare elements, passing AUX as auxiliary
127 data. When COMPARE is passed a pair of elements A and B,
128 respectively, it must return a strcmp()-type result, i.e. less
129 than zero if A < B, zero if A == B, greater than zero if A >
130 B. Runs in O(n lg n) time and O(1) space in CNT. */
131void
132sort (void *array, size_t cnt, size_t size,
133 int (*compare) (const void *, const void *, void *aux),
134 void *aux)
135{
136 size_t i;
137
138 ASSERT (array != NULL || cnt == 0);
139 ASSERT (compare != NULL);
140 ASSERT (size > 0);
141
142 /* Build a heap. */
143 for (i = cnt / 2; i > 0; i--)
144 heapify (array, i, cnt, size, compare, aux);
145
146 /* Sort the heap. */
147 for (i = cnt; i > 1; i--)
148 {
149 do_swap (array, 1, i, size);
150 heapify (array, 1, i - 1, size, compare, aux);
151 }
152}
153
154/* Searches ARRAY, which contains CNT elements of SIZE bytes
155 each, for the given KEY. Returns a match is found, otherwise
156 a null pointer. If there are multiple matches, returns an
157 arbitrary one of them.
158
159 ARRAY must be sorted in order according to COMPARE.
160
161 Uses COMPARE to compare elements. When COMPARE is passed a
162 pair of elements A and B, respectively, it must return a
163 strcmp()-type result, i.e. less than zero if A < B, zero if A
164 == B, greater than zero if A > B. */
165void *
166bsearch (const void *key, const void *array, size_t cnt,
167 size_t size, int (*compare) (const void *, const void *))
168{
169 return binary_search (key, array, cnt, size, compare_thunk, &compare);
170}
171
172/* Searches ARRAY, which contains CNT elements of SIZE bytes
173 each, for the given KEY. Returns a match is found, otherwise
174 a null pointer. If there are multiple matches, returns an
175 arbitrary one of them.
176
177 ARRAY must be sorted in order according to COMPARE.
178
179 Uses COMPARE to compare elements, passing AUX as auxiliary
180 data. When COMPARE is passed a pair of elements A and B,
181 respectively, it must return a strcmp()-type result, i.e. less
182 than zero if A < B, zero if A == B, greater than zero if A >
183 B. */
184void *
185binary_search (const void *key, const void *array, size_t cnt, size_t size,
186 int (*compare) (const void *, const void *, void *aux),
187 void *aux)
188{
189 const unsigned char *first = array;
190 const unsigned char *last = array + size * cnt;
191
192 while (first < last)
193 {
194 size_t range = (last - first) / size;
195 const unsigned char *middle = first + (range / 2) * size;
196 int cmp = compare (key, middle, aux);
197
198 if (cmp < 0)
199 last = middle;
200 else if (cmp > 0)
201 first = middle + size;
202 else
203 return (void *) middle;
204 }
205
206 return NULL;
207}
208
diff --git a/pintos-progos/lib/stdlib.h b/pintos-progos/lib/stdlib.h
new file mode 100644
index 0000000..d14afa3
--- /dev/null
+++ b/pintos-progos/lib/stdlib.h
@@ -0,0 +1,22 @@
1#ifndef __LIB_STDLIB_H
2#define __LIB_STDLIB_H
3
4#include <stddef.h>
5
6/* Standard functions. */
7int atoi (const char *);
8void qsort (void *array, size_t cnt, size_t size,
9 int (*compare) (const void *, const void *));
10void *bsearch (const void *key, const void *array, size_t cnt,
11 size_t size, int (*compare) (const void *, const void *));
12
13/* Nonstandard functions. */
14void sort (void *array, size_t cnt, size_t size,
15 int (*compare) (const void *, const void *, void *aux),
16 void *aux);
17void *binary_search (const void *key, const void *array, size_t cnt,
18 size_t size,
19 int (*compare) (const void *, const void *, void *aux),
20 void *aux);
21
22#endif /* lib/stdlib.h */
diff --git a/pintos-progos/lib/string.c b/pintos-progos/lib/string.c
new file mode 100644
index 0000000..d223c89
--- /dev/null
+++ b/pintos-progos/lib/string.c
@@ -0,0 +1,375 @@
1#include <string.h>
2#include <debug.h>
3
4/* Copies SIZE bytes from SRC to DST, which must not overlap.
5 Returns DST. */
6void *
7memcpy (void *dst_, const void *src_, size_t size)
8{
9 unsigned char *dst = dst_;
10 const unsigned char *src = src_;
11
12 ASSERT (dst != NULL || size == 0);
13 ASSERT (src != NULL || size == 0);
14
15 while (size-- > 0)
16 *dst++ = *src++;
17
18 return dst_;
19}
20
21/* Copies SIZE bytes from SRC to DST, which are allowed to
22 overlap. Returns DST. */
23void *
24memmove (void *dst_, const void *src_, size_t size)
25{
26 unsigned char *dst = dst_;
27 const unsigned char *src = src_;
28
29 ASSERT (dst != NULL || size == 0);
30 ASSERT (src != NULL || size == 0);
31
32 if (dst < src)
33 {
34 while (size-- > 0)
35 *dst++ = *src++;
36 }
37 else
38 {
39 dst += size;
40 src += size;
41 while (size-- > 0)
42 *--dst = *--src;
43 }
44
45 return dst;
46}
47
48/* Find the first differing byte in the two blocks of SIZE bytes
49 at A and B. Returns a positive value if the byte in A is
50 greater, a negative value if the byte in B is greater, or zero
51 if blocks A and B are equal. */
52int
53memcmp (const void *a_, const void *b_, size_t size)
54{
55 const unsigned char *a = a_;
56 const unsigned char *b = b_;
57
58 ASSERT (a != NULL || size == 0);
59 ASSERT (b != NULL || size == 0);
60
61 for (; size-- > 0; a++, b++)
62 if (*a != *b)
63 return *a > *b ? +1 : -1;
64 return 0;
65}
66
67/* Finds the first differing characters in strings A and B.
68 Returns a positive value if the character in A (as an unsigned
69 char) is greater, a negative value if the character in B (as
70 an unsigned char) is greater, or zero if strings A and B are
71 equal. */
72int
73strcmp (const char *a_, const char *b_)
74{
75 const unsigned char *a = (const unsigned char *) a_;
76 const unsigned char *b = (const unsigned char *) b_;
77
78 ASSERT (a != NULL);
79 ASSERT (b != NULL);
80
81 while (*a != '\0' && *a == *b)
82 {
83 a++;
84 b++;
85 }
86
87 return *a < *b ? -1 : *a > *b;
88}
89
90/* Returns a pointer to the first occurrence of CH in the first
91 SIZE bytes starting at BLOCK. Returns a null pointer if CH
92 does not occur in BLOCK. */
93void *
94memchr (const void *block_, int ch_, size_t size)
95{
96 const unsigned char *block = block_;
97 unsigned char ch = ch_;
98
99 ASSERT (block != NULL || size == 0);
100
101 for (; size-- > 0; block++)
102 if (*block == ch)
103 return (void *) block;
104
105 return NULL;
106}
107
108/* Finds and returns the first occurrence of C in STRING, or a
109 null pointer if C does not appear in STRING. If C == '\0'
110 then returns a pointer to the null terminator at the end of
111 STRING. */
112char *
113strchr (const char *string, int c_)
114{
115 char c = c_;
116
117 ASSERT (string != NULL);
118
119 for (;;)
120 if (*string == c)
121 return (char *) string;
122 else if (*string == '\0')
123 return NULL;
124 else
125 string++;
126}
127
128/* Returns the length of the initial substring of STRING that
129 consists of characters that are not in STOP. */
130size_t
131strcspn (const char *string, const char *stop)
132{
133 size_t length;
134
135 for (length = 0; string[length] != '\0'; length++)
136 if (strchr (stop, string[length]) != NULL)
137 break;
138 return length;
139}
140
141/* Returns a pointer to the first character in STRING that is
142 also in STOP. If no character in STRING is in STOP, returns a
143 null pointer. */
144char *
145strpbrk (const char *string, const char *stop)
146{
147 for (; *string != '\0'; string++)
148 if (strchr (stop, *string) != NULL)
149 return (char *) string;
150 return NULL;
151}
152
153/* Returns a pointer to the last occurrence of C in STRING.
154 Returns a null pointer if C does not occur in STRING. */
155char *
156strrchr (const char *string, int c_)
157{
158 char c = c_;
159 const char *p = NULL;
160
161 for (; *string != '\0'; string++)
162 if (*string == c)
163 p = string;
164 return (char *) p;
165}
166
167/* Returns the length of the initial substring of STRING that
168 consists of characters in SKIP. */
169size_t
170strspn (const char *string, const char *skip)
171{
172 size_t length;
173
174 for (length = 0; string[length] != '\0'; length++)
175 if (strchr (skip, string[length]) == NULL)
176 break;
177 return length;
178}
179
180/* Returns a pointer to the first occurrence of NEEDLE within
181 HAYSTACK. Returns a null pointer if NEEDLE does not exist
182 within HAYSTACK. */
183char *
184strstr (const char *haystack, const char *needle)
185{
186 size_t haystack_len = strlen (haystack);
187 size_t needle_len = strlen (needle);
188
189 if (haystack_len >= needle_len)
190 {
191 size_t i;
192
193 for (i = 0; i <= haystack_len - needle_len; i++)
194 if (!memcmp (haystack + i, needle, needle_len))
195 return (char *) haystack + i;
196 }
197
198 return NULL;
199}
200
201/* Breaks a string into tokens separated by DELIMITERS. The
202 first time this function is called, S should be the string to
203 tokenize, and in subsequent calls it must be a null pointer.
204 SAVE_PTR is the address of a `char *' variable used to keep
205 track of the tokenizer's position. The return value each time
206 is the next token in the string, or a null pointer if no
207 tokens remain.
208
209 This function treats multiple adjacent delimiters as a single
210 delimiter. The returned tokens will never be length 0.
211 DELIMITERS may change from one call to the next within a
212 single string.
213
214 strtok_r() modifies the string S, changing delimiters to null
215 bytes. Thus, S must be a modifiable string. String literals,
216 in particular, are *not* modifiable in C, even though for
217 backward compatibility they are not `const'.
218
219 Example usage:
220
221 char s[] = " String to tokenize. ";
222 char *token, *save_ptr;
223
224 for (token = strtok_r (s, " ", &save_ptr); token != NULL;
225 token = strtok_r (NULL, " ", &save_ptr))
226 printf ("'%s'\n", token);
227
228 outputs:
229
230 'String'
231 'to'
232 'tokenize.'
233*/
234char *
235strtok_r (char *s, const char *delimiters, char **save_ptr)
236{
237 char *token;
238
239 ASSERT (delimiters != NULL);
240 ASSERT (save_ptr != NULL);
241
242 /* If S is nonnull, start from it.
243 If S is null, start from saved position. */
244 if (s == NULL)
245 s = *save_ptr;
246 ASSERT (s != NULL);
247
248 /* Skip any DELIMITERS at our current position. */
249 while (strchr (delimiters, *s) != NULL)
250 {
251 /* strchr() will always return nonnull if we're searching
252 for a null byte, because every string contains a null
253 byte (at the end). */
254 if (*s == '\0')
255 {
256 *save_ptr = s;
257 return NULL;
258 }
259
260 s++;
261 }
262
263 /* Skip any non-DELIMITERS up to the end of the string. */
264 token = s;
265 while (strchr (delimiters, *s) == NULL)
266 s++;
267 if (*s != '\0')
268 {
269 *s = '\0';
270 *save_ptr = s + 1;
271 }
272 else
273 *save_ptr = s;
274 return token;
275}
276
277/* Sets the SIZE bytes in DST to VALUE. */
278void *
279memset (void *dst_, int value, size_t size)
280{
281 unsigned char *dst = dst_;
282
283 ASSERT (dst != NULL || size == 0);
284
285 while (size-- > 0)
286 *dst++ = value;
287
288 return dst_;
289}
290
291/* Returns the length of STRING. */
292size_t
293strlen (const char *string)
294{
295 const char *p;
296
297 ASSERT (string != NULL);
298
299 for (p = string; *p != '\0'; p++)
300 continue;
301 return p - string;
302}
303
304/* If STRING is less than MAXLEN characters in length, returns
305 its actual length. Otherwise, returns MAXLEN. */
306size_t
307strnlen (const char *string, size_t maxlen)
308{
309 size_t length;
310
311 for (length = 0; string[length] != '\0' && length < maxlen; length++)
312 continue;
313 return length;
314}
315
316/* Copies string SRC to DST. If SRC is longer than SIZE - 1
317 characters, only SIZE - 1 characters are copied. A null
318 terminator is always written to DST, unless SIZE is 0.
319 Returns the length of SRC, not including the null terminator.
320
321 strlcpy() is not in the standard C library, but it is an
322 increasingly popular extension. See
323 http://www.courtesan.com/todd/papers/strlcpy.html for
324 information on strlcpy(). */
325size_t
326strlcpy (char *dst, const char *src, size_t size)
327{
328 size_t src_len;
329
330 ASSERT (dst != NULL);
331 ASSERT (src != NULL);
332
333 src_len = strlen (src);
334 if (size > 0)
335 {
336 size_t dst_len = size - 1;
337 if (src_len < dst_len)
338 dst_len = src_len;
339 memcpy (dst, src, dst_len);
340 dst[dst_len] = '\0';
341 }
342 return src_len;
343}
344
345/* Concatenates string SRC to DST. The concatenated string is
346 limited to SIZE - 1 characters. A null terminator is always
347 written to DST, unless SIZE is 0. Returns the length that the
348 concatenated string would have assuming that there was
349 sufficient space, not including a null terminator.
350
351 strlcat() is not in the standard C library, but it is an
352 increasingly popular extension. See
353 http://www.courtesan.com/todd/papers/strlcpy.html for
354 information on strlcpy(). */
355size_t
356strlcat (char *dst, const char *src, size_t size)
357{
358 size_t src_len, dst_len;
359
360 ASSERT (dst != NULL);
361 ASSERT (src != NULL);
362
363 src_len = strlen (src);
364 dst_len = strlen (dst);
365 if (size > 0 && dst_len < size)
366 {
367 size_t copy_cnt = size - dst_len - 1;
368 if (src_len < copy_cnt)
369 copy_cnt = src_len;
370 memcpy (dst + dst_len, src, copy_cnt);
371 dst[dst_len + copy_cnt] = '\0';
372 }
373 return src_len + dst_len;
374}
375
diff --git a/pintos-progos/lib/string.h b/pintos-progos/lib/string.h
new file mode 100644
index 0000000..1fff82a
--- /dev/null
+++ b/pintos-progos/lib/string.h
@@ -0,0 +1,35 @@
1#ifndef __LIB_STRING_H
2#define __LIB_STRING_H
3
4#include <stddef.h>
5
6/* Standard. */
7void *memcpy (void *, const void *, size_t);
8void *memmove (void *, const void *, size_t);
9char *strncat (char *, const char *, size_t);
10int memcmp (const void *, const void *, size_t);
11int strcmp (const char *, const char *);
12void *memchr (const void *, int, size_t);
13char *strchr (const char *, int);
14size_t strcspn (const char *, const char *);
15char *strpbrk (const char *, const char *);
16char *strrchr (const char *, int);
17size_t strspn (const char *, const char *);
18char *strstr (const char *, const char *);
19void *memset (void *, int, size_t);
20size_t strlen (const char *);
21
22/* Extensions. */
23size_t strlcpy (char *, const char *, size_t);
24size_t strlcat (char *, const char *, size_t);
25char *strtok_r (char *, const char *, char **);
26size_t strnlen (const char *, size_t);
27
28/* Try to be helpful. */
29#define strcpy dont_use_strcpy_use_strlcpy
30#define strncpy dont_use_strncpy_use_strlcpy
31#define strcat dont_use_strcat_use_strlcat
32#define strncat dont_use_strncat_use_strlcat
33#define strtok dont_use_strtok_use_strtok_r
34
35#endif /* lib/string.h */
diff --git a/pintos-progos/lib/syscall-nr.h b/pintos-progos/lib/syscall-nr.h
new file mode 100644
index 0000000..21a7af9
--- /dev/null
+++ b/pintos-progos/lib/syscall-nr.h
@@ -0,0 +1,34 @@
1#ifndef __LIB_SYSCALL_NR_H
2#define __LIB_SYSCALL_NR_H
3
4/* System call numbers. */
5enum
6 {
7 /* Projects 2 and later. */
8 SYS_HALT, /* Halt the operating system. */
9 SYS_EXIT, /* Terminate this process. */
10 SYS_EXEC, /* Start another process. */
11 SYS_WAIT, /* Wait for a child process to die. */
12 SYS_CREATE, /* Create a file. */
13 SYS_REMOVE, /* Delete a file. */
14 SYS_OPEN, /* Open a file. */
15 SYS_FILESIZE, /* Obtain a file's size. */
16 SYS_READ, /* Read from a file. */
17 SYS_WRITE, /* Write to a file. */
18 SYS_SEEK, /* Change position in a file. */
19 SYS_TELL, /* Report current position in a file. */
20 SYS_CLOSE, /* Close a file. */
21
22 /* Project 3 and optionally project 4. */
23 SYS_MMAP, /* Map a file into memory. */
24 SYS_MUNMAP, /* Remove a memory mapping. */
25
26 /* Project 4 only. */
27 SYS_CHDIR, /* Change the current directory. */
28 SYS_MKDIR, /* Create a directory. */
29 SYS_READDIR, /* Reads a directory entry. */
30 SYS_ISDIR, /* Tests if a fd represents a directory. */
31 SYS_INUMBER /* Returns the inode number for a fd. */
32 };
33
34#endif /* lib/syscall-nr.h */
diff --git a/pintos-progos/lib/user/console.c b/pintos-progos/lib/user/console.c
new file mode 100644
index 0000000..22bdc8c
--- /dev/null
+++ b/pintos-progos/lib/user/console.c
@@ -0,0 +1,94 @@
1#include <stdio.h>
2#include <string.h>
3#include <syscall.h>
4#include <syscall-nr.h>
5
6/* The standard vprintf() function,
7 which is like printf() but uses a va_list. */
8int
9vprintf (const char *format, va_list args)
10{
11 return vhprintf (STDOUT_FILENO, format, args);
12}
13
14/* Like printf(), but writes output to the given HANDLE. */
15int
16hprintf (int handle, const char *format, ...)
17{
18 va_list args;
19 int retval;
20
21 va_start (args, format);
22 retval = vhprintf (handle, format, args);
23 va_end (args);
24
25 return retval;
26}
27
28/* Writes string S to the console, followed by a new-line
29 character. */
30int
31puts (const char *s)
32{
33 write (STDOUT_FILENO, s, strlen (s));
34 putchar ('\n');
35
36 return 0;
37}
38
39/* Writes C to the console. */
40int
41putchar (int c)
42{
43 char c2 = c;
44 write (STDOUT_FILENO, &c2, 1);
45 return c;
46}
47
48/* Auxiliary data for vhprintf_helper(). */
49struct vhprintf_aux
50 {
51 char buf[64]; /* Character buffer. */
52 char *p; /* Current position in buffer. */
53 int char_cnt; /* Total characters written so far. */
54 int handle; /* Output file handle. */
55 };
56
57static void add_char (char, void *);
58static void flush (struct vhprintf_aux *);
59
60/* Formats the printf() format specification FORMAT with
61 arguments given in ARGS and writes the output to the given
62 HANDLE. */
63int
64vhprintf (int handle, const char *format, va_list args)
65{
66 struct vhprintf_aux aux;
67 aux.p = aux.buf;
68 aux.char_cnt = 0;
69 aux.handle = handle;
70 __vprintf (format, args, add_char, &aux);
71 flush (&aux);
72 return aux.char_cnt;
73}
74
75/* Adds C to the buffer in AUX, flushing it if the buffer fills
76 up. */
77static void
78add_char (char c, void *aux_)
79{
80 struct vhprintf_aux *aux = aux_;
81 *aux->p++ = c;
82 if (aux->p >= aux->buf + sizeof aux->buf)
83 flush (aux);
84 aux->char_cnt++;
85}
86
87/* Flushes the buffer in AUX. */
88static void
89flush (struct vhprintf_aux *aux)
90{
91 if (aux->p > aux->buf)
92 write (aux->handle, aux->buf, aux->p - aux->buf);
93 aux->p = aux->buf;
94}
diff --git a/pintos-progos/lib/user/debug.c b/pintos-progos/lib/user/debug.c
new file mode 100644
index 0000000..f49b874
--- /dev/null
+++ b/pintos-progos/lib/user/debug.c
@@ -0,0 +1,25 @@
1#include <debug.h>
2#include <stdarg.h>
3#include <stdbool.h>
4#include <stdio.h>
5#include <syscall.h>
6
7/* Aborts the user program, printing the source file name, line
8 number, and function name, plus a user-specific message. */
9void
10debug_panic (const char *file, int line, const char *function,
11 const char *message, ...)
12{
13 va_list args;
14
15 printf ("User process ABORT at %s:%d in %s(): ", file, line, function);
16
17 va_start (args, message);
18 vprintf (message, args);
19 printf ("\n");
20 va_end (args);
21
22 debug_backtrace ();
23
24 exit (1);
25}
diff --git a/pintos-progos/lib/user/entry.c b/pintos-progos/lib/user/entry.c
new file mode 100644
index 0000000..a707c70
--- /dev/null
+++ b/pintos-progos/lib/user/entry.c
@@ -0,0 +1,10 @@
1#include <syscall.h>
2
3int main (int, char *[]);
4void _start (int argc, char *argv[]);
5
6void
7_start (int argc, char *argv[])
8{
9 exit (main (argc, argv));
10}
diff --git a/pintos-progos/lib/user/stdio.h b/pintos-progos/lib/user/stdio.h
new file mode 100644
index 0000000..b9f3cc6
--- /dev/null
+++ b/pintos-progos/lib/user/stdio.h
@@ -0,0 +1,7 @@
1#ifndef __LIB_USER_STDIO_H
2#define __LIB_USER_STDIO_H
3
4int hprintf (int, const char *, ...) PRINTF_FORMAT (2, 3);
5int vhprintf (int, const char *, va_list) PRINTF_FORMAT (2, 0);
6
7#endif /* lib/user/stdio.h */
diff --git a/pintos-progos/lib/user/syscall.c b/pintos-progos/lib/user/syscall.c
new file mode 100644
index 0000000..0a467f8
--- /dev/null
+++ b/pintos-progos/lib/user/syscall.c
@@ -0,0 +1,184 @@
1#include <syscall.h>
2#include "../syscall-nr.h"
3
4/* Invokes syscall NUMBER, passing no arguments, and returns the
5 return value as an `int'. */
6#define syscall0(NUMBER) \
7 ({ \
8 int retval; \
9 asm volatile \
10 ("pushl %[number]; int $0x30; addl $4, %%esp" \
11 : "=a" (retval) \
12 : [number] "i" (NUMBER) \
13 : "memory"); \
14 retval; \
15 })
16
17/* Invokes syscall NUMBER, passing argument ARG0, and returns the
18 return value as an `int'. */
19#define syscall1(NUMBER, ARG0) \
20 ({ \
21 int retval; \
22 asm volatile \
23 ("pushl %[arg0]; pushl %[number]; int $0x30; addl $8, %%esp" \
24 : "=a" (retval) \
25 : [number] "i" (NUMBER), \
26 [arg0] "g" (ARG0) \
27 : "memory"); \
28 retval; \
29 })
30
31/* Invokes syscall NUMBER, passing arguments ARG0 and ARG1, and
32 returns the return value as an `int'. */
33#define syscall2(NUMBER, ARG0, ARG1) \
34 ({ \
35 int retval; \
36 asm volatile \
37 ("pushl %[arg1]; pushl %[arg0]; " \
38 "pushl %[number]; int $0x30; addl $12, %%esp" \
39 : "=a" (retval) \
40 : [number] "i" (NUMBER), \
41 [arg0] "r" (ARG0), \
42 [arg1] "r" (ARG1) \
43 : "memory"); \
44 retval; \
45 })
46
47/* Invokes syscall NUMBER, passing arguments ARG0, ARG1, and
48 ARG2, and returns the return value as an `int'. */
49#define syscall3(NUMBER, ARG0, ARG1, ARG2) \
50 ({ \
51 int retval; \
52 asm volatile \
53 ("pushl %[arg2]; pushl %[arg1]; pushl %[arg0]; " \
54 "pushl %[number]; int $0x30; addl $16, %%esp" \
55 : "=a" (retval) \
56 : [number] "i" (NUMBER), \
57 [arg0] "r" (ARG0), \
58 [arg1] "r" (ARG1), \
59 [arg2] "r" (ARG2) \
60 : "memory"); \
61 retval; \
62 })
63
64void
65halt (void)
66{
67 syscall0 (SYS_HALT);
68 NOT_REACHED ();
69}
70
71void
72exit (int status)
73{
74 syscall1 (SYS_EXIT, status);
75 NOT_REACHED ();
76}
77
78pid_t
79exec (const char *cmd_line)
80{
81 return (pid_t) syscall1 (SYS_EXEC, cmd_line);
82}
83
84int
85wait (pid_t pid)
86{
87 return syscall1 (SYS_WAIT, pid);
88}
89
90bool
91create (const char *file, unsigned initial_size)
92{
93 return syscall2 (SYS_CREATE, file, initial_size);
94}
95
96bool
97remove (const char *file)
98{
99 return syscall1 (SYS_REMOVE, file);
100}
101
102int
103open (const char *file)
104{
105 return syscall1 (SYS_OPEN, file);
106}
107
108int
109filesize (int fd)
110{
111 return syscall1 (SYS_FILESIZE, fd);
112}
113
114int
115read (int fd, void *buffer, unsigned size)
116{
117 return syscall3 (SYS_READ, fd, buffer, size);
118}
119
120int
121write (int fd, const void *buffer, unsigned size)
122{
123 return syscall3 (SYS_WRITE, fd, buffer, size);
124}
125
126void
127seek (int fd, unsigned position)
128{
129 syscall2 (SYS_SEEK, fd, position);
130}
131
132unsigned
133tell (int fd)
134{
135 return syscall1 (SYS_TELL, fd);
136}
137
138void
139close (int fd)
140{
141 syscall1 (SYS_CLOSE, fd);
142}
143
144mapid_t
145mmap (int fd, void *addr)
146{
147 return syscall2 (SYS_MMAP, fd, addr);
148}
149
150void
151munmap (mapid_t mapid)
152{
153 syscall1 (SYS_MUNMAP, mapid);
154}
155
156bool
157chdir (const char *dir)
158{
159 return syscall1 (SYS_CHDIR, dir);
160}
161
162bool
163mkdir (const char *dir)
164{
165 return syscall1 (SYS_MKDIR, dir);
166}
167
168bool
169readdir (int fd, char name[READDIR_MAX_LEN + 1])
170{
171 return syscall2 (SYS_READDIR, fd, name);
172}
173
174bool
175isdir (int fd)
176{
177 return syscall1 (SYS_ISDIR, fd);
178}
179
180int
181inumber (int fd)
182{
183 return syscall1 (SYS_INUMBER, fd);
184}
diff --git a/pintos-progos/lib/user/syscall.h b/pintos-progos/lib/user/syscall.h
new file mode 100644
index 0000000..a1bcf0b
--- /dev/null
+++ b/pintos-progos/lib/user/syscall.h
@@ -0,0 +1,48 @@
1#ifndef __LIB_USER_SYSCALL_H
2#define __LIB_USER_SYSCALL_H
3
4#include <stdbool.h>
5#include <debug.h>
6
7/* Process identifier. */
8typedef int pid_t;
9#define PID_ERROR ((pid_t) -1)
10
11/* Map region identifier. */
12typedef int mapid_t;
13#define MAP_FAILED ((mapid_t) -1)
14
15/* Maximum characters in a filename written by readdir(). */
16#define READDIR_MAX_LEN 14
17
18/* Typical return values from main() and arguments to exit(). */
19#define EXIT_SUCCESS 0 /* Successful execution. */
20#define EXIT_FAILURE 1 /* Unsuccessful execution. */
21
22/* Projects 2 and later. */
23void halt (void) NO_RETURN;
24void exit (int status) NO_RETURN;
25pid_t exec (const char *cmd_line);
26int wait (pid_t);
27bool create (const char *file, unsigned initial_size);
28bool remove (const char *file);
29int open (const char *file);
30int filesize (int fd);
31int read (int fd, void *buffer, unsigned length);
32int write (int fd, const void *buffer, unsigned length);
33void seek (int fd, unsigned position);
34unsigned tell (int fd);
35void close (int fd);
36
37/* Project 3 and optionally project 4. */
38mapid_t mmap (int fd, void *addr);
39void munmap (mapid_t);
40
41/* Project 4 only. */
42bool chdir (const char *dir);
43bool mkdir (const char *dir);
44bool readdir (int fd, char name[READDIR_MAX_LEN + 1]);
45bool isdir (int fd);
46int inumber (int fd);
47
48#endif /* lib/user/syscall.h */
diff --git a/pintos-progos/lib/user/user.lds b/pintos-progos/lib/user/user.lds
new file mode 100644
index 0000000..cc6d6c0
--- /dev/null
+++ b/pintos-progos/lib/user/user.lds
@@ -0,0 +1,57 @@
1OUTPUT_FORMAT("elf32-i386")
2OUTPUT_ARCH(i386)
3ENTRY(_start)
4
5SECTIONS
6{
7 /* Read-only sections, merged into text segment: */
8 __executable_start = 0x08048000 + SIZEOF_HEADERS;
9 . = 0x08048000 + SIZEOF_HEADERS;
10 .text : { *(.text) } = 0x90
11 .rodata : { *(.rodata) }
12
13 /* Adjust the address for the data segment. We want to adjust up to
14 the same address within the page on the next page up. */
15 . = ALIGN (0x1000) - ((0x1000 - .) & (0x1000 - 1));
16 . = DATA_SEGMENT_ALIGN (0x1000, 0x1000);
17
18 .data : { *(.data) }
19 .bss : { *(.bss) }
20
21 /* Stabs debugging sections. */
22 .stab 0 : { *(.stab) }
23 .stabstr 0 : { *(.stabstr) }
24 .stab.excl 0 : { *(.stab.excl) }
25 .stab.exclstr 0 : { *(.stab.exclstr) }
26 .stab.index 0 : { *(.stab.index) }
27 .stab.indexstr 0 : { *(.stab.indexstr) }
28 .comment 0 : { *(.comment) }
29
30 /* DWARF debug sections.
31 Symbols in the DWARF debugging sections are relative to the beginning
32 of the section so we begin them at 0. */
33 /* DWARF 1 */
34 .debug 0 : { *(.debug) }
35 .line 0 : { *(.line) }
36 /* GNU DWARF 1 extensions */
37 .debug_srcinfo 0 : { *(.debug_srcinfo) }
38 .debug_sfnames 0 : { *(.debug_sfnames) }
39 /* DWARF 1.1 and DWARF 2 */
40 .debug_aranges 0 : { *(.debug_aranges) }
41 .debug_pubnames 0 : { *(.debug_pubnames) }
42 /* DWARF 2 */
43 .debug_info 0 : { *(.debug_info .gnu.linkonce.wi.*) }
44 .debug_abbrev 0 : { *(.debug_abbrev) }
45 .debug_line 0 : { *(.debug_line) }
46 .debug_frame 0 : { *(.debug_frame) }
47 .debug_str 0 : { *(.debug_str) }
48 .debug_loc 0 : { *(.debug_loc) }
49 .debug_macinfo 0 : { *(.debug_macinfo) }
50 /* SGI/MIPS DWARF 2 extensions */
51 .debug_weaknames 0 : { *(.debug_weaknames) }
52 .debug_funcnames 0 : { *(.debug_funcnames) }
53 .debug_typenames 0 : { *(.debug_typenames) }
54 .debug_varnames 0 : { *(.debug_varnames) }
55 /DISCARD/ : { *(.note.GNU-stack) }
56 /DISCARD/ : { *(.eh_frame) }
57}
diff --git a/pintos-progos/lib/ustar.c b/pintos-progos/lib/ustar.c
new file mode 100644
index 0000000..49af69a
--- /dev/null
+++ b/pintos-progos/lib/ustar.c
@@ -0,0 +1,228 @@
1#include <ustar.h>
2#include <limits.h>
3#include <packed.h>
4#include <stdio.h>
5#include <string.h>
6
7/* Header for ustar-format tar archive. See the documentation of
8 the "pax" utility in [SUSv3] for the the "ustar" format
9 specification. */
10struct ustar_header
11 {
12 char name[100]; /* File name. Null-terminated if room. */
13 char mode[8]; /* Permissions as octal string. */
14 char uid[8]; /* User ID as octal string. */
15 char gid[8]; /* Group ID as octal string. */
16 char size[12]; /* File size in bytes as octal string. */
17 char mtime[12]; /* Modification time in seconds
18 from Jan 1, 1970, as octal string. */
19 char chksum[8]; /* Sum of octets in header as octal string. */
20 char typeflag; /* An enum ustar_type value. */
21 char linkname[100]; /* Name of link target.
22 Null-terminated if room. */
23 char magic[6]; /* "ustar\0" */
24 char version[2]; /* "00" */
25 char uname[32]; /* User name, always null-terminated. */
26 char gname[32]; /* Group name, always null-terminated. */
27 char devmajor[8]; /* Device major number as octal string. */
28 char devminor[8]; /* Device minor number as octal string. */
29 char prefix[155]; /* Prefix to file name.
30 Null-terminated if room. */
31 char padding[12]; /* Pad to 512 bytes. */
32 }
33PACKED;
34
35/* Returns the checksum for the given ustar format HEADER. */
36static unsigned int
37calculate_chksum (const struct ustar_header *h)
38{
39 const uint8_t *header = (const uint8_t *) h;
40 unsigned int chksum;
41 size_t i;
42
43 chksum = 0;
44 for (i = 0; i < USTAR_HEADER_SIZE; i++)
45 {
46 /* The ustar checksum is calculated as if the chksum field
47 were all spaces. */
48 const size_t chksum_start = offsetof (struct ustar_header, chksum);
49 const size_t chksum_end = chksum_start + sizeof h->chksum;
50 bool in_chksum_field = i >= chksum_start && i < chksum_end;
51 chksum += in_chksum_field ? ' ' : header[i];
52 }
53 return chksum;
54}
55
56/* Drop possibly dangerous prefixes from FILE_NAME and return the
57 stripped name. An archive with file names that start with "/"
58 or "../" could cause a naive tar extractor to write to
59 arbitrary parts of the file system, not just the destination
60 directory. We don't want to create such archives or be such a
61 naive extractor.
62
63 The return value can be a suffix of FILE_NAME or a string
64 literal. */
65static const char *
66strip_antisocial_prefixes (const char *file_name)
67{
68 while (*file_name == '/'
69 || !memcmp (file_name, "./", 2)
70 || !memcmp (file_name, "../", 3))
71 file_name = strchr (file_name, '/') + 1;
72 return *file_name == '\0' || !strcmp (file_name, "..") ? "." : file_name;
73}
74
75/* Composes HEADER as a USTAR_HEADER_SIZE (512)-byte archive
76 header in ustar format for a SIZE-byte file named FILE_NAME of
77 the given TYPE. The caller is responsible for writing the
78 header to a file or device.
79
80 If successful, returns true. On failure (due to an
81 excessively long file name), returns false. */
82bool
83ustar_make_header (const char *file_name, enum ustar_type type,
84 int size, char header[USTAR_HEADER_SIZE])
85{
86 struct ustar_header *h = (struct ustar_header *) header;
87
88 ASSERT (sizeof (struct ustar_header) == USTAR_HEADER_SIZE);
89 ASSERT (type == USTAR_REGULAR || type == USTAR_DIRECTORY);
90
91 /* Check file name. */
92 file_name = strip_antisocial_prefixes (file_name);
93 if (strlen (file_name) > 99)
94 {
95 printf ("%s: file name too long\n", file_name);
96 return false;
97 }
98
99 /* Fill in header except for final checksum. */
100 memset (h, 0, sizeof *h);
101 strlcpy (h->name, file_name, sizeof h->name);
102 snprintf (h->mode, sizeof h->mode, "%07o",
103 type == USTAR_REGULAR ? 0644 : 0755);
104 strlcpy (h->uid, "0000000", sizeof h->uid);
105 strlcpy (h->gid, "0000000", sizeof h->gid);
106 snprintf (h->size, sizeof h->size, "%011o", size);
107 snprintf (h->mtime, sizeof h->size, "%011o", 1136102400);
108 h->typeflag = type;
109 strlcpy (h->magic, "ustar", sizeof h->magic);
110 h->version[0] = h->version[1] = '0';
111 strlcpy (h->gname, "root", sizeof h->gname);
112 strlcpy (h->uname, "root", sizeof h->uname);
113
114 /* Compute and fill in final checksum. */
115 snprintf (h->chksum, sizeof h->chksum, "%07o", calculate_chksum (h));
116
117 return true;
118}
119
120/* Parses a SIZE-byte octal field in S in the format used by
121 ustar format. If successful, stores the field's value in
122 *VALUE and returns true; on failure, returns false.
123
124 ustar octal fields consist of a sequence of octal digits
125 terminated by a space or a null byte. The ustar specification
126 seems ambiguous as to whether these fields must be padded on
127 the left with '0's, so we accept any field that fits in the
128 available space, regardless of whether it fills the space. */
129static bool
130parse_octal_field (const char *s, size_t size, unsigned long int *value)
131{
132 size_t ofs;
133
134 *value = 0;
135 for (ofs = 0; ofs < size; ofs++)
136 {
137 char c = s[ofs];
138 if (c >= '0' && c <= '7')
139 {
140 if (*value > ULONG_MAX / 8)
141 {
142 /* Overflow. */
143 return false;
144 }
145 *value = c - '0' + *value * 8;
146 }
147 else if (c == ' ' || c == '\0')
148 {
149 /* End of field, but disallow completely empty
150 fields. */
151 return ofs > 0;
152 }
153 else
154 {
155 /* Bad character. */
156 return false;
157 }
158 }
159
160 /* Field did not end in space or null byte. */
161 return false;
162}
163
164/* Returns true if the CNT bytes starting at BLOCK are all zero,
165 false otherwise. */
166static bool
167is_all_zeros (const char *block, size_t cnt)
168{
169 while (cnt-- > 0)
170 if (*block++ != 0)
171 return false;
172 return true;
173}
174
175/* Parses HEADER as a ustar-format archive header for a regular
176 file or directory. If successful, stores the archived file's
177 name in *FILE_NAME (as a pointer into HEADER or a string
178 literal), its type in *TYPE, and its size in bytes in *SIZE,
179 and returns a null pointer. On failure, returns a
180 human-readable error message. */
181const char *
182ustar_parse_header (const char header[USTAR_HEADER_SIZE],
183 const char **file_name, enum ustar_type *type, int *size)
184{
185 const struct ustar_header *h = (const struct ustar_header *) header;
186 unsigned long int chksum, size_ul;
187
188 ASSERT (sizeof (struct ustar_header) == USTAR_HEADER_SIZE);
189
190 /* Detect end of archive. */
191 if (is_all_zeros (header, USTAR_HEADER_SIZE))
192 {
193 *file_name = NULL;
194 *type = USTAR_EOF;
195 *size = 0;
196 return NULL;
197 }
198
199 /* Validate ustar header. */
200 if (memcmp (h->magic, "ustar", 6))
201 return "not a ustar archive";
202 else if (h->version[0] != '0' || h->version[1] != '0')
203 return "invalid ustar version";
204 else if (!parse_octal_field (h->chksum, sizeof h->chksum, &chksum))
205 return "corrupt chksum field";
206 else if (chksum != calculate_chksum (h))
207 return "checksum mismatch";
208 else if (h->name[sizeof h->name - 1] != '\0' || h->prefix[0] != '\0')
209 return "file name too long";
210 else if (h->typeflag != USTAR_REGULAR && h->typeflag != USTAR_DIRECTORY)
211 return "unimplemented file type";
212 if (h->typeflag == USTAR_REGULAR)
213 {
214 if (!parse_octal_field (h->size, sizeof h->size, &size_ul))
215 return "corrupt file size field";
216 else if (size_ul > INT_MAX)
217 return "file too large";
218 }
219 else
220 size_ul = 0;
221
222 /* Success. */
223 *file_name = strip_antisocial_prefixes (h->name);
224 *type = h->typeflag;
225 *size = size_ul;
226 return NULL;
227}
228
diff --git a/pintos-progos/lib/ustar.h b/pintos-progos/lib/ustar.h
new file mode 100644
index 0000000..43a5513
--- /dev/null
+++ b/pintos-progos/lib/ustar.h
@@ -0,0 +1,29 @@
1#ifndef __LIB_USTAR_H
2#define __LIB_USTAR_H
3
4/* Support for the standard Posix "ustar" format. See the
5 documentation of the "pax" utility in [SUSv3] for the the
6 "ustar" format specification. */
7
8#include <stdbool.h>
9
10/* Type of a file entry in an archive.
11 The values here are the bytes that appear in the file format.
12 Only types of interest to Pintos are listed here. */
13enum ustar_type
14 {
15 USTAR_REGULAR = '0', /* Ordinary file. */
16 USTAR_DIRECTORY = '5', /* Directory. */
17 USTAR_EOF = -1 /* End of archive (not an official value). */
18 };
19
20/* Size of a ustar archive header, in bytes. */
21#define USTAR_HEADER_SIZE 512
22
23bool ustar_make_header (const char *file_name, enum ustar_type,
24 int size, char header[USTAR_HEADER_SIZE]);
25const char *ustar_parse_header (const char header[USTAR_HEADER_SIZE],
26 const char **file_name,
27 enum ustar_type *, int *size);
28
29#endif /* lib/ustar.h */
generated by cgit v1.2.3 (git 2.25.1) at 2026-01-11 20:31:28 +0000