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