1. 29 Jul, 2016 1 commit
  2. 15 Jul, 2016 1 commit
  3. 07 Jul, 2016 1 commit
    • Thomas Gleixner's avatar
      timers: Remove set_timer_slack() leftovers · 53bf837b
      Thomas Gleixner authored
      
      
      We now have implicit batching in the timer wheel. The slack API is no longer
      used, so remove it.
      Signed-off-by: default avatarThomas Gleixner <tglx@linutronix.de>
      Cc: Alan Stern <stern@rowland.harvard.edu>
      Cc: Andrew F. Davis <afd@ti.com>
      Cc: Arjan van de Ven <arjan@infradead.org>
      Cc: Chris Mason <clm@fb.com>
      Cc: David S. Miller <davem@davemloft.net>
      Cc: David Woodhouse <dwmw2@infradead.org>
      Cc: Dmitry Eremin-Solenikov <dbaryshkov@gmail.com>
      Cc: Eric Dumazet <edumazet@google.com>
      Cc: Frederic Weisbecker <fweisbec@gmail.com>
      Cc: George Spelvin <linux@sciencehorizons.net>
      Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
      Cc: Jaehoon Chung <jh80.chung@samsung.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: John Stultz <john.stultz@linaro.org>
      Cc: Josh Triplett <josh@joshtriplett.org>
      Cc: Len Brown <lenb@kernel.org>
      Cc: Linus Torvalds <torvalds@linux-foundation.org>
      Cc: Mathias Nyman <mathias.nyman@intel.com>
      Cc: Pali Rohár <pali.rohar@gmail.com>
      Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
      Cc: Peter Zijlstra <peterz@infradead.org>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Sebastian Reichel <sre@kernel.org>
      Cc: Ulf Hansson <ulf.hansson@linaro.org>
      Cc: linux-block@vger.kernel.org
      Cc: linux-kernel@vger.kernel.org
      Cc: linux-mmc@vger.kernel.org
      Cc: linux-pm@vger.kernel.org
      Cc: linux-usb@vger.kernel.org
      Cc: netdev@vger.kernel.org
      Cc: rt@linutronix.de
      Link: http://lkml.kernel.org/r/20160704094342.189813118@linutronix.de
      
      Signed-off-by: default avatarIngo Molnar <mingo@kernel.org>
      53bf837b
  4. 01 Jul, 2016 2 commits
    • Herbert Xu's avatar
      lib/mpi: Do not do sg_virt · 127827b9
      Herbert Xu authored
      
      
      Currently the mpi SG helpers use sg_virt which is completely
      broken.  It happens to work with normal kernel memory but will
      fail with anything that is not linearly mapped.
      
      This patch fixes this by using the SG iterator helpers.
      Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      127827b9
    • Herbert Xu's avatar
      crypto: rsa - Generate fixed-length output · 9b45b7bb
      Herbert Xu authored
      
      
      Every implementation of RSA that we have naturally generates
      output with leading zeroes.  The one and only user of RSA,
      pkcs1pad wants to have those leading zeroes in place, in fact
      because they are currently absent it has to write those zeroes
      itself.
      
      So we shouldn't be stripping leading zeroes in the first place.
      In fact this patch makes rsa-generic produce output with fixed
      length so that pkcs1pad does not need to do any extra work.
      
      This patch also changes DH to use the new interface.
      Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      9b45b7bb
  5. 16 Jun, 2016 1 commit
    • Peter Zijlstra's avatar
      locking/atomic: Implement... · 28aa2bda
      Peter Zijlstra authored
      
      locking/atomic: Implement atomic{,64,_long}_fetch_{add,sub,and,andnot,or,xor}{,_relaxed,_acquire,_release}()
      
      Now that all the architectures have implemented support for these new
      atomic primitives add on the generic infrastructure to expose and use
      it.
      Signed-off-by: default avatarPeter Zijlstra (Intel) <peterz@infradead.org>
      Cc: Andrew Morton <akpm@linux-foundation.org>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Cc: Boqun Feng <boqun.feng@gmail.com>
      Cc: Borislav Petkov <bp@suse.de>
      Cc: Davidlohr Bueso <dave@stgolabs.net>
      Cc: Frederic Weisbecker <fweisbec@gmail.com>
      Cc: Linus Torvalds <torvalds@linux-foundation.org>
      Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
      Cc: Peter Zijlstra <peterz@infradead.org>
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Will Deacon <will.deacon@arm.com>
      Cc: linux-arch@vger.kernel.org
      Cc: linux-kernel@vger.kernel.org
      Signed-off-by: default avatarIngo Molnar <mingo@kernel.org>
      28aa2bda
  6. 14 Jun, 2016 2 commits
  7. 08 Jun, 2016 1 commit
  8. 31 May, 2016 8 commits
    • Nicolai Stange's avatar
      lib/mpi: refactor mpi_read_from_buffer() in terms of mpi_read_raw_data() · 20b5b7f3
      Nicolai Stange authored
      
      
      mpi_read_from_buffer() and mpi_read_raw_data() do basically the same thing
      except that the former extracts the number of payload bits from the first
      two bytes of the input buffer.
      
      Besides that, the data copying logic is exactly the same.
      
      Replace the open coded buffer to MPI instance conversion by a call to
      mpi_read_raw_data().
      Signed-off-by: default avatarNicolai Stange <nicstange@gmail.com>
      Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      20b5b7f3
    • Nicolai Stange's avatar
      lib/mpi: mpi_read_from_buffer(): sanitize short buffer printk · cdf24b42
      Nicolai Stange authored
      
      
      The first two bytes of the input buffer encode its expected length and
      mpi_read_from_buffer() prints a console message if the given buffer is too
      short.
      
      However, there are some oddities with how this message is printed:
      - It is printed at the default loglevel. This is different from the
        one used in the case that the first two bytes' value is unsupportedly
        large, i.e. KERN_INFO.
      - The format specifier '%d' is used for unsigned ints.
      - It prints the values of nread and *ret_nread. This is redundant since
        the former is always the latter + 1.
      
      Clean this up as follows:
      - Use pr_info() rather than printk() with no loglevel.
      - Use the format specifiers '%u' in place if '%d'.
      - Do not print the redundant 'nread' but the more helpful 'nbytes' value.
      Signed-off-by: default avatarNicolai Stange <nicstange@gmail.com>
      Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      cdf24b42
    • Nicolai Stange's avatar
      lib/mpi: mpi_read_from_buffer(): return -EINVAL upon too short buffer · 7af791e0
      Nicolai Stange authored
      
      
      Currently, if the input buffer is shorter than the expected length as
      indicated by its first two bytes, an MPI instance of this expected length
      will be allocated and filled with as much data as is available. The rest
      will remain uninitialized.
      
      Instead of leaving this condition undetected, an error code should be
      reported to the caller.
      
      Since this situation indicates that the input buffer's first two bytes,
      encoding the number of expected bits, are garbled, -EINVAL is appropriate
      here.
      
      If the input buffer is shorter than indicated by its first two bytes,
      make mpi_read_from_buffer() return -EINVAL.
      Get rid of the 'nread' variable: with the new semantics, the total number
      of bytes read from the input buffer is known in advance.
      Signed-off-by: default avatarNicolai Stange <nicstange@gmail.com>
      Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      7af791e0
    • Nicolai Stange's avatar
      lib/digsig: digsig_verify_rsa(): return -EINVAL if modulo length is zero · c5ce7c69
      Nicolai Stange authored
      
      
      Currently, if digsig_verify_rsa() detects that the modulo's length is zero,
      i.e. mlen == 0, it returns -ENOMEM which doesn't really fit here.
      
      Make digsig_verify_rsa() return -EINVAL upon mlen == 0.
      Signed-off-by: default avatarNicolai Stange <nicstange@gmail.com>
      Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      c5ce7c69
    • Nicolai Stange's avatar
      lib/mpi: mpi_read_from_buffer(): return error code · 03cdfaad
      Nicolai Stange authored
      
      
      mpi_read_from_buffer() reads a MPI from a buffer into a newly allocated
      MPI instance. It expects the buffer's leading two bytes to contain the
      number of bits, followed by the actual payload.
      
      On failure, it returns NULL and updates the in/out argument ret_nread
      somewhat inconsistently:
      - If the given buffer is too short to contain the leading two bytes
        encoding the number of bits or their value is unsupported, then
        ret_nread will be cleared.
      - If the allocation of the resulting MPI instance fails, ret_nread is left
        as is.
      
      The only user of mpi_read_from_buffer(), digsig_verify_rsa(), simply checks
      for a return value of NULL and returns -ENOMEM if that happens.
      
      While this is all of cosmetic nature only, there is another error condition
      which currently isn't detectable by the caller of mpi_read_from_buffer():
      if the given buffer is too small to hold the number of bits as encoded in
      its first two bytes, the return value will be non-NULL and *ret_nread > 0.
      
      In preparation of communicating this condition to the caller, let
      mpi_read_from_buffer() return error values by means of the ERR_PTR()
      mechanism.
      
      Make the sole caller of mpi_read_from_buffer(), digsig_verify_rsa(),
      check the return value for IS_ERR() rather than == NULL. If IS_ERR() is
      true, return the associated error value rather than the fixed -ENOMEM.
      Signed-off-by: default avatarNicolai Stange <nicstange@gmail.com>
      Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      03cdfaad
    • Nicolai Stange's avatar
      lib/mpi: mpi_read_raw_data(): fix nbits calculation · eef0df6a
      Nicolai Stange authored
      The number of bits, nbits, is calculated in mpi_read_raw_data() as follows:
      
        nbits = nbytes * 8;
      
      Afterwards, the number of leading zero bits of the first byte get
      subtracted:
      
        nbits -= count_leading_zeros(buffer[0]);
      
      However, count_leading_zeros() takes an unsigned long and thus,
      the u8 gets promoted to an unsigned long.
      
      Thus, the above doesn't subtract the number of leading zeros in the most
      significant nonzero input byte from nbits, but the number of leading
      zeros of the most significant nonzero input byte promoted to unsigned long,
      i.e. BITS_PER_LONG - 8 too many.
      
      Fix this by subtracting
      
        count_leading_zeros(...) - (BITS_PER_LONG - 8)
      
      from nbits only.
      
      Fixes: e1045992
      
       ("MPILIB: Provide a function to read raw data into an
                           MPI")
      Signed-off-by: default avatarNicolai Stange <nicstange@gmail.com>
      Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      eef0df6a
    • Nicolai Stange's avatar
      lib/mpi: mpi_read_raw_data(): purge redundant clearing of nbits · dfd90510
      Nicolai Stange authored
      
      
      In mpi_read_raw_data(), unsigned nbits is calculated as follows:
      
       nbits = nbytes * 8;
      
      and redundantly cleared later on if nbytes == 0:
      
        if (nbytes > 0)
          ...
        else
          nbits = 0;
      
      Purge this redundant clearing for the sake of clarity.
      Signed-off-by: default avatarNicolai Stange <nicstange@gmail.com>
      Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      dfd90510
    • Nicolai Stange's avatar
      lib/mpi: purge mpi_set_buffer() · 4bdf1cfc
      Nicolai Stange authored
      
      
      mpi_set_buffer() has no in-tree users and similar functionality is provided
      by mpi_read_raw_data().
      
      Remove mpi_set_buffer().
      Signed-off-by: default avatarNicolai Stange <nicstange@gmail.com>
      Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      4bdf1cfc
  9. 30 May, 2016 2 commits
  10. 28 May, 2016 1 commit
    • George Spelvin's avatar
      <linux/hash.h>: Add support for architecture-specific functions · 468a9428
      George Spelvin authored
      
      
      This is just the infrastructure; there are no users yet.
      
      This is modelled on CONFIG_ARCH_RANDOM; a CONFIG_ symbol declares
      the existence of <asm/hash.h>.
      
      That file may define its own versions of various functions, and define
      HAVE_* symbols (no CONFIG_ prefix!) to suppress the generic ones.
      
      Included is a self-test (in lib/test_hash.c) that verifies the basics.
      It is NOT in general required that the arch-specific functions compute
      the same thing as the generic, but if a HAVE_* symbol is defined with
      the value 1, then equality is tested.
      Signed-off-by: default avatarGeorge Spelvin <linux@sciencehorizons.net>
      Cc: Geert Uytterhoeven <geert@linux-m68k.org>
      Cc: Greg Ungerer <gerg@linux-m68k.org>
      Cc: Andreas Schwab <schwab@linux-m68k.org>
      Cc: Philippe De Muyter <phdm@macq.eu>
      Cc: linux-m68k@lists.linux-m68k.org
      Cc: Alistair Francis <alistai@xilinx.com>
      Cc: Michal Simek <michal.simek@xilinx.com>
      Cc: Yoshinori Sato <ysato@users.sourceforge.jp>
      Cc: uclinux-h8-devel@lists.sourceforge.jp
      468a9428
  11. 26 May, 2016 1 commit
  12. 25 May, 2016 1 commit
    • Al Viro's avatar
      do "fold checks into iterate_and_advance()" right · 19f18459
      Al Viro authored
      
      
      the only case when we should skip the iterate_and_advance() guts
      is when nothing's left in the iterator, _not_ just when requested
      amount is 0.  Said guts will do nothing in the latter case anyway;
      the problem we tried to deal with in the aforementioned commit is
      that when there's nothing left *and* the amount requested is 0,
      we might end up deferencing one iovec too many; the value we fetch
      from there is discarded in that case, but theoretically it might
      oops if the iovec array ends exactly at the end of page with the
      next page not mapped.
      
      Bailing out on zero size requested had an unexpected side effect -
      zero-length segment in the beginning of iovec array ended up
      throwing do_loop_readv_writev() into infinite spin; we do not
      advance past the empty segment at all.  Reproducer is trivial:
      echo '#include <sys/uio.h>' >a.c
      echo 'main() {char c; struct iovec v[] = {{&c,0},{&c,1}}; readv(0,v,2);}' >>a.c
      cc a.c && ./a.out </proc/uptime
      
      which should end up with the process not hanging.  Probably ought to
      go into LTP or xfstests...
      Signed-off-by: default avatarAl Viro <viro@zeniv.linux.org.uk>
      19f18459
  13. 24 May, 2016 1 commit
  14. 21 May, 2016 17 commits
    • Zhaoxiu Zeng's avatar
      lib/GCD.c: use binary GCD algorithm instead of Euclidean · fff7fb0b
      Zhaoxiu Zeng authored
      
      
      The binary GCD algorithm is based on the following facts:
      	1. If a and b are all evens, then gcd(a,b) = 2 * gcd(a/2, b/2)
      	2. If a is even and b is odd, then gcd(a,b) = gcd(a/2, b)
      	3. If a and b are all odds, then gcd(a,b) = gcd((a-b)/2, b) = gcd((a+b)/2, b)
      
      Even on x86 machines with reasonable division hardware, the binary
      algorithm runs about 25% faster (80% the execution time) than the
      division-based Euclidian algorithm.
      
      On platforms like Alpha and ARMv6 where division is a function call to
      emulation code, it's even more significant.
      
      There are two variants of the code here, depending on whether a fast
      __ffs (find least significant set bit) instruction is available.  This
      allows the unpredictable branches in the bit-at-a-time shifting loop to
      be eliminated.
      
      If fast __ffs is not available, the "even/odd" GCD variant is used.
      
      I use the following code to benchmark:
      
      	#include <stdio.h>
      	#include <stdlib.h>
      	#include <stdint.h>
      	#include <string.h>
      	#include <time.h>
      	#include <unistd.h>
      
      	#define swap(a, b) \
      		do { \
      			a ^= b; \
      			b ^= a; \
      			a ^= b; \
      		} while (0)
      
      	unsigned long gcd0(unsigned long a, unsigned long b)
      	{
      		unsigned long r;
      
      		if (a < b) {
      			swap(a, b);
      		}
      
      		if (b == 0)
      			return a;
      
      		while ((r = a % b) != 0) {
      			a = b;
      			b = r;
      		}
      
      		return b;
      	}
      
      	unsigned long gcd1(unsigned long a, unsigned long b)
      	{
      		unsigned long r = a | b;
      
      		if (!a || !b)
      			return r;
      
      		b >>= __builtin_ctzl(b);
      
      		for (;;) {
      			a >>= __builtin_ctzl(a);
      			if (a == b)
      				return a << __builtin_ctzl(r);
      
      			if (a < b)
      				swap(a, b);
      			a -= b;
      		}
      	}
      
      	unsigned long gcd2(unsigned long a, unsigned long b)
      	{
      		unsigned long r = a | b;
      
      		if (!a || !b)
      			return r;
      
      		r &= -r;
      
      		while (!(b & r))
      			b >>= 1;
      
      		for (;;) {
      			while (!(a & r))
      				a >>= 1;
      			if (a == b)
      				return a;
      
      			if (a < b)
      				swap(a, b);
      			a -= b;
      			a >>= 1;
      			if (a & r)
      				a += b;
      			a >>= 1;
      		}
      	}
      
      	unsigned long gcd3(unsigned long a, unsigned long b)
      	{
      		unsigned long r = a | b;
      
      		if (!a || !b)
      			return r;
      
      		b >>= __builtin_ctzl(b);
      		if (b == 1)
      			return r & -r;
      
      		for (;;) {
      			a >>= __builtin_ctzl(a);
      			if (a == 1)
      				return r & -r;
      			if (a == b)
      				return a << __builtin_ctzl(r);
      
      			if (a < b)
      				swap(a, b);
      			a -= b;
      		}
      	}
      
      	unsigned long gcd4(unsigned long a, unsigned long b)
      	{
      		unsigned long r = a | b;
      
      		if (!a || !b)
      			return r;
      
      		r &= -r;
      
      		while (!(b & r))
      			b >>= 1;
      		if (b == r)
      			return r;
      
      		for (;;) {
      			while (!(a & r))
      				a >>= 1;
      			if (a == r)
      				return r;
      			if (a == b)
      				return a;
      
      			if (a < b)
      				swap(a, b);
      			a -= b;
      			a >>= 1;
      			if (a & r)
      				a += b;
      			a >>= 1;
      		}
      	}
      
      	static unsigned long (*gcd_func[])(unsigned long a, unsigned long b) = {
      		gcd0, gcd1, gcd2, gcd3, gcd4,
      	};
      
      	#define TEST_ENTRIES (sizeof(gcd_func) / sizeof(gcd_func[0]))
      
      	#if defined(__x86_64__)
      
      	#define rdtscll(val) do { \
      		unsigned long __a,__d; \
      		__asm__ __volatile__("rdtsc" : "=a" (__a), "=d" (__d)); \
      		(val) = ((unsigned long long)__a) | (((unsigned long long)__d)<<32); \
      	} while(0)
      
      	static unsigned long long benchmark_gcd_func(unsigned long (*gcd)(unsigned long, unsigned long),
      								unsigned long a, unsigned long b, unsigned long *res)
      	{
      		unsigned long long start, end;
      		unsigned long long ret;
      		unsigned long gcd_res;
      
      		rdtscll(start);
      		gcd_res = gcd(a, b);
      		rdtscll(end);
      
      		if (end >= start)
      			ret = end - start;
      		else
      			ret = ~0ULL - start + 1 + end;
      
      		*res = gcd_res;
      		return ret;
      	}
      
      	#else
      
      	static inline struct timespec read_time(void)
      	{
      		struct timespec time;
      		clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &time);
      		return time;
      	}
      
      	static inline unsigned long long diff_time(struct timespec start, struct timespec end)
      	{
      		struct timespec temp;
      
      		if ((end.tv_nsec - start.tv_nsec) < 0) {
      			temp.tv_sec = end.tv_sec - start.tv_sec - 1;
      			temp.tv_nsec = 1000000000ULL + end.tv_nsec - start.tv_nsec;
      		} else {
      			temp.tv_sec = end.tv_sec - start.tv_sec;
      			temp.tv_nsec = end.tv_nsec - start.tv_nsec;
      		}
      
      		return temp.tv_sec * 1000000000ULL + temp.tv_nsec;
      	}
      
      	static unsigned long long benchmark_gcd_func(unsigned long (*gcd)(unsigned long, unsigned long),
      								unsigned long a, unsigned long b, unsigned long *res)
      	{
      		struct timespec start, end;
      		unsigned long gcd_res;
      
      		start = read_time();
      		gcd_res = gcd(a, b);
      		end = read_time();
      
      		*res = gcd_res;
      		return diff_time(start, end);
      	}
      
      	#endif
      
      	static inline unsigned long get_rand()
      	{
      		if (sizeof(long) == 8)
      			return (unsigned long)rand() << 32 | rand();
      		else
      			return rand();
      	}
      
      	int main(int argc, char **argv)
      	{
      		unsigned int seed = time(0);
      		int loops = 100;
      		int repeats = 1000;
      		unsigned long (*res)[TEST_ENTRIES];
      		unsigned long long elapsed[TEST_ENTRIES];
      		int i, j, k;
      
      		for (;;) {
      			int opt = getopt(argc, argv, "n:r:s:");
      			/* End condition always first */
      			if (opt == -1)
      				break;
      
      			switch (opt) {
      			case 'n':
      				loops = atoi(optarg);
      				break;
      			case 'r':
      				repeats = atoi(optarg);
      				break;
      			case 's':
      				seed = strtoul(optarg, NULL, 10);
      				break;
      			default:
      				/* You won't actually get here. */
      				break;
      			}
      		}
      
      		res = malloc(sizeof(unsigned long) * TEST_ENTRIES * loops);
      		memset(elapsed, 0, sizeof(elapsed));
      
      		srand(seed);
      		for (j = 0; j < loops; j++) {
      			unsigned long a = get_rand();
      			/* Do we have args? */
      			unsigned long b = argc > optind ? strtoul(argv[optind], NULL, 10) : get_rand();
      			unsigned long long min_elapsed[TEST_ENTRIES];
      			for (k = 0; k < repeats; k++) {
      				for (i = 0; i < TEST_ENTRIES; i++) {
      					unsigned long long tmp = benchmark_gcd_func(gcd_func[i], a, b, &res[j][i]);
      					if (k == 0 || min_elapsed[i] > tmp)
      						min_elapsed[i] = tmp;
      				}
      			}
      			for (i = 0; i < TEST_ENTRIES; i++)
      				elapsed[i] += min_elapsed[i];
      		}
      
      		for (i = 0; i < TEST_ENTRIES; i++)
      			printf("gcd%d: elapsed %llu\n", i, elapsed[i]);
      
      		k = 0;
      		srand(seed);
      		for (j = 0; j < loops; j++) {
      			unsigned long a = get_rand();
      			unsigned long b = argc > optind ? strtoul(argv[optind], NULL, 10) : get_rand();
      			for (i = 1; i < TEST_ENTRIES; i++) {
      				if (res[j][i] != res[j][0])
      					break;
      			}
      			if (i < TEST_ENTRIES) {
      				if (k == 0) {
      					k = 1;
      					fprintf(stderr, "Error:\n");
      				}
      				fprintf(stderr, "gcd(%lu, %lu): ", a, b);
      				for (i = 0; i < TEST_ENTRIES; i++)
      					fprintf(stderr, "%ld%s", res[j][i], i < TEST_ENTRIES - 1 ? ", " : "\n");
      			}
      		}
      
      		if (k == 0)
      			fprintf(stderr, "PASS\n");
      
      		free(res);
      
      		return 0;
      	}
      
      Compiled with "-O2", on "VirtualBox 4.4.0-22-generic #38-Ubuntu x86_64" got:
      
        zhaoxiuzeng@zhaoxiuzeng-VirtualBox:~/develop$ ./gcd -r 500000 -n 10
        gcd0: elapsed 10174
        gcd1: elapsed 2120
        gcd2: elapsed 2902
        gcd3: elapsed 2039
        gcd4: elapsed 2812
        PASS
        zhaoxiuzeng@zhaoxiuzeng-VirtualBox:~/develop$ ./gcd -r 500000 -n 10
        gcd0: elapsed 9309
        gcd1: elapsed 2280
        gcd2: elapsed 2822
        gcd3: elapsed 2217
        gcd4: elapsed 2710
        PASS
        zhaoxiuzeng@zhaoxiuzeng-VirtualBox:~/develop$ ./gcd -r 500000 -n 10
        gcd0: elapsed 9589
        gcd1: elapsed 2098
        gcd2: elapsed 2815
        gcd3: elapsed 2030
        gcd4: elapsed 2718
        PASS
        zhaoxiuzeng@zhaoxiuzeng-VirtualBox:~/develop$ ./gcd -r 500000 -n 10
        gcd0: elapsed 9914
        gcd1: elapsed 2309
        gcd2: elapsed 2779
        gcd3: elapsed 2228
        gcd4: elapsed 2709
        PASS
      
      [akpm@linux-foundation.org: avoid #defining a CONFIG_ variable]
      Signed-off-by: default avatarZhaoxiu Zeng <zhaoxiu.zeng@gmail.com>
      Signed-off-by: default avatarGeorge Spelvin <linux@horizon.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      fff7fb0b
    • Matthew Wilcox's avatar
      radix-tree: make radix_tree_descend() more useful · 9e85d811
      Matthew Wilcox authored
      
      
      Now that the shift amount is stored in the node, radix_tree_descend()
      can calculate offset itself from index, which removes several lines of
      code from each of the tree walkers.
      Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
      Cc: Konstantin Khlebnikov <koct9i@gmail.com>
      Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
      Cc: Jan Kara <jack@suse.com>
      Cc: Neil Brown <neilb@suse.de>
      Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      9e85d811
    • Matthew Wilcox's avatar
      radix-tree: introduce radix_tree_replace_clear_tags() · d604c324
      Matthew Wilcox authored
      
      
      In addition to replacing the entry, we also clear all associated tags.
      This is really a one-off special for page_cache_tree_delete() which had
      far too much detailed knowledge about how the radix tree works.
      
      For efficiency, factor node_tag_clear() out of radix_tree_tag_clear() It
      can be used by radix_tree_delete_item() as well as
      radix_tree_replace_clear_tags().
      Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
      Cc: Konstantin Khlebnikov <koct9i@gmail.com>
      Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
      Cc: Jan Kara <jack@suse.com>
      Cc: Neil Brown <neilb@suse.de>
      Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      d604c324
    • Matthew Wilcox's avatar
      radix-tree: tidy up __radix_tree_create() · 89148aa4
      Matthew Wilcox authored
      
      
      1. Rename the existing variable 'slot' to 'child'.
      2. Introduce a new variable called 'slot' which is the address of the
         slot we're dealing with.  This lets us simplify the tree insertion,
         and removes the recalculation of 'slot' at the end of the function.
      3. Using 'slot' in the sibling pointer insertion part makes the code
         more readable.
      Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
      Cc: Konstantin Khlebnikov <koct9i@gmail.com>
      Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
      Cc: Jan Kara <jack@suse.com>
      Cc: Neil Brown <neilb@suse.de>
      Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      89148aa4
    • Matthew Wilcox's avatar
      radix-tree: tidy up range_tag_if_tagged · a8e4da25
      Matthew Wilcox authored
      
      
      Convert radix_tree_range_tag_if_tagged to name the nodes parent, node
      and child instead of node & slot.
      
      Use parent->offset instead of playing games with 'upindex'.
      Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
      Cc: Konstantin Khlebnikov <koct9i@gmail.com>
      Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
      Cc: Jan Kara <jack@suse.com>
      Cc: Neil Brown <neilb@suse.de>
      Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      a8e4da25
    • Matthew Wilcox's avatar
      radix-tree: tidy up next_chunk · 8c1244de
      Matthew Wilcox authored
      
      
      Convert radix_tree_next_chunk to use 'child' instead of 'slot' as the
      name of the child node.  Also use node_maxindex() where it makes sense.
      
      The 'rnode' variable was unnecessary; it doesn't overlap in usage with
      'node', so we can just use 'node' the whole way through the function.
      
      Improve the testcase to start the walk from every index in the carefully
      constructed tree, and to accept any index within the range covered by
      the entry.
      Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
      Cc: Konstantin Khlebnikov <koct9i@gmail.com>
      Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
      Cc: Jan Kara <jack@suse.com>
      Cc: Neil Brown <neilb@suse.de>
      Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      8c1244de
    • Matthew Wilcox's avatar
      radix-tree: change naming conventions in radix_tree_shrink · af49a63e
      Matthew Wilcox authored
      
      
      Use the more standard 'node' and 'child' instead of 'to_free' and
      'slot'.
      Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
      Cc: Konstantin Khlebnikov <koct9i@gmail.com>
      Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
      Cc: Jan Kara <jack@suse.com>
      Cc: Neil Brown <neilb@suse.de>
      Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      af49a63e
    • Matthew Wilcox's avatar
      radix-tree: rename radix_tree_is_indirect_ptr() · b194d16c
      Matthew Wilcox authored
      
      
      As with indirect_to_ptr(), ptr_to_indirect() and
      RADIX_TREE_INDIRECT_PTR, change radix_tree_is_indirect_ptr() to
      radix_tree_is_internal_node().
      Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
      Cc: Konstantin Khlebnikov <koct9i@gmail.com>
      Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
      Cc: Jan Kara <jack@suse.com>
      Cc: Neil Brown <neilb@suse.de>
      Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      b194d16c
    • Matthew Wilcox's avatar
      radix-tree: rename indirect_to_ptr() to entry_to_node() · 4dd6c098
      Matthew Wilcox authored
      
      
      Mirrors the earlier commit introducing node_to_entry().
      
      Also change the type returned to be a struct radix_tree_node pointer.
      That lets us simplify a couple of places in the radix tree shrink &
      extend paths where we could convert an entry into a pointer, modify the
      node, then convert the pointer back into an entry.
      Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
      Cc: Konstantin Khlebnikov <koct9i@gmail.com>
      Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
      Cc: Jan Kara <jack@suse.com>
      Cc: Neil Brown <neilb@suse.de>
      Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      4dd6c098
    • Matthew Wilcox's avatar
      radix-tree: rename ptr_to_indirect() to node_to_entry() · a4db4dce
      Matthew Wilcox authored
      
      
      ptr_to_indirect() was a bad name.  What it really means is "Convert this
      pointer to a node into an entry suitable for storing in the radix tree".
      So node_to_entry() seemed like a better name.
      Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
      Cc: Konstantin Khlebnikov <koct9i@gmail.com>
      Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
      Cc: Jan Kara <jack@suse.com>
      Cc: Neil Brown <neilb@suse.de>
      Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      a4db4dce
    • Matthew Wilcox's avatar
      radix-tree: rename INDIRECT_PTR to INTERNAL_NODE · 30ff46cc
      Matthew Wilcox authored
      
      
      The name RADIX_TREE_INDIRECT_PTR doesn't really match the meaning.
      RADIX_TREE_INTERNAL_NODE is a better name.
      Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
      Cc: Konstantin Khlebnikov <koct9i@gmail.com>
      Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
      Cc: Jan Kara <jack@suse.com>
      Cc: Neil Brown <neilb@suse.de>
      Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      30ff46cc
    • Matthew Wilcox's avatar
      radix-tree: remove root->height · d0891265
      Matthew Wilcox authored
      
      
      The only remaining references to root->height were in extend and shrink,
      where it was updated.  Now we can remove it entirely.
      Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
      Reviewed-by: default avatarRoss Zwisler <ross.zwisler@linux.intel.com>
      Cc: Konstantin Khlebnikov <koct9i@gmail.com>
      Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
      Cc: Jan Kara <jack@suse.com>
      Cc: Neil Brown <neilb@suse.de>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      d0891265
    • Matthew Wilcox's avatar
      radix-tree: remove a use of root->height from delete_node · fb209019
      Matthew Wilcox authored
      
      
      If radix_tree_shrink returns whether it managed to shrink, then
      __radix_tree_delete_node doesn't ned to query the tree to find out
      whether it did any work or not.
      Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
      Cc: Konstantin Khlebnikov <koct9i@gmail.com>
      Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
      Cc: Jan Kara <jack@suse.com>
      Cc: Neil Brown <neilb@suse.de>
      Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      fb209019
    • Matthew Wilcox's avatar
      radix-tree: replace node->height with node->shift · c12e51b0
      Matthew Wilcox authored
      
      
      node->shift represents the shift necessary for looking in the slots
      array at this level.  It is equal to the old (node->height - 1) *
      RADIX_TREE_MAP_SHIFT.
      Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
      Reviewed-by: default avatarRoss Zwisler <ross.zwisler@linux.intel.com>
      Cc: Konstantin Khlebnikov <koct9i@gmail.com>
      Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
      Cc: Jan Kara <jack@suse.com>
      Cc: Neil Brown <neilb@suse.de>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      c12e51b0
    • Matthew Wilcox's avatar
      radix-tree: split node->path into offset and height · 0c7fa0a8
      Matthew Wilcox authored
      
      
      Neither piece of information we're storing in node->path can be larger
      than 64, so store each in its own unsigned char instead of shifting and
      masking to store them both in an unsigned int.
      Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
      Reviewed-by: default avatarRoss Zwisler <ross.zwisler@linux.intel.com>
      Cc: Konstantin Khlebnikov <koct9i@gmail.com>
      Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
      Cc: Jan Kara <jack@suse.com>
      Cc: Neil Brown <neilb@suse.de>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      0c7fa0a8
    • Matthew Wilcox's avatar
      radix-tree: miscellaneous fixes · 2fcd9005
      Matthew Wilcox authored
      
      
      Typos, whitespace, grammar, line length, using the correct types, etc.
      Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
      Reviewed-by: default avatarRoss Zwisler <ross.zwisler@linux.intel.com>
      Cc: Konstantin Khlebnikov <koct9i@gmail.com>
      Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
      Cc: Jan Kara <jack@suse.com>
      Cc: Neil Brown <neilb@suse.de>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      2fcd9005
    • Matthew Wilcox's avatar
      radix-tree: add copyright statements · 6b053b8e
      Matthew Wilcox authored
      
      
      The multiorder support is a sufficiently large feature to be worth
      adding copyrigt lines for.
      Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
      Reviewed-by: default avatarRoss Zwisler <ross.zwisler@linux.intel.com>
      Cc: Konstantin Khlebnikov <koct9i@gmail.com>
      Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
      Cc: Jan Kara <jack@suse.com>
      Cc: Neil Brown <neilb@suse.de>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      6b053b8e