livepatch: patch creation tooling proposal

Here's what I've been working on in preparation for my talk about "livepatch module creation tooling" at next week's Linux Plumbers Conference. I'm posting this code now as a sneak preview. Hopefully we can get the conversation started here, as the microconference agenda is packed and there might not be that much time for discussion.

Other than the consistency model, our last big missing piece for live patching is the tooling for creating patch modules.

In kpatch-land, we have kpatch-build:

https://github.com/dynup/kpatch/tree/master/kpatch-build

I wrote the original version of kpatch-build almost three years ago. It has been made much better since then, thanks to many improvements (and rewrites) from Seth, Jessica, and others. It's rather "magical". It takes a source code patch and spits out a patch module. It works by building the kernel twice: once without the patch and once with it. It then does a binary diff of the two kernels, and extracts that difference into the patch module, at a function granularity. It's a very powerful tool, and it's very easy to use, when it works.

But maintenance of kpatch-build can be a nightmare. It needs to have intimate knowledge of many gcc and kernel quirks. When one of those quirks change, the tool breaks. Not to mention all the bugs we already know about today (for example, see the issues on github). And porting it to other arches is going to be really hard, since each arch has its own set of quirks.

So while kpatch-build is powerful and easy to use, I get the feeling that it's just too complex to be reasonably sustainable. We need something simpler.

Today we *do* have something simpler upstream, but it's *too* simple. The existing kernel build infrastructure can be used to build livepatch modules pretty much like any other out-of-tree kernel module. See the sample in samples/livepatch. But it can't deal with relocations of local or unexported symbols.

So here's my proposal: use the existing kernel build infrastructure. If klp relocations are needed, manually specify them with a new klp_module_reloc struct and corresponding KLP_MODULE_RELOC macro. Then run a post-processing tool called klp-convert which converts those klp_module_reloc structs into the sections, relocations, and symbols needed by the klp runtime code.

See patch 2/2 to see what a patch's module source code would look like.

Note this is somewhat harder to use than kpatch-build, because you have to copy/paste the replacement function into the source file for your livepatch module. And then you have to determine if the new function needs any local or unexported symbols, and then specify those missing symbols with the KLP_MODULE_RELOC macro.

With this patch set, figuring out the missing symbols is relatively
easy: build the patch without the livepatch modinfo, and the linker warnings will tell you what's missing. Or alternatively, try to load the module and it should tell you the unresolved symbols and then fail to load.

We can probably add more tooling to make that easier. But anyway I think it won't be too bad if we document the process. The patch creation process doesn't need to be *too* easy: the patch author already needs to be very careful regardless.

For kGraft, what tooling do you guys use for patch creation? I seem to remember several approaches being mentioned -- one of them similar to what I'm proposing here, I believe -- but I don't know what you ended up with. Maybe you're already doing something like this?

In any case it would be good to hear everyone's opinions about this approach. This code is functional, but it's a work in progress, so don't review it *too* closely. Just wondering what people think about the general idea.

NOTE: There's still a big missing piece here: how to support the new .klp.arch.objname..altinstructions/.parainstructions sections. Specifically, when parsing the entries in an .altinstructions section, how can klp-convert determine which object a given entry belongs to?

One solution would be to replace the explicit klp_register_patch() interface with a more implicit special section based interface. For example, the klp_funcs/objects could be placed in a special section which is recognized by the module loader.

Then klp-convert would then be able to tell which object a given function belongs to, and could use that information to determine which object a given .altinstruction entry belongs to, and then move the entry to the appropriate .klp.arch section.

TODO:
- support .klp.arch.objname..altinstructions/parainstructions
- split up the patches better
- patch creation documentation
- more tooling support for detecting missing relocations? or automatically converting them if a sympos isn't needed?

Josh Poimboeuf (2):
livepatch: add klp-convert tool and integrate with module build
livepatch: update sample module to use klp relocations

 Makefile                             |   2 +-
 include/linux/livepatch.h            |   1 +
 include/uapi/linux/Kbuild            |   1 +
 include/uapi/linux/livepatch.h       |  37 ++
 kernel/livepatch/core.c              |   4 +-
 samples/livepatch/livepatch-sample.c |  15 +-
 scripts/Makefile                     |   1 +
 scripts/Makefile.modpost             |  18 +-
 scripts/livepatch/.gitignore         |   1 +
 scripts/livepatch/Makefile           |   7 +
 scripts/livepatch/elf.c              | 717 +++++++++++++++++++++++++++++++++++
 scripts/livepatch/elf.h              |  88 +++++
 scripts/livepatch/klp-convert.c      | 181 +++++++++
 scripts/livepatch/list.h             | 381 +++++++++++++++++++
 scripts/mod/modpost.c                |   9 +-
 scripts/mod/modpost.h                |   1 +
 16 files changed, 1454 insertions(+), 10 deletions(-)
 create mode 100644 include/uapi/linux/livepatch.h
 create mode 100644 scripts/livepatch/.gitignore
 create mode 100644 scripts/livepatch/Makefile
 create mode 100644 scripts/livepatch/elf.c
 create mode 100644 scripts/livepatch/elf.h
 create mode 100644 scripts/livepatch/klp-convert.c
 create mode 100644 scripts/livepatch/list.h

2.7.4

This still needs to be split up into several patches. It does several things:

- Create a klp_module_reloc struct and KLP_MODULE_RELOC macro which gives livepatch modules a way to specify which local and unexported symbols they need.

- Create a klp-convert tool which reads the klp_module_reloc structs from the ".klp.module_relocs.*" sections and converts the relevant symbols and relocations to their klp counterparts.

- Integrate klp-convert with the module build so that it automatically converts any kernel modules with the 'livepatch' modinfo to real livepatch modules.

---
 Makefile                        |   2 +-
 include/linux/livepatch.h       |   1 +
 include/uapi/linux/Kbuild       |   1 +
 include/uapi/linux/livepatch.h  |  37 +++
 kernel/livepatch/core.c         |   4 +-
 scripts/Makefile                |   1 +
 scripts/Makefile.modpost        |  18 +-
 scripts/livepatch/.gitignore    |   1 +
 scripts/livepatch/Makefile      |   7 +
 scripts/livepatch/elf.c         | 717 ++++++++++++++++++++++++++++++++++++++++
 scripts/livepatch/elf.h         |  88 +++++
 scripts/livepatch/klp-convert.c | 181 ++++++++++
 scripts/livepatch/list.h        | 381 +++++++++++++++++++++
 scripts/mod/modpost.c           |   9 +-
 scripts/mod/modpost.h           |   1 +
 15 files changed, 1443 insertions(+), 6 deletions(-)
 create mode 100644 include/uapi/linux/livepatch.h
 create mode 100644 scripts/livepatch/.gitignore
 create mode 100644 scripts/livepatch/Makefile
 create mode 100644 scripts/livepatch/elf.c
 create mode 100644 scripts/livepatch/elf.h
 create mode 100644 scripts/livepatch/klp-convert.c
 create mode 100644 scripts/livepatch/list.h

index 93beca4..5114e99 100644
@@ -555,7 +555,7 @@ ifeq ($(KBUILD_EXTMOD),)
 # in parallel
 PHONY += scripts
 scripts: scripts_basic include/config/auto.conf include/config/tristate.conf \
-	 asm-generic gcc-plugins
+	 asm-generic gcc-plugins headers_install
 	$(Q)$(MAKE) $(build)=$(@)
 
 # Objects we will link into vmlinux / subdirs we need to visit

index 9072f04..0537eb9 100644
@@ -23,6 +23,7 @@
 
 #include <linux/module.h>
 #include <linux/ftrace.h>
+#include <uapi/linux/livepatch.h>
 
 #if IS_ENABLED(CONFIG_LIVEPATCH)
 

index bc2ef9f..5500312 100644
@@ -250,6 +250,7 @@ header-y += l2tp.h
 header-y += libc-compat.h
 header-y += lirc.h
 header-y += limits.h
+header-y += livepatch.h
 header-y += llc.h
 header-y += loop.h
 header-y += lp.h

new file mode 100644
index 0000000..41184f9
@@ -0,0 +1,37 @@
+/*
+ * livepatch.h - Kernel Live Patching Core
+ *
+ * Copyright (C) 2016 Josh Poimboeuf <[email protected]>
+ *
+ * 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; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that 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/>.
+ */
+
+#ifndef _UAPI_LIVEPATCH_H
+#define _UAPI_LIVEPATCH_H
+
+#include <linux/types.h>
+
+#define KLP_RELA_PREFIX		".klp.rela."
+#define KLP_SYM_PREFIX		".klp.sym."
+
+struct klp_module_reloc {
+	void *sym;
+	unsigned int sympos;
+} __attribute__((packed));
+
+#define KLP_MODULE_RELOC(obj) \
+	klp_module_reloc \
+	__attribute__((__section__(".klp.module_relocs." #obj)))
+
+#endif /* _UAPI_LIVEPATCH_H */

index af46438..e451345 100644
@@ -240,7 +240,7 @@ static int klp_resolve_symbols(Elf_Shdr *relasec, struct module *pmod)
 
 		/* Format: .klp.sym.objname.symname,sympos */
 		cnt = sscanf(strtab + sym->st_name,
-			     ".klp.sym.%55[^.].%127[^,],%lu",
+			     KLP_SYM_PREFIX "%55[^.].%127[^,],%lu",
 			     objname, symname, &sympos);
 		if (cnt != 3) {
 			pr_err("symbol %s has an incorrectly formatted name",

@@ -286,7 +286,7 @@ static int klp_write_object_relocations(struct module *pmod,
 		 * See comment in klp_resolve_symbols() for an explanation
 		 * of the selected field width value.
 		 */
-		cnt = sscanf(secname, ".klp.rela.%55[^.]", sec_objname);
+		cnt = sscanf(secname, KLP_RELA_PREFIX "%55[^.]", sec_objname);
 		if (cnt != 1) {
 			pr_err("section %s has an incorrectly formatted name",
 			       secname);

index 1d80897..2cc2b8a 100644
@@ -45,6 +45,7 @@ subdir-y                     += mod
 subdir-$(CONFIG_SECURITY_SELINUX) += selinux
 subdir-$(CONFIG_DTC)         += dtc
 subdir-$(CONFIG_GDB_SCRIPTS) += gdb
+subdir-$(CONFIG_LIVEPATCH)   += livepatch
 
 # Let clean descend into subdirs
 subdir-	+= basic kconfig package gcc-plugins

index 16923ba..916dd34 100644
@@ -123,10 +123,24 @@ quiet_cmd_ld_ko_o = LD [M]  $@
 	$(LD) -r $(LDFLAGS)                                             \
                  $(KBUILD_LDFLAGS_MODULE) $(LDFLAGS_MODULE)             \
                  -o $@ $(filter-out FORCE,$^) ;                         \
-	$(if $(ARCH_POSTLINK), $(MAKE) -f $(ARCH_POSTLINK) $@, true)
+	$(if $(ARCH_POSTLINK), $(MAKE) -f $(ARCH_POSTLINK) $@, true) ;
+
+ifdef CONFIG_LIVEPATCH
+KLP_CONVERT = scripts/livepatch/klp-convert
+      cmd_klp_convert =							\
+	if [[ -n "`modinfo -F livepatch $@`" ]]; then			\
+		mv $@ $(@:.ko=.klp.o);					\
+		$(KLP_CONVERT) $(@:.ko=.klp.o) $@;			\
+	fi ;
+endif
+
+define rule_link_module
+	$(call echo-cmd,ld_ko_o) $(cmd_ld_ko_o)				\
+	$(cmd_klp_convert)
+endef
 
 $(modules): %.ko :%.o %.mod.o FORCE
-	+$(call if_changed,ld_ko_o)
+	+$(call if_changed_rule,link_module)
 
 targets += $(modules)
 

new file mode 100644
index 0000000..dc22fe4
@@ -0,0 +1 @@
+klp-convert

new file mode 100644
index 0000000..221829b
@@ -0,0 +1,7 @@
+hostprogs-y		:= klp-convert
+always			:= $(hostprogs-y)
+
+klp-convert-objs	:= klp-convert.o elf.o
+
+HOSTCFLAGS		:= -g -I$(INSTALL_HDR_PATH)/include -Wall
+HOSTLDFLAGS		:= -lelf

index bd83497..f1a9bbc 100644
@@ -1960,6 +1960,13 @@ static void read_symbols(char *modname)
 					   "license", license);
 	}
 
+	/*
+	 * For livepatch modules, any unresolved symbols will get resolved
+	 * after linking by klp-convert.
+	 */
+	if (get_modinfo(info.modinfo, info.modinfo_len, "livepatch"))
+		mod->livepatch = 1;
+
 	for (sym = info.symtab_start; sym < info.symtab_stop; sym++) {
 		symname = remove_dot(info.strtab + sym->st_name);
 

@@ -2153,7 +2160,7 @@ static int add_versions(struct buffer *b, struct module *mod)
 	for (s = mod->unres; s; s = s->next) {
 		exp = find_symbol(s->name);
 		if (!exp || exp->module == mod) {
-			if (have_vmlinux && !s->weak) {
+			if (have_vmlinux && !s->weak && !mod->livepatch) {
 				if (warn_unresolved) {
 					warn("\"%s\" [%s.ko] undefined!\n",
 					     s->name, mod->name);

index 6a5e151..dcb32a5 100644
@@ -117,6 +117,7 @@ struct module {
 	int skip;
 	int has_init;
 	int has_cleanup;
+	int livepatch;
 	struct buffer dev_table_buf;
 	char	     srcversion[25];
 	int is_dot_o;

2.7.4

I've found some minor problems, this patch fixes:

* save cmd_ld_ko_o into .module.cmd, if_changed_rule doesn't do that
* fix bashisms for debian where /bin/sh is a symlink to /bin/dash
* rename rule_link_module to rule_ld_ko_o, otherwise arg-check inside if_changed_rule compares cmd_link_module and cmd_ld_ko_o
* use HOSTLOADLIBES_$module instead of HOSTLDFLAGS: -lelf must be at the end
* check modinfo -F livepatch only if CONFIG_LIVEPATCH is true

I think "modinfo -F" could be replaced with explicit mark in makefile, for example: LIVEPATCH_module.ko := y (like KASAN_SANITIZE_obj.o := n).

---
 scripts/Kbuild.include     |    4 +++-
 scripts/Makefile.modpost   |   24 +++++++++++-------------
 scripts/livepatch/Makefile |    2 +-
 3 files changed, 15 insertions(+), 15 deletions(-)

index 179219845dfc..e299fde3423b 100644
@@ -247,6 +247,8 @@ endif
 # (needed for the shell)
 make-cmd = $(call escsq,$(subst \#,\\\#,$(subst $$,$$$$,$(cmd_$(1)))))
 
+save-cmd = printf '%s\n' 'cmd_$@ := $(make-cmd)' > $(dot-target).cmd
+
 # Find any prerequisites that is newer than target or that does not exist.
 # PHONY targets skipped in both cases.
 any-prereq = $(filter-out $(PHONY),$?) $(filter-out $(PHONY) $(wildcard $^),$^)

@@ -256,7 +258,7 @@ any-prereq = $(filter-out $(PHONY),$?) $(filter-out $(PHONY) $(wildcard $^),$^)
 if_changed = $(if $(strip $(any-prereq) $(arg-check)),                       \
 	@set -e;                                                             \
 	$(echo-cmd) $(cmd_$(1));                                             \
-	printf '%s\n' 'cmd_$@ := $(make-cmd)' > $(dot-target).cmd, @:)
+	$(save-cmd), @:)
 
 # Execute the command and also postprocess generated .d dependencies file.
 if_changed_dep = $(if $(strip $(any-prereq) $(arg-check) ),                  \

index 916dd347e8f6..5d149d0b05c2 100644
@@ -123,24 +123,22 @@ quiet_cmd_ld_ko_o = LD [M]  $@
 	$(LD) -r $(LDFLAGS)                                             \
                  $(KBUILD_LDFLAGS_MODULE) $(LDFLAGS_MODULE)             \
                  -o $@ $(filter-out FORCE,$^) ;                         \
-	$(if $(ARCH_POSTLINK), $(MAKE) -f $(ARCH_POSTLINK) $@, true) ;
+	$(if $(ARCH_POSTLINK), $(MAKE) -f $(ARCH_POSTLINK) $@, true)
 
-ifdef CONFIG_LIVEPATCH
 KLP_CONVERT = scripts/livepatch/klp-convert
-      cmd_klp_convert =							\
-	if [[ -n "`modinfo -F livepatch $@`" ]]; then			\
-		mv $@ $(@:.ko=.klp.o);					\
-		$(KLP_CONVERT) $(@:.ko=.klp.o) $@;			\
-	fi ;
-endif
-
-define rule_link_module
-	$(call echo-cmd,ld_ko_o) $(cmd_ld_ko_o)				\
-	$(cmd_klp_convert)
+quiet_cmd_klp_convert = LIVEPATCH $@
+      cmd_klp_convert = mv $@ $(@:.ko=.klp.o); $(KLP_CONVERT) $(@:.ko=.klp.o) $@
+
+define rule_ld_ko_o
+       $(call echo-cmd,ld_ko_o) $(cmd_ld_ko_o) ;                        \
+       $(call save-cmd,ld_ko_o) ;                                       \
+       $(if $(CONFIG_LIVEPATCH),                                        \
+         if [ -n "`modinfo -F livepatch $@`" ] ; then                   \
+           $(call echo-cmd,klp_convert) $(cmd_klp_convert) ; fi)
 endef
 
 $(modules): %.ko :%.o %.mod.o FORCE
-	+$(call if_changed_rule,link_module)
+	+$(call if_changed_rule,ld_ko_o)
 
 targets += $(modules)
 

index 221829bb34c7..bd5c1ae553ab 100644
@@ -4,4 +4,4 @@ always			:= $(hostprogs-y)
 klp-convert-objs	:= klp-convert.o elf.o
 
 HOSTCFLAGS		:= -g -I$(INSTALL_HDR_PATH)/include -Wall
-HOSTLDFLAGS		:= -lelf
+HOSTLOADLIBES_klp-convert	:= -lelf

Ok, why not. I'll incorporate these changes to the patch set, if you're ok with it.

Right, this was the case with Josh's changes too if I understand modpost correctly (still causing me headaches).

Yes, replacing modinfo is definitely something I plan to do and explicit mark in Makefile is one option how to deal with it. I also though about a mark somewhere in a source code, but it does not matter much, I guess.

Thanks,
Miroslav

---
 samples/livepatch/livepatch-sample.c | 15 +++++++++++----
 1 file changed, 11 insertions(+), 4 deletions(-)

index e34f871..478d102 100644
@@ -32,7 +32,7 @@
  *
  * $ insmod livepatch-sample.ko
  * $ cat /proc/cmdline
- * this has been live patched
+ * <your cmdline> livepatch=1
  *
  * $ echo 0 > /sys/kernel/livepatch/livepatch_sample/enabled
  * $ cat /proc/cmdline

@@ -42,11 +42,18 @@
 #include <linux/seq_file.h>
 static int livepatch_cmdline_proc_show(struct seq_file *m, void *v)
 {
-	seq_printf(m, "%s\n", "this has been live patched");
+	seq_printf(m, "%s livepatch=1\n", saved_command_line);
 	return 0;
 }
 
-static struct klp_func funcs[] = {
+struct KLP_MODULE_RELOC(vmlinux) vmlinux_relocs[] = {
+	{
+		.sym = &saved_command_line,
+		.sympos = 0,
+	},
+};
+
+static struct klp_func vmlinux_funcs[] = {
 	{
 		.old_name = "cmdline_proc_show",
 		.new_func = livepatch_cmdline_proc_show,

@@ -56,7 +63,7 @@ static struct klp_func funcs[] = {
 static struct klp_object objs[] = {
 	{
 		/* name being NULL means vmlinux */
-		.funcs = funcs,
+		.funcs = vmlinux_funcs,
 	}, { }
 };
 

2.7.4

I think the biggest blocker for this approach is detecting gcc optimizations which break function ABI, i.e. Miroslav's presentation:

http://www.linuxplumbersconf.org/2016/ocw//system/presentations/3573/original/pres_gcc.pdf

Right now we have no way of finding all such cases.

I think our options are:

1) Find a way for gcc to report when function ABI has been broken;

2) Disable all gcc optimizations which can break function ABI. Not sure if this is even possible, but if so, we'd need to quantify the performance impact. (Note we might be able to leave some options enabled if they result in a function name change (e.g., -fpartial-inlining, -fipa-sra, -fipa-cp)); or

3) Stay with the status quo (kpatch-build?), since it has detection of such optimizations "built in".

Does anybody want to take ownership of this patch set and/or try to explore the options further? I don't have any more bandwidth right now (mainly due to the consistency model and porting objtool to DWARF).

Josh

This is the one I'd like to pursue in parallel to 3). But it is going to be long way I imagine.

I don't think this is possible. I mean technically possible, because I'm almost sure some optimizations cannot be disabled easily. And also performance-wise. It could have a serious impact on the kernel with CONFIG_LIVEPATCH enabled.

I consider this option a last resort.

Also possible. We could explore the usability of Joerg's asmtool for the purpose.

https://github.com/joergroedel/asmtool

It could be useful even if for the detection of changed functions.

Sure. I can take it. I tried to write a similar tool, I saw kpatch-build sources and have a clue how it all works. On the other hand, no promises about a timeline.

Miroslav

To be precise... I'm really happy to take it. It is the top of my priority list for upstream livepatch. Only I get stuck with things as part of my day job once in a while :)

Miroslav

Yes, the gcc folks I've talked to seem to agree.

I have some doubts about whether it would noticeably impact performance. As far as I can tell these optimizations are quite rare.

FWIW, I've asked some gcc folks about the feasibility of something like a '-fpreserve-function-abi' option. But I'm not holding my breath. It seems like a hard problem.

Great, thanks! I think your experiences with the gcc optimizations and with the various patch building tools make you a great candidate for this.

Josh

Hi Josh,

I owe you (and others) update...

- I split up the patch set (but it is still not nice enough)
- Konstantin's changes are merged
- I removed a dependency on modinfo and made some changes

But much more importantly. Joao (CC'd) took it over from now on. He can help us with userspace tooling in the future too. I am sure there is going to be faster progress with it now, because something has always distracted me recently :/ and it is important to finish it.

Regards,
Miroslav