priority_queue.h

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