libgomp/priority_queue.h

   1 /* Copyright (C) 2015-2021 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
  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 typedef bool (*priority_queue_predicate) (struct gomp_task *);
 117
 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);
 127 extern struct gomp_task *priority_queue_find (enum priority_queue_type,
 128                                               struct priority_queue *,
 129                                               priority_queue_predicate);
 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_ */