1. 09 Apr, 2012 15 commits
  2. 30 Mar, 2012 1 commit
  3. 27 Mar, 2012 7 commits
  4. 23 Mar, 2012 17 commits
    • Hans Verkuil's avatar
      poll: add poll_requested_events() and poll_does_not_wait() functions · 626cf236
      Hans Verkuil authored
      In some cases the poll() implementation in a driver has to do different
      things depending on the events the caller wants to poll for.  An example
      is when a driver needs to start a DMA engine if the caller polls for
      POLLIN, but doesn't want to do that if POLLIN is not requested but instead
      only POLLOUT or POLLPRI is requested.  This is something that can happen
      in the video4linux subsystem among others.
      
      Unfortunately, the current epoll/poll/select implementation doesn't
      provide that information reliably.  The poll_table_struct does have it: it
      has a key field with the event mask.  But once a poll() call matches one
      or more bits of that mask any following poll() calls are passed a NULL
      poll_table pointer.
      
      Also, the eventpoll implementation always left the key field at ~0 instead
      of using the requested events mask.
      
      This was changed in eventpoll.c so the key field now contains the actual
      events that should be polled for as set by the caller.
      
      The solution to the NULL poll_table pointer is to set the qproc field to
      NULL in poll_table once poll() matches the events, not the poll_table
      pointer itself.  That way drivers can obtain the mask through a new
      poll_requested_events inline.
      
      The poll_table_struct can still be NULL since some kernel code calls it
      internally (netfs_state_poll() in ./drivers/staging/pohmelfs/netfs.h).  In
      that case poll_requested_events() returns ~0 (i.e.  all events).
      
      Very rarely drivers might want to know whether poll_wait will actually
      wait.  If another earlier file descriptor in the set already matched the
      events the caller wanted to wait for, then the kernel will return from the
      select() call without waiting.  This might be useful information in order
      to avoid doing expensive work.
      
      A new helper function poll_does_not_wait() is added that drivers can use
      to detect this situation.  This is now used in sock_poll_wait() in
      include/net/sock.h.  This was the only place in the kernel that needed
      this information.
      
      Drivers should no longer access any of the poll_table internals, but use
      the poll_requested_events() and poll_does_not_wait() access functions
      instead.  In order to enforce that the poll_table fields are now prepended
      with an underscore and a comment was added warning against using them
      directly.
      
      This required a change in unix_dgram_poll() in unix/af_unix.c which used
      the key field to get the requested events.  It's been replaced by a call
      to poll_requested_events().
      
      For qproc it was especially important to change its name since the
      behavior of that field changes with this patch since this function pointer
      can now be NULL when that wasn't possible in the past.
      
      Any driver accessing the qproc or key fields directly will now fail to compile.
      
      Some notes regarding the correctness of this patch: the driver's poll()
      function is called with a 'struct poll_table_struct *wait' argument.  This
      pointer may or may not be NULL, drivers can never rely on it being one or
      the other as that depends on whether or not an earlier file descriptor in
      the select()'s fdset matched the requested events.
      
      There are only three things a driver can do with the wait argument:
      
      1) obtain the key field:
      
      	events = wait ? wait->key : ~0;
      
         This will still work although it should be replaced with the new
         poll_requested_events() function (which does exactly the same).
         This will now even work better, since wait is no longer set to NULL
         unnecessarily.
      
      2) use the qproc callback. This could be deadly since qproc can now be
         NULL. Renaming qproc should prevent this from happening. There are no
         kernel drivers that actually access this callback directly, BTW.
      
      3) test whether wait == NULL to determine whether poll would return without
         waiting. This is no longer sufficient as the correct test is now
         wait == NULL || wait->_qproc == NULL.
      
         However, the worst that can happen here is a slight performance hit in
         the case where wait != NULL and wait->_qproc == NULL. In that case the
         driver will assume that poll_wait() will actually add the fd to the set
         of waiting file descriptors. Of course, poll_wait() will not do that
         since it tests for wait->_qproc. This will not break anything, though.
      
         There is only one place in the whole kernel where this happens
         (sock_poll_wait() in include/net/sock.h) and that code will be replaced
         by a call to poll_does_not_wait() in the next patch.
      
         Note that even if wait->_qproc != NULL drivers cannot rely on poll_wait()
         actually waiting. The next file descriptor from the set might match the
         event mask and thus any possible waits will never happen.
      Signed-off-by: default avatarHans Verkuil <hans.verkuil@cisco.com>
      Reviewed-by: default avatarJonathan Corbet <corbet@lwn.net>
      Reviewed-by: default avatarAl Viro <viro@zeniv.linux.org.uk>
      Cc: Davide Libenzi <davidel@xmailserver.org>
      Signed-off-by: default avatarHans de Goede <hdegoede@redhat.com>
      Cc: Mauro Carvalho Chehab <mchehab@infradead.org>
      Cc: David Miller <davem@davemloft.net>
      Cc: Eric Dumazet <eric.dumazet@gmail.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      626cf236
    • Darrick J. Wong's avatar
      crc32: select an algorithm via Kconfig · 5cde7656
      Darrick J. Wong authored
      Allow the kernel builder to choose a crc32* algorithm for the kernel.
      Signed-off-by: default avatarDarrick J. Wong <djwong@us.ibm.com>
      Cc: Bob Pearson <rpearson@systemfabricworks.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      5cde7656
    • Darrick J. Wong's avatar
      crc32: add self-test code for crc32c · 577eba9e
      Darrick J. Wong authored
      Add self-test code for crc32c.
      Signed-off-by: default avatarDarrick J. Wong <djwong@us.ibm.com>
      Cc: Bob Pearson <rpearson@systemfabricworks.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      577eba9e
    • Darrick J. Wong's avatar
      crypto: crc32c should use library implementation · 6a0962b2
      Darrick J. Wong authored
      Since lib/crc32.c now provides crc32c, remove the software implementation
      here and call the library function instead.
      Signed-off-by: default avatarDarrick J. Wong <djwong@us.ibm.com>
      Cc: Herbert Xu <herbert@gondor.apana.org.au>
      Cc: Bob Pearson <rpearson@systemfabricworks.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      6a0962b2
    • Darrick J. Wong's avatar
      crc32: bolt on crc32c · 46c5801e
      Darrick J. Wong authored
      Reuse the existing crc32 code to stamp out a crc32c implementation.
      Signed-off-by: default avatarDarrick J. Wong <djwong@us.ibm.com>
      Cc: Herbert Xu <herbert@gondor.apana.org.au>
      Cc: Bob Pearson <rpearson@systemfabricworks.com>
      Cc: Randy Dunlap <rdunlap@xenotime.net>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      46c5801e
    • Bob Pearson's avatar
      crc32: add note about this patchset to crc32.c · 78dff418
      Bob Pearson authored
      Add a comment at the top of crc32.c
      
      [djwong@us.ibm.com: Minor changelog tweaks]
      Signed-off-by: default avatarBob Pearson <rpearson@systemfabricworks.com>
      Signed-off-by: default avatarDarrick J. Wong <djwong@us.ibm.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      78dff418
    • Bob Pearson's avatar
      crc32: optimize loop counter for x86 · 0292c497
      Bob Pearson authored
      Add two changes that improve the performance of x86 systems
      
      1. replace main loop with incrementing counter this change improves
         the performance of the selftest by about 5-6% on Nehalem CPUs.  The
         apparent reason is that the compiler can use the loop index to perform
         an indexed memory access.  This is reported to make the performance of
         PowerPC CPUs to get worse.
      
      2. replace the rem_len loop with incrementing counter this change
         improves the performance of the selftest, which has more than the usual
         number of occurances, by about 1-2% on x86 CPUs.  In actual work loads
         the length is most often a multiple of 4 bytes and this code does not
         get executed as often if at all.  Again this change is reported to make
         the performance of PowerPC get worse.
      
      [djwong@us.ibm.com: Minor changelog tweaks]
      Signed-off-by: default avatarBob Pearson <rpearson@systemfabricworks.com>
      Signed-off-by: default avatarDarrick J. Wong <djwong@us.ibm.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      0292c497
    • Bob Pearson's avatar
      crc32: add slice-by-8 algorithm to existing code · 324eb0f1
      Bob Pearson authored
      Add slicing-by-8 algorithm to the existing slicing-by-4 algorithm.  This
      consists of:
      
      - extend largest BITS size from 32 to 64
      - extend tables from tab[4][256] to up to tab[8][256]
      - Add code for inner loop.
      
      [djwong@us.ibm.com: Minor changelog tweaks]
      Signed-off-by: default avatarBob Pearson <rpearson@systemfabricworks.com>
      Signed-off-by: default avatarDarrick J. Wong <djwong@us.ibm.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      324eb0f1
    • Bob Pearson's avatar
      crc32: make CRC_*_BITS definition correspond to actual bit counts · 9a1dbf6a
      Bob Pearson authored
      crc32.c provides a choice of one of several algorithms for computing the
      LSB and LSB versions of the CRC32 checksum based on the parameters
      CRC_LE_BITS and CRC_BE_BITS.
      
      In the original version the values 1, 2, 4 and 8 respectively selected
      versions of the alrogithm that computed the crc 1, 2, 4 and 32 bits as a
      time.
      
      This patch series adds a new version that computes the CRC 64 bits at a
      time.  To make things easier to understand the parameter has been
      reinterpreted to actually stand for the number of bits processed in each
      step of the algorithm so that the old value 8 has been replaced with the
      value 32.
      
      This also allows us to add in a widely used crc algorithm that computes
      the crc 8 bits at a time called the Sarwate algorithm.
      
      [djwong@us.ibm.com: Minor changelog tweaks]
      Signed-off-by: default avatarBob Pearson <rpearson@systemfabricworks.com>
      Signed-off-by: default avatarDarrick J. Wong <djwong@us.ibm.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      9a1dbf6a
    • Bob Pearson's avatar
      crc32: fix mixing of endian-specific types · ce4320dd
      Bob Pearson authored
      crc32.c in its original version freely mixed u32, __le32 and __be32 types
      which caused warnings from sparse with __CHECK_ENDIAN__.  This patch fixes
      these by forcing the types to u32.
      
      [djwong@us.ibm.com: Minor changelog tweaks]
      Signed-off-by: default avatarBob Pearson <rpearson@systemfabricworks.com>
      Signed-off-by: default avatarDarrick J. Wong <djwong@us.ibm.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      ce4320dd
    • Bob Pearson's avatar
      crc32: miscellaneous cleanups · 60e58d5c
      Bob Pearson authored
      Misc cleanup of lib/crc32.c and related files.
      
      - remove unnecessary header files.
      
      - straighten out some convoluted ifdef's
      
      - rewrite some references to 2 dimensional arrays as 1 dimensional
        arrays to make them correct.  I.e.  replace tab[i] with tab[0][i].
      
      - a few trivial whitespace changes
      
      - fix a warning in gen_crc32tables.c caused by a mismatch in the type of
        the pointer passed to output table.  Since the table is only used at
        kernel compile time, it is simpler to make the table big enough to hold
        the largest column size used.  One cannot make the column size smaller
        in output_table because it has to be used by both the le and be tables
        and they can have different column sizes.
      
      [djwong@us.ibm.com: Minor changelog tweaks]
      Signed-off-by: default avatarBob Pearson <rpearson@systemfabricworks.com>
      Signed-off-by: default avatarDarrick J. Wong <djwong@us.ibm.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      60e58d5c
    • Bob Pearson's avatar
      crc32: simplify unit test code · 3863ef31
      Bob Pearson authored
      Replace the unit test provided in crc32.c, which doesn't have a makefile
      and doesn't compile with current headers, with a simpler self test
      routine that also gives a measure of performance and runs at module init
      time.  The self test option can be enabled through a configuration
      option CONFIG_CRC32_SELFTEST.
      
      The test stresses the pre and post loops and is thus not very realistic
      since actual uses will likely have addresses and lengths that are at
      least 4 byte aligned.  However, the main loop is long enough so that the
      performance is dominated by that loop.
      
      The expected values for crc32_le and crc32_be were generated with the
      original version of crc32.c using CRC_BITS_LE = 8 and CRC_BITS_BE = 8.
      These values were then used to check all the values of the BITS
      parameters in both the original and new versions.
      
      The performance results show some variability from run to run in spite
      of attempts to both warm the cache and reduce the amount of OS noise by
      limiting interrutps during the test.  To get comparable results and to
      analyse options wrt performance the best time reported over a small
      sample of runs has been taken.
      
      [djwong@us.ibm.com: Minor changelog tweaks]
      Signed-off-by: default avatarBob Pearson <rpearson@systemfabricworks.com>
      Signed-off-by: default avatarDarrick J. Wong <djwong@us.ibm.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      3863ef31
    • Bob Pearson's avatar
      crc32: move long comment about crc32 fundamentals to Documentation/ · fbedceb1
      Bob Pearson authored
      Move a long comment from lib/crc32.c to Documentation/crc32.txt where it
      will more likely get read.
      
      Edited the resulting document to add an explanation of the slicing-by-n
      algorithm.
      
      [djwong@us.ibm.com: minor changelog tweaks]
      [akpm@linux-foundation.org: fix typo, per George]
      Signed-off-by: default avatarGeorge Spelvin <linux@horizon.com>
      Signed-off-by: default avatarBob Pearson <rpearson@systemfabricworks.com>
      Signed-off-by: default avatarDarrick J. Wong <djwong@us.ibm.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      fbedceb1
    • Bob Pearson's avatar
      crc32: remove two instances of trailing whitespaces · e30c7a8f
      Bob Pearson authored
      This patchset (re)uses Bob Pearson's crc32 slice-by-8 code to stamp out
      a software crc32c implementation.  It removes the crc32c implementation
      in crypto/ in favor of using the stamped-out one in lib/.  There is also
      a change to Kconfig so that the kernel builder can pick an
      implementation best suited for the hardware.
      
      The motivation for this patchset is that I am working on adding full
      metadata checksumming to ext4.  As far as performance impact of adding
      checksumming goes, I see nearly no change with a standard mail server
      ffsb simulation.  On a test that involves only file creation and
      deletion and extent tree writes, I see a drop of about 50 pcercent with
      the current kernel crc32c implementation; this improves to a drop of
      about 20 percent with the enclosed crc32c code.
      
      When metadata is usually a small fraction of total IO, this new
      implementation doesn't help much because metadata is usually a small
      fraction of total IO.  However, when we are doing IO that is almost all
      metadata (such as rm -rf'ing a tree), then this patch speeds up the
      operation substantially.
      
      Incidentally, given that iscsi, sctp, and btrfs also use crc32c, this
      patchset should improve their speed as well.  I have not yet quantified
      that, however.  This latest submission combines Bob's patches from late
      August 2011 with mine so that they can be one coherent patch set.
      Please excuse my inability to combine some of the patches; I've been
      advised to leave Bob's patches alone and build atop them instead.  :/
      
      Since the last posting, I've also collected some crc32c test results on
      a bunch of different x86/powerpc/sparc platforms.  The results can be
      viewed here: http://goo.gl/sgt3i ; the "crc32-kern-le" and "crc32c"
      columns describe the performance of the kernel's current crc32 and
      crc32c software implementations.  The "crc32c-by8-le" column shows
      crc32c performance with this patchset applied.  I expect crc32
      performance to be roughly the same.
      
      The two _boost columns at the right side of the spreadsheet shows how much
      faster the new implementation is over the old one.  As you can see, crc32
      rises substantially, and crc32c experiences a huge increase.
      
      This patch:
      
      - remove trailing whitespace from lib/crc32.c
      - remove trailing whitespace from lib/crc32defs.h
      
      [djwong@us.ibm.com: changelog tweaks]
      Signed-off-by: default avatarBob Pearson <rpearson@systemfabricworks.com>
      Signed-off-by: default avatarDarrick J. Wong <djwong@us.ibm.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      e30c7a8f
    • Josh Triplett's avatar
      checkpatch: check for quoted strings broken across lines · ca56dc09
      Josh Triplett authored
      checkpatch already makes an exception to the 80-column rule for quoted
      strings, and Documentation/CodingStyle recommends not splitting quoted
      strings across lines, because it breaks the ability to grep for the
      string.  Rather than just permitting this, actively warn about quoted
      strings split across lines.
      
      Test case:
      
      void context(void)
      {
      	struct { unsigned magic; const char *strdata; } foo[] = {
      		{ 42, "these strings"
      		      "do not produce warnings" },
      		{ 256, "though perhaps"
      		       "they should" },
      	};
      	pr_err("this string"
      	       " should produce a warning\n");
      	pr_err("this multi-line string\n"
      	       "should not produce a warning\n");
      	asm ("this asm\n\t"
      	     "should not produce a warning");
      }
      
      Results of checkpatch on that test case:
      
      WARNING: quoted string split across lines
      +	       " should produce a warning\n");
      
      total: 0 errors, 1 warnings, 15 lines checked
      Signed-off-by: default avatarJosh Triplett <josh@joshtriplett.org>
      Acked-by: default avatarJoe Perches <joe@perches.com>
      Cc: Andy Whitcroft <apw@canonical.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      ca56dc09
    • Joe Perches's avatar
      checkpatch: whitespace - add/remove blank lines · 6712d858
      Joe Perches authored
      Add blank lines between a few tests, remove an extraneous one.
      Signed-off-by: default avatarJoe Perches <joe@perches.com>
      Cc: Andy Whitcroft <apw@canonical.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      6712d858
    • Joe Perches's avatar
      checkpatch: warn on use of yield() · 2c92488a
      Joe Perches authored
      Using yield() is generally wrong.  Warn on its use.
      Signed-off-by: default avatarJoe Perches <joe@perches.com>
      Cc: Andy Whitcroft <apw@canonical.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      2c92488a