1. 08 Dec, 2006 2 commits
    • Akinobu Mita's avatar
      [PATCH] bit reverse library · a5cfc1ec
      Akinobu Mita authored
      
      
      This patch provides two bit reverse functions and bit reverse table.
      
      - reverse the order of bits in a u32 value
      
      	u8 bitrev8(u8 x);
      
      - reverse the order of bits in a u32 value
      
      	u32 bitrev32(u32 x);
      
      - byte reverse table
      
      	const u8 byte_rev_table[256];
      Signed-off-by: default avatarAkinobu Mita <akinobu.mita@gmail.com>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      a5cfc1ec
    • Jeremy Fitzhardinge's avatar
      [PATCH] Generic BUG implementation · 7664c5a1
      Jeremy Fitzhardinge authored
      
      
      This patch adds common handling for kernel BUGs, for use by architectures as
      they wish.  The code is derived from arch/powerpc.
      
      The advantages of having common BUG handling are:
       - consistent BUG reporting across architectures
       - shared implementation of out-of-line file/line data
       - implement CONFIG_DEBUG_BUGVERBOSE consistently
      
      This means that in inline impact of BUG is just the illegal instruction
      itself, which is an improvement for i386 and x86-64.
      
      A BUG is represented in the instruction stream as an illegal instruction,
      which has file/line information associated with it.  This extra information is
      stored in the __bug_table section in the ELF file.
      
      When the kernel gets an illegal instruction, it first confirms it might
      possibly be from a BUG (ie, in kernel mode, the right illegal instruction).
      It then calls report_bug().  This searches __bug_table for a matching
      instruction pointer, and if found, prints the corresponding file/line
      information.  If report_bug() determines that it wasn't a BUG which caused the
      trap, it returns BUG_TRAP_TYPE_NONE.
      
      Some architectures (powerpc) implement WARN using the same mechanism; if the
      illegal instruction was the result of a WARN, then report_bug(Q) returns
      CONFIG_DEBUG_BUGVERBOSE; otherwise it returns BUG_TRAP_TYPE_BUG.
      
      lib/bug.c keeps a list of loaded modules which can be searched for __bug_table
      entries.  The architecture must call
      module_bug_finalize()/module_bug_cleanup() from its corresponding
      module_finalize/cleanup functions.
      
      Unsetting CONFIG_DEBUG_BUGVERBOSE will reduce the kernel size by some amount.
      At the very least, filename and line information will not be recorded for each
      but, but architectures may decide to store no extra information per BUG at
      all.
      
      Unfortunately, gcc doesn't have a general way to mark an asm() as noreturn, so
      architectures will generally have to include an infinite loop (or similar) in
      the BUG code, so that gcc knows execution won't continue beyond that point.
      gcc does have a __builtin_trap() operator which may be useful to achieve the
      same effect, unfortunately it cannot be used to actually implement the BUG
      itself, because there's no way to get the instruction's address for use in
      generating the __bug_table entry.
      
      [randy.dunlap@oracle.com: Handle BUG=n, GENERIC_BUG=n to prevent build errors]
      [bunk@stusta.de: include/linux/bug.h must always #include <linux/module.h]
      Signed-off-by: default avatarJeremy Fitzhardinge <jeremy@goop.org>
      Cc: Andi Kleen <ak@muc.de>
      Cc: Hugh Dickens <hugh@veritas.com>
      Cc: Michael Ellerman <michael@ellerman.id.au>
      Cc: Paul Mackerras <paulus@samba.org>
      Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
      Cc: Rusty Russell <rusty@rustcorp.com.au>
      Signed-off-by: default avatarAdrian Bunk <bunk@stusta.de>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      7664c5a1
  2. 07 Dec, 2006 1 commit
    • Randy Dunlap's avatar
      [PATCH] lib functions: always build hweight for loadable modules · 702a28b1
      Randy Dunlap authored
      
      
      Always build hweight8/16/32/64() functions into the kernel so that loadable
      modules may use them.
      
      I didn't remove GENERIC_HWEIGHT since ALPHA_EV67, ia64, and some variants
      of UltraSparc(64) provide their own hweight functions.
      
      Fixes config/build problems with NTFS=m and JOYSTICK_ANALOG=m.
      
        Kernel: arch/x86_64/boot/bzImage is ready  (#19)
          Building modules, stage 2.
          MODPOST 94 modules
        WARNING: "hweight32" [fs/ntfs/ntfs.ko] undefined!
        WARNING: "hweight16" [drivers/input/joystick/analog.ko] undefined!
        WARNING: "hweight8" [drivers/input/joystick/analog.ko] undefined!
        make[1]: *** [__modpost] Error 1
        make: *** [modules] Error 2
      Signed-off-by: default avatarRandy Dunlap <randy.dunlap@oracle.com>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      702a28b1
  3. 17 Oct, 2006 2 commits
  4. 11 Oct, 2006 1 commit
  5. 05 Oct, 2006 1 commit
    • David Howells's avatar
      IRQ: Maintain regs pointer globally rather than passing to IRQ handlers · 7d12e780
      David Howells authored
      
      
      Maintain a per-CPU global "struct pt_regs *" variable which can be used instead
      of passing regs around manually through all ~1800 interrupt handlers in the
      Linux kernel.
      
      The regs pointer is used in few places, but it potentially costs both stack
      space and code to pass it around.  On the FRV arch, removing the regs parameter
      from all the genirq function results in a 20% speed up of the IRQ exit path
      (ie: from leaving timer_interrupt() to leaving do_IRQ()).
      
      Where appropriate, an arch may override the generic storage facility and do
      something different with the variable.  On FRV, for instance, the address is
      maintained in GR28 at all times inside the kernel as part of general exception
      handling.
      
      Having looked over the code, it appears that the parameter may be handed down
      through up to twenty or so layers of functions.  Consider a USB character
      device attached to a USB hub, attached to a USB controller that posts its
      interrupts through a cascaded auxiliary interrupt controller.  A character
      device driver may want to pass regs to the sysrq handler through the input
      layer which adds another few layers of parameter passing.
      
      I've build this code with allyesconfig for x86_64 and i386.  I've runtested the
      main part of the code on FRV and i386, though I can't test most of the drivers.
      I've also done partial conversion for powerpc and MIPS - these at least compile
      with minimal configurations.
      
      This will affect all archs.  Mostly the changes should be relatively easy.
      Take do_IRQ(), store the regs pointer at the beginning, saving the old one:
      
      	struct pt_regs *old_regs = set_irq_regs(regs);
      
      And put the old one back at the end:
      
      	set_irq_regs(old_regs);
      
      Don't pass regs through to generic_handle_irq() or __do_IRQ().
      
      In timer_interrupt(), this sort of change will be necessary:
      
      	-	update_process_times(user_mode(regs));
      	-	profile_tick(CPU_PROFILING, regs);
      	+	update_process_times(user_mode(get_irq_regs()));
      	+	profile_tick(CPU_PROFILING);
      
      I'd like to move update_process_times()'s use of get_irq_regs() into itself,
      except that i386, alone of the archs, uses something other than user_mode().
      
      Some notes on the interrupt handling in the drivers:
      
       (*) input_dev() is now gone entirely.  The regs pointer is no longer stored in
           the input_dev struct.
      
       (*) finish_unlinks() in drivers/usb/host/ohci-q.c needs checking.  It does
           something different depending on whether it's been supplied with a regs
           pointer or not.
      
       (*) Various IRQ handler function pointers have been moved to type
           irq_handler_t.
      Signed-Off-By: default avatarDavid Howells <dhowells@redhat.com>
      (cherry picked from 1b16e7ac850969f38b375e511e3fa2f474a33867 commit)
      7d12e780
  6. 02 Oct, 2006 2 commits
    • Arnd Bergmann's avatar
      [PATCH] remove remaining errno and __KERNEL_SYSCALLS__ references · 135ab6ec
      Arnd Bergmann authored
      
      
      The last in-kernel user of errno is gone, so we should remove the definition
      and everything referring to it.  This also removes the now-unused lib/execve.c
      file that was introduced earlier.
      
      Also remove every trace of __KERNEL_SYSCALLS__ that still remained in the
      kernel.
      Signed-off-by: default avatarArnd Bergmann <arnd@arndb.de>
      Cc: Andi Kleen <ak@muc.de>
      Cc: Paul Mackerras <paulus@samba.org>
      Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
      Cc: Richard Henderson <rth@twiddle.net>
      Cc: Ivan Kokshaysky <ink@jurassic.park.msu.ru>
      Cc: Russell King <rmk@arm.linux.org.uk>
      Cc: Ian Molton <spyro@f2s.com>
      Cc: Mikael Starvik <starvik@axis.com>
      Cc: David Howells <dhowells@redhat.com>
      Cc: Yoshinori Sato <ysato@users.sourceforge.jp>
      Cc: Hirokazu Takata <takata.hirokazu@renesas.com>
      Cc: Ralf Baechle <ralf@linux-mips.org>
      Cc: Kyle McMartin <kyle@mcmartin.ca>
      Cc: Heiko Carstens <heiko.carstens@de.ibm.com>
      Cc: Martin Schwidefsky <schwidefsky@de.ibm.com>
      Cc: Paul Mundt <lethal@linux-sh.org>
      Cc: Kazumoto Kojima <kkojima@rr.iij4u.or.jp>
      Cc: Richard Curnow <rc@rc0.org.uk>
      Cc: William Lee Irwin III <wli@holomorphy.com>
      Cc: "David S. Miller" <davem@davemloft.net>
      Cc: Jeff Dike <jdike@addtoit.com>
      Cc: Paolo 'Blaisorblade' Giarrusso <blaisorblade@yahoo.it>
      Cc: Miles Bader <uclinux-v850@lsi.nec.co.jp>
      Cc: Chris Zankel <chris@zankel.net>
      Cc: "Luck, Tony" <tony.luck@intel.com>
      Cc: Geert Uytterhoeven <geert@linux-m68k.org>
      Cc: Roman Zippel <zippel@linux-m68k.org>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      135ab6ec
    • Arnd Bergmann's avatar
      [PATCH] introduce kernel_execve · 67608567
      Arnd Bergmann authored
      
      
      The use of execve() in the kernel is dubious, since it relies on the
      __KERNEL_SYSCALLS__ mechanism that stores the result in a global errno
      variable.  As a first step of getting rid of this, change all users to a
      global kernel_execve function that returns a proper error code.
      
      This function is a terrible hack, and a later patch removes it again after the
      kernel syscalls are gone.
      Signed-off-by: default avatarArnd Bergmann <arnd@arndb.de>
      Cc: Andi Kleen <ak@muc.de>
      Cc: Paul Mackerras <paulus@samba.org>
      Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
      Cc: Richard Henderson <rth@twiddle.net>
      Cc: Ivan Kokshaysky <ink@jurassic.park.msu.ru>
      Cc: Russell King <rmk@arm.linux.org.uk>
      Cc: Ian Molton <spyro@f2s.com>
      Cc: Mikael Starvik <starvik@axis.com>
      Cc: David Howells <dhowells@redhat.com>
      Cc: Yoshinori Sato <ysato@users.sourceforge.jp>
      Cc: Hirokazu Takata <takata.hirokazu@renesas.com>
      Cc: Ralf Baechle <ralf@linux-mips.org>
      Cc: Kyle McMartin <kyle@mcmartin.ca>
      Cc: Heiko Carstens <heiko.carstens@de.ibm.com>
      Cc: Martin Schwidefsky <schwidefsky@de.ibm.com>
      Cc: Paul Mundt <lethal@linux-sh.org>
      Cc: Kazumoto Kojima <kkojima@rr.iij4u.or.jp>
      Cc: Richard Curnow <rc@rc0.org.uk>
      Cc: William Lee Irwin III <wli@holomorphy.com>
      Cc: "David S. Miller" <davem@davemloft.net>
      Cc: Jeff Dike <jdike@addtoit.com>
      Cc: Paolo 'Blaisorblade' Giarrusso <blaisorblade@yahoo.it>
      Cc: Miles Bader <uclinux-v850@lsi.nec.co.jp>
      Cc: Chris Zankel <chris@zankel.net>
      Cc: "Luck, Tony" <tony.luck@intel.com>
      Cc: Geert Uytterhoeven <geert@linux-m68k.org>
      Cc: Roman Zippel <zippel@linux-m68k.org>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      67608567
  7. 01 Oct, 2006 1 commit
    • Haavard Skinnemoen's avatar
      [PATCH] Generic ioremap_page_range: implementation · 74588d8b
      Haavard Skinnemoen authored
      
      
      This patch adds a generic implementation of ioremap_page_range() in
      lib/ioremap.c based on the i386 implementation. It differs from the
      i386 version in the following ways:
      
        * The PTE flags are passed as a pgprot_t argument and must be
          determined up front by the arch-specific code. No additional
          PTE flags are added.
        * Uses set_pte_at() instead of set_pte()
      
      [bunk@stusta.de: warning fix]
      ]dhowells@redhat.com: nommu build fix]
      Signed-off-by: default avatarHaavard Skinnemoen <hskinnemoen@atmel.com>
      Cc: Richard Henderson <rth@twiddle.net>
      Cc: Ivan Kokshaysky <ink@jurassic.park.msu.ru>
      Cc: Russell King <rmk@arm.linux.org.uk>
      Cc: Mikael Starvik <starvik@axis.com>
      Cc: Andi Kleen <ak@suse.de>
      Cc: <linux-m32r@ml.linux-m32r.org>
      Cc: Ralf Baechle <ralf@linux-mips.org>
      Cc: Kyle McMartin <kyle@parisc-linux.org>
      Cc: Martin Schwidefsky <schwidefsky@de.ibm.com>
      Cc: Paul Mundt <lethal@linux-sh.org>
      Signed-off-by: default avatarAdrian Bunk <bunk@stusta.de>
      Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      74588d8b
  8. 29 Sep, 2006 1 commit
  9. 12 Sep, 2006 1 commit
  10. 03 Jul, 2006 2 commits
    • Ingo Molnar's avatar
      [PATCH] lockdep: locking API self tests · cae2ed9a
      Ingo Molnar authored
      
      
      Introduce DEBUG_LOCKING_API_SELFTESTS, which uses the generic lock debugging
      code's silent-failure feature to run a matrix of testcases.  There are 210
      testcases currently:
      
        +-----------------------
        | Locking API testsuite:
        +------------------------------+------+------+------+------+------+------+
                                       | spin |wlock |rlock |mutex | wsem | rsem |
        -------------------------------+------+------+------+------+------+------+
                           A-A deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |
                       A-B-B-A deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |
                   A-B-B-C-C-A deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |
                   A-B-C-A-B-C deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |
               A-B-B-C-C-D-D-A deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |
               A-B-C-D-B-D-D-A deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |
               A-B-C-D-B-C-D-A deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |
                          double unlock:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |
                       bad unlock order:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |
        --------------------------------------+------+------+------+------+------+
                    recursive read-lock:             |  ok  |             |  ok  |
        --------------------------------------+------+------+------+------+------+
                      non-nested unlock:  ok  |  ok  |  ok  |  ok  |
        --------------------------------------+------+------+------+
           hard-irqs-on + irq-safe-A/12:  ok  |  ok  |  ok  |
           soft-irqs-on + irq-safe-A/12:  ok  |  ok  |  ok  |
           hard-irqs-on + irq-safe-A/21:  ok  |  ok  |  ok  |
           soft-irqs-on + irq-safe-A/21:  ok  |  ok  |  ok  |
             sirq-safe-A => hirqs-on/12:  ok  |  ok  |  ok  |
             sirq-safe-A => hirqs-on/21:  ok  |  ok  |  ok  |
               hard-safe-A + irqs-on/12:  ok  |  ok  |  ok  |
               soft-safe-A + irqs-on/12:  ok  |  ok  |  ok  |
               hard-safe-A + irqs-on/21:  ok  |  ok  |  ok  |
               soft-safe-A + irqs-on/21:  ok  |  ok  |  ok  |
          hard-safe-A + unsafe-B #1/123:  ok  |  ok  |  ok  |
          soft-safe-A + unsafe-B #1/123:  ok  |  ok  |  ok  |
          hard-safe-A + unsafe-B #1/132:  ok  |  ok  |  ok  |
          soft-safe-A + unsafe-B #1/132:  ok  |  ok  |  ok  |
          hard-safe-A + unsafe-B #1/213:  ok  |  ok  |  ok  |
          soft-safe-A + unsafe-B #1/213:  ok  |  ok  |  ok  |
          hard-safe-A + unsafe-B #1/231:  ok  |  ok  |  ok  |
          soft-safe-A + unsafe-B #1/231:  ok  |  ok  |  ok  |
          hard-safe-A + unsafe-B #1/312:  ok  |  ok  |  ok  |
          soft-safe-A + unsafe-B #1/312:  ok  |  ok  |  ok  |
          hard-safe-A + unsafe-B #1/321:  ok  |  ok  |  ok  |
          soft-safe-A + unsafe-B #1/321:  ok  |  ok  |  ok  |
          hard-safe-A + unsafe-B #2/123:  ok  |  ok  |  ok  |
          soft-safe-A + unsafe-B #2/123:  ok  |  ok  |  ok  |
          hard-safe-A + unsafe-B #2/132:  ok  |  ok  |  ok  |
          soft-safe-A + unsafe-B #2/132:  ok  |  ok  |  ok  |
          hard-safe-A + unsafe-B #2/213:  ok  |  ok  |  ok  |
          soft-safe-A + unsafe-B #2/213:  ok  |  ok  |  ok  |
          hard-safe-A + unsafe-B #2/231:  ok  |  ok  |  ok  |
          soft-safe-A + unsafe-B #2/231:  ok  |  ok  |  ok  |
          hard-safe-A + unsafe-B #2/312:  ok  |  ok  |  ok  |
          soft-safe-A + unsafe-B #2/312:  ok  |  ok  |  ok  |
          hard-safe-A + unsafe-B #2/321:  ok  |  ok  |  ok  |
          soft-safe-A + unsafe-B #2/321:  ok  |  ok  |  ok  |
            hard-irq lock-inversion/123:  ok  |  ok  |  ok  |
            soft-irq lock-inversion/123:  ok  |  ok  |  ok  |
            hard-irq lock-inversion/132:  ok  |  ok  |  ok  |
            soft-irq lock-inversion/132:  ok  |  ok  |  ok  |
            hard-irq lock-inversion/213:  ok  |  ok  |  ok  |
            soft-irq lock-inversion/213:  ok  |  ok  |  ok  |
            hard-irq lock-inversion/231:  ok  |  ok  |  ok  |
            soft-irq lock-inversion/231:  ok  |  ok  |  ok  |
            hard-irq lock-inversion/312:  ok  |  ok  |  ok  |
            soft-irq lock-inversion/312:  ok  |  ok  |  ok  |
            hard-irq lock-inversion/321:  ok  |  ok  |  ok  |
            soft-irq lock-inversion/321:  ok  |  ok  |  ok  |
            hard-irq read-recursion/123:  ok  |
            soft-irq read-recursion/123:  ok  |
            hard-irq read-recursion/132:  ok  |
            soft-irq read-recursion/132:  ok  |
            hard-irq read-recursion/213:  ok  |
            soft-irq read-recursion/213:  ok  |
            hard-irq read-recursion/231:  ok  |
            soft-irq read-recursion/231:  ok  |
            hard-irq read-recursion/312:  ok  |
            soft-irq read-recursion/312:  ok  |
            hard-irq read-recursion/321:  ok  |
            soft-irq read-recursion/321:  ok  |
        --------------------------------+-----+----------------
        Good, all 210 testcases passed! |
        --------------------------------+
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      Signed-off-by: default avatarArjan van de Ven <arjan@linux.intel.com>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      cae2ed9a
    • Ingo Molnar's avatar
      [PATCH] lockdep: better lock debugging · 9a11b49a
      Ingo Molnar authored
      
      
      Generic lock debugging:
      
       - generalized lock debugging framework. For example, a bug in one lock
         subsystem turns off debugging in all lock subsystems.
      
       - got rid of the caller address passing (__IP__/__IP_DECL__/etc.) from
         the mutex/rtmutex debugging code: it caused way too much prototype
         hackery, and lockdep will give the same information anyway.
      
       - ability to do silent tests
      
       - check lock freeing in vfree too.
      
       - more finegrained debugging options, to allow distributions to
         turn off more expensive debugging features.
      
      There's no separate 'held mutexes' list anymore - but there's a 'held locks'
      stack within lockdep, which unifies deadlock detection across all lock
      classes.  (this is independent of the lockdep validation stuff - lockdep first
      checks whether we are holding a lock already)
      
      Here are the current debugging options:
      
      CONFIG_DEBUG_MUTEXES=y
      CONFIG_DEBUG_LOCK_ALLOC=y
      
      which do:
      
       config DEBUG_MUTEXES
                bool "Mutex debugging, basic checks"
      
       config DEBUG_LOCK_ALLOC
               bool "Detect incorrect freeing of live mutexes"
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      Signed-off-by: default avatarArjan van de Ven <arjan@linux.intel.com>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      9a11b49a
  11. 28 Jun, 2006 1 commit
  12. 23 Jun, 2006 1 commit
  13. 26 Mar, 2006 1 commit
  14. 25 Mar, 2006 1 commit
  15. 01 Feb, 2006 1 commit
    • Bryan O'Sullivan's avatar
      [PATCH] Introduce __iowrite32_copy · c27a0d75
      Bryan O'Sullivan authored
      
      
      This arch-independent routine copies data to a memory-mapped I/O region,
      using 32-bit accesses.  The naming is double-underscored to make it clear
      that it does not guarantee write ordering, nor does it perform a memory
      barrier afterwards; the kernel doc also explicitly states this.  This style
      of access is required by some devices.
      
      This change also introduces include/linux/io.h, at Andrew's suggestion.  It
      only has one occupant at the moment, but is a logical destination for
      oft-replicated contents of include/asm-*/{io,iomap}.h to migrate to.
      Signed-off-by: default avatarBryan O'Sullivan <bos@pathscale.com>
      Cc: Andi Kleen <ak@muc.de>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      c27a0d75
  16. 29 Sep, 2005 1 commit
  17. 10 Sep, 2005 1 commit
    • Ingo Molnar's avatar
      [PATCH] spinlock consolidation · fb1c8f93
      Ingo Molnar authored
      
      
      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: default avatarIngo Molnar <mingo@elte.hu>
      Signed-off-by: default avatarArjan van de Ven <arjanv@infradead.org>
      Signed-off-by: default avatarGrant Grundler <grundler@parisc-linux.org>
      Cc: Matthew Wilcox <willy@debian.org>
      Signed-off-by: default avatarHirokazu Takata <takata@linux-m32r.org>
      Signed-off-by: default avatarMikael Pettersson <mikpe@csd.uu.se>
      Signed-off-by: default avatarBenoit Boissinot <benoit.boissinot@ens-lyon.org>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      fb1c8f93
  18. 08 Sep, 2005 1 commit
  19. 05 Sep, 2005 1 commit
  20. 29 Aug, 2005 1 commit
  21. 27 Jul, 2005 1 commit
  22. 24 Jun, 2005 4 commits
    • David S. Miller's avatar
      [LIB]: textsearch.o needs to be obj-y not lib-y. · 65df877a
      David S. Miller authored
      
      
      It exports symbols.
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      65df877a
    • Thomas Graf's avatar
      [LIB]: Naive finite state machine based textsearch · 6408f79c
      Thomas Graf authored
      
      
      A finite state machine consists of n states (struct ts_fsm_token)
      representing the pattern as a finite automation. The data is read
      sequentially on a octet basis. Every state token specifies the number
      of recurrences and the type of value accepted which can be either a
      specific character or ctype based set of characters. The available
      type of recurrences include 1, (0|1), [0 n], and [1 n].
      
      The algorithm differs between strict/non-strict mode specyfing
      whether the pattern has to start at the first octect. Strict mode
      is enabled by default and can be disabled by inserting
      TS_FSM_HEAD_IGNORE as the first token in the chain.
      
      The runtime performance of the algorithm should be around O(n),
      however while in strict mode the average runtime can be better.
      Signed-off-by: default avatarThomas Graf <tgraf@suug.ch>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      6408f79c
    • Thomas Graf's avatar
      [LIB]: Knuth-Morris-Pratt textsearch algorithm · df3fb93a
      Thomas Graf authored
      
      
      Implements a linear-time string-matching algorithm due to Knuth,
      Morris, and Pratt [1]. Their algorithm avoids the explicit
      computation of the transition function DELTA altogether. Its
      matching time is O(n), for n being length(text), using just an
      auxiliary function PI[1..m], for m being length(pattern),
      precomputed from the pattern in time O(m). The array PI allows
      the transition function DELTA to be computed efficiently
      "on the fly" as needed. Roughly speaking, for any state
      "q" = 0,1,...,m and any character "a" in SIGMA, the value
      PI["q"] contains the information that is independent of "a" and
      is needed to compute DELTA("q", "a") [2]. Since the array PI
      has only m entries, whereas DELTA has O(m|SIGMA|) entries, we
      save a factor of |SIGMA| in the preprocessing time by computing
      PI rather than DELTA.
       
      [1] Cormen, Leiserson, Rivest, Stein
          Introdcution to Algorithms, 2nd Edition, MIT Press
      [2] See finite automation theory
      Signed-off-by: default avatarThomas Graf <tgraf@suug.ch>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      df3fb93a
    • Thomas Graf's avatar
      [LIB]: Textsearch infrastructure. · 2de4ff7b
      Thomas Graf authored
      
      
      The textsearch infrastructure provides text searching
      facitilies for both linear and non-linear data.
      Individual search algorithms are implemented in modules
      and chosen by the user.
      Signed-off-by: default avatarThomas Graf <tgraf@suug.ch>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      2de4ff7b
  23. 22 Jun, 2005 2 commits
    • Jes Sorensen's avatar
      [PATCH] ia64 uncached alloc · f14f75b8
      Jes Sorensen authored
      
      
      This patch contains the ia64 uncached page allocator and the generic
      allocator (genalloc).  The uncached allocator was formerly part of the SN2
      mspec driver but there are several other users of it so it has been split
      off from the driver.
      
      The generic allocator can be used by device driver to manage special memory
      etc.  The generic allocator is based on the allocator from the sym53c8xx_2
      driver.
      
      Various users on ia64 needs uncached memory.  The SGI SN architecture requires
      it for inter-partition communication between partitions within a large NUMA
      cluster.  The specific user for this is the XPC code.  Another application is
      large MPI style applications which use it for synchronization, on SN this can
      be done using special 'fetchop' operations but it also benefits non SN
      hardware which may use regular uncached memory for this purpose.  Performance
      of doing this through uncached vs cached memory is pretty substantial.  This
      is handled by the mspec driver which I will push out in a seperate patch.
      
      Rather than creating a specific allocator for just uncached memory I came up
      with genalloc which is a generic purpose allocator that can be used by device
      drivers and other subsystems as they please.  For instance to handle onboard
      device memory.  It was derived from the sym53c7xx_2 driver's allocator which
      is also an example of a potential user (I am refraining from modifying sym2
      right now as it seems to have been under fairly heavy development recently).
      
      On ia64 memory has various properties within a granule, ie.  it isn't safe to
      access memory as uncached within the same granule as currently has memory
      accessed in cached mode.  The regular system therefore doesn't utilize memory
      in the lower granules which is mixed in with device PAL code etc.  The
      uncached driver walks the EFI memmap and pulls out the spill uncached pages
      and sticks them into the uncached pool.  Only after these chunks have been
      utilized, will it start converting regular cached memory into uncached memory.
      Hence the reason for the EFI related code additions.
      Signed-off-by: default avatarJes Sorensen <jes@wildopensource.com>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      f14f75b8
    • Ingo Molnar's avatar
      [PATCH] smp_processor_id() cleanup · 39c715b7
      Ingo Molnar authored
      
      
      This patch implements a number of smp_processor_id() cleanup ideas that
      Arjan van de Ven and I came up with.
      
      The previous __smp_processor_id/_smp_processor_id/smp_processor_id API
      spaghetti was hard to follow both on the implementational and on the
      usage side.
      
      Some of the complexity arose from picking wrong names, some of the
      complexity comes from the fact that not all architectures defined
      __smp_processor_id.
      
      In the new code, there are two externally visible symbols:
      
       - smp_processor_id(): debug variant.
      
       - raw_smp_processor_id(): nondebug variant. Replaces all existing
         uses of _smp_processor_id() and __smp_processor_id(). Defined
         by every SMP architecture in include/asm-*/smp.h.
      
      There is one new internal symbol, dependent on DEBUG_PREEMPT:
      
       - debug_smp_processor_id(): internal debug variant, mapped to
                                   smp_processor_id().
      
      Also, i moved debug_smp_processor_id() from lib/kernel_lock.c into a new
      lib/smp_processor_id.c file.  All related comments got updated and/or
      clarified.
      
      I have build/boot tested the following 8 .config combinations on x86:
      
       {SMP,UP} x {PREEMPT,!PREEMPT} x {DEBUG_PREEMPT,!DEBUG_PREEMPT}
      
      I have also build/boot tested x64 on UP/PREEMPT/DEBUG_PREEMPT.  (Other
      architectures are untested, but should work just fine.)
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      Signed-off-by: default avatarArjan van de Ven <arjan@infradead.org>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      39c715b7
  24. 20 Jun, 2005 1 commit
    • mochel@digitalimplant.org's avatar
      [PATCH] Add initial implementation of klist helpers. · 9a19fea4
      mochel@digitalimplant.org authored
      
      
      This klist interface provides a couple of structures that wrap around
      struct list_head to provide explicit list "head" (struct klist) and
      list "node" (struct klist_node) objects. For struct klist, a spinlock
      is included that protects access to the actual list itself. struct
      klist_node provides a pointer to the klist that owns it and a kref
      reference count that indicates the number of current users of that node
      in the list.
      
      The entire point is to provide an interface for iterating over a list
      that is safe and allows for modification of the list during the
      iteration (e.g. insertion and removal), including modification of the
      current node on the list.
      
      It works using a 3rd object type - struct klist_iter - that is declared
      and initialized before an iteration. klist_next() is used to acquire the
      next element in the list. It returns NULL if there are no more items.
      This klist interface provides a couple of structures that wrap around
      struct list_head to provide explicit list "head" (struct klist) and
      list "node" (struct klist_node) objects. For struct klist, a spinlock
      is included that protects access to the actual list itself. struct
      klist_node provides a pointer to the klist that owns it and a kref
      reference count that indicates the number of current users of that node
      in the list.
      
      The entire point is to provide an interface for iterating over a list
      that is safe and allows for modification of the list during the
      iteration (e.g. insertion and removal), including modification of the
      current node on the list.
      
      It works using a 3rd object type - struct klist_iter - that is declared
      and initialized before an iteration. klist_next() is used to acquire the
      next element in the list. It returns NULL if there are no more items.
      Internally, that routine takes the klist's lock, decrements the reference
      count of the previous klist_node and increments the count of the next
      klist_node. It then drops the lock and returns.
      
      There are primitives for adding and removing nodes to/from a klist.
      When deleting, klist_del() will simply decrement the reference count.
      Only when the count goes to 0 is the node removed from the list.
      klist_remove() will try to delete the node from the list and block
      until it is actually removed. This is useful for objects (like devices)
      that have been removed from the system and must be freed (but must wait
      until all accessors have finished).
      
      Internally, that routine takes the klist's lock, decrements the reference
      count of the previous klist_node and increments the count of the next
      klist_node. It then drops the lock and returns.
      
      There are primitives for adding and removing nodes to/from a klist.
      When deleting, klist_del() will simply decrement the reference count.
      Only when the count goes to 0 is the node removed from the list.
      klist_remove() will try to delete the node from the list and block
      until it is actually removed. This is useful for objects (like devices)
      that have been removed from the system and must be freed (but must wait
      until all accessors have finished).
      Signed-off-by: default avatarPatrick Mochel <mochel@digitalimplant.org>
      Signed-off-by: default avatarGreg Kroah-Hartman <gregkh@suse.de>
      
      diff -Nru a/include/linux/klist.h b/include/linux/klist.h
      9a19fea4
  25. 16 Apr, 2005 1 commit
    • Linus Torvalds's avatar
      Linux-2.6.12-rc2 · 1da177e4
      Linus Torvalds authored
      Initial git repository build. I'm not bothering with the full history,
      even though we have it. We can create a separate "historical" git
      archive of that later if we want to, and in the meantime it's about
      3.2GB when imported into git - space that would just make the early
      git days unnecessarily complicated, when we don't have a lot of good
      infrastructure for it.
      
      Let it rip!
      1da177e4