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
ALIGN(RT_ALIGN_SIZE)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
finsh_heap_init(void)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 */
finsh_heap_allocate(size_t size)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 */
finsh_heap_free(void * ptr)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 */
finsh_heap_gc(void)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 */
finsh_block_insert(struct finsh_block_header ** list,struct finsh_block_header * header)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 */
finsh_block_remove(struct finsh_block_header ** list,struct finsh_block_header * header)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 */
finsh_block_split(struct finsh_block_header * header,size_t size)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
finsh_block_merge(struct finsh_block_header ** list,struct finsh_block_header * header)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