Re: [PATCH] android: binder: Disable preemption while holding the global binder lock

[Todd Kjos]

Thanks Peter. We'll give that patch a try as part of our refactoring.
Looking at finer-grained locking and we'll try going back to rt_mutex
plus this patch.

On Wed, Sep 14, 2016 at 9:55 AM, Peter Zijlstra <peterz@xxxxxxxxxxxxx> wrote:
> On Wed, Sep 14, 2016 at 06:13:40PM +0200, Peter Zijlstra wrote:
>> On Wed, Sep 14, 2016 at 06:11:03PM +0200, Peter Zijlstra wrote:
>> > On Tue, Sep 13, 2016 at 12:53:27PM -0700, Arve HjÃnnevÃg wrote:
>> > > On Tue, Sep 13, 2016 at 12:32 AM, Peter Zijlstra <peterz@xxxxxxxxxxxxx> wrote:
>> > > > cgroups should be irrelevant, PI is unaware of them.
>> > >
>> > > I don't think cgroups are irrelevant. PI being unaware of them
>> > > explains the problem I described. If the task that holds the lock is
>> > > in a cgroup that has a low cpu.shares value, then boosting the task's
>> > > priority within that group does necessarily make it any more likely to
>> > > run.
>> >
>> > Thing is, for FIFO/DL the important parameters (prio and deadline resp.)
>> > are not cgroup dependent.
>> >
>> > For CFS you're right, and as per usual, cgroups will be a royal pain.
>> > While we can compute the total weight in the block chain, getting that
>> > back to a task which is stuck in a cgroup is just not going to work
>> > well.
>>
>> Not to mention the fact that the weight depends on the current running
>> state. Having those tasks block insta changes the actual weight.
>>
>> > /me curses @ cgroups.. bloody stupid things.
>>
>> More of that.
>
>
> Something a little like so... completely untested, and has a fair number
> of corner cases still left open I think..
>
>
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -1691,8 +1691,8 @@ struct task_struct {
>         struct seccomp seccomp;
>
>  /* Thread group tracking */
> -       u32 parent_exec_id;
> -       u32 self_exec_id;
> +       u32 parent_exec_id;
> +       u32 self_exec_id;
>  /* Protection of (de-)allocation: mm, files, fs, tty, keyrings, mems_allowed,
>   * mempolicy */
>         spinlock_t alloc_lock;
> @@ -1710,6 +1710,11 @@ struct task_struct {
>         struct task_struct *pi_top_task;
>         /* Deadlock detection and priority inheritance handling */
>         struct rt_mutex_waiter *pi_blocked_on;
> +       unsigned long pi_weight;
> +#ifdef CONFIG_CGROUP_SCHED
> +       struct task_group *orig_task_group;
> +       unsigned long normal_weight;
> +#endif
>  #endif
>
>  #ifdef CONFIG_DEBUG_MUTEXES
> @@ -1977,6 +1982,8 @@ static inline int tsk_nr_cpus_allowed(st
>         return p->nr_cpus_allowed;
>  }
>
> +extern unsigned long task_pi_weight(struct task_struct *p);
> +
>  #define TNF_MIGRATED   0x01
>  #define TNF_NO_GROUP   0x02
>  #define TNF_SHARED     0x04
> --- a/kernel/locking/rtmutex.c
> +++ b/kernel/locking/rtmutex.c
> @@ -20,6 +20,19 @@
>  #include "rtmutex_common.h"
>
>  /*
> + * !(rt_prio || dl_prio)
> + */
> +static inline bool other_prio(int prio)
> +{
> +       return prio >= MAX_RT_PRIO;
> +}
> +
> +static inline bool other_task(struct task_struct *task)
> +{
> +       return other_prio(task->prio);
> +}
> +
> +/*
>   * lock->owner state tracking:
>   *
>   * lock->owner holds the task_struct pointer of the owner. Bit 0
> @@ -226,6 +239,11 @@ rt_mutex_enqueue(struct rt_mutex *lock,
>
>         rb_link_node(&waiter->tree_entry, parent, link);
>         rb_insert_color(&waiter->tree_entry, &lock->waiters);
> +       /*
> +        * We want the lock->waiter_weight to reflect the sum of all queued
> +        * waiters.
> +        */
> +       lock->waiters_weight += waiter->weight;
>  }
>
>  static void
> @@ -239,6 +257,7 @@ rt_mutex_dequeue(struct rt_mutex *lock,
>
>         rb_erase(&waiter->tree_entry, &lock->waiters);
>         RB_CLEAR_NODE(&waiter->tree_entry);
> +       lock->waiters_weight += waiter->weight;
>  }
>
>  static void
> @@ -265,6 +284,18 @@ rt_mutex_enqueue_pi(struct task_struct *
>
>         rb_link_node(&waiter->pi_tree_entry, parent, link);
>         rb_insert_color(&waiter->pi_tree_entry, &task->pi_waiters);
> +
> +       /*
> +        * Since a task can own multiple locks, and we have one pi_waiter
> +        * for every lock, propagate the lock->waiter_weight, which is the sum
> +        * of all weights queued on that lock, into the top waiter, and add
> +        * that to the owning task's pi_weight.
> +        *
> +        * This results in pi_weight being the sum of all blocked waiters
> +        * on this task.
> +        */
> +       waiter->top_weight = waiter->lock->waiters_weight;
> +       task->pi_weight += waiter->top_weight;
>  }
>
>  static void
> @@ -278,6 +309,7 @@ rt_mutex_dequeue_pi(struct task_struct *
>
>         rb_erase(&waiter->pi_tree_entry, &task->pi_waiters);
>         RB_CLEAR_NODE(&waiter->pi_tree_entry);
> +       task->pi_weight -= waiter->top_weight;
>  }
>
>  static void rt_mutex_adjust_prio(struct task_struct *p)
> @@ -497,7 +529,7 @@ static int rt_mutex_adjust_prio_chain(st
>                  * detection is enabled we continue, but stop the
>                  * requeueing in the chain walk.
>                  */
> -               if (top_waiter != task_top_pi_waiter(task)) {
> +               if (top_waiter != task_top_pi_waiter(task) && !other_task(task)) {
>                         if (!detect_deadlock)
>                                 goto out_unlock_pi;
>                         else
> @@ -512,7 +544,7 @@ static int rt_mutex_adjust_prio_chain(st
>          * enabled we continue, but stop the requeueing in the chain
>          * walk.
>          */
> -       if (rt_mutex_waiter_equal(waiter, cmp_task(task))) {
> +       if (rt_mutex_waiter_equal(waiter, cmp_task(task)) && !other_task(task)) {
>                 if (!detect_deadlock)
>                         goto out_unlock_pi;
>                 else
> @@ -627,6 +659,11 @@ static int rt_mutex_adjust_prio_chain(st
>          */
>         waiter->prio = task->prio;
>         waiter->deadline = task->dl.deadline;
> +       /*
> +        * The weight of the task depends on the block chain, since
> +        * we're iterating that, its likely to have changed.
> +        */
> +       waiter->weight = task_pi_weight(task);
>
>         rt_mutex_enqueue(lock, waiter);
>
> @@ -685,6 +722,15 @@ static int rt_mutex_adjust_prio_chain(st
>                 waiter = rt_mutex_top_waiter(lock);
>                 rt_mutex_enqueue_pi(task, waiter);
>                 rt_mutex_adjust_prio(task);
> +
> +       } else if (other_task(task)) {
> +               /*
> +                * Propagate the lock->waiters_weight into task->pi_weight
> +                */
> +               rt_mutex_dequeue_pi(task, prerequeue_top_waiter);
> +               rt_mutex_enqueue_pi(task, prerequeue_top_waiter);
> +               rt_mutex_adjust_prio(task);
> +
>         } else {
>                 /*
>                  * Nothing changed. No need to do any priority
> @@ -728,7 +774,7 @@ static int rt_mutex_adjust_prio_chain(st
>          * then we can stop the chain walk here if we are not in full
>          * deadlock detection mode.
>          */
> -       if (!detect_deadlock && waiter != top_waiter)
> +       if (!detect_deadlock && waiter != top_waiter && !other_task(task))
>                 goto out_put_task;
>
>         goto again;
> @@ -904,6 +950,7 @@ static int task_blocks_on_rt_mutex(struc
>         waiter->lock = lock;
>         waiter->prio = task->prio;
>         waiter->deadline = task->dl.deadline;
> +       waiter->weight = task_pi_weight(task);
>
>         /* Get the top priority waiter on the lock */
>         if (rt_mutex_has_waiters(lock))
> @@ -918,7 +965,7 @@ static int task_blocks_on_rt_mutex(struc
>                 return 0;
>
>         raw_spin_lock(&owner->pi_lock);
> -       if (waiter == rt_mutex_top_waiter(lock)) {
> +       if (other_task(owner) || waiter == rt_mutex_top_waiter(lock)) {
>                 rt_mutex_dequeue_pi(owner, top_waiter);
>                 rt_mutex_enqueue_pi(owner, waiter);
>
> @@ -1017,7 +1064,8 @@ static void mark_wakeup_next_waiter(stru
>  static void remove_waiter(struct rt_mutex *lock,
>                           struct rt_mutex_waiter *waiter)
>  {
> -       bool is_top_waiter = (waiter == rt_mutex_top_waiter(lock));
> +       struct rt_mutex_waiter *top_waiter = rt_mutex_top_waiter(lock);
> +       bool is_top_waiter = (waiter == top_waiter);
>         struct task_struct *owner = rt_mutex_owner(lock);
>         struct rt_mutex *next_lock;
>
> @@ -1032,12 +1080,12 @@ static void remove_waiter(struct rt_mute
>          * Only update priority if the waiter was the highest priority
>          * waiter of the lock and there is an owner to update.
>          */
> -       if (!owner || !is_top_waiter)
> +       if (!owner || (!other_task(owner) && !is_top_waiter))
>                 return;
>
>         raw_spin_lock(&owner->pi_lock);
>
> -       rt_mutex_dequeue_pi(owner, waiter);
> +       rt_mutex_dequeue_pi(owner, top_waiter);
>
>         if (rt_mutex_has_waiters(lock))
>                 rt_mutex_enqueue_pi(owner, rt_mutex_top_waiter(lock));
> --- a/kernel/locking/rtmutex_common.h
> +++ b/kernel/locking/rtmutex_common.h
> @@ -34,6 +34,7 @@ struct rt_mutex_waiter {
>  #endif
>         int prio;
>         u64 deadline;
> +       unsigned weight, top_weight;
>  };
>
>  /*
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -3725,6 +3725,8 @@ void rt_mutex_setprio(struct task_struct
>                 if (rt_prio(oldprio))
>                         p->rt.timeout = 0;
>                 p->sched_class = &fair_sched_class;
> +
> +               task_set_pi_weight(p);
>         }
>
>         p->prio = prio;
> @@ -7933,6 +7935,12 @@ static void sched_change_group(struct ta
>         tg = container_of(task_css_check(tsk, cpu_cgrp_id, true),
>                           struct task_group, css);
>         tg = autogroup_task_group(tsk, tg);
> +
> +#ifdef CONFIG_RT_MUTEXES
> +       tsk->orig_task_group = tg;
> +
> +       if (!tsk->pi_weight)
> +#endif
>         tsk->sched_task_group = tg;
>
>  #ifdef CONFIG_FAIR_GROUP_SCHED
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -6646,6 +6646,32 @@ static void attach_tasks(struct lb_env *
>         raw_spin_unlock(&env->dst_rq->lock);
>  }
>
> +#ifdef CONFIG_RT_MUTEXES
> +/*
> + * See set_load_weight().
> + */
> +static inline unsigned long __task_normal_weight(struct task_struct *p)
> +{
> +       int prio = p->static_prio - MAX_RT_PRIO;
> +
> +       /*
> +        * SCHED_IDLE tasks get minimal weight:
> +        */
> +       if (idle_policy(p->policy))
> +               return scale_load(WEIGHT_IDLEPRIO);
> +
> +       return scale_load(sched_prio_to_weight[prio]);
> +}
> +
> +
> +static unsigned long task_normal_weight(struct task_struct *p);
> +
> +unsigned long task_pi_weight(struct task_struct *p)
> +{
> +       return task_normal_weight(p) + p->pi_weight;
> +}
> +#endif
> +
>  #ifdef CONFIG_FAIR_GROUP_SCHED
>  static void update_blocked_averages(int cpu)
>  {
> @@ -6717,7 +6743,80 @@ static unsigned long task_h_load(struct
>         return div64_ul(p->se.avg.load_avg * cfs_rq->h_load,
>                         cfs_rq_load_avg(cfs_rq) + 1);
>  }
> -#else
> +
> +#ifdef CONFIG_RT_MUTEXES
> +/*
> + * Humongous horrid hack.. because cgroups bloody stink.
> + *
> + * The idea with PI on CFS is to sum the weight of all blocked tasks but with
> + * cgroups the weight of a task depends on the running state of tasks. Blocking
> + * changes the weight.
> + *
> + * Paper over that problem by using the regular averages, and hoping boosting
> + * is short enough to not actually matter much.
> + *
> + * The next problem is that getting that weight back to the boosted task
> + * requires lifting it out of its cgroup. Ideally we'd place it in the first
> + * common parent, but *shees* then we'd have to compute that, so bail and stick
> + * it in the root group.
> + */
> +
> +static unsigned long task_normal_weight(struct task_struct *p)
> +{
> +       struct cfs_rq *cfs_rq = task_cfs_rq(p);
> +
> +       /*
> +        * Once we have ->pi_weight, we'll get boosted into the root group
> +        * and the below falls apart.
> +        */
> +       if (!p->pi_weight) {
> +               update_cfs_rq_h_load(cfs_rq);
> +               p->normal_weight =
> +                       div64_ul(__task_normal_weight(p) * cfs_rq->h_load,
> +                                       cfs_rq_load_avg(cfs_rq) + 1);
> +       }
> +
> +       return p->normal_weight;
> +}
> +
> +static void detach_task_cfs_rq(struct task_struct *p);
> +static void attach_task_cfs_rq(struct task_struct *p);
> +
> +void task_set_pi_weight(struct task_struct *p)
> +{
> +       unsigned long normal_weight = p->normal_weight;
> +       struct task_group *tg = &root_task_group;
> +       bool move_group;
> +
> +       if (!p->pi_weight) {
> +               tg = p->orig_task_group;
> +               normal_weight = __task_normal_weight(p);
> +       }
> +
> +       move_group = p->sched_task_group != tg;
> +
> +       if (move_group) {
> +               p->sched_task_group = tg;
> +
> +               detach_task_cfs_rq(p);
> +               set_task_rq(p, task_cpu(p));
> +
> +#ifdef CONFIG_SMP
> +               /* Tell se's cfs_rq has been changed -- migrated */
> +               p->se.avg.last_update_time = 0;
> +#endif
> +       }
> +
> +       update_load_set(&p->se.load, normal_weight + p->pi_weight);
> +
> +       if (move_group)
> +               attach_task_cfs_rq(p);
> +}
> +
> +#endif
> +
> +#else /* CONFIG_FAIR_GROUP_SCHED */
> +
>  static inline void update_blocked_averages(int cpu)
>  {
>         struct rq *rq = cpu_rq(cpu);
> @@ -6734,8 +6833,21 @@ static unsigned long task_h_load(struct
>  {
>         return p->se.avg.load_avg;
>  }
> +
> +#ifdef CONFIG_RT_MUTEXES
> +static unsigned long task_normal_weight(struct task_struct *p)
> +{
> +       return __task_normal_weight(p);
> +}
> +
> +void task_set_pi_weight(struct task_struct *p)
> +{
> +       update_load_set(&p->se.load, task_pi_weight(p));
> +}
>  #endif
>
> +#endif /* CONFIG_FAIR_GROUP_SCHED */
> +
>  /********** Helpers for find_busiest_group ************************/
>
>  enum group_type {
> --- a/kernel/sched/sched.h
> +++ b/kernel/sched/sched.h
> @@ -1827,3 +1827,5 @@ static inline void cpufreq_trigger_updat
>  #else /* arch_scale_freq_capacity */
>  #define arch_scale_freq_invariant()    (false)
>  #endif
> +
> +extern void task_set_pi_weight(struct task_struct *p);