aboutsummaryrefslogtreecommitdiff
path: root/libgomp/priority_queue.h
blob: e032d0799f3edd82d9b00c5721b4af44bbaa3e76 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
/* Copyright (C) 2015-2022 Free Software Foundation, Inc.
   Contributed by Aldy Hernandez <aldyh@redhat.com>.

   This file is part of the GNU Offloading and Multi Processing Library
   (libgomp).

   Libgomp is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3, or (at your option)
   any later version.

   Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY
   WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
   FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
   more details.

   Under Section 7 of GPL version 3, you are granted additional
   permissions described in the GCC Runtime Library Exception, version
   3.1, as published by the Free Software Foundation.

   You should have received a copy of the GNU General Public License and
   a copy of the GCC Runtime Library Exception along with this program;
   see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
   <http://www.gnu.org/licenses/>.  */

/* Header file for a priority queue of GOMP tasks.  */

/* ?? Perhaps all the priority_tree_* functions are complex and rare
   enough to go out-of-line and be moved to priority_queue.c.  ??  */

#ifndef _PRIORITY_QUEUE_H_
#define _PRIORITY_QUEUE_H_

/* One task.  */

struct priority_node
{
  /* Next and previous chains in a circular doubly linked list for
     tasks within this task's priority.  */
  struct priority_node *next, *prev;
};

/* All tasks within the same priority.  */

struct priority_list
{
  /* Priority of the tasks in this set.  */
  int priority;

  /* Tasks.  */
  struct priority_node *tasks;

  /* This points to the last of the higher priority WAITING tasks.
     Remember that for the children queue, we have:

	parent_depends_on WAITING tasks.
	!parent_depends_on WAITING tasks.
	TIED tasks.

     This is a pointer to the last of the parent_depends_on WAITING
     tasks which are essentially, higher priority items within their
     priority.  */
  struct priority_node *last_parent_depends_on;
};

/* Another splay tree instantiation, for priority_list's.  */
typedef struct prio_splay_tree_node_s *prio_splay_tree_node;
typedef struct prio_splay_tree_s *prio_splay_tree;
typedef struct prio_splay_tree_key_s *prio_splay_tree_key;
struct prio_splay_tree_key_s {
  /* This structure must only containing a priority_list, as we cast
     prio_splay_tree_key to priority_list throughout.  */
  struct priority_list l;
};
#define splay_tree_prefix prio
#include "splay-tree.h"

/* The entry point into a priority queue of tasks.

   There are two alternate implementations with which to store tasks:
   as a balanced tree of sorts, or as a simple list of tasks.  If
   there are only priority-0 items (ROOT is NULL), we use the simple
   list, otherwise (ROOT is non-NULL) we use the tree.  */

struct priority_queue
{
  /* If t.root != NULL, this is a splay tree of priority_lists to hold
     all tasks.  This is only used if multiple priorities are in play,
     otherwise we use the priority_list `l' below to hold all
     (priority-0) tasks.  */
  struct prio_splay_tree_s t;

  /* If T above is NULL, only priority-0 items exist, so keep them
     in a simple list.  */
  struct priority_list l;
};

enum priority_insert_type {
  /* Insert at the beginning of a priority list.  */
  PRIORITY_INSERT_BEGIN,
  /* Insert at the end of a priority list.  */
  PRIORITY_INSERT_END
};

/* Used to determine in which queue a given priority node belongs in.
   See pnode field of gomp_task.  */

enum priority_queue_type
{
  PQ_TEAM,	    /* Node belongs in gomp_team's task_queue.  */
  PQ_CHILDREN,	    /* Node belongs in parent's children_queue.  */
  PQ_TASKGROUP,	    /* Node belongs in taskgroup->taskgroup_queue.  */
  PQ_IGNORED = 999
};

typedef bool (*priority_queue_predicate) (struct gomp_task *);

/* Priority queue implementation prototypes.  */

extern bool priority_queue_task_in_queue_p (enum priority_queue_type,
					    struct priority_queue *,
					    struct gomp_task *);
extern void priority_queue_dump (enum priority_queue_type,
				 struct priority_queue *);
extern void priority_queue_verify (enum priority_queue_type,
				   struct priority_queue *, bool);
extern struct gomp_task *priority_queue_find (enum priority_queue_type,
					      struct priority_queue *,
					      priority_queue_predicate);
extern void priority_tree_remove (enum priority_queue_type,
				  struct priority_queue *,
				  struct priority_node *);
extern struct gomp_task *priority_tree_next_task (enum priority_queue_type,
						  struct priority_queue *,
						  enum priority_queue_type,
						  struct priority_queue *,
						  bool *);

/* Return TRUE if there is more than one priority in HEAD.  This is
   used throughout to to choose between the fast path (priority 0 only
   items) and a world with multiple priorities.  */

static inline bool
priority_queue_multi_p (struct priority_queue *head)
{
  return __builtin_expect (head->t.root != NULL, 0);
}

/* Initialize a priority queue.  */

static inline void
priority_queue_init (struct priority_queue *head)
{
  head->t.root = NULL;
  /* To save a few microseconds, we don't initialize head->l.priority
     to 0 here.  It is implied that priority will be 0 if head->t.root
     == NULL.

     priority_tree_insert() will fix this when we encounter multiple
     priorities.  */
  head->l.tasks = NULL;
  head->l.last_parent_depends_on = NULL;
}

static inline void
priority_queue_free (struct priority_queue *head)
{
  /* There's nothing to do, as tasks were freed as they were removed
     in priority_queue_remove.  */
}

/* Forward declarations.  */
static inline size_t priority_queue_offset (enum priority_queue_type);
static inline struct gomp_task *priority_node_to_task
				(enum priority_queue_type,
				 struct priority_node *);
static inline struct priority_node *task_to_priority_node
				    (enum priority_queue_type,
				     struct gomp_task *);

/* Return TRUE if priority queue HEAD is empty.

   MODEL IS MEMMODEL_ACQUIRE if we should use an acquire atomic to
   read from the root of the queue, otherwise MEMMODEL_RELAXED if we
   should use a plain load.  */

static inline _Bool
priority_queue_empty_p (struct priority_queue *head, enum memmodel model)
{
  /* Note: The acquire barriers on the loads here synchronize with
     the write of a NULL in gomp_task_run_post_remove_parent.  It is
     not necessary that we synchronize with other non-NULL writes at
     this point, but we must ensure that all writes to memory by a
     child thread task work function are seen before we exit from
     GOMP_taskwait.  */
  if (priority_queue_multi_p (head))
    {
      if (model == MEMMODEL_ACQUIRE)
	return __atomic_load_n (&head->t.root, MEMMODEL_ACQUIRE) == NULL;
      return head->t.root == NULL;
    }
  if (model == MEMMODEL_ACQUIRE)
    return __atomic_load_n (&head->l.tasks, MEMMODEL_ACQUIRE) == NULL;
  return head->l.tasks == NULL;
}

/* Look for a given PRIORITY in HEAD.  Return it if found, otherwise
   return NULL.  This only applies to the tree variant in HEAD.  There
   is no point in searching for priorities in HEAD->L.  */

static inline struct priority_list *
priority_queue_lookup_priority (struct priority_queue *head, int priority)
{
  if (head->t.root == NULL)
    return NULL;
  struct prio_splay_tree_key_s k;
  k.l.priority = priority;
  return (struct priority_list *)
    prio_splay_tree_lookup (&head->t, &k);
}

/* Insert task in DATA, with PRIORITY, in the priority list in LIST.
   LIST contains items of type TYPE.

   If POS is PRIORITY_INSERT_BEGIN, the new task is inserted at the
   top of its respective priority.  If POS is PRIORITY_INSERT_END, the
   task is inserted at the end of its priority.

   If ADJUST_PARENT_DEPENDS_ON is TRUE, LIST is a children queue, and
   we must keep track of higher and lower priority WAITING tasks by
   keeping the queue's last_parent_depends_on field accurate.  This
   only applies to the children queue, and the caller must ensure LIST
   is a children queue in this case.

   If ADJUST_PARENT_DEPENDS_ON is TRUE, TASK_IS_PARENT_DEPENDS_ON is
   set to the task's parent_depends_on field.  If
   ADJUST_PARENT_DEPENDS_ON is FALSE, this field is irrelevant.

   Return the new priority_node.  */

static inline void
priority_list_insert (enum priority_queue_type type,
		      struct priority_list *list,
		      struct gomp_task *task,
		      int priority,
		      enum priority_insert_type pos,
		      bool adjust_parent_depends_on,
		      bool task_is_parent_depends_on)
{
  struct priority_node *node = task_to_priority_node (type, task);
  if (list->tasks)
    {
      /* If we are keeping track of higher/lower priority items,
	 but this is a lower priority WAITING task
	 (parent_depends_on != NULL), put it after all ready to
	 run tasks.  See the comment in
	 priority_queue_upgrade_task for a visual on how tasks
	 should be organized.  */
      if (adjust_parent_depends_on
	  && pos == PRIORITY_INSERT_BEGIN
	  && list->last_parent_depends_on
	  && !task_is_parent_depends_on)
	{
	  struct priority_node *last_parent_depends_on
	    = list->last_parent_depends_on;
	  node->next = last_parent_depends_on->next;
	  node->prev = last_parent_depends_on;
	}
      /* Otherwise, put it at the top/bottom of the queue.  */
      else
	{
	  node->next = list->tasks;
	  node->prev = list->tasks->prev;
	  if (pos == PRIORITY_INSERT_BEGIN)
	    list->tasks = node;
	}
      node->next->prev = node;
      node->prev->next = node;
    }
  else
    {
      node->next = node;
      node->prev = node;
      list->tasks = node;
    }
  if (adjust_parent_depends_on
      && list->last_parent_depends_on == NULL
      && task_is_parent_depends_on)
    list->last_parent_depends_on = node;
}

/* Tree version of priority_list_insert.  */

static inline void
priority_tree_insert (enum priority_queue_type type,
		      struct priority_queue *head,
		      struct gomp_task *task,
		      int priority,
		      enum priority_insert_type pos,
		      bool adjust_parent_depends_on,
		      bool task_is_parent_depends_on)
{
  if (__builtin_expect (head->t.root == NULL, 0))
    {
      /* The first time around, transfer any priority 0 items to the
	 tree.  */
      if (head->l.tasks != NULL)
	{
	  prio_splay_tree_node k = gomp_malloc (sizeof (*k));
	  k->left = NULL;
	  k->right = NULL;
	  k->key.l.priority = 0;
	  k->key.l.tasks = head->l.tasks;
	  k->key.l.last_parent_depends_on = head->l.last_parent_depends_on;
	  prio_splay_tree_insert (&head->t, k);
	  head->l.tasks = NULL;
	}
    }
  struct priority_list *list
    = priority_queue_lookup_priority (head, priority);
  if (!list)
    {
      prio_splay_tree_node k = gomp_malloc (sizeof (*k));
      k->left = NULL;
      k->right = NULL;
      k->key.l.priority = priority;
      k->key.l.tasks = NULL;
      k->key.l.last_parent_depends_on = NULL;
      prio_splay_tree_insert (&head->t, k);
      list = &k->key.l;
    }
  priority_list_insert (type, list, task, priority, pos,
			adjust_parent_depends_on,
			task_is_parent_depends_on);
}

/* Generic version of priority_*_insert.  */

static inline void
priority_queue_insert (enum priority_queue_type type,
		       struct priority_queue *head,
		       struct gomp_task *task,
		       int priority,
		       enum priority_insert_type pos,
		       bool adjust_parent_depends_on,
		       bool task_is_parent_depends_on)
{
#if _LIBGOMP_CHECKING_
  if (priority_queue_task_in_queue_p (type, head, task))
    gomp_fatal ("Attempt to insert existing task %p", task);
#endif
  if (priority_queue_multi_p (head) || __builtin_expect (priority > 0, 0))
    priority_tree_insert (type, head, task, priority, pos,
			  adjust_parent_depends_on,
			  task_is_parent_depends_on);
  else
    priority_list_insert (type, &head->l, task, priority, pos,
			  adjust_parent_depends_on,
			  task_is_parent_depends_on);
}

/* If multiple priorities are in play, return the highest priority
   task from within Q1 and Q2, while giving preference to tasks from
   Q1.  If the returned task is chosen from Q1, *Q1_CHOSEN_P is set to
   TRUE, otherwise it is set to FALSE.

   If multiple priorities are not in play (only 0 priorities are
   available), the next task is chosen exclusively from Q1.

   As a special case, Q2 can be NULL, in which case, we just choose
   the highest priority WAITING task in Q1.  This is an optimization
   to speed up looking through only one queue.

   We assume Q1 has at least one item.  */

static inline struct gomp_task *
priority_queue_next_task (enum priority_queue_type t1,
			  struct priority_queue *q1,
			  enum priority_queue_type t2,
			  struct priority_queue *q2,
			  bool *q1_chosen_p)
{
#if _LIBGOMP_CHECKING_
  if (priority_queue_empty_p (q1, MEMMODEL_RELAXED))
    gomp_fatal ("priority_queue_next_task: Q1 is empty");
#endif
  if (priority_queue_multi_p (q1))
    {
      struct gomp_task *t
	= priority_tree_next_task (t1, q1, t2, q2, q1_chosen_p);
      /* If T is NULL, there are no WAITING tasks in Q1.  In which
	 case, return any old (non-waiting) task which will cause the
	 caller to do the right thing when checking T->KIND ==
	 GOMP_TASK_WAITING.  */
      if (!t)
	{
#if _LIBGOMP_CHECKING_
	  if (*q1_chosen_p == false)
	    gomp_fatal ("priority_queue_next_task inconsistency");
#endif
	  return priority_node_to_task (t1, q1->t.root->key.l.tasks);
	}
      return t;
    }
  else
    {
      *q1_chosen_p = true;
      return priority_node_to_task (t1, q1->l.tasks);
    }
}

/* Remove NODE from LIST.

   If we are removing the one and only item in the list, and MODEL is
   MEMMODEL_RELEASE, use an atomic release to clear the list.

   If the list becomes empty after the remove, return TRUE.  */

static inline bool
priority_list_remove (struct priority_list *list,
		      struct priority_node *node,
		      enum memmodel model)
{
  bool empty = false;
  node->prev->next = node->next;
  node->next->prev = node->prev;
  if (list->tasks == node)
    {
      if (node->next != node)
	list->tasks = node->next;
      else
	{
	  /* We access task->children in GOMP_taskwait outside of
	     the task lock mutex region, so need a release barrier
	     here to ensure memory written by child_task->fn above
	     is flushed before the NULL is written.  */
	  if (model == MEMMODEL_RELEASE)
	    __atomic_store_n (&list->tasks, NULL, MEMMODEL_RELEASE);
	  else
	    list->tasks = NULL;
	  empty = true;
	  goto remove_out;
	}
    }
remove_out:
#if _LIBGOMP_CHECKING_
  memset (node, 0xaf, sizeof (*node));
#endif
  return empty;
}

/* This is the generic version of priority_list_remove.

   Remove NODE from priority queue HEAD.  HEAD contains tasks of type TYPE.

   If we are removing the one and only item in the priority queue and
   MODEL is MEMMODEL_RELEASE, use an atomic release to clear the queue.

   If the queue becomes empty after the remove, return TRUE.  */

static inline bool
priority_queue_remove (enum priority_queue_type type,
		       struct priority_queue *head,
		       struct gomp_task *task,
		       enum memmodel model)
{
#if _LIBGOMP_CHECKING_
  if (!priority_queue_task_in_queue_p (type, head, task))
    gomp_fatal ("Attempt to remove missing task %p", task);
#endif
  if (priority_queue_multi_p (head))
    {
      priority_tree_remove (type, head, task_to_priority_node (type, task));
      if (head->t.root == NULL)
	{
	  if (model == MEMMODEL_RELEASE)
	    /* Errr, we store NULL twice, the alternative would be to
	       use an atomic release directly in the splay tree
	       routines.  Worth it?  */
	    __atomic_store_n (&head->t.root, NULL, MEMMODEL_RELEASE);
	  return true;
	}
      return false;
    }
  else
    return priority_list_remove (&head->l,
				 task_to_priority_node (type, task), model);
}

#endif /* _PRIORITY_QUEUE_H_ */