In the forthcoming task migration support, a key calculation will be
mapping cpu and node numbers from the old set to the new set while
preserving cpuset-relative offset.

For example, if a task and its pages on nodes 8-11 are being migrated to
nodes 24-27, then pages on node 9 (the 2nd node in the old set) should be
moved to node 25 (the 2nd node in the new set.)

As with other bitmap operations, the proper way to code this is to provide
the underlying calculation in lib/bitmap.c, and then to provide the usual
cpumask and nodemask wrappers.

This patch provides that.  These operations are termed 'remap' operations.
Both remapping a single bit and a set of bits is supported.
Signed-off-by: NPaul Jackson <pj@sgi.com>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

Cleanup trailing whitespace, blank lines, CodingStyle issues etc, for
lib/idr.c
Signed-off-by: NJesper Juhl <jesper.juhl@gmail.com>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

The first two hunks of the patch really belongs in patch 1, but I missed
them on the first pass and instead of redoing all 3 patches I stuck them in
this one.
Signed-off-by: NJesper Juhl <jesper.juhl@gmail.com>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

Removes a few pointless register keywords.  register is merely a compiler
hint that access to the variable should be optimized, but gcc (3.3.6 in my
case) generates the exact same code with and without the keyword, and even
if gcc did something different with register present I think it is doubtful
we would want to optimize access to these variables - especially since this
is generic library code and there are supposed to be optimized versions in
asm/ for anything that really matters speed wise.

(akpm: iirc, keyword register is a gcc no-op unless using -O0)
Signed-off-by: NJesper Juhl <jesper.juhl@gmail.com>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

Removes some blank lines, removes some trailing whitespace, adds spaces
after commas and a few similar changes.
Signed-off-by: NJesper Juhl <jesper.juhl@gmail.com>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

Add CONFIG_X86_32 for i386.  This allows selecting options that only apply
to 32-bit systems.

(X86 && !X86_64) becomes X86_32
(X86 ||  X86_64) becomes X86
Signed-off-by: NBrian Gerst <bgerst@didntduck.org>
Cc: Sam Ravnborg <sam@ravnborg.org>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

This patch changes trough to through in a comment in kobject_uevent.c.
Signed-off-by: NGreg Kroah-Hartman <gregkh@suse.de>

Signed-off-by: NAl Viro <viro@zeniv.linux.org.uk>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

Fix a bug which was reported and diagnosed by
Stefan Jones <stefan.jones@churchillrandoms.co.uk>

IDR trees include a cache of idr_layer objects.  There's no way to destroy
this cache, so when we discard an overall idr tree we end up leaking some
memory.

Add and use idr_destroy() for this.  v9fs and infiniband also need to use
idr_destroy() to avoid leaks.

Or, we make the cache global, like radix_tree_preload().  Which is probably
better.  Later.

Cc: Eric Van Hensbergen <ericvh@ericvh.myip.org>
Cc: Roland Dreier <rolandd@cisco.com>
Cc: Robert Love <rml@novell.com>
Cc: John McCutchan <ttb@tentacle.dhs.org>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

This still leaves driver and architecture-specific subdirectories alone,
but gets rid of the bulk of the "generic" generated files that we should
ignore.
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

 - added typedef unsigned int __nocast gfp_t;

 - replaced __nocast uses for gfp flags with gfp_t - it gives exactly
   the same warnings as far as sparse is concerned, doesn't change
   generated code (from gcc point of view we replaced unsigned int with
   typedef) and documents what's going on far better.
Signed-off-by: NAl Viro <viro@zeniv.linux.org.uk>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

Fix nocast sparse warnings:
include/linux/textsearch.h:165:57: warning: implicit cast to nocast type
Signed-off-by: NRandy Dunlap <rdunlap@xenotime.net>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

Several implementations were essentialy a common piece of C code using
the cmpxchg() macro.  Put the implementation in one spot that everyone
can share, and convert sparc64 over to using this.

Alpha is the lone arch-specific implementation, which codes up a
special fast path for the common case in order to avoid GP reloading
which a pure C version would require.
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

Allow frame pointer and fix help text.
Signed-off-by: NAndi Kleen <ak@suse.de>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

This patch contains the following small cleanups:
- make two needlessly global functions static
- every file should #include the header files containing the prototypes
  of it's global functions
Signed-off-by: NAdrian Bunk <bunk@stusta.de>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

Fix the sparse warning "implicit cast to nocast type"
Signed-off-by: NVictor Fusco <victor@cetuc.puc-rio.br>
Signed-off-by: NDomen Puncer <domen@coderock.org>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

This patch (written by me and also containing many suggestions of Arjan van
de Ven) does a major cleanup of the spinlock code.  It does the following
things:

 - consolidates and enhances the spinlock/rwlock debugging code

 - simplifies the asm/spinlock.h files

 - encapsulates the raw spinlock type and moves generic spinlock
   features (such as ->break_lock) into the generic code.

 - cleans up the spinlock code hierarchy to get rid of the spaghetti.

Most notably there's now only a single variant of the debugging code,
located in lib/spinlock_debug.c.  (previously we had one SMP debugging
variant per architecture, plus a separate generic one for UP builds)

Also, i've enhanced the rwlock debugging facility, it will now track
write-owners.  There is new spinlock-owner/CPU-tracking on SMP builds too.
All locks have lockup detection now, which will work for both soft and hard
spin/rwlock lockups.

The arch-level include files now only contain the minimally necessary
subset of the spinlock code - all the rest that can be generalized now
lives in the generic headers:

 include/asm-i386/spinlock_types.h       |   16
 include/asm-x86_64/spinlock_types.h     |   16

I have also split up the various spinlock variants into separate files,
making it easier to see which does what. The new layout is:

   SMP                         |  UP
   ----------------------------|-----------------------------------
   asm/spinlock_types_smp.h    |  linux/spinlock_types_up.h
   linux/spinlock_types.h      |  linux/spinlock_types.h
   asm/spinlock_smp.h          |  linux/spinlock_up.h
   linux/spinlock_api_smp.h    |  linux/spinlock_api_up.h
   linux/spinlock.h            |  linux/spinlock.h

/*
 * here's the role of the various spinlock/rwlock related include files:
 *
 * on SMP builds:
 *
 *  asm/spinlock_types.h: contains the raw_spinlock_t/raw_rwlock_t and the
 *                        initializers
 *
 *  linux/spinlock_types.h:
 *                        defines the generic type and initializers
 *
 *  asm/spinlock.h:       contains the __raw_spin_*()/etc. lowlevel
 *                        implementations, mostly inline assembly code
 *
 *   (also included on UP-debug builds:)
 *
 *  linux/spinlock_api_smp.h:
 *                        contains the prototypes for the _spin_*() APIs.
 *
 *  linux/spinlock.h:     builds the final spin_*() APIs.
 *
 * on UP builds:
 *
 *  linux/spinlock_type_up.h:
 *                        contains the generic, simplified UP spinlock type.
 *                        (which is an empty structure on non-debug builds)
 *
 *  linux/spinlock_types.h:
 *                        defines the generic type and initializers
 *
 *  linux/spinlock_up.h:
 *                        contains the __raw_spin_*()/etc. version of UP
 *                        builds. (which are NOPs on non-debug, non-preempt
 *                        builds)
 *
 *   (included on UP-non-debug builds:)
 *
 *  linux/spinlock_api_up.h:
 *                        builds the _spin_*() APIs.
 *
 *  linux/spinlock.h:     builds the final spin_*() APIs.
 */

All SMP and UP architectures are converted by this patch.

arm, i386, ia64, ppc, ppc64, s390/s390x, x64 was build-tested via
crosscompilers.  m32r, mips, sh, sparc, have not been tested yet, but should
be mostly fine.

From: Grant Grundler <grundler@parisc-linux.org>

  Booted and lightly tested on a500-44 (64-bit, SMP kernel, dual CPU).
  Builds 32-bit SMP kernel (not booted or tested).  I did not try to build
  non-SMP kernels.  That should be trivial to fix up later if necessary.

  I converted bit ops atomic_hash lock to raw_spinlock_t.  Doing so avoids
  some ugly nesting of linux/*.h and asm/*.h files.  Those particular locks
  are well tested and contained entirely inside arch specific code.  I do NOT
  expect any new issues to arise with them.

 If someone does ever need to use debug/metrics with them, then they will
  need to unravel this hairball between spinlocks, atomic ops, and bit ops
  that exist only because parisc has exactly one atomic instruction: LDCW
  (load and clear word).

From: "Luck, Tony" <tony.luck@intel.com>

   ia64 fix
Signed-off-by: NIngo Molnar <mingo@elte.hu>
Signed-off-by: NArjan van de Ven <arjanv@infradead.org>
Signed-off-by: NGrant Grundler <grundler@parisc-linux.org>
Cc: Matthew Wilcox <willy@debian.org>
Signed-off-by: NHirokazu Takata <takata@linux-m32r.org>
Signed-off-by: NMikael Pettersson <mikpe@csd.uu.se>
Signed-off-by: NBenoit Boissinot <benoit.boissinot@ens-lyon.org>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

Add the crc16 routines, as used by w1 devices.
Signed-off-by: NBen Gardner <bgardner@wabtec.com>
Signed-off-by: NEvgeniy Polyakov <johnpol@2ka.mipt.ru>
Signed-off-by: NGreg Kroah-Hartman <gregkh@suse.de>

The problem is that klists claim to provide semantics for safe traversal of
lists which are being modified.  The failure case is when traversal of a
list causes element removal (a fairly common case).  The issue is that
although the list node is refcounted, if it is embedded in an object (which
is universally the case), then the object will be freed regardless of the
klist refcount leading to slab corruption because the klist iterator refers
to the prior element to get the next.

The solution is to make the klist take and release references to the
embedding object meaning that the embedding object won't be released until
the list relinquishes the reference to it.

(akpm: fast-track this because it's needed for the 2.6.13 scsi merge)
Signed-off-by: NJames Bottomley <James.Bottomley@SteelEye.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@suse.de>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

Simple patch to radix_tree_tag_get() to return different values for non
present node and tag unset.

The function is not used by any in-kernel callers (yet), but this
information is definitely useful.
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

- There is frequent use of indirections in the radix code. This patch
  removes those indirections, makes the code more readable and allows
  the compilers to generate better code.

- Removing indirections allows the removal of several casts.

- Removing indirections allows the reduction of the radix_tree_path
  size from 3 to 2 words.

- Use pathp-> consistently.

- Remove unnecessary tmp variable in radix_tree_insert

- Separate the upper layer processing from the lowest layer in __lookup()
  in order to make it easier to understand what is going on and allow
  compilers to generate better code for the loop.
Signed-off-by: NChristoph Lameter <clameter@sgi.com>
Cc: Nick Piggin <nickpiggin@yahoo.com.au>
Cc: James Bottomley <James.Bottomley@steeleye.com>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

This patch adds a new kernel debug feature: CONFIG_DETECT_SOFTLOCKUP.

When enabled then per-CPU watchdog threads are started, which try to run
once per second.  If they get delayed for more than 10 seconds then a
callback from the timer interrupt detects this condition and prints out a
warning message and a stack dump (once per lockup incident).  The feature
is otherwise non-intrusive, it doesnt try to unlock the box in any way, it
only gets the debug info out, automatically, and on all CPUs affected by
the lockup.
Signed-off-by: NIngo Molnar <mingo@elte.hu>
Signed-off-by: NNishanth Aravamudan <nacc@us.ibm.com>
Signed-Off-By: NMatthias Urlichs <smurf@smurf.noris.de>
Signed-off-by: NRichard Purdie <rpurdie@rpsys.net>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

at the moment, the list_head semantics are

list_add(node, head)

whereas current klist semantics are

klist_add(head, node)

This is bound to cause confusion, and since klist is the newcomer, it
should follow the list_head semantics.

I also added missing include guards to klist.h
Signed-off-by: NJames Bottomley <James.Bottomley@SteelEye.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@suse.de>

This patch moves the common code in x86 and x86-64's semaphore.c into a
single file in lib/semaphore-sleepers.c.  The arch specific asm stubs are
left in the arch tree (in semaphore.c for i386 and in the asm for x86-64).
There should be no changes in code/functionality with this patch.
Signed-off-by: NBenjamin LaHaise <benjamin.c.lahaise@intel.com>
Cc: Andi Kleen <ak@muc.de>
Signed-off-by: NJeff Dike <jdike@addtoit.com>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

And select it when the relevant modules are enabled.
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

Attached the implementation of the Boyer-Moore string search
algorithm for the new textsearch infrastructure.

I've added as well a note about the limitations that this approach
presents, as Thomas has remarked.
Signed-off-by: NPablo Neira Ayuso <pablo@eurodev.net>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

Signed-off-by: NPatrick McHardy <kaber@trash.net>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

Signed-off-by: NPatrick McHardy <kaber@trash.net>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

netlink_broadcast users must initialize NETLINK_CB(skb).dst_groups to the
destination group mask for netlink_recvmsg.
Signed-off-by: NPatrick McHardy <kaber@trash.net>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

- Remove bogus code for compiling netlink as module
- Add module refcounting support for modules implementing a netlink
  protocol
- Add support for autoloading modules that implement a netlink protocol
  as soon as someone opens a socket for that protocol
Signed-off-by: NHarald Welte <laforge@netfilter.org>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

There is an off by one problem with idr_get_new_above.

The comment and function name suggest that it will return an id >
starting_id, but it actually returned an id >= starting_id, and kernel
callers other than inotify treated it as such.

The patch below fixes the comment, and fixes inotifys usage.  The
function name still doesn't match the behaviour, but it never did.
Signed-off-by: NJohn McCutchan <ttb@tentacle.dhs.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

handling of %t... (ptrdiff_t) in vsnprintf
Signed-off-by: NAl Viro <viro@parcelfarce.linux.theplanet.co.uk>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

It turns out that empty distance code tables are not an error, and that
a compressed block with only literals can validly have an empty table
and should not be flagged as a data error.

Some old versions of gzip had problems with this case, but it does not
affect the zlib code in the kernel.

Analysis and explanations thanks to Sergey Vlasov <vsu@altlinux.ru>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

This patch fixes a typo in lib/crc32.c which results in incorrect debug
output.
Signed-off-by: NDominik Hackl <dominik@hackl.dhs.org>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

These bugs have been fixed in the standard zlib for a while.

See for example

 a) http://sources.redhat.com/ml/bug-gnu-utils/1999-06/msg00183.html
 b) http://bugs.gentoo.org/show_bug.cgi?id=94584Signed-off-by: NTim Yamin <plasmaroo@gentoo.org>
Signed-off-by: NTavis Ormandy <taviso@gentoo.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

CONFIG_DEBUG_FS=y and CONFIG_SYSFS=n results in the following compile
error:

<--  snip  -->

...
  LD      vmlinux
fs/built-in.o: In function `debugfs_init':
inode.c:(.init.text+0x31be): undefined reference to `kernel_subsys'
make: *** [vmlinux] Error 1

<--  snip  -->
Signed-off-by: NAdrian Bunk <bunk@stusta.de>
Signed-off-by: NGreg Kroah-Hartman <gregkh@suse.de>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

For some reason halfmd4 isn't being linked into the kernel any more and
modular ext3 wants it.

So statically link the halfmd4 code into the kernel.
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

Add a new section called ".data.read_mostly" for data items that are read
frequently and rarely written to like cpumaps etc.

If these maps are placed in the .data section then these frequenly read
items may end up in cachelines with data is is frequently updated.  In that
case all processors in an SMP system must needlessly reload the cachelines
again and again containing elements of those frequently used variables.

The ability to share these cachelines will allow each cpu in an SMP system
to keep local copies of those shared cachelines thereby optimizing
performance.
Signed-off-by: NAlok N Kataria <alokk@calsoftinc.com>
Signed-off-by: NShobhit Dayal <shobhit@calsoftinc.com>
Signed-off-by: NChristoph Lameter <christoph@scalex86.org>
Signed-off-by: NShai Fultheim <shai@scalex86.org>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

This patch makes use of ALIGN() to remove duplicate round-up code.
Signed-off-by: NNick Wilson <njw@osdl.org>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

lib/sha1.c:44:10: warning: cast to restricted type
Signed-off-by: NAlexey Dobriyan <adobriyan@mail.ru>
Signed-off-by: NDomen Puncer <domen@coderock.org>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>