GCC Code Coverage Report
Directory: ../src/ Exec Total Coverage
File: /home/joels/Current/lispbm/src/lbm_memory.c Lines: 228 254 89.8 %
Date: 2025-04-14 11:29:35 Branches: 96 133 72.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 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
43848
int lbm_memory_init(lbm_uint *data, lbm_uint data_size,
55
                    lbm_uint *bits, lbm_uint bits_size) {
56
57
43848
  if (!lbm_mem_mutex_initialized) {
58
21924
    mutex_init(&lbm_mem_mutex);
59
21924
    lbm_mem_mutex_initialized = true;
60
  }
61
62
43848
  alloc_offset = 0;
63
64
43848
  mutex_lock(&lbm_mem_mutex);
65
43848
  int res = 0;
66

43848
  if (data == NULL || bits == NULL) return 0;
67
68
43848
  if (((lbm_uint)data % sizeof(lbm_uint) != 0) ||
69
43848
      (data_size * 2) != (bits_size * sizeof(lbm_uint) * 8) ||
70
43848
      data_size % 4 != 0 ||
71

43848
      ((lbm_uint)bits % sizeof(lbm_uint) != 0) ||
72
43848
      bits_size < 1 ||
73
43848
      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
43848
    bitmap = bits;
80
43848
    bitmap_size = bits_size;
81
82
11268936
    for (lbm_uint i = 0; i < bitmap_size; i ++) {
83
11225088
      bitmap[i] = 0;
84
    }
85
86
43848
    memory = data;
87
43848
    memory_base_address = (lbm_uint)data;
88
43848
    memory_size = data_size;
89
43848
    memory_min_free = data_size;
90
43848
    memory_num_free = data_size;
91
43848
    memory_reserve_level = (lbm_uint)(0.1 * (lbm_float)data_size);
92
43848
    res = 1;
93
  }
94
43848
  mutex_unlock(&lbm_mem_mutex);
95
43848
  return res;
96
}
97
98
void lbm_memory_set_reserve(lbm_uint num_words) {
99
  memory_reserve_level = num_words;
100
}
101
102
lbm_uint lbm_memory_get_reserve(void) {
103
  return memory_reserve_level;
104
}
105
106
10272740
static inline lbm_uint address_to_bitmap_ix(lbm_uint *ptr) {
107
  #ifndef LBM64
108
10272740
  return ((lbm_uint)ptr - memory_base_address) >> 2;
109
  #else
110
  return ((lbm_uint)ptr - memory_base_address) >> 3;
111
  #endif
112
}
113
114
22988
lbm_int lbm_memory_address_to_ix(lbm_uint *ptr) {
115
  /* TODO: assuming that index
116
           will have more then enough room in the
117
           positive half of a 28bit integer */
118
22988
  return (lbm_int)address_to_bitmap_ix(ptr);
119
}
120
121
122
10405319
static inline lbm_uint *bitmap_ix_to_address(lbm_uint ix) {
123
10405319
  return &((lbm_uint*)(memory_base_address))[ix];// + (ix << 2));
124
}
125
126
#ifndef LBM64
127
#define WORD_IX_SHIFT 5
128
#define WORD_MOD_MASK 0x1F
129
#define BITMAP_SIZE_SHIFT 4  // 16 statuses per bitmap word
130
#else
131
#define WORD_IX_SHIFT 6      // divide by 64
132
#define WORD_MOD_MASK 0x3F   // mod 64
133
#define BITMAP_SIZE_SHIFT 5  // times 32, 32 statuses per bitmap word
134
#endif
135
136
322188216
static inline lbm_uint status(lbm_uint i) {
137
138
322188216
  lbm_uint ix = i << 1;                      // * 2
139
322188216
  lbm_uint word_ix = ix >> WORD_IX_SHIFT;    // / 32
140
322188216
  lbm_uint bit_ix  = ix & WORD_MOD_MASK;              // % 32
141
142
322188216
  lbm_uint mask = ((lbm_uint)3) << bit_ix;       // 000110..0
143
322188216
  if (word_ix > bitmap_size) {
144
    return (lbm_uint)NULL;
145
  }
146
322188216
  return (bitmap[word_ix] & mask) >> bit_ix;
147
}
148
149
41169022
static inline void set_status(lbm_uint i, lbm_uint status) {
150
41169022
  lbm_uint ix = i << 1;          // * 2
151
41169022
  lbm_uint word_ix = ix >> WORD_IX_SHIFT;    // / 32
152
41169022
  lbm_uint bit_ix  = ix & WORD_MOD_MASK;  // % 32
153
154
41169022
  lbm_uint clr_mask = ~(((lbm_uint)3) << bit_ix);
155
41169022
  lbm_uint mask = status << bit_ix;
156
157
41169022
  bitmap[word_ix] &= clr_mask;
158
41169022
  bitmap[word_ix] |= mask;
159
41169022
}
160
161
28
lbm_uint lbm_memory_num_words(void) {
162
28
  return memory_size;
163
}
164
165
44912
lbm_uint lbm_memory_num_free(void) {
166
44912
  return memory_num_free;
167
}
168
169
lbm_uint lbm_memory_maximum_used(void) {
170
  return (memory_size - memory_min_free);
171
}
172
173
614552
void lbm_memory_update_min_free(void) {
174
614552
  if (memory_num_free < memory_min_free)
175
3112
    memory_min_free = memory_num_free;
176
614552
}
177
178
3960
lbm_uint lbm_memory_longest_free(void) {
179

3960
  if (memory == NULL || bitmap == NULL) {
180
    return 0;
181
  }
182
3960
  mutex_lock(&lbm_mem_mutex);
183
3960
  unsigned int state = INIT;
184
3960
  lbm_uint max_length = 0;
185
186
3960
  lbm_uint curr_length = 0;
187
16224120
  for (unsigned int i = 0; i < (bitmap_size << BITMAP_SIZE_SHIFT); i ++) {
188
189

16220160
    switch(status(i)) {
190

16097776
    case FREE_OR_USED:
191
      switch (state) {
192
4702
      case INIT:
193
4702
        curr_length = 1;
194
4702
        if (curr_length > max_length) max_length = curr_length;
195
4702
        state = FREE_LENGTH_CHECK;
196
4702
        break;
197
12385500
      case FREE_LENGTH_CHECK:
198
12385500
        curr_length ++;
199
12385500
        if (curr_length > max_length) max_length = curr_length;
200
12385500
        state = FREE_LENGTH_CHECK;
201
12385500
        break;
202
3707574
      case SKIP:
203
3707574
        break;
204
      }
205
16097776
      break;
206
59176
    case END:
207
59176
      state = INIT;
208
59176
      break;
209
59176
    case START:
210
59176
      state = SKIP;
211
59176
      break;
212
4032
    case START_END:
213
4032
      state = INIT;
214
4032
      break;
215
    default:
216
      mutex_unlock(&lbm_mem_mutex);
217
      return 0;
218
      break;
219
    }
220
  }
221
3960
  mutex_unlock(&lbm_mem_mutex);
222
3960
  if (memory_num_free - max_length < memory_reserve_level) {
223
3960
    lbm_uint n = memory_reserve_level - (memory_num_free - max_length);
224
3960
    max_length -= n;
225
  }
226
3960
  return max_length;
227
}
228
229
10410975
static lbm_uint *lbm_memory_allocate_internal(lbm_uint num_words) {
230
231

10410975
  if (memory == NULL || bitmap == NULL) {
232
    return NULL;
233
  }
234
235
10410975
  mutex_lock(&lbm_mem_mutex);
236
237
10410975
  lbm_uint start_ix = 0;
238
10410975
  lbm_uint end_ix = 0;
239
10410975
  lbm_uint free_length = 0;
240
10410975
  unsigned int state = INIT;
241
10410975
  lbm_uint loop_max = (bitmap_size << BITMAP_SIZE_SHIFT);
242
243
103833427
  for (lbm_uint i = 0; i < loop_max; i ++) {
244

103827771
    switch(status(alloc_offset)) {
245

93357727
    case FREE_OR_USED:
246
      switch (state) {
247
10415233
      case INIT:
248
10415233
        start_ix = alloc_offset;
249
10415233
        if (num_words == 1) {
250
73354
          end_ix = alloc_offset;
251
73354
          state = ALLOC_DONE;
252
        } else {
253
10341879
          state = FREE_LENGTH_CHECK;
254
10341879
          free_length = 1;
255
        }
256
10415233
        break;
257
63949456
      case FREE_LENGTH_CHECK:
258
63949456
        free_length ++;
259
63949456
        if (free_length == num_words) {
260
10331965
          end_ix = alloc_offset;
261
10331965
          state = ALLOC_DONE;
262
        } else {
263
53617491
          state = FREE_LENGTH_CHECK;
264
        }
265
63949456
        break;
266
18993038
      case SKIP:
267
18993038
        break;
268
      }
269
93357727
      break;
270
10324154
    case END:
271
10324154
      state = INIT;
272
10324154
      break;
273
71532
    case START:
274
71532
      state = SKIP;
275
71532
      break;
276
74358
    case START_END:
277
74358
      state = INIT;
278
74358
      break;
279
    default: // error case
280
      mutex_unlock(&lbm_mem_mutex);
281
      return NULL;
282
    }
283
284
103827771
    if (state == ALLOC_DONE) break;
285
286
93422452
    alloc_offset++;
287
93422452
    if (alloc_offset == loop_max ) {
288
5664
      free_length = 0;
289
5664
      alloc_offset = 0;
290
5664
      state = INIT;
291
    }
292
  }
293
294
10410975
  if (state == ALLOC_DONE) {
295
10405319
    if (start_ix == end_ix) {
296
73354
      set_status(start_ix, START_END);
297
    } else {
298
10331965
      set_status(start_ix, START);
299
10331965
      set_status(end_ix, END);
300
    }
301
10405319
    memory_num_free -= num_words;
302
10405319
    mutex_unlock(&lbm_mem_mutex);
303
10405319
    return bitmap_ix_to_address(start_ix);
304
  }
305
5656
  mutex_unlock(&lbm_mem_mutex);
306
5656
  return NULL;
307
}
308
309
46200
lbm_uint *lbm_memory_allocate(lbm_uint num_words) {
310
46200
  if (memory_num_free - num_words < memory_reserve_level) {
311
    lbm_request_gc();
312
    return NULL;
313
  }
314
46200
  return lbm_memory_allocate_internal(num_words);
315
}
316
317
10287965
int lbm_memory_free(lbm_uint *ptr) {
318
10287965
  int r = 0;
319
10287965
  if (lbm_memory_ptr_inside(ptr)) {
320
10239723
    mutex_lock(&lbm_mem_mutex);
321
10239723
    lbm_uint ix = address_to_bitmap_ix(ptr);
322
10239723
    lbm_uint count_freed = 0;
323
10239723
    alloc_offset = ix;
324
10239723
    switch(status(ix)) {
325
10171957
    case START:
326
10171957
      set_status(ix, FREE_OR_USED);
327
50716800
      for (lbm_uint i = ix; i < (bitmap_size << BITMAP_SIZE_SHIFT); i ++) {
328
50716800
        count_freed ++;
329
50716800
        if (status(i) == END) {
330
10171957
          set_status(i, FREE_OR_USED);
331
10171957
          r = 1;
332
10171957
          break;
333
        }
334
      }
335
10171957
      break;
336
67766
    case START_END:
337
67766
      set_status(ix, FREE_OR_USED);
338
67766
      count_freed = 1;
339
67766
      r = 1;
340
67766
      break;
341
    default:
342
      break;
343
    }
344
10239723
    if (r) {
345

131970881
      while (alloc_offset > 0 && status(alloc_offset - 1) == FREE_OR_USED) {
346
121731158
        alloc_offset--;
347
      }
348
    }
349
10239723
    memory_num_free += count_freed;
350
10239723
    mutex_unlock(&lbm_mem_mutex);
351
  }
352
10287965
  return r;
353
}
354
//Malloc/free like interface
355
10320730
void* lbm_malloc(size_t size) {
356
10320730
  if (size == 0) return NULL;
357
  lbm_uint alloc_size;
358
359
10320730
  alloc_size = size / sizeof(lbm_uint);
360
10320730
  if (size % sizeof(lbm_uint)) alloc_size += 1;
361
362
10320730
  if (memory_num_free - alloc_size < memory_reserve_level) {
363
5014
    lbm_request_gc();
364
5014
    return NULL;
365
  }
366
10315716
  return lbm_memory_allocate_internal(alloc_size);
367
}
368
369
49059
void* lbm_malloc_reserve(size_t size) {
370
49059
  if (size == 0) return NULL;
371
  lbm_uint alloc_size;
372
373
49059
  alloc_size = size / sizeof(lbm_uint);
374
49059
  if (size % sizeof(lbm_uint)) alloc_size += 1;
375
376
49059
  if (memory_num_free - alloc_size < memory_reserve_level) {
377
114
    lbm_request_gc();
378
  }
379
49059
  return lbm_memory_allocate_internal(alloc_size);
380
}
381
382
38671
void lbm_free(void *ptr) {
383
38671
  lbm_memory_free(ptr);
384
38671
}
385
386
10029
int lbm_memory_shrink(lbm_uint *ptr, lbm_uint n) {
387

10029
  if (!lbm_memory_ptr_inside(ptr) || n == 0) return 0;
388
389
10029
  lbm_uint ix = address_to_bitmap_ix(ptr);
390
391
10029
  mutex_lock(&lbm_mem_mutex);
392
10029
  if (status(ix) == START_END) {
393
    mutex_unlock(&lbm_mem_mutex);
394
    return 1; // A one word arrays always succeeds at remaining at 1 word
395
  }
396
10029
  if (status(ix) != START) {
397
    mutex_unlock(&lbm_mem_mutex);
398
    return 0; // ptr does not point to the start of an allocated range.
399
  }
400
401
10029
  bool done = false;
402
10029
  unsigned int i = 0;
403
404
115818
  for (i = 0; i < ((bitmap_size << BITMAP_SIZE_SHIFT) - ix); i ++) {
405

115818
    if (status(ix+i) == END && i < n) {
406
      mutex_unlock(&lbm_mem_mutex);
407
      return 0; // cannot shrink allocation to a larger size
408
    }
409
410
115818
    if (i == (n-1)) {
411

20058
      if (status(ix+i) == END ||
412
10029
          status(ix+i) == START_END) {
413
        done = true;
414
      }
415
10029
      if (i == 0) {
416
1176
        set_status(ix+i, START_END);
417
      }
418
      else {
419
8853
        set_status(ix+i, END);
420
      }
421
10029
      break;
422
    }
423
  }
424
10029
  alloc_offset = ix+i;
425
426
10029
  lbm_uint count = 0;
427
10029
  if (!done) {
428
10029
    i++; // move to next position, prev position should be END or START_END
429
9057031
    for (;i < ((bitmap_size << BITMAP_SIZE_SHIFT) - ix); i ++) {
430
9057031
      count ++;
431
9057031
      if (status(ix+i) == END) {
432
10029
        set_status(ix+i, FREE_OR_USED);
433
10029
        break;
434
      }
435
    }
436
  }
437
438
10029
  memory_num_free += count;
439
10029
  mutex_unlock(&lbm_mem_mutex);
440
10029
  return 1;
441
}
442
443
10297994
int lbm_memory_ptr_inside(lbm_uint *ptr) {
444
20547746
  return ((lbm_uint)ptr >= (lbm_uint)memory &&
445
10249752
          (lbm_uint)ptr < (lbm_uint)memory + (memory_size * sizeof(lbm_uint)));
446
}