WEBVTT

1
00:00:03.540 --> 00:00:11.130
William Cheng: Okay, this is the week nine discussion section. So we're going to talk about Colonel three

2
00:00:12.090 --> 00:00:21.270
William Cheng: So, Colonel three is the hardest assignment. It's bigger than Colonel one in to combine and also some of the concepts are

3
00:00:21.960 --> 00:00:28.200
William Cheng: More difficult to implement. Even though you know we sort of been talking about this ever since the beginning of the semester.

4
00:00:28.830 --> 00:00:37.620
William Cheng: So the main thing about Colonel three is to get the user space program to work there. Some of the highlights of Colonel three is, you know, one is probably more for them.

5
00:00:38.640 --> 00:00:44.430
William Cheng: You know, go recursive in Colonel to we were just experiencing power more for them by following the pointer.

6
00:00:44.880 --> 00:00:53.580
William Cheng: Into the actual file system, but we don't really have to write any I guess you don't have to write any code inside the actual file system.

7
00:00:54.240 --> 00:01:05.910
William Cheng: So in Colonel three, you actually have to implement some of the function that are probably more vague. So it's going to get a little more complicated. So it's kind of recursive but you know recursion can also be looked at.

8
00:01:07.080 --> 00:01:15.390
William Cheng: It can also be viewed as a loop. So, so you don't really have to worry about recursion. So, so I guess what I'm trying to point out is that some of the concept or

9
00:01:15.690 --> 00:01:20.460
William Cheng: Some of the way the comments is written is sounds like a function is recursive, but it doesn't have to be.

10
00:01:21.090 --> 00:01:28.770
William Cheng: Okay, so some people like recursive function because it's nice and short but sometime it's easier to actually doing the loop and you don't have to use recursion. Yeah.

11
00:01:29.550 --> 00:01:37.800
William Cheng: Alright, so I guess the stuff that we just covered in the last lecture, lecture 16. So to show you that there's a linked list of shadow objects.

12
00:01:38.190 --> 00:01:44.610
William Cheng: That will eventually linked to the bottom object. Right. So we have a sort of link this of shadow object. And eventually, there's a bottom up to get about them.

13
00:01:45.030 --> 00:01:53.160
William Cheng: So if when you try to resist this, you can use a recursive call. You can use a recursive function to do that. Where are you can use a loop to actually walk through these new these objects.

14
00:01:53.580 --> 00:02:06.060
William Cheng: So as a read a comment block certain places they will they will sort of recommend you to to to do it in a loop you should try to do it in a loop and then there are other places where it probably doesn't really matter. So maybe you can you can use recursion or maybe things that

15
00:02:07.410 --> 00:02:12.570
William Cheng: All right. The other thing, new is just a kernel through is that we have to implement address space abstraction.

16
00:02:12.960 --> 00:02:23.760
William Cheng: So, so the address space is equal to virtual memory map. And we talked a lot about that in chapter seven. So again, you should read the chapter seven lecture slides and read the colonel three FAQ. Yeah.

17
00:02:24.390 --> 00:02:28.530
William Cheng: You also need to handle a peaceful because we're doing on demand paging in the beginning.

18
00:02:28.920 --> 00:02:37.260
William Cheng: The page table entries completely equal to zero, right. So, so whatever you try to whenever you try to perform better chance Asia, you're trapped inside, Colonel. You have to fix the page fall

19
00:02:37.860 --> 00:02:47.640
William Cheng: So that's one of the things you have to do the system call so so now we're going to end up with rules system call right so so so for example, there's the right system call there.

20
00:02:48.270 --> 00:02:54.930
William Cheng: So again, the goal of the racism call is to reach your, your function in Colonel to you have to do right function over here.

21
00:02:55.770 --> 00:03:01.350
William Cheng: Now, so right is for the user space program. It's a system called the thin wrapper that are trapped machine instruction.

22
00:03:01.830 --> 00:03:08.700
William Cheng: So eventually, you need to go to the kernel version of the July. So one of the main difference over here is also that the the argument for rights.

23
00:03:08.940 --> 00:03:18.750
William Cheng: They are user space virtual your, your user space virtual dresses. Will you go inside, Colonel. I don't know if you have noticed that when you are writing your code into writing kernels in colonel colonel to

24
00:03:18.990 --> 00:03:27.570
William Cheng: All the arguments over here, especially if their addresses. They all have Colonel virtual addresses that. So part of the difficulty over here is to convert the user space virtual address

25
00:03:27.750 --> 00:03:37.110
William Cheng: To the kernel space virtual address that because otherwise, you know, if you could even use a user space virtual address, you're going to end up with the colonel paintball and the Colonel is going to panic. And it's a crash Yeah.

26
00:03:38.460 --> 00:03:47.790
William Cheng: Alright, so, so lots of functions over here in the user space, you know, they need to come inside of Colonel so quite a few of the function has been written for you already. But again, you need to, you know, sort of,

27
00:03:48.570 --> 00:03:55.140
William Cheng: You know, remember this is the goal. And then one of the things that you have to do to make it work is the fork system call right at the

28
00:03:55.350 --> 00:04:06.660
William Cheng: user space to parent process called for you come into the kernel. There was a function called do fork and you have to implement do for. Okay, so do fork. I think this was one of the most complicated functioning your kernel three

29
00:04:07.710 --> 00:04:12.120
William Cheng: You know so. So at some point, middle of the colonel three, you need to get this function to work. Yeah.

30
00:04:12.780 --> 00:04:19.320
William Cheng: Debug. They also get a little more tricky. You know in the in the kernel one and two, a debugging is just a debugging sequel.

31
00:04:19.890 --> 00:04:29.280
William Cheng: In Colonel three. Sometimes you have to single step in machine instruction in order for you to find bugs, because if you look at the CEO, the CFO good compound to multiple machines deductions.

32
00:04:30.000 --> 00:04:36.630
William Cheng: You know, I guess one of the sequel actually compile them into a sequence of machines Joshua and there are two traps machine instructions inside

33
00:04:37.290 --> 00:04:45.240
William Cheng: So, therefore, you know, when you get a buddy. So, Colonel. You say was that it died in the First traveled a second trap. So the only way to make sure is to do single stepping you know

34
00:04:46.230 --> 00:05:04.950
William Cheng: Assembly call. So this way you can you got together exactly what's wrong. Yeah. So I think in, then the next week's discussion section I was sort of show you, you know, just sort of sort of show you some assembly code. So today, I guess we're still stay at mostly at the at the sea level. Okay.

35
00:05:07.080 --> 00:05:15.060
William Cheng: All right, if you do make not yet implemented, you're going to see that there's a lot of functions that and I implement it. Right. So again, this is a lot more than Colonel one and two. So, you know,

36
00:05:15.480 --> 00:05:22.770
William Cheng: About a number over here is the same as the the you know the if you add them all up, you have the same number of question the assumptions.

37
00:05:23.610 --> 00:05:33.180
William Cheng: So the first one over here is in us over here. The M M stands for memory management so memory matters is how you manage pace frames. Right. So the buddy system is in there, P for him is in there.

38
00:05:33.570 --> 00:05:37.530
William Cheng: There are three function, you have to implement P for and get paper and pen and paper and pen.

39
00:05:37.980 --> 00:05:45.360
William Cheng: In lecture 16 I mentioned all these three functions. Right. So again, if you forgot what they are, you know, you should review lecture 16 and then

40
00:05:45.840 --> 00:05:52.020
William Cheng: The insight VM VM is virtual memory. It's, you know, again, the name of the colonel three of the colonel three assignment.

41
00:05:52.470 --> 00:06:03.210
William Cheng: There is a file called VM map that's where you need to implement the address space because your address space is also known as the BMX the virtual memory map right so VM out over here. This is where you implement your address space.

42
00:06:03.660 --> 00:06:09.960
William Cheng: There's a lot of function, you have to implement create a map rise again, man. We just look up data structure.

43
00:06:10.500 --> 00:06:20.580
William Cheng: Okay. I mean, it's just like, you know, we have physical map you try, you try to look up something he tried to figure out how to get somewhere. So you have a map. So over here, is create a map create an address space DESTROY, DESTROY an outer space.

44
00:06:21.120 --> 00:06:26.130
William Cheng: Via map insert when you need to create a new memories that mean you need to insert a memory segment into your

45
00:06:26.700 --> 00:06:31.770
William Cheng: into outer space. So again, I guess lecture 16 was a call them VM area.

46
00:06:32.250 --> 00:06:42.060
William Cheng: Okay, so a VM map is limitless a VM area. So when you when you create a new memory segment you need to insert into the current legless that so so so got this is insertion

47
00:06:42.630 --> 00:06:50.580
William Cheng: VMware fine range. So if you want to, sort of, so the five range over here. It's almost like the first fit memory alligator.

48
00:06:50.880 --> 00:06:53.910
William Cheng: When you try to create a memory segment. He said, well, where should I create it.

49
00:06:54.150 --> 00:07:02.670
William Cheng: So, so, so, so, yeah, you need to go to the sort of the free list and look up the empty spot over here to see if it's big enough. If it's not big enough, you have to go to the next party. Go to the next bar.

50
00:07:03.150 --> 00:07:08.970
William Cheng: So it's basically running the first fit memory alligator. And so now we're going to use them to allocate address space inside the carnal.

51
00:07:09.690 --> 00:07:14.940
William Cheng: Yeah so. So this one, you need to find a place where you to create a create memories admin.

52
00:07:15.690 --> 00:07:22.440
William Cheng: VMware look up. So given a virtual address, you know, which you know which VM area does it belong to. So again you walked on the linear

53
00:07:22.770 --> 00:07:29.100
William Cheng: Linear List of VM area and then you know for for each one of them find out if the virtual I just don't do them. So, so this way you could

54
00:07:29.670 --> 00:07:39.120
William Cheng: So, so remember the list of VM area. They are they are sorted. So, therefore, you can actually tell and then also they don't overlap. So use this function to to to

55
00:07:39.930 --> 00:07:49.920
William Cheng: To locate a particular VM area that that that contains a virtual address now the VMware cloud inside for you need to copy you

56
00:07:50.700 --> 00:07:59.220
William Cheng: Inside to fork or you need to create a trial process. You need to get a copy of the address space. So the cone over here is a function that you use to to to copy, I guess base.

57
00:08:00.210 --> 00:08:06.900
William Cheng: Via map is the one that you map you Matt part of a file into your address space, then

58
00:08:07.470 --> 00:08:16.080
William Cheng: So this one again. This function is complicated, because you can map it from a file, you can map it from anonymous memory. So in this case, it's not associated with a file. So again read all the details to

59
00:08:16.530 --> 00:08:27.810
William Cheng: Figure out how to do it. But the way you should think about is that this is the one that map a file into your address face now they're not remove this guy on link right you know for for for VM map.

60
00:08:29.130 --> 00:08:37.080
William Cheng: For for VM area that's no longer use, you need to you need to get rid of it, except that it sort of doing it in a slightly we're way over here, they actually

61
00:08:37.350 --> 00:08:44.400
William Cheng: Specify a virtual address range and you turn a map a bunch of stuff in them. Okay. So again, you know, read the read the comment box it says

62
00:08:44.940 --> 00:08:56.190
William Cheng: Try to find out what you need to do VM that is range empty at the final weather and range, you know, for for virtual address range of that is empty or not. I guess this is one of the utility function that's being used.

63
00:08:56.700 --> 00:09:02.040
William Cheng: Via map read. So this is your reading from the address space. So, so why do you want to read on the address space.

64
00:09:02.400 --> 00:09:09.660
William Cheng: Okay, so for example if the user space, a program. So you saw with user space where where and then you make a system called coming out of Colonel

65
00:09:10.350 --> 00:09:18.810
William Cheng: OK, so the colonel needs to find out what is the information that get passed on the user space into the kernel. So, in that case what would need to do that you would need to read from the address space.

66
00:09:20.070 --> 00:09:24.120
William Cheng: Okay. So this sounds really really were. And that's one of the sort of the major hurdle that you have to

67
00:09:25.320 --> 00:09:26.070
William Cheng: Have to overcome when

68
00:09:26.910 --> 00:09:36.870
William Cheng: You do to do to Colonel three is that in order for the colonel to get the data from the user space program what it needs to do is that needs to read from the address space. Right. Okay. What does that mean to refund address base right

69
00:09:37.080 --> 00:09:42.330
William Cheng: That means that reading from the reading from the user space program using the VM map data structure.

70
00:09:43.710 --> 00:09:48.660
William Cheng: Okay, so for example if the user pass your buffer right here's a buffer. And here's a number of bytes over here, right.

71
00:09:48.900 --> 00:10:00.870
William Cheng: This buffer is going to be a user space virtual address. So in this case, you have to use the virtual memory map to find out what it is and then get those data from the user space bovine so this way you know what the user wants what the user space program wants you to do.

72
00:10:02.070 --> 00:10:09.810
William Cheng: Okay, so, so again this is a user space virtual address. The address of the buffer over here to users virtual address if the colonel use it directly, you might end up with the Colonel.

73
00:10:10.140 --> 00:10:17.370
William Cheng: Colonel panic. So, therefore, what you need to do is you need to convert a user space virtual address to a kernel space virtual address and then you can actually read

74
00:10:18.780 --> 00:10:21.450
William Cheng: Me the data from from the address race.

75
00:10:22.230 --> 00:10:30.900
William Cheng: That. Similarly, you can also do the reverse, you need to write into the address space. Why do you need to write into the address page, right. So, for example, the user program called the reason some call

76
00:10:31.110 --> 00:10:41.940
William Cheng: Right, you try to read the stuff on the desk, you get the data from the data and then you need to copy data into the buffer that are supplied by the user space. So in this case you need to call VM map right to write data into the address space.

77
00:10:42.990 --> 00:10:51.330
William Cheng: OK. So again, you know, so look, I look like it's backwards, right. So when the user space program called read, you need to use us be a VM app right when the user space.

78
00:10:51.900 --> 00:11:03.270
William Cheng: The Pokemon call right, you need to use VMware V two, V, the data from the user space program. And this way you know what to send the data out to the desk. Okay, so again you know when you're confusing, you know, Colonel three. Make sure you send an email now.

79
00:11:04.950 --> 00:11:11.940
William Cheng: Some of them I need to buy the loader. The loader is called elf 32 Darcy, because the format of the executable file.

80
00:11:12.630 --> 00:11:23.190
William Cheng: Okay in Phoenix is in the it's in the fall for my call call call elf 3232 means that it's a 32 bit file format and elf. I don't know if you've heard of that, you know, I guess some

81
00:11:23.700 --> 00:11:37.890
William Cheng: Some unit system they or Linux is that that's the format for the executable file. Okay, so when whenever you see a dot O file or executable file are there in that format so so so in a way elf 32 dot c is kind of a partial

82
00:11:39.180 --> 00:11:41.910
William Cheng: Remember the executable file is just a data structure.

83
00:11:42.330 --> 00:11:48.870
William Cheng: Okay so y'all have 32 contain code that will understand the data structure and use that information to build an address space.

84
00:11:49.140 --> 00:12:00.450
William Cheng: Okay, so how does it go the address is my calling all these functions or so. So today's lecture I'm going to briefly show you what that could look like. Okay, so this way you know you know what what's getting involved.

85
00:12:01.980 --> 00:12:10.440
William Cheng: Alright, so the loader. Now the loader is going to be the one that will invoke the function of Elf 32 to get the to build the address.

86
00:12:11.070 --> 00:12:16.860
William Cheng: To be able to address space and then once that's built, then what it would do is that it will transfer control to the user space program.

87
00:12:17.070 --> 00:12:23.250
William Cheng: And the first thing the users PayPal and we'll do is to run the startup function and then the first thing that will happen is the patient and you can set a kernel.

88
00:12:23.610 --> 00:12:30.930
William Cheng: That so you also need to have a peaceful or there's one function for it. It's a virtual memory paste all Darcy and there's a function called handle page fall

89
00:12:31.230 --> 00:12:34.530
William Cheng: Okay, so, so one of the arguments over here is the DDR

90
00:12:34.770 --> 00:12:39.990
William Cheng: Then whenever you get to paste all you get paid for one virtual address and then in this case you need to use that virtual address

91
00:12:40.140 --> 00:12:47.880
William Cheng: And figure out what to do. You want to kill the user says program because there's the bad virtual address. For example, this is a virtual address equal to zero, well then you kill the user's Facebook way.

92
00:12:48.420 --> 00:13:00.150
William Cheng: Okay. Otherwise, you need to look it up inside that inside the outer space and then look at a VM area. Look at you know whether its private or share with us. We write or read only. And then you need to decide what to do now.

93
00:13:02.220 --> 00:13:10.890
William Cheng: All right. There are basic system for support over your sis races. Right. So, by the way, these are these function consists underscore so so again.

94
00:13:11.190 --> 00:13:16.410
William Cheng: If the, the user space program called right. Okay. So the first point, you have to pass is the whole program.

95
00:13:16.650 --> 00:13:23.520
William Cheng: Hello profile will call the racism call the racism was coming out of Colonel. So what do you will do is that he will reach the SIS right function.

96
00:13:23.970 --> 00:13:32.040
William Cheng: Okay, it's a sister I function is the entry points are the kernel for the system call so it will go to CES this right. And the goal of six verses. Right. It's the call do right

97
00:13:33.720 --> 00:13:42.300
William Cheng: Okay, so when I say, you know, starting from right, you need to go to do right what it goes that, you know, again, it goes to one level and direction it go to CES drivers and then go to do right

98
00:13:42.720 --> 00:13:53.730
William Cheng: So. So as it turns out, sis right is is empty. So you have to actually write code for it. Okay, so in Colonel three, you know, it gets a little complicated. But, but, again, the goal is for CES right to call do right

99
00:13:54.720 --> 00:13:59.370
William Cheng: Alright, so, so, so again you need to write code for so right read a comment blog to see what you have to do.

100
00:14:00.000 --> 00:14:04.500
William Cheng: There's a function called sis a get dense. So this one is very similar to

101
00:14:04.800 --> 00:14:18.270
William Cheng: Your kernel to you will have to get directory entry while we're there yet directory entries over here. So again, this is one of the function that you have to call. And again, the goal here is to go. It's called a function get a do get dance or okay and

102
00:14:19.290 --> 00:14:31.920
William Cheng: The function there. So, so remember that this is a this is the kernel version of a system call. So when the user space program called get directory entry, are they actually can can get more than one directory entry.

103
00:14:32.580 --> 00:14:40.950
William Cheng: Okay. So in this case, you're going to end up calling multiple times when you try to get directory entries inside because again the get the regular entries are you implementing right

104
00:14:42.420 --> 00:14:52.860
William Cheng: Alright so so inside API directory. There's a Cisco Cisco. There's a lot of function over here. And most of that has been written for you already. So there are only three of them are not written. So those are the way to implement

105
00:14:53.370 --> 00:15:05.460
William Cheng: There's a function. There's a file called access. So we hear you tried to determine whether you have permission to do something or not. So again, if you try to, you know, write to your address space is if it turns out of memory segment is read only one. In that case, you should

106
00:15:05.850 --> 00:15:14.640
William Cheng: You know, the, the, the, the page fall will turn into a segmentation volume should cohesive Facebook. Well, okay. So these are the function that check whether you have the right permission or not.

107
00:15:15.000 --> 00:15:20.190
William Cheng: So there's one function called the address permission. Given a virtual address you find out whether it has the right permission or not.

108
00:15:20.400 --> 00:15:25.740
William Cheng: And the other one is called the range permission, given an address range you find out that whether you have the right permissions and

109
00:15:26.430 --> 00:15:33.600
William Cheng: Then again, this is the one about the water function, you have to implement and then there's memory management, you have to implement the mmm LBJ

110
00:15:34.200 --> 00:15:46.620
William Cheng: Lecture 16 we mentioned that there are three different kind of mo BJ. You have to deal with in Colonel three. One of them's a shadow object. The other ones that are anonymous object and the other one is the demo BJ that is that a vino there. So this one is it a

111
00:15:47.190 --> 00:15:51.870
William Cheng: Non Darcy so so so over here, this is the father implement the anonymous object.

112
00:15:52.200 --> 00:16:00.720
William Cheng: Okay I think inside this phone number, the functions are implemented. So in this case, there are eight functions here, you have to implement and that will be anonymous object guys remember anonymous object. What does it do

113
00:16:01.050 --> 00:16:10.080
William Cheng: Write it create patients for us. So we saw this career page where you can create a patient out of thin air by just asking the buddy system for page initialized zero and then you're done.

114
00:16:11.010 --> 00:16:19.500
William Cheng: Okay, so even though they look like they're a function. They're all very, very simple. Okay. So keep in mind all they're doing is career page rank right over here, you know, fill the page with zero

115
00:16:20.550 --> 00:16:29.460
William Cheng: Make a patient and dirty clean up a page and then there you know look up a page, you know, a port and rough, you know, so, so I guess this is like the rep at the pub or similar

116
00:16:29.880 --> 00:16:35.490
William Cheng: You can initialize another project, you can create an anonymous object, you know. So again, so this object is pretty simple.

117
00:16:37.830 --> 00:16:46.710
William Cheng: All right, what else is here. Oh, so, so, you know, in order for you to get the first user space Pokemon to work, which is the hello world program. Right. So what is the hello

118
00:16:46.920 --> 00:16:51.570
William Cheng: Hello, we're gonna let you make the racism call and you print the string hello world to the screen.

119
00:16:52.260 --> 00:16:59.940
William Cheng: Okay, that's all you do that. So in order for you to get hello a program to to work you have to do all this kind of stuff. Starting from the Patriots

120
00:17:00.420 --> 00:17:06.930
William Cheng: All the BMS something you have to handle pays for you have to, you know, implement all these functions over here permissions.

121
00:17:07.710 --> 00:17:11.790
William Cheng: As it turns out, I guess, you know, you don't have to implement read and you don't have to implement get dense.

122
00:17:12.420 --> 00:17:17.760
William Cheng: Okay, because reading at a hollow. You just print to the screen. You're not the roof on the keyboard. So, therefore, you don't need to have since read to work.

123
00:17:18.120 --> 00:17:28.920
William Cheng: You don't need to get the right to entry right but you have to implement this. Right. Okay. Yeah. You also need to allow permission. You need to implement an anonymous object over here. So in this case, all these things has to work. Yeah.

124
00:17:30.600 --> 00:17:36.060
William Cheng: All right, to get the hello to work. You need to get all the above to work, except for CES read and six to get dance. Yeah.

125
00:17:37.920 --> 00:17:41.670
William Cheng: All right. And then, and then after hello world.

126
00:17:42.780 --> 00:17:52.830
William Cheng: Program passing the the pass a bunch of user space program, you know, just like hello. And then the last one is called for can wait. So at some point, you need to get for to work right. So, so I guess.

127
00:17:54.030 --> 00:18:06.000
William Cheng: This is section see in the section C and the grading airline essentially integrating it the last test is called for can wait. Okay, so in that case you need to go get a copy on write and forth to work.

128
00:18:06.570 --> 00:18:17.100
William Cheng: Together in this guy's, you are required to implement shadow object, okay. So actually, you don't have to implement a shout object. If you don't want to, because you can actually get hello to a program to work with inflammation object that

129
00:18:18.390 --> 00:18:24.300
William Cheng: You might you might have to implement why it's called shadow in it because if they and if it doesn't work, then you're going to fail in a call all and then

130
00:18:24.570 --> 00:18:30.720
William Cheng: That doesn't really work very well. Yeah, so, so, but but i want is very simple. Right. You just, you know, you just initialize the the the

131
00:18:32.340 --> 00:18:35.190
William Cheng: What he called it the slab alligator or something like that. I don't remember what's in it.

132
00:18:36.720 --> 00:18:41.940
William Cheng: So you can see that this function is very basic, the same right because they're all mmm LBJ, they have the same kind of function because

133
00:18:43.110 --> 00:18:48.360
William Cheng: Because we have these poly more fake you know pointers over here. So they all have to implement the same have the same function.

134
00:18:48.840 --> 00:18:53.670
William Cheng: You create a shadow RJ increment the reference guide you documented reference counting you look up a particular shadow object.

135
00:18:53.880 --> 00:19:00.390
William Cheng: You'll fill a page, you make a page 30 and then you can you can actually clean out the page that the shadow of did a little bit

136
00:19:00.600 --> 00:19:08.610
William Cheng: More complicated because we have to implement copy on write all the stuff I mentioned the lecture 16 about what you have to do a shout object. They have to be implemented.

137
00:19:08.970 --> 00:19:21.420
William Cheng: Okay, so even though anonymous object is mmm will be J shadow opposite mo BJ anonymous updates. Super simple. Okay. Shadow object to implement all the the sort of fancy algorithm that's mentioned in lecture 16

138
00:19:23.520 --> 00:19:38.280
William Cheng: And you only need to have when you have to pass for can wait. Okay, so, so, so, so, so, you know, for all the other tasks. So again, you should you should pass the test in the way to God I sequentially. When you get to fuckin way. That's when you have to implement shadow object, then

139
00:19:39.510 --> 00:19:51.960
William Cheng: I know that you have. You also need to implement more more system called we here to the to the support for for going away. I mean, clearly, you have to implement do forth. So again, this is in progress in the process of a fantasy.

140
00:19:52.470 --> 00:19:55.350
William Cheng: There's also a function called coke. Okay, through a clone.

141
00:19:56.100 --> 00:20:03.720
William Cheng: To make a copy of a threat right because you because you know we create a trial process, you need to make a copy of the process. You also need to make a copy of the thread.

142
00:20:04.200 --> 00:20:11.550
William Cheng: So in this case, there's a function coke a threat call that was implemented in Colonel one. So now you have to implementing Colonel three now.

143
00:20:12.300 --> 00:20:21.240
William Cheng: You also need to you know maps that we do address space, so, so, so, so there is the do n map. So again, this is the kernel version of the map system call

144
00:20:22.020 --> 00:20:27.060
William Cheng: Okay, so at some point in the users baseball and they have to call him map so so here you have to get this to work.

145
00:20:27.240 --> 00:20:36.810
William Cheng: And then there is the opposite function called me a map. So you met somebody into the address space. And then at the end, when you're done, you need a map as you do that, and there's also a function called do break

146
00:20:37.470 --> 00:20:43.020
William Cheng: So break is kind of an interesting concept as it turns out that you know we we mentioned that the

147
00:20:43.440 --> 00:20:51.360
William Cheng: address space. Oh look like this right texts like men data plus BSS and there's a heat and the heat can grow. How do the, how does the heat grow.

148
00:20:52.230 --> 00:20:58.620
William Cheng: That, as it turns out, at the beginning, when you write your program. The Hebrew set up to be a certain size and the, the end of the heap.

149
00:20:59.100 --> 00:21:04.110
William Cheng: The end of the heap is known as the process break. Okay. And the way we spoke break is be RK

150
00:21:04.650 --> 00:21:11.160
William Cheng: OK, so the process bridge over here is the end of the heat, you can actually adjust the end of the heap to make the heat bigger or it can actually make the heat smaller

151
00:21:11.580 --> 00:21:18.030
William Cheng: Okay, so there's a functional to break. He's also there's a system called break when you call Bray. You can actually adjust the end of the heat.

152
00:21:18.690 --> 00:21:28.320
William Cheng: Map. So that's the thing you have to implement and also indeed over here we have some we have a function of implement one of them is a special far end map. So this way. I think you can map, you know,

153
00:21:28.980 --> 00:21:39.180
William Cheng: You can map a device into your address space. There are also some of these functions are filthy dirty base clean page again the same idea as your kernel to the VM FS doesn't know.

154
00:21:39.930 --> 00:21:46.140
William Cheng: How to do this on these dudes to find the function pointer inside the actual versus that and make sure it's not know and then call this function indirectly.

155
00:21:46.590 --> 00:21:48.870
William Cheng: That's all got all these functions are pretty pretty straightforward.

156
00:21:49.830 --> 00:21:56.580
William Cheng: Right in order for you to to to pass forget way, you need to, you know, so yeah we we need all the function

157
00:21:56.760 --> 00:22:02.010
William Cheng: That's in. Hello, plus all the ones we just talked about up to a case right corner over here. So you don't need to do

158
00:22:02.220 --> 00:22:06.450
William Cheng: That and my map, all that kind of do break and stuff like that. But you have to, you have to get the shadow object to work.

159
00:22:06.690 --> 00:22:17.700
William Cheng: Okay, so you need to get shut out the world, you need to call do for you need to be able to make a copy of the threads are the Colonel, because you know where you create a cha cha cha process. You also need to create a child threat by making a copy of

160
00:22:18.600 --> 00:22:27.150
William Cheng: That. And the reason you want to make a copy of the parents who happy that's, you know, when both the parent and the child returning to the user space program, they need to return to exactly the same place.

161
00:22:27.570 --> 00:22:35.370
William Cheng: Right. So that's why you can't really come construct a new thread you need to make a copy of the contents of the panther. So this way. The child will return to exactly the same place. Okay.

162
00:22:35.790 --> 00:22:39.660
William Cheng: Alright, so again, you know, read, read a comment there. But in order for you.

163
00:22:40.140 --> 00:22:48.780
William Cheng: To run a spin in it. So the winnings document says that you know the way to go to the user space program is to call has been in it. So my recommendation is that you should

164
00:22:49.650 --> 00:22:52.290
William Cheng: You should only attempt a spin in it when

165
00:22:52.620 --> 00:22:58.650
William Cheng: You know what, when you can pass for can wait right because instead of working away. You have to implement for it. You have to get all these function to work over here.

166
00:22:58.860 --> 00:23:04.500
William Cheng: In order for you to pass a spin in it. You have to implement a form or function. Right. And again, the last one is super, super simple.

167
00:23:04.830 --> 00:23:17.550
William Cheng: Because this is not be no. Okay, so basically you have to implement these three things you need to implement the kernel version of the map system call the kernel version of the end a map system Hall and also the kernel version of the brakes is a call.

168
00:23:18.720 --> 00:23:28.860
William Cheng: Okay, so, so, so, so, so when you start just trying to get has been in it to work. You have to pay attention to those to those three function, right, because that's where most of the bugs are now.

169
00:23:29.520 --> 00:23:36.180
William Cheng: So, so the ESPN in it. That will be the first time Malik is called okay all the way up to for the focus away. There's no maaleh

170
00:23:36.450 --> 00:23:44.010
William Cheng: Okay. Will you call it's been in this. Some people are going to end up running into bugs, because that will be the first time Malik is called as it turns out, the user space.

171
00:23:44.280 --> 00:23:47.490
William Cheng: memory allocated amount, like a free. They are really, really complicated.

172
00:23:47.880 --> 00:23:57.210
William Cheng: Okay, you actually have the full blown source of a memory allocating the user space. And as it turns out, what it would do is that it will actually map Anonymous. Anonymous memory into your address space.

173
00:23:58.050 --> 00:24:11.310
William Cheng: There so therefore they will end up calling these functions. Again, you know, a lot of bugs that you have to overcome and then eventually you will get SP internet to work there. And then finally, if you want to pass all the other tasks you need to get everything else work. Okay.

174
00:24:12.990 --> 00:24:20.550
William Cheng: So a strategy and lecture 16 I sort of briefly talk about these five phases. Right. The first phase over here is to pass all these function.

175
00:24:21.000 --> 00:24:32.460
William Cheng: In P frame and then you keep a VM equal to zero set f5 FS equal to one and they need to pass BFS tests that I think I mentioned in lecture 16 already is I'm just going to go over quickly.

176
00:24:32.940 --> 00:24:41.610
William Cheng: In phase two is you have to get hello a program to run. So, so, by the way over here, right. I mentioned over here's how you should get, you know, these three functions to work in about two days.

177
00:24:42.150 --> 00:24:54.000
William Cheng: Okay, so, so, so I guess the idea here is that on Tuesday. If you finish a colonel to then on Wednesday and Thursday. You should go get these three functions to work. So God has not too many lines of code over here.

178
00:24:54.330 --> 00:25:04.290
William Cheng: But the top bar over here is to pass the the bfs test with with with as far as equal to one and VM equal to zero, that means that now your fastest them has a real desk.

179
00:25:04.920 --> 00:25:11.490
William Cheng: Okay. So all your bugs that are inside your kernel to maybe they're not bugs for Colonel to but now when you go into Colonel three they become bugs.

180
00:25:11.790 --> 00:25:21.630
William Cheng: Okay, so there's going to be reference counting problem that's going to be, you know, memory corruption bugs over here. So you try to figure fix all those code over here and then you can before that. So these two days.

181
00:25:22.200 --> 00:25:28.800
William Cheng: You shouldn't spend too much time and getting these three function to work but you got to spend the rest of the time to fix all the bugs and Colonel to know

182
00:25:30.090 --> 00:25:41.100
William Cheng: And then you need to run the the hollow program. So the way that you run the whole program is that the basic idea over here is that the new process inside the Colonel. Okay. Now, you shouldn't run a shot anymore.

183
00:25:41.640 --> 00:25:45.690
William Cheng: Okay. So inside the enterprise things I've heard of what he should do, they should go into the user space.

184
00:25:47.100 --> 00:25:52.650
William Cheng: Okay. So, so what we need to do is that instead in a process over here, what we need to do. So we need to call a function called

185
00:25:52.950 --> 00:26:02.220
William Cheng: That's called colonel. Exactly. We're going to make the exact system called inside the Colonel. So, so this is, again, this is not a system call is the kernel version of the exact system Hall.

186
00:26:02.520 --> 00:26:08.700
William Cheng: That. So when you make this function called he started, Colonel. And then in this case, what would you do, is you're running a program in the user space.

187
00:26:08.970 --> 00:26:14.610
William Cheng: Then the first argument you know in Colonel exactly is going to be user been hello and then Hello, you know,

188
00:26:15.090 --> 00:26:21.540
William Cheng: Probably doesn't really take any function, man. So again, we read the FAQ to find out how you should call Colonel exactly that.

189
00:26:22.200 --> 00:26:28.710
William Cheng: So inside in a problem or I've been in progress is the process and now it doesn't have anything to do but going to the user space.

190
00:26:29.280 --> 00:26:36.240
William Cheng: Okay, so in that case again inside the process you comment on all your code in Colonel to and then you simply call Colonel exactly

191
00:26:36.540 --> 00:26:46.620
William Cheng: There. So now what it will do is that will go into the user space. And now the user space so so so the colonel in in process is process idea why when you go into the user space is still positive number one.

192
00:26:46.860 --> 00:26:49.710
William Cheng: But now the process. Number one is going to run the hello program.

193
00:26:50.160 --> 00:26:54.090
William Cheng: Well, guess what it will do is that, so. So if you look at the homophone, it actually has three lines of code.

194
00:26:54.390 --> 00:27:05.790
William Cheng: It says, Open a slash si, si, si y zero open slashed fit y 02 to the open, you know, standard, you know, standard out and then what it will do is it will make the racism called using standard out

195
00:27:06.690 --> 00:27:18.930
William Cheng: There so so I guess, you know, so it's so the first time you call open, you get out the script zero and then a second that you'll be you'll give up some script or one and then will you call right you will write a file descriptor one and now you print hello and then

196
00:27:19.410 --> 00:27:29.640
William Cheng: Then you return from me. Right. And the program dies. We have program dies in the user space. What it will do is that it will make an exorcism call you will come inside the kernel and the Colonel will kill this out. Sorry.

197
00:27:29.970 --> 00:27:37.230
William Cheng: The, the unit process will kill us out because exorcism Hall and now the inner process, it will wake up the parent, which I know process and it passes will turn off the machine.

198
00:27:38.880 --> 00:27:48.360
William Cheng: Alright, so this is how you run a user space program inside the enterprise, you call Colonel exactly you go into the user space you do whatever the user space program does.

199
00:27:48.540 --> 00:27:54.660
William Cheng: And when they call exit it comes out of Colonel kill the entire process wake up the the idol process and idle possible turn off.

200
00:27:55.890 --> 00:28:04.290
William Cheng: That alright so insecure know exactly what it will do is that it will invoke the loader. It does the exact system called is, you know, it's basically invoking the loader.

201
00:28:04.740 --> 00:28:17.610
William Cheng: Okay, so in this case we're going to parse the executable file and then fill the address space for it. And then we're going to go into the user space that we're going to handle pays off. And then eventually we're gonna you know pacifism call for open and also for right now.

202
00:28:19.320 --> 00:28:27.420
William Cheng: All right, and so this isn't Bobby, as I mentioned before, you need to come come real user space virtual address kernel space virtual address again. That's sort of a new concept.

203
00:28:27.660 --> 00:28:36.360
William Cheng: And that's one of the things you have to implement that part of the call is being implemented for you already. So, so in this case. Okay, you have to implement VM map really be a map. Right, right.

204
00:28:37.200 --> 00:28:48.300
William Cheng: So, so there's a lot of stuff to get out there. Good, good working just to run the whole program. Okay, so, so again, please don't attempt to run a spin in it you know right away because that's almost impossible to do that.

205
00:28:49.230 --> 00:28:54.000
William Cheng: Over here I said I, you know, you should try to get the hello program to run in five days.

206
00:28:54.510 --> 00:28:59.130
William Cheng: Okay, so, so again this is assuming that you know you have a team, all you guys are working out.

207
00:28:59.550 --> 00:29:09.180
William Cheng: All the members of the team has been working really hard to get this to work, because there are lots of function that needs to be that that needs to work almost perfectly in order for the hello program to work.

208
00:29:10.440 --> 00:29:16.500
William Cheng: Okay, so, so, so again, you know, some people like to start late, but if you started late you came in finish the hello program.

209
00:29:17.130 --> 00:29:26.190
William Cheng: There's also got a hollow polka is very, very difficult to the good to get it to work. Yeah. Alright, so once you pass the hollow program right you print out the you know the

210
00:29:27.060 --> 00:29:32.610
William Cheng: You know the Hello World. Well message onto the screen and you celebrate for five minutes and then you go back to work and go into phase three

211
00:29:33.450 --> 00:29:37.830
William Cheng: And phase three, you do pass all the section B test, you know, without the user space shell.

212
00:29:38.370 --> 00:29:46.770
William Cheng: There's a few additional tests over here by doing exactly the same thing right directly for any proper I used in Coto. Exactly. So he tried to pass individual tasks. Again, you

213
00:29:47.640 --> 00:29:55.230
William Cheng: Know if you don't have bugs, then, then, then, then, then they should, they should just work. Okay. Otherwise, you know, otherwise you need to fix the bugs over here.

214
00:29:55.680 --> 00:30:03.480
William Cheng: Trying to get this all done in three days. The last one is the one that will take a, take a most of the time, because the last one is fucking way. And this one has to

215
00:30:03.840 --> 00:30:16.230
William Cheng: You have to get a copy on write together to work with, with work. Okay, so that's why I sort of give you three days to do it because in the end, the public gonna end up two days, just to get the fork system called to work. Yeah.

216
00:30:17.040 --> 00:30:24.900
William Cheng: Alright, so once you pass away. And now, you ready to run. It's been in so phase for you. Again, you do exactly the same thing inside the inner process.

217
00:30:25.320 --> 00:30:31.380
William Cheng: You call colonel. Exactly. And then you run the, the, the real inner process, the really new process. It's actually

218
00:30:31.740 --> 00:30:44.010
William Cheng: A pretty straightforward. All that does is that it creates a user Shaw and the user show is called slash business Sh and Then the user shell is the one that's going to, you know, use TTY si, si, si y zero to interact with the user.

219
00:30:44.700 --> 00:30:56.310
William Cheng: Okay, so this guy. Want to get a user show the user shot kind of look like Acacia you can type, how we can take x that you can have echo all kind of stuff. So will you type how you're going to see that in the user level shout they they allow you to run more commands.

220
00:30:57.270 --> 00:31:01.920
William Cheng: OK. So again, this case, you can. This can you can also run user space. But when you can actually type. Hello. And if you read the

221
00:31:02.340 --> 00:31:12.630
William Cheng: Whole program you can type in all the, the, the, the programming section B, and they will run all stairs. So then you know look at section see of the grading gala, and there will be a bunch of tests that you have to pass.

222
00:31:13.620 --> 00:31:18.240
William Cheng: That. So again, once you get the user level shelter work passing attack should be pretty straightforward.

223
00:31:18.540 --> 00:31:28.680
William Cheng: There are so try to get this to do to get done in two days or three days. I mean, if it takes three days for you to do it. That means that phase five you have let you have you have you have one less de de de de de to work on.

224
00:31:29.010 --> 00:31:34.530
William Cheng: That. So once you pass the user level shuttle here, you need to retry all the tests to make sure that everything can be done in user space.

225
00:31:34.770 --> 00:31:44.370
William Cheng: And finally phase five you try to get as many section detail out the past as possible, try to get as much partial credit section details, you have to pass the FS test again.

226
00:31:44.910 --> 00:31:57.030
William Cheng: Okay, and then you have to pass something called a memory test and then something called the fourth bomb in something called though. Eat memory or something like that. And then there's another one called the stress test that will run everything on the run everything simultaneously.

227
00:31:58.410 --> 00:32:01.080
William Cheng: Okay, so. So again, you know, you

228
00:32:01.410 --> 00:32:11.940
William Cheng: So my recommendation is to pass the the easy one first. Right. So, for example, BFS test, you know, you're very familiar with, you know, internal to and also at the beginning of Colonel three. Now you need to pass them as a user space program.

229
00:32:12.180 --> 00:32:21.990
William Cheng: Okay, you should read the code and DFS test. It's kind of a pretty tricky code because that code can can can run as a colonel only code or can be run as a user space program then

230
00:32:24.180 --> 00:32:36.960
William Cheng: All right, so P frame of. I see. So again, these other the first three function, you have to implement in the first two days again given a object, given a page down, right. So again, I mentioned your lecture 16 the key for a page friend.

231
00:32:37.200 --> 00:32:48.330
William Cheng: Is the mmm LBJ that owns the page frame and also the second one. It's called a patient on a page. I'm simply an array index and so that typically that's an index into the file that gets mapped into your space.

232
00:32:48.840 --> 00:32:56.700
William Cheng: There. So again, that that's going to page 90123 or something like that. And then the goal for P friend is to create a page frame object that

233
00:32:57.030 --> 00:33:09.330
William Cheng: But since the patient can be sure. So this is going to get a little tricky. So what we need to do is that is that P for and get first we need to see if there's one that exists already. If there's one exists already that we should just use that. And then in that case, you know,

234
00:33:12.060 --> 00:33:19.110
William Cheng: So, so in that case we need to use an existing P frame that otherwise if it doesn't, if it doesn't exist already. So in this case, when you create

235
00:33:20.160 --> 00:33:33.150
William Cheng: When you create a career page, right. All right. Okay. So again, the last argument over here. It's a return argument. So this one should return the newly created patient or the new or the one that you have found that already exists.

236
00:33:33.870 --> 00:33:40.200
William Cheng: Okay, so given that the LBJ and given the page number, find the page rank. If you cannot find a create one for me.

237
00:33:41.160 --> 00:33:44.100
William Cheng: So that's the basic things. Okay, read the comment over here, very carefully.

238
00:33:44.610 --> 00:33:50.370
William Cheng: P for important. This is the one that you play hide and seek with the page on demand. Right. So. So given a page read

239
00:33:50.640 --> 00:34:04.230
William Cheng: This page right if it's on the list that can be discovered by the page it man. Well, then you should unlinked from and then append to a different list. So this way you hide it away from the, from the page it man. The opposite function is called unpaid right so

240
00:34:04.710 --> 00:34:11.040
William Cheng: This one is hidden away from the page it, man. You need to unpack you remove it from the list that it belongs to. And then you can add it

241
00:34:11.760 --> 00:34:19.680
William Cheng: Add them into the list that the patient object and by okay there's some additional a pin counters. I'm going to ask again read the comment block and figure out what to do. Yeah.

242
00:34:21.390 --> 00:34:29.400
William Cheng: Alright, so this is the most important picture is the address page representation, your for your weenies Colonel the process control blogs property.

243
00:34:29.790 --> 00:34:43.470
William Cheng: The virtual memory man is VM map underscore te. And then there's a linked list of VM area. Every VM area has a pointer back to the, the, the VM map over here. Every VM area has a start address has a length of the memory segment.

244
00:34:44.190 --> 00:34:49.530
William Cheng: Has the, the, the, the mode was rewrite or maybe it's read only.

245
00:34:49.770 --> 00:34:57.510
William Cheng: And then whether their share private right and then they have polymorphous point over here that can point to a shadow object and plan to anonymous object and point to the

246
00:34:57.750 --> 00:35:03.120
William Cheng: LBJ that's inside a file object. So that's things that have been. Oh, and he knows inside of fall object, etc.

247
00:35:03.930 --> 00:35:16.710
William Cheng: So again, this is a very important picture that we will use the term VM VM area to refer to the VM area underscore te right because they all refer to a memory segment or VM area or as region. They all mean the same thing now.

248
00:35:17.850 --> 00:35:24.180
William Cheng: So please know that the value is in the VM is above or not, what's in winning. So, so this is the one that copy from the lecture slide.

249
00:35:24.780 --> 00:35:32.790
William Cheng: Okay, so we need to actually use a different value. Right. So. So again, what you need to do is you need to find out whether your address, your address space is built correctly or not.

250
00:35:33.030 --> 00:35:39.330
William Cheng: Shown encourage you to exchange that information, because we will will tell people to say, hey, this is what I see. Are you seeing the same thing that

251
00:35:39.810 --> 00:35:45.210
William Cheng: All right. And again, whether the page number the pastry. Where are the pace friends that are managed by IBM area.

252
00:35:45.510 --> 00:35:51.900
William Cheng: Okay, so this is that you know the the picture that you need to do to implement a pitfall when you got to paste all you're going to be a DDR right

253
00:35:52.140 --> 00:36:01.890
William Cheng: Because of the add over here. It's a virtual address a user space virtual address, you need to walk down this linear list of VM area and find out which one it belongs to. How do you determine

254
00:36:02.340 --> 00:36:13.140
William Cheng: Which word belongs to you see this video here is within this range. If it's not, you follow the point of view, we go into the next one, see if it's within this range, if it's not go to this one. So you keep walking down over here.

255
00:36:14.280 --> 00:36:22.110
William Cheng: Until you determine that this particular virtual address over here is not inside any memories that man or in that case, they will turn into a tutor segmentation ball.

256
00:36:22.410 --> 00:36:27.210
William Cheng: Okay. Otherwise, if this virtual address over here belong to a memory seven

257
00:36:28.020 --> 00:36:37.440
William Cheng: So so so if we add our OB here belong to this memory segment over here. What do you do right this memory segment has multiple page rank where the pace ramps.

258
00:36:38.130 --> 00:36:41.820
William Cheng: That. So where are the pace friends that are managed by a VM area.

259
00:36:42.330 --> 00:36:46.140
William Cheng: OK. So the idea here is that as as as explained lecture 60

260
00:36:46.440 --> 00:36:51.720
William Cheng: The page rain that belongs to a VM area is managed in a linked list of mmm OBS

261
00:36:51.900 --> 00:37:01.860
William Cheng: And so therefore you follow this pointer over here. And then there's a link as of shadow object that eventually will lead you to the bottom object. The bottom object can be anonymous object or could be the memo budget that inside of vino

262
00:37:02.640 --> 00:37:07.500
William Cheng: Okay, so this link list of mmm LBJ is where you can find the patriot.

263
00:37:08.280 --> 00:37:14.670
William Cheng: Guys, okay, you need to implement an algorithm. As mentioned, Russia 16 for you to actually find out, you know, whereas corresponding patient

264
00:37:15.030 --> 00:37:23.430
William Cheng: But if the patient doesn't exist. What do you do when the patient doesn't exist. What you do is that you got all the way to the bottom over here. The bottom object can create the PageRank.

265
00:37:24.300 --> 00:37:31.080
William Cheng: Now, what about the run in the middle of yeah the one in the middle, our shadow again though, the one that said object. They are used to implement copy on write

266
00:37:32.880 --> 00:37:46.140
William Cheng: Okay, so when you need to create a page when you go to the bottom object. Well, you need to perform copy or what you copy from the link does. And then, and then you copy into the first, you know, first shot object, the first shot of object instead of linked lists.

267
00:37:47.400 --> 00:37:51.060
William Cheng: Or so that's your basic algorithm for handling a pitfall then

268
00:37:53.610 --> 00:38:03.840
William Cheng: We mentioned. So this these are these picture come from the colonel FAQ. So this is very important picture in the colonel FAQ. So again, look at the colonel F3 FAQ each other. Look at this picture over here.

269
00:38:04.320 --> 00:38:12.450
William Cheng: So again, you know, every VM area over here can be covered by multiple pages, right. So over here. Here's an example. Here is a VM area called BMA over here.

270
00:38:12.660 --> 00:38:19.020
William Cheng: They cover three pages over here. Here's four kilobytes four kilobytes four kilobytes. Okay, so, so, so again,

271
00:38:19.560 --> 00:38:32.760
William Cheng: The virtual memory area has a beginning address and the address. So here is the beginning address I call the VA DVR over here. I think your current assignments. I guess they have a different name over here. And typically, the VA, do we hear is going to be paid a lot

272
00:38:34.080 --> 00:38:40.350
William Cheng: Okay, so this is over your typical is page line. So definitely will stuff on the beginning of a page over here and then the

273
00:38:41.130 --> 00:38:52.890
William Cheng: The other member segment has length. Right. So the way that we have maybe 10 kilobytes over here. So again, we're going to cover the four kilobytes over here four kilobytes over here. The last one is going to have 42 kilobytes, and followed by two kilobytes of blank space.

274
00:38:54.150 --> 00:39:04.920
William Cheng: Okay. So this guy's again. This one is this was going to call a page number zero page number one page number to over here, but inside the BMA over here. There's another parameter over here called the offset.

275
00:39:05.310 --> 00:39:14.790
William Cheng: Okay so offset. As it turns out, this offset is when you try to map a file into your address space. You don't have to map on the beginning of the file, you can actually map the file from a different place.

276
00:39:15.240 --> 00:39:23.280
William Cheng: Okay, so this also will tell you where to start from a particular particular file. So if you have a file that look like this. Here's a file again, the way you think about it is that

277
00:39:23.430 --> 00:39:34.260
William Cheng: A file is an array of pages, right. So we're going to divide into pages, each one of them is four kilobytes four kilobytes four kilobytes. So this one is going to be page number zero page number one page number two page number three, etc.

278
00:39:35.100 --> 00:39:42.780
William Cheng: But so when I'm updating my place. If I started from right here. I need to remember that this particular memory segments start from page number one in

279
00:39:43.020 --> 00:39:54.480
William Cheng: You know of starting from page number one of the file. So therefore, the way I memorized. I use me. I may have off over here to remember that this one come from far offset. Number one, which means that the page number one.

280
00:39:55.080 --> 00:40:01.890
William Cheng: Okay, so in this case this page over here correspond to pay zero and this page will be a corresponding page one and this page will be here correspond to page two.

281
00:40:02.550 --> 00:40:12.930
William Cheng: Okay. Will you translate into the demo, which is already inside MMA BJ. There's a bunch of pace frame. Okay, so in this case page number zero we hear a corresponding to corresponding to

282
00:40:13.470 --> 00:40:19.290
William Cheng: You know, the, the zeros page of this particular file and in this case it's not part of my my memory segment.

283
00:40:19.920 --> 00:40:30.180
William Cheng: Okay, so definitely this guy, this doesn't exist. So this mmm LBJ over here has to have to keep track of the other one and the page. Now for the otherwise known as one, two, and three, because they are the array index into this file.

284
00:40:30.540 --> 00:40:35.100
William Cheng: Again, this is going to be an array index in the unit of pages into that file.

285
00:40:35.490 --> 00:40:45.330
William Cheng: Okay, so this is where where the name patient I'm come from. So what you can do is that, you know, over here. This is page zero page one page two is the VM. A off equals two, one, that means they use

286
00:40:45.570 --> 00:40:51.270
William Cheng: One to zero, you're going to get the actual page number over here. So this will this will give you the name of the page, right.

287
00:40:52.500 --> 00:40:58.200
William Cheng: Okay. So yeah, I don't want to spend too much time on over here, you should read the colonel three FAQ, and to see exactly how this work.

288
00:40:58.980 --> 00:41:13.740
William Cheng: But I also read the colonel colonel FAQ about page DOM. So look for the stream page DOM. And, you know, and then there's a there's a few Colonel the FAQ items around it. It's very, very crucial that you need to understand all these kinds of stuff. Okay.

289
00:41:14.940 --> 00:41:25.950
William Cheng: Alright, so again I'm going to read through some of these thoughts are, they are important. You know concept over here at the address space is made up a list of non overlapping VM area. So again, every VM area, they are not allowed to overlap.

290
00:41:26.250 --> 00:41:32.910
William Cheng: Okay, so all out. So, so, so get the cover a memory segment the memory segment must not overlap that

291
00:41:33.180 --> 00:41:37.740
William Cheng: Each VM area has a memory segment contiguous memory locations over here. So in in the bar.

292
00:41:37.950 --> 00:41:48.330
William Cheng: In the above is show as VA DDR comma VA DDR plus car with them square bracket on the left and the courage and the parentheses on the right again that notation means that the love.

293
00:41:48.540 --> 00:41:57.690
William Cheng: This is the interval on the left, the interval is closed. That means that include this address and then on the right hand side. It's open. That means that it doesn't include the ADD ONS plus count.

294
00:41:58.890 --> 00:42:08.340
William Cheng: That. And again, the idea is typically page alive, although I sort of made a disclaimer over here is that I'm not 100% sure if it's possible not to be page alive.

295
00:42:09.180 --> 00:42:20.760
William Cheng: Okay, so therefore I draw the picture like this. I don't know. Inside the weenies kernel code, whether it's, you know, with it with a BTR can ever be non about page line or not. Okay. So. So again, you know,

296
00:42:22.590 --> 00:42:26.370
William Cheng: If you actually in India you figured out what it is, please let me know that

297
00:42:28.830 --> 00:42:33.450
William Cheng: The current oh man is memory in pages, right, you know, because otherwise we're going to end up with, you know,

298
00:42:34.080 --> 00:42:38.070
William Cheng: The manager memory said when they would go back to segmentation again. So now we're doing paging

299
00:42:38.340 --> 00:42:45.600
William Cheng: I will do everything paging so there's going to allocate enough pages so that the memory segment and can fit in. Right. So in this case I need to allocate three pages over here.

300
00:42:45.810 --> 00:42:49.650
William Cheng: So in the above example, it takes three virtual pages to cover the memory segment.

301
00:42:49.830 --> 00:42:59.610
William Cheng: Or also three physical pages right but physical paper is going to be tricky because some of them are the original page. Some of them are copy on. Right. So again, you know, India, I'm going to end up with a lot of patrons that

302
00:43:00.150 --> 00:43:08.880
William Cheng: Each virtual pays you to be mapped into a physical page. So the virtual page over here, you get a virtual page number right the virtual page number is the leading 20 bit of a virtual address

303
00:43:09.270 --> 00:43:15.180
William Cheng: OK. So again, this one is called VF N number wise the virtual frame number one virtual frame number two vertebrae. Number three.

304
00:43:15.390 --> 00:43:19.530
William Cheng: And so, is that a patient will be here is patient number one patient to patient number three.

305
00:43:19.740 --> 00:43:33.270
William Cheng: And patient number four. So in this case, since VM. A equals two. One VF N number one need to map to Peter number two VF N number two needs about the patient number three and number three need to match up for a number, number four, okay, because of the BMA off.

306
00:43:35.640 --> 00:43:48.240
William Cheng: All right, a physical place live inside of his friends I patient my managed by the mm will be J o B here. And again, this is an example over here. Are they show you if mmm LBJ can manage up to four page over here, even though one of them might be

307
00:43:48.450 --> 00:43:58.890
William Cheng: You know, might not be useful in this particular example, but he can still manage from zero to n minus one. Okay. And over here is a comment is that this is really not implement as link this as shown above.

308
00:43:59.430 --> 00:44:04.110
William Cheng: So the pigeons. I drove yeah i think you know somebody from previous message or this picture. So I just bought that picture.

309
00:44:04.860 --> 00:44:08.010
William Cheng: Okay. So as it turns out that this one is really not a linked list.

310
00:44:08.250 --> 00:44:19.140
William Cheng: Okay, so instead of weenies can either use a hash table over here. So for this demo widget over here. There's page. Now, one, two, and three. You can use you use the hash table to find out whether whether these pages frame exists or not.

311
00:44:20.190 --> 00:44:26.580
William Cheng: Okay, so the way that you can find all these PageRank is simply use the hash table to try to look them up, then

312
00:44:28.890 --> 00:44:38.040
William Cheng: Oh, so one mmm will be Jamie man and I may manage paste rain from multiple VM area. Again, I'm not 100% sure if this can happen in the weenies code over here.

313
00:44:38.250 --> 00:44:54.900
William Cheng: So it is possible that this nm LBJ manage these three Patreon is also manage this patient for another for another process. Alright. So again, I don't know if it's possible but again there's a possibility that this might happen via may off over here already mentioned what they are. Okay.

314
00:44:56.580 --> 00:45:03.660
William Cheng: ALL RIGHT, PLEASE PRAY may not be present in mo BJ. I guess since we're doing on demand paging at the beginning, we have no PageRank.

315
00:45:04.170 --> 00:45:08.250
William Cheng: So when we get a pace fall in that case we need to travel all the way to the bottom object.

316
00:45:08.430 --> 00:45:20.070
William Cheng: And the bottom object over here, they will be the one that will create a page rank right so the terminology that we use is that if a patient exists inside of a memo BJ. We're going to say that the patient is memory resident or that's a resident page.

317
00:45:20.820 --> 00:45:32.220
William Cheng: Okay, if a patient doesn't exist. That means that is not memory resident and only the bottom object which is the the admin will be J inside of email or the anonymous object, they are the one that can actually create the space race there.

318
00:45:32.850 --> 00:45:42.330
William Cheng: You know, the shadow object. They can only perform copy on. Right. So in this case, they will need to copy from somewhere and then make a copy of it and then they will they will be managed inside shadow object, okay.

319
00:45:44.580 --> 00:45:54.750
William Cheng: Alright, so the name for peace reign is. Oh, comma, and we're a is Mo Mo, mo BJ and and it's a patient gay mentioned that lecture 16 over here.

320
00:45:55.230 --> 00:46:02.700
William Cheng: page table, you know, map a virtual page number into physical page number. So, again, in the above over here. The mapping. I just talked about over here.

321
00:46:03.090 --> 00:46:09.210
William Cheng: Is that pays rent. There are three very, very important you know fields. One is called PDF at Dr.

322
00:46:09.690 --> 00:46:20.490
William Cheng: Because, again, the paid for and kind and loving information allow you to do for look odd reverse lookup, all that kind of saw pod Dr inside a Patreon is a kernel virtual address for the corresponding physical page.

323
00:46:20.970 --> 00:46:27.930
William Cheng: Or so once you find a Patreon will be here when you try to read data. So, so remember there's a function called V or VMware V and VMware right

324
00:46:28.350 --> 00:46:33.270
William Cheng: So in that case, in this case, once you have a pastry. And he said, a patient always there is a physical physical page.

325
00:46:33.450 --> 00:46:43.830
William Cheng: If you want to read or write data from the physical page or right into the physical page, you cannot use the physical physical address, you have to use the colonel virtual address. Okay. The Colonel or virtual address is called PFA DDR

326
00:46:44.220 --> 00:46:52.050
William Cheng: Okay, so using PF add are, you should be able to write data into that into that physical page or read it off on that fiscal page.

327
00:46:53.130 --> 00:47:04.800
William Cheng: Now inside of people in these other people all day. They're also P P FOB J MP PM page. Now, those are the name for the page, where am I remember the if you go to a previous slide over here.

328
00:47:05.250 --> 00:47:15.750
William Cheng: You know, there's the old comma, and over here. So again, over here is PF YO YO WHAT IS IT PF LBJ, that's the OH and then p AMP page down over here. That's the

329
00:47:16.650 --> 00:47:24.690
William Cheng: Guy, so he's not a patient, they're also the self, self identifying information to say that I am page frame. Oh, comma, and right so so those informational cat right here.

330
00:47:26.040 --> 00:47:32.940
William Cheng: Alright, so it sounds a little weird, you know, inside the Colonel, we have these self referencing information. So again, they, they, they do exist. Okay.

331
00:47:33.930 --> 00:47:45.420
William Cheng: All right. Finally, remember the remainder over here is that the other the x86 CPU use a multi level page table, we don't really want to do deal with that. And luckily the Brown University people they implement them for for us.

332
00:47:46.080 --> 00:47:53.880
William Cheng: So, so, so, so, so, so, so in that case, you know, inside a page table see a function. They have all the implementation.

333
00:47:54.240 --> 00:48:03.000
William Cheng: They also have the implementation of the buddy system. They're very difficult. We all we need to do is to figure out how to use them that the way we use them is that we're going to use a two level and

334
00:48:04.260 --> 00:48:13.710
William Cheng: We're going to use the basic to level page table abstraction. Now, so basically all we need. Over here is that we need to use, use the virtual address and then we can actually set and individual page table entry.

335
00:48:14.040 --> 00:48:18.210
William Cheng: Okay, the function that you, you will need to use is the function called PT ma p

336
00:48:18.570 --> 00:48:24.000
William Cheng: PDF tip is to map a page table entries. So this one is used to be to us to set up a patient of entry.

337
00:48:24.300 --> 00:48:35.700
William Cheng: What do you need to set up right, you need to set up the equals to zero or one, whether it's read only or rewrite and also the physical page number. So we need to set up a separate entry over here, you need to call PT underscore map.

338
00:48:36.510 --> 00:48:44.880
William Cheng: OK, so again inside page. Yeah, I guess, I guess the fanatical page table that I see is that a functional you only have to use a few of the function there. Most of the function

339
00:48:45.270 --> 00:48:54.390
William Cheng: You don't need to worry about. So again, you know, you know, just try to find that find a function that our export it. And those are the one that you thought that you might have to use right

340
00:48:55.980 --> 00:49:05.580
William Cheng: Alright, so I think I spent 15 minutes talking about these slides over here are the next thing that will do is that I will briefly, you know, go to look at some of the source code to look at the loader.

341
00:49:06.930 --> 00:49:11.070
William Cheng: Okay, so where is the code here.

342
00:49:13.470 --> 00:49:19.080
William Cheng: That. So the coder is elf 32 it inside Colonel API directory

343
00:49:22.200 --> 00:49:25.050
William Cheng: As I'm going to edit a colonel API.

344
00:49:26.310 --> 00:49:36.270
William Cheng: You know F 32 over here. Okay, so this is function as the loader. I mean, it's very long and 741 lines long. So what I'm gonna do is I'm going to look for VM.

345
00:49:36.870 --> 00:49:40.020
William Cheng: The one that the function that you have to implement right so

346
00:49:40.350 --> 00:49:53.010
William Cheng: So, so what a loader will do is that a loader will build your address space and the way that it will do is it will call all those VM map functions. Yeah. So, therefore, what I'm gonna do, I'm gonna search for all the strings VM AP underscore something

347
00:49:53.520 --> 00:50:00.030
William Cheng: Okay, and then this way. I will find all the function. Right. So the first one over here. It's a data structure. So, d. So, this is the

348
00:50:00.330 --> 00:50:04.170
William Cheng: VM app or your address space that you have to that they that they have to build

349
00:50:04.440 --> 00:50:12.270
William Cheng: That. So in the beginning, over here, they will pass you are the VM app data structure. So inside via mobile be here. That's what we need to create a linked list of em area.

350
00:50:12.480 --> 00:50:20.010
William Cheng: And we try to create something maybe you have to actually search for all you need to walk down that link lists or something like that. So again, that's good that that's the data structure right here.

351
00:50:20.370 --> 00:50:28.200
William Cheng: Now, so this one over here. That's what we do. Here's a function that you have to implement via map is range empty. Right. So given this

352
00:50:28.500 --> 00:50:35.700
William Cheng: You know, via map over here. You start with a virtual page number and then you look at the number of pages up here. You want to see if it's empty.

353
00:50:36.270 --> 00:50:42.660
William Cheng: Okay, so if this empty if this range is empty, then what you can do over here is you can actually, you know,

354
00:50:43.590 --> 00:50:46.350
William Cheng: What would you would do is that you will map something interview address space.

355
00:50:46.710 --> 00:50:56.370
William Cheng: Okay, so let's go back over here to see what function. This is, this is called elf 32 map segments. And this guy, you're going to map a memory segment from the desk into

356
00:50:56.880 --> 00:51:07.530
William Cheng: The funnel this into address space there. So again, you add your space the VM app. And this one we're going to start with a file that has been over here. And then we're going to map a portion of the fall into address space.

357
00:51:08.220 --> 00:51:14.700
William Cheng: That right so we need to check whether this the you know the this range inside the address space is is empty or not.

358
00:51:14.910 --> 00:51:20.610
William Cheng: If it's if it turns out it's not empty. Well, then in that case, we cannot map. So in that case will be error. So in this case we are

359
00:51:20.910 --> 00:51:27.060
William Cheng: You know, it's over here. I'm going to create an error message right otherwise we're going to map that into address space. We're going to call this function VM map, map.

360
00:51:27.330 --> 00:51:30.900
William Cheng: To map and you can see that this is a really complicated function as many, many arguments.

361
00:51:31.560 --> 00:51:39.420
William Cheng: OK. So again, read the comment box very, very helpful to see how we have to implement this function. Okay, so this is one of the very important function have to implement VM map, map.

362
00:51:40.140 --> 00:51:44.820
William Cheng: Why the function here again is called VM map is range empty and then a copy a map again.

363
00:51:45.090 --> 00:51:54.840
William Cheng: And then they will call via map right so this one is writing into the address space. Why do you need to write into address space right you read the stuff on the desk into a, you know, you read the data from a file.

364
00:51:55.200 --> 00:52:05.880
William Cheng: That and then you need to copy them into your address face right so this case, you know, copy data from the file into outer space, you're going to use a VM map right okay because you're writing into the address space that

365
00:52:07.380 --> 00:52:24.150
William Cheng: All right. And then over here, VM VM map. So again, VM app right again guys all these functions will be a VM and create right so in this case is going to create an empty map I. And then what else over here VM that fine range over here. So when you try to perform the first food memory alligator.

366
00:52:25.740 --> 00:52:30.840
William Cheng: Inside VMware, the last argument over here tell you how to look for this. How did you first.

367
00:52:31.740 --> 00:52:35.970
William Cheng: When you first read our that you can start from the low to high, or saw from high to low.

368
00:52:36.390 --> 00:52:45.990
William Cheng: Okay. So I think, you know, we need Colonel, we always do high to low. We start from the higher portion of address space and then try to look for empty spot. So this way you can actually create a memory segment.

369
00:52:46.650 --> 00:53:01.260
William Cheng: Okay, so again, this, this is called find range over here, find a range over here, you know, using the first fit memory alligator. Okay, be a map or soda already. And then here's the data structure. And then when you're done with a very via mobile, you can destroy it. Okay, and then that's it.

370
00:53:02.340 --> 00:53:15.450
William Cheng: Guys will we see VM up man VM up his range MTV find range VM map. Right. So these are the first few function, you have to do to get your loader to work. Okay, so once you load it to work over here, what you will do is that

371
00:53:16.680 --> 00:53:22.110
William Cheng: Is that, is that the loader finished building the address space and it will go into the user space program and then you'll start getting pitfall.

372
00:53:22.500 --> 00:53:29.880
William Cheng: OK. So again, the way that you look at this is by looking via map underscore inside this fall over here and find out which function, you have to implement. Okay.

373
00:53:30.420 --> 00:53:35.730
William Cheng: Also, the other phones. Yeah, I sort of want to mention over here inside API to be there is a function called access see that

374
00:53:36.000 --> 00:53:42.240
William Cheng: There are some very important function over here. One of them is called copy from user, right. So again, the application program.

375
00:53:42.480 --> 00:53:48.390
William Cheng: Give you some data and then you want to perform some function. So you need to copy the information from the application, Poli.

376
00:53:48.630 --> 00:53:56.070
William Cheng: To a colonel data structure. So this is it this way to kind of a desert can use that. Okay. So in this case, you're going to end up calling a function call copy from user

377
00:53:56.370 --> 00:54:07.200
William Cheng: Then you can see that this function is very, very simple what it would do is that he was first first to check whether you have the right kind of permission or not. If there's the wrong. Wrong kind of permission you return he fault and he fall is segmentation fault.

378
00:54:07.680 --> 00:54:12.930
William Cheng: Or guys are in this case your current Oh shoot. Do not return to the user space program, you should kill the user space for that right

379
00:54:13.140 --> 00:54:21.900
William Cheng: Otherwise, if there's permission. They are allowed in this case what you would do is that you will call the map read right so this is how you copy data from the user space probe on to the Colonel.

380
00:54:22.080 --> 00:54:31.590
William Cheng: Is by calling you know, first you check whether you have permission raw. Once you have permission that you can simply call the VM AP re function to refund the address space into a colonel data structure.

381
00:54:32.010 --> 00:54:39.060
William Cheng: That the argument over here KDD. So I think in the weaning source code they tried to be very, very consistent in the naming of the variable.

382
00:54:39.240 --> 00:54:51.120
William Cheng: K DDR mean that this one is a kernel space the virtual address and this one is going to be, you add as a user space virtual address that. So in this case, we're going to copy from the user space virtual address so many buys

383
00:54:52.230 --> 00:54:56.850
William Cheng: And then in the first argument is going to be a colonel buffer. I'm going to copy that data into the kernel buffer.

384
00:54:57.600 --> 00:55:09.420
William Cheng: So this guy. Want to call VM map read using the VM map of the current process there. And then we're going to start from the user space virtual address over here so many buyers and we can copy that into a colonel buffer.

385
00:55:10.380 --> 00:55:21.270
William Cheng: OK, so again VM at three is one of the function that you have to implement that. Similarly, we also need to copy data from the user will you transfers on data from the data into memory and then you need to copy them back into the user space program.

386
00:55:21.930 --> 00:55:31.050
William Cheng: So that we need to do this because when we copy data from that this into the into the memory, we need to read one page at a time. So if the user program only asked you to return bites you can't really write one

387
00:55:31.350 --> 00:55:35.580
William Cheng: You can't really write four kilobytes, if that user space a buffer because you're gonna end up with a buffer overflow.

388
00:55:36.120 --> 00:55:39.030
William Cheng: Okay. So, therefore, what you produce that you need to read the data from the disk.

389
00:55:39.300 --> 00:55:49.320
William Cheng: A four kilobytes at a time. And there are cities as I'm Colonel buffer. And then you're going to find the run that you've got to find the correct 10 pages and then you're going to call via map right to write it into the address space.

390
00:55:50.160 --> 00:55:53.160
William Cheng: There. So, this function is called copy to user given

391
00:55:53.460 --> 00:55:57.540
William Cheng: Colonel virtual address. This is the number of bytes, you have the right, you're going to write it into

392
00:55:57.720 --> 00:56:04.560
William Cheng: The user space virtual address right guys. We do this is that you called VM app, right, you're going to go to the outer space and you go right into the address various

393
00:56:04.740 --> 00:56:12.270
William Cheng: So you don't copy from the kernel of virtual address over here into the user space virtual address by using the virtual memory map.

394
00:56:13.620 --> 00:56:18.180
William Cheng: OK. So again, these two functions of yours, very important to understand. And then over here.

395
00:56:18.690 --> 00:56:30.270
William Cheng: That they will implement a function called user stream dupe. OK. So again, the user is passing your stream. So for example, when you are calling Hello World. Okay. Hello. Well, you tried to print hello world string.

396
00:56:31.770 --> 00:56:37.710
William Cheng: Straight into the device. So again, this string hello where it's going to have a user space virtual address in order for you.

397
00:56:38.010 --> 00:56:43.620
William Cheng: For you to pass it to the device. First, you need to copy that that that that stream into, you know,

398
00:56:44.070 --> 00:56:47.790
William Cheng: Into the kernel. And then you can use the quarter buffer and then pastor device.

399
00:56:48.090 --> 00:56:55.380
William Cheng: Okay, so you can actually see that this call as we implement it for you. So, what it will do is it will allocate you know one page over here using came out.

400
00:56:55.650 --> 00:57:07.050
William Cheng: And then he will call copy from user to copy the data stream from the user into the kernel. And then what he would do is over here is that you're going to end up with a with a street instead of kernel. And now you can, you know, you can have the return stream.

401
00:57:07.800 --> 00:57:12.780
William Cheng: You know the return. So, you cannot use it called do. Right, right, because the do right the first argument.

402
00:57:13.110 --> 00:57:16.050
William Cheng: I guess the do right. The second argument has to be a colonel virtual address

403
00:57:16.320 --> 00:57:26.010
William Cheng: That and the first and the first argument for string to what we're going to be a user space virtual dress and this is how you convert a user space string into a kernel string and then you pass it to another function.

404
00:57:27.000 --> 00:57:37.470
William Cheng: All right. And then there's also a vector Dube over here you can you can duplicate a vector of stuff over here. And then finally, the range permission and the range mission and these are the function that you have to implement

405
00:57:38.730 --> 00:57:51.090
William Cheng: Oh I so this is all the code that I don't want to walk through at this time next time we're going to take a look at some assembly code for you to, to, to implement a Hello World. Hello program. So I will see you till next week. Yeah.