1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
#include <euler/syscall.hpp>
//i guess we could figure out which parts of the pages the kernel allocated to
//load the application were not actually needed and add those to the memory
//that is available to be allocated, but whatever.
namespace euler::allocator {
struct block_info {
//vaddr, divisible by size
uint64_t start;
//power of 2, 0 for unused
uint64_t size;
};
struct block_info_page {
block_info infos[255];
block_info_page *next;
};
static_assert(sizeof(block_info_page) == 4088);
static block_info_page *first_bi_page = 0;
static block_info *try_find_block(uint64_t start, uint64_t size) {
for (block_info_page *bip = first_bi_page; bip; bip = bip->next)
for (int i = 0; i < 255; ++i)
if (bip->infos[i].start == start && bip->infos[i].size == size)
return bip->infos + i;
return 0;
}
static block_info *add_block(uint64_t start, uint64_t size) {
for (block_info_page *bip = first_bi_page; bip; bip = bip->next)
for (int i = 0; i < 255; ++i)
if (bip->infos[i].size == 0) {
bip->infos[i].start = start;
bip->infos[i].size = size;
return bip->infos + i;
}
block_info_page *new_bip = (block_info_page *)_syscall_get_new_pages(1);
new_bip->infos[0].start = start;
new_bip->infos[0].size = size;
for (int i = 1; i < 255; ++i)
new_bip->infos[i].size = 0;
new_bip->next = first_bi_page;
first_bi_page = new_bip;
return new_bip->infos;
}
static block_info *find_minimal_block(uint64_t minimum_length) {
block_info *minimal_so_far = 0;
uint64_t length_so_far = UINT64_MAX;
for (block_info_page *bip = first_bi_page; bip; bip = bip->next)
for (int i = 0; i < 255; ++i)
if (bip->infos[i].size == minimum_length)
return bip->infos + i;
else if (
bip->infos[i].size > minimum_length &&
bip->infos[i].size < length_so_far
) {
minimal_so_far = bip->infos + i;
length_so_far = bip->infos[i].size;
}
if (minimal_so_far != 0)
return minimal_so_far;
uint64_t pages_needed = (minimum_length - 1) / 4096 + 1;
void *block_start = _syscall_get_new_pages(pages_needed);
return add_block((uint64_t)block_start, pages_needed * 4096);
}
static void deallocate_aligned(uint64_t start, uint64_t length) {
block_info *buddy = try_find_block(start ^ length, length);
if (buddy) {
buddy->size = 0;
deallocate_aligned(start & ~length, length * 2);
return;
}
add_block(start, length);
}
static void deallocate(void *start, uint64_t length) {
uint64_t at = (uint64_t)start;
uint64_t left = length;
uint64_t i;
for (i = 1; i <= left; i *= 2)
if (at & i) {
deallocate_aligned(at, i);
at += i;
left -= i;
}
for (i /= 2; left > 0; i /= 2)
if (i <= left) {
deallocate_aligned(at, i);
at += i;
left -= i;
}
}
[[nodiscard]] static void *allocate(uint64_t length) {
block_info *bi = find_minimal_block(length);
void *to_return = (void *)bi->start;
void *new_start = (void *)(bi->start + length);
uint64_t new_length = bi->size - length;
bi->size = 0;
deallocate(new_start, new_length);
return to_return;
}
static void deallocate_with_length(void *start) {
uint64_t real_start = (uint64_t)start - 8;
deallocate((void *)real_start, *(uint64_t *)real_start);
}
[[nodiscard]] static void *allocate_with_length(uint64_t length) {
uint64_t *real_start = (uint64_t *)allocate(length + 8);
*real_start = length + 8;
return real_start + 1;
}
}
using namespace euler::allocator;
void operator delete[](void *start) {
deallocate_with_length(start);
}
void operator delete(void *start) {
deallocate_with_length(start);
}
void operator delete[](void *start, uint64_t) {
deallocate_with_length(start);
}
void operator delete(void *start, uint64_t) {
deallocate_with_length(start);
}
void *operator new[](uint64_t size) {
return allocate_with_length(size);
}
void *operator new(uint64_t size) {
return allocate_with_length(size);
}
|