Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/2217959/?format=api
{ "id": 2217959, "url": "http://patchwork.ozlabs.org/api/patches/2217959/?format=api", "web_url": "http://patchwork.ozlabs.org/project/qemu-devel/patch/20260331060731.82641-1-guobin@linux.alibaba.com/", "project": { "id": 14, "url": "http://patchwork.ozlabs.org/api/projects/14/?format=api", "name": "QEMU Development", "link_name": "qemu-devel", "list_id": "qemu-devel.nongnu.org", "list_email": "qemu-devel@nongnu.org", "web_url": "", "scm_url": "", "webscm_url": "", "list_archive_url": "", "list_archive_url_format": "", "commit_url_format": "" }, "msgid": "<20260331060731.82641-1-guobin@linux.alibaba.com>", "list_archive_url": null, "date": "2026-03-31T06:07:31", "name": "memory: Optimize flatview_simplify() to eliminate redundant memmove calls", "commit_ref": null, "pull_url": null, "state": "new", "archived": false, "hash": "b27b8fea78626b4f7fc36f7afb3deb9a0e4a98be", "submitter": { "id": 91693, "url": "http://patchwork.ozlabs.org/api/people/91693/?format=api", "name": "Bin Guo", "email": "guobin@linux.alibaba.com" }, "delegate": null, "mbox": "http://patchwork.ozlabs.org/project/qemu-devel/patch/20260331060731.82641-1-guobin@linux.alibaba.com/mbox/", "series": [ { "id": 498125, "url": "http://patchwork.ozlabs.org/api/series/498125/?format=api", "web_url": "http://patchwork.ozlabs.org/project/qemu-devel/list/?series=498125", "date": "2026-03-31T06:07:31", "name": "memory: Optimize flatview_simplify() to eliminate redundant memmove calls", "version": 1, "mbox": "http://patchwork.ozlabs.org/series/498125/mbox/" } ], "comments": "http://patchwork.ozlabs.org/api/patches/2217959/comments/", "check": "pending", "checks": "http://patchwork.ozlabs.org/api/patches/2217959/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org>", "X-Original-To": "incoming@patchwork.ozlabs.org", "Delivered-To": "patchwork-incoming@legolas.ozlabs.org", "Authentication-Results": [ "legolas.ozlabs.org;\n\tdkim=pass (1024-bit key;\n unprotected) header.d=linux.alibaba.com header.i=@linux.alibaba.com\n header.a=rsa-sha256 header.s=default header.b=i2yoM02u;\n\tdkim-atps=neutral", "legolas.ozlabs.org;\n spf=pass (sender SPF authorized) smtp.mailfrom=nongnu.org\n (client-ip=209.51.188.17; helo=lists.gnu.org;\n envelope-from=qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org;\n receiver=patchwork.ozlabs.org)" ], "Received": [ "from lists.gnu.org (lists.gnu.org [209.51.188.17])\n\t(using TLSv1.2 with cipher ECDHE-ECDSA-AES256-GCM-SHA384 (256/256 bits))\n\t(No client certificate requested)\n\tby legolas.ozlabs.org (Postfix) with ESMTPS id 4flHqs0gWjz1yGH\n\tfor <incoming@patchwork.ozlabs.org>; Tue, 31 Mar 2026 17:13:45 +1100 (AEDT)", "from localhost ([::1] helo=lists1p.gnu.org)\n\tby lists.gnu.org with esmtp (Exim 4.90_1)\n\t(envelope-from <qemu-devel-bounces@nongnu.org>)\n\tid 1w7SLh-0003iR-6y; Tue, 31 Mar 2026 02:13:13 -0400", "from eggs.gnu.org ([2001:470:142:3::10])\n by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)\n (Exim 4.90_1) (envelope-from <guobin@linux.alibaba.com>)\n id 1w7SLb-0003gP-AA\n for qemu-devel@nongnu.org; Tue, 31 Mar 2026 02:13:07 -0400", "from out30-118.freemail.mail.aliyun.com ([115.124.30.118])\n by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)\n (Exim 4.90_1) (envelope-from <guobin@linux.alibaba.com>)\n id 1w7SLX-00032T-2r\n for qemu-devel@nongnu.org; Tue, 31 Mar 2026 02:13:05 -0400", "from localhost(mailfrom:guobin@linux.alibaba.com\n fp:SMTPD_---0X03E62i_1774937251 cluster:ay36) by smtp.aliyun-inc.com;\n Tue, 31 Mar 2026 14:07:40 +0800" ], "DKIM-Signature": "v=1; a=rsa-sha256; c=relaxed/relaxed;\n d=linux.alibaba.com; s=default;\n t=1774937569; h=From:To:Subject:Date:Message-ID:MIME-Version:Content-Type;\n bh=k/Pw/7AwyXnbAwlCyIMzZnhcQ+HaOc0N3Dc1HQuWsgo=;\n b=i2yoM02uJSQKXvXuxDQUSGbaV4U1/j2rjjLTlSkILYXWK2qkxEyjJ7gqkCKRf9Z6FcZIH/l7R8MOBpEJN7tplaFQMsy9R2GTurpNZkugosdkrimzzADBBWCQWKEdkwaVwqxTNmANKA39d0RfFB4uYGNRa7Nuu5HbEPn1KLmUBk8=", "X-Alimail-AntiSpam": "AC=PASS; BC=-1|-1; BR=01201311R671e4; CH=green;\n DM=||false|;\n DS=||; FP=0|-1|-1|-1|0|-1|-1|-1; HT=maildocker-contentspam011083073210;\n MF=guobin@linux.alibaba.com; NM=1; PH=DS; RN=4; SR=0;\n TI=SMTPD_---0X03E62i_1774937251;", "From": "Bin Guo <guobin@linux.alibaba.com>", "To": "qemu-devel@nongnu.org", "Cc": "peterx@redhat.com,\n\trichard.henderson@linaro.org,\n\tphilmd@linaro.org", "Subject": "[PATCH] memory: Optimize flatview_simplify() to eliminate redundant\n memmove calls", "Date": "Tue, 31 Mar 2026 14:07:31 +0800", "Message-ID": "<20260331060731.82641-1-guobin@linux.alibaba.com>", "X-Mailer": "git-send-email 2.50.1", "MIME-Version": "1.0", "Content-Type": "text/plain; charset=UTF-8", "Content-Transfer-Encoding": "8bit", "Received-SPF": "pass client-ip=115.124.30.118;\n envelope-from=guobin@linux.alibaba.com;\n helo=out30-118.freemail.mail.aliyun.com", "X-Spam_score_int": "-154", "X-Spam_score": "-15.5", "X-Spam_bar": "---------------", "X-Spam_report": "(-15.5 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1,\n DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, ENV_AND_HDR_SPF_MATCH=-0.5,\n RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_VALIDITY_CERTIFIED_BLOCKED=1,\n RCVD_IN_VALIDITY_RPBL_BLOCKED=1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001,\n UNPARSEABLE_RELAY=0.001, USER_IN_DEF_DKIM_WL=-7.5,\n USER_IN_DEF_SPF_WL=-7.5 autolearn=no autolearn_force=no", "X-Spam_action": "no action", "X-BeenThere": "qemu-devel@nongnu.org", "X-Mailman-Version": "2.1.29", "Precedence": "list", "List-Id": "qemu development <qemu-devel.nongnu.org>", "List-Unsubscribe": "<https://lists.nongnu.org/mailman/options/qemu-devel>,\n <mailto:qemu-devel-request@nongnu.org?subject=unsubscribe>", "List-Archive": "<https://lists.nongnu.org/archive/html/qemu-devel>", "List-Post": "<mailto:qemu-devel@nongnu.org>", "List-Help": "<mailto:qemu-devel-request@nongnu.org?subject=help>", "List-Subscribe": "<https://lists.nongnu.org/mailman/listinfo/qemu-devel>,\n <mailto:qemu-devel-request@nongnu.org?subject=subscribe>", "Errors-To": "qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org", "Sender": "qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org" }, "content": "The original flatview_simplify() implementation uses memmove() to shift\narray elements after each merge operation, resulting in O(n²) time\ncomplexity in the worst case. This is inefficient for VMs with large\nmemory topologies containing hundreds of MemoryRegions.\n\nReplace the memmove-based approach with a two-pointer in-place compression\nalgorithm that achieves O(n) time complexity. The new algorithm uses a\nwrite pointer i and a read pointer j, where i ≤ j is always maintained.\nThis invariant ensures we never overwrite unprocessed data, making memmove\nunnecessary.\n\nSigned-off-by: Bin Guo <guobin@linux.alibaba.com>\n---\n system/memory.c | 27 ++++++++++++++-------------\n 1 file changed, 14 insertions(+), 13 deletions(-)", "diff": "diff --git a/system/memory.c b/system/memory.c\nindex 56f3225b21..0ff066c348 100644\n--- a/system/memory.c\n+++ b/system/memory.c\n@@ -336,24 +336,25 @@ static bool can_merge(FlatRange *r1, FlatRange *r2)\n /* Attempt to simplify a view by merging adjacent ranges */\n static void flatview_simplify(FlatView *view)\n {\n- unsigned i, j, k;\n+ unsigned i, j;\n+\n+ if (view->nr <= 1) {\n+ return;\n+ }\n \n i = 0;\n- while (i < view->nr) {\n- j = i + 1;\n- while (j < view->nr\n- && can_merge(&view->ranges[j-1], &view->ranges[j])) {\n+ for (j = 1; j < view->nr; j++) {\n+ if (can_merge(&view->ranges[i], &view->ranges[j])) {\n int128_addto(&view->ranges[i].addr.size, view->ranges[j].addr.size);\n- ++j;\n- }\n- ++i;\n- for (k = i; k < j; k++) {\n- memory_region_unref(view->ranges[k].mr);\n+ memory_region_unref(view->ranges[j].mr);\n+ } else {\n+ i++;\n+ if (i != j) {\n+ view->ranges[i] = view->ranges[j];\n+ }\n }\n- memmove(&view->ranges[i], &view->ranges[j],\n- (view->nr - j) * sizeof(view->ranges[j]));\n- view->nr -= j - i;\n }\n+ view->nr = i + 1;\n }\n \n static void adjust_endianness(MemoryRegion *mr, uint64_t *data, MemOp op)\n", "prefixes": [] }