1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
allocating large pages
context:
- x86_64 has three page sizes: 4K, 2M, 1G
- we only care about 4K and 2M right now
- pages have to be aligned on their size (2M is aligned at % 2M)
- memory capabilities have a small amount of storage to maintain the linked list
head for the free list
Memory capability
+-------------+
| head_4K ---> 2
| head_2M ---> 8
| ... |
+-------------+
Memory layout
0 1 2 3 |============== 2MiB ===============|
+-----------------------------------+-----------------------------------+
|........|........| | |...................................|
|..used..|..used..| *-------> -1 |...............used................|
|........|........| | |...................................|
+-----------------------------------+-----------------------------------+
|= 4KiB =|
8 16
+-----------------------------------+-----------------------------------+
| | |
| *---------------------------------> *--------------------------------->
| | |
+-----------------------------------+-----------------------------------+
24 32
+-----------------------------------+-----------------------------------+
| | |
| *---------------------------------> *--------------------------------->
| | |
+-----------------------------------+-----------------------------------+
40 48
+-----------------------------------+-----------------------------------+
| | |
| *---------------------------------> -1 |
| | |
+-----------------------------------+-----------------------------------+
Initially, memory is filled with a linked list of 2 MiB pages. head_4K is set to
-1 and head_2M is set to the first 2 MiB page.
Allocation algorithm
if 4K page
if head_4K != -1
[LABEL do_alloc_4K]
page = *head_4K
head_4K = *page
return page
else if head_2M == -1
out of memory
else
large_page = *head_2M
head_2M = *large_page
init_4K_freelist(large_page)
head_4K = large_page
GOTO do_alloc_4K
if 2M page
if head_2M != -1
page = *head_2M
head_2M = *page
else
out of memory
problems!
- freeing 4K pages. We can figure out what its 2M block is with a mask but we
lose its head. We'll probably have to waste the first 4K page out of every 2M
block to store the free list head, or a bitmap (512 bits). Buddy allocator
state would also fit in the first page (1024 bits ish)
- memory areas not divisible by 2M, or whose physical address is not 2M-aligned.
probably managable with a flag in the first page which indicates that a given
2M bucket is only useful for 4K allocations