1
00:00:01,180 --> 00:00:07,210
In this lecture, we will collect the free memory, divide them into a bunch of 2m pages 

2
00:00:07,210 --> 00:00:09,370
and save them in the linked list for later use. 

3
00:00:10,030 --> 00:00:13,940
The free memory we are talking about in this example is physical memory. 

4
00:00:14,770 --> 00:00:20,860
Let’s start from where we left off.   In the last video, we collect the memory map using the for loop 

5
00:00:21,490 --> 00:00:22,870
and print on the screen. 

6
00:00:25,590 --> 00:00:31,320
In this video, we will divide the free memory into a bunch of 2Mb pages 

7
00:00:31,320 --> 00:00:32,759
and these pages are used for the memory module. 

8
00:00:33,270 --> 00:00:37,500
So the memory module use 2m pages instead of 1g page.

9
00:00:39,090 --> 00:00:40,390
But here is the problem.

10
00:00:40,890 --> 00:00:46,260
remember we have mapped our kernel to the higher part of the memory, and we are using virtual address

11
00:00:46,260 --> 00:00:49,040
in the system after we enter 64-bit mode. 

12
00:00:49,980 --> 00:00:53,300
The free memory the memory module uses is physical address. 

13
00:00:53,910 --> 00:00:59,950
So the first thing we need to do is find the physical address according to the virtual address. 

14
00:01:00,000 --> 00:01:00,290
To achieve it, 

15
00:01:00,330 --> 00:01:02,130
we use a very simple method. 

16
00:01:04,340 --> 00:01:08,200
As you see, this is the virtual address space we have talked about before, 

17
00:01:09,400 --> 00:01:14,710
the lower 1g address space is mapped to the corresponding physical page at this point. 

18
00:01:16,170 --> 00:01:21,990
And we also mapped our kernel which is located at the higher part of virtual space to the same physical page 

19
00:01:21,990 --> 00:01:22,410
.

20
00:01:24,140 --> 00:01:29,540
In the following lectures, we will only remap the kernel space and leave the user space unused. 

21
00:01:31,010 --> 00:01:37,190
So the kernel space is what we will focus on.  In this example, we just map the whole 1g of memory space 

22
00:01:37,190 --> 00:01:43,700
to the 1g physical space, which means the offsets within the memory space remain unchanged

23
00:01:43,700 --> 00:01:44,360
.

24
00:01:45,630 --> 00:01:51,450
So to get the physical address we can simply subtract the value which is the base of kernel space from the virtual address. 

25
00:01:51,600 --> 00:01:54,840
The equation is like this 

26
00:01:56,470 --> 00:02:00,910
The virtual address is equal to physical address plus the base of the kernel. 

27
00:02:01,930 --> 00:02:08,620
And also, we only use the first 1gb of ram and simply ignore other free memory. 

28
00:02:08,620 --> 00:02:14,500
The reason is that we only mapped 1gb of ram in the loader file and 1gb of ram is enough for our small kernel. 

29
00:02:14,500 --> 00:02:17,330
If you want to use more ram, 

30
00:02:17,650 --> 00:02:21,400
don’t forget to set the corresponding items in the page translation tables. 

31
00:02:22,350 --> 00:02:23,790
OK, back to the project.

32
00:02:26,020 --> 00:02:27,550
In the memory header file, 

33
00:02:31,290 --> 00:02:35,460
you can see the macro page size which is set to 2mb. 

34
00:02:38,630 --> 00:02:45,230
The next two macros align the address to 2m boundary. The page align up will align the address 

35
00:02:45,230 --> 00:02:50,720
to the next 2m boundary if it is not aligned.  The page align down 

36
00:02:51,170 --> 00:02:53,810
will align the address to the previous 2m boundary 

37
00:02:53,810 --> 00:02:54,290
.

38
00:02:55,280 --> 00:03:01,550
There are several ways to do it. In this example, we simply shift right 21 bits and then shift left

39
00:03:01,550 --> 00:03:06,460
which will clear the 21 bits of the value and now we get the aligned address. 

40
00:03:08,770 --> 00:03:15,100
The p2v and v2p, as we have talked about, converts between virtual address and physical address 

41
00:03:15,100 --> 00:03:19,000
by adding or subtracting the base of the kernel. 

42
00:03:20,470 --> 00:03:20,860
OK.

43
00:03:21,870 --> 00:03:29,430
in the memory.c file, we divide the free memory into a bunch of 2mb pages. Here we define two variables

44
00:03:29,550 --> 00:03:35,430
vstart and vend which represent the beginning and end of the memory region. 

45
00:03:36,180 --> 00:03:40,580
You can see we use p2v to convert the physical address to virtual address 

46
00:03:41,310 --> 00:03:43,110
and assign it to the vstart. 

47
00:03:43,800 --> 00:03:47,950
Then we set vend by adding the length of region to vstart. 

48
00:03:48,600 --> 00:03:53,430
So vstart and vend hold the virtual addresses instead of physical address. 

49
00:03:54,560 --> 00:03:57,500
Now we get to the initialization of free memory part. 

50
00:03:58,770 --> 00:04:04,280
In this system, the memory we care about is from the end of our kernel to the end of the 1st gigabytes of memory

51
00:04:04,380 --> 00:04:05,350
.

52
00:04:06,060 --> 00:04:10,470
So how do we know where the end of our kernel is. 

53
00:04:12,560 --> 00:04:17,180
To get the info, we can add a symbol in the linker script. 

54
00:04:19,390 --> 00:04:26,770
At the end of the linker script, we write provide end = .,  which means the label end

55
00:04:26,770 --> 00:04:29,650
will represent the current position that is the end of the kernel. 

56
00:04:30,850 --> 00:04:34,570
Ok at this point, we can use the label end in the c file. 

57
00:04:35,470 --> 00:04:37,090
So let's go back to C file.

58
00:04:41,090 --> 00:04:46,970
Here we extern end, since it is not define in this module and set it to char type. 

59
00:04:47,860 --> 00:04:52,630
Alright, the next thing we are going to do is we are going to check the location of the memory region. 

60
00:04:55,250 --> 00:05:01,970
If the start of memory region is larger than the end of kernel, this is the free memory we want 

61
00:05:01,970 --> 00:05:05,330
and we do the initialization by calling function free region. 

62
00:05:06,540 --> 00:05:11,710
Note that here we need the address of end because the end is a symbol instead of a variable. 

63
00:05:12,550 --> 00:05:13,670
OK, let's move on.

64
00:05:14,590 --> 00:05:19,690
If the start address of the memory region is less than the end of kernel, 

65
00:05:19,690 --> 00:05:25,930
we will compare the end of the region with the end of the kernel.  If it is larger than the end of kernel, we will initialize the memory

66
00:05:25,930 --> 00:05:28,420
from the end of the kernel to the end of the region. 

67
00:05:29,420 --> 00:05:32,570
Otherwise we ignore the region because it is within the kernel. 

68
00:05:33,700 --> 00:05:35,710
Let’s see the function free region. 

69
00:05:37,900 --> 00:05:43,950
This function is simple, all it does is just divide the region into 2mb pages 

70
00:05:43,960 --> 00:05:46,270
and call the function kfree to collect the pages. 

71
00:05:46,840 --> 00:05:52,030
So in the for loop, we start off by aligning the address to the next 2m boundary. 

72
00:05:52,990 --> 00:05:55,540
Then we compare this page with the end of the region. 

73
00:05:56,320 --> 00:06:01,240
If it is within the region, we call the free function. 

74
00:06:01,250 --> 00:06:02,680
Note that here we also add another check.

75
00:06:03,460 --> 00:06:06,190
This value is 1g above the base of kernel. 

76
00:06:06,670 --> 00:06:12,340
So what it does is just check to see if the page we are about to initialize is beyond the first 1g of ram

77
00:06:12,340 --> 00:06:13,250
.

78
00:06:14,080 --> 00:06:17,560
Remember we only use the first 1g of ram in the program.

79
00:06:18,750 --> 00:06:20,890
OK, let's move to the kfree function.

80
00:06:21,630 --> 00:06:24,060
This is the function where we do the initialization. 

81
00:06:25,100 --> 00:06:32,180
Before we start, we add these simple checks, the first one is to make sure that the virtual address is page aligned. 

82
00:06:33,020 --> 00:06:36,500
The next one assumes that the virtual address is not within the kernel. 

83
00:06:37,500 --> 00:06:40,200
And the last one checks 1g memory limits. 

84
00:06:41,620 --> 00:06:43,640
OK, now we can collect the pages.

85
00:06:46,760 --> 00:06:49,940
These bunch of pages are stored in the form of linked list. 

86
00:06:50,860 --> 00:06:56,140
As you see, when we add a page, what we really do is that we link the page to the existing one.

87
00:06:57,400 --> 00:07:00,640
As we added more pages, we will extend the list.

88
00:07:02,220 --> 00:07:08,850
In the project, we use the link list except that we add pages in the reverse order.

89
00:07:08,850 --> 00:07:09,330
Let’s see how to do it.  

90
00:07:10,580 --> 00:07:11,790
In the header file, 

91
00:07:13,480 --> 00:07:16,870
the structure page is used to implement the linked list.

92
00:07:17,470 --> 00:07:21,760
It includes only one item which is the pointer to the next page structure. 

93
00:07:22,810 --> 00:07:29,140
So you see we use the first 8 bytes of every page to store the location of the next page 

94
00:07:29,140 --> 00:07:30,280
which creates a list of pages. 

95
00:07:31,170 --> 00:07:33,210
Ok in the c file, 

96
00:07:36,680 --> 00:07:40,490
we define the variable free memory which is the head of the linked list.

97
00:07:45,860 --> 00:07:52,110
In the function, we first convert the virtual address to the pointer to type structure page. 

98
00:07:52,370 --> 00:07:57,980
Next we copy the head of the list to the first 8 bytes of the page and then save the virtual address to free memory. 

99
00:07:59,380 --> 00:08:03,310
At this point, the head of the linked list points to the current page. 

100
00:08:04,790 --> 00:08:07,640
Alright, that’s it for the memory initialization.  

101
00:08:09,020 --> 00:08:11,990
Let's go back to the function, initialize memory.

102
00:08:14,260 --> 00:08:20,650
After we exit out the for loop, we have collected the free memory pages and we define a variable memory end 

103
00:08:20,920 --> 00:08:23,620
to save the end of the free memory. 

104
00:08:24,580 --> 00:08:30,610
Because we add the pages to the list in the reverse order, the head of the list points to the last page we collect, 

105
00:08:30,610 --> 00:08:36,850
then we add the page size.  The result is the end of free memory we can use in the system. 

106
00:08:37,539 --> 00:08:41,830
Here we print the message on the screen. We will check it out when we run the system. 

107
00:08:42,970 --> 00:08:45,690
The last function we will implement in this file

108
00:08:47,240 --> 00:08:53,570
is kalloc used in the kernel mode.  Allocating memory is just removing a page from the page list 

109
00:08:53,570 --> 00:08:55,600
and return to the caller. 

110
00:08:56,390 --> 00:09:03,020
So we copy the first page in the list to page address and check to see if it is NULL. If the page is not NULL

111
00:09:03,020 --> 00:09:03,230
,  

112
00:09:03,260 --> 00:09:07,370
this is a valid page and we will return the page to the caller. 

113
00:09:08,270 --> 00:09:14,600
As we did in the function kfree, we add the same checks before we allocate the page. 

114
00:09:14,600 --> 00:09:16,730
And then make the head of the list point to the next page. 

115
00:09:17,720 --> 00:09:19,970
No, we have removed the page from the list.

116
00:09:20,900 --> 00:09:22,380
Return the page and we are done. 

117
00:09:23,240 --> 00:09:25,850
Let’s run the build script and test it out. 

118
00:09:28,910 --> 00:09:29,890
let's run bochs

119
00:09:34,220 --> 00:09:37,680
As you see, the end of free memory in this example is this value.

120
00:09:38,870 --> 00:09:44,720
The free memory in the fourth entry is starting from 1mb. We add it to the length of the region 

121
00:09:44,720 --> 00:09:51,240
which produce the value 3fff0000 and we add the base of the kernel. 

122
00:09:51,530 --> 00:09:58,460
The result is ffff80003fff0000. 

123
00:09:59,330 --> 00:10:03,270
As you can see, the end of the free memory the system collect is different.

124
00:10:04,100 --> 00:10:08,300
Remember the free memory is stored as a list of 2m pages. 

125
00:10:09,230 --> 00:10:12,920
The memory address we get is not 2m aligned.

126
00:10:13,340 --> 00:10:16,210
If we align it to the previous 2m boundary, 

127
00:10:16,700 --> 00:10:19,970
we will find that we get the exact value showing on the screen.

128
00:10:21,450 --> 00:10:27,810
And also here we cannot align the address to the next 2m boundary, if we do it, we will include 

129
00:10:27,820 --> 00:10:28,950
the reserved memory.

130
00:10:30,410 --> 00:10:32,150
OK, that's it for this video.