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