1/* Copyright (C) 2015-2020 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