| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | Copyright 2024 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 | 17668 | static inline lbm_uint bs2ws(lbm_uint bs) { | |
| 23 |
2/2✓ Branch 0 taken 4340 times.
✓ Branch 1 taken 13328 times.
|
17668 | 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 (2*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 | #define DEFRAG_ALLOC_SIZE(X) X[0] | ||
| 35 | #define DEFRAG_ALLOC_DATA(X) X[1] | ||
| 36 | #define DEFRAG_ALLOC_CELLPTR(X) X[2] | ||
| 37 | |||
| 38 | 140 | lbm_value lbm_defrag_mem_create(lbm_uint nbytes) { | |
| 39 | 140 | lbm_value res = ENC_SYM_TERROR; | |
| 40 | 140 | lbm_uint nwords = bs2ws(nbytes); // multiple of 4. | |
| 41 |
1/2✓ Branch 0 taken 140 times.
✗ Branch 1 not taken.
|
140 | if (nwords > 0) { |
| 42 | 140 | res = ENC_SYM_MERROR; | |
| 43 | 140 | lbm_uint *data = (lbm_uint*)lbm_malloc(DEFRAG_MEM_HEADER_BYTES + nwords * sizeof(lbm_uint)); | |
| 44 |
1/2✓ Branch 0 taken 140 times.
✗ Branch 1 not taken.
|
140 | if (data) { |
| 45 | 140 | memset((uint8_t*)data , 0, DEFRAG_MEM_HEADER_BYTES + nwords*sizeof(lbm_uint)); | |
| 46 | 140 | data[0] = nwords; | |
| 47 | 140 | data[1] = 0; //flags | |
| 48 | 140 | lbm_value cell = lbm_heap_allocate_cell(LBM_TYPE_DEFRAG_MEM, (lbm_uint)data, ENC_SYM_DEFRAG_MEM_TYPE); | |
| 49 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 140 times.
|
140 | if (cell == ENC_SYM_MERROR) { |
| 50 | ✗ | lbm_free(data); | |
| 51 | } else { | ||
| 52 | 140 | res = cell; | |
| 53 | } | ||
| 54 | } | ||
| 55 | } | ||
| 56 | 140 | return res; | |
| 57 | } | ||
| 58 | |||
| 59 | 84 | static void free_defrag_allocation(lbm_uint *allocation) { | |
| 60 | 84 | lbm_uint size = DEFRAG_ALLOC_SIZE(allocation); // array allocation is size in bytes | |
| 61 | // a defrag-mem allocation is always bigger than 0 | ||
| 62 | 84 | lbm_uint nwords = bs2ws(size) + 3; | |
| 63 | 84 | lbm_value cell_back_ptr = DEFRAG_ALLOC_CELLPTR(allocation); | |
| 64 | |||
| 65 | // I have a feeling that it should be impossible for the | ||
| 66 | // cell to be recovered if we end up here. | ||
| 67 | // if the cell is recovered, then the data should also have been | ||
| 68 | // cleared in the defrag_mem. | ||
| 69 | |||
| 70 | 84 | cell_back_ptr = lbm_set_ptr_type(cell_back_ptr, LBM_TYPE_CONS); | |
| 71 | 84 | bool marked = lbm_cdr(cell_back_ptr) & LBM_GC_MASK; | |
| 72 |
1/2✓ Branch 0 taken 84 times.
✗ Branch 1 not taken.
|
84 | lbm_value new_cdr = marked ? (ENC_SYM_NIL | LBM_GC_MARKED) : ENC_SYM_NIL; |
| 73 | 84 | lbm_set_car_and_cdr(cell_back_ptr, ENC_SYM_NIL, new_cdr); | |
| 74 | // possible optimize, if not marked. dont bother setting anything. | ||
| 75 | |||
| 76 |
2/2✓ Branch 0 taken 504 times.
✓ Branch 1 taken 84 times.
|
588 | for (lbm_uint i = 0; i < nwords; i ++) { |
| 77 | 504 | allocation[i] = 0; | |
| 78 | } | ||
| 79 | 84 | } | |
| 80 | |||
| 81 | // Called by GC. | ||
| 82 | // As it is called by GC, gc bits may be set and needs to be | ||
| 83 | // honored! | ||
| 84 | 28 | void lbm_defrag_mem_destroy(lbm_uint *defrag_mem) { | |
| 85 | 28 | lbm_uint nwords = DEFRAG_MEM_SIZE(defrag_mem); | |
| 86 | 28 | lbm_uint *defrag_data = DEFRAG_MEM_DATA(defrag_mem); | |
| 87 |
2/2✓ Branch 0 taken 280 times.
✓ Branch 1 taken 28 times.
|
308 | for (lbm_uint i = 0; i < nwords;) { |
| 88 | 280 | lbm_uint a = defrag_data[i]; | |
| 89 |
2/2✓ Branch 0 taken 84 times.
✓ Branch 1 taken 196 times.
|
280 | if (a != 0) { |
| 90 | 84 | lbm_uint *allocation = &defrag_data[i]; | |
| 91 | 84 | lbm_uint alloc_words = 3 + bs2ws(DEFRAG_ALLOC_SIZE(allocation)); | |
| 92 | 84 | free_defrag_allocation(allocation); | |
| 93 | 84 | i += alloc_words; | |
| 94 | } | ||
| 95 | 196 | else i ++; | |
| 96 | } | ||
| 97 | 28 | lbm_free(defrag_mem); | |
| 98 | 28 | } | |
| 99 | |||
| 100 | |||
| 101 | 616 | static void lbm_defrag_mem_defrag(lbm_uint *defrag_mem, lbm_uint bytes) { | |
| 102 | 616 | lbm_uint mem_size = ((lbm_uint*)defrag_mem)[0]; // mem size words | |
| 103 | 616 | lbm_uint *mem_data = DEFRAG_MEM_DATA(defrag_mem); | |
| 104 | 616 | lbm_uint hole_start = 0; | |
| 105 | |||
| 106 | 616 | lbm_uint until_size = bs2ws(bytes) + 3; // defrag until hole is this size or complete defrag. | |
| 107 | |||
| 108 |
2/2✓ Branch 0 taken 6916 times.
✓ Branch 1 taken 588 times.
|
7504 | for (lbm_uint i = 0; i < mem_size; ) { |
| 109 | // check if there is an allocation here | ||
| 110 |
2/2✓ Branch 0 taken 2828 times.
✓ Branch 1 taken 4088 times.
|
6916 | if (mem_data[i] != 0) { |
| 111 | 2828 | lbm_uint *source = &mem_data[i]; | |
| 112 | 2828 | lbm_uint *target = &mem_data[hole_start]; | |
| 113 | 2828 | lbm_uint alloc_bytes = DEFRAG_ALLOC_SIZE(source); | |
| 114 | 2828 | lbm_uint alloc_words = bs2ws(alloc_bytes); | |
| 115 | // move allocation into hole | ||
| 116 |
2/2✓ Branch 0 taken 2604 times.
✓ Branch 1 taken 224 times.
|
2828 | if (hole_start == i) { |
| 117 | 2604 | i += alloc_words+3; | |
| 118 | 2604 | hole_start = i; | |
| 119 | } else { | ||
| 120 | 224 | lbm_uint move_dist = i - hole_start; | |
| 121 |
2/2✓ Branch 0 taken 28 times.
✓ Branch 1 taken 196 times.
|
224 | if (move_dist >= until_size) break; |
| 122 | 196 | lbm_uint clear_ix = (hole_start + alloc_words + 3); | |
| 123 | 196 | memmove(target, source, (alloc_words + 3) * sizeof(lbm_uint)); | |
| 124 | 196 | memset(&mem_data[clear_ix],0, move_dist* sizeof(lbm_uint)); | |
| 125 | 196 | DEFRAG_ALLOC_DATA(target) = (lbm_uint)&target[3]; | |
| 126 | 196 | lbm_value cell = DEFRAG_ALLOC_CELLPTR(target); | |
| 127 | |||
| 128 | 196 | lbm_set_car(cell,(lbm_uint)target); | |
| 129 | // move home and i forwards. | ||
| 130 | // i can move to the original end of allocation. | ||
| 131 | 196 | hole_start += alloc_words + 3; | |
| 132 | 196 | i += alloc_words + 3; | |
| 133 | } | ||
| 134 | } else { | ||
| 135 | // no allocation hole remains but i increments. | ||
| 136 | 4088 | i ++; | |
| 137 | } | ||
| 138 | } | ||
| 139 | 616 | } | |
| 140 | |||
| 141 | // Allocate an array from the defragable pool | ||
| 142 | // these arrays must be recognizable by GC so that | ||
| 143 | // gc can free them by performing a call into the defrag_mem api. | ||
| 144 | // At the same time they need to be just bytearrays.. | ||
| 145 | // Allocation must always scan from start. | ||
| 146 | // | ||
| 147 | |||
| 148 | #define INIT 0 | ||
| 149 | #define FREE_LEN 1 | ||
| 150 | |||
| 151 | // An array allocated in defragmem has the following layout inside of the defrag mem | ||
| 152 | // | ||
| 153 | // [header (size, data-ptr) cell_back_ptr | data | padding ] | ||
| 154 | |||
| 155 | 2800 | lbm_value lbm_defrag_mem_alloc_internal(lbm_uint *defrag_mem, lbm_uint bytes) { | |
| 156 | |||
| 157 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2800 times.
|
2800 | if (bytes == 0) return ENC_SYM_EERROR; |
| 158 | 2800 | lbm_value cell = lbm_heap_allocate_cell(LBM_TYPE_CONS, ENC_SYM_NIL, ENC_SYM_DEFRAG_ARRAY_TYPE); | |
| 159 | |||
| 160 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2800 times.
|
2800 | if (cell == ENC_SYM_MERROR) { |
| 161 | ✗ | return cell; | |
| 162 | } | ||
| 163 | |||
| 164 | 2800 | lbm_uint mem_size = DEFRAG_MEM_SIZE(defrag_mem); | |
| 165 | 2800 | lbm_uint *mem_data = DEFRAG_MEM_DATA(defrag_mem); | |
| 166 | |||
| 167 | 2800 | lbm_uint num_words = bs2ws(bytes); | |
| 168 | 2800 | lbm_uint alloc_words = num_words + 3; | |
| 169 | |||
| 170 | 2800 | uint8_t state = INIT; | |
| 171 | 2800 | lbm_uint free_words = 0; | |
| 172 | 2800 | lbm_uint free_start = 0; | |
| 173 | 2800 | bool alloc_found = false; | |
| 174 | 2800 | lbm_value res = ENC_SYM_MERROR; | |
| 175 | |||
| 176 |
2/2✓ Branch 0 taken 30492 times.
✓ Branch 1 taken 1176 times.
|
31668 | for (lbm_uint i = 0; i < mem_size;) { |
| 177 |
2/3✓ Branch 0 taken 12880 times.
✓ Branch 1 taken 17612 times.
✗ Branch 2 not taken.
|
30492 | switch(state) { |
| 178 | 12880 | case INIT: | |
| 179 |
2/2✓ Branch 0 taken 2800 times.
✓ Branch 1 taken 10080 times.
|
12880 | if (mem_data[i] == 0) { |
| 180 | 2800 | free_start = i; | |
| 181 | 2800 | free_words = 1; | |
| 182 | 2800 | state = FREE_LEN; | |
| 183 | 2800 | i++; | |
| 184 | } else { | ||
| 185 | // jump to next spot | ||
| 186 | 10080 | i += bs2ws(mem_data[i]) + 3; | |
| 187 | } | ||
| 188 | 12880 | break; | |
| 189 | 17612 | case FREE_LEN: | |
| 190 |
2/2✓ Branch 0 taken 17528 times.
✓ Branch 1 taken 84 times.
|
17612 | if (mem_data[i] == 0) { |
| 191 | 17528 | free_words ++; | |
| 192 |
2/2✓ Branch 0 taken 1624 times.
✓ Branch 1 taken 15904 times.
|
17528 | if (free_words >= alloc_words) { |
| 193 | 1624 | alloc_found = true; | |
| 194 | } else { | ||
| 195 | 15904 | i ++; | |
| 196 | } | ||
| 197 | } else { | ||
| 198 | 84 | state = INIT; | |
| 199 | 84 | i++; | |
| 200 | } | ||
| 201 | 17612 | break; | |
| 202 | } | ||
| 203 |
2/2✓ Branch 0 taken 1624 times.
✓ Branch 1 taken 28868 times.
|
30492 | if (alloc_found) break; |
| 204 | } | ||
| 205 |
2/2✓ Branch 0 taken 1624 times.
✓ Branch 1 taken 1176 times.
|
2800 | if (alloc_found) { |
| 206 | 1624 | lbm_uint *allocation = (lbm_uint*)&mem_data[free_start]; | |
| 207 | 1624 | DEFRAG_ALLOC_SIZE(allocation) = bytes; | |
| 208 | 1624 | DEFRAG_ALLOC_DATA(allocation) = (lbm_uint)&allocation[3]; //data starts after back_ptr | |
| 209 | 1624 | DEFRAG_ALLOC_CELLPTR(allocation) = cell; | |
| 210 | 1624 | lbm_set_car(cell, (lbm_uint)allocation); | |
| 211 | 1624 | cell = lbm_set_ptr_type(cell, LBM_TYPE_ARRAY); | |
| 212 | 1624 | res = cell; | |
| 213 | } else { | ||
| 214 | 1176 | DEFRAG_MEM_FLAGS(defrag_mem) = 1; | |
| 215 | 1176 | lbm_set_car_and_cdr(cell, ENC_SYM_NIL, ENC_SYM_NIL); | |
| 216 | } | ||
| 217 | 2800 | return res; | |
| 218 | } | ||
| 219 | |||
| 220 | 2184 | lbm_value lbm_defrag_mem_alloc(lbm_uint *defrag_mem, lbm_uint bytes) { | |
| 221 | |||
| 222 | 2184 | lbm_value res = lbm_defrag_mem_alloc_internal(defrag_mem, bytes); // Try to allocate | |
| 223 |
2/2✓ Branch 1 taken 616 times.
✓ Branch 2 taken 1568 times.
|
2184 | if (lbm_is_symbol_merror(res)) { |
| 224 |
1/2✓ Branch 0 taken 616 times.
✗ Branch 1 not taken.
|
616 | if (DEFRAG_MEM_FLAGS(defrag_mem)) { //if we already performed GC, then also defrag |
| 225 | 616 | lbm_defrag_mem_defrag(defrag_mem, bytes); | |
| 226 | 616 | res = lbm_defrag_mem_alloc_internal(defrag_mem, bytes); // then try again | |
| 227 | 616 | DEFRAG_MEM_FLAGS(defrag_mem) = 0; | |
| 228 | } | ||
| 229 | } | ||
| 230 | 2184 | return res; | |
| 231 | } | ||
| 232 | |||
| 233 | |||
| 234 | // IF GC frees a defrag allocation, the cell pointing to it will also be destroyed by GC. | ||
| 235 | |||
| 236 | // is it guaranteed there are no copies of a heap-cell representing a defrag allocation. | ||
| 237 | // Same guarantee must hold for arrays in general or it would not be possible to explicitly free | ||
| 238 | // any array. | ||
| 239 | |||
| 240 | // At the time of free from GC all we have is the pointer. | ||
| 241 | 1036 | void lbm_defrag_mem_free(lbm_uint* data) { | |
| 242 | 1036 | lbm_uint nbytes = data[0]; | |
| 243 | 1036 | lbm_uint words_to_wipe = 3 + bs2ws(nbytes); | |
| 244 |
2/2✓ Branch 0 taken 6440 times.
✓ Branch 1 taken 1036 times.
|
7476 | for (lbm_uint i = 0; i < words_to_wipe; i ++) { |
| 245 | 6440 | data[i] = 0; | |
| 246 | } | ||
| 247 | 1036 | } | |
| 248 | |||
| 249 |