27 february, 2010
-----BEGIN PGP SIGNED MESSAGE-----Hash: SHA1
=============================================================================
FreeBSD-EN-10:02.sched_ule Errata Notice
The FreeBSD Project
Topic: Deadlock in ULE scheduler
Category: core
Module: kern
Announced: 2010-02-27
Credits: Attilio Rao
Affects: FreeBSD 7.0, 7.1, and 7.2.
Corrected: 2009-09-24 09:08:22 UTC (RELENG_7, 7.2-STABLE)
2010-02-27 10:55:43 UTC (RELENG_7_2, 7.2-RELEASE-p7)
2010-02-27 10:55:43 UTC (RELENG_7_1, 7.1-RELEASE-p11)
For general information regarding FreeBSD Errata Notices and Security
Advisories, including descriptions of the fields above, security
branches, and the following sections, please visit
.
I. Background
FreeBSD has two schedulers: the classic 4BSD scheduler and a newer,
more SMP-aware scheduler called ULE. The 4BSD scheduler was the
default scheduler until FreeBSD 7.0. Starting with FreeBSD 7.1 the
default scheduler is ULE.
The scheduler is responsible for allocating CPU time to threads and
assigning threads to CPUs. Runnable threads (i.e. threads which are
not waiting for a blocking operation, such as an I/O operation, memory
allocation or lock acquisition, to complete) are assigned to a CPU and
placed in that CPU's run queue. Each thread and each CPU's run queue
is protected by a separate lock.
II. Problem Description
When a thread is reassigned from one CPU to another, the scheduler
first acquires the thread's lock, then releases the source CPU's run
queue lock. The scheduler then acquires the target CPU's run queue
lock and holds the lock while it adds the thread to the queue and signals
the target CPU. Finally it reacquires the source CPU's run queue lock
before unlocking the thread. A thread on the target CPU, having been
notified of the reassigned thread's arrival on the target CPU's run
queue, will then acquire the thread's lock before switching it in.
If, at the same time, a third thread tries to acquire both the source
and target CPUs' run queue locks, a three-way deadlock may occur:
- The second thread has acquired the target CPU's run queue lock, but
has not yet acquired the first thread's lock.
- The third thread has acquired the source CPU's run queue lock, and
is waiting to acquire the target CPU's run queue lock, which is
locked by the second thread.
- The first thread is waiting to acquire the source CPU's run queue
lock, which is held by the third thread, in order to release its
own lock.
As a result both CPUs' run queues are locked, and each of the three
threads is waiting to acquire a lock held by one of the others.
Eventually every CPU in the system ends up in a state where it is
waiting to acquire each other's locks.
It has not been determined whether this also affects single-CPU
systems but it is recommended this Errata Notice be applied to
single-CPU systems as well.
III. Impact
Affected systems may become deadlocked and require power-cycling. The
chance of a deadlock occurring increases with the number of CPUs.
There may be other aggravating factors such as running powerd(8). But
eventually any multi-processor system using the ULE scheduler will
become deadlocked.
IV. Workaround
Replace SCHED_ULE with SCHED_4BSD in your kernel configuration,
recompile your kernel and reboot the system.
Note that systems running the 4BSD scheduler are not affected; to
determine what scheduler a system is using, run
# sysctl kern.sched.name
V. Solution
Perform one of the following:
1) Upgrade your system to 7-STABLE, or to the RELENG_7_2 or RELENG_7_1
security branch dated after the correction date.
2) To patch your present system:
The following patches have been verified to apply to FreeBSD 7.1 and
7.2 systems.
a) Download the relevant patch from the location below, and verify the
detached PGP signature using your PGP utility.
# fetch http://security.FreeBSD.org/patches/EN-10:02/sched_ule.patch
# fetch http://security.FreeBSD.org/patches/EN-10:02/sched_ule.patch.asc
b) Apply the patch.
# cd /usr/src
# patch < /path/to/patch
c) Recompile your kernel as described in
and reboot the
system.
VI. Correction details
The following list contains the revision numbers of each file that was
corrected in FreeBSD.
CVS:
Branch Revision
Path
- -------------------------------------------------------------------------
RELENG_7
src/sys/kern/sched_ule.c 1.214.2.9
RELENG_7_2
src/UPDATING 1.507.2.23.2.10
src/sys/conf/newvers.sh 1.72.2.11.2.11
src/sys/kern/sched_ule.c 1.214.2.8.2.2
RELENG_7_1
src/UPDATING 1.507.2.13.2.14
src/sys/conf/newvers.sh 1.72.2.9.2.15
src/sys/kern/sched_ule.c 1.214.2.7.2.2
Subversion:
Branch/path Revision
- -------------------------------------------------------------------------
stable/7/ r197453
releng/7.2/ r204409
releng/7.1/ r204409
- -------------------------------------------------------------------------
VII. References
The latest revision of this advisory is available at
http://security.FreeBSD.org/advisories/FreeBSD-EN-10:02.sched_ule.asc
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (FreeBSD)
iEYEARECAAYFAkuI+1oACgkQFdaIBMps37ItgACghSdnagnmy9Zohrh5IKuhygiy
kVsAn2EXtts/l+IrjuWIzODSSUzLylia
=mj/v
-----END PGP SIGNATURE-----