| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | Copyright 2024, 2025 Joel Svensson svenssonjoel@yahoo.se | ||
| 3 | |||
| 4 | This program is free software: you can redistribute it and/or modify | ||
| 5 | it under the terms of the GNU General Public License as published by | ||
| 6 | the Free Software Foundation, either version 3 of the License, or | ||
| 7 | (at your option) any later version. | ||
| 8 | |||
| 9 | This program is distributed in the hope that it will be useful, | ||
| 10 | but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
| 11 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
| 12 | GNU General Public License for more details. | ||
| 13 | |||
| 14 | You should have received a copy of the GNU General Public License | ||
| 15 | along with this program. If not, see <http://www.gnu.org/licenses/>. | ||
| 16 | */ | ||
| 17 | |||
| 18 | #include <lbm_defrag_mem.h> | ||
| 19 | #include <heap.h> | ||
| 20 | #include <lbm_memory.h> | ||
| 21 | |||
| 22 | 678078 | static inline lbm_uint bs2ws(lbm_uint bs) { | |
| 23 |
2/2✓ Branch 0 taken 648145 times.
✓ Branch 1 taken 29933 times.
|
678078 | return bs % sizeof(lbm_uint) == 0 ? bs / sizeof(lbm_uint) : (bs / sizeof(lbm_uint)) + 1; |
| 24 | } | ||
| 25 | |||
| 26 | #define DEFRAG_MEM_HEADER_SIZE 2 | ||
| 27 | #define DEFRAG_MEM_HEADER_BYTES (DEFRAG_MEM_HEADER_SIZE*sizeof(lbm_uint)) | ||
| 28 | #define DEFRAG_MEM_DATA(X) &(X)[DEFRAG_MEM_HEADER_SIZE]; | ||
| 29 | // length and flags. | ||
| 30 | // Currently only one flag that tells if we should do a compaction before allocation. | ||
| 31 | #define DEFRAG_MEM_SIZE(X) X[0] | ||
| 32 | #define DEFRAG_MEM_FLAGS(X) X[1] | ||
| 33 | |||
| 34 | // TODO: We can move the GC index to the end (or elsewhere) of an array to save space in these | ||
| 35 | // headers in the case of ByteArrays. | ||
| 36 | #define DEFRAG_ALLOC_SIZE(X) X[0] | ||
| 37 | #define DEFRAG_ALLOC_DATA(X) X[1] | ||
| 38 | //#define DEFRAG_ALLOC_INDEX(X) X[2] // GC index for traversal of high-level arrays | ||
| 39 | #define DEFRAG_ALLOC_CELLPTR(X) X[2] | ||
| 40 | #define DEFRAG_ALLOC_ARRAY_HEADER_SIZE 3 | ||
| 41 | |||
| 42 | 337 | lbm_value lbm_defrag_mem_create(lbm_uint nbytes) { | |
| 43 | 337 | lbm_value res = ENC_SYM_TERROR; | |
| 44 | 337 | lbm_uint nwords = bs2ws(nbytes); // multiple of 4. | |
| 45 |
1/2✓ Branch 0 taken 337 times.
✗ Branch 1 not taken.
|
337 | if (nwords > 0) { |
| 46 | 337 | res = ENC_SYM_MERROR; | |
| 47 | 337 | lbm_uint *data = (lbm_uint*)lbm_malloc(DEFRAG_MEM_HEADER_BYTES + nwords * sizeof(lbm_uint)); | |
| 48 |
1/2✓ Branch 0 taken 337 times.
✗ Branch 1 not taken.
|
337 | if (data) { |
| 49 | 337 | memset((uint8_t*)data , 0, DEFRAG_MEM_HEADER_BYTES + nwords*sizeof(lbm_uint)); | |
| 50 | 337 | data[0] = nwords; | |
| 51 | 337 | data[1] = 0; //flags | |
| 52 | 337 | lbm_value cell = lbm_heap_allocate_cell(LBM_TYPE_DEFRAG_MEM, (lbm_uint)data, ENC_SYM_DEFRAG_MEM_TYPE); | |
| 53 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 337 times.
|
337 | if (cell == ENC_SYM_MERROR) { |
| 54 | ✗ | lbm_free(data); | |
| 55 | } else { | ||
| 56 | 337 | res = cell; | |
| 57 | } | ||
| 58 | } | ||
| 59 | } | ||
| 60 | 337 | return res; | |
| 61 | } | ||
| 62 | |||
| 63 | 196 | static void free_defrag_allocation(lbm_uint *allocation) { | |
| 64 | 196 | lbm_uint size = DEFRAG_ALLOC_SIZE(allocation); // array allocation is size in bytes | |
| 65 | // a defrag-mem allocation is always bigger than 0 | ||
| 66 | 196 | lbm_uint nwords = bs2ws(size) + DEFRAG_ALLOC_ARRAY_HEADER_SIZE; | |
| 67 | 196 | lbm_value cell_back_ptr = DEFRAG_ALLOC_CELLPTR(allocation); | |
| 68 | |||
| 69 | // I have a feeling that it should be impossible for the | ||
| 70 | // cell to be recovered if we end up here. | ||
| 71 | // if the cell is recovered, then the data should also have been | ||
| 72 | // cleared in the defrag_mem. | ||
| 73 | |||
| 74 | 196 | cell_back_ptr = lbm_set_ptr_type(cell_back_ptr, LBM_TYPE_CONS); | |
| 75 | 196 | bool marked = lbm_cdr(cell_back_ptr) & LBM_GC_MASK; | |
| 76 |
2/2✓ Branch 0 taken 168 times.
✓ Branch 1 taken 28 times.
|
196 | lbm_value new_cdr = marked ? (ENC_SYM_NIL | LBM_GC_MARKED) : ENC_SYM_NIL; |
| 77 | 196 | lbm_set_car_and_cdr(cell_back_ptr, ENC_SYM_NIL, new_cdr); | |
| 78 | // possible optimize, if not marked. dont bother setting anything. | ||
| 79 | |||
| 80 |
2/2✓ Branch 0 taken 1064 times.
✓ Branch 1 taken 196 times.
|
1260 | for (lbm_uint i = 0; i < nwords; i ++) { |
| 81 | 1064 | allocation[i] = 0; | |
| 82 | } | ||
| 83 | 196 | } | |
| 84 | |||
| 85 | // Called by GC. | ||
| 86 | // As it is called by GC, gc bits may be set and needs to be | ||
| 87 | // honored! | ||
| 88 | 56 | void lbm_defrag_mem_destroy(lbm_uint *defrag_mem) { | |
| 89 | 56 | lbm_uint nwords = DEFRAG_MEM_SIZE(defrag_mem); | |
| 90 | 56 | lbm_uint *defrag_data = DEFRAG_MEM_DATA(defrag_mem); | |
| 91 |
2/2✓ Branch 0 taken 532 times.
✓ Branch 1 taken 56 times.
|
588 | for (lbm_uint i = 0; i < nwords;) { |
| 92 | 532 | lbm_uint a = defrag_data[i]; | |
| 93 |
2/2✓ Branch 0 taken 196 times.
✓ Branch 1 taken 336 times.
|
532 | if (a != 0) { |
| 94 | 196 | lbm_uint *allocation = &defrag_data[i]; | |
| 95 | 196 | lbm_uint alloc_words = | |
| 96 | DEFRAG_ALLOC_ARRAY_HEADER_SIZE + | ||
| 97 | 196 | bs2ws(DEFRAG_ALLOC_SIZE(allocation)); | |
| 98 | 196 | free_defrag_allocation(allocation); | |
| 99 | 196 | i += alloc_words; | |
| 100 | } | ||
| 101 | 336 | else i ++; | |
| 102 | } | ||
| 103 | 56 | lbm_free(defrag_mem); | |
| 104 | 56 | } | |
| 105 | |||
| 106 | |||
| 107 | 57036 | static void lbm_defrag_mem_defrag(lbm_uint *defrag_mem, lbm_uint bytes) { | |
| 108 | 57036 | lbm_uint mem_size = ((lbm_uint*)defrag_mem)[0]; // mem size words | |
| 109 | 57036 | lbm_uint *mem_data = DEFRAG_MEM_DATA(defrag_mem); | |
| 110 | 57036 | lbm_uint hole_start = 0; | |
| 111 | |||
| 112 | 57036 | lbm_uint until_size = DEFRAG_ALLOC_ARRAY_HEADER_SIZE + bs2ws(bytes); // defrag until hole is this size or complete defrag. | |
| 113 | |||
| 114 |
2/2✓ Branch 0 taken 292208 times.
✓ Branch 1 taken 56952 times.
|
349160 | for (lbm_uint i = 0; i < mem_size; ) { |
| 115 | // check if there is an allocation here | ||
| 116 |
2/2✓ Branch 0 taken 117488 times.
✓ Branch 1 taken 174720 times.
|
292208 | if (mem_data[i] != 0) { |
| 117 | 117488 | lbm_uint *source = &mem_data[i]; | |
| 118 | 117488 | lbm_uint *target = &mem_data[hole_start]; | |
| 119 | 117488 | lbm_uint alloc_bytes = DEFRAG_ALLOC_SIZE(source); | |
| 120 | 117488 | lbm_uint alloc_words = bs2ws(alloc_bytes); | |
| 121 | // move allocation into hole | ||
| 122 |
2/2✓ Branch 0 taken 116984 times.
✓ Branch 1 taken 504 times.
|
117488 | if (hole_start == i) { |
| 123 | 116984 | i += alloc_words + DEFRAG_ALLOC_ARRAY_HEADER_SIZE; | |
| 124 | 116984 | hole_start = i; | |
| 125 | } else { | ||
| 126 | 504 | lbm_uint move_dist = i - hole_start; | |
| 127 |
2/2✓ Branch 0 taken 84 times.
✓ Branch 1 taken 420 times.
|
504 | if (move_dist >= until_size) break; |
| 128 | 420 | lbm_uint clear_ix = (hole_start + alloc_words + DEFRAG_ALLOC_ARRAY_HEADER_SIZE); | |
| 129 | 420 | memmove(target, source, (alloc_words + DEFRAG_ALLOC_ARRAY_HEADER_SIZE) * sizeof(lbm_uint)); | |
| 130 | 420 | memset(&mem_data[clear_ix],0, move_dist* sizeof(lbm_uint)); | |
| 131 | 420 | DEFRAG_ALLOC_DATA(target) = (lbm_uint)&target[DEFRAG_ALLOC_ARRAY_HEADER_SIZE]; | |
| 132 | 420 | lbm_value cell = DEFRAG_ALLOC_CELLPTR(target); | |
| 133 | |||
| 134 | 420 | lbm_set_car(cell,(lbm_uint)target); | |
| 135 | // move home and i forwards. | ||
| 136 | // i can move to the original end of allocation. | ||
| 137 | 420 | hole_start += alloc_words + DEFRAG_ALLOC_ARRAY_HEADER_SIZE; | |
| 138 | 420 | i += alloc_words + DEFRAG_ALLOC_ARRAY_HEADER_SIZE; | |
| 139 | } | ||
| 140 | } else { | ||
| 141 | // no allocation hole remains but i increments. | ||
| 142 | 174720 | i ++; | |
| 143 | } | ||
| 144 | } | ||
| 145 | 57036 | } | |
| 146 | |||
| 147 | // Allocate an array from the defragable pool | ||
| 148 | // these arrays must be recognizable by GC so that | ||
| 149 | // gc can free them by performing a call into the defrag_mem api. | ||
| 150 | // At the same time they need to be just bytearrays.. | ||
| 151 | // Allocation must always scan from start. | ||
| 152 | // | ||
| 153 | |||
| 154 | #define INIT 0 | ||
| 155 | #define FREE_LEN 1 | ||
| 156 | |||
| 157 | // An array allocated in defragmem has the following layout inside of the defrag mem | ||
| 158 | // | ||
| 159 | // [header (size, data-ptr) cell_back_ptr | data | padding ] | ||
| 160 | |||
| 161 | 173209 | lbm_value lbm_defrag_mem_alloc_internal(lbm_uint *defrag_mem, lbm_uint bytes, lbm_uint type) { | |
| 162 | |||
| 163 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 173209 times.
|
173209 | if (bytes == 0) return ENC_SYM_EERROR; |
| 164 | 173209 | lbm_value cell = lbm_heap_allocate_cell(LBM_TYPE_CONS, ENC_SYM_NIL, type); | |
| 165 | |||
| 166 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 173209 times.
|
173209 | if (cell == ENC_SYM_MERROR) { |
| 167 | ✗ | return cell; | |
| 168 | } | ||
| 169 | |||
| 170 | 173209 | lbm_uint mem_size = DEFRAG_MEM_SIZE(defrag_mem); | |
| 171 | 173209 | lbm_uint *mem_data = DEFRAG_MEM_DATA(defrag_mem); | |
| 172 | |||
| 173 | 173209 | lbm_uint num_words = bs2ws(bytes); | |
| 174 | 173209 | lbm_uint alloc_words = num_words + DEFRAG_ALLOC_ARRAY_HEADER_SIZE; | |
| 175 | |||
| 176 | 173209 | uint8_t state = INIT; | |
| 177 | 173209 | lbm_uint free_words = 0; | |
| 178 | 173209 | lbm_uint free_start = 0; | |
| 179 | 173209 | bool alloc_found = false; | |
| 180 | 173209 | lbm_value res = ENC_SYM_MERROR; | |
| 181 | |||
| 182 |
2/2✓ Branch 0 taken 1229479 times.
✓ Branch 1 taken 113904 times.
|
1343383 | for (lbm_uint i = 0; i < mem_size;) { |
| 183 |
2/3✓ Branch 0 taken 388501 times.
✓ Branch 1 taken 840978 times.
✗ Branch 2 not taken.
|
1229479 | switch(state) { |
| 184 | 388501 | case INIT: | |
| 185 |
2/2✓ Branch 0 taken 116873 times.
✓ Branch 1 taken 271628 times.
|
388501 | if (mem_data[i] == 0) { |
| 186 | 116873 | free_start = i; | |
| 187 | 116873 | free_words = 1; | |
| 188 | 116873 | state = FREE_LEN; | |
| 189 | 116873 | i++; | |
| 190 | } else { | ||
| 191 | // jump to next spot | ||
| 192 | 271628 | i += bs2ws(mem_data[i]) + DEFRAG_ALLOC_ARRAY_HEADER_SIZE; | |
| 193 | } | ||
| 194 | 388501 | break; | |
| 195 | 840978 | case FREE_LEN: | |
| 196 |
2/2✓ Branch 0 taken 840754 times.
✓ Branch 1 taken 224 times.
|
840978 | if (mem_data[i] == 0) { |
| 197 | 840754 | free_words ++; | |
| 198 |
2/2✓ Branch 0 taken 59305 times.
✓ Branch 1 taken 781449 times.
|
840754 | if (free_words >= alloc_words) { |
| 199 | 59305 | alloc_found = true; | |
| 200 | } else { | ||
| 201 | 781449 | i ++; | |
| 202 | } | ||
| 203 | } else { | ||
| 204 | 224 | state = INIT; | |
| 205 | 224 | i++; | |
| 206 | } | ||
| 207 | 840978 | break; | |
| 208 | } | ||
| 209 |
2/2✓ Branch 0 taken 59305 times.
✓ Branch 1 taken 1170174 times.
|
1229479 | if (alloc_found) break; |
| 210 | } | ||
| 211 |
2/2✓ Branch 0 taken 59305 times.
✓ Branch 1 taken 113904 times.
|
173209 | if (alloc_found) { |
| 212 | 59305 | lbm_uint *allocation = (lbm_uint*)&mem_data[free_start]; | |
| 213 | 59305 | DEFRAG_ALLOC_SIZE(allocation) = bytes; | |
| 214 | 59305 | DEFRAG_ALLOC_DATA(allocation) = (lbm_uint)&allocation[DEFRAG_ALLOC_ARRAY_HEADER_SIZE]; //data starts after back_ptr | |
| 215 | 59305 | DEFRAG_ALLOC_CELLPTR(allocation) = cell; | |
| 216 | 59305 | lbm_set_car(cell, (lbm_uint)allocation); | |
| 217 | 59305 | res = cell; | |
| 218 | } else { | ||
| 219 | 113904 | DEFRAG_MEM_FLAGS(defrag_mem) = 1; | |
| 220 | 113904 | lbm_set_car_and_cdr(cell, ENC_SYM_NIL, ENC_SYM_NIL); | |
| 221 | } | ||
| 222 | 173209 | return res; | |
| 223 | } | ||
| 224 | |||
| 225 | 116173 | lbm_value lbm_defrag_mem_alloc(lbm_uint *defrag_mem, lbm_uint bytes) { | |
| 226 | |||
| 227 | 116173 | lbm_value res = lbm_defrag_mem_alloc_internal(defrag_mem, bytes, ENC_SYM_DEFRAG_ARRAY_TYPE); // Try to allocate | |
| 228 |
2/2✓ Branch 0 taken 57036 times.
✓ Branch 1 taken 59137 times.
|
116173 | if (lbm_is_symbol_merror(res)) { |
| 229 |
1/2✓ Branch 0 taken 57036 times.
✗ Branch 1 not taken.
|
57036 | if (DEFRAG_MEM_FLAGS(defrag_mem)) { //if we already performed GC, then also defrag |
| 230 | 57036 | lbm_defrag_mem_defrag(defrag_mem, bytes); | |
| 231 | 57036 | res = lbm_defrag_mem_alloc_internal(defrag_mem, bytes, ENC_SYM_DEFRAG_ARRAY_TYPE); // then try again | |
| 232 | 57036 | DEFRAG_MEM_FLAGS(defrag_mem) = 0; | |
| 233 | } | ||
| 234 | } | ||
| 235 |
2/2✓ Branch 0 taken 59305 times.
✓ Branch 1 taken 56868 times.
|
116173 | if (!lbm_is_symbol_merror(res)) { |
| 236 | 59305 | res = lbm_set_ptr_type(res, LBM_TYPE_ARRAY); | |
| 237 | } | ||
| 238 | 116173 | return res; | |
| 239 | } | ||
| 240 | |||
| 241 | // Allocate a high-level array from DM area | ||
| 242 | /* lbm_value lbm_defrag_mem_alloc_lisparray(lbm_uint *defrag_mem, lbm_uint elts) { */ | ||
| 243 | |||
| 244 | /* size_t bytes = elts * sizeof(lbm_uint); */ | ||
| 245 | /* lbm_value res = lbm_defrag_mem_alloc_internal(defrag_mem, bytes, ENC_SYM_DEFRAG_LISPARRAY_TYPE); // Try to allocate */ | ||
| 246 | /* if (lbm_is_symbol_merror(res)) { */ | ||
| 247 | /* if (DEFRAG_MEM_FLAGS(defrag_mem)) { //if we already performed GC, then also defrag */ | ||
| 248 | /* lbm_defrag_mem_defrag(defrag_mem, bytes); */ | ||
| 249 | /* res = lbm_defrag_mem_alloc_internal(defrag_mem, bytes, ENC_SYM_DEFRAG_LISPARRAY_TYPE); // then try again */ | ||
| 250 | /* DEFRAG_MEM_FLAGS(defrag_mem) = 0; */ | ||
| 251 | /* } */ | ||
| 252 | /* } */ | ||
| 253 | /* if (!lbm_is_symbol_merror(res)) { */ | ||
| 254 | /* res = lbm_set_ptr_type(res, LBM_TYPE_LISPARRAY); */ | ||
| 255 | /* } */ | ||
| 256 | /* return res; */ | ||
| 257 | /* } */ | ||
| 258 | |||
| 259 | |||
| 260 | |||
| 261 | // IF GC frees a defrag allocation, the cell pointing to it will also be destroyed by GC. | ||
| 262 | |||
| 263 | // is it guaranteed there are no copies of a heap-cell representing a defrag allocation. | ||
| 264 | // Same guarantee must hold for arrays in general or it would not be possible to explicitly free | ||
| 265 | // any array. | ||
| 266 | |||
| 267 | // At the time of free from GC all we have is the pointer. | ||
| 268 | 57988 | void lbm_defrag_mem_free(lbm_uint* data) { | |
| 269 | 57988 | lbm_uint nbytes = data[0]; | |
| 270 | 57988 | lbm_uint words_to_wipe = DEFRAG_ALLOC_ARRAY_HEADER_SIZE + bs2ws(nbytes); | |
| 271 |
2/2✓ Branch 0 taken 598948 times.
✓ Branch 1 taken 57988 times.
|
656936 | for (lbm_uint i = 0; i < words_to_wipe; i ++) { |
| 272 | 598948 | data[i] = 0; | |
| 273 | } | ||
| 274 | 57988 | } | |
| 275 | |||
| 276 |