|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [xen master] lib: move list sorting code
commit 26dfde919cac720c29d076bc8fd38ad0af1b2abb
Author: Jan Beulich <jbeulich@xxxxxxxx>
AuthorDate: Fri Dec 18 13:20:42 2020 +0100
Commit: Jan Beulich <jbeulich@xxxxxxxx>
CommitDate: Fri Dec 18 13:20:42 2020 +0100
lib: move list sorting code
Build the source file always, as by putting it into an archive it still
won't be linked into final binaries when not needed. This way possible
build breakage will be easier to notice, and it's more consistent with
us unconditionally building other library kind of code (e.g. sort() or
bsearch()).
While moving the source file, take the opportunity and drop the
pointless EXPORT_SYMBOL() and an unnecessary #include.
Signed-off-by: Jan Beulich <jbeulich@xxxxxxxx>
Acked-by: Wei Liu <wl@xxxxxxx>
Reviewed-by: Bertrand Marquis <bertrand.marquis@xxxxxxx>
Acked-by: Julien Grall <jgrall@xxxxxxxxxx>
---
xen/arch/arm/Kconfig | 4 +-
xen/common/Kconfig | 3 -
xen/common/Makefile | 1 -
xen/common/list_sort.c | 157 -------------------------------------------------
xen/lib/Makefile | 1 +
xen/lib/list-sort.c | 155 ++++++++++++++++++++++++++++++++++++++++++++++++
6 files changed, 157 insertions(+), 164 deletions(-)
diff --git a/xen/arch/arm/Kconfig b/xen/arch/arm/Kconfig
index 41bde2f401..c3eb13ea73 100644
--- a/xen/arch/arm/Kconfig
+++ b/xen/arch/arm/Kconfig
@@ -56,9 +56,7 @@ config HVM
def_bool y
config NEW_VGIC
- bool
- prompt "Use new VGIC implementation"
- select NEEDS_LIST_SORT
+ bool "Use new VGIC implementation"
---help---
This is an alternative implementation of the ARM GIC interrupt
diff --git a/xen/common/Kconfig b/xen/common/Kconfig
index 3e2cf25088..0661328a99 100644
--- a/xen/common/Kconfig
+++ b/xen/common/Kconfig
@@ -66,9 +66,6 @@ config MEM_ACCESS
config NEEDS_LIBELF
bool
-config NEEDS_LIST_SORT
- bool
-
menu "Speculative hardening"
config SPECULATIVE_HARDEN_ARRAY
diff --git a/xen/common/Makefile b/xen/common/Makefile
index d109f279a4..332e7d667c 100644
--- a/xen/common/Makefile
+++ b/xen/common/Makefile
@@ -21,7 +21,6 @@ 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-$(CONFIG_MEM_ACCESS) += mem_access.o
obj-y += memory.o
diff --git a/xen/common/list_sort.c b/xen/common/list_sort.c
deleted file mode 100644
index af2b2f6519..0000000000
--- a/xen/common/list_sort.c
+++ /dev/null
@@ -1,157 +0,0 @@
-/*
- * 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 <http://www.gnu.org/licenses/>.
- */
-
-#include <xen/lib.h>
-#include <xen/list.h>
-
-#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/lib/Makefile b/xen/lib/Makefile
index b8814361d6..764f3624b5 100644
--- a/xen/lib/Makefile
+++ b/xen/lib/Makefile
@@ -1,3 +1,4 @@
obj-$(CONFIG_X86) += x86/
lib-y += ctype.o
+lib-y += list-sort.o
diff --git a/xen/lib/list-sort.c b/xen/lib/list-sort.c
new file mode 100644
index 0000000000..f8d8bbf281
--- /dev/null
+++ b/xen/lib/list-sort.c
@@ -0,0 +1,155 @@
+/*
+ * 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 <http://www.gnu.org/licenses/>.
+ */
+
+#include <xen/list.h>
+
+#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);
+}
--
generated by git-patchbot for /home/xen/git/xen.git#master
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |