blob: 2909ba7b1cbdc7b57ca0cf1512ecf2418bedca5a (
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
|
#include "halt.h"
#include "heap.h"
#define PAGESIZE 0x1000
#define MAGIC ((void *) 0x69)
typedef struct __attribute__((packed)) Header {
struct Header *next;
usize size;
} Header;
static Header init_free_ptr;
static Header *free_ptr = nil;
void free(void *ptr)
{
Header *h = ((Header *) ptr) - 1;
if (h->next != MAGIC)
panic("free: invalid pointer");
Header *next = free_ptr->next;
free_ptr->next = h;
h->next = next;
}
static void defragment()
{
//usize num_blocks = 0;
panic("defragment not implemented");
}
void *try_malloc(usize size)
{
for (Header *prev = free_ptr;; prev = prev->next) {
Header *h = prev->next;
if (h->size < size) {
if (h == free_ptr)
break;
else
continue;
}
if (h->size <= size + sizeof(Header)) {
prev->next = h->next;
} else {
// split
h->size -= size;
h = ((void *) h) + sizeof(Header) + h->size;
h->size = size;
}
h->next = MAGIC;
free_ptr = prev;
return h + 1;
}
return nil;
}
void *malloc(usize size)
{
void *p;
p = try_malloc(size);
if (p) return p;
defragment();
p = try_malloc(size);
if (p) return p;
panic("out of memory");
return nil;
}
void heap_init()
{
free_ptr = &init_free_ptr;
free_ptr->size = 0;
free_ptr->next = free_ptr;
}
void heap_add(void *ptr, usize size)
{
// discard blocks that are too small
if (size <= sizeof(Header))
return;
Header *h = ptr;
h->next = MAGIC;
h->size = size - sizeof(Header);
free(h + 1);
}
void heap_add_region(MemRegion *region)
{
switch (region->used) {
// region is reserved
case -1:
break;
// region is entirely free
case 0:
heap_add(region->start, region->size);
break;
// region is partly used
default: {
void *region_end = region->start + region->size;
// rounds up region->start to pagesize align
void *use_begin = (void *) ((u64) (region->start + PAGESIZE - 1) & ~(PAGESIZE - 1));
void *use_end = use_begin + region->used;
heap_add(region->start, use_begin - region->start);
heap_add(use_end, region_end - use_end);
}
}
region->used = -1; // just to be safe
}
|
