1. 18 Oct, 2005 1 commit
  2. 08 Oct, 2005 1 commit
  3. 05 Oct, 2005 1 commit
  4. 15 Sep, 2005 1 commit
    • David S. Miller's avatar
      [LIB]: Consolidate _atomic_dec_and_lock() · 4db2ce01
      David S. Miller authored
      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: default avatarDavid S. Miller <davem@davemloft.net>
      4db2ce01
  5. 12 Sep, 2005 1 commit
  6. 10 Sep, 2005 3 commits
    • Adrian Bunk's avatar
      [PATCH] lib/sort.c: small cleanups · ecec4cb7
      Adrian Bunk authored
      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: Adrian Bunk's avatarAdrian Bunk <bunk@stusta.de>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      ecec4cb7
    • Victor Fusco's avatar
      [PATCH] lib/radix-tree: Fix "nocast type" warnings · 00b61f51
      Victor Fusco authored
      Fix the sparse warning "implicit cast to nocast type"
      Signed-off-by: default avatarVictor Fusco <victor@cetuc.puc-rio.br>
      Signed-off-by: default avatarDomen Puncer <domen@coderock.org>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      00b61f51
    • 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
  7. 08 Sep, 2005 2 commits
  8. 07 Sep, 2005 3 commits
  9. 05 Sep, 2005 2 commits
  10. 29 Aug, 2005 6 commits
  11. 26 Aug, 2005 1 commit
  12. 24 Aug, 2005 1 commit
  13. 17 Aug, 2005 1 commit
    • Linus Torvalds's avatar
      Revert unnecessary zlib_inflate/inftrees.c fix · c231c7db
      Linus Torvalds authored
      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: default avatarLinus Torvalds <torvalds@osdl.org>
      c231c7db
  14. 07 Aug, 2005 1 commit
  15. 05 Aug, 2005 1 commit
  16. 29 Jul, 2005 1 commit
  17. 27 Jul, 2005 1 commit
  18. 08 Jul, 2005 1 commit
  19. 25 Jun, 2005 3 commits
  20. 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
  21. 22 Jun, 2005 3 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
    • Zaur Kambarov's avatar
      [PATCH] coverity: idr_get_new_above_int() overrun fix · 589777ea
      Zaur Kambarov authored
      This patch fixes overrun of array pa:
      92   		struct idr_layer *pa[MAX_LEVEL];
      
      in
      
      98   		l = idp->layers;
      99   		pa[l--] = NULL;
      
      by passing idp->layers, set in
      202  		idp->layers = layers;
      to function  sub_alloc in
      203  		v = sub_alloc(idp, ptr, &id);
      Signed-off-by: default avatarZaur Kambarov <zkambarov@coverity.com>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      589777ea
  22. 20 Jun, 2005 1 commit