From: Taniya Das tdas@codeaurora.org
[ Upstream commit 21ea4b62e1f3dc258001a68da98c9663a9dbd6c7 ]
In case of update config failure, return -EBUSY, so that consumers could handle the failure gracefully.
Signed-off-by: Taniya Das tdas@codeaurora.org Link: https://lkml.kernel.org/r/1557339895-21952-2-git-send-email-tdas@codeaurora.... Signed-off-by: Stephen Boyd sboyd@kernel.org Signed-off-by: Lee Jones lee.jones@linaro.org --- drivers/clk/qcom/clk-rcg2.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/drivers/clk/qcom/clk-rcg2.c b/drivers/clk/qcom/clk-rcg2.c index 350a01f748706..f7f31da1d6305 100644 --- a/drivers/clk/qcom/clk-rcg2.c +++ b/drivers/clk/qcom/clk-rcg2.c @@ -107,7 +107,7 @@ static int update_config(struct clk_rcg2 *rcg) }
WARN(1, "%s: rcg didn't update its configuration.", name); - return 0; + return -EBUSY; }
static int clk_rcg2_set_parent(struct clk_hw *hw, u8 index)
From: Rob Clark robdclark@chromium.org
[ Upstream commit 0036bc73ccbe7e600a3468bf8e8879b122252274 ]
Recently splats like this started showing up:
WARNING: CPU: 4 PID: 251 at drivers/iommu/dma-iommu.c:451 __iommu_dma_unmap+0xb8/0xc0 Modules linked in: ath10k_snoc ath10k_core fuse msm ath mac80211 uvcvideo cfg80211 videobuf2_vmalloc videobuf2_memops vide CPU: 4 PID: 251 Comm: kworker/u16:4 Tainted: G W 5.2.0-rc5-next-20190619+ #2317 Hardware name: LENOVO 81JL/LNVNB161216, BIOS 9UCN23WW(V1.06) 10/25/2018 Workqueue: msm msm_gem_free_work [msm] pstate: 80c00005 (Nzcv daif +PAN +UAO) pc : __iommu_dma_unmap+0xb8/0xc0 lr : __iommu_dma_unmap+0x54/0xc0 sp : ffff0000119abce0 x29: ffff0000119abce0 x28: 0000000000000000 x27: ffff8001f9946648 x26: ffff8001ec271068 x25: 0000000000000000 x24: ffff8001ea3580a8 x23: ffff8001f95ba010 x22: ffff80018e83ba88 x21: ffff8001e548f000 x20: fffffffffffff000 x19: 0000000000001000 x18: 00000000c00001fe x17: 0000000000000000 x16: 0000000000000000 x15: ffff000015b70068 x14: 0000000000000005 x13: 0003142cc1be1768 x12: 0000000000000001 x11: ffff8001f6de9100 x10: 0000000000000009 x9 : ffff000015b78000 x8 : 0000000000000000 x7 : 0000000000000001 x6 : fffffffffffff000 x5 : 0000000000000fff x4 : ffff00001065dbc8 x3 : 000000000000000d x2 : 0000000000001000 x1 : fffffffffffff000 x0 : 0000000000000000 Call trace: __iommu_dma_unmap+0xb8/0xc0 iommu_dma_unmap_sg+0x98/0xb8 put_pages+0x5c/0xf0 [msm] msm_gem_free_work+0x10c/0x150 [msm] process_one_work+0x1e0/0x330 worker_thread+0x40/0x438 kthread+0x12c/0x130 ret_from_fork+0x10/0x18 ---[ end trace afc0dc5ab81a06bf ]---
Not quite sure what triggered that, but we really shouldn't be abusing dma_{map,unmap}_sg() for cache maint.
Cc: Stephen Boyd sboyd@kernel.org Tested-by: Stephen Boyd swboyd@chromium.org Reviewed-by: Jordan Crouse jcrouse@codeaurora.org Signed-off-by: Rob Clark robdclark@chromium.org Signed-off-by: Sean Paul seanpaul@chromium.org Link: https://patchwork.freedesktop.org/patch/msgid/20190630124735.27786-1-robdcla... Signed-off-by: Lee Jones lee.jones@linaro.org --- drivers/gpu/drm/msm/msm_gem.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
diff --git a/drivers/gpu/drm/msm/msm_gem.c b/drivers/gpu/drm/msm/msm_gem.c index 644faf3ae93a3..055859095cf01 100644 --- a/drivers/gpu/drm/msm/msm_gem.c +++ b/drivers/gpu/drm/msm/msm_gem.c @@ -104,7 +104,7 @@ static struct page **get_pages(struct drm_gem_object *obj) * because display controller, GPU, etc. are not coherent: */ if (msm_obj->flags & (MSM_BO_WC|MSM_BO_UNCACHED)) - dma_map_sg(dev->dev, msm_obj->sgt->sgl, + dma_sync_sg_for_device(dev->dev, msm_obj->sgt->sgl, msm_obj->sgt->nents, DMA_BIDIRECTIONAL); }
@@ -120,7 +120,7 @@ static void put_pages(struct drm_gem_object *obj) * because display controller, GPU, etc. are not coherent: */ if (msm_obj->flags & (MSM_BO_WC|MSM_BO_UNCACHED)) - dma_unmap_sg(obj->dev->dev, msm_obj->sgt->sgl, + dma_sync_sg_for_cpu(obj->dev->dev, msm_obj->sgt->sgl, msm_obj->sgt->nents, DMA_BIDIRECTIONAL);
if (msm_obj->sgt)
From: Geert Uytterhoeven geert+renesas@glider.be
Commit 372e722ea4dd4ca1 ("gpiolib: use descriptors internally") renamed the functions to use a "gpiod" prefix, and commit 79a9becda8940deb ("gpiolib: export descriptor-based GPIO interface") introduced the "raw" variants, but both changes forgot to update the comments.
Readd a similar reference to gpiod_set_value(), which was accidentally removed by commit 1e77fc82110ac36f ("gpio: Add missing open drain/source handling to gpiod_set_value_cansleep()").
Signed-off-by: Geert Uytterhoeven geert+renesas@glider.be Link: https://lore.kernel.org/r/20190701142738.25219-1-geert+renesas@glider.be Signed-off-by: Linus Walleij linus.walleij@linaro.org Signed-off-by: Lee Jones lee.jones@linaro.org --- drivers/gpio/gpiolib.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)
diff --git a/drivers/gpio/gpiolib.c b/drivers/gpio/gpiolib.c index 503405d32d240..3369dcc230e58 100644 --- a/drivers/gpio/gpiolib.c +++ b/drivers/gpio/gpiolib.c @@ -1304,7 +1304,7 @@ int gpiod_get_raw_value(const struct gpio_desc *desc) { if (!desc) return 0; - /* Should be using gpio_get_value_cansleep() */ + /* Should be using gpiod_get_raw_value_cansleep() */ WARN_ON(desc->chip->can_sleep); return _gpiod_get_raw_value(desc); } @@ -1325,7 +1325,7 @@ int gpiod_get_value(const struct gpio_desc *desc) int value; if (!desc) return 0; - /* Should be using gpio_get_value_cansleep() */ + /* Should be using gpiod_get_value_cansleep() */ WARN_ON(desc->chip->can_sleep);
value = _gpiod_get_raw_value(desc); @@ -1501,7 +1501,7 @@ void gpiod_set_raw_value(struct gpio_desc *desc, int value) { if (!desc) return; - /* Should be using gpio_set_value_cansleep() */ + /* Should be using gpiod_set_raw_value_cansleep() */ WARN_ON(desc->chip->can_sleep); _gpiod_set_raw_value(desc, value); } @@ -1522,7 +1522,7 @@ void gpiod_set_value(struct gpio_desc *desc, int value) { if (!desc) return; - /* Should be using gpio_set_value_cansleep() */ + /* Should be using gpiod_set_value_cansleep() */ WARN_ON(desc->chip->can_sleep); if (test_bit(FLAG_ACTIVE_LOW, &desc->flags)) value = !value;
From: Alexey Brodkin alexey.brodkin@synopsys.com
[ Upstream commit a66d972465d15b1d89281258805eb8b47d66bd36 ]
Initially we bumped into problem with 32-bit aligned atomic64_t on ARC, see [1]. And then during quite lengthly discussion Peter Z. mentioned ARCH_KMALLOC_MINALIGN which IMHO makes perfect sense. If allocation is done by plain kmalloc() obtained buffer will be ARCH_KMALLOC_MINALIGN aligned and then why buffer obtained via devm_kmalloc() should have any other alignment?
This way we at least get the same behavior for both types of allocation.
[1] http://lists.infradead.org/pipermail/linux-snps-arc/2018-July/004009.html [2] http://lists.infradead.org/pipermail/linux-snps-arc/2018-July/004036.html
Signed-off-by: Alexey Brodkin abrodkin@synopsys.com Cc: Greg Kroah-Hartman gregkh@linuxfoundation.org Cc: Geert Uytterhoeven geert@linux-m68k.org Cc: David Laight David.Laight@ACULAB.COM Cc: Peter Zijlstra peterz@infradead.org Cc: Thomas Gleixner tglx@linutronix.de Cc: Vineet Gupta vgupta@synopsys.com Cc: Will Deacon will.deacon@arm.com Cc: Greg KH greg@kroah.com Cc: stable@vger.kernel.org # 4.8+ Signed-off-by: Greg Kroah-Hartman gregkh@linuxfoundation.org Signed-off-by: Lee Jones lee.jones@linaro.org --- drivers/base/devres.c | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-)
diff --git a/drivers/base/devres.c b/drivers/base/devres.c index 8fc654f0807bf..9763325a9c944 100644 --- a/drivers/base/devres.c +++ b/drivers/base/devres.c @@ -24,8 +24,14 @@ struct devres_node {
struct devres { struct devres_node node; - /* -- 3 pointers */ - unsigned long long data[]; /* guarantee ull alignment */ + /* + * Some archs want to perform DMA into kmalloc caches + * and need a guaranteed alignment larger than + * the alignment of a 64-bit integer. + * Thus we use ARCH_KMALLOC_MINALIGN here and get exactly the same + * buffer alignment as if it was allocated by plain kmalloc(). + */ + u8 __aligned(ARCH_KMALLOC_MINALIGN) data[]; };
struct devres_group {
From: Hans Verkuil hans.verkuil@cisco.com
[ Upstream commit a4c30a4861c54af78c4eb8b7855524c1a96d9f80 ]
When parsing the reply of a DP_REMOTE_DPCD_READ DPCD command the result is wrong due to a missing idx increment.
This was never noticed since DP_REMOTE_DPCD_READ is currently not used, but if you enable it, then it is all wrong.
Signed-off-by: Hans Verkuil hans.verkuil@cisco.com Reviewed-by: Lyude Paul lyude@redhat.com Acked-by: Alex Deucher alexander.deucher@amd.com Link: https://patchwork.freedesktop.org/patch/msgid/e72ddac2-1dc0-100a-d816-9ac98a... Signed-off-by: Lee Jones lee.jones@linaro.org --- drivers/gpu/drm/drm_dp_mst_topology.c | 1 + 1 file changed, 1 insertion(+)
diff --git a/drivers/gpu/drm/drm_dp_mst_topology.c b/drivers/gpu/drm/drm_dp_mst_topology.c index 4d0f77f0edad1..6f6a6325b4691 100644 --- a/drivers/gpu/drm/drm_dp_mst_topology.c +++ b/drivers/gpu/drm/drm_dp_mst_topology.c @@ -431,6 +431,7 @@ static bool drm_dp_sideband_parse_remote_dpcd_read(struct drm_dp_sideband_msg_rx if (idx > raw->curlen) goto fail_len; repmsg->u.remote_dpcd_read_ack.num_bytes = raw->msg[idx]; + idx++; if (idx > raw->curlen) goto fail_len;
From: Markus Elfring elfring@users.sourceforge.net
[ Upstream commit 0108aab1161532c9b62a0d05b8115f4d0b529831 ]
Omit an extra message for a memory allocation failure in this function.
This issue was detected by using the Coccinelle software.
Signed-off-by: Markus Elfring elfring@users.sourceforge.net Reviewed-by: Christophe Leroy christophe.leroy@c-s.fr Signed-off-by: Herbert Xu herbert@gondor.apana.org.au Signed-off-by: Lee Jones lee.jones@linaro.org --- drivers/crypto/talitos.c | 1 - 1 file changed, 1 deletion(-)
diff --git a/drivers/crypto/talitos.c b/drivers/crypto/talitos.c index 1c8857e7db894..f3d0a33f4ddb4 100644 --- a/drivers/crypto/talitos.c +++ b/drivers/crypto/talitos.c @@ -1287,7 +1287,6 @@ static struct talitos_edesc *talitos_edesc_alloc(struct device *dev, if (iv_dma) dma_unmap_single(dev, iv_dma, ivsize, DMA_TO_DEVICE);
- dev_err(dev, "could not allocate edescriptor\n"); return ERR_PTR(-ENOMEM); }
From: Joe Moriarty joe.moriarty@oracle.com
[ Upstream commit 22a07038c0eaf4d1315a493ce66dcd255accba19 ]
The Parfait (version 2.1.0) static code analysis tool found the following NULL pointer derefernce problem.
- drivers/gpu/drm/drm_dp_mst_topology.c The call to drm_dp_calculate_rad() in function drm_dp_port_setup_pdt() could result in a NULL pointer being returned to port->mstb due to a failure to allocate memory for port->mstb.
Signed-off-by: Joe Moriarty joe.moriarty@oracle.com Reviewed-by: Steven Sistare steven.sistare@oracle.com Signed-off-by: Daniel Vetter daniel.vetter@ffwll.ch Link: https://patchwork.freedesktop.org/patch/msgid/20180212195144.98323-3-joe.mor... Signed-off-by: Lee Jones lee.jones@linaro.org --- drivers/gpu/drm/drm_dp_mst_topology.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-)
diff --git a/drivers/gpu/drm/drm_dp_mst_topology.c b/drivers/gpu/drm/drm_dp_mst_topology.c index 6f6a6325b4691..9fc634d6074b0 100644 --- a/drivers/gpu/drm/drm_dp_mst_topology.c +++ b/drivers/gpu/drm/drm_dp_mst_topology.c @@ -1047,10 +1047,12 @@ static bool drm_dp_port_setup_pdt(struct drm_dp_mst_port *port) lct = drm_dp_calculate_rad(port, rad);
port->mstb = drm_dp_add_mst_branch_device(lct, rad); - port->mstb->mgr = port->mgr; - port->mstb->port_parent = port; + if (port->mstb) { + port->mstb->mgr = port->mgr; + port->mstb->port_parent = port;
- send_link = true; + send_link = true; + } break; } return send_link;
From: Geert Uytterhoeven geert+renesas@glider.be
[ Upstream commit 4c8326d5ebb0de3191e98980c80ab644026728d0 ]
When exposing data access through debugfs, the correct debugfs_create_*() functions must be used, matching the data types.
Remove all casts from data pointers passed to debugfs_create_*() functions, as such casts prevent the compiler from flagging bugs.
clk_core.rate and .accuracy are "unsigned long", hence casting their addresses to "u32 *" exposed the wrong halves on big-endian 64-bit systems. Fix this by using debugfs_create_ulong() instead.
Octal permissions are preferred, as they are easier to read than symbolic permissions. Hence replace "S_IRUGO" by "0444" throughout.
Signed-off-by: Geert Uytterhoeven geert+renesas@glider.be [sboyd@codeaurora.org: Squash the octal change in too] Signed-off-by: Stephen Boyd sboyd@codeaurora.org Signed-off-by: Lee Jones lee.jones@linaro.org --- drivers/clk/clk.c | 30 ++++++++++++++---------------- 1 file changed, 14 insertions(+), 16 deletions(-)
diff --git a/drivers/clk/clk.c b/drivers/clk/clk.c index 53c068f90b376..0654dbf86364f 100644 --- a/drivers/clk/clk.c +++ b/drivers/clk/clk.c @@ -2121,18 +2121,16 @@ static int clk_debug_create_one(struct clk_core *core, struct dentry *pdentry)
core->dentry = d;
- d = debugfs_create_u32("clk_rate", S_IRUGO, core->dentry, - (u32 *)&core->rate); + d = debugfs_create_ulong("clk_rate", 0444, core->dentry, &core->rate); if (!d) goto err_out;
- d = debugfs_create_u32("clk_accuracy", S_IRUGO, core->dentry, - (u32 *)&core->accuracy); + d = debugfs_create_ulong("clk_accuracy", 0444, core->dentry, + &core->accuracy); if (!d) goto err_out;
- d = debugfs_create_u32("clk_phase", S_IRUGO, core->dentry, - (u32 *)&core->phase); + d = debugfs_create_u32("clk_phase", 0444, core->dentry, &core->phase); if (!d) goto err_out;
@@ -2141,18 +2139,18 @@ static int clk_debug_create_one(struct clk_core *core, struct dentry *pdentry) if (!d) goto err_out;
- d = debugfs_create_u32("clk_prepare_count", S_IRUGO, core->dentry, - (u32 *)&core->prepare_count); + d = debugfs_create_u32("clk_prepare_count", 0444, core->dentry, + &core->prepare_count); if (!d) goto err_out;
- d = debugfs_create_u32("clk_enable_count", S_IRUGO, core->dentry, - (u32 *)&core->enable_count); + d = debugfs_create_u32("clk_enable_count", 0444, core->dentry, + &core->enable_count); if (!d) goto err_out;
- d = debugfs_create_u32("clk_notifier_count", S_IRUGO, core->dentry, - (u32 *)&core->notifier_count); + d = debugfs_create_u32("clk_notifier_count", 0444, core->dentry, + &core->notifier_count); if (!d) goto err_out;
@@ -2246,22 +2244,22 @@ static int __init clk_debug_init(void) if (!rootdir) return -ENOMEM;
- d = debugfs_create_file("clk_summary", S_IRUGO, rootdir, &all_lists, + d = debugfs_create_file("clk_summary", 0444, rootdir, &all_lists, &clk_summary_fops); if (!d) return -ENOMEM;
- d = debugfs_create_file("clk_dump", S_IRUGO, rootdir, &all_lists, + d = debugfs_create_file("clk_dump", 0444, rootdir, &all_lists, &clk_dump_fops); if (!d) return -ENOMEM;
- d = debugfs_create_file("clk_orphan_summary", S_IRUGO, rootdir, + d = debugfs_create_file("clk_orphan_summary", 0444, rootdir, &orphan_list, &clk_summary_fops); if (!d) return -ENOMEM;
- d = debugfs_create_file("clk_orphan_dump", S_IRUGO, rootdir, + d = debugfs_create_file("clk_orphan_dump", 0444, rootdir, &orphan_list, &clk_dump_fops); if (!d) return -ENOMEM;
From: Will Deacon will.deacon@arm.com
[ Upstream commit a25ffd3a6302a67814280274d8f1aa4ae2ea4b59 ]
Printing raw pointer values in backtraces has potential security implications and are of questionable value anyway.
This patch follows x86's lead and removes the "Exception stack:" dump from kernel backtraces, as well as converting PC/LR values to symbols such as "sysrq_handle_crash+0x20/0x30".
Tested-by: Laura Abbott labbott@redhat.com Signed-off-by: Will Deacon will.deacon@arm.com Signed-off-by: Lee Jones lee.jones@linaro.org --- arch/arm64/kernel/process.c | 9 +++-- arch/arm64/kernel/traps.c | 72 ++----------------------------------- 2 files changed, 7 insertions(+), 74 deletions(-)
diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c index 10d6627673cbf..2733b04900d1c 100644 --- a/arch/arm64/kernel/process.c +++ b/arch/arm64/kernel/process.c @@ -180,11 +180,10 @@ void __show_regs(struct pt_regs *regs) }
show_regs_print_info(KERN_DEFAULT); - print_symbol("PC is at %s\n", instruction_pointer(regs)); - print_symbol("LR is at %s\n", lr); - printk("pc : [<%016llx>] lr : [<%016llx>] pstate: %08llx\n", - regs->pc, lr, regs->pstate); - printk("sp : %016llx\n", sp); + print_symbol("pc : %s\n", regs->pc); + print_symbol("lr : %s\n", lr); + printk("sp : %016llx pstate : %08llx\n", sp, regs->pstate); + for (i = top_reg; i >= 0; i--) { printk("x%-2d: %016llx ", i, regs->regs[i]); if (i % 2 == 0) diff --git a/arch/arm64/kernel/traps.c b/arch/arm64/kernel/traps.c index 02710f99c1374..0cc78d60dac33 100644 --- a/arch/arm64/kernel/traps.c +++ b/arch/arm64/kernel/traps.c @@ -51,63 +51,9 @@ static const char *handler[]= {
int show_unhandled_signals = 0;
-/* - * Dump out the contents of some memory nicely... - */ -static void dump_mem(const char *lvl, const char *str, unsigned long bottom, - unsigned long top, bool compat) -{ - unsigned long first; - mm_segment_t fs; - int i; - unsigned int width = compat ? 4 : 8; - - /* - * We need to switch to kernel mode so that we can use __get_user - * to safely read from kernel space. - */ - fs = get_fs(); - set_fs(KERNEL_DS); - - printk("%s%s(0x%016lx to 0x%016lx)\n", lvl, str, bottom, top); - - for (first = bottom & ~31; first < top; first += 32) { - unsigned long p; - char str[sizeof(" 12345678") * 8 + 1]; - - memset(str, ' ', sizeof(str)); - str[sizeof(str) - 1] = '\0'; - - for (p = first, i = 0; i < (32 / width) - && p < top; i++, p += width) { - if (p >= bottom && p < top) { - unsigned long val; - - if (width == 8) { - if (__get_user(val, (unsigned long *)p) == 0) - sprintf(str + i * 17, " %016lx", val); - else - sprintf(str + i * 17, " ????????????????"); - } else { - if (__get_user(val, (unsigned int *)p) == 0) - sprintf(str + i * 9, " %08lx", val); - else - sprintf(str + i * 9, " ????????"); - } - } - } - printk("%s%04lx:%s\n", lvl, first & 0xffff, str); - } - - set_fs(fs); -} - static void dump_backtrace_entry(unsigned long where) { - /* - * Note that 'where' can have a physical address, but it's not handled. - */ - print_ip_sym(where); + printk(" %pS\n", (void *)where); }
static void __dump_instr(const char *lvl, struct pt_regs *regs) @@ -170,20 +116,11 @@ static void dump_backtrace(struct pt_regs *regs, struct task_struct *tsk) }
pr_emerg("Call trace:\n"); - while (1) { + do { unsigned long where = frame.pc; - unsigned long stack; - int ret;
dump_backtrace_entry(where); - ret = unwind_frame(&frame); - if (ret < 0) - break; - stack = frame.sp; - if (in_exception_text(where)) - dump_mem("", "Exception stack", stack, - stack + sizeof(struct pt_regs), false); - } + } while (!unwind_frame(&frame)); }
void show_stack(struct task_struct *tsk, unsigned long *sp) @@ -220,9 +157,6 @@ static int __die(const char *str, int err, struct thread_info *thread, TASK_COMM_LEN, tsk->comm, task_pid_nr(tsk), thread + 1);
if (!user_mode(regs) || in_interrupt()) { - dump_mem(KERN_EMERG, "Stack: ", regs->sp, - THREAD_SIZE + (unsigned long)task_stack_page(tsk), - compat_user_mode(regs)); dump_backtrace(regs, tsk); dump_instr(KERN_EMERG, regs); }
From: Yangtao Li tiny.windzz@gmail.com
[ Upstream commit 20d8e8611eb0596047fd4389be7a7203a883b9bf ]
of_find_node_by_path() acquires a reference to the node returned by it and that reference needs to be dropped by its caller. This place is not doing this, so fix it.
Signed-off-by: Yangtao Li tiny.windzz@gmail.com Signed-off-by: Greg Kroah-Hartman gregkh@linuxfoundation.org Signed-off-by: Lee Jones lee.jones@linaro.org --- drivers/tty/serial/sunsu.c | 20 +++++++++++++++----- 1 file changed, 15 insertions(+), 5 deletions(-)
diff --git a/drivers/tty/serial/sunsu.c b/drivers/tty/serial/sunsu.c index e124d2e88996f..8db64282260fb 100644 --- a/drivers/tty/serial/sunsu.c +++ b/drivers/tty/serial/sunsu.c @@ -1393,22 +1393,32 @@ static inline struct console *SUNSU_CONSOLE(void) static enum su_type su_get_type(struct device_node *dp) { struct device_node *ap = of_find_node_by_path("/aliases"); + enum su_type rc = SU_PORT_PORT;
if (ap) { + struct device_node *tmp; const char *keyb = of_get_property(ap, "keyboard", NULL); const char *ms = of_get_property(ap, "mouse", NULL);
if (keyb) { - if (dp == of_find_node_by_path(keyb)) - return SU_PORT_KBD; + tmp = of_find_node_by_path(keyb); + if (tmp && dp == tmp){ + rc = SU_PORT_KBD; + goto out; + } } if (ms) { - if (dp == of_find_node_by_path(ms)) - return SU_PORT_MS; + tmp = of_find_node_by_path(ms); + if (tmp && dp == tmp){ + rc = SU_PORT_MS; + goto out; + } } }
- return SU_PORT_PORT; +out: + of_node_put(ap); + return rc; }
static int su_probe(struct platform_device *op)
From: Hamad Kadmany hkadmany@codeaurora.org
[ Upstream commit 6ccae584014ef7074359eb4151086beef66ecfa9 ]
Firmware ready event may take longer than current timeout in some scenarios, for example with multiple RFs connected where each requires an initial calibration.
Increase the timeout to support these scenarios.
Signed-off-by: Hamad Kadmany hkadmany@codeaurora.org Signed-off-by: Maya Erez merez@codeaurora.org Signed-off-by: Kalle Valo kvalo@codeaurora.org Signed-off-by: Lee Jones lee.jones@linaro.org --- drivers/net/wireless/ath/wil6210/main.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/drivers/net/wireless/ath/wil6210/main.c b/drivers/net/wireless/ath/wil6210/main.c index f09fafaaaf1a3..c377937aae1c4 100644 --- a/drivers/net/wireless/ath/wil6210/main.c +++ b/drivers/net/wireless/ath/wil6210/main.c @@ -741,7 +741,7 @@ static void wil_bl_crash_info(struct wil6210_priv *wil, bool is_err)
static int wil_wait_for_fw_ready(struct wil6210_priv *wil) { - ulong to = msecs_to_jiffies(1000); + ulong to = msecs_to_jiffies(2000); ulong left = wait_for_completion_timeout(&wil->wmi_ready, to);
if (0 == left) {
From: Dedy Lansky dlansky@codeaurora.org
[ Upstream commit 6d9eb7ebae3d7e951bc0999235ae7028eb4cae4f ]
For negative temperatures, "temp" debugfs is showing wrong values. Use signed types so proper calculations is done for sub zero temperatures.
Signed-off-by: Dedy Lansky dlansky@codeaurora.org Signed-off-by: Maya Erez merez@codeaurora.org Signed-off-by: Kalle Valo kvalo@codeaurora.org Signed-off-by: Lee Jones lee.jones@linaro.org --- drivers/net/wireless/ath/wil6210/debugfs.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-)
diff --git a/drivers/net/wireless/ath/wil6210/debugfs.c b/drivers/net/wireless/ath/wil6210/debugfs.c index 97bc186f97282..2da03d69ed42e 100644 --- a/drivers/net/wireless/ath/wil6210/debugfs.c +++ b/drivers/net/wireless/ath/wil6210/debugfs.c @@ -1088,7 +1088,7 @@ static const struct file_operations fops_ssid = { };
/*---------temp------------*/ -static void print_temp(struct seq_file *s, const char *prefix, u32 t) +static void print_temp(struct seq_file *s, const char *prefix, s32 t) { switch (t) { case 0: @@ -1096,7 +1096,8 @@ static void print_temp(struct seq_file *s, const char *prefix, u32 t) seq_printf(s, "%s N/A\n", prefix); break; default: - seq_printf(s, "%s %d.%03d\n", prefix, t / 1000, t % 1000); + seq_printf(s, "%s %s%d.%03d\n", prefix, (t < 0 ? "-" : ""), + abs(t / 1000), abs(t % 1000)); break; } } @@ -1104,7 +1105,7 @@ static void print_temp(struct seq_file *s, const char *prefix, u32 t) static int wil_temp_debugfs_show(struct seq_file *s, void *data) { struct wil6210_priv *wil = s->private; - u32 t_m, t_r; + s32 t_m, t_r; int rc = wmi_get_temperature(wil, &t_m, &t_r);
if (rc) {
From: Subhash Jadavani subhashj@codeaurora.org
[ Upstream commit 69a6fff068567469c0ef1156ae5ac8d3d71701f0 ]
UFSHCD_QUIRK_BROKEN_UFS_HCI_VERSION is only applicable for QCOM UFS host controller version 2.x.y and this has been fixed from version 3.x.y onwards, hence this change removes this quirk for version 3.x.y onwards.
[mkp: applied by hand]
Signed-off-by: Subhash Jadavani subhashj@codeaurora.org Signed-off-by: Asutosh Das asutoshd@codeaurora.org Signed-off-by: Martin K. Petersen martin.petersen@oracle.com Signed-off-by: Lee Jones lee.jones@linaro.org --- drivers/scsi/ufs/ufs-qcom.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/drivers/scsi/ufs/ufs-qcom.c b/drivers/scsi/ufs/ufs-qcom.c index 4b82c3765e013..2b779a55f6999 100644 --- a/drivers/scsi/ufs/ufs-qcom.c +++ b/drivers/scsi/ufs/ufs-qcom.c @@ -1032,7 +1032,7 @@ static void ufs_qcom_advertise_quirks(struct ufs_hba *hba) hba->quirks |= UFSHCD_QUIRK_BROKEN_LCC; }
- if (host->hw_ver.major >= 0x2) { + if (host->hw_ver.major == 0x2) { hba->quirks |= UFSHCD_QUIRK_BROKEN_UFS_HCI_VERSION;
if (!ufs_qcom_cap_qunipro(host))
From: Dedy Lansky dlansky@codeaurora.org
[ Upstream commit 3d6b72729cc2933906de8d2c602ae05e920b2122 ]
wil_err inside wil_rx_refill can flood the log buffer. Replace it with wil_err_ratelimited.
Signed-off-by: Dedy Lansky dlansky@codeaurora.org Signed-off-by: Maya Erez merez@codeaurora.org Signed-off-by: Kalle Valo kvalo@codeaurora.org Signed-off-by: Lee Jones lee.jones@linaro.org --- drivers/net/wireless/ath/wil6210/txrx.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
diff --git a/drivers/net/wireless/ath/wil6210/txrx.c b/drivers/net/wireless/ath/wil6210/txrx.c index 3bc9bc0efbacc..af436292190b1 100644 --- a/drivers/net/wireless/ath/wil6210/txrx.c +++ b/drivers/net/wireless/ath/wil6210/txrx.c @@ -538,8 +538,8 @@ static int wil_rx_refill(struct wil6210_priv *wil, int count) v->swtail = next_tail) { rc = wil_vring_alloc_skb(wil, v, v->swtail, headroom); if (unlikely(rc)) { - wil_err(wil, "Error %d in wil_rx_refill[%d]\n", - rc, v->swtail); + wil_err_ratelimited(wil, "Error %d in rx refill[%d]\n", + rc, v->swtail); break; } }
From: Mohit Aggarwal maggarwa@codeaurora.org
[ Upstream commit 83220bf38b77a830f8e62ab1a0d0408304f9b966 ]
In order to set time in rtc, need to disable rtc hw before writing into rtc registers.
Also fixes disabling of alarm while setting rtc time.
Signed-off-by: Mohit Aggarwal maggarwa@codeaurora.org Signed-off-by: Alexandre Belloni alexandre.belloni@bootlin.com Signed-off-by: Lee Jones lee.jones@linaro.org --- drivers/rtc/rtc-pm8xxx.c | 49 +++++++++++++++++++++++++++++++--------- 1 file changed, 38 insertions(+), 11 deletions(-)
diff --git a/drivers/rtc/rtc-pm8xxx.c b/drivers/rtc/rtc-pm8xxx.c index a0dae6271ff64..cd4434cca877c 100644 --- a/drivers/rtc/rtc-pm8xxx.c +++ b/drivers/rtc/rtc-pm8xxx.c @@ -74,16 +74,18 @@ struct pm8xxx_rtc { /* * Steps to write the RTC registers. * 1. Disable alarm if enabled. - * 2. Write 0x00 to LSB. - * 3. Write Byte[1], Byte[2], Byte[3] then Byte[0]. - * 4. Enable alarm if disabled in step 1. + * 2. Disable rtc if enabled. + * 3. Write 0x00 to LSB. + * 4. Write Byte[1], Byte[2], Byte[3] then Byte[0]. + * 5. Enable rtc if disabled in step 2. + * 6. Enable alarm if disabled in step 1. */ static int pm8xxx_rtc_set_time(struct device *dev, struct rtc_time *tm) { int rc, i; unsigned long secs, irq_flags; - u8 value[NUM_8_BIT_RTC_REGS], alarm_enabled = 0; - unsigned int ctrl_reg; + u8 value[NUM_8_BIT_RTC_REGS], alarm_enabled = 0, rtc_disabled = 0; + unsigned int ctrl_reg, rtc_ctrl_reg; struct pm8xxx_rtc *rtc_dd = dev_get_drvdata(dev); const struct pm8xxx_rtc_regs *regs = rtc_dd->regs;
@@ -92,23 +94,38 @@ static int pm8xxx_rtc_set_time(struct device *dev, struct rtc_time *tm)
rtc_tm_to_time(tm, &secs);
+ dev_dbg(dev, "Seconds value to be written to RTC = %lu\n", secs); + for (i = 0; i < NUM_8_BIT_RTC_REGS; i++) { value[i] = secs & 0xFF; secs >>= 8; }
- dev_dbg(dev, "Seconds value to be written to RTC = %lu\n", secs); - spin_lock_irqsave(&rtc_dd->ctrl_reg_lock, irq_flags);
- rc = regmap_read(rtc_dd->regmap, regs->ctrl, &ctrl_reg); + rc = regmap_read(rtc_dd->regmap, regs->alarm_ctrl, &ctrl_reg); if (rc) goto rtc_rw_fail;
if (ctrl_reg & regs->alarm_en) { alarm_enabled = 1; ctrl_reg &= ~regs->alarm_en; - rc = regmap_write(rtc_dd->regmap, regs->ctrl, ctrl_reg); + rc = regmap_write(rtc_dd->regmap, regs->alarm_ctrl, ctrl_reg); + if (rc) { + dev_err(dev, "Write to RTC Alarm control register failed\n"); + goto rtc_rw_fail; + } + } + + /* Disable RTC H/w before writing on RTC register */ + rc = regmap_read(rtc_dd->regmap, regs->ctrl, &rtc_ctrl_reg); + if (rc) + goto rtc_rw_fail; + + if (rtc_ctrl_reg & PM8xxx_RTC_ENABLE) { + rtc_disabled = 1; + rtc_ctrl_reg &= ~PM8xxx_RTC_ENABLE; + rc = regmap_write(rtc_dd->regmap, regs->ctrl, rtc_ctrl_reg); if (rc) { dev_err(dev, "Write to RTC control register failed\n"); goto rtc_rw_fail; @@ -137,11 +154,21 @@ static int pm8xxx_rtc_set_time(struct device *dev, struct rtc_time *tm) goto rtc_rw_fail; }
+ /* Enable RTC H/w after writing on RTC register */ + if (rtc_disabled) { + rtc_ctrl_reg |= PM8xxx_RTC_ENABLE; + rc = regmap_write(rtc_dd->regmap, regs->ctrl, rtc_ctrl_reg); + if (rc) { + dev_err(dev, "Write to RTC control register failed\n"); + goto rtc_rw_fail; + } + } + if (alarm_enabled) { ctrl_reg |= regs->alarm_en; - rc = regmap_write(rtc_dd->regmap, regs->ctrl, ctrl_reg); + rc = regmap_write(rtc_dd->regmap, regs->alarm_ctrl, ctrl_reg); if (rc) { - dev_err(dev, "Write to RTC control register failed\n"); + dev_err(dev, "Write to RTC Alarm control register failed\n"); goto rtc_rw_fail; } }
From: Chris Lew clew@codeaurora.org
[ Upstream commit a216000f0140f415cec96129f777b5234c9d142f ]
Endianness can vary in the system, add le32_to_cpu when comparing partition sizes from smem.
Signed-off-by: Chris Lew clew@codeaurora.org Acked-by: Bjorn Andersson bjorn.andersson@linaro.org Signed-off-by: Andy Gross andy.gross@linaro.org Signed-off-by: Lee Jones lee.jones@linaro.org --- drivers/soc/qcom/smem.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/drivers/soc/qcom/smem.c b/drivers/soc/qcom/smem.c index 19019aa092e86..a1572075b8acc 100644 --- a/drivers/soc/qcom/smem.c +++ b/drivers/soc/qcom/smem.c @@ -646,7 +646,7 @@ static int qcom_smem_enumerate_partitions(struct qcom_smem *smem, return -EINVAL; }
- if (header->size != entry->size) { + if (le32_to_cpu(header->size) != le32_to_cpu(entry->size)) { dev_err(smem->dev, "Partition %d has invalid size\n", i); return -EINVAL;
From: Rob Herring robh@kernel.org
[ Upstream commit bd82bbf38cbe27f2c65660da801900d71bcc5cc8 ]
The ref counting is broken for OF_DYNAMIC when sysfs is disabled because the kobject initialization is skipped. Only the properties add/remove/update should be skipped for !SYSFS config.
Tested-by: Nicolas Pitre nico@linaro.org Reviewed-by: Frank Rowand frowand.list@gmail.com Acked-by: Grant Likely grant.likely@secretlab.ca Signed-off-by: Rob Herring robh@kernel.org Signed-off-by: Lee Jones lee.jones@linaro.org --- drivers/of/base.c | 3 --- 1 file changed, 3 deletions(-)
diff --git a/drivers/of/base.c b/drivers/of/base.c index 27783223ca5cd..8adffecd710b8 100644 --- a/drivers/of/base.c +++ b/drivers/of/base.c @@ -167,9 +167,6 @@ int __of_attach_node_sysfs(struct device_node *np) struct property *pp; int rc;
- if (!IS_ENABLED(CONFIG_SYSFS)) - return 0; - if (!of_kset) return 0;
From: Alexander Shishkin alexander.shishkin@linux.intel.com
[ Upstream commit f25d8ba9e1b204b90fbf55970ea6e68955006068 ]
A comment is in a wrong place in perf_event_create_kernel_counter(). Fix that.
Signed-off-by: Alexander Shishkin alexander.shishkin@linux.intel.com Signed-off-by: Peter Zijlstra (Intel) peterz@infradead.org Cc: Arnaldo Carvalho de Melo acme@redhat.com Cc: David Ahern dsahern@gmail.com Cc: Jiri Olsa jolsa@redhat.com Cc: Linus Torvalds torvalds@linux-foundation.org Cc: Mark Rutland mark.rutland@arm.com Cc: Namhyung Kim namhyung@kernel.org Cc: Stephane Eranian eranian@google.com Cc: Thomas Gleixner tglx@linutronix.de Cc: Vince Weaver vincent.weaver@maine.edu Link: https://lkml.kernel.org/r/20191030134731.5437-2-alexander.shishkin@linux.int... Signed-off-by: Ingo Molnar mingo@kernel.org Signed-off-by: Lee Jones lee.jones@linaro.org --- kernel/events/core.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-)
diff --git a/kernel/events/core.c b/kernel/events/core.c index a7014f854e67b..e61ada5574ffc 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -8727,10 +8727,6 @@ perf_event_create_kernel_counter(struct perf_event_attr *attr, int cpu, struct perf_event *event; int err;
- /* - * Get the target context (task or percpu): - */ - event = perf_event_alloc(attr, cpu, task, NULL, NULL, overflow_handler, context, -1); if (IS_ERR(event)) { @@ -8741,6 +8737,9 @@ perf_event_create_kernel_counter(struct perf_event_attr *attr, int cpu, /* Mark owner so we could distinguish it from user events. */ event->owner = EVENT_OWNER_KERNEL;
+ /* + * Get the target context (task or percpu): + */ ctx = find_get_context(event->pmu, task, event); if (IS_ERR(ctx)) { err = PTR_ERR(ctx);
From: Austin Kim austindh.kim@gmail.com
[ Upstream commit 7ea362427c170061b8822dd41bafaa72b3bcb9ad ]
If !area->pages statement is true where memory allocation fails, area is freed.
In this case 'area->pages = pages' should not executed. So move 'area->pages = pages' after if statement.
[akpm@linux-foundation.org: give area->pages the same treatment] Link: http://lkml.kernel.org/r/20190830035716.GA190684@LGEARND20B15 Signed-off-by: Austin Kim austindh.kim@gmail.com Acked-by: Michal Hocko mhocko@suse.com Reviewed-by: Andrew Morton akpm@linux-foundation.org Cc: Uladzislau Rezki (Sony) urezki@gmail.com Cc: Roman Gushchin guro@fb.com Cc: Roman Penyaev rpenyaev@suse.de Cc: Rick Edgecombe rick.p.edgecombe@intel.com Cc: Mike Rapoport rppt@linux.ibm.com Cc: Andrey Ryabinin aryabinin@virtuozzo.com Signed-off-by: Andrew Morton akpm@linux-foundation.org Signed-off-by: Linus Torvalds torvalds@linux-foundation.org Signed-off-by: Lee Jones lee.jones@linaro.org --- mm/vmalloc.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-)
diff --git a/mm/vmalloc.c b/mm/vmalloc.c index d118e59a2bef5..21d292e45599f 100644 --- a/mm/vmalloc.c +++ b/mm/vmalloc.c @@ -1593,7 +1593,6 @@ static void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask, nr_pages = get_vm_area_size(area) >> PAGE_SHIFT; array_size = (nr_pages * sizeof(struct page *));
- area->nr_pages = nr_pages; /* Please note that the recursion is strictly bounded. */ if (array_size > PAGE_SIZE) { pages = __vmalloc_node(array_size, 1, nested_gfp|__GFP_HIGHMEM, @@ -1602,13 +1601,16 @@ static void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask, } else { pages = kmalloc_node(array_size, nested_gfp, node); } - area->pages = pages; - if (!area->pages) { + + if (!pages) { remove_vm_area(area->addr); kfree(area); return NULL; }
+ area->pages = pages; + area->nr_pages = nr_pages; + for (i = 0; i < area->nr_pages; i++) { struct page *page;
From: George Spelvin lkml@sdf.org
[ Upstream commit 043b3f7b6388fca6be86ca82979f66c5723a0d10 ]
Rather than a fixed-size array of pending sorted runs, use the ->prev links to keep track of things. This reduces stack usage, eliminates some ugly overflow handling, and reduces the code size.
Also: * merge() no longer needs to handle NULL inputs, so simplify. * The same applies to merge_and_restore_back_links(), which is renamed to the less ponderous merge_final(). (It's a static helper function, so we don't need a super-descriptive name; comments will do.) * Document the actual return value requirements on the (*cmp)() function; some callers are already using this feature.
x86-64 code size 1086 -> 739 bytes (-347)
(Yes, I see checkpatch complaining about no space after comma in "__attribute__((nonnull(2,3,4,5)))". Checkpatch is wrong.)
Feedback from Rasmus Villemoes, Andy Shevchenko and Geert Uytterhoeven.
[akpm@linux-foundation.org: remove __pure usage due to mysterious warning] Link: http://lkml.kernel.org/r/f63c410e0ff76009c9b58e01027e751ff7fdb749.1552704200... Signed-off-by: George Spelvin lkml@sdf.org Acked-by: Andrey Abramov st5pub@yandex.ru Acked-by: Rasmus Villemoes linux@rasmusvillemoes.dk Reviewed-by: Andy Shevchenko andriy.shevchenko@linux.intel.com Cc: Geert Uytterhoeven geert@linux-m68k.org Cc: Daniel Wagner daniel.wagner@siemens.com Cc: Dave Chinner dchinner@redhat.com Cc: Don Mullis don.mullis@gmail.com Signed-off-by: Andrew Morton akpm@linux-foundation.org Signed-off-by: Linus Torvalds torvalds@linux-foundation.org Signed-off-by: Lee Jones lee.jones@linaro.org --- include/linux/list_sort.h | 1 + lib/list_sort.c | 165 ++++++++++++++++++++++++-------------- 2 files changed, 104 insertions(+), 62 deletions(-)
diff --git a/include/linux/list_sort.h b/include/linux/list_sort.h index 1a2df2efb7716..8a03fd8c7ec36 100644 --- a/include/linux/list_sort.h +++ b/include/linux/list_sort.h @@ -5,6 +5,7 @@
struct list_head;
+__attribute__((nonnull(2,3))) void list_sort(void *priv, struct list_head *head, int (*cmp)(void *priv, struct list_head *a, struct list_head *b)); diff --git a/lib/list_sort.c b/lib/list_sort.c index 3fe401067e20b..b4b130a9d536f 100644 --- a/lib/list_sort.c +++ b/lib/list_sort.c @@ -9,33 +9,41 @@ #include <linux/list_sort.h> #include <linux/list.h>
-#define MAX_LIST_LENGTH_BITS 20 +typedef int __attribute__((nonnull(2,3))) (*cmp_func)(void *, + struct list_head const *, struct list_head const *);
/* * Returns a list organized in an intermediate format suited * to chaining of merge() calls: null-terminated, no reserved or * sentinel head node, "prev" links not maintained. */ -static struct list_head *merge(void *priv, - int (*cmp)(void *priv, struct list_head *a, - struct list_head *b), +__attribute__((nonnull(2,3,4))) +static struct list_head *merge(void *priv, cmp_func cmp, struct list_head *a, struct list_head *b) { - struct list_head head, *tail = &head; + struct list_head *head, **tail = &head;
- while (a && b) { + for (;;) { /* if equal, take 'a' -- important for sort stability */ - if ((*cmp)(priv, a, b) <= 0) { - tail->next = a; + if (cmp(priv, a, b) <= 0) { + *tail = a; + tail = &a->next; a = a->next; + if (!a) { + *tail = b; + break; + } } else { - tail->next = b; + *tail = b; + tail = &b->next; b = b->next; + if (!b) { + *tail = a; + break; + } } - tail = tail->next; } - tail->next = a?:b; - return head.next; + return head; }
/* @@ -45,44 +53,52 @@ static struct list_head *merge(void *priv, * prev-link restoration pass, or maintaining the prev links * throughout. */ -static void merge_and_restore_back_links(void *priv, - int (*cmp)(void *priv, struct list_head *a, - struct list_head *b), - struct list_head *head, - struct list_head *a, struct list_head *b) +__attribute__((nonnull(2,3,4,5))) +static void merge_final(void *priv, cmp_func cmp, struct list_head *head, + struct list_head *a, struct list_head *b) { struct list_head *tail = head; u8 count = 0;
- while (a && b) { + for (;;) { /* if equal, take 'a' -- important for sort stability */ - if ((*cmp)(priv, a, b) <= 0) { + if (cmp(priv, a, b) <= 0) { tail->next = a; a->prev = tail; + tail = a; a = a->next; + if (!a) + break; } else { tail->next = b; b->prev = tail; + tail = b; b = b->next; + if (!b) { + b = a; + break; + } } - tail = tail->next; } - tail->next = a ? : b;
+ /* Finish linking remainder of list b on to tail */ + tail->next = b; do { /* - * In worst cases this loop may run many iterations. + * If the merge is highly unbalanced (e.g. the input is + * already sorted), this loop may run many iterations. * Continue callbacks to the client even though no * element comparison is needed, so the client's cmp() * routine can invoke cond_resched() periodically. */ - if (unlikely(!(++count))) - (*cmp)(priv, tail->next, tail->next); - - tail->next->prev = tail; - tail = tail->next; - } while (tail->next); - + if (unlikely(!++count)) + cmp(priv, b, b); + b->prev = tail; + tail = b; + b = b->next; + } while (b); + + /* And the final links to make a circular doubly-linked list */ tail->next = head; head->prev = tail; } @@ -93,56 +109,81 @@ static void merge_and_restore_back_links(void *priv, * @head: the list to sort * @cmp: the elements comparison function * - * This function implements "merge sort", which has O(nlog(n)) - * complexity. + * This function implements a bottom-up merge sort, which has O(nlog(n)) + * complexity. We use depth-first order to take advantage of cacheing. + * (E.g. when we get to the fourth element, we immediately merge the + * first two 2-element lists.) + * + * The comparison funtion @cmp must return > 0 if @a should sort after + * @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should + * sort before @b *or* their original order should be preserved. It is + * always called with the element that came first in the input in @a, + * and list_sort is a stable sort, so it is not necessary to distinguish + * the @a < @b and @a == @b cases. + * + * This is compatible with two styles of @cmp function: + * - The traditional style which returns <0 / =0 / >0, or + * - Returning a boolean 0/1. + * The latter offers a chance to save a few cycles in the comparison + * (which is used by e.g. plug_ctx_cmp() in block/blk-mq.c). * - * The comparison function @cmp must return a negative value if @a - * should sort before @b, and a positive value if @a should sort after - * @b. If @a and @b are equivalent, and their original relative - * ordering is to be preserved, @cmp must return 0. + * A good way to write a multi-word comparison is + * if (a->high != b->high) + * return a->high > b->high; + * if (a->middle != b->middle) + * return a->middle > b->middle; + * return a->low > b->low; */ +__attribute__((nonnull(2,3))) void list_sort(void *priv, struct list_head *head, int (*cmp)(void *priv, struct list_head *a, struct list_head *b)) { - struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists - -- last slot is a sentinel */ - int lev; /* index into part[] */ - int max_lev = 0; - struct list_head *list; + struct list_head *list = head->next, *pending = NULL; + size_t count = 0; /* Count of pending */
- if (list_empty(head)) + if (list == head->prev) /* Zero or one elements */ return;
- memset(part, 0, sizeof(part)); - + /* Convert to a null-terminated singly-linked list. */ head->prev->next = NULL; - list = head->next;
- while (list) { + /* + * Data structure invariants: + * - All lists are singly linked and null-terminated; prev + * pointers are not maintained. + * - pending is a prev-linked "list of lists" of sorted + * sublists awaiting further merging. + * - Each of the sorted sublists is power-of-two in size, + * corresponding to bits set in "count". + * - Sublists are sorted by size and age, smallest & newest at front. + */ + do { + size_t bits; struct list_head *cur = list; + + /* Extract the head of "list" as a single-element list "cur" */ list = list->next; cur->next = NULL;
- for (lev = 0; part[lev]; lev++) { - cur = merge(priv, cmp, part[lev], cur); - part[lev] = NULL; - } - if (lev > max_lev) { - if (unlikely(lev >= ARRAY_SIZE(part)-1)) { - printk_once(KERN_DEBUG "list too long for efficiency\n"); - lev--; - } - max_lev = lev; + /* Do merges corresponding to set lsbits in count */ + for (bits = count; bits & 1; bits >>= 1) { + cur = merge(priv, (cmp_func)cmp, pending, cur); + pending = pending->prev; /* Untouched by merge() */ } - part[lev] = cur; - } - - for (lev = 0; lev < max_lev; lev++) - if (part[lev]) - list = merge(priv, cmp, part[lev], list); + /* And place the result at the head of "pending" */ + cur->prev = pending; + pending = cur; + count++; + } while (list->next);
- merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); + /* Now merge together last element with all pending lists */ + while (pending->prev) { + list = merge(priv, (cmp_func)cmp, pending, list); + pending = pending->prev; + } + /* The final merge, rebuilding prev links */ + merge_final(priv, (cmp_func)cmp, head, pending, list); } EXPORT_SYMBOL(list_sort);
linux-stable-mirror@lists.linaro.org
-
Lee Jones