From patchwork Wed Mar 21 16:32:07 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andre Przywara X-Patchwork-Id: 132230 Delivered-To: patch@linaro.org Received: by 10.46.84.29 with SMTP id i29csp2356290ljb; Wed, 21 Mar 2018 09:35:11 -0700 (PDT) X-Google-Smtp-Source: AIpwx489zO5UHmCrcWFnoKrIjxuWP+uv4izHXdIK7YfTvD9/kHnSd0p8+9uZpgGyGIr6Kvz6bZPs X-Received: by 2002:a24:8908:: with SMTP id s8-v6mr4925110itd.24.1521650111320; Wed, 21 Mar 2018 09:35:11 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1521650111; cv=none; d=google.com; s=arc-20160816; b=D1DldH1Him1yUxkMvMxN2uRHPkPxBUV430ptL+RVa96DVZnn0IGkWbK0kpcXjQSuw1 K3yIxPzWCZWzXCv2E91XVztjwlBQUxkNmeV9dFxG3+qCzqy1LwqpEmI5VK3lcdQ2JmSE th/+/RMrMow7H7JUUTKgwJya888lqIfESwf2gGyRnB+mimksjTuswDhJLHCIpmzN3fqx 8aR6j62FnuDnhqy4O3jbmOfMh/N5k6USsXcXIz6M8QlzDQEaAU7au1PIUiKYixlMLtWT Qh8Y+3KF81vCXyddSjoT2El0h0ZTAA87MrI1zp99caeztwwap0ynwNGxxRYRBNTCmY+f jqCw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:content-transfer-encoding:mime-version:cc :list-subscribe:list-help:list-post:list-unsubscribe:list-id :precedence:subject:references:in-reply-to:message-id:date:to:from :dkim-signature:arc-authentication-results; bh=87WEp0XViUHTWQS4BCe8uBtAdHbzYm4uYZXyb+2gMgI=; b=hXNMAgYh+bCxCWMjAXSkl1sXEj2eDKz36ajhOYyypr1MD17GW9EPwdAvSdnd04XEf/ 1iOyfrK/XZYAukZKDAjEnW0oETQ25KYXAb7yPXTC3d45rlC+Req9SsPwStfBSTagquwN Io9KOOgahbU7x+IeLdkvdFJdKVAIo4YEF3xqHJmvXshuoKyIbkS300BvmR0Vd6WMOz+e 4BEgdFc75TtLhDjGud9yC2pCPOH5LL6emkQI08TmIBUER2C2LKUppfP+IJETY9STLWDh kpA1qAqdkRPwpHoRTJjlC2Ixffk9DcWhd59wPxCwugrIAAYHo0Esb4xA0xudalcX4Ahj r9zg== ARC-Authentication-Results: i=1; mx.google.com; dkim=neutral (body hash did not verify) header.i=@linaro.org header.s=google header.b=IsQxe4tp; spf=pass (google.com: best guess record for domain of xen-devel-bounces@lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from lists.xenproject.org (lists.xenproject.org. [192.237.175.120]) by mx.google.com with ESMTPS id c139-v6si3301817itc.4.2018.03.21.09.35.11 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Wed, 21 Mar 2018 09:35:11 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of xen-devel-bounces@lists.xenproject.org designates 192.237.175.120 as permitted sender) client-ip=192.237.175.120; Authentication-Results: mx.google.com; dkim=neutral (body hash did not verify) header.i=@linaro.org header.s=google header.b=IsQxe4tp; spf=pass (google.com: best guess record for domain of xen-devel-bounces@lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.89) (envelope-from ) id 1eygfg-0002CQ-0V; Wed, 21 Mar 2018 16:33:04 +0000 Received: from us1-rack-dfw2.inumbo.com ([104.130.134.6]) by lists.xenproject.org with esmtp (Exim 4.89) (envelope-from ) id 1eygfe-0002AF-N7 for xen-devel@lists.xenproject.org; Wed, 21 Mar 2018 16:33:02 +0000 X-Inumbo-ID: 7c63da67-2d25-11e8-9728-bc764e045a96 Received: from mail-wm0-x241.google.com (unknown [2a00:1450:400c:c09::241]) by us1-rack-dfw2.inumbo.com (Halon) with ESMTPS id 7c63da67-2d25-11e8-9728-bc764e045a96; Wed, 21 Mar 2018 17:32:46 +0100 (CET) Received: by mail-wm0-x241.google.com with SMTP id h76so10900039wme.4 for ; Wed, 21 Mar 2018 09:33:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=i81ZraMvWHd4ffPommRZ3NEnVEz27uDarYL8wdxr+74=; b=IsQxe4tpdlVhVcRuWyK+HfbYi2MyPvfeR89Iq2STcJe3wKRQo8+f8AIL3kTz03vB+D /qLhz45KNpng7SkB7N3JdwXcOsTaYydvxklMfQ4VppKn6OqZs3qwJJmBXyb4zDfX1kIz 6gm/cCzaWg/gA/TJLf6cjVr5Yym3FmR8VNkOA= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=i81ZraMvWHd4ffPommRZ3NEnVEz27uDarYL8wdxr+74=; b=SYIiURjDiLvMd0+PkKnk0+1i+gNYcXTR20iU+CSpMA7PwMDT9YIvt3ERQSvienKmC0 Zupqrknw1de9uzjtXUe2o79aUlmWIXCZ3igq52Z89hB1ttMLM+cz8/kIg7uS8unfUxwY mKH0ih6cK7b/ErAfUZMu0Zi0KREqlWD6A49mFFjt3bR3CEbzECSdiRcC9xpMZBvVFlQQ VIC1i8cWesYYMXAfX6PF1ch7ukI4liQkIPIUoSoSfh5Z2COEj2Mf29oqfONSybOpYuur Y8HFbfqTMMACqnGpkePP38VMFpSyeEl1HrzAwwhGujwv4sy5Rm3r96NXEY4ky/ssOSiM Bk/g== X-Gm-Message-State: AElRT7ErSrpYlsB7l6fLbVXooQ4iX+E/oGCAqWPA37idCXbcMw1xnvEB B7srd3h5iL4z3M8CENpM1twhIg== X-Received: by 10.28.152.6 with SMTP id a6mr3130761wme.119.1521649979973; Wed, 21 Mar 2018 09:32:59 -0700 (PDT) Received: from e104803-lin.lan (mail.andrep.de. [217.160.17.100]) by smtp.gmail.com with ESMTPSA id n64sm4423724wmd.11.2018.03.21.09.32.58 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 21 Mar 2018 09:32:59 -0700 (PDT) From: Andre Przywara To: Julien Grall , Stefano Stabellini Date: Wed, 21 Mar 2018 16:32:07 +0000 Message-Id: <20180321163235.12529-12-andre.przywara@linaro.org> X-Mailer: git-send-email 2.14.1 In-Reply-To: <20180321163235.12529-1-andre.przywara@linaro.org> References: <20180321163235.12529-1-andre.przywara@linaro.org> Subject: [Xen-devel] [PATCH v3 11/39] Add list_sort() routine from Linux X-BeenThere: xen-devel@lists.xenproject.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Cc: Wei Liu , George Dunlap , Andrew Cooper , Ian Jackson , Andre Przywara , Tim Deegan , Jan Beulich , xen-devel@lists.xenproject.org MIME-Version: 1.0 Errors-To: xen-devel-bounces@lists.xenproject.org Sender: "Xen-devel" This pulls in Linux' list_sort.c, which is a merge sort implementation for linked lists. Apart from adding a full featured license header and adjusting the #include file, nothing has been changed in this code. Define a promptless Kconfig which configurations can select when they need this code and add it to the Makefile. This is from Linux' lib/list_sort.c, as of commit e327fd7c8667 ("lib: add module support to linked list sorting tests"). Signed-off-by: Andre Przywara Acked-by: Julien Grall --- Changelog v2 ... v3: - introduce promptless Kconfig - add Makefile line - note Linux commit ID xen/common/Kconfig | 3 + xen/common/Makefile | 1 + xen/common/list_sort.c | 157 ++++++++++++++++++++++++++++++++++++++++++++ xen/include/xen/list_sort.h | 11 ++++ 4 files changed, 172 insertions(+) create mode 100644 xen/common/list_sort.c create mode 100644 xen/include/xen/list_sort.h diff --git a/xen/common/Kconfig b/xen/common/Kconfig index 68abf7a5e5..986f6c4149 100644 --- a/xen/common/Kconfig +++ b/xen/common/Kconfig @@ -44,6 +44,9 @@ config HAS_GDBSX config HAS_IOPORTS bool +config NEEDS_LIST_SORT + bool + config HAS_BUILD_ID string option env="XEN_HAS_BUILD_ID" diff --git a/xen/common/Makefile b/xen/common/Makefile index 3a349f478b..24d4752ccc 100644 --- a/xen/common/Makefile +++ b/xen/common/Makefile @@ -19,6 +19,7 @@ obj-y += keyhandler.o obj-$(CONFIG_KEXEC) += kexec.o obj-$(CONFIG_KEXEC) += kimage.o obj-y += lib.o +obj-$(CONFIG_NEEDS_LIST_SORT) += list_sort.o obj-$(CONFIG_LIVEPATCH) += livepatch.o livepatch_elf.o obj-y += lzo.o obj-$(CONFIG_HAS_MEM_ACCESS) += mem_access.o diff --git a/xen/common/list_sort.c b/xen/common/list_sort.c new file mode 100644 index 0000000000..af2b2f6519 --- /dev/null +++ b/xen/common/list_sort.c @@ -0,0 +1,157 @@ +/* + * list_sort.c: merge sort implementation for linked lists + * Copied from the Linux kernel (lib/list_sort.c) + * + * This program is free software; you can redistribute it and/or modify it + * under the terms and conditions of the GNU General Public License, + * version 2, as published by the Free Software Foundation. + * + * This program is distributed in the hope it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along with + * this program; If not, see . + */ + +#include +#include + +#define MAX_LIST_LENGTH_BITS 20 + +/* + * 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), + struct list_head *a, struct list_head *b) +{ + struct list_head head, *tail = &head; + + while (a && b) { + /* if equal, take 'a' -- important for sort stability */ + if ((*cmp)(priv, a, b) <= 0) { + tail->next = a; + a = a->next; + } else { + tail->next = b; + b = b->next; + } + tail = tail->next; + } + tail->next = a?:b; + return head.next; +} + +/* + * Combine final list merge with restoration of standard doubly-linked + * list structure. This approach duplicates code from merge(), but + * runs faster than the tidier alternatives of either a separate final + * 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) +{ + struct list_head *tail = head; + u8 count = 0; + + while (a && b) { + /* if equal, take 'a' -- important for sort stability */ + if ((*cmp)(priv, a, b) <= 0) { + tail->next = a; + a->prev = tail; + a = a->next; + } else { + tail->next = b; + b->prev = tail; + b = b->next; + } + tail = tail->next; + } + tail->next = a ? : b; + + do { + /* + * In worst cases 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); + + tail->next = head; + head->prev = tail; +} + +/** + * list_sort - sort a list + * @priv: private data, opaque to list_sort(), passed to @cmp + * @head: the list to sort + * @cmp: the elements comparison function + * + * This function implements "merge sort", which has O(nlog(n)) + * complexity. + * + * 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. + */ +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; + + if (list_empty(head)) + return; + + memset(part, 0, sizeof(part)); + + head->prev->next = NULL; + list = head->next; + + while (list) { + struct list_head *cur = list; + 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)) { + dprintk(XENLOG_DEBUG, + "list too long for efficiency\n"); + lev--; + } + max_lev = lev; + } + part[lev] = cur; + } + + 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); +} +EXPORT_SYMBOL(list_sort); diff --git a/xen/include/xen/list_sort.h b/xen/include/xen/list_sort.h new file mode 100644 index 0000000000..13ce0a55ec --- /dev/null +++ b/xen/include/xen/list_sort.h @@ -0,0 +1,11 @@ +#ifndef _LINUX_LIST_SORT_H +#define _LINUX_LIST_SORT_H + +#include + +struct list_head; + +void list_sort(void *priv, struct list_head *head, + int (*cmp)(void *priv, struct list_head *a, + struct list_head *b)); +#endif