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:	2024-12-12 17:16:36	Branches:	22	24	91.7 %


/***************************************************************************
 * 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
 **************************************************************************/


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