GCC Code Coverage Report

Directory: ../src/
File: /home/joels/Current/lispbm/src/lbm_memory.c
Date: 2024-11-05 17:11:09
Exec Total Coverage
Lines: 251 280 89.6%
Functions: 17 19 89.5%
Branches: 104 146 71.2%
Line Branch Exec Source
1 /*
2 Copyright 2020 - 2024 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 volatile lbm_uint memory_reserve_level = 0;
49 static mutex_t lbm_mem_mutex;
50 static bool lbm_mem_mutex_initialized;
51 static lbm_uint alloc_offset = 0;
52
53 43008 int lbm_memory_init(lbm_uint *data, lbm_uint data_size,
54 lbm_uint *bits, lbm_uint bits_size) {
55
56
2/2
✓ Branch 0 taken 21504 times.
✓ Branch 1 taken 21504 times.
 43008 if (!lbm_mem_mutex_initialized) {
57 21504 mutex_init(&lbm_mem_mutex);
58 21504 lbm_mem_mutex_initialized = true;
59 }
60
61 43008 alloc_offset = 0;
62
63 43008 mutex_lock(&lbm_mem_mutex);
64 43008 int res = 0;
65
2/4
✓ Branch 0 taken 43008 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 43008 times.
 43008 if (data == NULL || bits == NULL) return 0;
66
67
1/2
✓ Branch 0 taken 43008 times.
✗ Branch 1 not taken.
 43008 if (((lbm_uint)data % sizeof(lbm_uint) != 0) ||
68
1/2
✓ Branch 0 taken 43008 times.
✗ Branch 1 not taken.
 43008 (data_size * 2) != (bits_size * sizeof(lbm_uint) * 8) ||
69
1/2
✓ Branch 0 taken 43008 times.
✗ Branch 1 not taken.
 43008 data_size % 4 != 0 ||
70
2/4
✓ Branch 0 taken 43008 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 43008 times.
✗ Branch 3 not taken.
 43008 ((lbm_uint)bits % sizeof(lbm_uint) != 0) ||
71 43008 bits_size < 1 ||
72
1/2
✓ Branch 0 taken 43008 times.
✗ Branch 1 not taken.
 43008 bits_size % 4 != 0) {
73 // data is not aligned to sizeof lbm_uint
74 // size is too small
75 // or size is not a multiple of 4
76 } else {
77
78 43008 bitmap = bits;
79 43008 bitmap_size = bits_size;
80
81
2/2
✓ Branch 0 taken 11010048 times.
✓ Branch 1 taken 43008 times.
 11053056 for (lbm_uint i = 0; i < bitmap_size; i ++) {
82 11010048 bitmap[i] = 0;
83 }
84
85 43008 memory = data;
86 43008 memory_base_address = (lbm_uint)data;
87 43008 memory_size = data_size;
88 43008 memory_num_free = data_size;
89 43008 memory_reserve_level = (lbm_uint)(0.1 * (lbm_float)data_size);
90 43008 res = 1;
91 }
92 43008 mutex_unlock(&lbm_mem_mutex);
93 43008 return res;
94 }
95
96 ✗ void lbm_memory_set_reserve(lbm_uint num_words) {
97 ✗ memory_reserve_level = num_words;
98 ✗ }
99
100 ✗ lbm_uint lbm_memory_get_reserve(void) {
101 ✗ return memory_reserve_level;
102 }
103
104 9676966 static inline lbm_uint address_to_bitmap_ix(lbm_uint *ptr) {
105 #ifndef LBM64
106 9676966 return ((lbm_uint)ptr - memory_base_address) >> 2;
107 #else
108 return ((lbm_uint)ptr - memory_base_address) >> 3;
109 #endif
110 }
111
112 22540 lbm_int lbm_memory_address_to_ix(lbm_uint *ptr) {
113 /* TODO: assuming that index
114 will have more then enough room in the
115 positive half of a 28bit integer */
116 22540 return (lbm_int)address_to_bitmap_ix(ptr);
117 }
118
119
120 10394155 static inline lbm_uint *bitmap_ix_to_address(lbm_uint ix) {
121 10394155 return &((lbm_uint*)(memory_base_address))[ix];// + (ix << 2));
122 }
123
124 #ifndef LBM64
125 #define WORD_IX_SHIFT 5
126 #define WORD_MOD_MASK 0x1F
127 #define BITMAP_SIZE_SHIFT 4 // 16 statuses per bitmap word
128 #else
129 #define WORD_IX_SHIFT 6 // divide by 64
130 #define WORD_MOD_MASK 0x3F // mod 64
131 #define BITMAP_SIZE_SHIFT 5 // times 32, 32 statuses per bitmap word
132 #endif
133
134 459317070 static inline lbm_uint status(lbm_uint i) {
135
136 459317070 lbm_uint ix = i << 1; // * 2
137 459317070 lbm_uint word_ix = ix >> WORD_IX_SHIFT; // / 32
138 459317070 lbm_uint bit_ix = ix & WORD_MOD_MASK; // % 32
139
140 459317070 lbm_uint mask = ((lbm_uint)3) << bit_ix; // 000110..0
141
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 459317070 times.
 459317070 if (word_ix > bitmap_size) {
142 ✗ return (lbm_uint)NULL;
143 }
144 459317070 return (bitmap[word_ix] & mask) >> bit_ix;
145 }
146
147 39955956 static inline void set_status(lbm_uint i, lbm_uint status) {
148 39955956 lbm_uint ix = i << 1; // * 2
149 39955956 lbm_uint word_ix = ix >> WORD_IX_SHIFT; // / 32
150 39955956 lbm_uint bit_ix = ix & WORD_MOD_MASK; // % 32
151
152 39955956 lbm_uint clr_mask = ~(((lbm_uint)3) << bit_ix);
153 39955956 lbm_uint mask = status << bit_ix;
154
155 39955956 bitmap[word_ix] &= clr_mask;
156 39955956 bitmap[word_ix] |= mask;
157 39955956 }
158
159 28 lbm_uint lbm_memory_num_words(void) {
160 28 return memory_size;
161 }
162
163 44072 lbm_uint lbm_memory_num_free(void) {
164
2/4
✓ Branch 0 taken 44072 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 44072 times.
 44072 if (memory == NULL || bitmap == NULL) {
165 ✗ return 0;
166 }
167 44072 mutex_lock(&lbm_mem_mutex);
168 44072 unsigned int state = INIT;
169 44072 lbm_uint sum_length = 0;
170
171
2/2
✓ Branch 0 taken 180518912 times.
✓ Branch 1 taken 44072 times.
 180562984 for (unsigned int i = 0; i < (bitmap_size << BITMAP_SIZE_SHIFT); i ++) {
172
173
4/5
✓ Branch 1 taken 178375400 times.
✓ Branch 2 taken 1071448 times.
✓ Branch 3 taken 1071448 times.
✓ Branch 4 taken 616 times.
✗ Branch 5 not taken.
 180518912 switch(status(i)) {
174
3/4
✓ Branch 0 taken 45248 times.
✓ Branch 1 taken 158216520 times.
✓ Branch 2 taken 20113632 times.
✗ Branch 3 not taken.
 178375400 case FREE_OR_USED:
175 switch (state) {
176 45248 case INIT:
177 45248 state = FREE_LENGTH_CHECK;
178 45248 sum_length ++;
179 45248 break;
180 158216520 case FREE_LENGTH_CHECK:
181 158216520 sum_length ++;
182 158216520 state = FREE_LENGTH_CHECK;
183 158216520 break;
184 20113632 case SKIP:
185 20113632 break;
186 }
187 178375400 break;
188 1071448 case END:
189 1071448 state = INIT;
190 1071448 break;
191 1071448 case START:
192 1071448 state = SKIP;
193 1071448 break;
194 616 case START_END:
195 616 state = INIT;
196 616 break;
197 ✗ default:
198 ✗ mutex_unlock(&lbm_mem_mutex);
199 ✗ return 0;
200 break;
201 }
202 }
203 44072 mutex_unlock(&lbm_mem_mutex);
204 44072 return sum_length;
205 }
206
207 3360 lbm_uint lbm_memory_longest_free(void) {
208
2/4
✓ Branch 0 taken 3360 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 3360 times.
 3360 if (memory == NULL || bitmap == NULL) {
209 ✗ return 0;
210 }
211 3360 mutex_lock(&lbm_mem_mutex);
212 3360 unsigned int state = INIT;
213 3360 lbm_uint max_length = 0;
214
215 3360 lbm_uint curr_length = 0;
216
2/2
✓ Branch 0 taken 13762560 times.
✓ Branch 1 taken 3360 times.
 13765920 for (unsigned int i = 0; i < (bitmap_size << BITMAP_SIZE_SHIFT); i ++) {
217
218
4/5
✓ Branch 1 taken 13477520 times.
✓ Branch 2 taken 140504 times.
✓ Branch 3 taken 140504 times.
✓ Branch 4 taken 4032 times.
✗ Branch 5 not taken.
 13762560 switch(status(i)) {
219
3/4
✓ Branch 0 taken 3808 times.
✓ Branch 1 taken 10138828 times.
✓ Branch 2 taken 3334884 times.
✗ Branch 3 not taken.
 13477520 case FREE_OR_USED:
220 switch (state) {
221 3808 case INIT:
222 3808 curr_length = 1;
223
2/2
✓ Branch 0 taken 3360 times.
✓ Branch 1 taken 448 times.
 3808 if (curr_length > max_length) max_length = curr_length;
224 3808 state = FREE_LENGTH_CHECK;
225 3808 break;
226 10138828 case FREE_LENGTH_CHECK:
227 10138828 curr_length ++;
228
2/2
✓ Branch 0 taken 10114090 times.
✓ Branch 1 taken 24738 times.
 10138828 if (curr_length > max_length) max_length = curr_length;
229 10138828 state = FREE_LENGTH_CHECK;
230 10138828 break;
231 3334884 case SKIP:
232 3334884 break;
233 }
234 13477520 break;
235 140504 case END:
236 140504 state = INIT;
237 140504 break;
238 140504 case START:
239 140504 state = SKIP;
240 140504 break;
241 4032 case START_END:
242 4032 state = INIT;
243 4032 break;
244 ✗ default:
245 ✗ mutex_unlock(&lbm_mem_mutex);
246 ✗ return 0;
247 break;
248 }
249 }
250 3360 mutex_unlock(&lbm_mem_mutex);
251
1/2
✓ Branch 0 taken 3360 times.
✗ Branch 1 not taken.
 3360 if (memory_num_free - max_length < memory_reserve_level) {
252 3360 lbm_uint n = memory_reserve_level - (memory_num_free - max_length);
253 3360 max_length -= n;
254 }
255 3360 return max_length;
256 }
257
258 10400001 static lbm_uint *lbm_memory_allocate_internal(lbm_uint num_words) {
259
260
2/4
✓ Branch 0 taken 10400001 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 10400001 times.
 10400001 if (memory == NULL || bitmap == NULL) {
261 ✗ return NULL;
262 }
263
264 10400001 mutex_lock(&lbm_mem_mutex);
265
266 10400001 lbm_uint start_ix = 0;
267 10400001 lbm_uint end_ix = 0;
268 10400001 lbm_uint free_length = 0;
269 10400001 unsigned int state = INIT;
270 10400001 lbm_uint loop_max = (bitmap_size << BITMAP_SIZE_SHIFT);
271
272
2/2
✓ Branch 0 taken 100720527 times.
✓ Branch 1 taken 5846 times.
 100726373 for (lbm_uint i = 0; i < loop_max; i ++) {
273
4/5
✓ Branch 1 taken 89474637 times.
✓ Branch 2 taken 10707372 times.
✓ Branch 3 taken 458564 times.
✓ Branch 4 taken 79954 times.
✗ Branch 5 not taken.
 100720527 switch(status(alloc_offset)) {
274
3/4
✓ Branch 0 taken 10470867 times.
✓ Branch 1 taken 59357366 times.
✓ Branch 2 taken 19646404 times.
✗ Branch 3 not taken.
 89474637 case FREE_OR_USED:
275 switch (state) {
276 10470867 case INIT:
277 10470867 start_ix = alloc_offset;
278
2/2
✓ Branch 0 taken 73352 times.
✓ Branch 1 taken 10397515 times.
 10470867 if (num_words == 1) {
279 73352 end_ix = alloc_offset;
280 73352 state = ALLOC_DONE;
281 } else {
282 10397515 state = FREE_LENGTH_CHECK;
283 10397515 free_length = 1;
284 }
285 10470867 break;
286 59357366 case FREE_LENGTH_CHECK:
287 59357366 free_length ++;
288
2/2
✓ Branch 0 taken 10320803 times.
✓ Branch 1 taken 49036563 times.
 59357366 if (free_length == num_words) {
289 10320803 end_ix = alloc_offset;
290 10320803 state = ALLOC_DONE;
291 } else {
292 49036563 state = FREE_LENGTH_CHECK;
293 }
294 59357366 break;
295 19646404 case SKIP:
296 19646404 break;
297 }
298 89474637 break;
299 10707372 case END:
300 10707372 state = INIT;
301 10707372 break;
302 458564 case START:
303 458564 state = SKIP;
304 458564 break;
305 79954 case START_END:
306 79954 state = INIT;
307 79954 break;
308 ✗ default: // error case
309 ✗ mutex_unlock(&lbm_mem_mutex);
310 ✗ return NULL;
311 }
312
313
2/2
✓ Branch 0 taken 10394155 times.
✓ Branch 1 taken 90326372 times.
 100720527 if (state == ALLOC_DONE) break;
314
315 90326372 alloc_offset++;
316
2/2
✓ Branch 0 taken 6182 times.
✓ Branch 1 taken 90320190 times.
 90326372 if (alloc_offset == loop_max ) {
317 6182 free_length = 0;
318 6182 alloc_offset = 0;
319 6182 state = INIT;
320 }
321 }
322
323
2/2
✓ Branch 0 taken 10394155 times.
✓ Branch 1 taken 5846 times.
 10400001 if (state == ALLOC_DONE) {
324
2/2
✓ Branch 0 taken 73352 times.
✓ Branch 1 taken 10320803 times.
 10394155 if (start_ix == end_ix) {
325 73352 set_status(start_ix, START_END);
326 } else {
327 10320803 set_status(start_ix, START);
328 10320803 set_status(end_ix, END);
329 }
330 10394155 memory_num_free -= num_words;
331 10394155 mutex_unlock(&lbm_mem_mutex);
332 10394155 return bitmap_ix_to_address(start_ix);
333 }
334 5846 mutex_unlock(&lbm_mem_mutex);
335 5846 return NULL;
336 }
337
338 454328 lbm_uint *lbm_memory_allocate(lbm_uint num_words) {
339
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 454328 times.
 454328 if (memory_num_free - num_words < memory_reserve_level) {
340 ✗ lbm_request_gc();
341 ✗ return NULL;
342 }
343 454328 return lbm_memory_allocate_internal(num_words);
344 }
345
346 9691839 int lbm_memory_free(lbm_uint *ptr) {
347 9691839 int r = 0;
348 9691839 lbm_uint count_freed = 0;
349
2/2
✓ Branch 1 taken 9644657 times.
✓ Branch 2 taken 47182 times.
 9691839 if (lbm_memory_ptr_inside(ptr)) {
350 9644657 mutex_lock(&lbm_mem_mutex);
351 9644657 lbm_uint ix = address_to_bitmap_ix(ptr);
352 9644657 alloc_offset = ix;
353
354
2/3
✓ Branch 1 taken 9576803 times.
✓ Branch 2 taken 67854 times.
✗ Branch 3 not taken.
 9644657 switch(status(ix)) {
355 9576803 case START:
356 9576803 set_status(ix, FREE_OR_USED);
357
1/2
✓ Branch 0 taken 45759004 times.
✗ Branch 1 not taken.
 45759004 for (lbm_uint i = ix; i < (bitmap_size << BITMAP_SIZE_SHIFT); i ++) {
358 45759004 count_freed ++;
359
2/2
✓ Branch 1 taken 9576803 times.
✓ Branch 2 taken 36182201 times.
 45759004 if (status(i) == END) {
360 9576803 set_status(i, FREE_OR_USED);
361 9576803 r = 1;
362 9576803 break;
363 }
364 }
365 9576803 break;
366 67854 case START_END:
367 67854 set_status(ix, FREE_OR_USED);
368 67854 count_freed = 1;
369 67854 r = 1;
370 67854 break;
371 ✗ default:
372 ✗ break;
373 }
374
1/2
✓ Branch 0 taken 9644657 times.
✗ Branch 1 not taken.
 9644657 if (r) {
375
3/4
✓ Branch 0 taken 101216679 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 91572022 times.
✓ Branch 4 taken 9644657 times.
 101216679 while (alloc_offset > 0 && status(alloc_offset - 1) == FREE_OR_USED) {
376 91572022 alloc_offset--;
377 }
378 }
379 9644657 memory_num_free += count_freed;
380 9644657 mutex_unlock(&lbm_mem_mutex);
381 }
382 9691839 return r;
383 }
384 //Malloc/free like interface
385 9908858 void* lbm_malloc(size_t size) {
386
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 9908858 times.
 9908858 if (size == 0) return NULL;
387 lbm_uint alloc_size;
388
389 9908858 alloc_size = size / sizeof(lbm_uint);
390
2/2
✓ Branch 0 taken 325174 times.
✓ Branch 1 taken 9583684 times.
 9908858 if (size % sizeof(lbm_uint)) alloc_size += 1;
391
392
2/2
✓ Branch 0 taken 4280 times.
✓ Branch 1 taken 9904578 times.
 9908858 if (memory_num_free - alloc_size < memory_reserve_level) {
393 4280 lbm_request_gc();
394 4280 return NULL;
395 }
396 9904578 return lbm_memory_allocate_internal(alloc_size);
397 }
398
399 41095 void* lbm_malloc_reserve(size_t size) {
400
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 41095 times.
 41095 if (size == 0) return NULL;
401 lbm_uint alloc_size;
402
403 41095 alloc_size = size / sizeof(lbm_uint);
404
2/2
✓ Branch 0 taken 40695 times.
✓ Branch 1 taken 400 times.
 41095 if (size % sizeof(lbm_uint)) alloc_size += 1;
405
406
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 41007 times.
 41095 if (memory_num_free - alloc_size < memory_reserve_level) {
407 88 lbm_request_gc();
408 }
409 41095 return lbm_memory_allocate_internal(alloc_size);
410 }
411
412 30335 void lbm_free(void *ptr) {
413 30335 lbm_memory_free(ptr);
414 30335 }
415
416 9769 int lbm_memory_shrink(lbm_uint *ptr, lbm_uint n) {
417
2/4
✓ Branch 1 taken 9769 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 9769 times.
 9769 if (!lbm_memory_ptr_inside(ptr) || n == 0) return 0;
418
419 9769 lbm_uint ix = address_to_bitmap_ix(ptr);
420
421 9769 mutex_lock(&lbm_mem_mutex);
422
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 9769 times.
 9769 if (status(ix) == START_END) {
423 ✗ mutex_unlock(&lbm_mem_mutex);
424 ✗ return 1; // A one word arrays always succeeds at remaining at 1 word
425 }
426
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 9769 times.
 9769 if (status(ix) != START) {
427 ✗ mutex_unlock(&lbm_mem_mutex);
428 ✗ return 0; // ptr does not point to the start of an allocated range.
429 }
430
431 9769 bool done = false;
432 9769 unsigned int i = 0;
433
434
1/2
✓ Branch 0 taken 114178 times.
✗ Branch 1 not taken.
 114178 for (i = 0; i < ((bitmap_size << BITMAP_SIZE_SHIFT) - ix); i ++) {
435
1/4
✗ Branch 1 not taken.
✓ Branch 2 taken 114178 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 114178 if (status(ix+i) == END && i < n) {
436 ✗ mutex_unlock(&lbm_mem_mutex);
437 ✗ return 0; // cannot shrink allocation to a larger size
438 }
439
440
2/2
✓ Branch 0 taken 9769 times.
✓ Branch 1 taken 104409 times.
 114178 if (i == (n-1)) {
441
2/4
✓ Branch 1 taken 9769 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 9769 times.
 19538 if (status(ix+i) == END ||
442 9769 status(ix+i) == START_END) {
443 ✗ done = true;
444 }
445
2/2
✓ Branch 0 taken 1176 times.
✓ Branch 1 taken 8593 times.
 9769 if (i == 0) {
446 1176 set_status(ix+i, START_END);
447 }
448 else {
449 8593 set_status(ix+i, END);
450 }
451 9769 break;
452 }
453 }
454 9769 alloc_offset = ix+i;
455
456 9769 lbm_uint count = 0;
457
1/2
✓ Branch 0 taken 9769 times.
✗ Branch 1 not taken.
 9769 if (!done) {
458 9769 i++; // move to next position, prev position should be END or START_END
459
1/2
✓ Branch 0 taken 7541477 times.
✗ Branch 1 not taken.
 7541477 for (;i < ((bitmap_size << BITMAP_SIZE_SHIFT) - ix); i ++) {
460 7541477 count ++;
461
2/2
✓ Branch 1 taken 9769 times.
✓ Branch 2 taken 7531708 times.
 7541477 if (status(ix+i) == END) {
462 9769 set_status(ix+i, FREE_OR_USED);
463 9769 break;
464 }
465 }
466 }
467
468 9769 memory_num_free += count;
469 9769 mutex_unlock(&lbm_mem_mutex);
470 9769 return 1;
471 }
472
473 9701608 int lbm_memory_ptr_inside(lbm_uint *ptr) {
474
2/2
✓ Branch 0 taken 9654426 times.
✓ Branch 1 taken 47182 times.
 19356034 return ((lbm_uint)ptr >= (lbm_uint)memory &&
475
1/2
✓ Branch 0 taken 9654426 times.
✗ Branch 1 not taken.
 9654426 (lbm_uint)ptr < (lbm_uint)memory + (memory_size * sizeof(lbm_uint)));
476 }
477