1 /*
2 * FreeRTOS Kernel V11.1.0
3 * Copyright (C) 2021 Amazon.com, Inc. or its affiliates. All Rights Reserved.
4 *
5 * SPDX-License-Identifier: MIT
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining a copy of
8 * this software and associated documentation files (the "Software"), to deal in
9 * the Software without restriction, including without limitation the rights to
10 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
11 * the Software, and to permit persons to whom the Software is furnished to do so,
12 * subject to the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be included in all
15 * copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
19 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
20 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
21 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
22 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23 *
24 * https://www.FreeRTOS.org
25 * https://github.com/FreeRTOS
26 *
27 */
28
29 /* Standard includes. */
30 #include <stdint.h>
31
32 /* Secure context heap includes. */
33 #include "secure_heap.h"
34
35 /* Secure port macros. */
36 #include "secure_port_macros.h"
37
38 /**
39 * @brief Total heap size.
40 */
41 #ifndef secureconfigTOTAL_HEAP_SIZE
42 #define secureconfigTOTAL_HEAP_SIZE ( ( ( size_t ) ( 10 * 1024 ) ) )
43 #endif
44
45 /* No test marker by default. */
46 #ifndef mtCOVERAGE_TEST_MARKER
47 #define mtCOVERAGE_TEST_MARKER()
48 #endif
49
50 /* No tracing by default. */
51 #ifndef traceMALLOC
52 #define traceMALLOC( pvReturn, xWantedSize )
53 #endif
54
55 /* No tracing by default. */
56 #ifndef traceFREE
57 #define traceFREE( pv, xBlockSize )
58 #endif
59
60 /* Block sizes must not get too small. */
61 #define secureheapMINIMUM_BLOCK_SIZE ( ( size_t ) ( xHeapStructSize << 1 ) )
62
63 /* Assumes 8bit bytes! */
64 #define secureheapBITS_PER_BYTE ( ( size_t ) 8 )
65
66 /* Max value that fits in a size_t type. */
67 #define secureheapSIZE_MAX ( ~( ( size_t ) 0 ) )
68
69 /* Check if adding a and b will result in overflow. */
70 #define secureheapADD_WILL_OVERFLOW( a, b ) ( ( a ) > ( secureheapSIZE_MAX - ( b ) ) )
71
72 /* MSB of the xBlockSize member of an BlockLink_t structure is used to track
73 * the allocation status of a block. When MSB of the xBlockSize member of
74 * an BlockLink_t structure is set then the block belongs to the application.
75 * When the bit is free the block is still part of the free heap space. */
76 #define secureheapBLOCK_ALLOCATED_BITMASK ( ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * secureheapBITS_PER_BYTE ) - 1 ) )
77 #define secureheapBLOCK_SIZE_IS_VALID( xBlockSize ) ( ( ( xBlockSize ) & secureheapBLOCK_ALLOCATED_BITMASK ) == 0 )
78 #define secureheapBLOCK_IS_ALLOCATED( pxBlock ) ( ( ( pxBlock->xBlockSize ) & secureheapBLOCK_ALLOCATED_BITMASK ) != 0 )
79 #define secureheapALLOCATE_BLOCK( pxBlock ) ( ( pxBlock->xBlockSize ) |= secureheapBLOCK_ALLOCATED_BITMASK )
80 #define secureheapFREE_BLOCK( pxBlock ) ( ( pxBlock->xBlockSize ) &= ~secureheapBLOCK_ALLOCATED_BITMASK )
81 /*-----------------------------------------------------------*/
82
83 /* Allocate the memory for the heap. */
84 #if ( configAPPLICATION_ALLOCATED_HEAP == 1 )
85
86 /* The application writer has already defined the array used for the RTOS
87 * heap - probably so it can be placed in a special segment or address. */
88 extern uint8_t ucHeap[ secureconfigTOTAL_HEAP_SIZE ];
89 #else /* configAPPLICATION_ALLOCATED_HEAP */
90 static uint8_t ucHeap[ secureconfigTOTAL_HEAP_SIZE ];
91 #endif /* configAPPLICATION_ALLOCATED_HEAP */
92
93 /**
94 * @brief The linked list structure.
95 *
96 * This is used to link free blocks in order of their memory address.
97 */
98 typedef struct A_BLOCK_LINK
99 {
100 struct A_BLOCK_LINK * pxNextFreeBlock; /**< The next free block in the list. */
101 size_t xBlockSize; /**< The size of the free block. */
102 } BlockLink_t;
103 /*-----------------------------------------------------------*/
104
105 /**
106 * @brief Called automatically to setup the required heap structures the first
107 * time pvPortMalloc() is called.
108 */
109 static void prvHeapInit( void );
110
111 /**
112 * @brief Inserts a block of memory that is being freed into the correct
113 * position in the list of free memory blocks.
114 *
115 * The block being freed will be merged with the block in front it and/or the
116 * block behind it if the memory blocks are adjacent to each other.
117 *
118 * @param[in] pxBlockToInsert The block being freed.
119 */
120 static void prvInsertBlockIntoFreeList( BlockLink_t * pxBlockToInsert );
121 /*-----------------------------------------------------------*/
122
123 /**
124 * @brief The size of the structure placed at the beginning of each allocated
125 * memory block must by correctly byte aligned.
126 */
127 static const size_t xHeapStructSize = ( sizeof( BlockLink_t ) + ( ( size_t ) ( secureportBYTE_ALIGNMENT - 1 ) ) ) & ~( ( size_t ) secureportBYTE_ALIGNMENT_MASK );
128
129 /**
130 * @brief Create a couple of list links to mark the start and end of the list.
131 */
132 static BlockLink_t xStart;
133 static BlockLink_t * pxEnd = NULL;
134
135 /**
136 * @brief Keeps track of the number of free bytes remaining, but says nothing
137 * about fragmentation.
138 */
139 static size_t xFreeBytesRemaining = 0U;
140 static size_t xMinimumEverFreeBytesRemaining = 0U;
141
142 /*-----------------------------------------------------------*/
143
prvHeapInit(void)144 static void prvHeapInit( void )
145 {
146 BlockLink_t * pxFirstFreeBlock;
147 uint8_t * pucAlignedHeap;
148 size_t uxAddress;
149 size_t xTotalHeapSize = secureconfigTOTAL_HEAP_SIZE;
150
151 /* Ensure the heap starts on a correctly aligned boundary. */
152 uxAddress = ( size_t ) ucHeap;
153
154 if( ( uxAddress & secureportBYTE_ALIGNMENT_MASK ) != 0 )
155 {
156 uxAddress += ( secureportBYTE_ALIGNMENT - 1 );
157 uxAddress &= ~( ( size_t ) secureportBYTE_ALIGNMENT_MASK );
158 xTotalHeapSize -= uxAddress - ( size_t ) ucHeap;
159 }
160
161 pucAlignedHeap = ( uint8_t * ) uxAddress;
162
163 /* xStart is used to hold a pointer to the first item in the list of free
164 * blocks. The void cast is used to prevent compiler warnings. */
165 xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
166 xStart.xBlockSize = ( size_t ) 0;
167
168 /* pxEnd is used to mark the end of the list of free blocks and is inserted
169 * at the end of the heap space. */
170 uxAddress = ( ( size_t ) pucAlignedHeap ) + xTotalHeapSize;
171 uxAddress -= xHeapStructSize;
172 uxAddress &= ~( ( size_t ) secureportBYTE_ALIGNMENT_MASK );
173 pxEnd = ( void * ) uxAddress;
174 pxEnd->xBlockSize = 0;
175 pxEnd->pxNextFreeBlock = NULL;
176
177 /* To start with there is a single free block that is sized to take up the
178 * entire heap space, minus the space taken by pxEnd. */
179 pxFirstFreeBlock = ( void * ) pucAlignedHeap;
180 pxFirstFreeBlock->xBlockSize = uxAddress - ( size_t ) pxFirstFreeBlock;
181 pxFirstFreeBlock->pxNextFreeBlock = pxEnd;
182
183 /* Only one block exists - and it covers the entire usable heap space. */
184 xMinimumEverFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
185 xFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
186 }
187 /*-----------------------------------------------------------*/
188
prvInsertBlockIntoFreeList(BlockLink_t * pxBlockToInsert)189 static void prvInsertBlockIntoFreeList( BlockLink_t * pxBlockToInsert )
190 {
191 BlockLink_t * pxIterator;
192 uint8_t * puc;
193
194 /* Iterate through the list until a block is found that has a higher address
195 * than the block being inserted. */
196 for( pxIterator = &xStart; pxIterator->pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator->pxNextFreeBlock )
197 {
198 /* Nothing to do here, just iterate to the right position. */
199 }
200
201 /* Do the block being inserted, and the block it is being inserted after
202 * make a contiguous block of memory? */
203 puc = ( uint8_t * ) pxIterator;
204
205 if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )
206 {
207 pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;
208 pxBlockToInsert = pxIterator;
209 }
210 else
211 {
212 mtCOVERAGE_TEST_MARKER();
213 }
214
215 /* Do the block being inserted, and the block it is being inserted before
216 * make a contiguous block of memory? */
217 puc = ( uint8_t * ) pxBlockToInsert;
218
219 if( ( puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock )
220 {
221 if( pxIterator->pxNextFreeBlock != pxEnd )
222 {
223 /* Form one big block from the two blocks. */
224 pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize;
225 pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;
226 }
227 else
228 {
229 pxBlockToInsert->pxNextFreeBlock = pxEnd;
230 }
231 }
232 else
233 {
234 pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;
235 }
236
237 /* If the block being inserted plugged a gab, so was merged with the block
238 * before and the block after, then it's pxNextFreeBlock pointer will have
239 * already been set, and should not be set here as that would make it point
240 * to itself. */
241 if( pxIterator != pxBlockToInsert )
242 {
243 pxIterator->pxNextFreeBlock = pxBlockToInsert;
244 }
245 else
246 {
247 mtCOVERAGE_TEST_MARKER();
248 }
249 }
250 /*-----------------------------------------------------------*/
251
pvPortMalloc(size_t xWantedSize)252 void * pvPortMalloc( size_t xWantedSize )
253 {
254 BlockLink_t * pxBlock;
255 BlockLink_t * pxPreviousBlock;
256 BlockLink_t * pxNewBlockLink;
257 void * pvReturn = NULL;
258 size_t xAdditionalRequiredSize;
259
260 /* If this is the first call to malloc then the heap will require
261 * initialisation to setup the list of free blocks. */
262 if( pxEnd == NULL )
263 {
264 prvHeapInit();
265 }
266 else
267 {
268 mtCOVERAGE_TEST_MARKER();
269 }
270
271 if( xWantedSize > 0 )
272 {
273 /* The wanted size must be increased so it can contain a BlockLink_t
274 * structure in addition to the requested amount of bytes. */
275 if( secureheapADD_WILL_OVERFLOW( xWantedSize, xHeapStructSize ) == 0 )
276 {
277 xWantedSize += xHeapStructSize;
278
279 /* Ensure that blocks are always aligned to the required number
280 * of bytes. */
281 if( ( xWantedSize & secureportBYTE_ALIGNMENT_MASK ) != 0x00 )
282 {
283 /* Byte alignment required. */
284 xAdditionalRequiredSize = secureportBYTE_ALIGNMENT - ( xWantedSize & secureportBYTE_ALIGNMENT_MASK );
285
286 if( secureheapADD_WILL_OVERFLOW( xWantedSize, xAdditionalRequiredSize ) == 0 )
287 {
288 xWantedSize += xAdditionalRequiredSize;
289 }
290 else
291 {
292 xWantedSize = 0;
293 }
294 }
295 else
296 {
297 mtCOVERAGE_TEST_MARKER();
298 }
299 }
300 else
301 {
302 xWantedSize = 0;
303 }
304 }
305 else
306 {
307 mtCOVERAGE_TEST_MARKER();
308 }
309
310 /* Check the requested block size is not so large that the top bit is set.
311 * The top bit of the block size member of the BlockLink_t structure is used
312 * to determine who owns the block - the application or the kernel, so it
313 * must be free. */
314 if( secureheapBLOCK_SIZE_IS_VALID( xWantedSize ) != 0 )
315 {
316 if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
317 {
318 /* Traverse the list from the start (lowest address) block until
319 * one of adequate size is found. */
320 pxPreviousBlock = &xStart;
321 pxBlock = xStart.pxNextFreeBlock;
322
323 while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
324 {
325 pxPreviousBlock = pxBlock;
326 pxBlock = pxBlock->pxNextFreeBlock;
327 }
328
329 /* If the end marker was reached then a block of adequate size was
330 * not found. */
331 if( pxBlock != pxEnd )
332 {
333 /* Return the memory space pointed to - jumping over the
334 * BlockLink_t structure at its start. */
335 pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + xHeapStructSize );
336
337 /* This block is being returned for use so must be taken out
338 * of the list of free blocks. */
339 pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;
340
341 /* If the block is larger than required it can be split into
342 * two. */
343 if( ( pxBlock->xBlockSize - xWantedSize ) > secureheapMINIMUM_BLOCK_SIZE )
344 {
345 /* This block is to be split into two. Create a new
346 * block following the number of bytes requested. The void
347 * cast is used to prevent byte alignment warnings from the
348 * compiler. */
349 pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );
350 secureportASSERT( ( ( ( size_t ) pxNewBlockLink ) & secureportBYTE_ALIGNMENT_MASK ) == 0 );
351
352 /* Calculate the sizes of two blocks split from the single
353 * block. */
354 pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
355 pxBlock->xBlockSize = xWantedSize;
356
357 /* Insert the new block into the list of free blocks. */
358 pxNewBlockLink->pxNextFreeBlock = pxPreviousBlock->pxNextFreeBlock;
359 pxPreviousBlock->pxNextFreeBlock = pxNewBlockLink;
360 }
361 else
362 {
363 mtCOVERAGE_TEST_MARKER();
364 }
365
366 xFreeBytesRemaining -= pxBlock->xBlockSize;
367
368 if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )
369 {
370 xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;
371 }
372 else
373 {
374 mtCOVERAGE_TEST_MARKER();
375 }
376
377 /* The block is being returned - it is allocated and owned by
378 * the application and has no "next" block. */
379 secureheapALLOCATE_BLOCK( pxBlock );
380 pxBlock->pxNextFreeBlock = NULL;
381 }
382 else
383 {
384 mtCOVERAGE_TEST_MARKER();
385 }
386 }
387 else
388 {
389 mtCOVERAGE_TEST_MARKER();
390 }
391 }
392 else
393 {
394 mtCOVERAGE_TEST_MARKER();
395 }
396
397 traceMALLOC( pvReturn, xWantedSize );
398
399 #if ( secureconfigUSE_MALLOC_FAILED_HOOK == 1 )
400 {
401 if( pvReturn == NULL )
402 {
403 extern void vApplicationMallocFailedHook( void );
404 vApplicationMallocFailedHook();
405 }
406 else
407 {
408 mtCOVERAGE_TEST_MARKER();
409 }
410 }
411 #endif /* if ( secureconfigUSE_MALLOC_FAILED_HOOK == 1 ) */
412
413 secureportASSERT( ( ( ( size_t ) pvReturn ) & ( size_t ) secureportBYTE_ALIGNMENT_MASK ) == 0 );
414 return pvReturn;
415 }
416 /*-----------------------------------------------------------*/
417
vPortFree(void * pv)418 void vPortFree( void * pv )
419 {
420 uint8_t * puc = ( uint8_t * ) pv;
421 BlockLink_t * pxLink;
422
423 if( pv != NULL )
424 {
425 /* The memory being freed will have an BlockLink_t structure immediately
426 * before it. */
427 puc -= xHeapStructSize;
428
429 /* This casting is to keep the compiler from issuing warnings. */
430 pxLink = ( void * ) puc;
431
432 /* Check the block is actually allocated. */
433 secureportASSERT( secureheapBLOCK_IS_ALLOCATED( pxLink ) != 0 );
434 secureportASSERT( pxLink->pxNextFreeBlock == NULL );
435
436 if( secureheapBLOCK_IS_ALLOCATED( pxLink ) != 0 )
437 {
438 if( pxLink->pxNextFreeBlock == NULL )
439 {
440 /* The block is being returned to the heap - it is no longer
441 * allocated. */
442 secureheapFREE_BLOCK( pxLink );
443
444 secureportDISABLE_NON_SECURE_INTERRUPTS();
445 {
446 /* Add this block to the list of free blocks. */
447 xFreeBytesRemaining += pxLink->xBlockSize;
448 traceFREE( pv, pxLink->xBlockSize );
449 prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
450 }
451 secureportENABLE_NON_SECURE_INTERRUPTS();
452 }
453 else
454 {
455 mtCOVERAGE_TEST_MARKER();
456 }
457 }
458 else
459 {
460 mtCOVERAGE_TEST_MARKER();
461 }
462 }
463 }
464 /*-----------------------------------------------------------*/
465
xPortGetFreeHeapSize(void)466 size_t xPortGetFreeHeapSize( void )
467 {
468 return xFreeBytesRemaining;
469 }
470 /*-----------------------------------------------------------*/
471
xPortGetMinimumEverFreeHeapSize(void)472 size_t xPortGetMinimumEverFreeHeapSize( void )
473 {
474 return xMinimumEverFreeBytesRemaining;
475 }
476 /*-----------------------------------------------------------*/
477
