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
|
#include <types.h>
#include <heap.h>
#include <libk/math.h>
#include <paging.h>
#include <libk/stdio.h>
kheap_t main_kheap;
void kheap_init(kheap_t* kheap)
{
kheap->fblock = NULL;
}
void kheap_add_block(kheap_t* kheap, uint64_t addr, uint32_t size, uint32_t bsize)
{
kheapblock_t *kheapblock;
// store size & bsize into kheapblock
kheapblock = (kheapblock_t*)addr;
kheapblock->size = size - (uint32_t)sizeof(kheapblock_t);
kheapblock->bsize = bsize;
// add kheapblock to kheap
kheapblock->next = kheap->fblock;
kheap->fblock = kheapblock;
// block count & bitmap
uint32_t bcnt = kheapblock->size / kheapblock->bsize;
uint8_t* bm = (uint8_t*)&kheapblock[1];
// clear bitmap
for (size_t i = 0; i < bcnt; i++) {
bm[i] = 0;
}
bcnt = upper_div(bcnt, bsize);
for (size_t i = 0; i < bcnt; i++) {
bm[i] = 5;
}
kheapblock->used = bcnt;
}
void* kheap_alloc(kheap_t* kheap, uint32_t size)
{
kheapblock_t* kheapblock;
// find kheapblock that has enough space
for (kheapblock = kheap->fblock; kheapblock; kheapblock = kheapblock->next) {
if (kheapblock->size - (kheapblock->used * kheapblock->bsize) < size) {
continue;
}
uint32_t bcnt = kheapblock->size / kheapblock->bsize;
uint32_t bneed = upper_div(size, kheapblock->bsize);
uint8_t* bm = (uint8_t*)&kheapblock[1];
// find empty block
for (size_t i = 0; i < bcnt; i++) {
if (bm[i] != 0) {
continue;
}
// find bneed consecutive empty blocks
size_t j;
for (j = 0; bm[i + j] == 0 && j < bneed && i + j < bcnt; j++);
if (j != bneed) {
i += j - 1;
continue;
}
// using id for the block that is different from previous or next block
uint8_t idp = bm[i - 1], idn = bm[i + j], id;
for (id = idp + 1; id == idn || id == 0; id++);
// mark blocks as used
for (j = 0; j < bneed; j++) {
bm[i + j] = id;
}
kheapblock->used += bneed;
return (void*)(i * kheapblock->bsize + (uintptr_t)&kheapblock[1]);
}
}
printf("Error: there is no remaining memory in kheap\n");
return NULL;
}
void kheap_free(kheap_t* kheap, void* pointer)
{
kheapblock_t* kheapblock;
for (kheapblock = kheap->fblock; kheapblock; kheapblock = kheapblock->next) {
if ((uintptr_t)(pointer) > (uintptr_t)kheapblock && (uintptr_t)kheapblock + sizeof(kheapblock_t) + kheapblock->size) {
// found block
// get index of bitmap entry
uintptr_t pointer_offset = (uintptr_t)pointer - (uintptr_t)&kheapblock[1];
uint32_t bi = (uint32_t)pointer_offset / kheapblock->bsize;
uint8_t* bm = (uint8_t*)&kheapblock[1];
uint8_t id = bm[bi];
uint32_t max = kheapblock->size / kheapblock->bsize;
// set blocks as free
size_t i;
for (i = bi; bm[i] == id && i < max; i++) {
bm[i] = 0;
}
kheapblock->used -= (uint32_t)i - bi;
return;
}
}
printf("Error: %x not freed from kheap\n", pointer);
}
void init_heap()
{
kheap_init(&main_kheap);
// allocate pages for kheap
for (size_t i = 0; i < upper_div(HEAP_SIZE, PAGE_SIZE); i++)
map_addr(HEAP_START_ADDR + i * PAGE_SIZE, HEAP_START_ADDR + i * PAGE_SIZE, FLAG_PRESENT + FLAG_WRITABLE + FLAG_HUGE);
kheap_add_block(&main_kheap, HEAP_START_ADDR, HEAP_SIZE, HEAP_BLOCK_SIZE);
}
|
