1/* Copyright (C) 2015-2017 Free Software Foundation, Inc.
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
36struct 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
45struct 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. */
67typedef struct prio_splay_tree_node_s *prio_splay_tree_node;
68typedef struct prio_splay_tree_s *prio_splay_tree;
69typedef struct prio_splay_tree_key_s *prio_splay_tree_key;
70struct 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
85struct 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
98enum 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
108enum 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
118extern bool priority_queue_task_in_queue_p (enum priority_queue_type,
119 struct priority_queue *,
120 struct gomp_task *);
121extern void priority_queue_dump (enum priority_queue_type,
122 struct priority_queue *);
123extern void priority_queue_verify (enum priority_queue_type,
124 struct priority_queue *, bool);
125extern void priority_tree_remove (enum priority_queue_type,
126 struct priority_queue *,
127 struct priority_node *);
128extern 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
138static inline bool
139priority_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
146static inline void
147priority_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
160static inline void
161priority_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. */
168static inline size_t priority_queue_offset (enum priority_queue_type);
169static inline struct gomp_task *priority_node_to_task
170 (enum priority_queue_type,
171 struct priority_node *);
172static 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
182static inline _Bool
183priority_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
206static inline struct priority_list *
207priority_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
236static inline void
237priority_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
289static inline void
290priority_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
334static inline void
335priority_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
371static inline struct gomp_task *
372priority_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
414static inline bool
415priority_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 }
440remove_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
456static inline bool
457priority_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_ */
486