GCC Code Coverage Report

Directory: ../src/
File: /home/joels/Current/lispbm/src/lbm_memory.c
Date: 2025-10-27 19:12:55
Exec Total Coverage
Lines: 227 248 91.5%
Functions: 18 21 85.7%
Branches: 97 131 74.0%
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 lbm_mutex_t lbm_mem_mutex;
51 static bool lbm_mem_mutex_initialized;
52 static lbm_uint alloc_offset = 0;
53
54 44426 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 22390 times.
✓ Branch 1 taken 22036 times.
 44426 if (!lbm_mem_mutex_initialized) {
58 22390 lbm_mutex_init(&lbm_mem_mutex);
59 22390 lbm_mem_mutex_initialized = true;
60 }
61
62 44426 alloc_offset = 0;
63
64 44426 lbm_mutex_lock(&lbm_mem_mutex);
65 44426 bool res = false;
66
2/4
✓ Branch 0 taken 44426 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 44426 times.
✗ Branch 3 not taken.
 44426 if (data && bits) {
67
68
1/2
✓ Branch 0 taken 44426 times.
✗ Branch 1 not taken.
 44426 if (((lbm_uint)data % sizeof(lbm_uint) != 0) ||
69
1/2
✓ Branch 0 taken 44426 times.
✗ Branch 1 not taken.
 44426 (data_size * 2) != (bits_size * sizeof(lbm_uint) * 8) ||
70
1/2
✓ Branch 0 taken 44426 times.
✗ Branch 1 not taken.
 44426 data_size % 4 != 0 ||
71
2/4
✓ Branch 0 taken 44426 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 44426 times.
✗ Branch 3 not taken.
 44426 ((lbm_uint)bits % sizeof(lbm_uint) != 0) ||
72 44426 bits_size < 1 ||
73
1/2
✓ Branch 0 taken 44426 times.
✗ Branch 1 not taken.
 44426 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 44426 bitmap = bits;
80 44426 bitmap_size = bits_size;
81
82
2/2
✓ Branch 0 taken 12393632 times.
✓ Branch 1 taken 44426 times.
 12438058 for (lbm_uint i = 0; i < bitmap_size; i ++) {
83 12393632 bitmap[i] = 0;
84 }
85
86 44426 memory = data;
87 44426 memory_base_address = (lbm_uint)data;
88 44426 memory_size = data_size;
89 44426 memory_min_free = data_size;
90 44426 memory_num_free = data_size;
91 44426 memory_reserve_level = (lbm_uint)(0.1 * (lbm_float)data_size);
92 44426 res = true;
93 }
94 }
95 44426 lbm_mutex_unlock(&lbm_mem_mutex);
96 44426 return res;
97 }
98
99 ✗ void lbm_memory_set_reserve(lbm_uint num_words) {
100 ✗ memory_reserve_level = num_words;
101 ✗ }
102
103 ✗ lbm_uint lbm_memory_get_reserve(void) {
104 ✗ return memory_reserve_level;
105 }
106
107 10306618 static inline lbm_uint address_to_bitmap_ix(lbm_uint *ptr) {
108 #ifndef LBM64
109 10306618 return ((lbm_uint)ptr - memory_base_address) >> 2;
110 #else
111 return ((lbm_uint)ptr - memory_base_address) >> 3;
112 #endif
113 }
114
115 23564 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 23564 return (lbm_int)address_to_bitmap_ix(ptr);
120 }
121
122
123 10451581 static inline lbm_uint *bitmap_ix_to_address(lbm_uint ix) {
124 10451581 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 331808015 static inline lbm_uint status(lbm_uint i) {
138
139 331808015 lbm_uint ix = i << 1; // * 2
140 331808015 lbm_uint word_ix = ix >> WORD_IX_SHIFT; // / 32
141 331808015 lbm_uint bit_ix = ix & WORD_MOD_MASK; // % 32
142
143 331808015 lbm_uint mask = ((lbm_uint)3) << bit_ix; // 000110..0
144 331808015 return (bitmap[word_ix] & mask) >> bit_ix;
145 }
146
147 41306762 static inline void set_status(lbm_uint i, lbm_uint status) {
148 41306762 lbm_uint ix = i << 1; // * 2
149 41306762 lbm_uint word_ix = ix >> WORD_IX_SHIFT; // / 32
150 41306762 lbm_uint bit_ix = ix & WORD_MOD_MASK; // % 32
151
152 41306762 lbm_uint clr_mask = ~(((lbm_uint)3) << bit_ix);
153 41306762 lbm_uint mask = status << bit_ix;
154
155 41306762 bitmap[word_ix] &= clr_mask;
156 41306762 bitmap[word_ix] |= mask;
157 41306762 }
158
159 28 lbm_uint lbm_memory_num_words(void) {
160 28 return memory_size;
161 }
162
163 45137 lbm_uint lbm_memory_num_free(void) {
164 45137 return memory_num_free;
165 }
166
167 ✗ lbm_uint lbm_memory_maximum_used(void) {
168 ✗ return (memory_size - memory_min_free);
169 }
170
171 594687 void lbm_memory_update_min_free(void) {
172
2/2
✓ Branch 0 taken 3222 times.
✓ Branch 1 taken 591465 times.
 594687 if (memory_num_free < memory_min_free)
173 3222 memory_min_free = memory_num_free;
174 594687 }
175
176 4207 lbm_uint lbm_memory_longest_free(void) {
177
2/4
✓ Branch 0 taken 4207 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 4207 times.
 4207 if (memory == NULL || bitmap == NULL) {
178 ✗ return 0;
179 }
180 4207 lbm_mutex_lock(&lbm_mem_mutex);
181 4207 unsigned int state = INIT;
182 4207 lbm_uint max_length = 0;
183
184 4207 lbm_uint curr_length = 0;
185
2/2
✓ Branch 0 taken 17067520 times.
✓ Branch 1 taken 4207 times.
 17071727 for (unsigned int i = 0; i < memory_size; i ++) {
186
187 // The status field is 2 bits and this 4 cases is exhaustive!
188
4/4
✓ Branch 0 taken 16938742 times.
✓ Branch 1 taken 62201 times.
✓ Branch 2 taken 62201 times.
✓ Branch 3 taken 4376 times.
 17067520 switch(status(i)) {
189
3/4
✓ Branch 0 taken 4955 times.
✓ Branch 1 taken 13024066 times.
✓ Branch 2 taken 3909721 times.
✗ Branch 3 not taken.
 16938742 case FREE_OR_USED:
190 switch (state) {
191 4955 case INIT:
192 4955 curr_length = 1;
193
2/2
✓ Branch 0 taken 4207 times.
✓ Branch 1 taken 748 times.
 4955 if (curr_length > max_length) max_length = curr_length;
194 4955 state = FREE_LENGTH_CHECK;
195 4955 break;
196 13024066 case FREE_LENGTH_CHECK:
197 13024066 curr_length ++;
198
2/2
✓ Branch 0 taken 12984229 times.
✓ Branch 1 taken 39837 times.
 13024066 if (curr_length > max_length) max_length = curr_length;
199 13024066 state = FREE_LENGTH_CHECK;
200 13024066 break;
201 3909721 case SKIP:
202 3909721 break;
203 }
204 16938742 break;
205 62201 case END:
206 62201 state = INIT;
207 62201 break;
208 62201 case START:
209 62201 state = SKIP;
210 62201 break;
211 4376 default: // START_END
212 4376 state = INIT;
213 4376 break;
214 }
215 }
216 4207 lbm_mutex_unlock(&lbm_mem_mutex);
217
2/2
✓ Branch 0 taken 4205 times.
✓ Branch 1 taken 2 times.
 4207 if (memory_num_free - max_length < memory_reserve_level) {
218 4205 lbm_uint n = memory_reserve_level - (memory_num_free - max_length);
219
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4205 times.
 4205 if (n >= max_length) {
220 ✗ max_length = 0;
221 } else {
222 4205 max_length -= n;
223 }
224 }
225 4207 return max_length;
226 }
227
228 10457239 static lbm_uint *lbm_memory_allocate_internal(lbm_uint num_words) {
229
230
2/4
✓ Branch 0 taken 10457239 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 10457239 times.
 10457239 if (memory == NULL || bitmap == NULL) {
231 ✗ return NULL;
232 }
233
234 10457239 lbm_mutex_lock(&lbm_mem_mutex);
235
236 10457239 lbm_uint start_ix = 0;
237 10457239 lbm_uint end_ix = 0;
238 10457239 lbm_uint free_length = 0;
239 10457239 unsigned int state = INIT;
240
241
2/2
✓ Branch 0 taken 106804802 times.
✓ Branch 1 taken 5658 times.
 106810460 for (lbm_uint i = 0; i < memory_size; i ++) {
242
4/4
✓ Branch 0 taken 96276167 times.
✓ Branch 1 taken 10367262 times.
✓ Branch 2 taken 75495 times.
✓ Branch 3 taken 85878 times.
 106804802 switch(status(alloc_offset)) {
243
3/4
✓ Branch 0 taken 10461741 times.
✓ Branch 1 taken 66691890 times.
✓ Branch 2 taken 19122536 times.
✗ Branch 3 not taken.
 96276167 case FREE_OR_USED:
244 switch (state) {
245 10461741 case INIT:
246 10461741 start_ix = alloc_offset;
247
2/2
✓ Branch 0 taken 84720 times.
✓ Branch 1 taken 10377021 times.
 10461741 if (num_words == 1) {
248 84720 end_ix = alloc_offset;
249 84720 state = ALLOC_DONE;
250 } else {
251 10377021 state = FREE_LENGTH_CHECK;
252 10377021 free_length = 1;
253 }
254 10461741 break;
255 66691890 case FREE_LENGTH_CHECK:
256 66691890 free_length ++;
257
2/2
✓ Branch 0 taken 10366861 times.
✓ Branch 1 taken 56325029 times.
 66691890 if (free_length == num_words) {
258 10366861 end_ix = alloc_offset;
259 10366861 state = ALLOC_DONE;
260 } else {
261 56325029 state = FREE_LENGTH_CHECK;
262 }
263 66691890 break;
264 19122536 case SKIP:
265 19122536 break;
266 }
267 96276167 break;
268 10367262 case END:
269 10367262 state = INIT;
270 10367262 break;
271 75495 case START:
272 75495 state = SKIP;
273 75495 break;
274 85878 default: // START_END
275 85878 state = INIT;
276 85878 break;
277 }
278
279
2/2
✓ Branch 0 taken 10451581 times.
✓ Branch 1 taken 96353221 times.
 106804802 if (state == ALLOC_DONE) break;
280
281 96353221 alloc_offset++;
282
2/2
✓ Branch 0 taken 5666 times.
✓ Branch 1 taken 96347555 times.
 96353221 if (alloc_offset == memory_size ) {
283 5666 free_length = 0;
284 5666 alloc_offset = 0;
285 5666 state = INIT;
286 }
287 }
288
289
2/2
✓ Branch 0 taken 10451581 times.
✓ Branch 1 taken 5658 times.
 10457239 if (state == ALLOC_DONE) {
290
2/2
✓ Branch 0 taken 84720 times.
✓ Branch 1 taken 10366861 times.
 10451581 if (start_ix == end_ix) {
291 84720 set_status(start_ix, START_END);
292 } else {
293 10366861 set_status(start_ix, START);
294 10366861 set_status(end_ix, END);
295 }
296 10451581 memory_num_free -= num_words;
297 10451581 lbm_mutex_unlock(&lbm_mem_mutex);
298 10451581 return bitmap_ix_to_address(start_ix);
299 }
300 5658 lbm_mutex_unlock(&lbm_mem_mutex);
301 5658 return NULL;
302 }
303
304 47581 lbm_uint *lbm_memory_allocate(lbm_uint num_words) {
305
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 47581 times.
 47581 if (memory_num_free - num_words < memory_reserve_level) {
306 ✗ lbm_request_gc();
307 ✗ return NULL;
308 }
309 47581 return lbm_memory_allocate_internal(num_words);
310 }
311
312 10322287 int lbm_memory_free(lbm_uint *ptr) {
313 10322287 int r = 0;
314
2/2
✓ Branch 0 taken 10273031 times.
✓ Branch 1 taken 49256 times.
 10322287 if (lbm_memory_ptr_inside(ptr)) {
315 10273031 lbm_mutex_lock(&lbm_mem_mutex);
316 10273031 lbm_uint ix = address_to_bitmap_ix(ptr);
317 10273031 lbm_uint count_freed = 0;
318 10273031 alloc_offset = ix;
319
2/3
✓ Branch 0 taken 10195243 times.
✓ Branch 1 taken 77788 times.
✗ Branch 2 not taken.
 10273031 switch(status(ix)) {
320 10195243 case START:
321 10195243 set_status(ix, FREE_OR_USED);
322
1/2
✓ Branch 0 taken 51426836 times.
✗ Branch 1 not taken.
 51426836 for (lbm_uint i = ix; i < memory_size; i ++) {
323 51426836 count_freed ++;
324
2/2
✓ Branch 0 taken 10195243 times.
✓ Branch 1 taken 41231593 times.
 51426836 if (status(i) == END) {
325 10195243 set_status(i, FREE_OR_USED);
326 10195243 r = 1;
327 10195243 break;
328 }
329 }
330 10195243 break;
331 77788 case START_END:
332 77788 set_status(ix, FREE_OR_USED);
333 77788 count_freed = 1;
334 77788 r = 1;
335 77788 break;
336 ✗ default:
337 ✗ break;
338 }
339
1/2
✓ Branch 0 taken 10273031 times.
✗ Branch 1 not taken.
 10273031 if (r) {
340
4/4
✓ Branch 0 taken 136531831 times.
✓ Branch 1 taken 84 times.
✓ Branch 2 taken 126258884 times.
✓ Branch 3 taken 10272947 times.
 136531915 while (alloc_offset > 0 && status(alloc_offset - 1) == FREE_OR_USED) {
341 126258884 alloc_offset--;
342 }
343 }
344 10273031 memory_num_free += count_freed;
345 10273031 lbm_mutex_unlock(&lbm_mem_mutex);
346 }
347 10322287 return r;
348 }
349 //Malloc/free like interface
350 10366045 void* lbm_malloc(size_t size) {
351
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10366045 times.
 10366045 if (size == 0) return NULL;
352 lbm_uint alloc_size;
353
354 10366045 alloc_size = size / sizeof(lbm_uint);
355
2/2
✓ Branch 0 taken 204756 times.
✓ Branch 1 taken 10161289 times.
 10366045 if (size % sizeof(lbm_uint)) alloc_size += 1;
356
357
2/2
✓ Branch 0 taken 5798 times.
✓ Branch 1 taken 10360247 times.
 10366045 if (memory_num_free - alloc_size < memory_reserve_level) {
358 5798 lbm_request_gc();
359 5798 return NULL;
360 }
361 10360247 return lbm_memory_allocate_internal(alloc_size);
362 }
363
364 49411 void* lbm_malloc_reserve(size_t size) {
365
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 49411 times.
 49411 if (size == 0) return NULL;
366 lbm_uint alloc_size;
367
368 49411 alloc_size = size / sizeof(lbm_uint);
369
2/2
✓ Branch 0 taken 40235 times.
✓ Branch 1 taken 9176 times.
 49411 if (size % sizeof(lbm_uint)) alloc_size += 1;
370
371
2/2
✓ Branch 0 taken 141 times.
✓ Branch 1 taken 49270 times.
 49411 if (memory_num_free - alloc_size < memory_reserve_level) {
372 141 lbm_request_gc();
373 }
374 49411 return lbm_memory_allocate_internal(alloc_size);
375 }
376
377 40375 void lbm_free(void *ptr) {
378 40375 lbm_memory_free(ptr);
379 40375 }
380
381 10023 int lbm_memory_shrink(lbm_uint *ptr, lbm_uint n) {
382
2/4
✓ Branch 0 taken 10023 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 10023 times.
 10023 if (!lbm_memory_ptr_inside(ptr) || n == 0) return 0;
383
384 10023 lbm_uint ix = address_to_bitmap_ix(ptr);
385
386 10023 lbm_mutex_lock(&lbm_mem_mutex);
387
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10023 times.
 10023 if (status(ix) == START_END) {
388 ✗ lbm_mutex_unlock(&lbm_mem_mutex);
389 ✗ return 1; // A one word arrays always succeeds at remaining at 1 word
390 }
391
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10023 times.
 10023 if (status(ix) != START) {
392 ✗ lbm_mutex_unlock(&lbm_mem_mutex);
393 ✗ return 0; // ptr does not point to the start of an allocated range.
394 }
395
396 10023 bool done = false;
397 10023 unsigned int i = 0;
398
399
1/2
✓ Branch 0 taken 115821 times.
✗ Branch 1 not taken.
 115821 for (i = 0; i < (memory_size - ix); i ++) {
400
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 115821 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 115821 if (status(ix+i) == END && i < n) {
401 ✗ lbm_mutex_unlock(&lbm_mem_mutex);
402 ✗ return 0; // cannot shrink allocation to a larger size
403 }
404
405
2/2
✓ Branch 0 taken 10023 times.
✓ Branch 1 taken 105798 times.
 115821 if (i == (n-1)) {
406
2/4
✓ Branch 0 taken 10023 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 10023 times.
 20046 if (status(ix+i) == END ||
407 10023 status(ix+i) == START_END) {
408 ✗ done = true;
409 }
410
2/2
✓ Branch 0 taken 1311 times.
✓ Branch 1 taken 8712 times.
 10023 if (i == 0) {
411 1311 set_status(ix+i, START_END);
412 }
413 else {
414 8712 set_status(ix+i, END);
415 }
416 10023 break;
417 }
418 }
419 10023 alloc_offset = ix+i;
420
421 10023 lbm_uint count = 0;
422
1/2
✓ Branch 0 taken 10023 times.
✗ Branch 1 not taken.
 10023 if (!done) {
423 10023 i++; // move to next position, prev position should be END or START_END
424
1/2
✓ Branch 0 taken 9548082 times.
✗ Branch 1 not taken.
 9548082 for (;i < (memory_size - ix); i ++) {
425 9548082 count ++;
426
2/2
✓ Branch 0 taken 10023 times.
✓ Branch 1 taken 9538059 times.
 9548082 if (status(ix+i) == END) {
427 10023 set_status(ix+i, FREE_OR_USED);
428 10023 break;
429 }
430 }
431 }
432
433 10023 memory_num_free += count;
434 10023 lbm_mutex_unlock(&lbm_mem_mutex);
435 10023 return 1;
436 }
437
438 10343990 int lbm_memory_ptr_inside(lbm_uint *ptr) {
439
2/2
✓ Branch 0 taken 10283054 times.
✓ Branch 1 taken 60936 times.
 20627044 return ((lbm_uint)ptr >= (lbm_uint)memory &&
440
1/2
✓ Branch 0 taken 10283054 times.
✗ Branch 1 not taken.
 10283054 (lbm_uint)ptr < (lbm_uint)memory + (memory_size * sizeof(lbm_uint)));
441 }
442