-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLab 3_ User Environments.html
More file actions
1589 lines (1417 loc) · 65.2 KB
/
Lab 3_ User Environments.html
File metadata and controls
1589 lines (1417 loc) · 65.2 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html style="--wm-toolbar-height: 67px;"><head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8"><script src="Lab%203_%20User%20Environments_files/athena.js" type="text/javascript"></script>
<script type="text/javascript">window.addEventListener('DOMContentLoaded',function(){var v=archive_analytics.values;v.service='wb';v.server_name='wwwb-app213.us.archive.org';v.server_ms=420;archive_analytics.send_pageview({});});</script>
<script type="text/javascript" src="Lab%203_%20User%20Environments_files/bundle-playback.js" charset="utf-8"></script>
<script type="text/javascript" src="Lab%203_%20User%20Environments_files/wombat.js" charset="utf-8"></script>
<script>window.RufflePlayer=window.RufflePlayer||{};window.RufflePlayer.config={"autoplay":"on","unmuteOverlay":"hidden","showSwfDownload":true};</script>
<script type="text/javascript" src="Lab%203_%20User%20Environments_files/ruffle.js"></script>
<script type="text/javascript">
__wm.init("https://web.archive.org/web");
__wm.wombat("https://pdos.csail.mit.edu/6.828/2018/labs/lab3/","20250420202206","https://web.archive.org/","web","https://web-static.archive.org/_static/",
"1745180526");
</script>
<link rel="stylesheet" type="text/css" href="Lab%203_%20User%20Environments_files/banner-styles.css">
<link rel="stylesheet" type="text/css" href="Lab%203_%20User%20Environments_files/iconochive.css">
<!-- End Wayback Rewrite JS Include -->
<title>Lab 3: User Environments</title>
<link rel="stylesheet" href="Lab%203_%20User%20Environments_files/labs.css" type="text/css">
<script type="text/javascript" src="Lab%203_%20User%20Environments_files/labs.js"></script>
<!-- MIT 6.828 实验文档现代化增强 -->
<link rel="stylesheet" href="labs-modern.css" type="text/css">
<script src="labs-enhance.js"></script>
</head>
<body data-new-gr-c-s-check-loaded="8.933.0" data-gr-ext-installed=""><div class="jump-hdr"><div class="jump-section">Sections ▿<div class="jump-drop"><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Introduction" style="padding-left: 1em; background: rgb(192, 192, 255);">Introduction</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Getting-Started" style="padding-left: 2em;">Getting Started</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Lab-Requirements" style="padding-left: 2em;">Lab Requirements</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Inline-Assembly" style="padding-left: 2em;">Inline Assembly</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Part-A--User-Environments-and-Exception-Handling" style="padding-left: 1em;">Part A: User Environments and Exception Handling</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Environment-State" style="padding-left: 2em;">Environment State</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Allocating-the-Environments-Array" style="padding-left: 2em;">Allocating the Environments Array</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Creating-and-Running-Environments" style="padding-left: 2em;">Creating and Running Environments</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Handling-Interrupts-and-Exceptions" style="padding-left: 2em;">Handling Interrupts and Exceptions</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Basics-of-Protected-Control-Transfer" style="padding-left: 2em;">Basics of Protected Control Transfer</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Types-of-Exceptions-and-Interrupts" style="padding-left: 2em;">Types of Exceptions and Interrupts</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#An-Example" style="padding-left: 2em;">An Example</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Nested-Exceptions-and-Interrupts" style="padding-left: 2em;">Nested Exceptions and Interrupts</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Setting-Up-the-IDT" style="padding-left: 2em;">Setting Up the IDT</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Part-B--Page-Faults--Breakpoints-Exceptions--and-System-Calls" style="padding-left: 1em;">Part B: Page Faults, Breakpoints Exceptions, and System Calls</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Handling-Page-Faults" style="padding-left: 2em;">Handling Page Faults</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#The-Breakpoint-Exception" style="padding-left: 2em;">The Breakpoint Exception</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#System-calls" style="padding-left: 2em;">System calls</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#User-mode-startup" style="padding-left: 2em;">User-mode startup</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Page-faults-and-memory-protection" style="padding-left: 2em;">Page faults and memory protection</a></div></div><div class="jump-section">Exercises ▿<div class="jump-drop"><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Exercise-1">Exercise 1</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Exercise-2">Exercise 2</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Exercise-3">Exercise 3</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Exercise-4">Exercise 4</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Exercise-5">Exercise 5</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Exercise-6">Exercise 6</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Exercise-7">Exercise 7</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Exercise-8">Exercise 8</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Exercise-9">Exercise 9</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/#Exercise-10">Exercise 10</a></div></div><div class="jump-section">References ▿<div class="jump-drop"><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labguide.html">Lab tools guide</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/readings/i386/toc.htm">80386 manual</a><div>IA32</div><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/readings/ia32/IA32-1.pdf" style="padding-left: 1em;">Basic architecture</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/readings/ia32/IA32-2A.pdf" style="padding-left: 1em;">Instruction set A-M</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/readings/ia32/IA32-2B.pdf" style="padding-left: 1em;">Instruction set N-Z</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/readings/ia32/IA32-3A.pdf" style="padding-left: 1em;">System programming 1</a><a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/readings/ia32/IA32-3B.pdf" style="padding-left: 1em;">System programming 2</a></div></div></div><!-- BEGIN WAYBACK TOOLBAR INSERT -->
<script>__wm.rw(0);</script>
<div id="wm-ipp-base" lang="en" style="display: block; direction: ltr; height: 67px;" toolbar-mode="auto">
</div><div id="wm-ipp-print">The Wayback Machine - https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labs/lab3/</div>
<script type="text/javascript">//<![CDATA[
__wm.bt(750,27,25,2,"web","https://pdos.csail.mit.edu/6.828/2018/labs/lab3/","20250420202206",1996,"https://web-static.archive.org/_static/",["https://web-static.archive.org/_static/css/banner-styles.css?v=p7PEIJWi","https://web-static.archive.org/_static/css/iconochive.css?v=3PDvdIFv"], false);
__wm.rw(1);
//]]></script>
<!-- END WAYBACK TOOLBAR INSERT -->
<h1>Lab 3: User Environments</h1>
<p>
<b>
Part A due Thursday, October 4, 2018 <br>
Part B due Thursday, October 11, 2018
</b>
</p>
<h2 id="Introduction">Introduction</h2>
<p>
In this lab you will implement the basic kernel facilities
required to get a protected user-mode environment (i.e., "process") running.
You will enhance the JOS kernel
to set up the data structures to keep track of user environments,
create a single user environment,
load a program image into it,
and start it running.
You will also make the JOS kernel capable
of handling any system calls the user environment makes
and handling any other exceptions it causes.
</p>
<p>
<b>Note:</b>
In this lab, the terms <i>environment</i> and <i>process</i> are
interchangeable - both refer to an abstraction that allows you to run a program. We introduce the
term "environment" instead of the traditional term "process"
in order to stress the point that JOS environments and UNIX processes
provide different interfaces, and do not provide
the same semantics.
</p>
<h3 id="Getting-Started">Getting Started</h3>
<p>
Use Git to commit your changes after your Lab 2 submission (if any),
fetch the latest version of the course repository,
and then
create a local branch called <tt>lab3</tt> based on our lab3
branch, <tt>origin/lab3</tt>:
</p>
<pre>athena% <kbd>cd ~/6.828/lab</kbd>
athena% <kbd>add git</kbd>
athena% <kbd>git commit -am 'changes to lab2 after handin'</kbd>
Created commit 734fab7: changes to lab2 after handin
4 files changed, 42 insertions(+), 9 deletions(-)
athena% <kbd>git pull</kbd>
Already up-to-date.
athena% <kbd>git checkout -b lab3 origin/lab3</kbd>
Branch lab3 set up to track remote branch refs/remotes/origin/lab3.
Switched to a new branch "lab3"
athena% <kbd>git merge lab2</kbd>
Merge made by recursive.
kern/pmap.c | 42 +++++++++++++++++++
1 files changed, 42 insertions(+), 0 deletions(-)
athena%
</pre>
<p>
Lab 3 contains a number of new source files,
which you should browse:
</p>
<table align="center">
<tbody><tr> <td> <tt>inc/</tt></td>
<td> <tt>env.h</tt></td>
<td> Public definitions for user-mode environments</td></tr>
<tr> <td></td>
<td> <tt>trap.h</tt></td>
<td> Public definitions for trap handling</td></tr>
<tr> <td></td>
<td> <tt>syscall.h</tt></td>
<td> Public definitions for system calls
from user environments to the kernel</td></tr>
<tr> <td></td>
<td> <tt>lib.h</tt></td>
<td> Public definitions for the user-mode support library</td></tr>
<tr> <td> <tt>kern/</tt></td>
<td> <tt>env.h</tt></td>
<td> Kernel-private definitions for user-mode environments</td></tr>
<tr> <td></td>
<td> <tt>env.c</tt></td>
<td> Kernel code implementing user-mode environments</td></tr>
<tr> <td></td>
<td> <tt>trap.h</tt></td>
<td> Kernel-private trap handling definitions</td></tr>
<tr> <td></td>
<td> <tt>trap.c</tt></td>
<td> Trap handling code</td></tr>
<tr> <td></td>
<td> <tt>trapentry.S</tt></td>
<td> Assembly-language trap handler entry-points</td></tr>
<tr> <td></td>
<td> <tt>syscall.h</tt></td>
<td> Kernel-private definitions for system call handling</td></tr>
<tr> <td></td>
<td> <tt>syscall.c</tt></td>
<td> System call implementation code</td></tr>
<tr> <td> <tt>lib/</tt></td>
<td> <tt>Makefrag</tt></td>
<td> Makefile fragment to build user-mode library,
<tt>obj/lib/libjos.a</tt></td></tr>
<tr> <td></td>
<td> <tt>entry.S</tt></td>
<td> Assembly-language entry-point for user environments</td></tr>
<tr> <td></td>
<td> <tt>libmain.c</tt></td>
<td> User-mode library setup code called from <tt>entry.S</tt></td></tr>
<tr> <td></td>
<td> <tt>syscall.c</tt></td>
<td> User-mode system call stub functions</td></tr>
<tr> <td></td>
<td> <tt>console.c</tt></td>
<td> User-mode implementations of
<tt>putchar</tt> and <tt>getchar</tt>,
providing console I/O</td></tr>
<tr> <td></td>
<td> <tt>exit.c</tt></td>
<td> User-mode implementation of <tt>exit</tt></td></tr>
<tr> <td></td>
<td> <tt>panic.c</tt></td>
<td> User-mode implementation of <tt>panic</tt></td></tr>
<tr> <td> <tt>user/</tt></td>
<td> <tt>*</tt></td>
<td> Various test programs to check kernel lab 3 code</td></tr>
</tbody></table>
<p>
In addition, a number of the source files we handed out for lab2
are modified in lab3.
To see the differences, you can type:
</p>
<pre>$ <kbd>git diff lab2</kbd>
</pre>
<p>
You may also want to take another look at the <a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/labguide.html">lab tools guide</a>, as it includes
information on debugging user code that becomes relevant in this lab.
</p>
<h3 id="Lab-Requirements">Lab Requirements</h3>
<p>
This lab is divided into two parts, A and B.
Part A is due a week after this lab was assigned;
you should commit your changes and <kbd>make handin</kbd>
your lab before the Part A deadline,
making sure your code passes all of the Part A tests (it is okay
if your code does not pass the Part B tests yet).
You only need to have the Part B tests passing
by the Part B deadline at the end of the second week.
</p>
<p>
As in lab 2,
you will need to do all of the regular exercises described in the lab
and <i>at least one</i> challenge problem (for the entire lab, not for
each part).
Write up brief answers
to the questions posed in the lab
and a one or two paragraph description of what you did
to solve your chosen challenge problem
in a file called <tt>answers-lab3.txt</tt>
in the top level of your <tt>lab</tt> directory.
(If you implement more than one challenge problem,
you only need to describe one of them in the write-up.)
Do not forget to include the answer file in your submission with
<kbd>git add answers-lab3.txt</kbd>.
</p>
<!--
<p>
Passing all the <kbd>make grade</kbd> tests
does not mean your code is perfect. It may have subtle bugs that will
only be tickled by future labs.
In particular, all your kernel code is running in the same address
space with no protection. If you get weird crashes
that don't seem to be explainable by a bug in the crashing code,
it's likely that they're due to a bug somewhere else that is
modifying memory used by the crashing code.
GDB watchpoints are often a good way to debug such problems.
</p>
-->
<h3 id="Inline-Assembly">Inline Assembly</h3>
<p>
In this lab you may find GCC's inline assembly language feature useful,
although it is also possible to complete the lab without using it.
At the very least, you will need to be able to understand
the fragments of inline assembly language ("<tt>asm</tt>" statements)
that already exist in the source code we gave you.
You can find several sources of information
on GCC inline assembly language
on the class <a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/reference.html">reference materials</a> page.
</p>
<h2 id="Part-A--User-Environments-and-Exception-Handling">Part A: User Environments and Exception Handling</h2>
<p>
The new include file <tt>inc/env.h</tt>
contains basic definitions for user environments in JOS.
Read it now.
The kernel uses the <code>Env</code> data structure
to keep track of each user environment.
In this lab you will initially create just one environment,
but you will need to design the JOS kernel
to support multiple environments;
lab 4 will take advantage of this feature
by allowing a user environment to <code>fork</code> other environments.
</p>
<p>
As you can see in <tt>kern/env.c</tt>,
the kernel maintains three main global variables
pertaining to environments:
</p>
<pre>struct Env *envs = NULL; // All environments
struct Env *curenv = NULL; // The current env
static struct Env *env_free_list; // Free environment list
</pre>
<p>
Once JOS gets up and running,
the <code>envs</code> pointer points to an array of <code>Env</code> structures
representing all the environments in the system.
In our design,
the JOS kernel will support a maximum of <code>NENV</code>
simultaneously active environments,
although there will typically be far fewer running environments
at any given time.
(<code>NENV</code> is a constant <code>#define</code>'d in <tt>inc/env.h</tt>.)
Once it is allocated,
the <code>envs</code> array will contain
a single instance of the <code>Env</code> data structure
for each of the <code>NENV</code> possible environments.
</p>
<p>
The JOS kernel keeps all of the inactive <code>Env</code> structures
on the <code>env_free_list</code>.
This design allows easy allocation and
deallocation of environments,
as they merely have to be added to or removed from the free list.
</p>
<p>
The kernel uses the <code>curenv</code> symbol
to keep track of the <i>currently executing</i> environment at any given time.
During boot up, before the first environment is run,
<code>curenv</code> is initially set to <code>NULL</code>.
</p>
<h3 id="Environment-State">Environment State</h3>
<p>
The <code>Env</code> structure
is defined in <tt>inc/env.h</tt> as follows
(although more fields will be added in future labs):
</p>
<pre>struct Env {
struct Trapframe env_tf; // Saved registers
struct Env *env_link; // Next free Env
envid_t env_id; // Unique environment identifier
envid_t env_parent_id; // env_id of this env's parent
enum EnvType env_type; // Indicates special system environments
unsigned env_status; // Status of the environment
uint32_t env_runs; // Number of times environment has run
// Address space
pde_t *env_pgdir; // Kernel virtual address of page dir
};
</pre>
<p>
Here's what the <code>Env</code> fields are for:
</p>
<dl>
<dt><b>env_tf</b>:</dt>
<dd> This structure, defined in <tt>inc/trap.h</tt>,
holds the saved register values for the environment
while that environment is <i>not</i> running:
i.e., when the kernel or a different environment is running.
The kernel saves these when
switching from user to kernel mode,
so that the environment can later be resumed where it left off.</dd>
<dt><b>env_link</b>:</dt>
<dd> This is a link to the next <code>Env</code> on the
<code>env_free_list</code>. <code>env_free_list</code> points
to the first free environment on the list.</dd>
<dt><b>env_id</b>:</dt>
<dd> The kernel stores here a value
that uniquely identifiers
the environment currently using this <code>Env</code> structure
(i.e., using this particular slot in the <code>envs</code> array).
After a user environment terminates,
the kernel may re-allocate
the same <code>Env</code> structure to a different environment -
but the new environment
will have a different <code>env_id</code> from the old one
even though the new environment
is re-using the same slot in the <code>envs</code> array.</dd>
<dt><b>env_parent_id</b>:</dt>
<dd> The kernel stores here the <code>env_id</code>
of the environment that created this environment.
In this way the environments can form a “family tree,”
which will be useful for making security decisions
about which environments are allowed to do what to whom.</dd>
<dt><b>env_type</b>:</dt>
<dd> This is used to distinguish special environments. For most
environments, it will be <code>ENV_TYPE_USER</code>. We'll introduce
a few more types for special system service environments in later labs.
</dd>
<dt><b>env_status</b>:</dt>
<dd> This variable holds one of the following values:
<dl>
<dt><code>ENV_FREE</code>:</dt>
<dd> Indicates that the <code>Env</code> structure is inactive,
and therefore on the <code>env_free_list</code>.</dd>
<dt><code>ENV_RUNNABLE</code>:</dt>
<dd> Indicates that the <code>Env</code> structure
represents an environment that is waiting to run on the
processor.</dd>
<dt><code>ENV_RUNNING</code>:</dt>
<dd> Indicates that the <code>Env</code> structure
represents the currently running environment.</dd>
<dt><code>ENV_NOT_RUNNABLE</code>:</dt>
<dd> Indicates that the <code>Env</code> structure
represents a currently active environment,
but it is not currently ready to run:
for example, because it is waiting
for an interprocess communication (IPC)
from another environment.</dd>
<dt><code>ENV_DYING</code>:</dt>
<dd> Indicates that the <code>Env</code> structure
represents a zombie environment. A zombie environment will be
freed the next time it traps to the kernel. We will not use
this flag until Lab 4.</dd>
</dl></dd>
<dt><b>env_pgdir</b>:</dt>
<dd> This variable holds the kernel <i>virtual address</i>
of this environment's page directory.</dd>
</dl>
<p>
Like a Unix process, a JOS environment couples the concepts of
"thread" and "address space". The thread is defined primarily by the
saved registers (the <code>env_tf</code> field), and the address space
is defined by the page directory and page tables pointed to by
<code>env_pgdir</code>. To run an
environment, the kernel must set up the CPU with <i>both</i> the saved
registers and the appropriate address space.
</p>
<p>
Our <code>struct Env</code> is analogous to <code>struct proc</code>
in xv6. Both structures hold the environment's (i.e., process's)
user-mode register state in a <code>Trapframe</code>
structure. In JOS,
individual environments do not have their own kernel stacks as
processes do in xv6. There can be only one JOS environment active in
the kernel at a time, so JOS needs only a
<i>single</i> kernel stack.
</p>
<h3 id="Allocating-the-Environments-Array">Allocating the Environments Array</h3>
<p>
In lab 2,
you allocated memory in <code>mem_init()</code>
for the <code>pages[]</code> array,
which is a table the kernel uses to keep track of
which pages are free and which are not.
You will now need to modify <code>mem_init()</code> further
to allocate a similar array of <code>Env</code> structures,
called <code>envs</code>.
</p>
<div class="required"><div id="Exercise-1" style="position: relative; top: -5em;"></div>
<p><span class="header">Exercise 1.</span>
Modify <code>mem_init()</code> in <tt>kern/pmap.c</tt>
to allocate and map the <code>envs</code> array.
This array consists of
exactly <code>NENV</code> instances of the <code>Env</code>
structure allocated much like how you allocated the
<code>pages</code> array.
Also like the <code>pages</code> array, the memory backing
<code>envs</code> should also be mapped user read-only at
<code>UENVS</code> (defined in <tt>inc/memlayout.h</tt>) so
user processes can read from this array.
</p>
<p>
You should run your code and make sure
<code>check_kern_pgdir()</code> succeeds.
</p></div>
<h3 id="Creating-and-Running-Environments">Creating and Running Environments</h3>
<p>
You will now write the code in <tt>kern/env.c</tt> necessary to run a
user environment. Because we do not yet have a filesystem, we will
set up the kernel to load a static binary image that is <i>embedded
within the kernel itself</i>. JOS embeds
this binary in the kernel as a ELF executable image.
</p>
<p>
The Lab 3 <tt>GNUmakefile</tt> generates a number of binary images in
the <tt>obj/user/</tt> directory. If you look at
<tt>kern/Makefrag</tt>, you will notice some magic that "links" these
binaries directly into the kernel executable as if they were
<tt>.o</tt> files. The <tt>-b binary</tt> option on the linker
command line causes these files to be linked in as "raw" uninterpreted
binary files rather than as regular <tt>.o</tt> files produced by the
compiler. (As far as the linker is concerned, these files do not have
to be ELF images at all - they could be anything, such as text files
or pictures!) If you look at <tt>obj/kern/kernel.sym</tt> after
building the kernel, you will notice that the linker has "magically"
produced a number of funny symbols with obscure names like
<tt>_binary_obj_user_hello_start</tt>,
<tt>_binary_obj_user_hello_end</tt>, and
<tt>_binary_obj_user_hello_size</tt>. The linker generates these
symbol names by mangling the file names of the binary files; the
symbols provide the regular kernel code with a way to reference the
embedded binary files.
</p>
<p>
In <code>i386_init()</code> in <tt>kern/init.c</tt> you'll see code to run
one of these binary images in an environment. However, the critical
functions to set up user environments are not complete; you will need
to fill them in.
</p>
<div class="required"><div id="Exercise-2" style="position: relative; top: -5em;"></div>
<p><span class="header">Exercise 2.</span>
In the file <tt>env.c</tt>,
finish coding the following functions:
</p>
<dl>
<dt> <code>env_init()</code></dt>
<dd> Initialize all of the <code>Env</code> structures
in the <code>envs</code> array and
add them to the <code>env_free_list</code>.
Also calls <code>env_init_percpu</code>, which
configures the segmentation hardware with
separate segments for privilege level 0 (kernel) and
privilege level 3 (user).</dd>
<dt> <code>env_setup_vm()</code></dt>
<dd> Allocate a page directory for a new environment
and initialize the kernel portion
of the new environment's address space.</dd>
<dt> <code>region_alloc()</code></dt>
<dd> Allocates and maps physical memory for an environment</dd>
<dt> <code>load_icode()</code></dt>
<dd> You will need to parse an ELF binary image,
much like the boot loader already does,
and load its contents into the user address space
of a new environment.</dd>
<dt> <code>env_create()</code></dt>
<dd> Allocate an environment with <code>env_alloc</code>
and call <code>load_icode</code> to load an ELF binary into it.</dd>
<dt> <code>env_run()</code></dt>
<dd> Start a given environment running in user mode.</dd>
</dl>
<p>
As you write these functions,
you might find the new cprintf verb <code>%e</code>
useful -- it prints a description corresponding to an error code.
For example,
</p>
<pre> r = -E_NO_MEM;
panic("env_alloc: %e", r);</pre>
<p>
will panic with the message "env_alloc: out of memory".
</p>
</div>
<p>
Below is a call graph of the code up to the point where the user
code is invoked.
Make sure you understand the purpose of each step.
</p>
<ul>
<li> <code>start</code> (<code>kern/entry.S</code>)</li>
<li> <code>i386_init</code> (<code>kern/init.c</code>)
<ul>
<li> <code>cons_init</code></li>
<li> <code>mem_init</code></li>
<li> <code>env_init</code></li>
<li> <code>trap_init</code> (still incomplete at this point)</li>
<li> <code>env_create</code></li>
<li> <code>env_run</code>
<ul>
<li> <code>env_pop_tf</code></li>
</ul>
</li>
</ul>
</li>
</ul>
<p>
Once you are done you should compile your kernel and run it under QEMU.
If all goes well, your system should enter user space and execute the
<tt>hello</tt> binary until it makes a system call with the
<code>int</code> instruction. At that point there will be trouble, since
JOS has not set up the hardware to allow any kind of transition
from user space into the kernel.
When the CPU discovers that it is not set up to handle this system
call interrupt, it will generate a general protection exception, find
that it can't handle that, generate a double fault exception, find
that it can't handle that either, and finally give up with what's
known as a "triple fault". Usually, you would then see the CPU reset
and the system reboot. While this is important for legacy
applications (see <a href="https://web.archive.org/web/20250420202206/http://blogs.msdn.com/larryosterman/archive/2005/02/08/369243.aspx">
this blog post</a> for an explanation of why), it's a pain for kernel
development, so with the 6.828 patched QEMU you'll instead see a
register dump and a "Triple fault." message.
</p>
<p>
We'll address this problem shortly, but for now we can use the
debugger to check that we're entering user mode. Use <kbd>make
qemu-gdb</kbd> and set a GDB breakpoint at <code>env_pop_tf</code>,
which should be the last function you hit before actually entering user mode.
Single step through this function using <kbd>si</kbd>;
the processor should enter user mode after the <code>iret</code> instruction.
You should then see the first instruction
in the user environment's executable,
which is the <code>cmpl</code> instruction at the label <code>start</code>
in <tt>lib/entry.S</tt>.
Now use <kbd>b *0x...</kbd> to set a breakpoint at the
<code>int $0x30</code> in <code>sys_cputs()</code> in <tt>hello</tt>
(see <tt>obj/user/hello.asm</tt> for the user-space address).
This <code>int</code> is the system call to display a character to
the console.
If you cannot execute as far as the <code>int</code>,
then something is wrong with your address space setup
or program loading code;
go back and fix it before continuing.
</p>
<h3 id="Handling-Interrupts-and-Exceptions">Handling Interrupts and Exceptions</h3>
<p>
At this point,
the first <code>int $0x30</code> system call instruction in user space
is a dead end:
once the processor gets into user mode,
there is no way to get back out.
You will now need to implement
basic exception and system call handling,
so that it is possible for the kernel to recover control of the processor
from user-mode code.
The first thing you should do
is thoroughly familiarize yourself with
the x86 interrupt and exception mechanism.
</p>
<div class="required"><div id="Exercise-3" style="position: relative; top: -5em;"></div>
<p><span class="header">Exercise 3.</span>
Read
<a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/readings/i386/c09.htm">
Chapter 9, Exceptions and Interrupts</a>
in the
<a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/readings/i386/toc.htm">80386 Programmer's Manual</a>
(or Chapter 5 of the <a href="https://web.archive.org/web/20250420202206/https://pdos.csail.mit.edu/6.828/2018/readings/ia32/IA32-3A.pdf">
IA-32 Developer's Manual</a>),
if you haven't already.
</p></div>
<p>
In this lab we generally follow Intel's terminology
for interrupts, exceptions, and the like.
However,
terms such as exception, trap, interrupt, fault and
abort have no standard meaning
across architectures or operating systems,
and are often used without regard to the subtle distinctions between them
on a particular architecture such as the x86.
When you see these terms outside of this lab,
the meanings might be slightly different.
</p>
<h3 id="Basics-of-Protected-Control-Transfer">Basics of Protected Control Transfer</h3>
<p>
Exceptions and interrupts are both
"protected control transfers,"
which cause the processor to switch from user to kernel mode
(CPL=0) without giving the user-mode code any opportunity
to interfere with the functioning of the kernel or other environments.
In Intel's terminology,
an <i>interrupt</i> is a protected control transfer
that is caused by an asynchronous event usually external to the processor,
such as notification of external device I/O activity.
An <i>exception</i>, in contrast,
is a protected control transfer
caused synchronously by the currently running code,
for example due to a divide by zero or an invalid memory access.
</p>
<p>
In order to ensure that these protected control transfers
are actually <i>protected</i>,
the processor's interrupt/exception mechanism is designed so that
the code currently running when the interrupt or exception occurs
<i>does not get to choose arbitrarily where the kernel is entered or how</i>.
Instead,
the processor ensures that the kernel can be entered
only under carefully controlled conditions.
On the x86, two mechanisms work together to provide this protection:
</p>
<ol>
<li><p> <b>The Interrupt Descriptor Table.</b>
The processor ensures that interrupts and exceptions
can only cause the kernel to be entered
at a few specific, well-defined entry-points
<i>determined by the kernel itself</i>,
and not by the code running
when the interrupt or exception is taken.
</p>
<p>
The x86 allows up to 256 different
interrupt or exception entry points into the kernel,
each with a different <i>interrupt vector</i>.
A vector is a number between 0 and 255.
An interrupt's vector is determined by the
source of the interrupt: different devices, error
conditions, and application requests to the kernel
generate interrupts with different vectors.
The CPU uses the vector as an index
into the processor's <i>interrupt descriptor table</i> (IDT),
which the kernel sets up in kernel-private memory,
much like the GDT.
From the appropriate entry in this table
the processor loads:
</p>
<ul>
<li> the value to load into
the instruction pointer (<tt>EIP</tt>) register,
pointing to the kernel code designated
to handle that type of exception.</li>
<li> the value to load into
the code segment (<tt>CS</tt>) register,
which includes in bits 0-1 the privilege level
at which the exception handler is to run.
(In JOS, all exceptions are handled in kernel mode,
privilege level 0.)</li>
</ul>
</li>
<li><p> <b>The Task State Segment.</b>
The processor needs a place
to save the <i>old</i> processor state
before the interrupt or exception occurred,
such as the original values of <tt>EIP</tt> and <tt>CS</tt>
before the processor invoked the exception handler,
so that the exception handler can later restore that old state
and resume the interrupted code from where it left off.
But this save area for the old processor state
must in turn be protected from unprivileged user-mode code;
otherwise buggy or malicious user code
could compromise the kernel.
</p>
<p>
For this reason,
when an x86 processor takes an interrupt or trap
that causes a privilege level change from user to kernel mode,
it also switches to a stack in the kernel's memory.
A structure called the <i>task state segment</i> (TSS) specifies
the segment selector and address where this stack lives.
The processor pushes (on this new stack)
<tt>SS</tt>, <tt>ESP</tt>, <tt>EFLAGS</tt>, <tt>CS</tt>, <tt>EIP</tt>, and an optional error code.
Then it loads the <tt>CS</tt> and <tt>EIP</tt> from the interrupt descriptor,
and sets the <tt>ESP</tt> and <tt>SS</tt> to refer to the new stack.
</p>
<p>
Although the TSS is large
and can potentially serve a variety of purposes,
JOS only uses it to define
the kernel stack that the processor should switch to
when it transfers from user to kernel mode.
Since "kernel mode" in JOS
is privilege level 0 on the x86,
the processor uses the <tt>ESP0</tt> and <tt>SS0</tt> fields of the TSS
to define the kernel stack when entering kernel mode.
JOS doesn't use any other TSS fields.
</p>
</li>
</ol>
<h3 id="Types-of-Exceptions-and-Interrupts">Types of Exceptions and Interrupts</h3>
<p>
All of the synchronous exceptions
that the x86 processor can generate internally
use interrupt vectors between 0 and 31,
and therefore map to IDT entries 0-31.
For example,
a page fault always causes an exception through vector 14.
Interrupt vectors greater than 31 are only used by
<i>software interrupts</i>,
which can be generated by the <code>int</code> instruction, or
asynchronous <i>hardware interrupts</i>,
caused by external devices when they need attention.
</p>
<p>
In this section we will extend JOS to handle
the internally generated x86 exceptions in vectors 0-31.
In the next section we will make JOS handle
software interrupt vector 48 (0x30),
which JOS (fairly arbitrarily) uses as its system call interrupt vector.
In Lab 4 we will extend JOS to handle externally generated hardware interrupts
such as the clock interrupt.
</p>
<h3 id="An-Example">An Example</h3>
<p>
Let's put these pieces together and trace through an example.
Let's say the processor is executing code in a user environment
and encounters a divide instruction that attempts to divide by zero.
</p>
<ol>
<li> The processor switches to the stack defined by the
<tt>SS0</tt> and <tt>ESP0</tt> fields of the TSS,
which in JOS will hold the values
<code>GD_KD</code> and <code>KSTACKTOP</code>, respectively.</li>
<li> The processor pushes the exception parameters on the
kernel stack, starting at address <code>KSTACKTOP</code>:
<pre> +--------------------+ KSTACKTOP
| 0x00000 | old SS | " - 4
| old ESP | " - 8
| old EFLAGS | " - 12
| 0x00000 | old CS | " - 16
| old EIP | " - 20 <---- ESP
+--------------------+
</pre></li>
<li> Because we're handling a divide error,
which is interrupt vector 0 on the x86,
the processor reads IDT entry 0 and sets
<tt>CS:EIP</tt> to point to the handler function described by
the entry.</li>
<li> The handler function takes control and handles the exception,
for example by terminating the user environment.</li>
</ol>
<p>
For certain types of x86 exceptions,
in addition to the "standard" five words above,
the processor pushes onto the stack another word
containing an <i>error code</i>.
The page fault exception, number 14,
is an important example.
See the 80386 manual to determine for which exception numbers
the processor pushes an error code,
and what the error code means in that case.
When the processor pushes an error code,
the stack would look as follows at the beginning of the exception handler
when coming in from user mode:
</p>
<pre> +--------------------+ KSTACKTOP
| 0x00000 | old SS | " - 4
| old ESP | " - 8
| old EFLAGS | " - 12
| 0x00000 | old CS | " - 16
| old EIP | " - 20
| error code | " - 24 <---- ESP
+--------------------+
</pre>
<h3 id="Nested-Exceptions-and-Interrupts">Nested Exceptions and Interrupts</h3>
<p>
The processor can take exceptions and interrupts
both from kernel and user mode.
It is only when entering the kernel from user mode, however,
that the x86 processor automatically switches stacks
before pushing its old register state onto the stack
and invoking the appropriate exception handler through the IDT.
If the processor is <i>already</i> in kernel mode
when the interrupt or exception occurs
(the low 2 bits of the <tt>CS</tt> register are already zero),
then the CPU just pushes more values on the same kernel stack.
In this way, the kernel can gracefully handle <i>nested exceptions</i>
caused by code within the kernel itself.
This capability is an important tool in implementing protection,
as we will see later in the section on system calls.
</p>
<p>
If the processor is already in kernel mode
and takes a nested exception,
since it does not need to switch stacks,
it does not save the old <tt>SS</tt> or <tt>ESP</tt> registers.
For exception types that do not push an error code,
the kernel stack therefore looks like the following
on entry to the exception handler:
</p>
<pre> +--------------------+ <---- old ESP
| old EFLAGS | " - 4
| 0x00000 | old CS | " - 8
| old EIP | " - 12
+--------------------+
</pre>
<p>
For exception types that push an error code,
the processor pushes the error code immediately after the old <tt>EIP</tt>,
as before.
</p>
<p>
There is one important caveat to the processor's nested exception capability.
If the processor takes an exception while already in kernel mode,
and <i>cannot push its old state onto the kernel stack</i> for any reason
such as lack of stack space,
then there is nothing the processor can do to recover,
so it simply resets itself.
Needless to say, the kernel should be designed so that this can't happen.
</p>
<h3 id="Setting-Up-the-IDT">Setting Up the IDT</h3>
<p>
You should now have the basic information you need
in order to set up the IDT and handle exceptions in JOS.
For now, you will set up the IDT to handle
interrupt vectors 0-31 (the processor exceptions).
We'll handle system call interrupts later in this lab and add
interrupts 32-47 (the device IRQs) in a later lab.
</p>
<p>
The header files <tt>inc/trap.h</tt> and <tt>kern/trap.h</tt>
contain important definitions related to interrupts and exceptions
that you will need to become familiar with.
The file <tt>kern/trap.h</tt> contains definitions
that are strictly private to the kernel,
while <tt>inc/trap.h</tt>
contains definitions that may also be useful
to user-level programs and libraries.
</p>
<p>
Note:
Some of the exceptions in the range 0-31 are defined by Intel to be
reserved.
Since they will never be generated by the processor,
it doesn't really matter how you handle them.
Do whatever you think is cleanest.
</p>
<p>
The overall flow of control that you should achieve is depicted below:
</p>
<pre> IDT trapentry.S trap.c
+----------------+
| &handler1 |---------> handler1: trap (struct Trapframe *tf)
| | // do stuff {
| | call trap // handle the exception/interrupt
| | // ... }
+----------------+
| &handler2 |--------> handler2:
| | // do stuff
| | call trap
| | // ...
+----------------+
.
.
.
+----------------+
| &handlerX |--------> handlerX:
| | // do stuff
| | call trap
| | // ...
+----------------+
</pre>
<p>
Each exception or interrupt should have
its own handler in <tt>trapentry.S</tt>
and <code>trap_init()</code> should initialize the IDT with the addresses
of these handlers.
Each of the handlers should build a <code>struct Trapframe</code>
(see <tt>inc/trap.h</tt>) on the stack and call
<code>trap()</code> (in <tt>trap.c</tt>)
with a pointer to the Trapframe.
<code>trap()</code> then handles the
exception/interrupt or dispatches to a specific
handler function.
</p>
<div class="required"><div id="Exercise-4" style="position: relative; top: -5em;"></div>
<p><span class="header">Exercise 4.</span>
Edit <tt>trapentry.S</tt> and <tt>trap.c</tt> and
implement the features described above. The macros
<code>TRAPHANDLER</code> and <code>TRAPHANDLER_NOEC</code> in
<tt>trapentry.S</tt> should help you, as well as the T_*
defines in <tt>inc/trap.h</tt>. You will need to add an
entry point in <tt>trapentry.S</tt> (using those macros)
for each trap defined in <tt>inc/trap.h</tt>, and
you'll have to provide <code>_alltraps</code> which the
<code>TRAPHANDLER</code> macros refer to. You will
also need to modify <code>trap_init()</code> to initialize the
<code>idt</code> to point to each of these entry points
defined in <tt>trapentry.S</tt>; the <code>SETGATE</code>
macro will be helpful here.
</p>
<p>
Your <code>_alltraps</code> should:
</p>
<ol>
<li>push values to make the stack look like a struct Trapframe</li>
<li>load <code>GD_KD</code> into <tt>%ds</tt> and <tt>%es</tt></li>
<li><code>pushl %esp</code>
to pass a pointer to the Trapframe as an argument to trap()</li>
<li><code>call trap</code> (can <code>trap</code> ever return?)</li>
</ol>
<p>
Consider using the <code>pushal</code>
instruction; it fits nicely with the layout of the <code>struct
Trapframe</code>.
</p>
<p>
Test your trap handling code
using some of the test programs in the <tt>user</tt> directory
that cause exceptions before making any system calls,
such as <tt>user/divzero</tt>.