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 /** Thread - High Level SMP Support */
18 /** */
19 /**************************************************************************/
20 /**************************************************************************/
21
22 #define TX_SOURCE_CODE
23 #define TX_THREAD_SMP_SOURCE_CODE
24
25
26 /* Include necessary system files. */
27
28 #include "tx_api.h"
29 #include "tx_initialize.h"
30 #include "tx_timer.h"
31 #include "tx_thread.h"
32
33
34 /**************************************************************************/
35 /* */
36 /* FUNCTION RELEASE */
37 /* */
38 /* _tx_thread_smp_rebalance_execute_list PORTABLE SMP */
39 /* 6.1 */
40 /* AUTHOR */
41 /* */
42 /* William E. Lamie, Microsoft Corporation */
43 /* */
44 /* DESCRIPTION */
45 /* */
46 /* This function is responsible for mapping ready ThreadX threads with */
47 /* cores in the SMP . The basic idea is the standard ThreadX */
48 /* ready list is traversed to build the _tx_thread_execute_ptr list. */
49 /* Each index represents the and the corresponding entry in this */
50 /* array contains the thread that should be executed by that core. If */
51 /* the was previously running a different thread, it will be */
52 /* preempted and restarted so it can run the new thread. */
53 /* */
54 /* INPUT */
55 /* */
56 /* None */
57 /* */
58 /* OUTPUT */
59 /* */
60 /* None */
61 /* */
62 /* CALLS */
63 /* */
64 /* _tx_thread_smp_execute_list_clear Clear the thread execute list */
65 /* _tx_thread_smp_execute_list_setup Setup the thread execute list */
66 /* _tx_thread_smp_next_priority_find Find next priority with one */
67 /* or more ready threads */
68 /* _tx_thread_smp_remap_solution_find Attempt to remap threads to */
69 /* schedule another thread */
70 /* _tx_thread_smp_schedule_list_clear Clear the thread schedule list*/
71 /* */
72 /* CALLED BY */
73 /* */
74 /* _tx_mutex_priority_change Mutex priority change */
75 /* _tx_thread_create Thread create */
76 /* _tx_thread_preemption_change Thread preemption change */
77 /* _tx_thread_priority_change Thread priority change */
78 /* _tx_thread_relinquish Thread relinquish */
79 /* _tx_thread_resume Thread resume */
80 /* _tx_thread_smp_core_exclude Thread SMP core exclude */
81 /* _tx_thread_system_resume Thread system resume */
82 /* _tx_thread_system_suspend Thread suspend */
83 /* _tx_thread_time_slice Thread time-slice */
84 /* */
85 /* RELEASE HISTORY */
86 /* */
87 /* DATE NAME DESCRIPTION */
88 /* */
89 /* 09-30-2020 William E. Lamie Initial Version 6.1 */
90 /* */
91 /**************************************************************************/
_tx_thread_smp_rebalance_execute_list(UINT core_index)92 void _tx_thread_smp_rebalance_execute_list(UINT core_index)
93 {
94
95 UINT i, j, core;
96 UINT next_priority;
97 UINT last_priority;
98 TX_THREAD *schedule_thread;
99 #ifdef TX_THREAD_ENABLE_PERFORMANCE_INFO
100 TX_THREAD *mapped_thread;
101 #endif
102 TX_THREAD *preempted_thread;
103 ULONG possible_cores;
104 ULONG thread_possible_cores;
105 ULONG available_cores;
106 ULONG test_possible_cores;
107 ULONG test_cores;
108 UINT this_pass_complete;
109 UINT loop_finished;
110
111 #ifdef TX_THREAD_SMP_EQUAL_PRIORITY
112 TX_THREAD *highest_priority_thread;
113 #endif
114 #ifndef TX_DISABLE_PREEMPTION_THRESHOLD
115 ULONG priority_bit;
116 #if TX_MAX_PRIORITIES > 32
117 UINT map_index;
118 #endif
119 #endif
120
121
122 /* It is assumed that the preempt disable flag is still set at this point. */
123
124 /* Pickup the last schedule thread with preemption-threshold enabled. */
125 preempted_thread = _tx_thread_preemption__threshold_scheduled;
126
127 /* Clear the schedule list. */
128 _tx_thread_smp_schedule_list_clear();
129
130 /* Initialize the next priority to 0, the highest priority. */
131 next_priority = ((UINT) 0);
132
133 /* Initialize the last priority. */
134 last_priority = ((UINT) 0);
135
136 #ifndef TX_THREAD_SMP_DYNAMIC_CORE_MAX
137
138 /* Set the possible cores bit map to all cores. */
139 possible_cores = ((ULONG) TX_THREAD_SMP_CORE_MASK);
140 #else
141
142 /* Set the possible cores bit map to all cores. */
143 possible_cores = (((ULONG) 1) << _tx_thread_smp_max_cores) - 1;
144 #endif
145
146 /* Setup the available cores bit map. */
147 available_cores = possible_cores;
148
149 /* Clear the schedule thread pointer. */
150 schedule_thread = TX_NULL;
151
152 #ifdef TX_THREAD_SMP_EQUAL_PRIORITY
153
154 /* Set the highest priority thread to NULL. */
155 highest_priority_thread = TX_NULL;
156 #endif
157
158 /* Loop to rebuild the schedule list. */
159 i = ((UINT) 0);
160 loop_finished = TX_FALSE;
161 do
162 {
163
164 /* Clear the pass complete flag, which is used to skip the remaining processing
165 of this loop on certain conditions. */
166 this_pass_complete = TX_FALSE;
167
168 /* Determine if there is a thread to schedule. */
169 if (schedule_thread == TX_NULL)
170 {
171
172 /* Calculate the next ready priority. */
173 next_priority = _tx_thread_smp_next_priority_find(next_priority);
174
175 /* Determine if there are no more threads to execute. */
176 if (next_priority == ((UINT) TX_MAX_PRIORITIES))
177 {
178
179 /* Break out of loop. */
180 loop_finished = TX_TRUE;
181 this_pass_complete = TX_TRUE;
182 }
183 else
184 {
185
186 /* Determine if a thread was executed with preemption-threshold set. */
187 if (preempted_thread != TX_NULL)
188 {
189
190 /* Yes, a thread was previously preempted. Let's first see if we reached the
191 interrupted preemption-threshold level. */
192 if (next_priority >= preempted_thread -> tx_thread_preempt_threshold)
193 {
194
195 /* Yes, now lets see if we are within the preemption-threshold level. */
196 if (next_priority <= preempted_thread -> tx_thread_priority)
197 {
198
199 /* Yes, move the next priority to the preempted priority. */
200 next_priority = preempted_thread -> tx_thread_priority;
201
202 /* Setup the schedule thread to the preempted thread. */
203 schedule_thread = preempted_thread;
204
205 /* Start at the top of the loop. */
206 this_pass_complete = TX_TRUE;
207 }
208 else
209 {
210
211 /* Nothing else is allowed to execute after the preemption-threshold thread. */
212 next_priority = ((UINT) TX_MAX_PRIORITIES);
213
214 /* Break out of loop. */
215 loop_finished = TX_TRUE;
216 this_pass_complete = TX_TRUE;
217 }
218 }
219 }
220 }
221
222 /* Determine if this pass through the loop is already complete. */
223 if (this_pass_complete == TX_FALSE)
224 {
225
226 /* Pickup the next thread to schedule. */
227 schedule_thread = _tx_thread_priority_list[next_priority];
228 }
229 }
230
231 /* Determine if this pass through the loop is already complete. */
232 if (this_pass_complete == TX_FALSE)
233 {
234
235 /* Determine what the possible cores are for this thread. */
236 thread_possible_cores = schedule_thread -> tx_thread_smp_cores_allowed;
237
238 /* Apply the current possible cores. */
239 thread_possible_cores = thread_possible_cores & (available_cores | possible_cores);
240
241 /* Determine if it is possible to schedule this thread. */
242 if (thread_possible_cores == ((ULONG) 0))
243 {
244
245 /* No, this thread can't be scheduled. */
246
247 /* Look at the next thread at the same priority level. */
248 schedule_thread = schedule_thread -> tx_thread_ready_next;
249
250 /* Determine if this is the head of the list. */
251 if (schedule_thread == _tx_thread_priority_list[next_priority])
252 {
253
254 /* Set the schedule thread to NULL to force examination of the next priority level. */
255 schedule_thread = TX_NULL;
256
257 /* Move to the next priority level. */
258 next_priority++;
259
260 /* Determine if there are no more threads to execute. */
261 if (next_priority == ((UINT) TX_MAX_PRIORITIES))
262 {
263
264 /* Break out of loop. */
265 loop_finished = TX_TRUE;
266 }
267 }
268 }
269 else
270 {
271
272 /* It is possible to schedule this thread. */
273
274 /* Determine if this thread has preemption-threshold set. */
275 if (schedule_thread -> tx_thread_preempt_threshold < schedule_thread -> tx_thread_priority)
276 {
277
278 /* Yes, preemption-threshold is set. */
279
280 /* Determine if the last priority is above the preemption-threshold. If not, we can't
281 schedule this thread with preemption-threshold set. */
282 if ((last_priority >= schedule_thread -> tx_thread_preempt_threshold) && (i != ((UINT) 0)))
283 {
284
285 /* A thread was found that violates the next thread to be scheduled's preemption-threshold. We will simply
286 skip this thread and see if there is anything else we can schedule. */
287
288 /* Look at the next thread at the same priority level. */
289 schedule_thread = schedule_thread -> tx_thread_ready_next;
290
291 /* Determine if this is the head of the list. */
292 if (schedule_thread == _tx_thread_priority_list[next_priority])
293 {
294
295 /* Set the schedule thread to NULL to force examination of the next priority level. */
296 schedule_thread = TX_NULL;
297
298 /* Move to the next priority level. */
299 next_priority++;
300
301 /* Determine if there are no more threads to execute. */
302 if (next_priority == ((UINT) TX_MAX_PRIORITIES))
303 {
304
305 /* Break out of loop. */
306 loop_finished = TX_TRUE;
307 }
308 }
309
310 /* Restart the loop. */
311 this_pass_complete = TX_TRUE;
312 }
313 }
314
315 /* Determine if this pass through the loop is already complete. */
316 if (this_pass_complete == TX_FALSE)
317 {
318
319 #ifdef TX_THREAD_ENABLE_PERFORMANCE_INFO
320
321 /* Initialize index to an invalid value. */
322 j = ((UINT) TX_THREAD_SMP_MAX_CORES);
323 #endif
324
325 /* Determine if there is an available core for this thread to execute on. */
326 if ((thread_possible_cores & available_cores) != ((ULONG) 0))
327 {
328
329 /* Pickup the last executed core for this thread. */
330 j = schedule_thread -> tx_thread_smp_core_mapped;
331
332 /* Is this core valid and available? */
333 if ((thread_possible_cores & available_cores & (((ULONG) 1) << j)) == ((ULONG) 0))
334 {
335
336 /* No, we must find the next core for this thread. */
337 test_cores = (thread_possible_cores & available_cores);
338 TX_LOWEST_SET_BIT_CALCULATE(test_cores, j)
339
340 /* Setup the last executed core for this thread. */
341 schedule_thread -> tx_thread_smp_core_mapped = j;
342 }
343
344 /* Place the this thread on this core. */
345 _tx_thread_smp_schedule_list[j] = schedule_thread;
346
347 /* Clear the associated available cores bit. */
348 available_cores = available_cores & ~(((ULONG) 1) << j);
349 }
350 else
351 {
352
353 /* Note that we know that the thread must have at least one core excluded at this point,
354 since we didn't find a match and we have available cores. */
355
356 /* Now we need to see if one of the other threads in the non-excluded cores can be moved to make room
357 for this thread. */
358
359 /* Determine the possible core remapping attempt. */
360 test_possible_cores = possible_cores & ~(thread_possible_cores);
361
362 /* Attempt to remap the cores in order to schedule this thread. */
363 core = _tx_thread_smp_remap_solution_find(schedule_thread, available_cores, thread_possible_cores, test_possible_cores);
364
365 /* Determine if remapping was successful. */
366 if (core != ((UINT) TX_THREAD_SMP_MAX_CORES))
367 {
368
369 /* Yes, remapping was successful. Update the available cores accordingly. */
370 available_cores = available_cores & ~(((ULONG) 1) << core);
371 }
372 else
373 {
374
375 /* We couldn't assign the thread to any of the cores possible for the thread. */
376
377 /* Check to see if the thread is the last thread preempted. */
378 if (schedule_thread == preempted_thread)
379 {
380
381 /* To honor the preemption-threshold, we cannot schedule any more threads. */
382 loop_finished = TX_TRUE;
383 }
384 else
385 {
386
387 /* update the available cores for the next pass so we don't waste time looking at them again! */
388 possible_cores = possible_cores & (~thread_possible_cores);
389
390 /* No, we couldn't load the thread because none of the required cores were available. Look at the next thread at the same priority level. */
391 schedule_thread = schedule_thread -> tx_thread_ready_next;
392
393 /* Determine if this is the head of the list. */
394 if (schedule_thread == _tx_thread_priority_list[next_priority])
395 {
396
397 /* Set the schedule thread to NULL to force examination of the next priority level. */
398 schedule_thread = TX_NULL;
399
400 /* Move to the next priority level. */
401 next_priority++;
402
403 /* Determine if there are no more threads to execute. */
404 if (next_priority == ((UINT) TX_MAX_PRIORITIES))
405 {
406
407 /* Break out of loop. */
408 loop_finished = TX_TRUE;
409 }
410 }
411 }
412
413 /* Restart the loop. */
414 this_pass_complete = TX_TRUE;
415 }
416 }
417
418 /* Determine if this pass through the loop is already complete. */
419 if (this_pass_complete == TX_FALSE)
420 {
421
422 #ifdef TX_THREAD_SMP_EQUAL_PRIORITY
423
424 /* Determine if this is the highest priority thread. */
425 if (highest_priority_thread == TX_NULL)
426 {
427
428 /* No highest priority yet, remember this thread. */
429 highest_priority_thread = schedule_thread;
430 }
431 #endif
432
433 /* Increment the number of threads loaded. */
434 i++;
435
436 #ifdef TX_THREAD_ENABLE_PERFORMANCE_INFO
437
438 /* Determine if the thread was mapped. */
439 if (j != ((UINT) TX_THREAD_SMP_MAX_CORES))
440 {
441
442 /* Pickup the currently mapped thread. */
443 mapped_thread = _tx_thread_execute_ptr[j];
444
445 /* Determine if preemption is present. */
446 if ((mapped_thread != TX_NULL) && (schedule_thread != mapped_thread))
447 {
448
449 /* Determine if the previously mapped thread is still ready. */
450 if (mapped_thread -> tx_thread_state == TX_READY)
451 {
452
453 /* Determine if the caller is an interrupt or from a thread. */
454 if (_tx_thread_system_state[core_index] == ((ULONG) 0))
455 {
456
457 /* Caller is a thread, so this is a solicited preemption. */
458 _tx_thread_performance_solicited_preemption_count++;
459
460 /* Increment the thread's solicited preemption counter. */
461 mapped_thread -> tx_thread_performance_solicited_preemption_count++;
462 }
463 else
464 {
465
466 /* Is this an interrupt? */
467 if (_tx_thread_system_state[core_index] < TX_INITIALIZE_IN_PROGRESS)
468 {
469
470 /* Caller is an interrupt, so this is an interrupt preemption. */
471 _tx_thread_performance_interrupt_preemption_count++;
472
473 /* Increment the thread's interrupt preemption counter. */
474 mapped_thread -> tx_thread_performance_interrupt_preemption_count++;
475 }
476 }
477 }
478 }
479 }
480 #endif
481
482 /* Determine if this thread has preemption-threshold set. */
483 if (schedule_thread -> tx_thread_preempt_threshold < schedule_thread -> tx_thread_priority)
484 {
485
486 #ifndef TX_DISABLE_PREEMPTION_THRESHOLD
487
488 /* mark the bit map to show that a thread with preemption-threshold has been executed. */
489 #if TX_MAX_PRIORITIES > 32
490
491 /* Calculate the index into the bit map array. */
492 map_index = (schedule_thread -> tx_thread_priority)/((UINT) 32);
493
494 /* Set the active bit to remember that the preempt map has something set. */
495 TX_DIV32_BIT_SET(schedule_thread -> tx_thread_priority, priority_bit)
496 _tx_thread_preempted_map_active = _tx_thread_preempted_map_active | priority_bit;
497 #endif
498
499 /* Remember that this thread was executed with preemption-threshold set. */
500 TX_MOD32_BIT_SET(schedule_thread -> tx_thread_priority, priority_bit)
501 _tx_thread_preempted_maps[MAP_INDEX] = _tx_thread_preempted_maps[MAP_INDEX] | priority_bit;
502
503 /* Place the thread in the preempted list indicating preemption-threshold is in force. */
504 _tx_thread_preemption_threshold_list[schedule_thread -> tx_thread_priority] = schedule_thread;
505 #endif
506
507 /* Set the last thread with preemption-threshold enabled. */
508 _tx_thread_preemption__threshold_scheduled = schedule_thread;
509
510 /* Now break out of the scheduling loop. */
511 loop_finished = TX_TRUE;
512 }
513 else
514 {
515
516 /* Remember the last priority. */
517 last_priority = next_priority;
518
519 /* Pickup the next ready thread at the current priority level. */
520 schedule_thread = schedule_thread -> tx_thread_ready_next;
521
522 /* Determine if this is the head of the list, which implies that we have exhausted this priority level. */
523 if (schedule_thread == _tx_thread_priority_list[next_priority])
524 {
525
526 /* Set the schedule thread to NULL to force examination of the next priority level. */
527 schedule_thread = TX_NULL;
528
529 /* Move to the next priority level. */
530 next_priority++;
531
532 #ifdef TX_THREAD_SMP_EQUAL_PRIORITY
533
534 /* Determine if there is a highest priority thread. */
535 if (highest_priority_thread)
536 {
537
538 /* Yes, break out of the loop, since only same priority threads can be
539 scheduled in this mode. */
540 loop_finished = TX_TRUE;
541 }
542 #endif
543
544 /* Determine if there are no more threads to execute. */
545 if (next_priority == ((UINT) TX_MAX_PRIORITIES))
546 {
547
548 /* Break out of loop. */
549 loop_finished = TX_TRUE;
550 }
551 }
552 }
553 }
554 }
555 }
556 }
557
558 /* Determine if the loop is finished. */
559 if (loop_finished == TX_TRUE)
560 {
561
562 /* Finished, break the loop. */
563 break;
564 }
565
566 #ifndef TX_THREAD_SMP_DYNAMIC_CORE_MAX
567
568 } while (i < ((UINT) TX_THREAD_SMP_MAX_CORES));
569 #else
570
571 } while (i < _tx_thread_smp_max_cores);
572 #endif
573
574 /* Clear the execute list. */
575 _tx_thread_smp_execute_list_clear();
576
577 /* Setup the execute list based on the updated schedule list. */
578 _tx_thread_smp_execute_list_setup(core_index);
579 }
580
581
