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