- 21 May, 2016 40 commits
-
-
git://git.linaro.org/landing-teams/working/fujitsu/integrationLinus Torvalds authored
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
-
Linus Torvalds authored
Commit b3c1be1b ("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 ad7afc38..cc736607, 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>
-
Linus Torvalds authored
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() ...
-
git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/stagingLinus Torvalds authored
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 ...
-
git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/driver-coreLinus Torvalds authored
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() ...
-
git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/char-miscLinus Torvalds authored
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 ...
-
git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/usbLinus Torvalds authored
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 ...
-
git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/ttyLinus Torvalds authored
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 ...
-
git://git.kernel.org/pub/scm/linux/kernel/git/clk/linuxLinus Torvalds authored
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() ... -
git://git.kernel.org/pub/scm/linux/kernel/git/davem/netLinus Torvalds authored
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 ... -
Peter Zijlstra authored
Similar to commits: 51d7d520 ("powerpc: Add smp_mb() to arch_spin_is_locked()") d86b8da0 ("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:
-
git://git.samba.org/sfrench/cifs-2.6Linus Torvalds authored
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
-
Huang Shijie authored
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.comSigned-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:
-
Huang Shijie authored
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.comSigned-off-by:
-
Huang Shijie authored
Commit 3033f14a ("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:
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:
-
Rasmus Villemoes authored
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:
-
Heloise authored
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.cnSigned-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:
-
Joe Perches authored
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.comSigned-off-by:
Joe Perches <joe@perches.com> Signed-off-by:
-
Joe Perches authored
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.comSigned-off-by:
-
Du, Changbin authored
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 authored
The message types are not currently knowable without reading the code. Add a mechanism to see what they are. Signed-off-by:
-
Joe Perches authored
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 authored
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 authored
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 authored
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 authored
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:
-
Zhaoxiu Zeng authored
The binary GCD algorithm is based on the following facts: 1. If a and b are all evens, then gcd(a,b) = 2 * gcd(a/2, b/2) 2. If a is even and b is odd, then gcd(a,b) = gcd(a/2, b) 3. If a and b are all odds, then gcd(a,b) = gcd((a-b)/2, b) = gcd((a+b)/2, b) Even on x86 machines with reasonable division hardware, the binary algorithm runs about 25% faster (80% the execution time) than the division-based Euclidian algorithm. On platforms like Alpha and ARMv6 where division is a function call to emulation code, it's even more significant. There are two variants of the code here, depending on whether a fast __ffs (find least significant set bit) instruction is available. This allows the unpredictable branches in the bit-at-a-time shifting loop to be eliminated. If fast __ffs is not available, the "even/odd" GCD variant is used. I use the following code to benchmark: #include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <string.h> #include <time.h> #include <unistd.h> #define swap(a, b) \ do { \ a ^= b; \ b ^= a; \ a ^= b; \ } while (0) unsigned long gcd0(unsigned long a, unsigned long b) { unsigned long r; if (a < b) { swap(a, b); } if (b == 0) return a; while ((r = a % b) != 0) { a = b; b = r; } return b; } unsigned long gcd1(unsigned long a, unsigned long b) { unsigned long r = a | b; if (!a || !b) return r; b >>= __builtin_ctzl(b); for (;;) { a >>= __builtin_ctzl(a); if (a == b) return a << __builtin_ctzl(r); if (a < b) swap(a, b); a -= b; } } unsigned long gcd2(unsigned long a, unsigned long b) { unsigned long r = a | b; if (!a || !b) return r; r &= -r; while (!(b & r)) b >>= 1; for (;;) { while (!(a & r)) a >>= 1; if (a == b) return a; if (a < b) swap(a, b); a -= b; a >>= 1; if (a & r) a += b; a >>= 1; } } unsigned long gcd3(unsigned long a, unsigned long b) { unsigned long r = a | b; if (!a || !b) return r; b >>= __builtin_ctzl(b); if (b == 1) return r & -r; for (;;) { a >>= __builtin_ctzl(a); if (a == 1) return r & -r; if (a == b) return a << __builtin_ctzl(r); if (a < b) swap(a, b); a -= b; } } unsigned long gcd4(unsigned long a, unsigned long b) { unsigned long r = a | b; if (!a || !b) return r; r &= -r; while (!(b & r)) b >>= 1; if (b == r) return r; for (;;) { while (!(a & r)) a >>= 1; if (a == r) return r; if (a == b) return a; if (a < b) swap(a, b); a -= b; a >>= 1; if (a & r) a += b; a >>= 1; } } static unsigned long (*gcd_func[])(unsigned long a, unsigned long b) = { gcd0, gcd1, gcd2, gcd3, gcd4, }; #define TEST_ENTRIES (sizeof(gcd_func) / sizeof(gcd_func[0])) #if defined(__x86_64__) #define rdtscll(val) do { \ unsigned long __a,__d; \ __asm__ __volatile__("rdtsc" : "=a" (__a), "=d" (__d)); \ (val) = ((unsigned long long)__a) | (((unsigned long long)__d)<<32); \ } while(0) static unsigned long long benchmark_gcd_func(unsigned long (*gcd)(unsigned long, unsigned long), unsigned long a, unsigned long b, unsigned long *res) { unsigned long long start, end; unsigned long long ret; unsigned long gcd_res; rdtscll(start); gcd_res = gcd(a, b); rdtscll(end); if (end >= start) ret = end - start; else ret = ~0ULL - start + 1 + end; *res = gcd_res; return ret; } #else static inline struct timespec read_time(void) { struct timespec time; clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &time); return time; } static inline unsigned long long diff_time(struct timespec start, struct timespec end) { struct timespec temp; if ((end.tv_nsec - start.tv_nsec) < 0) { temp.tv_sec = end.tv_sec - start.tv_sec - 1; temp.tv_nsec = 1000000000ULL + end.tv_nsec - start.tv_nsec; } else { temp.tv_sec = end.tv_sec - start.tv_sec; temp.tv_nsec = end.tv_nsec - start.tv_nsec; } return temp.tv_sec * 1000000000ULL + temp.tv_nsec; } static unsigned long long benchmark_gcd_func(unsigned long (*gcd)(unsigned long, unsigned long), unsigned long a, unsigned long b, unsigned long *res) { struct timespec start, end; unsigned long gcd_res; start = read_time(); gcd_res = gcd(a, b); end = read_time(); *res = gcd_res; return diff_time(start, end); } #endif static inline unsigned long get_rand() { if (sizeof(long) == 8) return (unsigned long)rand() << 32 | rand(); else return rand(); } int main(int argc, char **argv) { unsigned int seed = time(0); int loops = 100; int repeats = 1000; unsigned long (*res)[TEST_ENTRIES]; unsigned long long elapsed[TEST_ENTRIES]; int i, j, k; for (;;) { int opt = getopt(argc, argv, "n:r:s:"); /* End condition always first */ if (opt == -1) break; switch (opt) { case 'n': loops = atoi(optarg); break; case 'r': repeats = atoi(optarg); break; case 's': seed = strtoul(optarg, NULL, 10); break; default: /* You won't actually get here. */ break; } } res = malloc(sizeof(unsigned long) * TEST_ENTRIES * loops); memset(elapsed, 0, sizeof(elapsed)); srand(seed); for (j = 0; j < loops; j++) { unsigned long a = get_rand(); /* Do we have args? */ unsigned long b = argc > optind ? strtoul(argv[optind], NULL, 10) : get_rand(); unsigned long long min_elapsed[TEST_ENTRIES]; for (k = 0; k < repeats; k++) { for (i = 0; i < TEST_ENTRIES; i++) { unsigned long long tmp = benchmark_gcd_func(gcd_func[i], a, b, &res[j][i]); if (k == 0 || min_elapsed[i] > tmp) min_elapsed[i] = tmp; } } for (i = 0; i < TEST_ENTRIES; i++) elapsed[i] += min_elapsed[i]; } for (i = 0; i < TEST_ENTRIES; i++) printf("gcd%d: elapsed %llu\n", i, elapsed[i]); k = 0; srand(seed); for (j = 0; j < loops; j++) { unsigned long a = get_rand(); unsigned long b = argc > optind ? strtoul(argv[optind], NULL, 10) : get_rand(); for (i = 1; i < TEST_ENTRIES; i++) { if (res[j][i] != res[j][0]) break; } if (i < TEST_ENTRIES) { if (k == 0) { k = 1; fprintf(stderr, "Error:\n"); } fprintf(stderr, "gcd(%lu, %lu): ", a, b); for (i = 0; i < TEST_ENTRIES; i++) fprintf(stderr, "%ld%s", res[j][i], i < TEST_ENTRIES - 1 ? ", " : "\n"); } } if (k == 0) fprintf(stderr, "PASS\n"); free(res); return 0; } Compiled with "-O2", on "VirtualBox 4.4.0-22-generic #38-Ubuntu x86_64" got: zhaoxiuzeng@zhaoxiuzeng-VirtualBox:~/develop$ ./gcd -r 500000 -n 10 gcd0: elapsed 10174 gcd1: elapsed 2120 gcd2: elapsed 2902 gcd3: elapsed 2039 gcd4: elapsed 2812 PASS zhaoxiuzeng@zhaoxiuzeng-VirtualBox:~/develop$ ./gcd -r 500000 -n 10 gcd0: elapsed 9309 gcd1: elapsed 2280 gcd2: elapsed 2822 gcd3: elapsed 2217 gcd4: elapsed 2710 PASS zhaoxiuzeng@zhaoxiuzeng-VirtualBox:~/develop$ ./gcd -r 500000 -n 10 gcd0: elapsed 9589 gcd1: elapsed 2098 gcd2: elapsed 2815 gcd3: elapsed 2030 gcd4: elapsed 2718 PASS zhaoxiuzeng@zhaoxiuzeng-VirtualBox:~/develop$ ./gcd -r 500000 -n 10 gcd0: elapsed 9914 gcd1: elapsed 2309 gcd2: elapsed 2779 gcd3: elapsed 2228 gcd4: elapsed 2709 PASS [akpm@linux-foundation.org: avoid #defining a CONFIG_ variable] Signed-off-by:Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com> Signed-off-by:
George Spelvin <linux@horizon.com> Signed-off-by:
-
Matthew Wilcox authored
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:
-
NeilBrown authored
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 authored
Now that the shift amount is stored in the node, radix_tree_descend() can calculate offset itself from index, which removes several lines of code from each of the tree walkers. Signed-off-by:
-
Matthew Wilcox authored
In addition to replacing the entry, we also clear all associated tags. This is really a one-off special for page_cache_tree_delete() which had far too much detailed knowledge about how the radix tree works. For efficiency, factor node_tag_clear() out of radix_tree_tag_clear() It can be used by radix_tree_delete_item() as well as radix_tree_replace_clear_tags(). Signed-off-by:
-
Matthew Wilcox authored
1. Rename the existing variable 'slot' to 'child'. 2. Introduce a new variable called 'slot' which is the address of the slot we're dealing with. This lets us simplify the tree insertion, and removes the recalculation of 'slot' at the end of the function. 3. Using 'slot' in the sibling pointer insertion part makes the code more readable. Signed-off-by:
-
Matthew Wilcox authored
Convert radix_tree_range_tag_if_tagged to name the nodes parent, node and child instead of node & slot. Use parent->offset instead of playing games with 'upindex'. Signed-off-by:
-
Matthew Wilcox authored
Convert radix_tree_next_chunk to use 'child' instead of 'slot' as the name of the child node. Also use node_maxindex() where it makes sense. The 'rnode' variable was unnecessary; it doesn't overlap in usage with 'node', so we can just use 'node' the whole way through the function. Improve the testcase to start the walk from every index in the carefully constructed tree, and to accept any index within the range covered by the entry. Signed-off-by:
-
Matthew Wilcox authored
Use the more standard 'node' and 'child' instead of 'to_free' and 'slot'. Signed-off-by:
-
Matthew Wilcox authored
As with indirect_to_ptr(), ptr_to_indirect() and RADIX_TREE_INDIRECT_PTR, change radix_tree_is_indirect_ptr() to radix_tree_is_internal_node(). Signed-off-by:
-
Matthew Wilcox authored
Mirrors the earlier commit introducing node_to_entry(). Also change the type returned to be a struct radix_tree_node pointer. That lets us simplify a couple of places in the radix tree shrink & extend paths where we could convert an entry into a pointer, modify the node, then convert the pointer back into an entry. Signed-off-by:
-
Matthew Wilcox authored
ptr_to_indirect() was a bad name. What it really means is "Convert this pointer to a node into an entry suitable for storing in the radix tree". So node_to_entry() seemed like a better name. Signed-off-by:
-
Matthew Wilcox authored
The name RADIX_TREE_INDIRECT_PTR doesn't really match the meaning. RADIX_TREE_INTERNAL_NODE is a better name. Signed-off-by:
-
Matthew Wilcox authored
The only remaining references to root->height were in extend and shrink, where it was updated. Now we can remove it entirely. Signed-off-by:
-
