-----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
<URL:http://security.freebsd.org/>.

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
<URL:http://www.FreeBSD.org/handbook/kernelconfig.html> 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-----