livepatch: hybrid consistency model

This is a horrible way to detect whether a task has been preempted. Come up with something better: task flag? or is there already an existing mechanism?

Quoted 3 lines · Josh Poimboeuf

This is a horrible way to detect whether a task has been preempted. Come up with something better: task flag? or is there already an existing mechanism?

What about using kallsyms_lookup_size_offset() to check the address. It is more heavyweight but less hacky. The following code seems to work for me:

bool in_preempt_schedule_irq(unsigned long addr)

{
	static unsigned long size;

	if (unlikely(!size)) {
		int ret;

		ret = kallsyms_lookup_size_offset(
				(unsigned long)preempt_schedule_irq,
				size, NULL);

		/*
		 * Warn when the function is used without kallsyms or
		 * when it is unable to locate preempt_schedule_irq().

		 * Be conservative and always return true in this case.
		 */
		if (WARN_ON(!ret))
			size = -1L;
	}

	return (addr - (unsigned long)preempt_schedule_irq <= size);
}

Quoted 13 lines · Petr Mladek

Quoted 3 lines · Josh Poimboeuf

This is a horrible way to detect whether a task has been preempted. Come up with something better: task flag? or is there already an existing mechanism?

What about using kallsyms_lookup_size_offset() to check the address. It is more heavyweight but less hacky. The following code seems to work for me:

bool in_preempt_schedule_irq(unsigned long addr)

{
	static unsigned long size;

Quoted 6 lines

	if (unlikely(!size)) {
		int ret;

		ret = kallsyms_lookup_size_offset(
				(unsigned long)preempt_schedule_irq,
				size, NULL);

Quoted 10 lines

		/*
		 * Warn when the function is used without kallsyms or
		 * when it is unable to locate preempt_schedule_irq().
		 * Be conservative and always return true in this case.
		 */
		if (WARN_ON(!ret))
			size = -1L;
	}

Quoted 2 lines

	return (addr - (unsigned long)preempt_schedule_irq <= size);
}

Yeah, that would definitely be better. Though still somewhat hacky.

Quoted 14 lines · Josh Poimboeuf

Quoted 13 lines · Petr Mladek

Quoted 3 lines · Josh Poimboeuf

This is a horrible way to detect whether a task has been preempted. Come up with something better: task flag? or is there already an existing mechanism?

What about using kallsyms_lookup_size_offset() to check the address. It is more heavyweight but less hacky. The following code seems to work for me:

bool in_preempt_schedule_irq(unsigned long addr)

{
	static unsigned long size;

Quoted 6 lines

Quoted 6 lines

	if (unlikely(!size)) {
		int ret;

		ret = kallsyms_lookup_size_offset(
				(unsigned long)preempt_schedule_irq,
				size, NULL);

				^^^^

It works even better with &size ;-)

Quoted 10 lines

Quoted 10 lines

		/*
		 * Warn when the function is used without kallsyms or
		 * when it is unable to locate preempt_schedule_irq().
		 * Be conservative and always return true in this case.
		 */
		if (WARN_ON(!ret))
			size = -1L;
	}

Quoted 4 lines

Quoted 2 lines

	return (addr - (unsigned long)preempt_schedule_irq <= size);
}

Yeah, that would definitely be better. Though still somewhat hacky.

Yeah. Well this is the same approach that we use to check if a patched function is on the stack.

We could even move this check into the livepatch code but then print_context_stack_reliable() will not always give reliable results.

Quoted 4 lines · Petr Mladek

Quoted 1 line · Josh Poimboeuf

On Wed, Apr 06, 2016 at 03:06:19PM +0200, Petr Mladek wrote:

We could even move this check into the livepatch code but then print_context_stack_reliable() will not always give reliable results.

Why would moving the check to the livepatch code affect the reliability of print_context_stack_reliable()?

Quoted 6 lines · Josh Poimboeuf

Quoted 4 lines · Petr Mladek

Quoted 1 line · Josh Poimboeuf

On Wed, Apr 06, 2016 at 03:06:19PM +0200, Petr Mladek wrote:

We could even move this check into the livepatch code but then print_context_stack_reliable() will not always give reliable results.

Quoted 2 lines

Why would moving the check to the livepatch code affect the reliability of print_context_stack_reliable()?

print_context_stack_reliable() is a generic function that might eventualy be used also outside livepatch code. If there is preempt_schedule_irq() on the stack, it means that the rest of the stack might be unreliable and it should be detected by the function itself.

Let's forget the idea of moving the check into the livepatch code :-)

This is a horrible way to detect whether a task has been preempted. Come up with something better: task flag? or is there already an existing mechanism?

Signed-off-by Josh Poimboeuf <[email protected]>

---
include/linux/sched.h | 11 ++++++++++-
kernel/sched/core.c | 26 ++++++++++++++++++++++++--

2 files changed, 34 insertions(+), 3 deletions(-)

include/linux/sched.h +10 -1

index 589c478..62d0961 100644
@@ -3239,4 +3239,13 @@ struct update_util_data {
 void cpufreq_set_update_util_data(int cpu, struct update_util_data *data);
 #endif /* CONFIG_CPU_FREQ */
 
-#endif
+#ifdef CONFIG_PREEMPT
+extern bool in_preempt_schedule_irq(unsigned long addr);
+#else
+static inline bool in_preempt_schedule_irq(unsigned long addr)
+{
+	return false;
+}
+#endif /* CONFIG_PREEMPT */
+
+#endif /* _LINUX_SCHED_H */

kernel/sched/core.c +17 -2

index d8465ee..be1ef22 100644
@@ -3334,8 +3334,6 @@ asmlinkage __visible void __sched notrace preempt_schedule_notrace(void)
 }
 EXPORT_SYMBOL_GPL(preempt_schedule_notrace);
 
-#endif /* CONFIG_PREEMPT */
-
 /*
 * this is the entry point to schedule() from kernel preemption
 * off of irq context.

@@ -3360,8 +3358,32 @@ asmlinkage __visible void __sched preempt_schedule_irq(void)
 	} while (need_resched());
 
 	exception_exit(prev_state);
+
+	asm("preempt_schedule_irq_end:");
 }
 
+/*
+ * in_preempt_schedule_irq - determine if instruction address is inside the
+ *			     preempt_schedule_irq() function
+ *
+ * This is used when walking the stack of a task to determine whether an
+ * interrupt frame exists.
+ *
+ * NOTE: This function could return false if the address is in the function
+ * epilogue.  But it's good enough for our purposes, because we only care about
+ * addresses which have been saved on a stack.  If preempt_schedule_irq() is on
+ * the stack of a task, the saved address will always be prior to the epilogue.
+ */
+bool in_preempt_schedule_irq(unsigned long addr)
+{
+	extern void *preempt_schedule_irq_end;

Been sort of rattling my head over the scheduler code :-) Just following the calls in and out of __schedule() it doesn't look like there is a current flag/mechanism to tell whether or not a task has been preempted..

Is there any reason why you didn't just create a new task flag, something like TIF_PREEMPTED_IRQ, which would be set once preempt_schedule_irq() is entered and unset after __schedule() returns (for that task)? This would roughly correspond to setting the task flag when the frame for preempt_schedule_irq() is pushed and unsetting it just before the frame preempt_schedule_irq() is popped for that task. This seems simpler than walking through all the frames just to see if in_preempt_schedule_irq() had been called. Would that work?

Quoted 4 lines · Jessica Yu

Been sort of rattling my head over the scheduler code :-) Just following the calls in and out of __schedule() it doesn't look like there is a current flag/mechanism to tell whether or not a task has been preempted..

Performing the complete stack unwind just to determine whether task has been preempted non-volutarily is a slight overkill indeed :/

Quoted 8 lines

Is there any reason why you didn't just create a new task flag, something like TIF_PREEMPTED_IRQ, which would be set once preempt_schedule_irq() is entered and unset after __schedule() returns (for that task)? This would roughly correspond to setting the task flag when the frame for preempt_schedule_irq() is pushed and unsetting it just before the frame preempt_schedule_irq() is popped for that task. This seems simpler than walking through all the frames just to see if in_preempt_schedule_irq() had been called. Would that work?

Alternatively, without eating up a TIF_ space, it'd be possible to push a magic contents on top of the stack in preempt_schedule_irq() (and pop it once we are returning from there), and if such magic value is detected, we just don't bother and claim unreliability.

That has advantages of both aproaches combined, i.e. it's relatively low-cost in terms of performance penalty, and it's reliable (in a sense that you don't have false positives).

The small disadvantage is that you can (very rarely, depending on the chosen magic) have false negatives. That probably doesn't hurt too much, given the high inprobability and non-lethal consequences.

How does that sound?

To do that from C code, I guess we'd still need some arch-specific code in an asm() statement to do the actual push?

Quoted 5 lines

Been sort of rattling my head over the scheduler code :-) Just following the calls in and out of __schedule() it doesn't look like there is a current flag/mechanism to tell whether or not a task has been preempted..

Performing the complete stack unwind just to determine whether task has been preempted non-volutarily is a slight overkill indeed :/

Quoted 8 lines

Is there any reason why you didn't just create a new task flag, something like TIF_PREEMPTED_IRQ, which would be set once preempt_schedule_irq() is entered and unset after __schedule() returns (for that task)? This would roughly correspond to setting the task flag when the frame for preempt_schedule_irq() is pushed and unsetting it just before the frame preempt_schedule_irq() is popped for that task. This seems simpler than walking through all the frames just to see if in_preempt_schedule_irq() had been called. Would that work?

Alternatively, without eating up a TIF_ space, it'd be possible to push a magic contents on top of the stack in preempt_schedule_irq() (and pop it once we are returning from there), and if such magic value is detected, we just don't bother and claim unreliability.

That has advantages of both aproaches combined, i.e. it's relatively low-cost in terms of performance penalty, and it's reliable (in a sense that you don't have false positives).

The small disadvantage is that you can (very rarely, depending on the chosen magic) have false negatives. That probably doesn't hurt too much, given the high inprobability and non-lethal consequences.

How does that sound?

Signature · 2 lines

Jiri Kosina
SUSE Labs

Quoted 4 lines

Alternatively, without eating up a TIF_ space, it'd be possible to push a magic contents on top of the stack in preempt_schedule_irq() (and pop it once we are returning from there), and if such magic value is detected, we just don't bother and claim unreliability.

Ah, but wouldn't we still have to walk through the frames (i.e. enter the loop in patch 7/14) to look for the magic value in this approach?

Quoted 5 lines · Jessica Yu

Quoted 4 lines

Alternatively, without eating up a TIF_ space, it'd be possible to push a magic contents on top of the stack in preempt_schedule_irq() (and pop it once we are returning from there), and if such magic value is detected, we just don't bother and claim unreliability.

Quoted 2 lines

Ah, but wouldn't we still have to walk through the frames (i.e. enter the loop in patch 7/14) to look for the magic value in this approach?

The idea was that it'd be located at a place to which saved stack pointer of the sleeping task is pointing to (or at a fixed offset from it).

Quoted 7 lines · Jiri Kosina

Quoted 5 lines · Jessica Yu

Quoted 4 lines

Alternatively, without eating up a TIF_ space, it'd be possible to push a magic contents on top of the stack in preempt_schedule_irq() (and pop it once we are returning from there), and if such magic value is detected, we just don't bother and claim unreliability.

Quoted 5 lines

Quoted 2 lines

Ah, but wouldn't we still have to walk through the frames (i.e. enter the loop in patch 7/14) to look for the magic value in this approach?

The idea was that it'd be located at a place to which saved stack pointer of the sleeping task is pointing to (or at a fixed offset from it).

It is an interesting idea but it looks even more hacky than checking the frame pointers and return values.

Checking the stack might be an overkill but we already do this for all the other patched functions.

The big advantage about checking the stack is that it does not add any overhead to the scheduler code, does not eat any TIF flag or memory. The overhead is only when we are migrating a task and it is charged to a separate process.

Quoted 4 lines · Petr Mladek

The big advantage about checking the stack is that it does not add any overhead to the scheduler code, does not eat any TIF flag or memory. The overhead is only when we are migrating a task and it is charged to a separate process.

My biggest concern about checking the stack for preempt_schedule_irq() is that it's kind of brittle:

- What if the preemption code changes such that it's no longer a reliable indicator? For example, what if preempt_schedule_irq() is only called in some places, and a new __preempt_schedule_irq() is called elsewhere?

- Or due to some obscure gcc optimization like partial inlining or sibling tail calls, preempt_schedule_irq() doesn't show up on the stack?

- Or the code could silently break if there were another static preempt_schedule_irq symbol somewhere (though we could prevent this by searching all symbols to ensure there are no duplicates).

These scenarios are unlikely, but they could conceivably happen...

Anyway, we really wouldn't have to eat a TIF flag. We could instead add something to task_struct. I can at least propose it. If anybody doesn't like it, maybe they'll suggest something else, or maybe then we can go with checking the stack.

arch/x86/Kconfig config X86 · line 141

Quoted 9 lines · Josh Poimboeuf

arch/x86/Kconfig +1 -0

index 2dc18605..76274b8 100644
@@ -138,6 +138,7 @@ config X86
 	select HAVE_PERF_REGS
 	select HAVE_PERF_USER_STACK_DUMP
 	select HAVE_REGS_AND_STACK_ACCESS_API
+	select HAVE_RELIABLE_STACKTRACE		if X86_64 && FRAME_POINTER

I understand we have to rely on frame pointer for now. Do you plan to switch to dwarf unwinder one day in the future? IOW is there a plan to implement dwarf stuff generation in objtool and then to have a dwarf-based stack unwinder upstream and to use it for live patching?

We have FRAME_POINTER unset in SLES for performance reasons (there was some 5 percent slowdown measured in the past. However we should redo the experiments.) and one day we'd really like to switch to upstream from kgraft :). So I'm just asking.

Quoted 16 lines · Miroslav Benes

arch/x86/Kconfig config X86 · line 141

Quoted 9 lines · Josh Poimboeuf

arch/x86/Kconfig +1 -0

index 2dc18605..76274b8 100644
@@ -138,6 +138,7 @@ config X86
 	select HAVE_PERF_REGS
 	select HAVE_PERF_USER_STACK_DUMP
 	select HAVE_REGS_AND_STACK_ACCESS_API
+	select HAVE_RELIABLE_STACKTRACE		if X86_64 && FRAME_POINTER

I understand we have to rely on frame pointer for now. Do you plan to switch to dwarf unwinder one day in the future? IOW is there a plan to implement dwarf stuff generation in objtool and then to have a dwarf-based stack unwinder upstream and to use it for live patching?

Yes, adding DWARF validation and generation to objtool and creating a DWARF unwinder upstream are all planned, hopefully soon.

Quoted 18 lines · Josh Poimboeuf

Quoted 16 lines · Miroslav Benes

arch/x86/Kconfig config X86 · line 141

Quoted 9 lines · Josh Poimboeuf

arch/x86/Kconfig +1 -0

index 2dc18605..76274b8 100644
@@ -138,6 +138,7 @@ config X86
 	select HAVE_PERF_REGS
 	select HAVE_PERF_USER_STACK_DUMP
 	select HAVE_REGS_AND_STACK_ACCESS_API
+	select HAVE_RELIABLE_STACKTRACE		if X86_64 && FRAME_POINTER

I understand we have to rely on frame pointer for now. Do you plan to switch to dwarf unwinder one day in the future? IOW is there a plan to implement dwarf stuff generation in objtool and then to have a dwarf-based stack unwinder upstream and to use it for live patching?

Quoted 2 lines

Yes, adding DWARF validation and generation to objtool and creating a DWARF unwinder upstream are all planned, hopefully soon.

I may seem to be obtrusive, but here, I would like to offer my help again. If you need any kind of help with the unwinder, I can definitely help with that. Be it coding, testing, ideas discussion or anything else.

We had been using unwinder for over a decade in SUSE but it stopped working for assembly recently (for obvious reasons). So having a working and reliable unwinder again is one of the top priorities for us.

Quoted 3 lines

We had been using unwinder for over a decade in SUSE but it stopped working for assembly recently (for obvious reasons). So having a working and reliable unwinder again is one of the top priorities for us.

Since you already have an unwinder in SUSE, it sounds like what you need most urgently is DWARF generation support in objtool so that your unwinder will work again for asm code, right? The kernel already emits DWARF today (for C code), so an upstream unwinder isn't needed first.

That's high on my TODO list, and the coding is probably 70-80% done. I don't want to hold up progress... But I don't really feel comfortable passing the code off because it's quite a big feature with some major changes to objtool. Being the objtool author, I want to make sure to give it my full attention.

I'm spread quite thin at the moment but I do hope to have v1 of those patches soon, hopefully May-ish.

Quoted 8 lines · Josh Poimboeuf

Quoted 3 lines

We had been using unwinder for over a decade in SUSE but it stopped working for assembly recently (for obvious reasons). So having a working and reliable unwinder again is one of the top priorities for us.

Since you already have an unwinder in SUSE, it sounds like what you need most urgently is DWARF generation support in objtool so that your unwinder will work again for asm code, right? The kernel already emits DWARF today (for C code), so an upstream unwinder isn't needed first.

Right, that's exact.

Quoted 5 lines

That's high on my TODO list, and the coding is probably 70-80% done. I don't want to hold up progress... But I don't really feel comfortable passing the code off because it's quite a big feature with some major changes to objtool. Being the objtool author, I want to make sure to give it my full attention.

Sure. There is going to be no pressure to merge the v1 of the changes. But it would be nice to see what you have now so that we can start reviewing and proposing patches on the top of what you have :).

Quoted 2 lines

I'm spread quite thin at the moment but I do hope to have v1 of those patches soon, hopefully May-ish.

So I hope we will see something we can start working on now. I can really dedicate one-man hours to that work.

Quoted 18 lines · Jiri Slaby

Quoted 8 lines · Josh Poimboeuf

Quoted 3 lines

We had been using unwinder for over a decade in SUSE but it stopped working for assembly recently (for obvious reasons). So having a working and reliable unwinder again is one of the top priorities for us.

Since you already have an unwinder in SUSE, it sounds like what you need most urgently is DWARF generation support in objtool so that your unwinder will work again for asm code, right? The kernel already emits DWARF today (for C code), so an upstream unwinder isn't needed first.

Right, that's exact.

Quoted 5 lines

That's high on my TODO list, and the coding is probably 70-80% done. I don't want to hold up progress... But I don't really feel comfortable passing the code off because it's quite a big feature with some major changes to objtool. Being the objtool author, I want to make sure to give it my full attention.

Quoted 3 lines

Sure. There is going to be no pressure to merge the v1 of the changes. But it would be nice to see what you have now so that we can start reviewing and proposing patches on the top of what you have :).

The code is still quite a mess and doesn't even work yet. I think it would be counterproductive for everybody if I were to share it at this stage.

Quoted 3 lines

Quoted 2 lines

I'm spread quite thin at the moment but I do hope to have v1 of those patches soon, hopefully May-ish.

Quoted 2 lines

So I hope we will see something we can start working on now. I can really dedicate one-man hours to that work.

I do appreciate your offer to help. Hopefully soon I'll get it to at least a decently working and halfway readable state, and then I'll post it. Then any help will be much appreciated.

Quoted 33 lines · Josh Poimboeuf

Quoted 18 lines · Jiri Slaby

Quoted 8 lines · Josh Poimboeuf

Quoted 3 lines

We had been using unwinder for over a decade in SUSE but it stopped working for assembly recently (for obvious reasons). So having a working and reliable unwinder again is one of the top priorities for us.

Since you already have an unwinder in SUSE, it sounds like what you need most urgently is DWARF generation support in objtool so that your unwinder will work again for asm code, right? The kernel already emits DWARF today (for C code), so an upstream unwinder isn't needed first.

Right, that's exact.

Quoted 5 lines

That's high on my TODO list, and the coding is probably 70-80% done. I don't want to hold up progress... But I don't really feel comfortable passing the code off because it's quite a big feature with some major changes to objtool. Being the objtool author, I want to make sure to give it my full attention.

Quoted 3 lines

Sure. There is going to be no pressure to merge the v1 of the changes. But it would be nice to see what you have now so that we can start reviewing and proposing patches on the top of what you have :).

The code is still quite a mess and doesn't even work yet. I think it would be counterproductive for everybody if I were to share it at this stage.

Quoted 5 lines

Quoted 2 lines

I'm spread quite thin at the moment but I do hope to have v1 of those patches soon, hopefully May-ish.

So I hope we will see something we can start working on now. I can really dedicate one-man hours to that work.

Quoted 3 lines

I do appreciate your offer to help. Hopefully soon I'll get it to at least a decently working and halfway readable state, and then I'll post it. Then any help will be much appreciated.

This has beaten us for way too long, so we are at the state we want to have the DWARF generation for asm in a very close future. So may I ask you again to send me what you have now? If not, I will start working on it from scratch to have something rather soon :).

I honestly am planning on picking it back up as soon as I post the consistency model v3, probably next week.

Here's its current state, though it ain't pretty:

https://github.com/jpoimboe/linux/tree/objtool-dwarf

For live patching and possibly other use cases, a stack trace is only useful if you can be assured that it's completely reliable. Add a new save_stack_trace_tsk_reliable() function to achieve that.

Scenarios which indicate that a stack strace may be unreliable:

- interrupt stacks
- preemption
- corrupted stack data
- newly forked tasks
- running tasks
- the user didn't provide a large enough entries array

Also add a config option so arch-independent code can determine at build time whether the function is implemented.

arch/x86/kernel/dumpstack.c +0 -0

index 3b10518..9c68bfc 100644

arch/x86/kernel/dumpstack.c +19 -0

+		    in_preempt_schedule_irq(addr))
+			return -EINVAL;
+
+		if (ops->address(data, addr, 1))
+			return -EINVAL;
+
+		print_ftrace_graph_addr(addr, data, ops, tinfo, graph);
+
+		last_frame = frame;
+		frame = frame->next_frame;
+		ret_addr = &frame->return_address;
+	}
+
+	if (last_frame + 1 != (void *)task_pt_regs(tinfo->task))
+		return -EINVAL;
+
+	*bp = (unsigned long)frame;
+	return 0;
+}

Quoted 21 lines · Josh Poimboeuf

For live patching and possibly other use cases, a stack trace is only useful if you can be assured that it's completely reliable. Add a new save_stack_trace_tsk_reliable() function to achieve that.

Scenarios which indicate that a stack strace may be unreliable:

- interrupt stacks
- preemption
- corrupted stack data
- newly forked tasks
- running tasks
- the user didn't provide a large enough entries array

Also add a config option so arch-independent code can determine at build time whether the function is implemented.

arch/x86/kernel/dumpstack.c +0 -0

index 3b10518..9c68bfc 100644

arch/x86/kernel/dumpstack.c int print_context_stack_bp(struct thread_info *tinfo, · line 154

Quoted 10 lines

arch/x86/kernel/dumpstack.c +7 -0

@@ -145,6 +145,42 @@ int print_context_stack_bp(struct thread_info *tinfo,
 }
 EXPORT_SYMBOL_GPL(print_context_stack_bp);
 
+int print_context_stack_reliable(struct thread_info *tinfo,
+				 unsigned long *stack, unsigned long *bp,
+				 const struct stacktrace_ops *ops,
+				 void *data, unsigned long *end, int *graph)
+{
+	struct stack_frame *frame = (struct stack_frame *)*bp;
+	struct stack_frame *last_frame = frame;

I tried to debug why the patching never finishes as reported by Mirek. This initialization breaks the whole function, see below.
I would initialize last_frame to NULL or maybe (void *)stack.

arch/x86/kernel/dumpstack.c int print_context_stack_bp(struct thread_info *tinfo, · line 163

Quoted 9 lines

arch/x86/kernel/dumpstack.c +9 -0

+	unsigned long *ret_addr = &frame->return_address;
+
+	if (test_ti_thread_flag(tinfo, TIF_FORK))
+		return -EINVAL;
+
+	while (valid_stack_ptr(tinfo, ret_addr, sizeof(*ret_addr), end)) {
+		unsigned long addr = *ret_addr;
+
+		if (frame <= last_frame || !__kernel_text_address(addr) ||

frame == last_frame in the very rist iteration, so we always return -EINVAL.

For live patching and possibly other use cases, a stack trace is only useful if you can be assured that it's completely reliable. Add a new save_stack_trace_tsk_reliable() function to achieve that.

Scenarios which indicate that a stack strace may be unreliable:

- interrupt stacks
- preemption
- corrupted stack data
- newly forked tasks
- running tasks
- the user didn't provide a large enough entries array

Also add a config option so arch-independent code can determine at build time whether the function is implemented.

arch/x86/kernel/dumpstack.c +1 -0

index 3b10518..9c68bfc 100644
@@ -145,6 +145,42 @@ int print_context_stack_bp(struct thread_info *tinfo,
 }
 EXPORT_SYMBOL_GPL(print_context_stack_bp);
 
+int print_context_stack_reliable(struct thread_info *tinfo,

Quoted 25 lines · Josh Poimboeuf

For live patching and possibly other use cases, a stack trace is only useful if you can be assured that it's completely reliable. Add a new save_stack_trace_tsk_reliable() function to achieve that.

Scenarios which indicate that a stack strace may be unreliable:

- interrupt stacks
- preemption
- corrupted stack data
- newly forked tasks
- running tasks
- the user didn't provide a large enough entries array

Also add a config option so arch-independent code can determine at build time whether the function is implemented.

arch/x86/kernel/dumpstack.c +1 -0

index 3b10518..9c68bfc 100644
@@ -145,6 +145,42 @@ int print_context_stack_bp(struct thread_info *tinfo,
 }
 EXPORT_SYMBOL_GPL(print_context_stack_bp);
 
+int print_context_stack_reliable(struct thread_info *tinfo,

arch/x86/kernel/dumpstack.c int print_context_stack_bp(struct thread_info *tinfo, · line 158

Quoted 10 lines

arch/x86/kernel/dumpstack.c +10 -0

+				 unsigned long *stack, unsigned long *bp,
+				 const struct stacktrace_ops *ops,
+				 void *data, unsigned long *end, int *graph)
+{
+	struct stack_frame *frame = (struct stack_frame *)*bp;
+	struct stack_frame *last_frame = frame;
+	unsigned long *ret_addr = &frame->return_address;
+
+	if (test_ti_thread_flag(tinfo, TIF_FORK))
+		return -EINVAL;

Why exactly is a stack of a forked task unreliable, please?

There was some discussion about the possible stack state and the patch state after forking, see
http://thread.gmane.org/gmane.linux.kernel/2184163/focus=2191057

Anyway, I think that the stack should be ready for use when the process is visible in the task list. It means that it should be reliable.

arch/x86/kernel/dumpstack.c int print_context_stack_bp(struct thread_info *tinfo, · line 164

Quoted 5 lines

arch/x86/kernel/dumpstack.c +5 -0

+	while (valid_stack_ptr(tinfo, ret_addr, sizeof(*ret_addr), end)) {
+		unsigned long addr = *ret_addr;
+
+		if (frame <= last_frame || !__kernel_text_address(addr) ||
+		    in_preempt_schedule_irq(addr))

I wonder how exactly this works :-)

First, __kernel_text_address() returns true also for dynamically generated ftrace handlers, see is_ftrace_trampoline(). Do we have a guarantee that these functions generate a valid stack frame? We might want to ignore these here.

Second, if I get it correctly, in_preempt_schedule_irq() works because this functions is called only for tasks that are _not_ running. It means that we must be exactly at

     preempt_schedule_irq()
       __schedule()
	  context_switch()
	    switch_to()

It means that preempt_schedule_irq() must be on the stack if at least one of the other functions is not inlined.

As Jiri Kosina explained to me. We check it because it is called on exit from an interrupt handler. The interrupt might came at any time, for example, right before a function saves the stack frame. This is why it makes the stack unreliable.

If I get it correctly, this is the only location when the running process might get rescheduled from irq context. Other possibilities keeps the process running and the stack is marked unreliable elsewhere.

Well, I wonder if we should be more suspicious and make sure that only the regular process stack is used.

Quoted 2 lines · Petr Mladek

Well, I wonder if we should be more suspicious and make sure that only the regular process stack is used.

Notice the save_stack_stack_reliable() function, which is called by dump_trace() when the task is running on an interrupt or exception stack. It returns -EINVAL, so the stack gets marked unreliable. Does that address your concern, or did you mean something else?

For live patching and possibly other use cases, a stack trace is only useful if you can be assured that it's completely reliable. Add a new save_stack_trace_tsk_reliable() function to achieve that.

Scenarios which indicate that a stack strace may be unreliable:

- interrupt stacks
- preemption
- corrupted stack data
- newly forked tasks
- running tasks
- the user didn't provide a large enough entries array

Also add a config option so arch-independent code can determine at build time whether the function is implemented.

Signed-off-by Josh Poimboeuf <[email protected]>

---

arch/Kconfig                 |  6 ++++++
arch/x86/Kconfig             |  1 +
arch/x86/kernel/dumpstack.c  | 36 ++++++++++++++++++++++++++++++++++++
arch/x86/kernel/stacktrace.c | 32 ++++++++++++++++++++++++++++++++
include/linux/stacktrace.h   | 20 ++++++++++++++++----
kernel/stacktrace.c          |  4 ++--
lib/Kconfig.debug            |  6 ++++++
7 files changed, 99 insertions(+), 6 deletions(-)

arch/Kconfig +0 -0

index 81869a5..68b95f1 100644

Once we have a consistency model, patches and their objects will be enabled and disabled at different times. For example, when a patch is disabled, its loaded objects' funcs can remain registered with ftrace indefinitely until the unpatching operation is complete and they're no longer in use.

It's less confusing if we give them different names: patches can be enabled or disabled; objects (and their funcs) can be patched or unpatched:

- Enabled means that a patch is logically enabled (but not necessarily fully applied).

- Patched means that an object's funcs are registered with ftrace and added to the klp_ops func stack.

Also, since these states are binary, represent them with booleans instead of ints.

Signed-off-by Josh Poimboeuf <[email protected]>

---
include/linux/livepatch.h | 17 ++++-------
kernel/livepatch/core.c | 72 +++++++++++++++++++++++------------------------

2 files changed, 42 insertions(+), 47 deletions(-)

include/linux/livepatch.h +2 -7

index bd830d5..6d45dc7 100644
@@ -28,11 +28,6 @@
 
 #include <asm/livepatch.h>
 
-enum klp_state {
-	KLP_DISABLED,
-	KLP_ENABLED
-};
-
 /**
 * struct klp_func - function structure for live patching
 * @old_name:	name of the function to be patched

@@ -41,8 +36,8 @@ enum klp_state {
 *		can be found (optional)
 * @old_addr:	the address of the function being patched
 * @kobj:	kobject for sysfs resources
- * @state:	tracks function-level patch application state
 * @stack_node:	list node for klp_ops func_stack list
+ * @patched:	the func has been added to the klp_ops list
 */
 struct klp_func {
 	/* external */

@@ -60,8 +55,8 @@ struct klp_func {
 	/* internal */
 	unsigned long old_addr;
 	struct kobject kobj;
-	enum klp_state state;
 	struct list_head stack_node;
+	bool patched;
 };
 
 /**

Once we have a consistency model, patches and their objects will be enabled and disabled at different times. For example, when a patch is disabled, its loaded objects' funcs can remain registered with ftrace indefinitely until the unpatching operation is complete and they're no longer in use.

It's less confusing if we give them different names: patches can be enabled or disabled; objects (and their funcs) can be patched or unpatched:

- Enabled means that a patch is logically enabled (but not necessarily fully applied).

- Patched means that an object's funcs are registered with ftrace and added to the klp_ops func stack.

Also, since these states are binary, represent them with booleans instead of ints.

Signed-off-by Josh Poimboeuf <[email protected]>

---
 include/linux/livepatch.h | 17 ++++-------
 kernel/livepatch/core.c   | 72 +++++++++++++++++++++++------------------------
 2 files changed, 42 insertions(+), 47 deletions(-)

include/linux/livepatch.h +6 -11

index bd830d5..6d45dc7 100644
@@ -28,11 +28,6 @@
 
 #include <asm/livepatch.h>
 
-enum klp_state {
-	KLP_DISABLED,
-	KLP_ENABLED
-};
-
 /**
  * struct klp_func - function structure for live patching
  * @old_name:	name of the function to be patched

@@ -41,8 +36,8 @@ enum klp_state {
  *		can be found (optional)
  * @old_addr:	the address of the function being patched
  * @kobj:	kobject for sysfs resources
- * @state:	tracks function-level patch application state
  * @stack_node:	list node for klp_ops func_stack list
+ * @patched:	the func has been added to the klp_ops list
  */
 struct klp_func {
 	/* external */

@@ -60,8 +55,8 @@ struct klp_func {
 	/* internal */
 	unsigned long old_addr;
 	struct kobject kobj;
-	enum klp_state state;
 	struct list_head stack_node;
+	bool patched;
 };
 
 /**

@@ -90,7 +85,7 @@ struct klp_reloc {
  * @kobj:	kobject for sysfs resources
  * @mod:	kernel module associated with the patched object
  * 		(NULL for vmlinux)
- * @state:	tracks object-level patch application state
+ * @patched:	the object's funcs have been add to the klp_ops list
  */
 struct klp_object {
 	/* external */

@@ -101,7 +96,7 @@ struct klp_object {
 	/* internal */
 	struct kobject kobj;
 	struct module *mod;
-	enum klp_state state;
+	bool patched;
 };
 
 /**

@@ -110,7 +105,7 @@ struct klp_object {
  * @objs:	object entries for kernel objects to be patched
  * @list:	list node for global list of registered patches
  * @kobj:	kobject for sysfs resources
- * @state:	tracks patch-level application state
+ * @enabled:	the patch is enabled (but operation may be incomplete)
  */
 struct klp_patch {
 	/* external */

@@ -120,7 +115,7 @@ struct klp_patch {
 	/* internal */
 	struct list_head list;
 	struct kobject kobj;
-	enum klp_state state;
+	bool enabled;
 };
 
 #define klp_for_each_object(patch, obj) \

kernel/livepatch/core.c +36 -36

index d68fbf6..be1e106 100644
@@ -298,11 +298,11 @@ unlock:
 	rcu_read_unlock();
 }
 
-static void klp_disable_func(struct klp_func *func)
+static void klp_unpatch_func(struct klp_func *func)
 {
 	struct klp_ops *ops;
 
-	if (WARN_ON(func->state != KLP_ENABLED))
+	if (WARN_ON(!func->patched))
 		return;
 	if (WARN_ON(!func->old_addr))
 		return;

@@ -322,10 +322,10 @@ static void klp_disable_func(struct klp_func *func)
 		list_del_rcu(&func->stack_node);
 	}
 
-	func->state = KLP_DISABLED;
+	func->patched = false;
 }
 
-static int klp_enable_func(struct klp_func *func)
+static int klp_patch_func(struct klp_func *func)
 {
 	struct klp_ops *ops;
 	int ret;

@@ -333,7 +333,7 @@ static int klp_enable_func(struct klp_func *func)
 	if (WARN_ON(!func->old_addr))
 		return -EINVAL;
 
-	if (WARN_ON(func->state != KLP_DISABLED))
+	if (WARN_ON(func->patched))
 		return -EINVAL;
 
 	ops = klp_find_ops(func->old_addr);

@@ -372,7 +372,7 @@ static int klp_enable_func(struct klp_func *func)
 		list_add_rcu(&func->stack_node, &ops->func_stack);
 	}
 
-	func->state = KLP_ENABLED;
+	func->patched = true;
 
 	return 0;
 

@@ -383,36 +383,36 @@ err:
 	return ret;
 }
 
-static void klp_disable_object(struct klp_object *obj)
+static void klp_unpatch_object(struct klp_object *obj)
 {
 	struct klp_func *func;
 
 	klp_for_each_func(obj, func)
-		if (func->state == KLP_ENABLED)
-			klp_disable_func(func);
+		if (func->patched)
+			klp_unpatch_func(func);
 
-	obj->state = KLP_DISABLED;
+	obj->patched = false;
 }
 
-static int klp_enable_object(struct klp_object *obj)
+static int klp_patch_object(struct klp_object *obj)
 {
 	struct klp_func *func;
 	int ret;
 
-	if (WARN_ON(obj->state != KLP_DISABLED))
+	if (WARN_ON(obj->patched))
 		return -EINVAL;
 
 	if (WARN_ON(!klp_is_object_loaded(obj)))
 		return -EINVAL;
 
 	klp_for_each_func(obj, func) {
-		ret = klp_enable_func(func);
+		ret = klp_patch_func(func);
 		if (ret) {
-			klp_disable_object(obj);
+			klp_unpatch_object(obj);
 			return ret;
 		}
 	}
-	obj->state = KLP_ENABLED;
+	obj->patched = true;
 
 	return 0;
 }

@@ -423,17 +423,17 @@ static int __klp_disable_patch(struct klp_patch *patch)
 
 	/* enforce stacking: only the last enabled patch can be disabled */
 	if (!list_is_last(&patch->list, &klp_patches) &&
-	    list_next_entry(patch, list)->state == KLP_ENABLED)
+	    list_next_entry(patch, list)->enabled)
 		return -EBUSY;
 
 	pr_notice("disabling patch '%s'\n", patch->mod->name);
 
 	klp_for_each_object(patch, obj) {
-		if (obj->state == KLP_ENABLED)
-			klp_disable_object(obj);
+		if (obj->patched)
+			klp_unpatch_object(obj);
 	}
 
-	patch->state = KLP_DISABLED;
+	patch->enabled = false;
 
 	return 0;
 }

@@ -457,7 +457,7 @@ int klp_disable_patch(struct klp_patch *patch)
 		goto err;
 	}
 
-	if (patch->state == KLP_DISABLED) {
+	if (!patch->enabled) {
 		ret = -EINVAL;
 		goto err;
 	}

@@ -475,12 +475,12 @@ static int __klp_enable_patch(struct klp_patch *patch)
 	struct klp_object *obj;
 	int ret;
 
-	if (WARN_ON(patch->state != KLP_DISABLED))
+	if (WARN_ON(patch->enabled))
 		return -EINVAL;
 
 	/* enforce stacking: only the first disabled patch can be enabled */
 	if (patch->list.prev != &klp_patches &&
-	    list_prev_entry(patch, list)->state == KLP_DISABLED)
+	    !list_prev_entry(patch, list)->enabled)
 		return -EBUSY;
 
 	pr_notice_once("tainting kernel with TAINT_LIVEPATCH\n");

@@ -492,12 +492,12 @@ static int __klp_enable_patch(struct klp_patch *patch)
 		if (!klp_is_object_loaded(obj))
 			continue;
 
-		ret = klp_enable_object(obj);
+		ret = klp_patch_object(obj);
 		if (ret)
 			goto unregister;
 	}
 
-	patch->state = KLP_ENABLED;
+	patch->enabled = true;
 
 	return 0;
 

@@ -555,20 +555,20 @@ static ssize_t enabled_store(struct kobject *kobj, struct kobj_attribute *attr,
 	if (ret)
 		return -EINVAL;
 
-	if (val != KLP_DISABLED && val != KLP_ENABLED)
+	if (val > 1)
 		return -EINVAL;
 
 	patch = container_of(kobj, struct klp_patch, kobj);
 
 	mutex_lock(&klp_mutex);
 
-	if (val == patch->state) {
+	if (patch->enabled == val) {
 		/* already in requested state */
 		ret = -EINVAL;
 		goto err;
 	}
 
-	if (val == KLP_ENABLED) {
+	if (val) {
 		ret = __klp_enable_patch(patch);
 		if (ret)
 			goto err;

@@ -593,7 +593,7 @@ static ssize_t enabled_show(struct kobject *kobj,
 	struct klp_patch *patch;
 
 	patch = container_of(kobj, struct klp_patch, kobj);
-	return snprintf(buf, PAGE_SIZE-1, "%d\n", patch->state);
+	return snprintf(buf, PAGE_SIZE-1, "%d\n", patch->enabled);
 }
 
 static struct kobj_attribute enabled_kobj_attr = __ATTR_RW(enabled);

@@ -684,7 +684,7 @@ static void klp_free_patch(struct klp_patch *patch)
 static int klp_init_func(struct klp_object *obj, struct klp_func *func)
 {
 	INIT_LIST_HEAD(&func->stack_node);
-	func->state = KLP_DISABLED;
+	func->patched = false;
 
 	/* The format for the sysfs directory is <function,sympos> where sympos
 	 * is the nth occurrence of this symbol in kallsyms for the patched

@@ -729,7 +729,7 @@ static int klp_init_object(struct klp_patch *patch, struct klp_object *obj)
 	if (!obj->funcs)
 		return -EINVAL;
 
-	obj->state = KLP_DISABLED;
+	obj->patched = false;
 	obj->mod = NULL;
 
 	klp_find_object_module(obj);

@@ -770,7 +770,7 @@ static int klp_init_patch(struct klp_patch *patch)
 
 	mutex_lock(&klp_mutex);
 
-	patch->state = KLP_DISABLED;
+	patch->enabled = false;
 
 	ret = kobject_init_and_add(&patch->kobj, &klp_ktype_patch,
 				   klp_root_kobj, "%s", patch->mod->name);

@@ -816,7 +816,7 @@ int klp_unregister_patch(struct klp_patch *patch)
 		goto out;
 	}
 
-	if (patch->state == KLP_ENABLED) {
+	if (patch->enabled) {
 		ret = -EBUSY;
 		goto out;
 	}

@@ -897,13 +897,13 @@ int klp_module_coming(struct module *mod)
 				goto err;
 			}
 
-			if (patch->state == KLP_DISABLED)
+			if (!patch->enabled)
 				break;
 
 			pr_notice("applying patch '%s' to loading module '%s'\n",
 				  patch->mod->name, obj->mod->name);
 
-			ret = klp_enable_object(obj);
+			ret = klp_patch_object(obj);
 			if (ret) {
 				pr_warn("failed to apply patch '%s' to module '%s' (%d)\n",
 					patch->mod->name, obj->mod->name, ret);

@@ -954,10 +954,10 @@ void klp_module_going(struct module *mod)
 			if (!klp_is_module(obj) || strcmp(obj->name, mod->name))
 				continue;
 
-			if (patch->state != KLP_DISABLED) {
+			if (patch->enabled) {
 				pr_notice("reverting patch '%s' on unloading module '%s'\n",
 					  patch->mod->name, obj->mod->name);
-				klp_disable_object(obj);
+				klp_unpatch_object(obj);
 			}
 
 			klp_free_object_loaded(obj);

Signature · 6 lines

2.4.3

--
To unsubscribe from this list: send the line "unsubscribe live-patching" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Quoted 10 lines · Josh Poimboeuf

Once we have a consistency model, patches and their objects will be enabled and disabled at different times. For example, when a patch is disabled, its loaded objects' funcs can remain registered with ftrace indefinitely until the unpatching operation is complete and they're no longer in use.

It's less confusing if we give them different names: patches can be enabled or disabled; objects (and their funcs) can be patched or unpatched:

Quoted 9 lines

- Enabled means that a patch is logically enabled (but not necessarily fully applied).

- Patched means that an object's funcs are registered with ftrace and added to the klp_ops func stack.

Also, since these states are binary, represent them with booleans instead of ints.

Josh,

Awesome work here first of all!

Looking through the patchset a bit I see the following bools:
- functions: patched, transitioning
- objects: patched
- patches: enabled

It seems this reflects the following states at a patch level:
disabled - module inserted, not yet logically enabled enabled - logically enabled, but not all objects/functions patched transitioning - objects/functions are being applied or reverted patched - all objects/functions patched

However each object and function could have the same state and the parent object just reflects the 'aggregate state'. For example if all funcs in an object are patched then the object is also patched.

Perhaps we need more states (or maybe there will be more in the future), but wouldn't this just be easier to have something like for each patch, object, and function?

enum klp_state{
KLP_DISABLED,
KLP_ENABLED,
KLP_TRANSITION,
KLP_PATCHED,
}

I'm happy to help out too.

Quoted 52 lines · Chris J Arges

Quoted 10 lines · Josh Poimboeuf

Once we have a consistency model, patches and their objects will be enabled and disabled at different times. For example, when a patch is disabled, its loaded objects' funcs can remain registered with ftrace indefinitely until the unpatching operation is complete and they're no longer in use.

It's less confusing if we give them different names: patches can be enabled or disabled; objects (and their funcs) can be patched or unpatched:

Quoted 9 lines

- Enabled means that a patch is logically enabled (but not necessarily fully applied).

- Patched means that an object's funcs are registered with ftrace and added to the klp_ops func stack.

Also, since these states are binary, represent them with booleans instead of ints.

Josh,

Awesome work here first of all!

Looking through the patchset a bit I see the following bools:
- functions: patched, transitioning
- objects: patched
- patches: enabled

It seems this reflects the following states at a patch level:
disabled - module inserted, not yet logically enabled enabled - logically enabled, but not all objects/functions patched transitioning - objects/functions are being applied or reverted patched - all objects/functions patched

However each object and function could have the same state and the parent object just reflects the 'aggregate state'. For example if all funcs in an object are patched then the object is also patched.

Perhaps we need more states (or maybe there will be more in the future), but wouldn't this just be easier to have something like for each patch, object, and function?

enum klp_state{
KLP_DISABLED,
KLP_ENABLED,
KLP_TRANSITION,
KLP_PATCHED,
}

Quoted 1 line

I'm happy to help out too.

Thanks for the comments. First let me try to explain why I chose two bools rather than a single state variable.

At a func level, it's always in one of the following states:

patched=0 transition=0: unpatched
patched=0 transition=1: unpatched, temporary starting state patched=1 transition=1: patched, may be visible to some tasks patched=1 transition=0: patched, visible to all tasks

And for unpatching, it goes in the reverse order:

patched=1 transition=0: patched, visible to all tasks patched=1 transition=1: patched, may be visible to some tasks patched=0 transition=1: unpatched, temporary ending state patched=0 transition=0: unpatched

(note to self, put the above in a comment somewhere)

Now, we could convert the states from two bools into a single enum. But I think it would complicate the code. Because nowhere in the code does it need to access the full state. In some places it accesses func->patched and in other places it accesses func->transition, but it never needs to access both.

So for example, the following check in klp_ftrace_handler():

	if (unlikely(func->transition)) { 

would change to:

	if (unlikely(func->state == KLP_ENABLED || func->state == KLP_TRANSITION)) {

Sure, we could use a helper function to make that more readable. But with the bools its clearer and you don't need a helper function.

As another example, see the following code in klp_complete_transition():

	klp_for_each_object(klp_transition_patch, obj)
		klp_for_each_func(obj, func)
			func->transition = false;

The last line would have to be changed to something like:

			if (patching...)
				func->state = KLP_PATCHED;
			else /* unpatching */
				func->state = KLP_DISABLED;

So that's why I picked two bools over a single state variable: it seems to make the code simpler.

As to the other idea about copying the func states to the object and patch level, I get the feeling that would also complicate the code. We patch and transition at a function granularity, so the "real" state is at the func level. Proliferating that state to objects and patches might be tricky to get right, and it could make it harder to understand exactly what's going on in the code. And I don't really see a benefit to doing that.

Signature · 1 line

Josh

Quoted 65 lines · Josh Poimboeuf

Quoted 52 lines · Chris J Arges

Quoted 10 lines · Josh Poimboeuf

Once we have a consistency model, patches and their objects will be enabled and disabled at different times. For example, when a patch is disabled, its loaded objects' funcs can remain registered with ftrace indefinitely until the unpatching operation is complete and they're no longer in use.

It's less confusing if we give them different names: patches can be enabled or disabled; objects (and their funcs) can be patched or unpatched:

Quoted 9 lines

- Enabled means that a patch is logically enabled (but not necessarily fully applied).

- Patched means that an object's funcs are registered with ftrace and added to the klp_ops func stack.

Also, since these states are binary, represent them with booleans instead of ints.

Josh,

Awesome work here first of all!

Looking through the patchset a bit I see the following bools:
- functions: patched, transitioning
- objects: patched
- patches: enabled

It seems this reflects the following states at a patch level:
disabled - module inserted, not yet logically enabled enabled - logically enabled, but not all objects/functions patched transitioning - objects/functions are being applied or reverted patched - all objects/functions patched

However each object and function could have the same state and the parent object just reflects the 'aggregate state'. For example if all funcs in an object are patched then the object is also patched.

Perhaps we need more states (or maybe there will be more in the future), but wouldn't this just be easier to have something like for each patch, object, and function?

enum klp_state{
KLP_DISABLED,
KLP_ENABLED,
KLP_TRANSITION,
KLP_PATCHED,
}

Quoted 1 line

I'm happy to help out too.

Thanks for the comments. First let me try to explain why I chose two bools rather than a single state variable.

At a func level, it's always in one of the following states:

patched=0 transition=0: unpatched
patched=0 transition=1: unpatched, temporary starting state patched=1 transition=1: patched, may be visible to some tasks patched=1 transition=0: patched, visible to all tasks

Quoted 9 lines

And for unpatching, it goes in the reverse order:

patched=1 transition=0: patched, visible to all tasks patched=1 transition=1: patched, may be visible to some tasks patched=0 transition=1: unpatched, temporary ending state patched=0 transition=0: unpatched

(note to self, put the above in a comment somewhere)

This is helpful and makes more sense.

Quoted 33 lines

Now, we could convert the states from two bools into a single enum. But I think it would complicate the code. Because nowhere in the code does it need to access the full state. In some places it accesses func->patched and in other places it accesses func->transition, but it never needs to access both.

So for example, the following check in klp_ftrace_handler():

	if (unlikely(func->transition)) { 

would change to:

	if (unlikely(func->state == KLP_ENABLED || func->state == KLP_TRANSITION)) {

Sure, we could use a helper function to make that more readable. But with the bools its clearer and you don't need a helper function.

As another example, see the following code in klp_complete_transition():

	klp_for_each_object(klp_transition_patch, obj)
		klp_for_each_func(obj, func)
			func->transition = false;

The last line would have to be changed to something like:

			if (patching...)
				func->state = KLP_PATCHED;
			else /* unpatching */
				func->state = KLP_DISABLED;

So that's why I picked two bools over a single state variable: it seems to make the code simpler.

Quoted 11 lines

As to the other idea about copying the func states to the object and patch level, I get the feeling that would also complicate the code. We patch and transition at a function granularity, so the "real" state is at the func level. Proliferating that state to objects and patches might be tricky to get right, and it could make it harder to understand exactly what's going on in the code. And I don't really see a benefit to doing that.

Signature · 1 line

Josh

I think keeping it simple makes a ton of sense, thanks for the explanation.

I'm also envisioning how to troubleshoot patches that don't converge.

So if someone wanted to check if a function has been fully patched on all tasks they would check:

/sys/kernel/livepatch/<patch>/transition
/sys/kernel/livepatch/<patch>/patched

And see if patched=1 and transition=0 things are applied.

However if patched=1 and transition=1 then if a user wanted to dig down and see which pid's we were waiting on we could do:

cat /proc/*/patch_status

and check if any pid's patch_status values still contain KLP_UNIVERSE_OLD.

If we wanted to see which function in the task needs patching we could:
cat /proc/<pid>/stack
and see if anything in that stack contains the functions in question.

Anyway I'll keep looking at this patchset, patching using the samples/livepatch code works for me without issue so far.

kernel/fork.c +1 -0

index d277e83..27b181e 100644
@@ -76,6 +76,7 @@
 #include <linux/compiler.h>
 #include <linux/sysctl.h>
 #include <linux/kcov.h>
+#include <linux/livepatch.h>
 
 #include <asm/pgtable.h>
 #include <asm/pgalloc.h>

On Fri, 25 Mar 2016, Josh Poimboeuf wrote:

[...]

Quoted 10 lines

kernel/fork.c +1 -0

index d277e83..27b181e 100644
@@ -76,6 +76,7 @@
 #include <linux/compiler.h>
 #include <linux/sysctl.h>
 #include <linux/kcov.h>
+#include <linux/livepatch.h>
 

kernel/fork.c static struct task_struct *copy_process(unsigned long clone_flags, · line 1619

Quoted 7 lines

kernel/fork.c +1 -0

 #include <asm/pgtable.h>
 #include <asm/pgalloc.h>

@@ -1615,6 +1616,7 @@ static struct task_struct *copy_process(unsigned long clone_flags,
 	total_forks++;
 	spin_unlock(&current->sighand->siglock);
 	syscall_tracepoint_update(p);
+	klp_update_task_universe(p);

Shouldn't we copy transition and TIF from the parent? I deal with a race in kgraft and the solution seems to be this code exactly at this place in copy_process(). I need to think about it.

Hm, can you explain why it should be copied from the parent?

I'm thinking the above code is correct for today, but it should still be changed to be more future-proof.

Here's my thinking:

A forked task starts out with no stack, so if I understand correctly, it can safely start out in the goal universe, regardless of which universe its parent belongs to.

However, the current ret_from_fork code is a mess, and Andy Lutomirski has mentioned that he would like to give newly forked tasks a proper stack such that instead of jumping to ret_from_fork, they would just return from schedule(). In that case, it would no longer be safe to start the new task in the goal universe because it could be "sleeping" on a to-be-patched function.

So for proper future proofing, newly forked tasks should be started in the initial universe (rather than starting in the goal universe or inheriting the parent's universe). They can then be transitioned over to the goal universe like any other task. How does that sound?

Quoted 18 lines · Josh Poimboeuf

Hm, can you explain why it should be copied from the parent?

I'm thinking the above code is correct for today, but it should still be changed to be more future-proof.

Here's my thinking:

A forked task starts out with no stack, so if I understand correctly, it can safely start out in the goal universe, regardless of which universe its parent belongs to.

However, the current ret_from_fork code is a mess, and Andy Lutomirski has mentioned that he would like to give newly forked tasks a proper stack such that instead of jumping to ret_from_fork, they would just return from schedule(). In that case, it would no longer be safe to start the new task in the goal universe because it could be "sleeping" on a to-be-patched function.

Quoted 4 lines

So for proper future proofing, newly forked tasks should be started in the initial universe (rather than starting in the goal universe or inheriting the parent's universe). They can then be transitioned over to the goal universe like any other task. How does that sound?

How could a newly forked task start in the old universe if its parent has already been migrated? Any context it inherits will already be from the new universe.

Quoted 25 lines · Vojtech Pavlik

Quoted 22 lines · Josh Poimboeuf

Hm, can you explain why it should be copied from the parent?

I'm thinking the above code is correct for today, but it should still be changed to be more future-proof.

Here's my thinking:

A forked task starts out with no stack, so if I understand correctly, it can safely start out in the goal universe, regardless of which universe its parent belongs to.

However, the current ret_from_fork code is a mess, and Andy Lutomirski has mentioned that he would like to give newly forked tasks a proper stack such that instead of jumping to ret_from_fork, they would just return from schedule(). In that case, it would no longer be safe to start the new task in the goal universe because it could be "sleeping" on a to-be-patched function.

So for proper future proofing, newly forked tasks should be started in the initial universe (rather than starting in the goal universe or inheriting the parent's universe). They can then be transitioned over to the goal universe like any other task. How does that sound?

Quoted 3 lines

How could a newly forked task start in the old universe if its parent has already been migrated? Any context it inherits will already be from the new universe.

Can you be more specific about "context" and why inheritance of it would be a problem?

Quoted 26 lines · Josh Poimboeuf

Quoted 25 lines · Vojtech Pavlik

Quoted 22 lines · Josh Poimboeuf

Hm, can you explain why it should be copied from the parent?

I'm thinking the above code is correct for today, but it should still be changed to be more future-proof.

Here's my thinking:

A forked task starts out with no stack, so if I understand correctly, it can safely start out in the goal universe, regardless of which universe its parent belongs to.

However, the current ret_from_fork code is a mess, and Andy Lutomirski has mentioned that he would like to give newly forked tasks a proper stack such that instead of jumping to ret_from_fork, they would just return from schedule(). In that case, it would no longer be safe to start the new task in the goal universe because it could be "sleeping" on a to-be-patched function.

So for proper future proofing, newly forked tasks should be started in the initial universe (rather than starting in the goal universe or inheriting the parent's universe). They can then be transitioned over to the goal universe like any other task. How does that sound?

Quoted 6 lines

Quoted 3 lines

How could a newly forked task start in the old universe if its parent has already been migrated? Any context it inherits will already be from the new universe.

Can you be more specific about "context" and why inheritance of it would be a problem?

Currently a forked task starts out with no stack, and as such it can start in the goal universe.

If we create a synthetic stack, then we may need to start in the initial universe, as the synthetic stack would likely be created using initial universe return addresses.

If we simply copy the stack of the parent process, which is in my opionion the safest way, as it places little assumptions on the compiler, then it may contain either old or new addresses and we need to copy the universe flag along.

kernel/livepatch/transition.c line 123

Quoted 13 lines · Josh Poimboeuf

kernel/livepatch/transition.c new file +13 -0

+static int klp_check_stack(struct task_struct *task)
+{
+	static unsigned long entries[MAX_STACK_ENTRIES];
+	struct stack_trace trace;
+	struct klp_object *obj;
+	struct klp_func *func;
+	int ret;
+
+	trace.skip = 0;
+	trace.nr_entries = 0;
+	trace.max_entries = MAX_STACK_ENTRIES;
+	trace.entries = entries;
+	ret = save_stack_trace_tsk_reliable(task, &trace);

Format the array entries before using it.

Add a basic per-task consistency model. This is the foundation which will eventually enable us to patch those ~10% of security patches which change function prototypes and/or data semantics.

When a patch is enabled, livepatch enters into a transition state where tasks are converging from the old universe to the new universe. If a given task isn't using any of the patched functions, it's switched to the new universe. Once all the tasks have been converged to the new universe, patching is complete.

The same sequence occurs when a patch is disabled, except the tasks converge from the new universe to the old universe.

The /sys/kernel/livepatch/<patch>/transition file shows whether a patch is in transition. Only a single patch (the topmost patch on the stack) can be in transition at a given time. A patch can remain in the transition state indefinitely, if any of the tasks are stuck in the previous universe.

A transition can be reversed and effectively canceled by writing the opposite value to the /sys/kernel/livepatch/<patch>/enabled file while the transition is in progress. Then all the tasks will attempt to converge back to the original universe.

include/linux/livepatch.h +7 -0

+/*
+ * klp_update_task_universe() - change the patched state of a task
+ * @task:	The task to change
+ *
+ * Converts the patched state of the task so that it will switch to the set of
+ * functions in the goal universe.
+ */

kernel/livepatch/transition.c new file +10 -0

+static bool klp_try_switch_task(struct task_struct *task)
+{
+	struct rq *rq;
+	unsigned long flags;
+	int ret;
+	bool success = false;
+
+	/* check if this task has already switched over */
+	if (task->klp_universe == klp_universe_goal)
+		return true;

kernel/livepatch/transition.c new file +5 -0

+/*
+ * This function can be called in the middle of an existing transition to
+ * reverse the direction of the universe goal.  This can be done to effectively
+ * cancel an existing enable or disable operation if there are any tasks which
+ * are stuck in the starting universe.

Quoted 19 lines · Josh Poimboeuf

Add a basic per-task consistency model. This is the foundation which will eventually enable us to patch those ~10% of security patches which change function prototypes and/or data semantics.

When a patch is enabled, livepatch enters into a transition state where tasks are converging from the old universe to the new universe. If a given task isn't using any of the patched functions, it's switched to the new universe. Once all the tasks have been converged to the new universe, patching is complete.

The same sequence occurs when a patch is disabled, except the tasks converge from the new universe to the old universe.

The /sys/kernel/livepatch/<patch>/transition file shows whether a patch is in transition. Only a single patch (the topmost patch on the stack) can be in transition at a given time. A patch can remain in the transition state indefinitely, if any of the tasks are stuck in the previous universe.

Quoted 4 lines

A transition can be reversed and effectively canceled by writing the opposite value to the /sys/kernel/livepatch/<patch>/enabled file while the transition is in progress. Then all the tasks will attempt to converge back to the original universe.

So after spending some time with this patch I must say hats off to you. I haven't managed to find anything serious yet and I doubt I would. Few things below.

Quoted 7 lines

include/linux/livepatch.h +7 -0

+/*
+ * klp_update_task_universe() - change the patched state of a task
+ * @task:	The task to change
+ *
+ * Converts the patched state of the task so that it will switch to the set of
+ * functions in the goal universe.
+ */

include/linux/livepatch.h int klp_disable_patch(struct klp_patch *); · line 162

Quoted 10 lines

include/linux/livepatch.h +10 -0

+static inline void klp_update_task_universe(struct task_struct *task)
+{
+	/*
+	 * The corresponding write barriers are in klp_init_transition() and
+	 * klp_start_transition().  See the comments there for an explanation.
+	 */
+	smp_rmb();
+
+	task->klp_universe = klp_universe_goal;
+}

I wonder whether we should introduce a static_key for this function. klp_update_task_universe() is called in some important code paths and it is called everytime if CONFIG_LIVEPATCH is on. It does not matter much for syscall paths, because we enter slowpath there only if TIF_KLP_NEED_UPDATE is set and that is set iff patching is in progress. But we call the function also elsewhere. So maybe it would be nice to introduce static_key in the function which would be on if the patching is in progress and off if not.

Maybe it is just an overoptimization though.

[...]

Quoted 10 lines

kernel/livepatch/transition.c new file +10 -0

+static bool klp_try_switch_task(struct task_struct *task)
+{
+	struct rq *rq;
+	unsigned long flags;
+	int ret;
+	bool success = false;
+
+	/* check if this task has already switched over */
+	if (task->klp_universe == klp_universe_goal)
+		return true;

[...]

Quoted 5 lines

kernel/livepatch/transition.c new file +5 -0

+/*
+ * This function can be called in the middle of an existing transition to
+ * reverse the direction of the universe goal.  This can be done to effectively
+ * cancel an existing enable or disable operation if there are any tasks which
+ * are stuck in the starting universe.

kernel/livepatch/transition.c line 318

Quoted 10 lines

kernel/livepatch/transition.c new file +10 -0

+ */
+void klp_reverse_transition(void)
+{
+	struct klp_patch *patch = klp_transition_patch;
+
+	klp_start_transition(!klp_universe_goal);
+	klp_try_complete_transition();
+
+	patch->enabled = !patch->enabled;
+}

This function could be called iff the patching is in progress, there are some not-yet-migrated tasks and we wait for scheduled workqueue to run klp_try_complete_transition() again, right? I have two questions.

1. Is the call to klp_try_complete_transition() here necessary? It would be called via workqueue, wouldn't it? I suspect we don't gain much with this and we introduce possible future problems because of "double success" of klp_try_complete_transition() (nothing serious there as of now though). But I might be wrong because I got really confused by this piece of code and its context :)

2. klp_reverse_transition() works well because not-yet-migrated tasks are still in KLP_UNIVERSE_OLD (without loss of generality) and since klp_universe_goal is swapped they are in fact in their target universe. klp_try_switch_task() returns immediately in such case. The rest is migrated in an ordinary way.

What about TIF_KLP_NEED_UPDATE (I know it is introduced in later patch but it is easier to discuss it here)? klp_start_transition() resets the flag for all the task. Shouldn't the flag be cleared for the task in klp_try_switch_task() if task->klp_universe == klp_universe_goal? In fact it does not matter if it is set. The patching success is determined by klp_func->klp_universe booleans. But those tasks would needlessly go through syscall slowpaths (see note above about static_key) which could hurt performance.

Does this make sense?

[...]

transition.h:

Quoted 1 line

kernel/livepatch/transition.h line 18

Quoted 5 lines

kernel/livepatch/transition.h new file +5 -0

+extern void klp_init_transition(struct klp_patch *patch, int universe);
+extern void klp_start_transition(int universe);
+extern void klp_reverse_transition(void);
+extern bool klp_try_complete_transition(void);
+extern void klp_complete_transition(void);

externs are superfluous here and we do not have them in other header files.

Anyway, great job!

Quoted 29 lines · Miroslav Benes

Quoted 7 lines · Josh Poimboeuf

include/linux/livepatch.h +7 -0

+/*
+ * klp_update_task_universe() - change the patched state of a task
+ * @task:	The task to change
+ *
+ * Converts the patched state of the task so that it will switch to the set of
+ * functions in the goal universe.
+ */

include/linux/livepatch.h int klp_disable_patch(struct klp_patch *); · line 162

Quoted 10 lines

include/linux/livepatch.h +10 -0

+static inline void klp_update_task_universe(struct task_struct *task)
+{
+	/*
+	 * The corresponding write barriers are in klp_init_transition() and
+	 * klp_start_transition().  See the comments there for an explanation.
+	 */
+	smp_rmb();
+
+	task->klp_universe = klp_universe_goal;
+}

I wonder whether we should introduce a static_key for this function. klp_update_task_universe() is called in some important code paths and it is called everytime if CONFIG_LIVEPATCH is on. It does not matter much for syscall paths, because we enter slowpath there only if TIF_KLP_NEED_UPDATE is set and that is set iff patching is in progress. But we call the function also elsewhere. So maybe it would be nice to introduce static_key in the function which would be on if the patching is in progress and off if not.

Quoted 1 line

Maybe it is just an overoptimization though.

klp_update_task_universe() is called from:

- exit_to_usermode_loop() (slow path for syscall/irq exit)
- copy_process() (though I'll be changing this code so children inherit parents' flags)
- init_idle()
- cpu_idle_loop()
- various places in livepatch code

I think none of those are fast paths, so my feeling is that a static key would be overkill.

Quoted 33 lines

Quoted 10 lines

kernel/livepatch/transition.c new file +10 -0

+static bool klp_try_switch_task(struct task_struct *task)
+{
+	struct rq *rq;
+	unsigned long flags;
+	int ret;
+	bool success = false;
+
+	/* check if this task has already switched over */
+	if (task->klp_universe == klp_universe_goal)
+		return true;

[...]

Quoted 5 lines

kernel/livepatch/transition.c new file +5 -0

+/*
+ * This function can be called in the middle of an existing transition to
+ * reverse the direction of the universe goal.  This can be done to effectively
+ * cancel an existing enable or disable operation if there are any tasks which
+ * are stuck in the starting universe.

kernel/livepatch/transition.c line 318

Quoted 10 lines

kernel/livepatch/transition.c new file +10 -0

+ */
+void klp_reverse_transition(void)
+{
+	struct klp_patch *patch = klp_transition_patch;
+
+	klp_start_transition(!klp_universe_goal);
+	klp_try_complete_transition();
+
+	patch->enabled = !patch->enabled;
+}

This function could be called iff the patching is in progress, there are some not-yet-migrated tasks and we wait for scheduled workqueue to run klp_try_complete_transition() again, right? I have two questions.

Quoted 6 lines

1. Is the call to klp_try_complete_transition() here necessary? It would be called via workqueue, wouldn't it? I suspect we don't gain much with this and we introduce possible future problems because of "double success" of klp_try_complete_transition() (nothing serious there as of now though). But I might be wrong because I got really confused by this piece of code and its context :)

Yeah, the call to klp_try_complete_transition() isn't necessary because of the workqueue. It's still kind of nice to have though, because it tries to transition immediately rather than waiting for the work (and we might end up deciding to change the delayed work frequency to be less often than once per second).

I can't really envision that future bugs related to "double success" would be much to worry about. The work function does check for klp_transition_patch beforehand, and if it didn't, klp_complete_transition() would die loudly with a NULL pointer dereference. Of course, it's always hard to anticipate future code changes and I could be completely wrong.

So I would vote to keep this call, but I don't feel too strongly about it since it isn't strictly needed.

Quoted 15 lines

2. klp_reverse_transition() works well because not-yet-migrated tasks are still in KLP_UNIVERSE_OLD (without loss of generality) and since klp_universe_goal is swapped they are in fact in their target universe. klp_try_switch_task() returns immediately in such case. The rest is migrated in an ordinary way.

What about TIF_KLP_NEED_UPDATE (I know it is introduced in later patch but it is easier to discuss it here)? klp_start_transition() resets the flag for all the task. Shouldn't the flag be cleared for the task in klp_try_switch_task() if task->klp_universe == klp_universe_goal? In fact it does not matter if it is set. The patching success is determined by klp_func->klp_universe booleans. But those tasks would needlessly go through syscall slowpaths (see note above about static_key) which could hurt performance.

Quoted 1 line

Does this make sense?

I agree with you, but for a different reason :-)

And actually there's another way this could happen: if a task is forked during klp_start_transition() after setting the universe goal but before setting the thread flags, it would already be transitioned but its flag would get unnecessarily set. (Though as I mentioned above, the copy_process() code will be changed anyway, so that should no longer be an issue).

But I don't think it's really a performance issue, because:

1) Assuming a reliable stack, in most cases the majority of tasks are transitioned immediately. So when reversing the transition, there would be only a few tasks that would get the flag set unnecessarily.

2) For those tasks which do have the flag set unnecessarily, only the next syscall will do the slow path. After that the flag gets cleared. So it only slows down a single syscall for each task. At a macro level, that's just a drop in the bucket for performance and, IMO, not worth worrying about and adding (potentially buggy) code for.

However, I can think of another reason setting the flag unnecessarily might be bad: it's just conceptually confusing and could maybe lead to bugs. (ok, here we go trying to predict the future again!)

Specifically, after klp_complete_transition(), a reasonable livepatch developer (is that an oxymoron? ;-)) might assume that all tasks' TIF_KLP_NEED_UPDATE flags are cleared and might write code which makes that assumption.

And, even with today's code it's kind of hard to convince myself that having a spurious TIF_KLP_NEED_UPDATE flag set from a previous patching operation won't cause issues on the next patch.

So maybe we should do as you suggest and clear the flag in klp_try_switch_task() if the task is already in the goal universe.

Or if we wanted to be paranoid we could just clear all the flags in klp_complete_transition(), but maybe that's a little too sloppy/lazy?

Expose the per-task klp_universe value so users can determine which tasks are holding up completion of a patching operation.

Call it "patch_status" rather than "universe": it's at least more descriptive for the average user.

Signed-off-by Josh Poimboeuf <[email protected]>

---
 fs/proc/base.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)

fs/proc/base.c +9 -0

index b1755b2..f90998b 100644
@@ -2801,6 +2801,15 @@ static int proc_pid_personality(struct seq_file *m, struct pid_namespace *ns,
 	return err;
 }
 
+#ifdef CONFIG_LIVEPATCH
+static int proc_pid_patch_status(struct seq_file *m, struct pid_namespace *ns,
+				 struct pid *pid, struct task_struct *task)
+{
+	seq_printf(m, "%d\n", task->klp_universe);
+	return 0;
+}
+#endif /* CONFIG_LIVEPATCH */
+
 /*
  * Thread groups
  */

Quoted 33 lines · Josh Poimboeuf

Expose the per-task klp_universe value so users can determine which tasks are holding up completion of a patching operation.

Call it "patch_status" rather than "universe": it's at least more descriptive for the average user.

Signed-off-by Josh Poimboeuf <[email protected]>

---
 fs/proc/base.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)

fs/proc/base.c +9 -0

index b1755b2..f90998b 100644
@@ -2801,6 +2801,15 @@ static int proc_pid_personality(struct seq_file *m, struct pid_namespace *ns,
 	return err;
 }
 
+#ifdef CONFIG_LIVEPATCH
+static int proc_pid_patch_status(struct seq_file *m, struct pid_namespace *ns,
+				 struct pid *pid, struct task_struct *task)
+{
+	seq_printf(m, "%d\n", task->klp_universe);
+	return 0;
+}
+#endif /* CONFIG_LIVEPATCH */
+
 /*
  * Thread groups
  */

@@ -2900,6 +2909,9 @@ static const struct pid_entry tgid_base_stuff[] = {
 	REG("timers",	  S_IRUGO, proc_timers_operations),

fs/proc/base.c static const struct pid_entry tgid_base_stuff[] = { · line 2914

Quoted 5 lines

fs/proc/base.c +3 -0

 #endif
 	REG("timerslack_ns", S_IRUGO|S_IWUGO, proc_pid_set_timerslack_ns_operations),
+#ifdef CONFIG_LIVEPATCH
+	ONE("patch_status",  S_IRUSR, proc_pid_patch_status),
+#endif

I think we want to know the state about all tasks, not only group leaders. This should go to tid_base_stuff.

thanks,

Quoted 33 lines · Josh Poimboeuf

Expose the per-task klp_universe value so users can determine which tasks are holding up completion of a patching operation.

Call it "patch_status" rather than "universe": it's at least more descriptive for the average user.

Signed-off-by Josh Poimboeuf <[email protected]>

---
 fs/proc/base.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)

fs/proc/base.c +9 -0

index b1755b2..f90998b 100644
@@ -2801,6 +2801,15 @@ static int proc_pid_personality(struct seq_file *m, struct pid_namespace *ns,
 	return err;
 }
 
+#ifdef CONFIG_LIVEPATCH
+static int proc_pid_patch_status(struct seq_file *m, struct pid_namespace *ns,
+				 struct pid *pid, struct task_struct *task)
+{
+	seq_printf(m, "%d\n", task->klp_universe);
+	return 0;
+}
+#endif /* CONFIG_LIVEPATCH */
+
 /*
  * Thread groups
  */

@@ -2900,6 +2909,9 @@ static const struct pid_entry tgid_base_stuff[] = {
 	REG("timers",	  S_IRUGO, proc_timers_operations),

fs/proc/base.c static const struct pid_entry tgid_base_stuff[] = { · line 2914

Quoted 5 lines

fs/proc/base.c +3 -0

 #endif
 	REG("timerslack_ns", S_IRUGO|S_IWUGO, proc_pid_set_timerslack_ns_operations),
+#ifdef CONFIG_LIVEPATCH
+	ONE("patch_status",  S_IRUSR, proc_pid_patch_status),
+#endif

I think we want to know the state about all tasks, not only group leaders. This should go to tid_base_stuff.