mem_lifo_allocator.c (8295B)
1 /* Copyright (C) 2013-2023, 2025 Vincent Forest (vaplv@free.fr) 2 * 3 * The RSys library is free software: you can redistribute it and/or modify 4 * it under the terms of the GNU General Public License as published 5 * by the Free Software Foundation, either version 3 of the License, or 6 * (at your option) any later version. 7 * 8 * The RSys library is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 * GNU General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public License 14 * along with the RSys library. If not, see <http://www.gnu.org/licenses/>. */ 15 16 #define _POSIX_C_SOURCE 200112L /* snprintf support */ 17 18 #include "math.h" 19 #include "mem_allocator.h" 20 #include "mutex.h" 21 #include <string.h> 22 23 struct lifo_data { 24 char* top; 25 char* stack; 26 size_t remain; 27 size_t capacity; 28 struct mem_allocator* allocator; 29 struct mutex* mutex; 30 }; 31 32 /* 33 * Stack entry memory layout: 34 * +----+-----------+-----------+------+----------+--------+-----------+ 35 * |... | A: 16bits | B: 48bits | DATA | C: 15bit | D: 1bit| E: 48bits | 36 * +----+-----------+-----------+------+----------+--------+-----------+ 37 * \___________Header_________/ \____________Footer___________/ 38 * 39 * A: size of the header in bytes 40 * B: size of DATA in bytes 41 * C: dummy data 42 * D: define whether the entry is in used or not 43 * E: size of DATA in bytes 44 */ 45 46 #define LIFO_DEFAULT_ALIGNMENT 8 47 48 /******************************************************************************* 49 * Helper functions 50 ******************************************************************************/ 51 static void* 52 lifo_alloc_aligned 53 (void* data, 54 const size_t size, 55 const size_t align, 56 const char* filename, 57 const unsigned int fileline) 58 { 59 struct lifo_data* lifo = data; 60 size_t align_adjusted; 61 size_t header_size; 62 size_t footer_size; 63 size_t data_size; 64 size_t entry_size; 65 char* mem; 66 int64_t header; 67 int64_t footer; 68 ASSERT(data); 69 (void)filename, (void)fileline; 70 71 if(!IS_POW2(align) || align > 32768) 72 return NULL; 73 74 align_adjusted = align < LIFO_DEFAULT_ALIGNMENT 75 ? LIFO_DEFAULT_ALIGNMENT : align; 76 77 mutex_lock(lifo->mutex); 78 { /* Critical section */ 79 intptr_t data_addr = (intptr_t)(lifo->top + sizeof(int64_t)); 80 data_addr = ALIGN_SIZE(data_addr, (intptr_t)align_adjusted); 81 82 header_size = (size_t)(data_addr - (intptr_t)lifo->top); 83 footer_size = sizeof(int64_t); 84 data_size = ALIGN_SIZE(size, sizeof(int64_t)); 85 entry_size = header_size + data_size + footer_size; 86 87 ASSERT(data_size < (size_t)(((int64_t)1<<48)-1)); 88 ASSERT(header_size < (1<<16)-1); 89 header = (int64_t)data_size | ((int64_t)header_size<<48); 90 footer = (int64_t)data_size | ((int64_t)1<<48); 91 92 if(lifo->remain < entry_size) { 93 mem = NULL; 94 } else { 95 lifo->remain -= entry_size; 96 mem = lifo->top + header_size; 97 ASSERT(IS_ALIGNED(lifo->top, LIFO_DEFAULT_ALIGNMENT)); 98 lifo->top += entry_size; 99 *(int64_t*)(mem - sizeof(int64_t)) = header; 100 *(int64_t*)(mem + data_size) = footer; 101 } 102 } 103 CHK(IS_ALIGNED(mem, align)); 104 105 mutex_unlock(lifo->mutex); 106 return mem; 107 } 108 109 static void* 110 lifo_alloc 111 (void* data, 112 const size_t size, 113 const char* filename, 114 const unsigned int fileline) 115 { 116 return lifo_alloc_aligned 117 (data, size, LIFO_DEFAULT_ALIGNMENT, filename, fileline); 118 } 119 120 static void* 121 lifo_calloc 122 (void* data, 123 const size_t nelmts, 124 const size_t size, 125 const char* filename, 126 const unsigned int fileline) 127 { 128 size_t allocation_size = nelmts * size; 129 void* mem = lifo_alloc(data, allocation_size, filename, fileline); 130 if(mem) mem = memset(mem, 0, allocation_size); 131 return mem; 132 } 133 134 static void 135 lifo_free(void* data, void* mem) 136 { 137 struct lifo_data* lifo = data; 138 int64_t header; 139 int64_t footer; 140 size_t data_size; 141 int64_t* pfooter; 142 char* ptr; 143 char* end; 144 ASSERT(data); 145 146 if(!mem) return; 147 148 ptr = mem; 149 header = *(int64_t*)(ptr-sizeof(int64_t)); 150 data_size = (size_t)(header & (((int64_t)1<<48)-1)); 151 pfooter = (int64_t*)(ptr + data_size); 152 end = ptr + data_size + sizeof(int64_t); 153 154 mutex_lock(lifo->mutex); 155 *pfooter &= ~((int64_t)1<<48); /* No more in use */ 156 if(end == lifo->top) { /* Pop */ 157 size_t header_size = (size_t)(header >> 48); 158 char* top = ptr - header_size; 159 160 lifo->remain += data_size + header_size + sizeof(int64_t)/*footer size*/; 161 162 while(top != lifo->stack) { /* Pop all free entries */ 163 ptr = top - sizeof(int64_t); 164 footer = *(int64_t*)ptr; 165 if(footer & ((int64_t)1<<48)) break; /* In use */ 166 167 data_size = (size_t)(footer & (((int64_t)1<<48)-1)); 168 ptr -= data_size; 169 170 header = *(int64_t*)(ptr-sizeof(int64_t)); 171 ASSERT(data_size == (size_t)(header & (((int64_t)1<<48)-1))); 172 header_size = (size_t)(header>>48); 173 top = ptr - header_size; 174 175 lifo->remain += data_size + header_size + sizeof(int64_t)/*footer_size*/; 176 ASSERT(lifo->remain <= lifo->capacity); 177 } 178 lifo->top = top; 179 } 180 mutex_unlock(lifo->mutex); 181 } 182 183 static void* 184 lifo_realloc 185 (void* data, 186 void* mem, 187 const size_t size, 188 const char* filename, 189 const unsigned int fileline) 190 { 191 if(size==0) { 192 lifo_free(data, mem); 193 return NULL; 194 } else { 195 size_t mem_size; 196 int64_t mem_header; 197 char* new_mem = lifo_alloc(data, size, filename, fileline); 198 if(!new_mem || !mem) return new_mem; 199 mem_header = *(int64_t*)((char*)mem - sizeof(int64_t)); 200 mem_size = (size_t)(mem_header & (((int64_t)1<<48)-1)); 201 memcpy(new_mem, mem, mem_size); 202 lifo_free(data, mem); 203 return new_mem; 204 } 205 } 206 207 static size_t 208 lifo_mem_size(void* data, void* mem) 209 { 210 int64_t header; 211 (void)data; 212 header = *(int64_t*)((char*)mem-sizeof(int64_t)); 213 return (size_t)(header & (((int64_t)1<<48)-1)); 214 } 215 216 static size_t 217 lifo_allocated_size(const void* data) 218 { 219 const struct lifo_data* lifo = data; 220 size_t size; 221 ASSERT(data); 222 mutex_lock(lifo->mutex); 223 size = lifo->capacity - lifo->remain; 224 mutex_unlock(lifo->mutex); 225 return size; 226 } 227 228 static size_t 229 lifo_dump(const void* data, char* dump, const size_t max_dump_len) 230 { 231 size_t len; 232 233 len = (size_t)snprintf(dump, max_dump_len, "%lu bytes allocated.", 234 (unsigned long)lifo_allocated_size(data)); 235 if(len >= (max_dump_len-1)) /* -1 <=> null char */ 236 dump[max_dump_len-1] = '\0'; 237 return len; 238 } 239 240 /******************************************************************************* 241 * Exported functions 242 ******************************************************************************/ 243 res_T 244 mem_init_lifo_allocator 245 (struct mem_allocator* lifo_allocator, 246 struct mem_allocator* allocator, 247 const size_t size) 248 { 249 struct lifo_data* lifo = NULL; 250 res_T res = RES_OK; 251 252 if(!allocator || !lifo_allocator) { 253 res = RES_BAD_ARG; 254 goto error; 255 } 256 memset(lifo_allocator, 0, sizeof(struct mem_allocator)); 257 258 lifo = MEM_CALLOC(allocator, 1, sizeof(struct lifo_data)); 259 if(!lifo) { 260 res = RES_MEM_ERR; 261 goto error; 262 } 263 lifo_allocator->data = (void*)lifo; 264 lifo->allocator = allocator; 265 lifo->stack = MEM_ALLOC_ALIGNED(allocator, size, LIFO_DEFAULT_ALIGNMENT); 266 if(!lifo->stack) { 267 res = RES_MEM_ERR; 268 goto error; 269 } 270 lifo->mutex = mutex_create(); 271 if(!lifo->mutex) { 272 res = RES_MEM_ERR; 273 goto error; 274 } 275 lifo->top = lifo->stack; 276 lifo->capacity = size; 277 lifo->remain = size; 278 279 lifo_allocator->alloc = lifo_alloc; 280 lifo_allocator->calloc = lifo_calloc; 281 lifo_allocator->realloc = lifo_realloc; 282 lifo_allocator->mem_size = lifo_mem_size; 283 lifo_allocator->alloc_aligned = lifo_alloc_aligned; 284 lifo_allocator->rm = lifo_free; 285 lifo_allocator->allocated_size = lifo_allocated_size; 286 lifo_allocator->dump = lifo_dump; 287 288 exit: 289 return res; 290 error: 291 if(lifo_allocator) 292 mem_shutdown_lifo_allocator(lifo_allocator); 293 goto exit; 294 } 295 296 void 297 mem_shutdown_lifo_allocator(struct mem_allocator* allocator) 298 { 299 struct lifo_data* lifo; 300 ASSERT(allocator); 301 lifo = allocator->data; 302 if(lifo) { 303 if(lifo->mutex) mutex_destroy(lifo->mutex); 304 if(lifo->stack) MEM_RM(lifo->allocator, lifo->stack); 305 MEM_RM(lifo->allocator, lifo); 306 } 307 memset(allocator, 0, sizeof(struct mem_allocator)); 308 }