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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
|
#include <stddef.h>
#include <stdint.h>
#if !defined(__cplusplus)
#if (defined(_MSC_VER) && _MSC_VER < 1800) || (!defined(_MSC_VER) && !defined(__STDC_VERSION__))
#ifndef true
#define true (0 == 0)
#endif
#ifndef false
#define false (0 != 0)
#endif
typedef unsigned char bool;
#else
#include <stdbool.h>
#endif
#endif
#include <stdio.h>
#include <assert.h>
#include <string.h>
bool is_power_of_two(uintptr_t x) {
return (x & (x-1)) == 0;
}
uintptr_t align_forward(uintptr_t ptr, size_t align) {
uintptr_t p, a, modulo;
assert(is_power_of_two(align));
p = ptr;
a = (uintptr_t)align;
// Same as (p % a) but faster as 'a' is a power of two
modulo = p & (a-1);
if (modulo != 0) {
// If 'p' address is not aligned, push the address to the
// next value which is aligned
p += a - modulo;
}
return p;
}
#ifndef DEFAULT_ALIGNMENT
#define DEFAULT_ALIGNMENT (2*sizeof(void *))
#endif
typedef struct Arena Arena;
struct Arena {
unsigned char *buf;
size_t buf_len;
size_t prev_offset; // This will be useful for later on
size_t curr_offset;
};
void arena_init(Arena *a, void *backing_buffer, size_t backing_buffer_length) {
a->buf = (unsigned char *)backing_buffer;
a->buf_len = backing_buffer_length;
a->curr_offset = 0;
a->prev_offset = 0;
}
void *arena_alloc_align(Arena *a, size_t size, size_t align) {
// Align 'curr_offset' forward to the specified alignment
uintptr_t curr_ptr = (uintptr_t)a->buf + (uintptr_t)a->curr_offset;
uintptr_t offset = align_forward(curr_ptr, align);
offset -= (uintptr_t)a->buf; // Change to relative offset
// Check to see if the backing memory has space left
if (offset+size <= a->buf_len) {
void *ptr = &a->buf[offset];
a->prev_offset = offset;
a->curr_offset = offset+size;
// Zero new memory by default
memset(ptr, 0, size);
return ptr;
}
// Return NULL if the arena is out of memory (or handle differently)
return NULL;
}
// Because C doesn't have default parameters
void *arena_alloc(Arena *a, size_t size) {
return arena_alloc_align(a, size, DEFAULT_ALIGNMENT);
}
void arena_free(Arena *a, void *ptr) {
// Do nothing
}
void *arena_resize_align(Arena *a, void *old_memory, size_t old_size, size_t new_size, size_t align) {
unsigned char *old_mem = (unsigned char *)old_memory;
assert(is_power_of_two(align));
if (old_mem == NULL || old_size == 0) {
return arena_alloc_align(a, new_size, align);
} else if (a->buf <= old_mem && old_mem < a->buf+buf_len) {
if (a->buf+a->prev_offset == old_mem) {
a->curr_offset = a->prev_offset + new_size;
if (new_size > old_size) {
// Zero the new memory by default
memset(&a->buf[a->curr_offset], 0, new_size-old_size);
}
return old_memory;
} else {
void *new_memory = arena_alloc_align(a, new_size, align);
size_t copy_size = old_size < new_size ? old_size : new_size;
// Copy across old memory to the new memory
memmove(new_memory, old_memory, copy_size);
return new_memory;
}
} else {
assert(0 && "Memory is out of bounds of the buffer in this arena");
return NULL;
}
}
// Because C doesn't have default parameters
void *arena_resize(Arena *a, void *old_memory, size_t old_size, size_t new_size) {
return arena_resize_align(a, old_memory, old_size, new_size, DEFAULT_ALIGNMENT);
}
void arena_free_all(Arena *a) {
a->curr_offset = 0;
a->prev_offset = 0;
}
// Extra Features
typedef struct Temp_Arena_Memory Temp_Arena_Memory;
struct Temp_Arena_Memory {
Arena *arena;
size_t prev_offset;
size_t curr_offset;
};
Temp_Arena_Memory temp_arena_memory_begin(Arena *a) {
Temp_Arena_Memory temp;
temp.arena = a;
temp.prev_offset = a->prev_offset;
temp.curr_offset = a->curr_offset;
return temp;
}
void temp_arena_memory_end(Temp_Arena_Memory temp) {
temp.arena->prev_offset = temp.prev_offset;
temp.arena->curr_offset = temp.curr_offset;
}
int main(int argc, char **argv) {
int i;
unsigned char backing_buffer[256];
Arena a = {0};
arena_init(&a, backing_buffer, 256);
for (i = 0; i < 10; i++) {
int *x;
float *f;
char *str;
// Reset all arena offsets for each loop
arena_free_all(&a);
x = (int *)arena_alloc(&a, sizeof(int));
f = (float *)arena_alloc(&a, sizeof(float));
str = arena_alloc(&a, 10);
*x = 123;
*f = 987;
memmove(str, "Hellope", 7);
printf("%p: %d\n", x, *x);
printf("%p: %f\n", f, *f);
printf("%p: %s\n", str, str);
str = arena_resize(&a, str, 10, 16);
memmove(str+7, " world!", 7);
printf("%p: %s\n", str, str);
}
arena_free_all(&a);
return 0;
}
|
我们使用一个 free list (linked-list) 来存储空闲的 chunks。
一般 free list 是直接写在 chunk 的内部（头部）。
该方法中，我们使用一个 linked list 存储一个连续的内存块及其的大小。当用户申请内存时，我们查找并返回一个满足需求的内存块，同时将该块从 linked list 中删除，并且在 block 的头部存储一个 header 信息。当 free 的时候，我们通过 header 的信息，知道需要 free 块的大小，将该块插入到 linked list 中，最后我们还会将邻近的 free blocks 进行合并变成更大的 block。