livepatch: fix race between enabled_store() and klp_unregister_patch()
PATCH 1/1 livepatch: fix race between enabled_store() and klp_unregister_patch()
There is a potential race as following:
CPU0 | CPU1
-----------------------------|-----------------------------------
enabled_store() | klp_unregister_patch()
| |-mutex_lock(&klp_mutex);
|-mutex_lock(&klp_mutex); | |-klp_free_patch();
| |-mutex_unlock(&klp_mutex);
|-[process the patch's state]|
|-mutex_unlock(&klp_mutex) |Fix this race condition by adding klp_is_patch_registered() check in enabled_store() after get the lock klp_mutex.
--- kernel/livepatch/core.c | 5 +++++ 1 files changed, 5 insertions(+), 0 deletions(-)
kernel/livepatch/core.c +5 -0
@@ -614,6 +614,11 @@ static ssize_t enabled_store(struct kobject *kobj, struct kobj_attribute *attr,mutex_lock (&klp_mutex); +if (!klp_is_patch_registered (patch)) { + ret = -EINVAL ; + goto err; + } +if (val == patch->state) {/* already in requested state */ ret = -EINVAL ;
Signature · 1 line
1.7.1
Petr Mladek
maintainerQuoted 11 lines · Li Bin
There is a potential race as following:
CPU0 | CPU1 -----------------------------|----------------------------------- enabled_store() | klp_unregister_patch() | |-mutex_lock(&klp_mutex); |-mutex_lock(&klp_mutex); | |-klp_free_patch(); | |-mutex_unlock(&klp_mutex); |-[process the patch's state]| |-mutex_unlock(&klp_mutex) |
Quoted 2 lines
Fix this race condition by adding
klp_is_patch_registered()check inenabled_store()after get the lockklp_mutex.
It seems that you are right but the situation is more complicated. See below.
Quoted 11 lines
Signed-off-by Li Bin <[email protected]>--- kernel/livepatch/core.c | 5 +++++ 1 files changed, 5 insertions(+), 0 deletions(-)kernel/livepatch/core.c +0
-0
kernel/livepatch/core.c static ssize_t enabled_store(struct kobject *kobj, struct kobj_attribute *attr, · line 617
Quoted 4 lines
kernel/livepatch/core.c +1
-0@@ -614,6 +614,11 @@ static ssize_t enabled_store(struct kobject *kobj, struct kobj_attribute *attr,mutex_lock (&klp_mutex); +if (!klp_is_patch_registered (patch)) {
How is it guaranteed that "patch" is still a valid pointer, please?
I think that we also need to modify klp_unregister_patch(). It must not finish until the patch->kobj is destroyed. Otherwise, the patch module would get removed and the "patch" would be invalid.
I guess that enabled_store() takes reference of the patch->kobj. Then kobject_put(&patch->kobj) in klp_free_patch() decrements the refcount but it does not free the object. It means that it does not wait for enabled_store() to finish. I am not 100% sure because the kobject/sysfs code is quite complex.
Anyway, we should refuse to call klp_unregister_patch() at all in the current implementation. It is not safe because we do not know if the patch is still used or not.
Note that if you disable the patch, you are only sure that the new function will not longer be called. But you do _not_ know if all the existing calls have already finished. A process might sleep inside the function from the patch. I guess that it will be possible after we introduce a more complex consistency algorithm for switching the patches.
Best Regards,
Petr
Quoted 14 lines
kernel/livepatch/core.c +4
-0+ ret = -EINVAL ; + goto err; + } +if (val == patch->state) {/* already in requested state */ ret = -EINVAL ;Signature · 6 lines
1.7.1 -- To unsubscribe from this list: send the line "unsubscribe live-patching" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 11 lines · Li Bin
There is a potential race as following:
CPU0 | CPU1 -----------------------------|----------------------------------- enabled_store() | klp_unregister_patch() | |-mutex_lock(&klp_mutex); |-mutex_lock(&klp_mutex); | |-klp_free_patch(); | |-mutex_unlock(&klp_mutex); |-[process the patch's state]| |-mutex_unlock(&klp_mutex) |
Quoted 2 lines
Fix this race condition by adding
klp_is_patch_registered()check inenabled_store()after get the lockklp_mutex.
I'm thinking this race isn't possible, and that instead it would deadlock.
When I try to recreate something similar by putting a delay in enabled_store(), klp_free_patch() just sleeps on its call to kobject_put() until enabled_store() returns. The unregister stack looks like:
[<ffffffff812e966b>] __kernfs_remove+0x1fb/0x380 [<ffffffff812ea273>] kernfs_remove+0x23/0x40 [<ffffffff812ec601>] sysfs_remove_dir+0x51/0x80 [<ffffffff81407fb8>] kobject_del+0x18/0x50 [<ffffffff8140804a>] kobject_release+0x5a/0x190 [<ffffffff81407f27>] kobject_put+0x27/0x50 [<ffffffff81128d41>] klp_unregister_patch+0x71/0x80
It seems to be waiting on a lock which is held by the kernfs code which called enabled_store(). So when enabled_store() tries to get the klp_mutex, it deadlocks.
Miroslav and I previously discussed a few options to fix this:
https://lkml.kernel.org/r/[email protected]
Signature · 1 line
Josh
Hi Josh,
Quoted 12 lines · Josh Poimboeuf
Quoted 11 lines · Li Bin
There is a potential race as following:
CPU0 | CPU1 -----------------------------|----------------------------------- enabled_store() | klp_unregister_patch() | |-mutex_lock(&klp_mutex); |-mutex_lock(&klp_mutex); | |-klp_free_patch(); | |-mutex_unlock(&klp_mutex); |-[process the patch's state]| |-mutex_unlock(&klp_mutex) |
Quoted 4 lines
Quoted 2 lines
Fix this race condition by adding
klp_is_patch_registered()check inenabled_store()after get the lockklp_mutex.I'm thinking this race isn't possible, and that instead it would deadlock.
Good point. I did not consider the kernfs lock.
Quoted 13 lines
When I try to recreate something similar by putting a delay in
enabled_store(),klp_free_patch()just sleeps on its call tokobject_put()untilenabled_store()returns. The unregister stack looks like:[<ffffffff812e966b>] __kernfs_remove+0x1fb/0x380 [<ffffffff812ea273>] kernfs_remove+0x23/0x40 [<ffffffff812ec601>] sysfs_remove_dir+0x51/0x80 [<ffffffff81407fb8>] kobject_del+0x18/0x50 [<ffffffff8140804a>] kobject_release+0x5a/0x190 [<ffffffff81407f27>] kobject_put+0x27/0x50 [<ffffffff81128d41>] klp_unregister_patch+0x71/0x80
Quoted 7 lines
It seems to be waiting on a lock which is held by the kernfs code which called
enabled_store(). So whenenabled_store()tries to get theklp_mutex, it deadlocks.Miroslav and I previously discussed a few options to fix this:
Both the options seem good to me. I look forward to the patch. :) Thanks,
Li Bin
Quoted 11 lines · Josh Poimboeuf
When I try to recreate something similar by putting a delay in
enabled_store(),klp_free_patch()just sleeps on its call tokobject_put()untilenabled_store()returns. The unregister stack looks like:[<ffffffff812e966b>] __kernfs_remove+0x1fb/0x380 [<ffffffff812ea273>] kernfs_remove+0x23/0x40 [<ffffffff812ec601>] sysfs_remove_dir+0x51/0x80 [<ffffffff81407fb8>] kobject_del+0x18/0x50 [<ffffffff8140804a>] kobject_release+0x5a/0x190 [<ffffffff81407f27>] kobject_put+0x27/0x50
What about _put outside of klp_mutex in klp_unregister_patch (and maybe the other _put's as well)? Plus Li Bin's patch.
thanks,
Signature · 2 lines
js suse labs
Petr Mladek
maintainerQuoted 13 lines · Jiri Slaby
Quoted 11 lines · Josh Poimboeuf
When I try to recreate something similar by putting a delay in
enabled_store(),klp_free_patch()just sleeps on its call tokobject_put()untilenabled_store()returns. The unregister stack looks like:[<ffffffff812e966b>] __kernfs_remove+0x1fb/0x380 [<ffffffff812ea273>] kernfs_remove+0x23/0x40 [<ffffffff812ec601>] sysfs_remove_dir+0x51/0x80 [<ffffffff81407fb8>] kobject_del+0x18/0x50 [<ffffffff8140804a>] kobject_release+0x5a/0x190 [<ffffffff81407f27>] kobject_put+0x27/0x50
Quoted 2 lines
What about
_putoutside ofklp_mutexinklp_unregister_patch(and maybe the other _put's as well)? Plus Li Bin's patch.
This might work. But I am pretty sure that we would need to put also all the other kobject_puts outside of the lock.
I wondered how the approach with mutex_trylock() would look like and got the patch below.
It is not trivial but it still might be easier than moving all the kobject_put() calls. Also it should be easier to review because all the logic is on a single place.
What do you think?
Quoted 1 line
From
3eaec912f2700cd2a886ada1e7b4361ae192ef25Mon Sep 17 00:00:00 2001
From: Petr Mladek <[email protected]>
Date: Tue, 1 Dec 2015 13:25:34 +0100
Subject: [PATCH] livepatch: Avoid deadlock when unregistering and enabling a
patch
There is a possible deadlock between kobject_put() calls and enabled_store(), see the lockdep report below.
A solution would be to put all kobject without the klp_mutex and check if the patch is registered in enabled_store(). But this would make the unregister/free code even more scattered.
This patch takes the other possible approach. It uses trylock in enabled_store(). It the lock is not available and the patch is not registered, it is probably being removed. Anyway, there is nothing to do and enable_store() returns -EINVAL. If the lock is not available and the patch is registered, it tries harder to get it. It uses mutex_is_locked() in the busy loop to avoid the cache bouncing.
Lockdep report:
[ 69.512196] ======================================================
[ 69.513139] [ INFO: possible circular locking dependency detected ]
[ 69.513437] 4.4.0-rc3-4-default+ #2079 Tainted: G W E K
[ 69.513437] -------------------------------------------------------
[ 69.513437] rmmod/3786 is trying to acquire lock:
[ 69.513437] (s_active#99){++++.+}, at: [<ffffffff8127d4a3>] kernfs_remove+0x23/0x40
[ 69.513437]
but task is already holding lock:
[ 69.513437] (klp_mutex){+.+.+.}, at: [<ffffffff810de383>] klp_unregister_patch+0x23/0xc0
[ 69.513437]which lock already depends on the new lock.
[ 69.513437]
the existing dependency chain (in reverse order) is:
[ 69.513437]
-> #1 (klp_mutex){+.+.+.}:
[ 69.513437] [<ffffffff810bfd5d>] lock_acquire+0xad/0x130
[ 69.513437] [<ffffffff81916f04>] mutex_lock_nested+0x44/0x380
[ 69.513437] [<ffffffff810debe0>] enabled_store+0x50/0xc0
[ 69.513437] [<ffffffff813fa4ef>] kobj_attr_store+0xf/0x20
[ 69.513437] [<ffffffff8127ef44>] sysfs_kf_write+0x44/0x60
[ 69.513437] [<ffffffff8127e564>] kernfs_fop_write+0x144/0x190
[ 69.513437] [<ffffffff811fb648>] __vfs_write+0x28/0xe0
[ 69.513437] [<ffffffff811fbd02>] vfs_write+0xa2/0x1a0
[ 69.513437] [<ffffffff811fca19>] SyS_write+0x49/0xa0
[ 69.513437] [<ffffffff8191a2f2>] entry_SYSCALL_64_fastpath+0x12/0x76
[ 69.513437]
-> #0 (s_active#99){++++.+}:
[ 69.513437] [<ffffffff810beead>] __lock_acquire+0x14fd/0x1bd0
[ 69.513437] [<ffffffff810bfd5d>] lock_acquire+0xad/0x130
[ 69.513437] [<ffffffff8127c745>] __kernfs_remove+0x1f5/0x2b0
[ 69.513437] [<ffffffff8127d4a3>] kernfs_remove+0x23/0x40
[ 69.513437] [<ffffffff8127f881>] sysfs_remove_dir+0x51/0x80
[ 69.513437] [<ffffffff813fa6e8>] kobject_del+0x18/0x50
[ 69.513437] [<ffffffff813fa774>] kobject_cleanup+0x54/0x70
[ 69.513437] [<ffffffff813fa645>] kobject_put+0x25/0x50
[ 69.513437] [<ffffffff810de3f8>] klp_unregister_patch+0x98/0xc0
[ 69.513437] [<ffffffffa00000c5>] livepatch_exit+0x25/0xf60 [livepatch_sample]
[ 69.513437] [<ffffffff810fd21c>] SyS_delete_module+0x16c/0x1d0
[ 69.513437] [<ffffffff8191a2f2>] entry_SYSCALL_64_fastpath+0x12/0x76
[ 69.513437]other info that might help us debug this:
[ 69.513437] Possible unsafe locking scenario:
[ 69.513437] CPU0 CPU1 [ 69.513437] ---- ---- [ 69.513437] lock(klp_mutex); [ 69.513437] lock(s_active#99); [ 69.513437] lock(klp_mutex); [ 69.513437] lock(s_active#99); [ 69.513437] *** DEADLOCK ***
--- kernel/livepatch/core.c | 14 +++++++++++++- 1 file changed, 13 insertions(+), 1 deletion(-)
kernel/livepatch/core.c +13 -1
@@ -612,7 +612,19 @@ static ssize_t enabled_store(struct kobject *kobj, struct kobj_attribute *attr, patch = container_of(kobj, struct klp_patch, kobj); -mutex_lock (&klp_mutex); +/* +* Avoid a deadlock with kobject_put(&patch->kobj) that is +* called under klp_mutex. Bail out when the patch is not +* longer registered. +*/ +if (!mutex_trylock (&klp_mutex)) { +if (!klp_is_patch_registered (patch)) +return -EINVAL ; +/* Do not spin with trylock that bounce cache lines. */ +while (mutex_is_locked (&klp_mutex) && +klp_is_patch_registered (patch)) +cond_resched (); + }if (val == patch->state) {/* already in requested state */
Signature · 1 line
1.8.5.6
kernel/livepatch/core.c static ssize_t enabled_store(struct kobject *kobj, struct kobj_attribute *attr, · line 620
Quoted 13 lines · Petr Mladek
kernel/livepatch/core.c +6
-1@@ -612,7 +612,19 @@ static ssize_t enabled_store(struct kobject *kobj, struct kobj_attribute *attr, patch = container_of(kobj, struct klp_patch, kobj); -mutex_lock (&klp_mutex); +/* +* Avoid a deadlock with kobject_put(&patch->kobj) that is +* called under klp_mutex. Bail out when the patch is not +* longer registered. +*/ +if (!mutex_trylock (&klp_mutex)) {
This introduces false positives. Deleting/enabling/disabling/other_op_under_klp_mutex of an unrelated patch may now cause enabled_store to fail. Hence I don't like this approach at all.
thanks,
Signature · 2 lines
js suse labs
Petr Mladek
maintainerQuoted 7 lines · Jiri Slaby
Quoted 6 lines · Petr Mladek
kernel/livepatch/core.c +0
-0@@ -612,7 +612,19 @@ static ssize_t enabled_store(struct kobject *kobj, struct kobj_attribute *attr, patch = container_of(kobj, struct klp_patch, kobj);
Quoted 12 lines
kernel/livepatch/core.c static ssize_t enabled_store(struct kobject *kobj, struct kobj_attribute *attr, · line 620
Quoted 7 lines
kernel/livepatch/core.c +6
-1-mutex_lock (&klp_mutex); +/* +* Avoid a deadlock with kobject_put(&patch->kobj) that is +* called under klp_mutex. Bail out when the patch is not +* longer registered. +*/ +if (!mutex_trylock (&klp_mutex)) {This introduces false positives. Deleting/enabling/disabling/other_op_under_klp_mutex of an unrelated patch may now cause
enabled_storeto fail. Hence I don't like this approach at all.
Ah, there should have been
while (!mutex_trylock(&klp_mutex)) {
if (!klp_is_patch_registered(patch))
return -EINVAL;
/* Do not spin with trylock that bounce cache lines. */
while (mutex_is_locked(&klp_mutex) &&
klp_is_patch_registered(patch))
cond_resched();
}, so it should not produce false positives.
But I do not have a strong opinion about it.
Best Regards,
Petr
Quoted 13 lines · Jiri Slaby
Quoted 11 lines · Josh Poimboeuf
When I try to recreate something similar by putting a delay in
enabled_store(),klp_free_patch()just sleeps on its call tokobject_put()untilenabled_store()returns. The unregister stack looks like:[<ffffffff812e966b>] __kernfs_remove+0x1fb/0x380 [<ffffffff812ea273>] kernfs_remove+0x23/0x40 [<ffffffff812ec601>] sysfs_remove_dir+0x51/0x80 [<ffffffff81407fb8>] kobject_del+0x18/0x50 [<ffffffff8140804a>] kobject_release+0x5a/0x190 [<ffffffff81407f27>] kobject_put+0x27/0x50
Quoted 2 lines
What about
_putoutside ofklp_mutexinklp_unregister_patch(and maybe the other _put's as well)? Plus Li Bin's patch.
This approach sounds the best to me. I think all _put's for the patch kobj need to be outside the mutex. There's also a _put for the patch kobj in the klp_init_patch() error path which needs to be moved out.
I think the rest of the _put's (for object and func kobjs) are fine as they are, because they don't have corresponding sysfs functions which get the mutex.
Signature · 1 line
Josh
Miroslav Benes
maintainerHi,
[ sry for late responses. Two weeks of holiday and trying to go through all the emails... ]
Quoted 11 lines · Li Bin
There is a potential race as following:
CPU0 | CPU1 -----------------------------|----------------------------------- enabled_store() | klp_unregister_patch() | |-mutex_lock(&klp_mutex); |-mutex_lock(&klp_mutex); | |-klp_free_patch(); | |-mutex_unlock(&klp_mutex); |-[process the patch's state]| |-mutex_unlock(&klp_mutex) |
Quoted 4 lines
Fix this race condition by adding
klp_is_patch_registered()check inenabled_store()after get the lockklp_mutex.Signed-off-by Li Bin <[email protected]>
Well, I think all the relevant feedback was mentioned in other replies. I'll add my two cents here than to reply to the respective ones.
1. as Josh pointed out this is a potential deadlock situation between sysfs infrastructure and our unregister path. It has been already discussed [1] and some solutions were proposed [2].
2. if I am not missing something it is purely theoretical now. klp_unregister_patch is supposed to be called from module_exit function to clean up after the patch module. There is no way today how this function can be called. We take module reference (try_module_get() in klp_register_patch()) and we do not put it anywhere. Because we can't as Petr mentioned. Without a consistency model we cannot know if there is a task in a module code or not.
So I think we can postpone the solution till there is a consistency model.
Regards,
Miroslav
[1] https://lkml.kernel.org/r/[email protected]
[2]
1. rework klp_unregister_patch and move kobject_put out of mutex protected parts. This is what Jiri Slaby also proposed.
2. as Petr Mladek said we could use mutex_trylock instead of mutex_lock in enabled_store.
I've even had the solution prepared in one of my git branches since April so here it is just for the sake of completeness. It is based on Jiri Slaby's kgraft consistency model for klp and it is maybe a superset, but you get the idea.
-->8---
Quoted 1 line
From
b854b3feac2883f5b0a17ea7a5c83b4389fcd6adMon Sep 17 00:00:00 2001
From: Miroslav Benes <[email protected]>
Date: Thu, 2 Apr 2015 14:13:00 +0200
Subject: [PATCH] livepatch: allow removal of a disabled patch
Currently we do not allow patch module to unload since there is no method to determine if a task is still running in the patched code.
The consistency model gives us the way because when the patching finishes we know that all tasks were marked as safe to call a new patched function. Thus every new call to the function calls the new patched code and at the same time no task can be somewhere in the old code, because it had to leave that code to be marked as safe.
We can safely let the patch module go after that.
Completion is used for synchronization between module removal and sysfs infrastructure. Note that we still do not allow the removal for simple model, that is no consistency model.
With this change a call to try_module_get() is moved to __klp_enable_patch from klp_register_patch to make module reference counting symmetric (module_put() is in a patch disable path). Also mutex_lock() in enabled_store is changed to mutex_trylock() to prevent a deadlock situation when klp_unregister_patch is called and sysfs directories are removed.
--- include/linux/livepatch.h | 3 ++ kernel/livepatch/core.c | 70 ++++++++++++++++++++++++------------ samples/livepatch/livepatch-sample.c | 1 - 3 files changed, 51 insertions(+), 23 deletions(-)
include/linux/livepatch.h +3 -0
@@ -24,6 +24,7 @@#include <linux/module.h> #include <linux/ftrace.h> #include <linux/ptrace.h> +#include <linux/completion.h> #if IS_ENABLED (CONFIG_LIVEPATCH )
@@ -163,6 +164,7 @@ struct klp_object {* @kobj: kobject for sysfs resources * @state: tracks patch-level application state * @cmodel: cmodel_id's implementation +* @finish: for waiting till it is safe to remove the patch module */ struct klp_patch {/* external */
@@ -175,6 +177,7 @@ struct klp_patch {struct kobject kobj;enum klp_state state;struct klp_cmodel *cmodel; +struct completion finish; };#define klp_for_each_object (patch, obj) \
kernel/livepatch/core.c +48 -22
128 lines not on this page · raw message
samples/livepatch/livepatch-sample.c +0 -1
@@ -83,7 +83,6 @@ static int livepatch_init(void)static void livepatch_exit (void ) { -WARN_ON (klp_disable_patch (&patch));WARN_ON (klp_unregister_patch (&patch)); }
Signature · 1 line
2.1.4