Signed-off-by: Sam Ravnborg <sam@ravnborg.org>

As pointed by Thomas Sailer, crc16.c module contains CRC16-CCITT (x^16 + x^12
+ x^5 + 1) implementation, not IBM CRC16 (x^16 + x^15 + x^2 + 1) one.  Looks
like we need to rename it accordingly and this patchset does exactly this.
Signed-off-by: Andrey Panin <pazke@donpac.ru>
Signed-off-by: Andrew Morton <akpm@osdl.org>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>

Currently we have 8 copies of CRC16 calculation table in different device
drivers, this patch creates common crc16.c module to replace them.
Signed-off-by: Andrey Panin <pazke@donpac.ru>
Signed-off-by: Andrew Morton <akpm@osdl.org>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>

Based on the kobject structure, but much smaller and simpler to use.

From: Joe Korty <joe.korty@ccur.com>

1) the version in 2.6.1 is broken, doesn't work on 64bit big endian
   machines at all.  This needed fixing.  I thought it best to fix by
   rewriting the printer/parser with an algorithm that is naturally endian &
   sizeof(long) resistant.

2) I wanted all digits to print, eg, 0000ffff,00000004 not ffff,4.

3) I wanted exactly NR_CPUS bits to print (or whatever the bitmap size is
   in bits, and not have what is displayed rounded up to the nearest full
   byte, as the current version did.

4) The bitmap printer and parser should be part of bitmap.[ch] with syntax
   and semantics to match.  The original lib/mask.c versions did not
   recognize this commonality.

This patch arranges for the exception tables to be sorted on most
architectures.  It sorts the main kernel exception table on startup
and the module exception tables when they get loaded.  The main table
is sorted reasonably early - just after kmem_cache_init - but that
could be moved even earlier if necessary.

There is now a lib/extable.c which includes the sort_extable()
function from arch/ppc/mm/extable.c and the search_extable() function
from arch/i386/mm/extable.c, which had been copied to many
architectures.  On many architectures, arch/$(ARCH)/mm/extable.c
became empty and so I have removed it.

There are four architectures which do things differently from i386:
alpha, ia64, sparc and sparc64.  Alpha and ia64 store the offset from
the offset from the exception table entry to the instruction, and
sparc and sparc64 have range entries in the table.  For those
architectures I have added empty sort_extable functions.  The
maintainers for those architectures can implement something better if
they care to.  As it is they are no worse off than before.

Although it is a moderately sizable patch, it ends up with a net
reduction of 377 lines in the size of the kernel source. :)

I have tested this on x86 and ppc with a module that uses __get_user
in an init function, deliberately laid out to get the exception table
out of order, and it works (whereas it oopsed without this patch).

- A couple of them are using alloca (via DECLARE_BITMAP) and this generates
  a cannot-inline warning with -Winline.

- These functions are too big to inline anwyay.

From: Paul Jackson <pj@sgi.com>

This patch is a followup to one from Bill Irwin.  On Nov
17, he had consolidated the half-dozen chunks of code
that displayed cpumasks in /proc/irq/prof_cpu_mask and
/proc/irq/<pid>/smp_affinity into a single routine, which he
called format_cpumask().

I believe that Andrew Morton has accepted Bill's patch into
his 2.6.0-test10-mm1 patch set as the "format_cpumask" patch.
I hope that the following patch will replace Bill's patch.
I look forward to Bill's feedback on this patch.

The following patch carries Bill's work further:

 1) It also consolidates the input side (write syscalls).
 2) It adapts a new format, same on input and output.
 3) The core routines work for any multi-word bitmask,
    not just cpumasks.
 4) The core routines avoid overrunning their output
    buffers.

Note esp. for David Mosberger:

    The small patch I sent you and the linux-ia64 list
    yesterday entitled: "check user access ok writing
    /proc/irq/<pid>/smp_affinity" for arch ia64 only is
    _separate_ from the following patch.  Neither presumes the
    other.  However, they do collide on one line.  Last one in
    is a Monkey's Uncle and will need an updated patch from me
    (or otherwise need to resolve the one obvious collision).

Details of the following patch:

Both the display and input of cpumasks on 9 arch's are
consolidated into a single pair of routines, which use the
same format for input and output, as recommended by Tony
Luck.  The two common routines work on any multi-word bitmask
(array of unsigned longs).  A pair of trivial inline wrappers
cpumask_snprintf() and cpumask_parse() hide this generality
for the common case of cpumask input and output.

My real motivation for consolidating this code will become
visible later - when I seek to add a nodemask_t that resembles
cpumask_t (just a different length).  These common underlying
routines will be used there as well, following up on a suggestion
of Christoph Hellwig that I investigate implementing nodemask_t
as an ADT sharing infrastructure with cpumask_t.  However, I
believe that this patch stands on its own merit, consolidating
a couple hundred lines of duplicated code, and making the
cpumask display format usable on very large systems.

There are two exceptions to the consolidation - the alpha and
sparc64 arch's manipulate bare unsigned longs, not cpumask_t's,
on input (write syscall), and do stuff that was more funky than
I could make sense of.  So the input side of these two arch's
was left as-is.  I'd welcome someone with access to either of
these systems to provide additional patches.

The new format consists of multiple 32 bit words, separated by
commas, displayed and input in hex.  The following comment from
this patch describes this format further:

* The ascii representation of multi-word bit masks displays each
* 32bit word in hex (not zero filled), and for masks longer than
* one word, uses a comma separator between words.  Words are
* displayed in big-endian order most significant first.  And hex
* digits within a word are also in big-endian order, of course.
*
* Examples:
*   A mask with just bit 0 set displays as "1".
*   A mask with just bit 127 set displays as "80000000,0,0,0".
*   A mask with just bit 64 set displays as "1,0,0".
*   A mask with bits 0, 1, 2, 4, 8, 16, 32 and 64 set displays
*     as "1,1,10117".  The first "1" is for bit 64, the second
*     for bit 32, the third for bit 16, and so forth, to the
*     "7", which is for bits 2, 1 and 0.
*   A mask with bits 32 through 39 set displays as "ff,0".

The essential reason for adding the comma breaks was to make
the long masks from our (SGI's) big 512 CPU systems parsable by
humans.  An unbroken string of 128 hex digits is pretty difficult
to read.  For those who are compiling systems with CONFIG_NR_CPUS
of 32 or less, there should be no visible change in format.

There are of course a thousand possible output formats that
meet similar criteria.  If someone wants to lobby for and seek
consensus behind another such format, that's fine.  Now that
the format is consolidated into a single pair of routines,
it should be easy to adapt whatever we choose.

Internally, the display routine uses snprintf to track the
remaining space in its output buffer, to avoid the risk of
overrunning it.

A new file, lib/mask.c, is added to the lib directory, to
hold the two common routines.  I anticipate adding a few more
common routines for generic support of multi-word bit masks to
lib/mask.c, in subsequent patches that will add a nodemask_t
type as an ADT sharing implementation with cpumask_t.

It turns out that the int_sqrt() function in oom_kill.c gets it wrong.

But fb_sqrt() in fbmon.c gets its math right.  Move that function into
lib/int_sqrt.c, and consolidate.

(oom_kill.c fix from Thomas Schlichter <schlicht@uni-mannheim.de>)

If both ext2 and ext3 are built as modules there is nothing to pull
percpu_counter_mod() into the kernel build and the ext2 and ext3 modules do
not load.

So move percpu_counter_mod() out of lib.a.

From: "Randy.Dunlap" <rddunlap@osdl.org>, Will Dyson <will_dyson@pobox.com>, me

Add generic filesystem options parser (infrastructure) and use it to parse
mount options in several filesystems (adfs, affs, autofs, autofs4, ext2,
ext3, fat, hfs, hpfs, isofs, jfs, procfs, udf, and ufs).

It saves between 128 and 512 bytes per filesystem.

Use "select CRC32" in Kconfig instead of makefile includes.

This offers a generic do_div64() that actually does the right thing,
unlike some architectures that "optimized" the 64-by-32 divide into
just a 32-bit divide.

Both ppc and sh were already providing an assembly optimized
__div64_32().  I called my function the same, so that their optimized
versions will automatically override mine in lib.a.

I've only tested extensively on m68knommu (uClinux) and made
sure generated code is reasonably short. Should be ok also on
parisc, since it's the same algorithm they were using before.

 - add generic C implementations of the do_div() for 32bit and 64bit
   archs in asm-generic/div64.h;

 - add generic library support function __div64_32() to handle the
   full 64/32 case on 32bit archs;

 - kill multiple copies of generic do_div() in architecture
   specific subdirs. Most copies were either buggy or not doing
   what they were supposed to do;

 - ensure all surviving instances of do_div() have their parameters
   correctly parenthesized to avoid funny side-effects;

 - add dvb subsystem as a crc32 lib user

New makefile variable introduced: lib-y

The lib-y syntax allows you to do the usual tricks such as:

	lib-$(CONFIG_SMP) += percpu_counter.o

A built-in.o is always present in a directory that list .o files in
either obj-* or lib-*.

In contrast, lib.a is made only when lib-y is defined.

I also updated lib/Makefile, so that crc32.o is now always built-in
if selected. 

Several places in ext2 and ext3 are using filesystem-wide counters which use
global locking.  Mainly for the orlov allocator's heuristics.

To solve the contention which this causes we can trade off accuracy against
speed.

This patch introduces a "percpu_counter" library type in which the counts are
per-cpu and are periodically spilled into a global counter.  Readers only
read the global counter.

These objects are *large*.  On a 32 CPU P4, they are 4 kbytes.  On a 4 way
p3, 128 bytes.

This is version 23 or so of the POSIX timer code.

Internal changelog:

 - Changed the signals code to match the new order of things.  Also the
   new xtime_lock code needed to be picked up.  It made some things a lot
   simpler.

 - Fixed a spin lock hand off problem in locking timers (thanks
   to Randy).

 - Fixed nanosleep to test for out of bound nanoseconds
   (thanks to Julie).

 - Fixed a couple of id deallocation bugs that left old ids
   laying around (hey I get this one).

 - This version has a new timer id manager.  Andrew Morton
   suggested elimination of recursion (done) and I added code
   to allow it to release unused nodes.  The prior version only
   released the leaf nodes.  (The id manager uses radix tree
   type nodes.)  Also added is a reuse count so ids will not
   repeat for at least 256 alloc/ free cycles.

 - The changes for the new sys_call restart now allow one
   restart function to handle both nanosleep and clock_nanosleep.
   Saves a bit of code, nice.

 - All the requested changes and Lindent too :).

 - I also broke clock_nanosleep() apart much the same way
   nanosleep() was with the 2.5.50-bk5 changes.

TIMER STORMS

The POSIX clocks and timers code prevents "timer storms" by
not putting repeating timers back in the timer list until
the signal is delivered for the prior expiry.  Timer events
missed by this delay are accounted for in the timer overrun
count.  The net result is MUCH lower system overhead while
presenting the same info to the user as would be the case if
an interrupt and timer processing were required for each
increment in the overrun count.

Use the kernel CRC routines rather than a do-it-yourself version.
By the way, I created a common USB Makefile.lib, rather than having
one for the class drivers, and one for speedtouch.

One of the goals of the whole new modversions implementation:
export-objs is gone for good!

This patch combines my patch which statically initialises the crc32
tables so they can be used at any time (during initialisation) and
Joakim Tjernlund's patch to speed up the crc calculations by doing word
operations instead of exclusively byte.

The crc routines are used extensively in jffs2 where speed is very
important.

I need the crc32 routines to calculate a checksum on values read from an
eeprom which contain cpu speed and memory size information - so they are
needed very much earlier in the initialisation process than they are
currently available.

Makefiles no longer need to include Rules.make, which is currently an
empty file.  This patch removes it from the remaining Makefiles, and
removes the empty Rules.make file.

This is not meant to be fancy; just something simple for which we can 
control the refcount and other common functionality using common code. 
   
The basic operations for registration and reference count manipulation are
included. 

This patch modifies the BlueZ BNEP layer to use the CRC32 code from
the lib/ directory.

From Christoph Hellwig, also present in 2.4.

Create an arch-independent `dump_stack()' function.  So we don't need to do

#ifdef CONFIG_X86
	show_stack(0);		/* No prototype in scope! */
#endif

any more.

The whole dump_stack() implementation is delegated to the architecture.
If it doesn't provide one, there is a default do-nothing library
function.

Before the mempool was added, the VM was getting many, many
0-order allocation failures due to the atomic ratnode
allocations inside swap_out.  That monster mempool is
doing its job - drove a 256meg machine a gigabyte into
swap with no ratnode allocation failures at all.

So we do need to trim that pool a bit, and also handle
the case where swap_out fails, and not just keep
pointlessly calling it.

fixed lib Makefile problem with usb files moving
moved drivers/usb/scanner/ to drivers/usb/image/

- Doug Ledford: i810 audio driver update
- Evgeniy Polyakov: update various SCSI drivers to new locking
- David Howells: syscall latency improvement, try 2
- Francois Romieu: dscc4 driver update
- Patrick Mochel: driver model fixes
- Andrew Morton: clean up a few details in ext3 inode initialization
- Pete Wyckoff: make x86 machine check print out right address..
- Hans Reiser: reiserfs update
- Richard Gooch: devfs update
- Greg KH: USB updates
- Dave Jones: PNPBIOS
- Nathan Scott: extended attributes
- Corey Minyard: clean up zlib duplication (triplication..)

- Matt Domsch: combine common crc32 library
- Pete Zaitcev: ymfpci update
- Davide Libenzi: scheduler improvements
- Al Viro: almost there: "struct block_device *" everywhere
- Richard Gooch: devfs cpqarray update, race fix
- Rusty Russell: PATH_MAX should include the final '0' count
- David Miller: various random updates (mainly net and sparc)

  - Neil Brown: md cleanups/fixes
  - Andrew Morton: console locking merge
  - Andrea Arkangeli: major VM merge

  - Al Viro: block device cleanups
  - Marcelo Tosatti: make bounce buffer allocations more robust (it's ok
  for them to do IO, just not cause recursive bounce IO. So allow them)
  - Anton Altaparmakov: NTFS update (1.1.17)
  - Paul Mackerras: PPC update (big re-org)
  - Petko Manolov: USB pegasus driver fixes
  - David Miller: networking and sparc updates
  - Trond Myklebust: Export atomic_dec_and_lock
  - OGAWA Hirofumi: find and fix umsdos "filldir" users that were broken
  by the 64-bit-cleanups. Fix msdos warnings.
  - Al Viro: superblock handling cleanups and race fixes
  - Johannes Erdfelt++: USB updates

  - Johannes Erdfelt: USB updates
  - David Howells: more rw-sem stuff
  - David Miller: network callback cleanups and fixes
  - Jan Harkes: make Coda use the proper VFS layer interfaces, so that it can use
  "non-traditional-unix" filesystems without inode numbers for backing store.

  - David Miller: sparc rw semaphores moved over
  - Alan Cox: yet more resyncs
  - NIIBE Yutaka: Super-H driver update
  - David Howells: more rw-sem cleanups, updates
  - USB updates
  - Al Viro: filesystem init cleanup

  - Hui-Fen Hsu: sis900 driver update
  - NIIBE Yutaka: Super-H update
  - Alan Cox: more resyncs (ARM down, but more to go)
  - David Miller: network zerocopy, Sparc sync, qlogic,FC fix, etc.
  - David Miller/me: get rid of various drivers hacks to do mmap
  alignment behind the back of the VM layer. Create a real
  protocol for it.