Dmitry Adamushko pointed out a known flaw in the rt-balancing algorithm
that could allow suboptimal balancing if a non-migratable task gets
queued behind a running migratable one.  It is discussed in this thread:

http://lkml.org/lkml/2008/4/22/296

This issue has been further exacerbated by a recent checkin to
sched-devel (git-id 5eee63a5ebc19a870ac40055c0be49457f3a89a3).

>From a pure priority standpoint, the run-queue is doing the "right"
thing. Using Dmitry's nomenclature, if T0 is on cpu1 first, and T1
wakes up at equal or lower priority (affined only to cpu1) later, it
*should* wait for T0 to finish.  However, in reality that is likely
suboptimal from a system perspective if there are other cores that
could allow T0 and T1 to run concurrently.  Since T1 can not migrate,
the only choice for higher concurrency is to try to move T0.  This is
not something we addessed in the recent rt-balancing re-work.

This patch tries to enhance the balancing algorithm by accomodating this
scenario.  It accomplishes this by incorporating the migratability of a
task into its priority calculation.  Within a numerical tsk->prio, a
non-migratable task is logically higher than a migratable one.  We
maintain this by introducing a new per-priority queue (xqueue, or
exclusive-queue) for holding non-migratable tasks.  The scheduler will
draw from the xqueue over the standard shared-queue (squeue) when
available.

There are several details for utilizing this properly.

1) During task-wake-up, we not only need to check if the priority
   preempts the current task, but we also need to check for this
   non-migratable condition.  Therefore, if a non-migratable task wakes
   up and sees an equal priority migratable task already running, it
   will attempt to preempt it *if* there is a likelyhood that the
   current task will find an immediate home.

2) Tasks only get this non-migratable "priority boost" on wake-up.  Any
   requeuing will result in the non-migratable task being queued to the
   end of the shared queue.  This is an attempt to prevent the system
   from being completely unfair to migratable tasks during things like
   SCHED_RR timeslicing.

I am sure this patch introduces potentially "odd" behavior if you
concoct a scenario where a bunch of non-migratable threads could starve
migratable ones given the right pattern.  I am not yet convinced that
this is a problem since we are talking about tasks of equal RT priority
anyway, and there never is much in the way of guarantees against
starvation under that scenario anyway. (e.g. you could come up with a
similar scenario with a specific timing environment verses an affinity
environment).  I can be convinced otherwise, but for now I think this is
"ok".
Signed-off-by: NGregory Haskins <ghaskins@novell.com>
CC: Dmitry Adamushko <dmitry.adamushko@gmail.com>
CC: Steven Rostedt <rostedt@goodmis.org>
Signed-off-by: NIngo Molnar <mingo@elte.hu>
Signed-off-by: NThomas Gleixner <tglx@linutronix.de>

* master.kernel.org:/home/rmk/linux-2.6-arm:
  [ARM] pxa: fix tosa.c build error
  [ARM] 5067/1: _raw_write_can_lock macro bugfix
  [ARM] 5070/1: pxa: add GPIO104_PSKTSEL to pxa27x MFP configuration
  [ARM] 5068/1: PXA2xx Additional gpio definitions
  [ARM] 5066/2: EM-X270: Fix DM9000 IRQ flags initialisation
  [ARM] 5065/2: CM-X270: Fix DM9000 IRQ flags initialisation
  [ARM] 5062/1: pxa: remove unused definition of CONFIG_ARCH_COTULLA_IDP
  [ARM] 5060/1: remove unnecessary include of asm/io.h
  [ARM] fix AT91 include loops

Fairly simple. "dev_use" was being allocated as a zero length array
because of bad math on 64-bit systems, causing a crash in
find_first_zero_bit(). One-liner follows:
Signed-off-by: NBen Collins <ben.collins@canonical.com>
Acked-by: NPierre Ossman <drzeus@drzeus.cx>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

* git://git.kernel.org/pub/scm/linux/kernel/git/mchehab/v4l-dvb: (48 commits)
  V4L/DVB (8001): dib0070: fix dib0070_attach when !CONFIG_DVB_TUNER_DIB0070
  V4L/DVB (8000): tda827x: fix NULL pointer in tda827xa_lna_gain
  V4L/DVB (7990): Fix entry for PowerColor RA 330 and make it run with firmware version 2.7
  V4L/DVB (7983): tda18271_calc_rf_cal must return the return value of tda18271_lookup_map
  V4L/DVB (7978): cx18: explicitly test for XC2028 tuner
  V4L/DVB (7977): cx18: fix init order and remove duplicate open_on_first_use.
  V4L/DVB (7975): saa7134_empress
  V4L/DVB (7974): fix MEDIA_TUNER && FW_LOADER build error
  V4L/DVB (7972): or51132.c: unaligned
  V4L/DVB (7971): usb: unaligned
  V4L/DVB (7970): mix trivial endianness annotations
  V4L/DVB (7969): m920x: unaligned access
  V4L/DVB (7968): zoran: endianness annotations
  V4L/DVB (7967): bt8xx: unaligned access
  V4L/DVB (7966): cx18: direct dereferencing of iomem
  V4L/DVB (7965): annotate bcx_riscmem
  V4L/DVB (7964): cx18 iomem annotations
  V4L/DVB (7963): ivtv: trivial annotations
  V4L/DVB (7962): ttusb endianness annotations and fixes
  V4L/DVB (7961): fix endianness bug in dib0700_devices.c
  ...

* 'upstream' of git://ftp.linux-mips.org/pub/scm/upstream-linus:
  Fix divide by zero error in build_clear_page() and build_copy_page()
  [MIPS] Fix typo in header guard
  [MIPS] Fix build error - Delete debugging crap that crept in with CMP
  [MIPS] Add accessors for random register.
  [MIPS] IP27: misc fixes
  [MIPS] IP27: Fix clockevent setup
  [MIPS] IP27: Fix bootmem memory setup
  [MIPS] remove CONFIG_CPU_R4000 line from Makefile
  [MIPS] Fix check for valid stack pointer during backtrace
  [MIPS] Add missing braces to pte_mkyoung
  [MIPS] R4700: Fix build_tlb_probe_entry
  [MIPS] Alchemy: dbdma: add API to delete custom DDMA device ids.
  [MIPS] Alchemy: export get_au1x00_speed for modules

* git://git.infradead.org/~dwmw2/mtd-2.6.26:
  [MTD] [MAPS] Fix cmdlineparse handling in mapping files
  [MTD] [NAND] pxa: fix incorrect calling of pxa3xx_nand_config() on resume path

Suggest how to deal with patch modifications caused by
merging or back-porting when you're a maintainer.
Signed-off-by: NWilly Tarreau <w@1wt.eu>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

- Don't trust a length which is greater than the working buffer.
  An invalid length could cause overflow when calculating buffer size
  for decoding oid.

- An oid length of zero is invalid and allows for an off-by-one error when
  decoding oid because the first subid actually encodes first 2 subids.

- A primitive encoding may not have an indefinite length.

Thanks to Wei Wang from McAfee for report.

Cc: Steven French <sfrench@us.ibm.com>
Cc: stable@kernel.org
Acked-by: NPatrick McHardy <kaber@trash.net>
Signed-off-by: NChris Wright <chrisw@sous-sol.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

Alias brd to rd in the hope of helping legacy users. Suggested by Jan.
Signed-off-by: NNick Piggin <npiggin@suse.de>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

Here is an attempt to translate the prompt and help text into something
which is legible and, as a bonus, correct.
Signed-off-by: NStefan Richter <stefanr@s5r6.in-berlin.de>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

ip_fast_csum() requires a memory clobber on its inline asm as it accesses
memory in a fashion that gcc can't predict.

The GCC manual says:

 If your assembler instructions access memory in an unpredictable
 fashion, add `memory' to the list of clobbered registers.  This will
 cause GCC to not keep memory values cached in registers across the
 assembler instruction and not optimize stores or loads to that memory.

The bug hasn't been noticed in FRV, but it has been seen in PA-RISC.
Signed-off-by: NDavid Howells <dhowells@redhat.com>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

We don't need to reserve "unset" resources.  Trying to reserve
them results in messages like this, which are ugly but harmless:

    system 00:08: iomem range 0x0-0x0 could not be reserved

Future PNP patches will remove use of IORESOURCE_UNSET, but
we still need it for now.
Signed-off-by: NBjorn Helgaas <bjorn.helgaas@hp.com>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

Signed-off-by: NYoichi Yuasa <yoichi_yuasa@tripeaks.co.jp>
Signed-off-by: NRalf Baechle <ralf@linux-mips.org>

Signed-off-by: NVegard Nossum <vegard.nossum@gmail.com>
Signed-off-by: NRalf Baechle <ralf@linux-mips.org>

Signed-off-by: NRalf Baechle <ralf@linux-mips.org>

Signed-off-by: NRalf Baechle <ralf@linux-mips.org>

- fix PCI interrupt assignment by emulating ioc3 interrupt pin register
- use pci_probe_only mode
- select correct page size in bridge
- remove no longer needed ioc3_sio_init() code

[Ralf: Fix for 64kB or larger pagesizes]
Signed-off-by: NThomas Bogendoerfer <tsbogend@alpha.franken.de>
Signed-off-by: NRalf Baechle <ralf@linux-mips.org>

Fix breakage introduced by converting hub_rt to clockevent.
Signed-off-by: NThomas Bogendoerfer <tsbogend@alpha.franken.de>
Signed-off-by: NRalf Baechle <ralf@linux-mips.org>

Changes in the generic bootmem code broke memory setup for IP27. This
patch fixes this by replacing lots of special IP27 code with generic
bootmon code. This has been tested only on a single node.
Signed-off-by: NThomas Bogendoerfer <tsbogend@alpha.franken.de>
Signed-off-by: NRalf Baechle <ralf@linux-mips.org>

The existing options are named CONFIG_CPU_R4300 and CONFIG_CPU_R4X00,
and they are directly below.
Reported-by: NRobert P. J. Day <rpjday@crashcourse.ca>
Signed-off-by: NAdrian Bunk <bunk@kernel.org>
Signed-off-by: NRalf Baechle <ralf@linux-mips.org>

The newly added check for valid stack pointer address breaks at least for
64bit kernels.  Use __get_user() for accessing stack content to avoid crashes,
when doing the backtrace.
Signed-off-by: NThomas Bogendoerfer <tsbogend@alpha.franken.de>
Signed-off-by: NRalf Baechle <ralf@linux-mips.org>

Only the version pte_mkyoung for 36-bit pagetables on 32-bit hw was
affected and with this bug being around since November 29, 2004 there
is evidence to suport the assumption it was benign ;-)
Signed-off-by: NIlpo Järvinen <ilpo.jarvinen@helsinki.fi>
Signed-off-by: NRalf Baechle <ralf@linux-mips.org>

Treat R4700 like R4600 in build_tlb_probe_entry. Without this fix kernel
will lock up.
Signed-off-by: NThomas Bogendoerfer <tsbogend@alpha.franken.de>
Signed-off-by: NRalf Baechle <ralf@linux-mips.org>

Add API to delete custom DDMA device ids create with
au1xxx_ddma_device_add().
Signed-off-by: NManuel Lauss <mano@roarinelk.homelinux.net>
Signed-off-by: NRalf Baechle <ralf@linux-mips.org>

au1xmmc.c driver depends on it, so export it for modules.
Signed-off-by: NManuel Lauss <mano@roarinelk.homelinux.net>
Signed-off-by: NRalf Baechle <ralf@linux-mips.org>

Fix G5 SATA irq 18: nobody cared, reported on -rc5 by Olaf Hering:
fixlet to a57c1bad libata-sff:
Fix oops reported in kerneloops.org for pnp devices with no ctl
Signed-off-by: NHugh Dickins <hugh@veritas.com>
Acked-by: NAlan Cox <alan@lxorguk.ukuu.org.uk>
Tested-by: NOlaf Hering <olaf@aepfle.de>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

Signed-off-by: NMichael Krufky <mkrufky@linuxtv.org>
Signed-off-by: NMauro Carvalho Chehab <mchehab@infradead.org>

Check that tda827x_config is defined before attempting to use it.
Signed-off-by: NSigmund Augdal <sigmund@snap.tv>
Signed-off-by: NMichael Krufky <mkrufky@linuxtv.org>
Signed-off-by: NMauro Carvalho Chehab <mchehab@infradead.org>

Signed-off-by: NDaniel Gimpelevich <daniel@gimpelevich.san-francisco.ca.us>
Signed-off-by: NMauro Carvalho Chehab <mchehab@infradead.org>

On the TDA18271HD/C1, we perform RF tracking filter correction for VHF low
band, only. If supplied a frequency out of range, the error must be returned
to the caller (tda18271c1_rf_tracking_filter_calibration) so that it can
decide whether or not to write to register EB14, RFC_CPROG[7:0]
Signed-off-by: NMichael Krufky <mkrufky@linuxtv.org>
Signed-off-by: NMauro Carvalho Chehab <mchehab@infradead.org>

Testing whether xceive_pin is non-zero is not good enough as 0 is a valid
value. Instead explicitly test whether the Xceive tuner is used.
Signed-off-by: NHans Verkuil <hverkuil@xs4all.nl>
Signed-off-by: NMauro Carvalho Chehab <mchehab@infradead.org>

Signed-off-by: NHans Verkuil <hverkuil@xs4all.nl>
Signed-off-by: NMauro Carvalho Chehab <mchehab@infradead.org>

This is patch for fix data structure in querycap syscall.
Signed-off-by: NBeholder Intl. Ltd. Dmitry Belimov <d.belimov@gmail.com>
Signed-off-by: NMauro Carvalho Chehab <mchehab@infradead.org>

-tip testing found the following build failure:

  LD      .tmp_vmlinux1
  drivers/built-in.o: In function `generic_set_freq':
  tuner-xc2028.c:(.text+0xbd896): undefined reference to `request_firmware'
  tuner-xc2028.c:(.text+0xbdd7a): undefined reference to `release_firmware'
  drivers/built-in.o: In function `xc_load_fw_and_init_tuner':
  xc5000.c:(.text+0xc68e6): undefined reference to `request_firmware'
  xc5000.c:(.text+0xc6abe): undefined reference to `release_firmware'

with this config:

  http://redhat.com/~mingo/misc/config-Tue_May_20_18_11_34_CEST_2008.bad

the reason is another kconfig tool bug that has to be worked around in
the driver's Kconfig file: if FW_LOADER is selected in a second
dependency, that is not properly propagated up the dependencies.

in this case, FW_LOADER is selected from MEDIA_TUNER_XC2028:

  config MEDIA_TUNER_XC2028
        tristate "XCeive xc2028/xc3028 tuners"
        depends on VIDEO_MEDIA && I2C
        depends on HOTPLUG
        select FW_LOADER

which got selected by MEDIA_TUNER:

  config MEDIA_TUNER
        tristate
        default VIDEO_MEDIA && I2C
        depends on VIDEO_MEDIA && I2C
        select FW_LOADER if !MEDIA_TUNER_CUSTOMIZE && HOTPLUG

but the kconfig tool did not pick up this second-order dependency and
allowed CONFIG_FW_LOADER=m to be selected - in which case the build
fails.

the workaround i found was to move the select of FW_LOADER one level up,
so that the buggy kconfig tool can notice it and can act appropriately.
This problem can probably be worked around in other ways as well, i went
for the minimal fix.

Obviously, the kconfig tool should be fixed, it is not reasonable to
expect driver authors to do manual dependency resolution (that kconfig
itself already does) and uglify the Kconfig files. The kconfig tool did
nothing to warn about this situation and did not prevent this faulty
.config from being constructed.
Signed-off-by: NIngo Molnar <mingo@elte.hu>
Signed-off-by: NMauro Carvalho Chehab <mchehab@infradead.org>

Signed-off-by: NAl Viro <viro@zeniv.linux.org.uk>
Signed-off-by: NMauro Carvalho Chehab <mchehab@infradead.org>

Signed-off-by: NAl Viro <viro@zeniv.linux.org.uk>
Signed-off-by: NMauro Carvalho Chehab <mchehab@infradead.org>

Signed-off-by: NAl Viro <viro@zeniv.linux.org.uk>
Signed-off-by: NMauro Carvalho Chehab <mchehab@infradead.org>

Signed-off-by: NAl Viro <viro@zeniv.linux.org.uk>
Signed-off-by: NMauro Carvalho Chehab <mchehab@infradead.org>

Signed-off-by: NAl Viro <viro@zeniv.linux.org.uk>
Signed-off-by: NMauro Carvalho Chehab <mchehab@infradead.org>

Signed-off-by: NAl Viro <viro@zeniv.linux.org.uk>
Signed-off-by: NMauro Carvalho Chehab <mchehab@infradead.org>