Yama: remove locking from delete path
Subsystems (2)
PATCH 1/1 Yama: remove locking from delete path
Instead of locking the list during a delete, mark entries as invalid and trigger a workqueue to clean them up. This lets us easily handle task_free from interrupt context.
--- security/yama/yama_lsm.c | 43 ++++++++++++++++++++++++++++++++++++------- 1 file changed, 36 insertions(+), 7 deletions(-)
security/yama/yama_lsm.c +36 -7
@@ -17,6 +17,7 @@#include <linux/ptrace.h> #include <linux/prctl.h> #include <linux/ratelimit.h> +#include <linux/workqueue.h> #define YAMA_SCOPE_DISABLED 0#define YAMA_SCOPE_RELATIONAL 1
@@ -29,6 +30,7 @@ static int ptrace_scope = YAMA_SCOPE_RELATIONAL;struct ptrace_relation {struct task_struct *tracer;struct task_struct *tracee; +bool invalid;struct list_head node;struct rcu_head rcu; };
@@ -36,6 +38,27 @@ struct ptrace_relation {static LIST_HEAD (ptracer_relations);static DEFINE_SPINLOCK (ptracer_relations_lock); +static void yama_relation_cleanup (struct work_struct *work); +static DECLARE_WORK(yama_relation_work, yama_relation_cleanup); + +/** +* yama_relation_cleanup - remove invalid entries from the relation list +* +*/ +static void yama_relation_cleanup (struct work_struct *work) +{ +struct ptrace_relation *relation; + +spin_lock (&ptracer_relations_lock); +list_for_each_entry_rcu (relation, &ptracer_relations, node) { +if (relation->invalid) { +list_del_rcu (&relation->node); +kfree_rcu (relation, rcu); + } + } +spin_unlock (&ptracer_relations_lock); +} +/** * yama_ptracer_add - add/replace an exception for this tracer/tracee pair * @tracer: the task_struct of the process doing the ptrace
@@ -57,9 +80,12 @@ static int yama_ptracer_add(struct task_struct *tracer, added->tracee = tracee; added->tracer = tracer; + added->invalid = false; -spin_lock_bh (&ptracer_relations_lock); +spin_lock (&ptracer_relations_lock);list_for_each_entry_rcu (relation, &ptracer_relations, node) { +if (relation->invalid) +continue ;if (relation->tracee == tracee) {list_replace_rcu (&relation->node, &added->node);kfree_rcu (relation, rcu);
@@ -70,7 +96,7 @@ static int yama_ptracer_add(struct task_struct *tracer,list_add_rcu (&added->node, &ptracer_relations); out: -spin_unlock_bh (&ptracer_relations_lock); +spin_unlock (&ptracer_relations_lock);return 0 ; }
@@ -84,15 +110,15 @@ static void yama_ptracer_del(struct task_struct *tracer, {struct ptrace_relation *relation; -spin_lock_bh (&ptracer_relations_lock);list_for_each_entry_rcu (relation, &ptracer_relations, node) { +if (relation->invalid) +continue ;if (relation->tracee == tracee || (tracer && relation->tracer == tracer)) { -list_del_rcu (&relation->node); -kfree_rcu (relation, rcu); + relation->invalid = true; +schedule_work (&yama_relation_work); } } -spin_unlock_bh (&ptracer_relations_lock); }/**
@@ -219,12 +245,15 @@ static int ptracer_exception_found(struct task_struct *tracer,rcu_read_lock ();if (!thread_group_leader (tracee)) tracee =rcu_dereference (tracee->group_leader); -list_for_each_entry_rcu (relation, &ptracer_relations, node) +list_for_each_entry_rcu (relation, &ptracer_relations, node) { +if (relation->invalid) +continue ;if (relation->tracee == tracee) { parent = relation->tracer; found = true;break ; } + }if (found && (parent ==NULL ||task_is_descendant (parent, tracer))) rc =1 ;
Signature · 6 lines
1.7.9.5 -- Kees Cook Chrome OS Security
James Morris
maintainerQuoted 6 lines · Kees Cook
Instead of locking the list during a delete, mark entries as invalid and trigger a workqueue to clean them up. This lets us easily handle
task_freefrom interrupt context.Cc Sasha Levin <[email protected]>Signed-off-by Kees Cook <[email protected]>
This doesn't apply cleanly to my -next branch.
Kees: can you think about using git to push changes to me for Yama?
Signature · 2 lines
James Morris <[email protected]>
Quoted 10 lines · James Morris
Quoted 6 lines · Kees Cook
Instead of locking the list during a delete, mark entries as invalid and trigger a workqueue to clean them up. This lets us easily handle
task_freefrom interrupt context.Cc Sasha Levin <[email protected]>Signed-off-by Kees Cook <[email protected]>This doesn't apply cleanly to my -next branch.
Did you already apply this from last week?
https://lkml.org/lkml/2012/11/13/808
Quoted 1 line
Kees: can you think about using git to push changes to me for Yama?
If this pace of changes keeps up, sure thing.
Thanks!
-Kees
Signature · 2 lines
Kees Cook Chrome OS Security
James Morris
maintainerQuoted 7 lines · Kees Cook
Quoted 6 lines · James Morris
Quoted 4 lines · Kees Cook
Instead of locking the list during a delete, mark entries as invalid and trigger a workqueue to clean them up. This lets us easily handle
task_freefrom interrupt context.
Quoted 7 lines
Quoted 4 lines
Quoted 2 lines
Cc Sasha Levin <[email protected]>Signed-off-by Kees Cook <[email protected]>This doesn't apply cleanly to my -next branch.
Did you already apply this from last week?
https://lkml.org/lkml/2012/11/13/808
Nope.
Quoted 4 lines
Quoted 2 lines
Kees: can you think about using git to push changes to me for Yama?
If this pace of changes keeps up, sure thing.
In any case, please check that your patches apply cleanly to my -next branch.
- James
Signature · 2 lines
James Morris <[email protected]>
Quoted 82 lines · Kees Cook
Instead of locking the list during a delete, mark entries as invalid and trigger a workqueue to clean them up. This lets us easily handle
task_freefrom interrupt context.Cc Sasha Levin <[email protected]>Signed-off-by Kees Cook <[email protected]>--- security/yama/yama_lsm.c | 43 ++++++++++++++++++++++++++++++++++++------- 1 file changed, 36 insertions(+), 7 deletions(-)security/yama/yama_lsm.c +28
-2@@ -17,6 +17,7 @@#include <linux/ptrace.h> #include <linux/prctl.h> #include <linux/ratelimit.h> +#include <linux/workqueue.h> #define YAMA_SCOPE_DISABLED 0#define YAMA_SCOPE_RELATIONAL 1@@ -29,6 +30,7 @@ static int ptrace_scope = YAMA_SCOPE_RELATIONAL;struct ptrace_relation {struct task_struct *tracer;struct task_struct *tracee; +bool invalid;struct list_head node;struct rcu_head rcu; };@@ -36,6 +38,27 @@ struct ptrace_relation {static LIST_HEAD (ptracer_relations);static DEFINE_SPINLOCK (ptracer_relations_lock); +static void yama_relation_cleanup (struct work_struct *work); +static DECLARE_WORK(yama_relation_work, yama_relation_cleanup); + +/** +* yama_relation_cleanup - remove invalid entries from the relation list +* +*/ +static void yama_relation_cleanup (struct work_struct *work) +{ +struct ptrace_relation *relation; + +spin_lock (&ptracer_relations_lock); +list_for_each_entry_rcu (relation, &ptracer_relations, node) { +if (relation->invalid) { +list_del_rcu (&relation->node); +kfree_rcu (relation, rcu); + } + } +spin_unlock (&ptracer_relations_lock); +} +/** * yama_ptracer_add - add/replace an exception for this tracer/tracee pair * @tracer: the task_struct of the process doing the ptrace @@ -57,9 +80,12 @@ static int yama_ptracer_add(struct task_struct *tracer, added->tracee = tracee; added->tracer = tracer; + added->invalid = false; -spin_lock_bh (&ptracer_relations_lock); +spin_lock (&ptracer_relations_lock);list_for_each_entry_rcu (relation, &ptracer_relations, node) { +if (relation->invalid) +continue ;if (relation->tracee == tracee) {list_replace_rcu (&relation->node, &added->node);kfree_rcu (relation, rcu);@@ -70,7 +96,7 @@ static int yama_ptracer_add(struct task_struct *tracer,list_add_rcu (&added->node, &ptracer_relations); out: -spin_unlock_bh (&ptracer_relations_lock); +spin_unlock (&ptracer_relations_lock);return 0 ; }
security/yama/yama_lsm.c static void yama_ptracer_del(struct task_struct *tracer, · line 87
Quoted 4 lines
security/yama/yama_lsm.c +0
-1@@ -84,15 +110,15 @@ static void yama_ptracer_del(struct task_struct *tracer, {struct ptrace_relation *relation; -spin_lock_bh (&ptracer_relations_lock);
I don't understand - is there a patch I don't have sitting around which puts the calls to yama_ptracer_del() under rcu_read_lock()? If not, I don't see how it's safe to walk the list here and risk racing against another yama_relation_cleanup() run.
I'm probably missing something really cool about the locking, but it doesn't look right to me. I would think you'd want to do the loop under rcu_read_lock(), set a boolean if one is changed, and call schedule_work() once at the end if the boolean is set.
Quoted 39 lines
security/yama/yama_lsm.c +8
-4list_for_each_entry_rcu (relation, &ptracer_relations, node) { +if (relation->invalid) +continue ;if (relation->tracee == tracee || (tracer && relation->tracer == tracer)) { -list_del_rcu (&relation->node); -kfree_rcu (relation, rcu); + relation->invalid = true; +schedule_work (&yama_relation_work); } } -spin_unlock_bh (&ptracer_relations_lock); }/** @@ -219,12 +245,15 @@ static int ptracer_exception_found(struct task_struct *tracer,rcu_read_lock ();if (!thread_group_leader (tracee)) tracee =rcu_dereference (tracee->group_leader); -list_for_each_entry_rcu (relation, &ptracer_relations, node) +list_for_each_entry_rcu (relation, &ptracer_relations, node) { +if (relation->invalid) +continue ;if (relation->tracee == tracee) { parent = relation->tracer; found = true;break ; } + }if (found && (parent ==NULL ||task_is_descendant (parent, tracer))) rc =1 ;Signature · 6 lines
1.7.9.5 -- Kees Cook Chrome OS Security
Quoted 93 lines · Serge Hallyn
Quoted 82 lines · Kees Cook
Instead of locking the list during a delete, mark entries as invalid and trigger a workqueue to clean them up. This lets us easily handle
task_freefrom interrupt context.Cc Sasha Levin <[email protected]>Signed-off-by Kees Cook <[email protected]>--- security/yama/yama_lsm.c | 43 ++++++++++++++++++++++++++++++++++++------- 1 file changed, 36 insertions(+), 7 deletions(-)security/yama/yama_lsm.c +28
-2@@ -17,6 +17,7 @@#include <linux/ptrace.h> #include <linux/prctl.h> #include <linux/ratelimit.h> +#include <linux/workqueue.h> #define YAMA_SCOPE_DISABLED 0#define YAMA_SCOPE_RELATIONAL 1@@ -29,6 +30,7 @@ static int ptrace_scope = YAMA_SCOPE_RELATIONAL;struct ptrace_relation {struct task_struct *tracer;struct task_struct *tracee; +bool invalid;struct list_head node;struct rcu_head rcu; };@@ -36,6 +38,27 @@ struct ptrace_relation {static LIST_HEAD (ptracer_relations);static DEFINE_SPINLOCK (ptracer_relations_lock); +static void yama_relation_cleanup (struct work_struct *work); +static DECLARE_WORK(yama_relation_work, yama_relation_cleanup); + +/** +* yama_relation_cleanup - remove invalid entries from the relation list +* +*/ +static void yama_relation_cleanup (struct work_struct *work) +{ +struct ptrace_relation *relation; + +spin_lock (&ptracer_relations_lock); +list_for_each_entry_rcu (relation, &ptracer_relations, node) { +if (relation->invalid) { +list_del_rcu (&relation->node); +kfree_rcu (relation, rcu); + } + } +spin_unlock (&ptracer_relations_lock); +} +/** * yama_ptracer_add - add/replace an exception for this tracer/tracee pair * @tracer: the task_struct of the process doing the ptrace @@ -57,9 +80,12 @@ static int yama_ptracer_add(struct task_struct *tracer, added->tracee = tracee; added->tracer = tracer; + added->invalid = false; -spin_lock_bh (&ptracer_relations_lock); +spin_lock (&ptracer_relations_lock);list_for_each_entry_rcu (relation, &ptracer_relations, node) { +if (relation->invalid) +continue ;if (relation->tracee == tracee) {list_replace_rcu (&relation->node, &added->node);kfree_rcu (relation, rcu);@@ -70,7 +96,7 @@ static int yama_ptracer_add(struct task_struct *tracer,list_add_rcu (&added->node, &ptracer_relations); out: -spin_unlock_bh (&ptracer_relations_lock); +spin_unlock (&ptracer_relations_lock);return 0 ; }security/yama/yama_lsm.c static void yama_ptracer_del(struct task_struct *tracer, · line 87
Quoted 4 lines
security/yama/yama_lsm.c +0
-1@@ -84,15 +110,15 @@ static void yama_ptracer_del(struct task_struct *tracer, {struct ptrace_relation *relation; -spin_lock_bh (&ptracer_relations_lock);I don't understand - is there a patch I don't have sitting around which puts the calls to
yama_ptracer_del()underrcu_read_lock()? If not, I don't see how it's safe to walk the list here and risk racing against anotheryama_relation_cleanup()run.
Quoted 5 lines
I'm probably missing something really cool about the locking, but it doesn't look right to me. I would think you'd want to do the loop under
rcu_read_lock(), set a boolean if one is changed, and callschedule_work()once at the end if the boolean is set.
Unless I'm mistaken and my lockdep tests are wrong, list_for_each_entry_rcu runs under rcu_read_lock().
I could optimize it to only run schedule_work() once all the marking is done at the end of the loop.
-Kees
Quoted 40 lines
Quoted 40 lines
security/yama/yama_lsm.c +8
-5list_for_each_entry_rcu (relation, &ptracer_relations, node) { +if (relation->invalid) +continue ;if (relation->tracee == tracee || (tracer && relation->tracer == tracer)) { -list_del_rcu (&relation->node); -kfree_rcu (relation, rcu); + relation->invalid = true; +schedule_work (&yama_relation_work); } } -spin_unlock_bh (&ptracer_relations_lock); }/** @@ -219,12 +245,15 @@ static int ptracer_exception_found(struct task_struct *tracer,rcu_read_lock ();if (!thread_group_leader (tracee)) tracee =rcu_dereference (tracee->group_leader); -list_for_each_entry_rcu (relation, &ptracer_relations, node) +list_for_each_entry_rcu (relation, &ptracer_relations, node) { +if (relation->invalid) +continue ;if (relation->tracee == tracee) { parent = relation->tracer; found = true;break ; } + }if (found && (parent ==NULL ||task_is_descendant (parent, tracer))) rc =1 ; --1.7.9.5
--
Kees Cook
Chrome OS Security
Signature · 2 lines
Kees Cook Chrome OS Security
Quoted 95 lines · Kees Cook
Quoted 93 lines · Serge Hallyn
Quoted 82 lines · Kees Cook
Instead of locking the list during a delete, mark entries as invalid and trigger a workqueue to clean them up. This lets us easily handle
task_freefrom interrupt context.Cc Sasha Levin <[email protected]>Signed-off-by Kees Cook <[email protected]>--- security/yama/yama_lsm.c | 43 ++++++++++++++++++++++++++++++++++++------- 1 file changed, 36 insertions(+), 7 deletions(-)security/yama/yama_lsm.c +28
-2@@ -17,6 +17,7 @@#include <linux/ptrace.h> #include <linux/prctl.h> #include <linux/ratelimit.h> +#include <linux/workqueue.h> #define YAMA_SCOPE_DISABLED 0#define YAMA_SCOPE_RELATIONAL 1@@ -29,6 +30,7 @@ static int ptrace_scope = YAMA_SCOPE_RELATIONAL;struct ptrace_relation {struct task_struct *tracer;struct task_struct *tracee; +bool invalid;struct list_head node;struct rcu_head rcu; };@@ -36,6 +38,27 @@ struct ptrace_relation {static LIST_HEAD (ptracer_relations);static DEFINE_SPINLOCK (ptracer_relations_lock); +static void yama_relation_cleanup (struct work_struct *work); +static DECLARE_WORK(yama_relation_work, yama_relation_cleanup); + +/** +* yama_relation_cleanup - remove invalid entries from the relation list +* +*/ +static void yama_relation_cleanup (struct work_struct *work) +{ +struct ptrace_relation *relation; + +spin_lock (&ptracer_relations_lock); +list_for_each_entry_rcu (relation, &ptracer_relations, node) { +if (relation->invalid) { +list_del_rcu (&relation->node); +kfree_rcu (relation, rcu); + } + } +spin_unlock (&ptracer_relations_lock); +} +/** * yama_ptracer_add - add/replace an exception for this tracer/tracee pair * @tracer: the task_struct of the process doing the ptrace @@ -57,9 +80,12 @@ static int yama_ptracer_add(struct task_struct *tracer, added->tracee = tracee; added->tracer = tracer; + added->invalid = false; -spin_lock_bh (&ptracer_relations_lock); +spin_lock (&ptracer_relations_lock);list_for_each_entry_rcu (relation, &ptracer_relations, node) { +if (relation->invalid) +continue ;if (relation->tracee == tracee) {list_replace_rcu (&relation->node, &added->node);kfree_rcu (relation, rcu);@@ -70,7 +96,7 @@ static int yama_ptracer_add(struct task_struct *tracer,list_add_rcu (&added->node, &ptracer_relations); out: -spin_unlock_bh (&ptracer_relations_lock); +spin_unlock (&ptracer_relations_lock);return 0 ; }security/yama/yama_lsm.c static void yama_ptracer_del(struct task_struct *tracer, · line 87
Quoted 4 lines
security/yama/yama_lsm.c +0
-1@@ -84,15 +110,15 @@ static void yama_ptracer_del(struct task_struct *tracer, {struct ptrace_relation *relation; -spin_lock_bh (&ptracer_relations_lock);I don't understand - is there a patch I don't have sitting around which puts the calls to
yama_ptracer_del()underrcu_read_lock()? If not, I don't see how it's safe to walk the list here and risk racing against anotheryama_relation_cleanup()run.
Quoted 8 lines
Quoted 5 lines
I'm probably missing something really cool about the locking, but it doesn't look right to me. I would think you'd want to do the loop under
rcu_read_lock(), set a boolean if one is changed, and callschedule_work()once at the end if the boolean is set.Unless I'm mistaken and my lockdep tests are wrong,
list_for_each_entry_rcuruns underrcu_read_lock().
Ew, yeah, no, the examples I was looking at are missing rcu_read_lock(). That's sad. Anyway, I'll fix this up here and in the other patch.
Quoted 2 lines
I could optimize it to only run
schedule_work()once all the marking is done at the end of the loop.
And I'll do this.
-Kees
Quoted 47 lines
-Kees
Quoted 37 lines
Quoted 37 lines
security/yama/yama_lsm.c +8
-5list_for_each_entry_rcu (relation, &ptracer_relations, node) { +if (relation->invalid) +continue ;if (relation->tracee == tracee || (tracer && relation->tracer == tracer)) { -list_del_rcu (&relation->node); -kfree_rcu (relation, rcu); + relation->invalid = true; +schedule_work (&yama_relation_work); } } -spin_unlock_bh (&ptracer_relations_lock); }/** @@ -219,12 +245,15 @@ static int ptracer_exception_found(struct task_struct *tracer,rcu_read_lock ();if (!thread_group_leader (tracee)) tracee =rcu_dereference (tracee->group_leader); -list_for_each_entry_rcu (relation, &ptracer_relations, node) +list_for_each_entry_rcu (relation, &ptracer_relations, node) { +if (relation->invalid) +continue ;if (relation->tracee == tracee) { parent = relation->tracer; found = true;break ; } + }if (found && (parent ==NULL ||task_is_descendant (parent, tracer))) rc =1 ; --1.7.9.5
Quoted 3 lines
Quoted 3 lines
--
Kees Cook
Chrome OS Security--
Kees Cook
Chrome OS Security
Signature · 2 lines
Kees Cook Chrome OS Security
security/yama/yama_lsm.c static int yama_ptracer_add(struct task_struct *tracer, · line 85
Quoted 12 lines · Kees Cook
Instead of locking the list during a delete, mark entries as invalid and trigger a workqueue to clean them up. This lets us easily handle
task_freefrom interrupt context.security/yama/yama_lsm.c +2
-1@@ -57,9 +80,12 @@ static int yama_ptracer_add(struct task_struct *tracer, added->tracee = tracee; added->tracer = tracer; + added->invalid = false; -spin_lock_bh (&ptracer_relations_lock); +spin_lock (&ptracer_relations_lock);
Can't you use
spin_lock_irqsave(&ptracer_relations_lock, flags); spin_unlock_irqrestore(&ptracer_relations_lock, flags);
instead of adding ->invalid ?
Quoted 11 lines · Tetsuo Handa
Quoted 10 lines · Kees Cook
Instead of locking the list during a delete, mark entries as invalid and trigger a workqueue to clean them up. This lets us easily handle
task_freefrom interrupt context.security/yama/yama_lsm.c +1
-0@@ -57,9 +80,12 @@ static int yama_ptracer_add(struct task_struct *tracer, added->tracee = tracee; added->tracer = tracer; + added->invalid = false;
Quoted 7 lines
security/yama/yama_lsm.c static int yama_ptracer_add(struct task_struct *tracer, · line 85
Quoted 2 lines
security/yama/yama_lsm.c +1
-1-spin_lock_bh (&ptracer_relations_lock); +spin_lock (&ptracer_relations_lock);Can't you use
spin_lock_irqsave(&ptracer_relations_lock, flags); spin_unlock_irqrestore(&ptracer_relations_lock, flags);instead of adding ->invalid ?
The _bh was sufficient originally, but looking at Sasha's deadlock, it seems like I should get rid of locking entirely on this path. What do you think of this report:
https://lkml.org/lkml/2012/10/17/600
I'm concerned that blocking interrupts would be an even more expensive solution, since every task_free() is forced to block interrupts briefly. Most systems will have either an empty relations list, or a very short one, so it seemed better to avoid any locking at all on the task_free() path. Now the locking contention would be moved to being between the workqueue and any add calls.
-Kees
-Kees
Signature · 2 lines
Kees Cook Chrome OS Security