libgomp/priority_queue.c

   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 /* Priority queue implementation of GOMP tasks.  */
  27
  28 #include "libgomp.h"
  29
  30 #if _LIBGOMP_CHECKING_
  31 #include <stdio.h>
  32
  33 /* Sanity check to verify whether a TASK is in LIST.  Return TRUE if
  34    found, FALSE otherwise.
  35
  36    TYPE is the type of priority queue this task resides in.  */
  37
  38 static inline bool
  39 priority_queue_task_in_list_p (enum priority_queue_type type,
  40                                struct priority_list *list,
  41                                struct gomp_task *task)
  42 {
  43   struct priority_node *p = list->tasks;
  44   do
  45     {
  46       if (priority_node_to_task (type, p) == task)
  47         return true;
  48       p = p->next;
  49     }
  50   while (p != list->tasks);
  51   return false;
  52 }
  53
  54 /* Tree version of priority_queue_task_in_list_p.  */
  55
  56 static inline bool
  57 priority_queue_task_in_tree_p (enum priority_queue_type type,
  58                                struct priority_queue *head,
  59                                struct gomp_task *task)
  60 {
  61   struct priority_list *list
  62     = priority_queue_lookup_priority (head, task->priority);
  63   if (!list)
  64     return false;
  65   return priority_queue_task_in_list_p (type, list, task);
  66 }
  67
  68 /* Generic version of priority_queue_task_in_list_p that works for
  69    trees or lists.  */
  70
  71 bool
  72 priority_queue_task_in_queue_p (enum priority_queue_type type,
  73                                 struct priority_queue *head,
  74                                 struct gomp_task *task)
  75 {
  76   if (priority_queue_empty_p (head, MEMMODEL_RELAXED))
  77     return false;
  78   if (priority_queue_multi_p (head))
  79     return priority_queue_task_in_tree_p (type, head, task);
  80   else
  81     return priority_queue_task_in_list_p (type, &head->l, task);
  82 }
  83
  84 /* Sanity check LIST to make sure the tasks therein are in the right
  85    order.  LIST is a priority list of type TYPE.
  86
  87    The expected order is that GOMP_TASK_WAITING tasks come before
  88    GOMP_TASK_TIED/GOMP_TASK_ASYNC_RUNNING ones.
  89
  90    If CHECK_DEPS is TRUE, we also check that parent_depends_on WAITING
  91    tasks come before !parent_depends_on WAITING tasks.  This is only
  92    applicable to the children queue, and the caller is expected to
  93    ensure that we are verifying the children queue.  */
  94
  95 static void
  96 priority_list_verify (enum priority_queue_type type,
  97                       struct priority_list *list, bool check_deps)
  98 {
  99   bool seen_tied = false;
 100   bool seen_plain_waiting = false;
 101   struct priority_node *p = list->tasks;
 102   while (1)
 103     {
 104       struct gomp_task *t = priority_node_to_task (type, p);
 105       if (seen_tied && t->kind == GOMP_TASK_WAITING)
 106         gomp_fatal ("priority_queue_verify: WAITING task after TIED");
 107       if (t->kind >= GOMP_TASK_TIED)
 108         seen_tied = true;
 109       else if (check_deps && t->kind == GOMP_TASK_WAITING)
 110         {
 111           if (t->parent_depends_on)
 112             {
 113               if (seen_plain_waiting)
 114                 gomp_fatal ("priority_queue_verify: "
 115                             "parent_depends_on after !parent_depends_on");
 116             }
 117           else
 118             seen_plain_waiting = true;
 119         }
 120       p = p->next;
 121       if (p == list->tasks)
 122         break;
 123     }
 124 }
 125
 126 /* Callback type for priority_tree_verify_callback.  */
 127 struct cbtype
 128 {
 129   enum priority_queue_type type;
 130   bool check_deps;
 131 };
 132
 133 /* Verify every task in NODE.
 134
 135    Callback for splay_tree_foreach.  */
 136
 137 static void
 138 priority_tree_verify_callback (prio_splay_tree_key key, void *data)
 139 {
 140   struct cbtype *cb = (struct cbtype *) data;
 141   priority_list_verify (cb->type, &key->l, cb->check_deps);
 142 }
 143
 144 /* Generic version of priority_list_verify.
 145
 146    Sanity check HEAD to make sure the tasks therein are in the right
 147    order.  The priority_queue holds tasks of type TYPE.
 148
 149    If CHECK_DEPS is TRUE, we also check that parent_depends_on WAITING
 150    tasks come before !parent_depends_on WAITING tasks.  This is only
 151    applicable to the children queue, and the caller is expected to
 152    ensure that we are verifying the children queue.  */
 153
 154 void
 155 priority_queue_verify (enum priority_queue_type type,
 156                        struct priority_queue *head, bool check_deps)
 157 {
 158   if (priority_queue_empty_p (head, MEMMODEL_RELAXED))
 159     return;
 160   if (priority_queue_multi_p (head))
 161     {
 162       struct cbtype cb = { type, check_deps };
 163       prio_splay_tree_foreach (&head->t,
 164                                priority_tree_verify_callback, &cb);
 165     }
 166   else
 167     priority_list_verify (type, &head->l, check_deps);
 168 }
 169 #endif /* _LIBGOMP_CHECKING_ */
 170
 171 /* Tree version of priority_queue_find.  */
 172
 173 static struct gomp_task *
 174 priority_tree_find (enum priority_queue_type type,
 175                     prio_splay_tree_node node,
 176                     priority_queue_predicate pred)
 177 {
 178  again:
 179   if (!node)
 180     return NULL;
 181   struct gomp_task *task = priority_tree_find (type, node->right, pred);
 182   if (task)
 183     return task;
 184   task = priority_node_to_task (type, node->key.l.tasks);
 185   if (pred (task))
 186     return task;
 187   node = node->left;
 188   goto again;
 189 }
 190
 191 /* List version of priority_queue_find.  */
 192
 193 static struct gomp_task *
 194 priority_list_find (enum priority_queue_type type,
 195                      struct priority_list *list,
 196                      priority_queue_predicate pred)
 197 {
 198   struct priority_node *node = list->tasks;
 199   if (!node)
 200     return NULL;
 201
 202   do
 203     {
 204       struct gomp_task *task = priority_node_to_task (type, node);
 205       if (pred (task))
 206         return task;
 207       node = node->next;
 208     }
 209   while (node != list->tasks);
 210
 211   return NULL;
 212 }
 213
 214 /* Return the highest priority task in the priority queue HEAD that
 215    satisfies the predicate PRED.  HEAD contains tasks of type TYPE.  */
 216
 217 struct gomp_task *
 218 priority_queue_find (enum priority_queue_type type,
 219                      struct priority_queue *head,
 220                      priority_queue_predicate pred)
 221 {
 222   if (priority_queue_multi_p (head))
 223     return priority_tree_find (type, head->t.root, pred);
 224   else
 225     return priority_list_find (type, &head->l, pred);
 226 }
 227
 228 /* Remove NODE from priority queue HEAD, wherever it may be inside the
 229    tree.  HEAD contains tasks of type TYPE.  */
 230
 231 void
 232 priority_tree_remove (enum priority_queue_type type,
 233                       struct priority_queue *head,
 234                       struct priority_node *node)
 235 {
 236   /* ?? The only reason this function is not inlined is because we
 237      need to find the priority within gomp_task (which has not been
 238      completely defined in the header file).  If the lack of inlining
 239      is a concern, we could pass the priority number as a
 240      parameter, or we could move this to libgomp.h.  */
 241   int priority = priority_node_to_task (type, node)->priority;
 242
 243   /* ?? We could avoid this lookup by keeping a pointer to the key in
 244      the priority_node.  */
 245   struct priority_list *list
 246     = priority_queue_lookup_priority (head, priority);
 247 #if _LIBGOMP_CHECKING_
 248   if (!list)
 249     gomp_fatal ("Unable to find priority %d", priority);
 250 #endif
 251   /* If NODE was the last in its priority, clean up the priority.  */
 252   if (priority_list_remove (list, node, MEMMODEL_RELAXED))
 253     {
 254       prio_splay_tree_remove (&head->t, (prio_splay_tree_key) list);
 255       list->tasks = NULL;
 256 #if _LIBGOMP_CHECKING_
 257       memset (list, 0xaf, sizeof (*list));
 258 #endif
 259       free (list);
 260     }
 261 }
 262
 263 /* Return the highest priority WAITING task in a splay tree NODE.  If
 264    there are no WAITING tasks available, return NULL.
 265
 266    NODE is a priority list containing tasks of type TYPE.
 267
 268    The right most node in a tree contains the highest priority.
 269    Recurse down to find such a node.  If the task at that max node is
 270    not WAITING, bubble back up and look at the remaining tasks
 271    in-order.  */
 272
 273 static struct gomp_task *
 274 priority_tree_next_task_1 (enum priority_queue_type type,
 275                            prio_splay_tree_node node)
 276 {
 277  again:
 278   if (!node)
 279     return NULL;
 280   struct gomp_task *ret = priority_tree_next_task_1 (type, node->right);
 281   if (ret)
 282     return ret;
 283   ret = priority_node_to_task (type, node->key.l.tasks);
 284   if (ret->kind == GOMP_TASK_WAITING)
 285     return ret;
 286   node = node->left;
 287   goto again;
 288 }
 289
 290 /* Return the highest priority WAITING task from within Q1 and Q2,
 291    while giving preference to tasks from Q1.  Q1 is a queue containing
 292    items of type TYPE1.  Q2 is a queue containing items of type TYPE2.
 293
 294    Since we are mostly interested in Q1, if there are no WAITING tasks
 295    in Q1, we don't bother checking Q2, and just return NULL.
 296
 297    As a special case, Q2 can be NULL, in which case, we just choose
 298    the highest priority WAITING task in Q1.  This is an optimization
 299    to speed up looking through only one queue.
 300
 301    If the returned task is chosen from Q1, *Q1_CHOSEN_P is set to
 302    TRUE, otherwise it is set to FALSE.  */
 303
 304 struct gomp_task *
 305 priority_tree_next_task (enum priority_queue_type type1,
 306                          struct priority_queue *q1,
 307                          enum priority_queue_type type2,
 308                          struct priority_queue *q2,
 309                          bool *q1_chosen_p)
 310 {
 311   struct gomp_task *t1 = priority_tree_next_task_1 (type1, q1->t.root);
 312   if (!t1
 313       /* Special optimization when only searching through one queue.  */
 314       || !q2)
 315     {
 316       *q1_chosen_p = true;
 317       return t1;
 318     }
 319   struct gomp_task *t2 = priority_tree_next_task_1 (type2, q2->t.root);
 320   if (!t2 || t1->priority > t2->priority)
 321     {
 322       *q1_chosen_p = true;
 323       return t1;
 324     }
 325   if (t2->priority > t1->priority)
 326     {
 327       *q1_chosen_p = false;
 328       return t2;
 329     }
 330   /* If we get here, the priorities are the same, so we must look at
 331      parent_depends_on to make our decision.  */
 332 #if _LIBGOMP_CHECKING_
 333   if (t1 != t2)
 334     gomp_fatal ("priority_tree_next_task: t1 != t2");
 335 #endif
 336   if (t2->parent_depends_on && !t1->parent_depends_on)
 337     {
 338       *q1_chosen_p = false;
 339       return t2;
 340     }
 341   *q1_chosen_p = true;
 342   return t1;
 343 }
 344
 345 /* Priority splay trees comparison function.  */
 346 static inline int
 347 prio_splay_compare (prio_splay_tree_key x, prio_splay_tree_key y)
 348 {
 349   if (x->l.priority == y->l.priority)
 350     return 0;
 351   return x->l.priority < y->l.priority ? -1 : 1;
 352 }
 353
 354 /* Define another splay tree instantiation, for priority_list's.  */
 355 #define splay_tree_prefix prio
 356 #define splay_tree_c
 357 #include "splay-tree.h"