blob: 042049d238110a7e03d989a1facf2c27ddbb5a61 (
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
|
#include "stdio.h"
#include "stdlib.h"
#include "../errno.h"
#include <stdint.h>
#include <stddef.h>
#include <string.h>
#define NEW_ALLOC_SIZE 0x1000
#define IS_FREE (1 << 0)
#define IS_FINAL (1 << 1)
typedef struct MallocHeader {
uint32_t size;
uint8_t flags;
} MallocHeader;
MallocHeader *head = NULL;
MallocHeader *final = NULL;
uint32_t total_heap_size = 0;
int init_heap(void) {
head = sbrk(NEW_ALLOC_SIZE);
if ((void *)-1 == head) {
// perror("sbrk");
return 0;
}
total_heap_size += NEW_ALLOC_SIZE;
head->size = NEW_ALLOC_SIZE;
head->flags = IS_FREE | IS_FINAL;
final = head;
return 1;
}
int add_heap_memory(void) {
if ((void *)-1 == sbrk(NEW_ALLOC_SIZE)) {
// perror("sbrk");
return 0;
}
total_heap_size += NEW_ALLOC_SIZE;
final->size += NEW_ALLOC_SIZE;
return 1;
}
MallocHeader *next_header(MallocHeader *a) {
if (a->flags & IS_FINAL)
return NULL;
return ((void *)a) + a->size;
}
MallocHeader *find_free_entry(uint32_t s) {
// A new header is required as well as the newly allocated chunk
s += sizeof(MallocHeader);
if (!head)
init_heap();
MallocHeader *p = head;
for (; p; p = next_header(p)) {
if (!(p->flags & IS_FREE))
continue;
if (p->size < s)
continue;
return p;
}
return NULL;
}
void merge_headers(MallocHeader *b) {
if (!(b->flags & IS_FREE))
return;
MallocHeader *n = next_header(b);
if (!n)
return;
if (!(n->flags & IS_FREE))
return;
// Remove the next header and just increase the newly freed header
b->size += n->size;
b->flags |= n->flags & IS_FINAL;
if (b->flags & IS_FINAL)
final = b;
}
extern int errno;
// https://pubs.opengroup.org/onlinepubs/9699919799/
void *malloc(size_t s) {
if(s == 0)
s = 1;
MallocHeader *free_entry = find_free_entry(s);
if (!free_entry) {
if (!add_heap_memory()) {
errno = ENOMEM;
return NULL;
}
return malloc(s);
}
// Create a new header
MallocHeader *new_entry = ((void *)free_entry) + s;
new_entry->flags |= IS_FREE;
new_entry->size = free_entry->size - s - sizeof(MallocHeader);
new_entry->flags |= free_entry->flags & IS_FINAL;
if (new_entry->flags & IS_FINAL)
final = new_entry;
merge_headers(new_entry);
// Modify the free entry
free_entry->size = s;
free_entry->flags = 0;
return ((void *)free_entry) + sizeof(MallocHeader);
}
// https://pubs.opengroup.org/onlinepubs/9699919799/
void *calloc(size_t nelem, size_t elsize) {
// The calloc() function shall allocate unused space for an array of
// nelem elements each of whose size in bytes is elsize.
size_t alloc_size = nelem*elsize;
void *rc = malloc(alloc_size);
// The space shall be initialized to all bits 0.
memset(rc, 0, alloc_size);
return rc;
}
void free(void *p) {
// FIXME: This assumes that p is at the start of a allocated area.
// Is this a assumption that can be made?
MallocHeader *h = p - sizeof(MallocHeader);
if (h->flags & IS_FREE)
return;
h->flags |= IS_FREE;
merge_headers(h);
}
|
