blob: 1e69d8a7c0e8aea7086dbb332e830c244bb6efe9 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
|
#include <memory.h>
#include <stdint.h>
#include <lib.h>
#include <panic.h>
#define MAGIC 0xBEEFCAFE
struct page_header {
struct page_header *next;
struct page_header *prev;
size_t node_number; // all headers on the same page alloc have the same node number (so they can be merged)
size_t free; // free space after the node (if its the last node in the alloc block)
size_t used; // how much space this allocation is using
uint64_t magic;
};
static const size_t header_len = sizeof(struct page_header);
static struct page_header *start_header = NULL;
static struct page_header *end_header = NULL;
struct page_header *get_header(void *ptr) {
struct page_header *header =
(struct page_header *) ((uintptr_t) ptr - header_len);
// PERF: do we want to make sure this pointer is paged
// before reading it???
if (header->magic != MAGIC) {
return NULL; // invalid pointer
}
return header;
}
void *kalloc_new(size_t size) {
size_t pages = ((size + header_len) / PAGE_SIZE) + 1;
void *addr = alloc_pages(pages);
void *mem = (char *)addr + header_len;
size_t total = pages * PAGE_SIZE;
size_t free = total - (size + header_len);
if (addr == NULL) {
return NULL;
}
size_t node;
if (end_header != NULL) {
node = end_header->node_number + 1;
} else {
node = 0;
}
memcpy(addr, 0, pages * PAGE_SIZE);
struct page_header *header = addr;
header->magic = 0xBEEFCAFE;
header->used = size;
header->free = free;
header->prev = end_header;
header->next = NULL;
header->node_number = node;
if (start_header == NULL) {
start_header = header;
}
if (end_header != NULL) {
end_header->next = header;
} else {
end_header = header;
}
return mem;
}
void *kalloc_block(size_t size, struct page_header *block) {
struct page_header *header =
(struct page_header *) ((char *) block + block->used + header_len);
size_t free = block->free - (size + header_len);
block->free = 0;
header->magic = MAGIC;
header->used = size;
header->free = free;
header->prev = block;
header->next = block->next;
block->next = header;
header->node_number = block->node_number;
void *mem = (char *) header + header_len;
return mem;
}
void *kalloc(size_t size) {
struct page_header *header = start_header;
for (; header != NULL; header = header->next) {
size_t free = header->free;
if (free < header_len) {
continue;
}
if (size <= (free - header_len)) { // we must be able to fit data + header
break;
}
}
if (header != NULL) {
return kalloc_block(size, header);
} else {
return kalloc_new(size);
}
}
void *krealloc(void *src, size_t dst_len) {
struct page_header *header;
size_t src_len;
void *dst;
// realloc of 0 means free pointer
if (dst_len == 0) {
kfree(src);
return NULL;
}
// NULL src means allocate ptr
if (src == NULL) {
dst = kalloc(dst_len);
return dst;
}
header = get_header(src);
if (header == NULL) {
panic("attempted to realloc on a invalid ptr");
}
src_len = header->used;
if (src_len == 0) {
panic("attempted to realloc on an empty ptr");
}
dst = kalloc(dst_len);
if (dst == NULL) {
return NULL; // allocation failed
}
if (dst_len < src_len)
src_len = dst_len;
memcpy(dst, src, src_len);
kfree(src);
return dst;
}
void kfree(void *ptr) {
struct page_header *header;
if (ptr == NULL) {
return;
}
header = get_header(ptr);
if (header == NULL) {
panic("attempted to kfree invalid pointer");
}
header->free += header->used;
header->used = 0;
struct page_header *neighbor;
// merge left
for (neighbor = header->prev; neighbor != NULL; neighbor = neighbor->prev) {
if (neighbor->node_number != header->node_number)
break;
if (neighbor->used && header->used)
break;
neighbor->free += header->free + header_len;
neighbor->next = header->next;
header = neighbor;
}
// merge right
for (neighbor = header->next; neighbor != NULL; neighbor = neighbor->next) {
if (neighbor->node_number != header->node_number)
break;
if (neighbor->used)
break;
header->free += neighbor->free + header_len;
header->next = neighbor->next;
}
if (
(header->next == NULL || header->next->node_number != header->node_number) &&
(header->prev == NULL || header->prev->node_number != header->node_number) &&
header->used == 0
) {
if (header->next)
header->next->prev = header->prev;
if (header->prev)
header->prev->next = header->next;
free_pages(header);
}
}
|
