summaryrefslogtreecommitdiffstats
path: root/cpukit/score/include/rtems/score/threadq.h
blob: 084161cc4d2d49e1d81df555a146a2c348c9020f (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
/**
 *  @file
 *
 *  @brief Constants and Structures Needed to Declare a Thread Queue
 *
 *  This include file contains all the constants and structures
 *  needed to declare a thread queue.
 */

/*
 *  COPYRIGHT (c) 1989-2014.
 *  On-Line Applications Research Corporation (OAR).
 *
 *  The license and distribution terms for this file may be
 *  found in the file LICENSE in this distribution or at
 *  http://www.rtems.org/license/LICENSE.
 */

#ifndef _RTEMS_SCORE_THREADQ_H
#define _RTEMS_SCORE_THREADQ_H

#include <rtems/score/chain.h>
#include <rtems/score/isrlock.h>
#include <rtems/score/object.h>
#include <rtems/score/priority.h>
#include <rtems/score/rbtree.h>
#include <rtems/score/watchdog.h>

#ifdef __cplusplus
extern "C" {
#endif

struct Scheduler_Node;

/**
 *  @defgroup ScoreThreadQueue Thread Queue Handler
 *
 *  @ingroup Score
 *
 *  This handler provides the capability to have threads block in
 *  ordered sets. The sets may be ordered using the FIFO or priority
 *  discipline.
 */
/**@{*/

typedef struct _Thread_Control Thread_Control;

typedef struct Thread_queue_Queue Thread_queue_Queue;

typedef struct Thread_queue_Operations Thread_queue_Operations;

/**
 * @brief Thread queue deadlock callout.
 *
 * @param the_thread The thread that detected the deadlock.
 *
 * @see _Thread_queue_Context_set_deadlock_callout().
 */
typedef void ( *Thread_queue_Deadlock_callout )(
  Thread_Control *the_thread
);

#if defined(RTEMS_MULTIPROCESSING)
/**
 * @brief Multiprocessing (MP) support callout for thread queue operations.
 *
 * @param the_proxy The thread proxy of the thread queue operation.  A thread
 *   control is actually a thread proxy if and only if
 *   _Objects_Is_local_id( the_proxy->Object.id ) is false.
 * @param mp_id Object identifier of the object containing the thread queue.
 *
 * @see _Thread_queue_Context_set_MP_callout().
 */
typedef void ( *Thread_queue_MP_callout )(
  Thread_Control *the_proxy,
  Objects_Id      mp_id
);
#endif

#if defined(RTEMS_SMP)
/**
 * @brief The thread queue gate is an SMP synchronization means.
 *
 * The gates are added to a list of requests.  A busy wait is performed to make
 * sure that preceding requests are carried out.  Each predecessor notifies its
 * successor about on request completion.
 *
 * @see _Thread_queue_Gate_add(), _Thread_queue_Gate_wait(), and
 *   _Thread_queue_Gate_open().
 */
typedef struct {
  Chain_Node Node;

  Atomic_Uint go_ahead;
} Thread_queue_Gate;
#endif

typedef struct {
  /**
   * @brief The lock context for the thread queue acquire and release
   * operations.
   */
  ISR_lock_Context Lock_context;

#if defined(RTEMS_SMP)
  /**
   * @brief Data to support thread queue enqueue operations.
   */
  struct {
    /**
     * @brief Gate to synchronize thread wait lock requests.
     *
     * @see _Thread_Wait_acquire_critical() and _Thread_Wait_tranquilize().
     */
    Thread_queue_Gate Gate;

    /**
     * @brief The thread queue in case the thread is blocked on a thread queue.
     */
    Thread_queue_Queue *queue;
  } Wait;
#endif
} Thread_queue_Lock_context;

#if defined(RTEMS_SMP)
/**
 * @brief A thread queue link from one thread to another specified by the
 * thread queue owner and thread wait queue relationships.
 */
typedef struct {
  /**
   * @brief Node to register this link in the global thread queue links lookup
   * tree.
   */
  RBTree_Node Registry_node;

  /**
   * @brief The source thread queue determined by the thread queue owner.
   */
  Thread_queue_Queue *source;

  /**
   * @brief The target thread queue determined by the thread wait queue of the
   * source owner.
   */
  Thread_queue_Queue *target;

  /**
   * @brief Node to add this link to a thread queue path.
   */
  Chain_Node Path_node;

  /**
   * @brief The owner of this thread queue link.
   */
  Thread_Control *owner;

  /**
   * @brief The queue lock context used to acquire the thread wait lock of the
   * owner.
   */
  Thread_queue_Lock_context Lock_context;
} Thread_queue_Link;
#endif

/**
 * @brief Thread queue context for the thread queue methods.
 *
 * @see _Thread_queue_Context_initialize().
 */
typedef struct {
  /**
   * @brief The lock context for the thread queue acquire and release
   * operations.
   */
  Thread_queue_Lock_context Lock_context;

  /**
   * @brief The expected thread dispatch disable level for
   * _Thread_queue_Enqueue_critical().
   *
   * In case the actual thread dispatch disable level is not equal to the
   * expected level, then a fatal error occurs.
   */
  uint32_t expected_thread_dispatch_disable_level;

  /**
   * @brief The clock discipline for the interval timeout.
   * Use WATCHDOG_NO_TIMEOUT to block indefinitely.
   */
  Watchdog_Discipline timeout_discipline;

  /**
   * @brief Interval to wait.
   */
  uint64_t timeout;

#if defined(RTEMS_SMP)
  /**
   * @brief Representation of a thread queue path from a start thread queue to
   * the terminal thread queue.
   *
   * The start thread queue is determined by the object on which a thread intends
   * to block.  The terminal thread queue is the thread queue reachable via
   * thread queue links whose owner is not blocked on a thread queue.  The thread
   * queue links are determined by the thread queue owner and thread wait queue
   * relationships.
   */
  struct {
    /**
     * @brief The chain of thread queue links defining the thread queue path.
     */
    Chain_Control Links;

    /**
     * @brief The start of a thread queue path.
     */
    Thread_queue_Link Start;

    /**
     * @brief In case of a deadlock, a link for the first thread on the path
     * that tries to enqueue on a thread queue.
     */
    Thread_queue_Link Deadlock;
  } Path;
#endif

  /**
   * @brief Block to manage thread priority changes due to a thread queue
   * operation.
   */
  struct {
    /**
     * @brief A priority action list.
     */
    Priority_Actions Actions;

    /**
     * @brief Count of threads to update the priority via
     * _Thread_Priority_update().
     */
    size_t update_count;

    /**
     * @brief Threads to update the priority via _Thread_Priority_update().
     *
     * Currently, a maximum of two threads need an update in one rush, for
     * example the thread of the thread queue operation and the owner of the
     * thread queue.
     */
    Thread_Control *update[ 2 ];
  } Priority;

  /**
   * @brief Invoked in case of a detected deadlock.
   *
   * Must be initialized for _Thread_queue_Enqueue_critical() in case the
   * thread queue may have an owner, e.g. for mutex objects.
   *
   * @see _Thread_queue_Context_set_deadlock_callout().
   */
  Thread_queue_Deadlock_callout deadlock_callout;

#if defined(RTEMS_MULTIPROCESSING)
  /**
   * @brief Callout to unblock the thread in case it is actually a thread
   * proxy.
   *
   * This field is only used on multiprocessing configurations.  Used by
   * thread queue extract and unblock methods for objects with multiprocessing
   * (MP) support.
   *
   * @see _Thread_queue_Context_set_MP_callout().
   */
  Thread_queue_MP_callout mp_callout;
#endif
} Thread_queue_Context;

/**
 * @brief Thread priority queue.
 */
typedef struct {
#if defined(RTEMS_SMP)
  /**
   * @brief Node to enqueue this queue in the FIFO chain of the corresponding
   * heads structure.
   *
   * @see Thread_queue_Heads::Heads::Fifo.
   */
  Chain_Node Node;
#endif

  /**
   * @brief The actual thread priority queue.
   */
  Priority_Aggregation Queue;

  /**
   * @brief This priority queue is added to a scheduler node of the owner in
   * case of priority inheritance.
   */
  struct Scheduler_Node *scheduler_node;
} Thread_queue_Priority_queue;

/**
 * @brief Thread queue heads.
 *
 * Each thread is equipped with spare thread queue heads in case it is not
 * enqueued on a thread queue.  The first thread enqueued on a thread queue
 * will give its spare thread queue heads to that thread queue.  The threads
 * arriving at the queue will add their thread queue heads to the free chain of
 * the queue heads provided by the first thread enqueued.  Once a thread is
 * dequeued it use the free chain to get new spare thread queue heads.
 *
 * Uses a leading underscore in the structure name to allow forward
 * declarations in standard header files provided by Newlib and GCC.
 */
typedef struct _Thread_queue_Heads {
  /** This union contains the data structures used to manage the blocked
   *  set of tasks which varies based upon the discipline.
   */
  union {
    /**
     * @brief This is the FIFO discipline list.
     *
     * On SMP configurations this FIFO is used to enqueue the per scheduler
     * instance priority queues of this structure.  This ensures FIFO fairness
     * among the highest priority thread of each scheduler instance.
     */
    Chain_Control Fifo;

#if !defined(RTEMS_SMP)
    /**
     * @brief This is the set of threads for priority discipline waiting.
     */
    Thread_queue_Priority_queue Priority;
#endif
  } Heads;

  /**
   * @brief A chain with free thread queue heads providing the spare thread
   * queue heads for a thread once it is dequeued.
   */
  Chain_Control Free_chain;

  /**
   * @brief A chain node to add these thread queue heads to the free chain of
   * the thread queue heads dedicated to the thread queue of an object.
   */
  Chain_Node Free_node;

#if defined(RTEMS_SMP)
  /**
   * @brief One priority queue per scheduler instance.
   */
  Thread_queue_Priority_queue Priority[ RTEMS_ZERO_LENGTH_ARRAY ];
#endif
} Thread_queue_Heads;

#if defined(RTEMS_SMP)
  #define THREAD_QUEUE_HEADS_SIZE( scheduler_count ) \
    ( sizeof( Thread_queue_Heads ) \
      + ( scheduler_count ) * sizeof( Thread_queue_Priority_queue ) )
#else
  #define THREAD_QUEUE_HEADS_SIZE( scheduler_count ) \
    sizeof( Thread_queue_Heads )
#endif

struct Thread_queue_Queue {
  /**
   * @brief Lock to protect this thread queue.
   *
   * It may be used to protect additional state of the object embedding this
   * thread queue.
   *
   * Must be the first component of this structure to be able to re-use
   * implementation parts for structures defined by Newlib <sys/lock.h>.
   *
   * @see _Thread_queue_Acquire(), _Thread_queue_Acquire_critical() and
   * _Thread_queue_Release().
   */
#if defined(RTEMS_SMP)
  SMP_ticket_lock_Control Lock;
#endif

  /**
   * @brief The thread queue heads.
   *
   * This pointer is NULL, if and only if no threads are enqueued.  The first
   * thread to enqueue will give its spare thread queue heads to this thread
   * queue.
   */
  Thread_queue_Heads *heads;

  /**
   * @brief The thread queue owner.
   */
  Thread_Control *owner;
};

/**
 * @brief Thread queue action operation.
 *
 * @param[in] queue The actual thread queue.
 * @param[in] the_thread The thread.
 * @param[in] queue_context The thread queue context providing the thread queue
 *   action set to perform.  Returns the thread queue action set to perform on
 *   the thread queue owner or the empty set in case there is nothing to do.
 */
typedef void ( *Thread_queue_Priority_actions_operation )(
  Thread_queue_Queue   *queue,
  Priority_Actions     *priority_actions
);

/**
 * @brief Thread queue enqueue operation.
 *
 * A potential thread to update the priority due to priority inheritance is
 * returned via the thread queue context.  This thread is handed over to
 * _Thread_Priority_update().
 *
 * @param[in] queue The actual thread queue.
 * @param[in] the_thread The thread to enqueue on the queue.
 */
typedef void ( *Thread_queue_Enqueue_operation )(
  Thread_queue_Queue   *queue,
  Thread_Control       *the_thread,
  Thread_queue_Context *queue_context
);

/**
 * @brief Thread queue extract operation.
 *
 * @param[in] queue The actual thread queue.
 * @param[in] the_thread The thread to extract from the thread queue.
 */
typedef void ( *Thread_queue_Extract_operation )(
  Thread_queue_Queue   *queue,
  Thread_Control       *the_thread,
  Thread_queue_Context *queue_context
);

/**
 * @brief Thread queue surrender operation.
 *
 * This operation must dequeue and return the first thread on the queue.
 *
 * @param[in] queue The actual thread queue.
 * @param[in] heads The thread queue heads.  It must not be NULL.
 * @param[in] previous_owner The previous owner of the thread queue.
 *
 * @return The previous first thread on the queue.
 */
typedef Thread_Control *( *Thread_queue_Surrender_operation )(
  Thread_queue_Queue   *queue,
  Thread_queue_Heads   *heads,
  Thread_Control       *previous_owner,
  Thread_queue_Context *queue_context
);

/**
 * @brief Thread queue first operation.
 *
 * @param[in] heads The thread queue heads.
 *
 * @retval NULL No thread is present on the thread queue.
 * @retval first The first thread of the thread queue according to the insert
 * order.  This thread remains on the thread queue.
 */
typedef Thread_Control *( *Thread_queue_First_operation )(
  Thread_queue_Heads *heads
);

/**
 * @brief Thread queue operations.
 *
 * @see _Thread_wait_Set_operations().
 */
struct Thread_queue_Operations {
  /**
   * @brief Thread queue priority actions operation.
   */
  Thread_queue_Priority_actions_operation priority_actions;

  /**
   * @brief Thread queue enqueue operation.
   *
   * Called by object routines to enqueue the thread.
   */
  Thread_queue_Enqueue_operation enqueue;

  /**
   * @brief Thread queue extract operation.
   *
   * Called by object routines to extract a thread from a thread queue.
   */
  Thread_queue_Extract_operation extract;

  /**
   * @brief Thread queue surrender operation.
   */
  Thread_queue_Surrender_operation surrender;

  /**
   * @brief Thread queue first operation.
   */
  Thread_queue_First_operation first;
};

/**
 *  This is the structure used to manage sets of tasks which are blocked
 *  waiting to acquire a resource.
 */
typedef struct {
#if defined(RTEMS_SMP)
#if defined(RTEMS_DEBUG)
  /**
   * @brief The index of the owning processor of the thread queue lock.
   *
   * The thread queue lock may be acquired via the thread lock also.  This path
   * is not covered by this field.  In case the lock is not owned directly via
   * _Thread_queue_Acquire(), then the value of this field is
   * SMP_LOCK_NO_OWNER.
   *
   * Must be before the queue component of this structure to be able to re-use
   * implementation parts for structures defined by Newlib <sys/lock.h>.
   */
  uint32_t owner;
#endif

#if defined(RTEMS_PROFILING)
  /**
   * @brief SMP lock statistics in case SMP and profiling are enabled.
   *
   * Must be before the queue component of this structure to be able to re-use
   * implementation parts for structures defined by Newlib <sys/lock.h>.
   */
  SMP_lock_Stats Lock_stats;
#endif
#endif

  /**
   * @brief The actual thread queue.
   */
  Thread_queue_Queue Queue;
} Thread_queue_Control;

/**@}*/

#ifdef __cplusplus
}
#endif

#endif
/* end of include file */