| blob | 3f741bfda80bc29e9eca36e8c90e62b6d949b68e |
1 [Kernel, CS 235 Advanced Operating Systems, Fall 2010
2 courtesy
3 IowaFarmer.com Lab 2: Memory Management and Exceptions
4 CornCam]
5 Due 11:59pm Friday, October 22
7 Introduction
9 In this lab, you'll write the memory management and initial exception handling
10 code for your operating system.
12 The first component of memory management is virtual memory, where we set up the
13 PC's Memory Management Unit (MMU) hardware to map the virtual addresses used by
14 software into the physical addresses that map directly to memory chips. You
15 will modify JOS to set up virtual memory mappings according to a specification
16 we provide. In particular, you'll build a page table data structure to match
17 our specification.
19 The second component is managing the physical memory of the computer so that
20 the kernel can allocate and free physical memory as needed. The x86 divides
21 physical memory into 4096-byte regions called pages. Your task will be to
22 maintain data structures that record which physical pages are free and which
23 are allocated, and how many processes are sharing each allocated page. You will
24 also write the routines to allocate and free pages of memory.
26 Finally, you'll write initial exception-handling code for JOS, so that it can
27 take an interrupt while in kernel mode.
29 Getting started
31 In this and future labs you will progressively build on this same kernel. With
32 each new lab we will update our source to contain additional files and possibly
33 some changes to existing files; you'll need to merge your changes from the
34 previous lab into the new source tree.
36 To fetch the new source, use Git to commit your lab 1 and save that code in a
37 branch called lab1. Then fetch the latest version of the course repository, and
38 update your local branch based on our lab2 branch, origin/lab2:
40 % git status
41 ... # Look over the output of this command.
42 # If you added new files to your source, add them
43 # using "git add".
44 % git commit -am 'my solution to lab1'
45 Created commit 254dac5: my solution to lab1
46 3 files changed, 31 insertions(+), 6 deletions(-)
47 % git branch lab1
48 # This creates the lab1 branch.
49 % git fetch
50 # This fetches our new code.
51 % git checkout -b lab2 origin/lab2
52 Branch lab2 set up to track remote branch refs/remotes/origin/lab2.
53 Switched to a new branch "lab2"
55 The git checkout -b command shown above actually does two things: it first
56 creates a local branch lab2 that is based on the origin/lab2 branch provided by
57 the course staff, and second, it changes the contents of your lab directory to
58 reflect the files stored on the lab2 branch. Git allows switching between
59 existing branches using git checkout branch-name, so you can recover your Lab 1
60 code with git checkout lab1. But you should commit any outstanding changes on
61 one branch before switching to a different one.
63 You will now need to merge the changes you made in your lab1 branch into the
64 lab2 branch, as follows:
66 % git merge lab1
67 Merge made by recursive.
68 kern/kdebug.c | 11 +++++++++--
69 kern/monitor.c | 19 +++++++++++++++++++
70 lib/printfmt.c | 7 +++----
71 3 files changed, 31 insertions(+), 6 deletions(-)
73 In some cases, Git may not be able to figure out how to merge your changes with
74 the new lab assignment (e.g. if you modified some of the code that is changed
75 in the second lab assignment). In that case, the git merge command will tell
76 you which files are conflicted, and you should first resolve the conflict (by
77 editing the relevant files) and then commit the resulting files with git commit
78 -a.
80 You can download the tarball if you'd like, but we recommend using Git.
82 You should browse through these source files for Lab 2, most of which are new.
84 • inc/memlayout.h
85 • kern/pmap.c
86 • kern/pmap.h
87 • kern/kclock.h
88 • kern/kclock.c
89 • inc/trap.h
90 • kern/trap.h
91 • kern/trap.c
92 • kern/trapentry.S
94 memlayout.h describes the layout of the virtual address space that you must
95 implement by modifying pmap.c. pmap.h defines the Page structure that you'll
96 use to keep track of which pages of physical memory are free. kclock.c and
97 kclock.h manipulate the PC's battery-backed clock and CMOS RAM hardware, in
98 which the BIOS records the amount of physical memory the PC contains, among
99 other things. The code in pmap.c needs to read this device hardware in order to
100 figure out how much physical memory there is, but that part of the code is done
101 for you: you do not need to know the details of how the CMOS hardware works.
102 The last four files are used to set up the processor's interrupt descriptor
103 table and handle interrupts and exceptions.
105 Lab Requirements
107 In this lab, you'll need to do all of the regular exercises described in the
108 lab and at least one challenge problem. Some challenge problems are more
109 challenging than others, of course! And feel free to design your own challenge
110 problem; just check with me first.
112 Additionally, write up brief answers to the 8 explicitly-marked Questions posed
113 in the lab and a short (one or two paragraph) description of what you did to
114 solve your chosen challenge problem. If you implement more than one challenge
115 problem, you only need to describe one of them in the write-up, though of
116 course you are welcome to do more. Place the write-up in a file called
117 answers.txt (plain text) or answers.html (HTML format) in the top level of your
118 lab2 directory before handing in your work.
120 Hand-In Procedure
122 When you are ready to hand in your lab code and write-up, run make tarball in
123 your jos directory. This will create a file called lab2-yourusername.tar.gz,
124 which you should submit via CourseWeb at 11:59pm on Friday, October 22. If you
125 have problems with CourseWeb, you may also email me the file.
127 As before, we will be grading your solutions with a grading program. You can
128 run make grade to test your kernel with the grading program. You may change any
129 of the kernel source and header files you need to in order to complete the lab,
130 but we check to make sure you aren't changing or otherwise subverting the
131 grading code.
133 Part 1: Virtual Memory
135 Before doing anything else, you will need to familiarize yourself with the
136 x86's protected-mode memory management architecture: namely segmentation and
137 page translation.
139 Exercise 1. Read chapters 5 and 6 of the Intel 80386 Reference Manual, if you
140 haven't done so already. Although JOS relies most heavily on page translation,
141 you will also need a basic understanding of how segmentation works in protected
142 mode to understand what's going on.
144 In x86 terminology, a virtual address is a "segment:offset"-style address
145 before segment translation is performed; a linear address is what you get after
146 segmentation but before page translation; and a physical address is what you
147 finally get after both segmentation and page translation. Be sure you
148 understand the difference between these three types or "levels" of addresses!
149 (For instance, what type of addresses are stored in page directory and page
150 table entries, virtual or physical?)
152 The JOS kernel tries to use consistent type names for different kinds of
153 address. In particular, the type uintptr_t represents virtual addresses, and
154 physaddr_t represents physical addresses. Of course, both these types are
155 really just synonyms for 32-bit integers (uint32_t), so the compiler won't stop
156 you from assigning one type to another! Every pointer value in JOS should be a
157 virtual address (once paging is set up), since only virtual addresses can be
158 dereferenced. The kernel runs in protected mode too! To summarize:
160 C type Address type
161 T* Virtual
162 uintptr_t Virtual
163 physaddr_t Physical
165 Question:
167 1. Assuming that the following code won't fail to compile or crash the JOS
168 kernel, should mystery_t be uintptr_t or physaddr_t?
170 mystery_t x;
171 char* value = return_a_pointer();
172 *value = 10;
173 x = (mystery_t) value;
175 The Physical Page Allocator
177 The operating system must keep track of which parts of physical RAM are free
178 and which are currently in use. JOS manages the PC's physical memory with page
179 granularity so that it can use the MMU to map and protect each piece of
180 allocated memory.
182 You'll now write the physical page allocator. The kernel maintains an array of
183 struct Page objects, one per physical page. Those Page objects whose physical
184 pages are available for allocation are kept on a linked list, page_free_list.
185 You need to write the physical page allocator before you can write the rest of
186 the virtual memory implementation, because your page table management code will
187 need to allocate physical memory in which to store page tables.
189 Exercise 2. Implement the following functions in kern/pmap.c.
191 boot_alloc()
192 page_init()
193 page_alloc()
194 page_free()
196 Then complete the implementation of the mem_init() function up to the call to
197 check_page_alloc(). These functions initialize the physical memory allocator.
199 Once you have done this, run the code by booting JOS. The function call to
200 check_page_alloc() will check your allocator and report any problems it finds.
201 Do not continue until you pass this check. Your code should also pass the
202 Physical page allocator test when you run make grade. You may find it helpful
203 to add your own assert()s to verify that your own assumptions are, in fact,
204 correct.
206 Page Table Management
208 Now you'll write a set of routines to manage page tables: to insert and remove
209 linear-to-physical mappings, and to create page table pages when needed.
211 In future labs you will often map the same physical page at multiple virtual
212 addresses (or in the address spaces of multiple environments), so you will keep
213 a count of the number of times each physical page is mapped in the
214 corresponding Page's pp_ref. The count should be equal to the number of
215 pointers to the page in the page table(s) below UTOP (the mappings above UTOP
216 are mostly just set up at boot time by the kernel and are not tracked by the
217 reference-counting system). When the count goes to zero, the physical page can
218 be freed.
220 Exercise 3. In the file kern/pmap.c, you must implement code for the four
221 functions listed below: You may find it useful to read inc/memlayout.h and kern
222 /pmap.h.
224 pgdir_walk()
225 page_lookup()
226 page_remove()
227 page_insert()
229 The function check_page(), called from mem_init(), tests these functions. You
230 must get check_page() to run successfully before proceeding. Your code should
231 also pass the Page management test when you run make grade.
233 The JOS Kernel Virtual Address Space
235 Now, mem_init() will set up the kernel's virtual address space -- the part
236 above UTOP. The actual layout is diagrammed in inc/memlayout.h.
238 In Part 3 of Lab 1 we noted that the boot loader sets up the x86 segmentation
239 hardware so that the kernel appears to run at its link address of 0xf0100000,
240 even though it is actually loaded in physical memory just above the ROM BIOS at
241 0x00100000. In other words, the kernel's virtual starting address at this point
242 is 0xf0100000, but its linear and physical starting addresses are both
243 0x00100000. The kernel's linear and physical addresses are the same because we
244 have not yet initialized or enabled page translation.
246 In the virtual memory layout you are going to set up for JOS, we will stop
247 using the x86 segmentation hardware for anything interesting, and instead start
248 using page translation to accomplish everything we've already done with
249 segmentation and much more. That is, after you finish this lab and the JOS
250 kernel successfully enables paging, linear addresses will be the same as (the
251 offset portion of) the kernel's virtual addresses, rather than being the same
252 as physical addresses as they are when the boot loader first enters the kernel.
254 In JOS, we divide the processor's 32-bit linear address space into two parts.
255 User environments (processes), which we will begin loading and running in lab
256 3, will have control over the layout and contents of the lower part, while the
257 kernel always maintains complete control over the upper part. The dividing line
258 is defined somewhat arbitrarily by the symbol ULIM in inc/memlayout.h,
259 reserving approximately 256MB of linear (and therefore virtual) address space
260 for the kernel. This explains why we needed to give the kernel such a high link
261 address in lab 1: otherwise there would not be enough room in the kernel's
262 linear address space to map in a user environment below it at the same time.
263 The JOS kernel also maintains constant complete control over the contents of
264 memory by mapping all of physical memory to its portion of the address space.
265 To change a byte of physical memory, all it needs to do is find a kernel
266 virtual pointer for this address (using the KADDR macro), and change the value
267 stored in that pointer.
269 Since the kernel and user environment will effectively co-exist in each
270 environment's address space, we will have to use permission bits in our x86
271 page tables to prevent user code from accessing the kernel's memory: i.e., to
272 enforce isolation. The user environment will have no permission to any of the
273 memory above ULIM, while the kernel will be able to read and write this memory.
274 For the address range [UTOP,ULIM), both the kernel and the user environment
275 have the same permission: they can read but not write this address range. This
276 range of addresses is used to expose certain kernel data structures read-only
277 to the user environment. Lastly, the address space below UTOP is for the user
278 environment to use; the user environment will set permissions for accessing
279 this memory.
281 Question:
283 2. What is the maximum amount of physical memory that this operating system
284 can support? Why?
286 It's now time to set up the kernel portion of the address space.
288 Exercise 4. In the file kern/pmap.c, you must implement code for the
289 page_map_segment function. Then, follow the comments to complete the code in
290 mem_init.
292 The function check_kern_pgdir(), called from mem_init(), tests your work. You
293 must get check_kern_pgdir() to run successfully before proceeding. Your code
294 should also pass the Kernel page directory test when you run make grade.
296 Questions:
298 3. What entries (rows) in the page directory have been filled in at this
299 point? What addresses do they map and where do they point? In other words,
300 fill out this table as much as possible:
302 Entry Base virtual address Logically points to
304 1023 0xFFC00000 Page table for top 4MB of physical memory
306 1022 0xFF800000 ?
308 ... ... ...
310 2 0x00800000 ?
312 1 0x00400000 ?
314 0 0x00000000 [see next question?]
316 4. In mem_init(), after check_kern_pgdir, we map the first entry of the page
317 directory to the page table of the first four MB of RAM, but delete this
318 mapping at the end of the function. Why is this necessary? What would
319 happen if it were omitted? Does this actually limit our kernel to be 4MB?
320 What must be true if our kernel were larger than 4MB?
322 5. On the x86, we place the kernel and user environment in the same address
323 space. What specific mechanism (i.e., what register, memory address, or bit
324 thereof) is used to protect the kernel's memory against a malicious user
325 process?
327 6. How much space overhead is there for managing memory, if we actually had
328 the maximum amount of physical memory? How is this overhead broken down?
329 Overhead includes the Page structures and the kernel's page directory.
331 Challenge! As Question 6 shows, we consumed many physical pages to hold the
332 page tables for the KERNBASE mapping. Do a more space-efficient job using the
333 PTE_PS ("Page Size") bit in the page directory entries. This bit was not
334 supported in the original 80386, but is supported on more recent x86
335 processors. You will therefore have to refer to Volume 3 of the current Intel
336 manuals. Make sure you design the kernel to use this optimization only on
337 processors that support it!
339 Challenge! Extend the JOS kernel monitor with commands to:
341 • Display in a useful and easy-to-read format all of the physical page
342 mappings (or lack thereof) that apply to a particular range of virtual/
343 linear addresses in the currently active address space. For example, you
344 might enter 'showmappings 0x3000 0x5000' to display the physical page
345 mappings and corresponding permission bits that apply to the pages at
346 virtual addresses 0x3000, 0x4000, and 0x5000.
347 • Explicitly set, clear, or change the permissions of any mapping in the
348 current address space.
349 • Dump the contents of a range of memory given either a virtual or physical
350 address range. Be sure the dump code behaves correctly when the range
351 extends across page boundaries!
352 • Do anything else that you think might be useful later for debugging the
353 kernel. (There's a good chance it will be!)
355 Address Space Layout Alternatives
357 Many other address space layouts are possible besides the one we chose for JOS;
358 all of this is up to the operating system. It is possible, for example, to map
359 the kernel at low linear addresses while leaving the upper part of the linear
360 address space for user processes. x86 kernels generally do not take this
361 approach, however, because one of the x86's backward-compatibility modes, known
362 as virtual 8086 mode, is "hard-wired" in the processor to use the bottom part
363 of the linear address space, and thus cannot be used at all if the kernel is
364 mapped there.
366 It is even possible, though much more difficult, to design the kernel so as not
367 to have to reserve any fixed portion of the processor's linear or virtual
368 address space for itself, but instead effectively to allow allow user-level
369 processes unrestricted use of the entire 4GB of virtual address space -- while
370 still fully protecting the kernel from these processes and protecting different
371 processes from each other!
373 Challenge! Write up an outline of how a kernel could be designed to allow user
374 environments unrestricted use of the full 4GB virtual and linear address space.
375 Hint: the technique is sometimes known as "follow the bouncing kernel" -- and
376 one of the x86's "legacy" memory features may come in handy! In your design, be
377 sure to address exactly what has to happen when the processor transitions
378 between kernel and user modes, and how the kernel would accomplish such
379 transitions. Also describe how the kernel would access physical memory and I/O
380 devices in this scheme, and how the kernel would access a user environment's
381 virtual address space during system calls and the like. Finally, think about
382 and describe the advantages and disadvantages of such a scheme in terms of
383 flexibility, performance, kernel complexity, and other factors you can think
384 of.
386 Challenge! Since our JOS kernel's memory management system only allocates and
387 frees memory on page granularity, we do not have anything comparable to a
388 general-purpose malloc/free facility that we can use within the kernel. This
389 could be a problem if we want to support certain types of I/O devices that
390 require physically contiguous buffers larger than 4KB in size, or if we want
391 user-level environments, and not just the kernel, to be able to allocate and
392 map 4MB superpages for maximum processor efficiency. (See the earlier challenge
393 problem about PTE_PS.)
395 Generalize the kernel's memory allocation system to support pages of a variety
396 of power-of-two allocation unit sizes from 4KB up to some reasonable maximum of
397 your choice. Be sure you have some way to divide larger allocation units into
398 smaller ones on demand, and to coalesce multiple small allocation units back
399 into larger units when possible. Think about the issues that might arise in
400 such a system.
402 Challenge! Extend the JOS kernel monitor with commands to allocate and free
403 pages explicitly, and display whether or not any given page of physical memory
404 is currently allocated. For example:
406 K> alloc_page
407 0x13000
408 K> page_status 0x13000
409 allocated
410 K> free_page 0x13000
411 K> page_status 0x13000
412 free
415 Think of other commands or extensions to these commands that may be useful for
416 debugging, and add them.
418 Part 3: Handling Interrupts and Exceptions
420 In this part of the lab, you'll add initial support for exception handling to
421 your JOS kernel. This includes processor exceptions, such as divide-by-zero
422 errors; hardware interrupts; and system calls, where user-level programs
423 transfer control to the kernel. (We don't have user-level programs yet, but
424 exceptions like page faults and divide-by-zero can happen in the kernel too.)
425 All of these are types of protected control transfer that, among other things,
426 enable the processor to switch from user to kernel mode cleanly without giving
427 the user-mode code any opportunity to interfere with the functioning of the
428 kernel or other environments.
430 The first thing you should do is thoroughly familiarize yourself with the x86
431 interrupt and exception mechanism. In Intel's terminology, an interrupt is a
432 protected control transfer that is caused by an asynchronous event usually
433 external to the processor, such as notification of external device I/O
434 activity. An exception, in contrast, is a protected control transfer caused
435 synchronously by the currently running code, for example due to a divide by
436 zero or an invalid memory access. In this lab we generally follow Intel's
437 terminology, but be aware that terms such as exceptions, traps, interrupts,
438 faults and aborts have no standardized meaning across architectures or
439 operating systems, and often used rather loosely without close regard to the
440 subtle distinctions between them on a particular architecture such as the x86.
441 When you see these terms outside of this lab, the meanings might be slightly
442 different.
444 Exercise 5. Read Chapter 9, Exceptions and Interrupts in the 80386 Programmer's
445 Manual (or Chapter 5 of the IA-32 Developer's Manual), if you haven't already.
447 Basics of Protected Control Transfer
449 In order to ensure that protected control transfers are actually protected, the
450 processor's interrupt/exception mechanism is designed so that the code running
451 when an interrupt or exception occurs has strictly limited influence over where
452 and how the kernel is entered. Instead, the processor ensures that the kernel
453 can be entered only under carefully controlled conditions. On the x86, this
454 protection is provided by two particular mechanisms:
456 1. The Interrupt Descriptor Table. The processor ensures that interrupts and
457 exceptions can only cause the kernel to be entered at a few specific,
458 well-defined entry-points determined by the kernel itself, and not by the
459 code currently running when the interrupt or exception is taken.
461 In particular, x86 interrupts and exceptions are differentiated into up to
462 256 possible "types", each associated with a particular interrupt number
463 (often referred to synonymously as an exception number or trap number).
464 Once the processor identifies a particular interrupt or exception to be
465 taken, it uses the interrupt number as an index into the processor's
466 interrupt descriptor table (IDT), which is a special table that the kernel
467 sets up in kernel-private memory, much like the GDT. From the appropriate
468 entry in this table the processor loads:
470 □ The value to load into the instruction pointer (EIP) register, which
471 points to the kernel code designated to handle that type of exception.
472 □ The value to load into the code segment (%cs) register, which includes
473 in bits 0-1 the privilege level at which the exception handler is to
474 run. (In JOS, all exceptions are handled in kernel mode, or privilege
475 level 0.)
476 2. The Task State Segment. In addition to having a well-defined entrypoint in
477 the kernel for an interrupt or exception handler, the processor also needs
478 a place to save the old processor state before the interrupt or exception
479 occurred, such as the original values of %eip and %cs before the processor
480 invoked the exception handler, so that the exception handler can later
481 restore that old state and resume the interrupted code from where it left
482 off. But this save area for the old processor state must in turn be
483 protected from unprivileged user-mode code; otherwise buggy or malicious
484 user code could easily compromise the kernel.
486 For this reason, when an x86 processor takes an interrupt or trap that
487 causes a privilege level change from user to kernel mode, it not only loads
488 new values into %eip and %cs, but also loads new values into the stack
489 pointer (%esp) and stack segment (%ss) registers, effectively switching to
490 a new stack private to the kernel. The processor then pushes the original
491 values of all of these registers, along with the contents of the eflags
492 register, onto this new kernel stack before starting to run the kernel's
493 exception handler code. The new %esp and %ss do not come from the IDT like
494 %eip and %cs, but instead from a separate structure called the task state
495 segment (TSS).
497 Although the TSS is a somewhat large and complex data structure that can
498 potentially serve a variety of purposes, in JOS it will only be used to
499 define the kernel stack that the processor should switch to when it
500 transfers from user to kernel mode. Since "kernel mode" in JOS is privilege
501 level 0 on the x86, the processor uses the ESP0 and SS0 fields of the TSS
502 to define the kernel stack when entering kernel mode; none of the other
503 fields in the TSS will ever ever be used in JOS.
505 Types of Exceptions and Interrupts
507 All of the synchronous exceptions that the x86 processor can generate
508 internally use interrupt numbers between 0 and 31, and therefore map to IDT
509 entries 0-31. For example, the page fault handler is "hard-wired" by Intel to
510 interrupt number 14. Interrupt numbers greater than 31 are only used by
511 software interrupts, which can be generated by the int instruction, or
512 asynchronous hardware interrupts, caused by external devices when they need
513 attention.
515 In this section we will extend JOS to handle the internally generated x86
516 exceptions in the 0-31 that are currently defined by Intel. In the next labs,
517 we'll make JOS handle software interrupt number 48, which it (fairly
518 arbitrarily) uses as its system call interrupt number, and extend it to handle
519 externally generated hardware interrupts such as the clock interrupt.
521 A Kernel-Mode Exception Example
523 Let's put these pieces together and trace through an example. Say the processor
524 is executing code in kernel mode (the low 2 bits of the %cs register are 0),
525 and encounters a divide instruction that attempts to divide by zero. Then:
527 1. The processor pushes the exception parameters on the kernel stack.
529 +-------------------+ <-- old ESP
530 | old EFLAGS | " - 4
531 | 0x0000 | old CS | " - 8
532 | old EIP | <-- ESP = old ESP - 12
533 +-------------------+
535 2. Because we're handling a divide error, which is interrupt number 0 on the
536 x86, the processor reads IDT entry 0 and sets CS:EIP to point to the
537 handler function defined there.
538 3. The handler function takes control and handles the exception.
539 4. When it's finished, the handler function can return from the interrupt by
540 executing an iret instruction.
542 For certain types of x86 exceptions, the processor pushes onto the stack
543 another word containing an error code. The page fault exception, number 14, is
544 an important example. See the 80386 manual to determine for which exception
545 numbers the processor pushes an error code, and what the error code means in
546 that case. (Exceptions 17, 18, and 19 are new since the 80386; see the IA-32
547 Architecture manual Volume 3, Section 5.) When the processor pushes an error
548 code, the stack would look as follows at the beginning of the exception
549 handler:
551 +-------------------+ <-- old ESP
552 | old EFLAGS | " - 4
553 | 0x0000 | old CS | " - 8
554 | old EIP | " - 12
555 | error code | <-- ESP = old ESP - 16
556 +-------------------+
558 There is one important caveat to the processor's kernel-mode exception
559 capability. If the processor takes an exception while already in kernel mode,
560 and cannot push its old state onto the kernel stack for any reason such as lack
561 of stack space, then there is nothing the processor can do to recover, so it
562 simply resets itself. Needless to say, any decent kernel should be designed so
563 that this will never happen unintentionally.
565 Of course, user-mode programs can divide by zero too! The processor handles
566 user-mode exceptions slightly differently to provide protection. It would not
567 be safe to simply push interrupt context information onto a user program stack.
568 (For one thing, a user program that runs out of stack space must not cause the
569 processor to reset!) Thus, when a user-mode program takes an exception, the
570 kernel switches to a special kernel stack. Information about the old stack is
571 pushed onto the exception stack first, above the old EFLAGS:
573 +-------------------+ <-- KSTACKTOP
574 | 0x0000 | old SS | " - 4
575 | old ESP | " - 8
576 | old EFLAGS | " - 12
577 | 0x0000 | old CS | " - 16
578 | old EIP | <-- ESP = KSTACKTOP - 20 (maybe)
579 | (optional errcode)| <-- ESP = KSTACKTOP - 24 (maybe)
580 +-------------------+
582 You'll handle user-mode exceptions in the next lab; just remember that there
583 are differences in calling convention between kernel-mode and user-mode
584 exceptions.
586 Setting Up the IDT
588 You should now have the basic information you need in order to set up the IDT
589 and handle exceptions in JOS. For now, you will set up the IDT to handle all
590 the to handle interrupt numbers 0-31 (the processor exceptions). We'll add
591 additional interrupts later.
593 The header files inc/trap.h and kern/trap.h contain important definitions
594 related to interrupts and exceptions that you will need to become familiar
595 with. The file kern/trap.h contains trap-related definitions that will remain
596 strictly private to the kernel, while the companion header file inc/trap.h
597 contains general definitions that may also be useful to user-level programs and
598 libraries in the system.
600 Note: Some of the exceptions in the range 0-31 are defined by Intel to be
601 reserved. Since they will never be generated by the processor, it doesn't
602 really matter how you handle them. Do whatever you think is cleanest.
604 The overall flow of control that you should achieve is depicted below:
606 IDT trapentry.S trap.c
608 +----------------+
609 | &handler1 |---------> handler1: +---> void trap(struct Trapframe *tf)
610 | | // do stuff | {
611 | | call trap -----+ // handle the exception/interrupt
612 | | <----+ return;
613 | | // undo stuff +---- }
614 +----------------+
615 | &handler2 |--------> handler2:
616 | | // do stuff
617 | | call trap
618 | | // undo stuff
619 +----------------+
620 .
621 .
622 .
623 +----------------+
624 | &handlerX |--------> handlerX:
625 | | // do stuff
626 | | call trap
627 | | // undo stuff
628 +----------------+
630 Each exception or interrupt should have its own handler in trapentry.S and
631 idt_init() should initialize the IDT with the addresses of these handlers. Each
632 of the handlers should build a struct Trapframe (see inc/trap.h) on the stack
633 and call into trap() (in trap.c) with a pointer to the Trapframe.
635 After control is passed to trap(), that function handles the exception/
636 interrupt or dispatches the exception/interrupt to a specific handler function.
637 If and when the trap() function returns, the code in trapentry.S restores the
638 old CPU state saved in the Trapframe and then uses the iret instruction to
639 return from the exception.
641 Exercise 6. Edit trapentry.S and trap.c and implement the functionality
642 described above. The macros TRAPHANDLER and TRAPHANDLER_NOEC in trapentry.S
643 should help you, as well as the T_* defines in inc/trap.h. You will need to add
644 an entry point in trapentry.S (using those macros) for each trap defined in inc
645 /trap.h. Hint: your code should perform the following steps:
647 1. Push values on the stack in the order defined by struct Trapframe and its
648 component struct PushRegs.
649 2. Load GD_KD into %ds and %es. This value is defined in <inc/memlayout.h> and
650 in pmap.c. This step isn't that important for this lab, but will become
651 vital later.
652 3. pushl %esp to pass a pointer to Trapframe that was built on the stack.
653 4. call trap.
654 5. Pop the values pushed in steps 1-3.
655 6. Clean up the stack. (How? Why?)
656 7. iret.
658 Consider using the pushal and popal instructions; they fit nicely with the
659 layout of struct PushRegs. (Remember that we draw stack diagrams with addresses
660 increasing up the page, but C structures are written with addresses increasing
661 down the page.)
663 You will also need to modify idt_init() to initialize the idt to point to each
664 of these entry points defined in trapentry.S. Check out the SETGATE macro in
665 <inc/mmu.h>.
667 Challenge! You probably have a lot of very similar code right now, between the
668 lists of TRAPHANDLERs in trapentry.S and their installations in trap.c. Clean
669 this up. Change the macros in trapentry.S to automatically generate a table for
670 trap.c to use. You will need to switch between laying down code and data in the
671 assembler by using the directives .text and .data.
673 Questions:
675 7. What is the purpose of having an individual handler function for each
676 exception/interrupt? (If all exceptions/interrupts were delivered to the
677 same handler, what functionality that exists in the current implementation
678 could not be provided?)
679 8. Why is the loading of GD_KD (Step 2 of the exercise) not important for this
680 lab, and why will it become important later?
682 The Breakpoint Exception
684 Now that your kernel has basic exception handling capabilities, you'll refine
685 its response to one particular exception. Much more of this will happen in the
686 next lab once we have user processes.
688 The breakpoint exception, interrupt number 3 (T_BRKPT), is normally used to
689 allow debuggers to insert breakpoints in a program's code by temporarily
690 replacing the relevant program instruction with the special 1-byte int3
691 software interrupt instruction. In JOS we will abuse this exception slightly by
692 turning it into a primitive pseudo-system call that anyone can use to invoke
693 the JOS kernel monitor, inside or outside the kernel. This usage is actually
694 somewhat appropriate if we think of the JOS kernel monitor as a primitive
695 debugger.
697 Exercise 7. Modify trap() to make breakpoint exceptions invoke the kernel
698 monitor.
700 Also, change the mon_backtrace() function from Lab 1 so that, when invoked
701 during a breakpoint, it prints a backtrace starting from the kernel function
702 that caused the trap. (Eventually, you will extend this to user processes too.)
703 You will use the struct Trapframe's instruction pointer component to print the
704 topmost frame. A breakpoint backtrace should look something like this (note the
705 different format for frame 0):
707 Stack backtrace:
708 0: eip f0100047
709 kern/init.c:46: _ZL22test_kernel_breakpointv+ac7 (0 arg)
710 1: ebp f0117fd8 eip f0100145 args f0104169 00001aac 00000000 00000000
711 kern/init.c:215: i386_init+4c (0 arg)
712 2: ebp f0117ff8 eip f010003d args 00000000 00000000 0000ffff 10cf9a00
713 kern/entry.S:79: <unknown>+0 (0 arg)
715 Finally, add an "exit" command to the kernel monitor that exits the kernel
716 monitor, returning from the interrupt. Make sure that you can safely exit a
717 breakpoint kernel monitor. When you are done, make grade should return 100/100.
719 Challenge! Modify the JOS kernel monitor so that you can step execution from
720 the current location (e.g., after the int3, if the kernel monitor was invoked
721 via the breakpoint exception), one instruction at a time. You will need to
722 understand certain bits of the EFLAGS register in order to implement
723 single-stepping.
725 Optional: If you're feeling really adventurous, find some x86 disassembler
726 source code - e.g., by ripping it out of Bochs, or out of GNU binutils, or just
727 write it yourself - and extend the JOS kernel monitor to be able to disassemble
728 and display instructions as you are stepping through them. Combined with the
729 symbol table loading functionality suggested by one of the challenge problems
730 in the previous lab, this is the stuff of which real kernel debuggers are made.
732 This completes the lab.
734 Back to CS 235 Advanced Operating Systems