Skip to main content

Browse the archive

Revision 6e2df0581f569038719cf2bc2b3baa3fcc83cab4 authored by Peter Zijlstra on 08 November 2019, 10:11:52 UTC, committed by Peter Zijlstra on 08 November 2019, 21:34:14 UTC 
sched: Fix pick_next_task() vs 'change' pattern race
 
Commit 67692435c411 ("sched: Rework pick_next_task() slow-path")
inadvertly introduced a race because it changed a previously
unexplored dependency between dropping the rq->lock and
sched_class::put_prev_task().

The comments about dropping rq->lock, in for example
newidle_balance(), only mentions the task being current and ->on_cpu
being set. But when we look at the 'change' pattern (in for example
sched_setnuma()):

	queued = task_on_rq_queued(p); /* p->on_rq == TASK_ON_RQ_QUEUED */
	running = task_current(rq, p); /* rq->curr == p */

	if (queued)
		dequeue_task(...);
	if (running)
		put_prev_task(...);

	/* change task properties */

	if (queued)
		enqueue_task(...);
	if (running)
		set_next_task(...);

It becomes obvious that if we do this after put_prev_task() has
already been called on @p, things go sideways. This is exactly what
the commit in question allows to happen when it does:

	prev->sched_class->put_prev_task(rq, prev, rf);
	if (!rq->nr_running)
		newidle_balance(rq, rf);

The newidle_balance() call will drop rq->lock after we've called
put_prev_task() and that allows the above 'change' pattern to
interleave and mess up the state.

Furthermore, it turns out we lost the RT-pull when we put the last DL
task.

Fix both problems by extracting the balancing from put_prev_task() and
doing a multi-class balance() pass before put_prev_task().

Fixes: 67692435c411 ("sched: Rework pick_next_task() slow-path")
Reported-by: Quentin Perret <qperret@google.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Tested-by: Quentin Perret <qperret@google.com>
Tested-by: Valentin Schneider <valentin.schneider@arm.com>
1 parent e3b8b6a
Raw File
ubsan.rst 
The Undefined Behavior Sanitizer - UBSAN
========================================

UBSAN is a runtime undefined behaviour checker.

UBSAN uses compile-time instrumentation to catch undefined behavior (UB).
Compiler inserts code that perform certain kinds of checks before operations
that may cause UB. If check fails (i.e. UB detected) __ubsan_handle_*
function called to print error message.

GCC has that feature since 4.9.x [1_] (see ``-fsanitize=undefined`` option and
its suboptions). GCC 5.x has more checkers implemented [2_].

Report example
--------------

::

	 ================================================================================
	 UBSAN: Undefined behaviour in ../include/linux/bitops.h:110:33
	 shift exponent 32 is to large for 32-bit type 'unsigned int'
	 CPU: 0 PID: 0 Comm: swapper Not tainted 4.4.0-rc1+ #26
	  0000000000000000 ffffffff82403cc8 ffffffff815e6cd6 0000000000000001
	  ffffffff82403cf8 ffffffff82403ce0 ffffffff8163a5ed 0000000000000020
	  ffffffff82403d78 ffffffff8163ac2b ffffffff815f0001 0000000000000002
	 Call Trace:
	  [<ffffffff815e6cd6>] dump_stack+0x45/0x5f
	  [<ffffffff8163a5ed>] ubsan_epilogue+0xd/0x40
	  [<ffffffff8163ac2b>] __ubsan_handle_shift_out_of_bounds+0xeb/0x130
	  [<ffffffff815f0001>] ? radix_tree_gang_lookup_slot+0x51/0x150
	  [<ffffffff8173c586>] _mix_pool_bytes+0x1e6/0x480
	  [<ffffffff83105653>] ? dmi_walk_early+0x48/0x5c
	  [<ffffffff8173c881>] add_device_randomness+0x61/0x130
	  [<ffffffff83105b35>] ? dmi_save_one_device+0xaa/0xaa
	  [<ffffffff83105653>] dmi_walk_early+0x48/0x5c
	  [<ffffffff831066ae>] dmi_scan_machine+0x278/0x4b4
	  [<ffffffff8111d58a>] ? vprintk_default+0x1a/0x20
	  [<ffffffff830ad120>] ? early_idt_handler_array+0x120/0x120
	  [<ffffffff830b2240>] setup_arch+0x405/0xc2c
	  [<ffffffff830ad120>] ? early_idt_handler_array+0x120/0x120
	  [<ffffffff830ae053>] start_kernel+0x83/0x49a
	  [<ffffffff830ad120>] ? early_idt_handler_array+0x120/0x120
	  [<ffffffff830ad386>] x86_64_start_reservations+0x2a/0x2c
	  [<ffffffff830ad4f3>] x86_64_start_kernel+0x16b/0x17a
	 ================================================================================

Usage
-----

To enable UBSAN configure kernel with::

	CONFIG_UBSAN=y

and to check the entire kernel::

        CONFIG_UBSAN_SANITIZE_ALL=y

To enable instrumentation for specific files or directories, add a line
similar to the following to the respective kernel Makefile:

- For a single file (e.g. main.o)::

    UBSAN_SANITIZE_main.o := y

- For all files in one directory::

    UBSAN_SANITIZE := y

To exclude files from being instrumented even if
``CONFIG_UBSAN_SANITIZE_ALL=y``, use::

  UBSAN_SANITIZE_main.o := n

and::

  UBSAN_SANITIZE := n

Detection of unaligned accesses controlled through the separate option -
CONFIG_UBSAN_ALIGNMENT. It's off by default on architectures that support
unaligned accesses (CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS=y). One could
still enable it in config, just note that it will produce a lot of UBSAN
reports.

References
----------

.. _1: https://gcc.gnu.org/onlinedocs/gcc-4.9.0/gcc/Debugging-Options.html
.. _2: https://gcc.gnu.org/onlinedocs/gcc/Debugging-Options.html
back to top