Merge tag 'omap-fixes-audio-clock-and-modem-signed' of git://git.kernel.org/pub/scm...

[platform/kernel/linux-rpi.git] / kernel / sched / fair.c

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index cb22592..061a30a 100644 (file)
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -664,6 +664,10 @@ void avg_vruntime_update(struct cfs_rq *cfs_rq, s64 delta)
        cfs_rq->avg_vruntime -= cfs_rq->avg_load * delta;
 }
 
+/*
+ * Specifically: avg_runtime() + 0 must result in entity_eligible() := true
+ * For this to be so, the result of this function must have a left bias.
+ */
 u64 avg_vruntime(struct cfs_rq *cfs_rq)
 {
        struct sched_entity *curr = cfs_rq->curr;
@@ -677,8 +681,12 @@ u64 avg_vruntime(struct cfs_rq *cfs_rq)
                load += weight;
        }
 
-       if (load)
+       if (load) {
+               /* sign flips effective floor / ceil */
+               if (avg < 0)
+                       avg -= (load - 1);
                avg = div_s64(avg, load);
+       }
 
        return cfs_rq->min_vruntime + avg;
 }
@@ -864,14 +872,16 @@ struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
  *
  * Which allows an EDF like search on (sub)trees.
  */
-static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq)
+static struct sched_entity *__pick_eevdf(struct cfs_rq *cfs_rq)
 {
        struct rb_node *node = cfs_rq->tasks_timeline.rb_root.rb_node;
        struct sched_entity *curr = cfs_rq->curr;
        struct sched_entity *best = NULL;
+       struct sched_entity *best_left = NULL;
 
        if (curr && (!curr->on_rq || !entity_eligible(cfs_rq, curr)))
                curr = NULL;
+       best = curr;
 
        /*
         * Once selected, run a task until it either becomes non-eligible or
@@ -892,33 +902,75 @@ static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq)
                }
 
                /*
-                * If this entity has an earlier deadline than the previous
-                * best, take this one. If it also has the earliest deadline
-                * of its subtree, we're done.
+                * Now we heap search eligible trees for the best (min_)deadline
                 */
-               if (!best || deadline_gt(deadline, best, se)) {
+               if (!best || deadline_gt(deadline, best, se))
                        best = se;
-                       if (best->deadline == best->min_deadline)
-                               break;
-               }
 
                /*
-                * If the earlest deadline in this subtree is in the fully
-                * eligible left half of our space, go there.
+                * Every se in a left branch is eligible, keep track of the
+                * branch with the best min_deadline
                 */
+               if (node->rb_left) {
+                       struct sched_entity *left = __node_2_se(node->rb_left);
+
+                       if (!best_left || deadline_gt(min_deadline, best_left, left))
+                               best_left = left;
+
+                       /*
+                        * min_deadline is in the left branch. rb_left and all
+                        * descendants are eligible, so immediately switch to the second
+                        * loop.
+                        */
+                       if (left->min_deadline == se->min_deadline)
+                               break;
+               }
+
+               /* min_deadline is at this node, no need to look right */
+               if (se->deadline == se->min_deadline)
+                       break;
+
+               /* else min_deadline is in the right branch. */
+               node = node->rb_right;
+       }
+
+       /*
+        * We ran into an eligible node which is itself the best.
+        * (Or nr_running == 0 and both are NULL)
+        */
+       if (!best_left || (s64)(best_left->min_deadline - best->deadline) > 0)
+               return best;
+
+       /*
+        * Now best_left and all of its children are eligible, and we are just
+        * looking for deadline == min_deadline
+        */
+       node = &best_left->run_node;
+       while (node) {
+               struct sched_entity *se = __node_2_se(node);
+
+               /* min_deadline is the current node */
+               if (se->deadline == se->min_deadline)
+                       return se;
+
+               /* min_deadline is in the left branch */
                if (node->rb_left &&
                    __node_2_se(node->rb_left)->min_deadline == se->min_deadline) {
                        node = node->rb_left;
                        continue;
                }
 
+               /* else min_deadline is in the right branch */
                node = node->rb_right;
        }
+       return NULL;
+}
 
-       if (!best || (curr && deadline_gt(deadline, best, curr)))
-               best = curr;
+static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq)
+{
+       struct sched_entity *se = __pick_eevdf(cfs_rq);
 
-       if (unlikely(!best)) {
+       if (!se) {
                struct sched_entity *left = __pick_first_entity(cfs_rq);
                if (left) {
                        pr_err("EEVDF scheduling fail, picking leftmost\n");
@@ -926,7 +978,7 @@ static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq)
                }
        }
 
-       return best;
+       return se;
 }
 
 #ifdef CONFIG_SCHED_DEBUG
@@ -3605,6 +3657,7 @@ static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
                 */
                deadline = div_s64(deadline * old_weight, weight);
                se->deadline = se->vruntime + deadline;
+               min_deadline_cb_propagate(&se->run_node, NULL);
        }
 
 #ifdef CONFIG_SMP
@@ -4919,10 +4972,12 @@ static inline void update_misfit_status(struct task_struct *p, struct rq *rq) {}
 static void
 place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 {
-       u64 vslice = calc_delta_fair(se->slice, se);
-       u64 vruntime = avg_vruntime(cfs_rq);
+       u64 vslice, vruntime = avg_vruntime(cfs_rq);
        s64 lag = 0;
 
+       se->slice = sysctl_sched_base_slice;
+       vslice = calc_delta_fair(se->slice, se);
+
        /*
         * Due to how V is constructed as the weighted average of entities,
         * adding tasks with positive lag, or removing tasks with negative lag