GCC Code Coverage Report

Directory: ../src/
File: /home/joels/Current/lispbm/src/lbm_memory.c
Date: 2025-10-28 15:15:18
Exec Total Coverage
Lines: 245 249 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 lbm_mutex_t lbm_mem_mutex;
51 static bool lbm_mem_mutex_initialized;
52 static lbm_uint alloc_offset = 0;
53
54 132726 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 66480 times.
✓ Branch 1 taken 66246 times.
 132726 if (!lbm_mem_mutex_initialized) {
58 66480 lbm_mutex_init(&lbm_mem_mutex);
59 66480 lbm_mem_mutex_initialized = true;
60 }
61
62 132726 alloc_offset = 0;
63
64 132726 lbm_mutex_lock(&lbm_mem_mutex);
65 132726 bool res = false;
66
4/4
✓ Branch 0 taken 132721 times.
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 132718 times.
✓ Branch 3 taken 3 times.
 132726 if (data && bits) {
67
68
1/2
✓ Branch 0 taken 132718 times.
✗ Branch 1 not taken.
 132718 if (((lbm_uint)data % sizeof(lbm_uint) != 0) ||
69
2/2
✓ Branch 0 taken 132713 times.
✓ Branch 1 taken 5 times.
 132718 (data_size * 2) != (bits_size * sizeof(lbm_uint) * 8) ||
70
1/2
✓ Branch 0 taken 132713 times.
✗ Branch 1 not taken.
 132713 data_size % 4 != 0 ||
71
2/4
✓ Branch 0 taken 132713 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 132713 times.
✗ Branch 3 not taken.
 132713 ((lbm_uint)bits % sizeof(lbm_uint) != 0) ||
72 132713 bits_size < 1 ||
73
1/2
✓ Branch 0 taken 132713 times.
✗ Branch 1 not taken.
 132713 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 132713 bitmap = bits;
80 132713 bitmap_size = bits_size;
81
82
2/2
✓ Branch 0 taken 207034556 times.
✓ Branch 1 taken 132713 times.
 207167269 for (lbm_uint i = 0; i < bitmap_size; i ++) {
83 207034556 bitmap[i] = 0;
84 }
85
86 132713 memory = data;
87 132713 memory_base_address = (lbm_uint)data;
88 132713 memory_size = data_size;
89 132713 memory_min_free = data_size;
90 132713 memory_num_free = data_size;
91 132713 memory_reserve_level = (lbm_uint)(0.1 * (lbm_float)data_size);
92 132713 res = true;
93 }
94 }
95 132726 lbm_mutex_unlock(&lbm_mem_mutex);
96 132726 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 22452901 static inline lbm_uint address_to_bitmap_ix(lbm_uint *ptr) {
108 #ifndef LBM64
109 20584382 return ((lbm_uint)ptr - memory_base_address) >> 2;
110 #else
111 1868519 return ((lbm_uint)ptr - memory_base_address) >> 3;
112 #endif
113 }
114
115 69801 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 69801 return (lbm_int)address_to_bitmap_ix(ptr);
120 }
121
122
123 22862999 static inline lbm_uint *bitmap_ix_to_address(lbm_uint ix) {
124 22862999 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 820470917 static inline lbm_uint status(lbm_uint i) {
138
139 820470917 lbm_uint ix = i << 1; // * 2
140 820470917 lbm_uint word_ix = ix >> WORD_IX_SHIFT; // / 32
141 820470917 lbm_uint bit_ix = ix & WORD_MOD_MASK; // % 32
142
143 820470917 lbm_uint mask = ((lbm_uint)3) << bit_ix; // 000110..0
144 820470917 return (bitmap[word_ix] & mask) >> bit_ix;
145 }
146
147 89902926 static inline void set_status(lbm_uint i, lbm_uint status) {
148 89902926 lbm_uint ix = i << 1; // * 2
149 89902926 lbm_uint word_ix = ix >> WORD_IX_SHIFT; // / 32
150 89902926 lbm_uint bit_ix = ix & WORD_MOD_MASK; // % 32
151
152 89902926 lbm_uint clr_mask = ~(((lbm_uint)3) << bit_ix);
153 89902926 lbm_uint mask = status << bit_ix;
154
155 89902926 bitmap[word_ix] &= clr_mask;
156 89902926 bitmap[word_ix] |= mask;
157 89902926 }
158
159 85 lbm_uint lbm_memory_num_words(void) {
160 85 return memory_size;
161 }
162
163 135432 lbm_uint lbm_memory_num_free(void) {
164 135432 return memory_num_free;
165 }
166
167 4 lbm_uint lbm_memory_maximum_used(void) {
168 4 return (memory_size - memory_min_free);
169 }
170
171 1606091 void lbm_memory_update_min_free(void) {
172
2/2
✓ Branch 0 taken 9563 times.
✓ Branch 1 taken 1596528 times.
 1606091 if (memory_num_free < memory_min_free)
173 9563 memory_min_free = memory_num_free;
174 1606091 }
175
176 12417 lbm_uint lbm_memory_longest_free(void) {
177
3/4
✓ Branch 0 taken 12416 times.
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 12416 times.
 12417 if (memory == NULL || bitmap == NULL) {
178 1 return 0;
179 }
180 12416 lbm_mutex_lock(&lbm_mem_mutex);
181 12416 unsigned int state = INIT;
182 12416 lbm_uint max_length = 0;
183
184 12416 lbm_uint curr_length = 0;
185
2/2
✓ Branch 0 taken 50660096 times.
✓ Branch 1 taken 12416 times.
 50672512 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 50281577 times.
✓ Branch 1 taken 182330 times.
✓ Branch 2 taken 182330 times.
✓ Branch 3 taken 13859 times.
 50660096 switch(status(i)) {
189
3/4
✓ Branch 0 taken 14658 times.
✓ Branch 1 taken 39166126 times.
✓ Branch 2 taken 11100793 times.
✗ Branch 3 not taken.
 50281577 case FREE_OR_USED:
190 switch (state) {
191 14658 case INIT:
192 14658 curr_length = 1;
193
2/2
✓ Branch 0 taken 12416 times.
✓ Branch 1 taken 2242 times.
 14658 if (curr_length > max_length) max_length = curr_length;
194 14658 state = FREE_LENGTH_CHECK;
195 14658 break;
196 39166126 case FREE_LENGTH_CHECK:
197 39166126 curr_length ++;
198
2/2
✓ Branch 0 taken 39072328 times.
✓ Branch 1 taken 93798 times.
 39166126 if (curr_length > max_length) max_length = curr_length;
199 39166126 state = FREE_LENGTH_CHECK;
200 39166126 break;
201 11100793 case SKIP:
202 11100793 break;
203 }
204 50281577 break;
205 182330 case END:
206 182330 state = INIT;
207 182330 break;
208 182330 case START:
209 182330 state = SKIP;
210 182330 break;
211 13859 default: // START_END
212 13859 state = INIT;
213 13859 break;
214 }
215 }
216 12416 lbm_mutex_unlock(&lbm_mem_mutex);
217
2/2
✓ Branch 0 taken 12414 times.
✓ Branch 1 taken 2 times.
 12416 if (memory_num_free - max_length < memory_reserve_level) {
218 12414 lbm_uint n = memory_reserve_level - (memory_num_free - max_length);
219
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12414 times.
 12414 if (n >= max_length) {
220 ✗ max_length = 0;
221 } else {
222 12414 max_length -= n;
223 }
224 }
225 12416 return max_length;
226 }
227
228 22877173 static lbm_uint *lbm_memory_allocate_internal(lbm_uint num_words) {
229
230
3/4
✓ Branch 0 taken 22877172 times.
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 22877172 times.
 22877173 if (memory == NULL || bitmap == NULL) {
231 1 return NULL;
232 }
233
234 22877172 lbm_mutex_lock(&lbm_mem_mutex);
235
236 22877172 lbm_uint start_ix = 0;
237 22877172 lbm_uint end_ix = 0;
238 22877172 lbm_uint free_length = 0;
239 22877172 unsigned int state = INIT;
240
241
2/2
✓ Branch 0 taken 270355099 times.
✓ Branch 1 taken 14173 times.
 270369272 for (lbm_uint i = 0; i < memory_size; i ++) {
242
4/4
✓ Branch 0 taken 247282735 times.
✓ Branch 1 taken 22559726 times.
✓ Branch 2 taken 198138 times.
✓ Branch 3 taken 314500 times.
 270355099 switch(status(alloc_offset)) {
243
3/4
✓ Branch 0 taken 22888931 times.
✓ Branch 1 taken 176719495 times.
✓ Branch 2 taken 47674309 times.
✗ Branch 3 not taken.
 247282735 case FREE_OR_USED:
244 switch (state) {
245 22888931 case INIT:
246 22888931 start_ix = alloc_offset;
247
2/2
✓ Branch 0 taken 308222 times.
✓ Branch 1 taken 22580709 times.
 22888931 if (num_words == 1) {
248 308222 end_ix = alloc_offset;
249 308222 state = ALLOC_DONE;
250 } else {
251 22580709 state = FREE_LENGTH_CHECK;
252 22580709 free_length = 1;
253 }
254 22888931 break;
255 176719495 case FREE_LENGTH_CHECK:
256 176719495 free_length ++;
257
2/2
✓ Branch 0 taken 22554777 times.
✓ Branch 1 taken 154164718 times.
 176719495 if (free_length == num_words) {
258 22554777 end_ix = alloc_offset;
259 22554777 state = ALLOC_DONE;
260 } else {
261 154164718 state = FREE_LENGTH_CHECK;
262 }
263 176719495 break;
264 47674309 case SKIP:
265 47674309 break;
266 }
267 247282735 break;
268 22559726 case END:
269 22559726 state = INIT;
270 22559726 break;
271 198138 case START:
272 198138 state = SKIP;
273 198138 break;
274 314500 default: // START_END
275 314500 state = INIT;
276 314500 break;
277 }
278
279
2/2
✓ Branch 0 taken 22862999 times.
✓ Branch 1 taken 247492100 times.
 270355099 if (state == ALLOC_DONE) break;
280
281 247492100 alloc_offset++;
282
2/2
✓ Branch 0 taken 14199 times.
✓ Branch 1 taken 247477901 times.
 247492100 if (alloc_offset == memory_size ) {
283 14199 free_length = 0;
284 14199 alloc_offset = 0;
285 14199 state = INIT;
286 }
287 }
288
289
2/2
✓ Branch 0 taken 22862999 times.
✓ Branch 1 taken 14173 times.
 22877172 if (state == ALLOC_DONE) {
290
2/2
✓ Branch 0 taken 308222 times.
✓ Branch 1 taken 22554777 times.
 22862999 if (start_ix == end_ix) {
291 308222 set_status(start_ix, START_END);
292 } else {
293 22554777 set_status(start_ix, START);
294 22554777 set_status(end_ix, END);
295 }
296 22862999 memory_num_free -= num_words;
297 22862999 lbm_mutex_unlock(&lbm_mem_mutex);
298 22862999 return bitmap_ix_to_address(start_ix);
299 }
300 14173 lbm_mutex_unlock(&lbm_mem_mutex);
301 14173 return NULL;
302 }
303
304 141616 lbm_uint *lbm_memory_allocate(lbm_uint num_words) {
305
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 141615 times.
 141616 if (memory_num_free - num_words < memory_reserve_level) {
306 1 lbm_request_gc();
307 1 return NULL;
308 }
309 141615 return lbm_memory_allocate_internal(num_words);
310 }
311
312 22495717 int lbm_memory_free(lbm_uint *ptr) {
313 22495717 int r = 0;
314
2/2
✓ Branch 0 taken 22349411 times.
✓ Branch 1 taken 146306 times.
 22495717 if (lbm_memory_ptr_inside(ptr)) {
315 22349411 lbm_mutex_lock(&lbm_mem_mutex);
316 22349411 lbm_uint ix = address_to_bitmap_ix(ptr);
317 22349411 lbm_uint count_freed = 0;
318 22349411 alloc_offset = ix;
319
3/3
✓ Branch 0 taken 22068369 times.
✓ Branch 1 taken 281040 times.
✓ Branch 2 taken 2 times.
 22349411 switch(status(ix)) {
320 22068369 case START:
321 22068369 set_status(ix, FREE_OR_USED);
322
1/2
✓ Branch 0 taken 127259318 times.
✗ Branch 1 not taken.
 127259318 for (lbm_uint i = ix; i < memory_size; i ++) {
323 127259318 count_freed ++;
324
2/2
✓ Branch 0 taken 22068369 times.
✓ Branch 1 taken 105190949 times.
 127259318 if (status(i) == END) {
325 22068369 set_status(i, FREE_OR_USED);
326 22068369 r = 1;
327 22068369 break;
328 }
329 }
330 22068369 break;
331 281040 case START_END:
332 281040 set_status(ix, FREE_OR_USED);
333 281040 count_freed = 1;
334 281040 r = 1;
335 281040 break;
336 2 default:
337 2 break;
338 }
339
2/2
✓ Branch 0 taken 22349409 times.
✓ Branch 1 taken 2 times.
 22349411 if (r) {
340
4/4
✓ Branch 0 taken 320583505 times.
✓ Branch 1 taken 1327 times.
✓ Branch 2 taken 298235423 times.
✓ Branch 3 taken 22348082 times.
 320584832 while (alloc_offset > 0 && status(alloc_offset - 1) == FREE_OR_USED) {
341 298235423 alloc_offset--;
342 }
343 }
344 22349411 memory_num_free += count_freed;
345 22349411 lbm_mutex_unlock(&lbm_mem_mutex);
346 }
347 22495717 return r;
348 }
349 //Malloc/free like interface
350 22597742 void* lbm_malloc(size_t size) {
351
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 22597741 times.
 22597742 if (size == 0) return NULL;
352 lbm_uint alloc_size;
353
354 22597741 alloc_size = size / sizeof(lbm_uint);
355
2/2
✓ Branch 0 taken 684665 times.
✓ Branch 1 taken 21913076 times.
 22597741 if (size % sizeof(lbm_uint)) alloc_size += 1;
356
357
2/2
✓ Branch 0 taken 13217 times.
✓ Branch 1 taken 22584524 times.
 22597741 if (memory_num_free - alloc_size < memory_reserve_level) {
358 13217 lbm_request_gc();
359 13217 return NULL;
360 }
361 22584524 return lbm_memory_allocate_internal(alloc_size);
362 }
363
364 151036 void* lbm_malloc_reserve(size_t size) {
365
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 151034 times.
 151036 if (size == 0) return NULL;
366 lbm_uint alloc_size;
367
368 151034 alloc_size = size / sizeof(lbm_uint);
369
2/2
✓ Branch 0 taken 124665 times.
✓ Branch 1 taken 26369 times.
 151034 if (size % sizeof(lbm_uint)) alloc_size += 1;
370
371
2/2
✓ Branch 0 taken 313 times.
✓ Branch 1 taken 150721 times.
 151034 if (memory_num_free - alloc_size < memory_reserve_level) {
372 313 lbm_request_gc();
373 }
374 151034 return lbm_memory_allocate_internal(alloc_size);
375 }
376
377 117931 void lbm_free(void *ptr) {
378 117931 lbm_memory_free(ptr);
379 117931 }
380
381 33696 int lbm_memory_shrink(lbm_uint *ptr, lbm_uint n) {
382
4/4
✓ Branch 0 taken 33693 times.
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 33689 times.
 33696 if (!lbm_memory_ptr_inside(ptr) || n == 0) return 0;
383
384 33689 lbm_uint ix = address_to_bitmap_ix(ptr);
385
386 33689 lbm_mutex_lock(&lbm_mem_mutex);
387
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 33687 times.
 33689 if (status(ix) == START_END) {
388 2 lbm_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 33687 times.
 33687 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 33687 bool done = false;
397 33687 unsigned int i = 0;
398
399
1/2
✓ Branch 0 taken 303237 times.
✗ Branch 1 not taken.
 303237 for (i = 0; i < (memory_size - ix); i ++) {
400
3/4
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 303236 times.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 303237 if (status(ix+i) == END && i < n) {
401 1 lbm_mutex_unlock(&lbm_mem_mutex);
402 1 return 0; // cannot shrink allocation to a larger size
403 }
404
405
2/2
✓ Branch 0 taken 33686 times.
✓ Branch 1 taken 269550 times.
 303236 if (i == (n-1)) {
406
2/4
✓ Branch 0 taken 33686 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 33686 times.
 67372 if (status(ix+i) == END ||
407 33686 status(ix+i) == START_END) {
408 ✗ done = true;
409 }
410
2/2
✓ Branch 0 taken 6452 times.
✓ Branch 1 taken 27234 times.
 33686 if (i == 0) {
411 6452 set_status(ix+i, START_END);
412 }
413 else {
414 27234 set_status(ix+i, END);
415 }
416 33686 break;
417 }
418 }
419 33686 alloc_offset = ix+i;
420
421 33686 lbm_uint count = 0;
422
1/2
✓ Branch 0 taken 33686 times.
✗ Branch 1 not taken.
 33686 if (!done) {
423 33686 i++; // move to next position, prev position should be END or START_END
424
1/2
✓ Branch 0 taken 28825503 times.
✗ Branch 1 not taken.
 28825503 for (;i < (memory_size - ix); i ++) {
425 28825503 count ++;
426
2/2
✓ Branch 0 taken 33686 times.
✓ Branch 1 taken 28791817 times.
 28825503 if (status(ix+i) == END) {
427 33686 set_status(ix+i, FREE_OR_USED);
428 33686 break;
429 }
430 }
431 }
432
433 33686 memory_num_free += count;
434 33686 lbm_mutex_unlock(&lbm_mem_mutex);
435 33686 return 1;
436 }
437
438 22541110 int lbm_memory_ptr_inside(lbm_uint *ptr) {
439
2/2
✓ Branch 0 taken 22383124 times.
✓ Branch 1 taken 157986 times.
 44924234 return ((lbm_uint)ptr >= (lbm_uint)memory &&
440
2/2
✓ Branch 0 taken 22383115 times.
✓ Branch 1 taken 9 times.
 22383124 (lbm_uint)ptr < (lbm_uint)memory + (memory_size * sizeof(lbm_uint)));
441 }
442