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
|
/*
* Copyright (c) 2014 embedded brains GmbH. All rights reserved.
*
* embedded brains GmbH
* Dornierstr. 4
* 82178 Puchheim
* Germany
* <rtems@embedded-brains.de>
*
* 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_RESOURCE_H
#define _RTEMS_SCORE_RESOURCE_H
#include <rtems/score/basedefs.h>
#include <rtems/score/chain.h>
#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */
/**
* @defgroup ScoreResource Resource Handler
*
* @ingroup Score
*
* @brief Support for resource dependency management.
*
* A resource is something that has at most one owner at a time and may have
* multiple rivals in case an owner is present. The owner and rivals are
* impersonated via resource nodes. A resource is represented via the resource
* control structure. The resource controls and nodes are organized as trees.
* It is possible to detect deadlocks via such a resource tree. The
* _Resource_Iterate() function can be used to iterate through such a resource
* tree starting at a top node.
*
* The following diagram shows an example resource tree with sixteen resource
* nodes n0 up to n15 and sixteen resources r0 up to r15. The root of this
* tree is n0. As a use case threads can be associated with resource nodes.
* In this case a thread represented by node n0 owns resources r0, r1, r2, r3,
* r6, r11 and r12 and is in the ready state. The threads represented by nodes
* n1 up to n15 wait directly or indirectly via resources owned by n0 and are
* in a blocked state.
*
* @dot
* digraph {
* n0 [style=filled, fillcolor=green];
* n0 -> r0;
* subgraph {
* rank=same;
* n1 [style=filled, fillcolor=green];
* r0 -> n1;
* n2 [style=filled, fillcolor=green];
* n1 -> n2;
* n4 [style=filled, fillcolor=green];
* n2 -> n4;
* n6 [style=filled, fillcolor=green];
* n4 -> n6;
* n8 [style=filled, fillcolor=green];
* n6 -> n8;
* n15 [style=filled, fillcolor=green];
* n8 -> n15;
* }
* n1 -> r5;
* subgraph {
* rank=same;
* n3 [style=filled, fillcolor=green];
* r5 -> n3;
* n12 [style=filled, fillcolor=green];
* n3 -> n12;
* }
* n3 -> r10;
* r10 -> r13;
* r13 -> r15;
* subgraph {
* rank=same;
* n10 [style=filled, fillcolor=green];
* r15 -> n10;
* }
* r5 -> r7;
* subgraph {
* rank=same;
* n11 [style=filled, fillcolor=green];
* r7 -> n11;
* n14 [style=filled, fillcolor=green];
* n11 -> n14;
* }
* n14 -> r4;
* r7 -> r8;
* subgraph {
* rank=same;
* n13 [style=filled, fillcolor=green];
* r8 -> n13;
* }
* r8 -> r9;
* n8 -> r14;
* r0 -> r1;
* subgraph {
* rank=same;
* n7 [style=filled, fillcolor=green];
* r1 -> n7;
* }
* r1 -> r2;
* r2 -> r3;
* r3 -> r6;
* r6 -> r11;
* r11 -> r12;
* subgraph {
* rank=same;
* n5 [style=filled, fillcolor=green];
* r12 -> n5;
* n9 [style=filled, fillcolor=green];
* n5 -> n9;
* }
* }
* @enddot
*
* The following example illustrates a deadlock situation. The root of the
* tree tries to get ownership of a resource owned by one of its children.
*
* @dot
* digraph {
* n0 [style=filled, fillcolor=green];
* n0 -> r0;
* subgraph {
* rank=same;
* n1 [style=filled, fillcolor=green];
* r0 -> n1;
* }
* n1 -> r1;
* n0 -> r1 [label=deadlock, style=dotted];
* }
* @enddot
*
* @{
*/
typedef struct Resource_Node Resource_Node;
typedef struct Resource_Control Resource_Control;
/**
* @brief Resource node to reflect ownership of resources and a dependency on a
* resource.
*/
struct Resource_Node {
/**
* @brief Node to build a chain of rivals depending on a resource.
*
* @see Resource_Control::Rivals.
*/
Chain_Node Node;
/**
* @brief A chain of resources owned by this node.
*
* @see Resource_Control::Node.
*/
Chain_Control Resources;
/**
* @brief Reference to a resource in case this node has to wait for ownership
* of this resource.
*
* It is @c NULL in case this node has no open resource dependency.
*/
Resource_Control *dependency;
/**
* @brief Reference to the root of the resource tree.
*
* The root references itself.
*/
Resource_Node *root;
};
/**
* @brief Resource control to manage ownership and rival nodes depending on a
* resource.
*/
struct Resource_Control {
/**
* @brief Node to build a chain of resources owned by a resource node.
*
* @see Resource_Node::Resources.
*/
Chain_Node Node;
/**
* @brief A chain of rivals waiting for resource ownership.
*
* @see Resource_Node::Node.
*/
Chain_Control Rivals;
/**
* @brief The owner of this resource.
*/
Resource_Node *owner;
};
/** @} */
#ifdef __cplusplus
}
#endif /* __cplusplus */
#endif /* _RTEMS_SCORE_RESOURCE_H */
|
