-
Notifications
You must be signed in to change notification settings - Fork 17
/
Copy pathmachine_execution.html
1628 lines (1464 loc) · 70 KB
/
machine_execution.html
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 4.0 Transitional//EN">
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8"/>
<title></title>
<meta name="generator" content="LibreOffice 5.1.6.2 (Linux)"/>
<meta name="created" content="2017-03-30T17:00:11.712220409"/>
<meta name="changed" content="2017-03-30T17:21:26.144510450"/>
<style type="text/css">
@page { margin: 2cm }
p { margin-bottom: 0.25cm; line-height: 120% }
</style>
</head>
<body lang="en-IN" dir="ltr">
<p style="margin-bottom: 0cm; line-height: 100%"><b>XSM Machine
Execution Environment Tutorial</b></p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">This tutorial will
help you to understand the architectural features of the XSM machine
necessary to for implementing the eXpOS operating system and these
features will be used by the eXpOS kernel.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">The CPU of the XSM
virtual machine [LINK:
snitc.github.io/arch_spec-files/machine_organisation.html] contains
20 general-purpose registers R0-R19, each of which can store an
integer or a string. (see XSM specification LINK:
http://exposnitc.github.io/arch_spec.html). Along with these are the
registers stack pointer (SP), base pointer (BP) and instruction
pointer (IP). There are other special purpose registers PTBR, PTLR,
EIP, EC, EPN, EMA and four ports P0,P1,P2,P3. We will discuss the
role of these soon.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">The machine's memory
consists of 65536 memory words. Each word can store an integer or a
string. The <b>memory is divided into pages of 512 words each</b>.
Thus memory addresses 0 to 511 belong to page 0, 512-1023 belong to
page 1 and so on. The last (page 127) contain memory address 65024
to 65535. The <b>memory is word addressable</b>. This means that
XSM provides instructions that allow you to access any memory word.
For instance, the instruction "MOV R0, [1345]" transfers
the contents of memory location 1345 to register R0.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">The machine also has
a disk having 512 blocks. Each <b>disk </b><b>block can store 512
words</b>. Thus the total storage capacity is 512 x 512 = 262144
words. However, the <b>disk is block addressable</b> and not word
addressable. XSM provides just three instructions to manipulate
the disk – LOAD, LOADI and STORE. These instructions can be used
to transfer a disk block to a memory page or back. Suppose we want
to access the 10th word of block 12, then the only way to do so is to
first transfer the 12th block to some memory page and then access the
corresponding memory address.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Apart from disk and
memory, the machine also has three devices – an I/O <b>Console, a
timer and disk controller</b>. We will discuss them later. The
organization of the XSM machine is given [here
http://exposnitc.github.io/arch_spec-files/machine_organisation.html]</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">The machine can
operate in two fundamental modes – <b>privileged and unprivileged.</b>
When the machine gets powered on, it begins execution in the
privileged mode. We will discuss unprivileged mode later and
assume privileged mode execution in the following.</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Note: The ExpOS
documentation (unfortunately) uses the words "kernel mode"
for privileged mode and "user mode" for unprivileged mode
execution. This terminology arose because the OS kernel code runs in
privileged mode and application programs run in unprivileged mode.
However "kernel" and "user" and OS level
abstractions, not connected to the machine, and the terminology is
not used in this document while referring to architectural concepts.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">\section <b>Boot-up.
</b>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">What happens when
the machine is powered on? All registers will be set to value zero.
In particular, IP register also assumes value 0. Once powered on,
the machine will start repeatedly executing the following
fetch-execute cycle in privileged mode.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">1. Transfer the
contents of two memory locations starting at the address stored in IP
register to the CPU. The XSM machine treats the contents read like a
machine instruction. This action is called the <span style="font-weight: normal">instruction</span><b>
fetch cycle</b>.
</p>
<p style="margin-bottom: 0cm; line-height: 100%">2. The next step is
the <b>execute cycle</b> where the instruction fetched in Step 1 is
executed by the machine. What happens here depends on the
instruction [ see XSM instruction set
http://exposnitc.github.io/arch_spec-files/instruction_set.html]</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">For example, if the
instruction fetched is "MOV R0, [1256]", the execute cycle
action will result in the contents of memory location 1256 being
transferred to register R0. If the instruction fetched in "JMP
1110", the value of the IP register will be set to 1110.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">3. The final step
is to set the instruction pointer to the next instruction to be
executed. Since each XSM instruction is two words, <span style="font-weight: normal">IP
will normally be incremented by 2.</span> There are exceptions to
this rule. For instance in the case of "JMP 1110", IP is
set to 1110 and hence not incremented. Thus the next fetch must be
from 1110. After Step 3, the machine loops back to Step 1.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Also see Wiki Link:
[https://en.wikipedia.org/wiki/Instruction_cycle]</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">When the machine is
just powered on, IP value is 0. Hence, the first instruction will be
fetched from memory locations 0 and 1. The XSM machine has a boot
ROM containing just two instructions:</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Location
Instruction Instruction semantics</p>
<p style="margin-bottom: 0cm; line-height: 100%">0
LOADI 1, 0 Load contents of disk
block 0 to memory page 1.
</p>
<p style="margin-bottom: 0cm; line-height: 100%">2
JMP 512 Change IP value to
512.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">The bootstrap code
is hard coded into a boot ROM so that the memory contents are not
lost even after machine shutdown. This is necessary because when
machine is powered on, there must be some meaningful instruction at
address 0 from where the first fetch takes place.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Study the above
bootstrap code carefully. What it does is to load the contents of
disk block zero to memory page 1 and then set the IP value to 512 so
that the next fetch happens from memory address 512. This last
step is very important because the machine will fetch contents of
memory address 512 and 513 next, decode it assuming there is a valid
instruction stored there and execute it and proceed from there.
Hence, if you write an XSM assembly language program and store it in
block 0 in such a way that your first instruction is stored in the
first word of block 0, the machine will execute it immediately after
JMP 512. Consequently, your code gets control of the machine, and
the fetch-execute cycle continues with your code. You will be
writing the <b>OS bootstrap loader </b>and storing it in block 0 in
Stage 3 of the ExpOS roadmap.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Note: The boot ROM
actually contains more information than what is written above. The
boot ROM contains an <b>interrupt vector table</b> located between
addresses 492 to 511. The vector table specifies the physical
address to which interrupts must transfer control to. We will
discuss this later.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">\section <b>Privileged
mode of execution</b>.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">The privileged mode
of execution is easy to comprehend. All instructions in the XSM
machine instruction set described here
[http://exposnitc.github.io/arch_spec-files/instruction_set.html]
will execute in the most natural way in the privileged mode of
execution. Most of the instructions like data transfer
instructions, arithmetic and logic instructions, and control flow
instructions (JMP etc.) are straightforward to understand from the
specification and not described here.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Instead, we will
focus here on the execution semantics of the following four (slightly
non-trivial) instructions when executed in privileged mode – PUSH,
POP, CALL and RET.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">The value of the SP
register holds a pivotal role in these operations. The PUSH
instruction results in the following actions:</p>
<p style="margin-bottom: 0cm; line-height: 100%">1. Contents of SP
gets incremented by 1.</p>
<p style="margin-bottom: 0cm; line-height: 100%">2. The data
specified by the PUSH instruction is transferred to the location
pointed to by SP.</p>
<p style="margin-bottom: 0cm; line-height: 100%">3. IP gets
incremented by 2 to point to the next instruction.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Example:
</p>
<p style="margin-bottom: 0cm; line-height: 100%">MOV SP, 1000 //
SP register is loaded with value 1000.
</p>
<p style="margin-bottom: 0cm; line-height: 100%">PUSH R0 // SP is
set to 1001 and contents of R0 is copied to memory address 1001.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">The POP instruction
is a reverse operation to PUSH. The contents of the memory address
pointed to by SP will be retrieved to a register specified, and SP is
decremented.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">The CALL instruction
results in the following:</p>
<p style="margin-bottom: 0cm; line-height: 100%">1. Increment SP by
one.</p>
<p style="margin-bottom: 0cm; line-height: 100%">2. Transfer
contents of IP register to the memory address pointed to by SP.</p>
<p style="margin-bottom: 0cm; line-height: 100%">3. Set IP to the
value of register/constant value specified in the CALL instruction.</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Example:</p>
<p style="margin-bottom: 0cm; line-height: 100%">MOV SP, 1000 // SP
is set 1000</p>
<p style="margin-bottom: 0cm; line-height: 100%">CALL 21110 // a)
Increment SP to1001, b) Copy contents of IP to location 1001 c) MOV
21110 to IP register.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">As a consequence,
the next instruction fetch will happen from address 21110.</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">The RET instruction
reverses the actions of a CALL instruction. The contents of address
pointed to by SP register is copied to the IP register, and SP is
decremented. Since IP is modified, the next instruction is fetched
from the newly set value.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Finally, we initiate
a discussion on the most complicated instruction – IRET. This
instruction can be only executed in privileged mode, but IRET is the
only XSM instruction that results in the XSM machine to switch from
the privileged mode to unprivileged mode. After an instruction
fetch, if the XSM encounters the IRET instruction, the following
actions take place:</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">IRET execution
semantics</p>
<p style="margin-bottom: 0cm; line-height: 100%">1. Enable paging
and change from privileged mode to unprivileged mode</p>
<p style="margin-bottom: 0cm; line-height: 100%">2. Execute the RET
instruction in the unprivileged mode. (The execution semantics now
is different, and you must read next section to understand how RET
works in unprivileged mode).
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">After the IRET
instruction, the machine continues fetch execute cycle, but in the
unprivileged mode. Note that the change of machine mode from
privileged to unprivileged happens before the actual fetch-execution
cycle. Thus, to understand how an instruction works, one needs to
know how paging and address translation works. We discuss
unprivileged mode execution in the next section.
</p>
<p style="margin-bottom: 0cm; line-height: 100%">
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">\ section
<b>Unpreviliged Mode Execution. </b>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><i>Pre-requisite
reading: </i>You must go through the following links before reading
further:
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><i>Paging
specification:</i>
http://exposnitc.github.io/arch_spec-files/paging_hardware.html</p>
<p style="margin-bottom: 0cm; line-height: 100%"><i>Virtual address
space model: </i>
http://exposnitc.github.io/virtual_machine_spec.html</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">In the privileged
mode, a memory address refers to the actual physical memory address.
For instance, The instruction sequence:
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">MOV SP, 1000</p>
<p style="margin-bottom: 0cm; line-height: 100%">PUSH R0</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">will first set SP to
1001 and transfer the contents of register R0 to the memory location
101.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">However, the PUSH
and other instructions have a different behavior when executed in
unprivileged mode. PUSH will increment SP to 1001 as before, but the
memory address to which contents of R0 is copied is determined in a
different way. The machine will treat the contents of SP as a<b>
logical address</b>, find out the physical address corresponding to
the logical address 1001 using page table address translation and
transfer contents of R0 to that location.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><span style="font-weight: normal">The
translation of a logical address to physical address is done
completely by the machine</span><span style="font-weight: normal">'s</span><span style="font-weight: normal">
</span><b>paging </b><b>hardware</b><span style="font-weight: normal">.</span>
The sequence of steps involved may be abstractly described by the
following steps, which will be described in detail with examples
soon:
</p>
<p style="margin-bottom: 0cm; line-height: 100%">
</p>
<p style="margin-bottom: 0cm; line-height: 100%">1. Given logical
address – find logical page number and offset specified by the
address.
</p>
<p style="margin-bottom: 0cm; line-height: 100%">2. Search the page
table to find the physical page number from the logical page number.</p>
<p style="margin-bottom: 0cm; line-height: 100%">3. Multiply
physical page number by page size to find physical page address.
</p>
<p style="margin-bottom: 0cm; line-height: 100%">3. physical address
= physical page address + offset.</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">The machine assumes
that the <b>PTBR register</b> holds the (starting) address of the
page table in memory. Since PTBR register can be accessed only in
privileged mode, your code must have set the PTBR register to store
the address of the page table before entering unprivileged mode
execution. Moreover, you also must set appropriate values in the
page table before you code execute an IRET instruction to switch the
machine to unprivileged mode to get the address translation work the
way you would like it to. Thus, some setup work needs to be done in
the previliged mode before a switch to unprivileged mode.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">How does the machine
translate a logical address – say 1001- to the physical address?
The machine does the following sequence of actions. Let us assume
that PTBR contains value – say 3000, set previously.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">a. calculate
logical_page_number = logical_address DIV page_size = (1001 DIV
512)=1.
</p>
<p style="margin-bottom: 0cm; line-height: 100%">b. calculate offset
= logical_address MOD page_size = (1001 MOD 512) = 489.
</p>
<p style="margin-bottom: 0cm; line-height: 100%">c. Find the
page_table_address = contents of PTBR = 3000.</p>
<p style="margin-bottom: 0cm; line-height: 100%">d. Find
physical_page_number = value stored in address (page_table_address +
2 x logical_page_number) =value stored in address (3000 + 2 x 1) =
value stored in address 3002.</p>
<p style="margin-bottom: 0cm; line-height: 100%">Suppose that this
value is 7. (The minimum value possible is 0 and the maximum value
possible is 63 – why?).
</p>
<p style="margin-bottom: 0cm; line-height: 100%">e. Calculate
Physical_address = physical_page_number x page_size + offset = 7 x
512 + 489 = 4073.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Thus, PUSH R0 will
transfer contents of R0 to the physical address 4073.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">There are several
points to mention here. The PUSH operation will be successful only
if the <b>auxiliary information</b> for logical page number 1 in the
page table is set to ensure that the page is valid. Otherwise, the
machine will generate an <b>exception</b>, switching back to
privileged mode. We will discuss exception handling later.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">To get a better
picture of the unprivileged mode execution, we need to digress
briefly to discuss the underlying theoretical concepts.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">\subsection <b>Paging
and virtual memory</b></p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">First of all, as an
OS designer, why should you learn to run the machine in unprivileged
mode at all? An OS will have to allow execution of other "user
programs" (or application programs). The OS needs to be
careful not to allow application programs to run malicious code that
corrupt other user programs or the OS itself. This requires
provision to run application programs in a "less privileged"
mode of execution where only a limited set of instructions can be
executed, and only limited memory space and system resources are
accessible. Architecture support is needed to achieve this.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">The architecture
support provided by the XSM machine is support for the [LINK: XSM
virtual machine model
http://exposnitc.github.io/virtual_machine_spec.html]. When a
program runs in unprivileged mode on the XSM machine, only a
restricted machine model is available to the application program. A
key architectural technique that supports such a model is paging.
Paging allows the OS to provide each application program running in
unprivileged mode a virtual (or logical) address space. The
application's access can be restricted to this address space.</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">The virtual address
space of an application is a contiguous memory address space starting
from logical address 0 to a maximum limit set by the OS. Thus the
addresses found in the application program's code shall only be
between 0 and the maximum limit. The application's code and data
must fit into this address space. When the application is loaded
into memory, the OS may load the pages into physical memory addresses
that are different from the logical address space of the application.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">XSM Paging hardware
provides machine support for such relocation. Before running an
application, the OS must execute previliged code to do the following:
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">1. Set the PTLR
register to define the address space maximum limit.</p>
<p style="margin-bottom: 0cm; line-height: 100%">2. Set up a valid
page table in memory and the PTBR register to the beginning address
of the page table.
</p>
<p style="margin-bottom: 0cm; line-height: 100%">3. Set up the
application's stack.
</p>
<p style="margin-bottom: 0cm; line-height: 100%">4. Compute the
physical address corresponding to the logical address in SP. Then,
copy the logical address of the first instruction (entry point) that
much be fetched after IRET into this physical memory location and
execute IRET.</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">We explain each of
the above four steps in detail:
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Step 1: XSM
stipulates that the address space limit of an application must be a
multiple of XSM page size=512. Suppose, the OS decides that the
application must be provided a virtual address space of 10 pages,
then the PTLR register must be set to value 10. In this case, the
logical address space of the application will be between 0 and
512x10-1=5119. (The ExpOS kernel that you design sets the address
space of every application to 10 pages).</p>
<p style="margin-bottom: 0cm; line-height: 100%"> While executing
in user mode, if an application generates an address beyond this
limit, the machine will raise an exception. This will result in the
machine switching to privileged mode and control transferred to the
starting address of the exception handler routine (memory address
1024 – see
http://exposnitc.github.io/arch_spec-files/machine_organisation.html#content).
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">For example, if
PTLR=10 and if the application contains an instruction like MOV R0,
[6000], an exception will be generated because the instructions
contain addresses outside the logical address space set by PTLR. As
another example, JMP 7000 instruction will result in setting IP to
7000 and in the very next fetch cycle, an exception will be generated
because an instruction fetch will be attempted from a logical address
beyond the address space. If SP holds value 5119, then a PUSH
instruction will similarly result in an exception. Exception
handling will be discussed in detail later.</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Step 2: Once the
address space size is determined by PTLR value, a page table has to
be set up in the memory to tell the hardware which logical page is
mapped to which physical page. The number of entries in the page
table is determined by the number of pages allocated to the
application. Thus if PTLR=10, then the page table must contain ten
entries.</p>
<p style="margin-bottom: 0cm; line-height: 100%"> Each page table
entry requires two memory words and contains information about the
corresponding logical page. That is, the first two words of the page
table contain information about logical page 0, the next two about
logical page 1 and so on. If PTLR=10, the page table of the
application will require total 20 memory words.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"> The first word of
each page table entry contains the physical page number of the
corresponding logical page. The second word stores auxiliary
information. The auxiliary information for a page consists of four
binary values:</p>
<p style="margin-bottom: 0cm; line-height: 100%">a) <b>Reference bit</b>.
b) <b>Valid bit</b>, c) <b>Write permission bit</b>, d) <b>Dirty
bit</b>.</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"> Proper values
for Valid (V bit) and the Write permission bit (W bit) must be set by
your privileged code of step 2 before starting unprivileged mode
execution. We describe these settings below.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">If the Valid bit is
set to 0, the page table entry is considered invalid. In this case,
if any logical address accessing the page will generate an exception.
If the write permission bit is set to 0, the application will not
have write permission to the page.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">For example, if
entry 0 of the page table has valid bit 0, then an instruction like
MOV [100],R0 or JMP 112 will generate an exception.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">If entry 0 of the
page table has write permission bit 0, then MOV [100],R0 that
modifies the page will raise an exception. However, JMP R0,[100] or
JMP 112 that do not modify the contents of the page will execute
normally in unprivileged mode.</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">The <b>Reference bit
and the Dirty bit are set by the machine</b>. When the application
is executing, if an address is generated accessing some logical page,
then the reference bit of the page is set automatically to 1 by the
machine. For instance, MOV R0, [1500] accesses the logical page 2
and hence the reference bit of the corresponding page table entry
will be set to 1 by the machine automatically. The dirty bit is set
if the instruction modifies the contents of the page. MOV R0, [1500]
does not result in the machine setting the dirty bit for logical page
2 because the instruction does not modify contents of the page.
However MOV [1500], R0 set the dirty bit.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">\subsection <b>Loading
application to address space</b></p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Suppose an
application contains 3 pages of code. Assume that the first page of
the code has been loaded into physical page number 100 and second
page to 110. Assume that the third page is not loaded into memory.
(The load instruction can be used in the privileged mode to transfer
a program in disk to memory).
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">suppose the first
few lines of the application code is as below:
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">MOV R0, 1</p>
<p style="margin-bottom: 0cm; line-height: 100%">MOV R1, 0</p>
<p style="margin-bottom: 0cm; line-height: 100%">L0: CMP R0, 10</p>
<p style="margin-bottom: 0cm; line-height: 100%">JNZ L1</p>
<p style="margin-bottom: 0cm; line-height: 100%">ADD R1, R0</p>
<p style="margin-bottom: 0cm; line-height: 100%">ADD R0, 1</p>
<p style="margin-bottom: 0cm; line-height: 100%">JMP L0</p>
<p style="margin-bottom: 0cm; line-height: 100%">L1: ....</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">JMP addresses are
indicated by labels for clarity of understanding. The actual
executable code will not have any labels, but will only have
logical addresses. Suppose L0 corresponds to logical address – say
2060, then the address of L1 must be 2070 because each XSM
instruction takes two words. Counting backward, the address of the
first instruction must have been 2056.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Here we must
particularly note something - the application code is designed to be
loaded by the OS to start execution from logical address 2056.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">The code with labels
replaced by logical addresses will be as follows:
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">MOV R0, 1</p>
<p style="margin-bottom: 0cm; line-height: 100%">MOV R1, 0</p>
<p style="margin-bottom: 0cm; line-height: 100%">CMP R0, 10</p>
<p style="margin-bottom: 0cm; line-height: 100%">JNZ 2070</p>
<p style="margin-bottom: 0cm; line-height: 100%">ADD R1, R0</p>
<p style="margin-bottom: 0cm; line-height: 100%">ADD R0, 1</p>
<p style="margin-bottom: 0cm; line-height: 100%">JMP 2060</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; font-weight: normal; line-height: 100%">
<i>This code will not execute correctly unless loaded as the fifth
logical page because jump addresses will be invalid. </i>
</p>
<p style="margin-bottom: 0cm; font-weight: normal; line-height: 100%">
<br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Thus, the physical
address of logical page 4 (starting at logical address 2048) must be
associated with physical page 100. Assume that the code continues
to the next logical pages, the page number for logical page 5 must
be set to 110. The valid bit for both entries must be set to 1. The
valid bit for logical page 6 must be set to 0 since the page is not
valid (and the machine should not assume that whatever value stored
in the entry for the physical address is correct). As noted
previously, setting off the valid bit ensures that the machine will
generate an exception if either or instruction fetch or operand fetch
is attempted from that page. Finally, since code pages are expected
not to be modified during program execution, the Write permission
bit must be set to 0.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">(Setting write
permission off for code pages is a necessary exercise. A typical
multi-tasking OS will permit several applications to share code
pages in memory. It then is the duty of the OS to ensure that one
application doesn't modify the shared code to "hack"
others.)
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">The essential idea
to understand here is that each application is designed (by some
programmer) to be loaded into certain part of its virtual address
space. Although paging allows logical pages to be mapped to
arbitrary physical pages, the logical page where each region of code
must be loaded cannot be changed.
</p>
<p style="margin-bottom: 0cm; line-height: 100%">(Note: There are
architectures that allow application programmers write position
independent code
[https://en.wikipedia.org/wiki/Position-independent_code] that can be
loaded anywhere into the address space. We will not discuss this
topic here.)
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Finally, the page
table itself needs to be stored somewhere in memory. Let us assume
that page table of the application begins at physical address 1000.
Then, the entries in the page table must be set as below:</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Location
Entry Desciption</p>
<p style="margin-bottom: 0cm; line-height: 100%">1000
xx // page 0 physical page number - irrelevant
(not loaded).</p>
<p style="margin-bottom: 0cm; line-height: 100%">1001
?? // page 0 invalid – what must be the value
set here?
</p>
<p style="margin-bottom: 0cm; line-height: 100%">1002
xx // page 1 physical page number (not loaded)
</p>
<p style="margin-bottom: 0cm; line-height: 100%">1003
?? // page 1 invalid – what must be the value
set here?
</p>
<p style="margin-bottom: 0cm; line-height: 100%">1004
xx // page 2 physical page number (not loaded)</p>
<p style="margin-bottom: 0cm; line-height: 100%">1005
?? // page 2 invalid - what must be the value set
here?</p>
<p style="margin-bottom: 0cm; line-height: 100%">1006
xx // Page 3 not loaded</p>
<p style="margin-bottom: 0cm; line-height: 100%">1007
?? // Must be set to invalid</p>
<p style="margin-bottom: 0cm; line-height: 100%">1008
100 // Page 4 – loaded to physical page100</p>
<p style="margin-bottom: 0cm; line-height: 100%">1009
?? // Page 4 – Valid, Write Only – what must
be set here?
</p>
<p style="margin-bottom: 0cm; line-height: 100%">1010
110 // Page 5 – loaded to physical page 110.</p>
<p style="margin-bottom: 0cm; line-height: 100%">1011
?? // Page 5 Valid, write only.
</p>
<p style="margin-bottom: 0cm; line-height: 100%">1012
xx // Page not loaded
</p>
<p style="margin-bottom: 0cm; line-height: 100%">1013
?? // Invalid
</p>
<p style="margin-bottom: 0cm; line-height: 100%">1014
xx // Page not loaded</p>
<p style="margin-bottom: 0cm; line-height: 100%">1015
?? // Invalid</p>
<p style="margin-bottom: 0cm; line-height: 100%">1016
xx // Page not loaded
</p>
<p style="margin-bottom: 0cm; line-height: 100%">1017
?? // Invalid</p>
<p style="margin-bottom: 0cm; line-height: 100%">1018
xx // Page not loaded</p>
<p style="margin-bottom: 0cm; line-height: 100%">1019
?? // Invalid.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Since PTLR=10,
there are 20 words for the page table. We must set all unloaded
pages invalid.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">The PTBR register
must be set to value 1000 (MOV PTBR, 1000). Now address translation
for logical page 4 and logical page 5 will correctly translate to
physical page 100 and physical page 110.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">To summarize:
</p>
<p style="margin-bottom: 0cm; line-height: 100%">a) The valid bit
must be set for the pages loaded.
</p>
<p style="margin-bottom: 0cm; line-height: 100%">b) Logical page to
physical page mapping must be set up in the page table correctly</p>
<p style="margin-bottom: 0cm; line-height: 100%">c) PTBR register
must be set to the start address of the page table.</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Important Note:
Suppose you are designing the loader program of an operating system
to load an execute an unknown applications, how will you figure out
where must be code pages of the application loaded? In general,
there is no way unless there is a prior agreement with the
application programmer. Hence, each operating system publishes an
interface specification called Application Binary Interface (ABI)
that fixes this and several other matters. In the eXpOS project,
the ABI convention is that the application code must be loaded to
logical pages 4,5,6 and 7. The details are given in the eXpOS ABI
given [here : http://exposnitc.github.io/abi.html]. Thus the code
area of an eXpOS application will start at address 2048. The above
example had followed this eXpOS ABI.</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Step 3: A minimum
of one page must be allocated to each application for maintaining a
stack before the application is executed in unprivileged mode in the
XSM machine. This is because the IRET instruction (to be discussed
next) that changes from privileged mode to unprivileged mode requires
a stack page. The pages allowed for stack must be writable, and
hence the write permission for these pages must be set in the page
table. Normally an application's run-time data will be stored in the
stack. Arguments to function calls in the application and return
values are also normally passed through the stack. How the
application uses the stack is its concern, but an aspect important to
us here is that INT instruction which allows an application to switch
the mode back to the privileged mode, as well as the IRET instruction
that allows the mode switch from previliged mode to unpreviliged
mode, requires the stack.
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><b>The eXpOS ABI of
our concern stipulates that logical pages 8 and 9 of an application
must be allocated for the stack.</b> Hence the stack begins at
logical address 4096. Therefore, before an application is run for
the first time, SP is set to value 4095 (why not 4096?). Continuing
the above example, if the physical pages allocated for the stack are
120 and 121, then the page table starting at address 1000 will be as
below:
</p>
<p style="margin-bottom: 0cm; line-height: 100%"><br/>
</p>
<p style="margin-bottom: 0cm; line-height: 100%">Location
Entry Description</p>
<p style="margin-bottom: 0cm; line-height: 100%">1000
xx // page 0 physical page number - irrelevant
(not loaded).</p>
<p style="margin-bottom: 0cm; line-height: 100%">1001
?? // page 0 invalid – what must be the value
set here?
</p>
<p style="margin-bottom: 0cm; line-height: 100%">1002
xx // page 1 physical page number (not loaded)
</p>
<p style="margin-bottom: 0cm; line-height: 100%">1003
?? // page 1 invalid – what must be the value
set here?
</p>
<p style="margin-bottom: 0cm; line-height: 100%">1004
xx // page 2 physical page number (not loaded)</p>
<p style="margin-bottom: 0cm; line-height: 100%">1005
?? // page 2 invalid - what must be the value set
here?</p>
<p style="margin-bottom: 0cm; line-height: 100%">1006
xx // Page 3 not loaded</p>
<p style="margin-bottom: 0cm; line-height: 100%">1007
?? // Must be set to invalid</p>
<p style="margin-bottom: 0cm; line-height: 100%">1008