1 /* 2 * Copyright (c) 2006-2018, RT-Thread Development Team 3 * 4 * SPDX-License-Identifier: Apache-2.0 5 * 6 * Change Logs: 7 * Date Author Notes 8 * 2010-03-22 Bernard first version 9 */ 10 #include <finsh.h> 11 12 #include "finsh_var.h" 13 14 ALIGN(RT_ALIGN_SIZE) 15 uint8_t finsh_heap[FINSH_HEAP_MAX]; 16 struct finsh_block_header 17 { 18 uint32_t length; 19 struct finsh_block_header* next; 20 }; 21 #define BLOCK_HEADER(x) (struct finsh_block_header*)(x) 22 #define finsh_block_get_header(data) (struct finsh_block_header*)((uint8_t*)data - sizeof(struct finsh_block_header)) 23 #define finsh_block_get_data(header) (uint8_t*)((struct finsh_block_header*)header + 1) 24 #define HEAP_ALIGN_SIZE(size) (((size) + HEAP_ALIGNMENT - 1) & ~(HEAP_ALIGNMENT-1)) 25 26 static struct finsh_block_header* free_list; 27 static struct finsh_block_header* allocate_list; 28 29 static void finsh_heap_gc(void); 30 31 static void finsh_block_insert(struct finsh_block_header** list, struct finsh_block_header* header); 32 static void finsh_block_remove(struct finsh_block_header** list, struct finsh_block_header* header); 33 static void finsh_block_split(struct finsh_block_header* header, size_t size); 34 static void finsh_block_merge(struct finsh_block_header** list, struct finsh_block_header* header); 35 36 int finsh_heap_init(void) 37 { 38 /* clear heap to zero */ 39 memset(&finsh_heap[0], 0, sizeof(finsh_heap)); 40 41 /* init free and alloc list */ 42 free_list = BLOCK_HEADER(&finsh_heap[0]); 43 free_list->length = FINSH_HEAP_MAX - sizeof(struct finsh_block_header); 44 free_list->next = NULL; 45 46 allocate_list = NULL; 47 48 return 0; 49 } 50 51 /** 52 * allocate a block from heap 53 */ 54 void* finsh_heap_allocate(size_t size) 55 { 56 struct finsh_block_header* header; 57 58 size = HEAP_ALIGN_SIZE(size); 59 60 /* find the first fit block */ 61 for (header = free_list; 62 ((header != NULL) && (header->length <= size + sizeof(struct finsh_block_header))); 63 header = header->next) ; 64 65 if (header == NULL) 66 { 67 finsh_heap_gc(); 68 69 /* find the first fit block */ 70 for (header = free_list; 71 ((header != NULL) && (header->length < size + sizeof(struct finsh_block_header))); 72 header = header->next) ; 73 74 /* there is no memory */ 75 if (header == NULL) return NULL; 76 } 77 78 /* split block */ 79 finsh_block_split(header, size); 80 81 /* remove from free list */ 82 finsh_block_remove(&free_list, header); 83 header->next = NULL; 84 85 /* insert to allocate list */ 86 finsh_block_insert(&allocate_list, header); 87 88 memset(finsh_block_get_data(header), 0, size); 89 90 return finsh_block_get_data(header); 91 } 92 93 /** 94 * release the allocated block 95 */ 96 void finsh_heap_free(void*ptr) 97 { 98 struct finsh_block_header* header; 99 100 /* get block header */ 101 header = finsh_block_get_header(ptr); 102 103 /* remove from allocate list */ 104 finsh_block_remove(&allocate_list, header); 105 106 /* insert to free list */ 107 finsh_block_insert(&free_list, header); 108 finsh_block_merge(&free_list, header); 109 } 110 111 /** 112 * garbage collector 113 */ 114 static void finsh_heap_gc(void) 115 { 116 int i; 117 struct finsh_block_header *header, *temp; 118 119 temp = NULL; 120 121 /* find the first fit block */ 122 for (header = allocate_list; header != NULL; ) 123 { 124 for (i = 0; i < FINSH_VARIABLE_MAX; i ++) 125 { 126 if (global_variable[i].type != finsh_type_unknown) 127 { 128 if (global_variable[i].value.ptr == finsh_block_get_data(header)) 129 break; 130 } 131 } 132 133 temp = header; 134 header = header->next; 135 136 /* this block is an unused block, release it */ 137 if (i == FINSH_VARIABLE_MAX) 138 { 139 finsh_heap_free(finsh_block_get_data(temp)); 140 } 141 } 142 } 143 144 /** 145 * insert a block to list 146 */ 147 void finsh_block_insert(struct finsh_block_header** list, struct finsh_block_header* header) 148 { 149 struct finsh_block_header* node; 150 151 if (*list == NULL) 152 { 153 *list = header; 154 return; 155 } 156 157 /* find out insert point */ 158 node = *list; 159 160 if (node > header) 161 { 162 /* insert node in the header of list */ 163 header->next = node; 164 *list = header; 165 166 return; 167 } 168 else 169 { 170 for (node = *list; node; node = node->next) 171 { 172 if (node->next > header) break; 173 174 if (node->next == NULL) break; 175 } 176 } 177 178 /* insert node */ 179 if (node->next != NULL) header->next = node->next; 180 node->next = header; 181 } 182 183 /** 184 * remove block from list 185 */ 186 void finsh_block_remove(struct finsh_block_header** list, struct finsh_block_header* header) 187 { 188 struct finsh_block_header* node; 189 190 node = *list; 191 if (node == header) 192 { 193 /* remove list header */ 194 *list = header->next; 195 header->next = NULL; 196 197 return; 198 } 199 200 for (node = *list; node != NULL; node = node->next) 201 { 202 if (node->next == header) 203 { 204 node->next = header->next; 205 break; 206 } 207 } 208 } 209 210 /** 211 * split block 212 */ 213 void finsh_block_split(struct finsh_block_header* header, size_t size) 214 { 215 struct finsh_block_header* next; 216 217 /* 218 * split header into two node: 219 * header->next->... 220 */ 221 next = BLOCK_HEADER((uint8_t*)header + sizeof(struct finsh_block_header) + size); 222 next->length = header->length - sizeof(struct finsh_block_header) - size; 223 header->length = size; 224 next->next = header->next; 225 226 header->next = next; 227 } 228 229 void finsh_block_merge(struct finsh_block_header** list, struct finsh_block_header* header) 230 { 231 struct finsh_block_header* prev_node; 232 struct finsh_block_header* next_node; 233 234 next_node = header->next; 235 236 if (*list == header) prev_node = NULL; 237 else 238 { 239 /* find out the previous header */ 240 for (prev_node = *list; prev_node; prev_node =prev_node->next) 241 { 242 if (prev_node->next == header) 243 break; 244 } 245 } 246 247 /* try merge node */ 248 249 /* merge to previous node */ 250 if (prev_node != NULL && 251 ((uint8_t*)prev_node + prev_node->length + sizeof(struct finsh_block_header) 252 == (uint8_t*)header)) 253 { 254 /* is it close to next node? */ 255 if ((next_node != NULL) && 256 ((uint8_t*)header + header->length + sizeof(struct finsh_block_header) 257 == (uint8_t*)next_node)) 258 { 259 /* merge three node */ 260 prev_node->length += header->length + next_node->length + 261 2 * sizeof(struct finsh_block_header); 262 263 prev_node->next = next_node->next; 264 } 265 else 266 { 267 prev_node->length += header->length + sizeof(struct finsh_block_header); 268 prev_node->next = header->next; 269 } 270 } 271 else /* merge to last node */ 272 if ( (next_node != NULL) && 273 ((uint8_t*)header + header->length + sizeof(struct finsh_block_header) 274 == (uint8_t*)next_node)) 275 { 276 header->length += next_node->length + sizeof(struct finsh_block_header); 277 header->next = next_node->next; 278 } 279 } 280