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