source: rtems/cpukit/score/src/threadqops.c @ aaaf9610

Last change on this file since aaaf9610 was aaaf9610, checked in by Sebastian Huber <sebastian.huber@…>, on Aug 8, 2016 at 6:44:51 AM

score: Add debug support to red-black trees

This helps to detect double insert and extract errors.

  • Property mode set to 100644
File size: 10.0 KB
Line 
1/*
2 * Copyright (c) 2015, 2016 embedded brains GmbH.  All rights reserved.
3 *
4 *  embedded brains GmbH
5 *  Dornierstr. 4
6 *  82178 Puchheim
7 *  Germany
8 *  <rtems@embedded-brains.de>
9 *
10 * The license and distribution terms for this file may be
11 * found in the file LICENSE in this distribution or at
12 * http://www.rtems.org/license/LICENSE.
13 */
14
15#if HAVE_CONFIG_H
16  #include "config.h"
17#endif
18
19#include <rtems/score/threadimpl.h>
20#include <rtems/score/assert.h>
21#include <rtems/score/chainimpl.h>
22#include <rtems/score/rbtreeimpl.h>
23#include <rtems/score/schedulerimpl.h>
24
25static void _Thread_queue_Do_nothing_priority_change(
26  Thread_queue_Queue *queue,
27  Thread_Control     *the_thread,
28  Priority_Control    new_priority
29)
30{
31  (void) queue;
32  (void) the_thread;
33  (void) new_priority;
34}
35
36static void _Thread_queue_Do_nothing_extract(
37  Thread_queue_Queue *queue,
38  Thread_Control     *the_thread
39)
40{
41  (void) queue;
42  (void) the_thread;
43}
44
45static Thread_queue_Heads *_Thread_queue_Queue_enqueue(
46  Thread_queue_Queue *queue,
47  Thread_Control     *the_thread,
48  void             ( *initialize )( Thread_queue_Heads * ),
49  void             ( *enqueue )( Thread_queue_Heads *, Thread_Control * )
50)
51{
52  Thread_queue_Heads *heads = queue->heads;
53  Thread_queue_Heads *spare_heads = the_thread->Wait.spare_heads;
54
55  the_thread->Wait.spare_heads = NULL;
56
57  if ( heads == NULL ) {
58    _Assert( spare_heads != NULL );
59    _Assert( _Chain_Is_empty( &spare_heads->Free_chain ) );
60    heads = spare_heads;
61    queue->heads = heads;
62    ( *initialize )( heads );
63  }
64
65  _Chain_Prepend_unprotected( &heads->Free_chain, &spare_heads->Free_node );
66
67  ( *enqueue )( heads, the_thread );
68
69  return heads;
70}
71
72static void _Thread_queue_Queue_extract(
73  Thread_queue_Queue *queue,
74  Thread_Control     *the_thread,
75  void             ( *extract )( Thread_queue_Heads *, Thread_Control * )
76)
77{
78  Thread_queue_Heads *heads = queue->heads;
79
80  _Assert( heads != NULL );
81
82  the_thread->Wait.spare_heads = RTEMS_CONTAINER_OF(
83    _Chain_Get_first_unprotected( &heads->Free_chain ),
84    Thread_queue_Heads,
85    Free_node
86  );
87
88  if ( _Chain_Is_empty( &heads->Free_chain ) ) {
89    queue->heads = NULL;
90  }
91
92  ( *extract )( heads, the_thread );
93}
94
95static void _Thread_queue_FIFO_do_initialize(
96  Thread_queue_Heads *heads
97)
98{
99  _Chain_Initialize_empty( &heads->Heads.Fifo );
100}
101
102static void _Thread_queue_FIFO_do_enqueue(
103  Thread_queue_Heads *heads,
104  Thread_Control     *the_thread
105)
106{
107  _Chain_Initialize_node( &the_thread->Wait.Node.Chain );
108  _Chain_Append_unprotected(
109    &heads->Heads.Fifo,
110    &the_thread->Wait.Node.Chain
111  );
112}
113
114static void _Thread_queue_FIFO_do_extract(
115  Thread_queue_Heads *heads,
116  Thread_Control     *the_thread
117)
118{
119  _Chain_Extract_unprotected( &the_thread->Wait.Node.Chain );
120}
121
122static void _Thread_queue_FIFO_enqueue(
123  Thread_queue_Queue *queue,
124  Thread_Control     *the_thread,
125  Thread_queue_Path  *path
126)
127{
128  path->update_priority = NULL;
129
130  _Thread_queue_Queue_enqueue(
131    queue,
132    the_thread,
133    _Thread_queue_FIFO_do_initialize,
134    _Thread_queue_FIFO_do_enqueue
135  );
136}
137
138static void _Thread_queue_FIFO_extract(
139  Thread_queue_Queue *queue,
140  Thread_Control     *the_thread
141)
142{
143  _Thread_queue_Queue_extract(
144    queue,
145    the_thread,
146    _Thread_queue_FIFO_do_extract
147  );
148}
149
150static Thread_Control *_Thread_queue_FIFO_first(
151  Thread_queue_Heads *heads
152)
153{
154  Chain_Control *fifo = &heads->Heads.Fifo;
155  Chain_Node    *first;
156
157  _Assert( !_Chain_Is_empty( fifo ) );
158  first = _Chain_First( fifo );
159
160  return THREAD_CHAIN_NODE_TO_THREAD( first );
161}
162
163static Thread_queue_Priority_queue *_Thread_queue_Priority_queue(
164  Thread_queue_Heads   *heads,
165  const Thread_Control *the_thread
166)
167{
168#if defined(RTEMS_SMP)
169  return &heads->Priority[
170    _Scheduler_Get_index( _Scheduler_Get_own( the_thread ) )
171  ];
172#else
173  (void) the_thread;
174
175  return &heads->Heads.Priority;
176#endif
177}
178
179static bool _Thread_queue_Priority_less(
180  const void        *left,
181  const RBTree_Node *right
182)
183{
184  const Priority_Control *the_left;
185  const Thread_Control   *the_right;
186
187  the_left = left;
188  the_right = THREAD_RBTREE_NODE_TO_THREAD( right );
189
190  return *the_left < the_right->current_priority;
191}
192
193static void _Thread_queue_Priority_priority_change(
194  Thread_queue_Queue *queue,
195  Thread_Control     *the_thread,
196  Priority_Control    new_priority
197)
198{
199  Thread_queue_Heads          *heads = queue->heads;
200  Thread_queue_Priority_queue *priority_queue;
201
202  _Assert( heads != NULL );
203
204  priority_queue = _Thread_queue_Priority_queue( heads, the_thread );
205
206  _RBTree_Extract(
207    &priority_queue->Queue,
208    &the_thread->Wait.Node.RBTree
209  );
210  _RBTree_Insert_inline(
211    &priority_queue->Queue,
212    &the_thread->Wait.Node.RBTree,
213    &new_priority,
214    _Thread_queue_Priority_less
215  );
216}
217
218static void _Thread_queue_Priority_do_initialize(
219  Thread_queue_Heads *heads
220)
221{
222#if defined(RTEMS_SMP)
223  _Chain_Initialize_empty( &heads->Heads.Fifo );
224#else
225  _RBTree_Initialize_empty( &heads->Heads.Priority.Queue );
226#endif
227}
228
229static void _Thread_queue_Priority_do_enqueue(
230  Thread_queue_Heads *heads,
231  Thread_Control     *the_thread
232)
233{
234  Thread_queue_Priority_queue *priority_queue =
235    _Thread_queue_Priority_queue( heads, the_thread );
236  Priority_Control current_priority;
237
238#if defined(RTEMS_SMP)
239  if ( _RBTree_Is_empty( &priority_queue->Queue ) ) {
240    _Chain_Append_unprotected( &heads->Heads.Fifo, &priority_queue->Node );
241  }
242#endif
243
244  current_priority = the_thread->current_priority;
245  _RBTree_Initialize_node( &the_thread->Wait.Node.RBTree );
246  _RBTree_Insert_inline(
247    &priority_queue->Queue,
248    &the_thread->Wait.Node.RBTree,
249    &current_priority,
250    _Thread_queue_Priority_less
251  );
252}
253
254static void _Thread_queue_Priority_do_extract(
255  Thread_queue_Heads *heads,
256  Thread_Control     *the_thread
257)
258{
259  Thread_queue_Priority_queue *priority_queue =
260    _Thread_queue_Priority_queue( heads, the_thread );
261
262  _RBTree_Extract(
263    &priority_queue->Queue,
264    &the_thread->Wait.Node.RBTree
265  );
266
267#if defined(RTEMS_SMP)
268  _Chain_Extract_unprotected( &priority_queue->Node );
269
270  if ( !_RBTree_Is_empty( &priority_queue->Queue ) ) {
271    _Chain_Append_unprotected( &heads->Heads.Fifo, &priority_queue->Node );
272  }
273#endif
274}
275
276static void _Thread_queue_Priority_enqueue(
277  Thread_queue_Queue *queue,
278  Thread_Control     *the_thread,
279  Thread_queue_Path  *path
280)
281{
282  path->update_priority = NULL;
283
284  _Thread_queue_Queue_enqueue(
285    queue,
286    the_thread,
287    _Thread_queue_Priority_do_initialize,
288    _Thread_queue_Priority_do_enqueue
289  );
290}
291
292static void _Thread_queue_Priority_extract(
293  Thread_queue_Queue *queue,
294  Thread_Control     *the_thread
295)
296{
297  _Thread_queue_Queue_extract(
298    queue,
299    the_thread,
300    _Thread_queue_Priority_do_extract
301  );
302}
303
304static Thread_Control *_Thread_queue_Priority_first(
305  Thread_queue_Heads *heads
306)
307{
308  Thread_queue_Priority_queue *priority_queue;
309  RBTree_Node                 *first;
310
311#if defined(RTEMS_SMP)
312  _Assert( !_Chain_Is_empty( &heads->Heads.Fifo ) );
313  priority_queue = (Thread_queue_Priority_queue *)
314    _Chain_First( &heads->Heads.Fifo );
315#else
316  priority_queue = &heads->Heads.Priority;
317#endif
318
319  _Assert( !_RBTree_Is_empty( &priority_queue->Queue ) );
320  first = _RBTree_Minimum( &priority_queue->Queue );
321
322  return THREAD_RBTREE_NODE_TO_THREAD( first );
323}
324
325static void _Thread_queue_Priority_inherit_enqueue(
326  Thread_queue_Queue *queue,
327  Thread_Control     *the_thread,
328  Thread_queue_Path  *path
329)
330{
331  Thread_queue_Heads *heads;
332  Thread_Control     *owner;
333  Priority_Control    priority;
334
335  heads = _Thread_queue_Queue_enqueue(
336    queue,
337    the_thread,
338    _Thread_queue_Priority_do_initialize,
339    _Thread_queue_Priority_do_enqueue
340  );
341
342  owner = queue->owner;
343
344#if defined(RTEMS_SMP)
345  if ( _Chain_Has_only_one_node( &heads->Heads.Fifo ) ) {
346    priority = the_thread->current_priority;
347  } else {
348    priority = _Scheduler_Map_priority(
349      _Scheduler_Get_own( the_thread ),
350      PRIORITY_PSEUDO_ISR
351    );
352  }
353#else
354  (void) heads;
355
356  priority = the_thread->current_priority;
357#endif
358
359  if ( priority < owner->current_priority ) {
360    path->update_priority = owner;
361
362    owner->priority_restore_hint = true;
363    _Atomic_Fence( ATOMIC_ORDER_ACQ_REL );
364
365    _Scheduler_Thread_set_priority( owner, priority, false );
366
367    ( *owner->Wait.operations->priority_change )(
368      owner->Wait.queue,
369      owner,
370      priority
371    );
372  } else {
373    path->update_priority = NULL;
374  }
375}
376
377#if defined(RTEMS_SMP)
378void _Thread_queue_Boost_priority(
379  Thread_queue_Queue *queue,
380  Thread_Control     *the_thread
381)
382{
383  Thread_queue_Heads *heads = queue->heads;
384
385  if ( !_Chain_Has_only_one_node( &heads->Heads.Fifo ) ) {
386    const Scheduler_Control *scheduler;
387    Priority_Control         boost_priority;
388
389    the_thread->priority_restore_hint = true;
390    _Atomic_Fence( ATOMIC_ORDER_ACQ_REL );
391
392    scheduler = _Scheduler_Get_own( the_thread );
393    boost_priority = _Scheduler_Map_priority( scheduler, PRIORITY_PSEUDO_ISR );
394
395    _Scheduler_Thread_set_priority( the_thread, boost_priority, false );
396  }
397}
398#endif
399
400const Thread_queue_Operations _Thread_queue_Operations_default = {
401  .priority_change = _Thread_queue_Do_nothing_priority_change,
402  .extract = _Thread_queue_Do_nothing_extract
403  /*
404   * The default operations are only used in _Thread_Change_priority() and
405   * _Thread_Timeout() and don't have a thread queue associated with them, so
406   * the enqueue and first operations are superfluous.
407   */
408};
409
410const Thread_queue_Operations _Thread_queue_Operations_FIFO = {
411  .priority_change = _Thread_queue_Do_nothing_priority_change,
412  .enqueue = _Thread_queue_FIFO_enqueue,
413  .extract = _Thread_queue_FIFO_extract,
414  .first = _Thread_queue_FIFO_first
415};
416
417const Thread_queue_Operations _Thread_queue_Operations_priority = {
418  .priority_change = _Thread_queue_Priority_priority_change,
419  .enqueue = _Thread_queue_Priority_enqueue,
420  .extract = _Thread_queue_Priority_extract,
421  .first = _Thread_queue_Priority_first
422};
423
424const Thread_queue_Operations _Thread_queue_Operations_priority_inherit = {
425  .priority_change = _Thread_queue_Priority_priority_change,
426  .enqueue = _Thread_queue_Priority_inherit_enqueue,
427  .extract = _Thread_queue_Priority_extract,
428  .first = _Thread_queue_Priority_first
429};
Note: See TracBrowser for help on using the repository browser.