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 /** ThreadX Component */
16 /** */
17 /** Byte Pool */
18 /** */
19 /**************************************************************************/
20 /**************************************************************************/
21
22 #define TX_SOURCE_CODE
23
24
25 /* Include necessary system files. */
26
27 #include "tx_api.h"
28 #include "tx_thread.h"
29 #include "tx_byte_pool.h"
30
31
32 /**************************************************************************/
33 /* */
34 /* FUNCTION RELEASE */
35 /* */
36 /* _tx_byte_pool_search PORTABLE C */
37 /* 6.1.7 */
38 /* AUTHOR */
39 /* */
40 /* William E. Lamie, Microsoft Corporation */
41 /* */
42 /* DESCRIPTION */
43 /* */
44 /* This function searches a byte pool for a memory block to satisfy */
45 /* the requested number of bytes. Merging of adjacent free blocks */
46 /* takes place during the search and a split of the block that */
47 /* satisfies the request may occur before this function returns. */
48 /* */
49 /* It is assumed that this function is called with interrupts enabled */
50 /* and with the tx_pool_owner field set to the thread performing the */
51 /* search. Also note that the search can occur during allocation and */
52 /* release of a memory block. */
53 /* */
54 /* INPUT */
55 /* */
56 /* pool_ptr Pointer to pool control block */
57 /* memory_size Number of bytes required */
58 /* */
59 /* OUTPUT */
60 /* */
61 /* UCHAR * Pointer to the allocated memory, */
62 /* if successful. Otherwise, a */
63 /* NULL is returned */
64 /* */
65 /* CALLS */
66 /* */
67 /* None */
68 /* */
69 /* CALLED BY */
70 /* */
71 /* _tx_byte_allocate Allocate bytes of memory */
72 /* _tx_byte_release Release bytes of memory */
73 /* */
74 /* RELEASE HISTORY */
75 /* */
76 /* DATE NAME DESCRIPTION */
77 /* */
78 /* 05-19-2020 William E. Lamie Initial Version 6.0 */
79 /* 09-30-2020 Yuxin Zhou Modified comment(s), */
80 /* resulting in version 6.1 */
81 /* 06-02-2021 Scott Larson Improve possible free bytes */
82 /* calculation, */
83 /* resulting in version 6.1.7 */
84 /* */
85 /**************************************************************************/
_tx_byte_pool_search(TX_BYTE_POOL * pool_ptr,ULONG memory_size)86 UCHAR *_tx_byte_pool_search(TX_BYTE_POOL *pool_ptr, ULONG memory_size)
87 {
88
89 TX_INTERRUPT_SAVE_AREA
90
91 UCHAR *current_ptr;
92 UCHAR *next_ptr;
93 UCHAR **this_block_link_ptr;
94 UCHAR **next_block_link_ptr;
95 ULONG available_bytes;
96 UINT examine_blocks;
97 UINT first_free_block_found = TX_FALSE;
98 TX_THREAD *thread_ptr;
99 ALIGN_TYPE *free_ptr;
100 UCHAR *work_ptr;
101 ULONG total_theoretical_available;
102
103
104 /* Disable interrupts. */
105 TX_DISABLE
106
107 /* First, determine if there are enough bytes in the pool. */
108 /* Theoretical bytes available = free bytes + ((fragments-2) * overhead of each block) */
109 total_theoretical_available = pool_ptr -> tx_byte_pool_available + ((pool_ptr -> tx_byte_pool_fragments - 2) * ((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE))));
110 if (memory_size >= total_theoretical_available)
111 {
112
113 /* Restore interrupts. */
114 TX_RESTORE
115
116 /* Not enough memory, return a NULL pointer. */
117 current_ptr = TX_NULL;
118 }
119 else
120 {
121
122 /* Pickup thread pointer. */
123 TX_THREAD_GET_CURRENT(thread_ptr)
124
125 /* Setup ownership of the byte pool. */
126 pool_ptr -> tx_byte_pool_owner = thread_ptr;
127
128 /* Walk through the memory pool in search for a large enough block. */
129 current_ptr = pool_ptr -> tx_byte_pool_search;
130 examine_blocks = pool_ptr -> tx_byte_pool_fragments + ((UINT) 1);
131 available_bytes = ((ULONG) 0);
132 do
133 {
134
135
136 #ifdef TX_BYTE_POOL_ENABLE_PERFORMANCE_INFO
137
138 /* Increment the total fragment search counter. */
139 _tx_byte_pool_performance_search_count++;
140
141 /* Increment the number of fragments searched on this pool. */
142 pool_ptr -> tx_byte_pool_performance_search_count++;
143 #endif
144
145 /* Check to see if this block is free. */
146 work_ptr = TX_UCHAR_POINTER_ADD(current_ptr, (sizeof(UCHAR *)));
147 free_ptr = TX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT(work_ptr);
148 if ((*free_ptr) == TX_BYTE_BLOCK_FREE)
149 {
150
151 /* Determine if this is the first free block. */
152 if (first_free_block_found == TX_FALSE)
153 {
154 /* This is the first free block. */
155 pool_ptr->tx_byte_pool_search = current_ptr;
156
157 /* Set the flag to indicate we have found the first free
158 block. */
159 first_free_block_found = TX_TRUE;
160 }
161
162 /* Block is free, see if it is large enough. */
163
164 /* Pickup the next block's pointer. */
165 this_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(current_ptr);
166 next_ptr = *this_block_link_ptr;
167
168 /* Calculate the number of bytes available in this block. */
169 available_bytes = TX_UCHAR_POINTER_DIF(next_ptr, current_ptr);
170 available_bytes = available_bytes - ((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE)));
171
172 /* If this is large enough, we are done because our first-fit algorithm
173 has been satisfied! */
174 if (available_bytes >= memory_size)
175 {
176 /* Get out of the search loop! */
177 break;
178 }
179 else
180 {
181
182 /* Clear the available bytes variable. */
183 available_bytes = ((ULONG) 0);
184
185 /* Not enough memory, check to see if the neighbor is
186 free and can be merged. */
187 work_ptr = TX_UCHAR_POINTER_ADD(next_ptr, (sizeof(UCHAR *)));
188 free_ptr = TX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT(work_ptr);
189 if ((*free_ptr) == TX_BYTE_BLOCK_FREE)
190 {
191
192 /* Yes, neighbor block can be merged! This is quickly accomplished
193 by updating the current block with the next blocks pointer. */
194 next_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(next_ptr);
195 *this_block_link_ptr = *next_block_link_ptr;
196
197 /* Reduce the fragment total. We don't need to increase the bytes
198 available because all free headers are also included in the available
199 count. */
200 pool_ptr -> tx_byte_pool_fragments--;
201
202 #ifdef TX_BYTE_POOL_ENABLE_PERFORMANCE_INFO
203
204 /* Increment the total merge counter. */
205 _tx_byte_pool_performance_merge_count++;
206
207 /* Increment the number of blocks merged on this pool. */
208 pool_ptr -> tx_byte_pool_performance_merge_count++;
209 #endif
210
211 /* See if the search pointer is affected. */
212 if (pool_ptr -> tx_byte_pool_search == next_ptr)
213 {
214 /* Yes, update the search pointer. */
215 pool_ptr -> tx_byte_pool_search = current_ptr;
216 }
217 }
218 else
219 {
220 /* Neighbor is not free so we can skip over it! */
221 next_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(next_ptr);
222 current_ptr = *next_block_link_ptr;
223
224 /* Decrement the examined block count to account for this one. */
225 if (examine_blocks != ((UINT) 0))
226 {
227 examine_blocks--;
228
229 #ifdef TX_BYTE_POOL_ENABLE_PERFORMANCE_INFO
230
231 /* Increment the total fragment search counter. */
232 _tx_byte_pool_performance_search_count++;
233
234 /* Increment the number of fragments searched on this pool. */
235 pool_ptr -> tx_byte_pool_performance_search_count++;
236 #endif
237 }
238 }
239 }
240 }
241 else
242 {
243
244 /* Block is not free, move to next block. */
245 this_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(current_ptr);
246 current_ptr = *this_block_link_ptr;
247 }
248
249 /* Another block has been searched... decrement counter. */
250 if (examine_blocks != ((UINT) 0))
251 {
252
253 examine_blocks--;
254 }
255
256 /* Restore interrupts temporarily. */
257 TX_RESTORE
258
259 /* Disable interrupts. */
260 TX_DISABLE
261
262 /* Determine if anything has changed in terms of pool ownership. */
263 if (pool_ptr -> tx_byte_pool_owner != thread_ptr)
264 {
265
266 /* Pool changed ownership in the brief period interrupts were
267 enabled. Reset the search. */
268 current_ptr = pool_ptr -> tx_byte_pool_search;
269 examine_blocks = pool_ptr -> tx_byte_pool_fragments + ((UINT) 1);
270
271 /* Setup our ownership again. */
272 pool_ptr -> tx_byte_pool_owner = thread_ptr;
273 }
274 } while(examine_blocks != ((UINT) 0));
275
276 /* Determine if a block was found. If so, determine if it needs to be
277 split. */
278 if (available_bytes != ((ULONG) 0))
279 {
280
281 /* Determine if we need to split this block. */
282 if ((available_bytes - memory_size) >= ((ULONG) TX_BYTE_BLOCK_MIN))
283 {
284
285 /* Split the block. */
286 next_ptr = TX_UCHAR_POINTER_ADD(current_ptr, (memory_size + ((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE)))));
287
288 /* Setup the new free block. */
289 next_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(next_ptr);
290 this_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(current_ptr);
291 *next_block_link_ptr = *this_block_link_ptr;
292 work_ptr = TX_UCHAR_POINTER_ADD(next_ptr, (sizeof(UCHAR *)));
293 free_ptr = TX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT(work_ptr);
294 *free_ptr = TX_BYTE_BLOCK_FREE;
295
296 /* Increase the total fragment counter. */
297 pool_ptr -> tx_byte_pool_fragments++;
298
299 /* Update the current pointer to point at the newly created block. */
300 *this_block_link_ptr = next_ptr;
301
302 /* Set available equal to memory size for subsequent calculation. */
303 available_bytes = memory_size;
304
305 #ifdef TX_BYTE_POOL_ENABLE_PERFORMANCE_INFO
306
307 /* Increment the total split counter. */
308 _tx_byte_pool_performance_split_count++;
309
310 /* Increment the number of blocks split on this pool. */
311 pool_ptr -> tx_byte_pool_performance_split_count++;
312 #endif
313 }
314
315 /* In any case, mark the current block as allocated. */
316 work_ptr = TX_UCHAR_POINTER_ADD(current_ptr, (sizeof(UCHAR *)));
317 this_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(work_ptr);
318 *this_block_link_ptr = TX_BYTE_POOL_TO_UCHAR_POINTER_CONVERT(pool_ptr);
319
320 /* Reduce the number of available bytes in the pool. */
321 pool_ptr -> tx_byte_pool_available = (pool_ptr -> tx_byte_pool_available - available_bytes) - ((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE)));
322
323 /* Determine if the search pointer needs to be updated. This is only done
324 if the search pointer matches the block to be returned. */
325 if (current_ptr == pool_ptr -> tx_byte_pool_search)
326 {
327
328 /* Yes, update the search pointer to the next block. */
329 this_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(current_ptr);
330 pool_ptr -> tx_byte_pool_search = *this_block_link_ptr;
331 }
332
333 /* Restore interrupts. */
334 TX_RESTORE
335
336 /* Adjust the pointer for the application. */
337 current_ptr = TX_UCHAR_POINTER_ADD(current_ptr, (((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE)))));
338 }
339 else
340 {
341
342 /* Restore interrupts. */
343 TX_RESTORE
344
345 /* Set current pointer to NULL to indicate nothing was found. */
346 current_ptr = TX_NULL;
347 }
348 }
349
350 /* Return the search pointer. */
351 return(current_ptr);
352 }
353
354
