summaryrefslogtreecommitdiffstats
path: root/pintos-progos/threads
diff options
context:
space:
mode:
Diffstat (limited to 'pintos-progos/threads')
-rw-r--r--pintos-progos/threads/.gitignore3
-rw-r--r--pintos-progos/threads/Make.vars7
-rw-r--r--pintos-progos/threads/Makefile1
-rw-r--r--pintos-progos/threads/flags.h8
-rw-r--r--pintos-progos/threads/init.c453
-rw-r--r--pintos-progos/threads/init.h12
-rw-r--r--pintos-progos/threads/interrupt.c438
-rw-r--r--pintos-progos/threads/interrupt.h70
-rw-r--r--pintos-progos/threads/intr-stubs.S203
-rw-r--r--pintos-progos/threads/intr-stubs.h19
-rw-r--r--pintos-progos/threads/io.h115
-rw-r--r--pintos-progos/threads/kernel.lds.S30
-rw-r--r--pintos-progos/threads/loader.S263
-rw-r--r--pintos-progos/threads/loader.h40
-rw-r--r--pintos-progos/threads/malloc.c294
-rw-r--r--pintos-progos/threads/malloc.h13
-rw-r--r--pintos-progos/threads/palloc.c199
-rw-r--r--pintos-progos/threads/palloc.h20
-rw-r--r--pintos-progos/threads/pte.h107
-rw-r--r--pintos-progos/threads/start.S204
-rw-r--r--pintos-progos/threads/switch.S65
-rw-r--r--pintos-progos/threads/switch.h39
-rw-r--r--pintos-progos/threads/synch.c338
-rw-r--r--pintos-progos/threads/synch.h51
-rw-r--r--pintos-progos/threads/thread.c594
-rw-r--r--pintos-progos/threads/thread.h144
-rw-r--r--pintos-progos/threads/vaddr.h89
27 files changed, 3819 insertions, 0 deletions
diff --git a/pintos-progos/threads/.gitignore b/pintos-progos/threads/.gitignore
new file mode 100644
index 0000000..6d5357c
--- /dev/null
+++ b/pintos-progos/threads/.gitignore
@@ -0,0 +1,3 @@
1build
2bochsrc.txt
3bochsout.txt
diff --git a/pintos-progos/threads/Make.vars b/pintos-progos/threads/Make.vars
new file mode 100644
index 0000000..310c240
--- /dev/null
+++ b/pintos-progos/threads/Make.vars
@@ -0,0 +1,7 @@
1# -*- makefile -*-
2
3kernel.bin: DEFINES =
4KERNEL_SUBDIRS = threads devices lib lib/kernel $(TEST_SUBDIRS)
5TEST_SUBDIRS = tests/threads
6GRADING_FILE = $(SRCDIR)/tests/threads/Grading
7SIMULATOR = --bochs
diff --git a/pintos-progos/threads/Makefile b/pintos-progos/threads/Makefile
new file mode 100644
index 0000000..34c10aa
--- /dev/null
+++ b/pintos-progos/threads/Makefile
@@ -0,0 +1 @@
include ../Makefile.kernel
diff --git a/pintos-progos/threads/flags.h b/pintos-progos/threads/flags.h
new file mode 100644
index 0000000..5654ac7
--- /dev/null
+++ b/pintos-progos/threads/flags.h
@@ -0,0 +1,8 @@
1#ifndef THREADS_FLAGS_H
2#define THREADS_FLAGS_H
3
4/* EFLAGS Register. */
5#define FLAG_MBS 0x00000002 /* Must be set. */
6#define FLAG_IF 0x00000200 /* Interrupt Flag. */
7
8#endif /* threads/flags.h */
diff --git a/pintos-progos/threads/init.c b/pintos-progos/threads/init.c
new file mode 100644
index 0000000..d8feacd
--- /dev/null
+++ b/pintos-progos/threads/init.c
@@ -0,0 +1,453 @@
1#include "threads/init.h"
2#include <console.h>
3#include <debug.h>
4#include <inttypes.h>
5#include <limits.h>
6#include <random.h>
7#include <stddef.h>
8#include <stdio.h>
9#include <stdlib.h>
10#include <string.h>
11#include "devices/kbd.h"
12#include "devices/input.h"
13#include "devices/serial.h"
14#include "devices/shutdown.h"
15#include "devices/timer.h"
16#include "devices/vga.h"
17#include "devices/rtc.h"
18#include "threads/interrupt.h"
19#include "threads/io.h"
20#include "threads/loader.h"
21#include "threads/malloc.h"
22#include "threads/palloc.h"
23#include "threads/pte.h"
24#include "threads/thread.h"
25#ifdef USERPROG
26#include "userprog/process.h"
27#include "userprog/exception.h"
28#include "userprog/gdt.h"
29#include "userprog/syscall.h"
30#include "userprog/tss.h"
31#else
32#include "tests/threads/tests.h"
33#endif
34#ifdef FILESYS
35#include "devices/block.h"
36#include "devices/ide.h"
37#include "filesys/filesys.h"
38#include "filesys/fsutil.h"
39#endif
40
41
42/* Page directory with kernel mappings only. */
43uint32_t *init_page_dir;
44
45#ifdef FILESYS
46/* -f: Format the file system? */
47static bool format_filesys;
48
49/* -filesys, -scratch, -swap: Names of block devices to use,
50 overriding the defaults. */
51static const char *filesys_bdev_name;
52static const char *scratch_bdev_name;
53#ifdef VM
54static const char *swap_bdev_name;
55#endif
56#endif /* FILESYS */
57
58/* -kernel-test: Run kernel test instead of user program */
59static bool kernel_test = false;
60
61/* provide weak kernel test definition if no test is available */
62void run_test (const char *param);
63__attribute__((weak))
64void
65run_test (const char *param UNUSED)
66{
67 printf("No kernel test linked into kernel\n");
68}
69
70
71/* -ul: Maximum number of pages to put into palloc's user pool. */
72static size_t user_page_limit = SIZE_MAX;
73
74static void bss_init (void);
75static void paging_init (void);
76
77static char **read_command_line (void);
78static char **parse_options (char **argv);
79static void run_actions (char **argv);
80static void usage (void);
81
82#ifdef FILESYS
83static void locate_block_devices (void);
84static void locate_block_device (enum block_type, const char *name);
85#endif
86
87int main (void) NO_RETURN;
88
89/* Pintos main program. */
90int
91main (void)
92{
93 char **argv;
94
95 /* Clear BSS. */
96 bss_init ();
97
98 /* Break command line into arguments and parse options. */
99 argv = read_command_line ();
100 argv = parse_options (argv);
101
102 /* Initialize ourselves as a thread so we can use locks,
103 then enable console locking. */
104 thread_init ();
105 console_init ();
106
107 /* Greet user. */
108 printf ("Pintos booting with %'"PRIu32" kB RAM...\n",
109 init_ram_pages * PGSIZE / 1024);
110
111 /* Initialize memory system. */
112 palloc_init (user_page_limit);
113 malloc_init ();
114 paging_init ();
115
116 /* Segmentation. */
117#ifdef USERPROG
118 tss_init ();
119 gdt_init ();
120#endif
121
122 /* Initialize interrupt handlers. */
123 intr_init ();
124 timer_init ();
125 kbd_init ();
126 input_init ();
127#ifdef USERPROG
128 exception_init ();
129 syscall_init ();
130#endif
131
132 /* Start thread scheduler and enable interrupts. */
133 thread_start ();
134 serial_init_queue ();
135 timer_calibrate ();
136
137#ifdef FILESYS
138 /* Initialize file system. */
139 ide_init ();
140 locate_block_devices ();
141 /* kernel tests do not need filesystem */
142 if (!kernel_test)
143 filesys_init (format_filesys);
144#endif
145
146 printf ("Boot complete.\n");
147
148 /* Run actions specified on kernel command line. */
149 run_actions (argv);
150
151 /* Finish up. */
152 shutdown ();
153 thread_exit ();
154}
155
156/* Clear the "BSS", a segment that should be initialized to
157 zeros. It isn't actually stored on disk or zeroed by the
158 kernel loader, so we have to zero it ourselves.
159
160 The start and end of the BSS segment is recorded by the
161 linker as _start_bss and _end_bss. See kernel.lds. */
162static void
163bss_init (void)
164{
165 extern char _start_bss, _end_bss;
166 memset (&_start_bss, 0, &_end_bss - &_start_bss);
167}
168
169/* Populates the base page directory and page table with the
170 kernel virtual mapping, and then sets up the CPU to use the
171 new page directory. Points init_page_dir to the page
172 directory it creates. */
173static void
174paging_init (void)
175{
176 uint32_t *pd, *pt;
177 size_t page;
178 extern char _start, _end_kernel_text;
179
180 pd = init_page_dir = palloc_get_page (PAL_ASSERT | PAL_ZERO);
181 pt = NULL;
182 for (page = 0; page < init_ram_pages; page++)
183 {
184 uintptr_t paddr = page * PGSIZE;
185 char *vaddr = ptov (paddr);
186 size_t pde_idx = pd_no (vaddr);
187 size_t pte_idx = pt_no (vaddr);
188 bool in_kernel_text = &_start <= vaddr && vaddr < &_end_kernel_text;
189
190 if (pd[pde_idx] == 0)
191 {
192 pt = palloc_get_page (PAL_ASSERT | PAL_ZERO);
193 pd[pde_idx] = pde_create (pt);
194 }
195
196 pt[pte_idx] = pte_create_kernel (vaddr, !in_kernel_text);
197 }
198
199 /* Store the physical address of the page directory into CR3
200 aka PDBR (page directory base register). This activates our
201 new page tables immediately. See [IA32-v2a] "MOV--Move
202 to/from Control Registers" and [IA32-v3a] 3.7.5 "Base Address
203 of the Page Directory". */
204 asm volatile ("movl %0, %%cr3" : : "r" (vtop (init_page_dir)));
205}
206
207/* Breaks the kernel command line into words and returns them as
208 an argv-like array. */
209static char **
210read_command_line (void)
211{
212 static char *argv[LOADER_ARGS_LEN / 2 + 1];
213 char *p, *end;
214 int argc;
215 int i;
216
217 argc = *(uint32_t *) ptov (LOADER_ARG_CNT);
218 p = ptov (LOADER_ARGS);
219 end = p + LOADER_ARGS_LEN;
220 for (i = 0; i < argc; i++)
221 {
222 if (p >= end)
223 PANIC ("command line arguments overflow");
224
225 argv[i] = p;
226 p += strnlen (p, end - p) + 1;
227 }
228 argv[argc] = NULL;
229
230 /* Print kernel command line. */
231 printf ("Kernel command line:");
232 for (i = 0; i < argc; i++)
233 if (strchr (argv[i], ' ') == NULL)
234 printf (" %s", argv[i]);
235 else
236 printf (" '%s'", argv[i]);
237 printf ("\n");
238
239 return argv;
240}
241
242/* Parses options in ARGV[]
243 and returns the first non-option argument. */
244static char **
245parse_options (char **argv)
246{
247 for (; *argv != NULL && **argv == '-'; argv++)
248 {
249 char *save_ptr;
250 char *name = strtok_r (*argv, "=", &save_ptr);
251 char *value = strtok_r (NULL, "", &save_ptr);
252
253#ifndef USERPROG
254 kernel_test = true;
255#endif
256 if (!strcmp (name, "-h"))
257 usage ();
258 else if (!strcmp (name, "-q"))
259 shutdown_configure (SHUTDOWN_POWER_OFF);
260 else if (!strcmp (name, "-r"))
261 shutdown_configure (SHUTDOWN_REBOOT);
262#ifdef FILESYS
263 else if (!strcmp (name, "-f"))
264 format_filesys = true;
265 else if (!strcmp (name, "-filesys"))
266 filesys_bdev_name = value;
267 else if (!strcmp (name, "-scratch"))
268 scratch_bdev_name = value;
269#ifdef VM
270 else if (!strcmp (name, "-swap"))
271 swap_bdev_name = value;
272#endif
273#endif
274 else if (!strcmp (name, "-rs"))
275 random_init (atoi (value));
276 else if (!strcmp (name, "-mlfqs"))
277 thread_mlfqs = true;
278#ifdef USERPROG
279 else if (!strcmp (name, "-kernel-test"))
280 kernel_test = true;
281 else if (!strcmp (name, "-ul"))
282 user_page_limit = atoi (value);
283#endif
284 else
285 PANIC ("unknown option `%s' (use -h for help)", name);
286 }
287
288 /* Initialize the random number generator based on the system
289 time. This has no effect if an "-rs" option was specified.
290
291 When running under Bochs, this is not enough by itself to
292 get a good seed value, because the pintos script sets the
293 initial time to a predictable value, not to the local time,
294 for reproducibility. To fix this, give the "-r" option to
295 the pintos script to request real-time execution. */
296 random_init (rtc_get_time ());
297
298 return argv;
299}
300
301/* Runs the task specified in ARGV[1]. */
302static void
303run_task (char **argv)
304{
305 const char *task = argv[1];
306
307 printf ("Executing '%s':\n", task);
308#ifdef USERPROG
309 if (kernel_test)
310 run_test (task);
311 else
312 process_wait (process_execute (task));
313#else
314 run_test (task);
315#endif
316 printf ("Execution of '%s' complete.\n", task);
317}
318
319/* Executes all of the actions specified in ARGV[]
320 up to the null pointer sentinel. */
321static void
322run_actions (char **argv)
323{
324 /* An action. */
325 struct action
326 {
327 char *name; /* Action name. */
328 int argc; /* # of args, including action name. */
329 void (*function) (char **argv); /* Function to execute action. */
330 };
331
332 /* Table of supported actions. */
333 static const struct action actions[] =
334 {
335 {"run", 2, run_task},
336#ifdef FILESYS
337 {"ls", 1, fsutil_ls},
338 {"cat", 2, fsutil_cat},
339 {"rm", 2, fsutil_rm},
340 {"extract", 1, fsutil_extract},
341 {"append", 2, fsutil_append},
342#endif
343 {NULL, 0, NULL},
344 };
345
346 while (*argv != NULL)
347 {
348 const struct action *a;
349 int i;
350
351 /* Find action name. */
352 for (a = actions; ; a++)
353 if (a->name == NULL)
354 PANIC ("unknown action `%s' (use -h for help)", *argv);
355 else if (!strcmp (*argv, a->name))
356 break;
357
358 /* Check for required arguments. */
359 for (i = 1; i < a->argc; i++)
360 if (argv[i] == NULL)
361 PANIC ("action `%s' requires %d argument(s)", *argv, a->argc - 1);
362
363 /* Invoke action and advance. */
364 a->function (argv);
365 argv += a->argc;
366 }
367
368}
369
370/* Prints a kernel command line help message and powers off the
371 machine. */
372static void
373usage (void)
374{
375 printf ("\nCommand line syntax: [OPTION...] [ACTION...]\n"
376 "Options must precede actions.\n"
377 "Actions are executed in the order specified.\n"
378 "\nAvailable actions:\n"
379#ifdef USERPROG
380 " run 'PROG [ARG...]' Run PROG and wait for it to complete.\n"
381#else
382 " run TEST Run TEST.\n"
383#endif
384#ifdef FILESYS
385 " ls List files in the root directory.\n"
386 " cat FILE Print FILE to the console.\n"
387 " rm FILE Delete FILE.\n"
388 "Use these actions indirectly via `pintos' -g and -p options:\n"
389 " extract Untar from scratch device into file system.\n"
390 " append FILE Append FILE to tar file on scratch device.\n"
391#endif
392 "\nOptions:\n"
393 " -h Print this help message and power off.\n"
394 " -q Power off VM after actions or on panic.\n"
395 " -r Reboot after actions.\n"
396#ifdef FILESYS
397 " -f Format file system device during startup.\n"
398 " -filesys=BDEV Use BDEV for file system instead of default.\n"
399 " -scratch=BDEV Use BDEV for scratch instead of default.\n"
400#ifdef VM
401 " -swap=BDEV Use BDEV for swap instead of default.\n"
402#endif
403#endif
404 " -rs=SEED Set random number seed to SEED.\n"
405 " -mlfqs Use multi-level feedback queue scheduler.\n"
406#ifdef USERPROG
407 " -ul=COUNT Limit user memory to COUNT pages.\n"
408#endif
409 );
410 shutdown_power_off ();
411}
412
413#ifdef FILESYS
414/* Figure out what block devices to cast in the various Pintos roles. */
415static void
416locate_block_devices (void)
417{
418 locate_block_device (BLOCK_FILESYS, filesys_bdev_name);
419 locate_block_device (BLOCK_SCRATCH, scratch_bdev_name);
420#ifdef VM
421 locate_block_device (BLOCK_SWAP, swap_bdev_name);
422#endif
423}
424
425/* Figures out what block device to use for the given ROLE: the
426 block device with the given NAME, if NAME is non-null,
427 otherwise the first block device in probe order of type
428 ROLE. */
429static void
430locate_block_device (enum block_type role, const char *name)
431{
432 struct block *block = NULL;
433
434 if (name != NULL)
435 {
436 block = block_get_by_name (name);
437 if (block == NULL)
438 PANIC ("No such block device \"%s\"", name);
439 }
440 else
441 {
442 for (block = block_first (); block != NULL; block = block_next (block))
443 if (block_type (block) == role)
444 break;
445 }
446
447 if (block != NULL)
448 {
449 printf ("%s: using %s\n", block_type_name (role), block_name (block));
450 block_set_role (role, block);
451 }
452}
453#endif
diff --git a/pintos-progos/threads/init.h b/pintos-progos/threads/init.h
new file mode 100644
index 0000000..8a3df90
--- /dev/null
+++ b/pintos-progos/threads/init.h
@@ -0,0 +1,12 @@
1#ifndef THREADS_INIT_H
2#define THREADS_INIT_H
3
4#include <debug.h>
5#include <stdbool.h>
6#include <stddef.h>
7#include <stdint.h>
8
9/* Page directory with kernel mappings only. */
10extern uint32_t *init_page_dir;
11
12#endif /* threads/init.h */
diff --git a/pintos-progos/threads/interrupt.c b/pintos-progos/threads/interrupt.c
new file mode 100644
index 0000000..e3b90dc
--- /dev/null
+++ b/pintos-progos/threads/interrupt.c
@@ -0,0 +1,438 @@
1#include "threads/interrupt.h"
2#include <debug.h>
3#include <inttypes.h>
4#include <stdint.h>
5#include <stdio.h>
6#include "threads/flags.h"
7#include "threads/intr-stubs.h"
8#include "threads/io.h"
9#include "threads/thread.h"
10#include "threads/vaddr.h"
11#include "devices/timer.h"
12
13/* Programmable Interrupt Controller (PIC) registers.
14 A PC has two PICs, called the master and slave PICs, with the
15 slave attached ("cascaded") to the master IRQ line 2. */
16#define PIC0_CTRL 0x20 /* Master PIC control register address. */
17#define PIC0_DATA 0x21 /* Master PIC data register address. */
18#define PIC1_CTRL 0xa0 /* Slave PIC control register address. */
19#define PIC1_DATA 0xa1 /* Slave PIC data register address. */
20
21/* Number of x86 interrupts. */
22#define INTR_CNT 256
23
24/* The Interrupt Descriptor Table (IDT). The format is fixed by
25 the CPU. See [IA32-v3a] sections 5.10 "Interrupt Descriptor
26 Table (IDT)", 5.11 "IDT Descriptors", 5.12.1.2 "Flag Usage By
27 Exception- or Interrupt-Handler Procedure". */
28static uint64_t idt[INTR_CNT];
29
30/* Interrupt handler functions for each interrupt. */
31static intr_handler_func *intr_handlers[INTR_CNT];
32
33/* Names for each interrupt, for debugging purposes. */
34static const char *intr_names[INTR_CNT];
35
36/* Number of unexpected interrupts for each vector. An
37 unexpected interrupt is one that has no registered handler. */
38static unsigned int unexpected_cnt[INTR_CNT];
39
40/* External interrupts are those generated by devices outside the
41 CPU, such as the timer. External interrupts run with
42 interrupts turned off, so they never nest, nor are they ever
43 pre-empted. Handlers for external interrupts also may not
44 sleep, although they may invoke intr_yield_on_return() to
45 request that a new process be scheduled just before the
46 interrupt returns. */
47static bool in_external_intr; /* Are we processing an external interrupt? */
48static bool yield_on_return; /* Should we yield on interrupt return? */
49
50/* Programmable Interrupt Controller helpers. */
51static void pic_init (void);
52static void pic_end_of_interrupt (int irq);
53
54/* Interrupt Descriptor Table helpers. */
55static uint64_t make_intr_gate (void (*) (void), int dpl);
56static uint64_t make_trap_gate (void (*) (void), int dpl);
57static inline uint64_t make_idtr_operand (uint16_t limit, void *base);
58
59/* Interrupt handlers. */
60void intr_handler (struct intr_frame *args);
61static void unexpected_interrupt (const struct intr_frame *);
62
63/* Returns the current interrupt status. */
64enum intr_level
65intr_get_level (void)
66{
67 uint32_t flags;
68
69 /* Push the flags register on the processor stack, then pop the
70 value off the stack into `flags'. See [IA32-v2b] "PUSHF"
71 and "POP" and [IA32-v3a] 5.8.1 "Masking Maskable Hardware
72 Interrupts". */
73 asm volatile ("pushfl; popl %0" : "=g" (flags));
74
75 return flags & FLAG_IF ? INTR_ON : INTR_OFF;
76}
77
78/* Enables or disables interrupts as specified by LEVEL and
79 returns the previous interrupt status. */
80enum intr_level
81intr_set_level (enum intr_level level)
82{
83 return level == INTR_ON ? intr_enable () : intr_disable ();
84}
85
86/* Enables interrupts and returns the previous interrupt status. */
87enum intr_level
88intr_enable (void)
89{
90 enum intr_level old_level = intr_get_level ();
91 ASSERT (!intr_context ());
92
93 /* Enable interrupts by setting the interrupt flag.
94
95 See [IA32-v2b] "STI" and [IA32-v3a] 5.8.1 "Masking Maskable
96 Hardware Interrupts". */
97 asm volatile ("sti");
98
99 return old_level;
100}
101
102/* Disables interrupts and returns the previous interrupt status. */
103enum intr_level
104intr_disable (void)
105{
106 enum intr_level old_level = intr_get_level ();
107
108 /* Disable interrupts by clearing the interrupt flag.
109 See [IA32-v2b] "CLI" and [IA32-v3a] 5.8.1 "Masking Maskable
110 Hardware Interrupts". */
111 asm volatile ("cli" : : : "memory");
112
113 return old_level;
114}
115
116/* Initializes the interrupt system. */
117void
118intr_init (void)
119{
120 uint64_t idtr_operand;
121 int i;
122
123 /* Initialize interrupt controller. */
124 pic_init ();
125
126 /* Initialize IDT. */
127 for (i = 0; i < INTR_CNT; i++)
128 idt[i] = make_intr_gate (intr_stubs[i], 0);
129
130 /* Load IDT register.
131 See [IA32-v2a] "LIDT" and [IA32-v3a] 5.10 "Interrupt
132 Descriptor Table (IDT)". */
133 idtr_operand = make_idtr_operand (sizeof idt - 1, idt);
134 asm volatile ("lidt %0" : : "m" (idtr_operand));
135
136 /* Initialize intr_names. */
137 for (i = 0; i < INTR_CNT; i++)
138 intr_names[i] = "unknown";
139 intr_names[0] = "#DE Divide Error";
140 intr_names[1] = "#DB Debug Exception";
141 intr_names[2] = "NMI Interrupt";
142 intr_names[3] = "#BP Breakpoint Exception";
143 intr_names[4] = "#OF Overflow Exception";
144 intr_names[5] = "#BR BOUND Range Exceeded Exception";
145 intr_names[6] = "#UD Invalid Opcode Exception";
146 intr_names[7] = "#NM Device Not Available Exception";
147 intr_names[8] = "#DF Double Fault Exception";
148 intr_names[9] = "Coprocessor Segment Overrun";
149 intr_names[10] = "#TS Invalid TSS Exception";
150 intr_names[11] = "#NP Segment Not Present";
151 intr_names[12] = "#SS Stack Fault Exception";
152 intr_names[13] = "#GP General Protection Exception";
153 intr_names[14] = "#PF Page-Fault Exception";
154 intr_names[16] = "#MF x87 FPU Floating-Point Error";
155 intr_names[17] = "#AC Alignment Check Exception";
156 intr_names[18] = "#MC Machine-Check Exception";
157 intr_names[19] = "#XF SIMD Floating-Point Exception";
158}
159
160/* Registers interrupt VEC_NO to invoke HANDLER with descriptor
161 privilege level DPL. Names the interrupt NAME for debugging
162 purposes. The interrupt handler will be invoked with
163 interrupt status set to LEVEL. */
164static void
165register_handler (uint8_t vec_no, int dpl, enum intr_level level,
166 intr_handler_func *handler, const char *name)
167{
168 ASSERT (intr_handlers[vec_no] == NULL);
169 if (level == INTR_ON)
170 idt[vec_no] = make_trap_gate (intr_stubs[vec_no], dpl);
171 else
172 idt[vec_no] = make_intr_gate (intr_stubs[vec_no], dpl);
173 intr_handlers[vec_no] = handler;
174 intr_names[vec_no] = name;
175}
176
177/* Registers external interrupt VEC_NO to invoke HANDLER, which
178 is named NAME for debugging purposes. The handler will
179 execute with interrupts disabled. */
180void
181intr_register_ext (uint8_t vec_no, intr_handler_func *handler,
182 const char *name)
183{
184 ASSERT (vec_no >= 0x20 && vec_no <= 0x2f);
185 register_handler (vec_no, 0, INTR_OFF, handler, name);
186}
187
188/* Registers internal interrupt VEC_NO to invoke HANDLER, which
189 is named NAME for debugging purposes. The interrupt handler
190 will be invoked with interrupt status LEVEL.
191
192 The handler will have descriptor privilege level DPL, meaning
193 that it can be invoked intentionally when the processor is in
194 the DPL or lower-numbered ring. In practice, DPL==3 allows
195 user mode to invoke the interrupts and DPL==0 prevents such
196 invocation. Faults and exceptions that occur in user mode
197 still cause interrupts with DPL==0 to be invoked. See
198 [IA32-v3a] sections 4.5 "Privilege Levels" and 4.8.1.1
199 "Accessing Nonconforming Code Segments" for further
200 discussion. */
201void
202intr_register_int (uint8_t vec_no, int dpl, enum intr_level level,
203 intr_handler_func *handler, const char *name)
204{
205 ASSERT (vec_no < 0x20 || vec_no > 0x2f);
206 register_handler (vec_no, dpl, level, handler, name);
207}
208
209/* Returns true during processing of an external interrupt
210 and false at all other times. */
211bool
212intr_context (void)
213{
214 return in_external_intr;
215}
216
217/* During processing of an external interrupt, directs the
218 interrupt handler to yield to a new process just before
219 returning from the interrupt. May not be called at any other
220 time. */
221void
222intr_yield_on_return (void)
223{
224 ASSERT (intr_context ());
225 yield_on_return = true;
226}
227
228/* 8259A Programmable Interrupt Controller. */
229
230/* Initializes the PICs. Refer to [8259A] for details.
231
232 By default, interrupts 0...15 delivered by the PICs will go to
233 interrupt vectors 0...15. Those vectors are also used for CPU
234 traps and exceptions, so we reprogram the PICs so that
235 interrupts 0...15 are delivered to interrupt vectors 32...47
236 (0x20...0x2f) instead. */
237static void
238pic_init (void)
239{
240 /* Mask all interrupts on both PICs. */
241 outb (PIC0_DATA, 0xff);
242 outb (PIC1_DATA, 0xff);
243
244 /* Initialize master. */
245 outb (PIC0_CTRL, 0x11); /* ICW1: single mode, edge triggered, expect ICW4. */
246 outb (PIC0_DATA, 0x20); /* ICW2: line IR0...7 -> irq 0x20...0x27. */
247 outb (PIC0_DATA, 0x04); /* ICW3: slave PIC on line IR2. */
248 outb (PIC0_DATA, 0x01); /* ICW4: 8086 mode, normal EOI, non-buffered. */
249
250 /* Initialize slave. */
251 outb (PIC1_CTRL, 0x11); /* ICW1: single mode, edge triggered, expect ICW4. */
252 outb (PIC1_DATA, 0x28); /* ICW2: line IR0...7 -> irq 0x28...0x2f. */
253 outb (PIC1_DATA, 0x02); /* ICW3: slave ID is 2. */
254 outb (PIC1_DATA, 0x01); /* ICW4: 8086 mode, normal EOI, non-buffered. */
255
256 /* Unmask all interrupts. */
257 outb (PIC0_DATA, 0x00);
258 outb (PIC1_DATA, 0x00);
259}
260
261/* Sends an end-of-interrupt signal to the PIC for the given IRQ.
262 If we don't acknowledge the IRQ, it will never be delivered to
263 us again, so this is important. */
264static void
265pic_end_of_interrupt (int irq)
266{
267 ASSERT (irq >= 0x20 && irq < 0x30);
268
269 /* Acknowledge master PIC. */
270 outb (0x20, 0x20);
271
272 /* Acknowledge slave PIC if this is a slave interrupt. */
273 if (irq >= 0x28)
274 outb (0xa0, 0x20);
275}
276
277/* Creates an gate that invokes FUNCTION.
278
279 The gate has descriptor privilege level DPL, meaning that it
280 can be invoked intentionally when the processor is in the DPL
281 or lower-numbered ring. In practice, DPL==3 allows user mode
282 to call into the gate and DPL==0 prevents such calls. Faults
283 and exceptions that occur in user mode still cause gates with
284 DPL==0 to be invoked. See [IA32-v3a] sections 4.5 "Privilege
285 Levels" and 4.8.1.1 "Accessing Nonconforming Code Segments"
286 for further discussion.
287
288 TYPE must be either 14 (for an interrupt gate) or 15 (for a
289 trap gate). The difference is that entering an interrupt gate
290 disables interrupts, but entering a trap gate does not. See
291 [IA32-v3a] section 5.12.1.2 "Flag Usage By Exception- or
292 Interrupt-Handler Procedure" for discussion. */
293static uint64_t
294make_gate (void (*function) (void), int dpl, int type)
295{
296 uint32_t e0, e1;
297
298 ASSERT (function != NULL);
299 ASSERT (dpl >= 0 && dpl <= 3);
300 ASSERT (type >= 0 && type <= 15);
301
302 e0 = (((uint32_t) function & 0xffff) /* Offset 15:0. */
303 | (SEL_KCSEG << 16)); /* Target code segment. */
304
305 e1 = (((uint32_t) function & 0xffff0000) /* Offset 31:16. */
306 | (1 << 15) /* Present. */
307 | ((uint32_t) dpl << 13) /* Descriptor privilege level. */
308 | (0 << 12) /* System. */
309 | ((uint32_t) type << 8)); /* Gate type. */
310
311 return e0 | ((uint64_t) e1 << 32);
312}
313
314/* Creates an interrupt gate that invokes FUNCTION with the given
315 DPL. */
316static uint64_t
317make_intr_gate (void (*function) (void), int dpl)
318{
319 return make_gate (function, dpl, 14);
320}
321
322/* Creates a trap gate that invokes FUNCTION with the given
323 DPL. */
324static uint64_t
325make_trap_gate (void (*function) (void), int dpl)
326{
327 return make_gate (function, dpl, 15);
328}
329
330/* Returns a descriptor that yields the given LIMIT and BASE when
331 used as an operand for the LIDT instruction. */
332static inline uint64_t
333make_idtr_operand (uint16_t limit, void *base)
334{
335 return limit | ((uint64_t) (uint32_t) base << 16);
336}
337
338/* Interrupt handlers. */
339
340/* Handler for all interrupts, faults, and exceptions. This
341 function is called by the assembly language interrupt stubs in
342 intr-stubs.S. FRAME describes the interrupt and the
343 interrupted thread's registers. */
344void
345intr_handler (struct intr_frame *frame)
346{
347 bool external;
348 intr_handler_func *handler;
349
350 /* External interrupts are special.
351 We only handle one at a time (so interrupts must be off)
352 and they need to be acknowledged on the PIC (see below).
353 An external interrupt handler cannot sleep. */
354 external = frame->vec_no >= 0x20 && frame->vec_no < 0x30;
355 if (external)
356 {
357 ASSERT (intr_get_level () == INTR_OFF);
358 ASSERT (!intr_context ());
359
360 in_external_intr = true;
361 yield_on_return = false;
362 }
363
364 /* Invoke the interrupt's handler. */
365 handler = intr_handlers[frame->vec_no];
366 if (handler != NULL)
367 handler (frame);
368 else if (frame->vec_no == 0x27 || frame->vec_no == 0x2f)
369 {
370 /* There is no handler, but this interrupt can trigger
371 spuriously due to a hardware fault or hardware race
372 condition. Ignore it. */
373 }
374 else
375 unexpected_interrupt (frame);
376
377 /* Complete the processing of an external interrupt. */
378 if (external)
379 {
380 ASSERT (intr_get_level () == INTR_OFF);
381 ASSERT (intr_context ());
382
383 in_external_intr = false;
384 pic_end_of_interrupt (frame->vec_no);
385
386 if (yield_on_return)
387 thread_yield ();
388 }
389}
390
391/* Handles an unexpected interrupt with interrupt frame F. An
392 unexpected interrupt is one that has no registered handler. */
393static void
394unexpected_interrupt (const struct intr_frame *f)
395{
396 /* Count the number so far. */
397 unsigned int n = ++unexpected_cnt[f->vec_no];
398
399 /* If the number is a power of 2, print a message. This rate
400 limiting means that we get information about an uncommon
401 unexpected interrupt the first time and fairly often after
402 that, but one that occurs many times will not overwhelm the
403 console. */
404 if ((n & (n - 1)) == 0)
405 printf ("Unexpected interrupt %#04x (%s)\n",
406 f->vec_no, intr_names[f->vec_no]);
407}
408
409/* Dumps interrupt frame F to the console, for debugging. */
410void
411intr_dump_frame (const struct intr_frame *f)
412{
413 uint32_t cr2;
414
415 /* Store current value of CR2 into `cr2'.
416 CR2 is the linear address of the last page fault.
417 See [IA32-v2a] "MOV--Move to/from Control Registers" and
418 [IA32-v3a] 5.14 "Interrupt 14--Page Fault Exception
419 (#PF)". */
420 asm ("movl %%cr2, %0" : "=r" (cr2));
421
422 printf ("Interrupt %#04x (%s) at eip=%p\n",
423 f->vec_no, intr_names[f->vec_no], f->eip);
424 printf (" cr2=%08"PRIx32" error=%08"PRIx32"\n", cr2, f->error_code);
425 printf (" eax=%08"PRIx32" ebx=%08"PRIx32" ecx=%08"PRIx32" edx=%08"PRIx32"\n",
426 f->eax, f->ebx, f->ecx, f->edx);
427 printf (" esi=%08"PRIx32" edi=%08"PRIx32" esp=%08"PRIx32" ebp=%08"PRIx32"\n",
428 f->esi, f->edi, (uint32_t) f->esp, f->ebp);
429 printf (" cs=%04"PRIx16" ds=%04"PRIx16" es=%04"PRIx16" ss=%04"PRIx16"\n",
430 f->cs, f->ds, f->es, f->ss);
431}
432
433/* Returns the name of interrupt VEC. */
434const char *
435intr_name (uint8_t vec)
436{
437 return intr_names[vec];
438}
diff --git a/pintos-progos/threads/interrupt.h b/pintos-progos/threads/interrupt.h
new file mode 100644
index 0000000..d43e06d
--- /dev/null
+++ b/pintos-progos/threads/interrupt.h
@@ -0,0 +1,70 @@
1#ifndef THREADS_INTERRUPT_H
2#define THREADS_INTERRUPT_H
3
4#include <stdbool.h>
5#include <stdint.h>
6
7/* Interrupts on or off? */
8enum intr_level
9 {
10 INTR_OFF, /* Interrupts disabled. */
11 INTR_ON /* Interrupts enabled. */
12 };
13
14enum intr_level intr_get_level (void);
15enum intr_level intr_set_level (enum intr_level);
16enum intr_level intr_enable (void);
17enum intr_level intr_disable (void);
18
19/* Interrupt stack frame. */
20struct intr_frame
21 {
22 /* Pushed by intr_entry in intr-stubs.S.
23 These are the interrupted task's saved registers. */
24 uint32_t edi; /* Saved EDI. */
25 uint32_t esi; /* Saved ESI. */
26 uint32_t ebp; /* Saved EBP. */
27 uint32_t esp_dummy; /* Not used. */
28 uint32_t ebx; /* Saved EBX. */
29 uint32_t edx; /* Saved EDX. */
30 uint32_t ecx; /* Saved ECX. */
31 uint32_t eax; /* Saved EAX. */
32 uint16_t gs, :16; /* Saved GS segment register. */
33 uint16_t fs, :16; /* Saved FS segment register. */
34 uint16_t es, :16; /* Saved ES segment register. */
35 uint16_t ds, :16; /* Saved DS segment register. */
36
37 /* Pushed by intrNN_stub in intr-stubs.S. */
38 uint32_t vec_no; /* Interrupt vector number. */
39
40 /* Sometimes pushed by the CPU,
41 otherwise for consistency pushed as 0 by intrNN_stub.
42 The CPU puts it just under `eip', but we move it here. */
43 uint32_t error_code; /* Error code. */
44
45 /* Pushed by intrNN_stub in intr-stubs.S.
46 This frame pointer eases interpretation of backtraces. */
47 void *frame_pointer; /* Saved EBP (frame pointer). */
48
49 /* Pushed by the CPU.
50 These are the interrupted task's saved registers. */
51 void (*eip) (void); /* Next instruction to execute. */
52 uint16_t cs, :16; /* Code segment for eip. */
53 uint32_t eflags; /* Saved CPU flags. */
54 void *esp; /* Saved stack pointer. */
55 uint16_t ss, :16; /* Data segment for esp. */
56 };
57
58typedef void intr_handler_func (struct intr_frame *);
59
60void intr_init (void);
61void intr_register_ext (uint8_t vec, intr_handler_func *, const char *name);
62void intr_register_int (uint8_t vec, int dpl, enum intr_level,
63 intr_handler_func *, const char *name);
64bool intr_context (void);
65void intr_yield_on_return (void);
66
67void intr_dump_frame (const struct intr_frame *);
68const char *intr_name (uint8_t vec);
69
70#endif /* threads/interrupt.h */
diff --git a/pintos-progos/threads/intr-stubs.S b/pintos-progos/threads/intr-stubs.S
new file mode 100644
index 0000000..adb674e
--- /dev/null
+++ b/pintos-progos/threads/intr-stubs.S
@@ -0,0 +1,203 @@
1#include "threads/loader.h"
2
3 .text
4
5/* Main interrupt entry point.
6
7 An internal or external interrupt starts in one of the
8 intrNN_stub routines, which push the `struct intr_frame'
9 frame_pointer, error_code, and vec_no members on the stack,
10 then jump here.
11
12 We save the rest of the `struct intr_frame' members to the
13 stack, set up some registers as needed by the kernel, and then
14 call intr_handler(), which actually handles the interrupt.
15
16 We "fall through" to intr_exit to return from the interrupt.
17*/
18.func intr_entry
19intr_entry:
20 /* Save caller's registers. */
21 pushl %ds
22 pushl %es
23 pushl %fs
24 pushl %gs
25 pushal
26
27 /* Set up kernel environment. */
28 cld /* String instructions go upward. */
29 mov $SEL_KDSEG, %eax /* Initialize segment registers. */
30 mov %eax, %ds
31 mov %eax, %es
32 leal 56(%esp), %ebp /* Set up frame pointer. */
33
34 /* Call interrupt handler. */
35 pushl %esp
36.globl intr_handler
37 call intr_handler
38 addl $4, %esp
39.endfunc
40
41/* Interrupt exit.
42
43 Restores the caller's registers, discards extra data on the
44 stack, and returns to the caller.
45
46 This is a separate function because it is called directly when
47 we launch a new user process (see start_process() in
48 userprog/process.c). */
49.globl intr_exit
50.func intr_exit
51intr_exit:
52 /* Restore caller's registers. */
53 popal
54 popl %gs
55 popl %fs
56 popl %es
57 popl %ds
58
59 /* Discard `struct intr_frame' vec_no, error_code,
60 frame_pointer members. */
61 addl $12, %esp
62
63 /* Return to caller. */
64 iret
65.endfunc
66
67/* Interrupt stubs.
68
69 This defines 256 fragments of code, named `intr00_stub'
70 through `intrff_stub', each of which is used as the entry
71 point for the corresponding interrupt vector. It also puts
72 the address of each of these functions in the correct spot in
73 `intr_stubs', an array of function pointers.
74
75 Most of the stubs do this:
76
77 1. Push %ebp on the stack (frame_pointer in `struct intr_frame').
78
79 2. Push 0 on the stack (error_code).
80
81 3. Push the interrupt number on the stack (vec_no).
82
83 The CPU pushes an extra "error code" on the stack for a few
84 interrupts. Because we want %ebp to be where the error code
85 is, we follow a different path:
86
87 1. Push a duplicate copy of the error code on the stack.
88
89 2. Replace the original copy of the error code by %ebp.
90
91 3. Push the interrupt number on the stack. */
92
93 .data
94.globl intr_stubs
95intr_stubs:
96
97/* This implements steps 1 and 2, described above, in the common
98 case where we just push a 0 error code. */
99#define zero \
100 pushl %ebp; \
101 pushl $0
102
103/* This implements steps 1 and 2, described above, in the case
104 where the CPU already pushed an error code. */
105#define REAL \
106 pushl (%esp); \
107 movl %ebp, 4(%esp)
108
109/* Emits a stub for interrupt vector NUMBER.
110 TYPE is `zero', for the case where we push a 0 error code,
111 or `REAL', if the CPU pushes an error code for us. */
112#define STUB(NUMBER, TYPE) \
113 .text; \
114.func intr##NUMBER##_stub; \
115intr##NUMBER##_stub: \
116 TYPE; \
117 push $0x##NUMBER; \
118 jmp intr_entry; \
119.endfunc; \
120 \
121 .data; \
122 .long intr##NUMBER##_stub;
123
124/* All the stubs. */
125STUB(00, zero) STUB(01, zero) STUB(02, zero) STUB(03, zero)
126STUB(04, zero) STUB(05, zero) STUB(06, zero) STUB(07, zero)
127STUB(08, REAL) STUB(09, zero) STUB(0a, REAL) STUB(0b, REAL)
128STUB(0c, zero) STUB(0d, REAL) STUB(0e, REAL) STUB(0f, zero)
129
130STUB(10, zero) STUB(11, REAL) STUB(12, zero) STUB(13, zero)
131STUB(14, zero) STUB(15, zero) STUB(16, zero) STUB(17, zero)
132STUB(18, REAL) STUB(19, zero) STUB(1a, REAL) STUB(1b, REAL)
133STUB(1c, zero) STUB(1d, REAL) STUB(1e, REAL) STUB(1f, zero)
134
135STUB(20, zero) STUB(21, zero) STUB(22, zero) STUB(23, zero)
136STUB(24, zero) STUB(25, zero) STUB(26, zero) STUB(27, zero)
137STUB(28, zero) STUB(29, zero) STUB(2a, zero) STUB(2b, zero)
138STUB(2c, zero) STUB(2d, zero) STUB(2e, zero) STUB(2f, zero)
139
140STUB(30, zero) STUB(31, zero) STUB(32, zero) STUB(33, zero)
141STUB(34, zero) STUB(35, zero) STUB(36, zero) STUB(37, zero)
142STUB(38, zero) STUB(39, zero) STUB(3a, zero) STUB(3b, zero)
143STUB(3c, zero) STUB(3d, zero) STUB(3e, zero) STUB(3f, zero)
144
145STUB(40, zero) STUB(41, zero) STUB(42, zero) STUB(43, zero)
146STUB(44, zero) STUB(45, zero) STUB(46, zero) STUB(47, zero)
147STUB(48, zero) STUB(49, zero) STUB(4a, zero) STUB(4b, zero)
148STUB(4c, zero) STUB(4d, zero) STUB(4e, zero) STUB(4f, zero)
149
150STUB(50, zero) STUB(51, zero) STUB(52, zero) STUB(53, zero)
151STUB(54, zero) STUB(55, zero) STUB(56, zero) STUB(57, zero)
152STUB(58, zero) STUB(59, zero) STUB(5a, zero) STUB(5b, zero)
153STUB(5c, zero) STUB(5d, zero) STUB(5e, zero) STUB(5f, zero)
154
155STUB(60, zero) STUB(61, zero) STUB(62, zero) STUB(63, zero)
156STUB(64, zero) STUB(65, zero) STUB(66, zero) STUB(67, zero)
157STUB(68, zero) STUB(69, zero) STUB(6a, zero) STUB(6b, zero)
158STUB(6c, zero) STUB(6d, zero) STUB(6e, zero) STUB(6f, zero)
159
160STUB(70, zero) STUB(71, zero) STUB(72, zero) STUB(73, zero)
161STUB(74, zero) STUB(75, zero) STUB(76, zero) STUB(77, zero)
162STUB(78, zero) STUB(79, zero) STUB(7a, zero) STUB(7b, zero)
163STUB(7c, zero) STUB(7d, zero) STUB(7e, zero) STUB(7f, zero)
164
165STUB(80, zero) STUB(81, zero) STUB(82, zero) STUB(83, zero)
166STUB(84, zero) STUB(85, zero) STUB(86, zero) STUB(87, zero)
167STUB(88, zero) STUB(89, zero) STUB(8a, zero) STUB(8b, zero)
168STUB(8c, zero) STUB(8d, zero) STUB(8e, zero) STUB(8f, zero)
169
170STUB(90, zero) STUB(91, zero) STUB(92, zero) STUB(93, zero)
171STUB(94, zero) STUB(95, zero) STUB(96, zero) STUB(97, zero)
172STUB(98, zero) STUB(99, zero) STUB(9a, zero) STUB(9b, zero)
173STUB(9c, zero) STUB(9d, zero) STUB(9e, zero) STUB(9f, zero)
174
175STUB(a0, zero) STUB(a1, zero) STUB(a2, zero) STUB(a3, zero)
176STUB(a4, zero) STUB(a5, zero) STUB(a6, zero) STUB(a7, zero)
177STUB(a8, zero) STUB(a9, zero) STUB(aa, zero) STUB(ab, zero)
178STUB(ac, zero) STUB(ad, zero) STUB(ae, zero) STUB(af, zero)
179
180STUB(b0, zero) STUB(b1, zero) STUB(b2, zero) STUB(b3, zero)
181STUB(b4, zero) STUB(b5, zero) STUB(b6, zero) STUB(b7, zero)
182STUB(b8, zero) STUB(b9, zero) STUB(ba, zero) STUB(bb, zero)
183STUB(bc, zero) STUB(bd, zero) STUB(be, zero) STUB(bf, zero)
184
185STUB(c0, zero) STUB(c1, zero) STUB(c2, zero) STUB(c3, zero)
186STUB(c4, zero) STUB(c5, zero) STUB(c6, zero) STUB(c7, zero)
187STUB(c8, zero) STUB(c9, zero) STUB(ca, zero) STUB(cb, zero)
188STUB(cc, zero) STUB(cd, zero) STUB(ce, zero) STUB(cf, zero)
189
190STUB(d0, zero) STUB(d1, zero) STUB(d2, zero) STUB(d3, zero)
191STUB(d4, zero) STUB(d5, zero) STUB(d6, zero) STUB(d7, zero)
192STUB(d8, zero) STUB(d9, zero) STUB(da, zero) STUB(db, zero)
193STUB(dc, zero) STUB(dd, zero) STUB(de, zero) STUB(df, zero)
194
195STUB(e0, zero) STUB(e1, zero) STUB(e2, zero) STUB(e3, zero)
196STUB(e4, zero) STUB(e5, zero) STUB(e6, zero) STUB(e7, zero)
197STUB(e8, zero) STUB(e9, zero) STUB(ea, zero) STUB(eb, zero)
198STUB(ec, zero) STUB(ed, zero) STUB(ee, zero) STUB(ef, zero)
199
200STUB(f0, zero) STUB(f1, zero) STUB(f2, zero) STUB(f3, zero)
201STUB(f4, zero) STUB(f5, zero) STUB(f6, zero) STUB(f7, zero)
202STUB(f8, zero) STUB(f9, zero) STUB(fa, zero) STUB(fb, zero)
203STUB(fc, zero) STUB(fd, zero) STUB(fe, zero) STUB(ff, zero)
diff --git a/pintos-progos/threads/intr-stubs.h b/pintos-progos/threads/intr-stubs.h
new file mode 100644
index 0000000..9ceba15
--- /dev/null
+++ b/pintos-progos/threads/intr-stubs.h
@@ -0,0 +1,19 @@
1#ifndef THREADS_INTR_STUBS_H
2#define THREADS_INTR_STUBS_H
3
4/* Interrupt stubs.
5
6 These are little snippets of code in intr-stubs.S, one for
7 each of the 256 possible x86 interrupts. Each one does a
8 little bit of stack manipulation, then jumps to intr_entry().
9 See intr-stubs.S for more information.
10
11 This array points to each of the interrupt stub entry points
12 so that intr_init() can easily find them. */
13typedef void intr_stub_func (void);
14extern intr_stub_func *intr_stubs[256];
15
16/* Interrupt return path. */
17void intr_exit (void);
18
19#endif /* threads/intr-stubs.h */
diff --git a/pintos-progos/threads/io.h b/pintos-progos/threads/io.h
new file mode 100644
index 0000000..30d52da
--- /dev/null
+++ b/pintos-progos/threads/io.h
@@ -0,0 +1,115 @@
1#ifndef THREADS_IO_H
2#define THREADS_IO_H
3
4#include <stddef.h>
5#include <stdint.h>
6
7/* Reads and returns a byte from PORT. */
8static inline uint8_t
9inb (uint16_t port)
10{
11 /* See [IA32-v2a] "IN". */
12 uint8_t data;
13 asm volatile ("inb %w1, %b0" : "=a" (data) : "Nd" (port));
14 return data;
15}
16
17/* Reads CNT bytes from PORT, one after another, and stores them
18 into the buffer starting at ADDR. */
19static inline void
20insb (uint16_t port, void *addr, size_t cnt)
21{
22 /* See [IA32-v2a] "INS". */
23 asm volatile ("rep insb" : "+D" (addr), "+c" (cnt) : "d" (port) : "memory");
24}
25
26/* Reads and returns 16 bits from PORT. */
27static inline uint16_t
28inw (uint16_t port)
29{
30 uint16_t data;
31 /* See [IA32-v2a] "IN". */
32 asm volatile ("inw %w1, %w0" : "=a" (data) : "Nd" (port));
33 return data;
34}
35
36/* Reads CNT 16-bit (halfword) units from PORT, one after
37 another, and stores them into the buffer starting at ADDR. */
38static inline void
39insw (uint16_t port, void *addr, size_t cnt)
40{
41 /* See [IA32-v2a] "INS". */
42 asm volatile ("rep insw" : "+D" (addr), "+c" (cnt) : "d" (port) : "memory");
43}
44
45/* Reads and returns 32 bits from PORT. */
46static inline uint32_t
47inl (uint16_t port)
48{
49 /* See [IA32-v2a] "IN". */
50 uint32_t data;
51 asm volatile ("inl %w1, %0" : "=a" (data) : "Nd" (port));
52 return data;
53}
54
55/* Reads CNT 32-bit (word) units from PORT, one after another,
56 and stores them into the buffer starting at ADDR. */
57static inline void
58insl (uint16_t port, void *addr, size_t cnt)
59{
60 /* See [IA32-v2a] "INS". */
61 asm volatile ("rep insl" : "+D" (addr), "+c" (cnt) : "d" (port) : "memory");
62}
63
64/* Writes byte DATA to PORT. */
65static inline void
66outb (uint16_t port, uint8_t data)
67{
68 /* See [IA32-v2b] "OUT". */
69 asm volatile ("outb %b0, %w1" : : "a" (data), "Nd" (port));
70}
71
72/* Writes to PORT each byte of data in the CNT-byte buffer
73 starting at ADDR. */
74static inline void
75outsb (uint16_t port, const void *addr, size_t cnt)
76{
77 /* See [IA32-v2b] "OUTS". */
78 asm volatile ("rep outsb" : "+S" (addr), "+c" (cnt) : "d" (port));
79}
80
81/* Writes the 16-bit DATA to PORT. */
82static inline void
83outw (uint16_t port, uint16_t data)
84{
85 /* See [IA32-v2b] "OUT". */
86 asm volatile ("outw %w0, %w1" : : "a" (data), "Nd" (port));
87}
88
89/* Writes to PORT each 16-bit unit (halfword) of data in the
90 CNT-halfword buffer starting at ADDR. */
91static inline void
92outsw (uint16_t port, const void *addr, size_t cnt)
93{
94 /* See [IA32-v2b] "OUTS". */
95 asm volatile ("rep outsw" : "+S" (addr), "+c" (cnt) : "d" (port));
96}
97
98/* Writes the 32-bit DATA to PORT. */
99static inline void
100outl (uint16_t port, uint32_t data)
101{
102 /* See [IA32-v2b] "OUT". */
103 asm volatile ("outl %0, %w1" : : "a" (data), "Nd" (port));
104}
105
106/* Writes to PORT each 32-bit unit (word) of data in the CNT-word
107 buffer starting at ADDR. */
108static inline void
109outsl (uint16_t port, const void *addr, size_t cnt)
110{
111 /* See [IA32-v2b] "OUTS". */
112 asm volatile ("rep outsl" : "+S" (addr), "+c" (cnt) : "d" (port));
113}
114
115#endif /* threads/io.h */
diff --git a/pintos-progos/threads/kernel.lds.S b/pintos-progos/threads/kernel.lds.S
new file mode 100644
index 0000000..19082d5
--- /dev/null
+++ b/pintos-progos/threads/kernel.lds.S
@@ -0,0 +1,30 @@
1#include "threads/loader.h"
2
3OUTPUT_FORMAT("elf32-i386")
4OUTPUT_ARCH("i386")
5ENTRY(start) /* Kernel starts at "start" symbol. */
6SECTIONS
7{
8 /* Specify the kernel base address. */
9 _start = LOADER_PHYS_BASE + LOADER_KERN_BASE;
10
11 /* Make room for the ELF headers. */
12 . = _start + SIZEOF_HEADERS;
13
14 /* Kernel starts with code, followed by read-only data and writable data. */
15 .text : { *(.start) *(.text) } = 0x90
16 .rodata : { *(.rodata) *(.rodata.*)
17 . = ALIGN(0x1000);
18 _end_kernel_text = .; }
19 .data : { *(.data)
20 _signature = .; LONG(0xaa55aa55) }
21
22 /* BSS (zero-initialized data) is after everything else. */
23 _start_bss = .;
24 .bss : { *(.bss) }
25 _end_bss = .;
26
27 _end = .;
28
29 ASSERT (_end - _start <= 512K, "Kernel image is too big.")
30}
diff --git a/pintos-progos/threads/loader.S b/pintos-progos/threads/loader.S
new file mode 100644
index 0000000..dd87ea1
--- /dev/null
+++ b/pintos-progos/threads/loader.S
@@ -0,0 +1,263 @@
1#include "threads/loader.h"
2
3#### Kernel loader.
4
5#### This code should be stored in the first sector of a hard disk.
6#### When the BIOS runs, it loads this code at physical address
7#### 0x7c00-0x7e00 (512 bytes) and jumps to the beginning of it,
8#### in real mode. The loader loads the kernel into memory and jumps
9#### to its entry point, which is the start function in start.S.
10####
11#### The BIOS passes in the drive that the loader was read from as
12#### DL, with floppy drives numbered 0x00, 0x01, ... and hard drives
13#### numbered 0x80, 0x81, ... We want to support booting a kernel on
14#### a different drive from the loader, so we don't take advantage of
15#### this.
16
17# Runs in real mode, which is a 16-bit segment.
18 .code16
19
20# Set up segment registers.
21# Set stack to grow downward from 60 kB (after boot, the kernel
22# continues to use this stack for its initial thread).
23
24 sub %ax, %ax
25 mov %ax, %ds
26 mov %ax, %ss
27 mov $0xf000, %esp
28
29# Configure serial port so we can report progress without connected VGA.
30# See [IntrList] for details.
31 sub %dx, %dx # Serial port 0.
32 mov $0xe3, %al # 9600 bps, N-8-1.
33 # AH is already 0 (Initialize Port).
34 int $0x14 # Destroys AX.
35
36 call puts
37 .string "PiLo"
38
39#### Read the partition table on each system hard disk and scan for a
40#### partition of type 0x20, which is the type that we use for a
41#### Pintos kernel.
42####
43#### Read [Partitions] for a description of the partition table format
44#### that we parse.
45####
46#### We print out status messages to show the disk and partition being
47#### scanned, e.g. hda1234 as we scan four partitions on the first
48#### hard disk.
49
50 mov $0x80, %dl # Hard disk 0.
51read_mbr:
52 sub %ebx, %ebx # Sector 0.
53 mov $0x2000, %ax # Use 0x20000 for buffer.
54 mov %ax, %es
55 call read_sector
56 jc no_such_drive
57
58 # Print hd[a-z].
59 call puts
60 .string " hd"
61 mov %dl, %al
62 add $'a' - 0x80, %al
63 call putc
64
65 # Check for MBR signature--if not present, it's not a
66 # partitioned hard disk.
67 cmpw $0xaa55, %es:510
68 jne next_drive
69
70 mov $446, %si # Offset of partition table entry 1.
71 mov $'1', %al
72check_partition:
73 # Is it an unused partition?
74 cmpl $0, %es:(%si)
75 je next_partition
76
77 # Print [1-4].
78 call putc
79
80 # Is it a Pintos kernel partition?
81 cmpb $0x20, %es:4(%si)
82 jne next_partition
83
84 # Is it a bootable partition?
85 cmpb $0x80, %es:(%si)
86 je load_kernel
87
88next_partition:
89 # No match for this partition, go on to the next one.
90 add $16, %si # Offset to next partition table entry.
91 inc %al
92 cmp $510, %si
93 jb check_partition
94
95next_drive:
96 # No match on this drive, go on to the next one.
97 inc %dl
98 jnc read_mbr
99
100no_such_drive:
101no_boot_partition:
102 # Didn't find a Pintos kernel partition anywhere, give up.
103 call puts
104 .string "\rNot found\r"
105
106 # Notify BIOS that boot failed. See [IntrList].
107 int $0x18
108
109#### We found a kernel. The kernel's drive is in DL. The partition
110#### table entry for the kernel's partition is at ES:SI. Our job now
111#### is to read the kernel from disk and jump to its start address.
112
113load_kernel:
114 call puts
115 .string "\rLoading"
116
117 # Figure out number of sectors to read. A Pintos kernel is
118 # just an ELF format object, which doesn't have an
119 # easy-to-read field to identify its own size (see [ELF1]).
120 # But we limit Pintos kernels to 512 kB for other reasons, so
121 # it's easy enough to just read the entire contents of the
122 # partition or 512 kB from disk, whichever is smaller.
123 mov %es:12(%si), %ecx # EBP = number of sectors
124 cmp $1024, %ecx # Cap size at 512 kB
125 jbe 1f
126 mov $1024, %cx
1271:
128
129 mov %es:8(%si), %ebx # EBX = first sector
130 mov $0x2000, %ax # Start load address: 0x20000
131
132next_sector:
133 # Read one sector into memory.
134 mov %ax, %es # ES:0000 -> load address
135 call read_sector
136 jc read_failed
137
138 # Print '.' as progress indicator once every 16 sectors == 8 kB.
139 test $15, %bl
140 jnz 1f
141 call puts
142 .string "."
1431:
144
145 # Advance memory pointer and disk sector.
146 add $0x20, %ax
147 inc %bx
148 loop next_sector
149
150 call puts
151 .string "\r"
152
153#### Transfer control to the kernel that we loaded. We read the start
154#### address out of the ELF header (see [ELF1]) and convert it from a
155#### 32-bit linear address into a 16:16 segment:offset address for
156#### real mode, then jump to the converted address. The 80x86 doesn't
157#### have an instruction to jump to an absolute segment:offset kept in
158#### registers, so in fact we store the address in a temporary memory
159#### location, then jump indirectly through that location. To save 4
160#### bytes in the loader, we reuse 4 bytes of the loader's code for
161#### this temporary pointer.
162
163 mov $0x2000, %ax
164 mov %ax, %es
165 mov %es:0x18, %dx
166 mov %dx, start
167 movw $0x2000, start + 2
168 ljmp *start
169
170read_failed:
171start:
172 # Disk sector read failed.
173 call puts
1741: .string "\rBad read\r"
175
176 # Notify BIOS that boot failed. See [IntrList].
177 int $0x18
178
179#### Print string subroutine. To save space in the loader, this
180#### subroutine takes its null-terminated string argument from the
181#### code stream just after the call, and then returns to the byte
182#### just after the terminating null. This subroutine preserves all
183#### general-purpose registers.
184
185puts: xchg %si, %ss:(%esp)
186 push %ax
187next_char:
188 mov %cs:(%si), %al
189 inc %si
190 test %al, %al
191 jz 1f
192 call putc
193 jmp next_char
1941: pop %ax
195 xchg %si, %ss:(%esp)
196 ret
197
198#### Character output subroutine. Prints the character in AL to the
199#### VGA display and serial port 0, using BIOS services (see
200#### [IntrList]). Preserves all general-purpose registers.
201####
202#### If called upon to output a carriage return, this subroutine
203#### automatically supplies the following line feed.
204
205putc: pusha
206
2071: sub %bh, %bh # Page 0.
208 mov $0x0e, %ah # Teletype output service.
209 int $0x10
210
211 mov $0x01, %ah # Serial port output service.
212 sub %dx, %dx # Serial port 0.
2132: int $0x14 # Destroys AH.
214 test $0x80, %ah # Output timed out?
215 jz 3f
216 movw $0x9090, 2b # Turn "int $0x14" above into NOPs.
217
2183:
219 cmp $'\r', %al
220 jne popa_ret
221 mov $'\n', %al
222 jmp 1b
223
224#### Sector read subroutine. Takes a drive number in DL (0x80 = hard
225#### disk 0, 0x81 = hard disk 1, ...) and a sector number in EBX, and
226#### reads the specified sector into memory at ES:0000. Returns with
227#### carry set on error, clear otherwise. Preserves all
228#### general-purpose registers.
229
230read_sector:
231 pusha
232 sub %ax, %ax
233 push %ax # LBA sector number [48:63]
234 push %ax # LBA sector number [32:47]
235 push %ebx # LBA sector number [0:31]
236 push %es # Buffer segment
237 push %ax # Buffer offset (always 0)
238 push $1 # Number of sectors to read
239 push $16 # Packet size
240 mov $0x42, %ah # Extended read
241 mov %sp, %si # DS:SI -> packet
242 int $0x13 # Error code in CF
243 popa # Pop 16 bytes, preserve flags
244popa_ret:
245 popa
246 ret # Error code still in CF
247
248#### Command-line arguments and their count.
249#### This is written by the `pintos' utility and read by the kernel.
250#### The loader itself does not do anything with the command line.
251 .org LOADER_ARG_CNT - LOADER_BASE
252 .fill LOADER_ARG_CNT_LEN, 1, 0
253
254 .org LOADER_ARGS - LOADER_BASE
255 .fill LOADER_ARGS_LEN, 1, 0
256
257#### Partition table.
258 .org LOADER_PARTS - LOADER_BASE
259 .fill LOADER_PARTS_LEN, 1, 0
260
261#### Boot-sector signature for BIOS inspection.
262 .org LOADER_SIG - LOADER_BASE
263 .word 0xaa55
diff --git a/pintos-progos/threads/loader.h b/pintos-progos/threads/loader.h
new file mode 100644
index 0000000..1bfe111
--- /dev/null
+++ b/pintos-progos/threads/loader.h
@@ -0,0 +1,40 @@
1#ifndef THREADS_LOADER_H
2#define THREADS_LOADER_H
3
4/* Constants fixed by the PC BIOS. */
5#define LOADER_BASE 0x7c00 /* Physical address of loader's base. */
6#define LOADER_END 0x7e00 /* Physical address of end of loader. */
7
8/* Physical address of kernel base. */
9#define LOADER_KERN_BASE 0x20000 /* 128 kB. */
10
11/* Kernel virtual address at which all physical memory is mapped.
12 Must be aligned on a 4 MB boundary. */
13#define LOADER_PHYS_BASE 0xc0000000 /* 3 GB. */
14
15/* Important loader physical addresses. */
16#define LOADER_SIG (LOADER_END - LOADER_SIG_LEN) /* 0xaa55 BIOS signature. */
17#define LOADER_PARTS (LOADER_SIG - LOADER_PARTS_LEN) /* Partition table. */
18#define LOADER_ARGS (LOADER_PARTS - LOADER_ARGS_LEN) /* Command-line args. */
19#define LOADER_ARG_CNT (LOADER_ARGS - LOADER_ARG_CNT_LEN) /* Number of args. */
20
21/* Sizes of loader data structures. */
22#define LOADER_SIG_LEN 2
23#define LOADER_PARTS_LEN 64
24#define LOADER_ARGS_LEN 128
25#define LOADER_ARG_CNT_LEN 4
26
27/* GDT selectors defined by loader.
28 More selectors are defined by userprog/gdt.h. */
29#define SEL_NULL 0x00 /* Null selector. */
30#define SEL_KCSEG 0x08 /* Kernel code selector. */
31#define SEL_KDSEG 0x10 /* Kernel data selector. */
32
33#ifndef __ASSEMBLER__
34#include <stdint.h>
35
36/* Amount of physical memory, in 4 kB pages. */
37extern uint32_t init_ram_pages;
38#endif
39
40#endif /* threads/loader.h */
diff --git a/pintos-progos/threads/malloc.c b/pintos-progos/threads/malloc.c
new file mode 100644
index 0000000..f6f803b
--- /dev/null
+++ b/pintos-progos/threads/malloc.c
@@ -0,0 +1,294 @@
1#include "threads/malloc.h"
2#include <debug.h>
3#include <list.h>
4#include <round.h>
5#include <stdint.h>
6#include <stdio.h>
7#include <string.h>
8#include "threads/palloc.h"
9#include "threads/synch.h"
10#include "threads/vaddr.h"
11
12/* A simple implementation of malloc().
13
14 The size of each request, in bytes, is rounded up to a power
15 of 2 and assigned to the "descriptor" that manages blocks of
16 that size. The descriptor keeps a list of free blocks. If
17 the free list is nonempty, one of its blocks is used to
18 satisfy the request.
19
20 Otherwise, a new page of memory, called an "arena", is
21 obtained from the page allocator (if none is available,
22 malloc() returns a null pointer). The new arena is divided
23 into blocks, all of which are added to the descriptor's free
24 list. Then we return one of the new blocks.
25
26 When we free a block, we add it to its descriptor's free list.
27 But if the arena that the block was in now has no in-use
28 blocks, we remove all of the arena's blocks from the free list
29 and give the arena back to the page allocator.
30
31 We can't handle blocks bigger than 2 kB using this scheme,
32 because they're too big to fit in a single page with a
33 descriptor. We handle those by allocating contiguous pages
34 with the page allocator and sticking the allocation size at
35 the beginning of the allocated block's arena header. */
36
37/* Descriptor. */
38struct desc
39 {
40 size_t block_size; /* Size of each element in bytes. */
41 size_t blocks_per_arena; /* Number of blocks in an arena. */
42 struct list free_list; /* List of free blocks. */
43 struct lock lock; /* Lock. */
44 };
45
46/* Magic number for detecting arena corruption. */
47#define ARENA_MAGIC 0x9a548eed
48
49/* Arena. */
50struct arena
51 {
52 unsigned magic; /* Always set to ARENA_MAGIC. */
53 struct desc *desc; /* Owning descriptor, null for big block. */
54 size_t free_cnt; /* Free blocks; pages in big block. */
55 };
56
57/* Free block. */
58struct block
59 {
60 struct list_elem free_elem; /* Free list element. */
61 };
62
63/* Our set of descriptors. */
64static struct desc descs[10]; /* Descriptors. */
65static size_t desc_cnt; /* Number of descriptors. */
66
67static struct arena *block_to_arena (struct block *);
68static struct block *arena_to_block (struct arena *, size_t idx);
69
70/* Initializes the malloc() descriptors. */
71void
72malloc_init (void)
73{
74 size_t block_size;
75
76 for (block_size = 16; block_size < PGSIZE / 2; block_size *= 2)
77 {
78 struct desc *d = &descs[desc_cnt++];
79 ASSERT (desc_cnt <= sizeof descs / sizeof *descs);
80 d->block_size = block_size;
81 d->blocks_per_arena = (PGSIZE - sizeof (struct arena)) / block_size;
82 list_init (&d->free_list);
83 lock_init (&d->lock);
84 }
85}
86
87/* Obtains and returns a new block of at least SIZE bytes.
88 Returns a null pointer if memory is not available. */
89void *
90malloc (size_t size)
91{
92 struct desc *d;
93 struct block *b;
94 struct arena *a;
95
96 /* A null pointer satisfies a request for 0 bytes. */
97 if (size == 0)
98 return NULL;
99
100 /* Find the smallest descriptor that satisfies a SIZE-byte
101 request. */
102 for (d = descs; d < descs + desc_cnt; d++)
103 if (d->block_size >= size)
104 break;
105 if (d == descs + desc_cnt)
106 {
107 /* SIZE is too big for any descriptor.
108 Allocate enough pages to hold SIZE plus an arena. */
109 size_t page_cnt = DIV_ROUND_UP (size + sizeof *a, PGSIZE);
110 a = palloc_get_multiple (0, page_cnt);
111 if (a == NULL)
112 return NULL;
113
114 /* Initialize the arena to indicate a big block of PAGE_CNT
115 pages, and return it. */
116 a->magic = ARENA_MAGIC;
117 a->desc = NULL;
118 a->free_cnt = page_cnt;
119 return a + 1;
120 }
121
122 lock_acquire (&d->lock);
123
124 /* If the free list is empty, create a new arena. */
125 if (list_empty (&d->free_list))
126 {
127 size_t i;
128
129 /* Allocate a page. */
130 a = palloc_get_page (0);
131 if (a == NULL)
132 {
133 lock_release (&d->lock);
134 return NULL;
135 }
136
137 /* Initialize arena and add its blocks to the free list. */
138 a->magic = ARENA_MAGIC;
139 a->desc = d;
140 a->free_cnt = d->blocks_per_arena;
141 for (i = 0; i < d->blocks_per_arena; i++)
142 {
143 struct block *b = arena_to_block (a, i);
144 list_push_back (&d->free_list, &b->free_elem);
145 }
146 }
147
148 /* Get a block from free list and return it. */
149 b = list_entry (list_pop_front (&d->free_list), struct block, free_elem);
150 a = block_to_arena (b);
151 a->free_cnt--;
152 lock_release (&d->lock);
153 return b;
154}
155
156/* Allocates and return A times B bytes initialized to zeroes.
157 Returns a null pointer if memory is not available. */
158void *
159calloc (size_t a, size_t b)
160{
161 void *p;
162 size_t size;
163
164 /* Calculate block size and make sure it fits in size_t. */
165 size = a * b;
166 if (size < a || size < b)
167 return NULL;
168
169 /* Allocate and zero memory. */
170 p = malloc (size);
171 if (p != NULL)
172 memset (p, 0, size);
173
174 return p;
175}
176
177/* Returns the number of bytes allocated for BLOCK. */
178static size_t
179block_size (void *block)
180{
181 struct block *b = block;
182 struct arena *a = block_to_arena (b);
183 struct desc *d = a->desc;
184
185 return d != NULL ? d->block_size : PGSIZE * a->free_cnt - pg_ofs (block);
186}
187
188/* Attempts to resize OLD_BLOCK to NEW_SIZE bytes, possibly
189 moving it in the process.
190 If successful, returns the new block; on failure, returns a
191 null pointer.
192 A call with null OLD_BLOCK is equivalent to malloc(NEW_SIZE).
193 A call with zero NEW_SIZE is equivalent to free(OLD_BLOCK). */
194void *
195realloc (void *old_block, size_t new_size)
196{
197 if (new_size == 0)
198 {
199 free (old_block);
200 return NULL;
201 }
202 else
203 {
204 void *new_block = malloc (new_size);
205 if (old_block != NULL && new_block != NULL)
206 {
207 size_t old_size = block_size (old_block);
208 size_t min_size = new_size < old_size ? new_size : old_size;
209 memcpy (new_block, old_block, min_size);
210 free (old_block);
211 }
212 return new_block;
213 }
214}
215
216/* Frees block P, which must have been previously allocated with
217 malloc(), calloc(), or realloc(). */
218void
219free (void *p)
220{
221 if (p != NULL)
222 {
223 struct block *b = p;
224 struct arena *a = block_to_arena (b);
225 struct desc *d = a->desc;
226
227 if (d != NULL)
228 {
229 /* It's a normal block. We handle it here. */
230
231#ifndef NDEBUG
232 /* Clear the block to help detect use-after-free bugs. */
233 memset (b, 0xcc, d->block_size);
234#endif
235
236 lock_acquire (&d->lock);
237
238 /* Add block to free list. */
239 list_push_front (&d->free_list, &b->free_elem);
240
241 /* If the arena is now entirely unused, free it. */
242 if (++a->free_cnt >= d->blocks_per_arena)
243 {
244 size_t i;
245
246 ASSERT (a->free_cnt == d->blocks_per_arena);
247 for (i = 0; i < d->blocks_per_arena; i++)
248 {
249 struct block *b = arena_to_block (a, i);
250 list_remove (&b->free_elem);
251 }
252 palloc_free_page (a);
253 }
254
255 lock_release (&d->lock);
256 }
257 else
258 {
259 /* It's a big block. Free its pages. */
260 palloc_free_multiple (a, a->free_cnt);
261 return;
262 }
263 }
264}
265
266/* Returns the arena that block B is inside. */
267static struct arena *
268block_to_arena (struct block *b)
269{
270 struct arena *a = pg_round_down (b);
271
272 /* Check that the arena is valid. */
273 ASSERT (a != NULL);
274 ASSERT (a->magic == ARENA_MAGIC);
275
276 /* Check that the block is properly aligned for the arena. */
277 ASSERT (a->desc == NULL
278 || (pg_ofs (b) - sizeof *a) % a->desc->block_size == 0);
279 ASSERT (a->desc != NULL || pg_ofs (b) == sizeof *a);
280
281 return a;
282}
283
284/* Returns the (IDX - 1)'th block within arena A. */
285static struct block *
286arena_to_block (struct arena *a, size_t idx)
287{
288 ASSERT (a != NULL);
289 ASSERT (a->magic == ARENA_MAGIC);
290 ASSERT (idx < a->desc->blocks_per_arena);
291 return (struct block *) ((uint8_t *) a
292 + sizeof *a
293 + idx * a->desc->block_size);
294}
diff --git a/pintos-progos/threads/malloc.h b/pintos-progos/threads/malloc.h
new file mode 100644
index 0000000..bc55d36
--- /dev/null
+++ b/pintos-progos/threads/malloc.h
@@ -0,0 +1,13 @@
1#ifndef THREADS_MALLOC_H
2#define THREADS_MALLOC_H
3
4#include <debug.h>
5#include <stddef.h>
6
7void malloc_init (void);
8void *malloc (size_t) __attribute__ ((malloc));
9void *calloc (size_t, size_t) __attribute__ ((malloc));
10void *realloc (void *, size_t);
11void free (void *);
12
13#endif /* threads/malloc.h */
diff --git a/pintos-progos/threads/palloc.c b/pintos-progos/threads/palloc.c
new file mode 100644
index 0000000..5c7ef2f
--- /dev/null
+++ b/pintos-progos/threads/palloc.c
@@ -0,0 +1,199 @@
1#include "threads/palloc.h"
2#include <bitmap.h>
3#include <debug.h>
4#include <inttypes.h>
5#include <round.h>
6#include <stddef.h>
7#include <stdint.h>
8#include <stdio.h>
9#include <string.h>
10#include "threads/loader.h"
11#include "threads/synch.h"
12#include "threads/vaddr.h"
13
14/* Page allocator. Hands out memory in page-size (or
15 page-multiple) chunks. See malloc.h for an allocator that
16 hands out smaller chunks.
17
18 System memory is divided into two "pools" called the kernel
19 and user pools. The user pool is for user (virtual) memory
20 pages, the kernel pool for everything else. The idea here is
21 that the kernel needs to have memory for its own operations
22 even if user processes are swapping like mad.
23
24 By default, half of system RAM is given to the kernel pool and
25 half to the user pool. That should be huge overkill for the
26 kernel pool, but that's just fine for demonstration purposes. */
27
28/* A memory pool. */
29struct pool
30 {
31 struct lock lock; /* Mutual exclusion. */
32 struct bitmap *used_map; /* Bitmap of free pages. */
33 uint8_t *base; /* Base of pool. */
34 };
35
36/* Two pools: one for kernel data, one for user pages. */
37static struct pool kernel_pool, user_pool;
38
39static void init_pool (struct pool *, void *base, size_t page_cnt,
40 const char *name);
41static bool page_from_pool (const struct pool *, void *page);
42
43/* Initializes the page allocator. At most USER_PAGE_LIMIT
44 pages are put into the user pool. */
45void
46palloc_init (size_t user_page_limit)
47{
48 /* Free memory starts at 1 MB and runs to the end of RAM. */
49 uint8_t *free_start = ptov (1024 * 1024);
50 uint8_t *free_end = ptov (init_ram_pages * PGSIZE);
51 size_t free_pages = (free_end - free_start) / PGSIZE;
52 size_t user_pages = free_pages / 2;
53 size_t kernel_pages;
54 if (user_pages > user_page_limit)
55 user_pages = user_page_limit;
56 kernel_pages = free_pages - user_pages;
57
58 /* Give half of memory to kernel, half to user. */
59 init_pool (&kernel_pool, free_start, kernel_pages, "kernel pool");
60 init_pool (&user_pool, free_start + kernel_pages * PGSIZE,
61 user_pages, "user pool");
62}
63
64/* Obtains and returns a group of PAGE_CNT contiguous free pages.
65 If PAL_USER is set, the pages are obtained from the user pool,
66 otherwise from the kernel pool. If PAL_ZERO is set in FLAGS,
67 then the pages are filled with zeros. If too few pages are
68 available, returns a null pointer, unless PAL_ASSERT is set in
69 FLAGS, in which case the kernel panics. */
70void *
71palloc_get_multiple (enum palloc_flags flags, size_t page_cnt)
72{
73 struct pool *pool = flags & PAL_USER ? &user_pool : &kernel_pool;
74 void *pages;
75 size_t page_idx;
76
77 if (page_cnt == 0)
78 return NULL;
79
80 lock_acquire (&pool->lock);
81 page_idx = bitmap_scan_and_flip (pool->used_map, 0, page_cnt, false);
82 lock_release (&pool->lock);
83
84 if (page_idx != BITMAP_ERROR)
85 pages = pool->base + PGSIZE * page_idx;
86 else
87 pages = NULL;
88
89 if (pages != NULL)
90 {
91 if (flags & PAL_ZERO)
92 memset (pages, 0, PGSIZE * page_cnt);
93 }
94 else
95 {
96 if (flags & PAL_ASSERT)
97 PANIC ("palloc_get: out of pages");
98 }
99
100 return pages;
101}
102
103/* Obtains a single free page and returns its kernel virtual
104 address.
105 If PAL_USER is set, the page is obtained from the user pool,
106 otherwise from the kernel pool. If PAL_ZERO is set in FLAGS,
107 then the page is filled with zeros. If no pages are
108 available, returns a null pointer, unless PAL_ASSERT is set in
109 FLAGS, in which case the kernel panics. */
110void *
111palloc_get_page (enum palloc_flags flags)
112{
113 return palloc_get_multiple (flags, 1);
114}
115
116/* Frees the PAGE_CNT pages starting at PAGES. */
117void
118palloc_free_multiple (void *pages, size_t page_cnt)
119{
120 struct pool *pool;
121 size_t page_idx;
122
123 ASSERT (pg_ofs (pages) == 0);
124 if (pages == NULL || page_cnt == 0)
125 return;
126
127 if (page_from_pool (&kernel_pool, pages))
128 pool = &kernel_pool;
129 else if (page_from_pool (&user_pool, pages))
130 pool = &user_pool;
131 else
132 NOT_REACHED ();
133
134 page_idx = pg_no (pages) - pg_no (pool->base);
135
136#ifndef NDEBUG
137 memset (pages, 0xcc, PGSIZE * page_cnt);
138#endif
139
140 ASSERT (bitmap_all (pool->used_map, page_idx, page_cnt));
141 bitmap_set_multiple (pool->used_map, page_idx, page_cnt, false);
142}
143
144/* Frees the page at PAGE. */
145void
146palloc_free_page (void *page)
147{
148 palloc_free_multiple (page, 1);
149}
150
151/* List all used pages */
152void
153palloc_dump_used_pages ()
154{
155 struct pool *pool;
156 int pool_index;
157 for (pool_index = 0; pool_index < 2; pool_index++) {
158 pool = (pool_index == 0) ? &kernel_pool : &user_pool;
159 printf("%s Pool at %p\n", (pool_index == 0) ? "kernel" : "user", pool->base);
160 size_t start = 0, index;
161 while ((index = bitmap_scan(pool->used_map,start,1,true)) != BITMAP_ERROR) {
162 printf(" - %p\n",pool->base + (PGSIZE * index));
163 start = index + 1;
164 }
165 }
166}
167
168/* Initializes pool P as starting at START and ending at END,
169 naming it NAME for debugging purposes. */
170static void
171init_pool (struct pool *p, void *base, size_t page_cnt, const char *name)
172{
173 /* We'll put the pool's used_map at its base.
174 Calculate the space needed for the bitmap
175 and subtract it from the pool's size. */
176 size_t bm_pages = DIV_ROUND_UP (bitmap_buf_size (page_cnt), PGSIZE);
177 if (bm_pages > page_cnt)
178 PANIC ("Not enough memory in %s for bitmap.", name);
179 page_cnt -= bm_pages;
180
181 printf ("%zu pages available in %s.\n", page_cnt, name);
182
183 /* Initialize the pool. */
184 lock_init (&p->lock);
185 p->used_map = bitmap_create_in_buf (page_cnt, base, bm_pages * PGSIZE);
186 p->base = base + bm_pages * PGSIZE;
187}
188
189/* Returns true if PAGE was allocated from POOL,
190 false otherwise. */
191static bool
192page_from_pool (const struct pool *pool, void *page)
193{
194 size_t page_no = pg_no (page);
195 size_t start_page = pg_no (pool->base);
196 size_t end_page = start_page + bitmap_size (pool->used_map);
197
198 return page_no >= start_page && page_no < end_page;
199}
diff --git a/pintos-progos/threads/palloc.h b/pintos-progos/threads/palloc.h
new file mode 100644
index 0000000..d7f4e0b
--- /dev/null
+++ b/pintos-progos/threads/palloc.h
@@ -0,0 +1,20 @@
1#ifndef THREADS_PALLOC_H
2#define THREADS_PALLOC_H
3
4#include <stddef.h>
5
6/* How to allocate pages. */
7enum palloc_flags
8 {
9 PAL_ASSERT = 001, /* Panic on failure. */
10 PAL_ZERO = 002, /* Zero page contents. */
11 PAL_USER = 004 /* User page. */
12 };
13void palloc_init (size_t user_page_limit);
14void *palloc_get_page (enum palloc_flags);
15void *palloc_get_multiple (enum palloc_flags, size_t page_cnt);
16void palloc_free_page (void *);
17void palloc_free_multiple (void *, size_t page_cnt);
18void palloc_dump_used_pages (void);
19
20#endif /* threads/palloc.h */
diff --git a/pintos-progos/threads/pte.h b/pintos-progos/threads/pte.h
new file mode 100644
index 0000000..1660727
--- /dev/null
+++ b/pintos-progos/threads/pte.h
@@ -0,0 +1,107 @@
1#ifndef THREADS_PTE_H
2#define THREADS_PTE_H
3
4#include "threads/vaddr.h"
5
6/* Functions and macros for working with x86 hardware page
7 tables.
8
9 See vaddr.h for more generic functions and macros for virtual
10 addresses.
11
12 Virtual addresses are structured as follows:
13
14 31 22 21 12 11 0
15 +----------------------+----------------------+----------------------+
16 | Page Directory Index | Page Table Index | Page Offset |
17 +----------------------+----------------------+----------------------+
18*/
19
20/* Page table index (bits 12:21). */
21#define PTSHIFT PGBITS /* First page table bit. */
22#define PTBITS 10 /* Number of page table bits. */
23#define PTSPAN (1 << PTBITS << PGBITS) /* Bytes covered by a page table. */
24#define PTMASK BITMASK(PTSHIFT, PTBITS) /* Page table bits (12:21). */
25
26/* Page directory index (bits 22:31). */
27#define PDSHIFT (PTSHIFT + PTBITS) /* First page directory bit. */
28#define PDBITS 10 /* Number of page dir bits. */
29#define PDMASK BITMASK(PDSHIFT, PDBITS) /* Page directory bits (22:31). */
30
31/* Obtains page table index from a virtual address. */
32static inline unsigned pt_no (const void *va) {
33 return ((uintptr_t) va & PTMASK) >> PTSHIFT;
34}
35
36/* Obtains page directory index from a virtual address. */
37static inline uintptr_t pd_no (const void *va) {
38 return (uintptr_t) va >> PDSHIFT;
39}
40
41/* Page directory and page table entries.
42
43 For more information see the section on page tables in the
44 Pintos reference guide chapter, or [IA32-v3a] 3.7.6
45 "Page-Directory and Page-Table Entries".
46
47 PDEs and PTEs share a common format:
48
49 31 12 11 0
50 +------------------------------------+------------------------+
51 | Physical Address | Flags |
52 +------------------------------------+------------------------+
53
54 In a PDE, the physical address points to a page table.
55 In a PTE, the physical address points to a data or code page.
56 The important flags are listed below.
57 When a PDE or PTE is not "present", the other flags are
58 ignored.
59 A PDE or PTE that is initialized to 0 will be interpreted as
60 "not present", which is just fine. */
61#define PTE_FLAGS 0x00000fff /* Flag bits. */
62#define PTE_ADDR 0xfffff000 /* Address bits. */
63#define PTE_AVL 0x00000e00 /* Bits available for OS use. */
64#define PTE_P 0x1 /* 1=present, 0=not present. */
65#define PTE_W 0x2 /* 1=read/write, 0=read-only. */
66#define PTE_U 0x4 /* 1=user/kernel, 0=kernel only. */
67#define PTE_A 0x20 /* 1=accessed, 0=not acccessed. */
68#define PTE_D 0x40 /* 1=dirty, 0=not dirty (PTEs only). */
69
70/* Returns a PDE that points to page table PT. */
71static inline uint32_t pde_create (uint32_t *pt) {
72 ASSERT (pg_ofs (pt) == 0);
73 return vtop (pt) | PTE_U | PTE_P | PTE_W;
74}
75
76/* Returns a pointer to the page table that page directory entry
77 PDE, which must "present", points to. */
78static inline uint32_t *pde_get_pt (uint32_t pde) {
79 ASSERT (pde & PTE_P);
80 return ptov (pde & PTE_ADDR);
81}
82
83/* Returns a PTE that points to PAGE.
84 The PTE's page is readable.
85 If WRITABLE is true then it will be writable as well.
86 The page will be usable only by ring 0 code (the kernel). */
87static inline uint32_t pte_create_kernel (void *page, bool writable) {
88 ASSERT (pg_ofs (page) == 0);
89 return vtop (page) | PTE_P | (writable ? PTE_W : 0);
90}
91
92/* Returns a PTE that points to PAGE.
93 The PTE's page is readable.
94 If WRITABLE is true then it will be writable as well.
95 The page will be usable by both user and kernel code. */
96static inline uint32_t pte_create_user (void *page, bool writable) {
97 return pte_create_kernel (page, writable) | PTE_U;
98}
99
100/* Returns a pointer to the page that page table entry PTE points
101 to. */
102static inline void *pte_get_page (uint32_t pte) {
103 return ptov (pte & PTE_ADDR);
104}
105
106#endif /* threads/pte.h */
107
diff --git a/pintos-progos/threads/start.S b/pintos-progos/threads/start.S
new file mode 100644
index 0000000..29ffa7a
--- /dev/null
+++ b/pintos-progos/threads/start.S
@@ -0,0 +1,204 @@
1 #include "threads/loader.h"
2
3#### Kernel startup code.
4
5#### The loader (in loader.S) loads the kernel at physical address
6#### 0x20000 (128 kB) and jumps to "start", defined here. This code
7#### switches from real mode to 32-bit protected mode and calls
8#### main().
9
10/* Flags in control register 0. */
11#define CR0_PE 0x00000001 /* Protection Enable. */
12#define CR0_EM 0x00000004 /* (Floating-point) Emulation. */
13#define CR0_PG 0x80000000 /* Paging. */
14#define CR0_WP 0x00010000 /* Write-Protect enable in kernel mode. */
15
16 .section .start
17
18# The following code runs in real mode, which is a 16-bit code segment.
19 .code16
20
21.func start
22.globl start
23start:
24
25# The loader called into us with CS = 0x2000, SS = 0x0000, ESP = 0xf000,
26# but we should initialize the other segment registers.
27
28 mov $0x2000, %ax
29 mov %ax, %ds
30 mov %ax, %es
31
32# Set string instructions to go upward.
33 cld
34
35#### Get memory size, via interrupt 15h function 88h (see [IntrList]),
36#### which returns AX = (kB of physical memory) - 1024. This only
37#### works for memory sizes <= 65 MB, which should be fine for our
38#### purposes. We cap memory at 64 MB because that's all we prepare
39#### page tables for, below.
40
41 movb $0x88, %ah
42 int $0x15
43 addl $1024, %eax # Total kB memory
44 cmp $0x10000, %eax # Cap at 64 MB
45 jbe 1f
46 mov $0x10000, %eax
471: shrl $2, %eax # Total 4 kB pages
48 addr32 movl %eax, init_ram_pages - LOADER_PHYS_BASE - 0x20000
49
50#### Enable A20. Address line 20 is tied low when the machine boots,
51#### which prevents addressing memory about 1 MB. This code fixes it.
52
53# Poll status register while busy.
54
551: inb $0x64, %al
56 testb $0x2, %al
57 jnz 1b
58
59# Send command for writing output port.
60
61 movb $0xd1, %al
62 outb %al, $0x64
63
64# Poll status register while busy.
65
661: inb $0x64, %al
67 testb $0x2, %al
68 jnz 1b
69
70# Enable A20 line.
71
72 movb $0xdf, %al
73 outb %al, $0x60
74
75# Poll status register while busy.
76
771: inb $0x64, %al
78 testb $0x2, %al
79 jnz 1b
80
81#### Create temporary page directory and page table and set page
82#### directory base register.
83
84# Create page directory at 0xf000 (60 kB) and fill with zeroes.
85 mov $0xf00, %ax
86 mov %ax, %es
87 subl %eax, %eax
88 subl %edi, %edi
89 movl $0x400, %ecx
90 rep stosl
91
92# Add PDEs to point to page tables for the first 64 MB of RAM.
93# Also add identical PDEs starting at LOADER_PHYS_BASE.
94# See [IA32-v3a] section 3.7.6 "Page-Directory and Page-Table Entries"
95# for a description of the bits in %eax.
96
97 movl $0x10007, %eax
98 movl $0x11, %ecx
99 subl %edi, %edi
1001: movl %eax, %es:(%di)
101 movl %eax, %es:LOADER_PHYS_BASE >> 20(%di)
102 addw $4, %di
103 addl $0x1000, %eax
104 loop 1b
105
106# Set up page tables for one-to-map linear to physical map for the
107# first 64 MB of RAM.
108# See [IA32-v3a] section 3.7.6 "Page-Directory and Page-Table Entries"
109# for a description of the bits in %eax.
110
111 movw $0x1000, %ax
112 movw %ax, %es
113 movl $0x7, %eax
114 movl $0x4000, %ecx
115 subl %edi, %edi
1161: movl %eax, %es:(%di)
117 addw $4, %di
118 addl $0x1000, %eax
119 loop 1b
120
121# Set page directory base register.
122
123 movl $0xf000, %eax
124 movl %eax, %cr3
125
126#### Switch to protected mode.
127
128# First, disable interrupts. We won't set up the IDT until we get
129# into C code, so any interrupt would blow us away.
130
131 cli
132
133# Protected mode requires a GDT, so point the GDTR to our GDT.
134# We need a data32 prefix to ensure that all 32 bits of the GDT
135# descriptor are loaded (default is to load only 24 bits).
136# The CPU doesn't need an addr32 prefix but ELF doesn't do 16-bit
137# relocations.
138
139 data32 addr32 lgdt gdtdesc - LOADER_PHYS_BASE - 0x20000
140
141# Then we turn on the following bits in CR0:
142# PE (Protect Enable): this turns on protected mode.
143# PG (Paging): turns on paging.
144# WP (Write Protect): if unset, ring 0 code ignores
145# write-protect bits in page tables (!).
146# EM (Emulation): forces floating-point instructions to trap.
147# We don't support floating point.
148
149 movl %cr0, %eax
150 orl $CR0_PE | CR0_PG | CR0_WP | CR0_EM, %eax
151 movl %eax, %cr0
152
153# We're now in protected mode in a 16-bit segment. The CPU still has
154# the real-mode code segment cached in %cs's segment descriptor. We
155# need to reload %cs, and the easiest way is to use a far jump.
156# Because we're not running in a 32-bit segment the data32 prefix is
157# needed to jump to a 32-bit offset in the target segment.
158
159 data32 ljmp $SEL_KCSEG, $1f
160
161# We're now in protected mode in a 32-bit segment.
162# Let the assembler know.
163
164 .code32
165
166# Reload all the other segment registers and the stack pointer to
167# point into our new GDT.
168
1691: mov $SEL_KDSEG, %ax
170 mov %ax, %ds
171 mov %ax, %es
172 mov %ax, %fs
173 mov %ax, %gs
174 mov %ax, %ss
175 addl $LOADER_PHYS_BASE, %esp
176 movl $0, %ebp # Null-terminate main()'s backtrace
177
178#### Call main().
179
180 call main
181
182# main() shouldn't ever return. If it does, spin.
183
1841: jmp 1b
185.endfunc
186
187#### GDT
188
189 .align 8
190gdt:
191 .quad 0x0000000000000000 # Null segment. Not used by CPU.
192 .quad 0x00cf9a000000ffff # System code, base 0, limit 4 GB.
193 .quad 0x00cf92000000ffff # System data, base 0, limit 4 GB.
194
195gdtdesc:
196 .word gdtdesc - gdt - 1 # Size of the GDT, minus 1 byte.
197 .long gdt # Address of the GDT.
198
199#### Physical memory size in 4 kB pages. This is exported to the rest
200#### of the kernel.
201.globl init_ram_pages
202init_ram_pages:
203 .long 0
204
diff --git a/pintos-progos/threads/switch.S b/pintos-progos/threads/switch.S
new file mode 100644
index 0000000..feca86c
--- /dev/null
+++ b/pintos-progos/threads/switch.S
@@ -0,0 +1,65 @@
1#include "threads/switch.h"
2
3#### struct thread *switch_threads (struct thread *cur, struct thread *next);
4####
5#### Switches from CUR, which must be the running thread, to NEXT,
6#### which must also be running switch_threads(), returning CUR in
7#### NEXT's context.
8####
9#### This function works by assuming that the thread we're switching
10#### into is also running switch_threads(). Thus, all it has to do is
11#### preserve a few registers on the stack, then switch stacks and
12#### restore the registers. As part of switching stacks we record the
13#### current stack pointer in CUR's thread structure.
14
15.globl switch_threads
16.func switch_threads
17switch_threads:
18 # Save caller's register state.
19 #
20 # Note that the SVR4 ABI allows us to destroy %eax, %ecx, %edx,
21 # but requires us to preserve %ebx, %ebp, %esi, %edi. See
22 # [SysV-ABI-386] pages 3-11 and 3-12 for details.
23 #
24 # This stack frame must match the one set up by thread_create()
25 # in size.
26 pushl %ebx
27 pushl %ebp
28 pushl %esi
29 pushl %edi
30
31 # Get offsetof (struct thread, stack).
32.globl thread_stack_ofs
33 mov thread_stack_ofs, %edx
34
35 # Save current stack pointer to old thread's stack, if any.
36 movl SWITCH_CUR(%esp), %eax
37 movl %esp, (%eax,%edx,1)
38
39 # Restore stack pointer from new thread's stack.
40 movl SWITCH_NEXT(%esp), %ecx
41 movl (%ecx,%edx,1), %esp
42
43 # Restore caller's register state.
44 popl %edi
45 popl %esi
46 popl %ebp
47 popl %ebx
48 ret
49.endfunc
50
51.globl switch_entry
52.func switch_entry
53switch_entry:
54 # Discard switch_threads() arguments.
55 addl $8, %esp
56
57 # Call thread_schedule_tail(prev).
58 pushl %eax
59.globl thread_schedule_tail
60 call thread_schedule_tail
61 addl $4, %esp
62
63 # Start thread proper.
64 ret
65.endfunc
diff --git a/pintos-progos/threads/switch.h b/pintos-progos/threads/switch.h
new file mode 100644
index 0000000..cc156b6
--- /dev/null
+++ b/pintos-progos/threads/switch.h
@@ -0,0 +1,39 @@
1#ifndef THREADS_SWITCH_H
2#define THREADS_SWITCH_H
3
4#ifndef __ASSEMBLER__
5/* switch_thread()'s stack frame. */
6struct switch_threads_frame
7 {
8 uint32_t edi; /* 0: Saved %edi. */
9 uint32_t esi; /* 4: Saved %esi. */
10 uint32_t ebp; /* 8: Saved %ebp. */
11 uint32_t ebx; /* 12: Saved %ebx. */
12 void (*eip) (void); /* 16: Return address. */
13 struct thread *cur; /* 20: switch_threads()'s CUR argument. */
14 struct thread *next; /* 24: switch_threads()'s NEXT argument. */
15 };
16
17/* Switches from CUR, which must be the running thread, to NEXT,
18 which must also be running switch_threads(), returning CUR in
19 NEXT's context. */
20struct thread *switch_threads (struct thread *cur, struct thread *next);
21
22/* Stack frame for switch_entry(). */
23struct switch_entry_frame
24 {
25 void (*eip) (void);
26 };
27
28void switch_entry (void);
29
30/* Pops the CUR and NEXT arguments off the stack, for use in
31 initializing threads. */
32void switch_thunk (void);
33#endif
34
35/* Offsets used by switch.S. */
36#define SWITCH_CUR 20
37#define SWITCH_NEXT 24
38
39#endif /* threads/switch.h */
diff --git a/pintos-progos/threads/synch.c b/pintos-progos/threads/synch.c
new file mode 100644
index 0000000..317c68a
--- /dev/null
+++ b/pintos-progos/threads/synch.c
@@ -0,0 +1,338 @@
1/* This file is derived from source code for the Nachos
2 instructional operating system. The Nachos copyright notice
3 is reproduced in full below. */
4
5/* Copyright (c) 1992-1996 The Regents of the University of California.
6 All rights reserved.
7
8 Permission to use, copy, modify, and distribute this software
9 and its documentation for any purpose, without fee, and
10 without written agreement is hereby granted, provided that the
11 above copyright notice and the following two paragraphs appear
12 in all copies of this software.
13
14 IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO
15 ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR
16 CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE
17 AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA
18 HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
19
20 THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY
21 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
22 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
23 PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS"
24 BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
25 PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
26 MODIFICATIONS.
27*/
28
29#include "threads/synch.h"
30#include <stdio.h>
31#include <string.h>
32#include "threads/interrupt.h"
33#include "threads/thread.h"
34
35/* Initializes semaphore SEMA to VALUE. A semaphore is a
36 nonnegative integer along with two atomic operators for
37 manipulating it:
38
39 - down or "P": wait for the value to become positive, then
40 decrement it.
41
42 - up or "V": increment the value (and wake up one waiting
43 thread, if any). */
44void
45sema_init (struct semaphore *sema, unsigned value)
46{
47 ASSERT (sema != NULL);
48
49 sema->value = value;
50 list_init (&sema->waiters);
51}
52
53/* Down or "P" operation on a semaphore. Waits for SEMA's value
54 to become positive and then atomically decrements it.
55
56 This function may sleep, so it must not be called within an
57 interrupt handler. This function may be called with
58 interrupts disabled, but if it sleeps then the next scheduled
59 thread will probably turn interrupts back on. */
60void
61sema_down (struct semaphore *sema)
62{
63 enum intr_level old_level;
64
65 ASSERT (sema != NULL);
66 ASSERT (!intr_context ());
67
68 old_level = intr_disable ();
69 while (sema->value == 0)
70 {
71 list_push_back (&sema->waiters, &thread_current ()->elem);
72 thread_block ();
73 }
74 sema->value--;
75 intr_set_level (old_level);
76}
77
78/* Down or "P" operation on a semaphore, but only if the
79 semaphore is not already 0. Returns true if the semaphore is
80 decremented, false otherwise.
81
82 This function may be called from an interrupt handler. */
83bool
84sema_try_down (struct semaphore *sema)
85{
86 enum intr_level old_level;
87 bool success;
88
89 ASSERT (sema != NULL);
90
91 old_level = intr_disable ();
92 if (sema->value > 0)
93 {
94 sema->value--;
95 success = true;
96 }
97 else
98 success = false;
99 intr_set_level (old_level);
100
101 return success;
102}
103
104/* Up or "V" operation on a semaphore. Increments SEMA's value
105 and wakes up one thread of those waiting for SEMA, if any.
106
107 This function may be called from an interrupt handler. */
108void
109sema_up (struct semaphore *sema)
110{
111 enum intr_level old_level;
112
113 ASSERT (sema != NULL);
114
115 old_level = intr_disable ();
116 if (!list_empty (&sema->waiters))
117 thread_unblock (list_entry (list_pop_front (&sema->waiters),
118 struct thread, elem));
119 sema->value++;
120 intr_set_level (old_level);
121}
122
123static void sema_test_helper (void *sema_);
124
125/* Self-test for semaphores that makes control "ping-pong"
126 between a pair of threads. Insert calls to printf() to see
127 what's going on. */
128void
129sema_self_test (void)
130{
131 struct semaphore sema[2];
132 int i;
133
134 printf ("Testing semaphores...");
135 sema_init (&sema[0], 0);
136 sema_init (&sema[1], 0);
137 thread_create ("sema-test", PRI_DEFAULT, sema_test_helper, &sema);
138 for (i = 0; i < 10; i++)
139 {
140 sema_up (&sema[0]);
141 sema_down (&sema[1]);
142 }
143 printf ("done.\n");
144}
145
146/* Thread function used by sema_self_test(). */
147static void
148sema_test_helper (void *sema_)
149{
150 struct semaphore *sema = sema_;
151 int i;
152
153 for (i = 0; i < 10; i++)
154 {
155 sema_down (&sema[0]);
156 sema_up (&sema[1]);
157 }
158}
159
160/* Initializes LOCK. A lock can be held by at most a single
161 thread at any given time. Our locks are not "recursive", that
162 is, it is an error for the thread currently holding a lock to
163 try to acquire that lock.
164
165 A lock is a specialization of a semaphore with an initial
166 value of 1. The difference between a lock and such a
167 semaphore is twofold. First, a semaphore can have a value
168 greater than 1, but a lock can only be owned by a single
169 thread at a time. Second, a semaphore does not have an owner,
170 meaning that one thread can "down" the semaphore and then
171 another one "up" it, but with a lock the same thread must both
172 acquire and release it. When these restrictions prove
173 onerous, it's a good sign that a semaphore should be used,
174 instead of a lock. */
175void
176lock_init (struct lock *lock)
177{
178 ASSERT (lock != NULL);
179
180 lock->holder = NULL;
181 sema_init (&lock->semaphore, 1);
182}
183
184/* Acquires LOCK, sleeping until it becomes available if
185 necessary. The lock must not already be held by the current
186 thread.
187
188 This function may sleep, so it must not be called within an
189 interrupt handler. This function may be called with
190 interrupts disabled, but interrupts will be turned back on if
191 we need to sleep. */
192void
193lock_acquire (struct lock *lock)
194{
195 ASSERT (lock != NULL);
196 ASSERT (!intr_context ());
197 ASSERT (!lock_held_by_current_thread (lock));
198
199 sema_down (&lock->semaphore);
200 lock->holder = thread_current ();
201}
202
203/* Tries to acquires LOCK and returns true if successful or false
204 on failure. The lock must not already be held by the current
205 thread.
206
207 This function will not sleep, so it may be called within an
208 interrupt handler. */
209bool
210lock_try_acquire (struct lock *lock)
211{
212 bool success;
213
214 ASSERT (lock != NULL);
215 ASSERT (!lock_held_by_current_thread (lock));
216
217 success = sema_try_down (&lock->semaphore);
218 if (success)
219 lock->holder = thread_current ();
220 return success;
221}
222
223/* Releases LOCK, which must be owned by the current thread.
224
225 An interrupt handler cannot acquire a lock, so it does not
226 make sense to try to release a lock within an interrupt
227 handler. */
228void
229lock_release (struct lock *lock)
230{
231 ASSERT (lock != NULL);
232 ASSERT (lock_held_by_current_thread (lock));
233
234 lock->holder = NULL;
235 sema_up (&lock->semaphore);
236}
237
238/* Returns true if the current thread holds LOCK, false
239 otherwise. (Note that testing whether some other thread holds
240 a lock would be racy.) */
241bool
242lock_held_by_current_thread (const struct lock *lock)
243{
244 ASSERT (lock != NULL);
245
246 return lock->holder == thread_current ();
247}
248
249/* One semaphore in a list. */
250struct semaphore_elem
251 {
252 struct list_elem elem; /* List element. */
253 struct semaphore semaphore; /* This semaphore. */
254 };
255
256/* Initializes condition variable COND. A condition variable
257 allows one piece of code to signal a condition and cooperating
258 code to receive the signal and act upon it. */
259void
260cond_init (struct condition *cond)
261{
262 ASSERT (cond != NULL);
263
264 list_init (&cond->waiters);
265}
266
267/* Atomically releases LOCK and waits for COND to be signaled by
268 some other piece of code. After COND is signaled, LOCK is
269 reacquired before returning. LOCK must be held before calling
270 this function.
271
272 The monitor implemented by this function is "Mesa" style, not
273 "Hoare" style, that is, sending and receiving a signal are not
274 an atomic operation. Thus, typically the caller must recheck
275 the condition after the wait completes and, if necessary, wait
276 again.
277
278 A given condition variable is associated with only a single
279 lock, but one lock may be associated with any number of
280 condition variables. That is, there is a one-to-many mapping
281 from locks to condition variables.
282
283 This function may sleep, so it must not be called within an
284 interrupt handler. This function may be called with
285 interrupts disabled, but interrupts will be turned back on if
286 we need to sleep. */
287void
288cond_wait (struct condition *cond, struct lock *lock)
289{
290 struct semaphore_elem waiter;
291
292 ASSERT (cond != NULL);
293 ASSERT (lock != NULL);
294 ASSERT (!intr_context ());
295 ASSERT (lock_held_by_current_thread (lock));
296
297 sema_init (&waiter.semaphore, 0);
298 list_push_back (&cond->waiters, &waiter.elem);
299 lock_release (lock);
300 sema_down (&waiter.semaphore);
301 lock_acquire (lock);
302}
303
304/* If any threads are waiting on COND (protected by LOCK), then
305 this function signals one of them to wake up from its wait.
306 LOCK must be held before calling this function.
307
308 An interrupt handler cannot acquire a lock, so it does not
309 make sense to try to signal a condition variable within an
310 interrupt handler. */
311void
312cond_signal (struct condition *cond, struct lock *lock UNUSED)
313{
314 ASSERT (cond != NULL);
315 ASSERT (lock != NULL);
316 ASSERT (!intr_context ());
317 ASSERT (lock_held_by_current_thread (lock));
318
319 if (!list_empty (&cond->waiters))
320 sema_up (&list_entry (list_pop_front (&cond->waiters),
321 struct semaphore_elem, elem)->semaphore);
322}
323
324/* Wakes up all threads, if any, waiting on COND (protected by
325 LOCK). LOCK must be held before calling this function.
326
327 An interrupt handler cannot acquire a lock, so it does not
328 make sense to try to signal a condition variable within an
329 interrupt handler. */
330void
331cond_broadcast (struct condition *cond, struct lock *lock)
332{
333 ASSERT (cond != NULL);
334 ASSERT (lock != NULL);
335
336 while (!list_empty (&cond->waiters))
337 cond_signal (cond, lock);
338}
diff --git a/pintos-progos/threads/synch.h b/pintos-progos/threads/synch.h
new file mode 100644
index 0000000..a19e88b
--- /dev/null
+++ b/pintos-progos/threads/synch.h
@@ -0,0 +1,51 @@
1#ifndef THREADS_SYNCH_H
2#define THREADS_SYNCH_H
3
4#include <list.h>
5#include <stdbool.h>
6
7/* A counting semaphore. */
8struct semaphore
9 {
10 unsigned value; /* Current value. */
11 struct list waiters; /* List of waiting threads. */
12 };
13
14void sema_init (struct semaphore *, unsigned value);
15void sema_down (struct semaphore *);
16bool sema_try_down (struct semaphore *);
17void sema_up (struct semaphore *);
18void sema_self_test (void);
19
20/* Lock. */
21struct lock
22 {
23 struct thread *holder; /* Thread holding lock (for debugging). */
24 struct semaphore semaphore; /* Binary semaphore controlling access. */
25 };
26
27void lock_init (struct lock *);
28void lock_acquire (struct lock *);
29bool lock_try_acquire (struct lock *);
30void lock_release (struct lock *);
31bool lock_held_by_current_thread (const struct lock *);
32
33/* Condition variable. */
34struct condition
35 {
36 struct list waiters; /* List of waiting threads. */
37 };
38
39void cond_init (struct condition *);
40void cond_wait (struct condition *, struct lock *);
41void cond_signal (struct condition *, struct lock *);
42void cond_broadcast (struct condition *, struct lock *);
43
44/* Optimization barrier.
45
46 The compiler will not reorder operations across an
47 optimization barrier. See "Optimization Barriers" in the
48 reference guide for more information.*/
49#define barrier() asm volatile ("" : : : "memory")
50
51#endif /* threads/synch.h */
diff --git a/pintos-progos/threads/thread.c b/pintos-progos/threads/thread.c
new file mode 100644
index 0000000..845f059
--- /dev/null
+++ b/pintos-progos/threads/thread.c
@@ -0,0 +1,594 @@
1#include "threads/thread.h"
2#include <debug.h>
3#include <stddef.h>
4#include <random.h>
5#include <stdio.h>
6#include <string.h>
7#include "threads/flags.h"
8#include "threads/interrupt.h"
9#include "threads/intr-stubs.h"
10#include "threads/palloc.h"
11#include "threads/switch.h"
12#include "threads/synch.h"
13#include "threads/vaddr.h"
14#ifdef USERPROG
15#include "userprog/process.h"
16#endif
17
18/* Random value for struct thread's `magic' member.
19 Used to detect stack overflow. See the big comment at the top
20 of thread.h for details. */
21#define THREAD_MAGIC 0xcd6abf4b
22
23/* List of processes in THREAD_READY state, that is, processes
24 that are ready to run but not actually running. */
25static struct list ready_list;
26
27/* List of all processes. Processes are added to this list
28 when they are first scheduled and removed when they exit. */
29static struct list all_list;
30
31/* Idle thread. */
32static struct thread *idle_thread;
33
34/* Initial thread, the thread running init.c:main(). */
35static struct thread *initial_thread;
36
37/* Lock used by allocate_tid(). */
38static struct lock tid_lock;
39
40/* Stack frame for kernel_thread(). */
41struct kernel_thread_frame
42 {
43 void *eip; /* Return address. */
44 thread_func *function; /* Function to call. */
45 void *aux; /* Auxiliary data for function. */
46 };
47
48/* Statistics. */
49static long long idle_ticks; /* # of timer ticks spent idle. */
50static long long kernel_ticks; /* # of timer ticks in kernel threads. */
51static long long user_ticks; /* # of timer ticks in user programs. */
52
53/* Scheduling. */
54#define TIME_SLICE 4 /* # of timer ticks to give each thread. */
55static unsigned thread_ticks; /* # of timer ticks since last yield. */
56
57/* If false (default), use round-robin scheduler.
58 If true, use multi-level feedback queue scheduler.
59 Controlled by kernel command-line option "-o mlfqs". */
60bool thread_mlfqs;
61
62static void kernel_thread (thread_func *, void *aux);
63
64static void idle (void *aux UNUSED);
65static struct thread *running_thread (void);
66static struct thread *next_thread_to_run (void);
67static void init_thread (struct thread *, const char *name, int priority);
68static bool is_thread (struct thread *) UNUSED;
69static void *alloc_frame (struct thread *, size_t size);
70static void schedule (void);
71void thread_schedule_tail (struct thread *prev);
72static tid_t allocate_tid (void);
73
74/* Initializes the threading system by transforming the code
75 that's currently running into a thread. This can't work in
76 general and it is possible in this case only because loader.S
77 was careful to put the bottom of the stack at a page boundary.
78
79 Also initializes the run queue and the tid lock.
80
81 After calling this function, be sure to initialize the page
82 allocator before trying to create any threads with
83 thread_create().
84
85 It is not safe to call thread_current() until this function
86 finishes. */
87void
88thread_init (void)
89{
90 ASSERT (intr_get_level () == INTR_OFF);
91
92 lock_init (&tid_lock);
93 list_init (&ready_list);
94 list_init (&all_list);
95
96#ifdef USERPROG
97 process_init ();
98#endif
99
100 /* Set up a thread structure for the running thread. */
101 initial_thread = running_thread ();
102 init_thread (initial_thread, "main", PRI_DEFAULT);
103 initial_thread->status = THREAD_RUNNING;
104 initial_thread->tid = allocate_tid ();
105}
106
107/* Starts preemptive thread scheduling by enabling interrupts.
108 Also creates the idle thread. */
109void
110thread_start (void)
111{
112 /* Create the idle thread. */
113 struct semaphore idle_started;
114 sema_init (&idle_started, 0);
115 thread_create ("idle", PRI_MIN, idle, &idle_started);
116
117 /* Start preemptive thread scheduling. */
118 intr_enable ();
119
120 /* Wait for the idle thread to initialize idle_thread. */
121 sema_down (&idle_started);
122}
123
124/* Called by the timer interrupt handler at each timer tick.
125 Thus, this function runs in an external interrupt context. */
126void
127thread_tick (void)
128{
129 struct thread *t = thread_current ();
130
131 /* Update statistics. */
132 if (t == idle_thread)
133 idle_ticks++;
134#ifdef USERPROG
135 else if (t->pagedir != NULL)
136 user_ticks++;
137#endif
138 else
139 kernel_ticks++;
140
141 /* Enforce preemption. */
142 if (++thread_ticks >= TIME_SLICE)
143 intr_yield_on_return ();
144}
145
146/* Prints thread statistics. */
147void
148thread_print_stats (void)
149{
150 printf ("Thread: %lld idle ticks, %lld kernel ticks, %lld user ticks\n",
151 idle_ticks, kernel_ticks, user_ticks);
152}
153
154/* Creates a new kernel thread named NAME with the given initial
155 PRIORITY, which executes FUNCTION passing AUX as the argument,
156 and adds it to the ready queue. Returns the thread identifier
157 for the new thread, or TID_ERROR if creation fails.
158
159 If thread_start() has been called, then the new thread may be
160 scheduled before thread_create() returns. It could even exit
161 before thread_create() returns. Contrariwise, the original
162 thread may run for any amount of time before the new thread is
163 scheduled. Use a semaphore or some other form of
164 synchronization if you need to ensure ordering.
165
166 The code provided sets the new thread's `priority' member to
167 PRIORITY, but no actual priority scheduling is implemented.
168 Priority scheduling is the goal of Problem 1-3. */
169tid_t
170thread_create (const char *name, int priority,
171 thread_func *function, void *aux)
172{
173 struct thread *t;
174 struct kernel_thread_frame *kf;
175 struct switch_entry_frame *ef;
176 struct switch_threads_frame *sf;
177 tid_t tid;
178 enum intr_level old_level;
179
180 ASSERT (function != NULL);
181
182 /* Allocate thread. */
183 t = palloc_get_page (PAL_ZERO);
184 if (t == NULL)
185 return TID_ERROR;
186
187 /* Initialize thread. */
188 init_thread (t, name, priority);
189 tid = t->tid = allocate_tid ();
190
191 /* Prepare thread for first run by initializing its stack.
192 Do this atomically so intermediate values for the 'stack'
193 member cannot be observed. */
194 old_level = intr_disable ();
195
196 /* Stack frame for kernel_thread(). */
197 kf = alloc_frame (t, sizeof *kf);
198 kf->eip = NULL;
199 kf->function = function;
200 kf->aux = aux;
201
202 /* Stack frame for switch_entry(). */
203 ef = alloc_frame (t, sizeof *ef);
204 ef->eip = (void (*) (void)) kernel_thread;
205
206 /* Stack frame for switch_threads(). */
207 sf = alloc_frame (t, sizeof *sf);
208 sf->eip = switch_entry;
209 sf->ebp = 0;
210
211 intr_set_level (old_level);
212
213 /* Add to run queue. */
214 thread_unblock (t);
215
216 return tid;
217}
218
219/* Puts the current thread to sleep. It will not be scheduled
220 again until awoken by thread_unblock().
221
222 This function must be called with interrupts turned off. It
223 is usually a better idea to use one of the synchronization
224 primitives in synch.h. */
225void
226thread_block (void)
227{
228 ASSERT (!intr_context ());
229 ASSERT (intr_get_level () == INTR_OFF);
230
231 thread_current ()->status = THREAD_BLOCKED;
232 schedule ();
233}
234
235/* Transitions a blocked thread T to the ready-to-run state.
236 This is an error if T is not blocked. (Use thread_yield() to
237 make the running thread ready.)
238
239 This function does not preempt the running thread. This can
240 be important: if the caller had disabled interrupts itself,
241 it may expect that it can atomically unblock a thread and
242 update other data. */
243void
244thread_unblock (struct thread *t)
245{
246 enum intr_level old_level;
247
248 ASSERT (is_thread (t));
249
250 old_level = intr_disable ();
251 ASSERT (t->status == THREAD_BLOCKED);
252 list_push_back (&ready_list, &t->elem);
253 t->status = THREAD_READY;
254 intr_set_level (old_level);
255}
256
257/* Returns the name of the running thread. */
258const char *
259thread_name (void)
260{
261 return thread_current ()->name;
262}
263
264/* Returns the running thread.
265 This is running_thread() plus a couple of sanity checks.
266 See the big comment at the top of thread.h for details. */
267struct thread *
268thread_current (void)
269{
270 struct thread *t = running_thread ();
271
272 /* Make sure T is really a thread.
273 If either of these assertions fire, then your thread may
274 have overflowed its stack. Each thread has less than 4 kB
275 of stack, so a few big automatic arrays or moderate
276 recursion can cause stack overflow. */
277 ASSERT (is_thread (t));
278 ASSERT (t->status == THREAD_RUNNING);
279
280 return t;
281}
282
283/* Returns the running thread's tid. */
284tid_t
285thread_tid (void)
286{
287 return thread_current ()->tid;
288}
289
290/* Deschedules the current thread and destroys it. Never
291 returns to the caller. */
292void
293thread_exit (void)
294{
295 ASSERT (!intr_context ());
296
297#ifdef USERPROG
298 process_exit ();
299#endif
300
301 /* Remove thread from all threads list, set our status to dying,
302 and schedule another process. That process will destroy us
303 when it calls thread_schedule_tail(). */
304 intr_disable ();
305 list_remove (&thread_current()->allelem);
306 thread_current ()->status = THREAD_DYING;
307 schedule ();
308 NOT_REACHED ();
309}
310
311/* Yields the CPU. The current thread is not put to sleep and
312 may be scheduled again immediately at the scheduler's whim. */
313void
314thread_yield (void)
315{
316 struct thread *cur = thread_current ();
317 enum intr_level old_level;
318
319 ASSERT (!intr_context ());
320
321 old_level = intr_disable ();
322 if (cur != idle_thread)
323 list_push_back (&ready_list, &cur->elem);
324 cur->status = THREAD_READY;
325 schedule ();
326 intr_set_level (old_level);
327}
328
329/* Invoke function 'func' on all threads, passing along 'aux'.
330 This function must be called with interrupts off. */
331void
332thread_foreach (thread_action_func *func, void *aux)
333{
334 struct list_elem *e;
335
336 ASSERT (intr_get_level () == INTR_OFF);
337
338 for (e = list_begin (&all_list); e != list_end (&all_list);
339 e = list_next (e))
340 {
341 struct thread *t = list_entry (e, struct thread, allelem);
342 func (t, aux);
343 }
344}
345
346/* Sets the current thread's priority to NEW_PRIORITY. */
347void
348thread_set_priority (int new_priority)
349{
350 thread_current ()->priority = new_priority;
351}
352
353/* Returns the current thread's priority. */
354int
355thread_get_priority (void)
356{
357 return thread_current ()->priority;
358}
359
360/* Sets the current thread's nice value to NICE. */
361void
362thread_set_nice (int nice UNUSED)
363{
364 /* Not yet implemented. */
365}
366
367/* Returns the current thread's nice value. */
368int
369thread_get_nice (void)
370{
371 /* Not yet implemented. */
372 return 0;
373}
374
375/* Returns 100 times the system load average. */
376int
377thread_get_load_avg (void)
378{
379 /* Not yet implemented. */
380 return 0;
381}
382
383/* Returns 100 times the current thread's recent_cpu value. */
384int
385thread_get_recent_cpu (void)
386{
387 /* Not yet implemented. */
388 return 0;
389}
390
391/* Idle thread. Executes when no other thread is ready to run.
392
393 The idle thread is initially put on the ready list by
394 thread_start(). It will be scheduled once initially, at which
395 point it initializes idle_thread, "up"s the semaphore passed
396 to it to enable thread_start() to continue, and immediately
397 blocks. After that, the idle thread never appears in the
398 ready list. It is returned by next_thread_to_run() as a
399 special case when the ready list is empty. */
400static void
401idle (void *idle_started_ UNUSED)
402{
403 struct semaphore *idle_started = idle_started_;
404 idle_thread = thread_current ();
405 sema_up (idle_started);
406
407 for (;;)
408 {
409 /* Let someone else run. */
410 intr_disable ();
411 thread_block ();
412
413 /* Re-enable interrupts and wait for the next one.
414
415 The `sti' instruction disables interrupts until the
416 completion of the next instruction, so these two
417 instructions are executed atomically. This atomicity is
418 important; otherwise, an interrupt could be handled
419 between re-enabling interrupts and waiting for the next
420 one to occur, wasting as much as one clock tick worth of
421 time.
422
423 See [IA32-v2a] "HLT", [IA32-v2b] "STI", and [IA32-v3a]
424 7.11.1 "HLT Instruction". */
425 asm volatile ("sti; hlt" : : : "memory");
426 }
427}
428
429/* Function used as the basis for a kernel thread. */
430static void
431kernel_thread (thread_func *function, void *aux)
432{
433 ASSERT (function != NULL);
434
435 intr_enable (); /* The scheduler runs with interrupts off. */
436 function (aux); /* Execute the thread function. */
437 thread_exit (); /* If function() returns, kill the thread. */
438}
439
440/* Returns the running thread. */
441struct thread *
442running_thread (void)
443{
444 uint32_t *esp;
445
446 /* Copy the CPU's stack pointer into `esp', and then round that
447 down to the start of a page. Because `struct thread' is
448 always at the beginning of a page and the stack pointer is
449 somewhere in the middle, this locates the curent thread. */
450 asm ("mov %%esp, %0" : "=g" (esp));
451 return pg_round_down (esp);
452}
453
454/* Returns true if T appears to point to a valid thread. */
455static bool
456is_thread (struct thread *t)
457{
458 return t != NULL && t->magic == THREAD_MAGIC;
459}
460
461/* Does basic initialization of T as a blocked thread named
462 NAME. */
463static void
464init_thread (struct thread *t, const char *name, int priority)
465{
466 ASSERT (t != NULL);
467 ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
468 ASSERT (name != NULL);
469
470 memset (t, 0, sizeof *t);
471 t->status = THREAD_BLOCKED;
472 strlcpy (t->name, name, sizeof t->name);
473 t->stack = (uint8_t *) t + PGSIZE;
474 t->priority = priority;
475 t->magic = THREAD_MAGIC;
476 list_push_back (&all_list, &t->allelem);
477#ifdef USERPROG
478 list_init(&t->children);
479#endif
480}
481
482/* Allocates a SIZE-byte frame at the top of thread T's stack and
483 returns a pointer to the frame's base. */
484static void *
485alloc_frame (struct thread *t, size_t size)
486{
487 /* Stack data is always allocated in word-size units. */
488 ASSERT (is_thread (t));
489 ASSERT (size % sizeof (uint32_t) == 0);
490
491 t->stack -= size;
492 return t->stack;
493}
494
495/* Chooses and returns the next thread to be scheduled. Should
496 return a thread from the run queue, unless the run queue is
497 empty. (If the running thread can continue running, then it
498 will be in the run queue.) If the run queue is empty, return
499 idle_thread. */
500static struct thread *
501next_thread_to_run (void)
502{
503 if (list_empty (&ready_list))
504 return idle_thread;
505 else
506 return list_entry (list_pop_front (&ready_list), struct thread, elem);
507}
508
509/* Completes a thread switch by activating the new thread's page
510 tables, and, if the previous thread is dying, destroying it.
511
512 At this function's invocation, we just switched from thread
513 PREV, the new thread is already running, and interrupts are
514 still disabled. This function is normally invoked by
515 thread_schedule() as its final action before returning, but
516 the first time a thread is scheduled it is called by
517 switch_entry() (see switch.S).
518
519 It's not safe to call printf() until the thread switch is
520 complete. In practice that means that printf()s should be
521 added at the end of the function.
522
523 After this function and its caller returns, the thread switch
524 is complete. */
525void
526thread_schedule_tail (struct thread *prev)
527{
528 struct thread *cur = running_thread ();
529
530 ASSERT (intr_get_level () == INTR_OFF);
531
532 /* Mark us as running. */
533 cur->status = THREAD_RUNNING;
534
535 /* Start new time slice. */
536 thread_ticks = 0;
537
538#ifdef USERPROG
539 /* Activate the new address space. */
540 process_activate ();
541#endif
542
543 /* If the thread we switched from is dying, destroy its struct
544 thread. This must happen late so that thread_exit() doesn't
545 pull out the rug under itself. (We don't free
546 initial_thread because its memory was not obtained via
547 palloc().) */
548 if (prev != NULL && prev->status == THREAD_DYING && prev != initial_thread)
549 {
550 ASSERT (prev != cur);
551 palloc_free_page (prev);
552 }
553}
554
555/* Schedules a new process. At entry, interrupts must be off and
556 the running process's state must have been changed from
557 running to some other state. This function finds another
558 thread to run and switches to it.
559
560 It's not safe to call printf() until thread_schedule_tail()
561 has completed. */
562static void
563schedule (void)
564{
565 struct thread *cur = running_thread ();
566 struct thread *next = next_thread_to_run ();
567 struct thread *prev = NULL;
568
569 ASSERT (intr_get_level () == INTR_OFF);
570 ASSERT (cur->status != THREAD_RUNNING);
571 ASSERT (is_thread (next));
572
573 if (cur != next)
574 prev = switch_threads (cur, next);
575 thread_schedule_tail (prev);
576}
577
578/* Returns a tid to use for a new thread. */
579static tid_t
580allocate_tid (void)
581{
582 static tid_t next_tid = 1;
583 tid_t tid;
584
585 lock_acquire (&tid_lock);
586 tid = next_tid++;
587 lock_release (&tid_lock);
588
589 return tid;
590}
591
592/* Offset of `stack' member within `struct thread'.
593 Used by switch.S, which can't figure it out on its own. */
594uint32_t thread_stack_ofs = offsetof (struct thread, stack);
diff --git a/pintos-progos/threads/thread.h b/pintos-progos/threads/thread.h
new file mode 100644
index 0000000..eebf42c
--- /dev/null
+++ b/pintos-progos/threads/thread.h
@@ -0,0 +1,144 @@
1#ifndef THREADS_THREAD_H
2#define THREADS_THREAD_H
3
4#include <debug.h>
5#include <list.h>
6#include <stdint.h>
7#include "threads/synch.h"
8
9/* States in a thread's life cycle. */
10enum thread_status
11 {
12 THREAD_RUNNING, /* Running thread. */
13 THREAD_READY, /* Not running but ready to run. */
14 THREAD_BLOCKED, /* Waiting for an event to trigger. */
15 THREAD_DYING /* About to be destroyed. */
16 };
17
18/* Thread identifier type.
19 You can redefine this to whatever type you like. */
20typedef int tid_t;
21#define TID_ERROR ((tid_t) -1) /* Error value for tid_t. */
22
23/* Thread priorities. */
24#define PRI_MIN 0 /* Lowest priority. */
25#define PRI_DEFAULT 31 /* Default priority. */
26#define PRI_MAX 63 /* Highest priority. */
27
28/* A kernel thread or user process.
29
30 Each thread structure is stored in its own 4 kB page. The
31 thread structure itself sits at the very bottom of the page
32 (at offset 0). The rest of the page is reserved for the
33 thread's kernel stack, which grows downward from the top of
34 the page (at offset 4 kB). Here's an illustration:
35
36 4 kB +---------------------------------+
37 | kernel stack |
38 | | |
39 | | |
40 | V |
41 | grows downward |
42 | |
43 | |
44 | |
45 | |
46 | |
47 | |
48 | |
49 | |
50 +---------------------------------+
51 | magic |
52 | : |
53 | : |
54 | name |
55 | status |
56 0 kB +---------------------------------+
57
58 The upshot of this is twofold:
59
60 1. First, `struct thread' must not be allowed to grow too
61 big. If it does, then there will not be enough room for
62 the kernel stack. Our base `struct thread' is only a
63 few bytes in size. It probably should stay well under 1
64 kB.
65
66 2. Second, kernel stacks must not be allowed to grow too
67 large. If a stack overflows, it will corrupt the thread
68 state. Thus, kernel functions should not allocate large
69 structures or arrays as non-static local variables. Use
70 dynamic allocation with malloc() or palloc_get_page()
71 instead.
72
73 The first symptom of either of these problems will probably be
74 an assertion failure in thread_current(), which checks that
75 the `magic' member of the running thread's `struct thread' is
76 set to THREAD_MAGIC. Stack overflow will normally change this
77 value, triggering the assertion. */
78/* The `elem' member has a dual purpose. It can be an element in
79 the run queue (thread.c), or it can be an element in a
80 semaphore wait list (synch.c). It can be used these two ways
81 only because they are mutually exclusive: only a thread in the
82 ready state is on the run queue, whereas only a thread in the
83 blocked state is on a semaphore wait list. */
84struct thread
85 {
86 /* Owned by thread.c. */
87 tid_t tid; /* Thread identifier. */
88 enum thread_status status; /* Thread state. */
89 char name[16]; /* Name (for debugging purposes). */
90 uint8_t *stack; /* Saved stack pointer. */
91 int priority; /* Priority. */
92 struct list_elem allelem; /* List element for all threads list. */
93
94 /* Shared between thread.c and synch.c. */
95 struct list_elem elem; /* List element. */
96
97#ifdef USERPROG
98 /* Owned by userprog/process.c */
99 struct process* process; /* Process Structure */
100 struct list children; /* Threads can hold processes, but not vice versa */
101 uint32_t *pagedir; /* Page directory. */
102#endif
103
104 /* Owned by thread.c. */
105 unsigned magic; /* Detects stack overflow. */
106 };
107
108/* If false (default), use round-robin scheduler.
109 If true, use multi-level feedback queue scheduler.
110 Controlled by kernel command-line option "-o mlfqs". */
111extern bool thread_mlfqs;
112
113void thread_init (void);
114void thread_start (void);
115
116void thread_tick (void);
117void thread_print_stats (void);
118
119typedef void thread_func (void *aux);
120tid_t thread_create (const char *name, int priority, thread_func *, void *);
121
122void thread_block (void);
123void thread_unblock (struct thread *);
124
125struct thread *thread_current (void);
126tid_t thread_tid (void);
127const char *thread_name (void);
128
129void thread_exit (void) NO_RETURN;
130void thread_yield (void);
131
132/* Performs some operation on thread t, given auxiliary data AUX. */
133typedef void thread_action_func (struct thread *t, void *aux);
134void thread_foreach (thread_action_func *, void *);
135
136int thread_get_priority (void);
137void thread_set_priority (int);
138
139int thread_get_nice (void);
140void thread_set_nice (int);
141int thread_get_recent_cpu (void);
142int thread_get_load_avg (void);
143
144#endif /* threads/thread.h */
diff --git a/pintos-progos/threads/vaddr.h b/pintos-progos/threads/vaddr.h
new file mode 100644
index 0000000..184c824
--- /dev/null
+++ b/pintos-progos/threads/vaddr.h
@@ -0,0 +1,89 @@
1#ifndef THREADS_VADDR_H
2#define THREADS_VADDR_H
3
4#include <debug.h>
5#include <stdint.h>
6#include <stdbool.h>
7
8#include "threads/loader.h"
9
10/* Functions and macros for working with virtual addresses.
11
12 See pte.h for functions and macros specifically for x86
13 hardware page tables. */
14
15#define BITMASK(SHIFT, CNT) (((1ul << (CNT)) - 1) << (SHIFT))
16
17/* Page offset (bits 0:12). */
18#define PGSHIFT 0 /* Index of first offset bit. */
19#define PGBITS 12 /* Number of offset bits. */
20#define PGSIZE (1 << PGBITS) /* Bytes in a page. */
21#define PGMASK BITMASK(PGSHIFT, PGBITS) /* Page offset bits (0:12). */
22
23/* Offset within a page. */
24static inline unsigned pg_ofs (const void *va) {
25 return (uintptr_t) va & PGMASK;
26}
27
28/* Virtual page number. */
29static inline uintptr_t pg_no (const void *va) {
30 return (uintptr_t) va >> PGBITS;
31}
32
33/* Round up to nearest page boundary. */
34static inline void *pg_round_up (const void *va) {
35 return (void *) (((uintptr_t) va + PGSIZE - 1) & ~PGMASK);
36}
37
38/* Round down to nearest page boundary. */
39static inline void *pg_round_down (const void *va) {
40 return (void *) ((uintptr_t) va & ~PGMASK);
41}
42
43/* Base address of the 1:1 physical-to-virtual mapping. Physical
44 memory is mapped starting at this virtual address. Thus,
45 physical address 0 is accessible at PHYS_BASE, physical
46 address address 0x1234 at (uint8_t *) PHYS_BASE + 0x1234, and
47 so on.
48
49 This address also marks the end of user programs' address
50 space. Up to this point in memory, user programs are allowed
51 to map whatever they like. At this point and above, the
52 virtual address space belongs to the kernel. */
53#define PHYS_BASE ((void *) LOADER_PHYS_BASE)
54
55/* Returns true if VADDR is a user virtual address. */
56static inline bool
57is_user_vaddr (const void *vaddr)
58{
59 return vaddr < PHYS_BASE;
60}
61
62/* Returns true if VADDR is a kernel virtual address. */
63static inline bool
64is_kernel_vaddr (const void *vaddr)
65{
66 return vaddr >= PHYS_BASE;
67}
68
69/* Returns kernel virtual address at which physical address PADDR
70 is mapped. */
71static inline void *
72ptov (uintptr_t paddr)
73{
74 ASSERT ((void *) paddr < PHYS_BASE);
75
76 return (void *) (paddr + PHYS_BASE);
77}
78
79/* Returns physical address at which kernel virtual address VADDR
80 is mapped. */
81static inline uintptr_t
82vtop (const void *vaddr)
83{
84 ASSERT (is_kernel_vaddr (vaddr));
85
86 return (uintptr_t) vaddr - (uintptr_t) PHYS_BASE;
87}
88
89#endif /* threads/vaddr.h */
generated by cgit v1.2.3 (git 2.25.1) at 2026-01-11 20:31:56 +0000