libgomp/priority_queue.h

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