[PATCH v2 0/8] xen: beginnings of moving library-like code into an archive

[PATCH v2 0/8] xen: beginnings of moving library-like code into an archive

[Jan Beulich]

In a few cases we link in library-like functions when they're not
actually needed. While we could use Kconfig options for each one
of them, I think the better approach for such generic code is to
build it always (thus making sure a build issue can't be introduced
for these in any however exotic configuration) and then put it into
an archive, for the linker to pick up as needed. The series here
presents a first few tiny steps towards such a goal.

Not that we can't use thin archives yet, due to our tool chain
(binutils) baseline being too low.

The first patch actually isn't directly related to the rest of the
series, except that - to avoid undue redundancy - I ran into the
issue addressed there while (originally) making patch 3 convert to
using $(call if_changed,ld) "on the fly". IOW it's a full
(contextual and functional) prereq to the series.

Further almost immediate steps I'd like to take if the approach
meets no opposition are
- split and move the rest of common/lib.c,
- split and move common/string.c, dropping the need for all the
  __HAVE_ARCH_* (implying possible per-arch archives then need to
  be specified ahead of lib/lib.a on the linker command lines),
- move common/libelf/ and common/libfdt/.

It's really only patch 7 which has changed in v7, but since no
other feedback arrived which would require adjustments, I'm
resending with just this one change.

1: lib: split _ctype[] into its own object, under lib/
2: lib: collect library files in an archive
3: lib: move list sorting code
4: lib: move parse_size_and_unit()
5: lib: move init_constructors()
6: lib: move rbtree code
7: lib: move bsearch code
8: lib: move sort code

Jan

[PATCH v2 1/8] lib: split _ctype[] into its own object, under lib/

[Jan Beulich]

This is, besides for tidying, in preparation of then starting to use an
archive rather than an object file for generic library code which
arch-es (or even specific configurations within a single arch) may or
may not need.

Signed-off-by: Jan Beulich <jbeulich@suse.com>
---
 xen/Makefile     |  3 ++-
 xen/Rules.mk     |  2 +-
 xen/common/lib.c | 29 -----------------------------
 xen/lib/Makefile |  1 +
 xen/lib/ctype.c  | 38 ++++++++++++++++++++++++++++++++++++++
 5 files changed, 42 insertions(+), 31 deletions(-)
 create mode 100644 xen/lib/ctype.c

diff --git a/xen/Makefile b/xen/Makefile
index bf0c804d4352..73bdc326c549 100644
--- a/xen/Makefile
+++ b/xen/Makefile
@@ -331,6 +331,7 @@ _clean: delete-unfresh-files
 	$(MAKE) $(clean) include
 	$(MAKE) $(clean) common
 	$(MAKE) $(clean) drivers
+	$(MAKE) $(clean) lib
 	$(MAKE) $(clean) xsm
 	$(MAKE) $(clean) crypto
 	$(MAKE) $(clean) arch/arm
@@ -414,7 +415,7 @@ include/asm-$(TARGET_ARCH)/asm-offsets.h: arch/$(TARGET_ARCH)/asm-offsets.s
 	  echo ""; \
 	  echo "#endif") <$< >$@
 
-SUBDIRS = xsm arch/$(TARGET_ARCH) common drivers test
+SUBDIRS = xsm arch/$(TARGET_ARCH) common drivers lib test
 define all_sources
     ( find include/asm-$(TARGET_ARCH) -name '*.h' -print; \
       find include -name 'asm-*' -prune -o -name '*.h' -print; \
diff --git a/xen/Rules.mk b/xen/Rules.mk
index 891c94e6ad00..333e19bec343 100644
--- a/xen/Rules.mk
+++ b/xen/Rules.mk
@@ -36,7 +36,7 @@ TARGET := $(BASEDIR)/xen
 # Note that link order matters!
 ALL_OBJS-y               += $(BASEDIR)/common/built_in.o
 ALL_OBJS-y               += $(BASEDIR)/drivers/built_in.o
-ALL_OBJS-$(CONFIG_X86)   += $(BASEDIR)/lib/built_in.o
+ALL_OBJS-y               += $(BASEDIR)/lib/built_in.o
 ALL_OBJS-y               += $(BASEDIR)/xsm/built_in.o
 ALL_OBJS-y               += $(BASEDIR)/arch/$(TARGET_ARCH)/built_in.o
 ALL_OBJS-$(CONFIG_CRYPTO)   += $(BASEDIR)/crypto/built_in.o
diff --git a/xen/common/lib.c b/xen/common/lib.c
index b2b799da44c5..a224efa8f6e8 100644
--- a/xen/common/lib.c
+++ b/xen/common/lib.c
@@ -1,37 +1,8 @@
-
-#include <xen/ctype.h>
 #include <xen/lib.h>
 #include <xen/types.h>
 #include <xen/init.h>
 #include <asm/byteorder.h>
 
-/* for ctype.h */
-const unsigned char _ctype[] = {
-    _C,_C,_C,_C,_C,_C,_C,_C,                        /* 0-7 */
-    _C,_C|_S,_C|_S,_C|_S,_C|_S,_C|_S,_C,_C,         /* 8-15 */
-    _C,_C,_C,_C,_C,_C,_C,_C,                        /* 16-23 */
-    _C,_C,_C,_C,_C,_C,_C,_C,                        /* 24-31 */
-    _S|_SP,_P,_P,_P,_P,_P,_P,_P,                    /* 32-39 */
-    _P,_P,_P,_P,_P,_P,_P,_P,                        /* 40-47 */
-    _D,_D,_D,_D,_D,_D,_D,_D,                        /* 48-55 */
-    _D,_D,_P,_P,_P,_P,_P,_P,                        /* 56-63 */
-    _P,_U|_X,_U|_X,_U|_X,_U|_X,_U|_X,_U|_X,_U,      /* 64-71 */
-    _U,_U,_U,_U,_U,_U,_U,_U,                        /* 72-79 */
-    _U,_U,_U,_U,_U,_U,_U,_U,                        /* 80-87 */
-    _U,_U,_U,_P,_P,_P,_P,_P,                        /* 88-95 */
-    _P,_L|_X,_L|_X,_L|_X,_L|_X,_L|_X,_L|_X,_L,      /* 96-103 */
-    _L,_L,_L,_L,_L,_L,_L,_L,                        /* 104-111 */
-    _L,_L,_L,_L,_L,_L,_L,_L,                        /* 112-119 */
-    _L,_L,_L,_P,_P,_P,_P,_C,                        /* 120-127 */
-    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,                /* 128-143 */
-    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,                /* 144-159 */
-    _S|_SP,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,   /* 160-175 */
-    _P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,       /* 176-191 */
-    _U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,       /* 192-207 */
-    _U,_U,_U,_U,_U,_U,_U,_P,_U,_U,_U,_U,_U,_U,_U,_L,       /* 208-223 */
-    _L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,       /* 224-239 */
-    _L,_L,_L,_L,_L,_L,_L,_P,_L,_L,_L,_L,_L,_L,_L,_L};      /* 240-255 */
-
 /*
  * A couple of 64 bit operations ported from FreeBSD.
  * The code within the '#if BITS_PER_LONG == 32' block below, and no other
diff --git a/xen/lib/Makefile b/xen/lib/Makefile
index 7019ca00e8fd..53b1da025e0d 100644
--- a/xen/lib/Makefile
+++ b/xen/lib/Makefile
@@ -1 +1,2 @@
+obj-y += ctype.o
 obj-$(CONFIG_X86) += x86/
diff --git a/xen/lib/ctype.c b/xen/lib/ctype.c
new file mode 100644
index 000000000000..7b233a335fdf
--- /dev/null
+++ b/xen/lib/ctype.c
@@ -0,0 +1,38 @@
+#include <xen/ctype.h>
+
+/* for ctype.h */
+const unsigned char _ctype[] = {
+    _C,_C,_C,_C,_C,_C,_C,_C,                        /* 0-7 */
+    _C,_C|_S,_C|_S,_C|_S,_C|_S,_C|_S,_C,_C,         /* 8-15 */
+    _C,_C,_C,_C,_C,_C,_C,_C,                        /* 16-23 */
+    _C,_C,_C,_C,_C,_C,_C,_C,                        /* 24-31 */
+    _S|_SP,_P,_P,_P,_P,_P,_P,_P,                    /* 32-39 */
+    _P,_P,_P,_P,_P,_P,_P,_P,                        /* 40-47 */
+    _D,_D,_D,_D,_D,_D,_D,_D,                        /* 48-55 */
+    _D,_D,_P,_P,_P,_P,_P,_P,                        /* 56-63 */
+    _P,_U|_X,_U|_X,_U|_X,_U|_X,_U|_X,_U|_X,_U,      /* 64-71 */
+    _U,_U,_U,_U,_U,_U,_U,_U,                        /* 72-79 */
+    _U,_U,_U,_U,_U,_U,_U,_U,                        /* 80-87 */
+    _U,_U,_U,_P,_P,_P,_P,_P,                        /* 88-95 */
+    _P,_L|_X,_L|_X,_L|_X,_L|_X,_L|_X,_L|_X,_L,      /* 96-103 */
+    _L,_L,_L,_L,_L,_L,_L,_L,                        /* 104-111 */
+    _L,_L,_L,_L,_L,_L,_L,_L,                        /* 112-119 */
+    _L,_L,_L,_P,_P,_P,_P,_C,                        /* 120-127 */
+    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,                /* 128-143 */
+    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,                /* 144-159 */
+    _S|_SP,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,   /* 160-175 */
+    _P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,       /* 176-191 */
+    _U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,       /* 192-207 */
+    _U,_U,_U,_U,_U,_U,_U,_P,_U,_U,_U,_U,_U,_U,_U,_L,       /* 208-223 */
+    _L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,       /* 224-239 */
+    _L,_L,_L,_L,_L,_L,_L,_P,_L,_L,_L,_L,_L,_L,_L,_L};      /* 240-255 */
+
+/*
+ * Local variables:
+ * mode: C
+ * c-file-style: "BSD"
+ * c-basic-offset: 4
+ * tab-width: 4
+ * indent-tabs-mode: nil
+ * End:
+ */
-- 
2.22.0

[PATCH v2 2/8] lib: collect library files in an archive

[Jan Beulich]

In order to (subsequently) drop odd things like CONFIG_NEEDS_LIST_SORT
just to avoid bloating binaries when only some arch-es and/or
configurations need generic library routines, combine objects under lib/
into an archive, which the linker then can pick the necessary objects
out of.

Note that we can't use thin archives just yet, until we've raised the
minimum required binutils version suitably.

Signed-off-by: Jan Beulich <jbeulich@suse.com>
---
 xen/Rules.mk          | 33 +++++++++++++++++++++++++++------
 xen/arch/arm/Makefile |  6 +++---
 xen/arch/x86/Makefile |  8 ++++----
 xen/lib/Makefile      |  3 ++-
 4 files changed, 36 insertions(+), 14 deletions(-)

diff --git a/xen/Rules.mk b/xen/Rules.mk
index 333e19bec343..e59c7f213f77 100644
--- a/xen/Rules.mk
+++ b/xen/Rules.mk
@@ -41,12 +41,16 @@ ALL_OBJS-y               += $(BASEDIR)/xsm/built_in.o
 ALL_OBJS-y               += $(BASEDIR)/arch/$(TARGET_ARCH)/built_in.o
 ALL_OBJS-$(CONFIG_CRYPTO)   += $(BASEDIR)/crypto/built_in.o
 
+ALL_LIBS-y               := $(BASEDIR)/lib/lib.a
+
 # Initialise some variables
+lib-y :=
 targets :=
 CFLAGS-y :=
 AFLAGS-y :=
 
 ALL_OBJS := $(ALL_OBJS-y)
+ALL_LIBS := $(ALL_LIBS-y)
 
 SPECIAL_DATA_SECTIONS := rodata $(foreach a,1 2 4 8 16, \
                                             $(foreach w,1 2 4, \
@@ -60,7 +64,14 @@ include Makefile
 # ---------------------------------------------------------------------------
 
 quiet_cmd_ld = LD      $@
-cmd_ld = $(LD) $(XEN_LDFLAGS) -r -o $@ $(real-prereqs)
+cmd_ld = $(LD) $(XEN_LDFLAGS) -r -o $@ $(filter-out %.a,$(real-prereqs)) \
+               --start-group $(filter %.a,$(real-prereqs)) --end-group
+
+# Archive
+# ---------------------------------------------------------------------------
+
+quiet_cmd_ar = AR      $@
+cmd_ar = rm -f $@; $(AR) cPrs $@ $(real-prereqs)
 
 # Objcopy
 # ---------------------------------------------------------------------------
@@ -86,6 +97,10 @@ obj-y    := $(patsubst %/, %/built_in.o, $(obj-y))
 # tell kbuild to descend
 subdir-obj-y := $(filter %/built_in.o, $(obj-y))
 
+# Libraries are always collected in one lib file.
+# Filter out objects already built-in
+lib-y := $(filter-out $(obj-y), $(sort $(lib-y)))
+
 $(filter %.init.o,$(obj-y) $(obj-bin-y) $(extra-y)): CFLAGS-y += -DINIT_SECTIONS_ONLY
 
 ifeq ($(CONFIG_COVERAGE),y)
@@ -129,19 +144,25 @@ include $(BASEDIR)/arch/$(TARGET_ARCH)/Rules.mk
 c_flags += $(CFLAGS-y)
 a_flags += $(CFLAGS-y) $(AFLAGS-y)
 
-built_in.o: $(obj-y) $(extra-y)
+built_in.o: $(obj-y) $(if $(strip $(lib-y)),lib.a) $(extra-y)
 ifeq ($(obj-y),)
 	$(CC) $(c_flags) -c -x c /dev/null -o $@
 else
 ifeq ($(CONFIG_LTO),y)
-	$(LD_LTO) -r -o $@ $(filter-out $(extra-y),$^)
+	$(LD_LTO) -r -o $@ $(filter-out lib.a $(extra-y),$^)
 else
-	$(LD) $(XEN_LDFLAGS) -r -o $@ $(filter-out $(extra-y),$^)
+	$(LD) $(XEN_LDFLAGS) -r -o $@ $(filter-out lib.a $(extra-y),$^)
 endif
 endif
 
+lib.a: $(lib-y) FORCE
+	$(call if_changed,ar)
+
 targets += built_in.o
-targets += $(filter-out $(subdir-obj-y), $(obj-y)) $(extra-y)
+ifneq ($(strip $(lib-y)),)
+targets += lib.a
+endif
+targets += $(filter-out $(subdir-obj-y), $(obj-y) $(lib-y)) $(extra-y)
 targets += $(MAKECMDGOALS)
 
 built_in_bin.o: $(obj-bin-y) $(extra-y)
@@ -155,7 +176,7 @@ endif
 PHONY += FORCE
 FORCE:
 
-%/built_in.o: FORCE
+%/built_in.o %/lib.a: FORCE
 	$(MAKE) -f $(BASEDIR)/Rules.mk -C $* built_in.o
 
 %/built_in_bin.o: FORCE
diff --git a/xen/arch/arm/Makefile b/xen/arch/arm/Makefile
index 296c5e68bbc3..612a83b315c8 100644
--- a/xen/arch/arm/Makefile
+++ b/xen/arch/arm/Makefile
@@ -90,14 +90,14 @@ endif
 
 ifeq ($(CONFIG_LTO),y)
 # Gather all LTO objects together
-prelink_lto.o: $(ALL_OBJS)
-	$(LD_LTO) -r -o $@ $^
+prelink_lto.o: $(ALL_OBJS) $(ALL_LIBS)
+	$(LD_LTO) -r -o $@ $(filter-out %.a,$^) --start-group $(filter %.a,$^) --end-group
 
 # Link it with all the binary objects
 prelink.o: $(patsubst %/built_in.o,%/built_in_bin.o,$(ALL_OBJS)) prelink_lto.o
 	$(call if_changed,ld)
 else
-prelink.o: $(ALL_OBJS) FORCE
+prelink.o: $(ALL_OBJS) $(ALL_LIBS) FORCE
 	$(call if_changed,ld)
 endif
 
diff --git a/xen/arch/x86/Makefile b/xen/arch/x86/Makefile
index 9b368632fb43..8f2180485b2b 100644
--- a/xen/arch/x86/Makefile
+++ b/xen/arch/x86/Makefile
@@ -132,8 +132,8 @@ EFI_OBJS-$(XEN_BUILD_EFI) := efi/relocs-dummy.o
 
 ifeq ($(CONFIG_LTO),y)
 # Gather all LTO objects together
-prelink_lto.o: $(ALL_OBJS)
-	$(LD_LTO) -r -o $@ $^
+prelink_lto.o: $(ALL_OBJS) $(ALL_LIBS)
+	$(LD_LTO) -r -o $@ $(filter-out %.a,$^) --start-group $(filter %.a,$^) --end-group
 
 # Link it with all the binary objects
 prelink.o: $(patsubst %/built_in.o,%/built_in_bin.o,$(ALL_OBJS)) prelink_lto.o $(EFI_OBJS-y) FORCE
@@ -142,10 +142,10 @@ prelink.o: $(patsubst %/built_in.o,%/built_in_bin.o,$(ALL_OBJS)) prelink_lto.o $
 prelink-efi.o: $(patsubst %/built_in.o,%/built_in_bin.o,$(ALL_OBJS)) prelink_lto.o FORCE
 	$(call if_changed,ld)
 else
-prelink.o: $(ALL_OBJS) $(EFI_OBJS-y) FORCE
+prelink.o: $(ALL_OBJS) $(ALL_LIBS) $(EFI_OBJS-y) FORCE
 	$(call if_changed,ld)
 
-prelink-efi.o: $(ALL_OBJS) FORCE
+prelink-efi.o: $(ALL_OBJS) $(ALL_LIBS) FORCE
 	$(call if_changed,ld)
 endif
 
diff --git a/xen/lib/Makefile b/xen/lib/Makefile
index 53b1da025e0d..b8814361d63e 100644
--- a/xen/lib/Makefile
+++ b/xen/lib/Makefile
@@ -1,2 +1,3 @@
-obj-y += ctype.o
 obj-$(CONFIG_X86) += x86/
+
+lib-y += ctype.o
-- 
2.22.0

[PATCH v2 3/8] lib: move list sorting code

[Jan Beulich]

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().

Signed-off-by: Jan Beulich <jbeulich@suse.com>

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().

Signed-off-by: Jan Beulich <jbeulich@suse.com>
---
 xen/arch/arm/Kconfig                        | 4 +---
 xen/common/Kconfig                          | 3 ---
 xen/common/Makefile                         | 1 -
 xen/lib/Makefile                            | 1 +
 xen/{common/list_sort.c => lib/list-sort.c} | 2 --
 5 files changed, 2 insertions(+), 9 deletions(-)
 rename xen/{common/list_sort.c => lib/list-sort.c} (98%)

diff --git a/xen/arch/arm/Kconfig b/xen/arch/arm/Kconfig
index 277738826581..cb7e2523b6de 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 3e2cf2508899..0661328a99e7 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 083f62acb634..52d3c2aa9384 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/lib/Makefile b/xen/lib/Makefile
index b8814361d63e..764f3624b5f9 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/common/list_sort.c b/xen/lib/list-sort.c
similarity index 98%
rename from xen/common/list_sort.c
rename to xen/lib/list-sort.c
index af2b2f6519f1..f8d8bbf28178 100644
--- a/xen/common/list_sort.c
+++ b/xen/lib/list-sort.c
@@ -15,7 +15,6 @@
  * this program; If not, see <http://www.gnu.org/licenses/>.
  */
 
-#include <xen/lib.h>
 #include <xen/list.h>
 
 #define MAX_LIST_LENGTH_BITS 20
@@ -154,4 +153,3 @@ void list_sort(void *priv, struct list_head *head,
 
 	merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
 }
-EXPORT_SYMBOL(list_sort);
-- 
2.22.0

[PATCH v2 4/8] lib: move parse_size_and_unit()

[Jan Beulich]

... into its own CU, to build it into an archive.

Signed-off-by: Jan Beulich <jbeulich@suse.com>

... into its own CU, to build it into an archive.

Signed-off-by: Jan Beulich <jbeulich@suse.com>
---
 xen/common/lib.c     | 39 ----------------------------------
 xen/lib/Makefile     |  1 +
 xen/lib/parse-size.c | 50 ++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 51 insertions(+), 39 deletions(-)
 create mode 100644 xen/lib/parse-size.c

diff --git a/xen/common/lib.c b/xen/common/lib.c
index a224efa8f6e8..6cfa332142a5 100644
--- a/xen/common/lib.c
+++ b/xen/common/lib.c
@@ -423,45 +423,6 @@ uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c)
 #endif
 }
 
-unsigned long long parse_size_and_unit(const char *s, const char **ps)
-{
-    unsigned long long ret;
-    const char *s1;
-
-    ret = simple_strtoull(s, &s1, 0);
-
-    switch ( *s1 )
-    {
-    case 'T': case 't':
-        ret <<= 10;
-        /* fallthrough */
-    case 'G': case 'g':
-        ret <<= 10;
-        /* fallthrough */
-    case 'M': case 'm':
-        ret <<= 10;
-        /* fallthrough */
-    case 'K': case 'k':
-        ret <<= 10;
-        /* fallthrough */
-    case 'B': case 'b':
-        s1++;
-        break;
-    case '%':
-        if ( ps )
-            break;
-        /* fallthrough */
-    default:
-        ret <<= 10; /* default to kB */
-        break;
-    }
-
-    if ( ps != NULL )
-        *ps = s1;
-
-    return ret;
-}
-
 typedef void (*ctor_func_t)(void);
 extern const ctor_func_t __ctors_start[], __ctors_end[];
 
diff --git a/xen/lib/Makefile b/xen/lib/Makefile
index 764f3624b5f9..99f857540c99 100644
--- a/xen/lib/Makefile
+++ b/xen/lib/Makefile
@@ -2,3 +2,4 @@ obj-$(CONFIG_X86) += x86/
 
 lib-y += ctype.o
 lib-y += list-sort.o
+lib-y += parse-size.o
diff --git a/xen/lib/parse-size.c b/xen/lib/parse-size.c
new file mode 100644
index 000000000000..ec980cadfff3
--- /dev/null
+++ b/xen/lib/parse-size.c
@@ -0,0 +1,50 @@
+#include <xen/lib.h>
+
+unsigned long long parse_size_and_unit(const char *s, const char **ps)
+{
+    unsigned long long ret;
+    const char *s1;
+
+    ret = simple_strtoull(s, &s1, 0);
+
+    switch ( *s1 )
+    {
+    case 'T': case 't':
+        ret <<= 10;
+        /* fallthrough */
+    case 'G': case 'g':
+        ret <<= 10;
+        /* fallthrough */
+    case 'M': case 'm':
+        ret <<= 10;
+        /* fallthrough */
+    case 'K': case 'k':
+        ret <<= 10;
+        /* fallthrough */
+    case 'B': case 'b':
+        s1++;
+        break;
+    case '%':
+        if ( ps )
+            break;
+        /* fallthrough */
+    default:
+        ret <<= 10; /* default to kB */
+        break;
+    }
+
+    if ( ps != NULL )
+        *ps = s1;
+
+    return ret;
+}
+
+/*
+ * Local variables:
+ * mode: C
+ * c-file-style: "BSD"
+ * c-basic-offset: 4
+ * tab-width: 4
+ * indent-tabs-mode: nil
+ * End:
+ */
-- 
2.22.0

[PATCH v2 5/8] lib: move init_constructors()

[Jan Beulich]

... into its own CU, for being unrelated to other things in
common/lib.c. For now it gets compiled into built_in.o rather than
lib.a, as it gets used unconditionally by Arm's as well as x86'es
{,__}start_xen(). But this could be changed in principle, the more that
there typically aren't any constructors anyway. Then again it's just
__init code anyway.

Signed-off-by: Jan Beulich <jbeulich@suse.com>
---
 xen/common/lib.c | 14 --------------
 xen/lib/Makefile |  1 +
 xen/lib/ctors.c  | 25 +++++++++++++++++++++++++
 3 files changed, 26 insertions(+), 14 deletions(-)
 create mode 100644 xen/lib/ctors.c

diff --git a/xen/common/lib.c b/xen/common/lib.c
index 6cfa332142a5..f5ca179a0af4 100644
--- a/xen/common/lib.c
+++ b/xen/common/lib.c
@@ -1,6 +1,5 @@
 #include <xen/lib.h>
 #include <xen/types.h>
-#include <xen/init.h>
 #include <asm/byteorder.h>
 
 /*
@@ -423,19 +422,6 @@ uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c)
 #endif
 }
 
-typedef void (*ctor_func_t)(void);
-extern const ctor_func_t __ctors_start[], __ctors_end[];
-
-void __init init_constructors(void)
-{
-    const ctor_func_t *f;
-    for ( f = __ctors_start; f < __ctors_end; ++f )
-        (*f)();
-
-    /* Putting this here seems as good (or bad) as any other place. */
-    BUILD_BUG_ON(sizeof(size_t) != sizeof(ssize_t));
-}
-
 /*
  * Local variables:
  * mode: C
diff --git a/xen/lib/Makefile b/xen/lib/Makefile
index 99f857540c99..ba1fb7bcdee2 100644
--- a/xen/lib/Makefile
+++ b/xen/lib/Makefile
@@ -1,3 +1,4 @@
+obj-y += ctors.o
 obj-$(CONFIG_X86) += x86/
 
 lib-y += ctype.o
diff --git a/xen/lib/ctors.c b/xen/lib/ctors.c
new file mode 100644
index 000000000000..5bdc591cd50a
--- /dev/null
+++ b/xen/lib/ctors.c
@@ -0,0 +1,25 @@
+#include <xen/init.h>
+#include <xen/lib.h>
+
+typedef void (*ctor_func_t)(void);
+extern const ctor_func_t __ctors_start[], __ctors_end[];
+
+void __init init_constructors(void)
+{
+    const ctor_func_t *f;
+    for ( f = __ctors_start; f < __ctors_end; ++f )
+        (*f)();
+
+    /* Putting this here seems as good (or bad) as any other place. */
+    BUILD_BUG_ON(sizeof(size_t) != sizeof(ssize_t));
+}
+
+/*
+ * Local variables:
+ * mode: C
+ * c-file-style: "BSD"
+ * c-basic-offset: 4
+ * tab-width: 4
+ * indent-tabs-mode: nil
+ * End:
+ */
-- 
2.22.0

[PATCH v2 6/8] lib: move rbtree code

[Jan Beulich]

Build this code into an archive, which results in not linking it into
x86 final binaries. This saves about 1.5k of dead code.

While moving the source file, take the opportunity and drop the
pointless EXPORT_SYMBOL().

Signed-off-by: Jan Beulich <jbeulich@suse.com>
---
 xen/common/Makefile          | 1 -
 xen/lib/Makefile             | 1 +
 xen/{common => lib}/rbtree.c | 9 +--------
 3 files changed, 2 insertions(+), 9 deletions(-)
 rename xen/{common => lib}/rbtree.c (98%)

diff --git a/xen/common/Makefile b/xen/common/Makefile
index 52d3c2aa9384..7bb779f780a1 100644
--- a/xen/common/Makefile
+++ b/xen/common/Makefile
@@ -33,7 +33,6 @@ obj-y += preempt.o
 obj-y += random.o
 obj-y += rangeset.o
 obj-y += radix-tree.o
-obj-y += rbtree.o
 obj-y += rcupdate.o
 obj-y += rwlock.o
 obj-y += shutdown.o
diff --git a/xen/lib/Makefile b/xen/lib/Makefile
index ba1fb7bcdee2..b469d2dff7b8 100644
--- a/xen/lib/Makefile
+++ b/xen/lib/Makefile
@@ -4,3 +4,4 @@ obj-$(CONFIG_X86) += x86/
 lib-y += ctype.o
 lib-y += list-sort.o
 lib-y += parse-size.o
+lib-y += rbtree.o
diff --git a/xen/common/rbtree.c b/xen/lib/rbtree.c
similarity index 98%
rename from xen/common/rbtree.c
rename to xen/lib/rbtree.c
index 9f5498a89d4e..95e045d52461 100644
--- a/xen/common/rbtree.c
+++ b/xen/lib/rbtree.c
@@ -25,7 +25,7 @@
 #include <xen/rbtree.h>
 
 /*
- * red-black trees properties:  http://en.wikipedia.org/wiki/Rbtree 
+ * red-black trees properties:  http://en.wikipedia.org/wiki/Rbtree
  *
  *  1) A node is either red or black
  *  2) The root is black
@@ -223,7 +223,6 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 		}
 	}
 }
-EXPORT_SYMBOL(rb_insert_color);
 
 static void __rb_erase_color(struct rb_node *parent, struct rb_root *root)
 {
@@ -467,7 +466,6 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
 	if (rebalance)
 		__rb_erase_color(rebalance, root);
 }
-EXPORT_SYMBOL(rb_erase);
 
 /*
  * This function returns the first node (in sort order) of the tree.
@@ -483,7 +481,6 @@ struct rb_node *rb_first(const struct rb_root *root)
 		n = n->rb_left;
 	return n;
 }
-EXPORT_SYMBOL(rb_first);
 
 struct rb_node *rb_last(const struct rb_root *root)
 {
@@ -496,7 +493,6 @@ struct rb_node *rb_last(const struct rb_root *root)
 		n = n->rb_right;
 	return n;
 }
-EXPORT_SYMBOL(rb_last);
 
 struct rb_node *rb_next(const struct rb_node *node)
 {
@@ -528,7 +524,6 @@ struct rb_node *rb_next(const struct rb_node *node)
 
 	return parent;
 }
-EXPORT_SYMBOL(rb_next);
 
 struct rb_node *rb_prev(const struct rb_node *node)
 {
@@ -557,7 +552,6 @@ struct rb_node *rb_prev(const struct rb_node *node)
 
 	return parent;
 }
-EXPORT_SYMBOL(rb_prev);
 
 void rb_replace_node(struct rb_node *victim, struct rb_node *new,
 		     struct rb_root *root)
@@ -574,4 +568,3 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
 	/* Copy the pointers/colour from the victim to the replacement */
 	*new = *victim;
 }
-EXPORT_SYMBOL(rb_replace_node);
-- 
2.22.0

[PATCH v2 7/8] lib: move bsearch code

[Jan Beulich]

Convert this code to an inline function (backed by an instance in an
archive in case the compiler decides against inlining), which results
in not having it in x86 final binaries. This saves a little bit of dead
code.

Signed-off-by: Jan Beulich <jbeulich@suse.com>
---
v2: Make the function an extern inline in its header.
---
 xen/common/Makefile        |  1 -
 xen/common/bsearch.c       | 51 --------------------------------------
 xen/include/xen/compiler.h |  1 +
 xen/include/xen/lib.h      | 42 ++++++++++++++++++++++++++++++-
 xen/lib/Makefile           |  1 +
 xen/lib/bsearch.c          | 13 ++++++++++
 6 files changed, 56 insertions(+), 53 deletions(-)
 delete mode 100644 xen/common/bsearch.c
 create mode 100644 xen/lib/bsearch.c

diff --git a/xen/common/Makefile b/xen/common/Makefile
index 7bb779f780a1..d8519a2cc163 100644
--- a/xen/common/Makefile
+++ b/xen/common/Makefile
@@ -1,6 +1,5 @@
 obj-$(CONFIG_ARGO) += argo.o
 obj-y += bitmap.o
-obj-y += bsearch.o
 obj-$(CONFIG_HYPFS_CONFIG) += config_data.o
 obj-$(CONFIG_CORE_PARKING) += core_parking.o
 obj-y += cpu.o
diff --git a/xen/common/bsearch.c b/xen/common/bsearch.c
deleted file mode 100644
index 7090930aab5c..000000000000
--- a/xen/common/bsearch.c
+++ /dev/null
@@ -1,51 +0,0 @@
-/*
- * A generic implementation of binary search for the Linux kernel
- *
- * Copyright (C) 2008-2009 Ksplice, Inc.
- * Author: Tim Abbott <tabbott@ksplice.com>
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License as
- * published by the Free Software Foundation; version 2.
- */
-
-#include <xen/lib.h>
-
-/*
- * bsearch - binary search an array of elements
- * @key: pointer to item being searched for
- * @base: pointer to first element to search
- * @num: number of elements
- * @size: size of each element
- * @cmp: pointer to comparison function
- *
- * This function does a binary search on the given array.  The
- * contents of the array should already be in ascending sorted order
- * under the provided comparison function.
- *
- * Note that the key need not have the same type as the elements in
- * the array, e.g. key could be a string and the comparison function
- * could compare the string with the struct's name field.  However, if
- * the key and elements in the array are of the same type, you can use
- * the same comparison function for both sort() and bsearch().
- */
-void *bsearch(const void *key, const void *base, size_t num, size_t size,
-	      int (*cmp)(const void *key, const void *elt))
-{
-	size_t start = 0, end = num;
-	int result;
-
-	while (start < end) {
-		size_t mid = start + (end - start) / 2;
-
-		result = cmp(key, base + mid * size);
-		if (result < 0)
-			end = mid;
-		else if (result > 0)
-			start = mid + 1;
-		else
-			return (void *)base + mid * size;
-	}
-
-	return NULL;
-}
diff --git a/xen/include/xen/compiler.h b/xen/include/xen/compiler.h
index c0e0ee9f27be..2b7acdf3b188 100644
--- a/xen/include/xen/compiler.h
+++ b/xen/include/xen/compiler.h
@@ -12,6 +12,7 @@
 
 #define inline        __inline__
 #define always_inline __inline__ __attribute__ ((__always_inline__))
+#define gnu_inline    __inline__ __attribute__ ((__gnu_inline__))
 #define noinline      __attribute__((__noinline__))
 
 #define noreturn      __attribute__((__noreturn__))
diff --git a/xen/include/xen/lib.h b/xen/include/xen/lib.h
index 076bcfb67dbb..940d23755661 100644
--- a/xen/include/xen/lib.h
+++ b/xen/include/xen/lib.h
@@ -192,8 +192,48 @@ void dump_execstate(struct cpu_user_regs *);
 
 void init_constructors(void);
 
+/*
+ * bsearch - binary search an array of elements
+ * @key: pointer to item being searched for
+ * @base: pointer to first element to search
+ * @num: number of elements
+ * @size: size of each element
+ * @cmp: pointer to comparison function
+ *
+ * This function does a binary search on the given array.  The
+ * contents of the array should already be in ascending sorted order
+ * under the provided comparison function.
+ *
+ * Note that the key need not have the same type as the elements in
+ * the array, e.g. key could be a string and the comparison function
+ * could compare the string with the struct's name field.  However, if
+ * the key and elements in the array are of the same type, you can use
+ * the same comparison function for both sort() and bsearch().
+ */
+#ifndef BSEARCH_IMPLEMENTATION
+extern gnu_inline
+#endif
 void *bsearch(const void *key, const void *base, size_t num, size_t size,
-              int (*cmp)(const void *key, const void *elt));
+              int (*cmp)(const void *key, const void *elt))
+{
+    size_t start = 0, end = num;
+    int result;
+
+    while ( start < end )
+    {
+        size_t mid = start + (end - start) / 2;
+
+        result = cmp(key, base + mid * size);
+        if ( result < 0 )
+            end = mid;
+        else if ( result > 0 )
+            start = mid + 1;
+        else
+            return (void *)base + mid * size;
+    }
+
+    return NULL;
+}
 
 #endif /* __ASSEMBLY__ */
 
diff --git a/xen/lib/Makefile b/xen/lib/Makefile
index b469d2dff7b8..122eeb3d327b 100644
--- a/xen/lib/Makefile
+++ b/xen/lib/Makefile
@@ -1,6 +1,7 @@
 obj-y += ctors.o
 obj-$(CONFIG_X86) += x86/
 
+lib-y += bsearch.o
 lib-y += ctype.o
 lib-y += list-sort.o
 lib-y += parse-size.o
diff --git a/xen/lib/bsearch.c b/xen/lib/bsearch.c
new file mode 100644
index 000000000000..149f7feafd1f
--- /dev/null
+++ b/xen/lib/bsearch.c
@@ -0,0 +1,13 @@
+/*
+ * A generic implementation of binary search for the Linux kernel
+ *
+ * Copyright (C) 2008-2009 Ksplice, Inc.
+ * Author: Tim Abbott <tabbott@ksplice.com>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; version 2.
+ */
+
+#define BSEARCH_IMPLEMENTATION
+#include <xen/lib.h>
-- 
2.22.0

[PATCH v2 8/8] lib: move sort code

[Jan Beulich]

Build this code into an archive, partly paralleling bsearch().

Signed-off-by: Jan Beulich <jbeulich@suse.com>
---
 xen/common/Makefile        | 1 -
 xen/lib/Makefile           | 1 +
 xen/{common => lib}/sort.c | 0
 3 files changed, 1 insertion(+), 1 deletion(-)
 rename xen/{common => lib}/sort.c (100%)

diff --git a/xen/common/Makefile b/xen/common/Makefile
index d8519a2cc163..90c679958965 100644
--- a/xen/common/Makefile
+++ b/xen/common/Makefile
@@ -36,7 +36,6 @@ obj-y += rcupdate.o
 obj-y += rwlock.o
 obj-y += shutdown.o
 obj-y += softirq.o
-obj-y += sort.o
 obj-y += smp.o
 obj-y += spinlock.o
 obj-y += stop_machine.o
diff --git a/xen/lib/Makefile b/xen/lib/Makefile
index 122eeb3d327b..33ff322b1655 100644
--- a/xen/lib/Makefile
+++ b/xen/lib/Makefile
@@ -6,3 +6,4 @@ lib-y += ctype.o
 lib-y += list-sort.o
 lib-y += parse-size.o
 lib-y += rbtree.o
+lib-y += sort.o
diff --git a/xen/common/sort.c b/xen/lib/sort.c
similarity index 100%
rename from xen/common/sort.c
rename to xen/lib/sort.c
-- 
2.22.0

Re: [PATCH v2 1/8] lib: split _ctype[] into its own object, under lib/

[Julien Grall]

Hi Jan,

On 23/10/2020 11:16, Jan Beulich wrote:
> This is, besides for tidying, in preparation of then starting to use an
> archive rather than an object file for generic library code which
> arch-es (or even specific configurations within a single arch) may or
> may not need.
> 
> Signed-off-by: Jan Beulich <jbeulich@suse.com>

Acked-by: Julien Grall <jgrall@amazon.com>

Cheers,

> ---
>   xen/Makefile     |  3 ++-
>   xen/Rules.mk     |  2 +-
>   xen/common/lib.c | 29 -----------------------------
>   xen/lib/Makefile |  1 +
>   xen/lib/ctype.c  | 38 ++++++++++++++++++++++++++++++++++++++
>   5 files changed, 42 insertions(+), 31 deletions(-)
>   create mode 100644 xen/lib/ctype.c
> 
> diff --git a/xen/Makefile b/xen/Makefile
> index bf0c804d4352..73bdc326c549 100644
> --- a/xen/Makefile
> +++ b/xen/Makefile
> @@ -331,6 +331,7 @@ _clean: delete-unfresh-files
>   	$(MAKE) $(clean) include
>   	$(MAKE) $(clean) common
>   	$(MAKE) $(clean) drivers
> +	$(MAKE) $(clean) lib
>   	$(MAKE) $(clean) xsm
>   	$(MAKE) $(clean) crypto
>   	$(MAKE) $(clean) arch/arm
> @@ -414,7 +415,7 @@ include/asm-$(TARGET_ARCH)/asm-offsets.h: arch/$(TARGET_ARCH)/asm-offsets.s
>   	  echo ""; \
>   	  echo "#endif") <$< >$@
>   
> -SUBDIRS = xsm arch/$(TARGET_ARCH) common drivers test
> +SUBDIRS = xsm arch/$(TARGET_ARCH) common drivers lib test
>   define all_sources
>       ( find include/asm-$(TARGET_ARCH) -name '*.h' -print; \
>         find include -name 'asm-*' -prune -o -name '*.h' -print; \
> diff --git a/xen/Rules.mk b/xen/Rules.mk
> index 891c94e6ad00..333e19bec343 100644
> --- a/xen/Rules.mk
> +++ b/xen/Rules.mk
> @@ -36,7 +36,7 @@ TARGET := $(BASEDIR)/xen
>   # Note that link order matters!
>   ALL_OBJS-y               += $(BASEDIR)/common/built_in.o
>   ALL_OBJS-y               += $(BASEDIR)/drivers/built_in.o
> -ALL_OBJS-$(CONFIG_X86)   += $(BASEDIR)/lib/built_in.o
> +ALL_OBJS-y               += $(BASEDIR)/lib/built_in.o
>   ALL_OBJS-y               += $(BASEDIR)/xsm/built_in.o
>   ALL_OBJS-y               += $(BASEDIR)/arch/$(TARGET_ARCH)/built_in.o
>   ALL_OBJS-$(CONFIG_CRYPTO)   += $(BASEDIR)/crypto/built_in.o
> diff --git a/xen/common/lib.c b/xen/common/lib.c
> index b2b799da44c5..a224efa8f6e8 100644
> --- a/xen/common/lib.c
> +++ b/xen/common/lib.c
> @@ -1,37 +1,8 @@
> -
> -#include <xen/ctype.h>
>   #include <xen/lib.h>
>   #include <xen/types.h>
>   #include <xen/init.h>
>   #include <asm/byteorder.h>
>   
> -/* for ctype.h */
> -const unsigned char _ctype[] = {
> -    _C,_C,_C,_C,_C,_C,_C,_C,                        /* 0-7 */
> -    _C,_C|_S,_C|_S,_C|_S,_C|_S,_C|_S,_C,_C,         /* 8-15 */
> -    _C,_C,_C,_C,_C,_C,_C,_C,                        /* 16-23 */
> -    _C,_C,_C,_C,_C,_C,_C,_C,                        /* 24-31 */
> -    _S|_SP,_P,_P,_P,_P,_P,_P,_P,                    /* 32-39 */
> -    _P,_P,_P,_P,_P,_P,_P,_P,                        /* 40-47 */
> -    _D,_D,_D,_D,_D,_D,_D,_D,                        /* 48-55 */
> -    _D,_D,_P,_P,_P,_P,_P,_P,                        /* 56-63 */
> -    _P,_U|_X,_U|_X,_U|_X,_U|_X,_U|_X,_U|_X,_U,      /* 64-71 */
> -    _U,_U,_U,_U,_U,_U,_U,_U,                        /* 72-79 */
> -    _U,_U,_U,_U,_U,_U,_U,_U,                        /* 80-87 */
> -    _U,_U,_U,_P,_P,_P,_P,_P,                        /* 88-95 */
> -    _P,_L|_X,_L|_X,_L|_X,_L|_X,_L|_X,_L|_X,_L,      /* 96-103 */
> -    _L,_L,_L,_L,_L,_L,_L,_L,                        /* 104-111 */
> -    _L,_L,_L,_L,_L,_L,_L,_L,                        /* 112-119 */
> -    _L,_L,_L,_P,_P,_P,_P,_C,                        /* 120-127 */
> -    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,                /* 128-143 */
> -    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,                /* 144-159 */
> -    _S|_SP,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,   /* 160-175 */
> -    _P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,       /* 176-191 */
> -    _U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,       /* 192-207 */
> -    _U,_U,_U,_U,_U,_U,_U,_P,_U,_U,_U,_U,_U,_U,_U,_L,       /* 208-223 */
> -    _L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,       /* 224-239 */
> -    _L,_L,_L,_L,_L,_L,_L,_P,_L,_L,_L,_L,_L,_L,_L,_L};      /* 240-255 */
> -
>   /*
>    * A couple of 64 bit operations ported from FreeBSD.
>    * The code within the '#if BITS_PER_LONG == 32' block below, and no other
> diff --git a/xen/lib/Makefile b/xen/lib/Makefile
> index 7019ca00e8fd..53b1da025e0d 100644
> --- a/xen/lib/Makefile
> +++ b/xen/lib/Makefile
> @@ -1 +1,2 @@
> +obj-y += ctype.o
>   obj-$(CONFIG_X86) += x86/
> diff --git a/xen/lib/ctype.c b/xen/lib/ctype.c
> new file mode 100644
> index 000000000000..7b233a335fdf
> --- /dev/null
> +++ b/xen/lib/ctype.c
> @@ -0,0 +1,38 @@
> +#include <xen/ctype.h>
> +
> +/* for ctype.h */
> +const unsigned char _ctype[] = {
> +    _C,_C,_C,_C,_C,_C,_C,_C,                        /* 0-7 */
> +    _C,_C|_S,_C|_S,_C|_S,_C|_S,_C|_S,_C,_C,         /* 8-15 */
> +    _C,_C,_C,_C,_C,_C,_C,_C,                        /* 16-23 */
> +    _C,_C,_C,_C,_C,_C,_C,_C,                        /* 24-31 */
> +    _S|_SP,_P,_P,_P,_P,_P,_P,_P,                    /* 32-39 */
> +    _P,_P,_P,_P,_P,_P,_P,_P,                        /* 40-47 */
> +    _D,_D,_D,_D,_D,_D,_D,_D,                        /* 48-55 */
> +    _D,_D,_P,_P,_P,_P,_P,_P,                        /* 56-63 */
> +    _P,_U|_X,_U|_X,_U|_X,_U|_X,_U|_X,_U|_X,_U,      /* 64-71 */
> +    _U,_U,_U,_U,_U,_U,_U,_U,                        /* 72-79 */
> +    _U,_U,_U,_U,_U,_U,_U,_U,                        /* 80-87 */
> +    _U,_U,_U,_P,_P,_P,_P,_P,                        /* 88-95 */
> +    _P,_L|_X,_L|_X,_L|_X,_L|_X,_L|_X,_L|_X,_L,      /* 96-103 */
> +    _L,_L,_L,_L,_L,_L,_L,_L,                        /* 104-111 */
> +    _L,_L,_L,_L,_L,_L,_L,_L,                        /* 112-119 */
> +    _L,_L,_L,_P,_P,_P,_P,_C,                        /* 120-127 */
> +    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,                /* 128-143 */
> +    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,                /* 144-159 */
> +    _S|_SP,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,   /* 160-175 */
> +    _P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,       /* 176-191 */
> +    _U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,       /* 192-207 */
> +    _U,_U,_U,_U,_U,_U,_U,_P,_U,_U,_U,_U,_U,_U,_U,_L,       /* 208-223 */
> +    _L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,       /* 224-239 */
> +    _L,_L,_L,_L,_L,_L,_L,_P,_L,_L,_L,_L,_L,_L,_L,_L};      /* 240-255 */
> +
> +/*
> + * Local variables:
> + * mode: C
> + * c-file-style: "BSD"
> + * c-basic-offset: 4
> + * tab-width: 4
> + * indent-tabs-mode: nil
> + * End:
> + */
> 

-- 
Julien Grall

Re: [PATCH v2 2/8] lib: collect library files in an archive

[Julien Grall]

(+ Anthony)

Hi Jan,

On 23/10/2020 11:17, Jan Beulich wrote:
> In order to (subsequently) drop odd things like CONFIG_NEEDS_LIST_SORT
> just to avoid bloating binaries when only some arch-es and/or
> configurations need generic library routines, combine objects under lib/
> into an archive, which the linker then can pick the necessary objects
> out of.
> 
> Note that we can't use thin archives just yet, until we've raised the
> minimum required binutils version suitably.
> 
> Signed-off-by: Jan Beulich <jbeulich@suse.com>
> ---
>   xen/Rules.mk          | 33 +++++++++++++++++++++++++++------
>   xen/arch/arm/Makefile |  6 +++---
>   xen/arch/x86/Makefile |  8 ++++----
>   xen/lib/Makefile      |  3 ++-

IIRC, Anthony worked on the build systems. If I am right, it would be 
good to get a review from him.

>   4 files changed, 36 insertions(+), 14 deletions(-)
> 
> diff --git a/xen/Rules.mk b/xen/Rules.mk
> index 333e19bec343..e59c7f213f77 100644
> --- a/xen/Rules.mk
> +++ b/xen/Rules.mk
> @@ -41,12 +41,16 @@ ALL_OBJS-y               += $(BASEDIR)/xsm/built_in.o
>   ALL_OBJS-y               += $(BASEDIR)/arch/$(TARGET_ARCH)/built_in.o
>   ALL_OBJS-$(CONFIG_CRYPTO)   += $(BASEDIR)/crypto/built_in.o
>   
> +ALL_LIBS-y               := $(BASEDIR)/lib/lib.a
> +
>   # Initialise some variables
> +lib-y :=
>   targets :=
>   CFLAGS-y :=
>   AFLAGS-y :=
>   
>   ALL_OBJS := $(ALL_OBJS-y)
> +ALL_LIBS := $(ALL_LIBS-y)
>   
>   SPECIAL_DATA_SECTIONS := rodata $(foreach a,1 2 4 8 16, \
>                                               $(foreach w,1 2 4, \
> @@ -60,7 +64,14 @@ include Makefile
>   # ---------------------------------------------------------------------------
>   
>   quiet_cmd_ld = LD      $@
> -cmd_ld = $(LD) $(XEN_LDFLAGS) -r -o $@ $(real-prereqs)
> +cmd_ld = $(LD) $(XEN_LDFLAGS) -r -o $@ $(filter-out %.a,$(real-prereqs)) \
> +               --start-group $(filter %.a,$(real-prereqs)) --end-group
> +
> +# Archive
> +# ---------------------------------------------------------------------------
> +
> +quiet_cmd_ar = AR      $@
> +cmd_ar = rm -f $@; $(AR) cPrs $@ $(real-prereqs)
>   
>   # Objcopy
>   # ---------------------------------------------------------------------------
> @@ -86,6 +97,10 @@ obj-y    := $(patsubst %/, %/built_in.o, $(obj-y))
>   # tell kbuild to descend
>   subdir-obj-y := $(filter %/built_in.o, $(obj-y))
>   
> +# Libraries are always collected in one lib file.
> +# Filter out objects already built-in
> +lib-y := $(filter-out $(obj-y), $(sort $(lib-y)))
> +
>   $(filter %.init.o,$(obj-y) $(obj-bin-y) $(extra-y)): CFLAGS-y += -DINIT_SECTIONS_ONLY
>   
>   ifeq ($(CONFIG_COVERAGE),y)
> @@ -129,19 +144,25 @@ include $(BASEDIR)/arch/$(TARGET_ARCH)/Rules.mk
>   c_flags += $(CFLAGS-y)
>   a_flags += $(CFLAGS-y) $(AFLAGS-y)
>   
> -built_in.o: $(obj-y) $(extra-y)
> +built_in.o: $(obj-y) $(if $(strip $(lib-y)),lib.a) $(extra-y)
>   ifeq ($(obj-y),)
>   	$(CC) $(c_flags) -c -x c /dev/null -o $@
>   else
>   ifeq ($(CONFIG_LTO),y)
> -	$(LD_LTO) -r -o $@ $(filter-out $(extra-y),$^)
> +	$(LD_LTO) -r -o $@ $(filter-out lib.a $(extra-y),$^)
>   else
> -	$(LD) $(XEN_LDFLAGS) -r -o $@ $(filter-out $(extra-y),$^)
> +	$(LD) $(XEN_LDFLAGS) -r -o $@ $(filter-out lib.a $(extra-y),$^)
>   endif
>   endif
>   
> +lib.a: $(lib-y) FORCE
> +	$(call if_changed,ar)
> +
>   targets += built_in.o
> -targets += $(filter-out $(subdir-obj-y), $(obj-y)) $(extra-y)
> +ifneq ($(strip $(lib-y)),)
> +targets += lib.a
> +endif
> +targets += $(filter-out $(subdir-obj-y), $(obj-y) $(lib-y)) $(extra-y)
>   targets += $(MAKECMDGOALS)
>   
>   built_in_bin.o: $(obj-bin-y) $(extra-y)
> @@ -155,7 +176,7 @@ endif
>   PHONY += FORCE
>   FORCE:
>   
> -%/built_in.o: FORCE
> +%/built_in.o %/lib.a: FORCE
>   	$(MAKE) -f $(BASEDIR)/Rules.mk -C $* built_in.o
>   
>   %/built_in_bin.o: FORCE
> diff --git a/xen/arch/arm/Makefile b/xen/arch/arm/Makefile
> index 296c5e68bbc3..612a83b315c8 100644
> --- a/xen/arch/arm/Makefile
> +++ b/xen/arch/arm/Makefile
> @@ -90,14 +90,14 @@ endif
>   
>   ifeq ($(CONFIG_LTO),y)
>   # Gather all LTO objects together
> -prelink_lto.o: $(ALL_OBJS)
> -	$(LD_LTO) -r -o $@ $^
> +prelink_lto.o: $(ALL_OBJS) $(ALL_LIBS)
> +	$(LD_LTO) -r -o $@ $(filter-out %.a,$^) --start-group $(filter %.a,$^) --end-group
>   
>   # Link it with all the binary objects
>   prelink.o: $(patsubst %/built_in.o,%/built_in_bin.o,$(ALL_OBJS)) prelink_lto.o
>   	$(call if_changed,ld)
>   else
> -prelink.o: $(ALL_OBJS) FORCE
> +prelink.o: $(ALL_OBJS) $(ALL_LIBS) FORCE
>   	$(call if_changed,ld)
>   endif
>   
> diff --git a/xen/arch/x86/Makefile b/xen/arch/x86/Makefile
> index 9b368632fb43..8f2180485b2b 100644
> --- a/xen/arch/x86/Makefile
> +++ b/xen/arch/x86/Makefile
> @@ -132,8 +132,8 @@ EFI_OBJS-$(XEN_BUILD_EFI) := efi/relocs-dummy.o
>   
>   ifeq ($(CONFIG_LTO),y)
>   # Gather all LTO objects together
> -prelink_lto.o: $(ALL_OBJS)
> -	$(LD_LTO) -r -o $@ $^
> +prelink_lto.o: $(ALL_OBJS) $(ALL_LIBS)
> +	$(LD_LTO) -r -o $@ $(filter-out %.a,$^) --start-group $(filter %.a,$^) --end-group
>   
>   # Link it with all the binary objects
>   prelink.o: $(patsubst %/built_in.o,%/built_in_bin.o,$(ALL_OBJS)) prelink_lto.o $(EFI_OBJS-y) FORCE
> @@ -142,10 +142,10 @@ prelink.o: $(patsubst %/built_in.o,%/built_in_bin.o,$(ALL_OBJS)) prelink_lto.o $
>   prelink-efi.o: $(patsubst %/built_in.o,%/built_in_bin.o,$(ALL_OBJS)) prelink_lto.o FORCE
>   	$(call if_changed,ld)
>   else
> -prelink.o: $(ALL_OBJS) $(EFI_OBJS-y) FORCE
> +prelink.o: $(ALL_OBJS) $(ALL_LIBS) $(EFI_OBJS-y) FORCE
>   	$(call if_changed,ld)
>   
> -prelink-efi.o: $(ALL_OBJS) FORCE
> +prelink-efi.o: $(ALL_OBJS) $(ALL_LIBS) FORCE
>   	$(call if_changed,ld)
>   endif
>   
> diff --git a/xen/lib/Makefile b/xen/lib/Makefile
> index 53b1da025e0d..b8814361d63e 100644
> --- a/xen/lib/Makefile
> +++ b/xen/lib/Makefile
> @@ -1,2 +1,3 @@
> -obj-y += ctype.o
>   obj-$(CONFIG_X86) += x86/
> +
> +lib-y += ctype.o

May I ask why all the code movement by ctype was done after this patch?

Cheers,

-- 
Julien Grall

Re: [PATCH v2 2/8] lib: collect library files in an archive

[Julien Grall]

Hi Jan,

On 23/10/2020 11:17, Jan Beulich wrote:
> In order to (subsequently) drop odd things like CONFIG_NEEDS_LIST_SORT
> just to avoid bloating binaries when only some arch-es and/or
> configurations need generic library routines, combine objects under lib/
> into an archive, which the linker then can pick the necessary objects
> out of.
> 
> Note that we can't use thin archives just yet, until we've raised the
> minimum required binutils version suitably.
> 
> Signed-off-by: Jan Beulich <jbeulich@suse.com>
> ---
>   xen/Rules.mk          | 33 +++++++++++++++++++++++++++------
>   xen/arch/arm/Makefile |  6 +++---
>   xen/arch/x86/Makefile |  8 ++++----
>   xen/lib/Makefile      |  3 ++-
>   4 files changed, 36 insertions(+), 14 deletions(-)

I can't build Xen on Arm after this patch:

   AR      lib.a
aarch64-linux-gnu-ld    -EL  -r -o built_in.o
aarch64-linux-gnu-ld: no input files
/home/ANT.AMAZON.COM/jgrall/works/oss/xen/xen/Rules.mk:154: recipe for 
target 'built_in.o' failed

Cheers,

-- 
Julien Grall

Re: [PATCH v2 3/8] lib: move list sorting code

[Julien Grall]

Hi Jan,

On 23/10/2020 11:17, Jan Beulich wrote:
> 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().
> 
> Signed-off-by: Jan Beulich <jbeulich@suse.com>

It looks like the commit message was duplicated.

> 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().

You are mentioning the EXPORT_SYMBOL() but...

> 
> Signed-off-by: Jan Beulich <jbeulich@suse.com>
> ---
>   xen/arch/arm/Kconfig                        | 4 +---
>   xen/common/Kconfig                          | 3 ---
>   xen/common/Makefile                         | 1 -
>   xen/lib/Makefile                            | 1 +
>   xen/{common/list_sort.c => lib/list-sort.c} | 2 --
>   5 files changed, 2 insertions(+), 9 deletions(-)
>   rename xen/{common/list_sort.c => lib/list-sort.c} (98%)
> 
> diff --git a/xen/arch/arm/Kconfig b/xen/arch/arm/Kconfig
> index 277738826581..cb7e2523b6de 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 3e2cf2508899..0661328a99e7 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 083f62acb634..52d3c2aa9384 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/lib/Makefile b/xen/lib/Makefile
> index b8814361d63e..764f3624b5f9 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/common/list_sort.c b/xen/lib/list-sort.c
> similarity index 98%
> rename from xen/common/list_sort.c
> rename to xen/lib/list-sort.c
> index af2b2f6519f1..f8d8bbf28178 100644
> --- a/xen/common/list_sort.c
> +++ b/xen/lib/list-sort.c
> @@ -15,7 +15,6 @@
>    * this program; If not, see <http://www.gnu.org/licenses/>.
>    */
>   
> -#include <xen/lib.h>

... this is not mentionned.

>   #include <xen/list.h>
>   
>   #define MAX_LIST_LENGTH_BITS 20
> @@ -154,4 +153,3 @@ void list_sort(void *priv, struct list_head *head,
>   
>   	merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
>   }
> -EXPORT_SYMBOL(list_sort);
> 

Cheers,

-- 
Julien Grall

Re: [PATCH v2 4/8] lib: move parse_size_and_unit()

[Julien Grall]

Hi Jan,

On 23/10/2020 11:17, Jan Beulich wrote:
> ... into its own CU, to build it into an archive.
> 
> Signed-off-by: Jan Beulich <jbeulich@suse.com>
> 
> ... into its own CU, to build it into an archive.
> 
> Signed-off-by: Jan Beulich <jbeulich@suse.com>

Acked-by: Julien Grall <jgrall@amazon.com>

Cheers,

-- 
Julien Grall

Re: [PATCH v2 5/8] lib: move init_constructors()

[Julien Grall]

Hi Jan,

On 23/10/2020 11:18, Jan Beulich wrote:
> ... into its own CU, for being unrelated to other things in
> common/lib.c. For now it gets compiled into built_in.o rather than
> lib.a, as it gets used unconditionally by Arm's as well as x86'es
> {,__}start_xen(). 

AFAICT, parse_size_and_unit() is also used unconditionally on both 
architectures.

I think we want to follow the same approach everywhere. If there are no 
major downside to build an archive, then we built in everything in lib/ 
in the archives.

Cheers,

-- 
Julien Grall

Re: [PATCH v2 6/8] lib: move rbtree code

[Julien Grall]

Hi Jan,

On 23/10/2020 11:18, Jan Beulich wrote:
> Build this code into an archive, which results in not linking it into
> x86 final binaries. This saves about 1.5k of dead code.
> 
> While moving the source file, take the opportunity and drop the
> pointless EXPORT_SYMBOL().

Given this code is borrowed from Linux, I don't think we want to remove 
them. This is to make easier to re-sync.

> 
> Signed-off-by: Jan Beulich <jbeulich@suse.com>
> ---
>   xen/common/Makefile          | 1 -
>   xen/lib/Makefile             | 1 +
>   xen/{common => lib}/rbtree.c | 9 +--------
>   3 files changed, 2 insertions(+), 9 deletions(-)
>   rename xen/{common => lib}/rbtree.c (98%)
> 
> diff --git a/xen/common/Makefile b/xen/common/Makefile
> index 52d3c2aa9384..7bb779f780a1 100644
> --- a/xen/common/Makefile
> +++ b/xen/common/Makefile
> @@ -33,7 +33,6 @@ obj-y += preempt.o
>   obj-y += random.o
>   obj-y += rangeset.o
>   obj-y += radix-tree.o
> -obj-y += rbtree.o
>   obj-y += rcupdate.o
>   obj-y += rwlock.o
>   obj-y += shutdown.o
> diff --git a/xen/lib/Makefile b/xen/lib/Makefile
> index ba1fb7bcdee2..b469d2dff7b8 100644
> --- a/xen/lib/Makefile
> +++ b/xen/lib/Makefile
> @@ -4,3 +4,4 @@ obj-$(CONFIG_X86) += x86/
>   lib-y += ctype.o
>   lib-y += list-sort.o
>   lib-y += parse-size.o
> +lib-y += rbtree.o
> diff --git a/xen/common/rbtree.c b/xen/lib/rbtree.c
> similarity index 98%
> rename from xen/common/rbtree.c
> rename to xen/lib/rbtree.c
> index 9f5498a89d4e..95e045d52461 100644
> --- a/xen/common/rbtree.c
> +++ b/xen/lib/rbtree.c
> @@ -25,7 +25,7 @@
>   #include <xen/rbtree.h>
>   
>   /*
> - * red-black trees properties:  http://en.wikipedia.org/wiki/Rbtree
> + * red-black trees properties:  http://en.wikipedia.org/wiki/Rbtree

This looks like a spurious change.

>    *
>    *  1) A node is either red or black
>    *  2) The root is black
> @@ -223,7 +223,6 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
>   		}
>   	}
>   }
> -EXPORT_SYMBOL(rb_insert_color);
>   
>   static void __rb_erase_color(struct rb_node *parent, struct rb_root *root)
>   {
> @@ -467,7 +466,6 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
>   	if (rebalance)
>   		__rb_erase_color(rebalance, root);
>   }
> -EXPORT_SYMBOL(rb_erase);
>   
>   /*
>    * This function returns the first node (in sort order) of the tree.
> @@ -483,7 +481,6 @@ struct rb_node *rb_first(const struct rb_root *root)
>   		n = n->rb_left;
>   	return n;
>   }
> -EXPORT_SYMBOL(rb_first);
>   
>   struct rb_node *rb_last(const struct rb_root *root)
>   {
> @@ -496,7 +493,6 @@ struct rb_node *rb_last(const struct rb_root *root)
>   		n = n->rb_right;
>   	return n;
>   }
> -EXPORT_SYMBOL(rb_last);
>   
>   struct rb_node *rb_next(const struct rb_node *node)
>   {
> @@ -528,7 +524,6 @@ struct rb_node *rb_next(const struct rb_node *node)
>   
>   	return parent;
>   }
> -EXPORT_SYMBOL(rb_next);
>   
>   struct rb_node *rb_prev(const struct rb_node *node)
>   {
> @@ -557,7 +552,6 @@ struct rb_node *rb_prev(const struct rb_node *node)
>   
>   	return parent;
>   }
> -EXPORT_SYMBOL(rb_prev);
>   
>   void rb_replace_node(struct rb_node *victim, struct rb_node *new,
>   		     struct rb_root *root)
> @@ -574,4 +568,3 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
>   	/* Copy the pointers/colour from the victim to the replacement */
>   	*new = *victim;
>   }
> -EXPORT_SYMBOL(rb_replace_node);
> 

Cheers,

-- 
Julien Grall

Re: [PATCH v2 4/8] lib: move parse_size_and_unit()

[Julien Grall]

On 18/11/2020 17:39, Julien Grall wrote:
> Hi Jan,
> 
> On 23/10/2020 11:17, Jan Beulich wrote:
>> ... into its own CU, to build it into an archive.
>>
>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>>

I forgot to mention the commit message was duplicated.

>> ... into its own CU, to build it into an archive.
>>
>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
> 
> Acked-by: Julien Grall <jgrall@amazon.com>
> 
> Cheers,
> 

-- 
Julien Grall

Re: [PATCH v2 7/8] lib: move bsearch code

[Julien Grall]

Hi Jan,

On 23/10/2020 11:19, Jan Beulich wrote:
> Convert this code to an inline function (backed by an instance in an
> archive in case the compiler decides against inlining), which results
> in not having it in x86 final binaries. This saves a little bit of dead
> code.
> 
> Signed-off-by: Jan Beulich <jbeulich@suse.com>
> ---
> v2: Make the function an extern inline in its header.
> ---
>   xen/common/Makefile        |  1 -
>   xen/common/bsearch.c       | 51 --------------------------------------
>   xen/include/xen/compiler.h |  1 +
>   xen/include/xen/lib.h      | 42 ++++++++++++++++++++++++++++++-
>   xen/lib/Makefile           |  1 +
>   xen/lib/bsearch.c          | 13 ++++++++++
>   6 files changed, 56 insertions(+), 53 deletions(-)
>   delete mode 100644 xen/common/bsearch.c
>   create mode 100644 xen/lib/bsearch.c
> 
> diff --git a/xen/common/Makefile b/xen/common/Makefile
> index 7bb779f780a1..d8519a2cc163 100644
> --- a/xen/common/Makefile
> +++ b/xen/common/Makefile
> @@ -1,6 +1,5 @@
>   obj-$(CONFIG_ARGO) += argo.o
>   obj-y += bitmap.o
> -obj-y += bsearch.o
>   obj-$(CONFIG_HYPFS_CONFIG) += config_data.o
>   obj-$(CONFIG_CORE_PARKING) += core_parking.o
>   obj-y += cpu.o
> diff --git a/xen/common/bsearch.c b/xen/common/bsearch.c
> deleted file mode 100644
> index 7090930aab5c..000000000000
> --- a/xen/common/bsearch.c
> +++ /dev/null
> @@ -1,51 +0,0 @@
> -/*
> - * A generic implementation of binary search for the Linux kernel
> - *
> - * Copyright (C) 2008-2009 Ksplice, Inc.
> - * Author: Tim Abbott <tabbott@ksplice.com>
> - *
> - * This program is free software; you can redistribute it and/or
> - * modify it under the terms of the GNU General Public License as
> - * published by the Free Software Foundation; version 2.
> - */
> -
> -#include <xen/lib.h>
> -
> -/*
> - * bsearch - binary search an array of elements
> - * @key: pointer to item being searched for
> - * @base: pointer to first element to search
> - * @num: number of elements
> - * @size: size of each element
> - * @cmp: pointer to comparison function
> - *
> - * This function does a binary search on the given array.  The
> - * contents of the array should already be in ascending sorted order
> - * under the provided comparison function.
> - *
> - * Note that the key need not have the same type as the elements in
> - * the array, e.g. key could be a string and the comparison function
> - * could compare the string with the struct's name field.  However, if
> - * the key and elements in the array are of the same type, you can use
> - * the same comparison function for both sort() and bsearch().
> - */
> -void *bsearch(const void *key, const void *base, size_t num, size_t size,
> -	      int (*cmp)(const void *key, const void *elt))
> -{
> -	size_t start = 0, end = num;
> -	int result;
> -
> -	while (start < end) {
> -		size_t mid = start + (end - start) / 2;
> -
> -		result = cmp(key, base + mid * size);
> -		if (result < 0)
> -			end = mid;
> -		else if (result > 0)
> -			start = mid + 1;
> -		else
> -			return (void *)base + mid * size;
> -	}
> -
> -	return NULL;
> -}
> diff --git a/xen/include/xen/compiler.h b/xen/include/xen/compiler.h
> index c0e0ee9f27be..2b7acdf3b188 100644
> --- a/xen/include/xen/compiler.h
> +++ b/xen/include/xen/compiler.h
> @@ -12,6 +12,7 @@
>   
>   #define inline        __inline__
>   #define always_inline __inline__ __attribute__ ((__always_inline__))
> +#define gnu_inline    __inline__ __attribute__ ((__gnu_inline__))

bsearch() is only used by Arm and I haven't seen anyone so far 
complaining about the perf of I/O emulation.

Therefore, I am not convinced that there is enough justification to 
introduce a GNU attribute just for this patch.

Cheers,

-- 
Julien Grall

Re: [PATCH v2 8/8] lib: move sort code

[Julien Grall]

Hi Jan,

On 23/10/2020 11:19, Jan Beulich wrote:
> Build this code into an archive, partly paralleling bsearch().
> 
> Signed-off-by: Jan Beulich <jbeulich@suse.com>

Acked-by: Julien Grall <jgrall@amazon.com>

Cheers,

-- 
Julien Grall

Re: [PATCH v2 3/8] lib: move list sorting code

[Jan Beulich]

On 18.11.2020 18:38, Julien Grall wrote:
> On 23/10/2020 11:17, Jan Beulich wrote:
>> 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().
>>
>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
> 
> It looks like the commit message was duplicated.

Indeed - no idea how it has happened (also in at least one other
patch in this series, as I've noticed now).

>> 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().
> 
> You are mentioning the EXPORT_SYMBOL() but...
[...]
>> --- a/xen/common/list_sort.c
>> +++ b/xen/lib/list-sort.c
>> @@ -15,7 +15,6 @@
>>    * this program; If not, see <http://www.gnu.org/licenses/>.
>>    */
>>   
>> -#include <xen/lib.h>
> 
> ... this is not mentionned.

Well, not sure what to say. But anyway, I've added half a sentence
to also mention this.

Jan

Re: [PATCH v2 2/8] lib: collect library files in an archive

[Jan Beulich]

On 18.11.2020 18:06, Julien Grall wrote:
> On 23/10/2020 11:17, Jan Beulich wrote:
>> In order to (subsequently) drop odd things like CONFIG_NEEDS_LIST_SORT
>> just to avoid bloating binaries when only some arch-es and/or
>> configurations need generic library routines, combine objects under lib/
>> into an archive, which the linker then can pick the necessary objects
>> out of.
>>
>> Note that we can't use thin archives just yet, until we've raised the
>> minimum required binutils version suitably.
>>
>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>> ---
>>   xen/Rules.mk          | 33 +++++++++++++++++++++++++++------
>>   xen/arch/arm/Makefile |  6 +++---
>>   xen/arch/x86/Makefile |  8 ++++----
>>   xen/lib/Makefile      |  3 ++-
> 
> IIRC, Anthony worked on the build systems. If I am right, it would be 
> good to get a review from him.

I'll try to remember next time round.

>> --- a/xen/lib/Makefile
>> +++ b/xen/lib/Makefile
>> @@ -1,2 +1,3 @@
>> -obj-y += ctype.o
>>   obj-$(CONFIG_X86) += x86/
>> +
>> +lib-y += ctype.o
> 
> May I ask why all the code movement by ctype was done after this patch?

I'm sorry, but I'm afraid I don't understand the question.

Jan

Re: [PATCH v2 6/8] lib: move rbtree code

[Jan Beulich]

On 18.11.2020 18:46, Julien Grall wrote:
> On 23/10/2020 11:18, Jan Beulich wrote:
>> Build this code into an archive, which results in not linking it into
>> x86 final binaries. This saves about 1.5k of dead code.
>>
>> While moving the source file, take the opportunity and drop the
>> pointless EXPORT_SYMBOL().
> 
> Given this code is borrowed from Linux, I don't think we want to remove 
> them. This is to make easier to re-sync.

That's one view on it. My view is that we should get rid of
EXPORT_SYMBOL altogether (and it is a good opportunity to do so
here). Not the least because otherwise for future cloning of Linux
code we may then need to introduce further variants of this
construct for no real purpose.

>> --- a/xen/common/rbtree.c
>> +++ b/xen/lib/rbtree.c
>> @@ -25,7 +25,7 @@
>>   #include <xen/rbtree.h>
>>   
>>   /*
>> - * red-black trees properties:  http://en.wikipedia.org/wiki/Rbtree
>> + * red-black trees properties:  http://en.wikipedia.org/wiki/Rbtree
> 
> This looks like a spurious change.

Not really, no - while not visible here anymore, it's correcting an
instance of trailing whitespace. Following your request on an
earlier patch, I've also added half a sentence to the description
here to mention this entirely benign change.

Jan

Re: [PATCH v2 7/8] lib: move bsearch code

[Jan Beulich]

On 18.11.2020 19:09, Julien Grall wrote:
> On 23/10/2020 11:19, Jan Beulich wrote:
>> --- a/xen/include/xen/compiler.h
>> +++ b/xen/include/xen/compiler.h
>> @@ -12,6 +12,7 @@
>>   
>>   #define inline        __inline__
>>   #define always_inline __inline__ __attribute__ ((__always_inline__))
>> +#define gnu_inline    __inline__ __attribute__ ((__gnu_inline__))
> 
> bsearch() is only used by Arm and I haven't seen anyone so far 
> complaining about the perf of I/O emulation.
> 
> Therefore, I am not convinced that there is enough justification to 
> introduce a GNU attribute just for this patch.

Please settle this with Andrew: He had asked for the function to
become inline. I don't view making it static inline in the header
as an option here - if the compiler decides to not inline it, we
should not end up with multiple instances in different CUs. And
without making it static inline the attribute needs adding; at
least I'm unaware of an alternative which works with the various
compiler versions.

Jan

Re: [PATCH v2 2/8] lib: collect library files in an archive

[Jan Beulich]

On 18.11.2020 18:31, Julien Grall wrote:
> On 23/10/2020 11:17, Jan Beulich wrote:
>> In order to (subsequently) drop odd things like CONFIG_NEEDS_LIST_SORT
>> just to avoid bloating binaries when only some arch-es and/or
>> configurations need generic library routines, combine objects under lib/
>> into an archive, which the linker then can pick the necessary objects
>> out of.
>>
>> Note that we can't use thin archives just yet, until we've raised the
>> minimum required binutils version suitably.
>>
>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>> ---
>>   xen/Rules.mk          | 33 +++++++++++++++++++++++++++------
>>   xen/arch/arm/Makefile |  6 +++---
>>   xen/arch/x86/Makefile |  8 ++++----
>>   xen/lib/Makefile      |  3 ++-
>>   4 files changed, 36 insertions(+), 14 deletions(-)
> 
> I can't build Xen on Arm after this patch:
> 
>    AR      lib.a
> aarch64-linux-gnu-ld    -EL  -r -o built_in.o
> aarch64-linux-gnu-ld: no input files
> /home/ANT.AMAZON.COM/jgrall/works/oss/xen/xen/Rules.mk:154: recipe for 
> target 'built_in.o' failed

Oh, indeed, this triggers a pre-existing bug. I didn't notice it
because for Arm I build-tested only the series as a whole. Will
add a fix for the issue as prereq patch.

Thanks for noticing,
Jan

Re: [PATCH v2 7/8] lib: move bsearch code

[Julien Grall]

Hi Jan,

On 19/11/2020 10:27, Jan Beulich wrote:
> On 18.11.2020 19:09, Julien Grall wrote:
>> On 23/10/2020 11:19, Jan Beulich wrote:
>>> --- a/xen/include/xen/compiler.h
>>> +++ b/xen/include/xen/compiler.h
>>> @@ -12,6 +12,7 @@
>>>    
>>>    #define inline        __inline__
>>>    #define always_inline __inline__ __attribute__ ((__always_inline__))
>>> +#define gnu_inline    __inline__ __attribute__ ((__gnu_inline__))
>>
>> bsearch() is only used by Arm and I haven't seen anyone so far
>> complaining about the perf of I/O emulation.
>>
>> Therefore, I am not convinced that there is enough justification to
>> introduce a GNU attribute just for this patch.
> 
> Please settle this with Andrew: He had asked for the function to
> become inline. I don't view making it static inline in the header
> as an option here - if the compiler decides to not inline it, we
> should not end up with multiple instances in different CUs.

That's the cons of static inline... but then why is it suddenly a 
problem with this helper?

> And
> without making it static inline the attribute needs adding; at
> least I'm unaware of an alternative which works with the various
> compiler versions.

The question we have to answer is: What is the gain with this approach?

If it is not quantifiable, then introducing compiler specific attribute 
is not an option.

IIRC, there are only two callers (all in Arm code) of this function. 
Even inlined, I don't believe you would drastically reduce the number of 
instructions compare to a full blown version. To be generous, I would 
say you may save ~20 instructions per copy.

Therefore, so far, the compiler specific attribute doesn't look 
justified to me. As usual, I am happy to be proven wrong.

Cheers,

-- 
Julien Grall

Re: [PATCH v2 7/8] lib: move bsearch code

[Andrew Cooper]

On 23/11/2020 22:49, Julien Grall wrote:
> Hi Jan,
>
> On 19/11/2020 10:27, Jan Beulich wrote:
>> On 18.11.2020 19:09, Julien Grall wrote:
>>> On 23/10/2020 11:19, Jan Beulich wrote:
>>>> --- a/xen/include/xen/compiler.h
>>>> +++ b/xen/include/xen/compiler.h
>>>> @@ -12,6 +12,7 @@
>>>>       #define inline        __inline__
>>>>    #define always_inline __inline__ __attribute__
>>>> ((__always_inline__))
>>>> +#define gnu_inline    __inline__ __attribute__ ((__gnu_inline__))
>>>
>>> bsearch() is only used by Arm and I haven't seen anyone so far
>>> complaining about the perf of I/O emulation.
>>>
>>> Therefore, I am not convinced that there is enough justification to
>>> introduce a GNU attribute just for this patch.
>>
>> Please settle this with Andrew: He had asked for the function to
>> become inline. I don't view making it static inline in the header
>> as an option here - if the compiler decides to not inline it, we
>> should not end up with multiple instances in different CUs.
>
> That's the cons of static inline... but then why is it suddenly a
> problem with this helper?
>
>> And
>> without making it static inline the attribute needs adding; at
>> least I'm unaware of an alternative which works with the various
>> compiler versions.
>
> The question we have to answer is: What is the gain with this approach?

Substantial.

>
> If it is not quantifiable, then introducing compiler specific
> attribute is not an option.
>
> IIRC, there are only two callers (all in Arm code) of this function.
> Even inlined, I don't believe you would drastically reduce the number
> of instructions compare to a full blown version. To be generous, I
> would say you may save ~20 instructions per copy.
>
> Therefore, so far, the compiler specific attribute doesn't look
> justified to me. As usual, I am happy to be proven wrong

There is a very good reason why this is the classic example used for
extern inline's in various libc's.

The gains are from the compiler being able to optimise away the function
pointer(s) entirely.  Instead of working on opaque objects, it can see
the accesses directly, implement compares as straight array reads, (for
sorting, the swap() call turns into memcpy()) and because it can see all
the memory accesses, doesn't have to assume that every call to cmp()
modifies arbitrary data in the array (i.e. doesn't have to reload the
objects from memory every iteration).

extern inline allows the compiler full flexibility to judge whether
inlining is a net win, based on optimisation settings and observing what
the practical memory access pattern would be from not inlining.

extern inline is the appropriate thing to use here, except for the big
note in the GCC manual saying "always use gnu_inline in this case" which
appears to be working around a change in the C99 standard which forces
any non-static inline to emit a body even when its not called, due to
rules about global symbols.

Therefore, Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>

Some further observations:

For arch/arm/io.c, the handlers are sorted, so find_mmio_handler() will
be O(lg n), but it will surely be faster with the inlined version, and
this is the fastpath.

register_mmio_handler() OTOH is massively expensive, because sort()
turns the array into a heap and back into an array on every insertion,
just to insert an entry into an already sorted array.  It would be more
efficient to library-fy the work I did for VT-x MSR load/save lists
(again, extern inline) and reuse
"insert_$FOO_into_sorted_list_of_FOOs()" which is a search, single
memmove() to make a gap, and a memcpy() into place.

When you compile io.c with this patch in place, the delta is:

add/remove: 0/1 grow/shrink: 1/0 up/down: 92/-164 (-72)
Function                                     old     new   delta
try_handle_mmio                              720     812     +92
bsearch                                      164       -    -164
Total: Before=992489, After=992417, chg -0.01%

The reason cmp_mmio_handler (140 bytes) doesn't drop out is because it
is referenced by register_mmio_hanlder()'s call to sort().  All in all,
the inlined version is less than 1/3 the size of the out-of-lined
version, but I haven't characterised it further than that.


On a totally separate point,  I wonder if we'd be better off compiling
with -fgnu89-inline because I can't see any case we're we'd want the C99
inline semantics anywhere in Xen.

~Andrew

Re: [PATCH v2 4/8] lib: move parse_size_and_unit()

[Andrew Cooper]

On 23/10/2020 11:17, Jan Beulich wrote:
> ... into its own CU, to build it into an archive.
>
> Signed-off-by: Jan Beulich <jbeulich@suse.com>
> ---
>  xen/common/lib.c     | 39 ----------------------------------
>  xen/lib/Makefile     |  1 +
>  xen/lib/parse-size.c | 50 ++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 51 insertions(+), 39 deletions(-)
>  create mode 100644 xen/lib/parse-size.c

What is the point of turning this into a library?  It isn't a leaf
function (calls simple_strtoull()) and doesn't have any any plausible
way of losing all its callers in various configurations (given its
direct use by the cmdline parsing logic).

~Andrew

Re: [PATCH v2 4/8] lib: move parse_size_and_unit()

[Jan Beulich]

On 24.11.2020 01:58, Andrew Cooper wrote:
> On 23/10/2020 11:17, Jan Beulich wrote:
>> ... into its own CU, to build it into an archive.
>>
>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>> ---
>>  xen/common/lib.c     | 39 ----------------------------------
>>  xen/lib/Makefile     |  1 +
>>  xen/lib/parse-size.c | 50 ++++++++++++++++++++++++++++++++++++++++++++
>>  3 files changed, 51 insertions(+), 39 deletions(-)
>>  create mode 100644 xen/lib/parse-size.c
> 
> What is the point of turning this into a library?  It isn't a leaf
> function (calls simple_strtoull()) and doesn't have any any plausible
> way of losing all its callers in various configurations (given its
> direct use by the cmdline parsing logic).

It's still a library function. As said earlier, I think _all_
of what's now in lib.c should move to lib/. That's how it
should have been from the beginning, or stuff shouldn't have
been put in lib.c.

The one alternative I see is to move the code next to
parse_bool() / parse_boolean(), in kernel.c, or put all
parse_*() into a new common/parse.c.

Jan

Re: [PATCH v2 7/8] lib: move bsearch code

[Jan Beulich]

On 24.11.2020 01:40, Andrew Cooper wrote:
> On 23/11/2020 22:49, Julien Grall wrote:
>> On 19/11/2020 10:27, Jan Beulich wrote:
>>> On 18.11.2020 19:09, Julien Grall wrote:
>>>> On 23/10/2020 11:19, Jan Beulich wrote:
>>>>> --- a/xen/include/xen/compiler.h
>>>>> +++ b/xen/include/xen/compiler.h
>>>>> @@ -12,6 +12,7 @@
>>>>>       #define inline        __inline__
>>>>>    #define always_inline __inline__ __attribute__
>>>>> ((__always_inline__))
>>>>> +#define gnu_inline    __inline__ __attribute__ ((__gnu_inline__))
>>>>
>>>> bsearch() is only used by Arm and I haven't seen anyone so far
>>>> complaining about the perf of I/O emulation.
>>>>
>>>> Therefore, I am not convinced that there is enough justification to
>>>> introduce a GNU attribute just for this patch.
>>>
>>> Please settle this with Andrew: He had asked for the function to
>>> become inline. I don't view making it static inline in the header
>>> as an option here - if the compiler decides to not inline it, we
>>> should not end up with multiple instances in different CUs.
>>
>> That's the cons of static inline... but then why is it suddenly a
>> problem with this helper?
>>
>>> And
>>> without making it static inline the attribute needs adding; at
>>> least I'm unaware of an alternative which works with the various
>>> compiler versions.
>>
>> The question we have to answer is: What is the gain with this approach?
> 
> Substantial.
> 
>>
>> If it is not quantifiable, then introducing compiler specific
>> attribute is not an option.
>>
>> IIRC, there are only two callers (all in Arm code) of this function.
>> Even inlined, I don't believe you would drastically reduce the number
>> of instructions compare to a full blown version. To be generous, I
>> would say you may save ~20 instructions per copy.
>>
>> Therefore, so far, the compiler specific attribute doesn't look
>> justified to me. As usual, I am happy to be proven wrong
> 
> There is a very good reason why this is the classic example used for
> extern inline's in various libc's.
> 
> The gains are from the compiler being able to optimise away the function
> pointer(s) entirely.  Instead of working on opaque objects, it can see
> the accesses directly, implement compares as straight array reads, (for
> sorting, the swap() call turns into memcpy()) and because it can see all
> the memory accesses, doesn't have to assume that every call to cmp()
> modifies arbitrary data in the array (i.e. doesn't have to reload the
> objects from memory every iteration).
> 
> extern inline allows the compiler full flexibility to judge whether
> inlining is a net win, based on optimisation settings and observing what
> the practical memory access pattern would be from not inlining.
> 
> extern inline is the appropriate thing to use here, except for the big
> note in the GCC manual saying "always use gnu_inline in this case" which
> appears to be working around a change in the C99 standard which forces
> any non-static inline to emit a body even when its not called, due to
> rules about global symbols.
> 
> Therefore, Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>

Thanks Andrew.

Julien - please clarify whether you're okay with Andrew's response,
or whether you continue to object the conversion to inline.

> On a totally separate point,  I wonder if we'd be better off compiling
> with -fgnu89-inline because I can't see any case we're we'd want the C99
> inline semantics anywhere in Xen.

I'm not sure about this, i.e. I wouldn't want to exclude such a
case appearing. I think using attributes is better in general, as
it allows fine grained control.

Jan

Re: [PATCH v2 7/8] lib: move bsearch code

[Julien Grall]

Hi Andrew,

Thank you for the detailed explanation :).

On 24/11/2020 00:40, Andrew Cooper wrote:
> On 23/11/2020 22:49, Julien Grall wrote:
>> Hi Jan,
>>
>> On 19/11/2020 10:27, Jan Beulich wrote:
>>> On 18.11.2020 19:09, Julien Grall wrote:
>>>> On 23/10/2020 11:19, Jan Beulich wrote:
>>>>> --- a/xen/include/xen/compiler.h
>>>>> +++ b/xen/include/xen/compiler.h
>>>>> @@ -12,6 +12,7 @@
>>>>>        #define inline        __inline__
>>>>>     #define always_inline __inline__ __attribute__
>>>>> ((__always_inline__))
>>>>> +#define gnu_inline    __inline__ __attribute__ ((__gnu_inline__))
>>>>
>>>> bsearch() is only used by Arm and I haven't seen anyone so far
>>>> complaining about the perf of I/O emulation.
>>>>
>>>> Therefore, I am not convinced that there is enough justification to
>>>> introduce a GNU attribute just for this patch.
>>>
>>> Please settle this with Andrew: He had asked for the function to
>>> become inline. I don't view making it static inline in the header
>>> as an option here - if the compiler decides to not inline it, we
>>> should not end up with multiple instances in different CUs.
>>
>> That's the cons of static inline... but then why is it suddenly a
>> problem with this helper?
>>
>>> And
>>> without making it static inline the attribute needs adding; at
>>> least I'm unaware of an alternative which works with the various
>>> compiler versions.
>>
>> The question we have to answer is: What is the gain with this approach?
> 
> Substantial.
> 
>>
>> If it is not quantifiable, then introducing compiler specific
>> attribute is not an option.
>>
>> IIRC, there are only two callers (all in Arm code) of this function.
>> Even inlined, I don't believe you would drastically reduce the number
>> of instructions compare to a full blown version. To be generous, I
>> would say you may save ~20 instructions per copy.
>>
>> Therefore, so far, the compiler specific attribute doesn't look
>> justified to me. As usual, I am happy to be proven wrong
> 
> There is a very good reason why this is the classic example used for
> extern inline's in various libc's.
> 
> The gains are from the compiler being able to optimise away the function
> pointer(s) entirely.  Instead of working on opaque objects, it can see
> the accesses directly, implement compares as straight array reads, (for
> sorting, the swap() call turns into memcpy()) and because it can see all
> the memory accesses, doesn't have to assume that every call to cmp()
> modifies arbitrary data in the array (i.e. doesn't have to reload the
> objects from memory every iteration).
> 
> extern inline allows the compiler full flexibility to judge whether
> inlining is a net win, based on optimisation settings and observing what
> the practical memory access pattern would be from not inlining.
> 
> extern inline is the appropriate thing to use here, except for the big
> note in the GCC manual saying "always use gnu_inline in this case" which
> appears to be working around a change in the C99 standard which forces
> any non-static inline to emit a body even when its not called, due to
> rules about global symbols.
> 
> Therefore, Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>
> 
> Some further observations:
> 
> For arch/arm/io.c, the handlers are sorted, so find_mmio_handler() will
> be O(lg n), but it will surely be faster with the inlined version, and
> this is the fastpath.
> 
> register_mmio_handler() OTOH is massively expensive, because sort()
> turns the array into a heap and back into an array on every insertion,
> just to insert an entry into an already sorted array.  It would be more
> efficient to library-fy the work I did for VT-x MSR load/save lists
> (again, extern inline) and reuse
> "insert_$FOO_into_sorted_list_of_FOOs()" which is a search, single
> memmove() to make a gap, and a memcpy() into place.
> 
> When you compile io.c with this patch in place, the delta is:
> 
> add/remove: 0/1 grow/shrink: 1/0 up/down: 92/-164 (-72)
> Function                                     old     new   delta
> try_handle_mmio                              720     812     +92
> bsearch                                      164       -    -164
> Total: Before=992489, After=992417, chg -0.01%
> 
> The reason cmp_mmio_handler (140 bytes) doesn't drop out is because it
> is referenced by register_mmio_hanlder()'s call to sort().  All in all,
> the inlined version is less than 1/3 the size of the out-of-lined
> version, but I haven't characterised it further than that.
> 
> 
> On a totally separate point,  I wonder if we'd be better off compiling
> with -fgnu89-inline because I can't see any case we're we'd want the C99
> inline semantics anywhere in Xen.

This was one of my point above. It feels that if we want to use the 
behavior in Xen, then it should be everywhere rather than just this helper.

Cheers,

-- 
Julien Grall

Re: [PATCH v2 7/8] lib: move bsearch code

[Jan Beulich]

On 24.11.2020 17:57, Julien Grall wrote:
> On 24/11/2020 00:40, Andrew Cooper wrote:
>> On a totally separate point,  I wonder if we'd be better off compiling
>> with -fgnu89-inline because I can't see any case we're we'd want the C99
>> inline semantics anywhere in Xen.
> 
> This was one of my point above. It feels that if we want to use the 
> behavior in Xen, then it should be everywhere rather than just this helper.

I'll be committing the series up to patch 6 in a minute. It remains
unclear to me whether your responses on this sub-thread are meant
to be an objection, or just a comment. Andrew gave his R-b despite
this separate consideration, and I now also have an ack from Wei
for the entire series. Please clarify.

Or actually I only thought I could commit a fair initial part of
the series - I'm still lacking Arm-side acks for patches 2 and 3
here.

Jan

Re: [PATCH v2 7/8] lib: move bsearch code

[Julien Grall]

Hi Jan,

On 07/12/2020 10:23, Jan Beulich wrote:
> On 24.11.2020 17:57, Julien Grall wrote:
>> On 24/11/2020 00:40, Andrew Cooper wrote:
>>> On a totally separate point,  I wonder if we'd be better off compiling
>>> with -fgnu89-inline because I can't see any case we're we'd want the C99
>>> inline semantics anywhere in Xen.
>>
>> This was one of my point above. It feels that if we want to use the
>> behavior in Xen, then it should be everywhere rather than just this helper.
> 
> I'll be committing the series up to patch 6 in a minute. It remains
> unclear to me whether your responses on this sub-thread are meant
> to be an objection, or just a comment. Andrew gave his R-b despite
> this separate consideration, and I now also have an ack from Wei
> for the entire series. Please clarify.

It still feels strange to apply to one function and not the others... 
But I don't have a strong objection against the idea of using C99 
inlines in Xen.

IOW, I will neither Ack nor NAck this patch.

> 
> Or actually I only thought I could commit a fair initial part of
> the series - I'm still lacking Arm-side acks for patches 2 and 3
> here.

If you remember, I have asked if Anthony could review the build system 
because he worked on it recently.

Unfortunately, I haven't seen any answer so far... I have pinged him on IRC.

Cheers,

-- 
Julien Grall

Re: [PATCH v2 7/8] lib: move bsearch code

[Bertrand Marquis]

Hi Jan,

> On 9 Dec 2020, at 09:41, Julien Grall <julien@xen.org> wrote:
> 
> Hi Jan,
> 
> On 07/12/2020 10:23, Jan Beulich wrote:
>> On 24.11.2020 17:57, Julien Grall wrote:
>>> On 24/11/2020 00:40, Andrew Cooper wrote:
>>>> On a totally separate point,  I wonder if we'd be better off compiling
>>>> with -fgnu89-inline because I can't see any case we're we'd want the C99
>>>> inline semantics anywhere in Xen.
>>> 
>>> This was one of my point above. It feels that if we want to use the
>>> behavior in Xen, then it should be everywhere rather than just this helper.
>> I'll be committing the series up to patch 6 in a minute. It remains
>> unclear to me whether your responses on this sub-thread are meant
>> to be an objection, or just a comment. Andrew gave his R-b despite
>> this separate consideration, and I now also have an ack from Wei
>> for the entire series. Please clarify.
> 
> It still feels strange to apply to one function and not the others... But I don't have a strong objection against the idea of using C99 inlines in Xen.
> 
> IOW, I will neither Ack nor NAck this patch.

I think as Julien here: why doing this inline thing for this function and not the others
provided by the library ?
Could you explain the reasons for this or the use cases you expect ?

I see 2 usage of bsearch in arm code and I do not get why you are doing this for
bsearch and not for the other functions.

Regards
Bertrand

> 
>> Or actually I only thought I could commit a fair initial part of
>> the series - I'm still lacking Arm-side acks for patches 2 and 3
>> here.
> 
> If you remember, I have asked if Anthony could review the build system because he worked on it recently.
> 
> Unfortunately, I haven't seen any answer so far... I have pinged him on IRC.
> 
> Cheers,
> 
> -- 
> Julien Grall
> 

Re: [PATCH v2 7/8] lib: move bsearch code

[Jan Beulich]

On 09.12.2020 15:27, Bertrand Marquis wrote:
>> On 9 Dec 2020, at 09:41, Julien Grall <julien@xen.org> wrote:
>> On 07/12/2020 10:23, Jan Beulich wrote:
>>> On 24.11.2020 17:57, Julien Grall wrote:
>>>> On 24/11/2020 00:40, Andrew Cooper wrote:
>>>>> On a totally separate point,  I wonder if we'd be better off compiling
>>>>> with -fgnu89-inline because I can't see any case we're we'd want the C99
>>>>> inline semantics anywhere in Xen.
>>>>
>>>> This was one of my point above. It feels that if we want to use the
>>>> behavior in Xen, then it should be everywhere rather than just this helper.
>>> I'll be committing the series up to patch 6 in a minute. It remains
>>> unclear to me whether your responses on this sub-thread are meant
>>> to be an objection, or just a comment. Andrew gave his R-b despite
>>> this separate consideration, and I now also have an ack from Wei
>>> for the entire series. Please clarify.
>>
>> It still feels strange to apply to one function and not the others... But I don't have a strong objection against the idea of using C99 inlines in Xen.
>>
>> IOW, I will neither Ack nor NAck this patch.
> 
> I think as Julien here: why doing this inline thing for this function and not the others
> provided by the library ?
> Could you explain the reasons for this or the use cases you expect ?
> 
> I see 2 usage of bsearch in arm code and I do not get why you are doing this for
> bsearch and not for the other functions.

May I ask whether you read Andrew's quite exhaustive reply to Julien
asking about this? Apart from this, it was Andrew who had asked to
inline bsearch(), and I followed that request. The initial version
of this series didn't have any inlining of these library functions
(which, after all, also isn't the goal of the series).

Jan

Re: [PATCH v2 7/8] lib: move bsearch code

[Bertrand Marquis]

Hi Jan,

> On 9 Dec 2020, at 14:54, Jan Beulich <jbeulich@suse.com> wrote:
> 
> On 09.12.2020 15:27, Bertrand Marquis wrote:
>>> On 9 Dec 2020, at 09:41, Julien Grall <julien@xen.org> wrote:
>>> On 07/12/2020 10:23, Jan Beulich wrote:
>>>> On 24.11.2020 17:57, Julien Grall wrote:
>>>>> On 24/11/2020 00:40, Andrew Cooper wrote:
>>>>>> On a totally separate point,  I wonder if we'd be better off compiling
>>>>>> with -fgnu89-inline because I can't see any case we're we'd want the C99
>>>>>> inline semantics anywhere in Xen.
>>>>> 
>>>>> This was one of my point above. It feels that if we want to use the
>>>>> behavior in Xen, then it should be everywhere rather than just this helper.
>>>> I'll be committing the series up to patch 6 in a minute. It remains
>>>> unclear to me whether your responses on this sub-thread are meant
>>>> to be an objection, or just a comment. Andrew gave his R-b despite
>>>> this separate consideration, and I now also have an ack from Wei
>>>> for the entire series. Please clarify.
>>> 
>>> It still feels strange to apply to one function and not the others... But I don't have a strong objection against the idea of using C99 inlines in Xen.
>>> 
>>> IOW, I will neither Ack nor NAck this patch.
>> 
>> I think as Julien here: why doing this inline thing for this function and not the others
>> provided by the library ?
>> Could you explain the reasons for this or the use cases you expect ?
>> 
>> I see 2 usage of bsearch in arm code and I do not get why you are doing this for
>> bsearch and not for the other functions.
> 
> May I ask whether you read Andrew's quite exhaustive reply to Julien
> asking about this? Apart from this, it was Andrew who had asked to
> inline bsearch(), and I followed that request. The initial version
> of this series didn't have any inlining of these library functions
> (which, after all, also isn't the goal of the series).

I just did (sorry missed that one in the history).

But seeing where this is called and the look of the code with this
change i do not really think that the complexity introduced by this
will make a real win in terms of performance/code size but it does
make this complex.

So I would rather have the inline part out but the code is right:
Reviewed-by: Bertrand Marquis <bertrand.marquis@arm.com>

so that this is unblocked.
Regards
Bertrand

> 
> Jan