heap_4.c
Go to the documentation of this file.
1 /*
2  FreeRTOS V9.0.1 - Copyright (C) 2017 Real Time Engineers Ltd.
3  All rights reserved
4 
5  VISIT http://www.FreeRTOS.org TO ENSURE YOU ARE USING THE LATEST VERSION.
6 
7  This file is part of the FreeRTOS distribution.
8 
9  FreeRTOS is free software; you can redistribute it and/or modify it under
10  the terms of the GNU General Public License (version 2) as published by the
11  Free Software Foundation >>>> AND MODIFIED BY <<<< the FreeRTOS exception.
12 
13  ***************************************************************************
14  >>! NOTE: The modification to the GPL is included to allow you to !<<
15  >>! distribute a combined work that includes FreeRTOS without being !<<
16  >>! obliged to provide the source code for proprietary components !<<
17  >>! outside of the FreeRTOS kernel. !<<
18  ***************************************************************************
19 
20  FreeRTOS is distributed in the hope that it will be useful, but WITHOUT ANY
21  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
22  FOR A PARTICULAR PURPOSE. Full license text is available on the following
23  link: http://www.freertos.org/a00114.html
24 
25  ***************************************************************************
26  * *
27  * FreeRTOS provides completely free yet professionally developed, *
28  * robust, strictly quality controlled, supported, and cross *
29  * platform software that is more than just the market leader, it *
30  * is the industry's de facto standard. *
31  * *
32  * Help yourself get started quickly while simultaneously helping *
33  * to support the FreeRTOS project by purchasing a FreeRTOS *
34  * tutorial book, reference manual, or both: *
35  * http://www.FreeRTOS.org/Documentation *
36  * *
37  ***************************************************************************
38 
39  http://www.FreeRTOS.org/FAQHelp.html - Having a problem? Start by reading
40  the FAQ page "My application does not run, what could be wrong?". Have you
41  defined configASSERT()?
42 
43  http://www.FreeRTOS.org/support - In return for receiving this top quality
44  embedded software for free we request you assist our global community by
45  participating in the support forum.
46 
47  http://www.FreeRTOS.org/training - Investing in training allows your team to
48  be as productive as possible as early as possible. Now you can receive
49  FreeRTOS training directly from Richard Barry, CEO of Real Time Engineers
50  Ltd, and the world's leading authority on the world's leading RTOS.
51 
52  http://www.FreeRTOS.org/plus - A selection of FreeRTOS ecosystem products,
53  including FreeRTOS+Trace - an indispensable productivity tool, a DOS
54  compatible FAT file system, and our tiny thread aware UDP/IP stack.
55 
56  http://www.FreeRTOS.org/labs - Where new FreeRTOS products go to incubate.
57  Come and try FreeRTOS+TCP, our new open source TCP/IP stack for FreeRTOS.
58 
59  http://www.OpenRTOS.com - Real Time Engineers ltd. license FreeRTOS to High
60  Integrity Systems ltd. to sell under the OpenRTOS brand. Low cost OpenRTOS
61  licenses offer ticketed support, indemnification and commercial middleware.
62 
63  http://www.SafeRTOS.com - High Integrity Systems also provide a safety
64  engineered and independently SIL3 certified version for use in safety and
65  mission critical applications that require provable dependability.
66 
67  1 tab == 4 spaces!
68 */
69 
70 /*
71  * A sample implementation of pvPortMalloc() and vPortFree() that combines
72  * (coalescences) adjacent memory blocks as they are freed, and in so doing
73  * limits memory fragmentation.
74  *
75  * See heap_1.c, heap_2.c and heap_3.c for alternative implementations, and the
76  * memory management pages of http://www.FreeRTOS.org for more information.
77  */
78 #include <stdlib.h>
79 
80 /* Defining MPU_WRAPPERS_INCLUDED_FROM_API_FILE prevents task.h from redefining
81 all the API functions to use the MPU wrappers. That should only be done when
82 task.h is included from an application file. */
83 #define MPU_WRAPPERS_INCLUDED_FROM_API_FILE
84 
85 #include "FreeRTOS.h"
86 #include "task.h"
87 
88 #undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE
89 
90 #if( configSUPPORT_DYNAMIC_ALLOCATION == 0 )
91  #error This file must not be used if configSUPPORT_DYNAMIC_ALLOCATION is 0
92 #endif
93 
94 /* Block sizes must not get too small. */
95 #define heapMINIMUM_BLOCK_SIZE ( ( size_t ) ( xHeapStructSize << 1 ) )
96 
97 /* Assumes 8bit bytes! */
98 #define heapBITS_PER_BYTE ( ( size_t ) 8 )
99 
100 /* Allocate the memory for the heap. */
101 #if( configAPPLICATION_ALLOCATED_HEAP == 1 )
102  /* The application writer has already defined the array used for the RTOS
103  heap - probably so it can be placed in a special segment or address. */
104  extern uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];
105 #else
106  static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];
107 #endif /* configAPPLICATION_ALLOCATED_HEAP */
108 
109 /* Define the linked list structure. This is used to link free blocks in order
110 of their memory address. */
111 typedef struct A_BLOCK_LINK
112 {
113  struct A_BLOCK_LINK *pxNextFreeBlock; /*<< The next free block in the list. */
114  size_t xBlockSize; /*<< The size of the free block. */
115 } BlockLink_t;
116 
117 /*-----------------------------------------------------------*/
118 
119 /*
120  * Inserts a block of memory that is being freed into the correct position in
121  * the list of free memory blocks. The block being freed will be merged with
122  * the block in front it and/or the block behind it if the memory blocks are
123  * adjacent to each other.
124  */
125 static void prvInsertBlockIntoFreeList( BlockLink_t *pxBlockToInsert );
126 
127 /*
128  * Called automatically to setup the required heap structures the first time
129  * pvPortMalloc() is called.
130  */
131 static void prvHeapInit( void );
132 
133 /*-----------------------------------------------------------*/
134 
135 /* The size of the structure placed at the beginning of each allocated memory
136 block must by correctly byte aligned. */
137 static const size_t xHeapStructSize = ( sizeof( BlockLink_t ) + ( ( size_t ) ( portBYTE_ALIGNMENT - 1 ) ) ) & ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
138 
139 /* Create a couple of list links to mark the start and end of the list. */
141 
142 /* Keeps track of the number of free bytes remaining, but says nothing about
143 fragmentation. */
144 static size_t xFreeBytesRemaining = 0U;
146 
147 /* Gets set to the top bit of an size_t type. When this bit in the xBlockSize
148 member of an BlockLink_t structure is set then the block belongs to the
149 application. When the bit is free the block is still part of the free heap
150 space. */
151 static size_t xBlockAllocatedBit = 0;
152 
153 /*-----------------------------------------------------------*/
154 
155 void *pvPortMalloc( size_t xWantedSize )
156 {
157 BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
158 void *pvReturn = NULL;
159 
160  vTaskSuspendAll();
161  {
162  /* If this is the first call to malloc then the heap will require
163  initialisation to setup the list of free blocks. */
164  if( pxEnd == NULL )
165  {
166  prvHeapInit();
167  }
168  else
169  {
171  }
172 
173  /* Check the requested block size is not so large that the top bit is
174  set. The top bit of the block size member of the BlockLink_t structure
175  is used to determine who owns the block - the application or the
176  kernel, so it must be free. */
177  if( ( xWantedSize & xBlockAllocatedBit ) == 0 )
178  {
179  /* The wanted size is increased so it can contain a BlockLink_t
180  structure in addition to the requested amount of bytes. */
181  if( xWantedSize > 0 )
182  {
183  xWantedSize += xHeapStructSize;
184 
185  /* Ensure that blocks are always aligned to the required number
186  of bytes. */
187  if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0x00 )
188  {
189  /* Byte alignment required. */
190  xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
191  configASSERT( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) == 0 );
192  }
193  else
194  {
196  }
197  }
198  else
199  {
201  }
202 
203  if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
204  {
205  /* Traverse the list from the start (lowest address) block until
206  one of adequate size is found. */
207  pxPreviousBlock = &xStart;
208  pxBlock = xStart.pxNextFreeBlock;
209  while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
210  {
211  pxPreviousBlock = pxBlock;
212  pxBlock = pxBlock->pxNextFreeBlock;
213  }
214 
215  /* If the end marker was reached then a block of adequate size
216  was not found. */
217  if( pxBlock != pxEnd )
218  {
219  /* Return the memory space pointed to - jumping over the
220  BlockLink_t structure at its start. */
221  pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + xHeapStructSize );
222 
223  /* This block is being returned for use so must be taken out
224  of the list of free blocks. */
225  pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;
226 
227  /* If the block is larger than required it can be split into
228  two. */
229  if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )
230  {
231  /* This block is to be split into two. Create a new
232  block following the number of bytes requested. The void
233  cast is used to prevent byte alignment warnings from the
234  compiler. */
235  pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );
236  configASSERT( ( ( ( size_t ) pxNewBlockLink ) & portBYTE_ALIGNMENT_MASK ) == 0 );
237 
238  /* Calculate the sizes of two blocks split from the
239  single block. */
240  pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
241  pxBlock->xBlockSize = xWantedSize;
242 
243  /* Insert the new block into the list of free blocks. */
244  prvInsertBlockIntoFreeList( pxNewBlockLink );
245  }
246  else
247  {
249  }
250 
251  xFreeBytesRemaining -= pxBlock->xBlockSize;
252 
253  if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )
254  {
255  xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;
256  }
257  else
258  {
260  }
261 
262  /* The block is being returned - it is allocated and owned
263  by the application and has no "next" block. */
264  traceMALLOC(pvReturn, pxBlock->xBlockSize);
265  pxBlock->xBlockSize |= xBlockAllocatedBit;
266  pxBlock->pxNextFreeBlock = NULL;
267  }
268  else
269  {
271  }
272  }
273  else
274  {
276  }
277  }
278  else
279  {
281  }
282  }
283  ( void ) xTaskResumeAll();
284 
285  #if( configUSE_MALLOC_FAILED_HOOK == 1 )
286  {
287  if( pvReturn == NULL )
288  {
289 #if defined(__GNUC__)
290 #pragma GCC diagnostic push
291 #pragma GCC diagnostic ignored "-Wnested-externs"
292 #endif
293  extern void vApplicationMallocFailedHook( uint32_t, uint32_t );
294 #if defined(__GNUC__)
295 #pragma GCC diagnostic pop
296 #endif
297  vApplicationMallocFailedHook(xWantedSize, xFreeBytesRemaining);
298  }
299  else
300  {
302  }
303  }
304  #endif
305 
306  configASSERT( ( ( ( size_t ) pvReturn ) & ( size_t ) portBYTE_ALIGNMENT_MASK ) == 0 );
307  return pvReturn;
308 }
309 /*-----------------------------------------------------------*/
310 
311 void vPortFree( void *pv )
312 {
313 uint8_t *puc = ( uint8_t * ) pv;
314 BlockLink_t *pxLink;
315 
316  if( pv != NULL )
317  {
318  /* The memory being freed will have an BlockLink_t structure immediately
319  before it. */
320  puc -= xHeapStructSize;
321 
322  /* This casting is to keep the compiler from issuing warnings. */
323  pxLink = ( void * ) puc;
324 
325  /* Check the block is actually allocated. */
326  configASSERT( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 );
327  configASSERT( pxLink->pxNextFreeBlock == NULL );
328 
329  if( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 )
330  {
331  if( pxLink->pxNextFreeBlock == NULL )
332  {
333  /* The block is being returned to the heap - it is no longer
334  allocated. */
335  pxLink->xBlockSize &= ~xBlockAllocatedBit;
336 
337  vTaskSuspendAll();
338  {
339  /* Add this block to the list of free blocks. */
340  xFreeBytesRemaining += pxLink->xBlockSize;
341  traceFREE(pv, pxLink->xBlockSize);
342  prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
343  }
344  ( void ) xTaskResumeAll();
345  }
346  else
347  {
349  }
350  }
351  else
352  {
354  }
355  }
356 }
357 /*-----------------------------------------------------------*/
358 
359 size_t xPortGetFreeHeapSize( void )
360 {
361  return xFreeBytesRemaining;
362 }
363 /*-----------------------------------------------------------*/
364 
366 {
368 }
369 /*-----------------------------------------------------------*/
370 
372 {
373  /* This just exists to keep the linker quiet. */
374 }
375 /*-----------------------------------------------------------*/
376 
377 static void prvHeapInit( void )
378 {
379 BlockLink_t *pxFirstFreeBlock;
380 uint8_t *pucAlignedHeap;
381 size_t uxAddress;
382 size_t xTotalHeapSize = configTOTAL_HEAP_SIZE;
383 
384  /* Ensure the heap starts on a correctly aligned boundary. */
385  uxAddress = ( size_t ) ucHeap;
386 
387  if( ( uxAddress & portBYTE_ALIGNMENT_MASK ) != 0 )
388  {
389  uxAddress += ( portBYTE_ALIGNMENT - 1 );
390  uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
391  xTotalHeapSize -= uxAddress - ( size_t ) ucHeap;
392  }
393 
394  pucAlignedHeap = ( uint8_t * ) uxAddress;
395 
396  /* xStart is used to hold a pointer to the first item in the list of free
397  blocks. The void cast is used to prevent compiler warnings. */
398  xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
399  xStart.xBlockSize = ( size_t ) 0;
400 
401  /* pxEnd is used to mark the end of the list of free blocks and is inserted
402  at the end of the heap space. */
403  uxAddress = ( ( size_t ) pucAlignedHeap ) + xTotalHeapSize;
404  uxAddress -= xHeapStructSize;
405  uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
406  pxEnd = ( void * ) uxAddress;
407  pxEnd->xBlockSize = 0;
408  pxEnd->pxNextFreeBlock = NULL;
409 
410  /* To start with there is a single free block that is sized to take up the
411  entire heap space, minus the space taken by pxEnd. */
412  pxFirstFreeBlock = ( void * ) pucAlignedHeap;
413  pxFirstFreeBlock->xBlockSize = uxAddress - ( size_t ) pxFirstFreeBlock;
414  pxFirstFreeBlock->pxNextFreeBlock = pxEnd;
415 
416  /* Only one block exists - and it covers the entire usable heap space. */
417  xMinimumEverFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
418  xFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
419 
420  /* Work out the position of the top bit in a size_t variable. */
421  xBlockAllocatedBit = ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 );
422 }
423 /*-----------------------------------------------------------*/
424 
425 static void prvInsertBlockIntoFreeList( BlockLink_t *pxBlockToInsert )
426 {
427 BlockLink_t *pxIterator;
428 uint8_t *puc;
429 
430  /* Iterate through the list until a block is found that has a higher address
431  than the block being inserted. */
432  for( pxIterator = &xStart; pxIterator->pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator->pxNextFreeBlock )
433  {
434  /* Nothing to do here, just iterate to the right position. */
435  }
436 
437  /* Do the block being inserted, and the block it is being inserted after
438  make a contiguous block of memory? */
439  puc = ( uint8_t * ) pxIterator;
440  if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )
441  {
442  pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;
443  pxBlockToInsert = pxIterator;
444  }
445  else
446  {
448  }
449 
450  /* Do the block being inserted, and the block it is being inserted before
451  make a contiguous block of memory? */
452  puc = ( uint8_t * ) pxBlockToInsert;
453  if( ( puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock )
454  {
455  if( pxIterator->pxNextFreeBlock != pxEnd )
456  {
457  /* Form one big block from the two blocks. */
458  pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize;
459  pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;
460  }
461  else
462  {
463  pxBlockToInsert->pxNextFreeBlock = pxEnd;
464  }
465  }
466  else
467  {
468  pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;
469  }
470 
471  /* If the block being inserted plugged a gab, so was merged with the block
472  before and the block after, then it's pxNextFreeBlock pointer will have
473  already been set, and should not be set here as that would make it point
474  to itself. */
475  if( pxIterator != pxBlockToInsert )
476  {
477  pxIterator->pxNextFreeBlock = pxBlockToInsert;
478  }
479  else
480  {
482  }
483 }
484 
void vApplicationMallocFailedHook(uint32_t size, uint32_t remaining, uint32_t prevLR)
Definition: rtos.c:166
static BlockLink_t * pxEnd
Definition: heap_4.c:140
void vPortInitialiseBlocks(void)
Definition: heap_4.c:371
void vTaskSuspendAll(void) PRIVILEGED_FUNCTION
Definition: tasks.c:2034
#define configTOTAL_HEAP_SIZE
size_t xPortGetMinimumEverFreeHeapSize(void)
Definition: heap_4.c:365
#define heapMINIMUM_BLOCK_SIZE
Definition: heap_4.c:95
#define NULL
Definition: nm_bsp.h:52
static size_t xBlockAllocatedBit
Definition: heap_4.c:151
#define heapBITS_PER_BYTE
Definition: heap_4.c:98
#define configASSERT(x)
Definition: FreeRTOS.h:235
static void prvInsertBlockIntoFreeList(BlockLink_t *pxBlockToInsert)
Definition: heap_4.c:425
void vPortFree(void *pv)
Definition: heap_4.c:311
static size_t xMinimumEverFreeBytesRemaining
Definition: heap_4.c:145
struct A_BLOCK_LINK BlockLink_t
#define traceFREE(pvAddress, uiSize)
Definition: FreeRTOS.h:553
static size_t xFreeBytesRemaining
Definition: heap_4.c:144
static void prvHeapInit(void)
Definition: heap_4.c:377
void * pvPortMalloc(size_t xWantedSize)
Definition: heap_4.c:155
BaseType_t xTaskResumeAll(void) PRIVILEGED_FUNCTION
Definition: tasks.c:2107
#define traceMALLOC(pvAddress, uiSize)
Definition: FreeRTOS.h:549
static BlockLink_t xStart
Definition: heap_4.c:140
#define portBYTE_ALIGNMENT
Definition: portmacro.h:76
size_t xPortGetFreeHeapSize(void)
Definition: heap_4.c:359
static const size_t xHeapStructSize
Definition: heap_4.c:137
#define mtCOVERAGE_TEST_MARKER()
Definition: FreeRTOS.h:787
static uint8_t ucHeap[configTOTAL_HEAP_SIZE]
Definition: heap_4.c:106


inertial_sense_ros
Author(s):
autogenerated on Sat Sep 19 2020 03:19:04