GCC Code Coverage Report

Directory: ../src/
File: /home/joels/Current/lispbm/src/lbm_memory.c
Date: 2025-08-08 18:10:24
Exec Total Coverage
Lines: 248 252 98.4%
Functions: 21 21 100.0%
Branches: 113 131 86.3%
Line Branch Exec Source
1 /*
2 Copyright 2020 - 2025 Joel Svensson svenssonjoel@yahoo.se
3 2024 Benjamin Vedder
4
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, either version 3 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #include <stdint.h>
20 #include <stdlib.h>
21 #include <stdio.h>
22
23 #include "lbm_memory.h"
24 #include "platform_mutex.h"
25
26 // pull in from eval_cps
27 void lbm_request_gc(void);
28
29 /* Status bit patterns */
30 #define FREE_OR_USED 0 //00b
31 #define END 1 //01b
32 #define START 2 //10b
33 #define START_END 3 //11b
34
35 /* States in memory_allocate state-machine*/
36 #define INIT 0
37 #define FREE_LENGTH_CHECK 1
38 #define SKIP 2
39 #define ALLOC_DONE 0xF00DF00D
40 #define ALLOC_FAILED 0xDEADBEAF
41
42 static lbm_uint *bitmap = NULL;
43 static lbm_uint *memory = NULL;
44 static lbm_uint memory_size; // in 4 or 8 byte words depending on 32 or 64 bit platform
45 static lbm_uint bitmap_size; // in 4 or 8 byte words
46 static lbm_uint memory_base_address = 0;
47 static lbm_uint memory_num_free = 0;
48 static lbm_uint memory_min_free = 0;
49 static volatile lbm_uint memory_reserve_level = 0;
50 static mutex_t lbm_mem_mutex;
51 static bool lbm_mem_mutex_initialized;
52 static lbm_uint alloc_offset = 0;
53
54 88493 bool lbm_memory_init(lbm_uint *data, lbm_uint data_size,
55 lbm_uint *bits, lbm_uint bits_size) {
56
57
2/2
✓ Branch 0 taken 44304 times.
✓ Branch 1 taken 44189 times.
 88493 if (!lbm_mem_mutex_initialized) {
58 44304 mutex_init(&lbm_mem_mutex);
59 44304 lbm_mem_mutex_initialized = true;
60 }
61
62 88493 alloc_offset = 0;
63
64 88493 mutex_lock(&lbm_mem_mutex);
65 88493 bool res = false;
66
4/4
✓ Branch 0 taken 88488 times.
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 88485 times.
✓ Branch 3 taken 3 times.
 88493 if (data && bits) {
67
68
1/2
✓ Branch 0 taken 88485 times.
✗ Branch 1 not taken.
 88485 if (((lbm_uint)data % sizeof(lbm_uint) != 0) ||
69
2/2
✓ Branch 0 taken 88480 times.
✓ Branch 1 taken 5 times.
 88485 (data_size * 2) != (bits_size * sizeof(lbm_uint) * 8) ||
70
1/2
✓ Branch 0 taken 88480 times.
✗ Branch 1 not taken.
 88480 data_size % 4 != 0 ||
71
2/4
✓ Branch 0 taken 88480 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 88480 times.
✗ Branch 3 not taken.
 88480 ((lbm_uint)bits % sizeof(lbm_uint) != 0) ||
72 88480 bits_size < 1 ||
73
1/2
✓ Branch 0 taken 88480 times.
✗ Branch 1 not taken.
 88480 bits_size % 4 != 0) {
74 // data is not aligned to sizeof lbm_uint
75 // size is too small
76 // or size is not a multiple of 4
77 } else {
78
79 88480 bitmap = bits;
80 88480 bitmap_size = bits_size;
81
82
2/2
✓ Branch 0 taken 195710172 times.
✓ Branch 1 taken 88480 times.
 195798652 for (lbm_uint i = 0; i < bitmap_size; i ++) {
83 195710172 bitmap[i] = 0;
84 }
85
86 88480 memory = data;
87 88480 memory_base_address = (lbm_uint)data;
88 88480 memory_size = data_size;
89 88480 memory_min_free = data_size;
90 88480 memory_num_free = data_size;
91 88480 memory_reserve_level = (lbm_uint)(0.1 * (lbm_float)data_size);
92 88480 res = true;
93 }
94 }
95 88493 mutex_unlock(&lbm_mem_mutex);
96 88493 return res;
97 }
98
99 7 void lbm_memory_set_reserve(lbm_uint num_words) {
100 7 memory_reserve_level = num_words;
101 7 }
102
103 3 lbm_uint lbm_memory_get_reserve(void) {
104 3 return memory_reserve_level;
105 }
106
107 12148513 static inline lbm_uint address_to_bitmap_ix(lbm_uint *ptr) {
108 #ifndef LBM64
109 10279885 return ((lbm_uint)ptr - memory_base_address) >> 2;
110 #else
111 1868628 return ((lbm_uint)ptr - memory_base_address) >> 3;
112 #endif
113 }
114
115 46520 lbm_int lbm_memory_address_to_ix(lbm_uint *ptr) {
116 /* TODO: assuming that index
117 will have more then enough room in the
118 positive half of a 28bit integer */
119 46520 return (lbm_int)address_to_bitmap_ix(ptr);
120 }
121
122
123 12415879 static inline lbm_uint *bitmap_ix_to_address(lbm_uint ix) {
124 12415879 return &((lbm_uint*)(memory_base_address))[ix];// + (ix << 2));
125 }
126
127 #ifndef LBM64
128 #define WORD_IX_SHIFT 5
129 #define WORD_MOD_MASK 0x1F
130 #define BITMAP_SIZE_SHIFT 4 // 16 statuses per bitmap word
131 #else
132 #define WORD_IX_SHIFT 6 // divide by 64
133 #define WORD_MOD_MASK 0x3F // mod 64
134 #define BITMAP_SIZE_SHIFT 5 // times 32, 32 statuses per bitmap word
135 #endif
136
137 490971805 static inline lbm_uint status(lbm_uint i) {
138
139 490971805 lbm_uint ix = i << 1; // * 2
140 490971805 lbm_uint word_ix = ix >> WORD_IX_SHIFT; // / 32
141 490971805 lbm_uint bit_ix = ix & WORD_MOD_MASK; // % 32
142
143 490971805 lbm_uint mask = ((lbm_uint)3) << bit_ix; // 000110..0
144
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 490971805 times.
 490971805 if (word_ix > bitmap_size) {
145 ✗ return (lbm_uint)NULL;
146 }
147 490971805 return (bitmap[word_ix] & mask) >> bit_ix;
148 }
149
150 48608568 static inline void set_status(lbm_uint i, lbm_uint status) {
151 48608568 lbm_uint ix = i << 1; // * 2
152 48608568 lbm_uint word_ix = ix >> WORD_IX_SHIFT; // / 32
153 48608568 lbm_uint bit_ix = ix & WORD_MOD_MASK; // % 32
154
155 48608568 lbm_uint clr_mask = ~(((lbm_uint)3) << bit_ix);
156 48608568 lbm_uint mask = status << bit_ix;
157
158 48608568 bitmap[word_ix] &= clr_mask;
159 48608568 bitmap[word_ix] |= mask;
160 48608568 }
161
162 57 lbm_uint lbm_memory_num_words(void) {
163 57 return memory_size;
164 }
165
166 90296 lbm_uint lbm_memory_num_free(void) {
167 90296 return memory_num_free;
168 }
169
170 4 lbm_uint lbm_memory_maximum_used(void) {
171 4 return (memory_size - memory_min_free);
172 }
173
174 1012970 void lbm_memory_update_min_free(void) {
175
2/2
✓ Branch 0 taken 6409 times.
✓ Branch 1 taken 1006561 times.
 1012970 if (memory_num_free < memory_min_free)
176 6409 memory_min_free = memory_num_free;
177 1012970 }
178
179 8288 lbm_uint lbm_memory_longest_free(void) {
180
3/4
✓ Branch 0 taken 8287 times.
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 8287 times.
 8288 if (memory == NULL || bitmap == NULL) {
181 1 return 0;
182 }
183 8287 mutex_lock(&lbm_mem_mutex);
184 8287 unsigned int state = INIT;
185 8287 lbm_uint max_length = 0;
186
187 8287 lbm_uint curr_length = 0;
188
2/2
✓ Branch 0 taken 33792256 times.
✓ Branch 1 taken 8287 times.
 33800543 for (unsigned int i = 0; i < (bitmap_size << BITMAP_SIZE_SHIFT); i ++) {
189
190 // The status field is 2 bits and this 4 cases is exhaustive!
191
4/4
✓ Branch 0 taken 33539976 times.
✓ Branch 1 taken 121351 times.
✓ Branch 2 taken 121351 times.
✓ Branch 3 taken 9578 times.
 33792256 switch(status(i)) {
192 33539976 case FREE_OR_USED:
193
3/4
✓ Branch 0 taken 9789 times.
✓ Branch 1 taken 26263044 times.
✓ Branch 2 taken 7267143 times.
✗ Branch 3 not taken.
 33539976 switch (state) {
194 9789 case INIT:
195 9789 curr_length = 1;
196
2/2
✓ Branch 0 taken 8287 times.
✓ Branch 1 taken 1502 times.
 9789 if (curr_length > max_length) max_length = curr_length;
197 9789 state = FREE_LENGTH_CHECK;
198 9789 break;
199 26263044 case FREE_LENGTH_CHECK:
200 26263044 curr_length ++;
201
2/2
✓ Branch 0 taken 26207722 times.
✓ Branch 1 taken 55322 times.
 26263044 if (curr_length > max_length) max_length = curr_length;
202 26263044 state = FREE_LENGTH_CHECK;
203 26263044 break;
204 7267143 case SKIP:
205 7267143 break;
206 }
207 33539976 break;
208 121351 case END:
209 121351 state = INIT;
210 121351 break;
211 121351 case START:
212 121351 state = SKIP;
213 121351 break;
214 9578 default: // START_END
215 9578 state = INIT;
216 9578 break;
217 }
218 }
219 8287 mutex_unlock(&lbm_mem_mutex);
220
2/2
✓ Branch 0 taken 8285 times.
✓ Branch 1 taken 2 times.
 8287 if (memory_num_free - max_length < memory_reserve_level) {
221 8285 lbm_uint n = memory_reserve_level - (memory_num_free - max_length);
222 8285 max_length -= n;
223 }
224 8287 return max_length;
225 }
226
227 12424397 static lbm_uint *lbm_memory_allocate_internal(lbm_uint num_words) {
228
229
3/4
✓ Branch 0 taken 12424396 times.
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 12424396 times.
 12424397 if (memory == NULL || bitmap == NULL) {
230 1 return NULL;
231 }
232
233 12424396 mutex_lock(&lbm_mem_mutex);
234
235 12424396 lbm_uint start_ix = 0;
236 12424396 lbm_uint end_ix = 0;
237 12424396 lbm_uint free_length = 0;
238 12424396 unsigned int state = INIT;
239 12424396 lbm_uint loop_max = (bitmap_size << BITMAP_SIZE_SHIFT);
240
241
2/2
✓ Branch 0 taken 165246318 times.
✓ Branch 1 taken 8517 times.
 165254835 for (lbm_uint i = 0; i < loop_max; i ++) {
242
4/4
✓ Branch 0 taken 152699162 times.
✓ Branch 1 taken 12195526 times.
✓ Branch 2 taken 122594 times.
✓ Branch 3 taken 229036 times.
 165246318 switch(status(alloc_offset)) {
243 152699162 case FREE_OR_USED:
244
3/4
✓ Branch 0 taken 12431704 times.
✓ Branch 1 taken 111708337 times.
✓ Branch 2 taken 28559121 times.
✗ Branch 3 not taken.
 152699162 switch (state) {
245 12431704 case INIT:
246 12431704 start_ix = alloc_offset;
247
2/2
✓ Branch 0 taken 223838 times.
✓ Branch 1 taken 12207866 times.
 12431704 if (num_words == 1) {
248 223838 end_ix = alloc_offset;
249 223838 state = ALLOC_DONE;
250 } else {
251 12207866 state = FREE_LENGTH_CHECK;
252 12207866 free_length = 1;
253 }
254 12431704 break;
255 111708337 case FREE_LENGTH_CHECK:
256 111708337 free_length ++;
257
2/2
✓ Branch 0 taken 12192041 times.
✓ Branch 1 taken 99516296 times.
 111708337 if (free_length == num_words) {
258 12192041 end_ix = alloc_offset;
259 12192041 state = ALLOC_DONE;
260 } else {
261 99516296 state = FREE_LENGTH_CHECK;
262 }
263 111708337 break;
264 28559121 case SKIP:
265 28559121 break;
266 }
267 152699162 break;
268 12195526 case END:
269 12195526 state = INIT;
270 12195526 break;
271 122594 case START:
272 122594 state = SKIP;
273 122594 break;
274 229036 default: // START_END
275 229036 state = INIT;
276 229036 break;
277 }
278
279
2/2
✓ Branch 0 taken 12415879 times.
✓ Branch 1 taken 152830439 times.
 165246318 if (state == ALLOC_DONE) break;
280
281 152830439 alloc_offset++;
282
2/2
✓ Branch 0 taken 8527 times.
✓ Branch 1 taken 152821912 times.
 152830439 if (alloc_offset == loop_max ) {
283 8527 free_length = 0;
284 8527 alloc_offset = 0;
285 8527 state = INIT;
286 }
287 }
288
289
2/2
✓ Branch 0 taken 12415879 times.
✓ Branch 1 taken 8517 times.
 12424396 if (state == ALLOC_DONE) {
290
2/2
✓ Branch 0 taken 223838 times.
✓ Branch 1 taken 12192041 times.
 12415879 if (start_ix == end_ix) {
291 223838 set_status(start_ix, START_END);
292 } else {
293 12192041 set_status(start_ix, START);
294 12192041 set_status(end_ix, END);
295 }
296 12415879 memory_num_free -= num_words;
297 12415879 mutex_unlock(&lbm_mem_mutex);
298 12415879 return bitmap_ix_to_address(start_ix);
299 }
300 8517 mutex_unlock(&lbm_mem_mutex);
301 8517 return NULL;
302 }
303
304 94768 lbm_uint *lbm_memory_allocate(lbm_uint num_words) {
305
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 94767 times.
 94768 if (memory_num_free - num_words < memory_reserve_level) {
306 1 lbm_request_gc();
307 1 return NULL;
308 }
309 94767 return lbm_memory_allocate_internal(num_words);
310 }
311
312 12176460 int lbm_memory_free(lbm_uint *ptr) {
313 12176460 int r = 0;
314
2/2
✓ Branch 0 taken 12078974 times.
✓ Branch 1 taken 97486 times.
 12176460 if (lbm_memory_ptr_inside(ptr)) {
315 12078974 mutex_lock(&lbm_mem_mutex);
316 12078974 lbm_uint ix = address_to_bitmap_ix(ptr);
317 12078974 lbm_uint count_freed = 0;
318 12078974 alloc_offset = ix;
319
3/3
✓ Branch 0 taken 11875644 times.
✓ Branch 1 taken 203328 times.
✓ Branch 2 taken 2 times.
 12078974 switch(status(ix)) {
320 11875644 case START:
321 11875644 set_status(ix, FREE_OR_USED);
322
1/2
✓ Branch 0 taken 76031549 times.
✗ Branch 1 not taken.
 76031549 for (lbm_uint i = ix; i < (bitmap_size << BITMAP_SIZE_SHIFT); i ++) {
323 76031549 count_freed ++;
324
2/2
✓ Branch 0 taken 11875644 times.
✓ Branch 1 taken 64155905 times.
 76031549 if (status(i) == END) {
325 11875644 set_status(i, FREE_OR_USED);
326 11875644 r = 1;
327 11875644 break;
328 }
329 }
330 11875644 break;
331 203328 case START_END:
332 203328 set_status(ix, FREE_OR_USED);
333 203328 count_freed = 1;
334 203328 r = 1;
335 203328 break;
336 2 default:
337 2 break;
338 }
339
2/2
✓ Branch 0 taken 12078972 times.
✓ Branch 1 taken 2 times.
 12078974 if (r) {
340
4/4
✓ Branch 0 taken 184185968 times.
✓ Branch 1 taken 1235 times.
✓ Branch 2 taken 172108231 times.
✓ Branch 3 taken 12077737 times.
 184187203 while (alloc_offset > 0 && status(alloc_offset - 1) == FREE_OR_USED) {
341 172108231 alloc_offset--;
342 }
343 }
344 12078974 memory_num_free += count_freed;
345 12078974 mutex_unlock(&lbm_mem_mutex);
346 }
347 12176460 return r;
348 }
349 //Malloc/free like interface
350 12235716 void* lbm_malloc(size_t size) {
351
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 12235715 times.
 12235716 if (size == 0) return NULL;
352 lbm_uint alloc_size;
353
354 12235715 alloc_size = size / sizeof(lbm_uint);
355
2/2
✓ Branch 0 taken 480510 times.
✓ Branch 1 taken 11755205 times.
 12235715 if (size % sizeof(lbm_uint)) alloc_size += 1;
356
357
2/2
✓ Branch 0 taken 7418 times.
✓ Branch 1 taken 12228297 times.
 12235715 if (memory_num_free - alloc_size < memory_reserve_level) {
358 7418 lbm_request_gc();
359 7418 return NULL;
360 }
361 12228297 return lbm_memory_allocate_internal(alloc_size);
362 }
363
364 101334 void* lbm_malloc_reserve(size_t size) {
365
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 101333 times.
 101334 if (size == 0) return NULL;
366 lbm_uint alloc_size;
367
368 101333 alloc_size = size / sizeof(lbm_uint);
369
2/2
✓ Branch 0 taken 83620 times.
✓ Branch 1 taken 17713 times.
 101333 if (size % sizeof(lbm_uint)) alloc_size += 1;
370
371
2/2
✓ Branch 0 taken 186 times.
✓ Branch 1 taken 101147 times.
 101333 if (memory_num_free - alloc_size < memory_reserve_level) {
372 186 lbm_request_gc();
373 }
374 101333 return lbm_memory_allocate_internal(alloc_size);
375 }
376
377 78934 void lbm_free(void *ptr) {
378 78934 lbm_memory_free(ptr);
379 78934 }
380
381 23026 int lbm_memory_shrink(lbm_uint *ptr, lbm_uint n) {
382
4/4
✓ Branch 0 taken 23023 times.
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 23019 times.
 23026 if (!lbm_memory_ptr_inside(ptr) || n == 0) return 0;
383
384 23019 lbm_uint ix = address_to_bitmap_ix(ptr);
385
386 23019 mutex_lock(&lbm_mem_mutex);
387
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 23017 times.
 23019 if (status(ix) == START_END) {
388 2 mutex_unlock(&lbm_mem_mutex);
389 2 return 1; // A one word arrays always succeeds at remaining at 1 word
390 }
391
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 23017 times.
 23017 if (status(ix) != START) {
392 ✗ mutex_unlock(&lbm_mem_mutex);
393 ✗ return 0; // ptr does not point to the start of an allocated range.
394 }
395
396 23017 bool done = false;
397 23017 unsigned int i = 0;
398
399
1/2
✓ Branch 0 taken 186109 times.
✗ Branch 1 not taken.
 186109 for (i = 0; i < ((bitmap_size << BITMAP_SIZE_SHIFT) - ix); i ++) {
400
3/4
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 186108 times.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 186109 if (status(ix+i) == END && i < n) {
401 1 mutex_unlock(&lbm_mem_mutex);
402 1 return 0; // cannot shrink allocation to a larger size
403 }
404
405
2/2
✓ Branch 0 taken 23016 times.
✓ Branch 1 taken 163092 times.
 186108 if (i == (n-1)) {
406
2/4
✓ Branch 0 taken 23016 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 23016 times.
 46032 if (status(ix+i) == END ||
407 23016 status(ix+i) == START_END) {
408 ✗ done = true;
409 }
410
2/2
✓ Branch 0 taken 5188 times.
✓ Branch 1 taken 17828 times.
 23016 if (i == 0) {
411 5188 set_status(ix+i, START_END);
412 }
413 else {
414 17828 set_status(ix+i, END);
415 }
416 23016 break;
417 }
418 }
419 23016 alloc_offset = ix+i;
420
421 23016 lbm_uint count = 0;
422
1/2
✓ Branch 0 taken 23016 times.
✗ Branch 1 not taken.
 23016 if (!done) {
423 23016 i++; // move to next position, prev position should be END or START_END
424
1/2
✓ Branch 0 taken 19358563 times.
✗ Branch 1 not taken.
 19358563 for (;i < ((bitmap_size << BITMAP_SIZE_SHIFT) - ix); i ++) {
425 19358563 count ++;
426
2/2
✓ Branch 0 taken 23016 times.
✓ Branch 1 taken 19335547 times.
 19358563 if (status(ix+i) == END) {
427 23016 set_status(ix+i, FREE_OR_USED);
428 23016 break;
429 }
430 }
431 }
432
433 23016 memory_num_free += count;
434 23016 mutex_unlock(&lbm_mem_mutex);
435 23016 return 1;
436 }
437
438 12204963 int lbm_memory_ptr_inside(lbm_uint *ptr) {
439
2/2
✓ Branch 0 taken 12102017 times.
✓ Branch 1 taken 102946 times.
 24306980 return ((lbm_uint)ptr >= (lbm_uint)memory &&
440
2/2
✓ Branch 0 taken 12102008 times.
✓ Branch 1 taken 9 times.
 12102017 (lbm_uint)ptr < (lbm_uint)memory + (memory_size * sizeof(lbm_uint)));
441 }
442