sfrench/cifs-2.6.git
3 years agoMerge tag 'rtc-4.7' of git://git.kernel.org/pub/scm/linux/kernel/git/abelloni/linux
Linus Torvalds [Sat, 21 May 2016 17:42:11 +0000 (10:42 -0700)]
Merge tag 'rtc-4.7' of git://git./linux/kernel/git/abelloni/linux

Pull RTC updates from Alexandre Belloni:
 "Subsystem wide cleanups:
   - Use IS_ENABLED() instead of checking for built-in or module
   - remove useless DRV_VERSION
   - remove CLK_IS_ROOT
   - remove UIE signaling

  Drivers:
   - ds1302: rewritten to be a proper SPI device driver
   - m41t80: huge cleanup, alarm, wakelarm ans oscialltor failure
     detection support
   - rv3029: switch to regmap to handle rv3049, alarm support, fixes
   - zynqmp: enable switching to battery power, fixes
   - small fixes for at91sam9, da9053, ds1307, ds1685, ds3232, r2025,
     sa1100, snvs, stmp3xxx, tps6586x"

* tag 'rtc-4.7' of git://git.kernel.org/pub/scm/linux/kernel/git/abelloni/linux: (40 commits)
  rtc: tps6586x: rename so module can be autoloaded
  rtc: rv3029: hide unused i2c device table
  rtc: rs5c372: r2025: fix check for 'oscillator halted' condition
  rtc: rv3029: add alarm IRQ
  rtc: rv3029: fix set_time function
  rtc: rv3029: fix alarm support
  rtc: rv3029: Remove some checks and warnings
  rtc: rv3029: Add support of RV3049
  rtc: rv3029: convert to use regmap
  rtc: rv3029: remove 'i2c' in functions names
  rtc: stmp3xxx: print message on error
  rtc: Use IS_ENABLED() instead of checking for built-in or module
  rtc: ds3232: fix call trace when rtc->ops_lock is used as NULL
  rtc: snvs: return error in case enable_irq_wake fails
  rtc: zynqmp: Update seconds time programming logic
  rtc: sa1100: DT spelling s/interrupt-name/interrupt-names/
  rtc: mc13xxx: remove UIE signaling
  rtc: mxc: remove UIE signaling
  rtc: ds1307: Remove CLK_IS_ROOT
  rtc: hym8563: Remove CLK_IS_ROOT
  ...

3 years agoMerge branch 'mailbox-for-next' of git://git.linaro.org/landing-teams/working/fujitsu...
Linus Torvalds [Sat, 21 May 2016 17:32:48 +0000 (10:32 -0700)]
Merge branch 'mailbox-for-next' of git://git.linaro.org/landing-teams/working/fujitsu/integration

Pull mailbox updates from Jassi Brar:
 "OMAP:
   - Remove non-DT support from mailbox driver
   - Move PM from client calls to native driver suspend/resume
   - Trivial cleanups to make checkpatch happy

  STI:
   - Check return from devm_ioremap_resource as ERR_PTR, not NULL"

* 'mailbox-for-next' of git://git.linaro.org/landing-teams/working/fujitsu/integration:
  mailbox: Fix devm_ioremap_resource error detection code
  mailbox/omap: kill omap_mbox_{save/restore}_ctx() functions
  mailbox/omap: check for any unread messages during suspend
  mailbox/omap: add support for suspend/resume
  mailbox/omap: store mailbox interrupt type in omap_mbox_device
  mailbox/omap: add blank lines after declarations
  mailbox/omap: remove FSF mailing address paragraph
  mailbox/omap: use variable name for sizeof() operator
  mailbox/omap: drop legacy platform device support

3 years agox86 isa: add back X86_32 dependency on CONFIG_ISA
Linus Torvalds [Sat, 21 May 2016 17:25:19 +0000 (10:25 -0700)]
x86 isa: add back X86_32 dependency on CONFIG_ISA

Commit b3c1be1b789c ("base: isa: Remove X86_32 dependency") made ISA
support available on x86-64 too.  That's not right - while there are
some LPC-style devices that might be useful still and be based on
ISA-like IP blocks, that is *not* an excuse to try to enable any random
legacy drivers.

Such drivers should be individually enabled and made to perhaps depend
on ISA_DMA_API instead (which we have continued to support on x86-64).
Or we could add another "ISA_XYZ_API" that we support that doesn't
enable random old drivers that aren't even 64-bit clean nor do we have
any test coverage for.

Turning off ISA will now also turn off some drivers that have been
marked as depending on it as part of this series, and that used to work
on modern platforms.

See for example commits ad7afc38eab3..cc736607c86d, which may also need
to be reverted.

This commit means that the warnings that came in due to enabling ISA
widely are now gone again.

Acked-by: William Breathitt Gray <vilhelm.gray@gmail.com>
Cc: Linus Walleij <linus.walleij@linaro.org>
Cc: Guenter Roeck <linux@roeck-us.net>
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agortc: tps6586x: rename so module can be autoloaded
Nicolas Chauvet [Tue, 10 May 2016 10:26:42 +0000 (12:26 +0200)]
rtc: tps6586x: rename so module can be autoloaded

This module is loaded by the related mfd driver which has
the needed MODULE_DEVICE_TABLE(i2c,...).

This patch fix the modalias when the rtc driver is built
as a module, so the right name is used.
Everything operates correctly when this module is builtin.

Fixes: esdc59ed3865 ("rtc: add RTC driver for TPS6586x")
Signed-off-by: Nicolas Chauvet <kwizart@gmail.com>
Signed-off-by: Alexandre Belloni <alexandre.belloni@free-electrons.com>
3 years agortc: rv3029: hide unused i2c device table
Arnd Bergmann [Wed, 4 May 2016 09:50:02 +0000 (11:50 +0200)]
rtc: rv3029: hide unused i2c device table

The added support for SPI mode made it possible to configure the driver
when I2C is disabled, leaving an unused device table:

drivers/rtc/rtc-rv3029c2.c:794:29: error: 'rv3029_id' defined but not used [-Werror=unused-variable]

This moves the table inside of the #ifdef section that has the
only user, to avoid the harmless warning.

Signed-off-by: Arnd Bergmann <arnd@arndb.de>
Fixes: d08f50dd0afc ("rtc: rv3029: Add support of RV3049")
Signed-off-by: Alexandre Belloni <alexandre.belloni@free-electrons.com>
3 years agortc: rs5c372: r2025: fix check for 'oscillator halted' condition
Thomas Koeller [Wed, 2 Jun 2010 13:53:05 +0000 (15:53 +0200)]
rtc: rs5c372: r2025: fix check for 'oscillator halted' condition

The R2025SD chip, according to its data sheet, sets the /XST
bit to zero if the oscillator stops. Hence the check for this
condition was wrong.

Signed-off-by: Thomas Koeller <thomas.koeller@baslerweb.com>
Signed-off-by: Alexandre Belloni <alexandre.belloni@free-electrons.com>
3 years agortc: rv3029: add alarm IRQ
Mylène Josserand [Tue, 3 May 2016 09:54:38 +0000 (11:54 +0200)]
rtc: rv3029: add alarm IRQ

Add the alarm IRQ functionality.

Signed-off-by: Mylène Josserand <mylene.josserand@free-electrons.com>
Signed-off-by: Alexandre Belloni <alexandre.belloni@free-electrons.com>
3 years agortc: rv3029: fix set_time function
Mylène Josserand [Tue, 3 May 2016 09:54:37 +0000 (11:54 +0200)]
rtc: rv3029: fix set_time function

The bin2bcd function in set_time is uncorrect on weekdays as the
bit mask should be done at the end of arithmetic operations.

Signed-off-by: Mylène Josserand <mylene.josserand@free-electrons.com>
Signed-off-by: Alexandre Belloni <alexandre.belloni@free-electrons.com>
3 years agortc: rv3029: fix alarm support
Mylène Josserand [Tue, 3 May 2016 09:54:36 +0000 (11:54 +0200)]
rtc: rv3029: fix alarm support

The RTC RV3029 handles different types of alarms : seconds, minutes, ...
These alarms can be enabled or disabled individually using an AE_x bit
which is the last bit (BIT(7)) on each alarm registers.

To prepare the alarm IRQ support, the current code enables all the alarm
types by setting each AE_x to 1.
It also fixes others alarms issues :
   - month and weekday errors : it was performing -1 instead of +1.
   - wrong use of bit mask with bin2bcd

Signed-off-by: Mylène Josserand <mylene.josserand@free-electrons.com>
Signed-off-by: Alexandre Belloni <alexandre.belloni@free-electrons.com>
3 years agortc: rv3029: Remove some checks and warnings
Mylène Josserand [Tue, 3 May 2016 09:54:35 +0000 (11:54 +0200)]
rtc: rv3029: Remove some checks and warnings

Remove some checks from checkpatch such as spaces around arithmetic
operations or prefer "unsigned int".

Signed-off-by: Mylène Josserand <mylene.josserand@free-electrons.com>
Signed-off-by: Alexandre Belloni <alexandre.belloni@free-electrons.com>
3 years agortc: rv3029: Add support of RV3049
Mylène Josserand [Tue, 3 May 2016 09:54:34 +0000 (11:54 +0200)]
rtc: rv3029: Add support of RV3049

Add support of Microcrystal RV3049 RTC (SPI) using regmap on the
RV3029 (I2C) driver.

Signed-off-by: Mylène Josserand <mylene.josserand@free-electrons.com>
Signed-off-by: Alexandre Belloni <alexandre.belloni@free-electrons.com>
3 years agortc: rv3029: convert to use regmap
Mylène Josserand [Tue, 3 May 2016 09:54:33 +0000 (11:54 +0200)]
rtc: rv3029: convert to use regmap

To add support of rv3049, the current driver is converted to use regmap.

Signed-off-by: Mylène Josserand <mylene.josserand@free-electrons.com>
Signed-off-by: Alexandre Belloni <alexandre.belloni@free-electrons.com>
3 years agortc: rv3029: remove 'i2c' in functions names
Mylène Josserand [Tue, 3 May 2016 09:54:32 +0000 (11:54 +0200)]
rtc: rv3029: remove 'i2c' in functions names

To prepare the use of regmap to add the support of RV-3049, all the
'i2c' in functions's names are removed.

Signed-off-by: Mylène Josserand <mylene.josserand@free-electrons.com>
Signed-off-by: Alexandre Belloni <alexandre.belloni@free-electrons.com>
3 years agoMerge branch 'akpm' (patches from Andrew)
Linus Torvalds [Sat, 21 May 2016 05:31:33 +0000 (22:31 -0700)]
Merge branch 'akpm' (patches from Andrew)

Merge more updates from Andrew Morton:

 - the rest of MM

 - KASAN updates

 - procfs updates

 - exit, fork updates

 - printk updates

 - lib/ updates

 - radix-tree testsuite updates

 - checkpatch updates

 - kprobes updates

 - a few other misc bits

* emailed patches from Andrew Morton <akpm@linux-foundation.org>: (162 commits)
  samples/kprobes: print out the symbol name for the hooks
  samples/kprobes: add a new module parameter
  kprobes: add the "tls" argument for j_do_fork
  init/main.c: simplify initcall_blacklisted()
  fs/efs/super.c: fix return value
  checkpatch: improve --git <commit-count> shortcut
  checkpatch: reduce number of `git log` calls with --git
  checkpatch: add support to check already applied git commits
  checkpatch: add --list-types to show message types to show or ignore
  checkpatch: advertise the --fix and --fix-inplace options more
  checkpatch: whine about ACCESS_ONCE
  checkpatch: add test for keywords not starting on tabstops
  checkpatch: improve CONSTANT_COMPARISON test for structure members
  checkpatch: add PREFER_IS_ENABLED test
  lib/GCD.c: use binary GCD algorithm instead of Euclidean
  radix-tree: free up the bottom bit of exceptional entries for reuse
  dax: move RADIX_DAX_ definitions to dax.c
  radix-tree: make radix_tree_descend() more useful
  radix-tree: introduce radix_tree_replace_clear_tags()
  radix-tree: tidy up __radix_tree_create()
  ...

3 years agoMerge tag 'staging-4.7-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh...
Linus Torvalds [Sat, 21 May 2016 05:20:48 +0000 (22:20 -0700)]
Merge tag 'staging-4.7-rc1' of git://git./linux/kernel/git/gregkh/staging

Pull staging and IIO driver updates from Greg KH:
 "Here's the big staging and iio driver update for 4.7-rc1.

  I think we almost broke even with this release, only adding a few more
  lines than we removed, which isn't bad overall given that there's a
  bunch of new iio drivers added.

  The Lustre developers seem to have woken up from their sleep and have
  been doing a great job in cleaning up the code and pruning unused or
  old cruft, the filesystem is almost readable :)

  Other than that, just a lot of basic coding style cleanups in the
  churn.  All have been in linux-next for a while with no reported
  issues"

* tag 'staging-4.7-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/staging: (938 commits)
  Staging: emxx_udc: emxx_udc: fixed coding style issue
  staging/gdm724x: fix "alignment should match open parenthesis" issues
  staging/gdm724x: Fix avoid CamelCase
  staging: unisys: rename misleading var ii with frag
  staging: unisys: visorhba: switch success handling to error handling
  staging: unisys: visorhba: main path needs to flow down the left margin
  staging: unisys: visorinput: handle_locking_key() simplifications
  staging: unisys: visorhba: fail gracefully for thread creation failures
  staging: unisys: visornic: comment restructuring and removing bad diction
  staging: unisys: fix format string %Lx to %llx for u64
  staging: unisys: remove unused struct members
  staging: unisys: visorchannel: correct variable misspelling
  staging: unisys: visorhba: replace functionlike macro with function
  staging: dgnc: Need to check for NULL of ch
  staging: dgnc: remove redundant condition check
  staging: dgnc: fix 'line over 80 characters'
  staging: dgnc: clean up the dgnc_get_modem_info()
  staging: lustre: lnet: enable configuration per NI interface
  staging: lustre: o2iblnd: properly set ibr_why
  staging: lustre: o2iblnd: remove last of kiblnd_tunables_fini
  ...

3 years agoMerge tag 'driver-core-4.7-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git...
Linus Torvalds [Sat, 21 May 2016 04:26:15 +0000 (21:26 -0700)]
Merge tag 'driver-core-4.7-rc1' of git://git./linux/kernel/git/gregkh/driver-core

Pull driver core updates from Greg KH:
 "Here's the "big" driver core update for 4.7-rc1.

  Mostly just debugfs changes, the long-known and messy races with
  removing debugfs files should be fixed thanks to the great work of
  Nicolai Stange.  We also have some isa updates in here (the x86
  maintainers told me to take it through this tree), a new warning when
  we run out of dynamic char major numbers, and a few other assorted
  changes, details in the shortlog.

  All have been in linux-next for some time with no reported issues"

* tag 'driver-core-4.7-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/driver-core: (32 commits)
  Revert "base: dd: don't remove driver_data in -EPROBE_DEFER case"
  gpio: ws16c48: Utilize the ISA bus driver
  gpio: 104-idio-16: Utilize the ISA bus driver
  gpio: 104-idi-48: Utilize the ISA bus driver
  gpio: 104-dio-48e: Utilize the ISA bus driver
  watchdog: ebc-c384_wdt: Utilize the ISA bus driver
  iio: stx104: Utilize the module_isa_driver and max_num_isa_dev macros
  iio: stx104: Add X86 dependency to STX104 Kconfig option
  Documentation: Add ISA bus driver documentation
  isa: Implement the max_num_isa_dev macro
  isa: Implement the module_isa_driver macro
  pnp: pnpbios: Add explicit X86_32 dependency to PNPBIOS
  isa: Decouple X86_32 dependency from the ISA Kconfig option
  driver-core: use 'dev' argument in dev_dbg_ratelimited stub
  base: dd: don't remove driver_data in -EPROBE_DEFER case
  kernfs: Move faulting copy_user operations outside of the mutex
  devcoredump: add scatterlist support
  debugfs: unproxify files created through debugfs_create_u32_array()
  debugfs: unproxify files created through debugfs_create_blob()
  debugfs: unproxify files created through debugfs_create_bool()
  ...

3 years agoMerge tag 'char-misc-4.7-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh...
Linus Torvalds [Sat, 21 May 2016 04:20:31 +0000 (21:20 -0700)]
Merge tag 'char-misc-4.7-rc1' of git://git./linux/kernel/git/gregkh/char-misc

Pull char / misc driver updates from Greg KH:
 "Here's the big char and misc driver update for 4.7-rc1.

  Lots of different tiny driver subsystems have updates here with new
  drivers and functionality.  Details in the shortlog.

  All have been in linux-next with no reported issues for a while"

* tag 'char-misc-4.7-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/char-misc: (125 commits)
  mcb: Delete num_cells variable which is not required
  mcb: Fixed bar number assignment for the gdd
  mcb: Replace ioremap and request_region with the devm version
  mcb: Implement bus->dev.release callback
  mcb: export bus information via sysfs
  mcb: Correctly initialize the bus's device
  mei: bus: call mei_cl_read_start under device lock
  coresight: etb10: adjust read pointer only when needed
  coresight: configuring ETF in FIFO mode when acting as link
  coresight: tmc: implementing TMC-ETF AUX space API
  coresight: moving struct cs_buffers to header file
  coresight: tmc: keep track of memory width
  coresight: tmc: make sysFS and Perf mode mutually exclusive
  coresight: tmc: dump system memory content only when needed
  coresight: tmc: adding mode of operation for link/sinks
  coresight: tmc: getting rid of multiple read access
  coresight: tmc: allocating memory when needed
  coresight: tmc: making prepare/unprepare functions generic
  coresight: tmc: splitting driver in ETB/ETF and ETR components
  coresight: tmc: cleaning up header file
  ...

3 years agoMerge tag 'usb-4.7-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/usb
Linus Torvalds [Sat, 21 May 2016 04:12:25 +0000 (21:12 -0700)]
Merge tag 'usb-4.7-rc1' of git://git./linux/kernel/git/gregkh/usb

Pull USB updates from Greg KH:
 "Here's the big pull request for USB and PHY drivers for 4.7-rc1

  Full details in the shortlog, but it's the normal major gadget driver
  updates, phy updates, new usbip code, as well as a bit of lots of
  other stuff.

  All have been in linux-next with no reported issues"

* tag 'usb-4.7-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/usb: (164 commits)
  USB: serial: ti_usb_3410_5052: add MOXA UPORT 11x0 support
  USB: serial: fix minor-number allocation
  USB: serial: quatech2: fix use-after-free in probe error path
  USB: serial: mxuport: fix use-after-free in probe error path
  USB: serial: keyspan: fix debug and error messages
  USB: serial: keyspan: fix URB unlink
  USB: serial: keyspan: fix use-after-free in probe error path
  USB: serial: io_edgeport: fix memory leaks in probe error path
  USB: serial: io_edgeport: fix memory leaks in attach error path
  usb: Remove unnecessary space before operator ','.
  usb: Remove unnecessary space before open square bracket.
  USB: FHCI: avoid redundant condition
  usb: host: xhci-rcar: Avoid long wait in xhci_reset()
  usb/host/fotg210: remove dead code in create_sysfs_files
  usb: wusbcore: Do not initialise statics to 0.
  usb: wusbcore: Remove space before ',' and '(' .
  USB: serial: cp210x: clean up CRTSCTS flag code
  USB: serial: cp210x: get rid of magic numbers in CRTSCTS flag code
  USB: serial: cp210x: fix hardware flow-control disable
  USB: serial: option: add even more ZTE device ids
  ...

3 years agoMerge tag 'tty-4.7-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/tty
Linus Torvalds [Sat, 21 May 2016 03:57:27 +0000 (20:57 -0700)]
Merge tag 'tty-4.7-rc1' of git://git./linux/kernel/git/gregkh/tty

Pull tty and serial driver updates from Greg KH:
 "Here's the large TTY and Serial driver update for 4.7-rc1.

  A few new serial drivers are added here, and Peter has fixed a bunch
  of long-standing bugs in the tty layer and serial drivers as normal.
  Full details in the shortlog.

  All of these have been in linux-next for a while with no reported
  issues"

* tag 'tty-4.7-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/tty: (88 commits)
  MAINTAINERS: 8250: remove website reference
  serial: core: Fix port mutex assert if lockdep disabled
  serial: 8250_dw: fix wrong logic in dw8250_check_lcr()
  tty: vt, finish looping on duplicate
  tty: vt, return error when con_startup fails
  QE-UART: add "fsl,t1040-ucc-uart" to of_device_id
  serial: mctrl_gpio: Drop support for out1-gpios and out2-gpios
  serial: 8250dw: Add device HID for future AMD UART controller
  Fix OpenSSH pty regression on close
  serial: mctrl_gpio: add IRQ locking
  serial: 8250: Integrate Fintek into 8250_base
  serial: mps2-uart: add support for early console
  serial: mps2-uart: add MPS2 UART driver
  dt-bindings: document the MPS2 UART bindings
  serial: sirf: Use generic uart-has-rtscts DT property
  serial: sirf: Introduce helper variable struct device_node *np
  serial: mxs-auart: Use generic uart-has-rtscts DT property
  serial: imx: Use generic uart-has-rtscts DT property
  doc: DT: Add Generic Serial Device Tree Bindings
  serial: 8250: of: Make tegra_serial_handle_break() static
  ...

3 years agoMerge tag 'clk-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/clk/linux
Linus Torvalds [Sat, 21 May 2016 03:18:12 +0000 (20:18 -0700)]
Merge tag 'clk-for-linus' of git://git./linux/kernel/git/clk/linux

Pull clk updates from Stephen Boyd:
 "It's the usual big pile of driver updates and additions, but we do
  have a couple core changes in here as well.

  Core:

   - CLK_IS_CRITICAL support has been added.  This should allow drivers
     to properly express that a certain clk should stay on even if their
     prepare/enable count drops to 0 (and in turn the parents of these
     clks should stay enabled).

   - A clk registration API has been added, clk_hw_register(), and an OF
     clk provider API has been added, of_clk_add_hw_provider().  These
     APIs have been put in place to further split clk providers from clk
     consumers, with the goal being to have clk providers never deal
     with struct clk pointers at all.  Conversion of provider drivers is
     on going.  clkdev has also gained support for registering clk_hw
     pointers directly so we can convert drivers that don't use
     devicetree.

  New Drivers:

   - Marvell ap806 and cp110 system controllers (with clks inside!)
   - Hisilicon Hi3519 clock and reset controller
   - Axis ARTPEC-6 clock controllers
   - Oxford Semiconductor OXNAS clock controllers
   - AXS10X I2S PLL
   - Rockchip RK3399 clock and reset controller

  Updates:

   - MMC2 and UART2 clks on Samsung Exynos 3250, ACLK on Samsung Exynos
     542x SoCs, and some more clk ID exporting for bus frequency scaling
   - Proper BCM2835 PCM clk support and various other clks
   - i.MX clk updates for i.MX6SX, i.MX7, and VF610
   - Renesas updates for R-Car H3
   - Tegra210 got updates for DisplayPort and HDMI 2.0
   - Rockchip driver refactorings and fixes due to adding RK3399 support"

* tag 'clk-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/clk/linux: (139 commits)
  clk: fix critical clock locking
  clk: qcom: mmcc-8996: Remove clocks that should be controlled by RPM
  clk: ingenic: Allow divider value to be divided
  clk: sunxi: Add display and TCON0 clocks driver
  clk: rockchip: drop old_rate calculation on pll rate changes
  clk: rockchip: simplify GRF handling in pll clocks
  clk: rockchip: lookup General Register Files in rockchip_clk_init
  clk: rockchip: fix the rk3399 sdmmc sample / drv name
  clk: mvebu: new driver for Armada CP110 system controller
  dt-bindings: arm: add DT binding for Marvell CP110 system controller
  clk: mvebu: new driver for Armada AP806 system controller
  clk: hisilicon: add CRG driver for hi3519 soc
  clk: hisilicon: export some hisilicon APIs to modules
  reset: hisilicon: add reset controller driver for hisilicon SOCs
  clk: bcm/kona: Do not use sizeof on pointer type
  clk: qcom: msm8916: Fix crypto clock flags
  clk: nxp: lpc18xx: Initialize clk_init_data::flags to 0
  clk/axs10x: Add I2S PLL clock driver
  clk: imx7d: fix ahb clock mux 1
  clk: fix comment of devm_clk_hw_register()
  ...

3 years agoMerge git://git.kernel.org/pub/scm/linux/kernel/git/davem/net
Linus Torvalds [Sat, 21 May 2016 03:01:26 +0000 (20:01 -0700)]
Merge git://git./linux/kernel/git/davem/net

Pull networking fixes and more updates from David Miller:

 1) Tunneling fixes from Tom Herbert and Alexander Duyck.

 2) AF_UNIX updates some struct sock bit fields with the socket lock,
    whereas setsockopt() sets overlapping ones with locking.  Seperate
    out the synchronized vs.  the AF_UNIX unsynchronized ones to avoid
    corruption.  From Andrey Ryabinin.

 3) Mount BPF filesystem with mount_nodev rather than mount_ns, from
    Eric Biederman.

 4) A couple kmemdup conversions, from Muhammad Falak R Wani.

 5) BPF verifier fixes from Alexei Starovoitov.

 6) Don't let tunneled UDP packets get stuck in socket queues, if
    something goes wrong during the encapsulation just drop the packet
    rather than signalling an error up the call stack.  From Hannes
    Frederic Sowa.

 7) SKB ref after free in batman-adv, from Florian Westphal.

 8) TCP iSCSI, ocfs2, rds, and tipc have to disable BH in it's TCP
    callbacks since the TCP stack runs pre-emptibly now.  From Eric
    Dumazet.

 9) Fix crash in fixed_phy_add, from Rabin Vincent.

10) Fix length checks in xen-netback, from Paul Durrant.

11) Fix mixup in KEY vs KEYID macsec attributes, from Sabrina Dubroca.

12) RDS connection spamming bug fixes from Sowmini Varadhan

* git://git.kernel.org/pub/scm/linux/kernel/git/davem/net: (152 commits)
  net: suppress warnings on dev_alloc_skb
  uapi glibc compat: fix compilation when !__USE_MISC in glibc
  udp: prevent skbs lingering in tunnel socket queues
  bpf: teach verifier to recognize imm += ptr pattern
  bpf: support decreasing order in direct packet access
  net: usb: ch9200: use kmemdup
  ps3_gelic: use kmemdup
  net:liquidio: use kmemdup
  bpf: Use mount_nodev not mount_ns to mount the bpf filesystem
  net: cdc_ncm: update datagram size after changing mtu
  tuntap: correctly wake up process during uninit
  intel: Add support for IPv6 IP-in-IP offload
  ip6_gre: Do not allow segmentation offloads GRE_CSUM is enabled with FOU/GUE
  RDS: TCP: Avoid rds connection churn from rogue SYNs
  RDS: TCP: rds_tcp_accept_worker() must exit gracefully when terminating rds-tcp
  net: sock: move ->sk_shutdown out of bitfields.
  ipv6: Don't reset inner headers in ip6_tnl_xmit
  ip4ip6: Support for GSO/GRO
  ip6ip6: Support for GSO/GRO
  ipv6: Set features for IPv6 tunnels
  ...

3 years agolocking,qspinlock: Fix spin_is_locked() and spin_unlock_wait()
Peter Zijlstra [Fri, 20 May 2016 16:04:36 +0000 (18:04 +0200)]
locking,qspinlock: Fix spin_is_locked() and spin_unlock_wait()

Similar to commits:

  51d7d5205d33 ("powerpc: Add smp_mb() to arch_spin_is_locked()")
  d86b8da04dfa ("arm64: spinlock: serialise spin_unlock_wait against concurrent lockers")

qspinlock suffers from the fact that the _Q_LOCKED_VAL store is
unordered inside the ACQUIRE of the lock.

And while this is not a problem for the regular mutual exclusive
critical section usage of spinlocks, it breaks creative locking like:

spin_lock(A) spin_lock(B)
spin_unlock_wait(B) if (!spin_is_locked(A))
do_something()   do_something()

In that both CPUs can end up running do_something at the same time,
because our _Q_LOCKED_VAL store can drop past the spin_unlock_wait()
spin_is_locked() loads (even on x86!!).

To avoid making the normal case slower, add smp_mb()s to the less used
spin_unlock_wait() / spin_is_locked() side of things to avoid this
problem.

Reported-and-tested-by: Davidlohr Bueso <dave@stgolabs.net>
Reported-by: Giovanni Gherdovich <ggherdovich@suse.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Cc: stable@vger.kernel.org # v4.2 and later
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoMerge branch 'for-next' of git://git.samba.org/sfrench/cifs-2.6
Linus Torvalds [Sat, 21 May 2016 02:16:12 +0000 (19:16 -0700)]
Merge branch 'for-next' of git://git.samba.org/sfrench/cifs-2.6

Pull cifs fixes from Steve French:
 "Two small cifs fixes, including one spnego upcall cifs security fix
  for stable"

* 'for-next' of git://git.samba.org/sfrench/cifs-2.6:
  CIFS: Remove some obsolete comments
  cifs: Create dedicated keyring for spnego operations

3 years agosamples/kprobes: print out the symbol name for the hooks
Huang Shijie [Sat, 21 May 2016 00:04:36 +0000 (17:04 -0700)]
samples/kprobes: print out the symbol name for the hooks

Print out the symbol name for the hooks, it makes the logs more
readable.

Link: http://lkml.kernel.org/r/1463535417-29637-2-git-send-email-shijie.huang@arm.com
Signed-off-by: Huang Shijie <shijie.huang@arm.com>
Cc: Petr Mladek <pmladek@suse.com>
Cc: Steve Capper <steve.capper@arm.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agosamples/kprobes: add a new module parameter
Huang Shijie [Sat, 21 May 2016 00:04:33 +0000 (17:04 -0700)]
samples/kprobes: add a new module parameter

Add a new module parameter which can be used as the symbol name.

Without this patch, we can only test the "_do_fork" function with this
kernel module.  With this patch, the module becomes more flexible; we
can test any functions with this module with

# insmod kprobe_example.ko symbol="xxx"

Link: http://lkml.kernel.org/r/1463535417-29637-1-git-send-email-shijie.huang@arm.com
Signed-off-by: Huang Shijie <shijie.huang@arm.com>
Cc: Petr Mladek <pmladek@suse.com>
Cc: Steve Capper <steve.capper@arm.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agokprobes: add the "tls" argument for j_do_fork
Huang Shijie [Sat, 21 May 2016 00:04:30 +0000 (17:04 -0700)]
kprobes: add the "tls" argument for j_do_fork

Commit 3033f14ab78c ("clone: support passing tls argument via C rather
than pt_regs magic") added the tls argument for _do_fork().  This patch
adds the "tls" argument for j_do_fork to make it match _do_fork().

Signed-off-by: Huang Shijie <shijie.huang@arm.com>
Acked-by: Steve Capper <steve.capper@arm.com>
Reviewed-by: Josh Triplett <josh@joshtriplett.org>
Cc: Masami Hiramatsu <masami.hiramatsu.pt@hitachi.com>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Thiago Macieira <thiago.macieira@intel.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoinit/main.c: simplify initcall_blacklisted()
Rasmus Villemoes [Sat, 21 May 2016 00:04:27 +0000 (17:04 -0700)]
init/main.c: simplify initcall_blacklisted()

Using kasprintf to get the function name makes us look up the name
twice, along with all the vsnprintf overhead of parsing the format
string etc.  It also means there is an allocation failure case to deal
with.  Since symbol_string in vsprintf.c would anyway allocate an array
of size KSYM_SYMBOL_LEN on the stack, that might as well be done up
here.

Moreover, since this is a debug feature and the blacklisted_initcalls
list is usually empty, we might as well test that and thus avoid looking
up the symbol name even once in the common case.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Acked-by: Rusty Russell <rusty@rustcorp.com.au>
Acked-by: Prarit Bhargava <prarit@redhat.com>
Cc: Oleg Nesterov <oleg@redhat.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agofs/efs/super.c: fix return value
Heloise [Sat, 21 May 2016 00:04:25 +0000 (17:04 -0700)]
fs/efs/super.c: fix return value

When sb_bread() fails, the return value should be -EIO, fix it.

Link: http://lkml.kernel.org/r/1463464943-4142-1-git-send-email-os@iscas.ac.cn
Signed-off-by: Heloise <os@iscas.ac.cn>
Cc: Johannes Weiner <hannes@cmpxchg.org>
Cc: Firo Yang <firogm@gmail.com>
Cc: Vladimir Davydov <vdavydov@virtuozzo.com>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agocheckpatch: improve --git <commit-count> shortcut
Joe Perches [Sat, 21 May 2016 00:04:22 +0000 (17:04 -0700)]
checkpatch: improve --git <commit-count> shortcut

The --git <commit-count> shortcut can be confused by a tag with a dash
like v4.4-rc1.

Improve the test to verify the <commit-count> expression ends with a
dash followed by a numeric value.

Improve the git log result to verify the "<sha1> <subject>" output
as well.

Link: http://lkml.kernel.org/r/c4a3f759291d967641860c3a54bb81177f34325f.1462711962.git.joe@perches.com
Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agocheckpatch: reduce number of `git log` calls with --git
Joe Perches [Sat, 21 May 2016 00:04:19 +0000 (17:04 -0700)]
checkpatch: reduce number of `git log` calls with --git

checkpatch currently calls git log multiple times to first get the
<revision range> sha1 values and again to get the subject for each
individual sha1 commit.

Always get the sha1 and subject at the same time instead.  Store the
subject in a sha1 hash to avoid the second git log exec.

Link: http://lkml.kernel.org/r/274efab2332ad2308ab5de85a95d255f6e2de5f3.1462711962.git.joe@perches.com
Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agocheckpatch: add support to check already applied git commits
Du, Changbin [Sat, 21 May 2016 00:04:16 +0000 (17:04 -0700)]
checkpatch: add support to check already applied git commits

It's sometimes useful to scan already committed patches.

Add --git <revision range> to scan specific or multiple commits.

Single commits are scanned with
--git <rev>
Multiple commits are scanned with
--git <range>
--git <commit>-<count>

[joe@perches.com:
o Don't exec git for each <commit>-<count>,
  use a single "git log -<count> <commit>"
o Consolidate the git exec for the <range> and <commit>-<count> variants
o Output 12 character commit hash ids
o Don't scan git commit merges
o Use -M to reduce the size of rename commits]

Signed-off-by: "Du, Changbin" <changbin.du@intel.com>
Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agocheckpatch: add --list-types to show message types to show or ignore
Joe Perches [Sat, 21 May 2016 00:04:14 +0000 (17:04 -0700)]
checkpatch: add --list-types to show message types to show or ignore

The message types are not currently knowable without reading the code.
Add a mechanism to see what they are.

Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agocheckpatch: advertise the --fix and --fix-inplace options more
Joe Perches [Sat, 21 May 2016 00:04:11 +0000 (17:04 -0700)]
checkpatch: advertise the --fix and --fix-inplace options more

The --fix option is relatively unknown and underutilized.

Add some text to show that it's available when style defects are found.

Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agocheckpatch: whine about ACCESS_ONCE
Joe Perches [Sat, 21 May 2016 00:04:08 +0000 (17:04 -0700)]
checkpatch: whine about ACCESS_ONCE

Add a test for use of ACCESS_ONCE that could be written using READ_ONCE or
WRITE_ONCE.

--fix it too if desired.

The WRITE_ONCE fixes are less correct than the coccinelle script below as
checkpatch cannot have a completely correct "expression" mechanism because
checkpatch works on patches and not complete files.

$ cat access_once.cocci
@@
expression e1;
expression e2;
@@

-       ACCESS_ONCE(e1) = e2
+       WRITE_ONCE(e1, e2)

@@
expression e1;
@@

-       ACCESS_ONCE(e1)
+       READ_ONCE(e1)

Signed-off-by: Joe Perches <joe@perches.com>
Cc: Julia Lawall <julia.lawall@lip6.fr>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agocheckpatch: add test for keywords not starting on tabstops
Joe Perches [Sat, 21 May 2016 00:04:05 +0000 (17:04 -0700)]
checkpatch: add test for keywords not starting on tabstops

It's somewhat common and in general a defect for c90 keywords to
not start on a tabstop.

Add a test for this condition and warn when it occurs.

Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agocheckpatch: improve CONSTANT_COMPARISON test for structure members
Joe Perches [Sat, 21 May 2016 00:04:02 +0000 (17:04 -0700)]
checkpatch: improve CONSTANT_COMPARISON test for structure members

A "." dereference to an all uppercase structure member can be
incorrectly reported as a CONSTANT_COMPARISON.

ie: "if (table[i].PANELID == tempdx)"

Fix it by checking for "." before the constant test.

Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agocheckpatch: add PREFER_IS_ENABLED test
Joe Perches [Sat, 21 May 2016 00:04:00 +0000 (17:04 -0700)]
checkpatch: add PREFER_IS_ENABLED test

Using #if defined CONFIG_<FOO> || defined CONFIG_<FOO>_MODULE is
more verbose than necessary and IS_ENABLED(CONFIG_<FOO>) is preferred.

So add a test and a message for it.

--fix it to if desired.

Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agolib/GCD.c: use binary GCD algorithm instead of Euclidean
Zhaoxiu Zeng [Sat, 21 May 2016 00:03:57 +0000 (17:03 -0700)]
lib/GCD.c: use binary GCD algorithm instead of Euclidean

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: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com>
Signed-off-by: George Spelvin <linux@horizon.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: free up the bottom bit of exceptional entries for reuse
Matthew Wilcox [Sat, 21 May 2016 00:03:54 +0000 (17:03 -0700)]
radix-tree: free up the bottom bit of exceptional entries for reuse

We are guaranteed that pointers to radix_tree_nodes always have the
bottom two bits clear (because they come from a slab cache, and slab
caches have a minimum alignment of sizeof(void *)), so we can redefine
'radix_tree_is_internal_node' to only return true if the bottom two bits
have value '01'.  This frees up one quarter of the potential values for
use by the user.

Idea from Neil Brown.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Suggested-by: Neil Brown <neilb@suse.de>
Cc: Konstantin Khlebnikov <koct9i@gmail.com>
Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
Cc: Jan Kara <jack@suse.com>
Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agodax: move RADIX_DAX_ definitions to dax.c
NeilBrown [Sat, 21 May 2016 00:03:51 +0000 (17:03 -0700)]
dax: move RADIX_DAX_ definitions to dax.c

These don't belong in radix-tree.h any more than PAGECACHE_TAG_* do.
Let's try to maintain the idea that radix-tree simply implements an
abstract data type.

Signed-off-by: NeilBrown <neilb@suse.com>
Reviewed-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Reviewed-by: Jan Kara <jack@suse.cz>
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Cc: Konstantin Khlebnikov <koct9i@gmail.com>
Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: make radix_tree_descend() more useful
Matthew Wilcox [Sat, 21 May 2016 00:03:48 +0000 (17:03 -0700)]
radix-tree: make radix_tree_descend() more useful

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: Matthew 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: introduce radix_tree_replace_clear_tags()
Matthew Wilcox [Sat, 21 May 2016 00:03:45 +0000 (17:03 -0700)]
radix-tree: introduce radix_tree_replace_clear_tags()

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: Matthew 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: tidy up __radix_tree_create()
Matthew Wilcox [Sat, 21 May 2016 00:03:42 +0000 (17:03 -0700)]
radix-tree: tidy up __radix_tree_create()

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: Matthew 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: tidy up range_tag_if_tagged
Matthew Wilcox [Sat, 21 May 2016 00:03:39 +0000 (17:03 -0700)]
radix-tree: tidy up range_tag_if_tagged

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: Matthew 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: tidy up next_chunk
Matthew Wilcox [Sat, 21 May 2016 00:03:36 +0000 (17:03 -0700)]
radix-tree: tidy up next_chunk

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: Matthew 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: change naming conventions in radix_tree_shrink
Matthew Wilcox [Sat, 21 May 2016 00:03:33 +0000 (17:03 -0700)]
radix-tree: change naming conventions in radix_tree_shrink

Use the more standard 'node' and 'child' instead of 'to_free' and
'slot'.

Signed-off-by: Matthew 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: rename radix_tree_is_indirect_ptr()
Matthew Wilcox [Sat, 21 May 2016 00:03:30 +0000 (17:03 -0700)]
radix-tree: rename radix_tree_is_indirect_ptr()

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: Matthew 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: rename indirect_to_ptr() to entry_to_node()
Matthew Wilcox [Sat, 21 May 2016 00:03:27 +0000 (17:03 -0700)]
radix-tree: rename indirect_to_ptr() to entry_to_node()

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: Matthew 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: rename ptr_to_indirect() to node_to_entry()
Matthew Wilcox [Sat, 21 May 2016 00:03:24 +0000 (17:03 -0700)]
radix-tree: rename ptr_to_indirect() to node_to_entry()

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: Matthew 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: rename INDIRECT_PTR to INTERNAL_NODE
Matthew Wilcox [Sat, 21 May 2016 00:03:22 +0000 (17:03 -0700)]
radix-tree: rename INDIRECT_PTR to INTERNAL_NODE

The name RADIX_TREE_INDIRECT_PTR doesn't really match the meaning.
RADIX_TREE_INTERNAL_NODE is a better name.

Signed-off-by: Matthew 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: remove root->height
Matthew Wilcox [Sat, 21 May 2016 00:03:19 +0000 (17:03 -0700)]
radix-tree: remove root->height

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: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix tree test suite: remove dependencies on height
Matthew Wilcox [Sat, 21 May 2016 00:03:16 +0000 (17:03 -0700)]
radix tree test suite: remove dependencies on height

verify_node() can use node->shift instead of the height.

tree_verify_min_height() can be converted over to using node_maxindex()
and shift_maxindex() instead of radix_tree_maxindex().

Signed-off-by: Matthew 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: remove a use of root->height from delete_node
Matthew Wilcox [Sat, 21 May 2016 00:03:13 +0000 (17:03 -0700)]
radix-tree: remove a use of root->height from delete_node

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: Matthew 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: replace node->height with node->shift
Matthew Wilcox [Sat, 21 May 2016 00:03:10 +0000 (17:03 -0700)]
radix-tree: replace node->height with node->shift

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: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: split node->path into offset and height
Matthew Wilcox [Sat, 21 May 2016 00:03:07 +0000 (17:03 -0700)]
radix-tree: split node->path into offset and height

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: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: miscellaneous fixes
Matthew Wilcox [Sat, 21 May 2016 00:03:04 +0000 (17:03 -0700)]
radix-tree: miscellaneous fixes

Typos, whitespace, grammar, line length, using the correct types, etc.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agodrivers/hwspinlock: use correct radix tree API
Matthew Wilcox [Sat, 21 May 2016 00:03:01 +0000 (17:03 -0700)]
drivers/hwspinlock: use correct radix tree API

radix_tree_is_indirect_ptr() is an internal API.  The correct call to
use is radix_tree_deref_retry() which has the appropriate unlikely()
annotation.

Fixes: c6400ba7e13a ("drivers/hwspinlock: fix race between radix tree insertion and lookup")
Signed-off-by: Matthew 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: add copyright statements
Matthew Wilcox [Sat, 21 May 2016 00:02:58 +0000 (17:02 -0700)]
radix-tree: add copyright statements

The multiorder support is a sufficiently large feature to be worth
adding copyrigt lines for.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: fix radix_tree_dump() for multi-order entries
Ross Zwisler [Sat, 21 May 2016 00:02:55 +0000 (17:02 -0700)]
radix-tree: fix radix_tree_dump() for multi-order entries

 - Print which indices are covered by every leaf entry
 - Print sibling entries
 - Print the node pointer instead of the slot entry
 - Build by default in userspace, and make it accessible to the test-suite

Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: Matthew 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>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: fix radix_tree_range_tag_if_tagged() for multiorder entries
Matthew Wilcox [Sat, 21 May 2016 00:02:52 +0000 (17:02 -0700)]
radix-tree: fix radix_tree_range_tag_if_tagged() for multiorder entries

I had previously decided that tagging a single multiorder entry would
count as tagging 2^order entries for the purposes of 'nr_to_tag'.  I now
believe that decision to be a mistake, and it should count as a single
entry.  That's more likely to be what callers expect.

When walking back up the tree from a newly-tagged entry, the current
code assumed we were starting from the lowest level of the tree; if we
have a multiorder entry with an order at least RADIX_TREE_MAP_SHIFT in
size then we need to shift the index by 'shift' before we start walking
back up the tree, or we will end up not setting tags on higher entries,
and then mistakenly thinking that entries below a certain point in the
tree are not tagged.

If the first index we examine is a sibling entry of a tagged multiorder
entry, we were not tagging it.  We need to examine the canonical entry,
and the easiest way to do that is to use radix_tree_descend().  We then
have to skip over sibling slots when looking for the next entry in the
tree or we will end up walking back to the canonical entry.

Add several tests for radix_tree_range_tag_if_tagged().

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: add test for radix_tree_locate_item()
Ross Zwisler [Sat, 21 May 2016 00:02:49 +0000 (17:02 -0700)]
radix-tree: add test for radix_tree_locate_item()

Add a unit test that provides coverage for the bug fixed in the commit
entitled "radix-tree: rewrite radix_tree_locate_item fix" from Hugh
Dickins.  I've verified that this test fails before his patch due to
miscalculated 'index' values in __locate() in lib/radix-tree.c, and
passes with his fix.

Link: http://lkml.kernel.org/r/1462307263-20623-1-git-send-email-ross.zwisler@linux.intel.com
Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Cc: Hugh Dickins <hughd@google.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: rewrite radix_tree_locate_item
Matthew Wilcox [Sat, 21 May 2016 00:02:46 +0000 (17:02 -0700)]
radix-tree: rewrite radix_tree_locate_item

Use the new multi-order support functions to rewrite
radix_tree_locate_item().  Modify the locate tests to test multiorder
entries too.

[hughd@google.com: radix_tree_locate_item() is often returning the wrong index]
Link: http://lkml.kernel.org/r/alpine.LSU.2.11.1605012108490.1166@eggly.anvils
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: fix radix_tree_create for sibling entries
Matthew Wilcox [Sat, 21 May 2016 00:02:44 +0000 (17:02 -0700)]
radix-tree: fix radix_tree_create for sibling entries

If the radix tree user attempted to insert a colliding entry with an
existing multiorder entry, then radix_tree_create() could encounter a
sibling entry when walking down the tree to look for a slot.  Use
radix_tree_descend() to fix the problem, and add a test-case to make
sure the problem doesn't come back in future.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree test suite: add multi-order tag test
Ross Zwisler [Sat, 21 May 2016 00:02:41 +0000 (17:02 -0700)]
radix-tree test suite: add multi-order tag test

Add a generic test for multi-order tag verification, and call it using
several different configurations.

This test creates a multi-order radix tree using the given index and
order, and then sets, checks and clears tags using the indices covered
by the single multi-order radix tree entry.

With the various calls done by this test we verify root multi-order
entries without siblings, multi-order entries without siblings in a
radix tree node, as well as multi-order entries with siblings of various
sizes.

Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: Matthew 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>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: rewrite radix_tree_tag_get
Ross Zwisler [Sat, 21 May 2016 00:02:38 +0000 (17:02 -0700)]
radix-tree: rewrite radix_tree_tag_get

Use the new multi-order support functions to rewrite
radix_tree_tag_get()

Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: Matthew 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>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: rewrite radix_tree_tag_clear
Ross Zwisler [Sat, 21 May 2016 00:02:35 +0000 (17:02 -0700)]
radix-tree: rewrite radix_tree_tag_clear

Use the new multi-order support functions to rewrite
radix_tree_tag_clear()

Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: Matthew 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>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: rewrite radix_tree_tag_set
Ross Zwisler [Sat, 21 May 2016 00:02:32 +0000 (17:02 -0700)]
radix-tree: rewrite radix_tree_tag_set

Use the new multi-order support functions to rewrite
radix_tree_tag_set()

Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: Matthew 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>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix tree test suite: multi-order iteration test
Ross Zwisler [Sat, 21 May 2016 00:02:29 +0000 (17:02 -0700)]
radix tree test suite: multi-order iteration test

Add a unit test to verify that we can iterate over multi-order entries
properly via a radix_tree_for_each_slot() loop.

This was done with a single, somewhat complicated configuration that was
meant to test many of the various corner cases having to do with
multi-order entries:

- An iteration could begin at a sibling entry, and we need to return the
  canonical entry.
- We could have entries of various orders in the same slots[] array.
- We could have multi-order entries at a nonzero height, followed by
  indirect pointers to more radix tree nodes later in that same slots[]
  array.

Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: Matthew 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>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: add support for multi-order iterating
Ross Zwisler [Sat, 21 May 2016 00:02:26 +0000 (17:02 -0700)]
radix-tree: add support for multi-order iterating

This enables the macros radix_tree_for_each_slot() and friends to be
used with multi-order entries.

The way that this works is that we treat all entries in a given slots[]
array as a single chunk.  If the index given to radix_tree_next_chunk()
happens to point us to a sibling entry, we will back up iter->index so
that it points to the canonical entry, and that will be the place where
we start our iteration.

As we're processing a chunk in radix_tree_next_slot(), we process
canonical entries, skip over sibling entries, and restart the chunk
lookup if we find a non-sibling indirect pointer.  This drops back to
the radix_tree_next_chunk() code, which will re-walk the tree and look
for another chunk.

This allows us to properly handle multi-order entries mixed with other
entries that are at various heights in the radix tree.

Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: Matthew 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>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: fix multiorder BUG_ON in radix_tree_insert
Matthew Wilcox [Sat, 21 May 2016 00:02:23 +0000 (17:02 -0700)]
radix-tree: fix multiorder BUG_ON in radix_tree_insert

These BUG_ON tests are to ensure that all the tags are clear when
inserting a new entry.  If we insert a multiorder entry, we'll end up
looking at the tags for a different node, and so the BUG_ON can end up
triggering spuriously.

Also, we now have three tags, not two, so check all three are clear, and
check all the root tags with a single call to BUG_ON since the bits are
stored contiguously.

Include a test-case to ensure this problem does not reoccur.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: rewrite __radix_tree_lookup
Matthew Wilcox [Sat, 21 May 2016 00:02:20 +0000 (17:02 -0700)]
radix-tree: rewrite __radix_tree_lookup

Use the new multi-order support functions to rewrite __radix_tree_lookup()

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: fix several shrinking bugs with multiorder entries
Matthew Wilcox [Sat, 21 May 2016 00:02:17 +0000 (17:02 -0700)]
radix-tree: fix several shrinking bugs with multiorder entries

Setting the indirect bit on the user data entry used to be unambiguous
because the tree walking code knew not to expect internal nodes in the
last level of the tree.  Multiorder entries can appear at any level of
the tree, and a leaf with the indirect bit set is indistinguishable from
a pointer to a node.

Introduce a special entry (RADIX_TREE_RETRY) which is neither a valid
user entry, nor a valid pointer to a node.  The radix_tree_deref_retry()
function continues to work the same way, but tree walking code can
distinguish it from a pointer to a node.

Also fix the condition for setting slot->parent to NULL; it does not
matter what height the tree is, it only matters whether slot is an
indirect pointer.  Move this code above the comment which is referring
to the assignment to root->rnode.

Also fix the condition for preventing the tree from shrinking to a
single entry if it's a multiorder entry.

Add a test-case to the test suite that checks that the tree goes back
down to its original height after an item is inserted & deleted from a
higher index in the tree.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix tree test suite: start adding multiorder tests
Matthew Wilcox [Sat, 21 May 2016 00:02:14 +0000 (17:02 -0700)]
radix tree test suite: start adding multiorder tests

Test suite infrastructure for working with multiorder entries.

The test itself is pretty basic: Add an entry, check that all expected
indices return that entry and that indices around that entry don't
return an entry.  Then delete the entry and check no index returns that
entry.  Tests a few edge conditions including the multiorder entry at
index 0 and at a higher index.  Also tests deleting through an alias as
well as through the canonical index.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: fix extending the tree for multi-order entries at offset 0
Matthew Wilcox [Sat, 21 May 2016 00:02:11 +0000 (17:02 -0700)]
radix-tree: fix extending the tree for multi-order entries at offset 0

The current code will insert entries at each level, as if we're going to
add a new entry at the bottom level, so we then get an -EEXIST when we
try to insert the entry into the tree.  The best way to fix this is to
not check 'order' when inserting into an empty tree.

We still need to 'extend' the tree to the height necessary for the maximum
index corresponding to this entry, so pass that value to
radix_tree_extend() rather than the index we're asked to create, or we
won't create a tree that's deep enough.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: introduce radix_tree_load_root()
Matthew Wilcox [Sat, 21 May 2016 00:02:08 +0000 (17:02 -0700)]
radix-tree: introduce radix_tree_load_root()

All the tree walking functions start with some variant of this code;
centralise it in one place so we're not chasing subtly different bugs
everywhere.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: remove restriction on multi-order entries
Matthew Wilcox [Sat, 21 May 2016 00:02:05 +0000 (17:02 -0700)]
radix-tree: remove restriction on multi-order entries

Now that sibling pointers are handled explicitly, there is no purpose
served by restricting the order to be >= RADIX_TREE_MAP_SHIFT.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: fix deleting a multi-order entry through an alias
Matthew Wilcox [Sat, 21 May 2016 00:02:02 +0000 (17:02 -0700)]
radix-tree: fix deleting a multi-order entry through an alias

If we deleted an entry through an index which looked up a sibling
pointer, we'd end up zeroing out the wrong slots in the node.  Use
get_slot_offset() to find the right slot.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: fix sibling entry insertion
Matthew Wilcox [Sat, 21 May 2016 00:01:59 +0000 (17:01 -0700)]
radix-tree: fix sibling entry insertion

The subtraction was the wrong way round, leading to undefined behaviour
(shift by an amount larger than the size of the type).

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: add missing sibling entry functionality
Matthew Wilcox [Sat, 21 May 2016 00:01:57 +0000 (17:01 -0700)]
radix-tree: add missing sibling entry functionality

The code I previously added to enable multiorder radix tree entries was
untested and therefore buggy.  This commit adds the support functions
that Ross and I decided were necessary over a four-week period of
iterating various designs.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoraxix-tree: introduce CONFIG_RADIX_TREE_MULTIORDER
Matthew Wilcox [Sat, 21 May 2016 00:01:54 +0000 (17:01 -0700)]
raxix-tree: introduce CONFIG_RADIX_TREE_MULTIORDER

I've been receiving increasingly concerned notes from 0day about how
much my recent changes have been bloating the radix tree.  Make it
happier by only including multiorder support if
CONFIG_TRANSPARENT_HUGEPAGES is set.

This is an independent Kconfig option, so other radix tree users can
also set it if they have a need.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: remove unused looping macros
Ross Zwisler [Sat, 21 May 2016 00:01:51 +0000 (17:01 -0700)]
radix-tree: remove unused looping macros

radix_tree_for_each_chunk() and radix_tree_for_each_chunk_slot() have
never been used in the kernel since their introduction in 2012, so
remove them.

Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: Matthew 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>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix tree test suite: rebuild when headers change
Ross Zwisler [Sat, 21 May 2016 00:01:48 +0000 (17:01 -0700)]
radix tree test suite: rebuild when headers change

When we make changes to radix-tree.h in the regular kernel source
(include/linux/radix-tree.h), we really want our test code to be
rebuilt.

We also include a few other headers from tools/include and probably want
to rebuild if these have been changed.

Update the makefile so that all of our objects will be rebuilt when any
of the headers we depend on are changed.

Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: Matthew 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>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix tree test suite: keep regression test runs short
Ross Zwisler [Sat, 21 May 2016 00:01:45 +0000 (17:01 -0700)]
radix tree test suite: keep regression test runs short

Currently the full suite of regression tests take upwards of 30 minutes
to run on my development machine.  The vast majority of this time is
taken by the big_gang_check() and copy_tag_check() tests, which each run
their tests through thousands of iterations...does this have value?

Without big_gang_check() and copy_tag_check(), the test suite runs in
around 15 seconds on my box.

Honestly the first time I ever ran through the entire test suite was to
gather the timings for this email - it simply takes too long to be
useful on a normal basis.

Instead, hide the excessive iterations through big_gang_check() and
copy_tag_check() tests behind an '-l' flag (for "long run") in case they
are still useful, but allow the regression test suite to complete in a
reasonable amount of time.  We still run each of these tests a few times
(3 at present) to try and keep the test coverage.

Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: Matthew 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>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix tree test suite: allow testing other fan-out values
Ross Zwisler [Sat, 21 May 2016 00:01:42 +0000 (17:01 -0700)]
radix tree test suite: allow testing other fan-out values

The defines in regression2.c are already in radix-tree.h and duplicating
them in the test case makes experimenting with other values for the
fan-out harder than necessary.  Allow the user of the radix tree to
decide what the fan-out should be rather than fixing it to 8 for
non-kernel uses.

Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: Matthew 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>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix tree test suite: add tests for radix_tree_locate_item()
Matthew Wilcox [Sat, 21 May 2016 00:01:39 +0000 (17:01 -0700)]
radix tree test suite: add tests for radix_tree_locate_item()

Fairly simple tests; add various items to the tree, then make sure we
can find them again.  Also check that a pointer that we know isn't in
the tree is not found.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix tree test suite: fix build
Matthew Wilcox [Sat, 21 May 2016 00:01:36 +0000 (17:01 -0700)]
radix tree test suite: fix build

Add an empty linux/init.h, and definitions for a few parts of the kernel
API either in use now, or to be used in the near future.  Start using the
common definitions in tools/include/linux, although more work needs to be
done here.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross 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: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoradix-tree: introduce radix_tree_empty
Matthew Wilcox [Sat, 21 May 2016 00:01:33 +0000 (17:01 -0700)]
radix-tree: introduce radix_tree_empty

Commit e61452365372 ("radix_tree: add support for multi-order entries")
left the impression that the support for multiorder radix tree entries
was functional.  As soon as Ross tried to use it, it became apparent
that my testing was completely inadequate, and it didn't even work a
little bit for orders that were not a multiple of shift.

This series of patches is the result of about 6 weeks of redesign,
reimplementation, testing, arguing and hair-pulling.  The great news is
that the test-suite is now far better than it was.  That's reflected in
the diffstat for the test-suite alone:

 12 files changed, 436 insertions(+), 28 deletions(-)

The highlight for users of the tree is that the restriction on the order
of inserted entries being >= RADIX_TREE_MAP_SHIFT is now gone; the radix
tree now supports any order between 0 and 64.

For those who are interested in how the tree works, patch 9 is probably
the most interesting one as it introduces the new machinery for handling
sibling entries.

I've tried to be fair in attributing authorship to the person who
contributed the majority of the code in each patch; Ross has been an
invaluable partner in the development of this support and it's fair to
say that each of us has code in every commit.

I should also express my appreciation of the 0day testing.  It prompted
me that I was bloating the tinyconfig in an unacceptable way, and it
bisected to a commit which contained a rather nasty memory-corruption
bug.

This patch (of 29):

The irqdomain code was checking for 0 or 1 entries, not 0 entries like
the comment said they were.  Introduce a new helper that will actually
check for an empty tree.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Reviewed-by: Jan Kara <jack@suse.cz>
Cc: Konstantin Khlebnikov <koct9i@gmail.com>
Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
Cc: Neil Brown <neilb@suse.de>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agodrivers/platform/x86/wmi.c: use generic UUID library
Andy Shevchenko [Sat, 21 May 2016 00:01:30 +0000 (17:01 -0700)]
drivers/platform/x86/wmi.c: use generic UUID library

Instead of opencoding let's use generic UUID library functions here.

Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Cc: Darren Hart <dvhart@linux.intel.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoblock/partitions/ldm.c: use generic UUID library
Andy Shevchenko [Sat, 21 May 2016 00:01:27 +0000 (17:01 -0700)]
block/partitions/ldm.c: use generic UUID library

Instead of opencoding let's use generic UUID library functions here.

Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Cc: "Richard Russon (FlatCap)" <ldm@flatcap.org>
Cc: Jens Axboe <axboe@kernel.dk>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoinclude/linux/genhd.h: move to use generic UUID library
Andy Shevchenko [Sat, 21 May 2016 00:01:24 +0000 (17:01 -0700)]
include/linux/genhd.h: move to use generic UUID library

UUID library provides uuid_be type and uuid_be_to_bin() function.  This
substitutes open coded variant by generic library calls.

Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Reviewed-by: Matt Fleming <matt@codeblueprint.co.uk>
Cc: Dmitry Kasatkin <dmitry.kasatkin@gmail.com>
Cc: Mimi Zohar <zohar@linux.vnet.ibm.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Cc: Jens Axboe <axboe@kernel.dk>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agofs/efivarfs/inode.c: use generic UUID library
Andy Shevchenko [Sat, 21 May 2016 00:01:21 +0000 (17:01 -0700)]
fs/efivarfs/inode.c: use generic UUID library

Instead of opencoding let's use generic UUID library functions here.

Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Reviewed-by: Matt Fleming <matt@codeblueprint.co.uk>
Cc: Dmitry Kasatkin <dmitry.kasatkin@gmail.com>
Cc: Mimi Zohar <zohar@linux.vnet.ibm.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Cc: Jens Axboe <axboe@kernel.dk>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoinclude/linux/efi.h: redefine type, constant, macro from generic code
Andy Shevchenko [Sat, 21 May 2016 00:01:18 +0000 (17:01 -0700)]
include/linux/efi.h: redefine type, constant, macro from generic code

Generic UUID library defines structure type, macro to define UUID, and
the length of the UUID string.  This patch removes duplicate data
structure definition, UUID string length constant as well as macro for
UUID handling.

Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Reviewed-by: Matt Fleming <matt@codeblueprint.co.uk>
Cc: Dmitry Kasatkin <dmitry.kasatkin@gmail.com>
Cc: Mimi Zohar <zohar@linux.vnet.ibm.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Cc: Jens Axboe <axboe@kernel.dk>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agokernel/sysctl_binary.c: use generic UUID library
Andy Shevchenko [Sat, 21 May 2016 00:01:10 +0000 (17:01 -0700)]
kernel/sysctl_binary.c: use generic UUID library

UUID library provides uuid_be type and uuid_be_to_bin() function.  This
substitutes open coded variant by generic library calls.

Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Reviewed-by: Matt Fleming <matt@codeblueprint.co.uk>
Cc: Dmitry Kasatkin <dmitry.kasatkin@gmail.com>
Cc: Mimi Zohar <zohar@linux.vnet.ibm.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Cc: Jens Axboe <axboe@kernel.dk>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agolib/uuid.c: remove FSF address
Andy Shevchenko [Sat, 21 May 2016 00:01:07 +0000 (17:01 -0700)]
lib/uuid.c: remove FSF address

There is no point in keeping an address in the file since it's subject
to change.

While here, update Intel Copyright years.

Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Reviewed-by: Matt Fleming <matt@codeblueprint.co.uk>
Cc: Dmitry Kasatkin <dmitry.kasatkin@gmail.com>
Cc: Mimi Zohar <zohar@linux.vnet.ibm.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Cc: Jens Axboe <axboe@kernel.dk>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agolib/uuid.c: introduce a few more generic helpers
Andy Shevchenko [Sat, 21 May 2016 00:01:04 +0000 (17:01 -0700)]
lib/uuid.c: introduce a few more generic helpers

There are new helpers in this patch:

  uuid_is_valid checks if a UUID is valid
  uuid_be_to_bin converts from string to binary (big endian)
  uuid_le_to_bin converts from string to binary (little endian)

They will be used in future, i.e. in the following patches in the series.

This also moves the indices arrays to lib/uuid.c to be shared accross
modules.

[andriy.shevchenko@linux.intel.com: fix typo]
Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Reviewed-by: Matt Fleming <matt@codeblueprint.co.uk>
Cc: Dmitry Kasatkin <dmitry.kasatkin@gmail.com>
Cc: Mimi Zohar <zohar@linux.vnet.ibm.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Cc: Jens Axboe <axboe@kernel.dk>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agolib/uuid.c: move generate_random_uuid() to uuid.c
Andy Shevchenko [Sat, 21 May 2016 00:01:00 +0000 (17:01 -0700)]
lib/uuid.c: move generate_random_uuid() to uuid.c

Let's gather the UUID related functions under one hood.

Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Reviewed-by: Matt Fleming <matt@codeblueprint.co.uk>
Cc: Dmitry Kasatkin <dmitry.kasatkin@gmail.com>
Cc: Mimi Zohar <zohar@linux.vnet.ibm.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Cc: Jens Axboe <axboe@kernel.dk>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agosecurity/integrity/ima/ima_policy.c: use %pU to output UUID in printable format
Andy Shevchenko [Sat, 21 May 2016 00:00:57 +0000 (17:00 -0700)]
security/integrity/ima/ima_policy.c: use %pU to output UUID in printable format

Instead of open coded variant re-use extension that vsprintf.c provides
us for ages.

Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Reviewed-by: Matt Fleming <matt@codeblueprint.co.uk>
Cc: Dmitry Kasatkin <dmitry.kasatkin@gmail.com>
Cc: Mimi Zohar <zohar@linux.vnet.ibm.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Cc: Jens Axboe <axboe@kernel.dk>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agolib/vsprintf: simplify UUID printing
Andy Shevchenko [Sat, 21 May 2016 00:00:54 +0000 (17:00 -0700)]
lib/vsprintf: simplify UUID printing

There are few functions here and there along with type definitions that
provide UUID API.  This series consolidates everything under one hood
and converts current users.

This has been tested for a while internally, however it doesn't mean we
covered all possible cases (especially accuracy of UUID constants after
conversion).  So, please test this as much as you can and provide your
tag.  We appreciate the effort.

The ACPI conversion is postponed for now to sort more generic things out
first.

This patch (of 9):

Since we have hex_byte_pack_upper() we may use it directly and avoid
second loop.

Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Reviewed-by: Matt Fleming <matt@codeblueprint.co.uk>
Cc: Dmitry Kasatkin <dmitry.kasatkin@gmail.com>
Cc: Mimi Zohar <zohar@linux.vnet.ibm.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Cc: Jens Axboe <axboe@kernel.dk>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoMAINTAINERS: remove Koichi Yasutake
Jiri Slaby [Sat, 21 May 2016 00:00:51 +0000 (17:00 -0700)]
MAINTAINERS: remove Koichi Yasutake

The MTA says:
 <yasutake.koichi@jp.panasonic.com>: unknown user:
    "yasutake.koichi@jp.panasonic.com"

Link: http://lkml.kernel.org/r/1462776755-9607-1-git-send-email-jslaby@suse.cz
Signed-off-by: Jiri Slaby <jslaby@suse.cz>
Cc: David Howells <dhowells@redhat.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
3 years agoMAINTAINERS: remove defunct spear mailing list
Eric Engestrom [Sat, 21 May 2016 00:00:49 +0000 (17:00 -0700)]
MAINTAINERS: remove defunct spear mailing list

It looks like the email address for this mailing list doesn't exist anymore:
<spear-devel@list.st.com>: host mxb-00178001.gslb.pphosted.com[91.207.212.93] said:
550 5.1.1 User Unknown (in reply to RCPT TO command)

Signed-off-by: Eric Engestrom <eric.engestrom@imgtec.com>
Acked-by: Viresh Kumar <viresh.kumar@linaro.org>
Cc: "David S. Miller" <davem@davemloft.net>
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Cc: Kalle Valo <kvalo@codeaurora.org>
Cc: Mauro Carvalho Chehab <mchehab@osg.samsung.com>
Cc: Guenter Roeck <linux@roeck-us.net>
Cc: Jiri Slaby <jslaby@suse.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>