| Message ID | eeda3a8cf83bcbb569db4774c646ad739b8db415.1481220077.git.jpoimboe@redhat.com (mailing list archive) |
|---|---|
| State | Superseded, archived |
| Headers | show |
On Thu 2016-12-08 12:08:38, Josh Poimboeuf wrote: > Change livepatch to use 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 or data semantics. This is the > biggest remaining piece needed to make livepatch more generally useful. > > [1] https://lkml.kernel.org/r/20141107140458.GA21774@suse.cz > > Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com> > --- > diff --git a/Documentation/livepatch/livepatch.txt b/Documentation/livepatch/livepatch.txt > index 6c43f6e..f87e742 100644 > --- a/Documentation/livepatch/livepatch.txt > +++ b/Documentation/livepatch/livepatch.txt I like the description. Just a note that we will also need to review the section about limitations. But I am not sure that we want to do it in this patch. It might open a long discussion on its own. > diff --git a/include/linux/livepatch.h b/include/linux/livepatch.h > index 1a5a93c..8e06fe5 100644 > --- a/include/linux/livepatch.h > +++ b/include/linux/livepatch.h > @@ -28,18 +28,40 @@ > > #include <asm/livepatch.h> > > +/* task patch states */ > +#define KLP_UNDEFINED -1 > +#define KLP_UNPATCHED 0 > +#define KLP_PATCHED 1 > + > /** > * struct klp_func - function structure for live patching > * @old_name: name of the function to be patched > * @new_func: pointer to the patched function code > * @old_sympos: a hint indicating which symbol position the old function > * can be found (optional) > + * @immediate: patch the func immediately, bypassing backtrace safety checks There are more checks possible. I would use the same description as for klp_object. > * @old_addr: the address of the function being patched > * @kobj: kobject for sysfs resources > * @stack_node: list node for klp_ops func_stack list > * @old_size: size of the old function > * @new_size: size of the new function > * @patched: the func has been added to the klp_ops list > + * @transition: the func is currently being applied or reverted > + * > @@ -86,6 +110,7 @@ struct klp_object { > * struct klp_patch - patch structure for live patching > * @mod: reference to the live patch module > * @objs: object entries for kernel objects to be patched > + * @immediate: patch all funcs immediately, bypassing safety mechanisms > * @list: list node for global list of registered patches > * @kobj: kobject for sysfs resources > * @enabled: the patch is enabled (but operation may be incomplete) [...] > diff --git a/kernel/livepatch/core.c b/kernel/livepatch/core.c > index fc160c6..22c0c01 100644 > --- a/kernel/livepatch/core.c > +++ b/kernel/livepatch/core.c > @@ -424,7 +477,10 @@ static ssize_t enabled_store(struct kobject *kobj, struct kobj_attribute *attr, > goto err; > } > > - if (enabled) { > + if (patch == klp_transition_patch) { > + klp_reverse_transition(); > + mod_delayed_work(system_wq, &klp_transition_work, 0); I would put this mod_delayed_work() into klp_reverse_transition(). Also I would put that schedule_delayed_work() into klp_try_complete_transition(). If I did not miss anything, it will allow to move the klp_transition_work code to transition.c where it logically belongs. > + } else if (enabled) { > ret = __klp_enable_patch(patch); > if (ret) > goto err; [...] > diff --git a/kernel/livepatch/patch.c b/kernel/livepatch/patch.c > index 5efa262..e79ebb5 100644 > --- a/kernel/livepatch/patch.c > +++ b/kernel/livepatch/patch.c > @@ -29,6 +29,7 @@ > #include <linux/bug.h> > #include <linux/printk.h> > #include "patch.h" > +#include "transition.h" > > static LIST_HEAD(klp_ops); > > @@ -54,15 +55,53 @@ static void notrace klp_ftrace_handler(unsigned long ip, > { > struct klp_ops *ops; > struct klp_func *func; > + int patch_state; > > ops = container_of(fops, struct klp_ops, fops); > > rcu_read_lock(); > + > func = list_first_or_null_rcu(&ops->func_stack, struct klp_func, > stack_node); > - if (WARN_ON_ONCE(!func)) > + > + if (!func) > goto unlock; Why do you removed the WARN_ON_ONCE(), please? We still add the function on the stack before registering the ftrace handler. Also we unregister the ftrace handler before removing the the last entry from the stack. AFAIK, unregister_ftrace_function() calls rcu_synchronize()' to make sure that no-one is inside the handler once finished. Mirek knows more about it. If this is not true, we have a problem. For example, we call kfree(ops) after unregister_ftrace_function(); BTW: I thought that this change was really needed because of klp_try_complete_transition(). But I think that the WARN could and should stay after all. See below. > + /* > + * Enforce the order of the ops->func_stack and func->transition reads. > + * The corresponding write barrier is in __klp_enable_patch(). > + */ > + smp_rmb(); > + > + if (unlikely(func->transition)) { > + > + /* > + * Enforce the order of the func->transition and > + * current->patch_state reads. Otherwise we could read an > + * out-of-date task state and pick the wrong function. The > + * corresponding write barriers are in klp_init_transition() > + * and __klp_disable_patch(). > + */ > + smp_rmb(); > + > + patch_state = current->patch_state; > + > + WARN_ON_ONCE(patch_state == KLP_UNDEFINED); > + > + if (patch_state == KLP_UNPATCHED) { > + /* > + * Use the previously patched version of the function. > + * If no previous patches exist, use the original > + * function. s/use the original/continue with the original/ ? > + */ > + func = list_entry_rcu(func->stack_node.next, > + struct klp_func, stack_node); > + > + if (&func->stack_node == &ops->func_stack) > + goto unlock; > + } > + } > + > klp_arch_set_pc(regs, (unsigned long)func->new_func); > unlock: > rcu_read_unlock(); > @@ -211,3 +250,12 @@ int klp_patch_object(struct klp_object *obj) > > return 0; > } > + > +void klp_unpatch_objects(struct klp_patch *patch) > +{ > + struct klp_object *obj; > + > + klp_for_each_object(patch, obj) > + if (obj->patched) > + klp_unpatch_object(obj); > +} > --- /dev/null > +++ b/kernel/livepatch/transition.c > @@ -0,0 +1,479 @@ > +/* > + * transition.c - Kernel Live Patching transition functions > + * > + * Copyright (C) 2015-2016 Josh Poimboeuf <jpoimboe@redhat.com> > + * > + * This program is free software; you can redistribute it and/or > + * modify it under the terms of the GNU General Public License > + * as published by the Free Software Foundation; 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/>. > + */ > + > +#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt > + > +#include <linux/cpu.h> > +#include <linux/stacktrace.h> > +#include "patch.h" > +#include "transition.h" > +#include "../sched/sched.h" Is this acceptable for the scheduler guys? > +#define MAX_STACK_ENTRIES 100 > + > +struct klp_patch *klp_transition_patch; > + > +static int klp_target_state = KLP_UNDEFINED; > + > +/* called from copy_process() during fork */ > +void klp_copy_process(struct task_struct *child) > +{ > + child->patch_state = current->patch_state; > + > + /* TIF_PATCH_PENDING gets copied in setup_thread_stack() */ > +} > + > +/* > + * klp_update_patch_state() - change the patched state of a task > + * @task: The task to change > + * > + * Switches the patched state of the task to the set of functions in the target > + * patch state. > + */ Please, add here some warning. Something like: * This function must never be called in parallel with * klp_ftrace_handler(). Otherwise, the handler might do random * decisions and break the consistency. * * By other words, call this function only by the @task itself * or make sure that it is not running. > +void klp_update_patch_state(struct task_struct *task) > +{ > + /* > + * The synchronize_rcu() call in klp_try_complete_transition() ensures > + * this critical section completes before the global patch transition > + * is considered complete so we don't have spurious patch_state updates > + * afterwards. > + */ > + rcu_read_lock(); > + > + /* > + * This test_and_clear_tsk_thread_flag() call also serves as a read > + * barrier to enforce the order of the TIF_PATCH_PENDING and > + * klp_target_state reads. The corresponding write barriers are in > + * __klp_disable_patch() and klp_reverse_transition(). > + */ > + if (test_and_clear_tsk_thread_flag(task, TIF_PATCH_PENDING)) > + task->patch_state = READ_ONCE(klp_target_state); > + > + rcu_read_unlock(); > +} > + > +/* > + * Initialize the global target patch state and all tasks to the initial patch > + * state, and initialize all function transition states to true in preparation > + * for patching or unpatching. > + */ > +void klp_init_transition(struct klp_patch *patch, int state) > +{ > + struct task_struct *g, *task; > + unsigned int cpu; > + struct klp_object *obj; > + struct klp_func *func; > + int initial_state = !state; > + > + WARN_ON_ONCE(klp_target_state != KLP_UNDEFINED); > + > + klp_transition_patch = patch; > + > + /* > + * Set the global target patch state which tasks will switch to. This > + * has no effect until the TIF_PATCH_PENDING flags get set later. > + */ > + klp_target_state = state; > + > + /* > + * If the patch can be applied or reverted immediately, skip the > + * per-task transitions. > + */ > + if (patch->immediate) > + return; > + > + /* > + * Initialize all tasks to the initial patch state to prepare them for > + * switching to the target state. > + */ > + read_lock(&tasklist_lock); > + for_each_process_thread(g, task) { > + WARN_ON_ONCE(task->patch_state != KLP_UNDEFINED); > + task->patch_state = initial_state; > + } > + read_unlock(&tasklist_lock); > + > + /* > + * Ditto for the idle "swapper" tasks. > + */ > + get_online_cpus(); > + for_each_online_cpu(cpu) { > + task = idle_task(cpu); > + WARN_ON_ONCE(task->patch_state != KLP_UNDEFINED); > + task->patch_state = initial_state; > + } > + put_online_cpus(); We allow to add/remove CPUs here. I am afraid that we will also need to add a cpu coming/going handler that will set the task->patch_state the right way. We must not set the klp_target_state until all ftrace handlers are ready. > + /* > + * Enforce the order of the task->patch_state initializations and the > + * func->transition updates to ensure that, in the enable path, > + * klp_ftrace_handler() doesn't see a func in transition with a > + * task->patch_state of KLP_UNDEFINED. > + */ > + smp_wmb(); > + > + /* > + * Set the func transition states so klp_ftrace_handler() will know to > + * switch to the transition logic. > + * > + * When patching, the funcs aren't yet in the func_stack and will be > + * made visible to the ftrace handler shortly by the calls to > + * klp_patch_object(). > + * > + * When unpatching, the funcs are already in the func_stack and so are > + * already visible to the ftrace handler. > + */ > + klp_for_each_object(patch, obj) > + klp_for_each_func(obj, func) > + func->transition = true; > +} > + > +/* > + * Start the transition to the specified target patch state so tasks can begin > + * switching to it. > + */ > +void klp_start_transition(void) > +{ > + struct task_struct *g, *task; > + unsigned int cpu; > + > + WARN_ON_ONCE(klp_target_state == KLP_UNDEFINED); > + > + pr_notice("'%s': %s...\n", klp_transition_patch->mod->name, > + klp_target_state == KLP_PATCHED ? "patching" : "unpatching"); > + > + /* > + * If the patch can be applied or reverted immediately, skip the > + * per-task transitions. > + */ > + if (klp_transition_patch->immediate) > + return; > + > + /* > + * Mark all normal tasks as needing a patch state update. As they pass > + * through the syscall barrier they'll switch over to the target state > + * (unless we switch them in klp_try_complete_transition() first). > + */ > + read_lock(&tasklist_lock); > + for_each_process_thread(g, task) > + set_tsk_thread_flag(task, TIF_PATCH_PENDING); This is called also from klp_reverse_transition(). We should set it only when the task need migration. Also we should clear it when the task is in the right state already. It is not only optimization. It actually solves a race between klp_complete_transition() and klp_update_patch_state(), see below. > + read_unlock(&tasklist_lock); > + > + /* > + * Ditto for the idle "swapper" tasks, though they never cross the > + * syscall barrier. Instead they switch over in cpu_idle_loop(). > + */ > + get_online_cpus(); > + for_each_online_cpu(cpu) > + set_tsk_thread_flag(idle_task(cpu), TIF_PATCH_PENDING); > + put_online_cpus(); Also this stage need to be somehow handled by CPU coming/going handlers. > +} > + > +/* > + * The transition to the target patch state is complete. Clean up the data > + * structures. > + */ > +void klp_complete_transition(void) > +{ > + struct klp_object *obj; > + struct klp_func *func; > + struct task_struct *g, *task; > + unsigned int cpu; > + > + if (klp_transition_patch->immediate) > + goto done; > + > + klp_for_each_object(klp_transition_patch, obj) > + klp_for_each_func(obj, func) > + func->transition = false; We should call rcu_synchronize() here. Otherwise, there might be a race, see below: CPU1 CPU2 klp_ftrace_handler() if (unlikely(func->transition)) // still true klp_complete_transition() func->transition = false; task->patch_state = KLP_UNDEFINED; patch_state = current->patch_state; WARN_ON(patch_state == KLP_UNDEFINED); BANG!: We print the warning. Note that that smp_wmb() is enough in klp_init_transition() but it is not enough here. We need to wait longer once someone might be inside the if (true) code. > + read_lock(&tasklist_lock); > + for_each_process_thread(g, task) { > + clear_tsk_thread_flag(task, TIF_PATCH_PENDING); > + task->patch_state = KLP_UNDEFINED; > + } > + read_unlock(&tasklist_lock); > + > + get_online_cpus(); > + for_each_online_cpu(cpu) { > + task = idle_task(cpu); > + clear_tsk_thread_flag(task, TIF_PATCH_PENDING); If TIF_PATCH_PENDING flag is set here it means that klp_update_patch_state() might get triggered and it might put wrong value into task->patch_state. We must make sure that all task have this cleared before calling this function. This is another reason why klp_init_transition() should set the flag only when transition is needed. We should only check the state here. It still might make sense to clear it when it is set wrongly. But the question is if it is really safe to continue. I am afraid that it is not. It would mean that the consistency model is broken and we are in strange state. > + task->patch_state = KLP_UNDEFINED; > + } > + put_online_cpus(); > + > +done: > + klp_target_state = KLP_UNDEFINED; > + klp_transition_patch = NULL; > +} [...] > + > +/* > + * Try to switch all remaining tasks to the target patch state by walking the > + * stacks of sleeping tasks and looking for any to-be-patched or > + * to-be-unpatched functions. If such functions are found, the task can't be > + * switched yet. > + * > + * If any tasks are still stuck in the initial patch state, schedule a retry. > + */ > +bool klp_try_complete_transition(void) > +{ > + unsigned int cpu; > + struct task_struct *g, *task; > + bool complete = true; > + > + WARN_ON_ONCE(klp_target_state == KLP_UNDEFINED); > + > + /* > + * If the patch can be applied or reverted immediately, skip the > + * per-task transitions. > + */ > + if (klp_transition_patch->immediate) > + goto success; > + > + /* > + * Try to switch the tasks to the target patch state by walking their > + * stacks and looking for any to-be-patched or to-be-unpatched > + * functions. If such functions are found on a stack, or if the stack > + * is deemed unreliable, the task can't be switched yet. > + * > + * Usually this will transition most (or all) of the tasks on a system > + * unless the patch includes changes to a very common function. > + */ > + read_lock(&tasklist_lock); > + for_each_process_thread(g, task) > + if (!klp_try_switch_task(task)) > + complete = false; > + read_unlock(&tasklist_lock); > + > + /* > + * Ditto for the idle "swapper" tasks. > + */ > + get_online_cpus(); > + for_each_online_cpu(cpu) > + if (!klp_try_switch_task(idle_task(cpu))) > + complete = false; > + put_online_cpus(); > + > + /* > + * Some tasks weren't able to be switched over. Try again later and/or > + * wait for other methods like syscall barrier switching. > + */ > + if (!complete) > + return false; > + > +success: > + > + /* > + * When unpatching, all tasks have transitioned to KLP_UNPATCHED so we > + * can now remove the new functions from the func_stack. > + */ > + if (klp_target_state == KLP_UNPATCHED) > + klp_unpatch_objects(klp_transition_patch); > + > + /* > + * Wait for all RCU read-side critical sections to complete. > + * > + * This has two purposes: > + * > + * 1) Ensure all existing critical sections in klp_update_patch_state() > + * complete, so task->patch_state won't be unexpectedly updated > + * later. We should not be here if anyone still might be in klp_update_patch_state(). > + * > + * 2) When unpatching, don't allow any existing instances of > + * klp_ftrace_handler() to access any obsolete funcs before we reset > + * the func transition states to false. Otherwise the handler may > + * see the deleted "new" func, see that it's not in transition, and > + * wrongly pick the new version of the function. > + */ This makes sense but it too me long time to understand. I wonder if this might be better: /* * Make sure that the function is removed from ops->func_stack * before we clear func->transition. Otherwise the handler may * pick the wrong version. */ And I would call this only when the patch is being removed if (klp_target_state = KLP_UNPATCHED) synchronize_rcu(); I think that this was the reason to remove WARN_ON_ONCE(!func) in klp_ftrace_handler(). But this is not related. If this was the last entry in the list, we removed the ftrace_handler before removing the last entry. And unregister_ftrace_function() calls rcu_synchronize() to prevent calling the handler later. > + synchronize_rcu(); > + > + pr_notice("'%s': %s complete\n", klp_transition_patch->mod->name, > + klp_target_state == KLP_PATCHED ? "patching" : "unpatching"); > + > + /* we're done, now cleanup the data structures */ > + klp_complete_transition(); > + > + return true; > +} > + > +/* > + * This function can be called in the middle of an existing transition to > + * reverse the direction of the target patch state. This can be done to > + * effectively cancel an existing enable or disable operation if there are any > + * tasks which are stuck in the initial patch state. > + */ > +void klp_reverse_transition(void) > +{ > + klp_transition_patch->enabled = !klp_transition_patch->enabled; > + > + klp_target_state = !klp_target_state; > + > + /* > + * Enforce the order of the write to klp_target_state above and the > + * TIF_PATCH_PENDING writes in klp_start_transition() to ensure that > + * klp_update_patch_state() doesn't set a wrong task->patch_state. > + */ > + smp_wmb(); I would call rcu_synchronize() here to make sure that klp_update_patch_state() calls will not set an outdated task->patch_state. Note that smp_wmb() is not enough. We do not check TIF_PATCH_PENDING in klp_try_switch_task(). There is a tiny race: CPU1 CPU2 klp_update_patch_state() if (test_and clear(task, TIF) READ_ONCE(klp_target_state); mutex_lock(klp_lock); klp_reverse_transition() klp_target_state = !klp_target_state; klp_start_transition() mutex_unlock(klp_lock); <switch to another process> klp_transition_work_fn() mutex_lock(klp_lock); klp_try_complete_transition() klp_try_switch_task() if (task->patch_state == klp_target_state) return true; task->patch_state = <outdated_value>; klp_ftrace_handler() BANG: klp_ftrace_handler() will use wrong implementation according to the outdated task->patch_state. At the same time, klp_transition() is not blocked by the task because it thinks that it has a correct state. > + > + klp_start_transition(); > +} > + > diff --git a/samples/livepatch/livepatch-sample.c b/samples/livepatch/livepatch-sample.c > index e34f871..bb61c65 100644 > --- a/samples/livepatch/livepatch-sample.c > +++ b/samples/livepatch/livepatch-sample.c > @@ -17,6 +17,8 @@ > * along with this program; if not, see <http://www.gnu.org/licenses/>. > */ > > +#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt > + > #include <linux/module.h> > #include <linux/kernel.h> > #include <linux/livepatch.h> > @@ -69,6 +71,11 @@ static int livepatch_init(void) > { > int ret; > > + if (!klp_have_reliable_stack() && !patch.immediate) { > + pr_notice("disabling consistency model!\n"); > + patch.immediate = true; > + } I am scared to have this in the sample module. It makes sense to use the consistency model even for immediate patches because it allows to remove them. But this must not be used for patches that really require the consistency model. We should add a big fat warning at least. > + > ret = klp_register_patch(&patch); > if (ret) > return ret; I like the patch. All the problems that I found look solvable. I think that we are on the right way. Best Regards, Petr
On Tue, Dec 20, 2016 at 06:32:46PM +0100, Petr Mladek wrote: > On Thu 2016-12-08 12:08:38, Josh Poimboeuf wrote: > > Change livepatch to use 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 or data semantics. This is the > > biggest remaining piece needed to make livepatch more generally useful. > > > > [1] https://lkml.kernel.org/r/20141107140458.GA21774@suse.cz > > > > Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com> > > --- > > diff --git a/Documentation/livepatch/livepatch.txt b/Documentation/livepatch/livepatch.txt > > index 6c43f6e..f87e742 100644 > > --- a/Documentation/livepatch/livepatch.txt > > +++ b/Documentation/livepatch/livepatch.txt > > I like the description. > > Just a note that we will also need to review the section about > limitations. But I am not sure that we want to do it in this patch. > It might open a long discussion on its own. > > > diff --git a/include/linux/livepatch.h b/include/linux/livepatch.h > > index 1a5a93c..8e06fe5 100644 > > --- a/include/linux/livepatch.h > > +++ b/include/linux/livepatch.h > > @@ -28,18 +28,40 @@ > > > > #include <asm/livepatch.h> > > > > +/* task patch states */ > > +#define KLP_UNDEFINED -1 > > +#define KLP_UNPATCHED 0 > > +#define KLP_PATCHED 1 > > + > > /** > > * struct klp_func - function structure for live patching > > * @old_name: name of the function to be patched > > * @new_func: pointer to the patched function code > > * @old_sympos: a hint indicating which symbol position the old function > > * can be found (optional) > > + * @immediate: patch the func immediately, bypassing backtrace safety checks > > There are more checks possible. I would use the same description > as for klp_object. Agreed. > > * @old_addr: the address of the function being patched > > * @kobj: kobject for sysfs resources > > * @stack_node: list node for klp_ops func_stack list > > * @old_size: size of the old function > > * @new_size: size of the new function > > * @patched: the func has been added to the klp_ops list > > + * @transition: the func is currently being applied or reverted > > + * > > @@ -86,6 +110,7 @@ struct klp_object { > > * struct klp_patch - patch structure for live patching > > * @mod: reference to the live patch module > > * @objs: object entries for kernel objects to be patched > > + * @immediate: patch all funcs immediately, bypassing safety mechanisms > > * @list: list node for global list of registered patches > > * @kobj: kobject for sysfs resources > > * @enabled: the patch is enabled (but operation may be incomplete) > > [...] > > > diff --git a/kernel/livepatch/core.c b/kernel/livepatch/core.c > > index fc160c6..22c0c01 100644 > > --- a/kernel/livepatch/core.c > > +++ b/kernel/livepatch/core.c > > @@ -424,7 +477,10 @@ static ssize_t enabled_store(struct kobject *kobj, struct kobj_attribute *attr, > > goto err; > > } > > > > - if (enabled) { > > + if (patch == klp_transition_patch) { > > + klp_reverse_transition(); > > + mod_delayed_work(system_wq, &klp_transition_work, 0); > > I would put this mod_delayed_work() into klp_reverse_transition(). > Also I would put that schedule_delayed_work() into > klp_try_complete_transition(). > > If I did not miss anything, it will allow to move the > klp_transition_work code to transition.c where it logically > belongs. Makes sense, I'll see if I can move all the klp_transition_work code to transition.c. > > + } else if (enabled) { > > ret = __klp_enable_patch(patch); > > if (ret) > > goto err; > > [...] > > > diff --git a/kernel/livepatch/patch.c b/kernel/livepatch/patch.c > > index 5efa262..e79ebb5 100644 > > --- a/kernel/livepatch/patch.c > > +++ b/kernel/livepatch/patch.c > > @@ -29,6 +29,7 @@ > > #include <linux/bug.h> > > #include <linux/printk.h> > > #include "patch.h" > > +#include "transition.h" > > > > static LIST_HEAD(klp_ops); > > > > @@ -54,15 +55,53 @@ static void notrace klp_ftrace_handler(unsigned long ip, > > { > > struct klp_ops *ops; > > struct klp_func *func; > > + int patch_state; > > > > ops = container_of(fops, struct klp_ops, fops); > > > > rcu_read_lock(); > > + > > func = list_first_or_null_rcu(&ops->func_stack, struct klp_func, > > stack_node); > > - if (WARN_ON_ONCE(!func)) > > + > > + if (!func) > > goto unlock; > > Why do you removed the WARN_ON_ONCE(), please? > > We still add the function on the stack before registering > the ftrace handler. Also we unregister the ftrace handler > before removing the the last entry from the stack. > > AFAIK, unregister_ftrace_function() calls rcu_synchronize()' > to make sure that no-one is inside the handler once finished. > Mirek knows more about it. Hm, this is news to me. Mirek, please share :-) > If this is not true, we have a problem. For example, > we call kfree(ops) after unregister_ftrace_function(); Agreed. > BTW: I thought that this change was really needed because of > klp_try_complete_transition(). But I think that the WARN > could and should stay after all. See below. > > > > + /* > > + * Enforce the order of the ops->func_stack and func->transition reads. > > + * The corresponding write barrier is in __klp_enable_patch(). > > + */ > > + smp_rmb(); > > + > > + if (unlikely(func->transition)) { > > + > > + /* > > + * Enforce the order of the func->transition and > > + * current->patch_state reads. Otherwise we could read an > > + * out-of-date task state and pick the wrong function. The > > + * corresponding write barriers are in klp_init_transition() > > + * and __klp_disable_patch(). > > + */ > > + smp_rmb(); > > + > > + patch_state = current->patch_state; > > + > > + WARN_ON_ONCE(patch_state == KLP_UNDEFINED); > > + > > + if (patch_state == KLP_UNPATCHED) { > > + /* > > + * Use the previously patched version of the function. > > + * If no previous patches exist, use the original > > + * function. > > s/use the original/continue with the original/ ? Ok. > > + */ > > + func = list_entry_rcu(func->stack_node.next, > > + struct klp_func, stack_node); > > + > > + if (&func->stack_node == &ops->func_stack) > > + goto unlock; > > + } > > + } > > + > > klp_arch_set_pc(regs, (unsigned long)func->new_func); > > unlock: > > rcu_read_unlock(); > > @@ -211,3 +250,12 @@ int klp_patch_object(struct klp_object *obj) > > > > return 0; > > } > > + > > +void klp_unpatch_objects(struct klp_patch *patch) > > +{ > > + struct klp_object *obj; > > + > > + klp_for_each_object(patch, obj) > > + if (obj->patched) > > + klp_unpatch_object(obj); > > +} > > --- /dev/null > > +++ b/kernel/livepatch/transition.c > > @@ -0,0 +1,479 @@ > > +/* > > + * transition.c - Kernel Live Patching transition functions > > + * > > + * Copyright (C) 2015-2016 Josh Poimboeuf <jpoimboe@redhat.com> > > + * > > + * This program is free software; you can redistribute it and/or > > + * modify it under the terms of the GNU General Public License > > + * as published by the Free Software Foundation; 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/>. > > + */ > > + > > +#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt > > + > > +#include <linux/cpu.h> > > +#include <linux/stacktrace.h> > > +#include "patch.h" > > +#include "transition.h" > > +#include "../sched/sched.h" > > Is this acceptable for the scheduler guys? I discussed the use of task_rq_lock() with Peter Zijlstra on IRC and he seemed to think it was ok. Peter, please speak up if you disagree :-) > > +#define MAX_STACK_ENTRIES 100 > > + > > +struct klp_patch *klp_transition_patch; > > + > > +static int klp_target_state = KLP_UNDEFINED; > > + > > +/* called from copy_process() during fork */ > > +void klp_copy_process(struct task_struct *child) > > +{ > > + child->patch_state = current->patch_state; > > + > > + /* TIF_PATCH_PENDING gets copied in setup_thread_stack() */ > > +} > > + > > +/* > > + * klp_update_patch_state() - change the patched state of a task > > + * @task: The task to change > > + * > > + * Switches the patched state of the task to the set of functions in the target > > + * patch state. > > + */ > > Please, add here some warning. Something like: > > * This function must never be called in parallel with > * klp_ftrace_handler(). Otherwise, the handler might do random > * decisions and break the consistency. > * > * By other words, call this function only by the @task itself > * or make sure that it is not running. Yeah, I'll add a comment here. This goes back to our discussion from last time: https://lkml.kernel.org/r/20160504172517.tdatoj2nlkqwyd4g@treble > > +void klp_update_patch_state(struct task_struct *task) > > +{ > > + /* > > + * The synchronize_rcu() call in klp_try_complete_transition() ensures > > + * this critical section completes before the global patch transition > > + * is considered complete so we don't have spurious patch_state updates > > + * afterwards. > > + */ > > + rcu_read_lock(); > > + > > + /* > > + * This test_and_clear_tsk_thread_flag() call also serves as a read > > + * barrier to enforce the order of the TIF_PATCH_PENDING and > > + * klp_target_state reads. The corresponding write barriers are in > > + * __klp_disable_patch() and klp_reverse_transition(). > > + */ > > + if (test_and_clear_tsk_thread_flag(task, TIF_PATCH_PENDING)) > > + task->patch_state = READ_ONCE(klp_target_state); > > + > > + rcu_read_unlock(); > > +} > > + > > +/* > > + * Initialize the global target patch state and all tasks to the initial patch > > + * state, and initialize all function transition states to true in preparation > > + * for patching or unpatching. > > + */ > > +void klp_init_transition(struct klp_patch *patch, int state) > > +{ > > + struct task_struct *g, *task; > > + unsigned int cpu; > > + struct klp_object *obj; > > + struct klp_func *func; > > + int initial_state = !state; > > + > > + WARN_ON_ONCE(klp_target_state != KLP_UNDEFINED); > > + > > + klp_transition_patch = patch; > > + > > + /* > > + * Set the global target patch state which tasks will switch to. This > > + * has no effect until the TIF_PATCH_PENDING flags get set later. > > + */ > > + klp_target_state = state; > > + > > + /* > > + * If the patch can be applied or reverted immediately, skip the > > + * per-task transitions. > > + */ > > + if (patch->immediate) > > + return; > > + > > + /* > > + * Initialize all tasks to the initial patch state to prepare them for > > + * switching to the target state. > > + */ > > + read_lock(&tasklist_lock); > > + for_each_process_thread(g, task) { > > + WARN_ON_ONCE(task->patch_state != KLP_UNDEFINED); > > + task->patch_state = initial_state; > > + } > > + read_unlock(&tasklist_lock); > > + > > + /* > > + * Ditto for the idle "swapper" tasks. > > + */ > > + get_online_cpus(); > > + for_each_online_cpu(cpu) { > > + task = idle_task(cpu); > > + WARN_ON_ONCE(task->patch_state != KLP_UNDEFINED); > > + task->patch_state = initial_state; > > + } > > + put_online_cpus(); > > We allow to add/remove CPUs here. I am afraid that we will also need > to add a cpu coming/going handler that will set the task->patch_state > the right way. We must not set the klp_target_state until all ftrace > handlers are ready. What if we instead just change the above to use for_each_possible_cpu()? We could do the same in klp_complete_transition(). > > + /* > > + * Enforce the order of the task->patch_state initializations and the > > + * func->transition updates to ensure that, in the enable path, > > + * klp_ftrace_handler() doesn't see a func in transition with a > > + * task->patch_state of KLP_UNDEFINED. > > + */ > > + smp_wmb(); > > + > > + /* > > + * Set the func transition states so klp_ftrace_handler() will know to > > + * switch to the transition logic. > > + * > > + * When patching, the funcs aren't yet in the func_stack and will be > > + * made visible to the ftrace handler shortly by the calls to > > + * klp_patch_object(). > > + * > > + * When unpatching, the funcs are already in the func_stack and so are > > + * already visible to the ftrace handler. > > + */ > > + klp_for_each_object(patch, obj) > > + klp_for_each_func(obj, func) > > + func->transition = true; > > +} > > + > > +/* > > + * Start the transition to the specified target patch state so tasks can begin > > + * switching to it. > > + */ > > +void klp_start_transition(void) > > +{ > > + struct task_struct *g, *task; > > + unsigned int cpu; > > + > > + WARN_ON_ONCE(klp_target_state == KLP_UNDEFINED); > > + > > + pr_notice("'%s': %s...\n", klp_transition_patch->mod->name, > > + klp_target_state == KLP_PATCHED ? "patching" : "unpatching"); > > + > > + /* > > + * If the patch can be applied or reverted immediately, skip the > > + * per-task transitions. > > + */ > > + if (klp_transition_patch->immediate) > > + return; > > + > > + /* > > + * Mark all normal tasks as needing a patch state update. As they pass > > + * through the syscall barrier they'll switch over to the target state > > + * (unless we switch them in klp_try_complete_transition() first). > > + */ > > + read_lock(&tasklist_lock); > > + for_each_process_thread(g, task) > > + set_tsk_thread_flag(task, TIF_PATCH_PENDING); > > This is called also from klp_reverse_transition(). We should set it > only when the task need migration. Also we should clear it when > the task is in the right state already. > > It is not only optimization. It actually solves a race between > klp_complete_transition() and klp_update_patch_state(), see below. I agree about the race, but if I did: for_each_process_thread(g, task) { if (task->patch_state != klp_target_state) set_tsk_thread_flag(task, TIF_PATCH_PENDING); else clear_tsk_thread_flag(task, TIF_PATCH_PENDING); } It would still leave a small window where TIF_PATCH_PENDING gets set for an already patched task, if klp_update_patch_state() is running at the same time. See below for another solution. > > + read_unlock(&tasklist_lock); > > + > > + /* > > + * Ditto for the idle "swapper" tasks, though they never cross the > > + * syscall barrier. Instead they switch over in cpu_idle_loop(). > > + */ > > + get_online_cpus(); > > + for_each_online_cpu(cpu) > > + set_tsk_thread_flag(idle_task(cpu), TIF_PATCH_PENDING); > > + put_online_cpus(); > > Also this stage need to be somehow handled by CPU coming/going > handlers. Here I think we could automatically switch any offline CPUs' idle tasks. And something similar in klp_try_complete_transition(). > > +} > > + > > +/* > > + * The transition to the target patch state is complete. Clean up the data > > + * structures. > > + */ > > +void klp_complete_transition(void) > > +{ > > + struct klp_object *obj; > > + struct klp_func *func; > > + struct task_struct *g, *task; > > + unsigned int cpu; > > + > > + if (klp_transition_patch->immediate) > > + goto done; > > + > > + klp_for_each_object(klp_transition_patch, obj) > > + klp_for_each_func(obj, func) > > + func->transition = false; > > We should call rcu_synchronize() here. Otherwise, there > might be a race, see below: > > CPU1 CPU2 > > klp_ftrace_handler() > if (unlikely(func->transition)) > // still true > > klp_complete_transition() > func->transition = false; > task->patch_state = > KLP_UNDEFINED; > > patch_state = current->patch_state; > > WARN_ON(patch_state == KLP_UNDEFINED); > > BANG!: We print the warning. This shouldn't be possible because klp_try_complete_transition() calls rcu_synchronize() before calling klp_complete_transition(). So by the time klp_complete_transition() is called, the ftrace handler can no longer see the affected func. See the comment for rcu_synchronize() in klp_try_complete_transition(). > Note that that smp_wmb() is enough in klp_init_transition() > but it is not enough here. We need to wait longer once > someone might be inside the if (true) code. > > > + read_lock(&tasklist_lock); > > + for_each_process_thread(g, task) { > > + clear_tsk_thread_flag(task, TIF_PATCH_PENDING); > > + task->patch_state = KLP_UNDEFINED; > > + } > > + read_unlock(&tasklist_lock); > > + > > + get_online_cpus(); > > + for_each_online_cpu(cpu) { > > + task = idle_task(cpu); > > + clear_tsk_thread_flag(task, TIF_PATCH_PENDING); > > If TIF_PATCH_PENDING flag is set here it means that > klp_update_patch_state() might get triggered and it might > put wrong value into task->patch_state. > > We must make sure that all task have this cleared before > calling this function. This is another reason why > klp_init_transition() should set the flag only when > transition is needed. > > We should only check the state here. > > It still might make sense to clear it when it is set wrongly. > But the question is if it is really safe to continue. I am > afraid that it is not. It would mean that the consistency > model is broken and we are in strange state. As I mentioned above, with your proposal I think there could still be a task with a spurious set TIF_PATCH_PENDING at this point. Maybe instead we should clear all the TIF_PATCH_PENDING flags before the synchronize_rcu() in klp_try_complete_transition(). > > + task->patch_state = KLP_UNDEFINED; > > + } > > + put_online_cpus(); > > + > > +done: > > + klp_target_state = KLP_UNDEFINED; > > + klp_transition_patch = NULL; > > +} > > [...] > > > + > > +/* > > + * Try to switch all remaining tasks to the target patch state by walking the > > + * stacks of sleeping tasks and looking for any to-be-patched or > > + * to-be-unpatched functions. If such functions are found, the task can't be > > + * switched yet. > > + * > > + * If any tasks are still stuck in the initial patch state, schedule a retry. > > + */ > > +bool klp_try_complete_transition(void) > > +{ > > + unsigned int cpu; > > + struct task_struct *g, *task; > > + bool complete = true; > > + > > + WARN_ON_ONCE(klp_target_state == KLP_UNDEFINED); > > + > > + /* > > + * If the patch can be applied or reverted immediately, skip the > > + * per-task transitions. > > + */ > > + if (klp_transition_patch->immediate) > > + goto success; > > + > > + /* > > + * Try to switch the tasks to the target patch state by walking their > > + * stacks and looking for any to-be-patched or to-be-unpatched > > + * functions. If such functions are found on a stack, or if the stack > > + * is deemed unreliable, the task can't be switched yet. > > + * > > + * Usually this will transition most (or all) of the tasks on a system > > + * unless the patch includes changes to a very common function. > > + */ > > + read_lock(&tasklist_lock); > > + for_each_process_thread(g, task) > > + if (!klp_try_switch_task(task)) > > + complete = false; > > + read_unlock(&tasklist_lock); > > + > > + /* > > + * Ditto for the idle "swapper" tasks. > > + */ > > + get_online_cpus(); > > + for_each_online_cpu(cpu) > > + if (!klp_try_switch_task(idle_task(cpu))) > > + complete = false; > > + put_online_cpus(); > > + > > + /* > > + * Some tasks weren't able to be switched over. Try again later and/or > > + * wait for other methods like syscall barrier switching. > > + */ > > + if (!complete) > > + return false; > > + > > +success: > > + > > + /* > > + * When unpatching, all tasks have transitioned to KLP_UNPATCHED so we > > + * can now remove the new functions from the func_stack. > > + */ > > + if (klp_target_state == KLP_UNPATCHED) > > + klp_unpatch_objects(klp_transition_patch); > > + > > + /* > > + * Wait for all RCU read-side critical sections to complete. > > + * > > + * This has two purposes: > > + * > > + * 1) Ensure all existing critical sections in klp_update_patch_state() > > + * complete, so task->patch_state won't be unexpectedly updated > > + * later. > > We should not be here if anyone still might be in klp_update_patch_state(). Depends on our discussion about conditionally setting TIF_PATCH_PENDING. > > > + * > > + * 2) When unpatching, don't allow any existing instances of > > + * klp_ftrace_handler() to access any obsolete funcs before we reset > > + * the func transition states to false. Otherwise the handler may > > + * see the deleted "new" func, see that it's not in transition, and > > + * wrongly pick the new version of the function. > > + */ > > This makes sense but it too me long time to understand. I wonder if > this might be better: > > /* > * Make sure that the function is removed from ops->func_stack > * before we clear func->transition. Otherwise the handler may > * pick the wrong version. > */ Sounds good. > And I would call this only when the patch is being removed > > if (klp_target_state = KLP_UNPATCHED) > synchronize_rcu(); Depends on our discussion about conditionally setting TIF_PATCH_PENDING. > I think that this was the reason to remove WARN_ON_ONCE(!func) > in klp_ftrace_handler(). But this is not related. If this was > the last entry in the list, we removed the ftrace_handler > before removing the last entry. And unregister_ftrace_function() > calls rcu_synchronize() to prevent calling the handler later. > > > > + synchronize_rcu(); > > + > > + pr_notice("'%s': %s complete\n", klp_transition_patch->mod->name, > > + klp_target_state == KLP_PATCHED ? "patching" : "unpatching"); > > + > > + /* we're done, now cleanup the data structures */ > > + klp_complete_transition(); > > + > > + return true; > > +} > > + > > +/* > > + * This function can be called in the middle of an existing transition to > > + * reverse the direction of the target patch state. This can be done to > > + * effectively cancel an existing enable or disable operation if there are any > > + * tasks which are stuck in the initial patch state. > > + */ > > +void klp_reverse_transition(void) > > +{ > > + klp_transition_patch->enabled = !klp_transition_patch->enabled; > > + > > + klp_target_state = !klp_target_state; > > + > > + /* > > + * Enforce the order of the write to klp_target_state above and the > > + * TIF_PATCH_PENDING writes in klp_start_transition() to ensure that > > + * klp_update_patch_state() doesn't set a wrong task->patch_state. > > + */ > > + smp_wmb(); > > I would call rcu_synchronize() here to make sure that > klp_update_patch_state() calls will not set > an outdated task->patch_state. > > Note that smp_wmb() is not enough. We do not check TIF_PATCH_PENDING > in klp_try_switch_task(). There is a tiny race: > > CPU1 CPU2 > > klp_update_patch_state() > > if (test_and clear(task, TIF) > READ_ONCE(klp_target_state); > > mutex_lock(klp_lock); > > klp_reverse_transition() > klp_target_state = > !klp_target_state; > > klp_start_transition() > > mutex_unlock(klp_lock); > > <switch to another process> > > klp_transition_work_fn() > mutex_lock(klp_lock); > klp_try_complete_transition() > klp_try_switch_task() > if (task->patch_state == > klp_target_state) > return true; > > task->patch_state = <outdated_value>; > > klp_ftrace_handler() > > BANG: klp_ftrace_handler() will use wrong implementation according > to the outdated task->patch_state. At the same time, > klp_transition() is not blocked by the task because it thinks > that it has a correct state. Good find! > > + > > + klp_start_transition(); > > +} > > + > > diff --git a/samples/livepatch/livepatch-sample.c b/samples/livepatch/livepatch-sample.c > > index e34f871..bb61c65 100644 > > --- a/samples/livepatch/livepatch-sample.c > > +++ b/samples/livepatch/livepatch-sample.c > > @@ -17,6 +17,8 @@ > > * along with this program; if not, see <http://www.gnu.org/licenses/>. > > */ > > > > +#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt > > + > > #include <linux/module.h> > > #include <linux/kernel.h> > > #include <linux/livepatch.h> > > @@ -69,6 +71,11 @@ static int livepatch_init(void) > > { > > int ret; > > > > + if (!klp_have_reliable_stack() && !patch.immediate) { > > + pr_notice("disabling consistency model!\n"); > > + patch.immediate = true; > > + } > > I am scared to have this in the sample module. It makes sense > to use the consistency model even for immediate patches because > it allows to remove them. But this must not be used for patches > that really require the consistency model. We should add > a big fat warning at least. I did this so that the sample module would still work for non-x86_64 arches, for which there's currently no way to patch kthreads. Notice I did add a warning: pr_notice("disabling consistency model!\n"); Is the warning not fat enough? > > + > > ret = klp_register_patch(&patch); > > if (ret) > > return ret; > > I like the patch. All the problems that I found look solvable. > I think that we are on the right way. Thank you for the excellent review!
On Wed 2016-12-21 15:25:05, Josh Poimboeuf wrote: > On Tue, Dec 20, 2016 at 06:32:46PM +0100, Petr Mladek wrote: > > On Thu 2016-12-08 12:08:38, Josh Poimboeuf wrote: > > > Change livepatch to use 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 or data semantics. This is the > > > biggest remaining piece needed to make livepatch more generally useful. > > > > > > [1] https://lkml.kernel.org/r/20141107140458.GA21774@suse.cz > > > > > > --- /dev/null > > > +++ b/kernel/livepatch/transition.c > > > +/* > > > + * Initialize the global target patch state and all tasks to the initial patch > > > + * state, and initialize all function transition states to true in preparation > > > + * for patching or unpatching. > > > + */ > > > +void klp_init_transition(struct klp_patch *patch, int state) > > > +{ > > > + struct task_struct *g, *task; > > > + unsigned int cpu; > > > + struct klp_object *obj; > > > + struct klp_func *func; > > > + int initial_state = !state; > > > + > > > + WARN_ON_ONCE(klp_target_state != KLP_UNDEFINED); > > > + > > > + klp_transition_patch = patch; > > > + > > > + /* > > > + * Set the global target patch state which tasks will switch to. This > > > + * has no effect until the TIF_PATCH_PENDING flags get set later. > > > + */ > > > + klp_target_state = state; > > > + > > > + /* > > > + * If the patch can be applied or reverted immediately, skip the > > > + * per-task transitions. > > > + */ > > > + if (patch->immediate) > > > + return; > > > + > > > + /* > > > + * Initialize all tasks to the initial patch state to prepare them for > > > + * switching to the target state. > > > + */ > > > + read_lock(&tasklist_lock); > > > + for_each_process_thread(g, task) { > > > + WARN_ON_ONCE(task->patch_state != KLP_UNDEFINED); > > > + task->patch_state = initial_state; > > > + } > > > + read_unlock(&tasklist_lock); > > > + > > > + /* > > > + * Ditto for the idle "swapper" tasks. > > > + */ > > > + get_online_cpus(); > > > + for_each_online_cpu(cpu) { > > > + task = idle_task(cpu); > > > + WARN_ON_ONCE(task->patch_state != KLP_UNDEFINED); > > > + task->patch_state = initial_state; > > > + } > > > + put_online_cpus(); > > > > We allow to add/remove CPUs here. I am afraid that we will also need > > to add a cpu coming/going handler that will set the task->patch_state > > the right way. We must not set the klp_target_state until all ftrace > > handlers are ready. > > What if we instead just change the above to use for_each_possible_cpu()? > We could do the same in klp_complete_transition(). I like this idea. It seems that there is idle task for each possible cpu, see idle_threads_init(). IMHO, we should do the same everytime we do anything with the idle tasks. I mean in klp_start_transition, klp_try_complete_transition() and also complete_transition(). Then they will be handled like any other processes and we do not need to think of any special races. > > > + /* > > > + * Enforce the order of the task->patch_state initializations and the > > > + * func->transition updates to ensure that, in the enable path, > > > + * klp_ftrace_handler() doesn't see a func in transition with a > > > + * task->patch_state of KLP_UNDEFINED. > > > + */ > > > + smp_wmb(); > > > + > > > + /* > > > + * Set the func transition states so klp_ftrace_handler() will know to > > > + * switch to the transition logic. > > > + * > > > + * When patching, the funcs aren't yet in the func_stack and will be > > > + * made visible to the ftrace handler shortly by the calls to > > > + * klp_patch_object(). > > > + * > > > + * When unpatching, the funcs are already in the func_stack and so are > > > + * already visible to the ftrace handler. > > > + */ > > > + klp_for_each_object(patch, obj) > > > + klp_for_each_func(obj, func) > > > + func->transition = true; > > > +} > > > + > > > +/* > > > + * Start the transition to the specified target patch state so tasks can begin > > > + * switching to it. > > > + */ > > > +void klp_start_transition(void) > > > +{ > > > + struct task_struct *g, *task; > > > + unsigned int cpu; > > > + > > > + WARN_ON_ONCE(klp_target_state == KLP_UNDEFINED); > > > + > > > + pr_notice("'%s': %s...\n", klp_transition_patch->mod->name, > > > + klp_target_state == KLP_PATCHED ? "patching" : "unpatching"); > > > + > > > + /* > > > + * If the patch can be applied or reverted immediately, skip the > > > + * per-task transitions. > > > + */ > > > + if (klp_transition_patch->immediate) > > > + return; > > > + > > > + /* > > > + * Mark all normal tasks as needing a patch state update. As they pass > > > + * through the syscall barrier they'll switch over to the target state > > > + * (unless we switch them in klp_try_complete_transition() first). > > > + */ > > > + read_lock(&tasklist_lock); > > > + for_each_process_thread(g, task) > > > + set_tsk_thread_flag(task, TIF_PATCH_PENDING); > > > > This is called also from klp_reverse_transition(). We should set it > > only when the task need migration. Also we should clear it when > > the task is in the right state already. > > > > It is not only optimization. It actually solves a race between > > klp_complete_transition() and klp_update_patch_state(), see below. > > I agree about the race, but if I did: > > for_each_process_thread(g, task) { > if (task->patch_state != klp_target_state) > set_tsk_thread_flag(task, TIF_PATCH_PENDING); > else > clear_tsk_thread_flag(task, TIF_PATCH_PENDING); > } > > It would still leave a small window where TIF_PATCH_PENDING gets set for > an already patched task, if klp_update_patch_state() is running at the > same time. I see your point. Well, it seems that it is more complicated: The race would be possible only when this was called from klp_reverse_transition(). But we need to call there rcu_synchronize() to prevent races with klp_update_patch_state() also to prevent prelimitary patch completion. The result is: if (task->patch_state != klp_target_state) { # it means that the task was already migrated before # we reverted klp_target_state. It means that # the TIF flag was already cleared, the related # klp_update_patch_state() already finished (thanks # to rcu_synchronize() and new one will be called # only when we set the flag again # => it is safe to set it # we should also check and warn when the TIF flag # was not clear before we set it here else # the task was not migrated before we reverted # klp_target_state. klp_update_patch_state() # could run in parallel but it will do the same # what we do, clear TIF flag and keep the patch_state # as is # => it is safe to clear it I agree that this is complex like hell. But it also allows use to check that things work as we expect. If we always set the flag here and always clear it later, we might hide a bug. If we want to make it slightly more straightforward, we might clear TIF flags in klp_reverse_transaction() before we revert klp_target_state. The later rcu_synchronize() should make sure that all migrations are finished and non-will run in parallel. Then we could set the TIF flag only where needed here. > > > + read_unlock(&tasklist_lock); > > > + > > > + /* > > > + * Ditto for the idle "swapper" tasks, though they never cross the > > > + * syscall barrier. Instead they switch over in cpu_idle_loop(). > > > + */ > > > + get_online_cpus(); > > > + for_each_online_cpu(cpu) > > > + set_tsk_thread_flag(idle_task(cpu), TIF_PATCH_PENDING); > > > + put_online_cpus(); > > > > Also this stage need to be somehow handled by CPU coming/going > > handlers. > > Here I think we could automatically switch any offline CPUs' idle tasks. > And something similar in klp_try_complete_transition(). We still need to make sure to do not race with the cpu_up()/cpu_down() calls. I would use here the trick with for_each_possible_cpu() and let the migration for the stack check. > > > +} > > > + > > > +/* > > > + * The transition to the target patch state is complete. Clean up the data > > > + * structures. > > > + */ > > > +void klp_complete_transition(void) > > > +{ > > > + struct klp_object *obj; > > > + struct klp_func *func; > > > + struct task_struct *g, *task; > > > + unsigned int cpu; > > > + > > > + if (klp_transition_patch->immediate) > > > + goto done; > > > + > > > + klp_for_each_object(klp_transition_patch, obj) > > > + klp_for_each_func(obj, func) > > > + func->transition = false; > > > > We should call rcu_synchronize() here. Otherwise, there > > might be a race, see below: > > > > CPU1 CPU2 > > > > klp_ftrace_handler() > > if (unlikely(func->transition)) > > // still true > > > > klp_complete_transition() > > func->transition = false; > > task->patch_state = > > KLP_UNDEFINED; > > > > patch_state = current->patch_state; > > > > WARN_ON(patch_state == KLP_UNDEFINED); > > > > BANG!: We print the warning. > > This shouldn't be possible because klp_try_complete_transition() calls > rcu_synchronize() before calling klp_complete_transition(). So by the > time klp_complete_transition() is called, the ftrace handler can no > longer see the affected func. See the comment for rcu_synchronize() in > klp_try_complete_transition(). But rcu_synchronize() in klp_try_complete_transition() will help only when the patch is being disabled. The ftrace handler will still see this function and race when the patch is being enabled. But you are partially right. We need the rcu_synchronize() here only when the patch is being enabled. It actually matches my comments in klp_try_complete_transition() where I suggested to call it only when the patch is being removed. > > Note that that smp_wmb() is enough in klp_init_transition() > > but it is not enough here. We need to wait longer once > > someone might be inside the if (true) code. > > > > > + read_lock(&tasklist_lock); > > > + for_each_process_thread(g, task) { > > > + clear_tsk_thread_flag(task, TIF_PATCH_PENDING); > > > + task->patch_state = KLP_UNDEFINED; > > > + } > > > + read_unlock(&tasklist_lock); > > > + > > > + get_online_cpus(); > > > + for_each_online_cpu(cpu) { > > > + task = idle_task(cpu); > > > + clear_tsk_thread_flag(task, TIF_PATCH_PENDING); > > > > If TIF_PATCH_PENDING flag is set here it means that > > klp_update_patch_state() might get triggered and it might > > put wrong value into task->patch_state. > > > > We must make sure that all task have this cleared before > > calling this function. This is another reason why > > klp_init_transition() should set the flag only when > > transition is needed. > > > > We should only check the state here. > > > > It still might make sense to clear it when it is set wrongly. > > But the question is if it is really safe to continue. I am > > afraid that it is not. It would mean that the consistency > > model is broken and we are in strange state. > > As I mentioned above, with your proposal I think there could still be a > task with a spurious set TIF_PATCH_PENDING at this point. I believe that it could not be here if we add that rcu_synchronize() into klp_reverse_transition(). > Maybe instead we should clear all the TIF_PATCH_PENDING flags before the > synchronize_rcu() in klp_try_complete_transition(). It might work. But I believe that we do not need this. If we do it, we might hide a bug. > > > + task->patch_state = KLP_UNDEFINED; > > > + } > > > + put_online_cpus(); > > > + > > > +done: > > > + klp_target_state = KLP_UNDEFINED; > > > + klp_transition_patch = NULL; > > > +} > > > > [...] > > > > > + > > > +/* > > > + * Try to switch all remaining tasks to the target patch state by walking the > > > + * stacks of sleeping tasks and looking for any to-be-patched or > > > + * to-be-unpatched functions. If such functions are found, the task can't be > > > + * switched yet. > > > + * > > > + * If any tasks are still stuck in the initial patch state, schedule a retry. > > > + */ > > > +bool klp_try_complete_transition(void) > > > +{ > > > + unsigned int cpu; > > > + struct task_struct *g, *task; > > > + bool complete = true; > > > + > > > + WARN_ON_ONCE(klp_target_state == KLP_UNDEFINED); > > > + > > > + /* > > > + * If the patch can be applied or reverted immediately, skip the > > > + * per-task transitions. > > > + */ > > > + if (klp_transition_patch->immediate) > > > + goto success; > > > + > > > + /* > > > + * Try to switch the tasks to the target patch state by walking their > > > + * stacks and looking for any to-be-patched or to-be-unpatched > > > + * functions. If such functions are found on a stack, or if the stack > > > + * is deemed unreliable, the task can't be switched yet. > > > + * > > > + * Usually this will transition most (or all) of the tasks on a system > > > + * unless the patch includes changes to a very common function. > > > + */ > > > + read_lock(&tasklist_lock); > > > + for_each_process_thread(g, task) > > > + if (!klp_try_switch_task(task)) > > > + complete = false; > > > + read_unlock(&tasklist_lock); > > > + > > > + /* > > > + * Ditto for the idle "swapper" tasks. > > > + */ > > > + get_online_cpus(); > > > + for_each_online_cpu(cpu) > > > + if (!klp_try_switch_task(idle_task(cpu))) > > > + complete = false; > > > + put_online_cpus(); > > > + > > > + /* > > > + * Some tasks weren't able to be switched over. Try again later and/or > > > + * wait for other methods like syscall barrier switching. > > > + */ > > > + if (!complete) > > > + return false; > > > + > > > +success: > > > + > > > + /* > > > + * When unpatching, all tasks have transitioned to KLP_UNPATCHED so we > > > + * can now remove the new functions from the func_stack. > > > + */ > > > + if (klp_target_state == KLP_UNPATCHED) > > > + klp_unpatch_objects(klp_transition_patch); > > > + > > > + /* > > > + * Wait for all RCU read-side critical sections to complete. > > > + * > > > + * This has two purposes: > > > + * > > > + * 1) Ensure all existing critical sections in klp_update_patch_state() > > > + * complete, so task->patch_state won't be unexpectedly updated > > > + * later. > > > > We should not be here if anyone still might be in klp_update_patch_state(). > > Depends on our discussion about conditionally setting TIF_PATCH_PENDING. Yup. > > > + * > > > + * 2) When unpatching, don't allow any existing instances of > > > + * klp_ftrace_handler() to access any obsolete funcs before we reset > > > + * the func transition states to false. Otherwise the handler may > > > + * see the deleted "new" func, see that it's not in transition, and > > > + * wrongly pick the new version of the function. > > > + */ > > > > This makes sense but it too me long time to understand. I wonder if > > this might be better: > > > > /* > > * Make sure that the function is removed from ops->func_stack > > * before we clear func->transition. Otherwise the handler may > > * pick the wrong version. > > */ > > Sounds good. > > > And I would call this only when the patch is being removed > > > > if (klp_target_state = KLP_UNPATCHED) > > synchronize_rcu(); > > Depends on our discussion about conditionally setting TIF_PATCH_PENDING. And yup. > > I think that this was the reason to remove WARN_ON_ONCE(!func) > > in klp_ftrace_handler(). But this is not related. If this was > > the last entry in the list, we removed the ftrace_handler > > before removing the last entry. And unregister_ftrace_function() > > calls rcu_synchronize() to prevent calling the handler later. > > > > > > > + synchronize_rcu(); > > > + > > > + pr_notice("'%s': %s complete\n", klp_transition_patch->mod->name, > > > + klp_target_state == KLP_PATCHED ? "patching" : "unpatching"); > > > + > > > + /* we're done, now cleanup the data structures */ > > > + klp_complete_transition(); > > > + > > > + return true; > > > +} > > > + > > > +/* > > > + * This function can be called in the middle of an existing transition to > > > + * reverse the direction of the target patch state. This can be done to > > > + * effectively cancel an existing enable or disable operation if there are any > > > + * tasks which are stuck in the initial patch state. > > > + */ > > > +void klp_reverse_transition(void) > > > +{ > > > + klp_transition_patch->enabled = !klp_transition_patch->enabled; > > > + > > > + klp_target_state = !klp_target_state; > > > + > > > + /* > > > + * Enforce the order of the write to klp_target_state above and the > > > + * TIF_PATCH_PENDING writes in klp_start_transition() to ensure that > > > + * klp_update_patch_state() doesn't set a wrong task->patch_state. > > > + */ > > > + smp_wmb(); > > > > I would call rcu_synchronize() here to make sure that > > klp_update_patch_state() calls will not set > > an outdated task->patch_state. > > > > Note that smp_wmb() is not enough. We do not check TIF_PATCH_PENDING > > in klp_try_switch_task(). There is a tiny race: > > > > CPU1 CPU2 > > > > klp_update_patch_state() > > > > if (test_and clear(task, TIF) > > READ_ONCE(klp_target_state); > > > > mutex_lock(klp_lock); > > > > klp_reverse_transition() > > klp_target_state = > > !klp_target_state; > > > > klp_start_transition() > > > > mutex_unlock(klp_lock); > > > > <switch to another process> > > > > klp_transition_work_fn() > > mutex_lock(klp_lock); > > klp_try_complete_transition() > > klp_try_switch_task() > > if (task->patch_state == > > klp_target_state) > > return true; > > > > task->patch_state = <outdated_value>; > > > > klp_ftrace_handler() > > > > BANG: klp_ftrace_handler() will use wrong implementation according > > to the outdated task->patch_state. At the same time, > > klp_transition() is not blocked by the task because it thinks > > that it has a correct state. > > Good find! This is important in the puzzle. > > > + > > > + klp_start_transition(); > > > +} > > > + > > > diff --git a/samples/livepatch/livepatch-sample.c b/samples/livepatch/livepatch-sample.c > > > index e34f871..bb61c65 100644 > > > --- a/samples/livepatch/livepatch-sample.c > > > +++ b/samples/livepatch/livepatch-sample.c > > > @@ -17,6 +17,8 @@ > > > * along with this program; if not, see <http://www.gnu.org/licenses/>. > > > */ > > > > > > +#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt > > > + > > > #include <linux/module.h> > > > #include <linux/kernel.h> > > > #include <linux/livepatch.h> > > > @@ -69,6 +71,11 @@ static int livepatch_init(void) > > > { > > > int ret; > > > > > > + if (!klp_have_reliable_stack() && !patch.immediate) { > > > + pr_notice("disabling consistency model!\n"); > > > + patch.immediate = true; > > > + } > > > > I am scared to have this in the sample module. It makes sense > > to use the consistency model even for immediate patches because > > it allows to remove them. But this must not be used for patches > > that really require the consistency model. We should add > > a big fat warning at least. > > I did this so that the sample module would still work for non-x86_64 > arches, for which there's currently no way to patch kthreads. > > Notice I did add a warning: > > pr_notice("disabling consistency model!\n"); > > Is the warning not fat enough? The warning does not explain who did it, why, if it is safe, and when this could be used. I suggest a comment like: /* * WARNING: Use this check only when you know what you do! * * This sample patch does not change the semantic of the data structures, * locks, or return adresses. It is safe to be applied immediately. * But we want to test and use the consistency model on supported * architectures. It allows to remove the patch module. * * See Documentation/livepatch/livepatch.txt for more details, please. */ Also the message might be more explicit. pr_notice("livepatch-sample: The consistency model is not supported on this architecture. Using the immediate model that is safe enough.\n"); Alternatively, we might allow more values for patch.immediate, e.g. enum klp_consistency_model { KLP_CM_IMMEDIATE, KLP_CM_TASK, KLP_CM_TASK_OR_IMMEDIATE, }; Then we could do the decision on the kernel side. But I am not sure if this would be widely used and it it is worth the complication. Best Regards, Petr PS: Merry Christmas and happy new year! I am not sure if I will be able to do another deep dive into this code until next year.
On Thu, Dec 22, 2016 at 03:34:52PM +0100, Petr Mladek wrote: > On Wed 2016-12-21 15:25:05, Josh Poimboeuf wrote: > > On Tue, Dec 20, 2016 at 06:32:46PM +0100, Petr Mladek wrote: > > > On Thu 2016-12-08 12:08:38, Josh Poimboeuf wrote: > > > > Change livepatch to use 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 or data semantics. This is the > > > > biggest remaining piece needed to make livepatch more generally useful. > > > > > > > > [1] https://lkml.kernel.org/r/20141107140458.GA21774@suse.cz > > > > > > > > --- /dev/null > > > > +++ b/kernel/livepatch/transition.c > > > > +/* > > > > + * Initialize the global target patch state and all tasks to the initial patch > > > > + * state, and initialize all function transition states to true in preparation > > > > + * for patching or unpatching. > > > > + */ > > > > +void klp_init_transition(struct klp_patch *patch, int state) > > > > +{ > > > > + struct task_struct *g, *task; > > > > + unsigned int cpu; > > > > + struct klp_object *obj; > > > > + struct klp_func *func; > > > > + int initial_state = !state; > > > > + > > > > + WARN_ON_ONCE(klp_target_state != KLP_UNDEFINED); > > > > + > > > > + klp_transition_patch = patch; > > > > + > > > > + /* > > > > + * Set the global target patch state which tasks will switch to. This > > > > + * has no effect until the TIF_PATCH_PENDING flags get set later. > > > > + */ > > > > + klp_target_state = state; > > > > + > > > > + /* > > > > + * If the patch can be applied or reverted immediately, skip the > > > > + * per-task transitions. > > > > + */ > > > > + if (patch->immediate) > > > > + return; > > > > + > > > > + /* > > > > + * Initialize all tasks to the initial patch state to prepare them for > > > > + * switching to the target state. > > > > + */ > > > > + read_lock(&tasklist_lock); > > > > + for_each_process_thread(g, task) { > > > > + WARN_ON_ONCE(task->patch_state != KLP_UNDEFINED); > > > > + task->patch_state = initial_state; > > > > + } > > > > + read_unlock(&tasklist_lock); > > > > + > > > > + /* > > > > + * Ditto for the idle "swapper" tasks. > > > > + */ > > > > + get_online_cpus(); > > > > + for_each_online_cpu(cpu) { > > > > + task = idle_task(cpu); > > > > + WARN_ON_ONCE(task->patch_state != KLP_UNDEFINED); > > > > + task->patch_state = initial_state; > > > > + } > > > > + put_online_cpus(); > > > > > > We allow to add/remove CPUs here. I am afraid that we will also need > > > to add a cpu coming/going handler that will set the task->patch_state > > > the right way. We must not set the klp_target_state until all ftrace > > > handlers are ready. > > > > What if we instead just change the above to use for_each_possible_cpu()? > > We could do the same in klp_complete_transition(). > > I like this idea. It seems that there is idle task for each possible > cpu, see idle_threads_init(). > > IMHO, we should do the same everytime we do anything with the idle > tasks. I mean in klp_start_transition, klp_try_complete_transition() > and also complete_transition(). > > Then they will be handled like any other processes and we do not need > to think of any special races. More on this below. > > > > + /* > > > > + * Enforce the order of the task->patch_state initializations and the > > > > + * func->transition updates to ensure that, in the enable path, > > > > + * klp_ftrace_handler() doesn't see a func in transition with a > > > > + * task->patch_state of KLP_UNDEFINED. > > > > + */ > > > > + smp_wmb(); > > > > + > > > > + /* > > > > + * Set the func transition states so klp_ftrace_handler() will know to > > > > + * switch to the transition logic. > > > > + * > > > > + * When patching, the funcs aren't yet in the func_stack and will be > > > > + * made visible to the ftrace handler shortly by the calls to > > > > + * klp_patch_object(). > > > > + * > > > > + * When unpatching, the funcs are already in the func_stack and so are > > > > + * already visible to the ftrace handler. > > > > + */ > > > > + klp_for_each_object(patch, obj) > > > > + klp_for_each_func(obj, func) > > > > + func->transition = true; > > > > +} > > > > + > > > > +/* > > > > + * Start the transition to the specified target patch state so tasks can begin > > > > + * switching to it. > > > > + */ > > > > +void klp_start_transition(void) > > > > +{ > > > > + struct task_struct *g, *task; > > > > + unsigned int cpu; > > > > + > > > > + WARN_ON_ONCE(klp_target_state == KLP_UNDEFINED); > > > > + > > > > + pr_notice("'%s': %s...\n", klp_transition_patch->mod->name, > > > > + klp_target_state == KLP_PATCHED ? "patching" : "unpatching"); > > > > + > > > > + /* > > > > + * If the patch can be applied or reverted immediately, skip the > > > > + * per-task transitions. > > > > + */ > > > > + if (klp_transition_patch->immediate) > > > > + return; > > > > + > > > > + /* > > > > + * Mark all normal tasks as needing a patch state update. As they pass > > > > + * through the syscall barrier they'll switch over to the target state > > > > + * (unless we switch them in klp_try_complete_transition() first). > > > > + */ > > > > + read_lock(&tasklist_lock); > > > > + for_each_process_thread(g, task) > > > > + set_tsk_thread_flag(task, TIF_PATCH_PENDING); > > > > > > This is called also from klp_reverse_transition(). We should set it > > > only when the task need migration. Also we should clear it when > > > the task is in the right state already. > > > > > > It is not only optimization. It actually solves a race between > > > klp_complete_transition() and klp_update_patch_state(), see below. > > > > I agree about the race, but if I did: > > > > for_each_process_thread(g, task) { > > if (task->patch_state != klp_target_state) > > set_tsk_thread_flag(task, TIF_PATCH_PENDING); > > else > > clear_tsk_thread_flag(task, TIF_PATCH_PENDING); > > } > > > > It would still leave a small window where TIF_PATCH_PENDING gets set for > > an already patched task, if klp_update_patch_state() is running at the > > same time. > > I see your point. Well, it seems that it is more complicated: > > The race would be possible only when this was called from > klp_reverse_transition(). But we need to call there > rcu_synchronize() to prevent races with klp_update_patch_state() > also to prevent prelimitary patch completion. > > The result is: > > if (task->patch_state != klp_target_state) { > # it means that the task was already migrated before > # we reverted klp_target_state. It means that > # the TIF flag was already cleared, the related > # klp_update_patch_state() already finished (thanks > # to rcu_synchronize() and new one will be called > # only when we set the flag again > # => it is safe to set it > > # we should also check and warn when the TIF flag > # was not clear before we set it here > > > else > > # the task was not migrated before we reverted > # klp_target_state. klp_update_patch_state() > # could run in parallel but it will do the same > # what we do, clear TIF flag and keep the patch_state > # as is > # => it is safe to clear it > > > I agree that this is complex like hell. But it also allows use to > check that things work as we expect. Ouch. I agree that it seems safe but it's way too hard to reason about. And then it gets worse if you try to think about what happens when adding another reverse operation. > > If we always set the flag here and always clear it later, we might > hide a bug. > > If we want to make it slightly more straightforward, we might > clear TIF flags in klp_reverse_transaction() before we revert > klp_target_state. The later rcu_synchronize() should make sure > that all migrations are finished and non-will run in parallel. > Then we could set the TIF flag only where needed here. I think this last paragraph is important. It would simplify things greatly and ensure we won't have klp_update_patch_state() changing things in the background. > > > > + read_unlock(&tasklist_lock); > > > > + > > > > + /* > > > > + * Ditto for the idle "swapper" tasks, though they never cross the > > > > + * syscall barrier. Instead they switch over in cpu_idle_loop(). > > > > + */ > > > > + get_online_cpus(); > > > > + for_each_online_cpu(cpu) > > > > + set_tsk_thread_flag(idle_task(cpu), TIF_PATCH_PENDING); > > > > + put_online_cpus(); > > > > > > Also this stage need to be somehow handled by CPU coming/going > > > handlers. > > > > Here I think we could automatically switch any offline CPUs' idle tasks. > > And something similar in klp_try_complete_transition(). > > We still need to make sure to do not race with the cpu_up()/cpu_down() > calls. Hm, maybe we'd need to call cpu_hotplug_disable() before switching the offline idle tasks? > I would use here the trick with for_each_possible_cpu() and let > the migration for the stack check. There are a few issues with that: 1) The idle task of a missing CPU doesn't *have* a stack, so it doesn't make much sense to try to check it. 2) We can't rely *only* on the stack check, because not all arches have it. The other way to migrate idle tasks is from the idle loop switch point. But if the task's CPU is down, its idle loop isn't running so it can't migrate. (Note this is currently a theoretical point: we currently don't allow such arches to use the consistency model anyway because there's no way for them to migrate kthreads.) > > > > +} > > > > + > > > > +/* > > > > + * The transition to the target patch state is complete. Clean up the data > > > > + * structures. > > > > + */ > > > > +void klp_complete_transition(void) > > > > +{ > > > > + struct klp_object *obj; > > > > + struct klp_func *func; > > > > + struct task_struct *g, *task; > > > > + unsigned int cpu; > > > > + > > > > + if (klp_transition_patch->immediate) > > > > + goto done; > > > > + > > > > + klp_for_each_object(klp_transition_patch, obj) > > > > + klp_for_each_func(obj, func) > > > > + func->transition = false; > > > > > > We should call rcu_synchronize() here. Otherwise, there > > > might be a race, see below: > > > > > > CPU1 CPU2 > > > > > > klp_ftrace_handler() > > > if (unlikely(func->transition)) > > > // still true > > > > > > klp_complete_transition() > > > func->transition = false; > > > task->patch_state = > > > KLP_UNDEFINED; > > > > > > patch_state = current->patch_state; > > > > > > WARN_ON(patch_state == KLP_UNDEFINED); > > > > > > BANG!: We print the warning. > > > > This shouldn't be possible because klp_try_complete_transition() calls > > rcu_synchronize() before calling klp_complete_transition(). So by the > > time klp_complete_transition() is called, the ftrace handler can no > > longer see the affected func. See the comment for rcu_synchronize() in > > klp_try_complete_transition(). > > But rcu_synchronize() in klp_try_complete_transition() will help only > when the patch is being disabled. The ftrace handler will still see > this function and race when the patch is being enabled. > > But you are partially right. We need the rcu_synchronize() here > only when the patch is being enabled. It actually matches my comments > in klp_try_complete_transition() where I suggested to call it > only when the patch is being removed. Sorry, for some reason I think I saw KLP_UNPATCHED in your example instead of KLP_UNDEFINED. I get it now. > > > Note that that smp_wmb() is enough in klp_init_transition() > > > but it is not enough here. We need to wait longer once > > > someone might be inside the if (true) code. > > > > > > > + read_lock(&tasklist_lock); > > > > + for_each_process_thread(g, task) { > > > > + clear_tsk_thread_flag(task, TIF_PATCH_PENDING); > > > > + task->patch_state = KLP_UNDEFINED; > > > > + } > > > > + read_unlock(&tasklist_lock); > > > > + > > > > + get_online_cpus(); > > > > + for_each_online_cpu(cpu) { > > > > + task = idle_task(cpu); > > > > + clear_tsk_thread_flag(task, TIF_PATCH_PENDING); > > > > > > If TIF_PATCH_PENDING flag is set here it means that > > > klp_update_patch_state() might get triggered and it might > > > put wrong value into task->patch_state. > > > > > > We must make sure that all task have this cleared before > > > calling this function. This is another reason why > > > klp_init_transition() should set the flag only when > > > transition is needed. > > > > > > We should only check the state here. > > > > > > It still might make sense to clear it when it is set wrongly. > > > But the question is if it is really safe to continue. I am > > > afraid that it is not. It would mean that the consistency > > > model is broken and we are in strange state. > > > > As I mentioned above, with your proposal I think there could still be a > > task with a spurious set TIF_PATCH_PENDING at this point. > > I believe that it could not be here if we add that rcu_synchronize() > into klp_reverse_transition(). > > > > Maybe instead we should clear all the TIF_PATCH_PENDING flags before the > > synchronize_rcu() in klp_try_complete_transition(). > > It might work. But I believe that we do not need this. If we do it, > we might hide a bug. > > > > > > + task->patch_state = KLP_UNDEFINED; > > > > + } > > > > + put_online_cpus(); > > > > + > > > > +done: > > > > + klp_target_state = KLP_UNDEFINED; > > > > + klp_transition_patch = NULL; > > > > +} > > > > > > [...] > > > > > > > + > > > > +/* > > > > + * Try to switch all remaining tasks to the target patch state by walking the > > > > + * stacks of sleeping tasks and looking for any to-be-patched or > > > > + * to-be-unpatched functions. If such functions are found, the task can't be > > > > + * switched yet. > > > > + * > > > > + * If any tasks are still stuck in the initial patch state, schedule a retry. > > > > + */ > > > > +bool klp_try_complete_transition(void) > > > > +{ > > > > + unsigned int cpu; > > > > + struct task_struct *g, *task; > > > > + bool complete = true; > > > > + > > > > + WARN_ON_ONCE(klp_target_state == KLP_UNDEFINED); > > > > + > > > > + /* > > > > + * If the patch can be applied or reverted immediately, skip the > > > > + * per-task transitions. > > > > + */ > > > > + if (klp_transition_patch->immediate) > > > > + goto success; > > > > + > > > > + /* > > > > + * Try to switch the tasks to the target patch state by walking their > > > > + * stacks and looking for any to-be-patched or to-be-unpatched > > > > + * functions. If such functions are found on a stack, or if the stack > > > > + * is deemed unreliable, the task can't be switched yet. > > > > + * > > > > + * Usually this will transition most (or all) of the tasks on a system > > > > + * unless the patch includes changes to a very common function. > > > > + */ > > > > + read_lock(&tasklist_lock); > > > > + for_each_process_thread(g, task) > > > > + if (!klp_try_switch_task(task)) > > > > + complete = false; > > > > + read_unlock(&tasklist_lock); > > > > + > > > > + /* > > > > + * Ditto for the idle "swapper" tasks. > > > > + */ > > > > + get_online_cpus(); > > > > + for_each_online_cpu(cpu) > > > > + if (!klp_try_switch_task(idle_task(cpu))) > > > > + complete = false; > > > > + put_online_cpus(); > > > > + > > > > + /* > > > > + * Some tasks weren't able to be switched over. Try again later and/or > > > > + * wait for other methods like syscall barrier switching. > > > > + */ > > > > + if (!complete) > > > > + return false; > > > > + > > > > +success: > > > > + > > > > + /* > > > > + * When unpatching, all tasks have transitioned to KLP_UNPATCHED so we > > > > + * can now remove the new functions from the func_stack. > > > > + */ > > > > + if (klp_target_state == KLP_UNPATCHED) > > > > + klp_unpatch_objects(klp_transition_patch); > > > > + > > > > + /* > > > > + * Wait for all RCU read-side critical sections to complete. > > > > + * > > > > + * This has two purposes: > > > > + * > > > > + * 1) Ensure all existing critical sections in klp_update_patch_state() > > > > + * complete, so task->patch_state won't be unexpectedly updated > > > > + * later. > > > > > > We should not be here if anyone still might be in klp_update_patch_state(). > > > > Depends on our discussion about conditionally setting TIF_PATCH_PENDING. > > Yup. > > > > > + * > > > > + * 2) When unpatching, don't allow any existing instances of > > > > + * klp_ftrace_handler() to access any obsolete funcs before we reset > > > > + * the func transition states to false. Otherwise the handler may > > > > + * see the deleted "new" func, see that it's not in transition, and > > > > + * wrongly pick the new version of the function. > > > > + */ > > > > > > This makes sense but it too me long time to understand. I wonder if > > > this might be better: > > > > > > /* > > > * Make sure that the function is removed from ops->func_stack > > > * before we clear func->transition. Otherwise the handler may > > > * pick the wrong version. > > > */ > > > > Sounds good. > > > > > And I would call this only when the patch is being removed > > > > > > if (klp_target_state = KLP_UNPATCHED) > > > synchronize_rcu(); > > > > Depends on our discussion about conditionally setting TIF_PATCH_PENDING. > > And yup. > > > > I think that this was the reason to remove WARN_ON_ONCE(!func) > > > in klp_ftrace_handler(). But this is not related. If this was > > > the last entry in the list, we removed the ftrace_handler > > > before removing the last entry. And unregister_ftrace_function() > > > calls rcu_synchronize() to prevent calling the handler later. > > > > > > > > > > + synchronize_rcu(); > > > > + > > > > + pr_notice("'%s': %s complete\n", klp_transition_patch->mod->name, > > > > + klp_target_state == KLP_PATCHED ? "patching" : "unpatching"); > > > > + > > > > + /* we're done, now cleanup the data structures */ > > > > + klp_complete_transition(); > > > > + > > > > + return true; > > > > +} > > > > + > > > > +/* > > > > + * This function can be called in the middle of an existing transition to > > > > + * reverse the direction of the target patch state. This can be done to > > > > + * effectively cancel an existing enable or disable operation if there are any > > > > + * tasks which are stuck in the initial patch state. > > > > + */ > > > > +void klp_reverse_transition(void) > > > > +{ > > > > + klp_transition_patch->enabled = !klp_transition_patch->enabled; > > > > + > > > > + klp_target_state = !klp_target_state; > > > > + > > > > + /* > > > > + * Enforce the order of the write to klp_target_state above and the > > > > + * TIF_PATCH_PENDING writes in klp_start_transition() to ensure that > > > > + * klp_update_patch_state() doesn't set a wrong task->patch_state. > > > > + */ > > > > + smp_wmb(); > > > > > > I would call rcu_synchronize() here to make sure that > > > klp_update_patch_state() calls will not set > > > an outdated task->patch_state. > > > > > > Note that smp_wmb() is not enough. We do not check TIF_PATCH_PENDING > > > in klp_try_switch_task(). There is a tiny race: > > > > > > CPU1 CPU2 > > > > > > klp_update_patch_state() > > > > > > if (test_and clear(task, TIF) > > > READ_ONCE(klp_target_state); > > > > > > mutex_lock(klp_lock); > > > > > > klp_reverse_transition() > > > klp_target_state = > > > !klp_target_state; > > > > > > klp_start_transition() > > > > > > mutex_unlock(klp_lock); > > > > > > <switch to another process> > > > > > > klp_transition_work_fn() > > > mutex_lock(klp_lock); > > > klp_try_complete_transition() > > > klp_try_switch_task() > > > if (task->patch_state == > > > klp_target_state) > > > return true; > > > > > > task->patch_state = <outdated_value>; > > > > > > klp_ftrace_handler() > > > > > > BANG: klp_ftrace_handler() will use wrong implementation according > > > to the outdated task->patch_state. At the same time, > > > klp_transition() is not blocked by the task because it thinks > > > that it has a correct state. > > > > Good find! > > This is important in the puzzle. > > > > > + > > > > + klp_start_transition(); > > > > +} > > > > + > > > > diff --git a/samples/livepatch/livepatch-sample.c b/samples/livepatch/livepatch-sample.c > > > > index e34f871..bb61c65 100644 > > > > --- a/samples/livepatch/livepatch-sample.c > > > > +++ b/samples/livepatch/livepatch-sample.c > > > > @@ -17,6 +17,8 @@ > > > > * along with this program; if not, see <http://www.gnu.org/licenses/>. > > > > */ > > > > > > > > +#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt > > > > + > > > > #include <linux/module.h> > > > > #include <linux/kernel.h> > > > > #include <linux/livepatch.h> > > > > @@ -69,6 +71,11 @@ static int livepatch_init(void) > > > > { > > > > int ret; > > > > > > > > + if (!klp_have_reliable_stack() && !patch.immediate) { > > > > + pr_notice("disabling consistency model!\n"); > > > > + patch.immediate = true; > > > > + } > > > > > > I am scared to have this in the sample module. It makes sense > > > to use the consistency model even for immediate patches because > > > it allows to remove them. But this must not be used for patches > > > that really require the consistency model. We should add > > > a big fat warning at least. > > > > I did this so that the sample module would still work for non-x86_64 > > arches, for which there's currently no way to patch kthreads. > > > > Notice I did add a warning: > > > > pr_notice("disabling consistency model!\n"); > > > > Is the warning not fat enough? > > The warning does not explain who did it, why, if it is safe, and when > this could be used. I suggest a comment like: > > /* > * WARNING: Use this check only when you know what you do! > * > * This sample patch does not change the semantic of the data structures, > * locks, or return adresses. It is safe to be applied immediately. > * But we want to test and use the consistency model on supported > * architectures. It allows to remove the patch module. > * > * See Documentation/livepatch/livepatch.txt for more details, please. > */ > > Also the message might be more explicit. > > pr_notice("livepatch-sample: The consistency model is not supported on > this architecture. Using the immediate model that is safe enough.\n"); Ok, will try to do something like that. > Alternatively, we might allow more values for patch.immediate, e.g. > > enum klp_consistency_model { > KLP_CM_IMMEDIATE, > KLP_CM_TASK, > KLP_CM_TASK_OR_IMMEDIATE, > }; > > Then we could do the decision on the kernel side. > But I am not sure if this would be widely used and it > it is worth the complication. I'd rather avoid that :-) > PS: Merry Christmas and happy new year! > > I am not sure if I will be able to do another deep dive into > this code until next year. Same here, I won't be around much until 2017. Cheers!
> > > diff --git a/kernel/livepatch/patch.c b/kernel/livepatch/patch.c > > > index 5efa262..e79ebb5 100644 > > > --- a/kernel/livepatch/patch.c > > > +++ b/kernel/livepatch/patch.c > > > @@ -29,6 +29,7 @@ > > > #include <linux/bug.h> > > > #include <linux/printk.h> > > > #include "patch.h" > > > +#include "transition.h" > > > > > > static LIST_HEAD(klp_ops); > > > > > > @@ -54,15 +55,53 @@ static void notrace klp_ftrace_handler(unsigned long ip, > > > { > > > struct klp_ops *ops; > > > struct klp_func *func; > > > + int patch_state; > > > > > > ops = container_of(fops, struct klp_ops, fops); > > > > > > rcu_read_lock(); > > > + > > > func = list_first_or_null_rcu(&ops->func_stack, struct klp_func, > > > stack_node); > > > - if (WARN_ON_ONCE(!func)) > > > + > > > + if (!func) > > > goto unlock; > > > > Why do you removed the WARN_ON_ONCE(), please? > > > > We still add the function on the stack before registering > > the ftrace handler. Also we unregister the ftrace handler > > before removing the the last entry from the stack. > > > > AFAIK, unregister_ftrace_function() calls rcu_synchronize()' > > to make sure that no-one is inside the handler once finished. > > Mirek knows more about it. > > Hm, this is news to me. Mirek, please share :-) Well, I think the whole thing is well described in emails I exchanged with Steven few months ago. See [1]. [1] http://lkml.kernel.org/r/alpine.LNX.2.00.1608081041060.10833@pobox.suse.cz > > If this is not true, we have a problem. For example, > > we call kfree(ops) after unregister_ftrace_function(); > > Agreed. TL;DR - we should be ok as long as we do not do crazy things in the handler, deliberate sleeping for example. WARN_ON_ONCE() may be crazy too. I think we discussed it long ago and we came to an agreement to remove it. Miroslav, very slowly going through the patch set
On Fri 2016-12-23 10:24:35, Miroslav Benes wrote: > > > > diff --git a/kernel/livepatch/patch.c b/kernel/livepatch/patch.c > > > > index 5efa262..e79ebb5 100644 > > > > --- a/kernel/livepatch/patch.c > > > > +++ b/kernel/livepatch/patch.c > > > > @@ -29,6 +29,7 @@ > > > > #include <linux/bug.h> > > > > #include <linux/printk.h> > > > > #include "patch.h" > > > > +#include "transition.h" > > > > > > > > static LIST_HEAD(klp_ops); > > > > > > > > @@ -54,15 +55,53 @@ static void notrace klp_ftrace_handler(unsigned long ip, > > > > { > > > > struct klp_ops *ops; > > > > struct klp_func *func; > > > > + int patch_state; > > > > > > > > ops = container_of(fops, struct klp_ops, fops); > > > > > > > > rcu_read_lock(); > > > > + > > > > func = list_first_or_null_rcu(&ops->func_stack, struct klp_func, > > > > stack_node); > > > > - if (WARN_ON_ONCE(!func)) > > > > + > > > > + if (!func) > > > > goto unlock; > > > > > > Why do you removed the WARN_ON_ONCE(), please? > > > > > > We still add the function on the stack before registering > > > the ftrace handler. Also we unregister the ftrace handler > > > before removing the the last entry from the stack. > > > > > > AFAIK, unregister_ftrace_function() calls rcu_synchronize()' > > > to make sure that no-one is inside the handler once finished. > > > Mirek knows more about it. > > > > Hm, this is news to me. Mirek, please share :-) > > Well, I think the whole thing is well described in emails I exchanged with > Steven few months ago. See [1]. > > [1] http://lkml.kernel.org/r/alpine.LNX.2.00.1608081041060.10833@pobox.suse.cz > > > > If this is not true, we have a problem. For example, > > > we call kfree(ops) after unregister_ftrace_function(); > > > > Agreed. > > TL;DR - we should be ok as long as we do not do crazy things in the > handler, deliberate sleeping for example. > > WARN_ON_ONCE() may be crazy too. I think we discussed it long ago and we > came to an agreement to remove it. There are definitely situations where this might hurt. For example, when we redirect a function called under logbuf_lock. On the other hand, there is a work in progress[1][2] that will mitigate this risk a lot. Also this warning would be printed only when something goes wrong. IMHO, it is worth the risk. It will succeed in 99,999% cases and it might save us some headache when debugging random crashes of the system. Anyway, if there is a reason to remove the warning, it should be described. And if it is not strictly related to this patch, it should be handled separately. [1] https://lkml.kernel.org/r/20161221143605.2272-1-sergey.senozhatsky@gmail.com [2] https://lkml.kernel.org/r/1461333180-2897-1-git-send-email-sergey.senozhatsky@gmail.com Best Regards, Petr
On Thu, 8 Dec 2016, Josh Poimboeuf wrote: > +void klp_start_transition(void) > +{ > + struct task_struct *g, *task; > + unsigned int cpu; > + > + WARN_ON_ONCE(klp_target_state == KLP_UNDEFINED); > + > + pr_notice("'%s': %s...\n", klp_transition_patch->mod->name, > + klp_target_state == KLP_PATCHED ? "patching" : "unpatching"); > + > + /* > + * If the patch can be applied or reverted immediately, skip the > + * per-task transitions. > + */ > + if (klp_transition_patch->immediate) > + return; > + > + /* > + * Mark all normal tasks as needing a patch state update. As they pass > + * through the syscall barrier they'll switch over to the target state > + * (unless we switch them in klp_try_complete_transition() first). > + */ > + read_lock(&tasklist_lock); > + for_each_process_thread(g, task) > + set_tsk_thread_flag(task, TIF_PATCH_PENDING); > + read_unlock(&tasklist_lock); > + > + /* > + * Ditto for the idle "swapper" tasks, though they never cross the > + * syscall barrier. Instead they switch over in cpu_idle_loop(). ...or we switch them in klp_try_complete_transition() first by looking at their stacks, right? I would add it to the comment. > + */ > + get_online_cpus(); > + for_each_online_cpu(cpu) > + set_tsk_thread_flag(idle_task(cpu), TIF_PATCH_PENDING); > + put_online_cpus(); > +} [...] > --- a/kernel/sched/idle.c > +++ b/kernel/sched/idle.c > @@ -9,6 +9,7 @@ > #include <linux/mm.h> > #include <linux/stackprotector.h> > #include <linux/suspend.h> > +#include <linux/livepatch.h> > > #include <asm/tlb.h> > > @@ -264,6 +265,9 @@ static void do_idle(void) > > sched_ttwu_pending(); > schedule_preempt_disabled(); > + > + if (unlikely(klp_patch_pending(current))) > + klp_update_patch_state(current); > } I think that (theoretically) this is not sufficient, if we patch a function present on an idle task's stack and one of the two following scenarios happen. 1. there is nothing to schedule on a cpu and an idle task does not leave a loop in do_idle() for some time. It may be a nonsense practically and if it is not we could solve with schedule_on_each_cpu() on an empty stub somewhere in our code. 2. there is a cpu-bound process running on one of the cpus. No chance of going to do_idle() there at all and the idle task would block the patching. We ran into it in kGraft and I tried to solve it with this new hunk in pick_next_task()... + /* + * Patching is in progress, schedule an idle task to migrate it + */ + if (kgr_in_progress_branch()) { + if (!test_bit(0, kgr_immutable) && + klp_kgraft_task_in_progress(rq->idle)) { + p = idle_sched_class.pick_next_task(rq, prev); + + return p; + } + } (kgr_in_progress_branch() is a static key basically. kgr_immutable flag solves something we don't have a problem with in upstream livepatch thanks to a combination of task->patch_state and klp_func->transition. klp_kgraft_task_in_progress() checks the livepatching TIF of a task.) It is not tested properly and it is a hack as hell so take it as that. Also note that the problem in kGraft is more serious as we don't have a stack checking there. So any livepatch could cause the issue easily. I can imagine even crazier solutions but nothing nice and pretty (which is probably impossible because the whole idea to deliberately schedule an idle task is not nice and pretty). Otherwise the patch looks good to me. I don't understand how Petr found those races there. Regards, Miroslav
> @@ -740,6 +809,14 @@ int klp_register_patch(struct klp_patch *patch) > return -ENODEV; > > /* > + * Architectures without reliable stack traces have to set > + * patch->immediate because there's currently no way to patch kthreads > + * with the consistency model. > + */ > + if (!klp_have_reliable_stack() && !patch->immediate) > + return -ENOSYS; > + I think an error message (pr_err) would be appropriate here. $ insmod patch_1.ko insmod: ERROR: could not insert module patch_1.ko: Function not implemented is not helpful much :) Miroslav
On Fri, Dec 23, 2016 at 11:18:03AM +0100, Petr Mladek wrote: > On Fri 2016-12-23 10:24:35, Miroslav Benes wrote: > > > > > diff --git a/kernel/livepatch/patch.c b/kernel/livepatch/patch.c > > > > > index 5efa262..e79ebb5 100644 > > > > > --- a/kernel/livepatch/patch.c > > > > > +++ b/kernel/livepatch/patch.c > > > > > @@ -29,6 +29,7 @@ > > > > > #include <linux/bug.h> > > > > > #include <linux/printk.h> > > > > > #include "patch.h" > > > > > +#include "transition.h" > > > > > > > > > > static LIST_HEAD(klp_ops); > > > > > > > > > > @@ -54,15 +55,53 @@ static void notrace klp_ftrace_handler(unsigned long ip, > > > > > { > > > > > struct klp_ops *ops; > > > > > struct klp_func *func; > > > > > + int patch_state; > > > > > > > > > > ops = container_of(fops, struct klp_ops, fops); > > > > > > > > > > rcu_read_lock(); > > > > > + > > > > > func = list_first_or_null_rcu(&ops->func_stack, struct klp_func, > > > > > stack_node); > > > > > - if (WARN_ON_ONCE(!func)) > > > > > + > > > > > + if (!func) > > > > > goto unlock; > > > > > > > > Why do you removed the WARN_ON_ONCE(), please? > > > > > > > > We still add the function on the stack before registering > > > > the ftrace handler. Also we unregister the ftrace handler > > > > before removing the the last entry from the stack. > > > > > > > > AFAIK, unregister_ftrace_function() calls rcu_synchronize()' > > > > to make sure that no-one is inside the handler once finished. > > > > Mirek knows more about it. > > > > > > Hm, this is news to me. Mirek, please share :-) > > > > Well, I think the whole thing is well described in emails I exchanged with > > Steven few months ago. See [1]. > > > > [1] http://lkml.kernel.org/r/alpine.LNX.2.00.1608081041060.10833@pobox.suse.cz > > > > > > If this is not true, we have a problem. For example, > > > > we call kfree(ops) after unregister_ftrace_function(); > > > > > > Agreed. > > > > TL;DR - we should be ok as long as we do not do crazy things in the > > handler, deliberate sleeping for example. > > > > WARN_ON_ONCE() may be crazy too. I think we discussed it long ago and we > > came to an agreement to remove it. > > There are definitely situations where this might hurt. For example, > when we redirect a function called under logbuf_lock. > > On the other hand, there is a work in progress[1][2] that will mitigate > this risk a lot. Also this warning would be printed only when > something goes wrong. IMHO, it is worth the risk. It will succeed > in 99,999% cases and it might save us some headache when debugging > random crashes of the system. > > Anyway, if there is a reason to remove the warning, it should be > described. And if it is not strictly related to this patch, it should > be handled separately. > > [1] https://lkml.kernel.org/r/20161221143605.2272-1-sergey.senozhatsky@gmail.com > [2] https://lkml.kernel.org/r/1461333180-2897-1-git-send-email-sergey.senozhatsky@gmail.com Yeah, I'm thinking we should keep the warning to catch any bugs in case any of our ftrace assumptions change. Maybe I should add a comment: /* * func can never be NULL because preemption should be disabled * here and unregister_ftrace_function() does the equivalent of * a synchronize_sched() before the func_stack removal. */ if (WARN_ON_ONCE(!func)) goto unlock;
On Wed, Jan 04, 2017 at 02:44:47PM +0100, Miroslav Benes wrote: > On Thu, 8 Dec 2016, Josh Poimboeuf wrote: > > > +void klp_start_transition(void) > > +{ > > + struct task_struct *g, *task; > > + unsigned int cpu; > > + > > + WARN_ON_ONCE(klp_target_state == KLP_UNDEFINED); > > + > > + pr_notice("'%s': %s...\n", klp_transition_patch->mod->name, > > + klp_target_state == KLP_PATCHED ? "patching" : "unpatching"); > > + > > + /* > > + * If the patch can be applied or reverted immediately, skip the > > + * per-task transitions. > > + */ > > + if (klp_transition_patch->immediate) > > + return; > > + > > + /* > > + * Mark all normal tasks as needing a patch state update. As they pass > > + * through the syscall barrier they'll switch over to the target state > > + * (unless we switch them in klp_try_complete_transition() first). > > + */ > > + read_lock(&tasklist_lock); > > + for_each_process_thread(g, task) > > + set_tsk_thread_flag(task, TIF_PATCH_PENDING); > > + read_unlock(&tasklist_lock); > > + > > + /* > > + * Ditto for the idle "swapper" tasks, though they never cross the > > + * syscall barrier. Instead they switch over in cpu_idle_loop(). > > ...or we switch them in klp_try_complete_transition() first by looking at > their stacks, right? I would add it to the comment. Yeah, I guess the "ditto" was intended to include the "unless we switch them in klp_try_complete_transition() first" statement from the previous comment. I'll try to make it clearer. > > + */ > > + get_online_cpus(); > > + for_each_online_cpu(cpu) > > + set_tsk_thread_flag(idle_task(cpu), TIF_PATCH_PENDING); > > + put_online_cpus(); > > +} > > [...] > > > --- a/kernel/sched/idle.c > > +++ b/kernel/sched/idle.c > > @@ -9,6 +9,7 @@ > > #include <linux/mm.h> > > #include <linux/stackprotector.h> > > #include <linux/suspend.h> > > +#include <linux/livepatch.h> > > > > #include <asm/tlb.h> > > > > @@ -264,6 +265,9 @@ static void do_idle(void) > > > > sched_ttwu_pending(); > > schedule_preempt_disabled(); > > + > > + if (unlikely(klp_patch_pending(current))) > > + klp_update_patch_state(current); > > } > > I think that (theoretically) this is not sufficient, if we patch a > function present on an idle task's stack and one of the two following > scenarios happen. Agreed, though I'd argue that these are rare edge cases which can probably be refined later, outside the scope of this patch set. > 1. there is nothing to schedule on a cpu and an idle task does not leave a > loop in do_idle() for some time. It may be a nonsense practically and if > it is not we could solve with schedule_on_each_cpu() on an empty stub > somewhere in our code. This might only be a theoretical issue, as it only happens when patching one of the idle functions themselves. If we decided that this were a real world problem, we could use something like schedule_on_each_cpu() to flush them out as you suggested. Or it could even be done from user space by briefly running a CPU-intensive program on the affected CPUs. > 2. there is a cpu-bound process running on one of the cpus. No chance of > going to do_idle() there at all and the idle task would block the > patching. To clarify I think this would only be an issue when trying to patch idle code or schedule()/__schedule(). > We ran into it in kGraft and I tried to solve it with this new > hunk in pick_next_task()... > > + /* > + * Patching is in progress, schedule an idle task to migrate it > + */ > + if (kgr_in_progress_branch()) { > + if (!test_bit(0, kgr_immutable) && > + klp_kgraft_task_in_progress(rq->idle)) { > + p = idle_sched_class.pick_next_task(rq, prev); > + > + return p; > + } > + } > > (kgr_in_progress_branch() is a static key basically. kgr_immutable flag > solves something we don't have a problem with in upstream livepatch thanks > to a combination of task->patch_state and klp_func->transition. > klp_kgraft_task_in_progress() checks the livepatching TIF of a task.) > > It is not tested properly and it is a hack as hell so take it as that. > Also note that the problem in kGraft is more serious as we don't have a > stack checking there. So any livepatch could cause the issue easily. > > I can imagine even crazier solutions but nothing nice and pretty (which is > probably impossible because the whole idea to deliberately schedule an > idle task is not nice and pretty). Yeah, that looks hairy... Since this is such a specialized case (patching the scheduler in an idle task while CPU-intensive tasks are running) this might also be more reasonably accomplished from user space by briefly SIGSTOPing the CPU hog. > Otherwise the patch looks good to me. I don't understand how Petr found > those races there. Agreed, kudos to Petr :-)
On Thu, Jan 05, 2017 at 10:34:57AM +0100, Miroslav Benes wrote: > > > @@ -740,6 +809,14 @@ int klp_register_patch(struct klp_patch *patch) > > return -ENODEV; > > > > /* > > + * Architectures without reliable stack traces have to set > > + * patch->immediate because there's currently no way to patch kthreads > > + * with the consistency model. > > + */ > > + if (!klp_have_reliable_stack() && !patch->immediate) > > + return -ENOSYS; > > + > > I think an error message (pr_err) would be appropriate here. > > $ insmod patch_1.ko > insmod: ERROR: could not insert module patch_1.ko: Function not implemented > > is not helpful much :) Ok :-)
On Fri 2017-01-06 14:07:34, Josh Poimboeuf wrote: > On Fri, Dec 23, 2016 at 11:18:03AM +0100, Petr Mladek wrote: > > On Fri 2016-12-23 10:24:35, Miroslav Benes wrote: > > > > > > diff --git a/kernel/livepatch/patch.c b/kernel/livepatch/patch.c > > > > > > index 5efa262..e79ebb5 100644 > > > > > > --- a/kernel/livepatch/patch.c > > > > > > +++ b/kernel/livepatch/patch.c > > > > > > @@ -29,6 +29,7 @@ > > > > > > #include <linux/bug.h> > > > > > > #include <linux/printk.h> > > > > > > #include "patch.h" > > > > > > +#include "transition.h" > > > > > > > > > > > > static LIST_HEAD(klp_ops); > > > > > > > > > > > > @@ -54,15 +55,53 @@ static void notrace klp_ftrace_handler(unsigned long ip, > > > > > > { > > > > > > struct klp_ops *ops; > > > > > > struct klp_func *func; > > > > > > + int patch_state; > > > > > > > > > > > > ops = container_of(fops, struct klp_ops, fops); > > > > > > > > > > > > rcu_read_lock(); > > > > > > + > > > > > > func = list_first_or_null_rcu(&ops->func_stack, struct klp_func, > > > > > > stack_node); > > > > > > - if (WARN_ON_ONCE(!func)) > > > > > > + > > > > > > + if (!func) > > > > > > goto unlock; > > > > > > Yeah, I'm thinking we should keep the warning to catch any bugs in case > any of our ftrace assumptions change. Maybe I should add a comment: > > /* > * func can never be NULL because preemption should be disabled > * here and unregister_ftrace_function() does the equivalent of > * a synchronize_sched() before the func_stack removal. > */ > if (WARN_ON_ONCE(!func)) > goto unlock; Sounds reasonable to me. Best Regards, Petr
> > > --- a/kernel/sched/idle.c > > > +++ b/kernel/sched/idle.c > > > @@ -9,6 +9,7 @@ > > > #include <linux/mm.h> > > > #include <linux/stackprotector.h> > > > #include <linux/suspend.h> > > > +#include <linux/livepatch.h> > > > > > > #include <asm/tlb.h> > > > > > > @@ -264,6 +265,9 @@ static void do_idle(void) > > > > > > sched_ttwu_pending(); > > > schedule_preempt_disabled(); > > > + > > > + if (unlikely(klp_patch_pending(current))) > > > + klp_update_patch_state(current); > > > } > > > > I think that (theoretically) this is not sufficient, if we patch a > > function present on an idle task's stack and one of the two following > > scenarios happen. > > Agreed, though I'd argue that these are rare edge cases which can > probably be refined later, outside the scope of this patch set. You're right. They should be really rare and we can solve them (if we even want to) later. > > 1. there is nothing to schedule on a cpu and an idle task does not leave a > > loop in do_idle() for some time. It may be a nonsense practically and if > > it is not we could solve with schedule_on_each_cpu() on an empty stub > > somewhere in our code. > > This might only be a theoretical issue, as it only happens when patching > one of the idle functions themselves. > > If we decided that this were a real world problem, we could use > something like schedule_on_each_cpu() to flush them out as you > suggested. Or it could even be done from user space by briefly running > a CPU-intensive program on the affected CPUs. Yes. > > 2. there is a cpu-bound process running on one of the cpus. No chance of > > going to do_idle() there at all and the idle task would block the > > patching. > > To clarify I think this would only be an issue when trying to patch idle > code or schedule()/__schedule(). Yes. > > We ran into it in kGraft and I tried to solve it with this new > > hunk in pick_next_task()... > > > > + /* > > + * Patching is in progress, schedule an idle task to migrate it > > + */ > > + if (kgr_in_progress_branch()) { > > + if (!test_bit(0, kgr_immutable) && > > + klp_kgraft_task_in_progress(rq->idle)) { > > + p = idle_sched_class.pick_next_task(rq, prev); > > + > > + return p; > > + } > > + } > > > > (kgr_in_progress_branch() is a static key basically. kgr_immutable flag > > solves something we don't have a problem with in upstream livepatch thanks > > to a combination of task->patch_state and klp_func->transition. > > klp_kgraft_task_in_progress() checks the livepatching TIF of a task.) > > > > It is not tested properly and it is a hack as hell so take it as that. > > Also note that the problem in kGraft is more serious as we don't have a > > stack checking there. So any livepatch could cause the issue easily. > > > > I can imagine even crazier solutions but nothing nice and pretty (which is > > probably impossible because the whole idea to deliberately schedule an > > idle task is not nice and pretty). > > Yeah, that looks hairy... > > Since this is such a specialized case (patching the scheduler in an idle > task while CPU-intensive tasks are running) this might also be more > reasonably accomplished from user space by briefly SIGSTOPing the CPU > hog. Yes, that is true. I can imagine there are users who don't want to stop the cpu hog at all. Even for a fraction of time. HPC comes to mind. But it is not worth it to solve it with something like the code above. Let's add it to the very end of our TODO lists :). Miroslav
On Thu 2016-12-22 12:31:37, Josh Poimboeuf wrote: > On Thu, Dec 22, 2016 at 03:34:52PM +0100, Petr Mladek wrote: > > On Wed 2016-12-21 15:25:05, Josh Poimboeuf wrote: > > > On Tue, Dec 20, 2016 at 06:32:46PM +0100, Petr Mladek wrote: > > > > On Thu 2016-12-08 12:08:38, Josh Poimboeuf wrote: > > > > > Change livepatch to use 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 or data semantics. This is the > > > > > biggest remaining piece needed to make livepatch more generally useful. > > > > > > > > > > [1] https://lkml.kernel.org/r/20141107140458.GA21774@suse.cz > > > > > > > > > > --- /dev/null > > > > > +++ b/kernel/livepatch/transition.c > > > > > + /* > > > > > + * Enforce the order of the task->patch_state initializations and the > > > > > + * func->transition updates to ensure that, in the enable path, > > > > > + * klp_ftrace_handler() doesn't see a func in transition with a > > > > > + * task->patch_state of KLP_UNDEFINED. > > > > > + */ > > > > > + smp_wmb(); > > > > > + > > > > > + /* > > > > > + * Set the func transition states so klp_ftrace_handler() will know to > > > > > + * switch to the transition logic. > > > > > + * > > > > > + * When patching, the funcs aren't yet in the func_stack and will be > > > > > + * made visible to the ftrace handler shortly by the calls to > > > > > + * klp_patch_object(). > > > > > + * > > > > > + * When unpatching, the funcs are already in the func_stack and so are > > > > > + * already visible to the ftrace handler. > > > > > + */ > > > > > + klp_for_each_object(patch, obj) > > > > > + klp_for_each_func(obj, func) > > > > > + func->transition = true; > > > > > +} > > > > > + > > > > > +/* > > > > > + * Start the transition to the specified target patch state so tasks can begin > > > > > + * switching to it. > > > > > + */ > > > > > +void klp_start_transition(void) > > > > > +{ > > > > > + struct task_struct *g, *task; > > > > > + unsigned int cpu; > > > > > + > > > > > + WARN_ON_ONCE(klp_target_state == KLP_UNDEFINED); > > > > > + > > > > > + pr_notice("'%s': %s...\n", klp_transition_patch->mod->name, > > > > > + klp_target_state == KLP_PATCHED ? "patching" : "unpatching"); > > > > > + > > > > > + /* > > > > > + * If the patch can be applied or reverted immediately, skip the > > > > > + * per-task transitions. > > > > > + */ > > > > > + if (klp_transition_patch->immediate) > > > > > + return; > > > > > + > > > > > + /* > > > > > + * Mark all normal tasks as needing a patch state update. As they pass > > > > > + * through the syscall barrier they'll switch over to the target state > > > > > + * (unless we switch them in klp_try_complete_transition() first). > > > > > + */ > > > > > + read_lock(&tasklist_lock); > > > > > + for_each_process_thread(g, task) > > > > > + set_tsk_thread_flag(task, TIF_PATCH_PENDING); > > > > > > > > This is called also from klp_reverse_transition(). We should set it > > > > only when the task need migration. Also we should clear it when > > > > the task is in the right state already. > > > > > > > > It is not only optimization. It actually solves a race between > > > > klp_complete_transition() and klp_update_patch_state(), see below. > > > > > > I agree about the race, but if I did: > > > > > > for_each_process_thread(g, task) { > > > if (task->patch_state != klp_target_state) > > > set_tsk_thread_flag(task, TIF_PATCH_PENDING); > > > else > > > clear_tsk_thread_flag(task, TIF_PATCH_PENDING); > > > } > > > > > > It would still leave a small window where TIF_PATCH_PENDING gets set for > > > an already patched task, if klp_update_patch_state() is running at the > > > same time. > > > > I see your point. Well, it seems that it is more complicated: > > > > The race would be possible only when this was called from > > klp_reverse_transition(). But we need to call there > > rcu_synchronize() to prevent races with klp_update_patch_state() > > also to prevent prelimitary patch completion. > > > > The result is: > > > > if (task->patch_state != klp_target_state) { > > # it means that the task was already migrated before > > # we reverted klp_target_state. It means that > > # the TIF flag was already cleared, the related > > # klp_update_patch_state() already finished (thanks > > # to rcu_synchronize() and new one will be called > > # only when we set the flag again > > # => it is safe to set it > > > > # we should also check and warn when the TIF flag > > # was not clear before we set it here > > > > > > else > > > > # the task was not migrated before we reverted > > # klp_target_state. klp_update_patch_state() > > # could run in parallel but it will do the same > > # what we do, clear TIF flag and keep the patch_state > > # as is > > # => it is safe to clear it > > > > > > I agree that this is complex like hell. But it also allows use to > > check that things work as we expect. > > Ouch. I agree that it seems safe but it's way too hard to reason about. > And then it gets worse if you try to think about what happens when > adding another reverse operation. > > > > > If we always set the flag here and always clear it later, we might > > hide a bug. > > > > If we want to make it slightly more straightforward, we might > > clear TIF flags in klp_reverse_transaction() before we revert > > klp_target_state. The later rcu_synchronize() should make sure > > that all migrations are finished and non-will run in parallel. > > Then we could set the TIF flag only where needed here. > > I think this last paragraph is important. It would simplify things > greatly and ensure we won't have klp_update_patch_state() changing > things in the background. OK, let's clear all TIF_PATCH_PENDIG flags and call rcu_synchronize() at the beginning of klp_reverse_transition(). It might be slightly suboptimal but it greatly simplifies the situation. I vote for it. We need to prevent our heads from cracking ;-) Note that I would still set TIF_PATCH_PENDING flag only for tasks that are not in the requested state. > > > > > + read_unlock(&tasklist_lock); > > > > > + > > > > > + /* > > > > > + * Ditto for the idle "swapper" tasks, though they never cross the > > > > > + * syscall barrier. Instead they switch over in cpu_idle_loop(). > > > > > + */ > > > > > + get_online_cpus(); > > > > > + for_each_online_cpu(cpu) > > > > > + set_tsk_thread_flag(idle_task(cpu), TIF_PATCH_PENDING); > > > > > + put_online_cpus(); > > > > > > > > Also this stage need to be somehow handled by CPU coming/going > > > > handlers. > > > > > > Here I think we could automatically switch any offline CPUs' idle tasks. > > > And something similar in klp_try_complete_transition(). > > > > We still need to make sure to do not race with the cpu_up()/cpu_down() > > calls. > > Hm, maybe we'd need to call cpu_hotplug_disable() before switching the > offline idle tasks? > > > I would use here the trick with for_each_possible_cpu() and let > > the migration for the stack check. > > There are a few issues with that: > > 1) The idle task of a missing CPU doesn't *have* a stack, so it doesn't > make much sense to try to check it. > > 2) We can't rely *only* on the stack check, because not all arches have > it. The other way to migrate idle tasks is from the idle loop switch > point. But if the task's CPU is down, its idle loop isn't running so > it can't migrate. > > (Note this is currently a theoretical point: we currently don't allow > such arches to use the consistency model anyway because there's no > way for them to migrate kthreads.) Good points. My only concern is that the transaction might take a long or even forever. I am not sure if it is wise to disable cpu_hotplug for the entire transaction. A compromise might be to disable cpu hotplug only when the task state is manipulated a more complex way. Hmm, cpu_hotplug_disable() looks like a rather costly function. We should not call it in klp_try_complete_transition(). But we could do: 1. When the patch is being enabled, disable cpu hotplug, go through each_possible_cpu and setup the transaction only for CPUs that are online. Then we could enable the hotplug again. 2. Check only each_online_cpu in klp_try_complete_transition(). If all tasks are migrated, disable cpu hotplug and re-check idle tasks on online CPUs. If any is not migrated, enable hotplug and return failure. Othewise, continue with completion of the transaction. [*] 3. In klp_complete_transition, update all tasks including the offline CPUs and enable cpu hotplug again. If the re-check in the 2nd step looks ugly, we could add some hotlug notifiers to make sure that enabled/disabled CPUs are in a reasonable state. We still should disable the hotplug in the 1st and 3rd step. BTW: There is a new API for the cpu hotplug callbacks. I was involved in one conversion. You might take inspiration in drivers/thermal/intel_powerclamp.c. See cpuhp_setup_state_nocalls() there. [...] > > > > > diff --git a/samples/livepatch/livepatch-sample.c b/samples/livepatch/livepatch-sample.c > > > > > index e34f871..bb61c65 100644 > > > > > --- a/samples/livepatch/livepatch-sample.c > > > > > +++ b/samples/livepatch/livepatch-sample.c > > > > > @@ -17,6 +17,8 @@ > > > > > * along with this program; if not, see <http://www.gnu.org/licenses/>. > > > > > */ > > > > > > > > > > +#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt > > > > > + > > > > > #include <linux/module.h> > > > > > #include <linux/kernel.h> > > > > > #include <linux/livepatch.h> > > > > > @@ -69,6 +71,11 @@ static int livepatch_init(void) > > > > > { > > > > > int ret; > > > > > > > > > > + if (!klp_have_reliable_stack() && !patch.immediate) { > > > > > + pr_notice("disabling consistency model!\n"); > > > > > + patch.immediate = true; > > > > > + } > > > > > > > > I am scared to have this in the sample module. It makes sense > > > > to use the consistency model even for immediate patches because > > > > it allows to remove them. But this must not be used for patches > > > > that really require the consistency model. We should add > > > > a big fat warning at least. > > > > > > I did this so that the sample module would still work for non-x86_64 > > > arches, for which there's currently no way to patch kthreads. > > > > > > Notice I did add a warning: > > > > > > pr_notice("disabling consistency model!\n"); > > > > > > Is the warning not fat enough? > > > > The warning does not explain who did it, why, if it is safe, and when > > this could be used. I suggest a comment like: > > > > /* > > * WARNING: Use this check only when you know what you do! > > * > > * This sample patch does not change the semantic of the data structures, > > * locks, or return adresses. It is safe to be applied immediately. > > * But we want to test and use the consistency model on supported > > * architectures. It allows to remove the patch module. > > * > > * See Documentation/livepatch/livepatch.txt for more details, please. > > */ > > > > Also the message might be more explicit. > > > > pr_notice("livepatch-sample: The consistency model is not supported on > > this architecture. Using the immediate model that is safe enough.\n"); > > Ok, will try to do something like that. > > > Alternatively, we might allow more values for patch.immediate, e.g. > > > > enum klp_consistency_model { > > KLP_CM_IMMEDIATE, > > KLP_CM_TASK, > > KLP_CM_TASK_OR_IMMEDIATE, > > }; > > > > Then we could do the decision on the kernel side. > > But I am not sure if this would be widely used and it > > it is worth the complication. > > I'd rather avoid that :-) Same here :-) Best Regards, Petr
On Tue, Jan 10, 2017 at 02:00:58PM +0100, Petr Mladek wrote: > On Thu 2016-12-22 12:31:37, Josh Poimboeuf wrote: > > On Thu, Dec 22, 2016 at 03:34:52PM +0100, Petr Mladek wrote: > > > On Wed 2016-12-21 15:25:05, Josh Poimboeuf wrote: > > > > On Tue, Dec 20, 2016 at 06:32:46PM +0100, Petr Mladek wrote: > > > > > On Thu 2016-12-08 12:08:38, Josh Poimboeuf wrote: > > > > > > Change livepatch to use 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 or data semantics. This is the > > > > > > biggest remaining piece needed to make livepatch more generally useful. > > > > > > > > > > > > [1] https://lkml.kernel.org/r/20141107140458.GA21774@suse.cz > > > > > > > > > > > > --- /dev/null > > > > > > +++ b/kernel/livepatch/transition.c > > > > > > + /* > > > > > > + * Enforce the order of the task->patch_state initializations and the > > > > > > + * func->transition updates to ensure that, in the enable path, > > > > > > + * klp_ftrace_handler() doesn't see a func in transition with a > > > > > > + * task->patch_state of KLP_UNDEFINED. > > > > > > + */ > > > > > > + smp_wmb(); > > > > > > + > > > > > > + /* > > > > > > + * Set the func transition states so klp_ftrace_handler() will know to > > > > > > + * switch to the transition logic. > > > > > > + * > > > > > > + * When patching, the funcs aren't yet in the func_stack and will be > > > > > > + * made visible to the ftrace handler shortly by the calls to > > > > > > + * klp_patch_object(). > > > > > > + * > > > > > > + * When unpatching, the funcs are already in the func_stack and so are > > > > > > + * already visible to the ftrace handler. > > > > > > + */ > > > > > > + klp_for_each_object(patch, obj) > > > > > > + klp_for_each_func(obj, func) > > > > > > + func->transition = true; > > > > > > +} > > > > > > + > > > > > > +/* > > > > > > + * Start the transition to the specified target patch state so tasks can begin > > > > > > + * switching to it. > > > > > > + */ > > > > > > +void klp_start_transition(void) > > > > > > +{ > > > > > > + struct task_struct *g, *task; > > > > > > + unsigned int cpu; > > > > > > + > > > > > > + WARN_ON_ONCE(klp_target_state == KLP_UNDEFINED); > > > > > > + > > > > > > + pr_notice("'%s': %s...\n", klp_transition_patch->mod->name, > > > > > > + klp_target_state == KLP_PATCHED ? "patching" : "unpatching"); > > > > > > + > > > > > > + /* > > > > > > + * If the patch can be applied or reverted immediately, skip the > > > > > > + * per-task transitions. > > > > > > + */ > > > > > > + if (klp_transition_patch->immediate) > > > > > > + return; > > > > > > + > > > > > > + /* > > > > > > + * Mark all normal tasks as needing a patch state update. As they pass > > > > > > + * through the syscall barrier they'll switch over to the target state > > > > > > + * (unless we switch them in klp_try_complete_transition() first). > > > > > > + */ > > > > > > + read_lock(&tasklist_lock); > > > > > > + for_each_process_thread(g, task) > > > > > > + set_tsk_thread_flag(task, TIF_PATCH_PENDING); > > > > > > > > > > This is called also from klp_reverse_transition(). We should set it > > > > > only when the task need migration. Also we should clear it when > > > > > the task is in the right state already. > > > > > > > > > > It is not only optimization. It actually solves a race between > > > > > klp_complete_transition() and klp_update_patch_state(), see below. > > > > > > > > I agree about the race, but if I did: > > > > > > > > for_each_process_thread(g, task) { > > > > if (task->patch_state != klp_target_state) > > > > set_tsk_thread_flag(task, TIF_PATCH_PENDING); > > > > else > > > > clear_tsk_thread_flag(task, TIF_PATCH_PENDING); > > > > } > > > > > > > > It would still leave a small window where TIF_PATCH_PENDING gets set for > > > > an already patched task, if klp_update_patch_state() is running at the > > > > same time. > > > > > > I see your point. Well, it seems that it is more complicated: > > > > > > The race would be possible only when this was called from > > > klp_reverse_transition(). But we need to call there > > > rcu_synchronize() to prevent races with klp_update_patch_state() > > > also to prevent prelimitary patch completion. > > > > > > The result is: > > > > > > if (task->patch_state != klp_target_state) { > > > # it means that the task was already migrated before > > > # we reverted klp_target_state. It means that > > > # the TIF flag was already cleared, the related > > > # klp_update_patch_state() already finished (thanks > > > # to rcu_synchronize() and new one will be called > > > # only when we set the flag again > > > # => it is safe to set it > > > > > > # we should also check and warn when the TIF flag > > > # was not clear before we set it here > > > > > > > > > else > > > > > > # the task was not migrated before we reverted > > > # klp_target_state. klp_update_patch_state() > > > # could run in parallel but it will do the same > > > # what we do, clear TIF flag and keep the patch_state > > > # as is > > > # => it is safe to clear it > > > > > > > > > I agree that this is complex like hell. But it also allows use to > > > check that things work as we expect. > > > > Ouch. I agree that it seems safe but it's way too hard to reason about. > > And then it gets worse if you try to think about what happens when > > adding another reverse operation. > > > > > > > > If we always set the flag here and always clear it later, we might > > > hide a bug. > > > > > > If we want to make it slightly more straightforward, we might > > > clear TIF flags in klp_reverse_transaction() before we revert > > > klp_target_state. The later rcu_synchronize() should make sure > > > that all migrations are finished and non-will run in parallel. > > > Then we could set the TIF flag only where needed here. > > > > I think this last paragraph is important. It would simplify things > > greatly and ensure we won't have klp_update_patch_state() changing > > things in the background. > > OK, let's clear all TIF_PATCH_PENDIG flags and call rcu_synchronize() > at the beginning of klp_reverse_transition(). It might be slightly > suboptimal but it greatly simplifies the situation. I vote for it. > We need to prevent our heads from cracking ;-) > > Note that I would still set TIF_PATCH_PENDING flag only for tasks > that are not in the requested state. Ok, sounds good. > > > > > > + read_unlock(&tasklist_lock); > > > > > > + > > > > > > + /* > > > > > > + * Ditto for the idle "swapper" tasks, though they never cross the > > > > > > + * syscall barrier. Instead they switch over in cpu_idle_loop(). > > > > > > + */ > > > > > > + get_online_cpus(); > > > > > > + for_each_online_cpu(cpu) > > > > > > + set_tsk_thread_flag(idle_task(cpu), TIF_PATCH_PENDING); > > > > > > + put_online_cpus(); > > > > > > > > > > Also this stage need to be somehow handled by CPU coming/going > > > > > handlers. > > > > > > > > Here I think we could automatically switch any offline CPUs' idle tasks. > > > > And something similar in klp_try_complete_transition(). > > > > > > We still need to make sure to do not race with the cpu_up()/cpu_down() > > > calls. > > > > Hm, maybe we'd need to call cpu_hotplug_disable() before switching the > > offline idle tasks? > > > > > I would use here the trick with for_each_possible_cpu() and let > > > the migration for the stack check. > > > > There are a few issues with that: > > > > 1) The idle task of a missing CPU doesn't *have* a stack, so it doesn't > > make much sense to try to check it. > > > > 2) We can't rely *only* on the stack check, because not all arches have > > it. The other way to migrate idle tasks is from the idle loop switch > > point. But if the task's CPU is down, its idle loop isn't running so > > it can't migrate. > > > > (Note this is currently a theoretical point: we currently don't allow > > such arches to use the consistency model anyway because there's no > > way for them to migrate kthreads.) > > Good points. My only concern is that the transaction might take a long > or even forever. I am not sure if it is wise to disable cpu_hotplug > for the entire transaction. > > A compromise might be to disable cpu hotplug only when the task > state is manipulated a more complex way. Hmm, cpu_hotplug_disable() > looks like a rather costly function. We should not call it in > klp_try_complete_transition(). But we could do: > > 1. When the patch is being enabled, disable cpu hotplug, > go through each_possible_cpu and setup the transaction > only for CPUs that are online. Then we could enable > the hotplug again. > > 2. Check only each_online_cpu in klp_try_complete_transition(). > If all tasks are migrated, disable cpu hotplug and re-check > idle tasks on online CPUs. If any is not migrated, enable > hotplug and return failure. Othewise, continue with > completion of the transaction. [*] > > 3. In klp_complete_transition, update all tasks including > the offline CPUs and enable cpu hotplug again. > > If the re-check in the 2nd step looks ugly, we could add some hotlug > notifiers to make sure that enabled/disabled CPUs are in a reasonable > state. We still should disable the hotplug in the 1st and 3rd step. > > BTW: There is a new API for the cpu hotplug callbacks. I was involved > in one conversion. You might take inspiration in > drivers/thermal/intel_powerclamp.c. See cpuhp_setup_state_nocalls() > there. Backing up a bit, although I brought up cpu_hotplug_disable(), I think I misunderstood the race you mentioned. I actually don't think cpu_hotplug_disable() is necessary. What do you think about something like the following: In klp_start_transition: get_online_cpus(); for_each_possible_cpu(cpu) set_tsk_thread_flag(idle_task(cpu), TIF_PATCH_PENDING); put_online_cpus(); In klp_try_complete_transition: get_online_cpus(); for_each_possible_cpu(cpu) { task = idle_task(cpu); if (cpu_online(cpu)) { if (!klp_try_switch_task(task)) complete = false; } else if (task->patch_state != klp_target_state) { /* offline CPU idle tasks can be switched immediately */ clear_tsk_thread_flag(task, TIF_PATCH_PENDING); task->patch_state = klp_target_state; } } put_online_cpus();
On Tue 2017-01-10 14:46:46, Josh Poimboeuf wrote: > On Tue, Jan 10, 2017 at 02:00:58PM +0100, Petr Mladek wrote: > > On Thu 2016-12-22 12:31:37, Josh Poimboeuf wrote: > > > On Thu, Dec 22, 2016 at 03:34:52PM +0100, Petr Mladek wrote: > > > > On Wed 2016-12-21 15:25:05, Josh Poimboeuf wrote: > > > > > On Tue, Dec 20, 2016 at 06:32:46PM +0100, Petr Mladek wrote: > > > > > > On Thu 2016-12-08 12:08:38, Josh Poimboeuf wrote: > > > > > > > + read_unlock(&tasklist_lock); > > > > > > > + > > > > > > > + /* > > > > > > > + * Ditto for the idle "swapper" tasks, though they never cross the > > > > > > > + * syscall barrier. Instead they switch over in cpu_idle_loop(). > > > > > > > + */ > > > > > > > + get_online_cpus(); > > > > > > > + for_each_online_cpu(cpu) > > > > > > > + set_tsk_thread_flag(idle_task(cpu), TIF_PATCH_PENDING); > > > > > > > + put_online_cpus(); > > > > > > > > > > > > Also this stage need to be somehow handled by CPU coming/going > > > > > > handlers. > > > > > > > > > > Here I think we could automatically switch any offline CPUs' idle tasks. > > > > > And something similar in klp_try_complete_transition(). > > > > > > > > We still need to make sure to do not race with the cpu_up()/cpu_down() > > > > calls. > > > > > > Hm, maybe we'd need to call cpu_hotplug_disable() before switching the > > > offline idle tasks? > > > > > > > I would use here the trick with for_each_possible_cpu() and let > > > > the migration for the stack check. > > > > > > There are a few issues with that: > > > > > > 1) The idle task of a missing CPU doesn't *have* a stack, so it doesn't > > > make much sense to try to check it. > > > > > > 2) We can't rely *only* on the stack check, because not all arches have > > > it. The other way to migrate idle tasks is from the idle loop switch > > > point. But if the task's CPU is down, its idle loop isn't running so > > > it can't migrate. > > > > > > (Note this is currently a theoretical point: we currently don't allow > > > such arches to use the consistency model anyway because there's no > > > way for them to migrate kthreads.) > > > > Good points. My only concern is that the transaction might take a long > > or even forever. I am not sure if it is wise to disable cpu_hotplug > > for the entire transaction. > > > > A compromise might be to disable cpu hotplug only when the task > > state is manipulated a more complex way. Hmm, cpu_hotplug_disable() > > looks like a rather costly function. We should not call it in > > klp_try_complete_transition(). But we could do: > > > > 1. When the patch is being enabled, disable cpu hotplug, > > go through each_possible_cpu and setup the transaction > > only for CPUs that are online. Then we could enable > > the hotplug again. > > > > 2. Check only each_online_cpu in klp_try_complete_transition(). > > If all tasks are migrated, disable cpu hotplug and re-check > > idle tasks on online CPUs. If any is not migrated, enable > > hotplug and return failure. Othewise, continue with > > completion of the transaction. [*] > > > > 3. In klp_complete_transition, update all tasks including > > the offline CPUs and enable cpu hotplug again. > > > > If the re-check in the 2nd step looks ugly, we could add some hotlug > > notifiers to make sure that enabled/disabled CPUs are in a reasonable > > state. We still should disable the hotplug in the 1st and 3rd step. > > > > BTW: There is a new API for the cpu hotplug callbacks. I was involved > > in one conversion. You might take inspiration in > > drivers/thermal/intel_powerclamp.c. See cpuhp_setup_state_nocalls() > > there. > > Backing up a bit, although I brought up cpu_hotplug_disable(), I think I > misunderstood the race you mentioned. I actually don't think > cpu_hotplug_disable() is necessary. Great backing! You made me to study the difference. If I get it correctly: + cpu_hotplug_disable() works like a writer lock. It gets exclusive access via cpu_hotplug_begin(). A side effect is that do_cpu_up() and do_cpu_down() do not wait. They return -EBUSY if hotplug is disabled. + get_online_cpus() is kind of reader lock. It makes sure that all the hotplug operations are finished and "softly" blocks other further operation. By "softly" I mean that the operations wait for the exclusive (write) access in cpu_hotplug_begin(). IMHO, we really have to use get_online_cpus() and avoid the the "hard" blocking. > What do you think about something like the following: > In klp_start_transition: > > get_online_cpus(); > for_each_possible_cpu(cpu) > set_tsk_thread_flag(idle_task(cpu), TIF_PATCH_PENDING); > put_online_cpus(); > > In klp_try_complete_transition: > > get_online_cpus(); > for_each_possible_cpu(cpu) { > task = idle_task(cpu); > if (cpu_online(cpu)) { > if (!klp_try_switch_task(task)) > complete = false; > } else if (task->patch_state != klp_target_state) { > /* offline CPU idle tasks can be switched immediately */ > clear_tsk_thread_flag(task, TIF_PATCH_PENDING); > task->patch_state = klp_target_state; > } > } > put_online_cpus(); I like the idea. You are right that it is enough to always get/put CPUs only when a state of the per-CPU idle tasks are manipulated. In the meantime, we are safe because of the consistency model (clever ftrace handler). Note that we have to use for_each_possible_cpu() everywhere, e.g. in klp_init_transition(), klp_complete_transition(). Otherwise, we might see an inconsistent state. For example, klp_ftrace_handler() might see KLP_UNDEFINED state if we do not set a valid one in klp_init_transition() and a CPU gets online. Best Regards, Petr
On Wed, Jan 11, 2017 at 04:18:28PM +0100, Petr Mladek wrote: > On Tue 2017-01-10 14:46:46, Josh Poimboeuf wrote: > > On Tue, Jan 10, 2017 at 02:00:58PM +0100, Petr Mladek wrote: > > > On Thu 2016-12-22 12:31:37, Josh Poimboeuf wrote: > > > > On Thu, Dec 22, 2016 at 03:34:52PM +0100, Petr Mladek wrote: > > > > > On Wed 2016-12-21 15:25:05, Josh Poimboeuf wrote: > > > > > > On Tue, Dec 20, 2016 at 06:32:46PM +0100, Petr Mladek wrote: > > > > > > > On Thu 2016-12-08 12:08:38, Josh Poimboeuf wrote: > > > > > > > > + read_unlock(&tasklist_lock); > > > > > > > > + > > > > > > > > + /* > > > > > > > > + * Ditto for the idle "swapper" tasks, though they never cross the > > > > > > > > + * syscall barrier. Instead they switch over in cpu_idle_loop(). > > > > > > > > + */ > > > > > > > > + get_online_cpus(); > > > > > > > > + for_each_online_cpu(cpu) > > > > > > > > + set_tsk_thread_flag(idle_task(cpu), TIF_PATCH_PENDING); > > > > > > > > + put_online_cpus(); > > > > > > > > > > > > > > Also this stage need to be somehow handled by CPU coming/going > > > > > > > handlers. > > > > > > > > > > > > Here I think we could automatically switch any offline CPUs' idle tasks. > > > > > > And something similar in klp_try_complete_transition(). > > > > > > > > > > We still need to make sure to do not race with the cpu_up()/cpu_down() > > > > > calls. > > > > > > > > Hm, maybe we'd need to call cpu_hotplug_disable() before switching the > > > > offline idle tasks? > > > > > > > > > I would use here the trick with for_each_possible_cpu() and let > > > > > the migration for the stack check. > > > > > > > > There are a few issues with that: > > > > > > > > 1) The idle task of a missing CPU doesn't *have* a stack, so it doesn't > > > > make much sense to try to check it. > > > > > > > > 2) We can't rely *only* on the stack check, because not all arches have > > > > it. The other way to migrate idle tasks is from the idle loop switch > > > > point. But if the task's CPU is down, its idle loop isn't running so > > > > it can't migrate. > > > > > > > > (Note this is currently a theoretical point: we currently don't allow > > > > such arches to use the consistency model anyway because there's no > > > > way for them to migrate kthreads.) > > > > > > Good points. My only concern is that the transaction might take a long > > > or even forever. I am not sure if it is wise to disable cpu_hotplug > > > for the entire transaction. > > > > > > A compromise might be to disable cpu hotplug only when the task > > > state is manipulated a more complex way. Hmm, cpu_hotplug_disable() > > > looks like a rather costly function. We should not call it in > > > klp_try_complete_transition(). But we could do: > > > > > > 1. When the patch is being enabled, disable cpu hotplug, > > > go through each_possible_cpu and setup the transaction > > > only for CPUs that are online. Then we could enable > > > the hotplug again. > > > > > > 2. Check only each_online_cpu in klp_try_complete_transition(). > > > If all tasks are migrated, disable cpu hotplug and re-check > > > idle tasks on online CPUs. If any is not migrated, enable > > > hotplug and return failure. Othewise, continue with > > > completion of the transaction. [*] > > > > > > 3. In klp_complete_transition, update all tasks including > > > the offline CPUs and enable cpu hotplug again. > > > > > > If the re-check in the 2nd step looks ugly, we could add some hotlug > > > notifiers to make sure that enabled/disabled CPUs are in a reasonable > > > state. We still should disable the hotplug in the 1st and 3rd step. > > > > > > BTW: There is a new API for the cpu hotplug callbacks. I was involved > > > in one conversion. You might take inspiration in > > > drivers/thermal/intel_powerclamp.c. See cpuhp_setup_state_nocalls() > > > there. > > > > Backing up a bit, although I brought up cpu_hotplug_disable(), I think I > > misunderstood the race you mentioned. I actually don't think > > cpu_hotplug_disable() is necessary. > > Great backing! You made me to study the difference. If I get it > correctly: > > + cpu_hotplug_disable() works like a writer lock. It gets > exclusive access via cpu_hotplug_begin(). A side effect > is that do_cpu_up() and do_cpu_down() do not wait. They > return -EBUSY if hotplug is disabled. > > + get_online_cpus() is kind of reader lock. It makes sure > that all the hotplug operations are finished and "softly" > blocks other further operation. By "softly" I mean that > the operations wait for the exclusive (write) access > in cpu_hotplug_begin(). > > IMHO, we really have to use get_online_cpus() and avoid the > the "hard" blocking. > > > > What do you think about something like the following: > > > In klp_start_transition: > > > > get_online_cpus(); > > for_each_possible_cpu(cpu) > > set_tsk_thread_flag(idle_task(cpu), TIF_PATCH_PENDING); > > put_online_cpus(); > > > > In klp_try_complete_transition: > > > > get_online_cpus(); > > for_each_possible_cpu(cpu) { > > task = idle_task(cpu); > > if (cpu_online(cpu)) { > > if (!klp_try_switch_task(task)) > > complete = false; > > } else if (task->patch_state != klp_target_state) { > > /* offline CPU idle tasks can be switched immediately */ > > clear_tsk_thread_flag(task, TIF_PATCH_PENDING); > > task->patch_state = klp_target_state; > > } > > } > > put_online_cpus(); > > I like the idea. You are right that it is enough to always get/put > CPUs only when a state of the per-CPU idle tasks are manipulated. > In the meantime, we are safe because of the consistency model > (clever ftrace handler). > > Note that we have to use for_each_possible_cpu() everywhere, > e.g. in klp_init_transition(), klp_complete_transition(). > Otherwise, we might see an inconsistent state. > > For example, klp_ftrace_handler() might see KLP_UNDEFINED state > if we do not set a valid one in klp_init_transition() and a CPU > gets online. Agreed! I will try to have v4 soon-ish.
diff --git a/Documentation/ABI/testing/sysfs-kernel-livepatch b/Documentation/ABI/testing/sysfs-kernel-livepatch index da87f43..24b6570 100644 --- a/Documentation/ABI/testing/sysfs-kernel-livepatch +++ b/Documentation/ABI/testing/sysfs-kernel-livepatch @@ -25,6 +25,14 @@ Description: code is currently applied. Writing 0 will disable the patch while writing 1 will re-enable the patch. +What: /sys/kernel/livepatch/<patch>/transition +Date: May 2016 +KernelVersion: 4.11.0 +Contact: live-patching@vger.kernel.org +Description: + An attribute which indicates whether the patch is currently in + transition. + What: /sys/kernel/livepatch/<patch>/<object> Date: Nov 2014 KernelVersion: 3.19.0 diff --git a/Documentation/livepatch/livepatch.txt b/Documentation/livepatch/livepatch.txt index 6c43f6e..f87e742 100644 --- a/Documentation/livepatch/livepatch.txt +++ b/Documentation/livepatch/livepatch.txt @@ -72,7 +72,8 @@ example, they add a NULL pointer or a boundary check, fix a race by adding a missing memory barrier, or add some locking around a critical section. Most of these changes are self contained and the function presents itself the same way to the rest of the system. In this case, the functions might -be updated independently one by one. +be updated independently one by one. (This can be done by setting the +'immediate' flag in the klp_patch struct.) But there are more complex fixes. For example, a patch might change ordering of locking in multiple functions at the same time. Or a patch @@ -86,20 +87,96 @@ or no data are stored in the modified structures at the moment. The theory about how to apply functions a safe way is rather complex. The aim is to define a so-called consistency model. It attempts to define conditions when the new implementation could be used so that the system -stays consistent. The theory is not yet finished. See the discussion at -http://thread.gmane.org/gmane.linux.kernel/1823033/focus=1828189 - -The current consistency model is very simple. It guarantees that either -the old or the new function is called. But various functions get redirected -one by one without any synchronization. - -In other words, the current implementation _never_ modifies the behavior -in the middle of the call. It is because it does _not_ rewrite the entire -function in the memory. Instead, the function gets redirected at the -very beginning. But this redirection is used immediately even when -some other functions from the same patch have not been redirected yet. - -See also the section "Limitations" below. +stays consistent. + +Livepatch has a consistency model which is a hybrid of kGraft and +kpatch: it uses kGraft's per-task consistency and syscall barrier +switching combined with kpatch's stack trace switching. There are also +a number of fallback options which make it quite flexible. + +Patches are applied on a per-task basis, when the task is deemed safe to +switch over. When a patch is enabled, livepatch enters into a +transition state where tasks are converging to the patched state. +Usually this transition state can complete in a few seconds. The same +sequence occurs when a patch is disabled, except the tasks converge from +the patched state to the unpatched state. + +An interrupt handler inherits the patched state of the task it +interrupts. The same is true for forked tasks: the child inherits the +patched state of the parent. + +Livepatch uses several complementary approaches to determine when it's +safe to patch tasks: + +1. The first and most effective approach is stack checking of sleeping + tasks. If no affected functions are on the stack of a given task, + the task is patched. In most cases this will patch most or all of + the tasks on the first try. Otherwise it'll keep trying + periodically. This option is only available if the architecture has + reliable stacks (HAVE_RELIABLE_STACKTRACE). + +2. The second approach, if needed, is kernel exit switching. A + task is switched when it returns to user space from a system call, a + user space IRQ, or a signal. It's useful in the following cases: + + a) Patching I/O-bound user tasks which are sleeping on an affected + function. In this case you have to send SIGSTOP and SIGCONT to + force it to exit the kernel and be patched. + b) Patching CPU-bound user tasks. If the task is highly CPU-bound + then it will get patched the next time it gets interrupted by an + IRQ. + c) In the future it could be useful for applying patches for + architectures which don't yet have HAVE_RELIABLE_STACKTRACE. In + this case you would have to signal most of the tasks on the + system. However this isn't supported yet because there's + currently no way to patch kthreads without + HAVE_RELIABLE_STACKTRACE. + +3. For idle "swapper" tasks, since they don't ever exit the kernel, they + instead have a klp_update_patch_state() call in the idle loop which + allows them to be patched before the CPU enters the idle state. + + (Note there's not yet such an approach for kthreads.) + +All the above approaches may be skipped by setting the 'immediate' flag +in the 'klp_patch' struct, which will disable per-task consistency and +patch all tasks immediately. This can be useful if the patch doesn't +change any function or data semantics. Note that, even with this flag +set, it's possible that some tasks may still be running with an old +version of the function, until that function returns. + +There's also an 'immediate' flag in the 'klp_func' struct which allows +you to specify that certain functions in the patch can be applied +without per-task consistency. This might be useful if you want to patch +a common function like schedule(), and the function change doesn't need +consistency but the rest of the patch does. + +For architectures which don't have HAVE_RELIABLE_STACKTRACE, the user +must set patch->immediate which causes all tasks to be patched +immediately. This option should be used with care, only when the patch +doesn't change any function or data semantics. + +In the future, architectures which don't have HAVE_RELIABLE_STACKTRACE +may be allowed to use per-task consistency if we can come up with +another way to patch kthreads. + +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 transition +indefinitely, if any of the tasks are stuck in the initial patch state. + +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 patch state. + +There's also a /proc/<pid>/patch_state file which can be used to +determine which tasks are blocking completion of a patching operation. +If a patch is in transition, this file shows 0 to indicate the task is +unpatched and 1 to indicate it's patched. Otherwise, if no patch is in +transition, it shows -1. Any tasks which are blocking the transition +can be signaled with SIGSTOP and SIGCONT to force them to change their +patched state. 4. Livepatch module @@ -134,7 +211,7 @@ Documentation/livepatch/module-elf-format.txt for more details. 4.2. Metadata ------------- +------------- The patch is described by several structures that split the information into three levels: @@ -239,9 +316,15 @@ Registered patches might be enabled either by calling klp_enable_patch() or by writing '1' to /sys/kernel/livepatch/<name>/enabled. The system will start using the new implementation of the patched functions at this stage. -In particular, if an original function is patched for the first time, a -function specific struct klp_ops is created and an universal ftrace handler -is registered. +When a patch is enabled, livepatch enters into a transition state where +tasks are converging to the patched state. This is indicated by a value +of '1' in /sys/kernel/livepatch/<name>/transition. Once all tasks have +been patched, the 'transition' value changes to '0'. For more +information about this process, see the "Consistency model" section. + +If an original function is patched for the first time, a function +specific struct klp_ops is created and an universal ftrace handler is +registered. Functions might be patched multiple times. The ftrace handler is registered only once for the given function. Further patches just add an entry to the @@ -261,6 +344,12 @@ by writing '0' to /sys/kernel/livepatch/<name>/enabled. At this stage either the code from the previously enabled patch or even the original code gets used. +When a patch is disabled, livepatch enters into a transition state where +tasks are converging to the unpatched state. This is indicated by a +value of '1' in /sys/kernel/livepatch/<name>/transition. Once all tasks +have been unpatched, the 'transition' value changes to '0'. For more +information about this process, see the "Consistency model" section. + Here all the functions (struct klp_func) associated with the to-be-disabled patch are removed from the corresponding struct klp_ops. The ftrace handler is unregistered and the struct klp_ops is freed when the func_stack list diff --git a/include/linux/init_task.h b/include/linux/init_task.h index 325f649..25f0360 100644 --- a/include/linux/init_task.h +++ b/include/linux/init_task.h @@ -14,6 +14,7 @@ #include <linux/rbtree.h> #include <net/net_namespace.h> #include <linux/sched/rt.h> +#include <linux/livepatch.h> #include <asm/thread_info.h> @@ -185,6 +186,13 @@ extern struct task_group root_task_group; # define INIT_KASAN(tsk) #endif +#ifdef CONFIG_LIVEPATCH +# define INIT_LIVEPATCH(tsk) \ + .patch_state = KLP_UNDEFINED, +#else +# define INIT_LIVEPATCH(tsk) +#endif + #ifdef CONFIG_THREAD_INFO_IN_TASK # define INIT_TASK_TI(tsk) \ .thread_info = INIT_THREAD_INFO(tsk), \ @@ -271,6 +279,7 @@ extern struct task_group root_task_group; INIT_VTIME(tsk) \ INIT_NUMA_BALANCING(tsk) \ INIT_KASAN(tsk) \ + INIT_LIVEPATCH(tsk) \ } diff --git a/include/linux/livepatch.h b/include/linux/livepatch.h index 1a5a93c..8e06fe5 100644 --- a/include/linux/livepatch.h +++ b/include/linux/livepatch.h @@ -28,18 +28,40 @@ #include <asm/livepatch.h> +/* task patch states */ +#define KLP_UNDEFINED -1 +#define KLP_UNPATCHED 0 +#define KLP_PATCHED 1 + /** * struct klp_func - function structure for live patching * @old_name: name of the function to be patched * @new_func: pointer to the patched function code * @old_sympos: a hint indicating which symbol position the old function * can be found (optional) + * @immediate: patch the func immediately, bypassing backtrace safety checks * @old_addr: the address of the function being patched * @kobj: kobject for sysfs resources * @stack_node: list node for klp_ops func_stack list * @old_size: size of the old function * @new_size: size of the new function * @patched: the func has been added to the klp_ops list + * @transition: the func is currently being applied or reverted + * + * The patched and transition variables define the func's patching state. When + * patching, a func is 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 when 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 */ struct klp_func { /* external */ @@ -53,6 +75,7 @@ struct klp_func { * in kallsyms for the given object is used. */ unsigned long old_sympos; + bool immediate; /* internal */ unsigned long old_addr; @@ -60,6 +83,7 @@ struct klp_func { struct list_head stack_node; unsigned long old_size, new_size; bool patched; + bool transition; }; /** @@ -86,6 +110,7 @@ struct klp_object { * struct klp_patch - patch structure for live patching * @mod: reference to the live patch module * @objs: object entries for kernel objects to be patched + * @immediate: patch all funcs immediately, bypassing safety mechanisms * @list: list node for global list of registered patches * @kobj: kobject for sysfs resources * @enabled: the patch is enabled (but operation may be incomplete) @@ -94,6 +119,7 @@ struct klp_patch { /* external */ struct module *mod; struct klp_object *objs; + bool immediate; /* internal */ struct list_head list; @@ -121,15 +147,27 @@ void arch_klp_init_object_loaded(struct klp_patch *patch, int klp_module_coming(struct module *mod); void klp_module_going(struct module *mod); -static inline bool klp_patch_pending(struct task_struct *task) { return false; } +void klp_copy_process(struct task_struct *child); void klp_update_patch_state(struct task_struct *task); +static inline bool klp_patch_pending(struct task_struct *task) +{ + return test_tsk_thread_flag(task, TIF_PATCH_PENDING); +} + +static inline bool klp_have_reliable_stack(void) +{ + return IS_ENABLED(CONFIG_STACKTRACE) && + IS_ENABLED(CONFIG_HAVE_RELIABLE_STACKTRACE); +} + #else /* !CONFIG_LIVEPATCH */ static inline int klp_module_coming(struct module *mod) { return 0; } static inline void klp_module_going(struct module *mod) {} static inline bool klp_patch_pending(struct task_struct *task) { return false; } static inline void klp_update_patch_state(struct task_struct *task) {} +static inline void klp_copy_process(struct task_struct *child) {} #endif /* CONFIG_LIVEPATCH */ diff --git a/include/linux/sched.h b/include/linux/sched.h index 1531c48..1b2b234 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -1988,6 +1988,9 @@ struct task_struct { /* A live task holds one reference. */ atomic_t stack_refcount; #endif +#ifdef CONFIG_LIVEPATCH + int patch_state; +#endif /* CPU-specific state of this task */ struct thread_struct thread; /* diff --git a/kernel/fork.c b/kernel/fork.c index 8f63bf9..3fadbbd 100644 --- a/kernel/fork.c +++ b/kernel/fork.c @@ -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> @@ -1759,6 +1760,8 @@ static __latent_entropy struct task_struct *copy_process( p->parent_exec_id = current->self_exec_id; } + klp_copy_process(p); + spin_lock(¤t->sighand->siglock); /* diff --git a/kernel/livepatch/Makefile b/kernel/livepatch/Makefile index e136dad..2b8bdb1 100644 --- a/kernel/livepatch/Makefile +++ b/kernel/livepatch/Makefile @@ -1,3 +1,3 @@ obj-$(CONFIG_LIVEPATCH) += livepatch.o -livepatch-objs := core.o patch.o +livepatch-objs := core.o patch.o transition.o diff --git a/kernel/livepatch/core.c b/kernel/livepatch/core.c index fc160c6..22c0c01 100644 --- a/kernel/livepatch/core.c +++ b/kernel/livepatch/core.c @@ -31,12 +31,15 @@ #include <linux/moduleloader.h> #include <asm/cacheflush.h> #include "patch.h" +#include "transition.h" /* - * The klp_mutex protects the global lists and state transitions of any - * structure reachable from them. References to any structure must be obtained - * under mutex protection (except in klp_ftrace_handler(), which uses RCU to - * ensure it gets consistent data). + * klp_mutex is a coarse lock which serializes access to klp data. All + * accesses to klp-related variables and structures must have mutex protection, + * except within the following functions which carefully avoid the need for it: + * + * - klp_ftrace_handler() + * - klp_update_patch_state() */ static DEFINE_MUTEX(klp_mutex); @@ -44,8 +47,26 @@ static LIST_HEAD(klp_patches); static struct kobject *klp_root_kobj; -/* TODO: temporary stub */ -void klp_update_patch_state(struct task_struct *task) {} +static void klp_transition_work_fn(struct work_struct *work); +static DECLARE_DELAYED_WORK(klp_transition_work, klp_transition_work_fn); + +#define KLP_TRANSITION_DELAY round_jiffies_relative(HZ) + +/* + * This work can be performed periodically to finish patching or unpatching any + * "straggler" tasks which failed to transition in klp_enable_patch(). + */ +static void klp_transition_work_fn(struct work_struct *work) +{ + mutex_lock(&klp_mutex); + + if (klp_transition_patch) + if (!klp_try_complete_transition()) + schedule_delayed_work(&klp_transition_work, + KLP_TRANSITION_DELAY); + + mutex_unlock(&klp_mutex); +} static bool klp_is_module(struct klp_object *obj) { @@ -85,7 +106,6 @@ static void klp_find_object_module(struct klp_object *obj) mutex_unlock(&module_mutex); } -/* klp_mutex must be held by caller */ static bool klp_is_patch_registered(struct klp_patch *patch) { struct klp_patch *mypatch; @@ -281,19 +301,28 @@ static int klp_write_object_relocations(struct module *pmod, static int __klp_disable_patch(struct klp_patch *patch) { - struct klp_object *obj; + if (klp_transition_patch) + return -EBUSY; /* enforce stacking: only the last enabled patch can be disabled */ if (!list_is_last(&patch->list, &klp_patches) && list_next_entry(patch, list)->enabled) return -EBUSY; - pr_notice("disabling patch '%s'\n", patch->mod->name); + klp_init_transition(patch, KLP_UNPATCHED); - klp_for_each_object(patch, obj) { - if (obj->patched) - klp_unpatch_object(obj); - } + /* + * Enforce the order of the klp_target_state write in + * klp_init_transition() and the TIF_PATCH_PENDING writes in + * klp_start_transition() to ensure that klp_update_patch_state() + * doesn't set a task->patch_state to KLP_UNDEFINED. + */ + smp_wmb(); + + klp_start_transition(); + if (!klp_try_complete_transition()) + schedule_delayed_work(&klp_transition_work, + KLP_TRANSITION_DELAY); patch->enabled = false; @@ -337,6 +366,9 @@ static int __klp_enable_patch(struct klp_patch *patch) struct klp_object *obj; int ret; + if (klp_transition_patch) + return -EBUSY; + if (WARN_ON(patch->enabled)) return -EINVAL; @@ -347,22 +379,42 @@ static int __klp_enable_patch(struct klp_patch *patch) pr_notice("enabling patch '%s'\n", patch->mod->name); + klp_init_transition(patch, KLP_PATCHED); + + /* + * Enforce the order of the func->transition writes in + * klp_init_transition() and the ops->func_stack writes in + * klp_patch_object(), so that klp_ftrace_handler() will see the + * func->transition updates before the handler is registered and the + * new funcs become visible to the handler. + */ + smp_wmb(); + klp_for_each_object(patch, obj) { if (!klp_is_object_loaded(obj)) continue; ret = klp_patch_object(obj); - if (ret) - goto unregister; + if (ret) { + pr_warn("failed to enable patch '%s'\n", + patch->mod->name); + + klp_unpatch_objects(patch); + klp_complete_transition(); + + return ret; + } } + klp_start_transition(); + + if (!klp_try_complete_transition()) + schedule_delayed_work(&klp_transition_work, + KLP_TRANSITION_DELAY); + patch->enabled = true; return 0; - -unregister: - WARN_ON(__klp_disable_patch(patch)); - return ret; } /** @@ -399,6 +451,7 @@ EXPORT_SYMBOL_GPL(klp_enable_patch); * /sys/kernel/livepatch * /sys/kernel/livepatch/<patch> * /sys/kernel/livepatch/<patch>/enabled + * /sys/kernel/livepatch/<patch>/transition * /sys/kernel/livepatch/<patch>/<object> * /sys/kernel/livepatch/<patch>/<object>/<function,sympos> */ @@ -424,7 +477,10 @@ static ssize_t enabled_store(struct kobject *kobj, struct kobj_attribute *attr, goto err; } - if (enabled) { + if (patch == klp_transition_patch) { + klp_reverse_transition(); + mod_delayed_work(system_wq, &klp_transition_work, 0); + } else if (enabled) { ret = __klp_enable_patch(patch); if (ret) goto err; @@ -452,9 +508,21 @@ static ssize_t enabled_show(struct kobject *kobj, return snprintf(buf, PAGE_SIZE-1, "%d\n", patch->enabled); } +static ssize_t transition_show(struct kobject *kobj, + struct kobj_attribute *attr, char *buf) +{ + struct klp_patch *patch; + + patch = container_of(kobj, struct klp_patch, kobj); + return snprintf(buf, PAGE_SIZE-1, "%d\n", + patch == klp_transition_patch); +} + static struct kobj_attribute enabled_kobj_attr = __ATTR_RW(enabled); +static struct kobj_attribute transition_kobj_attr = __ATTR_RO(transition); static struct attribute *klp_patch_attrs[] = { &enabled_kobj_attr.attr, + &transition_kobj_attr.attr, NULL }; @@ -544,6 +612,7 @@ static int klp_init_func(struct klp_object *obj, struct klp_func *func) INIT_LIST_HEAD(&func->stack_node); func->patched = false; + func->transition = false; /* The format for the sysfs directory is <function,sympos> where sympos * is the nth occurrence of this symbol in kallsyms for the patched @@ -740,6 +809,14 @@ int klp_register_patch(struct klp_patch *patch) return -ENODEV; /* + * Architectures without reliable stack traces have to set + * patch->immediate because there's currently no way to patch kthreads + * with the consistency model. + */ + if (!klp_have_reliable_stack() && !patch->immediate) + return -ENOSYS; + + /* * A reference is taken on the patch module to prevent it from being * unloaded. Right now, we don't allow patch modules to unload since * there is currently no method to determine if a thread is still @@ -788,7 +865,11 @@ int klp_module_coming(struct module *mod) goto err; } - if (!patch->enabled) + /* + * Only patch the module if the patch is enabled or is + * in transition. + */ + if (!patch->enabled && patch != klp_transition_patch) break; pr_notice("applying patch '%s' to loading module '%s'\n", diff --git a/kernel/livepatch/patch.c b/kernel/livepatch/patch.c index 5efa262..e79ebb5 100644 --- a/kernel/livepatch/patch.c +++ b/kernel/livepatch/patch.c @@ -29,6 +29,7 @@ #include <linux/bug.h> #include <linux/printk.h> #include "patch.h" +#include "transition.h" static LIST_HEAD(klp_ops); @@ -54,15 +55,53 @@ static void notrace klp_ftrace_handler(unsigned long ip, { struct klp_ops *ops; struct klp_func *func; + int patch_state; ops = container_of(fops, struct klp_ops, fops); rcu_read_lock(); + func = list_first_or_null_rcu(&ops->func_stack, struct klp_func, stack_node); - if (WARN_ON_ONCE(!func)) + + if (!func) goto unlock; + /* + * Enforce the order of the ops->func_stack and func->transition reads. + * The corresponding write barrier is in __klp_enable_patch(). + */ + smp_rmb(); + + if (unlikely(func->transition)) { + + /* + * Enforce the order of the func->transition and + * current->patch_state reads. Otherwise we could read an + * out-of-date task state and pick the wrong function. The + * corresponding write barriers are in klp_init_transition() + * and __klp_disable_patch(). + */ + smp_rmb(); + + patch_state = current->patch_state; + + WARN_ON_ONCE(patch_state == KLP_UNDEFINED); + + if (patch_state == KLP_UNPATCHED) { + /* + * Use the previously patched version of the function. + * If no previous patches exist, use the original + * function. + */ + func = list_entry_rcu(func->stack_node.next, + struct klp_func, stack_node); + + if (&func->stack_node == &ops->func_stack) + goto unlock; + } + } + klp_arch_set_pc(regs, (unsigned long)func->new_func); unlock: rcu_read_unlock(); @@ -211,3 +250,12 @@ int klp_patch_object(struct klp_object *obj) return 0; } + +void klp_unpatch_objects(struct klp_patch *patch) +{ + struct klp_object *obj; + + klp_for_each_object(patch, obj) + if (obj->patched) + klp_unpatch_object(obj); +} diff --git a/kernel/livepatch/patch.h b/kernel/livepatch/patch.h index 2d0cce0..0db2271 100644 --- a/kernel/livepatch/patch.h +++ b/kernel/livepatch/patch.h @@ -28,5 +28,6 @@ struct klp_ops *klp_find_ops(unsigned long old_addr); int klp_patch_object(struct klp_object *obj); void klp_unpatch_object(struct klp_object *obj); +void klp_unpatch_objects(struct klp_patch *patch); #endif /* _LIVEPATCH_PATCH_H */ diff --git a/kernel/livepatch/transition.c b/kernel/livepatch/transition.c new file mode 100644 index 0000000..4494fe6 --- /dev/null +++ b/kernel/livepatch/transition.c @@ -0,0 +1,479 @@ +/* + * transition.c - Kernel Live Patching transition functions + * + * Copyright (C) 2015-2016 Josh Poimboeuf <jpoimboe@redhat.com> + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; 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/>. + */ + +#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt + +#include <linux/cpu.h> +#include <linux/stacktrace.h> +#include "patch.h" +#include "transition.h" +#include "../sched/sched.h" + +#define MAX_STACK_ENTRIES 100 + +struct klp_patch *klp_transition_patch; + +static int klp_target_state = KLP_UNDEFINED; + +/* called from copy_process() during fork */ +void klp_copy_process(struct task_struct *child) +{ + child->patch_state = current->patch_state; + + /* TIF_PATCH_PENDING gets copied in setup_thread_stack() */ +} + +/* + * klp_update_patch_state() - change the patched state of a task + * @task: The task to change + * + * Switches the patched state of the task to the set of functions in the target + * patch state. + */ +void klp_update_patch_state(struct task_struct *task) +{ + /* + * The synchronize_rcu() call in klp_try_complete_transition() ensures + * this critical section completes before the global patch transition + * is considered complete so we don't have spurious patch_state updates + * afterwards. + */ + rcu_read_lock(); + + /* + * This test_and_clear_tsk_thread_flag() call also serves as a read + * barrier to enforce the order of the TIF_PATCH_PENDING and + * klp_target_state reads. The corresponding write barriers are in + * __klp_disable_patch() and klp_reverse_transition(). + */ + if (test_and_clear_tsk_thread_flag(task, TIF_PATCH_PENDING)) + task->patch_state = READ_ONCE(klp_target_state); + + rcu_read_unlock(); +} + +/* + * Initialize the global target patch state and all tasks to the initial patch + * state, and initialize all function transition states to true in preparation + * for patching or unpatching. + */ +void klp_init_transition(struct klp_patch *patch, int state) +{ + struct task_struct *g, *task; + unsigned int cpu; + struct klp_object *obj; + struct klp_func *func; + int initial_state = !state; + + WARN_ON_ONCE(klp_target_state != KLP_UNDEFINED); + + klp_transition_patch = patch; + + /* + * Set the global target patch state which tasks will switch to. This + * has no effect until the TIF_PATCH_PENDING flags get set later. + */ + klp_target_state = state; + + /* + * If the patch can be applied or reverted immediately, skip the + * per-task transitions. + */ + if (patch->immediate) + return; + + /* + * Initialize all tasks to the initial patch state to prepare them for + * switching to the target state. + */ + read_lock(&tasklist_lock); + for_each_process_thread(g, task) { + WARN_ON_ONCE(task->patch_state != KLP_UNDEFINED); + task->patch_state = initial_state; + } + read_unlock(&tasklist_lock); + + /* + * Ditto for the idle "swapper" tasks. + */ + get_online_cpus(); + for_each_online_cpu(cpu) { + task = idle_task(cpu); + WARN_ON_ONCE(task->patch_state != KLP_UNDEFINED); + task->patch_state = initial_state; + } + put_online_cpus(); + + /* + * Enforce the order of the task->patch_state initializations and the + * func->transition updates to ensure that, in the enable path, + * klp_ftrace_handler() doesn't see a func in transition with a + * task->patch_state of KLP_UNDEFINED. + */ + smp_wmb(); + + /* + * Set the func transition states so klp_ftrace_handler() will know to + * switch to the transition logic. + * + * When patching, the funcs aren't yet in the func_stack and will be + * made visible to the ftrace handler shortly by the calls to + * klp_patch_object(). + * + * When unpatching, the funcs are already in the func_stack and so are + * already visible to the ftrace handler. + */ + klp_for_each_object(patch, obj) + klp_for_each_func(obj, func) + func->transition = true; +} + +/* + * Start the transition to the specified target patch state so tasks can begin + * switching to it. + */ +void klp_start_transition(void) +{ + struct task_struct *g, *task; + unsigned int cpu; + + WARN_ON_ONCE(klp_target_state == KLP_UNDEFINED); + + pr_notice("'%s': %s...\n", klp_transition_patch->mod->name, + klp_target_state == KLP_PATCHED ? "patching" : "unpatching"); + + /* + * If the patch can be applied or reverted immediately, skip the + * per-task transitions. + */ + if (klp_transition_patch->immediate) + return; + + /* + * Mark all normal tasks as needing a patch state update. As they pass + * through the syscall barrier they'll switch over to the target state + * (unless we switch them in klp_try_complete_transition() first). + */ + read_lock(&tasklist_lock); + for_each_process_thread(g, task) + set_tsk_thread_flag(task, TIF_PATCH_PENDING); + read_unlock(&tasklist_lock); + + /* + * Ditto for the idle "swapper" tasks, though they never cross the + * syscall barrier. Instead they switch over in cpu_idle_loop(). + */ + get_online_cpus(); + for_each_online_cpu(cpu) + set_tsk_thread_flag(idle_task(cpu), TIF_PATCH_PENDING); + put_online_cpus(); +} + +/* + * The transition to the target patch state is complete. Clean up the data + * structures. + */ +void klp_complete_transition(void) +{ + struct klp_object *obj; + struct klp_func *func; + struct task_struct *g, *task; + unsigned int cpu; + + if (klp_transition_patch->immediate) + goto done; + + klp_for_each_object(klp_transition_patch, obj) + klp_for_each_func(obj, func) + func->transition = false; + + read_lock(&tasklist_lock); + for_each_process_thread(g, task) { + clear_tsk_thread_flag(task, TIF_PATCH_PENDING); + task->patch_state = KLP_UNDEFINED; + } + read_unlock(&tasklist_lock); + + get_online_cpus(); + for_each_online_cpu(cpu) { + task = idle_task(cpu); + clear_tsk_thread_flag(task, TIF_PATCH_PENDING); + task->patch_state = KLP_UNDEFINED; + } + put_online_cpus(); + +done: + klp_target_state = KLP_UNDEFINED; + klp_transition_patch = NULL; +} + +/* + * Determine whether the given stack trace includes any references to a + * to-be-patched or to-be-unpatched function. + */ +static int klp_check_stack_func(struct klp_func *func, + struct stack_trace *trace) +{ + unsigned long func_addr, func_size, address; + struct klp_ops *ops; + int i; + + if (func->immediate) + return 0; + + for (i = 0; i < trace->nr_entries; i++) { + address = trace->entries[i]; + + if (klp_target_state == KLP_UNPATCHED) { + /* + * Check for the to-be-unpatched function + * (the func itself). + */ + func_addr = (unsigned long)func->new_func; + func_size = func->new_size; + } else { + /* + * Check for the to-be-patched function + * (the previous func). + */ + ops = klp_find_ops(func->old_addr); + + if (list_is_singular(&ops->func_stack)) { + /* original function */ + func_addr = func->old_addr; + func_size = func->old_size; + } else { + /* previously patched function */ + struct klp_func *prev; + + prev = list_next_entry(func, stack_node); + func_addr = (unsigned long)prev->new_func; + func_size = prev->new_size; + } + } + + if (address >= func_addr && address < func_addr + func_size) + return -EAGAIN; + } + + return 0; +} + +/* + * Determine whether it's safe to transition the task to the target patch state + * by looking for any to-be-patched or to-be-unpatched functions on its stack. + */ +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); + WARN_ON_ONCE(ret == -ENOSYS); + if (ret) { + pr_debug("%s: %s:%d has an unreliable stack\n", + __func__, task->comm, task->pid); + return ret; + } + + klp_for_each_object(klp_transition_patch, obj) { + if (!obj->patched) + continue; + klp_for_each_func(obj, func) { + ret = klp_check_stack_func(func, &trace); + if (ret) { + pr_debug("%s: %s:%d is sleeping on function %s\n", + __func__, task->comm, task->pid, + func->old_name); + return ret; + } + } + } + + return 0; +} + +/* + * Try to safely switch a task to the target patch state. If it's currently + * running, or it's sleeping on a to-be-patched or to-be-unpatched function, or + * if the stack is unreliable, return false. + */ +static bool klp_try_switch_task(struct task_struct *task) +{ + struct rq *rq; + struct rq_flags flags; + int ret; + bool success = false; + + /* check if this task has already switched over */ + if (task->patch_state == klp_target_state) + return true; + + /* + * For arches which don't have reliable stack traces, we have to rely + * on other methods (e.g., switching tasks at the syscall barrier). + */ + if (!klp_have_reliable_stack()) + return false; + + /* + * Now try to check the stack for any to-be-patched or to-be-unpatched + * functions. If all goes well, switch the task to the target patch + * state. + */ + rq = task_rq_lock(task, &flags); + + if (task_running(rq, task) && task != current) { + pr_debug("%s: %s:%d is running\n", __func__, task->comm, + task->pid); + goto done; + } + + ret = klp_check_stack(task); + if (ret) + goto done; + + success = true; + + clear_tsk_thread_flag(task, TIF_PATCH_PENDING); + task->patch_state = klp_target_state; + +done: + task_rq_unlock(rq, task, &flags); + return success; +} + +/* + * Try to switch all remaining tasks to the target patch state by walking the + * stacks of sleeping tasks and looking for any to-be-patched or + * to-be-unpatched functions. If such functions are found, the task can't be + * switched yet. + * + * If any tasks are still stuck in the initial patch state, schedule a retry. + */ +bool klp_try_complete_transition(void) +{ + unsigned int cpu; + struct task_struct *g, *task; + bool complete = true; + + WARN_ON_ONCE(klp_target_state == KLP_UNDEFINED); + + /* + * If the patch can be applied or reverted immediately, skip the + * per-task transitions. + */ + if (klp_transition_patch->immediate) + goto success; + + /* + * Try to switch the tasks to the target patch state by walking their + * stacks and looking for any to-be-patched or to-be-unpatched + * functions. If such functions are found on a stack, or if the stack + * is deemed unreliable, the task can't be switched yet. + * + * Usually this will transition most (or all) of the tasks on a system + * unless the patch includes changes to a very common function. + */ + read_lock(&tasklist_lock); + for_each_process_thread(g, task) + if (!klp_try_switch_task(task)) + complete = false; + read_unlock(&tasklist_lock); + + /* + * Ditto for the idle "swapper" tasks. + */ + get_online_cpus(); + for_each_online_cpu(cpu) + if (!klp_try_switch_task(idle_task(cpu))) + complete = false; + put_online_cpus(); + + /* + * Some tasks weren't able to be switched over. Try again later and/or + * wait for other methods like syscall barrier switching. + */ + if (!complete) + return false; + +success: + + /* + * When unpatching, all tasks have transitioned to KLP_UNPATCHED so we + * can now remove the new functions from the func_stack. + */ + if (klp_target_state == KLP_UNPATCHED) + klp_unpatch_objects(klp_transition_patch); + + /* + * Wait for all RCU read-side critical sections to complete. + * + * This has two purposes: + * + * 1) Ensure all existing critical sections in klp_update_patch_state() + * complete, so task->patch_state won't be unexpectedly updated + * later. + * + * 2) When unpatching, don't allow any existing instances of + * klp_ftrace_handler() to access any obsolete funcs before we reset + * the func transition states to false. Otherwise the handler may + * see the deleted "new" func, see that it's not in transition, and + * wrongly pick the new version of the function. + */ + synchronize_rcu(); + + pr_notice("'%s': %s complete\n", klp_transition_patch->mod->name, + klp_target_state == KLP_PATCHED ? "patching" : "unpatching"); + + /* we're done, now cleanup the data structures */ + klp_complete_transition(); + + return true; +} + +/* + * This function can be called in the middle of an existing transition to + * reverse the direction of the target patch state. This can be done to + * effectively cancel an existing enable or disable operation if there are any + * tasks which are stuck in the initial patch state. + */ +void klp_reverse_transition(void) +{ + klp_transition_patch->enabled = !klp_transition_patch->enabled; + + klp_target_state = !klp_target_state; + + /* + * Enforce the order of the write to klp_target_state above and the + * TIF_PATCH_PENDING writes in klp_start_transition() to ensure that + * klp_update_patch_state() doesn't set a wrong task->patch_state. + */ + smp_wmb(); + + klp_start_transition(); +} + diff --git a/kernel/livepatch/transition.h b/kernel/livepatch/transition.h new file mode 100644 index 0000000..5191b96 --- /dev/null +++ b/kernel/livepatch/transition.h @@ -0,0 +1,14 @@ +#ifndef _LIVEPATCH_TRANSITION_H +#define _LIVEPATCH_TRANSITION_H + +#include <linux/livepatch.h> + +extern struct klp_patch *klp_transition_patch; + +void klp_init_transition(struct klp_patch *patch, int state); +void klp_start_transition(void); +void klp_reverse_transition(void); +bool klp_try_complete_transition(void); +void klp_complete_transition(void); + +#endif /* _LIVEPATCH_TRANSITION_H */ diff --git a/kernel/sched/idle.c b/kernel/sched/idle.c index 6a4bae0..a8b3f1a 100644 --- a/kernel/sched/idle.c +++ b/kernel/sched/idle.c @@ -9,6 +9,7 @@ #include <linux/mm.h> #include <linux/stackprotector.h> #include <linux/suspend.h> +#include <linux/livepatch.h> #include <asm/tlb.h> @@ -264,6 +265,9 @@ static void do_idle(void) sched_ttwu_pending(); schedule_preempt_disabled(); + + if (unlikely(klp_patch_pending(current))) + klp_update_patch_state(current); } bool cpu_in_idle(unsigned long pc) diff --git a/samples/livepatch/livepatch-sample.c b/samples/livepatch/livepatch-sample.c index e34f871..bb61c65 100644 --- a/samples/livepatch/livepatch-sample.c +++ b/samples/livepatch/livepatch-sample.c @@ -17,6 +17,8 @@ * along with this program; if not, see <http://www.gnu.org/licenses/>. */ +#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt + #include <linux/module.h> #include <linux/kernel.h> #include <linux/livepatch.h> @@ -69,6 +71,11 @@ static int livepatch_init(void) { int ret; + if (!klp_have_reliable_stack() && !patch.immediate) { + pr_notice("disabling consistency model!\n"); + patch.immediate = true; + } + ret = klp_register_patch(&patch); if (ret) return ret;
Change livepatch to use 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 or data semantics. This is the biggest remaining piece needed to make livepatch more generally useful. This code stems from the design proposal made by Vojtech [1] in November 2014. It's a hybrid of kGraft and kpatch: it uses kGraft's per-task consistency and syscall barrier switching combined with kpatch's stack trace switching. There are also a number of fallback options which make it quite flexible. Patches are applied on a per-task basis, when the task is deemed safe to switch over. When a patch is enabled, livepatch enters into a transition state where tasks are converging to the patched state. Usually this transition state can complete in a few seconds. The same sequence occurs when a patch is disabled, except the tasks converge from the patched state to the unpatched state. An interrupt handler inherits the patched state of the task it interrupts. The same is true for forked tasks: the child inherits the patched state of the parent. Livepatch uses several complementary approaches to determine when it's safe to patch tasks: 1. The first and most effective approach is stack checking of sleeping tasks. If no affected functions are on the stack of a given task, the task is patched. In most cases this will patch most or all of the tasks on the first try. Otherwise it'll keep trying periodically. This option is only available if the architecture has reliable stacks (HAVE_RELIABLE_STACKTRACE). 2. The second approach, if needed, is kernel exit switching. A task is switched when it returns to user space from a system call, a user space IRQ, or a signal. It's useful in the following cases: a) Patching I/O-bound user tasks which are sleeping on an affected function. In this case you have to send SIGSTOP and SIGCONT to force it to exit the kernel and be patched. b) Patching CPU-bound user tasks. If the task is highly CPU-bound then it will get patched the next time it gets interrupted by an IRQ. c) In the future it could be useful for applying patches for architectures which don't yet have HAVE_RELIABLE_STACKTRACE. In this case you would have to signal most of the tasks on the system. However this isn't supported yet because there's currently no way to patch kthreads without HAVE_RELIABLE_STACKTRACE. 3. For idle "swapper" tasks, since they don't ever exit the kernel, they instead have a klp_update_patch_state() call in the idle loop which allows them to be patched before the CPU enters the idle state. (Note there's not yet such an approach for kthreads.) All the above approaches may be skipped by setting the 'immediate' flag in the 'klp_patch' struct, which will disable per-task consistency and patch all tasks immediately. This can be useful if the patch doesn't change any function or data semantics. Note that, even with this flag set, it's possible that some tasks may still be running with an old version of the function, until that function returns. There's also an 'immediate' flag in the 'klp_func' struct which allows you to specify that certain functions in the patch can be applied without per-task consistency. This might be useful if you want to patch a common function like schedule(), and the function change doesn't need consistency but the rest of the patch does. For architectures which don't have HAVE_RELIABLE_STACKTRACE, the user must set patch->immediate which causes all tasks to be patched immediately. This option should be used with care, only when the patch doesn't change any function or data semantics. In the future, architectures which don't have HAVE_RELIABLE_STACKTRACE may be allowed to use per-task consistency if we can come up with another way to patch kthreads. 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 transition indefinitely, if any of the tasks are stuck in the initial patch state. 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 patch state. [1] https://lkml.kernel.org/r/20141107140458.GA21774@suse.cz Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com> --- Documentation/ABI/testing/sysfs-kernel-livepatch | 8 + Documentation/livepatch/livepatch.txt | 127 +++++- include/linux/init_task.h | 9 + include/linux/livepatch.h | 40 +- include/linux/sched.h | 3 + kernel/fork.c | 3 + kernel/livepatch/Makefile | 2 +- kernel/livepatch/core.c | 123 +++++- kernel/livepatch/patch.c | 50 ++- kernel/livepatch/patch.h | 1 + kernel/livepatch/transition.c | 479 +++++++++++++++++++++++ kernel/livepatch/transition.h | 14 + kernel/sched/idle.c | 4 + samples/livepatch/livepatch-sample.c | 7 + 14 files changed, 827 insertions(+), 43 deletions(-) create mode 100644 kernel/livepatch/transition.c create mode 100644 kernel/livepatch/transition.h