1#include <stdbit.h>
2#include <stdio.h>
3#include <stdlib.h>
4#include <sys/mman.h>
5
6#include "alignment.h"
7#include "dump.h"
8#include "fsb_arena.h"
9#include "src/word.h"
10
11struct _FsbaPageHeader {
12 FsbArena* arena;
13 struct _FsbaPageHeader* next;
14 struct _FsbaPageHeader* prev;
15 unsigned num_free;
16 Word bitmap[ /* bitmap_size */ ];
17};
18
19static void add_to_list(FsbaPageHeader** list, FsbaPageHeader* page)
20/*
21 * Add page to circular doubly-linked list.
22 */
23{
24 FsbaPageHeader* first = *list;
25 if (first == nullptr) {
26 // init list
27 *list = page->next = page->prev = page;
28 } else {
29 page->prev = first->prev;
30 page->next = first;
31 first->prev->next = page;
32 first->prev = page;
33 *list = page;
34 }
35}
36
37static void delete_from_list(FsbaPageHeader** list, FsbaPageHeader* page)
38/*
39 * Delete page from circular doubly-linked list.
40 */
41{
42 if (page->next == page->prev) {
43 // last page, make list empty
44 *list = nullptr;
45 } else {
46 if (*list == page) {
47 *list = page->next;
48 }
49 page->next->prev = page->prev;
50 page->prev->next = page->next;
51 }
52}
53
54static inline void free_page(FsbaPageHeader* page)
55{
56 munmap(page, sys_page_size());
57}
58
59bool _init_fsb_arena(FsbArena* arena, unsigned block_size, unsigned block_alignment)
60{
61 if (block_size < block_alignment) {
62 arena->block_size = block_alignment;
63 } else {
64 arena->block_size = block_size;
65 }
66 unsigned header_size = align_unsigned(sizeof(FsbaPageHeader) + sizeof(Word), arena->block_size);
67 unsigned max_block_size = sys_page_size() - header_size;
68
69 if (arena->block_size > max_block_size) {
70 return false;
71 }
72
73 // calculate bitmap size and blocks per page
74 arena->bitmap_size = 0;
75 do {
76 arena->bitmap_size++;
77 header_size = align_unsigned(sizeof(FsbaPageHeader) + sizeof(Word) * arena->bitmap_size, arena->block_size);
78 arena->blocks_per_page = (sys_page_size() - header_size) / arena->block_size;
79 } while (arena->blocks_per_page > (arena->bitmap_size * WORD_WIDTH));
80
81 // initialize lists
82 arena->avail_pages = nullptr;
83 arena->full_pages = nullptr;
84 return true;
85}
86
87void destroy_fsb_arena(FsbArena* arena)
88{
89 FsbaPageHeader* page = arena->avail_pages;
90 FsbaPageHeader* next;
91 if (page) {
92 do {
93 next = page->next;
94 free_page(page);
95 } while (page != next);
96 }
97 page = arena->full_pages;
98 if (page) {
99 do {
100 next = page->next;
101 free_page(page);
102 } while (page != next);
103 }
104 arena->avail_pages = nullptr;
105 arena->full_pages = nullptr;
106}
107
108void* fsb_arena_allocate(FsbArena* arena)
109{
110 FsbaPageHeader* page = arena->avail_pages;
111 if (!page) {
112 // allocate new page
113 page = mmap(nullptr, sys_page_size(), PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
114 if (page == MAP_FAILED) {
115 return nullptr;
116 }
117 page->arena = arena;
118 page->num_free = arena->blocks_per_page;
119 Word* bitmap = page->bitmap;
120 for (unsigned i = 0, n = arena->bitmap_size; i < n; i++) {
121 *bitmap++ = 0;
122 }
123 add_to_list(&arena->avail_pages, page);
124 }
125 // find available position in the bitmap
126 unsigned bitmap_size = arena->bitmap_size;
127 Word* bitmap = page->bitmap;
128 for (unsigned i = 0; i < bitmap_size; i++, bitmap++) {
129 Word w = ~*bitmap;
130 if (w) {
131 // found, do allocate
132 unsigned block_size = arena->block_size;
133 unsigned header_size = align_unsigned(sizeof(FsbaPageHeader) + sizeof(Word) * bitmap_size, block_size);
134 unsigned bit_index = stdc_trailing_zeros(w);
135 *bitmap |= ((Word) 1) << bit_index;
136
137 // decrement free blocks counter
138 page->num_free--;
139 if (page->num_free == 0) {
140 // the page is full, move it from avail_pages to full_pages
141 delete_from_list(&arena->avail_pages, page);
142 add_to_list(&arena->full_pages, page);
143 }
144 return ((uint8_t*) page) + header_size + (i * WORD_WIDTH + bit_index) * block_size;
145 }
146 }
147 fputs("FSB arena: bad bitmap\n", stderr);
148 abort();
149}
150
151void fsb_arena_release(void** block_ptr)
152{
153 void* block = *block_ptr;
154 if (!block) {
155 return;
156 }
157 *block_ptr = nullptr;
158
159 // get page from block address
160 FsbaPageHeader* page = (FsbaPageHeader*)( ((ptrdiff_t) block) & ~(ptrdiff_t) (sys_page_size() - 1) );
161
162 // calculate bit index in the bitmap
163 FsbArena* arena = page->arena;
164 unsigned offset = ((uint8_t*) block) - ((uint8_t*) page);
165 unsigned block_size = arena->block_size;
166 unsigned header_size = align_unsigned(sizeof(FsbaPageHeader) + sizeof(Word) * arena->bitmap_size, block_size);
167 unsigned index = (offset - header_size) / block_size;
168
169 // clear bit
170 page->bitmap[index / WORD_WIDTH] &= ~(((Word) 1) << (index & (WORD_WIDTH - 1)));
171
172 // increment free blocks counter
173 page->num_free++;
174 if (page->num_free == arena->blocks_per_page) {
175 // entire page is free now
176 FsbaPageHeader* list = arena->avail_pages;
177 if (list->next != list->prev) {
178 // not the last page, reclaim it back to the operating system
179 delete_from_list(&arena->avail_pages, page);
180 free_page(page);
181 }
182 } else if (page->num_free == 1) {
183 // the page was full, move it from full_pages to avail_pages
184 delete_from_list(&arena->full_pages, page);
185 add_to_list(&arena->avail_pages, page);
186 }
187}
188
189void fsb_arena_walk(FsbArena* arena, FsbArenaWalkCb callback, void* cb_data)
190{
191 if (arena->avail_pages == nullptr) {
192 return;
193 }
194 unsigned bitmap_size = arena->bitmap_size;
195 unsigned block_size = arena->block_size;
196 unsigned header_size = align_unsigned(sizeof(FsbaPageHeader) + sizeof(Word) * bitmap_size, block_size);
197 FsbaPageHeader* first_page = arena->avail_pages;
198 FsbaPageHeader* page = first_page;
199 do {
200 FsbaPageHeader* next_page = page->next; // get next page in advance because the block can be released from callback
201 Word* bitmap = page->bitmap;
202 uint8_t* block_ptr = ((uint8_t*) page) + header_size;
203 for (unsigned i = 0; i < bitmap_size; i++) {
204 Word w = *bitmap++;
205 Word mask = 1;
206 for (unsigned j = 0; j < WORD_WIDTH; j++, mask <<= 1) {
207 unsigned num_free = page->num_free;
208 if (w & mask) {
209 callback(arena, cb_data, (void*) block_ptr);
210 if (num_free >= arena->blocks_per_page - 1) {
211 // it was the last block on the page
212 goto page_done;
213 }
214 }
215 block_ptr += block_size;
216 }
217 }
218page_done:
219 page = next_page;
220 } while (page != first_page);
221}
222
223static void dump_page(FsbaPageHeader* page)
224{
225 fprintf(stderr, "Page %p: %u free blocks\n", (void*) page, page->num_free);
226 dump_bitmap(stderr, (uint8_t*)(page->bitmap), page->arena->bitmap_size * sizeof(Word));
227}
228
229void dump_fsb_arena(FsbArena* arena)
230{
231 fprintf(stderr, "\nFSB arena: block_size=%u, blocks_per_page=%u, bitmap_size=%u, word_size=%zu\nAvailable pages:",
232 arena->block_size, arena->blocks_per_page, arena->bitmap_size, sizeof(Word));
233 if (arena->avail_pages == nullptr) {
234 fputs(" none\n", stderr);
235 } else {
236 fputc('\n', stderr);
237 FsbaPageHeader* first_page = arena->avail_pages;
238 FsbaPageHeader* page = first_page;
239 do {
240 dump_page(page);
241 page = page->next;
242 } while (page != first_page);
243 }
244 fputs("Full pages:", stderr);
245 if (arena->full_pages == nullptr) {
246 fputs(" none\n", stderr);
247 } else {
248 fputc('\n', stderr);
249 FsbaPageHeader* first_page = arena->full_pages;
250 FsbaPageHeader* page = first_page;
251 do {
252 dump_page(page);
253 page = page->next;
254 } while (page != first_page);
255 }
256 fputc('\n', stderr);
257}