|
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 /* 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
|
|
|
116 /* Priority queue implementation prototypes. */
|
|
|
117
|
|
|
118 extern bool priority_queue_task_in_queue_p (enum priority_queue_type,
|
|
|
119 struct priority_queue *,
|
|
|
120 struct gomp_task *);
|
|
|
121 extern void priority_queue_dump (enum priority_queue_type,
|
|
|
122 struct priority_queue *);
|
|
|
123 extern void priority_queue_verify (enum priority_queue_type,
|
|
|
124 struct priority_queue *, bool);
|
|
|
125 extern void priority_tree_remove (enum priority_queue_type,
|
|
|
126 struct priority_queue *,
|
|
|
127 struct priority_node *);
|
|
|
128 extern struct gomp_task *priority_tree_next_task (enum priority_queue_type,
|
|
|
129 struct priority_queue *,
|
|
|
130 enum priority_queue_type,
|
|
|
131 struct priority_queue *,
|
|
|
132 bool *);
|
|
|
133
|
|
|
134 /* Return TRUE if there is more than one priority in HEAD. This is
|
|
|
135 used throughout to to choose between the fast path (priority 0 only
|
|
|
136 items) and a world with multiple priorities. */
|
|
|
137
|
|
|
138 static inline bool
|
|
|
139 priority_queue_multi_p (struct priority_queue *head)
|
|
|
140 {
|
|
|
141 return __builtin_expect (head->t.root != NULL, 0);
|
|
|
142 }
|
|
|
143
|
|
|
144 /* Initialize a priority queue. */
|
|
|
145
|
|
|
146 static inline void
|
|
|
147 priority_queue_init (struct priority_queue *head)
|
|
|
148 {
|
|
|
149 head->t.root = NULL;
|
|
|
150 /* To save a few microseconds, we don't initialize head->l.priority
|
|
|
151 to 0 here. It is implied that priority will be 0 if head->t.root
|
|
|
152 == NULL.
|
|
|
153
|
|
|
154 priority_tree_insert() will fix this when we encounter multiple
|
|
|
155 priorities. */
|
|
|
156 head->l.tasks = NULL;
|
|
|
157 head->l.last_parent_depends_on = NULL;
|
|
|
158 }
|
|
|
159
|
|
|
160 static inline void
|
|
|
161 priority_queue_free (struct priority_queue *head)
|
|
|
162 {
|
|
|
163 /* There's nothing to do, as tasks were freed as they were removed
|
|
|
164 in priority_queue_remove. */
|
|
|
165 }
|
|
|
166
|
|
|
167 /* Forward declarations. */
|
|
|
168 static inline size_t priority_queue_offset (enum priority_queue_type);
|
|
|
169 static inline struct gomp_task *priority_node_to_task
|
|
|
170 (enum priority_queue_type,
|
|
|
171 struct priority_node *);
|
|
|
172 static inline struct priority_node *task_to_priority_node
|
|
|
173 (enum priority_queue_type,
|
|
|
174 struct gomp_task *);
|
|
|
175
|
|
|
176 /* Return TRUE if priority queue HEAD is empty.
|
|
|
177
|
|
|
178 MODEL IS MEMMODEL_ACQUIRE if we should use an acquire atomic to
|
|
|
179 read from the root of the queue, otherwise MEMMODEL_RELAXED if we
|
|
|
180 should use a plain load. */
|
|
|
181
|
|
|
182 static inline _Bool
|
|
|
183 priority_queue_empty_p (struct priority_queue *head, enum memmodel model)
|
|
|
184 {
|
|
|
185 /* Note: The acquire barriers on the loads here synchronize with
|
|
|
186 the write of a NULL in gomp_task_run_post_remove_parent. It is
|
|
|
187 not necessary that we synchronize with other non-NULL writes at
|
|
|
188 this point, but we must ensure that all writes to memory by a
|
|
|
189 child thread task work function are seen before we exit from
|
|
|
190 GOMP_taskwait. */
|
|
|
191 if (priority_queue_multi_p (head))
|
|
|
192 {
|
|
|
193 if (model == MEMMODEL_ACQUIRE)
|
|
|
194 return __atomic_load_n (&head->t.root, MEMMODEL_ACQUIRE) == NULL;
|
|
|
195 return head->t.root == NULL;
|
|
|
196 }
|
|
|
197 if (model == MEMMODEL_ACQUIRE)
|
|
|
198 return __atomic_load_n (&head->l.tasks, MEMMODEL_ACQUIRE) == NULL;
|
|
|
199 return head->l.tasks == NULL;
|
|
|
200 }
|
|
|
201
|
|
|
202 /* Look for a given PRIORITY in HEAD. Return it if found, otherwise
|
|
|
203 return NULL. This only applies to the tree variant in HEAD. There
|
|
|
204 is no point in searching for priorities in HEAD->L. */
|
|
|
205
|
|
|
206 static inline struct priority_list *
|
|
|
207 priority_queue_lookup_priority (struct priority_queue *head, int priority)
|
|
|
208 {
|
|
|
209 if (head->t.root == NULL)
|
|
|
210 return NULL;
|
|
|
211 struct prio_splay_tree_key_s k;
|
|
|
212 k.l.priority = priority;
|
|
|
213 return (struct priority_list *)
|
|
|
214 prio_splay_tree_lookup (&head->t, &k);
|
|
|
215 }
|
|
|
216
|
|
|
217 /* Insert task in DATA, with PRIORITY, in the priority list in LIST.
|
|
|
218 LIST contains items of type TYPE.
|
|
|
219
|
|
|
220 If POS is PRIORITY_INSERT_BEGIN, the new task is inserted at the
|
|
|
221 top of its respective priority. If POS is PRIORITY_INSERT_END, the
|
|
|
222 task is inserted at the end of its priority.
|
|
|
223
|
|
|
224 If ADJUST_PARENT_DEPENDS_ON is TRUE, LIST is a children queue, and
|
|
|
225 we must keep track of higher and lower priority WAITING tasks by
|
|
|
226 keeping the queue's last_parent_depends_on field accurate. This
|
|
|
227 only applies to the children queue, and the caller must ensure LIST
|
|
|
228 is a children queue in this case.
|
|
|
229
|
|
|
230 If ADJUST_PARENT_DEPENDS_ON is TRUE, TASK_IS_PARENT_DEPENDS_ON is
|
|
|
231 set to the task's parent_depends_on field. If
|
|
|
232 ADJUST_PARENT_DEPENDS_ON is FALSE, this field is irrelevant.
|
|
|
233
|
|
|
234 Return the new priority_node. */
|
|
|
235
|
|
|
236 static inline void
|
|
|
237 priority_list_insert (enum priority_queue_type type,
|
|
|
238 struct priority_list *list,
|
|
|
239 struct gomp_task *task,
|
|
|
240 int priority,
|
|
|
241 enum priority_insert_type pos,
|
|
|
242 bool adjust_parent_depends_on,
|
|
|
243 bool task_is_parent_depends_on)
|
|
|
244 {
|
|
|
245 struct priority_node *node = task_to_priority_node (type, task);
|
|
|
246 if (list->tasks)
|
|
|
247 {
|
|
|
248 /* If we are keeping track of higher/lower priority items,
|
|
|
249 but this is a lower priority WAITING task
|
|
|
250 (parent_depends_on != NULL), put it after all ready to
|
|
|
251 run tasks. See the comment in
|
|
|
252 priority_queue_upgrade_task for a visual on how tasks
|
|
|
253 should be organized. */
|
|
|
254 if (adjust_parent_depends_on
|
|
|
255 && pos == PRIORITY_INSERT_BEGIN
|
|
|
256 && list->last_parent_depends_on
|
|
|
257 && !task_is_parent_depends_on)
|
|
|
258 {
|
|
|
259 struct priority_node *last_parent_depends_on
|
|
|
260 = list->last_parent_depends_on;
|
|
|
261 node->next = last_parent_depends_on->next;
|
|
|
262 node->prev = last_parent_depends_on;
|
|
|
263 }
|
|
|
264 /* Otherwise, put it at the top/bottom of the queue. */
|
|
|
265 else
|
|
|
266 {
|
|
|
267 node->next = list->tasks;
|
|
|
268 node->prev = list->tasks->prev;
|
|
|
269 if (pos == PRIORITY_INSERT_BEGIN)
|
|
|
270 list->tasks = node;
|
|
|
271 }
|
|
|
272 node->next->prev = node;
|
|
|
273 node->prev->next = node;
|
|
|
274 }
|
|
|
275 else
|
|
|
276 {
|
|
|
277 node->next = node;
|
|
|
278 node->prev = node;
|
|
|
279 list->tasks = node;
|
|
|
280 }
|
|
|
281 if (adjust_parent_depends_on
|
|
|
282 && list->last_parent_depends_on == NULL
|
|
|
283 && task_is_parent_depends_on)
|
|
|
284 list->last_parent_depends_on = node;
|
|
|
285 }
|
|
|
286
|
|
|
287 /* Tree version of priority_list_insert. */
|
|
|
288
|
|
|
289 static inline void
|
|
|
290 priority_tree_insert (enum priority_queue_type type,
|
|
|
291 struct priority_queue *head,
|
|
|
292 struct gomp_task *task,
|
|
|
293 int priority,
|
|
|
294 enum priority_insert_type pos,
|
|
|
295 bool adjust_parent_depends_on,
|
|
|
296 bool task_is_parent_depends_on)
|
|
|
297 {
|
|
|
298 if (__builtin_expect (head->t.root == NULL, 0))
|
|
|
299 {
|
|
|
300 /* The first time around, transfer any priority 0 items to the
|
|
|
301 tree. */
|
|
|
302 if (head->l.tasks != NULL)
|
|
|
303 {
|
|
|
304 prio_splay_tree_node k = gomp_malloc (sizeof (*k));
|
|
|
305 k->left = NULL;
|
|
|
306 k->right = NULL;
|
|
|
307 k->key.l.priority = 0;
|
|
|
308 k->key.l.tasks = head->l.tasks;
|
|
|
309 k->key.l.last_parent_depends_on = head->l.last_parent_depends_on;
|
|
|
310 prio_splay_tree_insert (&head->t, k);
|
|
|
311 head->l.tasks = NULL;
|
|
|
312 }
|
|
|
313 }
|
|
|
314 struct priority_list *list
|
|
|
315 = priority_queue_lookup_priority (head, priority);
|
|
|
316 if (!list)
|
|
|
317 {
|
|
|
318 prio_splay_tree_node k = gomp_malloc (sizeof (*k));
|
|
|
319 k->left = NULL;
|
|
|
320 k->right = NULL;
|
|
|
321 k->key.l.priority = priority;
|
|
|
322 k->key.l.tasks = NULL;
|
|
|
323 k->key.l.last_parent_depends_on = NULL;
|
|
|
324 prio_splay_tree_insert (&head->t, k);
|
|
|
325 list = &k->key.l;
|
|
|
326 }
|
|
|
327 priority_list_insert (type, list, task, priority, pos,
|
|
|
328 adjust_parent_depends_on,
|
|
|
329 task_is_parent_depends_on);
|
|
|
330 }
|
|
|
331
|
|
|
332 /* Generic version of priority_*_insert. */
|
|
|
333
|
|
|
334 static inline void
|
|
|
335 priority_queue_insert (enum priority_queue_type type,
|
|
|
336 struct priority_queue *head,
|
|
|
337 struct gomp_task *task,
|
|
|
338 int priority,
|
|
|
339 enum priority_insert_type pos,
|
|
|
340 bool adjust_parent_depends_on,
|
|
|
341 bool task_is_parent_depends_on)
|
|
|
342 {
|
|
|
343 #if _LIBGOMP_CHECKING_
|
|
|
344 if (priority_queue_task_in_queue_p (type, head, task))
|
|
|
345 gomp_fatal ("Attempt to insert existing task %p", task);
|
|
|
346 #endif
|
|
|
347 if (priority_queue_multi_p (head) || __builtin_expect (priority > 0, 0))
|
|
|
348 priority_tree_insert (type, head, task, priority, pos,
|
|
|
349 adjust_parent_depends_on,
|
|
|
350 task_is_parent_depends_on);
|
|
|
351 else
|
|
|
352 priority_list_insert (type, &head->l, task, priority, pos,
|
|
|
353 adjust_parent_depends_on,
|
|
|
354 task_is_parent_depends_on);
|
|
|
355 }
|
|
|
356
|
|
|
357 /* If multiple priorities are in play, return the highest priority
|
|
|
358 task from within Q1 and Q2, while giving preference to tasks from
|
|
|
359 Q1. If the returned task is chosen from Q1, *Q1_CHOSEN_P is set to
|
|
|
360 TRUE, otherwise it is set to FALSE.
|
|
|
361
|
|
|
362 If multiple priorities are not in play (only 0 priorities are
|
|
|
363 available), the next task is chosen exclusively from Q1.
|
|
|
364
|
|
|
365 As a special case, Q2 can be NULL, in which case, we just choose
|
|
|
366 the highest priority WAITING task in Q1. This is an optimization
|
|
|
367 to speed up looking through only one queue.
|
|
|
368
|
|
|
369 We assume Q1 has at least one item. */
|
|
|
370
|
|
|
371 static inline struct gomp_task *
|
|
|
372 priority_queue_next_task (enum priority_queue_type t1,
|
|
|
373 struct priority_queue *q1,
|
|
|
374 enum priority_queue_type t2,
|
|
|
375 struct priority_queue *q2,
|
|
|
376 bool *q1_chosen_p)
|
|
|
377 {
|
|
|
378 #if _LIBGOMP_CHECKING_
|
|
|
379 if (priority_queue_empty_p (q1, MEMMODEL_RELAXED))
|
|
|
380 gomp_fatal ("priority_queue_next_task: Q1 is empty");
|
|
|
381 #endif
|
|
|
382 if (priority_queue_multi_p (q1))
|
|
|
383 {
|
|
|
384 struct gomp_task *t
|
|
|
385 = priority_tree_next_task (t1, q1, t2, q2, q1_chosen_p);
|
|
|
386 /* If T is NULL, there are no WAITING tasks in Q1. In which
|
|
|
387 case, return any old (non-waiting) task which will cause the
|
|
|
388 caller to do the right thing when checking T->KIND ==
|
|
|
389 GOMP_TASK_WAITING. */
|
|
|
390 if (!t)
|
|
|
391 {
|
|
|
392 #if _LIBGOMP_CHECKING_
|
|
|
393 if (*q1_chosen_p == false)
|
|
|
394 gomp_fatal ("priority_queue_next_task inconsistency");
|
|
|
395 #endif
|
|
|
396 return priority_node_to_task (t1, q1->t.root->key.l.tasks);
|
|
|
397 }
|
|
|
398 return t;
|
|
|
399 }
|
|
|
400 else
|
|
|
401 {
|
|
|
402 *q1_chosen_p = true;
|
|
|
403 return priority_node_to_task (t1, q1->l.tasks);
|
|
|
404 }
|
|
|
405 }
|
|
|
406
|
|
|
407 /* Remove NODE from LIST.
|
|
|
408
|
|
|
409 If we are removing the one and only item in the list, and MODEL is
|
|
|
410 MEMMODEL_RELEASE, use an atomic release to clear the list.
|
|
|
411
|
|
|
412 If the list becomes empty after the remove, return TRUE. */
|
|
|
413
|
|
|
414 static inline bool
|
|
|
415 priority_list_remove (struct priority_list *list,
|
|
|
416 struct priority_node *node,
|
|
|
417 enum memmodel model)
|
|
|
418 {
|
|
|
419 bool empty = false;
|
|
|
420 node->prev->next = node->next;
|
|
|
421 node->next->prev = node->prev;
|
|
|
422 if (list->tasks == node)
|
|
|
423 {
|
|
|
424 if (node->next != node)
|
|
|
425 list->tasks = node->next;
|
|
|
426 else
|
|
|
427 {
|
|
|
428 /* We access task->children in GOMP_taskwait outside of
|
|
|
429 the task lock mutex region, so need a release barrier
|
|
|
430 here to ensure memory written by child_task->fn above
|
|
|
431 is flushed before the NULL is written. */
|
|
|
432 if (model == MEMMODEL_RELEASE)
|
|
|
433 __atomic_store_n (&list->tasks, NULL, MEMMODEL_RELEASE);
|
|
|
434 else
|
|
|
435 list->tasks = NULL;
|
|
|
436 empty = true;
|
|
|
437 goto remove_out;
|
|
|
438 }
|
|
|
439 }
|
|
|
440 remove_out:
|
|
|
441 #if _LIBGOMP_CHECKING_
|
|
|
442 memset (node, 0xaf, sizeof (*node));
|
|
|
443 #endif
|
|
|
444 return empty;
|
|
|
445 }
|
|
|
446
|
|
|
447 /* This is the generic version of priority_list_remove.
|
|
|
448
|
|
|
449 Remove NODE from priority queue HEAD. HEAD contains tasks of type TYPE.
|
|
|
450
|
|
|
451 If we are removing the one and only item in the priority queue and
|
|
|
452 MODEL is MEMMODEL_RELEASE, use an atomic release to clear the queue.
|
|
|
453
|
|
|
454 If the queue becomes empty after the remove, return TRUE. */
|
|
|
455
|
|
|
456 static inline bool
|
|
|
457 priority_queue_remove (enum priority_queue_type type,
|
|
|
458 struct priority_queue *head,
|
|
|
459 struct gomp_task *task,
|
|
|
460 enum memmodel model)
|
|
|
461 {
|
|
|
462 #if _LIBGOMP_CHECKING_
|
|
|
463 if (!priority_queue_task_in_queue_p (type, head, task))
|
|
|
464 gomp_fatal ("Attempt to remove missing task %p", task);
|
|
|
465 #endif
|
|
|
466 if (priority_queue_multi_p (head))
|
|
|
467 {
|
|
|
468 priority_tree_remove (type, head, task_to_priority_node (type, task));
|
|
|
469 if (head->t.root == NULL)
|
|
|
470 {
|
|
|
471 if (model == MEMMODEL_RELEASE)
|
|
|
472 /* Errr, we store NULL twice, the alternative would be to
|
|
|
473 use an atomic release directly in the splay tree
|
|
|
474 routines. Worth it? */
|
|
|
475 __atomic_store_n (&head->t.root, NULL, MEMMODEL_RELEASE);
|
|
|
476 return true;
|
|
|
477 }
|
|
|
478 return false;
|
|
|
479 }
|
|
|
480 else
|
|
|
481 return priority_list_remove (&head->l,
|
|
|
482 task_to_priority_node (type, task), model);
|
|
|
483 }
|
|
|
484
|
|
|
485 #endif /* _PRIORITY_QUEUE_H_ */
|
