]>
Commit | Line | Data |
---|---|---|
a5544970 | 1 | /* Copyright (C) 2015-2019 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 | ||
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" |