| /* Copyright (C) 2015-2018 Free Software Foundation, Inc. |
| Contributed by Aldy Hernandez <aldyh@redhat.com>. |
| |
| This file is part of the GNU Offloading and Multi Processing Library |
| (libgomp). |
| |
| Libgomp is free software; you can redistribute it and/or modify it |
| under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 3, or (at your option) |
| any later version. |
| |
| Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY |
| WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS |
| FOR A PARTICULAR PURPOSE. See the GNU General Public License for |
| more details. |
| |
| Under Section 7 of GPL version 3, you are granted additional |
| permissions described in the GCC Runtime Library Exception, version |
| 3.1, as published by the Free Software Foundation. |
| |
| You should have received a copy of the GNU General Public License and |
| a copy of the GCC Runtime Library Exception along with this program; |
| see the files COPYING3 and COPYING.RUNTIME respectively. If not, see |
| <http://www.gnu.org/licenses/>. */ |
| |
| /* Header file for a priority queue of GOMP tasks. */ |
| |
| /* ?? Perhaps all the priority_tree_* functions are complex and rare |
| enough to go out-of-line and be moved to priority_queue.c. ?? */ |
| |
| #ifndef _PRIORITY_QUEUE_H_ |
| #define _PRIORITY_QUEUE_H_ |
| |
| /* One task. */ |
| |
| struct priority_node |
| { |
| /* Next and previous chains in a circular doubly linked list for |
| tasks within this task's priority. */ |
| struct priority_node *next, *prev; |
| }; |
| |
| /* All tasks within the same priority. */ |
| |
| struct priority_list |
| { |
| /* Priority of the tasks in this set. */ |
| int priority; |
| |
| /* Tasks. */ |
| struct priority_node *tasks; |
| |
| /* This points to the last of the higher priority WAITING tasks. |
| Remember that for the children queue, we have: |
| |
| parent_depends_on WAITING tasks. |
| !parent_depends_on WAITING tasks. |
| TIED tasks. |
| |
| This is a pointer to the last of the parent_depends_on WAITING |
| tasks which are essentially, higher priority items within their |
| priority. */ |
| struct priority_node *last_parent_depends_on; |
| }; |
| |
| /* Another splay tree instantiation, for priority_list's. */ |
| typedef struct prio_splay_tree_node_s *prio_splay_tree_node; |
| typedef struct prio_splay_tree_s *prio_splay_tree; |
| typedef struct prio_splay_tree_key_s *prio_splay_tree_key; |
| struct prio_splay_tree_key_s { |
| /* This structure must only containing a priority_list, as we cast |
| prio_splay_tree_key to priority_list throughout. */ |
| struct priority_list l; |
| }; |
| #define splay_tree_prefix prio |
| #include "splay-tree.h" |
| |
| /* The entry point into a priority queue of tasks. |
| |
| There are two alternate implementations with which to store tasks: |
| as a balanced tree of sorts, or as a simple list of tasks. If |
| there are only priority-0 items (ROOT is NULL), we use the simple |
| list, otherwise (ROOT is non-NULL) we use the tree. */ |
| |
| struct priority_queue |
| { |
| /* If t.root != NULL, this is a splay tree of priority_lists to hold |
| all tasks. This is only used if multiple priorities are in play, |
| otherwise we use the priority_list `l' below to hold all |
| (priority-0) tasks. */ |
| struct prio_splay_tree_s t; |
| |
| /* If T above is NULL, only priority-0 items exist, so keep them |
| in a simple list. */ |
| struct priority_list l; |
| }; |
| |
| enum priority_insert_type { |
| /* Insert at the beginning of a priority list. */ |
| PRIORITY_INSERT_BEGIN, |
| /* Insert at the end of a priority list. */ |
| PRIORITY_INSERT_END |
| }; |
| |
| /* Used to determine in which queue a given priority node belongs in. |
| See pnode field of gomp_task. */ |
| |
| enum priority_queue_type |
| { |
| PQ_TEAM, /* Node belongs in gomp_team's task_queue. */ |
| PQ_CHILDREN, /* Node belongs in parent's children_queue. */ |
| PQ_TASKGROUP, /* Node belongs in taskgroup->taskgroup_queue. */ |
| PQ_IGNORED = 999 |
| }; |
| |
| /* Priority queue implementation prototypes. */ |
| |
| extern bool priority_queue_task_in_queue_p (enum priority_queue_type, |
| struct priority_queue *, |
| struct gomp_task *); |
| extern void priority_queue_dump (enum priority_queue_type, |
| struct priority_queue *); |
| extern void priority_queue_verify (enum priority_queue_type, |
| struct priority_queue *, bool); |
| extern void priority_tree_remove (enum priority_queue_type, |
| struct priority_queue *, |
| struct priority_node *); |
| extern struct gomp_task *priority_tree_next_task (enum priority_queue_type, |
| struct priority_queue *, |
| enum priority_queue_type, |
| struct priority_queue *, |
| bool *); |
| |
| /* Return TRUE if there is more than one priority in HEAD. This is |
| used throughout to to choose between the fast path (priority 0 only |
| items) and a world with multiple priorities. */ |
| |
| static inline bool |
| priority_queue_multi_p (struct priority_queue *head) |
| { |
| return __builtin_expect (head->t.root != NULL, 0); |
| } |
| |
| /* Initialize a priority queue. */ |
| |
| static inline void |
| priority_queue_init (struct priority_queue *head) |
| { |
| head->t.root = NULL; |
| /* To save a few microseconds, we don't initialize head->l.priority |
| to 0 here. It is implied that priority will be 0 if head->t.root |
| == NULL. |
| |
| priority_tree_insert() will fix this when we encounter multiple |
| priorities. */ |
| head->l.tasks = NULL; |
| head->l.last_parent_depends_on = NULL; |
| } |
| |
| static inline void |
| priority_queue_free (struct priority_queue *head) |
| { |
| /* There's nothing to do, as tasks were freed as they were removed |
| in priority_queue_remove. */ |
| } |
| |
| /* Forward declarations. */ |
| static inline size_t priority_queue_offset (enum priority_queue_type); |
| static inline struct gomp_task *priority_node_to_task |
| (enum priority_queue_type, |
| struct priority_node *); |
| static inline struct priority_node *task_to_priority_node |
| (enum priority_queue_type, |
| struct gomp_task *); |
| |
| /* Return TRUE if priority queue HEAD is empty. |
| |
| MODEL IS MEMMODEL_ACQUIRE if we should use an acquire atomic to |
| read from the root of the queue, otherwise MEMMODEL_RELAXED if we |
| should use a plain load. */ |
| |
| static inline _Bool |
| priority_queue_empty_p (struct priority_queue *head, enum memmodel model) |
| { |
| /* Note: The acquire barriers on the loads here synchronize with |
| the write of a NULL in gomp_task_run_post_remove_parent. It is |
| not necessary that we synchronize with other non-NULL writes at |
| this point, but we must ensure that all writes to memory by a |
| child thread task work function are seen before we exit from |
| GOMP_taskwait. */ |
| if (priority_queue_multi_p (head)) |
| { |
| if (model == MEMMODEL_ACQUIRE) |
| return __atomic_load_n (&head->t.root, MEMMODEL_ACQUIRE) == NULL; |
| return head->t.root == NULL; |
| } |
| if (model == MEMMODEL_ACQUIRE) |
| return __atomic_load_n (&head->l.tasks, MEMMODEL_ACQUIRE) == NULL; |
| return head->l.tasks == NULL; |
| } |
| |
| /* Look for a given PRIORITY in HEAD. Return it if found, otherwise |
| return NULL. This only applies to the tree variant in HEAD. There |
| is no point in searching for priorities in HEAD->L. */ |
| |
| static inline struct priority_list * |
| priority_queue_lookup_priority (struct priority_queue *head, int priority) |
| { |
| if (head->t.root == NULL) |
| return NULL; |
| struct prio_splay_tree_key_s k; |
| k.l.priority = priority; |
| return (struct priority_list *) |
| prio_splay_tree_lookup (&head->t, &k); |
| } |
| |
| /* Insert task in DATA, with PRIORITY, in the priority list in LIST. |
| LIST contains items of type TYPE. |
| |
| If POS is PRIORITY_INSERT_BEGIN, the new task is inserted at the |
| top of its respective priority. If POS is PRIORITY_INSERT_END, the |
| task is inserted at the end of its priority. |
| |
| If ADJUST_PARENT_DEPENDS_ON is TRUE, LIST is a children queue, and |
| we must keep track of higher and lower priority WAITING tasks by |
| keeping the queue's last_parent_depends_on field accurate. This |
| only applies to the children queue, and the caller must ensure LIST |
| is a children queue in this case. |
| |
| If ADJUST_PARENT_DEPENDS_ON is TRUE, TASK_IS_PARENT_DEPENDS_ON is |
| set to the task's parent_depends_on field. If |
| ADJUST_PARENT_DEPENDS_ON is FALSE, this field is irrelevant. |
| |
| Return the new priority_node. */ |
| |
| static inline void |
| priority_list_insert (enum priority_queue_type type, |
| struct priority_list *list, |
| struct gomp_task *task, |
| int priority, |
| enum priority_insert_type pos, |
| bool adjust_parent_depends_on, |
| bool task_is_parent_depends_on) |
| { |
| struct priority_node *node = task_to_priority_node (type, task); |
| if (list->tasks) |
| { |
| /* If we are keeping track of higher/lower priority items, |
| but this is a lower priority WAITING task |
| (parent_depends_on != NULL), put it after all ready to |
| run tasks. See the comment in |
| priority_queue_upgrade_task for a visual on how tasks |
| should be organized. */ |
| if (adjust_parent_depends_on |
| && pos == PRIORITY_INSERT_BEGIN |
| && list->last_parent_depends_on |
| && !task_is_parent_depends_on) |
| { |
| struct priority_node *last_parent_depends_on |
| = list->last_parent_depends_on; |
| node->next = last_parent_depends_on->next; |
| node->prev = last_parent_depends_on; |
| } |
| /* Otherwise, put it at the top/bottom of the queue. */ |
| else |
| { |
| node->next = list->tasks; |
| node->prev = list->tasks->prev; |
| if (pos == PRIORITY_INSERT_BEGIN) |
| list->tasks = node; |
| } |
| node->next->prev = node; |
| node->prev->next = node; |
| } |
| else |
| { |
| node->next = node; |
| node->prev = node; |
| list->tasks = node; |
| } |
| if (adjust_parent_depends_on |
| && list->last_parent_depends_on == NULL |
| && task_is_parent_depends_on) |
| list->last_parent_depends_on = node; |
| } |
| |
| /* Tree version of priority_list_insert. */ |
| |
| static inline void |
| priority_tree_insert (enum priority_queue_type type, |
| struct priority_queue *head, |
| struct gomp_task *task, |
| int priority, |
| enum priority_insert_type pos, |
| bool adjust_parent_depends_on, |
| bool task_is_parent_depends_on) |
| { |
| if (__builtin_expect (head->t.root == NULL, 0)) |
| { |
| /* The first time around, transfer any priority 0 items to the |
| tree. */ |
| if (head->l.tasks != NULL) |
| { |
| prio_splay_tree_node k = gomp_malloc (sizeof (*k)); |
| k->left = NULL; |
| k->right = NULL; |
| k->key.l.priority = 0; |
| k->key.l.tasks = head->l.tasks; |
| k->key.l.last_parent_depends_on = head->l.last_parent_depends_on; |
| prio_splay_tree_insert (&head->t, k); |
| head->l.tasks = NULL; |
| } |
| } |
| struct priority_list *list |
| = priority_queue_lookup_priority (head, priority); |
| if (!list) |
| { |
| prio_splay_tree_node k = gomp_malloc (sizeof (*k)); |
| k->left = NULL; |
| k->right = NULL; |
| k->key.l.priority = priority; |
| k->key.l.tasks = NULL; |
| k->key.l.last_parent_depends_on = NULL; |
| prio_splay_tree_insert (&head->t, k); |
| list = &k->key.l; |
| } |
| priority_list_insert (type, list, task, priority, pos, |
| adjust_parent_depends_on, |
| task_is_parent_depends_on); |
| } |
| |
| /* Generic version of priority_*_insert. */ |
| |
| static inline void |
| priority_queue_insert (enum priority_queue_type type, |
| struct priority_queue *head, |
| struct gomp_task *task, |
| int priority, |
| enum priority_insert_type pos, |
| bool adjust_parent_depends_on, |
| bool task_is_parent_depends_on) |
| { |
| #if _LIBGOMP_CHECKING_ |
| if (priority_queue_task_in_queue_p (type, head, task)) |
| gomp_fatal ("Attempt to insert existing task %p", task); |
| #endif |
| if (priority_queue_multi_p (head) || __builtin_expect (priority > 0, 0)) |
| priority_tree_insert (type, head, task, priority, pos, |
| adjust_parent_depends_on, |
| task_is_parent_depends_on); |
| else |
| priority_list_insert (type, &head->l, task, priority, pos, |
| adjust_parent_depends_on, |
| task_is_parent_depends_on); |
| } |
| |
| /* If multiple priorities are in play, return the highest priority |
| task from within Q1 and Q2, while giving preference to tasks from |
| Q1. If the returned task is chosen from Q1, *Q1_CHOSEN_P is set to |
| TRUE, otherwise it is set to FALSE. |
| |
| If multiple priorities are not in play (only 0 priorities are |
| available), the next task is chosen exclusively from Q1. |
| |
| As a special case, Q2 can be NULL, in which case, we just choose |
| the highest priority WAITING task in Q1. This is an optimization |
| to speed up looking through only one queue. |
| |
| We assume Q1 has at least one item. */ |
| |
| static inline struct gomp_task * |
| priority_queue_next_task (enum priority_queue_type t1, |
| struct priority_queue *q1, |
| enum priority_queue_type t2, |
| struct priority_queue *q2, |
| bool *q1_chosen_p) |
| { |
| #if _LIBGOMP_CHECKING_ |
| if (priority_queue_empty_p (q1, MEMMODEL_RELAXED)) |
| gomp_fatal ("priority_queue_next_task: Q1 is empty"); |
| #endif |
| if (priority_queue_multi_p (q1)) |
| { |
| struct gomp_task *t |
| = priority_tree_next_task (t1, q1, t2, q2, q1_chosen_p); |
| /* If T is NULL, there are no WAITING tasks in Q1. In which |
| case, return any old (non-waiting) task which will cause the |
| caller to do the right thing when checking T->KIND == |
| GOMP_TASK_WAITING. */ |
| if (!t) |
| { |
| #if _LIBGOMP_CHECKING_ |
| if (*q1_chosen_p == false) |
| gomp_fatal ("priority_queue_next_task inconsistency"); |
| #endif |
| return priority_node_to_task (t1, q1->t.root->key.l.tasks); |
| } |
| return t; |
| } |
| else |
| { |
| *q1_chosen_p = true; |
| return priority_node_to_task (t1, q1->l.tasks); |
| } |
| } |
| |
| /* Remove NODE from LIST. |
| |
| If we are removing the one and only item in the list, and MODEL is |
| MEMMODEL_RELEASE, use an atomic release to clear the list. |
| |
| If the list becomes empty after the remove, return TRUE. */ |
| |
| static inline bool |
| priority_list_remove (struct priority_list *list, |
| struct priority_node *node, |
| enum memmodel model) |
| { |
| bool empty = false; |
| node->prev->next = node->next; |
| node->next->prev = node->prev; |
| if (list->tasks == node) |
| { |
| if (node->next != node) |
| list->tasks = node->next; |
| else |
| { |
| /* We access task->children in GOMP_taskwait outside of |
| the task lock mutex region, so need a release barrier |
| here to ensure memory written by child_task->fn above |
| is flushed before the NULL is written. */ |
| if (model == MEMMODEL_RELEASE) |
| __atomic_store_n (&list->tasks, NULL, MEMMODEL_RELEASE); |
| else |
| list->tasks = NULL; |
| empty = true; |
| goto remove_out; |
| } |
| } |
| remove_out: |
| #if _LIBGOMP_CHECKING_ |
| memset (node, 0xaf, sizeof (*node)); |
| #endif |
| return empty; |
| } |
| |
| /* This is the generic version of priority_list_remove. |
| |
| Remove NODE from priority queue HEAD. HEAD contains tasks of type TYPE. |
| |
| If we are removing the one and only item in the priority queue and |
| MODEL is MEMMODEL_RELEASE, use an atomic release to clear the queue. |
| |
| If the queue becomes empty after the remove, return TRUE. */ |
| |
| static inline bool |
| priority_queue_remove (enum priority_queue_type type, |
| struct priority_queue *head, |
| struct gomp_task *task, |
| enum memmodel model) |
| { |
| #if _LIBGOMP_CHECKING_ |
| if (!priority_queue_task_in_queue_p (type, head, task)) |
| gomp_fatal ("Attempt to remove missing task %p", task); |
| #endif |
| if (priority_queue_multi_p (head)) |
| { |
| priority_tree_remove (type, head, task_to_priority_node (type, task)); |
| if (head->t.root == NULL) |
| { |
| if (model == MEMMODEL_RELEASE) |
| /* Errr, we store NULL twice, the alternative would be to |
| use an atomic release directly in the splay tree |
| routines. Worth it? */ |
| __atomic_store_n (&head->t.root, NULL, MEMMODEL_RELEASE); |
| return true; |
| } |
| return false; |
| } |
| else |
| return priority_list_remove (&head->l, |
| task_to_priority_node (type, task), model); |
| } |
| |
| #endif /* _PRIORITY_QUEUE_H_ */ |