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