keii.dev
1#include "malloc.h"
2#include <stdbool.h>
3#include <stdint.h>
4#include <string.h>
5#include <sys/mman.h>
6
7#define ALIGNMENT (4)
8#define DEVIDE_SPACE_BOUNDARY (32)
9
10static malloc_header_t* memory[MALLOC_MAX_ALLOCATED_BLOCKS];
11static size_t allocated_blocks = 0;
12
13static int _alloc_new_block(size_t sz);
14
15static int _alloc_new_block(size_t sz)
16{
17 sz += sizeof(malloc_header_t);
18
19 // this will reduce system calls for the small memory allocations
20 size_t allocated_sz = sz > MALLOC_DEFAULT_BLOCK_SIZE ? sz : MALLOC_DEFAULT_BLOCK_SIZE;
21
22 int ret = (int)mmap(NULL, allocated_sz, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, 0, 0);
23 if (ret < 0) {
24 return -1;
25 }
26 memory[allocated_blocks] = (void*)ret; // allocating a new block of memory
27 memory[allocated_blocks]->flags = 0;
28 memory[allocated_blocks]->next = 0;
29 memory[allocated_blocks]->prev = 0;
30 memory[allocated_blocks]->size = allocated_sz - sizeof(malloc_header_t);
31
32 allocated_blocks++;
33 return 0;
34}
35
36static inline char _malloc_need_to_divide_space(malloc_header_t* space, size_t alloc_size)
37{
38 return alloc_size + DEVIDE_SPACE_BOUNDARY <= space->size;
39}
40
41static inline char _malloc_can_fit_allocation(malloc_header_t* space, size_t alloc_size)
42{
43 uint32_t add[] = { 0, sizeof(malloc_header_t) };
44 return space->size >= (alloc_size + add[_malloc_need_to_divide_space(space, alloc_size)]);
45}
46
47void* malloc(size_t sz)
48{
49 if (!sz) {
50 return NULL;
51 }
52 sz += (ALIGNMENT - 1);
53 sz &= ~(uint32_t)(ALIGNMENT - 1);
54
55 void* res = slab_alloc(sz);
56 if (res) {
57 return res;
58 }
59
60 /* iterating over allocated by mmap blocks
61 and finding a first fit memory chunk */
62 malloc_header_t* first_fit = 0;
63 for (size_t i = 0; i < allocated_blocks; i++) {
64 malloc_header_t* cur_block = memory[i];
65 while (cur_block->next && !(block_is_free(cur_block) && _malloc_can_fit_allocation(cur_block, sz))) {
66 cur_block = cur_block->next;
67 }
68 if (block_is_free(cur_block) && _malloc_can_fit_allocation(cur_block, sz)) {
69 first_fit = cur_block;
70 break;
71 }
72 }
73
74 if (!first_fit) {
75 int err = _alloc_new_block(sz);
76 if (err) {
77 return NULL;
78 }
79 first_fit = memory[allocated_blocks - 1];
80 }
81
82 malloc_header_t* copy_next = first_fit->next;
83 size_t copy_size = first_fit->size;
84
85 first_fit->flags |= FLAG_ALLOCATED;
86 if (_malloc_need_to_divide_space(first_fit, sz)) {
87 first_fit->size = sz;
88 first_fit->next = (malloc_header_t*)((uintptr_t)first_fit + sz + sizeof(malloc_header_t));
89
90 // adjust the firstfit chunk
91 first_fit->next->flags = 0;
92 first_fit->next->size = copy_size - sz - sizeof(malloc_header_t);
93 first_fit->next->next = copy_next;
94 first_fit->next->prev = first_fit;
95
96 if (first_fit->next->next) {
97 first_fit->next->next->prev = first_fit->next;
98 }
99 }
100
101 return (void*)&((malloc_header_t*)first_fit)[1];
102}
103
104void free(void* mem)
105{
106 if (!mem) {
107 return;
108 }
109
110 malloc_header_t* mem_header = &((malloc_header_t*)mem)[-1];
111
112 if (block_is_slab(mem_header)) {
113 return slab_free(mem_header);
114 }
115
116 block_rem_flags(mem_header, FLAG_ALLOCATED);
117 while (mem_header->prev && block_is_free(mem_header->prev)) {
118 mem_header = mem_header->prev;
119 }
120
121 // Trying to glue the freed chunk with its neighbours.
122 while (mem_header->next && block_is_free(mem_header->next)) {
123 mem_header->size += mem_header->next->size + sizeof(malloc_header_t);
124
125 if (mem_header->next->next) {
126 mem_header->next->next->prev = mem_header;
127 }
128 mem_header->next = mem_header->next->next;
129 }
130}
131
132void* calloc(size_t num, size_t size)
133{
134 void* mem = malloc(num * size);
135 if (!mem) {
136 return NULL;
137 }
138
139 memset(mem, 0, num * size);
140 return mem;
141}
142
143void* realloc(void* ptr, size_t new_size)
144{
145 if (!ptr) {
146 return malloc(new_size);
147 }
148
149 size_t old_size = ((malloc_header_t*)ptr)[-1].size;
150 if (old_size == new_size) {
151 return ptr;
152 }
153
154 uint8_t* new_area = malloc(new_size);
155 if (!new_area) {
156 return NULL;
157 }
158
159 memcpy(new_area, ptr, new_size < old_size ? new_size : old_size);
160 free(ptr);
161
162 return new_area;
163}
164
165void _malloc_init()
166{
167 _slab_init();
168}