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 f59ca27a4a357..93b20ad23c23f 100644 --- a/drivers/gpu/drm/msm/msm_gem.c +++ b/drivers/gpu/drm/msm/msm_gem.c @@ -108,7 +108,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); }

@@ -138,7 +138,7 @@ static void put_pages(struct drm_gem_object *obj) * 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);

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 bf4eed5f6a7ee..a7c7f522fe1c4 100644 --- a/drivers/gpu/drm/drm_dp_mst_topology.c +++ b/drivers/gpu/drm/drm_dp_mst_topology.c @@ -439,6 +439,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: Maya Erez merez@codeaurora.org

[ Upstream commit 979c9d8d01c482b1befb44dc639ecb907b5a37bd ]

HALP ICR is set as long as the FW should stay awake. To prevent its multiple handling the driver masks this IRQ bit. However, if there is a different MISC ICR before the driver clears this bit, there is a risk of race condition between HALP mask and unmask. This race leads to HALP timeout, in case it is mistakenly masked. Add an atomic flag to indicate if HALP ICR should be handled.

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/interrupt.c | 12 ++++++++---- drivers/net/wireless/ath/wil6210/main.c | 3 +++ drivers/net/wireless/ath/wil6210/wil6210.h | 1 + 3 files changed, 12 insertions(+), 4 deletions(-)

diff --git a/drivers/net/wireless/ath/wil6210/interrupt.c b/drivers/net/wireless/ath/wil6210/interrupt.c index 0655cd8845142..d161dc930313d 100644 --- a/drivers/net/wireless/ath/wil6210/interrupt.c +++ b/drivers/net/wireless/ath/wil6210/interrupt.c @@ -1,6 +1,6 @@ /* * Copyright (c) 2012-2017 Qualcomm Atheros, Inc. - * Copyright (c) 2018, The Linux Foundation. All rights reserved. + * Copyright (c) 2018-2019, The Linux Foundation. All rights reserved. * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above @@ -590,10 +590,14 @@ static irqreturn_t wil6210_irq_misc(int irq, void *cookie) }

if (isr & BIT_DMA_EP_MISC_ICR_HALP) { - wil_dbg_irq(wil, "irq_misc: HALP IRQ invoked\n"); - wil6210_mask_halp(wil); isr &= ~BIT_DMA_EP_MISC_ICR_HALP; - complete(&wil->halp.comp); + if (wil->halp.handle_icr) { + /* no need to handle HALP ICRs until next vote */ + wil->halp.handle_icr = false; + wil_dbg_irq(wil, "irq_misc: HALP IRQ invoked\n"); + wil6210_mask_halp(wil); + complete(&wil->halp.comp); + } }

wil->isr_misc = isr; diff --git a/drivers/net/wireless/ath/wil6210/main.c b/drivers/net/wireless/ath/wil6210/main.c index 10673fa9388ec..28d2bfd0fde79 100644 --- a/drivers/net/wireless/ath/wil6210/main.c +++ b/drivers/net/wireless/ath/wil6210/main.c @@ -1814,11 +1814,14 @@ void wil_halp_vote(struct wil6210_priv *wil)

if (++wil->halp.ref_cnt == 1) { reinit_completion(&wil->halp.comp); + /* mark to IRQ context to handle HALP ICR */ + wil->halp.handle_icr = true; wil6210_set_halp(wil); rc = wait_for_completion_timeout(&wil->halp.comp, to_jiffies); if (!rc) { wil_err(wil, "HALP vote timed out\n"); /* Mask HALP as done in case the interrupt is raised */ + wil->halp.handle_icr = false; wil6210_mask_halp(wil); } else { wil_dbg_irq(wil, diff --git a/drivers/net/wireless/ath/wil6210/wil6210.h b/drivers/net/wireless/ath/wil6210/wil6210.h index 75fe1a3b70466..6a05f59ee58e9 100644 --- a/drivers/net/wireless/ath/wil6210/wil6210.h +++ b/drivers/net/wireless/ath/wil6210/wil6210.h @@ -778,6 +778,7 @@ struct wil_halp { struct mutex lock; /* protect halp ref_cnt */ unsigned int ref_cnt; struct completion comp; + u8 handle_icr; };

struct wil_blob_wrapper {

From: Dedy Lansky dlansky@codeaurora.org

[ Upstream commit 61e5ec044748486f06dec760a19dce78247b3ad8 ]

When enlarging rx_ring_order module param, wil6210 fails to load because there are not enough Rx buffers. Fix this by enlarging number of Rx buffers at startup, if needed based on rx_ring_order.

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/main.c | 2 +- drivers/net/wireless/ath/wil6210/txrx.c | 4 ++-- drivers/net/wireless/ath/wil6210/txrx_edma.c | 11 ++++++++--- drivers/net/wireless/ath/wil6210/wil6210.h | 2 +- 4 files changed, 12 insertions(+), 7 deletions(-)

diff --git a/drivers/net/wireless/ath/wil6210/main.c b/drivers/net/wireless/ath/wil6210/main.c index 28d2bfd0fde79..fe91db3478dc8 100644 --- a/drivers/net/wireless/ath/wil6210/main.c +++ b/drivers/net/wireless/ath/wil6210/main.c @@ -1687,7 +1687,7 @@ int __wil_up(struct wil6210_priv *wil) return rc;

/* Rx RING. After MAC and beacon */ - rc = wil->txrx_ops.rx_init(wil, 1 << rx_ring_order); + rc = wil->txrx_ops.rx_init(wil, rx_ring_order); if (rc) return rc;

diff --git a/drivers/net/wireless/ath/wil6210/txrx.c b/drivers/net/wireless/ath/wil6210/txrx.c index 73cdf54521f9b..236dcb6f5e84d 100644 --- a/drivers/net/wireless/ath/wil6210/txrx.c +++ b/drivers/net/wireless/ath/wil6210/txrx.c @@ -881,7 +881,7 @@ static void wil_rx_buf_len_init(struct wil6210_priv *wil) } }

-static int wil_rx_init(struct wil6210_priv *wil, u16 size) +static int wil_rx_init(struct wil6210_priv *wil, uint order) { struct wil_ring *vring = &wil->ring_rx; int rc; @@ -895,7 +895,7 @@ static int wil_rx_init(struct wil6210_priv *wil, u16 size)

wil_rx_buf_len_init(wil);

- vring->size = size; + vring->size = 1 << order; vring->is_rx = true; rc = wil_vring_alloc(wil, vring); if (rc) diff --git a/drivers/net/wireless/ath/wil6210/txrx_edma.c b/drivers/net/wireless/ath/wil6210/txrx_edma.c index 03d0e6c550b98..fe666a3583c10 100644 --- a/drivers/net/wireless/ath/wil6210/txrx_edma.c +++ b/drivers/net/wireless/ath/wil6210/txrx_edma.c @@ -593,9 +593,9 @@ static void wil_rx_buf_len_init_edma(struct wil6210_priv *wil) WIL_MAX_ETH_MTU : WIL_EDMA_RX_BUF_LEN_DEFAULT; }

-static int wil_rx_init_edma(struct wil6210_priv *wil, u16 desc_ring_size) +static int wil_rx_init_edma(struct wil6210_priv *wil, uint desc_ring_order) { - u16 status_ring_size; + u16 status_ring_size, desc_ring_size = 1 << desc_ring_order; struct wil_ring *ring = &wil->ring_rx; int rc; size_t elem_size = wil->use_compressed_rx_status ? @@ -610,7 +610,12 @@ static int wil_rx_init_edma(struct wil6210_priv *wil, u16 desc_ring_size) "compressed RX status cannot be used with SW reorder\n"); return -EINVAL; } - + if (wil->rx_status_ring_order <= desc_ring_order) + /* make sure sring is larger than desc ring */ + wil->rx_status_ring_order = desc_ring_order + 1; + if (wil->rx_buff_id_count <= desc_ring_size) + /* make sure we will not run out of buff_ids */ + wil->rx_buff_id_count = desc_ring_size + 512; if (wil->rx_status_ring_order < WIL_SRING_SIZE_ORDER_MIN || wil->rx_status_ring_order > WIL_SRING_SIZE_ORDER_MAX) wil->rx_status_ring_order = WIL_RX_SRING_SIZE_ORDER_DEFAULT; diff --git a/drivers/net/wireless/ath/wil6210/wil6210.h b/drivers/net/wireless/ath/wil6210/wil6210.h index 6a05f59ee58e9..bc89044d0b66e 100644 --- a/drivers/net/wireless/ath/wil6210/wil6210.h +++ b/drivers/net/wireless/ath/wil6210/wil6210.h @@ -602,7 +602,7 @@ struct wil_txrx_ops { struct wil_ring *ring, struct sk_buff *skb); irqreturn_t (*irq_tx)(int irq, void *cookie); /* RX ops */ - int (*rx_init)(struct wil6210_priv *wil, u16 ring_size); + int (*rx_init)(struct wil6210_priv *wil, uint ring_order); void (*rx_fini)(struct wil6210_priv *wil); int (*wmi_addba_rx_resp)(struct wil6210_priv *wil, u8 mid, u8 cid, u8 tid, u8 token, u16 status, bool amsdu,

From: Karthick Gopalasubramanian kargop@codeaurora.org

[ Upstream commit 32dcfe8316cdbd885542967c0c85f5b9de78874b ]

Reset file is not used and may cause race conditions with operational driver if used.

Signed-off-by: Karthick Gopalasubramanian kargop@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 | 27 ---------------------- 1 file changed, 27 deletions(-)

diff --git a/drivers/net/wireless/ath/wil6210/debugfs.c b/drivers/net/wireless/ath/wil6210/debugfs.c index acd95ca0430b9..55a809cb31054 100644 --- a/drivers/net/wireless/ath/wil6210/debugfs.c +++ b/drivers/net/wireless/ath/wil6210/debugfs.c @@ -730,32 +730,6 @@ struct dentry *wil_debugfs_create_ioblob(const char *name, return debugfs_create_file(name, mode, parent, wil_blob, &fops_ioblob); }

-/*---reset---*/ -static ssize_t wil_write_file_reset(struct file *file, const char __user *buf, - size_t len, loff_t *ppos) -{ - struct wil6210_priv *wil = file->private_data; - struct net_device *ndev = wil->main_ndev; - - /** - * BUG: - * this code does NOT sync device state with the rest of system - * use with care, debug only!!! - */ - rtnl_lock(); - dev_close(ndev); - ndev->flags &= ~IFF_UP; - rtnl_unlock(); - wil_reset(wil, true); - - return len; -} - -static const struct file_operations fops_reset = { - .write = wil_write_file_reset, - .open = simple_open, -}; - /*---write channel 1..4 to rxon for it, 0 to rxoff---*/ static ssize_t wil_write_file_rxon(struct file *file, const char __user *buf, size_t len, loff_t *ppos) @@ -2461,7 +2435,6 @@ static const struct { {"desc", 0444, &fops_txdesc}, {"bf", 0444, &fops_bf}, {"mem_val", 0644, &fops_memread}, - {"reset", 0244, &fops_reset}, {"rxon", 0244, &fops_rxon}, {"tx_mgmt", 0244, &fops_txmgmt}, {"wmi_send", 0244, &fops_wmi},

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 958d6ba9ee2d1..be65161f97531 100644 --- a/mm/vmalloc.c +++ b/mm/vmalloc.c @@ -1668,7 +1668,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|highmem_mask, @@ -1676,13 +1675,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 ba79956e848d5..20f178c24e9d1 100644 --- a/include/linux/list_sort.h +++ b/include/linux/list_sort.h @@ -6,6 +6,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 85759928215b4..ba9431bcac0bc 100644 --- a/lib/list_sort.c +++ b/lib/list_sort.c @@ -7,33 +7,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; }

/* @@ -43,44 +51,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; } @@ -91,55 +107,80 @@ 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. * - * 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. + * 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). + * + * 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; + /* 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() */ } - 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; - } - part[lev] = cur; + /* And place the result at the head of "pending" */ + cur->prev = pending; + pending = cur; + count++; + } while (list->next); + + /* Now merge together last element with all pending lists */ + while (pending->prev) { + list = merge(priv, (cmp_func)cmp, pending, list); + pending = pending->prev; } - - for (lev = 0; lev < max_lev; lev++) - if (part[lev]) - list = merge(priv, cmp, part[lev], list); - - merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); + /* The final merge, rebuilding prev links */ + merge_final(priv, (cmp_func)cmp, head, pending, list); } EXPORT_SYMBOL(list_sort);