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
|
#include <types.h>
#include <heap.h>
#include <libk/math.h>
#include <paging.h>
#include <libk/serial_stdio.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 */
size_t i;
for (i = 0; i < bcnt; i++) {
bm[i] = 0;
}
uint32_t bcnt_used =
upper_div((bcnt + (uint32_t)sizeof(kheapblock_t)), bsize);
for (i = 0; i < bcnt_used; i++) {
bm[i] = 5;
}
kheapblock->used = bcnt_used;
}
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;
}
/* use heap with bsize 4096 just for that block size */
bool ind1 = ((size % 4096) == 0);
bool ind2 = (kheapblock->bsize == 4096);
if (ind1 + ind2 == 1) {
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 */
size_t i;
size_t j;
for (i = 0; i < bcnt; i++) {
if (bm[i] != 0) {
continue;
}
/* find bneed consecutive empty blocks */
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[0]);
}
}
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)(pointer) < (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[0];
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);
kheap_add_block(&main_kheap, HEAP1_VMEM_ADDR, HEAP1_SIZE,
HEAP1_BLOCK_SIZE);
kheap_add_block(&main_kheap, HEAP2_VMEM_ADDR, HEAP2_SIZE,
HEAP2_BLOCK_SIZE);
}
|
