]>
Commit | Line | Data |
---|---|---|
99dee823 | 1 | /* Copyright (C) 2015-2021 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 | /* Header file for a priority queue of GOMP tasks. */ | |
27 | ||
28 | /* ?? Perhaps all the priority_tree_* functions are complex and rare | |
29 | enough to go out-of-line and be moved to priority_queue.c. ?? */ | |
30 | ||
31 | #ifndef _PRIORITY_QUEUE_H_ | |
32 | #define _PRIORITY_QUEUE_H_ | |
33 | ||
34 | /* One task. */ | |
35 | ||
36 | struct priority_node | |
37 | { | |
38 | /* Next and previous chains in a circular doubly linked list for | |
39 | tasks within this task's priority. */ | |
40 | struct priority_node *next, *prev; | |
41 | }; | |
42 | ||
43 | /* All tasks within the same priority. */ | |
44 | ||
45 | struct priority_list | |
46 | { | |
47 | /* Priority of the tasks in this set. */ | |
48 | int priority; | |
49 | ||
50 | /* Tasks. */ | |
51 | struct priority_node *tasks; | |
52 | ||
53 | /* This points to the last of the higher priority WAITING tasks. | |
54 | Remember that for the children queue, we have: | |
55 | ||
56 | parent_depends_on WAITING tasks. | |
57 | !parent_depends_on WAITING tasks. | |
58 | TIED tasks. | |
59 | ||
60 | This is a pointer to the last of the parent_depends_on WAITING | |
61 | tasks which are essentially, higher priority items within their | |
62 | priority. */ | |
63 | struct priority_node *last_parent_depends_on; | |
64 | }; | |
65 | ||
66 | /* Another splay tree instantiation, for priority_list's. */ | |
67 | typedef struct prio_splay_tree_node_s *prio_splay_tree_node; | |
68 | typedef struct prio_splay_tree_s *prio_splay_tree; | |
69 | typedef struct prio_splay_tree_key_s *prio_splay_tree_key; | |
70 | struct prio_splay_tree_key_s { | |
71 | /* This structure must only containing a priority_list, as we cast | |
72 | prio_splay_tree_key to priority_list throughout. */ | |
73 | struct priority_list l; | |
74 | }; | |
75 | #define splay_tree_prefix prio | |
76 | #include "splay-tree.h" | |
77 | ||
78 | /* The entry point into a priority queue of tasks. | |
79 | ||
80 | There are two alternate implementations with which to store tasks: | |
81 | as a balanced tree of sorts, or as a simple list of tasks. If | |
82 | there are only priority-0 items (ROOT is NULL), we use the simple | |
83 | list, otherwise (ROOT is non-NULL) we use the tree. */ | |
84 | ||
85 | struct priority_queue | |
86 | { | |
87 | /* If t.root != NULL, this is a splay tree of priority_lists to hold | |
88 | all tasks. This is only used if multiple priorities are in play, | |
89 | otherwise we use the priority_list `l' below to hold all | |
90 | (priority-0) tasks. */ | |
91 | struct prio_splay_tree_s t; | |
92 | ||
93 | /* If T above is NULL, only priority-0 items exist, so keep them | |
94 | in a simple list. */ | |
95 | struct priority_list l; | |
96 | }; | |
97 | ||
98 | enum priority_insert_type { | |
99 | /* Insert at the beginning of a priority list. */ | |
100 | PRIORITY_INSERT_BEGIN, | |
101 | /* Insert at the end of a priority list. */ | |
102 | PRIORITY_INSERT_END | |
103 | }; | |
104 | ||
105 | /* Used to determine in which queue a given priority node belongs in. | |
106 | See pnode field of gomp_task. */ | |
107 | ||
108 | enum priority_queue_type | |
109 | { | |
110 | PQ_TEAM, /* Node belongs in gomp_team's task_queue. */ | |
111 | PQ_CHILDREN, /* Node belongs in parent's children_queue. */ | |
112 | PQ_TASKGROUP, /* Node belongs in taskgroup->taskgroup_queue. */ | |
113 | PQ_IGNORED = 999 | |
114 | }; | |
115 | ||
a6d22fb2 KCY |
116 | typedef bool (*priority_queue_predicate) (struct gomp_task *); |
117 | ||
e4606348 JJ |
118 | /* Priority queue implementation prototypes. */ |
119 | ||
120 | extern bool priority_queue_task_in_queue_p (enum priority_queue_type, | |
121 | struct priority_queue *, | |
122 | struct gomp_task *); | |
123 | extern void priority_queue_dump (enum priority_queue_type, | |
124 | struct priority_queue *); | |
125 | extern void priority_queue_verify (enum priority_queue_type, | |
126 | struct priority_queue *, bool); | |
a6d22fb2 KCY |
127 | extern struct gomp_task *priority_queue_find (enum priority_queue_type, |
128 | struct priority_queue *, | |
129 | priority_queue_predicate); | |
e4606348 JJ |
130 | extern void priority_tree_remove (enum priority_queue_type, |
131 | struct priority_queue *, | |
132 | struct priority_node *); | |
133 | extern struct gomp_task *priority_tree_next_task (enum priority_queue_type, | |
134 | struct priority_queue *, | |
135 | enum priority_queue_type, | |
136 | struct priority_queue *, | |
137 | bool *); | |
138 | ||
139 | /* Return TRUE if there is more than one priority in HEAD. This is | |
140 | used throughout to to choose between the fast path (priority 0 only | |
141 | items) and a world with multiple priorities. */ | |
142 | ||
143 | static inline bool | |
144 | priority_queue_multi_p (struct priority_queue *head) | |
145 | { | |
146 | return __builtin_expect (head->t.root != NULL, 0); | |
147 | } | |
148 | ||
149 | /* Initialize a priority queue. */ | |
150 | ||
151 | static inline void | |
152 | priority_queue_init (struct priority_queue *head) | |
153 | { | |
154 | head->t.root = NULL; | |
155 | /* To save a few microseconds, we don't initialize head->l.priority | |
156 | to 0 here. It is implied that priority will be 0 if head->t.root | |
157 | == NULL. | |
158 | ||
159 | priority_tree_insert() will fix this when we encounter multiple | |
160 | priorities. */ | |
161 | head->l.tasks = NULL; | |
162 | head->l.last_parent_depends_on = NULL; | |
163 | } | |
164 | ||
165 | static inline void | |
166 | priority_queue_free (struct priority_queue *head) | |
167 | { | |
168 | /* There's nothing to do, as tasks were freed as they were removed | |
169 | in priority_queue_remove. */ | |
170 | } | |
171 | ||
172 | /* Forward declarations. */ | |
173 | static inline size_t priority_queue_offset (enum priority_queue_type); | |
174 | static inline struct gomp_task *priority_node_to_task | |
175 | (enum priority_queue_type, | |
176 | struct priority_node *); | |
177 | static inline struct priority_node *task_to_priority_node | |
178 | (enum priority_queue_type, | |
179 | struct gomp_task *); | |
180 | ||
181 | /* Return TRUE if priority queue HEAD is empty. | |
182 | ||
183 | MODEL IS MEMMODEL_ACQUIRE if we should use an acquire atomic to | |
184 | read from the root of the queue, otherwise MEMMODEL_RELAXED if we | |
185 | should use a plain load. */ | |
186 | ||
187 | static inline _Bool | |
188 | priority_queue_empty_p (struct priority_queue *head, enum memmodel model) | |
189 | { | |
190 | /* Note: The acquire barriers on the loads here synchronize with | |
191 | the write of a NULL in gomp_task_run_post_remove_parent. It is | |
192 | not necessary that we synchronize with other non-NULL writes at | |
193 | this point, but we must ensure that all writes to memory by a | |
194 | child thread task work function are seen before we exit from | |
195 | GOMP_taskwait. */ | |
196 | if (priority_queue_multi_p (head)) | |
197 | { | |
198 | if (model == MEMMODEL_ACQUIRE) | |
199 | return __atomic_load_n (&head->t.root, MEMMODEL_ACQUIRE) == NULL; | |
200 | return head->t.root == NULL; | |
201 | } | |
202 | if (model == MEMMODEL_ACQUIRE) | |
203 | return __atomic_load_n (&head->l.tasks, MEMMODEL_ACQUIRE) == NULL; | |
204 | return head->l.tasks == NULL; | |
205 | } | |
206 | ||
207 | /* Look for a given PRIORITY in HEAD. Return it if found, otherwise | |
208 | return NULL. This only applies to the tree variant in HEAD. There | |
209 | is no point in searching for priorities in HEAD->L. */ | |
210 | ||
211 | static inline struct priority_list * | |
212 | priority_queue_lookup_priority (struct priority_queue *head, int priority) | |
213 | { | |
214 | if (head->t.root == NULL) | |
215 | return NULL; | |
216 | struct prio_splay_tree_key_s k; | |
217 | k.l.priority = priority; | |
218 | return (struct priority_list *) | |
219 | prio_splay_tree_lookup (&head->t, &k); | |
220 | } | |
221 | ||
222 | /* Insert task in DATA, with PRIORITY, in the priority list in LIST. | |
223 | LIST contains items of type TYPE. | |
224 | ||
225 | If POS is PRIORITY_INSERT_BEGIN, the new task is inserted at the | |
226 | top of its respective priority. If POS is PRIORITY_INSERT_END, the | |
227 | task is inserted at the end of its priority. | |
228 | ||
229 | If ADJUST_PARENT_DEPENDS_ON is TRUE, LIST is a children queue, and | |
230 | we must keep track of higher and lower priority WAITING tasks by | |
231 | keeping the queue's last_parent_depends_on field accurate. This | |
232 | only applies to the children queue, and the caller must ensure LIST | |
233 | is a children queue in this case. | |
234 | ||
235 | If ADJUST_PARENT_DEPENDS_ON is TRUE, TASK_IS_PARENT_DEPENDS_ON is | |
236 | set to the task's parent_depends_on field. If | |
237 | ADJUST_PARENT_DEPENDS_ON is FALSE, this field is irrelevant. | |
238 | ||
239 | Return the new priority_node. */ | |
240 | ||
241 | static inline void | |
242 | priority_list_insert (enum priority_queue_type type, | |
243 | struct priority_list *list, | |
244 | struct gomp_task *task, | |
245 | int priority, | |
246 | enum priority_insert_type pos, | |
247 | bool adjust_parent_depends_on, | |
248 | bool task_is_parent_depends_on) | |
249 | { | |
250 | struct priority_node *node = task_to_priority_node (type, task); | |
251 | if (list->tasks) | |
252 | { | |
253 | /* If we are keeping track of higher/lower priority items, | |
254 | but this is a lower priority WAITING task | |
255 | (parent_depends_on != NULL), put it after all ready to | |
256 | run tasks. See the comment in | |
257 | priority_queue_upgrade_task for a visual on how tasks | |
258 | should be organized. */ | |
259 | if (adjust_parent_depends_on | |
260 | && pos == PRIORITY_INSERT_BEGIN | |
261 | && list->last_parent_depends_on | |
262 | && !task_is_parent_depends_on) | |
263 | { | |
264 | struct priority_node *last_parent_depends_on | |
265 | = list->last_parent_depends_on; | |
266 | node->next = last_parent_depends_on->next; | |
267 | node->prev = last_parent_depends_on; | |
268 | } | |
269 | /* Otherwise, put it at the top/bottom of the queue. */ | |
270 | else | |
271 | { | |
272 | node->next = list->tasks; | |
273 | node->prev = list->tasks->prev; | |
274 | if (pos == PRIORITY_INSERT_BEGIN) | |
275 | list->tasks = node; | |
276 | } | |
277 | node->next->prev = node; | |
278 | node->prev->next = node; | |
279 | } | |
280 | else | |
281 | { | |
282 | node->next = node; | |
283 | node->prev = node; | |
284 | list->tasks = node; | |
285 | } | |
286 | if (adjust_parent_depends_on | |
287 | && list->last_parent_depends_on == NULL | |
288 | && task_is_parent_depends_on) | |
289 | list->last_parent_depends_on = node; | |
290 | } | |
291 | ||
292 | /* Tree version of priority_list_insert. */ | |
293 | ||
294 | static inline void | |
295 | priority_tree_insert (enum priority_queue_type type, | |
296 | struct priority_queue *head, | |
297 | struct gomp_task *task, | |
298 | int priority, | |
299 | enum priority_insert_type pos, | |
300 | bool adjust_parent_depends_on, | |
301 | bool task_is_parent_depends_on) | |
302 | { | |
303 | if (__builtin_expect (head->t.root == NULL, 0)) | |
304 | { | |
305 | /* The first time around, transfer any priority 0 items to the | |
306 | tree. */ | |
307 | if (head->l.tasks != NULL) | |
308 | { | |
309 | prio_splay_tree_node k = gomp_malloc (sizeof (*k)); | |
310 | k->left = NULL; | |
311 | k->right = NULL; | |
312 | k->key.l.priority = 0; | |
313 | k->key.l.tasks = head->l.tasks; | |
314 | k->key.l.last_parent_depends_on = head->l.last_parent_depends_on; | |
315 | prio_splay_tree_insert (&head->t, k); | |
316 | head->l.tasks = NULL; | |
317 | } | |
318 | } | |
319 | struct priority_list *list | |
320 | = priority_queue_lookup_priority (head, priority); | |
321 | if (!list) | |
322 | { | |
323 | prio_splay_tree_node k = gomp_malloc (sizeof (*k)); | |
324 | k->left = NULL; | |
325 | k->right = NULL; | |
326 | k->key.l.priority = priority; | |
327 | k->key.l.tasks = NULL; | |
328 | k->key.l.last_parent_depends_on = NULL; | |
329 | prio_splay_tree_insert (&head->t, k); | |
330 | list = &k->key.l; | |
331 | } | |
332 | priority_list_insert (type, list, task, priority, pos, | |
333 | adjust_parent_depends_on, | |
334 | task_is_parent_depends_on); | |
335 | } | |
336 | ||
337 | /* Generic version of priority_*_insert. */ | |
338 | ||
339 | static inline void | |
340 | priority_queue_insert (enum priority_queue_type type, | |
341 | struct priority_queue *head, | |
342 | struct gomp_task *task, | |
343 | int priority, | |
344 | enum priority_insert_type pos, | |
345 | bool adjust_parent_depends_on, | |
346 | bool task_is_parent_depends_on) | |
347 | { | |
348 | #if _LIBGOMP_CHECKING_ | |
349 | if (priority_queue_task_in_queue_p (type, head, task)) | |
350 | gomp_fatal ("Attempt to insert existing task %p", task); | |
351 | #endif | |
352 | if (priority_queue_multi_p (head) || __builtin_expect (priority > 0, 0)) | |
353 | priority_tree_insert (type, head, task, priority, pos, | |
354 | adjust_parent_depends_on, | |
355 | task_is_parent_depends_on); | |
356 | else | |
357 | priority_list_insert (type, &head->l, task, priority, pos, | |
358 | adjust_parent_depends_on, | |
359 | task_is_parent_depends_on); | |
360 | } | |
361 | ||
362 | /* If multiple priorities are in play, return the highest priority | |
363 | task from within Q1 and Q2, while giving preference to tasks from | |
364 | Q1. If the returned task is chosen from Q1, *Q1_CHOSEN_P is set to | |
365 | TRUE, otherwise it is set to FALSE. | |
366 | ||
367 | If multiple priorities are not in play (only 0 priorities are | |
368 | available), the next task is chosen exclusively from Q1. | |
369 | ||
370 | As a special case, Q2 can be NULL, in which case, we just choose | |
371 | the highest priority WAITING task in Q1. This is an optimization | |
372 | to speed up looking through only one queue. | |
373 | ||
374 | We assume Q1 has at least one item. */ | |
375 | ||
376 | static inline struct gomp_task * | |
377 | priority_queue_next_task (enum priority_queue_type t1, | |
378 | struct priority_queue *q1, | |
379 | enum priority_queue_type t2, | |
380 | struct priority_queue *q2, | |
381 | bool *q1_chosen_p) | |
382 | { | |
383 | #if _LIBGOMP_CHECKING_ | |
384 | if (priority_queue_empty_p (q1, MEMMODEL_RELAXED)) | |
385 | gomp_fatal ("priority_queue_next_task: Q1 is empty"); | |
386 | #endif | |
387 | if (priority_queue_multi_p (q1)) | |
388 | { | |
389 | struct gomp_task *t | |
390 | = priority_tree_next_task (t1, q1, t2, q2, q1_chosen_p); | |
391 | /* If T is NULL, there are no WAITING tasks in Q1. In which | |
392 | case, return any old (non-waiting) task which will cause the | |
393 | caller to do the right thing when checking T->KIND == | |
394 | GOMP_TASK_WAITING. */ | |
395 | if (!t) | |
396 | { | |
397 | #if _LIBGOMP_CHECKING_ | |
398 | if (*q1_chosen_p == false) | |
399 | gomp_fatal ("priority_queue_next_task inconsistency"); | |
400 | #endif | |
401 | return priority_node_to_task (t1, q1->t.root->key.l.tasks); | |
402 | } | |
403 | return t; | |
404 | } | |
405 | else | |
406 | { | |
407 | *q1_chosen_p = true; | |
408 | return priority_node_to_task (t1, q1->l.tasks); | |
409 | } | |
410 | } | |
411 | ||
412 | /* Remove NODE from LIST. | |
413 | ||
414 | If we are removing the one and only item in the list, and MODEL is | |
415 | MEMMODEL_RELEASE, use an atomic release to clear the list. | |
416 | ||
417 | If the list becomes empty after the remove, return TRUE. */ | |
418 | ||
419 | static inline bool | |
420 | priority_list_remove (struct priority_list *list, | |
421 | struct priority_node *node, | |
422 | enum memmodel model) | |
423 | { | |
424 | bool empty = false; | |
425 | node->prev->next = node->next; | |
426 | node->next->prev = node->prev; | |
427 | if (list->tasks == node) | |
428 | { | |
429 | if (node->next != node) | |
430 | list->tasks = node->next; | |
431 | else | |
432 | { | |
433 | /* We access task->children in GOMP_taskwait outside of | |
434 | the task lock mutex region, so need a release barrier | |
435 | here to ensure memory written by child_task->fn above | |
436 | is flushed before the NULL is written. */ | |
437 | if (model == MEMMODEL_RELEASE) | |
438 | __atomic_store_n (&list->tasks, NULL, MEMMODEL_RELEASE); | |
439 | else | |
440 | list->tasks = NULL; | |
441 | empty = true; | |
442 | goto remove_out; | |
443 | } | |
444 | } | |
445 | remove_out: | |
446 | #if _LIBGOMP_CHECKING_ | |
447 | memset (node, 0xaf, sizeof (*node)); | |
448 | #endif | |
449 | return empty; | |
450 | } | |
451 | ||
452 | /* This is the generic version of priority_list_remove. | |
453 | ||
454 | Remove NODE from priority queue HEAD. HEAD contains tasks of type TYPE. | |
455 | ||
456 | If we are removing the one and only item in the priority queue and | |
457 | MODEL is MEMMODEL_RELEASE, use an atomic release to clear the queue. | |
458 | ||
459 | If the queue becomes empty after the remove, return TRUE. */ | |
460 | ||
461 | static inline bool | |
462 | priority_queue_remove (enum priority_queue_type type, | |
463 | struct priority_queue *head, | |
464 | struct gomp_task *task, | |
465 | enum memmodel model) | |
466 | { | |
467 | #if _LIBGOMP_CHECKING_ | |
468 | if (!priority_queue_task_in_queue_p (type, head, task)) | |
469 | gomp_fatal ("Attempt to remove missing task %p", task); | |
470 | #endif | |
471 | if (priority_queue_multi_p (head)) | |
472 | { | |
473 | priority_tree_remove (type, head, task_to_priority_node (type, task)); | |
474 | if (head->t.root == NULL) | |
475 | { | |
476 | if (model == MEMMODEL_RELEASE) | |
477 | /* Errr, we store NULL twice, the alternative would be to | |
478 | use an atomic release directly in the splay tree | |
479 | routines. Worth it? */ | |
480 | __atomic_store_n (&head->t.root, NULL, MEMMODEL_RELEASE); | |
481 | return true; | |
482 | } | |
483 | return false; | |
484 | } | |
485 | else | |
486 | return priority_list_remove (&head->l, | |
487 | task_to_priority_node (type, task), model); | |
488 | } | |
489 | ||
490 | #endif /* _PRIORITY_QUEUE_H_ */ |