source: rtems/cpukit/score/include/rtems/score/schedulerimpl.h @ 900d337f

4.115
Last change on this file since 900d337f was 900d337f, checked in by Sebastian Huber <sebastian.huber@…>, on 05/05/15 at 11:05:54

score: Rework _Thread_Change_priority()

Move the writes to Thread_Control::current_priority and
Thread_Control::real_priority into _Thread_Change_priority() under the
protection of the thread lock. Add a filter function to
_Thread_Change_priority() to enable specialized variants.

Avoid race conditions during a thread priority restore with the new
Thread_Control::priority_restore_hint for an important average case
optimizations used by priority inheritance mutexes.

Update #2273.

  • Property mode set to 100644
File size: 37.7 KB
Line 
1/**
2 * @file
3 *
4 * @brief Inlined Routines Associated with the Manipulation of the Scheduler
5 *
6 * This inline file contains all of the inlined routines associated with
7 * the manipulation of the scheduler.
8 */
9
10/*
11 *  Copyright (C) 2010 Gedare Bloom.
12 *  Copyright (C) 2011 On-Line Applications Research Corporation (OAR).
13 *  Copyright (c) 2014-2015 embedded brains GmbH
14 *
15 *  The license and distribution terms for this file may be
16 *  found in the file LICENSE in this distribution or at
17 *  http://www.rtems.org/license/LICENSE.
18 */
19
20#ifndef _RTEMS_SCORE_SCHEDULERIMPL_H
21#define _RTEMS_SCORE_SCHEDULERIMPL_H
22
23#include <rtems/score/scheduler.h>
24#include <rtems/score/cpusetimpl.h>
25#include <rtems/score/smpimpl.h>
26#include <rtems/score/threadimpl.h>
27
28#ifdef __cplusplus
29extern "C" {
30#endif
31
32/**
33 * @addtogroup ScoreScheduler
34 */
35/**@{**/
36
37/**
38 *  @brief Initializes the scheduler to the policy chosen by the user.
39 *
40 *  This routine initializes the scheduler to the policy chosen by the user
41 *  through confdefs, or to the priority scheduler with ready chains by
42 *  default.
43 */
44void _Scheduler_Handler_initialization( void );
45
46RTEMS_INLINE_ROUTINE Scheduler_Context *_Scheduler_Get_context(
47  const Scheduler_Control *scheduler
48)
49{
50  return scheduler->context;
51}
52
53RTEMS_INLINE_ROUTINE const Scheduler_Control *_Scheduler_Get(
54  const Thread_Control *the_thread
55)
56{
57#if defined(RTEMS_SMP)
58  return the_thread->Scheduler.control;
59#else
60  (void) the_thread;
61
62  return &_Scheduler_Table[ 0 ];
63#endif
64}
65
66RTEMS_INLINE_ROUTINE const Scheduler_Control *_Scheduler_Get_own(
67  const Thread_Control *the_thread
68)
69{
70#if defined(RTEMS_SMP)
71  return the_thread->Scheduler.own_control;
72#else
73  (void) the_thread;
74
75  return &_Scheduler_Table[ 0 ];
76#endif
77}
78
79RTEMS_INLINE_ROUTINE const Scheduler_Control *_Scheduler_Get_by_CPU_index(
80  uint32_t cpu_index
81)
82{
83#if defined(RTEMS_SMP)
84  return _Scheduler_Assignments[ cpu_index ].scheduler;
85#else
86  (void) cpu_index;
87
88  return &_Scheduler_Table[ 0 ];
89#endif
90}
91
92RTEMS_INLINE_ROUTINE const Scheduler_Control *_Scheduler_Get_by_CPU(
93  const Per_CPU_Control *cpu
94)
95{
96  uint32_t cpu_index = _Per_CPU_Get_index( cpu );
97
98  return _Scheduler_Get_by_CPU_index( cpu_index );
99}
100
101RTEMS_INLINE_ROUTINE Scheduler_Node *_Scheduler_Thread_get_own_node(
102  const Thread_Control *the_thread
103)
104{
105#if defined(RTEMS_SMP)
106  return the_thread->Scheduler.own_node;
107#else
108  return the_thread->Scheduler.node;
109#endif
110}
111
112#if defined(RTEMS_SMP)
113RTEMS_INLINE_ROUTINE Thread_Control *_Scheduler_Node_get_user(
114  const Scheduler_Node *node
115)
116{
117  return node->user;
118}
119#endif
120
121/**
122 * The preferred method to add a new scheduler is to define the jump table
123 * entries and add a case to the _Scheduler_Initialize routine.
124 *
125 * Generic scheduling implementations that rely on the ready queue only can
126 * be found in the _Scheduler_queue_XXX functions.
127 */
128
129/*
130 * Passing the Scheduler_Control* to these functions allows for multiple
131 * scheduler's to exist simultaneously, which could be useful on an SMP
132 * system.  Then remote Schedulers may be accessible.  How to protect such
133 * accesses remains an open problem.
134 */
135
136/**
137 * @brief General scheduling decision.
138 *
139 * This kernel routine implements the scheduling decision logic for
140 * the scheduler. It does NOT dispatch.
141 *
142 * @param[in] the_thread The thread which state changed previously.
143 */
144RTEMS_INLINE_ROUTINE void _Scheduler_Schedule( Thread_Control *the_thread )
145{
146  const Scheduler_Control *scheduler = _Scheduler_Get( the_thread );
147
148  ( *scheduler->Operations.schedule )( scheduler, the_thread );
149}
150
151#if defined(RTEMS_SMP)
152typedef struct {
153  Thread_Control *needs_help;
154  Thread_Control *next_needs_help;
155} Scheduler_Ask_for_help_context ;
156
157RTEMS_INLINE_ROUTINE bool _Scheduler_Ask_for_help_visitor(
158  Resource_Node *resource_node,
159  void          *arg
160)
161{
162  bool done;
163  Scheduler_Ask_for_help_context *help_context = arg;
164  Thread_Control *previous_needs_help = help_context->needs_help;
165  Thread_Control *next_needs_help;
166  Thread_Control *offers_help =
167    THREAD_RESOURCE_NODE_TO_THREAD( resource_node );
168  const Scheduler_Control *scheduler = _Scheduler_Get_own( offers_help );
169
170  next_needs_help = ( *scheduler->Operations.ask_for_help )(
171    scheduler,
172    offers_help,
173    previous_needs_help
174  );
175
176  done = next_needs_help != previous_needs_help;
177
178  if ( done ) {
179    help_context->next_needs_help = next_needs_help;
180  }
181
182  return done;
183}
184
185/**
186 * @brief Ask threads depending on resources owned by the thread for help.
187 *
188 * A thread is in need for help if it lost its assigned processor due to
189 * pre-emption by a higher priority thread or it was not possible to assign it
190 * a processor since its priority is to low on its current scheduler instance.
191 *
192 * The run-time of this function depends on the size of the resource tree of
193 * the thread needing help and other resource trees in case threads in need for
194 * help are produced during this operation.
195 *
196 * @param[in] needs_help The thread needing help.
197 */
198RTEMS_INLINE_ROUTINE void _Scheduler_Ask_for_help(
199  Thread_Control *needs_help
200)
201{
202  do {
203    const Scheduler_Control *scheduler = _Scheduler_Get_own( needs_help );
204
205    needs_help = ( *scheduler->Operations.ask_for_help )(
206      scheduler,
207      needs_help,
208      needs_help
209    );
210
211    if ( needs_help != NULL ) {
212      Scheduler_Ask_for_help_context help_context = { needs_help, NULL };
213
214      _Resource_Iterate(
215        &needs_help->Resource_node,
216        _Scheduler_Ask_for_help_visitor,
217        &help_context
218      );
219
220      needs_help = help_context.next_needs_help;
221    }
222  } while ( needs_help != NULL );
223}
224
225RTEMS_INLINE_ROUTINE void _Scheduler_Ask_for_help_if_necessary(
226  Thread_Control *needs_help
227)
228{
229  if (
230    needs_help != NULL
231      && _Resource_Node_owns_resources( &needs_help->Resource_node )
232  ) {
233    Scheduler_Node *node = _Scheduler_Thread_get_own_node( needs_help );
234
235    if (
236      node->help_state != SCHEDULER_HELP_ACTIVE_RIVAL
237        || _Scheduler_Node_get_user( node ) != needs_help
238    ) {
239      _Scheduler_Ask_for_help( needs_help );
240    }
241  }
242}
243#endif
244
245/**
246 * @brief Scheduler yield with a particular thread.
247 *
248 * This routine is invoked when a thread wishes to voluntarily transfer control
249 * of the processor to another thread.
250 *
251 * @param[in] the_thread The yielding thread.
252 */
253RTEMS_INLINE_ROUTINE void _Scheduler_Yield( Thread_Control *the_thread )
254{
255  const Scheduler_Control *scheduler = _Scheduler_Get( the_thread );
256#if defined(RTEMS_SMP)
257  Thread_Control *needs_help;
258
259  needs_help =
260#endif
261  ( *scheduler->Operations.yield )( scheduler, the_thread );
262
263#if defined(RTEMS_SMP)
264  _Scheduler_Ask_for_help_if_necessary( needs_help );
265#endif
266}
267
268/**
269 * @brief Blocks a thread with respect to the scheduler.
270 *
271 * This routine removes @a the_thread from the scheduling decision for
272 * the scheduler. The primary task is to remove the thread from the
273 * ready queue.  It performs any necessary schedulering operations
274 * including the selection of a new heir thread.
275 *
276 * @param[in] the_thread The thread.
277 */
278RTEMS_INLINE_ROUTINE void _Scheduler_Block( Thread_Control *the_thread )
279{
280  const Scheduler_Control *scheduler = _Scheduler_Get( the_thread );
281
282  ( *scheduler->Operations.block )( scheduler, the_thread );
283}
284
285/**
286 * @brief Unblocks a thread with respect to the scheduler.
287 *
288 * This routine adds @a the_thread to the scheduling decision for
289 * the scheduler.  The primary task is to add the thread to the
290 * ready queue per the schedulering policy and update any appropriate
291 * scheduling variables, for example the heir thread.
292 *
293 * @param[in] the_thread The thread.
294 */
295RTEMS_INLINE_ROUTINE void _Scheduler_Unblock( Thread_Control *the_thread )
296{
297  const Scheduler_Control *scheduler = _Scheduler_Get( the_thread );
298#if defined(RTEMS_SMP)
299  Thread_Control *needs_help;
300
301  needs_help =
302#endif
303  ( *scheduler->Operations.unblock )( scheduler, the_thread );
304
305#if defined(RTEMS_SMP)
306  _Scheduler_Ask_for_help_if_necessary( needs_help );
307#endif
308}
309
310/**
311 * @brief Propagates a priority change of a thread to the scheduler.
312 *
313 * The caller must ensure that the thread is in the ready state.  The caller
314 * must ensure that the priority value actually changed and is not equal to the
315 * current priority value.
316 *
317 * The operation must update the heir and thread dispatch necessary variables
318 * in case the set of scheduled threads changes.
319 *
320 * @param[in] the_thread The thread changing its priority.
321 * @param[in] new_priority The new thread priority.
322 * @param[in] prepend_it In case this is true, then enqueue the thread as the
323 * first of its priority group, otherwise enqueue the thread as the last of its
324 * priority group.
325 */
326RTEMS_INLINE_ROUTINE void _Scheduler_Change_priority(
327  Thread_Control          *the_thread,
328  Priority_Control         new_priority,
329  bool                     prepend_it
330)
331{
332  const Scheduler_Control *scheduler = _Scheduler_Get_own( the_thread );
333#if defined(RTEMS_SMP)
334  Thread_Control *needs_help;
335
336  needs_help =
337#endif
338  ( *scheduler->Operations.change_priority )(
339    scheduler,
340    the_thread,
341    new_priority,
342    prepend_it
343  );
344
345#if defined(RTEMS_SMP)
346  _Scheduler_Ask_for_help_if_necessary( needs_help );
347#endif
348}
349
350/**
351 * @brief Initializes a scheduler node.
352 *
353 * The scheduler node contains arbitrary data on function entry.  The caller
354 * must ensure that _Scheduler_Node_destroy() will be called after a
355 * _Scheduler_Node_initialize() before the memory of the scheduler node is
356 * destroyed.
357 *
358 * @param[in] scheduler The scheduler instance.
359 * @param[in] the_thread The thread containing the scheduler node.
360 */
361RTEMS_INLINE_ROUTINE void _Scheduler_Node_initialize(
362  const Scheduler_Control *scheduler,
363  Thread_Control          *the_thread
364)
365{
366  return ( *scheduler->Operations.node_initialize )( scheduler, the_thread );
367}
368
369/**
370 * @brief Destroys a scheduler node.
371 *
372 * The caller must ensure that _Scheduler_Node_destroy() will be called only
373 * after a corresponding _Scheduler_Node_initialize().
374 *
375 * @param[in] scheduler The scheduler instance.
376 * @param[in] the_thread The thread containing the scheduler node.
377 */
378RTEMS_INLINE_ROUTINE void _Scheduler_Node_destroy(
379  const Scheduler_Control *scheduler,
380  Thread_Control          *the_thread
381)
382{
383  ( *scheduler->Operations.node_destroy )( scheduler, the_thread );
384}
385
386/**
387 * @brief Updates the scheduler about a priority change of a not ready thread.
388 *
389 * @param[in] the_thread The thread.
390 * @param[in] new_priority The new priority of the thread.
391 */
392RTEMS_INLINE_ROUTINE void _Scheduler_Update_priority(
393  Thread_Control   *the_thread,
394  Priority_Control  new_priority
395)
396{
397  const Scheduler_Control *scheduler = _Scheduler_Get( the_thread );
398
399  ( *scheduler->Operations.update_priority )(
400    scheduler,
401    the_thread,
402    new_priority
403  );
404}
405
406/**
407 * @brief Compares two priority values.
408 *
409 * @param[in] scheduler The scheduler instance.
410 * @param[in] p1 The first priority value.
411 * @param[in] p2 The second priority value.
412 *
413 * @retval negative The value @a p1 encodes a lower priority than @a p2 in the
414 * intuitive sense of priority.
415 * @retval 0 The priorities @a p1 and @a p2 are equal.
416 * @retval positive The value @a p1 encodes a higher priority than @a p2 in the
417 * intuitive sense of priority.
418 *
419 * @see _Scheduler_Is_priority_lower_than() and
420 * _Scheduler_Is_priority_higher_than().
421 */
422RTEMS_INLINE_ROUTINE int _Scheduler_Priority_compare(
423  const Scheduler_Control *scheduler,
424  Priority_Control         p1,
425  Priority_Control         p2
426)
427{
428  return ( *scheduler->Operations.priority_compare )( p1, p2 );
429}
430
431/**
432 * @brief Releases a job of a thread with respect to the scheduler.
433 *
434 * @param[in] the_thread The thread.
435 * @param[in] length The period length.
436 */
437RTEMS_INLINE_ROUTINE void _Scheduler_Release_job(
438  Thread_Control *the_thread,
439  uint32_t        length
440)
441{
442  const Scheduler_Control *scheduler = _Scheduler_Get( the_thread );
443
444  ( *scheduler->Operations.release_job )( scheduler, the_thread, length );
445}
446
447/**
448 * @brief Scheduler method invoked at each clock tick.
449 *
450 * This method is invoked at each clock tick to allow the scheduler
451 * implementation to perform any activities required.  For the
452 * scheduler which support standard RTEMS features, this includes
453 * time-slicing management.
454 */
455RTEMS_INLINE_ROUTINE void _Scheduler_Tick( void )
456{
457  uint32_t cpu_count = _SMP_Get_processor_count();
458  uint32_t cpu_index;
459
460  for ( cpu_index = 0 ; cpu_index < cpu_count ; ++cpu_index ) {
461    const Per_CPU_Control *cpu = _Per_CPU_Get_by_index( cpu_index );
462    const Scheduler_Control *scheduler = _Scheduler_Get_by_CPU( cpu );
463    Thread_Control *executing = cpu->executing;
464
465    if ( scheduler != NULL && executing != NULL ) {
466      ( *scheduler->Operations.tick )( scheduler, executing );
467    }
468  }
469}
470
471/**
472 * @brief Starts the idle thread for a particular processor.
473 *
474 * @param[in] scheduler The scheduler instance.
475 * @param[in,out] the_thread The idle thread for the processor.
476 * @param[in,out] cpu The processor for the idle thread.
477 *
478 * @see _Thread_Create_idle().
479 */
480RTEMS_INLINE_ROUTINE void _Scheduler_Start_idle(
481  const Scheduler_Control *scheduler,
482  Thread_Control          *the_thread,
483  Per_CPU_Control         *cpu
484)
485{
486  ( *scheduler->Operations.start_idle )( scheduler, the_thread, cpu );
487}
488
489#if defined(RTEMS_SMP)
490RTEMS_INLINE_ROUTINE const Scheduler_Assignment *_Scheduler_Get_assignment(
491  uint32_t cpu_index
492)
493{
494  return &_Scheduler_Assignments[ cpu_index ];
495}
496
497RTEMS_INLINE_ROUTINE bool _Scheduler_Is_mandatory_processor(
498  const Scheduler_Assignment *assignment
499)
500{
501  return (assignment->attributes & SCHEDULER_ASSIGN_PROCESSOR_MANDATORY) != 0;
502}
503
504RTEMS_INLINE_ROUTINE bool _Scheduler_Should_start_processor(
505  const Scheduler_Assignment *assignment
506)
507{
508  return assignment->scheduler != NULL;
509}
510#endif /* defined(RTEMS_SMP) */
511
512RTEMS_INLINE_ROUTINE bool _Scheduler_Has_processor_ownership(
513  const Scheduler_Control *scheduler,
514  uint32_t cpu_index
515)
516{
517#if defined(RTEMS_SMP)
518  const Scheduler_Assignment *assignment =
519    _Scheduler_Get_assignment( cpu_index );
520
521  return assignment->scheduler == scheduler;
522#else
523  (void) scheduler;
524  (void) cpu_index;
525
526  return true;
527#endif
528}
529
530RTEMS_INLINE_ROUTINE void _Scheduler_Set(
531  const Scheduler_Control *scheduler,
532  Thread_Control          *the_thread
533)
534{
535#if defined(RTEMS_SMP)
536  const Scheduler_Control *current_scheduler = _Scheduler_Get( the_thread );
537
538  if ( current_scheduler != scheduler ) {
539    _Thread_Set_state( the_thread, STATES_MIGRATING );
540    _Scheduler_Node_destroy( current_scheduler, the_thread );
541    the_thread->Scheduler.own_control = scheduler;
542    the_thread->Scheduler.control = scheduler;
543    _Scheduler_Node_initialize( scheduler, the_thread );
544    _Scheduler_Update_priority( the_thread, the_thread->current_priority );
545    _Thread_Clear_state( the_thread, STATES_MIGRATING );
546  }
547#else
548  (void) scheduler;
549#endif
550}
551
552#if defined(__RTEMS_HAVE_SYS_CPUSET_H__)
553
554RTEMS_INLINE_ROUTINE void _Scheduler_Get_processor_set(
555  const Scheduler_Control *scheduler,
556  size_t                   cpusetsize,
557  cpu_set_t               *cpuset
558)
559{
560  uint32_t cpu_count = _SMP_Get_processor_count();
561  uint32_t cpu_index;
562
563  CPU_ZERO_S( cpusetsize, cpuset );
564
565  for ( cpu_index = 0 ; cpu_index < cpu_count ; ++cpu_index ) {
566#if defined(RTEMS_SMP)
567    if ( _Scheduler_Has_processor_ownership( scheduler, cpu_index ) ) {
568      CPU_SET_S( (int) cpu_index, cpusetsize, cpuset );
569    }
570#else
571    (void) scheduler;
572
573    CPU_SET_S( (int) cpu_index, cpusetsize, cpuset );
574#endif
575  }
576}
577
578RTEMS_INLINE_ROUTINE bool _Scheduler_default_Get_affinity_body(
579  const Scheduler_Control *scheduler,
580  Thread_Control          *the_thread,
581  size_t                   cpusetsize,
582  cpu_set_t               *cpuset
583)
584{
585  (void) the_thread;
586
587  _Scheduler_Get_processor_set( scheduler, cpusetsize, cpuset );
588
589  return true;
590}
591
592bool _Scheduler_Get_affinity(
593  Thread_Control *the_thread,
594  size_t          cpusetsize,
595  cpu_set_t      *cpuset
596);
597
598RTEMS_INLINE_ROUTINE bool _Scheduler_default_Set_affinity_body(
599  const Scheduler_Control *scheduler,
600  Thread_Control          *the_thread,
601  size_t                   cpusetsize,
602  const cpu_set_t         *cpuset
603)
604{
605  uint32_t cpu_count = _SMP_Get_processor_count();
606  uint32_t cpu_index;
607  bool     ok = true;
608
609  for ( cpu_index = 0 ; cpu_index < cpu_count ; ++cpu_index ) {
610#if defined(RTEMS_SMP)
611    const Scheduler_Control *scheduler_of_cpu =
612      _Scheduler_Get_by_CPU_index( cpu_index );
613
614    ok = ok
615      && ( CPU_ISSET_S( (int) cpu_index, cpusetsize, cpuset )
616        || ( !CPU_ISSET_S( (int) cpu_index, cpusetsize, cpuset )
617          && scheduler != scheduler_of_cpu ) );
618#else
619    (void) scheduler;
620
621    ok = ok && CPU_ISSET_S( (int) cpu_index, cpusetsize, cpuset );
622#endif
623  }
624
625  return ok;
626}
627
628bool _Scheduler_Set_affinity(
629  Thread_Control          *the_thread,
630  size_t                   cpusetsize,
631  const cpu_set_t         *cpuset
632);
633
634#endif /* defined(__RTEMS_HAVE_SYS_CPUSET_H__) */
635
636RTEMS_INLINE_ROUTINE void _Scheduler_Update_heir(
637  Thread_Control *new_heir,
638  bool            force_dispatch
639)
640{
641  Thread_Control *heir = _Thread_Heir;
642
643  if ( heir != new_heir && ( heir->is_preemptible || force_dispatch ) ) {
644    _Thread_Heir = new_heir;
645    _Thread_Dispatch_necessary = true;
646  }
647}
648
649RTEMS_INLINE_ROUTINE void _Scheduler_Generic_block(
650  const Scheduler_Control *scheduler,
651  Thread_Control          *the_thread,
652  void                  ( *extract )(
653                             const Scheduler_Control *,
654                             Thread_Control * ),
655  void                  ( *schedule )(
656                             const Scheduler_Control *,
657                             Thread_Control *,
658                             bool )
659)
660{
661  ( *extract )( scheduler, the_thread );
662
663  /* TODO: flash critical section? */
664
665  if ( _Thread_Is_executing( the_thread ) || _Thread_Is_heir( the_thread ) ) {
666    ( *schedule )( scheduler, the_thread, true );
667  }
668}
669
670/**
671 * @brief Returns true if @a p1 encodes a lower priority than @a p2 in the
672 * intuitive sense of priority.
673 */
674RTEMS_INLINE_ROUTINE bool _Scheduler_Is_priority_lower_than(
675  const Scheduler_Control *scheduler,
676  Priority_Control         p1,
677  Priority_Control         p2
678)
679{
680  return _Scheduler_Priority_compare( scheduler, p1,  p2 ) < 0;
681}
682
683/**
684 * @brief Returns true if @a p1 encodes a higher priority than @a p2 in the
685 * intuitive sense of priority.
686 */
687RTEMS_INLINE_ROUTINE bool _Scheduler_Is_priority_higher_than(
688  const Scheduler_Control *scheduler,
689  Priority_Control         p1,
690  Priority_Control         p2
691)
692{
693  return _Scheduler_Priority_compare( scheduler, p1,  p2 ) > 0;
694}
695
696RTEMS_INLINE_ROUTINE uint32_t _Scheduler_Get_processor_count(
697  const Scheduler_Control *scheduler
698)
699{
700#if defined(RTEMS_SMP)
701  return _Scheduler_Get_context( scheduler )->processor_count;
702#else
703  (void) scheduler;
704
705  return 1;
706#endif
707}
708
709RTEMS_INLINE_ROUTINE Objects_Id _Scheduler_Build_id( uint32_t scheduler_index )
710{
711  return _Objects_Build_id(
712    OBJECTS_FAKE_OBJECTS_API,
713    OBJECTS_FAKE_OBJECTS_SCHEDULERS,
714    _Objects_Local_node,
715    scheduler_index + 1
716  );
717}
718
719RTEMS_INLINE_ROUTINE uint32_t _Scheduler_Get_index_by_id( Objects_Id id )
720{
721  uint32_t minimum_id = _Scheduler_Build_id( 0 );
722
723  return id - minimum_id;
724}
725
726RTEMS_INLINE_ROUTINE bool _Scheduler_Get_by_id(
727  Objects_Id                id,
728  const Scheduler_Control **scheduler_p
729)
730{
731  uint32_t index = _Scheduler_Get_index_by_id( id );
732  const Scheduler_Control *scheduler = &_Scheduler_Table[ index ];
733
734  *scheduler_p = scheduler;
735
736  return index < _Scheduler_Count
737    && _Scheduler_Get_processor_count( scheduler ) > 0;
738}
739
740RTEMS_INLINE_ROUTINE bool _Scheduler_Is_id_valid( Objects_Id id )
741{
742  const Scheduler_Control *scheduler;
743  bool ok = _Scheduler_Get_by_id( id, &scheduler );
744
745  (void) scheduler;
746
747  return ok;
748}
749
750RTEMS_INLINE_ROUTINE uint32_t _Scheduler_Get_index(
751  const Scheduler_Control *scheduler
752)
753{
754  return (uint32_t) (scheduler - &_Scheduler_Table[ 0 ]);
755}
756
757RTEMS_INLINE_ROUTINE Scheduler_Node *_Scheduler_Thread_get_node(
758  const Thread_Control *the_thread
759)
760{
761  return the_thread->Scheduler.node;
762}
763
764RTEMS_INLINE_ROUTINE void _Scheduler_Node_do_initialize(
765  Scheduler_Node *node,
766  Thread_Control *the_thread
767)
768{
769#if defined(RTEMS_SMP)
770  node->user = the_thread;
771  node->help_state = SCHEDULER_HELP_YOURSELF;
772  node->owner = the_thread;
773  node->idle = NULL;
774  node->accepts_help = the_thread;
775#else
776  (void) node;
777  (void) the_thread;
778#endif
779}
780
781#if defined(RTEMS_SMP)
782/**
783 * @brief Gets an idle thread from the scheduler instance.
784 *
785 * @param[in] context The scheduler instance context.
786 *
787 * @retval idle An idle thread for use.  This function must always return an
788 * idle thread.  If none is available, then this is a fatal error.
789 */
790typedef Thread_Control *( *Scheduler_Get_idle_thread )(
791  Scheduler_Context *context
792);
793
794/**
795 * @brief Releases an idle thread to the scheduler instance for reuse.
796 *
797 * @param[in] context The scheduler instance context.
798 * @param[in] idle The idle thread to release
799 */
800typedef void ( *Scheduler_Release_idle_thread )(
801  Scheduler_Context *context,
802  Thread_Control    *idle
803);
804
805RTEMS_INLINE_ROUTINE Thread_Control *_Scheduler_Node_get_owner(
806  const Scheduler_Node *node
807)
808{
809  return node->owner;
810}
811
812RTEMS_INLINE_ROUTINE Thread_Control *_Scheduler_Node_get_idle(
813  const Scheduler_Node *node
814)
815{
816  return node->idle;
817}
818
819RTEMS_INLINE_ROUTINE void _Scheduler_Node_set_user(
820  Scheduler_Node *node,
821  Thread_Control *user
822)
823{
824  node->user = user;
825}
826
827RTEMS_INLINE_ROUTINE void _Scheduler_Thread_set_node(
828  Thread_Control *the_thread,
829  Scheduler_Node *node
830)
831{
832  the_thread->Scheduler.node = node;
833}
834
835RTEMS_INLINE_ROUTINE void _Scheduler_Thread_set_scheduler_and_node(
836  Thread_Control       *the_thread,
837  Scheduler_Node       *node,
838  const Thread_Control *previous_user_of_node
839)
840{
841  const Scheduler_Control *scheduler =
842    _Scheduler_Get_own( previous_user_of_node );
843
844  the_thread->Scheduler.control = scheduler;
845  _Scheduler_Thread_set_node( the_thread, node );
846}
847
848extern const bool _Scheduler_Thread_state_valid_state_changes[ 3 ][ 3 ];
849
850RTEMS_INLINE_ROUTINE void _Scheduler_Thread_change_state(
851  Thread_Control         *the_thread,
852  Thread_Scheduler_state  new_state
853)
854{
855  _Assert(
856    _Scheduler_Thread_state_valid_state_changes
857      [ the_thread->Scheduler.state ][ new_state ]
858  );
859
860  the_thread->Scheduler.state = new_state;
861}
862
863/**
864 * @brief Changes the scheduler help state of a thread.
865 *
866 * @param[in] the_thread The thread.
867 * @param[in] new_help_state The new help state.
868 *
869 * @return The previous help state.
870 */
871RTEMS_INLINE_ROUTINE Scheduler_Help_state _Scheduler_Thread_change_help_state(
872  Thread_Control       *the_thread,
873  Scheduler_Help_state  new_help_state
874)
875{
876  Scheduler_Node *node = _Scheduler_Thread_get_own_node( the_thread );
877  Scheduler_Help_state previous_help_state = node->help_state;
878
879  node->help_state = new_help_state;
880
881  return previous_help_state;
882}
883
884/**
885 * @brief Changes the resource tree root of a thread.
886 *
887 * For each node of the resource sub-tree specified by the top thread the
888 * scheduler asks for help.  So the root thread gains access to all scheduler
889 * nodes corresponding to the resource sub-tree.  In case a thread previously
890 * granted help is displaced by this operation, then the scheduler asks for
891 * help using its remaining resource tree.
892 *
893 * The run-time of this function depends on the size of the resource sub-tree
894 * and other resource trees in case threads in need for help are produced
895 * during this operation.
896 *
897 * @param[in] top The thread specifying the resource sub-tree top.
898 * @param[in] root The thread specifying the new resource sub-tree root.
899 */
900void _Scheduler_Thread_change_resource_root(
901  Thread_Control *top,
902  Thread_Control *root
903);
904
905RTEMS_INLINE_ROUTINE void _Scheduler_Set_idle_thread(
906  Scheduler_Node *node,
907  Thread_Control *idle
908)
909{
910  _Assert(
911    node->help_state == SCHEDULER_HELP_ACTIVE_OWNER
912      || node->help_state == SCHEDULER_HELP_ACTIVE_RIVAL
913  );
914  _Assert( _Scheduler_Node_get_idle( node ) == NULL );
915  _Assert(
916    _Scheduler_Node_get_owner( node ) == _Scheduler_Node_get_user( node )
917  );
918
919  _Scheduler_Thread_set_node( idle, node );
920
921  _Scheduler_Node_set_user( node, idle );
922  node->idle = idle;
923}
924
925/**
926 * @brief Use an idle thread for this scheduler node.
927 *
928 * A thread in the SCHEDULER_HELP_ACTIVE_OWNER or SCHEDULER_HELP_ACTIVE_RIVAL
929 * helping state may use an idle thread for the scheduler node owned by itself
930 * in case it executes currently using another scheduler node or in case it is
931 * in a blocking state.
932 *
933 * @param[in] context The scheduler instance context.
934 * @param[in] node The node which wants to use the idle thread.
935 * @param[in] get_idle_thread Function to get an idle thread.
936 */
937RTEMS_INLINE_ROUTINE Thread_Control *_Scheduler_Use_idle_thread(
938  Scheduler_Context         *context,
939  Scheduler_Node            *node,
940  Scheduler_Get_idle_thread  get_idle_thread
941)
942{
943  Thread_Control *idle = ( *get_idle_thread )( context );
944
945  _Scheduler_Set_idle_thread( node, idle );
946
947  return idle;
948}
949
950typedef enum {
951  SCHEDULER_TRY_TO_SCHEDULE_DO_SCHEDULE,
952  SCHEDULER_TRY_TO_SCHEDULE_DO_IDLE_EXCHANGE,
953  SCHEDULER_TRY_TO_SCHEDULE_DO_BLOCK
954} Scheduler_Try_to_schedule_action;
955
956/**
957 * @brief Try to schedule this scheduler node.
958 *
959 * @param[in] context The scheduler instance context.
960 * @param[in] node The node which wants to get scheduled.
961 * @param[in] idle A potential idle thread used by a potential victim node.
962 * @param[in] get_idle_thread Function to get an idle thread.
963 *
964 * @retval true This node can be scheduled.
965 * @retval false Otherwise.
966 */
967RTEMS_INLINE_ROUTINE Scheduler_Try_to_schedule_action
968_Scheduler_Try_to_schedule_node(
969  Scheduler_Context         *context,
970  Scheduler_Node            *node,
971  Thread_Control            *idle,
972  Scheduler_Get_idle_thread  get_idle_thread
973)
974{
975  Scheduler_Try_to_schedule_action action;
976  Thread_Control *owner;
977  Thread_Control *user;
978
979  action = SCHEDULER_TRY_TO_SCHEDULE_DO_SCHEDULE;
980
981  if ( node->help_state == SCHEDULER_HELP_YOURSELF ) {
982    return action;
983  }
984
985  owner = _Scheduler_Node_get_owner( node );
986  user = _Scheduler_Node_get_user( node );
987
988  if ( node->help_state == SCHEDULER_HELP_ACTIVE_RIVAL) {
989    if ( user->Scheduler.state == THREAD_SCHEDULER_READY ) {
990      _Scheduler_Thread_set_scheduler_and_node( user, node, owner );
991    } else if ( owner->Scheduler.state == THREAD_SCHEDULER_BLOCKED ) {
992      if ( idle != NULL ) {
993        action = SCHEDULER_TRY_TO_SCHEDULE_DO_IDLE_EXCHANGE;
994      } else {
995        _Scheduler_Use_idle_thread( context, node, get_idle_thread );
996      }
997    } else {
998      _Scheduler_Node_set_user( node, owner );
999    }
1000  } else if ( node->help_state == SCHEDULER_HELP_ACTIVE_OWNER ) {
1001    if ( user->Scheduler.state == THREAD_SCHEDULER_READY ) {
1002      _Scheduler_Thread_set_scheduler_and_node( user, node, owner );
1003    } else if ( idle != NULL ) {
1004      action = SCHEDULER_TRY_TO_SCHEDULE_DO_IDLE_EXCHANGE;
1005    } else {
1006      _Scheduler_Use_idle_thread( context, node, get_idle_thread );
1007    }
1008  } else {
1009    _Assert( node->help_state == SCHEDULER_HELP_PASSIVE );
1010
1011    if ( user->Scheduler.state == THREAD_SCHEDULER_READY ) {
1012      _Scheduler_Thread_set_scheduler_and_node( user, node, owner );
1013    } else {
1014      action = SCHEDULER_TRY_TO_SCHEDULE_DO_BLOCK;
1015    }
1016  }
1017
1018  return action;
1019}
1020
1021/**
1022 * @brief Release an idle thread using this scheduler node.
1023 *
1024 * @param[in] context The scheduler instance context.
1025 * @param[in] node The node which may have an idle thread as user.
1026 * @param[in] release_idle_thread Function to release an idle thread.
1027 *
1028 * @retval idle The idle thread which used this node.
1029 * @retval NULL This node had no idle thread as an user.
1030 */
1031RTEMS_INLINE_ROUTINE Thread_Control *_Scheduler_Release_idle_thread(
1032  Scheduler_Context             *context,
1033  Scheduler_Node                *node,
1034  Scheduler_Release_idle_thread  release_idle_thread
1035)
1036{
1037  Thread_Control *idle = _Scheduler_Node_get_idle( node );
1038
1039  if ( idle != NULL ) {
1040    Thread_Control *owner = _Scheduler_Node_get_owner( node );
1041
1042    node->idle = NULL;
1043    _Scheduler_Node_set_user( node, owner );
1044    _Scheduler_Thread_change_state( idle, THREAD_SCHEDULER_READY );
1045    _Scheduler_Thread_set_node( idle, idle->Scheduler.own_node );
1046
1047    ( *release_idle_thread )( context, idle );
1048  }
1049
1050  return idle;
1051}
1052
1053RTEMS_INLINE_ROUTINE void _Scheduler_Exchange_idle_thread(
1054  Scheduler_Node *needs_idle,
1055  Scheduler_Node *uses_idle,
1056  Thread_Control *idle
1057)
1058{
1059  uses_idle->idle = NULL;
1060  _Scheduler_Node_set_user(
1061    uses_idle,
1062    _Scheduler_Node_get_owner( uses_idle )
1063  );
1064  _Scheduler_Set_idle_thread( needs_idle, idle );
1065}
1066
1067/**
1068 * @brief Block this scheduler node.
1069 *
1070 * @param[in] context The scheduler instance context.
1071 * @param[in] thread The thread which wants to get blocked referencing this
1072 *   node.  This is not necessarily the user of this node in case the node
1073 *   participates in the scheduler helping protocol.
1074 * @param[in] node The node which wants to get blocked.
1075 * @param[in] is_scheduled This node is scheduled.
1076 * @param[in] get_idle_thread Function to get an idle thread.
1077 *
1078 * @retval true Continue with the blocking operation.
1079 * @retval false Otherwise.
1080 */
1081RTEMS_INLINE_ROUTINE bool _Scheduler_Block_node(
1082  Scheduler_Context         *context,
1083  Thread_Control            *thread,
1084  Scheduler_Node            *node,
1085  bool                       is_scheduled,
1086  Scheduler_Get_idle_thread  get_idle_thread
1087)
1088{
1089  Thread_Control *old_user;
1090  Thread_Control *new_user;
1091
1092  _Scheduler_Thread_change_state( thread, THREAD_SCHEDULER_BLOCKED );
1093
1094  if ( node->help_state == SCHEDULER_HELP_YOURSELF ) {
1095    _Assert( thread == _Scheduler_Node_get_user( node ) );
1096
1097    return true;
1098  }
1099
1100  new_user = NULL;
1101
1102  if ( node->help_state == SCHEDULER_HELP_ACTIVE_OWNER ) {
1103    if ( is_scheduled ) {
1104      _Assert( thread == _Scheduler_Node_get_user( node ) );
1105      old_user = thread;
1106      new_user = _Scheduler_Use_idle_thread( context, node, get_idle_thread );
1107    }
1108  } else if ( node->help_state == SCHEDULER_HELP_ACTIVE_RIVAL ) {
1109    if ( is_scheduled ) {
1110      old_user = _Scheduler_Node_get_user( node );
1111
1112      if ( thread == old_user ) {
1113        Thread_Control *owner = _Scheduler_Node_get_owner( node );
1114
1115        if (
1116          thread != owner
1117            && owner->Scheduler.state == THREAD_SCHEDULER_READY
1118        ) {
1119          new_user = owner;
1120          _Scheduler_Node_set_user( node, new_user );
1121        } else {
1122          new_user = _Scheduler_Use_idle_thread( context, node, get_idle_thread );
1123        }
1124      }
1125    }
1126  } else {
1127    /* Not implemented, this is part of the OMIP support path. */
1128    _Assert(0);
1129  }
1130
1131  if ( new_user != NULL ) {
1132    Per_CPU_Control *cpu = _Thread_Get_CPU( old_user );
1133
1134    _Scheduler_Thread_change_state( new_user, THREAD_SCHEDULER_SCHEDULED );
1135    _Thread_Set_CPU( new_user, cpu );
1136    _Thread_Dispatch_update_heir( _Per_CPU_Get(), cpu, new_user );
1137  }
1138
1139  return false;
1140}
1141
1142/**
1143 * @brief Unblock this scheduler node.
1144 *
1145 * @param[in] context The scheduler instance context.
1146 * @param[in] the_thread The thread which wants to get unblocked.
1147 * @param[in] node The node which wants to get unblocked.
1148 * @param[in] is_scheduled This node is scheduled.
1149 * @param[in] release_idle_thread Function to release an idle thread.
1150 *
1151 * @retval true Continue with the unblocking operation.
1152 * @retval false Otherwise.
1153 */
1154RTEMS_INLINE_ROUTINE bool _Scheduler_Unblock_node(
1155  Scheduler_Context             *context,
1156  Thread_Control                *the_thread,
1157  Scheduler_Node                *node,
1158  bool                           is_scheduled,
1159  Scheduler_Release_idle_thread  release_idle_thread
1160)
1161{
1162  bool unblock;
1163
1164  if ( is_scheduled ) {
1165    Thread_Control *old_user = _Scheduler_Node_get_user( node );
1166    Per_CPU_Control *cpu = _Thread_Get_CPU( old_user );
1167    Thread_Control *idle = _Scheduler_Release_idle_thread(
1168      context,
1169      node,
1170      release_idle_thread
1171    );
1172    Thread_Control *owner = _Scheduler_Node_get_owner( node );
1173    Thread_Control *new_user;
1174
1175    if ( node->help_state == SCHEDULER_HELP_ACTIVE_OWNER ) {
1176      _Assert( idle != NULL );
1177      new_user = the_thread;
1178    } else if ( idle != NULL ) {
1179      _Assert( node->help_state == SCHEDULER_HELP_ACTIVE_RIVAL );
1180      new_user = the_thread;
1181    } else if ( the_thread != owner ) {
1182      _Assert( node->help_state == SCHEDULER_HELP_ACTIVE_RIVAL );
1183      _Assert( old_user != the_thread );
1184      _Scheduler_Thread_change_state( owner, THREAD_SCHEDULER_READY );
1185      new_user = the_thread;
1186      _Scheduler_Node_set_user( node, new_user );
1187    } else {
1188      _Assert( node->help_state == SCHEDULER_HELP_ACTIVE_RIVAL );
1189      _Assert( old_user != the_thread );
1190      _Scheduler_Thread_change_state( the_thread, THREAD_SCHEDULER_READY );
1191      new_user = NULL;
1192    }
1193
1194    if ( new_user != NULL ) {
1195      _Scheduler_Thread_change_state( new_user, THREAD_SCHEDULER_SCHEDULED );
1196      _Thread_Set_CPU( new_user, cpu );
1197      _Thread_Dispatch_update_heir( _Per_CPU_Get(), cpu, new_user );
1198    }
1199
1200    unblock = false;
1201  } else {
1202    _Scheduler_Thread_change_state( the_thread, THREAD_SCHEDULER_READY );
1203
1204    unblock = true;
1205  }
1206
1207  return unblock;
1208}
1209
1210/**
1211 * @brief Asks a ready scheduler node for help.
1212 *
1213 * @param[in] node The ready node offering help.
1214 * @param[in] needs_help The thread needing help.
1215 *
1216 * @retval needs_help The thread needing help.
1217 */
1218RTEMS_INLINE_ROUTINE Thread_Control *_Scheduler_Ask_ready_node_for_help(
1219  Scheduler_Node *node,
1220  Thread_Control *needs_help
1221)
1222{
1223  _Scheduler_Node_set_user( node, needs_help );
1224
1225  return needs_help;
1226}
1227
1228/**
1229 * @brief Asks a scheduled scheduler node for help.
1230 *
1231 * @param[in] context The scheduler instance context.
1232 * @param[in] node The scheduled node offering help.
1233 * @param[in] offers_help The thread offering help.
1234 * @param[in] needs_help The thread needing help.
1235 * @param[in] previous_accepts_help The previous thread accepting help by this
1236 *   scheduler node.
1237 * @param[in] release_idle_thread Function to release an idle thread.
1238 *
1239 * @retval needs_help The previous thread accepting help by this scheduler node
1240 *   which was displaced by the thread needing help.
1241 * @retval NULL There are no more threads needing help.
1242 */
1243RTEMS_INLINE_ROUTINE Thread_Control *_Scheduler_Ask_scheduled_node_for_help(
1244  Scheduler_Context             *context,
1245  Scheduler_Node                *node,
1246  Thread_Control                *offers_help,
1247  Thread_Control                *needs_help,
1248  Thread_Control                *previous_accepts_help,
1249  Scheduler_Release_idle_thread  release_idle_thread
1250)
1251{
1252  Thread_Control *next_needs_help = NULL;
1253  Thread_Control *old_user = NULL;
1254  Thread_Control *new_user = NULL;
1255
1256  if (
1257    previous_accepts_help != needs_help
1258      && _Scheduler_Thread_get_node( previous_accepts_help ) == node
1259  ) {
1260    Thread_Control *idle = _Scheduler_Release_idle_thread(
1261      context,
1262      node,
1263      release_idle_thread
1264    );
1265
1266    if ( idle != NULL ) {
1267      old_user = idle;
1268    } else {
1269      _Assert( _Scheduler_Node_get_user( node ) == previous_accepts_help );
1270      old_user = previous_accepts_help;
1271    }
1272
1273    if ( needs_help->Scheduler.state == THREAD_SCHEDULER_READY ) {
1274      new_user = needs_help;
1275    } else {
1276      _Assert(
1277        node->help_state == SCHEDULER_HELP_ACTIVE_OWNER
1278          || node->help_state == SCHEDULER_HELP_ACTIVE_RIVAL
1279      );
1280      _Assert( offers_help->Scheduler.node == offers_help->Scheduler.own_node );
1281
1282      new_user = offers_help;
1283    }
1284
1285    if ( previous_accepts_help != offers_help ) {
1286      next_needs_help = previous_accepts_help;
1287    }
1288  } else if ( needs_help->Scheduler.state == THREAD_SCHEDULER_READY ) {
1289    Thread_Control *idle = _Scheduler_Release_idle_thread(
1290      context,
1291      node,
1292      release_idle_thread
1293    );
1294
1295    if ( idle != NULL ) {
1296      old_user = idle;
1297    } else {
1298      old_user = _Scheduler_Node_get_user( node );
1299    }
1300
1301    new_user = needs_help;
1302  } else {
1303    _Assert( needs_help->Scheduler.state == THREAD_SCHEDULER_SCHEDULED );
1304  }
1305
1306  if ( new_user != old_user ) {
1307    Per_CPU_Control *cpu_self = _Per_CPU_Get();
1308    Per_CPU_Control *cpu = _Thread_Get_CPU( old_user );
1309
1310    _Scheduler_Thread_change_state( old_user, THREAD_SCHEDULER_READY );
1311    _Scheduler_Thread_set_scheduler_and_node(
1312      old_user,
1313      _Scheduler_Thread_get_own_node( old_user ),
1314      old_user
1315    );
1316
1317    _Scheduler_Thread_change_state( new_user, THREAD_SCHEDULER_SCHEDULED );
1318    _Scheduler_Thread_set_scheduler_and_node( new_user, node, offers_help );
1319
1320    _Scheduler_Node_set_user( node, new_user );
1321    _Thread_Set_CPU( new_user, cpu );
1322    _Thread_Dispatch_update_heir( cpu_self, cpu, new_user );
1323  }
1324
1325  return next_needs_help;
1326}
1327
1328/**
1329 * @brief Asks a blocked scheduler node for help.
1330 *
1331 * @param[in] context The scheduler instance context.
1332 * @param[in] node The scheduled node offering help.
1333 * @param[in] offers_help The thread offering help.
1334 * @param[in] needs_help The thread needing help.
1335 *
1336 * @retval true Enqueue this scheduler node.
1337 * @retval false Otherwise.
1338 */
1339RTEMS_INLINE_ROUTINE bool _Scheduler_Ask_blocked_node_for_help(
1340  Scheduler_Context *context,
1341  Scheduler_Node    *node,
1342  Thread_Control    *offers_help,
1343  Thread_Control    *needs_help
1344)
1345{
1346  bool enqueue;
1347
1348  _Assert( node->help_state == SCHEDULER_HELP_PASSIVE );
1349
1350  if ( needs_help->Scheduler.state == THREAD_SCHEDULER_READY ) {
1351    _Scheduler_Node_set_user( node, needs_help );
1352    _Scheduler_Thread_set_scheduler_and_node( needs_help, node, offers_help );
1353
1354    enqueue = true;
1355  } else {
1356    enqueue = false;
1357  }
1358
1359  return enqueue;
1360}
1361#endif
1362
1363ISR_LOCK_DECLARE( extern, _Scheduler_Lock )
1364
1365/**
1366 * @brief Acquires the scheduler instance of the thread.
1367 *
1368 * @param[in] the_thread The thread.
1369 * @param[in] lock_context The lock context for _Scheduler_Release().
1370 */
1371RTEMS_INLINE_ROUTINE void _Scheduler_Acquire(
1372  Thread_Control   *the_thread,
1373  ISR_lock_Context *lock_context
1374)
1375{
1376  (void) the_thread;
1377  _ISR_lock_ISR_disable_and_acquire( &_Scheduler_Lock, lock_context );
1378}
1379
1380/**
1381 * @brief Releases the scheduler instance of the thread.
1382 *
1383 * @param[in] the_thread The thread.
1384 * @param[in] lock_context The lock context used for _Scheduler_Acquire().
1385 */
1386RTEMS_INLINE_ROUTINE void _Scheduler_Release(
1387  Thread_Control   *the_thread,
1388  ISR_lock_Context *lock_context
1389)
1390{
1391  (void) the_thread;
1392  _ISR_lock_Release_and_ISR_enable( &_Scheduler_Lock, lock_context );
1393}
1394
1395/** @} */
1396
1397#ifdef __cplusplus
1398}
1399#endif
1400
1401#endif
1402/* end of include file */
Note: See TracBrowser for help on using the repository browser.