|
145
|
1 /* Copyright (C) 2015-2020 Free Software Foundation, Inc.
|
|
111
|
2 Contributed by Aldy Hernandez <aldyh@redhat.com>.
|
|
|
3
|
|
|
4 This file is part of the GNU Offloading and Multi Processing Library
|
|
|
5 (libgomp).
|
|
|
6
|
|
|
7 Libgomp is free software; you can redistribute it and/or modify it
|
|
|
8 under the terms of the GNU General Public License as published by
|
|
|
9 the Free Software Foundation; either version 3, or (at your option)
|
|
|
10 any later version.
|
|
|
11
|
|
|
12 Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
|
|
|
14 FOR A PARTICULAR PURPOSE. See the GNU General Public License for
|
|
|
15 more details.
|
|
|
16
|
|
|
17 Under Section 7 of GPL version 3, you are granted additional
|
|
|
18 permissions described in the GCC Runtime Library Exception, version
|
|
|
19 3.1, as published by the Free Software Foundation.
|
|
|
20
|
|
|
21 You should have received a copy of the GNU General Public License and
|
|
|
22 a copy of the GCC Runtime Library Exception along with this program;
|
|
|
23 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
|
|
|
24 <http://www.gnu.org/licenses/>. */
|
|
|
25
|
|
|
26 /* Priority queue implementation of GOMP tasks. */
|
|
|
27
|
|
|
28 #include "libgomp.h"
|
|
|
29
|
|
|
30 #if _LIBGOMP_CHECKING_
|
|
|
31 #include <stdio.h>
|
|
|
32
|
|
|
33 /* Sanity check to verify whether a TASK is in LIST. Return TRUE if
|
|
|
34 found, FALSE otherwise.
|
|
|
35
|
|
|
36 TYPE is the type of priority queue this task resides in. */
|
|
|
37
|
|
|
38 static inline bool
|
|
|
39 priority_queue_task_in_list_p (enum priority_queue_type type,
|
|
|
40 struct priority_list *list,
|
|
|
41 struct gomp_task *task)
|
|
|
42 {
|
|
|
43 struct priority_node *p = list->tasks;
|
|
|
44 do
|
|
|
45 {
|
|
|
46 if (priority_node_to_task (type, p) == task)
|
|
|
47 return true;
|
|
|
48 p = p->next;
|
|
|
49 }
|
|
|
50 while (p != list->tasks);
|
|
|
51 return false;
|
|
|
52 }
|
|
|
53
|
|
|
54 /* Tree version of priority_queue_task_in_list_p. */
|
|
|
55
|
|
|
56 static inline bool
|
|
|
57 priority_queue_task_in_tree_p (enum priority_queue_type type,
|
|
|
58 struct priority_queue *head,
|
|
|
59 struct gomp_task *task)
|
|
|
60 {
|
|
|
61 struct priority_list *list
|
|
|
62 = priority_queue_lookup_priority (head, task->priority);
|
|
|
63 if (!list)
|
|
|
64 return false;
|
|
|
65 return priority_queue_task_in_list_p (type, list, task);
|
|
|
66 }
|
|
|
67
|
|
|
68 /* Generic version of priority_queue_task_in_list_p that works for
|
|
|
69 trees or lists. */
|
|
|
70
|
|
|
71 bool
|
|
|
72 priority_queue_task_in_queue_p (enum priority_queue_type type,
|
|
|
73 struct priority_queue *head,
|
|
|
74 struct gomp_task *task)
|
|
|
75 {
|
|
|
76 if (priority_queue_empty_p (head, MEMMODEL_RELAXED))
|
|
|
77 return false;
|
|
|
78 if (priority_queue_multi_p (head))
|
|
|
79 return priority_queue_task_in_tree_p (type, head, task);
|
|
|
80 else
|
|
|
81 return priority_queue_task_in_list_p (type, &head->l, task);
|
|
|
82 }
|
|
|
83
|
|
|
84 /* Sanity check LIST to make sure the tasks therein are in the right
|
|
|
85 order. LIST is a priority list of type TYPE.
|
|
|
86
|
|
|
87 The expected order is that GOMP_TASK_WAITING tasks come before
|
|
|
88 GOMP_TASK_TIED/GOMP_TASK_ASYNC_RUNNING ones.
|
|
|
89
|
|
|
90 If CHECK_DEPS is TRUE, we also check that parent_depends_on WAITING
|
|
|
91 tasks come before !parent_depends_on WAITING tasks. This is only
|
|
|
92 applicable to the children queue, and the caller is expected to
|
|
|
93 ensure that we are verifying the children queue. */
|
|
|
94
|
|
|
95 static void
|
|
|
96 priority_list_verify (enum priority_queue_type type,
|
|
|
97 struct priority_list *list, bool check_deps)
|
|
|
98 {
|
|
|
99 bool seen_tied = false;
|
|
|
100 bool seen_plain_waiting = false;
|
|
|
101 struct priority_node *p = list->tasks;
|
|
|
102 while (1)
|
|
|
103 {
|
|
|
104 struct gomp_task *t = priority_node_to_task (type, p);
|
|
|
105 if (seen_tied && t->kind == GOMP_TASK_WAITING)
|
|
|
106 gomp_fatal ("priority_queue_verify: WAITING task after TIED");
|
|
|
107 if (t->kind >= GOMP_TASK_TIED)
|
|
|
108 seen_tied = true;
|
|
|
109 else if (check_deps && t->kind == GOMP_TASK_WAITING)
|
|
|
110 {
|
|
|
111 if (t->parent_depends_on)
|
|
|
112 {
|
|
|
113 if (seen_plain_waiting)
|
|
|
114 gomp_fatal ("priority_queue_verify: "
|
|
|
115 "parent_depends_on after !parent_depends_on");
|
|
|
116 }
|
|
|
117 else
|
|
|
118 seen_plain_waiting = true;
|
|
|
119 }
|
|
|
120 p = p->next;
|
|
|
121 if (p == list->tasks)
|
|
|
122 break;
|
|
|
123 }
|
|
|
124 }
|
|
|
125
|
|
|
126 /* Callback type for priority_tree_verify_callback. */
|
|
|
127 struct cbtype
|
|
|
128 {
|
|
|
129 enum priority_queue_type type;
|
|
|
130 bool check_deps;
|
|
|
131 };
|
|
|
132
|
|
|
133 /* Verify every task in NODE.
|
|
|
134
|
|
|
135 Callback for splay_tree_foreach. */
|
|
|
136
|
|
|
137 static void
|
|
|
138 priority_tree_verify_callback (prio_splay_tree_key key, void *data)
|
|
|
139 {
|
|
|
140 struct cbtype *cb = (struct cbtype *) data;
|
|
|
141 priority_list_verify (cb->type, &key->l, cb->check_deps);
|
|
|
142 }
|
|
|
143
|
|
|
144 /* Generic version of priority_list_verify.
|
|
|
145
|
|
|
146 Sanity check HEAD to make sure the tasks therein are in the right
|
|
|
147 order. The priority_queue holds tasks of type TYPE.
|
|
|
148
|
|
|
149 If CHECK_DEPS is TRUE, we also check that parent_depends_on WAITING
|
|
|
150 tasks come before !parent_depends_on WAITING tasks. This is only
|
|
|
151 applicable to the children queue, and the caller is expected to
|
|
|
152 ensure that we are verifying the children queue. */
|
|
|
153
|
|
|
154 void
|
|
|
155 priority_queue_verify (enum priority_queue_type type,
|
|
|
156 struct priority_queue *head, bool check_deps)
|
|
|
157 {
|
|
|
158 if (priority_queue_empty_p (head, MEMMODEL_RELAXED))
|
|
|
159 return;
|
|
|
160 if (priority_queue_multi_p (head))
|
|
|
161 {
|
|
|
162 struct cbtype cb = { type, check_deps };
|
|
|
163 prio_splay_tree_foreach (&head->t,
|
|
|
164 priority_tree_verify_callback, &cb);
|
|
|
165 }
|
|
|
166 else
|
|
|
167 priority_list_verify (type, &head->l, check_deps);
|
|
|
168 }
|
|
|
169 #endif /* _LIBGOMP_CHECKING_ */
|
|
|
170
|
|
|
171 /* Remove NODE from priority queue HEAD, wherever it may be inside the
|
|
|
172 tree. HEAD contains tasks of type TYPE. */
|
|
|
173
|
|
|
174 void
|
|
|
175 priority_tree_remove (enum priority_queue_type type,
|
|
|
176 struct priority_queue *head,
|
|
|
177 struct priority_node *node)
|
|
|
178 {
|
|
|
179 /* ?? The only reason this function is not inlined is because we
|
|
|
180 need to find the priority within gomp_task (which has not been
|
|
|
181 completely defined in the header file). If the lack of inlining
|
|
|
182 is a concern, we could pass the priority number as a
|
|
|
183 parameter, or we could move this to libgomp.h. */
|
|
|
184 int priority = priority_node_to_task (type, node)->priority;
|
|
|
185
|
|
|
186 /* ?? We could avoid this lookup by keeping a pointer to the key in
|
|
|
187 the priority_node. */
|
|
|
188 struct priority_list *list
|
|
|
189 = priority_queue_lookup_priority (head, priority);
|
|
|
190 #if _LIBGOMP_CHECKING_
|
|
|
191 if (!list)
|
|
|
192 gomp_fatal ("Unable to find priority %d", priority);
|
|
|
193 #endif
|
|
|
194 /* If NODE was the last in its priority, clean up the priority. */
|
|
|
195 if (priority_list_remove (list, node, MEMMODEL_RELAXED))
|
|
|
196 {
|
|
|
197 prio_splay_tree_remove (&head->t, (prio_splay_tree_key) list);
|
|
|
198 list->tasks = NULL;
|
|
|
199 #if _LIBGOMP_CHECKING_
|
|
|
200 memset (list, 0xaf, sizeof (*list));
|
|
|
201 #endif
|
|
|
202 free (list);
|
|
|
203 }
|
|
|
204 }
|
|
|
205
|
|
|
206 /* Return the highest priority WAITING task in a splay tree NODE. If
|
|
|
207 there are no WAITING tasks available, return NULL.
|
|
|
208
|
|
|
209 NODE is a priority list containing tasks of type TYPE.
|
|
|
210
|
|
|
211 The right most node in a tree contains the highest priority.
|
|
|
212 Recurse down to find such a node. If the task at that max node is
|
|
|
213 not WAITING, bubble back up and look at the remaining tasks
|
|
|
214 in-order. */
|
|
|
215
|
|
|
216 static struct gomp_task *
|
|
|
217 priority_tree_next_task_1 (enum priority_queue_type type,
|
|
|
218 prio_splay_tree_node node)
|
|
|
219 {
|
|
|
220 again:
|
|
|
221 if (!node)
|
|
|
222 return NULL;
|
|
|
223 struct gomp_task *ret = priority_tree_next_task_1 (type, node->right);
|
|
|
224 if (ret)
|
|
|
225 return ret;
|
|
|
226 ret = priority_node_to_task (type, node->key.l.tasks);
|
|
|
227 if (ret->kind == GOMP_TASK_WAITING)
|
|
|
228 return ret;
|
|
|
229 node = node->left;
|
|
|
230 goto again;
|
|
|
231 }
|
|
|
232
|
|
|
233 /* Return the highest priority WAITING task from within Q1 and Q2,
|
|
|
234 while giving preference to tasks from Q1. Q1 is a queue containing
|
|
|
235 items of type TYPE1. Q2 is a queue containing items of type TYPE2.
|
|
|
236
|
|
|
237 Since we are mostly interested in Q1, if there are no WAITING tasks
|
|
|
238 in Q1, we don't bother checking Q2, and just return NULL.
|
|
|
239
|
|
|
240 As a special case, Q2 can be NULL, in which case, we just choose
|
|
|
241 the highest priority WAITING task in Q1. This is an optimization
|
|
|
242 to speed up looking through only one queue.
|
|
|
243
|
|
|
244 If the returned task is chosen from Q1, *Q1_CHOSEN_P is set to
|
|
|
245 TRUE, otherwise it is set to FALSE. */
|
|
|
246
|
|
|
247 struct gomp_task *
|
|
|
248 priority_tree_next_task (enum priority_queue_type type1,
|
|
|
249 struct priority_queue *q1,
|
|
|
250 enum priority_queue_type type2,
|
|
|
251 struct priority_queue *q2,
|
|
|
252 bool *q1_chosen_p)
|
|
|
253 {
|
|
|
254 struct gomp_task *t1 = priority_tree_next_task_1 (type1, q1->t.root);
|
|
|
255 if (!t1
|
|
|
256 /* Special optimization when only searching through one queue. */
|
|
|
257 || !q2)
|
|
|
258 {
|
|
|
259 *q1_chosen_p = true;
|
|
|
260 return t1;
|
|
|
261 }
|
|
|
262 struct gomp_task *t2 = priority_tree_next_task_1 (type2, q2->t.root);
|
|
|
263 if (!t2 || t1->priority > t2->priority)
|
|
|
264 {
|
|
|
265 *q1_chosen_p = true;
|
|
|
266 return t1;
|
|
|
267 }
|
|
|
268 if (t2->priority > t1->priority)
|
|
|
269 {
|
|
|
270 *q1_chosen_p = false;
|
|
|
271 return t2;
|
|
|
272 }
|
|
|
273 /* If we get here, the priorities are the same, so we must look at
|
|
|
274 parent_depends_on to make our decision. */
|
|
|
275 #if _LIBGOMP_CHECKING_
|
|
|
276 if (t1 != t2)
|
|
|
277 gomp_fatal ("priority_tree_next_task: t1 != t2");
|
|
|
278 #endif
|
|
|
279 if (t2->parent_depends_on && !t1->parent_depends_on)
|
|
|
280 {
|
|
|
281 *q1_chosen_p = false;
|
|
|
282 return t2;
|
|
|
283 }
|
|
|
284 *q1_chosen_p = true;
|
|
|
285 return t1;
|
|
|
286 }
|
|
|
287
|
|
|
288 /* Priority splay trees comparison function. */
|
|
|
289 static inline int
|
|
|
290 prio_splay_compare (prio_splay_tree_key x, prio_splay_tree_key y)
|
|
|
291 {
|
|
|
292 if (x->l.priority == y->l.priority)
|
|
|
293 return 0;
|
|
|
294 return x->l.priority < y->l.priority ? -1 : 1;
|
|
|
295 }
|
|
|
296
|
|
|
297 /* Define another splay tree instantiation, for priority_list's. */
|
|
|
298 #define splay_tree_prefix prio
|
|
|
299 #define splay_tree_c
|
|
|
300 #include "splay-tree.h"
|
