Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1373783 > unrolled thread

Re: sched: horrible way to detect whether a task has been preempted

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: sched: horrible way to detect whether a task has been preempted Jessica Yu <jeyu@redhat.com> - 2016-04-07 23:20 +0200
    Re: sched: horrible way to detect whether a task has been  preempted Jiri Kosina <jikos@kernel.org> - 2016-04-07 23:40 +0200
      Re: sched: horrible way to detect whether a task has been preempted Josh Poimboeuf <jpoimboe@redhat.com> - 2016-04-08 00:40 +0200
        Re: sched: horrible way to detect whether a task has been  preempted Jiri Kosina <jikos@kernel.org> - 2016-04-08 01:00 +0200
      Re: sched: horrible way to detect whether a task has been preempted Jessica Yu <jeyu@redhat.com> - 2016-04-08 01:20 +0200
        Re: sched: horrible way to detect whether a task has been  preempted Jiri Kosina <jikos@kernel.org> - 2016-04-08 09:10 +0200
          Re: sched: horrible way to detect whether a task has been preempted Petr Mladek <pmladek@suse.com> - 2016-04-08 10:10 +0200
            Re: sched: horrible way to detect whether a task has been preempted Josh Poimboeuf <jpoimboe@redhat.com> - 2016-04-08 16:40 +0200
              Re: sched: horrible way to detect whether a task has been preempted Petr Mladek <pmladek@suse.com> - 2016-04-11 10:40 +0200

#1373783 — Re: sched: horrible way to detect whether a task has been preempted

+++ Josh Poimboeuf [25/03/16 14:34 -0500]:
>This is a horrible way to detect whether a task has been preempted.
>Come up with something better: task flag?  or is there already an
>existing mechanism?
>
>Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
>---
> include/linux/sched.h | 11 ++++++++++-
> kernel/sched/core.c   | 26 ++++++++++++++++++++++++--
> 2 files changed, 34 insertions(+), 3 deletions(-)
>
>diff --git a/include/linux/sched.h b/include/linux/sched.h
>index 589c478..62d0961 100644
>--- a/include/linux/sched.h
>+++ b/include/linux/sched.h
>@@ -3239,4 +3239,13 @@ struct update_util_data {
> void cpufreq_set_update_util_data(int cpu, struct update_util_data *data);
> #endif /* CONFIG_CPU_FREQ */
>
>-#endif
>+#ifdef CONFIG_PREEMPT
>+extern bool in_preempt_schedule_irq(unsigned long addr);
>+#else
>+static inline bool in_preempt_schedule_irq(unsigned long addr)
>+{
>+	return false;
>+}
>+#endif /* CONFIG_PREEMPT */
>+
>+#endif /* _LINUX_SCHED_H */
>diff --git a/kernel/sched/core.c b/kernel/sched/core.c
>index d8465ee..be1ef22 100644
>--- a/kernel/sched/core.c
>+++ b/kernel/sched/core.c
>@@ -3334,8 +3334,6 @@ asmlinkage __visible void __sched notrace preempt_schedule_notrace(void)
> }
> EXPORT_SYMBOL_GPL(preempt_schedule_notrace);
>
>-#endif /* CONFIG_PREEMPT */
>-
> /*
>  * this is the entry point to schedule() from kernel preemption
>  * off of irq context.
>@@ -3360,8 +3358,32 @@ asmlinkage __visible void __sched preempt_schedule_irq(void)
> 	} while (need_resched());
>
> 	exception_exit(prev_state);
>+
>+	asm("preempt_schedule_irq_end:");
> }
>
>+/*
>+ * in_preempt_schedule_irq - determine if instruction address is inside the
>+ *			     preempt_schedule_irq() function
>+ *
>+ * This is used when walking the stack of a task to determine whether an
>+ * interrupt frame exists.
>+ *
>+ * NOTE: This function could return false if the address is in the function
>+ * epilogue.  But it's good enough for our purposes, because we only care about
>+ * addresses which have been saved on a stack.  If preempt_schedule_irq() is on
>+ * the stack of a task, the saved address will always be prior to the epilogue.
>+ */
>+bool in_preempt_schedule_irq(unsigned long addr)
>+{
>+	extern void *preempt_schedule_irq_end;
>+
>+	return (addr >= (unsigned long)preempt_schedule_irq &&
>+		addr <  (unsigned long)preempt_schedule_irq_end);
>+}
>+
>+#endif /* CONFIG_PREEMPT */
>+
> int default_wake_function(wait_queue_t *curr, unsigned mode, int wake_flags,
> 			  void *key)
> {

Been sort of rattling my head over the scheduler code :-) Just
following the calls in and out of __schedule() it doesn't look like
there is a current flag/mechanism to tell whether or not a task has
been preempted..

Is there any reason why you didn't just create a new task flag,
something like TIF_PREEMPTED_IRQ, which would be set once
preempt_schedule_irq() is entered and unset after __schedule() returns
(for that task)? This would roughly correspond to setting the task
flag when the frame for preempt_schedule_irq() is pushed and unsetting
it just before the frame preempt_schedule_irq() is popped for that
task. This seems simpler than walking through all the frames just to
see if in_preempt_schedule_irq() had been called. Would that work? 

Jessica

[toc] | [next] | [standalone]

#1373793 — Re: sched: horrible way to detect whether a task has been preempted

On Thu, 7 Apr 2016, Jessica Yu wrote:

> Been sort of rattling my head over the scheduler code :-) Just following 
> the calls in and out of __schedule() it doesn't look like there is a 
> current flag/mechanism to tell whether or not a task has been 
> preempted..

Performing the complete stack unwind just to determine whether task has 
been preempted non-volutarily is a slight overkill indeed :/

> Is there any reason why you didn't just create a new task flag, 
> something like TIF_PREEMPTED_IRQ, which would be set once 
> preempt_schedule_irq() is entered and unset after __schedule() returns 
> (for that task)? This would roughly correspond to setting the task flag 
> when the frame for preempt_schedule_irq() is pushed and unsetting it 
> just before the frame preempt_schedule_irq() is popped for that task. 
> This seems simpler than walking through all the frames just to see if 
> in_preempt_schedule_irq() had been called. Would that work?

Alternatively, without eating up a TIF_ space, it'd be possible to push a 
magic contents on top of the stack in preempt_schedule_irq() (and pop it 
once we are returning from there), and if such magic value is detected, we 
just don't bother and claim unreliability.

That has advantages of both aproaches combined, i.e. it's relatively 
low-cost in terms of performance penalty, and it's reliable (in a sense 
that you don't have false positives).

The small disadvantage is that you can (very rarely, depending on the 
chosen magic) have false negatives. That probably doesn't hurt too much, 
given the high inprobability and non-lethal consequences.

How does that sound?

-- 
Jiri Kosina
SUSE Labs

[toc] | [prev] | [next] | [standalone]

#1373821

On Thu, Apr 07, 2016 at 11:37:19PM +0200, Jiri Kosina wrote:
> On Thu, 7 Apr 2016, Jessica Yu wrote:
> 
> > Been sort of rattling my head over the scheduler code :-) Just following 
> > the calls in and out of __schedule() it doesn't look like there is a 
> > current flag/mechanism to tell whether or not a task has been 
> > preempted..
> 
> Performing the complete stack unwind just to determine whether task has 
> been preempted non-volutarily is a slight overkill indeed :/
> 
> > Is there any reason why you didn't just create a new task flag, 
> > something like TIF_PREEMPTED_IRQ, which would be set once 
> > preempt_schedule_irq() is entered and unset after __schedule() returns 
> > (for that task)? This would roughly correspond to setting the task flag 
> > when the frame for preempt_schedule_irq() is pushed and unsetting it 
> > just before the frame preempt_schedule_irq() is popped for that task. 
> > This seems simpler than walking through all the frames just to see if 
> > in_preempt_schedule_irq() had been called. Would that work?
> 
> Alternatively, without eating up a TIF_ space, it'd be possible to push a 
> magic contents on top of the stack in preempt_schedule_irq() (and pop it 
> once we are returning from there), and if such magic value is detected, we 
> just don't bother and claim unreliability.
> 
> That has advantages of both aproaches combined, i.e. it's relatively 
> low-cost in terms of performance penalty, and it's reliable (in a sense 
> that you don't have false positives).
> 
> The small disadvantage is that you can (very rarely, depending on the 
> chosen magic) have false negatives. That probably doesn't hurt too much, 
> given the high inprobability and non-lethal consequences.
> 
> How does that sound?

To do that from C code, I guess we'd still need some arch-specific code
in an asm() statement to do the actual push?

I think I'd prefer just updating some field in the task_struct.  That
way it would be simple and arch-independent.  And the stack walker
wouldn't have to scan for some special value on the stack.

-- 
Josh

[toc] | [prev] | [next] | [standalone]

#1373823 — Re: sched: horrible way to detect whether a task has been preempted

On Thu, 7 Apr 2016, Josh Poimboeuf wrote:

> To do that from C code, I guess we'd still need some arch-specific code
> in an asm() statement to do the actual push?

This could potentially be worked around I believe (thinking for example of 
a onstack-allocated local variable with predefined contents that the 
compiler would not be allowed to optimize out; certainly not the only 
option).

Thanks,

-- 
Jiri Kosina
SUSE Labs

[toc] | [prev] | [next] | [standalone]

#1373827

+++ Jiri Kosina [07/04/16 23:37 +0200]:
>On Thu, 7 Apr 2016, Jessica Yu wrote:
>
>> Been sort of rattling my head over the scheduler code :-) Just following
>> the calls in and out of __schedule() it doesn't look like there is a
>> current flag/mechanism to tell whether or not a task has been
>> preempted..
>
>Performing the complete stack unwind just to determine whether task has
>been preempted non-volutarily is a slight overkill indeed :/
>
>> Is there any reason why you didn't just create a new task flag,
>> something like TIF_PREEMPTED_IRQ, which would be set once
>> preempt_schedule_irq() is entered and unset after __schedule() returns
>> (for that task)? This would roughly correspond to setting the task flag
>> when the frame for preempt_schedule_irq() is pushed and unsetting it
>> just before the frame preempt_schedule_irq() is popped for that task.
>> This seems simpler than walking through all the frames just to see if
>> in_preempt_schedule_irq() had been called. Would that work?
>
>Alternatively, without eating up a TIF_ space, it'd be possible to push a
>magic contents on top of the stack in preempt_schedule_irq() (and pop it
>once we are returning from there), and if such magic value is detected, we
>just don't bother and claim unreliability.

Ah, but wouldn't we still have to walk through the frames (i.e. enter
the loop in patch 7/14) to look for the magic value in this approach?

>That has advantages of both aproaches combined, i.e. it's relatively
>low-cost in terms of performance penalty, and it's reliable (in a sense
>that you don't have false positives).
>
>The small disadvantage is that you can (very rarely, depending on the
>chosen magic) have false negatives. That probably doesn't hurt too much,
>given the high inprobability and non-lethal consequences.
>
>How does that sound?
>
>-- 
>Jiri Kosina
>SUSE Labs
>

[toc] | [prev] | [next] | [standalone]

#1374028 — Re: sched: horrible way to detect whether a task has been preempted

On Thu, 7 Apr 2016, Jessica Yu wrote:

> > Alternatively, without eating up a TIF_ space, it'd be possible to push a
> > magic contents on top of the stack in preempt_schedule_irq() (and pop it
> > once we are returning from there), and if such magic value is detected, we
> > just don't bother and claim unreliability.
> 
> Ah, but wouldn't we still have to walk through the frames (i.e. enter
> the loop in patch 7/14) to look for the magic value in this approach?

The idea was that it'd be located at a place to which saved stack pointer 
of the sleeping task is pointing to (or at a fixed offset from it).

-- 
Jiri Kosina
SUSE Labs

[toc] | [prev] | [next] | [standalone]

#1374064

On Fri 2016-04-08 09:05:28, Jiri Kosina wrote:
> On Thu, 7 Apr 2016, Jessica Yu wrote:
> 
> > > Alternatively, without eating up a TIF_ space, it'd be possible to push a
> > > magic contents on top of the stack in preempt_schedule_irq() (and pop it
> > > once we are returning from there), and if such magic value is detected, we
> > > just don't bother and claim unreliability.
> > 
> > Ah, but wouldn't we still have to walk through the frames (i.e. enter
> > the loop in patch 7/14) to look for the magic value in this approach?
> 
> The idea was that it'd be located at a place to which saved stack pointer 
> of the sleeping task is pointing to (or at a fixed offset from it).

It is an interesting idea but it looks even more hacky than checking
the frame pointers and return values.

Checking the stack might be an overkill but we already do this for all
the other patched functions.

The big advantage about checking the stack is that it does not add
any overhead to the scheduler code, does not eat any TIF flag or
memory. The overhead is only when we are migrating a task and it is
charged to a separate process.

Best Regards,
Petr

[toc] | [prev] | [next] | [standalone]

#1374255

On Fri, Apr 08, 2016 at 10:03:04AM +0200, Petr Mladek wrote:
> On Fri 2016-04-08 09:05:28, Jiri Kosina wrote:
> > On Thu, 7 Apr 2016, Jessica Yu wrote:
> > 
> > > > Alternatively, without eating up a TIF_ space, it'd be possible to push a
> > > > magic contents on top of the stack in preempt_schedule_irq() (and pop it
> > > > once we are returning from there), and if such magic value is detected, we
> > > > just don't bother and claim unreliability.
> > > 
> > > Ah, but wouldn't we still have to walk through the frames (i.e. enter
> > > the loop in patch 7/14) to look for the magic value in this approach?
> > 
> > The idea was that it'd be located at a place to which saved stack pointer 
> > of the sleeping task is pointing to (or at a fixed offset from it).
> 
> It is an interesting idea but it looks even more hacky than checking
> the frame pointers and return values.
> 
> Checking the stack might be an overkill but we already do this for all
> the other patched functions.
> 
> The big advantage about checking the stack is that it does not add
> any overhead to the scheduler code, does not eat any TIF flag or
> memory. The overhead is only when we are migrating a task and it is
> charged to a separate process.

My biggest concern about checking the stack for preempt_schedule_irq()
is that it's kind of brittle:

- What if the preemption code changes such that it's no longer a
  reliable indicator?  For example, what if preempt_schedule_irq() is
  only called in some places, and a new __preempt_schedule_irq() is
  called elsewhere?

- Or due to some obscure gcc optimization like partial inlining or
  sibling tail calls, preempt_schedule_irq() doesn't show up on the
  stack?  

- Or the code could silently break if there were another static
  preempt_schedule_irq symbol somewhere (though we could prevent this by
  searching all symbols to ensure there are no duplicates).

These scenarios are unlikely, but they could conceivably happen...

Anyway, we really wouldn't have to eat a TIF flag.  We could instead add
something to task_struct.  I can at least propose it.  If anybody
doesn't like it, maybe they'll suggest something else, or maybe then we
can go with checking the stack.

-- 
Josh

[toc] | [prev] | [next] | [standalone]

#1375619

On Fri 2016-04-08 09:31:31, Josh Poimboeuf wrote:
> On Fri, Apr 08, 2016 at 10:03:04AM +0200, Petr Mladek wrote:
> > The big advantage about checking the stack is that it does not add
> > any overhead to the scheduler code, does not eat any TIF flag or
> > memory. The overhead is only when we are migrating a task and it is
> > charged to a separate process.
> 
> My biggest concern about checking the stack for preempt_schedule_irq()
> is that it's kind of brittle:
> 
> - What if the preemption code changes such that it's no longer a
>   reliable indicator?  For example, what if preempt_schedule_irq() is
>   only called in some places, and a new __preempt_schedule_irq() is
>   called elsewhere?
> 
> - Or due to some obscure gcc optimization like partial inlining or
>   sibling tail calls, preempt_schedule_irq() doesn't show up on the
>   stack?  
> 
> - Or the code could silently break if there were another static
>   preempt_schedule_irq symbol somewhere (though we could prevent this by
>   searching all symbols to ensure there are no duplicates).
> 
> These scenarios are unlikely, but they could conceivably happen...

You are right.

> Anyway, we really wouldn't have to eat a TIF flag.  We could instead add
> something to task_struct.  I can at least propose it.  If anybody
> doesn't like it, maybe they'll suggest something else, or maybe then we
> can go with checking the stack.

Yup, we should give the extra task struct stuff a try. Another
advantage is that it would be easier to port for another
architectures.

Best Regards,
Petr

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web