/*
   * Completely Fair Scheduling (CFS) Class (SCHED_NORMAL/SCHED_BATCH)
   *
   *  Copyright (C) 2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
   *
   *  Interactivity improvements by Mike Galbraith
   *  (C) 2007 Mike Galbraith <efault@gmx.de>
   *
   *  Various enhancements by Dmitry Adamushko.
   *  (C) 2007 Dmitry Adamushko <dmitry.adamushko@gmail.com>
   *
   *  Group scheduling enhancements by Srivatsa Vaddagiri
   *  Copyright IBM Corporation, 2007
   *  Author: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
   *
   *  Scaled math optimizations by Thomas Gleixner
   *  Copyright (C) 2007, Thomas Gleixner <tglx@linutronix.de>

   *
   *  Adaptive scheduling granularity, math enhancements by Peter Zijlstra
   *  Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com>

   */

  #include <linux/latencytop.h>

  #include <linux/sched.h>

  #include <linux/cpumask.h>

  #include <linux/slab.h>
  #include <linux/profile.h>
  #include <linux/interrupt.h>

  #include <linux/mempolicy.h>

  #include <linux/migrate.h>

  #include <linux/task_work.h>

  
  #include <trace/events/sched.h>
  
  #include "sched.h"

  /*

   * Targeted preemption latency for CPU-bound tasks:

   * (default: 6ms * (1 + ilog(ncpus)), units: nanoseconds)

   *

   * NOTE: this latency value is not the same as the concept of

   * 'timeslice length' - timeslices in CFS are of variable length
   * and have no persistent notion like in traditional, time-slice
   * based scheduling concepts.

   *

   * (to see the precise effective timeslice length of your workload,
   *  run vmstat and monitor the context-switches (cs) field)

   */

  unsigned int sysctl_sched_latency = 6000000ULL;
  unsigned int normalized_sysctl_sched_latency = 6000000ULL;

  
  /*

   * The initial- and re-scaling of tunables is configurable
   * (default SCHED_TUNABLESCALING_LOG = *(1+ilog(ncpus))
   *
   * Options are:
   * SCHED_TUNABLESCALING_NONE - unscaled, always *1
   * SCHED_TUNABLESCALING_LOG - scaled logarithmical, *1+ilog(ncpus)
   * SCHED_TUNABLESCALING_LINEAR - scaled linear, *ncpus
   */
  enum sched_tunable_scaling sysctl_sched_tunable_scaling
  	= SCHED_TUNABLESCALING_LOG;
  
  /*

   * Minimal preemption granularity for CPU-bound tasks:

   * (default: 0.75 msec * (1 + ilog(ncpus)), units: nanoseconds)

   */

  unsigned int sysctl_sched_min_granularity = 750000ULL;
  unsigned int normalized_sysctl_sched_min_granularity = 750000ULL;

  
  /*

   * is kept at sysctl_sched_latency / sysctl_sched_min_granularity
   */

  static unsigned int sched_nr_latency = 8;

  
  /*

   * After fork, child runs first. If set to 0 (default) then

   * parent will (try to) run first.

   */

  unsigned int sysctl_sched_child_runs_first __read_mostly;

  
  /*

   * SCHED_OTHER wake-up granularity.

   * (default: 1 msec * (1 + ilog(ncpus)), units: nanoseconds)

   *
   * This option delays the preemption effects of decoupled workloads
   * and reduces their over-scheduling. Synchronous workloads will still
   * have immediate wakeup/sleep latencies.
   */

  unsigned int sysctl_sched_wakeup_granularity = 1000000UL;

  unsigned int normalized_sysctl_sched_wakeup_granularity = 1000000UL;

  const_debug unsigned int sysctl_sched_migration_cost = 500000UL;

  /*
   * The exponential sliding  window over which load is averaged for shares
   * distribution.
   * (default: 10msec)
   */
  unsigned int __read_mostly sysctl_sched_shares_window = 10000000UL;

  #ifdef CONFIG_CFS_BANDWIDTH
  /*
   * Amount of runtime to allocate from global (tg) to local (per-cfs_rq) pool
   * each time a cfs_rq requests quota.
   *
   * Note: in the case that the slice exceeds the runtime remaining (either due
   * to consumption or the quota being specified to be smaller than the slice)
   * we will always only issue the remaining available time.
   *
   * default: 5 msec, units: microseconds
    */
  unsigned int sysctl_sched_cfs_bandwidth_slice = 5000UL;
  #endif

  static inline void update_load_add(struct load_weight *lw, unsigned long inc)
  {
  	lw->weight += inc;
  	lw->inv_weight = 0;
  }
  
  static inline void update_load_sub(struct load_weight *lw, unsigned long dec)
  {
  	lw->weight -= dec;
  	lw->inv_weight = 0;
  }
  
  static inline void update_load_set(struct load_weight *lw, unsigned long w)
  {
  	lw->weight = w;
  	lw->inv_weight = 0;
  }

  /*
   * Increase the granularity value when there are more CPUs,
   * because with more CPUs the 'effective latency' as visible
   * to users decreases. But the relationship is not linear,
   * so pick a second-best guess by going with the log2 of the
   * number of CPUs.
   *
   * This idea comes from the SD scheduler of Con Kolivas:
   */
  static int get_update_sysctl_factor(void)
  {
  	unsigned int cpus = min_t(int, num_online_cpus(), 8);
  	unsigned int factor;
  
  	switch (sysctl_sched_tunable_scaling) {
  	case SCHED_TUNABLESCALING_NONE:
  		factor = 1;
  		break;
  	case SCHED_TUNABLESCALING_LINEAR:
  		factor = cpus;
  		break;
  	case SCHED_TUNABLESCALING_LOG:
  	default:
  		factor = 1 + ilog2(cpus);
  		break;
  	}
  
  	return factor;
  }
  
  static void update_sysctl(void)
  {
  	unsigned int factor = get_update_sysctl_factor();
  
  #define SET_SYSCTL(name) \
  	(sysctl_##name = (factor) * normalized_sysctl_##name)
  	SET_SYSCTL(sched_min_granularity);
  	SET_SYSCTL(sched_latency);
  	SET_SYSCTL(sched_wakeup_granularity);
  #undef SET_SYSCTL
  }
  
  void sched_init_granularity(void)
  {
  	update_sysctl();
  }

  #define WMULT_CONST	(~0U)

  #define WMULT_SHIFT	32

  static void __update_inv_weight(struct load_weight *lw)
  {
  	unsigned long w;
  
  	if (likely(lw->inv_weight))
  		return;
  
  	w = scale_load_down(lw->weight);
  
  	if (BITS_PER_LONG > 32 && unlikely(w >= WMULT_CONST))
  		lw->inv_weight = 1;
  	else if (unlikely(!w))
  		lw->inv_weight = WMULT_CONST;
  	else
  		lw->inv_weight = WMULT_CONST / w;
  }

  
  /*

   * delta_exec * weight / lw.weight
   *   OR
   * (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT
   *
   * Either weight := NICE_0_LOAD and lw \e prio_to_wmult[], in which case
   * we're guaranteed shift stays positive because inv_weight is guaranteed to
   * fit 32 bits, and NICE_0_LOAD gives another 10 bits; therefore shift >= 22.
   *
   * Or, weight =< lw.weight (because lw.weight is the runqueue weight), thus
   * weight/lw.weight <= 1, and therefore our shift will also be positive.

   */

  static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)

  {

  	u64 fact = scale_load_down(weight);
  	int shift = WMULT_SHIFT;

  	__update_inv_weight(lw);

  	if (unlikely(fact >> 32)) {
  		while (fact >> 32) {
  			fact >>= 1;
  			shift--;
  		}

  	}

  	/* hint to use a 32x32->64 mul */
  	fact = (u64)(u32)fact * lw->inv_weight;

  	while (fact >> 32) {
  		fact >>= 1;
  		shift--;
  	}

  	return mul_u64_u32_shr(delta_exec, fact, shift);

  }
  
  
  const struct sched_class fair_sched_class;

  /**************************************************************
   * CFS operations on generic schedulable entities:
   */

  #ifdef CONFIG_FAIR_GROUP_SCHED

  /* cpu runqueue to which this cfs_rq is attached */

  static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
  {

  	return cfs_rq->rq;

  }

  /* An entity is a task if it doesn't "own" a runqueue */
  #define entity_is_task(se)	(!se->my_q)

  static inline struct task_struct *task_of(struct sched_entity *se)
  {
  #ifdef CONFIG_SCHED_DEBUG
  	WARN_ON_ONCE(!entity_is_task(se));
  #endif
  	return container_of(se, struct task_struct, se);
  }

  /* Walk up scheduling entities hierarchy */
  #define for_each_sched_entity(se) \
  		for (; se; se = se->parent)
  
  static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
  {
  	return p->se.cfs_rq;
  }
  
  /* runqueue on which this entity is (to be) queued */
  static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
  {
  	return se->cfs_rq;
  }
  
  /* runqueue "owned" by this group */
  static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
  {
  	return grp->my_q;
  }

  static void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq,
  				       int force_update);

  static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
  {
  	if (!cfs_rq->on_list) {

  		/*
  		 * Ensure we either appear before our parent (if already
  		 * enqueued) or force our parent to appear after us when it is
  		 * enqueued.  The fact that we always enqueue bottom-up
  		 * reduces this to two cases.
  		 */
  		if (cfs_rq->tg->parent &&
  		    cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->on_list) {
  			list_add_rcu(&cfs_rq->leaf_cfs_rq_list,
  				&rq_of(cfs_rq)->leaf_cfs_rq_list);
  		} else {
  			list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,

  				&rq_of(cfs_rq)->leaf_cfs_rq_list);

  		}

  
  		cfs_rq->on_list = 1;

  		/* We should have no load, but we need to update last_decay. */

  		update_cfs_rq_blocked_load(cfs_rq, 0);

  	}
  }
  
  static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
  {
  	if (cfs_rq->on_list) {
  		list_del_rcu(&cfs_rq->leaf_cfs_rq_list);
  		cfs_rq->on_list = 0;
  	}
  }

  /* Iterate thr' all leaf cfs_rq's on a runqueue */
  #define for_each_leaf_cfs_rq(rq, cfs_rq) \
  	list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
  
  /* Do the two (enqueued) entities belong to the same group ? */

  static inline struct cfs_rq *

  is_same_group(struct sched_entity *se, struct sched_entity *pse)
  {
  	if (se->cfs_rq == pse->cfs_rq)

  		return se->cfs_rq;

  	return NULL;

  }
  
  static inline struct sched_entity *parent_entity(struct sched_entity *se)
  {
  	return se->parent;
  }

  static void
  find_matching_se(struct sched_entity **se, struct sched_entity **pse)
  {
  	int se_depth, pse_depth;
  
  	/*
  	 * preemption test can be made between sibling entities who are in the
  	 * same cfs_rq i.e who have a common parent. Walk up the hierarchy of
  	 * both tasks until we find their ancestors who are siblings of common
  	 * parent.
  	 */
  
  	/* First walk up until both entities are at same depth */

  	se_depth = (*se)->depth;
  	pse_depth = (*pse)->depth;

  
  	while (se_depth > pse_depth) {
  		se_depth--;
  		*se = parent_entity(*se);
  	}
  
  	while (pse_depth > se_depth) {
  		pse_depth--;
  		*pse = parent_entity(*pse);
  	}
  
  	while (!is_same_group(*se, *pse)) {
  		*se = parent_entity(*se);
  		*pse = parent_entity(*pse);
  	}
  }

  #else	/* !CONFIG_FAIR_GROUP_SCHED */
  
  static inline struct task_struct *task_of(struct sched_entity *se)
  {
  	return container_of(se, struct task_struct, se);
  }

  static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
  {
  	return container_of(cfs_rq, struct rq, cfs);

  }
  
  #define entity_is_task(se)	1

  #define for_each_sched_entity(se) \
  		for (; se; se = NULL)

  static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)

  {

  	return &task_rq(p)->cfs;

  }

  static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
  {
  	struct task_struct *p = task_of(se);
  	struct rq *rq = task_rq(p);
  
  	return &rq->cfs;
  }
  
  /* runqueue "owned" by this group */
  static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
  {
  	return NULL;
  }

  static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
  {
  }
  
  static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
  {
  }

  #define for_each_leaf_cfs_rq(rq, cfs_rq) \
  		for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)

  static inline struct sched_entity *parent_entity(struct sched_entity *se)
  {
  	return NULL;
  }

  static inline void
  find_matching_se(struct sched_entity **se, struct sched_entity **pse)
  {
  }

  #endif	/* CONFIG_FAIR_GROUP_SCHED */

  static __always_inline

  void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec);

  
  /**************************************************************
   * Scheduling class tree data structure manipulation methods:
   */

  static inline u64 max_vruntime(u64 max_vruntime, u64 vruntime)

  {

  	s64 delta = (s64)(vruntime - max_vruntime);

  	if (delta > 0)

  		max_vruntime = vruntime;

  	return max_vruntime;

  }

  static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)

  {
  	s64 delta = (s64)(vruntime - min_vruntime);
  	if (delta < 0)
  		min_vruntime = vruntime;
  
  	return min_vruntime;
  }

  static inline int entity_before(struct sched_entity *a,
  				struct sched_entity *b)
  {
  	return (s64)(a->vruntime - b->vruntime) < 0;
  }

  static void update_min_vruntime(struct cfs_rq *cfs_rq)
  {
  	u64 vruntime = cfs_rq->min_vruntime;
  
  	if (cfs_rq->curr)
  		vruntime = cfs_rq->curr->vruntime;
  
  	if (cfs_rq->rb_leftmost) {
  		struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
  						   struct sched_entity,
  						   run_node);

  		if (!cfs_rq->curr)

  			vruntime = se->vruntime;
  		else
  			vruntime = min_vruntime(vruntime, se->vruntime);
  	}

  	/* ensure we never gain time by being placed backwards. */

  	cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);

  #ifndef CONFIG_64BIT
  	smp_wmb();
  	cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
  #endif

  }

  /*
   * Enqueue an entity into the rb-tree:
   */

  static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)

  {
  	struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
  	struct rb_node *parent = NULL;
  	struct sched_entity *entry;

  	int leftmost = 1;
  
  	/*
  	 * Find the right place in the rbtree:
  	 */
  	while (*link) {
  		parent = *link;
  		entry = rb_entry(parent, struct sched_entity, run_node);
  		/*
  		 * We dont care about collisions. Nodes with
  		 * the same key stay together.
  		 */

  		if (entity_before(se, entry)) {

  			link = &parent->rb_left;
  		} else {
  			link = &parent->rb_right;
  			leftmost = 0;
  		}
  	}
  
  	/*
  	 * Maintain a cache of leftmost tree entries (it is frequently
  	 * used):
  	 */

  	if (leftmost)

  		cfs_rq->rb_leftmost = &se->run_node;

  
  	rb_link_node(&se->run_node, parent, link);
  	rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);

  }

  static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)

  {

  	if (cfs_rq->rb_leftmost == &se->run_node) {
  		struct rb_node *next_node;

  
  		next_node = rb_next(&se->run_node);
  		cfs_rq->rb_leftmost = next_node;

  	}

  	rb_erase(&se->run_node, &cfs_rq->tasks_timeline);

  }

  struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)

  {

  	struct rb_node *left = cfs_rq->rb_leftmost;
  
  	if (!left)
  		return NULL;
  
  	return rb_entry(left, struct sched_entity, run_node);

  }

  static struct sched_entity *__pick_next_entity(struct sched_entity *se)
  {
  	struct rb_node *next = rb_next(&se->run_node);
  
  	if (!next)
  		return NULL;
  
  	return rb_entry(next, struct sched_entity, run_node);
  }
  
  #ifdef CONFIG_SCHED_DEBUG

  struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)

  {

  	struct rb_node *last = rb_last(&cfs_rq->tasks_timeline);

  	if (!last)
  		return NULL;

  
  	return rb_entry(last, struct sched_entity, run_node);

  }

  /**************************************************************
   * Scheduling class statistics methods:
   */

  int sched_proc_update_handler(struct ctl_table *table, int write,

  		void __user *buffer, size_t *lenp,

  		loff_t *ppos)
  {

  	int ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);

  	int factor = get_update_sysctl_factor();

  
  	if (ret || !write)
  		return ret;
  
  	sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency,
  					sysctl_sched_min_granularity);

  #define WRT_SYSCTL(name) \
  	(normalized_sysctl_##name = sysctl_##name / (factor))
  	WRT_SYSCTL(sched_min_granularity);
  	WRT_SYSCTL(sched_latency);
  	WRT_SYSCTL(sched_wakeup_granularity);

  #undef WRT_SYSCTL

  	return 0;
  }
  #endif

  
  /*

   * delta /= w

   */

  static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)

  {

  	if (unlikely(se->load.weight != NICE_0_LOAD))

  		delta = __calc_delta(delta, NICE_0_LOAD, &se->load);

  
  	return delta;
  }
  
  /*

   * The idea is to set a period in which each task runs once.
   *

   * When there are too many tasks (sched_nr_latency) we have to stretch

   * this period because otherwise the slices get too small.
   *
   * p = (nr <= nl) ? l : l*nr/nl
   */

  static u64 __sched_period(unsigned long nr_running)
  {
  	u64 period = sysctl_sched_latency;

  	unsigned long nr_latency = sched_nr_latency;

  
  	if (unlikely(nr_running > nr_latency)) {

  		period = sysctl_sched_min_granularity;

  		period *= nr_running;

  	}
  
  	return period;
  }

  /*
   * We calculate the wall-time slice from the period by taking a part
   * proportional to the weight.
   *

   * s = p*P[w/rw]

   */

  static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)

  {

  	u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);

  	for_each_sched_entity(se) {

  		struct load_weight *load;

  		struct load_weight lw;

  
  		cfs_rq = cfs_rq_of(se);
  		load = &cfs_rq->load;

  		if (unlikely(!se->on_rq)) {

  			lw = cfs_rq->load;

  
  			update_load_add(&lw, se->load.weight);
  			load = &lw;
  		}

  		slice = __calc_delta(slice, se->load.weight, load);

  	}
  	return slice;

  }

  /*

   * We calculate the vruntime slice of a to-be-inserted task.

   *

   * vs = s/w

   */

  static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)

  {

  	return calc_delta_fair(sched_slice(cfs_rq, se), se);

  }

  #ifdef CONFIG_SMP

  static unsigned long task_h_load(struct task_struct *p);

  static inline void __update_task_entity_contrib(struct sched_entity *se);
  
  /* Give new task start runnable values to heavy its load in infant time */
  void init_task_runnable_average(struct task_struct *p)
  {
  	u32 slice;
  
  	p->se.avg.decay_count = 0;
  	slice = sched_slice(task_cfs_rq(p), &p->se) >> 10;
  	p->se.avg.runnable_avg_sum = slice;
  	p->se.avg.runnable_avg_period = slice;
  	__update_task_entity_contrib(&p->se);
  }
  #else
  void init_task_runnable_average(struct task_struct *p)
  {
  }
  #endif

  /*

   * Update the current task's runtime statistics.

   */

  static void update_curr(struct cfs_rq *cfs_rq)

  {

  	struct sched_entity *curr = cfs_rq->curr;

  	u64 now = rq_clock_task(rq_of(cfs_rq));

  	u64 delta_exec;

  
  	if (unlikely(!curr))
  		return;

  	delta_exec = now - curr->exec_start;
  	if (unlikely((s64)delta_exec <= 0))

  		return;

  	curr->exec_start = now;

  	schedstat_set(curr->statistics.exec_max,
  		      max(delta_exec, curr->statistics.exec_max));
  
  	curr->sum_exec_runtime += delta_exec;
  	schedstat_add(cfs_rq, exec_clock, delta_exec);
  
  	curr->vruntime += calc_delta_fair(delta_exec, curr);
  	update_min_vruntime(cfs_rq);

  	if (entity_is_task(curr)) {
  		struct task_struct *curtask = task_of(curr);

  		trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);

  		cpuacct_charge(curtask, delta_exec);

  		account_group_exec_runtime(curtask, delta_exec);

  	}

  
  	account_cfs_rq_runtime(cfs_rq, delta_exec);

  }
  
  static inline void

  update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se)

  {

  	schedstat_set(se->statistics.wait_start, rq_clock(rq_of(cfs_rq)));

  }

  /*
   * Task is being enqueued - update stats:
   */

  static void update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)

  {

  	/*
  	 * Are we enqueueing a waiting task? (for current tasks
  	 * a dequeue/enqueue event is a NOP)
  	 */

  	if (se != cfs_rq->curr)

  		update_stats_wait_start(cfs_rq, se);

  }

  static void

  update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se)

  {

  	schedstat_set(se->statistics.wait_max, max(se->statistics.wait_max,

  			rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start));

  	schedstat_set(se->statistics.wait_count, se->statistics.wait_count + 1);
  	schedstat_set(se->statistics.wait_sum, se->statistics.wait_sum +

  			rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start);

  #ifdef CONFIG_SCHEDSTATS
  	if (entity_is_task(se)) {
  		trace_sched_stat_wait(task_of(se),

  			rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start);

  	}
  #endif

  	schedstat_set(se->statistics.wait_start, 0);

  }
  
  static inline void

  update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)

  {

  	/*
  	 * Mark the end of the wait period if dequeueing a
  	 * waiting task:
  	 */

  	if (se != cfs_rq->curr)

  		update_stats_wait_end(cfs_rq, se);

  }
  
  /*
   * We are picking a new current task - update its stats:
   */
  static inline void

  update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)

  {
  	/*
  	 * We are starting a new run period:
  	 */

  	se->exec_start = rq_clock_task(rq_of(cfs_rq));

  }

  /**************************************************
   * Scheduling class queueing methods:
   */

  #ifdef CONFIG_NUMA_BALANCING
  /*

   * Approximate time to scan a full NUMA task in ms. The task scan period is
   * calculated based on the tasks virtual memory size and
   * numa_balancing_scan_size.

   */

  unsigned int sysctl_numa_balancing_scan_period_min = 1000;
  unsigned int sysctl_numa_balancing_scan_period_max = 60000;

  
  /* Portion of address space to scan in MB */
  unsigned int sysctl_numa_balancing_scan_size = 256;

  /* Scan @scan_size MB every @scan_period after an initial @scan_delay in ms */
  unsigned int sysctl_numa_balancing_scan_delay = 1000;

  static unsigned int task_nr_scan_windows(struct task_struct *p)
  {
  	unsigned long rss = 0;
  	unsigned long nr_scan_pages;
  
  	/*
  	 * Calculations based on RSS as non-present and empty pages are skipped
  	 * by the PTE scanner and NUMA hinting faults should be trapped based
  	 * on resident pages
  	 */
  	nr_scan_pages = sysctl_numa_balancing_scan_size << (20 - PAGE_SHIFT);
  	rss = get_mm_rss(p->mm);
  	if (!rss)
  		rss = nr_scan_pages;
  
  	rss = round_up(rss, nr_scan_pages);
  	return rss / nr_scan_pages;
  }
  
  /* For sanitys sake, never scan more PTEs than MAX_SCAN_WINDOW MB/sec. */
  #define MAX_SCAN_WINDOW 2560
  
  static unsigned int task_scan_min(struct task_struct *p)
  {
  	unsigned int scan, floor;
  	unsigned int windows = 1;
  
  	if (sysctl_numa_balancing_scan_size < MAX_SCAN_WINDOW)
  		windows = MAX_SCAN_WINDOW / sysctl_numa_balancing_scan_size;
  	floor = 1000 / windows;
  
  	scan = sysctl_numa_balancing_scan_period_min / task_nr_scan_windows(p);
  	return max_t(unsigned int, floor, scan);
  }
  
  static unsigned int task_scan_max(struct task_struct *p)
  {
  	unsigned int smin = task_scan_min(p);
  	unsigned int smax;
  
  	/* Watch for min being lower than max due to floor calculations */
  	smax = sysctl_numa_balancing_scan_period_max / task_nr_scan_windows(p);
  	return max(smin, smax);
  }

  static void account_numa_enqueue(struct rq *rq, struct task_struct *p)
  {
  	rq->nr_numa_running += (p->numa_preferred_nid != -1);
  	rq->nr_preferred_running += (p->numa_preferred_nid == task_node(p));
  }
  
  static void account_numa_dequeue(struct rq *rq, struct task_struct *p)
  {
  	rq->nr_numa_running -= (p->numa_preferred_nid != -1);
  	rq->nr_preferred_running -= (p->numa_preferred_nid == task_node(p));
  }

  struct numa_group {
  	atomic_t refcount;
  
  	spinlock_t lock; /* nr_tasks, tasks */
  	int nr_tasks;

  	pid_t gid;

  	struct list_head task_list;
  
  	struct rcu_head rcu;

  	nodemask_t active_nodes;

  	unsigned long total_faults;

  	/*
  	 * Faults_cpu is used to decide whether memory should move
  	 * towards the CPU. As a consequence, these stats are weighted
  	 * more by CPU use than by memory faults.
  	 */

  	unsigned long *faults_cpu;

  	unsigned long faults[0];

  };

  /* Shared or private faults. */
  #define NR_NUMA_HINT_FAULT_TYPES 2
  
  /* Memory and CPU locality */
  #define NR_NUMA_HINT_FAULT_STATS (NR_NUMA_HINT_FAULT_TYPES * 2)
  
  /* Averaged statistics, and temporary buffers. */
  #define NR_NUMA_HINT_FAULT_BUCKETS (NR_NUMA_HINT_FAULT_STATS * 2)

  pid_t task_numa_group_id(struct task_struct *p)
  {
  	return p->numa_group ? p->numa_group->gid : 0;
  }

  static inline int task_faults_idx(int nid, int priv)
  {

  	return NR_NUMA_HINT_FAULT_TYPES * nid + priv;

  }
  
  static inline unsigned long task_faults(struct task_struct *p, int nid)
  {

  	if (!p->numa_faults_memory)

  		return 0;

  	return p->numa_faults_memory[task_faults_idx(nid, 0)] +
  		p->numa_faults_memory[task_faults_idx(nid, 1)];

  }

  static inline unsigned long group_faults(struct task_struct *p, int nid)
  {
  	if (!p->numa_group)
  		return 0;

  	return p->numa_group->faults[task_faults_idx(nid, 0)] +
  		p->numa_group->faults[task_faults_idx(nid, 1)];

  }

  static inline unsigned long group_faults_cpu(struct numa_group *group, int nid)
  {
  	return group->faults_cpu[task_faults_idx(nid, 0)] +
  		group->faults_cpu[task_faults_idx(nid, 1)];
  }

  /*
   * These return the fraction of accesses done by a particular task, or
   * task group, on a particular numa node.  The group weight is given a
   * larger multiplier, in order to group tasks together that are almost
   * evenly spread out between numa nodes.
   */
  static inline unsigned long task_weight(struct task_struct *p, int nid)
  {
  	unsigned long total_faults;

  	if (!p->numa_faults_memory)

  		return 0;
  
  	total_faults = p->total_numa_faults;
  
  	if (!total_faults)
  		return 0;
  
  	return 1000 * task_faults(p, nid) / total_faults;
  }
  
  static inline unsigned long group_weight(struct task_struct *p, int nid)
  {

  	if (!p->numa_group || !p->numa_group->total_faults)

  		return 0;

  	return 1000 * group_faults(p, nid) / p->numa_group->total_faults;

  }

  bool should_numa_migrate_memory(struct task_struct *p, struct page * page,
  				int src_nid, int dst_cpu)
  {
  	struct numa_group *ng = p->numa_group;
  	int dst_nid = cpu_to_node(dst_cpu);
  	int last_cpupid, this_cpupid;
  
  	this_cpupid = cpu_pid_to_cpupid(dst_cpu, current->pid);
  
  	/*
  	 * Multi-stage node selection is used in conjunction with a periodic
  	 * migration fault to build a temporal task<->page relation. By using
  	 * a two-stage filter we remove short/unlikely relations.
  	 *
  	 * Using P(p) ~ n_p / n_t as per frequentist probability, we can equate
  	 * a task's usage of a particular page (n_p) per total usage of this
  	 * page (n_t) (in a given time-span) to a probability.
  	 *
  	 * Our periodic faults will sample this probability and getting the
  	 * same result twice in a row, given these samples are fully
  	 * independent, is then given by P(n)^2, provided our sample period
  	 * is sufficiently short compared to the usage pattern.
  	 *
  	 * This quadric squishes small probabilities, making it less likely we
  	 * act on an unlikely task<->page relation.
  	 */
  	last_cpupid = page_cpupid_xchg_last(page, this_cpupid);
  	if (!cpupid_pid_unset(last_cpupid) &&
  				cpupid_to_nid(last_cpupid) != dst_nid)
  		return false;
  
  	/* Always allow migrate on private faults */
  	if (cpupid_match_pid(p, last_cpupid))
  		return true;
  
  	/* A shared fault, but p->numa_group has not been set up yet. */
  	if (!ng)
  		return true;
  
  	/*
  	 * Do not migrate if the destination is not a node that
  	 * is actively used by this numa group.
  	 */
  	if (!node_isset(dst_nid, ng->active_nodes))
  		return false;
  
  	/*
  	 * Source is a node that is not actively used by this
  	 * numa group, while the destination is. Migrate.
  	 */
  	if (!node_isset(src_nid, ng->active_nodes))
  		return true;
  
  	/*
  	 * Both source and destination are nodes in active
  	 * use by this numa group. Maximize memory bandwidth
  	 * by migrating from more heavily used groups, to less
  	 * heavily used ones, spreading the load around.
  	 * Use a 1/4 hysteresis to avoid spurious page movement.
  	 */
  	return group_faults(p, dst_nid) < (group_faults(p, src_nid) * 3 / 4);
  }

  static unsigned long weighted_cpuload(const int cpu);

  static unsigned long source_load(int cpu, int type);
  static unsigned long target_load(int cpu, int type);
  static unsigned long power_of(int cpu);
  static long effective_load(struct task_group *tg, int cpu, long wl, long wg);

  /* Cached statistics for all CPUs within a node */

  struct numa_stats {

  	unsigned long nr_running;

  	unsigned long load;

  
  	/* Total compute capacity of CPUs on a node */
  	unsigned long power;
  
  	/* Approximate capacity in terms of runnable tasks on a node */
  	unsigned long capacity;
  	int has_capacity;

  };

  /*
   * XXX borrowed from update_sg_lb_stats
   */
  static void update_numa_stats(struct numa_stats *ns, int nid)
  {

  	int cpu, cpus = 0;

  
  	memset(ns, 0, sizeof(*ns));
  	for_each_cpu(cpu, cpumask_of_node(nid)) {
  		struct rq *rq = cpu_rq(cpu);
  
  		ns->nr_running += rq->nr_running;
  		ns->load += weighted_cpuload(cpu);
  		ns->power += power_of(cpu);

  
  		cpus++;

  	}

  	/*
  	 * If we raced with hotplug and there are no CPUs left in our mask
  	 * the @ns structure is NULL'ed and task_numa_compare() will
  	 * not find this node attractive.
  	 *
  	 * We'll either bail at !has_capacity, or we'll detect a huge imbalance
  	 * and bail there.
  	 */
  	if (!cpus)
  		return;

  	ns->load = (ns->load * SCHED_POWER_SCALE) / ns->power;
  	ns->capacity = DIV_ROUND_CLOSEST(ns->power, SCHED_POWER_SCALE);
  	ns->has_capacity = (ns->nr_running < ns->capacity);
  }

  struct task_numa_env {
  	struct task_struct *p;

  	int src_cpu, src_nid;
  	int dst_cpu, dst_nid;

  	struct numa_stats src_stats, dst_stats;

  	int imbalance_pct;

  
  	struct task_struct *best_task;
  	long best_imp;

  	int best_cpu;
  };

  static void task_numa_assign(struct task_numa_env *env,
  			     struct task_struct *p, long imp)
  {
  	if (env->best_task)
  		put_task_struct(env->best_task);
  	if (p)
  		get_task_struct(p);
  
  	env->best_task = p;
  	env->best_imp = imp;
  	env->best_cpu = env->dst_cpu;
  }
  
  /*
   * This checks if the overall compute and NUMA accesses of the system would
   * be improved if the source tasks was migrated to the target dst_cpu taking
   * into account that it might be best if task running on the dst_cpu should
   * be exchanged with the source task
   */

  static void task_numa_compare(struct task_numa_env *env,
  			      long taskimp, long groupimp)

  {
  	struct rq *src_rq = cpu_rq(env->src_cpu);
  	struct rq *dst_rq = cpu_rq(env->dst_cpu);
  	struct task_struct *cur;
  	long dst_load, src_load;
  	long load;

  	long imp = (groupimp > 0) ? groupimp : taskimp;

  
  	rcu_read_lock();
  	cur = ACCESS_ONCE(dst_rq->curr);
  	if (cur->pid == 0) /* idle */
  		cur = NULL;
  
  	/*
  	 * "imp" is the fault differential for the source task between the
  	 * source and destination node. Calculate the total differential for
  	 * the source task and potential destination task. The more negative
  	 * the value is, the more rmeote accesses that would be expected to
  	 * be incurred if the tasks were swapped.
  	 */
  	if (cur) {
  		/* Skip this swap candidate if cannot move to the source cpu */
  		if (!cpumask_test_cpu(env->src_cpu, tsk_cpus_allowed(cur)))
  			goto unlock;

  		/*
  		 * If dst and source tasks are in the same NUMA group, or not

  		 * in any group then look only at task weights.

  		 */

  		if (cur->numa_group == env->p->numa_group) {

  			imp = taskimp + task_weight(cur, env->src_nid) -
  			      task_weight(cur, env->dst_nid);

  			/*
  			 * Add some hysteresis to prevent swapping the
  			 * tasks within a group over tiny differences.
  			 */
  			if (cur->numa_group)
  				imp -= imp/16;

  		} else {

  			/*
  			 * Compare the group weights. If a task is all by
  			 * itself (not part of a group), use the task weight
  			 * instead.
  			 */
  			if (env->p->numa_group)
  				imp = groupimp;
  			else
  				imp = taskimp;
  
  			if (cur->numa_group)
  				imp += group_weight(cur, env->src_nid) -
  				       group_weight(cur, env->dst_nid);
  			else
  				imp += task_weight(cur, env->src_nid) -
  				       task_weight(cur, env->dst_nid);

  		}

  	}
  
  	if (imp < env->best_imp)
  		goto unlock;
  
  	if (!cur) {
  		/* Is there capacity at our destination? */
  		if (env->src_stats.has_capacity &&
  		    !env->dst_stats.has_capacity)
  			goto unlock;
  
  		goto balance;
  	}
  
  	/* Balance doesn't matter much if we're running a task per cpu */
  	if (src_rq->nr_running == 1 && dst_rq->nr_running == 1)
  		goto assign;
  
  	/*
  	 * In the overloaded case, try and keep the load balanced.
  	 */
  balance:
  	dst_load = env->dst_stats.load;
  	src_load = env->src_stats.load;
  
  	/* XXX missing power terms */
  	load = task_h_load(env->p);
  	dst_load += load;
  	src_load -= load;
  
  	if (cur) {
  		load = task_h_load(cur);
  		dst_load -= load;
  		src_load += load;
  	}
  
  	/* make src_load the smaller */
  	if (dst_load < src_load)
  		swap(dst_load, src_load);
  
  	if (src_load * env->imbalance_pct < dst_load * 100)
  		goto unlock;
  
  assign:
  	task_numa_assign(env, cur, imp);
  unlock:
  	rcu_read_unlock();
  }

  static void task_numa_find_cpu(struct task_numa_env *env,
  				long taskimp, long groupimp)

  {
  	int cpu;
  
  	for_each_cpu(cpu, cpumask_of_node(env->dst_nid)) {
  		/* Skip this CPU if the source task cannot migrate */
  		if (!cpumask_test_cpu(cpu, tsk_cpus_allowed(env->p)))
  			continue;
  
  		env->dst_cpu = cpu;

  		task_numa_compare(env, taskimp, groupimp);

  	}
  }

  static int task_numa_migrate(struct task_struct *p)
  {

  	struct task_numa_env env = {
  		.p = p,

  		.src_cpu = task_cpu(p),

  		.src_nid = task_node(p),

  
  		.imbalance_pct = 112,
  
  		.best_task = NULL,
  		.best_imp = 0,
  		.best_cpu = -1

  	};
  	struct sched_domain *sd;

  	unsigned long taskweight, groupweight;

  	int nid, ret;

  	long taskimp, groupimp;

  	/*

  	 * Pick the lowest SD_NUMA domain, as that would have the smallest
  	 * imbalance and would be the first to start moving tasks about.
  	 *
  	 * And we want to avoid any moving of tasks about, as that would create
  	 * random movement of tasks -- counter the numa conditions we're trying
  	 * to satisfy here.

  	 */
  	rcu_read_lock();

  	sd = rcu_dereference(per_cpu(sd_numa, env.src_cpu));

  	if (sd)
  		env.imbalance_pct = 100 + (sd->imbalance_pct - 100) / 2;

  	rcu_read_unlock();

  	/*
  	 * Cpusets can break the scheduler domain tree into smaller
  	 * balance domains, some of which do not cross NUMA boundaries.
  	 * Tasks that are "trapped" in such domains cannot be migrated
  	 * elsewhere, so there is no point in (re)trying.
  	 */
  	if (unlikely(!sd)) {

  		p->numa_preferred_nid = task_node(p);

  		return -EINVAL;
  	}

  	taskweight = task_weight(p, env.src_nid);
  	groupweight = group_weight(p, env.src_nid);

  	update_numa_stats(&env.src_stats, env.src_nid);

  	env.dst_nid = p->numa_preferred_nid;

  	taskimp = task_weight(p, env.dst_nid) - taskweight;
  	groupimp = group_weight(p, env.dst_nid) - groupweight;

  	update_numa_stats(&env.dst_stats, env.dst_nid);

  	/* If the preferred nid has capacity, try to use it. */
  	if (env.dst_stats.has_capacity)

  		task_numa_find_cpu(&env, taskimp, groupimp);

  
  	/* No space available on the preferred nid. Look elsewhere. */
  	if (env.best_cpu == -1) {

  		for_each_online_node(nid) {
  			if (nid == env.src_nid || nid == p->numa_preferred_nid)
  				continue;

  			/* Only consider nodes where both task and groups benefit */

  			taskimp = task_weight(p, nid) - taskweight;
  			groupimp = group_weight(p, nid) - groupweight;
  			if (taskimp < 0 && groupimp < 0)

  				continue;

  			env.dst_nid = nid;
  			update_numa_stats(&env.dst_stats, env.dst_nid);

  			task_numa_find_cpu(&env, taskimp, groupimp);

  		}
  	}

  	/* No better CPU than the current one was found. */
  	if (env.best_cpu == -1)
  		return -EAGAIN;

  	sched_setnuma(p, env.dst_nid);

  	/*
  	 * Reset the scan period if the task is being rescheduled on an
  	 * alternative node to recheck if the tasks is now properly placed.
  	 */
  	p->numa_scan_period = task_scan_min(p);

  	if (env.best_task == NULL) {

  		ret = migrate_task_to(p, env.best_cpu);
  		if (ret != 0)
  			trace_sched_stick_numa(p, env.src_cpu, env.best_cpu);

  		return ret;
  	}
  
  	ret = migrate_swap(p, env.best_task);

  	if (ret != 0)
  		trace_sched_stick_numa(p, env.src_cpu, task_cpu(env.best_task));

  	put_task_struct(env.best_task);
  	return ret;

  }

  /* Attempt to migrate a task to a CPU on the preferred node. */
  static void numa_migrate_preferred(struct task_struct *p)
  {

  	/* This task has no NUMA fault statistics yet */

  	if (unlikely(p->numa_preferred_nid == -1 || !p->numa_faults_memory))

  		return;

  	/* Periodically retry migrating the task to the preferred node */
  	p->numa_migrate_retry = jiffies + HZ;
  
  	/* Success if task is already running on preferred CPU */

  	if (task_node(p) == p->numa_preferred_nid)

  		return;
  
  	/* Otherwise, try migrate to a CPU on the preferred node */

  	task_numa_migrate(p);

  }

  /*

   * Find the nodes on which the workload is actively running. We do this by
   * tracking the nodes from which NUMA hinting faults are triggered. This can
   * be different from the set of nodes where the workload's memory is currently
   * located.
   *
   * The bitmask is used to make smarter decisions on when to do NUMA page
   * migrations, To prevent flip-flopping, and excessive page migrations, nodes
   * are added when they cause over 6/16 of the maximum number of faults, but
   * only removed when they drop below 3/16.
   */
  static void update_numa_active_node_mask(struct numa_group *numa_group)
  {
  	unsigned long faults, max_faults = 0;
  	int nid;
  
  	for_each_online_node(nid) {
  		faults = group_faults_cpu(numa_group, nid);
  		if (faults > max_faults)
  			max_faults = faults;
  	}
  
  	for_each_online_node(nid) {
  		faults = group_faults_cpu(numa_group, nid);
  		if (!node_isset(nid, numa_group->active_nodes)) {
  			if (faults > max_faults * 6 / 16)
  				node_set(nid, numa_group->active_nodes);
  		} else if (faults < max_faults * 3 / 16)
  			node_clear(nid, numa_group->active_nodes);
  	}
  }
  
  /*

   * When adapting the scan rate, the period is divided into NUMA_PERIOD_SLOTS
   * increments. The more local the fault statistics are, the higher the scan
   * period will be for the next scan window. If local/remote ratio is below
   * NUMA_PERIOD_THRESHOLD (where range of ratio is 1..NUMA_PERIOD_SLOTS) the
   * scan period will decrease
   */
  #define NUMA_PERIOD_SLOTS 10
  #define NUMA_PERIOD_THRESHOLD 3
  
  /*
   * Increase the scan period (slow down scanning) if the majority of
   * our memory is already on our local node, or if the majority of
   * the page accesses are shared with other processes.
   * Otherwise, decrease the scan period.
   */
  static void update_task_scan_period(struct task_struct *p,
  			unsigned long shared, unsigned long private)
  {
  	unsigned int period_slot;
  	int ratio;
  	int diff;
  
  	unsigned long remote = p->numa_faults_locality[0];
  	unsigned long local = p->numa_faults_locality[1];
  
  	/*
  	 * If there were no record hinting faults then either the task is
  	 * completely idle or all activity is areas that are not of interest
  	 * to automatic numa balancing. Scan slower
  	 */
  	if (local + shared == 0) {
  		p->numa_scan_period = min(p->numa_scan_period_max,
  			p->numa_scan_period << 1);
  
  		p->mm->numa_next_scan = jiffies +
  			msecs_to_jiffies(p->numa_scan_period);
  
  		return;
  	}
  
  	/*
  	 * Prepare to scale scan period relative to the current period.
  	 *	 == NUMA_PERIOD_THRESHOLD scan period stays the same
  	 *       <  NUMA_PERIOD_THRESHOLD scan period decreases (scan faster)
  	 *	 >= NUMA_PERIOD_THRESHOLD scan period increases (scan slower)
  	 */
  	period_slot = DIV_ROUND_UP(p->numa_scan_period, NUMA_PERIOD_SLOTS);
  	ratio = (local * NUMA_PERIOD_SLOTS) / (local + remote);
  	if (ratio >= NUMA_PERIOD_THRESHOLD) {
  		int slot = ratio - NUMA_PERIOD_THRESHOLD;
  		if (!slot)
  			slot = 1;
  		diff = slot * period_slot;
  	} else {
  		diff = -(NUMA_PERIOD_THRESHOLD - ratio) * period_slot;
  
  		/*
  		 * Scale scan rate increases based on sharing. There is an
  		 * inverse relationship between the degree of sharing and
  		 * the adjustment made to the scanning period. Broadly
  		 * speaking the intent is that there is little point
  		 * scanning faster if shared accesses dominate as it may
  		 * simply bounce migrations uselessly
  		 */

  		ratio = DIV_ROUND_UP(private * NUMA_PERIOD_SLOTS, (private + shared));
  		diff = (diff * ratio) / NUMA_PERIOD_SLOTS;
  	}
  
  	p->numa_scan_period = clamp(p->numa_scan_period + diff,
  			task_scan_min(p), task_scan_max(p));
  	memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
  }

  /*
   * Get the fraction of time the task has been running since the last
   * NUMA placement cycle. The scheduler keeps similar statistics, but
   * decays those on a 32ms period, which is orders of magnitude off
   * from the dozens-of-seconds NUMA balancing period. Use the scheduler
   * stats only if the task is so new there are no NUMA statistics yet.
   */
  static u64 numa_get_avg_runtime(struct task_struct *p, u64 *period)
  {
  	u64 runtime, delta, now;
  	/* Use the start of this time slice to avoid calculations. */
  	now = p->se.exec_start;
  	runtime = p->se.sum_exec_runtime;
  
  	if (p->last_task_numa_placement) {
  		delta = runtime - p->last_sum_exec_runtime;
  		*period = now - p->last_task_numa_placement;
  	} else {
  		delta = p->se.avg.runnable_avg_sum;
  		*period = p->se.avg.runnable_avg_period;
  	}
  
  	p->last_sum_exec_runtime = runtime;
  	p->last_task_numa_placement = now;
  
  	return delta;
  }

  static void task_numa_placement(struct task_struct *p)
  {

  	int seq, nid, max_nid = -1, max_group_nid = -1;
  	unsigned long max_faults = 0, max_group_faults = 0;

  	unsigned long fault_types[2] = { 0, 0 };

  	unsigned long total_faults;
  	u64 runtime, period;

  	spinlock_t *group_lock = NULL;

  	seq = ACCESS_ONCE(p->mm->numa_scan_seq);

  	if (p->numa_scan_seq == seq)
  		return;
  	p->numa_scan_seq = seq;

  	p->numa_scan_period_max = task_scan_max(p);

  	total_faults = p->numa_faults_locality[0] +
  		       p->numa_faults_locality[1];
  	runtime = numa_get_avg_runtime(p, &period);

  	/* If the task is part of a group prevent parallel updates to group stats */
  	if (p->numa_group) {
  		group_lock = &p->numa_group->lock;

  		spin_lock_irq(group_lock);

  	}

  	/* Find the node with the highest number of faults */
  	for_each_online_node(nid) {

  		unsigned long faults = 0, group_faults = 0;

  		int priv, i;

  		for (priv = 0; priv < NR_NUMA_HINT_FAULT_TYPES; priv++) {

  			long diff, f_diff, f_weight;

  			i = task_faults_idx(nid, priv);

  			/* Decay existing window, copy faults since last scan */

  			diff = p->numa_faults_buffer_memory[i] - p->numa_faults_memory[i] / 2;

  			fault_types[priv] += p->numa_faults_buffer_memory[i];
  			p->numa_faults_buffer_memory[i] = 0;

  			/*
  			 * Normalize the faults_from, so all tasks in a group
  			 * count according to CPU use, instead of by the raw
  			 * number of faults. Tasks with little runtime have
  			 * little over-all impact on throughput, and thus their
  			 * faults are less important.
  			 */
  			f_weight = div64_u64(runtime << 16, period + 1);
  			f_weight = (f_weight * p->numa_faults_buffer_cpu[i]) /
  				   (total_faults + 1);

  			f_diff = f_weight - p->numa_faults_cpu[i] / 2;

  			p->numa_faults_buffer_cpu[i] = 0;

  			p->numa_faults_memory[i] += diff;
  			p->numa_faults_cpu[i] += f_diff;

  			faults += p->numa_faults_memory[i];

  			p->total_numa_faults += diff;

  			if (p->numa_group) {
  				/* safe because we can only change our own group */

  				p->numa_group->faults[i] += diff;

  				p->numa_group->faults_cpu[i] += f_diff;

  				p->numa_group->total_faults += diff;
  				group_faults += p->numa_group->faults[i];

  			}

  		}

  		if (faults > max_faults) {
  			max_faults = faults;
  			max_nid = nid;
  		}

  
  		if (group_faults > max_group_faults) {
  			max_group_faults = group_faults;
  			max_group_nid = nid;
  		}
  	}

  	update_task_scan_period(p, fault_types[0], fault_types[1]);

  	if (p->numa_group) {

  		update_numa_active_node_mask(p->numa_group);

  		/*
  		 * If the preferred task and group nids are different,
  		 * iterate over the nodes again to find the best place.
  		 */
  		if (max_nid != max_group_nid) {
  			unsigned long weight, max_weight = 0;
  
  			for_each_online_node(nid) {
  				weight = task_weight(p, nid) + group_weight(p, nid);
  				if (weight > max_weight) {
  					max_weight = weight;
  					max_nid = nid;
  				}

  			}
  		}

  		spin_unlock_irq(group_lock);

  	}

  	/* Preferred node as the node with the most faults */

  	if (max_faults && max_nid != p->numa_preferred_nid) {

  		/* Update the preferred nid and migrate task if possible */

  		sched_setnuma(p, max_nid);

  		numa_migrate_preferred(p);

  	}

  }

  static inline int get_numa_group(struct numa_group *grp)
  {
  	return atomic_inc_not_zero(&grp->refcount);
  }
  
  static inline void put_numa_group(struct numa_group *grp)
  {
  	if (atomic_dec_and_test(&grp->refcount))
  		kfree_rcu(grp, rcu);
  }

  static void task_numa_group(struct task_struct *p, int cpupid, int flags,
  			int *priv)

  {
  	struct numa_group *grp, *my_grp;
  	struct task_struct *tsk;
  	bool join = false;
  	int cpu = cpupid_to_cpu(cpupid);
  	int i;
  
  	if (unlikely(!p->numa_group)) {
  		unsigned int size = sizeof(struct numa_group) +

  				    4*nr_node_ids*sizeof(unsigned long);

  
  		grp = kzalloc(size, GFP_KERNEL | __GFP_NOWARN);
  		if (!grp)
  			return;
  
  		atomic_set(&grp->refcount, 1);
  		spin_lock_init(&grp->lock);
  		INIT_LIST_HEAD(&grp->task_list);

  		grp->gid = p->pid;

  		/* Second half of the array tracks nids where faults happen */

  		grp->faults_cpu = grp->faults + NR_NUMA_HINT_FAULT_TYPES *
  						nr_node_ids;

  		node_set(task_node(current), grp->active_nodes);

  		for (i = 0; i < NR_NUMA_HINT_FAULT_STATS * nr_node_ids; i++)

  			grp->faults[i] = p->numa_faults_memory[i];

  		grp->total_faults = p->total_numa_faults;

  		list_add(&p->numa_entry, &grp->task_list);
  		grp->nr_tasks++;
  		rcu_assign_pointer(p->numa_group, grp);
  	}
  
  	rcu_read_lock();
  	tsk = ACCESS_ONCE(cpu_rq(cpu)->curr);
  
  	if (!cpupid_match_pid(tsk, cpupid))

  		goto no_join;

  
  	grp = rcu_dereference(tsk->numa_group);
  	if (!grp)

  		goto no_join;

  
  	my_grp = p->numa_group;
  	if (grp == my_grp)

  		goto no_join;

  
  	/*
  	 * Only join the other group if its bigger; if we're the bigger group,
  	 * the other task will join us.
  	 */
  	if (my_grp->nr_tasks > grp->nr_tasks)

  		goto no_join;

  
  	/*
  	 * Tie-break on the grp address.
  	 */
  	if (my_grp->nr_tasks == grp->nr_tasks && my_grp > grp)

  		goto no_join;

  	/* Always join threads in the same process. */
  	if (tsk->mm == current->mm)
  		join = true;
  
  	/* Simple filter to avoid false positives due to PID collisions */
  	if (flags & TNF_SHARED)
  		join = true;

  	/* Update priv based on whether false sharing was detected */
  	*priv = !join;

  	if (join && !get_numa_group(grp))

  		goto no_join;

  	rcu_read_unlock();
  
  	if (!join)
  		return;

  	BUG_ON(irqs_disabled());
  	double_lock_irq(&my_grp->lock, &grp->lock);

  	for (i = 0; i < NR_NUMA_HINT_FAULT_STATS * nr_node_ids; i++) {

  		my_grp->faults[i] -= p->numa_faults_memory[i];
  		grp->faults[i] += p->numa_faults_memory[i];

  	}

  	my_grp->total_faults -= p->total_numa_faults;
  	grp->total_faults += p->total_numa_faults;

  
  	list_move(&p->numa_entry, &grp->task_list);
  	my_grp->nr_tasks--;
  	grp->nr_tasks++;
  
  	spin_unlock(&my_grp->lock);

  	spin_unlock_irq(&grp->lock);

  
  	rcu_assign_pointer(p->numa_group, grp);
  
  	put_numa_group(my_grp);

  	return;
  
  no_join:
  	rcu_read_unlock();
  	return;

  }
  
  void task_numa_free(struct task_struct *p)
  {
  	struct numa_group *grp = p->numa_group;

  	void *numa_faults = p->numa_faults_memory;

  	unsigned long flags;
  	int i;

  
  	if (grp) {

  		spin_lock_irqsave(&grp->lock, flags);

  		for (i = 0; i < NR_NUMA_HINT_FAULT_STATS * nr_node_ids; i++)

  			grp->faults[i] -= p->numa_faults_memory[i];

  		grp->total_faults -= p->total_numa_faults;

  		list_del(&p->numa_entry);
  		grp->nr_tasks--;

  		spin_unlock_irqrestore(&grp->lock, flags);

  		rcu_assign_pointer(p->numa_group, NULL);
  		put_numa_group(grp);
  	}

  	p->numa_faults_memory = NULL;
  	p->numa_faults_buffer_memory = NULL;

  	p->numa_faults_cpu= NULL;
  	p->numa_faults_buffer_cpu = NULL;

  	kfree(numa_faults);

  }

  /*
   * Got a PROT_NONE fault for a page on @node.
   */

  void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags)

  {
  	struct task_struct *p = current;

  	bool migrated = flags & TNF_MIGRATED;

  	int cpu_node = task_node(current);

  	int priv;

  	if (!numabalancing_enabled)

  		return;

  	/* for example, ksmd faulting in a user's mm */
  	if (!p->mm)
  		return;

  	/* Do not worry about placement if exiting */
  	if (p->state == TASK_DEAD)
  		return;

  	/* Allocate buffer to track faults on a per-node basis */

  	if (unlikely(!p->numa_faults_memory)) {

  		int size = sizeof(*p->numa_faults_memory) *
  			   NR_NUMA_HINT_FAULT_BUCKETS * nr_node_ids;

  		p->numa_faults_memory = kzalloc(size, GFP_KERNEL|__GFP_NOWARN);

  		if (!p->numa_faults_memory)

  			return;

  		BUG_ON(p->numa_faults_buffer_memory);

  		/*
  		 * The averaged statistics, shared & private, memory & cpu,
  		 * occupy the first half of the array. The second half of the
  		 * array is for current counters, which are averaged into the
  		 * first set by task_numa_placement.
  		 */

  		p->numa_faults_cpu = p->numa_faults_memory + (2 * nr_node_ids);
  		p->numa_faults_buffer_memory = p->numa_faults_memory + (4 * nr_node_ids);
  		p->numa_faults_buffer_cpu = p->numa_faults_memory + (6 * nr_node_ids);

  		p->total_numa_faults = 0;

  		memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));

  	}

  	/*

  	 * First accesses are treated as private, otherwise consider accesses
  	 * to be private if the accessing pid has not changed
  	 */
  	if (unlikely(last_cpupid == (-1 & LAST_CPUPID_MASK))) {
  		priv = 1;
  	} else {
  		priv = cpupid_match_pid(p, last_cpupid);

  		if (!priv && !(flags & TNF_NO_GROUP))

  			task_numa_group(p, last_cpupid, flags, &priv);

  	}

  	task_numa_placement(p);

  	/*
  	 * Retry task to preferred node migration periodically, in case it
  	 * case it previously failed, or the scheduler moved us.
  	 */
  	if (time_after(jiffies, p->numa_migrate_retry))

  		numa_migrate_preferred(p);

  	if (migrated)
  		p->numa_pages_migrated += pages;

  	p->numa_faults_buffer_memory[task_faults_idx(mem_node, priv)] += pages;
  	p->numa_faults_buffer_cpu[task_faults_idx(cpu_node, priv)] += pages;

  	p->numa_faults_locality[!!(flags & TNF_FAULT_LOCAL)] += pages;

  }

  static void reset_ptenuma_scan(struct task_struct *p)
  {
  	ACCESS_ONCE(p->mm->numa_scan_seq)++;
  	p->mm->numa_scan_offset = 0;
  }

  /*
   * The expensive part of numa migration is done from task_work context.
   * Triggered from task_tick_numa().
   */
  void task_numa_work(struct callback_head *work)
  {
  	unsigned long migrate, next_scan, now = jiffies;
  	struct task_struct *p = current;
  	struct mm_struct *mm = p->mm;

  	struct vm_area_struct *vma;

  	unsigned long start, end;

  	unsigned long nr_pte_updates = 0;

  	long pages;

  
  	WARN_ON_ONCE(p != container_of(work, struct task_struct, numa_work));
  
  	work->next = work; /* protect against double add */
  	/*
  	 * Who cares about NUMA placement when they're dying.
  	 *
  	 * NOTE: make sure not to dereference p->mm before this check,
  	 * exit_task_work() happens _after_ exit_mm() so we could be called
  	 * without p->mm even though we still had it when we enqueued this
  	 * work.
  	 */
  	if (p->flags & PF_EXITING)
  		return;

  	if (!mm->numa_next_scan) {

  		mm->numa_next_scan = now +
  			msecs_to_jiffies(sysctl_numa_balancing_scan_delay);

  	}
  
  	/*

  	 * Enforce maximal scan/migration frequency..
  	 */
  	migrate = mm->numa_next_scan;
  	if (time_before(now, migrate))
  		return;

  	if (p->numa_scan_period == 0) {
  		p->numa_scan_period_max = task_scan_max(p);
  		p->numa_scan_period = task_scan_min(p);
  	}

  	next_scan = now + msecs_to_jiffies(p->numa_scan_period);

  	if (cmpxchg(&mm->numa_next_scan, migrate, next_scan) != migrate)
  		return;

  	/*

  	 * Delay this task enough that another task of this mm will likely win
  	 * the next time around.
  	 */
  	p->node_stamp += 2 * TICK_NSEC;

  	start = mm->numa_scan_offset;
  	pages = sysctl_numa_balancing_scan_size;
  	pages <<= 20 - PAGE_SHIFT; /* MB in pages */
  	if (!pages)
  		return;

  	down_read(&mm->mmap_sem);

  	vma = find_vma(mm, start);

  	if (!vma) {
  		reset_ptenuma_scan(p);

  		start = 0;

  		vma = mm->mmap;
  	}

  	for (; vma; vma = vma->vm_next) {

  		if (!vma_migratable(vma) || !vma_policy_mof(p, vma))

  			continue;

  		/*
  		 * Shared library pages mapped by multiple processes are not
  		 * migrated as it is expected they are cache replicated. Avoid
  		 * hinting faults in read-only file-backed mappings or the vdso
  		 * as migrating the pages will be of marginal benefit.
  		 */
  		if (!vma->vm_mm ||
  		    (vma->vm_file && (vma->vm_flags & (VM_READ|VM_WRITE)) == (VM_READ)))
  			continue;

  		/*
  		 * Skip inaccessible VMAs to avoid any confusion between
  		 * PROT_NONE and NUMA hinting ptes
  		 */
  		if (!(vma->vm_flags & (VM_READ | VM_EXEC | VM_WRITE)))
  			continue;

  		do {
  			start = max(start, vma->vm_start);
  			end = ALIGN(start + (pages << PAGE_SHIFT), HPAGE_SIZE);
  			end = min(end, vma->vm_end);

  			nr_pte_updates += change_prot_numa(vma, start, end);
  
  			/*
  			 * Scan sysctl_numa_balancing_scan_size but ensure that
  			 * at least one PTE is updated so that unused virtual
  			 * address space is quickly skipped.
  			 */
  			if (nr_pte_updates)
  				pages -= (end - start) >> PAGE_SHIFT;

  			start = end;
  			if (pages <= 0)
  				goto out;

  
  			cond_resched();

  		} while (end != vma->vm_end);

  	}

  out:

  	/*

  	 * It is possible to reach the end of the VMA list but the last few
  	 * VMAs are not guaranteed to the vma_migratable. If they are not, we
  	 * would find the !migratable VMA on the next scan but not reset the
  	 * scanner to the start so check it now.

  	 */
  	if (vma)

  		mm->numa_scan_offset = start;

  	else
  		reset_ptenuma_scan(p);
  	up_read(&mm->mmap_sem);

  }
  
  /*
   * Drive the periodic memory faults..
   */
  void task_tick_numa(struct rq *rq, struct task_struct *curr)
  {
  	struct callback_head *work = &curr->numa_work;
  	u64 period, now;
  
  	/*
  	 * We don't care about NUMA placement if we don't have memory.
  	 */
  	if (!curr->mm || (curr->flags & PF_EXITING) || work->next != work)
  		return;
  
  	/*
  	 * Using runtime rather than walltime has the dual advantage that
  	 * we (mostly) drive the selection from busy threads and that the
  	 * task needs to have done some actual work before we bother with
  	 * NUMA placement.
  	 */
  	now = curr->se.sum_exec_runtime;
  	period = (u64)curr->numa_scan_period * NSEC_PER_MSEC;
  
  	if (now - curr->node_stamp > period) {

  		if (!curr->node_stamp)

  			curr->numa_scan_period = task_scan_min(curr);

  		curr->node_stamp += period;

  
  		if (!time_before(jiffies, curr->mm->numa_next_scan)) {
  			init_task_work(work, task_numa_work); /* TODO: move this into sched_fork() */
  			task_work_add(curr, work, true);
  		}
  	}
  }
  #else
  static void task_tick_numa(struct rq *rq, struct task_struct *curr)
  {
  }

  
  static inline void account_numa_enqueue(struct rq *rq, struct task_struct *p)
  {
  }
  
  static inline void account_numa_dequeue(struct rq *rq, struct task_struct *p)
  {
  }

  #endif /* CONFIG_NUMA_BALANCING */

  static void
  account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
  {
  	update_load_add(&cfs_rq->load, se->load.weight);

  	if (!parent_entity(se))

  		update_load_add(&rq_of(cfs_rq)->load, se->load.weight);

  #ifdef CONFIG_SMP

  	if (entity_is_task(se)) {
  		struct rq *rq = rq_of(cfs_rq);
  
  		account_numa_enqueue(rq, task_of(se));
  		list_add(&se->group_node, &rq->cfs_tasks);
  	}

  #endif

  	cfs_rq->nr_running++;

  }
  
  static void
  account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
  {
  	update_load_sub(&cfs_rq->load, se->load.weight);

  	if (!parent_entity(se))

  		update_load_sub(&rq_of(cfs_rq)->load, se->load.weight);

  	if (entity_is_task(se)) {
  		account_numa_dequeue(rq_of(cfs_rq), task_of(se));

  		list_del_init(&se->group_node);

  	}

  	cfs_rq->nr_running--;

  }

  #ifdef CONFIG_FAIR_GROUP_SCHED
  # ifdef CONFIG_SMP

  static inline long calc_tg_weight(struct task_group *tg, struct cfs_rq *cfs_rq)
  {
  	long tg_weight;
  
  	/*
  	 * Use this CPU's actual weight instead of the last load_contribution
  	 * to gain a more accurate current total weight. See
  	 * update_cfs_rq_load_contribution().
  	 */

  	tg_weight = atomic_long_read(&tg->load_avg);

  	tg_weight -= cfs_rq->tg_load_contrib;

  	tg_weight += cfs_rq->load.weight;
  
  	return tg_weight;
  }

  static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)

  {

  	long tg_weight, load, shares;

  	tg_weight = calc_tg_weight(tg, cfs_rq);

  	load = cfs_rq->load.weight;

  	shares = (tg->shares * load);

  	if (tg_weight)
  		shares /= tg_weight;

  
  	if (shares < MIN_SHARES)
  		shares = MIN_SHARES;
  	if (shares > tg->shares)
  		shares = tg->shares;
  
  	return shares;
  }

  # else /* CONFIG_SMP */

  static inline long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)

  {
  	return tg->shares;
  }

  # endif /* CONFIG_SMP */

  static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
  			    unsigned long weight)
  {