Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	core/src/ux_utility_memory_byte_pool_search.c	Lines:	43	44	97.7 %
Date:	2026-03-06 18:57:10	Branches:	22	24	91.7 %


/***************************************************************************
 * Copyright (c) 2024 Microsoft Corporation
 * Copyright (c) 2026-present Eclipse ThreadX contributors
 *
 * 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
 **************************************************************************/


/**************************************************************************/
/**************************************************************************/
/**                                                                       */
/** USBX Component                                                        */
/**                                                                       */
/**   USBX main stack                                                     */
/**                                                                       */
/**************************************************************************/
/**************************************************************************/


/* Include necessary system files.  */

#define UX_SOURCE_CODE

#include "ux_api.h"


/**************************************************************************/
/*                                                                        */
/*  FUNCTION                                               RELEASE        */
/*                                                                        */
/*    _ux_utility_memory_byte_pool_search                 PORTABLE C      */
/*                                                           6.3.0        */
/*  AUTHOR                                                                */
/*                                                                        */
/*    Yajun Xia, 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.                                      */
/*                                                                        */
/*  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                                                             */
/*                                                                        */
/*    USBX Components                                                     */
/*                                                                        */
/**************************************************************************/
UCHAR  *_ux_utility_memory_byte_pool_search(UX_MEMORY_BYTE_POOL *pool_ptr, ULONG memory_size)
{
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 =  UX_FALSE;
ALIGN_TYPE          *free_ptr;
UCHAR               *work_ptr;
ULONG               total_theoretical_available;

    /* 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 -> ux_byte_pool_available + ((pool_ptr -> ux_byte_pool_fragments - 2) * UX_MEMORY_BLOCK_HEADER_SIZE);
    if (memory_size >= total_theoretical_available)
    {

        /* Not enough memory, return a NULL pointer.  */
        return(UX_NULL);
    }

    /* Check if the search pointer is valid.  */
    if ((pool_ptr -> ux_byte_pool_search < pool_ptr -> ux_byte_pool_start) ||
        (pool_ptr -> ux_byte_pool_search > pool_ptr -> ux_byte_pool_start + pool_ptr -> ux_byte_pool_size))
    {

        /* Return a NULL pointer.  */
        return(UX_NULL);
    }

    /* Walk through the memory pool in search for a large enough block.  */
    current_ptr =      pool_ptr -> ux_byte_pool_search;
    examine_blocks =   pool_ptr -> ux_byte_pool_fragments + ((UINT) 1);
    available_bytes =  ((ULONG) 0);
    do
    {
        /* Check to see if this block is free.  */
        work_ptr =  UX_UCHAR_POINTER_ADD(current_ptr, (sizeof(UCHAR *)));
        free_ptr =  UX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT(work_ptr);
        if ((*free_ptr) == UX_BYTE_BLOCK_FREE)
        {

            /* Determine if this is the first free block.  */
            if (first_free_block_found == UX_FALSE)
            {
                /* This is the first free block.  */
                pool_ptr->ux_byte_pool_search =  current_ptr;

                /* Set the flag to indicate we have found the first free
                    block.  */
                first_free_block_found =  UX_TRUE;
            }

            /* Block is free, see if it is large enough.  */

            /* Pickup the next block's pointer.  */
            this_block_link_ptr =  UX_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 =   UX_UCHAR_POINTER_DIF(next_ptr, current_ptr);
            available_bytes =   available_bytes - UX_MEMORY_BLOCK_HEADER_SIZE;

            /* 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 =  UX_UCHAR_POINTER_ADD(next_ptr, (sizeof(UCHAR *)));
                free_ptr =  UX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT(work_ptr);
                if ((*free_ptr) == UX_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 =  UX_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 -> ux_byte_pool_fragments--;

                    /* See if the search pointer is affected.  */
                    if (pool_ptr -> ux_byte_pool_search ==  next_ptr)
                    {
                        /* Yes, update the search pointer.   */
                        pool_ptr -> ux_byte_pool_search =  current_ptr;
                    }
                }
                else
                {
                    /* Neighbor is not free so we can skip over it!  */
                    next_block_link_ptr =  UX_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--;
                    }
                }
            }
        }
        else
        {

            /* Block is not free, move to next block.  */
            this_block_link_ptr =  UX_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--;
        }

    } while(examine_blocks != ((UINT) 0));

    /* If a block was found, just return. */
    if (available_bytes == ((ULONG) 0))
    {
        return(UX_NULL);
    }

    /* Return the search pointer.  */
    return(current_ptr);
}


Generated by: GCOVR (Version 4.1)

Line	Branch	Exec	Source
1			/***************************************************************************
2			* Copyright (c) 2024 Microsoft Corporation
3			* Copyright (c) 2026-present Eclipse ThreadX contributors
4			*
5			* This program and the accompanying materials are made available under the
6			* terms of the MIT License which is available at
7			* https://opensource.org/licenses/MIT.
8			*
9			* SPDX-License-Identifier: MIT
10			**************************************************************************/
11
12
13			/**************************************************************************/
14			/**************************************************************************/
15			/** */
16			/** USBX Component */
17			/** */
18			/** USBX main stack */
19			/** */
20			/**************************************************************************/
21			/**************************************************************************/
22
23
24			/* Include necessary system files. */
25
26			#define UX_SOURCE_CODE
27
28			#include "ux_api.h"
29
30
31			/**************************************************************************/
32			/* */
33			/* FUNCTION RELEASE */
34			/* */
35			/* _ux_utility_memory_byte_pool_search PORTABLE C */
36			/* 6.3.0 */
37			/* AUTHOR */
38			/* */
39			/* Yajun Xia, Microsoft Corporation */
40			/* */
41			/* DESCRIPTION */
42			/* */
43			/* This function searches a byte pool for a memory block to satisfy */
44			/* the requested number of bytes. Merging of adjacent free blocks */
45			/* takes place during the search. */
46			/* */
47			/* INPUT */
48			/* */
49			/* pool_ptr Pointer to pool control block */
50			/* memory_size Number of bytes required */
51			/* */
52			/* OUTPUT */
53			/* */
54			/* UCHAR * Pointer to the allocated memory, */
55			/* if successful. Otherwise, a */
56			/* NULL is returned */
57			/* */
58			/* CALLS */
59			/* */
60			/* None */
61			/* */
62			/* CALLED BY */
63			/* */
64			/* USBX Components */
65			/* */
66			/**************************************************************************/
67		343593	UCHAR _ux_utility_memory_byte_pool_search(UX_MEMORY_BYTE_POOL pool_ptr, ULONG memory_size)
68			{
69			UCHAR *current_ptr;
70			UCHAR *next_ptr;
71			UCHAR **this_block_link_ptr;
72			UCHAR **next_block_link_ptr;
73			ULONG available_bytes;
74			UINT examine_blocks;
75		343593	UINT first_free_block_found = UX_FALSE;
76			ALIGN_TYPE *free_ptr;
77			UCHAR *work_ptr;
78			ULONG total_theoretical_available;
79
80			/* First, determine if there are enough bytes in the pool. */
81			/* Theoretical bytes available = free bytes + ((fragments-2) * overhead of each block) */
82		343593	total_theoretical_available = pool_ptr -> ux_byte_pool_available + ((pool_ptr -> ux_byte_pool_fragments - 2) * UX_MEMORY_BLOCK_HEADER_SIZE);
83	✓✓	343593	if (memory_size >= total_theoretical_available)
84			{
85
86			/* Not enough memory, return a NULL pointer. */
87		291	return(UX_NULL);
88			}
89
90			/* Check if the search pointer is valid. */
91	✓✓	343302	if ((pool_ptr -> ux_byte_pool_search < pool_ptr -> ux_byte_pool_start) \|\|
92	✓✓	343286	(pool_ptr -> ux_byte_pool_search > pool_ptr -> ux_byte_pool_start + pool_ptr -> ux_byte_pool_size))
93			{
94
95			/* Return a NULL pointer. */
96		17	return(UX_NULL);
97			}
98
99			/* Walk through the memory pool in search for a large enough block. */
100		343285	current_ptr = pool_ptr -> ux_byte_pool_search;
101		343285	examine_blocks = pool_ptr -> ux_byte_pool_fragments + ((UINT) 1);
102		343285	available_bytes = ((ULONG) 0);
103			do
104			{
105			/* Check to see if this block is free. */
106		12989760	work_ptr = UX_UCHAR_POINTER_ADD(current_ptr, (sizeof(UCHAR *)));
107		12989760	free_ptr = UX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT(work_ptr);
108	✓✓	12989760	if ((*free_ptr) == UX_BYTE_BLOCK_FREE)
109			{
110
111			/* Determine if this is the first free block. */
112	✓✓	702200	if (first_free_block_found == UX_FALSE)
113			{
114			/* This is the first free block. */
115		342564	pool_ptr->ux_byte_pool_search = current_ptr;
116
117			/* Set the flag to indicate we have found the first free
118			block. */
119		342564	first_free_block_found = UX_TRUE;
120			}
121
122			/* Block is free, see if it is large enough. */
123
124			/* Pickup the next block's pointer. */
125		702200	this_block_link_ptr = UX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(current_ptr);
126		702200	next_ptr = *this_block_link_ptr;
127
128			/* Calculate the number of bytes available in this block. */
129		702200	available_bytes = UX_UCHAR_POINTER_DIF(next_ptr, current_ptr);
130		702200	available_bytes = available_bytes - UX_MEMORY_BLOCK_HEADER_SIZE;
131
132			/* If this is large enough, we are done because our first-fit algorithm
133			has been satisfied! */
134	✓✓	702200	if (available_bytes >= memory_size)
135			{
136
137			/* Get out of the search loop! */
138		328251	break;
139			}
140			else
141			{
142
143			/* Clear the available bytes variable. */
144		373949	available_bytes = ((ULONG) 0);
145
146			/* Not enough memory, check to see if the neighbor is
147			free and can be merged. */
148		373949	work_ptr = UX_UCHAR_POINTER_ADD(next_ptr, (sizeof(UCHAR *)));
149		373949	free_ptr = UX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT(work_ptr);
150	✓✓	373949	if ((*free_ptr) == UX_BYTE_BLOCK_FREE)
151			{
152
153			/* Yes, neighbor block can be merged! This is quickly accomplished
154			by updating the current block with the next blocks pointer. */
155		4235	next_block_link_ptr = UX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(next_ptr);
156		4235	this_block_link_ptr = next_block_link_ptr;
157
158			/* Reduce the fragment total. We don't need to increase the bytes
159			available because all free headers are also included in the available
160			count. */
161		4235	pool_ptr -> ux_byte_pool_fragments--;
162
163			/* See if the search pointer is affected. */
164	✗✓	4235	if (pool_ptr -> ux_byte_pool_search == next_ptr)
165			{
166			/* Yes, update the search pointer. */
167			pool_ptr -> ux_byte_pool_search = current_ptr;
168			}
169			}
170			else
171			{
172			/* Neighbor is not free so we can skip over it! */
173		369714	next_block_link_ptr = UX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(next_ptr);
174		369714	current_ptr = *next_block_link_ptr;
175
176			/* Decrement the examined block count to account for this one. */
177	✓✗	369714	if (examine_blocks != ((UINT) 0))
178			{
179		369714	examine_blocks--;
180			}
181			}
182			}
183			}
184			else
185			{
186
187			/* Block is not free, move to next block. */
188		12287560	this_block_link_ptr = UX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(current_ptr);
189		12287560	current_ptr = *this_block_link_ptr;
190			}
191
192			/* Another block has been searched... decrement counter. */
193	✓✓	12661509	if (examine_blocks != ((UINT) 0))
194			{
195
196		12647196	examine_blocks--;
197			}
198
199	✓✓	12661509	} while(examine_blocks != ((UINT) 0));
200
201			/* If a block was found, just return. */
202	✓✓	343285	if (available_bytes == ((ULONG) 0))
203			{
204		15034	return(UX_NULL);
205			}
206
207			/* Return the search pointer. */
208		328251	return(current_ptr);
209			}