]>
Commit | Line | Data |
---|---|---|
7adcbafe | 1 | /* Copyright (C) 2015-2022 Free Software Foundation, Inc. |
e4606348 JJ |
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 | ||
a6d22fb2 KCY |
171 | /* Tree version of priority_queue_find. */ |
172 | ||
173 | static struct gomp_task * | |
174 | priority_tree_find (enum priority_queue_type type, | |
175 | prio_splay_tree_node node, | |
176 | priority_queue_predicate pred) | |
177 | { | |
178 | again: | |
179 | if (!node) | |
180 | return NULL; | |
181 | struct gomp_task *task = priority_tree_find (type, node->right, pred); | |
182 | if (task) | |
183 | return task; | |
184 | task = priority_node_to_task (type, node->key.l.tasks); | |
185 | if (pred (task)) | |
186 | return task; | |
187 | node = node->left; | |
188 | goto again; | |
189 | } | |
190 | ||
191 | /* List version of priority_queue_find. */ | |
192 | ||
193 | static struct gomp_task * | |
194 | priority_list_find (enum priority_queue_type type, | |
195 | struct priority_list *list, | |
196 | priority_queue_predicate pred) | |
197 | { | |
198 | struct priority_node *node = list->tasks; | |
199 | if (!node) | |
200 | return NULL; | |
201 | ||
202 | do | |
203 | { | |
204 | struct gomp_task *task = priority_node_to_task (type, node); | |
205 | if (pred (task)) | |
206 | return task; | |
207 | node = node->next; | |
208 | } | |
209 | while (node != list->tasks); | |
210 | ||
211 | return NULL; | |
212 | } | |
213 | ||
214 | /* Return the highest priority task in the priority queue HEAD that | |
215 | satisfies the predicate PRED. HEAD contains tasks of type TYPE. */ | |
216 | ||
217 | struct gomp_task * | |
218 | priority_queue_find (enum priority_queue_type type, | |
219 | struct priority_queue *head, | |
220 | priority_queue_predicate pred) | |
221 | { | |
222 | if (priority_queue_multi_p (head)) | |
223 | return priority_tree_find (type, head->t.root, pred); | |
224 | else | |
225 | return priority_list_find (type, &head->l, pred); | |
226 | } | |
227 | ||
e4606348 JJ |
228 | /* Remove NODE from priority queue HEAD, wherever it may be inside the |
229 | tree. HEAD contains tasks of type TYPE. */ | |
230 | ||
231 | void | |
232 | priority_tree_remove (enum priority_queue_type type, | |
233 | struct priority_queue *head, | |
234 | struct priority_node *node) | |
235 | { | |
236 | /* ?? The only reason this function is not inlined is because we | |
237 | need to find the priority within gomp_task (which has not been | |
238 | completely defined in the header file). If the lack of inlining | |
239 | is a concern, we could pass the priority number as a | |
240 | parameter, or we could move this to libgomp.h. */ | |
241 | int priority = priority_node_to_task (type, node)->priority; | |
242 | ||
243 | /* ?? We could avoid this lookup by keeping a pointer to the key in | |
244 | the priority_node. */ | |
245 | struct priority_list *list | |
246 | = priority_queue_lookup_priority (head, priority); | |
247 | #if _LIBGOMP_CHECKING_ | |
248 | if (!list) | |
249 | gomp_fatal ("Unable to find priority %d", priority); | |
250 | #endif | |
251 | /* If NODE was the last in its priority, clean up the priority. */ | |
252 | if (priority_list_remove (list, node, MEMMODEL_RELAXED)) | |
253 | { | |
254 | prio_splay_tree_remove (&head->t, (prio_splay_tree_key) list); | |
255 | list->tasks = NULL; | |
256 | #if _LIBGOMP_CHECKING_ | |
257 | memset (list, 0xaf, sizeof (*list)); | |
258 | #endif | |
259 | free (list); | |
260 | } | |
261 | } | |
262 | ||
263 | /* Return the highest priority WAITING task in a splay tree NODE. If | |
264 | there are no WAITING tasks available, return NULL. | |
265 | ||
266 | NODE is a priority list containing tasks of type TYPE. | |
267 | ||
268 | The right most node in a tree contains the highest priority. | |
269 | Recurse down to find such a node. If the task at that max node is | |
270 | not WAITING, bubble back up and look at the remaining tasks | |
271 | in-order. */ | |
272 | ||
273 | static struct gomp_task * | |
274 | priority_tree_next_task_1 (enum priority_queue_type type, | |
275 | prio_splay_tree_node node) | |
276 | { | |
277 | again: | |
278 | if (!node) | |
279 | return NULL; | |
280 | struct gomp_task *ret = priority_tree_next_task_1 (type, node->right); | |
281 | if (ret) | |
282 | return ret; | |
283 | ret = priority_node_to_task (type, node->key.l.tasks); | |
284 | if (ret->kind == GOMP_TASK_WAITING) | |
285 | return ret; | |
286 | node = node->left; | |
287 | goto again; | |
288 | } | |
289 | ||
290 | /* Return the highest priority WAITING task from within Q1 and Q2, | |
291 | while giving preference to tasks from Q1. Q1 is a queue containing | |
292 | items of type TYPE1. Q2 is a queue containing items of type TYPE2. | |
293 | ||
294 | Since we are mostly interested in Q1, if there are no WAITING tasks | |
295 | in Q1, we don't bother checking Q2, and just return NULL. | |
296 | ||
297 | As a special case, Q2 can be NULL, in which case, we just choose | |
298 | the highest priority WAITING task in Q1. This is an optimization | |
299 | to speed up looking through only one queue. | |
300 | ||
301 | If the returned task is chosen from Q1, *Q1_CHOSEN_P is set to | |
302 | TRUE, otherwise it is set to FALSE. */ | |
303 | ||
304 | struct gomp_task * | |
305 | priority_tree_next_task (enum priority_queue_type type1, | |
306 | struct priority_queue *q1, | |
307 | enum priority_queue_type type2, | |
308 | struct priority_queue *q2, | |
309 | bool *q1_chosen_p) | |
310 | { | |
311 | struct gomp_task *t1 = priority_tree_next_task_1 (type1, q1->t.root); | |
312 | if (!t1 | |
313 | /* Special optimization when only searching through one queue. */ | |
314 | || !q2) | |
315 | { | |
316 | *q1_chosen_p = true; | |
317 | return t1; | |
318 | } | |
319 | struct gomp_task *t2 = priority_tree_next_task_1 (type2, q2->t.root); | |
320 | if (!t2 || t1->priority > t2->priority) | |
321 | { | |
322 | *q1_chosen_p = true; | |
323 | return t1; | |
324 | } | |
325 | if (t2->priority > t1->priority) | |
326 | { | |
327 | *q1_chosen_p = false; | |
328 | return t2; | |
329 | } | |
330 | /* If we get here, the priorities are the same, so we must look at | |
331 | parent_depends_on to make our decision. */ | |
332 | #if _LIBGOMP_CHECKING_ | |
333 | if (t1 != t2) | |
334 | gomp_fatal ("priority_tree_next_task: t1 != t2"); | |
335 | #endif | |
336 | if (t2->parent_depends_on && !t1->parent_depends_on) | |
337 | { | |
338 | *q1_chosen_p = false; | |
339 | return t2; | |
340 | } | |
341 | *q1_chosen_p = true; | |
342 | return t1; | |
343 | } | |
344 | ||
345 | /* Priority splay trees comparison function. */ | |
346 | static inline int | |
347 | prio_splay_compare (prio_splay_tree_key x, prio_splay_tree_key y) | |
348 | { | |
349 | if (x->l.priority == y->l.priority) | |
350 | return 0; | |
351 | return x->l.priority < y->l.priority ? -1 : 1; | |
352 | } | |
353 | ||
354 | /* Define another splay tree instantiation, for priority_list's. */ | |
355 | #define splay_tree_prefix prio | |
356 | #define splay_tree_c | |
357 | #include "splay-tree.h" |