/*************************************************************************** * Copyright (c) 2024 Microsoft Corporation * * This program and the accompanying materials are made available under the * terms of the MIT License which is available at * https://opensource.org/licenses/MIT. * * SPDX-License-Identifier: MIT **************************************************************************/ /**************************************************************************/ /**************************************************************************/ /** */ /** ThreadX Component */ /** */ /** Byte Pool */ /** */ /**************************************************************************/ /**************************************************************************/ #define TX_SOURCE_CODE /* Include necessary system files. */ #include "tx_api.h" #include "tx_thread.h" #include "tx_byte_pool.h" /**************************************************************************/ /* */ /* FUNCTION RELEASE */ /* */ /* _tx_byte_pool_search PORTABLE C */ /* 6.1.7 */ /* AUTHOR */ /* */ /* William E. Lamie, Microsoft Corporation */ /* */ /* DESCRIPTION */ /* */ /* This function searches a byte pool for a memory block to satisfy */ /* the requested number of bytes. Merging of adjacent free blocks */ /* takes place during the search and a split of the block that */ /* satisfies the request may occur before this function returns. */ /* */ /* It is assumed that this function is called with interrupts enabled */ /* and with the tx_pool_owner field set to the thread performing the */ /* search. Also note that the search can occur during allocation and */ /* release of a memory block. */ /* */ /* INPUT */ /* */ /* pool_ptr Pointer to pool control block */ /* memory_size Number of bytes required */ /* */ /* OUTPUT */ /* */ /* UCHAR * Pointer to the allocated memory, */ /* if successful. Otherwise, a */ /* NULL is returned */ /* */ /* CALLS */ /* */ /* None */ /* */ /* CALLED BY */ /* */ /* _tx_byte_allocate Allocate bytes of memory */ /* _tx_byte_release Release bytes of memory */ /* */ /* RELEASE HISTORY */ /* */ /* DATE NAME DESCRIPTION */ /* */ /* 05-19-2020 William E. Lamie Initial Version 6.0 */ /* 09-30-2020 Yuxin Zhou Modified comment(s), */ /* resulting in version 6.1 */ /* 06-02-2021 Scott Larson Improve possible free bytes */ /* calculation, */ /* resulting in version 6.1.7 */ /* */ /**************************************************************************/ UCHAR *_tx_byte_pool_search(TX_BYTE_POOL *pool_ptr, ULONG memory_size) { TX_INTERRUPT_SAVE_AREA UCHAR *current_ptr; UCHAR *next_ptr; UCHAR **this_block_link_ptr; UCHAR **next_block_link_ptr; ULONG available_bytes; UINT examine_blocks; UINT first_free_block_found = TX_FALSE; TX_THREAD *thread_ptr; ALIGN_TYPE *free_ptr; UCHAR *work_ptr; ULONG total_theoretical_available; /* Disable interrupts. */ TX_DISABLE /* First, determine if there are enough bytes in the pool. */ /* Theoretical bytes available = free bytes + ((fragments-2) * overhead of each block) */ total_theoretical_available = pool_ptr -> tx_byte_pool_available + ((pool_ptr -> tx_byte_pool_fragments - 2) * ((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE)))); if (memory_size >= total_theoretical_available) { /* Restore interrupts. */ TX_RESTORE /* Not enough memory, return a NULL pointer. */ current_ptr = TX_NULL; } else { /* Pickup thread pointer. */ TX_THREAD_GET_CURRENT(thread_ptr) /* Setup ownership of the byte pool. */ pool_ptr -> tx_byte_pool_owner = thread_ptr; /* Walk through the memory pool in search for a large enough block. */ current_ptr = pool_ptr -> tx_byte_pool_search; examine_blocks = pool_ptr -> tx_byte_pool_fragments + ((UINT) 1); available_bytes = ((ULONG) 0); do { #ifdef TX_BYTE_POOL_ENABLE_PERFORMANCE_INFO /* Increment the total fragment search counter. */ _tx_byte_pool_performance_search_count++; /* Increment the number of fragments searched on this pool. */ pool_ptr -> tx_byte_pool_performance_search_count++; #endif /* Check to see if this block is free. */ work_ptr = TX_UCHAR_POINTER_ADD(current_ptr, (sizeof(UCHAR *))); free_ptr = TX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT(work_ptr); if ((*free_ptr) == TX_BYTE_BLOCK_FREE) { /* Determine if this is the first free block. */ if (first_free_block_found == TX_FALSE) { /* This is the first free block. */ pool_ptr->tx_byte_pool_search = current_ptr; /* Set the flag to indicate we have found the first free block. */ first_free_block_found = TX_TRUE; } /* Block is free, see if it is large enough. */ /* Pickup the next block's pointer. */ this_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(current_ptr); next_ptr = *this_block_link_ptr; /* Calculate the number of bytes available in this block. */ available_bytes = TX_UCHAR_POINTER_DIF(next_ptr, current_ptr); available_bytes = available_bytes - ((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE))); /* If this is large enough, we are done because our first-fit algorithm has been satisfied! */ if (available_bytes >= memory_size) { /* Get out of the search loop! */ break; } else { /* Clear the available bytes variable. */ available_bytes = ((ULONG) 0); /* Not enough memory, check to see if the neighbor is free and can be merged. */ work_ptr = TX_UCHAR_POINTER_ADD(next_ptr, (sizeof(UCHAR *))); free_ptr = TX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT(work_ptr); if ((*free_ptr) == TX_BYTE_BLOCK_FREE) { /* Yes, neighbor block can be merged! This is quickly accomplished by updating the current block with the next blocks pointer. */ next_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(next_ptr); *this_block_link_ptr = *next_block_link_ptr; /* Reduce the fragment total. We don't need to increase the bytes available because all free headers are also included in the available count. */ pool_ptr -> tx_byte_pool_fragments--; #ifdef TX_BYTE_POOL_ENABLE_PERFORMANCE_INFO /* Increment the total merge counter. */ _tx_byte_pool_performance_merge_count++; /* Increment the number of blocks merged on this pool. */ pool_ptr -> tx_byte_pool_performance_merge_count++; #endif /* See if the search pointer is affected. */ if (pool_ptr -> tx_byte_pool_search == next_ptr) { /* Yes, update the search pointer. */ pool_ptr -> tx_byte_pool_search = current_ptr; } } else { /* Neighbor is not free so we can skip over it! */ next_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(next_ptr); current_ptr = *next_block_link_ptr; /* Decrement the examined block count to account for this one. */ if (examine_blocks != ((UINT) 0)) { examine_blocks--; #ifdef TX_BYTE_POOL_ENABLE_PERFORMANCE_INFO /* Increment the total fragment search counter. */ _tx_byte_pool_performance_search_count++; /* Increment the number of fragments searched on this pool. */ pool_ptr -> tx_byte_pool_performance_search_count++; #endif } } } } else { /* Block is not free, move to next block. */ this_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(current_ptr); current_ptr = *this_block_link_ptr; } /* Another block has been searched... decrement counter. */ if (examine_blocks != ((UINT) 0)) { examine_blocks--; } /* Restore interrupts temporarily. */ TX_RESTORE /* Disable interrupts. */ TX_DISABLE /* Determine if anything has changed in terms of pool ownership. */ if (pool_ptr -> tx_byte_pool_owner != thread_ptr) { /* Pool changed ownership in the brief period interrupts were enabled. Reset the search. */ current_ptr = pool_ptr -> tx_byte_pool_search; examine_blocks = pool_ptr -> tx_byte_pool_fragments + ((UINT) 1); /* Setup our ownership again. */ pool_ptr -> tx_byte_pool_owner = thread_ptr; } } while(examine_blocks != ((UINT) 0)); /* Determine if a block was found. If so, determine if it needs to be split. */ if (available_bytes != ((ULONG) 0)) { /* Determine if we need to split this block. */ if ((available_bytes - memory_size) >= ((ULONG) TX_BYTE_BLOCK_MIN)) { /* Split the block. */ next_ptr = TX_UCHAR_POINTER_ADD(current_ptr, (memory_size + ((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE))))); /* Setup the new free block. */ next_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(next_ptr); this_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(current_ptr); *next_block_link_ptr = *this_block_link_ptr; work_ptr = TX_UCHAR_POINTER_ADD(next_ptr, (sizeof(UCHAR *))); free_ptr = TX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT(work_ptr); *free_ptr = TX_BYTE_BLOCK_FREE; /* Increase the total fragment counter. */ pool_ptr -> tx_byte_pool_fragments++; /* Update the current pointer to point at the newly created block. */ *this_block_link_ptr = next_ptr; /* Set available equal to memory size for subsequent calculation. */ available_bytes = memory_size; #ifdef TX_BYTE_POOL_ENABLE_PERFORMANCE_INFO /* Increment the total split counter. */ _tx_byte_pool_performance_split_count++; /* Increment the number of blocks split on this pool. */ pool_ptr -> tx_byte_pool_performance_split_count++; #endif } /* In any case, mark the current block as allocated. */ work_ptr = TX_UCHAR_POINTER_ADD(current_ptr, (sizeof(UCHAR *))); this_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(work_ptr); *this_block_link_ptr = TX_BYTE_POOL_TO_UCHAR_POINTER_CONVERT(pool_ptr); /* Reduce the number of available bytes in the pool. */ pool_ptr -> tx_byte_pool_available = (pool_ptr -> tx_byte_pool_available - available_bytes) - ((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE))); /* Determine if the search pointer needs to be updated. This is only done if the search pointer matches the block to be returned. */ if (current_ptr == pool_ptr -> tx_byte_pool_search) { /* Yes, update the search pointer to the next block. */ this_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(current_ptr); pool_ptr -> tx_byte_pool_search = *this_block_link_ptr; } /* Restore interrupts. */ TX_RESTORE /* Adjust the pointer for the application. */ current_ptr = TX_UCHAR_POINTER_ADD(current_ptr, (((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE))))); } else { /* Restore interrupts. */ TX_RESTORE /* Set current pointer to NULL to indicate nothing was found. */ current_ptr = TX_NULL; } } /* Return the search pointer. */ return(current_ptr); }