GCC Code Coverage Report

Directory: ../src/
File: /home/joels/Current/lispbm/src/lbm_memory.c
Date: 2024-08-06 17:32:21
Exec Total Coverage
Lines: 250 280 89.3%
Functions: 16 19 84.2%
Branches: 103 146 70.5%
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 34888 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 17444 times.
✓ Branch 1 taken 17444 times.
 34888 if (!lbm_mem_mutex_initialized) {
57 17444 mutex_init(&lbm_mem_mutex);
58 17444 lbm_mem_mutex_initialized = true;
59 }
60
61 34888 alloc_offset = 0;
62
63 34888 mutex_lock(&lbm_mem_mutex);
64 34888 int res = 0;
65
2/4
✓ Branch 0 taken 34888 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 34888 times.
 34888 if (data == NULL || bits == NULL) return 0;
66
67
1/2
✓ Branch 0 taken 34888 times.
✗ Branch 1 not taken.
 34888 if (((lbm_uint)data % sizeof(lbm_uint) != 0) ||
68
1/2
✓ Branch 0 taken 34888 times.
✗ Branch 1 not taken.
 34888 (data_size * 2) != (bits_size * sizeof(lbm_uint) * 8) ||
69
1/2
✓ Branch 0 taken 34888 times.
✗ Branch 1 not taken.
 34888 data_size % 4 != 0 ||
70
2/4
✓ Branch 0 taken 34888 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 34888 times.
✗ Branch 3 not taken.
 34888 ((lbm_uint)bits % sizeof(lbm_uint) != 0) ||
71 34888 bits_size < 1 ||
72
1/2
✓ Branch 0 taken 34888 times.
✗ Branch 1 not taken.
 34888 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 34888 bitmap = bits;
79 34888 bitmap_size = bits_size;
80
81
2/2
✓ Branch 0 taken 8931328 times.
✓ Branch 1 taken 34888 times.
 8966216 for (lbm_uint i = 0; i < bitmap_size; i ++) {
82 8931328 bitmap[i] = 0;
83 }
84
85 34888 memory = data;
86 34888 memory_base_address = (lbm_uint)data;
87 34888 memory_size = data_size;
88 34888 memory_num_free = data_size;
89 34888 memory_reserve_level = (lbm_uint)(0.1 * (lbm_float)data_size);
90 34888 res = 1;
91 }
92 34888 mutex_unlock(&lbm_mem_mutex);
93 34888 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 8796070 static inline lbm_uint address_to_bitmap_ix(lbm_uint *ptr) {
105 #ifndef LBM64
106 8796070 return ((lbm_uint)ptr - memory_base_address) >> 2;
107 #else
108 return ((lbm_uint)ptr - memory_base_address) >> 3;
109 #endif
110 }
111
112 18228 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 18228 return (lbm_int)address_to_bitmap_ix(ptr);
117 }
118
119
120 9344182 static inline lbm_uint *bitmap_ix_to_address(lbm_uint ix) {
121 9344182 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 382365100 static inline lbm_uint status(lbm_uint i) {
135
136 382365100 lbm_uint ix = i << 1; // * 2
137 382365100 lbm_uint word_ix = ix >> WORD_IX_SHIFT; // / 32
138 382365100 lbm_uint bit_ix = ix & WORD_MOD_MASK; // % 32
139
140 382365100 lbm_uint mask = ((lbm_uint)3) << bit_ix; // 000110..0
141
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 382365100 times.
 382365100 if (word_ix > bitmap_size) {
142 ✗ return (lbm_uint)NULL;
143 }
144 382365100 return (bitmap[word_ix] & mask) >> bit_ix;
145 }
146
147 36106448 static inline void set_status(lbm_uint i, lbm_uint status) {
148 36106448 lbm_uint ix = i << 1; // * 2
149 36106448 lbm_uint word_ix = ix >> WORD_IX_SHIFT; // / 32
150 36106448 lbm_uint bit_ix = ix & WORD_MOD_MASK; // % 32
151
152 36106448 lbm_uint clr_mask = ~(((lbm_uint)3) << bit_ix);
153 36106448 lbm_uint mask = status << bit_ix;
154
155 36106448 bitmap[word_ix] &= clr_mask;
156 36106448 bitmap[word_ix] |= mask;
157 36106448 }
158
159 ✗ lbm_uint lbm_memory_num_words(void) {
160 ✗ return memory_size;
161 }
162
163 35952 lbm_uint lbm_memory_num_free(void) {
164
2/4
✓ Branch 0 taken 35952 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 35952 times.
 35952 if (memory == NULL || bitmap == NULL) {
165 ✗ return 0;
166 }
167 35952 mutex_lock(&lbm_mem_mutex);
168 35952 unsigned int state = INIT;
169 35952 lbm_uint sum_length = 0;
170
171
2/2
✓ Branch 0 taken 147259392 times.
✓ Branch 1 taken 35952 times.
 147295344 for (unsigned int i = 0; i < (bitmap_size << BITMAP_SIZE_SHIFT); i ++) {
172
173
4/5
✓ Branch 1 taken 145505640 times.
✓ Branch 2 taken 876568 times.
✓ Branch 3 taken 876568 times.
✓ Branch 4 taken 616 times.
✗ Branch 5 not taken.
 147259392 switch(status(i)) {
174
3/4
✓ Branch 0 taken 37128 times.
✓ Branch 1 taken 128999696 times.
✓ Branch 2 taken 16468816 times.
✗ Branch 3 not taken.
 145505640 case FREE_OR_USED:
175 switch (state) {
176 37128 case INIT:
177 37128 state = FREE_LENGTH_CHECK;
178 37128 sum_length ++;
179 37128 break;
180 128999696 case FREE_LENGTH_CHECK:
181 128999696 sum_length ++;
182 128999696 state = FREE_LENGTH_CHECK;
183 128999696 break;
184 16468816 case SKIP:
185 16468816 break;
186 }
187 145505640 break;
188 876568 case END:
189 876568 state = INIT;
190 876568 break;
191 876568 case START:
192 876568 state = SKIP;
193 876568 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 35952 mutex_unlock(&lbm_mem_mutex);
204 35952 return sum_length;
205 }
206
207 2912 lbm_uint lbm_memory_longest_free(void) {
208
2/4
✓ Branch 0 taken 2912 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 2912 times.
 2912 if (memory == NULL || bitmap == NULL) {
209 ✗ return 0;
210 }
211 2912 mutex_lock(&lbm_mem_mutex);
212 2912 unsigned int state = INIT;
213 2912 lbm_uint max_length = 0;
214
215 2912 lbm_uint curr_length = 0;
216
2/2
✓ Branch 0 taken 11927552 times.
✓ Branch 1 taken 2912 times.
 11930464 for (unsigned int i = 0; i < (bitmap_size << BITMAP_SIZE_SHIFT); i ++) {
217
218
4/5
✓ Branch 1 taken 11674838 times.
✓ Branch 2 taken 124348 times.
✓ Branch 3 taken 124348 times.
✓ Branch 4 taken 4018 times.
✗ Branch 5 not taken.
 11927552 switch(status(i)) {
219
3/4
✓ Branch 0 taken 3360 times.
✓ Branch 1 taken 8670746 times.
✓ Branch 2 taken 3000732 times.
✗ Branch 3 not taken.
 11674838 case FREE_OR_USED:
220 switch (state) {
221 3360 case INIT:
222 3360 curr_length = 1;
223
2/2
✓ Branch 0 taken 2912 times.
✓ Branch 1 taken 448 times.
 3360 if (curr_length > max_length) max_length = curr_length;
224 3360 state = FREE_LENGTH_CHECK;
225 3360 break;
226 8670746 case FREE_LENGTH_CHECK:
227 8670746 curr_length ++;
228
2/2
✓ Branch 0 taken 8645994 times.
✓ Branch 1 taken 24752 times.
 8670746 if (curr_length > max_length) max_length = curr_length;
229 8670746 state = FREE_LENGTH_CHECK;
230 8670746 break;
231 3000732 case SKIP:
232 3000732 break;
233 }
234 11674838 break;
235 124348 case END:
236 124348 state = INIT;
237 124348 break;
238 124348 case START:
239 124348 state = SKIP;
240 124348 break;
241 4018 case START_END:
242 4018 state = INIT;
243 4018 break;
244 ✗ default:
245 ✗ mutex_unlock(&lbm_mem_mutex);
246 ✗ return 0;
247 break;
248 }
249 }
250 2912 mutex_unlock(&lbm_mem_mutex);
251
1/2
✓ Branch 0 taken 2912 times.
✗ Branch 1 not taken.
 2912 if (memory_num_free - max_length < memory_reserve_level) {
252 2912 lbm_uint n = memory_reserve_level - (memory_num_free - max_length);
253 2912 max_length -= n;
254 }
255 2912 return max_length;
256 }
257
258 9349862 static lbm_uint *lbm_memory_allocate_internal(lbm_uint num_words) {
259
260
2/4
✓ Branch 0 taken 9349862 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 9349862 times.
 9349862 if (memory == NULL || bitmap == NULL) {
261 ✗ return NULL;
262 }
263
264 9349862 mutex_lock(&lbm_mem_mutex);
265
266 9349862 lbm_uint start_ix = 0;
267 9349862 lbm_uint end_ix = 0;
268 9349862 lbm_uint free_length = 0;
269 9349862 unsigned int state = INIT;
270 9349862 lbm_uint loop_max = (bitmap_size << BITMAP_SIZE_SHIFT);
271
272
2/2
✓ Branch 0 taken 85821296 times.
✓ Branch 1 taken 5680 times.
 85826976 for (lbm_uint i = 0; i < loop_max; i ++) {
273
4/5
✓ Branch 1 taken 75700646 times.
✓ Branch 2 taken 9629050 times.
✓ Branch 3 taken 415536 times.
✓ Branch 4 taken 76064 times.
✗ Branch 5 not taken.
 85821296 switch(status(alloc_offset)) {
274
3/4
✓ Branch 0 taken 9404368 times.
✓ Branch 1 taken 47041242 times.
✓ Branch 2 taken 19255036 times.
✗ Branch 3 not taken.
 75700646 case FREE_OR_USED:
275 switch (state) {
276 9404368 case INIT:
277 9404368 start_ix = alloc_offset;
278
2/2
✓ Branch 0 taken 69932 times.
✓ Branch 1 taken 9334436 times.
 9404368 if (num_words == 1) {
279 69932 end_ix = alloc_offset;
280 69932 state = ALLOC_DONE;
281 } else {
282 9334436 state = FREE_LENGTH_CHECK;
283 9334436 free_length = 1;
284 }
285 9404368 break;
286 47041242 case FREE_LENGTH_CHECK:
287 47041242 free_length ++;
288
2/2
✓ Branch 0 taken 9274250 times.
✓ Branch 1 taken 37766992 times.
 47041242 if (free_length == num_words) {
289 9274250 end_ix = alloc_offset;
290 9274250 state = ALLOC_DONE;
291 } else {
292 37766992 state = FREE_LENGTH_CHECK;
293 }
294 47041242 break;
295 19255036 case SKIP:
296 19255036 break;
297 }
298 75700646 break;
299 9629050 case END:
300 9629050 state = INIT;
301 9629050 break;
302 415536 case START:
303 415536 state = SKIP;
304 415536 break;
305 76064 case START_END:
306 76064 state = INIT;
307 76064 break;
308 ✗ default: // error case
309 ✗ mutex_unlock(&lbm_mem_mutex);
310 ✗ return NULL;
311 }
312
313
2/2
✓ Branch 0 taken 9344182 times.
✓ Branch 1 taken 76477114 times.
 85821296 if (state == ALLOC_DONE) break;
314
315 76477114 alloc_offset++;
316
2/2
✓ Branch 0 taken 5976 times.
✓ Branch 1 taken 76471138 times.
 76477114 if (alloc_offset == loop_max ) {
317 5976 free_length = 0;
318 5976 alloc_offset = 0;
319 5976 state = INIT;
320 }
321 }
322
323
2/2
✓ Branch 0 taken 9344182 times.
✓ Branch 1 taken 5680 times.
 9349862 if (state == ALLOC_DONE) {
324
2/2
✓ Branch 0 taken 69932 times.
✓ Branch 1 taken 9274250 times.
 9344182 if (start_ix == end_ix) {
325 69932 set_status(start_ix, START_END);
326 } else {
327 9274250 set_status(start_ix, START);
328 9274250 set_status(end_ix, END);
329 }
330 9344182 memory_num_free -= num_words;
331 9344182 mutex_unlock(&lbm_mem_mutex);
332 9344182 return bitmap_ix_to_address(start_ix);
333 }
334 5680 mutex_unlock(&lbm_mem_mutex);
335 5680 return NULL;
336 }
337
338 510474 lbm_uint *lbm_memory_allocate(lbm_uint num_words) {
339
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 510432 times.
 510474 if (memory_num_free - num_words < memory_reserve_level) {
340 42 lbm_request_gc();
341 42 return NULL;
342 }
343 510432 return lbm_memory_allocate_internal(num_words);
344 }
345
346 8767004 int lbm_memory_free(lbm_uint *ptr) {
347 8767004 int r = 0;
348 8767004 lbm_uint count_freed = 0;
349
1/2
✓ Branch 1 taken 8767004 times.
✗ Branch 2 not taken.
 8767004 if (lbm_memory_ptr_inside(ptr)) {
350 8767004 mutex_lock(&lbm_mem_mutex);
351 8767004 lbm_uint ix = address_to_bitmap_ix(ptr);
352 8767004 alloc_offset = ix;
353
354
2/3
✓ Branch 1 taken 8699336 times.
✓ Branch 2 taken 67668 times.
✗ Branch 3 not taken.
 8767004 switch(status(ix)) {
355 8699336 case START:
356 8699336 set_status(ix, FREE_OR_USED);
357
1/2
✓ Branch 0 taken 36318090 times.
✗ Branch 1 not taken.
 36318090 for (lbm_uint i = ix; i < (bitmap_size << BITMAP_SIZE_SHIFT); i ++) {
358 36318090 count_freed ++;
359
2/2
✓ Branch 1 taken 8699336 times.
✓ Branch 2 taken 27618754 times.
 36318090 if (status(i) == END) {
360 8699336 set_status(i, FREE_OR_USED);
361 8699336 r = 1;
362 8699336 break;
363 }
364 }
365 8699336 break;
366 67668 case START_END:
367 67668 set_status(ix, FREE_OR_USED);
368 67668 count_freed = 1;
369 67668 r = 1;
370 67668 break;
371 ✗ default:
372 ✗ break;
373 }
374
1/2
✓ Branch 0 taken 8767004 times.
✗ Branch 1 not taken.
 8767004 if (r) {
375
3/4
✓ Branch 0 taken 85718344 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 76951340 times.
✓ Branch 4 taken 8767004 times.
 85718344 while (alloc_offset > 0 && status(alloc_offset - 1) == FREE_OR_USED) {
376 76951340 alloc_offset--;
377 }
378 }
379 8767004 memory_num_free += count_freed;
380 8767004 mutex_unlock(&lbm_mem_mutex);
381 }
382 8767004 return r;
383 }
384 //Malloc/free like interface
385 8833970 void* lbm_malloc(size_t size) {
386
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8833970 times.
 8833970 if (size == 0) return NULL;
387 lbm_uint alloc_size;
388
389 8833970 alloc_size = size / sizeof(lbm_uint);
390
2/2
✓ Branch 0 taken 108870 times.
✓ Branch 1 taken 8725100 times.
 8833970 if (size % sizeof(lbm_uint)) alloc_size += 1;
391
392
2/2
✓ Branch 0 taken 2894 times.
✓ Branch 1 taken 8831076 times.
 8833970 if (memory_num_free - alloc_size < memory_reserve_level) {
393 2894 lbm_request_gc();
394 2894 return NULL;
395 }
396 8831076 return lbm_memory_allocate_internal(alloc_size);
397 }
398
399 8354 void* lbm_malloc_reserve(size_t size) {
400
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8354 times.
 8354 if (size == 0) return NULL;
401 lbm_uint alloc_size;
402
403 8354 alloc_size = size / sizeof(lbm_uint);
404
2/2
✓ Branch 0 taken 8290 times.
✓ Branch 1 taken 64 times.
 8354 if (size % sizeof(lbm_uint)) alloc_size += 1;
405
406
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8354 times.
 8354 if (memory_num_free - alloc_size < memory_reserve_level) {
407 ✗ lbm_request_gc();
408 }
409 8354 return lbm_memory_allocate_internal(alloc_size);
410 }
411
412 8961 void lbm_free(void *ptr) {
413 8961 lbm_memory_free(ptr);
414 8961 }
415
416 10838 int lbm_memory_shrink(lbm_uint *ptr, lbm_uint n) {
417
2/4
✓ Branch 1 taken 10838 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 10838 times.
 10838 if (!lbm_memory_ptr_inside(ptr) || n == 0) return 0;
418
419 10838 lbm_uint ix = address_to_bitmap_ix(ptr);
420
421 10838 mutex_lock(&lbm_mem_mutex);
422
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 10838 times.
 10838 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 10838 times.
 10838 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 10838 bool done = false;
432 10838 unsigned int i = 0;
433
434
1/2
✓ Branch 0 taken 118748 times.
✗ Branch 1 not taken.
 118748 for (i = 0; i < ((bitmap_size << BITMAP_SIZE_SHIFT) - ix); i ++) {
435
1/4
✗ Branch 1 not taken.
✓ Branch 2 taken 118748 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 118748 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 10838 times.
✓ Branch 1 taken 107910 times.
 118748 if (i == (n-1)) {
441
2/4
✓ Branch 1 taken 10838 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 10838 times.
 21676 if (status(ix+i) == END ||
442 10838 status(ix+i) == START_END) {
443 ✗ done = true;
444 }
445
2/2
✓ Branch 0 taken 1064 times.
✓ Branch 1 taken 9774 times.
 10838 if (i == 0) {
446 1064 set_status(ix+i, START_END);
447 }
448 else {
449 9774 set_status(ix+i, END);
450 }
451 10838 break;
452 }
453 }
454 10838 alloc_offset = ix+i;
455
456 10838 lbm_uint count = 0;
457
1/2
✓ Branch 0 taken 10838 times.
✗ Branch 1 not taken.
 10838 if (!done) {
458 10838 i++; // move to next position, prev position should be END or START_END
459
1/2
✓ Branch 0 taken 6391322 times.
✗ Branch 1 not taken.
 6391322 for (;i < ((bitmap_size << BITMAP_SIZE_SHIFT) - ix); i ++) {
460 6391322 count ++;
461
2/2
✓ Branch 1 taken 10838 times.
✓ Branch 2 taken 6380484 times.
 6391322 if (status(ix+i) == END) {
462 10838 set_status(ix+i, FREE_OR_USED);
463 10838 break;
464 }
465 }
466 }
467
468 10838 memory_num_free += count;
469 10838 mutex_unlock(&lbm_mem_mutex);
470 10838 return 1;
471 }
472
473 8979761 int lbm_memory_ptr_inside(lbm_uint *ptr) {
474
2/2
✓ Branch 0 taken 8942564 times.
✓ Branch 1 taken 37197 times.
 17922325 return ((lbm_uint)ptr >= (lbm_uint)memory &&
475
1/2
✓ Branch 0 taken 8942564 times.
✗ Branch 1 not taken.
 8942564 (lbm_uint)ptr < (lbm_uint)memory + (memory_size * sizeof(lbm_uint)));
476 }
477