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.1.7 */
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 /* */
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 volatile ULONG delay_count;
102 ULONG total_theoretical_available;
103 #ifdef TX_BYTE_POOL_MULTIPLE_BLOCK_SEARCH
104 UINT blocks_searched = ((UINT) 0);
105 #endif
106
107
108 /* Disable interrupts. */
109 TX_DISABLE
110
111 /* First, determine if there are enough bytes in the pool. */
112 /* Theoretical bytes available = free bytes + ((fragments-2) * overhead of each block) */
113 total_theoretical_available = pool_ptr -> tx_byte_pool_available + ((pool_ptr -> tx_byte_pool_fragments - 2) * ((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE))));
114 if (memory_size >= total_theoretical_available)
115 {
116
117 /* Restore interrupts. */
118 TX_RESTORE
119
120 /* Not enough memory, return a NULL pointer. */
121 current_ptr = TX_NULL;
122 }
123 else
124 {
125
126 /* Pickup thread pointer. */
127 TX_THREAD_GET_CURRENT(thread_ptr)
128
129 /* Setup ownership of the byte pool. */
130 pool_ptr -> tx_byte_pool_owner = thread_ptr;
131
132 /* Walk through the memory pool in search for a large enough block. */
133 current_ptr = pool_ptr -> tx_byte_pool_search;
134 examine_blocks = pool_ptr -> tx_byte_pool_fragments + ((UINT) 1);
135 available_bytes = ((ULONG) 0);
136 do
137 {
138
139
140 #ifdef TX_BYTE_POOL_ENABLE_PERFORMANCE_INFO
141
142 /* Increment the total fragment search counter. */
143 _tx_byte_pool_performance_search_count++;
144
145 /* Increment the number of fragments searched on this pool. */
146 pool_ptr -> tx_byte_pool_performance_search_count++;
147 #endif
148
149 /* Check to see if this block is free. */
150 work_ptr = TX_UCHAR_POINTER_ADD(current_ptr, (sizeof(UCHAR *)));
151 free_ptr = TX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT(work_ptr);
152 if ((*free_ptr) == TX_BYTE_BLOCK_FREE)
153 {
154
155 /* Determine if this is the first free block. */
156 if (first_free_block_found == TX_FALSE)
157 {
158 /* This is the first free block. */
159 pool_ptr->tx_byte_pool_search = current_ptr;
160
161 /* Set the flag to indicate we have found the first free
162 block. */
163 first_free_block_found = TX_TRUE;
164 }
165
166 /* Block is free, see if it is large enough. */
167
168 /* Pickup the next block's pointer. */
169 this_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(current_ptr);
170 next_ptr = *this_block_link_ptr;
171
172 /* Calculate the number of bytes available in this block. */
173 available_bytes = TX_UCHAR_POINTER_DIF(next_ptr, current_ptr);
174 available_bytes = available_bytes - ((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE)));
175
176 /* If this is large enough, we are done because our first-fit algorithm
177 has been satisfied! */
178 if (available_bytes >= memory_size)
179 {
180 /* Get out of the search loop! */
181 break;
182 }
183 else
184 {
185
186 /* Clear the available bytes variable. */
187 available_bytes = ((ULONG) 0);
188
189 /* Not enough memory, check to see if the neighbor is
190 free and can be merged. */
191 work_ptr = TX_UCHAR_POINTER_ADD(next_ptr, (sizeof(UCHAR *)));
192 free_ptr = TX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT(work_ptr);
193 if ((*free_ptr) == TX_BYTE_BLOCK_FREE)
194 {
195
196 /* Yes, neighbor block can be merged! This is quickly accomplished
197 by updating the current block with the next blocks pointer. */
198 next_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(next_ptr);
199 *this_block_link_ptr = *next_block_link_ptr;
200
201 /* Reduce the fragment total. We don't need to increase the bytes
202 available because all free headers are also included in the available
203 count. */
204 pool_ptr -> tx_byte_pool_fragments--;
205
206 #ifdef TX_BYTE_POOL_ENABLE_PERFORMANCE_INFO
207
208 /* Increment the total merge counter. */
209 _tx_byte_pool_performance_merge_count++;
210
211 /* Increment the number of blocks merged on this pool. */
212 pool_ptr -> tx_byte_pool_performance_merge_count++;
213 #endif
214
215 /* See if the search pointer is affected. */
216 if (pool_ptr -> tx_byte_pool_search == next_ptr)
217 {
218 /* Yes, update the search pointer. */
219 pool_ptr -> tx_byte_pool_search = current_ptr;
220 }
221 }
222 else
223 {
224 /* Neighbor is not free so we can skip over it! */
225 next_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(next_ptr);
226 current_ptr = *next_block_link_ptr;
227
228 /* Decrement the examined block count to account for this one. */
229 if (examine_blocks != ((UINT) 0))
230 {
231 examine_blocks--;
232
233 #ifdef TX_BYTE_POOL_ENABLE_PERFORMANCE_INFO
234
235 /* Increment the total fragment search counter. */
236 _tx_byte_pool_performance_search_count++;
237
238 /* Increment the number of fragments searched on this pool. */
239 pool_ptr -> tx_byte_pool_performance_search_count++;
240 #endif
241 }
242 }
243 }
244 }
245 else
246 {
247
248 /* Block is not free, move to next block. */
249 this_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(current_ptr);
250 current_ptr = *this_block_link_ptr;
251 }
252
253 /* Another block has been searched... decrement counter. */
254 if (examine_blocks != ((UINT) 0))
255 {
256
257 examine_blocks--;
258 }
259
260 #ifdef TX_BYTE_POOL_MULTIPLE_BLOCK_SEARCH
261
262 /* When this is enabled, multiple blocks are searched while holding the protection. */
263
264 /* Increment the number of blocks searched. */
265 blocks_searched = blocks_searched + ((UINT) 1);
266
267 /* Have we reached the maximum number of blocks to search while holding the protection? */
268 if (blocks_searched >= ((UINT) TX_BYTE_POOL_MULTIPLE_BLOCK_SEARCH))
269 {
270
271 /* Yes, we have exceeded the multiple block search limit. */
272
273 /* Restore interrupts temporarily. */
274 TX_RESTORE
275
276 /* Disable interrupts. */
277 TX_DISABLE
278
279 /* Reset the number of blocks searched counter. */
280 blocks_searched = ((UINT) 0);
281 }
282 #else
283 /* Restore interrupts temporarily. */
284 TX_RESTORE
285
286 /* Disable interrupts. */
287 TX_DISABLE
288 #endif
289 /* Determine if anything has changed in terms of pool ownership. */
290 if (pool_ptr -> tx_byte_pool_owner != thread_ptr)
291 {
292 /* Loop to delay changing the ownership back to avoid thrashing. */
293 delay_count = 0;
294 do
295 {
296 /* Restore interrupts temporarily. */
297 TX_RESTORE
298
299 /* Increment the delay counter. */
300 delay_count++;
301
302 /* Disable interrupts. */
303 TX_DISABLE
304 } while (delay_count < ((ULONG) TX_BYTE_POOL_DELAY_VALUE));
305 /* Pool changed ownership in the brief period interrupts were
306 enabled. Reset the search. */
307 current_ptr = pool_ptr -> tx_byte_pool_search;
308 examine_blocks = pool_ptr -> tx_byte_pool_fragments + ((UINT) 1);
309
310 /* Setup our ownership again. */
311 pool_ptr -> tx_byte_pool_owner = thread_ptr;
312 }
313 } while(examine_blocks != ((UINT) 0));
314
315 /* Determine if a block was found. If so, determine if it needs to be
316 split. */
317 if (available_bytes != ((ULONG) 0))
318 {
319
320 /* Determine if we need to split this block. */
321 if ((available_bytes - memory_size) >= ((ULONG) TX_BYTE_BLOCK_MIN))
322 {
323
324 /* Split the block. */
325 next_ptr = TX_UCHAR_POINTER_ADD(current_ptr, (memory_size + ((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE)))));
326
327 /* Setup the new free block. */
328 next_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(next_ptr);
329 this_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(current_ptr);
330 *next_block_link_ptr = *this_block_link_ptr;
331 work_ptr = TX_UCHAR_POINTER_ADD(next_ptr, (sizeof(UCHAR *)));
332 free_ptr = TX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT(work_ptr);
333 *free_ptr = TX_BYTE_BLOCK_FREE;
334
335 /* Increase the total fragment counter. */
336 pool_ptr -> tx_byte_pool_fragments++;
337
338 /* Update the current pointer to point at the newly created block. */
339 *this_block_link_ptr = next_ptr;
340
341 /* Set available equal to memory size for subsequent calculation. */
342 available_bytes = memory_size;
343
344 #ifdef TX_BYTE_POOL_ENABLE_PERFORMANCE_INFO
345
346 /* Increment the total split counter. */
347 _tx_byte_pool_performance_split_count++;
348
349 /* Increment the number of blocks split on this pool. */
350 pool_ptr -> tx_byte_pool_performance_split_count++;
351 #endif
352 }
353
354 /* In any case, mark the current block as allocated. */
355 work_ptr = TX_UCHAR_POINTER_ADD(current_ptr, (sizeof(UCHAR *)));
356 this_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(work_ptr);
357 *this_block_link_ptr = TX_BYTE_POOL_TO_UCHAR_POINTER_CONVERT(pool_ptr);
358
359 /* Reduce the number of available bytes in the pool. */
360 pool_ptr -> tx_byte_pool_available = (pool_ptr -> tx_byte_pool_available - available_bytes) - ((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE)));
361
362 /* Determine if the search pointer needs to be updated. This is only done
363 if the search pointer matches the block to be returned. */
364 if (current_ptr == pool_ptr -> tx_byte_pool_search)
365 {
366
367 /* Yes, update the search pointer to the next block. */
368 this_block_link_ptr = TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT(current_ptr);
369 pool_ptr -> tx_byte_pool_search = *this_block_link_ptr;
370 }
371
372 /* Restore interrupts. */
373 TX_RESTORE
374
375 /* Adjust the pointer for the application. */
376 current_ptr = TX_UCHAR_POINTER_ADD(current_ptr, (((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE)))));
377 }
378 else
379 {
380
381 /* Restore interrupts. */
382 TX_RESTORE
383
384 /* Set current pointer to NULL to indicate nothing was found. */
385 current_ptr = TX_NULL;
386 }
387 }
388
389 /* Return the search pointer. */
390 return(current_ptr);
391 }
392
393
